364
352
ensure_null(self.other_basis)]
365
353
if NULL_REVISION in revisions:
366
354
self.base_rev_id = NULL_REVISION
367
self.base_tree = self.revision_tree(self.base_rev_id)
368
self._is_criss_cross = False
370
lcas = self.revision_graph.find_lca(revisions[0], revisions[1])
371
self._is_criss_cross = False
373
self.base_rev_id = NULL_REVISION
375
self.base_rev_id = list(lcas)[0]
376
else: # len(lcas) > 1
378
# find_unique_lca can only handle 2 nodes, so we have to
379
# start back at the beginning. It is a shame to traverse
380
# the graph again, but better than re-implementing
382
self.base_rev_id = self.revision_graph.find_unique_lca(
383
revisions[0], revisions[1])
385
self.base_rev_id = self.revision_graph.find_unique_lca(
387
self._is_criss_cross = True
356
self.base_rev_id, steps = self.revision_graph.find_unique_lca(
357
revisions[0], revisions[1], count_steps=True)
388
358
if self.base_rev_id == NULL_REVISION:
389
359
raise UnrelatedBranches()
390
if self._is_criss_cross:
391
361
warning('Warning: criss-cross merge encountered. See bzr'
392
362
' help criss-cross.')
393
mutter('Criss-cross lcas: %r' % lcas)
394
interesting_revision_ids = [self.base_rev_id]
395
interesting_revision_ids.extend(lcas)
396
interesting_trees = dict((t.get_revision_id(), t)
397
for t in self.this_branch.repository.revision_trees(
398
interesting_revision_ids))
399
self._cached_trees.update(interesting_trees)
400
self.base_tree = interesting_trees.pop(self.base_rev_id)
401
sorted_lca_keys = self.revision_graph.find_merge_order(
403
self._lca_trees = [interesting_trees[key]
404
for key in sorted_lca_keys]
406
self.base_tree = self.revision_tree(self.base_rev_id)
363
self.base_tree = self.revision_tree(self.base_rev_id)
407
364
self.base_is_ancestor = True
408
365
self.base_is_other_ancestor = True
409
mutter('Base revid: %r' % self.base_rev_id)
411
367
def set_base(self, base_revision):
412
368
"""Set the base revision to use for the merge.
452
408
if self.merge_type.supports_cherrypick:
453
409
kwargs['cherrypick'] = (not self.base_is_ancestor or
454
410
not self.base_is_other_ancestor)
455
if self._is_criss_cross and getattr(self.merge_type,
456
'supports_lca_trees', False):
457
kwargs['lca_trees'] = self._lca_trees
458
411
return self.merge_type(pb=self._pb,
459
412
change_reporter=self.change_reporter,
462
def _do_merge_to(self, merge):
464
if self.recurse == 'down':
465
for relpath, file_id in self.this_tree.iter_references():
466
sub_tree = self.this_tree.get_nested_tree(file_id, relpath)
467
other_revision = self.other_tree.get_reference_revision(
469
if other_revision == sub_tree.last_revision():
471
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
472
sub_merge.merge_type = self.merge_type
473
other_branch = self.other_branch.reference_parent(file_id, relpath)
474
sub_merge.set_other_revision(other_revision, other_branch)
475
base_revision = self.base_tree.get_reference_revision(file_id)
476
sub_merge.base_tree = \
477
sub_tree.branch.repository.revision_tree(base_revision)
478
sub_merge.base_rev_id = base_revision
481
415
def do_merge(self):
482
416
self.this_tree.lock_tree_write()
417
if self.base_tree is not None:
418
self.base_tree.lock_read()
419
if self.other_tree is not None:
420
self.other_tree.lock_read()
422
merge = self.make_merger()
424
if self.recurse == 'down':
425
for relpath, file_id in self.this_tree.iter_references():
426
sub_tree = self.this_tree.get_nested_tree(file_id, relpath)
427
other_revision = self.other_tree.get_reference_revision(
429
if other_revision == sub_tree.last_revision():
431
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
432
sub_merge.merge_type = self.merge_type
433
other_branch = self.other_branch.reference_parent(file_id, relpath)
434
sub_merge.set_other_revision(other_revision, other_branch)
435
base_revision = self.base_tree.get_reference_revision(file_id)
436
sub_merge.base_tree = \
437
sub_tree.branch.repository.revision_tree(base_revision)
438
sub_merge.base_rev_id = base_revision
442
if self.other_tree is not None:
443
self.other_tree.unlock()
484
444
if self.base_tree is not None:
485
self.base_tree.lock_read()
487
if self.other_tree is not None:
488
self.other_tree.lock_read()
490
merge = self.make_merger()
491
self._do_merge_to(merge)
493
if self.other_tree is not None:
494
self.other_tree.unlock()
496
if self.base_tree is not None:
497
self.base_tree.unlock()
445
self.base_tree.unlock()
499
446
self.this_tree.unlock()
500
447
if len(merge.cooked_conflicts) == 0:
501
448
if not self.ignore_zero and not is_quiet():
701
613
result.append((file_id, changed, parents3, names3, executable3))
704
def _entries_lca(self):
705
"""Gather data about files modified between multiple trees.
707
This compares OTHER versus all LCA trees, and for interesting entries,
708
it then compares with THIS and BASE.
710
For the multi-valued entries, the format will be (BASE, [lca1, lca2])
711
:return: [(file_id, changed, parents, names, executable)]
712
file_id Simple file_id of the entry
713
changed Boolean, True if the kind or contents changed
715
parents ((base, [parent_id, in, lcas]), parent_id_other,
717
names ((base, [name, in, lcas]), name_in_other, name_in_this)
718
executable ((base, [exec, in, lcas]), exec_in_other, exec_in_this)
720
if self.interesting_files is not None:
721
lookup_trees = [self.this_tree, self.base_tree]
722
lookup_trees.extend(self._lca_trees)
723
# I think we should include the lca trees as well
724
interesting_ids = self.other_tree.paths2ids(self.interesting_files,
727
interesting_ids = self.interesting_ids
729
walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
731
base_inventory = self.base_tree.inventory
732
this_inventory = self.this_tree.inventory
733
for path, file_id, other_ie, lca_values in walker.iter_all():
734
# Is this modified at all from any of the other trees?
736
other_ie = _none_entry
737
if interesting_ids is not None and file_id not in interesting_ids:
740
# If other_revision is found in any of the lcas, that means this
741
# node is uninteresting. This is because when merging, if there are
742
# multiple heads(), we have to create a new node. So if we didn't,
743
# we know that the ancestry is linear, and that OTHER did not
745
# See doc/developers/lca_merge_resolution.txt for details
746
other_revision = other_ie.revision
747
if other_revision is not None:
748
# We can't use this shortcut when other_revision is None,
749
# because it may be None because things are WorkingTrees, and
750
# not because it is *actually* None.
751
is_unmodified = False
752
for lca_path, ie in lca_values:
753
if ie is not None and ie.revision == other_revision:
760
for lca_path, lca_ie in lca_values:
762
lca_entries.append(_none_entry)
764
lca_entries.append(lca_ie)
766
if file_id in base_inventory:
767
base_ie = base_inventory[file_id]
769
base_ie = _none_entry
771
if file_id in this_inventory:
772
this_ie = this_inventory[file_id]
774
this_ie = _none_entry
780
for lca_ie in lca_entries:
781
lca_kinds.append(lca_ie.kind)
782
lca_parent_ids.append(lca_ie.parent_id)
783
lca_names.append(lca_ie.name)
784
lca_executable.append(lca_ie.executable)
786
kind_winner = self._lca_multi_way(
787
(base_ie.kind, lca_kinds),
788
other_ie.kind, this_ie.kind)
789
parent_id_winner = self._lca_multi_way(
790
(base_ie.parent_id, lca_parent_ids),
791
other_ie.parent_id, this_ie.parent_id)
792
name_winner = self._lca_multi_way(
793
(base_ie.name, lca_names),
794
other_ie.name, this_ie.name)
796
content_changed = True
797
if kind_winner == 'this':
798
# No kind change in OTHER, see if there are *any* changes
799
if other_ie.kind == 'directory':
800
if parent_id_winner == 'this' and name_winner == 'this':
801
# No change for this directory in OTHER, skip
803
content_changed = False
804
elif other_ie.kind is None or other_ie.kind == 'file':
805
def get_sha1(ie, tree):
806
if ie.kind != 'file':
808
return tree.get_file_sha1(file_id)
809
base_sha1 = get_sha1(base_ie, self.base_tree)
810
lca_sha1s = [get_sha1(ie, tree) for ie, tree
811
in zip(lca_entries, self._lca_trees)]
812
this_sha1 = get_sha1(this_ie, self.this_tree)
813
other_sha1 = get_sha1(other_ie, self.other_tree)
814
sha1_winner = self._lca_multi_way(
815
(base_sha1, lca_sha1s), other_sha1, this_sha1,
816
allow_overriding_lca=False)
817
exec_winner = self._lca_multi_way(
818
(base_ie.executable, lca_executable),
819
other_ie.executable, this_ie.executable)
820
if (parent_id_winner == 'this' and name_winner == 'this'
821
and sha1_winner == 'this' and exec_winner == 'this'):
822
# No kind, parent, name, exec, or content change for
823
# OTHER, so this node is not considered interesting
825
if sha1_winner == 'this':
826
content_changed = False
827
elif other_ie.kind == 'symlink':
828
def get_target(ie, tree):
829
if ie.kind != 'symlink':
831
return tree.get_symlink_target(file_id)
832
base_target = get_target(base_ie, self.base_tree)
833
lca_targets = [get_target(ie, tree) for ie, tree
834
in zip(lca_entries, self._lca_trees)]
835
this_target = get_target(this_ie, self.this_tree)
836
other_target = get_target(other_ie, self.other_tree)
837
target_winner = self._lca_multi_way(
838
(base_target, lca_targets),
839
other_target, this_target)
840
if (parent_id_winner == 'this' and name_winner == 'this'
841
and target_winner == 'this'):
842
# No kind, parent, name, or symlink target change
845
if target_winner == 'this':
846
content_changed = False
847
elif other_ie.kind == 'tree-reference':
848
# The 'changed' information seems to be handled at a higher
849
# level. At least, _entries3 returns False for content
850
# changed, even when at a new revision_id.
851
content_changed = False
852
if (parent_id_winner == 'this' and name_winner == 'this'):
853
# Nothing interesting
856
raise AssertionError('unhandled kind: %s' % other_ie.kind)
857
# XXX: We need to handle kind == 'symlink'
859
# If we have gotten this far, that means something has changed
860
result.append((file_id, content_changed,
861
((base_ie.parent_id, lca_parent_ids),
862
other_ie.parent_id, this_ie.parent_id),
863
((base_ie.name, lca_names),
864
other_ie.name, this_ie.name),
865
((base_ie.executable, lca_executable),
866
other_ie.executable, this_ie.executable)
871
616
def fix_root(self):
873
618
self.tt.final_kind(self.tt.root)
965
def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
966
"""Consider LCAs when determining whether a change has occurred.
968
If LCAS are all identical, this is the same as a _three_way comparison.
970
:param bases: value in (BASE, [LCAS])
971
:param other: value in OTHER
972
:param this: value in THIS
973
:param allow_overriding_lca: If there is more than one unique lca
974
value, allow OTHER to override THIS if it has a new value, and
975
THIS only has an lca value, or vice versa. This is appropriate for
976
truly scalar values, not as much for non-scalars.
977
:return: 'this', 'other', or 'conflict' depending on whether an entry
980
# See doc/developers/lca_tree_merging.txt for details about this
983
# Either Ambiguously clean, or nothing was actually changed. We
986
base_val, lca_vals = bases
987
# Remove 'base_val' from the lca_vals, because it is not interesting
988
filtered_lca_vals = [lca_val for lca_val in lca_vals
989
if lca_val != base_val]
990
if len(filtered_lca_vals) == 0:
991
return Merge3Merger._three_way(base_val, other, this)
993
unique_lca_vals = set(filtered_lca_vals)
994
if len(unique_lca_vals) == 1:
995
return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
997
if allow_overriding_lca:
998
if other in unique_lca_vals:
999
if this in unique_lca_vals:
1000
# Each side picked a different lca, conflict
1003
# This has a value which supersedes both lca values, and
1004
# other only has an lca value
1006
elif this in unique_lca_vals:
1007
# OTHER has a value which supersedes both lca values, and this
1008
# only has an lca value
1011
# At this point, the lcas disagree, and the tips disagree
1015
707
def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
1016
708
"""Do a three-way test on a scalar.
1017
709
Return "this", "other" or "conflict", depending whether a value wins.
1119
810
base_pair = contents_pair(self.base_tree)
1120
811
other_pair = contents_pair(self.other_tree)
1122
this_pair = contents_pair(self.this_tree)
1123
lca_pairs = [contents_pair(tree) for tree in self._lca_trees]
1124
winner = self._lca_multi_way((base_pair, lca_pairs), other_pair,
1125
this_pair, allow_overriding_lca=False)
1127
if base_pair == other_pair:
1130
# We delayed evaluating this_pair as long as we can to avoid
1131
# unnecessary sha1 calculation
1132
this_pair = contents_pair(self.this_tree)
1133
winner = self._three_way(base_pair, other_pair, this_pair)
1134
if winner == 'this':
1135
# No interesting changes introduced by OTHER
1137
trans_id = self.tt.trans_id_file_id(file_id)
1138
if winner == 'other':
1139
# OTHER is a straight winner, so replace this contents with other
1140
file_in_this = file_id in self.this_tree
1142
# Remove any existing contents
1143
self.tt.delete_contents(trans_id)
1144
if file_id in self.other_tree:
1145
# OTHER changed the file
1146
create_from_tree(self.tt, trans_id,
1147
self.other_tree, file_id)
1148
if not file_in_this:
1149
self.tt.version_file(file_id, trans_id)
1152
# OTHER deleted the file
1153
self.tt.unversion_file(trans_id)
1156
# We have a hypothetical conflict, but if we have files, then we
1157
# can try to merge the content
1158
if this_pair[0] == 'file' and other_pair[0] == 'file':
812
if base_pair == other_pair:
813
# OTHER introduced no changes
815
this_pair = contents_pair(self.this_tree)
816
if this_pair == other_pair:
817
# THIS and OTHER introduced the same changes
820
trans_id = self.tt.trans_id_file_id(file_id)
821
if this_pair == base_pair:
822
# only OTHER introduced changes
823
if file_id in self.this_tree:
824
# Remove any existing contents
825
self.tt.delete_contents(trans_id)
826
if file_id in self.other_tree:
827
# OTHER changed the file
828
create_by_entry(self.tt,
829
self.other_tree.inventory[file_id],
830
self.other_tree, trans_id)
831
if file_id not in self.this_tree.inventory:
832
self.tt.version_file(file_id, trans_id)
834
elif file_id in self.this_tree.inventory:
835
# OTHER deleted the file
836
self.tt.unversion_file(trans_id)
838
#BOTH THIS and OTHER introduced changes; scalar conflict
839
elif this_pair[0] == "file" and other_pair[0] == "file":
1159
840
# THIS and OTHER are both files, so text merge. Either
1160
841
# BASE is a file, or both converted to files, so at least we
1161
842
# have agreement that output should be a file.
1249
931
versioned = True
1250
932
return file_group
1252
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
934
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
1254
936
"""Emit a single conflict file."""
1255
937
name = name + '.' + suffix
1256
938
trans_id = self.tt.create_path(name, parent_id)
1257
create_from_tree(self.tt, trans_id, tree, file_id, lines)
939
entry = tree.inventory[file_id]
940
create_by_entry(self.tt, entry, tree, trans_id, lines)
1260
943
def merge_executable(self, file_id, file_status):
1261
944
"""Perform a merge on the execute bit."""
1262
945
executable = [self.executable(t, file_id) for t in (self.base_tree,
1263
946
self.other_tree, self.this_tree)]
1264
self._merge_executable(file_id, executable, file_status,
1265
resolver=self._three_way)
947
self._merge_executable(file_id, executable, file_status)
1267
def _merge_executable(self, file_id, executable, file_status,
949
def _merge_executable(self, file_id, executable, file_status):
1269
950
"""Perform a merge on the execute bit."""
1270
951
base_executable, other_executable, this_executable = executable
1271
952
if file_status == "deleted":
1273
winner = resolver(*executable)
954
winner = self._three_way(*executable)
1274
955
if winner == "conflict":
1275
956
# There must be a None in here, if we have a conflict, but we
1276
957
# need executability since file status was not deleted.
1816
1491
self.graph.find_unique_ancestors(tip, [base_key]))
1817
1492
parent_map = self.graph.get_parent_map(interesting)
1818
1493
parent_map[base_key] = ()
1819
culled_parent_map, child_map, tails = self._remove_external_references(
1821
# Remove all the tails but base_key
1822
if base_key is not None:
1823
tails.remove(base_key)
1824
self._prune_tails(culled_parent_map, child_map, tails)
1825
# Now remove all the uninteresting 'linear' regions
1826
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
1830
def _remove_external_references(parent_map):
1831
"""Remove references that go outside of the parent map.
1833
:param parent_map: Something returned from Graph.get_parent_map(keys)
1834
:return: (filtered_parent_map, child_map, tails)
1835
filtered_parent_map is parent_map without external references
1836
child_map is the {parent_key: [child_keys]} mapping
1837
tails is a list of nodes that do not have any parents in the map
1839
# TODO: The basic effect of this function seems more generic than
1840
# _PlanMerge. But the specific details of building a child_map,
1841
# and computing tails seems very specific to _PlanMerge.
1842
# Still, should this be in Graph land?
1843
filtered_parent_map = {}
1494
culled_parent_map = {}
1495
extra_base_ancestors = set()
1846
1496
for key, parent_keys in parent_map.iteritems():
1847
culled_parent_keys = [p for p in parent_keys if p in parent_map]
1848
if not culled_parent_keys:
1850
for parent_key in culled_parent_keys:
1851
child_map.setdefault(parent_key, []).append(key)
1852
# TODO: Do we want to do this, it adds overhead for every node,
1853
# just to say that the node has no children
1854
child_map.setdefault(key, [])
1855
filtered_parent_map[key] = culled_parent_keys
1856
return filtered_parent_map, child_map, tails
1859
def _prune_tails(parent_map, child_map, tails_to_remove):
1860
"""Remove tails from the parent map.
1862
This will remove the supplied revisions until no more children have 0
1865
:param parent_map: A dict of {child: [parents]}, this dictionary will
1866
be modified in place.
1867
:param tails_to_remove: A list of tips that should be removed,
1868
this list will be consumed
1869
:param child_map: The reverse dict of parent_map ({parent: [children]})
1870
this dict will be modified
1871
:return: None, parent_map will be modified in place.
1873
while tails_to_remove:
1874
next = tails_to_remove.pop()
1875
parent_map.pop(next)
1876
children = child_map.pop(next)
1877
for child in children:
1878
child_parents = parent_map[child]
1879
child_parents.remove(next)
1880
if len(child_parents) == 0:
1881
tails_to_remove.append(child)
1497
culled_parent_keys = tuple([p for p in parent_keys
1498
if p in parent_map])
1499
if not culled_parent_keys and key is not base_key:
1500
# We have another 'tail', make sure to bring it into the
1501
# ancestry, so that we don't think all of its lines are unique.
1502
lcas = self.graph.find_lca(key, base_key)
1503
if lcas == set([NULL_REVISION]):
1506
# Nothing to do, no common ancestor
1509
# Technically, this isn't 100% correct, but it is better
1510
# than nothing. If we have more than 1 LCA, we probably
1511
# should keep tracking the rabbit down the hole, so that we
1512
# get proper annotations for lines. For now, though, we
1513
# just add the first lca, and live with it
1515
extra_base_ancestors.add(lca)
1516
culled_parent_keys = (lca,)
1517
if lca not in culled_parent_map:
1518
culled_parent_map[lca] = ()
1519
culled_parent_map[key] = culled_parent_keys
1520
if extra_base_ancestors:
1521
culled_parent_map[base_key] = self.graph.find_merge_order(base_key,
1522
extra_base_ancestors)
1523
return culled_parent_map
1883
1525
def _get_interesting_texts(self, parent_map):
1884
1526
"""Return a dict of texts we are interested in.
added
removed
bzrlib/merge.py
