Use a trail instead of a mark bit when processing recursive types in the VM

Use a trail instead of a mark bit when processing recursive types in the VM
(issue 15595).

R=asiva@google.com, rmacnak@google.com

Committed: https://code.google.com/p/dart/source/detail?r=31584

[siva, 2013-12-20 19:35:09]

LGTM with one comment.

https://codereview.chromium.org/109593003/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/109593003/diff/1/runtime/vm/object.cc#newcode...
runtime/vm/object.cc:12538: (*trail)->Add(buddy);
The code in this function seems to imply that a receiver can have
multiple buddies in the trail but AddBuddyToTrail below does not
allow that, it will ASSERT if you try to add a second buddy to a
receiver. This divergence seems confusing.

Maybe you could rename the function AddBuddyToTrail as
AddFirstBuddyToTrail or something like that to indicate we don't
expect to see any buddies for the receiver at that point.

https://codereview.chromium.org/109593003/diff/1/runtime/vm/object.cc#newcode...
runtime/vm/object.cc:12550: if (trail->At(i) == this->raw()) {
Should there be an assert here:
ASSERT(trail->At(i + 1) != Object::null());

https://codereview.chromium.org/109593003/diff/1/runtime/vm/object.h
File runtime/vm/object.h (right):

https://codereview.chromium.org/109593003/diff/1/runtime/vm/object.h#newcode4379
runtime/vm/object.h:4379: // the trail.
Comment does not indicate what happens if the receiver already exists in the
trail (should state that it does not expect a receiver with a buddy in the
trail)

[rmacnak, 2014-01-07 19:38:24]

LGTM

[regis, 2014-01-07 20:26:27]

Thanks!

https://codereview.chromium.org/109593003/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/109593003/diff/1/runtime/vm/object.cc#newcode...
runtime/vm/object.cc:12538: (*trail)->Add(buddy);
On 2013/12/20 19:35:10, siva wrote:
> The code in this function seems to imply that a receiver can have
> multiple buddies in the trail but AddBuddyToTrail below does not
> allow that, it will ASSERT if you try to add a second buddy to a
> receiver. This divergence seems confusing.
> 
> Maybe you could rename the function AddBuddyToTrail as
> AddFirstBuddyToTrail or something like that to indicate we don't
> expect to see any buddies for the receiver at that point.

I renamed the other function AddOnlyBuddyToTrail. This one allows more that one
pair for a given receiver. I updated the comment in the header.

https://codereview.chromium.org/109593003/diff/1/runtime/vm/object.cc#newcode...
runtime/vm/object.cc:12550: if (trail->At(i) == this->raw()) {
On 2013/12/20 19:35:10, siva wrote:
> Should there be an assert here:
> ASSERT(trail->At(i + 1) != Object::null());

Done.

https://codereview.chromium.org/109593003/diff/1/runtime/vm/object.h
File runtime/vm/object.h (right):

https://codereview.chromium.org/109593003/diff/1/runtime/vm/object.h#newcode4379
runtime/vm/object.h:4379: // the trail.
On 2013/12/20 19:35:10, siva wrote:
> Comment does not indicate what happens if the receiver already exists in the
> trail (should state that it does not expect a receiver with a buddy in the
> trail)

I added a comment and renamed the call to AddOnlyBuddyToTrail.

[regis, 2014-01-07 21:55:16]

Committed patchset #2 manually as r31584 (presubmit successful).