1
# Copyright (C) 2005, 2006, 2008 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
19
from itertools import chain
30
revision as _mod_revision,
34
from bzrlib.branch import Branch
35
from bzrlib.conflicts import ConflictList, Conflict
36
from bzrlib.errors import (BzrCommandError,
46
WorkingTreeNotRevision,
49
from bzrlib.graph import Graph
50
from bzrlib.merge3 import Merge3
51
from bzrlib.osutils import rename, pathjoin
52
from progress import DummyProgress, ProgressPhase
53
from bzrlib.revision import (NULL_REVISION, ensure_null)
54
from bzrlib.textfile import check_text_lines
55
from bzrlib.trace import mutter, warning, note, is_quiet
56
from bzrlib.transform import (TransformPreview, TreeTransform,
57
resolve_conflicts, cook_conflicts,
58
conflict_pass, FinalPaths, create_by_entry,
59
unique_add, ROOT_PARENT)
60
from bzrlib.versionedfile import PlanWeaveMerge
63
# TODO: Report back as changes are merged in
66
def transform_tree(from_tree, to_tree, interesting_ids=None):
67
merge_inner(from_tree.branch, to_tree, from_tree, ignore_zero=True,
68
interesting_ids=interesting_ids, this_tree=from_tree)
72
def __init__(self, this_branch, other_tree=None, base_tree=None,
73
this_tree=None, pb=DummyProgress(), change_reporter=None,
74
recurse='down', revision_graph=None):
76
self.this_branch = this_branch
77
self.this_basis = _mod_revision.ensure_null(
78
this_branch.last_revision())
79
self.this_rev_id = None
80
self.this_tree = this_tree
81
self.this_revision_tree = None
82
self.this_basis_tree = None
83
self.other_tree = other_tree
84
self.other_branch = None
85
self.base_tree = base_tree
86
self.ignore_zero = False
87
self.backup_files = False
88
self.interesting_ids = None
89
self.interesting_files = None
90
self.show_base = False
91
self.reprocess = False
94
self.recurse = recurse
95
self.change_reporter = change_reporter
96
self._cached_trees = {}
97
self._revision_graph = revision_graph
98
self._base_is_ancestor = None
99
self._base_is_other_ancestor = None
100
self._is_criss_cross = None
101
self._lca_trees = None
104
def revision_graph(self):
105
if self._revision_graph is None:
106
self._revision_graph = self.this_branch.repository.get_graph()
107
return self._revision_graph
109
def _set_base_is_ancestor(self, value):
110
self._base_is_ancestor = value
112
def _get_base_is_ancestor(self):
113
if self._base_is_ancestor is None:
114
self._base_is_ancestor = self.revision_graph.is_ancestor(
115
self.base_rev_id, self.this_basis)
116
return self._base_is_ancestor
118
base_is_ancestor = property(_get_base_is_ancestor, _set_base_is_ancestor)
120
def _set_base_is_other_ancestor(self, value):
121
self._base_is_other_ancestor = value
123
def _get_base_is_other_ancestor(self):
124
if self._base_is_other_ancestor is None:
125
if self.other_basis is None:
127
self._base_is_other_ancestor = self.revision_graph.is_ancestor(
128
self.base_rev_id, self.other_basis)
129
return self._base_is_other_ancestor
131
base_is_other_ancestor = property(_get_base_is_other_ancestor,
132
_set_base_is_other_ancestor)
135
def from_uncommitted(tree, other_tree, pb):
136
"""Return a Merger for uncommitted changes in other_tree.
138
:param tree: The tree to merge into
139
:param other_tree: The tree to get uncommitted changes from
140
:param pb: A progress indicator
142
merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,
144
merger.base_rev_id = merger.base_tree.get_revision_id()
145
merger.other_rev_id = None
146
merger.other_basis = merger.base_rev_id
150
def from_mergeable(klass, tree, mergeable, pb):
151
"""Return a Merger for a bundle or merge directive.
153
:param tree: The tree to merge changes into
154
:param mergeable: A merge directive or bundle
155
:param pb: A progress indicator
157
mergeable.install_revisions(tree.branch.repository)
158
base_revision_id, other_revision_id, verified =\
159
mergeable.get_merge_request(tree.branch.repository)
160
revision_graph = tree.branch.repository.get_graph()
161
if base_revision_id is not None:
162
if (base_revision_id != _mod_revision.NULL_REVISION and
163
revision_graph.is_ancestor(
164
base_revision_id, tree.branch.last_revision())):
165
base_revision_id = None
167
warning('Performing cherrypick')
168
merger = klass.from_revision_ids(pb, tree, other_revision_id,
169
base_revision_id, revision_graph=
171
return merger, verified
174
def from_revision_ids(pb, tree, other, base=None, other_branch=None,
175
base_branch=None, revision_graph=None):
176
"""Return a Merger for revision-ids.
178
:param tree: The tree to merge changes into
179
:param other: The revision-id to use as OTHER
180
:param base: The revision-id to use as BASE. If not specified, will
182
:param other_branch: A branch containing the other revision-id. If
183
not supplied, tree.branch is used.
184
:param base_branch: A branch containing the base revision-id. If
185
not supplied, other_branch or tree.branch will be used.
186
:param revision_graph: If you have a revision_graph precomputed, pass
187
it in, otherwise it will be created for you.
188
:param pb: A progress indicator
190
merger = Merger(tree.branch, this_tree=tree, pb=pb,
191
revision_graph=revision_graph)
192
if other_branch is None:
193
other_branch = tree.branch
194
merger.set_other_revision(other, other_branch)
198
if base_branch is None:
199
base_branch = other_branch
200
merger.set_base_revision(base, base_branch)
203
def revision_tree(self, revision_id, branch=None):
204
if revision_id not in self._cached_trees:
206
branch = self.this_branch
208
tree = self.this_tree.revision_tree(revision_id)
209
except errors.NoSuchRevisionInTree:
210
tree = branch.repository.revision_tree(revision_id)
211
self._cached_trees[revision_id] = tree
212
return self._cached_trees[revision_id]
214
def _get_tree(self, treespec, possible_transports=None):
215
from bzrlib import workingtree
216
location, revno = treespec
218
tree = workingtree.WorkingTree.open_containing(location)[0]
219
return tree.branch, tree
220
branch = Branch.open_containing(location, possible_transports)[0]
222
revision_id = branch.last_revision()
224
revision_id = branch.get_rev_id(revno)
225
revision_id = ensure_null(revision_id)
226
return branch, self.revision_tree(revision_id, branch)
228
def ensure_revision_trees(self):
229
if self.this_revision_tree is None:
230
self.this_basis_tree = self.revision_tree(self.this_basis)
231
if self.this_basis == self.this_rev_id:
232
self.this_revision_tree = self.this_basis_tree
234
if self.other_rev_id is None:
235
other_basis_tree = self.revision_tree(self.other_basis)
236
changes = other_basis_tree.changes_from(self.other_tree)
237
if changes.has_changed():
238
raise WorkingTreeNotRevision(self.this_tree)
239
other_rev_id = self.other_basis
240
self.other_tree = other_basis_tree
242
def file_revisions(self, file_id):
243
self.ensure_revision_trees()
244
def get_id(tree, file_id):
245
revision_id = tree.inventory[file_id].revision
247
if self.this_rev_id is None:
248
if self.this_basis_tree.get_file_sha1(file_id) != \
249
self.this_tree.get_file_sha1(file_id):
250
raise WorkingTreeNotRevision(self.this_tree)
252
trees = (self.this_basis_tree, self.other_tree)
253
return [get_id(tree, file_id) for tree in trees]
255
def check_basis(self, check_clean, require_commits=True):
256
if self.this_basis is None and require_commits is True:
257
raise BzrCommandError("This branch has no commits."
258
" (perhaps you would prefer 'bzr pull')")
261
if self.this_basis != self.this_rev_id:
262
raise errors.UncommittedChanges(self.this_tree)
264
def compare_basis(self):
266
basis_tree = self.revision_tree(self.this_tree.last_revision())
267
except errors.NoSuchRevision:
268
basis_tree = self.this_tree.basis_tree()
269
changes = self.this_tree.changes_from(basis_tree)
270
if not changes.has_changed():
271
self.this_rev_id = self.this_basis
273
def set_interesting_files(self, file_list):
274
self.interesting_files = file_list
276
def set_pending(self):
277
if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:
281
def _add_parent(self):
282
new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
283
new_parent_trees = []
284
for revision_id in new_parents:
286
tree = self.revision_tree(revision_id)
287
except errors.NoSuchRevision:
291
new_parent_trees.append((revision_id, tree))
293
self.this_tree.set_parent_trees(new_parent_trees,
294
allow_leftmost_as_ghost=True)
296
for _revision_id, tree in new_parent_trees:
300
def set_other(self, other_revision, possible_transports=None):
301
"""Set the revision and tree to merge from.
303
This sets the other_tree, other_rev_id, other_basis attributes.
305
:param other_revision: The [path, revision] list to merge from.
307
self.other_branch, self.other_tree = self._get_tree(other_revision,
309
if other_revision[1] == -1:
310
self.other_rev_id = _mod_revision.ensure_null(
311
self.other_branch.last_revision())
312
if _mod_revision.is_null(self.other_rev_id):
313
raise NoCommits(self.other_branch)
314
self.other_basis = self.other_rev_id
315
elif other_revision[1] is not None:
316
self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
317
self.other_basis = self.other_rev_id
319
self.other_rev_id = None
320
self.other_basis = self.other_branch.last_revision()
321
if self.other_basis is None:
322
raise NoCommits(self.other_branch)
323
if self.other_rev_id is not None:
324
self._cached_trees[self.other_rev_id] = self.other_tree
325
self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)
327
def set_other_revision(self, revision_id, other_branch):
328
"""Set 'other' based on a branch and revision id
330
:param revision_id: The revision to use for a tree
331
:param other_branch: The branch containing this tree
333
self.other_rev_id = revision_id
334
self.other_branch = other_branch
335
self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
336
self.other_tree = self.revision_tree(revision_id)
337
self.other_basis = revision_id
339
def set_base_revision(self, revision_id, branch):
340
"""Set 'base' based on a branch and revision id
342
:param revision_id: The revision to use for a tree
343
:param branch: The branch containing this tree
345
self.base_rev_id = revision_id
346
self.base_branch = branch
347
self._maybe_fetch(branch, self.this_branch, revision_id)
348
self.base_tree = self.revision_tree(revision_id)
350
def _maybe_fetch(self, source, target, revision_id):
351
if not source.repository.has_same_location(target.repository):
352
target.fetch(source, revision_id)
355
revisions = [ensure_null(self.this_basis),
356
ensure_null(self.other_basis)]
357
if NULL_REVISION in revisions:
358
self.base_rev_id = NULL_REVISION
359
self.base_tree = self.revision_tree(self.base_rev_id)
360
self._is_criss_cross = False
362
lcas = self.revision_graph.find_lca(revisions[0], revisions[1])
363
self._is_criss_cross = False
365
self.base_rev_id = NULL_REVISION
367
self.base_rev_id = list(lcas)[0]
368
else: # len(lcas) > 1
370
# find_unique_lca can only handle 2 nodes, so we have to
371
# start back at the beginning. It is a shame to traverse
372
# the graph again, but better than re-implementing
374
self.base_rev_id = self.revision_graph.find_unique_lca(
375
revisions[0], revisions[1])
377
self.base_rev_id = self.revision_graph.find_unique_lca(
379
self._is_criss_cross = True
380
if self.base_rev_id == NULL_REVISION:
381
raise UnrelatedBranches()
382
if self._is_criss_cross:
383
warning('Warning: criss-cross merge encountered. See bzr'
384
' help criss-cross.')
385
interesting_revision_ids = [self.base_rev_id]
386
interesting_revision_ids.extend(lcas)
387
interesting_trees = dict((t.get_revision_id(), t)
388
for t in self.this_branch.repository.revision_trees(
389
interesting_revision_ids))
390
self._cached_trees.update(interesting_trees)
391
self.base_tree = interesting_trees.pop(self.base_rev_id)
392
sorted_lca_keys = self.revision_graph.find_merge_order(
394
self._lca_trees = [interesting_trees[key]
395
for key in sorted_lca_keys]
397
self.base_tree = self.revision_tree(self.base_rev_id)
398
self.base_is_ancestor = True
399
self.base_is_other_ancestor = True
401
def set_base(self, base_revision):
402
"""Set the base revision to use for the merge.
404
:param base_revision: A 2-list containing a path and revision number.
406
mutter("doing merge() with no base_revision specified")
407
if base_revision == [None, None]:
410
base_branch, self.base_tree = self._get_tree(base_revision)
411
if base_revision[1] == -1:
412
self.base_rev_id = base_branch.last_revision()
413
elif base_revision[1] is None:
414
self.base_rev_id = _mod_revision.NULL_REVISION
416
self.base_rev_id = _mod_revision.ensure_null(
417
base_branch.get_rev_id(base_revision[1]))
418
self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
420
def make_merger(self):
421
kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
422
'other_tree': self.other_tree,
423
'interesting_ids': self.interesting_ids,
424
'interesting_files': self.interesting_files,
427
if self.merge_type.requires_base:
428
kwargs['base_tree'] = self.base_tree
429
if self.merge_type.supports_reprocess:
430
kwargs['reprocess'] = self.reprocess
432
raise BzrError("Conflict reduction is not supported for merge"
433
" type %s." % self.merge_type)
434
if self.merge_type.supports_show_base:
435
kwargs['show_base'] = self.show_base
437
raise BzrError("Showing base is not supported for this"
438
" merge type. %s" % self.merge_type)
439
if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
440
and not self.base_is_other_ancestor):
441
raise errors.CannotReverseCherrypick()
442
if self.merge_type.supports_cherrypick:
443
kwargs['cherrypick'] = (not self.base_is_ancestor or
444
not self.base_is_other_ancestor)
445
if self._is_criss_cross and getattr(self.merge_type,
446
'supports_lca_trees', False):
447
kwargs['lca_trees'] = self._lca_trees
448
return self.merge_type(pb=self._pb,
449
change_reporter=self.change_reporter,
453
self.this_tree.lock_tree_write()
454
if self.base_tree is not None:
455
self.base_tree.lock_read()
456
if self.other_tree is not None:
457
self.other_tree.lock_read()
459
merge = self.make_merger()
461
if self.recurse == 'down':
462
for relpath, file_id in self.this_tree.iter_references():
463
sub_tree = self.this_tree.get_nested_tree(file_id, relpath)
464
other_revision = self.other_tree.get_reference_revision(
466
if other_revision == sub_tree.last_revision():
468
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
469
sub_merge.merge_type = self.merge_type
470
other_branch = self.other_branch.reference_parent(file_id, relpath)
471
sub_merge.set_other_revision(other_revision, other_branch)
472
base_revision = self.base_tree.get_reference_revision(file_id)
473
sub_merge.base_tree = \
474
sub_tree.branch.repository.revision_tree(base_revision)
475
sub_merge.base_rev_id = base_revision
479
if self.other_tree is not None:
480
self.other_tree.unlock()
481
if self.base_tree is not None:
482
self.base_tree.unlock()
483
self.this_tree.unlock()
484
if len(merge.cooked_conflicts) == 0:
485
if not self.ignore_zero and not is_quiet():
486
note("All changes applied successfully.")
488
note("%d conflicts encountered." % len(merge.cooked_conflicts))
490
return len(merge.cooked_conflicts)
493
class _InventoryNoneEntry(object):
494
"""This represents an inventory entry which *isn't there*.
496
It simplifies the merging logic if we always have an InventoryEntry, even
497
if it isn't actually present
504
symlink_target = None
507
_none_entry = _InventoryNoneEntry()
510
class Merge3Merger(object):
511
"""Three-way merger that uses the merge3 text merger"""
513
supports_reprocess = True
514
supports_show_base = True
515
history_based = False
516
supports_cherrypick = True
517
supports_reverse_cherrypick = True
518
winner_idx = {"this": 2, "other": 1, "conflict": 1}
519
supports_lca_trees = True
521
def __init__(self, working_tree, this_tree, base_tree, other_tree,
522
interesting_ids=None, reprocess=False, show_base=False,
523
pb=DummyProgress(), pp=None, change_reporter=None,
524
interesting_files=None, do_merge=True,
525
cherrypick=False, lca_trees=None):
526
"""Initialize the merger object and perform the merge.
528
:param working_tree: The working tree to apply the merge to
529
:param this_tree: The local tree in the merge operation
530
:param base_tree: The common tree in the merge operation
531
:param other_tree: The other other tree to merge changes from
532
:param interesting_ids: The file_ids of files that should be
533
participate in the merge. May not be combined with
535
:param: reprocess If True, perform conflict-reduction processing.
536
:param show_base: If True, show the base revision in text conflicts.
537
(incompatible with reprocess)
538
:param pb: A Progress bar
539
:param pp: A ProgressPhase object
540
:param change_reporter: An object that should report changes made
541
:param interesting_files: The tree-relative paths of files that should
542
participate in the merge. If these paths refer to directories,
543
the contents of those directories will also be included. May not
544
be combined with interesting_ids. If neither interesting_files nor
545
interesting_ids is specified, all files may participate in the
547
:param lca_trees: Can be set to a dictionary of {revision_id:rev_tree}
548
if the ancestry was found to include a criss-cross merge.
549
Otherwise should be None.
551
object.__init__(self)
552
if interesting_files is not None and interesting_ids is not None:
554
'specify either interesting_ids or interesting_files')
555
self.interesting_ids = interesting_ids
556
self.interesting_files = interesting_files
557
self.this_tree = working_tree
558
self.base_tree = base_tree
559
self.other_tree = other_tree
560
self._raw_conflicts = []
561
self.cooked_conflicts = []
562
self.reprocess = reprocess
563
self.show_base = show_base
564
self._lca_trees = lca_trees
565
# Uncommenting this will change the default algorithm to always use
566
# _entries_lca. This can be useful for running the test suite and
567
# making sure we haven't missed any corner cases.
568
# if lca_trees is None:
569
# self._lca_trees = [self.base_tree]
572
self.change_reporter = change_reporter
573
self.cherrypick = cherrypick
575
self.pp = ProgressPhase("Merge phase", 3, self.pb)
580
self.this_tree.lock_tree_write()
581
self.base_tree.lock_read()
582
self.other_tree.lock_read()
583
self.tt = TreeTransform(self.this_tree, self.pb)
586
self._compute_transform()
588
results = self.tt.apply(no_conflicts=True)
589
self.write_modified(results)
591
self.this_tree.add_conflicts(self.cooked_conflicts)
592
except UnsupportedOperation:
596
self.other_tree.unlock()
597
self.base_tree.unlock()
598
self.this_tree.unlock()
601
def make_preview_transform(self):
602
self.base_tree.lock_read()
603
self.other_tree.lock_read()
604
self.tt = TransformPreview(self.this_tree)
607
self._compute_transform()
610
self.other_tree.unlock()
611
self.base_tree.unlock()
615
def _compute_transform(self):
616
if self._lca_trees is None:
617
entries = self._entries3()
618
resolver = self._three_way
620
entries = self._entries_lca()
621
resolver = self._lca_multi_way
622
child_pb = ui.ui_factory.nested_progress_bar()
624
for num, (file_id, changed, parents3, names3,
625
executable3) in enumerate(entries):
626
child_pb.update('Preparing file merge', num, len(entries))
627
self._merge_names(file_id, parents3, names3, resolver=resolver)
629
file_status = self.merge_contents(file_id)
631
file_status = 'unmodified'
632
self._merge_executable(file_id,
633
executable3, file_status, resolver=resolver)
638
child_pb = ui.ui_factory.nested_progress_bar()
640
fs_conflicts = resolve_conflicts(self.tt, child_pb,
641
lambda t, c: conflict_pass(t, c, self.other_tree))
644
if self.change_reporter is not None:
645
from bzrlib import delta
646
delta.report_changes(
647
self.tt.iter_changes(), self.change_reporter)
648
self.cook_conflicts(fs_conflicts)
649
for conflict in self.cooked_conflicts:
653
"""Gather data about files modified between three trees.
655
Return a list of tuples of file_id, changed, parents3, names3,
656
executable3. changed is a boolean indicating whether the file contents
657
or kind were changed. parents3 is a tuple of parent ids for base,
658
other and this. names3 is a tuple of names for base, other and this.
659
executable3 is a tuple of execute-bit values for base, other and this.
662
iterator = self.other_tree.iter_changes(self.base_tree,
663
include_unchanged=True, specific_files=self.interesting_files,
664
extra_trees=[self.this_tree])
665
for (file_id, paths, changed, versioned, parents, names, kind,
666
executable) in iterator:
667
if (self.interesting_ids is not None and
668
file_id not in self.interesting_ids):
670
if file_id in self.this_tree.inventory:
671
entry = self.this_tree.inventory[file_id]
672
this_name = entry.name
673
this_parent = entry.parent_id
674
this_executable = entry.executable
678
this_executable = None
679
parents3 = parents + (this_parent,)
680
names3 = names + (this_name,)
681
executable3 = executable + (this_executable,)
682
result.append((file_id, changed, parents3, names3, executable3))
685
def _entries_lca(self):
686
"""Gather data about files modified between multiple trees.
688
This compares OTHER versus all LCA trees, and for interesting entries,
689
it then compares with THIS and BASE.
691
For the multi-valued entries, the format will be (BASE, [lca1, lca2])
692
:return: [(file_id, changed, parents, names, executable)]
693
file_id Simple file_id of the entry
694
changed Boolean, True if the kind or contents changed
696
parents ((base, [parent_id, in, lcas]), parent_id_other,
698
names ((base, [name, in, lcas]), name_in_other, name_in_this)
699
executable ((base, [exec, in, lcas]), exec_in_other, exec_in_this)
701
if self.interesting_files is not None:
702
lookup_trees = [self.this_tree, self.base_tree]
703
lookup_trees.extend(self._lca_trees)
704
# I think we should include the lca trees as well
705
interesting_ids = self.other_tree.paths2ids(self.interesting_files,
708
interesting_ids = self.interesting_ids
710
walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
712
base_inventory = self.base_tree.inventory
713
this_inventory = self.this_tree.inventory
714
for path, file_id, other_ie, lca_values in walker.iter_all():
715
# Is this modified at all from any of the other trees?
717
other_ie = _none_entry
718
if interesting_ids is not None and file_id not in interesting_ids:
721
# If other_revision is found in any of the lcas, that means this
722
# node is uninteresting. This is because when merging, if there are
723
# multiple heads(), we have to create a new node. So if we didn't,
724
# we know that the ancestry is linear, and that OTHER did not
726
# See doc/developers/lca_merge_resolution.txt for details
727
other_revision = other_ie.revision
728
if other_revision is not None:
729
# We can't use this shortcut when other_revision is None,
730
# because it may be None because things are WorkingTrees, and
731
# not because it is *actually* None.
732
is_unmodified = False
733
for lca_path, ie in lca_values:
734
if ie is not None and ie.revision == other_revision:
741
for lca_path, lca_ie in lca_values:
743
lca_entries.append(_none_entry)
745
lca_entries.append(lca_ie)
747
if file_id in base_inventory:
748
base_ie = base_inventory[file_id]
750
base_ie = _none_entry
752
if file_id in this_inventory:
753
this_ie = this_inventory[file_id]
755
this_ie = _none_entry
761
for lca_ie in lca_entries:
762
lca_kinds.append(lca_ie.kind)
763
lca_parent_ids.append(lca_ie.parent_id)
764
lca_names.append(lca_ie.name)
765
lca_executable.append(lca_ie.executable)
767
kind_winner = self._lca_multi_way(
768
(base_ie.kind, lca_kinds),
769
other_ie.kind, this_ie.kind)
770
parent_id_winner = self._lca_multi_way(
771
(base_ie.parent_id, lca_parent_ids),
772
other_ie.parent_id, this_ie.parent_id)
773
name_winner = self._lca_multi_way(
774
(base_ie.name, lca_names),
775
other_ie.name, this_ie.name)
777
content_changed = True
778
if kind_winner == 'this':
779
# No kind change in OTHER, see if there are *any* changes
780
if other_ie.kind == None:
781
# No content and 'this' wins the kind, so skip this?
784
elif other_ie.kind == 'directory':
785
if parent_id_winner == 'this' and name_winner == 'this':
786
# No change for this directory in OTHER, skip
788
content_changed = False
789
elif other_ie.kind == 'file':
790
def get_sha1(ie, tree):
791
if ie.kind != 'file':
793
return tree.get_file_sha1(file_id)
794
base_sha1 = get_sha1(base_ie, self.base_tree)
795
lca_sha1s = [get_sha1(ie, tree) for ie, tree
796
in zip(lca_entries, self._lca_trees)]
797
this_sha1 = get_sha1(this_ie, self.this_tree)
798
other_sha1 = get_sha1(other_ie, self.other_tree)
799
sha1_winner = self._lca_multi_way(
800
(base_sha1, lca_sha1s), other_sha1, this_sha1,
801
allow_overriding_lca=False)
802
exec_winner = self._lca_multi_way(
803
(base_ie.executable, lca_executable),
804
other_ie.executable, this_ie.executable)
805
if (parent_id_winner == 'this' and name_winner == 'this'
806
and sha1_winner == 'this' and exec_winner == 'this'):
807
# No kind, parent, name, exec, or content change for
808
# OTHER, so this node is not considered interesting
810
if sha1_winner == 'this':
811
content_changed = False
812
elif other_ie.kind == 'symlink':
813
def get_target(ie, tree):
814
if ie.kind != 'symlink':
816
return tree.get_symlink_target(file_id)
817
base_target = get_target(base_ie, self.base_tree)
818
lca_targets = [get_target(ie, tree) for ie, tree
819
in zip(lca_entries, self._lca_trees)]
820
this_target = get_target(this_ie, self.this_tree)
821
other_target = get_target(other_ie, self.other_tree)
822
target_winner = self._lca_multi_way(
823
(base_target, lca_targets),
824
other_target, this_target)
825
if (parent_id_winner == 'this' and name_winner == 'this'
826
and target_winner == 'this'):
827
# No kind, parent, name, or symlink target change
830
if target_winner == 'this':
831
content_changed = False
832
elif other_ie.kind == 'tree-reference':
833
# The 'changed' information seems to be handled at a higher
834
# level. At least, _entries3 returns False for content
835
# changed, even when at a new revision_id.
836
content_changed = False
837
if (parent_id_winner == 'this' and name_winner == 'this'):
838
# Nothing interesting
841
raise AssertionError('unhandled kind: %s' % other_ie.kind)
842
# XXX: We need to handle kind == 'symlink'
844
# If we have gotten this far, that means something has changed
845
result.append((file_id, content_changed,
846
((base_ie.parent_id, lca_parent_ids),
847
other_ie.parent_id, this_ie.parent_id),
848
((base_ie.name, lca_names),
849
other_ie.name, this_ie.name),
850
((base_ie.executable, lca_executable),
851
other_ie.executable, this_ie.executable)
858
self.tt.final_kind(self.tt.root)
860
self.tt.cancel_deletion(self.tt.root)
861
if self.tt.final_file_id(self.tt.root) is None:
862
self.tt.version_file(self.tt.tree_file_id(self.tt.root),
864
if self.other_tree.inventory.root is None:
866
other_root_file_id = self.other_tree.get_root_id()
867
other_root = self.tt.trans_id_file_id(other_root_file_id)
868
if other_root == self.tt.root:
871
self.tt.final_kind(other_root)
874
if self.other_tree.inventory.root.file_id in self.this_tree.inventory:
875
# the other tree's root is a non-root in the current tree
877
self.reparent_children(self.other_tree.inventory.root, self.tt.root)
878
self.tt.cancel_creation(other_root)
879
self.tt.cancel_versioning(other_root)
881
def reparent_children(self, ie, target):
882
for thing, child in ie.children.iteritems():
883
trans_id = self.tt.trans_id_file_id(child.file_id)
884
self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)
886
def write_modified(self, results):
888
for path in results.modified_paths:
889
file_id = self.this_tree.path2id(self.this_tree.relpath(path))
892
hash = self.this_tree.get_file_sha1(file_id)
895
modified_hashes[file_id] = hash
896
self.this_tree.set_merge_modified(modified_hashes)
899
def parent(entry, file_id):
900
"""Determine the parent for a file_id (used as a key method)"""
903
return entry.parent_id
906
def name(entry, file_id):
907
"""Determine the name for a file_id (used as a key method)"""
913
def contents_sha1(tree, file_id):
914
"""Determine the sha1 of the file contents (used as a key method)."""
915
if file_id not in tree:
917
return tree.get_file_sha1(file_id)
920
def executable(tree, file_id):
921
"""Determine the executability of a file-id (used as a key method)."""
922
if file_id not in tree:
924
if tree.kind(file_id) != "file":
926
return tree.is_executable(file_id)
929
def kind(tree, file_id):
930
"""Determine the kind of a file-id (used as a key method)."""
931
if file_id not in tree:
933
return tree.kind(file_id)
936
def _three_way(base, other, this):
937
#if base == other, either they all agree, or only THIS has changed.
940
elif this not in (base, other):
942
# "Ambiguous clean merge" -- both sides have made the same change.
945
# this == base: only other has changed.
950
def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
951
"""Consider LCAs when determining whether a change has occurred.
953
If LCAS are all identical, this is the same as a _three_way comparison.
955
:param bases: value in (BASE, [LCAS])
956
:param other: value in OTHER
957
:param this: value in THIS
958
:param allow_overriding_lca: If there is more than one unique lca
959
value, allow OTHER to override THIS if it has a new value, and
960
THIS only has an lca value, or vice versa. This is appropriate for
961
truly scalar values, not as much for non-scalars.
962
:return: 'this', 'other', or 'conflict' depending on whether an entry
965
# See doc/developers/lca_merge_resolution.txt for details about this
968
# Either Ambiguously clean, or nothing was actually changed. We
971
base_val, lca_vals = bases
972
# Remove 'base_val' from the lca_vals, because it is not interesting
973
filtered_lca_vals = [lca_val for lca_val in lca_vals
974
if lca_val != base_val]
975
if len(filtered_lca_vals) == 0:
976
return Merge3Merger._three_way(base_val, other, this)
978
unique_lca_vals = set(filtered_lca_vals)
979
if len(unique_lca_vals) == 1:
980
return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
982
if allow_overriding_lca:
983
if other in unique_lca_vals:
984
if this in unique_lca_vals:
985
# Each side picked a different lca, conflict
988
# This has a value which supersedes both lca values, and
989
# other only has an lca value
991
elif this in unique_lca_vals:
992
# OTHER has a value which supersedes both lca values, and this
993
# only has an lca value
996
# At this point, the lcas disagree, and the tips disagree
1000
def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
1001
"""Do a three-way test on a scalar.
1002
Return "this", "other" or "conflict", depending whether a value wins.
1004
key_base = key(base_tree, file_id)
1005
key_other = key(other_tree, file_id)
1006
#if base == other, either they all agree, or only THIS has changed.
1007
if key_base == key_other:
1009
key_this = key(this_tree, file_id)
1010
# "Ambiguous clean merge"
1011
if key_this == key_other:
1013
elif key_this == key_base:
1018
def merge_names(self, file_id):
1019
def get_entry(tree):
1020
if file_id in tree.inventory:
1021
return tree.inventory[file_id]
1024
this_entry = get_entry(self.this_tree)
1025
other_entry = get_entry(self.other_tree)
1026
base_entry = get_entry(self.base_tree)
1027
entries = (base_entry, other_entry, this_entry)
1030
for entry in entries:
1033
parents.append(None)
1035
names.append(entry.name)
1036
parents.append(entry.parent_id)
1037
return self._merge_names(file_id, parents, names,
1038
resolver=self._three_way)
1040
def _merge_names(self, file_id, parents, names, resolver):
1041
"""Perform a merge on file_id names and parents"""
1042
base_name, other_name, this_name = names
1043
base_parent, other_parent, this_parent = parents
1045
name_winner = resolver(*names)
1047
parent_id_winner = resolver(*parents)
1048
if this_name is None:
1049
if name_winner == "this":
1050
name_winner = "other"
1051
if parent_id_winner == "this":
1052
parent_id_winner = "other"
1053
if name_winner == "this" and parent_id_winner == "this":
1055
if name_winner == "conflict":
1056
trans_id = self.tt.trans_id_file_id(file_id)
1057
self._raw_conflicts.append(('name conflict', trans_id,
1058
this_name, other_name))
1059
if parent_id_winner == "conflict":
1060
trans_id = self.tt.trans_id_file_id(file_id)
1061
self._raw_conflicts.append(('parent conflict', trans_id,
1062
this_parent, other_parent))
1063
if other_name is None:
1064
# it doesn't matter whether the result was 'other' or
1065
# 'conflict'-- if there's no 'other', we leave it alone.
1067
# if we get here, name_winner and parent_winner are set to safe values.
1068
trans_id = self.tt.trans_id_file_id(file_id)
1069
parent_id = parents[self.winner_idx[parent_id_winner]]
1070
if parent_id is not None:
1071
parent_trans_id = self.tt.trans_id_file_id(parent_id)
1072
self.tt.adjust_path(names[self.winner_idx[name_winner]],
1073
parent_trans_id, trans_id)
1075
def merge_contents(self, file_id):
1076
"""Performa a merge on file_id contents."""
1077
def contents_pair(tree):
1078
if file_id not in tree:
1080
kind = tree.kind(file_id)
1082
contents = tree.get_file_sha1(file_id)
1083
elif kind == "symlink":
1084
contents = tree.get_symlink_target(file_id)
1087
return kind, contents
1089
def contents_conflict():
1090
trans_id = self.tt.trans_id_file_id(file_id)
1091
name = self.tt.final_name(trans_id)
1092
parent_id = self.tt.final_parent(trans_id)
1093
if file_id in self.this_tree.inventory:
1094
self.tt.unversion_file(trans_id)
1095
if file_id in self.this_tree:
1096
self.tt.delete_contents(trans_id)
1097
file_group = self._dump_conflicts(name, parent_id, file_id,
1099
self._raw_conflicts.append(('contents conflict', file_group))
1101
# See SPOT run. run, SPOT, run.
1102
# So we're not QUITE repeating ourselves; we do tricky things with
1104
base_pair = contents_pair(self.base_tree)
1105
other_pair = contents_pair(self.other_tree)
1106
if base_pair == other_pair:
1107
# OTHER introduced no changes
1109
this_pair = contents_pair(self.this_tree)
1110
if this_pair == other_pair:
1111
# THIS and OTHER introduced the same changes
1114
trans_id = self.tt.trans_id_file_id(file_id)
1115
if this_pair == base_pair:
1116
# only OTHER introduced changes
1117
if file_id in self.this_tree:
1118
# Remove any existing contents
1119
self.tt.delete_contents(trans_id)
1120
if file_id in self.other_tree:
1121
# OTHER changed the file
1122
create_by_entry(self.tt,
1123
self.other_tree.inventory[file_id],
1124
self.other_tree, trans_id)
1125
if file_id not in self.this_tree.inventory:
1126
self.tt.version_file(file_id, trans_id)
1128
elif file_id in self.this_tree.inventory:
1129
# OTHER deleted the file
1130
self.tt.unversion_file(trans_id)
1132
#BOTH THIS and OTHER introduced changes; scalar conflict
1133
elif this_pair[0] == "file" and other_pair[0] == "file":
1134
# THIS and OTHER are both files, so text merge. Either
1135
# BASE is a file, or both converted to files, so at least we
1136
# have agreement that output should be a file.
1138
self.text_merge(file_id, trans_id)
1140
return contents_conflict()
1141
if file_id not in self.this_tree.inventory:
1142
self.tt.version_file(file_id, trans_id)
1144
self.tt.tree_kind(trans_id)
1145
self.tt.delete_contents(trans_id)
1150
# Scalar conflict, can't text merge. Dump conflicts
1151
return contents_conflict()
1153
def get_lines(self, tree, file_id):
1154
"""Return the lines in a file, or an empty list."""
1156
return tree.get_file(file_id).readlines()
1160
def text_merge(self, file_id, trans_id):
1161
"""Perform a three-way text merge on a file_id"""
1162
# it's possible that we got here with base as a different type.
1163
# if so, we just want two-way text conflicts.
1164
if file_id in self.base_tree and \
1165
self.base_tree.kind(file_id) == "file":
1166
base_lines = self.get_lines(self.base_tree, file_id)
1169
other_lines = self.get_lines(self.other_tree, file_id)
1170
this_lines = self.get_lines(self.this_tree, file_id)
1171
m3 = Merge3(base_lines, this_lines, other_lines,
1172
is_cherrypick=self.cherrypick)
1173
start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
1174
if self.show_base is True:
1175
base_marker = '|' * 7
1179
def iter_merge3(retval):
1180
retval["text_conflicts"] = False
1181
for line in m3.merge_lines(name_a = "TREE",
1182
name_b = "MERGE-SOURCE",
1183
name_base = "BASE-REVISION",
1184
start_marker=start_marker,
1185
base_marker=base_marker,
1186
reprocess=self.reprocess):
1187
if line.startswith(start_marker):
1188
retval["text_conflicts"] = True
1189
yield line.replace(start_marker, '<' * 7)
1193
merge3_iterator = iter_merge3(retval)
1194
self.tt.create_file(merge3_iterator, trans_id)
1195
if retval["text_conflicts"] is True:
1196
self._raw_conflicts.append(('text conflict', trans_id))
1197
name = self.tt.final_name(trans_id)
1198
parent_id = self.tt.final_parent(trans_id)
1199
file_group = self._dump_conflicts(name, parent_id, file_id,
1200
this_lines, base_lines,
1202
file_group.append(trans_id)
1204
def _dump_conflicts(self, name, parent_id, file_id, this_lines=None,
1205
base_lines=None, other_lines=None, set_version=False,
1207
"""Emit conflict files.
1208
If this_lines, base_lines, or other_lines are omitted, they will be
1209
determined automatically. If set_version is true, the .OTHER, .THIS
1210
or .BASE (in that order) will be created as versioned files.
1212
data = [('OTHER', self.other_tree, other_lines),
1213
('THIS', self.this_tree, this_lines)]
1215
data.append(('BASE', self.base_tree, base_lines))
1218
for suffix, tree, lines in data:
1220
trans_id = self._conflict_file(name, parent_id, tree, file_id,
1222
file_group.append(trans_id)
1223
if set_version and not versioned:
1224
self.tt.version_file(file_id, trans_id)
1228
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
1230
"""Emit a single conflict file."""
1231
name = name + '.' + suffix
1232
trans_id = self.tt.create_path(name, parent_id)
1233
entry = tree.inventory[file_id]
1234
create_by_entry(self.tt, entry, tree, trans_id, lines)
1237
def merge_executable(self, file_id, file_status):
1238
"""Perform a merge on the execute bit."""
1239
executable = [self.executable(t, file_id) for t in (self.base_tree,
1240
self.other_tree, self.this_tree)]
1241
self._merge_executable(file_id, executable, file_status,
1242
resolver=self._three_way)
1244
def _merge_executable(self, file_id, executable, file_status,
1246
"""Perform a merge on the execute bit."""
1247
base_executable, other_executable, this_executable = executable
1248
if file_status == "deleted":
1250
winner = resolver(*executable)
1251
if winner == "conflict":
1252
# There must be a None in here, if we have a conflict, but we
1253
# need executability since file status was not deleted.
1254
if self.executable(self.other_tree, file_id) is None:
1258
if winner == 'this' and file_status != "modified":
1260
trans_id = self.tt.trans_id_file_id(file_id)
1262
if self.tt.final_kind(trans_id) != "file":
1266
if winner == "this":
1267
executability = this_executable
1269
if file_id in self.other_tree:
1270
executability = other_executable
1271
elif file_id in self.this_tree:
1272
executability = this_executable
1273
elif file_id in self.base_tree:
1274
executability = base_executable
1275
if executability is not None:
1276
trans_id = self.tt.trans_id_file_id(file_id)
1277
self.tt.set_executability(executability, trans_id)
1279
def cook_conflicts(self, fs_conflicts):
1280
"""Convert all conflicts into a form that doesn't depend on trans_id"""
1281
from conflicts import Conflict
1283
self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
1284
fp = FinalPaths(self.tt)
1285
for conflict in self._raw_conflicts:
1286
conflict_type = conflict[0]
1287
if conflict_type in ('name conflict', 'parent conflict'):
1288
trans_id = conflict[1]
1289
conflict_args = conflict[2:]
1290
if trans_id not in name_conflicts:
1291
name_conflicts[trans_id] = {}
1292
unique_add(name_conflicts[trans_id], conflict_type,
1294
if conflict_type == 'contents conflict':
1295
for trans_id in conflict[1]:
1296
file_id = self.tt.final_file_id(trans_id)
1297
if file_id is not None:
1299
path = fp.get_path(trans_id)
1300
for suffix in ('.BASE', '.THIS', '.OTHER'):
1301
if path.endswith(suffix):
1302
path = path[:-len(suffix)]
1304
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1305
self.cooked_conflicts.append(c)
1306
if conflict_type == 'text conflict':
1307
trans_id = conflict[1]
1308
path = fp.get_path(trans_id)
1309
file_id = self.tt.final_file_id(trans_id)
1310
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1311
self.cooked_conflicts.append(c)
1313
for trans_id, conflicts in name_conflicts.iteritems():
1315
this_parent, other_parent = conflicts['parent conflict']
1316
if this_parent == other_parent:
1317
raise AssertionError()
1319
this_parent = other_parent = \
1320
self.tt.final_file_id(self.tt.final_parent(trans_id))
1322
this_name, other_name = conflicts['name conflict']
1323
if this_name == other_name:
1324
raise AssertionError()
1326
this_name = other_name = self.tt.final_name(trans_id)
1327
other_path = fp.get_path(trans_id)
1328
if this_parent is not None and this_name is not None:
1329
this_parent_path = \
1330
fp.get_path(self.tt.trans_id_file_id(this_parent))
1331
this_path = pathjoin(this_parent_path, this_name)
1333
this_path = "<deleted>"
1334
file_id = self.tt.final_file_id(trans_id)
1335
c = Conflict.factory('path conflict', path=this_path,
1336
conflict_path=other_path, file_id=file_id)
1337
self.cooked_conflicts.append(c)
1338
self.cooked_conflicts.sort(key=Conflict.sort_key)
1341
class WeaveMerger(Merge3Merger):
1342
"""Three-way tree merger, text weave merger."""
1343
supports_reprocess = True
1344
supports_show_base = False
1345
supports_reverse_cherrypick = False
1346
history_based = True
1348
def _merged_lines(self, file_id):
1349
"""Generate the merged lines.
1350
There is no distinction between lines that are meant to contain <<<<<<<
1354
base = self.base_tree
1357
plan = self.this_tree.plan_file_merge(file_id, self.other_tree,
1359
if 'merge' in debug.debug_flags:
1361
trans_id = self.tt.trans_id_file_id(file_id)
1362
name = self.tt.final_name(trans_id) + '.plan'
1363
contents = ('%10s|%s' % l for l in plan)
1364
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1365
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1366
'>>>>>>> MERGE-SOURCE\n')
1367
return textmerge.merge_lines(self.reprocess)
1369
def text_merge(self, file_id, trans_id):
1370
"""Perform a (weave) text merge for a given file and file-id.
1371
If conflicts are encountered, .THIS and .OTHER files will be emitted,
1372
and a conflict will be noted.
1374
lines, conflicts = self._merged_lines(file_id)
1376
# Note we're checking whether the OUTPUT is binary in this case,
1377
# because we don't want to get into weave merge guts.
1378
check_text_lines(lines)
1379
self.tt.create_file(lines, trans_id)
1381
self._raw_conflicts.append(('text conflict', trans_id))
1382
name = self.tt.final_name(trans_id)
1383
parent_id = self.tt.final_parent(trans_id)
1384
file_group = self._dump_conflicts(name, parent_id, file_id,
1386
file_group.append(trans_id)
1389
class LCAMerger(WeaveMerger):
1391
def _merged_lines(self, file_id):
1392
"""Generate the merged lines.
1393
There is no distinction between lines that are meant to contain <<<<<<<
1397
base = self.base_tree
1400
plan = self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1402
if 'merge' in debug.debug_flags:
1404
trans_id = self.tt.trans_id_file_id(file_id)
1405
name = self.tt.final_name(trans_id) + '.plan'
1406
contents = ('%10s|%s' % l for l in plan)
1407
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1408
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1409
'>>>>>>> MERGE-SOURCE\n')
1410
return textmerge.merge_lines(self.reprocess)
1413
class Diff3Merger(Merge3Merger):
1414
"""Three-way merger using external diff3 for text merging"""
1416
def dump_file(self, temp_dir, name, tree, file_id):
1417
out_path = pathjoin(temp_dir, name)
1418
out_file = open(out_path, "wb")
1420
in_file = tree.get_file(file_id)
1421
for line in in_file:
1422
out_file.write(line)
1427
def text_merge(self, file_id, trans_id):
1428
"""Perform a diff3 merge using a specified file-id and trans-id.
1429
If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
1430
will be dumped, and a will be conflict noted.
1433
temp_dir = osutils.mkdtemp(prefix="bzr-")
1435
new_file = pathjoin(temp_dir, "new")
1436
this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
1437
base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
1438
other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
1439
status = bzrlib.patch.diff3(new_file, this, base, other)
1440
if status not in (0, 1):
1441
raise BzrError("Unhandled diff3 exit code")
1442
f = open(new_file, 'rb')
1444
self.tt.create_file(f, trans_id)
1448
name = self.tt.final_name(trans_id)
1449
parent_id = self.tt.final_parent(trans_id)
1450
self._dump_conflicts(name, parent_id, file_id)
1451
self._raw_conflicts.append(('text conflict', trans_id))
1453
osutils.rmtree(temp_dir)
1456
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
1458
merge_type=Merge3Merger,
1459
interesting_ids=None,
1463
interesting_files=None,
1466
change_reporter=None):
1467
"""Primary interface for merging.
1469
typical use is probably
1470
'merge_inner(branch, branch.get_revision_tree(other_revision),
1471
branch.get_revision_tree(base_revision))'
1473
if this_tree is None:
1474
raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
1475
"parameter as of bzrlib version 0.8.")
1476
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1477
pb=pb, change_reporter=change_reporter)
1478
merger.backup_files = backup_files
1479
merger.merge_type = merge_type
1480
merger.interesting_ids = interesting_ids
1481
merger.ignore_zero = ignore_zero
1482
if interesting_files:
1484
raise ValueError('Only supply interesting_ids'
1485
' or interesting_files')
1486
merger.interesting_files = interesting_files
1487
merger.show_base = show_base
1488
merger.reprocess = reprocess
1489
merger.other_rev_id = other_rev_id
1490
merger.other_basis = other_rev_id
1491
get_revision_id = getattr(base_tree, 'get_revision_id', None)
1492
if get_revision_id is None:
1493
get_revision_id = base_tree.last_revision
1494
merger.set_base_revision(get_revision_id(), this_branch)
1495
return merger.do_merge()
1497
def get_merge_type_registry():
1498
"""Merge type registry is in bzrlib.option to avoid circular imports.
1500
This method provides a sanctioned way to retrieve it.
1502
from bzrlib import option
1503
return option._merge_type_registry
1506
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1507
def status_a(revision, text):
1508
if revision in ancestors_b:
1509
return 'killed-b', text
1511
return 'new-a', text
1513
def status_b(revision, text):
1514
if revision in ancestors_a:
1515
return 'killed-a', text
1517
return 'new-b', text
1519
plain_a = [t for (a, t) in annotated_a]
1520
plain_b = [t for (a, t) in annotated_b]
1521
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
1522
blocks = matcher.get_matching_blocks()
1525
for ai, bi, l in blocks:
1526
# process all mismatched sections
1527
# (last mismatched section is handled because blocks always
1528
# includes a 0-length last block)
1529
for revision, text in annotated_a[a_cur:ai]:
1530
yield status_a(revision, text)
1531
for revision, text in annotated_b[b_cur:bi]:
1532
yield status_b(revision, text)
1533
# and now the matched section
1536
for text_a in plain_a[ai:a_cur]:
1537
yield "unchanged", text_a
1540
class _PlanMergeBase(object):
1542
def __init__(self, a_rev, b_rev, vf, key_prefix):
1545
:param a_rev: Revision-id of one revision to merge
1546
:param b_rev: Revision-id of the other revision to merge
1547
:param vf: A VersionedFiles containing both revisions
1548
:param key_prefix: A prefix for accessing keys in vf, typically
1554
self._last_lines = None
1555
self._last_lines_revision_id = None
1556
self._cached_matching_blocks = {}
1557
self._key_prefix = key_prefix
1558
self._precache_tip_lines()
1560
def _precache_tip_lines(self):
1561
lines = self.get_lines([self.a_rev, self.b_rev])
1562
self.lines_a = lines[self.a_rev]
1563
self.lines_b = lines[self.b_rev]
1565
def get_lines(self, revisions):
1566
"""Get lines for revisions from the backing VersionedFiles.
1568
:raises RevisionNotPresent: on absent texts.
1570
keys = [(self._key_prefix + (rev,)) for rev in revisions]
1572
for record in self.vf.get_record_stream(keys, 'unordered', True):
1573
if record.storage_kind == 'absent':
1574
raise errors.RevisionNotPresent(record.key, self.vf)
1575
result[record.key[-1]] = osutils.split_lines(
1576
record.get_bytes_as('fulltext'))
1579
def plan_merge(self):
1580
"""Generate a 'plan' for merging the two revisions.
1582
This involves comparing their texts and determining the cause of
1583
differences. If text A has a line and text B does not, then either the
1584
line was added to text A, or it was deleted from B. Once the causes
1585
are combined, they are written out in the format described in
1586
VersionedFile.plan_merge
1588
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1589
unique_a, unique_b = self._unique_lines(blocks)
1590
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
1591
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
1592
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
1594
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1597
for i, j, n in blocks:
1598
for a_index in range(last_i, i):
1599
if a_index in new_a:
1600
if a_index in killed_b:
1601
yield 'conflicted-a', self.lines_a[a_index]
1603
yield 'new-a', self.lines_a[a_index]
1605
yield 'killed-b', self.lines_a[a_index]
1606
for b_index in range(last_j, j):
1607
if b_index in new_b:
1608
if b_index in killed_a:
1609
yield 'conflicted-b', self.lines_b[b_index]
1611
yield 'new-b', self.lines_b[b_index]
1613
yield 'killed-a', self.lines_b[b_index]
1614
# handle common lines
1615
for a_index in range(i, i+n):
1616
yield 'unchanged', self.lines_a[a_index]
1620
def _get_matching_blocks(self, left_revision, right_revision):
1621
"""Return a description of which sections of two revisions match.
1623
See SequenceMatcher.get_matching_blocks
1625
cached = self._cached_matching_blocks.get((left_revision,
1627
if cached is not None:
1629
if self._last_lines_revision_id == left_revision:
1630
left_lines = self._last_lines
1631
right_lines = self.get_lines([right_revision])[right_revision]
1633
lines = self.get_lines([left_revision, right_revision])
1634
left_lines = lines[left_revision]
1635
right_lines = lines[right_revision]
1636
self._last_lines = right_lines
1637
self._last_lines_revision_id = right_revision
1638
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1640
return matcher.get_matching_blocks()
1642
def _unique_lines(self, matching_blocks):
1643
"""Analyse matching_blocks to determine which lines are unique
1645
:return: a tuple of (unique_left, unique_right), where the values are
1646
sets of line numbers of unique lines.
1652
for i, j, n in matching_blocks:
1653
unique_left.extend(range(last_i, i))
1654
unique_right.extend(range(last_j, j))
1657
return unique_left, unique_right
1660
def _subtract_plans(old_plan, new_plan):
1661
"""Remove changes from new_plan that came from old_plan.
1663
It is assumed that the difference between the old_plan and new_plan
1664
is their choice of 'b' text.
1666
All lines from new_plan that differ from old_plan are emitted
1667
verbatim. All lines from new_plan that match old_plan but are
1668
not about the 'b' revision are emitted verbatim.
1670
Lines that match and are about the 'b' revision are the lines we
1671
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
1672
is skipped entirely.
1674
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1677
for i, j, n in matcher.get_matching_blocks():
1678
for jj in range(last_j, j):
1680
for jj in range(j, j+n):
1681
plan_line = new_plan[jj]
1682
if plan_line[0] == 'new-b':
1684
elif plan_line[0] == 'killed-b':
1685
yield 'unchanged', plan_line[1]
1691
class _PlanMerge(_PlanMergeBase):
1692
"""Plan an annotate merge using on-the-fly annotation"""
1694
def __init__(self, a_rev, b_rev, vf, key_prefix):
1695
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
1696
self.a_key = self._key_prefix + (self.a_rev,)
1697
self.b_key = self._key_prefix + (self.b_rev,)
1698
self.graph = Graph(self.vf)
1699
heads = self.graph.heads((self.a_key, self.b_key))
1701
# one side dominates, so we can just return its values, yay for
1703
# Ideally we would know that before we get this far
1704
self._head_key = heads.pop()
1705
if self._head_key == self.a_key:
1709
mutter('found dominating revision for %s\n%s > %s', self.vf,
1710
self._head_key[-1], other)
1713
self._head_key = None
1716
def _precache_tip_lines(self):
1717
# Turn this into a no-op, because we will do this later
1720
def _find_recursive_lcas(self):
1721
"""Find all the ancestors back to a unique lca"""
1722
cur_ancestors = (self.a_key, self.b_key)
1723
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
1724
# rather than a key tuple. We will just map that directly to no common
1728
next_lcas = self.graph.find_lca(*cur_ancestors)
1729
# Map a plain NULL_REVISION to a simple no-ancestors
1730
if next_lcas == set([NULL_REVISION]):
1732
# Order the lca's based on when they were merged into the tip
1733
# While the actual merge portion of weave merge uses a set() of
1734
# active revisions, the order of insertion *does* effect the
1735
# implicit ordering of the texts.
1736
for rev_key in cur_ancestors:
1737
ordered_parents = tuple(self.graph.find_merge_order(rev_key,
1739
parent_map[rev_key] = ordered_parents
1740
if len(next_lcas) == 0:
1742
elif len(next_lcas) == 1:
1743
parent_map[list(next_lcas)[0]] = ()
1745
elif len(next_lcas) > 2:
1746
# More than 2 lca's, fall back to grabbing all nodes between
1747
# this and the unique lca.
1748
mutter('More than 2 LCAs, falling back to all nodes for:'
1749
' %s, %s\n=> %s', self.a_key, self.b_key, cur_ancestors)
1750
cur_lcas = next_lcas
1751
while len(cur_lcas) > 1:
1752
cur_lcas = self.graph.find_lca(*cur_lcas)
1753
if len(cur_lcas) == 0:
1754
# No common base to find, use the full ancestry
1757
unique_lca = list(cur_lcas)[0]
1758
if unique_lca == NULL_REVISION:
1759
# find_lca will return a plain 'NULL_REVISION' rather
1760
# than a key tuple when there is no common ancestor, we
1761
# prefer to just use None, because it doesn't confuse
1762
# _get_interesting_texts()
1764
parent_map.update(self._find_unique_parents(next_lcas,
1767
cur_ancestors = next_lcas
1770
def _find_unique_parents(self, tip_keys, base_key):
1771
"""Find ancestors of tip that aren't ancestors of base.
1773
:param tip_keys: Nodes that are interesting
1774
:param base_key: Cull all ancestors of this node
1775
:return: The parent map for all revisions between tip_keys and
1776
base_key. base_key will be included. References to nodes outside of
1777
the ancestor set will also be removed.
1779
# TODO: this would be simpler if find_unique_ancestors took a list
1780
# instead of a single tip, internally it supports it, but it
1781
# isn't a "backwards compatible" api change.
1782
if base_key is None:
1783
parent_map = dict(self.graph.iter_ancestry(tip_keys))
1784
# We remove NULL_REVISION because it isn't a proper tuple key, and
1785
# thus confuses things like _get_interesting_texts, and our logic
1786
# to add the texts into the memory weave.
1787
if NULL_REVISION in parent_map:
1788
parent_map.pop(NULL_REVISION)
1791
for tip in tip_keys:
1793
self.graph.find_unique_ancestors(tip, [base_key]))
1794
parent_map = self.graph.get_parent_map(interesting)
1795
parent_map[base_key] = ()
1796
culled_parent_map, child_map, tails = self._remove_external_references(
1798
# Remove all the tails but base_key
1799
if base_key is not None:
1800
tails.remove(base_key)
1801
self._prune_tails(culled_parent_map, child_map, tails)
1802
# Now remove all the uninteresting 'linear' regions
1803
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
1807
def _remove_external_references(parent_map):
1808
"""Remove references that go outside of the parent map.
1810
:param parent_map: Something returned from Graph.get_parent_map(keys)
1811
:return: (filtered_parent_map, child_map, tails)
1812
filtered_parent_map is parent_map without external references
1813
child_map is the {parent_key: [child_keys]} mapping
1814
tails is a list of nodes that do not have any parents in the map
1816
# TODO: The basic effect of this function seems more generic than
1817
# _PlanMerge. But the specific details of building a child_map,
1818
# and computing tails seems very specific to _PlanMerge.
1819
# Still, should this be in Graph land?
1820
filtered_parent_map = {}
1823
for key, parent_keys in parent_map.iteritems():
1824
culled_parent_keys = [p for p in parent_keys if p in parent_map]
1825
if not culled_parent_keys:
1827
for parent_key in culled_parent_keys:
1828
child_map.setdefault(parent_key, []).append(key)
1829
# TODO: Do we want to do this, it adds overhead for every node,
1830
# just to say that the node has no children
1831
child_map.setdefault(key, [])
1832
filtered_parent_map[key] = culled_parent_keys
1833
return filtered_parent_map, child_map, tails
1836
def _prune_tails(parent_map, child_map, tails_to_remove):
1837
"""Remove tails from the parent map.
1839
This will remove the supplied revisions until no more children have 0
1842
:param parent_map: A dict of {child: [parents]}, this dictionary will
1843
be modified in place.
1844
:param tails_to_remove: A list of tips that should be removed,
1845
this list will be consumed
1846
:param child_map: The reverse dict of parent_map ({parent: [children]})
1847
this dict will be modified
1848
:return: None, parent_map will be modified in place.
1850
while tails_to_remove:
1851
next = tails_to_remove.pop()
1852
parent_map.pop(next)
1853
children = child_map.pop(next)
1854
for child in children:
1855
child_parents = parent_map[child]
1856
child_parents.remove(next)
1857
if len(child_parents) == 0:
1858
tails_to_remove.append(child)
1860
def _get_interesting_texts(self, parent_map):
1861
"""Return a dict of texts we are interested in.
1863
Note that the input is in key tuples, but the output is in plain
1866
:param parent_map: The output from _find_recursive_lcas
1867
:return: A dict of {'revision_id':lines} as returned by
1868
_PlanMergeBase.get_lines()
1870
all_revision_keys = set(parent_map)
1871
all_revision_keys.add(self.a_key)
1872
all_revision_keys.add(self.b_key)
1874
# Everything else is in 'keys' but get_lines is in 'revision_ids'
1875
all_texts = self.get_lines([k[-1] for k in all_revision_keys])
1878
def _build_weave(self):
1879
from bzrlib import weave
1880
self._weave = weave.Weave(weave_name='in_memory_weave',
1881
allow_reserved=True)
1882
parent_map = self._find_recursive_lcas()
1884
all_texts = self._get_interesting_texts(parent_map)
1886
# Note: Unfortunately, the order given by topo_sort will effect the
1887
# ordering resolution in the output. Specifically, if you add A then B,
1888
# then in the output text A lines will show up before B lines. And, of
1889
# course, topo_sort doesn't guarantee any real ordering.
1890
# So we use merge_sort, and add a fake node on the tip.
1891
# This ensures that left-hand parents will always be inserted into the
1892
# weave before right-hand parents.
1893
tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
1894
parent_map[tip_key] = (self.a_key, self.b_key)
1896
for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
1900
# for key in tsort.topo_sort(parent_map):
1901
parent_keys = parent_map[key]
1902
revision_id = key[-1]
1903
parent_ids = [k[-1] for k in parent_keys]
1904
self._weave.add_lines(revision_id, parent_ids,
1905
all_texts[revision_id])
1907
def plan_merge(self):
1908
"""Generate a 'plan' for merging the two revisions.
1910
This involves comparing their texts and determining the cause of
1911
differences. If text A has a line and text B does not, then either the
1912
line was added to text A, or it was deleted from B. Once the causes
1913
are combined, they are written out in the format described in
1914
VersionedFile.plan_merge
1916
if self._head_key is not None: # There was a single head
1917
if self._head_key == self.a_key:
1920
if self._head_key != self.b_key:
1921
raise AssertionError('There was an invalid head: %s != %s'
1922
% (self.b_key, self._head_key))
1924
head_rev = self._head_key[-1]
1925
lines = self.get_lines([head_rev])[head_rev]
1926
return ((plan, line) for line in lines)
1927
return self._weave.plan_merge(self.a_rev, self.b_rev)
1930
class _PlanLCAMerge(_PlanMergeBase):
1932
This merge algorithm differs from _PlanMerge in that:
1933
1. comparisons are done against LCAs only
1934
2. cases where a contested line is new versus one LCA but old versus
1935
another are marked as conflicts, by emitting the line as conflicted-a
1938
This is faster, and hopefully produces more useful output.
1941
def __init__(self, a_rev, b_rev, vf, key_prefix, graph):
1942
_PlanMergeBase.__init__(self, a_rev, b_rev, vf, key_prefix)
1943
lcas = graph.find_lca(key_prefix + (a_rev,), key_prefix + (b_rev,))
1946
if lca == NULL_REVISION:
1949
self.lcas.add(lca[-1])
1950
for lca in self.lcas:
1951
if _mod_revision.is_null(lca):
1954
lca_lines = self.get_lines([lca])[lca]
1955
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
1957
blocks = list(matcher.get_matching_blocks())
1958
self._cached_matching_blocks[(a_rev, lca)] = blocks
1959
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
1961
blocks = list(matcher.get_matching_blocks())
1962
self._cached_matching_blocks[(b_rev, lca)] = blocks
1964
def _determine_status(self, revision_id, unique_line_numbers):
1965
"""Determines the status unique lines versus all lcas.
1967
Basically, determines why the line is unique to this revision.
1969
A line may be determined new, killed, or both.
1971
If a line is determined new, that means it was not present in at least
1972
one LCA, and is not present in the other merge revision.
1974
If a line is determined killed, that means the line was present in
1977
If a line is killed and new, this indicates that the two merge
1978
revisions contain differing conflict resolutions.
1979
:param revision_id: The id of the revision in which the lines are
1981
:param unique_line_numbers: The line numbers of unique lines.
1982
:return a tuple of (new_this, killed_other):
1986
unique_line_numbers = set(unique_line_numbers)
1987
for lca in self.lcas:
1988
blocks = self._get_matching_blocks(revision_id, lca)
1989
unique_vs_lca, _ignored = self._unique_lines(blocks)
1990
new.update(unique_line_numbers.intersection(unique_vs_lca))
1991
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
bzrlib/merge.py
