Merge TrivialAtom and CharacterSet into a Term abstraction, prepare Term for composition
[WebKit-https.git] / Source / WebCore / contentextensions / URLFilterParser.cpp
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 #include "config.h"
27 #include "URLFilterParser.h"
28
29 #if ENABLE(CONTENT_EXTENSIONS)
30
31 #include "NFA.h"
32 #include <JavaScriptCore/YarrParser.h>
33 #include <wtf/BitVector.h>
34
35 namespace WebCore {
36
37 namespace ContentExtensions {
38
39 enum class AtomQuantifier : uint8_t {
40     One,
41     ZeroOrOne,
42     ZeroOrMore,
43     OneOrMore
44 };
45
46 class Term {
47 public:
48     Term()
49     {
50     }
51
52     Term(char character, bool isCaseSensitive)
53         : m_termType(TermType::CharacterSet)
54     {
55         new (NotNull, &m_atomData.characterSet) CharacterSet();
56         addCharacter(character, isCaseSensitive);
57     }
58
59     enum UniversalTransitionTag { UniversalTransition };
60     explicit Term(UniversalTransitionTag)
61         : m_termType(TermType::CharacterSet)
62     {
63         new (NotNull, &m_atomData.characterSet) CharacterSet();
64         for (unsigned i = 0; i < 128; ++i)
65             m_atomData.characterSet.characters.set(i);
66     }
67
68     enum CharacterSetTermTag { CharacterSetTerm };
69     Term(CharacterSetTermTag, bool isInverted)
70         : m_termType(TermType::CharacterSet)
71     {
72         new (NotNull, &m_atomData.characterSet) CharacterSet();
73         m_atomData.characterSet.inverted = isInverted;
74     }
75
76     Term(const Term& other)
77         : m_termType(other.m_termType)
78         , m_quantifier(other.m_quantifier)
79     {
80         switch (m_termType) {
81         case TermType::Empty:
82         case TermType::Deleted:
83             break;
84         case TermType::CharacterSet:
85             new (NotNull, &m_atomData.characterSet) CharacterSet(other.m_atomData.characterSet);
86             break;
87         }
88     }
89
90     Term(Term&& other)
91         : m_termType(WTF::move(other.m_termType))
92         , m_quantifier(WTF::move(other.m_quantifier))
93     {
94         switch (m_termType) {
95         case TermType::Empty:
96         case TermType::Deleted:
97             break;
98         case TermType::CharacterSet:
99             new (NotNull, &m_atomData.characterSet) CharacterSet(WTF::move(other.m_atomData.characterSet));
100             break;
101         }
102         other.destroy();
103     }
104
105     enum EmptyValueTag { EmptyValue };
106     Term(EmptyValueTag)
107         : m_termType(TermType::Empty)
108     {
109     }
110
111     enum DeletedValueTag { DeletedValue };
112     Term(DeletedValueTag)
113         : m_termType(TermType::Deleted)
114     {
115     }
116
117     ~Term()
118     {
119         destroy();
120     }
121
122     bool isValid() const
123     {
124         return m_termType != TermType::Empty && m_termType != TermType::Deleted;
125     }
126
127     void addCharacter(UChar character, bool isCaseSensitive)
128     {
129         ASSERT(isASCII(character));
130
131         ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::CharacterSet);
132         if (m_termType != TermType::CharacterSet)
133             return;
134
135         if (isCaseSensitive || !isASCIIAlpha(character))
136             m_atomData.characterSet.characters.set(character);
137         else {
138             m_atomData.characterSet.characters.set(toASCIIUpper(character));
139             m_atomData.characterSet.characters.set(toASCIILower(character));
140         }
141     }
142
143     void quantify(const AtomQuantifier& quantifier)
144     {
145         ASSERT_WITH_MESSAGE(m_quantifier == AtomQuantifier::One, "Transition to quantified term should only happen once.");
146         m_quantifier = quantifier;
147     }
148
149     AtomQuantifier quantifier() const
150     {
151         return m_quantifier;
152     }
153
154     bool isUniversalTransition() const
155     {
156         return m_termType == TermType::CharacterSet
157             && ((m_atomData.characterSet.inverted && !m_atomData.characterSet.characters.bitCount())
158                 || (!m_atomData.characterSet.inverted && m_atomData.characterSet.characters.bitCount() == 128));
159     }
160
161     void visitSimpleTransitions(std::function<void(char)> visitor) const
162     {
163         ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::CharacterSet);
164         if (m_termType != TermType::CharacterSet)
165             return;
166
167         if (!m_atomData.characterSet.inverted) {
168             for (const auto& characterIterator : m_atomData.characterSet.characters.setBits())
169                 visitor(static_cast<char>(characterIterator));
170         } else {
171             for (unsigned i = 1; i < m_atomData.characterSet.characters.size(); ++i) {
172                 if (m_atomData.characterSet.characters.get(i))
173                     continue;
174                 visitor(static_cast<char>(i));
175             }
176         }
177     }
178
179     Term& operator=(const Term& other)
180     {
181         destroy();
182         new (NotNull, this) Term(other);
183         return *this;
184     }
185
186     Term& operator=(Term&& other)
187     {
188         destroy();
189         new (NotNull, this) Term(WTF::move(other));
190         return *this;
191     }
192
193     bool operator==(const Term& other) const
194     {
195         if (other.m_termType != m_termType || other.m_quantifier != m_quantifier)
196             return false;
197
198         switch (m_termType) {
199         case TermType::Empty:
200         case TermType::Deleted:
201             return true;
202         case TermType::CharacterSet:
203             return m_atomData.characterSet == other.m_atomData.characterSet;
204         }
205         ASSERT_NOT_REACHED();
206         return false;
207     }
208
209     unsigned hash() const
210     {
211         unsigned primary = static_cast<unsigned>(m_termType) << 16 | static_cast<unsigned>(m_quantifier);
212         unsigned secondary = 0;
213         switch (m_termType) {
214         case TermType::Empty:
215             secondary = 52184393;
216             break;
217         case TermType::Deleted:
218             secondary = 40342988;
219             break;
220         case TermType::CharacterSet:
221             secondary = m_atomData.characterSet.hash();
222             break;
223         }
224         return WTF::pairIntHash(primary, secondary);
225     }
226
227     bool isEmptyValue() const
228     {
229         return m_termType == TermType::Empty;
230     }
231
232     bool isDeletedValue() const
233     {
234         return m_termType == TermType::Deleted;
235     }
236
237 private:
238     void destroy()
239     {
240         switch (m_termType) {
241         case TermType::Empty:
242         case TermType::Deleted:
243             break;
244         case TermType::CharacterSet:
245             m_atomData.characterSet.~CharacterSet();
246             break;
247         }
248         m_termType = TermType::Deleted;
249     }
250
251     enum class TermType : uint8_t {
252         Empty,
253         Deleted,
254         CharacterSet
255     };
256
257     TermType m_termType { TermType::Empty };
258     AtomQuantifier m_quantifier { AtomQuantifier::One };
259
260     struct CharacterSet {
261         bool inverted { false };
262         BitVector characters { 128 };
263
264         bool operator==(const CharacterSet& other) const
265         {
266             return other.inverted == inverted && other.characters == characters;
267         }
268
269         unsigned hash() const
270         {
271             return WTF::pairIntHash(inverted, characters.hash());
272         }
273     };
274
275     union AtomData {
276         AtomData()
277             : invalidTerm(0)
278         {
279         }
280         ~AtomData()
281         {
282         }
283
284         char invalidTerm;
285         CharacterSet characterSet;
286     } m_atomData;
287 };
288
289 struct TermHash {
290     static unsigned hash(const Term& term) { return term.hash(); }
291     static bool equal(const Term& a, const Term& b) { return a == b; }
292     static const bool safeToCompareToEmptyOrDeleted = true;
293 };
294
295 struct TermHashTraits : public WTF::CustomHashTraits<Term> { };
296
297 struct PrefixTreeEntry {
298     unsigned nfaNode;
299     HashMap<Term, std::unique_ptr<PrefixTreeEntry>, TermHash, TermHashTraits> nextPattern;
300 };
301
302 class GraphBuilder {
303 public:
304     GraphBuilder(NFA& nfa, PrefixTreeEntry& prefixTreeRoot, bool patternIsCaseSensitive, uint64_t patternId)
305         : m_nfa(nfa)
306         , m_patternIsCaseSensitive(patternIsCaseSensitive)
307         , m_patternId(patternId)
308         , m_subtreeStart(nfa.root())
309         , m_subtreeEnd(nfa.root())
310         , m_lastPrefixTreeEntry(&prefixTreeRoot)
311     {
312     }
313
314     void finalize()
315     {
316         if (hasError())
317             return;
318
319         sinkFloatingTermIfNecessary();
320
321         if (m_subtreeStart != m_subtreeEnd)
322             m_nfa.setFinal(m_subtreeEnd, m_patternId);
323         else
324             fail(ASCIILiteral("The pattern cannot match anything."));
325     }
326
327     const String& errorMessage() const
328     {
329         return m_errorMessage;
330     }
331
332     void atomPatternCharacter(UChar character)
333     {
334         if (hasError())
335             return;
336
337         if (!isASCII(character)) {
338             fail(ASCIILiteral("Only ASCII characters are supported in pattern."));
339             return;
340         }
341
342         sinkFloatingTermIfNecessary();
343         ASSERT(!m_floatingTerm.isValid());
344
345         char asciiChararacter = static_cast<char>(character);
346         m_floatingTerm = Term(asciiChararacter, m_patternIsCaseSensitive);
347     }
348
349     void atomBuiltInCharacterClass(JSC::Yarr::BuiltInCharacterClassID builtInCharacterClassID, bool inverted)
350     {
351         if (hasError())
352             return;
353
354         sinkFloatingTermIfNecessary();
355         ASSERT(!m_floatingTerm.isValid());
356
357         if (builtInCharacterClassID == JSC::Yarr::NewlineClassID && inverted)
358             m_floatingTerm = Term(Term::UniversalTransition);
359         else
360             fail(ASCIILiteral("Character class is not supported."));
361     }
362
363     void quantifyAtom(unsigned minimum, unsigned maximum, bool)
364     {
365         if (hasError())
366             return;
367
368         if (!m_floatingTerm.isValid())
369             fail(ASCIILiteral("Quantifier without corresponding term to quantify."));
370
371         if (!minimum && maximum == 1)
372             m_floatingTerm.quantify(AtomQuantifier::ZeroOrOne);
373         else if (!minimum && maximum == JSC::Yarr::quantifyInfinite)
374             m_floatingTerm.quantify(AtomQuantifier::ZeroOrMore);
375         else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
376             m_floatingTerm.quantify(AtomQuantifier::OneOrMore);
377         else
378             fail(ASCIILiteral("Arbitrary atom repetitions are not supported."));
379     }
380
381     void atomBackReference(unsigned)
382     {
383         fail(ASCIILiteral("Patterns cannot contain backreferences."));
384     }
385
386     void assertionBOL()
387     {
388         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
389     }
390
391     void assertionEOL()
392     {
393         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
394     }
395
396     void assertionWordBoundary(bool)
397     {
398         fail(ASCIILiteral("Word boundaries assertions are not supported yet."));
399     }
400
401     void atomCharacterClassBegin(bool inverted = false)
402     {
403         if (hasError())
404             return;
405
406         sinkFloatingTermIfNecessary();
407         ASSERT(!m_floatingTerm.isValid());
408
409         m_floatingTerm = Term(Term::CharacterSetTerm, inverted);
410     }
411
412     void atomCharacterClassAtom(UChar character)
413     {
414         if (hasError())
415             return;
416
417         if (!isASCII(character)) {
418             fail(ASCIILiteral("Non ASCII Character in a character set."));
419             return;
420         }
421
422         m_floatingTerm.addCharacter(character, m_patternIsCaseSensitive);
423     }
424
425     void atomCharacterClassRange(UChar a, UChar b)
426     {
427         if (hasError())
428             return;
429
430         if (!a || !b || !isASCII(a) || !isASCII(b)) {
431             fail(ASCIILiteral("Non ASCII Character in a character range of a character set."));
432             return;
433         }
434
435         for (unsigned i = a; i <= b; ++i)
436             m_floatingTerm.addCharacter(static_cast<UChar>(i), m_patternIsCaseSensitive);
437     }
438
439     void atomCharacterClassEnd()
440     {
441         // Nothing to do here. The character set atom may have a quantifier, we sink the atom lazily.
442     }
443
444     void atomCharacterClassBuiltIn(JSC::Yarr::BuiltInCharacterClassID, bool)
445     {
446         fail(ASCIILiteral("Builtins character class atoms are not supported yet."));
447     }
448
449     void atomParenthesesSubpatternBegin(bool = true)
450     {
451         fail(ASCIILiteral("Groups are not supported yet."));
452     }
453
454     void atomParentheticalAssertionBegin(bool = false)
455     {
456         fail(ASCIILiteral("Groups are not supported yet."));
457     }
458
459     void atomParenthesesEnd()
460     {
461         fail(ASCIILiteral("Groups are not supported yet."));
462     }
463
464     void disjunction()
465     {
466         fail(ASCIILiteral("Disjunctions are not supported yet."));
467     }
468
469 private:
470     bool hasError() const
471     {
472         return !m_errorMessage.isNull();
473     }
474
475     void fail(const String& errorMessage)
476     {
477         if (hasError())
478             return;
479
480         if (m_newPrefixSubtreeRoot)
481             m_newPrefixSubtreeRoot->nextPattern.remove(m_newPrefixStaringPoint);
482
483         m_errorMessage = errorMessage;
484     }
485
486     void addTransitions(unsigned source, unsigned target)
487     {
488         auto visitor = [this, source, target](char character) {
489             if (m_floatingTerm.isUniversalTransition())
490                 m_nfa.addTransitionsOnAnyCharacter(source, target);
491             else
492                 m_nfa.addTransition(source, target, character);
493         };
494         m_floatingTerm.visitSimpleTransitions(visitor);
495     }
496
497     unsigned sinkFloatingTerm(unsigned start)
498     {
499         switch (m_floatingTerm.quantifier()) {
500         case AtomQuantifier::One: {
501             unsigned newEnd = m_nfa.createNode();
502             m_nfa.addRuleId(newEnd, m_patternId);
503             addTransitions(start, newEnd);
504             return newEnd;
505         }
506         case AtomQuantifier::ZeroOrOne: {
507             unsigned newEnd = m_nfa.createNode();
508             m_nfa.addRuleId(newEnd, m_patternId);
509             addTransitions(start, newEnd);
510             return newEnd;
511         }
512         case AtomQuantifier::ZeroOrMore: {
513             unsigned repeatStart = m_nfa.createNode();
514             m_nfa.addRuleId(repeatStart, m_patternId);
515             unsigned repeatEnd = m_nfa.createNode();
516             m_nfa.addRuleId(repeatEnd, m_patternId);
517
518             addTransitions(repeatStart, repeatEnd);
519             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
520
521             m_nfa.addEpsilonTransition(start, repeatStart);
522
523             unsigned kleenEnd = m_nfa.createNode();
524             m_nfa.addRuleId(kleenEnd, m_patternId);
525             m_nfa.addEpsilonTransition(repeatEnd, kleenEnd);
526             m_nfa.addEpsilonTransition(start, kleenEnd);
527             return kleenEnd;
528         }
529         case AtomQuantifier::OneOrMore: {
530             unsigned repeatStart = m_nfa.createNode();
531             m_nfa.addRuleId(repeatStart, m_patternId);
532             unsigned repeatEnd = m_nfa.createNode();
533             m_nfa.addRuleId(repeatEnd, m_patternId);
534
535             addTransitions(repeatStart, repeatEnd);
536             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
537
538             m_nfa.addEpsilonTransition(start, repeatStart);
539
540             unsigned afterRepeat = m_nfa.createNode();
541             m_nfa.addRuleId(afterRepeat, m_patternId);
542             m_nfa.addEpsilonTransition(repeatEnd, afterRepeat);
543             return afterRepeat;
544         }
545         }
546     }
547
548     void sinkFloatingTermIfNecessary()
549     {
550         if (!m_floatingTerm.isValid())
551             return;
552
553         ASSERT(m_lastPrefixTreeEntry);
554
555         auto nextEntry = m_lastPrefixTreeEntry->nextPattern.find(m_floatingTerm);
556         if (nextEntry != m_lastPrefixTreeEntry->nextPattern.end()) {
557             m_lastPrefixTreeEntry = nextEntry->value.get();
558             m_nfa.addRuleId(m_lastPrefixTreeEntry->nfaNode, m_patternId);
559         } else {
560             std::unique_ptr<PrefixTreeEntry> nextPrefixTreeEntry = std::make_unique<PrefixTreeEntry>();
561
562             unsigned newEnd = sinkFloatingTerm(m_lastPrefixTreeEntry->nfaNode);
563             nextPrefixTreeEntry->nfaNode = newEnd;
564
565             auto addResult = m_lastPrefixTreeEntry->nextPattern.set(m_floatingTerm, WTF::move(nextPrefixTreeEntry));
566             ASSERT(addResult.isNewEntry);
567
568             if (!m_newPrefixSubtreeRoot) {
569                 m_newPrefixSubtreeRoot = m_lastPrefixTreeEntry;
570                 m_newPrefixStaringPoint = m_floatingTerm;
571             }
572
573             m_lastPrefixTreeEntry = addResult.iterator->value.get();
574         }
575         m_subtreeEnd = m_lastPrefixTreeEntry->nfaNode;
576
577         m_floatingTerm = Term();
578         ASSERT(m_lastPrefixTreeEntry);
579     }
580
581     NFA& m_nfa;
582     bool m_patternIsCaseSensitive;
583     const uint64_t m_patternId;
584
585     unsigned m_subtreeStart { 0 };
586     unsigned m_subtreeEnd { 0 };
587
588     PrefixTreeEntry* m_lastPrefixTreeEntry;
589     Term m_floatingTerm;
590
591     PrefixTreeEntry* m_newPrefixSubtreeRoot = nullptr;
592     Term m_newPrefixStaringPoint;
593
594     String m_errorMessage;
595 };
596
597 URLFilterParser::URLFilterParser(NFA& nfa)
598     : m_nfa(nfa)
599     , m_prefixTreeRoot(std::make_unique<PrefixTreeEntry>())
600 {
601     m_prefixTreeRoot->nfaNode = nfa.root();
602 }
603
604 URLFilterParser::~URLFilterParser()
605 {
606 }
607
608 String URLFilterParser::addPattern(const String& pattern, bool patternIsCaseSensitive, uint64_t patternId)
609 {
610     if (!pattern.containsOnlyASCII())
611         return ASCIILiteral("URLFilterParser only supports ASCII patterns.");
612     ASSERT(!pattern.isEmpty());
613
614     if (pattern.isEmpty())
615         return ASCIILiteral("Empty pattern.");
616
617     unsigned oldSize = m_nfa.graphSize();
618
619     String error;
620
621     GraphBuilder graphBuilder(m_nfa, *m_prefixTreeRoot, patternIsCaseSensitive, patternId);
622     error = String(JSC::Yarr::parse(graphBuilder, pattern, 0));
623     if (error.isNull())
624         graphBuilder.finalize();
625
626     if (error.isNull())
627         error = graphBuilder.errorMessage();
628
629     if (!error.isNull())
630         m_nfa.restoreToGraphSize(oldSize);
631
632     return error;
633 }
634
635 } // namespace ContentExtensions
636 } // namespace WebCore
637
638 #endif // ENABLE(CONTENT_EXTENSIONS)