Rev 3513: Work on writing an LCA algorithm for working on file names, etc. in http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/merge3_per_file
John Arbash Meinel
john at arbash-meinel.com
Tue Jun 24 21:09:48 BST 2008
At http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/merge3_per_file
------------------------------------------------------------
revno: 3513
revision-id: john at arbash-meinel.com-20080624200945-qwlitl30s5c7fpnm
parent: john at arbash-meinel.com-20080624171624-mu83fk2x1mgj8k2q
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: merge3_per_file
timestamp: Tue 2008-06-24 15:09:45 -0500
message:
Work on writing an LCA algorithm for working on file names, etc.
This would replace the _entries3 work whenever there is a criss cross merge.
modified:
bzrlib/merge.py merge.py-20050513021216-953b65a438527106
-------------- next part --------------
=== modified file 'bzrlib/merge.py'
--- a/bzrlib/merge.py 2008-06-24 17:16:24 +0000
+++ b/bzrlib/merge.py 2008-06-24 20:09:45 +0000
@@ -94,6 +94,7 @@
self._base_is_ancestor = None
self._base_is_other_ancestor = None
self._is_criss_cross = False
+ self._lca_trees = None
@property
def revision_graph(self):
@@ -357,10 +358,15 @@
if self.base_rev_id == NULL_REVISION:
raise UnrelatedBranches()
if steps > 1:
+ mutter('criss-cross base selected: %s', self.base_rev_id)
warning('Warning: criss-cross merge encountered. See bzr'
' help criss-cross.')
self._is_criss_cross = True
- mutter('criss-cross base selected: %s', self.base_rev_id)
+ first_lcas = self.revision_graph.find_lca(revisions[0],
+ revisions[1])
+ self._lca_trees = {}
+ for revision_id in first_lcas:
+ self._lca_trees[revision_id] = self.revision_tree(revision_id)
self.base_tree = self.revision_tree(self.base_rev_id)
self.base_is_ancestor = True
self.base_is_other_ancestor = True
@@ -391,7 +397,8 @@
'interesting_files': self.interesting_files,
'pp': self.pp,
'do_merge': False,
- 'is_criss_cross':self._is_criss_cross}
+ 'is_criss_cross':self._is_criss_cross,
+ 'lca_trees':self._lca_trees}
if self.merge_type.requires_base:
kwargs['base_tree'] = self.base_tree
if self.merge_type.supports_reprocess:
@@ -470,7 +477,8 @@
interesting_ids=None, reprocess=False, show_base=False,
pb=DummyProgress(), pp=None, change_reporter=None,
interesting_files=None, do_merge=True,
- cherrypick=False, is_criss_cross=False):
+ cherrypick=False, is_criss_cross=False,
+ lca_trees=None):
"""Initialize the merger object and perform the merge.
:param working_tree: The working tree to apply the merge to
@@ -511,6 +519,7 @@
self.change_reporter = change_reporter
self.cherrypick = cherrypick
self._is_criss_cross = is_criss_cross
+ self._lca_trees = lca_trees
if self.pp is None:
self.pp = ProgressPhase("Merge phase", 3, self.pb)
if do_merge:
@@ -553,19 +562,24 @@
return self.tt
def _compute_transform(self):
- entries = self._entries3()
+ if self._is_criss_cross:
+ entries = self._entries_lca()
+ compare = self._lca_multi_way
+ else:
+ entries = self._entries3()
+ compare = self._three_way
child_pb = ui.ui_factory.nested_progress_bar()
try:
for num, (file_id, changed, parents3, names3,
executable3) in enumerate(entries):
child_pb.update('Preparing file merge', num, len(entries))
- self._merge_names(file_id, parents3, names3)
+ self._merge_names(file_id, parents3, names3, compare)
if changed:
file_status = self.merge_contents(file_id)
else:
file_status = 'unmodified'
self._merge_executable(file_id,
- executable3, file_status)
+ executable3, file_status, compare)
finally:
child_pb.finished()
self.fix_root()
@@ -617,6 +631,89 @@
result.append((file_id, changed, parents3, names3, executable3))
return result
+ def _entries_lca(self):
+ """Gather data about files modified between other tree and lcas.
+
+ :return: a list of tuples of
+ (file_id, changed, parents, names, executable)
+ changed boolean indicating whether the file contents
+ or kind were changed versus any base
+ parents parent ids for ([bases], other, this)
+ names names for ([bases], other, this)
+ executable execute-bit values for ([bases], other, this)
+ """
+ bases_values = {}
+ other_values = {}
+ all_changed = {}
+
+ affected_ids = set()
+
+ for base_revision_id, base_tree in self._lca_trees.iteritems():
+ base_values = {}
+ bases_values[base_revision_id] = base_values
+ other_trees = [tree for rev_id, tree in self._lca_trees.iteritems()
+ if rev_id != base_revision_id]
+ other_trees.append(self.this_tree)
+ # ??? Do we want include_unchanged=True?, what about for all trees
+ # after the first?
+ iterator = self.other_tree.iter_changes(base_tree,
+ include_unchanged=True,
+ specific_files=self.interesting_files,
+ extra_trees=other_trees)
+ for (file_id, paths, changed, versioned, parents, names, kind,
+ executable) in iterator:
+ if (self.interesting_ids is not None and
+ file_id not in self.interesting_ids):
+ continue
+
+ if changed:
+ all_changed[file_id] = True
+
+ if file_id not in other_values:
+ other_values[file_id] = parents[0], names[0], executable[0]
+ base_values[file_id] = parents[1], names[1], executable[1]
+ # We filled in everything we could as we went along, now we need to
+ # make sure we have all the base and this information
+
+ def get_info_from_inventory(file_id, the_inventory):
+ if file_id in the_inventory:
+ entry = the_inventory[file_id]
+ return (entry.parent_id, entry.name, entry.executable)
+ else:
+ return (None, None, None)
+
+ this_values = {}
+ this_inventory = self.this_tree.inventory
+ all_file_ids = set(other_values)
+
+ this_values = dict((file_id, get_info_from_inventory(file_id,
+ this_inventory))
+ for file_id in all_file_ids)
+ for base_revision_id, base_values in bases_values.iteritems():
+ base_tree = self._lca_trees[base_revision_id]
+ base_file_ids = set(base_values)
+ missing_file_ids = all_file_ids - base_file_ids
+ base_inventory = base_tree.inventory
+ base_values.update((file_id, get_info_from_inventory(file_id,
+ base_inventory))
+ for file_id in missing_file_ids)
+ # Now we should have an entry in each base tree, and an entry for this
+ # and other
+ result = []
+ for file_id in all_file_ids:
+ base_tuples = [base[file_id] for base in bases_values.itervalues()]
+ changed = all_changed.get(file_id, False)
+ this_tuple = this_values[file_id]
+ other_tuple = other_values[file_id]
+ parents = ([b[0] for b in base_tuples], other_tuple[0],
+ this_tuple[0])
+ names = ([b[1] for b in base_tuples], other_tuple[1],
+ this_tuple[1])
+ executable = ([b[2] for b in base_tuples], other_tuple[2],
+ this_tuple[2])
+ result.append((file_id, changed, parents, names, executable))
+ return result
+
def fix_root(self):
try:
self.tt.final_kind(self.tt.root)
@@ -708,6 +805,39 @@
return "other"
@staticmethod
+ def _lca_multi_way(bases, other, this):
+ """Compare other and this to multiple bases.
+
+ :param bases: A list of values for each base
+ :param other: The value in other
+ :param this: The value in this
+ :return: One of 'this', 'conflict', or 'other'
+ indicating which one should be taken, or that there was a conflict.
+ """
+ base_first = bases[0]
+ for base in bases[1:]:
+ if base_first != base:
+ break
+ else: # All the bases are identical, we can just use 3-way
+ return Merge3Merger._three_way(base_first, other, this)
+ # If we got this far, we have variation in what the common ancestors
+ # think is the correct value for this path.
+
+ # "Ambiguous clean merge" -- both sides have made the same change.
+ if other == this:
+ return "this"
+ # Punt at this point, we might be able to work something out, but for
+ # now, just conflict
+ # TODO: Consider the ramifications of something like:
+ # if this in bases and other not in bases:
+ # # other changed something, this is the same as a base
+ # # so just pick 'other' and be done
+ # return "other"
+ # Also, if *both* are in 'bases' is this a conflict? Arguably
+ # both sides have chosen to supersede the base value.
+ return "conflict"
+
+ @staticmethod
def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
"""Do a three-way test on a scalar.
Return "this", "other" or "conflict", depending whether a value wins.
@@ -747,14 +877,16 @@
parents.append(entry.parent_id)
return self._merge_names(file_id, parents, names)
- def _merge_names(self, file_id, parents, names):
+ def _merge_names(self, file_id, parents, names, compare=None):
"""Perform a merge on file_id names and parents"""
+ if compare is None:
+ compare = self._three_way
base_name, other_name, this_name = names
base_parent, other_parent, this_parent = parents
- name_winner = self._three_way(*names)
+ name_winner = compare(*names)
- parent_id_winner = self._three_way(*parents)
+ parent_id_winner = compare(*parents)
if this_name is None:
if name_winner == "this":
name_winner = "other"
@@ -956,12 +1088,14 @@
self.other_tree, self.this_tree)]
self._merge_executable(file_id, executable, file_status)
- def _merge_executable(self, file_id, executable, file_status):
+ def _merge_executable(self, file_id, executable, file_status, compare=None):
"""Perform a merge on the execute bit."""
+ if compare is None:
+ compare = self._three_way
base_executable, other_executable, this_executable = executable
if file_status == "deleted":
return
- winner = self._three_way(*executable)
+ winner = compare(*executable)
if winner == "conflict":
# There must be a None in here, if we have a conflict, but we
# need executability since file status was not deleted.
More information about the bazaar-commits
mailing list