[ContentExtensions] Prepare for compiling stylesheets of selectors to be used on...
[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 #include <wtf/Deque.h>
35 #include <wtf/text/CString.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     {
52     }
53
54     Term(char character, bool isCaseSensitive)
55         : m_termType(TermType::CharacterSet)
56     {
57         new (NotNull, &m_atomData.characterSet) CharacterSet();
58         addCharacter(character, isCaseSensitive);
59     }
60
61     enum UniversalTransitionTag { UniversalTransition };
62     explicit Term(UniversalTransitionTag)
63         : m_termType(TermType::CharacterSet)
64     {
65         new (NotNull, &m_atomData.characterSet) CharacterSet();
66         for (unsigned i = 0; i < 128; ++i)
67             m_atomData.characterSet.characters.set(i);
68     }
69
70     enum CharacterSetTermTag { CharacterSetTerm };
71     explicit Term(CharacterSetTermTag, bool isInverted)
72         : m_termType(TermType::CharacterSet)
73     {
74         new (NotNull, &m_atomData.characterSet) CharacterSet();
75         m_atomData.characterSet.inverted = isInverted;
76     }
77
78     enum GroupTermTag { GroupTerm };
79     explicit Term(GroupTermTag)
80         : m_termType(TermType::Group)
81     {
82         new (NotNull, &m_atomData.group) Group();
83     }
84
85     enum EndOfLineAssertionTermTag { EndOfLineAssertionTerm };
86     explicit Term(EndOfLineAssertionTermTag)
87         : Term(CharacterSetTerm, false)
88     {
89         m_atomData.characterSet.characters.set(0);
90     }
91
92     Term(const Term& other)
93         : m_termType(other.m_termType)
94         , m_quantifier(other.m_quantifier)
95     {
96         switch (m_termType) {
97         case TermType::Empty:
98         case TermType::Deleted:
99             break;
100         case TermType::CharacterSet:
101             new (NotNull, &m_atomData.characterSet) CharacterSet(other.m_atomData.characterSet);
102             break;
103         case TermType::Group:
104             new (NotNull, &m_atomData.group) Group(other.m_atomData.group);
105             break;
106         }
107     }
108
109     Term(Term&& other)
110         : m_termType(WTF::move(other.m_termType))
111         , m_quantifier(WTF::move(other.m_quantifier))
112     {
113         switch (m_termType) {
114         case TermType::Empty:
115         case TermType::Deleted:
116             break;
117         case TermType::CharacterSet:
118             new (NotNull, &m_atomData.characterSet) CharacterSet(WTF::move(other.m_atomData.characterSet));
119             break;
120         case TermType::Group:
121             new (NotNull, &m_atomData.group) Group(WTF::move(other.m_atomData.group));
122             break;
123         }
124         other.destroy();
125     }
126
127     enum EmptyValueTag { EmptyValue };
128     Term(EmptyValueTag)
129         : m_termType(TermType::Empty)
130     {
131     }
132
133     enum DeletedValueTag { DeletedValue };
134     Term(DeletedValueTag)
135         : m_termType(TermType::Deleted)
136     {
137     }
138
139     ~Term()
140     {
141         destroy();
142     }
143
144     bool isValid() const
145     {
146         return m_termType != TermType::Empty && m_termType != TermType::Deleted;
147     }
148
149     void addCharacter(UChar character, bool isCaseSensitive)
150     {
151         ASSERT(isASCII(character));
152
153         ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::CharacterSet);
154         if (m_termType != TermType::CharacterSet)
155             return;
156
157         if (isCaseSensitive || !isASCIIAlpha(character))
158             m_atomData.characterSet.characters.set(character);
159         else {
160             m_atomData.characterSet.characters.set(toASCIIUpper(character));
161             m_atomData.characterSet.characters.set(toASCIILower(character));
162         }
163     }
164
165     void extendGroupSubpattern(const Term& term)
166     {
167         ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::Group);
168         if (m_termType != TermType::Group)
169             return;
170         m_atomData.group.terms.append(term);
171     }
172
173     void quantify(const AtomQuantifier& quantifier)
174     {
175         ASSERT_WITH_MESSAGE(m_quantifier == AtomQuantifier::One, "Transition to quantified term should only happen once.");
176         m_quantifier = quantifier;
177     }
178     AtomQuantifier quantifier() const { return m_quantifier; }
179
180     unsigned generateGraph(NFA& nfa, uint64_t patternId, unsigned start) const
181     {
182         ASSERT(isValid());
183
184         switch (m_quantifier) {
185         case AtomQuantifier::One: {
186             unsigned newEnd = generateSubgraphForAtom(nfa, patternId, start);
187             return newEnd;
188         }
189         case AtomQuantifier::ZeroOrOne: {
190             unsigned newEnd = generateSubgraphForAtom(nfa, patternId, start);
191             nfa.addEpsilonTransition(start, newEnd);
192             return newEnd;
193         }
194         case AtomQuantifier::ZeroOrMore: {
195             unsigned repeatStart = nfa.createNode();
196             nfa.addRuleId(repeatStart, patternId);
197             nfa.addEpsilonTransition(start, repeatStart);
198
199             unsigned repeatEnd = generateSubgraphForAtom(nfa, patternId, repeatStart);
200             nfa.addEpsilonTransition(repeatEnd, repeatStart);
201
202             unsigned kleenEnd = nfa.createNode();
203             nfa.addRuleId(kleenEnd, patternId);
204             nfa.addEpsilonTransition(repeatEnd, kleenEnd);
205             nfa.addEpsilonTransition(start, kleenEnd);
206             return kleenEnd;
207         }
208         case AtomQuantifier::OneOrMore: {
209             unsigned repeatStart = nfa.createNode();
210             nfa.addRuleId(repeatStart, patternId);
211             nfa.addEpsilonTransition(start, repeatStart);
212
213             unsigned repeatEnd = generateSubgraphForAtom(nfa, patternId, repeatStart);
214             nfa.addEpsilonTransition(repeatEnd, repeatStart);
215
216             unsigned afterRepeat = nfa.createNode();
217             nfa.addRuleId(afterRepeat, patternId);
218             nfa.addEpsilonTransition(repeatEnd, afterRepeat);
219             return afterRepeat;
220         }
221         }
222     }
223
224     bool isEndOfLineAssertion() const
225     {
226         return m_termType == TermType::CharacterSet && m_atomData.characterSet.characters.bitCount() == 1 && m_atomData.characterSet.characters.get(0);
227     }
228
229     Term& operator=(const Term& other)
230     {
231         destroy();
232         new (NotNull, this) Term(other);
233         return *this;
234     }
235
236     Term& operator=(Term&& other)
237     {
238         destroy();
239         new (NotNull, this) Term(WTF::move(other));
240         return *this;
241     }
242
243     bool operator==(const Term& other) const
244     {
245         if (other.m_termType != m_termType || other.m_quantifier != m_quantifier)
246             return false;
247
248         switch (m_termType) {
249         case TermType::Empty:
250         case TermType::Deleted:
251             return true;
252         case TermType::CharacterSet:
253             return m_atomData.characterSet == other.m_atomData.characterSet;
254         case TermType::Group:
255             return m_atomData.group == other.m_atomData.group;
256         }
257         ASSERT_NOT_REACHED();
258         return false;
259     }
260
261     unsigned hash() const
262     {
263         unsigned primary = static_cast<unsigned>(m_termType) << 16 | static_cast<unsigned>(m_quantifier);
264         unsigned secondary = 0;
265         switch (m_termType) {
266         case TermType::Empty:
267             secondary = 52184393;
268             break;
269         case TermType::Deleted:
270             secondary = 40342988;
271             break;
272         case TermType::CharacterSet:
273             secondary = m_atomData.characterSet.hash();
274             break;
275         case TermType::Group:
276             secondary = m_atomData.group.hash();
277             break;
278         }
279         return WTF::pairIntHash(primary, secondary);
280     }
281
282     bool isEmptyValue() const
283     {
284         return m_termType == TermType::Empty;
285     }
286
287     bool isDeletedValue() const
288     {
289         return m_termType == TermType::Deleted;
290     }
291
292 private:
293     bool isUniversalTransition() const
294     {
295         return m_termType == TermType::CharacterSet
296             && ((m_atomData.characterSet.inverted && !m_atomData.characterSet.characters.bitCount())
297                 || (!m_atomData.characterSet.inverted && m_atomData.characterSet.characters.bitCount() == 128));
298     }
299
300     unsigned generateSubgraphForAtom(NFA& nfa, uint64_t patternId, unsigned source) const
301     {
302         switch (m_termType) {
303         case TermType::Empty:
304         case TermType::Deleted:
305             ASSERT_NOT_REACHED();
306             return -1;
307         case TermType::CharacterSet: {
308             unsigned target = nfa.createNode();
309             nfa.addRuleId(target, patternId);
310             if (isUniversalTransition())
311                 nfa.addTransitionsOnAnyCharacter(source, target);
312             else {
313                 if (!m_atomData.characterSet.inverted) {
314                     for (const auto& characterIterator : m_atomData.characterSet.characters.setBits())
315                         nfa.addTransition(source, target, static_cast<char>(characterIterator));
316                 } else {
317                     for (unsigned i = 1; i < m_atomData.characterSet.characters.size(); ++i) {
318                         if (m_atomData.characterSet.characters.get(i))
319                             continue;
320                         nfa.addTransition(source, target, static_cast<char>(i));
321                     }
322                 }
323             }
324             return target;
325         }
326         case TermType::Group: {
327             unsigned lastTarget = source;
328             for (const Term& term : m_atomData.group.terms)
329                 lastTarget = term.generateGraph(nfa, patternId, lastTarget);
330             return lastTarget;
331         }
332         }
333     }
334
335     void destroy()
336     {
337         switch (m_termType) {
338         case TermType::Empty:
339         case TermType::Deleted:
340             break;
341         case TermType::CharacterSet:
342             m_atomData.characterSet.~CharacterSet();
343             break;
344         case TermType::Group:
345             m_atomData.group.~Group();
346             break;
347         }
348         m_termType = TermType::Deleted;
349     }
350
351     enum class TermType : uint8_t {
352         Empty,
353         Deleted,
354         CharacterSet,
355         Group
356     };
357
358     TermType m_termType { TermType::Empty };
359     AtomQuantifier m_quantifier { AtomQuantifier::One };
360
361     struct CharacterSet {
362         bool inverted { false };
363         BitVector characters { 128 };
364
365         bool operator==(const CharacterSet& other) const
366         {
367             return other.inverted == inverted && other.characters == characters;
368         }
369
370         unsigned hash() const
371         {
372             return WTF::pairIntHash(inverted, characters.hash());
373         }
374     };
375
376     struct Group {
377         Vector<Term> terms;
378
379         bool operator==(const Group& other) const
380         {
381             return other.terms == terms;
382         }
383
384         unsigned hash() const
385         {
386             unsigned hash = 6421749;
387             for (const Term& term : terms) {
388                 unsigned termHash = term.hash();
389                 hash = (hash << 16) ^ ((termHash << 11) ^ hash);
390                 hash += hash >> 11;
391             }
392             return hash;
393         }
394     };
395
396     union AtomData {
397         AtomData()
398             : invalidTerm(0)
399         {
400         }
401         ~AtomData()
402         {
403         }
404
405         char invalidTerm;
406         CharacterSet characterSet;
407         Group group;
408     } m_atomData;
409 };
410
411 struct TermHash {
412     static unsigned hash(const Term& term) { return term.hash(); }
413     static bool equal(const Term& a, const Term& b) { return a == b; }
414     static const bool safeToCompareToEmptyOrDeleted = true;
415 };
416
417 struct TermHashTraits : public WTF::CustomHashTraits<Term> { };
418
419 struct PrefixTreeEntry {
420     unsigned nfaNode;
421     HashMap<Term, std::unique_ptr<PrefixTreeEntry>, TermHash, TermHashTraits> nextPattern;
422 };
423
424 class GraphBuilder {
425 public:
426     GraphBuilder(NFA& nfa, PrefixTreeEntry& prefixTreeRoot, bool patternIsCaseSensitive, uint64_t patternId)
427         : m_nfa(nfa)
428         , m_patternIsCaseSensitive(patternIsCaseSensitive)
429         , m_patternId(patternId)
430         , m_subtreeStart(nfa.root())
431         , m_subtreeEnd(nfa.root())
432         , m_lastPrefixTreeEntry(&prefixTreeRoot)
433         , m_parseStatus(URLFilterParser::Ok)
434     {
435     }
436
437     void finalize()
438     {
439         if (hasError())
440             return;
441
442         sinkFloatingTermIfNecessary();
443
444         // Check to see if there are any terms without ? or *.
445         bool matchesEverything = true;
446         for (const auto& term : m_sunkTerms) {
447             if (term.quantifier() == AtomQuantifier::One || term.quantifier() == AtomQuantifier::OneOrMore) {
448                 matchesEverything = false;
449                 break;
450             }
451         }
452         if (matchesEverything)
453             fail(URLFilterParser::MatchesEverything);
454
455         for (const auto& term : m_sunkTerms) {
456             ASSERT(m_lastPrefixTreeEntry);
457             auto nextEntry = m_lastPrefixTreeEntry->nextPattern.find(term);
458             if (nextEntry != m_lastPrefixTreeEntry->nextPattern.end()) {
459                 m_lastPrefixTreeEntry = nextEntry->value.get();
460                 m_nfa.addRuleId(m_lastPrefixTreeEntry->nfaNode, m_patternId);
461             } else {
462                 std::unique_ptr<PrefixTreeEntry> nextPrefixTreeEntry = std::make_unique<PrefixTreeEntry>();
463                 
464                 unsigned newEnd = term.generateGraph(m_nfa, m_patternId, m_lastPrefixTreeEntry->nfaNode);
465                 nextPrefixTreeEntry->nfaNode = newEnd;
466                 
467                 auto addResult = m_lastPrefixTreeEntry->nextPattern.set(term, WTF::move(nextPrefixTreeEntry));
468                 ASSERT(addResult.isNewEntry);
469                 
470                 if (!m_newPrefixSubtreeRoot) {
471                     m_newPrefixSubtreeRoot = m_lastPrefixTreeEntry;
472                     m_newPrefixStaringPoint = term;
473                 }
474                 
475                 m_lastPrefixTreeEntry = addResult.iterator->value.get();
476             }
477             m_subtreeEnd = m_lastPrefixTreeEntry->nfaNode;
478         }
479         
480         if (!m_openGroups.isEmpty()) {
481             fail(URLFilterParser::UnclosedGroups);
482             return;
483         }
484
485         if (m_subtreeStart != m_subtreeEnd)
486             m_nfa.setFinal(m_subtreeEnd, m_patternId);
487         else
488             fail(URLFilterParser::CannotMatchAnything);
489     }
490
491     URLFilterParser::ParseStatus parseStatus() const
492     {
493         return m_parseStatus;
494     }
495
496     void atomPatternCharacter(UChar character)
497     {
498         if (hasError())
499             return;
500
501         if (!isASCII(character)) {
502             fail(URLFilterParser::NonASCII);
503             return;
504         }
505
506         sinkFloatingTermIfNecessary();
507         ASSERT(!m_floatingTerm.isValid());
508
509         char asciiChararacter = static_cast<char>(character);
510         m_floatingTerm = Term(asciiChararacter, m_patternIsCaseSensitive);
511     }
512
513     void atomBuiltInCharacterClass(JSC::Yarr::BuiltInCharacterClassID builtInCharacterClassID, bool inverted)
514     {
515         if (hasError())
516             return;
517
518         sinkFloatingTermIfNecessary();
519         ASSERT(!m_floatingTerm.isValid());
520
521         if (builtInCharacterClassID == JSC::Yarr::NewlineClassID && inverted)
522             m_floatingTerm = Term(Term::UniversalTransition);
523         else
524             fail(URLFilterParser::UnsupportedCharacterClass);
525     }
526
527     void quantifyAtom(unsigned minimum, unsigned maximum, bool)
528     {
529         if (hasError())
530             return;
531
532         if (!m_floatingTerm.isValid())
533             fail(URLFilterParser::MisplacedQuantifier);
534
535         if (!minimum && maximum == 1)
536             m_floatingTerm.quantify(AtomQuantifier::ZeroOrOne);
537         else if (!minimum && maximum == JSC::Yarr::quantifyInfinite)
538             m_floatingTerm.quantify(AtomQuantifier::ZeroOrMore);
539         else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
540             m_floatingTerm.quantify(AtomQuantifier::OneOrMore);
541         else
542             fail(URLFilterParser::InvalidQuantifier);
543     }
544
545     void atomBackReference(unsigned)
546     {
547         fail(URLFilterParser::BackReference);
548     }
549
550     void assertionBOL()
551     {
552         if (hasError())
553             return;
554
555         if (m_subtreeStart != m_subtreeEnd || m_floatingTerm.isValid() || !m_openGroups.isEmpty())
556             fail(URLFilterParser::MisplacedStartOfLine);
557     }
558
559     void assertionEOL()
560     {
561         if (hasError())
562             return;
563
564         sinkFloatingTermIfNecessary();
565         ASSERT(!m_floatingTerm.isValid());
566
567         m_floatingTerm = Term(Term::EndOfLineAssertionTerm);
568     }
569
570     void assertionWordBoundary(bool)
571     {
572         fail(URLFilterParser::WordBoundary);
573     }
574
575     void atomCharacterClassBegin(bool inverted = false)
576     {
577         if (hasError())
578             return;
579
580         sinkFloatingTermIfNecessary();
581         ASSERT(!m_floatingTerm.isValid());
582
583         m_floatingTerm = Term(Term::CharacterSetTerm, inverted);
584     }
585
586     void atomCharacterClassAtom(UChar character)
587     {
588         if (hasError())
589             return;
590
591         ASSERT(isASCII(character));
592
593         m_floatingTerm.addCharacter(character, m_patternIsCaseSensitive);
594     }
595
596     void atomCharacterClassRange(UChar a, UChar b)
597     {
598         if (hasError())
599             return;
600
601         ASSERT(a);
602         ASSERT(b);
603         ASSERT(isASCII(a));
604         ASSERT(isASCII(b));
605
606         for (unsigned i = a; i <= b; ++i)
607             m_floatingTerm.addCharacter(static_cast<UChar>(i), m_patternIsCaseSensitive);
608     }
609
610     void atomCharacterClassEnd()
611     {
612         // Nothing to do here. The character set atom may have a quantifier, we sink the atom lazily.
613     }
614
615     void atomCharacterClassBuiltIn(JSC::Yarr::BuiltInCharacterClassID, bool)
616     {
617         fail(URLFilterParser::AtomCharacter);
618     }
619
620     void atomParenthesesSubpatternBegin(bool = true)
621     {
622         if (hasError())
623             return;
624
625         sinkFloatingTermIfNecessary();
626
627         m_openGroups.append(Term(Term::GroupTerm));
628     }
629
630     void atomParentheticalAssertionBegin(bool = false)
631     {
632         fail(URLFilterParser::Group);
633     }
634
635     void atomParenthesesEnd()
636     {
637         if (hasError())
638             return;
639
640         sinkFloatingTermIfNecessary();
641         ASSERT(!m_floatingTerm.isValid());
642
643         m_floatingTerm = m_openGroups.takeLast();
644     }
645
646     void disjunction()
647     {
648         fail(URLFilterParser::Disjunction);
649     }
650
651 private:
652     bool hasError() const
653     {
654         return m_parseStatus != URLFilterParser::Ok;
655     }
656
657     void fail(URLFilterParser::ParseStatus reason)
658     {
659         if (hasError())
660             return;
661
662         if (m_newPrefixSubtreeRoot)
663             m_newPrefixSubtreeRoot->nextPattern.remove(m_newPrefixStaringPoint);
664
665         m_parseStatus = reason;
666     }
667
668     void sinkFloatingTermIfNecessary()
669     {
670         if (!m_floatingTerm.isValid())
671             return;
672
673         if (m_hasProcessedEndOfLineAssertion) {
674             fail(URLFilterParser::MisplacedEndOfLine);
675             m_floatingTerm = Term();
676             return;
677         }
678
679         if (m_floatingTerm.isEndOfLineAssertion())
680             m_hasProcessedEndOfLineAssertion = true;
681
682         if (!m_openGroups.isEmpty()) {
683             m_openGroups.last().extendGroupSubpattern(m_floatingTerm);
684             m_floatingTerm = Term();
685             return;
686         }
687
688         m_sunkTerms.append(m_floatingTerm);
689         m_floatingTerm = Term();
690     }
691
692     NFA& m_nfa;
693     bool m_patternIsCaseSensitive;
694     const uint64_t m_patternId;
695
696     unsigned m_subtreeStart { 0 };
697     unsigned m_subtreeEnd { 0 };
698
699     PrefixTreeEntry* m_lastPrefixTreeEntry;
700     Deque<Term> m_openGroups;
701     Vector<Term> m_sunkTerms;
702     Term m_floatingTerm;
703     bool m_hasProcessedEndOfLineAssertion { false };
704
705     PrefixTreeEntry* m_newPrefixSubtreeRoot = nullptr;
706     Term m_newPrefixStaringPoint;
707
708     URLFilterParser::ParseStatus m_parseStatus;
709 };
710
711 URLFilterParser::URLFilterParser(NFA& nfa)
712     : m_nfa(nfa)
713     , m_prefixTreeRoot(std::make_unique<PrefixTreeEntry>())
714 {
715     m_prefixTreeRoot->nfaNode = nfa.root();
716 }
717
718 URLFilterParser::~URLFilterParser()
719 {
720 }
721
722 URLFilterParser::ParseStatus URLFilterParser::addPattern(const String& pattern, bool patternIsCaseSensitive, uint64_t patternId)
723 {
724     if (!pattern.containsOnlyASCII())
725         return NonASCII;
726     ASSERT(!pattern.isEmpty());
727
728     if (pattern.isEmpty())
729         return EmptyPattern;
730
731     unsigned oldSize = m_nfa.graphSize();
732
733     ParseStatus status = Ok;
734     GraphBuilder graphBuilder(m_nfa, *m_prefixTreeRoot, patternIsCaseSensitive, patternId);
735     String error = String(JSC::Yarr::parse(graphBuilder, pattern, 0));
736     if (error.isNull())
737         graphBuilder.finalize();
738     else
739         status = YarrError;
740     
741     if (status == Ok)
742         status = graphBuilder.parseStatus();
743
744     if (status != Ok)
745         m_nfa.restoreToGraphSize(oldSize);
746
747     return status;
748 }
749
750 String URLFilterParser::statusString(ParseStatus status)
751 {
752     switch (status) {
753     case Ok:
754         return "Ok";
755     case MatchesEverything:
756         return "Matches everything.";
757     case UnclosedGroups:
758         return "The expression has unclosed groups.";
759     case CannotMatchAnything:
760         return "The pattern cannot match anything.";
761     case NonASCII:
762         return "Only ASCII characters are supported in pattern.";
763     case UnsupportedCharacterClass:
764         return "Character class is not supported.";
765     case MisplacedQuantifier:
766         return "Quantifier without corresponding term to quantify.";
767     case BackReference:
768         return "Patterns cannot contain backreferences.";
769     case MisplacedStartOfLine:
770         return "Start of line assertion can only appear as the first term in a filter.";
771     case WordBoundary:
772         return "Word boundaries assertions are not supported yet.";
773     case AtomCharacter:
774         return "Builtins character class atoms are not supported yet.";
775     case Group:
776         return "Groups are not supported yet.";
777     case Disjunction:
778         return "Disjunctions are not supported yet.";
779     case MisplacedEndOfLine:
780         return "The end of line assertion must be the last term in an expression.";
781     case EmptyPattern:
782         return "Empty pattern.";
783     case YarrError:
784         return "Internal error in YARR.";
785     case InvalidQuantifier:
786         return "Arbitrary atom repetitions are not supported.";
787     }
788 }
789     
790 } // namespace ContentExtensions
791 } // namespace WebCore
792
793 #endif // ENABLE(CONTENT_EXTENSIONS)