123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150 |
- /*
- * Copyright 2017 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #ifndef SKSL_NFASTATE
- #define SKSL_NFASTATE
- #include <string>
- #include <vector>
- #include "src/sksl/lex/LexUtil.h"
- struct NFAState {
- enum Kind {
- // represents an accept state - if the NFA ends up in this state, we have successfully
- // matched the token indicated by fData[0]
- kAccept_Kind,
- // matches the single character fChar
- kChar_Kind,
- // the regex '.'; matches any char but '\n'
- kDot_Kind,
- // a state which serves as a placeholder for the states indicated in fData. When we
- // transition to this state, we instead transition to all of the fData states.
- kRemapped_Kind,
- // contains a list of true/false values in fData. fData[c] tells us whether we accept the
- // character c.
- kTable_Kind
- };
- NFAState(Kind kind, std::vector<int> next)
- : fKind(kind)
- , fNext(std::move(next)) {}
- NFAState(char c, std::vector<int> next)
- : fKind(kChar_Kind)
- , fChar(c)
- , fNext(std::move(next)) {}
- NFAState(std::vector<int> states)
- : fKind(kRemapped_Kind)
- , fData(std::move(states)) {}
- NFAState(bool inverse, std::vector<bool> accepts, std::vector<int> next)
- : fKind(kTable_Kind)
- , fInverse(inverse)
- , fNext(std::move(next)) {
- for (bool b : accepts) {
- fData.push_back(b);
- }
- }
- NFAState(int token)
- : fKind(kAccept_Kind) {
- fData.push_back(token);
- }
- bool accept(char c) const {
- switch (fKind) {
- case kAccept_Kind:
- return false;
- case kChar_Kind:
- return c == fChar;
- case kDot_Kind:
- return c != '\n';
- case kTable_Kind: {
- bool value;
- if ((size_t) c < fData.size()) {
- value = fData[c];
- } else {
- value = false;
- }
- return value != fInverse;
- }
- default:
- ABORT("unreachable");
- }
- }
- std::string description() const {
- switch (fKind) {
- case kAccept_Kind:
- return "Accept(" + std::to_string(fData[0]) + ")";
- case kChar_Kind: {
- std::string result = "Char('" + std::string(1, fChar) + "'";
- for (int v : fNext) {
- result += ", ";
- result += std::to_string(v);
- }
- result += ")";
- return result;
- }
- case kDot_Kind: {
- std::string result = "Dot(";
- const char* separator = "";
- for (int v : fNext) {
- result += separator;
- result += std::to_string(v);
- separator = ", ";
- }
- result += ")";
- return result;
- }
- case kRemapped_Kind: {
- std::string result = "Remapped(";
- const char* separator = "";
- for (int v : fData) {
- result += separator;
- result += std::to_string(v);
- separator = ", ";
- }
- result += ")";
- return result;
- }
- case kTable_Kind: {
- std::string result = std::string("Table(") + (fInverse ? "true" : "false") + ", [";
- const char* separator = "";
- for (int v : fData) {
- result += separator;
- result += v ? "true" : "false";
- separator = ", ";
- }
- result += "]";
- for (int n : fNext) {
- result += ", ";
- result += std::to_string(n);
- }
- result += ")";
- return result;
- }
- default:
- ABORT("unreachable");
- }
- }
- Kind fKind;
- char fChar = 0;
- bool fInverse = false;
- std::vector<int> fData;
- // states we transition to upon a succesful match from this state
- std::vector<int> fNext;
- };
- #endif
|