/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

added ianc tweaks to tbzr strategy doc

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005-2010 Canonical Ltd
 
1
# Copyright (C) 2005, 2006 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
 
17
 
 
18
import os
 
19
import errno
17
20
import warnings
18
21
 
19
 
from bzrlib.lazy_import import lazy_import
20
 
lazy_import(globals(), """
21
22
from bzrlib import (
22
 
    branch as _mod_branch,
23
 
    conflicts as _mod_conflicts,
24
23
    debug,
25
24
    errors,
26
 
    graph as _mod_graph,
27
 
    merge3,
28
25
    osutils,
29
26
    patiencediff,
 
27
    registry,
30
28
    revision as _mod_revision,
31
 
    textfile,
32
 
    trace,
33
 
    transform,
34
 
    tree as _mod_tree,
35
 
    tsort,
36
 
    ui,
37
 
    versionedfile,
38
 
    )
39
 
from bzrlib.cleanup import OperationWithCleanups
40
 
""")
41
 
from bzrlib import (
42
 
    decorators,
43
 
    hooks,
44
 
    )
45
 
from bzrlib.symbol_versioning import (
46
 
    deprecated_in,
47
 
    deprecated_method,
48
 
    )
 
29
    )
 
30
from bzrlib.branch import Branch
 
31
from bzrlib.conflicts import ConflictList, Conflict
 
32
from bzrlib.errors import (BzrCommandError,
 
33
                           BzrError,
 
34
                           NoCommonAncestor,
 
35
                           NoCommits,
 
36
                           NoSuchRevision,
 
37
                           NoSuchFile,
 
38
                           NotBranchError,
 
39
                           NotVersionedError,
 
40
                           UnrelatedBranches,
 
41
                           UnsupportedOperation,
 
42
                           WorkingTreeNotRevision,
 
43
                           BinaryFile,
 
44
                           )
 
45
from bzrlib.merge3 import Merge3
 
46
from bzrlib.osutils import rename, pathjoin
 
47
from progress import DummyProgress, ProgressPhase
 
48
from bzrlib.revision import (NULL_REVISION, ensure_null)
 
49
from bzrlib.textfile import check_text_lines
 
50
from bzrlib.trace import mutter, warning, note, is_quiet
 
51
from bzrlib.transform import (TransformPreview, TreeTransform,
 
52
                              resolve_conflicts, cook_conflicts,
 
53
                              conflict_pass, FinalPaths, create_by_entry,
 
54
                              unique_add, ROOT_PARENT)
 
55
from bzrlib.versionedfile import PlanWeaveMerge
 
56
from bzrlib import ui
 
57
 
49
58
# TODO: Report back as changes are merged in
50
59
 
51
60
 
52
61
def transform_tree(from_tree, to_tree, interesting_ids=None):
53
 
    from_tree.lock_tree_write()
54
 
    operation = OperationWithCleanups(merge_inner)
55
 
    operation.add_cleanup(from_tree.unlock)
56
 
    operation.run_simple(from_tree.branch, to_tree, from_tree,
57
 
        ignore_zero=True, interesting_ids=interesting_ids, this_tree=from_tree)
58
 
 
59
 
 
60
 
class MergeHooks(hooks.Hooks):
61
 
 
62
 
    def __init__(self):
63
 
        hooks.Hooks.__init__(self)
64
 
        self.create_hook(hooks.HookPoint('merge_file_content',
65
 
            "Called with a bzrlib.merge.Merger object to create a per file "
66
 
            "merge object when starting a merge. "
67
 
            "Should return either None or a subclass of "
68
 
            "``bzrlib.merge.AbstractPerFileMerger``. "
69
 
            "Such objects will then be called per file "
70
 
            "that needs to be merged (including when one "
71
 
            "side has deleted the file and the other has changed it). "
72
 
            "See the AbstractPerFileMerger API docs for details on how it is "
73
 
            "used by merge.",
74
 
            (2, 1), None))
75
 
 
76
 
 
77
 
class AbstractPerFileMerger(object):
78
 
    """PerFileMerger objects are used by plugins extending merge for bzrlib.
79
 
 
80
 
    See ``bzrlib.plugins.news_merge.news_merge`` for an example concrete class.
81
 
    
82
 
    :ivar merger: The Merge3Merger performing the merge.
83
 
    """
84
 
 
85
 
    def __init__(self, merger):
86
 
        """Create a PerFileMerger for use with merger."""
87
 
        self.merger = merger
88
 
 
89
 
    def merge_contents(self, merge_params):
90
 
        """Attempt to merge the contents of a single file.
91
 
        
92
 
        :param merge_params: A bzrlib.merge.MergeHookParams
93
 
        :return : A tuple of (status, chunks), where status is one of
94
 
            'not_applicable', 'success', 'conflicted', or 'delete'.  If status
95
 
            is 'success' or 'conflicted', then chunks should be an iterable of
96
 
            strings for the new file contents.
97
 
        """
98
 
        return ('not applicable', None)
99
 
 
100
 
 
101
 
class PerFileMerger(AbstractPerFileMerger):
102
 
    """Merge individual files when self.file_matches returns True.
103
 
 
104
 
    This class is intended to be subclassed.  The file_matches and
105
 
    merge_matching methods should be overridden with concrete implementations.
106
 
    """
107
 
 
108
 
    def file_matches(self, params):
109
 
        """Return True if merge_matching should be called on this file.
110
 
 
111
 
        Only called with merges of plain files with no clear winner.
112
 
 
113
 
        Subclasses must override this.
114
 
        """
115
 
        raise NotImplementedError(self.file_matches)
116
 
 
117
 
    def get_filename(self, params, tree):
118
 
        """Lookup the filename (i.e. basename, not path), given a Tree (e.g.
119
 
        self.merger.this_tree) and a MergeHookParams.
120
 
        """
121
 
        return osutils.basename(tree.id2path(params.file_id))
122
 
 
123
 
    def get_filepath(self, params, tree):
124
 
        """Calculate the path to the file in a tree.
125
 
 
126
 
        :param params: A MergeHookParams describing the file to merge
127
 
        :param tree: a Tree, e.g. self.merger.this_tree.
128
 
        """
129
 
        return tree.id2path(params.file_id)
130
 
 
131
 
    def merge_contents(self, params):
132
 
        """Merge the contents of a single file."""
133
 
        # Check whether this custom merge logic should be used.
134
 
        if (
135
 
            # OTHER is a straight winner, rely on default merge.
136
 
            params.winner == 'other' or
137
 
            # THIS and OTHER aren't both files.
138
 
            not params.is_file_merge() or
139
 
            # The filename doesn't match *.xml
140
 
            not self.file_matches(params)):
141
 
            return 'not_applicable', None
142
 
        return self.merge_matching(params)
143
 
 
144
 
    def merge_matching(self, params):
145
 
        """Merge the contents of a single file that has matched the criteria
146
 
        in PerFileMerger.merge_contents (is a conflict, is a file,
147
 
        self.file_matches is True).
148
 
 
149
 
        Subclasses must override this.
150
 
        """
151
 
        raise NotImplementedError(self.merge_matching)
152
 
 
153
 
 
154
 
class ConfigurableFileMerger(PerFileMerger):
155
 
    """Merge individual files when configured via a .conf file.
156
 
 
157
 
    This is a base class for concrete custom file merging logic. Concrete
158
 
    classes should implement ``merge_text``.
159
 
 
160
 
    See ``bzrlib.plugins.news_merge.news_merge`` for an example concrete class.
161
 
    
162
 
    :ivar affected_files: The configured file paths to merge.
163
 
 
164
 
    :cvar name_prefix: The prefix to use when looking up configuration
165
 
        details. <name_prefix>_merge_files describes the files targeted by the
166
 
        hook for example.
167
 
        
168
 
    :cvar default_files: The default file paths to merge when no configuration
169
 
        is present.
170
 
    """
171
 
 
172
 
    name_prefix = None
173
 
    default_files = None
174
 
 
175
 
    def __init__(self, merger):
176
 
        super(ConfigurableFileMerger, self).__init__(merger)
177
 
        self.affected_files = None
178
 
        self.default_files = self.__class__.default_files or []
179
 
        self.name_prefix = self.__class__.name_prefix
180
 
        if self.name_prefix is None:
181
 
            raise ValueError("name_prefix must be set.")
182
 
 
183
 
    def file_matches(self, params):
184
 
        """Check whether the file should call the merge hook.
185
 
 
186
 
        <name_prefix>_merge_files configuration variable is a list of files
187
 
        that should use the hook.
188
 
        """
189
 
        affected_files = self.affected_files
190
 
        if affected_files is None:
191
 
            config = self.merger.this_branch.get_config()
192
 
            # Until bzr provides a better policy for caching the config, we
193
 
            # just add the part we're interested in to the params to avoid
194
 
            # reading the config files repeatedly (bazaar.conf, location.conf,
195
 
            # branch.conf).
196
 
            config_key = self.name_prefix + '_merge_files'
197
 
            affected_files = config.get_user_option_as_list(config_key)
198
 
            if affected_files is None:
199
 
                # If nothing was specified in the config, use the default.
200
 
                affected_files = self.default_files
201
 
            self.affected_files = affected_files
202
 
        if affected_files:
203
 
            filepath = self.get_filepath(params, self.merger.this_tree)
204
 
            if filepath in affected_files:
205
 
                return True
206
 
        return False
207
 
 
208
 
    def merge_matching(self, params):
209
 
        return self.merge_text(params)
210
 
 
211
 
    def merge_text(self, params):
212
 
        """Merge the byte contents of a single file.
213
 
 
214
 
        This is called after checking that the merge should be performed in
215
 
        merge_contents, and it should behave as per
216
 
        ``bzrlib.merge.AbstractPerFileMerger.merge_contents``.
217
 
        """
218
 
        raise NotImplementedError(self.merge_text)
219
 
 
220
 
 
221
 
class MergeHookParams(object):
222
 
    """Object holding parameters passed to merge_file_content hooks.
223
 
 
224
 
    There are some fields hooks can access:
225
 
 
226
 
    :ivar file_id: the file ID of the file being merged
227
 
    :ivar trans_id: the transform ID for the merge of this file
228
 
    :ivar this_kind: kind of file_id in 'this' tree
229
 
    :ivar other_kind: kind of file_id in 'other' tree
230
 
    :ivar winner: one of 'this', 'other', 'conflict'
231
 
    """
232
 
 
233
 
    def __init__(self, merger, file_id, trans_id, this_kind, other_kind,
234
 
            winner):
235
 
        self._merger = merger
236
 
        self.file_id = file_id
237
 
        self.trans_id = trans_id
238
 
        self.this_kind = this_kind
239
 
        self.other_kind = other_kind
240
 
        self.winner = winner
241
 
 
242
 
    def is_file_merge(self):
243
 
        """True if this_kind and other_kind are both 'file'."""
244
 
        return self.this_kind == 'file' and self.other_kind == 'file'
245
 
 
246
 
    @decorators.cachedproperty
247
 
    def base_lines(self):
248
 
        """The lines of the 'base' version of the file."""
249
 
        return self._merger.get_lines(self._merger.base_tree, self.file_id)
250
 
 
251
 
    @decorators.cachedproperty
252
 
    def this_lines(self):
253
 
        """The lines of the 'this' version of the file."""
254
 
        return self._merger.get_lines(self._merger.this_tree, self.file_id)
255
 
 
256
 
    @decorators.cachedproperty
257
 
    def other_lines(self):
258
 
        """The lines of the 'other' version of the file."""
259
 
        return self._merger.get_lines(self._merger.other_tree, self.file_id)
 
62
    merge_inner(from_tree.branch, to_tree, from_tree, ignore_zero=True,
 
63
                interesting_ids=interesting_ids, this_tree=from_tree)
260
64
 
261
65
 
262
66
class Merger(object):
263
 
 
264
 
    hooks = MergeHooks()
265
 
 
266
67
    def __init__(self, this_branch, other_tree=None, base_tree=None,
267
 
                 this_tree=None, pb=None, change_reporter=None,
 
68
                 this_tree=None, pb=DummyProgress(), change_reporter=None,
268
69
                 recurse='down', revision_graph=None):
269
70
        object.__init__(self)
270
71
        self.this_branch = this_branch
283
84
        self.interesting_files = None
284
85
        self.show_base = False
285
86
        self.reprocess = False
286
 
        if pb is not None:
287
 
            warnings.warn("pb parameter to Merger() is deprecated and ignored")
 
87
        self._pb = pb
288
88
        self.pp = None
289
89
        self.recurse = recurse
290
90
        self.change_reporter = change_reporter
292
92
        self._revision_graph = revision_graph
293
93
        self._base_is_ancestor = None
294
94
        self._base_is_other_ancestor = None
295
 
        self._is_criss_cross = None
296
 
        self._lca_trees = None
297
 
 
298
 
    def cache_trees_with_revision_ids(self, trees):
299
 
        """Cache any tree in trees if it has a revision_id."""
300
 
        for maybe_tree in trees:
301
 
            if maybe_tree is None:
302
 
                continue
303
 
            try:
304
 
                rev_id = maybe_tree.get_revision_id()
305
 
            except AttributeError:
306
 
                continue
307
 
            self._cached_trees[rev_id] = maybe_tree
308
95
 
309
96
    @property
310
97
    def revision_graph(self):
338
125
                                      _set_base_is_other_ancestor)
339
126
 
340
127
    @staticmethod
341
 
    def from_uncommitted(tree, other_tree, pb=None, base_tree=None):
 
128
    def from_uncommitted(tree, other_tree, pb):
