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