~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: Robert Collins
  • Date: 2006-05-24 08:14:45 UTC
  • mfrom: (1725.1.1 benchmark)
  • mto: (1725.2.6 commit)
  • mto: This revision was merged to the branch mainline in revision 1729.
  • Revision ID: robertc@robertcollins.net-20060524081445-c046b4406ffc8dfa
(rbc)Merge in benchmark --lsprof-timed lsprofiling feature. (Robert Collins, Martin Pool).

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