Define string sorting by "code unit order"

[domenic]

Background: whatwg/url#199

We want to update specs to be unambiguous about this, so I think infra is a good place to define it. It should include some examples (similar to the URLSearchParams WPTs).

[aphillips]

I don't want to add a circular reference here: I commented on url#199 to the effect that 'code unit' requires that the character encoding (probably UTF-16 if working in terms of the DOM) be specified. If we're working in terms of UTF-8 byte strings, code point order would be better. Otherwise sort won't do anything reasonable.

[annevk]

We should settle this in a similar way to how we settle sizing of strings I think, as discussed in #74. And this would be easy to fix once #73 is done.

[annevk]

We should also fix byte sorting for whatwg/fetch#454.

[annevk]

This should probably do something like https://en.wikipedia.org/wiki/Comparison_sort, but not sure yet. See also advice from @domenic in #74.

[annevk]

I'm thinking it should be something like this:

To sort JavaScript strings perform a comparison sort using the following three-way comparison operation, given A and B:

• If A is B, then return 0.
• If A is a prefix of B, then return -1.
• If B is a prefix of A, then return 1.
• For each code unit a and b in A and B:
  • If a is b, then continue.
  • If a is less than b, then return -1.
  • Return 1.

This will get a little repetitive though to do for byte sequences, JavaScript strings, and strings.

[aphillips]

For the W3C spec IndexedDb, I suggested some text that may come in handy in annotating this:

This matches the Array.prototype.sort on an Array of Strings. This ordering compares the 16-bit code units in each string, producing a highly efficient, consistent, and deterministic sort order. The resulting list will not match any particular alphabet or lexicographical order, particularly for code points represented by a surrogate pair.

[domenic]

Personally I think we should be able to just define a "less than" operation on two strings. We don't need the 0/1/-1. Mathematically at least only less than is necessary (plus an implicit "equals" concept).

I would also define "code unit comparison", and then say that a "sort" operation takes a comparison. I would not tie together the definition of sort and the specific comparison we use.

We should probably also define ascending vs. descending sort (and say ascending is the default), although we could wait until we have a definite consumer for that.

I like @aphillips's text particularly for pointing out the advantages and caveats.

As for the repetition, this kind of thing makes me wonder about our implicit concept of "sequence" that we are using for both strings + byte sequences. It's kind of a list even, but I'm not sure I'd want to go that far in the layering... Still, it would be nice to generalize the sorting to work on all three sequence types.

[annevk]

Perhaps they can be lists with immutable size/length. Even if you just define "less than", you'd still have most of the steps I outlined above, no? Apart from the first step that is.

[domenic]

Hmmm, yeah, I guess that's true.

[annevk]

Note that if we settle #91 on mutable treating these as list-likes seems likely. We already have places that use "append" on strings, although they sometimes get passed a code point and sometimes a string (which would more argue for "extend"/"concat" if we're being picky).

[annevk]

(CSS Typed OM uses "code point order" for some things.)