1
# Copyright (C) 2005, 2006 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
28
revision as _mod_revision,
30
from bzrlib.branch import Branch
31
from bzrlib.conflicts import ConflictList, Conflict
32
from bzrlib.errors import (BzrCommandError,
42
WorkingTreeNotRevision,
45
from bzrlib.merge3 import Merge3
46
from bzrlib.osutils import rename, pathjoin
47
from progress import DummyProgress, ProgressPhase
48
from bzrlib.revision import (NULL_REVISION, ensure_null)
49
from bzrlib.textfile import check_text_lines
50
from bzrlib.trace import mutter, warning, note
51
from bzrlib.transform import (TreeTransform, resolve_conflicts, cook_conflicts,
52
conflict_pass, FinalPaths, create_by_entry,
53
unique_add, ROOT_PARENT)
54
from bzrlib.versionedfile import PlanWeaveMerge
57
# TODO: Report back as changes are merged in
60
def transform_tree(from_tree, to_tree, interesting_ids=None):
61
merge_inner(from_tree.branch, to_tree, from_tree, ignore_zero=True,
62
interesting_ids=interesting_ids, this_tree=from_tree)
66
def __init__(self, this_branch, other_tree=None, base_tree=None,
67
this_tree=None, pb=DummyProgress(), change_reporter=None,
70
assert this_tree is not None, "this_tree is required"
71
self.this_branch = this_branch
72
self.this_basis = _mod_revision.ensure_null(
73
this_branch.last_revision())
74
self.this_rev_id = None
75
self.this_tree = this_tree
76
self.this_revision_tree = None
77
self.this_basis_tree = None
78
self.other_tree = other_tree
79
self.other_branch = None
80
self.base_tree = base_tree
81
self.ignore_zero = False
82
self.backup_files = False
83
self.interesting_ids = None
84
self.interesting_files = None
85
self.show_base = False
86
self.reprocess = False
89
self.recurse = recurse
90
self.change_reporter = change_reporter
91
self._cached_trees = {}
94
def from_uncommitted(tree, other_tree, pb):
95
"""Return a Merger for uncommitted changes in other_tree.
97
:param tree: The tree to merge into
98
:param other_tree: The tree to get uncommitted changes from
99
:param pb: A progress indicator
101
merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,
103
merger.base_rev_id = merger.base_tree.get_revision_id()
104
merger.other_rev_id = None
108
def from_mergeable(klass, tree, mergeable, pb):
109
"""Return a Merger for a bundle or merge directive.
111
:param tree: The tree to merge changes into
112
:param mergeable: A merge directive or bundle
113
:param pb: A progress indicator
115
mergeable.install_revisions(tree.branch.repository)
116
base_revision_id, other_revision_id, verified =\
117
mergeable.get_merge_request(tree.branch.repository)
118
if (base_revision_id != _mod_revision.NULL_REVISION and
119
tree.branch.repository.get_graph().is_ancestor(
120
base_revision_id, tree.branch.last_revision())):
121
base_revision_id = None
123
warning('Performing cherrypick')
124
merger = klass.from_revision_ids(pb, tree, other_revision_id,
126
return merger, verified
129
def from_revision_ids(pb, this, other, base=None, other_branch=None,
131
"""Return a Merger for revision-ids.
133
:param tree: The tree to merge changes into
134
:param other: The revision-id to use as OTHER
135
:param base: The revision-id to use as BASE. If not specified, will
137
:param other_branch: A branch containing the other revision-id. If
138
not supplied, this.branch is used.
139
:param base_branch: A branch containing the base revision-id. If
140
not supplied, other_branch or this.branch will be used.
141
:param pb: A progress indicator
143
merger = Merger(this.branch, this_tree=this, pb=pb)
144
if other_branch is None:
145
other_branch = this.branch
146
merger.set_other_revision(other, other_branch)
150
if base_branch is None:
151
base_branch = other_branch
152
merger.set_base_revision(base, base_branch)
155
def revision_tree(self, revision_id, branch=None):
156
if revision_id not in self._cached_trees:
158
branch = self.this_branch
160
tree = self.this_tree.revision_tree(revision_id)
161
except errors.NoSuchRevisionInTree:
162
tree = branch.repository.revision_tree(revision_id)
163
self._cached_trees[revision_id] = tree
164
return self._cached_trees[revision_id]
166
def _get_tree(self, treespec, possible_transports=None):
167
from bzrlib import workingtree
168
location, revno = treespec
170
tree = workingtree.WorkingTree.open_containing(location)[0]
171
return tree.branch, tree
172
branch = Branch.open_containing(location, possible_transports)[0]
174
revision_id = branch.last_revision()
176
revision_id = branch.get_rev_id(revno)
177
revision_id = ensure_null(revision_id)
178
return branch, self.revision_tree(revision_id, branch)
180
def ensure_revision_trees(self):
181
if self.this_revision_tree is None:
182
self.this_basis_tree = self.revision_tree(self.this_basis)
183
if self.this_basis == self.this_rev_id:
184
self.this_revision_tree = self.this_basis_tree
186
if self.other_rev_id is None:
187
other_basis_tree = self.revision_tree(self.other_basis)
188
changes = other_basis_tree.changes_from(self.other_tree)
189
if changes.has_changed():
190
raise WorkingTreeNotRevision(self.this_tree)
191
other_rev_id = self.other_basis
192
self.other_tree = other_basis_tree
194
def file_revisions(self, file_id):
195
self.ensure_revision_trees()
196
def get_id(tree, file_id):
197
revision_id = tree.inventory[file_id].revision
198
assert revision_id is not None
200
if self.this_rev_id is None:
201
if self.this_basis_tree.get_file_sha1(file_id) != \
202
self.this_tree.get_file_sha1(file_id):
203
raise WorkingTreeNotRevision(self.this_tree)
205
trees = (self.this_basis_tree, self.other_tree)
206
return [get_id(tree, file_id) for tree in trees]
208
def check_basis(self, check_clean, require_commits=True):
209
if self.this_basis is None and require_commits is True:
210
raise BzrCommandError("This branch has no commits."
211
" (perhaps you would prefer 'bzr pull')")
214
if self.this_basis != self.this_rev_id:
215
raise errors.UncommittedChanges(self.this_tree)
217
def compare_basis(self):
219
basis_tree = self.revision_tree(self.this_tree.last_revision())
220
except errors.RevisionNotPresent:
221
basis_tree = self.this_tree.basis_tree()
222
changes = self.this_tree.changes_from(basis_tree)
223
if not changes.has_changed():
224
self.this_rev_id = self.this_basis
226
def set_interesting_files(self, file_list):
227
self.interesting_files = file_list
229
def set_pending(self):
230
if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:
234
def _add_parent(self):
235
new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
236
new_parent_trees = []
237
for revision_id in new_parents:
239
tree = self.revision_tree(revision_id)
240
except errors.RevisionNotPresent:
244
new_parent_trees.append((revision_id, tree))
246
self.this_tree.set_parent_trees(new_parent_trees,
247
allow_leftmost_as_ghost=True)
249
for _revision_id, tree in new_parent_trees:
253
def set_other(self, other_revision, possible_transports=None):
254
"""Set the revision and tree to merge from.
256
This sets the other_tree, other_rev_id, other_basis attributes.
258
:param other_revision: The [path, revision] list to merge from.
260
self.other_branch, self.other_tree = self._get_tree(other_revision,
262
if other_revision[1] == -1:
263
self.other_rev_id = _mod_revision.ensure_null(
264
self.other_branch.last_revision())
265
if _mod_revision.is_null(self.other_rev_id):
266
raise NoCommits(self.other_branch)
267
self.other_basis = self.other_rev_id
268
elif other_revision[1] is not None:
269
self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
270
self.other_basis = self.other_rev_id
272
self.other_rev_id = None
273
self.other_basis = self.other_branch.last_revision()
274
if self.other_basis is None:
275
raise NoCommits(self.other_branch)
276
if self.other_rev_id is not None:
277
self._cached_trees[self.other_rev_id] = self.other_tree
278
self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)
280
def set_other_revision(self, revision_id, other_branch):
281
"""Set 'other' based on a branch and revision id
283
:param revision_id: The revision to use for a tree
284
:param other_branch: The branch containing this tree
286
self.other_rev_id = revision_id
287
self.other_branch = other_branch
288
self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
289
self.other_tree = self.revision_tree(revision_id)
290
self.other_basis = revision_id
292
def set_base_revision(self, revision_id, branch):
293
"""Set 'base' based on a branch and revision id
295
:param revision_id: The revision to use for a tree
296
:param branch: The branch containing this tree
298
self.base_rev_id = revision_id
299
self.base_branch = branch
300
self._maybe_fetch(branch, self.this_branch, revision_id)
301
self.base_tree = self.revision_tree(revision_id)
302
graph = self.this_branch.repository.get_graph()
303
self.base_is_ancestor = graph.is_ancestor(self.base_rev_id,
305
self.base_is_other_ancestor = graph.is_ancestor(self.base_rev_id,
308
def _maybe_fetch(self, source, target, revision_id):
309
if not source.repository.has_same_location(target.repository):
310
target.fetch(source, revision_id)
313
this_repo = self.this_branch.repository
314
graph = this_repo.get_graph()
315
revisions = [ensure_null(self.this_basis),
316
ensure_null(self.other_basis)]
317
if NULL_REVISION in revisions:
318
self.base_rev_id = NULL_REVISION
320
self.base_rev_id, steps = graph.find_unique_lca(revisions[0],
321
revisions[1], count_steps=True)
322
if self.base_rev_id == NULL_REVISION:
323
raise UnrelatedBranches()
325
warning('Warning: criss-cross merge encountered. See bzr'
326
' help criss-cross.')
327
self.base_tree = self.revision_tree(self.base_rev_id)
328
self.base_is_ancestor = True
329
self.base_is_other_ancestor = True
331
def set_base(self, base_revision):
332
"""Set the base revision to use for the merge.
334
:param base_revision: A 2-list containing a path and revision number.
336
mutter("doing merge() with no base_revision specified")
337
if base_revision == [None, None]:
340
base_branch, self.base_tree = self._get_tree(base_revision)
341
if base_revision[1] == -1:
342
self.base_rev_id = base_branch.last_revision()
343
elif base_revision[1] is None:
344
self.base_rev_id = _mod_revision.NULL_REVISION
346
self.base_rev_id = _mod_revision.ensure_null(
347
base_branch.get_rev_id(base_revision[1]))
348
self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
349
graph = self.this_branch.repository.get_graph()
350
self.base_is_ancestor = graph.is_ancestor(self.base_rev_id,
352
self.base_is_other_ancestor = graph.is_ancestor(self.base_rev_id,
356
kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
357
'other_tree': self.other_tree,
358
'interesting_ids': self.interesting_ids,
359
'interesting_files': self.interesting_files,
361
if self.merge_type.requires_base:
362
kwargs['base_tree'] = self.base_tree
363
if self.merge_type.supports_reprocess:
364
kwargs['reprocess'] = self.reprocess
366
raise BzrError("Conflict reduction is not supported for merge"
367
" type %s." % self.merge_type)
368
if self.merge_type.supports_show_base:
369
kwargs['show_base'] = self.show_base
371
raise BzrError("Showing base is not supported for this"
372
" merge type. %s" % self.merge_type)
373
if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
374
and not self.base_is_other_ancestor):
375
raise errors.CannotReverseCherrypick()
376
if self.merge_type.history_based:
377
kwargs['cherrypick'] = (not self.base_is_ancestor or
378
not self.base_is_other_ancestor)
379
self.this_tree.lock_tree_write()
380
if self.base_tree is not None:
381
self.base_tree.lock_read()
382
if self.other_tree is not None:
383
self.other_tree.lock_read()
385
merge = self.merge_type(pb=self._pb,
386
change_reporter=self.change_reporter,
388
if self.recurse == 'down':
389
for path, file_id in self.this_tree.iter_references():
390
sub_tree = self.this_tree.get_nested_tree(file_id, path)
391
other_revision = self.other_tree.get_reference_revision(
393
if other_revision == sub_tree.last_revision():
395
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
396
sub_merge.merge_type = self.merge_type
397
relpath = self.this_tree.relpath(path)
398
other_branch = self.other_branch.reference_parent(file_id, relpath)
399
sub_merge.set_other_revision(other_revision, other_branch)
400
base_revision = self.base_tree.get_reference_revision(file_id)
401
sub_merge.base_tree = \
402
sub_tree.branch.repository.revision_tree(base_revision)
406
if self.other_tree is not None:
407
self.other_tree.unlock()
408
if self.base_tree is not None:
409
self.base_tree.unlock()
410
self.this_tree.unlock()
411
if len(merge.cooked_conflicts) == 0:
412
if not self.ignore_zero:
413
note("All changes applied successfully.")
415
note("%d conflicts encountered." % len(merge.cooked_conflicts))
417
return len(merge.cooked_conflicts)
420
class Merge3Merger(object):
421
"""Three-way merger that uses the merge3 text merger"""
423
supports_reprocess = True
424
supports_show_base = True
425
history_based = False
426
supports_reverse_cherrypick = True
427
winner_idx = {"this": 2, "other": 1, "conflict": 1}
429
def __init__(self, working_tree, this_tree, base_tree, other_tree,
430
interesting_ids=None, reprocess=False, show_base=False,
431
pb=DummyProgress(), pp=None, change_reporter=None,
432
interesting_files=None):
433
"""Initialize the merger object and perform the merge.
435
:param working_tree: The working tree to apply the merge to
436
:param this_tree: The local tree in the merge operation
437
:param base_tree: The common tree in the merge operation
438
:param other_tree: The other other tree to merge changes from
439
:param interesting_ids: The file_ids of files that should be
440
participate in the merge. May not be combined with
442
:param: reprocess If True, perform conflict-reduction processing.
443
:param show_base: If True, show the base revision in text conflicts.
444
(incompatible with reprocess)
445
:param pb: A Progress bar
446
:param pp: A ProgressPhase object
447
:param change_reporter: An object that should report changes made
448
:param interesting_files: The tree-relative paths of files that should
449
participate in the merge. If these paths refer to directories,
450
the contents of those directories will also be included. May not
451
be combined with interesting_ids. If neither interesting_files nor
452
interesting_ids is specified, all files may participate in the
455
object.__init__(self)
456
if interesting_files is not None:
457
assert interesting_ids is None
458
self.interesting_ids = interesting_ids
459
self.interesting_files = interesting_files
460
self.this_tree = working_tree
461
self.this_tree.lock_tree_write()
462
self.base_tree = base_tree
463
self.base_tree.lock_read()
464
self.other_tree = other_tree
465
self.other_tree.lock_read()
466
self._raw_conflicts = []
467
self.cooked_conflicts = []
468
self.reprocess = reprocess
469
self.show_base = show_base
472
self.change_reporter = change_reporter
474
self.pp = ProgressPhase("Merge phase", 3, self.pb)
476
self.tt = TreeTransform(working_tree, self.pb)
479
entries = self._entries3()
480
child_pb = ui.ui_factory.nested_progress_bar()
482
for num, (file_id, changed, parents3, names3,
483
executable3) in enumerate(entries):
484
child_pb.update('Preparing file merge', num, len(entries))
485
self._merge_names(file_id, parents3, names3)
487
file_status = self.merge_contents(file_id)
489
file_status = 'unmodified'
490
self._merge_executable(file_id,
491
executable3, file_status)
496
child_pb = ui.ui_factory.nested_progress_bar()
498
fs_conflicts = resolve_conflicts(self.tt, child_pb,
499
lambda t, c: conflict_pass(t, c, self.other_tree))
502
if change_reporter is not None:
503
from bzrlib import delta
504
delta.report_changes(self.tt._iter_changes(), change_reporter)
505
self.cook_conflicts(fs_conflicts)
506
for conflict in self.cooked_conflicts:
509
results = self.tt.apply(no_conflicts=True)
510
self.write_modified(results)
512
working_tree.add_conflicts(self.cooked_conflicts)
513
except UnsupportedOperation:
517
self.other_tree.unlock()
518
self.base_tree.unlock()
519
self.this_tree.unlock()
523
"""Gather data about files modified between three trees.
525
Return a list of tuples of file_id, changed, parents3, names3,
526
executable3. changed is a boolean indicating whether the file contents
527
or kind were changed. parents3 is a tuple of parent ids for base,
528
other and this. names3 is a tuple of names for base, other and this.
529
executable3 is a tuple of execute-bit values for base, other and this.
532
iterator = self.other_tree._iter_changes(self.base_tree,
533
include_unchanged=True, specific_files=self.interesting_files,
534
extra_trees=[self.this_tree])
535
for (file_id, paths, changed, versioned, parents, names, kind,
536
executable) in iterator:
537
if (self.interesting_ids is not None and
538
file_id not in self.interesting_ids):
540
if file_id in self.this_tree.inventory:
541
entry = self.this_tree.inventory[file_id]
542
this_name = entry.name
543
this_parent = entry.parent_id
544
this_executable = entry.executable
548
this_executable = None
549
parents3 = parents + (this_parent,)
550
names3 = names + (this_name,)
551
executable3 = executable + (this_executable,)
552
result.append((file_id, changed, parents3, names3, executable3))
557
self.tt.final_kind(self.tt.root)
559
self.tt.cancel_deletion(self.tt.root)
560
if self.tt.final_file_id(self.tt.root) is None:
561
self.tt.version_file(self.tt.tree_file_id(self.tt.root),
563
if self.other_tree.inventory.root is None:
565
other_root_file_id = self.other_tree.get_root_id()
566
other_root = self.tt.trans_id_file_id(other_root_file_id)
567
if other_root == self.tt.root:
570
self.tt.final_kind(other_root)
573
self.reparent_children(self.other_tree.inventory.root, self.tt.root)
574
self.tt.cancel_creation(other_root)
575
self.tt.cancel_versioning(other_root)
577
def reparent_children(self, ie, target):
578
for thing, child in ie.children.iteritems():
579
trans_id = self.tt.trans_id_file_id(child.file_id)
580
self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)
582
def write_modified(self, results):
584
for path in results.modified_paths:
585
file_id = self.this_tree.path2id(self.this_tree.relpath(path))
588
hash = self.this_tree.get_file_sha1(file_id)
591
modified_hashes[file_id] = hash
592
self.this_tree.set_merge_modified(modified_hashes)
595
def parent(entry, file_id):
596
"""Determine the parent for a file_id (used as a key method)"""
599
return entry.parent_id
602
def name(entry, file_id):
603
"""Determine the name for a file_id (used as a key method)"""
609
def contents_sha1(tree, file_id):
610
"""Determine the sha1 of the file contents (used as a key method)."""
611
if file_id not in tree:
613
return tree.get_file_sha1(file_id)
616
def executable(tree, file_id):
617
"""Determine the executability of a file-id (used as a key method)."""
618
if file_id not in tree:
620
if tree.kind(file_id) != "file":
622
return tree.is_executable(file_id)
625
def kind(tree, file_id):
626
"""Determine the kind of a file-id (used as a key method)."""
627
if file_id not in tree:
629
return tree.kind(file_id)
632
def _three_way(base, other, this):
633
#if base == other, either they all agree, or only THIS has changed.
636
elif this not in (base, other):
638
# "Ambiguous clean merge" -- both sides have made the same change.
641
# this == base: only other has changed.
646
def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
647
"""Do a three-way test on a scalar.
648
Return "this", "other" or "conflict", depending whether a value wins.
650
key_base = key(base_tree, file_id)
651
key_other = key(other_tree, file_id)
652
#if base == other, either they all agree, or only THIS has changed.
653
if key_base == key_other:
655
key_this = key(this_tree, file_id)
656
if key_this not in (key_base, key_other):
658
# "Ambiguous clean merge"
659
elif key_this == key_other:
662
assert key_this == key_base
665
def merge_names(self, file_id):
667
if file_id in tree.inventory:
668
return tree.inventory[file_id]
671
this_entry = get_entry(self.this_tree)
672
other_entry = get_entry(self.other_tree)
673
base_entry = get_entry(self.base_tree)
674
entries = (base_entry, other_entry, this_entry)
677
for entry in entries:
682
names.append(entry.name)
683
parents.append(entry.parent_id)
684
return self._merge_names(file_id, parents, names)
686
def _merge_names(self, file_id, parents, names):
687
"""Perform a merge on file_id names and parents"""
688
base_name, other_name, this_name = names
689
base_parent, other_parent, this_parent = parents
691
name_winner = self._three_way(*names)
693
parent_id_winner = self._three_way(*parents)
694
if this_name is None:
695
if name_winner == "this":
696
name_winner = "other"
697
if parent_id_winner == "this":
698
parent_id_winner = "other"
699
if name_winner == "this" and parent_id_winner == "this":
701
if name_winner == "conflict":
702
trans_id = self.tt.trans_id_file_id(file_id)
703
self._raw_conflicts.append(('name conflict', trans_id,
704
this_name, other_name))
705
if parent_id_winner == "conflict":
706
trans_id = self.tt.trans_id_file_id(file_id)
707
self._raw_conflicts.append(('parent conflict', trans_id,
708
this_parent, other_parent))
709
if other_name is None:
710
# it doesn't matter whether the result was 'other' or
711
# 'conflict'-- if there's no 'other', we leave it alone.
713
# if we get here, name_winner and parent_winner are set to safe values.
714
trans_id = self.tt.trans_id_file_id(file_id)
715
parent_id = parents[self.winner_idx[parent_id_winner]]
716
if parent_id is not None:
717
parent_trans_id = self.tt.trans_id_file_id(parent_id)
718
self.tt.adjust_path(names[self.winner_idx[name_winner]],
719
parent_trans_id, trans_id)
721
def merge_contents(self, file_id):
722
"""Performa a merge on file_id contents."""
723
def contents_pair(tree):
724
if file_id not in tree:
726
kind = tree.kind(file_id)
728
contents = tree.get_file_sha1(file_id)
729
elif kind == "symlink":
730
contents = tree.get_symlink_target(file_id)
733
return kind, contents
735
def contents_conflict():
736
trans_id = self.tt.trans_id_file_id(file_id)
737
name = self.tt.final_name(trans_id)
738
parent_id = self.tt.final_parent(trans_id)
739
if file_id in self.this_tree.inventory:
740
self.tt.unversion_file(trans_id)
741
if file_id in self.this_tree:
742
self.tt.delete_contents(trans_id)
743
file_group = self._dump_conflicts(name, parent_id, file_id,
745
self._raw_conflicts.append(('contents conflict', file_group))
747
# See SPOT run. run, SPOT, run.
748
# So we're not QUITE repeating ourselves; we do tricky things with
750
base_pair = contents_pair(self.base_tree)
751
other_pair = contents_pair(self.other_tree)
752
if base_pair == other_pair:
753
# OTHER introduced no changes
755
this_pair = contents_pair(self.this_tree)
756
if this_pair == other_pair:
757
# THIS and OTHER introduced the same changes
760
trans_id = self.tt.trans_id_file_id(file_id)
761
if this_pair == base_pair:
762
# only OTHER introduced changes
763
if file_id in self.this_tree:
764
# Remove any existing contents
765
self.tt.delete_contents(trans_id)
766
if file_id in self.other_tree:
767
# OTHER changed the file
768
create_by_entry(self.tt,
769
self.other_tree.inventory[file_id],
770
self.other_tree, trans_id)
771
if file_id not in self.this_tree.inventory:
772
self.tt.version_file(file_id, trans_id)
774
elif file_id in self.this_tree.inventory:
775
# OTHER deleted the file
776
self.tt.unversion_file(trans_id)
778
#BOTH THIS and OTHER introduced changes; scalar conflict
779
elif this_pair[0] == "file" and other_pair[0] == "file":
780
# THIS and OTHER are both files, so text merge. Either
781
# BASE is a file, or both converted to files, so at least we
782
# have agreement that output should be a file.
784
self.text_merge(file_id, trans_id)
786
return contents_conflict()
787
if file_id not in self.this_tree.inventory:
788
self.tt.version_file(file_id, trans_id)
790
self.tt.tree_kind(trans_id)
791
self.tt.delete_contents(trans_id)
796
# Scalar conflict, can't text merge. Dump conflicts
797
return contents_conflict()
799
def get_lines(self, tree, file_id):
800
"""Return the lines in a file, or an empty list."""
802
return tree.get_file(file_id).readlines()
806
def text_merge(self, file_id, trans_id):
807
"""Perform a three-way text merge on a file_id"""
808
# it's possible that we got here with base as a different type.
809
# if so, we just want two-way text conflicts.
810
if file_id in self.base_tree and \
811
self.base_tree.kind(file_id) == "file":
812
base_lines = self.get_lines(self.base_tree, file_id)
815
other_lines = self.get_lines(self.other_tree, file_id)
816
this_lines = self.get_lines(self.this_tree, file_id)
817
m3 = Merge3(base_lines, this_lines, other_lines)
818
start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
819
if self.show_base is True:
820
base_marker = '|' * 7
824
def iter_merge3(retval):
825
retval["text_conflicts"] = False
826
for line in m3.merge_lines(name_a = "TREE",
827
name_b = "MERGE-SOURCE",
828
name_base = "BASE-REVISION",
829
start_marker=start_marker,
830
base_marker=base_marker,
831
reprocess=self.reprocess):
832
if line.startswith(start_marker):
833
retval["text_conflicts"] = True
834
yield line.replace(start_marker, '<' * 7)
838
merge3_iterator = iter_merge3(retval)
839
self.tt.create_file(merge3_iterator, trans_id)
840
if retval["text_conflicts"] is True:
841
self._raw_conflicts.append(('text conflict', trans_id))
842
name = self.tt.final_name(trans_id)
843
parent_id = self.tt.final_parent(trans_id)
844
file_group = self._dump_conflicts(name, parent_id, file_id,
845
this_lines, base_lines,
847
file_group.append(trans_id)
849
def _dump_conflicts(self, name, parent_id, file_id, this_lines=None,
850
base_lines=None, other_lines=None, set_version=False,
852
"""Emit conflict files.
853
If this_lines, base_lines, or other_lines are omitted, they will be
854
determined automatically. If set_version is true, the .OTHER, .THIS
855
or .BASE (in that order) will be created as versioned files.
857
data = [('OTHER', self.other_tree, other_lines),
858
('THIS', self.this_tree, this_lines)]
860
data.append(('BASE', self.base_tree, base_lines))
863
for suffix, tree, lines in data:
865
trans_id = self._conflict_file(name, parent_id, tree, file_id,
867
file_group.append(trans_id)
868
if set_version and not versioned:
869
self.tt.version_file(file_id, trans_id)
873
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
875
"""Emit a single conflict file."""
876
name = name + '.' + suffix
877
trans_id = self.tt.create_path(name, parent_id)
878
entry = tree.inventory[file_id]
879
create_by_entry(self.tt, entry, tree, trans_id, lines)
882
def merge_executable(self, file_id, file_status):
883
"""Perform a merge on the execute bit."""
884
executable = [self.executable(t, file_id) for t in (self.base_tree,
885
self.other_tree, self.this_tree)]
886
self._merge_executable(file_id, executable, file_status)
888
def _merge_executable(self, file_id, executable, file_status):
889
"""Perform a merge on the execute bit."""
890
base_executable, other_executable, this_executable = executable
891
if file_status == "deleted":
893
trans_id = self.tt.trans_id_file_id(file_id)
895
if self.tt.final_kind(trans_id) != "file":
899
winner = self._three_way(*executable)
900
if winner == "conflict":
901
# There must be a None in here, if we have a conflict, but we
902
# need executability since file status was not deleted.
903
if self.executable(self.other_tree, file_id) is None:
908
if file_status == "modified":
909
executability = this_executable
910
if executability is not None:
911
trans_id = self.tt.trans_id_file_id(file_id)
912
self.tt.set_executability(executability, trans_id)
914
assert winner == "other"
915
if file_id in self.other_tree:
916
executability = other_executable
917
elif file_id in self.this_tree:
918
executability = this_executable
919
elif file_id in self.base_tree:
920
executability = base_executable
921
if executability is not None:
922
trans_id = self.tt.trans_id_file_id(file_id)
923
self.tt.set_executability(executability, trans_id)
925
def cook_conflicts(self, fs_conflicts):
926
"""Convert all conflicts into a form that doesn't depend on trans_id"""
927
from conflicts import Conflict
929
self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
930
fp = FinalPaths(self.tt)
931
for conflict in self._raw_conflicts:
932
conflict_type = conflict[0]
933
if conflict_type in ('name conflict', 'parent conflict'):
934
trans_id = conflict[1]
935
conflict_args = conflict[2:]
936
if trans_id not in name_conflicts:
937
name_conflicts[trans_id] = {}
938
unique_add(name_conflicts[trans_id], conflict_type,
940
if conflict_type == 'contents conflict':
941
for trans_id in conflict[1]:
942
file_id = self.tt.final_file_id(trans_id)
943
if file_id is not None:
945
path = fp.get_path(trans_id)
946
for suffix in ('.BASE', '.THIS', '.OTHER'):
947
if path.endswith(suffix):
948
path = path[:-len(suffix)]
950
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
951
self.cooked_conflicts.append(c)
952
if conflict_type == 'text conflict':
953
trans_id = conflict[1]
954
path = fp.get_path(trans_id)
955
file_id = self.tt.final_file_id(trans_id)
956
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
957
self.cooked_conflicts.append(c)
959
for trans_id, conflicts in name_conflicts.iteritems():
961
this_parent, other_parent = conflicts['parent conflict']
962
assert this_parent != other_parent
964
this_parent = other_parent = \
965
self.tt.final_file_id(self.tt.final_parent(trans_id))
967
this_name, other_name = conflicts['name conflict']
968
assert this_name != other_name
970
this_name = other_name = self.tt.final_name(trans_id)
971
other_path = fp.get_path(trans_id)
972
if this_parent is not None and this_name is not None:
974
fp.get_path(self.tt.trans_id_file_id(this_parent))
975
this_path = pathjoin(this_parent_path, this_name)
977
this_path = "<deleted>"
978
file_id = self.tt.final_file_id(trans_id)
979
c = Conflict.factory('path conflict', path=this_path,
980
conflict_path=other_path, file_id=file_id)
981
self.cooked_conflicts.append(c)
982
self.cooked_conflicts.sort(key=Conflict.sort_key)
985
class WeaveMerger(Merge3Merger):
986
"""Three-way tree merger, text weave merger."""
987
supports_reprocess = True
988
supports_show_base = False
989
supports_reverse_cherrypick = False
992
def __init__(self, working_tree, this_tree, base_tree, other_tree,
993
interesting_ids=None, pb=DummyProgress(), pp=None,
994
reprocess=False, change_reporter=None,
995
interesting_files=None, cherrypick=False):
996
self.cherrypick = cherrypick
997
super(WeaveMerger, self).__init__(working_tree, this_tree,
998
base_tree, other_tree,
999
interesting_ids=interesting_ids,
1000
pb=pb, pp=pp, reprocess=reprocess,
1001
change_reporter=change_reporter)
1003
def _merged_lines(self, file_id):
1004
"""Generate the merged lines.
1005
There is no distinction between lines that are meant to contain <<<<<<<
1009
base = self.base_tree
1012
plan = self.this_tree.plan_file_merge(file_id, self.other_tree,
1014
if 'merge' in debug.debug_flags:
1016
trans_id = self.tt.trans_id_file_id(file_id)
1017
name = self.tt.final_name(trans_id) + '.plan'
1018
contents = ('%10s|%s' % l for l in plan)
1019
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1020
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1021
'>>>>>>> MERGE-SOURCE\n')
1022
return textmerge.merge_lines(self.reprocess)
1024
def text_merge(self, file_id, trans_id):
1025
"""Perform a (weave) text merge for a given file and file-id.
1026
If conflicts are encountered, .THIS and .OTHER files will be emitted,
1027
and a conflict will be noted.
1029
lines, conflicts = self._merged_lines(file_id)
1031
# Note we're checking whether the OUTPUT is binary in this case,
1032
# because we don't want to get into weave merge guts.
1033
check_text_lines(lines)
1034
self.tt.create_file(lines, trans_id)
1036
self._raw_conflicts.append(('text conflict', trans_id))
1037
name = self.tt.final_name(trans_id)
1038
parent_id = self.tt.final_parent(trans_id)
1039
file_group = self._dump_conflicts(name, parent_id, file_id,
1041
file_group.append(trans_id)
1044
class LCAMerger(WeaveMerger):
1046
def _merged_lines(self, file_id):
1047
"""Generate the merged lines.
1048
There is no distinction between lines that are meant to contain <<<<<<<
1052
base = self.base_tree
1055
plan = self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1057
if 'merge' in debug.debug_flags:
1059
trans_id = self.tt.trans_id_file_id(file_id)
1060
name = self.tt.final_name(trans_id) + '.plan'
1061
contents = ('%10s|%s' % l for l in plan)
1062
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1063
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1064
'>>>>>>> MERGE-SOURCE\n')
1065
return textmerge.merge_lines(self.reprocess)
1068
class Diff3Merger(Merge3Merger):
1069
"""Three-way merger using external diff3 for text merging"""
1071
def dump_file(self, temp_dir, name, tree, file_id):
1072
out_path = pathjoin(temp_dir, name)
1073
out_file = open(out_path, "wb")
1075
in_file = tree.get_file(file_id)
1076
for line in in_file:
1077
out_file.write(line)
1082
def text_merge(self, file_id, trans_id):
1083
"""Perform a diff3 merge using a specified file-id and trans-id.
1084
If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
1085
will be dumped, and a will be conflict noted.
1088
temp_dir = osutils.mkdtemp(prefix="bzr-")
1090
new_file = pathjoin(temp_dir, "new")
1091
this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
1092
base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
1093
other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
1094
status = bzrlib.patch.diff3(new_file, this, base, other)
1095
if status not in (0, 1):
1096
raise BzrError("Unhandled diff3 exit code")
1097
f = open(new_file, 'rb')
1099
self.tt.create_file(f, trans_id)
1103
name = self.tt.final_name(trans_id)
1104
parent_id = self.tt.final_parent(trans_id)
1105
self._dump_conflicts(name, parent_id, file_id)
1106
self._raw_conflicts.append(('text conflict', trans_id))
1108
osutils.rmtree(temp_dir)
1111
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
1113
merge_type=Merge3Merger,
1114
interesting_ids=None,
1118
interesting_files=None,
1121
change_reporter=None):
1122
"""Primary interface for merging.
1124
typical use is probably
1125
'merge_inner(branch, branch.get_revision_tree(other_revision),
1126
branch.get_revision_tree(base_revision))'
1128
if this_tree is None:
1129
raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
1130
"parameter as of bzrlib version 0.8.")
1131
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1132
pb=pb, change_reporter=change_reporter)
1133
merger.backup_files = backup_files
1134
merger.merge_type = merge_type
1135
merger.interesting_ids = interesting_ids
1136
merger.ignore_zero = ignore_zero
1137
if interesting_files:
1138
assert not interesting_ids, ('Only supply interesting_ids'
1139
' or interesting_files')
1140
merger.interesting_files = interesting_files
1141
merger.show_base = show_base
1142
merger.reprocess = reprocess
1143
merger.other_rev_id = other_rev_id
1144
merger.other_basis = other_rev_id
1145
return merger.do_merge()
1147
def get_merge_type_registry():
1148
"""Merge type registry is in bzrlib.option to avoid circular imports.
1150
This method provides a sanctioned way to retrieve it.
1152
from bzrlib import option
1153
return option._merge_type_registry
1156
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1157
def status_a(revision, text):
1158
if revision in ancestors_b:
1159
return 'killed-b', text
1161
return 'new-a', text
1163
def status_b(revision, text):
1164
if revision in ancestors_a:
1165
return 'killed-a', text
1167
return 'new-b', text
1169
plain_a = [t for (a, t) in annotated_a]
1170
plain_b = [t for (a, t) in annotated_b]
1171
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
1172
blocks = matcher.get_matching_blocks()
1175
for ai, bi, l in blocks:
1176
# process all mismatched sections
1177
# (last mismatched section is handled because blocks always
1178
# includes a 0-length last block)
1179
for revision, text in annotated_a[a_cur:ai]:
1180
yield status_a(revision, text)
1181
for revision, text in annotated_b[b_cur:bi]:
1182
yield status_b(revision, text)
1184
# and now the matched section
1187
for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
1188
assert text_a == text_b
1189
yield "unchanged", text_a
1192
class _PlanMergeBase(object):
1194
def __init__(self, a_rev, b_rev, vf):
1197
:param a_rev: Revision-id of one revision to merge
1198
:param b_rev: Revision-id of the other revision to merge
1199
:param vf: A versionedfile containing both revisions
1203
self.lines_a = vf.get_lines(a_rev)
1204
self.lines_b = vf.get_lines(b_rev)
1206
self._last_lines = None
1207
self._last_lines_revision_id = None
1208
self._cached_matching_blocks = {}
1210
def plan_merge(self):
1211
"""Generate a 'plan' for merging the two revisions.
1213
This involves comparing their texts and determining the cause of
1214
differences. If text A has a line and text B does not, then either the
1215
line was added to text A, or it was deleted from B. Once the causes
1216
are combined, they are written out in the format described in
1217
VersionedFile.plan_merge
1219
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1220
unique_a, unique_b = self._unique_lines(blocks)
1221
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
1222
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
1223
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
1225
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1228
for i, j, n in blocks:
1229
for a_index in range(last_i, i):
1230
if a_index in new_a:
1231
if a_index in killed_b:
1232
yield 'conflicted-a', self.lines_a[a_index]
1234
yield 'new-a', self.lines_a[a_index]
1236
yield 'killed-b', self.lines_a[a_index]
1237
for b_index in range(last_j, j):
1238
if b_index in new_b:
1239
if b_index in killed_a:
1240
yield 'conflicted-b', self.lines_b[a_index]
1242
yield 'new-b', self.lines_b[b_index]
1244
yield 'killed-a', self.lines_b[b_index]
1245
# handle common lines
1246
for a_index in range(i, i+n):
1247
yield 'unchanged', self.lines_a[a_index]
1251
def _get_matching_blocks(self, left_revision, right_revision):
1252
"""Return a description of which sections of two revisions match.
1254
See SequenceMatcher.get_matching_blocks
1256
cached = self._cached_matching_blocks.get((left_revision,
1258
if cached is not None:
1260
if self._last_lines_revision_id == left_revision:
1261
left_lines = self._last_lines
1263
left_lines = self.vf.get_lines(left_revision)
1264
right_lines = self.vf.get_lines(right_revision)
1265
self._last_lines = right_lines
1266
self._last_lines_revision_id = right_revision
1267
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1269
return matcher.get_matching_blocks()
1271
def _unique_lines(self, matching_blocks):
1272
"""Analyse matching_blocks to determine which lines are unique
1274
:return: a tuple of (unique_left, unique_right), where the values are
1275
sets of line numbers of unique lines.
1281
for i, j, n in matching_blocks:
1282
unique_left.extend(range(last_i, i))
1283
unique_right.extend(range(last_j, j))
1286
return unique_left, unique_right
1289
def _subtract_plans(old_plan, new_plan):
1290
"""Remove changes from new_plan that came from old_plan.
1292
It is assumed that the difference between the old_plan and new_plan
1293
is their choice of 'b' text.
1295
All lines from new_plan that differ from old_plan are emitted
1296
verbatim. All lines from new_plan that match old_plan but are
1297
not about the 'b' revision are emitted verbatim.
1299
Lines that match and are about the 'b' revision are the lines we
1300
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
1301
is skipped entirely.
1303
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1306
for i, j, n in matcher.get_matching_blocks():
1307
for jj in range(last_j, j):
1309
for jj in range(j, j+n):
1310
plan_line = new_plan[jj]
1311
if plan_line[0] == 'new-b':
1313
elif plan_line[0] == 'killed-b':
1314
yield 'unchanged', plan_line[1]
1320
class _PlanMerge(_PlanMergeBase):
1321
"""Plan an annotate merge using on-the-fly annotation"""
1323
def __init__(self, a_rev, b_rev, vf):
1324
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1325
a_ancestry = set(vf.get_ancestry(a_rev, topo_sorted=False))
1326
b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
1327
self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
1329
def _determine_status(self, revision_id, unique_line_numbers):
1330
"""Determines the status unique lines versus all lcas.
1332
Basically, determines why the line is unique to this revision.
1334
A line may be determined new or killed, but not both.
1336
:param revision_id: The id of the revision in which the lines are
1338
:param unique_line_numbers: The line numbers of unique lines.
1339
:return a tuple of (new_this, killed_other):
1341
new = self._find_new(revision_id)
1342
killed = set(unique_line_numbers).difference(new)
1345
def _find_new(self, version_id):
1346
"""Determine which lines are new in the ancestry of this version.
1348
If a lines is present in this version, and not present in any
1349
common ancestor, it is considered new.
1351
if version_id not in self.uncommon:
1353
parents = self.vf.get_parents(version_id)
1354
if len(parents) == 0:
1355
return set(range(len(self.vf.get_lines(version_id))))
1357
for parent in parents:
1358
blocks = self._get_matching_blocks(version_id, parent)
1359
result, unused = self._unique_lines(blocks)
1360
parent_new = self._find_new(parent)
1361
for i, j, n in blocks:
1362
for ii, jj in [(i+r, j+r) for r in range(n)]:
1363
if jj in parent_new:
1368
new.intersection_update(result)
1372
class _PlanLCAMerge(_PlanMergeBase):
1374
This merge algorithm differs from _PlanMerge in that:
1375
1. comparisons are done against LCAs only
1376
2. cases where a contested line is new versus one LCA but old versus
1377
another are marked as conflicts, by emitting the line as conflicted-a
1380
This is faster, and hopefully produces more useful output.
1383
def __init__(self, a_rev, b_rev, vf, graph):
1384
_PlanMergeBase.__init__(self, a_rev, b_rev, vf)
1385
self.lcas = graph.find_lca(a_rev, b_rev)
1386
for lca in self.lcas:
1387
lca_lines = self.vf.get_lines(lca)
1388
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
1390
blocks = list(matcher.get_matching_blocks())
1391
self._cached_matching_blocks[(a_rev, lca)] = blocks
1392
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
1394
blocks = list(matcher.get_matching_blocks())
1395
self._cached_matching_blocks[(b_rev, lca)] = blocks
1397
def _determine_status(self, revision_id, unique_line_numbers):
1398
"""Determines the status unique lines versus all lcas.
1400
Basically, determines why the line is unique to this revision.
1402
A line may be determined new, killed, or both.
1404
If a line is determined new, that means it was not present in at least
1405
one LCA, and is not present in the other merge revision.
1407
If a line is determined killed, that means the line was present in
1410
If a line is killed and new, this indicates that the two merge
1411
revisions contain differing conflict resolutions.
1412
:param revision_id: The id of the revision in which the lines are
1414
:param unique_line_numbers: The line numbers of unique lines.
1415
:return a tuple of (new_this, killed_other):
1419
unique_line_numbers = set(unique_line_numbers)
1420
for lca in self.lcas:
1421
blocks = self._get_matching_blocks(revision_id, lca)
1422
unique_vs_lca, _ignored = self._unique_lines(blocks)
1423
new.update(unique_line_numbers.intersection(unique_vs_lca))
1424
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
bzrlib/merge.py
