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
57
# TODO: Report back as changes are merged in
60
def transform_tree(from_tree, to_tree, interesting_files=None):
61
from_tree.lock_tree_write()
62
operation = cleanup.OperationWithCleanups(merge_inner)
63
operation.add_cleanup(from_tree.unlock)
64
operation.run_simple(from_tree.branch, to_tree, from_tree,
65
ignore_zero=True, this_tree=from_tree,
66
interesting_files=interesting_files)
69
class MergeHooks(hooks.Hooks):
72
hooks.Hooks.__init__(self, "breezy.merge", "Merger.hooks")
73
self.add_hook('merge_file_content',
74
"Called with a breezy.merge.Merger object to create a per file "
75
"merge object when starting a merge. "
76
"Should return either None or a subclass of "
77
"``breezy.merge.AbstractPerFileMerger``. "
78
"Such objects will then be called per file "
79
"that needs to be merged (including when one "
80
"side has deleted the file and the other has changed it). "
81
"See the AbstractPerFileMerger API docs for details on how it is "
84
self.add_hook('pre_merge',
85
'Called before a merge. '
86
'Receives a Merger object as the single argument.',
88
self.add_hook('post_merge',
89
'Called after a merge. '
90
'Receives a Merger object as the single argument. '
91
'The return value is ignored.',
95
class AbstractPerFileMerger(object):
96
"""PerFileMerger objects are used by plugins extending merge for breezy.
98
See ``breezy.plugins.news_merge.news_merge`` for an example concrete class.
100
:ivar merger: The Merge3Merger performing the merge.
103
def __init__(self, merger):
104
"""Create a PerFileMerger for use with merger."""
107
def merge_contents(self, merge_params):
108
"""Attempt to merge the contents of a single file.
110
:param merge_params: A breezy.merge.MergeFileHookParams
111
:return: A tuple of (status, chunks), where status is one of
112
'not_applicable', 'success', 'conflicted', or 'delete'. If status
113
is 'success' or 'conflicted', then chunks should be an iterable of
114
strings for the new file contents.
116
return ('not applicable', None)
119
class PerFileMerger(AbstractPerFileMerger):
120
"""Merge individual files when self.file_matches returns True.
122
This class is intended to be subclassed. The file_matches and
123
merge_matching methods should be overridden with concrete implementations.
126
def file_matches(self, params):
127
"""Return True if merge_matching should be called on this file.
129
Only called with merges of plain files with no clear winner.
131
Subclasses must override this.
133
raise NotImplementedError(self.file_matches)
135
def merge_contents(self, params):
136
"""Merge the contents of a single file."""
137
# Check whether this custom merge logic should be used.
139
# OTHER is a straight winner, rely on default merge.
140
params.winner == 'other' or
141
# THIS and OTHER aren't both files.
142
not params.is_file_merge() or
143
# The filename doesn't match
144
not self.file_matches(params)):
145
return 'not_applicable', None
146
return self.merge_matching(params)
148
def merge_matching(self, params):
149
"""Merge the contents of a single file that has matched the criteria
150
in PerFileMerger.merge_contents (is a conflict, is a file,
151
self.file_matches is True).
153
Subclasses must override this.
155
raise NotImplementedError(self.merge_matching)
158
class ConfigurableFileMerger(PerFileMerger):
159
"""Merge individual files when configured via a .conf file.
161
This is a base class for concrete custom file merging logic. Concrete
162
classes should implement ``merge_text``.
164
See ``breezy.plugins.news_merge.news_merge`` for an example concrete class.
166
:ivar affected_files: The configured file paths to merge.
168
:cvar name_prefix: The prefix to use when looking up configuration
169
details. <name_prefix>_merge_files describes the files targeted by the
172
:cvar default_files: The default file paths to merge when no configuration
179
def __init__(self, merger):
180
super(ConfigurableFileMerger, self).__init__(merger)
181
self.affected_files = None
182
self.default_files = self.__class__.default_files or []
183
self.name_prefix = self.__class__.name_prefix
184
if self.name_prefix is None:
185
raise ValueError("name_prefix must be set.")
187
def file_matches(self, params):
188
"""Check whether the file should call the merge hook.
190
<name_prefix>_merge_files configuration variable is a list of files
191
that should use the hook.
193
affected_files = self.affected_files
194
if affected_files is None:
195
config = self.merger.this_branch.get_config()
196
# Until bzr provides a better policy for caching the config, we
197
# just add the part we're interested in to the params to avoid
198
# reading the config files repeatedly (breezy.conf, location.conf,
200
config_key = self.name_prefix + '_merge_files'
201
affected_files = config.get_user_option_as_list(config_key)
202
if affected_files is None:
203
# If nothing was specified in the config, use the default.
204
affected_files = self.default_files
205
self.affected_files = affected_files
207
filepath = params.this_path
208
if filepath in affected_files:
212
def merge_matching(self, params):
213
return self.merge_text(params)
215
def merge_text(self, params):
216
"""Merge the byte contents of a single file.
218
This is called after checking that the merge should be performed in
219
merge_contents, and it should behave as per
220
``breezy.merge.AbstractPerFileMerger.merge_contents``.
222
raise NotImplementedError(self.merge_text)
225
class MergeFileHookParams(object):
226
"""Object holding parameters passed to merge_file_content hooks.
228
There are some fields hooks can access:
230
:ivar file_id: the file ID of the file being merged
231
:ivar base_path: Path in base tree
232
:ivar other_path: Path in other tree
233
:ivar this_path: Path in this tree
234
:ivar trans_id: the transform ID for the merge of this file
235
:ivar this_kind: kind of file_id in 'this' tree
236
:ivar other_kind: kind of file_id in 'other' tree
237
:ivar winner: one of 'this', 'other', 'conflict'
240
def __init__(self, merger, file_id, paths, trans_id, this_kind, other_kind,
242
self._merger = merger
243
self.file_id = file_id
245
self.base_path, self.other_path, self.this_path = paths
246
self.trans_id = trans_id
247
self.this_kind = this_kind
248
self.other_kind = other_kind
251
def is_file_merge(self):
252
"""True if this_kind and other_kind are both 'file'."""
253
return self.this_kind == 'file' and self.other_kind == 'file'
255
@decorators.cachedproperty
256
def base_lines(self):
257
"""The lines of the 'base' version of the file."""
258
return self._merger.get_lines(self._merger.base_tree, self.base_path, self.file_id)
260
@decorators.cachedproperty
261
def this_lines(self):
262
"""The lines of the 'this' version of the file."""
263
return self._merger.get_lines(self._merger.this_tree, self.this_path, self.file_id)
265
@decorators.cachedproperty
266
def other_lines(self):
267
"""The lines of the 'other' version of the file."""
268
return self._merger.get_lines(self._merger.other_tree, self.other_path, self.file_id)
271
class Merger(object):
275
def __init__(self, this_branch, other_tree=None, base_tree=None,
276
this_tree=None, change_reporter=None,
277
recurse='down', revision_graph=None):
278
object.__init__(self)
279
self.this_branch = this_branch
280
self.this_basis = _mod_revision.ensure_null(
281
this_branch.last_revision())
282
self.this_rev_id = None
283
self.this_tree = this_tree
284
self.this_revision_tree = None
285
self.this_basis_tree = None
286
self.other_tree = other_tree
287
self.other_branch = None
288
self.base_tree = base_tree
289
self.ignore_zero = False
290
self.backup_files = False
291
self.interesting_files = None
292
self.show_base = False
293
self.reprocess = False
295
self.recurse = recurse
296
self.change_reporter = change_reporter
297
self._cached_trees = {}
298
self._revision_graph = revision_graph
299
self._base_is_ancestor = None
300
self._base_is_other_ancestor = None
301
self._is_criss_cross = None
302
self._lca_trees = None
304
def cache_trees_with_revision_ids(self, trees):
305
"""Cache any tree in trees if it has a revision_id."""
306
for maybe_tree in trees:
307
if maybe_tree is None:
310
rev_id = maybe_tree.get_revision_id()
311
except AttributeError:
313
self._cached_trees[rev_id] = maybe_tree
316
def revision_graph(self):
317
if self._revision_graph is None:
318
self._revision_graph = self.this_branch.repository.get_graph()
319
return self._revision_graph
321
def _set_base_is_ancestor(self, value):
322
self._base_is_ancestor = value
324
def _get_base_is_ancestor(self):
325
if self._base_is_ancestor is None:
326
self._base_is_ancestor = self.revision_graph.is_ancestor(
327
self.base_rev_id, self.this_basis)
328
return self._base_is_ancestor
330
base_is_ancestor = property(_get_base_is_ancestor, _set_base_is_ancestor)
332
def _set_base_is_other_ancestor(self, value):
333
self._base_is_other_ancestor = value
335
def _get_base_is_other_ancestor(self):
336
if self._base_is_other_ancestor is None:
337
if self.other_basis is None:
339
self._base_is_other_ancestor = self.revision_graph.is_ancestor(
340
self.base_rev_id, self.other_basis)
341
return self._base_is_other_ancestor
343
base_is_other_ancestor = property(_get_base_is_other_ancestor,
344
_set_base_is_other_ancestor)
347
def from_uncommitted(tree, other_tree, base_tree=None):
348
"""Return a Merger for uncommitted changes in other_tree.
350
:param tree: The tree to merge into
351
:param other_tree: The tree to get uncommitted changes from
352
:param base_tree: The basis to use for the merge. If unspecified,
353
other_tree.basis_tree() will be used.
355
if base_tree is None:
356
base_tree = other_tree.basis_tree()
357
merger = Merger(tree.branch, other_tree, base_tree, tree)
358
merger.base_rev_id = merger.base_tree.get_revision_id()
359
merger.other_rev_id = None
360
merger.other_basis = merger.base_rev_id
364
def from_mergeable(klass, tree, mergeable):
365
"""Return a Merger for a bundle or merge directive.
367
:param tree: The tree to merge changes into
368
:param mergeable: A merge directive or bundle
370
mergeable.install_revisions(tree.branch.repository)
371
base_revision_id, other_revision_id, verified =\
372
mergeable.get_merge_request(tree.branch.repository)
373
revision_graph = tree.branch.repository.get_graph()
374
if base_revision_id is not None:
375
if (base_revision_id != _mod_revision.NULL_REVISION and
376
revision_graph.is_ancestor(
377
base_revision_id, tree.branch.last_revision())):
378
base_revision_id = None
380
trace.warning('Performing cherrypick')
381
merger = klass.from_revision_ids(tree, other_revision_id,
382
base_revision_id, revision_graph=
384
return merger, verified
387
def from_revision_ids(tree, other, base=None, other_branch=None,
388
base_branch=None, revision_graph=None,
390
"""Return a Merger for revision-ids.
392
:param tree: The tree to merge changes into
393
:param other: The revision-id to use as OTHER
394
:param base: The revision-id to use as BASE. If not specified, will
396
:param other_branch: A branch containing the other revision-id. If
397
not supplied, tree.branch is used.
398
:param base_branch: A branch containing the base revision-id. If
399
not supplied, other_branch or tree.branch will be used.
400
:param revision_graph: If you have a revision_graph precomputed, pass
401
it in, otherwise it will be created for you.
402
:param tree_branch: The branch associated with tree. If not supplied,
403
tree.branch will be used.
405
if tree_branch is None:
406
tree_branch = tree.branch
407
merger = Merger(tree_branch, this_tree=tree,
408
revision_graph=revision_graph)
409
if other_branch is None:
410
other_branch = tree.branch
411
merger.set_other_revision(other, other_branch)
415
if base_branch is None:
416
base_branch = other_branch
417
merger.set_base_revision(base, base_branch)
420
def revision_tree(self, revision_id, branch=None):
421
if revision_id not in self._cached_trees:
423
branch = self.this_branch
425
tree = self.this_tree.revision_tree(revision_id)
426
except errors.NoSuchRevisionInTree:
427
tree = branch.repository.revision_tree(revision_id)
428
self._cached_trees[revision_id] = tree
429
return self._cached_trees[revision_id]
431
def _get_tree(self, treespec, possible_transports=None):
432
location, revno = treespec
434
tree = workingtree.WorkingTree.open_containing(location)[0]
435
return tree.branch, tree
436
branch = _mod_branch.Branch.open_containing(
437
location, possible_transports)[0]
439
revision_id = branch.last_revision()
441
revision_id = branch.get_rev_id(revno)
442
revision_id = _mod_revision.ensure_null(revision_id)
443
return branch, self.revision_tree(revision_id, branch)
445
def set_interesting_files(self, file_list):
446
self.interesting_files = file_list
448
def set_pending(self):
449
if (not self.base_is_ancestor or not self.base_is_other_ancestor
450
or self.other_rev_id is None):
454
def _add_parent(self):
455
new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
456
new_parent_trees = []
457
operation = cleanup.OperationWithCleanups(
458
self.this_tree.set_parent_trees)
459
for revision_id in new_parents:
461
tree = self.revision_tree(revision_id)
462
except errors.NoSuchRevision:
466
operation.add_cleanup(tree.unlock)
467
new_parent_trees.append((revision_id, tree))
468
operation.run_simple(new_parent_trees, allow_leftmost_as_ghost=True)
470
def set_other(self, other_revision, possible_transports=None):
471
"""Set the revision and tree to merge from.
473
This sets the other_tree, other_rev_id, other_basis attributes.
475
:param other_revision: The [path, revision] list to merge from.
477
self.other_branch, self.other_tree = self._get_tree(other_revision,
479
if other_revision[1] == -1:
480
self.other_rev_id = _mod_revision.ensure_null(
481
self.other_branch.last_revision())
482
if _mod_revision.is_null(self.other_rev_id):
483
raise errors.NoCommits(self.other_branch)
484
self.other_basis = self.other_rev_id
485
elif other_revision[1] is not None:
486
self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
487
self.other_basis = self.other_rev_id
489
self.other_rev_id = None
490
self.other_basis = self.other_branch.last_revision()
491
if self.other_basis is None:
492
raise errors.NoCommits(self.other_branch)
493
if self.other_rev_id is not None:
494
self._cached_trees[self.other_rev_id] = self.other_tree
495
self._maybe_fetch(self.other_branch, self.this_branch, self.other_basis)
497
def set_other_revision(self, revision_id, other_branch):
498
"""Set 'other' based on a branch and revision id
500
:param revision_id: The revision to use for a tree
501
:param other_branch: The branch containing this tree
503
self.other_rev_id = revision_id
504
self.other_branch = other_branch
505
self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
506
self.other_tree = self.revision_tree(revision_id)
507
self.other_basis = revision_id
509
def set_base_revision(self, revision_id, branch):
510
"""Set 'base' based on a branch and revision id
512
:param revision_id: The revision to use for a tree
513
:param branch: The branch containing this tree
515
self.base_rev_id = revision_id
516
self.base_branch = branch
517
self._maybe_fetch(branch, self.this_branch, revision_id)
518
self.base_tree = self.revision_tree(revision_id)
520
def _maybe_fetch(self, source, target, revision_id):
521
if not source.repository.has_same_location(target.repository):
522
target.fetch(source, revision_id)
525
revisions = [_mod_revision.ensure_null(self.this_basis),
526
_mod_revision.ensure_null(self.other_basis)]
527
if _mod_revision.NULL_REVISION in revisions:
528
self.base_rev_id = _mod_revision.NULL_REVISION
529
self.base_tree = self.revision_tree(self.base_rev_id)
530
self._is_criss_cross = False
532
lcas = self.revision_graph.find_lca(revisions[0], revisions[1])
533
self._is_criss_cross = False
535
self.base_rev_id = _mod_revision.NULL_REVISION
537
self.base_rev_id = list(lcas)[0]
538
else: # len(lcas) > 1
539
self._is_criss_cross = True
541
# find_unique_lca can only handle 2 nodes, so we have to
542
# start back at the beginning. It is a shame to traverse
543
# the graph again, but better than re-implementing
545
self.base_rev_id = self.revision_graph.find_unique_lca(
546
revisions[0], revisions[1])
548
self.base_rev_id = self.revision_graph.find_unique_lca(
550
sorted_lca_keys = self.revision_graph.find_merge_order(
552
if self.base_rev_id == _mod_revision.NULL_REVISION:
553
self.base_rev_id = sorted_lca_keys[0]
555
if self.base_rev_id == _mod_revision.NULL_REVISION:
556
raise errors.UnrelatedBranches()
557
if self._is_criss_cross:
558
trace.warning('Warning: criss-cross merge encountered. See bzr'
559
' help criss-cross.')
560
trace.mutter('Criss-cross lcas: %r' % lcas)
561
if self.base_rev_id in lcas:
562
trace.mutter('Unable to find unique lca. '
563
'Fallback %r as best option.'
565
interesting_revision_ids = set(lcas)
566
interesting_revision_ids.add(self.base_rev_id)
567
interesting_trees = dict((t.get_revision_id(), t)
568
for t in self.this_branch.repository.revision_trees(
569
interesting_revision_ids))
570
self._cached_trees.update(interesting_trees)
571
if self.base_rev_id in lcas:
572
self.base_tree = interesting_trees[self.base_rev_id]
574
self.base_tree = interesting_trees.pop(self.base_rev_id)
575
self._lca_trees = [interesting_trees[key]
576
for key in sorted_lca_keys]
578
self.base_tree = self.revision_tree(self.base_rev_id)
579
self.base_is_ancestor = True
580
self.base_is_other_ancestor = True
581
trace.mutter('Base revid: %r' % self.base_rev_id)
583
def set_base(self, base_revision):
584
"""Set the base revision to use for the merge.
586
:param base_revision: A 2-list containing a path and revision number.
588
trace.mutter("doing merge() with no base_revision specified")
589
if base_revision == [None, None]:
592
base_branch, self.base_tree = self._get_tree(base_revision)
593
if base_revision[1] == -1:
594
self.base_rev_id = base_branch.last_revision()
595
elif base_revision[1] is None:
596
self.base_rev_id = _mod_revision.NULL_REVISION
598
self.base_rev_id = _mod_revision.ensure_null(
599
base_branch.get_rev_id(base_revision[1]))
600
self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
602
def make_merger(self):
603
kwargs = {'working_tree': self.this_tree, 'this_tree': self.this_tree,
604
'other_tree': self.other_tree,
605
'interesting_files': self.interesting_files,
606
'this_branch': self.this_branch,
607
'other_branch': self.other_branch,
609
if self.merge_type.requires_base:
610
kwargs['base_tree'] = self.base_tree
611
if self.merge_type.supports_reprocess:
612
kwargs['reprocess'] = self.reprocess
614
raise errors.BzrError(
615
"Conflict reduction is not supported for merge"
616
" type %s." % self.merge_type)
617
if self.merge_type.supports_show_base:
618
kwargs['show_base'] = self.show_base
620
raise errors.BzrError("Showing base is not supported for this"
621
" merge type. %s" % self.merge_type)
622
if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
623
and not self.base_is_other_ancestor):
624
raise errors.CannotReverseCherrypick()
625
if self.merge_type.supports_cherrypick:
626
kwargs['cherrypick'] = (not self.base_is_ancestor or
627
not self.base_is_other_ancestor)
628
if self._is_criss_cross and getattr(self.merge_type,
629
'supports_lca_trees', False):
630
kwargs['lca_trees'] = self._lca_trees
631
return self.merge_type(change_reporter=self.change_reporter,
634
def _do_merge_to(self):
635
merge = self.make_merger()
636
if self.other_branch is not None:
637
self.other_branch.update_references(self.this_branch)
638
for hook in Merger.hooks['pre_merge']:
641
for hook in Merger.hooks['post_merge']:
643
if self.recurse == 'down':
644
for relpath, file_id in self.this_tree.iter_references():
645
sub_tree = self.this_tree.get_nested_tree(relpath, file_id)
646
other_revision = self.other_tree.get_reference_revision(
648
if other_revision == sub_tree.last_revision():
650
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
651
sub_merge.merge_type = self.merge_type
652
other_branch = self.other_branch.reference_parent(
654
sub_merge.set_other_revision(other_revision, other_branch)
655
base_tree_path = _mod_tree.find_previous_path(
656
self.this_tree, self.base_tree, relpath)
657
base_revision = self.base_tree.get_reference_revision(
658
base_tree_path, file_id)
659
sub_merge.base_tree = \
660
sub_tree.branch.repository.revision_tree(base_revision)
661
sub_merge.base_rev_id = base_revision
666
operation = cleanup.OperationWithCleanups(self._do_merge_to)
667
self.this_tree.lock_tree_write()
668
operation.add_cleanup(self.this_tree.unlock)
669
if self.base_tree is not None:
670
self.base_tree.lock_read()
671
operation.add_cleanup(self.base_tree.unlock)
672
if self.other_tree is not None:
673
self.other_tree.lock_read()
674
operation.add_cleanup(self.other_tree.unlock)
675
merge = operation.run_simple()
676
if len(merge.cooked_conflicts) == 0:
677
if not self.ignore_zero and not trace.is_quiet():
678
trace.note(gettext("All changes applied successfully."))
680
trace.note(gettext("%d conflicts encountered.")
681
% len(merge.cooked_conflicts))
683
return len(merge.cooked_conflicts)
686
class _InventoryNoneEntry(object):
687
"""This represents an inventory entry which *isn't there*.
689
It simplifies the merging logic if we always have an InventoryEntry, even
690
if it isn't actually present
697
symlink_target = None
700
_none_entry = _InventoryNoneEntry()
703
class Merge3Merger(object):
704
"""Three-way merger that uses the merge3 text merger"""
706
supports_reprocess = True
707
supports_show_base = True
708
history_based = False
709
supports_cherrypick = True
710
supports_reverse_cherrypick = True
711
winner_idx = {"this": 2, "other": 1, "conflict": 1}
712
supports_lca_trees = True
713
requires_file_merge_plan = False
715
def __init__(self, working_tree, this_tree, base_tree, other_tree,
716
reprocess=False, show_base=False,
717
change_reporter=None, interesting_files=None, do_merge=True,
718
cherrypick=False, lca_trees=None, this_branch=None,
720
"""Initialize the merger object and perform the merge.
722
:param working_tree: The working tree to apply the merge to
723
:param this_tree: The local tree in the merge operation
724
:param base_tree: The common tree in the merge operation
725
:param other_tree: The other tree to merge changes from
726
:param this_branch: The branch associated with this_tree. Defaults to
727
this_tree.branch if not supplied.
728
:param other_branch: The branch associated with other_tree, if any.
729
:param: reprocess If True, perform conflict-reduction processing.
730
:param show_base: If True, show the base revision in text conflicts.
731
(incompatible with reprocess)
732
:param change_reporter: An object that should report changes made
733
:param interesting_files: The tree-relative paths of files that should
734
participate in the merge. If these paths refer to directories,
735
the contents of those directories will also be included. If not
736
specified, all files may participate in the
738
:param lca_trees: Can be set to a dictionary of {revision_id:rev_tree}
739
if the ancestry was found to include a criss-cross merge.
740
Otherwise should be None.
742
object.__init__(self)
743
if this_branch is None:
744
this_branch = this_tree.branch
745
self.interesting_files = interesting_files
746
self.working_tree = working_tree
747
self.this_tree = this_tree
748
self.base_tree = base_tree
749
self.other_tree = other_tree
750
self.this_branch = this_branch
751
self.other_branch = other_branch
752
self._raw_conflicts = []
753
self.cooked_conflicts = []
754
self.reprocess = reprocess
755
self.show_base = show_base
756
self._lca_trees = lca_trees
757
# Uncommenting this will change the default algorithm to always use
758
# _entries_lca. This can be useful for running the test suite and
759
# making sure we haven't missed any corner cases.
760
# if lca_trees is None:
761
# self._lca_trees = [self.base_tree]
762
self.change_reporter = change_reporter
763
self.cherrypick = cherrypick
768
operation = cleanup.OperationWithCleanups(self._do_merge)
769
self.working_tree.lock_tree_write()
770
operation.add_cleanup(self.working_tree.unlock)
771
self.this_tree.lock_read()
772
operation.add_cleanup(self.this_tree.unlock)
773
self.base_tree.lock_read()
774
operation.add_cleanup(self.base_tree.unlock)
775
self.other_tree.lock_read()
776
operation.add_cleanup(self.other_tree.unlock)
779
def _do_merge(self, operation):
780
self.tt = transform.TreeTransform(self.working_tree, None)
781
operation.add_cleanup(self.tt.finalize)
782
self._compute_transform()
783
results = self.tt.apply(no_conflicts=True)
784
self.write_modified(results)
786
self.working_tree.add_conflicts(self.cooked_conflicts)
787
except errors.UnsupportedOperation:
790
def make_preview_transform(self):
791
operation = cleanup.OperationWithCleanups(self._make_preview_transform)
792
self.base_tree.lock_read()
793
operation.add_cleanup(self.base_tree.unlock)
794
self.other_tree.lock_read()
795
operation.add_cleanup(self.other_tree.unlock)
796
return operation.run_simple()
798
def _make_preview_transform(self):
799
self.tt = transform.TransformPreview(self.working_tree)
800
self._compute_transform()
803
def _compute_transform(self):
804
if self._lca_trees is None:
805
entries = self._entries3()
806
resolver = self._three_way
808
entries = self._entries_lca()
809
resolver = self._lca_multi_way
810
# Prepare merge hooks
811
factories = Merger.hooks['merge_file_content']
812
# One hook for each registered one plus our default merger
813
hooks = [factory(self) for factory in factories] + [self]
814
self.active_hooks = [hook for hook in hooks if hook is not None]
815
with ui.ui_factory.nested_progress_bar() as child_pb:
816
for num, (file_id, changed, paths3, parents3, names3,
817
executable3) in enumerate(entries):
818
# Try merging each entry
819
child_pb.update(gettext('Preparing file merge'),
821
self._merge_names(file_id, paths3, parents3, names3, resolver=resolver)
823
file_status = self._do_merge_contents(paths3, file_id)
825
file_status = 'unmodified'
826
self._merge_executable(paths3, file_id, executable3,
827
file_status, resolver=resolver)
828
self.tt.fixup_new_roots()
829
self._finish_computing_transform()
831
def _finish_computing_transform(self):
832
"""Finalize the transform and report the changes.
834
This is the second half of _compute_transform.
836
with ui.ui_factory.nested_progress_bar() as child_pb:
837
fs_conflicts = transform.resolve_conflicts(self.tt, child_pb,
838
lambda t, c: transform.conflict_pass(t, c, self.other_tree))
839
if self.change_reporter is not None:
840
from breezy import delta
841
delta.report_changes(
842
self.tt.iter_changes(), self.change_reporter)
843
self.cook_conflicts(fs_conflicts)
844
for conflict in self.cooked_conflicts:
845
trace.warning('%s', conflict.describe())
848
"""Gather data about files modified between three trees.
850
Return a list of tuples of file_id, changed, parents3, names3,
851
executable3. changed is a boolean indicating whether the file contents
852
or kind were changed. parents3 is a tuple of parent ids for base,
853
other and this. names3 is a tuple of names for base, other and this.
854
executable3 is a tuple of execute-bit values for base, other and this.
857
iterator = self.other_tree.iter_changes(self.base_tree,
858
specific_files=self.interesting_files,
859
extra_trees=[self.this_tree])
860
this_interesting_files = self.this_tree.find_related_paths_across_trees(
861
self.interesting_files, trees=[self.other_tree])
862
this_entries = dict(self.this_tree.iter_entries_by_dir(
863
specific_files=this_interesting_files))
864
for (file_id, paths, changed, versioned, parents, names, kind,
865
executable) in iterator:
866
if paths[0] is not None:
867
this_path = _mod_tree.find_previous_path(
868
self.base_tree, self.this_tree, paths[0])
870
this_path = _mod_tree.find_previous_path(
871
self.other_tree, self.this_tree, paths[1])
872
this_entry = this_entries.get(this_path)
873
if this_entry is not None:
874
this_name = this_entry.name
875
this_parent = this_entry.parent_id
876
this_executable = this_entry.executable
880
this_executable = None
881
parents3 = parents + (this_parent,)
882
names3 = names + (this_name,)
883
paths3 = paths + (this_path, )
884
executable3 = executable + (this_executable,)
885
result.append((file_id, changed, paths3, parents3, names3, executable3))
888
def _entries_lca(self):
889
"""Gather data about files modified between multiple trees.
891
This compares OTHER versus all LCA trees, and for interesting entries,
892
it then compares with THIS and BASE.
894
For the multi-valued entries, the format will be (BASE, [lca1, lca2])
896
:return: [(file_id, changed, paths, parents, names, executable)], where:
898
* file_id: Simple file_id of the entry
899
* changed: Boolean, True if the kind or contents changed else False
900
* paths: ((base, [path, in, lcas]), path_other, path_this)
901
* parents: ((base, [parent_id, in, lcas]), parent_id_other,
903
* names: ((base, [name, in, lcas]), name_in_other, name_in_this)
904
* executable: ((base, [exec, in, lcas]), exec_in_other,
907
if self.interesting_files is not None:
908
lookup_trees = [self.this_tree, self.base_tree]
909
lookup_trees.extend(self._lca_trees)
910
# I think we should include the lca trees as well
911
interesting_files = self.other_tree.find_related_paths_across_trees(
912
self.interesting_files, lookup_trees)
914
interesting_files = None
916
walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
918
base_inventory = self.base_tree.root_inventory
919
this_inventory = self.this_tree.root_inventory
920
for path, file_id, other_ie, lca_values in walker.iter_all():
921
# Is this modified at all from any of the other trees?
923
other_ie = _none_entry
926
other_path = self.other_tree.id2path(file_id)
927
if interesting_files is not None and other_path not in interesting_files:
930
# If other_revision is found in any of the lcas, that means this
931
# node is uninteresting. This is because when merging, if there are
932
# multiple heads(), we have to create a new node. So if we didn't,
933
# we know that the ancestry is linear, and that OTHER did not
935
# See doc/developers/lca_merge_resolution.txt for details
936
other_revision = other_ie.revision
937
if other_revision is not None:
938
# We can't use this shortcut when other_revision is None,
939
# because it may be None because things are WorkingTrees, and
940
# not because it is *actually* None.
941
is_unmodified = False
942
for lca_path, ie in lca_values:
943
if ie is not None and ie.revision == other_revision:
951
for lca_path, lca_ie in lca_values:
953
lca_entries.append(_none_entry)
954
lca_paths.append(None)
956
lca_entries.append(lca_ie)
957
lca_paths.append(lca_path)
960
base_ie = base_inventory.get_entry(file_id)
961
except errors.NoSuchId:
962
base_ie = _none_entry
965
base_path = self.base_tree.id2path(file_id)
968
this_ie = this_inventory.get_entry(file_id)
969
except errors.NoSuchId:
970
this_ie = _none_entry
973
this_path = self.this_tree.id2path(file_id)
979
for lca_ie in lca_entries:
980
lca_kinds.append(lca_ie.kind)
981
lca_parent_ids.append(lca_ie.parent_id)
982
lca_names.append(lca_ie.name)
983
lca_executable.append(lca_ie.executable)
985
kind_winner = self._lca_multi_way(
986
(base_ie.kind, lca_kinds),
987
other_ie.kind, this_ie.kind)
988
parent_id_winner = self._lca_multi_way(
989
(base_ie.parent_id, lca_parent_ids),
990
other_ie.parent_id, this_ie.parent_id)
991
name_winner = self._lca_multi_way(
992
(base_ie.name, lca_names),
993
other_ie.name, this_ie.name)
995
content_changed = True
996
if kind_winner == 'this':
997
# No kind change in OTHER, see if there are *any* changes
998
if other_ie.kind == 'directory':
999
if parent_id_winner == 'this' and name_winner == 'this':
1000
# No change for this directory in OTHER, skip
1002
content_changed = False
1003
elif other_ie.kind is None or other_ie.kind == 'file':
1004
def get_sha1(tree, path):
1008
return tree.get_file_sha1(path, file_id)
1009
except errors.NoSuchFile:
1011
base_sha1 = get_sha1(self.base_tree, base_path)
1012
lca_sha1s = [get_sha1(tree, lca_path)
1014
in zip(self._lca_trees, lca_paths)]
1015
this_sha1 = get_sha1(self.this_tree, this_path)
1016
other_sha1 = get_sha1(self.other_tree, other_path)
1017
sha1_winner = self._lca_multi_way(
1018
(base_sha1, lca_sha1s), other_sha1, this_sha1,
1019
allow_overriding_lca=False)
1020
exec_winner = self._lca_multi_way(
1021
(base_ie.executable, lca_executable),
1022
other_ie.executable, this_ie.executable)
1023
if (parent_id_winner == 'this' and name_winner == 'this'
1024
and sha1_winner == 'this' and exec_winner == 'this'):
1025
# No kind, parent, name, exec, or content change for
1026
# OTHER, so this node is not considered interesting
1028
if sha1_winner == 'this':
1029
content_changed = False
1030
elif other_ie.kind == 'symlink':
1031
def get_target(ie, tree, path):
1032
if ie.kind != 'symlink':
1034
return tree.get_symlink_target(path, file_id)
1035
base_target = get_target(base_ie, self.base_tree, base_path)
1036
lca_targets = [get_target(ie, tree, lca_path) for ie, tree, lca_path
1037
in zip(lca_entries, self._lca_trees, lca_paths)]
1038
this_target = get_target(this_ie, self.this_tree, this_path)
1039
other_target = get_target(other_ie, self.other_tree, other_path)
1040
target_winner = self._lca_multi_way(
1041
(base_target, lca_targets),
1042
other_target, this_target)
1043
if (parent_id_winner == 'this' and name_winner == 'this'
1044
and target_winner == 'this'):
1045
# No kind, parent, name, or symlink target change
1048
if target_winner == 'this':
1049
content_changed = False
1050
elif other_ie.kind == 'tree-reference':
1051
# The 'changed' information seems to be handled at a higher
1052
# level. At least, _entries3 returns False for content
1053
# changed, even when at a new revision_id.
1054
content_changed = False
1055
if (parent_id_winner == 'this' and name_winner == 'this'):
1056
# Nothing interesting
1059
raise AssertionError('unhandled kind: %s' % other_ie.kind)
1061
# If we have gotten this far, that means something has changed
1062
result.append((file_id, content_changed,
1063
((base_path, lca_paths),
1064
other_path, this_path),
1065
((base_ie.parent_id, lca_parent_ids),
1066
other_ie.parent_id, this_ie.parent_id),
1067
((base_ie.name, lca_names),
1068
other_ie.name, this_ie.name),
1069
((base_ie.executable, lca_executable),
1070
other_ie.executable, this_ie.executable)
1074
def write_modified(self, results):
1075
if not self.working_tree.supports_merge_modified():
1077
modified_hashes = {}
1078
for path in results.modified_paths:
1079
wt_relpath = self.working_tree.relpath(path)
1080
file_id = self.working_tree.path2id(wt_relpath)
1083
hash = self.working_tree.get_file_sha1(wt_relpath, file_id)
1086
modified_hashes[file_id] = hash
1087
self.working_tree.set_merge_modified(modified_hashes)
1090
def parent(entry, file_id):
1091
"""Determine the parent for a file_id (used as a key method)"""
1094
return entry.parent_id
1097
def name(entry, file_id):
1098
"""Determine the name for a file_id (used as a key method)"""
1104
def contents_sha1(tree, path, file_id=None):
1105
"""Determine the sha1 of the file contents (used as a key method)."""
1107
return tree.get_file_sha1(path, file_id)
1108
except errors.NoSuchFile:
1112
def executable(tree, path, file_id=None):
1113
"""Determine the executability of a file-id (used as a key method)."""
1115
if tree.kind(path, file_id) != "file":
1117
except errors.NoSuchFile:
1119
return tree.is_executable(path, file_id)
1122
def kind(tree, path, file_id=None):
1123
"""Determine the kind of a file-id (used as a key method)."""
1125
return tree.kind(path, file_id)
1126
except errors.NoSuchFile:
1130
def _three_way(base, other, this):
1132
# if 'base == other', either they all agree, or only 'this' has
1135
elif this not in (base, other):
1136
# 'this' is neither 'base' nor 'other', so both sides changed
1139
# "Ambiguous clean merge" -- both sides have made the same change.
1142
# this == base: only other has changed.
1146
def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
1147
"""Consider LCAs when determining whether a change has occurred.
1149
If LCAS are all identical, this is the same as a _three_way comparison.
1151
:param bases: value in (BASE, [LCAS])
1152
:param other: value in OTHER
1153
:param this: value in THIS
1154
:param allow_overriding_lca: If there is more than one unique lca
1155
value, allow OTHER to override THIS if it has a new value, and
1156
THIS only has an lca value, or vice versa. This is appropriate for
1157
truly scalar values, not as much for non-scalars.
1158
:return: 'this', 'other', or 'conflict' depending on whether an entry
1161
# See doc/developers/lca_tree_merging.txt for details about this
1164
# Either Ambiguously clean, or nothing was actually changed. We
1167
base_val, lca_vals = bases
1168
# Remove 'base_val' from the lca_vals, because it is not interesting
1169
filtered_lca_vals = [lca_val for lca_val in lca_vals
1170
if lca_val != base_val]
1171
if len(filtered_lca_vals) == 0:
1172
return Merge3Merger._three_way(base_val, other, this)
1174
unique_lca_vals = set(filtered_lca_vals)
1175
if len(unique_lca_vals) == 1:
1176
return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
1178
if allow_overriding_lca:
1179
if other in unique_lca_vals:
1180
if this in unique_lca_vals:
1181
# Each side picked a different lca, conflict
1184
# This has a value which supersedes both lca values, and
1185
# other only has an lca value
1187
elif this in unique_lca_vals:
1188
# OTHER has a value which supersedes both lca values, and this
1189
# only has an lca value
1192
# At this point, the lcas disagree, and the tip disagree
1195
def merge_names(self, paths):
1196
def get_entry(tree, path):
1198
return next(tree.iter_entries_by_dir(specific_files=[path]))[1]
1199
except StopIteration:
1201
used_base_path, other_path, this_path = paths
1202
this_entry = get_entry(self.this_tree, this_path)
1203
other_entry = get_entry(self.other_tree, other_path)
1204
base_entry = get_entry(self.base_tree, base_path)
1205
entries = (base_entry, other_entry, this_entry)
1208
for entry in entries:
1211
parents.append(None)
1213
names.append(entry.name)
1214
parents.append(entry.parent_id)
1215
return self._merge_names(file_id, paths, parents, names,
1216
resolver=self._three_way)
1218
def _merge_names(self, file_id, paths, parents, names, resolver):
1219
"""Perform a merge on file_id names and parents"""
1220
base_name, other_name, this_name = names
1221
base_parent, other_parent, this_parent = parents
1222
unused_base_path, other_path, this_path = paths
1224
name_winner = resolver(*names)
1226
parent_id_winner = resolver(*parents)
1227
if this_name is None:
1228
if name_winner == "this":
1229
name_winner = "other"
1230
if parent_id_winner == "this":
1231
parent_id_winner = "other"
1232
if name_winner == "this" and parent_id_winner == "this":
1234
if name_winner == 'conflict' or parent_id_winner == 'conflict':
1235
# Creating helpers (.OTHER or .THIS) here cause problems down the
1236
# road if a ContentConflict needs to be created so we should not do
1238
trans_id = self.tt.trans_id_file_id(file_id)
1239
self._raw_conflicts.append(('path conflict', trans_id, file_id,
1240
this_parent, this_name,
1241
other_parent, other_name))
1242
if other_path is None:
1243
# it doesn't matter whether the result was 'other' or
1244
# 'conflict'-- if it has no file id, we leave it alone.
1246
parent_id = parents[self.winner_idx[parent_id_winner]]
1247
name = names[self.winner_idx[name_winner]]
1248
if parent_id is not None or name is not None:
1249
# if we get here, name_winner and parent_winner are set to safe
1251
if parent_id is None and name is not None:
1252
# if parent_id is None and name is non-None, current file is
1254
if names[self.winner_idx[parent_id_winner]] != '':
1255
raise AssertionError(
1256
'File looks like a root, but named %s' %
1257
names[self.winner_idx[parent_id_winner]])
1258
parent_trans_id = transform.ROOT_PARENT
1260
parent_trans_id = self.tt.trans_id_file_id(parent_id)
1261
self.tt.adjust_path(name, parent_trans_id,
1262
self.tt.trans_id_file_id(file_id))
1264
def _do_merge_contents(self, paths, file_id):
1265
"""Performs a merge on file_id contents."""
1266
def contents_pair(tree, path):
1270
kind = tree.kind(path, file_id)
1271
except errors.NoSuchFile:
1274
contents = tree.get_file_sha1(path, file_id)
1275
elif kind == "symlink":
1276
contents = tree.get_symlink_target(path, file_id)
1279
return kind, contents
1281
base_path, other_path, this_path = paths
1282
# See SPOT run. run, SPOT, run.
1283
# So we're not QUITE repeating ourselves; we do tricky things with
1285
other_pair = contents_pair(self.other_tree, other_path)
1286
this_pair = contents_pair(self.this_tree, this_path)
1288
(base_path, lca_paths) = base_path
1289
base_pair = contents_pair(self.base_tree, base_path)
1290
lca_pairs = [contents_pair(tree, path)
1291
for tree, path in zip(self._lca_trees, lca_paths)]
1292
winner = self._lca_multi_way((base_pair, lca_pairs), other_pair,
1293
this_pair, allow_overriding_lca=False)
1295
base_pair = contents_pair(self.base_tree, base_path)
1296
if base_pair == other_pair:
1299
# We delayed evaluating this_pair as long as we can to avoid
1300
# unnecessary sha1 calculation
1301
this_pair = contents_pair(self.this_tree, this_path)
1302
winner = self._three_way(base_pair, other_pair, this_pair)
1303
if winner == 'this':
1304
# No interesting changes introduced by OTHER
1306
# We have a hypothetical conflict, but if we have files, then we
1307
# can try to merge the content
1308
trans_id = self.tt.trans_id_file_id(file_id)
1309
params = MergeFileHookParams(
1310
self, file_id, (base_path, other_path,
1311
this_path), trans_id, this_pair[0],
1312
other_pair[0], winner)
1313
hooks = self.active_hooks
1314
hook_status = 'not_applicable'
1316
hook_status, lines = hook.merge_contents(params)
1317
if hook_status != 'not_applicable':
1318
# Don't try any more hooks, this one applies.
1320
# If the merge ends up replacing the content of the file, we get rid of
1321
# it at the end of this method (this variable is used to track the
1322
# exceptions to this rule).
1325
if hook_status == 'not_applicable':
1326
# No merge hook was able to resolve the situation. Two cases exist:
1327
# a content conflict or a duplicate one.
1329
name = self.tt.final_name(trans_id)
1330
parent_id = self.tt.final_parent(trans_id)
1332
inhibit_content_conflict = False
1333
if params.this_kind is None: # file_id is not in THIS
1334
# Is the name used for a different file_id ?
1335
if self.this_tree.is_versioned(other_path):
1336
# Two entries for the same path
1338
# versioning the merged file will trigger a duplicate
1340
self.tt.version_file(file_id, trans_id)
1341
transform.create_from_tree(
1342
self.tt, trans_id, self.other_tree,
1343
other_path, file_id=file_id,
1344
filter_tree_path=self._get_filter_tree_path(file_id))
1345
inhibit_content_conflict = True
1346
elif params.other_kind is None: # file_id is not in OTHER
1347
# Is the name used for a different file_id ?
1348
if self.other_tree.is_versioned(this_path):
1349
# Two entries for the same path again, but here, the other
1350
# entry will also be merged. We simply inhibit the
1351
# 'content' conflict creation because we know OTHER will
1352
# create (or has already created depending on ordering) an
1353
# entry at the same path. This will trigger a 'duplicate'
1356
inhibit_content_conflict = True
1357
if not inhibit_content_conflict:
1358
if params.this_kind is not None:
1359
self.tt.unversion_file(trans_id)
1360
# This is a contents conflict, because none of the available
1361
# functions could merge it.
1362
file_group = self._dump_conflicts(
1363
name, (base_path, other_path, this_path), parent_id,
1364
file_id, set_version=True)
1365
self._raw_conflicts.append(('contents conflict', file_group))
1366
elif hook_status == 'success':
1367
self.tt.create_file(lines, trans_id)
1368
elif hook_status == 'conflicted':
1369
# XXX: perhaps the hook should be able to provide
1370
# the BASE/THIS/OTHER files?
1371
self.tt.create_file(lines, trans_id)
1372
self._raw_conflicts.append(('text conflict', trans_id))
1373
name = self.tt.final_name(trans_id)
1374
parent_id = self.tt.final_parent(trans_id)
1375
self._dump_conflicts(
1376
name, (base_path, other_path, this_path), parent_id, file_id)
1377
elif hook_status == 'delete':
1378
self.tt.unversion_file(trans_id)
1380
elif hook_status == 'done':
1381
# The hook function did whatever it needs to do directly, no
1382
# further action needed here.
1385
raise AssertionError('unknown hook_status: %r' % (hook_status,))
1386
if not this_path and result == "modified":
1387
self.tt.version_file(file_id, trans_id)
1389
# The merge has been performed and produced a new content, so the
1390
# old contents should not be retained.
1391
self.tt.delete_contents(trans_id)
1394
def _default_other_winner_merge(self, merge_hook_params):
1395
"""Replace this contents with other."""
1396
file_id = merge_hook_params.file_id
1397
trans_id = merge_hook_params.trans_id
1398
if merge_hook_params.other_path is not None:
1399
# OTHER changed the file
1400
transform.create_from_tree(
1401
self.tt, trans_id, self.other_tree,
1402
merge_hook_params.other_path, file_id=file_id,
1403
filter_tree_path=self._get_filter_tree_path(file_id))
1405
elif merge_hook_params.this_path is not None:
1406
# OTHER deleted the file
1407
return 'delete', None
1409
raise AssertionError(
1410
'winner is OTHER, but file_id %r not in THIS or OTHER tree'
1413
def merge_contents(self, merge_hook_params):
1414
"""Fallback merge logic after user installed hooks."""
1415
# This function is used in merge hooks as the fallback instance.
1416
# Perhaps making this function and the functions it calls be a
1417
# a separate class would be better.
1418
if merge_hook_params.winner == 'other':
1419
# OTHER is a straight winner, so replace this contents with other
1420
return self._default_other_winner_merge(merge_hook_params)
1421
elif merge_hook_params.is_file_merge():
1422
# THIS and OTHER are both files, so text merge. Either
1423
# BASE is a file, or both converted to files, so at least we
1424
# have agreement that output should be a file.
1426
self.text_merge(merge_hook_params.trans_id,
1427
merge_hook_params.paths, merge_hook_params.file_id)
1428
except errors.BinaryFile:
1429
return 'not_applicable', None
1432
return 'not_applicable', None
1434
def get_lines(self, tree, path, file_id=None):
1435
"""Return the lines in a file, or an empty list."""
1439
kind = tree.kind(path, file_id)
1440
except errors.NoSuchFile:
1445
return tree.get_file_lines(path, file_id)
1447
def text_merge(self, trans_id, paths, file_id):
1448
"""Perform a three-way text merge on a file_id"""
1449
# it's possible that we got here with base as a different type.
1450
# if so, we just want two-way text conflicts.
1451
base_path, other_path, this_path = paths
1452
base_lines = self.get_lines(self.base_tree, base_path, file_id)
1453
other_lines = self.get_lines(self.other_tree, other_path, file_id)
1454
this_lines = self.get_lines(self.this_tree, this_path, file_id)
1455
m3 = merge3.Merge3(base_lines, this_lines, other_lines,
1456
is_cherrypick=self.cherrypick)
1457
start_marker = b"!START OF MERGE CONFLICT!" + b"I HOPE THIS IS UNIQUE"
1458
if self.show_base is True:
1459
base_marker = b'|' * 7
1463
def iter_merge3(retval):
1464
retval["text_conflicts"] = False
1465
for line in m3.merge_lines(name_a = b"TREE",
1466
name_b = b"MERGE-SOURCE",
1467
name_base = b"BASE-REVISION",
1468
start_marker=start_marker,
1469
base_marker=base_marker,
1470
reprocess=self.reprocess):
1471
if line.startswith(start_marker):
1472
retval["text_conflicts"] = True
1473
yield line.replace(start_marker, b'<' * 7)
1477
merge3_iterator = iter_merge3(retval)
1478
self.tt.create_file(merge3_iterator, trans_id)
1479
if retval["text_conflicts"] is True:
1480
self._raw_conflicts.append(('text conflict', trans_id))
1481
name = self.tt.final_name(trans_id)
1482
parent_id = self.tt.final_parent(trans_id)
1483
file_group = self._dump_conflicts(name, paths, parent_id, file_id,
1484
this_lines, base_lines,
1486
file_group.append(trans_id)
1488
def _get_filter_tree_path(self, file_id):
1489
if self.this_tree.supports_content_filtering():
1490
# We get the path from the working tree if it exists.
1491
# That fails though when OTHER is adding a file, so
1492
# we fall back to the other tree to find the path if
1493
# it doesn't exist locally.
1495
return self.this_tree.id2path(file_id)
1496
except errors.NoSuchId:
1497
return self.other_tree.id2path(file_id)
1498
# Skip the id2path lookup for older formats
1501
def _dump_conflicts(self, name, paths, parent_id, file_id, this_lines=None,
1502
base_lines=None, other_lines=None, set_version=False,
1504
"""Emit conflict files.
1505
If this_lines, base_lines, or other_lines are omitted, they will be
1506
determined automatically. If set_version is true, the .OTHER, .THIS
1507
or .BASE (in that order) will be created as versioned files.
1509
base_path, other_path, this_path = paths
1510
data = [('OTHER', self.other_tree, other_path, other_lines),
1511
('THIS', self.this_tree, this_path, this_lines)]
1513
data.append(('BASE', self.base_tree, base_path, base_lines))
1515
# We need to use the actual path in the working tree of the file here,
1516
# ignoring the conflict suffixes
1518
if wt.supports_content_filtering():
1520
filter_tree_path = wt.id2path(file_id)
1521
except errors.NoSuchId:
1522
# file has been deleted
1523
filter_tree_path = None
1525
# Skip the id2path lookup for older formats
1526
filter_tree_path = None
1530
for suffix, tree, path, lines in data:
1531
if path is not None:
1532
trans_id = self._conflict_file(
1533
name, parent_id, path, tree, file_id, suffix, lines,
1535
file_group.append(trans_id)
1536
if set_version and not versioned:
1537
self.tt.version_file(file_id, trans_id)
1541
def _conflict_file(self, name, parent_id, path, tree, file_id, suffix,
1542
lines=None, filter_tree_path=None):
1543
"""Emit a single conflict file."""
1544
name = name + '.' + suffix
1545
trans_id = self.tt.create_path(name, parent_id)
1546
transform.create_from_tree(
1547
self.tt, trans_id, tree, path,
1548
file_id=file_id, chunks=lines,
1549
filter_tree_path=filter_tree_path)
1552
def merge_executable(self, paths, file_id, file_status):
1553
"""Perform a merge on the execute bit."""
1554
executable = [self.executable(t, p, file_id) for t, p in zip([self.base_tree,
1555
self.other_tree, self.this_tree], paths)]
1556
self._merge_executable(paths, file_id, executable, file_status,
1557
resolver=self._three_way)
1559
def _merge_executable(self, paths, file_id, executable, file_status,
1561
"""Perform a merge on the execute bit."""
1562
base_executable, other_executable, this_executable = executable
1563
base_path, other_path, this_path = paths
1564
if file_status == "deleted":
1566
winner = resolver(*executable)
1567
if winner == "conflict":
1568
# There must be a None in here, if we have a conflict, but we
1569
# need executability since file status was not deleted.
1570
if other_path is None:
1574
if winner == 'this' and file_status != "modified":
1576
trans_id = self.tt.trans_id_file_id(file_id)
1577
if self.tt.final_kind(trans_id) != "file":
1579
if winner == "this":
1580
executability = this_executable
1582
if other_path is not None:
1583
executability = other_executable
1584
elif this_path is not None:
1585
executability = this_executable
1586
elif base_path is not None:
1587
executability = base_executable
1588
if executability is not None:
1589
trans_id = self.tt.trans_id_file_id(file_id)
1590
self.tt.set_executability(executability, trans_id)
1592
def cook_conflicts(self, fs_conflicts):
1593
"""Convert all conflicts into a form that doesn't depend on trans_id"""
1594
content_conflict_file_ids = set()
1595
cooked_conflicts = transform.cook_conflicts(fs_conflicts, self.tt)
1596
fp = transform.FinalPaths(self.tt)
1597
for conflict in self._raw_conflicts:
1598
conflict_type = conflict[0]
1599
if conflict_type == 'path conflict':
1601
this_parent, this_name,
1602
other_parent, other_name) = conflict[1:]
1603
if this_parent is None or this_name is None:
1604
this_path = '<deleted>'
1606
parent_path = fp.get_path(
1607
self.tt.trans_id_file_id(this_parent))
1608
this_path = osutils.pathjoin(parent_path, this_name)
1609
if other_parent is None or other_name is None:
1610
other_path = '<deleted>'
1612
if other_parent == self.other_tree.get_root_id():
1613
# The tree transform doesn't know about the other root,
1614
# so we special case here to avoid a NoFinalPath
1618
parent_path = fp.get_path(
1619
self.tt.trans_id_file_id(other_parent))
1620
other_path = osutils.pathjoin(parent_path, other_name)
1621
c = _mod_conflicts.Conflict.factory(
1622
'path conflict', path=this_path,
1623
conflict_path=other_path,
1625
elif conflict_type == 'contents conflict':
1626
for trans_id in conflict[1]:
1627
file_id = self.tt.final_file_id(trans_id)
1628
if file_id is not None:
1629
# Ok we found the relevant file-id
1631
path = fp.get_path(trans_id)
1632
for suffix in ('.BASE', '.THIS', '.OTHER'):
1633
if path.endswith(suffix):
1634
# Here is the raw path
1635
path = path[:-len(suffix)]
1637
c = _mod_conflicts.Conflict.factory(conflict_type,
1638
path=path, file_id=file_id)
1639
content_conflict_file_ids.add(file_id)
1640
elif conflict_type == 'text conflict':
1641
trans_id = conflict[1]
1642
path = fp.get_path(trans_id)
1643
file_id = self.tt.final_file_id(trans_id)
1644
c = _mod_conflicts.Conflict.factory(conflict_type,
1645
path=path, file_id=file_id)
1647
raise AssertionError('bad conflict type: %r' % (conflict,))
1648
cooked_conflicts.append(c)
1650
self.cooked_conflicts = []
1651
# We want to get rid of path conflicts when a corresponding contents
1652
# conflict exists. This can occur when one branch deletes a file while
1653
# the other renames *and* modifies it. In this case, the content
1654
# conflict is enough.
1655
for c in cooked_conflicts:
1656
if (c.typestring == 'path conflict'
1657
and c.file_id in content_conflict_file_ids):
1659
self.cooked_conflicts.append(c)
1660
self.cooked_conflicts.sort(key=_mod_conflicts.Conflict.sort_key)
1663
class WeaveMerger(Merge3Merger):
1664
"""Three-way tree merger, text weave merger."""
1665
supports_reprocess = True
1666
supports_show_base = False
1667
supports_reverse_cherrypick = False
1668
history_based = True
1669
requires_file_merge_plan = True
1671
def _generate_merge_plan(self, file_id, base):
1672
return self.this_tree.plan_file_merge(file_id, self.other_tree,
1675
def _merged_lines(self, file_id):
1676
"""Generate the merged lines.
1677
There is no distinction between lines that are meant to contain <<<<<<<
1681
base = self.base_tree
1684
plan = self._generate_merge_plan(file_id, base)
1685
if 'merge' in debug.debug_flags:
1687
trans_id = self.tt.trans_id_file_id(file_id)
1688
name = self.tt.final_name(trans_id) + '.plan'
1689
contents = (b'%11s|%s' % l for l in plan)
1690
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1691
textmerge = versionedfile.PlanWeaveMerge(plan, b'<<<<<<< TREE\n',
1692
b'>>>>>>> MERGE-SOURCE\n')
1693
lines, conflicts = textmerge.merge_lines(self.reprocess)
1695
base_lines = textmerge.base_from_plan()
1698
return lines, base_lines
1700
def text_merge(self, trans_id, paths, file_id):
1701
"""Perform a (weave) text merge for a given file and file-id.
1702
If conflicts are encountered, .THIS and .OTHER files will be emitted,
1703
and a conflict will be noted.
1705
base_path, other_path, this_path = paths
1706
lines, base_lines = self._merged_lines(file_id)
1708
# Note we're checking whether the OUTPUT is binary in this case,
1709
# because we don't want to get into weave merge guts.
1710
textfile.check_text_lines(lines)
1711
self.tt.create_file(lines, trans_id)
1712
if base_lines is not None:
1714
self._raw_conflicts.append(('text conflict', trans_id))
1715
name = self.tt.final_name(trans_id)
1716
parent_id = self.tt.final_parent(trans_id)
1717
file_group = self._dump_conflicts(name, paths, parent_id, file_id,
1719
base_lines=base_lines)
1720
file_group.append(trans_id)
1723
class LCAMerger(WeaveMerger):
1725
requires_file_merge_plan = True
1727
def _generate_merge_plan(self, file_id, base):
1728
return self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1731
class Diff3Merger(Merge3Merger):
1732
"""Three-way merger using external diff3 for text merging"""
1734
requires_file_merge_plan = False
1736
def dump_file(self, temp_dir, name, tree, path, file_id=None):
1737
out_path = osutils.pathjoin(temp_dir, name)
1738
with open(out_path, "wb") as out_file:
1739
in_file = tree.get_file(path, file_id=None)
1740
for line in in_file:
1741
out_file.write(line)
1744
def text_merge(self, trans_id, paths, file_id):
1745
"""Perform a diff3 merge using a specified file-id and trans-id.
1746
If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
1747
will be dumped, and a will be conflict noted.
1750
base_path, other_path, this_path = paths
1751
temp_dir = osutils.mkdtemp(prefix="bzr-")
1753
new_file = osutils.pathjoin(temp_dir, "new")
1754
this = self.dump_file(temp_dir, "this", self.this_tree, this_path, file_id)
1755
base = self.dump_file(temp_dir, "base", self.base_tree, base_path, file_id)
1756
other = self.dump_file(temp_dir, "other", self.other_tree, other_path, file_id)
1757
status = breezy.patch.diff3(new_file, this, base, other)
1758
if status not in (0, 1):
1759
raise errors.BzrError("Unhandled diff3 exit code")
1760
with open(new_file, 'rb') as f:
1761
self.tt.create_file(f, trans_id)
1763
name = self.tt.final_name(trans_id)
1764
parent_id = self.tt.final_parent(trans_id)
1765
self._dump_conflicts(name, paths, parent_id, file_id)
1766
self._raw_conflicts.append(('text conflict', trans_id))
1768
osutils.rmtree(temp_dir)
1771
class PathNotInTree(errors.BzrError):
1773
_fmt = """Merge-into failed because %(tree)s does not contain %(path)s."""
1775
def __init__(self, path, tree):
1776
errors.BzrError.__init__(self, path=path, tree=tree)
1779
class MergeIntoMerger(Merger):
1780
"""Merger that understands other_tree will be merged into a subdir.
1782
This also changes the Merger api so that it uses real Branch, revision_id,
1783
and RevisonTree objects, rather than using revision specs.
1786
def __init__(self, this_tree, other_branch, other_tree, target_subdir,
1787
source_subpath, other_rev_id=None):
1788
"""Create a new MergeIntoMerger object.
1790
source_subpath in other_tree will be effectively copied to
1791
target_subdir in this_tree.
1793
:param this_tree: The tree that we will be merging into.
1794
:param other_branch: The Branch we will be merging from.
1795
:param other_tree: The RevisionTree object we want to merge.
1796
:param target_subdir: The relative path where we want to merge
1797
other_tree into this_tree
1798
:param source_subpath: The relative path specifying the subtree of
1799
other_tree to merge into this_tree.
1801
# It is assumed that we are merging a tree that is not in our current
1802
# ancestry, which means we are using the "EmptyTree" as our basis.
1803
null_ancestor_tree = this_tree.branch.repository.revision_tree(
1804
_mod_revision.NULL_REVISION)
1805
super(MergeIntoMerger, self).__init__(
1806
this_branch=this_tree.branch,
1807
this_tree=this_tree,
1808
other_tree=other_tree,
1809
base_tree=null_ancestor_tree,
1811
self._target_subdir = target_subdir
1812
self._source_subpath = source_subpath
1813
self.other_branch = other_branch
1814
if other_rev_id is None:
1815
other_rev_id = other_tree.get_revision_id()
1816
self.other_rev_id = self.other_basis = other_rev_id
1817
self.base_is_ancestor = True
1818
self.backup_files = True
1819
self.merge_type = Merge3Merger
1820
self.show_base = False
1821
self.reprocess = False
1822
self.interesting_files = None
1823
self.merge_type = _MergeTypeParameterizer(MergeIntoMergeType,
1824
target_subdir=self._target_subdir,
1825
source_subpath=self._source_subpath)
1826
if self._source_subpath != '':
1827
# If this isn't a partial merge make sure the revisions will be
1829
self._maybe_fetch(self.other_branch, self.this_branch,
1832
def set_pending(self):
1833
if self._source_subpath != '':
1835
Merger.set_pending(self)
1838
class _MergeTypeParameterizer(object):
1839
"""Wrap a merge-type class to provide extra parameters.
1841
This is hack used by MergeIntoMerger to pass some extra parameters to its
1842
merge_type. Merger.do_merge() sets up its own set of parameters to pass to
1843
the 'merge_type' member. It is difficult override do_merge without
1844
re-writing the whole thing, so instead we create a wrapper which will pass
1845
the extra parameters.
1848
def __init__(self, merge_type, **kwargs):
1849
self._extra_kwargs = kwargs
1850
self._merge_type = merge_type
1852
def __call__(self, *args, **kwargs):
1853
kwargs.update(self._extra_kwargs)
1854
return self._merge_type(*args, **kwargs)
1856
def __getattr__(self, name):
1857
return getattr(self._merge_type, name)
1860
class MergeIntoMergeType(Merge3Merger):
1861
"""Merger that incorporates a tree (or part of a tree) into another."""
1863
def __init__(self, *args, **kwargs):
1864
"""Initialize the merger object.
1866
:param args: See Merge3Merger.__init__'s args.
1867
:param kwargs: See Merge3Merger.__init__'s keyword args, except for
1868
source_subpath and target_subdir.
1869
:keyword source_subpath: The relative path specifying the subtree of
1870
other_tree to merge into this_tree.
1871
:keyword target_subdir: The relative path where we want to merge
1872
other_tree into this_tree
1874
# All of the interesting work happens during Merge3Merger.__init__(),
1875
# so we have have to hack in to get our extra parameters set.
1876
self._source_subpath = kwargs.pop('source_subpath')
1877
self._target_subdir = kwargs.pop('target_subdir')
1878
super(MergeIntoMergeType, self).__init__(*args, **kwargs)
1880
def _compute_transform(self):
1881
with ui.ui_factory.nested_progress_bar() as child_pb:
1882
entries = self._entries_to_incorporate()
1883
entries = list(entries)
1884
for num, (entry, parent_id, relpath) in enumerate(entries):
1885
child_pb.update(gettext('Preparing file merge'), num, len(entries))
1886
parent_trans_id = self.tt.trans_id_file_id(parent_id)
1887
path = osutils.pathjoin(self._source_subpath, relpath)
1888
trans_id = transform.new_by_entry(path, self.tt, entry,
1889
parent_trans_id, self.other_tree)
1890
self._finish_computing_transform()
1892
def _entries_to_incorporate(self):
1893
"""Yields pairs of (inventory_entry, new_parent)."""
1894
other_inv = self.other_tree.root_inventory
1895
subdir_id = other_inv.path2id(self._source_subpath)
1896
if subdir_id is None:
1897
# XXX: The error would be clearer if it gave the URL of the source
1898
# branch, but we don't have a reference to that here.
1899
raise PathNotInTree(self._source_subpath, "Source tree")
1900
subdir = other_inv.get_entry(subdir_id)
1901
parent_in_target = osutils.dirname(self._target_subdir)
1902
target_id = self.this_tree.path2id(parent_in_target)
1903
if target_id is None:
1904
raise PathNotInTree(self._target_subdir, "Target tree")
1905
name_in_target = osutils.basename(self._target_subdir)
1906
merge_into_root = subdir.copy()
1907
merge_into_root.name = name_in_target
1908
if self.this_tree.has_id(merge_into_root.file_id):
1909
# Give the root a new file-id.
1910
# This can happen fairly easily if the directory we are
1911
# incorporating is the root, and both trees have 'TREE_ROOT' as
1912
# their root_id. Users will expect this to Just Work, so we
1913
# change the file-id here.
1914
# Non-root file-ids could potentially conflict too. That's really
1915
# an edge case, so we don't do anything special for those. We let
1916
# them cause conflicts.
1917
merge_into_root.file_id = generate_ids.gen_file_id(name_in_target)
1918
yield (merge_into_root, target_id, '')
1919
if subdir.kind != 'directory':
1920
# No children, so we are done.
1922
for path, entry in other_inv.iter_entries_by_dir(subdir_id):
1923
parent_id = entry.parent_id
1924
if parent_id == subdir.file_id:
1925
# The root's parent ID has changed, so make sure children of
1926
# the root refer to the new ID.
1927
parent_id = merge_into_root.file_id
1928
yield (entry, parent_id, path)
1931
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
1933
merge_type=Merge3Merger,
1937
interesting_files=None,
1939
change_reporter=None):
1940
"""Primary interface for merging.
1942
Typical use is probably::
1944
merge_inner(branch, branch.get_revision_tree(other_revision),
1945
branch.get_revision_tree(base_revision))
1947
if this_tree is None:
1948
raise errors.BzrError("breezy.merge.merge_inner requires a this_tree "
1950
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1951
change_reporter=change_reporter)
1952
merger.backup_files = backup_files
1953
merger.merge_type = merge_type
1954
merger.ignore_zero = ignore_zero
1955
merger.interesting_files = interesting_files
1956
merger.show_base = show_base
1957
merger.reprocess = reprocess
1958
merger.other_rev_id = other_rev_id
1959
merger.other_basis = other_rev_id
1960
get_revision_id = getattr(base_tree, 'get_revision_id', None)
1961
if get_revision_id is None:
1962
get_revision_id = base_tree.last_revision
1963
merger.cache_trees_with_revision_ids([other_tree, base_tree, this_tree])
1964
merger.set_base_revision(get_revision_id(), this_branch)
1965
return merger.do_merge()
1968
merge_type_registry = registry.Registry()
1969
merge_type_registry.register('diff3', Diff3Merger,
1970
"Merge using external diff3.")
1971
merge_type_registry.register('lca', LCAMerger,
1972
"LCA-newness merge.")
1973
merge_type_registry.register('merge3', Merge3Merger,
1974
"Native diff3-style merge.")
1975
merge_type_registry.register('weave', WeaveMerger,
1976
"Weave-based merge.")
1979
def get_merge_type_registry():
1980
"""Merge type registry was previously in breezy.option
1982
This method provides a backwards compatible way to retrieve it.
1984
return merge_type_registry
1987
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1988
def status_a(revision, text):
1989
if revision in ancestors_b:
1990
return 'killed-b', text
1992
return 'new-a', text
1994
def status_b(revision, text):
1995
if revision in ancestors_a:
1996
return 'killed-a', text
1998
return 'new-b', text
2000
plain_a = [t for (a, t) in annotated_a]
2001
plain_b = [t for (a, t) in annotated_b]
2002
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
2003
blocks = matcher.get_matching_blocks()
2006
for ai, bi, l in blocks:
2007
# process all mismatched sections
2008
# (last mismatched section is handled because blocks always
2009
# includes a 0-length last block)
2010
for revision, text in annotated_a[a_cur:ai]:
2011
yield status_a(revision, text)
2012
for revision, text in annotated_b[b_cur:bi]:
2013
yield status_b(revision, text)
2014
# and now the matched section
2017
for text_a in plain_a[ai:a_cur]:
2018
yield "unchanged", text_a
2021
class _PlanMergeBase(object):
2023
def __init__(self, a_rev, b_rev, vf, key_prefix):
2026
:param a_rev: Revision-id of one revision to merge
2027
:param b_rev: Revision-id of the other revision to merge
2028
:param vf: A VersionedFiles containing both revisions
2029
:param key_prefix: A prefix for accessing keys in vf, typically
2035
self._last_lines = None
2036
self._last_lines_revision_id = None
2037
self._cached_matching_blocks = {}
2038
self._key_prefix = key_prefix
2039
self._precache_tip_lines()
2041
def _precache_tip_lines(self):
2042
lines = self.get_lines([self.a_rev, self.b_rev])
2043
self.lines_a = lines[self.a_rev]
2044
self.lines_b = lines[self.b_rev]
2046
def get_lines(self, revisions):
2047
"""Get lines for revisions from the backing VersionedFiles.
2049
:raises RevisionNotPresent: on absent texts.
2051
keys = [(self._key_prefix + (rev,)) for rev in revisions]
2053
for record in self.vf.get_record_stream(keys, 'unordered', True):
2054
if record.storage_kind == 'absent':
2055
raise errors.RevisionNotPresent(record.key, self.vf)
2056
result[record.key[-1]] = osutils.chunks_to_lines(
2057
record.get_bytes_as('chunked'))
2060
def plan_merge(self):
2061
"""Generate a 'plan' for merging the two revisions.
2063
This involves comparing their texts and determining the cause of
2064
differences. If text A has a line and text B does not, then either the
2065
line was added to text A, or it was deleted from B. Once the causes
2066
are combined, they are written out in the format described in
2067
VersionedFile.plan_merge
2069
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
2070
unique_a, unique_b = self._unique_lines(blocks)
2071
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
2072
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
2073
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
2075
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
2078
for i, j, n in blocks:
2079
for a_index in range(last_i, i):
2080
if a_index in new_a:
2081
if a_index in killed_b:
2082
yield 'conflicted-a', self.lines_a[a_index]
2084
yield 'new-a', self.lines_a[a_index]
2086
yield 'killed-b', self.lines_a[a_index]
2087
for b_index in range(last_j, j):
2088
if b_index in new_b:
2089
if b_index in killed_a:
2090
yield 'conflicted-b', self.lines_b[b_index]
2092
yield 'new-b', self.lines_b[b_index]
2094
yield 'killed-a', self.lines_b[b_index]
2095
# handle common lines
2096
for a_index in range(i, i+n):
2097
yield 'unchanged', self.lines_a[a_index]
2101
def _get_matching_blocks(self, left_revision, right_revision):
2102
"""Return a description of which sections of two revisions match.
2104
See SequenceMatcher.get_matching_blocks
2106
cached = self._cached_matching_blocks.get((left_revision,
2108
if cached is not None:
2110
if self._last_lines_revision_id == left_revision:
2111
left_lines = self._last_lines
2112
right_lines = self.get_lines([right_revision])[right_revision]
2114
lines = self.get_lines([left_revision, right_revision])
2115
left_lines = lines[left_revision]
2116
right_lines = lines[right_revision]
2117
self._last_lines = right_lines
2118
self._last_lines_revision_id = right_revision
2119
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
2121
return matcher.get_matching_blocks()
2123
def _unique_lines(self, matching_blocks):
2124
"""Analyse matching_blocks to determine which lines are unique
2126
:return: a tuple of (unique_left, unique_right), where the values are
2127
sets of line numbers of unique lines.
2133
for i, j, n in matching_blocks:
2134
unique_left.extend(range(last_i, i))
2135
unique_right.extend(range(last_j, j))
2138
return unique_left, unique_right
2141
def _subtract_plans(old_plan, new_plan):
2142
"""Remove changes from new_plan that came from old_plan.
2144
It is assumed that the difference between the old_plan and new_plan
2145
is their choice of 'b' text.
2147
All lines from new_plan that differ from old_plan are emitted
2148
verbatim. All lines from new_plan that match old_plan but are
2149
not about the 'b' revision are emitted verbatim.
2151
Lines that match and are about the 'b' revision are the lines we
2152
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
2153
is skipped entirely.
2155
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
2158
for i, j, n in matcher.get_matching_blocks():
2159
for jj in range(last_j, j):
2161
for jj in range(j, j+n):
2162
plan_line = new_plan[jj]
2163
if plan_line[0] == 'new-b':
2165
elif plan_line[0] == 'killed-b':
2166
yield 'unchanged', plan_line[1]
2172
class _PlanMerge(_PlanMergeBase):
2173
"""Plan an annotate merge using on-the-fly annotation"""
2175
def __init__(self, a_rev, b_rev, vf, key_prefix):
2176
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
2177
self.a_key = self._key_prefix + (self.a_rev,)
2178
self.b_key = self._key_prefix + (self.b_rev,)
2179
self.graph = _mod_graph.Graph(self.vf)
2180
heads = self.graph.heads((self.a_key, self.b_key))
2182
# one side dominates, so we can just return its values, yay for
2184
# Ideally we would know that before we get this far
2185
self._head_key = heads.pop()
2186
if self._head_key == self.a_key:
2190
trace.mutter('found dominating revision for %s\n%s > %s', self.vf,
2191
self._head_key[-1], other)
2194
self._head_key = None
2197
def _precache_tip_lines(self):
2198
# Turn this into a no-op, because we will do this later
2201
def _find_recursive_lcas(self):
2202
"""Find all the ancestors back to a unique lca"""
2203
cur_ancestors = (self.a_key, self.b_key)
2204
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
2205
# rather than a key tuple. We will just map that directly to no common
2209
next_lcas = self.graph.find_lca(*cur_ancestors)
2210
# Map a plain NULL_REVISION to a simple no-ancestors
2211
if next_lcas == {_mod_revision.NULL_REVISION}:
2213
# Order the lca's based on when they were merged into the tip
2214
# While the actual merge portion of weave merge uses a set() of
2215
# active revisions, the order of insertion *does* effect the
2216
# implicit ordering of the texts.
2217
for rev_key in cur_ancestors:
2218
ordered_parents = tuple(self.graph.find_merge_order(rev_key,
2220
parent_map[rev_key] = ordered_parents
2221
if len(next_lcas) == 0:
2223
elif len(next_lcas) == 1:
2224
parent_map[list(next_lcas)[0]] = ()
2226
elif len(next_lcas) > 2:
2227
# More than 2 lca's, fall back to grabbing all nodes between
2228
# this and the unique lca.
2229
trace.mutter('More than 2 LCAs, falling back to all nodes for:'
2231
self.a_key, self.b_key, cur_ancestors)
2232
cur_lcas = next_lcas
2233
while len(cur_lcas) > 1:
2234
cur_lcas = self.graph.find_lca(*cur_lcas)
2235
if len(cur_lcas) == 0:
2236
# No common base to find, use the full ancestry
2239
unique_lca = list(cur_lcas)[0]
2240
if unique_lca == _mod_revision.NULL_REVISION:
2241
# find_lca will return a plain 'NULL_REVISION' rather
2242
# than a key tuple when there is no common ancestor, we
2243
# prefer to just use None, because it doesn't confuse
2244
# _get_interesting_texts()
2246
parent_map.update(self._find_unique_parents(next_lcas,
2249
cur_ancestors = next_lcas
2252
def _find_unique_parents(self, tip_keys, base_key):
2253
"""Find ancestors of tip that aren't ancestors of base.
2255
:param tip_keys: Nodes that are interesting
2256
:param base_key: Cull all ancestors of this node
2257
:return: The parent map for all revisions between tip_keys and
2258
base_key. base_key will be included. References to nodes outside of
2259
the ancestor set will also be removed.
2261
# TODO: this would be simpler if find_unique_ancestors took a list
2262
# instead of a single tip, internally it supports it, but it
2263
# isn't a "backwards compatible" api change.
2264
if base_key is None:
2265
parent_map = dict(self.graph.iter_ancestry(tip_keys))
2266
# We remove NULL_REVISION because it isn't a proper tuple key, and
2267
# thus confuses things like _get_interesting_texts, and our logic
2268
# to add the texts into the memory weave.
2269
if _mod_revision.NULL_REVISION in parent_map:
2270
parent_map.pop(_mod_revision.NULL_REVISION)
2273
for tip in tip_keys:
2275
self.graph.find_unique_ancestors(tip, [base_key]))
2276
parent_map = self.graph.get_parent_map(interesting)
2277
parent_map[base_key] = ()
2278
culled_parent_map, child_map, tails = self._remove_external_references(
2280
# Remove all the tails but base_key
2281
if base_key is not None:
2282
tails.remove(base_key)
2283
self._prune_tails(culled_parent_map, child_map, tails)
2284
# Now remove all the uninteresting 'linear' regions
2285
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
2289
def _remove_external_references(parent_map):
2290
"""Remove references that go outside of the parent map.
2292
:param parent_map: Something returned from Graph.get_parent_map(keys)
2293
:return: (filtered_parent_map, child_map, tails)
2294
filtered_parent_map is parent_map without external references
2295
child_map is the {parent_key: [child_keys]} mapping
2296
tails is a list of nodes that do not have any parents in the map
2298
# TODO: The basic effect of this function seems more generic than
2299
# _PlanMerge. But the specific details of building a child_map,
2300
# and computing tails seems very specific to _PlanMerge.
2301
# Still, should this be in Graph land?
2302
filtered_parent_map = {}
2305
for key, parent_keys in viewitems(parent_map):
2306
culled_parent_keys = [p for p in parent_keys if p in parent_map]
2307
if not culled_parent_keys:
2309
for parent_key in culled_parent_keys:
2310
child_map.setdefault(parent_key, []).append(key)
2311
# TODO: Do we want to do this, it adds overhead for every node,
2312
# just to say that the node has no children
2313
child_map.setdefault(key, [])
2314
filtered_parent_map[key] = culled_parent_keys
2315
return filtered_parent_map, child_map, tails
2318
def _prune_tails(parent_map, child_map, tails_to_remove):
2319
"""Remove tails from the parent map.
2321
This will remove the supplied revisions until no more children have 0
2324
:param parent_map: A dict of {child: [parents]}, this dictionary will
2325
be modified in place.
2326
:param tails_to_remove: A list of tips that should be removed,
2327
this list will be consumed
2328
:param child_map: The reverse dict of parent_map ({parent: [children]})
2329
this dict will be modified
2330
:return: None, parent_map will be modified in place.
2332
while tails_to_remove:
2333
next = tails_to_remove.pop()
2334
parent_map.pop(next)
2335
children = child_map.pop(next)
2336
for child in children:
2337
child_parents = parent_map[child]
2338
child_parents.remove(next)
2339
if len(child_parents) == 0:
2340
tails_to_remove.append(child)
2342
def _get_interesting_texts(self, parent_map):
2343
"""Return a dict of texts we are interested in.
2345
Note that the input is in key tuples, but the output is in plain
2348
:param parent_map: The output from _find_recursive_lcas
2349
:return: A dict of {'revision_id':lines} as returned by
2350
_PlanMergeBase.get_lines()
2352
all_revision_keys = set(parent_map)
2353
all_revision_keys.add(self.a_key)
2354
all_revision_keys.add(self.b_key)
2356
# Everything else is in 'keys' but get_lines is in 'revision_ids'
2357
all_texts = self.get_lines([k[-1] for k in all_revision_keys])
2360
def _build_weave(self):
2361
from .bzr import weave
2362
self._weave = weave.Weave(weave_name='in_memory_weave',
2363
allow_reserved=True)
2364
parent_map = self._find_recursive_lcas()
2366
all_texts = self._get_interesting_texts(parent_map)
2368
# Note: Unfortunately, the order given by topo_sort will effect the
2369
# ordering resolution in the output. Specifically, if you add A then B,
2370
# then in the output text A lines will show up before B lines. And, of
2371
# course, topo_sort doesn't guarantee any real ordering.
2372
# So we use merge_sort, and add a fake node on the tip.
2373
# This ensures that left-hand parents will always be inserted into the
2374
# weave before right-hand parents.
2375
tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
2376
parent_map[tip_key] = (self.a_key, self.b_key)
2378
for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
2382
# for key in tsort.topo_sort(parent_map):
2383
parent_keys = parent_map[key]
2384
revision_id = key[-1]
2385
parent_ids = [k[-1] for k in parent_keys]
2386
self._weave.add_lines(revision_id, parent_ids,
2387
all_texts[revision_id])
2389
def plan_merge(self):
2390
"""Generate a 'plan' for merging the two revisions.
2392
This involves comparing their texts and determining the cause of
2393
differences. If text A has a line and text B does not, then either the
2394
line was added to text A, or it was deleted from B. Once the causes
2395
are combined, they are written out in the format described in
2396
VersionedFile.plan_merge
2398
if self._head_key is not None: # There was a single head
2399
if self._head_key == self.a_key:
2402
if self._head_key != self.b_key:
2403
raise AssertionError('There was an invalid head: %s != %s'
2404
% (self.b_key, self._head_key))
2406
head_rev = self._head_key[-1]
2407
lines = self.get_lines([head_rev])[head_rev]
2408
return ((plan, line) for line in lines)
2409
return self._weave.plan_merge(self.a_rev, self.b_rev)
2412
class _PlanLCAMerge(_PlanMergeBase):
2414
This merge algorithm differs from _PlanMerge in that:
2416
1. comparisons are done against LCAs only
2417
2. cases where a contested line is new versus one LCA but old versus
2418
another are marked as conflicts, by emitting the line as conflicted-a
2421
This is faster, and hopefully produces more useful output.
2424
def __init__(self, a_rev, b_rev, vf, key_prefix, graph):
2425
_PlanMergeBase.__init__(self, a_rev, b_rev, vf, key_prefix)
2426
lcas = graph.find_lca(key_prefix + (a_rev,), key_prefix + (b_rev,))
2429
if lca == _mod_revision.NULL_REVISION:
2432
self.lcas.add(lca[-1])
2433
for lca in self.lcas:
2434
if _mod_revision.is_null(lca):
2437
lca_lines = self.get_lines([lca])[lca]
2438
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
2440
blocks = list(matcher.get_matching_blocks())
2441
self._cached_matching_blocks[(a_rev, lca)] = blocks
2442
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
2444
blocks = list(matcher.get_matching_blocks())
2445
self._cached_matching_blocks[(b_rev, lca)] = blocks
2447
def _determine_status(self, revision_id, unique_line_numbers):
2448
"""Determines the status unique lines versus all lcas.
2450
Basically, determines why the line is unique to this revision.
2452
A line may be determined new, killed, or both.
2454
If a line is determined new, that means it was not present in at least
2455
one LCA, and is not present in the other merge revision.
2457
If a line is determined killed, that means the line was present in
2460
If a line is killed and new, this indicates that the two merge
2461
revisions contain differing conflict resolutions.
2463
:param revision_id: The id of the revision in which the lines are
2465
:param unique_line_numbers: The line numbers of unique lines.
2466
:return: a tuple of (new_this, killed_other)
2470
unique_line_numbers = set(unique_line_numbers)
2471
for lca in self.lcas:
2472
blocks = self._get_matching_blocks(revision_id, lca)
2473
unique_vs_lca, _ignored = self._unique_lines(blocks)
2474
new.update(unique_line_numbers.intersection(unique_vs_lca))
2475
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
breezy/merge.py
