1 files changed, 227 insertions, 0 deletions
diff --git a/Source/WebCore/contentextensions/DFACombiner.cpp b/Source/WebCore/contentextensions/DFACombiner.cpp
new file mode 100644
index 000000000..513567540
--- /dev/null
+++ b/Source/WebCore/contentextensions/DFACombiner.cpp
@@ -0,0 +1,227 @@
+/*
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "DFACombiner.h"
+
+#if ENABLE(CONTENT_EXTENSIONS)
+
+#include "MutableRangeList.h"
+#include <wtf/HashMap.h>
+#include <wtf/HashSet.h>
+
+namespace WebCore {
+
+namespace ContentExtensions {
+
+class DFAMerger {
+    typedef MutableRangeList<char, uint64_t, 128> CombinedTransitionsMutableRangeList;
+
+    enum class WhichDFA {
+        A,
+        B
+    };
+
+    template<WhichDFA whichDFA>
+    struct TargetConverter {
+        uint64_t convert(uint32_t target)
+        {
+            uint64_t value = 0xffffffffffffffff;
+            extend(value, target);
+            return value;
+        }
+
+        void extend(uint64_t& destination, uint32_t target)
+        {
+            setHalfSignature(destination, target);
+        }
+    private:
+        void setHalfSignature(uint64_t& signature, uint32_t value)
+        {
+            unsigned shiftAmount = (whichDFA == WhichDFA::A) ? 32 : 0;
+            uint64_t mask = static_cast<uint64_t>(0xffffffff) << (32 - shiftAmount);
+            signature = (signature & mask) | static_cast<uint64_t>(value) << shiftAmount;
+        }
+    };
+
+public:
+    DFAMerger(const DFA& a, const DFA& b)
+        : m_dfaA(a)
+        , m_dfaB(b)
+    {
+    }
+
+    DFA merge()
+    {
+        if (!m_nodeMapping.isEmpty())
+            return m_output;
+
+        uint64_t rootSignature = signatureForIndices(m_dfaA.root, m_dfaB.root);
+        getOrCreateCombinedNode(rootSignature);
+
+        CombinedTransitionsMutableRangeList combinedTransitions;
+        while (!m_unprocessedNodes.isEmpty()) {
+            combinedTransitions.clear();
+
+            uint64_t unprocessedNode = m_unprocessedNodes.takeLast();
+
+            uint32_t indexA = extractIndexA(unprocessedNode);
+            if (indexA != invalidNodeIndex) {
+                const DFANode& nodeA = m_dfaA.nodes[indexA];
+                auto transitionsA = nodeA.transitions(m_dfaA);
+                TargetConverter<WhichDFA::A> converterA;
+                combinedTransitions.extend(transitionsA.begin(), transitionsA.end(), converterA);
+            }
+
+            uint32_t indexB = extractIndexB(unprocessedNode);
+            if (indexB != invalidNodeIndex) {
+                const DFANode& nodeB = m_dfaB.nodes[indexB];
+                auto transitionsB = nodeB.transitions(m_dfaB);
+                TargetConverter<WhichDFA::B> converterB;
+                combinedTransitions.extend(transitionsB.begin(), transitionsB.end(), converterB);
+            }
+
+            unsigned transitionsStart = m_output.transitionRanges.size();
+            for (const auto& range : combinedTransitions) {
+                unsigned targetNodeId = getOrCreateCombinedNode(range.data);
+                m_output.transitionRanges.append({ range.first, range.last });
+                m_output.transitionDestinations.append(targetNodeId);
+            }
+            unsigned transitionsEnd = m_output.transitionRanges.size();
+            unsigned transitionsLength = transitionsEnd - transitionsStart;
+
+            uint32_t sourceNodeId = m_nodeMapping.get(unprocessedNode);
+            DFANode& dfaSourceNode = m_output.nodes[sourceNodeId];
+            dfaSourceNode.setTransitions(transitionsStart, static_cast<uint8_t>(transitionsLength));
+        }
+        return m_output;
+    }
+
+private:
+    uint32_t invalidNodeIndex = 0xffffffff;
+
+    static uint64_t signatureForIndices(uint32_t aIndex, uint32_t bIndex)
+    {
+        return static_cast<uint64_t>(aIndex) << 32 | bIndex;
+    }
+
+    static uint32_t extractIndexA(uint64_t signature)
+    {
+        return static_cast<uint32_t>(signature >> 32);
+    }
+
+    static uint32_t extractIndexB(uint64_t signature)
+    {
+        return static_cast<uint32_t>(signature);
+    }
+
+    uint32_t getOrCreateCombinedNode(uint64_t newNodeSignature)
+    {
+        auto addResult = m_nodeMapping.add(newNodeSignature, invalidNodeIndex);
+        if (!addResult.isNewEntry)
+            return addResult.iterator->value;
+
+        m_output.nodes.append(DFANode());
+        uint32_t newNodeIndex = m_output.nodes.size() - 1;
+        addResult.iterator->value = newNodeIndex;
+        m_unprocessedNodes.append(newNodeSignature);
+
+        uint32_t indexA = extractIndexA(newNodeSignature);
+        uint32_t indexB = extractIndexB(newNodeSignature);
+
+        HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> actions;
+        if (indexA != invalidNodeIndex) {
+            const DFANode& node = m_dfaA.nodes[indexA];
+            uint32_t actionsStart = node.actionsStart();
+            uint32_t actionsEnd = actionsStart + node.actionsLength();
+            for (uint32_t i = actionsStart; i < actionsEnd; ++i)
+                actions.add(m_dfaA.actions[i]);
+        }
+        if (indexB != invalidNodeIndex) {
+            const DFANode& node = m_dfaB.nodes[indexB];
+            uint32_t actionsStart = node.actionsStart();
+            uint32_t actionsEnd = actionsStart + node.actionsLength();
+            for (uint32_t i = actionsStart; i < actionsEnd; ++i)
+                actions.add(m_dfaB.actions[i]);
+        }
+
+        uint32_t actionsStart = m_output.actions.size();
+        for (uint64_t action : actions)
+            m_output.actions.append(action);
+        uint32_t actionsEnd = m_output.actions.size();
+        uint16_t actionsLength = static_cast<uint16_t>(actionsEnd - actionsStart);
+
+        m_output.nodes.last().setActions(actionsStart, actionsLength);
+        return newNodeIndex;
+    }
+
+    const DFA& m_dfaA;
+    const DFA& m_dfaB;
+    DFA m_output;
+    HashMap<uint64_t, uint32_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> m_nodeMapping;
+    Vector<uint64_t, 0, ContentExtensionsOverflowHandler> m_unprocessedNodes;
+};
+
+void DFACombiner::combineDFAs(unsigned minimumSize, std::function<void(DFA&&)> handler)
+{
+    if (m_dfas.isEmpty())
+        return;
+
+    for (unsigned i = m_dfas.size(); i--;) {
+        if (m_dfas[i].graphSize() > minimumSize) {
+            handler(WTFMove(m_dfas[i]));
+            m_dfas.remove(i);
+        }
+    }
+
+    while (!m_dfas.isEmpty()) {
+        if (m_dfas.size() == 1) {
+            handler(WTFMove(m_dfas.first()));
+            return;
+        }
+
+        DFA a = m_dfas.takeLast();
+        DFA b = m_dfas.takeLast();
+        DFAMerger dfaMerger(a, b);
+        DFA c = dfaMerger.merge();
+
+        if (c.graphSize() > minimumSize || m_dfas.isEmpty()) {
+            // Minimizing is somewhat expensive. We only do it in bulk when we reach the threshold
+            // to reduce the load.
+            c.minimize();
+        }
+
+        if (c.graphSize() > minimumSize)
+            handler(WTFMove(c));
+        else
+            m_dfas.append(c);
+    }
+}
+
+}
+
+} // namespace WebCore
+
+#endif