342
129
        """Return a Merger for uncommitted changes in other_tree.
343
130
 
344
131
        :param tree: The tree to merge into
345
132
        :param other_tree: The tree to get uncommitted changes from
346
133
        :param pb: A progress indicator
347
 
        :param base_tree: The basis to use for the merge.  If unspecified,
348
 
            other_tree.basis_tree() will be used.
349
134
        """
350
 
        if base_tree is None:
351
 
            base_tree = other_tree.basis_tree()
352
 
        merger = Merger(tree.branch, other_tree, base_tree, tree, pb)
 
135
        merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,
 
136
                        pb)
353
137
        merger.base_rev_id = merger.base_tree.get_revision_id()
354
138
        merger.other_rev_id = None
355
139
        merger.other_basis = merger.base_rev_id
367
151
        base_revision_id, other_revision_id, verified =\
368
152
            mergeable.get_merge_request(tree.branch.repository)
369
153
        revision_graph = tree.branch.repository.get_graph()
370
 
        if base_revision_id is not None:
371
 
            if (base_revision_id != _mod_revision.NULL_REVISION and
372
 
                revision_graph.is_ancestor(
373
 
                base_revision_id, tree.branch.last_revision())):
374
 
                base_revision_id = None
375
 
            else:
376
 
                trace.warning('Performing cherrypick')
 
154
        if (base_revision_id != _mod_revision.NULL_REVISION and
 
155
            revision_graph.is_ancestor(
 
156
            base_revision_id, tree.branch.last_revision())):
 
157
            base_revision_id = None
 
158
        else:
 
159
            warning('Performing cherrypick')
377
160
        merger = klass.from_revision_ids(pb, tree, other_revision_id,
378
161
                                         base_revision_id, revision_graph=
379
162
                                         revision_graph)
381
164
 
382
165
    @staticmethod
383
166
    def from_revision_ids(pb, tree, other, base=None, other_branch=None,
384
 
                          base_branch=None, revision_graph=None,
385
 
                          tree_branch=None):
 
167
                          base_branch=None, revision_graph=None):
386
168
        """Return a Merger for revision-ids.
387
169
 
388
 
        :param pb: A progress indicator
389
170
        :param tree: The tree to merge changes into
390
171
        :param other: The revision-id to use as OTHER
391
172
        :param base: The revision-id to use as BASE.  If not specified, will
396
177
            not supplied, other_branch or tree.branch will be used.
397
178
        :param revision_graph: If you have a revision_graph precomputed, pass
398
179
            it in, otherwise it will be created for you.
399
 
        :param tree_branch: The branch associated with tree.  If not supplied,
400
 
            tree.branch will be used.
 
180
        :param pb: A progress indicator
401
181
        """
402
 
        if tree_branch is None:
403
 
            tree_branch = tree.branch
