| /* |
| * Copyright (C) 2015 Apple Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' |
| * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, |
| * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS |
| * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
| * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
| * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
| * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
| * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF |
| * THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "config.h" |
| #include "CombinedURLFilters.h" |
| |
| #if ENABLE(CONTENT_EXTENSIONS) |
| |
| #include "HashableActionList.h" |
| #include "Term.h" |
| #include <wtf/DataLog.h> |
| #include <wtf/Vector.h> |
| #include <wtf/text/CString.h> |
| |
| namespace WebCore { |
| |
| namespace ContentExtensions { |
| |
| struct PrefixTreeEdge { |
| const Term* term; |
| std::unique_ptr<PrefixTreeVertex> child; |
| }; |
| |
| typedef Vector<PrefixTreeEdge, 0, WTF::CrashOnOverflow, 1> PrefixTreeEdges; |
| |
| struct PrefixTreeVertex { |
| PrefixTreeEdges edges; |
| }; |
| |
| struct ReverseSuffixTreeVertex; |
| struct ReverseSuffixTreeEdge { |
| const Term* term; |
| std::unique_ptr<ReverseSuffixTreeVertex> child; |
| }; |
| typedef Vector<ReverseSuffixTreeEdge, 0, WTF::CrashOnOverflow, 1> ReverseSuffixTreeEdges; |
| |
| struct ReverseSuffixTreeVertex { |
| ReverseSuffixTreeEdges edges; |
| uint32_t nodeId; |
| }; |
| typedef HashMap<HashableActionList, ReverseSuffixTreeVertex, HashableActionListHash, HashableActionListHashTraits> ReverseSuffixTreeRoots; |
| |
| #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING |
| static size_t recursiveMemoryUsed(const PrefixTreeVertex& vertex) |
| { |
| size_t size = sizeof(PrefixTreeVertex) |
| + vertex.edges.capacity() * sizeof(PrefixTreeEdge); |
| for (const auto& edge : vertex.edges) { |
| ASSERT(edge.child); |
| size += recursiveMemoryUsed(*edge.child.get()); |
| } |
| return size; |
| } |
| |
| size_t CombinedURLFilters::memoryUsed() const |
| { |
| ASSERT(m_prefixTreeRoot); |
| |
| size_t actionsSize = 0; |
| for (const auto& slot : m_actions) |
| actionsSize += slot.value.capacity() * sizeof(uint64_t); |
| |
| return sizeof(CombinedURLFilters) |
| + m_alphabet.memoryUsed() |
| + recursiveMemoryUsed(*m_prefixTreeRoot.get()) |
| + sizeof(HashMap<PrefixTreeVertex*, ActionList>) |
| + m_actions.capacity() * (sizeof(PrefixTreeVertex*) + sizeof(ActionList)) |
| + actionsSize; |
| } |
| #endif |
| |
| #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING |
| static String prefixTreeVertexToString(const PrefixTreeVertex& vertex, const HashMap<const PrefixTreeVertex*, ActionList>& actions, unsigned depth) |
| { |
| StringBuilder builder; |
| while (depth--) |
| builder.appendLiteral(" "); |
| builder.appendLiteral("vertex actions: "); |
| |
| auto actionsSlot = actions.find(&vertex); |
| if (actionsSlot != actions.end()) { |
| for (uint64_t action : actionsSlot->value) { |
| builder.appendNumber(action); |
| builder.append(','); |
| } |
| } |
| builder.append('\n'); |
| return builder.toString(); |
| } |
| |
| static void recursivePrint(const PrefixTreeVertex& vertex, const HashMap<const PrefixTreeVertex*, ActionList>& actions, unsigned depth) |
| { |
| dataLogF("%s", prefixTreeVertexToString(vertex, actions, depth).utf8().data()); |
| for (const auto& edge : vertex.edges) { |
| StringBuilder builder; |
| for (unsigned i = 0; i < depth * 2; ++i) |
| builder.append(' '); |
| builder.appendLiteral("vertex edge: "); |
| builder.append(edge.term->toString()); |
| builder.append('\n'); |
| dataLogF("%s", builder.toString().utf8().data()); |
| ASSERT(edge.child); |
| recursivePrint(*edge.child.get(), actions, depth + 1); |
| } |
| } |
| |
| void CombinedURLFilters::print() const |
| { |
| recursivePrint(*m_prefixTreeRoot.get(), m_actions, 0); |
| } |
| #endif |
| |
| CombinedURLFilters::CombinedURLFilters() |
| : m_prefixTreeRoot(std::make_unique<PrefixTreeVertex>()) |
| { |
| } |
| |
| CombinedURLFilters::~CombinedURLFilters() = default; |
| |
| bool CombinedURLFilters::isEmpty() const |
| { |
| return m_prefixTreeRoot->edges.isEmpty(); |
| } |
| |
| void CombinedURLFilters::addDomain(uint64_t actionId, const String& domain) |
| { |
| unsigned domainLength = domain.length(); |
| if (domainLength && domain[0] == '*') { |
| // If domain starts with a '*' then it means match domain and its subdomains, like (^|.)domain$ |
| // This way a domain of "*webkit.org" will match "bugs.webkit.org" and "webkit.org". |
| Vector<Term> prependDot; |
| Vector<Term> prependBeginningOfLine; |
| prependDot.reserveInitialCapacity(domainLength + 2); |
| prependBeginningOfLine.reserveInitialCapacity(domainLength); // This is just no .* at the beginning. |
| |
| Term canonicalDotStar(Term::UniversalTransition); |
| canonicalDotStar.quantify(AtomQuantifier::ZeroOrMore); |
| prependDot.uncheckedAppend(canonicalDotStar); |
| prependDot.uncheckedAppend(Term('.', true)); |
| |
| for (unsigned i = 1; i < domainLength; i++) { |
| ASSERT(isASCII(domain[i])); |
| ASSERT(!isASCIIUpper(domain[i])); |
| prependDot.uncheckedAppend(Term(domain[i], true)); |
| prependBeginningOfLine.uncheckedAppend(Term(domain[i], true)); |
| } |
| prependDot.uncheckedAppend(Term::EndOfLineAssertionTerm); |
| prependBeginningOfLine.uncheckedAppend(Term::EndOfLineAssertionTerm); |
| |
| addPattern(actionId, prependDot); |
| addPattern(actionId, prependBeginningOfLine); |
| } else { |
| // This is like adding ^domain$, but interpreting domain as a series of characters, not a regular expression. |
| // "webkit.org" will match "webkit.org" but not "bugs.webkit.org". |
| Vector<Term> prependBeginningOfLine; |
| prependBeginningOfLine.reserveInitialCapacity(domainLength + 1); // This is just no .* at the beginning. |
| for (unsigned i = 0; i < domainLength; i++) { |
| ASSERT(isASCII(domain[i])); |
| ASSERT(!isASCIIUpper(domain[i])); |
| prependBeginningOfLine.uncheckedAppend(Term(domain[i], true)); |
| } |
| prependBeginningOfLine.uncheckedAppend(Term::EndOfLineAssertionTerm); |
| addPattern(actionId, prependBeginningOfLine); |
| } |
| } |
| |
| void CombinedURLFilters::addPattern(uint64_t actionId, const Vector<Term>& pattern) |
| { |
| ASSERT_WITH_MESSAGE(!pattern.isEmpty(), "The parser should have excluded empty patterns before reaching CombinedURLFilters."); |
| |
| if (pattern.isEmpty()) |
| return; |
| |
| // Extend the prefix tree with the new pattern. |
| PrefixTreeVertex* lastPrefixTree = m_prefixTreeRoot.get(); |
| |
| for (const Term& term : pattern) { |
| size_t nextEntryIndex = WTF::notFound; |
| for (size_t i = 0; i < lastPrefixTree->edges.size(); ++i) { |
| if (*lastPrefixTree->edges[i].term == term) { |
| nextEntryIndex = i; |
| break; |
| } |
| } |
| if (nextEntryIndex != WTF::notFound) |
| lastPrefixTree = lastPrefixTree->edges[nextEntryIndex].child.get(); |
| else { |
| lastPrefixTree->edges.append(PrefixTreeEdge({m_alphabet.interned(term), std::make_unique<PrefixTreeVertex>()})); |
| lastPrefixTree = lastPrefixTree->edges.last().child.get(); |
| } |
| } |
| |
| auto addResult = m_actions.add(lastPrefixTree, ActionList()); |
| ActionList& actions = addResult.iterator->value; |
| if (actions.find(actionId) == WTF::notFound) |
| actions.append(actionId); |
| } |
| |
| struct ActiveSubtree { |
| ActiveSubtree(PrefixTreeVertex& vertex, ImmutableCharNFANodeBuilder&& nfaNode, unsigned edgeIndex) |
| : vertex(vertex) |
| , nfaNode(WTFMove(nfaNode)) |
| , edgeIndex(edgeIndex) |
| { |
| } |
| PrefixTreeVertex& vertex; |
| ImmutableCharNFANodeBuilder nfaNode; |
| unsigned edgeIndex; |
| }; |
| |
| static void generateInfixUnsuitableForReverseSuffixTree(NFA& nfa, Vector<ActiveSubtree>& stack, const HashMap<const PrefixTreeVertex*, ActionList>& actions) |
| { |
| // To avoid conflicts, we use the reverse suffix tree for subtrees that do not merge |
| // in the prefix tree. |
| // |
| // We only unify the suffixes to the actions on the leaf. |
| // If there are actions inside the tree, we generate the part of the subtree up to the action. |
| // |
| // If we accidentally insert a node with action inside the reverse-suffix-tree, we would create |
| // new actions on unrelated pattern when unifying their suffixes. |
| for (unsigned i = stack.size() - 1; i--;) { |
| ActiveSubtree& activeSubtree = stack[i]; |
| if (activeSubtree.nfaNode.isValid()) |
| return; |
| |
| RELEASE_ASSERT_WITH_MESSAGE(i > 0, "The bottom of the stack must be the root of our fixed-length subtree. It should have it the isValid() case above."); |
| |
| auto actionsIterator = actions.find(&activeSubtree.vertex); |
| bool hasActionInsideTree = actionsIterator != actions.end(); |
| |
| // Stricto sensu, we should count the number of exit edges with fixed length. |
| // That is costly and unlikely to matter in practice. |
| bool hasSingleOutcome = activeSubtree.vertex.edges.size() == 1; |
| |
| if (hasActionInsideTree || !hasSingleOutcome) { |
| // Go back to the end of the subtree that has already been generated. |
| // From there, generate everything up to the vertex we found. |
| unsigned end = i; |
| unsigned beginning = end; |
| |
| ActiveSubtree* sourceActiveSubtree = nullptr; |
| while (beginning--) { |
| ActiveSubtree& activeSubtree = stack[beginning]; |
| if (activeSubtree.nfaNode.isValid()) { |
| sourceActiveSubtree = &activeSubtree; |
| break; |
| } |
| } |
| ASSERT_WITH_MESSAGE(sourceActiveSubtree, "The root should always have a valid generator."); |
| |
| for (unsigned stackIndex = beginning + 1; stackIndex <= end; ++stackIndex) { |
| ImmutableCharNFANodeBuilder& sourceNode = sourceActiveSubtree->nfaNode; |
| ASSERT(sourceNode.isValid()); |
| auto& edge = sourceActiveSubtree->vertex.edges[sourceActiveSubtree->edgeIndex]; |
| |
| ActiveSubtree& destinationActiveSubtree = stack[stackIndex]; |
| destinationActiveSubtree.nfaNode = edge.term->generateGraph(nfa, sourceNode, actions.get(&destinationActiveSubtree.vertex)); |
| |
| sourceActiveSubtree = &destinationActiveSubtree; |
| } |
| |
| return; |
| } |
| } |
| } |
| |
| static void generateSuffixWithReverseSuffixTree(NFA& nfa, Vector<ActiveSubtree>& stack, const HashMap<const PrefixTreeVertex*, ActionList>& actions, ReverseSuffixTreeRoots& reverseSuffixTreeRoots) |
| { |
| ActiveSubtree& leafSubtree = stack.last(); |
| ASSERT_WITH_MESSAGE(!leafSubtree.nfaNode.isValid(), "The leaf should never be generated by the code above, it should always be inserted into the prefix tree."); |
| |
| ActionList actionList = actions.get(&leafSubtree.vertex); |
| ASSERT_WITH_MESSAGE(!actionList.isEmpty(), "Our prefix tree should always have actions on the leaves by construction."); |
| |
| HashableActionList hashableActionList(actionList); |
| auto rootAddResult = reverseSuffixTreeRoots.add(hashableActionList, ReverseSuffixTreeVertex()); |
| if (rootAddResult.isNewEntry) { |
| ImmutableCharNFANodeBuilder newNode(nfa); |
| newNode.setActions(actionList.begin(), actionList.end()); |
| rootAddResult.iterator->value.nodeId = newNode.nodeId(); |
| } |
| |
| ReverseSuffixTreeVertex* activeReverseSuffixTreeVertex = &rootAddResult.iterator->value; |
| uint32_t destinationNodeId = rootAddResult.iterator->value.nodeId; |
| |
| unsigned stackPosition = stack.size() - 2; |
| while (true) { |
| ActiveSubtree& source = stack[stackPosition]; |
| auto& edge = source.vertex.edges[source.edgeIndex]; |
| |
| // This is the end condition: when we meet a node that has already been generated, |
| // we just need to connect our backward tree to the forward tree. |
| // |
| // We *must not* add this last node to the reverse-suffix tree. That node can have |
| // transitions back to earlier part of the prefix tree. If the prefix tree "caches" |
| // such node, it would create new transitions that did not exist in the source language. |
| if (source.nfaNode.isValid()) { |
| stack.shrink(stackPosition + 1); |
| edge.term->generateGraph(nfa, source.nfaNode, destinationNodeId); |
| return; |
| } |
| --stackPosition; |
| |
| ASSERT_WITH_MESSAGE(!actions.contains(&source.vertex), "Any node with final actions should have been created before hitting the reverse suffix-tree."); |
| |
| ReverseSuffixTreeEdge* existingEdge = nullptr; |
| for (ReverseSuffixTreeEdge& potentialExistingEdge : activeReverseSuffixTreeVertex->edges) { |
| if (edge.term == potentialExistingEdge.term) { |
| existingEdge = &potentialExistingEdge; |
| break; |
| } |
| } |
| |
| if (existingEdge) |
| activeReverseSuffixTreeVertex = existingEdge->child.get(); |
| else { |
| ImmutableCharNFANodeBuilder newNode(nfa); |
| edge.term->generateGraph(nfa, newNode, destinationNodeId); |
| std::unique_ptr<ReverseSuffixTreeVertex> newVertex(new ReverseSuffixTreeVertex()); |
| newVertex->nodeId = newNode.nodeId(); |
| |
| ReverseSuffixTreeVertex* newVertexAddress = newVertex.get(); |
| activeReverseSuffixTreeVertex->edges.append(ReverseSuffixTreeEdge({ edge.term, WTFMove(newVertex) })); |
| activeReverseSuffixTreeVertex = newVertexAddress; |
| } |
| destinationNodeId = activeReverseSuffixTreeVertex->nodeId; |
| |
| ASSERT(source.vertex.edges.size() == 1); |
| source.vertex.edges.clear(); |
| } |
| |
| RELEASE_ASSERT_NOT_REACHED(); |
| } |
| |
| static void clearReverseSuffixTree(ReverseSuffixTreeRoots& reverseSuffixTreeRoots) |
| { |
| // We cannot rely on the destructor being called in order from top to bottom as we may overflow |
| // the stack. Instead, we go depth first in the reverse-suffix-tree. |
| |
| for (auto& slot : reverseSuffixTreeRoots) { |
| Vector<ReverseSuffixTreeVertex*, 128> stack; |
| stack.append(&slot.value); |
| |
| while (true) { |
| ReverseSuffixTreeVertex* top = stack.last(); |
| if (top->edges.isEmpty()) { |
| stack.removeLast(); |
| if (stack.isEmpty()) |
| break; |
| stack.last()->edges.removeLast(); |
| } else |
| stack.append(top->edges.last().child.get()); |
| } |
| } |
| reverseSuffixTreeRoots.clear(); |
| } |
| |
| static void generateNFAForSubtree(NFA& nfa, ImmutableCharNFANodeBuilder&& subtreeRoot, PrefixTreeVertex& root, const HashMap<const PrefixTreeVertex*, ActionList>& actions, size_t maxNFASize) |
| { |
| // This recurses the subtree of the prefix tree. |
| // For each edge that has fixed length (no quantifiers like ?, *, or +) it generates the nfa graph, |
| // recurses into children, and deletes any processed leaf nodes. |
| |
| ReverseSuffixTreeRoots reverseSuffixTreeRoots; |
| Vector<ActiveSubtree> stack; |
| if (!root.edges.isEmpty()) |
| stack.append(ActiveSubtree(root, WTFMove(subtreeRoot), 0)); |
| |
| bool nfaTooBig = false; |
| |
| // Generate graphs for each subtree that does not contain any quantifiers. |
| while (!stack.isEmpty()) { |
| PrefixTreeVertex& vertex = stack.last().vertex; |
| const unsigned edgeIndex = stack.last().edgeIndex; |
| |
| if (edgeIndex < vertex.edges.size()) { |
| auto& edge = vertex.edges[edgeIndex]; |
| |
| // Clean up any processed leaves and return early if we are past the maxNFASize. |
| if (nfaTooBig) { |
| stack.last().edgeIndex = stack.last().vertex.edges.size(); |
| continue; |
| } |
| |
| // Quantified edges in the subtree will be a part of another NFA. |
| if (!edge.term->hasFixedLength()) { |
| stack.last().edgeIndex++; |
| continue; |
| } |
| |
| ASSERT(edge.child.get()); |
| ImmutableCharNFANodeBuilder emptyBuilder; |
| stack.append(ActiveSubtree(*edge.child.get(), WTFMove(emptyBuilder), 0)); |
| } else { |
| bool isLeaf = vertex.edges.isEmpty(); |
| |
| ASSERT(edgeIndex == vertex.edges.size()); |
| vertex.edges.removeAllMatching([](PrefixTreeEdge& edge) |
| { |
| return !edge.term; |
| }); |
| |
| if (isLeaf) { |
| generateInfixUnsuitableForReverseSuffixTree(nfa, stack, actions); |
| generateSuffixWithReverseSuffixTree(nfa, stack, actions, reverseSuffixTreeRoots); |
| |
| // Only stop generating an NFA at a leaf to ensure we have a correct NFA. We could go slightly over the maxNFASize. |
| if (nfa.nodes.size() > maxNFASize) |
| nfaTooBig = true; |
| } else |
| stack.removeLast(); |
| |
| if (!stack.isEmpty()) { |
| auto& activeSubtree = stack.last(); |
| auto& edge = activeSubtree.vertex.edges[stack.last().edgeIndex]; |
| if (edge.child->edges.isEmpty()) |
| edge.term = nullptr; // Mark this leaf for deleting. |
| activeSubtree.edgeIndex++; |
| } |
| } |
| } |
| clearReverseSuffixTree(reverseSuffixTreeRoots); |
| } |
| |
| void CombinedURLFilters::processNFAs(size_t maxNFASize, const WTF::Function<void(NFA&&)>& handler) |
| { |
| #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING |
| print(); |
| #endif |
| while (true) { |
| // Traverse out to a leaf. |
| Vector<PrefixTreeVertex*, 128> stack; |
| PrefixTreeVertex* vertex = m_prefixTreeRoot.get(); |
| while (true) { |
| ASSERT(vertex); |
| stack.append(vertex); |
| if (vertex->edges.isEmpty()) |
| break; |
| vertex = vertex->edges.last().child.get(); |
| } |
| if (stack.size() == 1) |
| break; // We're done once we have processed and removed all the edges in the prefix tree. |
| |
| // Find the prefix root for this NFA. This is the vertex after the last term with a quantifier if there is one, |
| // or the root if there are no quantifiers left. |
| while (stack.size() > 1) { |
| if (!stack[stack.size() - 2]->edges.last().term->hasFixedLength()) |
| break; |
| stack.removeLast(); |
| } |
| ASSERT_WITH_MESSAGE(!stack.isEmpty(), "At least the root should be in the stack"); |
| |
| // Make an NFA with the subtrees for whom this is also the last quantifier (or who also have no quantifier). |
| NFA nfa; |
| { |
| // Put the prefix into the NFA. |
| ImmutableCharNFANodeBuilder lastNode(nfa); |
| for (unsigned i = 0; i < stack.size() - 1; ++i) { |
| const PrefixTreeEdge& edge = stack[i]->edges.last(); |
| ImmutableCharNFANodeBuilder newNode = edge.term->generateGraph(nfa, lastNode, m_actions.get(edge.child.get())); |
| lastNode = WTFMove(newNode); |
| } |
| |
| // Put the non-quantified vertices in the subtree into the NFA and delete them. |
| ASSERT(stack.last()); |
| generateNFAForSubtree(nfa, WTFMove(lastNode), *stack.last(), m_actions, maxNFASize); |
| } |
| nfa.finalize(); |
| |
| handler(WTFMove(nfa)); |
| |
| // Clean up any processed leaf nodes. |
| while (true) { |
| if (stack.size() > 1) { |
| if (stack[stack.size() - 1]->edges.isEmpty()) { |
| stack[stack.size() - 2]->edges.removeLast(); |
| stack.removeLast(); |
| } else |
| break; // Vertex is not a leaf. |
| } else |
| break; // Leave the empty root. |
| } |
| } |
| } |
| |
| } // namespace ContentExtensions |
| } // namespace WebCore |
| |
| #endif // ENABLE(CONTENT_EXTENSIONS) |