[MERGE] faster tsort, ancestry corruption detection, reconcile to fix it, and fetch to not trigger said corruption

[Robert Collins]

This is a bit of a rollup merge request, because these things are quite
closely connected.

First this is a replacement for tsort which generates different
ordering, but is still topologically sorted. The change is from breadth
first output to depth first: Rather than emitting the graph {0:[],
1:[0], 2:[0], 3:[1]} as [0, 1, 2, 3] it may now emit it as any one of
[0, 1, 3, 2] or [0, 2, 1, 3] or [0, 1, 2, 3]. Its sqrt(graph nodes)
faster though - < 0.5 seconds (most granular I've got - it feels instant
though) on the largest graphs I've had at hand to test with - the old
tsort takes 9 seconds on those graphs (5488 revisions).

Secondly, it teaches repository to check using a relatively cheap test
when a revision that is accessed has less ancestry data that is actually
available. If this test fails a CorruptRepository exception is raised
telling users to run bzr reconcile.

Thirdly it adds a 'bzr reconcile' command that will scan for and correct
this ancestry data, garbage collecting inventories (stale inventories
without revisions would return incorrectly complete ancestry) and
filling out parents when the parent is now available(so ghosts now
become visible to get_ancestry).

Lastly, fetch is altered so that fetching from a repository will fill in
all ghosts that can be filled in, so that the sequence 'bzr check; bzr
fetch; bzr check' never results in an error.

ui wise I can change the command name easily if theres a better. And we
*might* want to make 'fetch' -from- a corrupt repository ignore the
corruption or some such, but I'm in favour of getting the data out there
consistent...


$ wc -l fast-reconcile-done.patch 
1386 fast-reconcile-done.patch
$ diffstat fast-reconcile-done.patch 
 builtins.py                                                   |   26 +
 commit.py                                                     |   44 --
 errors.py                                                     |    8 
 fetch.py                                                      |   26 -
 progress.py                                                   |    5 
 reconcile.py                                                  |  184 ++++++++++
 repository.py                                                 |   90 ++++
 store/weave.py                                                |    2 
 tests/__init__.py                                             |    1 
 tests/blackbox/__init__.py                                    |   21 +
 tests/blackbox/test_reconcile.py                              |   63 +++
 tests/blackbox/test_upgrade.py                                |   19 -
 tests/interrepository_implementations/test_interrepository.py |   43 ++
 tests/repository_implementations/__init__.py                  |    1 
 tests/repository_implementations/test_fileid_involved.py      |    1 
 tests/repository_implementations/test_reconcile.py            |  177 +++++++++
 tests/repository_implementations/test_repository.py           |   40 ++
 tests/test_errors.py                                          |    8 
 tests/test_reconcile.py                                       |   47 ++
 tests/test_tsort.py                                           |   75 ++--
 tsort.py                                                      |  167 +++++++--
 weave.py                                                      |    4 
 22 files changed, 925 insertions(+), 127 deletions(-)



Rob


-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fast-reconcile-done.patch
Type: text/x-patch
Size: 58836 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060228/66190f95/attachment.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 191 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060228/66190f95/attachment.pgp