OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/regexp_ast.h" | 5 #include "vm/regexp_ast.h" |
6 | 6 |
7 #include "platform/utils.h" | 7 #include "platform/utils.h" |
8 #include "vm/os.h" | 8 #include "vm/os.h" |
9 | 9 |
10 namespace dart { | 10 namespace dart { |
11 | 11 |
12 #define MAKE_ACCEPT(Name) \ | 12 #define MAKE_ACCEPT(Name) \ |
13 void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) { \ | 13 void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) { \ |
14 return visitor->Visit##Name(this, data); \ | 14 return visitor->Visit##Name(this, data); \ |
15 } | 15 } |
16 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT) | 16 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT) |
17 #undef MAKE_ACCEPT | 17 #undef MAKE_ACCEPT |
18 | 18 |
19 #define MAKE_TYPE_CASE(Name) \ | 19 #define MAKE_TYPE_CASE(Name) \ |
20 RegExp##Name* RegExpTree::As##Name() { \ | 20 RegExp##Name* RegExpTree::As##Name() { return NULL; } \ |
21 return NULL; \ | |
22 } \ | |
23 bool RegExpTree::Is##Name() const { return false; } | 21 bool RegExpTree::Is##Name() const { return false; } |
24 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) | 22 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) |
25 #undef MAKE_TYPE_CASE | 23 #undef MAKE_TYPE_CASE |
26 | 24 |
27 #define MAKE_TYPE_CASE(Name) \ | 25 #define MAKE_TYPE_CASE(Name) \ |
28 RegExp##Name* RegExp##Name::As##Name() { \ | 26 RegExp##Name* RegExp##Name::As##Name() { return this; } \ |
29 return this; \ | |
30 } \ | |
31 bool RegExp##Name::Is##Name() const { return true; } | 27 bool RegExp##Name::Is##Name() const { return true; } |
32 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) | 28 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) |
33 #undef MAKE_TYPE_CASE | 29 #undef MAKE_TYPE_CASE |
34 | 30 |
35 | 31 |
36 static Interval ListCaptureRegisters(ZoneGrowableArray<RegExpTree*>* children) { | 32 static Interval ListCaptureRegisters(ZoneGrowableArray<RegExpTree*>* children) { |
37 Interval result = Interval::Empty(); | 33 Interval result = Interval::Empty(); |
38 for (intptr_t i = 0; i < children->length(); i++) | 34 for (intptr_t i = 0; i < children->length(); i++) |
39 result = result.Union(children->At(i)->CaptureRegisters()); | 35 result = result.Union(children->At(i)->CaptureRegisters()); |
40 return result; | 36 return result; |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
74 | 70 |
75 bool RegExpAssertion::IsAnchoredAtEnd() const { | 71 bool RegExpAssertion::IsAnchoredAtEnd() const { |
76 return assertion_type() == RegExpAssertion::END_OF_INPUT; | 72 return assertion_type() == RegExpAssertion::END_OF_INPUT; |
77 } | 73 } |
78 | 74 |
79 | 75 |
80 bool RegExpAlternative::IsAnchoredAtStart() const { | 76 bool RegExpAlternative::IsAnchoredAtStart() const { |
81 ZoneGrowableArray<RegExpTree*>* nodes = this->nodes(); | 77 ZoneGrowableArray<RegExpTree*>* nodes = this->nodes(); |
82 for (intptr_t i = 0; i < nodes->length(); i++) { | 78 for (intptr_t i = 0; i < nodes->length(); i++) { |
83 RegExpTree* node = nodes->At(i); | 79 RegExpTree* node = nodes->At(i); |
84 if (node->IsAnchoredAtStart()) { return true; } | 80 if (node->IsAnchoredAtStart()) { |
85 if (node->max_match() > 0) { return false; } | 81 return true; |
| 82 } |
| 83 if (node->max_match() > 0) { |
| 84 return false; |
| 85 } |
86 } | 86 } |
87 return false; | 87 return false; |
88 } | 88 } |
89 | 89 |
90 | 90 |
91 bool RegExpAlternative::IsAnchoredAtEnd() const { | 91 bool RegExpAlternative::IsAnchoredAtEnd() const { |
92 ZoneGrowableArray<RegExpTree*>* nodes = this->nodes(); | 92 ZoneGrowableArray<RegExpTree*>* nodes = this->nodes(); |
93 for (intptr_t i = nodes->length() - 1; i >= 0; i--) { | 93 for (intptr_t i = nodes->length() - 1; i >= 0; i--) { |
94 RegExpTree* node = nodes->At(i); | 94 RegExpTree* node = nodes->At(i); |
95 if (node->IsAnchoredAtEnd()) { return true; } | 95 if (node->IsAnchoredAtEnd()) { |
96 if (node->max_match() > 0) { return false; } | 96 return true; |
| 97 } |
| 98 if (node->max_match() > 0) { |
| 99 return false; |
| 100 } |
97 } | 101 } |
98 return false; | 102 return false; |
99 } | 103 } |
100 | 104 |
101 | 105 |
102 bool RegExpDisjunction::IsAnchoredAtStart() const { | 106 bool RegExpDisjunction::IsAnchoredAtStart() const { |
103 ZoneGrowableArray<RegExpTree*>* alternatives = this->alternatives(); | 107 ZoneGrowableArray<RegExpTree*>* alternatives = this->alternatives(); |
104 for (intptr_t i = 0; i < alternatives->length(); i++) { | 108 for (intptr_t i = 0; i < alternatives->length(); i++) { |
105 if (!alternatives->At(i)->IsAnchoredAtStart()) | 109 if (!alternatives->At(i)->IsAnchoredAtStart()) return false; |
106 return false; | |
107 } | 110 } |
108 return true; | 111 return true; |
109 } | 112 } |
110 | 113 |
111 | 114 |
112 bool RegExpDisjunction::IsAnchoredAtEnd() const { | 115 bool RegExpDisjunction::IsAnchoredAtEnd() const { |
113 ZoneGrowableArray<RegExpTree*>* alternatives = this->alternatives(); | 116 ZoneGrowableArray<RegExpTree*>* alternatives = this->alternatives(); |
114 for (intptr_t i = 0; i < alternatives->length(); i++) { | 117 for (intptr_t i = 0; i < alternatives->length(); i++) { |
115 if (!alternatives->At(i)->IsAnchoredAtEnd()) | 118 if (!alternatives->At(i)->IsAnchoredAtEnd()) return false; |
116 return false; | |
117 } | 119 } |
118 return true; | 120 return true; |
119 } | 121 } |
120 | 122 |
121 | 123 |
122 bool RegExpLookahead::IsAnchoredAtStart() const { | 124 bool RegExpLookahead::IsAnchoredAtStart() const { |
123 return is_positive() && body()->IsAnchoredAtStart(); | 125 return is_positive() && body()->IsAnchoredAtStart(); |
124 } | 126 } |
125 | 127 |
126 | 128 |
127 bool RegExpCapture::IsAnchoredAtStart() const { | 129 bool RegExpCapture::IsAnchoredAtStart() const { |
128 return body()->IsAnchoredAtStart(); | 130 return body()->IsAnchoredAtStart(); |
129 } | 131 } |
130 | 132 |
131 | 133 |
132 bool RegExpCapture::IsAnchoredAtEnd() const { | 134 bool RegExpCapture::IsAnchoredAtEnd() const { |
133 return body()->IsAnchoredAtEnd(); | 135 return body()->IsAnchoredAtEnd(); |
134 } | 136 } |
135 | 137 |
136 | 138 |
137 // Convert regular expression trees to a simple sexp representation. | 139 // Convert regular expression trees to a simple sexp representation. |
138 // This representation should be different from the input grammar | 140 // This representation should be different from the input grammar |
139 // in as many cases as possible, to make it more difficult for incorrect | 141 // in as many cases as possible, to make it more difficult for incorrect |
140 // parses to look as correct ones which is likely if the input and | 142 // parses to look as correct ones which is likely if the input and |
141 // output formats are alike. | 143 // output formats are alike. |
142 class RegExpUnparser : public RegExpVisitor { | 144 class RegExpUnparser : public RegExpVisitor { |
143 public: | 145 public: |
144 void VisitCharacterRange(CharacterRange that); | 146 void VisitCharacterRange(CharacterRange that); |
145 #define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, \ | 147 #define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, void* data); |
146 void* data); | |
147 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE) | 148 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE) |
148 #undef MAKE_CASE | 149 #undef MAKE_CASE |
149 }; | 150 }; |
150 | 151 |
151 | 152 |
152 void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) { | 153 void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) { |
153 OS::Print("(|"); | 154 OS::Print("(|"); |
154 for (intptr_t i = 0; i < that->alternatives()->length(); i++) { | 155 for (intptr_t i = 0; i < that->alternatives()->length(); i++) { |
155 OS::Print(" "); | 156 OS::Print(" "); |
156 (*that->alternatives())[i]->Accept(this, data); | 157 (*that->alternatives())[i]->Accept(this, data); |
157 } | 158 } |
158 OS::Print(")"); | 159 OS::Print(")"); |
159 return NULL; | 160 return NULL; |
160 } | 161 } |
161 | 162 |
162 | 163 |
163 void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) { | 164 void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) { |
164 OS::Print("(:"); | 165 OS::Print("(:"); |
165 for (intptr_t i = 0; i < that->nodes()->length(); i++) { | 166 for (intptr_t i = 0; i < that->nodes()->length(); i++) { |
166 OS::Print(" "); | 167 OS::Print(" "); |
167 (*that->nodes())[i]->Accept(this, data); | 168 (*that->nodes())[i]->Accept(this, data); |
168 } | 169 } |
169 OS::Print(")"); | 170 OS::Print(")"); |
170 return NULL; | 171 return NULL; |
171 } | 172 } |
172 | 173 |
173 | 174 |
174 void RegExpUnparser::VisitCharacterRange(CharacterRange that) { | 175 void RegExpUnparser::VisitCharacterRange(CharacterRange that) { |
175 PrintUtf16(that.from()); | 176 PrintUtf16(that.from()); |
176 if (!that.IsSingleton()) { | 177 if (!that.IsSingleton()) { |
177 OS::Print("-"); | 178 OS::Print("-"); |
178 PrintUtf16(that.to()); | 179 PrintUtf16(that.to()); |
179 } | 180 } |
180 } | 181 } |
181 | 182 |
182 | 183 |
183 | |
184 void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that, | 184 void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that, |
185 void* data) { | 185 void* data) { |
186 if (that->is_negated()) OS::Print("^"); | 186 if (that->is_negated()) OS::Print("^"); |
187 OS::Print("["); | 187 OS::Print("["); |
188 for (intptr_t i = 0; i < that->ranges()->length(); i++) { | 188 for (intptr_t i = 0; i < that->ranges()->length(); i++) { |
189 if (i > 0) OS::Print(" "); | 189 if (i > 0) OS::Print(" "); |
190 VisitCharacterRange((*that->ranges())[i]); | 190 VisitCharacterRange((*that->ranges())[i]); |
191 } | 191 } |
192 OS::Print("]"); | 192 OS::Print("]"); |
193 return NULL; | 193 return NULL; |
194 } | 194 } |
195 | 195 |
196 | 196 |
197 void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) { | 197 void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) { |
198 switch (that->assertion_type()) { | 198 switch (that->assertion_type()) { |
199 case RegExpAssertion::START_OF_INPUT: | 199 case RegExpAssertion::START_OF_INPUT: |
200 OS::Print("@^i"); | 200 OS::Print("@^i"); |
201 break; | 201 break; |
202 case RegExpAssertion::END_OF_INPUT: | 202 case RegExpAssertion::END_OF_INPUT: |
203 OS::Print("@$i"); | 203 OS::Print("@$i"); |
204 break; | 204 break; |
205 case RegExpAssertion::START_OF_LINE: | 205 case RegExpAssertion::START_OF_LINE: |
206 OS::Print("@^l"); | 206 OS::Print("@^l"); |
207 break; | 207 break; |
208 case RegExpAssertion::END_OF_LINE: | 208 case RegExpAssertion::END_OF_LINE: |
209 OS::Print("@$l"); | 209 OS::Print("@$l"); |
210 break; | 210 break; |
211 case RegExpAssertion::BOUNDARY: | 211 case RegExpAssertion::BOUNDARY: |
212 OS::Print("@b"); | 212 OS::Print("@b"); |
213 break; | 213 break; |
214 case RegExpAssertion::NON_BOUNDARY: | 214 case RegExpAssertion::NON_BOUNDARY: |
215 OS::Print("@B"); | 215 OS::Print("@B"); |
216 break; | 216 break; |
217 } | 217 } |
218 return NULL; | 218 return NULL; |
219 } | 219 } |
220 | 220 |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
268 | 268 |
269 | 269 |
270 void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) { | 270 void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) { |
271 OS::Print("(-> %s", (that->is_positive() ? "+ " : "- ")); | 271 OS::Print("(-> %s", (that->is_positive() ? "+ " : "- ")); |
272 that->body()->Accept(this, data); | 272 that->body()->Accept(this, data); |
273 OS::Print(")"); | 273 OS::Print(")"); |
274 return NULL; | 274 return NULL; |
275 } | 275 } |
276 | 276 |
277 | 277 |
278 void* RegExpUnparser::VisitBackReference(RegExpBackReference* that, | 278 void* RegExpUnparser::VisitBackReference(RegExpBackReference* that, void*) { |
279 void*) { | |
280 OS::Print("(<- %" Pd ")", that->index()); | 279 OS::Print("(<- %" Pd ")", that->index()); |
281 return NULL; | 280 return NULL; |
282 } | 281 } |
283 | 282 |
284 | 283 |
285 void* RegExpUnparser::VisitEmpty(RegExpEmpty*, void*) { | 284 void* RegExpUnparser::VisitEmpty(RegExpEmpty*, void*) { |
286 OS::Print("%%"); | 285 OS::Print("%%"); |
287 return NULL; | 286 return NULL; |
288 } | 287 } |
289 | 288 |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
325 for (intptr_t i = 0; i < nodes->length(); i++) { | 324 for (intptr_t i = 0; i < nodes->length(); i++) { |
326 RegExpTree* node = nodes->At(i); | 325 RegExpTree* node = nodes->At(i); |
327 intptr_t node_min_match = node->min_match(); | 326 intptr_t node_min_match = node->min_match(); |
328 min_match_ = IncreaseBy(min_match_, node_min_match); | 327 min_match_ = IncreaseBy(min_match_, node_min_match); |
329 intptr_t node_max_match = node->max_match(); | 328 intptr_t node_max_match = node->max_match(); |
330 max_match_ = IncreaseBy(max_match_, node_max_match); | 329 max_match_ = IncreaseBy(max_match_, node_max_match); |
331 } | 330 } |
332 } | 331 } |
333 | 332 |
334 } // namespace dart | 333 } // namespace dart |
OLD | NEW |