1392
1397
"""Plan an annotate merge using on-the-fly annotation"""
1394
1399
def __init__(self, a_rev, b_rev, vf, key_prefix):
1395
_PlanMergeBase.__init__(self, a_rev, b_rev, vf, key_prefix)
1397
# XXX: There is probably a better API to use to examine less history.
1398
a_ancestry = set(chain(*graph._make_breadth_first_searcher(
1399
[key_prefix + (a_rev,)])))
1400
b_ancestry = set(chain(*graph._make_breadth_first_searcher(
1401
[key_prefix + (b_rev,)])))
1402
self.uncommon = set(key[-1] for key in
1403
a_ancestry.symmetric_difference(b_ancestry))
1405
def _determine_status(self, revision_id, unique_line_numbers):
1406
"""Determines the status unique lines versus all lcas.
1408
Basically, determines why the line is unique to this revision.
1410
A line may be determined new or killed, but not both.
1412
:param revision_id: The id of the revision in which the lines are
1414
:param unique_line_numbers: The line numbers of unique lines.
1415
:return a tuple of (new_this, killed_other):
1417
new = self._find_new(revision_id)
1418
killed = set(unique_line_numbers).difference(new)
1421
def _find_new(self, version_id):
1422
"""Determine which lines are new in the ancestry of this version.
1424
If a lines is present in this version, and not present in any
1425
common ancestor, it is considered new.
1427
if version_id not in self.uncommon:
1429
key = self._key_prefix + (version_id,)
1430
parent_map = self.vf.get_parent_map([key])
1431
parents = tuple(parent[-1] for parent in parent_map[key])
1432
if len(parents) == 0:
1433
return set(range(len(self.get_lines([version_id])[version_id])))
1435
for parent in parents:
1436
blocks = self._get_matching_blocks(version_id, parent)
1437
result, unused = self._unique_lines(blocks)
1438
parent_new = self._find_new(parent)
1439
for i, j, n in blocks:
1440
for ii, jj in [(i+r, j+r) for r in range(n)]:
1441
if jj in parent_new:
1446
new.intersection_update(result)
1400
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
1401
self.a_key = self._key_prefix + (self.a_rev,)
1402
self.b_key = self._key_prefix + (self.b_rev,)
1403
self.graph = Graph(self.vf)
1404
heads = self.graph.heads((self.a_key, self.b_key))
1406
# one side dominates, so we can just return its values, yay for
1408
# Ideally we would know that before we get this far
1409
self._head_key = heads.pop()
1410
if self._head_key == self.a_key:
1414
mutter('found dominating revision for %s\n%s > %s', self.vf,
1415
self._head_key[-1], other)
1418
self._head_key = None
1421
def _precache_tip_lines(self):
1422
# Turn this into a no-op, because we will do this later
1425
def _find_recursive_lcas(self):
1426
"""Find all the ancestors back to a unique lca"""
1427
cur_ancestors = (self.a_key, self.b_key)
1428
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
1429
# rather than a key tuple. We will just map that directly to no common
1433
next_lcas = self.graph.find_lca(*cur_ancestors)
1434
# Map a plain NULL_REVISION to a simple no-ancestors
1435
if next_lcas == set([NULL_REVISION]):
1437
# Order the lca's based on when they were merged into the tip
1438
# While the actual merge portion of weave merge uses a set() of
1439
# active revisions, the order of insertion *does* effect the
1440
# implicit ordering of the texts.
1441
for rev_key in cur_ancestors:
1442
ordered_parents = tuple(self.graph.find_merge_order(rev_key,
1444
parent_map[rev_key] = ordered_parents
1445
if len(next_lcas) == 0:
1447
elif len(next_lcas) == 1:
1448
parent_map[list(next_lcas)[0]] = ()
1450
elif len(next_lcas) > 2:
1451
# More than 2 lca's, fall back to grabbing all nodes between
1452
# this and the unique lca.
1453
mutter('More than 2 LCAs, falling back to all nodes for:'
1454
' %s, %s\n=> %s', self.a_key, self.b_key, cur_ancestors)
1455
cur_lcas = next_lcas
1456
while len(cur_lcas) > 1:
1457
cur_lcas = self.graph.find_lca(*cur_lcas)
1458
if len(cur_lcas) == 0:
1459
# No common base to find, use the full ancestry
1462
unique_lca = list(cur_lcas)[0]
1463
if unique_lca == NULL_REVISION:
1464
# find_lca will return a plain 'NULL_REVISION' rather
1465
# than a key tuple when there is no common ancestor, we
1466
# prefer to just use None, because it doesn't confuse
1467
# _get_interesting_texts()
1469
parent_map.update(self._find_unique_parents(next_lcas,
1472
cur_ancestors = next_lcas
1475
def _find_unique_parents(self, tip_keys, base_key):
1476
"""Find ancestors of tip that aren't ancestors of base.
1478
:param tip_keys: Nodes that are interesting
1479
:param base_key: Cull all ancestors of this node
1480
:return: The parent map for all revisions between tip_keys and
1481
base_key. base_key will be included. References to nodes outside of
1482
the ancestor set will also be removed.
1484
# TODO: this would be simpler if find_unique_ancestors took a list
1485
# instead of a single tip, internally it supports it, but it
1486
# isn't a "backwards compatible" api change.
1487
if base_key is None:
1488
parent_map = dict(self.graph.iter_ancestry(tip_keys))
1489
# We remove NULL_REVISION because it isn't a proper tuple key, and
1490
# thus confuses things like _get_interesting_texts, and our logic
1491
# to add the texts into the memory weave.
1492
if NULL_REVISION in parent_map:
1493
parent_map.pop(NULL_REVISION)
1496
for tip in tip_keys:
1498
self.graph.find_unique_ancestors(tip, [base_key]))
1499
parent_map = self.graph.get_parent_map(interesting)
1500
parent_map[base_key] = ()
1501
culled_parent_map, child_map, tails = self._remove_external_references(
1503
# Remove all the tails but base_key
1504
if base_key is not None:
1505
tails.remove(base_key)
1506
self._prune_tails(culled_parent_map, child_map, tails)
1507
# Now remove all the uninteresting 'linear' regions
1508
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
1512
def _remove_external_references(parent_map):
1513
"""Remove references that go outside of the parent map.
1515
:param parent_map: Something returned from Graph.get_parent_map(keys)
1516
:return: (filtered_parent_map, child_map, tails)
1517
filtered_parent_map is parent_map without external references
1518
child_map is the {parent_key: [child_keys]} mapping
1519
tails is a list of nodes that do not have any parents in the map
1521
# TODO: The basic effect of this function seems more generic than
1522
# _PlanMerge. But the specific details of building a child_map,
1523
# and computing tails seems very specific to _PlanMerge.
1524
# Still, should this be in Graph land?
1525
filtered_parent_map = {}
1528
for key, parent_keys in parent_map.iteritems():
1529
culled_parent_keys = [p for p in parent_keys if p in parent_map]
1530
if not culled_parent_keys:
1532
for parent_key in culled_parent_keys:
1533
child_map.setdefault(parent_key, []).append(key)
1534
# TODO: Do we want to do this, it adds overhead for every node,
1535
# just to say that the node has no children
1536
child_map.setdefault(key, [])
1537
filtered_parent_map[key] = culled_parent_keys
1538
return filtered_parent_map, child_map, tails
1541
def _prune_tails(parent_map, child_map, tails_to_remove):
1542
"""Remove tails from the parent map.
1544
This will remove the supplied revisions until no more children have 0
1547
:param parent_map: A dict of {child: [parents]}, this dictionary will
1548
be modified in place.
1549
:param tails_to_remove: A list of tips that should be removed,
1550
this list will be consumed
1551
:param child_map: The reverse dict of parent_map ({parent: [children]})
1552
this dict will be modified
1553
:return: None, parent_map will be modified in place.
1555
while tails_to_remove:
1556
next = tails_to_remove.pop()
1557
parent_map.pop(next)
1558
children = child_map.pop(next)
1559
for child in children:
1560
child_parents = parent_map[child]
1561
child_parents.remove(next)
1562
if len(child_parents) == 0:
1563
tails_to_remove.append(child)
1565
def _get_interesting_texts(self, parent_map):
1566
"""Return a dict of texts we are interested in.
1568
Note that the input is in key tuples, but the output is in plain
1571
:param parent_map: The output from _find_recursive_lcas
1572
:return: A dict of {'revision_id':lines} as returned by
1573
_PlanMergeBase.get_lines()
1575
all_revision_keys = set(parent_map)
1576
all_revision_keys.add(self.a_key)
1577
all_revision_keys.add(self.b_key)
1579
# Everything else is in 'keys' but get_lines is in 'revision_ids'
1580
all_texts = self.get_lines([k[-1] for k in all_revision_keys])
1583
def _build_weave(self):
1584
from bzrlib import weave
1585
self._weave = weave.Weave(weave_name='in_memory_weave',
1586
allow_reserved=True)
1587
parent_map = self._find_recursive_lcas()
1589
all_texts = self._get_interesting_texts(parent_map)
1591
# Note: Unfortunately, the order given by topo_sort will effect the
1592
# ordering resolution in the output. Specifically, if you add A then B,
1593
# then in the output text A lines will show up before B lines. And, of
1594
# course, topo_sort doesn't guarantee any real ordering.
1595
# So we use merge_sort, and add a fake node on the tip.
1596
# This ensures that left-hand parents will always be inserted into the
1597
# weave before right-hand parents.
1598
tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
1599
parent_map[tip_key] = (self.a_key, self.b_key)
1601
for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
1605
# for key in tsort.topo_sort(parent_map):
1606
parent_keys = parent_map[key]
1607
revision_id = key[-1]
1608
parent_ids = [k[-1] for k in parent_keys]
1609
self._weave.add_lines(revision_id, parent_ids,
1610
all_texts[revision_id])
1612
def plan_merge(self):
1613
"""Generate a 'plan' for merging the two revisions.
1615
This involves comparing their texts and determining the cause of
1616
differences. If text A has a line and text B does not, then either the
1617
line was added to text A, or it was deleted from B. Once the causes
1618
are combined, they are written out in the format described in
1619
VersionedFile.plan_merge
1621
if self._head_key is not None: # There was a single head
1622
if self._head_key == self.a_key:
1625
if self._head_key != self.b_key:
1626
raise AssertionError('There was an invalid head: %s != %s'
1627
% (self.b_key, self._head_key))
1629
head_rev = self._head_key[-1]
1630
lines = self.get_lines([head_rev])[head_rev]
1631
return ((plan, line) for line in lines)
1632
return self._weave.plan_merge(self.a_rev, self.b_rev)
1450
1635
class _PlanLCAMerge(_PlanMergeBase):
added
removed
bzrlib/merge.py
