86
70
class Merger(object):
87
def __init__(self, this_branch, other_tree=None, base_tree=None,
88
this_tree=None, pb=DummyProgress()):
71
def __init__(self, this_branch, other_tree=None, base_tree=None,
72
this_tree=None, pb=DummyProgress(), change_reporter=None,
73
recurse='down', revision_graph=None):
89
74
object.__init__(self)
90
assert this_tree is not None, "this_tree is required"
91
75
self.this_branch = this_branch
92
self.this_basis = this_branch.last_revision()
76
self.this_basis = _mod_revision.ensure_null(
77
this_branch.last_revision())
93
78
self.this_rev_id = None
94
79
self.this_tree = this_tree
95
80
self.this_revision_tree = None
96
81
self.this_basis_tree = None
97
82
self.other_tree = other_tree
83
self.other_branch = None
98
84
self.base_tree = base_tree
99
85
self.ignore_zero = False
100
86
self.backup_files = False
101
87
self.interesting_ids = None
88
self.interesting_files = None
102
89
self.show_base = False
103
90
self.reprocess = False
108
def revision_tree(self, revision_id):
109
return self.this_branch.repository.revision_tree(revision_id)
93
self.recurse = recurse
94
self.change_reporter = change_reporter
95
self._cached_trees = {}
96
self._revision_graph = revision_graph
97
self._base_is_ancestor = None
98
self._base_is_other_ancestor = None
101
def revision_graph(self):
102
if self._revision_graph is None:
103
self._revision_graph = self.this_branch.repository.get_graph()
104
return self._revision_graph
106
def _set_base_is_ancestor(self, value):
107
self._base_is_ancestor = value
109
def _get_base_is_ancestor(self):
110
if self._base_is_ancestor is None:
111
self._base_is_ancestor = self.revision_graph.is_ancestor(
112
self.base_rev_id, self.this_basis)
113
return self._base_is_ancestor
115
base_is_ancestor = property(_get_base_is_ancestor, _set_base_is_ancestor)
117
def _set_base_is_other_ancestor(self, value):
118
self._base_is_other_ancestor = value
120
def _get_base_is_other_ancestor(self):
121
if self._base_is_other_ancestor is None:
122
if self.other_basis is None:
124
self._base_is_other_ancestor = self.revision_graph.is_ancestor(
125
self.base_rev_id, self.other_basis)
126
return self._base_is_other_ancestor
128
base_is_other_ancestor = property(_get_base_is_other_ancestor,
129
_set_base_is_other_ancestor)
132
def from_uncommitted(tree, other_tree, pb):
133
"""Return a Merger for uncommitted changes in other_tree.
135
:param tree: The tree to merge into
136
:param other_tree: The tree to get uncommitted changes from
137
:param pb: A progress indicator
139
merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,
141
merger.base_rev_id = merger.base_tree.get_revision_id()
142
merger.other_rev_id = None
143
merger.other_basis = merger.base_rev_id
147
def from_mergeable(klass, tree, mergeable, pb):
148
"""Return a Merger for a bundle or merge directive.
150
:param tree: The tree to merge changes into
151
:param mergeable: A merge directive or bundle
152
:param pb: A progress indicator
154
mergeable.install_revisions(tree.branch.repository)
155
base_revision_id, other_revision_id, verified =\
156
mergeable.get_merge_request(tree.branch.repository)
157
revision_graph = tree.branch.repository.get_graph()
158
if base_revision_id is not None:
159
if (base_revision_id != _mod_revision.NULL_REVISION and
160
revision_graph.is_ancestor(
161
base_revision_id, tree.branch.last_revision())):
162
base_revision_id = None
164
warning('Performing cherrypick')
165
merger = klass.from_revision_ids(pb, tree, other_revision_id,
166
base_revision_id, revision_graph=
168
return merger, verified
171
def from_revision_ids(pb, tree, other, base=None, other_branch=None,
172
base_branch=None, revision_graph=None):
173
"""Return a Merger for revision-ids.
175
:param tree: The tree to merge changes into
176
:param other: The revision-id to use as OTHER
177
:param base: The revision-id to use as BASE. If not specified, will
179
:param other_branch: A branch containing the other revision-id. If
180
not supplied, tree.branch is used.
181
:param base_branch: A branch containing the base revision-id. If
182
not supplied, other_branch or tree.branch will be used.
183
:param revision_graph: If you have a revision_graph precomputed, pass
184
it in, otherwise it will be created for you.
185
:param pb: A progress indicator
187
merger = Merger(tree.branch, this_tree=tree, pb=pb,
188
revision_graph=revision_graph)
189
if other_branch is None:
190
other_branch = tree.branch
191
merger.set_other_revision(other, other_branch)
195
if base_branch is None:
196
base_branch = other_branch
197
merger.set_base_revision(base, base_branch)
200
def revision_tree(self, revision_id, branch=None):
201
if revision_id not in self._cached_trees:
203
branch = self.this_branch
205
tree = self.this_tree.revision_tree(revision_id)
206
except errors.NoSuchRevisionInTree:
207
tree = branch.repository.revision_tree(revision_id)
208
self._cached_trees[revision_id] = tree
209
return self._cached_trees[revision_id]
211
def _get_tree(self, treespec, possible_transports=None):
212
from bzrlib import workingtree
213
location, revno = treespec
215
tree = workingtree.WorkingTree.open_containing(location)[0]
216
return tree.branch, tree
217
branch = Branch.open_containing(location, possible_transports)[0]
219
revision_id = branch.last_revision()
221
revision_id = branch.get_rev_id(revno)
222
revision_id = ensure_null(revision_id)
223
return branch, self.revision_tree(revision_id, branch)
111
225
def ensure_revision_trees(self):
112
226
if self.this_revision_tree is None:
113
self.this_basis_tree = self.this_branch.repository.revision_tree(
227
self.this_basis_tree = self.revision_tree(self.this_basis)
115
228
if self.this_basis == self.this_rev_id:
116
229
self.this_revision_tree = self.this_basis_tree
118
231
if self.other_rev_id is None:
119
232
other_basis_tree = self.revision_tree(self.other_basis)
120
changes = compare_trees(self.other_tree, other_basis_tree)
233
changes = other_basis_tree.changes_from(self.other_tree)
121
234
if changes.has_changed():
122
235
raise WorkingTreeNotRevision(self.this_tree)
123
other_rev_id = other_basis
236
other_rev_id = self.other_basis
124
237
self.other_tree = other_basis_tree
126
239
def file_revisions(self, file_id):
127
240
self.ensure_revision_trees()
128
241
def get_id(tree, file_id):
129
242
revision_id = tree.inventory[file_id].revision
130
assert revision_id is not None
131
243
return revision_id
132
244
if self.this_rev_id is None:
133
245
if self.this_basis_tree.get_file_sha1(file_id) != \
140
252
def check_basis(self, check_clean, require_commits=True):
141
253
if self.this_basis is None and require_commits is True:
142
raise BzrCommandError("This branch has no commits")
254
raise BzrCommandError("This branch has no commits."
255
" (perhaps you would prefer 'bzr pull')")
144
257
self.compare_basis()
145
258
if self.this_basis != self.this_rev_id:
146
raise BzrCommandError("Working tree has uncommitted changes.")
259
raise errors.UncommittedChanges(self.this_tree)
148
261
def compare_basis(self):
149
changes = compare_trees(self.this_tree,
150
self.this_tree.basis_tree(), False)
263
basis_tree = self.revision_tree(self.this_tree.last_revision())
264
except errors.NoSuchRevision:
265
basis_tree = self.this_tree.basis_tree()
266
changes = self.this_tree.changes_from(basis_tree)
151
267
if not changes.has_changed():
152
268
self.this_rev_id = self.this_basis
154
270
def set_interesting_files(self, file_list):
156
self._set_interesting_files(file_list)
157
except NotVersionedError, e:
158
raise BzrCommandError("%s is not a source file in any"
161
def _set_interesting_files(self, file_list):
162
"""Set the list of interesting ids from a list of files."""
163
if file_list is None:
164
self.interesting_ids = None
167
interesting_ids = set()
168
for path in file_list:
170
for tree in (self.this_tree, self.base_tree, self.other_tree):
171
file_id = tree.inventory.path2id(path)
172
if file_id is not None:
173
interesting_ids.add(file_id)
176
raise NotVersionedError(path=path)
177
self.interesting_ids = interesting_ids
271
self.interesting_files = file_list
179
273
def set_pending(self):
180
if not self.base_is_ancestor:
182
if self.other_rev_id is None:
184
ancestry = self.this_branch.repository.get_ancestry(self.this_basis)
185
if self.other_rev_id in ancestry:
187
self.this_tree.add_pending_merge(self.other_rev_id)
189
def set_other(self, other_revision):
190
other_branch, self.other_tree = _get_tree(other_revision,
274
if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:
278
def _add_parent(self):
279
new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
280
new_parent_trees = []
281
for revision_id in new_parents:
283
tree = self.revision_tree(revision_id)
284
except errors.NoSuchRevision:
288
new_parent_trees.append((revision_id, tree))
290
self.this_tree.set_parent_trees(new_parent_trees,
291
allow_leftmost_as_ghost=True)
293
for _revision_id, tree in new_parent_trees:
297
def set_other(self, other_revision, possible_transports=None):
298
"""Set the revision and tree to merge from.
300
This sets the other_tree, other_rev_id, other_basis attributes.
302
:param other_revision: The [path, revision] list to merge from.
304
self.other_branch, self.other_tree = self._get_tree(other_revision,
192
306
if other_revision[1] == -1:
193
self.other_rev_id = other_branch.last_revision()
194
if self.other_rev_id is None:
195
raise NoCommits(other_branch)
307
self.other_rev_id = _mod_revision.ensure_null(
308
self.other_branch.last_revision())
309
if _mod_revision.is_null(self.other_rev_id):
310
raise NoCommits(self.other_branch)
196
311
self.other_basis = self.other_rev_id
197
312
elif other_revision[1] is not None:
198
self.other_rev_id = other_branch.get_rev_id(other_revision[1])
313
self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
199
314
self.other_basis = self.other_rev_id
201
316
self.other_rev_id = None
202
self.other_basis = other_branch.last_revision()
317
self.other_basis = self.other_branch.last_revision()
203
318
if self.other_basis is None:
204
raise NoCommits(other_branch)
205
if other_branch.base != self.this_branch.base:
206
self.this_branch.fetch(other_branch, last_revision=self.other_basis)
319
raise NoCommits(self.other_branch)
320
if self.other_rev_id is not None:
321
self._cached_trees[self.other_rev_id] = self.other_tree
322
self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)
324
def set_other_revision(self, revision_id, other_branch):
325
"""Set 'other' based on a branch and revision id
327
:param revision_id: The revision to use for a tree
328
:param other_branch: The branch containing this tree
330
self.other_rev_id = revision_id
331
self.other_branch = other_branch
332
self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
333
self.other_tree = self.revision_tree(revision_id)
334
self.other_basis = revision_id
336
def set_base_revision(self, revision_id, branch):
337
"""Set 'base' based on a branch and revision id
339
:param revision_id: The revision to use for a tree
340
:param branch: The branch containing this tree
342
self.base_rev_id = revision_id
343
self.base_branch = branch
344
self._maybe_fetch(branch, self.this_branch, revision_id)
345
self.base_tree = self.revision_tree(revision_id)
347
def _maybe_fetch(self, source, target, revision_id):
348
if not source.repository.has_same_location(target.repository):
349
target.fetch(source, revision_id)
208
351
def find_base(self):
209
self.set_base([None, None])
352
revisions = [ensure_null(self.this_basis),
353
ensure_null(self.other_basis)]
354
if NULL_REVISION in revisions:
355
self.base_rev_id = NULL_REVISION
357
self.base_rev_id, steps = self.revision_graph.find_unique_lca(
358
revisions[0], revisions[1], count_steps=True)
359
if self.base_rev_id == NULL_REVISION:
360
raise UnrelatedBranches()
362
warning('Warning: criss-cross merge encountered. See bzr'
363
' help criss-cross.')
364
self.base_tree = self.revision_tree(self.base_rev_id)
365
self.base_is_ancestor = True
366
self.base_is_other_ancestor = True
211
368
def set_base(self, base_revision):
369
"""Set the base revision to use for the merge.
371
:param base_revision: A 2-list containing a path and revision number.
212
373
mutter("doing merge() with no base_revision specified")
213
374
if base_revision == [None, None]:
215
pb = bzrlib.ui.ui_factory.nested_progress_bar()
217
this_repo = self.this_branch.repository
218
self.base_rev_id = common_ancestor(self.this_basis,
223
except NoCommonAncestor:
224
raise UnrelatedBranches()
225
self.base_tree = _get_revid_tree(self.this_branch, self.base_rev_id,
227
self.base_is_ancestor = True
229
base_branch, self.base_tree = _get_tree(base_revision)
377
base_branch, self.base_tree = self._get_tree(base_revision)
230
378
if base_revision[1] == -1:
231
379
self.base_rev_id = base_branch.last_revision()
232
380
elif base_revision[1] is None:
233
self.base_rev_id = None
381
self.base_rev_id = _mod_revision.NULL_REVISION
235
self.base_rev_id = base_branch.get_rev_id(base_revision[1])
236
if self.this_branch.base != base_branch.base:
237
self.this_branch.fetch(base_branch)
238
self.base_is_ancestor = is_ancestor(self.this_basis,
383
self.base_rev_id = _mod_revision.ensure_null(
384
base_branch.get_rev_id(base_revision[1]))
385
self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
243
kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
244
'other_tree': self.other_tree,
387
def make_merger(self):
388
kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
389
'other_tree': self.other_tree,
245
390
'interesting_ids': self.interesting_ids,
391
'interesting_files': self.interesting_files,
247
394
if self.merge_type.requires_base:
248
395
kwargs['base_tree'] = self.base_tree
249
396
if self.merge_type.supports_reprocess:
255
402
kwargs['show_base'] = self.show_base
256
403
elif self.show_base:
257
404
raise BzrError("Showing base is not supported for this"
258
" merge type. %s" % self.merge_type)
259
merge = self.merge_type(pb=self._pb, **kwargs)
405
" merge type. %s" % self.merge_type)
406
if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
407
and not self.base_is_other_ancestor):
408
raise errors.CannotReverseCherrypick()
409
if self.merge_type.supports_cherrypick:
410
kwargs['cherrypick'] = (not self.base_is_ancestor or
411
not self.base_is_other_ancestor)
412
return self.merge_type(pb=self._pb,
413
change_reporter=self.change_reporter,
416
def _do_merge_to(self, merge):
418
if self.recurse == 'down':
419
for relpath, file_id in self.this_tree.iter_references():
420
sub_tree = self.this_tree.get_nested_tree(file_id, relpath)
421
other_revision = self.other_tree.get_reference_revision(
423
if other_revision == sub_tree.last_revision():
425
sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
426
sub_merge.merge_type = self.merge_type
427
other_branch = self.other_branch.reference_parent(file_id, relpath)
428
sub_merge.set_other_revision(other_revision, other_branch)
429
base_revision = self.base_tree.get_reference_revision(file_id)
430
sub_merge.base_tree = \
431
sub_tree.branch.repository.revision_tree(base_revision)
432
sub_merge.base_rev_id = base_revision
436
self.this_tree.lock_tree_write()
438
if self.base_tree is not None:
439
self.base_tree.lock_read()
441
if self.other_tree is not None:
442
self.other_tree.lock_read()
444
merge = self.make_merger()
445
self._do_merge_to(merge)
447
if self.other_tree is not None:
448
self.other_tree.unlock()
450
if self.base_tree is not None:
451
self.base_tree.unlock()
453
self.this_tree.unlock()
260
454
if len(merge.cooked_conflicts) == 0:
261
if not self.ignore_zero:
455
if not self.ignore_zero and not is_quiet():
262
456
note("All changes applied successfully.")
264
458
note("%d conflicts encountered." % len(merge.cooked_conflicts))
266
460
return len(merge.cooked_conflicts)
268
def regen_inventory(self, new_entries):
269
old_entries = self.this_tree.read_working_inventory()
273
for path, file_id in new_entries:
276
new_entries_map[file_id] = path
278
def id2path(file_id):
279
path = new_entries_map.get(file_id)
282
entry = old_entries[file_id]
283
if entry.parent_id is None:
285
return pathjoin(id2path(entry.parent_id), entry.name)
287
for file_id in old_entries:
288
entry = old_entries[file_id]
289
path = id2path(file_id)
290
if file_id in self.base_tree.inventory:
291
executable = getattr(self.base_tree.inventory[file_id], 'executable', False)
293
executable = getattr(entry, 'executable', False)
294
new_inventory[file_id] = (path, file_id, entry.parent_id,
295
entry.kind, executable)
297
by_path[path] = file_id
302
for path, file_id in new_entries:
304
del new_inventory[file_id]
307
new_path_list.append((path, file_id))
308
if file_id not in old_entries:
310
# Ensure no file is added before its parent
312
for path, file_id in new_path_list:
316
parent = by_path[os.path.dirname(path)]
317
abspath = pathjoin(self.this_tree.basedir, path)
318
kind = bzrlib.osutils.file_kind(abspath)
319
if file_id in self.base_tree.inventory:
320
executable = getattr(self.base_tree.inventory[file_id], 'executable', False)
323
new_inventory[file_id] = (path, file_id, parent, kind, executable)
324
by_path[path] = file_id
326
# Get a list in insertion order
327
new_inventory_list = new_inventory.values()
328
mutter ("""Inventory regeneration:
329
old length: %i insertions: %i deletions: %i new_length: %i"""\
330
% (len(old_entries), insertions, deletions,
331
len(new_inventory_list)))
332
assert len(new_inventory_list) == len(old_entries) + insertions\
334
new_inventory_list.sort()
335
return new_inventory_list
338
463
class Merge3Merger(object):
339
464
"""Three-way merger that uses the merge3 text merger"""
356
512
self.show_base = show_base
515
self.change_reporter = change_reporter
516
self.cherrypick = cherrypick
359
517
if self.pp is None:
360
518
self.pp = ProgressPhase("Merge phase", 3, self.pb)
362
if interesting_ids is not None:
363
all_ids = interesting_ids
365
all_ids = set(base_tree)
366
all_ids.update(other_tree)
367
working_tree.lock_write()
368
self.tt = TreeTransform(working_tree, self.pb)
523
self.this_tree.lock_tree_write()
524
self.base_tree.lock_read()
525
self.other_tree.lock_read()
526
self.tt = TreeTransform(self.this_tree, self.pb)
370
528
self.pp.next_phase()
371
child_pb = bzrlib.ui.ui_factory.nested_progress_bar()
373
for num, file_id in enumerate(all_ids):
374
child_pb.update('Preparing file merge', num, len(all_ids))
375
self.merge_names(file_id)
376
file_status = self.merge_contents(file_id)
377
self.merge_executable(file_id, file_status)
382
child_pb = bzrlib.ui.ui_factory.nested_progress_bar()
384
fs_conflicts = resolve_conflicts(self.tt, child_pb)
387
self.cook_conflicts(fs_conflicts)
388
for conflict in self.cooked_conflicts:
391
results = self.tt.apply()
529
self._compute_transform()
531
results = self.tt.apply(no_conflicts=True)
392
532
self.write_modified(results)
394
working_tree.set_conflicts(ConflictList(self.cooked_conflicts))
534
self.this_tree.add_conflicts(self.cooked_conflicts)
395
535
except UnsupportedOperation:
402
working_tree.unlock()
539
self.other_tree.unlock()
540
self.base_tree.unlock()
541
self.this_tree.unlock()
544
def make_preview_transform(self):
545
self.base_tree.lock_read()
546
self.other_tree.lock_read()
547
self.tt = TransformPreview(self.this_tree)
550
self._compute_transform()
553
self.other_tree.unlock()
554
self.base_tree.unlock()
558
def _compute_transform(self):
559
entries = self._entries3()
560
child_pb = ui.ui_factory.nested_progress_bar()
562
for num, (file_id, changed, parents3, names3,
563
executable3) in enumerate(entries):
564
child_pb.update('Preparing file merge', num, len(entries))
565
self._merge_names(file_id, parents3, names3)
567
file_status = self.merge_contents(file_id)
569
file_status = 'unmodified'
570
self._merge_executable(file_id,
571
executable3, file_status)
576
child_pb = ui.ui_factory.nested_progress_bar()
578
fs_conflicts = resolve_conflicts(self.tt, child_pb,
579
lambda t, c: conflict_pass(t, c, self.other_tree))
582
if self.change_reporter is not None:
583
from bzrlib import delta
584
delta.report_changes(
585
self.tt.iter_changes(), self.change_reporter)
586
self.cook_conflicts(fs_conflicts)
587
for conflict in self.cooked_conflicts:
591
"""Gather data about files modified between three trees.
593
Return a list of tuples of file_id, changed, parents3, names3,
594
executable3. changed is a boolean indicating whether the file contents
595
or kind were changed. parents3 is a tuple of parent ids for base,
596
other and this. names3 is a tuple of names for base, other and this.
597
executable3 is a tuple of execute-bit values for base, other and this.
600
iterator = self.other_tree.iter_changes(self.base_tree,
601
include_unchanged=True, specific_files=self.interesting_files,
602
extra_trees=[self.this_tree])
603
for (file_id, paths, changed, versioned, parents, names, kind,
604
executable) in iterator:
605
if (self.interesting_ids is not None and
606
file_id not in self.interesting_ids):
608
if file_id in self.this_tree.inventory:
609
entry = self.this_tree.inventory[file_id]
610
this_name = entry.name
611
this_parent = entry.parent_id
612
this_executable = entry.executable
616
this_executable = None
617
parents3 = parents + (this_parent,)
618
names3 = names + (this_name,)
619
executable3 = executable + (this_executable,)
620
result.append((file_id, changed, parents3, names3, executable3))
625
self.tt.final_kind(self.tt.root)
627
self.tt.cancel_deletion(self.tt.root)
628
if self.tt.final_file_id(self.tt.root) is None:
629
self.tt.version_file(self.tt.tree_file_id(self.tt.root),
631
if self.other_tree.inventory.root is None:
633
other_root_file_id = self.other_tree.get_root_id()
634
other_root = self.tt.trans_id_file_id(other_root_file_id)
635
if other_root == self.tt.root:
638
self.tt.final_kind(other_root)
641
if self.other_tree.inventory.root.file_id in self.this_tree.inventory:
642
# the other tree's root is a non-root in the current tree
644
self.reparent_children(self.other_tree.inventory.root, self.tt.root)
645
self.tt.cancel_creation(other_root)
646
self.tt.cancel_versioning(other_root)
648
def reparent_children(self, ie, target):
649
for thing, child in ie.children.iteritems():
650
trans_id = self.tt.trans_id_file_id(child.file_id)
651
self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)
405
653
def write_modified(self, results):
406
654
modified_hashes = {}
896
1185
branch.get_revision_tree(base_revision))'
898
1187
if this_tree is None:
899
warn("bzrlib.merge.merge_inner requires a this_tree parameter as of "
900
"bzrlib version 0.8.",
903
this_tree = this_branch.bzrdir.open_workingtree()
904
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1188
raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
1189
"parameter as of bzrlib version 0.8.")
1190
merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1191
pb=pb, change_reporter=change_reporter)
906
1192
merger.backup_files = backup_files
907
1193
merger.merge_type = merge_type
908
1194
merger.interesting_ids = interesting_ids
909
1195
merger.ignore_zero = ignore_zero
910
1196
if interesting_files:
911
assert not interesting_ids, ('Only supply interesting_ids'
912
' or interesting_files')
913
merger._set_interesting_files(interesting_files)
914
merger.show_base = show_base
1198
raise ValueError('Only supply interesting_ids'
1199
' or interesting_files')
1200
merger.interesting_files = interesting_files
1201
merger.show_base = show_base
915
1202
merger.reprocess = reprocess
916
1203
merger.other_rev_id = other_rev_id
917
1204
merger.other_basis = other_rev_id
1205
get_revision_id = getattr(base_tree, 'get_revision_id', None)
1206
if get_revision_id is None:
1207
get_revision_id = base_tree.last_revision
1208
merger.set_base_revision(get_revision_id(), this_branch)
918
1209
return merger.do_merge()
921
merge_types = { "merge3": (Merge3Merger, "Native diff3-style merge"),
922
"diff3": (Diff3Merger, "Merge using external diff3"),
923
'weave': (WeaveMerger, "Weave-based merge")
927
def merge_type_help():
928
templ = '%s%%7s: %%s' % (' '*12)
929
lines = [templ % (f[0], f[1][1]) for f in merge_types.iteritems()]
930
return '\n'.join(lines)
1211
def get_merge_type_registry():
1212
"""Merge type registry is in bzrlib.option to avoid circular imports.
1214
This method provides a sanctioned way to retrieve it.
1216
from bzrlib import option
1217
return option._merge_type_registry
1220
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
1221
def status_a(revision, text):
1222
if revision in ancestors_b:
1223
return 'killed-b', text
1225
return 'new-a', text
1227
def status_b(revision, text):
1228
if revision in ancestors_a:
1229
return 'killed-a', text
1231
return 'new-b', text
1233
plain_a = [t for (a, t) in annotated_a]
1234
plain_b = [t for (a, t) in annotated_b]
1235
matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
1236
blocks = matcher.get_matching_blocks()
1239
for ai, bi, l in blocks:
1240
# process all mismatched sections
1241
# (last mismatched section is handled because blocks always
1242
# includes a 0-length last block)
1243
for revision, text in annotated_a[a_cur:ai]:
1244
yield status_a(revision, text)
1245
for revision, text in annotated_b[b_cur:bi]:
1246
yield status_b(revision, text)
1247
# and now the matched section
1250
for text_a in plain_a[ai:a_cur]:
1251
yield "unchanged", text_a
1254
class _PlanMergeBase(object):
1256
def __init__(self, a_rev, b_rev, vf, key_prefix):
1259
:param a_rev: Revision-id of one revision to merge
1260
:param b_rev: Revision-id of the other revision to merge
1261
:param vf: A VersionedFiles containing both revisions
1262
:param key_prefix: A prefix for accessing keys in vf, typically
1268
self._last_lines = None
1269
self._last_lines_revision_id = None
1270
self._cached_matching_blocks = {}
1271
self._key_prefix = key_prefix
1272
self._precache_tip_lines()
1274
def _precache_tip_lines(self):
1275
lines = self.get_lines([self.a_rev, self.b_rev])
1276
self.lines_a = lines[self.a_rev]
1277
self.lines_b = lines[self.b_rev]
1279
def get_lines(self, revisions):
1280
"""Get lines for revisions from the backing VersionedFiles.
1282
:raises RevisionNotPresent: on absent texts.
1284
keys = [(self._key_prefix + (rev,)) for rev in revisions]
1286
for record in self.vf.get_record_stream(keys, 'unordered', True):
1287
if record.storage_kind == 'absent':
1288
raise errors.RevisionNotPresent(record.key, self.vf)
1289
result[record.key[-1]] = osutils.split_lines(
1290
record.get_bytes_as('fulltext'))
1293
def plan_merge(self):
1294
"""Generate a 'plan' for merging the two revisions.
1296
This involves comparing their texts and determining the cause of
1297
differences. If text A has a line and text B does not, then either the
1298
line was added to text A, or it was deleted from B. Once the causes
1299
are combined, they are written out in the format described in
1300
VersionedFile.plan_merge
1302
blocks = self._get_matching_blocks(self.a_rev, self.b_rev)
1303
unique_a, unique_b = self._unique_lines(blocks)
1304
new_a, killed_b = self._determine_status(self.a_rev, unique_a)
1305
new_b, killed_a = self._determine_status(self.b_rev, unique_b)
1306
return self._iter_plan(blocks, new_a, killed_b, new_b, killed_a)
1308
def _iter_plan(self, blocks, new_a, killed_b, new_b, killed_a):
1311
for i, j, n in blocks:
1312
for a_index in range(last_i, i):
1313
if a_index in new_a:
1314
if a_index in killed_b:
1315
yield 'conflicted-a', self.lines_a[a_index]
1317
yield 'new-a', self.lines_a[a_index]
1319
yield 'killed-b', self.lines_a[a_index]
1320
for b_index in range(last_j, j):
1321
if b_index in new_b:
1322
if b_index in killed_a:
1323
yield 'conflicted-b', self.lines_b[b_index]
1325
yield 'new-b', self.lines_b[b_index]
1327
yield 'killed-a', self.lines_b[b_index]
1328
# handle common lines
1329
for a_index in range(i, i+n):
1330
yield 'unchanged', self.lines_a[a_index]
1334
def _get_matching_blocks(self, left_revision, right_revision):
1335
"""Return a description of which sections of two revisions match.
1337
See SequenceMatcher.get_matching_blocks
1339
cached = self._cached_matching_blocks.get((left_revision,
1341
if cached is not None:
1343
if self._last_lines_revision_id == left_revision:
1344
left_lines = self._last_lines
1345
right_lines = self.get_lines([right_revision])[right_revision]
1347
lines = self.get_lines([left_revision, right_revision])
1348
left_lines = lines[left_revision]
1349
right_lines = lines[right_revision]
1350
self._last_lines = right_lines
1351
self._last_lines_revision_id = right_revision
1352
matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1354
return matcher.get_matching_blocks()
1356
def _unique_lines(self, matching_blocks):
1357
"""Analyse matching_blocks to determine which lines are unique
1359
:return: a tuple of (unique_left, unique_right), where the values are
1360
sets of line numbers of unique lines.
1366
for i, j, n in matching_blocks:
1367
unique_left.extend(range(last_i, i))
1368
unique_right.extend(range(last_j, j))
1371
return unique_left, unique_right
1374
def _subtract_plans(old_plan, new_plan):
1375
"""Remove changes from new_plan that came from old_plan.
1377
It is assumed that the difference between the old_plan and new_plan
1378
is their choice of 'b' text.
1380
All lines from new_plan that differ from old_plan are emitted
1381
verbatim. All lines from new_plan that match old_plan but are
1382
not about the 'b' revision are emitted verbatim.
1384
Lines that match and are about the 'b' revision are the lines we
1385
don't want, so we convert 'killed-b' -> 'unchanged', and 'new-b'
1386
is skipped entirely.
1388
matcher = patiencediff.PatienceSequenceMatcher(None, old_plan,
1391
for i, j, n in matcher.get_matching_blocks():
1392
for jj in range(last_j, j):
1394
for jj in range(j, j+n):
1395
plan_line = new_plan[jj]
1396
if plan_line[0] == 'new-b':
1398
elif plan_line[0] == 'killed-b':
1399
yield 'unchanged', plan_line[1]
1405
class _PlanMerge(_PlanMergeBase):
1406
"""Plan an annotate merge using on-the-fly annotation"""
1408
def __init__(self, a_rev, b_rev, vf, key_prefix):
1409
super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
1410
self.a_key = self._key_prefix + (self.a_rev,)
1411
self.b_key = self._key_prefix + (self.b_rev,)
1412
self.graph = Graph(self.vf)
1413
heads = self.graph.heads((self.a_key, self.b_key))
1415
# one side dominates, so we can just return its values, yay for
1417
# Ideally we would know that before we get this far
1418
self._head_key = heads.pop()
1419
if self._head_key == self.a_key:
1423
mutter('found dominating revision for %s\n%s > %s', self.vf,
1424
self._head_key[-1], other)
1427
self._head_key = None
1430
def _precache_tip_lines(self):
1431
# Turn this into a no-op, because we will do this later
1434
def _find_recursive_lcas(self):
1435
"""Find all the ancestors back to a unique lca"""
1436
cur_ancestors = (self.a_key, self.b_key)
1437
# graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
1438
# rather than a key tuple. We will just map that directly to no common
1442
next_lcas = self.graph.find_lca(*cur_ancestors)
1443
# Map a plain NULL_REVISION to a simple no-ancestors
1444
if next_lcas == set([NULL_REVISION]):
1446
# Order the lca's based on when they were merged into the tip
1447
# While the actual merge portion of weave merge uses a set() of
1448
# active revisions, the order of insertion *does* effect the
1449
# implicit ordering of the texts.
1450
for rev_key in cur_ancestors:
1451
ordered_parents = tuple(self.graph.find_merge_order(rev_key,
1453
parent_map[rev_key] = ordered_parents
1454
if len(next_lcas) == 0:
1456
elif len(next_lcas) == 1:
1457
parent_map[list(next_lcas)[0]] = ()
1459
elif len(next_lcas) > 2:
1460
# More than 2 lca's, fall back to grabbing all nodes between
1461
# this and the unique lca.
1462
mutter('More than 2 LCAs, falling back to all nodes for:'
1463
' %s, %s\n=> %s', self.a_key, self.b_key, cur_ancestors)
1464
cur_lcas = next_lcas
1465
while len(cur_lcas) > 1:
1466
cur_lcas = self.graph.find_lca(*cur_lcas)
1467
if len(cur_lcas) == 0:
1468
# No common base to find, use the full ancestry
1471
unique_lca = list(cur_lcas)[0]
1472
if unique_lca == NULL_REVISION:
1473
# find_lca will return a plain 'NULL_REVISION' rather
1474
# than a key tuple when there is no common ancestor, we
1475
# prefer to just use None, because it doesn't confuse
1476
# _get_interesting_texts()
1478
parent_map.update(self._find_unique_parents(next_lcas,
1481
cur_ancestors = next_lcas
1484
def _find_unique_parents(self, tip_keys, base_key):
1485
"""Find ancestors of tip that aren't ancestors of base.
1487
:param tip_keys: Nodes that are interesting
1488
:param base_key: Cull all ancestors of this node
1489
:return: The parent map for all revisions between tip_keys and
1490
base_key. base_key will be included. References to nodes outside of
1491
the ancestor set will also be removed.
1493
# TODO: this would be simpler if find_unique_ancestors took a list
1494
# instead of a single tip, internally it supports it, but it
1495
# isn't a "backwards compatible" api change.
1496
if base_key is None:
1497
parent_map = dict(self.graph.iter_ancestry(tip_keys))
1498
# We remove NULL_REVISION because it isn't a proper tuple key, and
1499
# thus confuses things like _get_interesting_texts, and our logic
1500
# to add the texts into the memory weave.
1501
if NULL_REVISION in parent_map:
1502
parent_map.pop(NULL_REVISION)
1505
for tip in tip_keys:
1507
self.graph.find_unique_ancestors(tip, [base_key]))
1508
parent_map = self.graph.get_parent_map(interesting)
1509
parent_map[base_key] = ()
1510
culled_parent_map, child_map, tails = self._remove_external_references(
1512
# Remove all the tails but base_key
1513
if base_key is not None:
1514
tails.remove(base_key)
1515
self._prune_tails(culled_parent_map, child_map, tails)
1516
# Now remove all the uninteresting 'linear' regions
1517
simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
1521
def _remove_external_references(parent_map):
1522
"""Remove references that go outside of the parent map.
1524
:param parent_map: Something returned from Graph.get_parent_map(keys)
1525
:return: (filtered_parent_map, child_map, tails)
1526
filtered_parent_map is parent_map without external references
1527
child_map is the {parent_key: [child_keys]} mapping
1528
tails is a list of nodes that do not have any parents in the map
1530
# TODO: The basic effect of this function seems more generic than
1531
# _PlanMerge. But the specific details of building a child_map,
1532
# and computing tails seems very specific to _PlanMerge.
1533
# Still, should this be in Graph land?
1534
filtered_parent_map = {}
1537
for key, parent_keys in parent_map.iteritems():
1538
culled_parent_keys = [p for p in parent_keys if p in parent_map]
1539
if not culled_parent_keys:
1541
for parent_key in culled_parent_keys:
1542
child_map.setdefault(parent_key, []).append(key)
1543
# TODO: Do we want to do this, it adds overhead for every node,
1544
# just to say that the node has no children
1545
child_map.setdefault(key, [])
1546
filtered_parent_map[key] = culled_parent_keys
1547
return filtered_parent_map, child_map, tails
1550
def _prune_tails(parent_map, child_map, tails_to_remove):
1551
"""Remove tails from the parent map.
1553
This will remove the supplied revisions until no more children have 0
1556
:param parent_map: A dict of {child: [parents]}, this dictionary will
1557
be modified in place.
1558
:param tails_to_remove: A list of tips that should be removed,
1559
this list will be consumed
1560
:param child_map: The reverse dict of parent_map ({parent: [children]})
1561
this dict will be modified
1562
:return: None, parent_map will be modified in place.
1564
while tails_to_remove:
1565
next = tails_to_remove.pop()
1566
parent_map.pop(next)
1567
children = child_map.pop(next)
1568
for child in children:
1569
child_parents = parent_map[child]
1570
child_parents.remove(next)
1571
if len(child_parents) == 0:
1572
tails_to_remove.append(child)
1574
def _get_interesting_texts(self, parent_map):
1575
"""Return a dict of texts we are interested in.
1577
Note that the input is in key tuples, but the output is in plain
1580
:param parent_map: The output from _find_recursive_lcas
1581
:return: A dict of {'revision_id':lines} as returned by
1582
_PlanMergeBase.get_lines()
1584
all_revision_keys = set(parent_map)
1585
all_revision_keys.add(self.a_key)
1586
all_revision_keys.add(self.b_key)
1588
# Everything else is in 'keys' but get_lines is in 'revision_ids'
1589
all_texts = self.get_lines([k[-1] for k in all_revision_keys])
1592
def _build_weave(self):
1593
from bzrlib import weave
1594
self._weave = weave.Weave(weave_name='in_memory_weave',
1595
allow_reserved=True)
1596
parent_map = self._find_recursive_lcas()
1598
all_texts = self._get_interesting_texts(parent_map)
1600
# Note: Unfortunately, the order given by topo_sort will effect the
1601
# ordering resolution in the output. Specifically, if you add A then B,
1602
# then in the output text A lines will show up before B lines. And, of
1603
# course, topo_sort doesn't guarantee any real ordering.
1604
# So we use merge_sort, and add a fake node on the tip.
1605
# This ensures that left-hand parents will always be inserted into the
1606
# weave before right-hand parents.
1607
tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
1608
parent_map[tip_key] = (self.a_key, self.b_key)
1610
for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
1614
# for key in tsort.topo_sort(parent_map):
1615
parent_keys = parent_map[key]
1616
revision_id = key[-1]
1617
parent_ids = [k[-1] for k in parent_keys]
1618
self._weave.add_lines(revision_id, parent_ids,
1619
all_texts[revision_id])
1621
def plan_merge(self):
1622
"""Generate a 'plan' for merging the two revisions.
1624
This involves comparing their texts and determining the cause of
1625
differences. If text A has a line and text B does not, then either the
1626
line was added to text A, or it was deleted from B. Once the causes
1627
are combined, they are written out in the format described in
1628
VersionedFile.plan_merge
1630
if self._head_key is not None: # There was a single head
1631
if self._head_key == self.a_key:
1634
if self._head_key != self.b_key:
1635
raise AssertionError('There was an invalid head: %s != %s'
1636
% (self.b_key, self._head_key))
1638
head_rev = self._head_key[-1]
1639
lines = self.get_lines([head_rev])[head_rev]
1640
return ((plan, line) for line in lines)
1641
return self._weave.plan_merge(self.a_rev, self.b_rev)
1644
class _PlanLCAMerge(_PlanMergeBase):
1646
This merge algorithm differs from _PlanMerge in that:
1647
1. comparisons are done against LCAs only
1648
2. cases where a contested line is new versus one LCA but old versus
1649
another are marked as conflicts, by emitting the line as conflicted-a
1652
This is faster, and hopefully produces more useful output.
1655
def __init__(self, a_rev, b_rev, vf, key_prefix, graph):
1656
_PlanMergeBase.__init__(self, a_rev, b_rev, vf, key_prefix)
1657
lcas = graph.find_lca(key_prefix + (a_rev,), key_prefix + (b_rev,))
1660
if lca == NULL_REVISION:
1663
self.lcas.add(lca[-1])
1664
for lca in self.lcas:
1665
if _mod_revision.is_null(lca):
1668
lca_lines = self.get_lines([lca])[lca]
1669
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
1671
blocks = list(matcher.get_matching_blocks())
1672
self._cached_matching_blocks[(a_rev, lca)] = blocks
1673
matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_b,
1675
blocks = list(matcher.get_matching_blocks())
1676
self._cached_matching_blocks[(b_rev, lca)] = blocks
1678
def _determine_status(self, revision_id, unique_line_numbers):
1679
"""Determines the status unique lines versus all lcas.
1681
Basically, determines why the line is unique to this revision.
1683
A line may be determined new, killed, or both.
1685
If a line is determined new, that means it was not present in at least
1686
one LCA, and is not present in the other merge revision.
1688
If a line is determined killed, that means the line was present in
1691
If a line is killed and new, this indicates that the two merge
1692
revisions contain differing conflict resolutions.
1693
:param revision_id: The id of the revision in which the lines are
1695
:param unique_line_numbers: The line numbers of unique lines.
1696
:return a tuple of (new_this, killed_other):
1700
unique_line_numbers = set(unique_line_numbers)
1701
for lca in self.lcas:
1702
blocks = self._get_matching_blocks(revision_id, lca)
1703
unique_vs_lca, _ignored = self._unique_lines(blocks)
1704
new.update(unique_line_numbers.intersection(unique_vs_lca))
1705
killed.update(unique_line_numbers.difference(unique_vs_lca))
added
removed
bzrlib/merge.py
