From a5531459a4655f07df09915143f735afd6fe125d Mon Sep 17 00:00:00 2001 From: "yangguo@chromium.org" Date: Wed, 12 Nov 2014 08:04:41 +0000 Subject: [PATCH] Abstract string building in JSON-stringifier into IncrementalStringBuilder. R=ishell@chromium.org Review URL: https://codereview.chromium.org/713223002 Cr-Commit-Position: refs/heads/master@{#25276} git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@25276 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- BUILD.gn | 3 +- src/json-stringifier.h | 340 +++++++---------------------- src/runtime/runtime-regexp.cc | 2 +- src/runtime/runtime-strings.cc | 2 +- src/string-builder.cc | 111 ++++++++++ src/{runtime => }/string-builder.h | 206 ++++++++++++++--- tools/gyp/v8.gyp | 3 +- 7 files changed, 371 insertions(+), 296 deletions(-) create mode 100644 src/string-builder.cc rename src/{runtime => }/string-builder.h (62%) diff --git a/BUILD.gn b/BUILD.gn index f8384070e..11e8bf547 100644 --- a/BUILD.gn +++ b/BUILD.gn @@ -877,7 +877,6 @@ source_set("v8_base") { "src/runtime/runtime-utils.h", "src/runtime/runtime.cc", "src/runtime/runtime.h", - "src/runtime/string-builder.h", "src/safepoint-table.cc", "src/safepoint-table.h", "src/sampler.cc", @@ -897,6 +896,8 @@ source_set("v8_base") { "src/snapshot-source-sink.cc", "src/snapshot-source-sink.h", "src/snapshot.h", + "src/string-builder.h", + "src/string-builder.c", "src/string-search.cc", "src/string-search.h", "src/string-stream.cc", diff --git a/src/json-stringifier.h b/src/json-stringifier.h index 1ec6873b1..d28883fc5 100644 --- a/src/json-stringifier.h +++ b/src/json-stringifier.h @@ -8,6 +8,7 @@ #include "src/v8.h" #include "src/conversions.h" +#include "src/string-builder.h" #include "src/utils.h" namespace v8 { @@ -24,42 +25,8 @@ class BasicJsonStringifier BASE_EMBEDDED { Handle object)); private: - static const int kInitialPartLength = 32; - static const int kMaxPartLength = 16 * 1024; - static const int kPartLengthGrowthFactor = 2; - enum Result { UNCHANGED, SUCCESS, EXCEPTION }; - void Accumulate(); - - void Extend(); - - void ChangeEncoding(); - - INLINE(void ShrinkCurrentPart()); - - template - INLINE(void Append_(Char c)); - - template - INLINE(void Append_(const Char* chars)); - - INLINE(void Append(uint8_t c)) { - if (is_one_byte_) { - Append_(c); - } else { - Append_(c); - } - } - - INLINE(void AppendOneByte(const char* chars)) { - if (is_one_byte_) { - Append_(reinterpret_cast(chars)); - } else { - Append_(reinterpret_cast(chars)); - } - } - MUST_USE_RESULT MaybeHandle ApplyToJsonFunction( Handle object, Handle key); @@ -69,14 +36,9 @@ class BasicJsonStringifier BASE_EMBEDDED { bool deferred_comma, bool deferred_key); - template - INLINE(static Handle StringifyString_(Isolate* isolate, - Vector vector, - Handle result)); - // Entry point to serialize the object. INLINE(Result SerializeObject(Handle obj)) { - return Serialize_(obj, false, factory_->empty_string()); + return Serialize_(obj, false, factory()->empty_string()); } // Serialize an array element. @@ -103,9 +65,9 @@ class BasicJsonStringifier BASE_EMBEDDED { Result Serialize_(Handle object, bool comma, Handle key); void SerializeDeferredKey(bool deferred_comma, Handle deferred_key) { - if (deferred_comma) Append(','); + if (deferred_comma) builder_.AppendCharacter(','); SerializeString(Handle::cast(deferred_key)); - Append(':'); + builder_.AppendCharacter(':'); } Result SerializeSmi(Smi* object); @@ -125,11 +87,11 @@ class BasicJsonStringifier BASE_EMBEDDED { void SerializeString(Handle object); template - INLINE(static int SerializeStringUnchecked_(const SrcChar* src, - DestChar* dest, - int length)); + INLINE(static void SerializeStringUnchecked_( + Vector src, + IncrementalStringBuilder::NoExtend* dest)); - template + template INLINE(void SerializeString_(Handle string)); template @@ -141,26 +103,12 @@ class BasicJsonStringifier BASE_EMBEDDED { Result StackPush(Handle object); void StackPop(); - INLINE(Handle accumulator()) { - return Handle(String::cast(accumulator_store_->value()), isolate_); - } - - INLINE(void set_accumulator(Handle string)) { - return accumulator_store_->set_value(*string); - } + Factory* factory() { return isolate_->factory(); } Isolate* isolate_; - Factory* factory_; - // We use a value wrapper for the string accumulator to keep the - // (indirect) handle to it in the outermost handle scope. - Handle accumulator_store_; - Handle current_part_; + IncrementalStringBuilder builder_; Handle tojson_string_; Handle stack_; - int current_index_; - int part_length_; - bool is_one_byte_; - bool overflowed_; static const int kJsonEscapeTableEntrySize = 8; static const char* const JsonEscapeTable; @@ -237,31 +185,16 @@ const char* const BasicJsonStringifier::JsonEscapeTable = BasicJsonStringifier::BasicJsonStringifier(Isolate* isolate) - : isolate_(isolate), - current_index_(0), - is_one_byte_(true), - overflowed_(false) { - factory_ = isolate_->factory(); - accumulator_store_ = Handle::cast( - Object::ToObject(isolate, factory_->empty_string()).ToHandleChecked()); - part_length_ = kInitialPartLength; - current_part_ = factory_->NewRawOneByteString(part_length_).ToHandleChecked(); - tojson_string_ = factory_->toJSON_string(); - stack_ = factory_->NewJSArray(8); + : isolate_(isolate), builder_(isolate) { + tojson_string_ = factory()->toJSON_string(); + stack_ = factory()->NewJSArray(8); } MaybeHandle BasicJsonStringifier::Stringify(Handle object) { Result result = SerializeObject(object); - if (result == UNCHANGED) return isolate_->factory()->undefined_value(); - if (result == SUCCESS) { - ShrinkCurrentPart(); - Accumulate(); - if (overflowed_) { - THROW_NEW_ERROR(isolate_, NewInvalidStringLengthError(), Object); - } - return accumulator(); - } + if (result == UNCHANGED) return factory()->undefined_value(); + if (result == SUCCESS) return builder_.Finish(); DCHECK(result == EXCEPTION); return MaybeHandle(); } @@ -281,58 +214,29 @@ MaybeHandle BasicJsonStringifier::StringifyString( object = String::Flatten(object); DCHECK(object->IsFlat()); + Handle result; if (object->IsOneByteRepresentationUnderneath()) { - Handle result = isolate->factory()->NewRawOneByteString( - worst_case_length).ToHandleChecked(); - DisallowHeapAllocation no_gc; - return StringifyString_( - isolate, - object->GetFlatContent().ToOneByteVector(), - result); - } else { - Handle result = isolate->factory()->NewRawTwoByteString( - worst_case_length).ToHandleChecked(); - DisallowHeapAllocation no_gc; - return StringifyString_( - isolate, - object->GetFlatContent().ToUC16Vector(), - result); - } -} - - -template -Handle BasicJsonStringifier::StringifyString_(Isolate* isolate, - Vector vector, - Handle result) { - DisallowHeapAllocation no_gc; - int final_size = 0; - ResultType* dest = ResultType::cast(*result); - dest->Set(final_size++, '\"'); - final_size += SerializeStringUnchecked_(vector.start(), - dest->GetChars() + 1, - vector.length()); - dest->Set(final_size++, '\"'); - return SeqString::Truncate(Handle::cast(result), final_size); -} - - -template -void BasicJsonStringifier::Append_(Char c) { - if (is_one_byte) { - SeqOneByteString::cast(*current_part_)->SeqOneByteStringSet( - current_index_++, c); + result = isolate->factory() + ->NewRawOneByteString(worst_case_length) + .ToHandleChecked(); + IncrementalStringBuilder::NoExtendString no_extend( + result, worst_case_length); + no_extend.Append('\"'); + SerializeStringUnchecked_(object->GetFlatContent().ToOneByteVector(), + &no_extend); + no_extend.Append('\"'); } else { - SeqTwoByteString::cast(*current_part_)->SeqTwoByteStringSet( - current_index_++, c); + result = isolate->factory() + ->NewRawTwoByteString(worst_case_length) + .ToHandleChecked(); + IncrementalStringBuilder::NoExtendString no_extend(result, + worst_case_length); + no_extend.Append('\"'); + SerializeStringUnchecked_(object->GetFlatContent().ToUC16Vector(), + &no_extend); + no_extend.Append('\"'); } - if (current_index_ == part_length_) Extend(); -} - - -template -void BasicJsonStringifier::Append_(const Char* chars) { - for (; *chars != '\0'; chars++) Append_(*chars); + return result; } @@ -345,7 +249,7 @@ MaybeHandle BasicJsonStringifier::ApplyToJsonFunction( if (!fun->IsJSFunction()) return object; // Call toJSON function. - if (key->IsSmi()) key = factory_->NumberToString(key); + if (key->IsSmi()) key = factory()->NumberToString(key); Handle argv[] = { key }; HandleScope scope(isolate_); ASSIGN_RETURN_ON_EXCEPTION( @@ -372,7 +276,7 @@ BasicJsonStringifier::Result BasicJsonStringifier::StackPush( if (elements->get(i) == *object) { AllowHeapAllocation allow_to_return_error; Handle error; - MaybeHandle maybe_error = factory_->NewTypeError( + MaybeHandle maybe_error = factory()->NewTypeError( "circular_structure", HandleVector(NULL, 0)); if (maybe_error.ToHandle(&error)) isolate_->Throw(*error); return EXCEPTION; @@ -416,15 +320,15 @@ BasicJsonStringifier::Result BasicJsonStringifier::Serialize_( switch (Oddball::cast(*object)->kind()) { case Oddball::kFalse: if (deferred_string_key) SerializeDeferredKey(comma, key); - AppendOneByte("false"); + builder_.AppendCString("false"); return SUCCESS; case Oddball::kTrue: if (deferred_string_key) SerializeDeferredKey(comma, key); - AppendOneByte("true"); + builder_.AppendCString("true"); return SUCCESS; case Oddball::kNull: if (deferred_string_key) SerializeDeferredKey(comma, key); - AppendOneByte("null"); + builder_.AppendCString("null"); return SUCCESS; default: return UNCHANGED; @@ -472,23 +376,11 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeGeneric( EXCEPTION); if (result->IsUndefined()) return UNCHANGED; if (deferred_key) { - if (key->IsSmi()) key = factory_->NumberToString(key); + if (key->IsSmi()) key = factory()->NumberToString(key); SerializeDeferredKey(deferred_comma, key); } - Handle result_string = Handle::cast(result); - // Shrink current part, attach it to the accumulator, also attach the result - // string to the accumulator, and allocate a new part. - ShrinkCurrentPart(); // Shrink. - part_length_ = kInitialPartLength; // Allocate conservatively. - Extend(); // Attach current part and allocate new part. - // Attach result string to the accumulator. - Handle cons; - ASSIGN_RETURN_ON_EXCEPTION_VALUE( - isolate_, cons, - factory_->NewConsString(accumulator(), result_string), - EXCEPTION); - set_accumulator(cons); + builder_.AppendString(Handle::cast(result)); return SUCCESS; } @@ -511,7 +403,7 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeJSValue( DCHECK(class_name == isolate_->heap()->Boolean_string()); Object* value = JSValue::cast(*object)->value(); DCHECK(value->IsBoolean()); - AppendOneByte(value->IsTrue() ? "true" : "false"); + builder_.AppendCString(value->IsTrue() ? "true" : "false"); } return SUCCESS; } @@ -521,7 +413,7 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeSmi(Smi* object) { static const int kBufferSize = 100; char chars[kBufferSize]; Vector buffer(chars, kBufferSize); - AppendOneByte(IntToCString(object->value(), buffer)); + builder_.AppendCString(IntToCString(object->value(), buffer)); return SUCCESS; } @@ -529,13 +421,13 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeSmi(Smi* object) { BasicJsonStringifier::Result BasicJsonStringifier::SerializeDouble( double number) { if (std::isinf(number) || std::isnan(number)) { - AppendOneByte("null"); + builder_.AppendCString("null"); return SUCCESS; } static const int kBufferSize = 100; char chars[kBufferSize]; Vector buffer(chars, kBufferSize); - AppendOneByte(DoubleToCString(number, buffer)); + builder_.AppendCString(DoubleToCString(number, buffer)); return SUCCESS; } @@ -547,13 +439,13 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeJSArray( if (stack_push != SUCCESS) return stack_push; uint32_t length = 0; CHECK(object->length()->ToArrayIndex(&length)); - Append('['); + builder_.AppendCharacter('['); switch (object->GetElementsKind()) { case FAST_SMI_ELEMENTS: { Handle elements( FixedArray::cast(object->elements()), isolate_); for (uint32_t i = 0; i < length; i++) { - if (i > 0) Append(','); + if (i > 0) builder_.AppendCharacter(','); SerializeSmi(Smi::cast(elements->get(i))); } break; @@ -564,7 +456,7 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeJSArray( Handle elements( FixedDoubleArray::cast(object->elements()), isolate_); for (uint32_t i = 0; i < length; i++) { - if (i > 0) Append(','); + if (i > 0) builder_.AppendCharacter(','); SerializeDouble(elements->get_scalar(i)); } break; @@ -573,14 +465,14 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeJSArray( Handle elements( FixedArray::cast(object->elements()), isolate_); for (uint32_t i = 0; i < length; i++) { - if (i > 0) Append(','); + if (i > 0) builder_.AppendCharacter(','); Result result = SerializeElement(isolate_, Handle(elements->get(i), isolate_), i); if (result == SUCCESS) continue; if (result == UNCHANGED) { - AppendOneByte("null"); + builder_.AppendCString("null"); } else { return result; } @@ -596,9 +488,8 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeJSArray( break; } } - Append(']'); + builder_.AppendCharacter(']'); StackPop(); - current_part_ = handle_scope.CloseAndEscape(current_part_); return SUCCESS; } @@ -606,19 +497,19 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeJSArray( BasicJsonStringifier::Result BasicJsonStringifier::SerializeJSArraySlow( Handle object, uint32_t length) { for (uint32_t i = 0; i < length; i++) { - if (i > 0) Append(','); + if (i > 0) builder_.AppendCharacter(','); Handle element; ASSIGN_RETURN_ON_EXCEPTION_VALUE( isolate_, element, Object::GetElement(isolate_, object, i), EXCEPTION); if (element->IsUndefined()) { - AppendOneByte("null"); + builder_.AppendCString("null"); } else { Result result = SerializeElement(isolate_, element, i); if (result == SUCCESS) continue; if (result == UNCHANGED) { - AppendOneByte("null"); + builder_.AppendCString("null"); } else { return result; } @@ -635,7 +526,7 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeJSObject( if (stack_push != SUCCESS) return stack_push; DCHECK(!object->IsJSGlobalProxy() && !object->IsGlobalObject()); - Append('{'); + builder_.AppendCharacter('{'); bool comma = false; if (object->HasFastProperties() && @@ -687,7 +578,7 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeJSObject( maybe_property = Object::GetPropertyOrElement(object, key_handle); } else { DCHECK(key->IsNumber()); - key_handle = factory_->NumberToString(Handle(key, isolate_)); + key_handle = factory()->NumberToString(Handle(key, isolate_)); uint32_t index; if (key->IsSmi()) { maybe_property = Object::GetElement( @@ -707,130 +598,67 @@ BasicJsonStringifier::Result BasicJsonStringifier::SerializeJSObject( } } - Append('}'); + builder_.AppendCharacter('}'); StackPop(); - current_part_ = handle_scope.CloseAndEscape(current_part_); return SUCCESS; } -void BasicJsonStringifier::ShrinkCurrentPart() { - DCHECK(current_index_ < part_length_); - current_part_ = SeqString::Truncate(Handle::cast(current_part_), - current_index_); -} - - -void BasicJsonStringifier::Accumulate() { - if (accumulator()->length() + current_part_->length() > String::kMaxLength) { - // Screw it. Simply set the flag and carry on. Throw exception at the end. - set_accumulator(factory_->empty_string()); - overflowed_ = true; - } else { - set_accumulator(factory_->NewConsString(accumulator(), - current_part_).ToHandleChecked()); - } -} - - -void BasicJsonStringifier::Extend() { - Accumulate(); - if (part_length_ <= kMaxPartLength / kPartLengthGrowthFactor) { - part_length_ *= kPartLengthGrowthFactor; - } - if (is_one_byte_) { - current_part_ = - factory_->NewRawOneByteString(part_length_).ToHandleChecked(); - } else { - current_part_ = - factory_->NewRawTwoByteString(part_length_).ToHandleChecked(); - } - DCHECK(!current_part_.is_null()); - current_index_ = 0; -} - - -void BasicJsonStringifier::ChangeEncoding() { - ShrinkCurrentPart(); - Accumulate(); - current_part_ = - factory_->NewRawTwoByteString(part_length_).ToHandleChecked(); - DCHECK(!current_part_.is_null()); - current_index_ = 0; - is_one_byte_ = false; -} - - template -int BasicJsonStringifier::SerializeStringUnchecked_(const SrcChar* src, - DestChar* dest, - int length) { - DestChar* dest_start = dest; - +void BasicJsonStringifier::SerializeStringUnchecked_( + Vector src, + IncrementalStringBuilder::NoExtend* dest) { // Assert that uc16 character is not truncated down to 8 bit. // The version of this method must not be called. - DCHECK(sizeof(*dest) >= sizeof(*src)); + DCHECK(sizeof(DestChar) >= sizeof(SrcChar)); - for (int i = 0; i < length; i++) { + for (int i = 0; i < src.length(); i++) { SrcChar c = src[i]; if (DoNotEscape(c)) { - *(dest++) = static_cast(c); + dest->Append(c); } else { - const uint8_t* chars = reinterpret_cast( - &JsonEscapeTable[c * kJsonEscapeTableEntrySize]); - while (*chars != '\0') *(dest++) = *(chars++); + dest->AppendCString(&JsonEscapeTable[c * kJsonEscapeTableEntrySize]); } } - - return static_cast(dest - dest_start); } -template +template void BasicJsonStringifier::SerializeString_(Handle string) { int length = string->length(); - Append_('"'); + builder_.Append('"'); // We make a rough estimate to find out if the current string can be // serialized without allocating a new string part. The worst case length of // an escaped character is 6. Shifting the remainin string length right by 3 // is a more pessimistic estimate, but faster to calculate. - - if (((part_length_ - current_index_) >> 3) > length) { + int worst_case_length = length << 3; + if (builder_.CurrentPartCanFit(worst_case_length)) { DisallowHeapAllocation no_gc; - Vector vector = GetCharVector(string); - if (is_one_byte) { - current_index_ += SerializeStringUnchecked_( - vector.start(), - SeqOneByteString::cast(*current_part_)->GetChars() + current_index_, - length); - } else { - current_index_ += SerializeStringUnchecked_( - vector.start(), - SeqTwoByteString::cast(*current_part_)->GetChars() + current_index_, - length); - } + Vector vector = GetCharVector(string); + IncrementalStringBuilder::NoExtendBuilder no_extend( + &builder_, worst_case_length); + SerializeStringUnchecked_(vector, &no_extend); } else { String* string_location = NULL; - Vector vector(NULL, 0); + Vector vector(NULL, 0); for (int i = 0; i < length; i++) { // If GC moved the string, we need to refresh the vector. if (*string != string_location) { DisallowHeapAllocation no_gc; // This does not actually prevent the string from being relocated later. - vector = GetCharVector(string); + vector = GetCharVector(string); string_location = *string; } - Char c = vector[i]; + SrcChar c = vector[i]; if (DoNotEscape(c)) { - Append_(c); + builder_.Append(c); } else { - Append_(reinterpret_cast( - &JsonEscapeTable[c * kJsonEscapeTableEntrySize])); + builder_.AppendCString(&JsonEscapeTable[c * kJsonEscapeTableEntrySize]); } } } - Append_('"'); + builder_.Append('"'); } @@ -865,18 +693,18 @@ Vector BasicJsonStringifier::GetCharVector(Handle string) { void BasicJsonStringifier::SerializeString(Handle object) { object = String::Flatten(object); - if (is_one_byte_) { + if (builder_.CurrentEncoding() == String::ONE_BYTE_ENCODING) { if (object->IsOneByteRepresentationUnderneath()) { - SerializeString_(object); + SerializeString_(object); } else { - ChangeEncoding(); + builder_.ChangeEncoding(); SerializeString(object); } } else { if (object->IsOneByteRepresentationUnderneath()) { - SerializeString_(object); + SerializeString_(object); } else { - SerializeString_(object); + SerializeString_(object); } } } diff --git a/src/runtime/runtime-regexp.cc b/src/runtime/runtime-regexp.cc index b613f8a0e..982ef6669 100644 --- a/src/runtime/runtime-regexp.cc +++ b/src/runtime/runtime-regexp.cc @@ -8,7 +8,7 @@ #include "src/jsregexp-inl.h" #include "src/jsregexp.h" #include "src/runtime/runtime-utils.h" -#include "src/runtime/string-builder.h" +#include "src/string-builder.h" #include "src/string-search.h" namespace v8 { diff --git a/src/runtime/runtime-strings.cc b/src/runtime/runtime-strings.cc index 9c74f4b50..df2210c63 100644 --- a/src/runtime/runtime-strings.cc +++ b/src/runtime/runtime-strings.cc @@ -8,7 +8,7 @@ #include "src/jsregexp-inl.h" #include "src/jsregexp.h" #include "src/runtime/runtime-utils.h" -#include "src/runtime/string-builder.h" +#include "src/string-builder.h" #include "src/string-search.h" namespace v8 { diff --git a/src/string-builder.cc b/src/string-builder.cc new file mode 100644 index 000000000..38c3188a9 --- /dev/null +++ b/src/string-builder.cc @@ -0,0 +1,111 @@ +// Copyright 2014 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "src/string-builder.h" + +namespace v8 { +namespace internal { + +MaybeHandle ReplacementStringBuilder::ToString() { + Isolate* isolate = heap_->isolate(); + if (array_builder_.length() == 0) { + return isolate->factory()->empty_string(); + } + + Handle joined_string; + if (is_one_byte_) { + Handle seq; + ASSIGN_RETURN_ON_EXCEPTION( + isolate, seq, isolate->factory()->NewRawOneByteString(character_count_), + String); + + DisallowHeapAllocation no_gc; + uint8_t* char_buffer = seq->GetChars(); + StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(), + array_builder_.length()); + joined_string = Handle::cast(seq); + } else { + // Two-byte. + Handle seq; + ASSIGN_RETURN_ON_EXCEPTION( + isolate, seq, isolate->factory()->NewRawTwoByteString(character_count_), + String); + + DisallowHeapAllocation no_gc; + uc16* char_buffer = seq->GetChars(); + StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(), + array_builder_.length()); + joined_string = Handle::cast(seq); + } + return joined_string; +} + + +IncrementalStringBuilder::IncrementalStringBuilder(Isolate* isolate) + : isolate_(isolate), + encoding_(String::ONE_BYTE_ENCODING), + overflowed_(false), + part_length_(kInitialPartLength), + current_index_(0) { + // Create an accumulator handle starting with the empty string. + accumulator_ = Handle(isolate->heap()->empty_string(), isolate); + current_part_ = + factory()->NewRawOneByteString(part_length_).ToHandleChecked(); +} + + +void IncrementalStringBuilder::Accumulate() { + // Only accumulate fully written strings. Shrink first if necessary. + DCHECK_EQ(current_index_, current_part()->length()); + Handle new_accumulator; + if (accumulator()->length() + current_part()->length() > String::kMaxLength) { + // Set the flag and carry on. Delay throwing the exception till the end. + new_accumulator = factory()->empty_string(); + overflowed_ = true; + } else { + new_accumulator = factory() + ->NewConsString(accumulator(), current_part()) + .ToHandleChecked(); + } + set_accumulator(new_accumulator); +} + + +void IncrementalStringBuilder::Extend() { + Accumulate(); + if (part_length_ <= kMaxPartLength / kPartLengthGrowthFactor) { + part_length_ *= kPartLengthGrowthFactor; + } + Handle new_part; + if (encoding_ == String::ONE_BYTE_ENCODING) { + new_part = factory()->NewRawOneByteString(part_length_).ToHandleChecked(); + } else { + new_part = factory()->NewRawTwoByteString(part_length_).ToHandleChecked(); + } + // Reuse the same handle to avoid being invalidated when exiting handle scope. + set_current_part(new_part); + current_index_ = 0; +} + + +MaybeHandle IncrementalStringBuilder::Finish() { + ShrinkCurrentPart(); + Accumulate(); + if (overflowed_) { + THROW_NEW_ERROR(isolate_, NewInvalidStringLengthError(), String); + } + return accumulator(); +} + + +void IncrementalStringBuilder::AppendString(Handle string) { + ShrinkCurrentPart(); + part_length_ = kInitialPartLength; // Allocate conservatively. + Extend(); // Attach current part and allocate new part. + Handle concat = + factory()->NewConsString(accumulator(), string).ToHandleChecked(); + set_accumulator(concat); +} +} +} // namespace v8::internal diff --git a/src/runtime/string-builder.h b/src/string-builder.h similarity index 62% rename from src/runtime/string-builder.h rename to src/string-builder.h index 890b7f6be..f64f67987 100644 --- a/src/runtime/string-builder.h +++ b/src/string-builder.h @@ -2,8 +2,10 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. -#ifndef V8_RUNTIME_STRING_BUILDER_H_ -#define V8_RUNTIME_STRING_BUILDER_H_ +#ifndef V8_STRING_BUILDER_H_ +#define V8_STRING_BUILDER_H_ + +#include "src/v8.h" namespace v8 { namespace internal { @@ -233,39 +235,7 @@ class ReplacementStringBuilder { } - MaybeHandle ToString() { - Isolate* isolate = heap_->isolate(); - if (array_builder_.length() == 0) { - return isolate->factory()->empty_string(); - } - - Handle joined_string; - if (is_one_byte_) { - Handle seq; - ASSIGN_RETURN_ON_EXCEPTION( - isolate, seq, - isolate->factory()->NewRawOneByteString(character_count_), String); - - DisallowHeapAllocation no_gc; - uint8_t* char_buffer = seq->GetChars(); - StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(), - array_builder_.length()); - joined_string = Handle::cast(seq); - } else { - // Two-byte. - Handle seq; - ASSIGN_RETURN_ON_EXCEPTION( - isolate, seq, - isolate->factory()->NewRawTwoByteString(character_count_), String); - - DisallowHeapAllocation no_gc; - uc16* char_buffer = seq->GetChars(); - StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(), - array_builder_.length()); - joined_string = Handle::cast(seq); - } - return joined_string; - } + MaybeHandle ToString(); void IncrementCharacterCount(int by) { @@ -290,7 +260,171 @@ class ReplacementStringBuilder { int character_count_; bool is_one_byte_; }; + + +class IncrementalStringBuilder { + public: + explicit IncrementalStringBuilder(Isolate* isolate); + + INLINE(String::Encoding CurrentEncoding()) { return encoding_; } + + template + INLINE(void Append(SrcChar c)); + + INLINE(void AppendCharacter(uint8_t c)) { + if (encoding_ == String::ONE_BYTE_ENCODING) { + Append(c); + } else { + Append(c); + } + } + + INLINE(void AppendCString(const char* s)) { + const uint8_t* u = reinterpret_cast(s); + if (encoding_ == String::ONE_BYTE_ENCODING) { + while (*u != '\0') Append(*(u++)); + } else { + while (*u != '\0') Append(*(u++)); + } + } + + INLINE(bool CurrentPartCanFit(int length)) { + return part_length_ - current_index_ > length; + } + + void AppendString(Handle string); + + MaybeHandle Finish(); + + // Change encoding to two-byte. + void ChangeEncoding() { + DCHECK_EQ(String::ONE_BYTE_ENCODING, encoding_); + ShrinkCurrentPart(); + encoding_ = String::TWO_BYTE_ENCODING; + Extend(); + } + + template + class NoExtend { + public: + explicit NoExtend(Handle string, int offset) { + DCHECK(string->IsSeqOneByteString() || string->IsSeqTwoByteString()); + if (sizeof(DestChar) == 1) { + start_ = reinterpret_cast( + Handle::cast(string)->GetChars() + offset); + } else { + start_ = reinterpret_cast( + Handle::cast(string)->GetChars() + offset); + } + cursor_ = start_; + } + + INLINE(void Append(DestChar c)) { *(cursor_++) = c; } + INLINE(void AppendCString(const char* s)) { + const uint8_t* u = reinterpret_cast(s); + while (*u != '\0') Append(*(u++)); + } + + int written() { return cursor_ - start_; } + + private: + DestChar* start_; + DestChar* cursor_; + DisallowHeapAllocation no_gc_; + }; + + template + class NoExtendString : public NoExtend { + public: + NoExtendString(Handle string, int required_length) + : NoExtend(string, 0), string_(string) { + DCHECK(string->length() >= required_length); + } + + ~NoExtendString() { + Handle string = Handle::cast(string_); + int length = NoExtend::written(); + *string_.location() = *SeqString::Truncate(string, length); + } + + private: + Handle string_; + }; + + template + class NoExtendBuilder : public NoExtend { + public: + NoExtendBuilder(IncrementalStringBuilder* builder, int required_length) + : NoExtend(builder->current_part(), builder->current_index_), + builder_(builder) { + DCHECK(builder->CurrentPartCanFit(required_length)); + } + + ~NoExtendBuilder() { + builder_->current_index_ += NoExtend::written(); + } + + private: + IncrementalStringBuilder* builder_; + }; + + private: + Factory* factory() { return isolate_->factory(); } + + INLINE(Handle accumulator()) { return accumulator_; } + + INLINE(void set_accumulator(Handle string)) { + *accumulator_.location() = *string; + } + + INLINE(Handle current_part()) { return current_part_; } + + INLINE(void set_current_part(Handle string)) { + *current_part_.location() = *string; + } + + // Add the current part to the accumulator. + void Accumulate(); + + // Finish the current part and allocate a new part. + void Extend(); + + // Shrink current part to the right size. + void ShrinkCurrentPart() { + DCHECK(current_index_ < part_length_); + set_current_part(SeqString::Truncate( + Handle::cast(current_part()), current_index_)); + } + + static const int kInitialPartLength = 32; + static const int kMaxPartLength = 16 * 1024; + static const int kPartLengthGrowthFactor = 2; + + Isolate* isolate_; + String::Encoding encoding_; + bool overflowed_; + int part_length_; + int current_index_; + Handle accumulator_; + Handle current_part_; +}; + + +template +void IncrementalStringBuilder::Append(SrcChar c) { + DCHECK_EQ(encoding_ == String::ONE_BYTE_ENCODING, sizeof(DestChar) == 1); + if (sizeof(DestChar) == 1) { + DCHECK_EQ(String::ONE_BYTE_ENCODING, encoding_); + SeqOneByteString::cast(*current_part_) + ->SeqOneByteStringSet(current_index_++, c); + } else { + DCHECK_EQ(String::TWO_BYTE_ENCODING, encoding_); + SeqTwoByteString::cast(*current_part_) + ->SeqTwoByteStringSet(current_index_++, c); + } + if (current_index_ == part_length_) Extend(); +} } } // namespace v8::internal -#endif // V8_RUNTIME_STRING_BUILDER_H_ +#endif // V8_STRING_BUILDER_H_ diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index 268be23d1..23e901dd0 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -790,7 +790,6 @@ '../../src/runtime/runtime-utils.h', '../../src/runtime/runtime.cc', '../../src/runtime/runtime.h', - '../../src/runtime/string-builder.h', '../../src/safepoint-table.cc', '../../src/safepoint-table.h', '../../src/sampler.cc', @@ -810,6 +809,8 @@ '../../src/snapshot.h', '../../src/snapshot-source-sink.cc', '../../src/snapshot-source-sink.h', + '../../src/string-builder.h', + '../../src/string-builder.cc', '../../src/string-search.cc', '../../src/string-search.h', '../../src/string-stream.cc', -- 2.34.1