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