5 ms·

"Object members must be sorted by ascending lexicographic order of their keys." How should the following be serialized? {"öp":1, "op":0}

by dsp1234 10y ago

kbenson 10y ago
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.
- nocman 10y ago
  Um, the first character of each key is different -- they are not the same.
  - kbenson 10y ago
    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.
    - cwyers 10y ago
      Alphabetical order changes from language to language. If you don't specify a collation, you can run into edge cases.
      - wrs 10y ago
        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.
        kbenson 10y ago
        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)?
        seagreen 10y ago
        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.
        seagreen 10y ago
        Great point about new languages meaning language-aware sorting systems will definitely have breaking changes.
    - pwdisswordfish 10y ago
      Of those two? That depends on whether your language is German or Swedish.
amock 10y ago
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.
- dsp1234 10y ago
  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)?
  - seagreen 10y ago
    > 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 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.
seagreen 10y ago
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 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/ 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 https://tools.ietf.org/html/rfc7159#section-8.3

"Object members must be sorted by ascending lexicographic order of their keys." How should the following be serialized? {"öp":1, "op":0}

by dsp1234 10y ago

"Object members must be sorted by ascending lexicographic order of their keys." How should the following be serialized? {"öp":1, "op":0}

kbenson 10y ago

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.

nocman 10y ago
Um, the first character of each key is different -- they are not the same.
- kbenson 10y ago
  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.
  - cwyers 10y ago
    Alphabetical order changes from language to language. If you don't specify a collation, you can run into edge cases.
    - wrs 10y ago
      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.
      - kbenson 10y ago
        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)?
        seagreen 10y ago
        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.
      - seagreen 10y ago
        Great point about new languages meaning language-aware sorting systems will definitely have breaking changes.
  - pwdisswordfish 10y ago
    Of those two? That depends on whether your language is German or Swedish.

amock 10y ago

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.

dsp1234 10y ago
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)?
- seagreen 10y ago
  > 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 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.

seagreen 10y ago

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 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/ 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 https://tools.ietf.org/html/rfc7159#section-8.3