ChangeLog

2015-04-22  Alex Christensen  <achristensen@webkit.org>

        Use less memory when compiling content extensions.

        https://bugs.webkit.org/show_bug.cgi?id=144051

        Reviewed by NOBODY (OOPS!).

        No change in functionality, correctness already covered by existing tests.

        * contentextensions/CombinedURLFilters.cpp:

        (WebCore::ContentExtensions::recursiveMemoryUsed):

        (WebCore::ContentExtensions::CombinedURLFilters::memoryUsed):

        * contentextensions/CombinedURLFilters.h:

        * contentextensions/ContentExtensionCompiler.cpp:

        (WebCore::ContentExtensions::compileRuleList):

        * contentextensions/ContentExtensionsDebugging.h:

        * contentextensions/DFA.cpp:

        (WebCore::ContentExtensions::DFA::DFA):

        (WebCore::ContentExtensions::DFA::memoryUsed):

        (WebCore::ContentExtensions::DFANode::actions):

        (WebCore::ContentExtensions::DFANode::transitions):

        (WebCore::ContentExtensions::DFANode::fallbackTransitionDestination):

        (WebCore::ContentExtensions::DFANode::addFallbackTransition):

        (WebCore::ContentExtensions::DFANode::containsTransition):

        (WebCore::ContentExtensions::DFA::minimize):

        (WebCore::ContentExtensions::DFA::operator=): Deleted.

        * contentextensions/DFA.h:

        * contentextensions/DFABytecodeCompiler.cpp:

        (WebCore::ContentExtensions::DFABytecodeCompiler::emitAppendAction):

        (WebCore::ContentExtensions::DFABytecodeCompiler::emitTestFlagsAndAppendAction):

        (WebCore::ContentExtensions::DFABytecodeCompiler::emitJump):

        (WebCore::ContentExtensions::DFABytecodeCompiler::emitCheckValue):

        (WebCore::ContentExtensions::DFABytecodeCompiler::emitCheckValueRange):

        (WebCore::ContentExtensions::DFABytecodeCompiler::emitTerminate):

        (WebCore::ContentExtensions::DFABytecodeCompiler::compileNode):

        (WebCore::ContentExtensions::DFABytecodeCompiler::compileNodeTransitions):

        (WebCore::ContentExtensions::DFABytecodeCompiler::compile):

        * contentextensions/DFAMinimizer.cpp:

        (WebCore::ContentExtensions::DFAMinimizer::minimize):

        * contentextensions/DFAMinimizer.h:

        * contentextensions/DFANode.h:

        (WebCore::ContentExtensions::DFANode::DFANode):

        (WebCore::ContentExtensions::DFANode::isKilled):

        (WebCore::ContentExtensions::DFANode::hasFallbackTransition):

        (WebCore::ContentExtensions::DFANode::hasActions):

        (WebCore::ContentExtensions::DFANode::transitionsLength):

        (WebCore::ContentExtensions::DFANode::setActions):

        (WebCore::ContentExtensions::DFANode::setTransitions):

        (WebCore::ContentExtensions::DFANode::transitionsStart):

        * contentextensions/NFA.cpp:

        (WebCore::ContentExtensions::NFA::memoryUsed):

        * contentextensions/NFA.h:

        * contentextensions/NFAToDFA.cpp:

        (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetSource::NodeIdSetToUniqueNodeIdSetSource):

        (WebCore::ContentExtensions::NodeIdSetToUniqueNodeIdSetTranslator::translate):

        (WebCore::ContentExtensions::getOrCreateDFANode):

        (WebCore::ContentExtensions::NFAToDFA::convert):

2015-04-22  Eric Carlson  <eric.carlson@apple.com>

        Unreviewed post-review clean up after r183096.

183114

Source/WebCore/contentextensions/CombinedURLFilters.cpp

@@struct PrefixTreeVertex {

    bool inVariableLengthPrefix { false };

};

static size_t recursiveMemoryUsed(const std::unique_ptr<PrefixTreeVertex>& node)

{

    size_t size = sizeof(PrefixTreeVertex)

        + node->edges.capacity() * sizeof(std::pair<Term, std::unique_ptr<PrefixTreeVertex>>)

        + node->finalActions.capacity() * sizeof(uint64_t);

    for (const auto& child : node->edges.values())

        size += recursiveMemoryUsed(child);

    return size;

}

size_t CombinedURLFilters::memoryUsed() const

{

    return recursiveMemoryUsed(m_prefixTreeRoot);

}

CombinedURLFilters::CombinedURLFilters()

    : m_prefixTreeRoot(std::make_unique<PrefixTreeVertex>())

{

183021

Source/WebCore/contentextensions/CombinedURLFilters.h

@@public:

    Vector<NFA> createNFAs() const;

    void clear();

50 size_t memoryUsed() const;

51

private:

    std::unique_ptr<PrefixTreeVertex> m_prefixTreeRoot;

};

183021

Source/WebCore/contentextensions/ContentExtensionCompiler.cpp

