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
winner = self._three_way(*executable)
954
if winner == "conflict":
955
# There must be a None in here, if we have a conflict, but we
956
# need executability since file status was not deleted.
957
if self.executable(self.other_tree, file_id) is None:
961
if winner == 'this' and file_status != "modified":
963
trans_id = self.tt.trans_id_file_id(file_id)
965
if self.tt.final_kind(trans_id) != "file":
970
executability = this_executable
972
assert winner == "other"
973
if file_id in self.other_tree:
974
executability = other_executable
975
elif file_id in self.this_tree:
976
executability = this_executable
977
elif file_id in self.base_tree:
978
executability = base_executable
979
if executability is not None:
980
trans_id = self.tt.trans_id_file_id(file_id)
981
self.tt.set_executability(executability, trans_id)
983
def cook_conflicts(self, fs_conflicts):
984
"""Convert all conflicts into a form that doesn't depend on trans_id"""
985
from conflicts import Conflict
987
self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
988
fp = FinalPaths(self.tt)
989
for conflict in self._raw_conflicts:
990
conflict_type = conflict[0]
991
if conflict_type in ('name conflict', 'parent conflict'):
992
trans_id = conflict[1]
993
conflict_args = conflict[2:]
994
if trans_id not in name_conflicts:
995
name_conflicts[trans_id] = {}
996
unique_add(name_conflicts[trans_id], conflict_type,
998
if conflict_type == 'contents conflict':
999
for trans_id in conflict[1]:
1000
file_id = self.tt.final_file_id(trans_id)
1001
if file_id is not None:
1003
path = fp.get_path(trans_id)
1004
for suffix in ('.BASE', '.THIS', '.OTHER'):
1005
if path.endswith(suffix):
1006
path = path[:-len(suffix)]
1008
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1009
self.cooked_conflicts.append(c)
1010
if conflict_type == 'text conflict':
1011
trans_id = conflict[1]
1012
path = fp.get_path(trans_id)
1013
file_id = self.tt.final_file_id(trans_id)
1014
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1015
self.cooked_conflicts.append(c)
1017
for trans_id, conflicts in name_conflicts.iteritems():
1019
this_parent, other_parent = conflicts['parent conflict']
1020
assert this_parent != other_parent
1022
this_parent = other_parent = \
1023
self.tt.final_file_id(self.tt.final_parent(trans_id))
1025
this_name, other_name = conflicts['name conflict']
1026
assert this_name != other_name
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:
1185
assert not interesting_ids, ('Only supply interesting_ids'
1186
' or interesting_files')
1187
merger.interesting_files = interesting_files
1188
merger.show_base = show_base
1189
merger.reprocess = reprocess
1190
merger.other_rev_id = other_rev_id
1191
merger.other_basis = other_rev_id
1192
get_revision_id = getattr(base_tree, 'get_revision_id', None)
1193
if get_revision_id is None:
1194
get_revision_id = base_tree.last_revision
1195
merger.set_base_revision(get_revision_id(), this_branch)
1196
return merger.do_merge()
1198
def get_merge_type_registry():
1199
"""Merge type registry is in bzrlib.option to avoid circular imports.
1201
This method provides a sanctioned way to retrieve it.
1203
from bzrlib import option
1204
return option._merge_type_registry
1207
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1208
def status_a(revision, text):
1209
if revision in ancestors_b:
1210
return 'killed-b', text
1212
return 'new-a', text
1214
def status_b(revision, text):
1215
if revision in ancestors_a:
1216
return 'killed-a', text
1218
return 'new-b', text
1220
plain_a = [t for (a, t) in annotated_a]
1221
plain_b = [t for (a, t) in annotated_b]
1222
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
1223
blocks = matcher.get_matching_blocks()
1226
for ai, bi, l in blocks:
1227
# process all mismatched sections
1228
# (last mismatched section is handled because blocks always
1229
# includes a 0-length last block)
1230
for revision, text in annotated_a[a_cur:ai]:
1231
yield status_a(revision, text)
1232
for revision, text in annotated_b[b_cur:bi]:
1233
yield status_b(revision, text)
1235
# and now the matched section
1238
for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
1239
assert text_a == text_b
1240
yield "unchanged", text_a
1243
class _PlanMergeBase(object):
1245
def __init__(self, a_rev, b_rev, vf):
1248
:param a_rev: Revision-id of one revision to merge
1249
:param b_rev: Revision-id of the other revision to merge
1250
:param vf: A versionedfile containing both revisions
1254
self.lines_a = vf.get_lines(a_rev)
1255
self.lines_b = vf.get_lines(b_rev)
1257
self._last_lines = None
1258
self._last_lines_revision_id = None
1259
self._cached_matching_blocks = {}
1261
def plan_merge(self):
1262
"""Generate a 'plan' for merging the two revisions.
1264
This involves comparing their texts and determining the cause of
1265
differences. If text A has a line and text B does not, then either the
1266
line was added to text A, or it was deleted from B. Once the causes
1267
are combined, they are written out in the format described in
1268
VersionedFile.plan_merge
1270
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1271
unique_a, unique_b = self._unique_lines(blocks)
1272
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
1273
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
1274
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
1276
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1279
for i, j, n in blocks:
1280
for a_index in range(last_i, i):
1281
if a_index in new_a:
1282
if a_index in killed_b:
1283
yield 'conflicted-a', self.lines_a[a_index]
1285
yield 'new-a', self.lines_a[a_index]
1287
yield 'killed-b', self.lines_a[a_index]
1288
for b_index in range(last_j, j):
1289
if b_index in new_b:
1290
if b_index in killed_a:
1291
yield 'conflicted-b', self.lines_b[b_index]
1293
yield 'new-b', self.lines_b[b_index]
1295
yield 'killed-a', self.lines_b[b_index]
1296
# handle common lines
1297
for a_index in range(i, i+n):
1298
yield 'unchanged', self.lines_a[a_index]
1302
def _get_matching_blocks(self, left_revision, right_revision):
1303
"""Return a description of which sections of two revisions match.
1305
See SequenceMatcher.get_matching_blocks
1307
cached = self._cached_matching_blocks.get((left_revision,
1309
if cached is not None:
1311
if self._last_lines_revision_id == left_revision:
1312
left_lines = self._last_lines
1314
left_lines = self.vf.get_lines(left_revision)
1315
right_lines = self.vf.get_lines(right_revision)
1316
self._last_lines = right_lines
1317
self._last_lines_revision_id = right_revision
1318
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1320
return matcher.get_matching_blocks()
1322
def _unique_lines(self, matching_blocks):
1323
"""Analyse matching_blocks to determine which lines are unique
1325
:return: a tuple of (unique_left, unique_right), where the values are
1326
sets of line numbers of unique lines.
1332
for i, j, n in matching_blocks:
1333
unique_left.extend(range(last_i, i))
1334
unique_right.extend(range(last_j, j))
1337
return unique_left, unique_right
1340
def _subtract_plans(old_plan, new_plan):
1341
"""Remove changes from new_plan that came from old_plan.
1343
It is assumed that the difference between the old_plan and new_plan
1344
is their choice of 'b' text.
1346
All lines from new_plan that differ from old_plan are emitted
1347
verbatim. All lines from new_plan that match old_plan but are
1348
not about the 'b' revision are emitted verbatim.
1350
Lines that match and are about the 'b' revision are the lines we
1351
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
1352
is skipped entirely.
1354
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1357
for i, j, n in matcher.get_matching_blocks():
1358
for jj in range(last_j, j):
1360
for jj in range(j, j+n):
1361
plan_line = new_plan[jj]
1362
if plan_line[0] == 'new-b':
1364
elif plan_line[0] == 'killed-b':
1365
yield 'unchanged', plan_line[1]
1371
class _PlanMerge(_PlanMergeBase):
1372
"""Plan an annotate merge using on-the-fly annotation"""
1374
def __init__(self, a_rev, b_rev, vf):
1375
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1376
a_ancestry = set(vf.get_ancestry(a_rev, topo_sorted=False))
1377
b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
1378
self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
1380
def _determine_status(self, revision_id, unique_line_numbers):
1381
"""Determines the status unique lines versus all lcas.
1383
Basically, determines why the line is unique to this revision.
1385
A line may be determined new or killed, but not both.
1387
:param revision_id: The id of the revision in which the lines are
1389
:param unique_line_numbers: The line numbers of unique lines.
1390
:return a tuple of (new_this, killed_other):
1392
new = self._find_new(revision_id)
1393
killed = set(unique_line_numbers).difference(new)
1396
def _find_new(self, version_id):
1397
"""Determine which lines are new in the ancestry of this version.
1399
If a lines is present in this version, and not present in any
1400
common ancestor, it is considered new.
1402
if version_id not in self.uncommon:
1404
parents = self.vf.get_parent_map([version_id])[version_id]
1405
if len(parents) == 0:
1406
return set(range(len(self.vf.get_lines(version_id))))
1408
for parent in parents:
1409
blocks = self._get_matching_blocks(version_id, parent)
1410
result, unused = self._unique_lines(blocks)
1411
parent_new = self._find_new(parent)
1412
for i, j, n in blocks:
1413
for ii, jj in [(i+r, j+r) for r in range(n)]:
1414
if jj in parent_new:
1419
new.intersection_update(result)
1423
class _PlanLCAMerge(_PlanMergeBase):
1425
This merge algorithm differs from _PlanMerge in that:
1426
1. comparisons are done against LCAs only
1427
2. cases where a contested line is new versus one LCA but old versus
1428
another are marked as conflicts, by emitting the line as conflicted-a
1431
This is faster, and hopefully produces more useful output.
1434
def __init__(self, a_rev, b_rev, vf, graph):
1435
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1436
self.lcas = graph.find_lca(a_rev, b_rev)
1437
for lca in self.lcas:
1438
lca_lines = self.vf.get_lines(lca)
1439
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
1441
blocks = list(matcher.get_matching_blocks())
1442
self._cached_matching_blocks[(a_rev, lca)] = blocks
1443
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
1445
blocks = list(matcher.get_matching_blocks())
1446
self._cached_matching_blocks[(b_rev, lca)] = blocks
1448
def _determine_status(self, revision_id, unique_line_numbers):
1449
"""Determines the status unique lines versus all lcas.
1451
Basically, determines why the line is unique to this revision.
1453
A line may be determined new, killed, or both.
1455
If a line is determined new, that means it was not present in at least
1456
one LCA, and is not present in the other merge revision.
1458
If a line is determined killed, that means the line was present in
1461
If a line is killed and new, this indicates that the two merge
1462
revisions contain differing conflict resolutions.
1463
:param revision_id: The id of the revision in which the lines are
1465
:param unique_line_numbers: The line numbers of unique lines.
1466
:return a tuple of (new_this, killed_other):
1470
unique_line_numbers = set(unique_line_numbers)
1471
for lca in self.lcas:
1472
blocks = self._get_matching_blocks(revision_id, lca)
1473
unique_vs_lca, _ignored = self._unique_lines(blocks)
1474
new.update(unique_line_numbers.intersection(unique_vs_lca))
1475
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
bzrlib/merge.py
