← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: Robert Collins
  • Date: 2005-09-28 04:58:18 UTC
  • mto: (1092.2.19)
  • mto: This revision was merged to the branch mainline in revision 1391.
  • Revision ID: robertc@robertcollins.net-20050928045818-c5ce6c7cc796f6fc
patch from Rob Weir to correct bzr-man.py

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
 
22
from fetch import greedy_fetch
 
23
 
 
24
import bzrlib.osutils
 
25
import bzrlib.revision
 
26
from bzrlib.merge_core import merge_flex, ApplyMerge3, BackupBeforeChange
 
27
from bzrlib.changeset import generate_changeset, ExceptionConflictHandler
 
28
from bzrlib.changeset import Inventory, Diff3Merge
 
29
from bzrlib.branch import Branch
 
30
from bzrlib.errors import BzrCommandError, UnrelatedBranches, NoCommonAncestor
 
31
from bzrlib.errors import NoCommits
 
32
from bzrlib.delta import compare_trees
 
33
from bzrlib.trace import mutter, warning
 
34
from bzrlib.fetch import greedy_fetch
 
35
from bzrlib.revision import is_ancestor
 
36
from bzrlib.osutils import rename
 
37
 
 
38
 
 
39
# comments from abentley on irc: merge happens in two stages, each
 
40
# of which generates a changeset object
 
41
 
 
42
# stage 1: generate OLD->OTHER,
 
43
# stage 2: use MINE and OLD->OTHER to generate MINE -> RESULT
11
44
 
12
45
class MergeConflictHandler(ExceptionConflictHandler):
13
 
    """Handle conflicts encountered while merging"""
 
46
    """Handle conflicts encountered while merging.
 
47
 
 
48
    This subclasses ExceptionConflictHandler, so that any types of
 
49
    conflict that are not explicitly handled cause an exception and
 
50
    terminate the merge.
 
51
    """
 
52
    def __init__(self, ignore_zero=False):
 
53
        ExceptionConflictHandler.__init__(self)
 
54
        self.conflicts = 0
 
55
        self.ignore_zero = ignore_zero
 
56
 
14
57
    def copy(self, source, dest):
15
58
        """Copy the text and mode of a file
16
59
        :param source: The path of the file to copy
22
65
            d_file.write(line)
23
66
        os.chmod(dest, 0777 & os.stat(source).st_mode)
24
67
 
 
68
    def dump(self, lines, dest):
 
69
        """Copy the text and mode of a file
 
70
        :param source: The path of the file to copy
 
71
        :param dest: The distination file to create
 
72
        """
 
73
        d_file = file(dest, "wb")
 
74
        for line in lines:
 
75
            d_file.write(line)
 
76
 
25
77
    def add_suffix(self, name, suffix, last_new_name=None):
26
78
        """Rename a file to append a suffix.  If the new name exists, the
27
79
        suffix is added repeatedly until a non-existant name is found
34
86
            last_new_name = name
35
87
        new_name = last_new_name+suffix
36
88
        try:
37
 
            os.rename(name, new_name)
 
89
            rename(name, new_name)
 
90
            return new_name
38
91
        except OSError, e:
39
92
            if e.errno != errno.EEXIST and e.errno != errno.ENOTEMPTY:
40
93
                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):
 
94
            return self.add_suffix(name, suffix, last_new_name=new_name)
 
95
 
 
96
    def conflict(self, text):
 
97
        warning(text)
 
98
        self.conflicts += 1
 
99
        
 
100
 
 
101
    def merge_conflict(self, new_file, this_path, base_lines, other_lines):
44
102
        """
45
103
        Handle diff3 conflicts by producing a .THIS, .BASE and .OTHER.  The
46
104
        main file will be a version with diff3 conflicts.
50
108
        :param other_path: Path to the file text for the OTHER tree
51
109
        """
52
110
        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)
 
111
        self.dump(base_lines, this_path+".BASE")
 
112
        self.dump(other_lines, this_path+".OTHER")
 
113
        rename(new_file, this_path)
 
114
        self.conflict("Diff3 conflict encountered in %s" % this_path)
 
115
 
 
116
    def new_contents_conflict(self, filename, other_contents):
 
117
        """Conflicting contents for newly added file."""
 
118
        self.copy(other_contents, filename + ".OTHER")
 
119
        self.conflict("Conflict in newly added file %s" % filename)
 
120
    
56
121
 
57
122
    def target_exists(self, entry, target, old_path):
58
123
        """Handle the case when the target file or dir exists"""
59
 
        self.add_suffix(target, ".moved")
 
124
        moved_path = self.add_suffix(target, ".moved")
 
125
        self.conflict("Moved existing %s to %s" % (target, moved_path))
 
126
 
 
127
    def rmdir_non_empty(self, filename):
 
128
        """Handle the case where the dir to be removed still has contents"""
 
129
        self.conflict("Directory %s not removed because it is not empty"\
 
130
            % filename)
 
