[MERGE] make topo_sorting of get_ancestry optional

[Aaron Bentley]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi all,

Topological sorts are relatively expensive operations.  They are showing
up in my profiling of "bzr bundle", for example.

Repository.get_ancestry automatically does a topological sort, but most
of its callers do not need topologically-sorted results.  In fact, quite
a few turn it into a set (which is necessarily unsorted).

This patch will...

1. add a topo_sort flag to Repository.get_ancestry (and its callees).

2. convert all relevant callers to pass topo_sort=False.

3. introduce Graph.iter_topo_sorted, which operates only on the
   specified revisions

4. fix a bug in tsort.TopoSorter that caused GraphCycleError to be
   raised if one of the parents of the specified revisions was not in
   the list of specified revisions.

5. update bundle.serializer._write_bundle to use Graph.iter_topo_sorted
   so that it can use topo_sort=False

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGefZW0F+nu1YWqI0RAh83AJ9oyTWTWru7NJSIqUVa7QrmxfV8KACfa8Yo
z369Dky/ej7qEGeRORsKiAM=
=WlY/
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: no-topo-kthxbye.patch
Type: text/x-patch
Size: 113796 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20070620/4de4a221/attachment-0001.bin