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/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