131
        return "skip"
 
132
 
 
133
    def finalize(self):
 
134
        if not self.ignore_zero:
 
135
            print "%d conflicts encountered.\n" % self.conflicts
60
136
            
61
 
class SourceFile:
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)
 
137
def get_tree(treespec, temp_root, label, local_branch=None):
 
138
    location, revno = treespec
 
139
    branch = Branch.open_containing(location)
75
140
    if revno is None:
 
141
        revision = None
 
142
    elif revno == -1:
 
143
        revision = branch.last_patch()
 
144
    else:
 
145
        revision = branch.get_rev_id(revno)
 
146
    return branch, get_revid_tree(branch, revision, temp_root, label,
 
147
                                  local_branch)
 
148
 
 
149
def get_revid_tree(branch, revision, temp_root, label, local_branch):
 
150
    if revision is None:
76
151
        base_tree = branch.working_tree()
77
 
    elif revno == -1:
78
 
        base_tree = branch.basis_tree()
79
152
    else:
80
 
        base_tree = branch.revision_tree(branch.lookup_revision(revno))
 
153
        if local_branch is not None:
 
154
            greedy_fetch(local_branch, branch, revision)
 
155
            base_tree = local_branch.revision_tree(revision)
 
156
        else:
 
157
            base_tree = branch.revision_tree(revision)
81
158
    temp_path = os.path.join(temp_root, label)
82
159
    os.mkdir(temp_path)
83
160
    return MergeTree(base_tree, temp_path)
84
161
 
85
162
 
86
 
def abspath(tree, file_id):
87
 
    path = tree.inventory.id2path(file_id)
88
 
    if path == "":
89
 
        return "./."
90
 
    return "./" + path
91
 
 
92
163
def file_exists(tree, file_id):
93
164
    return tree.has_filename(tree.id2path(file_id))
94
165
    
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
166
 
105
167
class MergeTree(object):
106
168
    def __init__(self, tree, tempdir):
109
171
            self.root = tree.basedir
110
172
        else:
111
173
            self.root = None
112
 
        self.inventory = inventory_map(tree)
113
174
        self.tree = tree
114
175
        self.tempdir = tempdir
115
176
        os.mkdir(os.path.join(self.tempdir, "texts"))
116
177
        self.cached = {}
117
178
 
 
179
    def __iter__(self):
 
180
        return self.tree.__iter__()
 
181
 
 
182
    def __contains__(self, file_id):
 
183
        return file_id in self.tree
 
184
 
 
185
    def get_file(self, file_id):
 
186
        return self.tree.get_file(file_id)
 
187
 
 
188
    def get_file_sha1(self, id):
 
189
        return self.tree.get_file_sha1(id)
 
190
 
 
191
    def id2path(self, file_id):
 
192
        return self.tree.id2path(file_id)
 
193
 
 
194
    def has_id(self, file_id):
 
195
        return self.tree.has_id(file_id)
 
196
 
 
197
    def has_or_had_id(self, file_id):
 
198
        if file_id == self.tree.inventory.root.file_id:
 
199
            return True
 
200
        return self.tree.inventory.has_id(file_id)
 
201
 
 
202
    def has_or_had_id(self, file_id):
 
203
        if file_id == self.tree.inventory.root.file_id:
 
204
            return True
 
205
        return self.tree.inventory.has_id(file_id)
 
206
 
118
207
    def readonly_path(self, id):
 
208
        if id not in self.tree:
 
209
            return None
119
210
        if self.root is not None:
120
211
            return self.tree.abspath(self.tree.id2path(id))
121
212
        else:
129
220
                self.cached[id] = path
130
221
            return self.cached[id]
131
222
 
132
 
def merge(other_revision, base_revision):
 
223
 
 
224
 
 
225
def merge(other_revision, base_revision,
 
226
          check_clean=True, ignore_zero=False,
 
227
          this_dir=None, backup_files=False, merge_type=ApplyMerge3,
 
228
          file_list=None):
 
229
    """Merge changes into a tree.
 
230
 
 
231
    base_revision
 
232
        tuple(path, revision) Base for three-way merge.
 
233
    other_revision
 
234
        tuple(path, revision) Other revision for three-way merge.
 
235
    this_dir
 
236
        Directory to merge changes into; '.' by default.
 
237
    check_clean
 
238
        If true, this_dir must have no uncommitted changes before the
 
239
        merge begins.
 
240
    all available ancestors of other_revision and base_revision are
 
241
    automatically pulled into the branch.
 
242
    """
 
243
    from bzrlib.revision import common_ancestor, MultipleRevisionSources
 
244
    from bzrlib.errors import NoSuchRevision
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_patch()
 
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_patch()
 
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_patch()
 
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_patch()
 
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
            multi_source = MultipleRevisionSources(this_branch, base_branch)
 
291
            base_is_ancestor = is_ancestor(this_rev_id, base_rev_id,
 
292
                                           multi_source)
 
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