[Content Extensions] Add CombinedURLFilters debugging code.
[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     enum DeletedValueTag { DeletedValue };
75     Term(DeletedValueTag);
76
77     ~Term();
78
79     bool isValid() const;
80
81     // CharacterSet terms only.
82     void addCharacter(UChar character, bool isCaseSensitive);
83
84     // Group terms only.
85     void extendGroupSubpattern(const Term&);
86
87     void quantify(const AtomQuantifier&);
88
89     unsigned generateGraph(NFA&, unsigned start, const ActionList& finalActions) const;
90
91     bool isEndOfLineAssertion() const;
92
93     bool matchesAtLeastOneCharacter() const;
94
95     // Matches any string, the empty string included.
96     // This is very conservative. Patterns matching any string can return false here.
97     bool isKnownToMatchAnyString() const;
98
99     // Return true if the term can only match input of a single fixed length.
100     bool hasFixedLength() const;
101
102     Term& operator=(const Term& other);
103     Term& operator=(Term&& other);
104
105     bool operator==(const Term& other) const;
106
107     unsigned hash() const;
108
109     bool isEmptyValue() const;
110     bool isDeletedValue() const;
111
112 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
113     String toString() const;
114 #endif
115     
116 private:
117     // This is exact for character sets but conservative for groups.
118     // The return value can be false for a group equivalent to a universal transition.
119     bool isUniversalTransition() const;
120
121     unsigned generateSubgraphForAtom(NFA&, unsigned source) const;
122
123     void destroy();
124
125     enum class TermType : uint8_t {
126         Empty,
127         Deleted,
128         CharacterSet,
129         Group
130     };
131
132     TermType m_termType { TermType::Empty };
133     AtomQuantifier m_quantifier { AtomQuantifier::One };
134
135     class CharacterSet {
136     public:
137         void set(UChar character)
138         {
139             RELEASE_ASSERT(character < 128);
140             m_characters[character / 64] |= (uint64_t(1) << (character % 64));
141         }
142         
143         bool get(UChar character) const
144         {
145             RELEASE_ASSERT(character < 128);
146             return m_characters[character / 64] & (uint64_t(1) << (character % 64));
147         }
148         
149         void invert()
150         {
151             ASSERT(!m_inverted);
152             m_inverted = true;
153         }
154         
155         bool inverted() const { return m_inverted; }
156         
157         unsigned bitCount() const
158         {
159             return WTF::bitCount(m_characters[0]) + WTF::bitCount(m_characters[1]);
160         }
161         
162         bool operator==(const CharacterSet& other) const
163         {
164             return other.m_inverted == m_inverted
165                 && other.m_characters[0] == m_characters[0]
166                 && other.m_characters[1] == m_characters[1];
167         }
168
169         unsigned hash() const
170         {
171             return WTF::pairIntHash(WTF::pairIntHash(WTF::intHash(m_characters[0]), WTF::intHash(m_characters[1])), m_inverted);
172         }
173     private:
174         bool m_inverted { false };
175         uint64_t m_characters[2] { 0, 0 };
176     };
177
178     struct Group {
179         Vector<Term> terms;
180
181         bool operator==(const Group& other) const
182         {
183             return other.terms == terms;
184         }
185
186         unsigned hash() const
187         {
188             unsigned hash = 6421749;
189             for (const Term& term : terms) {
190                 unsigned termHash = term.hash();
191                 hash = (hash << 16) ^ ((termHash << 11) ^ hash);
192                 hash += hash >> 11;
193             }
194             return hash;
195         }
196     };
197
198     union AtomData {
199         AtomData()
200             : invalidTerm(0)
201         {
202         }
203         ~AtomData()
204         {
205         }
206
207         char invalidTerm;
208         CharacterSet characterSet;
209         Group group;
210     } m_atomData;
211 };
212
213 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
214 inline String quantifierToString(AtomQuantifier quantifier)
215 {
216     switch (quantifier) {
217     case AtomQuantifier::One:
218         return "";
219     case AtomQuantifier::ZeroOrOne:
220         return "?";
221     case AtomQuantifier::ZeroOrMore:
222         return "*";
223     case AtomQuantifier::OneOrMore:
224         return "+";
225     }
226 }
227     
228 inline String Term::toString() const
229 {
230     switch (m_termType) {
231     case TermType::Empty:
232         return "(Empty)";
233     case TermType::Deleted:
234         return "(Deleted)";
235     case TermType::CharacterSet: {
236         StringBuilder builder;
237         builder.append('[');
238         for (UChar c = 0; c < 128; c++) {
239             if (m_atomData.characterSet.get(c)) {
240                 if (isASCIIPrintable(c) && !isASCIISpace(c))
241                     builder.append(c);
242                 else {
243                     builder.append('\\');
244                     builder.append('u');
245                     builder.appendNumber(c);
246                 }
247             }
248         }
249         builder.append(']');
250         builder.append(quantifierToString(m_quantifier));
251         return builder.toString();
252     }
253     case TermType::Group: {
254         StringBuilder builder;
255         builder.append('(');
256         for (const Term& term : m_atomData.group.terms)
257             builder.append(term.toString());
258         builder.append(')');
259         builder.append(quantifierToString(m_quantifier));
260         return builder.toString();
261     }
262     }
263 }
264 #endif
265     
266 struct TermHash {
267     static unsigned hash(const Term& term) { return term.hash(); }
268     static bool equal(const Term& a, const Term& b) { return a == b; }
269     static const bool safeToCompareToEmptyOrDeleted = true;
270 };
271
272 struct TermHashTraits : public WTF::CustomHashTraits<Term> { };
273
274 inline Term::Term()
275 {
276 }
277
278 inline Term::Term(char character, bool isCaseSensitive)
279     : m_termType(TermType::CharacterSet)
280 {
281     new (NotNull, &m_atomData.characterSet) CharacterSet();
282     addCharacter(character, isCaseSensitive);
283 }
284
285 inline Term::Term(UniversalTransitionTag)
286     : m_termType(TermType::CharacterSet)
287 {
288     new (NotNull, &m_atomData.characterSet) CharacterSet();
289     for (UChar i = 0; i < 128; ++i)
290         m_atomData.characterSet.set(i);
291 }
292
293 inline Term::Term(CharacterSetTermTag, bool isInverted)
294     : m_termType(TermType::CharacterSet)
295 {
296     new (NotNull, &m_atomData.characterSet) CharacterSet();
297     if (isInverted)
298         m_atomData.characterSet.invert();
299 }
300
301 inline Term::Term(GroupTermTag)
302     : m_termType(TermType::Group)
303 {
304     new (NotNull, &m_atomData.group) Group();
305 }
306
307 inline Term::Term(EndOfLineAssertionTermTag)
308     : Term(CharacterSetTerm, false)
309 {
310     m_atomData.characterSet.set(0);
311 }
312
313 inline Term::Term(const Term& other)
314     : m_termType(other.m_termType)
315     , m_quantifier(other.m_quantifier)
316 {
317     switch (m_termType) {
318     case TermType::Empty:
319     case TermType::Deleted:
320         break;
321     case TermType::CharacterSet:
322         new (NotNull, &m_atomData.characterSet) CharacterSet(other.m_atomData.characterSet);
323         break;
324     case TermType::Group:
325         new (NotNull, &m_atomData.group) Group(other.m_atomData.group);
326         break;
327     }
328 }
329
330 inline Term::Term(Term&& other)
331     : m_termType(WTF::move(other.m_termType))
332     , m_quantifier(WTF::move(other.m_quantifier))
333 {
334     switch (m_termType) {
335     case TermType::Empty:
336     case TermType::Deleted:
337         break;
338     case TermType::CharacterSet:
339         new (NotNull, &m_atomData.characterSet) CharacterSet(WTF::move(other.m_atomData.characterSet));
340         break;
341     case TermType::Group:
342         new (NotNull, &m_atomData.group) Group(WTF::move(other.m_atomData.group));
343         break;
344     }
345     other.destroy();
346 }
347
348 inline Term::Term(EmptyValueTag)
349     : m_termType(TermType::Empty)
350 {
351 }
352
353 inline Term::Term(DeletedValueTag)
354     : m_termType(TermType::Deleted)
355 {
356 }
357
358 inline Term::~Term()
359 {
360     destroy();
361 }
362
363 inline bool Term::isValid() const
364 {
365     return m_termType != TermType::Empty && m_termType != TermType::Deleted;
366 }
367
368 inline void Term::addCharacter(UChar character, bool isCaseSensitive)
369 {
370     ASSERT(isASCII(character));
371
372     ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::CharacterSet);
373     if (m_termType != TermType::CharacterSet)
374         return;
375
376     if (isCaseSensitive || !isASCIIAlpha(character))
377         m_atomData.characterSet.set(character);
378     else {
379         m_atomData.characterSet.set(toASCIIUpper(character));
380         m_atomData.characterSet.set(toASCIILower(character));
381     }
382 }
383
384 inline void Term::extendGroupSubpattern(const Term& term)
385 {
386     ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::Group);
387     if (m_termType != TermType::Group)
388         return;
389     m_atomData.group.terms.append(term);
390 }
391
392 inline void Term::quantify(const AtomQuantifier& quantifier)
393 {
394     ASSERT_WITH_MESSAGE(m_quantifier == AtomQuantifier::One, "Transition to quantified term should only happen once.");
395     m_quantifier = quantifier;
396 }
397
398 inline unsigned Term::Term::generateGraph(NFA& nfa, unsigned start, const ActionList& finalActions) const
399 {
400     ASSERT(isValid());
401
402     unsigned newEnd;
403
404     switch (m_quantifier) {
405     case AtomQuantifier::One: {
406         newEnd = generateSubgraphForAtom(nfa, start);
407         break;
408     }
409     case AtomQuantifier::ZeroOrOne: {
410         newEnd = generateSubgraphForAtom(nfa, start);
411         nfa.addEpsilonTransition(start, newEnd);
412         break;
413     }
414     case AtomQuantifier::ZeroOrMore: {
415         unsigned repeatStart = nfa.createNode();
416         nfa.addEpsilonTransition(start, repeatStart);
417
418         unsigned repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
419         nfa.addEpsilonTransition(repeatEnd, repeatStart);
420
421         unsigned kleenEnd = nfa.createNode();
422         nfa.addEpsilonTransition(repeatEnd, kleenEnd);
423         nfa.addEpsilonTransition(start, kleenEnd);
424         newEnd = kleenEnd;
425         break;
426     }
427     case AtomQuantifier::OneOrMore: {
428         unsigned repeatStart = nfa.createNode();
429         nfa.addEpsilonTransition(start, repeatStart);
430
431         unsigned repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
432         nfa.addEpsilonTransition(repeatEnd, repeatStart);
433
434         unsigned afterRepeat = nfa.createNode();
435         nfa.addEpsilonTransition(repeatEnd, afterRepeat);
436         newEnd = afterRepeat;
437         break;
438     }
439     }
440     nfa.setActions(newEnd, finalActions);
441     return newEnd;
442 }
443
444 inline bool Term::isEndOfLineAssertion() const
445 {
446     return m_termType == TermType::CharacterSet && m_atomData.characterSet.bitCount() == 1 && m_atomData.characterSet.get(0);
447 }
448
449 inline bool Term::matchesAtLeastOneCharacter() const
450 {
451     ASSERT(isValid());
452
453     if (m_quantifier == AtomQuantifier::ZeroOrOne || m_quantifier == AtomQuantifier::ZeroOrMore)
454         return false;
455     if (isEndOfLineAssertion())
456         return false;
457
458     if (m_termType == TermType::Group) {
459         for (const Term& term : m_atomData.group.terms) {
460             if (term.matchesAtLeastOneCharacter())
461                 return true;
462         }
463         return false;
464     }
465     return true;
466 }
467
468 inline bool Term::isKnownToMatchAnyString() const
469 {
470     ASSERT(isValid());
471
472     switch (m_termType) {
473     case TermType::Empty:
474     case TermType::Deleted:
475         ASSERT_NOT_REACHED();
476         break;
477     case TermType::CharacterSet:
478         // ".*" is the only simple term matching any string.
479         return isUniversalTransition() && m_quantifier == AtomQuantifier::ZeroOrMore;
480         break;
481     case TermType::Group: {
482         // There are infinitely many ways to match anything with groups, we just handle simple cases
483         if (m_atomData.group.terms.size() != 1)
484             return false;
485
486         const Term& firstTermInGroup = m_atomData.group.terms.first();
487         // -(.*) with any quantifier.
488         if (firstTermInGroup.isKnownToMatchAnyString())
489             return true;
490
491         if (firstTermInGroup.isUniversalTransition()) {
492             // -(.)*, (.+)*, (.?)* etc.
493             if (m_quantifier == AtomQuantifier::ZeroOrMore)
494                 return true;
495
496             // -(.+)?.
497             if (m_quantifier == AtomQuantifier::ZeroOrOne && firstTermInGroup.m_quantifier == AtomQuantifier::OneOrMore)
498                 return true;
499
500             // -(.?)+.
501             if (m_quantifier == AtomQuantifier::OneOrMore && firstTermInGroup.m_quantifier == AtomQuantifier::ZeroOrOne)
502                 return true;
503         }
504         break;
505     }
506     }
507     return false;
508 }
509
510 inline bool Term::hasFixedLength() const
511 {
512     ASSERT(isValid());
513
514     switch (m_termType) {
515     case TermType::Empty:
516     case TermType::Deleted:
517         ASSERT_NOT_REACHED();
518         break;
519     case TermType::CharacterSet:
520         return m_quantifier == AtomQuantifier::One;
521     case TermType::Group: {
522         if (m_quantifier != AtomQuantifier::One)
523             return false;
524         for (const Term& term : m_atomData.group.terms) {
525             if (!term.hasFixedLength())
526                 return false;
527         }
528         return true;
529     }
530     }
531     return false;
532 }
533
534 inline Term& Term::operator=(const Term& other)
535 {
536     destroy();
537     new (NotNull, this) Term(other);
538     return *this;
539 }
540
541 inline Term& Term::operator=(Term&& other)
542 {
543     destroy();
544     new (NotNull, this) Term(WTF::move(other));
545     return *this;
546 }
547
548 inline bool Term::operator==(const Term& other) const
549 {
550     if (other.m_termType != m_termType || other.m_quantifier != m_quantifier)
551         return false;
552
553     switch (m_termType) {
554     case TermType::Empty:
555     case TermType::Deleted:
556         return true;
557     case TermType::CharacterSet:
558         return m_atomData.characterSet == other.m_atomData.characterSet;
559     case TermType::Group:
560         return m_atomData.group == other.m_atomData.group;
561     }
562     ASSERT_NOT_REACHED();
563     return false;
564 }
565
566 inline unsigned Term::hash() const
567 {
568     unsigned primary = static_cast<unsigned>(m_termType) << 16 | static_cast<unsigned>(m_quantifier);
569     unsigned secondary = 0;
570     switch (m_termType) {
571     case TermType::Empty:
572         secondary = 52184393;
573         break;
574     case TermType::Deleted:
575         secondary = 40342988;
576         break;
577     case TermType::CharacterSet:
578         secondary = m_atomData.characterSet.hash();
579         break;
580     case TermType::Group:
581         secondary = m_atomData.group.hash();
582         break;
583     }
584     return WTF::pairIntHash(primary, secondary);
585 }
586
587 inline bool Term::isEmptyValue() const
588 {
589     return m_termType == TermType::Empty;
590 }
591
592 inline bool Term::isDeletedValue() const
593 {
594     return m_termType == TermType::Deleted;
595 }
596
597 inline bool Term::isUniversalTransition() const
598 {
599     ASSERT(isValid());
600
601     switch (m_termType) {
602     case TermType::Empty:
603     case TermType::Deleted:
604         ASSERT_NOT_REACHED();
605         break;
606     case TermType::CharacterSet:
607         return (m_atomData.characterSet.inverted() && !m_atomData.characterSet.bitCount())
608             || (!m_atomData.characterSet.inverted() && m_atomData.characterSet.bitCount() == 128);
609     case TermType::Group:
610         return m_atomData.group.terms.size() == 1 && m_atomData.group.terms.first().isUniversalTransition();
611     }
612     return false;
613 }
614
615 inline unsigned Term::generateSubgraphForAtom(NFA& nfa, unsigned source) const
616 {
617     switch (m_termType) {
618     case TermType::Empty:
619     case TermType::Deleted:
620         ASSERT_NOT_REACHED();
621         return -1;
622     case TermType::CharacterSet: {
623         unsigned target = nfa.createNode();
624         if (isUniversalTransition())
625             nfa.addTransitionsOnAnyCharacter(source, target);
626         else {
627             if (!m_atomData.characterSet.inverted()) {
628                 for (UChar i = 0; i < 128; ++i) {
629                     if (m_atomData.characterSet.get(i))
630                         nfa.addTransition(source, target, static_cast<char>(i));
631                 }
632             } else {
633                 for (UChar i = 1; i < 128; ++i) {
634                     if (!m_atomData.characterSet.get(i))
635                         nfa.addTransition(source, target, static_cast<char>(i));
636                 }
637             }
638         }
639         return target;
640     }
641     case TermType::Group: {
642         unsigned lastTarget = source;
643         for (const Term& term : m_atomData.group.terms)
644             lastTarget = term.generateGraph(nfa, lastTarget, ActionList());
645         return lastTarget;
646     }
647     }
648 }
649
650 inline void Term::destroy()
651 {
652     switch (m_termType) {
653     case TermType::Empty:
654     case TermType::Deleted:
655         break;
656     case TermType::CharacterSet:
657         m_atomData.characterSet.~CharacterSet();
658         break;
659     case TermType::Group:
660         m_atomData.group.~Group();
661         break;
662     }
663     m_termType = TermType::Deleted;
664 }
665
666 } // namespace ContentExtensions
667 } // namespace WebCore
668
669 #endif // ENABLE(CONTENT_EXTENSIONS)
670
671 #endif // Term_h