RegexNode.cpp 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117
  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/RegexNode.h"
  8. #include "src/sksl/lex/NFA.h"
  9. std::vector<int> RegexNode::createStates(NFA* nfa, const std::vector<int>& accept) const {
  10. std::vector<int> result;
  11. switch (fKind) {
  12. case kChar_Kind:
  13. result.push_back(nfa->addState(NFAState(fPayload.fChar, accept)));
  14. break;
  15. case kCharset_Kind: {
  16. std::vector<bool> chars;
  17. for (const RegexNode& child : fChildren) {
  18. if (child.fKind == kChar_Kind) {
  19. while (chars.size() <= (size_t) child.fPayload.fChar) {
  20. chars.push_back(false);
  21. }
  22. chars[child.fPayload.fChar] = true;
  23. } else {
  24. SkASSERT(child.fKind == kRange_Kind);
  25. while (chars.size() <= (size_t) child.fChildren[1].fPayload.fChar) {
  26. chars.push_back(false);
  27. }
  28. for (char c = child.fChildren[0].fPayload.fChar;
  29. c <= child.fChildren[1].fPayload.fChar;
  30. ++c) {
  31. chars[c] = true;
  32. }
  33. }
  34. }
  35. result.push_back(nfa->addState(NFAState(fPayload.fBool, chars, accept)));
  36. break;
  37. }
  38. case kConcat_Kind: {
  39. std::vector<int> right = fChildren[1].createStates(nfa, accept);
  40. result = fChildren[0].createStates(nfa, right);
  41. break;
  42. }
  43. case kDot_Kind:
  44. result.push_back(nfa->addState(NFAState(NFAState::kDot_Kind, accept)));
  45. break;
  46. case kOr_Kind: {
  47. std::vector<int> states = fChildren[0].createStates(nfa, accept);
  48. result.insert(result.end(), states.begin(), states.end());
  49. states = fChildren[1].createStates(nfa, accept);
  50. result.insert(result.end(), states.begin(), states.end());
  51. break;
  52. }
  53. case kPlus_Kind: {
  54. std::vector<int> next = accept;
  55. std::vector<int> placeholder;
  56. int id = nfa->addState(NFAState(placeholder));
  57. next.push_back(id);
  58. result = fChildren[0].createStates(nfa, next);
  59. nfa->fStates[id] = NFAState(result);
  60. break;
  61. }
  62. case kQuestion_Kind:
  63. result = fChildren[0].createStates(nfa, accept);
  64. result.insert(result.end(), accept.begin(), accept.end());
  65. break;
  66. case kRange_Kind:
  67. ABORT("unreachable");
  68. case kStar_Kind: {
  69. std::vector<int> next = accept;
  70. std::vector<int> placeholder;
  71. int id = nfa->addState(NFAState(placeholder));
  72. next.push_back(id);
  73. result = fChildren[0].createStates(nfa, next);
  74. result.insert(result.end(), accept.begin(), accept.end());
  75. nfa->fStates[id] = NFAState(result);
  76. break;
  77. }
  78. }
  79. return result;
  80. }
  81. std::string RegexNode::description() const {
  82. switch (fKind) {
  83. case kChar_Kind:
  84. return std::string(1, fPayload.fChar);
  85. case kCharset_Kind: {
  86. std::string result("[");
  87. if (fPayload.fBool) {
  88. result += "^";
  89. }
  90. for (const RegexNode& c : fChildren) {
  91. result += c.description();
  92. }
  93. result += "]";
  94. return result;
  95. }
  96. case kConcat_Kind:
  97. return fChildren[0].description() + fChildren[1].description();
  98. case kDot_Kind:
  99. return ".";
  100. case kOr_Kind:
  101. return "(" + fChildren[0].description() + "|" + fChildren[1].description() + ")";
  102. case kPlus_Kind:
  103. return fChildren[0].description() + "+";
  104. case kQuestion_Kind:
  105. return fChildren[0].description() + "?";
  106. case kRange_Kind:
  107. return fChildren[0].description() + "-" + fChildren[1].description();
  108. case kStar_Kind:
  109. return fChildren[0].description() + "*";
  110. default:
  111. return "<" + std::to_string(fKind) + ">";
  112. }
  113. }