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, is_quiet
51
from bzrlib.transform import (TransformPreview, TreeTransform,
52
resolve_conflicts, cook_conflicts,
53
conflict_pass, FinalPaths, create_by_entry,
54
unique_add, ROOT_PARENT)
55
from bzrlib.versionedfile import PlanWeaveMerge
58
# TODO: Report back as changes are merged in
61
def transform_tree(from_tree, to_tree, interesting_ids=None):
62
merge_inner(from_tree.branch, to_tree, from_tree, ignore_zero=True,
63
interesting_ids=interesting_ids, this_tree=from_tree)
67
def __init__(self, this_branch, other_tree=None, base_tree=None,
68
this_tree=None, pb=DummyProgress(), change_reporter=None,
69
recurse='down', revision_graph=None):
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
if self.other_basis is None:
120
self._base_is_other_ancestor = self.revision_graph.is_ancestor(
121
self.base_rev_id, self.other_basis)
122
return self._base_is_other_ancestor
124
base_is_other_ancestor = property(_get_base_is_other_ancestor,
125
_set_base_is_other_ancestor)
128
def from_uncommitted(tree, other_tree, pb):
129
"""Return a Merger for uncommitted changes in other_tree.
131
:param tree: The tree to merge into
132
:param other_tree: The tree to get uncommitted changes from
133
:param pb: A progress indicator
135
merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,
137
merger.base_rev_id = merger.base_tree.get_revision_id()
138
merger.other_rev_id = None
139
merger.other_basis = merger.base_rev_id
143
def from_mergeable(klass, tree, mergeable, pb):
144
"""Return a Merger for a bundle or merge directive.
146
:param tree: The tree to merge changes into
147
:param mergeable: A merge directive or bundle
148
:param pb: A progress indicator
150
mergeable.install_revisions(tree.branch.repository)
151
base_revision_id, other_revision_id, verified =\
152
mergeable.get_merge_request(tree.branch.repository)
153
revision_graph = tree.branch.repository.get_graph()
154
if base_revision_id is not None:
155
if (base_revision_id != _mod_revision.NULL_REVISION and
156
revision_graph.is_ancestor(
157
base_revision_id, tree.branch.last_revision())):
158
base_revision_id = None
160
warning('Performing cherrypick')
161
merger = klass.from_revision_ids(pb, tree, other_revision_id,
162
base_revision_id, revision_graph=
164
return merger, verified
167
def from_revision_ids(pb, tree, other, base=None, other_branch=None,
168
base_branch=None, revision_graph=None):
169
"""Return a Merger for revision-ids.
171
:param tree: The tree to merge changes into
172
:param other: The revision-id to use as OTHER
173
:param base: The revision-id to use as BASE. If not specified, will
175
:param other_branch: A branch containing the other revision-id. If
176
not supplied, tree.branch is used.
177
:param base_branch: A branch containing the base revision-id. If
178
not supplied, other_branch or tree.branch will be used.
179
:param revision_graph: If you have a revision_graph precomputed, pass
180
it in, otherwise it will be created for you.
181
:param pb: A progress indicator
183
merger = Merger(tree.branch, this_tree=tree, pb=pb,
184
revision_graph=revision_graph)
185
if other_branch is None:
186
other_branch = tree.branch
187
merger.set_other_revision(other, other_branch)
191
if base_branch is None:
192
base_branch = other_branch
193
merger.set_base_revision(base, base_branch)
196
def revision_tree(self, revision_id, branch=None):
197
if revision_id not in self._cached_trees:
199
branch = self.this_branch
201
tree = self.this_tree.revision_tree(revision_id)
202
except errors.NoSuchRevisionInTree:
203
tree = branch.repository.revision_tree(revision_id)
204
self._cached_trees[revision_id] = tree
205
return self._cached_trees[revision_id]
207
def _get_tree(self, treespec, possible_transports=None):
208
from bzrlib import workingtree
209
location, revno = treespec
211
tree = workingtree.WorkingTree.open_containing(location)[0]
212
return tree.branch, tree
213
branch = Branch.open_containing(location, possible_transports)[0]
215
revision_id = branch.last_revision()
217
revision_id = branch.get_rev_id(revno)
218
revision_id = ensure_null(revision_id)
219
return branch, self.revision_tree(revision_id, branch)
221
def ensure_revision_trees(self):
222
if self.this_revision_tree is None:
223
self.this_basis_tree = self.revision_tree(self.this_basis)
224
if self.this_basis == self.this_rev_id:
225
self.this_revision_tree = self.this_basis_tree
227
if self.other_rev_id is None:
228
other_basis_tree = self.revision_tree(self.other_basis)
229
changes = other_basis_tree.changes_from(self.other_tree)
230
if changes.has_changed():
231
raise WorkingTreeNotRevision(self.this_tree)
232
other_rev_id = self.other_basis
233
self.other_tree = other_basis_tree
235
def file_revisions(self, file_id):
236
self.ensure_revision_trees()
237
def get_id(tree, file_id):
238
revision_id = tree.inventory[file_id].revision
240
if self.this_rev_id is None:
241
if self.this_basis_tree.get_file_sha1(file_id) != \
242
self.this_tree.get_file_sha1(file_id):
243
raise WorkingTreeNotRevision(self.this_tree)
245
trees = (self.this_basis_tree, self.other_tree)
246
return [get_id(tree, file_id) for tree in trees]
248
def check_basis(self, check_clean, require_commits=True):
249
if self.this_basis is None and require_commits is True:
250
raise BzrCommandError("This branch has no commits."
251
" (perhaps you would prefer 'bzr pull')")
254
if self.this_basis != self.this_rev_id:
255
raise errors.UncommittedChanges(self.this_tree)
257
def compare_basis(self):
259
basis_tree = self.revision_tree(self.this_tree.last_revision())
260
except errors.RevisionNotPresent:
261
basis_tree = self.this_tree.basis_tree()
262
changes = self.this_tree.changes_from(basis_tree)
263
if not changes.has_changed():
264
self.this_rev_id = self.this_basis
266
def set_interesting_files(self, file_list):
267
self.interesting_files = file_list
269
def set_pending(self):
270
if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:
274
def _add_parent(self):
275
new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
276
new_parent_trees = []
277
for revision_id in new_parents:
279
tree = self.revision_tree(revision_id)
280
except errors.RevisionNotPresent:
284
new_parent_trees.append((revision_id, tree))
286
self.this_tree.set_parent_trees(new_parent_trees,
287
allow_leftmost_as_ghost=True)
289
for _revision_id, tree in new_parent_trees:
293
def set_other(self, other_revision, possible_transports=None):
294
"""Set the revision and tree to merge from.
296
This sets the other_tree, other_rev_id, other_basis attributes.
298
:param other_revision: The [path, revision] list to merge from.
300
self.other_branch, self.other_tree = self._get_tree(other_revision,
302
if other_revision[1] == -1:
303
self.other_rev_id = _mod_revision.ensure_null(
304
self.other_branch.last_revision())
305
if _mod_revision.is_null(self.other_rev_id):
306
raise NoCommits(self.other_branch)
307
self.other_basis = self.other_rev_id
308
elif other_revision[1] is not None:
309
self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
310
self.other_basis = self.other_rev_id
312
self.other_rev_id = None
313
self.other_basis = self.other_branch.last_revision()
314
if self.other_basis is None:
315
raise NoCommits(self.other_branch)
316
if self.other_rev_id is not None:
317
self._cached_trees[self.other_rev_id] = self.other_tree
318
self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)
320
def set_other_revision(self, revision_id, other_branch):
321
"""Set 'other' based on a branch and revision id
323
:param revision_id: The revision to use for a tree
324
:param other_branch: The branch containing this tree
326
self.other_rev_id = revision_id
327
self.other_branch = other_branch
328
self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
329
self.other_tree = self.revision_tree(revision_id)
330
self.other_basis = revision_id
332
def set_base_revision(self, revision_id, branch):
333
"""Set 'base' based on a branch and revision id
335
:param revision_id: The revision to use for a tree
336
:param branch: The branch containing this tree
338
self.base_rev_id = revision_id
339
self.base_branch = branch
340
self._maybe_fetch(branch, self.this_branch, revision_id)
341
self.base_tree = self.revision_tree(revision_id)
343
def _maybe_fetch(self, source, target, revision_id):
344
if not source.repository.has_same_location(target.repository):
345
target.fetch(source, revision_id)
348
revisions = [ensure_null(self.this_basis),
349
ensure_null(self.other_basis)]
350
if NULL_REVISION in revisions:
351
self.base_rev_id = NULL_REVISION
353
self.base_rev_id, steps = self.revision_graph.find_unique_lca(
354
revisions[0], revisions[1], count_steps=True)
355
if self.base_rev_id == NULL_REVISION:
356
raise UnrelatedBranches()
358
warning('Warning: criss-cross merge encountered. See bzr'
359
' help criss-cross.')
360
self.base_tree = self.revision_tree(self.base_rev_id)
361
self.base_is_ancestor = True
362
self.base_is_other_ancestor = True
364
def set_base(self, base_revision):
365
"""Set the base revision to use for the merge.
367
:param base_revision: A 2-list containing a path and revision number.
369
mutter("doing merge() with no base_revision specified")
370
if base_revision == [None, None]:
373
base_branch, self.base_tree = self._get_tree(base_revision)
374
if base_revision[1] == -1:
375
self.base_rev_id = base_branch.last_revision()
376
elif base_revision[1] is None:
377
self.base_rev_id = _mod_revision.NULL_REVISION
379
self.base_rev_id = _mod_revision.ensure_null(
380
base_branch.get_rev_id(base_revision[1]))
381
self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
383
def make_merger(self):
384
kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
385
'other_tree': self.other_tree,
386
'interesting_ids': self.interesting_ids,
387
'interesting_files': self.interesting_files,
390
if self.merge_type.requires_base:
391
kwargs['base_tree'] = self.base_tree
392
if self.merge_type.supports_reprocess:
393
kwargs['reprocess'] = self.reprocess
395
raise BzrError("Conflict reduction is not supported for merge"
396
" type %s." % self.merge_type)
397
if self.merge_type.supports_show_base:
398
kwargs['show_base'] = self.show_base
400
raise BzrError("Showing base is not supported for this"
401
" merge type. %s" % self.merge_type)
402
if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
403
and not self.base_is_other_ancestor):
404
raise errors.CannotReverseCherrypick()
405
if self.merge_type.supports_cherrypick:
406
kwargs['cherrypick'] = (not self.base_is_ancestor or
407
not self.base_is_other_ancestor)
408
return self.merge_type(pb=self._pb,
409
change_reporter=self.change_reporter,
413
self.this_tree.lock_tree_write()
414
if self.base_tree is not None:
415
self.base_tree.lock_read()
416
if self.other_tree is not None:
417
self.other_tree.lock_read()
419
merge = self.make_merger()
421
if self.recurse == 'down':
422
for path, file_id in self.this_tree.iter_references():
423
sub_tree = self.this_tree.get_nested_tree(file_id, path)
424
other_revision = self.other_tree.get_reference_revision(
426
if other_revision == sub_tree.last_revision():
428
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
429
sub_merge.merge_type = self.merge_type
430
relpath = self.this_tree.relpath(path)
431
other_branch = self.other_branch.reference_parent(file_id, relpath)
432
sub_merge.set_other_revision(other_revision, other_branch)
433
base_revision = self.base_tree.get_reference_revision(file_id)
434
sub_merge.base_tree = \
435
sub_tree.branch.repository.revision_tree(base_revision)
436
sub_merge.base_rev_id = base_revision
440
if self.other_tree is not None:
441
self.other_tree.unlock()
442
if self.base_tree is not None:
443
self.base_tree.unlock()
444
self.this_tree.unlock()
445
if len(merge.cooked_conflicts) == 0:
446
if not self.ignore_zero and not is_quiet():
447
note("All changes applied successfully.")
449
note("%d conflicts encountered." % len(merge.cooked_conflicts))
451
return len(merge.cooked_conflicts)
454
class Merge3Merger(object):
455
"""Three-way merger that uses the merge3 text merger"""
457
supports_reprocess = True
458
supports_show_base = True
459
history_based = False
460
supports_cherrypick = True
461
supports_reverse_cherrypick = True
462
winner_idx = {"this": 2, "other": 1, "conflict": 1}
464
def __init__(self, working_tree, this_tree, base_tree, other_tree,
465
interesting_ids=None, reprocess=False, show_base=False,
466
pb=DummyProgress(), pp=None, change_reporter=None,
467
interesting_files=None, do_merge=True,
469
"""Initialize the merger object and perform the merge.
471
:param working_tree: The working tree to apply the merge to
472
:param this_tree: The local tree in the merge operation
473
:param base_tree: The common tree in the merge operation
474
:param other_tree: The other other tree to merge changes from
475
:param interesting_ids: The file_ids of files that should be
476
participate in the merge. May not be combined with
478
:param: reprocess If True, perform conflict-reduction processing.
479
:param show_base: If True, show the base revision in text conflicts.
480
(incompatible with reprocess)
481
:param pb: A Progress bar
482
:param pp: A ProgressPhase object
483
:param change_reporter: An object that should report changes made
484
:param interesting_files: The tree-relative paths of files that should
485
participate in the merge. If these paths refer to directories,
486
the contents of those directories will also be included. May not
487
be combined with interesting_ids. If neither interesting_files nor
488
interesting_ids is specified, all files may participate in the
491
object.__init__(self)
492
if interesting_files is not None and interesting_ids is not None:
494
'specify either interesting_ids or interesting_files')
495
self.interesting_ids = interesting_ids
496
self.interesting_files = interesting_files
497
self.this_tree = working_tree
498
self.base_tree = base_tree
499
self.other_tree = other_tree
500
self._raw_conflicts = []
501
self.cooked_conflicts = []
502
self.reprocess = reprocess
503
self.show_base = show_base
506
self.change_reporter = change_reporter
507
self.cherrypick = cherrypick
509
self.pp = ProgressPhase("Merge phase", 3, self.pb)
514
self.this_tree.lock_tree_write()
515
self.base_tree.lock_read()
516
self.other_tree.lock_read()
517
self.tt = TreeTransform(self.this_tree, self.pb)
520
self._compute_transform()
522
results = self.tt.apply(no_conflicts=True)
523
self.write_modified(results)
525
self.this_tree.add_conflicts(self.cooked_conflicts)
526
except UnsupportedOperation:
530
self.other_tree.unlock()
531
self.base_tree.unlock()
532
self.this_tree.unlock()
535
def make_preview_transform(self):
536
self.base_tree.lock_read()
537
self.other_tree.lock_read()
538
self.tt = TransformPreview(self.this_tree)
541
self._compute_transform()
544
self.other_tree.unlock()
545
self.base_tree.unlock()
549
def _compute_transform(self):
550
entries = self._entries3()
551
child_pb = ui.ui_factory.nested_progress_bar()
553
for num, (file_id, changed, parents3, names3,
554
executable3) in enumerate(entries):
555
child_pb.update('Preparing file merge', num, len(entries))
556
self._merge_names(file_id, parents3, names3)
558
file_status = self.merge_contents(file_id)
560
file_status = 'unmodified'
561
self._merge_executable(file_id,
562
executable3, file_status)
567
child_pb = ui.ui_factory.nested_progress_bar()
569
fs_conflicts = resolve_conflicts(self.tt, child_pb,
570
lambda t, c: conflict_pass(t, c, self.other_tree))
573
if self.change_reporter is not None:
574
from bzrlib import delta
575
delta.report_changes(
576
self.tt.iter_changes(), self.change_reporter)
577
self.cook_conflicts(fs_conflicts)
578
for conflict in self.cooked_conflicts:
582
"""Gather data about files modified between three trees.
584
Return a list of tuples of file_id, changed, parents3, names3,
585
executable3. changed is a boolean indicating whether the file contents
586
or kind were changed. parents3 is a tuple of parent ids for base,
587
other and this. names3 is a tuple of names for base, other and this.
588
executable3 is a tuple of execute-bit values for base, other and this.
591
iterator = self.other_tree.iter_changes(self.base_tree,
592
include_unchanged=True, specific_files=self.interesting_files,
593
extra_trees=[self.this_tree])
594
for (file_id, paths, changed, versioned, parents, names, kind,
595
executable) in iterator:
596
if (self.interesting_ids is not None and
597
file_id not in self.interesting_ids):
599
if file_id in self.this_tree.inventory:
600
entry = self.this_tree.inventory[file_id]
601
this_name = entry.name
602
this_parent = entry.parent_id
603
this_executable = entry.executable
607
this_executable = None
608
parents3 = parents + (this_parent,)
609
names3 = names + (this_name,)
610
executable3 = executable + (this_executable,)
611
result.append((file_id, changed, parents3, names3, executable3))
616
self.tt.final_kind(self.tt.root)
618
self.tt.cancel_deletion(self.tt.root)
619
if self.tt.final_file_id(self.tt.root) is None:
620
self.tt.version_file(self.tt.tree_file_id(self.tt.root),
622
if self.other_tree.inventory.root is None:
624
other_root_file_id = self.other_tree.get_root_id()
625
other_root = self.tt.trans_id_file_id(other_root_file_id)
626
if other_root == self.tt.root:
629
self.tt.final_kind(other_root)
632
self.reparent_children(self.other_tree.inventory.root, self.tt.root)
633
self.tt.cancel_creation(other_root)
634
self.tt.cancel_versioning(other_root)
636
def reparent_children(self, ie, target):
637
for thing, child in ie.children.iteritems():
638
trans_id = self.tt.trans_id_file_id(child.file_id)
639
self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)
641
def write_modified(self, results):
643
for path in results.modified_paths:
644
file_id = self.this_tree.path2id(self.this_tree.relpath(path))
647
hash = self.this_tree.get_file_sha1(file_id)
650
modified_hashes[file_id] = hash
651
self.this_tree.set_merge_modified(modified_hashes)
654
def parent(entry, file_id):
655
"""Determine the parent for a file_id (used as a key method)"""
658
return entry.parent_id
661
def name(entry, file_id):
662
"""Determine the name for a file_id (used as a key method)"""
668
def contents_sha1(tree, file_id):
669
"""Determine the sha1 of the file contents (used as a key method)."""
670
if file_id not in tree:
672
return tree.get_file_sha1(file_id)
675
def executable(tree, file_id):
676
"""Determine the executability of a file-id (used as a key method)."""
677
if file_id not in tree:
679
if tree.kind(file_id) != "file":
681
return tree.is_executable(file_id)
684
def kind(tree, file_id):
685
"""Determine the kind of a file-id (used as a key method)."""
686
if file_id not in tree:
688
return tree.kind(file_id)
691
def _three_way(base, other, this):
692
#if base == other, either they all agree, or only THIS has changed.
695
elif this not in (base, other):
697
# "Ambiguous clean merge" -- both sides have made the same change.
700
# this == base: only other has changed.
705
def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
706
"""Do a three-way test on a scalar.
707
Return "this", "other" or "conflict", depending whether a value wins.
709
key_base = key(base_tree, file_id)
710
key_other = key(other_tree, file_id)
711
#if base == other, either they all agree, or only THIS has changed.
712
if key_base == key_other:
714
key_this = key(this_tree, file_id)
715
# "Ambiguous clean merge"
716
if key_this == key_other:
718
elif key_this == key_base:
723
def merge_names(self, file_id):
725
if file_id in tree.inventory:
726
return tree.inventory[file_id]
729
this_entry = get_entry(self.this_tree)
730
other_entry = get_entry(self.other_tree)
731
base_entry = get_entry(self.base_tree)
732
entries = (base_entry, other_entry, this_entry)
735
for entry in entries:
740
names.append(entry.name)
741
parents.append(entry.parent_id)
742
return self._merge_names(file_id, parents, names)
744
def _merge_names(self, file_id, parents, names):
745
"""Perform a merge on file_id names and parents"""
746
base_name, other_name, this_name = names
747
base_parent, other_parent, this_parent = parents
749
name_winner = self._three_way(*names)
751
parent_id_winner = self._three_way(*parents)
752
if this_name is None:
753
if name_winner == "this":
754
name_winner = "other"
755
if parent_id_winner == "this":
756
parent_id_winner = "other"
757
if name_winner == "this" and parent_id_winner == "this":
759
if name_winner == "conflict":
760
trans_id = self.tt.trans_id_file_id(file_id)
761
self._raw_conflicts.append(('name conflict', trans_id,
762
this_name, other_name))
763
if parent_id_winner == "conflict":
764
trans_id = self.tt.trans_id_file_id(file_id)
765
self._raw_conflicts.append(('parent conflict', trans_id,
766
this_parent, other_parent))
767
if other_name is None:
768
# it doesn't matter whether the result was 'other' or
769
# 'conflict'-- if there's no 'other', we leave it alone.
771
# if we get here, name_winner and parent_winner are set to safe values.
772
trans_id = self.tt.trans_id_file_id(file_id)
773
parent_id = parents[self.winner_idx[parent_id_winner]]
774
if parent_id is not None:
775
parent_trans_id = self.tt.trans_id_file_id(parent_id)
776
self.tt.adjust_path(names[self.winner_idx[name_winner]],
777
parent_trans_id, trans_id)
779
def merge_contents(self, file_id):
780
"""Performa a merge on file_id contents."""
781
def contents_pair(tree):
782
if file_id not in tree:
784
kind = tree.kind(file_id)
786
contents = tree.get_file_sha1(file_id)
787
elif kind == "symlink":
788
contents = tree.get_symlink_target(file_id)
791
return kind, contents
793
def contents_conflict():
794
trans_id = self.tt.trans_id_file_id(file_id)
795
name = self.tt.final_name(trans_id)
796
parent_id = self.tt.final_parent(trans_id)
797
if file_id in self.this_tree.inventory:
798
self.tt.unversion_file(trans_id)
799
if file_id in self.this_tree:
800
self.tt.delete_contents(trans_id)
801
file_group = self._dump_conflicts(name, parent_id, file_id,
803
self._raw_conflicts.append(('contents conflict', file_group))
805
# See SPOT run. run, SPOT, run.
806
# So we're not QUITE repeating ourselves; we do tricky things with
808
base_pair = contents_pair(self.base_tree)
809
other_pair = contents_pair(self.other_tree)
810
if base_pair == other_pair:
811
# OTHER introduced no changes
813
this_pair = contents_pair(self.this_tree)
814
if this_pair == other_pair:
815
# THIS and OTHER introduced the same changes
818
trans_id = self.tt.trans_id_file_id(file_id)
819
if this_pair == base_pair:
820
# only OTHER introduced changes
821
if file_id in self.this_tree:
822
# Remove any existing contents
823
self.tt.delete_contents(trans_id)
824
if file_id in self.other_tree:
825
# OTHER changed the file
826
create_by_entry(self.tt,
827
self.other_tree.inventory[file_id],
828
self.other_tree, trans_id)
829
if file_id not in self.this_tree.inventory:
830
self.tt.version_file(file_id, trans_id)
832
elif file_id in self.this_tree.inventory:
833
# OTHER deleted the file
834
self.tt.unversion_file(trans_id)
836
#BOTH THIS and OTHER introduced changes; scalar conflict
837
elif this_pair[0] == "file" and other_pair[0] == "file":
838
# THIS and OTHER are both files, so text merge. Either
839
# BASE is a file, or both converted to files, so at least we
840
# have agreement that output should be a file.
842
self.text_merge(file_id, trans_id)
844
return contents_conflict()
845
if file_id not in self.this_tree.inventory:
846
self.tt.version_file(file_id, trans_id)
848
self.tt.tree_kind(trans_id)
849
self.tt.delete_contents(trans_id)
854
# Scalar conflict, can't text merge. Dump conflicts
855
return contents_conflict()
857
def get_lines(self, tree, file_id):
858
"""Return the lines in a file, or an empty list."""
860
return tree.get_file(file_id).readlines()
864
def text_merge(self, file_id, trans_id):
865
"""Perform a three-way text merge on a file_id"""
866
# it's possible that we got here with base as a different type.
867
# if so, we just want two-way text conflicts.
868
if file_id in self.base_tree and \
869
self.base_tree.kind(file_id) == "file":
870
base_lines = self.get_lines(self.base_tree, file_id)
873
other_lines = self.get_lines(self.other_tree, file_id)
874
this_lines = self.get_lines(self.this_tree, file_id)
875
m3 = Merge3(base_lines, this_lines, other_lines,
876
is_cherrypick=self.cherrypick)
877
start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
878
if self.show_base is True:
879
base_marker = '|' * 7
883
def iter_merge3(retval):
884
retval["text_conflicts"] = False
885
for line in m3.merge_lines(name_a = "TREE",
886
name_b = "MERGE-SOURCE",
887
name_base = "BASE-REVISION",
888
start_marker=start_marker,
889
base_marker=base_marker,
890
reprocess=self.reprocess):
891
if line.startswith(start_marker):
892
retval["text_conflicts"] = True
893
yield line.replace(start_marker, '<' * 7)
897
merge3_iterator = iter_merge3(retval)
898
self.tt.create_file(merge3_iterator, trans_id)
899
if retval["text_conflicts"] is True:
900
self._raw_conflicts.append(('text conflict', trans_id))
901
name = self.tt.final_name(trans_id)
902
parent_id = self.tt.final_parent(trans_id)
903
file_group = self._dump_conflicts(name, parent_id, file_id,
904
this_lines, base_lines,
906
file_group.append(trans_id)
908
def _dump_conflicts(self, name, parent_id, file_id, this_lines=None,
909
base_lines=None, other_lines=None, set_version=False,
911
"""Emit conflict files.
912
If this_lines, base_lines, or other_lines are omitted, they will be
913
determined automatically. If set_version is true, the .OTHER, .THIS
914
or .BASE (in that order) will be created as versioned files.
916
data = [('OTHER', self.other_tree, other_lines),
917
('THIS', self.this_tree, this_lines)]
919
data.append(('BASE', self.base_tree, base_lines))
922
for suffix, tree, lines in data:
924
trans_id = self._conflict_file(name, parent_id, tree, file_id,
926
file_group.append(trans_id)
927
if set_version and not versioned:
928
self.tt.version_file(file_id, trans_id)
932
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
934
"""Emit a single conflict file."""
935
name = name + '.' + suffix
936
trans_id = self.tt.create_path(name, parent_id)
937
entry = tree.inventory[file_id]
938
create_by_entry(self.tt, entry, tree, trans_id, lines)
941
def merge_executable(self, file_id, file_status):
942
"""Perform a merge on the execute bit."""
943
executable = [self.executable(t, file_id) for t in (self.base_tree,
944
self.other_tree, self.this_tree)]
945
self._merge_executable(file_id, executable, file_status)
947
def _merge_executable(self, file_id, executable, file_status):
948
"""Perform a merge on the execute bit."""
949
base_executable, other_executable, this_executable = executable
950
if file_status == "deleted":
952
winner = self._three_way(*executable)
953
if winner == "conflict":
954
# There must be a None in here, if we have a conflict, but we
955
# need executability since file status was not deleted.
956
if self.executable(self.other_tree, file_id) is None:
960
if winner == 'this' and file_status != "modified":
962
trans_id = self.tt.trans_id_file_id(file_id)
964
if self.tt.final_kind(trans_id) != "file":
969
executability = this_executable
971
if file_id in self.other_tree:
972
executability = other_executable
973
elif file_id in self.this_tree:
974
executability = this_executable
975
elif file_id in self.base_tree:
976
executability = base_executable
977
if executability is not None:
978
trans_id = self.tt.trans_id_file_id(file_id)
979
self.tt.set_executability(executability, trans_id)
981
def cook_conflicts(self, fs_conflicts):
982
"""Convert all conflicts into a form that doesn't depend on trans_id"""
983
from conflicts import Conflict
985
self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
986
fp = FinalPaths(self.tt)
987
for conflict in self._raw_conflicts:
988
conflict_type = conflict[0]
989
if conflict_type in ('name conflict', 'parent conflict'):
990
trans_id = conflict[1]
991
conflict_args = conflict[2:]
992
if trans_id not in name_conflicts:
993
name_conflicts[trans_id] = {}
994
unique_add(name_conflicts[trans_id], conflict_type,
996
if conflict_type == 'contents conflict':
997
for trans_id in conflict[1]:
998
file_id = self.tt.final_file_id(trans_id)
999
if file_id is not None:
1001
path = fp.get_path(trans_id)
1002
for suffix in ('.BASE', '.THIS', '.OTHER'):
1003
if path.endswith(suffix):
1004
path = path[:-len(suffix)]
1006
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1007
self.cooked_conflicts.append(c)
1008
if conflict_type == 'text conflict':
1009
trans_id = conflict[1]
1010
path = fp.get_path(trans_id)
1011
file_id = self.tt.final_file_id(trans_id)
1012
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1013
self.cooked_conflicts.append(c)
1015
for trans_id, conflicts in name_conflicts.iteritems():
1017
this_parent, other_parent = conflicts['parent conflict']
1018
if this_parent == other_parent:
1019
raise AssertionError()
1021
this_parent = other_parent = \
1022
self.tt.final_file_id(self.tt.final_parent(trans_id))
1024
this_name, other_name = conflicts['name conflict']
1025
if this_name == other_name:
1026
raise AssertionError()
1028
this_name = other_name = self.tt.final_name(trans_id)
1029
other_path = fp.get_path(trans_id)
1030
if this_parent is not None and this_name is not None:
1031
this_parent_path = \
1032
fp.get_path(self.tt.trans_id_file_id(this_parent))
1033
this_path = pathjoin(this_parent_path, this_name)
1035
this_path = "<deleted>"
1036
file_id = self.tt.final_file_id(trans_id)
1037
c = Conflict.factory('path conflict', path=this_path,
1038
conflict_path=other_path, file_id=file_id)
1039
self.cooked_conflicts.append(c)
1040
self.cooked_conflicts.sort(key=Conflict.sort_key)
1043
class WeaveMerger(Merge3Merger):
1044
"""Three-way tree merger, text weave merger."""
1045
supports_reprocess = True
1046
supports_show_base = False
1047
supports_reverse_cherrypick = False
1048
history_based = True
1050
def _merged_lines(self, file_id):
1051
"""Generate the merged lines.
1052
There is no distinction between lines that are meant to contain <<<<<<<
1056
base = self.base_tree
1059
plan = self.this_tree.plan_file_merge(file_id, self.other_tree,
1061
if 'merge' in debug.debug_flags:
1063
trans_id = self.tt.trans_id_file_id(file_id)
1064
name = self.tt.final_name(trans_id) + '.plan'
1065
contents = ('%10s|%s' % l for l in plan)
1066
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1067
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1068
'>>>>>>> MERGE-SOURCE\n')
1069
return textmerge.merge_lines(self.reprocess)
1071
def text_merge(self, file_id, trans_id):
1072
"""Perform a (weave) text merge for a given file and file-id.
1073
If conflicts are encountered, .THIS and .OTHER files will be emitted,
1074
and a conflict will be noted.
1076
lines, conflicts = self._merged_lines(file_id)
1078
# Note we're checking whether the OUTPUT is binary in this case,
1079
# because we don't want to get into weave merge guts.
1080
check_text_lines(lines)
1081
self.tt.create_file(lines, trans_id)
1083
self._raw_conflicts.append(('text conflict', trans_id))
1084
name = self.tt.final_name(trans_id)
1085
parent_id = self.tt.final_parent(trans_id)
1086
file_group = self._dump_conflicts(name, parent_id, file_id,
1088
file_group.append(trans_id)
1091
class LCAMerger(WeaveMerger):
1093
def _merged_lines(self, file_id):
1094
"""Generate the merged lines.
1095
There is no distinction between lines that are meant to contain <<<<<<<
1099
base = self.base_tree
1102
plan = self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1104
if 'merge' in debug.debug_flags:
1106
trans_id = self.tt.trans_id_file_id(file_id)
1107
name = self.tt.final_name(trans_id) + '.plan'
1108
contents = ('%10s|%s' % l for l in plan)
1109
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1110
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1111
'>>>>>>> MERGE-SOURCE\n')
1112
return textmerge.merge_lines(self.reprocess)
1115
class Diff3Merger(Merge3Merger):
1116
"""Three-way merger using external diff3 for text merging"""
1118
def dump_file(self, temp_dir, name, tree, file_id):
1119
out_path = pathjoin(temp_dir, name)
1120
out_file = open(out_path, "wb")
1122
in_file = tree.get_file(file_id)
1123
for line in in_file:
1124
out_file.write(line)
1129
def text_merge(self, file_id, trans_id):
1130
"""Perform a diff3 merge using a specified file-id and trans-id.
1131
If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
1132
will be dumped, and a will be conflict noted.
1135
temp_dir = osutils.mkdtemp(prefix="bzr-")
1137
new_file = pathjoin(temp_dir, "new")
1138
this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
1139
base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
1140
other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
1141
status = bzrlib.patch.diff3(new_file, this, base, other)
1142
if status not in (0, 1):
1143
raise BzrError("Unhandled diff3 exit code")
1144
f = open(new_file, 'rb')
1146
self.tt.create_file(f, trans_id)
1150
name = self.tt.final_name(trans_id)
1151
parent_id = self.tt.final_parent(trans_id)
1152
self._dump_conflicts(name, parent_id, file_id)
1153
self._raw_conflicts.append(('text conflict', trans_id))
1155
osutils.rmtree(temp_dir)
1158
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
1160
merge_type=Merge3Merger,
1161
interesting_ids=None,
1165
interesting_files=None,
1168
change_reporter=None):
1169
"""Primary interface for merging.
1171
typical use is probably
1172
'merge_inner(branch, branch.get_revision_tree(other_revision),
1173
branch.get_revision_tree(base_revision))'
1175
if this_tree is None:
1176
raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
1177
"parameter as of bzrlib version 0.8.")
1178
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1179
pb=pb, change_reporter=change_reporter)
1180
merger.backup_files = backup_files
1181
merger.merge_type = merge_type
1182
merger.interesting_ids = interesting_ids
1183
merger.ignore_zero = ignore_zero
1184
if interesting_files:
1186
raise ValueError('Only supply interesting_ids'
1187
' or interesting_files')
1188
merger.interesting_files = interesting_files
1189
merger.show_base = show_base
1190
merger.reprocess = reprocess
1191
merger.other_rev_id = other_rev_id
1192
merger.other_basis = other_rev_id
1193
get_revision_id = getattr(base_tree, 'get_revision_id', None)
1194
if get_revision_id is None:
1195
get_revision_id = base_tree.last_revision
1196
merger.set_base_revision(get_revision_id(), this_branch)
1197
return merger.do_merge()
1199
def get_merge_type_registry():
1200
"""Merge type registry is in bzrlib.option to avoid circular imports.
1202
This method provides a sanctioned way to retrieve it.
1204
from bzrlib import option
1205
return option._merge_type_registry
1208
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1209
def status_a(revision, text):
1210
if revision in ancestors_b:
1211
return 'killed-b', text
1213
return 'new-a', text
1215
def status_b(revision, text):
1216
if revision in ancestors_a:
1217
return 'killed-a', text
1219
return 'new-b', text
1221
plain_a = [t for (a, t) in annotated_a]
1222
plain_b = [t for (a, t) in annotated_b]
1223
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
1224
blocks = matcher.get_matching_blocks()
1227
for ai, bi, l in blocks:
1228
# process all mismatched sections
1229
# (last mismatched section is handled because blocks always
1230
# includes a 0-length last block)
1231
for revision, text in annotated_a[a_cur:ai]:
1232
yield status_a(revision, text)
1233
for revision, text in annotated_b[b_cur:bi]:
1234
yield status_b(revision, text)
1235
# and now the matched section
1238
for text_a in plain_a[ai:a_cur]:
1239
yield "unchanged", text_a
1242
class _PlanMergeBase(object):
1244
def __init__(self, a_rev, b_rev, vf):
1247
:param a_rev: Revision-id of one revision to merge
1248
:param b_rev: Revision-id of the other revision to merge
1249
:param vf: A versionedfile containing both revisions
1253
self.lines_a = vf.get_lines(a_rev)
1254
self.lines_b = vf.get_lines(b_rev)
1256
self._last_lines = None
1257
self._last_lines_revision_id = None
1258
self._cached_matching_blocks = {}
1260
def plan_merge(self):
1261
"""Generate a 'plan' for merging the two revisions.
1263
This involves comparing their texts and determining the cause of
1264
differences. If text A has a line and text B does not, then either the
1265
line was added to text A, or it was deleted from B. Once the causes
1266
are combined, they are written out in the format described in
1267
VersionedFile.plan_merge
1269
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1270
unique_a, unique_b = self._unique_lines(blocks)
1271
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
1272
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
1273
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
1275
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1278
for i, j, n in blocks:
1279
for a_index in range(last_i, i):
1280
if a_index in new_a:
1281
if a_index in killed_b:
1282
yield 'conflicted-a', self.lines_a[a_index]
1284
yield 'new-a', self.lines_a[a_index]
1286
yield 'killed-b', self.lines_a[a_index]
1287
for b_index in range(last_j, j):
1288
if b_index in new_b:
1289
if b_index in killed_a:
1290
yield 'conflicted-b', self.lines_b[b_index]
1292
yield 'new-b', self.lines_b[b_index]
1294
yield 'killed-a', self.lines_b[b_index]
1295
# handle common lines
1296
for a_index in range(i, i+n):
1297
yield 'unchanged', self.lines_a[a_index]
1301
def _get_matching_blocks(self, left_revision, right_revision):
1302
"""Return a description of which sections of two revisions match.
1304
See SequenceMatcher.get_matching_blocks
1306
cached = self._cached_matching_blocks.get((left_revision,
1308
if cached is not None:
1310
if self._last_lines_revision_id == left_revision:
1311
left_lines = self._last_lines
1313
left_lines = self.vf.get_lines(left_revision)
1314
right_lines = self.vf.get_lines(right_revision)
1315
self._last_lines = right_lines
1316
self._last_lines_revision_id = right_revision
1317
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1319
return matcher.get_matching_blocks()
1321
def _unique_lines(self, matching_blocks):
1322
"""Analyse matching_blocks to determine which lines are unique
1324
:return: a tuple of (unique_left, unique_right), where the values are
1325
sets of line numbers of unique lines.
1331
for i, j, n in matching_blocks:
1332
unique_left.extend(range(last_i, i))
1333
unique_right.extend(range(last_j, j))
1336
return unique_left, unique_right
1339
def _subtract_plans(old_plan, new_plan):
1340
"""Remove changes from new_plan that came from old_plan.
1342
It is assumed that the difference between the old_plan and new_plan
1343
is their choice of 'b' text.
1345
All lines from new_plan that differ from old_plan are emitted
1346
verbatim. All lines from new_plan that match old_plan but are
1347
not about the 'b' revision are emitted verbatim.
1349
Lines that match and are about the 'b' revision are the lines we
1350
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
1351
is skipped entirely.
1353
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1356
for i, j, n in matcher.get_matching_blocks():
1357
for jj in range(last_j, j):
1359
for jj in range(j, j+n):
1360
plan_line = new_plan[jj]
1361
if plan_line[0] == 'new-b':
1363
elif plan_line[0] == 'killed-b':
1364
yield 'unchanged', plan_line[1]
1370
class _PlanMerge(_PlanMergeBase):
1371
"""Plan an annotate merge using on-the-fly annotation"""
1373
def __init__(self, a_rev, b_rev, vf):
1374
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1375
a_ancestry = set(vf.get_ancestry(a_rev, topo_sorted=False))
1376
b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
1377
self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
1379
def _determine_status(self, revision_id, unique_line_numbers):
1380
"""Determines the status unique lines versus all lcas.
1382
Basically, determines why the line is unique to this revision.
1384
A line may be determined new or killed, but not both.
1386
:param revision_id: The id of the revision in which the lines are
1388
:param unique_line_numbers: The line numbers of unique lines.
1389
:return a tuple of (new_this, killed_other):
1391
new = self._find_new(revision_id)
1392
killed = set(unique_line_numbers).difference(new)
1395
def _find_new(self, version_id):
1396
"""Determine which lines are new in the ancestry of this version.
1398
If a lines is present in this version, and not present in any
1399
common ancestor, it is considered new.
1401
if version_id not in self.uncommon:
1403
parents = self.vf.get_parent_map([version_id])[version_id]
1404
if len(parents) == 0:
1405
return set(range(len(self.vf.get_lines(version_id))))
1407
for parent in parents:
1408
blocks = self._get_matching_blocks(version_id, parent)
1409
result, unused = self._unique_lines(blocks)
1410
parent_new = self._find_new(parent)
1411
for i, j, n in blocks:
1412
for ii, jj in [(i+r, j+r) for r in range(n)]:
1413
if jj in parent_new:
1418
new.intersection_update(result)
1422
class _PlanLCAMerge(_PlanMergeBase):
1424
This merge algorithm differs from _PlanMerge in that:
1425
1. comparisons are done against LCAs only
1426
2. cases where a contested line is new versus one LCA but old versus
1427
another are marked as conflicts, by emitting the line as conflicted-a
1430
This is faster, and hopefully produces more useful output.
1433
def __init__(self, a_rev, b_rev, vf, graph):
1434
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1435
self.lcas = graph.find_lca(a_rev, b_rev)
1436
for lca in self.lcas:
1437
if _mod_revision.is_null(lca):
1440
lca_lines = self.vf.get_lines(lca)
1441
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
1443
blocks = list(matcher.get_matching_blocks())
1444
self._cached_matching_blocks[(a_rev, lca)] = blocks
1445
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
1447
blocks = list(matcher.get_matching_blocks())
1448
self._cached_matching_blocks[(b_rev, lca)] = blocks
1450
def _determine_status(self, revision_id, unique_line_numbers):
1451
"""Determines the status unique lines versus all lcas.
1453
Basically, determines why the line is unique to this revision.
1455
A line may be determined new, killed, or both.
1457
If a line is determined new, that means it was not present in at least
1458
one LCA, and is not present in the other merge revision.
1460
If a line is determined killed, that means the line was present in
1463
If a line is killed and new, this indicates that the two merge
1464
revisions contain differing conflict resolutions.
1465
:param revision_id: The id of the revision in which the lines are
1467
:param unique_line_numbers: The line numbers of unique lines.
1468
:return a tuple of (new_this, killed_other):
1472
unique_line_numbers = set(unique_line_numbers)
1473
for lca in self.lcas:
1474
blocks = self._get_matching_blocks(revision_id, lca)
1475
unique_vs_lca, _ignored = self._unique_lines(blocks)
1476
new.update(unique_line_numbers.intersection(unique_vs_lca))
1477
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
bzrlib/merge.py
