Indeterministic result ordering for some selectors

[tobyink]

Migrated from rt.cpan.org #130488 (status was 'open')

Requestors:

• christoph.burgmer@gmail.com

From christoph.burgmer@gmail.com on 2019-09-10 21:38:27
:

For the given selectors and documents I can reproduce differently ordered results on re-runs:

Exhibit A

Selector: $[*]
Document:
{
"some": "string",
"int": 42,
"object": {
"key": "value"
},
"array": [0, 1]
}

Outcome #1:
[
42,
[
0,
1
],
"string",
{
"key": "value"
}
]

Outcome #2:
[
{
"key": "value"
},
42,
[
0,
1
],
"string"
]

Exhibit B

Selector: $.store..price
Document:
See https://cburgmer.github.io/json-path-comparison/results/recursive_on_nested_object.html

Outcome #1:
[
19.95,
8.95,
12.99,
8.99,
22.99
]

Outcome #2:
[
8.95,
12.99,
8.99,
22.99,
19.95
]

Expected:

Deterministic ordering to reduce flakiness in output.

Rationale:

This is a blocker for this implementation to be added to the comparison of aforementioned project, see cburgmer/json-path-comparison#4 .

I believe the nondeterminism comes from Perl's hashes not guaranteeing order. It's debatable however whether JSONPath should even guarantee order, see e.g. cburgmer/json-path-comparison#3 .
I'm happy to find other means for now to introduce a deterministic response but am limited by my knowledge of Perl. Happy for pointers. Looked at Tie::IxHash but can't figure out how to bring it in after JSON decoding.

[tobyink]

From popefelix@gmail.com on 2019-09-10 22:10:54
:

You are correct - the nondeterminism does come from Perl's hashes not
guaranteeing order.

How do other JSONPath implementations handle this? Is there a spec that
dictates this?

On Tue, Sep 10, 2019 at 4:38 PM Christoph Burgmer via RT <
bug-JSON-Path@rt.cpan.org> wrote:

Tue Sep 10 17:38:27 2019: Request 130488 was acted upon.
Transaction: Ticket created by christoph.burgmer@gmail.com
Queue: JSON-Path
Subject: Indeterministic result ordering for some selectors
Broken in: 0.420
Severity: Normal
Owner: popefelix
Requestors: christoph.burgmer@gmail.com
Status: new
Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=130488 >

For the given selectors and documents I can reproduce differently ordered
results on re-runs:

Exhibit A

Selector: $[*]
Document:
{
"some": "string",
"int": 42,
"object": {
"key": "value"
},
"array": [0, 1]
}

Outcome #1:
[
42,
[
0,
1
],
"string",
{
"key": "value"
}
]

Outcome #2:
[
{
"key": "value"
},
42,
[
0,
1
],
"string"
]

Exhibit B

Selector: $.store..price
Document:
See
https://cburgmer.github.io/json-path-comparison/results/recursive_on_nested_object.html

Outcome #1:
[
19.95,
8.95,
12.99,
8.99,
22.99
]

Outcome #2:
[
8.95,
12.99,
8.99,
22.99,
19.95
]

Expected:

Deterministic ordering to reduce flakiness in output.

Rationale:

This is a blocker for this implementation to be added to the comparison of
aforementioned project, see
cburgmer/json-path-comparison#4 .

I believe the nondeterminism comes from Perl's hashes not guaranteeing
order. It's debatable however whether JSONPath should even guarantee order,
see e.g. cburgmer/json-path-comparison#3 .
I'm happy to find other means for now to introduce a deterministic
response but am limited by my knowledge of Perl. Happy for pointers. Looked
at Tie::IxHash but can't figure out how to bring it in after JSON decoding.

--
Kit Peters, W0KEH
GPG public key fingerpint: D4FF AA62 AFEA 83D6 CC98 ACE5 6FAE 7E74 7F56 ED1D
Hello to any and all NSA, DEA, or other government or non-government agents
reading this email. Tell me about your life; I'll tell you about mine.

[tobyink]

From christoph.burgmer@gmail.com on 2019-09-11 07:08:25
:

With all the other implementations I've tried (Java, PHP, Python, Ruby, ...) they at least provide a stable response (possibly due to the underlying guarantees of the language).
Compare e.g. row "Wildcard dot notation on array" in the table under https://cburgmer.github.io/json-path-comparison/.

