Merge TrivialAtom and CharacterSet into a Term abstraction, prepare Term for composition
[WebKit-https.git] / Source / WebCore / contentextensions / NFA.cpp
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 #include "config.h"
27 #include "NFA.h"
28
29 #if ENABLE(CONTENT_EXTENSIONS)
30
31 #include <wtf/DataLog.h>
32 #include <wtf/HashSet.h>
33
34 namespace WebCore {
35
36 namespace ContentExtensions {
37
38 NFA::NFA()
39     : m_root(createNode())
40 {
41 }
42
43 unsigned NFA::createNode()
44 {
45     unsigned nextId = m_nodes.size();
46     m_nodes.append(NFANode());
47     return nextId;
48 }
49
50 void NFA::addTransition(unsigned from, unsigned to, char character)
51 {
52     ASSERT(from < m_nodes.size());
53     ASSERT(to < m_nodes.size());
54     ASSERT(character);
55
56     NFANode& fromNode = m_nodes[from];
57     if (fromNode.transitionsOnAnyCharacter.contains(to))
58         return;
59
60     auto addResult = m_nodes[from].transitions.add(character, HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>());
61     addResult.iterator->value.add(to);
62 }
63
64 void NFA::addEpsilonTransition(unsigned from, unsigned to)
65 {
66     ASSERT(from < m_nodes.size());
67     ASSERT(to < m_nodes.size());
68
69     auto addResult = m_nodes[from].transitions.add(epsilonTransitionCharacter, HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>());
70     addResult.iterator->value.add(to);
71 }
72
73 void NFA::addTransitionsOnAnyCharacter(unsigned from, unsigned to)
74 {
75     ASSERT(from < m_nodes.size());
76     ASSERT(to < m_nodes.size());
77
78     NFANode& fromNode = m_nodes[from];
79     fromNode.transitionsOnAnyCharacter.add(to);
80
81     for (auto transitionSlot : fromNode.transitions)
82         transitionSlot.value.remove(to);
83 }
84
85 void NFA::setFinal(unsigned node, uint64_t ruleId)
86 {
87     ASSERT(!m_nodes[node].finalRuleIds.contains(ruleId));
88     m_nodes[node].finalRuleIds.append(ruleId);
89 }
90
91 unsigned NFA::graphSize() const
92 {
93     return m_nodes.size();
94 }
95
96 void NFA::restoreToGraphSize(unsigned size)
97 {
98     ASSERT(size >= 1);
99     ASSERT(size <= graphSize());
100
101     m_nodes.shrink(size);
102 }
103
104 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
105
106 void NFA::addRuleId(unsigned node, uint64_t ruleId)
107 {
108     if (!m_nodes[node].ruleIds.contains(ruleId))
109         m_nodes[node].ruleIds.append(ruleId);
110 }
111
112 static void printRange(bool firstRange, uint16_t rangeStart, uint16_t rangeEnd, uint16_t epsilonTransitionCharacter)
113 {
114     if (!firstRange)
115         dataLogF(", ");
116     if (rangeStart == rangeEnd) {
117         if (rangeStart == epsilonTransitionCharacter)
118             dataLogF("ɛ");
119         else if (rangeStart == '"' || rangeStart == '\\')
120             dataLogF("\\%c", rangeStart);
121         else if (rangeStart >= '!' && rangeStart <= '~')
122             dataLogF("%c", rangeStart);
123         else
124             dataLogF("\\\\%d", rangeStart);
125     } else {
126         if (rangeStart == 1 && rangeEnd == 127)
127             dataLogF("[any input]");
128         else
129             dataLogF("\\\\%d-\\\\%d", rangeStart, rangeEnd);
130     }
131 }
132
133 static void printTransitions(const Vector<NFANode>& graph, unsigned sourceNode, uint16_t epsilonTransitionCharacter)
134 {
135     const NFANode& node = graph[sourceNode];
136     const HashMap<uint16_t, HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>>& transitions = node.transitions;
137
138     HashMap<unsigned, HashSet<uint16_t>, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> transitionsPerTarget;
139
140     for (const auto& transition : transitions) {
141         for (unsigned targetNode : transition.value) {
142             transitionsPerTarget.add(targetNode, HashSet<uint16_t>());
143             transitionsPerTarget.find(targetNode)->value.add(transition.key);
144         }
145     }
146
147     for (const auto& transitionPerTarget : transitionsPerTarget) {
148         dataLogF("        %d -> %d [label=\"", sourceNode, transitionPerTarget.key);
149
150         Vector<uint16_t> incommingCharacters;
151         copyToVector(transitionPerTarget.value, incommingCharacters);
152         std::sort(incommingCharacters.begin(), incommingCharacters.end());
153
154         uint16_t rangeStart = incommingCharacters.first();
155         uint16_t rangeEnd = rangeStart;
156         bool first = true;
157         for (unsigned sortedTransitionIndex = 1; sortedTransitionIndex < incommingCharacters.size(); ++sortedTransitionIndex) {
158             uint16_t nextChar = incommingCharacters[sortedTransitionIndex];
159             if (nextChar == rangeEnd+1) {
160                 rangeEnd = nextChar;
161                 continue;
162             }
163             printRange(first, rangeStart, rangeEnd, epsilonTransitionCharacter);
164             rangeStart = rangeEnd = nextChar;
165             first = false;
166         }
167         printRange(first, rangeStart, rangeEnd, epsilonTransitionCharacter);
168
169         dataLogF("\"];\n");
170     }
171
172     for (unsigned targetOnAnyCharacter : node.transitionsOnAnyCharacter)
173         dataLogF("        %d -> %d [label=\"[any input]\"];\n", sourceNode, targetOnAnyCharacter);
174 }
175
176 void NFA::debugPrintDot() const
177 {
178     dataLogF("digraph NFA_Transitions {\n");
179     dataLogF("    rankdir=LR;\n");
180     dataLogF("    node [shape=circle];\n");
181     dataLogF("    {\n");
182     for (unsigned i = 0; i < m_nodes.size(); ++i) {
183         dataLogF("         %d [label=<Node %d", i, i);
184
185         const Vector<uint64_t>& originalRules = m_nodes[i].ruleIds;
186         if (!originalRules.isEmpty()) {
187             dataLogF("<BR/>(Rules: ");
188             for (unsigned ruleIndex = 0; ruleIndex < originalRules.size(); ++ruleIndex) {
189                 if (ruleIndex)
190                     dataLogF(", ");
191                 dataLogF("%llu", originalRules[ruleIndex]);
192             }
193             dataLogF(")");
194         }
195
196         const Vector<uint64_t>& finalRules = m_nodes[i].finalRuleIds;
197         if (!finalRules.isEmpty()) {
198             dataLogF("<BR/>(Final: ");
199             for (unsigned ruleIndex = 0; ruleIndex < finalRules.size(); ++ruleIndex) {
200                 if (ruleIndex)
201                     dataLogF(", ");
202                 dataLogF("%llu", finalRules[ruleIndex]);
203             }
204             dataLogF(")");
205         }
206
207         dataLogF(">]");
208
209         if (!finalRules.isEmpty())
210             dataLogF(" [shape=doublecircle]");
211
212         dataLogF(";\n");
213     }
214     dataLogF("    }\n");
215
216     dataLogF("    {\n");
217     for (unsigned i = 0; i < m_nodes.size(); ++i)
218         printTransitions(m_nodes, i, epsilonTransitionCharacter);
219     dataLogF("    }\n");
220     dataLogF("}\n");
221 }
222 #endif
223
224 } // namespace ContentExtensions
225
226 } // namespace WebCore
227
228 #endif // ENABLE(CONTENT_EXTENSIONS)