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)