~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

Switched from actual, expected to expected, actual, for John.

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