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
assert this_tree is not None, "this_tree is required"
72
self.this_branch = this_branch
73
self.this_basis = _mod_revision.ensure_null(
74
this_branch.last_revision())
75
self.this_rev_id = None
76
self.this_tree = this_tree
77
self.this_revision_tree = None
78
self.this_basis_tree = None
79
self.other_tree = other_tree
80
self.other_branch = None
81
self.base_tree = base_tree
82
self.ignore_zero = False
83
self.backup_files = False
84
self.interesting_ids = None
85
self.interesting_files = None
86
self.show_base = False
87
self.reprocess = False
90
self.recurse = recurse
91
self.change_reporter = change_reporter
92
self._cached_trees = {}
93
self._revision_graph = revision_graph
94
self._base_is_ancestor = None
95
self._base_is_other_ancestor = None
98
def revision_graph(self):
99
if self._revision_graph is None:
100
self._revision_graph = self.this_branch.repository.get_graph()
101
return self._revision_graph
103
def _set_base_is_ancestor(self, value):
104
self._base_is_ancestor = value
106
def _get_base_is_ancestor(self):
107
if self._base_is_ancestor is None:
108
self._base_is_ancestor = self.revision_graph.is_ancestor(
109
self.base_rev_id, self.this_basis)
110
return self._base_is_ancestor
112
base_is_ancestor = property(_get_base_is_ancestor, _set_base_is_ancestor)
114
def _set_base_is_other_ancestor(self, value):
115
self._base_is_other_ancestor = value
117
def _get_base_is_other_ancestor(self):
118
if self._base_is_other_ancestor is None:
119
if self.other_basis is None:
121
self._base_is_other_ancestor = self.revision_graph.is_ancestor(
122
self.base_rev_id, self.other_basis)
123
return self._base_is_other_ancestor
125
base_is_other_ancestor = property(_get_base_is_other_ancestor,
126
_set_base_is_other_ancestor)
129
def from_uncommitted(tree, other_tree, pb):
130
"""Return a Merger for uncommitted changes in other_tree.
132
:param tree: The tree to merge into
133
:param other_tree: The tree to get uncommitted changes from
134
:param pb: A progress indicator
136
merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,
138
merger.base_rev_id = merger.base_tree.get_revision_id()
139
merger.other_rev_id = None
140
merger.other_basis = merger.base_rev_id
144
def from_mergeable(klass, tree, mergeable, pb):
145
"""Return a Merger for a bundle or merge directive.
147
:param tree: The tree to merge changes into
148
:param mergeable: A merge directive or bundle
149
:param pb: A progress indicator
151
mergeable.install_revisions(tree.branch.repository)
152
base_revision_id, other_revision_id, verified =\
153
mergeable.get_merge_request(tree.branch.repository)
154
revision_graph = tree.branch.repository.get_graph()
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
239
assert revision_id is not None
241
if self.this_rev_id is None:
242
if self.this_basis_tree.get_file_sha1(file_id) != \
243
self.this_tree.get_file_sha1(file_id):
244
raise WorkingTreeNotRevision(self.this_tree)
246
trees = (self.this_basis_tree, self.other_tree)
247
return [get_id(tree, file_id) for tree in trees]
249
def check_basis(self, check_clean, require_commits=True):
250
if self.this_basis is None and require_commits is True:
251
raise BzrCommandError("This branch has no commits."
252
" (perhaps you would prefer 'bzr pull')")
255
if self.this_basis != self.this_rev_id:
256
raise errors.UncommittedChanges(self.this_tree)
258
def compare_basis(self):
260
basis_tree = self.revision_tree(self.this_tree.last_revision())
261
except errors.RevisionNotPresent:
262
basis_tree = self.this_tree.basis_tree()
263
changes = self.this_tree.changes_from(basis_tree)
264
if not changes.has_changed():
265
self.this_rev_id = self.this_basis
267
def set_interesting_files(self, file_list):
268
self.interesting_files = file_list
270
def set_pending(self):
271
if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:
275
def _add_parent(self):
276
new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
277
new_parent_trees = []
278
for revision_id in new_parents:
280
tree = self.revision_tree(revision_id)
281
except errors.RevisionNotPresent:
285
new_parent_trees.append((revision_id, tree))
287
self.this_tree.set_parent_trees(new_parent_trees,
288
allow_leftmost_as_ghost=True)
290
for _revision_id, tree in new_parent_trees:
294
def set_other(self, other_revision, possible_transports=None):
295
"""Set the revision and tree to merge from.
297
This sets the other_tree, other_rev_id, other_basis attributes.
299
:param other_revision: The [path, revision] list to merge from.
301
self.other_branch, self.other_tree = self._get_tree(other_revision,
303
if other_revision[1] == -1:
304
self.other_rev_id = _mod_revision.ensure_null(
305
self.other_branch.last_revision())
306
if _mod_revision.is_null(self.other_rev_id):
307
raise NoCommits(self.other_branch)
308
self.other_basis = self.other_rev_id
309
elif other_revision[1] is not None:
310
self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
311
self.other_basis = self.other_rev_id
313
self.other_rev_id = None
314
self.other_basis = self.other_branch.last_revision()
315
if self.other_basis is None:
316
raise NoCommits(self.other_branch)
317
if self.other_rev_id is not None:
318
self._cached_trees[self.other_rev_id] = self.other_tree
319
self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)
321
def set_other_revision(self, revision_id, other_branch):
322
"""Set 'other' based on a branch and revision id
324
:param revision_id: The revision to use for a tree
325
:param other_branch: The branch containing this tree
327
self.other_rev_id = revision_id
328
self.other_branch = other_branch
329
self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
330
self.other_tree = self.revision_tree(revision_id)
331
self.other_basis = revision_id
333
def set_base_revision(self, revision_id, branch):
334
"""Set 'base' based on a branch and revision id
336
:param revision_id: The revision to use for a tree
337
:param branch: The branch containing this tree
339
self.base_rev_id = revision_id
340
self.base_branch = branch
341
self._maybe_fetch(branch, self.this_branch, revision_id)
342
self.base_tree = self.revision_tree(revision_id)
344
def _maybe_fetch(self, source, target, revision_id):
345
if not source.repository.has_same_location(target.repository):
346
target.fetch(source, revision_id)
349
revisions = [ensure_null(self.this_basis),
350
ensure_null(self.other_basis)]
351
if NULL_REVISION in revisions:
352
self.base_rev_id = NULL_REVISION
354
self.base_rev_id, steps = self.revision_graph.find_unique_lca(
355
revisions[0], revisions[1], count_steps=True)
356
if self.base_rev_id == NULL_REVISION:
357
raise UnrelatedBranches()
359
warning('Warning: criss-cross merge encountered. See bzr'
360
' help criss-cross.')
361
self.base_tree = self.revision_tree(self.base_rev_id)
362
self.base_is_ancestor = True
363
self.base_is_other_ancestor = True
365
def set_base(self, base_revision):
366
"""Set the base revision to use for the merge.
368
:param base_revision: A 2-list containing a path and revision number.
370
mutter("doing merge() with no base_revision specified")
371
if base_revision == [None, None]:
374
base_branch, self.base_tree = self._get_tree(base_revision)
375
if base_revision[1] == -1:
376
self.base_rev_id = base_branch.last_revision()
377
elif base_revision[1] is None:
378
self.base_rev_id = _mod_revision.NULL_REVISION
380
self.base_rev_id = _mod_revision.ensure_null(
381
base_branch.get_rev_id(base_revision[1]))
382
self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
384
def make_merger(self):
385
kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
386
'other_tree': self.other_tree,
387
'interesting_ids': self.interesting_ids,
388
'interesting_files': self.interesting_files,
391
if self.merge_type.requires_base:
392
kwargs['base_tree'] = self.base_tree
393
if self.merge_type.supports_reprocess:
394
kwargs['reprocess'] = self.reprocess
396
raise BzrError("Conflict reduction is not supported for merge"
397
" type %s." % self.merge_type)
398
if self.merge_type.supports_show_base:
399
kwargs['show_base'] = self.show_base
401
raise BzrError("Showing base is not supported for this"
402
" merge type. %s" % self.merge_type)
403
if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
404
and not self.base_is_other_ancestor):
405
raise errors.CannotReverseCherrypick()
406
if self.merge_type.supports_cherrypick:
407
kwargs['cherrypick'] = (not self.base_is_ancestor or
408
not self.base_is_other_ancestor)
409
return self.merge_type(pb=self._pb,
410
change_reporter=self.change_reporter,
414
self.this_tree.lock_tree_write()
415
if self.base_tree is not None:
416
self.base_tree.lock_read()
417
if self.other_tree is not None:
418
self.other_tree.lock_read()
420
merge = self.make_merger()
422
if self.recurse == 'down':
423
for path, file_id in self.this_tree.iter_references():
424
sub_tree = self.this_tree.get_nested_tree(file_id, path)
425
other_revision = self.other_tree.get_reference_revision(
427
if other_revision == sub_tree.last_revision():
429
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
430
sub_merge.merge_type = self.merge_type
431
relpath = self.this_tree.relpath(path)
432
other_branch = self.other_branch.reference_parent(file_id, relpath)
433
sub_merge.set_other_revision(other_revision, other_branch)
434
base_revision = self.base_tree.get_reference_revision(file_id)
435
sub_merge.base_tree = \
436
sub_tree.branch.repository.revision_tree(base_revision)
437
sub_merge.base_rev_id = base_revision
441
if self.other_tree is not None:
442
self.other_tree.unlock()
443
if self.base_tree is not None:
444
self.base_tree.unlock()
445
self.this_tree.unlock()
446
if len(merge.cooked_conflicts) == 0:
447
if not self.ignore_zero and not is_quiet():
448
note("All changes applied successfully.")
450
note("%d conflicts encountered." % len(merge.cooked_conflicts))
452
return len(merge.cooked_conflicts)
455
class Merge3Merger(object):
456
"""Three-way merger that uses the merge3 text merger"""
458
supports_reprocess = True
459
supports_show_base = True
460
history_based = False
461
supports_cherrypick = True
462
supports_reverse_cherrypick = True
463
winner_idx = {"this": 2, "other": 1, "conflict": 1}
465
def __init__(self, working_tree, this_tree, base_tree, other_tree,
466
interesting_ids=None, reprocess=False, show_base=False,
467
pb=DummyProgress(), pp=None, change_reporter=None,
468
interesting_files=None, do_merge=True,
470
"""Initialize the merger object and perform the merge.
472
:param working_tree: The working tree to apply the merge to
473
:param this_tree: The local tree in the merge operation
474
:param base_tree: The common tree in the merge operation
475
:param other_tree: The other other tree to merge changes from
476
:param interesting_ids: The file_ids of files that should be
477
participate in the merge. May not be combined with
479
:param: reprocess If True, perform conflict-reduction processing.
480
:param show_base: If True, show the base revision in text conflicts.
481
(incompatible with reprocess)
482
:param pb: A Progress bar
483
:param pp: A ProgressPhase object
484
:param change_reporter: An object that should report changes made
485
:param interesting_files: The tree-relative paths of files that should
486
participate in the merge. If these paths refer to directories,
487
the contents of those directories will also be included. May not
488
be combined with interesting_ids. If neither interesting_files nor
489
interesting_ids is specified, all files may participate in the
492
object.__init__(self)
493
if interesting_files is not None:
494
assert interesting_ids is None
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
if key_this not in (key_base, key_other):
717
# "Ambiguous clean merge"
718
elif key_this == key_other:
721
assert key_this == key_base
724
def merge_names(self, file_id):
726
if file_id in tree.inventory:
727
return tree.inventory[file_id]
730
this_entry = get_entry(self.this_tree)
731
other_entry = get_entry(self.other_tree)
732
base_entry = get_entry(self.base_tree)
733
entries = (base_entry, other_entry, this_entry)
736
for entry in entries:
741
names.append(entry.name)
742
parents.append(entry.parent_id)
743
return self._merge_names(file_id, parents, names)
745
def _merge_names(self, file_id, parents, names):
746
"""Perform a merge on file_id names and parents"""
747
base_name, other_name, this_name = names
748
base_parent, other_parent, this_parent = parents
750
name_winner = self._three_way(*names)
752
parent_id_winner = self._three_way(*parents)
753
if this_name is None:
754
if name_winner == "this":
755
name_winner = "other"
756
if parent_id_winner == "this":
757
parent_id_winner = "other"
758
if name_winner == "this" and parent_id_winner == "this":
760
if name_winner == "conflict":
761
trans_id = self.tt.trans_id_file_id(file_id)
762
self._raw_conflicts.append(('name conflict', trans_id,
763
this_name, other_name))
764
if parent_id_winner == "conflict":
765
trans_id = self.tt.trans_id_file_id(file_id)
766
self._raw_conflicts.append(('parent conflict', trans_id,
767
this_parent, other_parent))
768
if other_name is None:
769
# it doesn't matter whether the result was 'other' or
770
# 'conflict'-- if there's no 'other', we leave it alone.
772
# if we get here, name_winner and parent_winner are set to safe values.
773
trans_id = self.tt.trans_id_file_id(file_id)
774
parent_id = parents[self.winner_idx[parent_id_winner]]
775
if parent_id is not None:
776
parent_trans_id = self.tt.trans_id_file_id(parent_id)
777
self.tt.adjust_path(names[self.winner_idx[name_winner]],
778
parent_trans_id, trans_id)
780
def merge_contents(self, file_id):
781
"""Performa a merge on file_id contents."""
782
def contents_pair(tree):
783
if file_id not in tree:
785
kind = tree.kind(file_id)
787
contents = tree.get_file_sha1(file_id)
788
elif kind == "symlink":
789
contents = tree.get_symlink_target(file_id)
792
return kind, contents
794
def contents_conflict():
795
trans_id = self.tt.trans_id_file_id(file_id)
796
name = self.tt.final_name(trans_id)
797
parent_id = self.tt.final_parent(trans_id)
798
if file_id in self.this_tree.inventory:
799
self.tt.unversion_file(trans_id)
800
if file_id in self.this_tree:
801
self.tt.delete_contents(trans_id)
802
file_group = self._dump_conflicts(name, parent_id, file_id,
804
self._raw_conflicts.append(('contents conflict', file_group))
806
# See SPOT run. run, SPOT, run.
807
# So we're not QUITE repeating ourselves; we do tricky things with
809
base_pair = contents_pair(self.base_tree)
810
other_pair = contents_pair(self.other_tree)
811
if base_pair == other_pair:
812
# OTHER introduced no changes
814
this_pair = contents_pair(self.this_tree)
815
if this_pair == other_pair:
816
# THIS and OTHER introduced the same changes
819
trans_id = self.tt.trans_id_file_id(file_id)
820
if this_pair == base_pair:
821
# only OTHER introduced changes
822
if file_id in self.this_tree:
823
# Remove any existing contents
824
self.tt.delete_contents(trans_id)
825
if file_id in self.other_tree:
826
# OTHER changed the file
827
create_by_entry(self.tt,
828
self.other_tree.inventory[file_id],
829
self.other_tree, trans_id)
830
if file_id not in self.this_tree.inventory:
831
self.tt.version_file(file_id, trans_id)
833
elif file_id in self.this_tree.inventory:
834
# OTHER deleted the file
835
self.tt.unversion_file(trans_id)
837
#BOTH THIS and OTHER introduced changes; scalar conflict
838
elif this_pair[0] == "file" and other_pair[0] == "file":
839
# THIS and OTHER are both files, so text merge. Either
840
# BASE is a file, or both converted to files, so at least we
841
# have agreement that output should be a file.
843
self.text_merge(file_id, trans_id)
845
return contents_conflict()
846
if file_id not in self.this_tree.inventory:
847
self.tt.version_file(file_id, trans_id)
849
self.tt.tree_kind(trans_id)
850
self.tt.delete_contents(trans_id)
855
# Scalar conflict, can't text merge. Dump conflicts
856
return contents_conflict()
858
def get_lines(self, tree, file_id):
859
"""Return the lines in a file, or an empty list."""
861
return tree.get_file(file_id).readlines()
865
def text_merge(self, file_id, trans_id):
866
"""Perform a three-way text merge on a file_id"""
867
# it's possible that we got here with base as a different type.
868
# if so, we just want two-way text conflicts.
869
if file_id in self.base_tree and \
870
self.base_tree.kind(file_id) == "file":
871
base_lines = self.get_lines(self.base_tree, file_id)
874
other_lines = self.get_lines(self.other_tree, file_id)
875
this_lines = self.get_lines(self.this_tree, file_id)
876
m3 = Merge3(base_lines, this_lines, other_lines,
877
is_cherrypick=self.cherrypick)
878
start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
879
if self.show_base is True:
880
base_marker = '|' * 7
884
def iter_merge3(retval):
885
retval["text_conflicts"] = False
886
for line in m3.merge_lines(name_a = "TREE",
887
name_b = "MERGE-SOURCE",
888
name_base = "BASE-REVISION",
889
start_marker=start_marker,
890
base_marker=base_marker,
891
reprocess=self.reprocess):
892
if line.startswith(start_marker):
893
retval["text_conflicts"] = True
894
yield line.replace(start_marker, '<' * 7)
898
merge3_iterator = iter_merge3(retval)
899
self.tt.create_file(merge3_iterator, trans_id)
900
if retval["text_conflicts"] is True:
901
self._raw_conflicts.append(('text conflict', trans_id))
902
name = self.tt.final_name(trans_id)
903
parent_id = self.tt.final_parent(trans_id)
904
file_group = self._dump_conflicts(name, parent_id, file_id,
905
this_lines, base_lines,
907
file_group.append(trans_id)
909
def _dump_conflicts(self, name, parent_id, file_id, this_lines=None,
910
base_lines=None, other_lines=None, set_version=False,
912
"""Emit conflict files.
913
If this_lines, base_lines, or other_lines are omitted, they will be
914
determined automatically. If set_version is true, the .OTHER, .THIS
915
or .BASE (in that order) will be created as versioned files.
917
data = [('OTHER', self.other_tree, other_lines),
918
('THIS', self.this_tree, this_lines)]
920
data.append(('BASE', self.base_tree, base_lines))
923
for suffix, tree, lines in data:
925
trans_id = self._conflict_file(name, parent_id, tree, file_id,
927
file_group.append(trans_id)
928
if set_version and not versioned:
929
self.tt.version_file(file_id, trans_id)
933
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
935
"""Emit a single conflict file."""
936
name = name + '.' + suffix
937
trans_id = self.tt.create_path(name, parent_id)
938
entry = tree.inventory[file_id]
939
create_by_entry(self.tt, entry, tree, trans_id, lines)
942
def merge_executable(self, file_id, file_status):
943
"""Perform a merge on the execute bit."""
944
executable = [self.executable(t, file_id) for t in (self.base_tree,
945
self.other_tree, self.this_tree)]
946
self._merge_executable(file_id, executable, file_status)
948
def _merge_executable(self, file_id, executable, file_status):
949
"""Perform a merge on the execute bit."""
950
base_executable, other_executable, this_executable = executable
951
if file_status == "deleted":
953
trans_id = self.tt.trans_id_file_id(file_id)
955
if self.tt.final_kind(trans_id) != "file":
959
winner = self._three_way(*executable)
960
if winner == "conflict":
961
# There must be a None in here, if we have a conflict, but we
962
# need executability since file status was not deleted.
963
if self.executable(self.other_tree, file_id) is None:
968
if file_status == "modified":
969
executability = this_executable
970
if executability is not None:
971
trans_id = self.tt.trans_id_file_id(file_id)
972
self.tt.set_executability(executability, trans_id)
974
assert winner == "other"
975
if file_id in self.other_tree:
976
executability = other_executable
977
elif file_id in self.this_tree:
978
executability = this_executable
979
elif file_id in self.base_tree:
980
executability = base_executable
981
if executability is not None:
982
trans_id = self.tt.trans_id_file_id(file_id)
983
self.tt.set_executability(executability, trans_id)
985
def cook_conflicts(self, fs_conflicts):
986
"""Convert all conflicts into a form that doesn't depend on trans_id"""
987
from conflicts import Conflict
989
self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
990
fp = FinalPaths(self.tt)
991
for conflict in self._raw_conflicts:
992
conflict_type = conflict[0]
993
if conflict_type in ('name conflict', 'parent conflict'):
994
trans_id = conflict[1]
995
conflict_args = conflict[2:]
996
if trans_id not in name_conflicts:
997
name_conflicts[trans_id] = {}
998
unique_add(name_conflicts[trans_id], conflict_type,
1000
if conflict_type == 'contents conflict':
1001
for trans_id in conflict[1]:
1002
file_id = self.tt.final_file_id(trans_id)
1003
if file_id is not None:
1005
path = fp.get_path(trans_id)
1006
for suffix in ('.BASE', '.THIS', '.OTHER'):
1007
if path.endswith(suffix):
1008
path = path[:-len(suffix)]
1010
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1011
self.cooked_conflicts.append(c)
1012
if conflict_type == 'text conflict':
1013
trans_id = conflict[1]
1014
path = fp.get_path(trans_id)
1015
file_id = self.tt.final_file_id(trans_id)
1016
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1017
self.cooked_conflicts.append(c)
1019
for trans_id, conflicts in name_conflicts.iteritems():
1021
this_parent, other_parent = conflicts['parent conflict']
1022
assert this_parent != other_parent
1024
this_parent = other_parent = \
1025
self.tt.final_file_id(self.tt.final_parent(trans_id))
1027
this_name, other_name = conflicts['name conflict']
1028
assert this_name != other_name
1030
this_name = other_name = self.tt.final_name(trans_id)
1031
other_path = fp.get_path(trans_id)
1032
if this_parent is not None and this_name is not None:
1033
this_parent_path = \
1034
fp.get_path(self.tt.trans_id_file_id(this_parent))
1035
this_path = pathjoin(this_parent_path, this_name)
1037
this_path = "<deleted>"
1038
file_id = self.tt.final_file_id(trans_id)
1039
c = Conflict.factory('path conflict', path=this_path,
1040
conflict_path=other_path, file_id=file_id)
1041
self.cooked_conflicts.append(c)
1042
self.cooked_conflicts.sort(key=Conflict.sort_key)
1045
class WeaveMerger(Merge3Merger):
1046
"""Three-way tree merger, text weave merger."""
1047
supports_reprocess = True
1048
supports_show_base = False
1049
supports_reverse_cherrypick = False
1050
history_based = True
1052
def _merged_lines(self, file_id):
1053
"""Generate the merged lines.
1054
There is no distinction between lines that are meant to contain <<<<<<<
1058
base = self.base_tree
1061
plan = self.this_tree.plan_file_merge(file_id, self.other_tree,
1063
if 'merge' in debug.debug_flags:
1065
trans_id = self.tt.trans_id_file_id(file_id)
1066
name = self.tt.final_name(trans_id) + '.plan'
1067
contents = ('%10s|%s' % l for l in plan)
1068
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1069
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1070
'>>>>>>> MERGE-SOURCE\n')
1071
return textmerge.merge_lines(self.reprocess)
1073
def text_merge(self, file_id, trans_id):
1074
"""Perform a (weave) text merge for a given file and file-id.
1075
If conflicts are encountered, .THIS and .OTHER files will be emitted,
1076
and a conflict will be noted.
1078
lines, conflicts = self._merged_lines(file_id)
1080
# Note we're checking whether the OUTPUT is binary in this case,
1081
# because we don't want to get into weave merge guts.
1082
check_text_lines(lines)
1083
self.tt.create_file(lines, trans_id)
1085
self._raw_conflicts.append(('text conflict', trans_id))
1086
name = self.tt.final_name(trans_id)
1087
parent_id = self.tt.final_parent(trans_id)
1088
file_group = self._dump_conflicts(name, parent_id, file_id,
1090
file_group.append(trans_id)
1093
class LCAMerger(WeaveMerger):
1095
def _merged_lines(self, file_id):
1096
"""Generate the merged lines.
1097
There is no distinction between lines that are meant to contain <<<<<<<
1101
base = self.base_tree
1104
plan = self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1106
if 'merge' in debug.debug_flags:
1108
trans_id = self.tt.trans_id_file_id(file_id)
1109
name = self.tt.final_name(trans_id) + '.plan'
1110
contents = ('%10s|%s' % l for l in plan)
1111
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1112
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1113
'>>>>>>> MERGE-SOURCE\n')
1114
return textmerge.merge_lines(self.reprocess)
1117
class Diff3Merger(Merge3Merger):
1118
"""Three-way merger using external diff3 for text merging"""
1120
def dump_file(self, temp_dir, name, tree, file_id):
1121
out_path = pathjoin(temp_dir, name)
1122
out_file = open(out_path, "wb")
1124
in_file = tree.get_file(file_id)
1125
for line in in_file:
1126
out_file.write(line)
1131
def text_merge(self, file_id, trans_id):
1132
"""Perform a diff3 merge using a specified file-id and trans-id.
1133
If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
1134
will be dumped, and a will be conflict noted.
1137
temp_dir = osutils.mkdtemp(prefix="bzr-")
1139
new_file = pathjoin(temp_dir, "new")
1140
this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
1141
base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
1142
other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
1143
status = bzrlib.patch.diff3(new_file, this, base, other)
1144
if status not in (0, 1):
1145
raise BzrError("Unhandled diff3 exit code")
1146
f = open(new_file, 'rb')
1148
self.tt.create_file(f, trans_id)
1152
name = self.tt.final_name(trans_id)
1153
parent_id = self.tt.final_parent(trans_id)
1154
self._dump_conflicts(name, parent_id, file_id)
1155
self._raw_conflicts.append(('text conflict', trans_id))
1157
osutils.rmtree(temp_dir)
1160
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
1162
merge_type=Merge3Merger,
1163
interesting_ids=None,
1167
interesting_files=None,
1170
change_reporter=None):
1171
"""Primary interface for merging.
1173
typical use is probably
1174
'merge_inner(branch, branch.get_revision_tree(other_revision),
1175
branch.get_revision_tree(base_revision))'
1177
if this_tree is None:
1178
raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
1179
"parameter as of bzrlib version 0.8.")
1180
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1181
pb=pb, change_reporter=change_reporter)
1182
merger.backup_files = backup_files
1183
merger.merge_type = merge_type
1184
merger.interesting_ids = interesting_ids
1185
merger.ignore_zero = ignore_zero
1186
if interesting_files:
1187
assert not interesting_ids, ('Only supply interesting_ids'
1188
' or interesting_files')
1189
merger.interesting_files = interesting_files
1190
merger.show_base = show_base
1191
merger.reprocess = reprocess
1192
merger.other_rev_id = other_rev_id
1193
merger.other_basis = other_rev_id
1194
get_revision_id = getattr(base_tree, 'get_revision_id', None)
1195
if get_revision_id is None:
1196
get_revision_id = base_tree.last_revision
1197
merger.set_base_revision(get_revision_id(), this_branch)
1198
return merger.do_merge()
1200
def get_merge_type_registry():
1201
"""Merge type registry is in bzrlib.option to avoid circular imports.
1203
This method provides a sanctioned way to retrieve it.
1205
from bzrlib import option
1206
return option._merge_type_registry
1209
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1210
def status_a(revision, text):
1211
if revision in ancestors_b:
1212
return 'killed-b', text
1214
return 'new-a', text
1216
def status_b(revision, text):
1217
if revision in ancestors_a:
1218
return 'killed-a', text
1220
return 'new-b', text
1222
plain_a = [t for (a, t) in annotated_a]
1223
plain_b = [t for (a, t) in annotated_b]
1224
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
1225
blocks = matcher.get_matching_blocks()
1228
for ai, bi, l in blocks:
1229
# process all mismatched sections
1230
# (last mismatched section is handled because blocks always
1231
# includes a 0-length last block)
1232
for revision, text in annotated_a[a_cur:ai]:
1233
yield status_a(revision, text)
1234
for revision, text in annotated_b[b_cur:bi]:
1235
yield status_b(revision, text)
1237
# and now the matched section
1240
for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
1241
assert text_a == text_b
1242
yield "unchanged", text_a
1245
class _PlanMergeBase(object):
1247
def __init__(self, a_rev, b_rev, vf):
1250
:param a_rev: Revision-id of one revision to merge
1251
:param b_rev: Revision-id of the other revision to merge
1252
:param vf: A versionedfile containing both revisions
1256
self.lines_a = vf.get_lines(a_rev)
1257
self.lines_b = vf.get_lines(b_rev)
1259
self._last_lines = None
1260
self._last_lines_revision_id = None
1261
self._cached_matching_blocks = {}
1263
def plan_merge(self):
1264
"""Generate a 'plan' for merging the two revisions.
1266
This involves comparing their texts and determining the cause of
1267
differences. If text A has a line and text B does not, then either the
1268
line was added to text A, or it was deleted from B. Once the causes
1269
are combined, they are written out in the format described in
1270
VersionedFile.plan_merge
1272
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1273
unique_a, unique_b = self._unique_lines(blocks)
1274
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
1275
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
1276
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
1278
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1281
for i, j, n in blocks:
1282
for a_index in range(last_i, i):
1283
if a_index in new_a:
1284
if a_index in killed_b:
1285
yield 'conflicted-a', self.lines_a[a_index]
1287
yield 'new-a', self.lines_a[a_index]
1289
yield 'killed-b', self.lines_a[a_index]
1290
for b_index in range(last_j, j):
1291
if b_index in new_b:
1292
if b_index in killed_a:
1293
yield 'conflicted-b', self.lines_b[b_index]
1295
yield 'new-b', self.lines_b[b_index]
1297
yield 'killed-a', self.lines_b[b_index]
1298
# handle common lines
1299
for a_index in range(i, i+n):
1300
yield 'unchanged', self.lines_a[a_index]
1304
def _get_matching_blocks(self, left_revision, right_revision):
1305
"""Return a description of which sections of two revisions match.
1307
See SequenceMatcher.get_matching_blocks
1309
cached = self._cached_matching_blocks.get((left_revision,
1311
if cached is not None:
1313
if self._last_lines_revision_id == left_revision:
1314
left_lines = self._last_lines
1316
left_lines = self.vf.get_lines(left_revision)
1317
right_lines = self.vf.get_lines(right_revision)
1318
self._last_lines = right_lines
1319
self._last_lines_revision_id = right_revision
1320
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1322
return matcher.get_matching_blocks()
1324
def _unique_lines(self, matching_blocks):
1325
"""Analyse matching_blocks to determine which lines are unique
1327
:return: a tuple of (unique_left, unique_right), where the values are
1328
sets of line numbers of unique lines.
1334
for i, j, n in matching_blocks:
1335
unique_left.extend(range(last_i, i))
1336
unique_right.extend(range(last_j, j))
1339
return unique_left, unique_right
1342
def _subtract_plans(old_plan, new_plan):
1343
"""Remove changes from new_plan that came from old_plan.
1345
It is assumed that the difference between the old_plan and new_plan
1346
is their choice of 'b' text.
1348
All lines from new_plan that differ from old_plan are emitted
1349
verbatim. All lines from new_plan that match old_plan but are
1350
not about the 'b' revision are emitted verbatim.
1352
Lines that match and are about the 'b' revision are the lines we
1353
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
1354
is skipped entirely.
1356
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1359
for i, j, n in matcher.get_matching_blocks():
1360
for jj in range(last_j, j):
1362
for jj in range(j, j+n):
1363
plan_line = new_plan[jj]
1364
if plan_line[0] == 'new-b':
1366
elif plan_line[0] == 'killed-b':
1367
yield 'unchanged', plan_line[1]
1373
class _PlanMerge(_PlanMergeBase):
1374
"""Plan an annotate merge using on-the-fly annotation"""
1376
def __init__(self, a_rev, b_rev, vf):
1377
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1378
a_ancestry = set(vf.get_ancestry(a_rev, topo_sorted=False))
1379
b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
1380
self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
1382
def _determine_status(self, revision_id, unique_line_numbers):
1383
"""Determines the status unique lines versus all lcas.
1385
Basically, determines why the line is unique to this revision.
1387
A line may be determined new or killed, but not both.
1389
:param revision_id: The id of the revision in which the lines are
1391
:param unique_line_numbers: The line numbers of unique lines.
1392
:return a tuple of (new_this, killed_other):
1394
new = self._find_new(revision_id)
1395
killed = set(unique_line_numbers).difference(new)
1398
def _find_new(self, version_id):
1399
"""Determine which lines are new in the ancestry of this version.
1401
If a lines is present in this version, and not present in any
1402
common ancestor, it is considered new.
1404
if version_id not in self.uncommon:
1406
parents = self.vf.get_parents(version_id)
1407
if len(parents) == 0:
1408
return set(range(len(self.vf.get_lines(version_id))))
1410
for parent in parents:
1411
blocks = self._get_matching_blocks(version_id, parent)
1412
result, unused = self._unique_lines(blocks)
1413
parent_new = self._find_new(parent)
1414
for i, j, n in blocks:
1415
for ii, jj in [(i+r, j+r) for r in range(n)]:
1416
if jj in parent_new:
1421
new.intersection_update(result)
1425
class _PlanLCAMerge(_PlanMergeBase):
1427
This merge algorithm differs from _PlanMerge in that:
1428
1. comparisons are done against LCAs only
1429
2. cases where a contested line is new versus one LCA but old versus
1430
another are marked as conflicts, by emitting the line as conflicted-a
1433
This is faster, and hopefully produces more useful output.
1436
def __init__(self, a_rev, b_rev, vf, graph):
1437
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1438
self.lcas = graph.find_lca(a_rev, b_rev)
1439
for lca in self.lcas:
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
