LCOV - code coverage report
Current view: top level - src - string-builder.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 102 117 87.2 %
Date: 2019-04-19 Functions: 20 23 87.0 %

          Line data    Source code
       1             : // Copyright 2014 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/string-builder-inl.h"
       6             : 
       7             : #include "src/isolate-inl.h"
       8             : #include "src/objects/fixed-array-inl.h"
       9             : #include "src/objects/js-array-inl.h"
      10             : 
      11             : namespace v8 {
      12             : namespace internal {
      13             : 
      14             : template <typename sinkchar>
      15        2378 : void StringBuilderConcatHelper(String special, sinkchar* sink,
      16             :                                FixedArray fixed_array, int array_length) {
      17             :   DisallowHeapAllocation no_gc;
      18             :   int position = 0;
      19      669646 :   for (int i = 0; i < array_length; i++) {
      20             :     Object element = fixed_array->get(i);
      21      333634 :     if (element->IsSmi()) {
      22             :       // Smi encoding of position and length.
      23             :       int encoded_slice = Smi::ToInt(element);
      24             :       int pos;
      25             :       int len;
      26       61437 :       if (encoded_slice > 0) {
      27             :         // Position and length encoded in one smi.
      28       61419 :         pos = StringBuilderSubstringPosition::decode(encoded_slice);
      29             :         len = StringBuilderSubstringLength::decode(encoded_slice);
      30             :       } else {
      31             :         // Position and length encoded in two smis.
      32          18 :         Object obj = fixed_array->get(++i);
      33             :         DCHECK(obj->IsSmi());
      34             :         pos = Smi::ToInt(obj);
      35          18 :         len = -encoded_slice;
      36             :       }
      37       61437 :       String::WriteToFlat(special, sink + position, pos, pos + len);
      38       61437 :       position += len;
      39             :     } else {
      40             :       String string = String::cast(element);
      41             :       int element_length = string->length();
      42      272197 :       String::WriteToFlat(string, sink + position, 0, element_length);
      43      272197 :       position += element_length;
      44             :     }
      45             :   }
      46        2378 : }
      47             : 
      48             : template void StringBuilderConcatHelper<uint8_t>(String special, uint8_t* sink,
      49             :                                                  FixedArray fixed_array,
      50             :                                                  int array_length);
      51             : 
      52             : template void StringBuilderConcatHelper<uc16>(String special, uc16* sink,
      53             :                                               FixedArray fixed_array,
      54             :                                               int array_length);
      55             : 
      56         659 : int StringBuilderConcatLength(int special_length, FixedArray fixed_array,
      57             :                               int array_length, bool* one_byte) {
      58             :   DisallowHeapAllocation no_gc;
      59             :   int position = 0;
      60      660259 :   for (int i = 0; i < array_length; i++) {
      61             :     int increment = 0;
      62             :     Object elt = fixed_array->get(i);
      63      329809 :     if (elt->IsSmi()) {
      64             :       // Smi encoding of position and length.
      65             :       int smi_value = Smi::ToInt(elt);
      66             :       int pos;
      67             :       int len;
      68       58737 :       if (smi_value > 0) {
      69             :         // Position and length encoded in one smi.
      70       58737 :         pos = StringBuilderSubstringPosition::decode(smi_value);
      71             :         len = StringBuilderSubstringLength::decode(smi_value);
      72             :       } else {
      73             :         // Position and length encoded in two smis.
      74           0 :         len = -smi_value;
      75             :         // Get the position and check that it is a positive smi.
      76           0 :         i++;
      77           0 :         if (i >= array_length) return -1;
      78             :         Object next_smi = fixed_array->get(i);
      79           0 :         if (!next_smi->IsSmi()) return -1;
      80             :         pos = Smi::ToInt(next_smi);
      81           0 :         if (pos < 0) return -1;
      82             :       }
      83             :       DCHECK_GE(pos, 0);
      84             :       DCHECK_GE(len, 0);
      85       58737 :       if (pos > special_length || len > special_length - pos) return -1;
      86             :       increment = len;
      87      271072 :     } else if (elt->IsString()) {
      88             :       String element = String::cast(elt);
      89             :       int element_length = element->length();
      90             :       increment = element_length;
      91      542122 :       if (*one_byte && !element->IsOneByteRepresentation()) {
      92           0 :         *one_byte = false;
      93             :       }
      94             :     } else {
      95             :       return -1;
      96             :     }
      97      329809 :     if (increment > String::kMaxLength - position) {
      98             :       return kMaxInt;  // Provoke throw on allocation.
      99             :     }
     100      329800 :     position += increment;
     101             :   }
     102             :   return position;
     103             : }
     104             : 
     105           0 : FixedArrayBuilder::FixedArrayBuilder(Isolate* isolate, int initial_capacity)
     106             :     : array_(isolate->factory()->NewFixedArrayWithHoles(initial_capacity)),
     107             :       length_(0),
     108        1764 :       has_non_smi_elements_(false) {
     109             :   // Require a non-zero initial size. Ensures that doubling the size to
     110             :   // extend the array will work.
     111             :   DCHECK_GT(initial_capacity, 0);
     112           0 : }
     113             : 
     114       93153 : FixedArrayBuilder::FixedArrayBuilder(Handle<FixedArray> backing_store)
     115       93153 :     : array_(backing_store), length_(0), has_non_smi_elements_(false) {
     116             :   // Require a non-zero initial size. Ensures that doubling the size to
     117             :   // extend the array will work.
     118             :   DCHECK_GT(backing_store->length(), 0);
     119       93153 : }
     120             : 
     121           0 : bool FixedArrayBuilder::HasCapacity(int elements) {
     122             :   int length = array_->length();
     123           0 :   int required_length = length_ + elements;
     124           0 :   return (length >= required_length);
     125             : }
     126             : 
     127      367621 : void FixedArrayBuilder::EnsureCapacity(Isolate* isolate, int elements) {
     128             :   int length = array_->length();
     129      367621 :   int required_length = length_ + elements;
     130      367621 :   if (length < required_length) {
     131             :     int new_length = length;
     132             :     do {
     133        1424 :       new_length *= 2;
     134        1424 :     } while (new_length < required_length);
     135             :     Handle<FixedArray> extended_array =
     136        1424 :         isolate->factory()->NewFixedArrayWithHoles(new_length);
     137        2848 :     array_->CopyTo(0, *extended_array, 0, length_);
     138        1424 :     array_ = extended_array;
     139             :   }
     140      367621 : }
     141             : 
     142      363508 : void FixedArrayBuilder::Add(Object value) {
     143             :   DCHECK(!value->IsSmi());
     144      729842 :   array_->set(length_, value);
     145      364921 :   length_++;
     146      364921 :   has_non_smi_elements_ = true;
     147      363508 : }
     148             : 
     149       61455 : void FixedArrayBuilder::Add(Smi value) {
     150             :   DCHECK(value->IsSmi());
     151       61455 :   array_->set(length_, value);
     152       61455 :   length_++;
     153       61455 : }
     154             : 
     155           0 : int FixedArrayBuilder::capacity() { return array_->length(); }
     156             : 
     157       93095 : Handle<JSArray> FixedArrayBuilder::ToJSArray(Handle<JSArray> target_array) {
     158       93095 :   JSArray::SetContent(target_array, array_);
     159       93095 :   target_array->set_length(Smi::FromInt(length_));
     160       93095 :   return target_array;
     161             : }
     162             : 
     163        1764 : ReplacementStringBuilder::ReplacementStringBuilder(Heap* heap,
     164             :                                                    Handle<String> subject,
     165             :                                                    int estimated_part_count)
     166             :     : heap_(heap),
     167             :       array_builder_(Isolate::FromHeap(heap), estimated_part_count),
     168             :       subject_(subject),
     169             :       character_count_(0),
     170        7056 :       is_one_byte_(subject->IsOneByteRepresentation()) {
     171             :   // Require a non-zero initial size. Ensures that doubling the size to
     172             :   // extend the array will work.
     173             :   DCHECK_GT(estimated_part_count, 0);
     174        1764 : }
     175             : 
     176        2700 : void ReplacementStringBuilder::EnsureCapacity(int elements) {
     177        8226 :   array_builder_.EnsureCapacity(Isolate::FromHeap(heap_), elements);
     178        2700 : }
     179             : 
     180        1413 : void ReplacementStringBuilder::AddString(Handle<String> string) {
     181             :   int length = string->length();
     182             :   DCHECK_GT(length, 0);
     183        1413 :   AddElement(string);
     184        1413 :   if (!string->IsOneByteRepresentation()) {
     185           0 :     is_one_byte_ = false;
     186             :   }
     187             :   IncrementCharacterCount(length);
     188        1413 : }
     189             : 
     190        1764 : MaybeHandle<String> ReplacementStringBuilder::ToString() {
     191        1764 :   Isolate* isolate = Isolate::FromHeap(heap_);
     192        1764 :   if (array_builder_.length() == 0) {
     193          36 :     return isolate->factory()->empty_string();
     194             :   }
     195             : 
     196             :   Handle<String> joined_string;
     197        1728 :   if (is_one_byte_) {
     198             :     Handle<SeqOneByteString> seq;
     199        3456 :     ASSIGN_RETURN_ON_EXCEPTION(
     200             :         isolate, seq, isolate->factory()->NewRawOneByteString(character_count_),
     201             :         String);
     202             : 
     203             :     DisallowHeapAllocation no_gc;
     204             :     uint8_t* char_buffer = seq->GetChars(no_gc);
     205             :     StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
     206        1728 :                               array_builder_.length());
     207             :     joined_string = Handle<String>::cast(seq);
     208             :   } else {
     209             :     // Two-byte.
     210             :     Handle<SeqTwoByteString> seq;
     211           0 :     ASSIGN_RETURN_ON_EXCEPTION(
     212             :         isolate, seq, isolate->factory()->NewRawTwoByteString(character_count_),
     213             :         String);
     214             : 
     215             :     DisallowHeapAllocation no_gc;
     216             :     uc16* char_buffer = seq->GetChars(no_gc);
     217             :     StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
     218           0 :                               array_builder_.length());
     219             :     joined_string = Handle<String>::cast(seq);
     220             :   }
     221        1728 :   return joined_string;
     222             : }
     223             : 
     224        1413 : void ReplacementStringBuilder::AddElement(Handle<Object> element) {
     225             :   DCHECK(element->IsSmi() || element->IsString());
     226             :   EnsureCapacity(1);
     227             :   DisallowHeapAllocation no_gc;
     228             :   array_builder_.Add(*element);
     229        1413 : }
     230             : 
     231     6168807 : IncrementalStringBuilder::IncrementalStringBuilder(Isolate* isolate)
     232             :     : isolate_(isolate),
     233             :       encoding_(String::ONE_BYTE_ENCODING),
     234             :       overflowed_(false),
     235             :       part_length_(kInitialPartLength),
     236     6168807 :       current_index_(0) {
     237             :   // Create an accumulator handle starting with the empty string.
     238             :   accumulator_ =
     239     6168807 :       Handle<String>::New(ReadOnlyRoots(isolate).empty_string(), isolate);
     240             :   current_part_ =
     241    12337608 :       factory()->NewRawOneByteString(part_length_).ToHandleChecked();
     242     6168801 : }
     243             : 
     244     1088877 : int IncrementalStringBuilder::Length() const {
     245     1088877 :   return accumulator_->length() + current_index_;
     246             : }
     247             : 
     248    22763360 : void IncrementalStringBuilder::Accumulate(Handle<String> new_part) {
     249             :   Handle<String> new_accumulator;
     250    22763360 :   if (accumulator()->length() + new_part->length() > String::kMaxLength) {
     251             :     // Set the flag and carry on. Delay throwing the exception till the end.
     252             :     new_accumulator = factory()->empty_string();
     253          45 :     overflowed_ = true;
     254             :   } else {
     255             :     new_accumulator =
     256    45526631 :         factory()->NewConsString(accumulator(), new_part).ToHandleChecked();
     257             :   }
     258             :   set_accumulator(new_accumulator);
     259    22763361 : }
     260             : 
     261             : 
     262     9050401 : void IncrementalStringBuilder::Extend() {
     263             :   DCHECK_EQ(current_index_, current_part()->length());
     264     9050401 :   Accumulate(current_part());
     265     9050406 :   if (part_length_ <= kMaxPartLength / kPartLengthGrowthFactor) {
     266     8896144 :     part_length_ *= kPartLengthGrowthFactor;
     267             :   }
     268             :   Handle<String> new_part;
     269     9050406 :   if (encoding_ == String::ONE_BYTE_ENCODING) {
     270    16662540 :     new_part = factory()->NewRawOneByteString(part_length_).ToHandleChecked();
     271             :   } else {
     272     1438272 :     new_part = factory()->NewRawTwoByteString(part_length_).ToHandleChecked();
     273             :   }
     274             :   // Reuse the same handle to avoid being invalidated when exiting handle scope.
     275             :   set_current_part(new_part);
     276     9050406 :   current_index_ = 0;
     277     9050406 : }
     278             : 
     279             : 
     280     6168160 : MaybeHandle<String> IncrementalStringBuilder::Finish() {
     281     6168160 :   ShrinkCurrentPart();
     282     6168160 :   Accumulate(current_part());
     283     6168160 :   if (overflowed_) {
     284          45 :     THROW_NEW_ERROR(isolate_, NewInvalidStringLengthError(), String);
     285             :   }
     286     6168115 :   return accumulator();
     287             : }
     288             : 
     289             : 
     290     7544815 : void IncrementalStringBuilder::AppendString(Handle<String> string) {
     291     7544815 :   ShrinkCurrentPart();
     292     7544817 :   part_length_ = kInitialPartLength;  // Allocate conservatively.
     293     7544817 :   Extend();  // Attach current part and allocate new part.
     294     7544820 :   Accumulate(string);
     295     7544820 : }
     296             : }  // namespace internal
     297      122036 : }  // namespace v8

Generated by: LCOV version 1.10