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/RegexParser.h"
9
10 #include "src/sksl/lex/LexUtil.h"
11
parse(std::string source)12 RegexNode RegexParser::parse(std::string source) {
13 fSource = source;
14 fIndex = 0;
15 SkASSERT(fStack.size() == 0);
16 this->regex();
17 SkASSERT(fStack.size() == 1);
18 SkASSERT(fIndex == source.size());
19 return this->pop();
20 }
21
peek()22 char RegexParser::peek() {
23 if (fIndex >= fSource.size()) {
24 return END;
25 }
26 return fSource[fIndex];
27 }
28
expect(char c)29 void RegexParser::expect(char c) {
30 if (this->peek() != c) {
31 printf("expected '%c' at index %d, but found '%c'", c, (int) fIndex, this->peek());
32 exit(1);
33 }
34 ++fIndex;
35 }
36
pop()37 RegexNode RegexParser::pop() {
38 RegexNode result = fStack.top();
39 fStack.pop();
40 return result;
41 }
42
term()43 void RegexParser::term() {
44 switch (this->peek()) {
45 case '(': this->group(); break;
46 case '[': this->set(); break;
47 case '.': this->dot(); break;
48 default: this->literal(); break;
49 }
50 }
51
quantifiedTerm()52 void RegexParser::quantifiedTerm() {
53 this->term();
54 switch (this->peek()) {
55 case '*': fStack.push(RegexNode(RegexNode::kStar_Kind, this->pop())); ++fIndex; break;
56 case '+': fStack.push(RegexNode(RegexNode::kPlus_Kind, this->pop())); ++fIndex; break;
57 case '?': fStack.push(RegexNode(RegexNode::kQuestion_Kind, this->pop())); ++fIndex; break;
58 default: break;
59 }
60 }
61
sequence()62 void RegexParser::sequence() {
63 this->quantifiedTerm();
64 for (;;) {
65 switch (this->peek()) {
66 case END: [[fallthrough]];
67 case '|': [[fallthrough]];
68 case ')': return;
69 default:
70 this->sequence();
71 RegexNode right = this->pop();
72 RegexNode left = this->pop();
73 fStack.emplace(RegexNode::kConcat_Kind, std::move(left), std::move(right));
74 break;
75 }
76 }
77 }
78
escapeSequence(char c)79 RegexNode RegexParser::escapeSequence(char c) {
80 switch (c) {
81 case 'n': return RegexNode(RegexNode::kChar_Kind, '\n');
82 case 'r': return RegexNode(RegexNode::kChar_Kind, '\r');
83 case 't': return RegexNode(RegexNode::kChar_Kind, '\t');
84 case 's': return RegexNode(RegexNode::kCharset_Kind, " \t\n\r");
85 default: return RegexNode(RegexNode::kChar_Kind, c);
86 }
87 }
88
literal()89 void RegexParser::literal() {
90 char c = this->peek();
91 if (c == '\\') {
92 ++fIndex;
93 fStack.push(this->escapeSequence(peek()));
94 ++fIndex;
95 }
96 else {
97 fStack.push(RegexNode(RegexNode::kChar_Kind, c));
98 ++fIndex;
99 }
100 }
101
dot()102 void RegexParser::dot() {
103 this->expect('.');
104 fStack.push(RegexNode(RegexNode::kDot_Kind));
105 }
106
group()107 void RegexParser::group() {
108 this->expect('(');
109 this->regex();
110 this->expect(')');
111 }
112
setItem()113 void RegexParser::setItem() {
114 this->literal();
115 if (this->peek() == '-') {
116 ++fIndex;
117 if (peek() == ']') {
118 fStack.push(RegexNode(RegexNode::kChar_Kind, '-'));
119 }
120 else {
121 literal();
122 RegexNode end = this->pop();
123 SkASSERT(end.fKind == RegexNode::kChar_Kind);
124 RegexNode start = this->pop();
125 SkASSERT(start.fKind == RegexNode::kChar_Kind);
126 fStack.push(RegexNode(RegexNode::kRange_Kind, std::move(start), std::move(end)));
127 }
128 }
129 }
130
set()131 void RegexParser::set() {
132 expect('[');
133 size_t depth = fStack.size();
134 RegexNode set(RegexNode::kCharset_Kind);
135 if (this->peek() == '^') {
136 ++fIndex;
137 set.fPayload.fBool = true;
138 }
139 else {
140 set.fPayload.fBool = false;
141 }
142 for (;;) {
143 switch (this->peek()) {
144 case ']':
145 ++fIndex;
146 while (fStack.size() > depth) {
147 set.fChildren.push_back(this->pop());
148 }
149 fStack.push(std::move(set));
150 return;
151 case END:
152 printf("unterminated character set\n");
153 exit(1);
154 default:
155 this->setItem();
156 break;
157 }
158 }
159 }
160
regex()161 void RegexParser::regex() {
162 this->sequence();
163 switch (this->peek()) {
164 case '|': {
165 ++fIndex;
166 this->regex();
167 RegexNode right = this->pop();
168 RegexNode left = this->pop();
169 fStack.push(RegexNode(RegexNode::kOr_Kind, left, right));
170 break;
171 }
172 case END: // fall through
173 case ')':
174 return;
175 default:
176 SkASSERT(false);
177 }
178 }
179