[Content Extensions] Add a way to match a domain but not subdomains
[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/DataLog.h>
33 #include <wtf/Vector.h>
34 #include <wtf/text/CString.h>
35
36 namespace WebCore {
37
38 namespace ContentExtensions {
39
40 struct PrefixTreeEdge {
41     Term term;
42     std::unique_ptr<PrefixTreeVertex> child;
43 };
44     
45 typedef Vector<PrefixTreeEdge, 0, WTF::CrashOnOverflow, 1> PrefixTreeEdges;
46
47 struct PrefixTreeVertex {
48     PrefixTreeEdges edges;
49     ActionList finalActions;
50 };
51
52 #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
53 static size_t recursiveMemoryUsed(const PrefixTreeVertex& vertex)
54 {
55     size_t size = sizeof(PrefixTreeVertex)
56         + vertex.edges.capacity() * sizeof(PrefixTreeEdge)
57         + vertex.finalActions.capacity() * sizeof(uint64_t);
58     for (const auto& edge : vertex.edges) {
59         ASSERT(edge.child);
60         size += recursiveMemoryUsed(*edge.child.get());
61     }
62     return size;
63 }
64
65 size_t CombinedURLFilters::memoryUsed() const
66 {
67     ASSERT(m_prefixTreeRoot);
68     return recursiveMemoryUsed(*m_prefixTreeRoot.get());
69 }
70 #endif
71     
72 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
73 static String prefixTreeVertexToString(const PrefixTreeVertex& vertex, unsigned depth)
74 {
75     StringBuilder builder;
76     while (depth--)
77         builder.append("  ");
78     builder.append("vertex actions: ");
79     for (auto action : vertex.finalActions) {
80         builder.appendNumber(action);
81         builder.append(',');
82     }
83     builder.append('\n');
84     return builder.toString();
85 }
86
87 static void recursivePrint(const PrefixTreeVertex& vertex, unsigned depth)
88 {
89     dataLogF("%s", prefixTreeVertexToString(vertex, depth).utf8().data());
90     for (const auto& edge : vertex.edges) {
91         StringBuilder builder;
92         for (unsigned i = 0; i < depth * 2; ++i)
93             builder.append(' ');
94         builder.append("vertex edge: ");
95         builder.append(edge.term.toString());
96         builder.append('\n');
97         dataLogF("%s", builder.toString().utf8().data());
98         ASSERT(edge.child);
99         recursivePrint(*edge.child.get(), depth + 1);
100     }
101 }
102
103 void CombinedURLFilters::print() const
104 {
105     recursivePrint(*m_prefixTreeRoot.get(), 0);
106 }
107 #endif
108
109 CombinedURLFilters::CombinedURLFilters()
110     : m_prefixTreeRoot(std::make_unique<PrefixTreeVertex>())
111 {
112 }
113
114 CombinedURLFilters::~CombinedURLFilters()
115 {
116 }
117
118 bool CombinedURLFilters::isEmpty() const
119 {
120     return m_prefixTreeRoot->edges.isEmpty();
121 }
122
123 void CombinedURLFilters::addDomain(uint64_t actionId, const String& domain)
124 {
125     unsigned domainLength = domain.length();
126     if (domainLength && domain[0] == '*') {
127         // If domain starts with a '*' then it means match domain and its subdomains, like (^|.)domain$
128         // This way a domain of "*webkit.org" will match "bugs.webkit.org" and "webkit.org".
129         Vector<Term> prependDot;
130         Vector<Term> prependBeginningOfLine;
131         prependDot.reserveInitialCapacity(domainLength + 2);
132         prependBeginningOfLine.reserveInitialCapacity(domainLength); // This is just no .* at the beginning.
133         
134         Term canonicalDotStar(Term::UniversalTransition);
135         canonicalDotStar.quantify(AtomQuantifier::ZeroOrMore);
136         prependDot.uncheckedAppend(canonicalDotStar);
137         prependDot.uncheckedAppend(Term('.', true));
138         
139         for (unsigned i = 1; i < domainLength; i++) {
140             ASSERT(isASCII(domain[i]));
141             ASSERT(!isASCIIUpper(domain[i]));
142             prependDot.uncheckedAppend(Term(domain[i], true));
143             prependBeginningOfLine.uncheckedAppend(Term(domain[i], true));
144         }
145         prependDot.uncheckedAppend(Term::EndOfLineAssertionTerm);
146         prependBeginningOfLine.uncheckedAppend(Term::EndOfLineAssertionTerm);
147         
148         addPattern(actionId, prependDot);
149         addPattern(actionId, prependBeginningOfLine);
150     } else {
151         // This is like adding ^domain$, but interpreting domain as a series of characters, not a regular expression.
152         // "webkit.org" will match "webkit.org" but not "bugs.webkit.org".
153         Vector<Term> prependBeginningOfLine;
154         prependBeginningOfLine.reserveInitialCapacity(domainLength + 1); // This is just no .* at the beginning.
155         for (unsigned i = 0; i < domainLength; i++) {
156             ASSERT(isASCII(domain[i]));
157             ASSERT(!isASCIIUpper(domain[i]));
158             prependBeginningOfLine.uncheckedAppend(Term(domain[i], true));
159         }
160         prependBeginningOfLine.uncheckedAppend(Term::EndOfLineAssertionTerm);
161         addPattern(actionId, prependBeginningOfLine);
162     }
163 }
164
165 void CombinedURLFilters::addPattern(uint64_t actionId, const Vector<Term>& pattern)
166 {
167     ASSERT_WITH_MESSAGE(!pattern.isEmpty(), "The parser should have excluded empty patterns before reaching CombinedURLFilters.");
168
169     if (pattern.isEmpty())
170         return;
171
172     // Extend the prefix tree with the new pattern.
173     PrefixTreeVertex* lastPrefixTree = m_prefixTreeRoot.get();
174
175     for (const Term& term : pattern) {
176         size_t nextEntryIndex = WTF::notFound;
177         for (size_t i = 0; i < lastPrefixTree->edges.size(); ++i) {
178             if (lastPrefixTree->edges[i].term == term) {
179                 nextEntryIndex = i;
180                 break;
181             }
182         }
183         if (nextEntryIndex != WTF::notFound)
184             lastPrefixTree = lastPrefixTree->edges[nextEntryIndex].child.get();
185         else {
186             lastPrefixTree->edges.append(PrefixTreeEdge({term, std::make_unique<PrefixTreeVertex>()}));
187             lastPrefixTree = lastPrefixTree->edges.last().child.get();
188         }
189     }
190
191     ActionList& actions = lastPrefixTree->finalActions;
192     if (actions.find(actionId) == WTF::notFound)
193         actions.append(actionId);
194 }
195
196 static void generateNFAForSubtree(NFA& nfa, unsigned nfaRootId, PrefixTreeVertex& root, size_t maxNFASize)
197 {
198     // This recurses the subtree of the prefix tree.
199     // For each edge that has fixed length (no quantifiers like ?, *, or +) it generates the nfa graph,
200     // recurses into children, and deletes any processed leaf nodes.
201     struct ActiveSubtree {
202         ActiveSubtree(PrefixTreeVertex& vertex, unsigned nfaNodeId, unsigned edgeIndex)
203             : vertex(vertex)
204             , nfaNodeId(nfaNodeId)
205             , edgeIndex(edgeIndex)
206         {
207         }
208         PrefixTreeVertex& vertex;
209         unsigned nfaNodeId;
210         unsigned edgeIndex;
211     };
212     Vector<ActiveSubtree> stack;
213     if (!root.edges.isEmpty())
214         stack.append(ActiveSubtree(root, nfaRootId, 0));
215     bool nfaTooBig = false;
216     
217     // Generate graphs for each subtree that does not contain any quantifiers.
218     while (!stack.isEmpty()) {
219         PrefixTreeVertex& vertex = stack.last().vertex;
220         const unsigned edgeIndex = stack.last().edgeIndex;
221         
222         // Only stop generating an NFA at a leaf to ensure we have a correct NFA. We could go slightly over the maxNFASize.
223         if (vertex.edges.isEmpty() && nfa.graphSize() > maxNFASize)
224             nfaTooBig = true;
225         
226         if (edgeIndex < vertex.edges.size()) {
227             auto& edge = vertex.edges[edgeIndex];
228             
229             // Clean up any processed leaves and return early if we are past the maxNFASize.
230             if (nfaTooBig) {
231                 stack.last().edgeIndex = stack.last().vertex.edges.size();
232                 continue;
233             }
234             
235             // Quantified edges in the subtree will be a part of another NFA.
236             if (!edge.term.hasFixedLength()) {
237                 stack.last().edgeIndex++;
238                 continue;
239             }
240             
241             unsigned subtreeRootId = edge.term.generateGraph(nfa, stack.last().nfaNodeId, edge.child->finalActions);
242             ASSERT(edge.child.get());
243             stack.append(ActiveSubtree(*edge.child.get(), subtreeRootId, 0));
244         } else {
245             ASSERT(edgeIndex == vertex.edges.size());
246             vertex.edges.removeAllMatching([](PrefixTreeEdge& edge)
247             {
248                 return edge.term.isDeletedValue();
249             });
250             stack.removeLast();
251             if (!stack.isEmpty()) {
252                 auto& activeSubtree = stack.last();
253                 auto& edge = activeSubtree.vertex.edges[stack.last().edgeIndex];
254                 if (edge.child->edges.isEmpty())
255                     edge.term = Term(Term::DeletedValue); // Mark this leaf for deleting.
256                 activeSubtree.edgeIndex++;
257             }
258         }
259     }
260 }
261
262 void CombinedURLFilters::processNFAs(size_t maxNFASize, std::function<void(NFA&&)> handler)
263 {
264 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
265     print();
266 #endif
267     while (true) {
268         // Traverse out to a leaf.
269         Vector<PrefixTreeVertex*, 128> stack;
270         PrefixTreeVertex* vertex = m_prefixTreeRoot.get();
271         while (true) {
272             ASSERT(vertex);
273             stack.append(vertex);
274             if (vertex->edges.isEmpty())
275                 break;
276             vertex = vertex->edges.last().child.get();
277         }
278         if (stack.size() == 1)
279             break; // We're done once we have processed and removed all the edges in the prefix tree.
280         
281         // Find the prefix root for this NFA. This is the vertex after the last term with a quantifier if there is one,
282         // or the root if there are no quantifiers left.
283         while (stack.size() > 1) {
284             if (!stack[stack.size() - 2]->edges.last().term.hasFixedLength())
285                 break;
286             stack.removeLast();
287         }
288         ASSERT_WITH_MESSAGE(!stack.isEmpty(), "At least the root should be in the stack");
289         
290         // Make an NFA with the subtrees for whom this is also the last quantifier (or who also have no quantifier).
291         NFA nfa;
292         // Put the prefix into the NFA.
293         unsigned prefixEnd = nfa.root();
294         for (unsigned i = 0; i < stack.size() - 1; ++i) {
295             ASSERT(!stack[i]->edges.isEmpty());
296             const PrefixTreeEdge& edge = stack[i]->edges.last();
297             prefixEnd = edge.term.generateGraph(nfa, prefixEnd, edge.child->finalActions);
298         }
299         // Put the non-quantified vertices in the subtree into the NFA and delete them.
300         ASSERT(stack.last());
301         generateNFAForSubtree(nfa, prefixEnd, *stack.last(), maxNFASize);
302         
303         handler(WTF::move(nfa));
304         
305         // Clean up any processed leaf nodes.
306         while (true) {
307             if (stack.size() > 1) {
308                 if (stack[stack.size() - 1]->edges.isEmpty()) {
309                     stack[stack.size() - 2]->edges.removeLast();
310                     stack.removeLast();
311                 } else
312                     break; // Vertex is not a leaf.
313             } else
314                 break; // Leave the empty root.
315         }
316     }
317 }
318
319 } // namespace ContentExtensions
320 } // namespace WebCore
321
322 #endif // ENABLE(CONTENT_EXTENSIONS)