NFA.cpp 1.2 KB

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