~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: Robert Collins
  • Date: 2006-04-28 11:01:38 UTC
  • mfrom: (1687 +trunk)
  • mto: (1704.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 1706.
  • Revision ID: robertc@robertcollins.net-20060428110138-0e69ecb765434f9d
MergeĀ fromĀ mainline.

Show diffs side-by-side

added added

removed removed

Lines of Context:
17
17
 
18
18
import os
19
19
import errno
 
20
from shutil import rmtree
 
21
from tempfile import mkdtemp
20
22
 
21
23
import bzrlib
22
 
from bzrlib._changeset import generate_changeset, ExceptionConflictHandler
23
 
from bzrlib._changeset import Inventory, Diff3Merge, ReplaceContents
24
 
from bzrlib._merge_core import WeaveMerge
25
 
from bzrlib._merge_core import merge_flex, ApplyMerge3, BackupBeforeChange
26
24
from bzrlib.branch import Branch
 
25
from bzrlib.conflicts import ConflictList, Conflict
27
26
from bzrlib.delta import compare_trees
28
27
from bzrlib.errors import (BzrCommandError,
29
28
                           BzrError,
30
29
                           NoCommonAncestor,
31
30
                           NoCommits,
32
31
                           NoSuchRevision,
 
32
                           NoSuchFile,
33
33
                           NotBranchError,
34
34
                           NotVersionedError,
35
35
                           UnrelatedBranches,
 
36
                           UnsupportedOperation,
36
37
                           WorkingTreeNotRevision,
 
38
                           BinaryFile,
37
39
                           )
38
 
from bzrlib.fetch import greedy_fetch, fetch
 
40
from bzrlib.merge3 import Merge3
39
41
import bzrlib.osutils
40
42
from bzrlib.osutils import rename, pathjoin
 
43
from progress import DummyProgress, ProgressPhase
41
44
from bzrlib.revision import common_ancestor, is_ancestor, NULL_REVISION
 
45
from bzrlib.symbol_versioning import *
 
46
from bzrlib.textfile import check_text_lines
42
47
from bzrlib.trace import mutter, warning, note
 
48
from bzrlib.transform import (TreeTransform, resolve_conflicts, cook_conflicts,
 
49
                              FinalPaths, create_by_entry, unique_add)
 
50
from bzrlib.versionedfile import WeaveMerge
 
51
import bzrlib.ui
43
52
 
44
53
# TODO: Report back as changes are merged in
45
54
 
46
 
# comments from abentley on irc: merge happens in two stages, each
47
 
# of which generates a changeset object
48
 
 
49
 
# stage 1: generate OLD->OTHER,
50
 
# stage 2: use MINE and OLD->OTHER to generate MINE -> RESULT
51
 
 
52
 
class _MergeConflictHandler(ExceptionConflictHandler):
53
 
    """Handle conflicts encountered while merging.
54
 
 
55
 
    This subclasses ExceptionConflictHandler, so that any types of
56
 
    conflict that are not explicitly handled cause an exception and
57
 
    terminate the merge.
58
 
    """
59
 
    def __init__(self, this_tree, base_tree, other_tree, ignore_zero=False):
60
 
        ExceptionConflictHandler.__init__(self)
61
 
        self.conflicts = 0
62
 
        self.ignore_zero = ignore_zero
63
 
        self.this_tree = this_tree
64
 
        self.base_tree = base_tree
65
 
        self.other_tree = other_tree
66
 
 
67
 
    def copy(self, source, dest):
68
 
        """Copy the text and mode of a file
69
 
        :param source: The path of the file to copy
70
 
        :param dest: The distination file to create
71
 
        """
72
 
        s_file = file(source, "rb")
73
 
        d_file = file(dest, "wb")
74
 
        for line in s_file:
75
 
            d_file.write(line)
76
 
        os.chmod(dest, 0777 & os.stat(source).st_mode)
77
 
 
78
 
    def dump(self, lines, dest):
79
 
        """Copy the text and mode of a file
80
 
        :param source: The path of the file to copy
81
 
        :param dest: The distination file to create
82
 
        """
83
 
        d_file = file(dest, "wb")
84
 
        for line in lines:
85
 
            d_file.write(line)
86
 
 
87
 
    def add_suffix(self, name, suffix, last_new_name=None, fix_inventory=True):
88
 
        """Rename a file to append a suffix.  If the new name exists, the
89
 
        suffix is added repeatedly until a non-existant name is found
90
 
 
91
 
        :param name: The path of the file
92
 
        :param suffix: The suffix to append
93
 
        :param last_new_name: (used for recursive calls) the last name tried
94
 
        """
95
 
        if last_new_name is None:
96
 
            last_new_name = name
97
 
        new_name = last_new_name+suffix
98
 
        try:
99
 
            rename(name, new_name)
100
 
            if fix_inventory is True:
101
 
                try:
102
 
                    relpath = self.this_tree.relpath(name)
103
 
                except NotBranchError:
104
 
                    relpath = None
105
 
                if relpath is not None:
106
 
                    file_id = self.this_tree.path2id(relpath)
107
 
                    if file_id is not None:
108
 
                        new_path = self.this_tree.relpath(new_name)
109
 
                        rename(new_name, name)
110
 
                        self.this_tree.rename_one(relpath, new_path)
111
 
                        assert self.this_tree.id2path(file_id) == new_path
112
 
        except OSError, e:
113
 
            if e.errno != errno.EEXIST and e.errno != errno.ENOTEMPTY:
114
 
                raise
115
 
            return self.add_suffix(name, suffix, last_new_name=new_name, 
116
 
                                   fix_inventory=fix_inventory)
117
 
        return new_name
118
 
 
119
 
    def conflict(self, text):
120
 
        warning(text)
121
 
        self.conflicts += 1
122
 
        
123
 
 
124
 
    def merge_conflict(self, new_file, this_path, base_lines, other_lines):
125
 
        """
126
 
        Handle diff3 conflicts by producing a .THIS, .BASE and .OTHER.  The
127
 
        main file will be a version with diff3 conflicts.
128
 
        :param new_file: Path to the output file with diff3 markers
129
 
        :param this_path: Path to the file text for the THIS tree
130
 
        :param base_path: Path to the file text for the BASE tree
131
 
        :param other_path: Path to the file text for the OTHER tree
132
 
        """
133
 
        self.add_suffix(this_path, ".THIS", fix_inventory=False)
134
 
        self.dump(base_lines, this_path+".BASE")
135
 
        self.dump(other_lines, this_path+".OTHER")
136
 
        rename(new_file, this_path)
137
 
        self.conflict("Diff3 conflict encountered in %s" % this_path)
138
 
 
139
 
    def weave_merge_conflict(self, filename, weave, other_i, out_file):
140
 
        """
141
 
        Handle weave conflicts by producing a .THIS, and .OTHER.  The
142
 
        main file will be a version with diff3-style conflicts.
143
 
        """
144
 
        self.add_suffix(filename, ".THIS", fix_inventory=False)
145
 
        out_file.commit()
146
 
        self.dump(weave.get_iter(other_i), filename+".OTHER")
147
 
        self.conflict("Text conflict encountered in %s" % filename)
148
 
 
149
 
    def new_contents_conflict(self, filename, other_contents):
150
 
        """Conflicting contents for newly added file."""
151
 
        other_contents(filename + ".OTHER", self, False)
152
 
        self.conflict("Conflict in newly added file %s" % filename)
153
 
    
154
 
 
155
 
    def target_exists(self, entry, target, old_path):
156
 
        """Handle the case when the target file or dir exists"""
157
 
        moved_path = self.add_suffix(target, ".moved")
158
 
        self.conflict("Moved existing %s to %s" % (target, moved_path))
159
 
 
160
 
    def rmdir_non_empty(self, filename):
161
 
        """Handle the case where the dir to be removed still has contents"""
162
 
        self.conflict("Directory %s not removed because it is not empty"\
163
 
            % filename)
164
 
        return "skip"
165
 
 
166
 
    def rem_contents_conflict(self, filename, this_contents, base_contents):
167
 
        base_contents(filename+".BASE", self)
168
 
        this_contents(filename+".THIS", self)
169
 
        self.conflict("Other branch deleted locally modified file %s" %
170
 
                      filename)
171
 
        return ReplaceContents(this_contents, None)
172
 
 
173
 
    def abs_this_path(self, file_id):
174
 
        """Return the absolute path for a file_id in the this tree."""
175
 
        return self.this_tree.id2abspath(file_id)
176
 
 
177
 
    def add_missing_parents(self, file_id, tree):
178
 
        """If some of the parents for file_id are missing, add them."""
179
 
        entry = tree.inventory[file_id]
180
 
        if entry.parent_id not in self.this_tree:
181
 
            return self.create_all_missing(entry.parent_id, tree)
182
 
        else:
183
 
            return self.abs_this_path(entry.parent_id)
184
 
 
185
 
    def create_all_missing(self, file_id, tree):
186
 
        """Add contents for a file_id and all its parents to a tree."""
187
 
        entry = tree.inventory[file_id]
188
 
        if entry.parent_id is not None and entry.parent_id not in self.this_tree:
189
 
            abspath = self.create_all_missing(entry.parent_id, tree)
190
 
        else:
191
 
            abspath = self.abs_this_path(entry.parent_id)
192
 
        entry_path = pathjoin(abspath, entry.name)
193
 
        if not os.path.isdir(entry_path):
194
 
            self.create(file_id, entry_path, tree)
195
 
        return entry_path
196
 
 
197
 
    def create(self, file_id, path, tree):
198
 
        """Uses tree data to create a filesystem object for the file_id"""
199
 
        from bzrlib._changeset import get_contents
200
 
        get_contents(tree, file_id)(path, self)
201
 
 
202
 
    def missing_for_merge(self, file_id, other_path):
203
 
        """The file_id doesn't exist in THIS, but does in OTHER and BASE"""
204
 
        self.conflict("Other branch modified locally deleted file %s" %
205
 
                      other_path)
206
 
        parent_dir = self.add_missing_parents(file_id, self.other_tree)
207
 
        stem = pathjoin(parent_dir, os.path.basename(other_path))
208
 
        self.create(file_id, stem+".OTHER", self.other_tree)
209
 
        self.create(file_id, stem+".BASE", self.base_tree)
210
 
 
211
 
    def threeway_contents_conflict(filename, this_contents, base_contents,
212
 
                                   other_contents):
213
 
        self.conflict("Three-way conflict merging %s" % filename)
214
 
 
215
 
    def finalize(self):
216
 
        if self.conflicts == 0:
217
 
            if not self.ignore_zero:
218
 
                note("All changes applied successfully.")
219
 
        else:
220
 
            note("%d conflicts encountered." % self.conflicts)
221
 
 
222
55
def _get_tree(treespec, local_branch=None):
223
56
    location, revno = treespec
224
57
    branch = Branch.open_containing(location)[0]
239
72
    else:
240
73
        if local_branch is not None:
241
74
            if local_branch.base != branch.base:
242
 
                greedy_fetch(local_branch, branch, revision)
 
75
                local_branch.fetch(branch, revision)
243
76
            base_tree = local_branch.repository.revision_tree(revision)
244
77
        else:
245
78
            base_tree = branch.repository.revision_tree(revision)
248
81
 
249
82
def transform_tree(from_tree, to_tree, interesting_ids=None):
250
83
    merge_inner(from_tree.branch, to_tree, from_tree, ignore_zero=True,
251
 
                interesting_ids=interesting_ids)
252
 
 
253
 
 
254
 
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
255
 
                backup_files=False, 
256
 
                merge_type=ApplyMerge3, 
257
 
                interesting_ids=None, 
258
 
                show_base=False, 
259
 
                reprocess=False, 
260
 
                other_rev_id=None,
261
 
                interesting_files=None,
262
 
                this_tree=None):
