Reintroduced dictionary that can use objects as keys.

Reintroduced dictionary that can use objects as keys.

R=vitalyr@chromium.org
TEST=cctest/test-dictionary

Committed: http://code.google.com/p/v8/source/detail?r=8761

[Michael Starzinger, 2011-07-15 15:18:06]

Verified that this removes the regression in the webkit
http/tests/plugins/geturlnotify-from-npp-destroystr* test case.

[Michael Starzinger, 2011-07-25 17:17:22]

Since Slava is on vacation I thought it would be great if someone else could
review this. Is it OK to pass this on to you Mads?

[Vitaly Repeshko, 2011-07-25 17:37:17]

I'd be happy to review this, but I don't understand how it's supposed to work
when a hash allocation fails on lookup? E.g., if I add this code to the provided
test

  for (int i = 0; i < 100000; i++) {
    Handle<JSObject> o = FACTORY->NewJSArray(100);
    dict->FindEntry(*o);
  }

it triggers the assert below

4365	uint32_t ObjectDictionaryShape::Hash(JSObject* key) {
4366	  MaybeObject* maybe_hash = key->GetIdentityHash();
4367	  ASSERT(!maybe_hash->IsFailure());
4368	  return Smi::cast(maybe_hash->ToObjectUnchecked())->value();
4369	}

[Vitaly Repeshko, 2011-07-25 17:45:17]

I guess the intent was to rely on the fact that objects without allocated hash
codes can't possibly be already present as keys in a dictionary. In this case
the lookup logic should probably use a dummy hash code.

On 2011/07/25 17:37:17, Vitaly Repeshko wrote:
> I'd be happy to review this, but I don't understand how it's supposed to work
> when a hash allocation fails on lookup? E.g., if I add this code to the
provided
> test
> 
>   for (int i = 0; i < 100000; i++) {
>     Handle<JSObject> o = FACTORY->NewJSArray(100);
>     dict->FindEntry(*o);
>   }
> 
> it triggers the assert below
> 
> 4365	uint32_t ObjectDictionaryShape::Hash(JSObject* key) {
> 4366	  MaybeObject* maybe_hash = key->GetIdentityHash();
> 4367	  ASSERT(!maybe_hash->IsFailure());
> 4368	  return Smi::cast(maybe_hash->ToObjectUnchecked())->value();
> 4369	}

[Michael Starzinger, 2011-07-25 17:52:06]

Yes, ObjectDictionary::AddChecked (suggestions for a better name appreciated)
makes sure each object added to the dictionary has a hash attached to it. You
are right, lookups of objects not in the table trigger the assertion. I will fix
that. Thanks!

On 2011/07/25 17:45:17, Vitaly Repeshko wrote:
> I guess the intent was to rely on the fact that objects without allocated hash
> codes can't possibly be already present as keys in a dictionary. In this case
> the lookup logic should probably use a dummy hash code.
> 
> On 2011/07/25 17:37:17, Vitaly Repeshko wrote:
> > I'd be happy to review this, but I don't understand how it's supposed to
work
> > when a hash allocation fails on lookup? E.g., if I add this code to the
> provided
> > test
> > 
> >   for (int i = 0; i < 100000; i++) {
> >     Handle<JSObject> o = FACTORY->NewJSArray(100);
> >     dict->FindEntry(*o);
> >   }
> > 
> > it triggers the assert below
> > 
> > 4365	uint32_t ObjectDictionaryShape::Hash(JSObject* key) {
> > 4366	  MaybeObject* maybe_hash = key->GetIdentityHash();
> > 4367	  ASSERT(!maybe_hash->IsFailure());
> > 4368	  return Smi::cast(maybe_hash->ToObjectUnchecked())->value();
> > 4369	}

[Michael Starzinger, 2011-07-26 01:04:52]

Added the test snippet from Vitaly to cctest. I decided to completely overload
Dictionary::FindEntry and Dictionary::Add, because the base implementation
should not be called for object dictionaries anyways.

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

http://codereview.chromium.org/7385006/diff/7003/src/handles.cc
File src/handles.cc (right):

