ast-value-factory.cc 14.3 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
// Copyright 2014 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

28
#include "src/ast/ast-value-factory.h"
29

30
#include "src/base/logging.h"
31 32
#include "src/common/globals.h"
#include "src/heap/factory-inl.h"
33
#include "src/heap/local-factory-inl.h"
34 35
#include "src/objects/objects-inl.h"
#include "src/objects/objects.h"
36 37
#include "src/strings/char-predicates-inl.h"
#include "src/strings/string-hasher.h"
38
#include "src/utils/utils-inl.h"
39 40 41 42 43 44

namespace v8 {
namespace internal {

namespace {

45
// For using StringToIndex.
46 47
class OneByteStringStream {
 public:
48 49
  explicit OneByteStringStream(Vector<const byte> lb)
      : literal_bytes_(lb), pos_(0) {}
50 51 52 53 54 55 56 57 58

  bool HasMore() { return pos_ < literal_bytes_.length(); }
  uint16_t GetNext() { return literal_bytes_[pos_++]; }

 private:
  Vector<const byte> literal_bytes_;
  int pos_;
};

59
}  // namespace
60

61 62
template <typename LocalIsolate>
void AstRawString::Internalize(LocalIsolate* isolate) {
63
  DCHECK(!has_string_);
64
  if (literal_bytes_.length() == 0) {
65
    set_string(isolate->factory()->empty_string());
66 67
  } else if (is_one_byte()) {
    OneByteStringKey key(hash_field_, literal_bytes_);
68
    set_string(isolate->factory()->InternalizeStringWithKey(&key));
69
  } else {
70 71
    TwoByteStringKey key(hash_field_,
                         Vector<const uint16_t>::cast(literal_bytes_));
72
    set_string(isolate->factory()->InternalizeStringWithKey(&key));
73 74 75
  }
}

76 77 78 79
template EXPORT_TEMPLATE_DEFINE(
    V8_EXPORT_PRIVATE) void AstRawString::Internalize(Isolate* isolate);
template EXPORT_TEMPLATE_DEFINE(
    V8_EXPORT_PRIVATE) void AstRawString::Internalize(LocalIsolate* isolate);
80

81
bool AstRawString::AsArrayIndex(uint32_t* index) const {
82 83 84
  // The StringHasher will set up the hash. Bail out early if we know it
  // can't be convertible to an array index.
  if ((hash_field_ & Name::kIsNotIntegerIndexMask) != 0) return false;
85
  if (length() <= Name::kMaxCachedArrayIndexLength) {
86
    *index = Name::ArrayIndexValueBits::decode(hash_field_);
87
    return true;
88
  }
89 90 91 92 93
  // Might be an index, but too big to cache it. Do the slow conversion. This
  // might fail if the string is outside uint32_t (but within "safe integer")
  // range.
  OneByteStringStream stream(literal_bytes_);
  return StringToIndex(&stream, index);
94 95
}

96 97 98 99
bool AstRawString::IsIntegerIndex() const {
  return (hash_field_ & Name::kIsNotIntegerIndexMask) == 0;
}

100
bool AstRawString::IsOneByteEqualTo(const char* data) const {
101 102 103 104 105
  if (!is_one_byte()) return false;

  size_t length = static_cast<size_t>(literal_bytes_.length());
  if (length != strlen(data)) return false;

106
  return 0 == strncmp(reinterpret_cast<const char*>(literal_bytes_.begin()),
107 108 109 110 111
                      data, length);
}

uint16_t AstRawString::FirstCharacter() const {
  if (is_one_byte()) return literal_bytes_[0];
112
  const uint16_t* c = reinterpret_cast<const uint16_t*>(literal_bytes_.begin());
113
  return *c;
114 115
}

116 117 118
bool AstRawString::Compare(void* a, void* b) {
  const AstRawString* lhs = static_cast<AstRawString*>(a);
  const AstRawString* rhs = static_cast<AstRawString*>(b);
119
  DCHECK_EQ(lhs->Hash(), rhs->Hash());
120

121
  if (lhs->length() != rhs->length()) return false;
122
  if (lhs->length() == 0) return true;
123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
  const unsigned char* l = lhs->raw_data();
  const unsigned char* r = rhs->raw_data();
  size_t length = rhs->length();
  if (lhs->is_one_byte()) {
    if (rhs->is_one_byte()) {
      return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(l),
                                  reinterpret_cast<const uint8_t*>(r),
                                  length) == 0;
    } else {
      return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(l),
                                  reinterpret_cast<const uint16_t*>(r),
                                  length) == 0;
    }
  } else {
    if (rhs->is_one_byte()) {
      return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(l),
                                  reinterpret_cast<const uint8_t*>(r),
                                  length) == 0;
    } else {
      return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(l),
                                  reinterpret_cast<const uint16_t*>(r),
                                  length) == 0;
    }
  }
}
148

