← 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-08-25 05:58:05 UTC
  • mfrom: (974.1.36)
  • Revision ID: mbp@sourcefrog.net-20050825055805-8c892bc3c2d75131
- merge aaron's merge improvements:

  * When merging, pull in all missing revisions from the source
    branch. 

  * Detect common ancestors by looking at the whole ancestry graph, 
    rather than just mainline history.

  Some changes to reconcile this with parallel updates to the test and
  trace code.

aaron.bentley@utoronto.ca-20050823052551-f3401a8b57d9126f

Show diffs side-by-side

added added

removed removed

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