404
 
        merger = Merger(tree_branch, this_tree=tree, pb=pb,
 
182
        merger = Merger(tree.branch, this_tree=tree, pb=pb,
405
183
                        revision_graph=revision_graph)
406
184
        if other_branch is None:
407
185
            other_branch = tree.branch
431
209
        if revno is None:
432
210
            tree = workingtree.WorkingTree.open_containing(location)[0]
433
211
            return tree.branch, tree
434
 
        branch = _mod_branch.Branch.open_containing(
435
 
            location, possible_transports)[0]
 
212
        branch = Branch.open_containing(location, possible_transports)[0]
436
213
        if revno == -1:
437
214
            revision_id = branch.last_revision()
438
215
        else:
439
216
            revision_id = branch.get_rev_id(revno)
440
 
        revision_id = _mod_revision.ensure_null(revision_id)
 
217
        revision_id = ensure_null(revision_id)
441
218
        return branch, self.revision_tree(revision_id, branch)
442
219
 
443
 
    @deprecated_method(deprecated_in((2, 1, 0)))
444
220
    def ensure_revision_trees(self):
445
221
        if self.this_revision_tree is None:
446
222
            self.this_basis_tree = self.revision_tree(self.this_basis)
449
225
 
450
226
        if self.other_rev_id is None:
451
227
            other_basis_tree = self.revision_tree(self.other_basis)
452
 
            if other_basis_tree.has_changes(self.other_tree):
453
 
                raise errors.WorkingTreeNotRevision(self.this_tree)
 
228
            changes = other_basis_tree.changes_from(self.other_tree)
 
229
            if changes.has_changed():
 
230
                raise WorkingTreeNotRevision(self.this_tree)
454
231
            other_rev_id = self.other_basis
455
232
            self.other_tree = other_basis_tree
456
233
 
457
 
    @deprecated_method(deprecated_in((2, 1, 0)))
458
234
    def file_revisions(self, file_id):
459
235
        self.ensure_revision_trees()
460
236
        def get_id(tree, file_id):
463
239
        if self.this_rev_id is None:
464
240
            if self.this_basis_tree.get_file_sha1(file_id) != \
465
241
                self.this_tree.get_file_sha1(file_id):
466
 
                raise errors.WorkingTreeNotRevision(self.this_tree)
 
242
                raise WorkingTreeNotRevision(self.this_tree)
467
243
 
468
244
        trees = (self.this_basis_tree, self.other_tree)
469
245
        return [get_id(tree, file_id) for tree in trees]
470
246
 
471
 
    @deprecated_method(deprecated_in((2, 1, 0)))
472
247
    def check_basis(self, check_clean, require_commits=True):
473
248
        if self.this_basis is None and require_commits is True:
474
 
            raise errors.BzrCommandError(
475
 
                "This branch has no commits."
476
 
                " (perhaps you would prefer 'bzr pull')")
 
249
            raise BzrCommandError("This branch has no commits."
 
250
                                  " (perhaps you would prefer 'bzr pull')")
477
251
        if check_clean:
478
252
            self.compare_basis()
479
253
            if self.this_basis != self.this_rev_id:
480
254
                raise errors.UncommittedChanges(self.this_tree)
481
255
 
482
 
    @deprecated_method(deprecated_in((2, 1, 0)))
483
256
    def compare_basis(self):
484
257
        try:
485
258
            basis_tree = self.revision_tree(self.this_tree.last_revision())
486
 
        except errors.NoSuchRevision:
 
259
        except errors.RevisionNotPresent:
487
260
            basis_tree = self.this_tree.basis_tree()
488
 
        if not self.this_tree.has_changes(basis_tree):
 
261
        changes = self.this_tree.changes_from(basis_tree)
 
262
        if not changes.has_changed():
489
263
            self.this_rev_id = self.this_basis
490
264
 
491
265
    def set_interesting_files(self, file_list):
492
266
        self.interesting_files = file_list
493
267
 
494
268
    def set_pending(self):
495
 
        if (not self.base_is_ancestor or not self.base_is_other_ancestor
496
 
            or self.other_rev_id is None):
 
269
        if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:
497
270
            return
498
271
        self._add_parent()
499
272
 
500
273
    def _add_parent(self):
501
274
        new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
502
275
        new_parent_trees = []
503
 
        operation = OperationWithCleanups(self.this_tree.set_parent_trees)
504
276
        for revision_id in new_parents:
505
277
            try:
506
278
                tree = self.revision_tree(revision_id)
507
 
            except errors.NoSuchRevision:
 
279
            except errors.RevisionNotPresent:
508
280
                tree = None
509
281
            else:
510
282
                tree.lock_read()
511
 
                operation.add_cleanup(tree.unlock)
512
283
            new_parent_trees.append((revision_id, tree))
513
 
        operation.run_simple(new_parent_trees, allow_leftmost_as_ghost=True)
 
284
        try:
 
285
            self.this_tree.set_parent_trees(new_parent_trees,
 
286
                                            allow_leftmost_as_ghost=True)
 
287
        finally:
 
288
            for _revision_id, tree in new_parent_trees:
 
289
                if tree is not None:
 
290
                    tree.unlock()
514
291
 
515
292
    def set_other(self, other_revision, possible_transports=None):
516
293
        """Set the revision and tree to merge from.
525
302
            self.other_rev_id = _mod_revision.ensure_null(
526
303
                self.other_branch.last_revision())
527
304
            if _mod_revision.is_null(self.other_rev_id):
528
 
                raise errors.NoCommits(self.other_branch)
 
305
                raise NoCommits(self.other_branch)
529
306
            self.other_basis = self.other_rev_id
530
307
        elif other_revision[1] is not None:
531
308
            self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
534
311
            self.other_rev_id = None
535
312
            self.other_basis = self.other_branch.last_revision()
536
313
            if self.other_basis is None:
537
 
                raise errors.NoCommits(self.other_branch)
 
314
                raise NoCommits(self.other_branch)
538
315
        if self.other_rev_id is not None:
539
316
            self._cached_trees[self.other_rev_id] = self.other_tree
540
317
        self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)
567
344
            target.fetch(source, revision_id)
568
345
 
569
346
    def find_base(self):
570
 
        revisions = [_mod_revision.ensure_null(self.this_basis),
571
 
                     _mod_revision.ensure_null(self.other_basis)]
572
 
        if _mod_revision.NULL_REVISION in revisions:
573
 
            self.base_rev_id = _mod_revision.NULL_REVISION
574
 
            self.base_tree = self.revision_tree(self.base_rev_id)
575
 
            self._is_criss_cross = False
 
347
        revisions = [ensure_null(self.this_basis),
 
348
                     ensure_null(self.other_basis)]
 
349
        if NULL_REVISION in revisions:
 
350
            self.base_rev_id = NULL_REVISION
576
351
        else:
577
 
            lcas = self.revision_graph.find_lca(revisions[0], revisions[1])
578
 
            self._is_criss_cross = False
579
 
            if len(lcas) == 0:
580
 
                self.base_rev_id = _mod_revision.NULL_REVISION
581
 
            elif len(lcas) == 1:
582
 
                self.base_rev_id = list(lcas)[0]
583
 
            else: # len(lcas) > 1
584
 
                if len(lcas) > 2:
585
 
                    # find_unique_lca can only handle 2 nodes, so we have to
586
 
                    # start back at the beginning. It is a shame to traverse
587
 
                    # the graph again, but better than re-implementing
588
 
                    # find_unique_lca.
589
 
                    self.base_rev_id = self.revision_graph.find_unique_lca(
590
 
                                            revisions[0], revisions[1])
591
 
                else:
592
 
                    self.base_rev_id = self.revision_graph.find_unique_lca(
593
 
                                            *lcas)
594
 
                self._is_criss_cross = True
595
 
            if self.base_rev_id == _mod_revision.NULL_REVISION:
596
 
                raise errors.UnrelatedBranches()
597
 
            if self._is_criss_cross:
598
 
                trace.warning('Warning: criss-cross merge encountered.  See bzr'
599
 
                              ' help criss-cross.')
600
 
                trace.mutter('Criss-cross lcas: %r' % lcas)
601
 
                interesting_revision_ids = [self.base_rev_id]
602
 
                interesting_revision_ids.extend(lcas)
603
 
                interesting_trees = dict((t.get_revision_id(), t)
604
 
                    for t in self.this_branch.repository.revision_trees(
605
 
                        interesting_revision_ids))
606
 
                self._cached_trees.update(interesting_trees)
607
 
                self.base_tree = interesting_trees.pop(self.base_rev_id)
608
 
                sorted_lca_keys = self.revision_graph.find_merge_order(
609
 
                    revisions[0], lcas)
610
 
                self._lca_trees = [interesting_trees[key]
611
 
                                   for key in sorted_lca_keys]
612
 
            else:
613
 
                self.base_tree = self.revision_tree(self.base_rev_id)
 
352
            self.base_rev_id, steps = self.revision_graph.find_unique_lca(
 
353
                revisions[0], revisions[1], count_steps=True)
 
354
            if self.base_rev_id == NULL_REVISION:
 
355
                raise UnrelatedBranches()
 
356
            if steps > 1:
 
357
                warning('Warning: criss-cross merge encountered.  See bzr'
 
358
                        ' help criss-cross.')
 
359
        self.base_tree = self.revision_tree(self.base_rev_id)
614
360
        self.base_is_ancestor = True
615
361
        self.base_is_other_ancestor = True
616
 
        trace.mutter('Base revid: %r' % self.base_rev_id)
617
362
 
618
363
    def set_base(self, base_revision):
619
364
        """Set the base revision to use for the merge.
620
365
 
621
366
        :param base_revision: A 2-list containing a path and revision number.
622
367
        """
623
 
        trace.mutter("doing merge() with no base_revision specified")
 
368
        mutter("doing merge() with no base_revision specified")
624
369
        if base_revision == [None, None]:
625
370
            self.find_base()
626
371
        else:
639
384
                  'other_tree': self.other_tree,
640
385
                  'interesting_ids': self.interesting_ids,
641
386
                  'interesting_files': self.interesting_files,
642
 
                  'this_branch': self.this_branch,
 
387
                  'pp': self.pp,
643
388
                  'do_merge': False}
644
389
        if self.merge_type.requires_base:
645
390
            kwargs['base_tree'] = self.base_tree
646
391
        if self.merge_type.supports_reprocess:
647
392
            kwargs['reprocess'] = self.reprocess
648
393
        elif self.reprocess:
649
 
            raise errors.BzrError(
650
 
                "Conflict reduction is not supported for merge"
651
 
                " type %s." % self.merge_type)
 
394
            raise BzrError("Conflict reduction is not supported for merge"
 
395
                                  " type %s." % self.merge_type)
652
396
        if self.merge_type.supports_show_base:
653
397
            kwargs['show_base'] = self.show_base
654
398
        elif self.show_base:
655
 
            raise errors.BzrError("Showing base is not supported for this"
656
 
                                  " merge type. %s" % self.merge_type)
 
399
            raise BzrError("Showing base is not supported for this"
 
400
                           " merge type. %s" % self.merge_type)
657
401
        if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)
658
402
            and not self.base_is_other_ancestor):
659
403
            raise errors.CannotReverseCherrypick()
660
404
        if self.merge_type.supports_cherrypick:
661
405
            kwargs['cherrypick'] = (not self.base_is_ancestor or
662
406
                                    not self.base_is_other_ancestor)
663
 
        if self._is_criss_cross and getattr(self.merge_type,
664
 
                                            'supports_lca_trees', False):
665
 
            kwargs['lca_trees'] = self._lca_trees
666
 
        return self.merge_type(pb=None,
 
407
        return self.merge_type(pb=self._pb,
667
408
                               change_reporter=self.change_reporter,
668
409
                               **kwargs)
669
410
 
670
 
    def _do_merge_to(self):
671
 
        merge = self.make_merger()
672
 
        if self.other_branch is not None:
673
 
            self.other_branch.update_references(self.this_branch)
674
 
        merge.do_merge()
675
 
        if self.recurse == 'down':
676
 
            for relpath, file_id in self.this_tree.iter_references():
677
 
                sub_tree = self.this_tree.get_nested_tree(file_id, relpath)
678
 
                other_revision = self.other_tree.get_reference_revision(
679
 
                    file_id, relpath)
680
 
                if  other_revision == sub_tree.last_revision():
681
 
                    continue
682
 
                sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
683
 
                sub_merge.merge_type = self.merge_type
684
 
                other_branch = self.other_branch.reference_parent(file_id, relpath)
685
 
                sub_merge.set_other_revision(other_revision, other_branch)
686
 
                base_revision = self.base_tree.get_reference_revision(file_id)
687
 
                sub_merge.base_tree = \
688
 
                    sub_tree.branch.repository.revision_tree(base_revision)
689
 
                sub_merge.base_rev_id = base_revision
690
 
                sub_merge.do_merge()
691
 
        return merge
692
 
 
693
411
    def do_merge(self):
694
 
        operation = OperationWithCleanups(self._do_merge_to)
695
412
        self.this_tree.lock_tree_write()
696
 
        operation.add_cleanup(self.this_tree.unlock)
697
413
        if self.base_tree is not None:
698
414
            self.base_tree.lock_read()
699
 
            operation.add_cleanup(self.base_tree.unlock)
700
415
        if self.other_tree is not None:
701
416
            self.other_tree.lock_read()
702
 
            operation.add_cleanup(self.other_tree.unlock)
703
 
        merge = operation.run_simple()
 
417
        try:
 
418
            merge = self.make_merger()
 
419
            merge.do_merge()
 
420
            if self.recurse == 'down':
 
421
                for path, file_id in self.this_tree.iter_references():
 
422
                    sub_tree = self.this_tree.get_nested_tree(file_id, path)
 
423
                    other_revision = self.other_tree.get_reference_revision(
 
424
                        file_id, path)
 
425
                    if  other_revision == sub_tree.last_revision():
 
426
                        continue
 
427
                    sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
 
428
                    sub_merge.merge_type = self.merge_type
 
429
                    relpath = self.this_tree.relpath(path)
 
430
                    other_branch = self.other_branch.reference_parent(file_id, relpath)
 
431
                    sub_merge.set_other_revision(other_revision, other_branch)
 
432
                    base_revision = self.base_tree.get_reference_revision(file_id)
 
433
                    sub_merge.base_tree = \
 
434
                        sub_tree.branch.repository.revision_tree(base_revision)
 
435
                    sub_merge.base_rev_id = base_revision
 
436
                    sub_merge.do_merge()
 
437
 
 
438
        finally:
 
439
            if self.other_tree is not None:
 
440
                self.other_tree.unlock()
 
441
            if self.base_tree is not None:
 
442
                self.base_tree.unlock()
 
443
            self.this_tree.unlock()
704
444
        if len(merge.cooked_conflicts) == 0:
705
 
            if not self.ignore_zero and not trace.is_quiet():
706
 
                trace.note("All changes applied successfully.")
 
445
            if not self.ignore_zero and not is_quiet():
 
446
                note("All changes applied successfully.")
707
447
        else:
708
 
            trace.note("%d conflicts encountered."
709
 
                       % len(merge.cooked_conflicts))
 
448
            note("%d conflicts encountered." % len(merge.cooked_conflicts))
710
449
 
711
450
        return len(merge.cooked_conflicts)
712
451
 
713
452
 
714
 
class _InventoryNoneEntry(object):
715
 
    """This represents an inventory entry which *isn't there*.
716
 
 
717
 
    It simplifies the merging logic if we always have an InventoryEntry, even
718
 
    if it isn't actually present
719
 
    """
720
 
    executable = None
721
 
    kind = None
722
 
    name = None
723
 
    parent_id = None
724
 
    revision = None
725
 
    symlink_target = None
726
 
    text_sha1 = None
727
 
 
728
 
_none_entry = _InventoryNoneEntry()
729
 
 
730
 
 
731
453
class Merge3Merger(object):
732
454
    """Three-way merger that uses the merge3 text merger"""
733
455
    requires_base = True
737
459
    supports_cherrypick = True
738
460
    supports_reverse_cherrypick = True
739
461
    winner_idx = {"this": 2, "other": 1, "conflict": 1}
740
 
    supports_lca_trees = True
741
462
 
742
 
    def __init__(self, working_tree, this_tree, base_tree, other_tree,
 
463
    def __init__(self, working_tree, this_tree, base_tree, other_tree, 
743
464
                 interesting_ids=None, reprocess=False, show_base=False,
744
 
                 pb=None, pp=None, change_reporter=None,
 
465
                 pb=DummyProgress(), pp=None, change_reporter=None,
745
466
                 interesting_files=None, do_merge=True,
746
 
                 cherrypick=False, lca_trees=None, this_branch=None):
 
467
                 cherrypick=False):
747
468
        """Initialize the merger object and perform the merge.
748
469
 
749
470
        :param working_tree: The working tree to apply the merge to
750
471
        :param this_tree: The local tree in the merge operation
751
472
        :param base_tree: The common tree in the merge operation
752
 
        :param other_tree: The other tree to merge changes from
753
 
        :param this_branch: The branch associated with this_tree.  Defaults to
754
 
            this_tree.branch if not supplied.
 
473
        :param other_tree: The other other tree to merge changes from
755
474
        :param interesting_ids: The file_ids of files that should be
756
475
            participate in the merge.  May not be combined with
757
476
            interesting_files.
758
477
        :param: reprocess If True, perform conflict-reduction processing.
759
478
        :param show_base: If True, show the base revision in text conflicts.
760
479
            (incompatible with reprocess)
761
 
        :param pb: ignored
 
480
        :param pb: A Progress bar
762
481
        :param pp: A ProgressPhase object
763
482
        :param change_reporter: An object that should report changes made
764
483
        :param interesting_files: The tree-relative paths of files that should
767
486
            be combined with interesting_ids.  If neither interesting_files nor
768
487
            interesting_ids is specified, all files may participate in the
769
488
            merge.
770
 
        :param lca_trees: Can be set to a dictionary of {revision_id:rev_tree}
771
 
            if the ancestry was found to include a criss-cross merge.
772
 
            Otherwise should be None.
773
489
        """
774
490
        object.__init__(self)
775
491
        if interesting_files is not None and interesting_ids is not None:
776
492
            raise ValueError(
777
493
                'specify either interesting_ids or interesting_files')
778
 
        if this_branch is None:
779
 
            this_branch = this_tree.branch
780
494
        self.interesting_ids = interesting_ids
781
495
        self.interesting_files = interesting_files
782
496
        self.this_tree = working_tree
783
497
        self.base_tree = base_tree
784
498
        self.other_tree = other_tree
785
 
        self.this_branch = this_branch
786
499
        self._raw_conflicts = []
787
500
        self.cooked_conflicts = []
788
501
        self.reprocess = reprocess
789
502
        self.show_base = show_base
790
 
        self._lca_trees = lca_trees
791
 
        # Uncommenting this will change the default algorithm to always use
792
 
        # _entries_lca. This can be useful for running the test suite and
793
 
        # making sure we haven't missed any corner cases.
794
 
        # if lca_trees is None:
795
 
        #     self._lca_trees = [self.base_tree]
 
503
        self.pb = pb
 
504
        self.pp = pp
796
505
        self.change_reporter = change_reporter
797
506
        self.cherrypick = cherrypick
 
507
        if self.pp is None:
 
508
            self.pp = ProgressPhase("Merge phase", 3, self.pb)
798
509
        if do_merge:
799
510
            self.do_merge()
800
 
        if pp is not None:
801
 
            warnings.warn("pp argument to Merge3Merger is deprecated")
802
 
        if pb is not None:
803
 
            warnings.warn("pb argument to Merge3Merger is deprecated")
804
511
 
805
512
    def do_merge(self):
806
 
        operation = OperationWithCleanups(self._do_merge)
807
513
        self.this_tree.lock_tree_write()
808
 
        operation.add_cleanup(self.this_tree.unlock)
809
514
        self.base_tree.lock_read()
810
 
        operation.add_cleanup(self.base_tree.unlock)
811
515
        self.other_tree.lock_read()
812
 
        operation.add_cleanup(self.other_tree.unlock)
813
 
        operation.run()
814
 
 
815
 
    def _do_merge(self, operation):
816
 
        self.tt = transform.TreeTransform(self.this_tree, None)
817
 
        operation.add_cleanup(self.tt.finalize)
818
 
        self._compute_transform()
819
 
        results = self.tt.apply(no_conflicts=True)
820
 
        self.write_modified(results)
 
516
        self.tt = TreeTransform(self.this_tree, self.pb)
821
517
        try:
822
 
            self.this_tree.add_conflicts(self.cooked_conflicts)
823
 
        except errors.UnsupportedOperation:
824
 
            pass
 
518
            self.pp.next_phase()
 
519
            self._compute_transform()
 
520
            self.pp.next_phase()
 
521
            results = self.tt.apply(no_conflicts=True)
 
522
            self.write_modified(results)
 
523
            try:
 
524
                self.this_tree.add_conflicts(self.cooked_conflicts)
 
525
            except UnsupportedOperation:
 
526
                pass
 
527
        finally:
 
528
            self.tt.finalize()
 
529
            self.other_tree.unlock()
 
530
            self.base_tree.unlock()
 
531
            self.this_tree.unlock()
 
532
            self.pb.clear()
825
533
 
826
534
    def make_preview_transform(self):
827
 
        operation = OperationWithCleanups(self._make_preview_transform)
828
535
        self.base_tree.lock_read()
829
 
        operation.add_cleanup(self.base_tree.unlock)
830
536
        self.other_tree.lock_read()
831
 
        operation.add_cleanup(self.other_tree.unlock)
832
 
        return operation.run_simple()
833
 
 
834
 
    def _make_preview_transform(self):
835
 
        self.tt = transform.TransformPreview(self.this_tree)
836
 
        self._compute_transform()
 
537
        self.tt = TransformPreview(self.this_tree)
 
538
        try:
 
539
            self.pp.next_phase()
 
540
            self._compute_transform()
 
541
            self.pp.next_phase()
 
542
        finally:
 
543
            self.other_tree.unlock()
 
544
            self.base_tree.unlock()
 
545
            self.pb.clear()
837
546
        return self.tt
838
547
 
839
548
    def _compute_transform(self):
840
 
        if self._lca_trees is None:
841
 
            entries = self._entries3()
842
 
            resolver = self._three_way
843
 
        else:
844
 
            entries = self._entries_lca()
845
 
            resolver = self._lca_multi_way
 
549
        entries = self._entries3()
846
550
        child_pb = ui.ui_factory.nested_progress_bar()
847
551
        try:
848
 
            factories = Merger.hooks['merge_file_content']
849
 
            hooks = [factory(self) for factory in factories] + [self]
850
 
            self.active_hooks = [hook for hook in hooks if hook is not None]
851
552
            for num, (file_id, changed, parents3, names3,
852
553
                      executable3) in enumerate(entries):
853
554
                child_pb.update('Preparing file merge', num, len(entries))
854
 
                self._merge_names(file_id, parents3, names3, resolver=resolver)
 
555
                self._merge_names(file_id, parents3, names3)
855
556
                if changed:
856
 
                    file_status = self._do_merge_contents(file_id)
 
557
                    file_status = self.merge_contents(file_id)
857
558
                else:
858
559
                    file_status = 'unmodified'
859
560
                self._merge_executable(file_id,
860
 
                    executable3, file_status, resolver=resolver)
 
561
                    executable3, file_status)
861
562
        finally:
862
563
            child_pb.finished()
863
564
        self.fix_root()
 
565
        self.pp.next_phase()
864
566
        child_pb = ui.ui_factory.nested_progress_bar()
865
567
        try:
866
 
            fs_conflicts = transform.resolve_conflicts(self.tt, child_pb,
867
 
                lambda t, c: transform.conflict_pass(t, c, self.other_tree))
 
568
            fs_conflicts = resolve_conflicts(self.tt, child_pb,
 
569
                lambda t, c: conflict_pass(t, c, self.other_tree))
868
570
        finally:
869
571
            child_pb.finished()
870
572
        if self.change_reporter is not None:
873
575
                self.tt.iter_changes(), self.change_reporter)
874
576
        self.cook_conflicts(fs_conflicts)
875
577
        for conflict in self.cooked_conflicts:
876
 
            trace.warning(conflict)
 
578
            warning(conflict)
877
579
 
878
580
    def _entries3(self):
879
581
        """Gather data about files modified between three trees.
888
590
        iterator = self.other_tree.iter_changes(self.base_tree,
889
591
                include_unchanged=True, specific_files=self.interesting_files,
890
592
                extra_trees=[self.this_tree])
891
 
        this_entries = dict((e.file_id, e) for p, e in
892
 
                            self.this_tree.iter_entries_by_dir(
893
 
                            self.interesting_ids))
894
593
        for (file_id, paths, changed, versioned, parents, names, kind,
895
594
             executable) in iterator:
896
595
            if (self.interesting_ids is not None and
897
596
                file_id not in self.interesting_ids):
898
597
                continue
899
 
            entry = this_entries.get(file_id)
900
 
            if entry is not None:
 
598
            if file_id in self.this_tree.inventory:
 
599
                entry = self.this_tree.inventory[file_id]
901
600
                this_name = entry.name
902
601
                this_parent = entry.parent_id
903
602
                this_executable = entry.executable
911
610
            result.append((file_id, changed, parents3, names3, executable3))
912
611
        return result
913
612
 
914
 
    def _entries_lca(self):
915
 
        """Gather data about files modified between multiple trees.
916
 
 
917
 
        This compares OTHER versus all LCA trees, and for interesting entries,
918
 
        it then compares with THIS and BASE.
919
 
 
920
 
        For the multi-valued entries, the format will be (BASE, [lca1, lca2])
921
 
        :return: [(file_id, changed, parents, names, executable)]
922
 
            file_id     Simple file_id of the entry
923
 
            changed     Boolean, True if the kind or contents changed
924
 
                        else False
925
 
            parents     ((base, [parent_id, in, lcas]), parent_id_other,
926
 
                         parent_id_this)
927
 
            names       ((base, [name, in, lcas]), name_in_other, name_in_this)
928
 
            executable  ((base, [exec, in, lcas]), exec_in_other, exec_in_this)
929
 
        """
930
 
        if self.interesting_files is not None:
931
 
            lookup_trees = [self.this_tree, self.base_tree]
932
 
            lookup_trees.extend(self._lca_trees)
933
 
            # I think we should include the lca trees as well
934
 
            interesting_ids = self.other_tree.paths2ids(self.interesting_files,
935
 
                                                        lookup_trees)
936
 
        else:
937
 
            interesting_ids = self.interesting_ids
938
 
        result = []
939
 
        walker = _mod_tree.MultiWalker(self.other_tree, self._lca_trees)
940
 
 
941
 
        base_inventory = self.base_tree.inventory
942
 
        this_inventory = self.this_tree.inventory
943
 
        for path, file_id, other_ie, lca_values in walker.iter_all():
944
 
            # Is this modified at all from any of the other trees?
945
 
            if other_ie is None:
946
 
                other_ie = _none_entry
947
 
            if interesting_ids is not None and file_id not in interesting_ids:
948
 
                continue
949
 
 
950
 
            # If other_revision is found in any of the lcas, that means this
951
 
            # node is uninteresting. This is because when merging, if there are
952
 
            # multiple heads(), we have to create a new node. So if we didn't,
953
 
            # we know that the ancestry is linear, and that OTHER did not
954
 
            # modify anything
955
 
            # See doc/developers/lca_merge_resolution.txt for details
956
 
            other_revision = other_ie.revision
957
 
            if other_revision is not None:
958
 
                # We can't use this shortcut when other_revision is None,
959
 
                # because it may be None because things are WorkingTrees, and
960
 
                # not because it is *actually* None.
961
 
                is_unmodified = False
962
 
                for lca_path, ie in lca_values:
963
 
                    if ie is not None and ie.revision == other_revision:
964
 
                        is_unmodified = True
965
 
                        break
966
 
                if is_unmodified:
967
 
                    continue
968
 
 
969
 
            lca_entries = []
970
 
            for lca_path, lca_ie in lca_values:
971
 
                if lca_ie is None:
972
 
                    lca_entries.append(_none_entry)
973
 
                else:
974
 
                    lca_entries.append(lca_ie)
975
 
 
976
 
            if file_id in base_inventory:
977
 
                base_ie = base_inventory[file_id]
978
 
            else:
979
 
                base_ie = _none_entry
980
 
 
981
 
            if file_id in this_inventory:
982
 
                this_ie = this_inventory[file_id]
983
 
            else:
984
 
                this_ie = _none_entry
985
 
 
986
 
            lca_kinds = []
987
 
            lca_parent_ids = []
988
 
            lca_names = []
989
 
            lca_executable = []
990
 
            for lca_ie in lca_entries:
991
 
                lca_kinds.append(lca_ie.kind)
992
 
                lca_parent_ids.append(lca_ie.parent_id)
993
 
                lca_names.append(lca_ie.name)
994
 
                lca_executable.append(lca_ie.executable)
995
 
 
996
 
            kind_winner = self._lca_multi_way(
997
 
                (base_ie.kind, lca_kinds),
998
 
                other_ie.kind, this_ie.kind)
999
 
            parent_id_winner = self._lca_multi_way(
1000
 
                (base_ie.parent_id, lca_parent_ids),
1001
 
                other_ie.parent_id, this_ie.parent_id)
1002
 
            name_winner = self._lca_multi_way(
1003
 
                (base_ie.name, lca_names),
1004
 
                other_ie.name, this_ie.name)
1005
 
 
1006
 
            content_changed = True
1007
 
            if kind_winner == 'this':
1008
 
                # No kind change in OTHER, see if there are *any* changes
1009
 
                if other_ie.kind == 'directory':
1010
 
                    if parent_id_winner == 'this' and name_winner == 'this':
1011
 
                        # No change for this directory in OTHER, skip
1012
 
                        continue
1013
 
                    content_changed = False
1014
 
                elif other_ie.kind is None or other_ie.kind == 'file':
1015
 
                    def get_sha1(ie, tree):
1016
 
                        if ie.kind != 'file':
1017
 
                            return None
1018
 
                        return tree.get_file_sha1(file_id)
1019
 
                    base_sha1 = get_sha1(base_ie, self.base_tree)
1020
 
                    lca_sha1s = [get_sha1(ie, tree) for ie, tree
1021
 
                                 in zip(lca_entries, self._lca_trees)]
1022
 
                    this_sha1 = get_sha1(this_ie, self.this_tree)
1023
 
                    other_sha1 = get_sha1(other_ie, self.other_tree)
1024
 
                    sha1_winner = self._lca_multi_way(
1025
 
                        (base_sha1, lca_sha1s), other_sha1, this_sha1,
1026
 
                        allow_overriding_lca=False)
1027
 
                    exec_winner = self._lca_multi_way(
1028
 
                        (base_ie.executable, lca_executable),
1029
 
                        other_ie.executable, this_ie.executable)
1030
 
                    if (parent_id_winner == 'this' and name_winner == 'this'
1031
 
                        and sha1_winner == 'this' and exec_winner == 'this'):
1032
 
                        # No kind, parent, name, exec, or content change for
1033
 
                        # OTHER, so this node is not considered interesting
1034
 
                        continue
1035
 
                    if sha1_winner == 'this':
1036
 
                        content_changed = False
1037
 
                elif other_ie.kind == 'symlink':
1038
 
                    def get_target(ie, tree):
1039
 
                        if ie.kind != 'symlink':
1040
 
                            return None
1041
 
                        return tree.get_symlink_target(file_id)
1042
 
                    base_target = get_target(base_ie, self.base_tree)
1043
 
                    lca_targets = [get_target(ie, tree) for ie, tree
1044
 
                                   in zip(lca_entries, self._lca_trees)]
1045
 
                    this_target = get_target(this_ie, self.this_tree)
1046
 
                    other_target = get_target(other_ie, self.other_tree)
1047
 
                    target_winner = self._lca_multi_way(
1048
 
                        (base_target, lca_targets),
1049
 
                        other_target, this_target)
1050
 
                    if (parent_id_winner == 'this' and name_winner == 'this'
1051
 
                        and target_winner == 'this'):
1052
 
                        # No kind, parent, name, or symlink target change
1053
 
                        # not interesting
1054
 
                        continue
1055
 
                    if target_winner == 'this':
1056
 
                        content_changed = False
1057
 
                elif other_ie.kind == 'tree-reference':
1058
 
                    # The 'changed' information seems to be handled at a higher
1059
 
                    # level. At least, _entries3 returns False for content
1060
 
                    # changed, even when at a new revision_id.
1061
 
                    content_changed = False
1062
 
                    if (parent_id_winner == 'this' and name_winner == 'this'):
1063
 
                        # Nothing interesting
1064
 
                        continue
1065
 
                else:
1066
 
                    raise AssertionError('unhandled kind: %s' % other_ie.kind)
1067
 
 
1068
 
            # If we have gotten this far, that means something has changed
1069
 
            result.append((file_id, content_changed,
1070
 
                           ((base_ie.parent_id, lca_parent_ids),
1071
 
                            other_ie.parent_id, this_ie.parent_id),
1072
 
                           ((base_ie.name, lca_names),
1073
 
                            other_ie.name, this_ie.name),
1074
 
                           ((base_ie.executable, lca_executable),
1075
 
                            other_ie.executable, this_ie.executable)
1076
 
                          ))
1077
 
        return result
1078
 
 
1079
 
 
1080
613
    def fix_root(self):
1081
614
        try:
1082
615
            self.tt.final_kind(self.tt.root)
1083
 
        except errors.NoSuchFile:
 
616
        except NoSuchFile:
1084
617
            self.tt.cancel_deletion(self.tt.root)
1085
618
        if self.tt.final_file_id(self.tt.root) is None:
1086
 
            self.tt.version_file(self.tt.tree_file_id(self.tt.root),
 
619
            self.tt.version_file(self.tt.tree_file_id(self.tt.root), 
1087
620
                                 self.tt.root)
 
621
        if self.other_tree.inventory.root is None:
 
622
            return
1088
623
        other_root_file_id = self.other_tree.get_root_id()
1089
 
        if other_root_file_id is None:
1090
 
            return
1091
624
        other_root = self.tt.trans_id_file_id(other_root_file_id)
1092
625
        if other_root == self.tt.root:
1093
626
            return
1094
 
        if self.other_tree.inventory.root.file_id in self.this_tree.inventory:
1095
 
            # the other tree's root is a non-root in the current tree (as when
1096
 
            # a previously unrelated branch is merged into another)
1097
 
            return
1098
627
        try:
1099
628
            self.tt.final_kind(other_root)
1100
 
            other_root_is_present = True
1101
 
        except errors.NoSuchFile:
1102
 
            # other_root doesn't have a physical representation. We still need
1103
 
            # to move any references to the actual root of the tree.
1104
 
            other_root_is_present = False
1105
 
        # 'other_tree.inventory.root' is not present in this tree. We are
1106
 
        # calling adjust_path for children which *want* to be present with a
1107
 
        # correct place to go.
1108
 
        for thing, child in self.other_tree.inventory.root.children.iteritems():
 
629
        except NoSuchFile:
 
630
            return
 
631
        self.reparent_children(self.other_tree.inventory.root, self.tt.root)
 
632
        self.tt.cancel_creation(other_root)
 
633
        self.tt.cancel_versioning(other_root)
 
634
 
 
635
    def reparent_children(self, ie, target):
 
636
        for thing, child in ie.children.iteritems():
1109
637
            trans_id = self.tt.trans_id_file_id(child.file_id)
1110
 
            if not other_root_is_present:
1111
 
                # FIXME: Make final_kind returns None instead of raising
1112
 
                # NoSuchFile to avoid the ugly construct below -- vila 20100402
1113
 
                try:
1114
 
                    self.tt.final_kind(trans_id)
1115
 
                    # The item exist in the final tree and has a defined place
1116
 
                    # to go already.
1117
 
                    continue
1118
 
                except errors.NoSuchFile, e:
1119
 
                    pass
1120
 
            # Move the item into the root
1121
 
            self.tt.adjust_path(self.tt.final_name(trans_id),
1122
 
                                self.tt.root, trans_id)
1123
 
        if other_root_is_present:
1124
 
            self.tt.cancel_creation(other_root)
1125
 
            self.tt.cancel_versioning(other_root)
 
638
            self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)
1126
639
 
1127
640
    def write_modified(self, results):
1128
641
        modified_hashes = {}
1149
662
        if entry is None:
1150
663
            return None
1151
664
        return entry.name
1152
 
 
 
665
    
1153
666
    @staticmethod
1154
667
    def contents_sha1(tree, file_id):
1155
668
        """Determine the sha1 of the file contents (used as a key method)."""
1160
673
    @staticmethod
1161
674
    def executable(tree, file_id):
1162
675
        """Determine the executability of a file-id (used as a key method)."""
1163
 
        if not tree.has_id(file_id):
 
676
        if file_id not in tree:
1164
677
            return None
1165
678
        if tree.kind(file_id) != "file":
1166
679
            return False
1169
682
    @staticmethod
1170
683
    def kind(tree, file_id):
1171
684
        """Determine the kind of a file-id (used as a key method)."""
1172
 
        if not tree.has_id(file_id):
 
685
        if file_id not in tree:
1173
686
            return None
1174
687
        return tree.kind(file_id)
1175
688
 
1176
689
    @staticmethod
1177
690
    def _three_way(base, other, this):
 
691
        #if base == other, either they all agree, or only THIS has changed.
1178
692
        if base == other:
1179
 
            # if 'base == other', either they all agree, or only 'this' has
1180
 
            # changed.
1181
693
            return 'this'
1182
694
        elif this not in (base, other):
1183
 
            # 'this' is neither 'base' nor 'other', so both sides changed
1184
695
            return 'conflict'
 
696
        # "Ambiguous clean merge" -- both sides have made the same change.
1185
697
        elif this == other:
1186
 
            # "Ambiguous clean merge" -- both sides have made the same change.
1187
698
            return "this"
 
699
        # this == base: only other has changed.
1188
700
        else:
1189
 
            # this == base: only other has changed.
1190
701
            return "other"
1191
702
 
1192
703
    @staticmethod
1193
 
    def _lca_multi_way(bases, other, this, allow_overriding_lca=True):
1194
 
        """Consider LCAs when determining whether a change has occurred.
1195
 
 
1196
 
        If LCAS are all identical, this is the same as a _three_way comparison.
1197
 
 
1198
 
        :param bases: value in (BASE, [LCAS])
1199
 
        :param other: value in OTHER
1200
 
        :param this: value in THIS
1201
 
        :param allow_overriding_lca: If there is more than one unique lca
1202
 
            value, allow OTHER to override THIS if it has a new value, and
1203
 
            THIS only has an lca value, or vice versa. This is appropriate for
1204
 
            truly scalar values, not as much for non-scalars.
1205
 
        :return: 'this', 'other', or 'conflict' depending on whether an entry
1206
 
            changed or not.
1207
 
        """
1208
 
        # See doc/developers/lca_tree_merging.txt for details about this
1209
 
        # algorithm.
1210
 
        if other == this:
1211
 
            # Either Ambiguously clean, or nothing was actually changed. We
1212
 
            # don't really care
1213
 
            return 'this'
1214
 
        base_val, lca_vals = bases
1215
 
        # Remove 'base_val' from the lca_vals, because it is not interesting
1216
 
        filtered_lca_vals = [lca_val for lca_val in lca_vals
1217
 
                                      if lca_val != base_val]
1218
 
        if len(filtered_lca_vals) == 0:
1219
 
            return Merge3Merger._three_way(base_val, other, this)
1220
 
 
1221
 
        unique_lca_vals = set(filtered_lca_vals)
1222
 
        if len(unique_lca_vals) == 1:
1223
 
            return Merge3Merger._three_way(unique_lca_vals.pop(), other, this)
1224
 
 
1225
 
        if allow_overriding_lca:
1226
 
            if other in unique_lca_vals:
1227
 
                if this in unique_lca_vals:
1228
 
                    # Each side picked a different lca, conflict
1229
 
                    return 'conflict'
1230
 
                else:
1231
 
                    # This has a value which supersedes both lca values, and
1232
 
                    # other only has an lca value
1233
 
                    return 'this'
1234
 
            elif this in unique_lca_vals:
1235
 
                # OTHER has a value which supersedes both lca values, and this
1236
 
                # only has an lca value
1237
 
                return 'other'
1238
 
 
1239
 
        # At this point, the lcas disagree, and the tip disagree
1240
 
        return 'conflict'
1241
 
 
1242
 
    @staticmethod
1243
 
    @deprecated_method(deprecated_in((2, 2, 0)))
1244
704
    def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
1245
705
        """Do a three-way test on a scalar.
1246
706
        Return "this", "other" or "conflict", depending whether a value wins.
1261
721
 
1262
722
    def merge_names(self, file_id):
1263
723
        def get_entry(tree):
1264
 
            if tree.has_id(file_id):
 
724
            if file_id in tree.inventory:
1265
725
                return tree.inventory[file_id]
1266
726
            else:
1267
727
                return None
1278
738
            else:
1279
739
                names.append(entry.name)
1280
740
                parents.append(entry.parent_id)
1281
 
        return self._merge_names(file_id, parents, names,
1282
 
                                 resolver=self._three_way)
 
741
        return self._merge_names(file_id, parents, names)
1283
742
 
1284
 
    def _merge_names(self, file_id, parents, names, resolver):
 
743
    def _merge_names(self, file_id, parents, names):
1285
744
        """Perform a merge on file_id names and parents"""
1286
745
        base_name, other_name, this_name = names
1287
746
        base_parent, other_parent, this_parent = parents
1288
747
 
1289
 
        name_winner = resolver(*names)
 
748
        name_winner = self._three_way(*names)
1290
749
 
1291
 
        parent_id_winner = resolver(*parents)
 
750
        parent_id_winner = self._three_way(*parents)
1292
751
        if this_name is None:
1293
752
            if name_winner == "this":
1294
753
                name_winner = "other"
1296
755
                parent_id_winner = "other"
1297
756
        if name_winner == "this" and parent_id_winner == "this":
1298
757
            return
1299
 
        if name_winner == 'conflict' or parent_id_winner == 'conflict':
1300
 
            # Creating helpers (.OTHER or .THIS) here cause problems down the
1301
 
            # road if a ContentConflict needs to be created so we should not do
1302
 
            # that
1303
 
            trans_id = self.tt.trans_id_file_id(file_id)
1304
 
            self._raw_conflicts.append(('path conflict', trans_id, file_id,
1305
 
                                        this_parent, this_name,
1306
 
                                        other_parent, other_name))
 
758
        if name_winner == "conflict":
 
759
            trans_id = self.tt.trans_id_file_id(file_id)
 
760
            self._raw_conflicts.append(('name conflict', trans_id, 
 
761
                                        this_name, other_name))
 
762
        if parent_id_winner == "conflict":
 
763
            trans_id = self.tt.trans_id_file_id(file_id)
 
764
            self._raw_conflicts.append(('parent conflict', trans_id, 
 
765
                                        this_parent, other_parent))
1307
766
        if other_name is None:
1308
 
            # it doesn't matter whether the result was 'other' or
 
767
            # it doesn't matter whether the result was 'other' or 
1309
768
            # 'conflict'-- if there's no 'other', we leave it alone.
1310
769
            return
 
770
        # if we get here, name_winner and parent_winner are set to safe values.
 
771
        trans_id = self.tt.trans_id_file_id(file_id)
1311
772
        parent_id = parents[self.winner_idx[parent_id_winner]]
1312
773
        if parent_id is not None:
1313
 
            # if we get here, name_winner and parent_winner are set to safe
1314
 
            # values.
 
774
            parent_trans_id = self.tt.trans_id_file_id(parent_id)
1315
775
            self.tt.adjust_path(names[self.winner_idx[name_winner]],
1316
 
                                self.tt.trans_id_file_id(parent_id),
1317
 
                                self.tt.trans_id_file_id(file_id))
 
776
                                parent_trans_id, trans_id)
1318
777
 
1319
 
    def _do_merge_contents(self, file_id):
1320
 
        """Performs a merge on file_id contents."""
 
778
    def merge_contents(self, file_id):
 
779
        """Performa a merge on file_id contents."""
1321
780
        def contents_pair(tree):
1322
781
            if file_id not in tree:
1323
782
                return (None, None)
1330
789
                contents = None
1331
790
            return kind, contents
1332
791
 
 
792
        def contents_conflict():
 
793
            trans_id = self.tt.trans_id_file_id(file_id)
 
794
            name = self.tt.final_name(trans_id)
 
795
            parent_id = self.tt.final_parent(trans_id)
 
796
            if file_id in self.this_tree.inventory:
 
797
                self.tt.unversion_file(trans_id)
 
798
                if file_id in self.this_tree:
 
799
                    self.tt.delete_contents(trans_id)
 
800
            file_group = self._dump_conflicts(name, parent_id, file_id, 
 
801
                                              set_version=True)
 
802
            self._raw_conflicts.append(('contents conflict', file_group))
 
803
 
1333
804
        # See SPOT run.  run, SPOT, run.
1334
805
        # So we're not QUITE repeating ourselves; we do tricky things with
1335
806
        # file kind...
1336
807
        base_pair = contents_pair(self.base_tree)
1337
808
        other_pair = contents_pair(self.other_tree)
1338
 
        if self._lca_trees:
1339
 
            this_pair = contents_pair(self.this_tree)
1340
 
            lca_pairs = [contents_pair(tree) for tree in self._lca_trees]
1341
 
            winner = self._lca_multi_way((base_pair, lca_pairs), other_pair,
1342
 
                                         this_pair, allow_overriding_lca=False)
1343
 
        else:
1344
 
            if base_pair == other_pair:
1345
 
                winner = 'this'
1346
 
            else:
1347
 
                # We delayed evaluating this_pair as long as we can to avoid
1348
 
                # unnecessary sha1 calculation
1349
 
                this_pair = contents_pair(self.this_tree)
1350
 
                winner = self._three_way(base_pair, other_pair, this_pair)
1351
 
        if winner == 'this':
1352
 
            # No interesting changes introduced by OTHER
1353
 
            return "unmodified"
1354
 
        # We have a hypothetical conflict, but if we have files, then we
1355
 
        # can try to merge the content
1356
 
        trans_id = self.tt.trans_id_file_id(file_id)
1357
 
        params = MergeHookParams(self, file_id, trans_id, this_pair[0],
1358
 
            other_pair[0], winner)
1359
 
        hooks = self.active_hooks
1360
 
        hook_status = 'not_applicable'
1361
 
        for hook in hooks:
1362
 
            hook_status, lines = hook.merge_contents(params)
1363
 
            if hook_status != 'not_applicable':
1364
 
                # Don't try any more hooks, this one applies.
1365
 
                break
1366
 
        result = "modified"
1367
 
        if hook_status == 'not_applicable':
1368
 
            # This is a contents conflict, because none of the available
1369
 
            # functions could merge it.
1370
 
            result = None
1371
 
            name = self.tt.final_name(trans_id)
1372
 
            parent_id = self.tt.final_parent(trans_id)
1373
 
            if self.this_tree.has_id(file_id):
1374
 
                self.tt.unversion_file(trans_id)
1375
 
            file_group = self._dump_conflicts(name, parent_id, file_id,
1376
 
                                              set_version=True)
1377
 
            self._raw_conflicts.append(('contents conflict', file_group))
1378
 
        elif hook_status == 'success':
1379
 
            self.tt.create_file(lines, trans_id)
1380
 
        elif hook_status == 'conflicted':
1381
 
            # XXX: perhaps the hook should be able to provide
1382
 
            # the BASE/THIS/OTHER files?
1383
 
            self.tt.create_file(lines, trans_id)
1384
 
            self._raw_conflicts.append(('text conflict', trans_id))
1385
 
            name = self.tt.final_name(trans_id)
1386
 
            parent_id = self.tt.final_parent(trans_id)
1387
 
            self._dump_conflicts(name, parent_id, file_id)
1388
 
        elif hook_status == 'delete':
1389
 
            self.tt.unversion_file(trans_id)
1390
 
            result = "deleted"
1391
 
        elif hook_status == 'done':
1392
 
            # The hook function did whatever it needs to do directly, no
1393
 
            # further action needed here.
1394
 
            pass
1395
 
        else:
1396
 
            raise AssertionError('unknown hook_status: %r' % (hook_status,))
1397
 
        if not self.this_tree.has_id(file_id) and result == "modified":
1398
 
            self.tt.version_file(file_id, trans_id)
1399
 
        # The merge has been performed, so the old contents should not be
1400
 
        # retained.
1401
 
        try:
1402
 
            self.tt.delete_contents(trans_id)
1403
 
        except errors.NoSuchFile:
1404
 
            pass
1405
 
        return result
1406
 
 
1407
 
    def _default_other_winner_merge(self, merge_hook_params):
1408
 
        """Replace this contents with other."""
1409
 
        file_id = merge_hook_params.file_id
1410
 
        trans_id = merge_hook_params.trans_id
1411
 
        file_in_this = self.this_tree.has_id(file_id)
1412
 
        if self.other_tree.has_id(file_id):
1413
 
            # OTHER changed the file
1414
 
            wt = self.this_tree
1415
 
            if wt.supports_content_filtering():
1416
 
                # We get the path from the working tree if it exists.
1417
 
                # That fails though when OTHER is adding a file, so
1418
 
                # we fall back to the other tree to find the path if
1419
 
                # it doesn't exist locally.
1420
 
                try:
1421
 
                    filter_tree_path = wt.id2path(file_id)
1422
 
                except errors.NoSuchId:
1423
 
                    filter_tree_path = self.other_tree.id2path(file_id)
1424
 
            else:
1425
 
                # Skip the id2path lookup for older formats
1426
 
                filter_tree_path = None
1427
 
            transform.create_from_tree(self.tt, trans_id,
1428
 
                             self.other_tree, file_id,
1429
 
                             filter_tree_path=filter_tree_path)
1430
 
            return 'done', None
1431
 
        elif file_in_this:
1432
 
            # OTHER deleted the file
1433
 
            return 'delete', None
1434
 
        else:
1435
 
            raise AssertionError(
1436
 
                'winner is OTHER, but file_id %r not in THIS or OTHER tree'
1437
 
                % (file_id,))
1438
 
 
1439
 
    def merge_contents(self, merge_hook_params):
1440
 
        """Fallback merge logic after user installed hooks."""
1441
 
        # This function is used in merge hooks as the fallback instance.
1442
 
        # Perhaps making this function and the functions it calls be a 
1443
 
        # a separate class would be better.
1444
 
        if merge_hook_params.winner == 'other':
1445
 
            # OTHER is a straight winner, so replace this contents with other
1446
 
            return self._default_other_winner_merge(merge_hook_params)
1447
 
        elif merge_hook_params.is_file_merge():
1448
 
            # THIS and OTHER are both files, so text merge.  Either
1449
 
            # BASE is a file, or both converted to files, so at least we
1450
 
            # have agreement that output should be a file.
1451
 
            try:
1452
 
                self.text_merge(merge_hook_params.file_id,
1453
 
                    merge_hook_params.trans_id)
1454
 
            except errors.BinaryFile:
1455
 
                return 'not_applicable', None
1456
 
            return 'done', None
1457
 
        else:
1458
 
            return 'not_applicable', None
 
809
        if base_pair == other_pair:
 
810
            # OTHER introduced no changes
 
811
            return "unmodified"
 
812
        this_pair = contents_pair(self.this_tree)
 
813
        if this_pair == other_pair:
 
814
            # THIS and OTHER introduced the same changes
 
815
            return "unmodified"
 
816
        else:
 
817
            trans_id = self.tt.trans_id_file_id(file_id)
 
818
            if this_pair == base_pair:
 
819
                # only OTHER introduced changes
 
820
                if file_id in self.this_tree:
 
821
                    # Remove any existing contents
 
822
                    self.tt.delete_contents(trans_id)
 
823
                if file_id in self.other_tree:
 
824
                    # OTHER changed the file
 
825
                    create_by_entry(self.tt, 
 
826
                                    self.other_tree.inventory[file_id], 
 
827
                                    self.other_tree, trans_id)
 
828
                    if file_id not in self.this_tree.inventory:
 
829
                        self.tt.version_file(file_id, trans_id)
 
830
                    return "modified"
 
831
                elif file_id in self.this_tree.inventory:
 
832
                    # OTHER deleted the file
 
833
                    self.tt.unversion_file(trans_id)
 
834
                    return "deleted"
 
835
            #BOTH THIS and OTHER introduced changes; scalar conflict
 
836
            elif this_pair[0] == "file" and other_pair[0] == "file":
 
837
                # THIS and OTHER are both files, so text merge.  Either
 
838
                # BASE is a file, or both converted to files, so at least we
 
839
                # have agreement that output should be a file.
 
840
                try:
 
841
                    self.text_merge(file_id, trans_id)
 
842
                except BinaryFile:
 
843
                    return contents_conflict()
 
844
                if file_id not in self.this_tree.inventory:
 
845
                    self.tt.version_file(file_id, trans_id)
 
846
                try:
 
847
                    self.tt.tree_kind(trans_id)
 
848
                    self.tt.delete_contents(trans_id)
 
849
                except NoSuchFile:
 
850
                    pass
 
851
                return "modified"
 
852
            else:
 
853
                # Scalar conflict, can't text merge.  Dump conflicts
 
854
                return contents_conflict()
1459
855
 
1460
856
    def get_lines(self, tree, file_id):
1461
857
        """Return the lines in a file, or an empty list."""
1462
 
        if tree.has_id(file_id):
1463
 
            return tree.get_file_lines(file_id)
 
858
        if file_id in tree:
 
859
            return tree.get_file(file_id).readlines()
1464
860
        else:
1465
861
            return []
1466
862
 
1468
864
        """Perform a three-way text merge on a file_id"""
1469
865
        # it's possible that we got here with base as a different type.
1470
866
        # if so, we just want two-way text conflicts.
1471
 
        if self.base_tree.has_id(file_id) and \
 
867
        if file_id in self.base_tree and \
1472
868
            self.base_tree.kind(file_id) == "file":
1473
869
            base_lines = self.get_lines(self.base_tree, file_id)
1474
870
        else:
1475
871
            base_lines = []
1476
872
        other_lines = self.get_lines(self.other_tree, file_id)
1477
873
        this_lines = self.get_lines(self.this_tree, file_id)
1478
 
        m3 = merge3.Merge3(base_lines, this_lines, other_lines,
1479
 
                           is_cherrypick=self.cherrypick)
 
874
        m3 = Merge3(base_lines, this_lines, other_lines,
 
875
                    is_cherrypick=self.cherrypick)
1480
876
        start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
1481
877
        if self.show_base is True:
1482
878
            base_marker = '|' * 7
1485
881
 
1486
882
        def iter_merge3(retval):
1487
883
            retval["text_conflicts"] = False
1488
 
            for line in m3.merge_lines(name_a = "TREE",
1489
 
                                       name_b = "MERGE-SOURCE",
 
884
            for line in m3.merge_lines(name_a = "TREE", 
 
885
                                       name_b = "MERGE-SOURCE", 
1490
886
                                       name_base = "BASE-REVISION",
1491
 
                                       start_marker=start_marker,
 
887
                                       start_marker=start_marker, 
1492
888
                                       base_marker=base_marker,
1493
889
                                       reprocess=self.reprocess):
1494
890
                if line.startswith(start_marker):
1503
899
            self._raw_conflicts.append(('text conflict', trans_id))
1504
900
            name = self.tt.final_name(trans_id)
1505
901
            parent_id = self.tt.final_parent(trans_id)
1506
 
            file_group = self._dump_conflicts(name, parent_id, file_id,
 
902
            file_group = self._dump_conflicts(name, parent_id, file_id, 
1507
903
                                              this_lines, base_lines,
1508
904
                                              other_lines)
1509
905
            file_group.append(trans_id)
1510
906
 
1511
 
    def _dump_conflicts(self, name, parent_id, file_id, this_lines=None,
 
907
    def _dump_conflicts(self, name, parent_id, file_id, this_lines=None, 
1512
908
                        base_lines=None, other_lines=None, set_version=False,
1513
909
                        no_base=False):
1514
910
        """Emit conflict files.
1516
912
        determined automatically.  If set_version is true, the .OTHER, .THIS
1517
913
        or .BASE (in that order) will be created as versioned files.
1518
914
        """
1519
 
        data = [('OTHER', self.other_tree, other_lines),
 
915
        data = [('OTHER', self.other_tree, other_lines), 
1520
916
                ('THIS', self.this_tree, this_lines)]
1521
917
        if not no_base:
1522
918
            data.append(('BASE', self.base_tree, base_lines))
1523
 
 
1524
 
        # We need to use the actual path in the working tree of the file here,
1525
 
        # ignoring the conflict suffixes
1526
 
        wt = self.this_tree
1527
 
        if wt.supports_content_filtering():
1528
 
            try:
1529
 
                filter_tree_path = wt.id2path(file_id)
1530
 
            except errors.NoSuchId:
1531
 
                # file has been deleted
1532
 
                filter_tree_path = None
1533
 
        else:
1534
 
            # Skip the id2path lookup for older formats
1535
 
            filter_tree_path = None
1536
 
 
1537
919
        versioned = False
1538
920
        file_group = []
1539
921
        for suffix, tree, lines in data:
1540
 
            if tree.has_id(file_id):
 
922
            if file_id in tree:
1541
923
                trans_id = self._conflict_file(name, parent_id, tree, file_id,
1542
 
                                               suffix, lines, filter_tree_path)
 
924
                                               suffix, lines)
1543
925
                file_group.append(trans_id)
1544
926
                if set_version and not versioned:
1545
927
                    self.tt.version_file(file_id, trans_id)
1546
928
                    versioned = True
1547
929
        return file_group
1548
 
 
1549
 
    def _conflict_file(self, name, parent_id, tree, file_id, suffix,
1550
 
                       lines=None, filter_tree_path=None):
 
930
           
 
931
    def _conflict_file(self, name, parent_id, tree, file_id, suffix, 
 
932
                       lines=None):
1551
933
        """Emit a single conflict file."""
1552
934
        name = name + '.' + suffix
1553
935
        trans_id = self.tt.create_path(name, parent_id)
1554
 
        transform.create_from_tree(self.tt, trans_id, tree, file_id, lines,
1555
 
            filter_tree_path)
 
936
        entry = tree.inventory[file_id]
 
937
        create_by_entry(self.tt, entry, tree, trans_id, lines)
1556
938
        return trans_id
1557
939
 
1558
940
    def merge_executable(self, file_id, file_status):
1559
941
        """Perform a merge on the execute bit."""
1560
942
        executable = [self.executable(t, file_id) for t in (self.base_tree,
1561
943
                      self.other_tree, self.this_tree)]
1562
 
        self._merge_executable(file_id, executable, file_status,
1563
 
                               resolver=self._three_way)
 
944
        self._merge_executable(file_id, executable, file_status)
1564
945
 
1565
 
    def _merge_executable(self, file_id, executable, file_status,
1566
 
                          resolver):
 
946
    def _merge_executable(self, file_id, executable, file_status):
1567
947
        """Perform a merge on the execute bit."""
1568
948
        base_executable, other_executable, this_executable = executable
1569
949
        if file_status == "deleted":
1570
950
            return
1571
 
        winner = resolver(*executable)
 
951
        winner = self._three_way(*executable)
1572
952
        if winner == "conflict":
1573
953
        # There must be a None in here, if we have a conflict, but we
1574
954
        # need executability since file status was not deleted.
1582
962
        try:
1583
963
            if self.tt.final_kind(trans_id) != "file":
1584
964
                return
1585
 
        except errors.NoSuchFile:
 
965
        except NoSuchFile:
1586
966
            return
1587
967
        if winner == "this":
1588
968
            executability = this_executable
1589
969
        else:
1590
 
            if self.other_tree.has_id(file_id):
 
970
            if file_id in self.other_tree:
1591
971
                executability = other_executable
1592
 
            elif self.this_tree.has_id(file_id):
 
972
            elif file_id in self.this_tree:
1593
973
                executability = this_executable
1594
 
            elif self.base_tree_has_id(file_id):
 
974
            elif file_id in self.base_tree:
1595
975
                executability = base_executable
1596
976
        if executability is not None:
1597
977
            trans_id = self.tt.trans_id_file_id(file_id)
1599
979
 
1600
980
    def cook_conflicts(self, fs_conflicts):
1601
981
        """Convert all conflicts into a form that doesn't depend on trans_id"""
1602
 
        self.cooked_conflicts.extend(transform.cook_conflicts(
1603
 
                fs_conflicts, self.tt))
1604
 
        fp = transform.FinalPaths(self.tt)
 
982
        from conflicts import Conflict
 
983
        name_conflicts = {}
 
984
        self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
 
985
        fp = FinalPaths(self.tt)
1605
986
        for conflict in self._raw_conflicts:
1606
987
            conflict_type = conflict[0]
1607
 
            if conflict_type == 'path conflict':
1608
 
                (trans_id, file_id,
1609
 
                this_parent, this_name,
1610
 
                other_parent, other_name) = conflict[1:]
1611
 
                if this_parent is None or this_name is None:
1612
 
                    this_path = '<deleted>'
1613
 
                else:
1614
 
                    parent_path =  fp.get_path(
1615
 
                        self.tt.trans_id_file_id(this_parent))
1616
 
                    this_path = osutils.pathjoin(parent_path, this_name)
1617
 
                if other_parent is None or other_name is None:
1618
 
                    other_path = '<deleted>'
1619
 
                else:
1620
 
                    parent_path =  fp.get_path(
1621
 
                        self.tt.trans_id_file_id(other_parent))
1622
 
                    other_path = osutils.pathjoin(parent_path, other_name)
1623
 
                c = _mod_conflicts.Conflict.factory(
1624
 
                    'path conflict', path=this_path,
1625
 
                    conflict_path=other_path,
1626
 
                    file_id=file_id)
1627
 
            elif conflict_type == 'contents conflict':
 
988
            if conflict_type in ('name conflict', 'parent conflict'):
 
989
                trans_id = conflict[1]
 
990
                conflict_args = conflict[2:]
 
991
                if trans_id not in name_conflicts:
 
992
                    name_conflicts[trans_id] = {}
 
993
                unique_add(name_conflicts[trans_id], conflict_type, 
 
994
                           conflict_args)
 
995
            if conflict_type == 'contents conflict':
1628
996
                for trans_id in conflict[1]:
1629
997
                    file_id = self.tt.final_file_id(trans_id)
1630
998
                    if file_id is not None:
1634
1002
                    if path.endswith(suffix):
1635
1003
                        path = path[:-len(suffix)]
1636
1004
                        break
1637
 
                c = _mod_conflicts.Conflict.factory(conflict_type,
1638
 
                                                    path=path, file_id=file_id)
1639
 
            elif conflict_type == 'text conflict':
 
1005
                c = Conflict.factory(conflict_type, path=path, file_id=file_id)
 
1006
                self.cooked_conflicts.append(c)
 
1007
            if conflict_type == 'text conflict':
1640
1008
                trans_id = conflict[1]
1641
1009
                path = fp.get_path(trans_id)
1642
1010
                file_id = self.tt.final_file_id(trans_id)
1643
 
                c = _mod_conflicts.Conflict.factory(conflict_type,
1644
 
                                                    path=path, file_id=file_id)
 
1011
                c = Conflict.factory(conflict_type, path=path, file_id=file_id)
 
1012
                self.cooked_conflicts.append(c)
 
1013
 
 
1014
        for trans_id, conflicts in name_conflicts.iteritems():
 
1015
            try:
 
1016
                this_parent, other_parent = conflicts['parent conflict']
 
1017
                if this_parent == other_parent:
 
1018
                    raise AssertionError()
 
1019
            except KeyError:
 
1020
                this_parent = other_parent = \
 
1021
                    self.tt.final_file_id(self.tt.final_parent(trans_id))
 
1022
            try:
 
1023
                this_name, other_name = conflicts['name conflict']
 
1024
                if this_name == other_name:
 
1025
                    raise AssertionError()
 
1026
            except KeyError:
 
1027
                this_name = other_name = self.tt.final_name(trans_id)
 
1028
            other_path = fp.get_path(trans_id)
 
1029
            if this_parent is not None and this_name is not None:
 
1030
                this_parent_path = \
 
1031
                    fp.get_path(self.tt.trans_id_file_id(this_parent))
 
1032
                this_path = pathjoin(this_parent_path, this_name)
1645
1033
            else:
1646
 
                raise AssertionError('bad conflict type: %r' % (conflict,))
 
1034
                this_path = "<deleted>"
 
1035
            file_id = self.tt.final_file_id(trans_id)
 
1036
            c = Conflict.factory('path conflict', path=this_path,
 
1037
                                 conflict_path=other_path, file_id=file_id)
1647
1038
            self.cooked_conflicts.append(c)
1648
 
        self.cooked_conflicts.sort(key=_mod_conflicts.Conflict.sort_key)
 
1039
        self.cooked_conflicts.sort(key=Conflict.sort_key)
1649
1040
 
1650
1041
 
1651
1042
class WeaveMerger(Merge3Merger):
1655
1046
    supports_reverse_cherrypick = False
1656
1047
    history_based = True
1657
1048
 
1658
 
    def _generate_merge_plan(self, file_id, base):
1659
 
        return self.this_tree.plan_file_merge(file_id, self.other_tree,
 
1049
    def _merged_lines(self, file_id):
 
1050
        """Generate the merged lines.
 
1051
        There is no distinction between lines that are meant to contain <<<<<<<
 
1052
        and conflicts.
 
1053
        """
 
1054
        if self.cherrypick:
 
1055
            base = self.base_tree
 
1056
        else:
 
1057
            base = None
 
1058
        plan = self.this_tree.plan_file_merge(file_id, self.other_tree,
1660
1059
                                              base=base)
1661
 
 
1662
 
    def _merged_lines(self, file_id):
1663
 
        """Generate the merged lines.
1664
 
        There is no distinction between lines that are meant to contain <<<<<<<
1665
 
        and conflicts.
1666
 
        """
1667
 
        if self.cherrypick:
1668
 
            base = self.base_tree
1669
 
        else:
1670
 
            base = None
1671
 
        plan = self._generate_merge_plan(file_id, base)
1672
1060
        if 'merge' in debug.debug_flags:
1673
1061
            plan = list(plan)
1674
1062
            trans_id = self.tt.trans_id_file_id(file_id)
1675
1063
            name = self.tt.final_name(trans_id) + '.plan'
1676
 
            contents = ('%11s|%s' % l for l in plan)
 
1064
            contents = ('%10s|%s' % l for l in plan)
1677
1065
            self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
1678
 
        textmerge = versionedfile.PlanWeaveMerge(plan, '<<<<<<< TREE\n',
1679
 
                                                 '>>>>>>> MERGE-SOURCE\n')
1680
 
        lines, conflicts = textmerge.merge_lines(self.reprocess)
1681
 
        if conflicts:
1682
 
            base_lines = textmerge.base_from_plan()
1683
 
        else:
1684
 
            base_lines = None
1685
 
        return lines, base_lines
 
1066
        textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
 
1067
            '>>>>>>> MERGE-SOURCE\n')
 
1068
        return textmerge.merge_lines(self.reprocess)
1686
1069
 
1687
1070
    def text_merge(self, file_id, trans_id):
1688
1071
        """Perform a (weave) text merge for a given file and file-id.
1689
1072
        If conflicts are encountered, .THIS and .OTHER files will be emitted,
1690
1073
        and a conflict will be noted.
1691
1074
        """
1692
 
        lines, base_lines = self._merged_lines(file_id)
 
1075
        lines, conflicts = self._merged_lines(file_id)
1693
1076
        lines = list(lines)
1694
 
        # Note we're checking whether the OUTPUT is binary in this case,
 
1077
        # Note we're checking whether the OUTPUT is binary in this case, 
1695
1078
        # because we don't want to get into weave merge guts.
1696
 
        textfile.check_text_lines(lines)
 
1079
        check_text_lines(lines)
1697
1080
        self.tt.create_file(lines, trans_id)
1698
 
        if base_lines is not None:
1699
 
            # Conflict
 
1081
        if conflicts:
1700
1082
            self._raw_conflicts.append(('text conflict', trans_id))
1701
1083
            name = self.tt.final_name(trans_id)
1702
1084
            parent_id = self.tt.final_parent(trans_id)
1703
 
            file_group = self._dump_conflicts(name, parent_id, file_id,
1704
 
                                              no_base=False,
1705
 
                                              base_lines=base_lines)
 
1085
            file_group = self._dump_conflicts(name, parent_id, file_id, 
 
1086
                                              no_base=True)
1706
1087
            file_group.append(trans_id)
1707
1088
 
1708
1089
 
1709
1090
class LCAMerger(WeaveMerger):
1710
1091
 
1711
 
    def _generate_merge_plan(self, file_id, base):
1712
 
        return self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
 
1092
    def _merged_lines(self, file_id):
 
1093
        """Generate the merged lines.
 
1094
        There is no distinction between lines that are meant to contain <<<<<<<
 
1095
        and conflicts.
 
1096
        """
 
1097
        if self.cherrypick:
 
1098
            base = self.base_tree
 
1099
        else:
 
1100
            base = None
 
1101
        plan = self.this_tree.plan_file_lca_merge(file_id, self.other_tree,
1713
1102
                                                  base=base)
 
1103
        if 'merge' in debug.debug_flags:
 
1104
            plan = list(plan)
 
1105
            trans_id = self.tt.trans_id_file_id(file_id)
 
1106
            name = self.tt.final_name(trans_id) + '.plan'
 
1107
            contents = ('%10s|%s' % l for l in plan)
 
1108
            self.tt.new_file(name, self.tt.final_parent(trans_id), contents)
 
1109
        textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
 
1110
            '>>>>>>> MERGE-SOURCE\n')
 
