Replace WTF::move with WTFMove
[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 #if ENABLE(CONTENT_EXTENSIONS)
30
31 #include "MutableRangeList.h"
32 #include <wtf/HashMap.h>
33 #include <wtf/HashSet.h>
34
35 namespace WebCore {
36
37 namespace ContentExtensions {
38
39 class DFAMerger {
40     typedef MutableRangeList<char, uint64_t, 128> CombinedTransitionsMutableRangeList;
41
42     enum class WhichDFA {
43         A,
44         B
45     };
46
47     template<WhichDFA whichDFA>
48     struct TargetConverter {
49         uint64_t convert(uint32_t target)
50         {
51             uint64_t value = 0xffffffffffffffff;
52             extend(value, target);
53             return value;
54         }
55
56         void extend(uint64_t& destination, uint32_t target)
57         {
58             setHalfSignature(destination, target);
59         }
60     private:
61         void setHalfSignature(uint64_t& signature, uint32_t value)
62         {
63             unsigned shiftAmount = (whichDFA == WhichDFA::A) ? 32 : 0;
64             uint64_t mask = static_cast<uint64_t>(0xffffffff) << (32 - shiftAmount);
65             signature = (signature & mask) | static_cast<uint64_t>(value) << shiftAmount;
66         }
67     };
68
69 public:
70     DFAMerger(const DFA& a, const DFA& b)
71         : m_dfaA(a)
72         , m_dfaB(b)
73     {
74     }
75
76     DFA merge()
77     {
78         if (!m_nodeMapping.isEmpty())
79             return m_output;
80
81         uint64_t rootSignature = signatureForIndices(m_dfaA.root, m_dfaB.root);
82         getOrCreateCombinedNode(rootSignature);
83
84         CombinedTransitionsMutableRangeList combinedTransitions;
85         while (!m_unprocessedNodes.isEmpty()) {
86             combinedTransitions.clear();
87
88             uint64_t unprocessedNode = m_unprocessedNodes.takeLast();
89
90             uint32_t indexA = extractIndexA(unprocessedNode);
91             if (indexA != invalidNodeIndex) {
92                 const DFANode& nodeA = m_dfaA.nodes[indexA];
93                 auto transitionsA = nodeA.transitions(m_dfaA);
94                 TargetConverter<WhichDFA::A> converterA;
95                 combinedTransitions.extend(transitionsA.begin(), transitionsA.end(), converterA);
96             }
97
98             uint32_t indexB = extractIndexB(unprocessedNode);
99             if (indexB != invalidNodeIndex) {
100                 const DFANode& nodeB = m_dfaB.nodes[indexB];
101                 auto transitionsB = nodeB.transitions(m_dfaB);
102                 TargetConverter<WhichDFA::B> converterB;
103                 combinedTransitions.extend(transitionsB.begin(), transitionsB.end(), converterB);
104             }
105
106             unsigned transitionsStart = m_output.transitionRanges.size();
107             for (const auto& range : combinedTransitions) {
108                 unsigned targetNodeId = getOrCreateCombinedNode(range.data);
109                 m_output.transitionRanges.append({ range.first, range.last });
110                 m_output.transitionDestinations.append(targetNodeId);
111             }
112             unsigned transitionsEnd = m_output.transitionRanges.size();
113             unsigned transitionsLength = transitionsEnd - transitionsStart;
114
115             uint32_t sourceNodeId = m_nodeMapping.get(unprocessedNode);
116             DFANode& dfaSourceNode = m_output.nodes[sourceNodeId];
117             dfaSourceNode.setTransitions(transitionsStart, static_cast<uint8_t>(transitionsLength));
118         }
119         return m_output;
120     }
121
122 private:
123     uint32_t invalidNodeIndex = 0xffffffff;
124
125     static uint64_t signatureForIndices(uint32_t aIndex, uint32_t bIndex)
126     {
127         return static_cast<uint64_t>(aIndex) << 32 | bIndex;
128     }
129
130     static uint32_t extractIndexA(uint64_t signature)
131     {
132         return static_cast<uint32_t>(signature >> 32);
133     }
134
135     static uint32_t extractIndexB(uint64_t signature)
136     {
137         return static_cast<uint32_t>(signature);
138     }
139
140     uint32_t getOrCreateCombinedNode(uint64_t newNodeSignature)
141     {
142         auto addResult = m_nodeMapping.add(newNodeSignature, invalidNodeIndex);
143         if (!addResult.isNewEntry)
144             return addResult.iterator->value;
145
146         m_output.nodes.append(DFANode());
147         uint32_t newNodeIndex = m_output.nodes.size() - 1;
148         addResult.iterator->value = newNodeIndex;
149         m_unprocessedNodes.append(newNodeSignature);
150
151         uint32_t indexA = extractIndexA(newNodeSignature);
152         uint32_t indexB = extractIndexB(newNodeSignature);
153
154         HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> actions;
155         if (indexA != invalidNodeIndex) {
156             const DFANode& node = m_dfaA.nodes[indexA];
157             uint32_t actionsStart = node.actionsStart();
158             uint32_t actionsEnd = actionsStart + node.actionsLength();
159             for (uint32_t i = actionsStart; i < actionsEnd; ++i)
160                 actions.add(m_dfaA.actions[i]);
161         }
162         if (indexB != invalidNodeIndex) {
163             const DFANode& node = m_dfaB.nodes[indexB];
164             uint32_t actionsStart = node.actionsStart();
165             uint32_t actionsEnd = actionsStart + node.actionsLength();
166             for (uint32_t i = actionsStart; i < actionsEnd; ++i)
167                 actions.add(m_dfaB.actions[i]);
168         }
169
170         uint32_t actionsStart = m_output.actions.size();
171         for (uint64_t action : actions)
172             m_output.actions.append(action);
173         uint32_t actionsEnd = m_output.actions.size();
174         uint16_t actionsLength = static_cast<uint16_t>(actionsEnd - actionsStart);
175
176         m_output.nodes.last().setActions(actionsStart, actionsLength);
177         return newNodeIndex;
178     }
179
180     const DFA& m_dfaA;
181     const DFA& m_dfaB;
182     DFA m_output;
183     HashMap<uint64_t, uint32_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> m_nodeMapping;
184     Vector<uint64_t, 0, ContentExtensionsOverflowHandler> m_unprocessedNodes;
185 };
186
187 void DFACombiner::combineDFAs(unsigned minimumSize, std::function<void(DFA&&)> handler)
188 {
189     if (m_dfas.isEmpty())
190         return;
191
192     for (unsigned i = m_dfas.size(); i--;) {
193         if (m_dfas[i].graphSize() > minimumSize) {
194             handler(WTFMove(m_dfas[i]));
195             m_dfas.remove(i);
196         }
197     }
198
199     while (!m_dfas.isEmpty()) {
200         if (m_dfas.size() == 1) {
201             handler(WTFMove(m_dfas.first()));
202             return;
203         }
204
205         DFA a = m_dfas.takeLast();
206         DFA b = m_dfas.takeLast();
207         DFAMerger dfaMerger(a, b);
208         DFA c = dfaMerger.merge();
209
210         if (c.graphSize() > minimumSize || m_dfas.isEmpty()) {
211             // Minimizing is somewhat expensive. We only do it in bulk when we reach the threshold
212             // to reduce the load.
213             c.minimize();
214         }
215
216         if (c.graphSize() > minimumSize)
217             handler(WTFMove(c));
218         else
219             m_dfas.append(c);
220     }
221 }
222
223 }
224
225 } // namespace WebCore
226
227 #endif