Implement Harmony sets and maps.

src/objects.cc

 // Copyright 2011 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
@@ skipping 705 matching lines @@
     return context->string_function()->instance_prototype();
   }
   if (heap_object->IsBoolean()) {
     return context->boolean_function()->instance_prototype();
   } else {
     return heap->null_value();
   }
 }
 
 
+uint32_t Object::GetHash() {
+  // The object is either a number, a string, an odd-ball,
+  // a real JS object, or a Harmony proxy.
+  if (IsNumber()) return ComputeLongHash(double_to_uint64(Number()));
+  if (IsString()) return String::cast(this)->Hash();
+  if (IsOddball()) return Oddball::cast(this)->to_string()->Hash();
+  if (IsJSReceiver()) {
+    MaybeObject* maybe_hash =
+        JSReceiver::cast(this)->GetIdentityHash(OMIT_CREATION);
+    ASSERT(!maybe_hash->IsFailure());
+    return Smi::cast(maybe_hash->ToObjectUnchecked())->value();
+  }
+
+  UNREACHABLE();
+  return 0;
+}
+
+
+bool Object::SameValue(Object* other) {
+  if (other == this) return true;
+  if (!IsHeapObject() || !other->IsHeapObject()) return false;
+
+  // The object is either a number, a string, an odd-ball,
+  // a real JS object, or a Harmony proxy.
+  if (IsNumber() && other->IsNumber()) {
+    double this_value = Number();
+    double other_value = other->Number();
+    if (isnan(this_value) && isnan(other_value)) return true;
+    return this_value == other_value;

[rossberg, 2011/10/24 15:44:11]

Test the common case first. Also, you can condense these two lines to

return this == that || (isnan(this) && isnan(that));

[Michael Starzinger, 2011/10/25 11:17:26]

Done.

+  }
+  if (IsString() && other->IsString()) {
+    return String::cast(this)->Equals(String::cast(other));
+  }
+  return false;
+}
+
+
 void Object::ShortPrint(FILE* out) {
   HeapStringAllocator allocator;
   StringStream accumulator(&allocator);
   ShortPrint(&accumulator);
   accumulator.OutputToFile(out);
 }
 
 
 void Object::ShortPrint(StringStream* accumulator) {
   if (IsSmi()) {
@@ skipping 527 matching lines @@
   switch (type) {
     case FIXED_ARRAY_TYPE:
       FixedArray::BodyDescriptor::IterateBody(this, object_size, v);
       break;
     case FIXED_DOUBLE_ARRAY_TYPE:
       break;
     case JS_OBJECT_TYPE:
     case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
     case JS_VALUE_TYPE:
     case JS_ARRAY_TYPE:
+    case JS_SET_TYPE:
+    case JS_MAP_TYPE:
     case JS_WEAK_MAP_TYPE:
     case JS_REGEXP_TYPE:
     case JS_GLOBAL_PROXY_TYPE:
     case JS_GLOBAL_OBJECT_TYPE:
     case JS_BUILTINS_OBJECT_TYPE:
     case JS_MESSAGE_OBJECT_TYPE:
       JSObject::BodyDescriptor::IterateBody(this, object_size, v);
       break;
     case JS_FUNCTION_TYPE:
       reinterpret_cast<JSFunction*>(this)
@@ skipping 9537 matching lines @@
 
 // Force instantiation of template instances class.
 // Please note this list is compiler dependent.
 
 template class HashTable<SymbolTableShape, HashTableKey*>;
 
 template class HashTable<CompilationCacheShape, HashTableKey*>;
 
 template class HashTable<MapCacheShape, HashTableKey*>;
 
-template class HashTable<ObjectHashTableShape, JSReceiver*>;
+template class HashTable<ObjectHashTableShape<1>, Object*>;
+
+template class HashTable<ObjectHashTableShape<2>, Object*>;
 
 template class Dictionary<StringDictionaryShape, String*>;
 
 template class Dictionary<NumberDictionaryShape, uint32_t>;
 
 template MaybeObject* Dictionary<NumberDictionaryShape, uint32_t>::Allocate(
     int);
 
 template MaybeObject* Dictionary<StringDictionaryShape, String*>::Allocate(
     int);
@@ skipping 1325 matching lines @@
   ASSERT(obj->IsJSObject());
 
   descriptors->SetNextEnumerationIndex(NextEnumerationIndex());
   // Check that it really works.
   ASSERT(obj->HasFastProperties());
 
   return obj;
 }
 
 
-Object* ObjectHashTable::Lookup(JSReceiver* key) {
+bool ObjectHashSet::Contains(Object* key) {
   // If the object does not have an identity hash, it was never used as a key.
-  MaybeObject* maybe_hash = key->GetIdentityHash(OMIT_CREATION);
-  if (maybe_hash->IsFailure()) return GetHeap()->undefined_value();
+  if (key->IsJSReceiver() && !JSReceiver::cast(key)->HasIdentityHash()) {
+    return false;
+  }
+  return (FindEntry(key) != kNotFound);
+}
+
+
+MaybeObject* ObjectHashSet::Add(Object* key) {
+  // Make sure the key object has an identity hash code.
+  int hash;
+  if (key->IsJSReceiver()) {

[rossberg, 2011/10/24 15:44:11]

For example, this conditional is redundant if GetHash created a hash. (Same in
Put.)

[Michael Starzinger, 2011/10/25 11:17:26]

Done (see comment in objects.h).

+    MaybeObject* maybe_hash =
+        JSReceiver::cast(key)->GetIdentityHash(ALLOW_CREATION);
+    if (maybe_hash->IsFailure()) return maybe_hash;
+    hash = Smi::cast(maybe_hash->ToObjectUnchecked())->value();
+  } else {
+    hash = key->GetHash();
+  }
+  int entry = FindEntry(key);
+
+  // Check whether key is already present.
+  if (entry != kNotFound) return this;
+
+  // Check whether the hash set should be extended and add entry.
+  Object* obj;
+  { MaybeObject* maybe_obj = EnsureCapacity(1, key);
+    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+  }
+  ObjectHashSet* table = ObjectHashSet::cast(obj);
+  entry = table->FindInsertionEntry(hash);
+  table->set(EntryToIndex(entry), key);
+  table->ElementAdded();
+  return table;
+}
+
+
+MaybeObject* ObjectHashSet::Remove(Object* key) {
+  // If the object does not have an identity hash, it was never used as a key.
+  if (key->IsJSReceiver() && !JSReceiver::cast(key)->HasIdentityHash()) {
+    return this;
+  }
+  int entry = FindEntry(key);
+
+  // Check whether key is actually present.
+  if (entry == kNotFound) return this;
+
+  // Remove entry and try to shrink this hash set.
+  set_null(EntryToIndex(entry));
+  ElementRemoved();
+  return Shrink(key);
+}
+
+
+Object* ObjectHashTable::Lookup(Object* key) {
+  // If the object does not have an identity hash, it was never used as a key.
+  if (key->IsJSReceiver() && !JSReceiver::cast(key)->HasIdentityHash()) {
+    return GetHeap()->undefined_value();
+  }
   int entry = FindEntry(key);
   if (entry == kNotFound) return GetHeap()->undefined_value();
   return get(EntryToIndex(entry) + 1);
 }
 
 
-MaybeObject* ObjectHashTable::Put(JSReceiver* key, Object* value) {
+MaybeObject* ObjectHashTable::Put(Object* key, Object* value) {
   // Make sure the key object has an identity hash code.
   int hash;
-  { MaybeObject* maybe_hash = key->GetIdentityHash(ALLOW_CREATION);
+  if (key->IsJSReceiver()) {
+    MaybeObject* maybe_hash =
+        JSReceiver::cast(key)->GetIdentityHash(ALLOW_CREATION);
     if (maybe_hash->IsFailure()) return maybe_hash;
     hash = Smi::cast(maybe_hash->ToObjectUnchecked())->value();
+  } else {
+    hash = key->GetHash();
   }
   int entry = FindEntry(key);
 
   // Check whether to perform removal operation.
   if (value->IsUndefined()) {
     if (entry == kNotFound) return this;
     RemoveEntry(entry);
     return Shrink(key);
   }
 
   // Key is already in table, just overwrite value.
   if (entry != kNotFound) {
     set(EntryToIndex(entry) + 1, value);
     return this;
   }
 
   // Check whether the hash table should be extended.
   Object* obj;
   { MaybeObject* maybe_obj = EnsureCapacity(1, key);
     if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
   ObjectHashTable* table = ObjectHashTable::cast(obj);
   table->AddEntry(table->FindInsertionEntry(hash), key, value);
   return table;
 }
 
 
-void ObjectHashTable::AddEntry(int entry, JSReceiver* key, Object* value) {
+void ObjectHashTable::AddEntry(int entry, Object* key, Object* value) {
   set(EntryToIndex(entry), key);
   set(EntryToIndex(entry) + 1, value);
   ElementAdded();
 }
 
 
 void ObjectHashTable::RemoveEntry(int entry, Heap* heap) {
   set_null(heap, EntryToIndex(entry));
   set_null(heap, EntryToIndex(entry) + 1);
   ElementRemoved();
@@ skipping 247 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single break point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif  // ENABLE_DEBUGGER_SUPPORT
 
 
 } }  // namespace v8::internal