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