Diff
Modified: trunk/Source/WebCore/ChangeLog (183876 => 183877)
--- trunk/Source/WebCore/ChangeLog 2015-05-06 17:47:32 UTC (rev 183876)
+++ trunk/Source/WebCore/ChangeLog 2015-05-06 17:51:07 UTC (rev 183877)
@@ -1,3 +1,21 @@
+2015-05-06 Alex Christensen <achristen...@webkit.org>
+
+ [Content Extensions] Test splitting NFAs by max NFA size.
+ https://bugs.webkit.org/show_bug.cgi?id=144659
+
+ Reviewed by Darin Adler.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * contentextensions/CombinedURLFilters.cpp:
+ (WebCore::ContentExtensions::generateNFAForSubtree):
+ (WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
+ * contentextensions/CombinedURLFilters.h:
+ * contentextensions/ContentExtensionCompiler.cpp:
+ (WebCore::ContentExtensions::compileRuleList):
+ * contentextensions/DFABytecodeCompiler.h:
+ * contentextensions/DFABytecodeInterpreter.h:
+ Make maxNFASize a parameter so we can test it with small values.
+
2015-05-06 Antti Koivisto <an...@apple.com>
REGRESSION (r183467): Unable to start downloads in private browsing mode
Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (183876 => 183877)
--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-05-06 17:47:32 UTC (rev 183876)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2015-05-06 17:51:07 UTC (rev 183877)
@@ -2176,8 +2176,8 @@
5CBC8DAC1AAA302200E1C803 /* MediaAccessibilitySoftLink.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5CBC8DAA1AAA302200E1C803 /* MediaAccessibilitySoftLink.cpp */; };
5CBC8DAD1AAA302200E1C803 /* MediaAccessibilitySoftLink.h in Headers */ = {isa = PBXBuildFile; fileRef = 5CBC8DAB1AAA302200E1C803 /* MediaAccessibilitySoftLink.h */; };
5CD9F5661AA0F73C00DA45FF /* DFABytecode.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C39305D1AA0F6A90029C816 /* DFABytecode.h */; settings = {ATTRIBUTES = (Private, ); }; };
- 5CD9F5671AA0F74200DA45FF /* DFABytecodeCompiler.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C39305F1AA0F6A90029C816 /* DFABytecodeCompiler.h */; };
- 5CD9F5681AA0F74600DA45FF /* DFABytecodeInterpreter.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C3930611AA0F6A90029C816 /* DFABytecodeInterpreter.h */; };
+ 5CD9F5671AA0F74200DA45FF /* DFABytecodeCompiler.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C39305F1AA0F6A90029C816 /* DFABytecodeCompiler.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 5CD9F5681AA0F74600DA45FF /* DFABytecodeInterpreter.h in Headers */ = {isa = PBXBuildFile; fileRef = 5C3930611AA0F6A90029C816 /* DFABytecodeInterpreter.h */; settings = {ATTRIBUTES = (Private, ); }; };
5CDFA6C81AA4F2DA00EA8746 /* ContentExtensionActions.h in Headers */ = {isa = PBXBuildFile; fileRef = 5CDFA6C71AA4F2DA00EA8746 /* ContentExtensionActions.h */; settings = {ATTRIBUTES = (Private, ); }; };
5CFC4350192409E300A0D3B5 /* PointerLockController.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5CFC434E192406A900A0D3B5 /* PointerLockController.cpp */; };
5D21A80213ECE5DF00BB7064 /* WebVTTParser.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5D21A80013ECE5DF00BB7064 /* WebVTTParser.cpp */; };
Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp (183876 => 183877)
--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-05-06 17:47:32 UTC (rev 183876)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2015-05-06 17:51:07 UTC (rev 183877)
@@ -151,7 +151,7 @@
actions.append(actionId);
}
-static void generateNFAForSubtree(NFA& nfa, unsigned nfaRootId, PrefixTreeVertex& root)
+static void generateNFAForSubtree(NFA& nfa, unsigned nfaRootId, PrefixTreeVertex& root, 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,
@@ -176,9 +176,6 @@
while (!stack.isEmpty()) {
PrefixTreeVertex& vertex = stack.last().vertex;
const unsigned edgeIndex = stack.last().edgeIndex;
-
- // FIXME: This can be tuned. More NFAs take longer to interpret, fewer use more memory and time to compile.
- const unsigned maxNFASize = 50000;
// 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.graphSize() > maxNFASize)
@@ -220,7 +217,7 @@
}
}
-void CombinedURLFilters::processNFAs(std::function<void(NFA&&)> handler)
+void CombinedURLFilters::processNFAs(size_t maxNFASize, std::function<void(NFA&&)> handler)
{
#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
print();
@@ -259,7 +256,7 @@
}
// Put the non-quantified vertices in the subtree into the NFA and delete them.
ASSERT(stack.last());
- generateNFAForSubtree(nfa, prefixEnd, *stack.last());
+ generateNFAForSubtree(nfa, prefixEnd, *stack.last(), maxNFASize);
handler(WTF::move(nfa));
Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.h (183876 => 183877)
--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.h 2015-05-06 17:47:32 UTC (rev 183876)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.h 2015-05-06 17:51:07 UTC (rev 183877)
@@ -46,7 +46,7 @@
void addPattern(uint64_t patternId, const Vector<Term>& pattern);
- void processNFAs(std::function<void(NFA&&)> handler);
+ void processNFAs(size_t maxNFASize, std::function<void(NFA&&)> handler);
bool isEmpty();
#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
Modified: trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp (183876 => 183877)
--- trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-05-06 17:47:32 UTC (rev 183876)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2015-05-06 17:51:07 UTC (rev 183877)
@@ -198,9 +198,12 @@
double totalNFAToByteCodeBuildTimeStart = monotonicallyIncreasingTime();
#endif
+ // FIXME: This can be tuned. More NFAs take longer to interpret, fewer use more memory and time to compile.
+ const unsigned maxNFASize = 50000;
+
bool firstNFASeen = false;
// FIXME: Combine small NFAs to reduce the number of NFAs.
- combinedURLFilters.processNFAs([&](NFA&& nfa) {
+ combinedURLFilters.processNFAs(maxNFASize, [&](NFA&& nfa) {
#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
nfa.debugPrintDot();
#endif
Modified: trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h (183876 => 183877)
--- trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h 2015-05-06 17:47:32 UTC (rev 183876)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeCompiler.h 2015-05-06 17:51:07 UTC (rev 183877)
@@ -38,7 +38,7 @@
struct DFA;
class DFANode;
-class DFABytecodeCompiler {
+class WEBCORE_EXPORT DFABytecodeCompiler {
public:
DFABytecodeCompiler(const DFA& dfa, Vector<DFABytecode>& bytecode)
: m_bytecode(bytecode)
Modified: trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.h (183876 => 183877)
--- trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.h 2015-05-06 17:47:32 UTC (rev 183876)
+++ trunk/Source/WebCore/contentextensions/DFABytecodeInterpreter.h 2015-05-06 17:51:07 UTC (rev 183877)
@@ -39,7 +39,7 @@
namespace ContentExtensions {
-class DFABytecodeInterpreter {
+class WEBCORE_EXPORT DFABytecodeInterpreter {
public:
DFABytecodeInterpreter(const DFABytecode* bytecode, unsigned bytecodeLength, Vector<bool>& pagesUsed)
: m_bytecode(bytecode)
Modified: trunk/Tools/ChangeLog (183876 => 183877)
--- trunk/Tools/ChangeLog 2015-05-06 17:47:32 UTC (rev 183876)
+++ trunk/Tools/ChangeLog 2015-05-06 17:51:07 UTC (rev 183877)
@@ -1,3 +1,16 @@
+2015-05-06 Alex Christensen <achristen...@webkit.org>
+
+ [Content Extensions] Test splitting NFAs by max NFA size.
+ https://bugs.webkit.org/show_bug.cgi?id=144659
+
+ Reviewed by Darin Adler.
+
+ * TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
+ (TestWebKitAPI::createNFAs):
+ (TestWebKitAPI::TEST_F):
+ * TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:
+ (TestWebKitAPI::createNFAs):
+
2015-05-05 daegyu lee <daegyu....@navercorp.com>
Remove the remaining vestiges of SVG feature define
Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp (183876 => 183877)
--- trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-05-06 17:47:32 UTC (rev 183876)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2015-05-06 17:51:07 UTC (rev 183877)
@@ -31,7 +31,11 @@
#include <WebCore/ContentExtensionCompiler.h>
#include <WebCore/ContentExtensionError.h>
#include <WebCore/ContentExtensionsBackend.h>
+#include <WebCore/DFA.h>
+#include <WebCore/DFABytecodeCompiler.h>
+#include <WebCore/DFABytecodeInterpreter.h>
#include <WebCore/NFA.h>
+#include <WebCore/NFAToDFA.h>
#include <WebCore/ResourceLoadInfo.h>
#include <WebCore/URL.h>
#include <WebCore/URLFilterParser.h>
@@ -177,7 +181,7 @@
{
Vector<ContentExtensions::NFA> nfas;
- combinedURLFilters.processNFAs([&](ContentExtensions::NFA&& nfa) {
+ combinedURLFilters.processNFAs(std::numeric_limits<size_t>::max(), [&](ContentExtensions::NFA&& nfa) {
nfas.append(WTF::move(nfa));
});
@@ -717,6 +721,45 @@
EXPECT_EQ(2ul, createNFAs(combinedURLFilters).size());
}
+TEST_F(ContentExtensionTest, SplittingLargeNFAs)
+{
+ const size_t expectedNFACounts[16] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1};
+
+ for (size_t i = 0; i < 16; i++) {
+ ContentExtensions::CombinedURLFilters combinedURLFilters;
+ ContentExtensions::URLFilterParser parser(combinedURLFilters);
+
+ EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("A+BBB", false, 1));
+ EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("A+CCC", false, 2));
+ EXPECT_EQ(ContentExtensions::URLFilterParser::ParseStatus::Ok, parser.addPattern("A+DDD", false, 2));
+
+ Vector<ContentExtensions::NFA> nfas;
+ combinedURLFilters.processNFAs(i, [&](ContentExtensions::NFA&& nfa) {
+ nfas.append(WTF::move(nfa));
+ });
+ EXPECT_EQ(nfas.size(), expectedNFACounts[i]);
+
+ Vector<ContentExtensions::DFABytecode> combinedBytecode;
+ for (auto& nfa : nfas) {
+ Vector<ContentExtensions::DFABytecode> bytecode;
+ ContentExtensions::DFABytecodeCompiler compiler(ContentExtensions::NFAToDFA::convert(nfa), bytecode);
+ compiler.compile();
+ combinedBytecode.appendVector(bytecode);
+ }
+
+ Vector<bool> pagesUsed;
+ ContentExtensions::DFABytecodeInterpreter interpreter(&combinedBytecode[0], combinedBytecode.size(), pagesUsed);
+
+ EXPECT_EQ(interpreter.interpret("ABBBX", 0).size(), 1ull);
+ EXPECT_EQ(interpreter.interpret("ACCCX", 0).size(), 1ull);
+ EXPECT_EQ(interpreter.interpret("ADDDX", 0).size(), 1ull);
+ EXPECT_EQ(interpreter.interpret("XBBBX", 0).size(), 0ull);
+ EXPECT_EQ(interpreter.interpret("ABBX", 0).size(), 0ull);
+ EXPECT_EQ(interpreter.interpret("ACCX", 0).size(), 0ull);
+ EXPECT_EQ(interpreter.interpret("ADDX", 0).size(), 0ull);
+ }
+}
+
TEST_F(ContentExtensionTest, QuantifierInGroup)
{
ContentExtensions::CombinedURLFilters combinedURLFilters;
Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp (183876 => 183877)
--- trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-05-06 17:47:32 UTC (rev 183876)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp 2015-05-06 17:51:07 UTC (rev 183877)
@@ -57,7 +57,7 @@
{
Vector<ContentExtensions::NFA> nfas;
- combinedURLFilters.processNFAs([&](ContentExtensions::NFA&& nfa) {
+ combinedURLFilters.processNFAs(std::numeric_limits<size_t>::max(), [&](ContentExtensions::NFA&& nfa) {
nfas.append(WTF::move(nfa));
});
