4bfc83772d8048dfb8961e30dedd9ea7db63ed28
[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 size_t NFA::memoryUsed() const
51 {
52     size_t size = sizeof(NFA);
53     for (const NFANode& node : m_nodes) {
54         for (const auto& transition : node.transitions)
55             size += transition.value.capacity() * sizeof(unsigned);
56         size += sizeof(node)
57             + node.transitions.capacity() * sizeof(std::pair<uint16_t, NFANodeIndexSet>)
58             + node.transitionsOnAnyCharacter.capacity() * sizeof(unsigned)
59             + node.finalRuleIds.size() * sizeof(uint64_t);
60     }
61     return size;
62 }
63
64 void NFA::addTransition(unsigned from, unsigned to, char character)
65 {
66     ASSERT(from < m_nodes.size());
67     ASSERT(to < m_nodes.size());
68
69     NFANode& fromNode = m_nodes[from];
70     if (fromNode.transitionsOnAnyCharacter.contains(to))
71         return;
72
73     auto addResult = m_nodes[from].transitions.add(character, NFANodeIndexSet());
74     addResult.iterator->value.add(to);
75 }
76
77 void NFA::addEpsilonTransition(unsigned from, unsigned to)
78 {
79     ASSERT(from < m_nodes.size());
80     ASSERT(to < m_nodes.size());
81
82     auto addResult = m_nodes[from].transitions.add(epsilonTransitionCharacter, NFANodeIndexSet());
83     addResult.iterator->value.add(to);
84 }
85
86 void NFA::addTransitionsOnAnyCharacter(unsigned from, unsigned to)
87 {
88     ASSERT(from < m_nodes.size());
89     ASSERT(to < m_nodes.size());
90
91     NFANode& fromNode = m_nodes[from];
92     fromNode.transitionsOnAnyCharacter.add(to);
93
94     for (auto transitionSlot : fromNode.transitions)
95         transitionSlot.value.remove(to);
96 }
97
98 void NFA::setActions(unsigned node, const ActionList& actions)
99 {
100     ASSERT_WITH_MESSAGE(m_nodes[node].finalRuleIds.isEmpty(), "The final state should only be defined once.");
101     copyToVector(actions, m_nodes[node].finalRuleIds);
102 }
103
104 unsigned NFA::graphSize() const
105 {
106     return m_nodes.size();
107 }
108
109 void NFA::restoreToGraphSize(unsigned size)
110 {
111     ASSERT(size >= 1);
112     ASSERT(size <= graphSize());
113
114     m_nodes.shrink(size);
115 }
116
117 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
118 static void printRange(bool firstRange, uint16_t rangeStart, uint16_t rangeEnd, uint16_t epsilonTransitionCharacter)
119 {
120     if (!firstRange)
121         dataLogF(", ");
122     if (rangeStart == rangeEnd) {
123         if (rangeStart == epsilonTransitionCharacter)
124             dataLogF("ɛ");
125         else if (rangeStart == '"' || rangeStart == '\\')
126             dataLogF("\\%c", rangeStart);
127         else if (rangeStart >= '!' && rangeStart <= '~')
128             dataLogF("%c", rangeStart);
129         else
130             dataLogF("\\\\%d", rangeStart);
131     } else {
132         if (rangeStart == 1 && rangeEnd == 127)
133             dataLogF("[any input]");
134         else
135             dataLogF("\\\\%d-\\\\%d", rangeStart, rangeEnd);
136     }
137 }
138
139 static void printTransitions(const Vector<NFANode>& graph, unsigned sourceNode, uint16_t epsilonTransitionCharacter)
140 {
141     const NFANode& node = graph[sourceNode];
142     const HashMap<uint16_t, NFANodeIndexSet, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>>& transitions = node.transitions;
143
144     HashMap<unsigned, HashSet<uint16_t, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>>, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> transitionsPerTarget;
145
146     for (const auto& transition : transitions) {
147         for (unsigned targetNode : transition.value) {
148             transitionsPerTarget.add(targetNode, HashSet<uint16_t, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>>());
149             transitionsPerTarget.find(targetNode)->value.add(transition.key);
150         }
151     }
152
153     for (const auto& transitionPerTarget : transitionsPerTarget) {
154         dataLogF("        %d -> %d [label=\"", sourceNode, transitionPerTarget.key);
155
156         Vector<uint16_t> incommingCharacters;
157         copyToVector(transitionPerTarget.value, incommingCharacters);
158         std::sort(incommingCharacters.begin(), incommingCharacters.end());
159
160         uint16_t rangeStart = incommingCharacters.first();
161         uint16_t rangeEnd = rangeStart;
162         bool first = true;
163         for (unsigned sortedTransitionIndex = 1; sortedTransitionIndex < incommingCharacters.size(); ++sortedTransitionIndex) {
164             uint16_t nextChar = incommingCharacters[sortedTransitionIndex];
165             if (nextChar == rangeEnd+1) {
166                 rangeEnd = nextChar;
167                 continue;
168             }
169             printRange(first, rangeStart, rangeEnd, epsilonTransitionCharacter);
170             rangeStart = rangeEnd = nextChar;
171             first = false;
172         }
173         printRange(first, rangeStart, rangeEnd, epsilonTransitionCharacter);
174
175         dataLogF("\"];\n");
176     }
177
178     for (unsigned targetOnAnyCharacter : node.transitionsOnAnyCharacter)
179         dataLogF("        %d -> %d [label=\"[any input]\"];\n", sourceNode, targetOnAnyCharacter);
180 }
181
182 void NFA::debugPrintDot() const
183 {
184     dataLogF("digraph NFA_Transitions {\n");
185     dataLogF("    rankdir=LR;\n");
186     dataLogF("    node [shape=circle];\n");
187     dataLogF("    {\n");
188     for (unsigned i = 0; i < m_nodes.size(); ++i) {
189         dataLogF("         %d [label=<Node %d", i, i);
190
191         const ActionList& finalRules = m_nodes[i].finalRuleIds;
192         if (!finalRules.isEmpty()) {
193             dataLogF("<BR/>(Final: ");
194             for (unsigned ruleIndex = 0; ruleIndex < finalRules.size(); ++ruleIndex) {
195                 if (ruleIndex)
196                     dataLogF(", ");
197                 dataLogF("%llu", finalRules[ruleIndex]);
198             }
199             dataLogF(")");
200         }
201
202         dataLogF(">]");
203
204         if (!finalRules.isEmpty())
205             dataLogF(" [shape=doublecircle]");
206
207         dataLogF(";\n");
208     }
209     dataLogF("    }\n");
210
211     dataLogF("    {\n");
212     for (unsigned i = 0; i < m_nodes.size(); ++i)
213         printTransitions(m_nodes, i, epsilonTransitionCharacter);
214     dataLogF("    }\n");
215     dataLogF("}\n");
216 }
217 #endif
218
219 } // namespace ContentExtensions
220
221 } // namespace WebCore
222
223 #endif // ENABLE(CONTENT_EXTENSIONS)