NFA::Machine Struct Reference

#include <NFA.h>

Public Member Functions
	Machine ()
	~Machine ()
	Machine (Machine &&inMachine)
void	operator= (Machine &&inMachine)
	Machine (Builder *inBuilder)
StateIndex	feed (const char *&nextChar) const
std::string	dumpDFAGraphViz () const

Detailed Description

Definition at line 37 of file NFA.h.

Constructor & Destructor Documentation

Machine() [1/3]

NFA::Machine::Machine ( )

inline

Definition at line 39 of file NFA.h.

: stateAndOffsetToNextStateMap(nullptr), numClasses(0), numStates(0) {}

~Machine()

NFA::Machine::~Machine

(

)

Definition at line 379 of file NFA.cpp.

    {
        if(stateAndOffsetToNextStateMap)
        {
            delete [] stateAndOffsetToNextStateMap;
            stateAndOffsetToNextStateMap = nullptr;
        }
    }

Machine() [2/3]

NFA::Machine::Machine ( Machine && inMachine )

inline

Definition at line 42 of file NFA.h.

{ moveFrom(std::move(inMachine)); }

Machine() [3/3]

NFA::Machine::Machine

(

Builder *

inBuilder

)

Definition at line 319 of file NFA.cpp.

    {
        // Convert the NFA constructed by the builder to a DFA.
        std::vector<DFAState> dfaStates = convertToDFA(builder);
        WAVM_ASSERT_THROW(dfaStates.size() <= internalMaxStates);
        delete builder;
        
        Timing::Timer timer;
 
        // Transpose the [state][character] transition map to [character][state].
        std::vector<StateTransitionsByChar> stateTransitionsByChar;
        for(Uptr charIndex = 0;charIndex < 256;++charIndex)
        {
            stateTransitionsByChar.push_back(StateTransitionsByChar((U8)charIndex,dfaStates.size()));
            stateTransitionsByChar[charIndex].nextStateByInitialState = new StateIndex[dfaStates.size()];
            for(Uptr stateIndex = 0;stateIndex < dfaStates.size();++stateIndex)
            { stateTransitionsByChar[charIndex].nextStateByInitialState[stateIndex] = dfaStates[stateIndex].nextStateByChar[charIndex]; }
        }
 
        // Sort the [character][state] transition map by the [state] column.
        numStates = dfaStates.size();
        std::sort(stateTransitionsByChar.begin(),stateTransitionsByChar.end());
 
        // Build a minimal set of character equivalence classes that have the same transition across all states.
        U8 characterToClassMap[256];
        U8 representativeCharsByClass[256];
        numClasses = 1;
        characterToClassMap[stateTransitionsByChar[0].c] = 0;
        representativeCharsByClass[0] = stateTransitionsByChar[0].c;
        for(Uptr charIndex = 1;charIndex < stateTransitionsByChar.size();++charIndex)
        {
            if(stateTransitionsByChar[charIndex] != stateTransitionsByChar[charIndex-1])
            {
                representativeCharsByClass[numClasses] = stateTransitionsByChar[charIndex].c;
                ++numClasses;
            }
            characterToClassMap[stateTransitionsByChar[charIndex].c] = U8(numClasses - 1);
        }
 
        // Build a [charClass][state] transition map.
        stateAndOffsetToNextStateMap = new InternalStateIndex[numClasses * numStates];
        for(Uptr classIndex = 0;classIndex < numClasses;++classIndex)
        {
            for(Uptr stateIndex = 0;stateIndex < numStates;++stateIndex)
            {
                stateAndOffsetToNextStateMap[stateIndex + classIndex * numStates] = InternalStateIndex(dfaStates[stateIndex].nextStateByChar[representativeCharsByClass[classIndex]]);
            }
        }
 
        // Build a map from character index to offset into [charClass][initialState] transition map.
        WAVM_ASSERT_THROW((numClasses - 1) * (numStates - 1) <= UINT32_MAX);
        for(Uptr charIndex = 0;charIndex < 256;++charIndex)
        {
            charToOffsetMap[charIndex] = U32(numStates * characterToClassMap[charIndex]);
        }
 
        Timing::logTimer("reduced DFA character classes",timer);
        Log::printf(Log::Category::metrics,"  reduced DFA character classes to %u\n",numClasses);
    }

Here is the call graph for this function:

Member Function Documentation

dumpDFAGraphViz()

std::string NFA::Machine::dumpDFAGraphViz

(

)

const

