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
self.reparent_children(self.other_tree.inventory.root, self.tt.root)
875
self.tt.cancel_creation(other_root)
876
self.tt.cancel_versioning(other_root)
878
def reparent_children(self, ie, target):
879
for thing, child in ie.children.iteritems():
880
trans_id = self.tt.trans_id_file_id(child.file_id)
881
self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)
883
def write_modified(self, results):
885
for path in results.modified_paths:
886
file_id = self.this_tree.path2id(self.this_tree.relpath(path))
889
hash = self.this_tree.get_file_sha1(file_id)
892
modified_hashes[file_id] = hash
893
self.this_tree.set_merge_modified(modified_hashes)
896
def parent(entry, file_id):
897
"""Determine the parent for a file_id (used as a key method)"""
900
return entry.parent_id
903
def name(entry, file_id):
904
"""Determine the name for a file_id (used as a key method)"""
910
def contents_sha1(tree, file_id):
911
"""Determine the sha1 of the file contents (used as a key method)."""
912
if file_id not in tree:
914
return tree.get_file_sha1(file_id)
917
def executable(tree, file_id):
918
"""Determine the executability of a file-id (used as a key method)."""
919
if file_id not in tree:
921
if tree.kind(file_id) != "file":
923
return tree.is_executable(file_id)
926
def kind(tree, file_id):
927
"""Determine the kind of a file-id (used as a key method)."""
928
if file_id not in tree:
930
return tree.kind(file_id)
933
def _three_way(base, other, this):
934
#if base == other, either they all agree, or only THIS has changed.
937
elif this not in (base, other):
939
# "Ambiguous clean merge" -- both sides have made the same change.
942
# this == base: only other has changed.
947
def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
948
"""Consider LCAs when determining whether a change has occurred.
950
If LCAS are all identical, this is the same as a _three_way comparison.
952
:param bases: value in (BASE, [LCAS])
953
:param other: value in OTHER
954
:param this: value in THIS
955
:param allow_overriding_lca: If there is more than one unique lca
956
value, allow OTHER to override THIS if it has a new value, and
957
THIS only has an lca value, or vice versa. This is appropriate for
958
truly scalar values, not as much for non-scalars.
959
:return: 'this', 'other', or 'conflict' depending on whether an entry
962
# See doc/developers/lca_merge_resolution.txt for details about this
965
# Either Ambiguously clean, or nothing was actually changed. We
968
base_val, lca_vals = bases
969
# Remove 'base_val' from the lca_vals, because it is not interesting
970
filtered_lca_vals = [lca_val for lca_val in lca_vals
971
if lca_val != base_val]
972
if len(filtered_lca_vals) == 0:
973
return Merge3Merger._three_way(base_val, other, this)
975
unique_lca_vals = set(filtered_lca_vals)
976
if len(unique_lca_vals) == 1:
977
return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
979
if allow_overriding_lca:
980
if other in unique_lca_vals:
981
if this in unique_lca_vals:
982
# Each side picked a different lca, conflict
985
# This has a value which supersedes both lca values, and
986
# other only has an lca value
988
elif this in unique_lca_vals:
989
# OTHER has a value which supersedes both lca values, and this
990
# only has an lca value
993
# At this point, the lcas disagree, and the tips disagree
997
def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
998
"""Do a three-way test on a scalar.
999
Return "this", "other" or "conflict", depending whether a value wins.
1001
key_base = key(base_tree, file_id)
1002
key_other = key(other_tree, file_id)
1003
#if base == other, either they all agree, or only THIS has changed.
1004
if key_base == key_other:
1006
key_this = key(this_tree, file_id)
1007
# "Ambiguous clean merge"
1008
if key_this == key_other:
1010
elif key_this == key_base:
1015
def merge_names(self, file_id):
1016
def get_entry(tree):
1017
if file_id in tree.inventory:
1018
return tree.inventory[file_id]
1021
this_entry = get_entry(self.this_tree)
1022
other_entry = get_entry(self.other_tree)
1023
base_entry = get_entry(self.base_tree)
1024
entries = (base_entry, other_entry, this_entry)
1027
for entry in entries:
1030
parents.append(None)
1032
names.append(entry.name)
1033
parents.append(entry.parent_id)
1034
return self._merge_names(file_id, parents, names,
1035
resolver=self._three_way)
1037
def _merge_names(self, file_id, parents, names, resolver):
1038
"""Perform a merge on file_id names and parents"""
1039
base_name, other_name, this_name = names
1040
base_parent, other_parent, this_parent = parents
1042
name_winner = resolver(*names)
1044
parent_id_winner = resolver(*parents)
1045
if this_name is None:
1046
if name_winner == "this":
1047
name_winner = "other"
1048
if parent_id_winner == "this":
1049
parent_id_winner = "other"
1050
if name_winner == "this" and parent_id_winner == "this":
1052
if name_winner == "conflict":
1053
trans_id = self.tt.trans_id_file_id(file_id)
1054
self._raw_conflicts.append(('name conflict', trans_id,
1055
this_name, other_name))
1056
if parent_id_winner == "conflict":
1057
trans_id = self.tt.trans_id_file_id(file_id)
1058
self._raw_conflicts.append(('parent conflict', trans_id,
1059
this_parent, other_parent))
1060
if other_name is None:
1061
# it doesn't matter whether the result was 'other' or
1062
# 'conflict'-- if there's no 'other', we leave it alone.
1064
# if we get here, name_winner and parent_winner are set to safe values.
1065
trans_id = self.tt.trans_id_file_id(file_id)
1066
parent_id = parents[self.winner_idx[parent_id_winner]]
1067
if parent_id is not None:
1068
parent_trans_id = self.tt.trans_id_file_id(parent_id)
1069
self.tt.adjust_path(names[self.winner_idx[name_winner]],
1070
parent_trans_id, trans_id)
1072
def merge_contents(self, file_id):
1073
"""Performa a merge on file_id contents."""
1074
def contents_pair(tree):
1075
if file_id not in tree:
1077
kind = tree.kind(file_id)
1079
contents = tree.get_file_sha1(file_id)
1080
elif kind == "symlink":
1081
contents = tree.get_symlink_target(file_id)
1084
return kind, contents
1086
def contents_conflict():
1087
trans_id = self.tt.trans_id_file_id(file_id)
1088
name = self.tt.final_name(trans_id)
1089
parent_id = self.tt.final_parent(trans_id)
1090
if file_id in self.this_tree.inventory:
1091
self.tt.unversion_file(trans_id)
1092
if file_id in self.this_tree:
1093
self.tt.delete_contents(trans_id)
1094
file_group = self._dump_conflicts(name, parent_id, file_id,
1096
self._raw_conflicts.append(('contents conflict', file_group))
1098
# See SPOT run. run, SPOT, run.
1099
# So we're not QUITE repeating ourselves; we do tricky things with
1101
base_pair = contents_pair(self.base_tree)
1102
other_pair = contents_pair(self.other_tree)
1103
if base_pair == other_pair:
1104
# OTHER introduced no changes
1106
this_pair = contents_pair(self.this_tree)
1107
if this_pair == other_pair:
1108
# THIS and OTHER introduced the same changes
1111
trans_id = self.tt.trans_id_file_id(file_id)
1112
if this_pair == base_pair:
1113
# only OTHER introduced changes
1114
if file_id in self.this_tree:
1115
# Remove any existing contents
1116
self.tt.delete_contents(trans_id)
1117
if file_id in self.other_tree:
1118
# OTHER changed the file
1119
create_by_entry(self.tt,
1120
self.other_tree.inventory[file_id],
1121
self.other_tree, trans_id)
1122
if file_id not in self.this_tree.inventory:
1123
self.tt.version_file(file_id, trans_id)
1125
elif file_id in self.this_tree.inventory:
1126
# OTHER deleted the file
1127
self.tt.unversion_file(trans_id)
1129
#BOTH THIS and OTHER introduced changes; scalar conflict
1130
elif this_pair[0] == "file" and other_pair[0] == "file":
1131
# THIS and OTHER are both files, so text merge. Either
1132
# BASE is a file, or both converted to files, so at least we
1133
# have agreement that output should be a file.
1135
self.text_merge(file_id, trans_id)
1137
return contents_conflict()
1138
if file_id not in self.this_tree.inventory:
1139
self.tt.version_file(file_id, trans_id)
1141
self.tt.tree_kind(trans_id)
1142
self.tt.delete_contents(trans_id)
1147
# Scalar conflict, can't text merge. Dump conflicts
1148
return contents_conflict()
1150
def get_lines(self, tree, file_id):
1151
"""Return the lines in a file, or an empty list."""
1153
return tree.get_file(file_id).readlines()
1157
def text_merge(self, file_id, trans_id):
1158
"""Perform a three-way text merge on a file_id"""
1159
# it's possible that we got here with base as a different type.
1160
# if so, we just want two-way text conflicts.
1161
if file_id in self.base_tree and \
1162
self.base_tree.kind(file_id) == "file":
1163
base_lines = self.get_lines(self.base_tree, file_id)
1166
other_lines = self.get_lines(self.other_tree, file_id)
1167
this_lines = self.get_lines(self.this_tree, file_id)
1168
m3 = Merge3(base_lines, this_lines, other_lines,
1169
is_cherrypick=self.cherrypick)
1170
start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
1171
if self.show_base is True:
1172
base_marker = '|' * 7
1176
def iter_merge3(retval):
1177
retval["text_conflicts"] = False
1178
for line in m3.merge_lines(name_a = "TREE",
1179
name_b = "MERGE-SOURCE",
1180
name_base = "BASE-REVISION",
1181
start_marker=start_marker,
1182
base_marker=base_marker,
1183
reprocess=self.reprocess):
1184
if line.startswith(start_marker):
1185
retval["text_conflicts"] = True
1186
yield line.replace(start_marker, '<' * 7)
1190
merge3_iterator = iter_merge3(retval)
1191
self.tt.create_file(merge3_iterator, trans_id)
1192
if retval["text_conflicts"] is True:
1193
self._raw_conflicts.append(('text conflict', trans_id))
1194
name = self.tt.final_name(trans_id)
1195
parent_id = self.tt.final_parent(trans_id)
1196
file_group = self._dump_conflicts(name, parent_id, file_id,
1197
this_lines, base_lines,
1199
file_group.append(trans_id)
1201
def _dump_conflicts(self, name, parent_id, file_id, this_lines=None,
1202
base_lines=None, other_lines=None, set_version=False,
1204
"""Emit conflict files.
1205
If this_lines, base_lines, or other_lines are omitted, they will be
1206
determined automatically. If set_version is true, the .OTHER, .THIS
1207
or .BASE (in that order) will be created as versioned files.
1209
data = [('OTHER', self.other_tree, other_lines),
1210
('THIS', self.this_tree, this_lines)]
1212
data.append(('BASE', self.base_tree, base_lines))
1215
for suffix, tree, lines in data:
1217
trans_id = self._conflict_file(name, parent_id, tree, file_id,
1219
file_group.append(trans_id)
1220
if set_version and not versioned:
1221
self.tt.version_file(file_id, trans_id)
1225
def _conflict_file(self, name, parent_id, tree, file_id, suffix,
1227
"""Emit a single conflict file."""
1228
name = name + '.' + suffix
1229
trans_id = self.tt.create_path(name, parent_id)
1230
entry = tree.inventory[file_id]
1231
create_by_entry(self.tt, entry, tree, trans_id, lines)
1234
def merge_executable(self, file_id, file_status):
1235
"""Perform a merge on the execute bit."""
1236
executable = [self.executable(t, file_id) for t in (self.base_tree,
1237
self.other_tree, self.this_tree)]
1238
self._merge_executable(file_id, executable, file_status,
1239
resolver=self._three_way)
1241
def _merge_executable(self, file_id, executable, file_status,
1243
"""Perform a merge on the execute bit."""
1244
base_executable, other_executable, this_executable = executable
1245
if file_status == "deleted":
1247
winner = resolver(*executable)
1248
if winner == "conflict":
1249
# There must be a None in here, if we have a conflict, but we
1250
# need executability since file status was not deleted.
1251
if self.executable(self.other_tree, file_id) is None:
1255
if winner == 'this' and file_status != "modified":
1257
trans_id = self.tt.trans_id_file_id(file_id)
1259
if self.tt.final_kind(trans_id) != "file":
1263
if winner == "this":
1264
executability = this_executable
1266
if file_id in self.other_tree:
1267
executability = other_executable
1268
elif file_id in self.this_tree:
1269
executability = this_executable
1270
elif file_id in self.base_tree:
1271
executability = base_executable
1272
if executability is not None:
1273
trans_id = self.tt.trans_id_file_id(file_id)
1274
self.tt.set_executability(executability, trans_id)
1276
def cook_conflicts(self, fs_conflicts):
1277
"""Convert all conflicts into a form that doesn't depend on trans_id"""
1278
from conflicts import Conflict
1280
self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
1281
fp = FinalPaths(self.tt)
1282
for conflict in self._raw_conflicts:
1283
conflict_type = conflict[0]
1284
if conflict_type in ('name conflict', 'parent conflict'):
1285
trans_id = conflict[1]
1286
conflict_args = conflict[2:]
1287
if trans_id not in name_conflicts:
1288
name_conflicts[trans_id] = {}
1289
unique_add(name_conflicts[trans_id], conflict_type,
1291
if conflict_type == 'contents conflict':
1292
for trans_id in conflict[1]:
1293
file_id = self.tt.final_file_id(trans_id)
1294
if file_id is not None:
1296
path = fp.get_path(trans_id)
1297
for suffix in ('.BASE', '.THIS', '.OTHER'):
1298
if path.endswith(suffix):
1299
path = path[:-len(suffix)]
1301
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1302
self.cooked_conflicts.append(c)
1303
if conflict_type == 'text conflict':
1304
trans_id = conflict[1]
1305
path = fp.get_path(trans_id)
1306
file_id = self.tt.final_file_id(trans_id)
1307
c = Conflict.factory(conflict_type, path=path, file_id=file_id)
1308
self.cooked_conflicts.append(c)
1310
for trans_id, conflicts in name_conflicts.iteritems():
1312
this_parent, other_parent = conflicts['parent conflict']
1313
if this_parent == other_parent:
1314
raise AssertionError()
1316
this_parent = other_parent = \
1317
self.tt.final_file_id(self.tt.final_parent(trans_id))
1319
this_name, other_name = conflicts['name conflict']
1320
if this_name == other_name:
1321
raise AssertionError()
1323
this_name = other_name = self.tt.final_name(trans_id)
1324
other_path = fp.get_path(trans_id)
1325
if this_parent is not None and this_name is not None:
1326
this_parent_path = \
1327
fp.get_path(self.tt.trans_id_file_id(this_parent))
1328
this_path = pathjoin(this_parent_path, this_name)
1330
this_path = "<deleted>"
1331
file_id = self.tt.final_file_id(trans_id)
1332
c = Conflict.factory('path conflict', path=this_path,
1333
conflict_path=other_path, file_id=file_id)
1334
self.cooked_conflicts.append(c)
1335
self.cooked_conflicts.sort(key=Conflict.sort_key)
1338
class WeaveMerger(Merge3Merger):
1339
"""Three-way tree merger, text weave merger."""
1340
supports_reprocess = True
1341
supports_show_base = False
1342
supports_reverse_cherrypick = False
1343
history_based = True
1345
def _merged_lines(self, file_id):
1346
"""Generate the merged lines.
1347
There is no distinction between lines that are meant to contain <<<<<<<
1351
base = self.base_tree
1354
plan = self.this_tree.plan_file_merge(file_id, self.other_tree,
1356
if 'merge' in debug.debug_flags:
1358
trans_id = self.tt.trans_id_file_id(file_id)
1359
name = self.tt.final_name(trans_id) + '.plan'
1360
contents = ('%10s|%s' % l for l in plan)
1361
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1362
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1363
'>>>>>>> MERGE-SOURCE\n')
1364
return textmerge.merge_lines(self.reprocess)
1366
def text_merge(self, file_id, trans_id):
1367
"""Perform a (weave) text merge for a given file and file-id.
1368
If conflicts are encountered, .THIS and .OTHER files will be emitted,
1369
and a conflict will be noted.
1371
lines, conflicts = self._merged_lines(file_id)
1373
# Note we're checking whether the OUTPUT is binary in this case,
1374
# because we don't want to get into weave merge guts.
1375
check_text_lines(lines)
1376
self.tt.create_file(lines, trans_id)
1378
self._raw_conflicts.append(('text conflict', trans_id))
1379
name = self.tt.final_name(trans_id)
1380
parent_id = self.tt.final_parent(trans_id)
1381
file_group = self._dump_conflicts(name, parent_id, file_id,
1383
file_group.append(trans_id)
1386
class LCAMerger(WeaveMerger):
1388
def _merged_lines(self, file_id):
1389
"""Generate the merged lines.
1390
There is no distinction between lines that are meant to contain <<<<<<<
1394
base = self.base_tree
1397
plan = self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1399
if 'merge' in debug.debug_flags:
1401
trans_id = self.tt.trans_id_file_id(file_id)
1402
name = self.tt.final_name(trans_id) + '.plan'
1403
contents = ('%10s|%s' % l for l in plan)
1404
self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1405
textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1406
'>>>>>>> MERGE-SOURCE\n')
1407
return textmerge.merge_lines(self.reprocess)
1410
class Diff3Merger(Merge3Merger):
1411
"""Three-way merger using external diff3 for text merging"""
1413
def dump_file(self, temp_dir, name, tree, file_id):
1414
out_path = pathjoin(temp_dir, name)
1415
out_file = open(out_path, "wb")
1417
in_file = tree.get_file(file_id)
1418
for line in in_file:
1419
out_file.write(line)
1424
def text_merge(self, file_id, trans_id):
1425
"""Perform a diff3 merge using a specified file-id and trans-id.
1426
If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
1427
will be dumped, and a will be conflict noted.
1430
temp_dir = osutils.mkdtemp(prefix="bzr-")
1432
new_file = pathjoin(temp_dir, "new")
1433
this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
1434
base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
1435
other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
1436
status = bzrlib.patch.diff3(new_file, this, base, other)
1437
if status not in (0, 1):
1438
raise BzrError("Unhandled diff3 exit code")
1439
f = open(new_file, 'rb')
1441
self.tt.create_file(f, trans_id)
1445
name = self.tt.final_name(trans_id)
1446
parent_id = self.tt.final_parent(trans_id)
1447
self._dump_conflicts(name, parent_id, file_id)
1448
self._raw_conflicts.append(('text conflict', trans_id))
1450
osutils.rmtree(temp_dir)
1453
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
1455
merge_type=Merge3Merger,
1456
interesting_ids=None,
1460
interesting_files=None,
1463
change_reporter=None):
1464
"""Primary interface for merging.
1466
typical use is probably
1467
'merge_inner(branch, branch.get_revision_tree(other_revision),
1468
branch.get_revision_tree(base_revision))'
1470
if this_tree is None:
1471
raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
1472
"parameter as of bzrlib version 0.8.")
1473
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1474
pb=pb, change_reporter=change_reporter)
1475
merger.backup_files = backup_files
1476
merger.merge_type = merge_type
1477
merger.interesting_ids = interesting_ids
1478
merger.ignore_zero = ignore_zero
1479
if interesting_files:
1481
raise ValueError('Only supply interesting_ids'
1482
' or interesting_files')
1483
merger.interesting_files = interesting_files
1484
merger.show_base = show_base
1485
merger.reprocess = reprocess
1486
merger.other_rev_id = other_rev_id
1487
merger.other_basis = other_rev_id
1488
get_revision_id = getattr(base_tree, 'get_revision_id', None)
1489
if get_revision_id is None:
1490
get_revision_id = base_tree.last_revision
1491
merger.set_base_revision(get_revision_id(), this_branch)
1492
return merger.do_merge()
1494
def get_merge_type_registry():
1495
"""Merge type registry is in bzrlib.option to avoid circular imports.
1497
This method provides a sanctioned way to retrieve it.
1499
from bzrlib import option
1500
return option._merge_type_registry
1503
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1504
def status_a(revision, text):
1505
if revision in ancestors_b:
1506
return 'killed-b', text
1508
return 'new-a', text
1510
def status_b(revision, text):
1511
if revision in ancestors_a:
1512
return 'killed-a', text
1514
return 'new-b', text
1516
plain_a = [t for (a, t) in annotated_a]
1517
plain_b = [t for (a, t) in annotated_b]
1518
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
1519
blocks = matcher.get_matching_blocks()
1522
for ai, bi, l in blocks:
1523
# process all mismatched sections
1524
# (last mismatched section is handled because blocks always
1525
# includes a 0-length last block)
1526
for revision, text in annotated_a[a_cur:ai]:
1527
yield status_a(revision, text)
1528
for revision, text in annotated_b[b_cur:bi]:
1529
yield status_b(revision, text)
1530
# and now the matched section
1533
for text_a in plain_a[ai:a_cur]:
1534
yield "unchanged", text_a
1537
class _PlanMergeBase(object):
1539
def __init__(self, a_rev, b_rev, vf, key_prefix):
1542
:param a_rev: Revision-id of one revision to merge
1543
:param b_rev: Revision-id of the other revision to merge
1544
:param vf: A VersionedFiles containing both revisions
1545
:param key_prefix: A prefix for accessing keys in vf, typically
1551
self._last_lines = None
1552
self._last_lines_revision_id = None
1553
self._cached_matching_blocks = {}
1554
self._key_prefix = key_prefix
1555
self._precache_tip_lines()
1557
def _precache_tip_lines(self):
1558
lines = self.get_lines([self.a_rev, self.b_rev])
1559
self.lines_a = lines[self.a_rev]
1560
self.lines_b = lines[self.b_rev]
1562
def get_lines(self, revisions):
1563
"""Get lines for revisions from the backing VersionedFiles.
1565
:raises RevisionNotPresent: on absent texts.
1567
keys = [(self._key_prefix + (rev,)) for rev in revisions]
1569
for record in self.vf.get_record_stream(keys, 'unordered', True):
1570
if record.storage_kind == 'absent':
1571
raise errors.RevisionNotPresent(record.key, self.vf)
1572
result[record.key[-1]] = osutils.split_lines(
1573
record.get_bytes_as('fulltext'))
1576
def plan_merge(self):
1577
"""Generate a 'plan' for merging the two revisions.
1579
This involves comparing their texts and determining the cause of
1580
differences. If text A has a line and text B does not, then either the
1581
line was added to text A, or it was deleted from B. Once the causes
1582
are combined, they are written out in the format described in
1583
VersionedFile.plan_merge
1585
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1586
unique_a, unique_b = self._unique_lines(blocks)
1587
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
1588
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
1589
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
1591
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1594
for i, j, n in blocks:
1595
for a_index in range(last_i, i):
1596
if a_index in new_a:
1597
if a_index in killed_b:
1598
yield 'conflicted-a', self.lines_a[a_index]
1600
yield 'new-a', self.lines_a[a_index]
1602
yield 'killed-b', self.lines_a[a_index]
1603
for b_index in range(last_j, j):
1604
if b_index in new_b:
1605
if b_index in killed_a:
1606
yield 'conflicted-b', self.lines_b[b_index]
1608
yield 'new-b', self.lines_b[b_index]
1610
yield 'killed-a', self.lines_b[b_index]
1611
# handle common lines
1612
for a_index in range(i, i+n):
1613
yield 'unchanged', self.lines_a[a_index]
1617
def _get_matching_blocks(self, left_revision, right_revision):
1618
"""Return a description of which sections of two revisions match.
1620
See SequenceMatcher.get_matching_blocks
1622
cached = self._cached_matching_blocks.get((left_revision,
1624
if cached is not None:
1626
if self._last_lines_revision_id == left_revision:
1627
left_lines = self._last_lines
1628
right_lines = self.get_lines([right_revision])[right_revision]
1630
lines = self.get_lines([left_revision, right_revision])
1631
left_lines = lines[left_revision]
1632
right_lines = lines[right_revision]
1633
self._last_lines = right_lines
1634
self._last_lines_revision_id = right_revision
1635
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1637
return matcher.get_matching_blocks()
1639
def _unique_lines(self, matching_blocks):
1640
"""Analyse matching_blocks to determine which lines are unique
1642
:return: a tuple of (unique_left, unique_right), where the values are
1643
sets of line numbers of unique lines.
1649
for i, j, n in matching_blocks:
1650
unique_left.extend(range(last_i, i))
1651
unique_right.extend(range(last_j, j))
1654
return unique_left, unique_right
1657
def _subtract_plans(old_plan, new_plan):
1658
"""Remove changes from new_plan that came from old_plan.
1660
It is assumed that the difference between the old_plan and new_plan
1661
is their choice of 'b' text.
1663
All lines from new_plan that differ from old_plan are emitted
1664
verbatim. All lines from new_plan that match old_plan but are
1665
not about the 'b' revision are emitted verbatim.
1667
Lines that match and are about the 'b' revision are the lines we
1668
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
1669
is skipped entirely.
1671
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1674
for i, j, n in matcher.get_matching_blocks():
1675
for jj in range(last_j, j):
1677
for jj in range(j, j+n):
1678
plan_line = new_plan[jj]
1679
if plan_line[0] == 'new-b':
1681
elif plan_line[0] == 'killed-b':
1682
yield 'unchanged', plan_line[1]
1688
class _PlanMerge(_PlanMergeBase):
1689
"""Plan an annotate merge using on-the-fly annotation"""
1691
def __init__(self, a_rev, b_rev, vf, key_prefix):
1692
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
1693
self.a_key = self._key_prefix + (self.a_rev,)
1694
self.b_key = self._key_prefix + (self.b_rev,)
1695
self.graph = Graph(self.vf)
1696
heads = self.graph.heads((self.a_key, self.b_key))
1698
# one side dominates, so we can just return its values, yay for
1700
# Ideally we would know that before we get this far
1701
self._head_key = heads.pop()
1702
if self._head_key == self.a_key:
1706
mutter('found dominating revision for %s\n%s > %s', self.vf,
1707
self._head_key[-1], other)
1710
self._head_key = None
1713
def _precache_tip_lines(self):
1714
# Turn this into a no-op, because we will do this later
1717
def _find_recursive_lcas(self):
1718
"""Find all the ancestors back to a unique lca"""
1719
cur_ancestors = (self.a_key, self.b_key)
1720
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
1721
# rather than a key tuple. We will just map that directly to no common
1725
next_lcas = self.graph.find_lca(*cur_ancestors)
1726
# Map a plain NULL_REVISION to a simple no-ancestors
1727
if next_lcas == set([NULL_REVISION]):
1729
# Order the lca's based on when they were merged into the tip
1730
# While the actual merge portion of weave merge uses a set() of
1731
# active revisions, the order of insertion *does* effect the
1732
# implicit ordering of the texts.
1733
for rev_key in cur_ancestors:
1734
ordered_parents = tuple(self.graph.find_merge_order(rev_key,
1736
parent_map[rev_key] = ordered_parents
1737
if len(next_lcas) == 0:
1739
elif len(next_lcas) == 1:
1740
parent_map[list(next_lcas)[0]] = ()
1742
elif len(next_lcas) > 2:
1743
# More than 2 lca's, fall back to grabbing all nodes between
1744
# this and the unique lca.
1745
mutter('More than 2 LCAs, falling back to all nodes for:'
1746
' %s, %s\n=> %s', self.a_key, self.b_key, cur_ancestors)
1747
cur_lcas = next_lcas
1748
while len(cur_lcas) > 1:
1749
cur_lcas = self.graph.find_lca(*cur_lcas)
1750
if len(cur_lcas) == 0:
1751
# No common base to find, use the full ancestry
1754
unique_lca = list(cur_lcas)[0]
1755
if unique_lca == NULL_REVISION:
1756
# find_lca will return a plain 'NULL_REVISION' rather
1757
# than a key tuple when there is no common ancestor, we
1758
# prefer to just use None, because it doesn't confuse
1759
# _get_interesting_texts()
1761
parent_map.update(self._find_unique_parents(next_lcas,
1764
cur_ancestors = next_lcas
1767
def _find_unique_parents(self, tip_keys, base_key):
1768
"""Find ancestors of tip that aren't ancestors of base.
1770
:param tip_keys: Nodes that are interesting
1771
:param base_key: Cull all ancestors of this node
1772
:return: The parent map for all revisions between tip_keys and
1773
base_key. base_key will be included. References to nodes outside of
1774
the ancestor set will also be removed.
1776
# TODO: this would be simpler if find_unique_ancestors took a list
1777
# instead of a single tip, internally it supports it, but it
1778
# isn't a "backwards compatible" api change.
1779
if base_key is None:
1780
parent_map = dict(self.graph.iter_ancestry(tip_keys))
1781
# We remove NULL_REVISION because it isn't a proper tuple key, and
1782
# thus confuses things like _get_interesting_texts, and our logic
1783
# to add the texts into the memory weave.
1784
if NULL_REVISION in parent_map:
1785
parent_map.pop(NULL_REVISION)
1788
for tip in tip_keys:
1790
self.graph.find_unique_ancestors(tip, [base_key]))
1791
parent_map = self.graph.get_parent_map(interesting)
1792
parent_map[base_key] = ()
1793
culled_parent_map, child_map, tails = self._remove_external_references(
1795
# Remove all the tails but base_key
1796
if base_key is not None:
1797
tails.remove(base_key)
1798
self._prune_tails(culled_parent_map, child_map, tails)
1799
# Now remove all the uninteresting 'linear' regions
1800
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
1804
def _remove_external_references(parent_map):
1805
"""Remove references that go outside of the parent map.
1807
:param parent_map: Something returned from Graph.get_parent_map(keys)
1808
:return: (filtered_parent_map, child_map, tails)
1809
filtered_parent_map is parent_map without external references
1810
child_map is the {parent_key: [child_keys]} mapping
1811
tails is a list of nodes that do not have any parents in the map
1813
# TODO: The basic effect of this function seems more generic than
1814
# _PlanMerge. But the specific details of building a child_map,
1815
# and computing tails seems very specific to _PlanMerge.
1816
# Still, should this be in Graph land?
1817
filtered_parent_map = {}
1820
for key, parent_keys in parent_map.iteritems():
1821
culled_parent_keys = [p for p in parent_keys if p in parent_map]
1822
if not culled_parent_keys:
1824
for parent_key in culled_parent_keys:
1825
child_map.setdefault(parent_key, []).append(key)
1826
# TODO: Do we want to do this, it adds overhead for every node,
1827
# just to say that the node has no children
1828
child_map.setdefault(key, [])
1829
filtered_parent_map[key] = culled_parent_keys
1830
return filtered_parent_map, child_map, tails
1833
def _prune_tails(parent_map, child_map, tails_to_remove):
1834
"""Remove tails from the parent map.
1836
This will remove the supplied revisions until no more children have 0
1839
:param parent_map: A dict of {child: [parents]}, this dictionary will
1840
be modified in place.
1841
:param tails_to_remove: A list of tips that should be removed,
1842
this list will be consumed
1843
:param child_map: The reverse dict of parent_map ({parent: [children]})
1844
this dict will be modified
1845
:return: None, parent_map will be modified in place.
1847
while tails_to_remove:
1848
next = tails_to_remove.pop()
1849
parent_map.pop(next)
1850
children = child_map.pop(next)
1851
for child in children:
1852
child_parents = parent_map[child]
1853
child_parents.remove(next)
1854
if len(child_parents) == 0:
1855
tails_to_remove.append(child)
1857
def _get_interesting_texts(self, parent_map):
1858
"""Return a dict of texts we are interested in.
1860
Note that the input is in key tuples, but the output is in plain
1863
:param parent_map: The output from _find_recursive_lcas
1864
:return: A dict of {'revision_id':lines} as returned by
1865
_PlanMergeBase.get_lines()
1867
all_revision_keys = set(parent_map)
1868
all_revision_keys.add(self.a_key)
1869
all_revision_keys.add(self.b_key)
1871
# Everything else is in 'keys' but get_lines is in 'revision_ids'
1872
all_texts = self.get_lines([k[-1] for k in all_revision_keys])
1875
def _build_weave(self):
1876
from bzrlib import weave
1877
self._weave = weave.Weave(weave_name='in_memory_weave',
1878
allow_reserved=True)
1879
parent_map = self._find_recursive_lcas()
1881
all_texts = self._get_interesting_texts(parent_map)
1883
# Note: Unfortunately, the order given by topo_sort will effect the
1884
# ordering resolution in the output. Specifically, if you add A then B,
1885
# then in the output text A lines will show up before B lines. And, of
1886
# course, topo_sort doesn't guarantee any real ordering.
1887
# So we use merge_sort, and add a fake node on the tip.
1888
# This ensures that left-hand parents will always be inserted into the
1889
# weave before right-hand parents.
1890
tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
1891
parent_map[tip_key] = (self.a_key, self.b_key)
1893
for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
1897
# for key in tsort.topo_sort(parent_map):
1898
parent_keys = parent_map[key]
1899
revision_id = key[-1]
1900
parent_ids = [k[-1] for k in parent_keys]
1901
self._weave.add_lines(revision_id, parent_ids,
1902
all_texts[revision_id])
1904
def plan_merge(self):
1905
"""Generate a 'plan' for merging the two revisions.
1907
This involves comparing their texts and determining the cause of
1908
differences. If text A has a line and text B does not, then either the
1909
line was added to text A, or it was deleted from B. Once the causes
1910
are combined, they are written out in the format described in
1911
VersionedFile.plan_merge
1913
if self._head_key is not None: # There was a single head
1914
if self._head_key == self.a_key:
1917
if self._head_key != self.b_key:
1918
raise AssertionError('There was an invalid head: %s != %s'
1919
% (self.b_key, self._head_key))
1921
head_rev = self._head_key[-1]
1922
lines = self.get_lines([head_rev])[head_rev]
1923
return ((plan, line) for line in lines)
1924
return self._weave.plan_merge(self.a_rev, self.b_rev)
1927
class _PlanLCAMerge(_PlanMergeBase):
1929
This merge algorithm differs from _PlanMerge in that:
1930
1. comparisons are done against LCAs only
1931
2. cases where a contested line is new versus one LCA but old versus
1932
another are marked as conflicts, by emitting the line as conflicted-a
1935
This is faster, and hopefully produces more useful output.
1938
def __init__(self, a_rev, b_rev, vf, key_prefix, graph):
1939
_PlanMergeBase.__init__(self, a_rev, b_rev, vf, key_prefix)
1940
lcas = graph.find_lca(key_prefix + (a_rev,), key_prefix + (b_rev,))
1943
if lca == NULL_REVISION:
1946
self.lcas.add(lca[-1])
1947
for lca in self.lcas:
1948
if _mod_revision.is_null(lca):
1951
lca_lines = self.get_lines([lca])[lca]
1952
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
1954
blocks = list(matcher.get_matching_blocks())
1955
self._cached_matching_blocks[(a_rev, lca)] = blocks
1956
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
1958
blocks = list(matcher.get_matching_blocks())
1959
self._cached_matching_blocks[(b_rev, lca)] = blocks
1961
def _determine_status(self, revision_id, unique_line_numbers):
1962
"""Determines the status unique lines versus all lcas.
1964
Basically, determines why the line is unique to this revision.
1966
A line may be determined new, killed, or both.
1968
If a line is determined new, that means it was not present in at least
1969
one LCA, and is not present in the other merge revision.
1971
If a line is determined killed, that means the line was present in
1974
If a line is killed and new, this indicates that the two merge
1975
revisions contain differing conflict resolutions.
1976
:param revision_id: The id of the revision in which the lines are
1978
:param unique_line_numbers: The line numbers of unique lines.
1979
:return a tuple of (new_this, killed_other):
1983
unique_line_numbers = set(unique_line_numbers)
1984
for lca in self.lcas:
1985
blocks = self._get_matching_blocks(revision_id, lca)
1986
unique_vs_lca, _ignored = self._unique_lines(blocks)
1987
new.update(unique_line_numbers.intersection(unique_vs_lca))
1988
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
bzrlib/merge.py
