~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: Robert Collins
  • Date: 2010-04-08 04:34:03 UTC
  • mfrom: (5138 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5139.
  • Revision ID: robertc@robertcollins.net-20100408043403-56z0d07vdqrx7f3t
Update bugfix for 528114 to trunk.

Show diffs side-by-side

added added

removed removed

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