NFA Namespace Reference

Classes
struct	Builder
struct	DFAState
struct	Machine
struct	NFAState
struct	StateTransitionsByChar

Typedefs
typedef std::vector< StateIndex >	StateSet
typedef DenseStaticIntSet< U8, 256 >	CharSet
typedef I16	StateIndex

Enumerations
enum	{ edgeDoesntConsumeInputFlag = (StateIndex)0x4000 , unmatchedCharacterTerminal = (StateIndex)0x8000 , maximumTerminalStateIndex = (StateIndex)0xbfff }

Functions
template<typename Element >
void	addUnique (std::vector< Element > &vector, const Element &element)
Builder *	createBuilder ()
StateIndex	addState (Builder *builder)
void	addEdge (Builder *builder, StateIndex initialState, const CharSet &predicate, StateIndex nextState)
void	addEpsilonEdge (Builder *builder, StateIndex initialState, StateIndex nextState)
StateIndex	getNonTerminalEdge (Builder *builder, StateIndex initialState, char c)
std::vector< DFAState >	convertToDFA (Builder *builder)
char	nibbleToHexChar (U8 value)
std::string	escapeString (const std::string &string)
std::string	getGraphEdgeCharLabel (Uptr charIndex)
std::string	getGraphEdgeLabel (const CharSet &charSet)
std::string	dumpNFAGraphViz (const Builder *builder)

Typedef Documentation

CharSet

typedef DenseStaticIntSet<U8,256> NFA::CharSet

Definition at line 11 of file NFA.h.

StateIndex

typedef I16 NFA::StateIndex

Definition at line 14 of file NFA.h.

StateSet

typedef std::vector<StateIndex> NFA::StateSet

Definition at line 14 of file NFA.cpp.

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
edgeDoesntConsumeInputFlag
unmatchedCharacterTerminal
maximumTerminalStateIndex

Definition at line 16 of file NFA.h.

    {
        edgeDoesntConsumeInputFlag = (StateIndex)0x4000, // A flag that's set on terminal DFA state transitions that don't consume any input
        unmatchedCharacterTerminal = (StateIndex)0x8000, // An implicit terminal state that indicates the DFA didn't recognize the input
        maximumTerminalStateIndex = (StateIndex)0xbfff, // Should be the largest negative number that doesn't have edgeDoesntConsumeInputFlag set.
    };

Function Documentation

addEdge()

void NFA::addEdge	(	Builder *	builder,
		StateIndex	initialState,
		const CharSet &	predicate,
		StateIndex	nextState )

Definition at line 54 of file NFA.cpp.

    {
        CharSet& transitionPredicate = builder->nfaStates[initialState].nextStateToPredicateMap[nextState];
        transitionPredicate = transitionPredicate | predicate;
    }

addEpsilonEdge()

void NFA::addEpsilonEdge	(	Builder *	builder,
		StateIndex	initialState,
		StateIndex	nextState )

Definition at line 60 of file NFA.cpp.

    {
        addUnique(builder->nfaStates[initialState].epsilonNextStates,nextState);
    }

Here is the call graph for this function:

addState()

StateIndex NFA::addState

(

Builder *

builder

)

Definition at line 47 of file NFA.cpp.

    {
        WAVM_ASSERT_THROW(builder->nfaStates.size() < INT16_MAX);
        builder->nfaStates.emplace_back();
        return StateIndex(builder->nfaStates.size() - 1);
    }

Here is the caller graph for this function:

addUnique()

template<typename Element >

void NFA::addUnique	(	std::vector< Element > &	vector,
		const Element &	element )

Definition at line 17 of file NFA.cpp.

    {
        for(const auto& existingElement : vector)
        {
            if(existingElement == element)
            {
                return;
            }
        }
        vector.push_back(element);
    }

Here is the caller graph for this function:

convertToDFA()

std::vector< DFAState > NFA::convertToDFA

(

Builder *

builder

)

