#include "config.h"
#include "DFANode.h"
#include "DFA.h"
#if ENABLE(CONTENT_EXTENSIONS)
namespace WebCore {
namespace ContentExtensions {
Vector<uint64_t> DFANode::actions(const DFA& dfa) const
{
Vector<uint64_t> 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
{
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;
for (unsigned i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i) {
dfa.transitionRanges[i] = { -1, -1 };
dfa.transitionDestinations[i] = std::numeric_limits<uint32_t>::max();
}
for (unsigned i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)
dfa.actions[i] = std::numeric_limits<uint64_t>::max();
m_actionsStart = 0;
m_actionsLength = 0;
m_transitionsStart = 0;
m_transitionsLength = 0;
};
bool DFANode::canUseFallbackTransition(const DFA& dfa) const
{
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<uint32_t, unsigned, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t>> 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;
}
}
}
#endif // ENABLE(CONTENT_EXTENSIONS)