Flutter Engine
The Flutter Engine
NFAState.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_NFASTATE
9#define SKSL_NFASTATE
10
11#include <string>
12#include <vector>
13
15
16struct NFAState {
17 enum Kind {
18 // represents an accept state - if the NFA ends up in this state, we have successfully
19 // matched the token indicated by fData[0]
21 // matches the single character fChar
23 // the regex '.'; matches any char but '\n'
25 // a state which serves as a placeholder for the states indicated in fData. When we
26 // transition to this state, we instead transition to all of the fData states.
28 // contains a list of true/false values in fData. fData[c] tells us whether we accept the
29 // character c.
31 };
32
33 NFAState(Kind kind, std::vector<int> next)
34 : fKind(kind)
35 , fNext(std::move(next)) {}
36
37 NFAState(char c, std::vector<int> next)
39 , fChar(c)
40 , fNext(std::move(next)) {}
41
42 NFAState(std::vector<int> states)
44 , fData(std::move(states)) {}
45
46 NFAState(bool inverse, std::vector<bool> accepts, std::vector<int> next)
48 , fInverse(inverse)
49 , fNext(std::move(next)) {
50 for (bool b : accepts) {
51 fData.push_back(b);
52 }
53 }
54
55 NFAState(int token)
57 fData.push_back(token);
58 }
59
60 bool accept(char c) const {
61 switch (fKind) {
62 case kAccept_Kind:
63 return false;
64 case kChar_Kind:
65 return c == fChar;
66 case kDot_Kind:
67 return c != '\n';
68 case kTable_Kind: {
69 bool value;
70 if ((size_t) c < fData.size()) {
71 value = fData[c];
72 } else {
73 value = false;
74 }
75 return value != fInverse;
76 }
77 default:
79 }
80 }
81
82#ifdef SK_DEBUG
83 std::string description() const {
84 switch (fKind) {
85 case kAccept_Kind:
86 return "Accept(" + std::to_string(fData[0]) + ")";
87 case kChar_Kind: {
88 std::string result = "Char('" + std::string(1, fChar) + "'";
89 for (int v : fNext) {
90 result += ", ";
92 }
93 result += ")";
94 return result;
95 }
96 case kDot_Kind: {
97 std::string result = "Dot(";
98 const char* separator = "";
99 for (int v : fNext) {
100 result += separator;
102 separator = ", ";
103 }
104 result += ")";
105 return result;
106 }
107 case kRemapped_Kind: {
108 std::string result = "Remapped(";
109 const char* separator = "";
110 for (int v : fData) {
111 result += separator;
113 separator = ", ";
114 }
115 result += ")";
116 return result;
117 }
118 case kTable_Kind: {
119 std::string result = std::string("Table(") + (fInverse ? "true" : "false") + ", [";
120 const char* separator = "";
121 for (int v : fData) {
122 result += separator;
123 result += v ? "true" : "false";
124 separator = ", ";
125 }
126 result += "]";
127 for (int n : fNext) {
128 result += ", ";
130 }
131 result += ")";
132 return result;
133 }
134 default:
136 }
137 }
138#endif
139
141
142 char fChar = 0;
143
144 bool fInverse = false;
145
146 std::vector<int> fData;
147
148 // states we transition to upon a succesful match from this state
149 std::vector<int> fNext;
150};
151
152#endif
static float next(float f)
#define SkUNREACHABLE
Definition: SkAssert.h:135
static bool b
uint8_t value
GAsyncResult * result
Definition: ref_ptr.h:256
static SkString to_string(int n)
Definition: nanobench.cpp:119
std::vector< int > fData
Definition: NFAState.h:146
NFAState(int token)
Definition: NFAState.h:55
@ kChar_Kind
Definition: NFAState.h:22
@ kTable_Kind
Definition: NFAState.h:30
@ kRemapped_Kind
Definition: NFAState.h:27
@ kDot_Kind
Definition: NFAState.h:24
@ kAccept_Kind
Definition: NFAState.h:20
std::vector< int > fNext
Definition: NFAState.h:149
bool fInverse
Definition: NFAState.h:144
NFAState(Kind kind, std::vector< int > next)
Definition: NFAState.h:33
NFAState(std::vector< int > states)
Definition: NFAState.h:42
Kind fKind
Definition: NFAState.h:140
char fChar
Definition: NFAState.h:142
NFAState(bool inverse, std::vector< bool > accepts, std::vector< int > next)
Definition: NFAState.h:46
NFAState(char c, std::vector< int > next)
Definition: NFAState.h:37
bool accept(char c) const
Definition: NFAState.h:60