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 207 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
218 // Represents the location of one element relative to the intersection of | 218 // Represents the location of one element relative to the intersection of |
219 // two sets. Corresponds to the four areas of a Venn diagram. | 219 // two sets. Corresponds to the four areas of a Venn diagram. |
220 enum ElementInSetsRelation { | 220 enum ElementInSetsRelation { |
221 kInsideNone = 0, | 221 kInsideNone = 0, |
222 kInsideFirst = 1, | 222 kInsideFirst = 1, |
223 kInsideSecond = 2, | 223 kInsideSecond = 2, |
224 kInsideBoth = 3 | 224 kInsideBoth = 3 |
225 }; | 225 }; |
226 | 226 |
227 | 227 |
| 228 // Represents code units in the range from from_ to to_, both ends are |
| 229 // inclusive. |
228 class CharacterRange { | 230 class CharacterRange { |
229 public: | 231 public: |
230 CharacterRange() : from_(0), to_(0) { } | 232 CharacterRange() : from_(0), to_(0) { } |
231 // For compatibility with the CHECK_OK macro | 233 // For compatibility with the CHECK_OK macro |
232 CharacterRange(void* null) { ASSERT_EQ(NULL, null); } //NOLINT | 234 CharacterRange(void* null) { ASSERT_EQ(NULL, null); } //NOLINT |
233 CharacterRange(uc16 from, uc16 to) : from_(from), to_(to) { } | 235 CharacterRange(uc16 from, uc16 to) : from_(from), to_(to) { } |
234 static void AddClassEscape(uc16 type, ZoneList<CharacterRange>* ranges); | 236 static void AddClassEscape(uc16 type, ZoneList<CharacterRange>* ranges); |
235 static Vector<const int> GetWordBounds(); | 237 static Vector<const int> GetWordBounds(); |
236 static inline CharacterRange Singleton(uc16 value) { | 238 static inline CharacterRange Singleton(uc16 value) { |
237 return CharacterRange(value, value); | 239 return CharacterRange(value, value); |
(...skipping 169 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
407 | 409 |
408 | 410 |
409 struct NodeInfo { | 411 struct NodeInfo { |
410 NodeInfo() | 412 NodeInfo() |
411 : being_analyzed(false), | 413 : being_analyzed(false), |
412 been_analyzed(false), | 414 been_analyzed(false), |
413 follows_word_interest(false), | 415 follows_word_interest(false), |
414 follows_newline_interest(false), | 416 follows_newline_interest(false), |
415 follows_start_interest(false), | 417 follows_start_interest(false), |
416 at_end(false), | 418 at_end(false), |
417 visited(false) { } | 419 visited(false), |
| 420 replacement_calculated(false) { } |
418 | 421 |
419 // Returns true if the interests and assumptions of this node | 422 // Returns true if the interests and assumptions of this node |
420 // matches the given one. | 423 // matches the given one. |
421 bool Matches(NodeInfo* that) { | 424 bool Matches(NodeInfo* that) { |
422 return (at_end == that->at_end) && | 425 return (at_end == that->at_end) && |
423 (follows_word_interest == that->follows_word_interest) && | 426 (follows_word_interest == that->follows_word_interest) && |
424 (follows_newline_interest == that->follows_newline_interest) && | 427 (follows_newline_interest == that->follows_newline_interest) && |
425 (follows_start_interest == that->follows_start_interest); | 428 (follows_start_interest == that->follows_start_interest); |
426 } | 429 } |
427 | 430 |
(...skipping 29 matching lines...) Expand all Loading... |
457 bool been_analyzed: 1; | 460 bool been_analyzed: 1; |
458 | 461 |
459 // These bits are set of this node has to know what the preceding | 462 // These bits are set of this node has to know what the preceding |
460 // character was. | 463 // character was. |
461 bool follows_word_interest: 1; | 464 bool follows_word_interest: 1; |
462 bool follows_newline_interest: 1; | 465 bool follows_newline_interest: 1; |
463 bool follows_start_interest: 1; | 466 bool follows_start_interest: 1; |
464 | 467 |
465 bool at_end: 1; | 468 bool at_end: 1; |
466 bool visited: 1; | 469 bool visited: 1; |
| 470 bool replacement_calculated: 1; |
467 }; | 471 }; |
468 | 472 |
469 | 473 |
470 // Details of a quick mask-compare check that can look ahead in the | 474 // Details of a quick mask-compare check that can look ahead in the |
471 // input stream. | 475 // input stream. |
472 class QuickCheckDetails { | 476 class QuickCheckDetails { |
473 public: | 477 public: |
474 QuickCheckDetails() | 478 QuickCheckDetails() |
475 : characters_(0), | 479 : characters_(0), |
476 mask_(0), | 480 mask_(0), |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
512 Position positions_[4]; | 516 Position positions_[4]; |
513 // These values are the condensate of the above array after Rationalize(). | 517 // These values are the condensate of the above array after Rationalize(). |
514 uint32_t mask_; | 518 uint32_t mask_; |
515 uint32_t value_; | 519 uint32_t value_; |
516 // If set to true, there is no way this quick check can match at all. | 520 // If set to true, there is no way this quick check can match at all. |
517 // E.g., if it requires to be at the start of the input, and isn't. | 521 // E.g., if it requires to be at the start of the input, and isn't. |
518 bool cannot_match_; | 522 bool cannot_match_; |
519 }; | 523 }; |
520 | 524 |
521 | 525 |
| 526 extern int kUninitializedRegExpNodePlaceHolder; |
| 527 |
| 528 |
522 class RegExpNode: public ZoneObject { | 529 class RegExpNode: public ZoneObject { |
523 public: | 530 public: |
524 RegExpNode() : trace_count_(0) { | 531 RegExpNode() : replacement_(NULL), trace_count_(0) { |
525 bm_info_[0] = bm_info_[1] = NULL; | 532 bm_info_[0] = bm_info_[1] = NULL; |
526 } | 533 } |
527 virtual ~RegExpNode(); | 534 virtual ~RegExpNode(); |
528 virtual void Accept(NodeVisitor* visitor) = 0; | 535 virtual void Accept(NodeVisitor* visitor) = 0; |
529 // Generates a goto to this node or actually generates the code at this point. | 536 // Generates a goto to this node or actually generates the code at this point. |
530 virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0; | 537 virtual void Emit(RegExpCompiler* compiler, Trace* trace) = 0; |
531 // How many characters must this node consume at a minimum in order to | 538 // How many characters must this node consume at a minimum in order to |
532 // succeed. If we have found at least 'still_to_find' characters that | 539 // succeed. If we have found at least 'still_to_find' characters that |
533 // must be consumed there is no need to ask any following nodes whether | 540 // must be consumed there is no need to ask any following nodes whether |
534 // they are sure to eat any more characters. The not_at_start argument is | 541 // they are sure to eat any more characters. The not_at_start argument is |
(...skipping 30 matching lines...) Expand all Loading... |
565 } | 572 } |
566 | 573 |
567 // Collects information on the possible code units (mod 128) that can match if | 574 // Collects information on the possible code units (mod 128) that can match if |
568 // we look forward. This is used for a Boyer-Moore-like string searching | 575 // we look forward. This is used for a Boyer-Moore-like string searching |
569 // implementation. TODO(erikcorry): This should share more code with | 576 // implementation. TODO(erikcorry): This should share more code with |
570 // EatsAtLeast, GetQuickCheckDetails. | 577 // EatsAtLeast, GetQuickCheckDetails. |
571 virtual void FillInBMInfo( | 578 virtual void FillInBMInfo( |
572 int offset, BoyerMooreLookahead* bm, bool not_at_start) { | 579 int offset, BoyerMooreLookahead* bm, bool not_at_start) { |
573 UNREACHABLE(); | 580 UNREACHABLE(); |
574 } | 581 } |
| 582 |
| 583 // If we know that the input is ASCII then there are some nodes that can |
| 584 // never match. This method returns a node that can be substituted for |
| 585 // itself, or NULL if the node can never match. |
| 586 virtual RegExpNode* FilterASCII(int depth) { return this; } |
| 587 // Helper for FilterASCII. |
| 588 RegExpNode* replacement() { |
| 589 ASSERT(info()->replacement_calculated); |
| 590 return replacement_; |
| 591 } |
| 592 RegExpNode* set_replacement(RegExpNode* replacement) { |
| 593 info()->replacement_calculated = true; |
| 594 replacement_ = replacement; |
| 595 return replacement; // For convenience. |
| 596 } |
| 597 |
575 // We want to avoid recalculating the lookahead info, so we store it on the | 598 // We want to avoid recalculating the lookahead info, so we store it on the |
576 // node. Only info that is for this node is stored. We can tell that the | 599 // node. Only info that is for this node is stored. We can tell that the |
577 // info is for this node when offset == 0, so the information is calculated | 600 // info is for this node when offset == 0, so the information is calculated |
578 // relative to this node. | 601 // relative to this node. |
579 void SaveBMInfo(BoyerMooreLookahead* bm, bool not_at_start, int offset) { | 602 void SaveBMInfo(BoyerMooreLookahead* bm, bool not_at_start, int offset) { |
580 if (offset == 0) set_bm_info(not_at_start, bm); | 603 if (offset == 0) set_bm_info(not_at_start, bm); |
581 } | 604 } |
582 | 605 |
583 Label* label() { return &label_; } | 606 Label* label() { return &label_; } |
584 // If non-generic code is generated for a node (i.e. the node is not at the | 607 // If non-generic code is generated for a node (i.e. the node is not at the |
585 // start of the trace) then it cannot be reused. This variable sets a limit | 608 // start of the trace) then it cannot be reused. This variable sets a limit |
586 // on how often we allow that to happen before we insist on starting a new | 609 // on how often we allow that to happen before we insist on starting a new |
587 // trace and generating generic code for a node that can be reused by flushing | 610 // trace and generating generic code for a node that can be reused by flushing |
588 // the deferred actions in the current trace and generating a goto. | 611 // the deferred actions in the current trace and generating a goto. |
589 static const int kMaxCopiesCodeGenerated = 10; | 612 static const int kMaxCopiesCodeGenerated = 10; |
590 | 613 |
591 NodeInfo* info() { return &info_; } | 614 NodeInfo* info() { return &info_; } |
592 | 615 |
593 BoyerMooreLookahead* bm_info(bool not_at_start) { | 616 BoyerMooreLookahead* bm_info(bool not_at_start) { |
594 return bm_info_[not_at_start ? 1 : 0]; | 617 return bm_info_[not_at_start ? 1 : 0]; |
595 } | 618 } |
596 | 619 |
597 protected: | 620 protected: |
598 enum LimitResult { DONE, CONTINUE }; | 621 enum LimitResult { DONE, CONTINUE }; |
| 622 RegExpNode* replacement_; |
599 | 623 |
600 LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace); | 624 LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace); |
601 | 625 |
602 // Returns a clone of this node initialized using the copy constructor | |
603 // of its concrete class. Note that the node may have to be pre- | |
604 // processed before it is on a usable state. | |
605 virtual RegExpNode* Clone() = 0; | |
606 | |
607 void set_bm_info(bool not_at_start, BoyerMooreLookahead* bm) { | 626 void set_bm_info(bool not_at_start, BoyerMooreLookahead* bm) { |
608 bm_info_[not_at_start ? 1 : 0] = bm; | 627 bm_info_[not_at_start ? 1 : 0] = bm; |
609 } | 628 } |
610 | 629 |
611 private: | 630 private: |
612 static const int kFirstCharBudget = 10; | 631 static const int kFirstCharBudget = 10; |
613 Label label_; | 632 Label label_; |
614 NodeInfo info_; | 633 NodeInfo info_; |
615 // This variable keeps track of how many times code has been generated for | 634 // This variable keeps track of how many times code has been generated for |
616 // this node (in different traces). We don't keep track of where the | 635 // this node (in different traces). We don't keep track of where the |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
648 int to_; | 667 int to_; |
649 }; | 668 }; |
650 | 669 |
651 | 670 |
652 class SeqRegExpNode: public RegExpNode { | 671 class SeqRegExpNode: public RegExpNode { |
653 public: | 672 public: |
654 explicit SeqRegExpNode(RegExpNode* on_success) | 673 explicit SeqRegExpNode(RegExpNode* on_success) |
655 : on_success_(on_success) { } | 674 : on_success_(on_success) { } |
656 RegExpNode* on_success() { return on_success_; } | 675 RegExpNode* on_success() { return on_success_; } |
657 void set_on_success(RegExpNode* node) { on_success_ = node; } | 676 void set_on_success(RegExpNode* node) { on_success_ = node; } |
| 677 virtual RegExpNode* FilterASCII(int depth); |
658 virtual void FillInBMInfo( | 678 virtual void FillInBMInfo( |
659 int offset, BoyerMooreLookahead* bm, bool not_at_start) { | 679 int offset, BoyerMooreLookahead* bm, bool not_at_start) { |
660 on_success_->FillInBMInfo(offset, bm, not_at_start); | 680 on_success_->FillInBMInfo(offset, bm, not_at_start); |
661 if (offset == 0) set_bm_info(not_at_start, bm); | 681 if (offset == 0) set_bm_info(not_at_start, bm); |
662 } | 682 } |
| 683 |
| 684 protected: |
| 685 RegExpNode* FilterSuccessor(int depth); |
| 686 |
663 private: | 687 private: |
664 RegExpNode* on_success_; | 688 RegExpNode* on_success_; |
665 }; | 689 }; |
666 | 690 |
667 | 691 |
668 class ActionNode: public SeqRegExpNode { | 692 class ActionNode: public SeqRegExpNode { |
669 public: | 693 public: |
670 enum Type { | 694 enum Type { |
671 SET_REGISTER, | 695 SET_REGISTER, |
672 INCREMENT_REGISTER, | 696 INCREMENT_REGISTER, |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
704 int filled_in, | 728 int filled_in, |
705 bool not_at_start) { | 729 bool not_at_start) { |
706 return on_success()->GetQuickCheckDetails( | 730 return on_success()->GetQuickCheckDetails( |
707 details, compiler, filled_in, not_at_start); | 731 details, compiler, filled_in, not_at_start); |
708 } | 732 } |
709 virtual void FillInBMInfo( | 733 virtual void FillInBMInfo( |
710 int offset, BoyerMooreLookahead* bm, bool not_at_start); | 734 int offset, BoyerMooreLookahead* bm, bool not_at_start); |
711 Type type() { return type_; } | 735 Type type() { return type_; } |
712 // TODO(erikcorry): We should allow some action nodes in greedy loops. | 736 // TODO(erikcorry): We should allow some action nodes in greedy loops. |
713 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } | 737 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } |
714 virtual ActionNode* Clone() { return new ActionNode(*this); } | |
715 | 738 |
716 private: | 739 private: |
717 union { | 740 union { |
718 struct { | 741 struct { |
719 int reg; | 742 int reg; |
720 int value; | 743 int value; |
721 } u_store_register; | 744 } u_store_register; |
722 struct { | 745 struct { |
723 int reg; | 746 int reg; |
724 } u_increment_register; | 747 } u_increment_register; |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
771 RegExpCompiler* compiler, | 794 RegExpCompiler* compiler, |
772 int characters_filled_in, | 795 int characters_filled_in, |
773 bool not_at_start); | 796 bool not_at_start); |
774 ZoneList<TextElement>* elements() { return elms_; } | 797 ZoneList<TextElement>* elements() { return elms_; } |
775 void MakeCaseIndependent(bool is_ascii); | 798 void MakeCaseIndependent(bool is_ascii); |
776 virtual int GreedyLoopTextLength(); | 799 virtual int GreedyLoopTextLength(); |
777 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( | 800 virtual RegExpNode* GetSuccessorOfOmnivorousTextNode( |
778 RegExpCompiler* compiler); | 801 RegExpCompiler* compiler); |
779 virtual void FillInBMInfo( | 802 virtual void FillInBMInfo( |
780 int offset, BoyerMooreLookahead* bm, bool not_at_start); | 803 int offset, BoyerMooreLookahead* bm, bool not_at_start); |
781 virtual TextNode* Clone() { | |
782 TextNode* result = new TextNode(*this); | |
783 result->CalculateOffsets(); | |
784 return result; | |
785 } | |
786 void CalculateOffsets(); | 804 void CalculateOffsets(); |
| 805 virtual RegExpNode* FilterASCII(int depth); |
787 | 806 |
788 private: | 807 private: |
789 enum TextEmitPassType { | 808 enum TextEmitPassType { |
790 NON_ASCII_MATCH, // Check for characters that can't match. | 809 NON_ASCII_MATCH, // Check for characters that can't match. |
791 SIMPLE_CHARACTER_MATCH, // Case-dependent single character check. | 810 SIMPLE_CHARACTER_MATCH, // Case-dependent single character check. |
792 NON_LETTER_CHARACTER_MATCH, // Check characters that have no case equivs. | 811 NON_LETTER_CHARACTER_MATCH, // Check characters that have no case equivs. |
793 CASE_CHARACTER_MATCH, // Case-independent single character check. | 812 CASE_CHARACTER_MATCH, // Case-independent single character check. |
794 CHARACTER_CLASS_MATCH // Character class. | 813 CHARACTER_CLASS_MATCH // Character class. |
795 }; | 814 }; |
796 static bool SkipPass(int pass, bool ignore_case); | 815 static bool SkipPass(int pass, bool ignore_case); |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
835 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 854 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
836 virtual int EatsAtLeast(int still_to_find, | 855 virtual int EatsAtLeast(int still_to_find, |
837 int recursion_depth, | 856 int recursion_depth, |
838 bool not_at_start); | 857 bool not_at_start); |
839 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 858 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
840 RegExpCompiler* compiler, | 859 RegExpCompiler* compiler, |
841 int filled_in, | 860 int filled_in, |
842 bool not_at_start); | 861 bool not_at_start); |
843 virtual void FillInBMInfo( | 862 virtual void FillInBMInfo( |
844 int offset, BoyerMooreLookahead* bm, bool not_at_start); | 863 int offset, BoyerMooreLookahead* bm, bool not_at_start); |
845 virtual AssertionNode* Clone() { return new AssertionNode(*this); } | |
846 AssertionNodeType type() { return type_; } | 864 AssertionNodeType type() { return type_; } |
847 void set_type(AssertionNodeType type) { type_ = type; } | 865 void set_type(AssertionNodeType type) { type_ = type; } |
848 | 866 |
849 private: | 867 private: |
850 void EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace); | 868 void EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace); |
851 enum IfPrevious { kIsNonWord, kIsWord }; | 869 enum IfPrevious { kIsNonWord, kIsWord }; |
852 void BacktrackIfPrevious(RegExpCompiler* compiler, | 870 void BacktrackIfPrevious(RegExpCompiler* compiler, |
853 Trace* trace, | 871 Trace* trace, |
854 IfPrevious backtrack_if_previous); | 872 IfPrevious backtrack_if_previous); |
855 AssertionNode(AssertionNodeType t, RegExpNode* on_success) | 873 AssertionNode(AssertionNodeType t, RegExpNode* on_success) |
(...skipping 18 matching lines...) Expand all Loading... |
874 int recursion_depth, | 892 int recursion_depth, |
875 bool not_at_start); | 893 bool not_at_start); |
876 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 894 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
877 RegExpCompiler* compiler, | 895 RegExpCompiler* compiler, |
878 int characters_filled_in, | 896 int characters_filled_in, |
879 bool not_at_start) { | 897 bool not_at_start) { |
880 return; | 898 return; |
881 } | 899 } |
882 virtual void FillInBMInfo( | 900 virtual void FillInBMInfo( |
883 int offset, BoyerMooreLookahead* bm, bool not_at_start); | 901 int offset, BoyerMooreLookahead* bm, bool not_at_start); |
884 virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); } | |
885 | 902 |
886 private: | 903 private: |
887 int start_reg_; | 904 int start_reg_; |
888 int end_reg_; | 905 int end_reg_; |
889 }; | 906 }; |
890 | 907 |
891 | 908 |
892 class EndNode: public RegExpNode { | 909 class EndNode: public RegExpNode { |
893 public: | 910 public: |
894 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; | 911 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; |
895 explicit EndNode(Action action) : action_(action) { } | 912 explicit EndNode(Action action) : action_(action) { } |
896 virtual void Accept(NodeVisitor* visitor); | 913 virtual void Accept(NodeVisitor* visitor); |
897 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 914 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
898 virtual int EatsAtLeast(int still_to_find, | 915 virtual int EatsAtLeast(int still_to_find, |
899 int recursion_depth, | 916 int recursion_depth, |
900 bool not_at_start) { return 0; } | 917 bool not_at_start) { return 0; } |
901 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 918 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
902 RegExpCompiler* compiler, | 919 RegExpCompiler* compiler, |
903 int characters_filled_in, | 920 int characters_filled_in, |
904 bool not_at_start) { | 921 bool not_at_start) { |
905 // Returning 0 from EatsAtLeast should ensure we never get here. | 922 // Returning 0 from EatsAtLeast should ensure we never get here. |
906 UNREACHABLE(); | 923 UNREACHABLE(); |
907 } | 924 } |
908 virtual void FillInBMInfo( | 925 virtual void FillInBMInfo( |
909 int offset, BoyerMooreLookahead* bm, bool not_at_start) { | 926 int offset, BoyerMooreLookahead* bm, bool not_at_start) { |
910 // Returning 0 from EatsAtLeast should ensure we never get here. | 927 // Returning 0 from EatsAtLeast should ensure we never get here. |
911 UNREACHABLE(); | 928 UNREACHABLE(); |
912 } | 929 } |
913 virtual EndNode* Clone() { return new EndNode(*this); } | 930 |
914 private: | 931 private: |
915 Action action_; | 932 Action action_; |
916 }; | 933 }; |
917 | 934 |
918 | 935 |
919 class NegativeSubmatchSuccess: public EndNode { | 936 class NegativeSubmatchSuccess: public EndNode { |
920 public: | 937 public: |
921 NegativeSubmatchSuccess(int stack_pointer_reg, | 938 NegativeSubmatchSuccess(int stack_pointer_reg, |
922 int position_reg, | 939 int position_reg, |
923 int clear_capture_count, | 940 int clear_capture_count, |
(...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
990 int EatsAtLeastHelper(int still_to_find, | 1007 int EatsAtLeastHelper(int still_to_find, |
991 int recursion_depth, | 1008 int recursion_depth, |
992 RegExpNode* ignore_this_node, | 1009 RegExpNode* ignore_this_node, |
993 bool not_at_start); | 1010 bool not_at_start); |
994 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 1011 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
995 RegExpCompiler* compiler, | 1012 RegExpCompiler* compiler, |
996 int characters_filled_in, | 1013 int characters_filled_in, |
997 bool not_at_start); | 1014 bool not_at_start); |
998 virtual void FillInBMInfo( | 1015 virtual void FillInBMInfo( |
999 int offset, BoyerMooreLookahead* bm, bool not_at_start); | 1016 int offset, BoyerMooreLookahead* bm, bool not_at_start); |
1000 virtual ChoiceNode* Clone() { return new ChoiceNode(*this); } | |
1001 | 1017 |
1002 bool being_calculated() { return being_calculated_; } | 1018 bool being_calculated() { return being_calculated_; } |
1003 bool not_at_start() { return not_at_start_; } | 1019 bool not_at_start() { return not_at_start_; } |
1004 void set_not_at_start() { not_at_start_ = true; } | 1020 void set_not_at_start() { not_at_start_ = true; } |
1005 void set_being_calculated(bool b) { being_calculated_ = b; } | 1021 void set_being_calculated(bool b) { being_calculated_ = b; } |
1006 virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; } | 1022 virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; } |
| 1023 virtual RegExpNode* FilterASCII(int depth); |
1007 | 1024 |
1008 protected: | 1025 protected: |
1009 int GreedyLoopTextLengthForAlternative(GuardedAlternative* alternative); | 1026 int GreedyLoopTextLengthForAlternative(GuardedAlternative* alternative); |
1010 ZoneList<GuardedAlternative>* alternatives_; | 1027 ZoneList<GuardedAlternative>* alternatives_; |
1011 | 1028 |
1012 private: | 1029 private: |
1013 friend class DispatchTableConstructor; | 1030 friend class DispatchTableConstructor; |
1014 friend class Analysis; | 1031 friend class Analysis; |
1015 void GenerateGuard(RegExpMacroAssembler* macro_assembler, | 1032 void GenerateGuard(RegExpMacroAssembler* macro_assembler, |
1016 Guard* guard, | 1033 Guard* guard, |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1049 int offset, BoyerMooreLookahead* bm, bool not_at_start) { | 1066 int offset, BoyerMooreLookahead* bm, bool not_at_start) { |
1050 alternatives_->at(1).node()->FillInBMInfo(offset, bm, not_at_start); | 1067 alternatives_->at(1).node()->FillInBMInfo(offset, bm, not_at_start); |
1051 if (offset == 0) set_bm_info(not_at_start, bm); | 1068 if (offset == 0) set_bm_info(not_at_start, bm); |
1052 } | 1069 } |
1053 // For a negative lookahead we don't emit the quick check for the | 1070 // For a negative lookahead we don't emit the quick check for the |
1054 // alternative that is expected to fail. This is because quick check code | 1071 // alternative that is expected to fail. This is because quick check code |
1055 // starts by loading enough characters for the alternative that takes fewest | 1072 // starts by loading enough characters for the alternative that takes fewest |
1056 // characters, but on a negative lookahead the negative branch did not take | 1073 // characters, but on a negative lookahead the negative branch did not take |
1057 // part in that calculation (EatsAtLeast) so the assumptions don't hold. | 1074 // part in that calculation (EatsAtLeast) so the assumptions don't hold. |
1058 virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; } | 1075 virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; } |
| 1076 virtual RegExpNode* FilterASCII(int depth); |
1059 }; | 1077 }; |
1060 | 1078 |
1061 | 1079 |
1062 class LoopChoiceNode: public ChoiceNode { | 1080 class LoopChoiceNode: public ChoiceNode { |
1063 public: | 1081 public: |
1064 explicit LoopChoiceNode(bool body_can_be_zero_length) | 1082 explicit LoopChoiceNode(bool body_can_be_zero_length) |
1065 : ChoiceNode(2), | 1083 : ChoiceNode(2), |
1066 loop_node_(NULL), | 1084 loop_node_(NULL), |
1067 continue_node_(NULL), | 1085 continue_node_(NULL), |
1068 body_can_be_zero_length_(body_can_be_zero_length) { } | 1086 body_can_be_zero_length_(body_can_be_zero_length) { } |
1069 void AddLoopAlternative(GuardedAlternative alt); | 1087 void AddLoopAlternative(GuardedAlternative alt); |
1070 void AddContinueAlternative(GuardedAlternative alt); | 1088 void AddContinueAlternative(GuardedAlternative alt); |
1071 virtual void Emit(RegExpCompiler* compiler, Trace* trace); | 1089 virtual void Emit(RegExpCompiler* compiler, Trace* trace); |
1072 virtual int EatsAtLeast(int still_to_find, | 1090 virtual int EatsAtLeast(int still_to_find, |
1073 int recursion_depth, | 1091 int recursion_depth, |
1074 bool not_at_start); | 1092 bool not_at_start); |
1075 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 1093 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
1076 RegExpCompiler* compiler, | 1094 RegExpCompiler* compiler, |
1077 int characters_filled_in, | 1095 int characters_filled_in, |
1078 bool not_at_start); | 1096 bool not_at_start); |
1079 virtual void FillInBMInfo( | 1097 virtual void FillInBMInfo( |
1080 int offset, BoyerMooreLookahead* bm, bool not_at_start); | 1098 int offset, BoyerMooreLookahead* bm, bool not_at_start); |
1081 virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); } | |
1082 RegExpNode* loop_node() { return loop_node_; } | 1099 RegExpNode* loop_node() { return loop_node_; } |
1083 RegExpNode* continue_node() { return continue_node_; } | 1100 RegExpNode* continue_node() { return continue_node_; } |
1084 bool body_can_be_zero_length() { return body_can_be_zero_length_; } | 1101 bool body_can_be_zero_length() { return body_can_be_zero_length_; } |
1085 virtual void Accept(NodeVisitor* visitor); | 1102 virtual void Accept(NodeVisitor* visitor); |
| 1103 virtual RegExpNode* FilterASCII(int depth); |
1086 | 1104 |
1087 private: | 1105 private: |
1088 // AddAlternative is made private for loop nodes because alternatives | 1106 // AddAlternative is made private for loop nodes because alternatives |
1089 // should not be added freely, we need to keep track of which node | 1107 // should not be added freely, we need to keep track of which node |
1090 // goes back to the node itself. | 1108 // goes back to the node itself. |
1091 void AddAlternative(GuardedAlternative node) { | 1109 void AddAlternative(GuardedAlternative node) { |
1092 ChoiceNode::AddAlternative(node); | 1110 ChoiceNode::AddAlternative(node); |
1093 } | 1111 } |
1094 | 1112 |
1095 RegExpNode* loop_node_; | 1113 RegExpNode* loop_node_; |
(...skipping 469 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1565 int* vector_; | 1583 int* vector_; |
1566 int offsets_vector_length_; | 1584 int offsets_vector_length_; |
1567 | 1585 |
1568 friend class ExternalReference; | 1586 friend class ExternalReference; |
1569 }; | 1587 }; |
1570 | 1588 |
1571 | 1589 |
1572 } } // namespace v8::internal | 1590 } } // namespace v8::internal |
1573 | 1591 |
1574 #endif // V8_JSREGEXP_H_ | 1592 #endif // V8_JSREGEXP_H_ |
OLD | NEW |