NFAState.h 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150
  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. #ifndef SKSL_NFASTATE
  8. #define SKSL_NFASTATE
  9. #include <string>
  10. #include <vector>
  11. #include "src/sksl/lex/LexUtil.h"
  12. struct NFAState {
  13. enum Kind {
  14. // represents an accept state - if the NFA ends up in this state, we have successfully
  15. // matched the token indicated by fData[0]
  16. kAccept_Kind,
  17. // matches the single character fChar
  18. kChar_Kind,
  19. // the regex '.'; matches any char but '\n'
  20. kDot_Kind,
  21. // a state which serves as a placeholder for the states indicated in fData. When we
  22. // transition to this state, we instead transition to all of the fData states.
  23. kRemapped_Kind,
  24. // contains a list of true/false values in fData. fData[c] tells us whether we accept the
  25. // character c.
  26. kTable_Kind
  27. };
  28. NFAState(Kind kind, std::vector<int> next)
  29. : fKind(kind)
  30. , fNext(std::move(next)) {}
  31. NFAState(char c, std::vector<int> next)
  32. : fKind(kChar_Kind)
  33. , fChar(c)
  34. , fNext(std::move(next)) {}
  35. NFAState(std::vector<int> states)
  36. : fKind(kRemapped_Kind)
  37. , fData(std::move(states)) {}
  38. NFAState(bool inverse, std::vector<bool> accepts, std::vector<int> next)
  39. : fKind(kTable_Kind)
  40. , fInverse(inverse)
  41. , fNext(std::move(next)) {
  42. for (bool b : accepts) {
  43. fData.push_back(b);
  44. }
  45. }
  46. NFAState(int token)
  47. : fKind(kAccept_Kind) {
  48. fData.push_back(token);
  49. }
  50. bool accept(char c) const {
  51. switch (fKind) {
  52. case kAccept_Kind:
  53. return false;
  54. case kChar_Kind:
  55. return c == fChar;
  56. case kDot_Kind:
  57. return c != '\n';
  58. case kTable_Kind: {
  59. bool value;
  60. if ((size_t) c < fData.size()) {
  61. value = fData[c];
  62. } else {
  63. value = false;
  64. }
  65. return value != fInverse;
  66. }
  67. default:
  68. ABORT("unreachable");
  69. }
  70. }
  71. std::string description() const {
  72. switch (fKind) {
  73. case kAccept_Kind:
  74. return "Accept(" + std::to_string(fData[0]) + ")";
  75. case kChar_Kind: {
  76. std::string result = "Char('" + std::string(1, fChar) + "'";
  77. for (int v : fNext) {
  78. result += ", ";
  79. result += std::to_string(v);
  80. }
  81. result += ")";
  82. return result;
  83. }
  84. case kDot_Kind: {
  85. std::string result = "Dot(";
  86. const char* separator = "";
  87. for (int v : fNext) {
  88. result += separator;
  89. result += std::to_string(v);
  90. separator = ", ";
  91. }
  92. result += ")";
  93. return result;
  94. }
  95. case kRemapped_Kind: {
  96. std::string result = "Remapped(";
  97. const char* separator = "";
  98. for (int v : fData) {
  99. result += separator;
  100. result += std::to_string(v);
  101. separator = ", ";
  102. }
  103. result += ")";
  104. return result;
  105. }
  106. case kTable_Kind: {
  107. std::string result = std::string("Table(") + (fInverse ? "true" : "false") + ", [";
  108. const char* separator = "";
  109. for (int v : fData) {
  110. result += separator;
  111. result += v ? "true" : "false";
  112. separator = ", ";
  113. }
  114. result += "]";
  115. for (int n : fNext) {
  116. result += ", ";
  117. result += std::to_string(n);
  118. }
  119. result += ")";
  120. return result;
  121. }
  122. default:
  123. ABORT("unreachable");
  124. }
  125. }
  126. Kind fKind;
  127. char fChar = 0;
  128. bool fInverse = false;
  129. std::vector<int> fData;
  130. // states we transition to upon a succesful match from this state
  131. std::vector<int> fNext;
  132. };
  133. #endif