1111
        return textmerge.merge_lines(self.reprocess)
 
1112
 
1714
1113
 
1715
1114
class Diff3Merger(Merge3Merger):
1716
1115
    """Three-way merger using external diff3 for text merging"""
1717
1116
 
1718
1117
    def dump_file(self, temp_dir, name, tree, file_id):
1719
 
        out_path = osutils.pathjoin(temp_dir, name)
 
1118
        out_path = pathjoin(temp_dir, name)
1720
1119
        out_file = open(out_path, "wb")
1721
1120
        try:
1722
1121
            in_file = tree.get_file(file_id)
1734
1133
        import bzrlib.patch
1735
1134
        temp_dir = osutils.mkdtemp(prefix="bzr-")
1736
1135
        try:
1737
 
            new_file = osutils.pathjoin(temp_dir, "new")
 
1136
            new_file = pathjoin(temp_dir, "new")
1738
1137
            this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
1739
1138
            base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
1740
1139
            other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
1741
1140
            status = bzrlib.patch.diff3(new_file, this, base, other)
1742
1141
            if status not in (0, 1):
1743
 
                raise errors.BzrError("Unhandled diff3 exit code")
 
1142
                raise BzrError("Unhandled diff3 exit code")
1744
1143
            f = open(new_file, 'rb')