Definition at line 510 of file NFA.cpp.

    {
        std::string result;
        result += "digraph {\n";
        std::set<StateIndex> terminalStates;
 
        CharSet* classCharSets = (CharSet*)alloca(sizeof(CharSet) * numClasses);
        memset(classCharSets,0,sizeof(CharSet) * numClasses);
        for(Uptr charIndex = 0;charIndex < 256;++charIndex)
        {
            const Uptr classIndex = charToOffsetMap[charIndex] / numStates;
            classCharSets[classIndex].add((U8)charIndex);
        }
    
        {
            std::map<StateIndex,CharSet> transitions;
            for(Uptr classIndex = 0;classIndex < numClasses;++classIndex)
            {
                const InternalStateIndex nextState = stateAndOffsetToNextStateMap[0 + classIndex * numStates];
                CharSet& transitionPredicate = transitions[nextState];
                transitionPredicate = classCharSets[classIndex] | transitionPredicate;
            }
 
            Uptr startIndex = 0;
            for(auto transitionPair : transitions)
            {
                if((transitionPair.first & ~edgeDoesntConsumeInputFlag) != unmatchedCharacterTerminal)
                {
                    result += "start" + std::to_string(startIndex) + "[shape=triangle label=\"\"];\n";
 
                    std::string edgeLabel = getGraphEdgeLabel(transitionPair.second);
                    std::string nextStateName = transitionPair.first < 0
                        ? "terminal" + std::to_string(-(transitionPair.first & ~edgeDoesntConsumeInputFlag))
                        : "state" + std::to_string(transitionPair.first);
                    result += "start" + std::to_string(startIndex)
                        + " -> "
                        + nextStateName + "[label=\""
                        + (transitionPair.first < 0 && (transitionPair.first & edgeDoesntConsumeInputFlag) != 0 ? "&epsilon; " : "")
                        + escapeString(edgeLabel) + "\"];\n";
 
                    if(transitionPair.first < 0)
                    {
                        terminalStates.emplace(StateIndex(transitionPair.first & ~edgeDoesntConsumeInputFlag));
                    }
 
                    ++startIndex;
                }
            }
        }
 
        for(Uptr stateIndex = 1;stateIndex < numStates;++stateIndex)
        {
            result += "state" + std::to_string(stateIndex) + "[shape=square label=\"" + std::to_string(stateIndex) + "\"];\n";
 
            std::map<StateIndex,CharSet> transitions;
            for(Uptr classIndex = 0;classIndex < numClasses;++classIndex)
            {
                const InternalStateIndex nextState = stateAndOffsetToNextStateMap[stateIndex + classIndex * numStates];
                CharSet& transitionPredicate = transitions[nextState];
                transitionPredicate = classCharSets[classIndex] | transitionPredicate;
            }
 
            for(auto transitionPair : transitions)
            {
                if((transitionPair.first & ~edgeDoesntConsumeInputFlag) != unmatchedCharacterTerminal)
                {
                    std::string edgeLabel = getGraphEdgeLabel(transitionPair.second);
                    std::string nextStateName = transitionPair.first < 0
                        ? "terminal" + std::to_string(-(transitionPair.first & ~edgeDoesntConsumeInputFlag))
                        : "state" + std::to_string(transitionPair.first);
                    result += "state" + std::to_string(stateIndex)
                        + " -> "
                        + nextStateName + "[label=\""
                        + (transitionPair.first < 0 && (transitionPair.first & edgeDoesntConsumeInputFlag) != 0 ? "&epsilon; " : "")
                        + escapeString(edgeLabel) + "\"];\n";
 
                    if(transitionPair.first < 0)
                    {
                        terminalStates.emplace(transitionPair.first);
                    }
                }
            }
        }
        for(auto terminalState : terminalStates)
        {
            result += "terminal" + std::to_string(-(terminalState & ~edgeDoesntConsumeInputFlag))
                + "[shape=octagon label=\"" + std::to_string(maximumTerminalStateIndex - (terminalState & ~edgeDoesntConsumeInputFlag)) + "\"];\n";
        }
        result += "}\n";
        return result;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

feed()

StateIndex NFA::Machine::feed ( const char *& nextChar ) const

inline

Definition at line 51 of file NFA.h.

        {
            Iptr state = 0;
            do
            {
                state = stateAndOffsetToNextStateMap[state + charToOffsetMap[(U8)nextChar[0]]];
                if(state < 0) { nextChar += 1; break; }
                state = stateAndOffsetToNextStateMap[state + charToOffsetMap[(U8)nextChar[1]]];
                if(state < 0) { nextChar += 2; break; }
                state = stateAndOffsetToNextStateMap[state + charToOffsetMap[(U8)nextChar[2]]];
                if(state < 0) { nextChar += 3; break; }
                state = stateAndOffsetToNextStateMap[state + charToOffsetMap[(U8)nextChar[3]]];
                nextChar += 4;
            }
            while(state >= 0);
            if(state & edgeDoesntConsumeInputFlag)
            {
                --nextChar;
                state &= ~edgeDoesntConsumeInputFlag;
            }
            return (StateIndex)state;
        }

Here is the caller graph for this function:

operator=()

void NFA::Machine::operator= ( Machine && inMachine )

inline

Definition at line 43 of file NFA.h.

{ moveFrom(std::move(inMachine)); }

---

The documentation for this struct was generated from the following files:

• libraries/wasm-jit/Source/WAST/NFA.h
• libraries/wasm-jit/Source/WAST/NFA.cpp