453b636c6bac82c55228dd0fbcf0871fe337d14b
[WebKit-https.git] / Source / WebCore / contentextensions / CombinedURLFilters.cpp
1 /*
2  * Copyright (C) 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 "CombinedURLFilters.h"
28
29 #if ENABLE(CONTENT_EXTENSIONS)
30
31 #include "Term.h"
32 #include <wtf/HashMap.h>
33
34 namespace WebCore {
35
36 namespace ContentExtensions {
37
38 typedef HashMap<Term, std::unique_ptr<PrefixTreeVertex>, TermHash, TermHashTraits> PrefixTreeEdges;
39
40 struct PrefixTreeVertex {
41     PrefixTreeEdges edges;
42     ActionSet finalActions;
43     bool inVariableLengthPrefix { false };
44 };
45
46 CombinedURLFilters::CombinedURLFilters()
47     : m_prefixTreeRoot(std::make_unique<PrefixTreeVertex>())
48 {
49 }
50
51 CombinedURLFilters::~CombinedURLFilters()
52 {
53 }
54
55 void CombinedURLFilters::addPattern(uint64_t actionId, const Vector<Term>& pattern)
56 {
57     ASSERT_WITH_MESSAGE(!pattern.isEmpty(), "The parser should have excluded empty patterns before reaching CombinedURLFilters.");
58
59     if (pattern.isEmpty())
60         return;
61
62     Vector<PrefixTreeVertex*, 128> prefixTreeVerticesForPattern;
63     prefixTreeVerticesForPattern.reserveInitialCapacity(pattern.size() + 1);
64
65     // Extend the prefix tree with the new pattern.
66     bool hasNewTerm = false;
67     PrefixTreeVertex* lastPrefixTree = m_prefixTreeRoot.get();
68     prefixTreeVerticesForPattern.append(lastPrefixTree);
69
70     for (const Term& term : pattern) {
71         auto nextEntry = lastPrefixTree->edges.find(term);
72         if (nextEntry != lastPrefixTree->edges.end())
73             lastPrefixTree = nextEntry->value.get();
74         else {
75             hasNewTerm = true;
76
77             std::unique_ptr<PrefixTreeVertex> nextPrefixTreeVertex = std::make_unique<PrefixTreeVertex>();
78
79             auto addResult = lastPrefixTree->edges.set(term, WTF::move(nextPrefixTreeVertex));
80             ASSERT(addResult.isNewEntry);
81
82             lastPrefixTree = addResult.iterator->value.get();
83         }
84         prefixTreeVerticesForPattern.append(lastPrefixTree);
85     }
86
87     prefixTreeVerticesForPattern.last()->finalActions.add(actionId);
88
89     if (!hasNewTerm)
90         return;
91
92     bool hasSeenVariableLengthTerms = false;
93     for (unsigned i = pattern.size(); i--;) {
94         const Term& term = pattern[i];
95         hasSeenVariableLengthTerms |= !term.hasFixedLength();
96         prefixTreeVerticesForPattern[i + 1]->inVariableLengthPrefix |= hasSeenVariableLengthTerms;
97     }
98     prefixTreeVerticesForPattern[0]->inVariableLengthPrefix |= hasSeenVariableLengthTerms;
99 }
100
101 struct ActiveSubtree {
102     const PrefixTreeVertex* vertex;
103     PrefixTreeEdges::const_iterator iterator;
104 };
105
106 static void generateNFAForSubtree(NFA& nfa, unsigned rootId, const PrefixTreeVertex& prefixTreeVertex)
107 {
108     ASSERT_WITH_MESSAGE(!prefixTreeVertex.inVariableLengthPrefix, "This code assumes the subtrees with variable prefix length have already been handled.");
109
110     struct ActiveNFASubtree : ActiveSubtree {
111         ActiveNFASubtree(const PrefixTreeVertex* vertex, PrefixTreeEdges::const_iterator iterator, unsigned nodeIndex)
112             : ActiveSubtree({ vertex, iterator })
113             , lastNodeIndex(nodeIndex)
114         {
115         }
116         unsigned lastNodeIndex;
117     };
118
119     Vector<ActiveNFASubtree> activeStack;
120     activeStack.append(ActiveNFASubtree(&prefixTreeVertex, prefixTreeVertex.edges.begin(), rootId));
121
122     while (true) {
123     ProcessSubtree:
124         for (ActiveNFASubtree& activeSubtree = activeStack.last(); activeSubtree.iterator != activeSubtree.vertex->edges.end(); ++activeSubtree.iterator) {
125             if (activeSubtree.iterator->value->inVariableLengthPrefix)
126                 continue;
127
128             const Term& term = activeSubtree.iterator->key;
129             unsigned newEndNodeIndex = term.generateGraph(nfa, activeSubtree.lastNodeIndex, activeSubtree.iterator->value->finalActions);
130
131             PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->value.get();
132             if (!prefixTreeVertex->edges.isEmpty()) {
133                 activeStack.append(ActiveNFASubtree(prefixTreeVertex, prefixTreeVertex->edges.begin(), newEndNodeIndex));
134                 goto ProcessSubtree;
135             }
136         }
137
138         activeStack.removeLast();
139         if (activeStack.isEmpty())
140             break;
141         ++activeStack.last().iterator;
142     }
143 }
144
145 Vector<NFA> CombinedURLFilters::createNFAs() const
146 {
147     Vector<ActiveSubtree> activeStack;
148     activeStack.append(ActiveSubtree({ m_prefixTreeRoot.get(), m_prefixTreeRoot->edges.begin() }));
149
150     Vector<NFA> nfas;
151
152     while (true) {
153     ProcessSubtree:
154         ActiveSubtree& activeSubtree = activeStack.last();
155
156         // We go depth first into the subtrees with variable prefix. Find the next subtree.
157         for (; activeSubtree.iterator != activeSubtree.vertex->edges.end(); ++activeSubtree.iterator) {
158             PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->value.get();
159             if (prefixTreeVertex->inVariableLengthPrefix) {
160                 activeStack.append(ActiveSubtree({ prefixTreeVertex, prefixTreeVertex->edges.begin() }));
161                 goto ProcessSubtree;
162             }
163         }
164
165         // After we reached here, we know that all the subtrees with variable prefixes have been processed,
166         // time to generate the NFA for the graph rooted here.
167         bool needToGenerate = activeSubtree.vertex->edges.isEmpty() && !activeSubtree.vertex->finalActions.isEmpty();
168         if (!needToGenerate) {
169             for (const auto& edge : activeSubtree.vertex->edges) {
170                 if (!edge.value->inVariableLengthPrefix) {
171                     needToGenerate = true;
172                     break;
173                 }
174             }
175         }
176
177         if (needToGenerate) {
178             nfas.append(NFA());
179             NFA& generatingNFA = nfas.last();
180
181             unsigned prefixEnd = generatingNFA.root();
182
183             for (unsigned i = 0; i < activeStack.size() - 1; ++i) {
184                 const Term& term = activeStack[i].iterator->key;
185                 prefixEnd = term.generateGraph(generatingNFA, prefixEnd, activeStack[i].iterator->value->finalActions);
186             }
187
188             for (const auto& edge : activeSubtree.vertex->edges) {
189                 if (!edge.value->inVariableLengthPrefix) {
190                     const Term& term = edge.key;
191                     unsigned newSubtreeStart = term.generateGraph(generatingNFA, prefixEnd, edge.value->finalActions);
192                     generateNFAForSubtree(generatingNFA, newSubtreeStart, *edge.value);
193                 }
194             }
195         }
196
197         // We have processed all the subtrees of this level, pop the stack and move on to the next sibling.
198         activeStack.removeLast();
199         if (activeStack.isEmpty())
200             break;
201         ++activeStack.last().iterator;
202     }
203
204     return nfas;
205 }
206
207 } // namespace ContentExtensions
208 } // namespace WebCore
209
210 #endif // ENABLE(CONTENT_EXTENSIONS)