Reintroduced dictionary that can use objects as keys.

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 2946 matching lines @@
     PrintF("Object elements have been normalized:\n");
     Print();
   }
 #endif
 
   ASSERT(HasDictionaryElements() || HasDictionaryArgumentsElements());
   return dictionary;
 }
 
 
+MaybeObject* JSObject::GetHiddenProperties(bool create_if_needed) {
+  Isolate* isolate = GetIsolate();
+  Heap* heap = isolate->heap();
+  Object* holder = BypassGlobalProxy();
+  if (holder->IsUndefined()) return heap->undefined_value();
+  JSObject* obj = JSObject::cast(holder);
+  if (obj->HasFastProperties()) {
+    // If the object has fast properties, check whether the first slot
+    // in the descriptor array matches the hidden symbol. Since the
+    // hidden symbols hash code is zero (and no other string has hash
+    // code zero) it will always occupy the first entry if present.
+    DescriptorArray* descriptors = obj->map()->instance_descriptors();
+    if ((descriptors->number_of_descriptors() > 0) &&
+        (descriptors->GetKey(0) == heap->hidden_symbol()) &&
+        descriptors->IsProperty(0)) {
+      ASSERT(descriptors->GetType(0) == FIELD);
+      return obj->FastPropertyAt(descriptors->GetFieldIndex(0));
+    }
+  }
+
+  // Only attempt to find the hidden properties in the local object and not
+  // in the prototype chain.  Note that HasLocalProperty() can cause a GC in

[Vitaly Repeshko, 2011/07/26 13:53:14]

The comment about HasLocalProperty should be moved to where it's called in the
function below. Also it'd be nice to add AssertNoAllocation there.

[Michael Starzinger, 2011/07/26 22:30:23]

Fixed.

+  // the general case in the presence of interceptors.
+  if (!obj->HasHiddenPropertiesObject()) {
+    // Hidden properties object not found. Allocate a new hidden properties
+    // object if requested. Otherwise return the undefined value.
+    if (create_if_needed) {
+      Object* hidden_obj;
+      { MaybeObject* maybe_obj = heap->AllocateJSObject(
+            isolate->context()->global_context()->object_function());
+        if (!maybe_obj->ToObject(&hidden_obj)) return maybe_obj;
+      }
+      return obj->SetHiddenPropertiesObject(hidden_obj);
+    } else {
+      return heap->undefined_value();
+    }
+  }
+  return obj->GetHiddenPropertiesObject();
+}
+
+
+MaybeObject* JSObject::GetIdentityHash() {
+  Isolate* isolate = GetIsolate();
+  Object* hidden_props_obj;
+  { MaybeObject* maybe_obj = GetHiddenProperties(true);
+    if (!maybe_obj->ToObject(&hidden_props_obj)) return maybe_obj;
+  }
+  if (!hidden_props_obj->IsJSObject()) {
+    // We failed to create hidden properties.  That's a detached
+    // global proxy.
+    ASSERT(hidden_props_obj->IsUndefined());
+    return Smi::FromInt(0);
+  }
+  JSObject* hidden_props = JSObject::cast(hidden_props_obj);
+  String* hash_symbol = isolate->heap()->identity_hash_symbol();
+  if (hidden_props->HasLocalProperty(hash_symbol)) {
+    MaybeObject* hash = hidden_props->GetProperty(hash_symbol);
+    return Smi::cast(hash->ToObjectChecked());
+  }
+
+  int hash_value;
+  int attempts = 0;
+  do {
+    // Generate a random 32-bit hash value but limit range to fit
+    // within a smi.
+    hash_value = V8::Random(isolate) & Smi::kMaxValue;
+    attempts++;
+  } while (hash_value == 0 && attempts < 30);
+  hash_value = hash_value != 0 ? hash_value : 1;  // never return 0
+
+  Smi* hash = Smi::FromInt(hash_value);
+  { MaybeObject* result = hidden_props->SetLocalPropertyIgnoreAttributes(
+        hash_symbol,
+        hash,
+        static_cast<PropertyAttributes>(None));
+    if (result->IsFailure()) return result;
+  }
+  return hash;
+}
+
+
 MaybeObject* JSObject::DeletePropertyPostInterceptor(String* name,
                                                      DeleteMode mode) {
   // Check local property, ignore interceptor.
   LookupResult result;
   LocalLookupRealNamedProperty(name, &result);
   if (!result.IsProperty()) return GetHeap()->true_value();
 
   // Normalize object if needed.
   Object* obj;
   { MaybeObject* maybe_obj = NormalizeProperties(CLEAR_INOBJECT_PROPERTIES, 0);
@@ skipping 7389 matching lines @@
 template class HashTable<SymbolTableShape, HashTableKey*>;
 
 template class HashTable<CompilationCacheShape, HashTableKey*>;
 
 template class HashTable<MapCacheShape, HashTableKey*>;
 
 template class Dictionary<StringDictionaryShape, String*>;
 
 template class Dictionary<NumberDictionaryShape, uint32_t>;
 
+template class Dictionary<ObjectDictionaryShape, JSObject*>;
+
 template MaybeObject* Dictionary<NumberDictionaryShape, uint32_t>::Allocate(
     int);
 
 template MaybeObject* Dictionary<StringDictionaryShape, String*>::Allocate(
     int);
 
+template MaybeObject* Dictionary<ObjectDictionaryShape, JSObject*>::Allocate(
+    int);
+
 template MaybeObject* Dictionary<NumberDictionaryShape, uint32_t>::AtPut(
     uint32_t, Object*);
 
 template Object* Dictionary<NumberDictionaryShape, uint32_t>::SlowReverseLookup(
     Object*);
 
 template Object* Dictionary<StringDictionaryShape, String*>::SlowReverseLookup(
     Object*);
 
 template void Dictionary<NumberDictionaryShape, uint32_t>::CopyKeysTo(
@@ skipping 976 matching lines @@
   // Insert element at empty or deleted entry
   if (!details.IsDeleted() && details.index() == 0 && Shape::kIsEnumerable) {
     // Assign an enumeration index to the property and update
     // SetNextEnumerationIndex.
     int index = NextEnumerationIndex();
     details = PropertyDetails(details.attributes(), details.type(), index);
     SetNextEnumerationIndex(index + 1);
   }
   SetEntry(entry, k, value, details);
   ASSERT((Dictionary<Shape, Key>::KeyAt(entry)->IsNumber()
-          || Dictionary<Shape, Key>::KeyAt(entry)->IsString()));
+          || Dictionary<Shape, Key>::KeyAt(entry)->IsString()
+          || Dictionary<Shape, Key>::KeyAt(entry)->IsJSObject()));
   HashTable<Shape, Key>::ElementAdded();
   return this;
 }
 
 
 void NumberDictionary::UpdateMaxNumberKey(uint32_t key) {
   // If the dictionary requires slow elements an element has already
   // been added at a high index.
   if (requires_slow_elements()) return;
   // Check if this index is high enough that we should require slow
@@ skipping 284 matching lines @@
   ASSERT(obj->IsJSObject());
 
   descriptors->SetNextEnumerationIndex(NextEnumerationIndex());
   // Check that it really works.
   ASSERT(obj->HasFastProperties());
 
   return obj;
 }
 
 
