Partial Orderings

[mjpitz]

In investigating #131 yesterday, I noticed that part of our client-side code is incomplete. As a result, queries for a topology can return partial orderings instead of correct orderings.

How does this happen?

The most common way this comes up is when there is a cycle in the graph. Cycles in graphs introduce complications. For one, it's possible that there is no correct ordering.

Current Situation

When the deps command-line tool runs, it will output an ordering. We currently do not provide any feedback that the ordering is partial or correct. We don't provide a sense of how many modules are omitted.

Improvements

• set run to a non-error status code when the output is a partial ordering (determined by the remaining entries in the map)
• support outputting information to a file
• Update traversal logic to better account for this case. For example, some cycles can be addressed by re-running a loop. Another option could be to switch the topological sort over to using depth-first search. It might be able to handle some of these cases that breadth-first can't handle well.

[mjpitz]

@mkw for visibility

[mjpitz]

In v1beta, I've noticed this far less often. I suspect it's due to the improved data model.