← 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-22 06:19:33 UTC
  • Revision ID: mbp@sourcefrog.net-20050922061933-4b71d0f1e205b153
- keep track of number of checked revisions

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