[MERGE] Fix dotted revnos for ghosts

[John Arbash Meinel]

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

In my recent work, I discovered a small bug in our existing merge_sort
numbering. Specifically, if you had a graph like:

 a d    1   0.1.1
 | |\   |     |   \
 b e f  2   0.1.2 0.2.1  # XXX: 0.3.1
 | |/   |     |   /
 c g    3   0.1.3
 |/     | /
 h i    4   0.3.1
 |/     | /
 j      5


(which we *do* have in bzr.dev).

Basically, you have multiple nodes that have no parents, and some of
those are branches which themselves have multiple branches.

The specific issue was that the code that numbered new roots was doing a
post-increment (0, branch++, 1), while the code that was doing child
branches was doing a pre-increment (base, ++branch, 1).

This changes them both to be pre-increment, and adds tests for the behavior.

With the old behavior, node 'f' would cause a pre-increment, jumping its
number to 0.3.1, but node 'i' would post-increment, and also get
numbered 0.3.1. I *think* this is actually what was failing with 'bzr
log -r 0.8.1', because there were 2 nodes that were actually labeled 0.8.1.

There is also 1 more bug in our current implementation, which has to do
with ghosts, but I haven't figured out what to do about it. It occurs
because we have 1 graph which references nodes which aren't present
(get_parent_map()) which we then filter to remove any references to
nodes outside of the graph. So if you have:

 NULL_REVISION
 | | |
 a b f
 |/  |
 c d g
 |/ /
 e /
 |/
 h

In this case 'd' is a pure ghost.
	get_parent_map('e') = {e:(d,)}
  but
	get_parent_map('d') = {}

In this case, 'd' will get removed from our graph entirely. Which means
that 'f' will get 0.2.1 instead of the correct 0.3.1.

I don't have a great answer for that one yet. Because merge_sort doesn't
like dangling references (if you end up with a dangling reference, it
raises an exception about a cycle in your graph).

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkibenkACgkQJdeBCYSNAAMyQQCgz7Ops51hpg4RYnTJbQ9OGvby
ym4An00Mt6XvDQX/TAEpuAxpIkmxUlMs
=Cbke
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: correct_ghost_revnos.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20080807/7ad65aed/attachment.diff