1745
1144
            try:
1746
1145
                self.tt.create_file(f, trans_id)
1764
1163
                other_rev_id=None,
1765
1164
                interesting_files=None,
1766
1165
                this_tree=None,
1767
 
                pb=None,
 
1166
                pb=DummyProgress(),
1768
1167
                change_reporter=None):
1769
 
    """Primary interface for merging.
 
1168
    """Primary interface for merging. 
1770
1169
 
1771
 
        typical use is probably
 
1170
        typical use is probably 
1772
1171
        'merge_inner(branch, branch.get_revision_tree(other_revision),
1773
1172
                     branch.get_revision_tree(base_revision))'
1774
1173
        """
1775
1174
    if this_tree is None:
1776
 
        raise errors.BzrError("bzrlib.merge.merge_inner requires a this_tree "
1777
 
                              "parameter as of bzrlib version 0.8.")
 
1175
        raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
 
1176
            "parameter as of bzrlib version 0.8.")
1778
1177
    merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
1779
1178
                    pb=pb, change_reporter=change_reporter)
1780
1179
    merger.backup_files = backup_files
1793
1192
    get_revision_id = getattr(base_tree, 'get_revision_id', None)
1794
1193
    if get_revision_id is None:
1795
1194
        get_revision_id = base_tree.last_revision
1796
 
    merger.cache_trees_with_revision_ids([other_tree, base_tree, this_tree])
1797
1195
    merger.set_base_revision(get_revision_id(), this_branch)
1798
1196
    return merger.do_merge()
1799
1197
 
1842
1240
 
1843
1241
class _PlanMergeBase(object):
1844
1242
 
1845
 
    def __init__(self, a_rev, b_rev, vf, key_prefix):
 
1243
    def __init__(self, a_rev, b_rev, vf):
1846
1244
        """Contructor.
