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