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
1=== modified file 'bzrlib/tests/test_log.py'
2--- bzrlib/tests/test_log.py 2009-05-08 13:39:32 +0000
3+++ bzrlib/tests/test_log.py 2009-08-17 20:35:26 +0000
4@@ -1197,28 +1197,35 @@
5 # 4a: 3.1.1
6 return mainline_revs, rev_nos, wt
7
8- def make_tree_with_many_merges(self):
9+ def make_branch_with_many_merges(self):
10 """Create a tree with well-known revision ids"""
11- wt = self.make_branch_and_tree('tree1')
12- self.build_tree_contents([('tree1/f', '1\n')])
13- wt.add(['f'], ['f-id'])
14- wt.commit('commit one', rev_id='1')
15- wt.commit('commit two', rev_id='2')
16-
17- tree3 = wt.bzrdir.sprout('tree3').open_workingtree()
18- self.build_tree_contents([('tree3/f', '1\n2\n3a\n')])
19- tree3.commit('commit three a', rev_id='3a')
20-
21- tree2 = wt.bzrdir.sprout('tree2').open_workingtree()
22- tree2.merge_from_branch(tree3.branch)
23- tree2.commit('commit three b', rev_id='3b')
24-
25- wt.merge_from_branch(tree2.branch)
26- wt.commit('commit three c', rev_id='3c')
27- tree2.commit('four-a', rev_id='4a')
28-
29- wt.merge_from_branch(tree2.branch)
30- wt.commit('four-b', rev_id='4b')
31+ builder = self.make_branch_builder('tree1')
32+ builder.start_series()
33+ builder.build_snapshot('1', None, [
34+ ('add', ('', 'TREE_ROOT', 'directory', '')),
35+ ('add', ('f', 'f-id', 'file', '1\n'))])
36+ builder.build_snapshot('2', ['1'], [])
37+ builder.build_snapshot('3a', ['2'], [
38+ ('modify', ('f-id', '1\n2\n3a\n'))])
39+ builder.build_snapshot('3b', ['2', '3a'], [
40+ ('modify', ('f-id', '1\n2\n3a\n'))])
41+ builder.build_snapshot('3c', ['2', '3b'], [
42+ ('modify', ('f-id', '1\n2\n3a\n'))])
43+ builder.build_snapshot('4a', ['3b'], [])
44+ builder.build_snapshot('4b', ['3c', '4a'], [])
45+ builder.finish_series()
46+
47+ # 1
48+ # |
49+ # 2-.
50+ # |\ \
51+ # | | 3a
52+ # | |/
53+ # | 3b
54+ # |/|
55+ # 3c4a
56+ # |/
57+ # 4b
58
59 mainline_revs = [None, '1', '2', '3c', '4b']
60 rev_nos = {'1':1, '2':2, '3c': 3, '4b':4}
61@@ -1231,7 +1238,7 @@
62 '4a': '2.2.2', # second commit tree 2
63 '4b': '4', # merges 4a to main
64 }
65- return mainline_revs, rev_nos, wt
66+ return mainline_revs, rev_nos, builder.get_branch()
67
68 def test_get_view_revisions_forward(self):
69 """Test the get_view_revisions method"""
70@@ -1297,17 +1304,17 @@
71
72 def test_get_view_revisions_merge2(self):
73 """Test get_view_revisions when there are merges"""
74- mainline_revs, rev_nos, wt = self.make_tree_with_many_merges()
75- wt.lock_read()
76- self.addCleanup(wt.unlock)
77+ mainline_revs, rev_nos, b = self.make_branch_with_many_merges()
78+ b.lock_read()
79+ self.addCleanup(b.unlock)
80 revisions = list(log.get_view_revisions(
81- mainline_revs, rev_nos, wt.branch, 'forward'))
82+ mainline_revs, rev_nos, b, 'forward'))
83 expected = [('1', '1', 0), ('2', '2', 0), ('3c', '3', 0),
84- ('3a', '2.1.1', 1), ('3b', '2.2.1', 1), ('4b', '4', 0),
85+ ('3b', '2.2.1', 1), ('3a', '2.1.1', 2), ('4b', '4', 0),
86 ('4a', '2.2.2', 1)]
87 self.assertEqual(expected, revisions)
88 revisions = list(log.get_view_revisions(
89- mainline_revs, rev_nos, wt.branch, 'forward',
90+ mainline_revs, rev_nos, b, 'forward',
91 include_merges=False))
92 self.assertEqual([('1', '1', 0), ('2', '2', 0), ('3c', '3', 0),
93 ('4b', '4', 0)],
94@@ -1315,9 +1322,9 @@
95
96
97 def test_file_id_for_range(self):
98- mainline_revs, rev_nos, wt = self.make_tree_with_many_merges()
99- wt.lock_read()
100- self.addCleanup(wt.unlock)
101+ mainline_revs, rev_nos, b = self.make_branch_with_many_merges()
102+ b.lock_read()
103+ self.addCleanup(b.unlock)
104
105 def rev_from_rev_id(revid, branch):
106 revspec = revisionspec.RevisionSpec.from_string('revid:%s' % revid)
107@@ -1325,7 +1332,7 @@
108
109 def view_revs(start_rev, end_rev, file_id, direction):
110 revs = log.calculate_view_revisions(
111- wt.branch,
112+ b,
113 start_rev, # start_revision
114 end_rev, # end_revision
115 direction, # direction
116@@ -1334,12 +1341,12 @@
117 )
118 return revs
119
120- rev_3a = rev_from_rev_id('3a', wt.branch)
121- rev_4b = rev_from_rev_id('4b', wt.branch)
122- self.assertEqual([('3c', '3', 0), ('3a', '2.1.1', 1)],
123+ rev_3a = rev_from_rev_id('3a', b)
124+ rev_4b = rev_from_rev_id('4b', b)
125+ self.assertEqual([('3c', '3', 0), ('3b', '2.2.1', 1), ('3a', '2.1.1', 2)],
126 view_revs(rev_3a, rev_4b, 'f-id', 'reverse'))
127 # Note: 3c still appears before 3a here because of depth-based sorting
128- self.assertEqual([('3c', '3', 0), ('3a', '2.1.1', 1)],
129+ self.assertEqual([('3c', '3', 0), ('3b', '2.2.1', 1), ('3a', '2.1.1', 2)],
130 view_revs(rev_3a, rev_4b, 'f-id', 'forward'))
131
132
133
134=== modified file 'bzrlib/tests/test_tsort.py'
135--- bzrlib/tests/test_tsort.py 2009-03-23 14:59:43 +0000
136+++ bzrlib/tests/test_tsort.py 2009-08-17 20:35:26 +0000
137@@ -211,7 +211,7 @@
138 self.assertSortAndIterate(graph, 'F',
139 [(0, 'F', 0, (3,), False),
140 (1, 'D', 1, (2,2,1), False),
141- (2, 'C', 1, (2,1,1), True), # XXX: Shouldn't it be merge_depth=2?
142+ (2, 'C', 2, (2,1,1), True),
143 (3, 'B', 0, (2,), False),
144 (4, 'A', 0, (1,), True),
145 ], True)
146
147=== modified file 'bzrlib/tsort.py'
148--- bzrlib/tsort.py 2009-03-23 14:59:43 +0000
149+++ bzrlib/tsort.py 2009-08-17 20:35:26 +0000
150@@ -545,6 +545,8 @@
151 if not left_subtree_pushed_stack[-1]:
152 # recurse depth first into the primary parent
153 next_node_name = pending_parents_stack[-1].pop(0)
154+ is_left_subtree = True
155+ left_subtree_pushed_stack[-1] = True
156 else:
157 # place any merges in right-to-left order for scheduling
158 # which gives us left-to-right order after we reverse
159@@ -554,6 +556,7 @@
160 # display nicely (you get smaller trees at the top
161 # of the combined merge).
162 next_node_name = pending_parents_stack[-1].pop()
163+ is_left_subtree = False
164 if next_node_name in completed_node_names:
165 # this parent was completed by a child on the
166 # call stack. skip it.
167@@ -570,12 +573,11 @@
168 # this indicates a cycle.
169 raise errors.GraphCycleError(node_name_stack)
170 next_merge_depth = 0
171- if left_subtree_pushed_stack[-1]:
172+ if is_left_subtree:
173 # a new child branch from name_stack[-1]
174+ next_merge_depth = 0
175+ else:
176 next_merge_depth = 1
177- else:
178- next_merge_depth = 0
179- left_subtree_pushed_stack[-1] = True
180 next_merge_depth = (
181 node_merge_depth_stack[-1] + next_merge_depth)
182 push_node(