~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: Martin Packman
  • Date: 2011-12-23 19:38:22 UTC
  • mto: This revision was merged to the branch mainline in revision 6405.
  • Revision ID: martin.packman@canonical.com-20111223193822-hesheea4o8aqwexv
Accept and document passing the medium rather than transport for smart connections

Show diffs side-by-side

added added

removed removed

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