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#if ENABLE(CONTENT_EXTENSIONS)
29
30#include <wtf/Vector.h>
31
32namespace WebCore {
33
34namespace ContentExtensions {
35
36template <typename CharacterType>
37struct ImmutableRange {
38 uint32_t targetStart;
39 uint32_t targetEnd;
40 CharacterType first;
41 CharacterType last;
42};
43
44struct ImmutableNFANode {
45 uint32_t rangesStart { 0 };
46 uint32_t rangesEnd { 0 };
47 uint32_t epsilonTransitionTargetsStart { 0 };
48 uint32_t epsilonTransitionTargetsEnd { 0 };
49 uint32_t actionStart { 0 };
50 uint32_t actionEnd { 0 };
51};
52
53template <typename CharacterType, typename ActionType>
54struct ImmutableNFA {
55 Vector<ImmutableNFANode, 0, ContentExtensionsOverflowHandler> nodes;
56 Vector<ImmutableRange<CharacterType>, 0, ContentExtensionsOverflowHandler> transitions;
57 Vector<uint32_t, 0, ContentExtensionsOverflowHandler> targets;
58 Vector<uint32_t, 0, ContentExtensionsOverflowHandler> epsilonTransitionsTargets;
59 Vector<ActionType, 0, ContentExtensionsOverflowHandler> actions;
60
61 struct ConstTargetIterator {
62 const ImmutableNFA& immutableNFA;
63 uint32_t position;
64
65 const uint32_t& operator*() const { return immutableNFA.targets[position]; }
66 const uint32_t* operator->() const { return &immutableNFA.targets[position]; }
67
68 bool operator==(const ConstTargetIterator& other) const
69 {
70 ASSERT(&immutableNFA == &other.immutableNFA);
71 return position == other.position;
72 }
73 bool operator!=(const ConstTargetIterator& other) const { return !(*this == other); }
74
75 ConstTargetIterator& operator++()
76 {
77 ++position;
78 return *this;
79 }
80 };
81
82 struct IterableConstTargets {
83 const ImmutableNFA& immutableNFA;
84 uint32_t targetStart;
85 uint32_t targetEnd;
86
87 ConstTargetIterator begin() const { return { immutableNFA, targetStart }; }
88 ConstTargetIterator end() const { return { immutableNFA, targetEnd }; }
89 };
90
91 struct ConstRangeIterator {
92 const ImmutableNFA& immutableNFA;
93 uint32_t position;
94
95 bool operator==(const ConstRangeIterator& other) const
96 {
97 ASSERT(&immutableNFA == &other.immutableNFA);
98 return position == other.position;
99 }
100 bool operator!=(const ConstRangeIterator& other) const { return !(*this == other); }
101
102 ConstRangeIterator& operator++()
103 {
104 ++position;
105 return *this;
106 }
107
108 CharacterType first() const
109 {
110 return range().first;
111 }
112
113 CharacterType last() const
114 {
115 return range().last;
116 }
117
118 IterableConstTargets data() const
119 {
120 const ImmutableRange<CharacterType>& range = this->range();
121 return { immutableNFA, range.targetStart, range.targetEnd };
122 };
123
124 private:
125 const ImmutableRange<CharacterType>& range() const
126 {
127 return immutableNFA.transitions[position];
128 }
129 };
130
131 struct IterableConstRange {
132 const ImmutableNFA& immutableNFA;
133 uint32_t rangesStart;
134 uint32_t rangesEnd;
135
136 ConstRangeIterator begin() const { return { immutableNFA, rangesStart }; }
137 ConstRangeIterator end() const { return { immutableNFA, rangesEnd }; }
138
139#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
140 void debugPrint() const
141 {
142 for (const auto& range : *this)
143 WTFLogAlways(" %d-%d", range.first, range.last);
144 }
145#endif
146 };
147
148 IterableConstRange transitionsForNode(uint32_t nodeId) const
149 {
150 const ImmutableNFANode& node = nodes[nodeId];
151 return { *this, node.rangesStart, node.rangesEnd };
152 };
153
154 uint32_t root() const
155 {
156 RELEASE_ASSERT(!nodes.isEmpty());
157 return 0;
158 }
159
160 void finalize()
161 {
162 nodes.shrinkToFit();
163 transitions.shrinkToFit();
164 targets.shrinkToFit();
165 epsilonTransitionsTargets.shrinkToFit();
166 actions.shrinkToFit();
167 }
168
169 size_t memoryUsed() const
170 {
171 return nodes.capacity() * sizeof(ImmutableNFANode)
172 + transitions.capacity() * sizeof(ImmutableRange<CharacterType>)
173 + targets.capacity() * sizeof(uint32_t)
174 + epsilonTransitionsTargets.capacity() * sizeof(uint32_t)
175 + actions.capacity() * sizeof(ActionType);
176 }
177};
178
179} // namespace ContentExtensions
180} // namespace WebCore
181
182#endif // ENABLE(CONTENT_EXTENSIONS)
183