OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 2280 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2291 | 2291 |
2292 // If we get here code has been generated for this node too many times or | 2292 // If we get here code has been generated for this node too many times or |
2293 // recursion is too deep. Time to switch to a generic version. The code for | 2293 // recursion is too deep. Time to switch to a generic version. The code for |
2294 // generic versions above can handle deep recursion properly. | 2294 // generic versions above can handle deep recursion properly. |
2295 trace->Flush(compiler, this); | 2295 trace->Flush(compiler, this); |
2296 return DONE; | 2296 return DONE; |
2297 } | 2297 } |
2298 | 2298 |
2299 | 2299 |
2300 int ActionNode::EatsAtLeast(int still_to_find, | 2300 int ActionNode::EatsAtLeast(int still_to_find, |
2301 int recursion_depth, | 2301 int budget, |
2302 bool not_at_start) { | 2302 bool not_at_start) { |
2303 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; | 2303 if (budget <= 0) return 0; |
2304 if (type_ == POSITIVE_SUBMATCH_SUCCESS) return 0; // Rewinds input! | 2304 if (type_ == POSITIVE_SUBMATCH_SUCCESS) return 0; // Rewinds input! |
2305 return on_success()->EatsAtLeast(still_to_find, | 2305 return on_success()->EatsAtLeast(still_to_find, |
2306 recursion_depth + 1, | 2306 budget - 1, |
2307 not_at_start); | 2307 not_at_start); |
2308 } | 2308 } |
2309 | 2309 |
2310 | 2310 |
2311 void ActionNode::FillInBMInfo(int offset, | 2311 void ActionNode::FillInBMInfo(int offset, |
2312 int recursion_depth, | |
2313 int budget, | 2312 int budget, |
2314 BoyerMooreLookahead* bm, | 2313 BoyerMooreLookahead* bm, |
2315 bool not_at_start) { | 2314 bool not_at_start) { |
2316 if (type_ == BEGIN_SUBMATCH) { | 2315 if (type_ == BEGIN_SUBMATCH) { |
2317 bm->SetRest(offset); | 2316 bm->SetRest(offset); |
2318 } else if (type_ != POSITIVE_SUBMATCH_SUCCESS) { | 2317 } else if (type_ != POSITIVE_SUBMATCH_SUCCESS) { |
2319 on_success()->FillInBMInfo( | 2318 on_success()->FillInBMInfo(offset, budget - 1, bm, not_at_start); |
2320 offset, recursion_depth + 1, budget - 1, bm, not_at_start); | |
2321 } | 2319 } |
2322 SaveBMInfo(bm, not_at_start, offset); | 2320 SaveBMInfo(bm, not_at_start, offset); |
2323 } | 2321 } |
2324 | 2322 |
2325 | 2323 |
2326 int AssertionNode::EatsAtLeast(int still_to_find, | 2324 int AssertionNode::EatsAtLeast(int still_to_find, |
2327 int recursion_depth, | 2325 int budget, |
2328 bool not_at_start) { | 2326 bool not_at_start) { |
2329 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; | 2327 if (budget <= 0) return 0; |
2330 // If we know we are not at the start and we are asked "how many characters | 2328 // If we know we are not at the start and we are asked "how many characters |
2331 // will you match if you succeed?" then we can answer anything since false | 2329 // will you match if you succeed?" then we can answer anything since false |
2332 // implies false. So lets just return the max answer (still_to_find) since | 2330 // implies false. So lets just return the max answer (still_to_find) since |
2333 // that won't prevent us from preloading a lot of characters for the other | 2331 // that won't prevent us from preloading a lot of characters for the other |
2334 // branches in the node graph. | 2332 // branches in the node graph. |
2335 if (type() == AT_START && not_at_start) return still_to_find; | 2333 if (type() == AT_START && not_at_start) return still_to_find; |
2336 return on_success()->EatsAtLeast(still_to_find, | 2334 return on_success()->EatsAtLeast(still_to_find, |
2337 recursion_depth + 1, | 2335 budget - 1, |
2338 not_at_start); | 2336 not_at_start); |
2339 } | 2337 } |
2340 | 2338 |
2341 | 2339 |
2342 void AssertionNode::FillInBMInfo(int offset, | 2340 void AssertionNode::FillInBMInfo(int offset, |
2343 int recursion_depth, | |
2344 int budget, | 2341 int budget, |
2345 BoyerMooreLookahead* bm, | 2342 BoyerMooreLookahead* bm, |
2346 bool not_at_start) { | 2343 bool not_at_start) { |
2347 // Match the behaviour of EatsAtLeast on this node. | 2344 // Match the behaviour of EatsAtLeast on this node. |
2348 if (type() == AT_START && not_at_start) return; | 2345 if (type() == AT_START && not_at_start) return; |
2349 on_success()->FillInBMInfo( | 2346 on_success()->FillInBMInfo(offset, budget - 1, bm, not_at_start); |
2350 offset, recursion_depth + 1, budget - 1, bm, not_at_start); | |
2351 SaveBMInfo(bm, not_at_start, offset); | 2347 SaveBMInfo(bm, not_at_start, offset); |
2352 } | 2348 } |
2353 | 2349 |
2354 | 2350 |
2355 int BackReferenceNode::EatsAtLeast(int still_to_find, | 2351 int BackReferenceNode::EatsAtLeast(int still_to_find, |
2356 int recursion_depth, | 2352 int budget, |
2357 bool not_at_start) { | 2353 bool not_at_start) { |
2358 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; | 2354 if (budget <= 0) return 0; |
2359 return on_success()->EatsAtLeast(still_to_find, | 2355 return on_success()->EatsAtLeast(still_to_find, |
2360 recursion_depth + 1, | 2356 budget - 1, |
2361 not_at_start); | 2357 not_at_start); |
2362 } | 2358 } |
2363 | 2359 |
2364 | 2360 |
2365 int TextNode::EatsAtLeast(int still_to_find, | 2361 int TextNode::EatsAtLeast(int still_to_find, |
2366 int recursion_depth, | 2362 int budget, |
2367 bool not_at_start) { | 2363 bool not_at_start) { |
2368 int answer = Length(); | 2364 int answer = Length(); |
2369 if (answer >= still_to_find) return answer; | 2365 if (answer >= still_to_find) return answer; |
2370 if (recursion_depth > RegExpCompiler::kMaxRecursion) return answer; | 2366 if (budget <= 0) return answer; |
2371 // We are not at start after this node so we set the last argument to 'true'. | 2367 // We are not at start after this node so we set the last argument to 'true'. |
2372 return answer + on_success()->EatsAtLeast(still_to_find - answer, | 2368 return answer + on_success()->EatsAtLeast(still_to_find - answer, |
2373 recursion_depth + 1, | 2369 budget - 1, |
2374 true); | 2370 true); |
2375 } | 2371 } |
2376 | 2372 |
2377 | 2373 |
2378 int NegativeLookaheadChoiceNode::EatsAtLeast(int still_to_find, | 2374 int NegativeLookaheadChoiceNode::EatsAtLeast(int still_to_find, |
2379 int recursion_depth, | 2375 int budget, |
2380 bool not_at_start) { | 2376 bool not_at_start) { |
2381 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; | 2377 if (budget <= 0) return 0; |
2382 // Alternative 0 is the negative lookahead, alternative 1 is what comes | 2378 // Alternative 0 is the negative lookahead, alternative 1 is what comes |
2383 // afterwards. | 2379 // afterwards. |
2384 RegExpNode* node = alternatives_->at(1).node(); | 2380 RegExpNode* node = alternatives_->at(1).node(); |
2385 return node->EatsAtLeast(still_to_find, recursion_depth + 1, not_at_start); | 2381 return node->EatsAtLeast(still_to_find, budget - 1, not_at_start); |
2386 } | 2382 } |
2387 | 2383 |
2388 | 2384 |
2389 void NegativeLookaheadChoiceNode::GetQuickCheckDetails( | 2385 void NegativeLookaheadChoiceNode::GetQuickCheckDetails( |
2390 QuickCheckDetails* details, | 2386 QuickCheckDetails* details, |
2391 RegExpCompiler* compiler, | 2387 RegExpCompiler* compiler, |
2392 int filled_in, | 2388 int filled_in, |
2393 bool not_at_start) { | 2389 bool not_at_start) { |
2394 // Alternative 0 is the negative lookahead, alternative 1 is what comes | 2390 // Alternative 0 is the negative lookahead, alternative 1 is what comes |
2395 // afterwards. | 2391 // afterwards. |
2396 RegExpNode* node = alternatives_->at(1).node(); | 2392 RegExpNode* node = alternatives_->at(1).node(); |
2397 return node->GetQuickCheckDetails(details, compiler, filled_in, not_at_start); | 2393 return node->GetQuickCheckDetails(details, compiler, filled_in, not_at_start); |
2398 } | 2394 } |
2399 | 2395 |
2400 | 2396 |
2401 int ChoiceNode::EatsAtLeastHelper(int still_to_find, | 2397 int ChoiceNode::EatsAtLeastHelper(int still_to_find, |
2402 int recursion_depth, | 2398 int budget, |
2403 RegExpNode* ignore_this_node, | 2399 RegExpNode* ignore_this_node, |
2404 bool not_at_start) { | 2400 bool not_at_start) { |
2405 if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0; | 2401 if (budget <= 0) return 0; |
2406 int min = 100; | 2402 int min = 100; |
2407 int choice_count = alternatives_->length(); | 2403 int choice_count = alternatives_->length(); |
| 2404 budget = (budget - 1) / choice_count; |
2408 for (int i = 0; i < choice_count; i++) { | 2405 for (int i = 0; i < choice_count; i++) { |
2409 RegExpNode* node = alternatives_->at(i).node(); | 2406 RegExpNode* node = alternatives_->at(i).node(); |
2410 if (node == ignore_this_node) continue; | 2407 if (node == ignore_this_node) continue; |
2411 int node_eats_at_least = node->EatsAtLeast(still_to_find, | 2408 int node_eats_at_least = |
2412 recursion_depth + 1, | 2409 node->EatsAtLeast(still_to_find, budget, not_at_start); |
2413 not_at_start); | |
2414 if (node_eats_at_least < min) min = node_eats_at_least; | 2410 if (node_eats_at_least < min) min = node_eats_at_least; |
| 2411 if (min == 0) return 0; |
2415 } | 2412 } |
2416 return min; | 2413 return min; |
2417 } | 2414 } |
2418 | 2415 |
2419 | 2416 |
2420 int LoopChoiceNode::EatsAtLeast(int still_to_find, | 2417 int LoopChoiceNode::EatsAtLeast(int still_to_find, |
2421 int recursion_depth, | 2418 int budget, |
2422 bool not_at_start) { | 2419 bool not_at_start) { |
2423 return EatsAtLeastHelper(still_to_find, | 2420 return EatsAtLeastHelper(still_to_find, |
2424 recursion_depth, | 2421 budget - 1, |
2425 loop_node_, | 2422 loop_node_, |
2426 not_at_start); | 2423 not_at_start); |
2427 } | 2424 } |
2428 | 2425 |
2429 | 2426 |
2430 int ChoiceNode::EatsAtLeast(int still_to_find, | 2427 int ChoiceNode::EatsAtLeast(int still_to_find, |
2431 int recursion_depth, | 2428 int budget, |
2432 bool not_at_start) { | 2429 bool not_at_start) { |
2433 return EatsAtLeastHelper(still_to_find, | 2430 return EatsAtLeastHelper(still_to_find, |
2434 recursion_depth, | 2431 budget, |
2435 NULL, | 2432 NULL, |
2436 not_at_start); | 2433 not_at_start); |
2437 } | 2434 } |
2438 | 2435 |
2439 | 2436 |
2440 // Takes the left-most 1-bit and smears it out, setting all bits to its right. | 2437 // Takes the left-most 1-bit and smears it out, setting all bits to its right. |
2441 static inline uint32_t SmearBitsRight(uint32_t v) { | 2438 static inline uint32_t SmearBitsRight(uint32_t v) { |
2442 v |= v >> 1; | 2439 v |= v >> 1; |
2443 v |= v >> 2; | 2440 v |= v >> 2; |
2444 v |= v >> 4; | 2441 v |= v >> 4; |
(...skipping 535 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2980 if (body_can_be_zero_length_ || info()->visited) return; | 2977 if (body_can_be_zero_length_ || info()->visited) return; |
2981 VisitMarker marker(info()); | 2978 VisitMarker marker(info()); |
2982 return ChoiceNode::GetQuickCheckDetails(details, | 2979 return ChoiceNode::GetQuickCheckDetails(details, |
2983 compiler, | 2980 compiler, |
2984 characters_filled_in, | 2981 characters_filled_in, |
2985 not_at_start); | 2982 not_at_start); |
2986 } | 2983 } |
2987 | 2984 |
2988 | 2985 |
2989 void LoopChoiceNode::FillInBMInfo(int offset, | 2986 void LoopChoiceNode::FillInBMInfo(int offset, |
2990 int recursion_depth, | |
2991 int budget, | 2987 int budget, |
2992 BoyerMooreLookahead* bm, | 2988 BoyerMooreLookahead* bm, |
2993 bool not_at_start) { | 2989 bool not_at_start) { |
2994 if (body_can_be_zero_length_ || | 2990 if (body_can_be_zero_length_ || budget <= 0) { |
2995 recursion_depth > RegExpCompiler::kMaxRecursion || | |
2996 budget <= 0) { | |
2997 bm->SetRest(offset); | 2991 bm->SetRest(offset); |
2998 SaveBMInfo(bm, not_at_start, offset); | 2992 SaveBMInfo(bm, not_at_start, offset); |
2999 return; | 2993 return; |
3000 } | 2994 } |
3001 ChoiceNode::FillInBMInfo( | 2995 ChoiceNode::FillInBMInfo(offset, budget - 1, bm, not_at_start); |
3002 offset, recursion_depth + 1, budget - 1, bm, not_at_start); | |
3003 SaveBMInfo(bm, not_at_start, offset); | 2996 SaveBMInfo(bm, not_at_start, offset); |
3004 } | 2997 } |
3005 | 2998 |
3006 | 2999 |
3007 void ChoiceNode::GetQuickCheckDetails(QuickCheckDetails* details, | 3000 void ChoiceNode::GetQuickCheckDetails(QuickCheckDetails* details, |
3008 RegExpCompiler* compiler, | 3001 RegExpCompiler* compiler, |
3009 int characters_filled_in, | 3002 int characters_filled_in, |
3010 bool not_at_start) { | 3003 bool not_at_start) { |
3011 not_at_start = (not_at_start || not_at_start_); | 3004 not_at_start = (not_at_start || not_at_start_); |
3012 int choice_count = alternatives_->length(); | 3005 int choice_count = alternatives_->length(); |
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3089 | 3082 |
3090 | 3083 |
3091 // Emit the code to handle \b and \B (word-boundary or non-word-boundary). | 3084 // Emit the code to handle \b and \B (word-boundary or non-word-boundary). |
3092 void AssertionNode::EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace) { | 3085 void AssertionNode::EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace) { |
3093 RegExpMacroAssembler* assembler = compiler->macro_assembler(); | 3086 RegExpMacroAssembler* assembler = compiler->macro_assembler(); |
3094 Trace::TriBool next_is_word_character = Trace::UNKNOWN; | 3087 Trace::TriBool next_is_word_character = Trace::UNKNOWN; |
3095 bool not_at_start = (trace->at_start() == Trace::FALSE); | 3088 bool not_at_start = (trace->at_start() == Trace::FALSE); |
3096 BoyerMooreLookahead* lookahead = bm_info(not_at_start); | 3089 BoyerMooreLookahead* lookahead = bm_info(not_at_start); |
3097 if (lookahead == NULL) { | 3090 if (lookahead == NULL) { |
3098 int eats_at_least = | 3091 int eats_at_least = |
3099 Min(kMaxLookaheadForBoyerMoore, | 3092 Min(kMaxLookaheadForBoyerMoore, EatsAtLeast(kMaxLookaheadForBoyerMoore, |
3100 EatsAtLeast(kMaxLookaheadForBoyerMoore, 0, not_at_start)); | 3093 kRecursionBudget, |
| 3094 not_at_start)); |
3101 if (eats_at_least >= 1) { | 3095 if (eats_at_least >= 1) { |
3102 BoyerMooreLookahead* bm = | 3096 BoyerMooreLookahead* bm = |
3103 new(zone()) BoyerMooreLookahead(eats_at_least, compiler, zone()); | 3097 new(zone()) BoyerMooreLookahead(eats_at_least, compiler, zone()); |
3104 FillInBMInfo(0, 0, kFillInBMBudget, bm, not_at_start); | 3098 FillInBMInfo(0, kRecursionBudget, bm, not_at_start); |
3105 if (bm->at(0)->is_non_word()) next_is_word_character = Trace::FALSE; | 3099 if (bm->at(0)->is_non_word()) next_is_word_character = Trace::FALSE; |
3106 if (bm->at(0)->is_word()) next_is_word_character = Trace::TRUE; | 3100 if (bm->at(0)->is_word()) next_is_word_character = Trace::TRUE; |
3107 } | 3101 } |
3108 } else { | 3102 } else { |
3109 if (lookahead->at(0)->is_non_word()) next_is_word_character = Trace::FALSE; | 3103 if (lookahead->at(0)->is_non_word()) next_is_word_character = Trace::FALSE; |
3110 if (lookahead->at(0)->is_word()) next_is_word_character = Trace::TRUE; | 3104 if (lookahead->at(0)->is_word()) next_is_word_character = Trace::TRUE; |
3111 } | 3105 } |
3112 bool at_boundary = (type_ == AssertionNode::AT_BOUNDARY); | 3106 bool at_boundary = (type_ == AssertionNode::AT_BOUNDARY); |
3113 if (next_is_word_character == Trace::UNKNOWN) { | 3107 if (next_is_word_character == Trace::UNKNOWN) { |
3114 Label before_non_word; | 3108 Label before_non_word; |
(...skipping 911 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4026 // At this point we know that we are at a non-greedy loop that will eat | 4020 // At this point we know that we are at a non-greedy loop that will eat |
4027 // any character one at a time. Any non-anchored regexp has such a | 4021 // any character one at a time. Any non-anchored regexp has such a |
4028 // loop prepended to it in order to find where it starts. We look for | 4022 // loop prepended to it in order to find where it starts. We look for |
4029 // a pattern of the form ...abc... where we can look 6 characters ahead | 4023 // a pattern of the form ...abc... where we can look 6 characters ahead |
4030 // and step forwards 3 if the character is not one of abc. Abc need | 4024 // and step forwards 3 if the character is not one of abc. Abc need |
4031 // not be atoms, they can be any reasonably limited character class or | 4025 // not be atoms, they can be any reasonably limited character class or |
4032 // small alternation. | 4026 // small alternation. |
4033 ASSERT(trace->is_trivial()); // This is the case on LoopChoiceNodes. | 4027 ASSERT(trace->is_trivial()); // This is the case on LoopChoiceNodes. |
4034 BoyerMooreLookahead* lookahead = bm_info(not_at_start); | 4028 BoyerMooreLookahead* lookahead = bm_info(not_at_start); |
4035 if (lookahead == NULL) { | 4029 if (lookahead == NULL) { |
4036 eats_at_least = | 4030 eats_at_least = Min(kMaxLookaheadForBoyerMoore, |
4037 Min(kMaxLookaheadForBoyerMoore, | 4031 EatsAtLeast(kMaxLookaheadForBoyerMoore, |
4038 EatsAtLeast(kMaxLookaheadForBoyerMoore, 0, not_at_start)); | 4032 kRecursionBudget, |
| 4033 not_at_start)); |
4039 if (eats_at_least >= 1) { | 4034 if (eats_at_least >= 1) { |
4040 BoyerMooreLookahead* bm = | 4035 BoyerMooreLookahead* bm = |
4041 new(zone()) BoyerMooreLookahead(eats_at_least, | 4036 new(zone()) BoyerMooreLookahead(eats_at_least, |
4042 compiler, | 4037 compiler, |
4043 zone()); | 4038 zone()); |
4044 GuardedAlternative alt0 = alternatives_->at(0); | 4039 GuardedAlternative alt0 = alternatives_->at(0); |
4045 alt0.node()->FillInBMInfo(0, 0, kFillInBMBudget, bm, not_at_start); | 4040 alt0.node()->FillInBMInfo(0, kRecursionBudget, bm, not_at_start); |
4046 skip_was_emitted = bm->EmitSkipInstructions(macro_assembler); | 4041 skip_was_emitted = bm->EmitSkipInstructions(macro_assembler); |
4047 } | 4042 } |
4048 } else { | 4043 } else { |
4049 skip_was_emitted = lookahead->EmitSkipInstructions(macro_assembler); | 4044 skip_was_emitted = lookahead->EmitSkipInstructions(macro_assembler); |
4050 } | 4045 } |
4051 } | 4046 } |
4052 } | 4047 } |
4053 } | 4048 } |
4054 | 4049 |
4055 if (eats_at_least == kEatsAtLeastNotYetInitialized) { | 4050 if (eats_at_least == kEatsAtLeastNotYetInitialized) { |
4056 // Save some time by looking at most one machine word ahead. | 4051 // Save some time by looking at most one machine word ahead. |
4057 eats_at_least = EatsAtLeast(compiler->ascii() ? 4 : 2, 0, not_at_start); | 4052 eats_at_least = |
| 4053 EatsAtLeast(compiler->ascii() ? 4 : 2, kRecursionBudget, not_at_start); |
4058 } | 4054 } |
4059 int preload_characters = CalculatePreloadCharacters(compiler, eats_at_least); | 4055 int preload_characters = CalculatePreloadCharacters(compiler, eats_at_least); |
4060 | 4056 |
4061 bool preload_is_current = !skip_was_emitted && | 4057 bool preload_is_current = !skip_was_emitted && |
4062 (current_trace->characters_preloaded() == preload_characters); | 4058 (current_trace->characters_preloaded() == preload_characters); |
4063 bool preload_has_checked_bounds = preload_is_current; | 4059 bool preload_has_checked_bounds = preload_is_current; |
4064 | 4060 |
4065 AlternativeGenerationList alt_gens(choice_count, zone()); | 4061 AlternativeGenerationList alt_gens(choice_count, zone()); |
4066 | 4062 |
4067 // For now we just call all choices one after the other. The idea ultimately | 4063 // For now we just call all choices one after the other. The idea ultimately |
(...skipping 1735 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5803 EnsureAnalyzed(that->on_success()); | 5799 EnsureAnalyzed(that->on_success()); |
5804 } | 5800 } |
5805 | 5801 |
5806 | 5802 |
5807 void Analysis::VisitAssertion(AssertionNode* that) { | 5803 void Analysis::VisitAssertion(AssertionNode* that) { |
5808 EnsureAnalyzed(that->on_success()); | 5804 EnsureAnalyzed(that->on_success()); |
5809 } | 5805 } |
5810 | 5806 |
5811 | 5807 |
5812 void BackReferenceNode::FillInBMInfo(int offset, | 5808 void BackReferenceNode::FillInBMInfo(int offset, |
5813 int recursion_depth, | |
5814 int budget, | 5809 int budget, |
5815 BoyerMooreLookahead* bm, | 5810 BoyerMooreLookahead* bm, |
5816 bool not_at_start) { | 5811 bool not_at_start) { |
5817 // Working out the set of characters that a backreference can match is too | 5812 // Working out the set of characters that a backreference can match is too |
5818 // hard, so we just say that any character can match. | 5813 // hard, so we just say that any character can match. |
5819 bm->SetRest(offset); | 5814 bm->SetRest(offset); |
5820 SaveBMInfo(bm, not_at_start, offset); | 5815 SaveBMInfo(bm, not_at_start, offset); |
5821 } | 5816 } |
5822 | 5817 |
5823 | 5818 |
5824 STATIC_ASSERT(BoyerMoorePositionInfo::kMapSize == | 5819 STATIC_ASSERT(BoyerMoorePositionInfo::kMapSize == |
5825 RegExpMacroAssembler::kTableSize); | 5820 RegExpMacroAssembler::kTableSize); |
5826 | 5821 |
5827 | 5822 |
5828 void ChoiceNode::FillInBMInfo(int offset, | 5823 void ChoiceNode::FillInBMInfo(int offset, |
5829 int recursion_depth, | |
5830 int budget, | 5824 int budget, |
5831 BoyerMooreLookahead* bm, | 5825 BoyerMooreLookahead* bm, |
5832 bool not_at_start) { | 5826 bool not_at_start) { |
5833 ZoneList<GuardedAlternative>* alts = alternatives(); | 5827 ZoneList<GuardedAlternative>* alts = alternatives(); |
5834 budget = (budget - 1) / alts->length(); | 5828 budget = (budget - 1) / alts->length(); |
5835 for (int i = 0; i < alts->length(); i++) { | 5829 for (int i = 0; i < alts->length(); i++) { |
5836 GuardedAlternative& alt = alts->at(i); | 5830 GuardedAlternative& alt = alts->at(i); |
5837 if (alt.guards() != NULL && alt.guards()->length() != 0) { | 5831 if (alt.guards() != NULL && alt.guards()->length() != 0) { |
5838 bm->SetRest(offset); // Give up trying to fill in info. | 5832 bm->SetRest(offset); // Give up trying to fill in info. |
5839 SaveBMInfo(bm, not_at_start, offset); | 5833 SaveBMInfo(bm, not_at_start, offset); |
5840 return; | 5834 return; |
5841 } | 5835 } |
5842 alt.node()->FillInBMInfo( | 5836 alt.node()->FillInBMInfo(offset, budget, bm, not_at_start); |
5843 offset, recursion_depth + 1, budget, bm, not_at_start); | |
5844 } | 5837 } |
5845 SaveBMInfo(bm, not_at_start, offset); | 5838 SaveBMInfo(bm, not_at_start, offset); |
5846 } | 5839 } |
5847 | 5840 |
5848 | 5841 |
5849 void TextNode::FillInBMInfo(int initial_offset, | 5842 void TextNode::FillInBMInfo(int initial_offset, |
5850 int recursion_depth, | |
5851 int budget, | 5843 int budget, |
5852 BoyerMooreLookahead* bm, | 5844 BoyerMooreLookahead* bm, |
5853 bool not_at_start) { | 5845 bool not_at_start) { |
5854 if (initial_offset >= bm->length()) return; | 5846 if (initial_offset >= bm->length()) return; |
5855 int offset = initial_offset; | 5847 int offset = initial_offset; |
5856 int max_char = bm->max_char(); | 5848 int max_char = bm->max_char(); |
5857 for (int i = 0; i < elements()->length(); i++) { | 5849 for (int i = 0; i < elements()->length(); i++) { |
5858 if (offset >= bm->length()) { | 5850 if (offset >= bm->length()) { |
5859 if (initial_offset == 0) set_bm_info(not_at_start, bm); | 5851 if (initial_offset == 0) set_bm_info(not_at_start, bm); |
5860 return; | 5852 return; |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5897 } | 5889 } |
5898 } | 5890 } |
5899 offset++; | 5891 offset++; |
5900 } | 5892 } |
5901 } | 5893 } |
5902 if (offset >= bm->length()) { | 5894 if (offset >= bm->length()) { |
5903 if (initial_offset == 0) set_bm_info(not_at_start, bm); | 5895 if (initial_offset == 0) set_bm_info(not_at_start, bm); |
5904 return; | 5896 return; |
5905 } | 5897 } |
5906 on_success()->FillInBMInfo(offset, | 5898 on_success()->FillInBMInfo(offset, |
5907 recursion_depth + 1, | |
5908 budget - 1, | 5899 budget - 1, |
5909 bm, | 5900 bm, |
5910 true); // Not at start after a text node. | 5901 true); // Not at start after a text node. |
5911 if (initial_offset == 0) set_bm_info(not_at_start, bm); | 5902 if (initial_offset == 0) set_bm_info(not_at_start, bm); |
5912 } | 5903 } |
5913 | 5904 |
5914 | 5905 |
5915 // ------------------------------------------------------------------- | 5906 // ------------------------------------------------------------------- |
5916 // Dispatch table construction | 5907 // Dispatch table construction |
5917 | 5908 |
(...skipping 231 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
6149 } | 6140 } |
6150 | 6141 |
6151 return compiler.Assemble(¯o_assembler, | 6142 return compiler.Assemble(¯o_assembler, |
6152 node, | 6143 node, |
6153 data->capture_count, | 6144 data->capture_count, |
6154 pattern); | 6145 pattern); |
6155 } | 6146 } |
6156 | 6147 |
6157 | 6148 |
6158 }} // namespace v8::internal | 6149 }} // namespace v8::internal |
OLD | NEW |