Finding cycles in an object

[Gonzalo Diethelm]

I run the following JS code in the Chrome console:

// Version 67.0.3396.87 (Official Build) (64-bit)

var x = [1, 2, {"foo": 11}];
x[2].bar = x;

Now from C++ code, I get ahold of x as a Local<Object>, and wish to traverse the whole structure; for the sake of the example, let's say I am converting it into serialized data (I know I can use JSON.stringify() to do this, serializing is just an example to clarify ideas).  My question is, how can I keep track of the nodes in the structure  that I have already seen, and their associated serialized value, so that I can avoid an infinite traversal?

It seems to me doing this would require a way to get a unique identity for each node, so that the C++ code can do something similar to this:

typedef map<NodeId, NodeData> NodeMap;
NodeMap seen;
...
Local<Object> node = current.GetNextChild();
NodeId id = node.GetUniqueId();
NodeMap::iterator k = seen.find(id);
NodeData data;
if (k != seen.end()) {
    // node already seen, reuse its serialization
    data = k->first;
} else {
    // first time we see node, serialize and remember
    data = node.Serialize(); // recurses
    seen[id] = data;
}

The specific question is: what type could be NodeId, and how do I get the equivalent of GetUniqueId()?

I am very tempted to ask for a way to get a raw void* to each node, but I guess any way of doing this is fine, as long as I can get a unique id that is stable while I'm traversing the data.  For these reasons, GetIdentityHash() does not seem to fit the bill: "The return value will never be 0. Also, it is not guaranteed to be unique."

Incidentally, If I try to use JSON.stringify for my data, I get this:

JSON.stringify(x)
VM170:1 Uncaught TypeError: Converting circular structure to JSON
    at JSON.stringify (<anonymous>)
    at <anonymous>:1:6

This is taken care of here in the V8 code:

JsonStringifier::Result JsonStringifier::StackPush(Handle<Object> object) {
...
    // member stack_ is: Handle<JSArray> stack_;
    int length = Smi::ToInt(stack_->length());
    FixedArray* elements = FixedArray::cast(stack_->elements());
    for (int i = 0; i < length; i++) {
        FixedArray* elements = FixedArray::cast(stack_->elements());
        if (elements->get(i) == *object) {
            // boom
        }
    }
}

So, operator*() in a Handle<Object> gives me a unique id? Which is the type for this? Can I store that in a C++ map? Is it stable (enough)?

Thanks!

[Zac Hansen]

unary * on a local<T> gives a T*:  https://v8.paulfryzel.com/docs/master/classv8_1_1_local.html#a3c96c0bc5db1288bad5769e8e54e26da

[Gonzalo Diethelm]

Thanks, that is useful (not sure why it is unary * instead of unary &, but meh).

Do you know if there is any way to then go from the T* back into the Local<T>? Something like:

Handle<Object> object = Object::New(isolate);
Local<Object> ret = Local<Object>::Cast(object);
Object* ptr = *object; // this works, according to your comment
...
ret = Local<Object>::Cast(ptr); // this doesn't work

Cheers!

[Gonzalo Diethelm]

Never mind my last question, it didn't really make much sense.

So, I have found some basic behaviour related to this, which really surprised me:

Local<Object> parent;  // this will be a JS object
Local<Value>  slot;    // this will be a new slot in parent
Local<Object> object = // this will be the value we want to put in that slot => another object

// store object in parent
Local<Value> value = Local<Value>::Cast(object);
parent->Set(slot, value);

// remember its pointer and hash
int h0 = object->GetIdentityHash();
Value* p0 = *value;

// retrieve it back
Local<Value> check_value = parent->Get(slot);
Local<Object> check_object = Local<Object>::Cast(check_value);

// remember its pointer and hash
int h1 = check_object->GetIdentityHash();
Value* p1 = *check_value;

My surprise is that p0 and p1 are not the same, although h0 and h1 are the same. So, the object I store in that slot is actually not identical to what I retrieve back from the slot.

Is there any way to store that object so that what you get back is actually the same pointer?

I'm pretty sure this must be possible, because when you do this in the Chrome console, JSON does detect the cyclic reference.

Cheers!

[Gonzalo Diethelm]

Note to self: this might be related to Local<Object> vs Global<Object> (or Persistent<Object>? so many names...)

Need to look into that.

[Zac Hansen]

You're dereferencing a "super pointer" to get to a "pointer", hence * not &.   You can't "go back" because the local/global<T> represents an "reference count" to the object which must be known to the JS runtime.   

As for p0 and p1, have you tried setting slot to a fixed string value before using it as a key for storing/lookup?   I don't know what the expected behavior of using an empty value as a key into an object is.

These are all just guesses - if someone else answers differently, I'm probably wrong.

[Gonzalo Diethelm]

Sure, slot does have a value, I just didn't include it in the code. Something like:

Local<Value> slot = String::NewFromUtf8(isolate, "MyBeautifulSlot", NewStringType::kNormal).ToLocalChecked();

Cheers!

[Jakob Kummerow]

The Local class defines an operator == that should do exactly what you need.

--
--
v8-users mailing list
v8-u...@googlegroups.com
http://groups.google.com/group/v8-users
---
You received this message because you are subscribed to the Google Groups "v8-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to v8-users+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Gonzalo Diethelm]

Jakob, you rule. That in fact fixed all my problems. Thanks to you and Zac for all the guidance!