| // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| #include "vm/symbols.h" |
| |
| #include "vm/isolate.h" |
| #include "vm/object.h" |
| #include "vm/object_store.h" |
| #include "vm/raw_object.h" |
| #include "vm/snapshot_ids.h" |
| #include "vm/unicode.h" |
| #include "vm/visitor.h" |
| |
| namespace dart { |
| |
| RawString* Symbols::predefined_[Symbols::kMaxId]; |
| |
| static const char* names[] = { |
| NULL, |
| |
| #define DEFINE_SYMBOL_LITERAL(symbol, literal) \ |
| literal, |
| PREDEFINED_SYMBOLS_LIST(DEFINE_SYMBOL_LITERAL) |
| #undef DEFINE_SYMBOL_LITERAL |
| }; |
| |
| |
| const char* Symbols::Name(intptr_t symbol) { |
| ASSERT((symbol > kIllegal) && (symbol < kMaxId)); |
| return names[symbol]; |
| } |
| |
| |
| void Symbols::InitOnce(Isolate* isolate) { |
| // Should only be run by the vm isolate. |
| ASSERT(isolate == Dart::vm_isolate()); |
| |
| // Create and setup a symbol table in the vm isolate. |
| SetupSymbolTable(isolate); |
| |
| // Create all predefined symbols. |
| ASSERT((sizeof(names) / sizeof(const char*)) == Symbols::kMaxId); |
| ObjectStore* object_store = isolate->object_store(); |
| Array& symbol_table = Array::Handle(); |
| dart::String& str = String::Handle(); |
| |
| for (intptr_t i = 1; i < Symbols::kMaxId; i++) { |
| // The symbol_table needs to be reloaded as it might have grown in the |
| // previous iteration. |
| symbol_table = object_store->symbol_table(); |
| str = OneByteString::New(names[i], Heap::kOld); |
| Add(symbol_table, str); |
| predefined_[i] = str.raw(); |
| } |
| Object::RegisterSingletonClassNames(); |
| } |
| |
| |
| void Symbols::SetupSymbolTable(Isolate* isolate) { |
| ASSERT(isolate != NULL); |
| |
| // Setup the symbol table used within the String class. |
| const int initial_size = (isolate == Dart::vm_isolate()) ? |
| kInitialVMIsolateSymtabSize : kInitialSymtabSize; |
| const Array& array = Array::Handle(Array::New(initial_size + 1)); |
| |
| // Last element contains the count of used slots. |
| array.SetAt(initial_size, Smi::Handle(Smi::New(0))); |
| isolate->object_store()->set_symbol_table(array); |
| } |
| |
| |
| intptr_t Symbols::Size(Isolate* isolate) { |
| ASSERT(isolate != NULL); |
| Array& symbol_table = Array::Handle(isolate, |
| isolate->object_store()->symbol_table()); |
| intptr_t table_size_index = symbol_table.Length() - 1; |
| dart::Smi& used = Smi::Handle(); |
| used ^= symbol_table.At(table_size_index); |
| return used.Value(); |
| } |
| |
| |
| void Symbols::Add(const Array& symbol_table, const String& str) { |
| // Should only be run by the vm isolate. |
| ASSERT(Isolate::Current() == Dart::vm_isolate()); |
| intptr_t hash = str.Hash(); |
| intptr_t index = FindIndex(symbol_table, str, 0, str.Length(), hash); |
| ASSERT(symbol_table.At(index) == String::null()); |
| InsertIntoSymbolTable(symbol_table, str, index); |
| } |
| |
| |
| RawString* Symbols::New(const char* str) { |
| ASSERT(str != NULL); |
| Utf8::Type type; |
| intptr_t str_len = strlen(str); |
| const uint8_t* utf8_array = reinterpret_cast<const uint8_t*>(str); |
| intptr_t len = Utf8::CodePointCount(utf8_array, str_len, &type); |
| Zone* zone = Isolate::Current()->current_zone(); |
| if (len == 0) { |
| return Symbols::New(reinterpret_cast<uint8_t*>(NULL), 0); |
| } |
| if (type == Utf8::kLatin1) { |
| uint8_t* characters = zone->Alloc<uint8_t>(len); |
| Utf8::DecodeToLatin1(utf8_array, str_len, characters, len); |
| return New(characters, len); |
| } |
| ASSERT((type == Utf8::kBMP) || (type == Utf8::kSMP)); |
| uint16_t* characters = zone->Alloc<uint16_t>(len); |
| Utf8::DecodeToUTF16(utf8_array, str_len, characters, len); |
| return New(characters, len); |
| } |
| |
| |
| template<typename T> |
| RawString* Symbols::New(const T* characters, intptr_t len) { |
| Isolate* isolate = Isolate::Current(); |
| ASSERT(isolate != Dart::vm_isolate()); |
| String& symbol = String::Handle(isolate, String::null()); |
| Array& symbol_table = Array::Handle(isolate, Array::null()); |
| |
| // Calculate the String hash for this sequence of characters. |
| intptr_t hash = String::Hash(characters, len); |
| |
| // First check if a symbol exists in the vm isolate for these characters. |
| symbol_table = Dart::vm_isolate()->object_store()->symbol_table(); |
| intptr_t index = FindIndex(symbol_table, characters, len, hash); |
| symbol ^= symbol_table.At(index); |
| if (symbol.IsNull()) { |
| // Now try in the symbol table of the current isolate. |
| symbol_table = isolate->object_store()->symbol_table(); |
| index = FindIndex(symbol_table, characters, len, hash); |
| // Since we leave enough room in the table to guarantee, that we find an |
| // empty spot, index is the insertion point if symbol is null. |
| symbol ^= symbol_table.At(index); |
| if (symbol.IsNull()) { |
| // Allocate new result string. |
| symbol = String::New(characters, len, Heap::kOld); |
| symbol.SetHash(hash); // Remember the calculated hash value. |
| InsertIntoSymbolTable(symbol_table, symbol, index); |
| } |
| } |
| ASSERT(symbol.IsSymbol()); |
| return symbol.raw(); |
| } |
| |
| template RawString* Symbols::New(const uint8_t* characters, intptr_t len); |
| template RawString* Symbols::New(const uint16_t* characters, intptr_t len); |
| template RawString* Symbols::New(const uint32_t* characters, intptr_t len); |
| |
| |
| RawString* Symbols::New(const String& str) { |
| if (str.IsSymbol()) { |
| return str.raw(); |
| } |
| return New(str, 0, str.Length()); |
| } |
| |
| |
| RawString* Symbols::New(const String& str, intptr_t begin_index, intptr_t len) { |
| ASSERT(begin_index >= 0); |
| ASSERT(len >= 0); |
| ASSERT((begin_index + len) <= str.Length()); |
| Isolate* isolate = Isolate::Current(); |
| ASSERT(isolate != Dart::vm_isolate()); |
| String& symbol = String::Handle(isolate, String::null()); |
| Array& symbol_table = Array::Handle(isolate, Array::null()); |
| |
| // Calculate the String hash for this sequence of characters. |
| intptr_t hash = (begin_index == 0 && len == str.Length()) ? str.Hash() : |
| String::Hash(str, begin_index, len); |
| |
| // First check if a symbol exists in the vm isolate for these characters. |
| symbol_table = Dart::vm_isolate()->object_store()->symbol_table(); |
| intptr_t index = FindIndex(symbol_table, str, begin_index, len, hash); |
| symbol ^= symbol_table.At(index); |
| if (symbol.IsNull()) { |
| // Now try in the symbol table of the current isolate. |
| symbol_table = isolate->object_store()->symbol_table(); |
| index = FindIndex(symbol_table, str, begin_index, len, hash); |
| // Since we leave enough room in the table to guarantee, that we find an |
| // empty spot, index is the insertion point if symbol is null. |
| symbol ^= symbol_table.At(index); |
| if (symbol.IsNull()) { |
| if (str.IsOld() && begin_index == 0 && len == str.Length()) { |
| // Reuse the incoming str as the symbol value. |
| symbol = str.raw(); |
| } else { |
| // Allocate a copy in old space. |
| symbol = String::SubString(str, begin_index, len, Heap::kOld); |
| symbol.SetHash(hash); |
| } |
| InsertIntoSymbolTable(symbol_table, symbol, index); |
| } |
| } |
| ASSERT(symbol.IsSymbol()); |
| return symbol.raw(); |
| } |
| |
| |
| void Symbols::GrowSymbolTable(const Array& symbol_table) { |
| // TODO(iposva): Avoid exponential growth. |
| intptr_t table_size = symbol_table.Length() - 1; |
| intptr_t new_table_size = table_size * 2; |
| Array& new_symbol_table = Array::Handle(Array::New(new_table_size + 1)); |
| // Copy all elements from the original symbol table to the newly allocated |
| // array. |
| String& element = String::Handle(); |
| dart::Object& new_element = Object::Handle(); |
| for (intptr_t i = 0; i < table_size; i++) { |
| element ^= symbol_table.At(i); |
| if (!element.IsNull()) { |
| intptr_t hash = element.Hash(); |
| intptr_t index = hash % new_table_size; |
| new_element = new_symbol_table.At(index); |
| while (!new_element.IsNull()) { |
| index = (index + 1) % new_table_size; // Move to next element. |
| new_element = new_symbol_table.At(index); |
| } |
| new_symbol_table.SetAt(index, element); |
| } |
| } |
| // Copy used count. |
| new_element = symbol_table.At(table_size); |
| new_symbol_table.SetAt(new_table_size, new_element); |
| // Remember the new symbol table now. |
| Isolate::Current()->object_store()->set_symbol_table(new_symbol_table); |
| } |
| |
| |
| void Symbols::InsertIntoSymbolTable(const Array& symbol_table, |
| const String& symbol, |
| intptr_t index) { |
| intptr_t table_size = symbol_table.Length() - 1; |
| symbol.SetCanonical(); // Mark object as being canonical. |
| symbol_table.SetAt(index, symbol); // Remember the new symbol. |
| dart::Smi& used = Smi::Handle(); |
| used ^= symbol_table.At(table_size); |
| intptr_t used_elements = used.Value() + 1; // One more element added. |
| used = Smi::New(used_elements); |
| symbol_table.SetAt(table_size, used); // Update used count. |
| |
| // Rehash if symbol_table is 75% full. |
| if (used_elements > ((table_size / 4) * 3)) { |
| GrowSymbolTable(symbol_table); |
| } |
| } |
| |
| |
| template<typename T> |
| intptr_t Symbols::FindIndex(const Array& symbol_table, |
| const T* characters, |
| intptr_t len, |
| intptr_t hash) { |
| // Last element of the array is the number of used elements. |
| intptr_t table_size = symbol_table.Length() - 1; |
| intptr_t index = hash % table_size; |
| |
| String& symbol = String::Handle(); |
| symbol ^= symbol_table.At(index); |
| while (!symbol.IsNull() && !symbol.Equals(characters, len)) { |
| index = (index + 1) % table_size; // Move to next element. |
| symbol ^= symbol_table.At(index); |
| } |
| return index; // Index of symbol if found or slot into which to add symbol. |
| } |
| |
| |
| template intptr_t Symbols::FindIndex(const Array& symbol_table, |
| const uint8_t* characters, |
| intptr_t len, |
| intptr_t hash); |
| template intptr_t Symbols::FindIndex(const Array& symbol_table, |
| const uint16_t* characters, |
| intptr_t len, |
| intptr_t hash); |
| template intptr_t Symbols::FindIndex(const Array& symbol_table, |
| const uint32_t* characters, |
| intptr_t len, |
| intptr_t hash); |
| |
| |
| intptr_t Symbols::FindIndex(const Array& symbol_table, |
| const String& str, |
| intptr_t begin_index, |
| intptr_t len, |
| intptr_t hash) { |
| // Last element of the array is the number of used elements. |
| intptr_t table_size = symbol_table.Length() - 1; |
| intptr_t index = hash % table_size; |
| |
| String& symbol = String::Handle(); |
| symbol ^= symbol_table.At(index); |
| while (!symbol.IsNull() && !symbol.Equals(str, begin_index, len)) { |
| index = (index + 1) % table_size; // Move to next element. |
| symbol ^= symbol_table.At(index); |
| } |
| return index; // Index of symbol if found or slot into which to add symbol. |
| } |
| |
| |
| intptr_t Symbols::LookupVMSymbol(RawObject* obj) { |
| for (intptr_t i = 1; i < Symbols::kMaxId; i++) { |
| if (predefined_[i] == obj) { |
| return (i + kMaxPredefinedObjectIds); |
| } |
| } |
| return kInvalidIndex; |
| } |
| |
| |
| RawObject* Symbols::GetVMSymbol(intptr_t object_id) { |
| ASSERT(IsVMSymbolId(object_id)); |
| intptr_t i = (object_id - kMaxPredefinedObjectIds); |
| return (i > 0 && i < Symbols::kMaxId) ? predefined_[i] : Object::null(); |
| } |
| |
| } // namespace dart |