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 bzrlib.lazy_import import lazy_import
22
lazy_import(globals(), """
24
branch as _mod_branch,
26
conflicts as _mod_conflicts,
33
revision as _mod_revision,
43
from bzrlib.i18n import gettext
51
from bzrlib.symbol_versioning import (
55
# TODO: Report back as changes are merged in
58
def transform_tree(from_tree, to_tree, interesting_ids=None):
59
from_tree.lock_tree_write()
60
operation = cleanup.OperationWithCleanups(merge_inner)
61
operation.add_cleanup(from_tree.unlock)
62
operation.run_simple(from_tree.branch, to_tree, from_tree,
63
ignore_zero=True, interesting_ids=interesting_ids, this_tree=from_tree)
66
class MergeHooks(hooks.Hooks):
69
hooks.Hooks.__init__(self, "bzrlib.merge", "Merger.hooks")
70
self.add_hook('merge_file_content',
71
"Called with a bzrlib.merge.Merger object to create a per file "
72
"merge object when starting a merge. "
73
"Should return either None or a subclass of "
74
"``bzrlib.merge.AbstractPerFileMerger``. "
75
"Such objects will then be called per file "
76
"that needs to be merged (including when one "
77
"side has deleted the file and the other has changed it). "
78
"See the AbstractPerFileMerger API docs for details on how it is "
83
class AbstractPerFileMerger(object):
84
"""PerFileMerger objects are used by plugins extending merge for bzrlib.
86
See ``bzrlib.plugins.news_merge.news_merge`` for an example concrete class.
88
:ivar merger: The Merge3Merger performing the merge.
91
def __init__(self, merger):
92
"""Create a PerFileMerger for use with merger."""
95
def merge_contents(self, merge_params):
96
"""Attempt to merge the contents of a single file.
98
:param merge_params: A bzrlib.merge.MergeHookParams
99
:return: A tuple of (status, chunks), where status is one of
100
'not_applicable', 'success', 'conflicted', or 'delete'. If status
101
is 'success' or 'conflicted', then chunks should be an iterable of
102
strings for the new file contents.
104
return ('not applicable', None)
107
class PerFileMerger(AbstractPerFileMerger):
108
"""Merge individual files when self.file_matches returns True.
110
This class is intended to be subclassed. The file_matches and
111
merge_matching methods should be overridden with concrete implementations.
114
def file_matches(self, params):
115
"""Return True if merge_matching should be called on this file.
117
Only called with merges of plain files with no clear winner.
119
Subclasses must override this.
121
raise NotImplementedError(self.file_matches)
123
def get_filename(self, params, tree):
124
"""Lookup the filename (i.e. basename, not path), given a Tree (e.g.
125
self.merger.this_tree) and a MergeHookParams.
127
return osutils.basename(tree.id2path(params.file_id))
129
def get_filepath(self, params, tree):
130
"""Calculate the path to the file in a tree.
132
:param params: A MergeHookParams describing the file to merge
133
:param tree: a Tree, e.g. self.merger.this_tree.
135
return tree.id2path(params.file_id)
137
def merge_contents(self, params):
138
"""Merge the contents of a single file."""
139
# Check whether this custom merge logic should be used.
141
# OTHER is a straight winner, rely on default merge.
142
params.winner == 'other' or
143
# THIS and OTHER aren't both files.
144
not params.is_file_merge() or
145
# The filename doesn't match
146
not self.file_matches(params)):
147
return 'not_applicable', None
148
return self.merge_matching(params)
150
def merge_matching(self, params):
151
"""Merge the contents of a single file that has matched the criteria
152
in PerFileMerger.merge_contents (is a conflict, is a file,
153
self.file_matches is True).
155
Subclasses must override this.
157
raise NotImplementedError(self.merge_matching)
160
class ConfigurableFileMerger(PerFileMerger):
161
"""Merge individual files when configured via a .conf file.
163
This is a base class for concrete custom file merging logic. Concrete
164
classes should implement ``merge_text``.
166
See ``bzrlib.plugins.news_merge.news_merge`` for an example concrete class.
168
:ivar affected_files: The configured file paths to merge.
170
:cvar name_prefix: The prefix to use when looking up configuration
171
details. <name_prefix>_merge_files describes the files targeted by the
174
:cvar default_files: The default file paths to merge when no configuration
181
def __init__(self, merger):
182
super(ConfigurableFileMerger, self).__init__(merger)
183
self.affected_files = None
184
self.default_files = self.__class__.default_files or []
185
self.name_prefix = self.__class__.name_prefix
186
if self.name_prefix is None:
187
raise ValueError("name_prefix must be set.")
189
def file_matches(self, params):
190
"""Check whether the file should call the merge hook.
192
<name_prefix>_merge_files configuration variable is a list of files
193
that should use the hook.
195
affected_files = self.affected_files
196
if affected_files is None:
197
config = self.merger.this_branch.get_config()
198
# Until bzr provides a better policy for caching the config, we
199
# just add the part we're interested in to the params to avoid
200
# reading the config files repeatedly (bazaar.conf, location.conf,
202
config_key = self.name_prefix + '_merge_files'
203
affected_files = config.get_user_option_as_list(config_key)
204
if affected_files is None:
205
# If nothing was specified in the config, use the default.
206
affected_files = self.default_files
207
self.affected_files = affected_files
209
filepath = self.get_filepath(params, self.merger.this_tree)
210
if filepath in affected_files:
214
def merge_matching(self, params):
215
return self.merge_text(params)
217
def merge_text(self, params):
218
"""Merge the byte contents of a single file.
220
This is called after checking that the merge should be performed in
221
merge_contents, and it should behave as per
222
``bzrlib.merge.AbstractPerFileMerger.merge_contents``.
224
raise NotImplementedError(self.merge_text)
227
class MergeHookParams(object):
228
"""Object holding parameters passed to merge_file_content hooks.
230
There are some fields hooks can access:
232
:ivar file_id: the file ID of the file being merged
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, trans_id, this_kind, other_kind,
241
self._merger = merger
242
self.file_id = file_id
243
self.trans_id = trans_id
244
self.this_kind = this_kind
245
self.other_kind = other_kind
248
def is_file_merge(self):
249
"""True if this_kind and other_kind are both 'file'."""
250
return self.this_kind == 'file' and self.other_kind == 'file'
252
@decorators.cachedproperty
253
def base_lines(self):
254
"""The lines of the 'base' version of the file."""
255
return self._merger.get_lines(self._merger.base_tree, self.file_id)
257
@decorators.cachedproperty
258
def this_lines(self):
259
"""The lines of the 'this' version of the file."""
260
return self._merger.get_lines(self._merger.this_tree, self.file_id)
262
@decorators.cachedproperty
263
def other_lines(self):
264
"""The lines of the 'other' version of the file."""
265
return self._merger.get_lines(self._merger.other_tree, self.file_id)
268
class Merger(object):
272
def __init__(self, this_branch, other_tree=None, base_tree=None,
273
this_tree=None, pb=None, change_reporter=None,
274
recurse='down', revision_graph=None):
275
object.__init__(self)
276
self.this_branch = this_branch
277
self.this_basis = _mod_revision.ensure_null(
278
this_branch.last_revision())
279
self.this_rev_id = None
280
self.this_tree = this_tree
281
self.this_revision_tree = None
282
self.this_basis_tree = None
283
self.other_tree = other_tree
284
self.other_branch = None
285
self.base_tree = base_tree
286
self.ignore_zero = False
287
self.backup_files = False
288
self.interesting_ids = None
289
self.interesting_files = None
290
self.show_base = False
291
self.reprocess = False
293
warnings.warn("pb parameter to Merger() is deprecated and ignored")
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, pb=None, 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 pb: A progress indicator
353
:param base_tree: The basis to use for the merge. If unspecified,
354
other_tree.basis_tree() will be used.
356
if base_tree is None:
357
base_tree = other_tree.basis_tree()
358
merger = Merger(tree.branch, other_tree, base_tree, tree, pb)
359
merger.base_rev_id = merger.base_tree.get_revision_id()
360
merger.other_rev_id = None
361
merger.other_basis = merger.base_rev_id
365
def from_mergeable(klass, tree, mergeable, pb):
366
"""Return a Merger for a bundle or merge directive.
368
:param tree: The tree to merge changes into
369
:param mergeable: A merge directive or bundle
370
:param pb: A progress indicator
372
mergeable.install_revisions(tree.branch.repository)
373
base_revision_id, other_revision_id, verified =\
374
mergeable.get_merge_request(tree.branch.repository)
375
revision_graph = tree.branch.repository.get_graph()
376
if base_revision_id is not None:
377
if (base_revision_id != _mod_revision.NULL_REVISION and
378
revision_graph.is_ancestor(
379
base_revision_id, tree.branch.last_revision())):
380
base_revision_id = None
382
trace.warning('Performing cherrypick')
383
merger = klass.from_revision_ids(pb, tree, other_revision_id,
384
base_revision_id, revision_graph=
386
return merger, verified
389
def from_revision_ids(pb, tree, other, base=None, other_branch=None,
390
base_branch=None, revision_graph=None,
392
"""Return a Merger for revision-ids.
394
:param pb: A progress indicator
395
:param tree: The tree to merge changes into
396
:param other: The revision-id to use as OTHER
397
:param base: The revision-id to use as BASE. If not specified, will
399
:param other_branch: A branch containing the other revision-id. If
400
not supplied, tree.branch is used.
401
:param base_branch: A branch containing the base revision-id. If
402
not supplied, other_branch or tree.branch will be used.
403
:param revision_graph: If you have a revision_graph precomputed, pass
404
it in, otherwise it will be created for you.
405
:param tree_branch: The branch associated with tree. If not supplied,
406
tree.branch will be used.
408
if tree_branch is None:
409
tree_branch = tree.branch
410
merger = Merger(tree_branch, this_tree=tree, pb=pb,
411
revision_graph=revision_graph)
412
if other_branch is None:
413
other_branch = tree.branch
414
merger.set_other_revision(other, other_branch)
418
if base_branch is None:
419
base_branch = other_branch
420
merger.set_base_revision(base, base_branch)
423
def revision_tree(self, revision_id, branch=None):
424
if revision_id not in self._cached_trees:
426
branch = self.this_branch
428
tree = self.this_tree.revision_tree(revision_id)
429
except errors.NoSuchRevisionInTree:
430
tree = branch.repository.revision_tree(revision_id)
431
self._cached_trees[revision_id] = tree
432
return self._cached_trees[revision_id]
434
def _get_tree(self, treespec, possible_transports=None):
435
location, revno = treespec
437
tree = workingtree.WorkingTree.open_containing(location)[0]
438
return tree.branch, tree
439
branch = _mod_branch.Branch.open_containing(
440
location, possible_transports)[0]
442
revision_id = branch.last_revision()
444
revision_id = branch.get_rev_id(revno)
445
revision_id = _mod_revision.ensure_null(revision_id)
446
return branch, self.revision_tree(revision_id, branch)
448
def set_interesting_files(self, file_list):
449
self.interesting_files = file_list
451
def set_pending(self):
452
if (not self.base_is_ancestor or not self.base_is_other_ancestor
453
or self.other_rev_id is None):
457
def _add_parent(self):
458
new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
459
new_parent_trees = []
460
operation = cleanup.OperationWithCleanups(
461
self.this_tree.set_parent_trees)
462
for revision_id in new_parents:
464
tree = self.revision_tree(revision_id)
465
except errors.NoSuchRevision:
469
operation.add_cleanup(tree.unlock)
470
new_parent_trees.append((revision_id, tree))
471
operation.run_simple(new_parent_trees, allow_leftmost_as_ghost=True)
473
def set_other(self, other_revision, possible_transports=None):
474
"""Set the revision and tree to merge from.
476
This sets the other_tree, other_rev_id, other_basis attributes.
478
:param other_revision: The [path, revision] list to merge from.
480
self.other_branch, self.other_tree = self._get_tree(other_revision,
482
if other_revision[1] == -1:
483
self.other_rev_id = _mod_revision.ensure_null(
484
self.other_branch.last_revision())
485
if _mod_revision.is_null(self.other_rev_id):
486
raise errors.NoCommits(self.other_branch)
487
self.other_basis = self.other_rev_id
488
elif other_revision[1] is not None:
489
self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
490
self.other_basis = self.other_rev_id
492
self.other_rev_id = None
493
self.other_basis = self.other_branch.last_revision()
494
if self.other_basis is None:
495
raise errors.NoCommits(self.other_branch)
496
if self.other_rev_id is not None:
497
self._cached_trees[self.other_rev_id] = self.other_tree
498
self._maybe_fetch(self.other_branch, self.this_branch, self.other_basis)
500
def set_other_revision(self, revision_id, other_branch):
501
"""Set 'other' based on a branch and revision id
503
:param revision_id: The revision to use for a tree
504
:param other_branch: The branch containing this tree
506
self.other_rev_id = revision_id
507
self.other_branch = other_branch
508
self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
509
self.other_tree = self.revision_tree(revision_id)
510
self.other_basis = revision_id
512
def set_base_revision(self, revision_id, branch):
513
"""Set 'base' based on a branch and revision id
515
:param revision_id: The revision to use for a tree
516
:param branch: The branch containing this tree
518
self.base_rev_id = revision_id
519
self.base_branch = branch
520
self._maybe_fetch(branch, self.this_branch, revision_id)
521
self.base_tree = self.revision_tree(revision_id)
523
def _maybe_fetch(self, source, target, revision_id):
524
if not source.repository.has_same_location(target.repository):
525
target.fetch(source, revision_id)
528
revisions = [_mod_revision.ensure_null(self.this_basis),
529
_mod_revision.ensure_null(self.other_basis)]
530
if _mod_revision.NULL_REVISION in revisions:
531
self.base_rev_id = _mod_revision.NULL_REVISION
532
self.base_tree = self.revision_tree(self.base_rev_id)
533
self._is_criss_cross = False
535
lcas = self.revision_graph.find_lca(revisions[0], revisions[1])
536
self._is_criss_cross = False
538
self.base_rev_id = _mod_revision.NULL_REVISION
540
self.base_rev_id = list(lcas)[0]
541
else: # len(lcas) > 1
542
self._is_criss_cross = True
544
# find_unique_lca can only handle 2 nodes, so we have to
545
# start back at the beginning. It is a shame to traverse
546
# the graph again, but better than re-implementing
548
self.base_rev_id = self.revision_graph.find_unique_lca(
549
revisions[0], revisions[1])
551
self.base_rev_id = self.revision_graph.find_unique_lca(
553
sorted_lca_keys = self.revision_graph.find_merge_order(
555
if self.base_rev_id == _mod_revision.NULL_REVISION:
556
self.base_rev_id = sorted_lca_keys[0]
558
if self.base_rev_id == _mod_revision.NULL_REVISION:
559
raise errors.UnrelatedBranches()
560
if self._is_criss_cross:
561
trace.warning('Warning: criss-cross merge encountered. See bzr'
562
' help criss-cross.')
563
trace.mutter('Criss-cross lcas: %r' % lcas)
564
if self.base_rev_id in lcas:
565
trace.mutter('Unable to find unique lca. '
566
'Fallback %r as best option.'
568
interesting_revision_ids = set(lcas)
569
interesting_revision_ids.add(self.base_rev_id)
570
interesting_trees = dict((t.get_revision_id(), t)
571
for t in self.this_branch.repository.revision_trees(
572
interesting_revision_ids))
573
self._cached_trees.update(interesting_trees)
574
if self.base_rev_id in lcas:
575
self.base_tree = interesting_trees[self.base_rev_id]
577
self.base_tree = interesting_trees.pop(self.base_rev_id)
578
self._lca_trees = [interesting_trees[key]
579
for key in sorted_lca_keys]
581
self.base_tree = self.revision_tree(self.base_rev_id)
582
self.base_is_ancestor = True
583
self.base_is_other_ancestor = True
584
trace.mutter('Base revid: %r' % self.base_rev_id)
586
def set_base(self, base_revision):
587
"""Set the base revision to use for the merge.
589
:param base_revision: A 2-list containing a path and revision number.
591
trace.mutter("doing merge() with no base_revision specified")
592
if base_revision == [None, None]:
595
base_branch, self.base_tree = self._get_tree(base_revision)
596
if base_revision[1] == -1:
597
self.base_rev_id = base_branch.last_revision()
598
elif base_revision[1] is None:
599
self.base_rev_id = _mod_revision.NULL_REVISION
601
self.base_rev_id = _mod_revision.ensure_null(
602
base_branch.get_rev_id(base_revision[1]))
603
self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
605
def make_merger(self):
606
kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
607
'other_tree': self.other_tree,
608
'interesting_ids': self.interesting_ids,
609
'interesting_files': self.interesting_files,
610
'this_branch': self.this_branch,
612
if self.merge_type.requires_base:
613
kwargs['base_tree'] = self.base_tree
614
if self.merge_type.supports_reprocess:
615
kwargs['reprocess'] = self.reprocess
617
raise errors.BzrError(
618
"Conflict reduction is not supported for merge"
619
" type %s." % self.merge_type)
620
if self.merge_type.supports_show_base:
621
kwargs['show_base'] = self.show_base
623
raise errors.BzrError("Showing base is not supported for this"
624
" merge type. %s" % self.merge_type)
625
if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
626
and not self.base_is_other_ancestor):
627
raise errors.CannotReverseCherrypick()
628
if self.merge_type.supports_cherrypick:
629
kwargs['cherrypick'] = (not self.base_is_ancestor or
630
not self.base_is_other_ancestor)
631
if self._is_criss_cross and getattr(self.merge_type,
632
'supports_lca_trees', False):
633
kwargs['lca_trees'] = self._lca_trees
634
return self.merge_type(pb=None,
635
change_reporter=self.change_reporter,
638
def _do_merge_to(self):
639
merge = self.make_merger()
640
if self.other_branch is not None:
641
self.other_branch.update_references(self.this_branch)
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(file_id, relpath)
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(file_id,
654
sub_merge.set_other_revision(other_revision, other_branch)
655
base_revision = self.base_tree.get_reference_revision(file_id)
656
sub_merge.base_tree = \
657
sub_tree.branch.repository.revision_tree(base_revision)
658
sub_merge.base_rev_id = base_revision
663
operation = cleanup.OperationWithCleanups(self._do_merge_to)
664
self.this_tree.lock_tree_write()
665
operation.add_cleanup(self.this_tree.unlock)
666
if self.base_tree is not None:
667
self.base_tree.lock_read()
668
operation.add_cleanup(self.base_tree.unlock)
669
if self.other_tree is not None:
670
self.other_tree.lock_read()
671
operation.add_cleanup(self.other_tree.unlock)
672
merge = operation.run_simple()
673
if len(merge.cooked_conflicts) == 0:
674
if not self.ignore_zero and not trace.is_quiet():
675
trace.note(gettext("All changes applied successfully."))
677
trace.note(gettext("%d conflicts encountered.")
678
% len(merge.cooked_conflicts))
680
return len(merge.cooked_conflicts)
683
class _InventoryNoneEntry(object):
684
"""This represents an inventory entry which *isn't there*.
686
It simplifies the merging logic if we always have an InventoryEntry, even
687
if it isn't actually present
694
symlink_target = None
697
_none_entry = _InventoryNoneEntry()
700
class Merge3Merger(object):
701
"""Three-way merger that uses the merge3 text merger"""
703
supports_reprocess = True
704
supports_show_base = True
705
history_based = False
706
supports_cherrypick = True
707
supports_reverse_cherrypick = True
708
winner_idx = {"this": 2, "other": 1, "conflict": 1}
709
supports_lca_trees = True
711
def __init__(self, working_tree, this_tree, base_tree, other_tree,
712
interesting_ids=None, reprocess=False, show_base=False,
713
pb=None, pp=None, change_reporter=None,
714
interesting_files=None, do_merge=True,
715
cherrypick=False, lca_trees=None, this_branch=None):
716
"""Initialize the merger object and perform the merge.
718
:param working_tree: The working tree to apply the merge to
719
:param this_tree: The local tree in the merge operation
720
:param base_tree: The common tree in the merge operation
721
:param other_tree: The other tree to merge changes from
722
:param this_branch: The branch associated with this_tree. Defaults to
723
this_tree.branch if not supplied.
724
:param interesting_ids: The file_ids of files that should be
725
participate in the merge. May not be combined with
727
:param: reprocess If True, perform conflict-reduction processing.
728
:param show_base: If True, show the base revision in text conflicts.
729
(incompatible with reprocess)
731
:param pp: A ProgressPhase object
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. May not
736
be combined with interesting_ids. If neither interesting_files nor
737
interesting_ids is specified, all files may participate in the
739
:param lca_trees: Can be set to a dictionary of {revision_id:rev_tree}
740
if the ancestry was found to include a criss-cross merge.
741
Otherwise should be None.
743
object.__init__(self)
744
if interesting_files is not None and interesting_ids is not None:
746
'specify either interesting_ids or interesting_files')
747
if this_branch is None:
748
this_branch = this_tree.branch
749
self.interesting_ids = interesting_ids
750
self.interesting_files = interesting_files
751
self.this_tree = working_tree
752
self.base_tree = base_tree
753
self.other_tree = other_tree
754
self.this_branch = this_branch
755
self._raw_conflicts = []
756
self.cooked_conflicts = []
757
self.reprocess = reprocess
758
self.show_base = show_base
759
self._lca_trees = lca_trees
760
# Uncommenting this will change the default algorithm to always use
761
# _entries_lca. This can be useful for running the test suite and
762
# making sure we haven't missed any corner cases.
763
# if lca_trees is None:
764
# self._lca_trees = [self.base_tree]
765
self.change_reporter = change_reporter
766
self.cherrypick = cherrypick
770
warnings.warn("pp argument to Merge3Merger is deprecated")
772
warnings.warn("pb argument to Merge3Merger is deprecated")
775
operation = cleanup.OperationWithCleanups(self._do_merge)
776
self.this_tree.lock_tree_write()
777
operation.add_cleanup(self.this_tree.unlock)
778
self.base_tree.lock_read()
779
operation.add_cleanup(self.base_tree.unlock)
780
self.other_tree.lock_read()
781
operation.add_cleanup(self.other_tree.unlock)
784
def _do_merge(self, operation):
785
self.tt = transform.TreeTransform(self.this_tree, None)
786
operation.add_cleanup(self.tt.finalize)
787
self._compute_transform()
788
results = self.tt.apply(no_conflicts=True)
789
self.write_modified(results)
791
self.this_tree.add_conflicts(self.cooked_conflicts)
792
except errors.UnsupportedOperation:
795
def make_preview_transform(self):
796
operation = cleanup.OperationWithCleanups(self._make_preview_transform)
797
self.base_tree.lock_read()
798
operation.add_cleanup(self.base_tree.unlock)
799
self.other_tree.lock_read()
800
operation.add_cleanup(self.other_tree.unlock)
801
return operation.run_simple()
803
def _make_preview_transform(self):
804
self.tt = transform.TransformPreview(self.this_tree)
805
self._compute_transform()
808
def _compute_transform(self):
809
if self._lca_trees is None:
810
entries = self._entries3()
811
resolver = self._three_way
813
entries = self._entries_lca()
814
resolver = self._lca_multi_way
815
# Prepare merge hooks
816
factories = Merger.hooks['merge_file_content']
817
# One hook for each registered one plus our default merger
818
hooks = [factory(self) for factory in factories] + [self]
819
self.active_hooks = [hook for hook in hooks if hook is not None]
820
child_pb = ui.ui_factory.nested_progress_bar()
822
for num, (file_id, changed, parents3, names3,
823
executable3) in enumerate(entries):
824
# Try merging each entry
825
child_pb.update(gettext('Preparing file merge'),
827
self._merge_names(file_id, parents3, names3, resolver=resolver)
829
file_status = self._do_merge_contents(file_id)
831
file_status = 'unmodified'
832
self._merge_executable(file_id,
833
executable3, file_status, resolver=resolver)
836
self.tt.fixup_new_roots()
837
self._finish_computing_transform()
839
def _finish_computing_transform(self):
840
"""Finalize the transform and report the changes.
842
This is the second half of _compute_transform.
844
child_pb = ui.ui_factory.nested_progress_bar()
846
fs_conflicts = transform.resolve_conflicts(self.tt, child_pb,
847
lambda t, c: transform.conflict_pass(t, c, self.other_tree))
850
if self.change_reporter is not None:
851
from bzrlib import delta
852
delta.report_changes(
853
self.tt.iter_changes(), self.change_reporter)
854
self.cook_conflicts(fs_conflicts)
855
for conflict in self.cooked_conflicts:
856
trace.warning(unicode(conflict))
859
"""Gather data about files modified between three trees.
861
Return a list of tuples of file_id, changed, parents3, names3,
862
executable3. changed is a boolean indicating whether the file contents
863
or kind were changed. parents3 is a tuple of parent ids for base,
864
other and this. names3 is a tuple of names for base, other and this.
865
executable3 is a tuple of execute-bit values for base, other and this.
868
iterator = self.other_tree.iter_changes(self.base_tree,
869
specific_files=self.interesting_files,
870
extra_trees=[self.this_tree])
871
this_entries = dict((e.file_id, e) for p, e in
872
self.this_tree.iter_entries_by_dir(
873
self.interesting_ids))
874
for (file_id, paths, changed, versioned, parents, names, kind,
875
executable) in iterator:
876
if (self.interesting_ids is not None and
877
file_id not in self.interesting_ids):
879
entry = this_entries.get(file_id)
880
if entry is not None:
881
this_name = entry.name
882
this_parent = entry.parent_id
883
this_executable = entry.executable
887
this_executable = None
888
parents3 = parents + (this_parent,)
889
names3 = names + (this_name,)
890
executable3 = executable + (this_executable,)
891
result.append((file_id, changed, parents3, names3, executable3))
894
def _entries_lca(self):
895
"""Gather data about files modified between multiple trees.
897
This compares OTHER versus all LCA trees, and for interesting entries,
898
it then compares with THIS and BASE.
900
For the multi-valued entries, the format will be (BASE, [lca1, lca2])
902
:return: [(file_id, changed, parents, names, executable)], where:
904
* file_id: Simple file_id of the entry
905
* changed: Boolean, True if the kind or contents changed else False
906
* parents: ((base, [parent_id, in, lcas]), parent_id_other,
908
* names: ((base, [name, in, lcas]), name_in_other, name_in_this)
909
* executable: ((base, [exec, in, lcas]), exec_in_other,
912
if self.interesting_files is not None:
913
lookup_trees = [self.this_tree, self.base_tree]
914
lookup_trees.extend(self._lca_trees)
915
# I think we should include the lca trees as well
916
interesting_ids = self.other_tree.paths2ids(self.interesting_files,
919
interesting_ids = self.interesting_ids
921
walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
923
base_inventory = self.base_tree.inventory
924
this_inventory = self.this_tree.inventory
925
for path, file_id, other_ie, lca_values in walker.iter_all():
926
# Is this modified at all from any of the other trees?
928
other_ie = _none_entry
929
if interesting_ids is not None and file_id not in interesting_ids:
932
# If other_revision is found in any of the lcas, that means this
933
# node is uninteresting. This is because when merging, if there are
934
# multiple heads(), we have to create a new node. So if we didn't,
935
# we know that the ancestry is linear, and that OTHER did not
937
# See doc/developers/lca_merge_resolution.txt for details
938
other_revision = other_ie.revision
939
if other_revision is not None:
940
# We can't use this shortcut when other_revision is None,
941
# because it may be None because things are WorkingTrees, and
942
# not because it is *actually* None.
943
is_unmodified = False
944
for lca_path, ie in lca_values:
945
if ie is not None and ie.revision == other_revision:
952
for lca_path, lca_ie in lca_values:
954
lca_entries.append(_none_entry)
956
lca_entries.append(lca_ie)
958
if base_inventory.has_id(file_id):
959
base_ie = base_inventory[file_id]
961
base_ie = _none_entry
963
if this_inventory.has_id(file_id):
964
this_ie = this_inventory[file_id]
966
this_ie = _none_entry
972
for lca_ie in lca_entries:
973
lca_kinds.append(lca_ie.kind)
974
lca_parent_ids.append(lca_ie.parent_id)
975
lca_names.append(lca_ie.name)
976
lca_executable.append(lca_ie.executable)
978
kind_winner = self._lca_multi_way(
979
(base_ie.kind, lca_kinds),
980
other_ie.kind, this_ie.kind)
981
parent_id_winner = self._lca_multi_way(
982
(base_ie.parent_id, lca_parent_ids),
983
other_ie.parent_id, this_ie.parent_id)
984
name_winner = self._lca_multi_way(
985
(base_ie.name, lca_names),
986
other_ie.name, this_ie.name)
988
content_changed = True
989
if kind_winner == 'this':
990
# No kind change in OTHER, see if there are *any* changes
991
if other_ie.kind == 'directory':
992
if parent_id_winner == 'this' and name_winner == 'this':
993
# No change for this directory in OTHER, skip
995
content_changed = False
996
elif other_ie.kind is None or other_ie.kind == 'file':
997
def get_sha1(ie, tree):
998
if ie.kind != 'file':
1000
return tree.get_file_sha1(file_id)
1001
base_sha1 = get_sha1(base_ie, self.base_tree)
1002
lca_sha1s = [get_sha1(ie, tree) for ie, tree
1003
in zip(lca_entries, self._lca_trees)]
1004
this_sha1 = get_sha1(this_ie, self.this_tree)
1005
other_sha1 = get_sha1(other_ie, self.other_tree)
1006
sha1_winner = self._lca_multi_way(
1007
(base_sha1, lca_sha1s), other_sha1, this_sha1,
1008
allow_overriding_lca=False)
1009
exec_winner = self._lca_multi_way(
1010
(base_ie.executable, lca_executable),
1011
other_ie.executable, this_ie.executable)
1012
if (parent_id_winner == 'this' and name_winner == 'this'
1013
and sha1_winner == 'this' and exec_winner == 'this'):
1014
# No kind, parent, name, exec, or content change for
1015
# OTHER, so this node is not considered interesting
1017
if sha1_winner == 'this':
1018
content_changed = False
1019
elif other_ie.kind == 'symlink':
1020
def get_target(ie, tree):
1021
if ie.kind != 'symlink':
1023
return tree.get_symlink_target(file_id)
1024
base_target = get_target(base_ie, self.base_tree)
1025
lca_targets = [get_target(ie, tree) for ie, tree
1026
in zip(lca_entries, self._lca_trees)]
1027
this_target = get_target(this_ie, self.this_tree)
1028
other_target = get_target(other_ie, self.other_tree)
1029
target_winner = self._lca_multi_way(
1030
(base_target, lca_targets),
1031
other_target, this_target)
1032
if (parent_id_winner == 'this' and name_winner == 'this'
1033
and target_winner == 'this'):
1034
# No kind, parent, name, or symlink target change
1037
if target_winner == 'this':
1038
content_changed = False
1039
elif other_ie.kind == 'tree-reference':
1040
# The 'changed' information seems to be handled at a higher
1041
# level. At least, _entries3 returns False for content
1042
# changed, even when at a new revision_id.
1043
content_changed = False
1044
if (parent_id_winner == 'this' and name_winner == 'this'):
1045
# Nothing interesting
1048
raise AssertionError('unhandled kind: %s' % other_ie.kind)
1050
# If we have gotten this far, that means something has changed
1051
result.append((file_id, content_changed,
1052
((base_ie.parent_id, lca_parent_ids),
1053
other_ie.parent_id, this_ie.parent_id),
1054
((base_ie.name, lca_names),
1055
other_ie.name, this_ie.name),
1056
((base_ie.executable, lca_executable),
1057
other_ie.executable, this_ie.executable)
1061
@deprecated_method(deprecated_in((2, 4, 0)))
1063
if self.tt.final_kind(self.tt.root) is None:
1064
self.tt.cancel_deletion(self.tt.root)
1065
if self.tt.final_file_id(self.tt.root) is None:
1066
self.tt.version_file(self.tt.tree_file_id(self.tt.root),
1068
other_root_file_id = self.other_tree.get_root_id()
1069
if other_root_file_id is None:
1071
other_root = self.tt.trans_id_file_id(other_root_file_id)
1072
if other_root == self.tt.root:
1074
if self.this_tree.inventory.has_id(
1075
self.other_tree.inventory.root.file_id):
1076
# the other tree's root is a non-root in the current tree (as
1077
# when a previously unrelated branch is merged into another)
1079
if self.tt.final_kind(other_root) is not None:
1080
other_root_is_present = True
1082
# other_root doesn't have a physical representation. We still need
1083
# to move any references to the actual root of the tree.
1084
other_root_is_present = False
1085
# 'other_tree.inventory.root' is not present in this tree. We are
1086
# calling adjust_path for children which *want* to be present with a
1087
# correct place to go.
1088
for _, child in self.other_tree.inventory.root.children.iteritems():
1089
trans_id = self.tt.trans_id_file_id(child.file_id)
1090
if not other_root_is_present:
1091
if self.tt.final_kind(trans_id) is not None:
1092
# The item exist in the final tree and has a defined place
1095
# Move the item into the root
1097
final_name = self.tt.final_name(trans_id)
1098
except errors.NoFinalPath:
1099
# This file is not present anymore, ignore it.
1101
self.tt.adjust_path(final_name, self.tt.root, trans_id)
1102
if other_root_is_present:
1103
self.tt.cancel_creation(other_root)
1104
self.tt.cancel_versioning(other_root)
1106
def write_modified(self, results):
1107
modified_hashes = {}
1108
for path in results.modified_paths:
1109
file_id = self.this_tree.path2id(self.this_tree.relpath(path))
1112
hash = self.this_tree.get_file_sha1(file_id)
1115
modified_hashes[file_id] = hash
1116
self.this_tree.set_merge_modified(modified_hashes)
1119
def parent(entry, file_id):
1120
"""Determine the parent for a file_id (used as a key method)"""
1123
return entry.parent_id
1126
def name(entry, file_id):
1127
"""Determine the name for a file_id (used as a key method)"""
1133
def contents_sha1(tree, file_id):
1134
"""Determine the sha1 of the file contents (used as a key method)."""
1135
if not tree.has_id(file_id):
1137
return tree.get_file_sha1(file_id)
1140
def executable(tree, file_id):
1141
"""Determine the executability of a file-id (used as a key method)."""
1142
if not tree.has_id(file_id):
1144
if tree.kind(file_id) != "file":
1146
return tree.is_executable(file_id)
1149
def kind(tree, file_id):
1150
"""Determine the kind of a file-id (used as a key method)."""
1151
if not tree.has_id(file_id):
1153
return tree.kind(file_id)
1156
def _three_way(base, other, this):
1158
# if 'base == other', either they all agree, or only 'this' has
1161
elif this not in (base, other):
1162
# 'this' is neither 'base' nor 'other', so both sides changed
1165
# "Ambiguous clean merge" -- both sides have made the same change.
1168
# this == base: only other has changed.
1172
def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
1173
"""Consider LCAs when determining whether a change has occurred.
1175
If LCAS are all identical, this is the same as a _three_way comparison.
1177
:param bases: value in (BASE, [LCAS])
1178
:param other: value in OTHER
1179
:param this: value in THIS
1180
:param allow_overriding_lca: If there is more than one unique lca
1181
value, allow OTHER to override THIS if it has a new value, and
1182
THIS only has an lca value, or vice versa. This is appropriate for
1183
truly scalar values, not as much for non-scalars.
1184
:return: 'this', 'other', or 'conflict' depending on whether an entry
1187
# See doc/developers/lca_tree_merging.txt for details about this
1190
# Either Ambiguously clean, or nothing was actually changed. We
1193
base_val, lca_vals = bases
1194
# Remove 'base_val' from the lca_vals, because it is not interesting
1195
filtered_lca_vals = [lca_val for lca_val in lca_vals
1196
if lca_val != base_val]
1197
if len(filtered_lca_vals) == 0:
1198
return Merge3Merger._three_way(base_val, other, this)
1200
unique_lca_vals = set(filtered_lca_vals)
1201
if len(unique_lca_vals) == 1:
1202
return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
1204
if allow_overriding_lca:
1205
if other in unique_lca_vals:
1206
if this in unique_lca_vals:
1207
# Each side picked a different lca, conflict
1210
# This has a value which supersedes both lca values, and
1211
# other only has an lca value
1213
elif this in unique_lca_vals:
1214
# OTHER has a value which supersedes both lca values, and this
1215
# only has an lca value
1218
# At this point, the lcas disagree, and the tip disagree
1222
@deprecated_method(deprecated_in((2, 2, 0)))
1223
def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
1224
"""Do a three-way test on a scalar.
1225
Return "this", "other" or "conflict", depending whether a value wins.
1227
key_base = key(base_tree, file_id)
1228
key_other = key(other_tree, file_id)
1229
#if base == other, either they all agree, or only THIS has changed.
1230
if key_base == key_other:
1232
key_this = key(this_tree, file_id)
1233
# "Ambiguous clean merge"
1234
if key_this == key_other:
1236
elif key_this == key_base:
1241
def merge_names(self, file_id):
1242
def get_entry(tree):
1243
if tree.has_id(file_id):
1244
return tree.inventory[file_id]
1247
this_entry = get_entry(self.this_tree)
1248
other_entry = get_entry(self.other_tree)
1249
base_entry = get_entry(self.base_tree)
1250
entries = (base_entry, other_entry, this_entry)
1253
for entry in entries:
1256
parents.append(None)
1258
names.append(entry.name)
1259
parents.append(entry.parent_id)
1260
return self._merge_names(file_id, parents, names,
1261
resolver=self._three_way)
1263
def _merge_names(self, file_id, parents, names, resolver):
1264
"""Perform a merge on file_id names and parents"""
1265
base_name, other_name, this_name = names
1266
base_parent, other_parent, this_parent = parents
1268
name_winner = resolver(*names)
1270
parent_id_winner = resolver(*parents)
1271
if this_name is None:
1272
if name_winner == "this":
1273
name_winner = "other"
1274
if parent_id_winner == "this":
1275
parent_id_winner = "other"
1276
if name_winner == "this" and parent_id_winner == "this":
1278
if name_winner == 'conflict' or parent_id_winner == 'conflict':
1279
# Creating helpers (.OTHER or .THIS) here cause problems down the
1280
# road if a ContentConflict needs to be created so we should not do
1282
trans_id = self.tt.trans_id_file_id(file_id)
1283
self._raw_conflicts.append(('path conflict', trans_id, file_id,
1284
this_parent, this_name,
1285
other_parent, other_name))
1286
if not self.other_tree.has_id(file_id):
1287
# it doesn't matter whether the result was 'other' or
1288
# 'conflict'-- if it has no file id, we leave it alone.
1290
parent_id = parents[self.winner_idx[parent_id_winner]]
1291
name = names[self.winner_idx[name_winner]]
1292
if parent_id is not None or name is not None:
1293
# if we get here, name_winner and parent_winner are set to safe
1295
if parent_id is None and name is not None:
1296
# if parent_id is None and name is non-None, current file is
1298
if names[self.winner_idx[parent_id_winner]] != '':
1299
raise AssertionError(
1300
'File looks like a root, but named %s' %
1301
names[self.winner_idx[parent_id_winner]])
1302
parent_trans_id = transform.ROOT_PARENT
1304
parent_trans_id = self.tt.trans_id_file_id(parent_id)
1305
self.tt.adjust_path(name, parent_trans_id,
1306
self.tt.trans_id_file_id(file_id))
1308
def _do_merge_contents(self, file_id):
1309
"""Performs a merge on file_id contents."""
1310
def contents_pair(tree):
1311
if not tree.has_id(file_id):
1313
kind = tree.kind(file_id)
1315
contents = tree.get_file_sha1(file_id)
1316
elif kind == "symlink":
1317
contents = tree.get_symlink_target(file_id)
1320
return kind, contents
1322
# See SPOT run. run, SPOT, run.
1323
# So we're not QUITE repeating ourselves; we do tricky things with
1325
base_pair = contents_pair(self.base_tree)
1326
other_pair = contents_pair(self.other_tree)
1328
this_pair = contents_pair(self.this_tree)
1329
lca_pairs = [contents_pair(tree) for tree in self._lca_trees]
1330
winner = self._lca_multi_way((base_pair, lca_pairs), other_pair,
1331
this_pair, allow_overriding_lca=False)
1333
if base_pair == other_pair:
1336
# We delayed evaluating this_pair as long as we can to avoid
1337
# unnecessary sha1 calculation
1338
this_pair = contents_pair(self.this_tree)
1339
winner = self._three_way(base_pair, other_pair, this_pair)
1340
if winner == 'this':
1341
# No interesting changes introduced by OTHER
1343
# We have a hypothetical conflict, but if we have files, then we
1344
# can try to merge the content
1345
trans_id = self.tt.trans_id_file_id(file_id)
1346
params = MergeHookParams(self, file_id, trans_id, this_pair[0],
1347
other_pair[0], winner)
1348
hooks = self.active_hooks
1349
hook_status = 'not_applicable'
1351
hook_status, lines = hook.merge_contents(params)
1352
if hook_status != 'not_applicable':
1353
# Don't try any more hooks, this one applies.
1355
# If the merge ends up replacing the content of the file, we get rid of
1356
# it at the end of this method (this variable is used to track the
1357
# exceptions to this rule).
1360
if hook_status == 'not_applicable':
1361
# No merge hook was able to resolve the situation. Two cases exist:
1362
# a content conflict or a duplicate one.
1364
name = self.tt.final_name(trans_id)
1365
parent_id = self.tt.final_parent(trans_id)
1367
inhibit_content_conflict = False
1368
if params.this_kind is None: # file_id is not in THIS
1369
# Is the name used for a different file_id ?
1370
dupe_path = self.other_tree.id2path(file_id)
1371
this_id = self.this_tree.path2id(dupe_path)
1372
if this_id is not None:
1373
# Two entries for the same path
1375
# versioning the merged file will trigger a duplicate
1377
self.tt.version_file(file_id, trans_id)
1378
transform.create_from_tree(
1379
self.tt, trans_id, self.other_tree, file_id,
1380
filter_tree_path=self._get_filter_tree_path(file_id))
1381
inhibit_content_conflict = True
1382
elif params.other_kind is None: # file_id is not in OTHER
1383
# Is the name used for a different file_id ?
1384
dupe_path = self.this_tree.id2path(file_id)
1385
other_id = self.other_tree.path2id(dupe_path)
1386
if other_id is not None:
1387
# Two entries for the same path again, but here, the other
1388
# entry will also be merged. We simply inhibit the
1389
# 'content' conflict creation because we know OTHER will
1390
# create (or has already created depending on ordering) an
1391
# entry at the same path. This will trigger a 'duplicate'
1394
inhibit_content_conflict = True
1395
if not inhibit_content_conflict:
1396
if params.this_kind is not None:
1397
self.tt.unversion_file(trans_id)
1398
# This is a contents conflict, because none of the available
1399
# functions could merge it.
1400
file_group = self._dump_conflicts(name, parent_id, file_id,
1402
self._raw_conflicts.append(('contents conflict', file_group))
1403
elif hook_status == 'success':
1404
self.tt.create_file(lines, trans_id)
1405
elif hook_status == 'conflicted':
1406
# XXX: perhaps the hook should be able to provide
1407
# the BASE/THIS/OTHER files?
1408
self.tt.create_file(lines, trans_id)
1409
self._raw_conflicts.append(('text conflict', trans_id))
1410
name = self.tt.final_name(trans_id)
1411
parent_id = self.tt.final_parent(trans_id)
1412
self._dump_conflicts(name, parent_id, file_id)
1413
elif hook_status == 'delete':
1414
self.tt.unversion_file(trans_id)
1416
elif hook_status == 'done':
1417
# The hook function did whatever it needs to do directly, no
1418
# further action needed here.
1421
raise AssertionError('unknown hook_status: %r' % (hook_status,))
1422
if not self.this_tree.has_id(file_id) and result == "modified":
1423
self.tt.version_file(file_id, trans_id)
1425
# The merge has been performed and produced a new content, so the
1426
# old contents should not be retained.
1427
self.tt.delete_contents(trans_id)
1430
def _default_other_winner_merge(self, merge_hook_params):
1431
"""Replace this contents with other."""
1432
file_id = merge_hook_params.file_id
1433
trans_id = merge_hook_params.trans_id
1434
if self.other_tree.has_id(file_id):
1435
# OTHER changed the file
1436
transform.create_from_tree(
1437
self.tt, trans_id, self.other_tree, file_id,
1438
filter_tree_path=self._get_filter_tree_path(file_id))
1440
elif self.this_tree.has_id(file_id):
1441
# OTHER deleted the file
1442
return 'delete', None
1444
raise AssertionError(
1445
'winner is OTHER, but file_id %r not in THIS or OTHER tree'
1448
def merge_contents(self, merge_hook_params):
1449
"""Fallback merge logic after user installed hooks."""
1450
# This function is used in merge hooks as the fallback instance.
1451
# Perhaps making this function and the functions it calls be a
1452
# a separate class would be better.
1453
if merge_hook_params.winner == 'other':
1454
# OTHER is a straight winner, so replace this contents with other
1455
return self._default_other_winner_merge(merge_hook_params)
1456
elif merge_hook_params.is_file_merge():
1457
# THIS and OTHER are both files, so text merge. Either
1458
# BASE is a file, or both converted to files, so at least we
1459
# have agreement that output should be a file.
1461
self.text_merge(merge_hook_params.file_id,
1462
merge_hook_params.trans_id)
1463
except errors.BinaryFile:
1464
return 'not_applicable', None
1467
return 'not_applicable', None
1469
def get_lines(self, tree, file_id):
1470
"""Return the lines in a file, or an empty list."""
1471
if tree.has_id(file_id):
1472
return tree.get_file_lines(file_id)
1476
def text_merge(self, file_id, trans_id):
1477
"""Perform a three-way text merge on a file_id"""
1478
# it's possible that we got here with base as a different type.
1479
# if so, we just want two-way text conflicts.
1480
if self.base_tree.has_id(file_id) and \
1481
self.base_tree.kind(file_id) == "file":
1482
base_lines = self.get_lines(self.base_tree, file_id)
1485
other_lines = self.get_lines(self.other_tree, file_id)
1486
this_lines = self.get_lines(self.this_tree, file_id)
1487
m3 = merge3.Merge3(base_lines, this_lines, other_lines,
1488
is_cherrypick=self.cherrypick)
1489
start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
1490
if self.show_base is True:
1491
base_marker = '|' * 7
1495
def iter_merge3(retval):
1496
retval["text_conflicts"] = False
1497
for line in m3.merge_lines(name_a = "TREE",
1498
name_b = "MERGE-SOURCE",
1499
name_base = "BASE-REVISION",
1500
start_marker=start_marker,
1501
base_marker=base_marker,
1502
reprocess=self.reprocess):
1503
if line.startswith(start_marker):
1504
retval["text_conflicts"] = True
1505
yield line.replace(start_marker, '<' * 7)
1509
merge3_iterator = iter_merge3(retval)
1510
self.tt.create_file(merge3_iterator, trans_id)
1511
if retval["text_conflicts"] is True:
1512
self._raw_conflicts.append(('text conflict', trans_id))
1513
name = self.tt.final_name(trans_id)
1514
parent_id = self.tt.final_parent(trans_id)
1515
file_group = self._dump_conflicts(name, parent_id, file_id,
1516
this_lines, base_lines,
1518
file_group.append(trans_id)
1521
def _get_filter_tree_path(self, file_id):
1522
if self.this_tree.supports_content_filtering():
1523
# We get the path from the working tree if it exists.
1524
# That fails though when OTHER is adding a file, so
1525
# we fall back to the other tree to find the path if
1526
# it doesn't exist locally.
1528
return self.this_tree.id2path(file_id)
1529
except errors.NoSuchId:
1530
return self.other_tree.id2path(file_id)
1531
# Skip the id2path lookup for older formats
1534
def _dump_conflicts(self, name, parent_id, file_id, this_lines=None,
1535
base_lines=None, other_lines=None, set_version=False,
1537
"""Emit conflict files.
1538
If this_lines, base_lines, or other_lines are omitted, they will be
1539
determined automatically. If set_version is true, the .OTHER, .THIS
1540
or .BASE (in that order) will be created as versioned files.
1542
data = [('OTHER', self.other_tree, other_lines),
1543
('THIS', self.this_tree, this_lines)]
1545
data.append(('BASE', self.base_tree, base_lines))
1547
# We need to use the actual path in the working tree of the file here,
1548
# ignoring the conflict suffixes
1550
if wt.supports_content_filtering():
1552
filter_tree_path = wt.id2path(file_id)
1553
except errors.NoSuchId:
1554
# file has been deleted
1555
filter_tree_path = None
1557
# Skip the id2path lookup for older formats
1558
filter_tree_path = None
1562
for suffix, tree, lines in data:
1563
if tree.has_id(file_id):
1564
trans_id = self._conflict_file(name, parent_id, tree, file_id,
1565
suffix, lines, filter_tree_path)
1566
file_group.append(trans_id)
1567
if set_version and not versioned:
1568
self.tt.version_file(file_id, trans_id)
1572
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
1573
lines=None, filter_tree_path=None):
1574
"""Emit a single conflict file."""
1575
name = name + '.' + suffix
1576
trans_id = self.tt.create_path(name, parent_id)
1577
transform.create_from_tree(self.tt, trans_id, tree, file_id, lines,
1581
def merge_executable(self, file_id, file_status):
1582
"""Perform a merge on the execute bit."""
1583
executable = [self.executable(t, file_id) for t in (self.base_tree,
1584
self.other_tree, self.this_tree)]
1585
self._merge_executable(file_id, executable, file_status,
1586
resolver=self._three_way)
1588
def _merge_executable(self, file_id, executable, file_status,
1590
"""Perform a merge on the execute bit."""
1591
base_executable, other_executable, this_executable = executable
1592
if file_status == "deleted":
1594
winner = resolver(*executable)
1595
if winner == "conflict":
1596
# There must be a None in here, if we have a conflict, but we
1597
# need executability since file status was not deleted.
1598
if self.executable(self.other_tree, file_id) is None:
1602
if winner == 'this' and file_status != "modified":
1604
trans_id = self.tt.trans_id_file_id(file_id)
1605
if self.tt.final_kind(trans_id) != "file":
1607
if winner == "this":
1608
executability = this_executable
1610
if self.other_tree.has_id(file_id):
1611
executability = other_executable
1612
elif self.this_tree.has_id(file_id):
1613
executability = this_executable
1614
elif self.base_tree_has_id(file_id):
1615
executability = base_executable
1616
if executability is not None:
1617
trans_id = self.tt.trans_id_file_id(file_id)
1618
self.tt.set_executability(executability, trans_id)
1620
def cook_conflicts(self, fs_conflicts):
1621
"""Convert all conflicts into a form that doesn't depend on trans_id"""
1622
content_conflict_file_ids = set()
1623
cooked_conflicts = transform.cook_conflicts(fs_conflicts, self.tt)
1624
fp = transform.FinalPaths(self.tt)
1625
for conflict in self._raw_conflicts:
1626
conflict_type = conflict[0]
1627
if conflict_type == 'path conflict':
1629
this_parent, this_name,
1630
other_parent, other_name) = conflict[1:]
1631
if this_parent is None or this_name is None:
1632
this_path = '<deleted>'
1634
parent_path = fp.get_path(
1635
self.tt.trans_id_file_id(this_parent))
1636
this_path = osutils.pathjoin(parent_path, this_name)
1637
if other_parent is None or other_name is None:
1638
other_path = '<deleted>'
1640
if other_parent == self.other_tree.get_root_id():
1641
# The tree transform doesn't know about the other root,
1642
# so we special case here to avoid a NoFinalPath
1646
parent_path = fp.get_path(
1647
self.tt.trans_id_file_id(other_parent))
1648
other_path = osutils.pathjoin(parent_path, other_name)
1649
c = _mod_conflicts.Conflict.factory(
1650
'path conflict', path=this_path,
1651
conflict_path=other_path,
1653
elif conflict_type == 'contents conflict':
1654
for trans_id in conflict[1]:
1655
file_id = self.tt.final_file_id(trans_id)
1656
if file_id is not None:
1657
# Ok we found the relevant file-id
1659
path = fp.get_path(trans_id)
1660
for suffix in ('.BASE', '.THIS', '.OTHER'):
1661
if path.endswith(suffix):
1662
# Here is the raw path
1663
path = path[:-len(suffix)]
1665
c = _mod_conflicts.Conflict.factory(conflict_type,
1666
path=path, file_id=file_id)
1667
content_conflict_file_ids.add(file_id)
1668
elif conflict_type == 'text conflict':
1669
trans_id = conflict[1]
1670
path = fp.get_path(trans_id)
1671
file_id = self.tt.final_file_id(trans_id)
1672
c = _mod_conflicts.Conflict.factory(conflict_type,
1673
path=path, file_id=file_id)
1675
raise AssertionError('bad conflict type: %r' % (conflict,))
1676
cooked_conflicts.append(c)
1678
self.cooked_conflicts = []
1679
# We want to get rid of path conflicts when a corresponding contents
1680
# conflict exists. This can occur when one branch deletes a file while
1681
# the other renames *and* modifies it. In this case, the content
1682
# conflict is enough.
1683
for c in cooked_conflicts:
1684
if (c.typestring == 'path conflict'
1685
and c.file_id in content_conflict_file_ids):
1687
self.cooked_conflicts.append(c)
1688
self.cooked_conflicts.sort(key=_mod_conflicts.Conflict.sort_key)
1691
class WeaveMerger(Merge3Merger):
1692
"""Three-way tree merger, text weave merger."""
1693
supports_reprocess = True
1694
supports_show_base = False
1695
supports_reverse_cherrypick = False
1696
history_based = True
1698
def _generate_merge_plan(self, file_id, base):
1699
return self.this_tree.plan_file_merge(file_id, self.other_tree,
1702
def _merged_lines(self, file_id):
1703
"""Generate the merged lines.
1704
There is no distinction between lines that are meant to contain <<<<<<<
1708
base = self.base_tree
1711
plan = self._generate_merge_plan(file_id, base)
1712
if 'merge' in debug.debug_flags:
1714
trans_id = self.tt.trans_id_file_id(file_id)
1715
name = self.tt.final_name(trans_id) + '.plan'
1716
contents = ('%11s|%s' % l for l in plan)
1717
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1718
textmerge = versionedfile.PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1719
'>>>>>>> MERGE-SOURCE\n')
1720
lines, conflicts = textmerge.merge_lines(self.reprocess)
1722
base_lines = textmerge.base_from_plan()
1725
return lines, base_lines
1727
def text_merge(self, file_id, trans_id):
1728
"""Perform a (weave) text merge for a given file and file-id.
1729
If conflicts are encountered, .THIS and .OTHER files will be emitted,
1730
and a conflict will be noted.
1732
lines, base_lines = self._merged_lines(file_id)
1734
# Note we're checking whether the OUTPUT is binary in this case,
1735
# because we don't want to get into weave merge guts.
1736
textfile.check_text_lines(lines)
1737
self.tt.create_file(lines, trans_id)
1738
if base_lines is not None:
1740
self._raw_conflicts.append(('text conflict', trans_id))
1741
name = self.tt.final_name(trans_id)
1742
parent_id = self.tt.final_parent(trans_id)
1743
file_group = self._dump_conflicts(name, parent_id, file_id,
1745
base_lines=base_lines)
1746
file_group.append(trans_id)
1749
class LCAMerger(WeaveMerger):
1751
def _generate_merge_plan(self, file_id, base):
1752
return self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1755
class Diff3Merger(Merge3Merger):
1756
"""Three-way merger using external diff3 for text merging"""
1758
def dump_file(self, temp_dir, name, tree, file_id):
1759
out_path = osutils.pathjoin(temp_dir, name)
1760
out_file = open(out_path, "wb")
1762
in_file = tree.get_file(file_id)
1763
for line in in_file:
1764
out_file.write(line)
1769
def text_merge(self, file_id, trans_id):
1770
"""Perform a diff3 merge using a specified file-id and trans-id.
1771
If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
1772
will be dumped, and a will be conflict noted.
1775
temp_dir = osutils.mkdtemp(prefix="bzr-")
1777
new_file = osutils.pathjoin(temp_dir, "new")
1778
this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
1779
base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
1780
other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
1781
status = bzrlib.patch.diff3(new_file, this, base, other)
1782
if status not in (0, 1):
1783
raise errors.BzrError("Unhandled diff3 exit code")
1784
f = open(new_file, 'rb')
1786
self.tt.create_file(f, trans_id)
1790
name = self.tt.final_name(trans_id)
1791
parent_id = self.tt.final_parent(trans_id)
1792
self._dump_conflicts(name, parent_id, file_id)
1793
self._raw_conflicts.append(('text conflict', trans_id))
1795
osutils.rmtree(temp_dir)
1798
class PathNotInTree(errors.BzrError):
1800
_fmt = """Merge-into failed because %(tree)s does not contain %(path)s."""
1802
def __init__(self, path, tree):
1803
errors.BzrError.__init__(self, path=path, tree=tree)
1806
class MergeIntoMerger(Merger):
1807
"""Merger that understands other_tree will be merged into a subdir.
1809
This also changes the Merger api so that it uses real Branch, revision_id,
1810
and RevisonTree objects, rather than using revision specs.
1813
def __init__(self, this_tree, other_branch, other_tree, target_subdir,
1814
source_subpath, other_rev_id=None):
1815
"""Create a new MergeIntoMerger object.
1817
source_subpath in other_tree will be effectively copied to
1818
target_subdir in this_tree.
1820
:param this_tree: The tree that we will be merging into.
1821
:param other_branch: The Branch we will be merging from.
1822
:param other_tree: The RevisionTree object we want to merge.
1823
:param target_subdir: The relative path where we want to merge
1824
other_tree into this_tree
1825
:param source_subpath: The relative path specifying the subtree of
1826
other_tree to merge into this_tree.
1828
# It is assumed that we are merging a tree that is not in our current
1829
# ancestry, which means we are using the "EmptyTree" as our basis.
1830
null_ancestor_tree = this_tree.branch.repository.revision_tree(
1831
_mod_revision.NULL_REVISION)
1832
super(MergeIntoMerger, self).__init__(
1833
this_branch=this_tree.branch,
1834
this_tree=this_tree,
1835
other_tree=other_tree,
1836
base_tree=null_ancestor_tree,
1838
self._target_subdir = target_subdir
1839
self._source_subpath = source_subpath
1840
self.other_branch = other_branch
1841
if other_rev_id is None:
1842
other_rev_id = other_tree.get_revision_id()
1843
self.other_rev_id = self.other_basis = other_rev_id
1844
self.base_is_ancestor = True
1845
self.backup_files = True
1846
self.merge_type = Merge3Merger
1847
self.show_base = False
1848
self.reprocess = False
1849
self.interesting_ids = None
1850
self.merge_type = _MergeTypeParameterizer(MergeIntoMergeType,
1851
target_subdir=self._target_subdir,
1852
source_subpath=self._source_subpath)
1853
if self._source_subpath != '':
1854
# If this isn't a partial merge make sure the revisions will be
1856
self._maybe_fetch(self.other_branch, self.this_branch,
1859
def set_pending(self):
1860
if self._source_subpath != '':
1862
Merger.set_pending(self)
1865
class _MergeTypeParameterizer(object):
1866
"""Wrap a merge-type class to provide extra parameters.
1868
This is hack used by MergeIntoMerger to pass some extra parameters to its
1869
merge_type. Merger.do_merge() sets up its own set of parameters to pass to
1870
the 'merge_type' member. It is difficult override do_merge without
1871
re-writing the whole thing, so instead we create a wrapper which will pass
1872
the extra parameters.
1875
def __init__(self, merge_type, **kwargs):
1876
self._extra_kwargs = kwargs
1877
self._merge_type = merge_type
1879
def __call__(self, *args, **kwargs):
1880
kwargs.update(self._extra_kwargs)
1881
return self._merge_type(*args, **kwargs)
1883
def __getattr__(self, name):
1884
return getattr(self._merge_type, name)
1887
class MergeIntoMergeType(Merge3Merger):
1888
"""Merger that incorporates a tree (or part of a tree) into another."""
1890
def __init__(self, *args, **kwargs):
1891
"""Initialize the merger object.
1893
:param args: See Merge3Merger.__init__'s args.
1894
:param kwargs: See Merge3Merger.__init__'s keyword args, except for
1895
source_subpath and target_subdir.
1896
:keyword source_subpath: The relative path specifying the subtree of
1897
other_tree to merge into this_tree.
1898
:keyword target_subdir: The relative path where we want to merge
1899
other_tree into this_tree
1901
# All of the interesting work happens during Merge3Merger.__init__(),
1902
# so we have have to hack in to get our extra parameters set.
1903
self._source_subpath = kwargs.pop('source_subpath')
1904
self._target_subdir = kwargs.pop('target_subdir')
1905
super(MergeIntoMergeType, self).__init__(*args, **kwargs)
1907
def _compute_transform(self):
1908
child_pb = ui.ui_factory.nested_progress_bar()
1910
entries = self._entries_to_incorporate()
1911
entries = list(entries)
1912
for num, (entry, parent_id) in enumerate(entries):
1913
child_pb.update(gettext('Preparing file merge'), num, len(entries))
1914
parent_trans_id = self.tt.trans_id_file_id(parent_id)
1915
trans_id = transform.new_by_entry(self.tt, entry,
1916
parent_trans_id, self.other_tree)
1919
self._finish_computing_transform()
1921
def _entries_to_incorporate(self):
1922
"""Yields pairs of (inventory_entry, new_parent)."""
1923
other_inv = self.other_tree.inventory
1924
subdir_id = other_inv.path2id(self._source_subpath)
1925
if subdir_id is None:
1926
# XXX: The error would be clearer if it gave the URL of the source
1927
# branch, but we don't have a reference to that here.
1928
raise PathNotInTree(self._source_subpath, "Source tree")
1929
subdir = other_inv[subdir_id]
1930
parent_in_target = osutils.dirname(self._target_subdir)
1931
target_id = self.this_tree.inventory.path2id(parent_in_target)
1932
if target_id is None:
1933
raise PathNotInTree(self._target_subdir, "Target tree")
1934
name_in_target = osutils.basename(self._target_subdir)
1935
merge_into_root = subdir.copy()
1936
merge_into_root.name = name_in_target
1937
if self.this_tree.inventory.has_id(merge_into_root.file_id):
1938
# Give the root a new file-id.
1939
# This can happen fairly easily if the directory we are
1940
# incorporating is the root, and both trees have 'TREE_ROOT' as
1941
# their root_id. Users will expect this to Just Work, so we
1942
# change the file-id here.
1943
# Non-root file-ids could potentially conflict too. That's really
1944
# an edge case, so we don't do anything special for those. We let
1945
# them cause conflicts.
1946
merge_into_root.file_id = generate_ids.gen_file_id(name_in_target)
1947
yield (merge_into_root, target_id)
1948
if subdir.kind != 'directory':
1949
# No children, so we are done.
1951
for ignored_path, entry in other_inv.iter_entries_by_dir(subdir_id):
1952
parent_id = entry.parent_id
1953
if parent_id == subdir.file_id:
1954
# The root's parent ID has changed, so make sure children of
1955
# the root refer to the new ID.
1956
parent_id = merge_into_root.file_id
1957
yield (entry, parent_id)
1960
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
1962
merge_type=Merge3Merger,
1963
interesting_ids=None,
1967
interesting_files=None,
1970
change_reporter=None):
1971
"""Primary interface for merging.
1973
Typical use is probably::
1975
merge_inner(branch, branch.get_revision_tree(other_revision),
1976
branch.get_revision_tree(base_revision))
1978
if this_tree is None:
1979
raise errors.BzrError("bzrlib.merge.merge_inner requires a this_tree "
1981
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1982
pb=pb, change_reporter=change_reporter)
1983
merger.backup_files = backup_files
1984
merger.merge_type = merge_type
1985
merger.interesting_ids = interesting_ids
1986
merger.ignore_zero = ignore_zero
1987
if interesting_files:
1989
raise ValueError('Only supply interesting_ids'
1990
' or interesting_files')
1991
merger.interesting_files = interesting_files
1992
merger.show_base = show_base
1993
merger.reprocess = reprocess
1994
merger.other_rev_id = other_rev_id
1995
merger.other_basis = other_rev_id
1996
get_revision_id = getattr(base_tree, 'get_revision_id', None)
1997
if get_revision_id is None:
1998
get_revision_id = base_tree.last_revision
1999
merger.cache_trees_with_revision_ids([other_tree, base_tree, this_tree])
2000
merger.set_base_revision(get_revision_id(), this_branch)
2001
return merger.do_merge()
2004
merge_type_registry = registry.Registry()
2005
merge_type_registry.register('diff3', Diff3Merger,
2006
"Merge using external diff3.")
2007
merge_type_registry.register('lca', LCAMerger,
2008
"LCA-newness merge.")
2009
merge_type_registry.register('merge3', Merge3Merger,
2010
"Native diff3-style merge.")
2011
merge_type_registry.register('weave', WeaveMerger,
2012
"Weave-based merge.")
2015
def get_merge_type_registry():
2016
"""Merge type registry was previously in bzrlib.option
2018
This method provides a backwards compatible way to retrieve it.
2020
return merge_type_registry
2023
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
2024
def status_a(revision, text):
2025
if revision in ancestors_b:
2026
return 'killed-b', text
2028
return 'new-a', text
2030
def status_b(revision, text):
2031
if revision in ancestors_a:
2032
return 'killed-a', text
2034
return 'new-b', text
2036
plain_a = [t for (a, t) in annotated_a]
2037
plain_b = [t for (a, t) in annotated_b]
2038
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
2039
blocks = matcher.get_matching_blocks()
2042
for ai, bi, l in blocks:
2043
# process all mismatched sections
2044
# (last mismatched section is handled because blocks always
2045
# includes a 0-length last block)
2046
for revision, text in annotated_a[a_cur:ai]:
2047
yield status_a(revision, text)
2048
for revision, text in annotated_b[b_cur:bi]:
2049
yield status_b(revision, text)
2050
# and now the matched section
2053
for text_a in plain_a[ai:a_cur]:
2054
yield "unchanged", text_a
2057
class _PlanMergeBase(object):
2059
def __init__(self, a_rev, b_rev, vf, key_prefix):
2062
:param a_rev: Revision-id of one revision to merge
2063
:param b_rev: Revision-id of the other revision to merge
2064
:param vf: A VersionedFiles containing both revisions
2065
:param key_prefix: A prefix for accessing keys in vf, typically
2071
self._last_lines = None
2072
self._last_lines_revision_id = None
2073
self._cached_matching_blocks = {}
2074
self._key_prefix = key_prefix
2075
self._precache_tip_lines()
2077
def _precache_tip_lines(self):
2078
lines = self.get_lines([self.a_rev, self.b_rev])
2079
self.lines_a = lines[self.a_rev]
2080
self.lines_b = lines[self.b_rev]
2082
def get_lines(self, revisions):
2083
"""Get lines for revisions from the backing VersionedFiles.
2085
:raises RevisionNotPresent: on absent texts.
2087
keys = [(self._key_prefix + (rev,)) for rev in revisions]
2089
for record in self.vf.get_record_stream(keys, 'unordered', True):
2090
if record.storage_kind == 'absent':
2091
raise errors.RevisionNotPresent(record.key, self.vf)
2092
result[record.key[-1]] = osutils.chunks_to_lines(
2093
record.get_bytes_as('chunked'))
2096
def plan_merge(self):
2097
"""Generate a 'plan' for merging the two revisions.
2099
This involves comparing their texts and determining the cause of
2100
differences. If text A has a line and text B does not, then either the
2101
line was added to text A, or it was deleted from B. Once the causes
2102
are combined, they are written out in the format described in
2103
VersionedFile.plan_merge
2105
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
2106
unique_a, unique_b = self._unique_lines(blocks)
2107
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
2108
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
2109
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
2111
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
2114
for i, j, n in blocks:
2115
for a_index in range(last_i, i):
2116
if a_index in new_a:
2117
if a_index in killed_b:
2118
yield 'conflicted-a', self.lines_a[a_index]
2120
yield 'new-a', self.lines_a[a_index]
2122
yield 'killed-b', self.lines_a[a_index]
2123
for b_index in range(last_j, j):
2124
if b_index in new_b:
2125
if b_index in killed_a:
2126
yield 'conflicted-b', self.lines_b[b_index]
2128
yield 'new-b', self.lines_b[b_index]
2130
yield 'killed-a', self.lines_b[b_index]
2131
# handle common lines
2132
for a_index in range(i, i+n):
2133
yield 'unchanged', self.lines_a[a_index]
2137
def _get_matching_blocks(self, left_revision, right_revision):
2138
"""Return a description of which sections of two revisions match.
2140
See SequenceMatcher.get_matching_blocks
2142
cached = self._cached_matching_blocks.get((left_revision,
2144
if cached is not None:
2146
if self._last_lines_revision_id == left_revision:
2147
left_lines = self._last_lines
2148
right_lines = self.get_lines([right_revision])[right_revision]
2150
lines = self.get_lines([left_revision, right_revision])
2151
left_lines = lines[left_revision]
2152
right_lines = lines[right_revision]
2153
self._last_lines = right_lines
2154
self._last_lines_revision_id = right_revision
2155
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
2157
return matcher.get_matching_blocks()
2159
def _unique_lines(self, matching_blocks):
2160
"""Analyse matching_blocks to determine which lines are unique
2162
:return: a tuple of (unique_left, unique_right), where the values are
2163
sets of line numbers of unique lines.
2169
for i, j, n in matching_blocks:
2170
unique_left.extend(range(last_i, i))
2171
unique_right.extend(range(last_j, j))
2174
return unique_left, unique_right
2177
def _subtract_plans(old_plan, new_plan):
2178
"""Remove changes from new_plan that came from old_plan.
2180
It is assumed that the difference between the old_plan and new_plan
2181
is their choice of 'b' text.
2183
All lines from new_plan that differ from old_plan are emitted
2184
verbatim. All lines from new_plan that match old_plan but are
2185
not about the 'b' revision are emitted verbatim.
2187
Lines that match and are about the 'b' revision are the lines we
2188
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
2189
is skipped entirely.
2191
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
2194
for i, j, n in matcher.get_matching_blocks():
2195
for jj in range(last_j, j):
2197
for jj in range(j, j+n):
2198
plan_line = new_plan[jj]
2199
if plan_line[0] == 'new-b':
2201
elif plan_line[0] == 'killed-b':
2202
yield 'unchanged', plan_line[1]
2208
class _PlanMerge(_PlanMergeBase):
2209
"""Plan an annotate merge using on-the-fly annotation"""
2211
def __init__(self, a_rev, b_rev, vf, key_prefix):
2212
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
2213
self.a_key = self._key_prefix + (self.a_rev,)
2214
self.b_key = self._key_prefix + (self.b_rev,)
2215
self.graph = _mod_graph.Graph(self.vf)
2216
heads = self.graph.heads((self.a_key, self.b_key))
2218
# one side dominates, so we can just return its values, yay for
2220
# Ideally we would know that before we get this far
2221
self._head_key = heads.pop()
2222
if self._head_key == self.a_key:
2226
trace.mutter('found dominating revision for %s\n%s > %s', self.vf,
2227
self._head_key[-1], other)
2230
self._head_key = None
2233
def _precache_tip_lines(self):
2234
# Turn this into a no-op, because we will do this later
2237
def _find_recursive_lcas(self):
2238
"""Find all the ancestors back to a unique lca"""
2239
cur_ancestors = (self.a_key, self.b_key)
2240
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
2241
# rather than a key tuple. We will just map that directly to no common
2245
next_lcas = self.graph.find_lca(*cur_ancestors)
2246
# Map a plain NULL_REVISION to a simple no-ancestors
2247
if next_lcas == set([_mod_revision.NULL_REVISION]):
2249
# Order the lca's based on when they were merged into the tip
2250
# While the actual merge portion of weave merge uses a set() of
2251
# active revisions, the order of insertion *does* effect the
2252
# implicit ordering of the texts.
2253
for rev_key in cur_ancestors:
2254
ordered_parents = tuple(self.graph.find_merge_order(rev_key,
2256
parent_map[rev_key] = ordered_parents
2257
if len(next_lcas) == 0:
2259
elif len(next_lcas) == 1:
2260
parent_map[list(next_lcas)[0]] = ()
2262
elif len(next_lcas) > 2:
2263
# More than 2 lca's, fall back to grabbing all nodes between
2264
# this and the unique lca.
2265
trace.mutter('More than 2 LCAs, falling back to all nodes for:'
2267
self.a_key, self.b_key, cur_ancestors)
2268
cur_lcas = next_lcas
2269
while len(cur_lcas) > 1:
2270
cur_lcas = self.graph.find_lca(*cur_lcas)
2271
if len(cur_lcas) == 0:
2272
# No common base to find, use the full ancestry
2275
unique_lca = list(cur_lcas)[0]
2276
if unique_lca == _mod_revision.NULL_REVISION:
2277
# find_lca will return a plain 'NULL_REVISION' rather
2278
# than a key tuple when there is no common ancestor, we
2279
# prefer to just use None, because it doesn't confuse
2280
# _get_interesting_texts()
2282
parent_map.update(self._find_unique_parents(next_lcas,
2285
cur_ancestors = next_lcas
2288
def _find_unique_parents(self, tip_keys, base_key):
2289
"""Find ancestors of tip that aren't ancestors of base.
2291
:param tip_keys: Nodes that are interesting
2292
:param base_key: Cull all ancestors of this node
2293
:return: The parent map for all revisions between tip_keys and
2294
base_key. base_key will be included. References to nodes outside of
2295
the ancestor set will also be removed.
2297
# TODO: this would be simpler if find_unique_ancestors took a list
2298
# instead of a single tip, internally it supports it, but it
2299
# isn't a "backwards compatible" api change.
2300
if base_key is None:
2301
parent_map = dict(self.graph.iter_ancestry(tip_keys))
2302
# We remove NULL_REVISION because it isn't a proper tuple key, and
2303
# thus confuses things like _get_interesting_texts, and our logic
2304
# to add the texts into the memory weave.
2305
if _mod_revision.NULL_REVISION in parent_map:
2306
parent_map.pop(_mod_revision.NULL_REVISION)
2309
for tip in tip_keys:
2311
self.graph.find_unique_ancestors(tip, [base_key]))
2312
parent_map = self.graph.get_parent_map(interesting)
2313
parent_map[base_key] = ()
2314
culled_parent_map, child_map, tails = self._remove_external_references(
2316
# Remove all the tails but base_key
2317
if base_key is not None:
2318
tails.remove(base_key)
2319
self._prune_tails(culled_parent_map, child_map, tails)
2320
# Now remove all the uninteresting 'linear' regions
2321
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
2325
def _remove_external_references(parent_map):
2326
"""Remove references that go outside of the parent map.
2328
:param parent_map: Something returned from Graph.get_parent_map(keys)
2329
:return: (filtered_parent_map, child_map, tails)
2330
filtered_parent_map is parent_map without external references
2331
child_map is the {parent_key: [child_keys]} mapping
2332
tails is a list of nodes that do not have any parents in the map
2334
# TODO: The basic effect of this function seems more generic than
2335
# _PlanMerge. But the specific details of building a child_map,
2336
# and computing tails seems very specific to _PlanMerge.
2337
# Still, should this be in Graph land?
2338
filtered_parent_map = {}
2341
for key, parent_keys in parent_map.iteritems():
2342
culled_parent_keys = [p for p in parent_keys if p in parent_map]
2343
if not culled_parent_keys:
2345
for parent_key in culled_parent_keys:
2346
child_map.setdefault(parent_key, []).append(key)
2347
# TODO: Do we want to do this, it adds overhead for every node,
2348
# just to say that the node has no children
2349
child_map.setdefault(key, [])
2350
filtered_parent_map[key] = culled_parent_keys
2351
return filtered_parent_map, child_map, tails
2354
def _prune_tails(parent_map, child_map, tails_to_remove):
2355
"""Remove tails from the parent map.
2357
This will remove the supplied revisions until no more children have 0
2360
:param parent_map: A dict of {child: [parents]}, this dictionary will
2361
be modified in place.
2362
:param tails_to_remove: A list of tips that should be removed,
2363
this list will be consumed
2364
:param child_map: The reverse dict of parent_map ({parent: [children]})
2365
this dict will be modified
2366
:return: None, parent_map will be modified in place.
2368
while tails_to_remove:
2369
next = tails_to_remove.pop()
2370
parent_map.pop(next)
2371
children = child_map.pop(next)
2372
for child in children:
2373
child_parents = parent_map[child]
2374
child_parents.remove(next)
2375
if len(child_parents) == 0:
2376
tails_to_remove.append(child)
2378
def _get_interesting_texts(self, parent_map):
2379
"""Return a dict of texts we are interested in.
2381
Note that the input is in key tuples, but the output is in plain
2384
:param parent_map: The output from _find_recursive_lcas
2385
:return: A dict of {'revision_id':lines} as returned by
2386
_PlanMergeBase.get_lines()
2388
all_revision_keys = set(parent_map)
2389
all_revision_keys.add(self.a_key)
2390
all_revision_keys.add(self.b_key)
2392
# Everything else is in 'keys' but get_lines is in 'revision_ids'
2393
all_texts = self.get_lines([k[-1] for k in all_revision_keys])
2396
def _build_weave(self):
2397
from bzrlib import weave
2398
self._weave = weave.Weave(weave_name='in_memory_weave',
2399
allow_reserved=True)
2400
parent_map = self._find_recursive_lcas()
2402
all_texts = self._get_interesting_texts(parent_map)
2404
# Note: Unfortunately, the order given by topo_sort will effect the
2405
# ordering resolution in the output. Specifically, if you add A then B,
2406
# then in the output text A lines will show up before B lines. And, of
2407
# course, topo_sort doesn't guarantee any real ordering.
2408
# So we use merge_sort, and add a fake node on the tip.
2409
# This ensures that left-hand parents will always be inserted into the
2410
# weave before right-hand parents.
2411
tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
2412
parent_map[tip_key] = (self.a_key, self.b_key)
2414
for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
2418
# for key in tsort.topo_sort(parent_map):
2419
parent_keys = parent_map[key]
2420
revision_id = key[-1]
2421
parent_ids = [k[-1] for k in parent_keys]
2422
self._weave.add_lines(revision_id, parent_ids,
2423
all_texts[revision_id])
2425
def plan_merge(self):
2426
"""Generate a 'plan' for merging the two revisions.
2428
This involves comparing their texts and determining the cause of
2429
differences. If text A has a line and text B does not, then either the
2430
line was added to text A, or it was deleted from B. Once the causes
2431
are combined, they are written out in the format described in
2432
VersionedFile.plan_merge
2434
if self._head_key is not None: # There was a single head
2435
if self._head_key == self.a_key:
2438
if self._head_key != self.b_key:
2439
raise AssertionError('There was an invalid head: %s != %s'
2440
% (self.b_key, self._head_key))
2442
head_rev = self._head_key[-1]
2443
lines = self.get_lines([head_rev])[head_rev]
2444
return ((plan, line) for line in lines)
2445
return self._weave.plan_merge(self.a_rev, self.b_rev)
2448
class _PlanLCAMerge(_PlanMergeBase):
2450
This merge algorithm differs from _PlanMerge in that:
2452
1. comparisons are done against LCAs only
2453
2. cases where a contested line is new versus one LCA but old versus
2454
another are marked as conflicts, by emitting the line as conflicted-a
2457
This is faster, and hopefully produces more useful output.
2460
def __init__(self, a_rev, b_rev, vf, key_prefix, graph):
2461
_PlanMergeBase.__init__(self, a_rev, b_rev, vf, key_prefix)
2462
lcas = graph.find_lca(key_prefix + (a_rev,), key_prefix + (b_rev,))
2465
if lca == _mod_revision.NULL_REVISION:
2468
self.lcas.add(lca[-1])
2469
for lca in self.lcas:
2470
if _mod_revision.is_null(lca):
2473
lca_lines = self.get_lines([lca])[lca]
2474
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
2476
blocks = list(matcher.get_matching_blocks())
2477
self._cached_matching_blocks[(a_rev, lca)] = blocks
2478
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
2480
blocks = list(matcher.get_matching_blocks())
2481
self._cached_matching_blocks[(b_rev, lca)] = blocks
2483
def _determine_status(self, revision_id, unique_line_numbers):
2484
"""Determines the status unique lines versus all lcas.
2486
Basically, determines why the line is unique to this revision.
2488
A line may be determined new, killed, or both.
2490
If a line is determined new, that means it was not present in at least
2491
one LCA, and is not present in the other merge revision.
2493
If a line is determined killed, that means the line was present in
2496
If a line is killed and new, this indicates that the two merge
2497
revisions contain differing conflict resolutions.
2499
:param revision_id: The id of the revision in which the lines are
2501
:param unique_line_numbers: The line numbers of unique lines.
2502
:return: a tuple of (new_this, killed_other)
2506
unique_line_numbers = set(unique_line_numbers)
2507
for lca in self.lcas:
2508
blocks = self._get_matching_blocks(revision_id, lca)
2509
unique_vs_lca, _ignored = self._unique_lines(blocks)
2510
new.update(unique_line_numbers.intersection(unique_vs_lca))
2511
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
bzrlib/merge.py
