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