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