263
 
    """Primary interface for merging. 
264
 
 
265
 
        typical use is probably 
266
 
        'merge_inner(branch, branch.get_revision_tree(other_revision),
267
 
                     branch.get_revision_tree(base_revision))'
268
 
        """
269
 
    if this_tree is None:
270
 
        this_tree = this_branch.bzrdir.open_workingtree()
271
 
    merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree)
272
 
    merger.backup_files = backup_files
273
 
    merger.merge_type = merge_type
274
 
    merger.interesting_ids = interesting_ids
275
 
    if interesting_files:
276
 
        assert not interesting_ids, ('Only supply interesting_ids'
277
 
                                     ' or interesting_files')
278
 
        merger._set_interesting_files(interesting_files)
279
 
    merger.show_base = show_base 
280
 
    merger.reprocess = reprocess
281
 
    merger.conflict_handler = _MergeConflictHandler(merger.this_tree, 
282
 
                                                    base_tree, other_tree,
283
 
                                                    ignore_zero=ignore_zero)
284
 
    merger.other_rev_id = other_rev_id
285
 
    merger.other_basis = other_rev_id
286
 
    return merger.do_merge()
 
84
                interesting_ids=interesting_ids, this_tree=from_tree)
287
85
 
288
86
 
289
87
class Merger(object):
290
 
    def __init__(self, this_branch, other_tree=None, base_tree=None, this_tree=None):
 
