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

[John Arbash Meinel]

Robert Collins wrote:
> 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...
> 

How is this specific patch different than the other patches which I've
already reviewed. If it is just binding them together, you can piggy
back of the +1 I already gave you. If it is more extensively different,
then wait till Aaron or Martin review it.

John
=:->


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 254 bytes
Desc: OpenPGP digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060228/9450dfa0/attachment.pgp