Make URL filters case-insensitive by default
[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         if (builtInCharacterClassID == JSC::Yarr::NewlineClassID && inverted) {
130             m_hasValidAtom = true;
131             ASSERT(m_lastPrefixTreeEntry);
132             m_pendingTrivialAtom = trivialAtomForNewlineClassIDBuiltin();
133         } else
134             fail(ASCIILiteral("Character class is not supported."));
135     }
136
137     void quantifyAtom(unsigned minimum, unsigned maximum, bool)
138     {
139         if (hasError())
140             return;
141
142         ASSERT(m_hasValidAtom);
143         if (!m_hasValidAtom) {
144             fail(ASCIILiteral("Quantifier without corresponding atom to quantify."));
145             return;
146         }
147
148         ASSERT(m_lastPrefixTreeEntry);
149         if (!minimum && maximum == 1)
150             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::ZeroOrOne);
151         else if (!minimum && maximum == JSC::Yarr::quantifyInfinite)
152             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::ZeroToMany);
153         else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
154             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::OneToMany);
155         else
156             fail(ASCIILiteral("Arbitrary atom repetitions are not supported."));
157     }
158
159     NO_RETURN_DUE_TO_ASSERT void atomBackReference(unsigned)
160     {
161         fail(ASCIILiteral("Patterns cannot contain backreferences."));
162         ASSERT_NOT_REACHED();
163     }
164
165     void atomCharacterClassAtom(UChar)
166     {
167         fail(ASCIILiteral("Character class atoms are not supported yet."));
168     }
169
170     void assertionBOL()
171     {
172         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
173     }
174
175     void assertionEOL()
176     {
177         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
178     }
179
180     void assertionWordBoundary(bool)
181     {
182         fail(ASCIILiteral("Word boundaries assertions are not supported yet."));
183     }
184
185     void atomCharacterClassBegin(bool = false)
186     {
187         fail(ASCIILiteral("Character class atoms are not supported yet."));
188     }
189
190     void atomCharacterClassRange(UChar, UChar)
191     {
192         fail(ASCIILiteral("Character class ranges are not supported yet."));
193     }
194
195     void atomCharacterClassBuiltIn(JSC::Yarr::BuiltInCharacterClassID, bool)
196     {
197         fail(ASCIILiteral("Buildins character class atoms are not supported yet."));
198     }
199
200     void atomCharacterClassEnd()
201     {
202         fail(ASCIILiteral("Character class are not supported yet."));
203     }
204
205     void atomParenthesesSubpatternBegin(bool = true)
206     {
207         fail(ASCIILiteral("Groups are not supported yet."));
208     }
209
210     void atomParentheticalAssertionBegin(bool = false)
211     {
212         fail(ASCIILiteral("Groups are not supported yet."));
213     }
214
215     void atomParenthesesEnd()
216     {
217         fail(ASCIILiteral("Groups are not supported yet."));
218     }
219
220     void disjunction()
221     {
222         fail(ASCIILiteral("Disjunctions are not supported yet."));
223     }
224
225 private:
226     bool hasError() const
227     {
228         return !m_errorMessage.isNull();
229     }
230
231     void fail(const String& errorMessage)
232     {
233         if (hasError())
234             return;
235
236         if (m_newPrefixSubtreeRoot)
237             m_newPrefixSubtreeRoot->nextPattern.remove(m_newPrefixStaringPoint);
238
239         m_errorMessage = errorMessage;
240     }
241
242     void generateTransition(TrivialAtom trivialAtom, unsigned source, unsigned target)
243     {
244         if (trivialAtom & hasNonCharacterMask) {
245             ASSERT(trivialAtom & newlineClassIDBuiltinMask);
246             for (unsigned i = 1; i < 128; ++i)
247                 m_nfa.addTransition(source, target, i);
248         } else {
249             if (trivialAtom & caseInsensitiveMask) {
250                 char character = static_cast<char>(trivialAtom & characterMask);
251                 m_nfa.addTransition(source, target, character);
252                 m_nfa.addTransition(source, target, toASCIIUpper(character));
253             } else
254                 m_nfa.addTransition(source, target, static_cast<char>(trivialAtom & characterMask));
255         }
256     }
257
258     BoundedSubGraph sinkTrivialAtom(TrivialAtom trivialAtom, unsigned start)
259     {
260         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroOrOne)) {
261             unsigned newEnd = m_nfa.createNode();
262             m_nfa.addRuleId(newEnd, m_patternId);
263             generateTransition(trivialAtom, start, newEnd);
264             m_nfa.addEpsilonTransition(start, newEnd);
265             return { start, newEnd };
266         }
267
268         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroToMany)) {
269             unsigned repeatStart = m_nfa.createNode();
270             m_nfa.addRuleId(repeatStart, m_patternId);
271             unsigned repeatEnd = m_nfa.createNode();
272             m_nfa.addRuleId(repeatEnd, m_patternId);
273
274             generateTransition(trivialAtom, repeatStart, repeatEnd);
275             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
276
277             m_nfa.addEpsilonTransition(start, repeatStart);
278
279             unsigned kleenEnd = m_nfa.createNode();
280             m_nfa.addRuleId(kleenEnd, m_patternId);
281             m_nfa.addEpsilonTransition(repeatEnd, kleenEnd);
282             m_nfa.addEpsilonTransition(start, kleenEnd);
283             return { start, kleenEnd };
284         }
285
286         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::OneToMany)) {
287             unsigned repeatStart = m_nfa.createNode();
288             m_nfa.addRuleId(repeatStart, m_patternId);
289             unsigned repeatEnd = m_nfa.createNode();
290             m_nfa.addRuleId(repeatEnd, m_patternId);
291
292             generateTransition(trivialAtom, repeatStart, repeatEnd);
293             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
294
295             m_nfa.addEpsilonTransition(start, repeatStart);
296
297             unsigned afterRepeat = m_nfa.createNode();
298             m_nfa.addRuleId(afterRepeat, m_patternId);
299             m_nfa.addEpsilonTransition(repeatEnd, afterRepeat);
300             return { start, afterRepeat };
301         }
302
303         unsigned newEnd = m_nfa.createNode();
304         m_nfa.addRuleId(newEnd, m_patternId);
305         generateTransition(trivialAtom, start, newEnd);
306         return { start, newEnd };
307     }
308
309     void sinkPendingAtomIfNecessary()
310     {
311         ASSERT(m_lastPrefixTreeEntry);
312
313         if (!m_hasValidAtom)
314             return;
315
316         ASSERT(m_pendingTrivialAtom);
317
318         auto nextEntry = m_lastPrefixTreeEntry->nextPattern.find(m_pendingTrivialAtom);
319         if (nextEntry != m_lastPrefixTreeEntry->nextPattern.end()) {
320             m_lastPrefixTreeEntry = nextEntry->value.get();
321             m_nfa.addRuleId(m_lastPrefixTreeEntry->nfaNode, m_patternId);
322         } else {
323             std::unique_ptr<PrefixTreeEntry> nextPrefixTreeEntry = std::make_unique<PrefixTreeEntry>();
324
325             BoundedSubGraph newSubGraph = sinkTrivialAtom(m_pendingTrivialAtom, m_lastPrefixTreeEntry->nfaNode);
326             nextPrefixTreeEntry->nfaNode = newSubGraph.end;
327
328             auto addResult = m_lastPrefixTreeEntry->nextPattern.set(m_pendingTrivialAtom, WTF::move(nextPrefixTreeEntry));
329             ASSERT(addResult.isNewEntry);
330
331             m_newPrefixSubtreeRoot = m_lastPrefixTreeEntry;
332             m_newPrefixStaringPoint = m_pendingTrivialAtom;
333
334             m_lastPrefixTreeEntry = addResult.iterator->value.get();
335         }
336         ASSERT(m_lastPrefixTreeEntry);
337
338         m_activeGroup.end = m_lastPrefixTreeEntry->nfaNode;
339         m_pendingTrivialAtom = 0;
340         m_hasValidAtom = false;
341     }
342
343     NFA& m_nfa;
344     bool m_patternIsCaseSensitive;
345     const uint64_t m_patternId;
346
347     BoundedSubGraph m_activeGroup;
348
349     PrefixTreeEntry* m_lastPrefixTreeEntry;
350     bool m_hasValidAtom = false;
351     TrivialAtom m_pendingTrivialAtom = 0;
352
353     PrefixTreeEntry* m_newPrefixSubtreeRoot = nullptr;
354     TrivialAtom m_newPrefixStaringPoint = 0;
355
356     String m_errorMessage;
357 };
358
359 URLFilterParser::URLFilterParser(NFA& nfa)
360     : m_nfa(nfa)
361 {
362     m_prefixTreeRoot.nfaNode = nfa.root();
363 }
364
365 String URLFilterParser::addPattern(const String& pattern, bool patternIsCaseSensitive, uint64_t patternId)
366 {
367     if (!pattern.containsOnlyASCII())
368         return ASCIILiteral("URLFilterParser only supports ASCII patterns.");
369     ASSERT(!pattern.isEmpty());
370
371     if (pattern.isEmpty())
372         return ASCIILiteral("Empty pattern.");
373
374     unsigned oldSize = m_nfa.graphSize();
375
376     String error;
377
378     GraphBuilder graphBuilder(m_nfa, m_prefixTreeRoot, patternIsCaseSensitive, patternId);
379     error = String(JSC::Yarr::parse(graphBuilder, pattern, 0));
380     if (error.isNull())
381         graphBuilder.finalize();
382
383     if (error.isNull())
384         error = graphBuilder.errorMessage();
385
386     if (!error.isNull())
387         m_nfa.restoreToGraphSize(oldSize);
388
389     return error;
390 }
391
392 } // namespace ContentExtensions
393 } // namespace WebCore
394
395 #endif // ENABLE(CONTENT_EXTENSIONS)