Revision: 10422
Author: [email protected]
Date: Tue Jan 17 06:29:17 2012
Log: Recursion limit for one-char string replace and retire
String::kMinNonFlatLength.
TEST=mjsunit/string-replace-one-char.js
Review URL: https://chromiumcodereview.appspot.com/9231017
http://code.google.com/p/v8/source/detail?r=10422
Added:
/branches/bleeding_edge/test/mjsunit/string-replace-one-char.js
Modified:
/branches/bleeding_edge/src/arm/code-stubs-arm.cc
/branches/bleeding_edge/src/heap.cc
/branches/bleeding_edge/src/ia32/code-stubs-ia32.cc
/branches/bleeding_edge/src/mips/code-stubs-mips.cc
/branches/bleeding_edge/src/objects-debug.cc
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/src/runtime.cc
/branches/bleeding_edge/src/runtime.h
/branches/bleeding_edge/src/string.js
/branches/bleeding_edge/src/x64/code-stubs-x64.cc
/branches/bleeding_edge/test/cctest/test-strings.cc
=======================================
--- /dev/null
+++ /branches/bleeding_edge/test/mjsunit/string-replace-one-char.js Tue Jan
17 06:29:17 2012
@@ -0,0 +1,92 @@
+// Copyright 2012 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// Make sure the strings are long enough to trigger the one-char string
replace.
+var prefix1024 = "0123456789ABCDEF";
+for (var i = 0; i < 6; i++) prefix1024 += prefix1024;
+
+function test_replace(result, expected, search, replace) {
+ assertEquals(expected, result.replace(search, replace));
+}
+
+// '$' in the replace string.
+test_replace(prefix1024 + "abcdefghijklmnopqrstuvwxyz",
+ prefix1024 + "abcdefghijk#l#mnopqrstuvwxyz",
+ "l", "#$&#");
+
+test_replace(prefix1024 + "abcdefghijklmnopqrstuvwxyz\u1234",
+ prefix1024 + "abcdefghijk\u2012l\u2012mnopqrstuvwxyz\u1234",
+ "l", "\u2012$&\u2012");
+
+test_replace(prefix1024 + "abcdefghijklmnopqrstuvwxyz",
+ prefix1024 + "abcdefghijk$mnopqrstuvwxyz",
+ "l", "$$");
+
+test_replace(prefix1024 + "abcdefghijklmnopqrstuvwxyz\u1234",
+ prefix1024 + "abcdefghijk$mnopqrstuvwxyz\u1234",
+ "l", "$$");
+
+// Zero length replace string.
+test_replace(prefix1024 + "abcdefghijklmnopqrstuvwxyz",
+ prefix1024 + "abcdefghijklmnopqstuvwxyz",
+ "r", "");
+
+test_replace(prefix1024 + "abcdefghijklmnopq\u1234stuvwxyz",
+ prefix1024 + "abcdefghijklmnopqstuvwxyz",
+ "\u1234", "");
+
+// Search char not found.
+var not_found_1 = prefix1024 + "abcdefghijklmnopqrstuvwxyz";
+test_replace(not_found_1, not_found_1, "+", "-");
+
+var not_found_2 = prefix1024 + "abcdefghijklm\u1234nopqrstuvwxyz";
+test_replace(not_found_2, not_found_2, "+", "---");
+
+var not_found_3 = prefix1024 + "abcdefghijklmnopqrstuvwxyz";
+test_replace(not_found_3, not_found_3, "\u1234", "ZZZ");
+
+// Deep cons tree.
+var nested_1 = "";
+for (var i = 0; i < 1000000; i++) nested_1 += "y";
+var nested_1_result = prefix1024 + nested_1 + "aa";
+nested_1 = prefix1024 + nested_1 + "z";
+test_replace(nested_1, nested_1_result, "z", "aa");
+
+var nested_2 = "\u2244";
+for (var i = 0; i < 1000000; i++) nested_2 += "y";
+var nested_2_result = prefix1024 + nested_2 + "aa";
+nested_2 = prefix1024 + nested_2 + "\u2012";
+test_replace(nested_2, nested_2_result, "\u2012", "aa");
+
+// Sliced string as input. A cons string is always flattened before
sliced.
+var slice_1 = ("ab" + prefix1024 + "cdefghijklmnopqrstuvwxyz").slice(1,
-1);
+var slice_1_result = "b" + prefix1024 + "cdefghijklmnopqrstuvwxQ";
+test_replace(slice_1, slice_1_result, "y", "Q");
+
+var slice_2 = (prefix1024 + "abcdefghijklmno\u1234\u1234p").slice(1, -1);
+var slice_2_result = prefix1024.substr(1) + "abcdefghijklmnoQ\u1234";
+test_replace(slice_2, slice_2_result, "\u1234", "Q");
=======================================
--- /branches/bleeding_edge/src/arm/code-stubs-arm.cc Mon Jan 16 04:38:59
2012
+++ /branches/bleeding_edge/src/arm/code-stubs-arm.cc Tue Jan 17 06:29:17
2012
@@ -6268,7 +6268,7 @@
__ bind(&longer_than_two);
// Check if resulting string will be flat.
- __ cmp(r6, Operand(String::kMinNonFlatLength));
+ __ cmp(r6, Operand(ConsString::kMinLength));
__ b(lt, &string_add_flat_result);
// Handle exceptionally long strings in the runtime system.
STATIC_ASSERT((String::kMaxLength & 0x80000000) == 0);
@@ -6322,7 +6322,7 @@
__ jmp(&allocated);
// We cannot encounter sliced strings or cons strings here since:
- STATIC_ASSERT(SlicedString::kMinLength >= String::kMinNonFlatLength);
+ STATIC_ASSERT(SlicedString::kMinLength >= ConsString::kMinLength);
// Handle creating a flat result from either external or sequential
strings.
// Locate the first characters' locations.
// r0: first string
=======================================
--- /branches/bleeding_edge/src/heap.cc Tue Jan 17 05:13:55 2012
+++ /branches/bleeding_edge/src/heap.cc Tue Jan 17 06:29:17 2012
@@ -2933,9 +2933,9 @@
}
// If the resulting string is small make a flat string.
- if (length < String::kMinNonFlatLength) {
+ if (length < ConsString::kMinLength) {
// Note that neither of the two inputs can be a slice because:
- STATIC_ASSERT(String::kMinNonFlatLength <= SlicedString::kMinLength);
+ STATIC_ASSERT(ConsString::kMinLength <= SlicedString::kMinLength);
ASSERT(first->IsFlat());
ASSERT(second->IsFlat());
if (is_ascii) {
=======================================
--- /branches/bleeding_edge/src/ia32/code-stubs-ia32.cc Mon Jan 16 04:38:59
2012
+++ /branches/bleeding_edge/src/ia32/code-stubs-ia32.cc Tue Jan 17 06:29:17
2012
@@ -5585,7 +5585,7 @@
__ bind(&longer_than_two);
// Check if resulting string will be flat.
- __ cmp(ebx, Immediate(Smi::FromInt(String::kMinNonFlatLength)));
+ __ cmp(ebx, Immediate(Smi::FromInt(ConsString::kMinLength)));
__ j(below, &string_add_flat_result);
// If result is not supposed to be flat allocate a cons string object.
If both
@@ -5633,7 +5633,7 @@
__ jmp(&allocated);
// We cannot encounter sliced strings or cons strings here since:
- STATIC_ASSERT(SlicedString::kMinLength >= String::kMinNonFlatLength);
+ STATIC_ASSERT(SlicedString::kMinLength >= ConsString::kMinLength);
// Handle creating a flat result from either external or sequential
strings.
// Locate the first characters' locations.
// eax: first string
=======================================
--- /branches/bleeding_edge/src/mips/code-stubs-mips.cc Mon Jan 16 04:38:59
2012
+++ /branches/bleeding_edge/src/mips/code-stubs-mips.cc Tue Jan 17 06:29:17
2012
@@ -6491,7 +6491,7 @@
__ bind(&longer_than_two);
// Check if resulting string will be flat.
__ Branch(&string_add_flat_result, lt, t2,
- Operand(String::kMinNonFlatLength));
+ Operand(ConsString::kMinLength));
// Handle exceptionally long strings in the runtime system.
STATIC_ASSERT((String::kMaxLength & 0x80000000) == 0);
ASSERT(IsPowerOf2(String::kMaxLength + 1));
@@ -6543,7 +6543,7 @@
__ Branch(&allocated);
// We cannot encounter sliced strings or cons strings here since:
- STATIC_ASSERT(SlicedString::kMinLength >= String::kMinNonFlatLength);
+ STATIC_ASSERT(SlicedString::kMinLength >= ConsString::kMinLength);
// Handle creating a flat result from either external or sequential
strings.
// Locate the first characters' locations.
// a0: first string
=======================================
--- /branches/bleeding_edge/src/objects-debug.cc Mon Jan 16 01:44:35 2012
+++ /branches/bleeding_edge/src/objects-debug.cc Tue Jan 17 06:29:17 2012
@@ -388,7 +388,7 @@
CHECK(this->first()->IsString());
CHECK(this->second() == GetHeap()->empty_string() ||
this->second()->IsString());
- CHECK(this->length() >= String::kMinNonFlatLength);
+ CHECK(this->length() >= ConsString::kMinLength);
if (this->IsFlat()) {
// A flat cons can only be created by String::SlowTryFlatten.
// Afterwards, the first part may be externalized.
=======================================
--- /branches/bleeding_edge/src/objects.h Mon Jan 16 04:38:59 2012
+++ /branches/bleeding_edge/src/objects.h Tue Jan 17 06:29:17 2012
@@ -6591,9 +6591,6 @@
static const unsigned kMaxAsciiCharCodeU =
unibrow::Utf8::kMaxOneByteChar;
static const int kMaxUC16CharCode = 0xffff;
- // Minimum length for a cons string.
- static const int kMinNonFlatLength = 13;
-
// Mask constant for checking if a string has a computed hash code
// and if it is an array index. The least significant bit indicates
// whether a hash code has been computed. If the hash code has been
=======================================
--- /branches/bleeding_edge/src/runtime.cc Mon Jan 16 07:21:38 2012
+++ /branches/bleeding_edge/src/runtime.cc Tue Jan 17 06:29:17 2012
@@ -3237,26 +3237,34 @@
Handle<String>
subject,
Handle<String>
search,
Handle<String>
replace,
- bool* found) {
+ bool* found,
+ int
recursion_limit) {
+ if (recursion_limit == 0) return Handle<String>::null();
if (subject->IsConsString()) {
ConsString* cons = ConsString::cast(*subject);
Handle<String> first = Handle<String>(cons->first());
Handle<String> second = Handle<String>(cons->second());
- Handle<String> new_first = StringReplaceOneCharWithString(isolate,
- first,
- search,
- replace,
- found);
- if (*found) {
- return isolate->factory()->NewConsString(new_first, second);
- } else {
- Handle<String> new_second = StringReplaceOneCharWithString(isolate,
- second,
- search,
- replace,
- found);
- return isolate->factory()->NewConsString(first, new_second);
- }
+ Handle<String> new_first =
+ StringReplaceOneCharWithString(isolate,
+ first,
+ search,
+ replace,
+ found,
+ recursion_limit - 1);
+ if (*found) return isolate->factory()->NewConsString(new_first,
second);
+ if (new_first.is_null()) return new_first;
+
+ Handle<String> new_second =
+ StringReplaceOneCharWithString(isolate,
+ second,
+ search,
+ replace,
+ found,
+ recursion_limit - 1);
+ if (*found) return isolate->factory()->NewConsString(first,
new_second);
+ if (new_second.is_null()) return new_second;
+
+ return subject;
} else {
int index = StringMatch(isolate, subject, search, 0);
if (index == -1) return subject;
@@ -3276,13 +3284,25 @@
CONVERT_ARG_CHECKED(String, subject, 0);
CONVERT_ARG_CHECKED(String, search, 1);
CONVERT_ARG_CHECKED(String, replace, 2);
- bool found = false;
-
- return *(Runtime::StringReplaceOneCharWithString(isolate,
- subject,
- search,
- replace,
- &found));
+
+ // If the cons string tree is too deep, we simply abort the recursion and
+ // retry with a flattened subject string.
+ const int kRecursionLimit = 0x1000;
+ bool found = false;
+ Handle<String> result =
+ Runtime::StringReplaceOneCharWithString(isolate,
+ subject,
+ search,
+ replace,
+ &found,
+ kRecursionLimit);
+ if (!result.is_null()) return *result;
+ return *Runtime::StringReplaceOneCharWithString(isolate,
+
FlattenGetString(subject),
+ search,
+ replace,
+ &found,
+ kRecursionLimit);
}
=======================================
--- /branches/bleeding_edge/src/runtime.h Mon Jan 16 07:21:38 2012
+++ /branches/bleeding_edge/src/runtime.h Tue Jan 17 06:29:17 2012
@@ -634,7 +634,8 @@
Handle<String>
subject,
Handle<String>
search,
Handle<String>
replace,
- bool* found);
+ bool* found,
+ int
recursion_limit);
// General-purpose helper functions for runtime system.
static int StringMatch(Isolate* isolate,
=======================================
--- /branches/bleeding_edge/src/string.js Mon Jan 16 07:21:38 2012
+++ /branches/bleeding_edge/src/string.js Tue Jan 17 06:29:17 2012
@@ -245,8 +245,12 @@
// Convert the search argument to a string and search for it.
search = TO_STRING_INLINE(search);
if (search.length == 1 &&
+ subject.length > 0xFF &&
IS_STRING(replace) &&
%StringIndexOf(replace, '$', 0) < 0) {
+ // Searching by traversing a cons string tree and replace with cons of
+ // slices works only when the replaced string is a single character,
being
+ // replaced by a simple string and only pays off for long strings.
return %StringReplaceOneCharWithString(subject, search, replace);
}
var start = %StringIndexOf(subject, search, 0);
=======================================
--- /branches/bleeding_edge/src/x64/code-stubs-x64.cc Mon Jan 16 07:11:56
2012
+++ /branches/bleeding_edge/src/x64/code-stubs-x64.cc Tue Jan 17 06:29:17
2012
@@ -4547,7 +4547,7 @@
__ bind(&longer_than_two);
// Check if resulting string will be flat.
- __ SmiCompare(rbx, Smi::FromInt(String::kMinNonFlatLength));
+ __ SmiCompare(rbx, Smi::FromInt(ConsString::kMinLength));
__ j(below, &string_add_flat_result);
// Handle exceptionally long strings in the runtime system.
STATIC_ASSERT((String::kMaxLength & 0x80000000) == 0);
@@ -4599,7 +4599,7 @@
__ jmp(&allocated);
// We cannot encounter sliced strings or cons strings here since:
- STATIC_ASSERT(SlicedString::kMinLength >= String::kMinNonFlatLength);
+ STATIC_ASSERT(SlicedString::kMinLength >= ConsString::kMinLength);
// Handle creating a flat result from either external or sequential
strings.
// Locate the first characters' locations.
// rax: first string
=======================================
--- /branches/bleeding_edge/test/cctest/test-strings.cc Thu Sep 15 05:47:06
2011
+++ /branches/bleeding_edge/test/cctest/test-strings.cc Tue Jan 17 06:29:17
2012
@@ -355,7 +355,7 @@
// Make sure we cover all always-flat lengths and at least one above.
static const int kMaxLength = 20;
- CHECK_GT(kMaxLength, i::String::kMinNonFlatLength);
+ CHECK_GT(kMaxLength, i::ConsString::kMinLength);
// Allocate two JavaScript arrays for holding short strings.
v8::Handle<v8::Array> ascii_external_strings =
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