+int ObjectDictionary::FindEntry(JSObject* key) {
+  // If the object does not have an identity hash, it was never used as a key.
+  MaybeObject* maybe_hash = key->GetIdentityHash();

[Vitaly Repeshko, 2011/07/26 13:53:14]

It'd be nice to avoid allocating a hidden properties object in this case. Looks
like GetIdentityHash needs create_if_needed too. Since the flag gets more usage
our style is to create an enum for it to aid readability.

[Michael Starzinger, 2011/07/26 22:30:23]

Fixed (partially, didn't create an enum so far). I suggest turning it into an
enum in a separate CL.

[Vitaly Repeshko, 2011/07/27 15:42:26]

Why do you want to add the enum in a separate CL? Seems like a logical part of
this change to me.

[Michael Starzinger, 2011/07/28 01:23:18]

Fixed. Ok. :)

+  if (maybe_hash->IsFailure()) return kNotFound;
+  return Dictionary<ObjectDictionaryShape, JSObject*>::FindEntry(key);
+}
+
+
+MaybeObject* ObjectDictionary::Add(JSObject* key, Object* value) {
+  // Make sure the key object has an identity hash code.
+  MaybeObject* maybe_hash = key->GetIdentityHash();
+  if (maybe_hash->IsFailure()) return maybe_hash;
+  PropertyDetails details(NONE, NORMAL);
+  return Dictionary<ObjectDictionaryShape, JSObject*>::Add(key, value, details);
+}
+
+
 #ifdef ENABLE_DEBUGGER_SUPPORT
 // Check if there is a break point at this code position.
 bool DebugInfo::HasBreakPoint(int code_position) {
   // Get the break point info object for this code position.
   Object* break_point_info = GetBreakPointInfo(code_position);
 
   // If there is no break point info object or no break points in the break
   // point info object there is no break point at this code position.
   if (break_point_info->IsUndefined()) return false;
   return BreakPointInfo::cast(break_point_info)->GetBreakPointCount() > 0;
@@ skipping 234 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single beak point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif
 
 
 } }  // namespace v8::internal