149 150
template <typename LocalIsolate>
Handle<String> AstConsString::Allocate(LocalIsolate* isolate) const {
151 152
  DCHECK(string_.is_null());

153
  if (IsEmpty()) {
154
    return isolate->factory()->empty_string();
155
  }
156
  // AstRawStrings are internalized before AstConsStrings are allocated, so
157
  // AstRawString::string() will just work.
158
  Handle<String> tmp = segment_.string->string();
159 160
  for (AstConsString::Segment* current = segment_.next; current != nullptr;
       current = current->next) {
161
    tmp = isolate->factory()
162
              ->NewConsString(current->string->string(), tmp,
163 164 165 166 167 168
                              AllocationType::kOld)
              .ToHandleChecked();
  }
  return tmp;
}
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
169
    Handle<String> AstConsString::Allocate<Isolate>(Isolate* isolate) const;
170
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
171 172
    Handle<String> AstConsString::Allocate<LocalIsolate>(
        LocalIsolate* isolate) const;
173

174 175
template <typename LocalIsolate>
Handle<String> AstConsString::AllocateFlat(LocalIsolate* isolate) const {
176
  if (IsEmpty()) {
177
    return isolate->factory()->empty_string();
178 179
  }
  if (!segment_.next) {
180
    return segment_.string->string();
181 182 183 184 185 186 187 188 189 190 191
  }

  int result_length = 0;
  bool is_one_byte = true;
  for (const AstConsString::Segment* current = &segment_; current != nullptr;
       current = current->next) {
    result_length += current->string->length();
    is_one_byte = is_one_byte && current->string->is_one_byte();
  }

  if (is_one_byte) {
192
    Handle<SeqOneByteString> result =
193 194
        isolate->factory()
            ->NewRawOneByteString(result_length, AllocationType::kOld)
195
            .ToHandleChecked();
196 197 198 199 200 201 202 203 204 205 206 207
    DisallowHeapAllocation no_gc;
    uint8_t* dest = result->GetChars(no_gc) + result_length;
    for (const AstConsString::Segment* current = &segment_; current != nullptr;
         current = current->next) {
      int length = current->string->length();
      dest -= length;
      CopyChars(dest, current->string->raw_data(), length);
    }
    DCHECK_EQ(dest, result->GetChars(no_gc));
    return result;
  }

208
  Handle<SeqTwoByteString> result =
209 210
      isolate->factory()
          ->NewRawTwoByteString(result_length, AllocationType::kOld)
211 212 213 214 215 216 217 218 219 220 221 222 223 224
          .ToHandleChecked();
  DisallowHeapAllocation no_gc;
  uint16_t* dest = result->GetChars(no_gc) + result_length;
  for (const AstConsString::Segment* current = &segment_; current != nullptr;
       current = current->next) {
    int length = current->string->length();
    dest -= length;
    if (current->string->is_one_byte()) {
      CopyChars(dest, current->string->raw_data(), length);
    } else {
      CopyChars(dest,
                reinterpret_cast<const uint16_t*>(current->string->raw_data()),
                length);
    }
225
  }
226 227
  DCHECK_EQ(dest, result->GetChars(no_gc));
  return result;
228
}
229
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
230
    Handle<String> AstConsString::AllocateFlat<Isolate>(Isolate* isolate) const;
231
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
232 233
    Handle<String> AstConsString::AllocateFlat<LocalIsolate>(
        LocalIsolate* isolate) const;
234

235 236 237 238 239 240 241 242 243 244 245 246 247 248
std::forward_list<const AstRawString*> AstConsString::ToRawStrings() const {
  std::forward_list<const AstRawString*> result;
  if (IsEmpty()) {
    return result;
  }

  result.emplace_front(segment_.string);
  for (AstConsString::Segment* current = segment_.next; current != nullptr;
       current = current->next) {
    result.emplace_front(current->string);
  }
  return result;
}

