1 /*
2  * Copyright 2017 Google Inc.
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 
8 #ifndef SKSL_NFA
9 #define SKSL_NFA
10 
11 #include "NFAState.h"
12 #include "RegexNode.h"
13 
14 /**
15  * A nondeterministic finite automaton for matching regular expressions. The NFA is initialized with
16  * a number of regular expressions, and then matches a string against all of them simultaneously.
17  */
18 struct NFA {
19     /**
20      * Adds a new regular expression to the set of expressions matched by this automaton, returning
21      * its index.
22      */
addRegexNFA23     int addRegex(const RegexNode& regex) {
24         std::vector<int> accept;
25         // we reserve token 0 for END_OF_FILE, so this starts at 1
26         accept.push_back(this->addState(NFAState(++fRegexCount)));
27         std::vector<int> startStates = regex.createStates(this, accept);
28         fStartStates.insert(fStartStates.end(), startStates.begin(), startStates.end());
29         return fStartStates.size() - 1;
30     }
31 
32     /**
33      * Adds a new state to the NFA, returning its index.
34      */
addStateNFA35     int addState(NFAState s) {
36         fStates.push_back(std::move(s));
37         return fStates.size() - 1;
38     }
39 
40     /**
41      * Matches a string against all of the regexes added to this NFA. Returns the index of the first
42      * (in addRegex order) matching expression, or -1 if no match. This is relatively slow and used
43      * only for debugging purposes; the NFA should be converted to a DFA before actual use.
44      */
45     int match(std::string s) const;
46 
47     int fRegexCount = 0;
48 
49     std::vector<NFAState> fStates;
50 
51     std::vector<int> fStartStates;
52 };
53 
54 #endif
55