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