1794078 - Make "seen" list of objects in "clone an object" compliant to the WebDriver spec

Status: RESOLVED FIXED

(Remote Protocol :: Marionette, defect, P1)

Description

[Henrik Skupin [:whimboo][⌚️UTC+1]]

Our current implementation is at:

https://searchfox.org/mozilla-central/rev/d416a7b827c2d76b12848e355a4e03dde49ece25/remote/marionette/evaluate.sys.mjs#365-377

Note that we explicitly assert for acyclic and do not try to serialize the object at all. But even if we would remove this line the serialization we will end-up in an infinite recursion.

We should investigate what's wrong with our implementation for JSON.clone

Comment 1

[James Graham [:jgraham]]

It's not obvious to me that this is wrong.

In the spec we structure this as checking for circular references when serializing, and aborting if we find one. In the implementation we structure this as an upfront check for circular references, and a serializer which doesn't consider cycles at all. Intuitively those should be equivalent, as long as we are using the same properties for the circular reference check as we would when serializing (e.g. if a.foo = a, but foo wouldn't be reached by the serializer, but will by the cycle check, that's a bug).

Comment 2

[Henrik Skupin [:whimboo][⌚️UTC+1]]

Ok, so lets get into the details...

JSON close is called as following:

To perform a JSON clone return the result of calling the internal JSON clone algorithm with arguments value and an empty List. 

