src/strings/string-builder.cc

// 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/base/strings.h"
#include "src/execution/isolate-inl.h"
#include "src/objects/fixed-array-inl.h"
#include "src/objects/js-array-inl.h"
#include "src/strings/string-builder-inl.h"

namespace v8 {
namespace internal {

template <typename sinkchar>
void StringBuilderConcatHelper(String special, sinkchar* sink,
                               FixedArray fixed_array, int array_length) {
  DisallowGarbageCollection no_gc;
  int position = 0;
  for (int i = 0; i < array_length; i++) {
    Object element = fixed_array.get(i);
    if (element.IsSmi()) {
      // Smi encoding of position and length.
      int encoded_slice = Smi::ToInt(element);
      int pos;
      int len;
      if (encoded_slice > 0) {
        // Position and length encoded in one smi.
        pos = StringBuilderSubstringPosition::decode(encoded_slice);
        len = StringBuilderSubstringLength::decode(encoded_slice);
      } else {
        // Position and length encoded in two smis.
        Object obj = fixed_array.get(++i);
        DCHECK(obj.IsSmi());
        pos = Smi::ToInt(obj);
        len = -encoded_slice;
      }
      String::WriteToFlat(special, sink + position, pos, len);
      position += len;
    } else {
      String string = String::cast(element);
      int element_length = string.length();
      String::WriteToFlat(string, sink + position, 0, element_length);
      position += element_length;
    }
  }
}

template void StringBuilderConcatHelper<uint8_t>(String special, uint8_t* sink,
                                                 FixedArray fixed_array,
                                                 int array_length);

template void StringBuilderConcatHelper<base::uc16>(String special,
                                                    base::uc16* sink,
                                                    FixedArray fixed_array,
                                                    int array_length);

int StringBuilderConcatLength(int special_length, FixedArray fixed_array,
                              int array_length, bool* one_byte) {
  DisallowGarbageCollection no_gc;
  int position = 0;
  for (int i = 0; i < array_length; i++) {
    int increment = 0;
    Object elt = fixed_array.get(i);
    if (elt.IsSmi()) {
      // Smi encoding of position and length.
      int smi_value = Smi::ToInt(elt);
      int pos;
      int len;
      if (smi_value > 0) {
        // Position and length encoded in one smi.
        pos = StringBuilderSubstringPosition::decode(smi_value);
        len = StringBuilderSubstringLength::decode(smi_value);
      } else {
        // Position and length encoded in two smis.
        len = -smi_value;
        // Get the position and check that it is a positive smi.
        i++;
        if (i >= array_length) return -1;
        Object next_smi = fixed_array.get(i);
        if (!next_smi.IsSmi()) return -1;
        pos = Smi::ToInt(next_smi);
        if (pos < 0) return -1;
      }
      DCHECK_GE(pos, 0);
      DCHECK_GE(len, 0);
      if (pos > special_length || len > special_length - pos) return -1;
      increment = len;
    } else if (elt.IsString()) {
      String element = String::cast(elt);
      int element_length = element.length();
      increment = element_length;
      if (*one_byte && !element.IsOneByteRepresentation()) {
        *one_byte = false;
      }
    } else {
      return -1;
    }
    if (increment > String::kMaxLength - position) {
      return kMaxInt;  // Provoke throw on allocation.
    }
    position += increment;
  }
  return position;
}

FixedArrayBuilder::FixedArrayBuilder(Isolate* isolate, int initial_capacity)
    : array_(isolate->factory()->NewFixedArrayWithHoles(initial_capacity)),
      length_(0),
      has_non_smi_elements_(false) {
  // Require a non-zero initial size. Ensures that doubling the size to
  // extend the array will work.
  DCHECK_GT(initial_capacity, 0);
}

FixedArrayBuilder::FixedArrayBuilder(Handle<FixedArray> backing_store)
    : array_(backing_store), length_(0), has_non_smi_elements_(false) {
  // Require a non-zero initial size. Ensures that doubling the size to
  // extend the array will work.
  DCHECK_GT(backing_store->length(), 0);
}

bool FixedArrayBuilder::HasCapacity(int elements) {
  int length = array_->length();
  int required_length = length_ + elements;
  return (length >= required_length);
}

void FixedArrayBuilder::EnsureCapacity(Isolate* isolate, int elements) {
  int length = array_->length();
  int required_length = length_ + elements;
  if (length < required_length) {
    int new_length = length;
    do {
      new_length *= 2;
    } while (new_length < required_length);
    Handle<FixedArray> extended_array =
        isolate->factory()->NewFixedArrayWithHoles(new_length);
    array_->CopyTo(0, *extended_array, 0, length_);
    array_ = extended_array;
  }
}

void FixedArrayBuilder::Add(Object value) {
  DCHECK(!value.IsSmi());
  array_->set(length_, value);
  length_++;
  has_non_smi_elements_ = true;
}

void FixedArrayBuilder::Add(Smi value) {
  DCHECK(value.IsSmi());
  array_->set(length_, value);
  length_++;
}

int FixedArrayBuilder::capacity() { return array_->length(); }

Handle<JSArray> FixedArrayBuilder::ToJSArray(Handle<JSArray> target_array) {
  JSArray::SetContent(target_array, array_);
  target_array->set_length(Smi::FromInt(length_));
  return target_array;
}

ReplacementStringBuilder::ReplacementStringBuilder(Heap* heap,
                                                   Handle<String> subject,
                                                   int estimated_part_count)
    : heap_(heap),
      array_builder_(Isolate::FromHeap(heap), estimated_part_count),
      subject_(subject),
      character_count_(0),
      is_one_byte_(subject->IsOneByteRepresentation()) {
  // Require a non-zero initial size. Ensures that doubling the size to
  // extend the array will work.
  DCHECK_GT(estimated_part_count, 0);
}

void ReplacementStringBuilder::EnsureCapacity(int elements) {
  array_builder_.EnsureCapacity(Isolate::FromHeap(heap_), elements);
}

void ReplacementStringBuilder::AddString(Handle<String> string) {
  int length = string->length();
  DCHECK_GT(length, 0);
  AddElement(string);
  if (!string->IsOneByteRepresentation()) {
    is_one_byte_ = false;
  }
  IncrementCharacterCount(length);
}

MaybeHandle<String> ReplacementStringBuilder::ToString() {
  Isolate* isolate = Isolate::FromHeap(heap_);
  if (array_builder_.length() == 0) {
    return isolate->factory()->empty_string();
  }

  Handle<String> joined_string;
  if (is_one_byte_) {
    Handle<SeqOneByteString> seq;
    ASSIGN_RETURN_ON_EXCEPTION(
        isolate, seq, isolate->factory()->NewRawOneByteString(character_count_),
        String);

    DisallowGarbageCollection no_gc;
    uint8_t* char_buffer = seq->GetChars(no_gc);
    StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
                              array_builder_.length());
    joined_string = Handle<String>::cast(seq);
  } else {
    // Two-byte.
    Handle<SeqTwoByteString> seq;
    ASSIGN_RETURN_ON_EXCEPTION(
        isolate, seq, isolate->factory()->NewRawTwoByteString(character_count_),
        String);

    DisallowGarbageCollection no_gc;
    base::uc16* char_buffer = seq->GetChars(no_gc);
    StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
                              array_builder_.length());
    joined_string = Handle<String>::cast(seq);
  }
  return joined_string;
}

