Diff
Modified: trunk/Source/WebCore/ChangeLog (270413 => 270414)
--- trunk/Source/WebCore/ChangeLog 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/ChangeLog 2020-12-04 00:01:23 UTC (rev 270414)
@@ -1,3 +1,97 @@
+2020-12-03 Alex Christensen <[email protected]>
+
+ Serialize NFA to disk before converting it to a DFA when compiling a WKContentRuleList
+ https://bugs.webkit.org/show_bug.cgi?id=219452
+
+ Reviewed by Geoffrey Garen.
+
+ This decreases maximum memory use by about 50% because the NFA and DFA never need to be in memory at the same time.
+ I'll have to do some tuning and on-device measurement, but this may allow us to increase maxRuleCount.
+
+ * Headers.cmake:
+ * Sources.txt:
+ * WebCore.xcodeproj/project.pbxproj:
+ * contentextensions/CombinedURLFilters.cpp:
+ (WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
+ * contentextensions/CombinedURLFilters.h:
+ * contentextensions/ContentExtensionCompiler.cpp:
+ (WebCore::ContentExtensions::compileToBytecode):
+ (WebCore::ContentExtensions::compileRuleList):
+ * contentextensions/ContentExtensionError.cpp:
+ (WebCore::ContentExtensions::contentExtensionErrorCategory):
+ * contentextensions/ContentExtensionError.h:
+ * contentextensions/ContentExtensionsDebugging.h:
+ * contentextensions/DFA.cpp:
+ (WebCore::ContentExtensions::DFA::shrinkToFit): Deleted.
+ * contentextensions/DFA.h:
+ * contentextensions/ImmutableNFA.h:
+ (WebCore::ContentExtensions::ImmutableNFA::clear):
+ (WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator* const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator-> const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator== const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator!= const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstTargetIterator::operator++): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::IterableConstTargets::begin const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::IterableConstTargets::end const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator== const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator!= const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::operator++): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::first const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::last const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::data const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::ConstRangeIterator::range const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::IterableConstRange::begin const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::IterableConstRange::end const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::IterableConstRange::debugPrint const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::transitionsForNode const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::root const): Deleted.
+ (WebCore::ContentExtensions::ImmutableNFA::finalize): Deleted.
+ * contentextensions/ImmutableNFANodeBuilder.h:
+ * contentextensions/NFAToDFA.cpp:
+ (WebCore::ContentExtensions::epsilonClosureExcludingSelf):
+ (WebCore::ContentExtensions::resolveEpsilonClosures):
+ (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetSource::NodeIdSetToUniqueNodeIdSetSource):
+ (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::translate):
+ (WebCore::ContentExtensions::createCombinedTransition):
+ (WebCore::ContentExtensions::getOrCreateDFANode):
+ (WebCore::ContentExtensions::NFAToDFA::convert):
+ * contentextensions/NFAToDFA.h:
+ * contentextensions/SerializedNFA.cpp: Added.
+ (WebCore::ContentExtensions::writeAllToFile):
+ (WebCore::ContentExtensions::SerializedNFA::serialize):
+ (WebCore::ContentExtensions::SerializedNFA::SerializedNFA):
+ (WebCore::ContentExtensions::SerializedNFA::pointerAtOffsetInFile const):
+ (WebCore::ContentExtensions::SerializedNFA::nodes const const):
+ (WebCore::ContentExtensions::SerializedNFA::transitions const const):
+ (WebCore::ContentExtensions::SerializedNFA::targets const const):
+ (WebCore::ContentExtensions::SerializedNFA::epsilonTransitionsTargets const const):
+ (WebCore::ContentExtensions::SerializedNFA::actions const const):
+ * contentextensions/SerializedNFA.h: Copied from Source/WebCore/contentextensions/ImmutableNFA.h.
+ (WebCore::ContentExtensions::SerializedNFA::Range::Range):
+ (WebCore::ContentExtensions::SerializedNFA::Range::begin const):
+ (WebCore::ContentExtensions::SerializedNFA::Range::end const):
+ (WebCore::ContentExtensions::SerializedNFA::Range::size const):
+ (WebCore::ContentExtensions::SerializedNFA::Range::operator[] const):
+ (WebCore::ContentExtensions::SerializedNFA::root const):
+ (WebCore::ContentExtensions::SerializedNFA::ConstTargetIterator::operator* const):
+ (WebCore::ContentExtensions::SerializedNFA::ConstTargetIterator::operator-> const):
+ (WebCore::ContentExtensions::SerializedNFA::ConstTargetIterator::operator== const):
+ (WebCore::ContentExtensions::SerializedNFA::ConstTargetIterator::operator!= const):
+ (WebCore::ContentExtensions::SerializedNFA::ConstTargetIterator::operator++):
+ (WebCore::ContentExtensions::SerializedNFA::IterableConstTargets::begin const):
+ (WebCore::ContentExtensions::SerializedNFA::IterableConstTargets::end const):
+ (WebCore::ContentExtensions::SerializedNFA::ConstRangeIterator::operator== const):
+ (WebCore::ContentExtensions::SerializedNFA::ConstRangeIterator::operator!= const):
+ (WebCore::ContentExtensions::SerializedNFA::ConstRangeIterator::operator++):
+ (WebCore::ContentExtensions::SerializedNFA::ConstRangeIterator::first const):
+ (WebCore::ContentExtensions::SerializedNFA::ConstRangeIterator::last const):
+ (WebCore::ContentExtensions::SerializedNFA::ConstRangeIterator::data const):
+ (WebCore::ContentExtensions::SerializedNFA::ConstRangeIterator::range const):
+ (WebCore::ContentExtensions::SerializedNFA::IterableConstRange::begin const):
+ (WebCore::ContentExtensions::SerializedNFA::IterableConstRange::end const):
+ (WebCore::ContentExtensions::SerializedNFA::IterableConstRange::debugPrint const):
+ (WebCore::ContentExtensions::SerializedNFA::transitionsForNode const):
+
2020-12-03 Tim Horton <[email protected]>
ASSERTION FAILED: isMainThread() in WTF::Optional<IntSize> &WebCore::surfaceMaximumSize()
Modified: trunk/Source/WebCore/Headers.cmake (270413 => 270414)
--- trunk/Source/WebCore/Headers.cmake 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/Headers.cmake 2020-12-04 00:01:23 UTC (rev 270414)
@@ -323,6 +323,7 @@
contentextensions/NFA.h
contentextensions/NFANode.h
contentextensions/NFAToDFA.h
+ contentextensions/SerializedNFA.h
contentextensions/Term.h
contentextensions/URLFilterParser.h
Modified: trunk/Source/WebCore/Sources.txt (270413 => 270414)
--- trunk/Source/WebCore/Sources.txt 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/Sources.txt 2020-12-04 00:01:23 UTC (rev 270414)
@@ -665,6 +665,7 @@
contentextensions/DFANode.cpp
contentextensions/NFA.cpp
contentextensions/NFAToDFA.cpp
+contentextensions/SerializedNFA.cpp
contentextensions/URLFilterParser.cpp
crypto/CryptoAlgorithm.cpp
crypto/CryptoAlgorithmRegistry.cpp
Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (270413 => 270414)
--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2020-12-04 00:01:23 UTC (rev 270414)
@@ -9408,6 +9408,8 @@
5B7AB9F62567DB7E006592D0 /* ScrollSnapOffsetsInfo.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ScrollSnapOffsetsInfo.cpp; sourceTree = "<group>"; };
5C001521250011000094AA93 /* TextCodecSingleByte.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TextCodecSingleByte.cpp; sourceTree = "<group>"; };
5C001523250011010094AA93 /* TextCodecSingleByte.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TextCodecSingleByte.h; sourceTree = "<group>"; };
+ 5C2EBE012577198900D55B05 /* SerializedNFA.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SerializedNFA.h; sourceTree = "<group>"; };
+ 5C2EBE0325771A4C00D55B05 /* SerializedNFA.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SerializedNFA.cpp; sourceTree = "<group>"; };
5C39305D1AA0F6A90029C816 /* DFABytecode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DFABytecode.h; sourceTree = "<group>"; };
5C39305E1AA0F6A90029C816 /* DFABytecodeCompiler.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DFABytecodeCompiler.cpp; sourceTree = "<group>"; };
5C39305F1AA0F6A90029C816 /* DFABytecodeCompiler.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DFABytecodeCompiler.h; sourceTree = "<group>"; };
@@ -18898,6 +18900,8 @@
269397201A4A412F00E8349D /* NFANode.h */,
267725FA1A5B3AD9003C24DD /* NFAToDFA.cpp */,
267725FB1A5B3AD9003C24DD /* NFAToDFA.h */,
+ 5C2EBE0325771A4C00D55B05 /* SerializedNFA.cpp */,
+ 5C2EBE012577198900D55B05 /* SerializedNFA.h */,
26E944DC1AC4B4EA007B85B5 /* Term.h */,
267726021A5DF6F2003C24DD /* URLFilterParser.cpp */,
267726031A5DF6F2003C24DD /* URLFilterParser.h */,
Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.cpp 2020-12-04 00:01:23 UTC (rev 270414)
@@ -444,7 +444,7 @@
clearReverseSuffixTree(reverseSuffixTreeRoots);
}
-void CombinedURLFilters::processNFAs(size_t maxNFASize, const WTF::Function<void(NFA&&)>& handler)
+bool CombinedURLFilters::processNFAs(size_t maxNFASize, Function<bool(NFA&&)>&& handler)
{
#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
print();
@@ -487,9 +487,9 @@
ASSERT(stack.last());
generateNFAForSubtree(nfa, WTFMove(lastNode), *stack.last(), m_actions, maxNFASize);
}
- nfa.finalize();
- handler(WTFMove(nfa));
+ if (!handler(WTFMove(nfa)))
+ return false;
// Clean up any processed leaf nodes.
while (true) {
@@ -503,6 +503,7 @@
break; // Leave the empty root.
}
}
+ return true;
}
} // namespace ContentExtensions
Modified: trunk/Source/WebCore/contentextensions/CombinedURLFilters.h (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/CombinedURLFilters.h 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/CombinedURLFilters.h 2020-12-04 00:01:23 UTC (rev 270414)
@@ -47,7 +47,7 @@
void addPattern(uint64_t actionId, const Vector<Term>& pattern);
void addDomain(uint64_t actionId, const String& domain);
- void processNFAs(size_t maxNFASize, const WTF::Function<void(NFA&&)>& handler);
+ bool processNFAs(size_t maxNFASize, Function<bool(NFA&&)>&&);
bool isEmpty() const;
#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
Modified: trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionCompiler.cpp 2020-12-04 00:01:23 UTC (rev 270414)
@@ -212,7 +212,7 @@
}
template<typename Functor>
-static void compileToBytecode(CombinedURLFilters&& filters, UniversalActionSet&& universalActions, Functor writeBytecodeToClient)
+static bool compileToBytecode(CombinedURLFilters&& filters, UniversalActionSet&& universalActions, Functor writeBytecodeToClient)
{
// Smaller maxNFASizes risk high compiling and interpreting times from having too many DFAs,
// larger maxNFASizes use too much memory when compiling.
@@ -243,22 +243,27 @@
const unsigned smallDFASize = 100;
DFACombiner smallDFACombiner;
- filters.processNFAs(maxNFASize, [&](NFA&& nfa) {
+ bool processedSuccessfully = filters.processNFAs(maxNFASize, [&](NFA&& nfa) {
#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
dataLogF("NFA\n");
nfa.debugPrintDot();
#endif
LOG_LARGE_STRUCTURES(nfa, nfa.memoryUsed());
- DFA dfa = NFAToDFA::convert(nfa);
- LOG_LARGE_STRUCTURES(dfa, dfa.memoryUsed());
+ auto dfa = NFAToDFA::convert(WTFMove(nfa));
+ if (!dfa)
+ return false;
+ LOG_LARGE_STRUCTURES(*dfa, dfa->memoryUsed());
- if (dfa.graphSize() < smallDFASize)
- smallDFACombiner.addDFA(WTFMove(dfa));
+ if (dfa->graphSize() < smallDFASize)
+ smallDFACombiner.addDFA(WTFMove(*dfa));
else {
- dfa.minimize();
- lowerDFAToBytecode(WTFMove(dfa));
+ dfa->minimize();
+ lowerDFAToBytecode(WTFMove(*dfa));
}
+ return true;
});
+ if (!processedSuccessfully)
+ return false;
smallDFACombiner.combineDFAs(smallDFASize, [&](DFA&& dfa) {
LOG_LARGE_STRUCTURES(dfa, dfa.memoryUsed());
@@ -281,6 +286,7 @@
writeBytecodeToClient(WTFMove(bytecode));
}
LOG_LARGE_STRUCTURES(universalActions, universalActions.capacity() * sizeof(unsigned));
+ return true;
}
std::error_code compileRuleList(ContentExtensionCompilationClient& client, String&& ruleJSON, Vector<ContentExtensionRule>&& parsedRuleList)
@@ -414,16 +420,22 @@
MonotonicTime totalNFAToByteCodeBuildTimeStart = MonotonicTime::now();
#endif
- compileToBytecode(WTFMove(filtersWithoutConditions), WTFMove(universalActionsWithoutConditions), [&](Vector<DFABytecode>&& bytecode) {
+ bool success = compileToBytecode(WTFMove(filtersWithoutConditions), WTFMove(universalActionsWithoutConditions), [&](Vector<DFABytecode>&& bytecode) {
client.writeFiltersWithoutConditionsBytecode(WTFMove(bytecode));
});
- compileToBytecode(WTFMove(filtersWithConditions), WTFMove(universalActionsWithConditions), [&](Vector<DFABytecode>&& bytecode) {
+ if (!success)
+ return ContentExtensionError::ErrorWritingSerializedNFA;
+ success = compileToBytecode(WTFMove(filtersWithConditions), WTFMove(universalActionsWithConditions), [&](Vector<DFABytecode>&& bytecode) {
client.writeFiltersWithConditionsBytecode(WTFMove(bytecode));
});
- compileToBytecode(WTFMove(topURLFilters), WTFMove(universalTopURLActions), [&](Vector<DFABytecode>&& bytecode) {
+ if (!success)
+ return ContentExtensionError::ErrorWritingSerializedNFA;
+ success = compileToBytecode(WTFMove(topURLFilters), WTFMove(universalTopURLActions), [&](Vector<DFABytecode>&& bytecode) {
client.writeTopURLFiltersBytecode(WTFMove(bytecode));
});
-
+ if (!success)
+ return ContentExtensionError::ErrorWritingSerializedNFA;
+
#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
MonotonicTime totalNFAToByteCodeBuildTimeEnd = MonotonicTime::now();
dataLogF(" Time spent building and compiling the DFAs: %f\n", (totalNFAToByteCodeBuildTimeEnd - totalNFAToByteCodeBuildTimeStart).seconds());
Modified: trunk/Source/WebCore/contentextensions/ContentExtensionError.cpp (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/ContentExtensionError.cpp 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionError.cpp 2020-12-04 00:01:23 UTC (rev 270414)
@@ -89,6 +89,8 @@
return "A list cannot have if-domain and unless-domain mixed with if-top-url and unless-top-url";
case ContentExtensionError::JSONInvalidNotification:
return "A notify action must have a string notification";
+ case ContentExtensionError::ErrorWritingSerializedNFA:
+ return "Internal I/O error";
}
return std::string();
Modified: trunk/Source/WebCore/contentextensions/ContentExtensionError.h (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/ContentExtensionError.h 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionError.h 2020-12-04 00:01:23 UTC (rev 270414)
@@ -59,6 +59,8 @@
JSONInvalidCSSDisplayNoneActionType,
JSONInvalidNotification,
JSONInvalidRegex,
+
+ ErrorWritingSerializedNFA,
};
extern const char* WebKitContentBlockerDomain;
Modified: trunk/Source/WebCore/contentextensions/ContentExtensionsDebugging.h (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/ContentExtensionsDebugging.h 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionsDebugging.h 2020-12-04 00:01:23 UTC (rev 270414)
@@ -33,9 +33,6 @@
#define CONTENT_EXTENSIONS_PERFORMANCE_REPORTING 0
-#define CONTENT_EXTENSIONS_MEMORY_REPORTING 0
-#define CONTENT_EXTENSIONS_PAGE_SIZE 16384
-
#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
typedef WTF::CrashOnOverflow ContentExtensionsOverflowHandler;
#else
Modified: trunk/Source/WebCore/contentextensions/DFA.cpp (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/DFA.cpp 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/DFA.cpp 2020-12-04 00:01:23 UTC (rev 270414)
@@ -51,14 +51,6 @@
+ nodes.capacity() * sizeof(DFANode);
}
-void DFA::shrinkToFit()
-{
- nodes.shrinkToFit();
- actions.shrinkToFit();
- transitionRanges.shrinkToFit();
- transitionDestinations.shrinkToFit();
-}
-
void DFA::minimize()
{
DFAMinimizer::minimize(*this);
Modified: trunk/Source/WebCore/contentextensions/DFA.h (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/DFA.h 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/DFA.h 2020-12-04 00:01:23 UTC (rev 270414)
@@ -39,7 +39,6 @@
struct WEBCORE_EXPORT DFA {
static DFA empty();
- void shrinkToFit();
void minimize();
unsigned graphSize() const;
size_t memoryUsed() const;
Modified: trunk/Source/WebCore/contentextensions/ImmutableNFA.h (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/ImmutableNFA.h 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/ImmutableNFA.h 2020-12-04 00:01:23 UTC (rev 270414)
@@ -58,114 +58,15 @@
Vector<uint32_t, 0, ContentExtensionsOverflowHandler> epsilonTransitionsTargets;
Vector<ActionType, 0, ContentExtensionsOverflowHandler> actions;
- struct ConstTargetIterator {
- const ImmutableNFA& immutableNFA;
- uint32_t position;
-
- const uint32_t& operator*() const { return immutableNFA.targets[position]; }
- const uint32_t* operator->() const { return &immutableNFA.targets[position]; }
-
- bool operator==(const ConstTargetIterator& other) const
- {
- ASSERT(&immutableNFA == &other.immutableNFA);
- return position == other.position;
- }
- bool operator!=(const ConstTargetIterator& other) const { return !(*this == other); }
-
- ConstTargetIterator& operator++()
- {
- ++position;
- return *this;
- }
- };
-
- struct IterableConstTargets {
- const ImmutableNFA& immutableNFA;
- uint32_t targetStart;
- uint32_t targetEnd;
-
- ConstTargetIterator begin() const { return { immutableNFA, targetStart }; }
- ConstTargetIterator end() const { return { immutableNFA, targetEnd }; }
- };
-
- struct ConstRangeIterator {
- const ImmutableNFA& immutableNFA;
- uint32_t position;
-
- bool operator==(const ConstRangeIterator& other) const
- {
- ASSERT(&immutableNFA == &other.immutableNFA);
- return position == other.position;
- }
- bool operator!=(const ConstRangeIterator& other) const { return !(*this == other); }
-
- ConstRangeIterator& operator++()
- {
- ++position;
- return *this;
- }
-
- CharacterType first() const
- {
- return range().first;
- }
-
- CharacterType last() const
- {
- return range().last;
- }
-
- IterableConstTargets data() const
- {
- const ImmutableRange<CharacterType>& range = this->range();
- return { immutableNFA, range.targetStart, range.targetEnd };
- };
-
- private:
- const ImmutableRange<CharacterType>& range() const
- {
- return immutableNFA.transitions[position];
- }
- };
-
- struct IterableConstRange {
- const ImmutableNFA& immutableNFA;
- uint32_t rangesStart;
- uint32_t rangesEnd;
-
- ConstRangeIterator begin() const { return { immutableNFA, rangesStart }; }
- ConstRangeIterator end() const { return { immutableNFA, rangesEnd }; }
-
-#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
- void debugPrint() const
- {
- for (const auto& range : *this)
- WTFLogAlways(" %d-%d", range.first, range.last);
- }
-#endif
- };
-
- IterableConstRange transitionsForNode(uint32_t nodeId) const
+ void clear()
{
- const ImmutableNFANode& node = nodes[nodeId];
- return { *this, node.rangesStart, node.rangesEnd };
- };
-
- uint32_t root() const
- {
- RELEASE_ASSERT(!nodes.isEmpty());
- return 0;
+ nodes.clear();
+ transitions.clear();
+ targets.clear();
+ epsilonTransitionsTargets.clear();
+ actions.clear();
}
- void finalize()
- {
- nodes.shrinkToFit();
- transitions.shrinkToFit();
- targets.shrinkToFit();
- epsilonTransitionsTargets.shrinkToFit();
- actions.shrinkToFit();
- }
-
size_t memoryUsed() const
{
return nodes.capacity() * sizeof(ImmutableNFANode)
Modified: trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/ImmutableNFANodeBuilder.h 2020-12-04 00:01:23 UTC (rev 270414)
@@ -35,9 +35,9 @@
namespace ContentExtensions {
-// A ImmutableNFANodeBuilder let you build a NFA node by adding states and linking with other nodes.
-// Whe a builder is destructed, all its properties are finalized into the NFA. Using the NA with a live
-// builder results in undefined behaviors.
+// A ImmutableNFANodeBuilder let you build an NFA node by adding states and linking with other nodes.
+// When a builder is destructed, all its properties are finalized into the NFA. Using the NFA with a live
+// builder results in undefined behavior.
template <typename CharacterType, typename ActionType>
class ImmutableNFANodeBuilder {
typedef ImmutableNFA<CharacterType, ActionType> TypedImmutableNFA;
Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.cpp (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.cpp 2020-12-04 00:01:23 UTC (rev 270414)
@@ -33,6 +33,7 @@
#include "ImmutableNFA.h"
#include "MutableRangeList.h"
#include "NFA.h"
+#include "SerializedNFA.h"
#include <wtf/DataLog.h>
#include <wtf/HashMap.h>
#include <wtf/HashSet.h>
@@ -51,7 +52,7 @@
// FIXME: include the hash inside NodeIdSet.
typedef NFANodeIndexSet NodeIdSet;
-static inline void epsilonClosureExcludingSelf(NFA& nfa, unsigned nodeId, UniqueNodeList& output)
+static inline void epsilonClosureExcludingSelf(const SerializedNFA& nfa, unsigned nodeId, UniqueNodeList& output)
{
NodeIdSet closure({ nodeId });
Vector<unsigned, 64, ContentExtensionsOverflowHandler> unprocessedNodes({ nodeId });
@@ -58,10 +59,10 @@
do {
unsigned unprocessedNodeId = unprocessedNodes.takeLast();
- const auto& node = nfa.nodes[unprocessedNodeId];
+ const auto& node = nfa.nodes()[unprocessedNodeId];
for (uint32_t epsilonTargetIndex = node.epsilonTransitionTargetsStart; epsilonTargetIndex < node.epsilonTransitionTargetsEnd; ++epsilonTargetIndex) {
- uint32_t targetNodeId = nfa.epsilonTransitionsTargets[epsilonTargetIndex];
+ uint32_t targetNodeId = nfa.epsilonTransitionsTargets()[epsilonTargetIndex];
auto addResult = closure.add(targetNodeId);
if (addResult.isNewEntry) {
unprocessedNodes.append(targetNodeId);
@@ -73,18 +74,16 @@
output.shrinkToFit();
}
-static void resolveEpsilonClosures(NFA& nfa, NFANodeClosures& nfaNodeClosures)
+static NFANodeClosures resolveEpsilonClosures(const SerializedNFA& nfa)
{
- unsigned nfaGraphSize = nfa.nodes.size();
+ NFANodeClosures nfaNodeClosures;
+ unsigned nfaGraphSize = nfa.nodes().size();
nfaNodeClosures.resize(nfaGraphSize);
for (unsigned nodeId = 0; nodeId < nfaGraphSize; ++nodeId)
epsilonClosureExcludingSelf(nfa, nodeId, nfaNodeClosures[nodeId]);
- // Every nodes still point to that table, but we won't use it ever again.
- // Clear it to get back the memory. That's not pretty but memory is important here, we have both
- // graphs existing at the same time.
- nfa.epsilonTransitionsTargets.clear();
+ return nfaNodeClosures;
}
static ALWAYS_INLINE void extendSetWithClosure(const NFANodeClosures& nfaNodeClosures, unsigned nodeId, NodeIdSet& set)
@@ -215,7 +214,7 @@
typedef HashSet<std::unique_ptr<UniqueNodeIdSet>, UniqueNodeIdSetHash, UniqueNodeIdSetHashHashTraits> UniqueNodeIdSetTable;
struct NodeIdSetToUniqueNodeIdSetSource {
- NodeIdSetToUniqueNodeIdSetSource(DFA& dfa, const NFA& nfa, const NodeIdSet& nodeIdSet)
+ NodeIdSetToUniqueNodeIdSetSource(DFA& dfa, const SerializedNFA& nfa, const NodeIdSet& nodeIdSet)
: dfa(dfa)
, nfa(nfa)
, nodeIdSet(nodeIdSet)
@@ -227,7 +226,7 @@
this->hash = DefaultHash<unsigned>::hash(hash);
}
DFA& dfa;
- const NFA& nfa;
+ const SerializedNFA& nfa;
const NodeIdSet& nodeIdSet;
unsigned hash;
};
@@ -250,9 +249,9 @@
HashSet<uint64_t, DefaultHash<uint64_t>, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> actions;
for (unsigned nfaNodeId : source.nodeIdSet) {
- const auto& nfaNode = source.nfa.nodes[nfaNodeId];
+ const auto& nfaNode = source.nfa.nodes()[nfaNodeId];
for (unsigned actionIndex = nfaNode.actionStart; actionIndex < nfaNode.actionEnd; ++actionIndex)
- actions.add(source.nfa.actions[actionIndex]);
+ actions.add(source.nfa.actions()[actionIndex]);
}
unsigned actionsStart = source.dfa.actions.size();
@@ -299,7 +298,7 @@
}
};
-static inline void createCombinedTransition(PreallocatedNFANodeRangeList& combinedRangeList, const UniqueNodeIdSetImpl& sourceNodeSet, const NFA& immutableNFA, const NFANodeClosures& nfaNodeclosures)
+static inline void createCombinedTransition(PreallocatedNFANodeRangeList& combinedRangeList, const UniqueNodeIdSetImpl& sourceNodeSet, const SerializedNFA& serializedNFA, const NFANodeClosures& nfaNodeclosures)
{
combinedRangeList.clear();
@@ -308,14 +307,14 @@
DataConverterWithEpsilonClosure converter { nfaNodeclosures };
for (unsigned i = 0; i < sourceNodeSet.m_size; ++i) {
unsigned nodeId = buffer[i];
- auto transitions = immutableNFA.transitionsForNode(nodeId);
+ auto transitions = serializedNFA.transitionsForNode(nodeId);
combinedRangeList.extend(transitions.begin(), transitions.end(), converter);
}
}
-static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const NFA& nfa, DFA& dfa, UniqueNodeIdSetTable& uniqueNodeIdSetTable, UniqueNodeQueue& unprocessedNodes)
+static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const SerializedNFA& serializedNFA, DFA& dfa, UniqueNodeIdSetTable& uniqueNodeIdSetTable, UniqueNodeQueue& unprocessedNodes)
{
- NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfa, nfa, nfaNodeSet);
+ NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfa, serializedNFA, nfaNodeSet);
auto uniqueNodeIdAddResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(nodeIdSetToUniqueNodeIdSetSource);
if (uniqueNodeIdAddResult.isNewEntry)
unprocessedNodes.append(uniqueNodeIdAddResult.iterator->impl());
@@ -323,19 +322,21 @@
return uniqueNodeIdAddResult.iterator->impl()->m_dfaNodeId;
}
-DFA NFAToDFA::convert(NFA& nfa)
+Optional<DFA> NFAToDFA::convert(NFA&& nfa)
{
- NFANodeClosures nfaNodeClosures;
- resolveEpsilonClosures(nfa, nfaNodeClosures);
+ auto serializedNFA = SerializedNFA::serialize(WTFMove(nfa));
+ if (!serializedNFA)
+ return WTF::nullopt;
+ NFANodeClosures nfaNodeClosures = resolveEpsilonClosures(*serializedNFA);
DFA dfa;
- NodeIdSet initialSet({ nfa.root() });
- extendSetWithClosure(nfaNodeClosures, nfa.root(), initialSet);
+ NodeIdSet initialSet({ serializedNFA->root() });
+ extendSetWithClosure(nfaNodeClosures, serializedNFA->root(), initialSet);
UniqueNodeIdSetTable uniqueNodeIdSetTable;
- NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfa, nfa, initialSet);
+ NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfa, *serializedNFA, initialSet);
auto addResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(initialNodeIdSetToUniqueNodeIdSetSource);
UniqueNodeQueue unprocessedNodes;
@@ -344,11 +345,11 @@
PreallocatedNFANodeRangeList combinedRangeList;
do {
UniqueNodeIdSetImpl* uniqueNodeIdSetImpl = unprocessedNodes.takeLast();
- createCombinedTransition(combinedRangeList, *uniqueNodeIdSetImpl, nfa, nfaNodeClosures);
+ createCombinedTransition(combinedRangeList, *uniqueNodeIdSetImpl, *serializedNFA, nfaNodeClosures);
unsigned transitionsStart = dfa.transitionRanges.size();
for (const NFANodeRange& range : combinedRangeList) {
- unsigned targetNodeId = getOrCreateDFANode(range.data, nfa, dfa, uniqueNodeIdSetTable, unprocessedNodes);
+ unsigned targetNodeId = getOrCreateDFANode(range.data, *serializedNFA, dfa, uniqueNodeIdSetTable, unprocessedNodes);
dfa.transitionRanges.append({ range.first, range.last });
dfa.transitionDestinations.append(targetNodeId);
}
@@ -360,8 +361,7 @@
dfaSourceNode.setTransitions(transitionsStart, static_cast<uint8_t>(transitionsLength));
} while (!unprocessedNodes.isEmpty());
- dfa.shrinkToFit();
- return dfa;
+ return WTFMove(dfa);
}
} // namespace ContentExtensions
Modified: trunk/Source/WebCore/contentextensions/NFAToDFA.h (270413 => 270414)
--- trunk/Source/WebCore/contentextensions/NFAToDFA.h 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebCore/contentextensions/NFAToDFA.h 2020-12-04 00:01:23 UTC (rev 270414)
@@ -38,7 +38,7 @@
// NFAToDFA provides a way to build a DFA corresponding to a NFA.
class NFAToDFA {
public:
- WEBCORE_EXPORT static DFA convert(NFA&);
+ WEBCORE_EXPORT static Optional<DFA> convert(NFA&&);
};
} // namespace ContentExtensions
Added: trunk/Source/WebCore/contentextensions/SerializedNFA.cpp (0 => 270414)
--- trunk/Source/WebCore/contentextensions/SerializedNFA.cpp (rev 0)
+++ trunk/Source/WebCore/contentextensions/SerializedNFA.cpp 2020-12-04 00:01:23 UTC (rev 270414)
@@ -0,0 +1,139 @@
+/*
+ * Copyright (C) 2020 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 "SerializedNFA.h"
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+namespace WebCore {
+namespace ContentExtensions {
+
+template<typename T>
+bool writeAllToFile(FileSystem::PlatformFileHandle file, const T& container)
+{
+ const char* bytes = reinterpret_cast<const char*>(container.data());
+ size_t bytesLength = container.size() * sizeof(container[0]);
+ const char* end = bytes + bytesLength;
+ while (bytes < end) {
+ auto written = FileSystem::writeToFile(file, bytes, bytesLength);
+ if (written == -1)
+ return false;
+ bytes += written;
+ bytesLength -= written;
+ }
+ return true;
+}
+
+Optional<SerializedNFA> SerializedNFA::serialize(NFA&& nfa)
+{
+ auto file = FileSystem::invalidPlatformFileHandle;
+ auto filename = FileSystem::openTemporaryFile("SerializedNFA", file);
+ if (!FileSystem::isHandleValid(file))
+ return WTF::nullopt;
+
+ bool wroteSuccessfully = writeAllToFile(file, nfa.nodes)
+ && writeAllToFile(file, nfa.transitions)
+ && writeAllToFile(file, nfa.targets)
+ && writeAllToFile(file, nfa.epsilonTransitionsTargets)
+ && writeAllToFile(file, nfa.actions);
+ if (!wroteSuccessfully) {
+ FileSystem::closeFile(file);
+ FileSystem::deleteFile(filename);
+ return WTF::nullopt;
+ }
+
+ bool mappedSuccessfully = false;
+ FileSystem::MappedFileData mappedFile(file, FileSystem::MappedFileMode::Private, mappedSuccessfully);
+ FileSystem::closeFile(file);
+ FileSystem::deleteFile(filename);
+ if (!mappedSuccessfully)
+ return WTF::nullopt;
+
+ Metadata metadata {
+ nfa.nodes.size(),
+ nfa.transitions.size(),
+ nfa.targets.size(),
+ nfa.epsilonTransitionsTargets.size(),
+ nfa.actions.size(),
+ 0,
+ nfa.nodes.size() * sizeof(nfa.nodes[0]),
+ nfa.nodes.size() * sizeof(nfa.nodes[0])
+ + nfa.transitions.size() * sizeof(nfa.transitions[0]),
+ nfa.nodes.size() * sizeof(nfa.nodes[0])
+ + nfa.transitions.size() * sizeof(nfa.transitions[0])
+ + nfa.targets.size() * sizeof(nfa.targets[0]),
+ nfa.nodes.size() * sizeof(nfa.nodes[0])
+ + nfa.transitions.size() * sizeof(nfa.transitions[0])
+ + nfa.targets.size() * sizeof(nfa.targets[0])
+ + nfa.epsilonTransitionsTargets.size() * sizeof(nfa.epsilonTransitionsTargets[0])
+ };
+
+ nfa.clear();
+
+ return {{ WTFMove(mappedFile), WTFMove(metadata) }};
+}
+
+SerializedNFA::SerializedNFA(FileSystem::MappedFileData&& file, Metadata&& metadata)
+ : m_file(WTFMove(file))
+ , m_metadata(WTFMove(metadata))
+{
+}
+
+template<typename T>
+const T* SerializedNFA::pointerAtOffsetInFile(size_t offset) const
+{
+ return reinterpret_cast<const T*>(reinterpret_cast<const uint8_t*>(m_file.data()) + offset);
+}
+
+auto SerializedNFA::nodes() const -> const Range<ImmutableNFANode>
+{
+ return { pointerAtOffsetInFile<ImmutableNFANode>(m_metadata.nodesOffset), m_metadata.nodesSize };
+}
+
+auto SerializedNFA::transitions() const -> const Range<ImmutableRange<char>>
+{
+ return { pointerAtOffsetInFile<ImmutableRange<char>>(m_metadata.transitionsOffset), m_metadata.transitionsSize };
+}
+
+auto SerializedNFA::targets() const -> const Range<uint32_t>
+{
+ return { pointerAtOffsetInFile<uint32_t>(m_metadata.targetsOffset), m_metadata.targetsSize };
+}
+
+auto SerializedNFA::epsilonTransitionsTargets() const -> const Range<uint32_t>
+{
+ return { pointerAtOffsetInFile<uint32_t>(m_metadata.epsilonTransitionsTargetsOffset), m_metadata.epsilonTransitionsTargetsSize };
+}
+
+auto SerializedNFA::actions() const -> const Range<uint64_t>
+{
+ return { pointerAtOffsetInFile<uint64_t>(m_metadata.actionsOffset), m_metadata.actionsSize };
+}
+
+} // namespace ContentExtensions
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
Copied: trunk/Source/WebCore/contentextensions/SerializedNFA.h (from rev 270413, trunk/Source/WebCore/contentextensions/ImmutableNFA.h) (0 => 270414)
--- trunk/Source/WebCore/contentextensions/SerializedNFA.h (rev 0)
+++ trunk/Source/WebCore/contentextensions/SerializedNFA.h 2020-12-04 00:01:23 UTC (rev 270414)
@@ -0,0 +1,192 @@
+/*
+ * Copyright (C) 2020 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.
+ */
+
+#pragma once
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+#include <wtf/FileSystem.h>
+
+namespace WebCore {
+namespace ContentExtensions {
+
+struct NFA;
+
+class SerializedNFA {
+public:
+ static Optional<SerializedNFA> serialize(NFA&&);
+ SerializedNFA(SerializedNFA&&) = default;
+
+ template<typename T>
+ class Range {
+ public:
+ Range(const T* begin, size_t size)
+ : m_begin(begin)
+ , m_size(size) { }
+ const T* begin() const { return m_begin; }
+ const T* end() const { return m_begin + m_size; }
+ size_t size() const { return m_size; }
+ const T& operator[](size_t i) const
+ {
+ RELEASE_ASSERT(i < m_size);
+ return begin()[i];
+ }
+ private:
+ const T* m_begin { nullptr };
+ size_t m_size { 0 };
+ };
+
+ const Range<ImmutableNFANode> nodes() const;
+ const Range<ImmutableRange<char>> transitions() const;
+ const Range<uint32_t> targets() const;
+ const Range<uint32_t> epsilonTransitionsTargets() const;
+ const Range<uint64_t> actions() const;
+
+ uint32_t root() const
+ {
+ RELEASE_ASSERT(nodes().size());
+ return 0;
+ }
+
+ struct ConstTargetIterator {
+ const SerializedNFA& serializedNFA;
+ uint32_t position;
+
+ const uint32_t& operator*() const { return serializedNFA.targets()[position]; }
+ const uint32_t* operator->() const { return &serializedNFA.targets()[position]; }
+
+ bool operator==(const ConstTargetIterator& other) const
+ {
+ ASSERT(&serializedNFA == &other.serializedNFA);
+ return position == other.position;
+ }
+ bool operator!=(const ConstTargetIterator& other) const { return !(*this == other); }
+
+ ConstTargetIterator& operator++()
+ {
+ ++position;
+ return *this;
+ }
+ };
+
+ struct IterableConstTargets {
+ const SerializedNFA& serializedNFA;
+ uint32_t targetStart;
+ uint32_t targetEnd;
+
+ ConstTargetIterator begin() const { return { serializedNFA, targetStart }; }
+ ConstTargetIterator end() const { return { serializedNFA, targetEnd }; }
+ };
+
+ struct ConstRangeIterator {
+ const SerializedNFA& serializedNFA;
+ uint32_t position;
+
+ bool operator==(const ConstRangeIterator& other) const
+ {
+ ASSERT(&serializedNFA == &other.serializedNFA);
+ return position == other.position;
+ }
+ bool operator!=(const ConstRangeIterator& other) const { return !(*this == other); }
+
+ ConstRangeIterator& operator++()
+ {
+ ++position;
+ return *this;
+ }
+
+ char first() const
+ {
+ return range().first;
+ }
+
+ char last() const
+ {
+ return range().last;
+ }
+
+ IterableConstTargets data() const
+ {
+ const ImmutableRange<char>& range = this->range();
+ return { serializedNFA, range.targetStart, range.targetEnd };
+ };
+
+ private:
+ const ImmutableRange<char>& range() const
+ {
+ return serializedNFA.transitions()[position];
+ }
+ };
+
+ struct IterableConstRange {
+ const SerializedNFA& serializedNFA;
+ uint32_t rangesStart;
+ uint32_t rangesEnd;
+
+ ConstRangeIterator begin() const { return { serializedNFA, rangesStart }; }
+ ConstRangeIterator end() const { return { serializedNFA, rangesEnd }; }
+
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+ void debugPrint() const
+ {
+ for (const auto& range : *this)
+ WTFLogAlways(" %d-%d", range.first, range.last);
+ }
+#endif
+ };
+
+ IterableConstRange transitionsForNode(uint32_t nodeId) const
+ {
+ const auto& node = nodes()[nodeId];
+ return { *this, node.rangesStart, node.rangesEnd };
+ }
+
+private:
+ struct Metadata {
+ size_t nodesSize { 0 };
+ size_t transitionsSize { 0 };
+ size_t targetsSize { 0 };
+ size_t epsilonTransitionsTargetsSize { 0 };
+ size_t actionsSize { 0 };
+
+ size_t nodesOffset { 0 };
+ size_t transitionsOffset { 0 };
+ size_t targetsOffset { 0 };
+ size_t epsilonTransitionsTargetsOffset { 0 };
+ size_t actionsOffset { 0 };
+ };
+ SerializedNFA(FileSystem::MappedFileData&&, Metadata&&);
+
+ template<typename T>
+ const T* pointerAtOffsetInFile(size_t) const;
+
+ FileSystem::MappedFileData m_file;
+ Metadata m_metadata;
+};
+
+} // namespace ContentExtensions
+} // namespace WebCore
+
+#endif // ENABLE(CONTENT_EXTENSIONS)
Modified: trunk/Source/WebKit/ChangeLog (270413 => 270414)
--- trunk/Source/WebKit/ChangeLog 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebKit/ChangeLog 2020-12-04 00:01:23 UTC (rev 270414)
@@ -1,3 +1,15 @@
+2020-12-03 Alex Christensen <[email protected]>
+
+ Serialize NFA to disk before converting it to a DFA when compiling a WKContentRuleList
+ https://bugs.webkit.org/show_bug.cgi?id=219452
+
+ Reviewed by Geoffrey Garen.
+
+ * UIProcess/API/Cocoa/WKContentRuleListStore.mm:
+ (-[WKContentRuleListStore _compileContentRuleListForIdentifier:encodedContentRuleList:completionHandler:]):
+ * UIProcess/API/Cocoa/WKContentRuleListStorePrivate.h:
+ Remove NS_RELEASES_ARGUMENT because it was incorrect and unnecessary because the WTF::String is copied to a background thread.
+
2020-12-03 Chris Dumez <[email protected]>
Make sure the GPUConnectionToWebProcess gets destroyed when the connection to the WebProcess gets severed
Modified: trunk/Source/WebKit/UIProcess/API/Cocoa/WKContentRuleListStore.mm (270413 => 270414)
--- trunk/Source/WebKit/UIProcess/API/Cocoa/WKContentRuleListStore.mm 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebKit/UIProcess/API/Cocoa/WKContentRuleListStore.mm 2020-12-04 00:01:23 UTC (rev 270414)
@@ -146,8 +146,7 @@
});
}
-// NS_RELEASES_ARGUMENT to keep peak memory usage low.
-- (void)_compileContentRuleListForIdentifier:(NSString *)identifier encodedContentRuleList:(NSString *) NS_RELEASES_ARGUMENT encodedContentRuleList completionHandler:(void (^)(WKContentRuleList *, NSError *))completionHandler
+- (void)_compileContentRuleListForIdentifier:(NSString *)identifier encodedContentRuleList:(NSString *) encodedContentRuleList completionHandler:(void (^)(WKContentRuleList *, NSError *))completionHandler
{
String json(encodedContentRuleList);
[encodedContentRuleList release];
Modified: trunk/Source/WebKit/UIProcess/API/Cocoa/WKContentRuleListStorePrivate.h (270413 => 270414)
--- trunk/Source/WebKit/UIProcess/API/Cocoa/WKContentRuleListStorePrivate.h 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Source/WebKit/UIProcess/API/Cocoa/WKContentRuleListStorePrivate.h 2020-12-04 00:01:23 UTC (rev 270414)
@@ -32,8 +32,7 @@
- (void)_invalidateContentRuleListVersionForIdentifier:(NSString *)identifier;
- (void)_getContentRuleListSourceForIdentifier:(NSString *)identifier completionHandler:(void (^)(NSString*))completionHandler;
-// NS_RELEASES_ARGUMENT to keep peak memory usage low.
-- (void)_compileContentRuleListForIdentifier:(NSString *)identifier encodedContentRuleList:(NSString *) NS_RELEASES_ARGUMENT encodedContentRuleList completionHandler:(void (^)(WKContentRuleList *, NSError *))completionHandler;
+- (void)_compileContentRuleListForIdentifier:(NSString *)identifier encodedContentRuleList:(NSString *) encodedContentRuleList completionHandler:(void (^)(WKContentRuleList *, NSError *))completionHandler;
// To maintain compatibility with _WKUserContentExtensionStore
// FIXME: Add something to existing clients of _WKUserContentExtensionStore to migrate files from legacy filenames,
Modified: trunk/Tools/ChangeLog (270413 => 270414)
--- trunk/Tools/ChangeLog 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Tools/ChangeLog 2020-12-04 00:01:23 UTC (rev 270414)
@@ -1,3 +1,19 @@
+2020-12-03 Alex Christensen <[email protected]>
+
+ Serialize NFA to disk before converting it to a DFA when compiling a WKContentRuleList
+ https://bugs.webkit.org/show_bug.cgi?id=219452
+
+ Reviewed by Geoffrey Garen.
+
+ Update syntax of existing tests, which cover behavior quite well.
+
+ * TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp:
+ (TestWebKitAPI::createNFAs):
+ (TestWebKitAPI::TEST_F):
+ * TestWebKitAPI/Tests/WebCore/DFAHelpers.h:
+ (TestWebKitAPI::createNFAs):
+ (TestWebKitAPI::buildDFAFromPatterns):
+
2020-12-03 Jonathan Bedard <[email protected]>
[webkitscmpy] Incorrect identifier on remote SVN branches
Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp (270413 => 270414)
--- trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/ContentExtensions.cpp 2020-12-04 00:01:23 UTC (rev 270414)
@@ -227,11 +227,10 @@
static Vector<ContentExtensions::NFA> createNFAs(ContentExtensions::CombinedURLFilters& combinedURLFilters)
{
Vector<ContentExtensions::NFA> nfas;
-
combinedURLFilters.processNFAs(std::numeric_limits<size_t>::max(), [&](ContentExtensions::NFA&& nfa) {
nfas.append(WTFMove(nfa));
+ return true;
});
-
return nfas;
}
@@ -576,7 +575,7 @@
EXPECT_EQ(1ul, nfas.size());
EXPECT_EQ(12ul, nfas.first().nodes.size());
- ContentExtensions::DFA dfa = ContentExtensions::NFAToDFA::convert(nfas.first());
+ ContentExtensions::DFA dfa = *ContentExtensions::NFAToDFA::convert(WTFMove(nfas.first()));
Vector<ContentExtensions::DFABytecode> bytecode;
ContentExtensions::DFABytecodeCompiler compiler(dfa, bytecode);
compiler.compile();
@@ -602,7 +601,7 @@
EXPECT_EQ(1ul, nfas.size());
EXPECT_EQ(17ul, nfas.first().nodes.size());
- ContentExtensions::DFA dfa = ContentExtensions::NFAToDFA::convert(nfas.first());
+ ContentExtensions::DFA dfa = *ContentExtensions::NFAToDFA::convert(WTFMove(nfas.first()));
Vector<ContentExtensions::DFABytecode> bytecode;
ContentExtensions::DFABytecodeCompiler compiler(dfa, bytecode);
compiler.compile();
@@ -1125,7 +1124,7 @@
EXPECT_EQ(1ul, nfas.size());
EXPECT_EQ(7ul, nfas.first().nodes.size());
- ContentExtensions::DFA dfa = ContentExtensions::NFAToDFA::convert(nfas.first());
+ ContentExtensions::DFA dfa = *ContentExtensions::NFAToDFA::convert(WTFMove(nfas.first()));
Vector<ContentExtensions::DFABytecode> bytecode;
ContentExtensions::DFABytecodeCompiler compiler(dfa, bytecode);
compiler.compile();
@@ -1271,12 +1270,13 @@
Vector<ContentExtensions::NFA> nfas;
combinedURLFilters.processNFAs(std::numeric_limits<size_t>::max(), [&](ContentExtensions::NFA&& nfa) {
nfas.append(WTFMove(nfa));
+ return true;
});
EXPECT_EQ(nfas.size(), 1ull);
Vector<ContentExtensions::DFA> dfas;
- for (auto& nfa : nfas)
- dfas.append(ContentExtensions::NFAToDFA::convert(nfa));
+ for (auto&& nfa : WTFMove(nfas))
+ dfas.append(*ContentExtensions::NFAToDFA::convert(WTFMove(nfa)));
EXPECT_EQ(dfas.size(), 1ull);
Vector<ContentExtensions::DFABytecode> combinedBytecode;
@@ -1685,12 +1685,13 @@
Vector<ContentExtensions::NFA> nfas;
combinedURLFilters.processNFAs(i, [&](ContentExtensions::NFA&& nfa) {
nfas.append(WTFMove(nfa));
+ return true;
});
EXPECT_EQ(nfas.size(), expectedNFACounts[i]);
Vector<ContentExtensions::DFA> dfas;
- for (auto& nfa : nfas)
- dfas.append(ContentExtensions::NFAToDFA::convert(nfa));
+ for (auto& nfa : WTFMove(nfas))
+ dfas.append(*ContentExtensions::NFAToDFA::convert(WTFMove(nfa)));
Vector<ContentExtensions::DFABytecode> combinedBytecode;
for (const auto& dfa : dfas) {
Modified: trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAHelpers.h (270413 => 270414)
--- trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAHelpers.h 2020-12-03 23:54:52 UTC (rev 270413)
+++ trunk/Tools/TestWebKitAPI/Tests/WebCore/DFAHelpers.h 2020-12-04 00:01:23 UTC (rev 270414)
@@ -47,11 +47,10 @@
static Vector<ContentExtensions::NFA> createNFAs(ContentExtensions::CombinedURLFilters& combinedURLFilters)
{
Vector<ContentExtensions::NFA> nfas;
-
combinedURLFilters.processNFAs(std::numeric_limits<size_t>::max(), [&](ContentExtensions::NFA&& nfa) {
nfas.append(WTFMove(nfa));
+ return true;
});
-
return nfas;
}
@@ -63,7 +62,8 @@
for (const char* pattern : patterns)
parser.addPattern(pattern, false, 0);
Vector<ContentExtensions::NFA> nfas = createNFAs(combinedURLFilters);
- return ContentExtensions::NFAToDFA::convert(nfas[0]);
+ EXPECT_EQ(1ul, nfas.size());
+ return *ContentExtensions::NFAToDFA::convert(WTFMove(nfas.first()));
}
} // namespace TestWebKitAPI