88
    def __init__(self, this_branch, other_tree=None, base_tree=None, 
 
89
                 this_tree=None, pb=DummyProgress()):
291
90
        object.__init__(self)
292
91
        assert this_tree is not None, "this_tree is required"
293
92
        self.this_branch = this_branch
303
102
        self.interesting_ids = None
304
103
        self.show_base = False
305
104
        self.reprocess = False
306
 
        self.conflict_handler = _MergeConflictHandler(self.this_tree, 
307
 
                                                      base_tree, other_tree)
 
105
        self._pb = pb 
 
106
        self.pp = None
 
107
 
308
108
 
309
109
    def revision_tree(self, revision_id):
310
110
        return self.this_branch.repository.revision_tree(revision_id)
338
138
        trees = (self.this_basis_tree, self.other_tree)
339
139
        return [get_id(tree, file_id) for tree in trees]
340
140
 
341
 
    def merge_factory(self, file_id, base, other):
342
 
        if self.merge_type.history_based:
343
 
            if self.show_base is True:
344
 
                raise BzrError("Cannot show base for hisory-based merges")
345
 
            if self.reprocess is True:
346
 
                raise BzrError("Cannot reprocess history-based merges")
347
 
                
348
 
            t_revid, o_revid = self.file_revisions(file_id)
349
 
            weave = self.this_basis_tree.get_weave(file_id)
350
 
            contents_change = self.merge_type(weave, t_revid, o_revid)
351
 
        else:
352
 
            if self.show_base is True or self.reprocess is True:
353
 
                contents_change = self.merge_type(file_id, base, other, 
354
 
                                                  show_base=self.show_base, 
355
 
                                                  reprocess=self.reprocess)
356
 
            else:
357
 
                contents_change = self.merge_type(file_id, base, other)
358
 
        if self.backup_files:
359
 
            contents_change = BackupBeforeChange(contents_change)
360
 
        return contents_change
361
 
 
362
141
    def check_basis(self, check_clean):
363
142
        if self.this_basis is None:
364
143
            raise BzrCommandError("This branch has no commits")
425
204
            if self.other_basis is None:
426
205
                raise NoCommits(other_branch)
427
206
        if other_branch.base != self.this_branch.base:
428
 
            fetch(from_branch=other_branch, to_branch=self.this_branch, 
429
 
                  last_revision=self.other_basis)
 
207
            self.this_branch.fetch(other_branch, last_revision=self.other_basis)
430
208
 
431
209
    def set_base(self, base_revision):
432
210
        mutter("doing merge() with no base_revision specified")
433
211
        if base_revision == [None, None]:
434
212
            try:
435
 
                self.base_rev_id = common_ancestor(self.this_basis, 
436
 
                                                   self.other_basis, 
437
 
                                                   self.this_branch.repository)
 
213
                pb = bzrlib.ui.ui_factory.nested_progress_bar()
 
214
                try:
 
215
                    this_repo = self.this_branch.repository
 
216
                    self.base_rev_id = common_ancestor(self.this_basis, 
 
217
                                                       self.other_basis, 
 
218
                                                       this_repo, pb)
 
219
                finally:
 
220
                    pb.finished()
438
221
            except NoCommonAncestor:
439
222
                raise UnrelatedBranches()
440
223
            self.base_tree = _get_revid_tree(self.this_branch, self.base_rev_id,
448
231
                self.base_rev_id = None
449
232
            else:
450
233
                self.base_rev_id = base_branch.get_rev_id(base_revision[1])
451
 
            fetch(from_branch=base_branch, to_branch=self.this_branch)
 
234
            if self.this_branch.base != base_branch.base:
 
235
                self.this_branch.fetch(base_branch)
452
236
            self.base_is_ancestor = is_ancestor(self.this_basis, 
453
237
                                                self.base_rev_id,
454
238
                                                self.this_branch)
455
239
 
456
240
    def do_merge(self):
457
 
        def get_inventory(tree):
458
 
            return tree.inventory
459
 
        
460
 
        inv_changes = merge_flex(self.this_tree, self.base_tree, 
461
 
                                 self.other_tree,
462
 
                                 generate_changeset, get_inventory,
463
 
                                 self.conflict_handler,
464
 
                                 merge_factory=self.merge_factory, 
465
 
                                 interesting_ids=self.interesting_ids)
 
241
        kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree, 
 
242
                  'other_tree': self.other_tree, 
 
243
                  'interesting_ids': self.interesting_ids,
 
244
                  'pp': self.pp}
 
245
        if self.merge_type.requires_base:
 
246
            kwargs['base_tree'] = self.base_tree
 
247
        if self.merge_type.supports_reprocess:
 
248
            kwargs['reprocess'] = self.reprocess
 
249
        elif self.reprocess:
 
250
            raise BzrError("Conflict reduction is not supported for merge"
 
251
                                  " type %s." % self.merge_type)
 
