CUE_EXPERIMENT=toposort Feedback

[cuematthew]

By running cue eval and cue export with CUE_EXPERIMENT=toposort, you enable the new "topological sorting" algorithm. This can be combined with other experimental flags, e.g. CUE_EXPERIMENT=toposort,evalv3.

The intention is that "topological sorting" should produce the same output with both versions of the evaluator, though we are aware of some minor differences at the time of writing.

It is called "topological sorting" because it creates a graph of field names and attempts to find a topological walk through that graph. For example:

x: {g: _, b: _, c: _}
y: {c: _, a: _}
z: x & y

For z, we establish a graph with the following edges:

• g before b
• b before c
• c before a

From these edges, there's a simple topological walk, which guarantees the output of z will be:

{g: _, b: _, c: _, a: _}

However, cycles can exist in this graph. Consider:

x: {g: _, b: _, c: _}
y: {c: _, a: _, b: _}
z: x & y

This minor change to the original example adds in the edge a before b, thus creating a cycle in z. Our algorithm detects these cycles and attempts to find a sensible place to break such cycles, in a deterministic fashion. Currently, in this particular scenario, after reaching g, it then finds the cycle (a -> b -> c -> a) and chooses b as the entry to the cycle (which is justified because of the edge g -> b, and the fact there's no edge from g (or any predecessor of g) to any other node within the cycle), so the output of z will be {g: _, b: _, c: _, a: _}.

Please use this issue to record further feedback; surprises, undesirable behaviour etc.