Diff
Modified: trunk/Source/WTF/ChangeLog (186909 => 186910)
--- trunk/Source/WTF/ChangeLog 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WTF/ChangeLog 2015-07-16 21:51:08 UTC (rev 186910)
@@ -1,3 +1,18 @@
+2015-07-16 Benjamin Poulain <[email protected]>
+
+ [Content extensions] Combine suffixes when generating NFAs
+ https://bugs.webkit.org/show_bug.cgi?id=146961
+
+ Reviewed by Alex Christensen.
+
+ * wtf/Vector.h:
+ (WTF::minCapacity>::Vector):
+ (WTF::=):
+ Copying a vector with a different inline capacity was broken due to
+ the addition of MinimumCapacity.
+
+ This feature was needed by this patch so I fixed WTF.
+
2015-07-15 Anders Carlsson <[email protected]>
Make _javascript_Core SPI headers used by WebCore SPI headers self-contained
Modified: trunk/Source/WTF/wtf/Vector.h (186909 => 186910)
--- trunk/Source/WTF/wtf/Vector.h 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WTF/wtf/Vector.h 2015-07-16 21:51:08 UTC (rev 186910)
@@ -638,12 +638,12 @@
}
Vector(const Vector&);
- template<size_t otherCapacity, typename otherOverflowBehaviour>
- explicit Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>&);
+ template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
+ explicit Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
Vector& operator=(const Vector&);
- template<size_t otherCapacity, typename otherOverflowBehaviour>
- Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>&);
+ template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
+ Vector& operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>&);
Vector(Vector&&);
Vector& operator=(Vector&&);
@@ -819,8 +819,8 @@
}
template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
-template<size_t otherCapacity, typename otherOverflowBehaviour>
-Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
+template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
+Vector<T, inlineCapacity, OverflowHandler, minCapacity>::Vector(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
: Base(other.capacity(), other.size())
{
asanSetInitialBufferSizeTo(other.size());
@@ -855,8 +855,8 @@
inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
-template<size_t otherCapacity, typename otherOverflowBehaviour>
-Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour>& other)
+template<size_t otherCapacity, typename otherOverflowBehaviour, size_t otherMinimumCapacity>
+Vector<T, inlineCapacity, OverflowHandler, minCapacity>& Vector<T, inlineCapacity, OverflowHandler, minCapacity>::operator=(const Vector<T, otherCapacity, otherOverflowBehaviour, otherMinimumCapacity>& other)
{
// If the inline capacities match, we should call the more specific
// template. If the inline capacities don't match, the two objects
Modified: trunk/Source/WebCore/ChangeLog (186909 => 186910)
--- trunk/Source/WebCore/ChangeLog 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/ChangeLog 2015-07-16 21:51:08 UTC (rev 186910)
@@ -1,3 +1,104 @@
+2015-07-16 Benjamin Poulain <[email protected]>
+
+ [Content extensions] Combine suffixes when generating NFAs
+ https://bugs.webkit.org/show_bug.cgi?id=146961
+
+ Reviewed by Alex Christensen.
+
+ In this patch, I add a mechanism very similar to the prefix tree
+ but for the suffix (called a reverse suffix tree here).
+
+ The idea is here is to reuse the existing NFA nodes when generating
+ a chain of suffix Term that were already generated previously.
+ When generating a disjunction ending with the same suffix, we now
+ have the same trailing NFA nodes for both sides of the disjunction.
+
+ Mixing the prefix and suffix generation can be tricky, we do not want
+ transitions from a pattern to creep into the suffix of an other.
+
+ To avoid any conflict, the rules here are very simple:
+ -Only use the reverse suffix tree for terms without actions
+ up to a leaf term with actions.
+
+ This rule ensure that no action will accidentally make its way
+ to an other rule by resuing a vertex of the reverse suffix tree.
+
+ -Only use the reverse suffix tree for chains of terms in which
+ each term only has zero or one following term.
+
+ With this condition, when taking any vertex of the reverse suffix
+ tree, there is only one edge that move out of that vertex when reading
+ from left to right.
+ For any vertex, there is only one possible string generated
+ left-to-right, a single suffix.
+
+ This is overly restrictive but it is fast, easier to verify, and it works
+ well in practice.
+ For all the more complicated cases, we can count on the Minimizer to
+ find a better solution.
+
+
+ With all the simple suffixes merged, our NFAs are smaller, which
+ let us combine more patterns.
+ The DFAs are also smaller and faster to produce since their size
+ is relative to the NFA sizes.
+
+ Overall, I get the following gains:
+ -Chris's test case:
+ compile time -40%.
+ bytecode size -14%.
+ -Armand's test case:
+ compile time -53%.
+ bytecode size -13%.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * contentextensions/CombinedURLFilters.cpp:
+ (WebCore::ContentExtensions::ActiveSubtree::ActiveSubtree):
+ (WebCore::ContentExtensions::generateInfixUnsuitableForReverseSuffixTree):
+ (WebCore::ContentExtensions::generateSuffixWithReverseSuffixTree):
+ (WebCore::ContentExtensions::clearReverseSuffixTree):
+ (WebCore::ContentExtensions::generateNFAForSubtree):
+ * contentextensions/DFA.cpp:
+ (WebCore::ContentExtensions::DFA::debugPrintDot):
+ Forgot to close a tag, dot was not happy.
+
+ * contentextensions/HashableActionList.h: Added.
+ (WebCore::ContentExtensions::HashableActionList::HashableActionList):
+ (WebCore::ContentExtensions::HashableActionList::isEmptyValue):
+ (WebCore::ContentExtensions::HashableActionList::isDeletedValue):
+ (WebCore::ContentExtensions::HashableActionList::operator==):
+ (WebCore::ContentExtensions::HashableActionList::operator!=):
+ (WebCore::ContentExtensions::HashableActionListHash::hash):
+ (WebCore::ContentExtensions::HashableActionListHash::equal):
+ We need a way to group reverse suffix tree by their terminal actions.
+ This new hash structure lets us find unique vertex for a list of actions
+ in any order.
+
+ * contentextensions/ImmutableNFANodeBuilder.h:
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::isValid):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::nodeId):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::addTransition):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::addEpsilonTransition):
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::ImmutableNFANodeBuilder): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::~ImmutableNFANodeBuilder): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFANodeBuilder::operator=): Deleted.
+ * contentextensions/Term.h:
+ (WebCore::ContentExtensions::Term::generateGraph):
+ (WebCore::ContentExtensions::Term::generateSubgraphForAtom):
+ Node building changes a bit.
+
+ Previously, it was assumed nodes are always built from left to right.
+ Getting the node on the right was done by providing the left node and the term
+ doing the transition.
+
+ Now we have both left to right and right to left generation.
+
+ The right-to-left has a specific property: no edge can be added after
+ it's initial term (rule 2 of our reverse suffix tree). This simplifies
+ things a bit since we can finalize all the nodes in the suffix tree.
+ All we need is to keep their ID to be able to link new nodes
+ to the reverse suffix tree.
+
2015-07-16 Brady Eidson <[email protected]>
Rolling out part of r186895 until rdar://problem/21861167 is resolved.
Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (186909 => 186910)
--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-07-16 21:51:08 UTC (rev 186910)
@@ -1040,6 +1040,7 @@
26E944D91AC4B2DD007B85B5 /* CombinedURLFilters.h in Headers */ = {isa = PBXBuildFile; fileRef = 26E944D51AC4B2DD007B85B5 /* CombinedURLFilters.h */; settings = {ATTRIBUTES = (Private, ); }; };
26E944DD1AC4B4EA007B85B5 /* Term.h in Headers */ = {isa = PBXBuildFile; fileRef = 26E944DC1AC4B4EA007B85B5 /* Term.h */; settings = {ATTRIBUTES = (Private, ); }; };
26E98A10130A9FCA008EB7B2 /* TextCodecASCIIFastPath.h in Headers */ = {isa = PBXBuildFile; fileRef = 26E98A0F130A9FCA008EB7B2 /* TextCodecASCIIFastPath.h */; };
+ 26EA89A71B4F2B75008C5FD2 /* HashableActionList.h in Headers */ = {isa = PBXBuildFile; fileRef = 26EA89A61B4F2B75008C5FD2 /* HashableActionList.h */; };
26F0C8971A2E724B002794F8 /* ContentExtensionParser.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26F0C8951A2E724B002794F8 /* ContentExtensionParser.cpp */; };
26F0C8981A2E724B002794F8 /* ContentExtensionParser.h in Headers */ = {isa = PBXBuildFile; fileRef = 26F0C8961A2E724B002794F8 /* ContentExtensionParser.h */; settings = {ATTRIBUTES = (Private, ); }; };
26F0C89B1A2EC110002794F8 /* ContentExtensionRule.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26F0C8991A2EC110002794F8 /* ContentExtensionRule.cpp */; };
@@ -8200,6 +8201,7 @@
26E944D51AC4B2DD007B85B5 /* CombinedURLFilters.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CombinedURLFilters.h; sourceTree = "<group>"; };
26E944DC1AC4B4EA007B85B5 /* Term.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Term.h; sourceTree = "<group>"; };
26E98A0F130A9FCA008EB7B2 /* TextCodecASCIIFastPath.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TextCodecASCIIFastPath.h; sourceTree = "<group>"; };
+ 26EA89A61B4F2B75008C5FD2 /* HashableActionList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HashableActionList.h; sourceTree = "<group>"; };
26F0C8951A2E724B002794F8 /* ContentExtensionParser.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ContentExtensionParser.cpp; sourceTree = "<group>"; };
26F0C8961A2E724B002794F8 /* ContentExtensionParser.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ContentExtensionParser.h; sourceTree = "<group>"; };
26F0C8991A2EC110002794F8 /* ContentExtensionRule.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ContentExtensionRule.cpp; sourceTree = "<group>"; };
@@ -15736,6 +15738,7 @@
26A517FC1AB92238006335DF /* DFAMinimizer.h */,
26D4E8451B42539D00E033A2 /* DFANode.cpp */,
267725F91A5B3AD9003C24DD /* DFANode.h */,
+ 26EA89A61B4F2B75008C5FD2 /* HashableActionList.h */,
26F756B21B3B66F70005DD79 /* ImmutableNFA.h */,
26F756B41B3B68F20005DD79 /* ImmutableNFANodeBuilder.h */,
26F756AE1B3B65AC0005DD79 /* MutableRange.h */,
@@ -27288,6 +27291,7 @@
0709D78F1AE55554004E42F8 /* WebMediaSessionManager.h in Headers */,
0709D7951AE55A29004E42F8 /* WebMediaSessionManagerClient.h in Headers */,
0709D7931AE5557E004E42F8 /* WebMediaSessionManagerMac.h in Headers */,
+ 26EA89A71B4F2B75008C5FD2 /* HashableActionList.h in Headers */,
E1A3162D134BC32D007C9A4F /* WebNSAttributedStringExtras.h in Headers */,
99CC0B6B18BEA1FF006CEBCC /* WebReplayInputs.h in Headers */,
A502C5DF13049B3500FC7D53 /* WebSafeGCActivityCallbackIOS.h in Headers */,
Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp (186909 => 186910)
--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-07-16 21:51:08 UTC (rev 186910)
@@ -28,6 +28,7 @@
#if ENABLE(CONTENT_EXTENSIONS)
+#include "HashableActionList.h"
#include "Term.h"
#include <wtf/DataLog.h>
#include <wtf/Vector.h>
@@ -48,6 +49,19 @@
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)
{
@@ -206,39 +220,186 @@
actions.append(actionId);
}
-static void generateNFAForSubtree(NFA& nfa, ImmutableCharNFANodeBuilder&& subtreeRoot, PrefixTreeVertex& root, HashMap<const PrefixTreeVertex*, ActionList>& actions, size_t maxNFASize)
+struct ActiveSubtree {
+ ActiveSubtree(PrefixTreeVertex& vertex, ImmutableCharNFANodeBuilder&& nfaNode, unsigned edgeIndex)
+ : vertex(vertex)
+ , nfaNode(WTF::move(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, WTF::move(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.
- struct ActiveSubtree {
- ActiveSubtree(PrefixTreeVertex& vertex, ImmutableCharNFANodeBuilder&& nfaNode, unsigned edgeIndex)
- : vertex(vertex)
- , nfaNode(WTF::move(nfaNode))
- , edgeIndex(edgeIndex)
- {
- }
- PrefixTreeVertex& vertex;
- ImmutableCharNFANodeBuilder nfaNode;
- unsigned edgeIndex;
- };
+
+ ReverseSuffixTreeRoots reverseSuffixTreeRoots;
Vector<ActiveSubtree> stack;
if (!root.edges.isEmpty())
stack.append(ActiveSubtree(root, WTF::move(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;
-
- // Only stop generating an NFA at a leaf to ensure we have a correct NFA. We could go slightly over the maxNFASize.
- if (vertex.edges.isEmpty() && nfa.nodes.size() > maxNFASize)
- nfaTooBig = true;
-
+
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();
@@ -251,17 +412,28 @@
continue;
}
-
- ImmutableCharNFANodeBuilder newNode = edge.term->generateGraph(nfa, stack.last().nfaNode, actions.get(edge.child.get()));
ASSERT(edge.child.get());
- stack.append(ActiveSubtree(*edge.child.get(), WTF::move(newNode), 0));
+ ImmutableCharNFANodeBuilder emptyBuilder;
+ stack.append(ActiveSubtree(*edge.child.get(), WTF::move(emptyBuilder), 0));
} else {
+ bool isLeaf = vertex.edges.isEmpty();
+
ASSERT(edgeIndex == vertex.edges.size());
vertex.edges.removeAllMatching([](PrefixTreeEdge& edge)
{
return !edge.term;
});
- stack.removeLast();
+
+ 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];
@@ -271,6 +443,7 @@
}
}
}
+ clearReverseSuffixTree(reverseSuffixTreeRoots);
}
void CombinedURLFilters::processNFAs(size_t maxNFASize, std::function<void(NFA&&)> handler)
Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (186909 => 186910)
--- trunk/Source/WebCore/contentextensions/DFA.cpp 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2015-07-16 21:51:08 UTC (rev 186910)
@@ -147,7 +147,7 @@
dataLogF("%llu", actions[actionIndex]);
}
}
- dataLogF("]");
+ dataLogF(">]");
if (!actions.isEmpty())
dataLogF(" [shape=doublecircle]");
Added: trunk/Source/WebCore/contentextensions/HashableActionList.h (0 => 186910)
--- trunk/Source/WebCore/contentextensions/HashableActionList.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/HashableActionList.h 2015-07-16 21:51:08 UTC (rev 186910)
@@ -0,0 +1,97 @@
+/*
+ * 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.
+ */
+
+#ifndef HashableActionList_h
+#define HashableActionList_h
+
+#include <wtf/StringHasher.h>
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+struct HashableActionList {
+ enum DeletedValueTag { DeletedValue };
+ explicit HashableActionList(DeletedValueTag) { state = Deleted; }
+
+ enum EmptyValueTag { EmptyValue };
+ explicit HashableActionList(EmptyValueTag) { state = Empty; }
+
+ template<typename AnyVectorType>
+ explicit HashableActionList(const AnyVectorType& otherActions)
+ : actions(otherActions)
+ , state(Valid)
+ {
+ std::sort(actions.begin(), actions.end());
+ StringHasher hasher;
+ hasher.addCharactersAssumingAligned(reinterpret_cast<const UChar*>(actions.data()), actions.size() * sizeof(uint64_t) / sizeof(UChar));
+ hash = hasher.hash();
+ }
+
+ bool isEmptyValue() const { return state == Empty; }
+ bool isDeletedValue() const { return state == Deleted; }
+
+ bool operator==(const HashableActionList other) const
+ {
+ return state == other.state && actions == other.actions;
+ }
+
+ bool operator!=(const HashableActionList other) const
+ {
+ return !(*this == other);
+ }
+
+ Vector<uint64_t> actions;
+ unsigned hash;
+ enum {
+ Valid,
+ Empty,
+ Deleted
+ } state;
+};
+
+struct HashableActionListHash {
+ static unsigned hash(const HashableActionList& actionKey)
+ {
+ return actionKey.hash;
+ }
+
+ static bool equal(const HashableActionList& a, const HashableActionList& b)
+ {
+ return a == b;
+ }
+ static const bool safeToCompareToEmptyOrDeleted = false;
+};
+
+struct HashableActionListHashTraits : public WTF::CustomHashTraits<HashableActionList> {
+ static const bool emptyValueIsZero = false;
+};
+
+} // namespace ContentExtensions
+
+} // namespace WebCore
+
+#endif
Modified: trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h (186909 => 186910)
--- trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h 2015-07-16 21:51:08 UTC (rev 186910)
@@ -52,9 +52,6 @@
{
m_nodeId = m_immutableNFA->nodes.size();
m_immutableNFA->nodes.append(ImmutableNFANode());
-#if !ASSERT_DISABLED
- m_isDisconnected = true;
-#endif
}
ImmutableNFANodeBuilder(ImmutableNFANodeBuilder&& other)
@@ -64,25 +61,28 @@
, m_actions(WTF::move(other.m_actions))
, m_nodeId(other.m_nodeId)
, m_finalized(other.m_finalized)
-#if !ASSERT_DISABLED
- , m_isDisconnected(other.m_isDisconnected)
-#endif
{
other.m_immutableNFA = nullptr;
other.m_finalized = true;
-#if !ASSERT_DISABLED
- other.m_isDisconnected = false;
-#endif
}
~ImmutableNFANodeBuilder()
{
- ASSERT_WITH_MESSAGE(!m_isDisconnected, "This nodes is not connected to anything and is not reached by any other node.");
-
if (!m_finalized)
finalize();
}
+ bool isValid() const
+ {
+ return !!m_immutableNFA;
+ }
+
+ uint32_t nodeId() const
+ {
+ ASSERT(isValid());
+ return m_nodeId;
+ }
+
struct TrivialRange {
CharacterType first;
CharacterType last;
@@ -108,15 +108,10 @@
bool isEnd;
};
- void addTransition(CharacterType first, CharacterType last, const ImmutableNFANodeBuilder& target)
+ void addTransition(CharacterType first, CharacterType last, uint32_t targetNodeId)
{
ASSERT(!m_finalized);
ASSERT(m_immutableNFA);
- ASSERT(m_immutableNFA == target.m_immutableNFA);
-#if !ASSERT_DISABLED
- m_isDisconnected = false;
- target.m_isDisconnected = false;
-#endif
struct Converter {
TargetSet convert(uint32_t target)
@@ -130,19 +125,20 @@
};
Converter converter;
- m_ranges.extend(FakeRangeIterator { { first, last }, target.m_nodeId, false }, FakeRangeIterator { { 0, 0 }, target.m_nodeId, true }, converter);
+ m_ranges.extend(FakeRangeIterator { { first, last }, targetNodeId, false }, FakeRangeIterator { { 0, 0 }, targetNodeId, true }, converter);
}
void addEpsilonTransition(const ImmutableNFANodeBuilder& target)
{
+ ASSERT(m_immutableNFA == target.m_immutableNFA);
+ addEpsilonTransition(target.m_nodeId);
+ }
+
+ void addEpsilonTransition(uint32_t targetNodeId)
+ {
ASSERT(!m_finalized);
ASSERT(m_immutableNFA);
- ASSERT(m_immutableNFA == target.m_immutableNFA);
-#if !ASSERT_DISABLED
- m_isDisconnected = false;
- target.m_isDisconnected = false;
-#endif
- m_epsilonTransitionTargets.add(target.m_nodeId);
+ m_epsilonTransitionTargets.add(targetNodeId);
}
template<typename ActionIterator>
@@ -168,10 +164,6 @@
other.m_immutableNFA = nullptr;
other.m_finalized = true;
-#if !ASSERT_DISABLED
- m_isDisconnected = other.m_isDisconnected;
- other.m_isDisconnected = false;
-#endif
return *this;
}
@@ -230,9 +222,6 @@
HashSet<ActionType, WTF::IntHash<ActionType>, WTF::UnsignedWithZeroKeyHashTraits<ActionType>> m_actions;
uint32_t m_nodeId;
bool m_finalized { true };
-#if !ASSERT_DISABLED
- mutable bool m_isDisconnected { false };
-#endif
};
}
Modified: trunk/Source/WebCore/contentextensions/Term.h (186909 => 186910)
--- trunk/Source/WebCore/contentextensions/Term.h 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Source/WebCore/contentextensions/Term.h 2015-07-16 21:51:08 UTC (rev 186910)
@@ -83,7 +83,8 @@
void quantify(const AtomQuantifier&);
- ImmutableCharNFANodeBuilder generateGraph(NFA&, ImmutableCharNFANodeBuilder& start, const ActionList& finalActions) const;
+ ImmutableCharNFANodeBuilder generateGraph(NFA&, ImmutableCharNFANodeBuilder& source, const ActionList& finalActions) const;
+ void generateGraph(NFA&, ImmutableCharNFANodeBuilder& source, uint32_t destination) const;
bool isEndOfLineAssertion() const;
@@ -118,7 +119,8 @@
// The return value can be false for a group equivalent to a universal transition.
bool isUniversalTransition() const;
- ImmutableCharNFANodeBuilder generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source) const;
+ void generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source, const ImmutableCharNFANodeBuilder& destination) const;
+ void generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source, uint32_t destination) const;
void destroy();
@@ -377,50 +379,52 @@
m_quantifier = quantifier;
}
-inline ImmutableCharNFANodeBuilder Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& start, const ActionList& finalActions) const
+inline ImmutableCharNFANodeBuilder Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& source, const ActionList& finalActions) const
{
+ ImmutableCharNFANodeBuilder newEnd(nfa);
+ generateGraph(nfa, source, newEnd.nodeId());
+ newEnd.setActions(finalActions.begin(), finalActions.end());
+ return newEnd;
+}
+
+inline void Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& source, uint32_t destination) const
+{
ASSERT(isValid());
- ImmutableCharNFANodeBuilder newEnd;
-
switch (m_quantifier) {
case AtomQuantifier::One: {
- newEnd = generateSubgraphForAtom(nfa, start);
+ generateSubgraphForAtom(nfa, source, destination);
break;
}
case AtomQuantifier::ZeroOrOne: {
- newEnd = generateSubgraphForAtom(nfa, start);
- start.addEpsilonTransition(newEnd);
+ generateSubgraphForAtom(nfa, source, destination);
+ source.addEpsilonTransition(destination);
break;
}
case AtomQuantifier::ZeroOrMore: {
ImmutableCharNFANodeBuilder repeatStart(nfa);
- start.addEpsilonTransition(repeatStart);
+ source.addEpsilonTransition(repeatStart);
- ImmutableCharNFANodeBuilder repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
+ ImmutableCharNFANodeBuilder repeatEnd(nfa);
+ generateSubgraphForAtom(nfa, repeatStart, repeatEnd);
repeatEnd.addEpsilonTransition(repeatStart);
- ImmutableCharNFANodeBuilder kleenEnd(nfa);
- repeatEnd.addEpsilonTransition(kleenEnd);
- start.addEpsilonTransition(kleenEnd);
- newEnd = WTF::move(kleenEnd);
+ repeatEnd.addEpsilonTransition(destination);
+ source.addEpsilonTransition(destination);
break;
}
case AtomQuantifier::OneOrMore: {
ImmutableCharNFANodeBuilder repeatStart(nfa);
- start.addEpsilonTransition(repeatStart);
+ source.addEpsilonTransition(repeatStart);
- ImmutableCharNFANodeBuilder repeatEnd = generateSubgraphForAtom(nfa, repeatStart);
+ ImmutableCharNFANodeBuilder repeatEnd(nfa);
+ generateSubgraphForAtom(nfa, repeatStart, repeatEnd);
repeatEnd.addEpsilonTransition(repeatStart);
- ImmutableCharNFANodeBuilder afterRepeat(nfa);
- repeatEnd.addEpsilonTransition(afterRepeat);
- newEnd = WTF::move(afterRepeat);
+ repeatEnd.addEpsilonTransition(destination);
break;
}
}
- newEnd.setActions(finalActions.begin(), finalActions.end());
- return newEnd;
}
inline bool Term::isEndOfLineAssertion() const
@@ -582,14 +586,19 @@
return false;
}
-inline ImmutableCharNFANodeBuilder Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source) const
+inline void Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source, const ImmutableCharNFANodeBuilder& destination) const
{
+ generateSubgraphForAtom(nfa, source, destination.nodeId());
+}
+
+inline void Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source, uint32_t destination) const
+{
switch (m_termType) {
case TermType::Empty:
ASSERT_NOT_REACHED();
- return ImmutableCharNFANodeBuilder();
+ source.addEpsilonTransition(destination);
+ break;
case TermType::CharacterSet: {
- ImmutableCharNFANodeBuilder newNode(nfa);
if (!m_atomData.characterSet.inverted()) {
UChar i = 0;
while (true) {
@@ -602,7 +611,7 @@
++i;
while (i < 128 && m_atomData.characterSet.get(i))
++i;
- source.addTransition(start, i - 1, newNode);
+ source.addTransition(start, i - 1, destination);
}
} else {
UChar i = 1;
@@ -616,27 +625,32 @@
++i;
while (i < 128 && !m_atomData.characterSet.get(i))
++i;
- source.addTransition(start, i - 1, newNode);
+ source.addTransition(start, i - 1, destination);
}
}
- return newNode;
+ break;
}
case TermType::Group: {
if (m_atomData.group.terms.isEmpty()) {
// FIXME: any kind of empty term could be avoided in the parser. This case should turned into an assertion.
- ImmutableCharNFANodeBuilder newNode(nfa);
- source.addEpsilonTransition(newNode);
- return newNode;
+ source.addEpsilonTransition(destination);
+ return;
}
+ if (m_atomData.group.terms.size() == 1) {
+ m_atomData.group.terms.first().generateGraph(nfa, source, destination);
+ return;
+ }
+
ImmutableCharNFANodeBuilder lastTarget = m_atomData.group.terms.first().generateGraph(nfa, source, ActionList());
- for (unsigned i = 1; i < m_atomData.group.terms.size(); ++i) {
+ for (unsigned i = 1; i < m_atomData.group.terms.size() - 1; ++i) {
const Term& currentTerm = m_atomData.group.terms[i];
ImmutableCharNFANodeBuilder newNode = currentTerm.generateGraph(nfa, lastTarget, ActionList());
lastTarget = WTF::move(newNode);
}
-
- return lastTarget;
+ const Term& lastTerm = m_atomData.group.terms.last();
+ lastTerm.generateGraph(nfa, lastTarget, destination);
+ break;
}
}
}
Modified: trunk/Tools/ChangeLog (186909 => 186910)
--- trunk/Tools/ChangeLog 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Tools/ChangeLog 2015-07-16 21:51:08 UTC (rev 186910)
@@ -1,3 +1,14 @@
+2015-07-16 Benjamin Poulain <[email protected]>
+
+ [Content extensions] Combine suffixes when generating NFAs
+ https://bugs.webkit.org/show_bug.cgi?id=146961
+
+ Reviewed by Alex Christensen.
+
+ * TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
+ (TestWebKitAPI::compareContents):
+ * TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
+
2015-07-15 Carlos Garcia Campos <[email protected]>
[GTK] Input method filter is always enabled when the view is focused
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp (186909 => 186910)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp 2015-07-16 21:51:08 UTC (rev 186910)
@@ -95,6 +95,103 @@
EXPECT_EQ(4, vector[3]);
}
+TEST(WTF_Vector, InitializeFromOtherInitialCapacity)
+{
+ Vector<int, 3> vector = { 1, 3, 2, 4 };
+ Vector<int, 5> vectorCopy(vector);
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+ EXPECT_EQ(5U, vectorCopy.capacity());
+
+ EXPECT_EQ(1, vectorCopy[0]);
+ EXPECT_EQ(3, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(4, vectorCopy[3]);
+}
+
+TEST(WTF_Vector, CopyFromOtherInitialCapacity)
+{
+ Vector<int, 3> vector = { 1, 3, 2, 4 };
+ Vector<int, 5> vectorCopy { 0 };
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(1U, vectorCopy.size());
+
+ vectorCopy = vector;
+
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+ EXPECT_EQ(5U, vectorCopy.capacity());
+
+ EXPECT_EQ(1, vectorCopy[0]);
+ EXPECT_EQ(3, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(4, vectorCopy[3]);
+}
+
+TEST(WTF_Vector, InitializeFromOtherOverflowBehavior)
+{
+ Vector<int, 7, WTF::CrashOnOverflow> vector = { 4, 3, 2, 1 };
+ Vector<int, 7, UnsafeVectorOverflow> vectorCopy(vector);
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+
+ EXPECT_EQ(4, vectorCopy[0]);
+ EXPECT_EQ(3, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(1, vectorCopy[3]);
+}
+
+TEST(WTF_Vector, CopyFromOtherOverflowBehavior)
+{
+ Vector<int, 7, WTF::CrashOnOverflow> vector = { 4, 3, 2, 1 };
+ Vector<int, 7, UnsafeVectorOverflow> vectorCopy = { 0, 0, 0 };
+
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(3U, vectorCopy.size());
+
+ vectorCopy = vector;
+
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+
+ EXPECT_EQ(4, vectorCopy[0]);
+ EXPECT_EQ(3, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(1, vectorCopy[3]);
+}
+
+TEST(WTF_Vector, InitializeFromOtherMinCapacity)
+{
+ Vector<int, 7, WTF::CrashOnOverflow, 1> vector = { 3, 4, 2, 1 };
+ Vector<int, 7, WTF::CrashOnOverflow, 50> vectorCopy(vector);
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+
+ EXPECT_EQ(3, vectorCopy[0]);
+ EXPECT_EQ(4, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(1, vectorCopy[3]);
+}
+
+TEST(WTF_Vector, CopyFromOtherMinCapacity)
+{
+ Vector<int, 7, WTF::CrashOnOverflow, 1> vector = { 3, 4, 2, 1 };
+ Vector<int, 7, WTF::CrashOnOverflow, 50> vectorCopy;
+
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(0U, vectorCopy.size());
+
+ vectorCopy = vector;
+
+ EXPECT_EQ(4U, vector.size());
+ EXPECT_EQ(4U, vectorCopy.size());
+
+ EXPECT_EQ(3, vectorCopy[0]);
+ EXPECT_EQ(4, vectorCopy[1]);
+ EXPECT_EQ(2, vectorCopy[2]);
+ EXPECT_EQ(1, vectorCopy[3]);
+}
+
TEST(WTF_Vector, Reverse)
{
Vector<int> intVector;
Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp (186909 => 186910)
--- trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-07-16 21:51:08 UTC (rev 186910)
@@ -235,6 +235,36 @@
testRequest(backend, mainDocumentRequest("http://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
}
+TEST_F(ContentExtensionTest, SingleCharacter)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^z\"}}]");
+ testRequest(matchBackend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("zttp://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"y\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/ywebkit"), { ContentExtensions::ActionType::BlockLoad });
+}
+
+TEST_F(ContentExtensionTest, SingleCharacterDisjunction)
+{
+ auto matchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^z\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"^c\"}}]");
+ testRequest(matchBackend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("bttp://webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("cttp://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(matchBackend, mainDocumentRequest("dttp://webkit.org/"), { });
+ testRequest(matchBackend, mainDocumentRequest("zttp://webkit.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ auto searchBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"x\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"y\"}}]");
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/dwebkit"), { });
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/xwebkit"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/ywebkit"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(searchBackend, mainDocumentRequest("http://webkit.org/zwebkit"), { });
+}
+
TEST_F(ContentExtensionTest, RangeBasic)
{
auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"w[0-9]c\", \"url-filter-is-case-sensitive\":true}},"
@@ -444,6 +474,142 @@
testRequest(backend, mainDocumentRequest("https://post.org/post"), { });
}
+TEST_F(ContentExtensionTest, UndistinguishableActionInsidePrefixTree)
+{
+ // In this case, the two actions are undistinguishable. The actions of "prefix" appear inside the prefixtree
+ // ending at "suffix".
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"prefix\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"prefixsuffix\"}}]");
+
+ testRequest(backend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://prefix.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/prefix"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/aaaprefixaaa"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://prefixsuffix.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/prefixsuffix"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/bbbprefixsuffixbbb"), { ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("http://suffix.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/suffix"), { });
+}
+
+TEST_F(ContentExtensionTest, DistinguishableActionInsidePrefixTree)
+{
+ // In this case, the two actions are distinguishable.
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"prefix\"}},"
+ "{\"action\":{\"type\":\"block-cookies\"},\"trigger\":{\"url-filter\":\"prefixsuffix\"}}]");
+
+ testRequest(backend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://prefix.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/prefix"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/aaaprefixaaa"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://prefixsuffix.org/"), { ContentExtensions::ActionType::BlockCookies, ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/prefixsuffix"), { ContentExtensions::ActionType::BlockCookies, ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/bbbprefixsuffixbbb"), { ContentExtensions::ActionType::BlockCookies, ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("http://suffix.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://webkit.org/suffix"), { });
+}
+
+TEST_F(ContentExtensionTest, DistinguishablePrefixAreNotMerged)
+{
+ auto backend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"foo\\\\.org\"}},"
+ "{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"bar\\\\.org\"}}]");
+
+ testRequest(backend, mainDocumentRequest("http://webkit.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://foo.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://bar.org/"), { ContentExtensions::ActionType::BlockLoad });
+
+ testRequest(backend, mainDocumentRequest("http://foor.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://fooar.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://fooba.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://foob.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://foor.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://foar.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://foba.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://fob.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://barf.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://barfo.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://baroo.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://baro.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://baf.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://bafo.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://baoo.org/"), { });
+ testRequest(backend, mainDocumentRequest("http://bao.org/"), { });
+
+ testRequest(backend, mainDocumentRequest("http://foo.orgbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://oo.orgbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://o.orgbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://.orgbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://rgbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://gbar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.orgar.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.orgr.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.org.org/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.orgorg/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.orgrg/"), { ContentExtensions::ActionType::BlockLoad });
+ testRequest(backend, mainDocumentRequest("http://foo.orgg/"), { ContentExtensions::ActionType::BlockLoad });
+}
+
+static void compareContents(const ContentExtensions::DFABytecodeInterpreter::Actions& a, const Vector<uint64_t>& b)
+{
+ EXPECT_EQ(a.size(), b.size());
+ for (unsigned i = 0; i < b.size(); ++i)
+ EXPECT_TRUE(a.contains(b[i]));
+}
+
+TEST_F(ContentExtensionTest, SearchSuffixesWithIdenticalActionAreMerged)
+{
+ ContentExtensions::CombinedURLFilters combinedURLFilters;
+ ContentExtensions::URLFilterParser parser(combinedURLFilters);
+ EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("foo\\.org", false, 0));
+ EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("ba\\.org", false, 0));
+
+ Vector<ContentExtensions::NFA> nfas = createNFAs(combinedURLFilters);
+ EXPECT_EQ(1ul, nfas.size());
+ EXPECT_EQ(12ul, nfas.first().nodes.size());
+
+ ContentExtensions::DFA dfa = ContentExtensions::NFAToDFA::convert(nfas.first());
+ Vector<ContentExtensions::DFABytecode> bytecode;
+ ContentExtensions::DFABytecodeCompiler compiler(dfa, bytecode);
+ compiler.compile();
+ ContentExtensions::DFABytecodeInterpreter interpreter(bytecode.data(), bytecode.size());
+ compareContents(interpreter.interpret("foo.org", 0), { 0 });
+ compareContents(interpreter.interpret("ba.org", 0), { 0 });
+ compareContents(interpreter.interpret("bar.org", 0), { });
+
+ compareContents(interpreter.interpret("paddingfoo.org", 0), { 0 });
+ compareContents(interpreter.interpret("paddingba.org", 0), { 0 });
+ compareContents(interpreter.interpret("paddingbar.org", 0), { });
+}
+
+TEST_F(ContentExtensionTest, SearchSuffixesWithDistinguishableActionAreNotMerged)
+{
+ ContentExtensions::CombinedURLFilters combinedURLFilters;
+ ContentExtensions::URLFilterParser parser(combinedURLFilters);
+ EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("foo\\.org", false, 0));
+ EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("ba\\.org", false, 1));
+
+ Vector<ContentExtensions::NFA> nfas = createNFAs(combinedURLFilters);
+
+ EXPECT_EQ(1ul, nfas.size());
+ EXPECT_EQ(17ul, nfas.first().nodes.size());
+
+ ContentExtensions::DFA dfa = ContentExtensions::NFAToDFA::convert(nfas.first());
+ Vector<ContentExtensions::DFABytecode> bytecode;
+ ContentExtensions::DFABytecodeCompiler compiler(dfa, bytecode);
+ compiler.compile();
+ ContentExtensions::DFABytecodeInterpreter interpreter(bytecode.data(), bytecode.size());
+ compareContents(interpreter.interpret("foo.org", 0), { 0 });
+ compareContents(interpreter.interpret("ba.org", 0), { 1 });
+ compareContents(interpreter.interpret("bar.org", 0), { });
+
+ compareContents(interpreter.interpret("paddingfoo.org", 0), { 0 });
+ compareContents(interpreter.interpret("paddingba.org", 0), { 1 });
+ compareContents(interpreter.interpret("paddingba.orgfoo.org", 0), { 1, 0 });
+ compareContents(interpreter.interpret("paddingbar.org", 0), { });
+}
+
TEST_F(ContentExtensionTest, DomainTriggers)
{
auto ifDomainBackend = makeBackend("[{\"action\":{\"type\":\"block\"},\"trigger\":{\"url-filter\":\"test\\\\.html\", \"if-domain\":[\"webkit.org\"]}}]");
@@ -853,13 +1019,6 @@
}
#ifdef NDEBUG
-static void compareContents(const ContentExtensions::DFABytecodeInterpreter::Actions& a, const Vector<uint64_t>& b)
-{
- EXPECT_EQ(a.size(), b.size());
- for (unsigned i = 0; i < b.size(); ++i)
- EXPECT_TRUE(a.contains(b[i]));
-}
-
static uint64_t expectedIndex(char c, unsigned position)
{
uint64_t index = c - 'A';
Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp (186909 => 186910)
--- trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-07-16 21:50:50 UTC (rev 186909)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-07-16 21:51:08 UTC (rev 186910)
@@ -41,15 +41,31 @@
TEST_F(DFAMinimizerTest, BasicSearch)
{
ContentExtensions::DFA dfa = buildDFAFromPatterns({ ".*foo", ".*bar", ".*bang"});
- EXPECT_EQ(static_cast<size_t>(10), countLiveNodes(dfa));
+ EXPECT_EQ(static_cast<size_t>(8), countLiveNodes(dfa));
dfa.minimize();
EXPECT_EQ(static_cast<size_t>(7), countLiveNodes(dfa));
}
+TEST_F(DFAMinimizerTest, MergeSuffixes)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ ".*aaa", ".*aab", ".*aba", ".*abb", ".*baa", ".*bab", ".*bba", ".*bbb"});
+ EXPECT_EQ(static_cast<size_t>(12), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(4), countLiveNodes(dfa));
+}
+
+TEST_F(DFAMinimizerTest, MergeInfixes)
+{
+ ContentExtensions::DFA dfa = buildDFAFromPatterns({ ".*aaakit", ".*aabkit", ".*abakit", ".*abbkit", ".*baakit", ".*babkit", ".*bbakit", ".*bbbkit"});
+ EXPECT_EQ(static_cast<size_t>(15), countLiveNodes(dfa));
+ dfa.minimize();
+ EXPECT_EQ(static_cast<size_t>(7), countLiveNodes(dfa));
+}
+
TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge1)
{
ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^a.a", "^b.a", "^bac", "^bbc", "^BCC"});
- EXPECT_EQ(static_cast<size_t>(13), countLiveNodes(dfa));
+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
dfa.minimize();
EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
}
@@ -57,7 +73,7 @@
TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge2)
{
ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^bbc", "^BCC", "^a.a", "^b.a"});
- EXPECT_EQ(static_cast<size_t>(11), countLiveNodes(dfa));
+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
dfa.minimize();
EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
}
@@ -65,7 +81,7 @@
TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge3)
{
ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^a.c", "^b.c", "^baa", "^bba", "^BCA"});
- EXPECT_EQ(static_cast<size_t>(13), countLiveNodes(dfa));
+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
dfa.minimize();
EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
}
@@ -73,7 +89,7 @@
TEST_F(DFAMinimizerTest, FallbackTransitionsWithDifferentiatorDoNotMerge4)
{
ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^baa", "^bba", "^BCA", "^a.c", "^b.c"});
- EXPECT_EQ(static_cast<size_t>(13), countLiveNodes(dfa));
+ EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
dfa.minimize();
EXPECT_EQ(static_cast<size_t>(6), countLiveNodes(dfa));
}
@@ -81,7 +97,7 @@
TEST_F(DFAMinimizerTest, FallbackTransitionsToOtherNodeInSameGroupDoesNotDifferentiateGroup)
{
ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^aac", "^a.c", "^b.c"});
- EXPECT_EQ(static_cast<size_t>(9), countLiveNodes(dfa));
+ EXPECT_EQ(static_cast<size_t>(5), countLiveNodes(dfa));
dfa.minimize();
EXPECT_EQ(static_cast<size_t>(4), countLiveNodes(dfa));
}
@@ -89,7 +105,7 @@
TEST_F(DFAMinimizerTest, SimpleFallBackTransitionDifferentiator1)
{
ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^a.bc.de", "^a.bd.ef"});
- EXPECT_EQ(static_cast<size_t>(12), countLiveNodes(dfa));
+ EXPECT_EQ(static_cast<size_t>(11), countLiveNodes(dfa));
dfa.minimize();
EXPECT_EQ(static_cast<size_t>(11), countLiveNodes(dfa));
}
@@ -97,7 +113,7 @@
TEST_F(DFAMinimizerTest, SimpleFallBackTransitionDifferentiator2)
{
ContentExtensions::DFA dfa = buildDFAFromPatterns({ "^cb.", "^db.b"});
- EXPECT_EQ(static_cast<size_t>(8), countLiveNodes(dfa));
+ EXPECT_EQ(static_cast<size_t>(7), countLiveNodes(dfa));
dfa.minimize();
EXPECT_EQ(static_cast<size_t>(7), countLiveNodes(dfa));
}