252
        if self.merge_type.supports_show_base:
 
253
            kwargs['show_base'] = self.show_base
 
254
        elif self.show_base:
 
255
            raise BzrError("Showing base is not supported for this"
 
256
                                  " merge type. %s" % self.merge_type)
 
257
        merge = self.merge_type(pb=self._pb, **kwargs)
 
258
        if len(merge.cooked_conflicts) == 0:
 
259
            if not self.ignore_zero:
 
260
                note("All changes applied successfully.")
 
261
        else:
 
262
            note("%d conflicts encountered." % len(merge.cooked_conflicts))
466
263
 
467
 
        adjust_ids = []
468
 
        for id, path in inv_changes.iteritems():
469
 
            if path is not None:
470
 
                if path == u'.':
471
 
                    path = u''
472
 
                else:
473
 
                    assert path.startswith('.' + '/') or path.startswith('.' + '\\'), "path is %s" % path
474
 
                path = path[2:]
475
 
            adjust_ids.append((path, id))
476
 
        if len(adjust_ids) > 0:
477
 
            self.this_tree.set_inventory(self.regen_inventory(adjust_ids))
478
 
        conflicts = self.conflict_handler.conflicts
479
 
        self.conflict_handler.finalize()
480
 
        return conflicts
 
264
        return len(merge.cooked_conflicts)
481
265
 
482
266
    def regen_inventory(self, new_entries):
483
267
        old_entries = self.this_tree.read_working_inventory()
501
285
        for file_id in old_entries:
502
286
            entry = old_entries[file_id]
503
287
            path = id2path(file_id)
 
288
            if file_id in self.base_tree.inventory:
 
289
                executable = getattr(self.base_tree.inventory[file_id], 'executable', False)
 
290
            else:
 
291
                executable = getattr(entry, 'executable', False)
504
292
            new_inventory[file_id] = (path, file_id, entry.parent_id, 
505
 
                                      entry.kind)
 
293
                                      entry.kind, executable)
 
294
                                      
506
295
            by_path[path] = file_id
507
296
        
508
297
        deletions = 0
525
314
                parent = by_path[os.path.dirname(path)]
526
315
            abspath = pathjoin(self.this_tree.basedir, path)
527
316
            kind = bzrlib.osutils.file_kind(abspath)
528
 
            new_inventory[file_id] = (path, file_id, parent, kind)
 
317
            if file_id in self.base_tree.inventory:
 
318
                executable = getattr(self.base_tree.inventory[file_id], 'executable', False)
 
319
            else:
 
320
                executable = False
 
321
            new_inventory[file_id] = (path, file_id, parent, kind, executable)
529
322
            by_path[path] = file_id 
530
323
 
531
324
        # Get a list in insertion order
540
333
        return new_inventory_list
541
334
 
542
335
 
543
 
