Subject: Re: [Jsonpath] Partial determinism of the descendant selector (..)

From: Stefan Gössner <[email-masked]>
Date: Fri, 10 Sep 2021 14:24:45 +0200

I must confess, that I am quite passionless here, but I can see the 
usefulness for test. I am open to arguments in any directions, as long 
as it not too restrictive seen from implementations.
--
sg

Am 17.08.2021 um 12:43 schrieb Glyn Normington:
> On Mon, 16 Aug 2021 at 15:50, Carsten Bormann <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     On 2021-08-16, at 16:07, Glyn Normington
>     <[email-masked]
>     <mailto:[email-masked]>> wrote:
>     >
>     > This topic is covered in issue 103, which seems to have stalled,
>     so let me put the main options to the mailing list to try to
>     discern any consensus.
>     > Regardless of the detailed language, please could you indicate
>     which of these options you favour:
>     >
>     > A. Don't tie down the non-determinism of .. at all
>     >
>     > B. Require .. to visit arrays in array order and visit nodes
>     before their descendants
>
>     Yes.
>     (There is no order in maps, so this is as deterministic as it can
>     get.)
>     BTW, the term “pre-order” [1] is in wide use as a handy term for
>     "visit nodes before their descendants” (we would still define it
>     that way).
>
>
> At the risk of another digression, pre-order is more prescriptive than 
> "visit nodes before their descendants". Take this example from [1]:
>
> image.png
>
>
> Pre-order traversal would be "F, B, A, D, C, E, G, I, H", but "visit 
> nodes before their descendants” allows more possibilities, such as "F, 
> B, G, A, D, C, I, E, H".
>
> By being less prescriptive, I was trying to allow for parallel 
> implementations.
>
>
>     > C. Some other option involving B with the option of A or A with
>     the option of B, using some kind of language TBD.
>
>     Yes, as well :-).
>     We haven’t really discussed levels of compliance, and a version of
>     “doesn’t return .. in order” could be a form of conditional
>     compliance.
>     *If* we think we need this to drag some implementations along.
>     (That is, I’d like to hear arguments of the form “We’d lose
>     foomatic’s JSONPath implementation because they make a point of
>     returning arrays in reverse order on Fridays” before we load
>     ourselves with conditional compliance.)
>
>     Grüße, Carsten
>
>     [1]: https://en.wikipedia.org/wiki/Tree_traversal#Pre-order,_NLR
>     <https://en.wikipedia.org/wiki/Tree_traversal#Pre-order,_NLR>
>     (This article talks about binary trees only, probably because they
>     want to discuss in-order as well, which only makes sense for
>     binary trees.)
>
>     > D. Something else, in which case please say what.
>     >
>     > Regards,
>     >
>     > Glyn
>     >
>     >
>     >
>     > --
>     > Jsonpath mailing list
>     > [email-masked] <mailto:[email-masked]>
>     > https://www.ietf.org/mailman/listinfo/jsonpath
>     <https://www.ietf.org/mailman/listinfo/jsonpath>
>
>
> <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient> 
> 	Virenfrei. www.avg.com 
> <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient> 
>
>
> <#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>
>

---

From: Tim Bray <[email-masked]>
Date: Fri, 10 Sep 2021 14:40:23 -0700

I would much prefer to avoid levels of compliance to the degree possible,
so I am in favor of option B.

I'd go further and be in favor of strict pre-order. In this case I think
being unsurprisingly deterministic is more important than hypothetical
optimizations that might turn out to unlock parallel implementations which
might be relevant to some proportion of users.  Anyhow, if you told me to
write a parallel implementation that preserved pre-order, I think I could,
by having each thread remember the array index it's rooted at, then
re-stitching together, no?

On Mon, Aug 16, 2021 at 7:50 AM Carsten Bormann <[email-masked]> wrote:

> On 2021-08-16, at 16:07, Glyn Normington <[email-masked]>
> wrote:
> >
> > This topic is covered in issue 103, which seems to have stalled, so let
> me put the main options to the mailing list to try to discern any consensus.
> > Regardless of the detailed language, please could you indicate which of
> these options you favour:
> >
> > B. Require .. to visit arrays in array order and visit nodes before
> their descendants
>
> Yes.
> (There is no order in maps, so this is as deterministic as it can get.)
> BTW, the term “pre-order” [1] is in wide use as a handy term for "visit
> nodes before their descendants” (we would still define it that way).
>
> > C. Some other option involving B with the option of A or A with the
> option of B, using some kind of language TBD.
>
> Yes, as well :-).
> “doesn’t return .. in order” could be a form of conditional compliance.
> (That is, I’d like to hear arguments of the form “We’d lose foomatic’s
> JSONPath implementation because they make a point of returning arrays in
> reverse order on Fridays” before we load ourselves with conditional
> compliance.)
>
> Grüße, Carsten
>
> (This article talks about binary trees only, probably because they want to
> discuss in-order as well, which only makes sense for binary trees.)
>
> > [email-masked]
> [email-masked]

---

From: Martin J. Dürst <[email-masked]>
Date: Sat, 11 Sep 2021 09:17:57 +0900

I'm very much with Tim here.

But if maps are by definition unordered, it looks like the whole 
argument about testing,... doesn't work out.

Ruby for a long time pretended that hashes (the equivalent of maps) were 
unordered, but because users depended on the order the implementation 
produced, we eventually had to give up on that and declare them ordered.

For JSON, the situation is probably different.

Regards,   Martin.

---

From: Glyn Normington <[email-masked]>
Date: Sat, 11 Sep 2021 03:28:45 +0100

Yes, maps are unavoidably unordered, but that can be catered for in testing
by using maps with only one key/value pair or by allowing multiple possible
results for maps with more than one key/value pair. E.g. to unit test a
selector containing `..`, I can make sure any maps in the input argument
have only one key/value pair each.

In other words, making `..` partially deterministic doesn't solve the
testing problem for maps with more than one key/value pair, but it makes
testing more tractable than with a non-deterministic `..`.