From 6882a04fb36642862b11efe514251d32070c3d65 Mon Sep 17 00:00:00 2001 From: Konstantin Tokarev Date: Thu, 25 Aug 2016 19:20:41 +0300 Subject: Imported QtWebKit TP3 (git b57bc6801f1876c3220d5a4bfea33d620d477443) Change-Id: I3b1d8a2808782c9f34d50240000e20cb38d3680f Reviewed-by: Konstantin Tokarev --- Source/WebCore/contentextensions/DFANode.cpp | 147 +++++++++++++++++++++++++++ 1 file changed, 147 insertions(+) create mode 100644 Source/WebCore/contentextensions/DFANode.cpp (limited to 'Source/WebCore/contentextensions/DFANode.cpp') diff --git a/Source/WebCore/contentextensions/DFANode.cpp b/Source/WebCore/contentextensions/DFANode.cpp new file mode 100644 index 000000000..762a13558 --- /dev/null +++ b/Source/WebCore/contentextensions/DFANode.cpp @@ -0,0 +1,147 @@ +/* + * Copyright (C) 2014, 2015 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" +#include "DFANode.h" + +#include "DFA.h" + +#if ENABLE(CONTENT_EXTENSIONS) + +namespace WebCore { + +namespace ContentExtensions { + +Vector DFANode::actions(const DFA& dfa) const +{ + // FIXME: Use iterators instead of copying the Vector elements. + Vector vector; + vector.reserveInitialCapacity(m_actionsLength); + for (uint32_t i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i) + vector.uncheckedAppend(dfa.actions[i]); + return vector; +} + +bool DFANode::containsTransition(char transition, const DFA& dfa) const +{ + // Called from DFAMinimizer, this loops though a maximum of 128 transitions, so it's not too slow. + ASSERT(m_transitionsLength <= 128); + for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) { + if (dfa.transitionRanges[i].first <= transition + && dfa.transitionRanges[i].last >= transition) + return true; + } + return false; +} + +void DFANode::kill(DFA& dfa) +{ + ASSERT(m_flags != IsKilled); + m_flags = IsKilled; // Killed nodes don't have any other flags. + + // Invalidate the now-unused memory in the DFA to make finding bugs easier. + for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) { + dfa.transitionRanges[i] = { -1, -1 }; + dfa.transitionDestinations[i] = std::numeric_limits::max(); + } + for (unsigned i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i) + dfa.actions[i] = std::numeric_limits::max(); + + m_actionsStart = 0; + m_actionsLength = 0; + m_transitionsStart = 0; + m_transitionsLength = 0; +}; + +bool DFANode::canUseFallbackTransition(const DFA& dfa) const +{ + // Transitions can contain '\0' if the expression has a end-of-line marker. + // Fallback transitions cover 1-127. We have to be careful with the first. + + IterableConstRange iterableTransitions = transitions(dfa); + auto iterator = iterableTransitions.begin(); + auto end = iterableTransitions.end(); + if (iterator == end) + return false; + + char lastSeenCharacter = 0; + if (!iterator.first()) { + lastSeenCharacter = iterator.last(); + if (lastSeenCharacter == 127) + return true; + ++iterator; + } + + for (;iterator != end; ++iterator) { + ASSERT(iterator.first() > lastSeenCharacter); + if (iterator.first() != lastSeenCharacter + 1) + return false; + + if (iterator.range().last == 127) + return true; + lastSeenCharacter = iterator.last(); + } + return false; +} + +uint32_t DFANode::bestFallbackTarget(const DFA& dfa) const +{ + ASSERT(canUseFallbackTransition(dfa)); + + HashMap::Hash, WTF::UnsignedWithZeroKeyHashTraits> histogram; + + IterableConstRange iterableTransitions = transitions(dfa); + auto iterator = iterableTransitions.begin(); + auto end = iterableTransitions.end(); + ASSERT_WITH_MESSAGE(iterator != end, "An empty range list cannot use a fallback transition."); + + if (!iterator.first() && !iterator.last()) + ++iterator; + ASSERT_WITH_MESSAGE(iterator != end, "An empty range list matching only zero cannot use a fallback transition."); + + uint32_t bestTarget = iterator.target(); + unsigned bestTargetScore = !iterator.range().first ? iterator.range().size() - 1 : iterator.range().size(); + histogram.add(bestTarget, bestTargetScore); + ++iterator; + + for (;iterator != end; ++iterator) { + unsigned rangeSize = iterator.range().size(); + uint32_t target = iterator.target(); + auto addResult = histogram.add(target, rangeSize); + if (!addResult.isNewEntry) + addResult.iterator->value += rangeSize; + if (addResult.iterator->value > bestTargetScore) { + bestTargetScore = addResult.iterator->value; + bestTarget = target; + } + } + return bestTarget; +} + +} // namespace ContentExtensions + +} // namespace WebCore + +#endif // ENABLE(CONTENT_EXTENSIONS) -- cgit v1.2.1