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 14 #include "src/sksl/lex/LexUtil.h" 15 16 struct 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] 20 kAccept_Kind, 21 // matches the single character fChar 22 kChar_Kind, 23 // the regex '.'; matches any char but '\n' 24 kDot_Kind, 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. 27 kRemapped_Kind, 28 // contains a list of true/false values in fData. fData[c] tells us whether we accept the 29 // character c. 30 kTable_Kind 31 }; 32 NFAStateNFAState33 NFAState(Kind kind, std::vector<int> next) 34 : fKind(kind) 35 , fNext(std::move(next)) {} 36 NFAStateNFAState37 NFAState(char c, std::vector<int> next) 38 : fKind(kChar_Kind) 39 , fChar(c) 40 , fNext(std::move(next)) {} 41 NFAStateNFAState42 NFAState(std::vector<int> states) 43 : fKind(kRemapped_Kind) 44 , fData(std::move(states)) {} 45 NFAStateNFAState46 NFAState(bool inverse, std::vector<bool> accepts, std::vector<int> next) 47 : fKind(kTable_Kind) 48 , fInverse(inverse) 49 , fNext(std::move(next)) { 50 for (bool b : accepts) { 51 fData.push_back(b); 52 } 53 } 54 NFAStateNFAState55 NFAState(int token) 56 : fKind(kAccept_Kind) { 57 fData.push_back(token); 58 } 59 acceptNFAState60 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: 78 SkUNREACHABLE; 79 } 80 } 81 82 #ifdef SK_DEBUG descriptionNFAState83 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 += ", "; 91 result += std::to_string(v); 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; 101 result += std::to_string(v); 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; 112 result += std::to_string(v); 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 += ", "; 129 result += std::to_string(n); 130 } 131 result += ")"; 132 return result; 133 } 134 default: 135 SkUNREACHABLE; 136 } 137 } 138 #endif 139 140 Kind fKind; 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 153