Refactor ContentExtensionParser
[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 "CombinedURLFilters.h"
32 #include "Term.h"
33 #include <JavaScriptCore/YarrParser.h>
34 #include <wtf/Deque.h>
35 #include <wtf/text/CString.h>
36
37 namespace WebCore {
38
39 namespace ContentExtensions {
40
41 class PatternParser {
42 public:
43     PatternParser(bool patternIsCaseSensitive)
44         : m_patternIsCaseSensitive(patternIsCaseSensitive)
45         , m_parseStatus(URLFilterParser::Ok)
46     {
47     }
48
49     void finalize(uint64_t patternId, CombinedURLFilters& combinedURLFilters)
50     {
51         if (hasError())
52             return;
53
54         sinkFloatingTermIfNecessary();
55
56         simplifySunkTerms();
57
58         // Check to see if there are any terms without ? or *.
59         bool matchesEverything = true;
60         for (const auto& term : m_sunkTerms) {
61             if (term.matchesAtLeastOneCharacter()) {
62                 matchesEverything = false;
63                 break;
64             }
65         }
66         if (matchesEverything) {
67             fail(URLFilterParser::MatchesEverything);
68             return;
69         }
70
71         combinedURLFilters.addPattern(patternId, m_sunkTerms);
72     }
73
74     URLFilterParser::ParseStatus parseStatus() const
75     {
76         return m_parseStatus;
77     }
78
79     void atomPatternCharacter(UChar character)
80     {
81         if (hasError())
82             return;
83
84         if (!isASCII(character)) {
85             fail(URLFilterParser::NonASCII);
86             return;
87         }
88
89         sinkFloatingTermIfNecessary();
90         ASSERT(!m_floatingTerm.isValid());
91
92         char asciiChararacter = static_cast<char>(character);
93         m_floatingTerm = Term(asciiChararacter, m_patternIsCaseSensitive);
94     }
95
96     void atomBuiltInCharacterClass(JSC::Yarr::BuiltInCharacterClassID builtInCharacterClassID, bool inverted)
97     {
98         if (hasError())
99             return;
100
101         sinkFloatingTermIfNecessary();
102         ASSERT(!m_floatingTerm.isValid());
103
104         if (builtInCharacterClassID == JSC::Yarr::NewlineClassID && inverted)
105             m_floatingTerm = Term(Term::UniversalTransition);
106         else
107             fail(URLFilterParser::UnsupportedCharacterClass);
108     }
109
110     void quantifyAtom(unsigned minimum, unsigned maximum, bool)
111     {
112         if (hasError())
113             return;
114
115         ASSERT(m_floatingTerm.isValid());
116
117         if (!minimum && maximum == 1)
118             m_floatingTerm.quantify(AtomQuantifier::ZeroOrOne);
119         else if (!minimum && maximum == JSC::Yarr::quantifyInfinite)
120             m_floatingTerm.quantify(AtomQuantifier::ZeroOrMore);
121         else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
122             m_floatingTerm.quantify(AtomQuantifier::OneOrMore);
123         else
124             fail(URLFilterParser::InvalidQuantifier);
125     }
126
127     void atomBackReference(unsigned)
128     {
129         fail(URLFilterParser::BackReference);
130     }
131
132     void assertionBOL()
133     {
134         if (hasError())
135             return;
136
137         if (m_floatingTerm.isValid() || !m_sunkTerms.isEmpty() || !m_openGroups.isEmpty()) {
138             fail(URLFilterParser::MisplacedStartOfLine);
139             return;
140         }
141
142         m_hasBeginningOfLineAssertion = true;
143     }
144
145     void assertionEOL()
146     {
147         if (hasError())
148             return;
149
150         sinkFloatingTermIfNecessary();
151         ASSERT(!m_floatingTerm.isValid());
152
153         m_floatingTerm = Term(Term::EndOfLineAssertionTerm);
154     }
155
156     void assertionWordBoundary(bool)
157     {
158         fail(URLFilterParser::WordBoundary);
159     }
160
161     void atomCharacterClassBegin(bool inverted = false)
162     {
163         if (hasError())
164             return;
165
166         sinkFloatingTermIfNecessary();
167         ASSERT(!m_floatingTerm.isValid());
168
169         m_floatingTerm = Term(Term::CharacterSetTerm, inverted);
170     }
171
172     void atomCharacterClassAtom(UChar character)
173     {
174         if (hasError())
175             return;
176
177         ASSERT(isASCII(character));
178
179         m_floatingTerm.addCharacter(character, m_patternIsCaseSensitive);
180     }
181
182     void atomCharacterClassRange(UChar a, UChar b)
183     {
184         if (hasError())
185             return;
186
187         ASSERT(a);
188         ASSERT(b);
189         ASSERT(isASCII(a));
190         ASSERT(isASCII(b));
191
192         for (unsigned i = a; i <= b; ++i)
193             m_floatingTerm.addCharacter(static_cast<UChar>(i), m_patternIsCaseSensitive);
194     }
195
196     void atomCharacterClassEnd()
197     {
198         // Nothing to do here. The character set atom may have a quantifier, we sink the atom lazily.
199     }
200
201     void atomCharacterClassBuiltIn(JSC::Yarr::BuiltInCharacterClassID, bool)
202     {
203         fail(URLFilterParser::AtomCharacter);
204     }
205
206     void atomParenthesesSubpatternBegin(bool = true)
207     {
208         if (hasError())
209             return;
210
211         sinkFloatingTermIfNecessary();
212
213         m_openGroups.append(Term(Term::GroupTerm));
214     }
215
216     void atomParentheticalAssertionBegin(bool = false)
217     {
218         fail(URLFilterParser::Group);
219     }
220
221     void atomParenthesesEnd()
222     {
223         if (hasError())
224             return;
225
226         sinkFloatingTermIfNecessary();
227         ASSERT(!m_floatingTerm.isValid());
228
229         m_floatingTerm = m_openGroups.takeLast();
230     }
231
232     void disjunction()
233     {
234         fail(URLFilterParser::Disjunction);
235     }
236
237 private:
238     bool hasError() const
239     {
240         return m_parseStatus != URLFilterParser::Ok;
241     }
242
243     void fail(URLFilterParser::ParseStatus reason)
244     {
245         if (hasError())
246             return;
247
248         m_parseStatus = reason;
249     }
250
251     void sinkFloatingTermIfNecessary()
252     {
253         if (!m_floatingTerm.isValid())
254             return;
255
256         if (m_hasProcessedEndOfLineAssertion) {
257             fail(URLFilterParser::MisplacedEndOfLine);
258             m_floatingTerm = Term();
259             return;
260         }
261
262         if (m_floatingTerm.isEndOfLineAssertion())
263             m_hasProcessedEndOfLineAssertion = true;
264
265         if (!m_openGroups.isEmpty()) {
266             m_openGroups.last().extendGroupSubpattern(m_floatingTerm);
267             m_floatingTerm = Term();
268             return;
269         }
270
271         m_sunkTerms.append(m_floatingTerm);
272         m_floatingTerm = Term();
273     }
274
275     void simplifySunkTerms()
276     {
277         ASSERT(!m_floatingTerm.isValid());
278
279         if (m_sunkTerms.isEmpty())
280             return;
281
282         Term canonicalDotStar(Term::UniversalTransition);
283         canonicalDotStar.quantify(AtomQuantifier::ZeroOrMore);
284
285         // Replace every ".*"-like terms by our canonical version. Remove any duplicate ".*".
286         {
287             unsigned termIndex = 0;
288             bool isAfterDotStar = false;
289             while (termIndex < m_sunkTerms.size()) {
290                 if (isAfterDotStar && m_sunkTerms[termIndex].isKnownToMatchAnyString()) {
291                     m_sunkTerms.remove(termIndex);
292                     continue;
293                 }
294                 isAfterDotStar = false;
295
296                 if (m_sunkTerms[termIndex].isKnownToMatchAnyString()) {
297                     m_sunkTerms[termIndex] = canonicalDotStar;
298                     isAfterDotStar = true;
299                 }
300                 ++termIndex;
301             }
302         }
303
304         // Add our ".*" in front if needed.
305         if (!m_hasBeginningOfLineAssertion && !m_sunkTerms.first().isKnownToMatchAnyString())
306             m_sunkTerms.insert(0, canonicalDotStar);
307
308         // Remove trailing ".*$".
309         if (m_sunkTerms.size() > 2 && m_sunkTerms.last().isEndOfLineAssertion() && m_sunkTerms[m_sunkTerms.size() - 2].isKnownToMatchAnyString())
310             m_sunkTerms.shrink(m_sunkTerms.size() - 2);
311
312         // Remove irrelevant terms that can match empty. For example in "foob?", matching "b" is irrelevant.
313         if (m_sunkTerms.last().isEndOfLineAssertion())
314             return;
315         while (!m_sunkTerms.isEmpty() && !m_sunkTerms.last().matchesAtLeastOneCharacter())
316             m_sunkTerms.removeLast();
317     }
318
319     bool m_patternIsCaseSensitive;
320
321     Deque<Term> m_openGroups;
322     Vector<Term> m_sunkTerms;
323     Term m_floatingTerm;
324     bool m_hasBeginningOfLineAssertion { false };
325     bool m_hasProcessedEndOfLineAssertion { false };
326
327     URLFilterParser::ParseStatus m_parseStatus;
328 };
329
330 URLFilterParser::URLFilterParser(CombinedURLFilters& combinedURLFilters)
331     : m_combinedURLFilters(combinedURLFilters)
332 {
333 }
334
335 URLFilterParser::~URLFilterParser()
336 {
337 }
338
339 URLFilterParser::ParseStatus URLFilterParser::addPattern(const String& pattern, bool patternIsCaseSensitive, uint64_t patternId)
340 {
341     if (!pattern.containsOnlyASCII())
342         return NonASCII;
343     if (pattern.isEmpty())
344         return EmptyPattern;
345
346     ParseStatus status = Ok;
347     PatternParser patternParser(patternIsCaseSensitive);
348     String error = String(JSC::Yarr::parse(patternParser, pattern, false, 0));
349     if (error.isNull())
350         patternParser.finalize(patternId, m_combinedURLFilters);
351     else
352         status = YarrError;
353     
354     if (status == Ok)
355         status = patternParser.parseStatus();
356
357     return status;
358 }
359
360 String URLFilterParser::statusString(ParseStatus status)
361 {
362     switch (status) {
363     case Ok:
364         return "Ok";
365     case MatchesEverything:
366         return "Matches everything.";
367     case NonASCII:
368         return "Only ASCII characters are supported in pattern.";
369     case UnsupportedCharacterClass:
370         return "Character class is not supported.";
371     case BackReference:
372         return "Patterns cannot contain backreferences.";
373     case MisplacedStartOfLine:
374         return "Start of line assertion can only appear as the first term in a filter.";
375     case WordBoundary:
376         return "Word boundaries assertions are not supported yet.";
377     case AtomCharacter:
378         return "Builtins character class atoms are not supported yet.";
379     case Group:
380         return "Groups are not supported yet.";
381     case Disjunction:
382         return "Disjunctions are not supported yet.";
383     case MisplacedEndOfLine:
384         return "The end of line assertion must be the last term in an expression.";
385     case EmptyPattern:
386         return "Empty pattern.";
387     case YarrError:
388         return "Internal error in YARR.";
389     case InvalidQuantifier:
390         return "Arbitrary atom repetitions are not supported.";
391     }
392 }
393     
394 } // namespace ContentExtensions
395 } // namespace WebCore
396
397 #endif // ENABLE(CONTENT_EXTENSIONS)