Refactor ContentExtensionParser
[WebKit-https.git] / Source / WebCore / contentextensions / ImmutableNFA.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 #if ENABLE(CONTENT_EXTENSIONS)
29
30 #include <wtf/Vector.h>
31
32 namespace WebCore {
33
34 namespace ContentExtensions {
35
36 template <typename CharacterType>
37 struct ImmutableRange {
38     uint32_t targetStart;
39     uint32_t targetEnd;
40     CharacterType first;
41     CharacterType last;
42 };
43
44 struct 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
53 template <typename CharacterType, typename ActionType>
54 struct 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)