merge_types = {     "merge3": (ApplyMerge3, "Native diff3-style merge"), 
544
 
                     "diff3": (Diff3Merge,  "Merge using external diff3"),
545
 
                     'weave': (WeaveMerge, "Weave-based merge")
 
336
class Merge3Merger(object):
 
337
    """Three-way merger that uses the merge3 text merger"""
 
338
    requires_base = True
 
339
    supports_reprocess = True
 
340
    supports_show_base = True
 
341
    history_based = False
 
342
 
 
343
    def __init__(self, working_tree, this_tree, base_tree, other_tree, 
 
344
                 interesting_ids=None, reprocess=False, show_base=False,
 
345
                 pb=DummyProgress(), pp=None):
 
346
        """Initialize the merger object and perform the merge."""
 
347
        object.__init__(self)
 
348
        self.this_tree = working_tree
 
349
        self.base_tree = base_tree
 
350
        self.other_tree = other_tree
 
351
        self._raw_conflicts = []
 
352
        self.cooked_conflicts = []
 
353
        self.reprocess = reprocess
 
354
        self.show_base = show_base
 
355
        self.pb = pb
 
356
        self.pp = pp
 
357
        if self.pp is None:
 
358
            self.pp = ProgressPhase("Merge phase", 3, self.pb)
 
359
 
 
360
        if interesting_ids is not None:
 
361
            all_ids = interesting_ids
 
362
        else:
 
363
            all_ids = set(base_tree)
 
364
            all_ids.update(other_tree)
 
365
        working_tree.lock_write()
 
366
        self.tt = TreeTransform(working_tree, self.pb)
 
367
        try:
 
368
            self.pp.next_phase()
 
369
            child_pb = bzrlib.ui.ui_factory.nested_progress_bar()
 
370
            try:
 
371
                for num, file_id in enumerate(all_ids):
 
372
                    child_pb.update('Preparing file merge', num, len(all_ids))
 
373
                    self.merge_names(file_id)
 
374
                    file_status = self.merge_contents(file_id)
 
375
                    self.merge_executable(file_id, file_status)
 
376
            finally:
 
377
                child_pb.finished()
 
378
                
 
379
            self.pp.next_phase()
 
380
            child_pb = bzrlib.ui.ui_factory.nested_progress_bar()
 
381
            try:
 
382
                fs_conflicts = resolve_conflicts(self.tt, child_pb)
 
383
            finally:
 
384
                child_pb.finished()
 
385
            self.cook_conflicts(fs_conflicts)
 
386
            for conflict in self.cooked_conflicts:
 
387
                warning(conflict)
 
388
            self.pp.next_phase()
 
389
            results = self.tt.apply()
 
390
            self.write_modified(results)
 
391
            try:
 
392
                working_tree.set_conflicts(ConflictList(self.cooked_conflicts))
 
393
            except UnsupportedOperation:
 
394
                pass
 
395
        finally:
 
396
            try:
 
397
                self.tt.finalize()
 
398
            except:
 
399
                pass
 
400
            working_tree.unlock()
 
401
            self.pb.clear()
 
402
 
 
403
    def write_modified(self, results):
 
404
        modified_hashes = {}
 
405
        for path in results.modified_paths:
 
406
            file_id = self.this_tree.path2id(self.this_tree.relpath(path))
 
407
            if file_id is None:
 
408
                continue
 
409
            hash = self.this_tree.get_file_sha1(file_id)
 
410
            if hash is None:
 
411
                continue
 
412
            modified_hashes[file_id] = hash
 
413
        self.this_tree.set_merge_modified(modified_hashes)
 
414
 
 
415
    @staticmethod
 
416
    def parent(entry, file_id):
 
417
        """Determine the parent for a file_id (used as a key method)"""
 
418
        if entry is None:
 
419
            return None
 
420
        return entry.parent_id
 
421
 
 
422
    @staticmethod
 
423
    def name(entry, file_id):
 
424
        """Determine the name for a file_id (used as a key method)"""
 
425
        if entry is None:
 
426
            return None
 
427
        return entry.name
 
428
    
 
429
    @staticmethod
 
430
    def contents_sha1(tree, file_id):
 
431
        """Determine the sha1 of the file contents (used as a key method)."""
 
432
        if file_id not in tree:
 
433
            return None
 
434
        return tree.get_file_sha1(file_id)
 
435
 
 
436
    @staticmethod
 
437
    def executable(tree, file_id):
 
438
        """Determine the executability of a file-id (used as a key method)."""
 
439
        if file_id not in tree:
 
440
            return None
 
441
        if tree.kind(file_id) != "file":
 
442
            return False
 
443
        return tree.is_executable(file_id)
 
444
 
 
445
    @staticmethod
 
446
    def kind(tree, file_id):
 
447
        """Determine the kind of a file-id (used as a key method)."""
 
448
        if file_id not in tree:
 
449
            return None
 
450
        return tree.kind(file_id)
 
451
 
 
452
    @staticmethod
 
453
    def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
 
454
        """Do a three-way test on a scalar.
 
455
        Return "this", "other" or "conflict", depending whether a value wins.
 
456
        """
 
457
        key_base = key(base_tree, file_id)
 
458
        key_other = key(other_tree, file_id)
 
459
        #if base == other, either they all agree, or only THIS has changed.
 
460
        if key_base == key_other:
 
461
            return "this"
 
462
        key_this = key(this_tree, file_id)
 
463
        if key_this not in (key_base, key_other):
 
464
            return "conflict"
 
465
        # "Ambiguous clean merge"
 
466
        elif key_this == key_other:
 
467
            return "this"
 
468
        else:
 
469
            assert key_this == key_base
 
470
            return "other"
 
471
 
 
472
    def merge_names(self, file_id):
 
473
        """Perform a merge on file_id names and parents"""
 
474
        def get_entry(tree):
 
475
            if file_id in tree.inventory:
 
476
                return tree.inventory[file_id]
 
477
            else:
 
478
                return None
 
479
        this_entry = get_entry(self.this_tree)
 
480
        other_entry = get_entry(self.other_tree)
 
481
        base_entry = get_entry(self.base_tree)
 
482
        name_winner = self.scalar_three_way(this_entry, base_entry, 
 
483
                                            other_entry, file_id, self.name)
 
484
        parent_id_winner = self.scalar_three_way(this_entry, base_entry, 
 
485
                                                 other_entry, file_id, 
 
486
                                                 self.parent)
 
487
        if this_entry is None:
 
488
            if name_winner == "this":
 
489
                name_winner = "other"
 
490
            if parent_id_winner == "this":
 
491
                parent_id_winner = "other"
 
492
        if name_winner == "this" and parent_id_winner == "this":
 
493
            return
 
494
        if name_winner == "conflict":
 
495
            trans_id = self.tt.trans_id_file_id(file_id)
 
496
            self._raw_conflicts.append(('name conflict', trans_id, 
 
497
                                        self.name(this_entry, file_id), 
 
498
                                        self.name(other_entry, file_id)))
 
499
        if parent_id_winner == "conflict":
 
500
            trans_id = self.tt.trans_id_file_id(file_id)
 
501
            self._raw_conflicts.append(('parent conflict', trans_id, 
 
502
                                        self.parent(this_entry, file_id), 
 
503
                                        self.parent(other_entry, file_id)))
 
504
        if other_entry is None:
 
505
            # it doesn't matter whether the result was 'other' or 
 
506
            # 'conflict'-- if there's no 'other', we leave it alone.
 
507
            return
 
508
        # if we get here, name_winner and parent_winner are set to safe values.
 
509
        winner_entry = {"this": this_entry, "other": other_entry, 
 
510
                        "conflict": other_entry}
 
511
        trans_id = self.tt.trans_id_file_id(file_id)
 
512
        parent_id = winner_entry[parent_id_winner].parent_id
 
513
        parent_trans_id = self.tt.trans_id_file_id(parent_id)
 
514
        self.tt.adjust_path(winner_entry[name_winner].name, parent_trans_id,
 
515
                            trans_id)
 
516
 
 
517
    def merge_contents(self, file_id):
 
518
        """Performa a merge on file_id contents."""
 
519
        def contents_pair(tree):
 
520
            if file_id not in tree:
 
521
                return (None, None)
 
522
            kind = tree.kind(file_id)
 
523
            if kind == "root_directory":
 
524
                kind = "directory"
 
525
            if kind == "file":
 
526
                contents = tree.get_file_sha1(file_id)
 
527
            elif kind == "symlink":
 
528
                contents = tree.get_symlink_target(file_id)
 
529
            else:
 
530
                contents = None
 
531
            return kind, contents
 
532
 
 
533
        def contents_conflict():
 
534
            trans_id = self.tt.trans_id_file_id(file_id)
 
535
            name = self.tt.final_name(trans_id)
 
536
            parent_id = self.tt.final_parent(trans_id)
 
537
            if file_id in self.this_tree.inventory:
 
538
                self.tt.unversion_file(trans_id)
 
539
                self.tt.delete_contents(trans_id)
 
540
            file_group = self._dump_conflicts(name, parent_id, file_id, 
 
541
                                              set_version=True)
 
542
            self._raw_conflicts.append(('contents conflict', file_group))
 
543
 
 
544
        # See SPOT run.  run, SPOT, run.
 
545
        # So we're not QUITE repeating ourselves; we do tricky things with
 
546
        # file kind...
 
547
        base_pair = contents_pair(self.base_tree)
 
548
        other_pair = contents_pair(self.other_tree)
 
549
        if base_pair == other_pair:
 
550
            # OTHER introduced no changes
 
551
            return "unmodified"
 
552
        this_pair = contents_pair(self.this_tree)
 
553
        if this_pair == other_pair:
 
554
            # THIS and OTHER introduced the same changes
 
555
            return "unmodified"
 
556
        else:
 
557
            trans_id = self.tt.trans_id_file_id(file_id)
 
558
            if this_pair == base_pair:
 
559
                # only OTHER introduced changes
 
560
                if file_id in self.this_tree:
 
561
                    # Remove any existing contents
 
562
                    self.tt.delete_contents(trans_id)
 
563
                if file_id in self.other_tree:
 
564
                    # OTHER changed the file
 
565
                    create_by_entry(self.tt, 
 
566
                                    self.other_tree.inventory[file_id], 
 
567
                                    self.other_tree, trans_id)
 
568
                    if file_id not in self.this_tree.inventory:
 
569
                        self.tt.version_file(file_id, trans_id)
 
570
                    return "modified"
 
571
                elif file_id in self.this_tree.inventory:
 
572
                    # OTHER deleted the file
 
573
                    self.tt.unversion_file(trans_id)
 
574
                    return "deleted"
 
575
            #BOTH THIS and OTHER introduced changes; scalar conflict
 
576
            elif this_pair[0] == "file" and other_pair[0] == "file":
 
577
                # THIS and OTHER are both files, so text merge.  Either
 
578
                # BASE is a file, or both converted to files, so at least we
 
579
                # have agreement that output should be a file.
 
580
                try:
 
581
                    self.text_merge(file_id, trans_id)
 
582
                except BinaryFile:
 
583
                    return contents_conflict()
 
584
                if file_id not in self.this_tree.inventory:
 
585
                    self.tt.version_file(file_id, trans_id)
 
586
                try:
 
587
                    self.tt.tree_kind(trans_id)
 
588
                    self.tt.delete_contents(trans_id)
 
589
                except NoSuchFile:
 
590
                    pass
 
591
                return "modified"
 
592
            else:
 
593
                # Scalar conflict, can't text merge.  Dump conflicts
 
594
                return contents_conflict()
 
595
 
 
596
    def get_lines(self, tree, file_id):
 
597
        """Return the lines in a file, or an empty list."""
 
598
        if file_id in tree:
 
599
            return tree.get_file(file_id).readlines()
 
600
        else:
 
601
            return []
 
602
 
 
603
    def text_merge(self, file_id, trans_id):
 
604
        """Perform a three-way text merge on a file_id"""
 
605
        # it's possible that we got here with base as a different type.
 
606
        # if so, we just want two-way text conflicts.
 
607
        if file_id in self.base_tree and \
 
608
            self.base_tree.kind(file_id) == "file":
 
609
            base_lines = self.get_lines(self.base_tree, file_id)
 
610
        else:
 
611
            base_lines = []
 
612
        other_lines = self.get_lines(self.other_tree, file_id)
 
613
        this_lines = self.get_lines(self.this_tree, file_id)
 
614
        m3 = Merge3(base_lines, this_lines, other_lines)
 
615
        start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
 
616
        if self.show_base is True:
 
617
            base_marker = '|' * 7
 
618
        else:
 
619
            base_marker = None
 
620
 
 
621
        def iter_merge3(retval):
 
622
            retval["text_conflicts"] = False
 
623
            for line in m3.merge_lines(name_a = "TREE", 
 
624
                                       name_b = "MERGE-SOURCE", 
 
625
                                       name_base = "BASE-REVISION",
 
626
                                       start_marker=start_marker, 
 
627
                                       base_marker=base_marker,
 
628
                                       reprocess=self.reprocess):
 
629
                if line.startswith(start_marker):
 
630
                    retval["text_conflicts"] = True
 
631
                    yield line.replace(start_marker, '<' * 7)
 
632
                else:
 
633
                    yield line
 
634
        retval = {}
 
635
        merge3_iterator = iter_merge3(retval)
 
636
        self.tt.create_file(merge3_iterator, trans_id)
 
637
        if retval["text_conflicts"] is True:
 
638
            self._raw_conflicts.append(('text conflict', trans_id))
 
639
            name = self.tt.final_name(trans_id)
 
640
            parent_id = self.tt.final_parent(trans_id)
 
641
            file_group = self._dump_conflicts(name, parent_id, file_id, 
 
642
                                              this_lines, base_lines,
 
643
                                              other_lines)
 
644
            file_group.append(trans_id)
 
645
 
 
646
    def _dump_conflicts(self, name, parent_id, file_id, this_lines=None, 
 
647
                        base_lines=None, other_lines=None, set_version=False,
 
648
                        no_base=False):
 
649
        """Emit conflict files.
 
650
        If this_lines, base_lines, or other_lines are omitted, they will be
 
651
        determined automatically.  If set_version is true, the .OTHER, .THIS
 
652
        or .BASE (in that order) will be created as versioned files.
 
653
        """
 
654
        data = [('OTHER', self.other_tree, other_lines), 
 
655
                ('THIS', self.this_tree, this_lines)]
 
656
        if not no_base:
 
657
            data.append(('BASE', self.base_tree, base_lines))
 
658
        versioned = False
 
659
        file_group = []
 
660
        for suffix, tree, lines in data:
 
661
            if file_id in tree:
 
662
                trans_id = self._conflict_file(name, parent_id, tree, file_id,
 
663
                                               suffix, lines)
 
664
                file_group.append(trans_id)
 
665
                if set_version and not versioned:
 
666
                    self.tt.version_file(file_id, trans_id)
 
667
                    versioned = True
 
668
        return file_group
 
669
           
 
670
    def _conflict_file(self, name, parent_id, tree, file_id, suffix, 
 
671
                       lines=None):
 
672
        """Emit a single conflict file."""
 
673
        name = name + '.' + suffix
 
674
        trans_id = self.tt.create_path(name, parent_id)
 
675
        entry = tree.inventory[file_id]
 
676
        create_by_entry(self.tt, entry, tree, trans_id, lines)
 
677
        return trans_id
 
678
 
 
679
    def merge_executable(self, file_id, file_status):
 
680
        """Perform a merge on the execute bit."""
 
681
        if file_status == "deleted":
 
682
            return
 
683
        trans_id = self.tt.trans_id_file_id(file_id)
 
684
        try:
 
685
            if self.tt.final_kind(trans_id) != "file":
 
686
                return
 
687
        except NoSuchFile:
 
688
            return
 
689
        winner = self.scalar_three_way(self.this_tree, self.base_tree, 
 
690
                                       self.other_tree, file_id, 
 
691
                                       self.executable)
 
692
        if winner == "conflict":
 
693
        # There must be a None in here, if we have a conflict, but we
 
694
        # need executability since file status was not deleted.
 
695
            if self.other_tree.is_executable(file_id) is None:
 
696
                winner = "this"
 
697
            else:
 
698
                winner = "other"
 
699
        if winner == "this":
 
700
            if file_status == "modified":
 
701
                executability = self.this_tree.is_executable(file_id)
 
702
                if executability is not None:
 
703
                    trans_id = self.tt.trans_id_file_id(file_id)
 
704
                    self.tt.set_executability(executability, trans_id)
 
705
        else:
 
706
            assert winner == "other"
 
707
            if file_id in self.other_tree:
 
708
                executability = self.other_tree.is_executable(file_id)
 
709
            elif file_id in self.this_tree:
 
710
                executability = self.this_tree.is_executable(file_id)
 
711
            elif file_id in self.base_tree:
 
712
                executability = self.base_tree.is_executable(file_id)
 
713
            if executability is not None:
 
714
                trans_id = self.tt.trans_id_file_id(file_id)
 
715
                self.tt.set_executability(executability, trans_id)
 
716
 
 
717
    def cook_conflicts(self, fs_conflicts):
 
718
        """Convert all conflicts into a form that doesn't depend on trans_id"""
 
719
        from conflicts import Conflict
 
720
        name_conflicts = {}
 
721
        self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
 
722
        fp = FinalPaths(self.tt)
 
723
        for conflict in self._raw_conflicts:
 
724
            conflict_type = conflict[0]
 
725
            if conflict_type in ('name conflict', 'parent conflict'):
 
726
                trans_id = conflict[1]
 
727
                conflict_args = conflict[2:]
 
728
                if trans_id not in name_conflicts:
 
729
                    name_conflicts[trans_id] = {}
 
730
                unique_add(name_conflicts[trans_id], conflict_type, 
 
731
                           conflict_args)
 
732
            if conflict_type == 'contents conflict':
 
733
                for trans_id in conflict[1]:
 
734
                    file_id = self.tt.final_file_id(trans_id)
 
735
                    if file_id is not None:
 
736
                        break
 
737
                path = fp.get_path(trans_id)
 
738
                for suffix in ('.BASE', '.THIS', '.OTHER'):
 
739
                    if path.endswith(suffix):
 
740
                        path = path[:-len(suffix)]
 
741
                        break
 
742
                c = Conflict.factory(conflict_type, path=path, file_id=file_id)
 
743
                self.cooked_conflicts.append(c)
 
744
            if conflict_type == 'text conflict':
 
745
                trans_id = conflict[1]
 
746
                path = fp.get_path(trans_id)
 
747
                file_id = self.tt.final_file_id(trans_id)
 
748
                c = Conflict.factory(conflict_type, path=path, file_id=file_id)
 
749
                self.cooked_conflicts.append(c)
 
750
 
 
751
        for trans_id, conflicts in name_conflicts.iteritems():
 
752
            try:
 
753
                this_parent, other_parent = conflicts['parent conflict']
 
754
                assert this_parent != other_parent
 
755
            except KeyError:
 
756
                this_parent = other_parent = \
 
757
                    self.tt.final_file_id(self.tt.final_parent(trans_id))
 
758
            try:
 
759
                this_name, other_name = conflicts['name conflict']
 
760
                assert this_name != other_name
 
761
            except KeyError:
 
762
                this_name = other_name = self.tt.final_name(trans_id)
 
763
            other_path = fp.get_path(trans_id)
 
764
            if this_parent is not None:
 
765
                this_parent_path = \
 
766
                    fp.get_path(self.tt.trans_id_file_id(this_parent))
 
767
                this_path = pathjoin(this_parent_path, this_name)
 
768
            else:
 
769
                this_path = "<deleted>"
 
770
            file_id = self.tt.final_file_id(trans_id)
 
771
            c = Conflict.factory('path conflict', path=this_path,
 
772
                                 conflict_path=other_path, file_id=file_id)
 
773
            self.cooked_conflicts.append(c)
 
774
        self.cooked_conflicts.sort(key=Conflict.sort_key)
 
775
 
 
776
 
 
777
class WeaveMerger(Merge3Merger):
 
778
    """Three-way tree merger, text weave merger."""
 
779
    supports_reprocess = True
 
780
    supports_show_base = False
 
781
 
 
782
    def __init__(self, working_tree, this_tree, base_tree, other_tree, 
 
783
                 interesting_ids=None, pb=DummyProgress(), pp=None,
 
784
                 reprocess=False):
 
785
        self.this_revision_tree = self._get_revision_tree(this_tree)
 
786
        self.other_revision_tree = self._get_revision_tree(other_tree)
 
787
        super(WeaveMerger, self).__init__(working_tree, this_tree, 
 
788
                                          base_tree, other_tree, 
 
789
                                          interesting_ids=interesting_ids, 
 
790
                                          pb=pb, pp=pp, reprocess=reprocess)
 
791
 
 
792
    def _get_revision_tree(self, tree):
 
793
        """Return a revision tree releated to this tree.
 
794
        If the tree is a WorkingTree, the basis will be returned.
 
795
        """
 
796
        if getattr(tree, 'get_weave', False) is False:
 
797
            # If we have a WorkingTree, try using the basis
 
798
            return tree.branch.basis_tree()
 
799
        else:
 
800
            return tree
 
801
 
 
802
    def _check_file(self, file_id):
 
803
        """Check that the revision tree's version of the file matches."""
 
804
        for tree, rt in ((self.this_tree, self.this_revision_tree), 
 
805
                         (self.other_tree, self.other_revision_tree)):
 
806
            if rt is tree:
 
807
                continue
 
808
            if tree.get_file_sha1(file_id) != rt.get_file_sha1(file_id):
 
809
                raise WorkingTreeNotRevision(self.this_tree)
 
810
 
 
811
    def _merged_lines(self, file_id):
 
812
        """Generate the merged lines.
 
813
        There is no distinction between lines that are meant to contain <<<<<<<
 
814
        and conflicts.
 
815
        """
 
816
        weave = self.this_revision_tree.get_weave(file_id)
 
817
        this_revision_id = self.this_revision_tree.inventory[file_id].revision
 
818
        other_revision_id = \
 
819
            self.other_revision_tree.inventory[file_id].revision
 
820
        wm = WeaveMerge(weave, this_revision_id, other_revision_id, 
 
821
                        '<<<<<<< TREE\n', '>>>>>>> MERGE-SOURCE\n')
 
822
        return wm.merge_lines(self.reprocess)
 
823
 
 
824
    def text_merge(self, file_id, trans_id):
 
825
        """Perform a (weave) text merge for a given file and file-id.
 
826
        If conflicts are encountered, .THIS and .OTHER files will be emitted,
 
827
        and a conflict will be noted.
 
828
        """
 
829
        self._check_file(file_id)
 
830
        lines, conflicts = self._merged_lines(file_id)
 
831
        lines = list(lines)
 
832
        # Note we're checking whether the OUTPUT is binary in this case, 
 
833
        # because we don't want to get into weave merge guts.
 
834
        check_text_lines(lines)
 
835
        self.tt.create_file(lines, trans_id)
 
836
        if conflicts:
 
837
            self._raw_conflicts.append(('text conflict', trans_id))
 
838
            name = self.tt.final_name(trans_id)
 
839
            parent_id = self.tt.final_parent(trans_id)
 
840
            file_group = self._dump_conflicts(name, parent_id, file_id, 
 
841
                                              no_base=True)
 
842
            file_group.append(trans_id)
 
843
 
 
844
 
 
845
class Diff3Merger(Merge3Merger):
 
846
    """Three-way merger using external diff3 for text merging"""
 
847
    def dump_file(self, temp_dir, name, tree, file_id):
 
848
        out_path = pathjoin(temp_dir, name)
 
849
        out_file = file(out_path, "wb")
 
850
        in_file = tree.get_file(file_id)
 
851
        for line in in_file:
 
852
            out_file.write(line)
 
853
        return out_path
 
854
 
 
855
    def text_merge(self, file_id, trans_id):
 
856
        """Perform a diff3 merge using a specified file-id and trans-id.
 
857
        If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
 
858
        will be dumped, and a will be conflict noted.
 
859
        """
 
860
        import bzrlib.patch
 
861
        temp_dir = mkdtemp(prefix="bzr-")
 
862
        try:
 
863
            new_file = pathjoin(temp_dir, "new")
 
864
            this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
 
865
            base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
 
866
            other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
 
867
            status = bzrlib.patch.diff3(new_file, this, base, other)
 
868
            if status not in (0, 1):
 
869
                raise BzrError("Unhandled diff3 exit code")
 
870
            self.tt.create_file(file(new_file, "rb"), trans_id)
 
871
            if status == 1:
 
872
                name = self.tt.final_name(trans_id)
 
873
                parent_id = self.tt.final_parent(trans_id)
 
874
                self._dump_conflicts(name, parent_id, file_id)
 
875
            self._raw_conflicts.append(('text conflict', trans_id))
 
876
        finally:
 
877
            rmtree(temp_dir)
 
878
 
 
879
 
 
880
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
 
881
                backup_files=False, 
 
882
                merge_type=Merge3Merger, 
 
883
                interesting_ids=None, 
 
884
                show_base=False, 
 
885
                reprocess=False, 
 
886
                other_rev_id=None,
 
887
                interesting_files=None,
 
888
                this_tree=None,
 
889
                pb=DummyProgress()):
 