1847
1245
 
1848
1246
        :param a_rev: Revision-id of one revision to merge
1849
1247
        :param b_rev: Revision-id of the other revision to merge
1850
 
        :param vf: A VersionedFiles containing both revisions
1851
 
        :param key_prefix: A prefix for accessing keys in vf, typically
1852
 
            (file_id,).
 
1248
        :param vf: A versionedfile containing both revisions
1853
1249
        """
1854
1250
        self.a_rev = a_rev
1855
1251
        self.b_rev = b_rev
 
1252
        self.lines_a = vf.get_lines(a_rev)
 
1253
        self.lines_b = vf.get_lines(b_rev)
1856
1254
        self.vf = vf
1857
1255
        self._last_lines = None
1858
1256
        self._last_lines_revision_id = None
1859
1257
        self._cached_matching_blocks = {}
1860
 
        self._key_prefix = key_prefix
1861
 
        self._precache_tip_lines()
1862
 
 
1863
 
    def _precache_tip_lines(self):
1864
 
        lines = self.get_lines([self.a_rev, self.b_rev])
1865
 
        self.lines_a = lines[self.a_rev]
1866
 
        self.lines_b = lines[self.b_rev]
1867
 
 
1868
 
    def get_lines(self, revisions):
1869
 
        """Get lines for revisions from the backing VersionedFiles.
