~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: Vincent Ladeuil
  • Date: 2007-10-09 20:32:29 UTC
  • mto: (2903.1.1 trunk)
  • mto: This revision was merged to the branch mainline in revision 2904.
  • Revision ID: v.ladeuil+lp@free.fr-20071009203229-5k200m1g7mf4jf9l
Fix 149019 by using a proper line number when reporting errors.

* bzrlib/util/configobj/configobj.py:
(ConfigObj._handle_error): Trivial fix. Since cur_index is
0-based, line number was off by one.

Show diffs side-by-side

added added

removed removed

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