/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

Merge 2.0 into 2.1 including fixes for #262450, #373898, #498409

Show diffs side-by-side

added added

removed removed

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