1
# Copyright (C) 2005-2011 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
from __future__ import absolute_import
21
from .lazy_import import lazy_import
22
lazy_import(globals(), """
24
branch as _mod_branch,
26
conflicts as _mod_conflicts,
33
revision as _mod_revision,
42
from breezy.bzr import (
45
from breezy.i18n import gettext
56
# TODO: Report back as changes are merged in
59
def transform_tree(from_tree, to_tree, interesting_files=None):
60
from_tree.lock_tree_write()
61
operation = cleanup.OperationWithCleanups(merge_inner)
62
operation.add_cleanup(from_tree.unlock)
63
operation.run_simple(from_tree.branch, to_tree, from_tree,
64
ignore_zero=True, this_tree=from_tree,
65
interesting_files=interesting_files)
68
class MergeHooks(hooks.Hooks):
71
hooks.Hooks.__init__(self, "breezy.merge", "Merger.hooks")
72
self.add_hook('merge_file_content',
73
"Called with a breezy.merge.Merger object to create a per file "
74
"merge object when starting a merge. "
75
"Should return either None or a subclass of "
76
"``breezy.merge.AbstractPerFileMerger``. "
77
"Such objects will then be called per file "
78
"that needs to be merged (including when one "
79
"side has deleted the file and the other has changed it). "
80
"See the AbstractPerFileMerger API docs for details on how it is "
83
self.add_hook('pre_merge',
84
'Called before a merge. '
85
'Receives a Merger object as the single argument.',
87
self.add_hook('post_merge',
88
'Called after a merge. '
89
'Receives a Merger object as the single argument. '
90
'The return value is ignored.',
94
class AbstractPerFileMerger(object):
95
"""PerFileMerger objects are used by plugins extending merge for breezy.
97
See ``breezy.plugins.news_merge.news_merge`` for an example concrete class.
99
:ivar merger: The Merge3Merger performing the merge.
102
def __init__(self, merger):
103
"""Create a PerFileMerger for use with merger."""
106
def merge_contents(self, merge_params):
107
"""Attempt to merge the contents of a single file.
109
:param merge_params: A breezy.merge.MergeFileHookParams
110
:return: A tuple of (status, chunks), where status is one of
111
'not_applicable', 'success', 'conflicted', or 'delete'. If status
112
is 'success' or 'conflicted', then chunks should be an iterable of
113
strings for the new file contents.
115
return ('not applicable', None)
118
class PerFileMerger(AbstractPerFileMerger):
119
"""Merge individual files when self.file_matches returns True.
121
This class is intended to be subclassed. The file_matches and
122
merge_matching methods should be overridden with concrete implementations.
125
def file_matches(self, params):
126
"""Return True if merge_matching should be called on this file.
128
Only called with merges of plain files with no clear winner.
130
Subclasses must override this.
132
raise NotImplementedError(self.file_matches)
134
def merge_contents(self, params):
135
"""Merge the contents of a single file."""
136
# Check whether this custom merge logic should be used.
138
# OTHER is a straight winner, rely on default merge.
139
params.winner == 'other' or
140
# THIS and OTHER aren't both files.
141
not params.is_file_merge() or
142
# The filename doesn't match
143
not self.file_matches(params)):
144
return 'not_applicable', None
145
return self.merge_matching(params)
147
def merge_matching(self, params):
148
"""Merge the contents of a single file that has matched the criteria
149
in PerFileMerger.merge_contents (is a conflict, is a file,
150
self.file_matches is True).
152
Subclasses must override this.
154
raise NotImplementedError(self.merge_matching)
157
class ConfigurableFileMerger(PerFileMerger):
158
"""Merge individual files when configured via a .conf file.
160
This is a base class for concrete custom file merging logic. Concrete
161
classes should implement ``merge_text``.
163
See ``breezy.plugins.news_merge.news_merge`` for an example concrete class.
165
:ivar affected_files: The configured file paths to merge.
167
:cvar name_prefix: The prefix to use when looking up configuration
168
details. <name_prefix>_merge_files describes the files targeted by the
171
:cvar default_files: The default file paths to merge when no configuration
178
def __init__(self, merger):
179
super(ConfigurableFileMerger, self).__init__(merger)
180
self.affected_files = None
181
self.default_files = self.__class__.default_files or []
182
self.name_prefix = self.__class__.name_prefix
183
if self.name_prefix is None:
184
raise ValueError("name_prefix must be set.")
186
def file_matches(self, params):
187
"""Check whether the file should call the merge hook.
189
<name_prefix>_merge_files configuration variable is a list of files
190
that should use the hook.
192
affected_files = self.affected_files
193
if affected_files is None:
194
config = self.merger.this_branch.get_config()
195
# Until bzr provides a better policy for caching the config, we
196
# just add the part we're interested in to the params to avoid
197
# reading the config files repeatedly (breezy.conf, location.conf,
199
config_key = self.name_prefix + '_merge_files'
200
affected_files = config.get_user_option_as_list(config_key)
201
if affected_files is None:
202
# If nothing was specified in the config, use the default.
203
affected_files = self.default_files
204
self.affected_files = affected_files
206
filepath = params.this_path
207
if filepath in affected_files:
211
def merge_matching(self, params):
212
return self.merge_text(params)
214
def merge_text(self, params):
215
"""Merge the byte contents of a single file.
217
This is called after checking that the merge should be performed in
218
merge_contents, and it should behave as per
219
``breezy.merge.AbstractPerFileMerger.merge_contents``.
221
raise NotImplementedError(self.merge_text)
224
class MergeFileHookParams(object):
225
"""Object holding parameters passed to merge_file_content hooks.
227
There are some fields hooks can access:
229
:ivar file_id: the file ID of the file being merged
230
:ivar base_path: Path in base tree
231
:ivar other_path: Path in other tree
232
:ivar this_path: Path in this tree
233
:ivar trans_id: the transform ID for the merge of this file
234
:ivar this_kind: kind of file_id in 'this' tree
235
:ivar other_kind: kind of file_id in 'other' tree
236
:ivar winner: one of 'this', 'other', 'conflict'
239
def __init__(self, merger, file_id, paths, trans_id, this_kind, other_kind,
241
self._merger = merger
242
self.file_id = file_id
244
self.base_path, self.other_path, self.this_path = paths
245
self.trans_id = trans_id
246
self.this_kind = this_kind
247
self.other_kind = other_kind
250
def is_file_merge(self):
251
"""True if this_kind and other_kind are both 'file'."""
252
return self.this_kind == 'file' and self.other_kind == 'file'
254
@decorators.cachedproperty
255
def base_lines(self):
256
"""The lines of the 'base' version of the file."""
257
return self._merger.get_lines(self._merger.base_tree, self.base_path, self.file_id)
259
@decorators.cachedproperty
260
def this_lines(self):
261
"""The lines of the 'this' version of the file."""
262
return self._merger.get_lines(self._merger.this_tree, self.this_path, self.file_id)
264
@decorators.cachedproperty
265
def other_lines(self):
266
"""The lines of the 'other' version of the file."""
267
return self._merger.get_lines(self._merger.other_tree, self.other_path, self.file_id)
270
class Merger(object):
274
def __init__(self, this_branch, other_tree=None, base_tree=None,
275
this_tree=None, change_reporter=None,
276
recurse='down', revision_graph=None):
277
object.__init__(self)
278
self.this_branch = this_branch
279
self.this_basis = _mod_revision.ensure_null(
280
this_branch.last_revision())
281
self.this_rev_id = None
282
self.this_tree = this_tree
283
self.this_revision_tree = None
284
self.this_basis_tree = None
285
self.other_tree = other_tree
286
self.other_branch = None
287
self.base_tree = base_tree
288
self.ignore_zero = False
289
self.backup_files = False
290
self.interesting_files = None
291
self.show_base = False
292
self.reprocess = False
294
self.recurse = recurse
295
self.change_reporter = change_reporter
296
self._cached_trees = {}
297
self._revision_graph = revision_graph
298
self._base_is_ancestor = None
299
self._base_is_other_ancestor = None
300
self._is_criss_cross = None
301
self._lca_trees = None
303
def cache_trees_with_revision_ids(self, trees):
304
"""Cache any tree in trees if it has a revision_id."""
305
for maybe_tree in trees:
306
if maybe_tree is None:
309
rev_id = maybe_tree.get_revision_id()
310
except AttributeError:
312
self._cached_trees[rev_id] = maybe_tree
315
def revision_graph(self):
316
if self._revision_graph is None:
317
self._revision_graph = self.this_branch.repository.get_graph()
318
return self._revision_graph
320
def _set_base_is_ancestor(self, value):
321
self._base_is_ancestor = value
323
def _get_base_is_ancestor(self):
324
if self._base_is_ancestor is None:
325
self._base_is_ancestor = self.revision_graph.is_ancestor(
326
self.base_rev_id, self.this_basis)
327
return self._base_is_ancestor
329
base_is_ancestor = property(_get_base_is_ancestor, _set_base_is_ancestor)
331
def _set_base_is_other_ancestor(self, value):
332
self._base_is_other_ancestor = value
334
def _get_base_is_other_ancestor(self):
335
if self._base_is_other_ancestor is None:
336
if self.other_basis is None:
338
self._base_is_other_ancestor = self.revision_graph.is_ancestor(
339
self.base_rev_id, self.other_basis)
340
return self._base_is_other_ancestor
342
base_is_other_ancestor = property(_get_base_is_other_ancestor,
343
_set_base_is_other_ancestor)
346
def from_uncommitted(tree, other_tree, base_tree=None):
347
"""Return a Merger for uncommitted changes in other_tree.
349
:param tree: The tree to merge into
350
:param other_tree: The tree to get uncommitted changes from
351
:param base_tree: The basis to use for the merge. If unspecified,
352
other_tree.basis_tree() will be used.
354
if base_tree is None:
355
base_tree = other_tree.basis_tree()
356
merger = Merger(tree.branch, other_tree, base_tree, tree)
357
merger.base_rev_id = merger.base_tree.get_revision_id()
358
merger.other_rev_id = None
359
merger.other_basis = merger.base_rev_id
363
def from_mergeable(klass, tree, mergeable):
364
"""Return a Merger for a bundle or merge directive.
366
:param tree: The tree to merge changes into
367
:param mergeable: A merge directive or bundle
369
mergeable.install_revisions(tree.branch.repository)
370
base_revision_id, other_revision_id, verified =\
371
mergeable.get_merge_request(tree.branch.repository)
372
revision_graph = tree.branch.repository.get_graph()
373
if base_revision_id is not None:
374
if (base_revision_id != _mod_revision.NULL_REVISION and
375
revision_graph.is_ancestor(
376
base_revision_id, tree.branch.last_revision())):
377
base_revision_id = None
379
trace.warning('Performing cherrypick')
380
merger = klass.from_revision_ids(tree, other_revision_id,
381
base_revision_id, revision_graph=
383
return merger, verified
386
def from_revision_ids(tree, other, base=None, other_branch=None,
387
base_branch=None, revision_graph=None,
389
"""Return a Merger for revision-ids.
391
:param tree: The tree to merge changes into
392
:param other: The revision-id to use as OTHER
393
:param base: The revision-id to use as BASE. If not specified, will
395
:param other_branch: A branch containing the other revision-id. If
396
not supplied, tree.branch is used.
397
:param base_branch: A branch containing the base revision-id. If
398
not supplied, other_branch or tree.branch will be used.
399
:param revision_graph: If you have a revision_graph precomputed, pass
400
it in, otherwise it will be created for you.
401
:param tree_branch: The branch associated with tree. If not supplied,
402
tree.branch will be used.
404
if tree_branch is None:
405
tree_branch = tree.branch
406
merger = Merger(tree_branch, this_tree=tree,
407
revision_graph=revision_graph)
408
if other_branch is None:
409
other_branch = tree.branch
410
merger.set_other_revision(other, other_branch)
414
if base_branch is None:
415
base_branch = other_branch
416
merger.set_base_revision(base, base_branch)
419
def revision_tree(self, revision_id, branch=None):
420
if revision_id not in self._cached_trees:
422
branch = self.this_branch
424
tree = self.this_tree.revision_tree(revision_id)
425
except errors.NoSuchRevisionInTree:
426
tree = branch.repository.revision_tree(revision_id)
427
self._cached_trees[revision_id] = tree
428
return self._cached_trees[revision_id]
430
def _get_tree(self, treespec, possible_transports=None):
431
location, revno = treespec
433
tree = workingtree.WorkingTree.open_containing(location)[0]
434
return tree.branch, tree
435
branch = _mod_branch.Branch.open_containing(
436
location, possible_transports)[0]
438
revision_id = branch.last_revision()
440
revision_id = branch.get_rev_id(revno)
441
revision_id = _mod_revision.ensure_null(revision_id)
442
return branch, self.revision_tree(revision_id, branch)
444
def set_interesting_files(self, file_list):
445
self.interesting_files = file_list
447
def set_pending(self):
448
if (not self.base_is_ancestor or not self.base_is_other_ancestor
449
or self.other_rev_id is None):
453
def _add_parent(self):
454
new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
455
new_parent_trees = []
456
operation = cleanup.OperationWithCleanups(
457
self.this_tree.set_parent_trees)
458
for revision_id in new_parents:
460
tree = self.revision_tree(revision_id)
461
except errors.NoSuchRevision:
465
operation.add_cleanup(tree.unlock)
466
new_parent_trees.append((revision_id, tree))
467
operation.run_simple(new_parent_trees, allow_leftmost_as_ghost=True)
469
def set_other(self, other_revision, possible_transports=None):
470
"""Set the revision and tree to merge from.
472
This sets the other_tree, other_rev_id, other_basis attributes.
474
:param other_revision: The [path, revision] list to merge from.
476
self.other_branch, self.other_tree = self._get_tree(other_revision,
478
if other_revision[1] == -1:
479
self.other_rev_id = _mod_revision.ensure_null(
480
self.other_branch.last_revision())
481
if _mod_revision.is_null(self.other_rev_id):
482
raise errors.NoCommits(self.other_branch)
483
self.other_basis = self.other_rev_id
484
elif other_revision[1] is not None:
485
self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
486
self.other_basis = self.other_rev_id
488
self.other_rev_id = None
489
self.other_basis = self.other_branch.last_revision()
490
if self.other_basis is None:
491
raise errors.NoCommits(self.other_branch)
492
if self.other_rev_id is not None:
493
self._cached_trees[self.other_rev_id] = self.other_tree
494
self._maybe_fetch(self.other_branch, self.this_branch, self.other_basis)
496
def set_other_revision(self, revision_id, other_branch):
497
"""Set 'other' based on a branch and revision id
499
:param revision_id: The revision to use for a tree
500
:param other_branch: The branch containing this tree
502
self.other_rev_id = revision_id
503
self.other_branch = other_branch
504
self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
505
self.other_tree = self.revision_tree(revision_id)
506
self.other_basis = revision_id
508
def set_base_revision(self, revision_id, branch):
509
"""Set 'base' based on a branch and revision id
511
:param revision_id: The revision to use for a tree
512
:param branch: The branch containing this tree
514
self.base_rev_id = revision_id
515
self.base_branch = branch
516
self._maybe_fetch(branch, self.this_branch, revision_id)
517
self.base_tree = self.revision_tree(revision_id)
519
def _maybe_fetch(self, source, target, revision_id):
520
if not source.repository.has_same_location(target.repository):
521
target.fetch(source, revision_id)
524
revisions = [_mod_revision.ensure_null(self.this_basis),
525
_mod_revision.ensure_null(self.other_basis)]
526
if _mod_revision.NULL_REVISION in revisions:
527
self.base_rev_id = _mod_revision.NULL_REVISION
528
self.base_tree = self.revision_tree(self.base_rev_id)
529
self._is_criss_cross = False
531
lcas = self.revision_graph.find_lca(revisions[0], revisions[1])
532
self._is_criss_cross = False
534
self.base_rev_id = _mod_revision.NULL_REVISION
536
self.base_rev_id = list(lcas)[0]
537
else: # len(lcas) > 1
538
self._is_criss_cross = True
540
# find_unique_lca can only handle 2 nodes, so we have to
541
# start back at the beginning. It is a shame to traverse
542
# the graph again, but better than re-implementing
544
self.base_rev_id = self.revision_graph.find_unique_lca(
545
revisions[0], revisions[1])
547
self.base_rev_id = self.revision_graph.find_unique_lca(
549
sorted_lca_keys = self.revision_graph.find_merge_order(
551
if self.base_rev_id == _mod_revision.NULL_REVISION:
552
self.base_rev_id = sorted_lca_keys[0]
554
if self.base_rev_id == _mod_revision.NULL_REVISION:
555
raise errors.UnrelatedBranches()
556
if self._is_criss_cross:
557
trace.warning('Warning: criss-cross merge encountered. See bzr'
558
' help criss-cross.')
559
trace.mutter('Criss-cross lcas: %r' % lcas)
560
if self.base_rev_id in lcas:
561
trace.mutter('Unable to find unique lca. '
562
'Fallback %r as best option.'
564
interesting_revision_ids = set(lcas)
565
interesting_revision_ids.add(self.base_rev_id)
566
interesting_trees = dict((t.get_revision_id(), t)
567
for t in self.this_branch.repository.revision_trees(
568
interesting_revision_ids))
569
self._cached_trees.update(interesting_trees)
570
if self.base_rev_id in lcas:
571
self.base_tree = interesting_trees[self.base_rev_id]
573
self.base_tree = interesting_trees.pop(self.base_rev_id)
574
self._lca_trees = [interesting_trees[key]
575
for key in sorted_lca_keys]
577
self.base_tree = self.revision_tree(self.base_rev_id)
578
self.base_is_ancestor = True
579
self.base_is_other_ancestor = True
580
trace.mutter('Base revid: %r' % self.base_rev_id)
582
def set_base(self, base_revision):
583
"""Set the base revision to use for the merge.
585
:param base_revision: A 2-list containing a path and revision number.
587
trace.mutter("doing merge() with no base_revision specified")
588
if base_revision == [None, None]:
591
base_branch, self.base_tree = self._get_tree(base_revision)
592
if base_revision[1] == -1:
593
self.base_rev_id = base_branch.last_revision()
594
elif base_revision[1] is None:
595
self.base_rev_id = _mod_revision.NULL_REVISION
597
self.base_rev_id = _mod_revision.ensure_null(
598
base_branch.get_rev_id(base_revision[1]))
599
self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
601
def make_merger(self):
602
kwargs = {'working_tree': self.this_tree, 'this_tree': self.this_tree,
603
'other_tree': self.other_tree,
604
'interesting_files': self.interesting_files,
605
'this_branch': self.this_branch,
606
'other_branch': self.other_branch,
608
if self.merge_type.requires_base:
609
kwargs['base_tree'] = self.base_tree
610
if self.merge_type.supports_reprocess:
611
kwargs['reprocess'] = self.reprocess
613
raise errors.BzrError(
614
"Conflict reduction is not supported for merge"
615
" type %s." % self.merge_type)
616
if self.merge_type.supports_show_base:
617
kwargs['show_base'] = self.show_base
619
raise errors.BzrError("Showing base is not supported for this"
620
" merge type. %s" % self.merge_type)
621
if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
622
and not self.base_is_other_ancestor):
623
raise errors.CannotReverseCherrypick()
624
if self.merge_type.supports_cherrypick:
625
kwargs['cherrypick'] = (not self.base_is_ancestor or
626
not self.base_is_other_ancestor)
627
if self._is_criss_cross and getattr(self.merge_type,
628
'supports_lca_trees', False):
629
kwargs['lca_trees'] = self._lca_trees
630
return self.merge_type(change_reporter=self.change_reporter,
633
def _do_merge_to(self):
634
merge = self.make_merger()
635
if self.other_branch is not None:
636
self.other_branch.update_references(self.this_branch)
637
for hook in Merger.hooks['pre_merge']:
640
for hook in Merger.hooks['post_merge']:
642
if self.recurse == 'down':
643
for relpath, file_id in self.this_tree.iter_references():
644
sub_tree = self.this_tree.get_nested_tree(relpath, file_id)
645
other_revision = self.other_tree.get_reference_revision(
647
if other_revision == sub_tree.last_revision():
649
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
650
sub_merge.merge_type = self.merge_type
651
other_branch = self.other_branch.reference_parent(
653
sub_merge.set_other_revision(other_revision, other_branch)
654
base_tree_path = _mod_tree.find_previous_path(
655
self.this_tree, self.base_tree, relpath)
656
base_revision = self.base_tree.get_reference_revision(
657
base_tree_path, file_id)
658
sub_merge.base_tree = \
659
sub_tree.branch.repository.revision_tree(base_revision)
660
sub_merge.base_rev_id = base_revision
665
operation = cleanup.OperationWithCleanups(self._do_merge_to)
666
self.this_tree.lock_tree_write()
667
operation.add_cleanup(self.this_tree.unlock)
668
if self.base_tree is not None:
669
self.base_tree.lock_read()
670
operation.add_cleanup(self.base_tree.unlock)
671
if self.other_tree is not None:
672
self.other_tree.lock_read()
673
operation.add_cleanup(self.other_tree.unlock)
674
merge = operation.run_simple()
675
if len(merge.cooked_conflicts) == 0:
676
if not self.ignore_zero and not trace.is_quiet():
677
trace.note(gettext("All changes applied successfully."))
679
trace.note(gettext("%d conflicts encountered.")
680
% len(merge.cooked_conflicts))
682
return len(merge.cooked_conflicts)
685
class _InventoryNoneEntry(object):
686
"""This represents an inventory entry which *isn't there*.
688
It simplifies the merging logic if we always have an InventoryEntry, even
689
if it isn't actually present
696
symlink_target = None
699
_none_entry = _InventoryNoneEntry()
702
class Merge3Merger(object):
703
"""Three-way merger that uses the merge3 text merger"""
705
supports_reprocess = True
706
supports_show_base = True
707
history_based = False
708
supports_cherrypick = True
709
supports_reverse_cherrypick = True
710
winner_idx = {"this": 2, "other": 1, "conflict": 1}
711
supports_lca_trees = True
712
requires_file_merge_plan = False
714
def __init__(self, working_tree, this_tree, base_tree, other_tree,
715
reprocess=False, show_base=False,
716
change_reporter=None, interesting_files=None, do_merge=True,
717
cherrypick=False, lca_trees=None, this_branch=None,
719
"""Initialize the merger object and perform the merge.
721
:param working_tree: The working tree to apply the merge to
722
:param this_tree: The local tree in the merge operation
723
:param base_tree: The common tree in the merge operation
724
:param other_tree: The other tree to merge changes from
725
:param this_branch: The branch associated with this_tree. Defaults to
726
this_tree.branch if not supplied.
727
:param other_branch: The branch associated with other_tree, if any.
728
:param: reprocess If True, perform conflict-reduction processing.
729
:param show_base: If True, show the base revision in text conflicts.
730
(incompatible with reprocess)
731
:param change_reporter: An object that should report changes made
732
:param interesting_files: The tree-relative paths of files that should
733
participate in the merge. If these paths refer to directories,
734
the contents of those directories will also be included. If not
735
specified, all files may participate in the
737
:param lca_trees: Can be set to a dictionary of {revision_id:rev_tree}
738
if the ancestry was found to include a criss-cross merge.
739
Otherwise should be None.
741
object.__init__(self)
742
if this_branch is None:
743
this_branch = this_tree.branch
744
self.interesting_files = interesting_files
745
self.working_tree = working_tree
746
self.this_tree = this_tree
747
self.base_tree = base_tree
748
self.other_tree = other_tree
749
self.this_branch = this_branch
750
self.other_branch = other_branch
751
self._raw_conflicts = []
752
self.cooked_conflicts = []
753
self.reprocess = reprocess
754
self.show_base = show_base
755
self._lca_trees = lca_trees
756
# Uncommenting this will change the default algorithm to always use
757
# _entries_lca. This can be useful for running the test suite and
758
# making sure we haven't missed any corner cases.
759
# if lca_trees is None:
760
# self._lca_trees = [self.base_tree]
761
self.change_reporter = change_reporter
762
self.cherrypick = cherrypick
767
operation = cleanup.OperationWithCleanups(self._do_merge)
768
self.working_tree.lock_tree_write()
769
operation.add_cleanup(self.working_tree.unlock)
770
self.this_tree.lock_read()
771
operation.add_cleanup(self.this_tree.unlock)
772
self.base_tree.lock_read()
773
operation.add_cleanup(self.base_tree.unlock)
774
self.other_tree.lock_read()
775
operation.add_cleanup(self.other_tree.unlock)
778
def _do_merge(self, operation):
779
self.tt = transform.TreeTransform(self.working_tree, None)
780
operation.add_cleanup(self.tt.finalize)
781
self._compute_transform()
782
results = self.tt.apply(no_conflicts=True)
783
self.write_modified(results)
785
self.working_tree.add_conflicts(self.cooked_conflicts)
786
except errors.UnsupportedOperation:
789
def make_preview_transform(self):
790
operation = cleanup.OperationWithCleanups(self._make_preview_transform)
791
self.base_tree.lock_read()
792
operation.add_cleanup(self.base_tree.unlock)
793
self.other_tree.lock_read()
794
operation.add_cleanup(self.other_tree.unlock)
795
return operation.run_simple()
797
def _make_preview_transform(self):
798
self.tt = transform.TransformPreview(self.working_tree)
799
self._compute_transform()
802
def _compute_transform(self):
803
if self._lca_trees is None:
804
entries = self._entries3()
805
resolver = self._three_way
807
entries = self._entries_lca()
808
resolver = self._lca_multi_way
809
# Prepare merge hooks
810
factories = Merger.hooks['merge_file_content']
811
# One hook for each registered one plus our default merger
812
hooks = [factory(self) for factory in factories] + [self]
813
self.active_hooks = [hook for hook in hooks if hook is not None]
814
with ui.ui_factory.nested_progress_bar() as child_pb:
815
for num, (file_id, changed, paths3, parents3, names3,
816
executable3) in enumerate(entries):
817
# Try merging each entry
818
child_pb.update(gettext('Preparing file merge'),
820
self._merge_names(file_id, paths3, parents3, names3, resolver=resolver)
822
file_status = self._do_merge_contents(paths3, file_id)
824
file_status = 'unmodified'
825
self._merge_executable(paths3, file_id, executable3,
826
file_status, resolver=resolver)
827
self.tt.fixup_new_roots()
828
self._finish_computing_transform()
830
def _finish_computing_transform(self):
831
"""Finalize the transform and report the changes.
833
This is the second half of _compute_transform.
835
with ui.ui_factory.nested_progress_bar() as child_pb:
836
fs_conflicts = transform.resolve_conflicts(self.tt, child_pb,
837
lambda t, c: transform.conflict_pass(t, c, self.other_tree))
838
if self.change_reporter is not None:
839
from breezy import delta
840
delta.report_changes(
841
self.tt.iter_changes(), self.change_reporter)
842
self.cook_conflicts(fs_conflicts)
843
for conflict in self.cooked_conflicts:
844
trace.warning(unicode(conflict))
847
"""Gather data about files modified between three trees.
849
Return a list of tuples of file_id, changed, parents3, names3,
850
executable3. changed is a boolean indicating whether the file contents
851
or kind were changed. parents3 is a tuple of parent ids for base,
852
other and this. names3 is a tuple of names for base, other and this.
853
executable3 is a tuple of execute-bit values for base, other and this.
856
iterator = self.other_tree.iter_changes(self.base_tree,
857
specific_files=self.interesting_files,
858
extra_trees=[self.this_tree])
859
this_interesting_files = self.this_tree.find_related_paths_across_trees(
860
self.interesting_files, trees=[self.other_tree])
861
this_entries = dict(self.this_tree.iter_entries_by_dir(
862
specific_files=this_interesting_files))
863
for (file_id, paths, changed, versioned, parents, names, kind,
864
executable) in iterator:
865
if paths[0] is not None:
866
this_path = _mod_tree.find_previous_path(
867
self.base_tree, self.this_tree, paths[0])
869
this_path = _mod_tree.find_previous_path(
870
self.other_tree, self.this_tree, paths[1])
871
this_entry = this_entries.get(this_path)
872
if this_entry is not None:
873
this_name = this_entry.name
874
this_parent = this_entry.parent_id
875
this_executable = this_entry.executable
879
this_executable = None
880
parents3 = parents + (this_parent,)
881
names3 = names + (this_name,)
882
paths3 = paths + (this_path, )
883
executable3 = executable + (this_executable,)
884
result.append((file_id, changed, paths3, parents3, names3, executable3))
887
def _entries_lca(self):
888
"""Gather data about files modified between multiple trees.
890
This compares OTHER versus all LCA trees, and for interesting entries,
891
it then compares with THIS and BASE.
893
For the multi-valued entries, the format will be (BASE, [lca1, lca2])
895
:return: [(file_id, changed, paths, parents, names, executable)], where:
897
* file_id: Simple file_id of the entry
898
* changed: Boolean, True if the kind or contents changed else False
899
* paths: ((base, [path, in, lcas]), path_other, path_this)
900
* parents: ((base, [parent_id, in, lcas]), parent_id_other,
902
* names: ((base, [name, in, lcas]), name_in_other, name_in_this)
903
* executable: ((base, [exec, in, lcas]), exec_in_other,
906
if self.interesting_files is not None:
907
lookup_trees = [self.this_tree, self.base_tree]
908
lookup_trees.extend(self._lca_trees)
909
# I think we should include the lca trees as well
910
interesting_files = self.other_tree.find_related_paths_across_trees(
911
self.interesting_files, lookup_trees)
913
interesting_files = None
915
walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
917
base_inventory = self.base_tree.root_inventory
918
this_inventory = self.this_tree.root_inventory
919
for path, file_id, other_ie, lca_values in walker.iter_all():
920
# Is this modified at all from any of the other trees?
922
other_ie = _none_entry
925
other_path = self.other_tree.id2path(file_id)
926
if interesting_files is not None and other_path not in interesting_files:
929
# If other_revision is found in any of the lcas, that means this
930
# node is uninteresting. This is because when merging, if there are
931
# multiple heads(), we have to create a new node. So if we didn't,
932
# we know that the ancestry is linear, and that OTHER did not
934
# See doc/developers/lca_merge_resolution.txt for details
935
other_revision = other_ie.revision
936
if other_revision is not None:
937
# We can't use this shortcut when other_revision is None,
938
# because it may be None because things are WorkingTrees, and
939
# not because it is *actually* None.
940
is_unmodified = False
941
for lca_path, ie in lca_values:
942
if ie is not None and ie.revision == other_revision:
950
for lca_path, lca_ie in lca_values:
952
lca_entries.append(_none_entry)
953
lca_paths.append(None)
955
lca_entries.append(lca_ie)
956
lca_paths.append(lca_path)
959
base_ie = base_inventory.get_entry(file_id)
960
except errors.NoSuchId:
961
base_ie = _none_entry
964
base_path = self.base_tree.id2path(file_id)
967
this_ie = this_inventory.get_entry(file_id)
968
except errors.NoSuchId:
969
this_ie = _none_entry
972
this_path = self.this_tree.id2path(file_id)
978
for lca_ie in lca_entries:
979
lca_kinds.append(lca_ie.kind)
980
lca_parent_ids.append(lca_ie.parent_id)
981
lca_names.append(lca_ie.name)
982
lca_executable.append(lca_ie.executable)
984
kind_winner = self._lca_multi_way(
985
(base_ie.kind, lca_kinds),
986
other_ie.kind, this_ie.kind)
987
parent_id_winner = self._lca_multi_way(
988
(base_ie.parent_id, lca_parent_ids),
989
other_ie.parent_id, this_ie.parent_id)
990
name_winner = self._lca_multi_way(
991
(base_ie.name, lca_names),
992
other_ie.name, this_ie.name)
994
content_changed = True
995
if kind_winner == 'this':
996
# No kind change in OTHER, see if there are *any* changes
997
if other_ie.kind == 'directory':
998
if parent_id_winner == 'this' and name_winner == 'this':
999
# No change for this directory in OTHER, skip
1001
content_changed = False
1002
elif other_ie.kind is None or other_ie.kind == 'file':
1003
def get_sha1(tree, path):
1007
return tree.get_file_sha1(path, file_id)
1008
except errors.NoSuchFile:
1010
base_sha1 = get_sha1(self.base_tree, base_path)
1011
lca_sha1s = [get_sha1(tree, lca_path)
1013
in zip(self._lca_trees, lca_paths)]
1014
this_sha1 = get_sha1(self.this_tree, this_path)
1015
other_sha1 = get_sha1(self.other_tree, other_path)
1016
sha1_winner = self._lca_multi_way(
1017
(base_sha1, lca_sha1s), other_sha1, this_sha1,
1018
allow_overriding_lca=False)
1019
exec_winner = self._lca_multi_way(
1020
(base_ie.executable, lca_executable),
1021
other_ie.executable, this_ie.executable)
1022
if (parent_id_winner == 'this' and name_winner == 'this'
1023
and sha1_winner == 'this' and exec_winner == 'this'):
1024
# No kind, parent, name, exec, or content change for
1025
# OTHER, so this node is not considered interesting
1027
if sha1_winner == 'this':
1028
content_changed = False
1029
elif other_ie.kind == 'symlink':
1030
def get_target(ie, tree, path):
1031
if ie.kind != 'symlink':
1033
return tree.get_symlink_target(path, file_id)
1034
base_target = get_target(base_ie, self.base_tree, base_path)
1035
lca_targets = [get_target(ie, tree, lca_path) for ie, tree, lca_path
1036
in zip(lca_entries, self._lca_trees, lca_paths)]
1037
this_target = get_target(this_ie, self.this_tree, this_path)
1038
other_target = get_target(other_ie, self.other_tree, other_path)
1039
target_winner = self._lca_multi_way(
1040
(base_target, lca_targets),
1041
other_target, this_target)
1042
if (parent_id_winner == 'this' and name_winner == 'this'
1043
and target_winner == 'this'):
1044
# No kind, parent, name, or symlink target change
1047
if target_winner == 'this':
1048
content_changed = False
1049
elif other_ie.kind == 'tree-reference':
1050
# The 'changed' information seems to be handled at a higher
1051
# level. At least, _entries3 returns False for content
1052
# changed, even when at a new revision_id.
1053
content_changed = False
1054
if (parent_id_winner == 'this' and name_winner == 'this'):
1055
# Nothing interesting
1058
raise AssertionError('unhandled kind: %s' % other_ie.kind)
1060
# If we have gotten this far, that means something has changed
1061
result.append((file_id, content_changed,
1062
((base_path, lca_paths),
1063
other_path, this_path),
1064
((base_ie.parent_id, lca_parent_ids),
1065
other_ie.parent_id, this_ie.parent_id),
1066
((base_ie.name, lca_names),
1067
other_ie.name, this_ie.name),
1068
((base_ie.executable, lca_executable),
1069
other_ie.executable, this_ie.executable)
1073
def write_modified(self, results):
1074
if not self.working_tree.supports_merge_modified():
1076
modified_hashes = {}
1077
for path in results.modified_paths:
1078
wt_relpath = self.working_tree.relpath(path)
1079
file_id = self.working_tree.path2id(wt_relpath)
1082
hash = self.working_tree.get_file_sha1(wt_relpath, file_id)
1085
modified_hashes[file_id] = hash
1086
self.working_tree.set_merge_modified(modified_hashes)
1089
def parent(entry, file_id):
1090
"""Determine the parent for a file_id (used as a key method)"""
1093
return entry.parent_id
1096
def name(entry, file_id):
1097
"""Determine the name for a file_id (used as a key method)"""
1103
def contents_sha1(tree, path, file_id=None):
1104
"""Determine the sha1 of the file contents (used as a key method)."""
1106
return tree.get_file_sha1(path, file_id)
1107
except errors.NoSuchFile:
1111
def executable(tree, path, file_id=None):
1112
"""Determine the executability of a file-id (used as a key method)."""
1114
if tree.kind(path, file_id) != "file":
1116
except errors.NoSuchFile:
1118
return tree.is_executable(path, file_id)
1121
def kind(tree, path, file_id=None):
1122
"""Determine the kind of a file-id (used as a key method)."""
1124
return tree.kind(path, file_id)
1125
except errors.NoSuchFile:
1129
def _three_way(base, other, this):
1131
# if 'base == other', either they all agree, or only 'this' has
1134
elif this not in (base, other):
1135
# 'this' is neither 'base' nor 'other', so both sides changed
1138
# "Ambiguous clean merge" -- both sides have made the same change.
1141
# this == base: only other has changed.
1145
def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
1146
"""Consider LCAs when determining whether a change has occurred.
1148
If LCAS are all identical, this is the same as a _three_way comparison.
1150
:param bases: value in (BASE, [LCAS])
1151
:param other: value in OTHER
1152
:param this: value in THIS
1153
:param allow_overriding_lca: If there is more than one unique lca
1154
value, allow OTHER to override THIS if it has a new value, and
1155
THIS only has an lca value, or vice versa. This is appropriate for
1156
truly scalar values, not as much for non-scalars.
1157
:return: 'this', 'other', or 'conflict' depending on whether an entry
1160
# See doc/developers/lca_tree_merging.txt for details about this
1163
# Either Ambiguously clean, or nothing was actually changed. We
1166
base_val, lca_vals = bases
1167
# Remove 'base_val' from the lca_vals, because it is not interesting
1168
filtered_lca_vals = [lca_val for lca_val in lca_vals
1169
if lca_val != base_val]
1170
if len(filtered_lca_vals) == 0:
1171
return Merge3Merger._three_way(base_val, other, this)
1173
unique_lca_vals = set(filtered_lca_vals)
1174
if len(unique_lca_vals) == 1:
1175
return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
1177
if allow_overriding_lca:
1178
if other in unique_lca_vals:
1179
if this in unique_lca_vals:
1180
# Each side picked a different lca, conflict
1183
# This has a value which supersedes both lca values, and
1184
# other only has an lca value
1186
elif this in unique_lca_vals:
1187
# OTHER has a value which supersedes both lca values, and this
1188
# only has an lca value
1191
# At this point, the lcas disagree, and the tip disagree
1194
def merge_names(self, paths):
1195
def get_entry(tree, path):
1197
return next(tree.iter_entries_by_dir(specific_files=[path]))[1]
1198
except StopIteration:
1200
used_base_path, other_path, this_path = paths
1201
this_entry = get_entry(self.this_tree, this_path)
1202
other_entry = get_entry(self.other_tree, other_path)
1203
base_entry = get_entry(self.base_tree, base_path)
1204
entries = (base_entry, other_entry, this_entry)
1207
for entry in entries:
1210
parents.append(None)
1212
names.append(entry.name)
1213
parents.append(entry.parent_id)
1214
return self._merge_names(file_id, paths, parents, names,
1215
resolver=self._three_way)
1217
def _merge_names(self, file_id, paths, parents, names, resolver):
1218
"""Perform a merge on file_id names and parents"""
1219
base_name, other_name, this_name = names
1220
base_parent, other_parent, this_parent = parents
1221
unused_base_path, other_path, this_path = paths
1223
name_winner = resolver(*names)
1225
parent_id_winner = resolver(*parents)
1226
if this_name is None:
1227
if name_winner == "this":
1228
name_winner = "other"
1229
if parent_id_winner == "this":
1230
parent_id_winner = "other"
1231
if name_winner == "this" and parent_id_winner == "this":
1233
if name_winner == 'conflict' or parent_id_winner == 'conflict':
1234
# Creating helpers (.OTHER or .THIS) here cause problems down the
1235
# road if a ContentConflict needs to be created so we should not do
1237
trans_id = self.tt.trans_id_file_id(file_id)
1238
self._raw_conflicts.append(('path conflict', trans_id, file_id,
1239
this_parent, this_name,
1240
other_parent, other_name))
1241
if other_path is None:
1242
# it doesn't matter whether the result was 'other' or
1243
# 'conflict'-- if it has no file id, we leave it alone.
1245
parent_id = parents[self.winner_idx[parent_id_winner]]
1246
name = names[self.winner_idx[name_winner]]
1247
if parent_id is not None or name is not None:
1248
# if we get here, name_winner and parent_winner are set to safe
1250
if parent_id is None and name is not None:
1251
# if parent_id is None and name is non-None, current file is
1253
if names[self.winner_idx[parent_id_winner]] != '':
1254
raise AssertionError(
1255
'File looks like a root, but named %s' %
1256
names[self.winner_idx[parent_id_winner]])
1257
parent_trans_id = transform.ROOT_PARENT
1259
parent_trans_id = self.tt.trans_id_file_id(parent_id)
1260
self.tt.adjust_path(name, parent_trans_id,
1261
self.tt.trans_id_file_id(file_id))
1263
def _do_merge_contents(self, paths, file_id):
1264
"""Performs a merge on file_id contents."""
1265
def contents_pair(tree, path):
1269
kind = tree.kind(path, file_id)
1270
except errors.NoSuchFile:
1273
contents = tree.get_file_sha1(path, file_id)
1274
elif kind == "symlink":
1275
contents = tree.get_symlink_target(path, file_id)
1278
return kind, contents
1280
base_path, other_path, this_path = paths
1281
# See SPOT run. run, SPOT, run.
1282
# So we're not QUITE repeating ourselves; we do tricky things with
1284
other_pair = contents_pair(self.other_tree, other_path)
1285
this_pair = contents_pair(self.this_tree, this_path)
1287
(base_path, lca_paths) = base_path
1288
base_pair = contents_pair(self.base_tree, base_path)
1289
lca_pairs = [contents_pair(tree, path)
1290
for tree, path in zip(self._lca_trees, lca_paths)]
1291
winner = self._lca_multi_way((base_pair, lca_pairs), other_pair,
1292
this_pair, allow_overriding_lca=False)
1294
base_pair = contents_pair(self.base_tree, base_path)
1295
if base_pair == other_pair:
1298
# We delayed evaluating this_pair as long as we can to avoid
1299
# unnecessary sha1 calculation
1300
this_pair = contents_pair(self.this_tree, this_path)
1301
winner = self._three_way(base_pair, other_pair, this_pair)
1302
if winner == 'this':
1303
# No interesting changes introduced by OTHER
1305
# We have a hypothetical conflict, but if we have files, then we
1306
# can try to merge the content
1307
trans_id = self.tt.trans_id_file_id(file_id)
1308
params = MergeFileHookParams(
1309
self, file_id, (base_path, other_path,
1310
this_path), trans_id, this_pair[0],
1311
other_pair[0], winner)
1312
hooks = self.active_hooks
1313
hook_status = 'not_applicable'
1315
hook_status, lines = hook.merge_contents(params)
1316
if hook_status != 'not_applicable':
1317
# Don't try any more hooks, this one applies.
1319
# If the merge ends up replacing the content of the file, we get rid of
1320
# it at the end of this method (this variable is used to track the
1321
# exceptions to this rule).
1324
if hook_status == 'not_applicable':
1325
# No merge hook was able to resolve the situation. Two cases exist:
1326
# a content conflict or a duplicate one.
1328
name = self.tt.final_name(trans_id)
1329
parent_id = self.tt.final_parent(trans_id)
1331
inhibit_content_conflict = False
1332
if params.this_kind is None: # file_id is not in THIS
1333
# Is the name used for a different file_id ?
1334
if self.this_tree.is_versioned(other_path):
1335
# Two entries for the same path
1337
# versioning the merged file will trigger a duplicate
1339
self.tt.version_file(file_id, trans_id)
1340
transform.create_from_tree(
1341
self.tt, trans_id, self.other_tree,
1342
other_path, file_id=file_id,
1343
filter_tree_path=self._get_filter_tree_path(file_id))
1344
inhibit_content_conflict = True
1345
elif params.other_kind is None: # file_id is not in OTHER
1346
# Is the name used for a different file_id ?
1347
if self.other_tree.is_versioned(this_path):
1348
# Two entries for the same path again, but here, the other
1349
# entry will also be merged. We simply inhibit the
1350
# 'content' conflict creation because we know OTHER will
1351
# create (or has already created depending on ordering) an
1352
# entry at the same path. This will trigger a 'duplicate'
1355
inhibit_content_conflict = True
1356
if not inhibit_content_conflict:
1357
if params.this_kind is not None:
1358
self.tt.unversion_file(trans_id)
1359
# This is a contents conflict, because none of the available
1360
# functions could merge it.
1361
file_group = self._dump_conflicts(
1362
name, (base_path, other_path, this_path), parent_id,
1363
file_id, set_version=True)
1364
self._raw_conflicts.append(('contents conflict', file_group))
1365
elif hook_status == 'success':
1366
self.tt.create_file(lines, trans_id)
1367
elif hook_status == 'conflicted':
1368
# XXX: perhaps the hook should be able to provide
1369
# the BASE/THIS/OTHER files?
1370
self.tt.create_file(lines, trans_id)
1371
self._raw_conflicts.append(('text conflict', trans_id))
1372
name = self.tt.final_name(trans_id)
1373
parent_id = self.tt.final_parent(trans_id)
1374
self._dump_conflicts(
1375
name, (base_path, other_path, this_path), parent_id, file_id)
1376
elif hook_status == 'delete':
1377
self.tt.unversion_file(trans_id)
1379
elif hook_status == 'done':
1380
# The hook function did whatever it needs to do directly, no
1381
# further action needed here.
1384
raise AssertionError('unknown hook_status: %r' % (hook_status,))
1385
if not this_path and result == "modified":
1386
self.tt.version_file(file_id, trans_id)
1388
# The merge has been performed and produced a new content, so the
1389
# old contents should not be retained.
1390
self.tt.delete_contents(trans_id)
1393
def _default_other_winner_merge(self, merge_hook_params):
1394
"""Replace this contents with other."""
1395
file_id = merge_hook_params.file_id
1396
trans_id = merge_hook_params.trans_id
1397
if merge_hook_params.other_path is not None:
1398
# OTHER changed the file
1399
transform.create_from_tree(
1400
self.tt, trans_id, self.other_tree,
1401
merge_hook_params.other_path, file_id=file_id,
1402
filter_tree_path=self._get_filter_tree_path(file_id))
1404
elif merge_hook_params.this_path is not None:
1405
# OTHER deleted the file
1406
return 'delete', None
1408
raise AssertionError(
1409
'winner is OTHER, but file_id %r not in THIS or OTHER tree'
1412
def merge_contents(self, merge_hook_params):
1413
"""Fallback merge logic after user installed hooks."""
1414
# This function is used in merge hooks as the fallback instance.
1415
# Perhaps making this function and the functions it calls be a
1416
# a separate class would be better.
1417
if merge_hook_params.winner == 'other':
1418
# OTHER is a straight winner, so replace this contents with other
1419
return self._default_other_winner_merge(merge_hook_params)
1420
elif merge_hook_params.is_file_merge():
1421
# THIS and OTHER are both files, so text merge. Either
1422
# BASE is a file, or both converted to files, so at least we
1423
# have agreement that output should be a file.
1425
self.text_merge(merge_hook_params.trans_id,
1426
merge_hook_params.paths, merge_hook_params.file_id)
1427
except errors.BinaryFile:
1428
return 'not_applicable', None
1431
return 'not_applicable', None
1433
def get_lines(self, tree, path, file_id=None):
1434
"""Return the lines in a file, or an empty list."""
1438
kind = tree.kind(path, file_id)
1439
except errors.NoSuchFile:
1444
return tree.get_file_lines(path, file_id)
1446
def text_merge(self, trans_id, paths, file_id):
1447
"""Perform a three-way text merge on a file_id"""
1448
# it's possible that we got here with base as a different type.
1449
# if so, we just want two-way text conflicts.
1450
base_path, other_path, this_path = paths
1451
base_lines = self.get_lines(self.base_tree, base_path, file_id)
1452
other_lines = self.get_lines(self.other_tree, other_path, file_id)
1453
this_lines = self.get_lines(self.this_tree, this_path, file_id)
1454
m3 = merge3.Merge3(base_lines, this_lines, other_lines,
1455
is_cherrypick=self.cherrypick)
1456
start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
1457
if self.show_base is True:
1458
base_marker = '|' * 7
1462
def iter_merge3(retval):
1463
retval["text_conflicts"] = False
1464
for line in m3.merge_lines(name_a = "TREE",
1465
name_b = "MERGE-SOURCE",
1466
name_base = "BASE-REVISION",
1467
start_marker=start_marker,
1468
base_marker=base_marker,
1469
reprocess=self.reprocess):
1470
if line.startswith(start_marker):
1471
retval["text_conflicts"] = True
1472
yield line.replace(start_marker, '<' * 7)
1476
merge3_iterator = iter_merge3(retval)
1477
self.tt.create_file(merge3_iterator, trans_id)
1478
if retval["text_conflicts"] is True:
1479
self._raw_conflicts.append(('text conflict', trans_id))
1480
name = self.tt.final_name(trans_id)
1481
parent_id = self.tt.final_parent(trans_id)
1482
file_group = self._dump_conflicts(name, paths, parent_id, file_id,
1483
this_lines, base_lines,
1485
file_group.append(trans_id)
1487
def _get_filter_tree_path(self, file_id):
1488
if self.this_tree.supports_content_filtering():
1489
# We get the path from the working tree if it exists.
1490
# That fails though when OTHER is adding a file, so
1491
# we fall back to the other tree to find the path if
1492
# it doesn't exist locally.
1494
return self.this_tree.id2path(file_id)
1495
except errors.NoSuchId:
1496
return self.other_tree.id2path(file_id)
1497
# Skip the id2path lookup for older formats
1500
def _dump_conflicts(self, name, paths, parent_id, file_id, this_lines=None,
1501
base_lines=None, other_lines=None, set_version=False,
1503
"""Emit conflict files.
1504
If this_lines, base_lines, or other_lines are omitted, they will be
1505
determined automatically. If set_version is true, the .OTHER, .THIS
1506
or .BASE (in that order) will be created as versioned files.
1508
base_path, other_path, this_path = paths
1509
data = [('OTHER', self.other_tree, other_path, other_lines),
1510
('THIS', self.this_tree, this_path, this_lines)]
1512
data.append(('BASE', self.base_tree, base_path, base_lines))
1514
# We need to use the actual path in the working tree of the file here,
1515
# ignoring the conflict suffixes
1517
if wt.supports_content_filtering():
1519
filter_tree_path = wt.id2path(file_id)
1520
except errors.NoSuchId:
1521
# file has been deleted
1522
filter_tree_path = None
1524
# Skip the id2path lookup for older formats
1525
filter_tree_path = None
1529
for suffix, tree, path, lines in data:
1530
if path is not None:
1531
trans_id = self._conflict_file(
1532
name, parent_id, path, tree, file_id, suffix, lines,
1534
file_group.append(trans_id)
1535
if set_version and not versioned:
1536
self.tt.version_file(file_id, trans_id)
1540
def _conflict_file(self, name, parent_id, path, tree, file_id, suffix,
1541
lines=None, filter_tree_path=None):
1542
"""Emit a single conflict file."""
1543
name = name + '.' + suffix
1544
trans_id = self.tt.create_path(name, parent_id)
1545
transform.create_from_tree(
1546
self.tt, trans_id, tree, path,
1547
file_id=file_id, bytes=lines,
1548
filter_tree_path=filter_tree_path)
1551
def merge_executable(self, paths, file_id, file_status):
1552
"""Perform a merge on the execute bit."""
1553
executable = [self.executable(t, p, file_id) for t, p in zip([self.base_tree,
1554
self.other_tree, self.this_tree], paths)]
1555
self._merge_executable(paths, file_id, executable, file_status,
1556
resolver=self._three_way)
1558
def _merge_executable(self, paths, file_id, executable, file_status,
1560
"""Perform a merge on the execute bit."""
1561
base_executable, other_executable, this_executable = executable
1562
base_path, other_path, this_path = paths
1563
if file_status == "deleted":
1565
winner = resolver(*executable)
1566
if winner == "conflict":
1567
# There must be a None in here, if we have a conflict, but we
1568
# need executability since file status was not deleted.
1569
if other_path is None:
1573
if winner == 'this' and file_status != "modified":
1575
trans_id = self.tt.trans_id_file_id(file_id)
1576
if self.tt.final_kind(trans_id) != "file":
1578
if winner == "this":
1579
executability = this_executable
1581
if other_path is not None:
1582
executability = other_executable
1583
elif this_path is not None:
1584
executability = this_executable
1585
elif base_path is not None:
1586
executability = base_executable
1587
if executability is not None:
1588
trans_id = self.tt.trans_id_file_id(file_id)
1589
self.tt.set_executability(executability, trans_id)
1591
def cook_conflicts(self, fs_conflicts):
1592
"""Convert all conflicts into a form that doesn't depend on trans_id"""
1593
content_conflict_file_ids = set()
1594
cooked_conflicts = transform.cook_conflicts(fs_conflicts, self.tt)
1595
fp = transform.FinalPaths(self.tt)
1596
for conflict in self._raw_conflicts:
1597
conflict_type = conflict[0]
1598
if conflict_type == 'path conflict':
1600
this_parent, this_name,
1601
other_parent, other_name) = conflict[1:]
1602
if this_parent is None or this_name is None:
1603
this_path = '<deleted>'
1605
parent_path = fp.get_path(
1606
self.tt.trans_id_file_id(this_parent))
1607
this_path = osutils.pathjoin(parent_path, this_name)
1608
if other_parent is None or other_name is None:
1609
other_path = '<deleted>'
1611
if other_parent == self.other_tree.get_root_id():
1612
# The tree transform doesn't know about the other root,
1613
# so we special case here to avoid a NoFinalPath
1617
parent_path = fp.get_path(
1618
self.tt.trans_id_file_id(other_parent))
1619
other_path = osutils.pathjoin(parent_path, other_name)
1620
c = _mod_conflicts.Conflict.factory(
1621
'path conflict', path=this_path,
1622
conflict_path=other_path,
1624
elif conflict_type == 'contents conflict':
1625
for trans_id in conflict[1]:
1626
file_id = self.tt.final_file_id(trans_id)
1627
if file_id is not None:
1628
# Ok we found the relevant file-id
1630
path = fp.get_path(trans_id)
1631
for suffix in ('.BASE', '.THIS', '.OTHER'):
1632
if path.endswith(suffix):
1633
# Here is the raw path
1634
path = path[:-len(suffix)]
1636
c = _mod_conflicts.Conflict.factory(conflict_type,
1637
path=path, file_id=file_id)
1638
content_conflict_file_ids.add(file_id)
1639
elif conflict_type == 'text conflict':
1640
trans_id = conflict[1]
1641
path = fp.get_path(trans_id)
1642
file_id = self.tt.final_file_id(trans_id)
1643
c = _mod_conflicts.Conflict.factory(conflict_type,
1644
path=path, file_id=file_id)
1646
raise AssertionError('bad conflict type: %r' % (conflict,))
1647
cooked_conflicts.append(c)
1649
self.cooked_conflicts = []
1650
# We want to get rid of path conflicts when a corresponding contents
1651
# conflict exists. This can occur when one branch deletes a file while
1652
# the other renames *and* modifies it. In this case, the content
1653
# conflict is enough.
1654
for c in cooked_conflicts:
1655
if (c.typestring == 'path conflict'
1656
and c.file_id in content_conflict_file_ids):
1658
self.cooked_conflicts.append(c)
1659
self.cooked_conflicts.sort(key=_mod_conflicts.Conflict.sort_key)
1662
class WeaveMerger(Merge3Merger):
1663
"""Three-way tree merger, text weave merger."""
1664
supports_reprocess = True
1665
supports_show_base = False
1666
supports_reverse_cherrypick = False
1667
history_based = True
1668
requires_file_merge_plan = True
1670
def _generate_merge_plan(self, file_id, base):
1671
return self.this_tree.plan_file_merge(file_id, self.other_tree,
1674
def _merged_lines(self, file_id):
1675
"""Generate the merged lines.
1676
There is no distinction between lines that are meant to contain <<<<<<<
1680
base = self.base_tree
1683
plan = self._generate_merge_plan(file_id, base)
1684
if 'merge' in debug.debug_flags:
1686
trans_id = self.tt.trans_id_file_id(file_id)
1687
name = self.tt.final_name(trans_id) + '.plan'
1688
contents = ('%11s|%s' % l for l in plan)
1689
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1690
textmerge = versionedfile.PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1691
'>>>>>>> MERGE-SOURCE\n')
1692
lines, conflicts = textmerge.merge_lines(self.reprocess)
1694
base_lines = textmerge.base_from_plan()
1697
return lines, base_lines
1699
def text_merge(self, trans_id, paths, file_id):
1700
"""Perform a (weave) text merge for a given file and file-id.
1701
If conflicts are encountered, .THIS and .OTHER files will be emitted,
1702
and a conflict will be noted.
1704
base_path, other_path, this_path = paths
1705
lines, base_lines = self._merged_lines(file_id)
1707
# Note we're checking whether the OUTPUT is binary in this case,
1708
# because we don't want to get into weave merge guts.
1709
textfile.check_text_lines(lines)
1710
self.tt.create_file(lines, trans_id)
1711
if base_lines is not None:
1713
self._raw_conflicts.append(('text conflict', trans_id))
1714
name = self.tt.final_name(trans_id)
1715
parent_id = self.tt.final_parent(trans_id)
1716
file_group = self._dump_conflicts(name, paths, parent_id, file_id,
1718
base_lines=base_lines)
1719
file_group.append(trans_id)
1722
class LCAMerger(WeaveMerger):
1724
requires_file_merge_plan = True
1726
def _generate_merge_plan(self, file_id, base):
1727
return self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1730
class Diff3Merger(Merge3Merger):
1731
"""Three-way merger using external diff3 for text merging"""
1733
requires_file_merge_plan = False
1735
def dump_file(self, temp_dir, name, tree, path, file_id=None):
1736
out_path = osutils.pathjoin(temp_dir, name)
1737
with open(out_path, "wb") as out_file:
1738
in_file = tree.get_file(path, file_id=None)
1739
for line in in_file:
1740
out_file.write(line)
1743
def text_merge(self, trans_id, paths, file_id):
1744
"""Perform a diff3 merge using a specified file-id and trans-id.
1745
If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
1746
will be dumped, and a will be conflict noted.
1749
base_path, other_path, this_path = paths
1750
temp_dir = osutils.mkdtemp(prefix="bzr-")
1752
new_file = osutils.pathjoin(temp_dir, "new")
1753
this = self.dump_file(temp_dir, "this", self.this_tree, this_path, file_id)
1754
base = self.dump_file(temp_dir, "base", self.base_tree, base_path, file_id)
1755
other = self.dump_file(temp_dir, "other", self.other_tree, other_path, file_id)
1756
status = breezy.patch.diff3(new_file, this, base, other)
1757
if status not in (0, 1):
1758
raise errors.BzrError("Unhandled diff3 exit code")
1759
with open(new_file, 'rb') as f:
1760
self.tt.create_file(f, trans_id)
1762
name = self.tt.final_name(trans_id)
1763
parent_id = self.tt.final_parent(trans_id)
1764
self._dump_conflicts(name, paths, parent_id, file_id)
1765
self._raw_conflicts.append(('text conflict', trans_id))
1767
osutils.rmtree(temp_dir)
1770
class PathNotInTree(errors.BzrError):
1772
_fmt = """Merge-into failed because %(tree)s does not contain %(path)s."""
1774
def __init__(self, path, tree):
1775
errors.BzrError.__init__(self, path=path, tree=tree)
1778
class MergeIntoMerger(Merger):
1779
"""Merger that understands other_tree will be merged into a subdir.
1781
This also changes the Merger api so that it uses real Branch, revision_id,
1782
and RevisonTree objects, rather than using revision specs.
1785
def __init__(self, this_tree, other_branch, other_tree, target_subdir,
1786
source_subpath, other_rev_id=None):
1787
"""Create a new MergeIntoMerger object.
1789
source_subpath in other_tree will be effectively copied to
1790
target_subdir in this_tree.
1792
:param this_tree: The tree that we will be merging into.
1793
:param other_branch: The Branch we will be merging from.
1794
:param other_tree: The RevisionTree object we want to merge.
1795
:param target_subdir: The relative path where we want to merge
1796
other_tree into this_tree
1797
:param source_subpath: The relative path specifying the subtree of
1798
other_tree to merge into this_tree.
1800
# It is assumed that we are merging a tree that is not in our current
1801
# ancestry, which means we are using the "EmptyTree" as our basis.
1802
null_ancestor_tree = this_tree.branch.repository.revision_tree(
1803
_mod_revision.NULL_REVISION)
1804
super(MergeIntoMerger, self).__init__(
1805
this_branch=this_tree.branch,
1806
this_tree=this_tree,
1807
other_tree=other_tree,
1808
base_tree=null_ancestor_tree,
1810
self._target_subdir = target_subdir
1811
self._source_subpath = source_subpath
1812
self.other_branch = other_branch
1813
if other_rev_id is None:
1814
other_rev_id = other_tree.get_revision_id()
1815
self.other_rev_id = self.other_basis = other_rev_id
1816
self.base_is_ancestor = True
1817
self.backup_files = True
1818
self.merge_type = Merge3Merger
1819
self.show_base = False
1820
self.reprocess = False
1821
self.interesting_files = None
1822
self.merge_type = _MergeTypeParameterizer(MergeIntoMergeType,
1823
target_subdir=self._target_subdir,
1824
source_subpath=self._source_subpath)
1825
if self._source_subpath != '':
1826
# If this isn't a partial merge make sure the revisions will be
1828
self._maybe_fetch(self.other_branch, self.this_branch,
1831
def set_pending(self):
1832
if self._source_subpath != '':
1834
Merger.set_pending(self)
1837
class _MergeTypeParameterizer(object):
1838
"""Wrap a merge-type class to provide extra parameters.
1840
This is hack used by MergeIntoMerger to pass some extra parameters to its
1841
merge_type. Merger.do_merge() sets up its own set of parameters to pass to
1842
the 'merge_type' member. It is difficult override do_merge without
1843
re-writing the whole thing, so instead we create a wrapper which will pass
1844
the extra parameters.
1847
def __init__(self, merge_type, **kwargs):
1848
self._extra_kwargs = kwargs
1849
self._merge_type = merge_type
1851
def __call__(self, *args, **kwargs):
1852
kwargs.update(self._extra_kwargs)
1853
return self._merge_type(*args, **kwargs)
1855
def __getattr__(self, name):
1856
return getattr(self._merge_type, name)
1859
class MergeIntoMergeType(Merge3Merger):
1860
"""Merger that incorporates a tree (or part of a tree) into another."""
1862
def __init__(self, *args, **kwargs):
1863
"""Initialize the merger object.
1865
:param args: See Merge3Merger.__init__'s args.
1866
:param kwargs: See Merge3Merger.__init__'s keyword args, except for
1867
source_subpath and target_subdir.
1868
:keyword source_subpath: The relative path specifying the subtree of
1869
other_tree to merge into this_tree.
1870
:keyword target_subdir: The relative path where we want to merge
1871
other_tree into this_tree
1873
# All of the interesting work happens during Merge3Merger.__init__(),
1874
# so we have have to hack in to get our extra parameters set.
1875
self._source_subpath = kwargs.pop('source_subpath')
1876
self._target_subdir = kwargs.pop('target_subdir')
1877
super(MergeIntoMergeType, self).__init__(*args, **kwargs)
1879
def _compute_transform(self):
1880
with ui.ui_factory.nested_progress_bar() as child_pb:
1881
entries = self._entries_to_incorporate()
1882
entries = list(entries)
1883
for num, (entry, parent_id, relpath) in enumerate(entries):
1884
child_pb.update(gettext('Preparing file merge'), num, len(entries))
1885
parent_trans_id = self.tt.trans_id_file_id(parent_id)
1886
path = osutils.pathjoin(self._source_subpath, relpath)
1887
trans_id = transform.new_by_entry(path, self.tt, entry,
1888
parent_trans_id, self.other_tree)
1889
self._finish_computing_transform()
1891
def _entries_to_incorporate(self):
1892
"""Yields pairs of (inventory_entry, new_parent)."""
1893
other_inv = self.other_tree.root_inventory
1894
subdir_id = other_inv.path2id(self._source_subpath)
1895
if subdir_id is None:
1896
# XXX: The error would be clearer if it gave the URL of the source
1897
# branch, but we don't have a reference to that here.
1898
raise PathNotInTree(self._source_subpath, "Source tree")
1899
subdir = other_inv.get_entry(subdir_id)
1900
parent_in_target = osutils.dirname(self._target_subdir)
1901
target_id = self.this_tree.path2id(parent_in_target)
1902
if target_id is None:
1903
raise PathNotInTree(self._target_subdir, "Target tree")
1904
name_in_target = osutils.basename(self._target_subdir)
1905
merge_into_root = subdir.copy()
1906
merge_into_root.name = name_in_target
1907
if self.this_tree.has_id(merge_into_root.file_id):
1908
# Give the root a new file-id.
1909
# This can happen fairly easily if the directory we are
1910
# incorporating is the root, and both trees have 'TREE_ROOT' as
1911
# their root_id. Users will expect this to Just Work, so we
1912
# change the file-id here.
1913
# Non-root file-ids could potentially conflict too. That's really
1914
# an edge case, so we don't do anything special for those. We let
1915
# them cause conflicts.
1916
merge_into_root.file_id = generate_ids.gen_file_id(name_in_target)
1917
yield (merge_into_root, target_id, '')
1918
if subdir.kind != 'directory':
1919
# No children, so we are done.
1921
for path, entry in other_inv.iter_entries_by_dir(subdir_id):
1922
parent_id = entry.parent_id
1923
if parent_id == subdir.file_id:
1924
# The root's parent ID has changed, so make sure children of
1925
# the root refer to the new ID.
1926
parent_id = merge_into_root.file_id
1927
yield (entry, parent_id, path)
1930
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
1932
merge_type=Merge3Merger,
1936
interesting_files=None,
1938
change_reporter=None):
1939
"""Primary interface for merging.
1941
Typical use is probably::
1943
merge_inner(branch, branch.get_revision_tree(other_revision),
1944
branch.get_revision_tree(base_revision))
1946
if this_tree is None:
1947
raise errors.BzrError("breezy.merge.merge_inner requires a this_tree "
1949
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1950
change_reporter=change_reporter)
1951
merger.backup_files = backup_files
1952
merger.merge_type = merge_type
1953
merger.ignore_zero = ignore_zero
1954
merger.interesting_files = interesting_files
1955
merger.show_base = show_base
1956
merger.reprocess = reprocess
1957
merger.other_rev_id = other_rev_id
1958
merger.other_basis = other_rev_id
1959
get_revision_id = getattr(base_tree, 'get_revision_id', None)
1960
if get_revision_id is None:
1961
get_revision_id = base_tree.last_revision
1962
merger.cache_trees_with_revision_ids([other_tree, base_tree, this_tree])
1963
merger.set_base_revision(get_revision_id(), this_branch)
1964
return merger.do_merge()
1967
merge_type_registry = registry.Registry()
1968
merge_type_registry.register('diff3', Diff3Merger,
1969
"Merge using external diff3.")
1970
merge_type_registry.register('lca', LCAMerger,
1971
"LCA-newness merge.")
1972
merge_type_registry.register('merge3', Merge3Merger,
1973
"Native diff3-style merge.")
1974
merge_type_registry.register('weave', WeaveMerger,
1975
"Weave-based merge.")
1978
def get_merge_type_registry():
1979
"""Merge type registry was previously in breezy.option
1981
This method provides a backwards compatible way to retrieve it.
1983
return merge_type_registry
1986
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1987
def status_a(revision, text):
1988
if revision in ancestors_b:
1989
return 'killed-b', text
1991
return 'new-a', text
1993
def status_b(revision, text):
1994
if revision in ancestors_a:
1995
return 'killed-a', text
1997
return 'new-b', text
1999
plain_a = [t for (a, t) in annotated_a]
2000
plain_b = [t for (a, t) in annotated_b]
2001
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
2002
blocks = matcher.get_matching_blocks()
2005
for ai, bi, l in blocks:
2006
# process all mismatched sections
2007
# (last mismatched section is handled because blocks always
2008
# includes a 0-length last block)
2009
for revision, text in annotated_a[a_cur:ai]:
2010
yield status_a(revision, text)
2011
for revision, text in annotated_b[b_cur:bi]:
2012
yield status_b(revision, text)
2013
# and now the matched section
2016
for text_a in plain_a[ai:a_cur]:
2017
yield "unchanged", text_a
2020
class _PlanMergeBase(object):
2022
def __init__(self, a_rev, b_rev, vf, key_prefix):
2025
:param a_rev: Revision-id of one revision to merge
2026
:param b_rev: Revision-id of the other revision to merge
2027
:param vf: A VersionedFiles containing both revisions
2028
:param key_prefix: A prefix for accessing keys in vf, typically
2034
self._last_lines = None
2035
self._last_lines_revision_id = None
2036
self._cached_matching_blocks = {}
2037
self._key_prefix = key_prefix
2038
self._precache_tip_lines()
2040
def _precache_tip_lines(self):
2041
lines = self.get_lines([self.a_rev, self.b_rev])
2042
self.lines_a = lines[self.a_rev]
2043
self.lines_b = lines[self.b_rev]
2045
def get_lines(self, revisions):
2046
"""Get lines for revisions from the backing VersionedFiles.
2048
:raises RevisionNotPresent: on absent texts.
2050
keys = [(self._key_prefix + (rev,)) for rev in revisions]
2052
for record in self.vf.get_record_stream(keys, 'unordered', True):
2053
if record.storage_kind == 'absent':
2054
raise errors.RevisionNotPresent(record.key, self.vf)
2055
result[record.key[-1]] = osutils.chunks_to_lines(
2056
record.get_bytes_as('chunked'))
2059
def plan_merge(self):
2060
"""Generate a 'plan' for merging the two revisions.
2062
This involves comparing their texts and determining the cause of
2063
differences. If text A has a line and text B does not, then either the
2064
line was added to text A, or it was deleted from B. Once the causes
2065
are combined, they are written out in the format described in
2066
VersionedFile.plan_merge
2068
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
2069
unique_a, unique_b = self._unique_lines(blocks)
2070
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
2071
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
2072
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
2074
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
2077
for i, j, n in blocks:
2078
for a_index in range(last_i, i):
2079
if a_index in new_a:
2080
if a_index in killed_b:
2081
yield 'conflicted-a', self.lines_a[a_index]
2083
yield 'new-a', self.lines_a[a_index]
2085
yield 'killed-b', self.lines_a[a_index]
2086
for b_index in range(last_j, j):
2087
if b_index in new_b:
2088
if b_index in killed_a:
2089
yield 'conflicted-b', self.lines_b[b_index]
2091
yield 'new-b', self.lines_b[b_index]
2093
yield 'killed-a', self.lines_b[b_index]
2094
# handle common lines
2095
for a_index in range(i, i+n):
2096
yield 'unchanged', self.lines_a[a_index]
2100
def _get_matching_blocks(self, left_revision, right_revision):
2101
"""Return a description of which sections of two revisions match.
2103
See SequenceMatcher.get_matching_blocks
2105
cached = self._cached_matching_blocks.get((left_revision,
2107
if cached is not None:
2109
if self._last_lines_revision_id == left_revision:
2110
left_lines = self._last_lines
2111
right_lines = self.get_lines([right_revision])[right_revision]
2113
lines = self.get_lines([left_revision, right_revision])
2114
left_lines = lines[left_revision]
2115
right_lines = lines[right_revision]
2116
self._last_lines = right_lines
2117
self._last_lines_revision_id = right_revision
2118
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
2120
return matcher.get_matching_blocks()
2122
def _unique_lines(self, matching_blocks):
2123
"""Analyse matching_blocks to determine which lines are unique
2125
:return: a tuple of (unique_left, unique_right), where the values are
2126
sets of line numbers of unique lines.
2132
for i, j, n in matching_blocks:
2133
unique_left.extend(range(last_i, i))
2134
unique_right.extend(range(last_j, j))
2137
return unique_left, unique_right
2140
def _subtract_plans(old_plan, new_plan):
2141
"""Remove changes from new_plan that came from old_plan.
2143
It is assumed that the difference between the old_plan and new_plan
2144
is their choice of 'b' text.
2146
All lines from new_plan that differ from old_plan are emitted
2147
verbatim. All lines from new_plan that match old_plan but are
2148
not about the 'b' revision are emitted verbatim.
2150
Lines that match and are about the 'b' revision are the lines we
2151
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
2152
is skipped entirely.
2154
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
2157
for i, j, n in matcher.get_matching_blocks():
2158
for jj in range(last_j, j):
2160
for jj in range(j, j+n):
2161
plan_line = new_plan[jj]
2162
if plan_line[0] == 'new-b':
2164
elif plan_line[0] == 'killed-b':
2165
yield 'unchanged', plan_line[1]
2171
class _PlanMerge(_PlanMergeBase):
2172
"""Plan an annotate merge using on-the-fly annotation"""
2174
def __init__(self, a_rev, b_rev, vf, key_prefix):
2175
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
2176
self.a_key = self._key_prefix + (self.a_rev,)
2177
self.b_key = self._key_prefix + (self.b_rev,)
2178
self.graph = _mod_graph.Graph(self.vf)
2179
heads = self.graph.heads((self.a_key, self.b_key))
2181
# one side dominates, so we can just return its values, yay for
2183
# Ideally we would know that before we get this far
2184
self._head_key = heads.pop()
2185
if self._head_key == self.a_key:
2189
trace.mutter('found dominating revision for %s\n%s > %s', self.vf,
2190
self._head_key[-1], other)
2193
self._head_key = None
2196
def _precache_tip_lines(self):
2197
# Turn this into a no-op, because we will do this later
2200
def _find_recursive_lcas(self):
2201
"""Find all the ancestors back to a unique lca"""
2202
cur_ancestors = (self.a_key, self.b_key)
2203
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
2204
# rather than a key tuple. We will just map that directly to no common
2208
next_lcas = self.graph.find_lca(*cur_ancestors)
2209
# Map a plain NULL_REVISION to a simple no-ancestors
2210
if next_lcas == {_mod_revision.NULL_REVISION}:
2212
# Order the lca's based on when they were merged into the tip
2213
# While the actual merge portion of weave merge uses a set() of
2214
# active revisions, the order of insertion *does* effect the
2215
# implicit ordering of the texts.
2216
for rev_key in cur_ancestors:
2217
ordered_parents = tuple(self.graph.find_merge_order(rev_key,
2219
parent_map[rev_key] = ordered_parents
2220
if len(next_lcas) == 0:
2222
elif len(next_lcas) == 1:
2223
parent_map[list(next_lcas)[0]] = ()
2225
elif len(next_lcas) > 2:
2226
# More than 2 lca's, fall back to grabbing all nodes between
2227
# this and the unique lca.
2228
trace.mutter('More than 2 LCAs, falling back to all nodes for:'
2230
self.a_key, self.b_key, cur_ancestors)
2231
cur_lcas = next_lcas
2232
while len(cur_lcas) > 1:
2233
cur_lcas = self.graph.find_lca(*cur_lcas)
2234
if len(cur_lcas) == 0:
2235
# No common base to find, use the full ancestry
2238
unique_lca = list(cur_lcas)[0]
2239
if unique_lca == _mod_revision.NULL_REVISION:
2240
# find_lca will return a plain 'NULL_REVISION' rather
2241
# than a key tuple when there is no common ancestor, we
2242
# prefer to just use None, because it doesn't confuse
2243
# _get_interesting_texts()
2245
parent_map.update(self._find_unique_parents(next_lcas,
2248
cur_ancestors = next_lcas
2251
def _find_unique_parents(self, tip_keys, base_key):
2252
"""Find ancestors of tip that aren't ancestors of base.
2254
:param tip_keys: Nodes that are interesting
2255
:param base_key: Cull all ancestors of this node
2256
:return: The parent map for all revisions between tip_keys and
2257
base_key. base_key will be included. References to nodes outside of
2258
the ancestor set will also be removed.
2260
# TODO: this would be simpler if find_unique_ancestors took a list
2261
# instead of a single tip, internally it supports it, but it
2262
# isn't a "backwards compatible" api change.
2263
if base_key is None:
2264
parent_map = dict(self.graph.iter_ancestry(tip_keys))
2265
# We remove NULL_REVISION because it isn't a proper tuple key, and
2266
# thus confuses things like _get_interesting_texts, and our logic
2267
# to add the texts into the memory weave.
2268
if _mod_revision.NULL_REVISION in parent_map:
2269
parent_map.pop(_mod_revision.NULL_REVISION)
2272
for tip in tip_keys:
2274
self.graph.find_unique_ancestors(tip, [base_key]))
2275
parent_map = self.graph.get_parent_map(interesting)
2276
parent_map[base_key] = ()
2277
culled_parent_map, child_map, tails = self._remove_external_references(
2279
# Remove all the tails but base_key
2280
if base_key is not None:
2281
tails.remove(base_key)
2282
self._prune_tails(culled_parent_map, child_map, tails)
2283
# Now remove all the uninteresting 'linear' regions
2284
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
2288
def _remove_external_references(parent_map):
2289
"""Remove references that go outside of the parent map.
2291
:param parent_map: Something returned from Graph.get_parent_map(keys)
2292
:return: (filtered_parent_map, child_map, tails)
2293
filtered_parent_map is parent_map without external references
2294
child_map is the {parent_key: [child_keys]} mapping
2295
tails is a list of nodes that do not have any parents in the map
2297
# TODO: The basic effect of this function seems more generic than
2298
# _PlanMerge. But the specific details of building a child_map,
2299
# and computing tails seems very specific to _PlanMerge.
2300
# Still, should this be in Graph land?
2301
filtered_parent_map = {}
2304
for key, parent_keys in viewitems(parent_map):
2305
culled_parent_keys = [p for p in parent_keys if p in parent_map]
2306
if not culled_parent_keys:
2308
for parent_key in culled_parent_keys:
2309
child_map.setdefault(parent_key, []).append(key)
2310
# TODO: Do we want to do this, it adds overhead for every node,
2311
# just to say that the node has no children
2312
child_map.setdefault(key, [])
2313
filtered_parent_map[key] = culled_parent_keys
2314
return filtered_parent_map, child_map, tails
2317
def _prune_tails(parent_map, child_map, tails_to_remove):
2318
"""Remove tails from the parent map.
2320
This will remove the supplied revisions until no more children have 0
2323
:param parent_map: A dict of {child: [parents]}, this dictionary will
2324
be modified in place.
2325
:param tails_to_remove: A list of tips that should be removed,
2326
this list will be consumed
2327
:param child_map: The reverse dict of parent_map ({parent: [children]})
2328
this dict will be modified
2329
:return: None, parent_map will be modified in place.
2331
while tails_to_remove:
2332
next = tails_to_remove.pop()
2333
parent_map.pop(next)
2334
children = child_map.pop(next)
2335
for child in children:
2336
child_parents = parent_map[child]
2337
child_parents.remove(next)
2338
if len(child_parents) == 0:
2339
tails_to_remove.append(child)
2341
def _get_interesting_texts(self, parent_map):
2342
"""Return a dict of texts we are interested in.
2344
Note that the input is in key tuples, but the output is in plain
2347
:param parent_map: The output from _find_recursive_lcas
2348
:return: A dict of {'revision_id':lines} as returned by
2349
_PlanMergeBase.get_lines()
2351
all_revision_keys = set(parent_map)
2352
all_revision_keys.add(self.a_key)
2353
all_revision_keys.add(self.b_key)
2355
# Everything else is in 'keys' but get_lines is in 'revision_ids'
2356
all_texts = self.get_lines([k[-1] for k in all_revision_keys])
2359
def _build_weave(self):
2360
from .bzr import weave
2361
self._weave = weave.Weave(weave_name='in_memory_weave',
2362
allow_reserved=True)
2363
parent_map = self._find_recursive_lcas()
2365
all_texts = self._get_interesting_texts(parent_map)
2367
# Note: Unfortunately, the order given by topo_sort will effect the
2368
# ordering resolution in the output. Specifically, if you add A then B,
2369
# then in the output text A lines will show up before B lines. And, of
2370
# course, topo_sort doesn't guarantee any real ordering.
2371
# So we use merge_sort, and add a fake node on the tip.
2372
# This ensures that left-hand parents will always be inserted into the
2373
# weave before right-hand parents.
2374
tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
2375
parent_map[tip_key] = (self.a_key, self.b_key)
2377
for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
2381
# for key in tsort.topo_sort(parent_map):
2382
parent_keys = parent_map[key]
2383
revision_id = key[-1]
2384
parent_ids = [k[-1] for k in parent_keys]
2385
self._weave.add_lines(revision_id, parent_ids,
2386
all_texts[revision_id])
2388
def plan_merge(self):
2389
"""Generate a 'plan' for merging the two revisions.
2391
This involves comparing their texts and determining the cause of
2392
differences. If text A has a line and text B does not, then either the
2393
line was added to text A, or it was deleted from B. Once the causes
2394
are combined, they are written out in the format described in
2395
VersionedFile.plan_merge
2397
if self._head_key is not None: # There was a single head
2398
if self._head_key == self.a_key:
2401
if self._head_key != self.b_key:
2402
raise AssertionError('There was an invalid head: %s != %s'
2403
% (self.b_key, self._head_key))
2405
head_rev = self._head_key[-1]
2406
lines = self.get_lines([head_rev])[head_rev]
2407
return ((plan, line) for line in lines)
2408
return self._weave.plan_merge(self.a_rev, self.b_rev)
2411
class _PlanLCAMerge(_PlanMergeBase):
2413
This merge algorithm differs from _PlanMerge in that:
2415
1. comparisons are done against LCAs only
2416
2. cases where a contested line is new versus one LCA but old versus
2417
another are marked as conflicts, by emitting the line as conflicted-a
2420
This is faster, and hopefully produces more useful output.
2423
def __init__(self, a_rev, b_rev, vf, key_prefix, graph):
2424
_PlanMergeBase.__init__(self, a_rev, b_rev, vf, key_prefix)
2425
lcas = graph.find_lca(key_prefix + (a_rev,), key_prefix + (b_rev,))
2428
if lca == _mod_revision.NULL_REVISION:
2431
self.lcas.add(lca[-1])
2432
for lca in self.lcas:
2433
if _mod_revision.is_null(lca):
2436
lca_lines = self.get_lines([lca])[lca]
2437
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
2439
blocks = list(matcher.get_matching_blocks())
2440
self._cached_matching_blocks[(a_rev, lca)] = blocks
2441
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
2443
blocks = list(matcher.get_matching_blocks())
2444
self._cached_matching_blocks[(b_rev, lca)] = blocks
2446
def _determine_status(self, revision_id, unique_line_numbers):
2447
"""Determines the status unique lines versus all lcas.
2449
Basically, determines why the line is unique to this revision.
2451
A line may be determined new, killed, or both.
2453
If a line is determined new, that means it was not present in at least
2454
one LCA, and is not present in the other merge revision.
2456
If a line is determined killed, that means the line was present in
2459
If a line is killed and new, this indicates that the two merge
2460
revisions contain differing conflict resolutions.
2462
:param revision_id: The id of the revision in which the lines are
2464
:param unique_line_numbers: The line numbers of unique lines.
2465
:return: a tuple of (new_this, killed_other)
2469
unique_line_numbers = set(unique_line_numbers)
2470
for lca in self.lcas:
2471
blocks = self._get_matching_blocks(revision_id, lca)
2472
unique_vs_lca, _ignored = self._unique_lines(blocks)
2473
new.update(unique_line_numbers.intersection(unique_vs_lca))
2474
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
breezy/merge.py
