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
35namespace WebCore {
36
37namespace ContentExtensions {
38
39class DFAMerger {
40 typedef MutableRangeList<signed 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
69public:
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
122private:
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
187void DFACombiner::combineDFAs(unsigned minimumSize, const WTF::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
228