http://codereview.chromium.org/7385006/diff/7003/src/handles.cc#newcode433
src/handles.cc:433: CALL_HEAP_FUNCTION(obj->GetIsolate(),
obj->GetIdentityHash(), Smi);
Creating a handle for a Smi is a waste. Use something like
CALL_AND_RETRY(obj->GetIsolate(),
               obj->GetIdentityHash(),
               Smi::cast(__object__)->value(),
               0)
and change the return type to int.

http://codereview.chromium.org/7385006/diff/7003/src/objects-inl.h
File src/objects-inl.h (right):

http://codereview.chromium.org/7385006/diff/7003/src/objects-inl.h#newcode4360
src/objects-inl.h:4360: ASSERT(other->IsJSObject());
JSObject::cast does the same assert.

http://codereview.chromium.org/7385006/diff/7003/src/objects-inl.h#newcode4373
src/objects-inl.h:4373: ASSERT(other->IsJSObject());
Ditto.

http://codereview.chromium.org/7385006/diff/7003/src/objects.cc
File src/objects.cc (right):

http://codereview.chromium.org/7385006/diff/7003/src/objects.cc#newcode2988
src/objects.cc:2988: // in the prototype chain.  Note that HasLocalProperty()
can cause a GC in
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.

http://codereview.chromium.org/7385006/diff/7003/src/objects.cc#newcode11772
src/objects.cc:11772: MaybeObject* maybe_hash = key->GetIdentityHash();
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.

http://codereview.chromium.org/7385006/diff/7003/src/objects.h
File src/objects.h (right):

http://codereview.chromium.org/7385006/diff/7003/src/objects.h#newcode1641
src/objects.h:1641: MUST_USE_RESULT MaybeObject* GetHiddenProperties(bool
create_if_needed);
Document what is returned when there are no existing hidden properties and
create_if_needed is false.