1870
 
 
1871
 
        :raises RevisionNotPresent: on absent texts.
1872
 
        """
1873
 
        keys = [(self._key_prefix + (rev,)) for rev in revisions]
1874
 
        result = {}
1875
 
        for record in self.vf.get_record_stream(keys, 'unordered', True):
1876
 
            if record.storage_kind == 'absent':
1877
 
                raise errors.RevisionNotPresent(record.key, self.vf)
1878
 
            result[record.key[-1]] = osutils.chunks_to_lines(
1879
 
                record.get_bytes_as('chunked'))
1880
 
        return result
1881
1258
 
1882
1259
    def plan_merge(self):
1883
1260
        """Generate a 'plan' for merging the two revisions.
1931
1308
            return cached
1932
1309
        if self._last_lines_revision_id == left_revision:
1933
1310
            left_lines = self._last_lines
1934
 
            right_lines = self.get_lines([right_revision])[right_revision]
1935
1311
        else:
1936
 
            lines = self.get_lines([left_revision, right_revision])
1937
 
            left_lines = lines[left_revision]
1938
 
            right_lines = lines[right_revision]
 
1312
            left_lines = self.vf.get_lines(left_revision)
 
1313
        right_lines = self.vf.get_lines(right_revision)
1939
1314
        self._last_lines = right_lines
1940
1315
        self._last_lines_revision_id = right_revision
