evaluator: commutativity failure when using json/yaml marshal

[rogpeppe]

What version of CUE are you using (cue version)?

$ cue version
cue version v0.0.0-20230211165554-7d89acd5c44b

go version devel go1.21-a4d5fbc3a4 Thu Feb 9 21:14:00 2023 +0000
      -buildmode exe
       -compiler gc
     CGO_ENABLED 1
          GOARCH amd64
            GOOS linux
         GOAMD64 v1
             vcs git
    vcs.revision 7d89acd5c44bca0c756f76089436ee9913818b03
        vcs.time 2023-02-11T16:55:54Z
    vcs.modified false

Does this issue reproduce with the latest stable release?

Yes

What did you do?

Export this code:

import "encoding/json"

source1: {
    a: {
        p: 10
        q: 11
    }
    b: json.Marshal(a)
}
source2: {
    a: {
        q: 11
        p: 10
    }
    b: json.Marshal(a)
}
both1: source2 & source1
both2: source1 & source2

What did you expect to see?

both1 and both2 should be in error because source1.b and source2.b are different, so there's a conflict.

Alternatively, json.Marshal should ignore source order and source1, source2, both1, and both2 should be identical and contain the same fields in the same order.

What did you see instead?

{
    "source1": {
        "a": {
            "p": 10,
            "q": 11
        },
        "b": "{\"p\":10,\"q\":11}"
    },
    "source2": {
        "a": {
            "q": 11,
            "p": 10
        },
        "b": "{\"q\":11,\"p\":10}"
    },
    "both1": {
        "a": {
            "q": 11,
            "p": 10
        },
        "b": "{\"q\":11,\"p\":10}"
    },
    "both2": {
        "a": {
            "p": 10,
            "q": 11
        },
        "b": "{\"p\":10,\"q\":11}"
    }
}

[mpvl]

As usually is the case in CUE evaluation, the value of b in both(1|2) is recomputed. So x.b & y.b failing does, in general, not imply that x & y fails. For instance:

x: {
    a: *1 | 2
    b: a
}
y: {
    a: 2
    b: 2
}
z: x & y

Even though x.b & y.b fails, x & y is valid.

The current CUE was designed to adhere to a topological sort, falling back to a deterministic order if topological sort is not possible. So in that case, both1.b and both2.b should indeed have the same value. But this can be the case even if source1.b and source2.b are different.

[myitcv]

Note to self to write up notes/conclusions from this conversation.

[myitcv]

Linking to the issue which covers us defining order in the spec: https://github.com/cue-lang/cue/issues/474.

@mpvl

As usually is the case in CUE evaluation, the value of b in both(1|2) is recomputed

For my own understanding, is it that b is recomputed, or rather that its evaluation is, in all cases, delayed, and therefore happens after all unifications have been considered?

[rogpeppe]

To my mind, the issue is more clear cut than the comments above seem to make it out.

To my mind, one of the core properties of CUE is that it's commutative. That is, for any two subexpressions a and b, the result of a & b should be the same as the result of b & a. To my mind, that property is clearly violated here:

both1: source2 & source1
both2: source1 & source2

If & is truly commutative, then the result of both1 and both2 will be the same irrespective of what's inside source1 and source2.