The JSONPath "spec" doesn't seem to say anything about this, whereas for the actual JSON spec I've read conflicting interpretations - many discussions claim that order is not guaranteed, but I have to yet find this in any spec.

What I've done with Python when I wanted to maintain order is use an OrderedDict: https://github.com/cburgmer/json-path-comparison/blob/master/src/oneliner_json.py

[tobyink]

From popefelix@gmail.com on 2019-09-11 14:14:56
:

So the JSON spec says that objects are unordered. In your Exhibit A, you're
passing in an object, so there's no guarantee of how things will be ordered
coming out. Exhibit B is similar - you'll note that 19.95 is either the
first or the last element in the list, but never in the middle.

I'd be willing to work on a "canonical" flag similar to the flag used by
Storable (https://metacpan.org/pod/Storable#CANONICAL-REPRESENTATION).
Would that be sufficient?

On Wed, Sep 11, 2019 at 2:08 AM Christoph Burgmer via RT <
bug-JSON-Path@rt.cpan.org> wrote:

   Queue: JSON-Path

Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=130488 >

With all the other implementations I've tried (Java, PHP, Python, Ruby,
...) they at least provide a stable response (possibly due to the
underlying guarantees of the language).
Compare e.g. row "Wildcard dot notation on array" in the table under
https://cburgmer.github.io/json-path-comparison/.

The JSONPath "spec" doesn't seem to say anything about this, whereas for
the actual JSON spec I've read conflicting interpretations - many
discussions claim that order is not guaranteed, but I have to yet find this
in any spec.

What I've done with Python when I wanted to maintain order is use an
OrderedDict:
https://github.com/cburgmer/json-path-comparison/blob/master/src/oneliner_json.py

--
Kit Peters, W0KEH
GPG public key fingerpint: D4FF AA62 AFEA 83D6 CC98 ACE5 6FAE 7E74 7F56 ED1D
Hello to any and all NSA, DEA, or other government or non-government agents
reading this email. Tell me about your life; I'll tell you about mine.

[tobyink]

From christoph.burgmer@gmail.com on 2019-09-12 15:24:55
:

I needed some time to think on this.

