OLD | NEW |
1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 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 574 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
585 class RegExpNode: public ZoneObject { | 585 class RegExpNode: public ZoneObject { |
586 public: | 586 public: |
587 RegExpNode() : trace_count_(0) { } | 587 RegExpNode() : trace_count_(0) { } |
588 virtual ~RegExpNode(); | 588 virtual ~RegExpNode(); |
589 virtual void Accept(NodeVisitor* visitor) = 0; | 589 virtual void Accept(NodeVisitor* visitor) = 0; |
590 // Generates a goto to this node or actually generates the code at this point. | 590 // Generates a goto to this node or actually generates the code at this point. |
591 // Until the implementation is complete we will return true for success and | 591 // Until the implementation is complete we will return true for success and |
592 // false for failure. | 592 // false for failure. |
593 virtual bool Emit(RegExpCompiler* compiler, Trace* trace) = 0; | 593 virtual bool Emit(RegExpCompiler* compiler, Trace* trace) = 0; |
594 // How many characters must this node consume at a minimum in order to | 594 // How many characters must this node consume at a minimum in order to |
595 // succeed. | 595 // succeed. If we have found at least 'still_to_find' characters that |
596 virtual int EatsAtLeast(int recursion_depth) = 0; | 596 // must be consumed there is no need to ask any following nodes whether |
| 597 // they are sure to eat any more characters. |
| 598 virtual int EatsAtLeast(int still_to_find, int recursion_depth) = 0; |
597 // Emits some quick code that checks whether the preloaded characters match. | 599 // Emits some quick code that checks whether the preloaded characters match. |
598 // Falls through on certain failure, jumps to the label on possible success. | 600 // Falls through on certain failure, jumps to the label on possible success. |
599 // If the node cannot make a quick check it does nothing and returns false. | 601 // If the node cannot make a quick check it does nothing and returns false. |
600 bool EmitQuickCheck(RegExpCompiler* compiler, | 602 bool EmitQuickCheck(RegExpCompiler* compiler, |
601 Trace* trace, | 603 Trace* trace, |
602 bool preload_has_checked_bounds, | 604 bool preload_has_checked_bounds, |
603 Label* on_possible_success, | 605 Label* on_possible_success, |
604 QuickCheckDetails* details_return, | 606 QuickCheckDetails* details_return, |
605 bool fall_through_on_failure); | 607 bool fall_through_on_failure); |
606 // For a given number of characters this returns a mask and a value. The | 608 // For a given number of characters this returns a mask and a value. The |
(...skipping 119 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
726 RegExpNode* on_success); | 728 RegExpNode* on_success); |
727 static ActionNode* PositiveSubmatchSuccess(int stack_pointer_reg, | 729 static ActionNode* PositiveSubmatchSuccess(int stack_pointer_reg, |
728 int restore_reg, | 730 int restore_reg, |
729 RegExpNode* on_success); | 731 RegExpNode* on_success); |
730 static ActionNode* EmptyMatchCheck(int start_register, | 732 static ActionNode* EmptyMatchCheck(int start_register, |
731 int repetition_register, | 733 int repetition_register, |
732 int repetition_limit, | 734 int repetition_limit, |
733 RegExpNode* on_success); | 735 RegExpNode* on_success); |
734 virtual void Accept(NodeVisitor* visitor); | 736 virtual void Accept(NodeVisitor* visitor); |
735 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 737 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
736 virtual int EatsAtLeast(int recursion_depth); | 738 virtual int EatsAtLeast(int still_to_find, int recursion_depth); |
737 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 739 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
738 RegExpCompiler* compiler, | 740 RegExpCompiler* compiler, |
739 int filled_in) { | 741 int filled_in) { |
740 return on_success()->GetQuickCheckDetails(details, compiler, filled_in); | 742 return on_success()->GetQuickCheckDetails(details, compiler, filled_in); |
741 } | 743 } |
742 Type type() { return type_; } | 744 Type type() { return type_; } |
743 // TODO(erikcorry): We should allow some action nodes in greedy loops. | 745 // TODO(erikcorry): We should allow some action nodes in greedy loops. |
744 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } | 746 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } |
745 virtual ActionNode* Clone() { return new ActionNode(*this); } | 747 virtual ActionNode* Clone() { return new ActionNode(*this); } |
746 | 748 |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
785 : SeqRegExpNode(on_success), | 787 : SeqRegExpNode(on_success), |
786 elms_(elms) { } | 788 elms_(elms) { } |
787 TextNode(RegExpCharacterClass* that, | 789 TextNode(RegExpCharacterClass* that, |
788 RegExpNode* on_success) | 790 RegExpNode* on_success) |
789 : SeqRegExpNode(on_success), | 791 : SeqRegExpNode(on_success), |
790 elms_(new ZoneList<TextElement>(1)) { | 792 elms_(new ZoneList<TextElement>(1)) { |
791 elms_->Add(TextElement::CharClass(that)); | 793 elms_->Add(TextElement::CharClass(that)); |
792 } | 794 } |
793 virtual void Accept(NodeVisitor* visitor); | 795 virtual void Accept(NodeVisitor* visitor); |
794 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 796 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
795 virtual int EatsAtLeast(int recursion_depth); | 797 virtual int EatsAtLeast(int still_to_find, int recursion_depth); |
796 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 798 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
797 RegExpCompiler* compiler, | 799 RegExpCompiler* compiler, |
798 int characters_filled_in); | 800 int characters_filled_in); |
799 ZoneList<TextElement>* elements() { return elms_; } | 801 ZoneList<TextElement>* elements() { return elms_; } |
800 void MakeCaseIndependent(); | 802 void MakeCaseIndependent(); |
801 virtual int GreedyLoopTextLength(); | 803 virtual int GreedyLoopTextLength(); |
802 virtual TextNode* Clone() { | 804 virtual TextNode* Clone() { |
803 TextNode* result = new TextNode(*this); | 805 TextNode* result = new TextNode(*this); |
804 result->CalculateOffsets(); | 806 result->CalculateOffsets(); |
805 return result; | 807 return result; |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
843 return new AssertionNode(AT_BOUNDARY, on_success); | 845 return new AssertionNode(AT_BOUNDARY, on_success); |
844 } | 846 } |
845 static AssertionNode* AtNonBoundary(RegExpNode* on_success) { | 847 static AssertionNode* AtNonBoundary(RegExpNode* on_success) { |
846 return new AssertionNode(AT_NON_BOUNDARY, on_success); | 848 return new AssertionNode(AT_NON_BOUNDARY, on_success); |
847 } | 849 } |
848 static AssertionNode* AfterNewline(RegExpNode* on_success) { | 850 static AssertionNode* AfterNewline(RegExpNode* on_success) { |
849 return new AssertionNode(AFTER_NEWLINE, on_success); | 851 return new AssertionNode(AFTER_NEWLINE, on_success); |
850 } | 852 } |
851 virtual void Accept(NodeVisitor* visitor); | 853 virtual void Accept(NodeVisitor* visitor); |
852 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 854 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
853 virtual int EatsAtLeast(int recursion_depth); | 855 virtual int EatsAtLeast(int still_to_find, int recursion_depth); |
854 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 856 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
855 RegExpCompiler* compiler, | 857 RegExpCompiler* compiler, |
856 int filled_in) { | 858 int filled_in) { |
857 return on_success()->GetQuickCheckDetails(details, compiler, filled_in); | 859 return on_success()->GetQuickCheckDetails(details, compiler, filled_in); |
858 } | 860 } |
859 virtual AssertionNode* Clone() { return new AssertionNode(*this); } | 861 virtual AssertionNode* Clone() { return new AssertionNode(*this); } |
860 AssertionNodeType type() { return type_; } | 862 AssertionNodeType type() { return type_; } |
861 private: | 863 private: |
862 AssertionNode(AssertionNodeType t, RegExpNode* on_success) | 864 AssertionNode(AssertionNodeType t, RegExpNode* on_success) |
863 : SeqRegExpNode(on_success), type_(t) { } | 865 : SeqRegExpNode(on_success), type_(t) { } |
864 AssertionNodeType type_; | 866 AssertionNodeType type_; |
865 }; | 867 }; |
866 | 868 |
867 | 869 |
868 class BackReferenceNode: public SeqRegExpNode { | 870 class BackReferenceNode: public SeqRegExpNode { |
869 public: | 871 public: |
870 BackReferenceNode(int start_reg, | 872 BackReferenceNode(int start_reg, |
871 int end_reg, | 873 int end_reg, |
872 RegExpNode* on_success) | 874 RegExpNode* on_success) |
873 : SeqRegExpNode(on_success), | 875 : SeqRegExpNode(on_success), |
874 start_reg_(start_reg), | 876 start_reg_(start_reg), |
875 end_reg_(end_reg) { } | 877 end_reg_(end_reg) { } |
876 virtual void Accept(NodeVisitor* visitor); | 878 virtual void Accept(NodeVisitor* visitor); |
877 int start_register() { return start_reg_; } | 879 int start_register() { return start_reg_; } |
878 int end_register() { return end_reg_; } | 880 int end_register() { return end_reg_; } |
879 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 881 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
880 virtual int EatsAtLeast(int recursion_depth); | 882 virtual int EatsAtLeast(int still_to_find, int recursion_depth); |
881 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 883 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
882 RegExpCompiler* compiler, | 884 RegExpCompiler* compiler, |
883 int characters_filled_in) { | 885 int characters_filled_in) { |
884 return; | 886 return; |
885 } | 887 } |
886 virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); } | 888 virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); } |
887 | 889 |
888 private: | 890 private: |
889 int start_reg_; | 891 int start_reg_; |
890 int end_reg_; | 892 int end_reg_; |
891 }; | 893 }; |
892 | 894 |
893 | 895 |
894 class EndNode: public RegExpNode { | 896 class EndNode: public RegExpNode { |
895 public: | 897 public: |
896 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; | 898 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; |
897 explicit EndNode(Action action) : action_(action) { } | 899 explicit EndNode(Action action) : action_(action) { } |
898 virtual void Accept(NodeVisitor* visitor); | 900 virtual void Accept(NodeVisitor* visitor); |
899 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 901 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
900 virtual int EatsAtLeast(int recursion_depth) { return 0; } | 902 virtual int EatsAtLeast(int still_to_find, int recursion_depth) { return 0; } |
901 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 903 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
902 RegExpCompiler* compiler, | 904 RegExpCompiler* compiler, |
903 int characters_filled_in) { | 905 int characters_filled_in) { |
904 // Returning 0 from EatsAtLeast should ensure we never get here. | 906 // Returning 0 from EatsAtLeast should ensure we never get here. |
905 UNREACHABLE(); | 907 UNREACHABLE(); |
906 } | 908 } |
907 virtual EndNode* Clone() { return new EndNode(*this); } | 909 virtual EndNode* Clone() { return new EndNode(*this); } |
908 | 910 |
909 private: | 911 private: |
910 Action action_; | 912 Action action_; |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
964 public: | 966 public: |
965 explicit ChoiceNode(int expected_size) | 967 explicit ChoiceNode(int expected_size) |
966 : alternatives_(new ZoneList<GuardedAlternative>(expected_size)), | 968 : alternatives_(new ZoneList<GuardedAlternative>(expected_size)), |
967 table_(NULL), | 969 table_(NULL), |
968 being_calculated_(false) { } | 970 being_calculated_(false) { } |
969 virtual void Accept(NodeVisitor* visitor); | 971 virtual void Accept(NodeVisitor* visitor); |
970 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); } | 972 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); } |
971 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } | 973 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } |
972 DispatchTable* GetTable(bool ignore_case); | 974 DispatchTable* GetTable(bool ignore_case); |
973 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 975 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
974 virtual int EatsAtLeast(int recursion_depth); | 976 virtual int EatsAtLeast(int still_to_find, int recursion_depth); |
975 int EatsAtLeastHelper(int recursion_depth, RegExpNode* ignore_this_node); | 977 int EatsAtLeastHelper(int still_to_find, |
| 978 int recursion_depth, |
| 979 RegExpNode* ignore_this_node); |
976 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 980 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
977 RegExpCompiler* compiler, | 981 RegExpCompiler* compiler, |
978 int characters_filled_in); | 982 int characters_filled_in); |
979 virtual ChoiceNode* Clone() { return new ChoiceNode(*this); } | 983 virtual ChoiceNode* Clone() { return new ChoiceNode(*this); } |
980 | 984 |
981 bool being_calculated() { return being_calculated_; } | 985 bool being_calculated() { return being_calculated_; } |
982 void set_being_calculated(bool b) { being_calculated_ = b; } | 986 void set_being_calculated(bool b) { being_calculated_ = b; } |
983 virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; } | 987 virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; } |
984 | 988 |
985 protected: | 989 protected: |
(...skipping 19 matching lines...) Expand all Loading... |
1005 | 1009 |
1006 | 1010 |
1007 class NegativeLookaheadChoiceNode: public ChoiceNode { | 1011 class NegativeLookaheadChoiceNode: public ChoiceNode { |
1008 public: | 1012 public: |
1009 explicit NegativeLookaheadChoiceNode(GuardedAlternative this_must_fail, | 1013 explicit NegativeLookaheadChoiceNode(GuardedAlternative this_must_fail, |
1010 GuardedAlternative then_do_this) | 1014 GuardedAlternative then_do_this) |
1011 : ChoiceNode(2) { | 1015 : ChoiceNode(2) { |
1012 AddAlternative(this_must_fail); | 1016 AddAlternative(this_must_fail); |
1013 AddAlternative(then_do_this); | 1017 AddAlternative(then_do_this); |
1014 } | 1018 } |
1015 virtual int EatsAtLeast(int recursion_depth); | 1019 virtual int EatsAtLeast(int still_to_find, int recursion_depth); |
1016 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 1020 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
1017 RegExpCompiler* compiler, | 1021 RegExpCompiler* compiler, |
1018 int characters_filled_in); | 1022 int characters_filled_in); |
1019 // For a negative lookahead we don't emit the quick check for the | 1023 // For a negative lookahead we don't emit the quick check for the |
1020 // alternative that is expected to fail. This is because quick check code | 1024 // alternative that is expected to fail. This is because quick check code |
1021 // starts by loading enough characters for the alternative that takes fewest | 1025 // starts by loading enough characters for the alternative that takes fewest |
1022 // characters, but on a negative lookahead the negative branch did not take | 1026 // characters, but on a negative lookahead the negative branch did not take |
1023 // part in that calculation (EatsAtLeast) so the assumptions don't hold. | 1027 // part in that calculation (EatsAtLeast) so the assumptions don't hold. |
1024 virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; } | 1028 virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; } |
1025 }; | 1029 }; |
1026 | 1030 |
1027 | 1031 |
1028 class LoopChoiceNode: public ChoiceNode { | 1032 class LoopChoiceNode: public ChoiceNode { |
1029 public: | 1033 public: |
1030 explicit LoopChoiceNode(bool body_can_be_zero_length) | 1034 explicit LoopChoiceNode(bool body_can_be_zero_length) |
1031 : ChoiceNode(2), | 1035 : ChoiceNode(2), |
1032 loop_node_(NULL), | 1036 loop_node_(NULL), |
1033 continue_node_(NULL), | 1037 continue_node_(NULL), |
1034 body_can_be_zero_length_(body_can_be_zero_length) { } | 1038 body_can_be_zero_length_(body_can_be_zero_length) { } |
1035 void AddLoopAlternative(GuardedAlternative alt); | 1039 void AddLoopAlternative(GuardedAlternative alt); |
1036 void AddContinueAlternative(GuardedAlternative alt); | 1040 void AddContinueAlternative(GuardedAlternative alt); |
1037 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 1041 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
1038 virtual int EatsAtLeast(int recursion_depth); // Returns 0. | 1042 virtual int EatsAtLeast(int still_to_find, int recursion_depth); |
1039 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 1043 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
1040 RegExpCompiler* compiler, | 1044 RegExpCompiler* compiler, |
1041 int characters_filled_in); | 1045 int characters_filled_in); |
1042 virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); } | 1046 virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); } |
1043 RegExpNode* loop_node() { return loop_node_; } | 1047 RegExpNode* loop_node() { return loop_node_; } |
1044 RegExpNode* continue_node() { return continue_node_; } | 1048 RegExpNode* continue_node() { return continue_node_; } |
1045 bool body_can_be_zero_length() { return body_can_be_zero_length_; } | 1049 bool body_can_be_zero_length() { return body_can_be_zero_length_; } |
1046 virtual void Accept(NodeVisitor* visitor); | 1050 virtual void Accept(NodeVisitor* visitor); |
1047 | 1051 |
1048 private: | 1052 private: |
(...skipping 254 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1303 Handle<String> pattern, | 1307 Handle<String> pattern, |
1304 bool is_ascii); | 1308 bool is_ascii); |
1305 | 1309 |
1306 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case); | 1310 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case); |
1307 }; | 1311 }; |
1308 | 1312 |
1309 | 1313 |
1310 } } // namespace v8::internal | 1314 } } // namespace v8::internal |
1311 | 1315 |
1312 #endif // V8_JSREGEXP_H_ | 1316 #endif // V8_JSREGEXP_H_ |
OLD | NEW |