1
# Copyright (C) 2005, 2006, 2008 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19
from itertools import chain
30
revision as _mod_revision,
34
from bzrlib.branch import Branch
35
from bzrlib.conflicts import ConflictList, Conflict
36
from bzrlib.errors import (BzrCommandError,
46
WorkingTreeNotRevision,
49
from bzrlib.graph import Graph
50
from bzrlib.merge3 import Merge3
51
from bzrlib.osutils import rename, pathjoin
52
from progress import DummyProgress, ProgressPhase
53
from bzrlib.revision import (NULL_REVISION, ensure_null)
54
from bzrlib.textfile import check_text_lines
55
from bzrlib.trace import mutter, warning, note, is_quiet
56
from bzrlib.transform import (TransformPreview, TreeTransform,
57
resolve_conflicts, cook_conflicts,
58
conflict_pass, FinalPaths, create_by_entry,
59
unique_add, ROOT_PARENT)
60
from bzrlib.versionedfile import PlanWeaveMerge
63
# TODO: Report back as changes are merged in
66
def transform_tree(from_tree, to_tree, interesting_ids=None):
67
merge_inner(from_tree.branch, to_tree, from_tree, ignore_zero=True,
68
interesting_ids=interesting_ids, this_tree=from_tree)
72
def __init__(self, this_branch, other_tree=None, base_tree=None,
73
this_tree=None, pb=DummyProgress(), change_reporter=None,
74
recurse='down', revision_graph=None):
76
self.this_branch = this_branch
77
self.this_basis = _mod_revision.ensure_null(
78
this_branch.last_revision())
79
self.this_rev_id = None
80
self.this_tree = this_tree
81
self.this_revision_tree = None
82
self.this_basis_tree = None
83
self.other_tree = other_tree
84
self.other_branch = None
85
self.base_tree = base_tree
86
self.ignore_zero = False
87
self.backup_files = False
88
self.interesting_ids = None
89
self.interesting_files = None
90
self.show_base = False
91
self.reprocess = False
94
self.recurse = recurse
95
self.change_reporter = change_reporter
96
self._cached_trees = {}
97
self._revision_graph = revision_graph
98
self._base_is_ancestor = None
99
self._base_is_other_ancestor = None
100
self._is_criss_cross = None
101
self._lca_trees = None
104
def revision_graph(self):
105
if self._revision_graph is None:
106
self._revision_graph = self.this_branch.repository.get_graph()
107
return self._revision_graph
109
def _set_base_is_ancestor(self, value):
110
self._base_is_ancestor = value
112
def _get_base_is_ancestor(self):
113
if self._base_is_ancestor is None:
114
self._base_is_ancestor = self.revision_graph.is_ancestor(
115
self.base_rev_id, self.this_basis)
116
return self._base_is_ancestor
118
base_is_ancestor = property(_get_base_is_ancestor, _set_base_is_ancestor)
120
def _set_base_is_other_ancestor(self, value):
121
self._base_is_other_ancestor = value
123
def _get_base_is_other_ancestor(self):
124
if self._base_is_other_ancestor is None:
125
if self.other_basis is None:
127
self._base_is_other_ancestor = self.revision_graph.is_ancestor(
128
self.base_rev_id, self.other_basis)
129
return self._base_is_other_ancestor
131
base_is_other_ancestor = property(_get_base_is_other_ancestor,
132
_set_base_is_other_ancestor)
135
def from_uncommitted(tree, other_tree, pb):
136
"""Return a Merger for uncommitted changes in other_tree.
138
:param tree: The tree to merge into
139
:param other_tree: The tree to get uncommitted changes from
140
:param pb: A progress indicator
142
merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,
144
merger.base_rev_id = merger.base_tree.get_revision_id()
145
merger.other_rev_id = None
146
merger.other_basis = merger.base_rev_id
150
def from_mergeable(klass, tree, mergeable, pb):
151
"""Return a Merger for a bundle or merge directive.
153
:param tree: The tree to merge changes into
154
:param mergeable: A merge directive or bundle
155
:param pb: A progress indicator
157
mergeable.install_revisions(tree.branch.repository)
158
base_revision_id, other_revision_id, verified =\
159
mergeable.get_merge_request(tree.branch.repository)
160
revision_graph = tree.branch.repository.get_graph()
161
if base_revision_id is not None:
162
if (base_revision_id != _mod_revision.NULL_REVISION and
163
revision_graph.is_ancestor(
164
base_revision_id, tree.branch.last_revision())):
165
base_revision_id = None
167
warning('Performing cherrypick')
168
merger = klass.from_revision_ids(pb, tree, other_revision_id,
169
base_revision_id, revision_graph=
171
return merger, verified
174
def from_revision_ids(pb, tree, other, base=None, other_branch=None,
175
base_branch=None, revision_graph=None):
176
"""Return a Merger for revision-ids.
178
:param tree: The tree to merge changes into
179
:param other: The revision-id to use as OTHER
180
:param base: The revision-id to use as BASE. If not specified, will
182
:param other_branch: A branch containing the other revision-id. If
183
not supplied, tree.branch is used.
184
:param base_branch: A branch containing the base revision-id. If
185
not supplied, other_branch or tree.branch will be used.
186
:param revision_graph: If you have a revision_graph precomputed, pass
187
it in, otherwise it will be created for you.
188
:param pb: A progress indicator
190
merger = Merger(tree.branch, this_tree=tree, pb=pb,
191
revision_graph=revision_graph)
192
if other_branch is None:
193
other_branch = tree.branch
194
merger.set_other_revision(other, other_branch)
198
if base_branch is None:
199
base_branch = other_branch
200
merger.set_base_revision(base, base_branch)
203
def revision_tree(self, revision_id, branch=None):
204
if revision_id not in self._cached_trees:
206
branch = self.this_branch
208
tree = self.this_tree.revision_tree(revision_id)
209
except errors.NoSuchRevisionInTree:
210
tree = branch.repository.revision_tree(revision_id)
211
self._cached_trees[revision_id] = tree
212
return self._cached_trees[revision_id]
214
def _get_tree(self, treespec, possible_transports=None):
215
from bzrlib import workingtree
216
location, revno = treespec
218
tree = workingtree.WorkingTree.open_containing(location)[0]
219
return tree.branch, tree
220
branch = Branch.open_containing(location, possible_transports)[0]
222
revision_id = branch.last_revision()
224
revision_id = branch.get_rev_id(revno)
225
revision_id = ensure_null(revision_id)
226
return branch, self.revision_tree(revision_id, branch)
228
def ensure_revision_trees(self):
229
if self.this_revision_tree is None:
230
self.this_basis_tree = self.revision_tree(self.this_basis)
231
if self.this_basis == self.this_rev_id:
232
self.this_revision_tree = self.this_basis_tree
234
if self.other_rev_id is None:
235
other_basis_tree = self.revision_tree(self.other_basis)
236
changes = other_basis_tree.changes_from(self.other_tree)
237
if changes.has_changed():
238
raise WorkingTreeNotRevision(self.this_tree)
239
other_rev_id = self.other_basis
240
self.other_tree = other_basis_tree
242
def file_revisions(self, file_id):
243
self.ensure_revision_trees()
244
def get_id(tree, file_id):
245
revision_id = tree.inventory[file_id].revision
247
if self.this_rev_id is None:
248
if self.this_basis_tree.get_file_sha1(file_id) != \
249
self.this_tree.get_file_sha1(file_id):
250
raise WorkingTreeNotRevision(self.this_tree)
252
trees = (self.this_basis_tree, self.other_tree)
253
return [get_id(tree, file_id) for tree in trees]
255
def check_basis(self, check_clean, require_commits=True):
256
if self.this_basis is None and require_commits is True:
257
raise BzrCommandError("This branch has no commits."
258
" (perhaps you would prefer 'bzr pull')")
261
if self.this_basis != self.this_rev_id:
262
raise errors.UncommittedChanges(self.this_tree)
264
def compare_basis(self):
266
basis_tree = self.revision_tree(self.this_tree.last_revision())
267
except errors.NoSuchRevision:
268
basis_tree = self.this_tree.basis_tree()
269
changes = self.this_tree.changes_from(basis_tree)
270
if not changes.has_changed():
271
self.this_rev_id = self.this_basis
273
def set_interesting_files(self, file_list):
274
self.interesting_files = file_list
276
def set_pending(self):
277
if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:
281
def _add_parent(self):
282
new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
283
new_parent_trees = []
284
for revision_id in new_parents:
286
tree = self.revision_tree(revision_id)
287
except errors.NoSuchRevision:
291
new_parent_trees.append((revision_id, tree))
293
self.this_tree.set_parent_trees(new_parent_trees,
294
allow_leftmost_as_ghost=True)
296
for _revision_id, tree in new_parent_trees:
300
def set_other(self, other_revision, possible_transports=None):
301
"""Set the revision and tree to merge from.
303
This sets the other_tree, other_rev_id, other_basis attributes.
305
:param other_revision: The [path, revision] list to merge from.
307
self.other_branch, self.other_tree = self._get_tree(other_revision,
309
if other_revision[1] == -1:
310
self.other_rev_id = _mod_revision.ensure_null(
311
self.other_branch.last_revision())
312
if _mod_revision.is_null(self.other_rev_id):
313
raise NoCommits(self.other_branch)
314
self.other_basis = self.other_rev_id
315
elif other_revision[1] is not None:
316
self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
317
self.other_basis = self.other_rev_id
319
self.other_rev_id = None
320
self.other_basis = self.other_branch.last_revision()
321
if self.other_basis is None:
322
raise NoCommits(self.other_branch)
323
if self.other_rev_id is not None:
324
self._cached_trees[self.other_rev_id] = self.other_tree
325
self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)
327
def set_other_revision(self, revision_id, other_branch):
328
"""Set 'other' based on a branch and revision id
330
:param revision_id: The revision to use for a tree
331
:param other_branch: The branch containing this tree
333
self.other_rev_id = revision_id
334
self.other_branch = other_branch
335
self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
336
self.other_tree = self.revision_tree(revision_id)
337
self.other_basis = revision_id
339
def set_base_revision(self, revision_id, branch):
340
"""Set 'base' based on a branch and revision id
342
:param revision_id: The revision to use for a tree
343
:param branch: The branch containing this tree
345
self.base_rev_id = revision_id
346
self.base_branch = branch
347
self._maybe_fetch(branch, self.this_branch, revision_id)
348
self.base_tree = self.revision_tree(revision_id)
350
def _maybe_fetch(self, source, target, revision_id):
351
if not source.repository.has_same_location(target.repository):
352
target.fetch(source, revision_id)
355
revisions = [ensure_null(self.this_basis),
356
ensure_null(self.other_basis)]
357
if NULL_REVISION in revisions:
358
self.base_rev_id = NULL_REVISION
359
self.base_tree = self.revision_tree(self.base_rev_id)
360
self._is_criss_cross = False
362
lcas = self.revision_graph.find_lca(revisions[0], revisions[1])
363
self._is_criss_cross = False
365
self.base_rev_id = NULL_REVISION
367
self.base_rev_id = list(lcas)[0]
368
else: # len(lcas) > 1
370
# find_unique_lca can only handle 2 nodes, so we have to
371
# start back at the beginning. It is a shame to traverse
372
# the graph again, but better than re-implementing
374
self.base_rev_id = self.revision_graph.find_unique_lca(
375
revisions[0], revisions[1])
377
self.base_rev_id = self.revision_graph.find_unique_lca(
379
self._is_criss_cross = True
380
if self.base_rev_id == NULL_REVISION:
381
raise UnrelatedBranches()
382
if self._is_criss_cross:
383
warning('Warning: criss-cross merge encountered. See bzr'
384
' help criss-cross.')
385
interesting_revision_ids = [self.base_rev_id]
386
interesting_revision_ids.extend(lcas)
387
interesting_trees = dict((t.get_revision_id(), t)
388
for t in self.this_branch.repository.revision_trees(
389
interesting_revision_ids))
390
self._cached_trees.update(interesting_trees)
391
self.base_tree = interesting_trees.pop(self.base_rev_id)
392
sorted_lca_keys = self.revision_graph.find_merge_order(
394
self._lca_trees = [interesting_trees[key]
395
for key in sorted_lca_keys]
397
self.base_tree = self.revision_tree(self.base_rev_id)
398
self.base_is_ancestor = True
399
self.base_is_other_ancestor = True
401
def set_base(self, base_revision):
402
"""Set the base revision to use for the merge.
404
:param base_revision: A 2-list containing a path and revision number.
406
mutter("doing merge() with no base_revision specified")
407
if base_revision == [None, None]:
410
base_branch, self.base_tree = self._get_tree(base_revision)
411
if base_revision[1] == -1:
412
self.base_rev_id = base_branch.last_revision()
413
elif base_revision[1] is None:
414
self.base_rev_id = _mod_revision.NULL_REVISION
416
self.base_rev_id = _mod_revision.ensure_null(
417
base_branch.get_rev_id(base_revision[1]))
418
self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
420
def make_merger(self):
421
kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
422
'other_tree': self.other_tree,
423
'interesting_ids': self.interesting_ids,
424
'interesting_files': self.interesting_files,
427
if self.merge_type.requires_base:
428
kwargs['base_tree'] = self.base_tree
429
if self.merge_type.supports_reprocess:
430
kwargs['reprocess'] = self.reprocess
432
raise BzrError("Conflict reduction is not supported for merge"
433
" type %s." % self.merge_type)
434
if self.merge_type.supports_show_base:
435
kwargs['show_base'] = self.show_base
437
raise BzrError("Showing base is not supported for this"
438
" merge type. %s" % self.merge_type)
439
if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
440
and not self.base_is_other_ancestor):
441
raise errors.CannotReverseCherrypick()
442
if self.merge_type.supports_cherrypick:
443
kwargs['cherrypick'] = (not self.base_is_ancestor or
444
not self.base_is_other_ancestor)
445
if self._is_criss_cross and getattr(self.merge_type,
446
'supports_lca_trees', False):
447
kwargs['lca_trees'] = self._lca_trees
448
return self.merge_type(pb=self._pb,
449
change_reporter=self.change_reporter,
452
def _do_merge_to(self, merge):
454
if self.recurse == 'down':
455
for relpath, file_id in self.this_tree.iter_references():
456
sub_tree = self.this_tree.get_nested_tree(file_id, relpath)
457
other_revision = self.other_tree.get_reference_revision(
459
if other_revision == sub_tree.last_revision():
461
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
462
sub_merge.merge_type = self.merge_type
463
other_branch = self.other_branch.reference_parent(file_id, relpath)
464
sub_merge.set_other_revision(other_revision, other_branch)
465
base_revision = self.base_tree.get_reference_revision(file_id)
466
sub_merge.base_tree = \
467
sub_tree.branch.repository.revision_tree(base_revision)
468
sub_merge.base_rev_id = base_revision
472
self.this_tree.lock_tree_write()
474
if self.base_tree is not None:
475
self.base_tree.lock_read()
477
if self.other_tree is not None:
478
self.other_tree.lock_read()
480
merge = self.make_merger()
481
self._do_merge_to(merge)
483
if self.other_tree is not None:
484
self.other_tree.unlock()
486
if self.base_tree is not None:
487
self.base_tree.unlock()
489
self.this_tree.unlock()
490
if len(merge.cooked_conflicts) == 0:
491
if not self.ignore_zero and not is_quiet():
492
note("All changes applied successfully.")
494
note("%d conflicts encountered." % len(merge.cooked_conflicts))
496
return len(merge.cooked_conflicts)
499
class _InventoryNoneEntry(object):
500
"""This represents an inventory entry which *isn't there*.
502
It simplifies the merging logic if we always have an InventoryEntry, even
503
if it isn't actually present
510
symlink_target = None
513
_none_entry = _InventoryNoneEntry()
516
class Merge3Merger(object):
517
"""Three-way merger that uses the merge3 text merger"""
519
supports_reprocess = True
520
supports_show_base = True
521
history_based = False
522
supports_cherrypick = True
523
supports_reverse_cherrypick = True
524
winner_idx = {"this": 2, "other": 1, "conflict": 1}
525
supports_lca_trees = True
527
def __init__(self, working_tree, this_tree, base_tree, other_tree,
528
interesting_ids=None, reprocess=False, show_base=False,
529
pb=DummyProgress(), pp=None, change_reporter=None,
530
interesting_files=None, do_merge=True,
531
cherrypick=False, lca_trees=None):
532
"""Initialize the merger object and perform the merge.
534
:param working_tree: The working tree to apply the merge to
535
:param this_tree: The local tree in the merge operation
536
:param base_tree: The common tree in the merge operation
537
:param other_tree: The other other tree to merge changes from
538
:param interesting_ids: The file_ids of files that should be
539
participate in the merge. May not be combined with
541
:param: reprocess If True, perform conflict-reduction processing.
542
:param show_base: If True, show the base revision in text conflicts.
543
(incompatible with reprocess)
544
:param pb: A Progress bar
545
:param pp: A ProgressPhase object
546
:param change_reporter: An object that should report changes made
547
:param interesting_files: The tree-relative paths of files that should
548
participate in the merge. If these paths refer to directories,
549
the contents of those directories will also be included. May not
550
be combined with interesting_ids. If neither interesting_files nor
551
interesting_ids is specified, all files may participate in the
553
:param lca_trees: Can be set to a dictionary of {revision_id:rev_tree}
554
if the ancestry was found to include a criss-cross merge.
555
Otherwise should be None.
557
object.__init__(self)
558
if interesting_files is not None and interesting_ids is not None:
560
'specify either interesting_ids or interesting_files')
561
self.interesting_ids = interesting_ids
562
self.interesting_files = interesting_files
563
self.this_tree = working_tree
564
self.base_tree = base_tree
565
self.other_tree = other_tree
566
self._raw_conflicts = []
567
self.cooked_conflicts = []
568
self.reprocess = reprocess
569
self.show_base = show_base
570
self._lca_trees = lca_trees
571
# Uncommenting this will change the default algorithm to always use
572
# _entries_lca. This can be useful for running the test suite and
573
# making sure we haven't missed any corner cases.
574
# if lca_trees is None:
575
# self._lca_trees = [self.base_tree]
578
self.change_reporter = change_reporter
579
self.cherrypick = cherrypick
581
self.pp = ProgressPhase("Merge phase", 3, self.pb)
586
self.this_tree.lock_tree_write()
587
self.base_tree.lock_read()
588
self.other_tree.lock_read()
589
self.tt = TreeTransform(self.this_tree, self.pb)
592
self._compute_transform()
594
results = self.tt.apply(no_conflicts=True)
595
self.write_modified(results)
597
self.this_tree.add_conflicts(self.cooked_conflicts)
598
except UnsupportedOperation:
602
self.other_tree.unlock()
603
self.base_tree.unlock()
604
self.this_tree.unlock()
607
def make_preview_transform(self):
608
self.base_tree.lock_read()
609
self.other_tree.lock_read()
610
self.tt = TransformPreview(self.this_tree)
613
self._compute_transform()
616
self.other_tree.unlock()
617
self.base_tree.unlock()
621
def _compute_transform(self):
622
if self._lca_trees is None:
623
entries = self._entries3()
624
resolver = self._three_way
626
entries = self._entries_lca()
627
resolver = self._lca_multi_way
628
child_pb = ui.ui_factory.nested_progress_bar()
630
for num, (file_id, changed, parents3, names3,
631
executable3) in enumerate(entries):
632
child_pb.update('Preparing file merge', num, len(entries))
633
self._merge_names(file_id, parents3, names3, resolver=resolver)
635
file_status = self.merge_contents(file_id)
637
file_status = 'unmodified'
638
self._merge_executable(file_id,
639
executable3, file_status, resolver=resolver)
644
child_pb = ui.ui_factory.nested_progress_bar()
646
fs_conflicts = resolve_conflicts(self.tt, child_pb,
647
lambda t, c: conflict_pass(t, c, self.other_tree))
650
if self.change_reporter is not None:
651
from bzrlib import delta
652
delta.report_changes(
653
self.tt.iter_changes(), self.change_reporter)
654
self.cook_conflicts(fs_conflicts)
655
for conflict in self.cooked_conflicts:
659
"""Gather data about files modified between three trees.
661
Return a list of tuples of file_id, changed, parents3, names3,
662
executable3. changed is a boolean indicating whether the file contents
663
or kind were changed. parents3 is a tuple of parent ids for base,
664
other and this. names3 is a tuple of names for base, other and this.
665
executable3 is a tuple of execute-bit values for base, other and this.
668
iterator = self.other_tree.iter_changes(self.base_tree,
669
include_unchanged=True, specific_files=self.interesting_files,
670
extra_trees=[self.this_tree])
671
for (file_id, paths, changed, versioned, parents, names, kind,
672
executable) in iterator:
673
if (self.interesting_ids is not None and
674
file_id not in self.interesting_ids):
676
if file_id in self.this_tree.inventory:
677
entry = self.this_tree.inventory[file_id]
678
this_name = entry.name
679
this_parent = entry.parent_id
680
this_executable = entry.executable
684
this_executable = None
685
parents3 = parents + (this_parent,)
686
names3 = names + (this_name,)
687
executable3 = executable + (this_executable,)
688
result.append((file_id, changed, parents3, names3, executable3))
691
def _entries_lca(self):
692
"""Gather data about files modified between multiple trees.
694
This compares OTHER versus all LCA trees, and for interesting entries,
695
it then compares with THIS and BASE.
697
For the multi-valued entries, the format will be (BASE, [lca1, lca2])
698
:return: [(file_id, changed, parents, names, executable)]
699
file_id Simple file_id of the entry
700
changed Boolean, True if the kind or contents changed
702
parents ((base, [parent_id, in, lcas]), parent_id_other,
704
names ((base, [name, in, lcas]), name_in_other, name_in_this)
705
executable ((base, [exec, in, lcas]), exec_in_other, exec_in_this)
707
if self.interesting_files is not None:
708
lookup_trees = [self.this_tree, self.base_tree]
709
lookup_trees.extend(self._lca_trees)
710
# I think we should include the lca trees as well
711
interesting_ids = self.other_tree.paths2ids(self.interesting_files,
714
interesting_ids = self.interesting_ids
716
walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
718
base_inventory = self.base_tree.inventory
719
this_inventory = self.this_tree.inventory
720
for path, file_id, other_ie, lca_values in walker.iter_all():
721
# Is this modified at all from any of the other trees?
723
other_ie = _none_entry
724
if interesting_ids is not None and file_id not in interesting_ids:
727
# If other_revision is found in any of the lcas, that means this
728
# node is uninteresting. This is because when merging, if there are
729
# multiple heads(), we have to create a new node. So if we didn't,
730
# we know that the ancestry is linear, and that OTHER did not
732
# See doc/developers/lca_merge_resolution.txt for details
733
other_revision = other_ie.revision
734
if other_revision is not None:
735
# We can't use this shortcut when other_revision is None,
736
# because it may be None because things are WorkingTrees, and
737
# not because it is *actually* None.
738
is_unmodified = False
739
for lca_path, ie in lca_values:
740
if ie is not None and ie.revision == other_revision:
747
for lca_path, lca_ie in lca_values:
749
lca_entries.append(_none_entry)
751
lca_entries.append(lca_ie)
753
if file_id in base_inventory:
754
base_ie = base_inventory[file_id]
756
base_ie = _none_entry
758
if file_id in this_inventory:
759
this_ie = this_inventory[file_id]
761
this_ie = _none_entry
767
for lca_ie in lca_entries:
768
lca_kinds.append(lca_ie.kind)
769
lca_parent_ids.append(lca_ie.parent_id)
770
lca_names.append(lca_ie.name)
771
lca_executable.append(lca_ie.executable)
773
kind_winner = self._lca_multi_way(
774
(base_ie.kind, lca_kinds),
775
other_ie.kind, this_ie.kind)
776
parent_id_winner = self._lca_multi_way(
777
(base_ie.parent_id, lca_parent_ids),
778
other_ie.parent_id, this_ie.parent_id)
779
name_winner = self._lca_multi_way(
780
(base_ie.name, lca_names),
781
other_ie.name, this_ie.name)
783
content_changed = True
784
if kind_winner == 'this':
785
# No kind change in OTHER, see if there are *any* changes
786
if other_ie.kind == None:
787
# No content and 'this' wins the kind, so skip this?
790
elif other_ie.kind == 'directory':
791
if parent_id_winner == 'this' and name_winner == 'this':
792
# No change for this directory in OTHER, skip
794
content_changed = False
795
elif other_ie.kind == 'file':
796
def get_sha1(ie, tree):
797
if ie.kind != 'file':
799
return tree.get_file_sha1(file_id)
800
base_sha1 = get_sha1(base_ie, self.base_tree)
801
lca_sha1s = [get_sha1(ie, tree) for ie, tree
802
in zip(lca_entries, self._lca_trees)]
803
this_sha1 = get_sha1(this_ie, self.this_tree)
804
other_sha1 = get_sha1(other_ie, self.other_tree)
805
sha1_winner = self._lca_multi_way(
806
(base_sha1, lca_sha1s), other_sha1, this_sha1,
807
allow_overriding_lca=False)
808
exec_winner = self._lca_multi_way(
809
(base_ie.executable, lca_executable),
810
other_ie.executable, this_ie.executable)
811
if (parent_id_winner == 'this' and name_winner == 'this'
812
and sha1_winner == 'this' and exec_winner == 'this'):
813
# No kind, parent, name, exec, or content change for
814
# OTHER, so this node is not considered interesting
816
if sha1_winner == 'this':
817
content_changed = False
818
elif other_ie.kind == 'symlink':
819
def get_target(ie, tree):
820
if ie.kind != 'symlink':
822
return tree.get_symlink_target(file_id)
823
base_target = get_target(base_ie, self.base_tree)
824
lca_targets = [get_target(ie, tree) for ie, tree
825
in zip(lca_entries, self._lca_trees)]
826
this_target = get_target(this_ie, self.this_tree)
827
other_target = get_target(other_ie, self.other_tree)
828
target_winner = self._lca_multi_way(
829
(base_target, lca_targets),
830
other_target, this_target)
831
if (parent_id_winner == 'this' and name_winner == 'this'
832
and target_winner == 'this'):
833
# No kind, parent, name, or symlink target change
836
if target_winner == 'this':
837
content_changed = False
838
elif other_ie.kind == 'tree-reference':
839
# The 'changed' information seems to be handled at a higher
840
# level. At least, _entries3 returns False for content
841
# changed, even when at a new revision_id.
842
content_changed = False
843
if (parent_id_winner == 'this' and name_winner == 'this'):
844
# Nothing interesting
847
raise AssertionError('unhandled kind: %s' % other_ie.kind)
848
# XXX: We need to handle kind == 'symlink'
850
# If we have gotten this far, that means something has changed
851
result.append((file_id, content_changed,
852
((base_ie.parent_id, lca_parent_ids),
853
other_ie.parent_id, this_ie.parent_id),
854
((base_ie.name, lca_names),
855
other_ie.name, this_ie.name),
856
((base_ie.executable, lca_executable),
857
other_ie.executable, this_ie.executable)
864
self.tt.final_kind(self.tt.root)
866
self.tt.cancel_deletion(self.tt.root)
867
if self.tt.final_file_id(self.tt.root) is None:
868
self.tt.version_file(self.tt.tree_file_id(self.tt.root),
870
if self.other_tree.inventory.root is None:
872
other_root_file_id = self.other_tree.get_root_id()
873
other_root = self.tt.trans_id_file_id(other_root_file_id)
874
if other_root == self.tt.root:
877
self.tt.final_kind(other_root)
880
if self.other_tree.inventory.root.file_id in self.this_tree.inventory:
881
# the other tree's root is a non-root in the current tree
883
self.reparent_children(self.other_tree.inventory.root, self.tt.root)
884
self.tt.cancel_creation(other_root)
885
self.tt.cancel_versioning(other_root)
887
def reparent_children(self, ie, target):
888
for thing, child in ie.children.iteritems():
889
trans_id = self.tt.trans_id_file_id(child.file_id)
890
self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)
892
def write_modified(self, results):
894
for path in results.modified_paths:
895
file_id = self.this_tree.path2id(self.this_tree.relpath(path))
898
hash = self.this_tree.get_file_sha1(file_id)
901
modified_hashes[file_id] = hash
902
self.this_tree.set_merge_modified(modified_hashes)
905
def parent(entry, file_id):
906
"""Determine the parent for a file_id (used as a key method)"""
909
return entry.parent_id
912
def name(entry, file_id):
913
"""Determine the name for a file_id (used as a key method)"""
919
def contents_sha1(tree, file_id):
920
"""Determine the sha1 of the file contents (used as a key method)."""
921
if file_id not in tree:
923
return tree.get_file_sha1(file_id)
926
def executable(tree, file_id):
927
"""Determine the executability of a file-id (used as a key method)."""
928
if file_id not in tree:
930
if tree.kind(file_id) != "file":
932
return tree.is_executable(file_id)
935
def kind(tree, file_id):
936
"""Determine the kind of a file-id (used as a key method)."""
937
if file_id not in tree:
939
return tree.kind(file_id)
942
def _three_way(base, other, this):
943
#if base == other, either they all agree, or only THIS has changed.
946
elif this not in (base, other):
948
# "Ambiguous clean merge" -- both sides have made the same change.
951
# this == base: only other has changed.
956
def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
957
"""Consider LCAs when determining whether a change has occurred.
959
If LCAS are all identical, this is the same as a _three_way comparison.
961
:param bases: value in (BASE, [LCAS])
962
:param other: value in OTHER
963
:param this: value in THIS
964
:param allow_overriding_lca: If there is more than one unique lca
965
value, allow OTHER to override THIS if it has a new value, and
966
THIS only has an lca value, or vice versa. This is appropriate for
967
truly scalar values, not as much for non-scalars.
968
:return: 'this', 'other', or 'conflict' depending on whether an entry
971
# See doc/developers/lca_merge_resolution.txt for details about this
974
# Either Ambiguously clean, or nothing was actually changed. We
977
base_val, lca_vals = bases
978
# Remove 'base_val' from the lca_vals, because it is not interesting
979
filtered_lca_vals = [lca_val for lca_val in lca_vals
980
if lca_val != base_val]
981
if len(filtered_lca_vals) == 0:
982
return Merge3Merger._three_way(base_val, other, this)
984
unique_lca_vals = set(filtered_lca_vals)
985
if len(unique_lca_vals) == 1:
986
return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
988
if allow_overriding_lca:
989
if other in unique_lca_vals:
990
if this in unique_lca_vals:
991
# Each side picked a different lca, conflict
994
# This has a value which supersedes both lca values, and
995
# other only has an lca value
997
elif this in unique_lca_vals:
998
# OTHER has a value which supersedes both lca values, and this
999
# only has an lca value
1002
# At this point, the lcas disagree, and the tips disagree
1006
def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
1007
"""Do a three-way test on a scalar.
1008
Return "this", "other" or "conflict", depending whether a value wins.
1010
key_base = key(base_tree, file_id)
1011
key_other = key(other_tree, file_id)
1012
#if base == other, either they all agree, or only THIS has changed.
1013
if key_base == key_other:
1015
key_this = key(this_tree, file_id)
1016
# "Ambiguous clean merge"
1017
if key_this == key_other:
1019
elif key_this == key_base:
1024
def merge_names(self, file_id):
1025
def get_entry(tree):
1026
if file_id in tree.inventory:
1027
return tree.inventory[file_id]
1030
this_entry = get_entry(self.this_tree)
1031
other_entry = get_entry(self.other_tree)
1032
base_entry = get_entry(self.base_tree)
1033
entries = (base_entry, other_entry, this_entry)
1036
for entry in entries:
1039
parents.append(None)
1041
names.append(entry.name)
1042
parents.append(entry.parent_id)
1043
return self._merge_names(file_id, parents, names,
1044
resolver=self._three_way)
1046
def _merge_names(self, file_id, parents, names, resolver):
1047
"""Perform a merge on file_id names and parents"""
1048
base_name, other_name, this_name = names
1049
base_parent, other_parent, this_parent = parents
1051
name_winner = resolver(*names)
1053
parent_id_winner = resolver(*parents)
1054
if this_name is None:
1055
if name_winner == "this":
1056
name_winner = "other"
1057
if parent_id_winner == "this":
1058
parent_id_winner = "other"
1059
if name_winner == "this" and parent_id_winner == "this":
1061
if name_winner == "conflict":
1062
trans_id = self.tt.trans_id_file_id(file_id)
1063
self._raw_conflicts.append(('name conflict', trans_id,
1064
this_name, other_name))
1065
if parent_id_winner == "conflict":
1066
trans_id = self.tt.trans_id_file_id(file_id)
1067
self._raw_conflicts.append(('parent conflict', trans_id,
1068
this_parent, other_parent))
1069
if other_name is None:
1070
# it doesn't matter whether the result was 'other' or
1071
# 'conflict'-- if there's no 'other', we leave it alone.
1073
# if we get here, name_winner and parent_winner are set to safe values.
1074
trans_id = self.tt.trans_id_file_id(file_id)
1075
parent_id = parents[self.winner_idx[parent_id_winner]]
1076
if parent_id is not None:
1077
parent_trans_id = self.tt.trans_id_file_id(parent_id)
1078
self.tt.adjust_path(names[self.winner_idx[name_winner]],
1079
parent_trans_id, trans_id)
1081
def merge_contents(self, file_id):
1082
"""Performa a merge on file_id contents."""
1083
def contents_pair(tree):
1084
if file_id not in tree:
1086
kind = tree.kind(file_id)
1088
contents = tree.get_file_sha1(file_id)
1089
elif kind == "symlink":
1090
contents = tree.get_symlink_target(file_id)
1093
return kind, contents
1095
def contents_conflict():
1096
trans_id = self.tt.trans_id_file_id(file_id)
1097
name = self.tt.final_name(trans_id)
1098
parent_id = self.tt.final_parent(trans_id)
1099
if file_id in self.this_tree.inventory:
1100
self.tt.unversion_file(trans_id)
1101
if file_id in self.this_tree:
1102
self.tt.delete_contents(trans_id)
1103
file_group = self._dump_conflicts(name, parent_id, file_id,
1105
self._raw_conflicts.append(('contents conflict', file_group))
1107
# See SPOT run. run, SPOT, run.
1108
# So we're not QUITE repeating ourselves; we do tricky things with
1110
base_pair = contents_pair(self.base_tree)
1111
other_pair = contents_pair(self.other_tree)
1112
if base_pair == other_pair:
1113
# OTHER introduced no changes
1115
this_pair = contents_pair(self.this_tree)
1116
if this_pair == other_pair:
1117
# THIS and OTHER introduced the same changes
1120
trans_id = self.tt.trans_id_file_id(file_id)
1121
if this_pair == base_pair:
1122
# only OTHER introduced changes
1123
if file_id in self.this_tree:
1124
# Remove any existing contents
1125
self.tt.delete_contents(trans_id)
1126
if file_id in self.other_tree:
1127
# OTHER changed the file
1128
create_by_entry(self.tt,
1129
self.other_tree.inventory[file_id],
1130
self.other_tree, trans_id)
1131
if file_id not in self.this_tree.inventory:
1132
self.tt.version_file(file_id, trans_id)
1134
elif file_id in self.this_tree.inventory:
1135
# OTHER deleted the file
1136
self.tt.unversion_file(trans_id)
1138
#BOTH THIS and OTHER introduced changes; scalar conflict
1139
elif this_pair[0] == "file" and other_pair[0] == "file":
1140
# THIS and OTHER are both files, so text merge. Either
1141
# BASE is a file, or both converted to files, so at least we
1142
# have agreement that output should be a file.
1144
self.text_merge(file_id, trans_id)
1146
return contents_conflict()
1147
if file_id not in self.this_tree.inventory:
1148
self.tt.version_file(file_id, trans_id)
1150
self.tt.tree_kind(trans_id)
1151
self.tt.delete_contents(trans_id)
1156
# Scalar conflict, can't text merge. Dump conflicts
1157
return contents_conflict()
1159
def get_lines(self, tree, file_id):
1160
"""Return the lines in a file, or an empty list."""
1162
return tree.get_file(file_id).readlines()
1166
def text_merge(self, file_id, trans_id):
1167
"""Perform a three-way text merge on a file_id"""
1168
# it's possible that we got here with base as a different type.
1169
# if so, we just want two-way text conflicts.
1170
if file_id in self.base_tree and \
1171
self.base_tree.kind(file_id) == "file":
1172
base_lines = self.get_lines(self.base_tree, file_id)
1175
other_lines = self.get_lines(self.other_tree, file_id)
1176
this_lines = self.get_lines(self.this_tree, file_id)
1177
m3 = Merge3(base_lines, this_lines, other_lines,
1178
is_cherrypick=self.cherrypick)
1179
start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
1180
if self.show_base is True:
1181
base_marker = '|' * 7
1185
def iter_merge3(retval):
1186
retval["text_conflicts"] = False
1187
for line in m3.merge_lines(name_a = "TREE",
1188
name_b = "MERGE-SOURCE",
1189
name_base = "BASE-REVISION",
1190
start_marker=start_marker,
1191
base_marker=base_marker,
1192
reprocess=self.reprocess):
1193
if line.startswith(start_marker):
1194
retval["text_conflicts"] = True
1195
yield line.replace(start_marker, '<' * 7)
1199
merge3_iterator = iter_merge3(retval)
1200
self.tt.create_file(merge3_iterator, trans_id)
1201
if retval["text_conflicts"] is True:
1202
self._raw_conflicts.append(('text conflict', trans_id))
1203
name = self.tt.final_name(trans_id)
1204
parent_id = self.tt.final_parent(trans_id)
1205
file_group = self._dump_conflicts(name, parent_id, file_id,
1206
this_lines, base_lines,
1208
file_group.append(trans_id)
1210
def _dump_conflicts(self, name, parent_id, file_id, this_lines=None,
1211
base_lines=None, other_lines=None, set_version=False,
1213
"""Emit conflict files.
1214
If this_lines, base_lines, or other_lines are omitted, they will be
1215
determined automatically. If set_version is true, the .OTHER, .THIS
1216
or .BASE (in that order) will be created as versioned files.
1218
data = [('OTHER', self.other_tree, other_lines),
1219
('THIS', self.this_tree, this_lines)]
1221
data.append(('BASE', self.base_tree, base_lines))
1224
for suffix, tree, lines in data:
1226
trans_id = self._conflict_file(name, parent_id, tree, file_id,
1228
file_group.append(trans_id)
1229
if set_version and not versioned:
1230
self.tt.version_file(file_id, trans_id)
1234
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
1236
"""Emit a single conflict file."""
1237
name = name + '.' + suffix
1238
trans_id = self.tt.create_path(name, parent_id)
1239
entry = tree.inventory[file_id]
1240
create_by_entry(self.tt, entry, tree, trans_id, lines)
1243
def merge_executable(self, file_id, file_status):
1244
"""Perform a merge on the execute bit."""
1245
executable = [self.executable(t, file_id) for t in (self.base_tree,
1246
self.other_tree, self.this_tree)]
1247
self._merge_executable(file_id, executable, file_status,
1248
resolver=self._three_way)
1250
def _merge_executable(self, file_id, executable, file_status,
1252
"""Perform a merge on the execute bit."""
1253
base_executable, other_executable, this_executable = executable
1254
if file_status == "deleted":
1256
winner = resolver(*executable)
1257
if winner == "conflict":
1258
# There must be a None in here, if we have a conflict, but we
1259
# need executability since file status was not deleted.
1260
if self.executable(self.other_tree, file_id) is None:
1264
if winner == 'this' and file_status != "modified":
1266
trans_id = self.tt.trans_id_file_id(file_id)
1268
if self.tt.final_kind(trans_id) != "file":
1272
if winner == "this":
1273
executability = this_executable
1275
if file_id in self.other_tree:
1276
executability = other_executable
1277
elif file_id in self.this_tree:
1278
executability = this_executable
1279
elif file_id in self.base_tree:
1280
executability = base_executable
1281
if executability is not None:
1282
trans_id = self.tt.trans_id_file_id(file_id)
1283
self.tt.set_executability(executability, trans_id)
1285
def cook_conflicts(self, fs_conflicts):
1286
"""Convert all conflicts into a form that doesn't depend on trans_id"""
1287
from conflicts import Conflict
1289
self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
1290
fp = FinalPaths(self.tt)
1291
for conflict in self._raw_conflicts:
1292
conflict_type = conflict[0]
1293
if conflict_type in ('name conflict', 'parent conflict'):
1294
trans_id = conflict[1]
1295
conflict_args = conflict[2:]
1296
if trans_id not in name_conflicts:
1297
name_conflicts[trans_id] = {}
1298
unique_add(name_conflicts[trans_id], conflict_type,
1300
if conflict_type == 'contents conflict':
1301
for trans_id in conflict[1]:
1302
file_id = self.tt.final_file_id(trans_id)
1303
if file_id is not None:
1305
path = fp.get_path(trans_id)
1306
for suffix in ('.BASE', '.THIS', '.OTHER'):
1307
if path.endswith(suffix):
1308
path = path[:-len(suffix)]
1310
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1311
self.cooked_conflicts.append(c)
1312
if conflict_type == 'text conflict':
1313
trans_id = conflict[1]
1314
path = fp.get_path(trans_id)
1315
file_id = self.tt.final_file_id(trans_id)
1316
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1317
self.cooked_conflicts.append(c)
1319
for trans_id, conflicts in name_conflicts.iteritems():
1321
this_parent, other_parent = conflicts['parent conflict']
1322
if this_parent == other_parent:
1323
raise AssertionError()
1325
this_parent = other_parent = \
1326
self.tt.final_file_id(self.tt.final_parent(trans_id))
1328
this_name, other_name = conflicts['name conflict']
1329
if this_name == other_name:
1330
raise AssertionError()
1332
this_name = other_name = self.tt.final_name(trans_id)
1333
other_path = fp.get_path(trans_id)
1334
if this_parent is not None and this_name is not None:
1335
this_parent_path = \
1336
fp.get_path(self.tt.trans_id_file_id(this_parent))
1337
this_path = pathjoin(this_parent_path, this_name)
1339
this_path = "<deleted>"
1340
file_id = self.tt.final_file_id(trans_id)
1341
c = Conflict.factory('path conflict', path=this_path,
1342
conflict_path=other_path, file_id=file_id)
1343
self.cooked_conflicts.append(c)
1344
self.cooked_conflicts.sort(key=Conflict.sort_key)
1347
class WeaveMerger(Merge3Merger):
1348
"""Three-way tree merger, text weave merger."""
1349
supports_reprocess = True
1350
supports_show_base = False
1351
supports_reverse_cherrypick = False
1352
history_based = True
1354
def _merged_lines(self, file_id):
1355
"""Generate the merged lines.
1356
There is no distinction between lines that are meant to contain <<<<<<<
1360
base = self.base_tree
1363
plan = self.this_tree.plan_file_merge(file_id, self.other_tree,
1365
if 'merge' in debug.debug_flags:
1367
trans_id = self.tt.trans_id_file_id(file_id)
1368
name = self.tt.final_name(trans_id) + '.plan'
1369
contents = ('%10s|%s' % l for l in plan)
1370
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1371
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1372
'>>>>>>> MERGE-SOURCE\n')
1373
return textmerge.merge_lines(self.reprocess)
1375
def text_merge(self, file_id, trans_id):
1376
"""Perform a (weave) text merge for a given file and file-id.
1377
If conflicts are encountered, .THIS and .OTHER files will be emitted,
1378
and a conflict will be noted.
1380
lines, conflicts = self._merged_lines(file_id)
1382
# Note we're checking whether the OUTPUT is binary in this case,
1383
# because we don't want to get into weave merge guts.
1384
check_text_lines(lines)
1385
self.tt.create_file(lines, trans_id)
1387
self._raw_conflicts.append(('text conflict', trans_id))
1388
name = self.tt.final_name(trans_id)
1389
parent_id = self.tt.final_parent(trans_id)
1390
file_group = self._dump_conflicts(name, parent_id, file_id,
1392
file_group.append(trans_id)
1395
class LCAMerger(WeaveMerger):
1397
def _merged_lines(self, file_id):
1398
"""Generate the merged lines.
1399
There is no distinction between lines that are meant to contain <<<<<<<
1403
base = self.base_tree
1406
plan = self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1408
if 'merge' in debug.debug_flags:
1410
trans_id = self.tt.trans_id_file_id(file_id)
1411
name = self.tt.final_name(trans_id) + '.plan'
1412
contents = ('%10s|%s' % l for l in plan)
1413
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1414
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1415
'>>>>>>> MERGE-SOURCE\n')
1416
return textmerge.merge_lines(self.reprocess)
1419
class Diff3Merger(Merge3Merger):
1420
"""Three-way merger using external diff3 for text merging"""
1422
def dump_file(self, temp_dir, name, tree, file_id):
1423
out_path = pathjoin(temp_dir, name)
1424
out_file = open(out_path, "wb")
1426
in_file = tree.get_file(file_id)
1427
for line in in_file:
1428
out_file.write(line)
1433
def text_merge(self, file_id, trans_id):
1434
"""Perform a diff3 merge using a specified file-id and trans-id.
1435
If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
1436
will be dumped, and a will be conflict noted.
1439
temp_dir = osutils.mkdtemp(prefix="bzr-")
1441
new_file = pathjoin(temp_dir, "new")
1442
this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
1443
base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
1444
other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
1445
status = bzrlib.patch.diff3(new_file, this, base, other)
1446
if status not in (0, 1):
1447
raise BzrError("Unhandled diff3 exit code")
1448
f = open(new_file, 'rb')
1450
self.tt.create_file(f, trans_id)
1454
name = self.tt.final_name(trans_id)
1455
parent_id = self.tt.final_parent(trans_id)
1456
self._dump_conflicts(name, parent_id, file_id)
1457
self._raw_conflicts.append(('text conflict', trans_id))
1459
osutils.rmtree(temp_dir)
1462
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
1464
merge_type=Merge3Merger,
1465
interesting_ids=None,
1469
interesting_files=None,
1472
change_reporter=None):
1473
"""Primary interface for merging.
1475
typical use is probably
1476
'merge_inner(branch, branch.get_revision_tree(other_revision),
1477
branch.get_revision_tree(base_revision))'
1479
if this_tree is None:
1480
raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
1481
"parameter as of bzrlib version 0.8.")
1482
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1483
pb=pb, change_reporter=change_reporter)
1484
merger.backup_files = backup_files
1485
merger.merge_type = merge_type
1486
merger.interesting_ids = interesting_ids
1487
merger.ignore_zero = ignore_zero
1488
if interesting_files:
1490
raise ValueError('Only supply interesting_ids'
1491
' or interesting_files')
1492
merger.interesting_files = interesting_files
1493
merger.show_base = show_base
1494
merger.reprocess = reprocess
1495
merger.other_rev_id = other_rev_id
1496
merger.other_basis = other_rev_id
1497
get_revision_id = getattr(base_tree, 'get_revision_id', None)
1498
if get_revision_id is None:
1499
get_revision_id = base_tree.last_revision
1500
merger.set_base_revision(get_revision_id(), this_branch)
1501
return merger.do_merge()
1503
def get_merge_type_registry():
1504
"""Merge type registry is in bzrlib.option to avoid circular imports.
1506
This method provides a sanctioned way to retrieve it.
1508
from bzrlib import option
1509
return option._merge_type_registry
1512
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1513
def status_a(revision, text):
1514
if revision in ancestors_b:
1515
return 'killed-b', text
1517
return 'new-a', text
1519
def status_b(revision, text):
1520
if revision in ancestors_a:
1521
return 'killed-a', text
1523
return 'new-b', text
1525
plain_a = [t for (a, t) in annotated_a]
1526
plain_b = [t for (a, t) in annotated_b]
1527
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
1528
blocks = matcher.get_matching_blocks()
1531
for ai, bi, l in blocks:
1532
# process all mismatched sections
1533
# (last mismatched section is handled because blocks always
1534
# includes a 0-length last block)
1535
for revision, text in annotated_a[a_cur:ai]:
1536
yield status_a(revision, text)
1537
for revision, text in annotated_b[b_cur:bi]:
1538
yield status_b(revision, text)
1539
# and now the matched section
1542
for text_a in plain_a[ai:a_cur]:
1543
yield "unchanged", text_a
1546
class _PlanMergeBase(object):
1548
def __init__(self, a_rev, b_rev, vf, key_prefix):
1551
:param a_rev: Revision-id of one revision to merge
1552
:param b_rev: Revision-id of the other revision to merge
1553
:param vf: A VersionedFiles containing both revisions
1554
:param key_prefix: A prefix for accessing keys in vf, typically
1560
self._last_lines = None
1561
self._last_lines_revision_id = None
1562
self._cached_matching_blocks = {}
1563
self._key_prefix = key_prefix
1564
self._precache_tip_lines()
1566
def _precache_tip_lines(self):
1567
lines = self.get_lines([self.a_rev, self.b_rev])
1568
self.lines_a = lines[self.a_rev]
1569
self.lines_b = lines[self.b_rev]
1571
def get_lines(self, revisions):
1572
"""Get lines for revisions from the backing VersionedFiles.
1574
:raises RevisionNotPresent: on absent texts.
1576
keys = [(self._key_prefix + (rev,)) for rev in revisions]
1578
for record in self.vf.get_record_stream(keys, 'unordered', True):
1579
if record.storage_kind == 'absent':
1580
raise errors.RevisionNotPresent(record.key, self.vf)
1581
result[record.key[-1]] = osutils.split_lines(
1582
record.get_bytes_as('fulltext'))
1585
def plan_merge(self):
1586
"""Generate a 'plan' for merging the two revisions.
1588
This involves comparing their texts and determining the cause of
1589
differences. If text A has a line and text B does not, then either the
1590
line was added to text A, or it was deleted from B. Once the causes
1591
are combined, they are written out in the format described in
1592
VersionedFile.plan_merge
1594
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1595
unique_a, unique_b = self._unique_lines(blocks)
1596
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
1597
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
1598
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
1600
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1603
for i, j, n in blocks:
1604
for a_index in range(last_i, i):
1605
if a_index in new_a:
1606
if a_index in killed_b:
1607
yield 'conflicted-a', self.lines_a[a_index]
1609
yield 'new-a', self.lines_a[a_index]
1611
yield 'killed-b', self.lines_a[a_index]
1612
for b_index in range(last_j, j):
1613
if b_index in new_b:
1614
if b_index in killed_a:
1615
yield 'conflicted-b', self.lines_b[b_index]
1617
yield 'new-b', self.lines_b[b_index]
1619
yield 'killed-a', self.lines_b[b_index]
1620
# handle common lines
1621
for a_index in range(i, i+n):
1622
yield 'unchanged', self.lines_a[a_index]
1626
def _get_matching_blocks(self, left_revision, right_revision):
1627
"""Return a description of which sections of two revisions match.
1629
See SequenceMatcher.get_matching_blocks
1631
cached = self._cached_matching_blocks.get((left_revision,
1633
if cached is not None:
1635
if self._last_lines_revision_id == left_revision:
1636
left_lines = self._last_lines
1637
right_lines = self.get_lines([right_revision])[right_revision]
1639
lines = self.get_lines([left_revision, right_revision])
1640
left_lines = lines[left_revision]
1641
right_lines = lines[right_revision]
1642
self._last_lines = right_lines
1643
self._last_lines_revision_id = right_revision
1644
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1646
return matcher.get_matching_blocks()
1648
def _unique_lines(self, matching_blocks):
1649
"""Analyse matching_blocks to determine which lines are unique
1651
:return: a tuple of (unique_left, unique_right), where the values are
1652
sets of line numbers of unique lines.
1658
for i, j, n in matching_blocks:
1659
unique_left.extend(range(last_i, i))
1660
unique_right.extend(range(last_j, j))
1663
return unique_left, unique_right
1666
def _subtract_plans(old_plan, new_plan):
1667
"""Remove changes from new_plan that came from old_plan.
1669
It is assumed that the difference between the old_plan and new_plan
1670
is their choice of 'b' text.
1672
All lines from new_plan that differ from old_plan are emitted
1673
verbatim. All lines from new_plan that match old_plan but are
1674
not about the 'b' revision are emitted verbatim.
1676
Lines that match and are about the 'b' revision are the lines we
1677
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
1678
is skipped entirely.
1680
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1683
for i, j, n in matcher.get_matching_blocks():
1684
for jj in range(last_j, j):
1686
for jj in range(j, j+n):
1687
plan_line = new_plan[jj]
1688
if plan_line[0] == 'new-b':
1690
elif plan_line[0] == 'killed-b':
1691
yield 'unchanged', plan_line[1]
1697
class _PlanMerge(_PlanMergeBase):
1698
"""Plan an annotate merge using on-the-fly annotation"""
1700
def __init__(self, a_rev, b_rev, vf, key_prefix):
1701
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
1702
self.a_key = self._key_prefix + (self.a_rev,)
1703
self.b_key = self._key_prefix + (self.b_rev,)
1704
self.graph = Graph(self.vf)
1705
heads = self.graph.heads((self.a_key, self.b_key))
1707
# one side dominates, so we can just return its values, yay for
1709
# Ideally we would know that before we get this far
1710
self._head_key = heads.pop()
1711
if self._head_key == self.a_key:
1715
mutter('found dominating revision for %s\n%s > %s', self.vf,
1716
self._head_key[-1], other)
1719
self._head_key = None
1722
def _precache_tip_lines(self):
1723
# Turn this into a no-op, because we will do this later
1726
def _find_recursive_lcas(self):
1727
"""Find all the ancestors back to a unique lca"""
1728
cur_ancestors = (self.a_key, self.b_key)
1729
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
1730
# rather than a key tuple. We will just map that directly to no common
1734
next_lcas = self.graph.find_lca(*cur_ancestors)
1735
# Map a plain NULL_REVISION to a simple no-ancestors
1736
if next_lcas == set([NULL_REVISION]):
1738
# Order the lca's based on when they were merged into the tip
1739
# While the actual merge portion of weave merge uses a set() of
1740
# active revisions, the order of insertion *does* effect the
1741
# implicit ordering of the texts.
1742
for rev_key in cur_ancestors:
1743
ordered_parents = tuple(self.graph.find_merge_order(rev_key,
1745
parent_map[rev_key] = ordered_parents
1746
if len(next_lcas) == 0:
1748
elif len(next_lcas) == 1:
1749
parent_map[list(next_lcas)[0]] = ()
1751
elif len(next_lcas) > 2:
1752
# More than 2 lca's, fall back to grabbing all nodes between
1753
# this and the unique lca.
1754
mutter('More than 2 LCAs, falling back to all nodes for:'
1755
' %s, %s\n=> %s', self.a_key, self.b_key, cur_ancestors)
1756
cur_lcas = next_lcas
1757
while len(cur_lcas) > 1:
1758
cur_lcas = self.graph.find_lca(*cur_lcas)
1759
if len(cur_lcas) == 0:
1760
# No common base to find, use the full ancestry
1763
unique_lca = list(cur_lcas)[0]
1764
if unique_lca == NULL_REVISION:
1765
# find_lca will return a plain 'NULL_REVISION' rather
1766
# than a key tuple when there is no common ancestor, we
1767
# prefer to just use None, because it doesn't confuse
1768
# _get_interesting_texts()
1770
parent_map.update(self._find_unique_parents(next_lcas,
1773
cur_ancestors = next_lcas
1776
def _find_unique_parents(self, tip_keys, base_key):
1777
"""Find ancestors of tip that aren't ancestors of base.
1779
:param tip_keys: Nodes that are interesting
1780
:param base_key: Cull all ancestors of this node
1781
:return: The parent map for all revisions between tip_keys and
1782
base_key. base_key will be included. References to nodes outside of
1783
the ancestor set will also be removed.
1785
# TODO: this would be simpler if find_unique_ancestors took a list
1786
# instead of a single tip, internally it supports it, but it
1787
# isn't a "backwards compatible" api change.
1788
if base_key is None:
1789
parent_map = dict(self.graph.iter_ancestry(tip_keys))
1790
# We remove NULL_REVISION because it isn't a proper tuple key, and
1791
# thus confuses things like _get_interesting_texts, and our logic
1792
# to add the texts into the memory weave.
1793
if NULL_REVISION in parent_map:
1794
parent_map.pop(NULL_REVISION)
1797
for tip in tip_keys:
1799
self.graph.find_unique_ancestors(tip, [base_key]))
1800
parent_map = self.graph.get_parent_map(interesting)
1801
parent_map[base_key] = ()
1802
culled_parent_map, child_map, tails = self._remove_external_references(
1804
# Remove all the tails but base_key
1805
if base_key is not None:
1806
tails.remove(base_key)
1807
self._prune_tails(culled_parent_map, child_map, tails)
1808
# Now remove all the uninteresting 'linear' regions
1809
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
1813
def _remove_external_references(parent_map):
1814
"""Remove references that go outside of the parent map.
1816
:param parent_map: Something returned from Graph.get_parent_map(keys)
1817
:return: (filtered_parent_map, child_map, tails)
1818
filtered_parent_map is parent_map without external references
1819
child_map is the {parent_key: [child_keys]} mapping
1820
tails is a list of nodes that do not have any parents in the map
1822
# TODO: The basic effect of this function seems more generic than
1823
# _PlanMerge. But the specific details of building a child_map,
1824
# and computing tails seems very specific to _PlanMerge.
1825
# Still, should this be in Graph land?
1826
filtered_parent_map = {}
1829
for key, parent_keys in parent_map.iteritems():
1830
culled_parent_keys = [p for p in parent_keys if p in parent_map]
1831
if not culled_parent_keys:
1833
for parent_key in culled_parent_keys:
1834
child_map.setdefault(parent_key, []).append(key)
1835
# TODO: Do we want to do this, it adds overhead for every node,
1836
# just to say that the node has no children
1837
child_map.setdefault(key, [])
1838
filtered_parent_map[key] = culled_parent_keys
1839
return filtered_parent_map, child_map, tails
1842
def _prune_tails(parent_map, child_map, tails_to_remove):
1843
"""Remove tails from the parent map.
1845
This will remove the supplied revisions until no more children have 0
1848
:param parent_map: A dict of {child: [parents]}, this dictionary will
1849
be modified in place.
1850
:param tails_to_remove: A list of tips that should be removed,
1851
this list will be consumed
1852
:param child_map: The reverse dict of parent_map ({parent: [children]})
1853
this dict will be modified
1854
:return: None, parent_map will be modified in place.
1856
while tails_to_remove:
1857
next = tails_to_remove.pop()
1858
parent_map.pop(next)
1859
children = child_map.pop(next)
1860
for child in children:
1861
child_parents = parent_map[child]
1862
child_parents.remove(next)
1863
if len(child_parents) == 0:
1864
tails_to_remove.append(child)
1866
def _get_interesting_texts(self, parent_map):
1867
"""Return a dict of texts we are interested in.
1869
Note that the input is in key tuples, but the output is in plain
1872
:param parent_map: The output from _find_recursive_lcas
1873
:return: A dict of {'revision_id':lines} as returned by
1874
_PlanMergeBase.get_lines()
1876
all_revision_keys = set(parent_map)
1877
all_revision_keys.add(self.a_key)
1878
all_revision_keys.add(self.b_key)
1880
# Everything else is in 'keys' but get_lines is in 'revision_ids'
1881
all_texts = self.get_lines([k[-1] for k in all_revision_keys])
1884
def _build_weave(self):
1885
from bzrlib import weave
1886
self._weave = weave.Weave(weave_name='in_memory_weave',
1887
allow_reserved=True)
1888
parent_map = self._find_recursive_lcas()
1890
all_texts = self._get_interesting_texts(parent_map)
1892
# Note: Unfortunately, the order given by topo_sort will effect the
1893
# ordering resolution in the output. Specifically, if you add A then B,
1894
# then in the output text A lines will show up before B lines. And, of
1895
# course, topo_sort doesn't guarantee any real ordering.
1896
# So we use merge_sort, and add a fake node on the tip.
1897
# This ensures that left-hand parents will always be inserted into the
1898
# weave before right-hand parents.
1899
tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
1900
parent_map[tip_key] = (self.a_key, self.b_key)
1902
for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
1906
# for key in tsort.topo_sort(parent_map):
1907
parent_keys = parent_map[key]
1908
revision_id = key[-1]
1909
parent_ids = [k[-1] for k in parent_keys]
1910
self._weave.add_lines(revision_id, parent_ids,
1911
all_texts[revision_id])
1913
def plan_merge(self):
1914
"""Generate a 'plan' for merging the two revisions.
1916
This involves comparing their texts and determining the cause of
1917
differences. If text A has a line and text B does not, then either the
1918
line was added to text A, or it was deleted from B. Once the causes
1919
are combined, they are written out in the format described in
1920
VersionedFile.plan_merge
1922
if self._head_key is not None: # There was a single head
1923
if self._head_key == self.a_key:
1926
if self._head_key != self.b_key:
1927
raise AssertionError('There was an invalid head: %s != %s'
1928
% (self.b_key, self._head_key))
1930
head_rev = self._head_key[-1]
1931
lines = self.get_lines([head_rev])[head_rev]
1932
return ((plan, line) for line in lines)
1933
return self._weave.plan_merge(self.a_rev, self.b_rev)
1936
class _PlanLCAMerge(_PlanMergeBase):
1938
This merge algorithm differs from _PlanMerge in that:
1939
1. comparisons are done against LCAs only
1940
2. cases where a contested line is new versus one LCA but old versus
1941
another are marked as conflicts, by emitting the line as conflicted-a
1944
This is faster, and hopefully produces more useful output.
1947
def __init__(self, a_rev, b_rev, vf, key_prefix, graph):
1948
_PlanMergeBase.__init__(self, a_rev, b_rev, vf, key_prefix)
1949
lcas = graph.find_lca(key_prefix + (a_rev,), key_prefix + (b_rev,))
1952
if lca == NULL_REVISION:
1955
self.lcas.add(lca[-1])
1956
for lca in self.lcas:
1957
if _mod_revision.is_null(lca):
1960
lca_lines = self.get_lines([lca])[lca]
1961
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
1963
blocks = list(matcher.get_matching_blocks())
1964
self._cached_matching_blocks[(a_rev, lca)] = blocks
1965
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
1967
blocks = list(matcher.get_matching_blocks())
1968
self._cached_matching_blocks[(b_rev, lca)] = blocks
1970
def _determine_status(self, revision_id, unique_line_numbers):
1971
"""Determines the status unique lines versus all lcas.
1973
Basically, determines why the line is unique to this revision.
1975
A line may be determined new, killed, or both.
1977
If a line is determined new, that means it was not present in at least
1978
one LCA, and is not present in the other merge revision.
1980
If a line is determined killed, that means the line was present in
1983
If a line is killed and new, this indicates that the two merge
1984
revisions contain differing conflict resolutions.
1985
:param revision_id: The id of the revision in which the lines are
1987
:param unique_line_numbers: The line numbers of unique lines.
1988
:return a tuple of (new_this, killed_other):
1992
unique_line_numbers = set(unique_line_numbers)
1993
for lca in self.lcas:
1994
blocks = self._get_matching_blocks(revision_id, lca)
1995
unique_vs_lca, _ignored = self._unique_lines(blocks)
1996
new.update(unique_line_numbers.intersection(unique_vs_lca))
1997
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
bzrlib/merge.py
