[Content Extensions] Add CombinedURLFilters debugging code.
authorachristensen@apple.com <achristensen@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 1 May 2015 17:03:45 +0000 (17:03 +0000)
committerachristensen@apple.com <achristensen@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 1 May 2015 17:03:45 +0000 (17:03 +0000)
https://bugs.webkit.org/show_bug.cgi?id=144491

Reviewed by Daniel Bates.

No change in behavior.

* contentextensions/CombinedURLFilters.cpp:
(WebCore::ContentExtensions::recursiveMemoryUsed):
(WebCore::ContentExtensions::CombinedURLFilters::memoryUsed):
(WebCore::ContentExtensions::prefixTreeVertexToString):
(WebCore::ContentExtensions::recursivePrint):
(WebCore::ContentExtensions::CombinedURLFilters::print):
(WebCore::ContentExtensions::CombinedURLFilters::addPattern):
(WebCore::ContentExtensions::generateNFAForSubtree):
(WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
* contentextensions/CombinedURLFilters.h:
* contentextensions/NFA.cpp:
(WebCore::ContentExtensions::NFA::memoryUsed):
* contentextensions/NFA.h:
* contentextensions/Term.h:
(WebCore::ContentExtensions::quantifierToString):
(WebCore::ContentExtensions::Term::toString):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@183677 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/contentextensions/CombinedURLFilters.cpp
Source/WebCore/contentextensions/CombinedURLFilters.h
Source/WebCore/contentextensions/NFA.cpp
Source/WebCore/contentextensions/NFA.h
Source/WebCore/contentextensions/Term.h

index 6dc161e..11c0cb9 100644 (file)
@@ -1,3 +1,29 @@
+2015-05-01  Alex Christensen  <achristensen@webkit.org>
+
+        [Content Extensions] Add CombinedURLFilters debugging code.
+        https://bugs.webkit.org/show_bug.cgi?id=144491
+
+        Reviewed by Daniel Bates.
+
+        No change in behavior.
+
+        * contentextensions/CombinedURLFilters.cpp:
+        (WebCore::ContentExtensions::recursiveMemoryUsed):
+        (WebCore::ContentExtensions::CombinedURLFilters::memoryUsed):
+        (WebCore::ContentExtensions::prefixTreeVertexToString):
+        (WebCore::ContentExtensions::recursivePrint):
+        (WebCore::ContentExtensions::CombinedURLFilters::print):
+        (WebCore::ContentExtensions::CombinedURLFilters::addPattern):
+        (WebCore::ContentExtensions::generateNFAForSubtree):
+        (WebCore::ContentExtensions::CombinedURLFilters::processNFAs):
+        * contentextensions/CombinedURLFilters.h:
+        * contentextensions/NFA.cpp:
+        (WebCore::ContentExtensions::NFA::memoryUsed):
+        * contentextensions/NFA.h:
+        * contentextensions/Term.h:
+        (WebCore::ContentExtensions::quantifierToString):
+        (WebCore::ContentExtensions::Term::toString):
+
 2015-05-01  Eric Carlson  <eric.carlson@apple.com>
 
         Fix text track language selection logic
index 479d3d7..c0c1401 100644 (file)
 #if ENABLE(CONTENT_EXTENSIONS)
 
 #include "Term.h"
+#include <wtf/DataLog.h>
 #include <wtf/Vector.h>
+#include <wtf/text/CString.h>
 
 namespace WebCore {
 
 namespace ContentExtensions {
 
-typedef Vector<std::pair<Term, std::unique_ptr<PrefixTreeVertex>>, 0, WTF::CrashOnOverflow, 1> PrefixTreeEdges;
+struct PrefixTreeEdge {
+    Term term;
+    std::unique_ptr<PrefixTreeVertex> child;
+};
+    
+typedef Vector<PrefixTreeEdge, 0, WTF::CrashOnOverflow, 1> PrefixTreeEdges;
 
 struct PrefixTreeVertex {
     PrefixTreeEdges edges;
@@ -43,21 +50,63 @@ struct PrefixTreeVertex {
     bool inVariableLengthPrefix { false };
 };
 
-static size_t recursiveMemoryUsed(const std::unique_ptr<PrefixTreeVertex>& node)
+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
+static size_t recursiveMemoryUsed(const PrefixTreeVertex& vertex)
 {
     size_t size = sizeof(PrefixTreeVertex)
-        + node->edges.capacity() * sizeof(std::pair<Term, std::unique_ptr<PrefixTreeVertex>>)
-        + node->finalActions.capacity() * sizeof(uint64_t);
-    for (const auto& child : node->edges)
-        size += recursiveMemoryUsed(child.second);
+        + vertex.edges.capacity() * sizeof(PrefixTreeEdge)
+        + vertex.finalActions.capacity() * sizeof(uint64_t);
+    for (const auto& edge : vertex.edges) {
+        ASSERT(edge.child);
+        size += recursiveMemoryUsed(*edge.child.get());
+    }
     return size;
 }
 
 size_t CombinedURLFilters::memoryUsed() const
 {
-    return recursiveMemoryUsed(m_prefixTreeRoot);
+    ASSERT(m_prefixTreeRoot);
+    return recursiveMemoryUsed(*m_prefixTreeRoot.get());
 }
+#endif
     
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+static String prefixTreeVertexToString(const PrefixTreeVertex& vertex, unsigned depth)
+{
+    StringBuilder builder;
+    while (depth--)
+        builder.append("  ");
+    builder.append("vertex actions: ");
+    for (auto action : vertex.finalActions) {
+        builder.appendNumber(action);
+        builder.append(',');
+    }
+    builder.append('\n');
+    return builder.toString();
+}
+
+static void recursivePrint(const PrefixTreeVertex& vertex, unsigned depth)
+{
+    dataLogF("%s", prefixTreeVertexToString(vertex, depth).utf8().data());
+    for (const auto& edge : vertex.edges) {
+        StringBuilder builder;
+        for (unsigned i = 0; i < depth * 2; ++i)
+            builder.append(' ');
+        builder.append("vertex edge: ");
+        builder.append(edge.term.toString());
+        builder.append('\n');
+        dataLogF("%s", builder.toString().utf8().data());
+        ASSERT(edge.child);
+        recursivePrint(*edge.child.get(), depth + 1);
+    }
+}
+
+void CombinedURLFilters::print() const
+{
+    recursivePrint(*m_prefixTreeRoot.get(), 0);
+}
+#endif
+
 CombinedURLFilters::CombinedURLFilters()
     : m_prefixTreeRoot(std::make_unique<PrefixTreeVertex>())
 {
@@ -90,21 +139,18 @@ void CombinedURLFilters::addPattern(uint64_t actionId, const Vector<Term>& patte
     for (const Term& term : pattern) {
         size_t nextEntryIndex = WTF::notFound;
         for (size_t i = 0; i < lastPrefixTree->edges.size(); ++i) {
-            if (lastPrefixTree->edges[i].first == term) {
+            if (lastPrefixTree->edges[i].term == term) {
                 nextEntryIndex = i;
                 break;
             }
         }
         if (nextEntryIndex != WTF::notFound)
-            lastPrefixTree = lastPrefixTree->edges[nextEntryIndex].second.get();
+            lastPrefixTree = lastPrefixTree->edges[nextEntryIndex].child.get();
         else {
             hasNewTerm = true;
 
-            std::unique_ptr<PrefixTreeVertex> nextPrefixTreeVertex = std::make_unique<PrefixTreeVertex>();
-
-            ASSERT(lastPrefixTree->edges.find(std::make_pair(term, std::make_unique<PrefixTreeVertex>())) == WTF::notFound);
-            lastPrefixTree->edges.append(std::make_pair(term, WTF::move(nextPrefixTreeVertex)));
-            lastPrefixTree = lastPrefixTree->edges.last().second.get();
+            lastPrefixTree->edges.append(PrefixTreeEdge({term, std::make_unique<PrefixTreeVertex>()}));
+            lastPrefixTree = lastPrefixTree->edges.last().child.get();
         }
         prefixTreeVerticesForPattern.append(lastPrefixTree);
     }
@@ -149,13 +195,13 @@ static void generateNFAForSubtree(NFA& nfa, unsigned rootId, const PrefixTreeVer
     while (true) {
     ProcessSubtree:
         for (ActiveNFASubtree& activeSubtree = activeStack.last(); activeSubtree.iterator != activeSubtree.vertex->edges.end(); ++activeSubtree.iterator) {
-            if (activeSubtree.iterator->second->inVariableLengthPrefix)
+            if (activeSubtree.iterator->child->inVariableLengthPrefix)
                 continue;
 
-            const Term& term = activeSubtree.iterator->first;
-            unsigned newEndNodeIndex = term.generateGraph(nfa, activeSubtree.lastNodeIndex, activeSubtree.iterator->second->finalActions);
+            const Term& term = activeSubtree.iterator->term;
+            unsigned newEndNodeIndex = term.generateGraph(nfa, activeSubtree.lastNodeIndex, activeSubtree.iterator->child->finalActions);
 
-            PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->second.get();
+            PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->child.get();
             if (!prefixTreeVertex->edges.isEmpty()) {
                 activeStack.append(ActiveNFASubtree(prefixTreeVertex, prefixTreeVertex->edges.begin(), newEndNodeIndex));
                 goto ProcessSubtree;
@@ -180,7 +226,7 @@ void CombinedURLFilters::processNFAs(std::function<void(NFA&&)> handler) const
 
         // We go depth first into the subtrees with variable prefix. Find the next subtree.
         for (; activeSubtree.iterator != activeSubtree.vertex->edges.end(); ++activeSubtree.iterator) {
-            PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->second.get();
+            PrefixTreeVertex* prefixTreeVertex = activeSubtree.iterator->child.get();
             if (prefixTreeVertex->inVariableLengthPrefix) {
                 activeStack.append(ActiveSubtree({ prefixTreeVertex, prefixTreeVertex->edges.begin() }));
                 goto ProcessSubtree;
@@ -192,7 +238,7 @@ void CombinedURLFilters::processNFAs(std::function<void(NFA&&)> handler) const
         bool needToGenerate = activeSubtree.vertex->edges.isEmpty() && !activeSubtree.vertex->finalActions.isEmpty();
         if (!needToGenerate) {
             for (const auto& edge : activeSubtree.vertex->edges) {
-                if (!edge.second->inVariableLengthPrefix) {
+                if (!edge.child->inVariableLengthPrefix) {
                     needToGenerate = true;
                     break;
                 }
@@ -205,15 +251,14 @@ void CombinedURLFilters::processNFAs(std::function<void(NFA&&)> handler) const
             unsigned prefixEnd = nfa.root();
 
             for (unsigned i = 0; i < activeStack.size() - 1; ++i) {
-                const Term& term = activeStack[i].iterator->first;
-                prefixEnd = term.generateGraph(nfa, prefixEnd, activeStack[i].iterator->second->finalActions);
+                const Term& term = activeStack[i].iterator->term;
+                prefixEnd = term.generateGraph(nfa, prefixEnd, activeStack[i].iterator->child->finalActions);
             }
 
             for (const auto& edge : activeSubtree.vertex->edges) {
-                if (!edge.second->inVariableLengthPrefix) {
-                    const Term& term = edge.first;
-                    unsigned newSubtreeStart = term.generateGraph(nfa, prefixEnd, edge.second->finalActions);
-                    generateNFAForSubtree(nfa, newSubtreeStart, *edge.second);
+                if (!edge.child->inVariableLengthPrefix) {
+                    unsigned newSubtreeStart = edge.term.generateGraph(nfa, prefixEnd, edge.child->finalActions);
+                    generateNFAForSubtree(nfa, newSubtreeStart, *edge.child);
                 }
             }
             
index 2b0847f..e2d071f 100644 (file)
@@ -28,6 +28,7 @@
 
 #if ENABLE(CONTENT_EXTENSIONS)
 
+#include "ContentExtensionsDebugging.h"
 #include "NFA.h"
 #include <wtf/Vector.h>
 
@@ -48,7 +49,12 @@ public:
     void processNFAs(std::function<void(NFA&&)> handler) const;
     void clear();
 
+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
     size_t memoryUsed() const;
+#endif
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+    void print() const;
+#endif
     
 private:
     std::unique_ptr<PrefixTreeVertex> m_prefixTreeRoot;
index 4bfc837..b301884 100644 (file)
@@ -47,6 +47,7 @@ unsigned NFA::createNode()
     return nextId;
 }
 
+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
 size_t NFA::memoryUsed() const
 {
     size_t size = sizeof(NFA);
@@ -56,10 +57,11 @@ size_t NFA::memoryUsed() const
         size += sizeof(node)
             + node.transitions.capacity() * sizeof(std::pair<uint16_t, NFANodeIndexSet>)
             + node.transitionsOnAnyCharacter.capacity() * sizeof(unsigned)
-            + node.finalRuleIds.size() * sizeof(uint64_t);
+            + node.finalRuleIds.capacity() * sizeof(uint64_t);
     }
     return size;
 }
+#endif
 
 void NFA::addTransition(unsigned from, unsigned to, char character)
 {
index f8e4941..4e4c228 100644 (file)
@@ -61,7 +61,9 @@ public:
 #else
     void addRuleId(unsigned, uint64_t) { }
 #endif
+#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
     size_t memoryUsed() const;
+#endif
 
 private:
     friend class NFAToDFA;
index 8bb16a7..8d2246a 100644 (file)
 
 #if ENABLE(CONTENT_EXTENSIONS)
 
+#include "ContentExtensionsDebugging.h"
 #include "NFA.h"
 #include <unicode/utypes.h>
 #include <wtf/ASCIICType.h>
 #include <wtf/HashMap.h>
 #include <wtf/Vector.h>
+#include <wtf/text/StringBuilder.h>
+#include <wtf/text/WTFString.h>
 
 namespace WebCore {
 
@@ -106,6 +109,10 @@ public:
     bool isEmptyValue() const;
     bool isDeletedValue() const;
 
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+    String toString() const;
+#endif
+    
 private:
     // This is exact for character sets but conservative for groups.
     // The return value can be false for a group equivalent to a universal transition.
@@ -203,6 +210,59 @@ private:
     } m_atomData;
 };
 
+#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
+inline String quantifierToString(AtomQuantifier quantifier)
+{
+    switch (quantifier) {
+    case AtomQuantifier::One:
+        return "";
+    case AtomQuantifier::ZeroOrOne:
+        return "?";
+    case AtomQuantifier::ZeroOrMore:
+        return "*";
+    case AtomQuantifier::OneOrMore:
+        return "+";
+    }
+}
+    
+inline String Term::toString() const
+{
+    switch (m_termType) {
+    case TermType::Empty:
+        return "(Empty)";
+    case TermType::Deleted:
+        return "(Deleted)";
+    case TermType::CharacterSet: {
+        StringBuilder builder;
+        builder.append('[');
+        for (UChar c = 0; c < 128; c++) {
+            if (m_atomData.characterSet.get(c)) {
+                if (isASCIIPrintable(c) && !isASCIISpace(c))
+                    builder.append(c);
+                else {
+                    builder.append('\\');
+                    builder.append('u');
+                    builder.appendNumber(c);
+                }
+            }
+        }
+        builder.append(']');
+        builder.append(quantifierToString(m_quantifier));
+        return builder.toString();
+    }
+    case TermType::Group: {
+        StringBuilder builder;
+        builder.append('(');
+        for (const Term& term : m_atomData.group.terms)
+            builder.append(term.toString());
+        builder.append(')');
+        builder.append(quantifierToString(m_quantifier));
+        return builder.toString();
+    }
+    }
+}
+#endif
+    
 struct TermHash {
     static unsigned hash(const Term& term) { return term.hash(); }
     static bool equal(const Term& a, const Term& b) { return a == b; }