1/*
2 * Copyright (C) 2014, 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 "ContentExtensionsDebugging.h"
31#include <wtf/HashMap.h>
32#include <wtf/Vector.h>
33
34namespace WebCore {
35
36namespace ContentExtensions {
37
38struct DFA;
39
40struct CharRange {
41 signed char first;
42 signed char last;
43 unsigned size() const { return last - first + 1; }
44};
45
46// A DFANode abstract the transition table out of a DFA state. If a state is accepting, the DFANode also have
47// the actions for that state.
48class DFANode {
49public:
50 struct ConstRangeIterator {
51 const DFA& dfa;
52 uint32_t position;
53
54 const ConstRangeIterator& operator*() const { return *this; }
55
56 bool operator==(const ConstRangeIterator& other) const
57 {
58 ASSERT(&dfa == &other.dfa);
59 return position == other.position;
60 }
61 bool operator!=(const ConstRangeIterator& other) const { return !(*this == other); }
62
63 ConstRangeIterator& operator++()
64 {
65 ++position;
66 return *this;
67 }
68
69 const CharRange& range() const;
70 uint32_t target() const;
71
72 char first() const { return range().first; }
73 char last() const { return range().last; }
74 uint32_t data() const { return target(); }
75 };
76
77 struct IterableConstRange {
78 const DFA& dfa;
79 uint32_t rangesStart;
80 uint32_t rangesEnd;
81
82 ConstRangeIterator begin() const { return { dfa, rangesStart }; }
83 ConstRangeIterator end() const { return { dfa, rangesEnd }; }
84 };
85
86 IterableConstRange transitions(const DFA& dfa) const
87 {
88 return IterableConstRange { dfa, m_transitionsStart, m_transitionsStart + m_transitionsLength };
89 }
90
91 struct RangeIterator {
92 DFA& dfa;
93 uint32_t position;
94
95 RangeIterator& operator*() { return *this; }
96
97 bool operator==(const RangeIterator& other) const
98 {
99 ASSERT(&dfa == &other.dfa);
100 return position == other.position;
101 }
102 bool operator!=(const RangeIterator& other) const { return !(*this == other); }
103
104 RangeIterator& operator++()
105 {
106 ++position;
107 return *this;
108 }
109
110 const CharRange& range() const;
111 uint32_t target() const;
112 void resetTarget(uint32_t);
113
114 char first() const { return range().first; }
115 char last() const { return range().last; }
116 uint32_t data() const { return target(); }
117 };
118
119 struct IterableRange {
120 DFA& dfa;
121 uint32_t rangesStart;
122 uint32_t rangesEnd;
123
124 RangeIterator begin() const { return { dfa, rangesStart }; }
125 RangeIterator end() const { return { dfa, rangesEnd }; }
126 };
127
128 IterableRange transitions(DFA& dfa)
129 {
130 return IterableRange { dfa, m_transitionsStart, m_transitionsStart + m_transitionsLength };
131 }
132
133 // FIXME: Stop minimizing killed nodes and add ASSERT(!isKilled()) in many functions here.
134 void kill(DFA&);
135 Vector<uint64_t> actions(const DFA&) const;
136 bool containsTransition(char, const DFA&) const;
137
138 bool isKilled() const { return m_flags & IsKilled; }
139 bool hasActions() const { return !!m_actionsLength; }
140 uint16_t actionsLength() const { return m_actionsLength; }
141 uint32_t actionsStart() const { return m_actionsStart; }
142
143 bool canUseFallbackTransition(const DFA&) const;
144 uint32_t bestFallbackTarget(const DFA&) const;
145
146 void setActions(uint32_t start, uint16_t length)
147 {
148 ASSERT(!m_actionsLength);
149 m_actionsStart = start;
150 m_actionsLength = length;
151 }
152 void setTransitions(uint32_t start, uint16_t length)
153 {
154 ASSERT(!m_transitionsStart);
155 ASSERT(!m_transitionsLength);
156 m_transitionsStart = start;
157 m_transitionsLength = length;
158 }
159
160private:
161 uint32_t m_actionsStart { 0 };
162 uint32_t m_transitionsStart { 0 };
163 uint16_t m_actionsLength { 0 };
164 uint8_t m_transitionsLength { 0 };
165
166 uint8_t m_flags { 0 };
167 const uint8_t IsKilled = 0x01;
168};
169
170COMPILE_ASSERT(sizeof(DFANode) <= 16, Keep the DFANodes small);
171
172} // namespace ContentExtensions
173} // namespace WebCore
174
175#endif // ENABLE(CONTENT_EXTENSIONS)
176