Repository: bazelbuild/bazel
Issue: json.decode is too strict; fails on duplicate keys
Labels: type: bug
P4
team-Starlark-Interpreter

### Description of the bug:


A couple of packages are published to npm with a JSON descriptor which is valid in every context it's used.

However `json.decode` fails on this part of the file:
```
  "typeCoverage": {
    "atLeast": 100,
    "detail": true,
    "strict": true
  },
  "typeCoverage": {
    "atLeast": 100,
    "detail": true,
    "strict": true,
    "ignoreCatch": true
  }
```
More context here:
https://github.com/aspect-build/rules_js/issues/148

I agree with the library author that it's really a Bazel bug, which should follow the https://en.wikipedia.org/wiki/Robustness_principle of "be permissive in what you accept". Author points this out:
https://github.com/wooorm/decode-named-character-reference/issues/2
https://github.com/wooorm/stringify-entities/issues/11

### What's the simplest, easiest way to reproduce this bug? Please provide a minimal example if possible.


```
json.decode("""
{
  "typeCoverage": {
    "atLeast": 100,
    "detail": true,
    "strict": true
  },
  "typeCoverage": {
    "atLeast": 100,
    "detail": true,
    "strict": true,
    "ignoreCatch": true
  }
}
""")
```

### What is the output of `bazel info release`?

5.x


Issue comments:
What is the most useful and still rational behavior here? You could plausibly argue four approaches:

1. keep the value of the first key seen
2. keep the value of the last key seen
3. merge the values of duplicates if the value is an object
4. error

experiment:
```
$ node -e 'console.log(JSON.parse("{\"a\": 1, \"a\": 2}"))'
{ a: 2 }
```

So the answer I'd most like coming from a NodeJS ecosystem is to take your option 2.

I dunno if that's formally documented in the nodejs spec.
Taking the last entry seems preferable over taking the first, since it's more consistent with `dict.update`, the `dict()` constructor, etc. But it's not clear whether that's better or worse than failing. We could also make it an option, i.e. a named arg to decode, but I'm not sure I want to complicate that API.
ping! @brandjon will you take PRs for this?
[ECMA-262](https://262.ecma-international.org/13.0/#sec-json.parse) says under 25.5.1.1
> Note 2 In the case where there are duplicate name Strings within an object, lexically preceding values for the same key shall be overwritten.

This aligns with option 2.
ping! @brandjon would you accept a PR? Another user on Slack tripped over this.
Different JSON parsers diverge on this point: https://stackoverflow.com/questions/21832701/does-json-syntax-allow-duplicate-keys-in-an-object

Javascript, and anything that tries to be compatible with Javascript, of course allows duplicate keys and keeps the last value.

C and C++ based JSON parsers typically don't allow duplicate keys.

I have no strong opinion on which way to go, but given the need to integrate with npm, we may as well follow Javascript's behavior.
I think the critical observation is that Bazel is meant to be the orchestration for a bunch of third-party package managers and tools, so it should follow the https://en.wikipedia.org/wiki/Robustness_principle
Meaning, even if parsers typically reject some input, Bazel's job is to "be permissive in what it accepts" to maximize compatibility.
Same argument I made for https://github.com/bazelbuild/bazel/commit/c9e2be52a067dd9abf5efa4f5f55bb5b98cf5d3b
Rationale for accepting the change:

* The JSON RFC apparently leaves this unspecified, so we're not prohibited from doing it.
* JavaScript will allow it, with the unsurprising (and consistent with `dict`) semantics that last key wins.
* It supports this Node-related use case.

(The "Robustness principle" can be problematic -- think HTML. But we're maintaining a parser, not writing a new standard.)
@brandjon @tetromino I don't suppose you guys know which release this will hit? 
Given that this doesn't change the behavior on inputs that didn't hard fail before this change, I would propose to cherry-pick it into 6.2.0. Otherwise it would naturally make its way into 7.0.0.
I am asking for a cherry-pick at https://github.com/bazelbuild/bazel/pull/17868

Pull request review comments:

Patch that resolved the issue:
diff --git a/src/main/java/net/starlark/java/lib/json/Json.java b/src/main/java/net/starlark/java/lib/json/Json.java
index c97972d8599f97..b366c740a18022 100644
--- a/src/main/java/net/starlark/java/lib/json/Json.java
+++ b/src/main/java/net/starlark/java/lib/json/Json.java
@@ -287,7 +287,8 @@ private void appendQuoted(String s) {
               + " a decimal point or an exponent. Although JSON has no syntax "
               + " for non-finite values, very large values may be decoded as infinity.\n"
               + "<li>a JSON object is parsed as a new unfrozen Starlark dict."
-              + " Keys must be unique strings.\n"
+              + " If the same key string occurs more than once in the object, the last"
+              + " value for the key is kept.\n"
               + "<li>a JSON array is parsed as new unfrozen Starlark list.\n"
               + "</ul>\n"
               + "Decoding fails if x is not a valid JSON encoding.\n",
@@ -398,11 +399,7 @@ private Object parse() throws EvalException {
               }
               i++; // ':'
               Object value = parse();
-              int sz = dict.size();
               dict.putEntry((String) key, value); // can't fail
-              if (dict.size() == sz) {
-                throw Starlark.errorf("object has duplicate key: %s", Starlark.repr(key));
-              }
               c = next();
               if (c != ',') {
                 if (c != '}') {


Test patch:
diff --git a/src/test/java/net/starlark/java/eval/testdata/json.star b/src/test/java/net/starlark/java/eval/testdata/json.star
index 51180b44860b2d..ff43163505cf78 100644
--- a/src/test/java/net/starlark/java/eval/testdata/json.star
+++ b/src/test/java/net/starlark/java/eval/testdata/json.star
@@ -80,6 +80,9 @@ assert_eq(json.decode('"\\u0123"'), 'ģ')
 assert_eq(json.decode('\t[\t1,\r2,\n3]\n'), [1, 2, 3]) # whitespace other than ' '
 assert_eq(json.decode('\n{\t"a":\r1\t}\n'), {'a': 1}) # same, with dict
 assert_eq(json.decode(r'"\\\/\"\n\r\t"'), "\\/\"\n\r\t") # TODO(adonovan): test \b\f when Starlark/Java supports them
+assert_eq(json.decode('{"x": 1, "x": 2}'), {"x": 2})
+assert_eq(json.decode('{"x": {"y": 1, "y": 2}}'), {"x": {"y": 2}})
+assert_eq(json.decode('{"x": {"y": 1, "z": 1}, "x": {"y": 2}}'), {"x": {"y": 2}})
 
 # We accept UTF-16 strings that have been arbitrarily truncated,
 # as many Java and JavaScript programs emit them.
@@ -123,7 +126,6 @@ assert_fails(lambda: json.decode('[1, 2}'), "got \"}\", want ',' or ']'")
 assert_fails(lambda: json.decode('{"one": 1'), "unexpected end of file")
 assert_fails(lambda: json.decode('{"one" 1'), 'after object key, got "1", want \':\'')
 assert_fails(lambda: json.decode('{"one": 1 "two": 2'), "in object, got ..\"., want ',' or '}'")
-assert_fails(lambda: json.decode('{"x": 1, "x": 2}'), 'object has duplicate key: "x"')
 assert_fails(lambda: json.decode('{1:2}'), "got int for object key, want string")
 assert_fails(lambda: json.decode('{"one": 1,'), "unexpected end of file")
 assert_fails(lambda: json.decode('{"one": 1, }'), 'unexpected character "}"')