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