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 #ifndef V8_REGEXP_REGEXP_AST_H_ 6 #define V8_REGEXP_REGEXP_AST_H_ 7 8 #include "src/objects.h" 9 #include "src/objects/js-regexp.h" 10 #include "src/objects/string.h" 11 #include "src/utils.h" 12 #include "src/zone/zone-containers.h" 13 #include "src/zone/zone.h" 14 15 namespace v8 { 16 namespace internal { 17 18 #define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \ 19 VISIT(Disjunction) \ 20 VISIT(Alternative) \ 21 VISIT(Assertion) \ 22 VISIT(CharacterClass) \ 23 VISIT(Atom) \ 24 VISIT(Quantifier) \ 25 VISIT(Capture) \ 26 VISIT(Group) \ 27 VISIT(Lookaround) \ 28 VISIT(BackReference) \ 29 VISIT(Empty) \ 30 VISIT(Text) 31 32 #define FORWARD_DECLARE(Name) class RegExp##Name; 33 FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE) 34 #undef FORWARD_DECLARE 35 36 class RegExpCompiler; 37 class RegExpNode; 38 class RegExpTree; 39 40 41 class RegExpVisitor BASE_EMBEDDED { 42 public: ~RegExpVisitor()43 virtual ~RegExpVisitor() {} 44 #define MAKE_CASE(Name) \ 45 virtual void* Visit##Name(RegExp##Name*, void* data) = 0; 46 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE) 47 #undef MAKE_CASE 48 }; 49 50 51 // A simple closed interval. 52 class Interval { 53 public: Interval()54 Interval() : from_(kNone), to_(kNone) {} Interval(int from,int to)55 Interval(int from, int to) : from_(from), to_(to) {} Union(Interval that)56 Interval Union(Interval that) { 57 if (that.from_ == kNone) 58 return *this; 59 else if (from_ == kNone) 60 return that; 61 else 62 return Interval(Min(from_, that.from_), Max(to_, that.to_)); 63 } Contains(int value)64 bool Contains(int value) { return (from_ <= value) && (value <= to_); } is_empty()65 bool is_empty() { return from_ == kNone; } from()66 int from() const { return from_; } to()67 int to() const { return to_; } Empty()68 static Interval Empty() { return Interval(); } 69 static const int kNone = -1; 70 71 private: 72 int from_; 73 int to_; 74 }; 75 76 77 // Represents code units in the range from from_ to to_, both ends are 78 // inclusive. 79 class CharacterRange { 80 public: CharacterRange()81 CharacterRange() : from_(0), to_(0) {} 82 // For compatibility with the CHECK_OK macro CharacterRange(void * null)83 CharacterRange(void* null) { DCHECK_NULL(null); } // NOLINT 84 static void AddClassEscape(char type, ZoneList<CharacterRange>* ranges, 85 Zone* zone); 86 // Add class escapes. Add case equivalent closure for \w and \W if necessary. 87 static void AddClassEscape(char type, ZoneList<CharacterRange>* ranges, 88 bool add_unicode_case_equivalents, Zone* zone); 89 static Vector<const int> GetWordBounds(); Singleton(uc32 value)90 static inline CharacterRange Singleton(uc32 value) { 91 return CharacterRange(value, value); 92 } Range(uc32 from,uc32 to)93 static inline CharacterRange Range(uc32 from, uc32 to) { 94 DCHECK(0 <= from && to <= String::kMaxCodePoint); 95 DCHECK(static_cast<uint32_t>(from) <= static_cast<uint32_t>(to)); 96 return CharacterRange(from, to); 97 } Everything()98 static inline CharacterRange Everything() { 99 return CharacterRange(0, String::kMaxCodePoint); 100 } List(Zone * zone,CharacterRange range)101 static inline ZoneList<CharacterRange>* List(Zone* zone, 102 CharacterRange range) { 103 ZoneList<CharacterRange>* list = 104 new (zone) ZoneList<CharacterRange>(1, zone); 105 list->Add(range, zone); 106 return list; 107 } Contains(uc32 i)108 bool Contains(uc32 i) { return from_ <= i && i <= to_; } from()109 uc32 from() const { return from_; } set_from(uc32 value)110 void set_from(uc32 value) { from_ = value; } to()111 uc32 to() const { return to_; } set_to(uc32 value)112 void set_to(uc32 value) { to_ = value; } is_valid()113 bool is_valid() { return from_ <= to_; } IsEverything(uc32 max)114 bool IsEverything(uc32 max) { return from_ == 0 && to_ >= max; } IsSingleton()115 bool IsSingleton() { return (from_ == to_); } 116 static void AddCaseEquivalents(Isolate* isolate, Zone* zone, 117 ZoneList<CharacterRange>* ranges, 118 bool is_one_byte); 119 // Whether a range list is in canonical form: Ranges ordered by from value, 120 // and ranges non-overlapping and non-adjacent. 121 static bool IsCanonical(ZoneList<CharacterRange>* ranges); 122 // Convert range list to canonical form. The characters covered by the ranges 123 // will still be the same, but no character is in more than one range, and 124 // adjacent ranges are merged. The resulting list may be shorter than the 125 // original, but cannot be longer. 126 static void Canonicalize(ZoneList<CharacterRange>* ranges); 127 // Negate the contents of a character range in canonical form. 128 static void Negate(ZoneList<CharacterRange>* src, 129 ZoneList<CharacterRange>* dst, Zone* zone); 130 static const int kStartMarker = (1 << 24); 131 static const int kPayloadMask = (1 << 24) - 1; 132 133 private: CharacterRange(uc32 from,uc32 to)134 CharacterRange(uc32 from, uc32 to) : from_(from), to_(to) {} 135 136 uc32 from_; 137 uc32 to_; 138 }; 139 140 141 class CharacterSet final BASE_EMBEDDED { 142 public: CharacterSet(uc16 standard_set_type)143 explicit CharacterSet(uc16 standard_set_type) 144 : ranges_(nullptr), standard_set_type_(standard_set_type) {} CharacterSet(ZoneList<CharacterRange> * ranges)145 explicit CharacterSet(ZoneList<CharacterRange>* ranges) 146 : ranges_(ranges), standard_set_type_(0) {} 147 ZoneList<CharacterRange>* ranges(Zone* zone); standard_set_type()148 uc16 standard_set_type() const { return standard_set_type_; } set_standard_set_type(uc16 special_set_type)149 void set_standard_set_type(uc16 special_set_type) { 150 standard_set_type_ = special_set_type; 151 } is_standard()152 bool is_standard() { return standard_set_type_ != 0; } 153 void Canonicalize(); 154 155 private: 156 ZoneList<CharacterRange>* ranges_; 157 // If non-zero, the value represents a standard set (e.g., all whitespace 158 // characters) without having to expand the ranges. 159 uc16 standard_set_type_; 160 }; 161 162 163 class TextElement final BASE_EMBEDDED { 164 public: 165 enum TextType { ATOM, CHAR_CLASS }; 166 167 static TextElement Atom(RegExpAtom* atom); 168 static TextElement CharClass(RegExpCharacterClass* char_class); 169 cp_offset()170 int cp_offset() const { return cp_offset_; } set_cp_offset(int cp_offset)171 void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; } 172 int length() const; 173 text_type()174 TextType text_type() const { return text_type_; } 175 tree()176 RegExpTree* tree() const { return tree_; } 177 atom()178 RegExpAtom* atom() const { 179 DCHECK(text_type() == ATOM); 180 return reinterpret_cast<RegExpAtom*>(tree()); 181 } 182 char_class()183 RegExpCharacterClass* char_class() const { 184 DCHECK(text_type() == CHAR_CLASS); 185 return reinterpret_cast<RegExpCharacterClass*>(tree()); 186 } 187 188 private: TextElement(TextType text_type,RegExpTree * tree)189 TextElement(TextType text_type, RegExpTree* tree) 190 : cp_offset_(-1), text_type_(text_type), tree_(tree) {} 191 192 int cp_offset_; 193 TextType text_type_; 194 RegExpTree* tree_; 195 }; 196 197 198 class RegExpTree : public ZoneObject { 199 public: 200 static const int kInfinity = kMaxInt; ~RegExpTree()201 virtual ~RegExpTree() {} 202 virtual void* Accept(RegExpVisitor* visitor, void* data) = 0; 203 virtual RegExpNode* ToNode(RegExpCompiler* compiler, 204 RegExpNode* on_success) = 0; IsTextElement()205 virtual bool IsTextElement() { return false; } IsAnchoredAtStart()206 virtual bool IsAnchoredAtStart() { return false; } IsAnchoredAtEnd()207 virtual bool IsAnchoredAtEnd() { return false; } 208 virtual int min_match() = 0; 209 virtual int max_match() = 0; 210 // Returns the interval of registers used for captures within this 211 // expression. CaptureRegisters()212 virtual Interval CaptureRegisters() { return Interval::Empty(); } 213 virtual void AppendToText(RegExpText* text, Zone* zone); 214 std::ostream& Print(std::ostream& os, Zone* zone); // NOLINT 215 #define MAKE_ASTYPE(Name) \ 216 virtual RegExp##Name* As##Name(); \ 217 virtual bool Is##Name(); 218 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ASTYPE) 219 #undef MAKE_ASTYPE 220 }; 221 222 223 class RegExpDisjunction final : public RegExpTree { 224 public: 225 explicit RegExpDisjunction(ZoneList<RegExpTree*>* alternatives); 226 void* Accept(RegExpVisitor* visitor, void* data) override; 227 RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override; 228 RegExpDisjunction* AsDisjunction() override; 229 Interval CaptureRegisters() override; 230 bool IsDisjunction() override; 231 bool IsAnchoredAtStart() override; 232 bool IsAnchoredAtEnd() override; min_match()233 int min_match() override { return min_match_; } max_match()234 int max_match() override { return max_match_; } alternatives()235 ZoneList<RegExpTree*>* alternatives() { return alternatives_; } 236 237 private: 238 bool SortConsecutiveAtoms(RegExpCompiler* compiler); 239 void RationalizeConsecutiveAtoms(RegExpCompiler* compiler); 240 void FixSingleCharacterDisjunctions(RegExpCompiler* compiler); 241 ZoneList<RegExpTree*>* alternatives_; 242 int min_match_; 243 int max_match_; 244 }; 245 246 247 class RegExpAlternative final : public RegExpTree { 248 public: 249 explicit RegExpAlternative(ZoneList<RegExpTree*>* nodes); 250 void* Accept(RegExpVisitor* visitor, void* data) override; 251 RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override; 252 RegExpAlternative* AsAlternative() override; 253 Interval CaptureRegisters() override; 254 bool IsAlternative() override; 255 bool IsAnchoredAtStart() override; 256 bool IsAnchoredAtEnd() override; min_match()257 int min_match() override { return min_match_; } max_match()258 int max_match() override { return max_match_; } nodes()259 ZoneList<RegExpTree*>* nodes() { return nodes_; } 260 261 private: 262 ZoneList<RegExpTree*>* nodes_; 263 int min_match_; 264 int max_match_; 265 }; 266 267 268 class RegExpAssertion final : public RegExpTree { 269 public: 270 enum AssertionType { 271 START_OF_LINE, 272 START_OF_INPUT, 273 END_OF_LINE, 274 END_OF_INPUT, 275 BOUNDARY, 276 NON_BOUNDARY 277 }; RegExpAssertion(AssertionType type,JSRegExp::Flags flags)278 RegExpAssertion(AssertionType type, JSRegExp::Flags flags) 279 : assertion_type_(type), flags_(flags) {} 280 void* Accept(RegExpVisitor* visitor, void* data) override; 281 RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override; 282 RegExpAssertion* AsAssertion() override; 283 bool IsAssertion() override; 284 bool IsAnchoredAtStart() override; 285 bool IsAnchoredAtEnd() override; min_match()286 int min_match() override { return 0; } max_match()287 int max_match() override { return 0; } assertion_type()288 AssertionType assertion_type() { return assertion_type_; } 289 290 private: 291 const AssertionType assertion_type_; 292 const JSRegExp::Flags flags_; 293 }; 294 295 296 class RegExpCharacterClass final : public RegExpTree { 297 public: 298 // NEGATED: The character class is negated and should match everything but 299 // the specified ranges. 300 // CONTAINS_SPLIT_SURROGATE: The character class contains part of a split 301 // surrogate and should not be unicode-desugared (crbug.com/641091). 302 enum Flag { 303 NEGATED = 1 << 0, 304 CONTAINS_SPLIT_SURROGATE = 1 << 1, 305 }; 306 typedef base::Flags<Flag> CharacterClassFlags; 307 308 RegExpCharacterClass( 309 Zone* zone, ZoneList<CharacterRange>* ranges, JSRegExp::Flags flags, 310 CharacterClassFlags character_class_flags = CharacterClassFlags()) set_(ranges)311 : set_(ranges), 312 flags_(flags), 313 character_class_flags_(character_class_flags) { 314 // Convert the empty set of ranges to the negated Everything() range. 315 if (ranges->is_empty()) { 316 ranges->Add(CharacterRange::Everything(), zone); 317 character_class_flags_ ^= NEGATED; 318 } 319 } RegExpCharacterClass(uc16 type,JSRegExp::Flags flags)320 RegExpCharacterClass(uc16 type, JSRegExp::Flags flags) 321 : set_(type), 322 flags_(flags), 323 character_class_flags_(CharacterClassFlags()) {} 324 void* Accept(RegExpVisitor* visitor, void* data) override; 325 RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override; 326 RegExpCharacterClass* AsCharacterClass() override; 327 bool IsCharacterClass() override; IsTextElement()328 bool IsTextElement() override { return true; } min_match()329 int min_match() override { return 1; } 330 // The character class may match two code units for unicode regexps. 331 // TODO(yangguo): we should split this class for usage in TextElement, and 332 // make max_match() dependent on the character class content. max_match()333 int max_match() override { return 2; } 334 void AppendToText(RegExpText* text, Zone* zone) override; character_set()335 CharacterSet character_set() { return set_; } 336 // TODO(lrn): Remove need for complex version if is_standard that 337 // recognizes a mangled standard set and just do { return set_.is_special(); } 338 bool is_standard(Zone* zone); 339 // Returns a value representing the standard character set if is_standard() 340 // returns true. 341 // Currently used values are: 342 // s : unicode whitespace 343 // S : unicode non-whitespace 344 // w : ASCII word character (digit, letter, underscore) 345 // W : non-ASCII word character 346 // d : ASCII digit 347 // D : non-ASCII digit 348 // . : non-newline 349 // * : All characters, for advancing unanchored regexp standard_type()350 uc16 standard_type() const { return set_.standard_set_type(); } ranges(Zone * zone)351 ZoneList<CharacterRange>* ranges(Zone* zone) { return set_.ranges(zone); } is_negated()352 bool is_negated() const { return (character_class_flags_ & NEGATED) != 0; } flags()353 JSRegExp::Flags flags() const { return flags_; } contains_split_surrogate()354 bool contains_split_surrogate() const { 355 return (character_class_flags_ & CONTAINS_SPLIT_SURROGATE) != 0; 356 } 357 358 private: 359 CharacterSet set_; 360 const JSRegExp::Flags flags_; 361 CharacterClassFlags character_class_flags_; 362 }; 363 364 365 class RegExpAtom final : public RegExpTree { 366 public: RegExpAtom(Vector<const uc16> data,JSRegExp::Flags flags)367 explicit RegExpAtom(Vector<const uc16> data, JSRegExp::Flags flags) 368 : data_(data), flags_(flags) {} 369 void* Accept(RegExpVisitor* visitor, void* data) override; 370 RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override; 371 RegExpAtom* AsAtom() override; 372 bool IsAtom() override; IsTextElement()373 bool IsTextElement() override { return true; } min_match()374 int min_match() override { return data_.length(); } max_match()375 int max_match() override { return data_.length(); } 376 void AppendToText(RegExpText* text, Zone* zone) override; data()377 Vector<const uc16> data() { return data_; } length()378 int length() { return data_.length(); } flags()379 JSRegExp::Flags flags() const { return flags_; } ignore_case()380 bool ignore_case() const { return (flags_ & JSRegExp::kIgnoreCase) != 0; } 381 382 private: 383 Vector<const uc16> data_; 384 const JSRegExp::Flags flags_; 385 }; 386 387 388 class RegExpText final : public RegExpTree { 389 public: RegExpText(Zone * zone)390 explicit RegExpText(Zone* zone) : elements_(2, zone), length_(0) {} 391 void* Accept(RegExpVisitor* visitor, void* data) override; 392 RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override; 393 RegExpText* AsText() override; 394 bool IsText() override; IsTextElement()395 bool IsTextElement() override { return true; } min_match()396 int min_match() override { return length_; } max_match()397 int max_match() override { return length_; } 398 void AppendToText(RegExpText* text, Zone* zone) override; AddElement(TextElement elm,Zone * zone)399 void AddElement(TextElement elm, Zone* zone) { 400 elements_.Add(elm, zone); 401 length_ += elm.length(); 402 } elements()403 ZoneList<TextElement>* elements() { return &elements_; } 404 405 private: 406 ZoneList<TextElement> elements_; 407 int length_; 408 }; 409 410 411 class RegExpQuantifier final : public RegExpTree { 412 public: 413 enum QuantifierType { GREEDY, NON_GREEDY, POSSESSIVE }; RegExpQuantifier(int min,int max,QuantifierType type,RegExpTree * body)414 RegExpQuantifier(int min, int max, QuantifierType type, RegExpTree* body) 415 : body_(body), 416 min_(min), 417 max_(max), 418 min_match_(min * body->min_match()), 419 quantifier_type_(type) { 420 if (max > 0 && body->max_match() > kInfinity / max) { 421 max_match_ = kInfinity; 422 } else { 423 max_match_ = max * body->max_match(); 424 } 425 } 426 void* Accept(RegExpVisitor* visitor, void* data) override; 427 RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override; 428 static RegExpNode* ToNode(int min, int max, bool is_greedy, RegExpTree* body, 429 RegExpCompiler* compiler, RegExpNode* on_success, 430 bool not_at_start = false); 431 RegExpQuantifier* AsQuantifier() override; 432 Interval CaptureRegisters() override; 433 bool IsQuantifier() override; min_match()434 int min_match() override { return min_match_; } max_match()435 int max_match() override { return max_match_; } min()436 int min() { return min_; } max()437 int max() { return max_; } is_possessive()438 bool is_possessive() { return quantifier_type_ == POSSESSIVE; } is_non_greedy()439 bool is_non_greedy() { return quantifier_type_ == NON_GREEDY; } is_greedy()440 bool is_greedy() { return quantifier_type_ == GREEDY; } body()441 RegExpTree* body() { return body_; } 442 443 private: 444 RegExpTree* body_; 445 int min_; 446 int max_; 447 int min_match_; 448 int max_match_; 449 QuantifierType quantifier_type_; 450 }; 451 452 453 class RegExpCapture final : public RegExpTree { 454 public: RegExpCapture(int index)455 explicit RegExpCapture(int index) 456 : body_(nullptr), index_(index), name_(nullptr) {} 457 void* Accept(RegExpVisitor* visitor, void* data) override; 458 RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override; 459 static RegExpNode* ToNode(RegExpTree* body, int index, 460 RegExpCompiler* compiler, RegExpNode* on_success); 461 RegExpCapture* AsCapture() override; 462 bool IsAnchoredAtStart() override; 463 bool IsAnchoredAtEnd() override; 464 Interval CaptureRegisters() override; 465 bool IsCapture() override; min_match()466 int min_match() override { return body_->min_match(); } max_match()467 int max_match() override { return body_->max_match(); } body()468 RegExpTree* body() { return body_; } set_body(RegExpTree * body)469 void set_body(RegExpTree* body) { body_ = body; } index()470 int index() { return index_; } name()471 const ZoneVector<uc16>* name() const { return name_; } set_name(const ZoneVector<uc16> * name)472 void set_name(const ZoneVector<uc16>* name) { name_ = name; } StartRegister(int index)473 static int StartRegister(int index) { return index * 2; } EndRegister(int index)474 static int EndRegister(int index) { return index * 2 + 1; } 475 476 private: 477 RegExpTree* body_; 478 int index_; 479 const ZoneVector<uc16>* name_; 480 }; 481 482 class RegExpGroup final : public RegExpTree { 483 public: RegExpGroup(RegExpTree * body)484 explicit RegExpGroup(RegExpTree* body) : body_(body) {} 485 void* Accept(RegExpVisitor* visitor, void* data) override; ToNode(RegExpCompiler * compiler,RegExpNode * on_success)486 RegExpNode* ToNode(RegExpCompiler* compiler, 487 RegExpNode* on_success) override { 488 return body_->ToNode(compiler, on_success); 489 } 490 RegExpGroup* AsGroup() override; IsAnchoredAtStart()491 bool IsAnchoredAtStart() override { return body_->IsAnchoredAtStart(); } IsAnchoredAtEnd()492 bool IsAnchoredAtEnd() override { return body_->IsAnchoredAtEnd(); } 493 bool IsGroup() override; min_match()494 int min_match() override { return body_->min_match(); } max_match()495 int max_match() override { return body_->max_match(); } CaptureRegisters()496 Interval CaptureRegisters() override { return body_->CaptureRegisters(); } body()497 RegExpTree* body() { return body_; } 498 499 private: 500 RegExpTree* body_; 501 }; 502 503 class RegExpLookaround final : public RegExpTree { 504 public: 505 enum Type { LOOKAHEAD, LOOKBEHIND }; 506 RegExpLookaround(RegExpTree * body,bool is_positive,int capture_count,int capture_from,Type type)507 RegExpLookaround(RegExpTree* body, bool is_positive, int capture_count, 508 int capture_from, Type type) 509 : body_(body), 510 is_positive_(is_positive), 511 capture_count_(capture_count), 512 capture_from_(capture_from), 513 type_(type) {} 514 515 void* Accept(RegExpVisitor* visitor, void* data) override; 516 RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override; 517 RegExpLookaround* AsLookaround() override; 518 Interval CaptureRegisters() override; 519 bool IsLookaround() override; 520 bool IsAnchoredAtStart() override; min_match()521 int min_match() override { return 0; } max_match()522 int max_match() override { return 0; } body()523 RegExpTree* body() { return body_; } is_positive()524 bool is_positive() { return is_positive_; } capture_count()525 int capture_count() { return capture_count_; } capture_from()526 int capture_from() { return capture_from_; } type()527 Type type() { return type_; } 528 529 class Builder { 530 public: 531 Builder(bool is_positive, RegExpNode* on_success, 532 int stack_pointer_register, int position_register, 533 int capture_register_count = 0, int capture_register_start = 0); on_match_success()534 RegExpNode* on_match_success() { return on_match_success_; } 535 RegExpNode* ForMatch(RegExpNode* match); 536 537 private: 538 bool is_positive_; 539 RegExpNode* on_match_success_; 540 RegExpNode* on_success_; 541 int stack_pointer_register_; 542 int position_register_; 543 }; 544 545 private: 546 RegExpTree* body_; 547 bool is_positive_; 548 int capture_count_; 549 int capture_from_; 550 Type type_; 551 }; 552 553 554 class RegExpBackReference final : public RegExpTree { 555 public: RegExpBackReference(JSRegExp::Flags flags)556 explicit RegExpBackReference(JSRegExp::Flags flags) 557 : capture_(nullptr), name_(nullptr), flags_(flags) {} RegExpBackReference(RegExpCapture * capture,JSRegExp::Flags flags)558 RegExpBackReference(RegExpCapture* capture, JSRegExp::Flags flags) 559 : capture_(capture), name_(nullptr), flags_(flags) {} 560 void* Accept(RegExpVisitor* visitor, void* data) override; 561 RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override; 562 RegExpBackReference* AsBackReference() override; 563 bool IsBackReference() override; min_match()564 int min_match() override { return 0; } 565 // The back reference may be recursive, e.g. /(\2)(\1)/. To avoid infinite 566 // recursion, we give up. Ignorance is bliss. max_match()567 int max_match() override { return kInfinity; } index()568 int index() { return capture_->index(); } capture()569 RegExpCapture* capture() { return capture_; } set_capture(RegExpCapture * capture)570 void set_capture(RegExpCapture* capture) { capture_ = capture; } name()571 const ZoneVector<uc16>* name() const { return name_; } set_name(const ZoneVector<uc16> * name)572 void set_name(const ZoneVector<uc16>* name) { name_ = name; } 573 574 private: 575 RegExpCapture* capture_; 576 const ZoneVector<uc16>* name_; 577 const JSRegExp::Flags flags_; 578 }; 579 580 581 class RegExpEmpty final : public RegExpTree { 582 public: RegExpEmpty()583 RegExpEmpty() {} 584 void* Accept(RegExpVisitor* visitor, void* data) override; 585 RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override; 586 RegExpEmpty* AsEmpty() override; 587 bool IsEmpty() override; min_match()588 int min_match() override { return 0; } max_match()589 int max_match() override { return 0; } 590 }; 591 592 } // namespace internal 593 } // namespace v8 594 595 #endif // V8_REGEXP_REGEXP_AST_H_ 596