If you think a bug might affect users in the 57 release, please set the correct tracking and status flags for Release Management.

JS tests should not depend on enumeration order

NEW
Unassigned

Status

()

Core
JavaScript Engine
--
critical
6 years ago
3 years ago

People

(Reporter: decoder, Unassigned)

Tracking

Trunk
x86_64
Linux
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments)

(Reporter)

Description

6 years ago
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

6 years ago
I bet you'll find additional broken tests if you do another run with the reverse sort ;)
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.
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

6 years ago
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

6 years ago
Two words per property? I don't care how many web sites break. Ship it.
(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

6 years ago
(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.
Additional tests that fail in jit-tests:

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

Comment 9

5 years ago
Created attachment 627854 [details] [diff] [review]
Attempt to fix "json-stringify-dropping-xml-elements.js"

Hi, would like opinions on my code.  Passes both tests, enumerated and non-enumerated.
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?
Attachment #627854 - Flags: review?(luke)
(Reporter)

Comment 11

5 years ago
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

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

forwarding JSON test review to Waldo
Attachment #627854 - Flags: review?(luke) → review?(jwalden+bmo)

Comment 13

5 years ago
Created attachment 629042 [details] [diff] [review]
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

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

Comment 15

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

You bet.
Attachment #629042 - Flags: review?(jwalden+bmo)
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.
Attachment #627854 - Flags: review?(jwalden+bmo)
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.
Attachment #629042 - Flags: review?(jwalden+bmo)
(Assignee)

Updated

3 years ago
Assignee: general → nobody
You need to log in before you can comment on or make changes to this bug.