708794 - JS tests should not depend on enumeration order

Status: RESOLVED INCOMPLETE

(Core :: JavaScript Engine, defect)

Description

[Christian Holler (:decoder)]

The patch in bug 707017 changes the enumeration order to be always sorted with a special compile flag (used for fuzzing). This change caused the following tests to fail:

e4x/extensions/json-stringify-dropping-xml-elements.js
ecma_5/JSON/stringify.js
ecma_5/JSON/stringify-dropping-elements.js
ecma_5/JSON/stringify-ignore-noncallable-toJSON.js
ecma_5/JSON/stringify-replacer.js
ecma_5/Object/15.2.3.7-01.js
ecma_5/Object/15.2.3.14-01.js
js1_5/extensions/regress-381304.js
js1_5/Regress/regress-465013.js


It seems like those tests have a certain enumeration order hardcoded from what I can see.

Comment 1

[Jesse Ruderman]

I bet you'll find additional broken tests if you do another run with the reverse sort ;)

Comment 2

[Brian Hackett [Laid off!]]

I don't understand the desire to keep tests from depending on a specific enumeration order.  ECMA doesn't specify one, but in certain cases the web requires one, and if we don't have tests that the de facto enumeration order is preserved then we can break websites without triggering test failures.

Comment 3

[Jeff Walden [:Waldo]]

Different browsers already implement different enumeration orders.  The order we implement for plain old objects is quite different from the one v8 implements.  They're well aware of the differences and have no plans to fix them.  The order we implement for dense arrays was a change from the order implemented for them prior to shavarrays.  We were aware of this difference and had, and have, no plans to fix it.  And even in the subset of cases when ordering is in agreement, there are still occasional deviations like the one you yourself introduced.  There has been and will be inconsistency, and I think the existing inconsistencies and the general lack of bug reports on them indicate that websites depend much less on enumeration order than might be believed.

Comment 4

[Luke Wagner [:luke]]

I wonder if we can do experiments to determine if we can break our traditional enumeration order.  At least in the case of dictionary objects, that would shave off two words per property in the owned shape...

Comment 5

[Jesse Ruderman]

Two words per property? I don't care how many web sites break. Ship it.

Comment 6

[Nicholas Nethercote [inactive]]

