URLFilterParser dismisses the last atom when parsing a builtin character class
[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
34 namespace WebCore {
35
36 namespace ContentExtensions {
37
38 const uint16_t hasNonCharacterMask = 0x0080;
39 const uint16_t characterMask = 0x0007F;
40 const uint16_t newlineClassIDBuiltinMask = 0x100;
41 const uint16_t caseInsensitiveMask = 0x200;
42
43 static TrivialAtom trivialAtomFromASCIICharacter(char character, bool caseSensitive)
44 {
45     ASSERT(isASCII(character));
46
47     if (caseSensitive || !isASCIIAlpha(character))
48         return static_cast<uint16_t>(character);
49
50     return static_cast<uint16_t>(toASCIILower(character)) | caseInsensitiveMask;
51 }
52
53 enum class TrivialAtomQuantifier : uint16_t {
54     ZeroOrOne = 0x1000,
55     ZeroToMany = 0x2000,
56     OneToMany = 0x4000
57 };
58
59 static void quantifyTrivialAtom(TrivialAtom& trivialAtom, TrivialAtomQuantifier quantifier)
60 {
61     ASSERT(trivialAtom & (hasNonCharacterMask | characterMask));
62     ASSERT(!(trivialAtom & 0xf000));
63     trivialAtom |= static_cast<uint16_t>(quantifier);
64 }
65
66 static TrivialAtom trivialAtomForNewlineClassIDBuiltin()
67 {
68     return hasNonCharacterMask | newlineClassIDBuiltinMask;
69 }
70
71 class GraphBuilder {
72 private:
73     struct BoundedSubGraph {
74         unsigned start;
75         unsigned end;
76     };
77 public:
78     GraphBuilder(NFA& nfa, PrefixTreeEntry& prefixTreeRoot, bool patternIsCaseSensitive, uint64_t patternId)
79         : m_nfa(nfa)
80         , m_patternIsCaseSensitive(patternIsCaseSensitive)
81         , m_patternId(patternId)
82         , m_activeGroup({ nfa.root(), nfa.root() })
83         , m_lastPrefixTreeEntry(&prefixTreeRoot)
84     {
85     }
86
87     void finalize()
88     {
89         if (hasError())
90             return;
91
92         sinkPendingAtomIfNecessary();
93
94         if (m_activeGroup.start != m_activeGroup.end)
95             m_nfa.setFinal(m_activeGroup.end, m_patternId);
96         else
97             fail(ASCIILiteral("The pattern cannot match anything."));
98     }
99
100     const String& errorMessage() const
101     {
102         return m_errorMessage;
103     }
104
105     void atomPatternCharacter(UChar character)
106     {
107         if (!isASCII(character)) {
108             fail(ASCIILiteral("Only ASCII characters are supported in pattern."));
109             return;
110         }
111
112         if (hasError())
113             return;
114
115         sinkPendingAtomIfNecessary();
116
117         char asciiChararacter = static_cast<char>(character);
118         m_hasValidAtom = true;
119
120         ASSERT(m_lastPrefixTreeEntry);
121         m_pendingTrivialAtom = trivialAtomFromASCIICharacter(asciiChararacter, m_patternIsCaseSensitive);
122     }
123
124     void atomBuiltInCharacterClass(JSC::Yarr::BuiltInCharacterClassID builtInCharacterClassID, bool inverted)
125     {
126         if (hasError())
127             return;
128
129         sinkPendingAtomIfNecessary();
130
131         if (builtInCharacterClassID == JSC::Yarr::NewlineClassID && inverted) {
132             m_hasValidAtom = true;
133             ASSERT(m_lastPrefixTreeEntry);
134             m_pendingTrivialAtom = trivialAtomForNewlineClassIDBuiltin();
135         } else
136             fail(ASCIILiteral("Character class is not supported."));
137     }
138
139     void quantifyAtom(unsigned minimum, unsigned maximum, bool)
140     {
141         if (hasError())
142             return;
143
144         ASSERT(m_hasValidAtom);
145         if (!m_hasValidAtom) {
146             fail(ASCIILiteral("Quantifier without corresponding atom to quantify."));
147             return;
148         }
149
150         ASSERT(m_lastPrefixTreeEntry);
151         if (!minimum && maximum == 1)
152             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::ZeroOrOne);
153         else if (!minimum && maximum == JSC::Yarr::quantifyInfinite)
154             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::ZeroToMany);
155         else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
156             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::OneToMany);
157         else
158             fail(ASCIILiteral("Arbitrary atom repetitions are not supported."));
159     }
160
161     NO_RETURN_DUE_TO_ASSERT void atomBackReference(unsigned)
162     {
163         fail(ASCIILiteral("Patterns cannot contain backreferences."));
164         ASSERT_NOT_REACHED();
165     }
166
167     void atomCharacterClassAtom(UChar)
168     {
169         fail(ASCIILiteral("Character class atoms are not supported yet."));
170     }
171
172     void assertionBOL()
173     {
174         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
175     }
176
177     void assertionEOL()
178     {
179         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
180     }
181
182     void assertionWordBoundary(bool)
183     {
184         fail(ASCIILiteral("Word boundaries assertions are not supported yet."));
185     }
186
187     void atomCharacterClassBegin(bool = false)
188     {
189         fail(ASCIILiteral("Character class atoms are not supported yet."));
190     }
191
192     void atomCharacterClassRange(UChar, UChar)
193     {
194         fail(ASCIILiteral("Character class ranges are not supported yet."));
195     }
196
197     void atomCharacterClassBuiltIn(JSC::Yarr::BuiltInCharacterClassID, bool)
198     {
199         fail(ASCIILiteral("Buildins character class atoms are not supported yet."));
200     }
201
202     void atomCharacterClassEnd()
203     {
204         fail(ASCIILiteral("Character class are not supported yet."));
205     }
206
207     void atomParenthesesSubpatternBegin(bool = true)
208     {
209         fail(ASCIILiteral("Groups are not supported yet."));
210     }
211
212     void atomParentheticalAssertionBegin(bool = false)
213     {
214         fail(ASCIILiteral("Groups are not supported yet."));
215     }
216
217     void atomParenthesesEnd()
218     {
219         fail(ASCIILiteral("Groups are not supported yet."));
220     }
221
222     void disjunction()
223     {
224         fail(ASCIILiteral("Disjunctions are not supported yet."));
225     }
226
227 private:
228     bool hasError() const
229     {
230         return !m_errorMessage.isNull();
231     }
232
233     void fail(const String& errorMessage)
234     {
235         if (hasError())
236             return;
237
238         if (m_newPrefixSubtreeRoot)
239             m_newPrefixSubtreeRoot->nextPattern.remove(m_newPrefixStaringPoint);
240
241         m_errorMessage = errorMessage;
242     }
243
244     void generateTransition(TrivialAtom trivialAtom, unsigned source, unsigned target)
245     {
246         if (trivialAtom & hasNonCharacterMask) {
247             ASSERT(trivialAtom & newlineClassIDBuiltinMask);
248             for (unsigned i = 1; i < 128; ++i)
249                 m_nfa.addTransition(source, target, i);
250         } else {
251             if (trivialAtom & caseInsensitiveMask) {
252                 char character = static_cast<char>(trivialAtom & characterMask);
253                 m_nfa.addTransition(source, target, character);
254                 m_nfa.addTransition(source, target, toASCIIUpper(character));
255             } else
256                 m_nfa.addTransition(source, target, static_cast<char>(trivialAtom & characterMask));
257         }
258     }
259
260     BoundedSubGraph sinkTrivialAtom(TrivialAtom trivialAtom, unsigned start)
261     {
262         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroOrOne)) {
263             unsigned newEnd = m_nfa.createNode();
264             m_nfa.addRuleId(newEnd, m_patternId);
265             generateTransition(trivialAtom, start, newEnd);
266             m_nfa.addEpsilonTransition(start, newEnd);
267             return { start, newEnd };
268         }
269
270         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroToMany)) {
271             unsigned repeatStart = m_nfa.createNode();
272             m_nfa.addRuleId(repeatStart, m_patternId);
273             unsigned repeatEnd = m_nfa.createNode();
274             m_nfa.addRuleId(repeatEnd, m_patternId);
275
276             generateTransition(trivialAtom, repeatStart, repeatEnd);
277             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
278
279             m_nfa.addEpsilonTransition(start, repeatStart);
280
281             unsigned kleenEnd = m_nfa.createNode();
282             m_nfa.addRuleId(kleenEnd, m_patternId);
283             m_nfa.addEpsilonTransition(repeatEnd, kleenEnd);
284             m_nfa.addEpsilonTransition(start, kleenEnd);
285             return { start, kleenEnd };
286         }
287
288         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::OneToMany)) {
289             unsigned repeatStart = m_nfa.createNode();
290             m_nfa.addRuleId(repeatStart, m_patternId);
291             unsigned repeatEnd = m_nfa.createNode();
292             m_nfa.addRuleId(repeatEnd, m_patternId);
293
294             generateTransition(trivialAtom, repeatStart, repeatEnd);
295             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
296
297             m_nfa.addEpsilonTransition(start, repeatStart);
298
299             unsigned afterRepeat = m_nfa.createNode();
300             m_nfa.addRuleId(afterRepeat, m_patternId);
301             m_nfa.addEpsilonTransition(repeatEnd, afterRepeat);
302             return { start, afterRepeat };
303         }
304
305         unsigned newEnd = m_nfa.createNode();
306         m_nfa.addRuleId(newEnd, m_patternId);
307         generateTransition(trivialAtom, start, newEnd);
308         return { start, newEnd };
309     }
310
311     void sinkPendingAtomIfNecessary()
312     {
313         ASSERT(m_lastPrefixTreeEntry);
314
315         if (!m_hasValidAtom)
316             return;
317
318         ASSERT(m_pendingTrivialAtom);
319
320         auto nextEntry = m_lastPrefixTreeEntry->nextPattern.find(m_pendingTrivialAtom);
321         if (nextEntry != m_lastPrefixTreeEntry->nextPattern.end()) {
322             m_lastPrefixTreeEntry = nextEntry->value.get();
323             m_nfa.addRuleId(m_lastPrefixTreeEntry->nfaNode, m_patternId);
324         } else {
325             std::unique_ptr<PrefixTreeEntry> nextPrefixTreeEntry = std::make_unique<PrefixTreeEntry>();
326
327             BoundedSubGraph newSubGraph = sinkTrivialAtom(m_pendingTrivialAtom, m_lastPrefixTreeEntry->nfaNode);
328             nextPrefixTreeEntry->nfaNode = newSubGraph.end;
329
330             auto addResult = m_lastPrefixTreeEntry->nextPattern.set(m_pendingTrivialAtom, WTF::move(nextPrefixTreeEntry));
331             ASSERT(addResult.isNewEntry);
332
333             m_newPrefixSubtreeRoot = m_lastPrefixTreeEntry;
334             m_newPrefixStaringPoint = m_pendingTrivialAtom;
335
336             m_lastPrefixTreeEntry = addResult.iterator->value.get();
337         }
338         ASSERT(m_lastPrefixTreeEntry);
339
340         m_activeGroup.end = m_lastPrefixTreeEntry->nfaNode;
341         m_pendingTrivialAtom = 0;
342         m_hasValidAtom = false;
343     }
344
345     NFA& m_nfa;
346     bool m_patternIsCaseSensitive;
347     const uint64_t m_patternId;
348
349     BoundedSubGraph m_activeGroup;
350
351     PrefixTreeEntry* m_lastPrefixTreeEntry;
352     bool m_hasValidAtom = false;
353     TrivialAtom m_pendingTrivialAtom = 0;
354
355     PrefixTreeEntry* m_newPrefixSubtreeRoot = nullptr;
356     TrivialAtom m_newPrefixStaringPoint = 0;
357
358     String m_errorMessage;
359 };
360
361 URLFilterParser::URLFilterParser(NFA& nfa)
362     : m_nfa(nfa)
363 {
364     m_prefixTreeRoot.nfaNode = nfa.root();
365 }
366
367 String URLFilterParser::addPattern(const String& pattern, bool patternIsCaseSensitive, uint64_t patternId)
368 {
369     if (!pattern.containsOnlyASCII())
370         return ASCIILiteral("URLFilterParser only supports ASCII patterns.");
371     ASSERT(!pattern.isEmpty());
372
373     if (pattern.isEmpty())
374         return ASCIILiteral("Empty pattern.");
375
376     unsigned oldSize = m_nfa.graphSize();
377
378     String error;
379
380     GraphBuilder graphBuilder(m_nfa, m_prefixTreeRoot, patternIsCaseSensitive, patternId);
381     error = String(JSC::Yarr::parse(graphBuilder, pattern, 0));
382     if (error.isNull())
383         graphBuilder.finalize();
384
385     if (error.isNull())
386         error = graphBuilder.errorMessage();
387
388     if (!error.isNull())
389         m_nfa.restoreToGraphSize(oldSize);
390
391     return error;
392 }
393
394 } // namespace ContentExtensions
395 } // namespace WebCore
396
397 #endif // ENABLE(CONTENT_EXTENSIONS)