Rev 3537: Switch the lca_trees to be in 'find_merge_order'. in http://bzr.arbash-meinel.com/branches/bzr/1.7-dev/merge_lca_multi
John Arbash Meinel
john at arbash-meinel.com
Tue Jul 22 23:26:48 BST 2008
At http://bzr.arbash-meinel.com/branches/bzr/1.7-dev/merge_lca_multi
------------------------------------------------------------
revno: 3537
revision-id: john at arbash-meinel.com-20080722222542-r4so03343ba2me68
parent: john at arbash-meinel.com-20080722221021-j1b5fln4430q827r
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: merge_lca_multi
timestamp: Tue 2008-07-22 17:25:42 -0500
message:
Switch the lca_trees to be in 'find_merge_order'.
We don't *have* to use that order, but it means we guarantee the lca ordering,
rather than just guessing.
One alternative that would be a bit faster is just simple lexicographical ordering.
Also handle when one of the LCA trees doesn't have an entry.
-------------- next part --------------
=== modified file 'bzrlib/merge.py'
--- a/bzrlib/merge.py 2008-07-22 22:10:21 +0000
+++ b/bzrlib/merge.py 2008-07-22 22:25:42 +0000
@@ -378,7 +378,10 @@
interesting_revision_ids))
self._cached_trees.update(interesting_trees)
self.base_tree = interesting_trees.pop(self.base_rev_id)
- self._lca_trees = interesting_trees
+ sorted_lca_keys = self.revision_graph.find_merge_order(
+ revisions[0], lcas)
+ self._lca_trees = [interesting_trees[key]
+ for key in sorted_lca_keys]
else:
self.base_tree = self.revision_tree(self.base_rev_id)
self.base_is_ancestor = True
@@ -658,16 +661,18 @@
executable ((base, [exec, in, lcas]), exec_in_other, exec_in_this)
"""
result = []
- walker = _mod_tree.MultiWalker(self.other_tree,
- self._lca_trees.values())
+ # XXX: Do we want a better sort order than this?
+ walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
base_inventory = self.base_tree.inventory
this_inventory = self.this_tree.inventory
for path, file_id, other_ie, lca_values in walker.iter_all():
# Is this modified at all from any of the other trees?
last_rev = other_ie.revision
+ # I believe we can actually change this to see if last_rev is
+ # identical to *any* of the lca values.
for lca_path, ie in lca_values:
- if ie.revision != last_rev:
+ if ie is None or ie.revision != last_rev:
break
else: # Identical in all trees
continue
@@ -678,6 +683,9 @@
parent_id_changed = False
name_changed = False
for lca_path, ie in lca_values:
+ if ie is None:
+ kind_changed = parent_id_changed = name_changed = True
+ break
if ie.kind != other_kind:
kind_changed = True
if ie.parent_id != other_parent_id:
@@ -706,15 +714,26 @@
else:
this_parent_id = this_name = this_executable = None
+ lca_parent_ids = []
+ lca_names = []
+ lca_executable = []
+ for path, ie in lca_values:
+ if ie is None:
+ lca_parent_ids.append(None)
+ lca_names.append(None)
+ lca_executable.append(None)
+ else:
+ lca_parent_ids.append(ie.parent_id)
+ lca_names.append(ie.name)
+ lca_executable.append(ie.executable)
+
+ # If we have gotten this far, that means something has changed
result.append((file_id, True,
- ((base_parent_id,
- [ie.parent_id for path, ie in lca_values]),
+ ((base_parent_id, lca_parent_ids),
other_ie.parent_id, this_parent_id),
- ((base_name,
- [ie.name for path, ie in lca_values]),
+ ((base_name, lca_names),
other_ie.name, this_name),
- ((base_executable,
- [ie.executable for path, ie in lca_values]),
+ ((base_executable, lca_executable),
other_ie.executable, this_executable)
))
return result
=== modified file 'bzrlib/tests/test_merge.py'
--- a/bzrlib/tests/test_merge.py 2008-07-22 22:10:21 +0000
+++ b/bzrlib/tests/test_merge.py 2008-07-22 22:25:42 +0000
@@ -1166,7 +1166,8 @@
merger = self.make_Merger(self.setup_criss_cross_graph(), 'E-id')
self.assertEqual('A-id', merger.base_rev_id)
self.assertTrue(merger._is_criss_cross)
- self.assertEqual(['B-id', 'C-id'], sorted(merger._lca_trees.keys()))
+ self.assertEqual(['B-id', 'C-id'], [t.get_revision_id()
+ for t in merger._lca_trees])
def test_no_criss_cross_passed_to_merge_type(self):
class LCATreesMerger(LoggingMerger):
@@ -1182,7 +1183,8 @@
merger = self.make_Merger(self.setup_criss_cross_graph(), 'E-id')
merger.merge_type = _mod_merge.Merge3Merger
merge_obj = merger.make_merger()
- self.assertEqual(['B-id', 'C-id'], sorted(merge_obj._lca_trees.keys()))
+ self.assertEqual(['B-id', 'C-id'], [t.get_revision_id()
+ for t in merger._lca_trees])
def test_criss_cross_not_supported_merge_type(self):
class NoLCATreesMerger(LoggingMerger):
@@ -1227,7 +1229,8 @@
[('modify', ('a-id', 'a\nB\nb\nC\nc\n'))])
merge_obj = self.make_merge_obj(builder, 'E-id')
- self.assertEqual(['B-id', 'C-id'], sorted(merge_obj._lca_trees.keys()))
+ self.assertEqual(['B-id', 'C-id'], [t.get_revision_id()
+ for t in merge_obj._lca_trees])
self.assertEqual('A-id', merge_obj.base_tree.get_revision_id())
entries = list(merge_obj._entries_lca())
@@ -1268,7 +1271,8 @@
builder.build_snapshot('F-id', ['D-id', 'E-id'], [])
merge_obj = self.make_merge_obj(builder, 'G-id')
- self.assertEqual(['D-id', 'E-id'], sorted(merge_obj._lca_trees.keys()))
+ self.assertEqual(['D-id', 'E-id'], [t.get_revision_id()
+ for t in merge_obj._lca_trees])
self.assertEqual('A-id', merge_obj.base_tree.get_revision_id())
entries = list(merge_obj._entries_lca())
root_id = 'a-root-id'
@@ -1283,17 +1287,18 @@
builder.build_snapshot('A-id', None,
[('add', (u'', 'a-root-id', 'directory', None)),
('add', (u'a', 'a-id', 'file', 'a\nb\nc\n'))])
+ builder.build_snapshot('B-id', ['A-id'],
+ [('modify', ('a-id', 'a\nB\nb\nc\n'))])
builder.build_snapshot('C-id', ['A-id'],
[('modify', ('a-id', 'a\nb\nC\nc\n'))])
- builder.build_snapshot('B-id', ['A-id'],
- [('modify', ('a-id', 'a\nB\nb\nc\n'))])
builder.build_snapshot('E-id', ['C-id', 'B-id'],
[('modify', ('a-id', 'a\nB\nb\nC\nc\nE\n'))])
builder.build_snapshot('D-id', ['B-id', 'C-id'],
[('unversion', 'a-id')])
merge_obj = self.make_merge_obj(builder, 'E-id')
- self.assertEqual(['B-id', 'C-id'], sorted(merge_obj._lca_trees.keys()))
+ self.assertEqual(['B-id', 'C-id'], [t.get_revision_id()
+ for t in merge_obj._lca_trees])
self.assertEqual('A-id', merge_obj.base_tree.get_revision_id())
entries = list(merge_obj._entries_lca())
@@ -1304,6 +1309,30 @@
((False, [False, False]), False, None)),
], entries)
+ def test_not_in_one_lca(self):
+ builder = self.get_builder()
+ builder.build_snapshot('A-id', None,
+ [('add', (u'', 'a-root-id', 'directory', None))])
+ builder.build_snapshot('B-id', ['A-id'], [])
+ builder.build_snapshot('C-id', ['A-id'],
+ [('add', (u'a', 'a-id', 'file', 'a\nb\nc\n'))])
+ builder.build_snapshot('E-id', ['C-id', 'B-id'], [])
+ builder.build_snapshot('D-id', ['B-id', 'C-id'],
+ [('add', (u'a', 'a-id', 'file', 'a\nb\nc\n'))])
+ merge_obj = self.make_merge_obj(builder, 'E-id')
+
+ self.assertEqual(['B-id', 'C-id'], [t.get_revision_id()
+ for t in merge_obj._lca_trees])
+ self.assertEqual('A-id', merge_obj.base_tree.get_revision_id())
+
+ entries = list(merge_obj._entries_lca())
+ root_id = 'a-root-id'
+ self.assertEqual([('a-id', True,
+ ((None, [None, root_id]), root_id, root_id),
+ ((None, [None, u'a']), u'a', u'a'),
+ ((None, [None, False]), False, False)),
+ ], entries)
+
# TODO: cases to test
# simple criss-cross LCAS identical, BASE different
# x-x changed from BASE but identical for all LCAs and tips
@@ -1311,3 +1340,4 @@
# x-x OTHER deletes the file
# x-x OTHER introduces the file
# x-x LCAs differ, one in ancestry of other for a given file
+ # x-x file missing in LCA
More information about the bazaar-commits
mailing list