Couldn't you solve that by sorting by the underlying byte order? Since it is required to be UTF-8 that should be fast and unambiguous.

You could, and that's partially what prompted the question, but that's not quite what the specification says currently.

edit:

and unambiguous.

var x = "\u0307\u0323\u0073"

var y = "\u0073\u0323\u0307"

These are arguably the same grapheme when displayed on a screen, but they would be considered different keys in SON, and sorted in different spots. I'm actually unsure if most diffing systems would catch that they are different or not, and if so, how they would represent that difference to the end user (since just showing the grapheme would be useless as they are the same).

The specification is silent on normalization, so a SON pipe could output an object with those as keys (and still meet spec), but not be accepted by a conforming SON parser (that did unicode normalization on incoming keys). So really, the specification should say which of the canonical normalized forms to use, or that keys should specifically may not be normalized/modified in any way. This works fine if you're running something like JavaScript -> JavaScript -> JavaScript, but would fail if a (currently conforming) system in the middle defaults to normalized unicode representations. In other words, would a pipeline like Firefox -> Swift -> Python -> Swift -> Nodejs -> Swift -> Firefox, even if they had conforming SON implementations (of the current specification)?

> not be accepted by a conforming SON parser (that did unicode normalization on incoming keys)

I don't think RFC 7159 actually mentions Unicode normalization at all. If it was in there I think it would be mentioned in the section on string comparisons, but that just talks about going unescaped codepoint by unescaped codepoint: https://tools.ietf.org/html/rfc7159#section-8.3

EDIT: Does Unicode normalization change over time? If so we definitely have to leave it out and just go codepoint by codepoint, because we don't want the validity of a Son document to change.

Good catch. I kind of slacked on this since I knew it would be a solvable problem once everything else got worked out.

Right now the reference implementation sorts by comparing codepoints one-on-by one. When it reaches a codepoint that's unequal or nonexistant it orders the string with the lesser or nonexistant codepoint first.

So in your example, after serializing from JSON and deserializing to Son we get `{"op":0,"öp":1}`.

Two remaining questions:

1. What's the most unambiguous way to describe this process?

2. Right now the comparison is on unescaped strings. Should it be on escaped strings instead?

There's an issue open to discuss this here: https://github.com/seagreen/Son/issues/1

EDIT: I am curious what Unicode recommends for language-aware sorting, even though we're not going to use it. Is this the right place to look? http://unicode.org/reports/tr10/

EDIT2: RFC 7159 has language about equality that's relevant to comparisons. I'm confident now we're on the right track: https://tools.ietf.org/html/rfc7159#section-8.3

Isn't that invalid? You can't have two object members with the same name, can you? I would assume that should be impossible to emit.

Um, the first character of each key is different -- they are not the same.

Ah, I see. That wasn't obvious to me when I first looked.

Isn't sorting of Unicode characters defined under Unicode? I think the correct answer for "how do I sort my unicode strings" is "defer to unicode".

That may be quite expensive in the end, depending on object size and content.

Of those two? That depends on whether your language is German or Swedish.

Alphabetical order changes from language to language. If you don't specify a collation, you can run into edge cases.

And you can't specify "a collation" in a way that will be guaranteed to mean exactly the same thing next year. I don't believe there's a way to do a permanently stable sort if you also want it to reflect the current state of Unicode. (An obvious example is that an entire language might have been added to Unicode since you serialized something with those code points in it.)

NTFS, which has to build a b-tree of filenames in a permanently stable sort order, solved this by writing the collation table to the disk when it's formatted, and never changing it again. Which means the Windows shell still has to re-sort the filenames because the currently "correct" collation may be different.

Hmm, then maybe the easiest solution is to sort numerically by unicode code point, and accept that combining characters will look weird.

Or are there problems with that as well that I'm not considering (beyond it being less human readable)?

I think the way to go is definitely by code point. We don't want to pull any more of the Unicode spec into Son than we have to.

Happily sorting is only used to order members within Son objects. Individual strings are never sorted, so there isn't a worry about sorted strings coming out messy.

Great point about new languages meaning language-aware sorting systems will definitely have breaking changes.