Yang Guo's avatar
Yang Guo committed
249
AstStringConstants::AstStringConstants(Isolate* isolate, uint64_t hash_seed)
250 251 252
    : zone_(isolate->allocator(), ZONE_NAME),
      string_table_(AstRawString::Compare),
      hash_seed_(hash_seed) {
Clemens Hammacher's avatar
Clemens Hammacher committed
253
  DCHECK_EQ(ThreadId::Current(), isolate->thread_id());
254 255 256 257 258 259 260 261 262 263 264 265 266 267 268
#define F(name, str)                                                      \
  {                                                                       \
    const char* data = str;                                               \
    Vector<const uint8_t> literal(reinterpret_cast<const uint8_t*>(data), \
                                  static_cast<int>(strlen(data)));        \
    uint32_t hash_field = StringHasher::HashSequentialString<uint8_t>(    \
        literal.begin(), literal.length(), hash_seed_);                   \
    name##_string_ = zone_.New<AstRawString>(true, literal, hash_field);  \
    /* The Handle returned by the factory is located on the roots */      \
    /* array, not on the temporary HandleScope, so this is safe.  */      \
    name##_string_->set_string(isolate->factory()->name##_string());      \
    base::HashMap::Entry* entry =                                         \
        string_table_.InsertNew(name##_string_, name##_string_->Hash());  \
    DCHECK_NULL(entry->value);                                            \
    entry->value = reinterpret_cast<void*>(1);                            \
269 270 271 272 273
  }
  AST_STRING_CONSTANTS(F)
#undef F
}

274
AstRawString* AstValueFactory::GetOneByteStringInternal(
275
    Vector<const uint8_t> literal) {
276 277 278
  if (literal.length() == 1 && literal[0] < kMaxOneCharStringValue) {
    int key = literal[0];
    if (V8_UNLIKELY(one_character_strings_[key] == nullptr)) {
279
      uint32_t hash_field = StringHasher::HashSequentialString<uint8_t>(
280
          literal.begin(), literal.length(), hash_seed_);
281
      one_character_strings_[key] = GetString(hash_field, true, literal);
282 283 284
    }
    return one_character_strings_[key];
  }
285
  uint32_t hash_field = StringHasher::HashSequentialString<uint8_t>(
286
      literal.begin(), literal.length(), hash_seed_);
287
  return GetString(hash_field, true, literal);
288 289
}

290
AstRawString* AstValueFactory::GetTwoByteStringInternal(
291
    Vector<const uint16_t> literal) {
292
  uint32_t hash_field = StringHasher::HashSequentialString<uint16_t>(
293
      literal.begin(), literal.length(), hash_seed_);
294
  return GetString(hash_field, false, Vector<const byte>::cast(literal));
295 296
}

297
const AstRawString* AstValueFactory::GetString(Handle<String> literal) {
298
  AstRawString* result = nullptr;
299
  DisallowHeapAllocation no_gc;
300
  String::FlatContent content = literal->GetFlatContent(no_gc);
301
  if (content.IsOneByte()) {
302
    result = GetOneByteStringInternal(content.ToOneByteVector());
303 304
  } else {
    DCHECK(content.IsTwoByte());
305
    result = GetTwoByteStringInternal(content.ToUC16Vector());
306
  }
307
  return result;
308 309
}

310 311 312 313 314 315 316 317
const AstRawString* AstValueFactory::CloneFromOtherFactory(
    const AstRawString* raw_string) {
  const AstRawString* result = GetString(
      raw_string->hash_field(), raw_string->is_one_byte(),
      Vector<const byte>(raw_string->raw_data(), raw_string->byte_length()));
  return result;
}

318
AstConsString* AstValueFactory::NewConsString() {
319
  return zone()->New<AstConsString>();
320 321
}

322
AstConsString* AstValueFactory::NewConsString(const AstRawString* str) {
323
  return NewConsString()->AddString(zone(), str);
324 325 326 327
}

AstConsString* AstValueFactory::NewConsString(const AstRawString* str1,
                                              const AstRawString* str2) {
328
  return NewConsString()->AddString(zone(), str1)->AddString(zone(), str2);
329 330
}

331 332
template <typename LocalIsolate>
void AstValueFactory::Internalize(LocalIsolate* isolate) {
333 334
  if (!zone_) return;

335
  // Strings need to be internalized before values, because values refer to
336
  // strings.
337 338
  for (AstRawString* current = strings_; current != nullptr;) {
    AstRawString* next = current->next();
339
    current->Internalize(isolate);
340 341 342
    current = next;
  }

343
  ResetStrings();
344
  zone_ = nullptr;
345
}
346
template EXPORT_TEMPLATE_DEFINE(
347 348 349
    V8_EXPORT_PRIVATE) void AstValueFactory::Internalize(Isolate* isolate);
template EXPORT_TEMPLATE_DEFINE(
    V8_EXPORT_PRIVATE) void AstValueFactory::Internalize(LocalIsolate* isolate);
350

351
AstRawString* AstValueFactory::GetString(uint32_t hash_field, bool is_one_byte,
352
                                         Vector<const byte> literal_bytes) {
353 354 355 356
  // literal_bytes here points to whatever the user passed, and this is OK
  // because we use vector_compare (which checks the contents) to compare
  // against the AstRawStrings which are in the string_table_. We should not
  // return this AstRawString.
357
  AstRawString key(is_one_byte, literal_bytes, hash_field);
358
  base::HashMap::Entry* entry = string_table_.LookupOrInsert(&key, key.Hash());
359
  if (entry->value == nullptr) {
360 361
    // Copy literal contents for later comparison.
    int length = literal_bytes.length();
362
    byte* new_literal_bytes = zone()->NewArray<byte>(length);
363
    memcpy(new_literal_bytes, literal_bytes.begin(), length);
364
    AstRawString* new_string = zone()->New<AstRawString>(
365
        is_one_byte, Vector<const byte>(new_literal_bytes, length), hash_field);
366 367
    CHECK_NOT_NULL(new_string);
    AddString(new_string);
368 369 370 371 372 373
    entry->key = new_string;
    entry->value = reinterpret_cast<void*>(1);
  }
  return reinterpret_cast<AstRawString*>(entry->key);
}

374 375
}  // namespace internal
}  // namespace v8