Handle the transition on any character as a separate type of transition
[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             m_nfa.addTransitionsOnAnyCharacter(source, target);
249         } else {
250             if (trivialAtom & caseInsensitiveMask) {
251                 char character = static_cast<char>(trivialAtom & characterMask);
252                 m_nfa.addTransition(source, target, character);
253                 m_nfa.addTransition(source, target, toASCIIUpper(character));
254             } else
255                 m_nfa.addTransition(source, target, static_cast<char>(trivialAtom & characterMask));
256         }
257     }
258
259     BoundedSubGraph sinkTrivialAtom(TrivialAtom trivialAtom, unsigned start)
260     {
261         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroOrOne)) {
262             unsigned newEnd = m_nfa.createNode();
263             m_nfa.addRuleId(newEnd, m_patternId);
264             generateTransition(trivialAtom, start, newEnd);
265             m_nfa.addEpsilonTransition(start, newEnd);
266             return { start, newEnd };
267         }
268
269         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroToMany)) {
270             unsigned repeatStart = m_nfa.createNode();
271             m_nfa.addRuleId(repeatStart, m_patternId);
272             unsigned repeatEnd = m_nfa.createNode();
273             m_nfa.addRuleId(repeatEnd, m_patternId);
274
275             generateTransition(trivialAtom, repeatStart, repeatEnd);
276             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
277
278             m_nfa.addEpsilonTransition(start, repeatStart);
279
280             unsigned kleenEnd = m_nfa.createNode();
281             m_nfa.addRuleId(kleenEnd, m_patternId);
282             m_nfa.addEpsilonTransition(repeatEnd, kleenEnd);
283             m_nfa.addEpsilonTransition(start, kleenEnd);
284             return { start, kleenEnd };
285         }
286
287         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::OneToMany)) {
288             unsigned repeatStart = m_nfa.createNode();
289             m_nfa.addRuleId(repeatStart, m_patternId);
290             unsigned repeatEnd = m_nfa.createNode();
291             m_nfa.addRuleId(repeatEnd, m_patternId);
292
293             generateTransition(trivialAtom, repeatStart, repeatEnd);
294             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
295
296             m_nfa.addEpsilonTransition(start, repeatStart);
297
298             unsigned afterRepeat = m_nfa.createNode();
299             m_nfa.addRuleId(afterRepeat, m_patternId);
300             m_nfa.addEpsilonTransition(repeatEnd, afterRepeat);
301             return { start, afterRepeat };
302         }
303
304         unsigned newEnd = m_nfa.createNode();
305         m_nfa.addRuleId(newEnd, m_patternId);
306         generateTransition(trivialAtom, start, newEnd);
307         return { start, newEnd };
308     }
309
310     void sinkPendingAtomIfNecessary()
311     {
312         ASSERT(m_lastPrefixTreeEntry);
313
314         if (!m_hasValidAtom)
315             return;
316
317         ASSERT(m_pendingTrivialAtom);
318
319         auto nextEntry = m_lastPrefixTreeEntry->nextPattern.find(m_pendingTrivialAtom);
320         if (nextEntry != m_lastPrefixTreeEntry->nextPattern.end()) {
321             m_lastPrefixTreeEntry = nextEntry->value.get();
322             m_nfa.addRuleId(m_lastPrefixTreeEntry->nfaNode, m_patternId);
323         } else {
324             std::unique_ptr<PrefixTreeEntry> nextPrefixTreeEntry = std::make_unique<PrefixTreeEntry>();
325
326             BoundedSubGraph newSubGraph = sinkTrivialAtom(m_pendingTrivialAtom, m_lastPrefixTreeEntry->nfaNode);
327             nextPrefixTreeEntry->nfaNode = newSubGraph.end;
328
329             auto addResult = m_lastPrefixTreeEntry->nextPattern.set(m_pendingTrivialAtom, WTF::move(nextPrefixTreeEntry));
330             ASSERT(addResult.isNewEntry);
331
332             m_newPrefixSubtreeRoot = m_lastPrefixTreeEntry;
333             m_newPrefixStaringPoint = m_pendingTrivialAtom;
334
335             m_lastPrefixTreeEntry = addResult.iterator->value.get();
336         }
337         ASSERT(m_lastPrefixTreeEntry);
338
339         m_activeGroup.end = m_lastPrefixTreeEntry->nfaNode;
340         m_pendingTrivialAtom = 0;
341         m_hasValidAtom = false;
342     }
343
344     NFA& m_nfa;
345     bool m_patternIsCaseSensitive;
346     const uint64_t m_patternId;
347
348     BoundedSubGraph m_activeGroup;
349
350     PrefixTreeEntry* m_lastPrefixTreeEntry;
351     bool m_hasValidAtom = false;
352     TrivialAtom m_pendingTrivialAtom = 0;
353
354     PrefixTreeEntry* m_newPrefixSubtreeRoot = nullptr;
355     TrivialAtom m_newPrefixStaringPoint = 0;
356
357     String m_errorMessage;
358 };
359
360 URLFilterParser::URLFilterParser(NFA& nfa)
361     : m_nfa(nfa)
362 {
363     m_prefixTreeRoot.nfaNode = nfa.root();
364 }
365
366 String URLFilterParser::addPattern(const String& pattern, bool patternIsCaseSensitive, uint64_t patternId)
367 {
368     if (!pattern.containsOnlyASCII())
369         return ASCIILiteral("URLFilterParser only supports ASCII patterns.");
370     ASSERT(!pattern.isEmpty());
371
372     if (pattern.isEmpty())
373         return ASCIILiteral("Empty pattern.");
374
375     unsigned oldSize = m_nfa.graphSize();
376
377     String error;
378
379     GraphBuilder graphBuilder(m_nfa, m_prefixTreeRoot, patternIsCaseSensitive, patternId);
380     error = String(JSC::Yarr::parse(graphBuilder, pattern, 0));
381     if (error.isNull())
382         graphBuilder.finalize();
383
384     if (error.isNull())
385         error = graphBuilder.errorMessage();
386
387     if (!error.isNull())
388         m_nfa.restoreToGraphSize(oldSize);
389
390     return error;
391 }
392
393 } // namespace ContentExtensions
394 } // namespace WebCore
395
396 #endif // ENABLE(CONTENT_EXTENSIONS)