What's currently making the outcome hard to compare is that a query like
$[*] on an object doesn't yield a stable representation. If there is a,
say, simple way of achieving that, it would help, yes.
The ordering has to already be preserved when parsing the JSON document
though (see
https://github.com/cburgmer/json-path-comparison/blob/Perl_JSON-Path/implementations/Perl_JSON-Path/main.pl#L9),
as this already introduces indeterminism in Perl I believe (as
decode_json returns
a hash I believe). Python for example does allow that.

Kit, my goal with the comparison project is to seek clarification on what
"good" JSONPath is (including I guess when a certain order can be
guaranteed), but I'm trying to keep my on personal opinion out of it, hence
the whole approach of comparing via consensus.

[tobyink]

From christoph.burgmer@gmail.com on 2019-09-12 15:38:36
:

Just for reference, I've tried looking for a source on the much quoted JSON
standard as it came up in other discussions as well, and so far only found

The JSON syntax does not impose any restrictions on the strings used as
names, does not require that name strings be unique, and does not
assign any significance to the ordering of name/value pairs. These are
all semantic considerations that may be defined by JSON processors or in
specifications defining specific uses of JSON for data interchange.

I've mentioned this in
cburgmer/json-path-comparison#3 where I'd try to
focus the general discussion on ordering for JSONPath, but wanted to call
this out here once.

Am Do., 12. Sept. 2019 um 17:24 Uhr schrieb Christoph Burgmer <
christoph.burgmer@gmail.com>:

I needed some time to think on this.

What's currently making the outcome hard to compare is that a query like
$[*] on an object doesn't yield a stable representation. If there is a,
say, simple way of achieving that, it would help, yes.
The ordering has to already be preserved when parsing the JSON document
though (see
https://github.com/cburgmer/json-path-comparison/blob/Perl_JSON-Path/implementations/Perl_JSON-Path/main.pl#L9),
as this already introduces indeterminism in Perl I believe (as decode_json
returns a hash I believe). Python for example does allow that.

Kit, my goal with the comparison project is to seek clarification on what
"good" JSONPath is (including I guess when a certain order can be
guaranteed), but I'm trying to keep my on personal opinion out of it, hence
the whole approach of comparing via consensus.

[tobyink]

From popefelix@gmail.com on 2019-09-12 16:01:13
:

"Just for reference, I've tried looking for a source on the much quoted JSON
standard"

Ah, that's an easy one! :)

RFC 7159 (http://www.rfc-editor.org/rfc/rfc7159.txt) states "An object is
an unordered collection of zero or more name/value pairs" (emphasis mine)

On Thu, Sep 12, 2019, 10:38 Christoph Burgmer via RT <
bug-JSON-Path@rt.cpan.org> wrote:

   Queue: JSON-Path

Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=130488 >

Just for reference, I've tried looking for a source on the much quoted JSON
standard as it came up in other discussions as well, and so far only found

The JSON syntax does not impose any restrictions on the strings used as
names, does not require that name strings be unique, and does not
assign any significance to the ordering of name/value pairs. These are
all semantic considerations that may be defined by JSON processors or in
specifications defining specific uses of JSON for data interchange.

I've mentioned this in
cburgmer/json-path-comparison#3 where I'd try to
focus the general discussion on ordering for JSONPath, but wanted to call
this out here once.

Am Do., 12. Sept. 2019 um 17:24 Uhr schrieb Christoph Burgmer <
christoph.burgmer@gmail.com>:

I needed some time to think on this.

What's currently making the outcome hard to compare is that a query like
$[*] on an object doesn't yield a stable representation. If there is a,
say, simple way of achieving that, it would help, yes.
The ordering has to already be preserved when parsing the JSON document
though (see

https://github.com/cburgmer/json-path-comparison/blob/Perl_JSON-Path/implementations/Perl_JSON-Path/main.pl#L9
),

as this already introduces indeterminism in Perl I believe (as
decode_json
returns a hash I believe). Python for example does allow that.

Kit, my goal with the comparison project is to seek clarification on what
"good" JSONPath is (including I guess when a certain order can be
guaranteed), but I'm trying to keep my on personal opinion out of it,
hence
the whole approach of comparing via consensus.

[tobyink]

From popefelix@gmail.com on 2019-09-12 16:54:15
:

Sorry - I quoted an obsolete RFC. The correct one is RFC8259 (
https://datatracker.ietf.org/doc/rfc8259/?include_text=1), which again
defines an object to be "an unordered collection of zero or more name/value
pairs".

To your question above of what constitutes "good" JSONPath, I would say
that good JSONPath produces results that a reasonable person would expect
having read Goessner's definition and RFC 8159. Thus, to put the question
in the context of this issue, if a JSONPath implementation imposes an order
on the keys of an object, that implementation is out of compliance with the
spec, consensus or no.

On Thu, Sep 12, 2019 at 11:00 AM Kit Peters popefelix@gmail.com wrote:

"Just for reference, I've tried looking for a source on the much quoted
JSON
standard"

Ah, that's an easy one! :)

RFC 7159 (http://www.rfc-editor.org/rfc/rfc7159.txt) states "An object is
an unordered collection of zero or more name/value pairs" (emphasis
mine)

On Thu, Sep 12, 2019, 10:38 Christoph Burgmer via RT <
bug-JSON-Path@rt.cpan.org> wrote:

   Queue: JSON-Path

Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=130488 >

Just for reference, I've tried looking for a source on the much quoted
JSON
standard as it came up in other discussions as well, and so far only found

The JSON syntax does not impose any restrictions on the strings used as
names, does not require that name strings be unique, and does
not
assign any significance to the ordering of name/value pairs. These are
all semantic considerations that may be defined by JSON processors or in
specifications defining specific uses of JSON for data interchange.

I've mentioned this in
cburgmer/json-path-comparison#3 where I'd try
to
focus the general discussion on ordering for JSONPath, but wanted to call
this out here once.

Am Do., 12. Sept. 2019 um 17:24 Uhr schrieb Christoph Burgmer <
christoph.burgmer@gmail.com>:

I needed some time to think on this.

What's currently making the outcome hard to compare is that a query like
$[*] on an object doesn't yield a stable representation. If there is
a,
say, simple way of achieving that, it would help, yes.
The ordering has to already be preserved when parsing the JSON document
though (see

https://github.com/cburgmer/json-path-comparison/blob/Perl_JSON-Path/implementations/Perl_JSON-Path/main.pl#L9
),

as this already introduces indeterminism in Perl I believe (as
decode_json
returns a hash I believe). Python for example does allow that.

Kit, my goal with the comparison project is to seek clarification on
what
"good" JSONPath is (including I guess when a certain order can be
guaranteed), but I'm trying to keep my on personal opinion out of it,
hence
the whole approach of comparing via consensus.

--
Kit Peters, W0KEH
GPG public key fingerpint: D4FF AA62 AFEA 83D6 CC98 ACE5 6FAE 7E74 7F56 ED1D
Hello to any and all NSA, DEA, or other government or non-government agents
reading this email. Tell me about your life; I'll tell you about mine.

[tobyink]

From christoph.burgmer@gmail.com on 2019-09-12 18:52:46
:

Fair point, but let's also call out

JSON parsing libraries have been observed to differ as to whether or
not they make the ordering of object members visible to calling
software. Implementations whose behavior does not depend on member
ordering will be interoperable in the sense that they will not be
affected by these differences.

It seems some people have seen the need to somewhat pass on the order.

Anyhow, let me know what you think is reasonable for your library. Feel
free to give the json-path-comparison project a run, it's meant to help,
not enforce :)

Am Do., 12. Sept. 2019 um 18:54 Uhr schrieb Kit Peters via RT <
bug-JSON-Path@rt.cpan.org>:

<URL: https://rt.cpan.org/Ticket/Display.html?id=130488 >

Sorry - I quoted an obsolete RFC. The correct one is RFC8259 (
https://datatracker.ietf.org/doc/rfc8259/?include_text=1), which again
defines an object to be "an unordered collection of zero or more name/value
pairs".

To your question above of what constitutes "good" JSONPath, I would say
that good JSONPath produces results that a reasonable person would expect
having read Goessner's definition and RFC 8159. Thus, to put the question
in the context of this issue, if a JSONPath implementation imposes an order
on the keys of an object, that implementation is out of compliance with the
spec, consensus or no.

On Thu, Sep 12, 2019 at 11:00 AM Kit Peters popefelix@gmail.com wrote:

"Just for reference, I've tried looking for a source on the much quoted
JSON
standard"

Ah, that's an easy one! :)

RFC 7159 (http://www.rfc-editor.org/rfc/rfc7159.txt) states "An object
is
an unordered collection of zero or more name/value pairs" (emphasis
mine)

On Thu, Sep 12, 2019, 10:38 Christoph Burgmer via RT <
bug-JSON-Path@rt.cpan.org> wrote:

   Queue: JSON-Path

Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=130488 >

Just for reference, I've tried looking for a source on the much quoted
JSON
standard as it came up in other discussions as well, and so far only
found

The JSON syntax does not impose any restrictions on the strings used
as
names, does not require that name strings be unique, and does
not
assign any significance to the ordering of name/value pairs. These are
all semantic considerations that may be defined by JSON processors or in
specifications defining specific uses of JSON for data interchange.

I've mentioned this in
cburgmer/json-path-comparison#3 where I'd try
to
focus the general discussion on ordering for JSONPath, but wanted to
call
this out here once.

Am Do., 12. Sept. 2019 um 17:24 Uhr schrieb Christoph Burgmer <
christoph.burgmer@gmail.com>:

I needed some time to think on this.

What's currently making the outcome hard to compare is that a query
like
$[*] on an object doesn't yield a stable representation. If there is
a,
say, simple way of achieving that, it would help, yes.
The ordering has to already be preserved when parsing the JSON
document
though (see

https://github.com/cburgmer/json-path-comparison/blob/Perl_JSON-Path/implementations/Perl_JSON-Path/main.pl#L9

),

as this already introduces indeterminism in Perl I believe (as
decode_json
returns a hash I believe). Python for example does allow that.

Kit, my goal with the comparison project is to seek clarification on
what
"good" JSONPath is (including I guess when a certain order can be
guaranteed), but I'm trying to keep my on personal opinion out of it,
hence
the whole approach of comparing via consensus.

--
Kit Peters, W0KEH
GPG public key fingerpint: D4FF AA62 AFEA 83D6 CC98 ACE5 6FAE 7E74 7F56
ED1D
Hello to any and all NSA, DEA, or other government or non-government agents
reading this email. Tell me about your life; I'll tell you about mine.

[tobyink]

From popefelix@gmail.com on 2019-09-12 18:58:25
:

You make a fair point as well. :)

I think that the best way to move forward is either for you to update your
tests to not care about object order, or for me to add the "canonical" flag
I mentioned above. I would prefer that you updated your tests, because
that's less work on my part, but I'm OK with doing the work if need be. Or
we could split the difference and I could advise you on adding the flag
yourself. :D

Up to you.

KP

On Thu, Sep 12, 2019 at 1:52 PM Christoph Burgmer via RT <
bug-JSON-Path@rt.cpan.org> wrote:

   Queue: JSON-Path

Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=130488 >

Fair point, but let's also call out

JSON parsing libraries have been observed to differ as to whether or
not they make the ordering of object members visible to calling
software. Implementations whose behavior does not depend on member
ordering will be interoperable in the sense that they will not be
affected by these differences.

It seems some people have seen the need to somewhat pass on the order.

Anyhow, let me know what you think is reasonable for your library. Feel
free to give the json-path-comparison project a run, it's meant to help,
not enforce :)

Am Do., 12. Sept. 2019 um 18:54 Uhr schrieb Kit Peters via RT <
bug-JSON-Path@rt.cpan.org>:

<URL: https://rt.cpan.org/Ticket/Display.html?id=130488 >

Sorry - I quoted an obsolete RFC. The correct one is RFC8259 (
https://datatracker.ietf.org/doc/rfc8259/?include_text=1), which again
defines an object to be "an unordered collection of zero or more
name/value
pairs".

To your question above of what constitutes "good" JSONPath, I would say
that good JSONPath produces results that a reasonable person would expect
having read Goessner's definition and RFC 8159. Thus, to put the question
in the context of this issue, if a JSONPath implementation imposes an
order
on the keys of an object, that implementation is out of compliance with
the
spec, consensus or no.

On Thu, Sep 12, 2019 at 11:00 AM Kit Peters popefelix@gmail.com wrote:

"Just for reference, I've tried looking for a source on the much quoted
JSON
standard"

Ah, that's an easy one! :)

RFC 7159 (http://www.rfc-editor.org/rfc/rfc7159.txt) states "An object
is
an unordered collection of zero or more name/value pairs" (emphasis
mine)

On Thu, Sep 12, 2019, 10:38 Christoph Burgmer via RT <
bug-JSON-Path@rt.cpan.org> wrote:

   Queue: JSON-Path

Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=130488 >

Just for reference, I've tried looking for a source on the much quoted
JSON
standard as it came up in other discussions as well, and so far only
found

The JSON syntax does not impose any restrictions on the strings used
as
names, does not require that name strings be unique, and does
not
assign any significance to the ordering of name/value pairs. These
are
all semantic considerations that may be defined by JSON processors or
in
specifications defining specific uses of JSON for data interchange.

I've mentioned this in
cburgmer/json-path-comparison#3 where I'd
try
to
focus the general discussion on ordering for JSONPath, but wanted to
call
this out here once.

Am Do., 12. Sept. 2019 um 17:24 Uhr schrieb Christoph Burgmer <
christoph.burgmer@gmail.com>:

I needed some time to think on this.

What's currently making the outcome hard to compare is that a query
like
$[*] on an object doesn't yield a stable representation. If there
is
a,
say, simple way of achieving that, it would help, yes.
The ordering has to already be preserved when parsing the JSON
document
though (see

https://github.com/cburgmer/json-path-comparison/blob/Perl_JSON-Path/implementations/Perl_JSON-Path/main.pl#L9

),

as this already introduces indeterminism in Perl I believe (as
decode_json
returns a hash I believe). Python for example does allow that.

Kit, my goal with the comparison project is to seek clarification on
what
"good" JSONPath is (including I guess when a certain order can be
guaranteed), but I'm trying to keep my on personal opinion out of
it,
hence
the whole approach of comparing via consensus.

--
Kit Peters, W0KEH
GPG public key fingerpint: D4FF AA62 AFEA 83D6 CC98 ACE5 6FAE 7E74 7F56
ED1D
Hello to any and all NSA, DEA, or other government or non-government
agents
reading this email. Tell me about your life; I'll tell you about mine.

--
Kit Peters, W0KEH
GPG public key fingerpint: D4FF AA62 AFEA 83D6 CC98 ACE5 6FAE 7E74 7F56 ED1D
Hello to any and all NSA, DEA, or other government or non-government agents
reading this email. Tell me about your life; I'll tell you about mine.