Rev 3526: Start refactoring into helper functions in http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/weave_merge
John Arbash Meinel
john at arbash-meinel.com
Sat Jul 12 19:06:41 BST 2008
At http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/weave_merge
------------------------------------------------------------
revno: 3526
revision-id: john at arbash-meinel.com-20080712180630-5hc93d3s2vff9olo
parent: john at arbash-meinel.com-20080711214124-qi09irlj7pd5cuzg
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: weave_merge
timestamp: Sat 2008-07-12 13:06:30 -0500
message:
Start refactoring into helper functions
-------------- next part --------------
=== modified file 'bzrlib/merge.py'
--- a/bzrlib/merge.py 2008-07-11 21:41:24 +0000
+++ b/bzrlib/merge.py 2008-07-12 18:06:30 +0000
@@ -1491,36 +1491,41 @@
self.graph.find_unique_ancestors(tip, [base_key]))
parent_map = self.graph.get_parent_map(interesting)
parent_map[base_key] = ()
- culled_parent_map = {}
- extra_base_ancestors = set()
+ culled_parent_map, child_map, tails = self._remove_external_references(
+ parent_map)
+ return culled_parent_map
+
+ @staticmethod
+ def _remove_external_references(parent_map):
+ """Remove references that go outside of the parent map.
+
+ :param parent_map: Something returned from Graph.get_parent_map(keys)
+ :return: (filtered_parent_map, child_map, tails)
+ filtered_parent_map is parent_map without external references
+ child_map is the {parent_key: [child_keys]} mapping
+ tails is a list of nodes that do not have any parents in the map
+ """
+ # TODO: The basic effect of this function seems more generic than
+ # _PlanMerge. But the specific details of building a child_map,
+ # and computing tails seems very specific to _PlanMerge.
+ # Still, should this be in Graph land?
+ filtered_parent_map = {}
+ child_map = {}
+ tails = []
for key, parent_keys in parent_map.iteritems():
- culled_parent_keys = tuple([p for p in parent_keys
- if p in parent_map])
- if not culled_parent_keys and key is not base_key:
- # We have another 'tail', make sure to bring it into the
- # ancestry, so that we don't think all of its lines are unique.
- lcas = self.graph.find_lca(key, base_key)
- if lcas == set([NULL_REVISION]):
- lcas = ()
- if len(lcas) == 0:
- # Nothing to do, no common ancestor
- pass
- else:
- # Technically, this isn't 100% correct, but it is better
- # than nothing. If we have more than 1 LCA, we probably
- # should keep tracking the rabbit down the hole, so that we
- # get proper annotations for lines. For now, though, we
- # just add the first lca, and live with it
- lca = list(lcas)[0]
- extra_base_ancestors.add(lca)
- culled_parent_keys = (lca,)
- if lca not in culled_parent_map:
- culled_parent_map[lca] = ()
- culled_parent_map[key] = culled_parent_keys
- if extra_base_ancestors:
- culled_parent_map[base_key] = self.graph.find_merge_order(base_key,
- extra_base_ancestors)
- return culled_parent_map
+ culled_parent_keys = [p for p in parent_keys if p in parent_map]
+ if not culled_parent_keys:
+ tails.append(key)
+ for parent_key in culled_parent_keys:
+ child_map.setdefault(parent_key, []).append(key)
+ # TODO: Do we want to do this, it adds overhead for every node,
+ # just to say that the node has no children
+ child_map.setdefault(key, [])
+ filtered_parent_map[key] = culled_parent_keys
+ return filtered_parent_map, child_map, tails
+
+ def _prune_tails(self, parent_map, tails_to_remove, child_map):
+ """Remove tails from the parent map."""
def _get_interesting_texts(self, parent_map):
"""Return a dict of texts we are interested in.
=== modified file 'bzrlib/tests/test_merge.py'
--- a/bzrlib/tests/test_merge.py 2008-07-11 21:41:24 +0000
+++ b/bzrlib/tests/test_merge.py 2008-07-12 18:06:30 +0000
@@ -773,6 +773,45 @@
('unchanged', 'g\n')],
list(plan))
+ def assertRemoveExternalReferences(self, filtered_parent_map,
+ child_map, tails, parent_map):
+ """Assert results for _PlanMerge._remove_external_references."""
+ (act_filtered_parent_map, act_child_map,
+ act_tails) = _PlanMerge._remove_external_references(parent_map)
+
+ # The parent map *should* preserve ordering, but the ordering of
+ # children is not strictly defined
+ # child_map = dict((k, sorted(children))
+ # for k, children in child_map.iteritems())
+ # act_child_map = dict(k, sorted(children)
+ # for k, children in act_child_map.iteritems())
+ self.assertEqual(filtered_parent_map, act_filtered_parent_map)
+ self.assertEqual(child_map, act_child_map)
+ self.assertEqual(sorted(tails), sorted(act_tails))
+
+ def test__remove_external_references(self):
+ # First, nothing to remove
+ self.assertRemoveExternalReferences({3: [2], 2: [1], 1: []},
+ {1: [2], 2: [3], 3: []}, [1], {3: [2], 2: [1], 1: []})
+ # The reverse direction
+ self.assertRemoveExternalReferences({1: [2], 2: [3], 3: []},
+ {3: [2], 2: [1], 1: []}, [3], {1: [2], 2: [3], 3: []})
+ # Extra references
+ self.assertRemoveExternalReferences({3: [2], 2: [1], 1: []},
+ {1: [2], 2: [3], 3: []}, [1], {3: [2, 4], 2: [1, 5], 1: [6]})
+ # Multiple tails
+ self.assertRemoveExternalReferences(
+ {4: [2, 3], 3: [], 2: [1], 1: []},
+ {1: [2], 2: [4], 3: [4], 4: []},
+ [1, 3],
+ {4: [2, 3], 3: [5], 2: [1], 1: [6]})
+ # Multiple children
+ self.assertRemoveExternalReferences(
+ {1: [3], 2: [3, 4], 3: [], 4: []},
+ {1: [], 2: [], 3: [1, 2], 4: [2]},
+ [3, 4],
+ {1: [3], 2: [3, 4], 3: [5], 4: []})
+
def test_subtract_plans(self):
old_plan = [
('unchanged', 'a\n'),
More information about the bazaar-commits
mailing list