(In reply to Luke Wagner [:luke] from comment #4)
> I wonder if we can do experiments to determine if we can break our
> traditional enumeration order.  At least in the case of dictionary objects,
> that would shave off two words per property in the owned shape...

Can you explain more?

Comment 7

[Luke Wagner [:luke]]

(In reply to Nicholas Nethercote [:njn] from comment #6)
If we don't need to preserve order then we don't need to maintain the doubly-linked list (hence, two words per shape) of dictionary shapes.  So how would we enumerate shapes?  The order of entries in the hash table would be bad since it would change when we rehash which adds content-visible non-determinism.  Instead, we could store the shapes contiguously (many options of how: in a malloc()'d array pointed to be lastProperty; interleaved with slot values; to the "left" of the slots array; etc) and use their linear ordering.  Furthermore, this contiguous storage could remove the need for storing the slot number so, with some more work (killing tinyids, moving nfixed, hoisting attrs to BaseShape, obviating remaining flags) that would leave only two words (id and BaseShape*) per dictionary shape.

I was excited by this so I looked at about:memory over the weekend on a trunk build (and was delighted to see that there is already a dict/tree distinction, although it would be nice to have dict/shape summed up individually in "Other Measurements").  It seems that tree shape memory usage dominates dictionary memory usage, so I don't see this winning big on most of what I looked at.

Comment 8

[Terrence Cole [:terrence]]

Additional tests that fail in jit-tests:

basic/bug703157.js
basic/testCrossCompartmentTransparency2.js
sunspider/check-string-fasta.js

Comment 9

[daletron]

Attachment: Attempt to fix "json-stringify-dropping-xml-elements.js"

Hi, would like opinions on my code.  Passes both tests, enumerated and non-enumerated.

Comment 10

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Comment on attachment 627854 [details] [diff] [review]
Attempt to fix "json-stringify-dropping-xml-elements.js"

daletron, thanks for this patch!

Luke, is it ok for you to take an initial look at this?

Comment 11

[Christian Holler (:decoder)]

Comment on attachment 627854 [details] [diff] [review]
Attempt to fix "json-stringify-dropping-xml-elements.js"

I think your idea is right (trying to split up the strings to order the stuff before comparing) and better than just relying on JSON.parse again.

However, you could probably come up with a more generic function that can test these examples, maybe "assertEqStringifiedJSON" or something like that. For simplicity, you could assume that the elements in the JSON are all simple elements (no nested objects/arrays), just as it is in this test. Then just cut off the first and the last character of the given string (which could be {} or [] of course), then split by ", " (including whitespace), sort the result, toString it and call assertEq.

It'll do the same as your code, but use up less space. If you need this in other tests too, we can even move it up to one of the test shells. 

Note that this method will of course not work if you have nested objects/arrays.

Comment 12

[Luke Wagner [:luke]]

Comment on attachment 627854 [details] [diff] [review]
Attempt to fix "json-stringify-dropping-xml-elements.js"

forwarding JSON test review to Waldo

Comment 13

[daletron]

Attachment: Attempt to fix "json-stringify-dropping-xml-elements.js", but modified with Christian's suggestions

Fixed my patch per Christian Holler's comments.  I knew my patch was messy -.-  Let me know what you guys think now.

Comment 14

[daletron]

^ Luke, if you could forward this patch instead that would be great

Comment 15

[Luke Wagner [:luke]]

Comment on attachment 629042 [details] [diff] [review]
Attempt to fix "json-stringify-dropping-xml-elements.js", but modified with Christian's suggestions

You bet.

Comment 16

[Jeff Walden [:Waldo]]

Comment on attachment 627854 [details] [diff] [review]
Attempt to fix "json-stringify-dropping-xml-elements.js"

Review of attachment 627854 [details] [diff] [review]:
-----------------------------------------------------------------

Sorry for the delay, I'm kind of busy with other, fairly pressing work to be done.  :-\

::: js/src/tests/e4x/extensions/json-stringify-dropping-xml-elements.js
@@ -5,3 @@
>  
> -assertEq(JSON.stringify([123, <x><y></y></x>, 456]),
> -         '[123,null,456]');

Property enumeration order for arrays is well-defined for JSON stuff, so there's no need to gunk up that case -- leave it as-is.

@@ +11,5 @@
> +
> +temp = '{' + temp.toString() + '}';
> +temp2 = '{' + temp2.toString() + '}';
> +
> +assertEq(temp2, temp);

So we

1. Remove the {} at the ends of each.
2. Split on "," to get [charsForFirstProp, charsForSecondProp] for each.
3. Compare "{" + arr + "}" for the first and for the second for equality.

A bit complicated, but perhaps not horrible.

Still, it seems like this particular case could be done more simply given that the expected output will only have two properties.  Why not just assert that the result is either '{"foo":123,"baz":123}' or '{"baz":123,"foo":123}'.  Less general to be sure, but a bit more readable.

Comment 17

[Jeff Walden [:Waldo]]

Comment on attachment 629042 [details] [diff] [review]
Attempt to fix "json-stringify-dropping-xml-elements.js", but modified with Christian's suggestions

Review of attachment 629042 [details] [diff] [review]:
-----------------------------------------------------------------

I tend to think the suggestion I made on the other patch is preferable to a fully general solution as far as readability goes.  And I think we can usually write tests that are simpler to avoid the need for more-general comparisons here, too -- like only having two properties in the serialized output, or even having only one, or whatever.

Comment 18

[Timea Cernea [:tbabos][inactive]]

Hey Jeff,
Is this issue still relevant now or it can be closed?

Comment 19

[Timea Cernea [:tbabos][inactive]]

Closing this as resolved:incomplete, if this issue is still reproducible please re-open it and update the flags for the affected versions. Thanks.