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 2459 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2470 } | 2470 } |
2471 | 2471 |
2472 | 2472 |
2473 bool RegExpNode::EmitQuickCheck(RegExpCompiler* compiler, | 2473 bool RegExpNode::EmitQuickCheck(RegExpCompiler* compiler, |
2474 Trace* trace, | 2474 Trace* trace, |
2475 bool preload_has_checked_bounds, | 2475 bool preload_has_checked_bounds, |
2476 Label* on_possible_success, | 2476 Label* on_possible_success, |
2477 QuickCheckDetails* details, | 2477 QuickCheckDetails* details, |
2478 bool fall_through_on_failure) { | 2478 bool fall_through_on_failure) { |
2479 if (details->characters() == 0) return false; | 2479 if (details->characters() == 0) return false; |
2480 GetQuickCheckDetails(details, compiler, 0, trace->at_start() == Trace::FALSE); | 2480 GetQuickCheckDetails( |
| 2481 details, compiler, 0, trace->at_start() == Trace::FALSE_LITERAL); |
2481 if (details->cannot_match()) return false; | 2482 if (details->cannot_match()) return false; |
2482 if (!details->Rationalize(compiler->ascii())) return false; | 2483 if (!details->Rationalize(compiler->ascii())) return false; |
2483 ASSERT(details->characters() == 1 || | 2484 ASSERT(details->characters() == 1 || |
2484 compiler->macro_assembler()->CanReadUnaligned()); | 2485 compiler->macro_assembler()->CanReadUnaligned()); |
2485 uint32_t mask = details->mask(); | 2486 uint32_t mask = details->mask(); |
2486 uint32_t value = details->value(); | 2487 uint32_t value = details->value(); |
2487 | 2488 |
2488 RegExpMacroAssembler* assembler = compiler->macro_assembler(); | 2489 RegExpMacroAssembler* assembler = compiler->macro_assembler(); |
2489 | 2490 |
2490 if (trace->characters_preloaded() != details->characters()) { | 2491 if (trace->characters_preloaded() != details->characters()) { |
(...skipping 568 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3059 } | 3060 } |
3060 assembler->Bind(&ok); | 3061 assembler->Bind(&ok); |
3061 on_success->Emit(compiler, &new_trace); | 3062 on_success->Emit(compiler, &new_trace); |
3062 } | 3063 } |
3063 | 3064 |
3064 | 3065 |
3065 // Emit the code to handle \b and \B (word-boundary or non-word-boundary). | 3066 // Emit the code to handle \b and \B (word-boundary or non-word-boundary). |
3066 void AssertionNode::EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace) { | 3067 void AssertionNode::EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace) { |
3067 RegExpMacroAssembler* assembler = compiler->macro_assembler(); | 3068 RegExpMacroAssembler* assembler = compiler->macro_assembler(); |
3068 Trace::TriBool next_is_word_character = Trace::UNKNOWN; | 3069 Trace::TriBool next_is_word_character = Trace::UNKNOWN; |
3069 bool not_at_start = (trace->at_start() == Trace::FALSE); | 3070 bool not_at_start = (trace->at_start() == Trace::FALSE_LITERAL); |
3070 BoyerMooreLookahead* lookahead = bm_info(not_at_start); | 3071 BoyerMooreLookahead* lookahead = bm_info(not_at_start); |
3071 if (lookahead == NULL) { | 3072 if (lookahead == NULL) { |
3072 int eats_at_least = | 3073 int eats_at_least = |
3073 Min(kMaxLookaheadForBoyerMoore, EatsAtLeast(kMaxLookaheadForBoyerMoore, | 3074 Min(kMaxLookaheadForBoyerMoore, EatsAtLeast(kMaxLookaheadForBoyerMoore, |
3074 kRecursionBudget, | 3075 kRecursionBudget, |
3075 not_at_start)); | 3076 not_at_start)); |
3076 if (eats_at_least >= 1) { | 3077 if (eats_at_least >= 1) { |
3077 BoyerMooreLookahead* bm = | 3078 BoyerMooreLookahead* bm = |
3078 new(zone()) BoyerMooreLookahead(eats_at_least, compiler, zone()); | 3079 new(zone()) BoyerMooreLookahead(eats_at_least, compiler, zone()); |
3079 FillInBMInfo(0, kRecursionBudget, bm, not_at_start); | 3080 FillInBMInfo(0, kRecursionBudget, bm, not_at_start); |
3080 if (bm->at(0)->is_non_word()) next_is_word_character = Trace::FALSE; | 3081 if (bm->at(0)->is_non_word()) |
3081 if (bm->at(0)->is_word()) next_is_word_character = Trace::TRUE; | 3082 next_is_word_character = Trace::FALSE_LITERAL; |
| 3083 if (bm->at(0)->is_word()) next_is_word_character = Trace::TRUE_LITERAL; |
3082 } | 3084 } |
3083 } else { | 3085 } else { |
3084 if (lookahead->at(0)->is_non_word()) next_is_word_character = Trace::FALSE; | 3086 if (lookahead->at(0)->is_non_word()) |
3085 if (lookahead->at(0)->is_word()) next_is_word_character = Trace::TRUE; | 3087 next_is_word_character = Trace::FALSE_LITERAL; |
| 3088 if (lookahead->at(0)->is_word()) |
| 3089 next_is_word_character = Trace::TRUE_LITERAL; |
3086 } | 3090 } |
3087 bool at_boundary = (assertion_type_ == AssertionNode::AT_BOUNDARY); | 3091 bool at_boundary = (assertion_type_ == AssertionNode::AT_BOUNDARY); |
3088 if (next_is_word_character == Trace::UNKNOWN) { | 3092 if (next_is_word_character == Trace::UNKNOWN) { |
3089 Label before_non_word; | 3093 Label before_non_word; |
3090 Label before_word; | 3094 Label before_word; |
3091 if (trace->characters_preloaded() != 1) { | 3095 if (trace->characters_preloaded() != 1) { |
3092 assembler->LoadCurrentCharacter(trace->cp_offset(), &before_non_word); | 3096 assembler->LoadCurrentCharacter(trace->cp_offset(), &before_non_word); |
3093 } | 3097 } |
3094 // Fall through on non-word. | 3098 // Fall through on non-word. |
3095 EmitWordCheck(assembler, &before_word, &before_non_word, false); | 3099 EmitWordCheck(assembler, &before_word, &before_non_word, false); |
3096 // Next character is not a word character. | 3100 // Next character is not a word character. |
3097 assembler->Bind(&before_non_word); | 3101 assembler->Bind(&before_non_word); |
3098 Label ok; | 3102 Label ok; |
3099 BacktrackIfPrevious(compiler, trace, at_boundary ? kIsNonWord : kIsWord); | 3103 BacktrackIfPrevious(compiler, trace, at_boundary ? kIsNonWord : kIsWord); |
3100 assembler->GoTo(&ok); | 3104 assembler->GoTo(&ok); |
3101 | 3105 |
3102 assembler->Bind(&before_word); | 3106 assembler->Bind(&before_word); |
3103 BacktrackIfPrevious(compiler, trace, at_boundary ? kIsWord : kIsNonWord); | 3107 BacktrackIfPrevious(compiler, trace, at_boundary ? kIsWord : kIsNonWord); |
3104 assembler->Bind(&ok); | 3108 assembler->Bind(&ok); |
3105 } else if (next_is_word_character == Trace::TRUE) { | 3109 } else if (next_is_word_character == Trace::TRUE_LITERAL) { |
3106 BacktrackIfPrevious(compiler, trace, at_boundary ? kIsWord : kIsNonWord); | 3110 BacktrackIfPrevious(compiler, trace, at_boundary ? kIsWord : kIsNonWord); |
3107 } else { | 3111 } else { |
3108 ASSERT(next_is_word_character == Trace::FALSE); | 3112 ASSERT(next_is_word_character == Trace::FALSE_LITERAL); |
3109 BacktrackIfPrevious(compiler, trace, at_boundary ? kIsNonWord : kIsWord); | 3113 BacktrackIfPrevious(compiler, trace, at_boundary ? kIsNonWord : kIsWord); |
3110 } | 3114 } |
3111 } | 3115 } |
3112 | 3116 |
3113 | 3117 |
3114 void AssertionNode::BacktrackIfPrevious( | 3118 void AssertionNode::BacktrackIfPrevious( |
3115 RegExpCompiler* compiler, | 3119 RegExpCompiler* compiler, |
3116 Trace* trace, | 3120 Trace* trace, |
3117 AssertionNode::IfPrevious backtrack_if_previous) { | 3121 AssertionNode::IfPrevious backtrack_if_previous) { |
3118 RegExpMacroAssembler* assembler = compiler->macro_assembler(); | 3122 RegExpMacroAssembler* assembler = compiler->macro_assembler(); |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3162 RegExpMacroAssembler* assembler = compiler->macro_assembler(); | 3166 RegExpMacroAssembler* assembler = compiler->macro_assembler(); |
3163 switch (assertion_type_) { | 3167 switch (assertion_type_) { |
3164 case AT_END: { | 3168 case AT_END: { |
3165 Label ok; | 3169 Label ok; |
3166 assembler->CheckPosition(trace->cp_offset(), &ok); | 3170 assembler->CheckPosition(trace->cp_offset(), &ok); |
3167 assembler->GoTo(trace->backtrack()); | 3171 assembler->GoTo(trace->backtrack()); |
3168 assembler->Bind(&ok); | 3172 assembler->Bind(&ok); |
3169 break; | 3173 break; |
3170 } | 3174 } |
3171 case AT_START: { | 3175 case AT_START: { |
3172 if (trace->at_start() == Trace::FALSE) { | 3176 if (trace->at_start() == Trace::FALSE_LITERAL) { |
3173 assembler->GoTo(trace->backtrack()); | 3177 assembler->GoTo(trace->backtrack()); |
3174 return; | 3178 return; |
3175 } | 3179 } |
3176 if (trace->at_start() == Trace::UNKNOWN) { | 3180 if (trace->at_start() == Trace::UNKNOWN) { |
3177 assembler->CheckNotAtStart(trace->backtrack()); | 3181 assembler->CheckNotAtStart(trace->backtrack()); |
3178 Trace at_start_trace = *trace; | 3182 Trace at_start_trace = *trace; |
3179 at_start_trace.set_at_start(true); | 3183 at_start_trace.set_at_start(true); |
3180 on_success()->Emit(compiler, &at_start_trace); | 3184 on_success()->Emit(compiler, &at_start_trace); |
3181 return; | 3185 return; |
3182 } | 3186 } |
(...skipping 796 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3979 greedy_match_trace.set_loop_label(&loop_label); | 3983 greedy_match_trace.set_loop_label(&loop_label); |
3980 alternatives_->at(0).node()->Emit(compiler, &greedy_match_trace); | 3984 alternatives_->at(0).node()->Emit(compiler, &greedy_match_trace); |
3981 macro_assembler->Bind(&greedy_match_failed); | 3985 macro_assembler->Bind(&greedy_match_failed); |
3982 } | 3986 } |
3983 | 3987 |
3984 Label second_choice; // For use in greedy matches. | 3988 Label second_choice; // For use in greedy matches. |
3985 macro_assembler->Bind(&second_choice); | 3989 macro_assembler->Bind(&second_choice); |
3986 | 3990 |
3987 int first_normal_choice = greedy_loop ? 1 : 0; | 3991 int first_normal_choice = greedy_loop ? 1 : 0; |
3988 | 3992 |
3989 bool not_at_start = current_trace->at_start() == Trace::FALSE; | 3993 bool not_at_start = current_trace->at_start() == Trace::FALSE_LITERAL; |
3990 const int kEatsAtLeastNotYetInitialized = -1; | 3994 const int kEatsAtLeastNotYetInitialized = -1; |
3991 int eats_at_least = kEatsAtLeastNotYetInitialized; | 3995 int eats_at_least = kEatsAtLeastNotYetInitialized; |
3992 | 3996 |
3993 bool skip_was_emitted = false; | 3997 bool skip_was_emitted = false; |
3994 | 3998 |
3995 if (!greedy_loop && choice_count == 2) { | 3999 if (!greedy_loop && choice_count == 2) { |
3996 GuardedAlternative alt1 = alternatives_->at(1); | 4000 GuardedAlternative alt1 = alternatives_->at(1); |
3997 if (alt1.guards() == NULL || alt1.guards()->length() == 0) { | 4001 if (alt1.guards() == NULL || alt1.guards()->length() == 0) { |
3998 RegExpNode* eats_anything_node = alt1.node(); | 4002 RegExpNode* eats_anything_node = alt1.node(); |
3999 if (eats_anything_node->GetSuccessorOfOmnivorousTextNode(compiler) == | 4003 if (eats_anything_node->GetSuccessorOfOmnivorousTextNode(compiler) == |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4050 ZoneList<Guard*>* guards = alternative.guards(); | 4054 ZoneList<Guard*>* guards = alternative.guards(); |
4051 int guard_count = (guards == NULL) ? 0 : guards->length(); | 4055 int guard_count = (guards == NULL) ? 0 : guards->length(); |
4052 Trace new_trace(*current_trace); | 4056 Trace new_trace(*current_trace); |
4053 new_trace.set_characters_preloaded(preload_is_current ? | 4057 new_trace.set_characters_preloaded(preload_is_current ? |
4054 preload_characters : | 4058 preload_characters : |
4055 0); | 4059 0); |
4056 if (preload_has_checked_bounds) { | 4060 if (preload_has_checked_bounds) { |
4057 new_trace.set_bound_checked_up_to(preload_characters); | 4061 new_trace.set_bound_checked_up_to(preload_characters); |
4058 } | 4062 } |
4059 new_trace.quick_check_performed()->Clear(); | 4063 new_trace.quick_check_performed()->Clear(); |
4060 if (not_at_start_) new_trace.set_at_start(Trace::FALSE); | 4064 if (not_at_start_) new_trace.set_at_start(Trace::FALSE_LITERAL); |
4061 alt_gen->expects_preload = preload_is_current; | 4065 alt_gen->expects_preload = preload_is_current; |
4062 bool generate_full_check_inline = false; | 4066 bool generate_full_check_inline = false; |
4063 if (FLAG_regexp_optimization && | 4067 if (FLAG_regexp_optimization && |
4064 try_to_emit_quick_check_for_alternative(i) && | 4068 try_to_emit_quick_check_for_alternative(i) && |
4065 alternative.node()->EmitQuickCheck(compiler, | 4069 alternative.node()->EmitQuickCheck(compiler, |
4066 &new_trace, | 4070 &new_trace, |
4067 preload_has_checked_bounds, | 4071 preload_has_checked_bounds, |
4068 &alt_gen->possible_success, | 4072 &alt_gen->possible_success, |
4069 &alt_gen->quick_check_details, | 4073 &alt_gen->quick_check_details, |
4070 i < choice_count - 1)) { | 4074 i < choice_count - 1)) { |
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4150 AlternativeGeneration* alt_gen, | 4154 AlternativeGeneration* alt_gen, |
4151 int preload_characters, | 4155 int preload_characters, |
4152 bool next_expects_preload) { | 4156 bool next_expects_preload) { |
4153 if (!alt_gen->possible_success.is_linked()) return; | 4157 if (!alt_gen->possible_success.is_linked()) return; |
4154 | 4158 |
4155 RegExpMacroAssembler* macro_assembler = compiler->macro_assembler(); | 4159 RegExpMacroAssembler* macro_assembler = compiler->macro_assembler(); |
4156 macro_assembler->Bind(&alt_gen->possible_success); | 4160 macro_assembler->Bind(&alt_gen->possible_success); |
4157 Trace out_of_line_trace(*trace); | 4161 Trace out_of_line_trace(*trace); |
4158 out_of_line_trace.set_characters_preloaded(preload_characters); | 4162 out_of_line_trace.set_characters_preloaded(preload_characters); |
4159 out_of_line_trace.set_quick_check_performed(&alt_gen->quick_check_details); | 4163 out_of_line_trace.set_quick_check_performed(&alt_gen->quick_check_details); |
4160 if (not_at_start_) out_of_line_trace.set_at_start(Trace::FALSE); | 4164 if (not_at_start_) out_of_line_trace.set_at_start(Trace::FALSE_LITERAL); |
4161 ZoneList<Guard*>* guards = alternative.guards(); | 4165 ZoneList<Guard*>* guards = alternative.guards(); |
4162 int guard_count = (guards == NULL) ? 0 : guards->length(); | 4166 int guard_count = (guards == NULL) ? 0 : guards->length(); |
4163 if (next_expects_preload) { | 4167 if (next_expects_preload) { |
4164 Label reload_current_char; | 4168 Label reload_current_char; |
4165 out_of_line_trace.set_backtrack(&reload_current_char); | 4169 out_of_line_trace.set_backtrack(&reload_current_char); |
4166 for (int j = 0; j < guard_count; j++) { | 4170 for (int j = 0; j < guard_count; j++) { |
4167 GenerateGuard(macro_assembler, guards->at(j), &out_of_line_trace); | 4171 GenerateGuard(macro_assembler, guards->at(j), &out_of_line_trace); |
4168 } | 4172 } |
4169 alternative.node()->Emit(compiler, &out_of_line_trace); | 4173 alternative.node()->Emit(compiler, &out_of_line_trace); |
4170 macro_assembler->Bind(&reload_current_char); | 4174 macro_assembler->Bind(&reload_current_char); |
(...skipping 1950 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
6121 } | 6125 } |
6122 | 6126 |
6123 return compiler.Assemble(¯o_assembler, | 6127 return compiler.Assemble(¯o_assembler, |
6124 node, | 6128 node, |
6125 data->capture_count, | 6129 data->capture_count, |
6126 pattern); | 6130 pattern); |
6127 } | 6131 } |
6128 | 6132 |
6129 | 6133 |
6130 }} // namespace v8::internal | 6134 }} // namespace v8::internal |
OLD | NEW |