5 #ifndef V8_REGEXP_REGEXP_AST_H_ 6 #define V8_REGEXP_REGEXP_AST_H_ 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" 18 #define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \ 22 VISIT(CharacterClass) \ 28 VISIT(BackReference) \ 32 #define FORWARD_DECLARE(Name) class RegExp##Name; 33 FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE)
34 #undef FORWARD_DECLARE 43 #define MAKE_CASE(Name) \ 44 virtual void* Visit##Name(RegExp##Name*, void* data) = 0; 45 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
53 Interval() : from_(kNone), to_(kNone) {}
54 Interval(
int from,
int to) : from_(from), to_(to) {}
56 if (that.from_ == kNone)
58 else if (from_ == kNone)
61 return Interval(Min(from_, that.from_), Max(to_, that.to_));
63 bool Contains(
int value) {
return (from_ <= value) && (value <= to_); }
64 bool is_empty() {
return from_ == kNone; }
65 int from()
const {
return from_; }
66 int to()
const {
return to_; }
68 static const int kNone = -1;
87 bool add_unicode_case_equivalents,
Zone* zone);
93 DCHECK(0 <= from && to <= String::kMaxCodePoint);
94 DCHECK(static_cast<uint32_t>(from) <= static_cast<uint32_t>(to));
104 list->Add(range, zone);
107 bool Contains(uc32
i) {
return from_ <=
i &&
i <= to_; }
108 uc32 from()
const {
return from_; }
109 void set_from(uc32 value) { from_ = value; }
110 uc32 to()
const {
return to_; }
111 void set_to(uc32 value) { to_ = value; }
112 bool is_valid() {
return from_ <= to_; }
113 bool IsEverything(uc32 max) {
return from_ == 0 && to_ >= max; }
114 bool IsSingleton() {
return (from_ == to_); }
115 static void AddCaseEquivalents(
Isolate* isolate,
Zone* zone,
129 static const int kStartMarker = (1 << 24);
130 static const int kPayloadMask = (1 << 24) - 1;
142 : ranges_(
nullptr), standard_set_type_(standard_set_type) {}
144 : ranges_(ranges), standard_set_type_(0) {}
146 uc16 standard_set_type()
const {
return standard_set_type_; }
147 void set_standard_set_type(uc16 special_set_type) {
148 standard_set_type_ = special_set_type;
150 bool is_standard() {
return standard_set_type_ != 0; }
157 uc16 standard_set_type_;
162 enum TextType { ATOM, CHAR_CLASS };
167 int cp_offset()
const {
return cp_offset_; }
168 void set_cp_offset(
int cp_offset) { cp_offset_ = cp_offset; }
171 TextType text_type()
const {
return text_type_; }
176 DCHECK(text_type() == ATOM);
181 DCHECK(text_type() == CHAR_CLASS);
187 : cp_offset_(-1), text_type_(text_type), tree_(tree) {}
197 static const int kInfinity = kMaxInt;
199 virtual void* Accept(
RegExpVisitor* visitor,
void* data) = 0;
202 virtual bool IsTextElement() {
return false; }
203 virtual bool IsAnchoredAtStart() {
return false; }
204 virtual bool IsAnchoredAtEnd() {
return false; }
205 virtual int min_match() = 0;
206 virtual int max_match() = 0;
209 virtual Interval CaptureRegisters() {
return Interval::Empty(); }
211 std::ostream& Print(std::ostream& os,
Zone* zone);
212 #define MAKE_ASTYPE(Name) \ 213 virtual RegExp##Name* As##Name(); \ 214 virtual bool Is##Name(); 215 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ASTYPE)
226 Interval CaptureRegisters()
override;
227 bool IsDisjunction()
override;
228 bool IsAnchoredAtStart()
override;
229 bool IsAnchoredAtEnd()
override;
230 int min_match()
override {
return min_match_; }
231 int max_match()
override {
return max_match_; }
250 Interval CaptureRegisters()
override;
251 bool IsAlternative()
override;
252 bool IsAnchoredAtStart()
override;
253 bool IsAnchoredAtEnd()
override;
254 int min_match()
override {
return min_match_; }
255 int max_match()
override {
return max_match_; }
276 : assertion_type_(
type), flags_(flags) {}
280 bool IsAssertion()
override;
281 bool IsAnchoredAtStart()
override;
282 bool IsAnchoredAtEnd()
override;
283 int min_match()
override {
return 0; }
284 int max_match()
override {
return 0; }
285 AssertionType assertion_type() {
return assertion_type_; }
288 const AssertionType assertion_type_;
301 CONTAINS_SPLIT_SURROGATE = 1 << 1,
310 character_class_flags_(character_class_flags) {
312 if (ranges->is_empty()) {
313 ranges->Add(CharacterRange::Everything(), zone);
314 character_class_flags_ ^= NEGATED;
324 bool IsCharacterClass()
override;
325 bool IsTextElement()
override {
return true; }
326 int min_match()
override {
return 1; }
330 int max_match()
override {
return 2; }
335 bool is_standard(
Zone* zone);
347 uc16 standard_type()
const {
return set_.standard_set_type(); }
349 bool is_negated()
const {
return (character_class_flags_ & NEGATED) != 0; }
351 bool contains_split_surrogate()
const {
352 return (character_class_flags_ & CONTAINS_SPLIT_SURROGATE) != 0;
365 : data_(data), flags_(flags) {}
369 bool IsAtom()
override;
370 bool IsTextElement()
override {
return true; }
371 int min_match()
override {
return data_.length(); }
372 int max_match()
override {
return data_.length(); }
375 int length() {
return data_.length(); }
377 bool ignore_case()
const {
return (flags_ & JSRegExp::kIgnoreCase) != 0; }
387 explicit RegExpText(
Zone* zone) : elements_(2, zone), length_(0) {}
391 bool IsText()
override;
392 bool IsTextElement()
override {
return true; }
393 int min_match()
override {
return length_; }
394 int max_match()
override {
return length_; }
397 elements_.Add(elm, zone);
398 length_ += elm.length();
410 enum QuantifierType { GREEDY, NON_GREEDY, POSSESSIVE };
415 min_match_(min * body->min_match()),
416 quantifier_type_(
type) {
417 if (max > 0 && body->max_match() > kInfinity / max) {
418 max_match_ = kInfinity;
420 max_match_ = max * body->max_match();
427 bool not_at_start =
false);
429 Interval CaptureRegisters()
override;
430 bool IsQuantifier()
override;
431 int min_match()
override {
return min_match_; }
432 int max_match()
override {
return max_match_; }
433 int min() {
return min_; }
434 int max() {
return max_; }
435 bool is_possessive() {
return quantifier_type_ == POSSESSIVE; }
436 bool is_non_greedy() {
return quantifier_type_ == NON_GREEDY; }
437 bool is_greedy() {
return quantifier_type_ == GREEDY; }
446 QuantifierType quantifier_type_;
453 : body_(
nullptr), index_(index), name_(
nullptr) {}
459 bool IsAnchoredAtStart()
override;
460 bool IsAnchoredAtEnd()
override;
461 Interval CaptureRegisters()
override;
462 bool IsCapture()
override;
463 int min_match()
override {
return body_->min_match(); }
464 int max_match()
override {
return body_->max_match(); }
466 void set_body(
RegExpTree* body) { body_ = body; }
467 int index() {
return index_; }
470 static int StartRegister(
int index) {
return index * 2; }
471 static int EndRegister(
int index) {
return index * 2 + 1; }
485 return body_->ToNode(compiler, on_success);
488 bool IsAnchoredAtStart()
override {
return body_->IsAnchoredAtStart(); }
489 bool IsAnchoredAtEnd()
override {
return body_->IsAnchoredAtEnd(); }
490 bool IsGroup()
override;
491 int min_match()
override {
return body_->min_match(); }
492 int max_match()
override {
return body_->max_match(); }
493 Interval CaptureRegisters()
override {
return body_->CaptureRegisters(); }
502 enum Type { LOOKAHEAD, LOOKBEHIND };
505 int capture_from, Type
type)
507 is_positive_(is_positive),
508 capture_count_(capture_count),
509 capture_from_(capture_from),
515 Interval CaptureRegisters()
override;
516 bool IsLookaround()
override;
517 bool IsAnchoredAtStart()
override;
518 int min_match()
override {
return 0; }
519 int max_match()
override {
return 0; }
521 bool is_positive() {
return is_positive_; }
522 int capture_count() {
return capture_count_; }
523 int capture_from() {
return capture_from_; }
524 Type
type() {
return type_; }
529 int stack_pointer_register,
int position_register,
530 int capture_register_count = 0,
int capture_register_start = 0);
531 RegExpNode* on_match_success() {
return on_match_success_; }
538 int stack_pointer_register_;
539 int position_register_;
554 : capture_(
nullptr), name_(
nullptr), flags_(flags) {}
556 : capture_(capture), name_(
nullptr), flags_(flags) {}
560 bool IsBackReference()
override;
561 int min_match()
override {
return 0; }
564 int max_match()
override {
return kInfinity; }
565 int index() {
return capture_->index(); }
567 void set_capture(
RegExpCapture* capture) { capture_ = capture; }
584 bool IsEmpty()
override;
585 int min_match()
override {
return 0; }
586 int max_match()
override {
return 0; }
592 #endif // V8_REGEXP_REGEXP_AST_H_