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 "DFANode.h"
28
29#include "DFA.h"
30
31#if ENABLE(CONTENT_EXTENSIONS)
32
33namespace WebCore {
34
35namespace ContentExtensions {
36
37Vector<uint64_t> DFANode::actions(const DFA& dfa) const
38{
39 // FIXME: Use iterators instead of copying the Vector elements.
40 Vector<uint64_t> vector;
41 vector.reserveInitialCapacity(m_actionsLength);
42 for (uint32_t i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)
43 vector.uncheckedAppend(dfa.actions[i]);
44 return vector;
45}
46
47bool DFANode::containsTransition(char transition, const DFA& dfa) const
48{
49 // Called from DFAMinimizer, this loops though a maximum of 128 transitions, so it's not too slow.
50 ASSERT(m_transitionsLength <= 128);
51 for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) {
52 if (dfa.transitionRanges[i].first <= transition
53 && dfa.transitionRanges[i].last >= transition)
54 return true;
55 }
56 return false;
57}
58
59void DFANode::kill(DFA& dfa)
60{
61 ASSERT(m_flags != IsKilled);
62 m_flags = IsKilled; // Killed nodes don't have any other flags.
63
64 // Invalidate the now-unused memory in the DFA to make finding bugs easier.
65 for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) {
66 dfa.transitionRanges[i] = { -1, -1 };
67 dfa.transitionDestinations[i] = std::numeric_limits<uint32_t>::max();
68 }
69 for (unsigned i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)
70 dfa.actions[i] = std::numeric_limits<uint64_t>::max();
71
72 m_actionsStart = 0;
73 m_actionsLength = 0;
74 m_transitionsStart = 0;
75 m_transitionsLength = 0;
76};
77
78bool DFANode::canUseFallbackTransition(const DFA& dfa) const
79{
80 // Transitions can contain '\0' if the expression has a end-of-line marker.
81 // Fallback transitions cover 1-127. We have to be careful with the first.
82
83 IterableConstRange iterableTransitions = transitions(dfa);
84 auto iterator = iterableTransitions.begin();
85 auto end = iterableTransitions.end();
86 if (iterator == end)
87 return false;
88
89 char lastSeenCharacter = 0;
90 if (!iterator.first()) {
91 lastSeenCharacter = iterator.last();
92 if (lastSeenCharacter == 127)
93 return true;
94 ++iterator;
95 }
96
97 for (;iterator != end; ++iterator) {
98 ASSERT(iterator.first() > lastSeenCharacter);
99 if (iterator.first() != lastSeenCharacter + 1)
100 return false;
101
102 if (iterator.range().last == 127)
103 return true;
104 lastSeenCharacter = iterator.last();
105 }
106 return false;
107}
108
109uint32_t DFANode::bestFallbackTarget(const DFA& dfa) const
110{
111 ASSERT(canUseFallbackTransition(dfa));
112
113 HashMap<uint32_t, unsigned, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t>> histogram;
114
115 IterableConstRange iterableTransitions = transitions(dfa);
116 auto iterator = iterableTransitions.begin();
117 auto end = iterableTransitions.end();
118 ASSERT_WITH_MESSAGE(iterator != end, "An empty range list cannot use a fallback transition.");
119
120 if (!iterator.first() && !iterator.last())
121 ++iterator;
122 ASSERT_WITH_MESSAGE(iterator != end, "An empty range list matching only zero cannot use a fallback transition.");
123
124 uint32_t bestTarget = iterator.target();
125 unsigned bestTargetScore = !iterator.range().first ? iterator.range().size() - 1 : iterator.range().size();
126 histogram.add(bestTarget, bestTargetScore);
127 ++iterator;
128
129 for (;iterator != end; ++iterator) {
130 unsigned rangeSize = iterator.range().size();
131 uint32_t target = iterator.target();
132 auto addResult = histogram.add(target, rangeSize);
133 if (!addResult.isNewEntry)
134 addResult.iterator->value += rangeSize;
135 if (addResult.iterator->value > bestTargetScore) {
136 bestTargetScore = addResult.iterator->value;
137 bestTarget = target;
138 }
139 }
140 return bestTarget;
141}
142
143} // namespace ContentExtensions
144
145} // namespace WebCore
146
147#endif // ENABLE(CONTENT_EXTENSIONS)
148