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#pragma once
27
28#include "ImmutableNFA.h"
29#include "MutableRangeList.h"
30#include <wtf/HashSet.h>
31
32#if ENABLE(CONTENT_EXTENSIONS)
33
34namespace WebCore {
35
36namespace ContentExtensions {
37
38// A ImmutableNFANodeBuilder let you build a NFA node by adding states and linking with other nodes.
39// Whe a builder is destructed, all its properties are finalized into the NFA. Using the NA with a live
40// builder results in undefined behaviors.
41template <typename CharacterType, typename ActionType>
42class ImmutableNFANodeBuilder {
43 typedef ImmutableNFA<CharacterType, ActionType> TypedImmutableNFA;
44 typedef HashSet<uint32_t, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t>> TargetSet;
45public:
46 ImmutableNFANodeBuilder() { }
47
48 ImmutableNFANodeBuilder(TypedImmutableNFA& immutableNFA)
49 : m_immutableNFA(&immutableNFA)
50 , m_finalized(false)
51 {
52 m_nodeId = m_immutableNFA->nodes.size();
53 m_immutableNFA->nodes.append(ImmutableNFANode());
54 }
55
56 ImmutableNFANodeBuilder(ImmutableNFANodeBuilder&& other)
57 : m_immutableNFA(other.m_immutableNFA)
58 , m_ranges(WTFMove(other.m_ranges))
59 , m_epsilonTransitionTargets(WTFMove(other.m_epsilonTransitionTargets))
60 , m_actions(WTFMove(other.m_actions))
61 , m_nodeId(other.m_nodeId)
62 , m_finalized(other.m_finalized)
63 {
64 other.m_immutableNFA = nullptr;
65 other.m_finalized = true;
66 }
67
68 ~ImmutableNFANodeBuilder()
69 {
70 if (!m_finalized)
71 finalize();
72 }
73
74 bool isValid() const
75 {
76 return !!m_immutableNFA;
77 }
78
79 uint32_t nodeId() const
80 {
81 ASSERT(isValid());
82 return m_nodeId;
83 }
84
85 struct TrivialRange {
86 CharacterType first;
87 CharacterType last;
88 };
89
90 struct FakeRangeIterator {
91 CharacterType first() const { return range.first; }
92 CharacterType last() const { return range.last; }
93 uint32_t data() const { return targetId; }
94 bool operator==(const FakeRangeIterator& other)
95 {
96 return this->isEnd == other.isEnd;
97 }
98 bool operator!=(const FakeRangeIterator& other) { return !(*this == other); }
99 FakeRangeIterator operator++()
100 {
101 isEnd = true;
102 return *this;
103 }
104
105 TrivialRange range;
106 uint32_t targetId;
107 bool isEnd;
108 };
109
110 void addTransition(CharacterType first, CharacterType last, uint32_t targetNodeId)
111 {
112 ASSERT(!m_finalized);
113 ASSERT(m_immutableNFA);
114
115 struct Converter {
116 TargetSet convert(uint32_t target)
117 {
118 return TargetSet({ target });
119 }
120 void extend(TargetSet& existingTargets, uint32_t target)
121 {
122 existingTargets.add(target);
123 }
124 };
125
126 Converter converter;
127 m_ranges.extend(FakeRangeIterator { { first, last }, targetNodeId, false }, FakeRangeIterator { { 0, 0 }, targetNodeId, true }, converter);
128 }
129
130 void addEpsilonTransition(const ImmutableNFANodeBuilder& target)
131 {
132 ASSERT(m_immutableNFA == target.m_immutableNFA);
133 addEpsilonTransition(target.m_nodeId);
134 }
135
136 void addEpsilonTransition(uint32_t targetNodeId)
137 {
138 ASSERT(!m_finalized);
139 ASSERT(m_immutableNFA);
140 m_epsilonTransitionTargets.add(targetNodeId);
141 }
142
143 template<typename ActionIterator>
144 void setActions(ActionIterator begin, ActionIterator end)
145 {
146 ASSERT(!m_finalized);
147 ASSERT(m_immutableNFA);
148
149 m_actions.add(begin, end);
150 }
151
152 ImmutableNFANodeBuilder& operator=(ImmutableNFANodeBuilder&& other)
153 {
154 if (!m_finalized)
155 finalize();
156
157 m_immutableNFA = other.m_immutableNFA;
158 m_ranges = WTFMove(other.m_ranges);
159 m_epsilonTransitionTargets = WTFMove(other.m_epsilonTransitionTargets);
160 m_actions = WTFMove(other.m_actions);
161 m_nodeId = other.m_nodeId;
162 m_finalized = other.m_finalized;
163
164 other.m_immutableNFA = nullptr;
165 other.m_finalized = true;
166 return *this;
167 }
168
169private:
170 void finalize()
171 {
172 ASSERT_WITH_MESSAGE(!m_finalized, "The API contract is that the builder can only be finalized once.");
173 m_finalized = true;
174 ImmutableNFANode& immutableNFANode = m_immutableNFA->nodes[m_nodeId];
175 sinkActions(immutableNFANode);
176 sinkEpsilonTransitions(immutableNFANode);
177 sinkTransitions(immutableNFANode);
178 }
179
180 void sinkActions(ImmutableNFANode& immutableNFANode)
181 {
182 unsigned actionStart = m_immutableNFA->actions.size();
183 for (const ActionType& action : m_actions)
184 m_immutableNFA->actions.append(action);
185 unsigned actionEnd = m_immutableNFA->actions.size();
186 immutableNFANode.actionStart = actionStart;
187 immutableNFANode.actionEnd = actionEnd;
188 }
189
190 void sinkTransitions(ImmutableNFANode& immutableNFANode)
191 {
192 unsigned transitionsStart = m_immutableNFA->transitions.size();
193 for (const auto& range : m_ranges) {
194 unsigned targetsStart = m_immutableNFA->targets.size();
195 for (uint32_t target : range.data)
196 m_immutableNFA->targets.append(target);
197 unsigned targetsEnd = m_immutableNFA->targets.size();
198
199 m_immutableNFA->transitions.append(ImmutableRange<CharacterType> { targetsStart, targetsEnd, range.first, range.last });
200 }
201 unsigned transitionsEnd = m_immutableNFA->transitions.size();
202
203 immutableNFANode.rangesStart = transitionsStart;
204 immutableNFANode.rangesEnd = transitionsEnd;
205 }
206
207 void sinkEpsilonTransitions(ImmutableNFANode& immutableNFANode)
208 {
209 unsigned start = m_immutableNFA->epsilonTransitionsTargets.size();
210 for (uint32_t target : m_epsilonTransitionTargets)
211 m_immutableNFA->epsilonTransitionsTargets.append(target);
212 unsigned end = m_immutableNFA->epsilonTransitionsTargets.size();
213
214 immutableNFANode.epsilonTransitionTargetsStart = start;
215 immutableNFANode.epsilonTransitionTargetsEnd = end;
216 }
217
218 TypedImmutableNFA* m_immutableNFA { nullptr };
219 MutableRangeList<CharacterType, TargetSet> m_ranges;
220 TargetSet m_epsilonTransitionTargets;
221 HashSet<ActionType, WTF::IntHash<ActionType>, WTF::UnsignedWithZeroKeyHashTraits<ActionType>> m_actions;
222 uint32_t m_nodeId;
223 bool m_finalized { true };
224};
225
226} // namespace ContentExtensions
227} // namespace WebCore
228
229#endif // ENABLE(CONTENT_EXTENSIONS)
230