1941
1316
        matcher = patiencediff.PatienceSequenceMatcher(None, left_lines,
1994
1369
class _PlanMerge(_PlanMergeBase):
1995
1370
    """Plan an annotate merge using on-the-fly annotation"""
1996
1371
 
1997
 
    def __init__(self, a_rev, b_rev, vf, key_prefix):
1998
 
        super(_PlanMerge, self).__init__(a_rev, b_rev, vf, key_prefix)
1999
 
        self.a_key = self._key_prefix + (self.a_rev,)
2000
 
        self.b_key = self._key_prefix + (self.b_rev,)
2001
 
        self.graph = _mod_graph.Graph(self.vf)
2002
 
        heads = self.graph.heads((self.a_key, self.b_key))
2003
 
        if len(heads) == 1:
2004
 
            # one side dominates, so we can just return its values, yay for
2005
 
            # per-file graphs
2006
 
            # Ideally we would know that before we get this far
2007
 
            self._head_key = heads.pop()
2008
 
            if self._head_key == self.a_key:
2009
 
                other = b_rev
2010
 
            else:
2011
 
                other = a_rev
2012
 
            trace.mutter('found dominating revision for %s\n%s > %s', self.vf,
2013
 
                         self._head_key[-1], other)
2014
 
            self._weave = None
2015
 
        else:
2016
 
            self._head_key = None
2017
 
            self._build_weave()
2018
 
 
2019
 
    def _precache_tip_lines(self):
2020
 
        # Turn this into a no-op, because we will do this later
2021
 
        pass
2022
 
 
2023
 
    def _find_recursive_lcas(self):
2024
 
        """Find all the ancestors back to a unique lca"""
2025
 
        cur_ancestors = (self.a_key, self.b_key)
2026
 
        # graph.find_lca(uncommon, keys) now returns plain NULL_REVISION,
2027
 
        # rather than a key tuple. We will just map that directly to no common
2028
 
        # ancestors.
2029
 
        parent_map = {}
2030
 
        while True:
2031
 
            next_lcas = self.graph.find_lca(*cur_ancestors)
2032
 
            # Map a plain NULL_REVISION to a simple no-ancestors
2033
 
            if next_lcas == set([_mod_revision.NULL_REVISION]):
2034
 
                next_lcas = ()
2035
 
            # Order the lca's based on when they were merged into the tip
2036
 
            # While the actual merge portion of weave merge uses a set() of
2037
 
            # active revisions, the order of insertion *does* effect the
2038
 
            # implicit ordering of the texts.
2039
 
            for rev_key in cur_ancestors:
2040
 
                ordered_parents = tuple(self.graph.find_merge_order(rev_key,
2041
 
                                                                    next_lcas))
2042
 
                parent_map[rev_key] = ordered_parents
2043
 
            if len(next_lcas) == 0:
2044
 
                break
2045
 
            elif len(next_lcas) == 1:
2046
 
                parent_map[list(next_lcas)[0]] = ()
2047
 
                break
2048
 
            elif len(next_lcas) > 2:
2049
 
                # More than 2 lca's, fall back to grabbing all nodes between
2050
 
                # this and the unique lca.
2051
 
                trace.mutter('More than 2 LCAs, falling back to all nodes for:'
2052
 
                             ' %s, %s\n=> %s',
2053
 
                             self.a_key, self.b_key, cur_ancestors)
2054
 
                cur_lcas = next_lcas
2055
 
                while len(cur_lcas) > 1:
2056
 
                    cur_lcas = self.graph.find_lca(*cur_lcas)
2057
 
                if len(cur_lcas) == 0:
2058
 
                    # No common base to find, use the full ancestry
2059
 
                    unique_lca = None
2060
 
                else:
2061
 
                    unique_lca = list(cur_lcas)[0]
2062
 
                    if unique_lca == _mod_revision.NULL_REVISION:
2063
 
                        # find_lca will return a plain 'NULL_REVISION' rather
2064
 
                        # than a key tuple when there is no common ancestor, we
2065
 
                        # prefer to just use None, because it doesn't confuse
2066
 
                        # _get_interesting_texts()
2067
 
                        unique_lca = None
2068
 
                parent_map.update(self._find_unique_parents(next_lcas,
2069
 
                                                            unique_lca))
2070
 
                break
2071
 
            cur_ancestors = next_lcas
2072
 
        return parent_map
2073
 
 
2074
 
    def _find_unique_parents(self, tip_keys, base_key):
2075
 
        """Find ancestors of tip that aren't ancestors of base.
2076
 
 
2077
 
        :param tip_keys: Nodes that are interesting
2078
 
        :param base_key: Cull all ancestors of this node
2079
 
        :return: The parent map for all revisions between tip_keys and
2080
 
            base_key. base_key will be included. References to nodes outside of
2081
 
            the ancestor set will also be removed.
2082
 
        """
2083
 
        # TODO: this would be simpler if find_unique_ancestors took a list
2084
 
        #       instead of a single tip, internally it supports it, but it
2085
 
        #       isn't a "backwards compatible" api change.
2086
 
        if base_key is None:
2087
 
            parent_map = dict(self.graph.iter_ancestry(tip_keys))
2088
 
            # We remove NULL_REVISION because it isn't a proper tuple key, and
2089
 
            # thus confuses things like _get_interesting_texts, and our logic
2090
 
            # to add the texts into the memory weave.
2091
 
            if _mod_revision.NULL_REVISION in parent_map:
2092
 
                parent_map.pop(_mod_revision.NULL_REVISION)
2093
 
        else:
2094
 
            interesting = set()
2095
 
            for tip in tip_keys:
2096
 
                interesting.update(
2097
 
                    self.graph.find_unique_ancestors(tip, [base_key]))
2098
 
            parent_map = self.graph.get_parent_map(interesting)
2099
 
            parent_map[base_key] = ()
2100
 
        culled_parent_map, child_map, tails = self._remove_external_references(
2101
 
            parent_map)
2102
 
        # Remove all the tails but base_key
2103
 
        if base_key is not None:
2104
 
            tails.remove(base_key)
2105
 
            self._prune_tails(culled_parent_map, child_map, tails)
2106
 
        # Now remove all the uninteresting 'linear' regions
2107
 
        simple_map = _mod_graph.collapse_linear_regions(culled_parent_map)
2108
 
        return simple_map
2109
 
 
2110
 
    @staticmethod
2111
 
    def _remove_external_references(parent_map):
2112
 
        """Remove references that go outside of the parent map.
2113
 
 
2114
 
        :param parent_map: Something returned from Graph.get_parent_map(keys)
2115
 
        :return: (filtered_parent_map, child_map, tails)
2116
 
            filtered_parent_map is parent_map without external references
2117
 
            child_map is the {parent_key: [child_keys]} mapping
2118
 
            tails is a list of nodes that do not have any parents in the map
2119
 
        """
2120
 
        # TODO: The basic effect of this function seems more generic than
2121
 
        #       _PlanMerge. But the specific details of building a child_map,
2122
 
        #       and computing tails seems very specific to _PlanMerge.
2123
 
        #       Still, should this be in Graph land?
2124
 
        filtered_parent_map = {}
2125
 
        child_map = {}
2126
 
        tails = []
2127
 
        for key, parent_keys in parent_map.iteritems():
2128
 
            culled_parent_keys = [p for p in parent_keys if p in parent_map]
2129
 
            if not culled_parent_keys:
2130
 
                tails.append(key)
2131
 
            for parent_key in culled_parent_keys:
2132
 
                child_map.setdefault(parent_key, []).append(key)
2133
 
            # TODO: Do we want to do this, it adds overhead for every node,
2134
 
            #       just to say that the node has no children
2135
 
            child_map.setdefault(key, [])
2136
 
            filtered_parent_map[key] = culled_parent_keys
2137
 
        return filtered_parent_map, child_map, tails
2138
 
 
2139
 
    @staticmethod
2140
 
    def _prune_tails(parent_map, child_map, tails_to_remove):
2141
 
        """Remove tails from the parent map.
2142
 
 
2143
 
        This will remove the supplied revisions until no more children have 0
2144
 
        parents.
2145
 
 
2146
 
        :param parent_map: A dict of {child: [parents]}, this dictionary will
2147
 
            be modified in place.
2148
 
        :param tails_to_remove: A list of tips that should be removed,
2149
 
            this list will be consumed
2150
 
        :param child_map: The reverse dict of parent_map ({parent: [children]})
2151
 
            this dict will be modified
2152
 
        :return: None, parent_map will be modified in place.
2153
 
        """
2154
 
        while tails_to_remove:
2155
 
            next = tails_to_remove.pop()
2156
 
            parent_map.pop(next)
2157
 
            children = child_map.pop(next)
2158
 
            for child in children:
2159
 
                child_parents = parent_map[child]
2160
 
                child_parents.remove(next)
2161
 
                if len(child_parents) == 0:
2162
 
                    tails_to_remove.append(child)
2163
 
 
2164
 
    def _get_interesting_texts(self, parent_map):
2165
 
        """Return a dict of texts we are interested in.
2166
 
 
2167
 
        Note that the input is in key tuples, but the output is in plain
2168
 
        revision ids.
2169
 
 
2170
 
        :param parent_map: The output from _find_recursive_lcas
2171
 
        :return: A dict of {'revision_id':lines} as returned by
2172
 
            _PlanMergeBase.get_lines()
2173
 
        """
2174
 
        all_revision_keys = set(parent_map)
2175
 
        all_revision_keys.add(self.a_key)
2176
 
        all_revision_keys.add(self.b_key)
2177
 
 
2178
 
        # Everything else is in 'keys' but get_lines is in 'revision_ids'
2179
 
        all_texts = self.get_lines([k[-1] for k in all_revision_keys])
2180
 
        return all_texts
2181
 
 
2182
 
    def _build_weave(self):
2183
 
        from bzrlib import weave
2184
 
        self._weave = weave.Weave(weave_name='in_memory_weave',
2185
 
                                  allow_reserved=True)
2186
 
        parent_map = self._find_recursive_lcas()
2187
 
 
2188
 
        all_texts = self._get_interesting_texts(parent_map)
2189
 
 
2190
 
        # Note: Unfortunately, the order given by topo_sort will effect the
2191
 
        # ordering resolution in the output. Specifically, if you add A then B,
2192
 
        # then in the output text A lines will show up before B lines. And, of
2193
 
        # course, topo_sort doesn't guarantee any real ordering.
2194
 
        # So we use merge_sort, and add a fake node on the tip.
2195
 
        # This ensures that left-hand parents will always be inserted into the
2196
 
        # weave before right-hand parents.
2197
 
        tip_key = self._key_prefix + (_mod_revision.CURRENT_REVISION,)
2198
 
        parent_map[tip_key] = (self.a_key, self.b_key)
2199
 
 
2200
 
        for seq_num, key, depth, eom in reversed(tsort.merge_sort(parent_map,
2201
 
                                                                  tip_key)):
2202
 
            if key == tip_key:
2203
 
                continue
2204
 
        # for key in tsort.topo_sort(parent_map):
2205
 
            parent_keys = parent_map[key]
2206
 
            revision_id = key[-1]
2207
 
            parent_ids = [k[-1] for k in parent_keys]
2208
 
            self._weave.add_lines(revision_id, parent_ids,
2209
 
                                  all_texts[revision_id])
2210
 
 
2211
 
    def plan_merge(self):
2212
 
        """Generate a 'plan' for merging the two revisions.
2213
 
 
2214
 
        This involves comparing their texts and determining the cause of
2215
 
        differences.  If text A has a line and text B does not, then either the
2216
 
        line was added to text A, or it was deleted from B.  Once the causes
2217
 
        are combined, they are written out in the format described in
2218
 
        VersionedFile.plan_merge
2219
 
        """
2220
 
        if self._head_key is not None: # There was a single head
2221
 
            if self._head_key == self.a_key:
2222
 
                plan = 'new-a'
2223
 
            else:
2224
 
                if self._head_key != self.b_key:
2225
 
                    raise AssertionError('There was an invalid head: %s != %s'
2226
 
                                         % (self.b_key, self._head_key))
2227
 
                plan = 'new-b'
2228
 
            head_rev = self._head_key[-1]
2229
 
            lines = self.get_lines([head_rev])[head_rev]
2230
 
            return ((plan, line) for line in lines)
2231
 
        return self._weave.plan_merge(self.a_rev, self.b_rev)
 
1372
    def __init__(self, a_rev, b_rev, vf):
 
1373
       _PlanMergeBase.__init__(self, a_rev, b_rev, vf)
 
1374
       a_ancestry = set(vf.get_ancestry(a_rev, topo_sorted=False))
 
1375
       b_ancestry = set(vf.get_ancestry(b_rev, topo_sorted=False))
 
1376
       self.uncommon = a_ancestry.symmetric_difference(b_ancestry)
 
1377
 
 
1378
    def _determine_status(self, revision_id, unique_line_numbers):
 
1379
        """Determines the status unique lines versus all lcas.
 
1380
 
 
1381
        Basically, determines why the line is unique to this revision.
 
1382
 
 
1383
        A line may be determined new or killed, but not both.
 
1384
 
 
1385
        :param revision_id: The id of the revision in which the lines are
 
1386
            unique
 
1387
        :param unique_line_numbers: The line numbers of unique lines.
 
1388
        :return a tuple of (new_this, killed_other):
 
1389
        """
 
1390
        new = self._find_new(revision_id)
 
1391
        killed = set(unique_line_numbers).difference(new)
 
1392
        return new, killed
 
1393
 
 
1394
    def _find_new(self, version_id):
 
1395
        """Determine which lines are new in the ancestry of this version.
 
1396
 
 
1397
        If a lines is present in this version, and not present in any
 
1398
        common ancestor, it is considered new.
 
1399
        """
 
1400
        if version_id not in self.uncommon:
 
1401
            return set()
 
1402
        parents = self.vf.get_parent_map([version_id])[version_id]
 
1403
        if len(parents) == 0:
 
1404
            return set(range(len(self.vf.get_lines(version_id))))
 
1405
        new = None
 
1406
        for parent in parents:
 
1407
            blocks = self._get_matching_blocks(version_id, parent)
 
1408
            result, unused = self._unique_lines(blocks)
 
1409
            parent_new = self._find_new(parent)
 
1410
            for i, j, n in blocks:
 
1411
                for ii, jj in [(i+r, j+r) for r in range(n)]:
 
1412
                    if jj in parent_new:
 
1413
                        result.append(ii)
 
1414
            if new is None:
 
1415
                new = set(result)
 
1416
            else:
 
1417
                new.intersection_update(result)
 
1418
        return new
2232
1419
 
2233
1420
 
2234
1421
class _PlanLCAMerge(_PlanMergeBase):
2242
1429
    This is faster, and hopefully produces more useful output.
2243
1430
    """
2244
1431
 
2245
 
    def __init__(self, a_rev, b_rev, vf, key_prefix, graph):
2246
 
        _PlanMergeBase.__init__(self, a_rev, b_rev, vf, key_prefix)
2247
 
        lcas = graph.find_lca(key_prefix + (a_rev,), key_prefix + (b_rev,))
2248
 
        self.lcas = set()
2249
 
        for lca in lcas:
2250
 
            if lca == _mod_revision.NULL_REVISION:
2251
 
                self.lcas.add(lca)
2252
 
            else:
2253
 
                self.lcas.add(lca[-1])
 
1432
    def __init__(self, a_rev, b_rev, vf, graph):
 
1433
        _PlanMergeBase.__init__(self, a_rev, b_rev, vf)
 
1434
        self.lcas = graph.find_lca(a_rev, b_rev)
2254
1435
        for lca in self.lcas:
2255
 
            if _mod_revision.is_null(lca):
2256
 
                lca_lines = []
2257
 
            else:
2258
 
                lca_lines = self.get_lines([lca])[lca]
 
1436
            lca_lines = self.vf.get_lines(lca)
2259
1437
            matcher = patiencediff.PatienceSequenceMatcher(None, self.lines_a,
2260
1438
                                                           lca_lines)
2261
1439
            blocks = list(matcher.get_matching_blocks())