Rev 3614: Fix the merge_sort code so that it properly increments. in http://bzr.arbash-meinel.com/branches/bzr/1.7-dev/correct_ghost_revnos

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/1.7-dev/correct_ghost_revnos

------------------------------------------------------------
revno: 3614
revision-id: john at arbash-meinel.com-20080807222648-ako39zeldqibnk40
parent: pqm at pqm.ubuntu.com-20080807005717-qxnuq9je71bt9tcs
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: correct_ghost_revnos
timestamp: Thu 2008-08-07 17:26:48 -0500
message:
  Fix the merge_sort code so that it properly increments.
  We had a small bug where if you had branches descend from new
  roots, as well as sub-branches within them, the branch counter
  would skip, and then repeat itself. (the root was a post-increment,
  while sub-branches were pre-increment.)
  This changes both to be pre-increment.
-------------- next part --------------
=== modified file 'bzrlib/tests/test_tsort.py'
--- a/bzrlib/tests/test_tsort.py	2008-07-09 13:36:48 +0000
+++ b/bzrlib/tests/test_tsort.py	2008-08-07 22:26:48 +0000
@@ -98,6 +98,13 @@
     def assertSortAndIterate(self, graph, branch_tip, result_list,
             generate_revno, mainline_revisions=None):
         """Check that merge based sorting and iter_topo_order on graph works."""
+        value = merge_sort(graph, branch_tip,
+                           mainline_revisions=mainline_revisions,
+                           generate_revno=generate_revno)
+        if result_list != value:
+            import pprint
+            self.assertEqualDiff(pprint.pformat(result_list),
+                                 pprint.pformat(value))
         self.assertEquals(result_list,
             merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions,
                 generate_revno=generate_revno))
@@ -605,3 +612,62 @@
              ],
             True
             )
+
+    def test_roots_and_sub_branches_versus_ghosts(self):
+        """Extra roots and their mini branches use the same numbering.
+
+        All of them use the 0-node numbering.
+        """
+        #       A D   K
+        #       | |\  |\
+        #       B E F L M
+        #       | |/  |/
+        #       C G   N
+        #       |/    |\
+        #       H I   O P
+        #       |/    |/
+        #       J     Q
+        #       |.---'
+        #       R
+        self.assertSortAndIterate(
+            {'A': [],
+             'B': ['A'],
+             'C': ['B'],
+             'D': [],
+             'E': ['D'],
+             'F': ['D'],
+             'G': ['E', 'F'],
+             'H': ['C', 'G'],
+             'I': [],
+             'J': ['H', 'I'],
+             'K': [],
+             'L': ['K'],
+             'M': ['K'],
+             'N': ['L', 'M'],
+             'O': ['N'],
+             'P': ['N'],
+             'Q': ['O', 'P'],
+             'R': ['J', 'Q'],
+            }.items(),
+            'R',
+            [( 0, 'R', 0, (6,), False),
+             ( 1, 'Q', 1, (0,4,5), False),
+             ( 2, 'P', 2, (0,6,1), True),
+             ( 3, 'O', 1, (0,4,4), False),
+             ( 4, 'N', 1, (0,4,3), False),
+             ( 5, 'M', 2, (0,5,1), True),
+             ( 6, 'L', 1, (0,4,2), False),
+             ( 7, 'K', 1, (0,4,1), True),
+             ( 8, 'J', 0, (5,), False),
+             ( 9, 'I', 1, (0,3,1), True),
+             (10, 'H', 0, (4,), False),
+             (11, 'G', 1, (0,1,3), False),
+             (12, 'F', 2, (0,2,1), True),
+             (13, 'E', 1, (0,1,2), False),
+             (14, 'D', 1, (0,1,1), True),
+             (15, 'C', 0, (3,), False),
+             (16, 'B', 0, (2,), False),
+             (17, 'A', 0, (1,), True),
+             ],
+            True
+            )

=== modified file 'bzrlib/tsort.py'
--- a/bzrlib/tsort.py	2008-07-09 13:36:48 +0000
+++ b/bzrlib/tsort.py	2008-08-07 22:26:48 +0000
@@ -516,12 +516,12 @@
                     revno = parent_revno[:-1] + (parent_revno[-1] + 1,)
             else:
                 # no parents, use the root sequence
-                root_count = revno_to_branch_count.get(0, 0)
+                root_count = revno_to_branch_count.get(0, -1)
+                root_count += 1
                 if root_count:
                     revno = (0, root_count, 1)
                 else:
                     revno = (1,)
-                root_count += 1
                 revno_to_branch_count[0] = root_count
 
             # store the revno for this node for future reference