351
379
ensure_null(self.other_basis)]
352
380
if NULL_REVISION in revisions:
353
381
self.base_rev_id = NULL_REVISION
382
self.base_tree = self.revision_tree(self.base_rev_id)
383
self._is_criss_cross = False
355
self.base_rev_id, steps = self.revision_graph.find_unique_lca(
356
revisions[0], revisions[1], count_steps=True)
385
lcas = self.revision_graph.find_lca(revisions[0], revisions[1])
386
self._is_criss_cross = False
388
self.base_rev_id = NULL_REVISION
390
self.base_rev_id = list(lcas)[0]
391
else: # len(lcas) > 1
393
# find_unique_lca can only handle 2 nodes, so we have to
394
# start back at the beginning. It is a shame to traverse
395
# the graph again, but better than re-implementing
397
self.base_rev_id = self.revision_graph.find_unique_lca(
398
revisions[0], revisions[1])
400
self.base_rev_id = self.revision_graph.find_unique_lca(
402
self._is_criss_cross = True
357
403
if self.base_rev_id == NULL_REVISION:
358
404
raise UnrelatedBranches()
405
if self._is_criss_cross:
360
406
warning('Warning: criss-cross merge encountered. See bzr'
361
407
' help criss-cross.')
362
self.base_tree = self.revision_tree(self.base_rev_id)
408
mutter('Criss-cross lcas: %r' % lcas)
409
interesting_revision_ids = [self.base_rev_id]
410
interesting_revision_ids.extend(lcas)
411
interesting_trees = dict((t.get_revision_id(), t)
412
for t in self.this_branch.repository.revision_trees(
413
interesting_revision_ids))
414
self._cached_trees.update(interesting_trees)
415
self.base_tree = interesting_trees.pop(self.base_rev_id)
416
sorted_lca_keys = self.revision_graph.find_merge_order(
418
self._lca_trees = [interesting_trees[key]
419
for key in sorted_lca_keys]
421
self.base_tree = self.revision_tree(self.base_rev_id)
363
422
self.base_is_ancestor = True
364
423
self.base_is_other_ancestor = True
424
mutter('Base revid: %r' % self.base_rev_id)
366
426
def set_base(self, base_revision):
367
427
"""Set the base revision to use for the merge.
407
467
if self.merge_type.supports_cherrypick:
408
468
kwargs['cherrypick'] = (not self.base_is_ancestor or
409
469
not self.base_is_other_ancestor)
470
if self._is_criss_cross and getattr(self.merge_type,
471
'supports_lca_trees', False):
472
kwargs['lca_trees'] = self._lca_trees
410
473
return self.merge_type(pb=self._pb,
411
474
change_reporter=self.change_reporter,
477
def _do_merge_to(self, merge):
478
if self.other_branch is not None:
479
self.other_branch.update_references(self.this_branch)
481
if self.recurse == 'down':
482
for relpath, file_id in self.this_tree.iter_references():
483
sub_tree = self.this_tree.get_nested_tree(file_id, relpath)
484
other_revision = self.other_tree.get_reference_revision(
486
if other_revision == sub_tree.last_revision():
488
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
489
sub_merge.merge_type = self.merge_type
490
other_branch = self.other_branch.reference_parent(file_id, relpath)
491
sub_merge.set_other_revision(other_revision, other_branch)
492
base_revision = self.base_tree.get_reference_revision(file_id)
493
sub_merge.base_tree = \
494
sub_tree.branch.repository.revision_tree(base_revision)
495
sub_merge.base_rev_id = base_revision
414
498
def do_merge(self):
415
499
self.this_tree.lock_tree_write()
416
if self.base_tree is not None:
417
self.base_tree.lock_read()
418
if self.other_tree is not None:
419
self.other_tree.lock_read()
421
merge = self.make_merger()
423
if self.recurse == 'down':
424
for relpath, file_id in self.this_tree.iter_references():
425
sub_tree = self.this_tree.get_nested_tree(file_id, relpath)
426
other_revision = self.other_tree.get_reference_revision(
428
if other_revision == sub_tree.last_revision():
430
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
431
sub_merge.merge_type = self.merge_type
432
other_branch = self.other_branch.reference_parent(file_id, relpath)
433
sub_merge.set_other_revision(other_revision, other_branch)
434
base_revision = self.base_tree.get_reference_revision(file_id)
435
sub_merge.base_tree = \
436
sub_tree.branch.repository.revision_tree(base_revision)
437
sub_merge.base_rev_id = base_revision
441
if self.other_tree is not None:
442
self.other_tree.unlock()
443
501
if self.base_tree is not None:
444
self.base_tree.unlock()
502
self.base_tree.lock_read()
504
if self.other_tree is not None:
505
self.other_tree.lock_read()
507
merge = self.make_merger()
508
self._do_merge_to(merge)
510
if self.other_tree is not None:
511
self.other_tree.unlock()
513
if self.base_tree is not None:
514
self.base_tree.unlock()
445
516
self.this_tree.unlock()
446
517
if len(merge.cooked_conflicts) == 0:
447
518
if not self.ignore_zero and not is_quiet():
612
720
result.append((file_id, changed, parents3, names3, executable3))
723
def _entries_lca(self):
724
"""Gather data about files modified between multiple trees.
726
This compares OTHER versus all LCA trees, and for interesting entries,
727
it then compares with THIS and BASE.
729
For the multi-valued entries, the format will be (BASE, [lca1, lca2])
730
:return: [(file_id, changed, parents, names, executable)]
731
file_id Simple file_id of the entry
732
changed Boolean, True if the kind or contents changed
734
parents ((base, [parent_id, in, lcas]), parent_id_other,
736
names ((base, [name, in, lcas]), name_in_other, name_in_this)
737
executable ((base, [exec, in, lcas]), exec_in_other, exec_in_this)
739
if self.interesting_files is not None:
740
lookup_trees = [self.this_tree, self.base_tree]
741
lookup_trees.extend(self._lca_trees)
742
# I think we should include the lca trees as well
743
interesting_ids = self.other_tree.paths2ids(self.interesting_files,
746
interesting_ids = self.interesting_ids
748
walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
750
base_inventory = self.base_tree.inventory
751
this_inventory = self.this_tree.inventory
752
for path, file_id, other_ie, lca_values in walker.iter_all():
753
# Is this modified at all from any of the other trees?
755
other_ie = _none_entry
756
if interesting_ids is not None and file_id not in interesting_ids:
759
# If other_revision is found in any of the lcas, that means this
760
# node is uninteresting. This is because when merging, if there are
761
# multiple heads(), we have to create a new node. So if we didn't,
762
# we know that the ancestry is linear, and that OTHER did not
764
# See doc/developers/lca_merge_resolution.txt for details
765
other_revision = other_ie.revision
766
if other_revision is not None:
767
# We can't use this shortcut when other_revision is None,
768
# because it may be None because things are WorkingTrees, and
769
# not because it is *actually* None.
770
is_unmodified = False
771
for lca_path, ie in lca_values:
772
if ie is not None and ie.revision == other_revision:
779
for lca_path, lca_ie in lca_values:
781
lca_entries.append(_none_entry)
783
lca_entries.append(lca_ie)
785
if file_id in base_inventory:
786
base_ie = base_inventory[file_id]
788
base_ie = _none_entry
790
if file_id in this_inventory:
791
this_ie = this_inventory[file_id]
793
this_ie = _none_entry
799
for lca_ie in lca_entries:
800
lca_kinds.append(lca_ie.kind)
801
lca_parent_ids.append(lca_ie.parent_id)
802
lca_names.append(lca_ie.name)
803
lca_executable.append(lca_ie.executable)
805
kind_winner = self._lca_multi_way(
806
(base_ie.kind, lca_kinds),
807
other_ie.kind, this_ie.kind)
808
parent_id_winner = self._lca_multi_way(
809
(base_ie.parent_id, lca_parent_ids),
810
other_ie.parent_id, this_ie.parent_id)
811
name_winner = self._lca_multi_way(
812
(base_ie.name, lca_names),
813
other_ie.name, this_ie.name)
815
content_changed = True
816
if kind_winner == 'this':
817
# No kind change in OTHER, see if there are *any* changes
818
if other_ie.kind == 'directory':
819
if parent_id_winner == 'this' and name_winner == 'this':
820
# No change for this directory in OTHER, skip
822
content_changed = False
823
elif other_ie.kind is None or other_ie.kind == 'file':
824
def get_sha1(ie, tree):
825
if ie.kind != 'file':
827
return tree.get_file_sha1(file_id)
828
base_sha1 = get_sha1(base_ie, self.base_tree)
829
lca_sha1s = [get_sha1(ie, tree) for ie, tree
830
in zip(lca_entries, self._lca_trees)]
831
this_sha1 = get_sha1(this_ie, self.this_tree)
832
other_sha1 = get_sha1(other_ie, self.other_tree)
833
sha1_winner = self._lca_multi_way(
834
(base_sha1, lca_sha1s), other_sha1, this_sha1,
835
allow_overriding_lca=False)
836
exec_winner = self._lca_multi_way(
837
(base_ie.executable, lca_executable),
838
other_ie.executable, this_ie.executable)
839
if (parent_id_winner == 'this' and name_winner == 'this'
840
and sha1_winner == 'this' and exec_winner == 'this'):
841
# No kind, parent, name, exec, or content change for
842
# OTHER, so this node is not considered interesting
844
if sha1_winner == 'this':
845
content_changed = False
846
elif other_ie.kind == 'symlink':
847
def get_target(ie, tree):
848
if ie.kind != 'symlink':
850
return tree.get_symlink_target(file_id)
851
base_target = get_target(base_ie, self.base_tree)
852
lca_targets = [get_target(ie, tree) for ie, tree
853
in zip(lca_entries, self._lca_trees)]
854
this_target = get_target(this_ie, self.this_tree)
855
other_target = get_target(other_ie, self.other_tree)
856
target_winner = self._lca_multi_way(
857
(base_target, lca_targets),
858
other_target, this_target)
859
if (parent_id_winner == 'this' and name_winner == 'this'
860
and target_winner == 'this'):
861
# No kind, parent, name, or symlink target change
864
if target_winner == 'this':
865
content_changed = False
866
elif other_ie.kind == 'tree-reference':
867
# The 'changed' information seems to be handled at a higher
868
# level. At least, _entries3 returns False for content
869
# changed, even when at a new revision_id.
870
content_changed = False
871
if (parent_id_winner == 'this' and name_winner == 'this'):
872
# Nothing interesting
875
raise AssertionError('unhandled kind: %s' % other_ie.kind)
876
# XXX: We need to handle kind == 'symlink'
878
# If we have gotten this far, that means something has changed
879
result.append((file_id, content_changed,
880
((base_ie.parent_id, lca_parent_ids),
881
other_ie.parent_id, this_ie.parent_id),
882
((base_ie.name, lca_names),
883
other_ie.name, this_ie.name),
884
((base_ie.executable, lca_executable),
885
other_ie.executable, this_ie.executable)
615
890
def fix_root(self):
617
892
self.tt.final_kind(self.tt.root)
618
893
except NoSuchFile:
619
894
self.tt.cancel_deletion(self.tt.root)
620
895
if self.tt.final_file_id(self.tt.root) is None:
621
self.tt.version_file(self.tt.tree_file_id(self.tt.root),
896
self.tt.version_file(self.tt.tree_file_id(self.tt.root),
623
if self.other_tree.inventory.root is None:
625
898
other_root_file_id = self.other_tree.get_root_id()
899
if other_root_file_id is None:
626
901
other_root = self.tt.trans_id_file_id(other_root_file_id)
627
902
if other_root == self.tt.root:
984
def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
985
"""Consider LCAs when determining whether a change has occurred.
987
If LCAS are all identical, this is the same as a _three_way comparison.
989
:param bases: value in (BASE, [LCAS])
990
:param other: value in OTHER
991
:param this: value in THIS
992
:param allow_overriding_lca: If there is more than one unique lca
993
value, allow OTHER to override THIS if it has a new value, and
994
THIS only has an lca value, or vice versa. This is appropriate for
995
truly scalar values, not as much for non-scalars.
996
:return: 'this', 'other', or 'conflict' depending on whether an entry
999
# See doc/developers/lca_tree_merging.txt for details about this
1002
# Either Ambiguously clean, or nothing was actually changed. We
1005
base_val, lca_vals = bases
1006
# Remove 'base_val' from the lca_vals, because it is not interesting
1007
filtered_lca_vals = [lca_val for lca_val in lca_vals
1008
if lca_val != base_val]
1009
if len(filtered_lca_vals) == 0:
1010
return Merge3Merger._three_way(base_val, other, this)
1012
unique_lca_vals = set(filtered_lca_vals)
1013
if len(unique_lca_vals) == 1:
1014
return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
1016
if allow_overriding_lca:
1017
if other in unique_lca_vals:
1018
if this in unique_lca_vals:
1019
# Each side picked a different lca, conflict
1022
# This has a value which supersedes both lca values, and
1023
# other only has an lca value
1025
elif this in unique_lca_vals:
1026
# OTHER has a value which supersedes both lca values, and this
1027
# only has an lca value
1030
# At this point, the lcas disagree, and the tips disagree
706
1034
def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
707
1035
"""Do a three-way test on a scalar.
708
1036
Return "this", "other" or "conflict", depending whether a value wins.
809
1138
base_pair = contents_pair(self.base_tree)
810
1139
other_pair = contents_pair(self.other_tree)
811
if base_pair == other_pair:
812
# OTHER introduced no changes
814
this_pair = contents_pair(self.this_tree)
815
if this_pair == other_pair:
816
# THIS and OTHER introduced the same changes
819
trans_id = self.tt.trans_id_file_id(file_id)
820
if this_pair == base_pair:
821
# only OTHER introduced changes
822
if file_id in self.this_tree:
823
# Remove any existing contents
824
self.tt.delete_contents(trans_id)
825
if file_id in self.other_tree:
826
# OTHER changed the file
827
create_by_entry(self.tt,
828
self.other_tree.inventory[file_id],
829
self.other_tree, trans_id)
830
if file_id not in self.this_tree.inventory:
831
self.tt.version_file(file_id, trans_id)
833
elif file_id in self.this_tree.inventory:
834
# OTHER deleted the file
835
self.tt.unversion_file(trans_id)
837
#BOTH THIS and OTHER introduced changes; scalar conflict
838
elif this_pair[0] == "file" and other_pair[0] == "file":
1141
this_pair = contents_pair(self.this_tree)
1142
lca_pairs = [contents_pair(tree) for tree in self._lca_trees]
1143
winner = self._lca_multi_way((base_pair, lca_pairs), other_pair,
1144
this_pair, allow_overriding_lca=False)
1146
if base_pair == other_pair:
1149
# We delayed evaluating this_pair as long as we can to avoid
1150
# unnecessary sha1 calculation
1151
this_pair = contents_pair(self.this_tree)
1152
winner = self._three_way(base_pair, other_pair, this_pair)
1153
if winner == 'this':
1154
# No interesting changes introduced by OTHER
1156
trans_id = self.tt.trans_id_file_id(file_id)
1157
if winner == 'other':
1158
# OTHER is a straight winner, so replace this contents with other
1159
file_in_this = file_id in self.this_tree
1161
# Remove any existing contents
1162
self.tt.delete_contents(trans_id)
1163
if file_id in self.other_tree:
1164
# OTHER changed the file
1166
if wt.supports_content_filtering():
1167
# We get the path from the working tree if it exists.
1168
# That fails though when OTHER is adding a file, so
1169
# we fall back to the other tree to find the path if
1170
# it doesn't exist locally.
1172
filter_tree_path = wt.id2path(file_id)
1173
except errors.NoSuchId:
1174
filter_tree_path = self.other_tree.id2path(file_id)
1176
# Skip the id2path lookup for older formats
1177
filter_tree_path = None
1178
create_from_tree(self.tt, trans_id,
1179
self.other_tree, file_id,
1180
filter_tree_path=filter_tree_path)
1181
if not file_in_this:
1182
self.tt.version_file(file_id, trans_id)
1185
# OTHER deleted the file
1186
self.tt.unversion_file(trans_id)
1189
# We have a hypothetical conflict, but if we have files, then we
1190
# can try to merge the content
1191
if this_pair[0] == 'file' and other_pair[0] == 'file':
839
1192
# THIS and OTHER are both files, so text merge. Either
840
1193
# BASE is a file, or both converted to files, so at least we
841
1194
# have agreement that output should be a file.
914
1266
determined automatically. If set_version is true, the .OTHER, .THIS
915
1267
or .BASE (in that order) will be created as versioned files.
917
data = [('OTHER', self.other_tree, other_lines),
1269
data = [('OTHER', self.other_tree, other_lines),
918
1270
('THIS', self.this_tree, this_lines)]
920
1272
data.append(('BASE', self.base_tree, base_lines))
1274
# We need to use the actual path in the working tree of the file here,
1275
# ignoring the conflict suffixes
1277
if wt.supports_content_filtering():
1279
filter_tree_path = wt.id2path(file_id)
1280
except errors.NoSuchId:
1281
# file has been deleted
1282
filter_tree_path = None
1284
# Skip the id2path lookup for older formats
1285
filter_tree_path = None
921
1287
versioned = False
923
1289
for suffix, tree, lines in data:
924
1290
if file_id in tree:
925
1291
trans_id = self._conflict_file(name, parent_id, tree, file_id,
1292
suffix, lines, filter_tree_path)
927
1293
file_group.append(trans_id)
928
1294
if set_version and not versioned:
929
1295
self.tt.version_file(file_id, trans_id)
930
1296
versioned = True
931
1297
return file_group
933
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
1299
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
1300
lines=None, filter_tree_path=None):
935
1301
"""Emit a single conflict file."""
936
1302
name = name + '.' + suffix
937
1303
trans_id = self.tt.create_path(name, parent_id)
938
entry = tree.inventory[file_id]
939
create_by_entry(self.tt, entry, tree, trans_id, lines)
1304
create_from_tree(self.tt, trans_id, tree, file_id, lines,
942
1308
def merge_executable(self, file_id, file_status):
943
1309
"""Perform a merge on the execute bit."""
944
1310
executable = [self.executable(t, file_id) for t in (self.base_tree,
945
1311
self.other_tree, self.this_tree)]
946
self._merge_executable(file_id, executable, file_status)
1312
self._merge_executable(file_id, executable, file_status,
1313
resolver=self._three_way)
948
def _merge_executable(self, file_id, executable, file_status):
1315
def _merge_executable(self, file_id, executable, file_status,
949
1317
"""Perform a merge on the execute bit."""
950
1318
base_executable, other_executable, this_executable = executable
951
1319
if file_status == "deleted":
953
winner = self._three_way(*executable)
1321
winner = resolver(*executable)
954
1322
if winner == "conflict":
955
1323
# There must be a None in here, if we have a conflict, but we
956
1324
# need executability since file status was not deleted.
1392
1764
"""Plan an annotate merge using on-the-fly annotation"""
1394
1766
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)
1767
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
1768
self.a_key = self._key_prefix + (self.a_rev,)
1769
self.b_key = self._key_prefix + (self.b_rev,)
1770
self.graph = Graph(self.vf)
1771
heads = self.graph.heads((self.a_key, self.b_key))
1773
# one side dominates, so we can just return its values, yay for
1775
# Ideally we would know that before we get this far
1776
self._head_key = heads.pop()
1777
if self._head_key == self.a_key:
1781
mutter('found dominating revision for %s\n%s > %s', self.vf,
1782
self._head_key[-1], other)
1785
self._head_key = None
1788
def _precache_tip_lines(self):
1789
# Turn this into a no-op, because we will do this later
1792
def _find_recursive_lcas(self):
1793
"""Find all the ancestors back to a unique lca"""
1794
cur_ancestors = (self.a_key, self.b_key)
1795
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
1796
# rather than a key tuple. We will just map that directly to no common
1800
next_lcas = self.graph.find_lca(*cur_ancestors)
1801
# Map a plain NULL_REVISION to a simple no-ancestors
1802
if next_lcas == set([NULL_REVISION]):
1804
# Order the lca's based on when they were merged into the tip
1805
# While the actual merge portion of weave merge uses a set() of
1806
# active revisions, the order of insertion *does* effect the
1807
# implicit ordering of the texts.
1808
for rev_key in cur_ancestors:
1809
ordered_parents = tuple(self.graph.find_merge_order(rev_key,
1811
parent_map[rev_key] = ordered_parents
1812
if len(next_lcas) == 0:
1814
elif len(next_lcas) == 1:
1815
parent_map[list(next_lcas)[0]] = ()
1817
elif len(next_lcas) > 2:
1818
# More than 2 lca's, fall back to grabbing all nodes between
1819
# this and the unique lca.
1820
mutter('More than 2 LCAs, falling back to all nodes for:'
1821
' %s, %s\n=> %s', self.a_key, self.b_key, cur_ancestors)
1822
cur_lcas = next_lcas
1823
while len(cur_lcas) > 1:
1824
cur_lcas = self.graph.find_lca(*cur_lcas)
1825
if len(cur_lcas) == 0:
1826
# No common base to find, use the full ancestry
1829
unique_lca = list(cur_lcas)[0]
1830
if unique_lca == NULL_REVISION:
1831
# find_lca will return a plain 'NULL_REVISION' rather
1832
# than a key tuple when there is no common ancestor, we
1833
# prefer to just use None, because it doesn't confuse
1834
# _get_interesting_texts()
1836
parent_map.update(self._find_unique_parents(next_lcas,
1839
cur_ancestors = next_lcas
1842
def _find_unique_parents(self, tip_keys, base_key):
1843
"""Find ancestors of tip that aren't ancestors of base.
1845
:param tip_keys: Nodes that are interesting
1846
:param base_key: Cull all ancestors of this node
1847
:return: The parent map for all revisions between tip_keys and
1848
base_key. base_key will be included. References to nodes outside of
1849
the ancestor set will also be removed.
1851
# TODO: this would be simpler if find_unique_ancestors took a list
1852
# instead of a single tip, internally it supports it, but it
1853
# isn't a "backwards compatible" api change.
1854
if base_key is None:
1855
parent_map = dict(self.graph.iter_ancestry(tip_keys))
1856
# We remove NULL_REVISION because it isn't a proper tuple key, and
1857
# thus confuses things like _get_interesting_texts, and our logic
1858
# to add the texts into the memory weave.
1859
if NULL_REVISION in parent_map:
1860
parent_map.pop(NULL_REVISION)
1863
for tip in tip_keys:
1865
self.graph.find_unique_ancestors(tip, [base_key]))
1866
parent_map = self.graph.get_parent_map(interesting)
1867
parent_map[base_key] = ()
1868
culled_parent_map, child_map, tails = self._remove_external_references(
1870
# Remove all the tails but base_key
1871
if base_key is not None:
1872
tails.remove(base_key)
1873
self._prune_tails(culled_parent_map, child_map, tails)
1874
# Now remove all the uninteresting 'linear' regions
1875
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
1879
def _remove_external_references(parent_map):
1880
"""Remove references that go outside of the parent map.
1882
:param parent_map: Something returned from Graph.get_parent_map(keys)
1883
:return: (filtered_parent_map, child_map, tails)
1884
filtered_parent_map is parent_map without external references
1885
child_map is the {parent_key: [child_keys]} mapping
1886
tails is a list of nodes that do not have any parents in the map
1888
# TODO: The basic effect of this function seems more generic than
1889
# _PlanMerge. But the specific details of building a child_map,
1890
# and computing tails seems very specific to _PlanMerge.
1891
# Still, should this be in Graph land?
1892
filtered_parent_map = {}
1895
for key, parent_keys in parent_map.iteritems():
1896
culled_parent_keys = [p for p in parent_keys if p in parent_map]
1897
if not culled_parent_keys:
1899
for parent_key in culled_parent_keys:
1900
child_map.setdefault(parent_key, []).append(key)
1901
# TODO: Do we want to do this, it adds overhead for every node,
1902
# just to say that the node has no children
1903
child_map.setdefault(key, [])
1904
filtered_parent_map[key] = culled_parent_keys
1905
return filtered_parent_map, child_map, tails
1908
def _prune_tails(parent_map, child_map, tails_to_remove):
1909
"""Remove tails from the parent map.
1911
This will remove the supplied revisions until no more children have 0
1914
:param parent_map: A dict of {child: [parents]}, this dictionary will
1915
be modified in place.
1916
:param tails_to_remove: A list of tips that should be removed,
1917
this list will be consumed
1918
:param child_map: The reverse dict of parent_map ({parent: [children]})
1919
this dict will be modified
1920
:return: None, parent_map will be modified in place.
1922
while tails_to_remove:
1923
next = tails_to_remove.pop()
1924
parent_map.pop(next)
1925
children = child_map.pop(next)
1926
for child in children:
1927
child_parents = parent_map[child]
1928
child_parents.remove(next)
1929
if len(child_parents) == 0:
1930
tails_to_remove.append(child)
1932
def _get_interesting_texts(self, parent_map):
1933
"""Return a dict of texts we are interested in.
1935
Note that the input is in key tuples, but the output is in plain
1938
:param parent_map: The output from _find_recursive_lcas
1939
:return: A dict of {'revision_id':lines} as returned by
1940
_PlanMergeBase.get_lines()
1942
all_revision_keys = set(parent_map)
1943
all_revision_keys.add(self.a_key)
1944
all_revision_keys.add(self.b_key)
1946
# Everything else is in 'keys' but get_lines is in 'revision_ids'
1947
all_texts = self.get_lines([k[-1] for k in all_revision_keys])
1950
def _build_weave(self):
1951
from bzrlib import weave
1952
self._weave = weave.Weave(weave_name='in_memory_weave',
1953
allow_reserved=True)
1954
parent_map = self._find_recursive_lcas()
1956
all_texts = self._get_interesting_texts(parent_map)
1958
# Note: Unfortunately, the order given by topo_sort will effect the
1959
# ordering resolution in the output. Specifically, if you add A then B,
1960
# then in the output text A lines will show up before B lines. And, of
1961
# course, topo_sort doesn't guarantee any real ordering.
1962
# So we use merge_sort, and add a fake node on the tip.
1963
# This ensures that left-hand parents will always be inserted into the
1964
# weave before right-hand parents.
1965
tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
1966
parent_map[tip_key] = (self.a_key, self.b_key)
1968
for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
1972
# for key in tsort.topo_sort(parent_map):
1973
parent_keys = parent_map[key]
1974
revision_id = key[-1]
1975
parent_ids = [k[-1] for k in parent_keys]
1976
self._weave.add_lines(revision_id, parent_ids,
1977
all_texts[revision_id])
1979
def plan_merge(self):
1980
"""Generate a 'plan' for merging the two revisions.
1982
This involves comparing their texts and determining the cause of
1983
differences. If text A has a line and text B does not, then either the
1984
line was added to text A, or it was deleted from B. Once the causes
1985
are combined, they are written out in the format described in
1986
VersionedFile.plan_merge
1988
if self._head_key is not None: # There was a single head
1989
if self._head_key == self.a_key:
1992
if self._head_key != self.b_key:
1993
raise AssertionError('There was an invalid head: %s != %s'
1994
% (self.b_key, self._head_key))
1996
head_rev = self._head_key[-1]
1997
lines = self.get_lines([head_rev])[head_rev]
1998
return ((plan, line) for line in lines)
1999
return self._weave.plan_merge(self.a_rev, self.b_rev)
1450
2002
class _PlanLCAMerge(_PlanMergeBase):
added
removed
bzrlib/merge.py
