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 #include "src/sksl/lex/NFA.h" 9 10 #include "src/sksl/lex/LexUtil.h" 11 #include <string> 12 match(std::string s) const13int NFA::match(std::string s) const { 14 std::vector<int> states = fStartStates; 15 for (size_t i = 0; i < s.size(); ++i) { 16 std::vector<int> next; 17 for (int id : states) { 18 if (fStates[id].accept(s[i])) { 19 for (int nextId : fStates[id].fNext) { 20 if (fStates[nextId].fKind != NFAState::kRemapped_Kind) { 21 next.push_back(nextId); 22 } else { 23 next.insert(next.end(), fStates[nextId].fData.begin(), 24 fStates[nextId].fData.end()); 25 } 26 } 27 } 28 } 29 if (!next.size()) { 30 return INVALID; 31 } 32 states = next; 33 } 34 int accept = INVALID; 35 for (int id : states) { 36 if (fStates[id].fKind == NFAState::kAccept_Kind) { 37 int result = fStates[id].fData[0]; 38 if (accept == INVALID || result < accept) { 39 accept = result; 40 } 41 } 42 } 43 return accept; 44 } 45