« back to all changes in this revision
Viewing changes to bzrlib/merge.py
- browse files at revision 3514.2.2
- compare with another revision
- compare with revision 3514.2.2
- download diff
- download tarball
- view history from revision 3514.2.2
- Committer: John Arbash Meinel
- Date: 2008-07-09 21:42:24 UTC
- mto: This revision was merged to the branch mainline in revision 3543.
- Revision ID: john@arbash-meinel.com-20080709214224-r75k87r6a01pfc3h
Restore a real weave merge to 'bzr merge --weave'.
To do so efficiently, we only add the simple LCAs to the final weave
object, unless we run into complexities with the merge graph.
This gives the same effective result as adding all the texts,
with the advantage of not having to extract all of them.
To do so efficiently, we only add the simple LCAs to the final weave
object, unless we run into complexities with the merge graph.
This gives the same effective result as adding all the texts,
with the advantage of not having to extract all of them.
added
removed
bzrlib/merge.py
1258
1258
self._last_lines_revision_id = None
1259
1259
self._cached_matching_blocks = {}
1260
1260
self._key_prefix = key_prefix
1261
lines = self.get_lines([a_rev, b_rev])
1262
self.lines_a = lines[a_rev]
1263
self.lines_b = lines[b_rev]
1261
self._precache_tip_lines()
1262
1263
def _precache_tip_lines(self):
1264
lines = self.get_lines([self.a_rev, self.b_rev])
1265
self.lines_a = lines[self.a_rev]
1266
self.lines_b = lines[self.b_rev]
1264
1267
1265
1268
def get_lines(self, revisions):
1266
1269
"""Get lines for revisions from the backing VersionedFiles.
1392
1395
"""Plan an annotate merge using on-the-fly annotation"""
1393
1396
1394
1397
def __init__(self, a_rev, b_rev, vf, key_prefix):
1395
_PlanMergeBase.__init__(self, a_rev, b_rev, vf, key_prefix)
1396
graph = Graph(vf)
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))
1404
1405
def _determine_status(self, revision_id, unique_line_numbers):
1406
"""Determines the status unique lines versus all lcas.
1407
1408
Basically, determines why the line is unique to this revision.
1409
1410
A line may be determined new or killed, but not both.
1411
1412
:param revision_id: The id of the revision in which the lines are
1413
unique
1414
:param unique_line_numbers: The line numbers of unique lines.
1415
:return a tuple of (new_this, killed_other):
1416
"""
1417
new = self._find_new(revision_id)
1418
killed = set(unique_line_numbers).difference(new)
1419
return new, killed
1420
1421
def _find_new(self, version_id):
1422
"""Determine which lines are new in the ancestry of this version.
1423
1424
If a lines is present in this version, and not present in any
1425
common ancestor, it is considered new.
1426
"""
1427
if version_id not in self.uncommon:
1428
return set()
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])))
1434
new = None
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:
1442
result.append(ii)
1443
if new is None:
1444
new = set(result)
1398
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
1399
self.a_key = self._key_prefix + (self.a_rev,)
1400
self.b_key = self._key_prefix + (self.b_rev,)
1401
self.graph = Graph(self.vf)
1402
# heads = self.graph.heads((self.a_key, self.b_key))
1403
# if len(heads) == 1:
1404
# # one side dominates, so we can just return its values, yay for
1405
# # per-file graphs
1406
# # Ideally we would know that before we get this far
1407
# self._head_key = heads.pop()
1408
# if self._head_key == self.a_key:
1409
# other = b_rev
1410
# else:
1411
# other = a_rev
1412
# mutter('found dominating revision for %s\n%s > %s', self.vf,
1413
# self._head_key[-1], other)
1414
# self._weave = None
1415
# else:
1416
self._head_key = None
1417
self._build_weave()
1418
1419
def _precache_tip_lines(self):
1420
# Turn this into a no-op, because we will do this later
1421
pass
1422
1423
def _find_recursive_lcas(self):
1424
"""Find all the ancestors back to a unique lca"""
1425
cur_ancestors = (self.a_key, self.b_key)
1426
ancestor_keys = [cur_ancestors]
1427
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
1428
# rather than a key tuple, but everything else expects tuples, so we
1429
# adapt the result to be normalized, this way we don't have to special
1430
# case _get_interesting_texts, etc.
1431
null_key = self._key_prefix + (NULL_REVISION,)
1432
while True:
1433
next_lcas = self.graph.find_lca(*cur_ancestors)
1434
ancestor_keys.append(next_lcas)
1435
if len(next_lcas) == 0:
1436
ancestor_keys[-1] = [null_key]
1437
self.vf.add_lines(null_key, [], [])
1438
break
1439
elif len(next_lcas) == 1:
1440
if next_lcas == set([NULL_REVISION]):
1441
ancestor_keys[-1] = [null_key]
1442
self.vf.add_lines(null_key, [], [])
1443
break
1444
cur_ancestors = next_lcas
1445
ancestor_keys.reverse()
1446
return ancestor_keys
1447
1448
def _get_interesting_texts(self, lca_keys):
1449
"""Return a dict of texts we are interested in.
1450
1451
Note that the input is in key tuples, but the output is in plain
1452
revision ids.
1453
1454
:param lca_keys: The output from _find_recursive_lcas
1455
:return: A dict of {'revision_id':lines} as returned by
1456
_PlanMergeBase.get_lines()
1457
"""
1458
all_revision_ids = set()
1459
# lcas are in keys, but get_lines works in revision_ids
1460
for ancestor_keys in lca_keys:
1461
all_revision_ids.update([key[-1] for key in ancestor_keys])
1462
all_revision_ids.add(self.a_rev)
1463
all_revision_ids.add(self.b_rev)
1464
1465
all_texts = self.get_lines(all_revision_ids)
1466
return all_texts
1467
1468
def _build_weave(self):
1469
from bzrlib import weave
1470
self._weave = weave.Weave(weave_name='in_memory_weave',
1471
allow_reserved=True)
1472
lca_keys = self._find_recursive_lcas()
1473
1474
all_texts = self._get_interesting_texts(lca_keys)
1475
1476
last_parents = ()
1477
for ancestor_keys in lca_keys:
1478
for ancestor_key in ancestor_keys:
1479
ancestor = ancestor_key[-1]
1480
if self._weave.has_version(ancestor):
1481
# Most likely this happened because one node purely
1482
# dominated another in the per-file graph. That is okay, we
1483
# already have it in the weave, and the plan should be very
1484
# straightforward.
1485
continue
1486
self._weave.add_lines(ancestor, last_parents,
1487
all_texts[ancestor])
1488
last_parents = [a[-1] for a in ancestor_keys]
1489
1490
def plan_merge(self):
1491
"""Generate a 'plan' for merging the two revisions.
1492
1493
This involves comparing their texts and determining the cause of
1494
differences. If text A has a line and text B does not, then either the
1495
line was added to text A, or it was deleted from B. Once the causes
1496
are combined, they are written out in the format described in
1497
VersionedFile.plan_merge
1498
"""
1499
if self._head_key is not None: # There was a single head
1500
if self._head_key == self.a_key:
1501
plan = 'new-a'
1445
1502
else:
1446
new.intersection_update(result)
1447
return new
1503
if self._head_key != self.b_key:
1504
raise AssertionError('There was an invalid head: %s != %s'
1505
% (self.b_key, self._head_key))
1506
plan = 'new-b'
1507
lines = self.get_lines([self._head_key[-1]])[self._head_key[-1]]
1508
return ((plan, line) for line in lines)
1509
return self._weave.plan_merge(self.a_rev, self.b_rev)
1448
1510
1449
1511
1450
1512
class _PlanLCAMerge(_PlanMergeBase):
Loggerhead is a web-based interface for Breezy
Version: 2.0.1