Bazaar

Merge lp:~jameinel/bzr/2.0b1-merge-sort into lp:~bzr/bzr/trunk-old

  1. 2.0b1-merge-sort
  2. Merge into trunk-old
Proposed by John A Meinel
Status: Merged
Merged at revision: not available
Proposed branch: lp:~jameinel/bzr/2.0b1-merge-sort
Merge into: lp:~bzr/bzr/trunk-old
Diff against target: 182 lines
To merge this branch: bzr merge lp:~jameinel/bzr/2.0b1-merge-sort
Reviewer Review Type Date Requested Status
Vincent Ladeuil Approve
Review via email: mp+10253@code.launchpad.net
To post a comment you must log in.
Revision history for this message
John A Meinel (jameinel) wrote :

This is a small tweak to how merge_sort counts 'merge_depth'. I think this is actually what we want. I believe Gary van der Merwe had noticed this in the past while working on qlog.

Basically the situation is (time going down):

 A
 |
 B-.
 |\ \
 | | C
 | |/
 | D
 |/
 F

The question is whether this should be logged as (time going up for log):

 F
   D
   C
 B
 A

or

 F
   D
     C
 B
 A

As C is a right-hand parent of D, I think it makes sense to increase its merge depth, even though the left-hand parent of D is a mainline ancestor.

Looking at the fix, I think it was just a matter of not paying attention to the:

                    if next_node_name in completed_node_names:
                        # this parent was completed by a child on the
                        # call stack. skip it.
                        continue

continue statement between when we pull off the left-hand parent and when we decide that the current node is a left-hand and thus doesn't increment the merge depth.

I'm working on an optimized Pyrex version, and so came across this.

