OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_REGEXP_JSREGEXP_H_ | 5 #ifndef V8_REGEXP_JSREGEXP_H_ |
6 #define V8_REGEXP_JSREGEXP_H_ | 6 #define V8_REGEXP_JSREGEXP_H_ |
7 | 7 |
8 #include "src/allocation.h" | 8 #include "src/allocation.h" |
9 #include "src/assembler.h" | 9 #include "src/assembler.h" |
10 | 10 |
(...skipping 369 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
380 | 380 |
381 #define FOR_EACH_NODE_TYPE(VISIT) \ | 381 #define FOR_EACH_NODE_TYPE(VISIT) \ |
382 VISIT(End) \ | 382 VISIT(End) \ |
383 VISIT(Action) \ | 383 VISIT(Action) \ |
384 VISIT(Choice) \ | 384 VISIT(Choice) \ |
385 VISIT(BackReference) \ | 385 VISIT(BackReference) \ |
386 VISIT(Assertion) \ | 386 VISIT(Assertion) \ |
387 VISIT(Text) | 387 VISIT(Text) |
388 | 388 |
389 | 389 |
390 #define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \ | 390 #define FOR_EACH_REG_EXP_TREE_TYPE(VISIT) \ |
391 VISIT(Disjunction) \ | 391 VISIT(Disjunction) \ |
392 VISIT(Alternative) \ | 392 VISIT(Alternative) \ |
393 VISIT(Assertion) \ | 393 VISIT(Assertion) \ |
394 VISIT(CharacterClass) \ | 394 VISIT(CharacterClass) \ |
395 VISIT(Atom) \ | 395 VISIT(Atom) \ |
396 VISIT(Quantifier) \ | 396 VISIT(Quantifier) \ |
397 VISIT(Capture) \ | 397 VISIT(Capture) \ |
398 VISIT(Lookahead) \ | 398 VISIT(Lookaround) \ |
399 VISIT(BackReference) \ | 399 VISIT(BackReference) \ |
400 VISIT(Empty) \ | 400 VISIT(Empty) \ |
401 VISIT(Text) | 401 VISIT(Text) |
402 | 402 |
403 | 403 |
404 #define FORWARD_DECLARE(Name) class RegExp##Name; | 404 #define FORWARD_DECLARE(Name) class RegExp##Name; |
405 FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE) | 405 FOR_EACH_REG_EXP_TREE_TYPE(FORWARD_DECLARE) |
406 #undef FORWARD_DECLARE | 406 #undef FORWARD_DECLARE |
407 | 407 |
408 | 408 |
409 class TextElement final BASE_EMBEDDED { | 409 class TextElement final BASE_EMBEDDED { |
410 public: | 410 public: |
(...skipping 409 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
820 ActionNode(ActionType action_type, RegExpNode* on_success) | 820 ActionNode(ActionType action_type, RegExpNode* on_success) |
821 : SeqRegExpNode(on_success), | 821 : SeqRegExpNode(on_success), |
822 action_type_(action_type) { } | 822 action_type_(action_type) { } |
823 ActionType action_type_; | 823 ActionType action_type_; |
824 friend class DotPrinter; | 824 friend class DotPrinter; |
825 }; | 825 }; |
826 | 826 |
827 | 827 |
828 class TextNode: public SeqRegExpNode { | 828 class TextNode: public SeqRegExpNode { |
829 public: | 829 public: |
830 TextNode(ZoneList<TextElement>* elms, | 830 TextNode(ZoneList<TextElement>* elms, bool read_backward, |
| 831 RegExpNode* on_success) |
| 832 : SeqRegExpNode(on_success), elms_(elms), read_backward_(read_backward) {} |
| 833 TextNode(RegExpCharacterClass* that, bool read_backward, |
831 RegExpNode* on_success) | 834 RegExpNode* on_success) |
832 : SeqRegExpNode(on_success), | 835 : SeqRegExpNode(on_success), |
833 elms_(elms) { } | 836 elms_(new (zone()) ZoneList<TextElement>(1, zone())), |
834 TextNode(RegExpCharacterClass* that, | 837 read_backward_(read_backward) { |
835 RegExpNode* on_success) | |
836 : SeqRegExpNode(on_success), | |
837 elms_(new(zone()) ZoneList<TextElement>(1, zone())) { | |
838 elms_->Add(TextElement::CharClass(that), zone()); | 838 elms_->Add(TextElement::CharClass(that), zone()); |
839 } | 839 } |
840 virtual void Accept(NodeVisitor* visitor); | 840 virtual void Accept(NodeVisitor* visitor); |
841 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 841 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
842 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); | 842 virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start); |
843 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 843 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
844 RegExpCompiler* compiler, | 844 RegExpCompiler* compiler, |
845 int characters_filled_in, | 845 int characters_filled_in, |
846 bool not_at_start); | 846 bool not_at_start); |
847 ZoneList<TextElement>* elements() { return elms_; } | 847 ZoneList<TextElement>* elements() { return elms_; } |
| 848 bool read_backward() { return read_backward_; } |
848 void MakeCaseIndependent(Isolate* isolate, bool is_one_byte); | 849 void MakeCaseIndependent(Isolate* isolate, bool is_one_byte); |
849 virtual int GreedyLoopTextLength(); | 850 virtual int GreedyLoopTextLength(); |
850 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( | 851 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( |
851 RegExpCompiler* compiler); | 852 RegExpCompiler* compiler); |
852 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | 853 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, |
853 BoyerMooreLookahead* bm, bool not_at_start); | 854 BoyerMooreLookahead* bm, bool not_at_start); |
854 void CalculateOffsets(); | 855 void CalculateOffsets(); |
855 virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); | 856 virtual RegExpNode* FilterOneByte(int depth, bool ignore_case); |
856 | 857 |
857 private: | 858 private: |
858 enum TextEmitPassType { | 859 enum TextEmitPassType { |
859 NON_LATIN1_MATCH, // Check for characters that can't match. | 860 NON_LATIN1_MATCH, // Check for characters that can't match. |
860 SIMPLE_CHARACTER_MATCH, // Case-dependent single character check. | 861 SIMPLE_CHARACTER_MATCH, // Case-dependent single character check. |
861 NON_LETTER_CHARACTER_MATCH, // Check characters that have no case equivs. | 862 NON_LETTER_CHARACTER_MATCH, // Check characters that have no case equivs. |
862 CASE_CHARACTER_MATCH, // Case-independent single character check. | 863 CASE_CHARACTER_MATCH, // Case-independent single character check. |
863 CHARACTER_CLASS_MATCH // Character class. | 864 CHARACTER_CLASS_MATCH // Character class. |
864 }; | 865 }; |
865 static bool SkipPass(int pass, bool ignore_case); | 866 static bool SkipPass(int pass, bool ignore_case); |
866 static const int kFirstRealPass = SIMPLE_CHARACTER_MATCH; | 867 static const int kFirstRealPass = SIMPLE_CHARACTER_MATCH; |
867 static const int kLastPass = CHARACTER_CLASS_MATCH; | 868 static const int kLastPass = CHARACTER_CLASS_MATCH; |
868 void TextEmitPass(RegExpCompiler* compiler, | 869 void TextEmitPass(RegExpCompiler* compiler, |
869 TextEmitPassType pass, | 870 TextEmitPassType pass, |
870 bool preloaded, | 871 bool preloaded, |
871 Trace* trace, | 872 Trace* trace, |
872 bool first_element_checked, | 873 bool first_element_checked, |
873 int* checked_up_to); | 874 int* checked_up_to); |
874 int Length(); | 875 int Length(); |
875 ZoneList<TextElement>* elms_; | 876 ZoneList<TextElement>* elms_; |
| 877 bool read_backward_; |
876 }; | 878 }; |
877 | 879 |
878 | 880 |
879 class AssertionNode: public SeqRegExpNode { | 881 class AssertionNode: public SeqRegExpNode { |
880 public: | 882 public: |
881 enum AssertionType { | 883 enum AssertionType { |
882 AT_END, | 884 AT_END, |
883 AT_START, | 885 AT_START, |
884 AT_BOUNDARY, | 886 AT_BOUNDARY, |
885 AT_NON_BOUNDARY, | 887 AT_NON_BOUNDARY, |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
918 Trace* trace, | 920 Trace* trace, |
919 IfPrevious backtrack_if_previous); | 921 IfPrevious backtrack_if_previous); |
920 AssertionNode(AssertionType t, RegExpNode* on_success) | 922 AssertionNode(AssertionType t, RegExpNode* on_success) |
921 : SeqRegExpNode(on_success), assertion_type_(t) { } | 923 : SeqRegExpNode(on_success), assertion_type_(t) { } |
922 AssertionType assertion_type_; | 924 AssertionType assertion_type_; |
923 }; | 925 }; |
924 | 926 |
925 | 927 |
926 class BackReferenceNode: public SeqRegExpNode { | 928 class BackReferenceNode: public SeqRegExpNode { |
927 public: | 929 public: |
928 BackReferenceNode(int start_reg, | 930 BackReferenceNode(int start_reg, int end_reg, bool read_backward, |
929 int end_reg, | |
930 RegExpNode* on_success) | 931 RegExpNode* on_success) |
931 : SeqRegExpNode(on_success), | 932 : SeqRegExpNode(on_success), |
932 start_reg_(start_reg), | 933 start_reg_(start_reg), |
933 end_reg_(end_reg) { } | 934 end_reg_(end_reg), |
| 935 read_backward_(read_backward) {} |
934 virtual void Accept(NodeVisitor* visitor); | 936 virtual void Accept(NodeVisitor* visitor); |
935 int start_register() { return start_reg_; } | 937 int start_register() { return start_reg_; } |
936 int end_register() { return end_reg_; } | 938 int end_register() { return end_reg_; } |
| 939 bool read_backward() { return read_backward_; } |
937 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 940 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
938 virtual int EatsAtLeast(int still_to_find, | 941 virtual int EatsAtLeast(int still_to_find, |
939 int recursion_depth, | 942 int recursion_depth, |
940 bool not_at_start); | 943 bool not_at_start); |
941 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 944 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
942 RegExpCompiler* compiler, | 945 RegExpCompiler* compiler, |
943 int characters_filled_in, | 946 int characters_filled_in, |
944 bool not_at_start) { | 947 bool not_at_start) { |
945 return; | 948 return; |
946 } | 949 } |
947 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, | 950 virtual void FillInBMInfo(Isolate* isolate, int offset, int budget, |
948 BoyerMooreLookahead* bm, bool not_at_start); | 951 BoyerMooreLookahead* bm, bool not_at_start); |
949 | 952 |
950 private: | 953 private: |
951 int start_reg_; | 954 int start_reg_; |
952 int end_reg_; | 955 int end_reg_; |
| 956 bool read_backward_; |
953 }; | 957 }; |
954 | 958 |
955 | 959 |
956 class EndNode: public RegExpNode { | 960 class EndNode: public RegExpNode { |
957 public: | 961 public: |
958 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; | 962 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; |
959 explicit EndNode(Action action, Zone* zone) | 963 explicit EndNode(Action action, Zone* zone) |
960 : RegExpNode(zone), action_(action) { } | 964 : RegExpNode(zone), action_(action) { } |
961 virtual void Accept(NodeVisitor* visitor); | 965 virtual void Accept(NodeVisitor* visitor); |
962 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 966 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
(...skipping 468 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1431 bool is_trivial() { | 1435 bool is_trivial() { |
1432 return backtrack_ == NULL && | 1436 return backtrack_ == NULL && |
1433 actions_ == NULL && | 1437 actions_ == NULL && |
1434 cp_offset_ == 0 && | 1438 cp_offset_ == 0 && |
1435 characters_preloaded_ == 0 && | 1439 characters_preloaded_ == 0 && |
1436 bound_checked_up_to_ == 0 && | 1440 bound_checked_up_to_ == 0 && |
1437 quick_check_performed_.characters() == 0 && | 1441 quick_check_performed_.characters() == 0 && |
1438 at_start_ == UNKNOWN; | 1442 at_start_ == UNKNOWN; |
1439 } | 1443 } |
1440 TriBool at_start() { return at_start_; } | 1444 TriBool at_start() { return at_start_; } |
1441 void set_at_start(bool at_start) { | 1445 void set_at_start(TriBool at_start) { at_start_ = at_start; } |
1442 at_start_ = at_start ? TRUE_VALUE : FALSE_VALUE; | |
1443 } | |
1444 Label* backtrack() { return backtrack_; } | 1446 Label* backtrack() { return backtrack_; } |
1445 Label* loop_label() { return loop_label_; } | 1447 Label* loop_label() { return loop_label_; } |
1446 RegExpNode* stop_node() { return stop_node_; } | 1448 RegExpNode* stop_node() { return stop_node_; } |
1447 int characters_preloaded() { return characters_preloaded_; } | 1449 int characters_preloaded() { return characters_preloaded_; } |
1448 int bound_checked_up_to() { return bound_checked_up_to_; } | 1450 int bound_checked_up_to() { return bound_checked_up_to_; } |
1449 int flush_budget() { return flush_budget_; } | 1451 int flush_budget() { return flush_budget_; } |
1450 QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; } | 1452 QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; } |
1451 bool mentions_reg(int reg); | 1453 bool mentions_reg(int reg); |
1452 // Returns true if a deferred position store exists to the specified | 1454 // Returns true if a deferred position store exists to the specified |
1453 // register and stores the offset in the out-parameter. Otherwise | 1455 // register and stores the offset in the out-parameter. Otherwise |
(...skipping 226 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1680 static const int kStringOffset = 0; | 1682 static const int kStringOffset = 0; |
1681 static const int kPatternOffset = 1; | 1683 static const int kPatternOffset = 1; |
1682 static const int kArrayOffset = 2; | 1684 static const int kArrayOffset = 2; |
1683 static const int kLastMatchOffset = 3; | 1685 static const int kLastMatchOffset = 3; |
1684 }; | 1686 }; |
1685 | 1687 |
1686 } // namespace internal | 1688 } // namespace internal |
1687 } // namespace v8 | 1689 } // namespace v8 |
1688 | 1690 |
1689 #endif // V8_REGEXP_JSREGEXP_H_ | 1691 #endif // V8_REGEXP_JSREGEXP_H_ |
OLD | NEW |