Replace WTF::move with WTFMove
[WebKit-https.git] / Source / WebCore / contentextensions / Term.h
1 /*
2  * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #ifndef Term_h
27 #define Term_h
28
29 #if ENABLE(CONTENT_EXTENSIONS)
30
31 #include "ContentExtensionsDebugging.h"
32 #include "NFA.h"
33 #include <unicode/utypes.h>
34 #include <wtf/ASCIICType.h>
35 #include <wtf/HashMap.h>
36 #include <wtf/Vector.h>
37 #include <wtf/text/StringBuilder.h>
38 #include <wtf/text/WTFString.h>
39
40 namespace WebCore {
41
42 namespace ContentExtensions {
43
44 enum class AtomQuantifier : uint8_t {
45     One,
46     ZeroOrOne,
47     ZeroOrMore,
48     OneOrMore
49 };
50
51 class Term {
52 public:
53     Term();
54     Term(char character, bool isCaseSensitive);
55
56     enum UniversalTransitionTag { UniversalTransition };
57     explicit Term(UniversalTransitionTag);
58
59     enum CharacterSetTermTag { CharacterSetTerm };
60     explicit Term(CharacterSetTermTag, bool isInverted);
61
62     enum GroupTermTag { GroupTerm };
63     explicit Term(GroupTermTag);
64
65     enum EndOfLineAssertionTermTag { EndOfLineAssertionTerm };
66     explicit Term(EndOfLineAssertionTermTag);
67
68     Term(const Term& other);
69     Term(Term&& other);
70
71     enum EmptyValueTag { EmptyValue };
72     Term(EmptyValueTag);
73
74     ~Term();
75
76     bool isValid() const;
77
78     // CharacterSet terms only.
79     void addCharacter(UChar character, bool isCaseSensitive);
80
81     // Group terms only.
82     void extendGroupSubpattern(const Term&);
83
84     void quantify(const AtomQuantifier&);
85
86     ImmutableCharNFANodeBuilder generateGraph(NFA&, ImmutableCharNFANodeBuilder& source, const ActionList& finalActions) const;
87     void generateGraph(NFA&, ImmutableCharNFANodeBuilder& source, uint32_t destination) const;
88
89     bool isEndOfLineAssertion() const;
90
91     bool matchesAtLeastOneCharacter() const;
92
93     // Matches any string, the empty string included.
94     // This is very conservative. Patterns matching any string can return false here.
95     bool isKnownToMatchAnyString() const;
96
97     // Return true if the term can only match input of a single fixed length.
98     bool hasFixedLength() const;
99
100     Term& operator=(const Term& other);
101     Term& operator=(Term&& other);
102
103     bool operator==(const Term& other) const;
104
105     unsigned hash() const;
106
107     bool isEmptyValue() const;
108
109 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
110     String toString() const;
111 #endif
112
113 #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
114     size_t memoryUsed() const;
115 #endif
116     
117 private:
118     // This is exact for character sets but conservative for groups.
119     // The return value can be false for a group equivalent to a universal transition.
120     bool isUniversalTransition() const;
121
122     void generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source, const ImmutableCharNFANodeBuilder& destination) const;
123     void generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source, uint32_t destination) const;
124
125     void destroy();
126
127     enum class TermType : uint8_t {
128         Empty,
129         CharacterSet,
130         Group
131     };
132
133     TermType m_termType { TermType::Empty };
134     AtomQuantifier m_quantifier { AtomQuantifier::One };
135
136     class CharacterSet {
137     public:
138         void set(UChar character)
139         {
140             RELEASE_ASSERT(character < 128);
141             m_characters[character / 64] |= (uint64_t(1) << (character % 64));
142         }
143         
144         bool get(UChar character) const
145         {
146             RELEASE_ASSERT(character < 128);
147             return m_characters[character / 64] & (uint64_t(1) << (character % 64));
148         }
149         
150         void invert()
151         {
152             ASSERT(!m_inverted);
153             m_inverted = true;
154         }
155         
156         bool inverted() const { return m_inverted; }
157         
158         unsigned bitCount() const
159         {
160             return WTF::bitCount(m_characters[0]) + WTF::bitCount(m_characters[1]);
161         }
162         
163         bool operator==(const CharacterSet& other) const
164         {
165             return other.m_inverted == m_inverted
166                 && other.m_characters[0] == m_characters[0]
167                 && other.m_characters[1] == m_characters[1];
168         }
169
170         unsigned hash() const
171         {
172             return WTF::pairIntHash(WTF::pairIntHash(WTF::intHash(m_characters[0]), WTF::intHash(m_characters[1])), m_inverted);
173         }
174     private:
175         bool m_inverted { false };
176         uint64_t m_characters[2] { 0, 0 };
177     };
178
179     struct Group {
180         Vector<Term> terms;
181
182         bool operator==(const Group& other) const
183         {
184             return other.terms == terms;
185         }
186
187         unsigned hash() const
188         {
189             unsigned hash = 6421749;
190             for (const Term& term : terms) {
191                 unsigned termHash = term.hash();
192                 hash = (hash << 16) ^ ((termHash << 11) ^ hash);
193                 hash += hash >> 11;
194             }
195             return hash;
196         }
197     };
198
199     union AtomData {
200         AtomData()
201             : invalidTerm(0)
202         {
203         }
204         ~AtomData()
205         {
206         }
207
208         char invalidTerm;
209         CharacterSet characterSet;
210         Group group;
211     } m_atomData;
212 };
213
214 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
215 inline String quantifierToString(AtomQuantifier quantifier)
216 {
217     switch (quantifier) {
218     case AtomQuantifier::One:
219         return "";
220     case AtomQuantifier::ZeroOrOne:
221         return "?";
222     case AtomQuantifier::ZeroOrMore:
223         return "*";
224     case AtomQuantifier::OneOrMore:
225         return "+";
226     }
227 }
228     
229 inline String Term::toString() const
230 {
231     switch (m_termType) {
232     case TermType::Empty:
233         return "(Empty)";
234     case TermType::CharacterSet: {
235         StringBuilder builder;
236         builder.append('[');
237         for (UChar c = 0; c < 128; c++) {
238             if (m_atomData.characterSet.get(c)) {
239                 if (isASCIIPrintable(c) && !isASCIISpace(c))
240                     builder.append(c);
241                 else {
242                     builder.append('\\');
243                     builder.append('u');
244                     builder.appendNumber(c);
245                 }
246             }
247         }
248         builder.append(']');
249         builder.append(quantifierToString(m_quantifier));
250         return builder.toString();
251     }
252     case TermType::Group: {
253         StringBuilder builder;
254         builder.append('(');
255         for (const Term& term : m_atomData.group.terms)
256             builder.append(term.toString());
257         builder.append(')');
258         builder.append(quantifierToString(m_quantifier));
259         return builder.toString();
260     }
261     }
262 }
263 #endif
264
265 inline Term::Term()
266 {
267 }
268
269 inline Term::Term(char character, bool isCaseSensitive)
270     : m_termType(TermType::CharacterSet)
271 {
272     new (NotNull, &m_atomData.characterSet) CharacterSet();
273     addCharacter(character, isCaseSensitive);
274 }
275
276 inline Term::Term(UniversalTransitionTag)
277     : m_termType(TermType::CharacterSet)
278 {
279     new (NotNull, &m_atomData.characterSet) CharacterSet();
280     for (UChar i = 1; i < 128; ++i)
281         m_atomData.characterSet.set(i);
282 }
283
284 inline Term::Term(CharacterSetTermTag, bool isInverted)
285     : m_termType(TermType::CharacterSet)
286 {
287     new (NotNull, &m_atomData.characterSet) CharacterSet();
288     if (isInverted)
289         m_atomData.characterSet.invert();
290 }
291
292 inline Term::Term(GroupTermTag)
293     : m_termType(TermType::Group)
294 {
295     new (NotNull, &m_atomData.group) Group();
296 }
297
298 inline Term::Term(EndOfLineAssertionTermTag)
299     : Term(CharacterSetTerm, false)
300 {
301     m_atomData.characterSet.set(0);
302 }
303
304 inline Term::Term(const Term& other)
305     : m_termType(other.m_termType)
306     , m_quantifier(other.m_quantifier)
307 {
308     switch (m_termType) {
309     case TermType::Empty:
310         break;
311     case TermType::CharacterSet:
312         new (NotNull, &m_atomData.characterSet) CharacterSet(other.m_atomData.characterSet);
313         break;
314     case TermType::Group:
315         new (NotNull, &m_atomData.group) Group(other.m_atomData.group);
316         break;
317     }
318 }
319
320 inline Term::Term(Term&& other)
321     : m_termType(WTFMove(other.m_termType))
322     , m_quantifier(WTFMove(other.m_quantifier))
323 {
324     switch (m_termType) {
325     case TermType::Empty:
326         break;
327     case TermType::CharacterSet:
328         new (NotNull, &m_atomData.characterSet) CharacterSet(WTFMove(other.m_atomData.characterSet));
329         break;
330     case TermType::Group:
331         new (NotNull, &m_atomData.group) Group(WTFMove(other.m_atomData.group));
332         break;
333     }
334     other.destroy();
335 }
336
337 inline Term::Term(EmptyValueTag)
338     : m_termType(TermType::Empty)
339 {
340 }
341
342 inline Term::~Term()
343 {
344     destroy();
345 }
346
347 inline bool Term::isValid() const
348 {
349     return m_termType != TermType::Empty;
350 }
351
352 inline void Term::addCharacter(UChar character, bool isCaseSensitive)
353 {
354     ASSERT(isASCII(character));
355
356     ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::CharacterSet);
357     if (m_termType != TermType::CharacterSet)
358         return;
359
360     if (isCaseSensitive || !isASCIIAlpha(character))
361         m_atomData.characterSet.set(character);
362     else {
363         m_atomData.characterSet.set(toASCIIUpper(character));
364         m_atomData.characterSet.set(toASCIILower(character));
365     }
366 }
367
368 inline void Term::extendGroupSubpattern(const Term& term)
369 {
370     ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::Group);
371     if (m_termType != TermType::Group)
372         return;
373     m_atomData.group.terms.append(term);
374 }
375
376 inline void Term::quantify(const AtomQuantifier& quantifier)
377 {
378     ASSERT_WITH_MESSAGE(m_quantifier == AtomQuantifier::One, "Transition to quantified term should only happen once.");
379     m_quantifier = quantifier;
380 }
381
382 inline ImmutableCharNFANodeBuilder Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& source, const ActionList& finalActions) const
383 {
384     ImmutableCharNFANodeBuilder newEnd(nfa);
385     generateGraph(nfa, source, newEnd.nodeId());
386     newEnd.setActions(finalActions.begin(), finalActions.end());
387     return newEnd;
388 }
389
390 inline void Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& source, uint32_t destination) const
391 {
392     ASSERT(isValid());
393
394     switch (m_quantifier) {
395     case AtomQuantifier::One: {
396         generateSubgraphForAtom(nfa, source, destination);
397         break;
398     }
399     case AtomQuantifier::ZeroOrOne: {
400         generateSubgraphForAtom(nfa, source, destination);
401         source.addEpsilonTransition(destination);
402         break;
403     }
404     case AtomQuantifier::ZeroOrMore: {
405         ImmutableCharNFANodeBuilder repeatStart(nfa);
406         source.addEpsilonTransition(repeatStart);
407
408         ImmutableCharNFANodeBuilder repeatEnd(nfa);
409         generateSubgraphForAtom(nfa, repeatStart, repeatEnd);
410         repeatEnd.addEpsilonTransition(repeatStart);
411
412         repeatEnd.addEpsilonTransition(destination);
413         source.addEpsilonTransition(destination);
414         break;
415     }
416     case AtomQuantifier::OneOrMore: {
417         ImmutableCharNFANodeBuilder repeatStart(nfa);
418         source.addEpsilonTransition(repeatStart);
419
420         ImmutableCharNFANodeBuilder repeatEnd(nfa);
421         generateSubgraphForAtom(nfa, repeatStart, repeatEnd);
422         repeatEnd.addEpsilonTransition(repeatStart);
423
424         repeatEnd.addEpsilonTransition(destination);
425         break;
426     }
427     }
428 }
429
430 inline bool Term::isEndOfLineAssertion() const
431 {
432     return m_termType == TermType::CharacterSet && m_atomData.characterSet.bitCount() == 1 && m_atomData.characterSet.get(0);
433 }
434
435 inline bool Term::matchesAtLeastOneCharacter() const
436 {
437     ASSERT(isValid());
438
439     if (m_quantifier == AtomQuantifier::ZeroOrOne || m_quantifier == AtomQuantifier::ZeroOrMore)
440         return false;
441     if (isEndOfLineAssertion())
442         return false;
443
444     if (m_termType == TermType::Group) {
445         for (const Term& term : m_atomData.group.terms) {
446             if (term.matchesAtLeastOneCharacter())
447                 return true;
448         }
449         return false;
450     }
451     return true;
452 }
453
454 inline bool Term::isKnownToMatchAnyString() const
455 {
456     ASSERT(isValid());
457
458     switch (m_termType) {
459     case TermType::Empty:
460         ASSERT_NOT_REACHED();
461         break;
462     case TermType::CharacterSet:
463         // ".*" is the only simple term matching any string.
464         return isUniversalTransition() && m_quantifier == AtomQuantifier::ZeroOrMore;
465         break;
466     case TermType::Group: {
467         // There are infinitely many ways to match anything with groups, we just handle simple cases
468         if (m_atomData.group.terms.size() != 1)
469             return false;
470
471         const Term& firstTermInGroup = m_atomData.group.terms.first();
472         // -(.*) with any quantifier.
473         if (firstTermInGroup.isKnownToMatchAnyString())
474             return true;
475
476         if (firstTermInGroup.isUniversalTransition()) {
477             // -(.)*, (.+)*, (.?)* etc.
478             if (m_quantifier == AtomQuantifier::ZeroOrMore)
479                 return true;
480
481             // -(.+)?.
482             if (m_quantifier == AtomQuantifier::ZeroOrOne && firstTermInGroup.m_quantifier == AtomQuantifier::OneOrMore)
483                 return true;
484
485             // -(.?)+.
486             if (m_quantifier == AtomQuantifier::OneOrMore && firstTermInGroup.m_quantifier == AtomQuantifier::ZeroOrOne)
487                 return true;
488         }
489         break;
490     }
491     }
492     return false;
493 }
494
495 inline bool Term::hasFixedLength() const
496 {
497     ASSERT(isValid());
498
499     switch (m_termType) {
500     case TermType::Empty:
501         ASSERT_NOT_REACHED();
502         break;
503     case TermType::CharacterSet:
504         return m_quantifier == AtomQuantifier::One;
505     case TermType::Group: {
506         if (m_quantifier != AtomQuantifier::One)
507             return false;
508         for (const Term& term : m_atomData.group.terms) {
509             if (!term.hasFixedLength())
510                 return false;
511         }
512         return true;
513     }
514     }
515     return false;
516 }
517
518 inline Term& Term::operator=(const Term& other)
519 {
520     destroy();
521     new (NotNull, this) Term(other);
522     return *this;
523 }
524
525 inline Term& Term::operator=(Term&& other)
526 {
527     destroy();
528     new (NotNull, this) Term(WTFMove(other));
529     return *this;
530 }
531
532 inline bool Term::operator==(const Term& other) const
533 {
534     if (other.m_termType != m_termType || other.m_quantifier != m_quantifier)
535         return false;
536
537     switch (m_termType) {
538     case TermType::Empty:
539         return true;
540     case TermType::CharacterSet:
541         return m_atomData.characterSet == other.m_atomData.characterSet;
542     case TermType::Group:
543         return m_atomData.group == other.m_atomData.group;
544     }
545     ASSERT_NOT_REACHED();
546     return false;
547 }
548
549 inline unsigned Term::hash() const
550 {
551     unsigned primary = static_cast<unsigned>(m_termType) << 16 | static_cast<unsigned>(m_quantifier);
552     unsigned secondary = 0;
553     switch (m_termType) {
554     case TermType::Empty:
555         secondary = 52184393;
556         break;
557     case TermType::CharacterSet:
558         secondary = m_atomData.characterSet.hash();
559         break;
560     case TermType::Group:
561         secondary = m_atomData.group.hash();
562         break;
563     }
564     return WTF::pairIntHash(primary, secondary);
565 }
566
567 inline bool Term::isEmptyValue() const
568 {
569     return m_termType == TermType::Empty;
570 }
571
572 inline bool Term::isUniversalTransition() const
573 {
574     ASSERT(isValid());
575
576     switch (m_termType) {
577     case TermType::Empty:
578         ASSERT_NOT_REACHED();
579         break;
580     case TermType::CharacterSet:
581         return (m_atomData.characterSet.inverted() && !m_atomData.characterSet.bitCount())
582             || (!m_atomData.characterSet.inverted() && m_atomData.characterSet.bitCount() == 127 && !m_atomData.characterSet.get(0));
583     case TermType::Group:
584         return m_atomData.group.terms.size() == 1 && m_atomData.group.terms.first().isUniversalTransition();
585     }
586     return false;
587 }
588
589 inline void Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source, const ImmutableCharNFANodeBuilder& destination) const
590 {
591     generateSubgraphForAtom(nfa, source, destination.nodeId());
592 }
593
594 inline void Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source, uint32_t destination) const
595 {
596     switch (m_termType) {
597     case TermType::Empty:
598         ASSERT_NOT_REACHED();
599         source.addEpsilonTransition(destination);
600         break;
601     case TermType::CharacterSet: {
602         if (!m_atomData.characterSet.inverted()) {
603             UChar i = 0;
604             while (true) {
605                 while (i < 128 && !m_atomData.characterSet.get(i))
606                     ++i;
607                 if (i == 128)
608                     break;
609
610                 UChar start = i;
611                 ++i;
612                 while (i < 128 && m_atomData.characterSet.get(i))
613                     ++i;
614                 source.addTransition(start, i - 1, destination);
615             }
616         } else {
617             UChar i = 1;
618             while (true) {
619                 while (i < 128 && m_atomData.characterSet.get(i))
620                     ++i;
621                 if (i == 128)
622                     break;
623
624                 UChar start = i;
625                 ++i;
626                 while (i < 128 && !m_atomData.characterSet.get(i))
627                     ++i;
628                 source.addTransition(start, i - 1, destination);
629             }
630         }
631         break;
632     }
633     case TermType::Group: {
634         if (m_atomData.group.terms.isEmpty()) {
635             // FIXME: any kind of empty term could be avoided in the parser. This case should turned into an assertion.
636             source.addEpsilonTransition(destination);
637             return;
638         }
639
640         if (m_atomData.group.terms.size() == 1) {
641             m_atomData.group.terms.first().generateGraph(nfa, source, destination);
642             return;
643         }
644
645         ImmutableCharNFANodeBuilder lastTarget = m_atomData.group.terms.first().generateGraph(nfa, source, ActionList());
646         for (unsigned i = 1; i < m_atomData.group.terms.size() - 1; ++i) {
647             const Term& currentTerm = m_atomData.group.terms[i];
648             ImmutableCharNFANodeBuilder newNode = currentTerm.generateGraph(nfa, lastTarget, ActionList());
649             lastTarget = WTFMove(newNode);
650         }
651         const Term& lastTerm = m_atomData.group.terms.last();
652         lastTerm.generateGraph(nfa, lastTarget, destination);
653         break;
654     }
655     }
656 }
657
658 inline void Term::destroy()
659 {
660     switch (m_termType) {
661     case TermType::Empty:
662         break;
663     case TermType::CharacterSet:
664         m_atomData.characterSet.~CharacterSet();
665         break;
666     case TermType::Group:
667         m_atomData.group.~Group();
668         break;
669     }
670     m_termType = TermType::Empty;
671 }
672
673 #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
674 inline size_t Term::memoryUsed() const
675 {
676     size_t extraMemory = 0;
677     if (m_termType == TermType::Group) {
678         for (const Term& term : m_atomData.group.terms)
679             extraMemory += term.memoryUsed();
680     }
681     return sizeof(Term) + extraMemory;
682 }
683 #endif
684
685 } // namespace ContentExtensions
686 } // namespace WebCore
687
688 #endif // ENABLE(CONTENT_EXTENSIONS)
689
690 #endif // Term_h