~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: mbp at sourcefrog
  • Date: 2005-03-28 10:10:23 UTC
  • Revision ID: mbp@sourcefrog.net-20050328101023-ff2d0426c40cba72
Update news

Show diffs side-by-side

added added

removed removed

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