234 {
235 public:
236 enum TextType {
ATOM, CHAR_CLASS };
237
238 static TextElement Atom(RegExpAtom* atom);
239 static TextElement CharClass(RegExpCharacterClass* char_class);
240
241 intptr_t cp_offset() const { return cp_offset_; }
242 void set_cp_offset(intptr_t cp_offset) { cp_offset_ = cp_offset; }
244
245 TextType text_type() const { return text_type_; }
246
247 RegExpTree* tree() const { return tree_; }
248
249 RegExpAtom* atom() const {
251 return reinterpret_cast<RegExpAtom*>(tree());
252 }
253
254 RegExpCharacterClass* char_class() const {
255 ASSERT(text_type() == CHAR_CLASS);
256 return reinterpret_cast<RegExpCharacterClass*>(tree());
257 }
258
259 private:
260 TextElement(TextType text_type, RegExpTree* tree)
261 : cp_offset_(-1), text_type_(text_type), tree_(tree) {}
262
263 intptr_t cp_offset_;
264 TextType text_type_;
265 RegExpTree* tree_;
266
268};
269
270class Trace;
271struct PreloadState;
272class GreedyLoopState;
273class AlternativeGenerationList;
274
275struct NodeInfo {
276 NodeInfo()
277 : being_analyzed(
false),
278 been_analyzed(
false),
279 follows_word_interest(
false),
280 follows_newline_interest(
false),
281 follows_start_interest(
false),
284 replacement_calculated(
false) {}
285
286
287
288 bool Matches(NodeInfo* that) {
289 return (at_end == that->at_end) &&
290 (follows_word_interest == that->follows_word_interest) &&
291 (follows_newline_interest == that->follows_newline_interest) &&
292 (follows_start_interest == that->follows_start_interest);
293 }
294
295
296
297 void AddFromPreceding(NodeInfo* that) {
298 at_end |= that->at_end;
299 follows_word_interest |= that->follows_word_interest;
300 follows_newline_interest |= that->follows_newline_interest;
301 follows_start_interest |= that->follows_start_interest;
302 }
303
304 bool HasLookbehind() {
305 return follows_word_interest || follows_newline_interest ||
306 follows_start_interest;
307 }
308
309
310
311 void AddFromFollowing(NodeInfo* that) {
312 follows_word_interest |= that->follows_word_interest;
313 follows_newline_interest |= that->follows_newline_interest;
314 follows_start_interest |= that->follows_start_interest;
315 }
316
317 void ResetCompilationState() {
318 being_analyzed = false;
319 been_analyzed = false;
320 }
321
322 bool being_analyzed : 1;
323 bool been_analyzed : 1;
324
325
326
327 bool follows_word_interest : 1;
328 bool follows_newline_interest : 1;
329 bool follows_start_interest : 1;
330
331 bool at_end : 1;
332 bool visited : 1;
333 bool replacement_calculated : 1;
334};
335
336
337
338class QuickCheckDetails {
339 public:
340 QuickCheckDetails()
341 : characters_(0), mask_(0), value_(0), cannot_match_(
false) {}
342 explicit QuickCheckDetails(intptr_t characters)
343 : characters_(characters), mask_(0), value_(0), cannot_match_(
false) {}
344 bool Rationalize(bool one_byte);
345
346 void Merge(QuickCheckDetails* other, intptr_t from_index);
347
348 void Advance(intptr_t by, bool one_byte);
349 void Clear();
350 bool cannot_match() { return cannot_match_; }
351 void set_cannot_match() { cannot_match_ = true; }
352 struct Position {
353 Position() : mask(0),
value(0), determines_perfectly(
false) {}
354 uint16_t mask;
356 bool determines_perfectly;
357 };
358 intptr_t characters() { return characters_; }
359 void set_characters(intptr_t characters) { characters_ = characters; }
360 Position* positions(intptr_t index) {
362 ASSERT(index < characters_);
363 return positions_ + index;
364 }
365 uint32_t mask() { return mask_; }
366 uint32_t
value() {
return value_; }
367
368 private:
369
370
371 intptr_t characters_;
372 Position positions_[4];
373
374 uint32_t mask_;
375 uint32_t value_;
376
377
378 bool cannot_match_;
379
381};
382
383class RegExpNode : public ZoneAllocated {
384 public:
385 explicit RegExpNode(Zone* zone)
386 : replacement_(nullptr), trace_count_(0), zone_(zone) {
387 bm_info_[0] = bm_info_[1] = nullptr;
388 }
389 virtual ~RegExpNode();
390 virtual void Accept(NodeVisitor* visitor) = 0;
391
392 virtual void Emit(RegExpCompiler*
compiler, Trace* trace) = 0;
393
394
395
396
397
398
399
400 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
401 intptr_t budget,
402 bool not_at_start) = 0;
403
404
405
406 bool EmitQuickCheck(RegExpCompiler*
compiler,
407 Trace* bounds_check_trace,
408 Trace* trace,
409 bool preload_has_checked_bounds,
410 BlockLabel* on_possible_success,
411 QuickCheckDetails* details_return,
412 bool fall_through_on_failure);
413
414
415
416
417 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
419 intptr_t characters_filled_in,
420 bool not_at_start) = 0;
421 static constexpr intptr_t kNodeIsTooComplexForGreedyLoops = -1;
422 virtual intptr_t GreedyLoopTextLength() {
423 return kNodeIsTooComplexForGreedyLoops;
424 }
425
426
427 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
429 return nullptr;
430 }
431
432
433
434
435
436
437 static constexpr intptr_t kRecursionBudget = 200;
438 virtual void FillInBMInfo(intptr_t
offset,
439 intptr_t budget,
440 BoyerMooreLookahead* bm,
441 bool not_at_start) {
443 }
444
445
446
447
448 virtual RegExpNode* FilterOneByte(intptr_t depth) { return this; }
449
450 RegExpNode* replacement() {
452 return replacement_;
453 }
454 RegExpNode* set_replacement(RegExpNode* replacement) {
455 info()->replacement_calculated =
true;
456 replacement_ = replacement;
457 return replacement;
458 }
459
460
461
462
463
464 void SaveBMInfo(BoyerMooreLookahead* bm,
bool not_at_start, intptr_t
offset) {
465 if (
offset == 0) set_bm_info(not_at_start, bm);
466 }
467
468 BlockLabel* label() { return &label_; }
469
470
471
472
473
474 static constexpr intptr_t kMaxCopiesCodeGenerated = 10;
475
476 NodeInfo*
info() {
return &info_; }
477
478 BoyerMooreLookahead* bm_info(bool not_at_start) {
479 return bm_info_[not_at_start ? 1 : 0];
480 }
481
482 Zone* zone() const { return zone_; }
483
484 protected:
485 enum LimitResult { DONE, CONTINUE };
486 RegExpNode* replacement_;
487
488 LimitResult LimitVersions(RegExpCompiler*
compiler, Trace* trace);
489
490 void set_bm_info(bool not_at_start, BoyerMooreLookahead* bm) {
491 bm_info_[not_at_start ? 1 : 0] = bm;
492 }
493
494 private:
495 static constexpr intptr_t kFirstCharBudget = 10;
496 BlockLabel label_;
497 NodeInfo info_;
498
499
500
501
502
503 intptr_t trace_count_;
504 BoyerMooreLookahead* bm_info_[2];
505 Zone* zone_;
506};
507
508
510 public:
512 Interval(intptr_t from, intptr_t to) : from_(from), to_(to) {}
513
515 if (that.from_ ==
kNone)
516 return *this;
517 else if (from_ ==
kNone)
518 return that;
519 else
520 return Interval(Utils::Minimum(from_, that.from_),
521 Utils::Maximum(to_, that.to_));
522 }
523 bool Contains(intptr_t value)
const {
524 return (from_ <= value) && (
value <= to_);
525 }
527 intptr_t from() const { return from_; }
528 intptr_t to() const { return to_; }
530 static constexpr intptr_t
kNone = -1;
531
532 private:
533 intptr_t from_;
534 intptr_t to_;
535
537};
538
539class SeqRegExpNode : public RegExpNode {
540 public:
541 explicit SeqRegExpNode(RegExpNode* on_success)
542 : RegExpNode(on_success->zone()), on_success_(on_success) {}
543 RegExpNode* on_success() { return on_success_; }
544 void set_on_success(RegExpNode* node) { on_success_ = node; }
545 virtual RegExpNode* FilterOneByte(intptr_t depth);
546 virtual void FillInBMInfo(intptr_t
offset,
547 intptr_t budget,
548 BoyerMooreLookahead* bm,
549 bool not_at_start) {
550 on_success_->FillInBMInfo(
offset, budget - 1, bm, not_at_start);
551 if (
offset == 0) set_bm_info(not_at_start, bm);
552 }
553
554 protected:
555 RegExpNode* FilterSuccessor(intptr_t depth);
556
557 private:
558 RegExpNode* on_success_;
559};
560
561class ActionNode : public SeqRegExpNode {
562 public:
563 enum ActionType {
564 SET_REGISTER,
565 INCREMENT_REGISTER,
566 STORE_POSITION,
567 BEGIN_SUBMATCH,
568 POSITIVE_SUBMATCH_SUCCESS,
569 EMPTY_MATCH_CHECK,
570 CLEAR_CAPTURES
571 };
572 static ActionNode* SetRegister(intptr_t reg,
573 intptr_t val,
574 RegExpNode* on_success);
575 static ActionNode* IncrementRegister(intptr_t reg, RegExpNode* on_success);
576 static ActionNode* StorePosition(intptr_t reg,
577 bool is_capture,
578 RegExpNode* on_success);
579 static ActionNode* ClearCaptures(
Interval range, RegExpNode* on_success);
580 static ActionNode* BeginSubmatch(intptr_t stack_pointer_reg,
581 intptr_t position_reg,
582 RegExpNode* on_success);
583 static ActionNode* PositiveSubmatchSuccess(intptr_t stack_pointer_reg,
584 intptr_t restore_reg,
585 intptr_t clear_capture_count,
586 intptr_t clear_capture_from,
587 RegExpNode* on_success);
588 static ActionNode* EmptyMatchCheck(intptr_t start_register,
589 intptr_t repetition_register,
590 intptr_t repetition_limit,
591 RegExpNode* on_success);
592 virtual void Accept(NodeVisitor* visitor);
593 virtual void Emit(RegExpCompiler*
compiler, Trace* trace);
594 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
595 intptr_t budget,
596 bool not_at_start);
597 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
599 intptr_t filled_in,
600 bool not_at_start) {
601 return on_success()->GetQuickCheckDetails(details,
compiler, filled_in,
602 not_at_start);
603 }
604 virtual void FillInBMInfo(intptr_t
offset,
605 intptr_t budget,
606 BoyerMooreLookahead* bm,
607 bool not_at_start);
608 ActionType action_type() { return action_type_; }
609
610 virtual intptr_t GreedyLoopTextLength() {
611 return kNodeIsTooComplexForGreedyLoops;
612 }
613
614 private:
615 union {
616 struct {
617 intptr_t reg;
619 } u_store_register;
620 struct {
621 intptr_t reg;
622 } u_increment_register;
623 struct {
624 intptr_t reg;
625 bool is_capture;
626 } u_position_register;
627 struct {
628 intptr_t stack_pointer_register;
629 intptr_t current_position_register;
630 intptr_t clear_register_count;
631 intptr_t clear_register_from;
632 } u_submatch;
633 struct {
634 intptr_t start_register;
635 intptr_t repetition_register;
636 intptr_t repetition_limit;
637 } u_empty_match_check;
638 struct {
639 intptr_t range_from;
640 intptr_t range_to;
641 } u_clear_captures;
642 } data_;
643 ActionNode(ActionType action_type, RegExpNode* on_success)
644 : SeqRegExpNode(on_success), action_type_(action_type) {}
645 ActionType action_type_;
646 friend class DotPrinter;
647};
648
649class TextNode : public SeqRegExpNode {
650 public:
651 TextNode(ZoneGrowableArray<TextElement>* elms,
652 bool read_backward,
653 RegExpNode* on_success)
654 : SeqRegExpNode(on_success), elms_(elms), read_backward_(read_backward) {}
655 TextNode(RegExpCharacterClass* that,
656 bool read_backward,
657 RegExpNode* on_success)
658 : SeqRegExpNode(on_success),
659 elms_(new(zone()) ZoneGrowableArray<TextElement>(1)),
660 read_backward_(read_backward) {
661 elms_->Add(TextElement::CharClass(that));
662 }
663
664 static TextNode* CreateForCharacterRanges(
665 ZoneGrowableArray<CharacterRange>* ranges,
666 bool read_backward,
667 RegExpNode* on_success,
669
670
671 static TextNode* CreateForSurrogatePair(CharacterRange lead,
672 CharacterRange trail,
673 bool read_backward,
674 RegExpNode* on_success,
676 virtual void Accept(NodeVisitor* visitor);
677 virtual void Emit(RegExpCompiler*
compiler, Trace* trace);
678 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
679 intptr_t budget,
680 bool not_at_start);
681 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
683 intptr_t characters_filled_in,
684 bool not_at_start);
685 ZoneGrowableArray<TextElement>* elements() { return elms_; }
686 bool read_backward() { return read_backward_; }
687 void MakeCaseIndependent(bool is_one_byte);
688 virtual intptr_t GreedyLoopTextLength();
689 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
691 virtual void FillInBMInfo(intptr_t
offset,
692 intptr_t budget,
693 BoyerMooreLookahead* bm,
694 bool not_at_start);
695 void CalculateOffsets();
696 virtual RegExpNode* FilterOneByte(intptr_t depth);
697
698 private:
699 enum TextEmitPassType {
700 NON_LATIN1_MATCH,
701 SIMPLE_CHARACTER_MATCH,
702 NON_LETTER_CHARACTER_MATCH,
703 CASE_CHARACTER_MATCH,
704 CHARACTER_CLASS_MATCH
705 };
706 static bool SkipPass(intptr_t pass, bool ignore_case);
707 static constexpr intptr_t kFirstRealPass = SIMPLE_CHARACTER_MATCH;
708 static constexpr intptr_t kLastPass = CHARACTER_CLASS_MATCH;
709 void TextEmitPass(RegExpCompiler*
compiler,
710 TextEmitPassType pass,
711 bool preloaded,
712 Trace* trace,
713 bool first_element_checked,
714 intptr_t* checked_up_to);
715 intptr_t Length();
716 ZoneGrowableArray<TextElement>* elms_;
717 bool read_backward_;
718};
719
720class AssertionNode : public SeqRegExpNode {
721 public:
722 enum AssertionType {
723 AT_END,
724 AT_START,
725 AT_BOUNDARY,
726 AT_NON_BOUNDARY,
727 AFTER_NEWLINE
728 };
729 static AssertionNode* AtEnd(RegExpNode* on_success) {
730 return new (on_success->zone()) AssertionNode(AT_END, on_success);
731 }
732 static AssertionNode* AtStart(RegExpNode* on_success) {
733 return new (on_success->zone()) AssertionNode(AT_START, on_success);
734 }
735 static AssertionNode* AtBoundary(RegExpNode* on_success) {
736 return new (on_success->zone()) AssertionNode(AT_BOUNDARY, on_success);
737 }
738 static AssertionNode* AtNonBoundary(RegExpNode* on_success) {
739 return new (on_success->zone()) AssertionNode(AT_NON_BOUNDARY, on_success);
740 }
741 static AssertionNode* AfterNewline(RegExpNode* on_success) {
742 return new (on_success->zone()) AssertionNode(AFTER_NEWLINE, on_success);
743 }
744 virtual void Accept(NodeVisitor* visitor);
745 virtual void Emit(RegExpCompiler*
compiler, Trace* trace);
746 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
747 intptr_t budget,
748 bool not_at_start);
749 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
751 intptr_t filled_in,
752 bool not_at_start);
753 virtual void FillInBMInfo(intptr_t
offset,
754 intptr_t budget,
755 BoyerMooreLookahead* bm,
756 bool not_at_start);
757 AssertionType assertion_type() { return assertion_type_; }
758
759 private:
760 void EmitBoundaryCheck(RegExpCompiler*
compiler, Trace* trace);
761 enum IfPrevious { kIsNonWord, kIsWord };
762 void BacktrackIfPrevious(RegExpCompiler*
compiler,
763 Trace* trace,
764 IfPrevious backtrack_if_previous);
765 AssertionNode(AssertionType t, RegExpNode* on_success)
766 : SeqRegExpNode(on_success), assertion_type_(t) {}
767 AssertionType assertion_type_;
768};
769
770class BackReferenceNode : public SeqRegExpNode {
771 public:
772 BackReferenceNode(intptr_t start_reg,
773 intptr_t end_reg,
775 bool read_backward,
776 RegExpNode* on_success)
777 : SeqRegExpNode(on_success),
778 start_reg_(start_reg),
779 end_reg_(end_reg),
781 read_backward_(read_backward) {}
782 virtual void Accept(NodeVisitor* visitor);
783 intptr_t start_register() { return start_reg_; }
784 intptr_t end_register() { return end_reg_; }
785 bool read_backward() { return read_backward_; }
786 virtual void Emit(RegExpCompiler*
compiler, Trace* trace);
787 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
788 intptr_t recursion_depth,
789 bool not_at_start);
790 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
792 intptr_t characters_filled_in,
793 bool not_at_start) {
794 return;
795 }
796 virtual void FillInBMInfo(intptr_t
offset,
797 intptr_t budget,
798 BoyerMooreLookahead* bm,
799 bool not_at_start);
800
801 private:
802 intptr_t start_reg_;
803 intptr_t end_reg_;
804 RegExpFlags flags_;
805 bool read_backward_;
806};
807
808class EndNode : public RegExpNode {
809 public:
810 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
811 explicit EndNode(Action
action, Zone* zone)
812 : RegExpNode(zone), action_(
action) {}
813 virtual void Accept(NodeVisitor* visitor);
814 virtual void Emit(RegExpCompiler*
compiler, Trace* trace);
815 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
816 intptr_t recursion_depth,
817 bool not_at_start) {
818 return 0;
819 }
820 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
822 intptr_t characters_filled_in,
823 bool not_at_start) {
824
826 }
827 virtual void FillInBMInfo(intptr_t
offset,
828 intptr_t budget,
829 BoyerMooreLookahead* bm,
830 bool not_at_start) {
831
833 }
834
835 private:
837};
838
839class NegativeSubmatchSuccess : public EndNode {
840 public:
841 NegativeSubmatchSuccess(intptr_t stack_pointer_reg,
842 intptr_t position_reg,
843 intptr_t clear_capture_count,
844 intptr_t clear_capture_start,
845 Zone* zone)
846 : EndNode(NEGATIVE_SUBMATCH_SUCCESS, zone),
847 stack_pointer_register_(stack_pointer_reg),
848 current_position_register_(position_reg),
849 clear_capture_count_(clear_capture_count),
850 clear_capture_start_(clear_capture_start) {}
851 virtual void Emit(RegExpCompiler*
compiler, Trace* trace);
852
853 private:
854 intptr_t stack_pointer_register_;
855 intptr_t current_position_register_;
856 intptr_t clear_capture_count_;
857 intptr_t clear_capture_start_;
858};
859
860class Guard : public ZoneAllocated {
861 public:
862 enum Relation {
LT, GEQ };
863 Guard(intptr_t reg, Relation op, intptr_t value)
864 : reg_(reg), op_(op), value_(
value) {}
865 intptr_t reg() { return reg_; }
866 Relation op() { return op_; }
867 intptr_t
value() {
return value_; }
868
869 private:
870 intptr_t reg_;
871 Relation op_;
872 intptr_t value_;
873};
874
875class GuardedAlternative {
876 public:
877 explicit GuardedAlternative(RegExpNode* node)
878 : node_(node), guards_(nullptr) {}
879 void AddGuard(Guard* guard, Zone* zone);
880 RegExpNode* node() const { return node_; }
881 void set_node(RegExpNode* node) { node_ = node; }
882 ZoneGrowableArray<Guard*>* guards() const { return guards_; }
883
884 private:
885 RegExpNode* node_;
886 ZoneGrowableArray<Guard*>* guards_;
887
889};
890
891struct AlternativeGeneration;
892
893class ChoiceNode : public RegExpNode {
894 public:
895 explicit ChoiceNode(intptr_t expected_size, Zone* zone)
896 : RegExpNode(zone),
897 alternatives_(new(zone)
898 ZoneGrowableArray<GuardedAlternative>(expected_size)),
899 not_at_start_(
false),
900 being_calculated_(
false) {}
901 virtual void Accept(NodeVisitor* visitor);
902 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); }
903 ZoneGrowableArray<GuardedAlternative>* alternatives() {
904 return alternatives_;
905 }
906 virtual void Emit(RegExpCompiler*
compiler, Trace* trace);
907 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
908 intptr_t budget,
909 bool not_at_start);
910 intptr_t EatsAtLeastHelper(intptr_t still_to_find,
911 intptr_t budget,
912 RegExpNode* ignore_this_node,
913 bool not_at_start);
914 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
916 intptr_t characters_filled_in,
917 bool not_at_start);
918 virtual void FillInBMInfo(intptr_t
offset,
919 intptr_t budget,
920 BoyerMooreLookahead* bm,
921 bool not_at_start);
922
923 bool being_calculated() { return being_calculated_; }
924 bool not_at_start() { return not_at_start_; }
925 void set_not_at_start() { not_at_start_ = true; }
926 void set_being_calculated(
bool b) { being_calculated_ =
b; }
927 virtual bool try_to_emit_quick_check_for_alternative(bool is_first) {
928 return true;
929 }
930 virtual RegExpNode* FilterOneByte(intptr_t depth);
931 virtual bool read_backward() { return false; }
932
933 protected:
934 intptr_t GreedyLoopTextLengthForAlternative(
935 const GuardedAlternative* alternative);
936 ZoneGrowableArray<GuardedAlternative>* alternatives_;
937
938 private:
939 friend class Analysis;
940 void GenerateGuard(RegExpMacroAssembler* macro_assembler,
941 Guard* guard,
942 Trace* trace);
943 intptr_t CalculatePreloadCharacters(RegExpCompiler*
compiler,
944 intptr_t eats_at_least);
945 void EmitOutOfLineContinuation(RegExpCompiler*
compiler,
946 Trace* trace,
947 GuardedAlternative alternative,
948 AlternativeGeneration* alt_gen,
949 intptr_t preload_characters,
950 bool next_expects_preload);
951 void SetUpPreLoad(RegExpCompiler*
compiler,
952 Trace* current_trace,
953 PreloadState* preloads);
954 void AssertGuardsMentionRegisters(Trace* trace);
955 intptr_t EmitOptimizedUnanchoredSearch(RegExpCompiler*
compiler,
956 Trace* trace);
957 Trace* EmitGreedyLoop(RegExpCompiler*
compiler,
958 Trace* trace,
959 AlternativeGenerationList* alt_gens,
960 PreloadState* preloads,
961 GreedyLoopState* greedy_loop_state,
962 intptr_t text_length);
963 void EmitChoices(RegExpCompiler*
compiler,
964 AlternativeGenerationList* alt_gens,
965 intptr_t first_choice,
966 Trace* trace,
967 PreloadState* preloads);
968
969
970 bool not_at_start_;
971 bool being_calculated_;
972};
973
974class NegativeLookaroundChoiceNode : public ChoiceNode {
975 public:
976 explicit NegativeLookaroundChoiceNode(GuardedAlternative this_must_fail,
977 GuardedAlternative then_do_this,
978 Zone* zone)
979 : ChoiceNode(2, zone) {
980 AddAlternative(this_must_fail);
981 AddAlternative(then_do_this);
982 }
983 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
984 intptr_t budget,
985 bool not_at_start);
986 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
988 intptr_t characters_filled_in,
989 bool not_at_start);
990 virtual void FillInBMInfo(intptr_t
offset,
991 intptr_t budget,
992 BoyerMooreLookahead* bm,
993 bool not_at_start) {
994 (*alternatives_)[1].node()->FillInBMInfo(
offset, budget - 1, bm,
995 not_at_start);
996 if (
offset == 0) set_bm_info(not_at_start, bm);
997 }
998
999
1000
1001
1002
1003 virtual bool try_to_emit_quick_check_for_alternative(bool is_first) {
1004 return !is_first;
1005 }
1006 virtual RegExpNode* FilterOneByte(intptr_t depth);
1007};
1008
1009class LoopChoiceNode : public ChoiceNode {
1010 public:
1011 explicit LoopChoiceNode(bool body_can_be_zero_length,
1012 bool read_backward,
1013 Zone* zone)
1014 : ChoiceNode(2, zone),
1015 loop_node_(nullptr),
1016 continue_node_(nullptr),
1017 body_can_be_zero_length_(body_can_be_zero_length),
1018 read_backward_(read_backward) {}
1019 void AddLoopAlternative(GuardedAlternative alt);
1020 void AddContinueAlternative(GuardedAlternative alt);
1021 virtual void Emit(RegExpCompiler*
compiler, Trace* trace);
1022 virtual intptr_t EatsAtLeast(intptr_t still_to_find,
1023 intptr_t budget,
1024 bool not_at_start);
1025 virtual void GetQuickCheckDetails(QuickCheckDetails* details,
1027 intptr_t characters_filled_in,
1028 bool not_at_start);
1029 virtual void FillInBMInfo(intptr_t
offset,
1030 intptr_t budget,
1031 BoyerMooreLookahead* bm,
1032 bool not_at_start);
1033 RegExpNode* loop_node() { return loop_node_; }
1034 RegExpNode* continue_node() { return continue_node_; }
1035 bool body_can_be_zero_length() { return body_can_be_zero_length_; }
1036 virtual bool read_backward() { return read_backward_; }
1037 virtual void Accept(NodeVisitor* visitor);
1038 virtual RegExpNode* FilterOneByte(intptr_t depth);
1039
1040 private:
1041
1042
1043
1044 void AddAlternative(GuardedAlternative node) {
1045 ChoiceNode::AddAlternative(node);
1046 }
1047
1048 RegExpNode* loop_node_;
1049 RegExpNode* continue_node_;
1050 bool body_can_be_zero_length_;
1051 bool read_backward_;
1052};
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1084};
1085
1088}
1089
1091 const intptr_t* ranges,
1092 intptr_t ranges_size,
1094
1095class BoyerMoorePositionInfo : public ZoneAllocated {
1096 public:
1097 explicit BoyerMoorePositionInfo(Zone* zone)
1098 : map_(new(zone) ZoneGrowableArray<bool>(kMapSize)),
1099 map_count_(0),
1104 for (intptr_t i = 0; i < kMapSize; i++) {
1105 map_->Add(false);
1106 }
1107 }
1108
1109 bool& at(intptr_t i) { return (*map_)[i]; }
1110
1111 static constexpr intptr_t kMapSize = 128;
1112 static constexpr intptr_t
kMask = kMapSize - 1;
1113
1114 intptr_t map_count() const { return map_count_; }
1115
1117 void SetInterval(
const Interval& interval);
1118 void SetAll();
1121
1122 private:
1123 ZoneGrowableArray<bool>* map_;
1124 intptr_t map_count_;
1129};
1130
1131class BoyerMooreLookahead : public ZoneAllocated {
1132 public:
1133 BoyerMooreLookahead(intptr_t
length, RegExpCompiler*
compiler, Zone* Zone);
1134
1135 intptr_t
length() {
return length_; }
1136 intptr_t max_char() { return max_char_; }
1137 RegExpCompiler*
compiler() {
return compiler_; }
1138
1139 intptr_t Count(intptr_t map_number) {
1140 return bitmaps_->At(map_number)->map_count();
1141 }
1142
1143 BoyerMoorePositionInfo* at(intptr_t i) { return bitmaps_->At(i); }
1144
1145 void Set(intptr_t map_number, intptr_t
character) {
1147 BoyerMoorePositionInfo*
info = bitmaps_->At(map_number);
1149 }
1150
1151 void SetInterval(intptr_t map_number,
const Interval& interval) {
1152 if (interval.from() > max_char_) return;
1153 BoyerMoorePositionInfo*
info = bitmaps_->At(map_number);
1154 if (interval.to() > max_char_) {
1155 info->SetInterval(
Interval(interval.from(), max_char_));
1156 } else {
1157 info->SetInterval(interval);
1158 }
1159 }
1160
1161 void SetAll(intptr_t map_number) { bitmaps_->At(map_number)->SetAll(); }
1162
1163 void SetRest(intptr_t from_map) {
1164 for (intptr_t i = from_map; i < length_; i++)
1165 SetAll(i);
1166 }
1167 void EmitSkipInstructions(RegExpMacroAssembler* masm);
1168
1169 private:
1170
1171
1172
1173
1174 intptr_t length_;
1175 RegExpCompiler* compiler_;
1176
1177 intptr_t max_char_;
1178 ZoneGrowableArray<BoyerMoorePositionInfo*>* bitmaps_;
1179
1180 intptr_t GetSkipTable(intptr_t min_lookahead,
1181 intptr_t max_lookahead,
1182 const TypedData& boolean_skip_table);
1183 bool FindWorthwhileInterval(intptr_t* from, intptr_t* to);
1184 intptr_t FindBestInterval(intptr_t max_number_of_chars,
1185 intptr_t old_biggest_points,
1186 intptr_t* from,
1187 intptr_t* to);
1188};
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201class Trace {
1202 public:
1203
1204
1205 enum TriBool { UNKNOWN = -1, FALSE_VALUE = 0, TRUE_VALUE = 1 };
1206
1207 class DeferredAction {
1208 public:
1209 DeferredAction(ActionNode::ActionType action_type, intptr_t reg)
1210 : action_type_(action_type), reg_(reg), next_(nullptr) {}
1211 DeferredAction*
next() {
return next_; }
1212 bool Mentions(intptr_t reg);
1213 intptr_t reg() { return reg_; }
1214 ActionNode::ActionType action_type() { return action_type_; }
1215
1216 private:
1217 ActionNode::ActionType action_type_;
1218 intptr_t reg_;
1219 DeferredAction* next_;
1220 friend class Trace;
1221
1223 };
1224
1225 class DeferredCapture : public DeferredAction {
1226 public:
1227 DeferredCapture(intptr_t reg, bool is_capture, Trace* trace)
1228 : DeferredAction(ActionNode::STORE_POSITION, reg),
1229 cp_offset_(trace->cp_offset()),
1230 is_capture_(is_capture) {}
1231 intptr_t cp_offset() { return cp_offset_; }
1232 bool is_capture() { return is_capture_; }
1233
1234 private:
1235 intptr_t cp_offset_;
1236 bool is_capture_;
1237 void set_cp_offset(intptr_t cp_offset) { cp_offset_ = cp_offset; }
1238 };
1239
1240 class DeferredSetRegister : public DeferredAction {
1241 public:
1242 DeferredSetRegister(intptr_t reg, intptr_t value)
1243 : DeferredAction(ActionNode::SET_REGISTER, reg), value_(
value) {}
1244 intptr_t
value() {
return value_; }
1245
1246 private:
1247 intptr_t value_;
1248 };
1249
1250 class DeferredClearCaptures : public DeferredAction {
1251 public:
1252 explicit DeferredClearCaptures(
Interval range)
1253 : DeferredAction(ActionNode::CLEAR_CAPTURES, -1), range_(range) {}
1254 Interval range() {
return range_; }
1255
1256 private:
1258 };
1259
1260 class DeferredIncrementRegister : public DeferredAction {
1261 public:
1262 explicit DeferredIncrementRegister(intptr_t reg)
1263 : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) {}
1264 };
1265
1266 Trace()
1267 : cp_offset_(0),
1268 actions_(nullptr),
1269 backtrack_(nullptr),
1270 stop_node_(nullptr),
1271 loop_label_(nullptr),
1272 characters_preloaded_(0),
1273 bound_checked_up_to_(0),
1274 flush_budget_(100),
1275 at_start_(UNKNOWN) {}
1276
1277
1278
1279
1280
1281 void Flush(RegExpCompiler*
compiler, RegExpNode* successor);
1282 intptr_t cp_offset() { return cp_offset_; }
1283 DeferredAction* actions() { return actions_; }
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294 bool is_trivial() {
1295 return backtrack_ == nullptr && actions_ == nullptr && cp_offset_ == 0 &&
1296 characters_preloaded_ == 0 && bound_checked_up_to_ == 0 &&
1297 quick_check_performed_.characters() == 0 && at_start_ == UNKNOWN;
1298 }
1299 TriBool at_start() { return at_start_; }
1300 void set_at_start(TriBool at_start) { at_start_ = at_start; }
1301 BlockLabel* backtrack() { return backtrack_; }
1302 BlockLabel* loop_label() { return loop_label_; }
1303 RegExpNode* stop_node() { return stop_node_; }
1304 intptr_t characters_preloaded() { return characters_preloaded_; }
1305 intptr_t bound_checked_up_to() { return bound_checked_up_to_; }
1306 intptr_t flush_budget() { return flush_budget_; }
1307 QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; }
1308 bool mentions_reg(intptr_t reg);
1309
1310
1311
1312 bool GetStoredPosition(intptr_t reg, intptr_t* cp_offset);
1313
1314
1315 void add_action(DeferredAction* new_action) {
1316 ASSERT(new_action->next_ ==
nullptr);
1317 new_action->next_ = actions_;
1318 actions_ = new_action;
1319 }
1320 void set_backtrack(BlockLabel* backtrack) { backtrack_ = backtrack; }
1321 void set_stop_node(RegExpNode* node) { stop_node_ = node; }
1322 void set_loop_label(BlockLabel* label) { loop_label_ = label; }
1323 void set_characters_preloaded(intptr_t
count) {
1324 characters_preloaded_ =
count;
1325 }
1326 void set_bound_checked_up_to(intptr_t to) { bound_checked_up_to_ = to; }
1327 void set_flush_budget(intptr_t to) { flush_budget_ = to; }
1328 void set_quick_check_performed(QuickCheckDetails*
d) {
1329 quick_check_performed_ = *
d;
1330 }
1331 void InvalidateCurrentCharacter();
1332 void AdvanceCurrentPositionInTrace(intptr_t by, RegExpCompiler*
compiler);
1333
1334 private:
1335 intptr_t FindAffectedRegisters(OutSet* affected_registers, Zone* zone);
1336 void PerformDeferredActions(RegExpMacroAssembler* macro,
1337 intptr_t max_register,
1338 const OutSet& affected_registers,
1339 OutSet* registers_to_pop,
1340 OutSet* registers_to_clear,
1341 Zone* zone);
1342 void RestoreAffectedRegisters(RegExpMacroAssembler* macro,
1343 intptr_t max_register,
1344 const OutSet& registers_to_pop,
1345 const OutSet& registers_to_clear);
1346 intptr_t cp_offset_;
1347 DeferredAction* actions_;
1348 BlockLabel* backtrack_;
1349 RegExpNode* stop_node_;
1350 BlockLabel* loop_label_;
1351 intptr_t characters_preloaded_;
1352 intptr_t bound_checked_up_to_;
1353 QuickCheckDetails quick_check_performed_;
1354 intptr_t flush_budget_;
1355 TriBool at_start_;
1356
1358};
1359
1360class GreedyLoopState {
1361 public:
1362 explicit GreedyLoopState(bool not_at_start);
1363
1364 BlockLabel* label() { return &label_; }
1365 Trace* counter_backtrack_trace() { return &counter_backtrack_trace_; }
1366
1367 private:
1368 BlockLabel label_;
1369 Trace counter_backtrack_trace_;
1370};
1371
1372struct PreloadState {
1373 static constexpr intptr_t kEatsAtLeastNotYetInitialized = -1;
1374 bool preload_is_current_;
1375 bool preload_has_checked_bounds_;
1376 intptr_t preload_characters_;
1377 intptr_t eats_at_least_;
1378 void init() { eats_at_least_ = kEatsAtLeastNotYetInitialized; }
1379
1381};
1382
1383class NodeVisitor : public ValueObject {
1384 public:
1385 virtual ~NodeVisitor() {}
1386#define DECLARE_VISIT(Type) virtual void Visit##Type(Type##Node* that) = 0;
1388#undef DECLARE_VISIT
1389 virtual void VisitLoopChoice(LoopChoiceNode* that) { VisitChoice(that); }
1390};
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404class Analysis : public NodeVisitor {
1405 public:
1406 explicit Analysis(bool is_one_byte)
1407 : is_one_byte_(is_one_byte), error_message_(nullptr) {}
1408 void EnsureAnalyzed(RegExpNode* node);
1409
1410#define DECLARE_VISIT(Type) virtual void Visit##Type(Type##Node* that);
1412#undef DECLARE_VISIT
1413 virtual void VisitLoopChoice(LoopChoiceNode* that);
1414
1415 bool has_failed() { return error_message_ != nullptr; }
1416 const char* error_message() {
1417 ASSERT(error_message_ !=
nullptr);
1418 return error_message_;
1419 }
1420 void fail(
const char* error_message) { error_message_ = error_message; }
1421
1422 private:
1423 bool is_one_byte_;
1424 const char* error_message_;
1425
1427};
1428
1429struct RegExpCompileData : public ZoneAllocated {
1430 RegExpCompileData()
1431 : tree(nullptr),
1432 node(nullptr),
1434 contains_anchor(
false),
1435 capture_name_map(Array::Handle(Array::null())),
1436 error(String::Handle(String::null())),
1437 capture_count(0) {}
1438 RegExpTree* tree;
1439 RegExpNode* node;
1440 bool simple;
1441 bool contains_anchor;
1442 Array& capture_name_map;
1444 intptr_t capture_count;
1445};
1446
1447class RegExpEngine : public AllStatic {
1448 public:
1449 struct CompilationResult {
1450 explicit CompilationResult(const char* error_message)
1451 : error_message(error_message),
1452#
if !defined(DART_PRECOMPILED_RUNTIME)
1453 backtrack_goto(nullptr),
1454 graph_entry(nullptr),
1455 num_blocks(-1),
1456 num_stack_locals(-1),
1457#endif
1458 bytecode(nullptr),
1459 num_registers(-1) {
1460 }
1461
1462 CompilationResult(TypedData* bytecode, intptr_t num_registers)
1463 : error_message(nullptr),
1464#
if !defined(DART_PRECOMPILED_RUNTIME)
1465 backtrack_goto(nullptr),
1466 graph_entry(nullptr),
1467 num_blocks(-1),
1468 num_stack_locals(-1),
1469#endif
1470 bytecode(bytecode),
1471 num_registers(num_registers) {
1472 }
1473
1474#if !defined(DART_PRECOMPILED_RUNTIME)
1475 CompilationResult(IndirectGotoInstr* backtrack_goto,
1476 GraphEntryInstr* graph_entry,
1477 intptr_t num_blocks,
1478 intptr_t num_stack_locals,
1479 intptr_t num_registers)
1480 : error_message(nullptr),
1481 backtrack_goto(backtrack_goto),
1482 graph_entry(graph_entry),
1483 num_blocks(num_blocks),
1484 num_stack_locals(num_stack_locals),
1485 bytecode(nullptr) {}
1486#endif
1487
1488 const char* error_message;
1489
1494
1495 TypedData* bytecode;
1496 intptr_t num_registers;
1497 };
1498
1499#if !defined(DART_PRECOMPILED_RUNTIME)
1500 static CompilationResult CompileIR(
1501 RegExpCompileData* input,
1502 const ParsedFunction* parsed_function,
1503 const ZoneGrowableArray<const ICData*>& ic_data_array,
1504 intptr_t osr_id);
1505#endif
1506
1507 static CompilationResult CompileBytecode(RegExpCompileData* data,
1508 const RegExp& regexp,
1509 bool is_one_byte,
1510 bool sticky,
1511 Zone* zone);
1512
1513 static RegExpPtr CreateRegExp(Thread* thread,
1514 const String& pattern,
1516
1517 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case);
1518};
1519
1521 Zone* zone,
1522 const RegExp& regexp,
1523 intptr_t specialization_cid,
1524 bool sticky,
1525 const Object& owner);
1526
1527}
1528
1529#endif
static void fail(const SkString &err)
static void info(const char *fmt,...) SK_PRINTF_LIKE(1
static constexpr uint64_t kMask
static void is_empty(skiatest::Reporter *reporter, const SkPath &p)
static float next(float f)
static void Union(SkRegion *rgn, const SkIRect &rect)
#define DECLARE_VISIT(type, attrs)
VULKAN_HPP_DEFAULT_DISPATCH_LOADER_DYNAMIC_STORAGE auto & d
FlutterSemanticsFlag flags
const uint8_t uint32_t uint32_t GError ** error
bool Contains(const Container &container, const Value &value)
ContainedInLattice AddRange(ContainedInLattice containment, const int32_t *ranges, intptr_t ranges_length, Interval new_range)
void CreateSpecializedFunction(Thread *thread, Zone *zone, const RegExp ®exp, intptr_t specialization_cid, bool sticky, const Object &owner)
ContainedInLattice Combine(ContainedInLattice a, ContainedInLattice b)
void Flush(SkSurface *surface)
#define FOR_EACH_NODE_TYPE(VISIT)
#define NOT_IN_PRECOMPILED(code)