Here we have a value, which is the to serializable objectand an empty list forseen` elements. This is already the point where we have the bug because we pass in the list of known elements from the element cache.

Later under Otherwise there is the following in the first step:

        1. If value is in seen, return error with error code javascript error.

        2. Append value to seen.

        3. Let result be the value of running the clone an object algorithm with arguments value and seen, and the internal JSON clone algorithm as the clone algorithm.

        4. Remove the last element of seen.

        5. Return result. 

We should only raise a javascript error exception if the value has been seen and not all the time because the object has circular references. Also we never append value to the seen list and as such also wouldn't be able to recognize if we already have serialized the value or not. The only thing that we pass around is the list of seen web element references, and that is basically wrong.

So I'm fairly sure that with a fix for this we should be able to correctly handle objects with circular references.

Adding to the webdriver triage list so that we can discuss this today.

Comment 3

[James Graham [:jgraham]]

Can you give a concrete example of something that you think would serialize according to the spec but not in our implementation? I don't mind if you want to change the implementation to look more like the spec, but I'm still not understanding what specific case you think is currently wrong.

Comment 4

[Henrik Skupin [:whimboo][⌚️UTC+1]]

Any arbitrary object is currently affected that is not covered by the other cases above and which has cyclic references. As said we do not store already seen objects at all at the moment.

Comment 5

[James Graham [:jgraham]]

From matrix:

The classic spec just doesn't allow serializing cycles at all. It's not a "bug" as such; it's by design. That's because it tries to represent JS objects directly as JSON objects. That's great in simple cases, but it does have some limitations:

• No DOM types. For Element and Window we invent an "unlikely" looking JSON object to represent the remote value, but it's totally a hack.
• No references. This means we can't say that e.g. a = [1,2,3]; {prop1: a, prop2: a} has two copies of the same array; we just get it serialized as {"prop1": [1,2,3], "prop2": [1,2,3]}. That also means no cycles: if we have a = {}; a.prop = a then {prop1: a} is impossible to represent because we can't say that obj.prop1.prop === obj.prop1. We could just cut the serialization at that point or something, but we don't: if we try to serialize such an object we just return a Javascript Error on the reasonable-ish basis that in normal testing use cases returning a JS object containing cycles is rare. Of course the DOM has cycles on pretty much everything since it's a tree with parent pointers, but a generic object representation of DOM nodes isn't that useful anyway.

In the spec the way we handle cycle detection is via a one-pass algorithm. Basically as we're serializing objects we put each source object into a set and as we recurse the object graph, if we come across an object we've seen before we abort serialization and return an error.

In the marionette implemenation we use a two-pass approach; first we traverse the object graph looking for objects we've seen before (this is isCyclic in the code). If we find one we return an error without doing any serialization. Once we've passed that check we go on to serialize assuming there aren't cycles (seenElms in the toJSON implementation seems to be about handling Elements, not cycles).

In theory both approaches are equivalent. In practice there are some tradeoffs: doing an upfront check for cycles avoids the overhead of partial serialization if we find a cycle, but is slower in the case where there aren't cycles. It also requires that we visit the exact same properties on the two passes; if you can construct a case where we miss a property containing a cycle in the validation pass that we'll later use in the serialization it will lead to a hang.

So I think it might make sense to update the marionette code to look more like the spec. But absent a case where we get a hang in the code (or similarly fail to abort given a cyclic input to the spec algorithm), I don't think there's a bug, just different engineering tradeoffs.

Comment 6

[Henrik Skupin [:whimboo][⌚️UTC+1]]

As discussed with James it's basically any other DOM node beside Element that should cause a cyclic value error. Windows are hereby handled differently.

Given that bug 1692468 introduces quite a good amount of changes lets wait with any work until this bug is done. Basically what's left to do here is the correct handling of seen which is not spec compliant. Maybe I might already fix it with bug 1692468.

Comment 7

[Julian Descottes [:jdescottes]]

Henrik, can you add some details about what needs to be changed here? Or do we just wait for bug 1692468 before considering this again?

Comment 8

[Henrik Skupin [:whimboo][⌚️UTC+1]]

We need the changes from bug 1692468 first due to the amount of changes. What needs to be done in a nutshell:

1. Access the elementReferenceStore directly from the appropriate places and do not pass a reference through fromJSON/toJSON calls
2. Use seenEls for already seen objects for a call to fromJSON/toJSON
3. Try to get rid of the two-pass approach

Comment 9

[Henrik Skupin [:whimboo][⌚️UTC+1]]

Attachment: Bug 1794078 - [marionette] Refactor evaluate's "fromJSON" and "toJSON" methods.

Comment 10

[Henrik Skupin [:whimboo][⌚️UTC+1]]

Attachment: Bug 1794078 - [wdspec] Enhance JSON serialization and deserialization tests for script execution.

Comment 11

[Henrik Skupin [:whimboo][⌚️UTC+1]]

Attachment: Bug 1794078 - [marionette] Refactor evaluate's "fromJSON" and "toJSON" methods.

Depends on D166032

Comment 12

[Henrik Skupin [:whimboo][⌚️UTC+1]]

Attachment: Bug 1794078 - [marionette] Make "seen" list of objects in "clone an object" compliant to the WebDriver spec.

Depends on D166033

Comment 13

[Henrik Skupin [:whimboo][⌚️UTC+1]]

See also https://github.com/w3c/webdriver/pull/1709 for the changes of the WebDriver classic specification.

Comment 14

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/319ebaa96be1
[wdspec] Enhance JSON serialization and deserialization tests for script execution. r=webdriver-reviewers,jdescottes
https://hg.mozilla.org/integration/autoland/rev/0cf075766291
[marionette] Refactor evaluate's "fromJSON" and "toJSON" methods. r=jdescottes,webdriver-reviewers
https://hg.mozilla.org/integration/autoland/rev/4e0fc592643f
[marionette] Make "seen" list of objects in "clone an object" compliant to the WebDriver spec. r=webdriver-reviewers,jgraham,jdescottes

Comment 15

[Web Platform Test Sync Bot (Matrix: #interop:mozilla.org)]

Created web-platform-tests PR https://github.com/web-platform-tests/wpt/pull/37779 for changes under testing/web-platform/tests

Comment 16

[Sandor Molnar]

https://hg.mozilla.org/mozilla-central/rev/319ebaa96be1
https://hg.mozilla.org/mozilla-central/rev/0cf075766291
https://hg.mozilla.org/mozilla-central/rev/4e0fc592643f

Comment 17

[Web Platform Test Sync Bot (Matrix: #interop:mozilla.org)]

Upstream PR merged by moz-wptsync-bot