void ReplacementStringBuilder::AddElement(Handle<Object> element) {
  DCHECK(element->IsSmi() || element->IsString());
  EnsureCapacity(1);
  DisallowGarbageCollection no_gc;
  array_builder_.Add(*element);
}

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<String>::New(ReadOnlyRoots(isolate).empty_string(), isolate);
  current_part_ =
      factory()->NewRawOneByteString(part_length_).ToHandleChecked();
}

int IncrementalStringBuilder::Length() const {
  return accumulator_->length() + current_index_;
}

bool IncrementalStringBuilder::HasValidCurrentIndex() const {
  return current_index_ < part_length_;
}

void IncrementalStringBuilder::Accumulate(Handle<String> new_part) {
  Handle<String> new_accumulator;
  if (accumulator()->length() + new_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(), new_part).ToHandleChecked();
  }
  set_accumulator(new_accumulator);
}

void IncrementalStringBuilder::Extend() {
  DCHECK_EQ(current_index_, current_part()->length());
  Accumulate(current_part());
  if (part_length_ <= kMaxPartLength / kPartLengthGrowthFactor) {
    part_length_ *= kPartLengthGrowthFactor;
  }
  Handle<String> 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<String> IncrementalStringBuilder::Finish() {
  ShrinkCurrentPart();
  Accumulate(current_part());
  if (overflowed_) {
    THROW_NEW_ERROR(isolate_, NewInvalidStringLengthError(), String);
  }
  return accumulator();
}

// Short strings can be copied directly to {current_part_}.
// Requires the IncrementalStringBuilder to either have two byte encoding or
// the incoming string to have one byte representation "underneath" (The
// one byte check requires the string to be flat).
bool IncrementalStringBuilder::CanAppendByCopy(Handle<String> string) {
  constexpr int kMaxStringLengthForCopy = 16;
  const bool representation_ok =
      encoding_ == String::TWO_BYTE_ENCODING ||
      (string->IsFlat() && String::IsOneByteRepresentationUnderneath(*string));

  return representation_ok && string->length() <= kMaxStringLengthForCopy &&
         CurrentPartCanFit(string->length());
}

void IncrementalStringBuilder::AppendStringByCopy(Handle<String> string) {
  DCHECK(CanAppendByCopy(string));

  Handle<SeqOneByteString> part =
      Handle<SeqOneByteString>::cast(current_part());
  {
    DisallowGarbageCollection no_gc;
    String::WriteToFlat(*string, part->GetChars(no_gc) + current_index_, 0,
                        string->length());
  }
  current_index_ += string->length();
  DCHECK(current_index_ <= part_length_);
  if (current_index_ == part_length_) Extend();
}

void IncrementalStringBuilder::AppendString(Handle<String> string) {
  if (CanAppendByCopy(string)) {
    AppendStringByCopy(string);
    return;
  }

  ShrinkCurrentPart();
  part_length_ = kInitialPartLength;  // Allocate conservatively.
  Extend();  // Attach current part and allocate new part.
  Accumulate(string);
}
}  // namespace internal
}  // namespace v8