~bzr-pqm/bzr/bzr.dev

Viewing all changes in revision 4593.5.3.

  • Committer: John Arbash Meinel
  • Date: 2009-08-13 21:30:07 UTC
  • mfrom: (4577.3.2 1.18-topo_sort)
  • mto: This revision was merged to the branch mainline in revision 4629.
  • Revision ID: john@arbash-meinel.com-20090813213007-4wqkou02fo0tegay
Bring in the optimized tsort code.

It turns out we needed a way to detect that there was graph cycles.
The easiest way to do it, is by noticing that we end up with a node
that has no gdfo. That means it has a parent that was not reached
before the child was reached, when walking from nodes with no known parents.
I'm 90% sure that this is correct, but arguably it should be detected
when creating the KnownGraph, and not during topo_sort.

expand all expand all

Show diffs side-by-side

added added

removed removed

Lines of Context: