← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: John Arbash Meinel
  • Date: 2005-09-19 03:26:14 UTC
  • mto: (1393.2.1)
  • mto: This revision was merged to the branch mainline in revision 1396.
  • Revision ID: john@arbash-meinel.com-20050919032614-79751b0510f24929
Major refactoring of testtransport.
Rewrote test_transport() as a class which can be subclassed which provides
many test_* functions, rather than one large function.
Much easier to debug.

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