1
# Copyright (C) 2005, 2006 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
28
revision as _mod_revision,
30
from bzrlib.branch import Branch
31
from bzrlib.conflicts import ConflictList, Conflict
32
from bzrlib.errors import (BzrCommandError,
42
WorkingTreeNotRevision,
45
from bzrlib.merge3 import Merge3
46
from bzrlib.osutils import rename, pathjoin
47
from progress import DummyProgress, ProgressPhase
48
from bzrlib.revision import (NULL_REVISION, ensure_null)
49
from bzrlib.textfile import check_text_lines
50
from bzrlib.trace import mutter, warning, note
51
from bzrlib.transform import (TreeTransform, resolve_conflicts, cook_conflicts,
52
conflict_pass, FinalPaths, create_by_entry,
53
unique_add, ROOT_PARENT)
54
from bzrlib.versionedfile import PlanWeaveMerge
57
# TODO: Report back as changes are merged in
60
def transform_tree(from_tree, to_tree, interesting_ids=None):
61
merge_inner(from_tree.branch, to_tree, from_tree, ignore_zero=True,
62
interesting_ids=interesting_ids, this_tree=from_tree)
66
def __init__(self, this_branch, other_tree=None, base_tree=None,
67
this_tree=None, pb=DummyProgress(), change_reporter=None,
68
recurse='down', revision_graph=None):
70
assert this_tree is not None, "this_tree is required"
71
self.this_branch = this_branch
72
self.this_basis = _mod_revision.ensure_null(
73
this_branch.last_revision())
74
self.this_rev_id = None
75
self.this_tree = this_tree
76
self.this_revision_tree = None
77
self.this_basis_tree = None
78
self.other_tree = other_tree
79
self.other_branch = None
80
self.base_tree = base_tree
81
self.ignore_zero = False
82
self.backup_files = False
83
self.interesting_ids = None
84
self.interesting_files = None
85
self.show_base = False
86
self.reprocess = False
89
self.recurse = recurse
90
self.change_reporter = change_reporter
91
self._cached_trees = {}
92
self._revision_graph = revision_graph
93
self._base_is_ancestor = None
94
self._base_is_other_ancestor = None
97
def revision_graph(self):
98
if self._revision_graph is None:
99
self._revision_graph = self.this_branch.repository.get_graph()
100
return self._revision_graph
102
def _set_base_is_ancestor(self, value):
103
self._base_is_ancestor = value
105
def _get_base_is_ancestor(self):
106
if self._base_is_ancestor is None:
107
self._base_is_ancestor = self.revision_graph.is_ancestor(
108
self.base_rev_id, self.this_basis)
109
return self._base_is_ancestor
111
base_is_ancestor = property(_get_base_is_ancestor, _set_base_is_ancestor)
113
def _set_base_is_other_ancestor(self, value):
114
self._base_is_other_ancestor = value
116
def _get_base_is_other_ancestor(self):
117
if self._base_is_other_ancestor is None:
118
self.base_is_other_ancestor = self.revision_graph.is_ancestor(
119
self.base_rev_id, self.other_basis)
120
return self._base_is_other_ancestor
122
base_is_other_ancestor = property(_get_base_is_other_ancestor,
123
_set_base_is_other_ancestor)
126
def from_uncommitted(tree, other_tree, pb):
127
"""Return a Merger for uncommitted changes in other_tree.
129
:param tree: The tree to merge into
130
:param other_tree: The tree to get uncommitted changes from
131
:param pb: A progress indicator
133
merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,
135
merger.base_rev_id = merger.base_tree.get_revision_id()
136
merger.other_rev_id = None
137
merger.other_basis = merger.base_rev_id
141
def from_mergeable(klass, tree, mergeable, pb):
142
"""Return a Merger for a bundle or merge directive.
144
:param tree: The tree to merge changes into
145
:param mergeable: A merge directive or bundle
146
:param pb: A progress indicator
148
mergeable.install_revisions(tree.branch.repository)
149
base_revision_id, other_revision_id, verified =\
150
mergeable.get_merge_request(tree.branch.repository)
151
revision_graph = tree.branch.repository.get_graph()
152
if (base_revision_id != _mod_revision.NULL_REVISION and
153
revision_graph.is_ancestor(
154
base_revision_id, tree.branch.last_revision())):
155
base_revision_id = None
157
warning('Performing cherrypick')
158
merger = klass.from_revision_ids(pb, tree, other_revision_id,
159
base_revision_id, revision_graph=
161
return merger, verified
164
def from_revision_ids(pb, this, other, base=None, other_branch=None,
165
base_branch=None, revision_graph=None):
166
"""Return a Merger for revision-ids.
168
:param tree: The tree to merge changes into
169
:param other: The revision-id to use as OTHER
170
:param base: The revision-id to use as BASE. If not specified, will
172
:param other_branch: A branch containing the other revision-id. If
173
not supplied, this.branch is used.
174
:param base_branch: A branch containing the base revision-id. If
175
not supplied, other_branch or this.branch will be used.
176
:param pb: A progress indicator
178
merger = Merger(this.branch, this_tree=this, pb=pb,
179
revision_graph=revision_graph)
180
if other_branch is None:
181
other_branch = this.branch
182
merger.set_other_revision(other, other_branch)
186
if base_branch is None:
187
base_branch = other_branch
188
merger.set_base_revision(base, base_branch)
191
def revision_tree(self, revision_id, branch=None):
192
if revision_id not in self._cached_trees:
194
branch = self.this_branch
196
tree = self.this_tree.revision_tree(revision_id)
197
except errors.NoSuchRevisionInTree:
198
tree = branch.repository.revision_tree(revision_id)
199
self._cached_trees[revision_id] = tree
200
return self._cached_trees[revision_id]
202
def _get_tree(self, treespec, possible_transports=None):
203
from bzrlib import workingtree
204
location, revno = treespec
206
tree = workingtree.WorkingTree.open_containing(location)[0]
207
return tree.branch, tree
208
branch = Branch.open_containing(location, possible_transports)[0]
210
revision_id = branch.last_revision()
212
revision_id = branch.get_rev_id(revno)
213
revision_id = ensure_null(revision_id)
214
return branch, self.revision_tree(revision_id, branch)
216
def ensure_revision_trees(self):
217
if self.this_revision_tree is None:
218
self.this_basis_tree = self.revision_tree(self.this_basis)
219
if self.this_basis == self.this_rev_id:
220
self.this_revision_tree = self.this_basis_tree
222
if self.other_rev_id is None:
223
other_basis_tree = self.revision_tree(self.other_basis)
224
changes = other_basis_tree.changes_from(self.other_tree)
225
if changes.has_changed():
226
raise WorkingTreeNotRevision(self.this_tree)
227
other_rev_id = self.other_basis
228
self.other_tree = other_basis_tree
230
def file_revisions(self, file_id):
231
self.ensure_revision_trees()
232
def get_id(tree, file_id):
233
revision_id = tree.inventory[file_id].revision
234
assert revision_id is not None
236
if self.this_rev_id is None:
237
if self.this_basis_tree.get_file_sha1(file_id) != \
238
self.this_tree.get_file_sha1(file_id):
239
raise WorkingTreeNotRevision(self.this_tree)
241
trees = (self.this_basis_tree, self.other_tree)
242
return [get_id(tree, file_id) for tree in trees]
244
def check_basis(self, check_clean, require_commits=True):
245
if self.this_basis is None and require_commits is True:
246
raise BzrCommandError("This branch has no commits."
247
" (perhaps you would prefer 'bzr pull')")
250
if self.this_basis != self.this_rev_id:
251
raise errors.UncommittedChanges(self.this_tree)
253
def compare_basis(self):
255
basis_tree = self.revision_tree(self.this_tree.last_revision())
256
except errors.RevisionNotPresent:
257
basis_tree = self.this_tree.basis_tree()
258
changes = self.this_tree.changes_from(basis_tree)
259
if not changes.has_changed():
260
self.this_rev_id = self.this_basis
262
def set_interesting_files(self, file_list):
263
self.interesting_files = file_list
265
def set_pending(self):
266
if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:
270
def _add_parent(self):
271
new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
272
new_parent_trees = []
273
for revision_id in new_parents:
275
tree = self.revision_tree(revision_id)
276
except errors.RevisionNotPresent:
280
new_parent_trees.append((revision_id, tree))
282
self.this_tree.set_parent_trees(new_parent_trees,
283
allow_leftmost_as_ghost=True)
285
for _revision_id, tree in new_parent_trees:
289
def set_other(self, other_revision, possible_transports=None):
290
"""Set the revision and tree to merge from.
292
This sets the other_tree, other_rev_id, other_basis attributes.
294
:param other_revision: The [path, revision] list to merge from.
296
self.other_branch, self.other_tree = self._get_tree(other_revision,
298
if other_revision[1] == -1:
299
self.other_rev_id = _mod_revision.ensure_null(
300
self.other_branch.last_revision())
301
if _mod_revision.is_null(self.other_rev_id):
302
raise NoCommits(self.other_branch)
303
self.other_basis = self.other_rev_id
304
elif other_revision[1] is not None:
305
self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
306
self.other_basis = self.other_rev_id
308
self.other_rev_id = None
309
self.other_basis = self.other_branch.last_revision()
310
if self.other_basis is None:
311
raise NoCommits(self.other_branch)
312
if self.other_rev_id is not None:
313
self._cached_trees[self.other_rev_id] = self.other_tree
314
self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)
316
def set_other_revision(self, revision_id, other_branch):
317
"""Set 'other' based on a branch and revision id
319
:param revision_id: The revision to use for a tree
320
:param other_branch: The branch containing this tree
322
self.other_rev_id = revision_id
323
self.other_branch = other_branch
324
self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
325
self.other_tree = self.revision_tree(revision_id)
326
self.other_basis = revision_id
328
def set_base_revision(self, revision_id, branch):
329
"""Set 'base' based on a branch and revision id
331
:param revision_id: The revision to use for a tree
332
:param branch: The branch containing this tree
334
self.base_rev_id = revision_id
335
self.base_branch = branch
336
self._maybe_fetch(branch, self.this_branch, revision_id)
337
self.base_tree = self.revision_tree(revision_id)
339
def _maybe_fetch(self, source, target, revision_id):
340
if not source.repository.has_same_location(target.repository):
341
target.fetch(source, revision_id)
344
revisions = [ensure_null(self.this_basis),
345
ensure_null(self.other_basis)]
346
if NULL_REVISION in revisions:
347
self.base_rev_id = NULL_REVISION
349
self.base_rev_id, steps = self.revision_graph.find_unique_lca(
350
revisions[0], revisions[1], count_steps=True)
351
if self.base_rev_id == NULL_REVISION:
352
raise UnrelatedBranches()
354
warning('Warning: criss-cross merge encountered. See bzr'
355
' help criss-cross.')
356
self.base_tree = self.revision_tree(self.base_rev_id)
357
self.base_is_ancestor = True
358
self.base_is_other_ancestor = True
360
def set_base(self, base_revision):
361
"""Set the base revision to use for the merge.
363
:param base_revision: A 2-list containing a path and revision number.
365
mutter("doing merge() with no base_revision specified")
366
if base_revision == [None, None]:
369
base_branch, self.base_tree = self._get_tree(base_revision)
370
if base_revision[1] == -1:
371
self.base_rev_id = base_branch.last_revision()
372
elif base_revision[1] is None:
373
self.base_rev_id = _mod_revision.NULL_REVISION
375
self.base_rev_id = _mod_revision.ensure_null(
376
base_branch.get_rev_id(base_revision[1]))
377
self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
380
kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
381
'other_tree': self.other_tree,
382
'interesting_ids': self.interesting_ids,
383
'interesting_files': self.interesting_files,
385
if self.merge_type.requires_base:
386
kwargs['base_tree'] = self.base_tree
387
if self.merge_type.supports_reprocess:
388
kwargs['reprocess'] = self.reprocess
390
raise BzrError("Conflict reduction is not supported for merge"
391
" type %s." % self.merge_type)
392
if self.merge_type.supports_show_base:
393
kwargs['show_base'] = self.show_base
395
raise BzrError("Showing base is not supported for this"
396
" merge type. %s" % self.merge_type)
397
if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
398
and not self.base_is_other_ancestor):
399
raise errors.CannotReverseCherrypick()
400
if self.merge_type.history_based:
401
kwargs['cherrypick'] = (not self.base_is_ancestor or
402
not self.base_is_other_ancestor)
403
self.this_tree.lock_tree_write()
404
if self.base_tree is not None:
405
self.base_tree.lock_read()
406
if self.other_tree is not None:
407
self.other_tree.lock_read()
409
merge = self.merge_type(pb=self._pb,
410
change_reporter=self.change_reporter,
412
if self.recurse == 'down':
413
for path, file_id in self.this_tree.iter_references():
414
sub_tree = self.this_tree.get_nested_tree(file_id, path)
415
other_revision = self.other_tree.get_reference_revision(
417
if other_revision == sub_tree.last_revision():
419
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
420
sub_merge.merge_type = self.merge_type
421
relpath = self.this_tree.relpath(path)
422
other_branch = self.other_branch.reference_parent(file_id, relpath)
423
sub_merge.set_other_revision(other_revision, other_branch)
424
base_revision = self.base_tree.get_reference_revision(file_id)
425
sub_merge.base_tree = \
426
sub_tree.branch.repository.revision_tree(base_revision)
430
if self.other_tree is not None:
431
self.other_tree.unlock()
432
if self.base_tree is not None:
433
self.base_tree.unlock()
434
self.this_tree.unlock()
435
if len(merge.cooked_conflicts) == 0:
436
if not self.ignore_zero:
437
note("All changes applied successfully.")
439
note("%d conflicts encountered." % len(merge.cooked_conflicts))
441
return len(merge.cooked_conflicts)
444
class Merge3Merger(object):
445
"""Three-way merger that uses the merge3 text merger"""
447
supports_reprocess = True
448
supports_show_base = True
449
history_based = False
450
supports_reverse_cherrypick = True
451
winner_idx = {"this": 2, "other": 1, "conflict": 1}
453
def __init__(self, working_tree, this_tree, base_tree, other_tree,
454
interesting_ids=None, reprocess=False, show_base=False,
455
pb=DummyProgress(), pp=None, change_reporter=None,
456
interesting_files=None):
457
"""Initialize the merger object and perform the merge.
459
:param working_tree: The working tree to apply the merge to
460
:param this_tree: The local tree in the merge operation
461
:param base_tree: The common tree in the merge operation
462
:param other_tree: The other other tree to merge changes from
463
:param interesting_ids: The file_ids of files that should be
464
participate in the merge. May not be combined with
466
:param: reprocess If True, perform conflict-reduction processing.
467
:param show_base: If True, show the base revision in text conflicts.
468
(incompatible with reprocess)
469
:param pb: A Progress bar
470
:param pp: A ProgressPhase object
471
:param change_reporter: An object that should report changes made
472
:param interesting_files: The tree-relative paths of files that should
473
participate in the merge. If these paths refer to directories,
474
the contents of those directories will also be included. May not
475
be combined with interesting_ids. If neither interesting_files nor
476
interesting_ids is specified, all files may participate in the
479
object.__init__(self)
480
if interesting_files is not None:
481
assert interesting_ids is None
482
self.interesting_ids = interesting_ids
483
self.interesting_files = interesting_files
484
self.this_tree = working_tree
485
self.this_tree.lock_tree_write()
486
self.base_tree = base_tree
487
self.base_tree.lock_read()
488
self.other_tree = other_tree
489
self.other_tree.lock_read()
490
self._raw_conflicts = []
491
self.cooked_conflicts = []
492
self.reprocess = reprocess
493
self.show_base = show_base
496
self.change_reporter = change_reporter
498
self.pp = ProgressPhase("Merge phase", 3, self.pb)
500
self.tt = TreeTransform(working_tree, self.pb)
503
entries = self._entries3()
504
child_pb = ui.ui_factory.nested_progress_bar()
506
for num, (file_id, changed, parents3, names3,
507
executable3) in enumerate(entries):
508
child_pb.update('Preparing file merge', num, len(entries))
509
self._merge_names(file_id, parents3, names3)
511
file_status = self.merge_contents(file_id)
513
file_status = 'unmodified'
514
self._merge_executable(file_id,
515
executable3, file_status)
520
child_pb = ui.ui_factory.nested_progress_bar()
522
fs_conflicts = resolve_conflicts(self.tt, child_pb,
523
lambda t, c: conflict_pass(t, c, self.other_tree))
526
if change_reporter is not None:
527
from bzrlib import delta
528
delta.report_changes(self.tt._iter_changes(), change_reporter)
529
self.cook_conflicts(fs_conflicts)
530
for conflict in self.cooked_conflicts:
533
results = self.tt.apply(no_conflicts=True)
534
self.write_modified(results)
536
working_tree.add_conflicts(self.cooked_conflicts)
537
except UnsupportedOperation:
541
self.other_tree.unlock()
542
self.base_tree.unlock()
543
self.this_tree.unlock()
547
"""Gather data about files modified between three trees.
549
Return a list of tuples of file_id, changed, parents3, names3,
550
executable3. changed is a boolean indicating whether the file contents
551
or kind were changed. parents3 is a tuple of parent ids for base,
552
other and this. names3 is a tuple of names for base, other and this.
553
executable3 is a tuple of execute-bit values for base, other and this.
556
iterator = self.other_tree._iter_changes(self.base_tree,
557
include_unchanged=True, specific_files=self.interesting_files,
558
extra_trees=[self.this_tree])
559
for (file_id, paths, changed, versioned, parents, names, kind,
560
executable) in iterator:
561
if (self.interesting_ids is not None and
562
file_id not in self.interesting_ids):
564
if file_id in self.this_tree.inventory:
565
entry = self.this_tree.inventory[file_id]
566
this_name = entry.name
567
this_parent = entry.parent_id
568
this_executable = entry.executable
572
this_executable = None
573
parents3 = parents + (this_parent,)
574
names3 = names + (this_name,)
575
executable3 = executable + (this_executable,)
576
result.append((file_id, changed, parents3, names3, executable3))
581
self.tt.final_kind(self.tt.root)
583
self.tt.cancel_deletion(self.tt.root)
584
if self.tt.final_file_id(self.tt.root) is None:
585
self.tt.version_file(self.tt.tree_file_id(self.tt.root),
587
if self.other_tree.inventory.root is None:
589
other_root_file_id = self.other_tree.get_root_id()
590
other_root = self.tt.trans_id_file_id(other_root_file_id)
591
if other_root == self.tt.root:
594
self.tt.final_kind(other_root)
597
self.reparent_children(self.other_tree.inventory.root, self.tt.root)
598
self.tt.cancel_creation(other_root)
599
self.tt.cancel_versioning(other_root)
601
def reparent_children(self, ie, target):
602
for thing, child in ie.children.iteritems():
603
trans_id = self.tt.trans_id_file_id(child.file_id)
604
self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)
606
def write_modified(self, results):
608
for path in results.modified_paths:
609
file_id = self.this_tree.path2id(self.this_tree.relpath(path))
612
hash = self.this_tree.get_file_sha1(file_id)
615
modified_hashes[file_id] = hash
616
self.this_tree.set_merge_modified(modified_hashes)
619
def parent(entry, file_id):
620
"""Determine the parent for a file_id (used as a key method)"""
623
return entry.parent_id
626
def name(entry, file_id):
627
"""Determine the name for a file_id (used as a key method)"""
633
def contents_sha1(tree, file_id):
634
"""Determine the sha1 of the file contents (used as a key method)."""
635
if file_id not in tree:
637
return tree.get_file_sha1(file_id)
640
def executable(tree, file_id):
641
"""Determine the executability of a file-id (used as a key method)."""
642
if file_id not in tree:
644
if tree.kind(file_id) != "file":
646
return tree.is_executable(file_id)
649
def kind(tree, file_id):
650
"""Determine the kind of a file-id (used as a key method)."""
651
if file_id not in tree:
653
return tree.kind(file_id)
656
def _three_way(base, other, this):
657
#if base == other, either they all agree, or only THIS has changed.
660
elif this not in (base, other):
662
# "Ambiguous clean merge" -- both sides have made the same change.
665
# this == base: only other has changed.
670
def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
671
"""Do a three-way test on a scalar.
672
Return "this", "other" or "conflict", depending whether a value wins.
674
key_base = key(base_tree, file_id)
675
key_other = key(other_tree, file_id)
676
#if base == other, either they all agree, or only THIS has changed.
677
if key_base == key_other:
679
key_this = key(this_tree, file_id)
680
if key_this not in (key_base, key_other):
682
# "Ambiguous clean merge"
683
elif key_this == key_other:
686
assert key_this == key_base
689
def merge_names(self, file_id):
691
if file_id in tree.inventory:
692
return tree.inventory[file_id]
695
this_entry = get_entry(self.this_tree)
696
other_entry = get_entry(self.other_tree)
697
base_entry = get_entry(self.base_tree)
698
entries = (base_entry, other_entry, this_entry)
701
for entry in entries:
706
names.append(entry.name)
707
parents.append(entry.parent_id)
708
return self._merge_names(file_id, parents, names)
710
def _merge_names(self, file_id, parents, names):
711
"""Perform a merge on file_id names and parents"""
712
base_name, other_name, this_name = names
713
base_parent, other_parent, this_parent = parents
715
name_winner = self._three_way(*names)
717
parent_id_winner = self._three_way(*parents)
718
if this_name is None:
719
if name_winner == "this":
720
name_winner = "other"
721
if parent_id_winner == "this":
722
parent_id_winner = "other"
723
if name_winner == "this" and parent_id_winner == "this":
725
if name_winner == "conflict":
726
trans_id = self.tt.trans_id_file_id(file_id)
727
self._raw_conflicts.append(('name conflict', trans_id,
728
this_name, other_name))
729
if parent_id_winner == "conflict":
730
trans_id = self.tt.trans_id_file_id(file_id)
731
self._raw_conflicts.append(('parent conflict', trans_id,
732
this_parent, other_parent))
733
if other_name is None:
734
# it doesn't matter whether the result was 'other' or
735
# 'conflict'-- if there's no 'other', we leave it alone.
737
# if we get here, name_winner and parent_winner are set to safe values.
738
trans_id = self.tt.trans_id_file_id(file_id)
739
parent_id = parents[self.winner_idx[parent_id_winner]]
740
if parent_id is not None:
741
parent_trans_id = self.tt.trans_id_file_id(parent_id)
742
self.tt.adjust_path(names[self.winner_idx[name_winner]],
743
parent_trans_id, trans_id)
745
def merge_contents(self, file_id):
746
"""Performa a merge on file_id contents."""
747
def contents_pair(tree):
748
if file_id not in tree:
750
kind = tree.kind(file_id)
752
contents = tree.get_file_sha1(file_id)
753
elif kind == "symlink":
754
contents = tree.get_symlink_target(file_id)
757
return kind, contents
759
def contents_conflict():
760
trans_id = self.tt.trans_id_file_id(file_id)
761
name = self.tt.final_name(trans_id)
762
parent_id = self.tt.final_parent(trans_id)
763
if file_id in self.this_tree.inventory:
764
self.tt.unversion_file(trans_id)
765
if file_id in self.this_tree:
766
self.tt.delete_contents(trans_id)
767
file_group = self._dump_conflicts(name, parent_id, file_id,
769
self._raw_conflicts.append(('contents conflict', file_group))
771
# See SPOT run. run, SPOT, run.
772
# So we're not QUITE repeating ourselves; we do tricky things with
774
base_pair = contents_pair(self.base_tree)
775
other_pair = contents_pair(self.other_tree)
776
if base_pair == other_pair:
777
# OTHER introduced no changes
779
this_pair = contents_pair(self.this_tree)
780
if this_pair == other_pair:
781
# THIS and OTHER introduced the same changes
784
trans_id = self.tt.trans_id_file_id(file_id)
785
if this_pair == base_pair:
786
# only OTHER introduced changes
787
if file_id in self.this_tree:
788
# Remove any existing contents
789
self.tt.delete_contents(trans_id)
790
if file_id in self.other_tree:
791
# OTHER changed the file
792
create_by_entry(self.tt,
793
self.other_tree.inventory[file_id],
794
self.other_tree, trans_id)
795
if file_id not in self.this_tree.inventory:
796
self.tt.version_file(file_id, trans_id)
798
elif file_id in self.this_tree.inventory:
799
# OTHER deleted the file
800
self.tt.unversion_file(trans_id)
802
#BOTH THIS and OTHER introduced changes; scalar conflict
803
elif this_pair[0] == "file" and other_pair[0] == "file":
804
# THIS and OTHER are both files, so text merge. Either
805
# BASE is a file, or both converted to files, so at least we
806
# have agreement that output should be a file.
808
self.text_merge(file_id, trans_id)
810
return contents_conflict()
811
if file_id not in self.this_tree.inventory:
812
self.tt.version_file(file_id, trans_id)
814
self.tt.tree_kind(trans_id)
815
self.tt.delete_contents(trans_id)
820
# Scalar conflict, can't text merge. Dump conflicts
821
return contents_conflict()
823
def get_lines(self, tree, file_id):
824
"""Return the lines in a file, or an empty list."""
826
return tree.get_file(file_id).readlines()
830
def text_merge(self, file_id, trans_id):
831
"""Perform a three-way text merge on a file_id"""
832
# it's possible that we got here with base as a different type.
833
# if so, we just want two-way text conflicts.
834
if file_id in self.base_tree and \
835
self.base_tree.kind(file_id) == "file":
836
base_lines = self.get_lines(self.base_tree, file_id)
839
other_lines = self.get_lines(self.other_tree, file_id)
840
this_lines = self.get_lines(self.this_tree, file_id)
841
m3 = Merge3(base_lines, this_lines, other_lines)
842
start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
843
if self.show_base is True:
844
base_marker = '|' * 7
848
def iter_merge3(retval):
849
retval["text_conflicts"] = False
850
for line in m3.merge_lines(name_a = "TREE",
851
name_b = "MERGE-SOURCE",
852
name_base = "BASE-REVISION",
853
start_marker=start_marker,
854
base_marker=base_marker,
855
reprocess=self.reprocess):
856
if line.startswith(start_marker):
857
retval["text_conflicts"] = True
858
yield line.replace(start_marker, '<' * 7)
862
merge3_iterator = iter_merge3(retval)
863
self.tt.create_file(merge3_iterator, trans_id)
864
if retval["text_conflicts"] is True:
865
self._raw_conflicts.append(('text conflict', trans_id))
866
name = self.tt.final_name(trans_id)
867
parent_id = self.tt.final_parent(trans_id)
868
file_group = self._dump_conflicts(name, parent_id, file_id,
869
this_lines, base_lines,
871
file_group.append(trans_id)
873
def _dump_conflicts(self, name, parent_id, file_id, this_lines=None,
874
base_lines=None, other_lines=None, set_version=False,
876
"""Emit conflict files.
877
If this_lines, base_lines, or other_lines are omitted, they will be
878
determined automatically. If set_version is true, the .OTHER, .THIS
879
or .BASE (in that order) will be created as versioned files.
881
data = [('OTHER', self.other_tree, other_lines),
882
('THIS', self.this_tree, this_lines)]
884
data.append(('BASE', self.base_tree, base_lines))
887
for suffix, tree, lines in data:
889
trans_id = self._conflict_file(name, parent_id, tree, file_id,
891
file_group.append(trans_id)
892
if set_version and not versioned:
893
self.tt.version_file(file_id, trans_id)
897
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
899
"""Emit a single conflict file."""
900
name = name + '.' + suffix
901
trans_id = self.tt.create_path(name, parent_id)
902
entry = tree.inventory[file_id]
903
create_by_entry(self.tt, entry, tree, trans_id, lines)
906
def merge_executable(self, file_id, file_status):
907
"""Perform a merge on the execute bit."""
908
executable = [self.executable(t, file_id) for t in (self.base_tree,
909
self.other_tree, self.this_tree)]
910
self._merge_executable(file_id, executable, file_status)
912
def _merge_executable(self, file_id, executable, file_status):
913
"""Perform a merge on the execute bit."""
914
base_executable, other_executable, this_executable = executable
915
if file_status == "deleted":
917
trans_id = self.tt.trans_id_file_id(file_id)
919
if self.tt.final_kind(trans_id) != "file":
923
winner = self._three_way(*executable)
924
if winner == "conflict":
925
# There must be a None in here, if we have a conflict, but we
926
# need executability since file status was not deleted.
927
if self.executable(self.other_tree, file_id) is None:
932
if file_status == "modified":
933
executability = this_executable
934
if executability is not None:
935
trans_id = self.tt.trans_id_file_id(file_id)
936
self.tt.set_executability(executability, trans_id)
938
assert winner == "other"
939
if file_id in self.other_tree:
940
executability = other_executable
941
elif file_id in self.this_tree:
942
executability = this_executable
943
elif file_id in self.base_tree:
944
executability = base_executable
945
if executability is not None:
946
trans_id = self.tt.trans_id_file_id(file_id)
947
self.tt.set_executability(executability, trans_id)
949
def cook_conflicts(self, fs_conflicts):
950
"""Convert all conflicts into a form that doesn't depend on trans_id"""
951
from conflicts import Conflict
953
self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
954
fp = FinalPaths(self.tt)
955
for conflict in self._raw_conflicts:
956
conflict_type = conflict[0]
957
if conflict_type in ('name conflict', 'parent conflict'):
958
trans_id = conflict[1]
959
conflict_args = conflict[2:]
960
if trans_id not in name_conflicts:
961
name_conflicts[trans_id] = {}
962
unique_add(name_conflicts[trans_id], conflict_type,
964
if conflict_type == 'contents conflict':
965
for trans_id in conflict[1]:
966
file_id = self.tt.final_file_id(trans_id)
967
if file_id is not None:
969
path = fp.get_path(trans_id)
970
for suffix in ('.BASE', '.THIS', '.OTHER'):
971
if path.endswith(suffix):
972
path = path[:-len(suffix)]
974
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
975
self.cooked_conflicts.append(c)
976
if conflict_type == 'text conflict':
977
trans_id = conflict[1]
978
path = fp.get_path(trans_id)
979
file_id = self.tt.final_file_id(trans_id)
980
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
981
self.cooked_conflicts.append(c)
983
for trans_id, conflicts in name_conflicts.iteritems():
985
this_parent, other_parent = conflicts['parent conflict']
986
assert this_parent != other_parent
988
this_parent = other_parent = \
989
self.tt.final_file_id(self.tt.final_parent(trans_id))
991
this_name, other_name = conflicts['name conflict']
992
assert this_name != other_name
994
this_name = other_name = self.tt.final_name(trans_id)
995
other_path = fp.get_path(trans_id)
996
if this_parent is not None and this_name is not None:
998
fp.get_path(self.tt.trans_id_file_id(this_parent))
999
this_path = pathjoin(this_parent_path, this_name)
1001
this_path = "<deleted>"
1002
file_id = self.tt.final_file_id(trans_id)
1003
c = Conflict.factory('path conflict', path=this_path,
1004
conflict_path=other_path, file_id=file_id)
1005
self.cooked_conflicts.append(c)
1006
self.cooked_conflicts.sort(key=Conflict.sort_key)
1009
class WeaveMerger(Merge3Merger):
1010
"""Three-way tree merger, text weave merger."""
1011
supports_reprocess = True
1012
supports_show_base = False
1013
supports_reverse_cherrypick = False
1014
history_based = True
1016
def __init__(self, working_tree, this_tree, base_tree, other_tree,
1017
interesting_ids=None, pb=DummyProgress(), pp=None,
1018
reprocess=False, change_reporter=None,
1019
interesting_files=None, cherrypick=False):
1020
self.cherrypick = cherrypick
1021
super(WeaveMerger, self).__init__(working_tree, this_tree,
1022
base_tree, other_tree,
1023
interesting_ids=interesting_ids,
1024
pb=pb, pp=pp, reprocess=reprocess,
1025
change_reporter=change_reporter)
1027
def _merged_lines(self, file_id):
1028
"""Generate the merged lines.
1029
There is no distinction between lines that are meant to contain <<<<<<<
1033
base = self.base_tree
1036
plan = self.this_tree.plan_file_merge(file_id, self.other_tree,
1038
if 'merge' in debug.debug_flags:
1040
trans_id = self.tt.trans_id_file_id(file_id)
1041
name = self.tt.final_name(trans_id) + '.plan'
1042
contents = ('%10s|%s' % l for l in plan)
1043
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1044
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1045
'>>>>>>> MERGE-SOURCE\n')
1046
return textmerge.merge_lines(self.reprocess)
1048
def text_merge(self, file_id, trans_id):
1049
"""Perform a (weave) text merge for a given file and file-id.
1050
If conflicts are encountered, .THIS and .OTHER files will be emitted,
1051
and a conflict will be noted.
1053
lines, conflicts = self._merged_lines(file_id)
1055
# Note we're checking whether the OUTPUT is binary in this case,
1056
# because we don't want to get into weave merge guts.
1057
check_text_lines(lines)
1058
self.tt.create_file(lines, trans_id)
1060
self._raw_conflicts.append(('text conflict', trans_id))
1061
name = self.tt.final_name(trans_id)
1062
parent_id = self.tt.final_parent(trans_id)
1063
file_group = self._dump_conflicts(name, parent_id, file_id,
1065
file_group.append(trans_id)
1068
class LCAMerger(WeaveMerger):
1070
def _merged_lines(self, file_id):
1071
"""Generate the merged lines.
1072
There is no distinction between lines that are meant to contain <<<<<<<
1076
base = self.base_tree
1079
plan = self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1081
if 'merge' in debug.debug_flags:
1083
trans_id = self.tt.trans_id_file_id(file_id)
1084
name = self.tt.final_name(trans_id) + '.plan'
1085
contents = ('%10s|%s' % l for l in plan)
1086
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1087
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1088
'>>>>>>> MERGE-SOURCE\n')
1089
return textmerge.merge_lines(self.reprocess)
1092
class Diff3Merger(Merge3Merger):
1093
"""Three-way merger using external diff3 for text merging"""
1095
def dump_file(self, temp_dir, name, tree, file_id):
1096
out_path = pathjoin(temp_dir, name)
1097
out_file = open(out_path, "wb")
1099
in_file = tree.get_file(file_id)
1100
for line in in_file:
1101
out_file.write(line)
1106
def text_merge(self, file_id, trans_id):
1107
"""Perform a diff3 merge using a specified file-id and trans-id.
1108
If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
1109
will be dumped, and a will be conflict noted.
1112
temp_dir = osutils.mkdtemp(prefix="bzr-")
1114
new_file = pathjoin(temp_dir, "new")
1115
this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
1116
base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
1117
other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
1118
status = bzrlib.patch.diff3(new_file, this, base, other)
1119
if status not in (0, 1):
1120
raise BzrError("Unhandled diff3 exit code")
1121
f = open(new_file, 'rb')
1123
self.tt.create_file(f, trans_id)
1127
name = self.tt.final_name(trans_id)
1128
parent_id = self.tt.final_parent(trans_id)
1129
self._dump_conflicts(name, parent_id, file_id)
1130
self._raw_conflicts.append(('text conflict', trans_id))
1132
osutils.rmtree(temp_dir)
1135
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
1137
merge_type=Merge3Merger,
1138
interesting_ids=None,
1142
interesting_files=None,
1145
change_reporter=None):
1146
"""Primary interface for merging.
1148
typical use is probably
1149
'merge_inner(branch, branch.get_revision_tree(other_revision),
1150
branch.get_revision_tree(base_revision))'
1152
if this_tree is None:
1153
raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
1154
"parameter as of bzrlib version 0.8.")
1155
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1156
pb=pb, change_reporter=change_reporter)
1157
merger.backup_files = backup_files
1158
merger.merge_type = merge_type
1159
merger.interesting_ids = interesting_ids
1160
merger.ignore_zero = ignore_zero
1161
if interesting_files:
1162
assert not interesting_ids, ('Only supply interesting_ids'
1163
' or interesting_files')
1164
merger.interesting_files = interesting_files
1165
merger.show_base = show_base
1166
merger.reprocess = reprocess
1167
merger.other_rev_id = other_rev_id
1168
merger.other_basis = other_rev_id
1169
return merger.do_merge()
1171
def get_merge_type_registry():
1172
"""Merge type registry is in bzrlib.option to avoid circular imports.
1174
This method provides a sanctioned way to retrieve it.
1176
from bzrlib import option
1177
return option._merge_type_registry
1180
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1181
def status_a(revision, text):
1182
if revision in ancestors_b:
1183
return 'killed-b', text
1185
return 'new-a', text
1187
def status_b(revision, text):
1188
if revision in ancestors_a:
1189
return 'killed-a', text
1191
return 'new-b', text
1193
plain_a = [t for (a, t) in annotated_a]
1194
plain_b = [t for (a, t) in annotated_b]
1195
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
1196
blocks = matcher.get_matching_blocks()
1199
for ai, bi, l in blocks:
1200
# process all mismatched sections
1201
# (last mismatched section is handled because blocks always
1202
# includes a 0-length last block)
1203
for revision, text in annotated_a[a_cur:ai]:
1204
yield status_a(revision, text)
1205
for revision, text in annotated_b[b_cur:bi]:
1206
yield status_b(revision, text)
1208
# and now the matched section
1211
for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
1212
assert text_a == text_b
1213
yield "unchanged", text_a
1216
class _PlanMergeBase(object):
1218
def __init__(self, a_rev, b_rev, vf):
1221
:param a_rev: Revision-id of one revision to merge
1222
:param b_rev: Revision-id of the other revision to merge
1223
:param vf: A versionedfile containing both revisions
1227
self.lines_a = vf.get_lines(a_rev)
1228
self.lines_b = vf.get_lines(b_rev)
1230
self._last_lines = None
1231
self._last_lines_revision_id = None
1232
self._cached_matching_blocks = {}
1234
def plan_merge(self):
1235
"""Generate a 'plan' for merging the two revisions.
1237
This involves comparing their texts and determining the cause of
1238
differences. If text A has a line and text B does not, then either the
1239
line was added to text A, or it was deleted from B. Once the causes
1240
are combined, they are written out in the format described in
1241
VersionedFile.plan_merge
1243
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1244
unique_a, unique_b = self._unique_lines(blocks)
1245
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
1246
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
1247
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
1249
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1252
for i, j, n in blocks:
1253
for a_index in range(last_i, i):
1254
if a_index in new_a:
1255
if a_index in killed_b:
1256
yield 'conflicted-a', self.lines_a[a_index]
1258
yield 'new-a', self.lines_a[a_index]
1260
yield 'killed-b', self.lines_a[a_index]
1261
for b_index in range(last_j, j):
1262
if b_index in new_b:
1263
if b_index in killed_a:
1264
yield 'conflicted-b', self.lines_b[a_index]
1266
yield 'new-b', self.lines_b[b_index]
1268
yield 'killed-a', self.lines_b[b_index]
1269
# handle common lines
1270
for a_index in range(i, i+n):
1271
yield 'unchanged', self.lines_a[a_index]
1275
def _get_matching_blocks(self, left_revision, right_revision):
1276
"""Return a description of which sections of two revisions match.
1278
See SequenceMatcher.get_matching_blocks
1280
cached = self._cached_matching_blocks.get((left_revision,
1282
if cached is not None:
1284
if self._last_lines_revision_id == left_revision:
1285
left_lines = self._last_lines
1287
left_lines = self.vf.get_lines(left_revision)
1288
right_lines = self.vf.get_lines(right_revision)
1289
self._last_lines = right_lines
1290
self._last_lines_revision_id = right_revision
1291
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1293
return matcher.get_matching_blocks()
1295
def _unique_lines(self, matching_blocks):
1296
"""Analyse matching_blocks to determine which lines are unique
1298
:return: a tuple of (unique_left, unique_right), where the values are
1299
sets of line numbers of unique lines.
1305
for i, j, n in matching_blocks:
1306
unique_left.extend(range(last_i, i))
1307
unique_right.extend(range(last_j, j))
1310
return unique_left, unique_right
1313
def _subtract_plans(old_plan, new_plan):
1314
"""Remove changes from new_plan that came from old_plan.
1316
It is assumed that the difference between the old_plan and new_plan
1317
is their choice of 'b' text.
1319
All lines from new_plan that differ from old_plan are emitted
1320
verbatim. All lines from new_plan that match old_plan but are
1321
not about the 'b' revision are emitted verbatim.
1323
Lines that match and are about the 'b' revision are the lines we
1324
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
1325
is skipped entirely.
1327
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1330
for i, j, n in matcher.get_matching_blocks():
1331
for jj in range(last_j, j):
1333
for jj in range(j, j+n):
1334
plan_line = new_plan[jj]
1335
if plan_line[0] == 'new-b':
1337
elif plan_line[0] == 'killed-b':
1338
yield 'unchanged', plan_line[1]
1344
class _PlanMerge(_PlanMergeBase):
1345
"""Plan an annotate merge using on-the-fly annotation"""
1347
def __init__(self, a_rev, b_rev, vf):
1348
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1349
a_ancestry = set(vf.get_ancestry(a_rev, topo_sorted=False))
1350
b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
1351
self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
1353
def _determine_status(self, revision_id, unique_line_numbers):
1354
"""Determines the status unique lines versus all lcas.
1356
Basically, determines why the line is unique to this revision.
1358
A line may be determined new or killed, but not both.
1360
:param revision_id: The id of the revision in which the lines are
1362
:param unique_line_numbers: The line numbers of unique lines.
1363
:return a tuple of (new_this, killed_other):
1365
new = self._find_new(revision_id)
1366
killed = set(unique_line_numbers).difference(new)
1369
def _find_new(self, version_id):
1370
"""Determine which lines are new in the ancestry of this version.
1372
If a lines is present in this version, and not present in any
1373
common ancestor, it is considered new.
1375
if version_id not in self.uncommon:
1377
parents = self.vf.get_parents(version_id)
1378
if len(parents) == 0:
1379
return set(range(len(self.vf.get_lines(version_id))))
1381
for parent in parents:
1382
blocks = self._get_matching_blocks(version_id, parent)
1383
result, unused = self._unique_lines(blocks)
1384
parent_new = self._find_new(parent)
1385
for i, j, n in blocks:
1386
for ii, jj in [(i+r, j+r) for r in range(n)]:
1387
if jj in parent_new:
1392
new.intersection_update(result)
1396
class _PlanLCAMerge(_PlanMergeBase):
1398
This merge algorithm differs from _PlanMerge in that:
1399
1. comparisons are done against LCAs only
1400
2. cases where a contested line is new versus one LCA but old versus
1401
another are marked as conflicts, by emitting the line as conflicted-a
1404
This is faster, and hopefully produces more useful output.
1407
def __init__(self, a_rev, b_rev, vf, graph):
1408
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1409
self.lcas = graph.find_lca(a_rev, b_rev)
1410
for lca in self.lcas:
1411
lca_lines = self.vf.get_lines(lca)
1412
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
1414
blocks = list(matcher.get_matching_blocks())
1415
self._cached_matching_blocks[(a_rev, lca)] = blocks
1416
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
1418
blocks = list(matcher.get_matching_blocks())
1419
self._cached_matching_blocks[(b_rev, lca)] = blocks
1421
def _determine_status(self, revision_id, unique_line_numbers):
1422
"""Determines the status unique lines versus all lcas.
1424
Basically, determines why the line is unique to this revision.
1426
A line may be determined new, killed, or both.
1428
If a line is determined new, that means it was not present in at least
1429
one LCA, and is not present in the other merge revision.
1431
If a line is determined killed, that means the line was present in
1434
If a line is killed and new, this indicates that the two merge
1435
revisions contain differing conflict resolutions.
1436
:param revision_id: The id of the revision in which the lines are
1438
:param unique_line_numbers: The line numbers of unique lines.
1439
:return a tuple of (new_this, killed_other):
1443
unique_line_numbers = set(unique_line_numbers)
1444
for lca in self.lcas:
1445
blocks = self._get_matching_blocks(revision_id, lca)
1446
unique_vs_lca, _ignored = self._unique_lines(blocks)
1447
new.update(unique_line_numbers.intersection(unique_vs_lca))
1448
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
bzrlib/merge.py
