Rev 4620: (jam) Tweak how merge_sort handles right parents when the left parent in file:///home/pqm/archives/thelove/bzr/%2Btrunk/
Canonical.com Patch Queue Manager
pqm at pqm.ubuntu.com
Mon Aug 17 22:06:58 BST 2009
At file:///home/pqm/archives/thelove/bzr/%2Btrunk/
------------------------------------------------------------
revno: 4620 [merge]
revision-id: pqm at pqm.ubuntu.com-20090817210655-w8d1xxic3wi6gs61
parent: pqm at pqm.ubuntu.com-20090817181818-6ks7pxgiwpqvsd3l
parent: john at arbash-meinel.com-20090817193129-0512zwglhybx6eiq
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Mon 2009-08-17 22:06:55 +0100
message:
(jam) Tweak how merge_sort handles right parents when the left parent
is already processed.
modified:
bzrlib/tests/test_log.py testlog.py-20050728115707-1a514809d7d49309
bzrlib/tests/test_tsort.py testtsort.py-20051025073946-27da871c394d5be4
bzrlib/tsort.py tsort.py-20051025073946-7808f6aaf7d07208
=== modified file 'bzrlib/tests/test_log.py'
--- a/bzrlib/tests/test_log.py 2009-05-08 13:39:32 +0000
+++ b/bzrlib/tests/test_log.py 2009-08-17 19:31:29 +0000
@@ -1197,28 +1197,35 @@
# 4a: 3.1.1
return mainline_revs, rev_nos, wt
- def make_tree_with_many_merges(self):
+ def make_branch_with_many_merges(self):
"""Create a tree with well-known revision ids"""
- wt = self.make_branch_and_tree('tree1')
- self.build_tree_contents([('tree1/f', '1\n')])
- wt.add(['f'], ['f-id'])
- wt.commit('commit one', rev_id='1')
- wt.commit('commit two', rev_id='2')
-
- tree3 = wt.bzrdir.sprout('tree3').open_workingtree()
- self.build_tree_contents([('tree3/f', '1\n2\n3a\n')])
- tree3.commit('commit three a', rev_id='3a')
-
- tree2 = wt.bzrdir.sprout('tree2').open_workingtree()
- tree2.merge_from_branch(tree3.branch)
- tree2.commit('commit three b', rev_id='3b')
-
- wt.merge_from_branch(tree2.branch)
- wt.commit('commit three c', rev_id='3c')
- tree2.commit('four-a', rev_id='4a')
-
- wt.merge_from_branch(tree2.branch)
- wt.commit('four-b', rev_id='4b')
+ builder = self.make_branch_builder('tree1')
+ builder.start_series()
+ builder.build_snapshot('1', None, [
+ ('add', ('', 'TREE_ROOT', 'directory', '')),
+ ('add', ('f', 'f-id', 'file', '1\n'))])
+ builder.build_snapshot('2', ['1'], [])
+ builder.build_snapshot('3a', ['2'], [
+ ('modify', ('f-id', '1\n2\n3a\n'))])
+ builder.build_snapshot('3b', ['2', '3a'], [
+ ('modify', ('f-id', '1\n2\n3a\n'))])
+ builder.build_snapshot('3c', ['2', '3b'], [
+ ('modify', ('f-id', '1\n2\n3a\n'))])
+ builder.build_snapshot('4a', ['3b'], [])
+ builder.build_snapshot('4b', ['3c', '4a'], [])
+ builder.finish_series()
+
+ # 1
+ # |
+ # 2-.
+ # |\ \
+ # | | 3a
+ # | |/
+ # | 3b
+ # |/|
+ # 3c4a
+ # |/
+ # 4b
mainline_revs = [None, '1', '2', '3c', '4b']
rev_nos = {'1':1, '2':2, '3c': 3, '4b':4}
@@ -1231,7 +1238,7 @@
'4a': '2.2.2', # second commit tree 2
'4b': '4', # merges 4a to main
}
- return mainline_revs, rev_nos, wt
+ return mainline_revs, rev_nos, builder.get_branch()
def test_get_view_revisions_forward(self):
"""Test the get_view_revisions method"""
@@ -1297,17 +1304,17 @@
def test_get_view_revisions_merge2(self):
"""Test get_view_revisions when there are merges"""
- mainline_revs, rev_nos, wt = self.make_tree_with_many_merges()
- wt.lock_read()
- self.addCleanup(wt.unlock)
+ mainline_revs, rev_nos, b = self.make_branch_with_many_merges()
+ b.lock_read()
+ self.addCleanup(b.unlock)
revisions = list(log.get_view_revisions(
- mainline_revs, rev_nos, wt.branch, 'forward'))
+ mainline_revs, rev_nos, b, 'forward'))
expected = [('1', '1', 0), ('2', '2', 0), ('3c', '3', 0),
- ('3a', '2.1.1', 1), ('3b', '2.2.1', 1), ('4b', '4', 0),
+ ('3b', '2.2.1', 1), ('3a', '2.1.1', 2), ('4b', '4', 0),
('4a', '2.2.2', 1)]
self.assertEqual(expected, revisions)
revisions = list(log.get_view_revisions(
- mainline_revs, rev_nos, wt.branch, 'forward',
+ mainline_revs, rev_nos, b, 'forward',
include_merges=False))
self.assertEqual([('1', '1', 0), ('2', '2', 0), ('3c', '3', 0),
('4b', '4', 0)],
@@ -1315,9 +1322,9 @@
def test_file_id_for_range(self):
- mainline_revs, rev_nos, wt = self.make_tree_with_many_merges()
- wt.lock_read()
- self.addCleanup(wt.unlock)
+ mainline_revs, rev_nos, b = self.make_branch_with_many_merges()
+ b.lock_read()
+ self.addCleanup(b.unlock)
def rev_from_rev_id(revid, branch):
revspec = revisionspec.RevisionSpec.from_string('revid:%s' % revid)
@@ -1325,7 +1332,7 @@
def view_revs(start_rev, end_rev, file_id, direction):
revs = log.calculate_view_revisions(
- wt.branch,
+ b,
start_rev, # start_revision
end_rev, # end_revision
direction, # direction
@@ -1334,12 +1341,12 @@
)
return revs
- rev_3a = rev_from_rev_id('3a', wt.branch)
- rev_4b = rev_from_rev_id('4b', wt.branch)
- self.assertEqual([('3c', '3', 0), ('3a', '2.1.1', 1)],
+ rev_3a = rev_from_rev_id('3a', b)
+ rev_4b = rev_from_rev_id('4b', b)
+ self.assertEqual([('3c', '3', 0), ('3b', '2.2.1', 1), ('3a', '2.1.1', 2)],
view_revs(rev_3a, rev_4b, 'f-id', 'reverse'))
# Note: 3c still appears before 3a here because of depth-based sorting
- self.assertEqual([('3c', '3', 0), ('3a', '2.1.1', 1)],
+ self.assertEqual([('3c', '3', 0), ('3b', '2.2.1', 1), ('3a', '2.1.1', 2)],
view_revs(rev_3a, rev_4b, 'f-id', 'forward'))
=== modified file 'bzrlib/tests/test_tsort.py'
--- a/bzrlib/tests/test_tsort.py 2009-03-23 14:59:43 +0000
+++ b/bzrlib/tests/test_tsort.py 2009-08-17 15:26:18 +0000
@@ -211,7 +211,7 @@
self.assertSortAndIterate(graph, 'F',
[(0, 'F', 0, (3,), False),
(1, 'D', 1, (2,2,1), False),
- (2, 'C', 1, (2,1,1), True), # XXX: Shouldn't it be merge_depth=2?
+ (2, 'C', 2, (2,1,1), True),
(3, 'B', 0, (2,), False),
(4, 'A', 0, (1,), True),
], True)
=== modified file 'bzrlib/tsort.py'
--- a/bzrlib/tsort.py 2009-03-23 14:59:43 +0000
+++ b/bzrlib/tsort.py 2009-08-17 15:26:18 +0000
@@ -545,6 +545,8 @@
if not left_subtree_pushed_stack[-1]:
# recurse depth first into the primary parent
next_node_name = pending_parents_stack[-1].pop(0)
+ is_left_subtree = True
+ left_subtree_pushed_stack[-1] = True
else:
# place any merges in right-to-left order for scheduling
# which gives us left-to-right order after we reverse
@@ -554,6 +556,7 @@
# display nicely (you get smaller trees at the top
# of the combined merge).
next_node_name = pending_parents_stack[-1].pop()
+ is_left_subtree = False
if next_node_name in completed_node_names:
# this parent was completed by a child on the
# call stack. skip it.
@@ -570,12 +573,11 @@
# this indicates a cycle.
raise errors.GraphCycleError(node_name_stack)
next_merge_depth = 0
- if left_subtree_pushed_stack[-1]:
+ if is_left_subtree:
# a new child branch from name_stack[-1]
+ next_merge_depth = 0
+ else:
next_merge_depth = 1
- else:
- next_merge_depth = 0
- left_subtree_pushed_stack[-1] = True
next_merge_depth = (
node_merge_depth_stack[-1] + next_merge_depth)
push_node(
More information about the bazaar-commits
mailing list