http://codereview.chromium.org/7385006/diff/7003/src/objects.h#newcode2933
src/objects.h:2933: class ObjectDictionary: public
Dictionary<ObjectDictionaryShape, JSObject*> {
Needs a comment.

http://codereview.chromium.org/7385006/diff/7003/src/objects.h#newcode2942
src/objects.h:2942: int FindEntry(Isolate* isolate, JSObject* key);
Doesn't seem to be defined/called. Remove?

http://codereview.chromium.org/7385006/diff/7003/src/objects.h#newcode2946
src/objects.h:2946: MUST_USE_RESULT MaybeObject* Add(JSObject* key,
Same here.

Are PropertyDetails really required? If not, change the entry size in the shape
to 2.

http://codereview.chromium.org/7385006/diff/7003/test/cctest/test-dictionary.cc
File test/cctest/test-dictionary.cc (right):

http://codereview.chromium.org/7385006/diff/7003/test/cctest/test-dictionary....
test/cctest/test-dictionary.cc:41: static Handle<ObjectDictionary>
NewObjectDictionary(int at_least_space_for) {
Make this a method on Factory?

http://codereview.chromium.org/7385006/diff/7003/test/cctest/test-dictionary....
test/cctest/test-dictionary.cc:48: TEST(ObjectDictionary) {
Test adding more entries to the dictionary and check the returned values.

http://codereview.chromium.org/7385006/diff/7003/test/cctest/test-dictionary....
test/cctest/test-dictionary.cc:66: Handle<JSObject> o =
FACTORY->NewJSArray(100);
We need larger arrays here to exhaust the new space. There's a flag
max_new_space_size that can help, but I'm not sure how to use it in a cctest.

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

http://codereview.chromium.org/7385006/diff/7003/src/handles.cc
File src/handles.cc (right):

http://codereview.chromium.org/7385006/diff/7003/src/handles.cc#newcode433
src/handles.cc:433: CALL_HEAP_FUNCTION(obj->GetIsolate(),
obj->GetIdentityHash(), Smi);
On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> Creating a handle for a Smi is a waste. Use something like
> CALL_AND_RETRY(obj->GetIsolate(),
>                obj->GetIdentityHash(),
>                Smi::cast(__object__)->value(),
>                0)
> and change the return type to int.

Fixed.

http://codereview.chromium.org/7385006/diff/7003/src/objects-inl.h
File src/objects-inl.h (right):

http://codereview.chromium.org/7385006/diff/7003/src/objects-inl.h#newcode4360
src/objects-inl.h:4360: ASSERT(other->IsJSObject());
On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> JSObject::cast does the same assert.

Fixed.

http://codereview.chromium.org/7385006/diff/7003/src/objects-inl.h#newcode4373
src/objects-inl.h:4373: ASSERT(other->IsJSObject());
On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> Ditto.

Fixed.

http://codereview.chromium.org/7385006/diff/7003/src/objects.cc
File src/objects.cc (right):

http://codereview.chromium.org/7385006/diff/7003/src/objects.cc#newcode2988
src/objects.cc:2988: // in the prototype chain.  Note that HasLocalProperty()
can cause a GC in
On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> 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.

Fixed.

http://codereview.chromium.org/7385006/diff/7003/src/objects.cc#newcode11772
src/objects.cc:11772: MaybeObject* maybe_hash = key->GetIdentityHash();
On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> 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.

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

http://codereview.chromium.org/7385006/diff/7003/src/objects.h
File src/objects.h (right):

http://codereview.chromium.org/7385006/diff/7003/src/objects.h#newcode1641
src/objects.h:1641: MUST_USE_RESULT MaybeObject* GetHiddenProperties(bool
create_if_needed);
On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> Document what is returned when there are no existing hidden properties and
> create_if_needed is false.

Fixed.

http://codereview.chromium.org/7385006/diff/7003/src/objects.h#newcode2933
src/objects.h:2933: class ObjectDictionary: public
Dictionary<ObjectDictionaryShape, JSObject*> {
On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> Needs a comment.

Fixed.

http://codereview.chromium.org/7385006/diff/7003/src/objects.h#newcode2946
src/objects.h:2946: MUST_USE_RESULT MaybeObject* Add(JSObject* key,
On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> Same here.
> 
> Are PropertyDetails really required? If not, change the entry size in the
shape
> to 2.

In that case the ObjectDictionary should use HashTable instead of Dictionary as
a base class, because those PropertyDetails are the only difference (besides
being enumerable) between them. Right?

http://codereview.chromium.org/7385006/diff/7003/test/cctest/test-dictionary.cc
File test/cctest/test-dictionary.cc (right):

http://codereview.chromium.org/7385006/diff/7003/test/cctest/test-dictionary....
test/cctest/test-dictionary.cc:41: static Handle<ObjectDictionary>
NewObjectDictionary(int at_least_space_for) {
On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> Make this a method on Factory?

Fixed.

http://codereview.chromium.org/7385006/diff/7003/test/cctest/test-dictionary....
test/cctest/test-dictionary.cc:48: TEST(ObjectDictionary) {
On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> Test adding more entries to the dictionary and check the returned values.

Fixed.

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

http://codereview.chromium.org/7385006/diff/7003/src/objects.cc
File src/objects.cc (right):

http://codereview.chromium.org/7385006/diff/7003/src/objects.cc#newcode11772
src/objects.cc:11772: MaybeObject* maybe_hash = key->GetIdentityHash();
On 2011/07/26 22:30:23, Michael Starzinger wrote:
> On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> > 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.
> 
> Fixed (partially, didn't create an enum so far). I suggest turning it into an
> enum in a separate CL.

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

http://codereview.chromium.org/7385006/diff/7003/src/objects.h
File src/objects.h (right):

http://codereview.chromium.org/7385006/diff/7003/src/objects.h#newcode2942
src/objects.h:2942: int FindEntry(Isolate* isolate, JSObject* key);
On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> Doesn't seem to be defined/called. Remove?

Did you miss this one?

http://codereview.chromium.org/7385006/diff/7003/src/objects.h#newcode2946
src/objects.h:2946: MUST_USE_RESULT MaybeObject* Add(JSObject* key,
On 2011/07/26 22:30:23, Michael Starzinger wrote:
> On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> > Same here.
> > 
> > Are PropertyDetails really required? If not, change the entry size in the
> shape
> > to 2.
> 
> In that case the ObjectDictionary should use HashTable instead of Dictionary
as
> a base class, because those PropertyDetails are the only difference (besides
> being enumerable) between them. Right?

Yes, Dictionaries are used for storing properties and elements. Change the base
class. Maybe the name should also be changed to ObjectHashTable.

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

The last set of patches is bigger than expected because of changing the base
class. Also the testcase is more comprehensive. But it should be much cleaner
now. Sorry for the review-overhead, I am still trying to get to know the
codebase. :)

http://codereview.chromium.org/7385006/diff/7003/src/objects.cc
File src/objects.cc (right):

http://codereview.chromium.org/7385006/diff/7003/src/objects.cc#newcode11772
src/objects.cc:11772: MaybeObject* maybe_hash = key->GetIdentityHash();
On 2011/07/27 15:42:26, Vitaly Repeshko wrote:
> On 2011/07/26 22:30:23, Michael Starzinger wrote:
> > On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> > > 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.
> > 
> > Fixed (partially, didn't create an enum so far). I suggest turning it into
an
> > enum in a separate CL.
> 
> Why do you want to add the enum in a separate CL? Seems like a logical part of
> this change to me.

Fixed. Ok. :)

http://codereview.chromium.org/7385006/diff/7003/src/objects.h
File src/objects.h (right):

http://codereview.chromium.org/7385006/diff/7003/src/objects.h#newcode2942
src/objects.h:2942: int FindEntry(Isolate* isolate, JSObject* key);
On 2011/07/27 15:42:26, Vitaly Repeshko wrote:
> On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> > Doesn't seem to be defined/called. Remove?
> 
> Did you miss this one?

Fixed. Yep, missed that one.

http://codereview.chromium.org/7385006/diff/7003/src/objects.h#newcode2946
src/objects.h:2946: MUST_USE_RESULT MaybeObject* Add(JSObject* key,
On 2011/07/27 15:42:26, Vitaly Repeshko wrote:
> On 2011/07/26 22:30:23, Michael Starzinger wrote:
> > On 2011/07/26 13:53:14, Vitaly Repeshko wrote:
> > > Same here.
> > > 
> > > Are PropertyDetails really required? If not, change the entry size in the
> > shape
> > > to 2.
> > 
> > In that case the ObjectDictionary should use HashTable instead of Dictionary
> as
> > a base class, because those PropertyDetails are the only difference (besides
> > being enumerable) between them. Right?
> 
> Yes, Dictionaries are used for storing properties and elements. Change the
base
> class. Maybe the name should also be changed to ObjectHashTable.

Fixed. Required a lot of other changes, but it becomes much cleaner now I think.
:)

[Vitaly Repeshko, 2011-07-28 13:30:07]

LGTM

http://codereview.chromium.org/7385006/diff/15001/src/objects.h
File src/objects.h (right):

http://codereview.chromium.org/7385006/diff/15001/src/objects.h#newcode1646
src/objects.h:1646: // Makes sure to properly call BypassGlobalProxy to be safe
for JSGlobalProxy
I don't think the comments on proxies and fast properties are important. Let's
remove them.

http://codereview.chromium.org/7385006/diff/15001/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/7385006/diff/15001/src/runtime.cc#newcode4521
src/runtime.cc:4521: if (!GetHiddenProperties(jsproto,
JSObject::OMIT_CREATION)->IsUndefined()) {
Maybe we need HasHiddenProperties to simplify this?

[Michael Starzinger, 2011-07-28 17:19:46]

http://codereview.chromium.org/7385006/diff/15001/src/objects.h
File src/objects.h (right):

http://codereview.chromium.org/7385006/diff/15001/src/objects.h#newcode1646
src/objects.h:1646: // Makes sure to properly call BypassGlobalProxy to be safe
for JSGlobalProxy
On 2011/07/28 13:30:07, Vitaly Repeshko wrote:
> I don't think the comments on proxies and fast properties are important. Let's
> remove them.

Fixed.

http://codereview.chromium.org/7385006/diff/15001/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/7385006/diff/15001/src/runtime.cc#newcode4521
src/runtime.cc:4521: if (!GetHiddenProperties(jsproto,
JSObject::OMIT_CREATION)->IsUndefined()) {
On 2011/07/28 13:30:07, Vitaly Repeshko wrote:
> Maybe we need HasHiddenProperties to simplify this?

Fixed