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