| OLD | NEW |
|---|
| (Empty) |
| 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 #ifndef V8_RUNTIME_STRING_BUILDER_H_ | |
| 6 #define V8_RUNTIME_STRING_BUILDER_H_ | |
| 7 | |
| 8 namespace v8 { | |
| 9 namespace internal { | |
| 10 | |
| 11 const int kStringBuilderConcatHelperLengthBits = 11; | |
| 12 const int kStringBuilderConcatHelperPositionBits = 19; | |
| 13 | |
| 14 typedef BitField<int, 0, kStringBuilderConcatHelperLengthBits> | |
| 15 StringBuilderSubstringLength; | |
| 16 typedef BitField<int, kStringBuilderConcatHelperLengthBits, | |
| 17 kStringBuilderConcatHelperPositionBits> | |
| 18 StringBuilderSubstringPosition; | |
| 19 | |
| 20 | |
| 21 template <typename sinkchar> | |
| 22 static inline void StringBuilderConcatHelper(String* special, sinkchar* sink, | |
| 23 FixedArray* fixed_array, | |
| 24 int array_length) { | |
| 25 DisallowHeapAllocation no_gc; | |
| 26 int position = 0; | |
| 27 for (int i = 0; i < array_length; i++) { | |
| 28 Object* element = fixed_array->get(i); | |
| 29 if (element->IsSmi()) { | |
| 30 // Smi encoding of position and length. | |
| 31 int encoded_slice = Smi::cast(element)->value(); | |
| 32 int pos; | |
| 33 int len; | |
| 34 if (encoded_slice > 0) { | |
| 35 // Position and length encoded in one smi. | |
| 36 pos = StringBuilderSubstringPosition::decode(encoded_slice); | |
| 37 len = StringBuilderSubstringLength::decode(encoded_slice); | |
| 38 } else { | |
| 39 // Position and length encoded in two smis. | |
| 40 Object* obj = fixed_array->get(++i); | |
| 41 DCHECK(obj->IsSmi()); | |
| 42 pos = Smi::cast(obj)->value(); | |
| 43 len = -encoded_slice; | |
| 44 } | |
| 45 String::WriteToFlat(special, sink + position, pos, pos + len); | |
| 46 position += len; | |
| 47 } else { | |
| 48 String* string = String::cast(element); | |
| 49 int element_length = string->length(); | |
| 50 String::WriteToFlat(string, sink + position, 0, element_length); | |
| 51 position += element_length; | |
| 52 } | |
| 53 } | |
| 54 } | |
| 55 | |
| 56 | |
| 57 // Returns the result length of the concatenation. | |
| 58 // On illegal argument, -1 is returned. | |
| 59 static inline int StringBuilderConcatLength(int special_length, | |
| 60 FixedArray* fixed_array, | |
| 61 int array_length, bool* one_byte) { | |
| 62 DisallowHeapAllocation no_gc; | |
| 63 int position = 0; | |
| 64 for (int i = 0; i < array_length; i++) { | |
| 65 int increment = 0; | |
| 66 Object* elt = fixed_array->get(i); | |
| 67 if (elt->IsSmi()) { | |
| 68 // Smi encoding of position and length. | |
| 69 int smi_value = Smi::cast(elt)->value(); | |
| 70 int pos; | |
| 71 int len; | |
| 72 if (smi_value > 0) { | |
| 73 // Position and length encoded in one smi. | |
| 74 pos = StringBuilderSubstringPosition::decode(smi_value); | |
| 75 len = StringBuilderSubstringLength::decode(smi_value); | |
| 76 } else { | |
| 77 // Position and length encoded in two smis. | |
| 78 len = -smi_value; | |
| 79 // Get the position and check that it is a positive smi. | |
| 80 i++; | |
| 81 if (i >= array_length) return -1; | |
| 82 Object* next_smi = fixed_array->get(i); | |
| 83 if (!next_smi->IsSmi()) return -1; | |
| 84 pos = Smi::cast(next_smi)->value(); | |
| 85 if (pos < 0) return -1; | |
| 86 } | |
| 87 DCHECK(pos >= 0); | |
| 88 DCHECK(len >= 0); | |
| 89 if (pos > special_length || len > special_length - pos) return -1; | |
| 90 increment = len; | |
| 91 } else if (elt->IsString()) { | |
| 92 String* element = String::cast(elt); | |
| 93 int element_length = element->length(); | |
| 94 increment = element_length; | |
| 95 if (*one_byte && !element->HasOnlyOneByteChars()) { | |
| 96 *one_byte = false; | |
| 97 } | |
| 98 } else { | |
| 99 return -1; | |
| 100 } | |
| 101 if (increment > String::kMaxLength - position) { | |
| 102 return kMaxInt; // Provoke throw on allocation. | |
| 103 } | |
| 104 position += increment; | |
| 105 } | |
| 106 return position; | |
| 107 } | |
| 108 | |
| 109 | |
| 110 class FixedArrayBuilder { | |
| 111 public: | |
| 112 explicit FixedArrayBuilder(Isolate* isolate, int initial_capacity) | |
| 113 : array_(isolate->factory()->NewFixedArrayWithHoles(initial_capacity)), | |
| 114 length_(0), | |
| 115 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(initial_capacity > 0); | |
| 119 } | |
| 120 | |
| 121 explicit FixedArrayBuilder(Handle<FixedArray> backing_store) | |
| 122 : array_(backing_store), length_(0), has_non_smi_elements_(false) { | |
| 123 // Require a non-zero initial size. Ensures that doubling the size to | |
| 124 // extend the array will work. | |
| 125 DCHECK(backing_store->length() > 0); | |
| 126 } | |
| 127 | |
| 128 bool HasCapacity(int elements) { | |
| 129 int length = array_->length(); | |
| 130 int required_length = length_ + elements; | |
| 131 return (length >= required_length); | |
| 132 } | |
| 133 | |
| 134 void EnsureCapacity(int elements) { | |
| 135 int length = array_->length(); | |
| 136 int required_length = length_ + elements; | |
| 137 if (length < required_length) { | |
| 138 int new_length = length; | |
| 139 do { | |
| 140 new_length *= 2; | |
| 141 } while (new_length < required_length); | |
| 142 Handle<FixedArray> extended_array = | |
| 143 array_->GetIsolate()->factory()->NewFixedArrayWithHoles(new_length); | |
| 144 array_->CopyTo(0, *extended_array, 0, length_); | |
| 145 array_ = extended_array; | |
| 146 } | |
| 147 } | |
| 148 | |
| 149 void Add(Object* value) { | |
| 150 DCHECK(!value->IsSmi()); | |
| 151 DCHECK(length_ < capacity()); | |
| 152 array_->set(length_, value); | |
| 153 length_++; | |
| 154 has_non_smi_elements_ = true; | |
| 155 } | |
| 156 | |
| 157 void Add(Smi* value) { | |
| 158 DCHECK(value->IsSmi()); | |
| 159 DCHECK(length_ < capacity()); | |
| 160 array_->set(length_, value); | |
| 161 length_++; | |
| 162 } | |
| 163 | |
| 164 Handle<FixedArray> array() { return array_; } | |
| 165 | |
| 166 int length() { return length_; } | |
| 167 | |
| 168 int capacity() { return array_->length(); } | |
| 169 | |
| 170 Handle<JSArray> ToJSArray(Handle<JSArray> target_array) { | |
| 171 JSArray::SetContent(target_array, array_); | |
| 172 target_array->set_length(Smi::FromInt(length_)); | |
| 173 return target_array; | |
| 174 } | |
| 175 | |
| 176 | |
| 177 private: | |
| 178 Handle<FixedArray> array_; | |
| 179 int length_; | |
| 180 bool has_non_smi_elements_; | |
| 181 }; | |
| 182 | |
| 183 | |
| 184 class ReplacementStringBuilder { | |
| 185 public: | |
| 186 ReplacementStringBuilder(Heap* heap, Handle<String> subject, | |
| 187 int estimated_part_count) | |
| 188 : heap_(heap), | |
| 189 array_builder_(heap->isolate(), estimated_part_count), | |
| 190 subject_(subject), | |
| 191 character_count_(0), | |
| 192 is_one_byte_(subject->IsOneByteRepresentation()) { | |
| 193 // Require a non-zero initial size. Ensures that doubling the size to | |
| 194 // extend the array will work. | |
| 195 DCHECK(estimated_part_count > 0); | |
| 196 } | |
| 197 | |
| 198 static inline void AddSubjectSlice(FixedArrayBuilder* builder, int from, | |
| 199 int to) { | |
| 200 DCHECK(from >= 0); | |
| 201 int length = to - from; | |
| 202 DCHECK(length > 0); | |
| 203 if (StringBuilderSubstringLength::is_valid(length) && | |
| 204 StringBuilderSubstringPosition::is_valid(from)) { | |
| 205 int encoded_slice = StringBuilderSubstringLength::encode(length) | | |
| 206 StringBuilderSubstringPosition::encode(from); | |
| 207 builder->Add(Smi::FromInt(encoded_slice)); | |
| 208 } else { | |
| 209 // Otherwise encode as two smis. | |
| 210 builder->Add(Smi::FromInt(-length)); | |
| 211 builder->Add(Smi::FromInt(from)); | |
| 212 } | |
| 213 } | |
| 214 | |
| 215 | |
| 216 void EnsureCapacity(int elements) { array_builder_.EnsureCapacity(elements); } | |
| 217 | |
| 218 | |
| 219 void AddSubjectSlice(int from, int to) { | |
| 220 AddSubjectSlice(&array_builder_, from, to); | |
| 221 IncrementCharacterCount(to - from); | |
| 222 } | |
| 223 | |
| 224 | |
| 225 void AddString(Handle<String> string) { | |
| 226 int length = string->length(); | |
| 227 DCHECK(length > 0); | |
| 228 AddElement(*string); | |
| 229 if (!string->IsOneByteRepresentation()) { | |
| 230 is_one_byte_ = false; | |
| 231 } | |
| 232 IncrementCharacterCount(length); | |
| 233 } | |
| 234 | |
| 235 | |
| 236 MaybeHandle<String> ToString() { | |
| 237 Isolate* isolate = heap_->isolate(); | |
| 238 if (array_builder_.length() == 0) { | |
| 239 return isolate->factory()->empty_string(); | |
| 240 } | |
| 241 | |
| 242 Handle<String> joined_string; | |
| 243 if (is_one_byte_) { | |
| 244 Handle<SeqOneByteString> seq; | |
| 245 ASSIGN_RETURN_ON_EXCEPTION( | |
| 246 isolate, seq, | |
| 247 isolate->factory()->NewRawOneByteString(character_count_), String); | |
| 248 | |
| 249 DisallowHeapAllocation no_gc; | |
| 250 uint8_t* char_buffer = seq->GetChars(); | |
| 251 StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(), | |
| 252 array_builder_.length()); | |
| 253 joined_string = Handle<String>::cast(seq); | |
| 254 } else { | |
| 255 // Two-byte. | |
| 256 Handle<SeqTwoByteString> seq; | |
| 257 ASSIGN_RETURN_ON_EXCEPTION( | |
| 258 isolate, seq, | |
| 259 isolate->factory()->NewRawTwoByteString(character_count_), String); | |
| 260 | |
| 261 DisallowHeapAllocation no_gc; | |
| 262 uc16* char_buffer = seq->GetChars(); | |
| 263 StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(), | |
| 264 array_builder_.length()); | |
| 265 joined_string = Handle<String>::cast(seq); | |
| 266 } | |
| 267 return joined_string; | |
| 268 } | |
| 269 | |
| 270 | |
| 271 void IncrementCharacterCount(int by) { | |
| 272 if (character_count_ > String::kMaxLength - by) { | |
| 273 STATIC_ASSERT(String::kMaxLength < kMaxInt); | |
| 274 character_count_ = kMaxInt; | |
| 275 } else { | |
| 276 character_count_ += by; | |
| 277 } | |
| 278 } | |
| 279 | |
| 280 private: | |
| 281 void AddElement(Object* element) { | |
| 282 DCHECK(element->IsSmi() || element->IsString()); | |
| 283 DCHECK(array_builder_.capacity() > array_builder_.length()); | |
| 284 array_builder_.Add(element); | |
| 285 } | |
| 286 | |
| 287 Heap* heap_; | |
| 288 FixedArrayBuilder array_builder_; | |
| 289 Handle<String> subject_; | |
| 290 int character_count_; | |
| 291 bool is_one_byte_; | |
| 292 }; | |
| 293 } | |
| 294 } // namespace v8::internal | |
| 295 | |
| 296 #endif // V8_RUNTIME_STRING_BUILDER_H_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 713223002:
Abstract string building in JSON-stringifier into IncrementalStringBuilder. (Closed)
Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge