← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: Martin Pool
  • Date: 2005-09-29 12:49:59 UTC
  • mto: (1185.14.2)
  • mto: This revision was merged to the branch mainline in revision 1396.
  • Revision ID: mbp@sourcefrog.net-20050929124959-df3f175844fc90ed
- remove redundant import

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge.py
1
 
from merge_core import merge_flex
2
 
from changeset import generate_changeset, ExceptionConflictHandler
3
 
from changeset import Inventory
4
 
from bzrlib import Branch
5
 
import bzrlib.osutils
6
 
from trace import mutter
7
 
import os.path
 
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
8
19
import tempfile
9
20
import shutil
10
21
import errno
11
22
 
 
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
 
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
 
 
40
# comments from abentley on irc: merge happens in two stages, each
 
41
# of which generates a changeset object
 
42
 
 
43
# stage 1: generate OLD->OTHER,
 
44
# stage 2: use MINE and OLD->OTHER to generate MINE -> RESULT
 
45
 
12
46
class MergeConflictHandler(ExceptionConflictHandler):
13
 
    """Handle conflicts encountered while merging"""
 
47
    """Handle conflicts encountered while merging.
 
48
 
 
49
    This subclasses ExceptionConflictHandler, so that any types of
 
50
    conflict that are not explicitly handled cause an exception and
 
51
    terminate the merge.
 
52
    """
 
53
    def __init__(self, ignore_zero=False):
 
54
        ExceptionConflictHandler.__init__(self)
 
55
        self.conflicts = 0
 
56
        self.ignore_zero = ignore_zero
 
57
 
14
58
    def copy(self, source, dest):
15
59
        """Copy the text and mode of a file
16
60
        :param source: The path of the file to copy
22
66
            d_file.write(line)
23
67
        os.chmod(dest, 0777 & os.stat(source).st_mode)
24
68
 
 
69
    def dump(self, lines, dest):
 
70
        """Copy the text and mode of a file
 
71
        :param source: The path of the file to copy
 
72
        :param dest: The distination file to create
 
73
        """
 
74
        d_file = file(dest, "wb")
 
75
        for line in lines:
 
76
            d_file.write(line)
 
77
 
25
78
    def add_suffix(self, name, suffix, last_new_name=None):
26
79
        """Rename a file to append a suffix.  If the new name exists, the
27
80
        suffix is added repeatedly until a non-existant name is found
34
87
            last_new_name = name
35
88
        new_name = last_new_name+suffix
36
89
        try:
37
 
            os.rename(name, new_name)
 
90
            rename(name, new_name)
 
91
            return new_name
38
92
        except OSError, e:
39
93
            if e.errno != errno.EEXIST and e.errno != errno.ENOTEMPTY:
40
94
                raise
41
 
            self.add_suffix(name, suffix, last_new_name=new_name)
42
 
 
43
 
    def merge_conflict(self, new_file, this_path, base_path, other_path):
 
95
            return self.add_suffix(name, suffix, last_new_name=new_name)
 
96
 
 
97
    def conflict(self, text):
 
98
        warning(text)
 
99
        self.conflicts += 1
 
100
        
 
101
 
 
102
    def merge_conflict(self, new_file, this_path, base_lines, other_lines):
44
103
        """
45
104
        Handle diff3 conflicts by producing a .THIS, .BASE and .OTHER.  The
46
105
        main file will be a version with diff3 conflicts.
50
109
        :param other_path: Path to the file text for the OTHER tree
51
110
        """
52
111
        self.add_suffix(this_path, ".THIS")
53
 
        self.copy(base_path, this_path+".BASE")
54
 
        self.copy(other_path, this_path+".OTHER")
55
 
        os.rename(new_file, this_path)
 
112
        self.dump(base_lines, this_path+".BASE")
 
113
        self.dump(other_lines, this_path+".OTHER")
 
114
        rename(new_file, this_path)
 
115
        self.conflict("Diff3 conflict encountered in %s" % this_path)
 
116
 
 
117
    def new_contents_conflict(self, filename, other_contents):
 
118
        """Conflicting contents for newly added file."""
 
119
        self.copy(other_contents, filename + ".OTHER")
 
120
        self.conflict("Conflict in newly added file %s" % filename)
 
121
    
56
122
 
57
123
    def target_exists(self, entry, target, old_path):
58
124
        """Handle the case when the target file or dir exists"""
59
 
        self.add_suffix(target, ".moved")
 
125
        moved_path = self.add_suffix(target, ".moved")
 
126
        self.conflict("Moved existing %s to %s" % (target, moved_path))
 
127
 
 
128
    def rmdir_non_empty(self, filename):
 
129
        """Handle the case where the dir to be removed still has contents"""
 
130
        self.conflict("Directory %s not removed because it is not empty"\
 
131
            % filename)
 
132
        return "skip"
 
133
 
 
134
    def finalize(self):
 
135
        if not self.ignore_zero:
 
136
            print "%d conflicts encountered.\n" % self.conflicts
60
137
            
61
 
class SourceFile(object):
62
 
    def __init__(self, path, id, present=None, isdir=None):
63
 
        self.path = path
64
 
        self.id = id
65
 
        self.present = present
66
 
        self.isdir = isdir
67
 
        self.interesting = True
68
 
 
69
 
    def __repr__(self):
70
 
        return "SourceFile(%s, %s)" % (self.path, self.id)
71
 
 
72
 
def get_tree(treespec, temp_root, label):
73
 
    dir, revno = treespec
74
 
    branch = Branch(dir)
 
138
def get_tree(treespec, temp_root, label, local_branch=None):
 
139
    location, revno = treespec
 
140
    branch = Branch.open_containing(location)
75
141
    if revno is None:
 
142
        revision = None
 
143
    elif revno == -1:
 
144
        revision = branch.last_revision()
 
145
    else:
 
146
        revision = branch.get_rev_id(revno)
 
147
    return branch, get_revid_tree(branch, revision, temp_root, label,
 
148
                                  local_branch)
 
149
 
 
150
def get_revid_tree(branch, revision, temp_root, label, local_branch):
 
151
    if revision is None:
76
152
        base_tree = branch.working_tree()
77
 
    elif revno == -1:
78
 
        base_tree = branch.basis_tree()
79
153
    else:
80
 
        base_tree = branch.revision_tree(branch.lookup_revision(revno))
 
154
        if local_branch is not None:
 
155
            greedy_fetch(local_branch, branch, revision)
 
156
            base_tree = local_branch.revision_tree(revision)
 
157
        else:
 
158
            base_tree = branch.revision_tree(revision)
81
159
    temp_path = os.path.join(temp_root, label)
82
160
    os.mkdir(temp_path)
83
161
    return MergeTree(base_tree, temp_path)
84
162
 
85
163
 
86
 
def abspath(tree, file_id):
87
 
    path = tree.inventory.id2path(file_id)
88
 
    if path == "":
89
 
        return "./."
90
 
    return "./" + path
91
 
 
92
164
def file_exists(tree, file_id):
93
165
    return tree.has_filename(tree.id2path(file_id))
94
166
    
95
 
def inventory_map(tree):
96
 
    inventory = {}
97
 
    for file_id in tree.inventory:
98
 
        if not file_exists(tree, file_id):
99
 
            continue
100
 
        path = abspath(tree, file_id)
101
 
        inventory[path] = SourceFile(path, file_id)
102
 
    return inventory
103
 
 
104
167
 
105
168
class MergeTree(object):
106
169
    def __init__(self, tree, tempdir):
109
172
            self.root = tree.basedir
110
173
        else:
111
174
            self.root = None
112
 
        self.inventory = inventory_map(tree)
113
175
        self.tree = tree
114
176
        self.tempdir = tempdir
115
177
        os.mkdir(os.path.join(self.tempdir, "texts"))
116
178
        self.cached = {}
117
179
 
 
180
    def __iter__(self):
 
181
        return self.tree.__iter__()
 
182
 
 
183
    def __contains__(self, file_id):
 
184
        return file_id in self.tree
 
185
 
 
186
    def get_file(self, file_id):
 
187
        return self.tree.get_file(file_id)
 
188
 
 
189
    def get_file_sha1(self, id):
 
190
        return self.tree.get_file_sha1(id)
 
191
 
 
192
    def id2path(self, file_id):
 
193
        return self.tree.id2path(file_id)
 
194
 
 
195
    def has_id(self, file_id):
 
196
        return self.tree.has_id(file_id)
 
197
 
 
198
    def has_or_had_id(self, file_id):
 
199
        if file_id == self.tree.inventory.root.file_id:
 
200
            return True
 
201
        return self.tree.inventory.has_id(file_id)
 
202
 
 
203
    def has_or_had_id(self, file_id):
 
204
        if file_id == self.tree.inventory.root.file_id:
 
205
            return True
 
206
        return self.tree.inventory.has_id(file_id)
 
207
 
118
208
    def readonly_path(self, id):
 
209
        if id not in self.tree:
 
210
            return None
119
211
        if self.root is not None:
120
212
            return self.tree.abspath(self.tree.id2path(id))
121
213
        else:
129
221
                self.cached[id] = path
130
222
            return self.cached[id]
131
223
 
132
 
def merge(other_revision, base_revision):
 
224
 
 
225
 
 
226
def merge(other_revision, base_revision,
 
227
          check_clean=True, ignore_zero=False,
 
228
          this_dir=None, backup_files=False, merge_type=ApplyMerge3,
 
229
          file_list=None):
 
230
    """Merge changes into a tree.
 
231
 
 
232
    base_revision
 
233
        tuple(path, revision) Base for three-way merge.
 
234
    other_revision
 
235
        tuple(path, revision) Other revision for three-way merge.
 
236
    this_dir
 
237
        Directory to merge changes into; '.' by default.
 
238
    check_clean
 
239
        If true, this_dir must have no uncommitted changes before the
 
240
        merge begins.
 
241
 
 
242
    All available ancestors of other_revision and base_revision are
 
243
    automatically pulled into the branch.
 
244
    """
133
245
    tempdir = tempfile.mkdtemp(prefix="bzr-")
134
246
    try:
135
 
        this_branch = Branch('.') 
136
 
        other_tree = get_tree(other_revision, tempdir, "other")
137
 
        base_tree = get_tree(base_revision, tempdir, "base")
138
 
        merge_inner(this_branch, other_tree, base_tree, tempdir)
 
247
        if this_dir is None:
 
248
            this_dir = '.'
 
249
        this_branch = Branch.open_containing(this_dir)
 
250
        this_rev_id = this_branch.last_revision()
 
251
        if this_rev_id is None:
 
252
            raise BzrCommandError("This branch has no commits")
 
253
        if check_clean:
 
254
            changes = compare_trees(this_branch.working_tree(), 
 
255
                                    this_branch.basis_tree(), False)
 
256
            if changes.has_changed():
 
257
                raise BzrCommandError("Working tree has uncommitted changes.")
 
258
        other_branch, other_tree = get_tree(other_revision, tempdir, "other",
 
259
                                            this_branch)
 
260
        if other_revision[1] == -1:
 
261
            other_rev_id = other_branch.last_revision()
 
262
            if other_rev_id is None:
 
263
                raise NoCommits(other_branch)
 
264
            other_basis = other_rev_id
 
265
        elif other_revision[1] is not None:
 
266
            other_rev_id = other_branch.get_rev_id(other_revision[1])
 
267
            other_basis = other_rev_id
 
268
        else:
 
269
            other_rev_id = None
 
270
            other_basis = other_branch.last_revision()
 
271
            if other_basis is None:
 
272
                raise NoCommits(other_branch)
 
273
        if base_revision == [None, None]:
 
274
            try:
 
275
                base_rev_id = common_ancestor(this_rev_id, other_basis, 
 
276
                                              this_branch)
 
277
            except NoCommonAncestor:
 
278
                raise UnrelatedBranches()
 
279
            base_tree = get_revid_tree(this_branch, base_rev_id, tempdir, 
 
280
                                       "base", None)
 
281
            base_is_ancestor = True
 
282
        else:
 
283
            base_branch, base_tree = get_tree(base_revision, tempdir, "base")
 
284
            if base_revision[1] == -1:
 
285
                base_rev_id = base_branch.last_revision()
 
286
            elif base_revision[1] is None:
 
287
                base_rev_id = None
 
288
            else:
 
289
                base_rev_id = base_branch.get_rev_id(base_revision[1])
 
290
            fetch(from_branch=base_branch, to_branch=this_branch)
 
291
            base_is_ancestor = is_ancestor(this_rev_id, base_rev_id,
 
292
                                           this_branch)
 
293
        if file_list is None:
 
294
            interesting_ids = None
 
295
        else:
 
296
            interesting_ids = set()
 
297
            this_tree = this_branch.working_tree()
 
298
            for fname in file_list:
 
299
                path = this_branch.relpath(fname)
 
300
                found_id = False
 
301
                for tree in (this_tree, base_tree.tree, other_tree.tree):
 
302
                    file_id = tree.inventory.path2id(path)
 
303
                    if file_id is not None:
 
304
                        interesting_ids.add(file_id)
 
305
                        found_id = True
 
306
                if not found_id:
 
307
                    raise BzrCommandError("%s is not a source file in any"
 
308
                                          " tree." % fname)
 
309
        merge_inner(this_branch, other_tree, base_tree, tempdir, 
 
310
                    ignore_zero=ignore_zero, backup_files=backup_files, 
 
311
                    merge_type=merge_type, interesting_ids=interesting_ids)
 
312
        if base_is_ancestor and other_rev_id is not None\
 
313
            and other_rev_id not in this_branch.revision_history():
 
314
            this_branch.add_pending_merge(other_rev_id)
139
315
    finally:
140
316
        shutil.rmtree(tempdir)
141
317
 
142
318
 
143
 
def generate_cset_optimized(tree_a, tree_b, inventory_a, inventory_b):
144
 
    """Generate a changeset, using the text_id to mark really-changed files.
145
 
    This permits blazing comparisons when text_ids are present.  It also
146
 
    disables metadata comparison for files with identical texts.
 
319
def set_interesting(inventory_a, inventory_b, interesting_ids):
 
320
    """Mark files whose ids are in interesting_ids as interesting
 
321
    """
 
322
    for inventory in (inventory_a, inventory_b):
 
323
        for path, source_file in inventory.iteritems():
 
324
             source_file.interesting = source_file.id in interesting_ids
 
325
 
 
326
 
 
327
def generate_cset_optimized(tree_a, tree_b, interesting_ids=None):
 
328
    """Generate a changeset.  If interesting_ids is supplied, only changes
 
329
    to those files will be shown.  Metadata changes are stripped.
147
330
    """ 
148
 
    for file_id in tree_a.tree.inventory:
149
 
        if file_id not in tree_b.tree.inventory:
150
 
            continue
151
 
        entry_a = tree_a.tree.inventory[file_id]
152
 
        entry_b = tree_b.tree.inventory[file_id]
153
 
        if (entry_a.kind, entry_b.kind) != ("file", "file"):
154
 
            continue
155
 
        if None in (entry_a.text_id, entry_b.text_id):
156
 
            continue
157
 
        if entry_a.text_id != entry_b.text_id:
158
 
            continue
159
 
        inventory_a[abspath(tree_a.tree, file_id)].interesting = False
160
 
        inventory_b[abspath(tree_b.tree, file_id)].interesting = False
161
 
    cset =  generate_changeset(tree_a, tree_b, inventory_a, inventory_b)
 
331
    cset =  generate_changeset(tree_a, tree_b, interesting_ids)
162
332
    for entry in cset.entries.itervalues():
163
333
        entry.metadata_change = None
164
334
    return cset
165
335
 
166
336
 
167
 
def merge_inner(this_branch, other_tree, base_tree, tempdir):
168
 
    this_tree = get_tree(('.', None), tempdir, "this")
 
337
def merge_inner(this_branch, other_tree, base_tree, tempdir, 
 
338
                ignore_zero=False, merge_type=ApplyMerge3, backup_files=False,
 
339
                interesting_ids=None):
 
340
 
 
341
    def merge_factory(file_id, base, other):
 
342
        contents_change = merge_type(file_id, base, other)
 
343
        if backup_files:
 
344
            contents_change = BackupBeforeChange(contents_change)
 
345
        return contents_change
 
346
 
 
347
    this_tree = get_tree((this_branch.base, None), tempdir, "this")[1]
169
348
 
170
349
    def get_inventory(tree):
171
 
        return tree.inventory
 
350
        return tree.tree.inventory
172
351
 
173
352
    inv_changes = merge_flex(this_tree, base_tree, other_tree,
174
353
                             generate_cset_optimized, get_inventory,
175
 
                             MergeConflictHandler(base_tree.root))
 
354
                             MergeConflictHandler(ignore_zero=ignore_zero),
 
355
                             merge_factory=merge_factory, 
 
356
                             interesting_ids=interesting_ids)
176
357
 
177
358
    adjust_ids = []
178
359
    for id, path in inv_changes.iteritems():
180
361
            if path == '.':
181
362
                path = ''
182
363
            else:
183
 
                assert path.startswith('./')
 
364
                assert path.startswith('.' + os.sep), "path is %s" % path
184
365
            path = path[2:]
185
366
        adjust_ids.append((path, id))
186
 
    this_branch.set_inventory(regen_inventory(this_branch, this_tree.root, adjust_ids))
 
367
    if len(adjust_ids) > 0:
 
368
        this_branch.set_inventory(regen_inventory(this_branch, this_tree.root,
 
369
                                                  adjust_ids))
187
370
 
188
371
 
189
372
def regen_inventory(this_branch, root, new_entries):
190
373
    old_entries = this_branch.read_working_inventory()
191
374
    new_inventory = {}
192
375
    by_path = {}
 
376
    new_entries_map = {} 
 
377
    for path, file_id in new_entries:
 
378
        if path is None:
 
379
            continue
 
380
        new_entries_map[file_id] = path
 
381
 
 
382
    def id2path(file_id):
 
383
        path = new_entries_map.get(file_id)
 
384
        if path is not None:
 
385
            return path
 
386
        entry = old_entries[file_id]
 
387
        if entry.parent_id is None:
 
388
            return entry.name
 
389
        return os.path.join(id2path(entry.parent_id), entry.name)
 
390
        
193
391
    for file_id in old_entries:
194
392
        entry = old_entries[file_id]
195
 
        path = old_entries.id2path(file_id)
 
393
        path = id2path(file_id)
196
394
        new_inventory[file_id] = (path, file_id, entry.parent_id, entry.kind)
197
395
        by_path[path] = file_id
198
396
    
226
424
    assert len(new_inventory_list) == len(old_entries) + insertions - deletions
227
425
    new_inventory_list.sort()
228
426
    return new_inventory_list
 
427
 
 
428
merge_types = {     "merge3": (ApplyMerge3, "Native diff3-style merge"), 
 
429
                     "diff3": (Diff3Merge,  "Merge using external diff3")
 
430
              }
 
431