1 // Copyright 2014 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
4 // met:
5 //
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided
11 // with the distribution.
12 // * Neither the name of Google Inc. nor the names of its
13 // contributors may be used to endorse or promote products derived
14 // from this software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28 #include "src/ast/ast-value-factory.h"
29
30 #include "src/base/hashmap-entry.h"
31 #include "src/base/logging.h"
32 #include "src/base/platform/wrappers.h"
33 #include "src/common/globals.h"
34 #include "src/heap/factory-inl.h"
35 #include "src/heap/local-factory-inl.h"
36 #include "src/objects/objects-inl.h"
37 #include "src/objects/objects.h"
38 #include "src/objects/string.h"
39 #include "src/strings/char-predicates-inl.h"
40 #include "src/strings/string-hasher.h"
41 #include "src/utils/utils-inl.h"
42
43 namespace v8 {
44 namespace internal {
45
46 namespace {
47
48 // For using StringToIndex.
49 class OneByteStringStream {
50 public:
OneByteStringStream(base::Vector<const byte> lb)51 explicit OneByteStringStream(base::Vector<const byte> lb)
52 : literal_bytes_(lb), pos_(0) {}
53
HasMore()54 bool HasMore() { return pos_ < literal_bytes_.length(); }
GetNext()55 uint16_t GetNext() { return literal_bytes_[pos_++]; }
56
57 private:
58 base::Vector<const byte> literal_bytes_;
59 int pos_;
60 };
61
62 } // namespace
63
64 template <typename IsolateT>
Internalize(IsolateT * isolate)65 void AstRawString::Internalize(IsolateT* isolate) {
66 DCHECK(!has_string_);
67 if (literal_bytes_.length() == 0) {
68 set_string(isolate->factory()->empty_string());
69 } else if (is_one_byte()) {
70 OneByteStringKey key(raw_hash_field_, literal_bytes_);
71 set_string(isolate->factory()->InternalizeStringWithKey(&key));
72 } else {
73 TwoByteStringKey key(raw_hash_field_,
74 base::Vector<const uint16_t>::cast(literal_bytes_));
75 set_string(isolate->factory()->InternalizeStringWithKey(&key));
76 }
77 }
78
79 template EXPORT_TEMPLATE_DEFINE(
80 V8_EXPORT_PRIVATE) void AstRawString::Internalize(Isolate* isolate);
81 template EXPORT_TEMPLATE_DEFINE(
82 V8_EXPORT_PRIVATE) void AstRawString::Internalize(LocalIsolate* isolate);
83
AsArrayIndex(uint32_t * index) const84 bool AstRawString::AsArrayIndex(uint32_t* index) const {
85 // The StringHasher will set up the hash. Bail out early if we know it
86 // can't be convertible to an array index.
87 if (!IsIntegerIndex()) return false;
88 if (length() <= Name::kMaxCachedArrayIndexLength) {
89 *index = Name::ArrayIndexValueBits::decode(raw_hash_field_);
90 return true;
91 }
92 // Might be an index, but too big to cache it. Do the slow conversion. This
93 // might fail if the string is outside uint32_t (but within "safe integer")
94 // range.
95 OneByteStringStream stream(literal_bytes_);
96 return StringToIndex(&stream, index);
97 }
98
IsIntegerIndex() const99 bool AstRawString::IsIntegerIndex() const {
100 return Name::IsIntegerIndex(raw_hash_field_);
101 }
102
IsOneByteEqualTo(const char * data) const103 bool AstRawString::IsOneByteEqualTo(const char* data) const {
104 if (!is_one_byte()) return false;
105
106 size_t length = static_cast<size_t>(literal_bytes_.length());
107 if (length != strlen(data)) return false;
108
109 return 0 == strncmp(reinterpret_cast<const char*>(literal_bytes_.begin()),
110 data, length);
111 }
112
FirstCharacter() const113 uint16_t AstRawString::FirstCharacter() const {
114 if (is_one_byte()) return literal_bytes_[0];
115 const uint16_t* c = reinterpret_cast<const uint16_t*>(literal_bytes_.begin());
116 return *c;
117 }
118
Equal(const AstRawString * lhs,const AstRawString * rhs)119 bool AstRawString::Equal(const AstRawString* lhs, const AstRawString* rhs) {
120 DCHECK_EQ(lhs->Hash(), rhs->Hash());
121
122 if (lhs->length() != rhs->length()) return false;
123 if (lhs->length() == 0) return true;
124 const unsigned char* l = lhs->raw_data();
125 const unsigned char* r = rhs->raw_data();
126 size_t length = rhs->length();
127 if (lhs->is_one_byte()) {
128 if (rhs->is_one_byte()) {
129 return CompareCharsEqualUnsigned(reinterpret_cast<const uint8_t*>(l),
130 reinterpret_cast<const uint8_t*>(r),
131 length);
132 } else {
133 return CompareCharsEqualUnsigned(reinterpret_cast<const uint8_t*>(l),
134 reinterpret_cast<const uint16_t*>(r),
135 length);
136 }
137 } else {
138 if (rhs->is_one_byte()) {
139 return CompareCharsEqualUnsigned(reinterpret_cast<const uint16_t*>(l),
140 reinterpret_cast<const uint8_t*>(r),
141 length);
142 } else {
143 return CompareCharsEqualUnsigned(reinterpret_cast<const uint16_t*>(l),
144 reinterpret_cast<const uint16_t*>(r),
145 length);
146 }
147 }
148 }
149
Compare(const AstRawString * lhs,const AstRawString * rhs)150 int AstRawString::Compare(const AstRawString* lhs, const AstRawString* rhs) {
151 // Fast path for equal pointers.
152 if (lhs == rhs) return 0;
153
154 const unsigned char* lhs_data = lhs->raw_data();
155 const unsigned char* rhs_data = rhs->raw_data();
156 size_t length = std::min(lhs->length(), rhs->length());
157
158 // Code point order by contents.
159 if (lhs->is_one_byte()) {
160 if (rhs->is_one_byte()) {
161 if (int result = CompareCharsUnsigned(
162 reinterpret_cast<const uint8_t*>(lhs_data),
163 reinterpret_cast<const uint8_t*>(rhs_data), length))
164 return result;
165 } else {
166 if (int result = CompareCharsUnsigned(
167 reinterpret_cast<const uint8_t*>(lhs_data),
168 reinterpret_cast<const uint16_t*>(rhs_data), length))
169 return result;
170 }
171 } else {
172 if (rhs->is_one_byte()) {
173 if (int result = CompareCharsUnsigned(
174 reinterpret_cast<const uint16_t*>(lhs_data),
175 reinterpret_cast<const uint8_t*>(rhs_data), length))
176 return result;
177 } else {
178 if (int result = CompareCharsUnsigned(
179 reinterpret_cast<const uint16_t*>(lhs_data),
180 reinterpret_cast<const uint16_t*>(rhs_data), length))
181 return result;
182 }
183 }
184
185 return lhs->byte_length() - rhs->byte_length();
186 }
187
188 template <typename IsolateT>
Allocate(IsolateT * isolate) const189 Handle<String> AstConsString::Allocate(IsolateT* isolate) const {
190 DCHECK(string_.is_null());
191
192 if (IsEmpty()) {
193 return isolate->factory()->empty_string();
194 }
195 // AstRawStrings are internalized before AstConsStrings are allocated, so
196 // AstRawString::string() will just work.
197 Handle<String> tmp = segment_.string->string();
198 for (AstConsString::Segment* current = segment_.next; current != nullptr;
199 current = current->next) {
200 tmp = isolate->factory()
201 ->NewConsString(current->string->string(), tmp,
202 AllocationType::kOld)
203 .ToHandleChecked();
204 }
205 return tmp;
206 }
207 template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
208 Handle<String> AstConsString::Allocate<Isolate>(Isolate* isolate) const;
209 template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
210 Handle<String> AstConsString::Allocate<LocalIsolate>(
211 LocalIsolate* isolate) const;
212
213 template <typename IsolateT>
AllocateFlat(IsolateT * isolate) const214 Handle<String> AstConsString::AllocateFlat(IsolateT* isolate) const {
215 if (IsEmpty()) {
216 return isolate->factory()->empty_string();
217 }
218 if (!segment_.next) {
219 return segment_.string->string();
220 }
221
222 int result_length = 0;
223 bool is_one_byte = true;
224 for (const AstConsString::Segment* current = &segment_; current != nullptr;
225 current = current->next) {
226 result_length += current->string->length();
227 is_one_byte = is_one_byte && current->string->is_one_byte();
228 }
229
230 if (is_one_byte) {
231 Handle<SeqOneByteString> result =
232 isolate->factory()
233 ->NewRawOneByteString(result_length, AllocationType::kOld)
234 .ToHandleChecked();
235 DisallowGarbageCollection no_gc;
236 uint8_t* dest =
237 result->GetChars(no_gc, SharedStringAccessGuardIfNeeded::NotNeeded()) +
238 result_length;
239 for (const AstConsString::Segment* current = &segment_; current != nullptr;
240 current = current->next) {
241 int length = current->string->length();
242 dest -= length;
243 CopyChars(dest, current->string->raw_data(), length);
244 }
245 DCHECK_EQ(dest, result->GetChars(
246 no_gc, SharedStringAccessGuardIfNeeded::NotNeeded()));
247 return result;
248 }
249
250 Handle<SeqTwoByteString> result =
251 isolate->factory()
252 ->NewRawTwoByteString(result_length, AllocationType::kOld)
253 .ToHandleChecked();
254 DisallowGarbageCollection no_gc;
255 uint16_t* dest =
256 result->GetChars(no_gc, SharedStringAccessGuardIfNeeded::NotNeeded()) +
257 result_length;
258 for (const AstConsString::Segment* current = &segment_; current != nullptr;
259 current = current->next) {
260 int length = current->string->length();
261 dest -= length;
262 if (current->string->is_one_byte()) {
263 CopyChars(dest, current->string->raw_data(), length);
264 } else {
265 CopyChars(dest,
266 reinterpret_cast<const uint16_t*>(current->string->raw_data()),
267 length);
268 }
269 }
270 DCHECK_EQ(dest, result->GetChars(
271 no_gc, SharedStringAccessGuardIfNeeded::NotNeeded()));
272 return result;
273 }
274 template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
275 Handle<String> AstConsString::AllocateFlat<Isolate>(Isolate* isolate) const;
276 template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
277 Handle<String> AstConsString::AllocateFlat<LocalIsolate>(
278 LocalIsolate* isolate) const;
279
ToRawStrings() const280 std::forward_list<const AstRawString*> AstConsString::ToRawStrings() const {
281 std::forward_list<const AstRawString*> result;
282 if (IsEmpty()) {
283 return result;
284 }
285
286 result.emplace_front(segment_.string);
287 for (AstConsString::Segment* current = segment_.next; current != nullptr;
288 current = current->next) {
289 result.emplace_front(current->string);
290 }
291 return result;
292 }
293
AstStringConstants(Isolate * isolate,uint64_t hash_seed)294 AstStringConstants::AstStringConstants(Isolate* isolate, uint64_t hash_seed)
295 : zone_(isolate->allocator(), ZONE_NAME),
296 string_table_(),
297 hash_seed_(hash_seed) {
298 DCHECK_EQ(ThreadId::Current(), isolate->thread_id());
299 #define F(name, str) \
300 { \
301 const char* data = str; \
302 base::Vector<const uint8_t> literal( \
303 reinterpret_cast<const uint8_t*>(data), \
304 static_cast<int>(strlen(data))); \
305 uint32_t raw_hash_field = StringHasher::HashSequentialString<uint8_t>( \
306 literal.begin(), literal.length(), hash_seed_); \
307 name##_string_ = zone_.New<AstRawString>(true, literal, raw_hash_field); \
308 /* The Handle returned by the factory is located on the roots */ \
309 /* array, not on the temporary HandleScope, so this is safe. */ \
310 name##_string_->set_string(isolate->factory()->name##_string()); \
311 string_table_.InsertNew(name##_string_, name##_string_->Hash()); \
312 }
313 AST_STRING_CONSTANTS(F)
314 #undef F
315 }
316
GetOneByteStringInternal(base::Vector<const uint8_t> literal)317 const AstRawString* AstValueFactory::GetOneByteStringInternal(
318 base::Vector<const uint8_t> literal) {
319 if (literal.length() == 1 && literal[0] < kMaxOneCharStringValue) {
320 int key = literal[0];
321 if (V8_UNLIKELY(one_character_strings_[key] == nullptr)) {
322 uint32_t raw_hash_field = StringHasher::HashSequentialString<uint8_t>(
323 literal.begin(), literal.length(), hash_seed_);
324 one_character_strings_[key] = GetString(raw_hash_field, true, literal);
325 }
326 return one_character_strings_[key];
327 }
328 uint32_t raw_hash_field = StringHasher::HashSequentialString<uint8_t>(
329 literal.begin(), literal.length(), hash_seed_);
330 return GetString(raw_hash_field, true, literal);
331 }
332
GetTwoByteStringInternal(base::Vector<const uint16_t> literal)333 const AstRawString* AstValueFactory::GetTwoByteStringInternal(
334 base::Vector<const uint16_t> literal) {
335 uint32_t raw_hash_field = StringHasher::HashSequentialString<uint16_t>(
336 literal.begin(), literal.length(), hash_seed_);
337 return GetString(raw_hash_field, false,
338 base::Vector<const byte>::cast(literal));
339 }
340
GetString(String literal,const SharedStringAccessGuardIfNeeded & access_guard)341 const AstRawString* AstValueFactory::GetString(
342 String literal, const SharedStringAccessGuardIfNeeded& access_guard) {
343 const AstRawString* result = nullptr;
344 DisallowGarbageCollection no_gc;
345 String::FlatContent content = literal.GetFlatContent(no_gc, access_guard);
346 if (content.IsOneByte()) {
347 result = GetOneByteStringInternal(content.ToOneByteVector());
348 } else {
349 DCHECK(content.IsTwoByte());
350 result = GetTwoByteStringInternal(content.ToUC16Vector());
351 }
352 return result;
353 }
354
NewConsString()355 AstConsString* AstValueFactory::NewConsString() {
356 return single_parse_zone()->New<AstConsString>();
357 }
358
NewConsString(const AstRawString * str)359 AstConsString* AstValueFactory::NewConsString(const AstRawString* str) {
360 return NewConsString()->AddString(single_parse_zone(), str);
361 }
362
NewConsString(const AstRawString * str1,const AstRawString * str2)363 AstConsString* AstValueFactory::NewConsString(const AstRawString* str1,
364 const AstRawString* str2) {
365 return NewConsString()
366 ->AddString(single_parse_zone(), str1)
367 ->AddString(single_parse_zone(), str2);
368 }
369
370 template <typename IsolateT>
Internalize(IsolateT * isolate)371 void AstValueFactory::Internalize(IsolateT* isolate) {
372 // Strings need to be internalized before values, because values refer to
373 // strings.
374 for (AstRawString* current = strings_; current != nullptr;) {
375 AstRawString* next = current->next();
376 current->Internalize(isolate);
377 current = next;
378 }
379
380 ResetStrings();
381 }
382 template EXPORT_TEMPLATE_DEFINE(
383 V8_EXPORT_PRIVATE) void AstValueFactory::Internalize(Isolate* isolate);
384 template EXPORT_TEMPLATE_DEFINE(
385 V8_EXPORT_PRIVATE) void AstValueFactory::Internalize(LocalIsolate* isolate);
386
GetString(uint32_t raw_hash_field,bool is_one_byte,base::Vector<const byte> literal_bytes)387 const AstRawString* AstValueFactory::GetString(
388 uint32_t raw_hash_field, bool is_one_byte,
389 base::Vector<const byte> literal_bytes) {
390 // literal_bytes here points to whatever the user passed, and this is OK
391 // because we use vector_compare (which checks the contents) to compare
392 // against the AstRawStrings which are in the string_table_. We should not
393 // return this AstRawString.
394 AstRawString key(is_one_byte, literal_bytes, raw_hash_field);
395 AstRawStringMap::Entry* entry = string_table_.LookupOrInsert(
396 &key, key.Hash(),
397 [&]() {
398 // Copy literal contents for later comparison.
399 int length = literal_bytes.length();
400 byte* new_literal_bytes = ast_raw_string_zone()->NewArray<byte>(length);
401 memcpy(new_literal_bytes, literal_bytes.begin(), length);
402 AstRawString* new_string = ast_raw_string_zone()->New<AstRawString>(
403 is_one_byte, base::Vector<const byte>(new_literal_bytes, length),
404 raw_hash_field);
405 CHECK_NOT_NULL(new_string);
406 AddString(new_string);
407 return new_string;
408 },
409 [&]() { return base::NoHashMapValue(); });
410 return entry->key;
411 }
412
413 } // namespace internal
414 } // namespace v8
415