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 392 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
403 ZoneSplayTree<Config>* tree() { return &tree_; } | 403 ZoneSplayTree<Config>* tree() { return &tree_; } |
404 ZoneSplayTree<Config> tree_; | 404 ZoneSplayTree<Config> tree_; |
405 }; | 405 }; |
406 | 406 |
407 | 407 |
408 #define FOR_EACH_NODE_TYPE(VISIT) \ | 408 #define FOR_EACH_NODE_TYPE(VISIT) \ |
409 VISIT(End) \ | 409 VISIT(End) \ |
410 VISIT(Action) \ | 410 VISIT(Action) \ |
411 VISIT(Choice) \ | 411 VISIT(Choice) \ |
412 VISIT(BackReference) \ | 412 VISIT(BackReference) \ |
| 413 VISIT(Assertion) \ |
413 VISIT(Text) | 414 VISIT(Text) |
414 | 415 |
415 | 416 |
416 #define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \ | 417 #define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \ |
417 VISIT(Disjunction) \ | 418 VISIT(Disjunction) \ |
418 VISIT(Alternative) \ | 419 VISIT(Alternative) \ |
419 VISIT(Assertion) \ | 420 VISIT(Assertion) \ |
420 VISIT(CharacterClass) \ | 421 VISIT(CharacterClass) \ |
421 VISIT(Atom) \ | 422 VISIT(Atom) \ |
422 VISIT(Quantifier) \ | 423 VISIT(Quantifier) \ |
(...skipping 189 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
612 static const int kNodeIsTooComplexForGreedyLoops = -1; | 613 static const int kNodeIsTooComplexForGreedyLoops = -1; |
613 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } | 614 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } |
614 Label* label() { return &label_; } | 615 Label* label() { return &label_; } |
615 // If non-generic code is generated for a node (ie the node is not at the | 616 // If non-generic code is generated for a node (ie the node is not at the |
616 // start of the trace) then it cannot be reused. This variable sets a limit | 617 // start of the trace) then it cannot be reused. This variable sets a limit |
617 // on how often we allow that to happen before we insist on starting a new | 618 // on how often we allow that to happen before we insist on starting a new |
618 // trace and generating generic code for a node that can be reused by flushing | 619 // trace and generating generic code for a node that can be reused by flushing |
619 // the deferred actions in the current trace and generating a goto. | 620 // the deferred actions in the current trace and generating a goto. |
620 static const int kMaxCopiesCodeGenerated = 10; | 621 static const int kMaxCopiesCodeGenerated = 10; |
621 | 622 |
622 // Propagates the given interest information forward. When seeing | |
623 // \bfoo for instance, the \b is implemented by propagating forward | |
624 // to the 'foo' string that it should only succeed if its first | |
625 // character is a letter xor the previous character was a letter. | |
626 virtual RegExpNode* PropagateForward(NodeInfo* info) = 0; | |
627 | |
628 NodeInfo* info() { return &info_; } | 623 NodeInfo* info() { return &info_; } |
629 | 624 |
630 void AddSibling(RegExpNode* node) { siblings_.Add(node); } | 625 void AddSibling(RegExpNode* node) { siblings_.Add(node); } |
631 | 626 |
632 // Static version of EnsureSibling that expresses the fact that the | 627 // Static version of EnsureSibling that expresses the fact that the |
633 // result has the same type as the input. | 628 // result has the same type as the input. |
634 template <class C> | 629 template <class C> |
635 static C* EnsureSibling(C* node, NodeInfo* info, bool* cloned) { | 630 static C* EnsureSibling(C* node, NodeInfo* info, bool* cloned) { |
636 return static_cast<C*>(node->EnsureSibling(info, cloned)); | 631 return static_cast<C*>(node->EnsureSibling(info, cloned)); |
637 } | 632 } |
(...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
737 int repetition_limit, | 732 int repetition_limit, |
738 RegExpNode* on_success); | 733 RegExpNode* on_success); |
739 virtual void Accept(NodeVisitor* visitor); | 734 virtual void Accept(NodeVisitor* visitor); |
740 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 735 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
741 virtual int EatsAtLeast(int recursion_depth); | 736 virtual int EatsAtLeast(int recursion_depth); |
742 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 737 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
743 RegExpCompiler* compiler, | 738 RegExpCompiler* compiler, |
744 int filled_in) { | 739 int filled_in) { |
745 return on_success()->GetQuickCheckDetails(details, compiler, filled_in); | 740 return on_success()->GetQuickCheckDetails(details, compiler, filled_in); |
746 } | 741 } |
747 virtual RegExpNode* PropagateForward(NodeInfo* info); | |
748 Type type() { return type_; } | 742 Type type() { return type_; } |
749 // TODO(erikcorry): We should allow some action nodes in greedy loops. | 743 // TODO(erikcorry): We should allow some action nodes in greedy loops. |
750 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } | 744 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } |
751 virtual ActionNode* Clone() { return new ActionNode(*this); } | 745 virtual ActionNode* Clone() { return new ActionNode(*this); } |
752 | 746 |
753 private: | 747 private: |
754 union { | 748 union { |
755 struct { | 749 struct { |
756 int reg; | 750 int reg; |
757 int value; | 751 int value; |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
790 RegExpNode* on_success) | 784 RegExpNode* on_success) |
791 : SeqRegExpNode(on_success), | 785 : SeqRegExpNode(on_success), |
792 elms_(elms) { } | 786 elms_(elms) { } |
793 TextNode(RegExpCharacterClass* that, | 787 TextNode(RegExpCharacterClass* that, |
794 RegExpNode* on_success) | 788 RegExpNode* on_success) |
795 : SeqRegExpNode(on_success), | 789 : SeqRegExpNode(on_success), |
796 elms_(new ZoneList<TextElement>(1)) { | 790 elms_(new ZoneList<TextElement>(1)) { |
797 elms_->Add(TextElement::CharClass(that)); | 791 elms_->Add(TextElement::CharClass(that)); |
798 } | 792 } |
799 virtual void Accept(NodeVisitor* visitor); | 793 virtual void Accept(NodeVisitor* visitor); |
800 virtual RegExpNode* PropagateForward(NodeInfo* info); | |
801 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 794 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
802 virtual int EatsAtLeast(int recursion_depth); | 795 virtual int EatsAtLeast(int recursion_depth); |
803 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 796 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
804 RegExpCompiler* compiler, | 797 RegExpCompiler* compiler, |
805 int characters_filled_in); | 798 int characters_filled_in); |
806 ZoneList<TextElement>* elements() { return elms_; } | 799 ZoneList<TextElement>* elements() { return elms_; } |
807 void MakeCaseIndependent(); | 800 void MakeCaseIndependent(); |
808 virtual int GreedyLoopTextLength(); | 801 virtual int GreedyLoopTextLength(); |
809 virtual TextNode* Clone() { | 802 virtual TextNode* Clone() { |
810 TextNode* result = new TextNode(*this); | 803 TextNode* result = new TextNode(*this); |
(...skipping 13 matching lines...) Expand all Loading... |
824 TextEmitPassType pass, | 817 TextEmitPassType pass, |
825 bool preloaded, | 818 bool preloaded, |
826 Trace* trace, | 819 Trace* trace, |
827 bool first_element_checked, | 820 bool first_element_checked, |
828 int* checked_up_to); | 821 int* checked_up_to); |
829 int Length(); | 822 int Length(); |
830 ZoneList<TextElement>* elms_; | 823 ZoneList<TextElement>* elms_; |
831 }; | 824 }; |
832 | 825 |
833 | 826 |
| 827 class AssertionNode: public SeqRegExpNode { |
| 828 public: |
| 829 enum AssertionNodeType { |
| 830 AT_END, |
| 831 AT_START, |
| 832 AT_BOUNDARY, |
| 833 AT_NON_BOUNDARY, |
| 834 AFTER_NEWLINE |
| 835 }; |
| 836 static AssertionNode* AtEnd(RegExpNode* on_success) { |
| 837 return new AssertionNode(AT_END, on_success); |
| 838 } |
| 839 static AssertionNode* AtStart(RegExpNode* on_success) { |
| 840 return new AssertionNode(AT_START, on_success); |
| 841 } |
| 842 static AssertionNode* AtBoundary(RegExpNode* on_success) { |
| 843 return new AssertionNode(AT_BOUNDARY, on_success); |
| 844 } |
| 845 static AssertionNode* AtNonBoundary(RegExpNode* on_success) { |
| 846 return new AssertionNode(AT_NON_BOUNDARY, on_success); |
| 847 } |
| 848 static AssertionNode* AfterNewline(RegExpNode* on_success) { |
| 849 return new AssertionNode(AFTER_NEWLINE, on_success); |
| 850 } |
| 851 virtual void Accept(NodeVisitor* visitor); |
| 852 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
| 853 virtual int EatsAtLeast(int recursion_depth); |
| 854 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
| 855 RegExpCompiler* compiler, |
| 856 int filled_in) { |
| 857 return on_success()->GetQuickCheckDetails(details, compiler, filled_in); |
| 858 } |
| 859 virtual AssertionNode* Clone() { return new AssertionNode(*this); } |
| 860 AssertionNodeType type() { return type_; } |
| 861 private: |
| 862 AssertionNode(AssertionNodeType t, RegExpNode* on_success) |
| 863 : SeqRegExpNode(on_success), type_(t) { } |
| 864 AssertionNodeType type_; |
| 865 }; |
| 866 |
| 867 |
834 class BackReferenceNode: public SeqRegExpNode { | 868 class BackReferenceNode: public SeqRegExpNode { |
835 public: | 869 public: |
836 BackReferenceNode(int start_reg, | 870 BackReferenceNode(int start_reg, |
837 int end_reg, | 871 int end_reg, |
838 RegExpNode* on_success) | 872 RegExpNode* on_success) |
839 : SeqRegExpNode(on_success), | 873 : SeqRegExpNode(on_success), |
840 start_reg_(start_reg), | 874 start_reg_(start_reg), |
841 end_reg_(end_reg) { } | 875 end_reg_(end_reg) { } |
842 virtual void Accept(NodeVisitor* visitor); | 876 virtual void Accept(NodeVisitor* visitor); |
843 int start_register() { return start_reg_; } | 877 int start_register() { return start_reg_; } |
844 int end_register() { return end_reg_; } | 878 int end_register() { return end_reg_; } |
845 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 879 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
846 virtual int EatsAtLeast(int recursion_depth) { return 0; } | 880 virtual int EatsAtLeast(int recursion_depth); |
847 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 881 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
848 RegExpCompiler* compiler, | 882 RegExpCompiler* compiler, |
849 int characters_filled_in) { | 883 int characters_filled_in) { |
850 return; | 884 return; |
851 } | 885 } |
852 virtual RegExpNode* PropagateForward(NodeInfo* info); | |
853 virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); } | 886 virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); } |
854 | 887 |
855 private: | 888 private: |
856 int start_reg_; | 889 int start_reg_; |
857 int end_reg_; | 890 int end_reg_; |
858 }; | 891 }; |
859 | 892 |
860 | 893 |
861 class EndNode: public RegExpNode { | 894 class EndNode: public RegExpNode { |
862 public: | 895 public: |
863 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; | 896 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; |
864 explicit EndNode(Action action) : action_(action) { } | 897 explicit EndNode(Action action) : action_(action) { } |
865 virtual void Accept(NodeVisitor* visitor); | 898 virtual void Accept(NodeVisitor* visitor); |
866 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 899 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
867 virtual int EatsAtLeast(int recursion_depth) { return 0; } | 900 virtual int EatsAtLeast(int recursion_depth) { return 0; } |
868 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 901 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
869 RegExpCompiler* compiler, | 902 RegExpCompiler* compiler, |
870 int characters_filled_in) { | 903 int characters_filled_in) { |
871 // Returning 0 from EatsAtLeast should ensure we never get here. | 904 // Returning 0 from EatsAtLeast should ensure we never get here. |
872 UNREACHABLE(); | 905 UNREACHABLE(); |
873 } | 906 } |
874 virtual RegExpNode* PropagateForward(NodeInfo* info); | |
875 virtual EndNode* Clone() { return new EndNode(*this); } | 907 virtual EndNode* Clone() { return new EndNode(*this); } |
876 | 908 |
877 protected: | |
878 void EmitInfoChecks(RegExpMacroAssembler* macro, Trace* trace); | |
879 | |
880 private: | 909 private: |
881 Action action_; | 910 Action action_; |
882 }; | 911 }; |
883 | 912 |
884 | 913 |
885 class NegativeSubmatchSuccess: public EndNode { | 914 class NegativeSubmatchSuccess: public EndNode { |
886 public: | 915 public: |
887 NegativeSubmatchSuccess(int stack_pointer_reg, int position_reg) | 916 NegativeSubmatchSuccess(int stack_pointer_reg, int position_reg) |
888 : EndNode(NEGATIVE_SUBMATCH_SUCCESS), | 917 : EndNode(NEGATIVE_SUBMATCH_SUCCESS), |
889 stack_pointer_register_(stack_pointer_reg), | 918 stack_pointer_register_(stack_pointer_reg), |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
940 virtual void Accept(NodeVisitor* visitor); | 969 virtual void Accept(NodeVisitor* visitor); |
941 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); } | 970 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); } |
942 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } | 971 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } |
943 DispatchTable* GetTable(bool ignore_case); | 972 DispatchTable* GetTable(bool ignore_case); |
944 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); | 973 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
945 virtual int EatsAtLeast(int recursion_depth); | 974 virtual int EatsAtLeast(int recursion_depth); |
946 int EatsAtLeastHelper(int recursion_depth, RegExpNode* ignore_this_node); | 975 int EatsAtLeastHelper(int recursion_depth, RegExpNode* ignore_this_node); |
947 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 976 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
948 RegExpCompiler* compiler, | 977 RegExpCompiler* compiler, |
949 int characters_filled_in); | 978 int characters_filled_in); |
950 virtual RegExpNode* PropagateForward(NodeInfo* info); | |
951 virtual ChoiceNode* Clone() { return new ChoiceNode(*this); } | 979 virtual ChoiceNode* Clone() { return new ChoiceNode(*this); } |
952 | 980 |
953 bool being_calculated() { return being_calculated_; } | 981 bool being_calculated() { return being_calculated_; } |
954 void set_being_calculated(bool b) { being_calculated_ = b; } | 982 void set_being_calculated(bool b) { being_calculated_ = b; } |
955 | 983 |
956 protected: | 984 protected: |
957 int GreedyLoopTextLength(GuardedAlternative *alternative); | 985 int GreedyLoopTextLength(GuardedAlternative *alternative); |
958 ZoneList<GuardedAlternative>* alternatives_; | 986 ZoneList<GuardedAlternative>* alternatives_; |
959 | 987 |
960 private: | 988 private: |
(...skipping 293 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1254 Handle<String> pattern, | 1282 Handle<String> pattern, |
1255 bool is_ascii); | 1283 bool is_ascii); |
1256 | 1284 |
1257 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case); | 1285 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case); |
1258 }; | 1286 }; |
1259 | 1287 |
1260 | 1288 |
1261 } } // namespace v8::internal | 1289 } } // namespace v8::internal |
1262 | 1290 |
1263 #endif // V8_JSREGEXP_H_ | 1291 #endif // V8_JSREGEXP_H_ |
OLD | NEW |