| 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/regexp/jsregexp.h" | 5 #include "src/regexp/jsregexp.h" |
| 6 | 6 |
| 7 #include "src/ast/ast.h" | 7 #include "src/ast/ast.h" |
| 8 #include "src/base/platform/platform.h" | 8 #include "src/base/platform/platform.h" |
| 9 #include "src/compilation-cache.h" | 9 #include "src/compilation-cache.h" |
| 10 #include "src/compiler.h" | 10 #include "src/compiler.h" |
| (...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 65 Handle<String> error_text) { | 65 Handle<String> error_text) { |
| 66 USE(ThrowRegExpException(re, Handle<String>(re->Pattern()), error_text)); | 66 USE(ThrowRegExpException(re, Handle<String>(re->Pattern()), error_text)); |
| 67 } | 67 } |
| 68 | 68 |
| 69 | 69 |
| 70 ContainedInLattice AddRange(ContainedInLattice containment, | 70 ContainedInLattice AddRange(ContainedInLattice containment, |
| 71 const int* ranges, | 71 const int* ranges, |
| 72 int ranges_length, | 72 int ranges_length, |
| 73 Interval new_range) { | 73 Interval new_range) { |
| 74 DCHECK((ranges_length & 1) == 1); | 74 DCHECK((ranges_length & 1) == 1); |
| 75 DCHECK(ranges[ranges_length - 1] == String::kMaxCodePoint + 1); | 75 DCHECK(ranges[ranges_length - 1] == String::kMaxUtf16CodeUnit + 1); |
| 76 if (containment == kLatticeUnknown) return containment; | 76 if (containment == kLatticeUnknown) return containment; |
| 77 bool inside = false; | 77 bool inside = false; |
| 78 int last = 0; | 78 int last = 0; |
| 79 for (int i = 0; i < ranges_length; inside = !inside, last = ranges[i], i++) { | 79 for (int i = 0; i < ranges_length; inside = !inside, last = ranges[i], i++) { |
| 80 // Consider the range from last to ranges[i]. | 80 // Consider the range from last to ranges[i]. |
| 81 // We haven't got to the new range yet. | 81 // We haven't got to the new range yet. |
| 82 if (ranges[i] <= new_range.from()) continue; | 82 if (ranges[i] <= new_range.from()) continue; |
| 83 // New range is wholly inside last-ranges[i]. Note that new_range.to() is | 83 // New range is wholly inside last-ranges[i]. Note that new_range.to() is |
| 84 // inclusive, but the values in ranges are not. | 84 // inclusive, but the values in ranges are not. |
| 85 if (last <= new_range.from() && new_range.to() < ranges[i]) { | 85 if (last <= new_range.from() && new_range.to() < ranges[i]) { |
| (...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 138 | 138 |
| 139 Handle<Object> result; | 139 Handle<Object> result; |
| 140 if (in_cache) { | 140 if (in_cache) { |
| 141 re->set_data(*cached); | 141 re->set_data(*cached); |
| 142 return re; | 142 return re; |
| 143 } | 143 } |
| 144 pattern = String::Flatten(pattern); | 144 pattern = String::Flatten(pattern); |
| 145 PostponeInterruptsScope postpone(isolate); | 145 PostponeInterruptsScope postpone(isolate); |
| 146 RegExpCompileData parse_result; | 146 RegExpCompileData parse_result; |
| 147 FlatStringReader reader(isolate, pattern); | 147 FlatStringReader reader(isolate, pattern); |
| 148 if (!RegExpParser::ParseRegExp(re->GetIsolate(), &zone, &reader, flags, | 148 if (!RegExpParser::ParseRegExp(re->GetIsolate(), &zone, &reader, |
| 149 &parse_result)) { | 149 flags & JSRegExp::kMultiline, |
| 150 flags & JSRegExp::kUnicode, &parse_result)) { |
| 150 // Throw an exception if we fail to parse the pattern. | 151 // Throw an exception if we fail to parse the pattern. |
| 151 return ThrowRegExpException(re, pattern, parse_result.error); | 152 return ThrowRegExpException(re, pattern, parse_result.error); |
| 152 } | 153 } |
| 153 | 154 |
| 154 bool has_been_compiled = false; | 155 bool has_been_compiled = false; |
| 155 | 156 |
| 156 if (parse_result.simple && !(flags & JSRegExp::kIgnoreCase) && | 157 if (parse_result.simple && !(flags & JSRegExp::kIgnoreCase) && |
| 157 !(flags & JSRegExp::kSticky) && !HasFewDifferentCharacters(pattern)) { | 158 !(flags & JSRegExp::kSticky) && !HasFewDifferentCharacters(pattern)) { |
| 158 // Parse-tree is a single atom that is equal to the pattern. | 159 // Parse-tree is a single atom that is equal to the pattern. |
| 159 AtomCompile(re, pattern, flags, pattern); | 160 AtomCompile(re, pattern, flags, pattern); |
| (...skipping 203 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 363 ThrowRegExpException(re, error_message); | 364 ThrowRegExpException(re, error_message); |
| 364 return false; | 365 return false; |
| 365 } | 366 } |
| 366 | 367 |
| 367 JSRegExp::Flags flags = re->GetFlags(); | 368 JSRegExp::Flags flags = re->GetFlags(); |
| 368 | 369 |
| 369 Handle<String> pattern(re->Pattern()); | 370 Handle<String> pattern(re->Pattern()); |
| 370 pattern = String::Flatten(pattern); | 371 pattern = String::Flatten(pattern); |
| 371 RegExpCompileData compile_data; | 372 RegExpCompileData compile_data; |
| 372 FlatStringReader reader(isolate, pattern); | 373 FlatStringReader reader(isolate, pattern); |
| 373 if (!RegExpParser::ParseRegExp(isolate, &zone, &reader, flags, | 374 if (!RegExpParser::ParseRegExp(isolate, &zone, &reader, |
| 374 &compile_data)) { | 375 flags & JSRegExp::kMultiline, |
| 376 flags & JSRegExp::kUnicode, &compile_data)) { |
| 375 // Throw an exception if we fail to parse the pattern. | 377 // Throw an exception if we fail to parse the pattern. |
| 376 // THIS SHOULD NOT HAPPEN. We already pre-parsed it successfully once. | 378 // THIS SHOULD NOT HAPPEN. We already pre-parsed it successfully once. |
| 377 USE(ThrowRegExpException(re, pattern, compile_data.error)); | 379 USE(ThrowRegExpException(re, pattern, compile_data.error)); |
| 378 return false; | 380 return false; |
| 379 } | 381 } |
| 380 RegExpEngine::CompilationResult result = | 382 RegExpEngine::CompilationResult result = RegExpEngine::Compile( |
| 381 RegExpEngine::Compile(isolate, &zone, &compile_data, flags, pattern, | 383 isolate, &zone, &compile_data, flags & JSRegExp::kIgnoreCase, |
| 382 sample_subject, is_one_byte); | 384 flags & JSRegExp::kGlobal, flags & JSRegExp::kMultiline, |
| 385 flags & JSRegExp::kSticky, pattern, sample_subject, is_one_byte); |
| 383 if (result.error_message != NULL) { | 386 if (result.error_message != NULL) { |
| 384 // Unable to compile regexp. | 387 // Unable to compile regexp. |
| 385 Handle<String> error_message = isolate->factory()->NewStringFromUtf8( | 388 Handle<String> error_message = isolate->factory()->NewStringFromUtf8( |
| 386 CStrVector(result.error_message)).ToHandleChecked(); | 389 CStrVector(result.error_message)).ToHandleChecked(); |
| 387 ThrowRegExpException(re, error_message); | 390 ThrowRegExpException(re, error_message); |
| 388 return false; | 391 return false; |
| 389 } | 392 } |
| 390 | 393 |
| 391 Handle<FixedArray> data = Handle<FixedArray>(FixedArray::cast(re->data())); | 394 Handle<FixedArray> data = Handle<FixedArray>(FixedArray::cast(re->data())); |
| 392 data->set(JSRegExp::code_index(is_one_byte), result.code); | 395 data->set(JSRegExp::code_index(is_one_byte), result.code); |
| (...skipping 542 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 935 | 938 |
| 936 private: | 939 private: |
| 937 CharacterFrequency frequencies_[RegExpMacroAssembler::kTableSize]; | 940 CharacterFrequency frequencies_[RegExpMacroAssembler::kTableSize]; |
| 938 int total_samples_; | 941 int total_samples_; |
| 939 }; | 942 }; |
| 940 | 943 |
| 941 | 944 |
| 942 class RegExpCompiler { | 945 class RegExpCompiler { |
| 943 public: | 946 public: |
| 944 RegExpCompiler(Isolate* isolate, Zone* zone, int capture_count, | 947 RegExpCompiler(Isolate* isolate, Zone* zone, int capture_count, |
| 945 JSRegExp::Flags flags, bool is_one_byte); | 948 bool ignore_case, bool is_one_byte); |
| 946 | 949 |
| 947 int AllocateRegister() { | 950 int AllocateRegister() { |
| 948 if (next_register_ >= RegExpMacroAssembler::kMaxRegister) { | 951 if (next_register_ >= RegExpMacroAssembler::kMaxRegister) { |
| 949 reg_exp_too_big_ = true; | 952 reg_exp_too_big_ = true; |
| 950 return next_register_; | 953 return next_register_; |
| 951 } | 954 } |
| 952 return next_register_++; | 955 return next_register_++; |
| 953 } | 956 } |
| 954 | 957 |
| 955 // Lookarounds to match lone surrogates for unicode character class matches | |
| 956 // are never nested. We can therefore reuse registers. | |
| 957 int UnicodeLookaroundStackRegister() { | |
| 958 if (unicode_lookaround_stack_register_ == kNoRegister) { | |
| 959 unicode_lookaround_stack_register_ = AllocateRegister(); | |
| 960 } | |
| 961 return unicode_lookaround_stack_register_; | |
| 962 } | |
| 963 | |
| 964 int UnicodeLookaroundPositionRegister() { | |
| 965 if (unicode_lookaround_position_register_ == kNoRegister) { | |
| 966 unicode_lookaround_position_register_ = AllocateRegister(); | |
| 967 } | |
| 968 return unicode_lookaround_position_register_; | |
| 969 } | |
| 970 | |
| 971 RegExpEngine::CompilationResult Assemble(RegExpMacroAssembler* assembler, | 958 RegExpEngine::CompilationResult Assemble(RegExpMacroAssembler* assembler, |
| 972 RegExpNode* start, | 959 RegExpNode* start, |
| 973 int capture_count, | 960 int capture_count, |
| 974 Handle<String> pattern); | 961 Handle<String> pattern); |
| 975 | 962 |
| 976 inline void AddWork(RegExpNode* node) { | 963 inline void AddWork(RegExpNode* node) { |
| 977 if (!node->on_work_list() && !node->label()->is_bound()) { | 964 if (!node->on_work_list() && !node->label()->is_bound()) { |
| 978 node->set_on_work_list(true); | 965 node->set_on_work_list(true); |
| 979 work_list_->Add(node); | 966 work_list_->Add(node); |
| 980 } | 967 } |
| 981 } | 968 } |
| 982 | 969 |
| 983 static const int kImplementationOffset = 0; | 970 static const int kImplementationOffset = 0; |
| 984 static const int kNumberOfRegistersOffset = 0; | 971 static const int kNumberOfRegistersOffset = 0; |
| 985 static const int kCodeOffset = 1; | 972 static const int kCodeOffset = 1; |
| 986 | 973 |
| 987 RegExpMacroAssembler* macro_assembler() { return macro_assembler_; } | 974 RegExpMacroAssembler* macro_assembler() { return macro_assembler_; } |
| 988 EndNode* accept() { return accept_; } | 975 EndNode* accept() { return accept_; } |
| 989 | 976 |
| 990 static const int kMaxRecursion = 100; | 977 static const int kMaxRecursion = 100; |
| 991 inline int recursion_depth() { return recursion_depth_; } | 978 inline int recursion_depth() { return recursion_depth_; } |
| 992 inline void IncrementRecursionDepth() { recursion_depth_++; } | 979 inline void IncrementRecursionDepth() { recursion_depth_++; } |
| 993 inline void DecrementRecursionDepth() { recursion_depth_--; } | 980 inline void DecrementRecursionDepth() { recursion_depth_--; } |
| 994 | 981 |
| 995 void SetRegExpTooBig() { reg_exp_too_big_ = true; } | 982 void SetRegExpTooBig() { reg_exp_too_big_ = true; } |
| 996 | 983 |
| 997 inline bool ignore_case() { return (flags_ & JSRegExp::kIgnoreCase) != 0; } | 984 inline bool ignore_case() { return ignore_case_; } |
| 998 inline bool unicode() { return (flags_ & JSRegExp::kUnicode) != 0; } | |
| 999 inline bool one_byte() { return one_byte_; } | 985 inline bool one_byte() { return one_byte_; } |
| 1000 inline bool optimize() { return optimize_; } | 986 inline bool optimize() { return optimize_; } |
| 1001 inline void set_optimize(bool value) { optimize_ = value; } | 987 inline void set_optimize(bool value) { optimize_ = value; } |
| 1002 inline bool limiting_recursion() { return limiting_recursion_; } | 988 inline bool limiting_recursion() { return limiting_recursion_; } |
| 1003 inline void set_limiting_recursion(bool value) { | 989 inline void set_limiting_recursion(bool value) { |
| 1004 limiting_recursion_ = value; | 990 limiting_recursion_ = value; |
| 1005 } | 991 } |
| 1006 bool read_backward() { return read_backward_; } | 992 bool read_backward() { return read_backward_; } |
| 1007 void set_read_backward(bool value) { read_backward_ = value; } | 993 void set_read_backward(bool value) { read_backward_ = value; } |
| 1008 FrequencyCollator* frequency_collator() { return &frequency_collator_; } | 994 FrequencyCollator* frequency_collator() { return &frequency_collator_; } |
| 1009 | 995 |
| 1010 int current_expansion_factor() { return current_expansion_factor_; } | 996 int current_expansion_factor() { return current_expansion_factor_; } |
| 1011 void set_current_expansion_factor(int value) { | 997 void set_current_expansion_factor(int value) { |
| 1012 current_expansion_factor_ = value; | 998 current_expansion_factor_ = value; |
| 1013 } | 999 } |
| 1014 | 1000 |
| 1015 Isolate* isolate() const { return isolate_; } | 1001 Isolate* isolate() const { return isolate_; } |
| 1016 Zone* zone() const { return zone_; } | 1002 Zone* zone() const { return zone_; } |
| 1017 | 1003 |
| 1018 static const int kNoRegister = -1; | 1004 static const int kNoRegister = -1; |
| 1019 | 1005 |
| 1020 private: | 1006 private: |
| 1021 EndNode* accept_; | 1007 EndNode* accept_; |
| 1022 int next_register_; | 1008 int next_register_; |
| 1023 int unicode_lookaround_stack_register_; | |
| 1024 int unicode_lookaround_position_register_; | |
| 1025 List<RegExpNode*>* work_list_; | 1009 List<RegExpNode*>* work_list_; |
| 1026 int recursion_depth_; | 1010 int recursion_depth_; |
| 1027 RegExpMacroAssembler* macro_assembler_; | 1011 RegExpMacroAssembler* macro_assembler_; |
| 1028 JSRegExp::Flags flags_; | 1012 bool ignore_case_; |
| 1029 bool one_byte_; | 1013 bool one_byte_; |
| 1030 bool reg_exp_too_big_; | 1014 bool reg_exp_too_big_; |
| 1031 bool limiting_recursion_; | 1015 bool limiting_recursion_; |
| 1032 bool optimize_; | 1016 bool optimize_; |
| 1033 bool read_backward_; | 1017 bool read_backward_; |
| 1034 int current_expansion_factor_; | 1018 int current_expansion_factor_; |
| 1035 FrequencyCollator frequency_collator_; | 1019 FrequencyCollator frequency_collator_; |
| 1036 Isolate* isolate_; | 1020 Isolate* isolate_; |
| 1037 Zone* zone_; | 1021 Zone* zone_; |
| 1038 }; | 1022 }; |
| (...skipping 11 matching lines...) Expand all Loading... |
| 1050 | 1034 |
| 1051 | 1035 |
| 1052 static RegExpEngine::CompilationResult IrregexpRegExpTooBig(Isolate* isolate) { | 1036 static RegExpEngine::CompilationResult IrregexpRegExpTooBig(Isolate* isolate) { |
| 1053 return RegExpEngine::CompilationResult(isolate, "RegExp too big"); | 1037 return RegExpEngine::CompilationResult(isolate, "RegExp too big"); |
| 1054 } | 1038 } |
| 1055 | 1039 |
| 1056 | 1040 |
| 1057 // Attempts to compile the regexp using an Irregexp code generator. Returns | 1041 // Attempts to compile the regexp using an Irregexp code generator. Returns |
| 1058 // a fixed array or a null handle depending on whether it succeeded. | 1042 // a fixed array or a null handle depending on whether it succeeded. |
| 1059 RegExpCompiler::RegExpCompiler(Isolate* isolate, Zone* zone, int capture_count, | 1043 RegExpCompiler::RegExpCompiler(Isolate* isolate, Zone* zone, int capture_count, |
| 1060 JSRegExp::Flags flags, bool one_byte) | 1044 bool ignore_case, bool one_byte) |
| 1061 : next_register_(2 * (capture_count + 1)), | 1045 : next_register_(2 * (capture_count + 1)), |
| 1062 unicode_lookaround_stack_register_(kNoRegister), | |
| 1063 unicode_lookaround_position_register_(kNoRegister), | |
| 1064 work_list_(NULL), | 1046 work_list_(NULL), |
| 1065 recursion_depth_(0), | 1047 recursion_depth_(0), |
| 1066 flags_(flags), | 1048 ignore_case_(ignore_case), |
| 1067 one_byte_(one_byte), | 1049 one_byte_(one_byte), |
| 1068 reg_exp_too_big_(false), | 1050 reg_exp_too_big_(false), |
| 1069 limiting_recursion_(false), | 1051 limiting_recursion_(false), |
| 1070 optimize_(FLAG_regexp_optimization), | 1052 optimize_(FLAG_regexp_optimization), |
| 1071 read_backward_(false), | 1053 read_backward_(false), |
| 1072 current_expansion_factor_(1), | 1054 current_expansion_factor_(1), |
| 1073 frequency_collator_(), | 1055 frequency_collator_(), |
| 1074 isolate_(isolate), | 1056 isolate_(isolate), |
| 1075 zone_(zone) { | 1057 zone_(zone) { |
| 1076 accept_ = new(zone) EndNode(EndNode::ACCEPT, zone); | 1058 accept_ = new(zone) EndNode(EndNode::ACCEPT, zone); |
| (...skipping 1032 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2109 flip ? even_label : odd_label); | 2091 flip ? even_label : odd_label); |
| 2110 } | 2092 } |
| 2111 } | 2093 } |
| 2112 | 2094 |
| 2113 | 2095 |
| 2114 static void EmitCharClass(RegExpMacroAssembler* macro_assembler, | 2096 static void EmitCharClass(RegExpMacroAssembler* macro_assembler, |
| 2115 RegExpCharacterClass* cc, bool one_byte, | 2097 RegExpCharacterClass* cc, bool one_byte, |
| 2116 Label* on_failure, int cp_offset, bool check_offset, | 2098 Label* on_failure, int cp_offset, bool check_offset, |
| 2117 bool preloaded, Zone* zone) { | 2099 bool preloaded, Zone* zone) { |
| 2118 ZoneList<CharacterRange>* ranges = cc->ranges(zone); | 2100 ZoneList<CharacterRange>* ranges = cc->ranges(zone); |
| 2119 CharacterRange::Canonicalize(ranges); | 2101 if (!CharacterRange::IsCanonical(ranges)) { |
| 2102 CharacterRange::Canonicalize(ranges); |
| 2103 } |
| 2120 | 2104 |
| 2121 int max_char; | 2105 int max_char; |
| 2122 if (one_byte) { | 2106 if (one_byte) { |
| 2123 max_char = String::kMaxOneByteCharCode; | 2107 max_char = String::kMaxOneByteCharCode; |
| 2124 } else { | 2108 } else { |
| 2125 max_char = String::kMaxUtf16CodeUnit; | 2109 max_char = String::kMaxUtf16CodeUnit; |
| 2126 } | 2110 } |
| 2127 | 2111 |
| 2128 int range_count = ranges->length(); | 2112 int range_count = ranges->length(); |
| 2129 | 2113 |
| (...skipping 21 matching lines...) Expand all Loading... |
| 2151 if (cc->is_negated()) { | 2135 if (cc->is_negated()) { |
| 2152 macro_assembler->GoTo(on_failure); | 2136 macro_assembler->GoTo(on_failure); |
| 2153 } else { | 2137 } else { |
| 2154 // This is a common case hit by non-anchored expressions. | 2138 // This is a common case hit by non-anchored expressions. |
| 2155 if (check_offset) { | 2139 if (check_offset) { |
| 2156 macro_assembler->CheckPosition(cp_offset, on_failure); | 2140 macro_assembler->CheckPosition(cp_offset, on_failure); |
| 2157 } | 2141 } |
| 2158 } | 2142 } |
| 2159 return; | 2143 return; |
| 2160 } | 2144 } |
| 2145 if (last_valid_range == 0 && |
| 2146 !cc->is_negated() && |
| 2147 ranges->at(0).IsEverything(max_char)) { |
| 2148 // This is a common case hit by non-anchored expressions. |
| 2149 if (check_offset) { |
| 2150 macro_assembler->CheckPosition(cp_offset, on_failure); |
| 2151 } |
| 2152 return; |
| 2153 } |
| 2161 | 2154 |
| 2162 if (!preloaded) { | 2155 if (!preloaded) { |
| 2163 macro_assembler->LoadCurrentCharacter(cp_offset, on_failure, check_offset); | 2156 macro_assembler->LoadCurrentCharacter(cp_offset, on_failure, check_offset); |
| 2164 } | 2157 } |
| 2165 | 2158 |
| 2166 if (cc->is_standard(zone) && | 2159 if (cc->is_standard(zone) && |
| 2167 macro_assembler->CheckSpecialCharacterClass(cc->standard_type(), | 2160 macro_assembler->CheckSpecialCharacterClass(cc->standard_type(), |
| 2168 on_failure)) { | 2161 on_failure)) { |
| 2169 return; | 2162 return; |
| 2170 } | 2163 } |
| 2171 | 2164 |
| 2172 | 2165 |
| 2173 // A new list with ascending entries. Each entry is a code unit | 2166 // A new list with ascending entries. Each entry is a code unit |
| 2174 // where there is a boundary between code units that are part of | 2167 // where there is a boundary between code units that are part of |
| 2175 // the class and code units that are not. Normally we insert an | 2168 // the class and code units that are not. Normally we insert an |
| 2176 // entry at zero which goes to the failure label, but if there | 2169 // entry at zero which goes to the failure label, but if there |
| 2177 // was already one there we fall through for success on that entry. | 2170 // was already one there we fall through for success on that entry. |
| 2178 // Subsequent entries have alternating meaning (success/failure). | 2171 // Subsequent entries have alternating meaning (success/failure). |
| (...skipping 619 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2798 // Character is outside Latin-1 completely | 2791 // Character is outside Latin-1 completely |
| 2799 if (converted == 0) return set_replacement(NULL); | 2792 if (converted == 0) return set_replacement(NULL); |
| 2800 // Convert quark to Latin-1 in place. | 2793 // Convert quark to Latin-1 in place. |
| 2801 uint16_t* copy = const_cast<uint16_t*>(quarks.start()); | 2794 uint16_t* copy = const_cast<uint16_t*>(quarks.start()); |
| 2802 copy[j] = converted; | 2795 copy[j] = converted; |
| 2803 } | 2796 } |
| 2804 } else { | 2797 } else { |
| 2805 DCHECK(elm.text_type() == TextElement::CHAR_CLASS); | 2798 DCHECK(elm.text_type() == TextElement::CHAR_CLASS); |
| 2806 RegExpCharacterClass* cc = elm.char_class(); | 2799 RegExpCharacterClass* cc = elm.char_class(); |
| 2807 ZoneList<CharacterRange>* ranges = cc->ranges(zone()); | 2800 ZoneList<CharacterRange>* ranges = cc->ranges(zone()); |
| 2808 CharacterRange::Canonicalize(ranges); | 2801 if (!CharacterRange::IsCanonical(ranges)) { |
| 2802 CharacterRange::Canonicalize(ranges); |
| 2803 } |
| 2809 // Now they are in order so we only need to look at the first. | 2804 // Now they are in order so we only need to look at the first. |
| 2810 int range_count = ranges->length(); | 2805 int range_count = ranges->length(); |
| 2811 if (cc->is_negated()) { | 2806 if (cc->is_negated()) { |
| 2812 if (range_count != 0 && | 2807 if (range_count != 0 && |
| 2813 ranges->at(0).from() == 0 && | 2808 ranges->at(0).from() == 0 && |
| 2814 ranges->at(0).to() >= String::kMaxOneByteCharCode) { | 2809 ranges->at(0).to() >= String::kMaxOneByteCharCode) { |
| 2815 // This will be handled in a later filter. | 2810 // This will be handled in a later filter. |
| 2816 if (ignore_case && RangesContainLatin1Equivalents(ranges)) continue; | 2811 if (ignore_case && RangesContainLatin1Equivalents(ranges)) continue; |
| 2817 return set_replacement(NULL); | 2812 return set_replacement(NULL); |
| 2818 } | 2813 } |
| (...skipping 468 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 3287 bool TextNode::SkipPass(int int_pass, bool ignore_case) { | 3282 bool TextNode::SkipPass(int int_pass, bool ignore_case) { |
| 3288 TextEmitPassType pass = static_cast<TextEmitPassType>(int_pass); | 3283 TextEmitPassType pass = static_cast<TextEmitPassType>(int_pass); |
| 3289 if (ignore_case) { | 3284 if (ignore_case) { |
| 3290 return pass == SIMPLE_CHARACTER_MATCH; | 3285 return pass == SIMPLE_CHARACTER_MATCH; |
| 3291 } else { | 3286 } else { |
| 3292 return pass == NON_LETTER_CHARACTER_MATCH || pass == CASE_CHARACTER_MATCH; | 3287 return pass == NON_LETTER_CHARACTER_MATCH || pass == CASE_CHARACTER_MATCH; |
| 3293 } | 3288 } |
| 3294 } | 3289 } |
| 3295 | 3290 |
| 3296 | 3291 |
| 3297 TextNode* TextNode::CreateForCharacterRanges(Zone* zone, | |
| 3298 ZoneList<CharacterRange>* ranges, | |
| 3299 bool read_backward, | |
| 3300 RegExpNode* on_success) { | |
| 3301 DCHECK_NOT_NULL(ranges); | |
| 3302 ZoneList<TextElement>* elms = new (zone) ZoneList<TextElement>(1, zone); | |
| 3303 elms->Add( | |
| 3304 TextElement::CharClass(new (zone) RegExpCharacterClass(ranges, false)), | |
| 3305 zone); | |
| 3306 return new (zone) TextNode(elms, read_backward, on_success); | |
| 3307 } | |
| 3308 | |
| 3309 | |
| 3310 TextNode* TextNode::CreateForSurrogatePair(Zone* zone, CharacterRange lead, | |
| 3311 CharacterRange trail, | |
| 3312 bool read_backward, | |
| 3313 RegExpNode* on_success) { | |
| 3314 ZoneList<CharacterRange>* lead_ranges = CharacterRange::List(zone, lead); | |
| 3315 ZoneList<CharacterRange>* trail_ranges = CharacterRange::List(zone, trail); | |
| 3316 ZoneList<TextElement>* elms = new (zone) ZoneList<TextElement>(2, zone); | |
| 3317 elms->Add(TextElement::CharClass( | |
| 3318 new (zone) RegExpCharacterClass(lead_ranges, false)), | |
| 3319 zone); | |
| 3320 elms->Add(TextElement::CharClass( | |
| 3321 new (zone) RegExpCharacterClass(trail_ranges, false)), | |
| 3322 zone); | |
| 3323 return new (zone) TextNode(elms, read_backward, on_success); | |
| 3324 } | |
| 3325 | |
| 3326 | |
| 3327 // This generates the code to match a text node. A text node can contain | 3292 // This generates the code to match a text node. A text node can contain |
| 3328 // straight character sequences (possibly to be matched in a case-independent | 3293 // straight character sequences (possibly to be matched in a case-independent |
| 3329 // way) and character classes. For efficiency we do not do this in a single | 3294 // way) and character classes. For efficiency we do not do this in a single |
| 3330 // pass from left to right. Instead we pass over the text node several times, | 3295 // pass from left to right. Instead we pass over the text node several times, |
| 3331 // emitting code for some character positions every time. See the comment on | 3296 // emitting code for some character positions every time. See the comment on |
| 3332 // TextEmitPass for details. | 3297 // TextEmitPass for details. |
| 3333 void TextNode::Emit(RegExpCompiler* compiler, Trace* trace) { | 3298 void TextNode::Emit(RegExpCompiler* compiler, Trace* trace) { |
| 3334 LimitResult limit_result = LimitVersions(compiler, trace); | 3299 LimitResult limit_result = LimitVersions(compiler, trace); |
| 3335 if (limit_result == DONE) return; | 3300 if (limit_result == DONE) return; |
| 3336 DCHECK(limit_result == CONTINUE); | 3301 DCHECK(limit_result == CONTINUE); |
| (...skipping 96 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 3433 | 3398 |
| 3434 | 3399 |
| 3435 RegExpNode* TextNode::GetSuccessorOfOmnivorousTextNode( | 3400 RegExpNode* TextNode::GetSuccessorOfOmnivorousTextNode( |
| 3436 RegExpCompiler* compiler) { | 3401 RegExpCompiler* compiler) { |
| 3437 if (read_backward()) return NULL; | 3402 if (read_backward()) return NULL; |
| 3438 if (elements()->length() != 1) return NULL; | 3403 if (elements()->length() != 1) return NULL; |
| 3439 TextElement elm = elements()->at(0); | 3404 TextElement elm = elements()->at(0); |
| 3440 if (elm.text_type() != TextElement::CHAR_CLASS) return NULL; | 3405 if (elm.text_type() != TextElement::CHAR_CLASS) return NULL; |
| 3441 RegExpCharacterClass* node = elm.char_class(); | 3406 RegExpCharacterClass* node = elm.char_class(); |
| 3442 ZoneList<CharacterRange>* ranges = node->ranges(zone()); | 3407 ZoneList<CharacterRange>* ranges = node->ranges(zone()); |
| 3443 CharacterRange::Canonicalize(ranges); | 3408 if (!CharacterRange::IsCanonical(ranges)) { |
| 3409 CharacterRange::Canonicalize(ranges); |
| 3410 } |
| 3444 if (node->is_negated()) { | 3411 if (node->is_negated()) { |
| 3445 return ranges->length() == 0 ? on_success() : NULL; | 3412 return ranges->length() == 0 ? on_success() : NULL; |
| 3446 } | 3413 } |
| 3447 if (ranges->length() != 1) return NULL; | 3414 if (ranges->length() != 1) return NULL; |
| 3448 uint32_t max_char; | 3415 uint32_t max_char; |
| 3449 if (compiler->one_byte()) { | 3416 if (compiler->one_byte()) { |
| 3450 max_char = String::kMaxOneByteCharCode; | 3417 max_char = String::kMaxOneByteCharCode; |
| 3451 } else { | 3418 } else { |
| 3452 max_char = String::kMaxUtf16CodeUnit; | 3419 max_char = String::kMaxUtf16CodeUnit; |
| 3453 } | 3420 } |
| (...skipping 126 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 3580 return alt_gens_[i]; | 3547 return alt_gens_[i]; |
| 3581 } | 3548 } |
| 3582 | 3549 |
| 3583 private: | 3550 private: |
| 3584 static const int kAFew = 10; | 3551 static const int kAFew = 10; |
| 3585 ZoneList<AlternativeGeneration*> alt_gens_; | 3552 ZoneList<AlternativeGeneration*> alt_gens_; |
| 3586 AlternativeGeneration a_few_alt_gens_[kAFew]; | 3553 AlternativeGeneration a_few_alt_gens_[kAFew]; |
| 3587 }; | 3554 }; |
| 3588 | 3555 |
| 3589 | 3556 |
| 3590 static const uc32 kLeadSurrogateStart = 0xd800; | |
| 3591 static const uc32 kLeadSurrogateEnd = 0xdbff; | |
| 3592 static const uc32 kTrailSurrogateStart = 0xdc00; | |
| 3593 static const uc32 kTrailSurrogateEnd = 0xdfff; | |
| 3594 static const uc32 kNonBmpStart = 0x10000; | |
| 3595 static const uc32 kNonBmpEnd = 0x10ffff; | |
| 3596 static const uc32 kRangeEndMarker = 0x110000; | |
| 3597 | |
| 3598 // The '2' variant is has inclusive from and exclusive to. | 3557 // The '2' variant is has inclusive from and exclusive to. |
| 3599 // This covers \s as defined in ECMA-262 5.1, 15.10.2.12, | 3558 // This covers \s as defined in ECMA-262 5.1, 15.10.2.12, |
| 3600 // which include WhiteSpace (7.2) or LineTerminator (7.3) values. | 3559 // which include WhiteSpace (7.2) or LineTerminator (7.3) values. |
| 3601 static const int kSpaceRanges[] = { | 3560 static const int kSpaceRanges[] = { '\t', '\r' + 1, ' ', ' ' + 1, |
| 3602 '\t', '\r' + 1, ' ', ' ' + 1, 0x00A0, 0x00A1, 0x1680, 0x1681, | 3561 0x00A0, 0x00A1, 0x1680, 0x1681, 0x180E, 0x180F, 0x2000, 0x200B, |
| 3603 0x180E, 0x180F, 0x2000, 0x200B, 0x2028, 0x202A, 0x202F, 0x2030, | 3562 0x2028, 0x202A, 0x202F, 0x2030, 0x205F, 0x2060, 0x3000, 0x3001, |
| 3604 0x205F, 0x2060, 0x3000, 0x3001, 0xFEFF, 0xFF00, kRangeEndMarker}; | 3563 0xFEFF, 0xFF00, 0x10000 }; |
| 3605 static const int kSpaceRangeCount = arraysize(kSpaceRanges); | 3564 static const int kSpaceRangeCount = arraysize(kSpaceRanges); |
| 3606 | 3565 |
| 3607 static const int kWordRanges[] = { | 3566 static const int kWordRanges[] = { |
| 3608 '0', '9' + 1, 'A', 'Z' + 1, '_', '_' + 1, 'a', 'z' + 1, kRangeEndMarker}; | 3567 '0', '9' + 1, 'A', 'Z' + 1, '_', '_' + 1, 'a', 'z' + 1, 0x10000 }; |
| 3609 static const int kWordRangeCount = arraysize(kWordRanges); | 3568 static const int kWordRangeCount = arraysize(kWordRanges); |
| 3610 static const int kDigitRanges[] = {'0', '9' + 1, kRangeEndMarker}; | 3569 static const int kDigitRanges[] = { '0', '9' + 1, 0x10000 }; |
| 3611 static const int kDigitRangeCount = arraysize(kDigitRanges); | 3570 static const int kDigitRangeCount = arraysize(kDigitRanges); |
| 3612 static const int kSurrogateRanges[] = { | 3571 static const int kSurrogateRanges[] = { 0xd800, 0xe000, 0x10000 }; |
| 3613 kLeadSurrogateStart, kLeadSurrogateStart + 1, kRangeEndMarker}; | |
| 3614 static const int kSurrogateRangeCount = arraysize(kSurrogateRanges); | 3572 static const int kSurrogateRangeCount = arraysize(kSurrogateRanges); |
| 3615 static const int kLineTerminatorRanges[] = { | 3573 static const int kLineTerminatorRanges[] = { 0x000A, 0x000B, 0x000D, 0x000E, |
| 3616 0x000A, 0x000B, 0x000D, 0x000E, 0x2028, 0x202A, kRangeEndMarker}; | 3574 0x2028, 0x202A, 0x10000 }; |
| 3617 static const int kLineTerminatorRangeCount = arraysize(kLineTerminatorRanges); | 3575 static const int kLineTerminatorRangeCount = arraysize(kLineTerminatorRanges); |
| 3618 | 3576 |
| 3577 |
| 3619 void BoyerMoorePositionInfo::Set(int character) { | 3578 void BoyerMoorePositionInfo::Set(int character) { |
| 3620 SetInterval(Interval(character, character)); | 3579 SetInterval(Interval(character, character)); |
| 3621 } | 3580 } |
| 3622 | 3581 |
| 3623 | 3582 |
| 3624 void BoyerMoorePositionInfo::SetInterval(const Interval& interval) { | 3583 void BoyerMoorePositionInfo::SetInterval(const Interval& interval) { |
| 3625 s_ = AddRange(s_, kSpaceRanges, kSpaceRangeCount, interval); | 3584 s_ = AddRange(s_, kSpaceRanges, kSpaceRangeCount, interval); |
| 3626 w_ = AddRange(w_, kWordRanges, kWordRangeCount, interval); | 3585 w_ = AddRange(w_, kWordRanges, kWordRangeCount, interval); |
| 3627 d_ = AddRange(d_, kDigitRanges, kDigitRangeCount, interval); | 3586 d_ = AddRange(d_, kDigitRanges, kDigitRangeCount, interval); |
| 3628 surrogate_ = | 3587 surrogate_ = |
| (...skipping 1137 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 4766 RegExpNode* RegExpText::ToNode(RegExpCompiler* compiler, | 4725 RegExpNode* RegExpText::ToNode(RegExpCompiler* compiler, |
| 4767 RegExpNode* on_success) { | 4726 RegExpNode* on_success) { |
| 4768 return new (compiler->zone()) | 4727 return new (compiler->zone()) |
| 4769 TextNode(elements(), compiler->read_backward(), on_success); | 4728 TextNode(elements(), compiler->read_backward(), on_success); |
| 4770 } | 4729 } |
| 4771 | 4730 |
| 4772 | 4731 |
| 4773 static bool CompareInverseRanges(ZoneList<CharacterRange>* ranges, | 4732 static bool CompareInverseRanges(ZoneList<CharacterRange>* ranges, |
| 4774 const int* special_class, | 4733 const int* special_class, |
| 4775 int length) { | 4734 int length) { |
| 4776 length--; // Remove final marker. | 4735 length--; // Remove final 0x10000. |
| 4777 DCHECK(special_class[length] == kRangeEndMarker); | 4736 DCHECK(special_class[length] == 0x10000); |
| 4778 DCHECK(ranges->length() != 0); | 4737 DCHECK(ranges->length() != 0); |
| 4779 DCHECK(length != 0); | 4738 DCHECK(length != 0); |
| 4780 DCHECK(special_class[0] != 0); | 4739 DCHECK(special_class[0] != 0); |
| 4781 if (ranges->length() != (length >> 1) + 1) { | 4740 if (ranges->length() != (length >> 1) + 1) { |
| 4782 return false; | 4741 return false; |
| 4783 } | 4742 } |
| 4784 CharacterRange range = ranges->at(0); | 4743 CharacterRange range = ranges->at(0); |
| 4785 if (range.from() != 0) { | 4744 if (range.from() != 0) { |
| 4786 return false; | 4745 return false; |
| 4787 } | 4746 } |
| 4788 for (int i = 0; i < length; i += 2) { | 4747 for (int i = 0; i < length; i += 2) { |
| 4789 if (special_class[i] != (range.to() + 1)) { | 4748 if (special_class[i] != (range.to() + 1)) { |
| 4790 return false; | 4749 return false; |
| 4791 } | 4750 } |
| 4792 range = ranges->at((i >> 1) + 1); | 4751 range = ranges->at((i >> 1) + 1); |
| 4793 if (special_class[i+1] != range.from()) { | 4752 if (special_class[i+1] != range.from()) { |
| 4794 return false; | 4753 return false; |
| 4795 } | 4754 } |
| 4796 } | 4755 } |
| 4797 if (range.to() != 0xffff) { | 4756 if (range.to() != 0xffff) { |
| 4798 return false; | 4757 return false; |
| 4799 } | 4758 } |
| 4800 return true; | 4759 return true; |
| 4801 } | 4760 } |
| 4802 | 4761 |
| 4803 | 4762 |
| 4804 static bool CompareRanges(ZoneList<CharacterRange>* ranges, | 4763 static bool CompareRanges(ZoneList<CharacterRange>* ranges, |
| 4805 const int* special_class, | 4764 const int* special_class, |
| 4806 int length) { | 4765 int length) { |
| 4807 length--; // Remove final marker. | 4766 length--; // Remove final 0x10000. |
| 4808 DCHECK(special_class[length] == kRangeEndMarker); | 4767 DCHECK(special_class[length] == 0x10000); |
| 4809 if (ranges->length() * 2 != length) { | 4768 if (ranges->length() * 2 != length) { |
| 4810 return false; | 4769 return false; |
| 4811 } | 4770 } |
| 4812 for (int i = 0; i < length; i += 2) { | 4771 for (int i = 0; i < length; i += 2) { |
| 4813 CharacterRange range = ranges->at(i >> 1); | 4772 CharacterRange range = ranges->at(i >> 1); |
| 4814 if (range.from() != special_class[i] || | 4773 if (range.from() != special_class[i] || |
| 4815 range.to() != special_class[i + 1] - 1) { | 4774 range.to() != special_class[i + 1] - 1) { |
| 4816 return false; | 4775 return false; |
| 4817 } | 4776 } |
| 4818 } | 4777 } |
| (...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 4854 return true; | 4813 return true; |
| 4855 } | 4814 } |
| 4856 if (CompareInverseRanges(set_.ranges(zone), kWordRanges, kWordRangeCount)) { | 4815 if (CompareInverseRanges(set_.ranges(zone), kWordRanges, kWordRangeCount)) { |
| 4857 set_.set_standard_set_type('W'); | 4816 set_.set_standard_set_type('W'); |
| 4858 return true; | 4817 return true; |
| 4859 } | 4818 } |
| 4860 return false; | 4819 return false; |
| 4861 } | 4820 } |
| 4862 | 4821 |
| 4863 | 4822 |
| 4864 bool RegExpCharacterClass::NeedsDesugaringForUnicode(Zone* zone) { | |
| 4865 ZoneList<CharacterRange>* ranges = this->ranges(zone); | |
| 4866 CharacterRange::Canonicalize(ranges); | |
| 4867 for (int i = ranges->length() - 1; i >= 0; i--) { | |
| 4868 uc32 from = ranges->at(i).from(); | |
| 4869 uc32 to = ranges->at(i).to(); | |
| 4870 // Check for non-BMP characters. | |
| 4871 if (to >= kNonBmpStart) return true; | |
| 4872 // Check for lone surrogates. | |
| 4873 if (from <= kTrailSurrogateEnd && to >= kLeadSurrogateStart) return true; | |
| 4874 } | |
| 4875 return false; | |
| 4876 } | |
| 4877 | |
| 4878 | |
| 4879 UnicodeRangeSplitter::UnicodeRangeSplitter(Zone* zone, | |
| 4880 ZoneList<CharacterRange>* base) | |
| 4881 : zone_(zone), | |
| 4882 table_(zone), | |
| 4883 bmp_(nullptr), | |
| 4884 lead_surrogates_(nullptr), | |
| 4885 trail_surrogates_(nullptr), | |
| 4886 non_bmp_(nullptr) { | |
| 4887 // The unicode range splitter categorizes given character ranges into: | |
| 4888 // - Code points from the BMP representable by one code unit. | |
| 4889 // - Code points outside the BMP that need to be split into surrogate pairs. | |
| 4890 // - Lone lead surrogates. | |
| 4891 // - Lone trail surrogates. | |
| 4892 // Lone surrogates are valid code points, even though no actual characters. | |
| 4893 // They require special matching to make sure we do not split surrogate pairs. | |
| 4894 // We use the dispatch table to accomplish this. The base range is split up | |
| 4895 // by the table by the overlay ranges, and the Call callback is used to | |
| 4896 // filter and collect ranges for each category. | |
| 4897 for (int i = 0; i < base->length(); i++) { | |
| 4898 table_.AddRange(base->at(i), kBase, zone_); | |
| 4899 } | |
| 4900 // Add overlay ranges. | |
| 4901 table_.AddRange(CharacterRange(0, kLeadSurrogateStart - 1), kBmpCodePoints, | |
| 4902 zone_); | |
| 4903 table_.AddRange(CharacterRange(kLeadSurrogateStart, kLeadSurrogateEnd), | |
| 4904 kLeadSurrogates, zone_); | |
| 4905 table_.AddRange(CharacterRange(kTrailSurrogateStart, kTrailSurrogateEnd), | |
| 4906 kTrailSurrogates, zone_); | |
| 4907 table_.AddRange(CharacterRange(kTrailSurrogateEnd, kNonBmpStart - 1), | |
| 4908 kBmpCodePoints, zone_); | |
| 4909 table_.AddRange(CharacterRange(kNonBmpStart, kNonBmpEnd), kNonBmpCodePoints, | |
| 4910 zone_); | |
| 4911 table_.ForEach(this); | |
| 4912 } | |
| 4913 | |
| 4914 | |
| 4915 void UnicodeRangeSplitter::Call(uc32 from, DispatchTable::Entry entry) { | |
| 4916 OutSet* outset = entry.out_set(); | |
| 4917 if (!outset->Get(kBase)) return; | |
| 4918 ZoneList<CharacterRange>** target = NULL; | |
| 4919 if (outset->Get(kBmpCodePoints)) { | |
| 4920 target = &bmp_; | |
| 4921 } else if (outset->Get(kLeadSurrogates)) { | |
| 4922 target = &lead_surrogates_; | |
| 4923 } else if (outset->Get(kTrailSurrogates)) { | |
| 4924 target = &trail_surrogates_; | |
| 4925 } else { | |
| 4926 DCHECK(outset->Get(kNonBmpCodePoints)); | |
| 4927 target = &non_bmp_; | |
| 4928 } | |
| 4929 if (*target == NULL) *target = new (zone_) ZoneList<CharacterRange>(2, zone_); | |
| 4930 (*target)->Add(CharacterRange::Range(entry.from(), entry.to()), zone_); | |
| 4931 } | |
| 4932 | |
| 4933 | |
| 4934 void AddBmpCharacters(RegExpCompiler* compiler, ChoiceNode* result, | |
| 4935 RegExpNode* on_success, UnicodeRangeSplitter* splitter) { | |
| 4936 ZoneList<CharacterRange>* bmp = splitter->bmp(); | |
| 4937 if (bmp == nullptr) return; | |
| 4938 result->AddAlternative(GuardedAlternative(TextNode::CreateForCharacterRanges( | |
| 4939 compiler->zone(), bmp, compiler->read_backward(), on_success))); | |
| 4940 } | |
| 4941 | |
| 4942 | |
| 4943 void AddNonBmpSurrogatePairs(RegExpCompiler* compiler, ChoiceNode* result, | |
| 4944 RegExpNode* on_success, | |
| 4945 UnicodeRangeSplitter* splitter) { | |
| 4946 ZoneList<CharacterRange>* non_bmp = splitter->non_bmp(); | |
| 4947 if (non_bmp == nullptr) return; | |
| 4948 DCHECK(compiler->unicode()); | |
| 4949 DCHECK(!compiler->one_byte()); | |
| 4950 Zone* zone = compiler->zone(); | |
| 4951 CharacterRange::Canonicalize(non_bmp); | |
| 4952 for (int i = 0; i < non_bmp->length(); i++) { | |
| 4953 // Match surrogate pair. | |
| 4954 // E.g. [\u10005-\u11005] becomes | |
| 4955 // \ud800[\udc05-\udfff]| | |
| 4956 // [\ud801-\ud803][\udc00-\udfff]| | |
| 4957 // \ud804[\udc00-\udc05] | |
| 4958 uc32 from = non_bmp->at(i).from(); | |
| 4959 uc32 to = non_bmp->at(i).to(); | |
| 4960 uc16 from_l = unibrow::Utf16::LeadSurrogate(from); | |
| 4961 uc16 from_t = unibrow::Utf16::TrailSurrogate(from); | |
| 4962 uc16 to_l = unibrow::Utf16::LeadSurrogate(to); | |
| 4963 uc16 to_t = unibrow::Utf16::TrailSurrogate(to); | |
| 4964 if (from_l == to_l) { | |
| 4965 // The lead surrogate is the same. | |
| 4966 result->AddAlternative( | |
| 4967 GuardedAlternative(TextNode::CreateForSurrogatePair( | |
| 4968 zone, CharacterRange::Singleton(from_l), | |
| 4969 CharacterRange::Range(from_t, to_t), compiler->read_backward(), | |
| 4970 on_success))); | |
| 4971 } else { | |
| 4972 if (from_t != kTrailSurrogateStart) { | |
| 4973 // Add [from_l][from_t-\udfff] | |
| 4974 result->AddAlternative( | |
| 4975 GuardedAlternative(TextNode::CreateForSurrogatePair( | |
| 4976 zone, CharacterRange::Singleton(from_l), | |
| 4977 CharacterRange::Range(from_t, kTrailSurrogateEnd), | |
| 4978 compiler->read_backward(), on_success))); | |
| 4979 from_l++; | |
| 4980 } | |
| 4981 if (to_t != kTrailSurrogateEnd) { | |
| 4982 // Add [to_l][\udc00-to_t] | |
| 4983 result->AddAlternative( | |
| 4984 GuardedAlternative(TextNode::CreateForSurrogatePair( | |
| 4985 zone, CharacterRange::Singleton(to_l), | |
| 4986 CharacterRange::Range(kTrailSurrogateStart, to_t), | |
| 4987 compiler->read_backward(), on_success))); | |
| 4988 to_l--; | |
| 4989 } | |
| 4990 if (from_l <= to_l) { | |
| 4991 // Add [from_l-to_l][\udc00-\udfff] | |
| 4992 result->AddAlternative( | |
| 4993 GuardedAlternative(TextNode::CreateForSurrogatePair( | |
| 4994 zone, CharacterRange::Range(from_l, to_l), | |
| 4995 CharacterRange::Range(kTrailSurrogateStart, kTrailSurrogateEnd), | |
| 4996 compiler->read_backward(), on_success))); | |
| 4997 } | |
| 4998 } | |
| 4999 } | |
| 5000 } | |
| 5001 | |
| 5002 | |
| 5003 RegExpNode* NegativeLookaroundAgainstReadDirectionAndMatch( | |
| 5004 RegExpCompiler* compiler, ZoneList<CharacterRange>* lookbehind, | |
| 5005 ZoneList<CharacterRange>* match, RegExpNode* on_success, | |
| 5006 bool read_backward) { | |
| 5007 Zone* zone = compiler->zone(); | |
| 5008 RegExpNode* match_node = TextNode::CreateForCharacterRanges( | |
| 5009 zone, match, read_backward, on_success); | |
| 5010 int stack_register = compiler->UnicodeLookaroundStackRegister(); | |
| 5011 int position_register = compiler->UnicodeLookaroundPositionRegister(); | |
| 5012 RegExpLookaround::Builder lookaround(false, match_node, stack_register, | |
| 5013 position_register); | |
| 5014 RegExpNode* negative_match = TextNode::CreateForCharacterRanges( | |
| 5015 zone, lookbehind, !read_backward, lookaround.on_match_success()); | |
| 5016 return lookaround.ForMatch(negative_match); | |
| 5017 } | |
| 5018 | |
| 5019 | |
| 5020 RegExpNode* MatchAndNegativeLookaroundInReadDirection( | |
| 5021 RegExpCompiler* compiler, ZoneList<CharacterRange>* match, | |
| 5022 ZoneList<CharacterRange>* lookahead, RegExpNode* on_success, | |
| 5023 bool read_backward) { | |
| 5024 Zone* zone = compiler->zone(); | |
| 5025 int stack_register = compiler->UnicodeLookaroundStackRegister(); | |
| 5026 int position_register = compiler->UnicodeLookaroundPositionRegister(); | |
| 5027 RegExpLookaround::Builder lookaround(false, on_success, stack_register, | |
| 5028 position_register); | |
| 5029 RegExpNode* negative_match = TextNode::CreateForCharacterRanges( | |
| 5030 zone, lookahead, read_backward, lookaround.on_match_success()); | |
| 5031 return TextNode::CreateForCharacterRanges( | |
| 5032 zone, match, read_backward, lookaround.ForMatch(negative_match)); | |
| 5033 } | |
| 5034 | |
| 5035 | |
| 5036 void AddLoneLeadSurrogates(RegExpCompiler* compiler, ChoiceNode* result, | |
| 5037 RegExpNode* on_success, | |
| 5038 UnicodeRangeSplitter* splitter) { | |
| 5039 ZoneList<CharacterRange>* lead_surrogates = splitter->lead_surrogates(); | |
| 5040 if (lead_surrogates == nullptr) return; | |
| 5041 Zone* zone = compiler->zone(); | |
| 5042 // E.g. \ud801 becomes \ud801(?![\udc00-\udfff]). | |
| 5043 ZoneList<CharacterRange>* trail_surrogates = | |
| 5044 new (zone) ZoneList<CharacterRange>(1, zone); | |
| 5045 trail_surrogates->Add( | |
| 5046 CharacterRange::Range(kTrailSurrogateStart, kTrailSurrogateEnd), zone); | |
| 5047 | |
| 5048 RegExpNode* match = | |
| 5049 compiler->read_backward() | |
| 5050 // Reading backward. Assert that reading forward, there is no trail | |
| 5051 // surrogate, and then backward match the lead surrogate. | |
| 5052 ? NegativeLookaroundAgainstReadDirectionAndMatch( | |
| 5053 compiler, trail_surrogates, lead_surrogates, on_success, true) | |
| 5054 // Reading forward. Forwrad match the lead surrogate and assert that | |
| 5055 // no | |
| 5056 // trail surrogate follows. | |
| 5057 : MatchAndNegativeLookaroundInReadDirection( | |
| 5058 compiler, lead_surrogates, trail_surrogates, on_success, false); | |
| 5059 result->AddAlternative(GuardedAlternative(match)); | |
| 5060 } | |
| 5061 | |
| 5062 | |
| 5063 void AddLoneTrailSurrogates(RegExpCompiler* compiler, ChoiceNode* result, | |
| 5064 RegExpNode* on_success, | |
| 5065 UnicodeRangeSplitter* splitter) { | |
| 5066 ZoneList<CharacterRange>* trail_surrogates = splitter->trail_surrogates(); | |
| 5067 if (trail_surrogates == nullptr) return; | |
| 5068 Zone* zone = compiler->zone(); | |
| 5069 // E.g. \udc01 becomes (?<![\ud800-\udbff])\udc01 | |
| 5070 ZoneList<CharacterRange>* lead_surrogates = | |
| 5071 new (zone) ZoneList<CharacterRange>(1, zone); | |
| 5072 lead_surrogates->Add( | |
| 5073 CharacterRange::Range(kLeadSurrogateStart, kLeadSurrogateEnd), zone); | |
| 5074 | |
| 5075 RegExpNode* match = | |
| 5076 compiler->read_backward() | |
| 5077 // Reading backward. Backward match the trail surrogate and assert | |
| 5078 // that no lead surrogate precedes it. | |
| 5079 ? MatchAndNegativeLookaroundInReadDirection( | |
| 5080 compiler, trail_surrogates, lead_surrogates, on_success, true) | |
| 5081 // Reading forward. Assert that reading backward, there is no lead | |
| 5082 // surrogate, and then forward match the trail surrogate. | |
| 5083 : NegativeLookaroundAgainstReadDirectionAndMatch( | |
| 5084 compiler, lead_surrogates, trail_surrogates, on_success, false); | |
| 5085 result->AddAlternative(GuardedAlternative(match)); | |
| 5086 } | |
| 5087 | |
| 5088 | |
| 5089 RegExpNode* RegExpCharacterClass::ToNode(RegExpCompiler* compiler, | 4823 RegExpNode* RegExpCharacterClass::ToNode(RegExpCompiler* compiler, |
| 5090 RegExpNode* on_success) { | 4824 RegExpNode* on_success) { |
| 5091 set_.Canonicalize(); | 4825 return new (compiler->zone()) |
| 5092 Zone* zone = compiler->zone(); | 4826 TextNode(this, compiler->read_backward(), on_success); |
| 5093 ZoneList<CharacterRange>* ranges = this->ranges(zone); | |
| 5094 if (compiler->unicode() && !compiler->one_byte()) { | |
| 5095 if (is_negated()) { | |
| 5096 ZoneList<CharacterRange>* negated = | |
| 5097 new (zone) ZoneList<CharacterRange>(2, zone); | |
| 5098 CharacterRange::Negate(ranges, negated, zone); | |
| 5099 ranges = negated; | |
| 5100 } | |
| 5101 if (ranges->length() == 0) { | |
| 5102 // No matches possible. | |
| 5103 return new (zone) EndNode(EndNode::BACKTRACK, zone); | |
| 5104 } | |
| 5105 UnicodeRangeSplitter splitter(zone, ranges); | |
| 5106 ChoiceNode* result = new (compiler->zone()) ChoiceNode(2, compiler->zone()); | |
| 5107 AddBmpCharacters(compiler, result, on_success, &splitter); | |
| 5108 AddNonBmpSurrogatePairs(compiler, result, on_success, &splitter); | |
| 5109 AddLoneLeadSurrogates(compiler, result, on_success, &splitter); | |
| 5110 AddLoneTrailSurrogates(compiler, result, on_success, &splitter); | |
| 5111 return result; | |
| 5112 } else { | |
| 5113 return new (zone) TextNode(this, compiler->read_backward(), on_success); | |
| 5114 } | |
| 5115 } | 4827 } |
| 5116 | 4828 |
| 5117 | 4829 |
| 5118 int CompareFirstChar(RegExpTree* const* a, RegExpTree* const* b) { | 4830 int CompareFirstChar(RegExpTree* const* a, RegExpTree* const* b) { |
| 5119 RegExpAtom* atom1 = (*a)->AsAtom(); | 4831 RegExpAtom* atom1 = (*a)->AsAtom(); |
| 5120 RegExpAtom* atom2 = (*b)->AsAtom(); | 4832 RegExpAtom* atom2 = (*b)->AsAtom(); |
| 5121 uc16 character1 = atom1->data().at(0); | 4833 uc16 character1 = atom1->data().at(0); |
| 5122 uc16 character2 = atom2->data().at(0); | 4834 uc16 character2 = atom2->data().at(0); |
| 5123 if (character1 < character2) return -1; | 4835 if (character1 < character2) return -1; |
| 5124 if (character1 > character2) return 1; | 4836 if (character1 > character2) return 1; |
| (...skipping 494 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 5619 compiler->read_backward(), on_success); | 5331 compiler->read_backward(), on_success); |
| 5620 } | 5332 } |
| 5621 | 5333 |
| 5622 | 5334 |
| 5623 RegExpNode* RegExpEmpty::ToNode(RegExpCompiler* compiler, | 5335 RegExpNode* RegExpEmpty::ToNode(RegExpCompiler* compiler, |
| 5624 RegExpNode* on_success) { | 5336 RegExpNode* on_success) { |
| 5625 return on_success; | 5337 return on_success; |
| 5626 } | 5338 } |
| 5627 | 5339 |
| 5628 | 5340 |
| 5629 RegExpLookaround::Builder::Builder(bool is_positive, RegExpNode* on_success, | |
| 5630 int stack_pointer_register, | |
| 5631 int position_register, | |
| 5632 int capture_register_count, | |
| 5633 int capture_register_start) | |
| 5634 : is_positive_(is_positive), | |
| 5635 on_success_(on_success), | |
| 5636 stack_pointer_register_(stack_pointer_register), | |
| 5637 position_register_(position_register) { | |
| 5638 if (is_positive_) { | |
| 5639 on_match_success_ = ActionNode::PositiveSubmatchSuccess( | |
| 5640 stack_pointer_register, position_register, capture_register_count, | |
| 5641 capture_register_start, on_success_); | |
| 5642 } else { | |
| 5643 Zone* zone = on_success_->zone(); | |
| 5644 on_match_success_ = new (zone) NegativeSubmatchSuccess( | |
| 5645 stack_pointer_register, position_register, capture_register_count, | |
| 5646 capture_register_start, zone); | |
| 5647 } | |
| 5648 } | |
| 5649 | |
| 5650 | |
| 5651 RegExpNode* RegExpLookaround::Builder::ForMatch(RegExpNode* match) { | |
| 5652 if (is_positive_) { | |
| 5653 return ActionNode::BeginSubmatch(stack_pointer_register_, | |
| 5654 position_register_, match); | |
| 5655 } else { | |
| 5656 Zone* zone = on_success_->zone(); | |
| 5657 // We use a ChoiceNode to represent the negative lookaround. The first | |
| 5658 // alternative is the negative match. On success, the end node backtracks. | |
| 5659 // On failure, the second alternative is tried and leads to success. | |
| 5660 // NegativeLookaheadChoiceNode is a special ChoiceNode that ignores the | |
| 5661 // first exit when calculating quick checks. | |
| 5662 ChoiceNode* choice_node = new (zone) NegativeLookaroundChoiceNode( | |
| 5663 GuardedAlternative(match), GuardedAlternative(on_success_), zone); | |
| 5664 return ActionNode::BeginSubmatch(stack_pointer_register_, | |
| 5665 position_register_, choice_node); | |
| 5666 } | |
| 5667 } | |
| 5668 | |
| 5669 | |
| 5670 RegExpNode* RegExpLookaround::ToNode(RegExpCompiler* compiler, | 5341 RegExpNode* RegExpLookaround::ToNode(RegExpCompiler* compiler, |
| 5671 RegExpNode* on_success) { | 5342 RegExpNode* on_success) { |
| 5672 int stack_pointer_register = compiler->AllocateRegister(); | 5343 int stack_pointer_register = compiler->AllocateRegister(); |
| 5673 int position_register = compiler->AllocateRegister(); | 5344 int position_register = compiler->AllocateRegister(); |
| 5674 | 5345 |
| 5675 const int registers_per_capture = 2; | 5346 const int registers_per_capture = 2; |
| 5676 const int register_of_first_capture = 2; | 5347 const int register_of_first_capture = 2; |
| 5677 int register_count = capture_count_ * registers_per_capture; | 5348 int register_count = capture_count_ * registers_per_capture; |
| 5678 int register_start = | 5349 int register_start = |
| 5679 register_of_first_capture + capture_from_ * registers_per_capture; | 5350 register_of_first_capture + capture_from_ * registers_per_capture; |
| 5680 | 5351 |
| 5681 RegExpNode* result; | 5352 RegExpNode* result; |
| 5682 bool was_reading_backward = compiler->read_backward(); | 5353 bool was_reading_backward = compiler->read_backward(); |
| 5683 compiler->set_read_backward(type() == LOOKBEHIND); | 5354 compiler->set_read_backward(type() == LOOKBEHIND); |
| 5684 Builder builder(is_positive(), on_success, stack_pointer_register, | 5355 if (is_positive()) { |
| 5685 position_register, register_count, register_start); | 5356 result = ActionNode::BeginSubmatch( |
| 5686 RegExpNode* match = body_->ToNode(compiler, builder.on_match_success()); | 5357 stack_pointer_register, position_register, |
| 5687 result = builder.ForMatch(match); | 5358 body()->ToNode(compiler, |
| 5359 ActionNode::PositiveSubmatchSuccess( |
| 5360 stack_pointer_register, position_register, |
| 5361 register_count, register_start, on_success))); |
| 5362 } else { |
| 5363 // We use a ChoiceNode for a negative lookahead because it has most of |
| 5364 // the characteristics we need. It has the body of the lookahead as its |
| 5365 // first alternative and the expression after the lookahead of the second |
| 5366 // alternative. If the first alternative succeeds then the |
| 5367 // NegativeSubmatchSuccess will unwind the stack including everything the |
| 5368 // choice node set up and backtrack. If the first alternative fails then |
| 5369 // the second alternative is tried, which is exactly the desired result |
| 5370 // for a negative lookahead. The NegativeLookaheadChoiceNode is a special |
| 5371 // ChoiceNode that knows to ignore the first exit when calculating quick |
| 5372 // checks. |
| 5373 Zone* zone = compiler->zone(); |
| 5374 |
| 5375 GuardedAlternative body_alt( |
| 5376 body()->ToNode(compiler, new (zone) NegativeSubmatchSuccess( |
| 5377 stack_pointer_register, position_register, |
| 5378 register_count, register_start, zone))); |
| 5379 ChoiceNode* choice_node = new (zone) NegativeLookaroundChoiceNode( |
| 5380 body_alt, GuardedAlternative(on_success), zone); |
| 5381 result = ActionNode::BeginSubmatch(stack_pointer_register, |
| 5382 position_register, choice_node); |
| 5383 } |
| 5688 compiler->set_read_backward(was_reading_backward); | 5384 compiler->set_read_backward(was_reading_backward); |
| 5689 return result; | 5385 return result; |
| 5690 } | 5386 } |
| 5691 | 5387 |
| 5692 | 5388 |
| 5693 RegExpNode* RegExpCapture::ToNode(RegExpCompiler* compiler, | 5389 RegExpNode* RegExpCapture::ToNode(RegExpCompiler* compiler, |
| 5694 RegExpNode* on_success) { | 5390 RegExpNode* on_success) { |
| 5695 return ToNode(body(), index(), compiler, on_success); | 5391 return ToNode(body(), index(), compiler, on_success); |
| 5696 } | 5392 } |
| 5697 | 5393 |
| (...skipping 27 matching lines...) Expand all Loading... |
| 5725 } | 5421 } |
| 5726 return current; | 5422 return current; |
| 5727 } | 5423 } |
| 5728 | 5424 |
| 5729 | 5425 |
| 5730 static void AddClass(const int* elmv, | 5426 static void AddClass(const int* elmv, |
| 5731 int elmc, | 5427 int elmc, |
| 5732 ZoneList<CharacterRange>* ranges, | 5428 ZoneList<CharacterRange>* ranges, |
| 5733 Zone* zone) { | 5429 Zone* zone) { |
| 5734 elmc--; | 5430 elmc--; |
| 5735 DCHECK(elmv[elmc] == kRangeEndMarker); | 5431 DCHECK(elmv[elmc] == 0x10000); |
| 5736 for (int i = 0; i < elmc; i += 2) { | 5432 for (int i = 0; i < elmc; i += 2) { |
| 5737 DCHECK(elmv[i] < elmv[i + 1]); | 5433 DCHECK(elmv[i] < elmv[i + 1]); |
| 5738 ranges->Add(CharacterRange(elmv[i], elmv[i + 1] - 1), zone); | 5434 ranges->Add(CharacterRange(elmv[i], elmv[i + 1] - 1), zone); |
| 5739 } | 5435 } |
| 5740 } | 5436 } |
| 5741 | 5437 |
| 5742 | 5438 |
| 5743 static void AddClassNegated(const int *elmv, | 5439 static void AddClassNegated(const int *elmv, |
| 5744 int elmc, | 5440 int elmc, |
| 5745 ZoneList<CharacterRange>* ranges, | 5441 ZoneList<CharacterRange>* ranges, |
| 5746 Zone* zone) { | 5442 Zone* zone) { |
| 5747 elmc--; | 5443 elmc--; |
| 5748 DCHECK(elmv[elmc] == kRangeEndMarker); | 5444 DCHECK(elmv[elmc] == 0x10000); |
| 5749 DCHECK(elmv[0] != 0x0000); | 5445 DCHECK(elmv[0] != 0x0000); |
| 5750 DCHECK(elmv[elmc - 1] != String::kMaxCodePoint); | 5446 DCHECK(elmv[elmc-1] != String::kMaxUtf16CodeUnit); |
| 5751 uc16 last = 0x0000; | 5447 uc16 last = 0x0000; |
| 5752 for (int i = 0; i < elmc; i += 2) { | 5448 for (int i = 0; i < elmc; i += 2) { |
| 5753 DCHECK(last <= elmv[i] - 1); | 5449 DCHECK(last <= elmv[i] - 1); |
| 5754 DCHECK(elmv[i] < elmv[i + 1]); | 5450 DCHECK(elmv[i] < elmv[i + 1]); |
| 5755 ranges->Add(CharacterRange(last, elmv[i] - 1), zone); | 5451 ranges->Add(CharacterRange(last, elmv[i] - 1), zone); |
| 5756 last = elmv[i + 1]; | 5452 last = elmv[i + 1]; |
| 5757 } | 5453 } |
| 5758 ranges->Add(CharacterRange(last, String::kMaxCodePoint), zone); | 5454 ranges->Add(CharacterRange(last, String::kMaxUtf16CodeUnit), zone); |
| 5759 } | 5455 } |
| 5760 | 5456 |
| 5761 | 5457 |
| 5762 void CharacterRange::AddClassEscape(uc16 type, | 5458 void CharacterRange::AddClassEscape(uc16 type, |
| 5763 ZoneList<CharacterRange>* ranges, | 5459 ZoneList<CharacterRange>* ranges, |
| 5764 Zone* zone) { | 5460 Zone* zone) { |
| 5765 switch (type) { | 5461 switch (type) { |
| 5766 case 's': | 5462 case 's': |
| 5767 AddClass(kSpaceRanges, kSpaceRangeCount, ranges, zone); | 5463 AddClass(kSpaceRanges, kSpaceRangeCount, ranges, zone); |
| 5768 break; | 5464 break; |
| (...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 5805 UNREACHABLE(); | 5501 UNREACHABLE(); |
| 5806 } | 5502 } |
| 5807 } | 5503 } |
| 5808 | 5504 |
| 5809 | 5505 |
| 5810 Vector<const int> CharacterRange::GetWordBounds() { | 5506 Vector<const int> CharacterRange::GetWordBounds() { |
| 5811 return Vector<const int>(kWordRanges, kWordRangeCount - 1); | 5507 return Vector<const int>(kWordRanges, kWordRangeCount - 1); |
| 5812 } | 5508 } |
| 5813 | 5509 |
| 5814 | 5510 |
| 5511 class CharacterRangeSplitter { |
| 5512 public: |
| 5513 CharacterRangeSplitter(ZoneList<CharacterRange>** included, |
| 5514 ZoneList<CharacterRange>** excluded, |
| 5515 Zone* zone) |
| 5516 : included_(included), |
| 5517 excluded_(excluded), |
| 5518 zone_(zone) { } |
| 5519 void Call(uc16 from, DispatchTable::Entry entry); |
| 5520 |
| 5521 static const int kInBase = 0; |
| 5522 static const int kInOverlay = 1; |
| 5523 |
| 5524 private: |
| 5525 ZoneList<CharacterRange>** included_; |
| 5526 ZoneList<CharacterRange>** excluded_; |
| 5527 Zone* zone_; |
| 5528 }; |
| 5529 |
| 5530 |
| 5531 void CharacterRangeSplitter::Call(uc16 from, DispatchTable::Entry entry) { |
| 5532 if (!entry.out_set()->Get(kInBase)) return; |
| 5533 ZoneList<CharacterRange>** target = entry.out_set()->Get(kInOverlay) |
| 5534 ? included_ |
| 5535 : excluded_; |
| 5536 if (*target == NULL) *target = new(zone_) ZoneList<CharacterRange>(2, zone_); |
| 5537 (*target)->Add(CharacterRange(entry.from(), entry.to()), zone_); |
| 5538 } |
| 5539 |
| 5540 |
| 5541 void CharacterRange::Split(ZoneList<CharacterRange>* base, |
| 5542 Vector<const int> overlay, |
| 5543 ZoneList<CharacterRange>** included, |
| 5544 ZoneList<CharacterRange>** excluded, |
| 5545 Zone* zone) { |
| 5546 DCHECK_NULL(*included); |
| 5547 DCHECK_NULL(*excluded); |
| 5548 DispatchTable table(zone); |
| 5549 for (int i = 0; i < base->length(); i++) |
| 5550 table.AddRange(base->at(i), CharacterRangeSplitter::kInBase, zone); |
| 5551 for (int i = 0; i < overlay.length(); i += 2) { |
| 5552 table.AddRange(CharacterRange(overlay[i], overlay[i + 1] - 1), |
| 5553 CharacterRangeSplitter::kInOverlay, zone); |
| 5554 } |
| 5555 CharacterRangeSplitter callback(included, excluded, zone); |
| 5556 table.ForEach(&callback); |
| 5557 } |
| 5558 |
| 5559 |
| 5815 void CharacterRange::AddCaseEquivalents(Isolate* isolate, Zone* zone, | 5560 void CharacterRange::AddCaseEquivalents(Isolate* isolate, Zone* zone, |
| 5816 ZoneList<CharacterRange>* ranges, | 5561 ZoneList<CharacterRange>* ranges, |
| 5817 bool is_one_byte) { | 5562 bool is_one_byte) { |
| 5818 uc32 bottom = from(); | 5563 uc16 bottom = from(); |
| 5819 uc32 top = to(); | 5564 uc16 top = to(); |
| 5820 // Nothing to be done for surrogates. | |
| 5821 if (bottom >= kLeadSurrogateStart && top <= kTrailSurrogateEnd) return; | |
| 5822 if (is_one_byte && !RangeContainsLatin1Equivalents(*this)) { | 5565 if (is_one_byte && !RangeContainsLatin1Equivalents(*this)) { |
| 5823 if (bottom > String::kMaxOneByteCharCode) return; | 5566 if (bottom > String::kMaxOneByteCharCode) return; |
| 5824 if (top > String::kMaxOneByteCharCode) top = String::kMaxOneByteCharCode; | 5567 if (top > String::kMaxOneByteCharCode) top = String::kMaxOneByteCharCode; |
| 5825 } | 5568 } |
| 5826 unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth]; | 5569 unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth]; |
| 5827 if (top == bottom) { | 5570 if (top == bottom) { |
| 5828 // If this is a singleton we just expand the one character. | 5571 // If this is a singleton we just expand the one character. |
| 5829 int length = isolate->jsregexp_uncanonicalize()->get(bottom, '\0', chars); | 5572 int length = isolate->jsregexp_uncanonicalize()->get(bottom, '\0', chars); |
| 5830 for (int i = 0; i < length; i++) { | 5573 for (int i = 0; i < length; i++) { |
| 5831 uc32 chr = chars[i]; | 5574 uc32 chr = chars[i]; |
| (...skipping 17 matching lines...) Expand all Loading... |
| 5849 // we look up ['z', 'Z'] and produce [c-f] and [C-F]. We then only | 5592 // we look up ['z', 'Z'] and produce [c-f] and [C-F]. We then only |
| 5850 // add a range if it is not already contained in the input, so [c-f] | 5593 // add a range if it is not already contained in the input, so [c-f] |
| 5851 // will be skipped but [C-F] will be added. If this range is not | 5594 // will be skipped but [C-F] will be added. If this range is not |
| 5852 // completely contained in a block we do this for all the blocks | 5595 // completely contained in a block we do this for all the blocks |
| 5853 // covered by the range (handling characters that is not in a block | 5596 // covered by the range (handling characters that is not in a block |
| 5854 // as a "singleton block"). | 5597 // as a "singleton block"). |
| 5855 unibrow::uchar range[unibrow::Ecma262UnCanonicalize::kMaxWidth]; | 5598 unibrow::uchar range[unibrow::Ecma262UnCanonicalize::kMaxWidth]; |
| 5856 int pos = bottom; | 5599 int pos = bottom; |
| 5857 while (pos <= top) { | 5600 while (pos <= top) { |
| 5858 int length = isolate->jsregexp_canonrange()->get(pos, '\0', range); | 5601 int length = isolate->jsregexp_canonrange()->get(pos, '\0', range); |
| 5859 uc32 block_end; | 5602 uc16 block_end; |
| 5860 if (length == 0) { | 5603 if (length == 0) { |
| 5861 block_end = pos; | 5604 block_end = pos; |
| 5862 } else { | 5605 } else { |
| 5863 DCHECK_EQ(1, length); | 5606 DCHECK_EQ(1, length); |
| 5864 block_end = range[0]; | 5607 block_end = range[0]; |
| 5865 } | 5608 } |
| 5866 int end = (block_end > top) ? top : block_end; | 5609 int end = (block_end > top) ? top : block_end; |
| 5867 length = isolate->jsregexp_uncanonicalize()->get(block_end, '\0', range); | 5610 length = isolate->jsregexp_uncanonicalize()->get(block_end, '\0', range); |
| 5868 for (int i = 0; i < length; i++) { | 5611 for (int i = 0; i < length; i++) { |
| 5869 uc32 c = range[i]; | 5612 uc32 c = range[i]; |
| 5870 uc32 range_from = c - (block_end - pos); | 5613 uc16 range_from = c - (block_end - pos); |
| 5871 uc32 range_to = c - (block_end - end); | 5614 uc16 range_to = c - (block_end - end); |
| 5872 if (!(bottom <= range_from && range_to <= top)) { | 5615 if (!(bottom <= range_from && range_to <= top)) { |
| 5873 ranges->Add(CharacterRange(range_from, range_to), zone); | 5616 ranges->Add(CharacterRange(range_from, range_to), zone); |
| 5874 } | 5617 } |
| 5875 } | 5618 } |
| 5876 pos = end + 1; | 5619 pos = end + 1; |
| 5877 } | 5620 } |
| 5878 } | 5621 } |
| 5879 } | 5622 } |
| 5880 | 5623 |
| 5881 | 5624 |
| (...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 5922 | 5665 |
| 5923 | 5666 |
| 5924 static int InsertRangeInCanonicalList(ZoneList<CharacterRange>* list, | 5667 static int InsertRangeInCanonicalList(ZoneList<CharacterRange>* list, |
| 5925 int count, | 5668 int count, |
| 5926 CharacterRange insert) { | 5669 CharacterRange insert) { |
| 5927 // Inserts a range into list[0..count[, which must be sorted | 5670 // Inserts a range into list[0..count[, which must be sorted |
| 5928 // by from value and non-overlapping and non-adjacent, using at most | 5671 // by from value and non-overlapping and non-adjacent, using at most |
| 5929 // list[0..count] for the result. Returns the number of resulting | 5672 // list[0..count] for the result. Returns the number of resulting |
| 5930 // canonicalized ranges. Inserting a range may collapse existing ranges into | 5673 // canonicalized ranges. Inserting a range may collapse existing ranges into |
| 5931 // fewer ranges, so the return value can be anything in the range 1..count+1. | 5674 // fewer ranges, so the return value can be anything in the range 1..count+1. |
| 5932 uc32 from = insert.from(); | 5675 uc16 from = insert.from(); |
| 5933 uc32 to = insert.to(); | 5676 uc16 to = insert.to(); |
| 5934 int start_pos = 0; | 5677 int start_pos = 0; |
| 5935 int end_pos = count; | 5678 int end_pos = count; |
| 5936 for (int i = count - 1; i >= 0; i--) { | 5679 for (int i = count - 1; i >= 0; i--) { |
| 5937 CharacterRange current = list->at(i); | 5680 CharacterRange current = list->at(i); |
| 5938 if (current.from() > to + 1) { | 5681 if (current.from() > to + 1) { |
| 5939 end_pos = i; | 5682 end_pos = i; |
| 5940 } else if (current.to() + 1 < from) { | 5683 } else if (current.to() + 1 < from) { |
| 5941 start_pos = i + 1; | 5684 start_pos = i + 1; |
| 5942 break; | 5685 break; |
| 5943 } | 5686 } |
| (...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 6023 DCHECK(CharacterRange::IsCanonical(character_ranges)); | 5766 DCHECK(CharacterRange::IsCanonical(character_ranges)); |
| 6024 } | 5767 } |
| 6025 | 5768 |
| 6026 | 5769 |
| 6027 void CharacterRange::Negate(ZoneList<CharacterRange>* ranges, | 5770 void CharacterRange::Negate(ZoneList<CharacterRange>* ranges, |
| 6028 ZoneList<CharacterRange>* negated_ranges, | 5771 ZoneList<CharacterRange>* negated_ranges, |
| 6029 Zone* zone) { | 5772 Zone* zone) { |
| 6030 DCHECK(CharacterRange::IsCanonical(ranges)); | 5773 DCHECK(CharacterRange::IsCanonical(ranges)); |
| 6031 DCHECK_EQ(0, negated_ranges->length()); | 5774 DCHECK_EQ(0, negated_ranges->length()); |
| 6032 int range_count = ranges->length(); | 5775 int range_count = ranges->length(); |
| 6033 uc32 from = 0; | 5776 uc16 from = 0; |
| 6034 int i = 0; | 5777 int i = 0; |
| 6035 if (range_count > 0 && ranges->at(0).from() == 0) { | 5778 if (range_count > 0 && ranges->at(0).from() == 0) { |
| 6036 from = ranges->at(0).to(); | 5779 from = ranges->at(0).to(); |
| 6037 i = 1; | 5780 i = 1; |
| 6038 } | 5781 } |
| 6039 while (i < range_count) { | 5782 while (i < range_count) { |
| 6040 CharacterRange range = ranges->at(i); | 5783 CharacterRange range = ranges->at(i); |
| 6041 negated_ranges->Add(CharacterRange(from + 1, range.from() - 1), zone); | 5784 negated_ranges->Add(CharacterRange(from + 1, range.from() - 1), zone); |
| 6042 from = range.to(); | 5785 from = range.to(); |
| 6043 i++; | 5786 i++; |
| 6044 } | 5787 } |
| 6045 if (from < String::kMaxCodePoint) { | 5788 if (from < String::kMaxUtf16CodeUnit) { |
| 6046 negated_ranges->Add(CharacterRange(from + 1, String::kMaxCodePoint), zone); | 5789 negated_ranges->Add(CharacterRange(from + 1, String::kMaxUtf16CodeUnit), |
| 5790 zone); |
| 6047 } | 5791 } |
| 6048 } | 5792 } |
| 6049 | 5793 |
| 6050 | 5794 |
| 6051 // ------------------------------------------------------------------- | 5795 // ------------------------------------------------------------------- |
| 6052 // Splay tree | 5796 // Splay tree |
| 6053 | 5797 |
| 6054 | 5798 |
| 6055 OutSet* OutSet::Extend(unsigned value, Zone* zone) { | 5799 OutSet* OutSet::Extend(unsigned value, Zone* zone) { |
| 6056 if (Get(value)) | 5800 if (Get(value)) |
| (...skipping 30 matching lines...) Expand all Loading... |
| 6087 if (value < kFirstLimit) { | 5831 if (value < kFirstLimit) { |
| 6088 return (first_ & (1 << value)) != 0; | 5832 return (first_ & (1 << value)) != 0; |
| 6089 } else if (remaining_ == NULL) { | 5833 } else if (remaining_ == NULL) { |
| 6090 return false; | 5834 return false; |
| 6091 } else { | 5835 } else { |
| 6092 return remaining_->Contains(value); | 5836 return remaining_->Contains(value); |
| 6093 } | 5837 } |
| 6094 } | 5838 } |
| 6095 | 5839 |
| 6096 | 5840 |
| 6097 const uc32 DispatchTable::Config::kNoKey = unibrow::Utf8::kBadChar; | 5841 const uc16 DispatchTable::Config::kNoKey = unibrow::Utf8::kBadChar; |
| 6098 | 5842 |
| 6099 | 5843 |
| 6100 void DispatchTable::AddRange(CharacterRange full_range, int value, | 5844 void DispatchTable::AddRange(CharacterRange full_range, int value, |
| 6101 Zone* zone) { | 5845 Zone* zone) { |
| 6102 CharacterRange current = full_range; | 5846 CharacterRange current = full_range; |
| 6103 if (tree()->is_empty()) { | 5847 if (tree()->is_empty()) { |
| 6104 // If this is the first range we just insert into the table. | 5848 // If this is the first range we just insert into the table. |
| 6105 ZoneSplayTree<Config>::Locator loc; | 5849 ZoneSplayTree<Config>::Locator loc; |
| 6106 bool inserted = tree()->Insert(current.from(), &loc); | 5850 bool inserted = tree()->Insert(current.from(), &loc); |
| 6107 DCHECK(inserted); | 5851 DCHECK(inserted); |
| (...skipping 81 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 6189 USE(inserted); | 5933 USE(inserted); |
| 6190 ins.set_value(Entry(current.from(), | 5934 ins.set_value(Entry(current.from(), |
| 6191 current.to(), | 5935 current.to(), |
| 6192 empty()->Extend(value, zone))); | 5936 empty()->Extend(value, zone))); |
| 6193 break; | 5937 break; |
| 6194 } | 5938 } |
| 6195 } | 5939 } |
| 6196 } | 5940 } |
| 6197 | 5941 |
| 6198 | 5942 |
| 6199 OutSet* DispatchTable::Get(uc32 value) { | 5943 OutSet* DispatchTable::Get(uc16 value) { |
| 6200 ZoneSplayTree<Config>::Locator loc; | 5944 ZoneSplayTree<Config>::Locator loc; |
| 6201 if (!tree()->FindGreatestLessThan(value, &loc)) | 5945 if (!tree()->FindGreatestLessThan(value, &loc)) |
| 6202 return empty(); | 5946 return empty(); |
| 6203 Entry* entry = &loc.value(); | 5947 Entry* entry = &loc.value(); |
| 6204 if (value <= entry->to()) | 5948 if (value <= entry->to()) |
| 6205 return entry->out_set(); | 5949 return entry->out_set(); |
| 6206 else | 5950 else |
| 6207 return empty(); | 5951 return empty(); |
| 6208 } | 5952 } |
| 6209 | 5953 |
| (...skipping 297 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 6507 } | 6251 } |
| 6508 | 6252 |
| 6509 | 6253 |
| 6510 void DispatchTableConstructor::VisitAction(ActionNode* that) { | 6254 void DispatchTableConstructor::VisitAction(ActionNode* that) { |
| 6511 RegExpNode* target = that->on_success(); | 6255 RegExpNode* target = that->on_success(); |
| 6512 target->Accept(this); | 6256 target->Accept(this); |
| 6513 } | 6257 } |
| 6514 | 6258 |
| 6515 | 6259 |
| 6516 RegExpEngine::CompilationResult RegExpEngine::Compile( | 6260 RegExpEngine::CompilationResult RegExpEngine::Compile( |
| 6517 Isolate* isolate, Zone* zone, RegExpCompileData* data, | 6261 Isolate* isolate, Zone* zone, RegExpCompileData* data, bool ignore_case, |
| 6518 JSRegExp::Flags flags, Handle<String> pattern, | 6262 bool is_global, bool is_multiline, bool is_sticky, Handle<String> pattern, |
| 6519 Handle<String> sample_subject, bool is_one_byte) { | 6263 Handle<String> sample_subject, bool is_one_byte) { |
| 6520 if ((data->capture_count + 1) * 2 - 1 > RegExpMacroAssembler::kMaxRegister) { | 6264 if ((data->capture_count + 1) * 2 - 1 > RegExpMacroAssembler::kMaxRegister) { |
| 6521 return IrregexpRegExpTooBig(isolate); | 6265 return IrregexpRegExpTooBig(isolate); |
| 6522 } | 6266 } |
| 6523 bool ignore_case = flags & JSRegExp::kIgnoreCase; | 6267 RegExpCompiler compiler(isolate, zone, data->capture_count, ignore_case, |
| 6524 bool is_sticky = flags & JSRegExp::kSticky; | |
| 6525 bool is_global = flags & JSRegExp::kGlobal; | |
| 6526 RegExpCompiler compiler(isolate, zone, data->capture_count, flags, | |
| 6527 is_one_byte); | 6268 is_one_byte); |
| 6528 | 6269 |
| 6529 if (compiler.optimize()) compiler.set_optimize(!TooMuchRegExpCode(pattern)); | 6270 if (compiler.optimize()) compiler.set_optimize(!TooMuchRegExpCode(pattern)); |
| 6530 | 6271 |
| 6531 // Sample some characters from the middle of the string. | 6272 // Sample some characters from the middle of the string. |
| 6532 static const int kSampleSize = 128; | 6273 static const int kSampleSize = 128; |
| 6533 | 6274 |
| 6534 sample_subject = String::Flatten(sample_subject); | 6275 sample_subject = String::Flatten(sample_subject); |
| 6535 int chars_sampled = 0; | 6276 int chars_sampled = 0; |
| 6536 int half_way = (sample_subject->length() - kSampleSize) / 2; | 6277 int half_way = (sample_subject->length() - kSampleSize) / 2; |
| (...skipping 222 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 6759 | 6500 |
| 6760 | 6501 |
| 6761 void RegExpResultsCache::Clear(FixedArray* cache) { | 6502 void RegExpResultsCache::Clear(FixedArray* cache) { |
| 6762 for (int i = 0; i < kRegExpResultsCacheSize; i++) { | 6503 for (int i = 0; i < kRegExpResultsCacheSize; i++) { |
| 6763 cache->set(i, Smi::FromInt(0)); | 6504 cache->set(i, Smi::FromInt(0)); |
| 6764 } | 6505 } |
| 6765 } | 6506 } |
| 6766 | 6507 |
| 6767 } // namespace internal | 6508 } // namespace internal |
| 6768 } // namespace v8 | 6509 } // namespace v8 |
| OLD | NEW |