@@std::error_code compileRuleList(ContentE

    Vector<SerializedActionByte> actions;

    Vector<unsigned> actionLocations = serializeActions(parsedRuleList, actions);

    client.writeActions(WTF::move(actions));

137 LOG_LARGE_STRUCTURES(actions, actions.size() * sizeof(SerializedActionByte));

    actions.clear();

    HashSet<uint64_t, DefaultHash<uint64_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint64_t>> universalActionLocations;

@@std::error_code compileRuleList(ContentE

        if (contentExtensionRule.action().type() == ActionType::IgnorePreviousRules)

            ignorePreviousRulesSeen = true;

    }

168 LOG_LARGE_STRUCTURES(parsedRuleList, parsedRuleList.size() * sizeof(ContentExtensionRule)); // Doesn't include strings.

169 LOG_LARGE_STRUCTURES(actionLocations, actionLocations.size() * sizeof(unsigned));

    parsedRuleList.clear();

    actionLocations.clear();

@@std::error_code compileRuleList(ContentE

#endif

    Vector<NFA> nfas = combinedURLFilters.createNFAs();

183 LOG_LARGE_STRUCTURES(combinedURLFilters, combinedURLFilters.memoryUsed());

    combinedURLFilters.clear();

    if (!nfas.size() && universalActionLocations.size())

        nfas.append(NFA());

@@std::error_code compileRuleList(ContentE

        double dfaBuildTimeStart = monotonicallyIncreasingTime();

#endif

        DFA dfa = NFAToDFA::convert(nfas[i]);

211 LOG_LARGE_STRUCTURES(dfa, dfa.memoryUsed());

#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING

        double dfaBuildTimeEnd = monotonicallyIncreasingTime();

        dataLogF("    Time spent building the DFA %zu: %f\n", i, (dfaBuildTimeEnd - dfaBuildTimeStart));

@@std::error_code compileRuleList(ContentE

        dfa.debugPrintDot();

#endif

226 ASSERT_WITH_MESSAGE(!dfa.nodeAt(dfa.root()).actions.size(), "All actions on the DFA root should come from regular expressions that match everything.");

227231 if (!i) {

228232 // Put all the universal actions on the first DFA.

233 unsigned actionsStart = dfa.actions.size();

229234 for (uint64_t actionLocation : universalActionLocations)

230 dfa.nodeAt(dfa.root()).actions.append(actionLocation);

                dfa.actions.append(actionLocation);

            unsigned actionsEnd = dfa.actions.size();

            unsigned actionsLength = actionsEnd - actionsStart;

            RELEASE_ASSERT_WITH_MESSAGE(actionsLength < std::numeric_limits<uint16_t>::max(), "Too many uncombined actions that match everything");

            dfa.nodes[dfa.root].setActions(actionsStart, static_cast<uint16_t>(actionsLength));

        }

        DFABytecodeCompiler compiler(dfa, bytecode);

        compiler.compile();

    }

244 LOG_LARGE_STRUCTURES(universalActionLocations, universalActionLocations.size() * sizeof(unsigned));

    universalActionLocations.clear();

#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING

@@std::error_code compileRuleList(ContentE

    dataLogF("    Bytecode size %zu\n", bytecode.size());

    dataLogF("    DFA count %zu\n", nfas.size());

#endif

    size_t nfaMemoryUsed = 0;

    for (const NFA& nfa : nfas)

        nfaMemoryUsed += sizeof(NFA) + nfa.memoryUsed();

    LOG_LARGE_STRUCTURES(nfas, nfaMemoryUsed);

243257 nfas.clear();

244258

259 LOG_LARGE_STRUCTURES(bytecode, bytecode.size() * sizeof(uint8_t));

245260 client.writeBytecode(WTF::move(bytecode));

261 bytecode.clear();

    return { };

}

183021

Source/WebCore/contentextensions/ContentExtensionsDebugging.h

#define CONTENT_EXTENSIONS_MEMORY_REPORTING 0

#define CONTENT_EXTENSIONS_PAGE_SIZE 16384

38#define LOG_LARGE_STRUCTURES(name, size) /* if (size > 1000000) { WTFLogAlways("NAME: %s SIZE %d", #name, (int)(size)); }; */

39

#endif // ENABLE(CONTENT_EXTENSIONS)

#endif // ContentExtensionsDebugging_h

183021

Source/WebCore/contentextensions/DFA.cpp

@@namespace WebCore {

namespace ContentExtensions {

DFA::DFA()

39 : m_root(0)

39 : root(0)

{

}

DFA::DFA(Vector<DFANode>&& nodes, unsigned rootIndex)

    : m_nodes(WTF::move(nodes))

    , m_root(rootIndex)

43size_t DFA::memoryUsed() const

4644{

47 ASSERT(rootIndex < m_nodes.size());

    return sizeof(DFA)

        + actions.size() * sizeof(uint64_t)

        + transitions.size() * sizeof(std::pair<uint8_t, uint32_t>)

        + nodes.size() * sizeof(DFANode);

4849}

4950

DFA::DFA(const DFA& dfa)

    : m_nodes(dfa.m_nodes)

    , m_root(dfa.m_root)

51// FIXME: Make DFANode.cpp.

52Vector<uint64_t> DFANode::actions(const DFA& dfa) const

5353{

    // FIXME: Use iterators instead of copying the Vector elements.

    Vector<uint64_t> vector;

    vector.reserveInitialCapacity(m_actionsLength);

    for (uint32_t i = m_actionsStart; i < m_actionsStart + m_actionsLength; ++i)

        vector.append(dfa.actions[i]);

    return vector;

}

Vector<std::pair<uint8_t, uint32_t>> DFANode::transitions(const DFA& dfa) const

{

    // FIXME: Use iterators instead of copying the Vector elements.

    Vector<std::pair<uint8_t, uint32_t>> vector;

    vector.reserveInitialCapacity(transitionsLength());

    for (uint32_t i = m_transitionsStart; i < m_transitionsStart + m_transitionsLength; ++i)

        vector.append(dfa.transitions[i]);

    return vector;

5470}

5571

56 ~~DFA&~~ DFA~~::ope~~rat~~or=~~(const DFA& dfa)

72uint32_t DFANode::fallbackTransitionDestination(const DFA& dfa) const

5773{

    m_nodes = dfa.m_nodes;

    m_root = dfa.m_root;

    return *this;

    RELEASE_ASSERT(hasFallbackTransition());

    // If there is a fallback transition, it is just after the other transitions and has an invalid ASCII character to mark it as a fallback transition.

    ASSERT(dfa.transitions[m_transitionsStart + m_transitionsLength].first == std::numeric_limits<uint8_t>::max());

    return dfa.transitions[m_transitionsStart + m_transitionsLength].second;

}

void DFANode::changeFallbackTransition(DFA& dfa, uint32_t newDestination)

{

    RELEASE_ASSERT(hasFallbackTransition());

    ASSERT_WITH_MESSAGE(dfa.transitions[m_transitionsStart + m_transitionsLength].first == std::numeric_limits<uint8_t>::max(), "When changing a fallback transition, the fallback transition should already be marked as such");

    dfa.transitions[m_transitionsStart + m_transitionsLength] = std::pair<uint8_t, uint32_t>(std::numeric_limits<uint8_t>::max(), newDestination);

}

void DFANode::addFallbackTransition(DFA& dfa, uint32_t destination)

{

    RELEASE_ASSERT_WITH_MESSAGE(dfa.transitions.size() == m_transitionsStart + m_transitionsLength, "Adding a fallback transition should only happen if the node is at the end");

    dfa.transitions.append(std::pair<uint8_t, uint32_t>(std::numeric_limits<uint8_t>::max(), destination));

    ASSERT(!(m_flags & HasFallbackTransition));

    m_flags |= HasFallbackTransition;

}

bool DFANode::containsTransition(uint8_t transition, DFA& dfa)

{

    // 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.transitions[i].first == transition)

            return true;

    }

    return false;

}

void DFA::minimize()

{

65 ~~m_root =~~ DFAMinimizer::minimize(~~m_nodes, m_root~~);

109 DFAMinimizer::minimize(*this);

}

#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING

183021

Source/WebCore/contentextensions/DFA.h

@@namespace ContentExtensions {

class WEBCORE_EXPORT DFA {

public:

    DFA();

    DFA(Vector<DFANode>&& nodes, unsigned rootIndex);

    DFA(const DFA& dfa);

    DFA& operator=(const DFA&);

    unsigned root() const { return m_root; }

    unsigned size() const { return m_nodes.size(); }

    const DFANode& nodeAt(unsigned i) const { return m_nodes[i]; }

    DFANode& nodeAt(unsigned i) { return m_nodes[i]; }

5243

5344 void minimize();

45 size_t memoryUsed() const;

#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING

    void debugPrintDot() const;

#endif

private:

    Vector<DFANode> m_nodes;

    unsigned m_root;

    Vector<uint64_t> actions;

    Vector<std::pair<uint8_t, uint32_t>> transitions;

    Vector<DFANode> nodes;

    unsigned root;

};

}

183021

Source/WebCore/contentextensions/DFABytecodeCompiler.cpp

@@void DFABytecodeCompiler::emitTerminate(

void DFABytecodeCompiler::compileNode(unsigned index, bool root)

{

98 const DFANode& node = m_dfa.node~~At(~~index);

99 if (node.isKilled) {

98 const DFANode& node = m_dfa.nodes[index];

99 if (node.isKilled()) {

        m_nodeStartOffsets[index] = std::numeric_limits<unsigned>::max();

        return;

    }

@@void DFABytecodeCompiler::compileNode(un

    if (!root)

        m_nodeStartOffsets[index] = m_bytecode.size();

108 for (uint64_t action : node.actions) {

108 for (uint64_t action : node.actions(m_dfa)) {

        // High bits are used to store flags. See compileRuleList.

        if (action & 0xFFFF00000000)

            emitTestFlagsAndAppendAction(static_cast<uint16_t>(action >> 32), static_cast<unsigned>(action));

@@void DFABytecodeCompiler::compileNode(un

void DFABytecodeCompiler::compileNodeTransitions(const DFANode& node)

{

    unsigned destinations[128];

    const unsigned noDestination = std::numeric_limits<unsigned>::max();

    for (uint16_t i = 0; i < 128; i++) {

        auto it = node.transitions.find(i);

        if (it == node.transitions.end())

            destinations[i] = noDestination;

        else

            destinations[i] = it->value;

    uint32_t destinations[128];

    memset(destinations, 0xff, sizeof(destinations));

    const uint32_t noDestination = std::numeric_limits<uint32_t>::max();

    for (const std::pair<uint8_t, uint32_t>& pair : node.transitions(m_dfa)) {

        RELEASE_ASSERT(pair.first < 128);

        ASSERT_WITH_MESSAGE(destinations[pair.first] == noDestination, "Transitions should be unique");

        destinations[pair.first] = pair.second;

    }

    Vector<Range> ranges;

@@void DFABytecodeCompiler::compileNodeTra

    bool hasRangeMin = false;

    for (uint8_t i = 0; i < 128; i++) {

        if (hasRangeMin) {

141 ASSERT_WITH_MESSAGE(!(node.hasFallbackTransition && node.fallbackTransition == destinations[rangeMin]), "Individual transitions to the fallback transitions should have been eliminated by the optimizer.");

141 ASSERT_WITH_MESSAGE(!(node.hasFallbackTransition() && node.fallbackTransitionDestination(m_dfa) == destinations[rangeMin]), "Individual transitions to the fallback transitions should have been eliminated by the optimizer.");

            if (destinations[i] != destinations[rangeMin]) {

                // This is the end of a range. Check if it can be case insensitive.

@@void DFABytecodeCompiler::compileNodeTra

    for (const auto& range : ranges)

        compileCheckForRange(range);

189 if (node.hasFallbackTransition)

190 emitJump(node.fallbackTransition);

189 if (node.hasFallbackTransition())

190 emitJump(node.fallbackTransitionDestination(m_dfa));

    else

        emitTerminate();

}

@@void DFABytecodeCompiler::compileCheckFo

void DFABytecodeCompiler::compile()

{

208 WTFLogAlways("DFABytecodeCompiler::compile");

    // DFA header.

    unsigned startLocation = m_bytecode.size();

    append<unsigned>(m_bytecode, 0);

211 m_nodeStartOffsets.resize(m_dfa.size());

212 m_nodeStartOffsets.resize(m_dfa.nodes.size());

212213

213214 // Make sure the root is always at the beginning of the bytecode.

    compileNode(m_dfa.root(), true);

    for (unsigned i = 0; i < m_dfa.size(); i++) {

        if (i != m_dfa.root())

    compileNode(m_dfa.root, true);

    for (unsigned i = 0; i < m_dfa.nodes.size(); i++) {

        if (i != m_dfa.root)

            compileNode(i, false);

    }

183021

Source/WebCore/contentextensions/DFAMinimizer.cpp

@@namespace {

// simplifyTransitions() tries to collapse individual transitions into fallback transitions.

// After simplifyTransitions(), you can also make the assumption that a fallback transition target will never be

// also the target of an individual transition.

42 static void simplifyTransitions(~~Vector<~~DFA~~Node>~~& dfa~~Graph~~)

42static void simplifyTransitions(DFA& dfa)

4343{

    for (DFANode& dfaNode : dfaGraph) {

        if (!dfaNode.hasFallbackTransition

            && ((dfaNode.transitions.size() == 126 && !dfaNode.transitions.contains(0))

                || (dfaNode.transitions.size() == 127 && dfaNode.transitions.contains(0)))) {

    for (DFANode& dfaNode : dfa.nodes) {

        bool addingFallbackTransition = false;

        uint32_t newFallbackDestination = std::numeric_limits<uint32_t>::max();

        if (!dfaNode.hasFallbackTransition()

            && ((dfaNode.transitionsLength() == 126 && !dfaNode.containsTransition(0, dfa))

                || (dfaNode.transitionsLength() == 127 && dfaNode.containsTransition(0, dfa)))) {

            unsigned bestTarget = std::numeric_limits<unsigned>::max();

            unsigned bestTargetScore = 0;

            HashMap<unsigned, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> targetHistogram;

51 for (const auto& transition : dfaNode.transitions) {

52 if (!transition.~~key~~)

53 for (const auto& transition : dfaNode.transitions(dfa)) {

54 if (!transition.first)

5355 continue;

5456

55 unsigned transitionTarget = transition.~~valu~~e;

57 unsigned transitionTarget = transition.second;

                auto addResult = targetHistogram.add(transitionTarget, 1);

                if (!addResult.isNewEntry)

                    addResult.iterator->value++;

@@static void simplifyTransitions(Vector<D

            }

            ASSERT_WITH_MESSAGE(bestTargetScore, "There should be at least one valid target since having transitions is a precondition to enter this path.");

            dfaNode.hasFallbackTransition = true;

            dfaNode.fallbackTransition = bestTarget;

        }

        if (dfaNode.hasFallbackTransition) {

            Vector<uint16_t, 128> keys;

            DFANodeTransitions& transitions = dfaNode.transitions;

            copyKeysToVector(transitions, keys);

            for (uint16_t key : keys) {

                auto transitionIterator = transitions.find(key);

                if (transitionIterator->value == dfaNode.fallbackTransition)

                    transitions.remove(transitionIterator);

            }

69 addingFallbackTransition = true;

70 newFallbackDestination = bestTarget;

8171 }

        
        // FIXME: Use the same location to write new transitions followed by unused memory.

        // We can do this because we are always decreasing the amount of memory used.

        // We will probably need something like setHasFallbackTransitionWithoutChangingDFA to do that.

    }

}

@@private:

class FullGraphPartition {

public:

224 FullGraphPartition(const ~~Vector<~~DFA~~Node>~~& dfa~~Graph~~)

218 FullGraphPartition(const DFA& dfa)

225219 {

226 m_nodePartition.initialize(dfa~~Graph~~.size());

220 m_nodePartition.initialize(dfa.nodes.size());

227221

228 m_flattenedTransitionsStartOffsetPerNode.resize(dfa~~Graph~~.size());

222 m_flattenedTransitionsStartOffsetPerNode.resize(dfa.nodes.size());

        for (unsigned& counter : m_flattenedTransitionsStartOffsetPerNode)

            counter = 0;

232 m_flattenedFallbackTransitionsStartOffsetPerNode.resize(dfa~~Graph~~.size());

226 m_flattenedFallbackTransitionsStartOffsetPerNode.resize(dfa.nodes.size());

        for (unsigned& counter : m_flattenedFallbackTransitionsStartOffsetPerNode)

            counter = 0;

        // Count the number of incoming transitions per node.

        for (const DFANode& dfaNode : dfaGraph) {

            for (const auto& transition : dfaNode.transitions)

                ++m_flattenedTransitionsStartOffsetPerNode[transition.value];

            if (dfaNode.hasFallbackTransition)

                ++m_flattenedFallbackTransitionsStartOffsetPerNode[dfaNode.fallbackTransition];

        for (const DFANode& dfaNode : dfa.nodes) {

            for (const auto& transition : dfaNode.transitions(dfa))

                ++m_flattenedTransitionsStartOffsetPerNode[transition.second];

            if (dfaNode.hasFallbackTransition())

                ++m_flattenedFallbackTransitionsStartOffsetPerNode[dfaNode.fallbackTransitionDestination(dfa)];

        }

        // Accumulate the offsets.

@@public:

        unsigned flattenedFallbackTransitionsSize = fallbackTransitionAccumulator;

        // Next, let's fill the transition table and set up the size of each group at the same time.

262 m_flattenedTransitionsSizePerNode.resize(dfa~~Graph~~.size());

256 m_flattenedTransitionsSizePerNode.resize(dfa.nodes.size());

        for (unsigned& counter : m_flattenedTransitionsSizePerNode)

            counter = 0;

266 m_flattenedFallbackTransitionsSizePerNode.resize(dfa~~Graph~~.size());

260 m_flattenedFallbackTransitionsSizePerNode.resize(dfa.nodes.size());

        for (unsigned& counter : m_flattenedFallbackTransitionsSizePerNode)

            counter = 0;

@@public:

        m_flattenedFallbackTransitions.resize(flattenedFallbackTransitionsSize);

        for (unsigned i = 0; i < dfaGraph.size(); ++i) {

            const DFANode& dfaNode = dfaGraph[i];

            for (const auto& transition : dfaNode.transitions) {

                unsigned targetNodeIndex = transition.value;

        for (unsigned i = 0; i < dfa.nodes.size(); ++i) {

            const DFANode& dfaNode = dfa.nodes[i];

            for (const auto& transition : dfaNode.transitions(dfa)) {

                unsigned targetNodeIndex = transition.second;

                unsigned start = m_flattenedTransitionsStartOffsetPerNode[targetNodeIndex];

                unsigned offset = m_flattenedTransitionsSizePerNode[targetNodeIndex];

282 m_flattenedTransitions[start + offset] = Transition({ i, targetNodeIndex, transition.~~key~~ });

276 m_flattenedTransitions[start + offset] = Transition({ i, targetNodeIndex, transition.first });

                ++m_flattenedTransitionsSizePerNode[targetNodeIndex];

            }

286 if (dfaNode.hasFallbackTransition) {

287 unsigned targetNodeIndex = dfaNode.fallbackTransition;

280 if (dfaNode.hasFallbackTransition()) {

281 unsigned targetNodeIndex = dfaNode.fallbackTransitionDestination(dfa);

                unsigned start = m_flattenedFallbackTransitionsStartOffsetPerNode[targetNodeIndex];

                unsigned offset = m_flattenedFallbackTransitionsSizePerNode[targetNodeIndex];

@@struct ActionKeyHashTraits : public WTF:

} // anonymous namespace.

446 ~~unsigne~~d DFAMinimizer::minimize(~~Vector<~~DFA~~Node>~~& dfa~~Graph, unsigned root~~)

440void DFAMinimizer::minimize(DFA& dfa)

447441{

448 simplifyTransitions(dfa~~Graph~~);

442 simplifyTransitions(dfa);

449443

450 FullGraphPartition fullGraphPartition(dfa~~Graph~~);

444 FullGraphPartition fullGraphPartition(dfa);

    // Unlike traditional minimization final states can be differentiated by their action.

    // Instead of creating a single set for the final state, we partition by actions from

    // the start.

    HashMap<ActionKey, Vector<unsigned>, ActionKeyHash, ActionKeyHashTraits> finalStates;

456 for (unsigned i = 0; i < dfa~~Graph~~.size(); ++i) {

457 Vector<uint64_t>& actions = dfa~~Graph~~[i].actions;

450 for (unsigned i = 0; i < dfa.nodes.size(); ++i) {

451 Vector<uint64_t> actions = dfa.nodes[i].actions(dfa);

        if (actions.size()) {

            std::sort(actions.begin(), actions.end());

            auto addResult = finalStates.add(ActionKey(actions), Vector<unsigned>());

@@unsigned DFAMinimizer::minimize(Vector<D

    fullGraphPartition.splitByFallbackTransitions();

    Vector<unsigned> relocationVector;

484 relocationVector.reserveInitialCapacity(dfa~~Graph~~.size());

485 for (unsigned i = 0; i < dfa~~Graph~~.size(); ++i)

478 relocationVector.reserveInitialCapacity(dfa.nodes.size());

479 for (unsigned i = 0; i < dfa.nodes.size(); ++i)

        relocationVector.append(i);

    // Kill the useless nodes and keep track of the new node transitions should point to.

489 for (unsigned i = 0; i < dfa~~Graph~~.size(); ++i) {

483 for (unsigned i = 0; i < dfa.nodes.size(); ++i) {

        unsigned replacement = fullGraphPartition.nodeReplacement(i);

        if (i != replacement) {

            relocationVector[i] = replacement;

            DFANode& node = dfaGraph[i];

            node.actions.clear();

            node.transitions.clear();

            node.hasFallbackTransition = false;

            node.isKilled = true;

487 dfa.nodes[i].kill();

        }

    }

    for (DFANode& node : dfaGraph) {

        for (auto& transition : node.transitions)

            transition.value = relocationVector[transition.value];

        if (node.hasFallbackTransition)

            node.fallbackTransition = relocationVector[node.fallbackTransition];

    for (DFANode& node : dfa.nodes) {

        for (auto& transition : node.transitions(dfa))

            transition.second = relocationVector[transition.second];

        if (node.hasFallbackTransition())

            node.changeFallbackTransition(dfa, relocationVector[node.fallbackTransitionDestination(dfa)]);

    }

    // After minimizing, there is no guarantee individual transition are still poiting to different states.

    // The state pointed by one individual transition and the fallback states may have been merged.

511 simplifyTransitions(dfa~~Graph~~);

500 simplifyTransitions(dfa);

512501

513 re~~turn~~ relocationVector[root];

502 dfa.root = relocationVector[dfa.root];

}

} // namespace ContentExtensions

183021

Source/WebCore/contentextensions/DFAMinimizer.h

#if ENABLE(CONTENT_EXTENSIONS)

31 #include "DFA~~Node~~.h"

31#include "DFA.h"

#include <wtf/Vector.h>

namespace WebCore {

@@namespace ContentExtensions {

class DFAMinimizer {

public:

39 WEBCORE_EXPORT static ~~unsigne~~d minimize(~~Vector<~~DFA~~Node>& dfaGraph, unsigned rootNode~~);

39 WEBCORE_EXPORT static void minimize(DFA&);

};

} // namespace ContentExtensions

183021

Source/WebCore/contentextensions/DFANode.h

@@namespace WebCore {

namespace ContentExtensions {

39class DFA;

40

3941// A DFANode abstract the transition table out of a DFA state. If a state is accepting, the DFANode also have

4042// the actions for that state.

typedef HashMap<uint16_t, unsigned, DefaultHash<uint16_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint16_t>> DFANodeTransitions;

4443class DFANode {

4544public:

    DFANodeTransitions transitions;

    bool hasFallbackTransition { false };

    bool isKilled { false };

    unsigned fallbackTransition;

    Vector<uint64_t> actions;

    
    // FIXME: Stop minimizing killed nodes and add ASSERT(!isKilled()) in many functions here.

    void kill()

    {

        ASSERT(m_flags != IsKilled);

        m_flags = IsKilled; // Killed nodes don't have any other flags.

        m_actionsStart = m_actionsLength = m_transitionsStart = m_transitionsLength = 0;

    };

    bool isKilled() const { return m_flags & IsKilled; }

    bool hasFallbackTransition() const { return m_flags & HasFallbackTransition; }

    bool hasActions() const { return !!m_actionsLength; }

    Vector<uint64_t> actions(const DFA&) const;

    uint32_t fallbackTransitionDestination(const DFA&) const;

    Vector<std::pair<uint8_t, uint32_t>> transitions(const DFA&) const;

    uint16_t transitionsLength() const { return m_transitionsLength; }

    void addFallbackTransition(DFA&, uint32_t destination);

    void setActions(uint32_t start, uint16_t length) { ASSERT(!m_actionsStart); ASSERT(!m_actionsLength); m_actionsStart = start; m_actionsLength = length; }

    void setTransitions(uint32_t start, uint16_t length) { ASSERT(!m_transitionsStart); ASSERT(!m_transitionsLength); m_transitionsStart = start; m_transitionsLength = length; }

    bool containsTransition(uint8_t, DFA&);

    uint32_t transitionsStart() { return m_transitionsStart; }

    void changeFallbackTransition(DFA&, uint32_t newDestination);

    void setHasFallbackTransitionWithoutChangingDFA(bool shouldHaveFallbackTransition)

    {

        if (shouldHaveFallbackTransition)

            m_flags |= HasFallbackTransition;

        else

            m_flags &= ~HasFallbackTransition;

    }

#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING

    Vector<unsigned> correspondingNFANodes;

#endif

private:

    uint32_t m_actionsStart { 0 };

    uint32_t m_transitionsStart { 0 };

    uint16_t m_actionsLength { 0 };

    uint8_t m_transitionsLength { 0 };

    uint8_t m_flags { 0 };

    const uint8_t HasFallbackTransition = 0x01;

    const uint8_t IsKilled = 0x02;

5586};

5687

// FIXME: Pack this down to 12.

// It's probably already 12 on ARMv7.

COMPILE_ASSERT(sizeof(DFANode) <= 16, Keep the DFANodes small);

}

} // namespace WebCore

183021

Source/WebCore/contentextensions/NFA.cpp

@@unsigned NFA::createNode()

    return nextId;

}

size_t NFA::memoryUsed() const

{

    size_t size = 0;

    for (const NFANode& node : m_nodes) {

        size += sizeof(node)

            + node.transitions.capacity() * sizeof(std::pair<uint16_t, NFANodeIndexSet>)

            + node.transitionsOnAnyCharacter.capacity() * sizeof(unsigned)

            + node.finalRuleIds.size() * sizeof(uint64_t);

    }

    return size;

}

void NFA::addTransition(unsigned from, unsigned to, char character)

{

    ASSERT(from < m_nodes.size());

183021

Source/WebCore/contentextensions/NFA.h

@@public:

#else

    void addRuleId(unsigned, uint64_t) { }

#endif

66 size_t memoryUsed() const;

private:

    friend class NFAToDFA;

183021

Source/WebCore/contentextensions/NFAToDFA.cpp

@@struct UniqueNodeIdSetHashHashTraits : p

typedef HashSet<std::unique_ptr<UniqueNodeIdSet>, UniqueNodeIdSetHash, UniqueNodeIdSetHashHashTraits> UniqueNodeIdSetTable;

struct NodeIdSetToUniqueNodeIdSetSource {

217 NodeIdSetToUniqueNodeIdSetSource(~~Vector<~~DFA~~Node>~~& dfa~~Graph~~, const Vector<NFANode>& nfaGraph, const NodeIdSet& nodeIdSet)

218 : dfa~~Graph~~(dfa~~Graph~~)

217 NodeIdSetToUniqueNodeIdSetSource(DFA& dfa, const Vector<NFANode>& nfaGraph, const NodeIdSet& nodeIdSet)

218 : dfa(dfa)

        , nfaGraph(nfaGraph)

        , nodeIdSet(nodeIdSet)

    {

@@struct NodeIdSetToUniqueNodeIdSetSource

            hash += nodeId;

        this->hash = DefaultHash<unsigned>::Hash::hash(hash);

    }

228 ~~Vector<~~DFA~~Node>~~& dfa~~Graph~~;

228 DFA& dfa;

    const Vector<NFANode>& nfaGraph;

    const NodeIdSet& nodeIdSet;

    unsigned hash;

@@struct NodeIdSetToUniqueNodeIdSetTransla

            newDFANode.correspondingNFANodes.append(nfaNodeId);

#endif

        }

257 copyToVector(actions, newDFANode.actions);

        
        unsigned actionsStart = source.dfa.actions.size();

        for (uint64_t action : actions)

            source.dfa.actions.append(action);

        unsigned actionsEnd = source.dfa.actions.size();

        unsigned actionsLength = actionsEnd - actionsStart;

        RELEASE_ASSERT_WITH_MESSAGE(actionsLength <= std::numeric_limits<uint16_t>::max(), "Too many actions for the current DFANode size.");

        newDFANode.setActions(actionsStart, static_cast<uint16_t>(actionsLength));

258265

259 unsigned dfaNodeId = source.dfa~~Graph~~.size();

260 source.dfa~~Graph~~.append(newDFANode);

266 unsigned dfaNodeId = source.dfa.nodes.size();

267 source.dfa.nodes.append(newDFANode);

        new (NotNull, &location) UniqueNodeIdSet(source.nodeIdSet, hash, dfaNodeId);

        ASSERT(location.impl());

@@static inline void populateTransitions(S

    }

}

331 static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const Vector<NFANode>& nfaGraph, ~~Vector<~~DFA~~Node>~~& dfa~~Graph~~, UniqueNodeIdSetTable& uniqueNodeIdSetTable, Vector<UniqueNodeIdSetImpl*>& unprocessedNodes)

338static ALWAYS_INLINE unsigned getOrCreateDFANode(const NodeIdSet& nfaNodeSet, const Vector<NFANode>& nfaGraph, DFA& dfa, UniqueNodeIdSetTable& uniqueNodeIdSetTable, Vector<UniqueNodeIdSetImpl*>& unprocessedNodes)

332339{

333 NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfa~~Graph~~, nfaGraph, nfaNodeSet);

340 NodeIdSetToUniqueNodeIdSetSource nodeIdSetToUniqueNodeIdSetSource(dfa, nfaGraph, nfaNodeSet);

    auto uniqueNodeIdAddResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(nodeIdSetToUniqueNodeIdSetSource);

    if (uniqueNodeIdAddResult.isNewEntry)

        unprocessedNodes.append(uniqueNodeIdAddResult.iterator->impl());

@@static ALWAYS_INLINE unsigned getOrCreat

DFA NFAToDFA::convert(NFA& nfa)

{

350 DFA dfa;

    Vector<NFANode>& nfaGraph = nfa.m_nodes;

    Vector<Vector<unsigned>> nfaNodeClosures;

@@DFA NFAToDFA::convert(NFA& nfa)

    UniqueNodeIdSetTable uniqueNodeIdSetTable;

353 Vector<DFANode> dfaGraph;

354 NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfaGraph, nfaGraph, initialSet);

361 NodeIdSetToUniqueNodeIdSetSource initialNodeIdSetToUniqueNodeIdSetSource(dfa, nfaGraph, initialSet);

    auto addResult = uniqueNodeIdSetTable.add<NodeIdSetToUniqueNodeIdSetTranslator>(initialNodeIdSetToUniqueNodeIdSetSource);

    Vector<UniqueNodeIdSetImpl*> unprocessedNodes;

@@DFA NFAToDFA::convert(NFA& nfa)

        NodeIdSet setFallbackTransition;

        populateTransitions(transitionsFromClosedSet, setFallbackTransition, *uniqueNodeIdSetImpl, nfaGraph, nfaNodeClosures);

376 unsigned transitionsStart = dfa.transitions.size();

        for (unsigned key = 0; key < transitionsFromClosedSet.size(); ++key) {

            NodeIdSet& targetNodeSet = transitionsFromClosedSet[key];

            if (targetNodeSet.isEmpty())

                continue;

            unsigned targetNodeId = getOrCreateDFANode(targetNodeSet, nfaGraph, dfaGraph, uniqueNodeIdSetTable, unprocessedNodes);

            const auto addResult = dfaGraph[dfaNodeId].transitions.add(key, targetNodeId);

            ASSERT_UNUSED(addResult, addResult.isNewEntry);

            unsigned targetNodeId = getOrCreateDFANode(targetNodeSet, nfaGraph, dfa, uniqueNodeIdSetTable, unprocessedNodes);

            RELEASE_ASSERT_WITH_MESSAGE(key <= std::numeric_limits<uint8_t>::max(), "ASCII transition should always fit in 8 bits");

            dfa.transitions.append(std::make_pair(static_cast<uint8_t>(key), targetNodeId));

            targetNodeSet.clear();

        }

        unsigned transitionsEnd = dfa.transitions.size();

        unsigned transitionsLength = transitionsEnd - transitionsStart;

        RELEASE_ASSERT_WITH_MESSAGE(transitionsLength <= std::numeric_limits<uint8_t>::max(), "ASCII transition count should always fit in 8 bits");

        dfa.nodes[dfaNodeId].setTransitions(transitionsStart, static_cast<uint8_t>(transitionsLength));

381394 if (!setFallbackTransition.isEmpty()) {

            unsigned targetNodeId = getOrCreateDFANode(setFallbackTransition, nfaGraph, dfaGraph, uniqueNodeIdSetTable, unprocessedNodes);

            DFANode& dfaSourceNode = dfaGraph[dfaNodeId];

            ASSERT(!dfaSourceNode.hasFallbackTransition);

            dfaSourceNode.hasFallbackTransition = true;

            dfaSourceNode.fallbackTransition = targetNodeId;

            unsigned targetNodeId = getOrCreateDFANode(setFallbackTransition, nfaGraph, dfa, uniqueNodeIdSetTable, unprocessedNodes);

            DFANode& dfaSourceNode = dfa.nodes[dfaNodeId];

            dfaSourceNode.addFallbackTransition(dfa, targetNodeId);

        }

    } while (!unprocessedNodes.isEmpty());

390 return ~~DFA(WTF::move(~~dfa~~Graph), 0)~~;

401 return dfa;

}

} // namespace ContentExtensions

183021

Tools/ChangeLog

2015-04-22  Alex Christensen  <achristensen@webkit.org>

        Use less memory when compiling content extensions.

        https://bugs.webkit.org/show_bug.cgi?id=144051

        Reviewed by NOBODY (OOPS!).

        * TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp:

        (TestWebKitAPI::countLiveNodes):

2015-04-22  Carlos Garcia Campos  <cgarcia@igalia.com>

        Unreviewed. Do not run GTK+ user media unit tests when ENABLE_MEDIA_STREAM is disabled.

183114

Tools/TestWebKitAPI/Tests/WebCore/DFAMinimizer.cpp

@@public:

unsigned countLiveNodes(const ContentExtensions::DFA& dfa)

{

    unsigned counter = 0;

49 for (u~~nsig~~ned ~~i = 0; i <~~ dfa.~~size(); ++i~~) {

50 if (!~~dfa.~~node~~At(i)~~.isKilled)

49 for (const auto& node : dfa.nodes) {

50 if (!node.isKilled())

            ++counter;

    }

    return counter;

183021