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/api.h" 31 #include "src/char-predicates-inl.h" 32 #include "src/objects-inl.h" 33 #include "src/objects.h" 34 #include "src/utils.h" 35 36 namespace v8 { 37 namespace internal { 38 39 namespace { 40 41 // For using StringToArrayIndex. 42 class OneByteStringStream { 43 public: 44 explicit OneByteStringStream(Vector<const byte> lb) : 45 literal_bytes_(lb), pos_(0) {} 46 47 bool HasMore() { return pos_ < literal_bytes_.length(); } 48 uint16_t GetNext() { return literal_bytes_[pos_++]; } 49 50 private: 51 Vector<const byte> literal_bytes_; 52 int pos_; 53 }; 54 55 } // namespace 56 57 class AstRawStringInternalizationKey : public HashTableKey { 58 public: 59 explicit AstRawStringInternalizationKey(const AstRawString* string) 60 : string_(string) {} 61 62 bool IsMatch(Object* other) override { 63 if (string_->is_one_byte()) 64 return String::cast(other)->IsOneByteEqualTo(string_->literal_bytes_); 65 return String::cast(other)->IsTwoByteEqualTo( 66 Vector<const uint16_t>::cast(string_->literal_bytes_)); 67 } 68 69 uint32_t Hash() override { return string_->hash() >> Name::kHashShift; } 70 71 uint32_t HashForObject(Object* key) override { 72 return String::cast(key)->Hash(); 73 } 74 75 Handle<Object> AsHandle(Isolate* isolate) override { 76 if (string_->is_one_byte()) 77 return isolate->factory()->NewOneByteInternalizedString( 78 string_->literal_bytes_, string_->hash()); 79 return isolate->factory()->NewTwoByteInternalizedString( 80 Vector<const uint16_t>::cast(string_->literal_bytes_), string_->hash()); 81 } 82 83 private: 84 const AstRawString* string_; 85 }; 86 87 int AstString::length() const { 88 if (IsRawStringBits::decode(bit_field_)) { 89 return reinterpret_cast<const AstRawString*>(this)->length(); 90 } 91 return reinterpret_cast<const AstConsString*>(this)->length(); 92 } 93 94 void AstString::Internalize(Isolate* isolate) { 95 if (IsRawStringBits::decode(bit_field_)) { 96 return reinterpret_cast<AstRawString*>(this)->Internalize(isolate); 97 } 98 return reinterpret_cast<AstConsString*>(this)->Internalize(isolate); 99 } 100 101 void AstRawString::Internalize(Isolate* isolate) { 102 if (literal_bytes_.length() == 0) { 103 set_string(isolate->factory()->empty_string()); 104 } else { 105 AstRawStringInternalizationKey key(this); 106 set_string(StringTable::LookupKey(isolate, &key)); 107 } 108 } 109 110 bool AstRawString::AsArrayIndex(uint32_t* index) const { 111 // The StringHasher will set up the hash in such a way that we can use it to 112 // figure out whether the string is convertible to an array index. 113 if ((hash_ & Name::kIsNotArrayIndexMask) != 0) return false; 114 if (length() <= Name::kMaxCachedArrayIndexLength) { 115 *index = Name::ArrayIndexValueBits::decode(hash_); 116 } else { 117 OneByteStringStream stream(literal_bytes_); 118 CHECK(StringToArrayIndex(&stream, index)); 119 } 120 return true; 121 } 122 123 bool AstRawString::IsOneByteEqualTo(const char* data) const { 124 int length = static_cast<int>(strlen(data)); 125 if (is_one_byte() && literal_bytes_.length() == length) { 126 const char* token = reinterpret_cast<const char*>(literal_bytes_.start()); 127 return !strncmp(token, data, length); 128 } 129 return false; 130 } 131 132 bool AstRawString::Compare(void* a, void* b) { 133 const AstRawString* lhs = static_cast<AstRawString*>(a); 134 const AstRawString* rhs = static_cast<AstRawString*>(b); 135 DCHECK_EQ(lhs->hash(), rhs->hash()); 136 if (lhs->length() != rhs->length()) return false; 137 const unsigned char* l = lhs->raw_data(); 138 const unsigned char* r = rhs->raw_data(); 139 size_t length = rhs->length(); 140 if (lhs->is_one_byte()) { 141 if (rhs->is_one_byte()) { 142 return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(l), 143 reinterpret_cast<const uint8_t*>(r), 144 length) == 0; 145 } else { 146 return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(l), 147 reinterpret_cast<const uint16_t*>(r), 148 length) == 0; 149 } 150 } else { 151 if (rhs->is_one_byte()) { 152 return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(l), 153 reinterpret_cast<const uint8_t*>(r), 154 length) == 0; 155 } else { 156 return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(l), 157 reinterpret_cast<const uint16_t*>(r), 158 length) == 0; 159 } 160 } 161 } 162 163 void AstConsString::Internalize(Isolate* isolate) { 164 // AstRawStrings are internalized before AstConsStrings so left and right are 165 // already internalized. 166 set_string(isolate->factory() 167 ->NewConsString(left_->string(), right_->string()) 168 .ToHandleChecked()); 169 } 170 171 bool AstValue::IsPropertyName() const { 172 if (type_ == STRING) { 173 uint32_t index; 174 return !string_->AsArrayIndex(&index); 175 } 176 return false; 177 } 178 179 180 bool AstValue::BooleanValue() const { 181 switch (type_) { 182 case STRING: 183 DCHECK(string_ != NULL); 184 return !string_->IsEmpty(); 185 case SYMBOL: 186 UNREACHABLE(); 187 break; 188 case NUMBER_WITH_DOT: 189 case NUMBER: 190 return DoubleToBoolean(number_); 191 case SMI_WITH_DOT: 192 case SMI: 193 return smi_ != 0; 194 case BOOLEAN: 195 return bool_; 196 case NULL_TYPE: 197 return false; 198 case THE_HOLE: 199 UNREACHABLE(); 200 break; 201 case UNDEFINED: 202 return false; 203 } 204 UNREACHABLE(); 205 return false; 206 } 207 208 209 void AstValue::Internalize(Isolate* isolate) { 210 switch (type_) { 211 case STRING: 212 DCHECK_NOT_NULL(string_); 213 // Strings are already internalized. 214 DCHECK(!string_->string().is_null()); 215 break; 216 case SYMBOL: 217 switch (symbol_) { 218 case AstSymbol::kHomeObjectSymbol: 219 set_value(isolate->factory()->home_object_symbol()); 220 break; 221 } 222 break; 223 case NUMBER_WITH_DOT: 224 case NUMBER: 225 set_value(isolate->factory()->NewNumber(number_, TENURED)); 226 break; 227 case SMI_WITH_DOT: 228 case SMI: 229 set_value(handle(Smi::FromInt(smi_), isolate)); 230 break; 231 case BOOLEAN: 232 if (bool_) { 233 set_value(isolate->factory()->true_value()); 234 } else { 235 set_value(isolate->factory()->false_value()); 236 } 237 break; 238 case NULL_TYPE: 239 set_value(isolate->factory()->null_value()); 240 break; 241 case THE_HOLE: 242 set_value(isolate->factory()->the_hole_value()); 243 break; 244 case UNDEFINED: 245 set_value(isolate->factory()->undefined_value()); 246 break; 247 } 248 } 249 250 AstRawString* AstValueFactory::GetOneByteStringInternal( 251 Vector<const uint8_t> literal) { 252 if (literal.length() == 1 && IsInRange(literal[0], 'a', 'z')) { 253 int key = literal[0] - 'a'; 254 if (one_character_strings_[key] == nullptr) { 255 uint32_t hash = StringHasher::HashSequentialString<uint8_t>( 256 literal.start(), literal.length(), hash_seed_); 257 one_character_strings_[key] = GetString(hash, true, literal); 258 } 259 return one_character_strings_[key]; 260 } 261 uint32_t hash = StringHasher::HashSequentialString<uint8_t>( 262 literal.start(), literal.length(), hash_seed_); 263 return GetString(hash, true, literal); 264 } 265 266 267 AstRawString* AstValueFactory::GetTwoByteStringInternal( 268 Vector<const uint16_t> literal) { 269 uint32_t hash = StringHasher::HashSequentialString<uint16_t>( 270 literal.start(), literal.length(), hash_seed_); 271 return GetString(hash, false, Vector<const byte>::cast(literal)); 272 } 273 274 275 const AstRawString* AstValueFactory::GetString(Handle<String> literal) { 276 AstRawString* result = NULL; 277 DisallowHeapAllocation no_gc; 278 String::FlatContent content = literal->GetFlatContent(); 279 if (content.IsOneByte()) { 280 result = GetOneByteStringInternal(content.ToOneByteVector()); 281 } else { 282 DCHECK(content.IsTwoByte()); 283 result = GetTwoByteStringInternal(content.ToUC16Vector()); 284 } 285 return result; 286 } 287 288 289 const AstConsString* AstValueFactory::NewConsString( 290 const AstString* left, const AstString* right) { 291 // This Vector will be valid as long as the Collector is alive (meaning that 292 // the AstRawString will not be moved). 293 AstConsString* new_string = new (zone_) AstConsString(left, right); 294 CHECK(new_string != nullptr); 295 AddString(new_string); 296 return new_string; 297 } 298 299 void AstValueFactory::Internalize(Isolate* isolate) { 300 // Strings need to be internalized before values, because values refer to 301 // strings. 302 for (AstString* current = strings_; current != nullptr;) { 303 AstString* next = current->next(); 304 current->Internalize(isolate); 305 current = next; 306 } 307 308 for (AstValue* current = values_; current != nullptr;) { 309 AstValue* next = current->next(); 310 current->Internalize(isolate); 311 current = next; 312 } 313 ResetStrings(); 314 values_ = nullptr; 315 } 316 317 318 const AstValue* AstValueFactory::NewString(const AstRawString* string) { 319 AstValue* value = new (zone_) AstValue(string); 320 CHECK_NOT_NULL(string); 321 return AddValue(value); 322 } 323 324 const AstValue* AstValueFactory::NewSymbol(AstSymbol symbol) { 325 AstValue* value = new (zone_) AstValue(symbol); 326 return AddValue(value); 327 } 328 329 330 const AstValue* AstValueFactory::NewNumber(double number, bool with_dot) { 331 AstValue* value = new (zone_) AstValue(number, with_dot); 332 return AddValue(value); 333 } 334 335 const AstValue* AstValueFactory::NewSmi(uint32_t number) { 336 bool cacheable_smi = number <= kMaxCachedSmi; 337 if (cacheable_smi && smis_[number] != nullptr) return smis_[number]; 338 339 AstValue* value = new (zone_) AstValue(AstValue::SMI, number); 340 if (cacheable_smi) smis_[number] = value; 341 return AddValue(value); 342 } 343 344 #define GENERATE_VALUE_GETTER(value, initializer) \ 345 if (!value) { \ 346 value = AddValue(new (zone_) AstValue(initializer)); \ 347 } \ 348 return value; 349 350 const AstValue* AstValueFactory::NewBoolean(bool b) { 351 if (b) { 352 GENERATE_VALUE_GETTER(true_value_, true); 353 } else { 354 GENERATE_VALUE_GETTER(false_value_, false); 355 } 356 } 357 358 359 const AstValue* AstValueFactory::NewNull() { 360 GENERATE_VALUE_GETTER(null_value_, AstValue::NULL_TYPE); 361 } 362 363 364 const AstValue* AstValueFactory::NewUndefined() { 365 GENERATE_VALUE_GETTER(undefined_value_, AstValue::UNDEFINED); 366 } 367 368 369 const AstValue* AstValueFactory::NewTheHole() { 370 GENERATE_VALUE_GETTER(the_hole_value_, AstValue::THE_HOLE); 371 } 372 373 374 #undef GENERATE_VALUE_GETTER 375 376 AstRawString* AstValueFactory::GetString(uint32_t hash, bool is_one_byte, 377 Vector<const byte> literal_bytes) { 378 // literal_bytes here points to whatever the user passed, and this is OK 379 // because we use vector_compare (which checks the contents) to compare 380 // against the AstRawStrings which are in the string_table_. We should not 381 // return this AstRawString. 382 AstRawString key(is_one_byte, literal_bytes, hash); 383 base::HashMap::Entry* entry = string_table_.LookupOrInsert(&key, hash); 384 if (entry->value == nullptr) { 385 // Copy literal contents for later comparison. 386 int length = literal_bytes.length(); 387 byte* new_literal_bytes = zone_->NewArray<byte>(length); 388 memcpy(new_literal_bytes, literal_bytes.start(), length); 389 AstRawString* new_string = new (zone_) AstRawString( 390 is_one_byte, Vector<const byte>(new_literal_bytes, length), hash); 391 CHECK_NOT_NULL(new_string); 392 AddString(new_string); 393 entry->key = new_string; 394 entry->value = reinterpret_cast<void*>(1); 395 } 396 return reinterpret_cast<AstRawString*>(entry->key); 397 } 398 399 } // namespace internal 400 } // namespace v8 401