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.
EDIT: Since v0.12.0-alpha.2, "toposort" is enabled by default. If you need to turn it off, set CUE_EXPERIMENT=toposort=0 in your environment.
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 bb before cc before a
From these edges, there's a simple topological walk, which guarantees the output of z will be:
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.
By running
cue evalandcue exportwithCUE_EXPERIMENT=toposort, you enable the new "topological sorting" algorithm. This can be combined with other experimental flags, e.g.CUE_EXPERIMENT=toposort,evalv3.EDIT: Since v0.12.0-alpha.2, "toposort" is enabled by default. If you need to turn it off, set
CUE_EXPERIMENT=toposort=0in your environment.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:
For
z, we establish a graph with the following edges:gbeforebbbeforeccbeforeaFrom these edges, there's a simple topological walk, which guarantees the output of
zwill be:However, cycles can exist in this graph. Consider:
This minor change to the original example adds in the edge
abeforeb, thus creating a cycle inz. 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 reachingg, it then finds the cycle (a -> b -> c -> a) and choosesbas the entry to the cycle (which is justified because of the edgeg -> b, and the fact there's no edge fromg(or any predecessor ofg) to any other node within the cycle), so the output ofzwill be{g: _, b: _, c: _, a: _}.Please use this issue to record further feedback; surprises, undesirable behaviour etc.