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 331 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
342 // The successors are a list of sets that contain the same values | 342 // The successors are a list of sets that contain the same values |
343 // as this set and the one more value that is not present in this | 343 // as this set and the one more value that is not present in this |
344 // set. | 344 // set. |
345 ZoneList<OutSet*>* successors() { return successors_; } | 345 ZoneList<OutSet*>* successors() { return successors_; } |
346 | 346 |
347 OutSet(uint32_t first, ZoneList<unsigned>* remaining) | 347 OutSet(uint32_t first, ZoneList<unsigned>* remaining) |
348 : first_(first), remaining_(remaining), successors_(NULL) { } | 348 : first_(first), remaining_(remaining), successors_(NULL) { } |
349 uint32_t first_; | 349 uint32_t first_; |
350 ZoneList<unsigned>* remaining_; | 350 ZoneList<unsigned>* remaining_; |
351 ZoneList<OutSet*>* successors_; | 351 ZoneList<OutSet*>* successors_; |
352 friend class GenerationVariant; | 352 friend class Trace; |
353 }; | 353 }; |
354 | 354 |
355 | 355 |
356 // A mapping from integers, specified as ranges, to a set of integers. | 356 // A mapping from integers, specified as ranges, to a set of integers. |
357 // Used for mapping character ranges to choices. | 357 // Used for mapping character ranges to choices. |
358 class DispatchTable : public ZoneObject { | 358 class DispatchTable : public ZoneObject { |
359 public: | 359 public: |
360 class Entry { | 360 class Entry { |
361 public: | 361 public: |
362 Entry() : from_(0), to_(0), out_set_(NULL) { } | 362 Entry() : from_(0), to_(0), out_set_(NULL) { } |
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
442 int length(); | 442 int length(); |
443 Type type; | 443 Type type; |
444 union { | 444 union { |
445 RegExpAtom* u_atom; | 445 RegExpAtom* u_atom; |
446 RegExpCharacterClass* u_char_class; | 446 RegExpCharacterClass* u_char_class; |
447 } data; | 447 } data; |
448 int cp_offset; | 448 int cp_offset; |
449 }; | 449 }; |
450 | 450 |
451 | 451 |
452 class GenerationVariant; | 452 class Trace; |
453 | 453 |
454 | 454 |
455 struct NodeInfo { | 455 struct NodeInfo { |
456 enum TriBool { | 456 enum TriBool { |
457 UNKNOWN = -1, FALSE = 0, TRUE = 1 | 457 UNKNOWN = -1, FALSE = 0, TRUE = 1 |
458 }; | 458 }; |
459 | 459 |
460 NodeInfo() | 460 NodeInfo() |
461 : being_analyzed(false), | 461 : being_analyzed(false), |
462 been_analyzed(false), | 462 been_analyzed(false), |
(...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
576 int characters_; | 576 int characters_; |
577 Position positions_[4]; | 577 Position positions_[4]; |
578 // These values are the condensate of the above array after Rationalize(). | 578 // These values are the condensate of the above array after Rationalize(). |
579 uint32_t mask_; | 579 uint32_t mask_; |
580 uint32_t value_; | 580 uint32_t value_; |
581 }; | 581 }; |
582 | 582 |
583 | 583 |
584 class RegExpNode: public ZoneObject { | 584 class RegExpNode: public ZoneObject { |
585 public: | 585 public: |
586 RegExpNode() : variants_generated_(0) { } | 586 RegExpNode() : trace_count_(0) { } |
587 virtual ~RegExpNode(); | 587 virtual ~RegExpNode(); |
588 virtual void Accept(NodeVisitor* visitor) = 0; | 588 virtual void Accept(NodeVisitor* visitor) = 0; |
589 // Generates a goto to this node or actually generates the code at this point. | 589 // Generates a goto to this node or actually generates the code at this point. |
590 // Until the implementation is complete we will return true for success and | 590 // Until the implementation is complete we will return true for success and |
591 // false for failure. | 591 // false for failure. |
592 virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant) = 0; | 592 virtual bool Emit(RegExpCompiler* compiler, Trace* trace) = 0; |
593 // How many characters must this node consume at a minimum in order to | 593 // How many characters must this node consume at a minimum in order to |
594 // succeed. | 594 // succeed. |
595 virtual int EatsAtLeast(int recursion_depth) = 0; | 595 virtual int EatsAtLeast(int recursion_depth) = 0; |
596 // Emits some quick code that checks whether the preloaded characters match. | 596 // Emits some quick code that checks whether the preloaded characters match. |
597 // Falls through on certain failure, jumps to the label on possible success. | 597 // Falls through on certain failure, jumps to the label on possible success. |
598 // If the node cannot make a quick check it does nothing and returns false. | 598 // If the node cannot make a quick check it does nothing and returns false. |
599 bool EmitQuickCheck(RegExpCompiler* compiler, | 599 bool EmitQuickCheck(RegExpCompiler* compiler, |
600 GenerationVariant* variant, | 600 Trace* trace, |
601 bool preload_has_checked_bounds, | 601 bool preload_has_checked_bounds, |
602 Label* on_possible_success, | 602 Label* on_possible_success, |
603 QuickCheckDetails* details_return, | 603 QuickCheckDetails* details_return, |
604 bool fall_through_on_failure); | 604 bool fall_through_on_failure); |
605 // For a given number of characters this returns a mask and a value. The | 605 // For a given number of characters this returns a mask and a value. The |
606 // next n characters are anded with the mask and compared with the value. | 606 // next n characters are anded with the mask and compared with the value. |
607 // A comparison failure indicates the node cannot match the next n characters. | 607 // A comparison failure indicates the node cannot match the next n characters. |
608 // A comparison success indicates the node may match. | 608 // A comparison success indicates the node may match. |
609 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 609 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
610 RegExpCompiler* compiler, | 610 RegExpCompiler* compiler, |
611 int characters_filled_in) = 0; | 611 int characters_filled_in) = 0; |
612 static const int kNodeIsTooComplexForGreedyLoops = -1; | 612 static const int kNodeIsTooComplexForGreedyLoops = -1; |
613 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } | 613 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } |
614 Label* label() { return &label_; } | 614 Label* label() { return &label_; } |
615 static const int kMaxVariantsGenerated = 10; | 615 // 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 // 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 // the deferred actions in the current trace and generating a goto. |
| 620 static const int kMaxCopiesCodeGenerated = 10; |
616 | 621 |
617 // Propagates the given interest information forward. When seeing | 622 // Propagates the given interest information forward. When seeing |
618 // \bfoo for instance, the \b is implemented by propagating forward | 623 // \bfoo for instance, the \b is implemented by propagating forward |
619 // to the 'foo' string that it should only succeed if its first | 624 // to the 'foo' string that it should only succeed if its first |
620 // character is a letter xor the previous character was a letter. | 625 // character is a letter xor the previous character was a letter. |
621 virtual RegExpNode* PropagateForward(NodeInfo* info) = 0; | 626 virtual RegExpNode* PropagateForward(NodeInfo* info) = 0; |
622 | 627 |
623 NodeInfo* info() { return &info_; } | 628 NodeInfo* info() { return &info_; } |
624 | 629 |
625 void AddSibling(RegExpNode* node) { siblings_.Add(node); } | 630 void AddSibling(RegExpNode* node) { siblings_.Add(node); } |
626 | 631 |
627 // Static version of EnsureSibling that expresses the fact that the | 632 // Static version of EnsureSibling that expresses the fact that the |
628 // result has the same type as the input. | 633 // result has the same type as the input. |
629 template <class C> | 634 template <class C> |
630 static C* EnsureSibling(C* node, NodeInfo* info, bool* cloned) { | 635 static C* EnsureSibling(C* node, NodeInfo* info, bool* cloned) { |
631 return static_cast<C*>(node->EnsureSibling(info, cloned)); | 636 return static_cast<C*>(node->EnsureSibling(info, cloned)); |
632 } | 637 } |
633 | 638 |
634 SiblingList* siblings() { return &siblings_; } | 639 SiblingList* siblings() { return &siblings_; } |
635 void set_siblings(SiblingList* other) { siblings_ = *other; } | 640 void set_siblings(SiblingList* other) { siblings_ = *other; } |
636 | 641 |
637 protected: | 642 protected: |
638 enum LimitResult { DONE, FAIL, CONTINUE }; | 643 enum LimitResult { DONE, FAIL, CONTINUE }; |
639 LimitResult LimitVersions(RegExpCompiler* compiler, | 644 LimitResult LimitVersions(RegExpCompiler* compiler, Trace* trace); |
640 GenerationVariant* variant); | |
641 | 645 |
642 // Returns a sibling of this node whose interests and assumptions | 646 // Returns a sibling of this node whose interests and assumptions |
643 // match the ones in the given node info. If no sibling exists NULL | 647 // match the ones in the given node info. If no sibling exists NULL |
644 // is returned. | 648 // is returned. |
645 RegExpNode* TryGetSibling(NodeInfo* info); | 649 RegExpNode* TryGetSibling(NodeInfo* info); |
646 | 650 |
647 // Returns a sibling of this node whose interests match the ones in | 651 // Returns a sibling of this node whose interests match the ones in |
648 // the given node info. The info must not contain any assertions. | 652 // the given node info. The info must not contain any assertions. |
649 // If no node exists a new one will be created by cloning the current | 653 // If no node exists a new one will be created by cloning the current |
650 // node. The result will always be an instance of the same concrete | 654 // node. The result will always be an instance of the same concrete |
651 // class as this node. | 655 // class as this node. |
652 RegExpNode* EnsureSibling(NodeInfo* info, bool* cloned); | 656 RegExpNode* EnsureSibling(NodeInfo* info, bool* cloned); |
653 | 657 |
654 // Returns a clone of this node initialized using the copy constructor | 658 // Returns a clone of this node initialized using the copy constructor |
655 // of its concrete class. Note that the node may have to be pre- | 659 // of its concrete class. Note that the node may have to be pre- |
656 // processed before it is on a useable state. | 660 // processed before it is on a useable state. |
657 virtual RegExpNode* Clone() = 0; | 661 virtual RegExpNode* Clone() = 0; |
658 | 662 |
659 private: | 663 private: |
660 Label label_; | 664 Label label_; |
661 NodeInfo info_; | 665 NodeInfo info_; |
662 SiblingList siblings_; | 666 SiblingList siblings_; |
663 int variants_generated_; | 667 // This variable keeps track of how many times code has been generated for |
| 668 // this node (in different traces). We don't keep track of where the |
| 669 // generated code is located unless the code is generated at the start of |
| 670 // a trace, in which case it is generic and can be reused by flushing the |
| 671 // deferred operations in the current trace and generating a goto. |
| 672 int trace_count_; |
664 }; | 673 }; |
665 | 674 |
666 | 675 |
667 // A simple closed interval. | 676 // A simple closed interval. |
668 class Interval { | 677 class Interval { |
669 public: | 678 public: |
670 Interval() : from_(kNone), to_(kNone) { } | 679 Interval() : from_(kNone), to_(kNone) { } |
671 Interval(int from, int to) : from_(from), to_(to) { } | 680 Interval(int from, int to) : from_(from), to_(to) { } |
672 Interval Union(Interval that) { | 681 Interval Union(Interval that) { |
673 if (that.from_ == kNone) | 682 if (that.from_ == kNone) |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
721 int position_reg, | 730 int position_reg, |
722 RegExpNode* on_success); | 731 RegExpNode* on_success); |
723 static ActionNode* PositiveSubmatchSuccess(int stack_pointer_reg, | 732 static ActionNode* PositiveSubmatchSuccess(int stack_pointer_reg, |
724 int restore_reg, | 733 int restore_reg, |
725 RegExpNode* on_success); | 734 RegExpNode* on_success); |
726 static ActionNode* EmptyMatchCheck(int start_register, | 735 static ActionNode* EmptyMatchCheck(int start_register, |
727 int repetition_register, | 736 int repetition_register, |
728 int repetition_limit, | 737 int repetition_limit, |
729 RegExpNode* on_success); | 738 RegExpNode* on_success); |
730 virtual void Accept(NodeVisitor* visitor); | 739 virtual void Accept(NodeVisitor* visitor); |
731 virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant); | 740 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
732 virtual int EatsAtLeast(int recursion_depth); | 741 virtual int EatsAtLeast(int recursion_depth); |
733 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 742 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
734 RegExpCompiler* compiler, | 743 RegExpCompiler* compiler, |
735 int filled_in) { | 744 int filled_in) { |
736 return on_success()->GetQuickCheckDetails(details, compiler, filled_in); | 745 return on_success()->GetQuickCheckDetails(details, compiler, filled_in); |
737 } | 746 } |
738 virtual RegExpNode* PropagateForward(NodeInfo* info); | 747 virtual RegExpNode* PropagateForward(NodeInfo* info); |
739 Type type() { return type_; } | 748 Type type() { return type_; } |
740 // TODO(erikcorry): We should allow some action nodes in greedy loops. | 749 // TODO(erikcorry): We should allow some action nodes in greedy loops. |
741 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } | 750 virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; } |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
782 : SeqRegExpNode(on_success), | 791 : SeqRegExpNode(on_success), |
783 elms_(elms) { } | 792 elms_(elms) { } |
784 TextNode(RegExpCharacterClass* that, | 793 TextNode(RegExpCharacterClass* that, |
785 RegExpNode* on_success) | 794 RegExpNode* on_success) |
786 : SeqRegExpNode(on_success), | 795 : SeqRegExpNode(on_success), |
787 elms_(new ZoneList<TextElement>(1)) { | 796 elms_(new ZoneList<TextElement>(1)) { |
788 elms_->Add(TextElement::CharClass(that)); | 797 elms_->Add(TextElement::CharClass(that)); |
789 } | 798 } |
790 virtual void Accept(NodeVisitor* visitor); | 799 virtual void Accept(NodeVisitor* visitor); |
791 virtual RegExpNode* PropagateForward(NodeInfo* info); | 800 virtual RegExpNode* PropagateForward(NodeInfo* info); |
792 virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant); | 801 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
793 virtual int EatsAtLeast(int recursion_depth); | 802 virtual int EatsAtLeast(int recursion_depth); |
794 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 803 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
795 RegExpCompiler* compiler, | 804 RegExpCompiler* compiler, |
796 int characters_filled_in); | 805 int characters_filled_in); |
797 ZoneList<TextElement>* elements() { return elms_; } | 806 ZoneList<TextElement>* elements() { return elms_; } |
798 void MakeCaseIndependent(); | 807 void MakeCaseIndependent(); |
799 virtual int GreedyLoopTextLength(); | 808 virtual int GreedyLoopTextLength(); |
800 virtual TextNode* Clone() { | 809 virtual TextNode* Clone() { |
801 TextNode* result = new TextNode(*this); | 810 TextNode* result = new TextNode(*this); |
802 result->CalculateOffsets(); | 811 result->CalculateOffsets(); |
803 return result; | 812 return result; |
804 } | 813 } |
805 void CalculateOffsets(); | 814 void CalculateOffsets(); |
806 | 815 |
807 private: | 816 private: |
808 enum TextEmitPassType { | 817 enum TextEmitPassType { |
809 NON_ASCII_MATCH, | 818 NON_ASCII_MATCH, |
810 CHARACTER_MATCH, | 819 CHARACTER_MATCH, |
811 CASE_CHARACTER_MATCH, | 820 CASE_CHARACTER_MATCH, |
812 CHARACTER_CLASS_MATCH | 821 CHARACTER_CLASS_MATCH |
813 }; | 822 }; |
814 void TextEmitPass(RegExpCompiler* compiler, | 823 void TextEmitPass(RegExpCompiler* compiler, |
815 TextEmitPassType pass, | 824 TextEmitPassType pass, |
816 bool preloaded, | 825 bool preloaded, |
817 GenerationVariant* variant, | 826 Trace* trace, |
818 bool first_element_checked, | 827 bool first_element_checked, |
819 int* checked_up_to); | 828 int* checked_up_to); |
820 int Length(); | 829 int Length(); |
821 ZoneList<TextElement>* elms_; | 830 ZoneList<TextElement>* elms_; |
822 }; | 831 }; |
823 | 832 |
824 | 833 |
825 class BackReferenceNode: public SeqRegExpNode { | 834 class BackReferenceNode: public SeqRegExpNode { |
826 public: | 835 public: |
827 BackReferenceNode(int start_reg, | 836 BackReferenceNode(int start_reg, |
828 int end_reg, | 837 int end_reg, |
829 RegExpNode* on_success) | 838 RegExpNode* on_success) |
830 : SeqRegExpNode(on_success), | 839 : SeqRegExpNode(on_success), |
831 start_reg_(start_reg), | 840 start_reg_(start_reg), |
832 end_reg_(end_reg) { } | 841 end_reg_(end_reg) { } |
833 virtual void Accept(NodeVisitor* visitor); | 842 virtual void Accept(NodeVisitor* visitor); |
834 int start_register() { return start_reg_; } | 843 int start_register() { return start_reg_; } |
835 int end_register() { return end_reg_; } | 844 int end_register() { return end_reg_; } |
836 virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant); | 845 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
837 virtual int EatsAtLeast(int recursion_depth) { return 0; } | 846 virtual int EatsAtLeast(int recursion_depth) { return 0; } |
838 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 847 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
839 RegExpCompiler* compiler, | 848 RegExpCompiler* compiler, |
840 int characters_filled_in) { | 849 int characters_filled_in) { |
841 return; | 850 return; |
842 } | 851 } |
843 virtual RegExpNode* PropagateForward(NodeInfo* info); | 852 virtual RegExpNode* PropagateForward(NodeInfo* info); |
844 virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); } | 853 virtual BackReferenceNode* Clone() { return new BackReferenceNode(*this); } |
845 | 854 |
846 private: | 855 private: |
847 int start_reg_; | 856 int start_reg_; |
848 int end_reg_; | 857 int end_reg_; |
849 }; | 858 }; |
850 | 859 |
851 | 860 |
852 class EndNode: public RegExpNode { | 861 class EndNode: public RegExpNode { |
853 public: | 862 public: |
854 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; | 863 enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS }; |
855 explicit EndNode(Action action) : action_(action) { } | 864 explicit EndNode(Action action) : action_(action) { } |
856 virtual void Accept(NodeVisitor* visitor); | 865 virtual void Accept(NodeVisitor* visitor); |
857 virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant); | 866 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
858 virtual int EatsAtLeast(int recursion_depth) { return 0; } | 867 virtual int EatsAtLeast(int recursion_depth) { return 0; } |
859 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 868 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
860 RegExpCompiler* compiler, | 869 RegExpCompiler* compiler, |
861 int characters_filled_in) { | 870 int characters_filled_in) { |
862 // Returning 0 from EatsAtLeast should ensure we never get here. | 871 // Returning 0 from EatsAtLeast should ensure we never get here. |
863 UNREACHABLE(); | 872 UNREACHABLE(); |
864 } | 873 } |
865 virtual RegExpNode* PropagateForward(NodeInfo* info); | 874 virtual RegExpNode* PropagateForward(NodeInfo* info); |
866 virtual EndNode* Clone() { return new EndNode(*this); } | 875 virtual EndNode* Clone() { return new EndNode(*this); } |
867 | 876 |
868 protected: | 877 protected: |
869 void EmitInfoChecks(RegExpMacroAssembler* macro, GenerationVariant* variant); | 878 void EmitInfoChecks(RegExpMacroAssembler* macro, Trace* trace); |
870 | 879 |
871 private: | 880 private: |
872 Action action_; | 881 Action action_; |
873 }; | 882 }; |
874 | 883 |
875 | 884 |
876 class NegativeSubmatchSuccess: public EndNode { | 885 class NegativeSubmatchSuccess: public EndNode { |
877 public: | 886 public: |
878 NegativeSubmatchSuccess(int stack_pointer_reg, int position_reg) | 887 NegativeSubmatchSuccess(int stack_pointer_reg, int position_reg) |
879 : EndNode(NEGATIVE_SUBMATCH_SUCCESS), | 888 : EndNode(NEGATIVE_SUBMATCH_SUCCESS), |
880 stack_pointer_register_(stack_pointer_reg), | 889 stack_pointer_register_(stack_pointer_reg), |
881 current_position_register_(position_reg) { } | 890 current_position_register_(position_reg) { } |
882 virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant); | 891 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
883 | 892 |
884 private: | 893 private: |
885 int stack_pointer_register_; | 894 int stack_pointer_register_; |
886 int current_position_register_; | 895 int current_position_register_; |
887 }; | 896 }; |
888 | 897 |
889 | 898 |
890 class Guard: public ZoneObject { | 899 class Guard: public ZoneObject { |
891 public: | 900 public: |
892 enum Relation { LT, GEQ }; | 901 enum Relation { LT, GEQ }; |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
925 class ChoiceNode: public RegExpNode { | 934 class ChoiceNode: public RegExpNode { |
926 public: | 935 public: |
927 explicit ChoiceNode(int expected_size) | 936 explicit ChoiceNode(int expected_size) |
928 : alternatives_(new ZoneList<GuardedAlternative>(expected_size)), | 937 : alternatives_(new ZoneList<GuardedAlternative>(expected_size)), |
929 table_(NULL), | 938 table_(NULL), |
930 being_calculated_(false) { } | 939 being_calculated_(false) { } |
931 virtual void Accept(NodeVisitor* visitor); | 940 virtual void Accept(NodeVisitor* visitor); |
932 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); } | 941 void AddAlternative(GuardedAlternative node) { alternatives()->Add(node); } |
933 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } | 942 ZoneList<GuardedAlternative>* alternatives() { return alternatives_; } |
934 DispatchTable* GetTable(bool ignore_case); | 943 DispatchTable* GetTable(bool ignore_case); |
935 virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant); | 944 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
936 virtual int EatsAtLeast(int recursion_depth); | 945 virtual int EatsAtLeast(int recursion_depth); |
937 int EatsAtLeastHelper(int recursion_depth, RegExpNode* ignore_this_node); | 946 int EatsAtLeastHelper(int recursion_depth, RegExpNode* ignore_this_node); |
938 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 947 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
939 RegExpCompiler* compiler, | 948 RegExpCompiler* compiler, |
940 int characters_filled_in); | 949 int characters_filled_in); |
941 virtual RegExpNode* PropagateForward(NodeInfo* info); | 950 virtual RegExpNode* PropagateForward(NodeInfo* info); |
942 virtual ChoiceNode* Clone() { return new ChoiceNode(*this); } | 951 virtual ChoiceNode* Clone() { return new ChoiceNode(*this); } |
943 | 952 |
944 bool being_calculated() { return being_calculated_; } | 953 bool being_calculated() { return being_calculated_; } |
945 void set_being_calculated(bool b) { being_calculated_ = b; } | 954 void set_being_calculated(bool b) { being_calculated_ = b; } |
946 | 955 |
947 protected: | 956 protected: |
948 int GreedyLoopTextLength(GuardedAlternative *alternative); | 957 int GreedyLoopTextLength(GuardedAlternative *alternative); |
949 ZoneList<GuardedAlternative>* alternatives_; | 958 ZoneList<GuardedAlternative>* alternatives_; |
950 | 959 |
951 private: | 960 private: |
952 friend class DispatchTableConstructor; | 961 friend class DispatchTableConstructor; |
953 friend class Analysis; | 962 friend class Analysis; |
954 void GenerateGuard(RegExpMacroAssembler* macro_assembler, | 963 void GenerateGuard(RegExpMacroAssembler* macro_assembler, |
955 Guard *guard, | 964 Guard *guard, |
956 GenerationVariant* variant); | 965 Trace* trace); |
957 int CalculatePreloadCharacters(RegExpCompiler* compiler); | 966 int CalculatePreloadCharacters(RegExpCompiler* compiler); |
958 bool EmitOutOfLineContinuation(RegExpCompiler* compiler, | 967 bool EmitOutOfLineContinuation(RegExpCompiler* compiler, |
959 GenerationVariant* variant, | 968 Trace* trace, |
960 GuardedAlternative alternative, | 969 GuardedAlternative alternative, |
961 AlternativeGeneration* alt_gen, | 970 AlternativeGeneration* alt_gen, |
962 int preload_characters, | 971 int preload_characters, |
963 bool next_expects_preload); | 972 bool next_expects_preload); |
964 DispatchTable* table_; | 973 DispatchTable* table_; |
965 bool being_calculated_; | 974 bool being_calculated_; |
966 }; | 975 }; |
967 | 976 |
968 | 977 |
969 class LoopChoiceNode: public ChoiceNode { | 978 class LoopChoiceNode: public ChoiceNode { |
970 public: | 979 public: |
971 explicit LoopChoiceNode(bool body_can_be_zero_length) | 980 explicit LoopChoiceNode(bool body_can_be_zero_length) |
972 : ChoiceNode(2), | 981 : ChoiceNode(2), |
973 loop_node_(NULL), | 982 loop_node_(NULL), |
974 continue_node_(NULL), | 983 continue_node_(NULL), |
975 body_can_be_zero_length_(body_can_be_zero_length) { } | 984 body_can_be_zero_length_(body_can_be_zero_length) { } |
976 void AddLoopAlternative(GuardedAlternative alt); | 985 void AddLoopAlternative(GuardedAlternative alt); |
977 void AddContinueAlternative(GuardedAlternative alt); | 986 void AddContinueAlternative(GuardedAlternative alt); |
978 virtual bool Emit(RegExpCompiler* compiler, GenerationVariant* variant); | 987 virtual bool Emit(RegExpCompiler* compiler, Trace* trace); |
979 virtual int EatsAtLeast(int recursion_depth); // Returns 0. | 988 virtual int EatsAtLeast(int recursion_depth); // Returns 0. |
980 virtual void GetQuickCheckDetails(QuickCheckDetails* details, | 989 virtual void GetQuickCheckDetails(QuickCheckDetails* details, |
981 RegExpCompiler* compiler, | 990 RegExpCompiler* compiler, |
982 int characters_filled_in); | 991 int characters_filled_in); |
983 virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); } | 992 virtual LoopChoiceNode* Clone() { return new LoopChoiceNode(*this); } |
984 RegExpNode* loop_node() { return loop_node_; } | 993 RegExpNode* loop_node() { return loop_node_; } |
985 RegExpNode* continue_node() { return continue_node_; } | 994 RegExpNode* continue_node() { return continue_node_; } |
986 bool body_can_be_zero_length() { return body_can_be_zero_length_; } | 995 bool body_can_be_zero_length() { return body_can_be_zero_length_; } |
987 virtual void Accept(NodeVisitor* visitor); | 996 virtual void Accept(NodeVisitor* visitor); |
988 | 997 |
989 private: | 998 private: |
990 // AddAlternative is made private for loop nodes because alternatives | 999 // AddAlternative is made private for loop nodes because alternatives |
991 // should not be added freely, we need to keep track of which node | 1000 // should not be added freely, we need to keep track of which node |
992 // goes back to the node itself. | 1001 // goes back to the node itself. |
993 void AddAlternative(GuardedAlternative node) { | 1002 void AddAlternative(GuardedAlternative node) { |
994 ChoiceNode::AddAlternative(node); | 1003 ChoiceNode::AddAlternative(node); |
995 } | 1004 } |
996 | 1005 |
997 RegExpNode* loop_node_; | 1006 RegExpNode* loop_node_; |
998 RegExpNode* continue_node_; | 1007 RegExpNode* continue_node_; |
999 bool body_can_be_zero_length_; | 1008 bool body_can_be_zero_length_; |
1000 }; | 1009 }; |
1001 | 1010 |
1002 | 1011 |
1003 // There are many ways to generate code for a node. This class encapsulates | 1012 // There are many ways to generate code for a node. This class encapsulates |
1004 // the current way we should be generating. In other words it encapsulates | 1013 // the current way we should be generating. In other words it encapsulates |
1005 // the current state of the code generator. | 1014 // the current state of the code generator. The effect of this is that we |
1006 class GenerationVariant { | 1015 // generate code for paths that the matcher can take through the regular |
| 1016 // expression. A given node in the regexp can be code-generated several times |
| 1017 // as it can be part of several traces. For example for the regexp: |
| 1018 // /foo(bar|ip)baz/ the code to match baz will be generated twice, once as part |
| 1019 // of the foo-bar-baz trace and once as part of the foo-ip-baz trace. The code |
| 1020 // to match foo is generated only once (the traces have a common prefix). The |
| 1021 // code to store the capture is deferred and generated (twice) after the places |
| 1022 // where baz has been matched. |
| 1023 class Trace { |
1007 public: | 1024 public: |
1008 class DeferredAction { | 1025 class DeferredAction { |
1009 public: | 1026 public: |
1010 DeferredAction(ActionNode::Type type, int reg) | 1027 DeferredAction(ActionNode::Type type, int reg) |
1011 : type_(type), reg_(reg), next_(NULL) { } | 1028 : type_(type), reg_(reg), next_(NULL) { } |
1012 DeferredAction* next() { return next_; } | 1029 DeferredAction* next() { return next_; } |
1013 bool Mentions(int reg); | 1030 bool Mentions(int reg); |
1014 int reg() { return reg_; } | 1031 int reg() { return reg_; } |
1015 ActionNode::Type type() { return type_; } | 1032 ActionNode::Type type() { return type_; } |
1016 private: | 1033 private: |
1017 ActionNode::Type type_; | 1034 ActionNode::Type type_; |
1018 int reg_; | 1035 int reg_; |
1019 DeferredAction* next_; | 1036 DeferredAction* next_; |
1020 friend class GenerationVariant; | 1037 friend class Trace; |
1021 }; | 1038 }; |
1022 | 1039 |
1023 class DeferredCapture: public DeferredAction { | 1040 class DeferredCapture: public DeferredAction { |
1024 public: | 1041 public: |
1025 DeferredCapture(int reg, GenerationVariant* variant) | 1042 DeferredCapture(int reg, Trace* trace) |
1026 : DeferredAction(ActionNode::STORE_POSITION, reg), | 1043 : DeferredAction(ActionNode::STORE_POSITION, reg), |
1027 cp_offset_(variant->cp_offset()) { } | 1044 cp_offset_(trace->cp_offset()) { } |
1028 int cp_offset() { return cp_offset_; } | 1045 int cp_offset() { return cp_offset_; } |
1029 private: | 1046 private: |
1030 int cp_offset_; | 1047 int cp_offset_; |
1031 void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; } | 1048 void set_cp_offset(int cp_offset) { cp_offset_ = cp_offset; } |
1032 }; | 1049 }; |
1033 | 1050 |
1034 class DeferredSetRegister :public DeferredAction { | 1051 class DeferredSetRegister :public DeferredAction { |
1035 public: | 1052 public: |
1036 DeferredSetRegister(int reg, int value) | 1053 DeferredSetRegister(int reg, int value) |
1037 : DeferredAction(ActionNode::SET_REGISTER, reg), | 1054 : DeferredAction(ActionNode::SET_REGISTER, reg), |
(...skipping 12 matching lines...) Expand all Loading... |
1050 private: | 1067 private: |
1051 Interval range_; | 1068 Interval range_; |
1052 }; | 1069 }; |
1053 | 1070 |
1054 class DeferredIncrementRegister: public DeferredAction { | 1071 class DeferredIncrementRegister: public DeferredAction { |
1055 public: | 1072 public: |
1056 explicit DeferredIncrementRegister(int reg) | 1073 explicit DeferredIncrementRegister(int reg) |
1057 : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { } | 1074 : DeferredAction(ActionNode::INCREMENT_REGISTER, reg) { } |
1058 }; | 1075 }; |
1059 | 1076 |
1060 GenerationVariant() | 1077 Trace() |
1061 : cp_offset_(0), | 1078 : cp_offset_(0), |
1062 actions_(NULL), | 1079 actions_(NULL), |
1063 backtrack_(NULL), | 1080 backtrack_(NULL), |
1064 stop_node_(NULL), | 1081 stop_node_(NULL), |
1065 loop_label_(NULL), | 1082 loop_label_(NULL), |
1066 characters_preloaded_(0), | 1083 characters_preloaded_(0), |
1067 bound_checked_up_to_(0) { } | 1084 bound_checked_up_to_(0) { } |
| 1085 // End the trace. This involves flushing the deferred actions in the trace an
d |
| 1086 // pushing a backtrack location onto the backtrack stack. Once this is done w
e |
| 1087 // can start a new trace or go to one that has already been generated. |
1068 bool Flush(RegExpCompiler* compiler, RegExpNode* successor); | 1088 bool Flush(RegExpCompiler* compiler, RegExpNode* successor); |
1069 int cp_offset() { return cp_offset_; } | 1089 int cp_offset() { return cp_offset_; } |
1070 DeferredAction* actions() { return actions_; } | 1090 DeferredAction* actions() { return actions_; } |
| 1091 // A trivial trace is one that has no deferred actions or other state that |
| 1092 // affects the assumptions used when generating code. There is no recorded |
| 1093 // backtrack location in a trivial trace, so with a trivial trace we will |
| 1094 // generate code that, on a failure to match, gets the backtrack location |
| 1095 // from the backtrack stack rather than using a direct jump instruction. We |
| 1096 // always start code generation with a trivial trace and non-trivial traces |
| 1097 // are created as we emit code for nodes or add to the list of deferred |
| 1098 // actions in the trace. The location of the code generated for a node using |
| 1099 // a trivial trace is recorded in a label in the node so that gotos can be |
| 1100 // generated to that code. |
1071 bool is_trivial() { | 1101 bool is_trivial() { |
1072 return backtrack_ == NULL && | 1102 return backtrack_ == NULL && |
1073 actions_ == NULL && | 1103 actions_ == NULL && |
1074 cp_offset_ == 0 && | 1104 cp_offset_ == 0 && |
1075 characters_preloaded_ == 0 && | 1105 characters_preloaded_ == 0 && |
1076 bound_checked_up_to_ == 0 && | 1106 bound_checked_up_to_ == 0 && |
1077 quick_check_performed_.characters() == 0; | 1107 quick_check_performed_.characters() == 0; |
1078 } | 1108 } |
1079 Label* backtrack() { return backtrack_; } | 1109 Label* backtrack() { return backtrack_; } |
1080 Label* loop_label() { return loop_label_; } | 1110 Label* loop_label() { return loop_label_; } |
1081 RegExpNode* stop_node() { return stop_node_; } | 1111 RegExpNode* stop_node() { return stop_node_; } |
1082 int characters_preloaded() { return characters_preloaded_; } | 1112 int characters_preloaded() { return characters_preloaded_; } |
1083 int bound_checked_up_to() { return bound_checked_up_to_; } | 1113 int bound_checked_up_to() { return bound_checked_up_to_; } |
1084 QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; } | 1114 QuickCheckDetails* quick_check_performed() { return &quick_check_performed_; } |
1085 bool mentions_reg(int reg); | 1115 bool mentions_reg(int reg); |
1086 // Returns true if a deferred position store exists to the specified | 1116 // Returns true if a deferred position store exists to the specified |
1087 // register and stores the offset in the out-parameter. Otherwise | 1117 // register and stores the offset in the out-parameter. Otherwise |
1088 // returns false. | 1118 // returns false. |
1089 bool GetStoredPosition(int reg, int* cp_offset); | 1119 bool GetStoredPosition(int reg, int* cp_offset); |
1090 // These set methods and AdvanceVariant should be used only on new | 1120 // These set methods and AdvanceCurrentPositionInTrace should be used only on |
1091 // GenerationVariants - the intention is that GenerationVariants are | 1121 // new traces - the intention is that traces are immutable after creation. |
1092 // immutable after creation. | |
1093 void add_action(DeferredAction* new_action) { | 1122 void add_action(DeferredAction* new_action) { |
1094 ASSERT(new_action->next_ == NULL); | 1123 ASSERT(new_action->next_ == NULL); |
1095 new_action->next_ = actions_; | 1124 new_action->next_ = actions_; |
1096 actions_ = new_action; | 1125 actions_ = new_action; |
1097 } | 1126 } |
1098 void set_backtrack(Label* backtrack) { backtrack_ = backtrack; } | 1127 void set_backtrack(Label* backtrack) { backtrack_ = backtrack; } |
1099 void set_stop_node(RegExpNode* node) { stop_node_ = node; } | 1128 void set_stop_node(RegExpNode* node) { stop_node_ = node; } |
1100 void set_loop_label(Label* label) { loop_label_ = label; } | 1129 void set_loop_label(Label* label) { loop_label_ = label; } |
1101 void set_characters_preloaded(int cpre) { characters_preloaded_ = cpre; } | 1130 void set_characters_preloaded(int cpre) { characters_preloaded_ = cpre; } |
1102 void set_bound_checked_up_to(int to) { bound_checked_up_to_ = to; } | 1131 void set_bound_checked_up_to(int to) { bound_checked_up_to_ = to; } |
1103 void set_quick_check_performed(QuickCheckDetails* d) { | 1132 void set_quick_check_performed(QuickCheckDetails* d) { |
1104 quick_check_performed_ = *d; | 1133 quick_check_performed_ = *d; |
1105 } | 1134 } |
1106 void clear_quick_check_performed() { | 1135 void clear_quick_check_performed() { |
1107 } | 1136 } |
1108 void AdvanceVariant(int by, bool ascii); | 1137 void AdvanceCurrentPositionInTrace(int by, bool ascii); |
1109 private: | 1138 private: |
1110 int FindAffectedRegisters(OutSet* affected_registers); | 1139 int FindAffectedRegisters(OutSet* affected_registers); |
1111 void PerformDeferredActions(RegExpMacroAssembler* macro, | 1140 void PerformDeferredActions(RegExpMacroAssembler* macro, |
1112 int max_register, | 1141 int max_register, |
1113 OutSet& affected_registers); | 1142 OutSet& affected_registers); |
1114 void RestoreAffectedRegisters(RegExpMacroAssembler* macro, | 1143 void RestoreAffectedRegisters(RegExpMacroAssembler* macro, |
1115 int max_register, | 1144 int max_register, |
1116 OutSet& affected_registers); | 1145 OutSet& affected_registers); |
1117 void PushAffectedRegisters(RegExpMacroAssembler* macro, | 1146 void PushAffectedRegisters(RegExpMacroAssembler* macro, |
1118 int max_register, | 1147 int max_register, |
(...skipping 105 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1224 Handle<String> pattern, | 1253 Handle<String> pattern, |
1225 bool is_ascii); | 1254 bool is_ascii); |
1226 | 1255 |
1227 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case); | 1256 static void DotPrint(const char* label, RegExpNode* node, bool ignore_case); |
1228 }; | 1257 }; |
1229 | 1258 |
1230 | 1259 |
1231 } } // namespace v8::internal | 1260 } } // namespace v8::internal |
1232 | 1261 |
1233 #endif // V8_JSREGEXP_H_ | 1262 #endif // V8_JSREGEXP_H_ |
OLD | NEW |