Use "= default" to denote default constructor or destructor
[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::BuiltInCharacterClassID::DotClassID && !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 atomNamedBackReference(String)
133     {
134         fail(URLFilterParser::BackReference);
135     }
136
137     void assertionBOL()
138     {
139         if (hasError())
140             return;
141
142         if (m_floatingTerm.isValid() || !m_sunkTerms.isEmpty() || !m_openGroups.isEmpty()) {
143             fail(URLFilterParser::MisplacedStartOfLine);
144             return;
145         }
146
147         m_hasBeginningOfLineAssertion = true;
148     }
149
150     void assertionEOL()
151     {
152         if (hasError())
153             return;
154
155         sinkFloatingTermIfNecessary();
156         ASSERT(!m_floatingTerm.isValid());
157
158         m_floatingTerm = Term(Term::EndOfLineAssertionTerm);
159     }
160
161     void assertionWordBoundary(bool)
162     {
163         fail(URLFilterParser::WordBoundary);
164     }
165
166     void atomCharacterClassBegin(bool inverted = false)
167     {
168         if (hasError())
169             return;
170
171         sinkFloatingTermIfNecessary();
172         ASSERT(!m_floatingTerm.isValid());
173
174         m_floatingTerm = Term(Term::CharacterSetTerm, inverted);
175     }
176
177     void atomCharacterClassAtom(UChar character)
178     {
179         if (hasError())
180             return;
181
182         ASSERT(isASCII(character));
183
184         m_floatingTerm.addCharacter(character, m_patternIsCaseSensitive);
185     }
186
187     void atomCharacterClassRange(UChar a, UChar b)
188     {
189         if (hasError())
190             return;
191
192         ASSERT(a);
193         ASSERT(b);
194         ASSERT(isASCII(a));
195         ASSERT(isASCII(b));
196
197         for (unsigned i = a; i <= b; ++i)
198             m_floatingTerm.addCharacter(static_cast<UChar>(i), m_patternIsCaseSensitive);
199     }
200
201     void atomCharacterClassEnd()
202     {
203         // Nothing to do here. The character set atom may have a quantifier, we sink the atom lazily.
204     }
205
206     void atomCharacterClassBuiltIn(JSC::Yarr::BuiltInCharacterClassID, bool)
207     {
208         fail(URLFilterParser::AtomCharacter);
209     }
210
211     void atomParenthesesSubpatternBegin(bool = true, std::optional<String> = std::nullopt)
212     {
213         if (hasError())
214             return;
215
216         sinkFloatingTermIfNecessary();
217
218         m_openGroups.append(Term(Term::GroupTerm));
219     }
220
221     void atomParentheticalAssertionBegin(bool = false)
222     {
223         fail(URLFilterParser::Group);
224     }
225
226     void atomParenthesesEnd()
227     {
228         if (hasError())
229             return;
230
231         sinkFloatingTermIfNecessary();
232         ASSERT(!m_floatingTerm.isValid());
233
234         m_floatingTerm = m_openGroups.takeLast();
235     }
236
237     void disjunction()
238     {
239         fail(URLFilterParser::Disjunction);
240     }
241
242 private:
243     bool hasError() const
244     {
245         return m_parseStatus != URLFilterParser::Ok;
246     }
247
248     void fail(URLFilterParser::ParseStatus reason)
249     {
250         if (hasError())
251             return;
252
253         m_parseStatus = reason;
254     }
255
256     void sinkFloatingTermIfNecessary()
257     {
258         if (!m_floatingTerm.isValid())
259             return;
260
261         if (m_hasProcessedEndOfLineAssertion) {
262             fail(URLFilterParser::MisplacedEndOfLine);
263             m_floatingTerm = Term();
264             return;
265         }
266
267         if (m_floatingTerm.isEndOfLineAssertion())
268             m_hasProcessedEndOfLineAssertion = true;
269
270         if (!m_openGroups.isEmpty()) {
271             m_openGroups.last().extendGroupSubpattern(m_floatingTerm);
272             m_floatingTerm = Term();
273             return;
274         }
275
276         m_sunkTerms.append(m_floatingTerm);
277         m_floatingTerm = Term();
278     }
279
280     void simplifySunkTerms()
281     {
282         ASSERT(!m_floatingTerm.isValid());
283
284         if (m_sunkTerms.isEmpty())
285             return;
286
287         Term canonicalDotStar(Term::UniversalTransition);
288         canonicalDotStar.quantify(AtomQuantifier::ZeroOrMore);
289
290         // Replace every ".*"-like terms by our canonical version. Remove any duplicate ".*".
291         {
292             unsigned termIndex = 0;
293             bool isAfterDotStar = false;
294             while (termIndex < m_sunkTerms.size()) {
295                 if (isAfterDotStar && m_sunkTerms[termIndex].isKnownToMatchAnyString()) {
296                     m_sunkTerms.remove(termIndex);
297                     continue;
298                 }
299                 isAfterDotStar = false;
300
301                 if (m_sunkTerms[termIndex].isKnownToMatchAnyString()) {
302                     m_sunkTerms[termIndex] = canonicalDotStar;
303                     isAfterDotStar = true;
304                 }
305                 ++termIndex;
306             }
307         }
308
309         // Add our ".*" in front if needed.
310         if (!m_hasBeginningOfLineAssertion && !m_sunkTerms.first().isKnownToMatchAnyString())
311             m_sunkTerms.insert(0, canonicalDotStar);
312
313         // Remove trailing ".*$".
314         if (m_sunkTerms.size() > 2 && m_sunkTerms.last().isEndOfLineAssertion() && m_sunkTerms[m_sunkTerms.size() - 2].isKnownToMatchAnyString())
315             m_sunkTerms.shrink(m_sunkTerms.size() - 2);
316
317         // Remove irrelevant terms that can match empty. For example in "foob?", matching "b" is irrelevant.
318         if (m_sunkTerms.last().isEndOfLineAssertion())
319             return;
320         while (!m_sunkTerms.isEmpty() && !m_sunkTerms.last().matchesAtLeastOneCharacter())
321             m_sunkTerms.removeLast();
322     }
323
324     bool m_patternIsCaseSensitive;
325
326     Deque<Term> m_openGroups;
327     Vector<Term> m_sunkTerms;
328     Term m_floatingTerm;
329     bool m_hasBeginningOfLineAssertion { false };
330     bool m_hasProcessedEndOfLineAssertion { false };
331
332     URLFilterParser::ParseStatus m_parseStatus;
333 };
334
335 URLFilterParser::URLFilterParser(CombinedURLFilters& combinedURLFilters)
336     : m_combinedURLFilters(combinedURLFilters)
337 {
338 }
339
340 URLFilterParser::~URLFilterParser() = default;
341
342 URLFilterParser::ParseStatus URLFilterParser::addPattern(const String& pattern, bool patternIsCaseSensitive, uint64_t patternId)
343 {
344     if (!pattern.containsOnlyASCII())
345         return NonASCII;
346     if (pattern.isEmpty())
347         return EmptyPattern;
348
349     ParseStatus status = Ok;
350     PatternParser patternParser(patternIsCaseSensitive);
351     String error = String(JSC::Yarr::parse(patternParser, pattern, false, 0));
352     if (error.isNull())
353         patternParser.finalize(patternId, m_combinedURLFilters);
354     else
355         status = YarrError;
356     
357     if (status == Ok)
358         status = patternParser.parseStatus();
359
360     return status;
361 }
362
363 String URLFilterParser::statusString(ParseStatus status)
364 {
365     switch (status) {
366     case Ok:
367         return "Ok";
368     case MatchesEverything:
369         return "Matches everything.";
370     case NonASCII:
371         return "Only ASCII characters are supported in pattern.";
372     case UnsupportedCharacterClass:
373         return "Character class is not supported.";
374     case BackReference:
375         return "Patterns cannot contain backreferences.";
376     case MisplacedStartOfLine:
377         return "Start of line assertion can only appear as the first term in a filter.";
378     case WordBoundary:
379         return "Word boundaries assertions are not supported yet.";
380     case AtomCharacter:
381         return "Builtins character class atoms are not supported yet.";
382     case Group:
383         return "Groups are not supported yet.";
384     case Disjunction:
385         return "Disjunctions are not supported yet.";
386     case MisplacedEndOfLine:
387         return "The end of line assertion must be the last term in an expression.";
388     case EmptyPattern:
389         return "Empty pattern.";
390     case YarrError:
391         return "Internal error in YARR.";
392     case InvalidQuantifier:
393         return "Arbitrary atom repetitions are not supported.";
394     }
395 }
396     
397 } // namespace ContentExtensions
398 } // namespace WebCore
399
400 #endif // ENABLE(CONTENT_EXTENSIONS)