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 #include "src/ast/ast.h" | 5 #include "src/ast/ast.h" |
6 | 6 |
7 #include <cmath> // For isfinite. | 7 #include <cmath> // For isfinite. |
8 #include "src/ast/scopes.h" | 8 #include "src/ast/scopes.h" |
9 #include "src/builtins.h" | 9 #include "src/builtins.h" |
10 #include "src/code-stubs.h" | 10 #include "src/code-stubs.h" |
(...skipping 780 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
791 // The variable statement visiting code may pass NULL expressions | 791 // The variable statement visiting code may pass NULL expressions |
792 // to this code. Maybe this should be handled by introducing an | 792 // to this code. Maybe this should be handled by introducing an |
793 // undefined expression or literal? Revisit this code if this | 793 // undefined expression or literal? Revisit this code if this |
794 // changes | 794 // changes |
795 Expression* expression = expressions->at(i); | 795 Expression* expression = expressions->at(i); |
796 if (expression != NULL) Visit(expression); | 796 if (expression != NULL) Visit(expression); |
797 } | 797 } |
798 } | 798 } |
799 | 799 |
800 | 800 |
801 // ---------------------------------------------------------------------------- | |
802 // Regular expressions | |
803 | |
804 #define MAKE_ACCEPT(Name) \ | |
805 void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) { \ | |
806 return visitor->Visit##Name(this, data); \ | |
807 } | |
808 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT) | |
809 #undef MAKE_ACCEPT | |
810 | |
811 #define MAKE_TYPE_CASE(Name) \ | |
812 RegExp##Name* RegExpTree::As##Name() { \ | |
813 return NULL; \ | |
814 } \ | |
815 bool RegExpTree::Is##Name() { return false; } | |
816 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) | |
817 #undef MAKE_TYPE_CASE | |
818 | |
819 #define MAKE_TYPE_CASE(Name) \ | |
820 RegExp##Name* RegExp##Name::As##Name() { \ | |
821 return this; \ | |
822 } \ | |
823 bool RegExp##Name::Is##Name() { return true; } | |
824 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) | |
825 #undef MAKE_TYPE_CASE | |
826 | |
827 | |
828 static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) { | |
829 Interval result = Interval::Empty(); | |
830 for (int i = 0; i < children->length(); i++) | |
831 result = result.Union(children->at(i)->CaptureRegisters()); | |
832 return result; | |
833 } | |
834 | |
835 | |
836 Interval RegExpAlternative::CaptureRegisters() { | |
837 return ListCaptureRegisters(nodes()); | |
838 } | |
839 | |
840 | |
841 Interval RegExpDisjunction::CaptureRegisters() { | |
842 return ListCaptureRegisters(alternatives()); | |
843 } | |
844 | |
845 | |
846 Interval RegExpLookaround::CaptureRegisters() { | |
847 return body()->CaptureRegisters(); | |
848 } | |
849 | |
850 | |
851 Interval RegExpCapture::CaptureRegisters() { | |
852 Interval self(StartRegister(index()), EndRegister(index())); | |
853 return self.Union(body()->CaptureRegisters()); | |
854 } | |
855 | |
856 | |
857 Interval RegExpQuantifier::CaptureRegisters() { | |
858 return body()->CaptureRegisters(); | |
859 } | |
860 | |
861 | |
862 bool RegExpAssertion::IsAnchoredAtStart() { | |
863 return assertion_type() == RegExpAssertion::START_OF_INPUT; | |
864 } | |
865 | |
866 | |
867 bool RegExpAssertion::IsAnchoredAtEnd() { | |
868 return assertion_type() == RegExpAssertion::END_OF_INPUT; | |
869 } | |
870 | |
871 | |
872 bool RegExpAlternative::IsAnchoredAtStart() { | |
873 ZoneList<RegExpTree*>* nodes = this->nodes(); | |
874 for (int i = 0; i < nodes->length(); i++) { | |
875 RegExpTree* node = nodes->at(i); | |
876 if (node->IsAnchoredAtStart()) { return true; } | |
877 if (node->max_match() > 0) { return false; } | |
878 } | |
879 return false; | |
880 } | |
881 | |
882 | |
883 bool RegExpAlternative::IsAnchoredAtEnd() { | |
884 ZoneList<RegExpTree*>* nodes = this->nodes(); | |
885 for (int i = nodes->length() - 1; i >= 0; i--) { | |
886 RegExpTree* node = nodes->at(i); | |
887 if (node->IsAnchoredAtEnd()) { return true; } | |
888 if (node->max_match() > 0) { return false; } | |
889 } | |
890 return false; | |
891 } | |
892 | |
893 | |
894 bool RegExpDisjunction::IsAnchoredAtStart() { | |
895 ZoneList<RegExpTree*>* alternatives = this->alternatives(); | |
896 for (int i = 0; i < alternatives->length(); i++) { | |
897 if (!alternatives->at(i)->IsAnchoredAtStart()) | |
898 return false; | |
899 } | |
900 return true; | |
901 } | |
902 | |
903 | |
904 bool RegExpDisjunction::IsAnchoredAtEnd() { | |
905 ZoneList<RegExpTree*>* alternatives = this->alternatives(); | |
906 for (int i = 0; i < alternatives->length(); i++) { | |
907 if (!alternatives->at(i)->IsAnchoredAtEnd()) | |
908 return false; | |
909 } | |
910 return true; | |
911 } | |
912 | |
913 | |
914 bool RegExpLookaround::IsAnchoredAtStart() { | |
915 return is_positive() && type() == LOOKAHEAD && body()->IsAnchoredAtStart(); | |
916 } | |
917 | |
918 | |
919 bool RegExpCapture::IsAnchoredAtStart() { | |
920 return body()->IsAnchoredAtStart(); | |
921 } | |
922 | |
923 | |
924 bool RegExpCapture::IsAnchoredAtEnd() { | |
925 return body()->IsAnchoredAtEnd(); | |
926 } | |
927 | |
928 | |
929 // Convert regular expression trees to a simple sexp representation. | |
930 // This representation should be different from the input grammar | |
931 // in as many cases as possible, to make it more difficult for incorrect | |
932 // parses to look as correct ones which is likely if the input and | |
933 // output formats are alike. | |
934 class RegExpUnparser final : public RegExpVisitor { | |
935 public: | |
936 RegExpUnparser(std::ostream& os, Zone* zone) : os_(os), zone_(zone) {} | |
937 void VisitCharacterRange(CharacterRange that); | |
938 #define MAKE_CASE(Name) void* Visit##Name(RegExp##Name*, void* data) override; | |
939 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE) | |
940 #undef MAKE_CASE | |
941 private: | |
942 std::ostream& os_; | |
943 Zone* zone_; | |
944 }; | |
945 | |
946 | |
947 void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) { | |
948 os_ << "(|"; | |
949 for (int i = 0; i < that->alternatives()->length(); i++) { | |
950 os_ << " "; | |
951 that->alternatives()->at(i)->Accept(this, data); | |
952 } | |
953 os_ << ")"; | |
954 return NULL; | |
955 } | |
956 | |
957 | |
958 void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) { | |
959 os_ << "(:"; | |
960 for (int i = 0; i < that->nodes()->length(); i++) { | |
961 os_ << " "; | |
962 that->nodes()->at(i)->Accept(this, data); | |
963 } | |
964 os_ << ")"; | |
965 return NULL; | |
966 } | |
967 | |
968 | |
969 void RegExpUnparser::VisitCharacterRange(CharacterRange that) { | |
970 os_ << AsUC16(that.from()); | |
971 if (!that.IsSingleton()) { | |
972 os_ << "-" << AsUC16(that.to()); | |
973 } | |
974 } | |
975 | |
976 | |
977 | |
978 void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that, | |
979 void* data) { | |
980 if (that->is_negated()) os_ << "^"; | |
981 os_ << "["; | |
982 for (int i = 0; i < that->ranges(zone_)->length(); i++) { | |
983 if (i > 0) os_ << " "; | |
984 VisitCharacterRange(that->ranges(zone_)->at(i)); | |
985 } | |
986 os_ << "]"; | |
987 return NULL; | |
988 } | |
989 | |
990 | |
991 void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) { | |
992 switch (that->assertion_type()) { | |
993 case RegExpAssertion::START_OF_INPUT: | |
994 os_ << "@^i"; | |
995 break; | |
996 case RegExpAssertion::END_OF_INPUT: | |
997 os_ << "@$i"; | |
998 break; | |
999 case RegExpAssertion::START_OF_LINE: | |
1000 os_ << "@^l"; | |
1001 break; | |
1002 case RegExpAssertion::END_OF_LINE: | |
1003 os_ << "@$l"; | |
1004 break; | |
1005 case RegExpAssertion::BOUNDARY: | |
1006 os_ << "@b"; | |
1007 break; | |
1008 case RegExpAssertion::NON_BOUNDARY: | |
1009 os_ << "@B"; | |
1010 break; | |
1011 } | |
1012 return NULL; | |
1013 } | |
1014 | |
1015 | |
1016 void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) { | |
1017 os_ << "'"; | |
1018 Vector<const uc16> chardata = that->data(); | |
1019 for (int i = 0; i < chardata.length(); i++) { | |
1020 os_ << AsUC16(chardata[i]); | |
1021 } | |
1022 os_ << "'"; | |
1023 return NULL; | |
1024 } | |
1025 | |
1026 | |
1027 void* RegExpUnparser::VisitText(RegExpText* that, void* data) { | |
1028 if (that->elements()->length() == 1) { | |
1029 that->elements()->at(0).tree()->Accept(this, data); | |
1030 } else { | |
1031 os_ << "(!"; | |
1032 for (int i = 0; i < that->elements()->length(); i++) { | |
1033 os_ << " "; | |
1034 that->elements()->at(i).tree()->Accept(this, data); | |
1035 } | |
1036 os_ << ")"; | |
1037 } | |
1038 return NULL; | |
1039 } | |
1040 | |
1041 | |
1042 void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) { | |
1043 os_ << "(# " << that->min() << " "; | |
1044 if (that->max() == RegExpTree::kInfinity) { | |
1045 os_ << "- "; | |
1046 } else { | |
1047 os_ << that->max() << " "; | |
1048 } | |
1049 os_ << (that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n "); | |
1050 that->body()->Accept(this, data); | |
1051 os_ << ")"; | |
1052 return NULL; | |
1053 } | |
1054 | |
1055 | |
1056 void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) { | |
1057 os_ << "(^ "; | |
1058 that->body()->Accept(this, data); | |
1059 os_ << ")"; | |
1060 return NULL; | |
1061 } | |
1062 | |
1063 | |
1064 void* RegExpUnparser::VisitLookaround(RegExpLookaround* that, void* data) { | |
1065 os_ << "("; | |
1066 os_ << (that->type() == RegExpLookaround::LOOKAHEAD ? "->" : "<-"); | |
1067 os_ << (that->is_positive() ? " + " : " - "); | |
1068 that->body()->Accept(this, data); | |
1069 os_ << ")"; | |
1070 return NULL; | |
1071 } | |
1072 | |
1073 | |
1074 void* RegExpUnparser::VisitBackReference(RegExpBackReference* that, | |
1075 void* data) { | |
1076 os_ << "(<- " << that->index() << ")"; | |
1077 return NULL; | |
1078 } | |
1079 | |
1080 | |
1081 void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) { | |
1082 os_ << '%'; | |
1083 return NULL; | |
1084 } | |
1085 | |
1086 | |
1087 std::ostream& RegExpTree::Print(std::ostream& os, Zone* zone) { // NOLINT | |
1088 RegExpUnparser unparser(os, zone); | |
1089 Accept(&unparser, NULL); | |
1090 return os; | |
1091 } | |
1092 | |
1093 | |
1094 RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives) | |
1095 : alternatives_(alternatives) { | |
1096 DCHECK(alternatives->length() > 1); | |
1097 RegExpTree* first_alternative = alternatives->at(0); | |
1098 min_match_ = first_alternative->min_match(); | |
1099 max_match_ = first_alternative->max_match(); | |
1100 for (int i = 1; i < alternatives->length(); i++) { | |
1101 RegExpTree* alternative = alternatives->at(i); | |
1102 min_match_ = Min(min_match_, alternative->min_match()); | |
1103 max_match_ = Max(max_match_, alternative->max_match()); | |
1104 } | |
1105 } | |
1106 | |
1107 | |
1108 static int IncreaseBy(int previous, int increase) { | |
1109 if (RegExpTree::kInfinity - previous < increase) { | |
1110 return RegExpTree::kInfinity; | |
1111 } else { | |
1112 return previous + increase; | |
1113 } | |
1114 } | |
1115 | |
1116 RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes) | |
1117 : nodes_(nodes) { | |
1118 DCHECK(nodes->length() > 1); | |
1119 min_match_ = 0; | |
1120 max_match_ = 0; | |
1121 for (int i = 0; i < nodes->length(); i++) { | |
1122 RegExpTree* node = nodes->at(i); | |
1123 int node_min_match = node->min_match(); | |
1124 min_match_ = IncreaseBy(min_match_, node_min_match); | |
1125 int node_max_match = node->max_match(); | |
1126 max_match_ = IncreaseBy(max_match_, node_max_match); | |
1127 } | |
1128 } | |
1129 | |
1130 | |
1131 CaseClause::CaseClause(Zone* zone, Expression* label, | 801 CaseClause::CaseClause(Zone* zone, Expression* label, |
1132 ZoneList<Statement*>* statements, int pos) | 802 ZoneList<Statement*>* statements, int pos) |
1133 : Expression(zone, pos), | 803 : Expression(zone, pos), |
1134 label_(label), | 804 label_(label), |
1135 statements_(statements), | 805 statements_(statements), |
1136 compare_type_(Type::None(zone)) {} | 806 compare_type_(Type::None(zone)) {} |
1137 | 807 |
1138 | 808 |
1139 uint32_t Literal::Hash() { | 809 uint32_t Literal::Hash() { |
1140 return raw_value()->IsString() | 810 return raw_value()->IsString() |
1141 ? raw_value()->AsString()->hash() | 811 ? raw_value()->AsString()->hash() |
1142 : ComputeLongHash(double_to_uint64(raw_value()->AsNumber())); | 812 : ComputeLongHash(double_to_uint64(raw_value()->AsNumber())); |
1143 } | 813 } |
1144 | 814 |
1145 | 815 |
1146 // static | 816 // static |
1147 bool Literal::Match(void* literal1, void* literal2) { | 817 bool Literal::Match(void* literal1, void* literal2) { |
1148 const AstValue* x = static_cast<Literal*>(literal1)->raw_value(); | 818 const AstValue* x = static_cast<Literal*>(literal1)->raw_value(); |
1149 const AstValue* y = static_cast<Literal*>(literal2)->raw_value(); | 819 const AstValue* y = static_cast<Literal*>(literal2)->raw_value(); |
1150 return (x->IsString() && y->IsString() && x->AsString() == y->AsString()) || | 820 return (x->IsString() && y->IsString() && x->AsString() == y->AsString()) || |
1151 (x->IsNumber() && y->IsNumber() && x->AsNumber() == y->AsNumber()); | 821 (x->IsNumber() && y->IsNumber() && x->AsNumber() == y->AsNumber()); |
1152 } | 822 } |
1153 | 823 |
1154 | 824 |
1155 } // namespace internal | 825 } // namespace internal |
1156 } // namespace v8 | 826 } // namespace v8 |
OLD | NEW |