spec: need to specify iteration order of struct comprehension

[cueckoo]

Originally opened by @myitcv in https://github.com/cuelang/cue/issues/474

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

$ cue version
cue version +304b02e linux/amd64

Does this issue reproduce with the latest release?

Yes

What did you do?

exec cue eval

-- a.cue --
package x

m: banana: 4
-- b.cue --
package x

m: apple: 3
-- cue.mod/module.cue --
module: "mod.com"
-- x.cue --
package x

m: {
        aardvark: 5
}

l: [ for k, _ in m {k}]

What did you expect to see?

From the spec I'm unclear what to expect. My intuition is that the iteration order of the struct comprehension would be defined as [filename, offset].

What did you see instead?

m: {
    banana:   4
    apple:    3
    aardvark: 5
}
l: ["banana", "apple", "aardvark"]

which matches my intuition.

That said I think clarifying this in the spec is probably necessary?

See also discussion in https://github.com/cue-lang/cue/issues/1348

[cueckoo]

Original reply by @mpvl in https://github.com/cuelang/cue/issues/474#issuecomment-674040620

Currently, the iteration order is not defined in the spec (unspecified) and thus up to the implementation.

In the old implementation, each field name had a unique id (assigned roughly in order of appearance) and the order was defined by this ID.

In the new implementation there is currently no ordering at all. I do want to implement merge sorting for unification (making it O(n)), after which this ordering would be reintroduced.

The new exporter, however, prints fields in topological order (or undefined if this is there is no topological sort). It probably makes sense to give some guarantees for this in the spec. Similarly, we could then also give some guarantees for iteration order.

[JensRantil]

FYI, https://github.com/cue-lang/cue/discussions/1896#discussion-4346676 contains a use-case for order-preserving iteration.