Revision history for this message
Vincent Ladeuil (vila) :
review: Approve

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
=== modified file 'bzrlib/tests/test_log.py'
--- bzrlib/tests/test_log.py 2009-05-08 13:39:32 +0000
+++ bzrlib/tests/test_log.py 2009-08-17 20:35:26 +0000
@@ -1197,28 +1197,35 @@
1197 # 4a: 3.1.11197 # 4a: 3.1.1
1198 return mainline_revs, rev_nos, wt1198 return mainline_revs, rev_nos, wt
11991199
1200 def make_tree_with_many_merges(self):1200 def make_branch_with_many_merges(self):
1201 """Create a tree with well-known revision ids"""1201 """Create a tree with well-known revision ids"""
1202 wt = self.make_branch_and_tree('tree1')1202 builder = self.make_branch_builder('tree1')
1203 self.build_tree_contents([('tree1/f', '1\n')])1203 builder.start_series()
1204 wt.add(['f'], ['f-id'])1204 builder.build_snapshot('1', None, [
1205 wt.commit('commit one', rev_id='1')1205 ('add', ('', 'TREE_ROOT', 'directory', '')),
1206 wt.commit('commit two', rev_id='2')1206 ('add', ('f', 'f-id', 'file', '1\n'))])
12071207 builder.build_snapshot('2', ['1'], [])
1208 tree3 = wt.bzrdir.sprout('tree3').open_workingtree()1208 builder.build_snapshot('3a', ['2'], [
1209 self.build_tree_contents([('tree3/f', '1\n2\n3a\n')])1209 ('modify', ('f-id', '1\n2\n3a\n'))])
1210 tree3.commit('commit three a', rev_id='3a')1210 builder.build_snapshot('3b', ['2', '3a'], [
12111211 ('modify', ('f-id', '1\n2\n3a\n'))])
1212 tree2 = wt.bzrdir.sprout('tree2').open_workingtree()1212 builder.build_snapshot('3c', ['2', '3b'], [
1213 tree2.merge_from_branch(tree3.branch)1213 ('modify', ('f-id', '1\n2\n3a\n'))])
1214 tree2.commit('commit three b', rev_id='3b')1214 builder.build_snapshot('4a', ['3b'], [])
12151215 builder.build_snapshot('4b', ['3c', '4a'], [])
1216 wt.merge_from_branch(tree2.branch)1216 builder.finish_series()
1217 wt.commit('commit three c', rev_id='3c')1217
1218 tree2.commit('four-a', rev_id='4a')1218 # 1
12191219 # |
1220 wt.merge_from_branch(tree2.branch)1220 # 2-.
1221 wt.commit('four-b', rev_id='4b')1221 # |\ \
1222 # | | 3a
1223 # | |/
1224 # | 3b
1225 # |/|
1226 # 3c4a
1227 # |/
1228 # 4b
12221229
1223 mainline_revs = [None, '1', '2', '3c', '4b']1230 mainline_revs = [None, '1', '2', '3c', '4b']
1224 rev_nos = {'1':1, '2':2, '3c': 3, '4b':4}1231 rev_nos = {'1':1, '2':2, '3c': 3, '4b':4}
@@ -1231,7 +1238,7 @@
1231 '4a': '2.2.2', # second commit tree 21238 '4a': '2.2.2', # second commit tree 2
1232 '4b': '4', # merges 4a to main1239 '4b': '4', # merges 4a to main
1233 }1240 }
1234 return mainline_revs, rev_nos, wt1241 return mainline_revs, rev_nos, builder.get_branch()
12351242
1236 def test_get_view_revisions_forward(self):1243 def test_get_view_revisions_forward(self):
1237 """Test the get_view_revisions method"""1244 """Test the get_view_revisions method"""
@@ -1297,17 +1304,17 @@
12971304
1298 def test_get_view_revisions_merge2(self):1305 def test_get_view_revisions_merge2(self):
1299 """Test get_view_revisions when there are merges"""1306 """Test get_view_revisions when there are merges"""
1300 mainline_revs, rev_nos, wt = self.make_tree_with_many_merges()1307 mainline_revs, rev_nos, b = self.make_branch_with_many_merges()
1301 wt.lock_read()1308 b.lock_read()
1302 self.addCleanup(wt.unlock)1309 self.addCleanup(b.unlock)
1303 revisions = list(log.get_view_revisions(1310 revisions = list(log.get_view_revisions(
1304 mainline_revs, rev_nos, wt.branch, 'forward'))1311 mainline_revs, rev_nos, b, 'forward'))
1305 expected = [('1', '1', 0), ('2', '2', 0), ('3c', '3', 0),1312 expected = [('1', '1', 0), ('2', '2', 0), ('3c', '3', 0),
1306 ('3a', '2.1.1', 1), ('3b', '2.2.1', 1), ('4b', '4', 0),1313 ('3b', '2.2.1', 1), ('3a', '2.1.1', 2), ('4b', '4', 0),
1307 ('4a', '2.2.2', 1)]1314 ('4a', '2.2.2', 1)]
1308 self.assertEqual(expected, revisions)1315 self.assertEqual(expected, revisions)
1309 revisions = list(log.get_view_revisions(1316 revisions = list(log.get_view_revisions(
1310 mainline_revs, rev_nos, wt.branch, 'forward',1317 mainline_revs, rev_nos, b, 'forward',
1311 include_merges=False))1318 include_merges=False))
1312 self.assertEqual([('1', '1', 0), ('2', '2', 0), ('3c', '3', 0),1319 self.assertEqual([('1', '1', 0), ('2', '2', 0), ('3c', '3', 0),
1313 ('4b', '4', 0)],1320 ('4b', '4', 0)],
@@ -1315,9 +1322,9 @@
13151322
13161323
1317 def test_file_id_for_range(self):1324 def test_file_id_for_range(self):
1318 mainline_revs, rev_nos, wt = self.make_tree_with_many_merges()1325 mainline_revs, rev_nos, b = self.make_branch_with_many_merges()
1319 wt.lock_read()1326 b.lock_read()
1320 self.addCleanup(wt.unlock)1327 self.addCleanup(b.unlock)
13211328
1322 def rev_from_rev_id(revid, branch):1329 def rev_from_rev_id(revid, branch):
1323 revspec = revisionspec.RevisionSpec.from_string('revid:%s' % revid)1330 revspec = revisionspec.RevisionSpec.from_string('revid:%s' % revid)
@@ -1325,7 +1332,7 @@
13251332
1326 def view_revs(start_rev, end_rev, file_id, direction):1333 def view_revs(start_rev, end_rev, file_id, direction):
1327 revs = log.calculate_view_revisions(1334 revs = log.calculate_view_revisions(
1328 wt.branch,1335 b,
1329 start_rev, # start_revision1336 start_rev, # start_revision
1330 end_rev, # end_revision1337 end_rev, # end_revision
1331 direction, # direction1338 direction, # direction
@@ -1334,12 +1341,12 @@
1334 )1341 )
1335 return revs1342 return revs
13361343
1337 rev_3a = rev_from_rev_id('3a', wt.branch)1344 rev_3a = rev_from_rev_id('3a', b)
1338 rev_4b = rev_from_rev_id('4b', wt.branch)1345 rev_4b = rev_from_rev_id('4b', b)
1339 self.assertEqual([('3c', '3', 0), ('3a', '2.1.1', 1)],1346 self.assertEqual([('3c', '3', 0), ('3b', '2.2.1', 1), ('3a', '2.1.1', 2)],
1340 view_revs(rev_3a, rev_4b, 'f-id', 'reverse'))1347 view_revs(rev_3a, rev_4b, 'f-id', 'reverse'))
1341 # Note: 3c still appears before 3a here because of depth-based sorting1348 # Note: 3c still appears before 3a here because of depth-based sorting
1342 self.assertEqual([('3c', '3', 0), ('3a', '2.1.1', 1)],1349 self.assertEqual([('3c', '3', 0), ('3b', '2.2.1', 1), ('3a', '2.1.1', 2)],
1343 view_revs(rev_3a, rev_4b, 'f-id', 'forward'))1350 view_revs(rev_3a, rev_4b, 'f-id', 'forward'))
13441351
13451352
13461353
=== modified file 'bzrlib/tests/test_tsort.py'
--- bzrlib/tests/test_tsort.py 2009-03-23 14:59:43 +0000
+++ bzrlib/tests/test_tsort.py 2009-08-17 20:35:26 +0000
@@ -211,7 +211,7 @@
211 self.assertSortAndIterate(graph, 'F',211 self.assertSortAndIterate(graph, 'F',
212 [(0, 'F', 0, (3,), False),212 [(0, 'F', 0, (3,), False),
213 (1, 'D', 1, (2,2,1), False),213 (1, 'D', 1, (2,2,1), False),
214 (2, 'C', 1, (2,1,1), True), # XXX: Shouldn't it be merge_depth=2?214 (2, 'C', 2, (2,1,1), True),
215 (3, 'B', 0, (2,), False),215 (3, 'B', 0, (2,), False),
216 (4, 'A', 0, (1,), True),216 (4, 'A', 0, (1,), True),
217 ], True)217 ], True)
218218
=== modified file 'bzrlib/tsort.py'
--- bzrlib/tsort.py 2009-03-23 14:59:43 +0000
+++ bzrlib/tsort.py 2009-08-17 20:35:26 +0000
@@ -545,6 +545,8 @@
545 if not left_subtree_pushed_stack[-1]:545 if not left_subtree_pushed_stack[-1]:
546 # recurse depth first into the primary parent546 # recurse depth first into the primary parent
547 next_node_name = pending_parents_stack[-1].pop(0)547 next_node_name = pending_parents_stack[-1].pop(0)
548 is_left_subtree = True
549 left_subtree_pushed_stack[-1] = True
548 else:550 else:
549 # place any merges in right-to-left order for scheduling551 # place any merges in right-to-left order for scheduling
550 # which gives us left-to-right order after we reverse552 # which gives us left-to-right order after we reverse
@@ -554,6 +556,7 @@
554 # display nicely (you get smaller trees at the top556 # display nicely (you get smaller trees at the top
555 # of the combined merge).557 # of the combined merge).
556 next_node_name = pending_parents_stack[-1].pop()558 next_node_name = pending_parents_stack[-1].pop()
559 is_left_subtree = False
557 if next_node_name in completed_node_names:560 if next_node_name in completed_node_names:
558 # this parent was completed by a child on the561 # this parent was completed by a child on the
559 # call stack. skip it.562 # call stack. skip it.
@@ -570,12 +573,11 @@
570 # this indicates a cycle.573 # this indicates a cycle.
571 raise errors.GraphCycleError(node_name_stack)574 raise errors.GraphCycleError(node_name_stack)
572 next_merge_depth = 0575 next_merge_depth = 0
573 if left_subtree_pushed_stack[-1]:576 if is_left_subtree:
574 # a new child branch from name_stack[-1]577 # a new child branch from name_stack[-1]
578 next_merge_depth = 0
579 else:
575 next_merge_depth = 1580 next_merge_depth = 1
576 else:
577 next_merge_depth = 0
578 left_subtree_pushed_stack[-1] = True
579 next_merge_depth = (581 next_merge_depth = (
580 node_merge_depth_stack[-1] + next_merge_depth)582 node_merge_depth_stack[-1] + next_merge_depth)
581 push_node(583 push_node(