Unreviewed, fix -Wmisleading-indentation warning introduced in r246764
[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 #pragma once
27
28 #include "ImmutableNFA.h"
29 #include "MutableRangeList.h"
30 #include <wtf/HashSet.h>
31
32 #if ENABLE(CONTENT_EXTENSIONS)
33
34 namespace WebCore {
35
36 namespace 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.
41 template <typename CharacterType, typename ActionType>
42 class ImmutableNFANodeBuilder {
43     typedef ImmutableNFA<CharacterType, ActionType> TypedImmutableNFA;
44     typedef HashSet<uint32_t, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t>> TargetSet;
45 public:
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
169 private:
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)