Unreviewed, fix -Wmisleading-indentation warning introduced in r246764
[WebKit-https.git] / Source / WebCore / contentextensions / DFA.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 "DFA.h"
28
29 #if ENABLE(CONTENT_EXTENSIONS)
30
31 #include "DFAMinimizer.h"
32 #include <wtf/DataLog.h>
33
34 namespace WebCore {
35
36 namespace ContentExtensions {
37
38 DFA DFA::empty()
39 {
40     DFA newDFA;
41     newDFA.nodes.append(DFANode());
42     return newDFA;
43 }
44
45 size_t DFA::memoryUsed() const
46 {
47     return sizeof(DFA)
48         + actions.capacity() * sizeof(uint64_t)
49         + transitionRanges.capacity() * sizeof(CharRange)
50         + transitionDestinations.capacity() * sizeof(uint32_t)
51         + nodes.capacity() * sizeof(DFANode);
52 }
53
54 void DFA::shrinkToFit()
55 {
56     nodes.shrinkToFit();
57     actions.shrinkToFit();
58     transitionRanges.shrinkToFit();
59     transitionDestinations.shrinkToFit();
60 }
61
62 void DFA::minimize()
63 {
64     DFAMinimizer::minimize(*this);
65 }
66
67 unsigned DFA::graphSize() const
68 {
69     unsigned count = 0;
70     for (const DFANode& node : nodes) {
71         if (!node.isKilled())
72             ++count;
73     }
74     return count;
75 }
76
77 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
78 static void printRange(bool firstRange, char rangeStart, char rangeEnd)
79 {
80     if (!firstRange)
81         dataLogF(", ");
82     if (rangeStart == rangeEnd) {
83         if (rangeStart == '"' || rangeStart == '\\')
84             dataLogF("\\%c", rangeStart);
85         else if (rangeStart >= '!' && rangeStart <= '~')
86             dataLogF("%c", rangeStart);
87         else
88             dataLogF("\\\\%d", rangeStart);
89     } else
90         dataLogF("\\\\%d-\\\\%d", rangeStart, rangeEnd);
91 }
92
93 static void printTransitions(const DFA& dfa, unsigned sourceNodeId)
94 {
95     const DFANode& sourceNode = dfa.nodes[sourceNodeId];
96     auto transitions = sourceNode.transitions(dfa);
97
98     if (transitions.begin() == transitions.end())
99         return;
100
101     HashMap<unsigned, Vector<uint16_t>, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> transitionsPerTarget;
102
103     // First, we build the list of transitions coming to each target node.
104     for (const auto& transition : transitions) {
105         unsigned target = transition.target();
106         transitionsPerTarget.add(target, Vector<uint16_t>());
107
108         for (unsigned offset = 0; offset < transition.range().size(); ++offset)
109             transitionsPerTarget.find(target)->value.append(transition.first() + offset);
110     }
111
112     // Then we go over each one an display the ranges one by one.
113     for (const auto& transitionPerTarget : transitionsPerTarget) {
114         dataLogF("        %d -> %d [label=\"", sourceNodeId, transitionPerTarget.key);
115
116         Vector<uint16_t> incommingCharacters = transitionPerTarget.value;
117         std::sort(incommingCharacters.begin(), incommingCharacters.end());
118
119         char rangeStart = incommingCharacters.first();
120         char rangeEnd = rangeStart;
121         bool first = true;
122         for (unsigned sortedTransitionIndex = 1; sortedTransitionIndex < incommingCharacters.size(); ++sortedTransitionIndex) {
123             char nextChar = incommingCharacters[sortedTransitionIndex];
124             if (nextChar == rangeEnd+1) {
125                 rangeEnd = nextChar;
126                 continue;
127             }
128             printRange(first, rangeStart, rangeEnd);
129             rangeStart = rangeEnd = nextChar;
130             first = false;
131         }
132         printRange(first, rangeStart, rangeEnd);
133
134         dataLogF("\"];\n");
135     }
136 }
137
138 void DFA::debugPrintDot() const
139 {
140     dataLogF("digraph DFA_Transitions {\n");
141     dataLogF("    rankdir=LR;\n");
142     dataLogF("    node [shape=circle];\n");
143     dataLogF("    {\n");
144     for (unsigned i = 0; i < nodes.size(); ++i) {
145         if (nodes[i].isKilled())
146             continue;
147
148         dataLogF("         %d [label=<Node %d", i, i);
149         const Vector<uint64_t>& actions = nodes[i].actions(*this);
150         if (!actions.isEmpty()) {
151             dataLogF("<BR/>Actions: ");
152             for (unsigned actionIndex = 0; actionIndex < actions.size(); ++actionIndex) {
153                 if (actionIndex)
154                     dataLogF(", ");
155                 dataLogF("%" PRIu64, actions[actionIndex]);
156             }
157         }
158         dataLogF(">]");
159
160         if (!actions.isEmpty())
161             dataLogF(" [shape=doublecircle]");
162
163         dataLogF(";\n");
164     }
165     dataLogF("    }\n");
166
167     dataLogF("    {\n");
168     for (unsigned i = 0; i < nodes.size(); ++i)
169         printTransitions(*this, i);
170
171     dataLogF("    }\n");
172     dataLogF("}\n");
173 }
174 #endif
175
176 } // namespace ContentExtensions
177
178 } // namespace WebCore
179
180 #endif // ENABLE(CONTENT_EXTENSIONS)