Sorting Problem with Unicode Character Ordering

[marcelotto]

I encountered a sorting issue in this JCS implementation when using it in my JSON-LD.ex library while updating it to conform to the JSON-LD 1.1 specification. When running the W3C test suite, specifically test tjs13, the test is failing due to incorrect ordering of Unicode characters.

Input JSON

{
  "\u20ac": "Euro Sign",
  "\r": "Carriage Return",
  "\u000a": "Newline",
  "1": "One",
  "\u0080": "Control\u007f",
  "\ud83d\ude02": "Smiley",
  "\u00f6": "Latin Small Letter O With Diaeresis",
  "</script>": "Browser Challenge"
}

Expected output

{"\u000a":"Newline","\r":"Carriage Return","1":"One","</script>":"Browser Challenge","\u0080": "Control\u007f","\u00f6":"Latin Small Letter O With Diaeresis","\u20ac":"Euro Sign","\ud83d\ude02":"Smiley"}

Actual output

{"1":"One","</script>":"Browser Challenge","\u000a":"Newline","\r":"Carriage Return","\u0080":"Control ","\u00f6":"Latin Small Letter O With Diaeresis","\u20ac":"Euro Sign","\ud83d\ude02":"Smiley"}

[pzingg]

Thanks @marcelotto for submitting this. I am adding tjs09 through tjs13 to the tests. Right now tjs11, tjs12 and tjs13 are failing. I will try to fix them soon.

[marcelotto]

That's strange. These tests are actually passing in my implementation. I have just checked tjs12 again manually on a random basis and can confirm that your implementation is producing the correct result. It should be noted that within these tests only the value of a property with a @json type should be compared with respective object values in the RDF output, since only there the JSON canonicalization is applied.

# the value under e in toRdf/js12-in.jsonld
iex> "{\n    \"numbers\": [333333333.33333329, 1E30, 4.50, 2e-3, 0.000000000000000000000000001],\n    \"string\": \"\\u20ac$\\u000F\\u000aA'\\u0042\\u0022\\u005c\\\\\\\"\\/\",\n    \"literals\": [null, true, false]\n  }"
...>  |> Jason.decode!()
...>  |> Jcs.encode()
"{\"literals\":[null,true,false],\"numbers\":[333333333.3333333,1e+30,4.5,0.002,1e-27],\"string\":\"€$\\u000f\\nA'B\\\"\\\\\\\\\\\"/\"}"

This exactly matches the rdf:JSON object value in toRdf/js12-out.nq:

_:b0 <http://example.org/vocab#c14n> "{\"literals\":[null,true,false],\"numbers\":[333333333.3333333,1e+30,4.5,0.002,1e-27],\"string\":\"€$\\u000f\\nA'B\\\"\\\\\\\\\\\"/\"}"^^<http://www.w3.org/1999/02/22-rdf-syntax-ns#JSON> .

[pzingg]

@marcelotto I found the bug, was sorting keys after encoding them, not before. I have a "unicode" branch started for a pull request.

However, now some of the floating-point number encoding tests are failing. The ECMA-262 number serialization algorithm is moderately complex and the Erlang float_to_binary function I was relying on must have changed (for the worse) in more recent OTP releases. I am working through the ECMA serialization now.

"Such [numeric] data MUST be serialized according to Section 7.1.12.1 of [ECMA-262], including the "Note 2" enhancement."

[pzingg]

@marcelotto PR #4 is open if you would like to test it. The 5 JSON-LD API "tjs" tests were added and pass., and the number serialization tweaks have been applied to the OTP 26 :erlang.float_to_binary results so that the 26 tests in the ECMA-262 Appendix B are now passing again.

[marcelotto]

Thank you for the PR. I've tested it, and the sorting issue is indeed fixed now.

I'm still getting a test failure with tjs13, but after investigating, I believe this is due to an issue in my N-Quads decoder in RDF.ex, not in your JCS implementation. (The way the special character U+0080 is being handled during the RDF deserialization process appears to be the root cause.)

Also, I'll be investigating another separate failing test that's now appearing with this new version in my RDF.ex library (where the JCS implementation is used as part of the rdf:JSON datatype handling). I'll let you know what I find out about this once I know more.

Thanks again for the quick fix on the sorting!

[marcelotto]

I've investigated the failing RDF.ex test and found a behavioural change I describe in this comment on the PR: #4 (comment)

[pzingg]

I will get back to this tomorrow to fix the codepoint error. I also want to see how Javascript, Go, and Rust implementations encode "\x80" through "\xa0" keys and values.

[marcelotto]

I've now investigated also the remaining problem with the tjs13 fail, which I initially thought was a problem with my N-Quads decoder, but I no longer believe that's the case.

Instead, I've traced it to the following behavioral change:

Previous version:

iex> Jcs.encode("\u0080")
<<34, 194, 128, 34>>

New version:

iex> Jcs.encode("\u0080")
"\"\\u0080\""

Here's my failing test in JSON-LD.ex:

  1) test toRdf#tjs13: Transform JSON literal with wierd canonicalization (JSON.LD.W3C.ToRdfTest)
     test/acceptance/w3c/to_rdf_test.exs:71
     RDF data is not isomorphic
     code:  assert_rdf_isomorphic(
     left:  #RDF.Graph<name: nil\n  @prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .\n  @prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .\n  @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .\n\n  [\n      <http://example.org/vocab#c14n> "{\\"\\\\n\\":\\"Newline\\",\\"\\\\r\\":\\"Carriage Return\\",\\"1\\":\\"One\\",\\"</script>\\":\\"Browser Challenge\\",\\"\\\\u0080\\":\\"Control\d\\",\\"ö\\":\\"Latin Small Letter O With Diaeresis\\",\\"€\\":\\"Euro Sign\\",\\"😂\\":\\"Smiley\\"}"^^rdf:JSON\n  ] .\n>
     right: #RDF.Graph<name: nil\n  @prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .\n  @prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .\n  @prefix xsd: <http://www.w3.org/2001/XMLSchema#> .\n\n  [\n      <http://example.org/vocab#c14n> "{\\"\\\\n\\":\\"Newline\\",\\"\\\\r\\":\\"Carriage Return\\",\\"1\\":\\"One\\",\\"</script>\\":\\"Browser Challenge\\",\\"\x80\\":\\"Control\d\\",\\"ö\\":\\"Latin Small Letter O With Diaeresis\\",\\"€\\":\\"Euro Sign\\",\\"😂\\":\\"Smiley\\"}"^^rdf:JSON\n  ] .\n>
     stacktrace:
       (rdf 2.1.0-pre) lib/rdf/test/assertions.ex:28: RDF.Test.Assertions.raise_non_isomorphic_error/2
       test/acceptance/w3c/to_rdf_test.exs:86: (test)

[pzingg]

Resolved by PR #4