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/v8.h" | 5 #include "src/v8.h" |
6 | 6 |
7 #include "src/ast.h" | 7 #include "src/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 968 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
979 return next_register_; | 979 return next_register_; |
980 } | 980 } |
981 return next_register_++; | 981 return next_register_++; |
982 } | 982 } |
983 | 983 |
984 RegExpEngine::CompilationResult Assemble(RegExpMacroAssembler* assembler, | 984 RegExpEngine::CompilationResult Assemble(RegExpMacroAssembler* assembler, |
985 RegExpNode* start, | 985 RegExpNode* start, |
986 int capture_count, | 986 int capture_count, |
987 Handle<String> pattern); | 987 Handle<String> pattern); |
988 | 988 |
989 inline void AddWork(RegExpNode* node) { work_list_->Add(node); } | 989 inline void AddWork(RegExpNode* node) { |
| 990 if (!node->on_work_list() && !node->label()->is_bound()) { |
| 991 node->set_on_work_list(true); |
| 992 work_list_->Add(node); |
| 993 } |
| 994 } |
990 | 995 |
991 static const int kImplementationOffset = 0; | 996 static const int kImplementationOffset = 0; |
992 static const int kNumberOfRegistersOffset = 0; | 997 static const int kNumberOfRegistersOffset = 0; |
993 static const int kCodeOffset = 1; | 998 static const int kCodeOffset = 1; |
994 | 999 |
995 RegExpMacroAssembler* macro_assembler() { return macro_assembler_; } | 1000 RegExpMacroAssembler* macro_assembler() { return macro_assembler_; } |
996 EndNode* accept() { return accept_; } | 1001 EndNode* accept() { return accept_; } |
997 | 1002 |
998 static const int kMaxRecursion = 100; | 1003 static const int kMaxRecursion = 100; |
999 inline int recursion_depth() { return recursion_depth_; } | 1004 inline int recursion_depth() { return recursion_depth_; } |
1000 inline void IncrementRecursionDepth() { recursion_depth_++; } | 1005 inline void IncrementRecursionDepth() { recursion_depth_++; } |
1001 inline void DecrementRecursionDepth() { recursion_depth_--; } | 1006 inline void DecrementRecursionDepth() { recursion_depth_--; } |
1002 | 1007 |
1003 void SetRegExpTooBig() { reg_exp_too_big_ = true; } | 1008 void SetRegExpTooBig() { reg_exp_too_big_ = true; } |
1004 | 1009 |
1005 inline bool ignore_case() { return ignore_case_; } | 1010 inline bool ignore_case() { return ignore_case_; } |
1006 inline bool one_byte() { return one_byte_; } | 1011 inline bool one_byte() { return one_byte_; } |
1007 inline bool optimize() { return optimize_; } | 1012 inline bool optimize() { return optimize_; } |
1008 inline void set_optimize(bool value) { optimize_ = value; } | 1013 inline void set_optimize(bool value) { optimize_ = value; } |
| 1014 inline bool limiting_recursion() { return limiting_recursion_; } |
| 1015 inline void set_limiting_recursion(bool value) { |
| 1016 limiting_recursion_ = value; |
| 1017 } |
1009 FrequencyCollator* frequency_collator() { return &frequency_collator_; } | 1018 FrequencyCollator* frequency_collator() { return &frequency_collator_; } |
1010 | 1019 |
1011 int current_expansion_factor() { return current_expansion_factor_; } | 1020 int current_expansion_factor() { return current_expansion_factor_; } |
1012 void set_current_expansion_factor(int value) { | 1021 void set_current_expansion_factor(int value) { |
1013 current_expansion_factor_ = value; | 1022 current_expansion_factor_ = value; |
1014 } | 1023 } |
1015 | 1024 |
1016 Isolate* isolate() const { return isolate_; } | 1025 Isolate* isolate() const { return isolate_; } |
1017 Zone* zone() const { return zone_; } | 1026 Zone* zone() const { return zone_; } |
1018 | 1027 |
1019 static const int kNoRegister = -1; | 1028 static const int kNoRegister = -1; |
1020 | 1029 |
1021 private: | 1030 private: |
1022 EndNode* accept_; | 1031 EndNode* accept_; |
1023 int next_register_; | 1032 int next_register_; |
1024 List<RegExpNode*>* work_list_; | 1033 List<RegExpNode*>* work_list_; |
1025 int recursion_depth_; | 1034 int recursion_depth_; |
1026 RegExpMacroAssembler* macro_assembler_; | 1035 RegExpMacroAssembler* macro_assembler_; |
1027 bool ignore_case_; | 1036 bool ignore_case_; |
1028 bool one_byte_; | 1037 bool one_byte_; |
1029 bool reg_exp_too_big_; | 1038 bool reg_exp_too_big_; |
| 1039 bool limiting_recursion_; |
1030 bool optimize_; | 1040 bool optimize_; |
1031 int current_expansion_factor_; | 1041 int current_expansion_factor_; |
1032 FrequencyCollator frequency_collator_; | 1042 FrequencyCollator frequency_collator_; |
1033 Isolate* isolate_; | 1043 Isolate* isolate_; |
1034 Zone* zone_; | 1044 Zone* zone_; |
1035 }; | 1045 }; |
1036 | 1046 |
1037 | 1047 |
1038 class RecursionCheck { | 1048 class RecursionCheck { |
1039 public: | 1049 public: |
(...skipping 14 matching lines...) Expand all Loading... |
1054 // Attempts to compile the regexp using an Irregexp code generator. Returns | 1064 // Attempts to compile the regexp using an Irregexp code generator. Returns |
1055 // a fixed array or a null handle depending on whether it succeeded. | 1065 // a fixed array or a null handle depending on whether it succeeded. |
1056 RegExpCompiler::RegExpCompiler(Isolate* isolate, Zone* zone, int capture_count, | 1066 RegExpCompiler::RegExpCompiler(Isolate* isolate, Zone* zone, int capture_count, |
1057 bool ignore_case, bool one_byte) | 1067 bool ignore_case, bool one_byte) |
1058 : next_register_(2 * (capture_count + 1)), | 1068 : next_register_(2 * (capture_count + 1)), |
1059 work_list_(NULL), | 1069 work_list_(NULL), |
1060 recursion_depth_(0), | 1070 recursion_depth_(0), |
1061 ignore_case_(ignore_case), | 1071 ignore_case_(ignore_case), |
1062 one_byte_(one_byte), | 1072 one_byte_(one_byte), |
1063 reg_exp_too_big_(false), | 1073 reg_exp_too_big_(false), |
| 1074 limiting_recursion_(false), |
1064 optimize_(FLAG_regexp_optimization), | 1075 optimize_(FLAG_regexp_optimization), |
1065 current_expansion_factor_(1), | 1076 current_expansion_factor_(1), |
1066 frequency_collator_(), | 1077 frequency_collator_(), |
1067 isolate_(isolate), | 1078 isolate_(isolate), |
1068 zone_(zone) { | 1079 zone_(zone) { |
1069 accept_ = new(zone) EndNode(EndNode::ACCEPT, zone); | 1080 accept_ = new(zone) EndNode(EndNode::ACCEPT, zone); |
1070 DCHECK(next_register_ - 1 <= RegExpMacroAssembler::kMaxRegister); | 1081 DCHECK(next_register_ - 1 <= RegExpMacroAssembler::kMaxRegister); |
1071 } | 1082 } |
1072 | 1083 |
1073 | 1084 |
(...skipping 14 matching lines...) Expand all Loading... |
1088 | 1099 |
1089 List <RegExpNode*> work_list(0); | 1100 List <RegExpNode*> work_list(0); |
1090 work_list_ = &work_list; | 1101 work_list_ = &work_list; |
1091 Label fail; | 1102 Label fail; |
1092 macro_assembler_->PushBacktrack(&fail); | 1103 macro_assembler_->PushBacktrack(&fail); |
1093 Trace new_trace; | 1104 Trace new_trace; |
1094 start->Emit(this, &new_trace); | 1105 start->Emit(this, &new_trace); |
1095 macro_assembler_->Bind(&fail); | 1106 macro_assembler_->Bind(&fail); |
1096 macro_assembler_->Fail(); | 1107 macro_assembler_->Fail(); |
1097 while (!work_list.is_empty()) { | 1108 while (!work_list.is_empty()) { |
1098 work_list.RemoveLast()->Emit(this, &new_trace); | 1109 RegExpNode* node = work_list.RemoveLast(); |
| 1110 node->set_on_work_list(false); |
| 1111 if (!node->label()->is_bound()) node->Emit(this, &new_trace); |
1099 } | 1112 } |
1100 if (reg_exp_too_big_) return IrregexpRegExpTooBig(isolate_); | 1113 if (reg_exp_too_big_) return IrregexpRegExpTooBig(isolate_); |
1101 | 1114 |
1102 Handle<HeapObject> code = macro_assembler_->GetCode(pattern); | 1115 Handle<HeapObject> code = macro_assembler_->GetCode(pattern); |
1103 heap->IncreaseTotalRegexpCodeGenerated(code->Size()); | 1116 heap->IncreaseTotalRegexpCodeGenerated(code->Size()); |
1104 work_list_ = NULL; | 1117 work_list_ = NULL; |
1105 #ifdef ENABLE_DISASSEMBLER | 1118 #ifdef ENABLE_DISASSEMBLER |
1106 if (FLAG_print_code) { | 1119 if (FLAG_print_code) { |
1107 CodeTracer::Scope trace_scope(heap->isolate()->GetCodeTracer()); | 1120 CodeTracer::Scope trace_scope(heap->isolate()->GetCodeTracer()); |
1108 OFStream os(trace_scope.file()); | 1121 OFStream os(trace_scope.file()); |
(...skipping 255 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1364 ®isters_to_pop, | 1377 ®isters_to_pop, |
1365 ®isters_to_clear, | 1378 ®isters_to_clear, |
1366 compiler->zone()); | 1379 compiler->zone()); |
1367 if (cp_offset_ != 0) { | 1380 if (cp_offset_ != 0) { |
1368 assembler->AdvanceCurrentPosition(cp_offset_); | 1381 assembler->AdvanceCurrentPosition(cp_offset_); |
1369 } | 1382 } |
1370 | 1383 |
1371 // Create a new trivial state and generate the node with that. | 1384 // Create a new trivial state and generate the node with that. |
1372 Label undo; | 1385 Label undo; |
1373 assembler->PushBacktrack(&undo); | 1386 assembler->PushBacktrack(&undo); |
1374 Trace new_state; | 1387 if (successor->KeepRecursing(compiler)) { |
1375 successor->Emit(compiler, &new_state); | 1388 Trace new_state; |
| 1389 successor->Emit(compiler, &new_state); |
| 1390 } else { |
| 1391 compiler->AddWork(successor); |
| 1392 assembler->GoTo(successor->label()); |
| 1393 } |
1376 | 1394 |
1377 // On backtrack we need to restore state. | 1395 // On backtrack we need to restore state. |
1378 assembler->Bind(&undo); | 1396 assembler->Bind(&undo); |
1379 RestoreAffectedRegisters(assembler, | 1397 RestoreAffectedRegisters(assembler, |
1380 max_register, | 1398 max_register, |
1381 registers_to_pop, | 1399 registers_to_pop, |
1382 registers_to_clear); | 1400 registers_to_clear); |
1383 if (backtrack() == NULL) { | 1401 if (backtrack() == NULL) { |
1384 assembler->Backtrack(); | 1402 assembler->Backtrack(); |
1385 } else { | 1403 } else { |
(...skipping 820 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2206 | 2224 |
2207 RegExpNode::LimitResult RegExpNode::LimitVersions(RegExpCompiler* compiler, | 2225 RegExpNode::LimitResult RegExpNode::LimitVersions(RegExpCompiler* compiler, |
2208 Trace* trace) { | 2226 Trace* trace) { |
2209 // If we are generating a greedy loop then don't stop and don't reuse code. | 2227 // If we are generating a greedy loop then don't stop and don't reuse code. |
2210 if (trace->stop_node() != NULL) { | 2228 if (trace->stop_node() != NULL) { |
2211 return CONTINUE; | 2229 return CONTINUE; |
2212 } | 2230 } |
2213 | 2231 |
2214 RegExpMacroAssembler* macro_assembler = compiler->macro_assembler(); | 2232 RegExpMacroAssembler* macro_assembler = compiler->macro_assembler(); |
2215 if (trace->is_trivial()) { | 2233 if (trace->is_trivial()) { |
2216 if (label_.is_bound()) { | 2234 if (label_.is_bound() || on_work_list() || !KeepRecursing(compiler)) { |
2217 // We are being asked to generate a generic version, but that's already | 2235 // If a generic version is already scheduled to be generated or we have |
2218 // been done so just go to it. | 2236 // recursed too deeply then just generate a jump to that code. |
2219 macro_assembler->GoTo(&label_); | 2237 macro_assembler->GoTo(&label_); |
2220 return DONE; | 2238 // This will queue it up for generation of a generic version if it hasn't |
2221 } | 2239 // already been queued. |
2222 if (compiler->recursion_depth() >= RegExpCompiler::kMaxRecursion) { | |
2223 // To avoid too deep recursion we push the node to the work queue and just | |
2224 // generate a goto here. | |
2225 compiler->AddWork(this); | 2240 compiler->AddWork(this); |
2226 macro_assembler->GoTo(&label_); | |
2227 return DONE; | 2241 return DONE; |
2228 } | 2242 } |
2229 // Generate generic version of the node and bind the label for later use. | 2243 // Generate generic version of the node and bind the label for later use. |
2230 macro_assembler->Bind(&label_); | 2244 macro_assembler->Bind(&label_); |
2231 return CONTINUE; | 2245 return CONTINUE; |
2232 } | 2246 } |
2233 | 2247 |
2234 // We are being asked to make a non-generic version. Keep track of how many | 2248 // We are being asked to make a non-generic version. Keep track of how many |
2235 // non-generic versions we generate so as not to overdo it. | 2249 // non-generic versions we generate so as not to overdo it. |
2236 trace_count_++; | 2250 trace_count_++; |
2237 if (compiler->optimize() && trace_count_ < kMaxCopiesCodeGenerated && | 2251 if (KeepRecursing(compiler) && compiler->optimize() && |
2238 compiler->recursion_depth() <= RegExpCompiler::kMaxRecursion) { | 2252 trace_count_ < kMaxCopiesCodeGenerated) { |
2239 return CONTINUE; | 2253 return CONTINUE; |
2240 } | 2254 } |
2241 | 2255 |
2242 // If we get here code has been generated for this node too many times or | 2256 // If we get here code has been generated for this node too many times or |
2243 // recursion is too deep. Time to switch to a generic version. The code for | 2257 // recursion is too deep. Time to switch to a generic version. The code for |
2244 // generic versions above can handle deep recursion properly. | 2258 // generic versions above can handle deep recursion properly. |
| 2259 bool was_limiting = compiler->limiting_recursion(); |
| 2260 compiler->set_limiting_recursion(true); |
2245 trace->Flush(compiler, this); | 2261 trace->Flush(compiler, this); |
| 2262 compiler->set_limiting_recursion(was_limiting); |
2246 return DONE; | 2263 return DONE; |
2247 } | 2264 } |
2248 | 2265 |
2249 | 2266 |
| 2267 bool RegExpNode::KeepRecursing(RegExpCompiler* compiler) { |
| 2268 return !compiler->limiting_recursion() && |
| 2269 compiler->recursion_depth() <= RegExpCompiler::kMaxRecursion; |
| 2270 } |
| 2271 |
| 2272 |
2250 int ActionNode::EatsAtLeast(int still_to_find, | 2273 int ActionNode::EatsAtLeast(int still_to_find, |
2251 int budget, | 2274 int budget, |
2252 bool not_at_start) { | 2275 bool not_at_start) { |
2253 if (budget <= 0) return 0; | 2276 if (budget <= 0) return 0; |
2254 if (action_type_ == POSITIVE_SUBMATCH_SUCCESS) return 0; // Rewinds input! | 2277 if (action_type_ == POSITIVE_SUBMATCH_SUCCESS) return 0; // Rewinds input! |
2255 return on_success()->EatsAtLeast(still_to_find, | 2278 return on_success()->EatsAtLeast(still_to_find, |
2256 budget - 1, | 2279 budget - 1, |
2257 not_at_start); | 2280 not_at_start); |
2258 } | 2281 } |
2259 | 2282 |
(...skipping 3758 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
6018 RegExpEngine::CompilationResult RegExpEngine::Compile( | 6041 RegExpEngine::CompilationResult RegExpEngine::Compile( |
6019 Isolate* isolate, Zone* zone, RegExpCompileData* data, bool ignore_case, | 6042 Isolate* isolate, Zone* zone, RegExpCompileData* data, bool ignore_case, |
6020 bool is_global, bool is_multiline, bool is_sticky, Handle<String> pattern, | 6043 bool is_global, bool is_multiline, bool is_sticky, Handle<String> pattern, |
6021 Handle<String> sample_subject, bool is_one_byte) { | 6044 Handle<String> sample_subject, bool is_one_byte) { |
6022 if ((data->capture_count + 1) * 2 - 1 > RegExpMacroAssembler::kMaxRegister) { | 6045 if ((data->capture_count + 1) * 2 - 1 > RegExpMacroAssembler::kMaxRegister) { |
6023 return IrregexpRegExpTooBig(isolate); | 6046 return IrregexpRegExpTooBig(isolate); |
6024 } | 6047 } |
6025 RegExpCompiler compiler(isolate, zone, data->capture_count, ignore_case, | 6048 RegExpCompiler compiler(isolate, zone, data->capture_count, ignore_case, |
6026 is_one_byte); | 6049 is_one_byte); |
6027 | 6050 |
6028 compiler.set_optimize(!TooMuchRegExpCode(pattern)); | 6051 if (compiler.optimize()) compiler.set_optimize(!TooMuchRegExpCode(pattern)); |
6029 | 6052 |
6030 // Sample some characters from the middle of the string. | 6053 // Sample some characters from the middle of the string. |
6031 static const int kSampleSize = 128; | 6054 static const int kSampleSize = 128; |
6032 | 6055 |
6033 sample_subject = String::Flatten(sample_subject); | 6056 sample_subject = String::Flatten(sample_subject); |
6034 int chars_sampled = 0; | 6057 int chars_sampled = 0; |
6035 int half_way = (sample_subject->length() - kSampleSize) / 2; | 6058 int half_way = (sample_subject->length() - kSampleSize) / 2; |
6036 for (int i = Max(0, half_way); | 6059 for (int i = Max(0, half_way); |
6037 i < sample_subject->length() && chars_sampled < kSampleSize; | 6060 i < sample_subject->length() && chars_sampled < kSampleSize; |
6038 i++, chars_sampled++) { | 6061 i++, chars_sampled++) { |
(...skipping 122 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
6161 Heap* heap = pattern->GetHeap(); | 6184 Heap* heap = pattern->GetHeap(); |
6162 bool too_much = pattern->length() > RegExpImpl::kRegExpTooLargeToOptimize; | 6185 bool too_much = pattern->length() > RegExpImpl::kRegExpTooLargeToOptimize; |
6163 if (heap->total_regexp_code_generated() > RegExpImpl::kRegExpCompiledLimit && | 6186 if (heap->total_regexp_code_generated() > RegExpImpl::kRegExpCompiledLimit && |
6164 heap->isolate()->memory_allocator()->SizeExecutable() > | 6187 heap->isolate()->memory_allocator()->SizeExecutable() > |
6165 RegExpImpl::kRegExpExecutableMemoryLimit) { | 6188 RegExpImpl::kRegExpExecutableMemoryLimit) { |
6166 too_much = true; | 6189 too_much = true; |
6167 } | 6190 } |
6168 return too_much; | 6191 return too_much; |
6169 } | 6192 } |
6170 }} // namespace v8::internal | 6193 }} // namespace v8::internal |
OLD | NEW |