~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: Martin Pool
  • Date: 2005-05-03 08:00:27 UTC
  • Revision ID: mbp@sourcefrog.net-20050503080027-908edb5b39982198
doc

Show diffs side-by-side

added added

removed removed

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