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