Ordering, Associative Arrays, and JSON Objects

[mnot]

In #1, we decided to not attach significance to the ordering of associative arrays in variables, and to adjust the test case format to suit. However, it appears that some tests added after #1 was incorporated didn't account for this. Specifically:

• uritemplate-test/extended-tests.json

  Lines 144 to 146 in 1eb27ab

  	["{+keys}", "key1,val1%2F,key2,val2%2F"],
  	["{#keys}", "#key1,val1%2F,key2,val2%2F"],
  	["{keys}", "key1,val1%252F,key2,val2%252F"]

  (commit 8281c73)

In #58, we had a report that because some implementations of JSON don't expose object ordering (as noted in the JSON RFC), so some tests were failing for them.

Having forgotten about #1, I reasoned that associative arrays are implicitly ordered, and started #63.

I think our choices are:

1. Associative array ordering should be honoured by templates, so we should incorporate JSON objects -> associative arrays #63 (after more work), or
2. It shouldn't, so we should incorporate Reserved expansion dictionary explode alternate ordering #58.

In either case, an errata against the spec should be filed to clarify this.

If we had a clean slate, I think (1) is the right way to go -- associative arrays are clearly ordered, the spec uses them and not hashes/dictionaries for examples, and it's downright odd/surprising for cases where ordering matters (e.g., path segments).

BUT we don't have a clean slate: we have an unknown number of implementations and several years of deployment. That argues for (2).

HOWEVER, I would note that the change in 8281c73 has been in the test cases for several years now and no one has complained about this causing issues for them until now. That seems to me to indicate that implementations are already honouring the ordering here, and that we could do (1) safely.

Data most welcome.

/CC @jcgregorio @royfielding @hadleynet @DavidOrchard

[mnot]

While there are some examples that accommodate other orderings, there are also some that do not, implying that this isn't interoperable.

[andreaTP]

Hi, thanks for the write up @mnot !

I'm a maintainer of std-uritemplate, currently, there is no support for associative arrays in std-uritemplate, the simple reason is that there are no tests leveraging it in the current master branch of this repo.

Currently, we pass the testsuite by using a specific ordering in 2 different languages(out of 9): Go and Swift.

I think we need to formally define "associative arrays", in the spec they are arrays of tuples(name, value), but, when encoded in JSON, an array of array is used, this is a lossy translation and open the door to multiple edge cases (null values, pairs with missing/multiple values etc. etc.).

Talking about the choices:

1. Associative array ordering should be honoured by templates -> since associative arrays are already part of the spec this seems the natural choice, but, I think that we should take into consideration 2 additional aspects:
   • performance: uritemplate is used on hot paths and accessing a list of tuples instead of looking up in a map has performance consequences
   • UX: using arrays of tuples differs very much across different programming languages, it's usually fine with dynamic PLs but it becomes cumbersome in some typed ones, e.g. in Java 8 it would look like:

Map<String, Object> substs = new HashMap();
List<List<Object>> assocArrayValue = new ArrayList();
List<Object> tuple1 = new ArrayList();
tuple1.add("key1");
tuple1.add("value1");
assocArrayValue.add(tuple1);

subst.put("mysubst", assocArrayValue);

2. This requires the least effort, and we would be able to remove the additional, costly, sorting of maps from the Go and Swift implementations

[alexdeem]

Hi, thanks for the context on this @mnot

I am the maintainer of SwiftScream/URITemplate and the author of #58 that seems to have kicked this discussion off.

I too think that (1) would be the correct approach if we had a clean slate, and that things are complicated because we don't.

My perspective on this is that choosing (2) has the benefit of not rendering any currently valid implementations invalid; and that (1) has the benefit of fully specifying the process such that different implementations are interoperable.

I don't feel I have the experience to make a call on this, so I'm happy to delegate to those that do.