Definition at line 90 of file NFA.cpp.

    {
        Timing::Timer timer;
 
        std::vector<DFAState> dfaStates;
        std::map<StateSet,StateIndex> nfaStateSetToDFAStateMap;
        std::vector<StateSet> dfaStateToNFAStateSetMap;
        std::vector<StateIndex> pendingDFAStates;
 
        nfaStateSetToDFAStateMap.emplace(StateSet {0},(StateIndex)0);
        dfaStateToNFAStateSetMap.emplace_back(StateSet {0});
        dfaStates.emplace_back();
        pendingDFAStates.push_back((StateIndex)0);
 
        Uptr maxLocalStates = 0;
        Uptr maxDFANextStates = 0;
 
        while(pendingDFAStates.size())
        {
            const StateIndex currentDFAStateIndex = pendingDFAStates.back();
            pendingDFAStates.pop_back();
        
            const StateSet currentStateSet = dfaStateToNFAStateSetMap[currentDFAStateIndex];
 
            // Expand the set of current states to include all states reachable by epsilon transitions from the current states.
            StateSet epsilonClosureCurrentStateSet = currentStateSet;
            for(Uptr scanIndex = 0;scanIndex < epsilonClosureCurrentStateSet.size();++scanIndex)
            {
                StateIndex scanState = epsilonClosureCurrentStateSet[scanIndex];
                if(scanState >= 0)
                {
                    for(auto epsilonNextState : builder->nfaStates[scanState].epsilonNextStates)
                    {
                        addUnique(epsilonClosureCurrentStateSet,epsilonNextState);
                    }
                }
            }
 
            // Find the subset of the non-terminal states in the current set.
            StateSet nonTerminalCurrentStateSet;
            StateIndex currentTerminalState = unmatchedCharacterTerminal | edgeDoesntConsumeInputFlag;
            bool hasCurrentTerminalState = false;
            for(auto stateIndex : epsilonClosureCurrentStateSet)
            {
                if(stateIndex >= 0)
                {
                    addUnique(nonTerminalCurrentStateSet,stateIndex);
                }
                else
                {
                    if(hasCurrentTerminalState)
                    {
                        Errors::fatalf("NFA has multiple possible terminal states for the same input");
                    }
                    hasCurrentTerminalState = true;
                    currentTerminalState = stateIndex | edgeDoesntConsumeInputFlag;
                }
            }
 
            // Build a compact index of the states following all states in the current set.
            std::map<StateIndex,StateIndex> stateIndexToLocalStateIndexMap;
            std::vector<StateIndex> localStateIndexToStateIndexMap;
            for(auto stateIndex : nonTerminalCurrentStateSet)
            {
                const NFAState& nfaState = builder->nfaStates[stateIndex];
                for(auto transition : nfaState.nextStateToPredicateMap)
                {
                    if(!stateIndexToLocalStateIndexMap.count(transition.first))
                    {
                        stateIndexToLocalStateIndexMap.emplace(transition.first,(StateIndex)localStateIndexToStateIndexMap.size());
                        localStateIndexToStateIndexMap.emplace_back(transition.first);
                    }
                }
            }
 
            if(!stateIndexToLocalStateIndexMap.count(currentTerminalState))
            {
                stateIndexToLocalStateIndexMap.emplace(currentTerminalState,(StateIndex)localStateIndexToStateIndexMap.size());
                localStateIndexToStateIndexMap.emplace_back(currentTerminalState);
            }
        
            enum { numSupportedLocalStates = 64 };
            typedef DenseStaticIntSet<StateIndex,numSupportedLocalStates> LocalStateSet;
 
            const Uptr numLocalStates = stateIndexToLocalStateIndexMap.size();
            WAVM_ASSERT_THROW(numLocalStates <= numSupportedLocalStates);
            maxLocalStates = std::max<Uptr>(maxLocalStates,numLocalStates);
 
            // Combine the [nextState][char] transition maps for current states and transpose to [char][nextState]
            // After building the compact index of referenced states, the nextState set can be represented as a 64-bit mask.
            LocalStateSet charToLocalStateSet[256];
            for(auto stateIndex : nonTerminalCurrentStateSet)
            {
                const NFAState& nfaState = builder->nfaStates[stateIndex];
                for(auto transition : nfaState.nextStateToPredicateMap)
                {
                    for(Uptr charIndex = 0;charIndex < 256;++charIndex)
                    {
                        if(transition.second.contains((char)charIndex))
                        {
                            charToLocalStateSet[charIndex].add(stateIndexToLocalStateIndexMap.at(transition.first));
                        }
                    }
                }
            }
        
            const LocalStateSet currentTerminalStateLocalSet(stateIndexToLocalStateIndexMap.at(currentTerminalState));
            for(Uptr charIndex = 0;charIndex < 256;++charIndex)
            {
                if(charToLocalStateSet[charIndex].isEmpty())
                {
                    charToLocalStateSet[charIndex] = currentTerminalStateLocalSet;
                }
            }
 
            // Find the set of unique local state sets that follow this state set.
            std::vector<LocalStateSet> uniqueLocalNextStateSets;
            for(Uptr charIndex = 0;charIndex < 256;++charIndex)
            {
                const LocalStateSet localStateSet = charToLocalStateSet[charIndex];
                if(!localStateSet.isEmpty())
                {
                    addUnique(uniqueLocalNextStateSets,localStateSet);
                }
            }
 
            // For each unique local state set that follows this state set, find or create a corresponding DFA state.
            std::map<LocalStateSet,StateIndex> localStateSetToDFAStateIndexMap;
            for(auto localNextStateSet : uniqueLocalNextStateSets)
            {
                // Convert the local state set bit mask to a global NFA state set.
                StateSet nextStateSet;
                {
                    LocalStateSet residualLocalStateSet = localNextStateSet;
                    while(true)
                    {
                        const StateIndex localStateIndex = residualLocalStateSet.getSmallestMember();
                        if(localStateIndex == numSupportedLocalStates) { break; }
 
                        nextStateSet.push_back(localStateIndexToStateIndexMap.at(localStateIndex));
                        residualLocalStateSet.remove(localStateIndex);
                    };
                }
 
                if(nextStateSet.size() == 1 && *nextStateSet.begin() < 0)
                {
                    localStateSetToDFAStateIndexMap.insert(std::make_pair(localNextStateSet,*nextStateSet.begin()));
                }
                else
                {
                    // Find an existing DFA state corresponding to this NFA state set.
                    auto nextDFAStateIt = nfaStateSetToDFAStateMap.find(nextStateSet);
                    StateIndex nextDFAStateIndex;
                    if(nextDFAStateIt != nfaStateSetToDFAStateMap.end())
                    {
                        localStateSetToDFAStateIndexMap.emplace(localNextStateSet,nextDFAStateIt->second);
                    }
                    else
                    {
                        // If no corresponding DFA state existing yet, create a new one and add it to the queue
                        // of pending states to process.
                        nextDFAStateIndex = (StateIndex)dfaStates.size();
                        localStateSetToDFAStateIndexMap.emplace(localNextStateSet,nextDFAStateIndex);
                        nfaStateSetToDFAStateMap.insert(std::make_pair(nextStateSet,nextDFAStateIndex));
                        dfaStateToNFAStateSetMap.emplace_back(nextStateSet);
                        dfaStates.emplace_back();
                        pendingDFAStates.push_back(nextDFAStateIndex);
                    }
                }           
            }
 
            // Set up the DFA transition map.
            DFAState& dfaState = dfaStates[nfaStateSetToDFAStateMap[currentStateSet]];
            for(auto localStateSetToDFAStateIndex : localStateSetToDFAStateIndexMap)
            {
                const LocalStateSet localStateSet = localStateSetToDFAStateIndex.first;
                const StateIndex nextDFAStateIndex = localStateSetToDFAStateIndex.second;
                for(Uptr charIndex = 0;charIndex < 256;++charIndex)
                {
                    if(charToLocalStateSet[charIndex] == localStateSet)
                    {
                        dfaState.nextStateByChar[charIndex] = nextDFAStateIndex;
                    }
                }
            }
            maxDFANextStates = std::max(maxDFANextStates,(Uptr)uniqueLocalNextStateSets.size());
        };
        
        Timing::logTimer("translated NFA->DFA",timer);
        Log::printf(Log::Category::metrics,"  translated NFA with %u states to DFA with %u states\n",builder->nfaStates.size(),dfaStates.size());
        Log::printf(Log::Category::metrics,"  maximum number of states following a NFA state set: %u\n",maxLocalStates);
        Log::printf(Log::Category::metrics,"  maximum number of states following a DFA state: %u\n",maxDFANextStates);
 
        return dfaStates;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

createBuilder()

Builder * NFA::createBuilder

(

)

Definition at line 40 of file NFA.cpp.

    {
        auto builder = new Builder();
        addState(builder);
        return builder;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

dumpNFAGraphViz()

std::string NFA::dumpNFAGraphViz

(

const Builder *

builder

)

Definition at line 467 of file NFA.cpp.

    {
        std::string result;
        result += "digraph {\n";
        std::set<StateIndex> terminalStates;
        for(Uptr stateIndex = 0;stateIndex < builder->nfaStates.size();++stateIndex)
        {
            const NFAState& nfaState = builder->nfaStates[stateIndex];
 
            result += "state" + std::to_string(stateIndex) + "[shape=square label=\"" + std::to_string(stateIndex) + "\"];\n";
 
            for(const auto& statePredicatePair : nfaState.nextStateToPredicateMap)
            {
                std::string edgeLabel = getGraphEdgeLabel(statePredicatePair.second);
                std::string nextStateName = statePredicatePair.first < 0
                    ? "terminal" + std::to_string(-statePredicatePair.first)
                    : "state" + std::to_string(statePredicatePair.first);
                result += "state" + std::to_string(stateIndex)
                    + " -> "
                    + nextStateName + "[label=\"" + escapeString(edgeLabel) + "\"];\n";
                if(statePredicatePair.first < 0)
                {
                    terminalStates.emplace(statePredicatePair.first);
                }
            }
 
            for(auto epsilonNextState : nfaState.epsilonNextStates)
            {
                std::string nextStateName = epsilonNextState < 0
                    ? "terminal" + std::to_string(-epsilonNextState)
                    : "state" + std::to_string(epsilonNextState);
                result += "state" + std::to_string(stateIndex) + " -> " + nextStateName + "[label=\"&epsilon;\"];\n";
            }
        }
        for(auto terminalState : terminalStates)
        {
            result += "terminal" + std::to_string(-terminalState)
                + "[shape=octagon label=\"" + std::to_string(maximumTerminalStateIndex - terminalState) + "\"];\n";
        }
        result += "}\n";
        return result;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

escapeString()

std::string NFA::escapeString

(

const std::string &

string

)

Definition at line 399 of file NFA.cpp.

    {
        std::string result;
        for(Uptr charIndex = 0;charIndex < string.size();++charIndex)
        {
            auto c = string[charIndex];
            if(c == '\\') { result += "\\\\"; }
            else if(c == '\"') { result += "\\\""; }
            else if(c == '\n') { result += "\\n"; }
            else if(c < 0x20 || c > 0x7e)
            {
                result += "\\\\";
                result += nibbleToHexChar((c & 0xf0) >> 4);
                result += nibbleToHexChar((c & 0x0f) >> 0);
            }
            else { result += c; }
        }
        return result;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

getGraphEdgeCharLabel()

std::string NFA::getGraphEdgeCharLabel

(

Uptr

charIndex

)

Definition at line 419 of file NFA.cpp.

    {
        switch(charIndex)
        {
        case '^': return "\\^";
        case '\f': return "\\f";
        case '\r': return "\\r";
        case '\n': return "\\n";
        case '\t': return "\\t";
        case '\'': return "\\\'";
        case '\"': return "\\\"";
        case '\\': return "\\\\";
        case '-': return "\\-";
        default: return std::string(1,(char)charIndex);
        };
    }

Here is the caller graph for this function:

getGraphEdgeLabel()

std::string NFA::getGraphEdgeLabel

(

const CharSet &

charSet

)

Definition at line 436 of file NFA.cpp.

    {
        std::string edgeLabel;
        U8 numSetChars = 0;
        for(Uptr charIndex = 0;charIndex < 256;++charIndex)
        {
            if(charSet.contains((char)charIndex)) { ++numSetChars; }
        }
        if(numSetChars > 1) { edgeLabel += "["; }
        const bool isNegative = numSetChars >= 100;
        if(isNegative) { edgeLabel += "^"; }
        for(Uptr charIndex = 0;charIndex < 256;++charIndex)
        {
            if(charSet.contains((char)charIndex) != isNegative)
            {
                edgeLabel += getGraphEdgeCharLabel(charIndex);
                if(charIndex + 2 < 256
                && charSet.contains((char)charIndex+1) != isNegative
                && charSet.contains((char)charIndex+2) != isNegative)
                {
                    edgeLabel += "-";
                    charIndex += 2;
                    while(charIndex + 1 < 256 && charSet.contains((char)charIndex+1) != isNegative) { ++charIndex; }
                    edgeLabel += getGraphEdgeCharLabel(charIndex);
                }
            }
        }
        if(numSetChars > 1) { edgeLabel += "]"; }
        return edgeLabel;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

getNonTerminalEdge()

StateIndex NFA::getNonTerminalEdge	(	Builder *	builder,
		StateIndex	initialState,
		char	c )

Definition at line 65 of file NFA.cpp.

    {
        for(const auto& nextStateToPredicatePair : builder->nfaStates[initialState].nextStateToPredicateMap)
        {
            if(nextStateToPredicatePair.first >= 0 && nextStateToPredicatePair.second.contains((U8)c))
            {
                return nextStateToPredicatePair.first;
            }
        }
 
        return unmatchedCharacterTerminal;
    }

nibbleToHexChar()

char NFA::nibbleToHexChar

(

U8

value

)

Definition at line 397 of file NFA.cpp.

{ return value < 10 ? ('0' + value) : 'a' + value - 10; }

Here is the caller graph for this function: