Flutter Engine
The Flutter Engine
Loading...
Searching...
No Matches
third_party
skia
src
sksl
lex
NFA.h
Go to the documentation of this file.
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 "
src/sksl/lex/NFAState.h
"
12
#include "
src/sksl/lex/RegexNode.h
"
13
14
#include <string>
15
#include <utility>
16
#include <vector>
17
18
/**
19
* A nondeterministic finite automaton for matching regular expressions. The NFA is initialized with
20
* a number of regular expressions, and then matches a string against all of them simultaneously.
21
*/
22
struct
NFA
{
23
/**
24
* Adds a new regular expression to the set of expressions matched by this automaton, returning
25
* its index.
26
*/
27
int
addRegex
(
const
RegexNode
& regex) {
28
std::vector<int> accept;
29
// we reserve token 0 for END_OF_FILE, so this starts at 1
30
accept.push_back(this->
addState
(
NFAState
(++
fRegexCount
)));
31
std::vector<int> startStates = regex.createStates(
this
, accept);
32
fStartStates
.insert(
fStartStates
.end(), startStates.begin(), startStates.end());
33
return
fStartStates
.size() - 1;
34
}
35
36
/**
37
* Adds a new state to the NFA, returning its index.
38
*/
39
int
addState
(
NFAState
s
) {
40
fStates
.push_back(std::move(
s
));
41
return
fStates
.size() - 1;
42
}
43
44
/**
45
* Matches a string against all of the regexes added to this NFA. Returns the index of the first
46
* (in addRegex order) matching expression, or -1 if no match. This is relatively slow and used
47
* only for debugging purposes; the NFA should be converted to a DFA before actual use.
48
*/
49
int
match
(std::string
s
)
const
;
50
51
int
fRegexCount
= 0;
52
53
std::vector<NFAState>
fStates
;
54
55
std::vector<int>
fStartStates
;
56
};
57
58
#endif
NFAState.h
RegexNode.h
s
struct MyStruct s
NFAState
Definition
NFAState.h:16
NFA
Definition
NFA.h:22
NFA::fStartStates
std::vector< int > fStartStates
Definition
NFA.h:55
NFA::addState
int addState(NFAState s)
Definition
NFA.h:39
NFA::addRegex
int addRegex(const RegexNode ®ex)
Definition
NFA.h:27
NFA::fStates
std::vector< NFAState > fStates
Definition
NFA.h:53
NFA::match
int match(std::string s) const
Definition
NFA.cpp:13
NFA::fRegexCount
int fRegexCount
Definition
NFA.h:51
RegexNode
Definition
RegexNode.h:20
Generated on Fri Apr 26 2024 06:17:33 for Flutter Engine by
1.9.8