« back to all changes in this revision
Viewing changes to bzrlib/merge.py
- browse files at revision 886
- compare with another revision
- download diff
- download tarball
- view history from revision 886
- Committer: Martin Pool
- Date: 2005-07-11 03:42:53 UTC
- Revision ID: mbp@sourcefrog.net-20050711034253-412281abeb9f56ad
doc
- files added:
- bzrlib/meta_store.py
- plugins/changeset
- files removed:
- HACKING
- bzrlib/store
- bzrlib/transport
- bzrlib/util
- contrib/emacs
- files renamed:
- contrib/newinventory.py => bzrlib/newinventory.py
- bzrlib/store/__init__.py => bzrlib/store.py
- bzrlib/util/effbot/ => effbot/
- bzrlib/util/elementtree/ => elementtree/
- bzrlib/plugins/ => plugins/
- bzrlib/selftest/test_weave.py => tools/testweave.py
- bzrlib/util/urlgrabber/ => urlgrabber/
- files modified:
- .bzrignore
added
removed
bzrlib/merge.py
1
# Copyright (C) 2005 Canonical Ltd
2
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.
7
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.
12
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
16
17
18
import os
1
from merge_core import merge_flex
2
from changeset import generate_changeset, ExceptionConflictHandler
3
from changeset import Inventory
4
from bzrlib import find_branch
5
import bzrlib.osutils
6
from bzrlib.errors import BzrCommandError
7
from bzrlib.diff import compare_trees
8
from trace import mutter, warning
9
import os.path
19
10
import tempfile
20
11
import shutil
21
12
import errno
22
13
23
import bzrlib.osutils
24
import bzrlib.revision
25
from bzrlib.merge_core import merge_flex, ApplyMerge3, BackupBeforeChange
26
from bzrlib.changeset import generate_changeset, ExceptionConflictHandler
27
from bzrlib.changeset import Inventory, Diff3Merge, ReplaceContents
28
from bzrlib.branch import Branch
29
from bzrlib.errors import BzrCommandError, UnrelatedBranches, NoCommonAncestor
30
from bzrlib.errors import NoCommits
31
from bzrlib.delta import compare_trees
32
from bzrlib.trace import mutter, warning
33
from bzrlib.fetch import greedy_fetch, fetch
34
from bzrlib.revision import is_ancestor
35
from bzrlib.osutils import rename
36
from bzrlib.revision import common_ancestor, MultipleRevisionSources
37
from bzrlib.errors import NoSuchRevision
38
39
# TODO: build_working_dir can be built on something simpler than merge()
40
41
# FIXME: merge() parameters seem oriented towards the command line
42
43
# comments from abentley on irc: merge happens in two stages, each
44
# of which generates a changeset object
45
46
# stage 1: generate OLD->OTHER,
47
# stage 2: use MINE and OLD->OTHER to generate MINE -> RESULT
14
class UnrelatedBranches(BzrCommandError):
15
def __init__(self):
16
msg = "Branches have no common ancestor, and no base revision"\
17
" specified."
18
BzrCommandError.__init__(self, msg)
19
48
20
49
21
class MergeConflictHandler(ExceptionConflictHandler):
50
"""Handle conflicts encountered while merging.
51
52
This subclasses ExceptionConflictHandler, so that any types of
53
conflict that are not explicitly handled cause an exception and
54
terminate the merge.
55
"""
56
def __init__(self, this_tree, base_tree, other_tree, ignore_zero=False):
57
ExceptionConflictHandler.__init__(self)
22
"""Handle conflicts encountered while merging"""
23
def __init__(self, dir, ignore_zero=False):
24
ExceptionConflictHandler.__init__(self, dir)
58
25
self.conflicts = 0
59
26
self.ignore_zero = ignore_zero
60
self.this_tree = this_tree
61
self.base_tree = base_tree
62
self.other_tree = other_tree
63
27
64
28
def copy(self, source, dest):
65
29
"""Copy the text and mode of a file
72
36
d_file.write(line)
73
37
os.chmod(dest, 0777 & os.stat(source).st_mode)
74
38
75
def dump(self, lines, dest):
76
"""Copy the text and mode of a file
77
:param source: The path of the file to copy
78
:param dest: The distination file to create
79
"""
80
d_file = file(dest, "wb")
81
for line in lines:
82
d_file.write(line)
83
84
39
def add_suffix(self, name, suffix, last_new_name=None):
85
40
"""Rename a file to append a suffix. If the new name exists, the
86
41
suffix is added repeatedly until a non-existant name is found
93
48
last_new_name = name
94
49
new_name = last_new_name+suffix
95
50
try:
96
rename(name, new_name)
51
os.rename(name, new_name)
97
52
return new_name
98
53
except OSError, e:
99
54
if e.errno != errno.EEXIST and e.errno != errno.ENOTEMPTY:
105
60
self.conflicts += 1
106
61
107
62
108
def merge_conflict(self, new_file, this_path, base_lines, other_lines):
63
def merge_conflict(self, new_file, this_path, base_path, other_path):
109
64
"""
110
65
Handle diff3 conflicts by producing a .THIS, .BASE and .OTHER. The
111
66
main file will be a version with diff3 conflicts.
115
70
:param other_path: Path to the file text for the OTHER tree
116
71
"""
117
72
self.add_suffix(this_path, ".THIS")
118
self.dump(base_lines, this_path+".BASE")
119
self.dump(other_lines, this_path+".OTHER")
120
rename(new_file, this_path)
73
self.copy(base_path, this_path+".BASE")
74
self.copy(other_path, this_path+".OTHER")
75
os.rename(new_file, this_path)
121
76
self.conflict("Diff3 conflict encountered in %s" % this_path)
122
77
123
def new_contents_conflict(self, filename, other_contents):
124
"""Conflicting contents for newly added file."""
125
self.copy(other_contents, filename + ".OTHER")
126
self.conflict("Conflict in newly added file %s" % filename)
127
128
129
78
def target_exists(self, entry, target, old_path):
130
79
"""Handle the case when the target file or dir exists"""
131
80
moved_path = self.add_suffix(target, ".moved")
137
86
% filename)
138
87
return "skip"
139
88
140
def rem_contents_conflict(self, filename, this_contents, base_contents):
141
base_contents(filename+".BASE", self, False)
142
this_contents(filename+".THIS", self, False)
143
self.conflict("Other branch deleted locally modified file %s" %
144
filename)
145
return ReplaceContents(this_contents, None)
146
147
def abs_this_path(self, file_id):
148
"""Return the absolute path for a file_id in the this tree."""
149
relpath = self.this_tree.id2path(file_id)
150
return self.this_tree.tree.abspath(relpath)
151
152
def add_missing_parents(self, file_id, tree):
153
"""If some of the parents for file_id are missing, add them."""
154
entry = tree.tree.inventory[file_id]
155
if entry.parent_id not in self.this_tree:
156
return self.create_all_missing(entry.parent_id, tree)
157
else:
158
return self.abs_this_path(entry.parent_id)
159
160
def create_all_missing(self, file_id, tree):
161
"""Add contents for a file_id and all its parents to a tree."""
162
entry = tree.tree.inventory[file_id]
163
if entry.parent_id is not None and entry.parent_id not in self.this_tree:
164
abspath = self.create_all_missing(entry.parent_id, tree)
165
else:
166
abspath = self.abs_this_path(entry.parent_id)
167
entry_path = os.path.join(abspath, entry.name)
168
if not os.path.isdir(entry_path):
169
self.create(file_id, entry_path, tree)
170
return entry_path
171
172
def create(self, file_id, path, tree, reverse=False):
173
"""Uses tree data to create a filesystem object for the file_id"""
174
from merge_core import get_id_contents
175
get_id_contents(file_id, tree)(path, self, reverse)
176
177
def missing_for_merge(self, file_id, other_path):
178
"""The file_id doesn't exist in THIS, but does in OTHER and BASE"""
179
self.conflict("Other branch modified locally deleted file %s" %
180
other_path)
181
parent_dir = self.add_missing_parents(file_id, self.other_tree)
182
stem = os.path.join(parent_dir, os.path.basename(other_path))
183
self.create(file_id, stem+".OTHER", self.other_tree)
184
self.create(file_id, stem+".BASE", self.base_tree)
185
186
89
def finalize(self):
187
90
if not self.ignore_zero:
188
91
print "%d conflicts encountered.\n" % self.conflicts
189
92
190
def get_tree(treespec, temp_root, label, local_branch=None):
93
class SourceFile(object):
94
def __init__(self, path, id, present=None, isdir=None):
95
self.path = path
96
self.id = id
97
self.present = present
98
self.isdir = isdir
99
self.interesting = True
100
101
def __repr__(self):
102
return "SourceFile(%s, %s)" % (self.path, self.id)
103
104
def get_tree(treespec, temp_root, label):
191
105
location, revno = treespec
192
branch = Branch.open_containing(location)
106
branch = find_branch(location)
193
107
if revno is None:
194
revision = None
108
base_tree = branch.working_tree()
195
109
elif revno == -1:
196
revision = branch.last_revision()
197
else:
198
revision = branch.get_rev_id(revno)
199
return branch, get_revid_tree(branch, revision, temp_root, label,
200
local_branch)
201
202
def get_revid_tree(branch, revision, temp_root, label, local_branch):
203
if revision is None:
204
base_tree = branch.working_tree()
205
else:
206
if local_branch is not None:
207
greedy_fetch(local_branch, branch, revision)
208
base_tree = local_branch.revision_tree(revision)
209
else:
210
base_tree = branch.revision_tree(revision)
110
base_tree = branch.basis_tree()
111
else:
112
base_tree = branch.revision_tree(branch.lookup_revision(revno))
211
113
temp_path = os.path.join(temp_root, label)
212
114
os.mkdir(temp_path)
213
return MergeTree(base_tree, temp_path)
214
115
return branch, MergeTree(base_tree, temp_path)
116
117
118
def abspath(tree, file_id):
119
path = tree.inventory.id2path(file_id)
120
if path == "":
121
return "./."
122
return "./" + path
215
123
216
124
def file_exists(tree, file_id):
217
125
return tree.has_filename(tree.id2path(file_id))
218
126
127
def inventory_map(tree):
128
inventory = {}
129
for file_id in tree.inventory:
130
path = abspath(tree, file_id)
131
inventory[path] = SourceFile(path, file_id)
132
return inventory
133
219
134
220
135
class MergeTree(object):
221
136
def __init__(self, tree, tempdir):
224
139
self.root = tree.basedir
225
140
else:
226
141
self.root = None
142
self.inventory = inventory_map(tree)
227
143
self.tree = tree
228
144
self.tempdir = tempdir
229
145
os.mkdir(os.path.join(self.tempdir, "texts"))
230
os.mkdir(os.path.join(self.tempdir, "symlinks"))
231
146
self.cached = {}
232
147
233
def __iter__(self):
234
return self.tree.__iter__()
235
236
def __contains__(self, file_id):
237
return file_id in self.tree
238
239
def get_file(self, file_id):
240
return self.tree.get_file(file_id)
241
242
def get_file_sha1(self, id):
243
return self.tree.get_file_sha1(id)
244
245
def is_executable(self, id):
246
return self.tree.is_executable(id)
247
248
def id2path(self, file_id):
249
return self.tree.id2path(file_id)
250
251
def has_id(self, file_id):
252
return self.tree.has_id(file_id)
253
254
def has_or_had_id(self, file_id):
255
if file_id == self.tree.inventory.root.file_id:
256
return True
257
return self.tree.inventory.has_id(file_id)
258
259
def has_or_had_id(self, file_id):
260
if file_id == self.tree.inventory.root.file_id:
261
return True
262
return self.tree.inventory.has_id(file_id)
263
264
148
def readonly_path(self, id):
265
149
if id not in self.tree:
266
150
return None
267
151
if self.root is not None:
268
152
return self.tree.abspath(self.tree.id2path(id))
269
153
else:
270
kind = self.tree.inventory[id].kind
271
if kind in ("directory", "root_directory"):
154
if self.tree.inventory[id].kind in ("directory", "root_directory"):
272
155
return self.tempdir
273
156
if not self.cached.has_key(id):
274
if kind == "file":
275
path = os.path.join(self.tempdir, "texts", id)
276
outfile = file(path, "wb")
277
outfile.write(self.tree.get_file(id).read())
278
assert(bzrlib.osutils.lexists(path))
279
if self.tree.is_executable(id):
280
os.chmod(path, 0755)
281
else:
282
assert kind == "symlink"
283
path = os.path.join(self.tempdir, "symlinks", id)
284
target = self.tree.get_symlink_target(id)
285
os.symlink(target, path)
157
path = os.path.join(self.tempdir, "texts", id)
158
outfile = file(path, "wb")
159
outfile.write(self.tree.get_file(id).read())
160
assert(os.path.exists(path))
286
161
self.cached[id] = path
287
162
return self.cached[id]
288
163
289
164
290
def build_working_dir(to_dir):
291
"""Build a working directory in an empty directory.
292
293
to_dir is a directory containing branch metadata but no working files,
294
typically constructed by cloning an existing branch.
295
296
This is split out as a special idiomatic case of merge. It could
297
eventually be done by just building the tree directly calling into
298
lower-level code (e.g. constructing a changeset).
299
"""
300
merge((to_dir, -1), (to_dir, 0), this_dir=to_dir,
301
check_clean=False, ignore_zero=True)
302
303
165
304
166
def merge(other_revision, base_revision,
305
167
check_clean=True, ignore_zero=False,
306
this_dir=None, backup_files=False, merge_type=ApplyMerge3,
307
file_list=None):
168
this_dir=None):
308
169
"""Merge changes into a tree.
309
170
310
171
base_revision
311
tuple(path, revision) Base for three-way merge.
172
Base for three-way merge.
312
173
other_revision
313
tuple(path, revision) Other revision for three-way merge.
174
Other revision for three-way merge.
314
175
this_dir
315
176
Directory to merge changes into; '.' by default.
316
177
check_clean
317
178
If true, this_dir must have no uncommitted changes before the
318
179
merge begins.
319
ignore_zero - If true, suppress the "zero conflicts" message when
320
there are no conflicts; should be set when doing something we expect
321
to complete perfectly.
322
323
All available ancestors of other_revision and base_revision are
324
automatically pulled into the branch.
325
180
"""
326
181
tempdir = tempfile.mkdtemp(prefix="bzr-")
327
182
try:
328
183
if this_dir is None:
329
184
this_dir = '.'
330
this_branch = Branch.open_containing(this_dir)
331
this_rev_id = this_branch.last_revision()
332
if this_rev_id is None:
333
raise BzrCommandError("This branch has no commits")
185
this_branch = find_branch(this_dir)
334
186
if check_clean:
335
187
changes = compare_trees(this_branch.working_tree(),
336
188
this_branch.basis_tree(), False)
337
189
if changes.has_changed():
338
190
raise BzrCommandError("Working tree has uncommitted changes.")
339
other_branch, other_tree = get_tree(other_revision, tempdir, "other",
340
this_branch)
341
if other_revision[1] == -1:
342
other_rev_id = other_branch.last_revision()
343
if other_rev_id is None:
344
raise NoCommits(other_branch)
345
other_basis = other_rev_id
346
elif other_revision[1] is not None:
347
other_rev_id = other_branch.get_rev_id(other_revision[1])
348
other_basis = other_rev_id
349
else:
350
other_rev_id = None
351
other_basis = other_branch.last_revision()
352
if other_basis is None:
353
raise NoCommits(other_branch)
191
other_branch, other_tree = get_tree(other_revision, tempdir, "other")
354
192
if base_revision == [None, None]:
355
try:
356
base_rev_id = common_ancestor(this_rev_id, other_basis,
357
this_branch)
358
except NoCommonAncestor:
193
if other_revision[1] == -1:
194
o_revno = None
195
else:
196
o_revno = other_revision[1]
197
base_revno = this_branch.common_ancestor(other_branch,
198
other_revno=o_revno)[0]
199
if base_revno is None:
359
200
raise UnrelatedBranches()
360
base_tree = get_revid_tree(this_branch, base_rev_id, tempdir,
361
"base", None)
362
base_is_ancestor = True
363
else:
364
base_branch, base_tree = get_tree(base_revision, tempdir, "base")
365
if base_revision[1] == -1:
366
base_rev_id = base_branch.last_revision()
367
elif base_revision[1] is None:
368
base_rev_id = None
369
else:
370
base_rev_id = base_branch.get_rev_id(base_revision[1])
371
fetch(from_branch=base_branch, to_branch=this_branch)
372
base_is_ancestor = is_ancestor(this_rev_id, base_rev_id,
373
this_branch)
374
if file_list is None:
375
interesting_ids = None
376
else:
377
interesting_ids = set()
378
this_tree = this_branch.working_tree()
379
for fname in file_list:
380
path = this_branch.relpath(fname)
381
found_id = False
382
for tree in (this_tree, base_tree.tree, other_tree.tree):
383
file_id = tree.inventory.path2id(path)
384
if file_id is not None:
385
interesting_ids.add(file_id)
386
found_id = True
387
if not found_id:
388
raise BzrCommandError("%s is not a source file in any"
389
" tree." % fname)
201
base_revision = ['.', base_revno]
202
base_branch, base_tree = get_tree(base_revision, tempdir, "base")
390
203
merge_inner(this_branch, other_tree, base_tree, tempdir,
391
ignore_zero=ignore_zero, backup_files=backup_files,
392
merge_type=merge_type, interesting_ids=interesting_ids)
393
if base_is_ancestor and other_rev_id is not None\
394
and other_rev_id not in this_branch.revision_history():
395
this_branch.add_pending_merge(other_rev_id)
204
ignore_zero=ignore_zero)
396
205
finally:
397
206
shutil.rmtree(tempdir)
398
207
399
208
400
def set_interesting(inventory_a, inventory_b, interesting_ids):
401
"""Mark files whose ids are in interesting_ids as interesting
402
"""
403
for inventory in (inventory_a, inventory_b):
404
for path, source_file in inventory.iteritems():
405
source_file.interesting = source_file.id in interesting_ids
406
407
408
def generate_cset_optimized(tree_a, tree_b, interesting_ids=None):
409
"""Generate a changeset. If interesting_ids is supplied, only changes
410
to those files will be shown. Metadata changes are stripped.
209
def generate_cset_optimized(tree_a, tree_b, inventory_a, inventory_b):
210
"""Generate a changeset, using the text_id to mark really-changed files.
211
This permits blazing comparisons when text_ids are present. It also
212
disables metadata comparison for files with identical texts.
411
213
"""
412
cset = generate_changeset(tree_a, tree_b, interesting_ids)
214
for file_id in tree_a.tree.inventory:
215
if file_id not in tree_b.tree.inventory:
216
continue
217
entry_a = tree_a.tree.inventory[file_id]
218
entry_b = tree_b.tree.inventory[file_id]
219
if (entry_a.kind, entry_b.kind) != ("file", "file"):
220
continue
221
if None in (entry_a.text_id, entry_b.text_id):
222
continue
223
if entry_a.text_id != entry_b.text_id:
224
continue
225
inventory_a[abspath(tree_a.tree, file_id)].interesting = False
226
inventory_b[abspath(tree_b.tree, file_id)].interesting = False
227
cset = generate_changeset(tree_a, tree_b, inventory_a, inventory_b)
413
228
for entry in cset.entries.itervalues():
414
229
entry.metadata_change = None
415
230
return cset
416
231
417
232
418
233
def merge_inner(this_branch, other_tree, base_tree, tempdir,
419
ignore_zero=False, merge_type=ApplyMerge3, backup_files=False,
420
interesting_ids=None):
421
422
def merge_factory(file_id, base, other):
423
contents_change = merge_type(file_id, base, other)
424
if backup_files:
425
contents_change = BackupBeforeChange(contents_change)
426
return contents_change
427
234
ignore_zero=False):
428
235
this_tree = get_tree((this_branch.base, None), tempdir, "this")[1]
429
236
430
237
def get_inventory(tree):
431
return tree.tree.inventory
238
return tree.inventory
432
239
433
240
inv_changes = merge_flex(this_tree, base_tree, other_tree,
434
241
generate_cset_optimized, get_inventory,
435
MergeConflictHandler(this_tree, base_tree,
436
other_tree, ignore_zero=ignore_zero),
437
merge_factory=merge_factory,
438
interesting_ids=interesting_ids)
242
MergeConflictHandler(base_tree.root,
243
ignore_zero=ignore_zero))
439
244
440
245
adjust_ids = []
441
246
for id, path in inv_changes.iteritems():
443
248
if path == '.':
444
249
path = ''
445
250
else:
446
assert path.startswith('.' + os.sep), "path is %s" % path
251
assert path.startswith('./')
447
252
path = path[2:]
448
253
adjust_ids.append((path, id))
449
if len(adjust_ids) > 0:
450
this_branch.set_inventory(regen_inventory(this_branch, this_tree.root,
451
adjust_ids))
254
this_branch.set_inventory(regen_inventory(this_branch, this_tree.root, adjust_ids))
452
255
453
256
454
257
def regen_inventory(this_branch, root, new_entries):
455
258
old_entries = this_branch.read_working_inventory()
456
259
new_inventory = {}
457
260
by_path = {}
458
new_entries_map = {}
459
for path, file_id in new_entries:
460
if path is None:
461
continue
462
new_entries_map[file_id] = path
463
464
def id2path(file_id):
465
path = new_entries_map.get(file_id)
466
if path is not None:
467
return path
468
entry = old_entries[file_id]
469
if entry.parent_id is None:
470
return entry.name
471
return os.path.join(id2path(entry.parent_id), entry.name)
472
473
261
for file_id in old_entries:
474
262
entry = old_entries[file_id]
475
path = id2path(file_id)
263
path = old_entries.id2path(file_id)
476
264
new_inventory[file_id] = (path, file_id, entry.parent_id, entry.kind)
477
265
by_path[path] = file_id
478
266
506
294
assert len(new_inventory_list) == len(old_entries) + insertions - deletions
507
295
new_inventory_list.sort()
508
296
return new_inventory_list
509
510
merge_types = { "merge3": (ApplyMerge3, "Native diff3-style merge"),
511
"diff3": (Diff3Merge, "Merge using external diff3")
512
}
513
Loggerhead is a web-based interface for Breezy
Version: 2.0.1