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 2394 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
2405 } | 2405 } |
2406 | 2406 |
2407 int length() { | 2407 int length() { |
2408 return length_; | 2408 return length_; |
2409 } | 2409 } |
2410 | 2410 |
2411 int capacity() { | 2411 int capacity() { |
2412 return array_->length(); | 2412 return array_->length(); |
2413 } | 2413 } |
2414 | 2414 |
2415 Handle<JSArray> ToJSArray() { | |
2416 Handle<JSArray> result_array = FACTORY->NewJSArrayWithElements(array_); | |
2417 result_array->set_length(Smi::FromInt(length_)); | |
2418 return result_array; | |
2419 } | |
2420 | |
2421 Handle<JSArray> ToJSArray(Handle<JSArray> target_array) { | 2415 Handle<JSArray> ToJSArray(Handle<JSArray> target_array) { |
2422 FACTORY->SetContent(target_array, array_); | 2416 FACTORY->SetContent(target_array, array_); |
2423 target_array->set_length(Smi::FromInt(length_)); | 2417 target_array->set_length(Smi::FromInt(length_)); |
2424 return target_array; | 2418 return target_array; |
2425 } | 2419 } |
2426 | 2420 |
2421 | |
2422 static int GetFinalLength(Handle<FixedArray> array) { | |
ulan
2012/08/31 08:52:51
It can be removed now.
| |
2423 // Get final length from last element. | |
2424 return Smi::cast(array->get(array->length() - 1))->value(); | |
2425 } | |
2426 | |
2427 | |
2427 private: | 2428 private: |
2428 Handle<FixedArray> array_; | 2429 Handle<FixedArray> array_; |
2429 int length_; | 2430 int length_; |
2430 bool has_non_smi_elements_; | 2431 bool has_non_smi_elements_; |
2431 }; | 2432 }; |
2432 | 2433 |
2433 | 2434 |
2434 // Forward declarations. | 2435 // Forward declarations. |
2435 const int kStringBuilderConcatHelperLengthBits = 11; | 2436 const int kStringBuilderConcatHelperLengthBits = 11; |
2436 const int kStringBuilderConcatHelperPositionBits = 19; | 2437 const int kStringBuilderConcatHelperPositionBits = 19; |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
2535 } | 2536 } |
2536 | 2537 |
2537 | 2538 |
2538 void IncrementCharacterCount(int by) { | 2539 void IncrementCharacterCount(int by) { |
2539 if (character_count_ > String::kMaxLength - by) { | 2540 if (character_count_ > String::kMaxLength - by) { |
2540 V8::FatalProcessOutOfMemory("String.replace result too large."); | 2541 V8::FatalProcessOutOfMemory("String.replace result too large."); |
2541 } | 2542 } |
2542 character_count_ += by; | 2543 character_count_ += by; |
2543 } | 2544 } |
2544 | 2545 |
2545 Handle<JSArray> GetParts() { | |
2546 return array_builder_.ToJSArray(); | |
2547 } | |
2548 | |
2549 private: | 2546 private: |
2550 Handle<SeqAsciiString> NewRawAsciiString(int length) { | 2547 Handle<SeqAsciiString> NewRawAsciiString(int length) { |
2551 return heap_->isolate()->factory()->NewRawAsciiString(length); | 2548 return heap_->isolate()->factory()->NewRawAsciiString(length); |
2552 } | 2549 } |
2553 | 2550 |
2554 | 2551 |
2555 Handle<SeqTwoByteString> NewRawTwoByteString(int length) { | 2552 Handle<SeqTwoByteString> NewRawTwoByteString(int length) { |
2556 return heap_->isolate()->factory()->NewRawTwoByteString(length); | 2553 return heap_->isolate()->factory()->NewRawTwoByteString(length); |
2557 } | 2554 } |
2558 | 2555 |
(...skipping 1100 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
3659 } | 3656 } |
3660 Handle<JSArray> result = isolate->factory()->NewJSArrayWithElements(elements); | 3657 Handle<JSArray> result = isolate->factory()->NewJSArrayWithElements(elements); |
3661 result->set_length(Smi::FromInt(matches)); | 3658 result->set_length(Smi::FromInt(matches)); |
3662 return *result; | 3659 return *result; |
3663 } | 3660 } |
3664 | 3661 |
3665 | 3662 |
3666 // Only called from Runtime_RegExpExecMultiple so it doesn't need to maintain | 3663 // Only called from Runtime_RegExpExecMultiple so it doesn't need to maintain |
3667 // separate last match info. See comment on that function. | 3664 // separate last match info. See comment on that function. |
3668 template<bool has_capture> | 3665 template<bool has_capture> |
3669 static int SearchRegExpMultiple( | 3666 static MaybeObject* SearchRegExpMultiple( |
3670 Isolate* isolate, | 3667 Isolate* isolate, |
3671 Handle<String> subject, | 3668 Handle<String> subject, |
3672 Handle<JSRegExp> regexp, | 3669 Handle<JSRegExp> regexp, |
3673 Handle<JSArray> last_match_array, | 3670 Handle<JSArray> last_match_array, |
3674 FixedArrayBuilder* builder) { | 3671 Handle<JSArray> result_array) { |
3675 ASSERT(subject->IsFlat()); | 3672 ASSERT(subject->IsFlat()); |
3676 ASSERT_NE(has_capture, regexp->CaptureCount() == 0); | 3673 ASSERT_NE(has_capture, regexp->CaptureCount() == 0); |
3677 | 3674 |
3678 RegExpImpl::GlobalCache global_cache(regexp, subject, true, isolate); | |
3679 if (global_cache.HasException()) return RegExpImpl::RE_EXCEPTION; | |
3680 | |
3681 int capture_count = regexp->CaptureCount(); | 3675 int capture_count = regexp->CaptureCount(); |
3682 int subject_length = subject->length(); | 3676 int subject_length = subject->length(); |
3683 | 3677 |
3678 static const int kMinLengthToCache = 0x1000; | |
3679 | |
3680 if (subject_length > kMinLengthToCache) { | |
3681 Handle<Object> cached_answer(RegExpResultsCache::Lookup( | |
3682 isolate->heap(), | |
3683 *subject, | |
3684 regexp->data(), | |
3685 RegExpResultsCache::REGEXP_MULTIPLE_INDICES)); | |
3686 if (*cached_answer != Smi::FromInt(0)) { | |
3687 Handle<FixedArray> cached_fixed_array = | |
3688 Handle<FixedArray>(FixedArray::cast(*cached_answer)); | |
3689 // The cache FixedArray is a COW-array and can therefore be reused. | |
3690 isolate->factory()->SetContent(result_array, cached_fixed_array); | |
3691 // The actual length of the result array is stored in the last element of | |
3692 // the backing store (the backing FixedArray may have a larger capacity). | |
3693 Object* cached_fixed_array_last_element = | |
3694 cached_fixed_array->get(cached_fixed_array->length() - 1); | |
3695 Smi* js_array_length = Smi::cast(cached_fixed_array_last_element); | |
3696 result_array->set_length(js_array_length); | |
3697 RegExpImpl::SetLastMatchInfo( | |
3698 last_match_array, subject, capture_count, NULL); | |
3699 return *result_array; | |
3700 } | |
3701 } | |
3702 | |
3703 RegExpImpl::GlobalCache global_cache(regexp, subject, true, isolate); | |
3704 if (global_cache.HasException()) return Failure::Exception(); | |
3705 | |
3706 Handle<FixedArray> result_elements; | |
3707 if (result_array->HasFastObjectElements()) { | |
3708 result_elements = | |
3709 Handle<FixedArray>(FixedArray::cast(result_array->elements())); | |
3710 } | |
3711 if (result_elements.is_null() || result_elements->length() < 16) { | |
3712 result_elements = isolate->factory()->NewFixedArrayWithHoles(16); | |
3713 } | |
3714 | |
3715 FixedArrayBuilder builder(result_elements); | |
3716 | |
3684 // Position to search from. | 3717 // Position to search from. |
3685 int match_start = -1; | 3718 int match_start = -1; |
3686 int match_end = 0; | 3719 int match_end = 0; |
3687 bool first = true; | 3720 bool first = true; |
3688 | 3721 |
3689 // Two smis before and after the match, for very long strings. | 3722 // Two smis before and after the match, for very long strings. |
3690 static const int kMaxBuilderEntriesPerRegExpMatch = 5; | 3723 static const int kMaxBuilderEntriesPerRegExpMatch = 5; |
3691 | 3724 |
3692 while (true) { | 3725 while (true) { |
3693 int32_t* current_match = global_cache.FetchNext(); | 3726 int32_t* current_match = global_cache.FetchNext(); |
3694 if (current_match == NULL) break; | 3727 if (current_match == NULL) break; |
3695 match_start = current_match[0]; | 3728 match_start = current_match[0]; |
3696 builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch); | 3729 builder.EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch); |
3697 if (match_end < match_start) { | 3730 if (match_end < match_start) { |
3698 ReplacementStringBuilder::AddSubjectSlice(builder, | 3731 ReplacementStringBuilder::AddSubjectSlice(&builder, |
3699 match_end, | 3732 match_end, |
3700 match_start); | 3733 match_start); |
3701 } | 3734 } |
3702 match_end = current_match[1]; | 3735 match_end = current_match[1]; |
3703 { | 3736 { |
3704 // Avoid accumulating new handles inside loop. | 3737 // Avoid accumulating new handles inside loop. |
3705 HandleScope temp_scope(isolate); | 3738 HandleScope temp_scope(isolate); |
3706 Handle<String> match; | 3739 Handle<String> match; |
3707 if (!first) { | 3740 if (!first) { |
3708 match = isolate->factory()->NewProperSubString(subject, | 3741 match = isolate->factory()->NewProperSubString(subject, |
(...skipping 21 matching lines...) Expand all Loading... | |
3730 Handle<String> substring = | 3763 Handle<String> substring = |
3731 isolate->factory()->NewSubString(subject, start, end); | 3764 isolate->factory()->NewSubString(subject, start, end); |
3732 elements->set(i, *substring); | 3765 elements->set(i, *substring); |
3733 } else { | 3766 } else { |
3734 ASSERT(current_match[i * 2 + 1] < 0); | 3767 ASSERT(current_match[i * 2 + 1] < 0); |
3735 elements->set(i, isolate->heap()->undefined_value()); | 3768 elements->set(i, isolate->heap()->undefined_value()); |
3736 } | 3769 } |
3737 } | 3770 } |
3738 elements->set(capture_count + 1, Smi::FromInt(match_start)); | 3771 elements->set(capture_count + 1, Smi::FromInt(match_start)); |
3739 elements->set(capture_count + 2, *subject); | 3772 elements->set(capture_count + 2, *subject); |
3740 builder->Add(*isolate->factory()->NewJSArrayWithElements(elements)); | 3773 builder.Add(*isolate->factory()->NewJSArrayWithElements(elements)); |
3741 } else { | 3774 } else { |
3742 builder->Add(*match); | 3775 builder.Add(*match); |
3743 } | 3776 } |
3744 } | 3777 } |
3745 } | 3778 } |
3746 | 3779 |
3747 if (global_cache.HasException()) return RegExpImpl::RE_EXCEPTION; | 3780 if (global_cache.HasException()) return Failure::Exception(); |
3748 | 3781 |
3749 if (match_start >= 0) { | 3782 if (match_start >= 0) { |
3750 // Finished matching, with at least one match. | 3783 // Finished matching, with at least one match. |
3751 if (match_end < subject_length) { | 3784 if (match_end < subject_length) { |
3752 ReplacementStringBuilder::AddSubjectSlice(builder, | 3785 ReplacementStringBuilder::AddSubjectSlice(&builder, |
3753 match_end, | 3786 match_end, |
3754 subject_length); | 3787 subject_length); |
3755 } | 3788 } |
3756 | 3789 |
3757 RegExpImpl::SetLastMatchInfo( | 3790 RegExpImpl::SetLastMatchInfo( |
3758 last_match_array, subject, capture_count, NULL); | 3791 last_match_array, subject, capture_count, NULL); |
3759 | 3792 |
3760 return RegExpImpl::RE_SUCCESS; | 3793 if (subject_length > kMinLengthToCache) { |
3794 // Store the length of the result array into the last element of the | |
3795 // backing FixedArray. | |
3796 builder.EnsureCapacity(1); | |
3797 Handle<FixedArray> fixed_array = builder.array(); | |
3798 fixed_array->set(fixed_array->length() - 1, | |
3799 Smi::FromInt(builder.length())); | |
3800 // Cache the result and turn the FixedArray into a COW array. | |
3801 RegExpResultsCache::Enter(isolate->heap(), | |
3802 *subject, | |
3803 regexp->data(), | |
3804 *fixed_array, | |
3805 RegExpResultsCache::REGEXP_MULTIPLE_INDICES); | |
3806 } | |
3807 return *builder.ToJSArray(result_array); | |
3761 } else { | 3808 } else { |
3762 return RegExpImpl::RE_FAILURE; // No matches at all. | 3809 return isolate->heap()->null_value(); // No matches at all. |
3763 } | 3810 } |
3764 } | 3811 } |
3765 | 3812 |
3766 | 3813 |
3767 // This is only called for StringReplaceGlobalRegExpWithFunction. This sets | 3814 // This is only called for StringReplaceGlobalRegExpWithFunction. This sets |
3768 // lastMatchInfoOverride to maintain the last match info, so we don't need to | 3815 // lastMatchInfoOverride to maintain the last match info, so we don't need to |
3769 // set any other last match array info. | 3816 // set any other last match array info. |
3770 RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpExecMultiple) { | 3817 RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpExecMultiple) { |
3771 ASSERT(args.length() == 4); | 3818 ASSERT(args.length() == 4); |
3772 HandleScope handles(isolate); | 3819 HandleScope handles(isolate); |
3773 | 3820 |
3774 CONVERT_ARG_HANDLE_CHECKED(String, subject, 1); | 3821 CONVERT_ARG_HANDLE_CHECKED(String, subject, 1); |
3775 if (!subject->IsFlat()) FlattenString(subject); | 3822 if (!subject->IsFlat()) FlattenString(subject); |
3776 CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0); | 3823 CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0); |
3777 CONVERT_ARG_HANDLE_CHECKED(JSArray, last_match_info, 2); | 3824 CONVERT_ARG_HANDLE_CHECKED(JSArray, last_match_info, 2); |
3778 CONVERT_ARG_HANDLE_CHECKED(JSArray, result_array, 3); | 3825 CONVERT_ARG_HANDLE_CHECKED(JSArray, result_array, 3); |
3779 | 3826 |
3780 ASSERT(last_match_info->HasFastObjectElements()); | 3827 ASSERT(last_match_info->HasFastObjectElements()); |
3781 ASSERT(regexp->GetFlags().is_global()); | 3828 ASSERT(regexp->GetFlags().is_global()); |
3782 Handle<FixedArray> result_elements; | 3829 |
3783 if (result_array->HasFastObjectElements()) { | 3830 if (regexp->CaptureCount() == 0) { |
3784 result_elements = | 3831 return SearchRegExpMultiple<false>( |
3785 Handle<FixedArray>(FixedArray::cast(result_array->elements())); | 3832 isolate, subject, regexp, last_match_info, result_array); |
3833 } else { | |
3834 return SearchRegExpMultiple<true>( | |
3835 isolate, subject, regexp, last_match_info, result_array); | |
3786 } | 3836 } |
3787 if (result_elements.is_null() || result_elements->length() < 16) { | |
3788 result_elements = isolate->factory()->NewFixedArrayWithHoles(16); | |
3789 } | |
3790 FixedArrayBuilder builder(result_elements); | |
3791 | |
3792 int result; | |
3793 if (regexp->CaptureCount() == 0) { | |
3794 result = SearchRegExpMultiple<false>( | |
3795 isolate, subject, regexp, last_match_info, &builder); | |
3796 } else { | |
3797 result = SearchRegExpMultiple<true>( | |
3798 isolate, subject, regexp, last_match_info, &builder); | |
3799 } | |
3800 | |
3801 if (result == RegExpImpl::RE_SUCCESS) return *builder.ToJSArray(result_array); | |
3802 if (result == RegExpImpl::RE_FAILURE) return isolate->heap()->null_value(); | |
3803 ASSERT_EQ(result, RegExpImpl::RE_EXCEPTION); | |
3804 return Failure::Exception(); | |
3805 } | 3837 } |
3806 | 3838 |
3807 | 3839 |
3808 RUNTIME_FUNCTION(MaybeObject*, Runtime_NumberToRadixString) { | 3840 RUNTIME_FUNCTION(MaybeObject*, Runtime_NumberToRadixString) { |
3809 NoHandleAllocation ha; | 3841 NoHandleAllocation ha; |
3810 ASSERT(args.length() == 2); | 3842 ASSERT(args.length() == 2); |
3811 CONVERT_SMI_ARG_CHECKED(radix, 1); | 3843 CONVERT_SMI_ARG_CHECKED(radix, 1); |
3812 RUNTIME_ASSERT(2 <= radix && radix <= 36); | 3844 RUNTIME_ASSERT(2 <= radix && radix <= 36); |
3813 | 3845 |
3814 // Fast case where the result is a one character string. | 3846 // Fast case where the result is a one character string. |
(...skipping 2296 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
6111 HandleScope handle_scope(isolate); | 6143 HandleScope handle_scope(isolate); |
6112 CONVERT_ARG_HANDLE_CHECKED(String, subject, 0); | 6144 CONVERT_ARG_HANDLE_CHECKED(String, subject, 0); |
6113 CONVERT_ARG_HANDLE_CHECKED(String, pattern, 1); | 6145 CONVERT_ARG_HANDLE_CHECKED(String, pattern, 1); |
6114 CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[2]); | 6146 CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[2]); |
6115 | 6147 |
6116 int subject_length = subject->length(); | 6148 int subject_length = subject->length(); |
6117 int pattern_length = pattern->length(); | 6149 int pattern_length = pattern->length(); |
6118 RUNTIME_ASSERT(pattern_length > 0); | 6150 RUNTIME_ASSERT(pattern_length > 0); |
6119 | 6151 |
6120 if (limit == 0xffffffffu) { | 6152 if (limit == 0xffffffffu) { |
6121 Handle<Object> cached_answer(StringSplitCache::Lookup( | 6153 Handle<Object> cached_answer(RegExpResultsCache::Lookup( |
6122 isolate->heap()->string_split_cache(), | 6154 isolate->heap(), |
6123 *subject, | 6155 *subject, |
6124 *pattern)); | 6156 *pattern, |
6157 RegExpResultsCache::STRING_SPLIT_SUBSTRINGS)); | |
6125 if (*cached_answer != Smi::FromInt(0)) { | 6158 if (*cached_answer != Smi::FromInt(0)) { |
6159 // The cache FixedArray is a COW-array and can therefore be reused. | |
6126 Handle<JSArray> result = | 6160 Handle<JSArray> result = |
6127 isolate->factory()->NewJSArrayWithElements( | 6161 isolate->factory()->NewJSArrayWithElements( |
6128 Handle<FixedArray>::cast(cached_answer)); | 6162 Handle<FixedArray>::cast(cached_answer)); |
6129 return *result; | 6163 return *result; |
6130 } | 6164 } |
6131 } | 6165 } |
6132 | 6166 |
6133 // The limit can be very large (0xffffffffu), but since the pattern | 6167 // The limit can be very large (0xffffffffu), but since the pattern |
6134 // isn't empty, we can never create more parts than ~half the length | 6168 // isn't empty, we can never create more parts than ~half the length |
6135 // of the subject. | 6169 // of the subject. |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
6175 HandleScope local_loop_handle; | 6209 HandleScope local_loop_handle; |
6176 int part_end = indices.at(i); | 6210 int part_end = indices.at(i); |
6177 Handle<String> substring = | 6211 Handle<String> substring = |
6178 isolate->factory()->NewProperSubString(subject, part_start, part_end); | 6212 isolate->factory()->NewProperSubString(subject, part_start, part_end); |
6179 elements->set(i, *substring); | 6213 elements->set(i, *substring); |
6180 part_start = part_end + pattern_length; | 6214 part_start = part_end + pattern_length; |
6181 } | 6215 } |
6182 | 6216 |
6183 if (limit == 0xffffffffu) { | 6217 if (limit == 0xffffffffu) { |
6184 if (result->HasFastObjectElements()) { | 6218 if (result->HasFastObjectElements()) { |
6185 StringSplitCache::Enter(isolate->heap(), | 6219 RegExpResultsCache::Enter(isolate->heap(), |
6186 isolate->heap()->string_split_cache(), | 6220 *subject, |
6187 *subject, | 6221 *pattern, |
6188 *pattern, | 6222 *elements, |
6189 *elements); | 6223 RegExpResultsCache::STRING_SPLIT_SUBSTRINGS); |
6190 } | 6224 } |
6191 } | 6225 } |
6192 | 6226 |
6193 return *result; | 6227 return *result; |
6194 } | 6228 } |
6195 | 6229 |
6196 | 6230 |
6197 // Copies ASCII characters to the given fixed array looking up | 6231 // Copies ASCII characters to the given fixed array looking up |
6198 // one-char strings in the cache. Gives up on the first char that is | 6232 // one-char strings in the cache. Gives up on the first char that is |
6199 // not in the cache and fills the remainder with smi zeros. Returns | 6233 // not in the cache and fills the remainder with smi zeros. Returns |
(...skipping 7147 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
13347 // Handle last resort GC and make sure to allow future allocations | 13381 // Handle last resort GC and make sure to allow future allocations |
13348 // to grow the heap without causing GCs (if possible). | 13382 // to grow the heap without causing GCs (if possible). |
13349 isolate->counters()->gc_last_resort_from_js()->Increment(); | 13383 isolate->counters()->gc_last_resort_from_js()->Increment(); |
13350 isolate->heap()->CollectAllGarbage(Heap::kNoGCFlags, | 13384 isolate->heap()->CollectAllGarbage(Heap::kNoGCFlags, |
13351 "Runtime::PerformGC"); | 13385 "Runtime::PerformGC"); |
13352 } | 13386 } |
13353 } | 13387 } |
13354 | 13388 |
13355 | 13389 |
13356 } } // namespace v8::internal | 13390 } } // namespace v8::internal |
OLD | NEW |