The last 2 merged DFAs are not minimized by DFACombiner
[WebKit-https.git] / Source / WebCore / contentextensions / DFACombiner.cpp
1 /*
2  * Copyright (C) 2015 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "DFACombiner.h"
28
29 #include <wtf/HashMap.h>
30 #include <wtf/HashSet.h>
31
32 namespace WebCore {
33
34 namespace ContentExtensions {
35
36 class DFAMerger {
37 public:
38     DFAMerger(const DFA& a, const DFA& b)
39         : m_dfaA(a)
40         , m_dfaB(b)
41     {
42     }
43
44     DFA merge()
45     {
46         if (!m_nodeMapping.isEmpty())
47             return m_output;
48
49         uint64_t rootSignature = signatureForIndices(m_dfaA.root, m_dfaB.root);
50         getOrCreateCombinedNode(rootSignature);
51
52         while (!m_unprocessedNodes.isEmpty()) {
53             memset(m_transitionTargets, 0xff, sizeof(m_transitionTargets));
54
55             uint64_t unprocessedNode = m_unprocessedNodes.takeLast();
56
57             // We cannot cache the source node itself since we modify the machine. We only manipulate the IDs.
58             uint32_t sourceNodeId = m_nodeMapping.get(unprocessedNode);
59
60             // Populate the unique transitions.
61             uint32_t indexA = extractIndexA(unprocessedNode);
62             if (indexA != invalidNodeIndex)
63                 populateTransitions<WhichDFA::A>(indexA);
64
65             uint32_t indexB = extractIndexB(unprocessedNode);
66             if (indexB != invalidNodeIndex)
67                 populateTransitions<WhichDFA::B>(indexB);
68
69             // Spread the fallback transitions over the unique transitions and keep a reference to the fallback transition.
70             uint64_t fallbackTransitionSignature = signatureForIndices(invalidNodeIndex, invalidNodeIndex);
71             if (indexA != invalidNodeIndex)
72                 populateFromFallbackTransitions<WhichDFA::A>(indexA, fallbackTransitionSignature);
73             if (indexB != invalidNodeIndex)
74                 populateFromFallbackTransitions<WhichDFA::B>(indexB, fallbackTransitionSignature);
75
76             createTransitions(sourceNodeId);
77             createFallbackTransitionIfNeeded(sourceNodeId, fallbackTransitionSignature);
78         }
79         return m_output;
80     }
81
82 private:
83     uint32_t invalidNodeIndex = 0xffffffff;
84
85     enum class WhichDFA {
86         A,
87         B
88     };
89
90     static uint64_t signatureForIndices(uint32_t aIndex, uint32_t bIndex)
91     {
92         return static_cast<uint64_t>(aIndex) << 32 | bIndex;
93     }
94
95     static uint32_t extractIndexA(uint64_t signature)
96     {
97         return static_cast<uint32_t>(signature >> 32);
98     }
99
100     static uint32_t extractIndexB(uint64_t signature)
101     {
102         return static_cast<uint32_t>(signature);
103     }
104
105     uint32_t getOrCreateCombinedNode(uint64_t newNodeSignature)
106     {
107         auto addResult = m_nodeMapping.add(newNodeSignature, invalidNodeIndex);
108         if (!addResult.isNewEntry)
109             return addResult.iterator->value;
110
111         m_output.nodes.append(DFANode());
112         uint32_t newNodeIndex = m_output.nodes.size() - 1;
113         addResult.iterator->value = newNodeIndex;
114         m_unprocessedNodes.append(newNodeSignature);
115
116         uint32_t indexA = extractIndexA(newNodeSignature);
117         uint32_t indexB = extractIndexB(newNodeSignature);
118
119         HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> actions;
120         if (indexA != invalidNodeIndex) {
121             const DFANode& node = m_dfaA.nodes[indexA];
122             uint32_t actionsStart = node.actionsStart();
123             uint32_t actionsEnd = actionsStart + node.actionsLength();
124             for (uint32_t i = actionsStart; i < actionsEnd; ++i)
125             actions.add(m_dfaA.actions[i]);
126         }
127         if (indexB != invalidNodeIndex) {
128             const DFANode& node = m_dfaB.nodes[indexB];
129             uint32_t actionsStart = node.actionsStart();
130             uint32_t actionsEnd = actionsStart + node.actionsLength();
131             for (uint32_t i = actionsStart; i < actionsEnd; ++i)
132             actions.add(m_dfaB.actions[i]);
133         }
134
135         uint32_t actionsStart = m_output.actions.size();
136         for (uint64_t action : actions)
137             m_output.actions.append(action);
138         uint32_t actionsEnd = m_output.actions.size();
139         uint16_t actionsLength = static_cast<uint16_t>(actionsEnd - actionsStart);
140
141         m_output.nodes.last().setActions(actionsStart, actionsLength);
142         return newNodeIndex;
143     }
144
145     template<WhichDFA whichDFA>
146     void setHalfSignature(uint64_t& signature, uint32_t value)
147     {
148         unsigned shiftAmount = (whichDFA == WhichDFA::A) ? 32 : 0;
149         uint64_t mask = static_cast<uint64_t>(0xffffffff) << (32 - shiftAmount);
150         signature = (signature & mask) | static_cast<uint64_t>(value) << shiftAmount;
151     }
152
153     template<WhichDFA whichDFA>
154     void populateTransitions(uint32_t nodeIndex)
155     {
156         const DFA& dfa = (whichDFA == WhichDFA::A) ? m_dfaA : m_dfaB;
157         const DFANode& node = dfa.nodes[nodeIndex];
158         uint32_t transitionsStart = node.transitionsStart();
159         uint32_t transitionsEnd = transitionsStart + node.transitionsLength();
160
161         // Extract transitions.
162         for (uint32_t transitionIndex = transitionsStart; transitionIndex < transitionsEnd; ++transitionIndex) {
163             uint8_t transitionCharacter = dfa.transitionCharacters[transitionIndex];
164             RELEASE_ASSERT(transitionCharacter < WTF_ARRAY_LENGTH(m_transitionTargets));
165
166             uint32_t transitionDestination = dfa.transitionDestinations[transitionIndex];
167             setHalfSignature<whichDFA>(m_transitionTargets[transitionCharacter], transitionDestination);
168         }
169     }
170
171     template<WhichDFA whichDFA>
172     void populateFromFallbackTransitions(uint32_t nodeIndex, uint64_t& fallbackTransitionSignature)
173     {
174         const DFA& dfa = (whichDFA == WhichDFA::A) ? m_dfaA : m_dfaB;
175         const DFANode& node = dfa.nodes[nodeIndex];
176         if (!node.hasFallbackTransition())
177             return;
178
179         uint32_t fallbackTarget = node.fallbackTransitionDestination(dfa);
180         setHalfSignature<whichDFA>(fallbackTransitionSignature, fallbackTarget);
181
182         // Spread the fallback over transitions where the other has something and we don't.
183         for (unsigned i = 0; i < WTF_ARRAY_LENGTH(m_transitionTargets); ++i) {
184             uint64_t& targetSignature = m_transitionTargets[i];
185
186             uint32_t otherTarget = (whichDFA == WhichDFA::A) ? extractIndexB(targetSignature) : extractIndexA(targetSignature);
187             uint32_t selfTarget = (whichDFA == WhichDFA::A) ? extractIndexA(targetSignature) : extractIndexB(targetSignature);
188
189             if (otherTarget != invalidNodeIndex && selfTarget == invalidNodeIndex)
190                 setHalfSignature<whichDFA>(targetSignature, fallbackTarget);
191         }
192     }
193
194     void createTransitions(uint32_t sourceNodeId)
195     {
196         // Create transitions out of the source node, creating new nodes as needed.
197         uint32_t transitionsStart = m_output.transitionCharacters.size();
198         for (uint8_t i = 0; i < WTF_ARRAY_LENGTH(m_transitionTargets); ++i) {
199             uint64_t signature = m_transitionTargets[i];
200             if (signature == signatureForIndices(invalidNodeIndex, invalidNodeIndex))
201                 continue;
202             uint32_t nodeId = getOrCreateCombinedNode(signature);
203             m_output.transitionCharacters.append(i);
204             m_output.transitionDestinations.append(nodeId);
205         }
206         uint32_t transitionsEnd = m_output.transitionCharacters.size();
207         uint8_t transitionsLength = static_cast<uint8_t>(transitionsEnd - transitionsStart);
208
209         m_output.nodes[sourceNodeId].setTransitions(transitionsStart, transitionsLength);
210     }
211
212     void createFallbackTransitionIfNeeded(uint32_t sourceNodeId, uint64_t fallbackTransitionSignature)
213     {
214         if (fallbackTransitionSignature != signatureForIndices(invalidNodeIndex, invalidNodeIndex)) {
215             uint32_t nodeId = getOrCreateCombinedNode(fallbackTransitionSignature);
216             m_output.nodes[sourceNodeId].addFallbackTransition(m_output, nodeId);
217         }
218     }
219
220     const DFA& m_dfaA;
221     const DFA& m_dfaB;
222     DFA m_output;
223     HashMap<uint64_t, uint32_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> m_nodeMapping;
224     Vector<uint64_t> m_unprocessedNodes;
225     uint64_t m_transitionTargets[128];
226 };
227
228 void DFACombiner::combineDFAs(unsigned minimumSize, std::function<void(DFA&&)> handler)
229 {
230     if (m_dfas.isEmpty())
231         return;
232
233     for (unsigned i = m_dfas.size(); i--;) {
234         if (m_dfas[i].graphSize() > minimumSize) {
235             handler(WTF::move(m_dfas[i]));
236             m_dfas.remove(i);
237         }
238     }
239
240     while (!m_dfas.isEmpty()) {
241         if (m_dfas.size() == 1) {
242             handler(WTF::move(m_dfas.first()));
243             return;
244         }
245
246         DFA a = m_dfas.takeLast();
247         DFA b = m_dfas.takeLast();
248         DFAMerger dfaMerger(a, b);
249         DFA c = dfaMerger.merge();
250
251         if (c.graphSize() > minimumSize || m_dfas.isEmpty()) {
252             // Minimizing is somewhat expensive. We only do it in bulk when we reach the threshold
253             // to reduce the load.
254             c.minimize();
255         }
256
257         if (c.graphSize() > minimumSize)
258             handler(WTF::move(c));
259         else
260             m_dfas.append(c);
261     }
262 }
263
264 }
265
266 } // namespace WebCore