For what it's worth, my implementation does support ordered associative arrays. My trouble has just been with extracting ordered associative arrays from these json files. I've worked around this currently by sorting the elements by key, as that happens to be the order in the file.

I have some thoughts regarding the remarks on approach (1) made by @andreaTP:

performance: uritemplate is used on hot paths and accessing a list of tuples instead of looking up in a map has performance consequences

I don't understand. Template processing never performs a lookup in an associative array, the elements are just enumerated. The performance comparison would be between enumerating a map, and enumerating a list of tuples. What am I missing?

UX: using arrays of tuples differs very much across different programming languages, it's usually fine with dynamic PLs but it becomes cumbersome in some typed ones

I agree this is a concern. However, I think it's reasonable for an implementation to provide convenience here, particularly for the case where the consumer explicitly does not care about ordering. In SwiftScream/URITemplate the processing core operates on ordered key-value pairs, but providing an unordered dictionary is supported. The unordered dictionary is converted into ordered key-value pairs prior to processing.

[andreaTP]

I don't understand. Template processing never performs a lookup in an associative array, the elements are just enumerated. The performance comparison would be between enumerating a map, and enumerating a list of tuples. What am I missing?

I double checked the implementation and you are right 👍 no performance difference, I'll strike it in my previous message.

My trouble has just been with extracting ordered associative arrays from these json files. I've worked around this currently by sorting the elements by key, as that happens to be the order in the file.

I think this shows the impracticality of using nested arrays to represent tuples, at the same time I agree that this aspect can be smoothed by providing convenience at the library level.

[royfielding]

This isn't an errata for the spec, though perhaps a worthy note if it is ever revised.

URI templates exist first to describe a potential URI set [the range of valid URIs to access the described resource(s)] and second as a guide to generating a single URI given values for the named variables.

For query parameters (a design based on HTML forms), the potential URI set is unordered (just like in real life HTML forms), whereas the second set is defined as ordered generation. IOW, the spec identifies queries as an unordered set but only defines one order for generation. I believe that was intentional for simplicity and to reduce duplicate cache entries.

Hence, if you are testing the scope of resources described by a given URI template, the result set needs to be unordered. However, if you are specifically testing the generation algorithm, that algorithm (defined by the spec) is ordered. On purpose.

[sigmavirus24]

As the author and maintainer of the defacto python standard uritemplate I think it's probably best to do 1.

However, if you are specifically testing the generation algorithm, that algorithm (defined by the spec) is ordered. On purpose.

It's been a while since I've re-read 6570, but I don't recall an order being specified in the RFC. A quick scan in the places I'd expect to see mention aren't obviously calling out an ordering of hash-based storage.

Orders of arrays I agree are implicit, but that is a detail common across languages. Assuming a hash-based object, (JSON Object) parsed into something preserving ordering is not reasonable necessarily. Entertainingly Ruby used to preserve insertion order and Python didn't, and I believe in recent years, that's flip-flopped.

[royfielding]

Bah, you are right -- I was looking at the wrong example. We didn't specify an ordering for keys expansion since there is no order visible in the template. So, I would go with (2) and keep the tests relatively short.

[mnot]

That makes the path-oriented operator effectively useless. My thinking was that we used associative arrays for variables in the examples to make the ordering explicit - in all examples, it is honoured.

[royfielding]

I agree it doesn't behave like a traditional path, but there is no requirement that paths be path-like. I have actually implemented a virtual path that was treated as a parameter list, but I can't remember why. Probably because PATH_INFO was available where query was reserved for some other (customer) use. Anyway, …

The problem with making the order explicit is that we don't communicate the array values. We provide them in the spec in a certain order because they are local to the implementation. How do clients and servers know each other's order? If we had specified some kind of sort order, that would interop, but we didn't have an example of that in practice. Perhaps we could say that something else might specify the order, like Link-Template, but I'd rather just leave it less useful.

Generally speaking, we only have to worry about specifying the useful stuff correctly. ;-)