890
    """Primary interface for merging. 
 
891
 
 
892
        typical use is probably 
 
893
        'merge_inner(branch, branch.get_revision_tree(other_revision),
 
894
                     branch.get_revision_tree(base_revision))'
 
895
        """
 
896
    if this_tree is None:
 
897
        warn("bzrlib.merge.merge_inner requires a this_tree parameter as of "
 
898
             "bzrlib version 0.8.",
 
899
             DeprecationWarning,
 
900
             stacklevel=2)
 
901
        this_tree = this_branch.bzrdir.open_workingtree()
 
902
    merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree, 
 
903
                    pb=pb)
 
904
    merger.backup_files = backup_files
 
905
    merger.merge_type = merge_type
 
906
    merger.interesting_ids = interesting_ids
 
907
    merger.ignore_zero = ignore_zero
 
908
    if interesting_files:
 
909
        assert not interesting_ids, ('Only supply interesting_ids'
 
910
                                     ' or interesting_files')
 
911
        merger._set_interesting_files(interesting_files)
 
912
    merger.show_base = show_base 
 
913
    merger.reprocess = reprocess
 
914
    merger.other_rev_id = other_rev_id
 
915
    merger.other_basis = other_rev_id
 
916
    return merger.do_merge()
 
917
 
 
918
 
 
919
merge_types = {     "merge3": (Merge3Merger, "Native diff3-style merge"), 
 
920
                     "diff3": (Diff3Merger,  "Merge using external diff3"),
 
921
                     'weave': (WeaveMerger, "Weave-based merge")
546
922
              }