Line data Source code
1 : // Copyright 2016 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include "src/ostreams.h"
6 : #include "src/regexp/regexp-ast.h"
7 :
8 : namespace v8 {
9 : namespace internal {
10 :
11 : #define MAKE_ACCEPT(Name) \
12 : void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) { \
13 : return visitor->Visit##Name(this, data); \
14 : }
15 5352 : FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT)
16 : #undef MAKE_ACCEPT
17 :
18 : #define MAKE_TYPE_CASE(Name) \
19 : RegExp##Name* RegExpTree::As##Name() { return nullptr; } \
20 : bool RegExpTree::Is##Name() { return false; }
21 2009528 : FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
22 : #undef MAKE_TYPE_CASE
23 :
24 : #define MAKE_TYPE_CASE(Name) \
25 : RegExp##Name* RegExp##Name::As##Name() { return this; } \
26 : bool RegExp##Name::Is##Name() { return true; }
27 2139236 : FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE)
28 : #undef MAKE_TYPE_CASE
29 :
30 :
31 71902 : static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) {
32 : Interval result = Interval::Empty();
33 108760 : for (int i = 0; i < children->length(); i++)
34 36858 : result = result.Union(children->at(i)->CaptureRegisters());
35 17522 : return result;
36 : }
37 :
38 :
39 14919 : Interval RegExpAlternative::CaptureRegisters() {
40 14919 : return ListCaptureRegisters(nodes());
41 : }
42 :
43 :
44 2603 : Interval RegExpDisjunction::CaptureRegisters() {
45 2603 : return ListCaptureRegisters(alternatives());
46 : }
47 :
48 :
49 91 : Interval RegExpLookaround::CaptureRegisters() {
50 91 : return body()->CaptureRegisters();
51 : }
52 :
53 :
54 13844 : Interval RegExpCapture::CaptureRegisters() {
55 : Interval self(StartRegister(index()), EndRegister(index()));
56 13844 : return self.Union(body()->CaptureRegisters());
57 : }
58 :
59 :
60 15634 : Interval RegExpQuantifier::CaptureRegisters() {
61 15634 : return body()->CaptureRegisters();
62 : }
63 :
64 :
65 5010 : bool RegExpAssertion::IsAnchoredAtStart() {
66 5010 : return assertion_type() == RegExpAssertion::START_OF_INPUT;
67 : }
68 :
69 :
70 3271 : bool RegExpAssertion::IsAnchoredAtEnd() {
71 3271 : return assertion_type() == RegExpAssertion::END_OF_INPUT;
72 : }
73 :
74 :
75 20690 : bool RegExpAlternative::IsAnchoredAtStart() {
76 22543 : ZoneList<RegExpTree*>* nodes = this->nodes();
77 45086 : for (int i = 0; i < nodes->length(); i++) {
78 22518 : RegExpTree* node = nodes->at(i);
79 22518 : if (node->IsAnchoredAtStart()) {
80 : return true;
81 : }
82 18400 : if (node->max_match() > 0) {
83 : return false;
84 : }
85 : }
86 : return false;
87 : }
88 :
89 :
90 15449 : bool RegExpAlternative::IsAnchoredAtEnd() {
91 15449 : ZoneList<RegExpTree*>* nodes = this->nodes();
92 15907 : for (int i = nodes->length() - 1; i >= 0; i--) {
93 15838 : RegExpTree* node = nodes->at(i);
94 15838 : if (node->IsAnchoredAtEnd()) {
95 : return true;
96 : }
97 12738 : if (node->max_match() > 0) {
98 : return false;
99 : }
100 : }
101 : return false;
102 : }
103 :
104 :
105 939 : bool RegExpDisjunction::IsAnchoredAtStart() {
106 1052 : ZoneList<RegExpTree*>* alternatives = this->alternatives();
107 2104 : for (int i = 0; i < alternatives->length(); i++) {
108 1041 : if (!alternatives->at(i)->IsAnchoredAtStart()) return false;
109 : }
110 : return true;
111 : }
112 :
113 :
114 981 : bool RegExpDisjunction::IsAnchoredAtEnd() {
115 1026 : ZoneList<RegExpTree*>* alternatives = this->alternatives();
116 2052 : for (int i = 0; i < alternatives->length(); i++) {
117 1005 : if (!alternatives->at(i)->IsAnchoredAtEnd()) return false;
118 : }
119 : return true;
120 : }
121 :
122 :
123 2321 : bool RegExpLookaround::IsAnchoredAtStart() {
124 2321 : return is_positive() && type() == LOOKAHEAD && body()->IsAnchoredAtStart();
125 : }
126 :
127 :
128 11619 : bool RegExpCapture::IsAnchoredAtStart() { return body()->IsAnchoredAtStart(); }
129 :
130 :
131 4113 : bool RegExpCapture::IsAnchoredAtEnd() { return body()->IsAnchoredAtEnd(); }
132 :
133 :
134 : // Convert regular expression trees to a simple sexp representation.
135 : // This representation should be different from the input grammar
136 : // in as many cases as possible, to make it more difficult for incorrect
137 : // parses to look as correct ones which is likely if the input and
138 : // output formats are alike.
139 0 : class RegExpUnparser final : public RegExpVisitor {
140 : public:
141 1812 : RegExpUnparser(std::ostream& os, Zone* zone) : os_(os), zone_(zone) {}
142 : void VisitCharacterRange(CharacterRange that);
143 : #define MAKE_CASE(Name) void* Visit##Name(RegExp##Name*, void* data) override;
144 : FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
145 : #undef MAKE_CASE
146 : private:
147 : std::ostream& os_;
148 : Zone* zone_;
149 : };
150 :
151 :
152 612 : void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) {
153 90 : os_ << "(|";
154 612 : for (int i = 0; i < that->alternatives()->length(); i++) {
155 216 : os_ << " ";
156 216 : that->alternatives()->at(i)->Accept(this, data);
157 : }
158 90 : os_ << ")";
159 90 : return nullptr;
160 : }
161 :
162 :
163 5136 : void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) {
164 618 : os_ << "(:";
165 5136 : for (int i = 0; i < that->nodes()->length(); i++) {
166 1950 : os_ << " ";
167 1950 : that->nodes()->at(i)->Accept(this, data);
168 : }
169 618 : os_ << ")";
170 618 : return nullptr;
171 : }
172 :
173 :
174 960 : void RegExpUnparser::VisitCharacterRange(CharacterRange that) {
175 960 : os_ << AsUC32(that.from());
176 960 : if (!that.IsSingleton()) {
177 222 : os_ << "-" << AsUC32(that.to());
178 : }
179 960 : }
180 :
181 :
182 444 : void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that,
183 : void* data) {
184 444 : if (that->is_negated()) os_ << "^";
185 444 : os_ << "[";
186 2808 : for (int i = 0; i < that->ranges(zone_)->length(); i++) {
187 960 : if (i > 0) os_ << " ";
188 1920 : VisitCharacterRange(that->ranges(zone_)->at(i));
189 : }
190 444 : os_ << "]";
191 444 : return nullptr;
192 : }
193 :
194 :
195 168 : void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) {
196 168 : switch (that->assertion_type()) {
197 : case RegExpAssertion::START_OF_INPUT:
198 24 : os_ << "@^i";
199 24 : break;
200 : case RegExpAssertion::END_OF_INPUT:
201 24 : os_ << "@$i";
202 24 : break;
203 : case RegExpAssertion::START_OF_LINE:
204 0 : os_ << "@^l";
205 0 : break;
206 : case RegExpAssertion::END_OF_LINE:
207 0 : os_ << "@$l";
208 0 : break;
209 : case RegExpAssertion::BOUNDARY:
210 96 : os_ << "@b";
211 96 : break;
212 : case RegExpAssertion::NON_BOUNDARY:
213 24 : os_ << "@B";
214 24 : break;
215 : }
216 168 : return nullptr;
217 : }
218 :
219 :
220 2274 : void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) {
221 2274 : os_ << "'";
222 : Vector<const uc16> chardata = that->data();
223 13380 : for (int i = 0; i < chardata.length(); i++) {
224 13248 : os_ << AsUC16(chardata[i]);
225 : }
226 2274 : os_ << "'";
227 2274 : return nullptr;
228 : }
229 :
230 :
231 18 : void* RegExpUnparser::VisitText(RegExpText* that, void* data) {
232 18 : if (that->elements()->length() == 1) {
233 0 : that->elements()->at(0).tree()->Accept(this, data);
234 : } else {
235 18 : os_ << "(!";
236 54 : for (int i = 0; i < that->elements()->length(); i++) {
237 36 : os_ << " ";
238 36 : that->elements()->at(i).tree()->Accept(this, data);
239 : }
240 18 : os_ << ")";
241 : }
242 18 : return nullptr;
243 : }
244 :
245 :
246 1080 : void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) {
247 270 : os_ << "(# " << that->min() << " ";
248 270 : if (that->max() == RegExpTree::kInfinity) {
249 162 : os_ << "- ";
250 : } else {
251 108 : os_ << that->max() << " ";
252 : }
253 270 : os_ << (that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n ");
254 270 : that->body()->Accept(this, data);
255 270 : os_ << ")";
256 270 : return nullptr;
257 : }
258 :
259 :
260 1824 : void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) {
261 912 : os_ << "(^ ";
262 912 : that->body()->Accept(this, data);
263 912 : os_ << ")";
264 912 : return nullptr;
265 : }
266 :
267 72 : void* RegExpUnparser::VisitGroup(RegExpGroup* that, void* data) {
268 36 : os_ << "(?: ";
269 36 : that->body()->Accept(this, data);
270 36 : os_ << ")";
271 36 : return nullptr;
272 : }
273 :
274 480 : void* RegExpUnparser::VisitLookaround(RegExpLookaround* that, void* data) {
275 120 : os_ << "(";
276 120 : os_ << (that->type() == RegExpLookaround::LOOKAHEAD ? "->" : "<-");
277 120 : os_ << (that->is_positive() ? " + " : " - ");
278 120 : that->body()->Accept(this, data);
279 120 : os_ << ")";
280 120 : return nullptr;
281 : }
282 :
283 :
284 360 : void* RegExpUnparser::VisitBackReference(RegExpBackReference* that,
285 : void* data) {
286 360 : os_ << "(<- " << that->index() << ")";
287 360 : return nullptr;
288 : }
289 :
290 :
291 42 : void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) {
292 42 : os_ << '%';
293 42 : return nullptr;
294 : }
295 :
296 :
297 1812 : std::ostream& RegExpTree::Print(std::ostream& os, Zone* zone) { // NOLINT
298 : RegExpUnparser unparser(os, zone);
299 1812 : Accept(&unparser, nullptr);
300 1812 : return os;
301 : }
302 :
303 :
304 197239 : RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
305 26969 : : alternatives_(alternatives) {
306 : DCHECK_LT(1, alternatives->length());
307 26969 : RegExpTree* first_alternative = alternatives->at(0);
308 26969 : min_match_ = first_alternative->min_match();
309 26969 : max_match_ = first_alternative->max_match();
310 340540 : for (int i = 1; i < alternatives->length(); i++) {
311 143301 : RegExpTree* alternative = alternatives->at(i);
312 286602 : min_match_ = Min(min_match_, alternative->min_match());
313 286602 : max_match_ = Max(max_match_, alternative->max_match());
314 : }
315 26969 : }
316 :
317 :
318 : static int IncreaseBy(int previous, int increase) {
319 3652892 : if (RegExpTree::kInfinity - previous < increase) {
320 : return RegExpTree::kInfinity;
321 : } else {
322 3591067 : return previous + increase;
323 : }
324 : }
325 :
326 :
327 1959042 : RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes)
328 66298 : : nodes_(nodes) {
329 : DCHECK_LT(1, nodes->length());
330 66298 : min_match_ = 0;
331 66298 : max_match_ = 0;
332 3785488 : for (int i = 0; i < nodes->length(); i++) {
333 1826446 : RegExpTree* node = nodes->at(i);
334 1826446 : int node_min_match = node->min_match();
335 3652892 : min_match_ = IncreaseBy(min_match_, node_min_match);
336 1826446 : int node_max_match = node->max_match();
337 3652892 : max_match_ = IncreaseBy(max_match_, node_max_match);
338 : }
339 66298 : }
340 :
341 :
342 : } // namespace internal
343 : } // namespace v8
|
