OLD | NEW |
---|---|
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 564 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
575 virtual void Accept(NodeVisitor* visitor) = 0; | 575 virtual void Accept(NodeVisitor* visitor) = 0; |
576 // Generates a goto to this node or actually generates the code at this point. | 576 // Generates a goto to this node or actually generates the code at this point. |
577 virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0; | 577 virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0; |
578 // How many characters must this node consume at a minimum in order to | 578 // How many characters must this node consume at a minimum in order to |
579 // succeed. If we have found at least 'still_to_find' characters that | 579 // succeed. If we have found at least 'still_to_find' characters that |
580 // must be consumed there is no need to ask any following nodes whether | 580 // must be consumed there is no need to ask any following nodes whether |
581 // they are sure to eat any more characters. The not_at_start argument is | 581 // they are sure to eat any more characters. The not_at_start argument is |
582 // used to indicate that we know we are not at the start of the input. In | 582 // used to indicate that we know we are not at the start of the input. In |
583 // this case anchored branches will always fail and can be ignored when | 583 // this case anchored branches will always fail and can be ignored when |
584 // determining how many characters are consumed on success. | 584 // determining how many characters are consumed on success. |
585 virtual int EatsAtLeast(int still_to_find, | 585 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start) = 0; |
586 int recursion_depth, | |
587 bool not_at_start) = 0; | |
588 // Emits some quick code that checks whether the preloaded characters match. | 586 // Emits some quick code that checks whether the preloaded characters match. |
589 // Falls through on certain failure, jumps to the label on possible success. | 587 // Falls through on certain failure, jumps to the label on possible success. |
590 // If the node cannot make a quick check it does nothing and returns false. | 588 // If the node cannot make a quick check it does nothing and returns false. |
591 bool EmitQuickCheck(RegExpCompiler* compiler, | 589 bool EmitQuickCheck(RegExpCompiler* compiler, |
592 Trace* trace, | 590 Trace* trace, |
593 bool preload_has_checked_bounds, | 591 bool preload_has_checked_bounds, |
594 Label* on_possible_success, | 592 Label* on_possible_success, |
595 QuickCheckDetails* details_return, | 593 QuickCheckDetails* details_return, |
596 bool fall_through_on_failure); | 594 bool fall_through_on_failure); |
597 // For a given number of characters this returns a mask and a value. The | 595 // For a given number of characters this returns a mask and a value. The |
(...skipping 11 matching lines...) Expand all Loading... | |
609 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( | 607 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( |
610 RegExpCompiler* compiler) { | 608 RegExpCompiler* compiler) { |
611 return NULL; | 609 return NULL; |
612 } | 610 } |
613 | 611 |
614 // Collects information on the possible code units (mod 128) that can match if | 612 // Collects information on the possible code units (mod 128) that can match if |
615 // we look forward. This is used for a Boyer-Moore-like string searching | 613 // we look forward. This is used for a Boyer-Moore-like string searching |
616 // implementation. TODO(erikcorry): This should share more code with | 614 // implementation. TODO(erikcorry): This should share more code with |
617 // EatsAtLeast, GetQuickCheckDetails. The budget argument is used to limit | 615 // EatsAtLeast, GetQuickCheckDetails. The budget argument is used to limit |
618 // the number of nodes we are willing to look at in order to create this data. | 616 // the number of nodes we are willing to look at in order to create this data. |
619 static const int kFillInBMBudget = 200; | 617 static const int kFillInBMBudget = 200; |
erikcorry
2013/03/01 09:15:53
This seems misnamed now. How about kRecursionBudg
| |
620 virtual void FillInBMInfo(int offset, | 618 virtual void FillInBMInfo(int offset, |
621 int recursion_depth, | |
622 int budget, | 619 int budget, |
623 BoyerMooreLookahead* bm, | 620 BoyerMooreLookahead* bm, |
624 bool not_at_start) { | 621 bool not_at_start) { |
625 UNREACHABLE(); | 622 UNREACHABLE(); |
626 } | 623 } |
627 | 624 |
628 // If we know that the input is ASCII then there are some nodes that can | 625 // If we know that the input is ASCII then there are some nodes that can |
629 // never match. This method returns a node that can be substituted for | 626 // never match. This method returns a node that can be substituted for |
630 // itself, or NULL if the node can never match. | 627 // itself, or NULL if the node can never match. |
631 virtual RegExpNode* FilterASCII(int depth, bool ignore_case) { return this; } | 628 virtual RegExpNode* FilterASCII(int depth, bool ignore_case) { return this; } |
(...skipping 86 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
718 | 715 |
719 | 716 |
720 class SeqRegExpNode: public RegExpNode { | 717 class SeqRegExpNode: public RegExpNode { |
721 public: | 718 public: |
722 explicit SeqRegExpNode(RegExpNode* on_success) | 719 explicit SeqRegExpNode(RegExpNode* on_success) |
723 : RegExpNode(on_success->zone()), on_success_(on_success) { } | 720 : RegExpNode(on_success->zone()), on_success_(on_success) { } |
724 RegExpNode* on_success() { return on_success_; } | 721 RegExpNode* on_success() { return on_success_; } |
725 void set_on_success(RegExpNode* node) { on_success_ = node; } | 722 void set_on_success(RegExpNode* node) { on_success_ = node; } |
726 virtual RegExpNode* FilterASCII(int depth, bool ignore_case); | 723 virtual RegExpNode* FilterASCII(int depth, bool ignore_case); |
727 virtual void FillInBMInfo(int offset, | 724 virtual void FillInBMInfo(int offset, |
728 int recursion_depth, | |
729 int budget, | 725 int budget, |
730 BoyerMooreLookahead* bm, | 726 BoyerMooreLookahead* bm, |
731 bool not_at_start) { | 727 bool not_at_start) { |
732 on_success_->FillInBMInfo( | 728 on_success_->FillInBMInfo(offset, budget - 1, bm, not_at_start); |
733 offset, recursion_depth + 1, budget - 1, bm, not_at_start); | |
734 if (offset == 0) set_bm_info(not_at_start, bm); | 729 if (offset == 0) set_bm_info(not_at_start, bm); |
735 } | 730 } |
736 | 731 |
737 protected: | 732 protected: |
738 RegExpNode* FilterSuccessor(int depth, bool ignore_case); | 733 RegExpNode* FilterSuccessor(int depth, bool ignore_case); |
739 | 734 |
740 private: | 735 private: |
741 RegExpNode* on_success_; | 736 RegExpNode* on_success_; |
742 }; | 737 }; |
743 | 738 |
(...skipping 22 matching lines...) Expand all Loading... | |
766 int restore_reg, | 761 int restore_reg, |
767 int clear_capture_count, | 762 int clear_capture_count, |
768 int clear_capture_from, | 763 int clear_capture_from, |
769 RegExpNode* on_success); | 764 RegExpNode* on_success); |
770 static ActionNode* EmptyMatchCheck(int start_register, | 765 static ActionNode* EmptyMatchCheck(int start_register, |
771 int repetition_register, | 766 int repetition_register, |
772 int repetition_limit, | 767 int repetition_limit, |
773 RegExpNode* on_success); | 768 RegExpNode* on_success); |
774 virtual void Accept(NodeVisitor* visitor); | 769 virtual void Accept(NodeVisitor* visitor); |
775 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 770 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
776 virtual int EatsAtLeast(int still_to_find, | 771 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); |
777 int recursion_depth, | |
778 bool not_at_start); | |
779 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 772 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
780 RegExpCompiler* compiler, | 773 RegExpCompiler* compiler, |
781 int filled_in, | 774 int filled_in, |
782 bool not_at_start) { | 775 bool not_at_start) { |
783 return on_success()->GetQuickCheckDetails( | 776 return on_success()->GetQuickCheckDetails( |
784 details, compiler, filled_in, not_at_start); | 777 details, compiler, filled_in, not_at_start); |
785 } | 778 } |
786 virtual void FillInBMInfo(int offset, | 779 virtual void FillInBMInfo(int offset, |
787 int recursion_depth, | |
788 int budget, | 780 int budget, |
789 BoyerMooreLookahead* bm, | 781 BoyerMooreLookahead* bm, |
790 bool not_at_start); | 782 bool not_at_start); |
791 Type type() { return type_; } | 783 Type type() { return type_; } |
792 // TODO(erikcorry): We should allow some action nodes in greedy loops. | 784 // TODO(erikcorry): We should allow some action nodes in greedy loops. |
793 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } | 785 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } |
794 | 786 |
795 private: | 787 private: |
796 union { | 788 union { |
797 struct { | 789 struct { |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
836 : SeqRegExpNode(on_success), | 828 : SeqRegExpNode(on_success), |
837 elms_(elms) { } | 829 elms_(elms) { } |
838 TextNode(RegExpCharacterClass* that, | 830 TextNode(RegExpCharacterClass* that, |
839 RegExpNode* on_success) | 831 RegExpNode* on_success) |
840 : SeqRegExpNode(on_success), | 832 : SeqRegExpNode(on_success), |
841 elms_(new(zone()) ZoneList<TextElement>(1, zone())) { | 833 elms_(new(zone()) ZoneList<TextElement>(1, zone())) { |
842 elms_->Add(TextElement::CharClass(that), zone()); | 834 elms_->Add(TextElement::CharClass(that), zone()); |
843 } | 835 } |
844 virtual void Accept(NodeVisitor* visitor); | 836 virtual void Accept(NodeVisitor* visitor); |
845 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 837 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
846 virtual int EatsAtLeast(int still_to_find, | 838 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); |
847 int recursion_depth, | |
848 bool not_at_start); | |
849 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 839 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
850 RegExpCompiler* compiler, | 840 RegExpCompiler* compiler, |
851 int characters_filled_in, | 841 int characters_filled_in, |
852 bool not_at_start); | 842 bool not_at_start); |
853 ZoneList<TextElement>* elements() { return elms_; } | 843 ZoneList<TextElement>* elements() { return elms_; } |
854 void MakeCaseIndependent(bool is_ascii); | 844 void MakeCaseIndependent(bool is_ascii); |
855 virtual int GreedyLoopTextLength(); | 845 virtual int GreedyLoopTextLength(); |
856 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( | 846 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( |
857 RegExpCompiler* compiler); | 847 RegExpCompiler* compiler); |
858 virtual void FillInBMInfo(int offset, | 848 virtual void FillInBMInfo(int offset, |
859 int recursion_depth, | |
860 int budget, | 849 int budget, |
861 BoyerMooreLookahead* bm, | 850 BoyerMooreLookahead* bm, |
862 bool not_at_start); | 851 bool not_at_start); |
863 void CalculateOffsets(); | 852 void CalculateOffsets(); |
864 virtual RegExpNode* FilterASCII(int depth, bool ignore_case); | 853 virtual RegExpNode* FilterASCII(int depth, bool ignore_case); |
865 | 854 |
866 private: | 855 private: |
867 enum TextEmitPassType { | 856 enum TextEmitPassType { |
868 NON_ASCII_MATCH, // Check for characters that can't match. | 857 NON_ASCII_MATCH, // Check for characters that can't match. |
869 SIMPLE_CHARACTER_MATCH, // Case-dependent single character check. | 858 SIMPLE_CHARACTER_MATCH, // Case-dependent single character check. |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
904 return new(on_success->zone()) AssertionNode(AT_BOUNDARY, on_success); | 893 return new(on_success->zone()) AssertionNode(AT_BOUNDARY, on_success); |
905 } | 894 } |
906 static AssertionNode* AtNonBoundary(RegExpNode* on_success) { | 895 static AssertionNode* AtNonBoundary(RegExpNode* on_success) { |
907 return new(on_success->zone()) AssertionNode(AT_NON_BOUNDARY, on_success); | 896 return new(on_success->zone()) AssertionNode(AT_NON_BOUNDARY, on_success); |
908 } | 897 } |
909 static AssertionNode* AfterNewline(RegExpNode* on_success) { | 898 static AssertionNode* AfterNewline(RegExpNode* on_success) { |
910 return new(on_success->zone()) AssertionNode(AFTER_NEWLINE, on_success); | 899 return new(on_success->zone()) AssertionNode(AFTER_NEWLINE, on_success); |
911 } | 900 } |
912 virtual void Accept(NodeVisitor* visitor); | 901 virtual void Accept(NodeVisitor* visitor); |
913 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 902 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
914 virtual int EatsAtLeast(int still_to_find, | 903 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); |
915 int recursion_depth, | |
916 bool not_at_start); | |
917 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 904 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
918 RegExpCompiler* compiler, | 905 RegExpCompiler* compiler, |
919 int filled_in, | 906 int filled_in, |
920 bool not_at_start); | 907 bool not_at_start); |
921 virtual void FillInBMInfo(int offset, | 908 virtual void FillInBMInfo(int offset, |
922 int recursion_depth, | |
923 int budget, | 909 int budget, |
924 BoyerMooreLookahead* bm, | 910 BoyerMooreLookahead* bm, |
925 bool not_at_start); | 911 bool not_at_start); |
926 AssertionNodeType type() { return type_; } | 912 AssertionNodeType type() { return type_; } |
927 void set_type(AssertionNodeType type) { type_ = type; } | 913 void set_type(AssertionNodeType type) { type_ = type; } |
928 | 914 |
929 private: | 915 private: |
930 void EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace); | 916 void EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace); |
931 enum IfPrevious { kIsNonWord, kIsWord }; | 917 enum IfPrevious { kIsNonWord, kIsWord }; |
932 void BacktrackIfPrevious(RegExpCompiler* compiler, | 918 void BacktrackIfPrevious(RegExpCompiler* compiler, |
(...skipping 20 matching lines...) Expand all Loading... | |
953 virtual int EatsAtLeast(int still_to_find, | 939 virtual int EatsAtLeast(int still_to_find, |
954 int recursion_depth, | 940 int recursion_depth, |
955 bool not_at_start); | 941 bool not_at_start); |
956 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 942 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
957 RegExpCompiler* compiler, | 943 RegExpCompiler* compiler, |
958 int characters_filled_in, | 944 int characters_filled_in, |
959 bool not_at_start) { | 945 bool not_at_start) { |
960 return; | 946 return; |
961 } | 947 } |
962 virtual void FillInBMInfo(int offset, | 948 virtual void FillInBMInfo(int offset, |
963 int recursion_depth, | |
964 int budget, | 949 int budget, |
965 BoyerMooreLookahead* bm, | 950 BoyerMooreLookahead* bm, |
966 bool not_at_start); | 951 bool not_at_start); |
967 | 952 |
968 private: | 953 private: |
969 int start_reg_; | 954 int start_reg_; |
970 int end_reg_; | 955 int end_reg_; |
971 }; | 956 }; |
972 | 957 |
973 | 958 |
974 class EndNode: public RegExpNode { | 959 class EndNode: public RegExpNode { |
975 public: | 960 public: |
976 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; | 961 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; |
977 explicit EndNode(Action action, Zone* zone) | 962 explicit EndNode(Action action, Zone* zone) |
978 : RegExpNode(zone), action_(action) { } | 963 : RegExpNode(zone), action_(action) { } |
979 virtual void Accept(NodeVisitor* visitor); | 964 virtual void Accept(NodeVisitor* visitor); |
980 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 965 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
981 virtual int EatsAtLeast(int still_to_find, | 966 virtual int EatsAtLeast(int still_to_find, |
982 int recursion_depth, | 967 int recursion_depth, |
983 bool not_at_start) { return 0; } | 968 bool not_at_start) { return 0; } |
984 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 969 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
985 RegExpCompiler* compiler, | 970 RegExpCompiler* compiler, |
986 int characters_filled_in, | 971 int characters_filled_in, |
987 bool not_at_start) { | 972 bool not_at_start) { |
988 // Returning 0 from EatsAtLeast should ensure we never get here. | 973 // Returning 0 from EatsAtLeast should ensure we never get here. |
989 UNREACHABLE(); | 974 UNREACHABLE(); |
990 } | 975 } |
991 virtual void FillInBMInfo(int offset, | 976 virtual void FillInBMInfo(int offset, |
992 int recursion_depth, | |
993 int budget, | 977 int budget, |
994 BoyerMooreLookahead* bm, | 978 BoyerMooreLookahead* bm, |
995 bool not_at_start) { | 979 bool not_at_start) { |
996 // Returning 0 from EatsAtLeast should ensure we never get here. | 980 // Returning 0 from EatsAtLeast should ensure we never get here. |
997 UNREACHABLE(); | 981 UNREACHABLE(); |
998 } | 982 } |
999 | 983 |
1000 private: | 984 private: |
1001 Action action_; | 985 Action action_; |
1002 }; | 986 }; |
(...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1068 table_(NULL), | 1052 table_(NULL), |
1069 not_at_start_(false), | 1053 not_at_start_(false), |
1070 being_calculated_(false) { } | 1054 being_calculated_(false) { } |
1071 virtual void Accept(NodeVisitor* visitor); | 1055 virtual void Accept(NodeVisitor* visitor); |
1072 void AddAlternative(GuardedAlternative node) { | 1056 void AddAlternative(GuardedAlternative node) { |
1073 alternatives()->Add(node, zone()); | 1057 alternatives()->Add(node, zone()); |
1074 } | 1058 } |
1075 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } | 1059 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } |
1076 DispatchTable* GetTable(bool ignore_case); | 1060 DispatchTable* GetTable(bool ignore_case); |
1077 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 1061 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
1078 virtual int EatsAtLeast(int still_to_find, | 1062 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); |
1079 int recursion_depth, | |
1080 bool not_at_start); | |
1081 int EatsAtLeastHelper(int still_to_find, | 1063 int EatsAtLeastHelper(int still_to_find, |
1082 int recursion_depth, | 1064 int budget, |
1083 RegExpNode* ignore_this_node, | 1065 RegExpNode* ignore_this_node, |
1084 bool not_at_start); | 1066 bool not_at_start); |
1085 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 1067 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
1086 RegExpCompiler* compiler, | 1068 RegExpCompiler* compiler, |
1087 int characters_filled_in, | 1069 int characters_filled_in, |
1088 bool not_at_start); | 1070 bool not_at_start); |
1089 virtual void FillInBMInfo(int offset, | 1071 virtual void FillInBMInfo(int offset, |
1090 int recursion_depth, | |
1091 int budget, | 1072 int budget, |
1092 BoyerMooreLookahead* bm, | 1073 BoyerMooreLookahead* bm, |
1093 bool not_at_start); | 1074 bool not_at_start); |
1094 | 1075 |
1095 bool being_calculated() { return being_calculated_; } | 1076 bool being_calculated() { return being_calculated_; } |
1096 bool not_at_start() { return not_at_start_; } | 1077 bool not_at_start() { return not_at_start_; } |
1097 void set_not_at_start() { not_at_start_ = true; } | 1078 void set_not_at_start() { not_at_start_ = true; } |
1098 void set_being_calculated(bool b) { being_calculated_ = b; } | 1079 void set_being_calculated(bool b) { being_calculated_ = b; } |
1099 virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; } | 1080 virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; } |
1100 virtual RegExpNode* FilterASCII(int depth, bool ignore_case); | 1081 virtual RegExpNode* FilterASCII(int depth, bool ignore_case); |
(...skipping 25 matching lines...) Expand all Loading... | |
1126 | 1107 |
1127 class NegativeLookaheadChoiceNode: public ChoiceNode { | 1108 class NegativeLookaheadChoiceNode: public ChoiceNode { |
1128 public: | 1109 public: |
1129 explicit NegativeLookaheadChoiceNode(GuardedAlternative this_must_fail, | 1110 explicit NegativeLookaheadChoiceNode(GuardedAlternative this_must_fail, |
1130 GuardedAlternative then_do_this, | 1111 GuardedAlternative then_do_this, |
1131 Zone* zone) | 1112 Zone* zone) |
1132 : ChoiceNode(2, zone) { | 1113 : ChoiceNode(2, zone) { |
1133 AddAlternative(this_must_fail); | 1114 AddAlternative(this_must_fail); |
1134 AddAlternative(then_do_this); | 1115 AddAlternative(then_do_this); |
1135 } | 1116 } |
1136 virtual int EatsAtLeast(int still_to_find, | 1117 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); |
1137 int recursion_depth, | |
1138 bool not_at_start); | |
1139 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 1118 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
1140 RegExpCompiler* compiler, | 1119 RegExpCompiler* compiler, |
1141 int characters_filled_in, | 1120 int characters_filled_in, |
1142 bool not_at_start); | 1121 bool not_at_start); |
1143 virtual void FillInBMInfo(int offset, | 1122 virtual void FillInBMInfo(int offset, |
1144 int recursion_depth, | |
1145 int budget, | 1123 int budget, |
1146 BoyerMooreLookahead* bm, | 1124 BoyerMooreLookahead* bm, |
1147 bool not_at_start) { | 1125 bool not_at_start) { |
1148 alternatives_->at(1).node()->FillInBMInfo( | 1126 alternatives_->at(1).node()->FillInBMInfo( |
1149 offset, recursion_depth + 1, budget - 1, bm, not_at_start); | 1127 offset, budget - 1, bm, not_at_start); |
1150 if (offset == 0) set_bm_info(not_at_start, bm); | 1128 if (offset == 0) set_bm_info(not_at_start, bm); |
1151 } | 1129 } |
1152 // For a negative lookahead we don't emit the quick check for the | 1130 // For a negative lookahead we don't emit the quick check for the |
1153 // alternative that is expected to fail. This is because quick check code | 1131 // alternative that is expected to fail. This is because quick check code |
1154 // starts by loading enough characters for the alternative that takes fewest | 1132 // starts by loading enough characters for the alternative that takes fewest |
1155 // characters, but on a negative lookahead the negative branch did not take | 1133 // characters, but on a negative lookahead the negative branch did not take |
1156 // part in that calculation (EatsAtLeast) so the assumptions don't hold. | 1134 // part in that calculation (EatsAtLeast) so the assumptions don't hold. |
1157 virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; } | 1135 virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; } |
1158 virtual RegExpNode* FilterASCII(int depth, bool ignore_case); | 1136 virtual RegExpNode* FilterASCII(int depth, bool ignore_case); |
1159 }; | 1137 }; |
1160 | 1138 |
1161 | 1139 |
1162 class LoopChoiceNode: public ChoiceNode { | 1140 class LoopChoiceNode: public ChoiceNode { |
1163 public: | 1141 public: |
1164 explicit LoopChoiceNode(bool body_can_be_zero_length, Zone* zone) | 1142 explicit LoopChoiceNode(bool body_can_be_zero_length, Zone* zone) |
1165 : ChoiceNode(2, zone), | 1143 : ChoiceNode(2, zone), |
1166 loop_node_(NULL), | 1144 loop_node_(NULL), |
1167 continue_node_(NULL), | 1145 continue_node_(NULL), |
1168 body_can_be_zero_length_(body_can_be_zero_length) { } | 1146 body_can_be_zero_length_(body_can_be_zero_length) { } |
1169 void AddLoopAlternative(GuardedAlternative alt); | 1147 void AddLoopAlternative(GuardedAlternative alt); |
1170 void AddContinueAlternative(GuardedAlternative alt); | 1148 void AddContinueAlternative(GuardedAlternative alt); |
1171 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 1149 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
1172 virtual int EatsAtLeast(int still_to_find, | 1150 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); |
1173 int recursion_depth, | |
1174 bool not_at_start); | |
1175 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 1151 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
1176 RegExpCompiler* compiler, | 1152 RegExpCompiler* compiler, |
1177 int characters_filled_in, | 1153 int characters_filled_in, |
1178 bool not_at_start); | 1154 bool not_at_start); |
1179 virtual void FillInBMInfo(int offset, | 1155 virtual void FillInBMInfo(int offset, |
1180 int recursion_depth, | |
1181 int budget, | 1156 int budget, |
1182 BoyerMooreLookahead* bm, | 1157 BoyerMooreLookahead* bm, |
1183 bool not_at_start); | 1158 bool not_at_start); |
1184 RegExpNode* loop_node() { return loop_node_; } | 1159 RegExpNode* loop_node() { return loop_node_; } |
1185 RegExpNode* continue_node() { return continue_node_; } | 1160 RegExpNode* continue_node() { return continue_node_; } |
1186 bool body_can_be_zero_length() { return body_can_be_zero_length_; } | 1161 bool body_can_be_zero_length() { return body_can_be_zero_length_; } |
1187 virtual void Accept(NodeVisitor* visitor); | 1162 virtual void Accept(NodeVisitor* visitor); |
1188 virtual RegExpNode* FilterASCII(int depth, bool ignore_case); | 1163 virtual RegExpNode* FilterASCII(int depth, bool ignore_case); |
1189 | 1164 |
1190 private: | 1165 private: |
(...skipping 449 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1640 Handle<String> sample_subject, | 1615 Handle<String> sample_subject, |
1641 bool is_ascii, Zone* zone); | 1616 bool is_ascii, Zone* zone); |
1642 | 1617 |
1643 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case); | 1618 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case); |
1644 }; | 1619 }; |
1645 | 1620 |
1646 | 1621 |
1647 } } // namespace v8::internal | 1622 } } // namespace v8::internal |
1648 | 1623 |
1649 #endif // V8_JSREGEXP_H_ | 1624 #endif // V8_JSREGEXP_H_ |
OLD | NEW |