450
405
if self.merge_type.supports_cherrypick:
451
406
kwargs['cherrypick'] = (not self.base_is_ancestor or
452
407
not self.base_is_other_ancestor)
453
if self._is_criss_cross and getattr(self.merge_type,
454
'supports_lca_trees', False):
455
kwargs['lca_trees'] = self._lca_trees
456
408
return self.merge_type(pb=self._pb,
457
409
change_reporter=self.change_reporter,
460
def _do_merge_to(self, merge):
462
if self.recurse == 'down':
463
for relpath, file_id in self.this_tree.iter_references():
464
sub_tree = self.this_tree.get_nested_tree(file_id, relpath)
465
other_revision = self.other_tree.get_reference_revision(
467
if other_revision == sub_tree.last_revision():
469
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
470
sub_merge.merge_type = self.merge_type
471
other_branch = self.other_branch.reference_parent(file_id, relpath)
472
sub_merge.set_other_revision(other_revision, other_branch)
473
base_revision = self.base_tree.get_reference_revision(file_id)
474
sub_merge.base_tree = \
475
sub_tree.branch.repository.revision_tree(base_revision)
476
sub_merge.base_rev_id = base_revision
479
412
def do_merge(self):
480
413
self.this_tree.lock_tree_write()
414
if self.base_tree is not None:
415
self.base_tree.lock_read()
416
if self.other_tree is not None:
417
self.other_tree.lock_read()
419
merge = self.make_merger()
421
if self.recurse == 'down':
422
for path, file_id in self.this_tree.iter_references():
423
sub_tree = self.this_tree.get_nested_tree(file_id, path)
424
other_revision = self.other_tree.get_reference_revision(
426
if other_revision == sub_tree.last_revision():
428
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
429
sub_merge.merge_type = self.merge_type
430
relpath = self.this_tree.relpath(path)
431
other_branch = self.other_branch.reference_parent(file_id, relpath)
432
sub_merge.set_other_revision(other_revision, other_branch)
433
base_revision = self.base_tree.get_reference_revision(file_id)
434
sub_merge.base_tree = \
435
sub_tree.branch.repository.revision_tree(base_revision)
436
sub_merge.base_rev_id = base_revision
440
if self.other_tree is not None:
441
self.other_tree.unlock()
482
442
if self.base_tree is not None:
483
self.base_tree.lock_read()
485
if self.other_tree is not None:
486
self.other_tree.lock_read()
488
merge = self.make_merger()
489
self._do_merge_to(merge)
491
if self.other_tree is not None:
492
self.other_tree.unlock()
494
if self.base_tree is not None:
495
self.base_tree.unlock()
443
self.base_tree.unlock()
497
444
self.this_tree.unlock()
498
445
if len(merge.cooked_conflicts) == 0:
499
446
if not self.ignore_zero and not is_quiet():
699
611
result.append((file_id, changed, parents3, names3, executable3))
702
def _entries_lca(self):
703
"""Gather data about files modified between multiple trees.
705
This compares OTHER versus all LCA trees, and for interesting entries,
706
it then compares with THIS and BASE.
708
For the multi-valued entries, the format will be (BASE, [lca1, lca2])
709
:return: [(file_id, changed, parents, names, executable)]
710
file_id Simple file_id of the entry
711
changed Boolean, True if the kind or contents changed
713
parents ((base, [parent_id, in, lcas]), parent_id_other,
715
names ((base, [name, in, lcas]), name_in_other, name_in_this)
716
executable ((base, [exec, in, lcas]), exec_in_other, exec_in_this)
718
if self.interesting_files is not None:
719
lookup_trees = [self.this_tree, self.base_tree]
720
lookup_trees.extend(self._lca_trees)
721
# I think we should include the lca trees as well
722
interesting_ids = self.other_tree.paths2ids(self.interesting_files,
725
interesting_ids = self.interesting_ids
727
walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
729
base_inventory = self.base_tree.inventory
730
this_inventory = self.this_tree.inventory
731
for path, file_id, other_ie, lca_values in walker.iter_all():
732
# Is this modified at all from any of the other trees?
734
other_ie = _none_entry
735
if interesting_ids is not None and file_id not in interesting_ids:
738
# If other_revision is found in any of the lcas, that means this
739
# node is uninteresting. This is because when merging, if there are
740
# multiple heads(), we have to create a new node. So if we didn't,
741
# we know that the ancestry is linear, and that OTHER did not
743
# See doc/developers/lca_merge_resolution.txt for details
744
other_revision = other_ie.revision
745
if other_revision is not None:
746
# We can't use this shortcut when other_revision is None,
747
# because it may be None because things are WorkingTrees, and
748
# not because it is *actually* None.
749
is_unmodified = False
750
for lca_path, ie in lca_values:
751
if ie is not None and ie.revision == other_revision:
758
for lca_path, lca_ie in lca_values:
760
lca_entries.append(_none_entry)
762
lca_entries.append(lca_ie)
764
if file_id in base_inventory:
765
base_ie = base_inventory[file_id]
767
base_ie = _none_entry
769
if file_id in this_inventory:
770
this_ie = this_inventory[file_id]
772
this_ie = _none_entry
778
for lca_ie in lca_entries:
779
lca_kinds.append(lca_ie.kind)
780
lca_parent_ids.append(lca_ie.parent_id)
781
lca_names.append(lca_ie.name)
782
lca_executable.append(lca_ie.executable)
784
kind_winner = self._lca_multi_way(
785
(base_ie.kind, lca_kinds),
786
other_ie.kind, this_ie.kind)
787
parent_id_winner = self._lca_multi_way(
788
(base_ie.parent_id, lca_parent_ids),
789
other_ie.parent_id, this_ie.parent_id)
790
name_winner = self._lca_multi_way(
791
(base_ie.name, lca_names),
792
other_ie.name, this_ie.name)
794
content_changed = True
795
if kind_winner == 'this':
796
# No kind change in OTHER, see if there are *any* changes
797
if other_ie.kind == None:
798
# No content and 'this' wins the kind, so skip this?
801
elif other_ie.kind == 'directory':
802
if parent_id_winner == 'this' and name_winner == 'this':
803
# No change for this directory in OTHER, skip
805
content_changed = False
806
elif other_ie.kind == 'file':
807
def get_sha1(ie, tree):
808
if ie.kind != 'file':
810
return tree.get_file_sha1(file_id)
811
base_sha1 = get_sha1(base_ie, self.base_tree)
812
lca_sha1s = [get_sha1(ie, tree) for ie, tree
813
in zip(lca_entries, self._lca_trees)]
814
this_sha1 = get_sha1(this_ie, self.this_tree)
815
other_sha1 = get_sha1(other_ie, self.other_tree)
816
sha1_winner = self._lca_multi_way(
817
(base_sha1, lca_sha1s), other_sha1, this_sha1,
818
allow_overriding_lca=False)
819
exec_winner = self._lca_multi_way(
820
(base_ie.executable, lca_executable),
821
other_ie.executable, this_ie.executable)
822
if (parent_id_winner == 'this' and name_winner == 'this'
823
and sha1_winner == 'this' and exec_winner == 'this'):
824
# No kind, parent, name, exec, or content change for
825
# OTHER, so this node is not considered interesting
827
if sha1_winner == 'this':
828
content_changed = False
829
elif other_ie.kind == 'symlink':
830
def get_target(ie, tree):
831
if ie.kind != 'symlink':
833
return tree.get_symlink_target(file_id)
834
base_target = get_target(base_ie, self.base_tree)
835
lca_targets = [get_target(ie, tree) for ie, tree
836
in zip(lca_entries, self._lca_trees)]
837
this_target = get_target(this_ie, self.this_tree)
838
other_target = get_target(other_ie, self.other_tree)
839
target_winner = self._lca_multi_way(
840
(base_target, lca_targets),
841
other_target, this_target)
842
if (parent_id_winner == 'this' and name_winner == 'this'
843
and target_winner == 'this'):
844
# No kind, parent, name, or symlink target change
847
if target_winner == 'this':
848
content_changed = False
849
elif other_ie.kind == 'tree-reference':
850
# The 'changed' information seems to be handled at a higher
851
# level. At least, _entries3 returns False for content
852
# changed, even when at a new revision_id.
853
content_changed = False
854
if (parent_id_winner == 'this' and name_winner == 'this'):
855
# Nothing interesting
858
raise AssertionError('unhandled kind: %s' % other_ie.kind)
859
# XXX: We need to handle kind == 'symlink'
861
# If we have gotten this far, that means something has changed
862
result.append((file_id, content_changed,
863
((base_ie.parent_id, lca_parent_ids),
864
other_ie.parent_id, this_ie.parent_id),
865
((base_ie.name, lca_names),
866
other_ie.name, this_ie.name),
867
((base_ie.executable, lca_executable),
868
other_ie.executable, this_ie.executable)
873
614
def fix_root(self):
875
616
self.tt.final_kind(self.tt.root)
967
def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
968
"""Consider LCAs when determining whether a change has occurred.
970
If LCAS are all identical, this is the same as a _three_way comparison.
972
:param bases: value in (BASE, [LCAS])
973
:param other: value in OTHER
974
:param this: value in THIS
975
:param allow_overriding_lca: If there is more than one unique lca
976
value, allow OTHER to override THIS if it has a new value, and
977
THIS only has an lca value, or vice versa. This is appropriate for
978
truly scalar values, not as much for non-scalars.
979
:return: 'this', 'other', or 'conflict' depending on whether an entry
982
# See doc/developers/lca_merge_resolution.txt for details about this
985
# Either Ambiguously clean, or nothing was actually changed. We
988
base_val, lca_vals = bases
989
# Remove 'base_val' from the lca_vals, because it is not interesting
990
filtered_lca_vals = [lca_val for lca_val in lca_vals
991
if lca_val != base_val]
992
if len(filtered_lca_vals) == 0:
993
return Merge3Merger._three_way(base_val, other, this)
995
unique_lca_vals = set(filtered_lca_vals)
996
if len(unique_lca_vals) == 1:
997
return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
999
if allow_overriding_lca:
1000
if other in unique_lca_vals:
1001
if this in unique_lca_vals:
1002
# Each side picked a different lca, conflict
1005
# This has a value which supersedes both lca values, and
1006
# other only has an lca value
1008
elif this in unique_lca_vals:
1009
# OTHER has a value which supersedes both lca values, and this
1010
# only has an lca value
1013
# At this point, the lcas disagree, and the tips disagree
1017
705
def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
1018
706
"""Do a three-way test on a scalar.
1019
707
Return "this", "other" or "conflict", depending whether a value wins.
1241
929
versioned = True
1242
930
return file_group
1244
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
932
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
1246
934
"""Emit a single conflict file."""
1247
935
name = name + '.' + suffix
1248
936
trans_id = self.tt.create_path(name, parent_id)
1249
create_from_tree(self.tt, trans_id, tree, file_id, lines)
937
entry = tree.inventory[file_id]
938
create_by_entry(self.tt, entry, tree, trans_id, lines)
1252
941
def merge_executable(self, file_id, file_status):
1253
942
"""Perform a merge on the execute bit."""
1254
943
executable = [self.executable(t, file_id) for t in (self.base_tree,
1255
944
self.other_tree, self.this_tree)]
1256
self._merge_executable(file_id, executable, file_status,
1257
resolver=self._three_way)
945
self._merge_executable(file_id, executable, file_status)
1259
def _merge_executable(self, file_id, executable, file_status,
947
def _merge_executable(self, file_id, executable, file_status):
1261
948
"""Perform a merge on the execute bit."""
1262
949
base_executable, other_executable, this_executable = executable
1263
950
if file_status == "deleted":
1265
winner = resolver(*executable)
952
winner = self._three_way(*executable)
1266
953
if winner == "conflict":
1267
954
# There must be a None in here, if we have a conflict, but we
1268
955
# need executability since file status was not deleted.
1706
1370
class _PlanMerge(_PlanMergeBase):
1707
1371
"""Plan an annotate merge using on-the-fly annotation"""
1709
def __init__(self, a_rev, b_rev, vf, key_prefix):
1710
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
1711
self.a_key = self._key_prefix + (self.a_rev,)
1712
self.b_key = self._key_prefix + (self.b_rev,)
1713
self.graph = Graph(self.vf)
1714
heads = self.graph.heads((self.a_key, self.b_key))
1716
# one side dominates, so we can just return its values, yay for
1718
# Ideally we would know that before we get this far
1719
self._head_key = heads.pop()
1720
if self._head_key == self.a_key:
1724
mutter('found dominating revision for %s\n%s > %s', self.vf,
1725
self._head_key[-1], other)
1728
self._head_key = None
1731
def _precache_tip_lines(self):
1732
# Turn this into a no-op, because we will do this later
1735
def _find_recursive_lcas(self):
1736
"""Find all the ancestors back to a unique lca"""
1737
cur_ancestors = (self.a_key, self.b_key)
1738
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
1739
# rather than a key tuple. We will just map that directly to no common
1743
next_lcas = self.graph.find_lca(*cur_ancestors)
1744
# Map a plain NULL_REVISION to a simple no-ancestors
1745
if next_lcas == set([NULL_REVISION]):
1747
# Order the lca's based on when they were merged into the tip
1748
# While the actual merge portion of weave merge uses a set() of
1749
# active revisions, the order of insertion *does* effect the
1750
# implicit ordering of the texts.
1751
for rev_key in cur_ancestors:
1752
ordered_parents = tuple(self.graph.find_merge_order(rev_key,
1754
parent_map[rev_key] = ordered_parents
1755
if len(next_lcas) == 0:
1757
elif len(next_lcas) == 1:
1758
parent_map[list(next_lcas)[0]] = ()
1760
elif len(next_lcas) > 2:
1761
# More than 2 lca's, fall back to grabbing all nodes between
1762
# this and the unique lca.
1763
mutter('More than 2 LCAs, falling back to all nodes for:'
1764
' %s, %s\n=> %s', self.a_key, self.b_key, cur_ancestors)
1765
cur_lcas = next_lcas
1766
while len(cur_lcas) > 1:
1767
cur_lcas = self.graph.find_lca(*cur_lcas)
1768
if len(cur_lcas) == 0:
1769
# No common base to find, use the full ancestry
1772
unique_lca = list(cur_lcas)[0]
1773
if unique_lca == NULL_REVISION:
1774
# find_lca will return a plain 'NULL_REVISION' rather
1775
# than a key tuple when there is no common ancestor, we
1776
# prefer to just use None, because it doesn't confuse
1777
# _get_interesting_texts()
1779
parent_map.update(self._find_unique_parents(next_lcas,
1782
cur_ancestors = next_lcas
1785
def _find_unique_parents(self, tip_keys, base_key):
1786
"""Find ancestors of tip that aren't ancestors of base.
1788
:param tip_keys: Nodes that are interesting
1789
:param base_key: Cull all ancestors of this node
1790
:return: The parent map for all revisions between tip_keys and
1791
base_key. base_key will be included. References to nodes outside of
1792
the ancestor set will also be removed.
1794
# TODO: this would be simpler if find_unique_ancestors took a list
1795
# instead of a single tip, internally it supports it, but it
1796
# isn't a "backwards compatible" api change.
1797
if base_key is None:
1798
parent_map = dict(self.graph.iter_ancestry(tip_keys))
1799
# We remove NULL_REVISION because it isn't a proper tuple key, and
1800
# thus confuses things like _get_interesting_texts, and our logic
1801
# to add the texts into the memory weave.
1802
if NULL_REVISION in parent_map:
1803
parent_map.pop(NULL_REVISION)
1806
for tip in tip_keys:
1808
self.graph.find_unique_ancestors(tip, [base_key]))
1809
parent_map = self.graph.get_parent_map(interesting)
1810
parent_map[base_key] = ()
1811
culled_parent_map, child_map, tails = self._remove_external_references(
1813
# Remove all the tails but base_key
1814
if base_key is not None:
1815
tails.remove(base_key)
1816
self._prune_tails(culled_parent_map, child_map, tails)
1817
# Now remove all the uninteresting 'linear' regions
1818
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
1822
def _remove_external_references(parent_map):
1823
"""Remove references that go outside of the parent map.
1825
:param parent_map: Something returned from Graph.get_parent_map(keys)
1826
:return: (filtered_parent_map, child_map, tails)
1827
filtered_parent_map is parent_map without external references
1828
child_map is the {parent_key: [child_keys]} mapping
1829
tails is a list of nodes that do not have any parents in the map
1831
# TODO: The basic effect of this function seems more generic than
1832
# _PlanMerge. But the specific details of building a child_map,
1833
# and computing tails seems very specific to _PlanMerge.
1834
# Still, should this be in Graph land?
1835
filtered_parent_map = {}
1838
for key, parent_keys in parent_map.iteritems():
1839
culled_parent_keys = [p for p in parent_keys if p in parent_map]
1840
if not culled_parent_keys:
1842
for parent_key in culled_parent_keys:
1843
child_map.setdefault(parent_key, []).append(key)
1844
# TODO: Do we want to do this, it adds overhead for every node,
1845
# just to say that the node has no children
1846
child_map.setdefault(key, [])
1847
filtered_parent_map[key] = culled_parent_keys
1848
return filtered_parent_map, child_map, tails
1851
def _prune_tails(parent_map, child_map, tails_to_remove):
1852
"""Remove tails from the parent map.
1854
This will remove the supplied revisions until no more children have 0
1857
:param parent_map: A dict of {child: [parents]}, this dictionary will
1858
be modified in place.
1859
:param tails_to_remove: A list of tips that should be removed,
1860
this list will be consumed
1861
:param child_map: The reverse dict of parent_map ({parent: [children]})
1862
this dict will be modified
1863
:return: None, parent_map will be modified in place.
1865
while tails_to_remove:
1866
next = tails_to_remove.pop()
1867
parent_map.pop(next)
1868
children = child_map.pop(next)
1869
for child in children:
1870
child_parents = parent_map[child]
1871
child_parents.remove(next)
1872
if len(child_parents) == 0:
1873
tails_to_remove.append(child)
1875
def _get_interesting_texts(self, parent_map):
1876
"""Return a dict of texts we are interested in.
1878
Note that the input is in key tuples, but the output is in plain
1881
:param parent_map: The output from _find_recursive_lcas
1882
:return: A dict of {'revision_id':lines} as returned by
1883
_PlanMergeBase.get_lines()
1885
all_revision_keys = set(parent_map)
1886
all_revision_keys.add(self.a_key)
1887
all_revision_keys.add(self.b_key)
1889
# Everything else is in 'keys' but get_lines is in 'revision_ids'
1890
all_texts = self.get_lines([k[-1] for k in all_revision_keys])
1893
def _build_weave(self):
1894
from bzrlib import weave
1895
self._weave = weave.Weave(weave_name='in_memory_weave',
1896
allow_reserved=True)
1897
parent_map = self._find_recursive_lcas()
1899
all_texts = self._get_interesting_texts(parent_map)
1901
# Note: Unfortunately, the order given by topo_sort will effect the
1902
# ordering resolution in the output. Specifically, if you add A then B,
1903
# then in the output text A lines will show up before B lines. And, of
1904
# course, topo_sort doesn't guarantee any real ordering.
1905
# So we use merge_sort, and add a fake node on the tip.
1906
# This ensures that left-hand parents will always be inserted into the
1907
# weave before right-hand parents.
1908
tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
1909
parent_map[tip_key] = (self.a_key, self.b_key)
1911
for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
1915
# for key in tsort.topo_sort(parent_map):
1916
parent_keys = parent_map[key]
1917
revision_id = key[-1]
1918
parent_ids = [k[-1] for k in parent_keys]
1919
self._weave.add_lines(revision_id, parent_ids,
1920
all_texts[revision_id])
1922
def plan_merge(self):
1923
"""Generate a 'plan' for merging the two revisions.
1925
This involves comparing their texts and determining the cause of
1926
differences. If text A has a line and text B does not, then either the
1927
line was added to text A, or it was deleted from B. Once the causes
1928
are combined, they are written out in the format described in
1929
VersionedFile.plan_merge
1931
if self._head_key is not None: # There was a single head
1932
if self._head_key == self.a_key:
1935
if self._head_key != self.b_key:
1936
raise AssertionError('There was an invalid head: %s != %s'
1937
% (self.b_key, self._head_key))
1939
head_rev = self._head_key[-1]
1940
lines = self.get_lines([head_rev])[head_rev]
1941
return ((plan, line) for line in lines)
1942
return self._weave.plan_merge(self.a_rev, self.b_rev)
1373
def __init__(self, a_rev, b_rev, vf):
1374
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1375
a_ancestry = set(vf.get_ancestry(a_rev, topo_sorted=False))
1376
b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
1377
self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
1379
def _determine_status(self, revision_id, unique_line_numbers):
1380
"""Determines the status unique lines versus all lcas.
1382
Basically, determines why the line is unique to this revision.
1384
A line may be determined new or killed, but not both.
1386
:param revision_id: The id of the revision in which the lines are
1388
:param unique_line_numbers: The line numbers of unique lines.
1389
:return a tuple of (new_this, killed_other):
1391
new = self._find_new(revision_id)
1392
killed = set(unique_line_numbers).difference(new)
1395
def _find_new(self, version_id):
1396
"""Determine which lines are new in the ancestry of this version.
1398
If a lines is present in this version, and not present in any
1399
common ancestor, it is considered new.
1401
if version_id not in self.uncommon:
1403
parents = self.vf.get_parent_map([version_id])[version_id]
1404
if len(parents) == 0:
1405
return set(range(len(self.vf.get_lines(version_id))))
1407
for parent in parents:
1408
blocks = self._get_matching_blocks(version_id, parent)
1409
result, unused = self._unique_lines(blocks)
1410
parent_new = self._find_new(parent)
1411
for i, j, n in blocks:
1412
for ii, jj in [(i+r, j+r) for r in range(n)]:
1413
if jj in parent_new:
1418
new.intersection_update(result)
1945
1422
class _PlanLCAMerge(_PlanMergeBase):
added
removed
bzrlib/merge.py
