~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge.py

  • Committer: Aaron Bentley
  • Date: 2007-12-12 15:17:13 UTC
  • mto: This revision was merged to the branch mainline in revision 3113.
  • Revision ID: abentley@panoramicfeedback.com-20071212151713-ox5n8rlx8m3nsspy
Add support for reconfiguring repositories into branches or trees

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2005 Canonical Ltd
2
 
 
 
1
# Copyright (C) 2005, 2006 Canonical Ltd
 
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
5
5
# the Free Software Foundation; either version 2 of the License, or
6
6
# (at your option) any later version.
7
 
 
 
7
#
8
8
# This program is distributed in the hope that it will be useful,
9
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
11
# GNU General Public License for more details.
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
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
 
18
18
import os
19
 
import shutil
20
19
import errno
 
20
import warnings
21
21
 
22
 
import bzrlib.osutils
23
 
import bzrlib.revision
24
 
from bzrlib.merge_core import merge_flex, ApplyMerge3, BackupBeforeChange
25
 
from bzrlib.merge_core import WeaveMerge
26
 
from bzrlib.changeset import generate_changeset, ExceptionConflictHandler
27
 
from bzrlib.changeset import Inventory, Diff3Merge, ReplaceContents
 
22
from bzrlib import (
 
23
    errors,
 
24
    osutils,
 
25
    patiencediff,
 
26
    registry,
 
27
    revision as _mod_revision,
 
28
    )
28
29
from bzrlib.branch import Branch
 
30
from bzrlib.conflicts import ConflictList, Conflict
29
31
from bzrlib.errors import (BzrCommandError,
30
 
                           UnrelatedBranches,
 
32
                           BzrError,
31
33
                           NoCommonAncestor,
32
34
                           NoCommits,
33
 
                           WorkingTreeNotRevision,
 
35
                           NoSuchRevision,
 
36
                           NoSuchFile,
34
37
                           NotBranchError,
35
38
                           NotVersionedError,
36
 
                           BzrError)
37
 
from bzrlib.delta import compare_trees
 
39
                           UnrelatedBranches,
 
40
                           UnsupportedOperation,
 
41
                           WorkingTreeNotRevision,
 
42
                           BinaryFile,
 
43
                           )
 
44
from bzrlib.merge3 import Merge3
 
45
from bzrlib.osutils import rename, pathjoin
 
46
from progress import DummyProgress, ProgressPhase
 
47
from bzrlib.revision import (is_ancestor, NULL_REVISION, ensure_null)
 
48
from bzrlib.textfile import check_text_lines
38
49
from bzrlib.trace import mutter, warning, note
39
 
from bzrlib.fetch import greedy_fetch, fetch
40
 
from bzrlib.revision import is_ancestor, NULL_REVISION
41
 
from bzrlib.osutils import rename, pathjoin
42
 
from bzrlib.revision import common_ancestor, MultipleRevisionSources
43
 
from bzrlib.errors import NoSuchRevision
 
50
from bzrlib.transform import (TreeTransform, resolve_conflicts, cook_conflicts,
 
51
                              conflict_pass, FinalPaths, create_by_entry,
 
52
                              unique_add, ROOT_PARENT)
 
53
from bzrlib.versionedfile import PlanWeaveMerge
 
54
from bzrlib import ui
44
55
 
45
56
# TODO: Report back as changes are merged in
46
57
 
47
 
# TODO: build_working_dir can be built on something simpler than merge()
48
 
 
49
 
# FIXME: merge() parameters seem oriented towards the command line
50
 
# NOTABUG: merge is a helper for commandline functions.  merge_inner is the
51
 
#          the core functionality.
52
 
 
53
 
# comments from abentley on irc: merge happens in two stages, each
54
 
# of which generates a changeset object
55
 
 
56
 
# stage 1: generate OLD->OTHER,
57
 
# stage 2: use MINE and OLD->OTHER to generate MINE -> RESULT
58
 
 
59
 
class MergeConflictHandler(ExceptionConflictHandler):
60
 
    """Handle conflicts encountered while merging.
61
 
 
62
 
    This subclasses ExceptionConflictHandler, so that any types of
63
 
    conflict that are not explicitly handled cause an exception and
64
 
    terminate the merge.
65
 
    """
66
 
    def __init__(self, this_tree, base_tree, other_tree, ignore_zero=False):
67
 
        ExceptionConflictHandler.__init__(self)
68
 
        self.conflicts = 0
69
 
        self.ignore_zero = ignore_zero
70
 
        self.this_tree = this_tree
71
 
        self.base_tree = base_tree
72
 
        self.other_tree = other_tree
73
 
 
74
 
    def copy(self, source, dest):
75
 
        """Copy the text and mode of a file
76
 
        :param source: The path of the file to copy
77
 
        :param dest: The distination file to create
78
 
        """
79
 
        s_file = file(source, "rb")
80
 
        d_file = file(dest, "wb")
81
 
        for line in s_file:
82
 
            d_file.write(line)
83
 
        os.chmod(dest, 0777 & os.stat(source).st_mode)
84
 
 
85
 
    def dump(self, lines, dest):
86
 
        """Copy the text and mode of a file
87
 
        :param source: The path of the file to copy
88
 
        :param dest: The distination file to create
89
 
        """
90
 
        d_file = file(dest, "wb")
91
 
        for line in lines:
92
 
            d_file.write(line)
93
 
 
94
 
    def add_suffix(self, name, suffix, last_new_name=None, fix_inventory=True):
95
 
        """Rename a file to append a suffix.  If the new name exists, the
96
 
        suffix is added repeatedly until a non-existant name is found
97
 
 
98
 
        :param name: The path of the file
99
 
        :param suffix: The suffix to append
100
 
        :param last_new_name: (used for recursive calls) the last name tried
101
 
        """
102
 
        if last_new_name is None:
103
 
            last_new_name = name
104
 
        new_name = last_new_name+suffix
105
 
        try:
106
 
            rename(name, new_name)
107
 
            if fix_inventory is True:
108
 
                try:
109
 
                    relpath = self.this_tree.relpath(name)
110
 
                except NotBranchError:
111
 
                    relpath = None
112
 
                if relpath is not None:
113
 
                    file_id = self.this_tree.path2id(relpath)
114
 
                    if file_id is not None:
115
 
                        new_path = self.this_tree.relpath(new_name)
116
 
                        rename(new_name, name)
117
 
                        self.this_tree.rename_one(relpath, new_path)
118
 
                        assert self.this_tree.id2path(file_id) == new_path
119
 
        except OSError, e:
120
 
            if e.errno != errno.EEXIST and e.errno != errno.ENOTEMPTY:
121
 
                raise
122
 
            return self.add_suffix(name, suffix, last_new_name=new_name, 
123
 
                                   fix_inventory=fix_inventory)
124
 
        return new_name
125
 
 
126
 
    def conflict(self, text):
127
 
        warning(text)
128
 
        self.conflicts += 1
129
 
        
130
 
 
131
 
    def merge_conflict(self, new_file, this_path, base_lines, other_lines):
132
 
        """
133
 
        Handle diff3 conflicts by producing a .THIS, .BASE and .OTHER.  The
134
 
        main file will be a version with diff3 conflicts.
135
 
        :param new_file: Path to the output file with diff3 markers
136
 
        :param this_path: Path to the file text for the THIS tree
137
 
        :param base_path: Path to the file text for the BASE tree
138
 
        :param other_path: Path to the file text for the OTHER tree
139
 
        """
140
 
        self.add_suffix(this_path, ".THIS", fix_inventory=False)
141
 
        self.dump(base_lines, this_path+".BASE")
142
 
        self.dump(other_lines, this_path+".OTHER")
143
 
        rename(new_file, this_path)
144
 
        self.conflict("Diff3 conflict encountered in %s" % this_path)
145
 
 
146
 
    def weave_merge_conflict(self, filename, weave, other_i, out_file):
147
 
        """
148
 
        Handle weave conflicts by producing a .THIS, and .OTHER.  The
149
 
        main file will be a version with diff3-style conflicts.
150
 
        """
151
 
        self.add_suffix(filename, ".THIS", fix_inventory=False)
152
 
        out_file.commit()
153
 
        self.dump(weave.get_iter(other_i), filename+".OTHER")
154
 
        self.conflict("Text conflict encountered in %s" % filename)
155
 
 
156
 
    def new_contents_conflict(self, filename, other_contents):
157
 
        """Conflicting contents for newly added file."""
158
 
        other_contents(filename + ".OTHER", self, False)
159
 
        self.conflict("Conflict in newly added file %s" % filename)
160
 
    
161
 
 
162
 
    def target_exists(self, entry, target, old_path):
163
 
        """Handle the case when the target file or dir exists"""
164
 
        moved_path = self.add_suffix(target, ".moved")
165
 
        self.conflict("Moved existing %s to %s" % (target, moved_path))
166
 
 
167
 
    def rmdir_non_empty(self, filename):
168
 
        """Handle the case where the dir to be removed still has contents"""
169
 
        self.conflict("Directory %s not removed because it is not empty"\
170
 
            % filename)
171
 
        return "skip"
172
 
 
173
 
    def rem_contents_conflict(self, filename, this_contents, base_contents):
174
 
        base_contents(filename+".BASE", self)
175
 
        this_contents(filename+".THIS", self)
176
 
        self.conflict("Other branch deleted locally modified file %s" %
177
 
                      filename)
178
 
        return ReplaceContents(this_contents, None)
179
 
 
180
 
    def abs_this_path(self, file_id):
181
 
        """Return the absolute path for a file_id in the this tree."""
182
 
        return self.this_tree.id2abspath(file_id)
183
 
 
184
 
    def add_missing_parents(self, file_id, tree):
185
 
        """If some of the parents for file_id are missing, add them."""
186
 
        entry = tree.inventory[file_id]
187
 
        if entry.parent_id not in self.this_tree:
188
 
            return self.create_all_missing(entry.parent_id, tree)
189
 
        else:
190
 
            return self.abs_this_path(entry.parent_id)
191
 
 
192
 
    def create_all_missing(self, file_id, tree):
193
 
        """Add contents for a file_id and all its parents to a tree."""
194
 
        entry = tree.inventory[file_id]
195
 
        if entry.parent_id is not None and entry.parent_id not in self.this_tree:
196
 
            abspath = self.create_all_missing(entry.parent_id, tree)
197
 
        else:
198
 
            abspath = self.abs_this_path(entry.parent_id)
199
 
        entry_path = pathjoin(abspath, entry.name)
200
 
        if not os.path.isdir(entry_path):
201
 
            self.create(file_id, entry_path, tree)
202
 
        return entry_path
203
 
 
204
 
    def create(self, file_id, path, tree):
205
 
        """Uses tree data to create a filesystem object for the file_id"""
206
 
        from changeset import get_contents
207
 
        get_contents(tree, file_id)(path, self)
208
 
 
209
 
    def missing_for_merge(self, file_id, other_path):
210
 
        """The file_id doesn't exist in THIS, but does in OTHER and BASE"""
211
 
        self.conflict("Other branch modified locally deleted file %s" %
212
 
                      other_path)
213
 
        parent_dir = self.add_missing_parents(file_id, self.other_tree)
214
 
        stem = pathjoin(parent_dir, os.path.basename(other_path))
215
 
        self.create(file_id, stem+".OTHER", self.other_tree)
216
 
        self.create(file_id, stem+".BASE", self.base_tree)
217
 
 
218
 
    def threeway_contents_conflict(filename, this_contents, base_contents,
219
 
                                   other_contents):
220
 
        self.conflict("Three-way conflict merging %s" % filename)
221
 
 
222
 
    def finalize(self):
223
 
        if self.conflicts == 0:
224
 
            if not self.ignore_zero:
225
 
                note("All changes applied successfully.")
226
 
        else:
227
 
            note("%d conflicts encountered." % self.conflicts)
228
 
            
229
 
def get_tree(treespec, local_branch=None):
230
 
    location, revno = treespec
231
 
    branch = Branch.open_containing(location)[0]
232
 
    if revno is None:
233
 
        revision = None
234
 
    elif revno == -1:
235
 
        revision = branch.last_revision()
236
 
    else:
237
 
        revision = branch.get_rev_id(revno)
238
 
        if revision is None:
239
 
            revision = NULL_REVISION
240
 
    return branch, get_revid_tree(branch, revision, local_branch)
241
 
 
242
 
def get_revid_tree(branch, revision, local_branch):
243
 
    if revision is None:
244
 
        base_tree = branch.working_tree()
245
 
    else:
246
 
        if local_branch is not None:
247
 
            greedy_fetch(local_branch, branch, revision)
248
 
            base_tree = local_branch.revision_tree(revision)
249
 
        else:
250
 
            base_tree = branch.revision_tree(revision)
251
 
    return base_tree
252
 
 
253
 
 
254
 
def file_exists(tree, file_id):
255
 
    return tree.has_filename(tree.id2path(file_id))
256
 
    
257
 
 
258
 
def build_working_dir(to_dir):
259
 
    """Build a working directory in an empty directory.
260
 
 
261
 
    to_dir is a directory containing branch metadata but no working files,
262
 
    typically constructed by cloning an existing branch. 
263
 
 
264
 
    This is split out as a special idiomatic case of merge.  It could
265
 
    eventually be done by just building the tree directly calling into 
266
 
    lower-level code (e.g. constructing a changeset).
267
 
    """
268
 
    # RBC 20051019 is this not just 'export' ?
269
 
    # AB Well, export doesn't take care of inventory...
270
 
    this_branch = Branch.open_containing(to_dir)[0]
271
 
    transform_tree(this_branch.working_tree(), this_branch.basis_tree())
272
 
 
273
58
 
274
59
def transform_tree(from_tree, to_tree, interesting_ids=None):
275
60
    merge_inner(from_tree.branch, to_tree, from_tree, ignore_zero=True,
276
 
                interesting_ids=interesting_ids)
277
 
 
278
 
 
279
 
def merge(other_revision, base_revision,
280
 
          check_clean=True, ignore_zero=False,
281
 
          this_dir=None, backup_files=False, merge_type=ApplyMerge3,
282
 
          file_list=None, show_base=False, reprocess=False):
283
 
    """Merge changes into a tree.
284
 
 
285
 
    base_revision
286
 
        list(path, revno) Base for three-way merge.  
287
 
        If [None, None] then a base will be automatically determined.
288
 
    other_revision
289
 
        list(path, revno) Other revision for three-way merge.
290
 
    this_dir
291
 
        Directory to merge changes into; '.' by default.
292
 
    check_clean
293
 
        If true, this_dir must have no uncommitted changes before the
294
 
        merge begins.
295
 
    ignore_zero - If true, suppress the "zero conflicts" message when 
296
 
        there are no conflicts; should be set when doing something we expect
297
 
        to complete perfectly.
298
 
    file_list - If supplied, merge only changes to selected files.
299
 
 
300
 
    All available ancestors of other_revision and base_revision are
301
 
    automatically pulled into the branch.
302
 
 
303
 
    The revno may be -1 to indicate the last revision on the branch, which is
304
 
    the typical case.
305
 
 
306
 
    This function is intended for use from the command line; programmatic
307
 
    clients might prefer to call merge_inner(), which has less magic behavior.
308
 
    """
309
 
    if this_dir is None:
310
 
        this_dir = u'.'
311
 
    this_branch = Branch.open_containing(this_dir)[0]
312
 
    if show_base and not merge_type is ApplyMerge3:
313
 
        raise BzrCommandError("Show-base is not supported for this merge"
314
 
                              " type. %s" % merge_type)
315
 
    if reprocess and not merge_type is ApplyMerge3:
316
 
        raise BzrCommandError("Reprocess is not supported for this merge"
317
 
                              " type. %s" % merge_type)
318
 
    if reprocess and show_base:
319
 
        raise BzrCommandError("Cannot reprocess and show base.")
320
 
    merger = Merger(this_branch)
321
 
    merger.check_basis(check_clean)
322
 
    merger.set_other(other_revision)
323
 
    merger.set_base(base_revision)
324
 
    if merger.base_rev_id == merger.other_rev_id:
325
 
        note('Nothing to do.')
326
 
        return 0
327
 
    merger.backup_files = backup_files
328
 
    merger.merge_type = merge_type 
329
 
    merger.set_interesting_files(file_list)
330
 
    merger.show_base = show_base 
331
 
    merger.reprocess = reprocess
332
 
    merger.conflict_handler = MergeConflictHandler(merger.this_tree, 
333
 
                                                   merger.base_tree, 
334
 
                                                   merger.other_tree,
335
 
                                                   ignore_zero=ignore_zero)
336
 
    conflicts = merger.do_merge()
337
 
    merger.set_pending()
338
 
    return conflicts
339
 
 
340
 
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
341
 
                backup_files=False, 
342
 
                merge_type=ApplyMerge3, 
343
 
                interesting_ids=None, 
344
 
                show_base=False, 
345
 
                reprocess=False, 
346
 
                other_rev_id=None,
347
 
                interesting_files=None):
348
 
    """Primary interface for merging. 
349
 
 
350
 
        typical use is probably 
351
 
        'merge_inner(branch, branch.get_revision_tree(other_revision),
352
 
                     branch.get_revision_tree(base_revision))'
353
 
        """
354
 
    merger = Merger(this_branch, other_tree, base_tree)
355
 
    merger.backup_files = backup_files
356
 
    merger.merge_type = merge_type
357
 
    merger.interesting_ids = interesting_ids
358
 
    if interesting_files:
359
 
        assert not interesting_ids, ('Only supply interesting_ids'
360
 
                                     ' or interesting_files')
361
 
        merger._set_interesting_files(interesting_files)
362
 
    merger.show_base = show_base 
363
 
    merger.reprocess = reprocess
364
 
    merger.conflict_handler = MergeConflictHandler(merger.this_tree, base_tree, 
365
 
                                                   other_tree,
366
 
                                                   ignore_zero=ignore_zero)
367
 
    merger.other_rev_id = other_rev_id
368
 
    merger.other_basis = other_rev_id
369
 
    return merger.do_merge()
 
61
                interesting_ids=interesting_ids, this_tree=from_tree)
370
62
 
371
63
 
372
64
class Merger(object):
373
 
    def __init__(self, this_branch, other_tree=None, base_tree=None):
 
65
    def __init__(self, this_branch, other_tree=None, base_tree=None,
 
66
                 this_tree=None, pb=DummyProgress(), change_reporter=None,
 
67
                 recurse='down'):
374
68
        object.__init__(self)
 
69
        assert this_tree is not None, "this_tree is required"
375
70
        self.this_branch = this_branch
376
 
        self.this_basis = this_branch.last_revision()
 
71
        self.this_basis = _mod_revision.ensure_null(
 
72
            this_branch.last_revision())
377
73
        self.this_rev_id = None
378
 
        self.this_tree = this_branch.working_tree()
 
74
        self.this_tree = this_tree
379
75
        self.this_revision_tree = None
380
76
        self.this_basis_tree = None
381
77
        self.other_tree = other_tree
 
78
        self.other_branch = None
382
79
        self.base_tree = base_tree
383
80
        self.ignore_zero = False
384
81
        self.backup_files = False
385
82
        self.interesting_ids = None
 
83
        self.interesting_files = None
386
84
        self.show_base = False
387
85
        self.reprocess = False
388
 
        self.conflict_handler = MergeConflictHandler(self.this_tree, base_tree, 
389
 
                                                     other_tree)
390
 
 
391
 
    def revision_tree(self, revision_id):
392
 
        return self.this_branch.revision_tree(revision_id)
 
86
        self._pb = pb
 
87
        self.pp = None
 
88
        self.recurse = recurse
 
89
        self.change_reporter = change_reporter
 
90
        self._cached_trees = {}
 
91
 
 
92
    @staticmethod
 
93
    def from_uncommitted(tree, other_tree, pb):
 
94
        """Return a Merger for uncommitted changes in other_tree.
 
95
 
 
96
        :param tree: The tree to merge into
 
97
        :param other_tree: The tree to get uncommitted changes from
 
98
        :param pb: A progress indicator
 
99
        """
 
100
        merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,
 
101
                        pb)
 
102
        merger.base_rev_id = merger.base_tree.get_revision_id()
 
103
        merger.other_rev_id = None
 
104
        return merger
 
105
 
 
106
    @classmethod
 
107
    def from_mergeable(klass, tree, mergeable, pb):
 
108
        """Return a Merger for a bundle or merge directive.
 
109
 
 
110
        :param tree: The tree to merge changes into
 
111
        :param mergeable: A merge directive or bundle
 
112
        :param pb: A progress indicator
 
113
        """
 
114
        mergeable.install_revisions(tree.branch.repository)
 
115
        base_revision_id, other_revision_id, verified =\
 
116
            mergeable.get_merge_request(tree.branch.repository)
 
117
        if (base_revision_id != _mod_revision.NULL_REVISION and
 
118
            tree.branch.repository.get_graph().is_ancestor(
 
119
            base_revision_id, tree.branch.last_revision())):
 
120
            base_revision_id = None
 
121
        merger = klass.from_revision_ids(pb, tree, other_revision_id,
 
122
                                         base_revision_id)
 
123
        return merger, verified
 
124
 
 
125
    @staticmethod
 
126
    def from_revision_ids(pb, this, other, base=None, other_branch=None,
 
127
                          base_branch=None):
 
128
        """Return a Merger for revision-ids.
 
129
 
 
130
        :param tree: The tree to merge changes into
 
131
        :param other: The revision-id to use as OTHER
 
132
        :param base: The revision-id to use as BASE.  If not specified, will
 
133
            be auto-selected.
 
134
        :param other_branch: A branch containing the other revision-id.  If
 
135
            not supplied, this.branch is used.
 
136
        :param base_branch: A branch containing the base revision-id.  If
 
137
            not supplied, other_branch or this.branch will be used.
 
138
        :param pb: A progress indicator
 
139
        """
 
140
        merger = Merger(this.branch, this_tree=this, pb=pb)
 
141
        if other_branch is None:
 
142
            other_branch = this.branch
 
143
        merger.set_other_revision(other, other_branch)
 
144
        if base is None:
 
145
            merger.find_base()
 
146
        else:
 
147
            if base_branch is None:
 
148
                base_branch = other_branch
 
149
            merger.set_base_revision(base, base_branch)
 
150
        return merger
 
151
 
 
152
    def revision_tree(self, revision_id, branch=None):
 
153
        if revision_id not in self._cached_trees:
 
154
            if branch is None:
 
155
                branch = self.this_branch
 
156
            try:
 
157
                tree = self.this_tree.revision_tree(revision_id)
 
158
            except errors.NoSuchRevisionInTree:
 
159
                tree = branch.repository.revision_tree(revision_id)
 
160
            self._cached_trees[revision_id] = tree
 
161
        return self._cached_trees[revision_id]
 
162
 
 
163
    def _get_tree(self, treespec, possible_transports=None):
 
164
        from bzrlib import workingtree
 
165
        location, revno = treespec
 
166
        if revno is None:
 
167
            tree = workingtree.WorkingTree.open_containing(location)[0]
 
168
            return tree.branch, tree
 
169
        branch = Branch.open_containing(location, possible_transports)[0]
 
170
        if revno == -1:
 
171
            revision_id = branch.last_revision()
 
172
        else:
 
173
            revision_id = branch.get_rev_id(revno)
 
174
        revision_id = ensure_null(revision_id)
 
175
        return branch, self.revision_tree(revision_id, branch)
393
176
 
394
177
    def ensure_revision_trees(self):
395
178
        if self.this_revision_tree is None:
396
 
            self.this_basis_tree = self.this_branch.revision_tree(
397
 
                self.this_basis)
 
179
            self.this_basis_tree = self.revision_tree(self.this_basis)
398
180
            if self.this_basis == self.this_rev_id:
399
181
                self.this_revision_tree = self.this_basis_tree
400
182
 
401
 
 
402
183
        if self.other_rev_id is None:
403
184
            other_basis_tree = self.revision_tree(self.other_basis)
404
 
            changes = compare_trees(self.other_tree, other_basis_tree)
 
185
            changes = other_basis_tree.changes_from(self.other_tree)
405
186
            if changes.has_changed():
406
187
                raise WorkingTreeNotRevision(self.this_tree)
407
 
            other_rev_id = other_basis
 
188
            other_rev_id = self.other_basis
408
189
            self.other_tree = other_basis_tree
409
190
 
410
 
 
411
191
    def file_revisions(self, file_id):
412
192
        self.ensure_revision_trees()
413
193
        def get_id(tree, file_id):
421
201
 
422
202
        trees = (self.this_basis_tree, self.other_tree)
423
203
        return [get_id(tree, file_id) for tree in trees]
424
 
            
425
 
 
426
 
    def merge_factory(self, file_id, base, other):
427
 
        if self.merge_type.history_based:
428
 
            if self.show_base is True:
429
 
                raise BzrError("Cannot show base for hisory-based merges")
430
 
            if self.reprocess is True:
431
 
                raise BzrError("Cannot reprocess history-based merges")
432
 
                
433
 
            t_revid, o_revid = self.file_revisions(file_id)
434
 
            weave = self.this_basis_tree.get_weave(file_id)
435
 
            contents_change = self.merge_type(weave, t_revid, o_revid)
436
 
        else:
437
 
            if self.show_base is True or self.reprocess is True:
438
 
                contents_change = self.merge_type(file_id, base, other, 
439
 
                                                  show_base=self.show_base, 
440
 
                                                  reprocess=self.reprocess)
441
 
            else:
442
 
                contents_change = self.merge_type(file_id, base, other)
443
 
        if self.backup_files:
444
 
            contents_change = BackupBeforeChange(contents_change)
445
 
        return contents_change
446
 
 
447
 
    def check_basis(self, check_clean):
448
 
        if self.this_basis is None:
449
 
            raise BzrCommandError("This branch has no commits")
 
204
 
 
205
    def check_basis(self, check_clean, require_commits=True):
 
206
        if self.this_basis is None and require_commits is True:
 
207
            raise BzrCommandError("This branch has no commits."
 
208
                                  " (perhaps you would prefer 'bzr pull')")
450
209
        if check_clean:
451
210
            self.compare_basis()
452
211
            if self.this_basis != self.this_rev_id:
453
 
                raise BzrCommandError("Working tree has uncommitted changes.")
 
212
                raise errors.UncommittedChanges(self.this_tree)
454
213
 
455
214
    def compare_basis(self):
456
 
        changes = compare_trees(self.this_branch.working_tree(), 
457
 
                                self.this_branch.basis_tree(), False)
 
215
        try:
 
216
            basis_tree = self.revision_tree(self.this_tree.last_revision())
 
217
        except errors.RevisionNotPresent:
 
218
            basis_tree = self.this_tree.basis_tree()
 
219
        changes = self.this_tree.changes_from(basis_tree)
458
220
        if not changes.has_changed():
459
221
            self.this_rev_id = self.this_basis
460
222
 
461
223
    def set_interesting_files(self, file_list):
462
 
        try:
463
 
            self._set_interesting_files(file_list)
464
 
        except NotVersionedError, e:
465
 
            raise BzrCommandError("%s is not a source file in any"
466
 
                                      " tree." % e.path)
467
 
 
468
 
    def _set_interesting_files(self, file_list):
469
 
        """Set the list of interesting ids from a list of files."""
470
 
        if file_list is None:
471
 
            self.interesting_ids = None
472
 
            return
473
 
 
474
 
        interesting_ids = set()
475
 
        for fname in file_list:
476
 
            path = self.this_tree.relpath(fname)
477
 
            found_id = False
478
 
            for tree in (self.this_tree, self.base_tree, self.other_tree):
479
 
                file_id = tree.inventory.path2id(path)
480
 
                if file_id is not None:
481
 
                    interesting_ids.add(file_id)
482
 
                    found_id = True
483
 
            if not found_id:
484
 
                raise NotVersionedError(path=fname)
485
 
        self.interesting_ids = interesting_ids
 
224
        self.interesting_files = file_list
486
225
 
487
226
    def set_pending(self):
488
 
        if not self.base_is_ancestor:
489
 
            return
490
 
        if self.other_rev_id is None:
491
 
            return
492
 
        if self.other_rev_id in self.this_branch.get_ancestry(self.this_basis):
493
 
            return
494
 
        self.this_branch.working_tree().add_pending_merge(self.other_rev_id)
495
 
 
496
 
    def set_other(self, other_revision):
497
 
        other_branch, self.other_tree = get_tree(other_revision, 
498
 
                                                 self.this_branch)
 
227
        if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:
 
228
            return
 
229
        self._add_parent()
 
230
 
 
231
    def _add_parent(self):
 
232
        new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]
 
233
        new_parent_trees = []
 
234
        for revision_id in new_parents:
 
235
            try:
 
236
                tree = self.revision_tree(revision_id)
 
237
            except errors.RevisionNotPresent:
 
238
                tree = None
 
239
            else:
 
240
                tree.lock_read()
 
241
            new_parent_trees.append((revision_id, tree))
 
242
        try:
 
243
            self.this_tree.set_parent_trees(new_parent_trees,
 
244
                                            allow_leftmost_as_ghost=True)
 
245
        finally:
 
246
            for _revision_id, tree in new_parent_trees:
 
247
                if tree is not None:
 
248
                    tree.unlock()
 
249
 
 
250
    def set_other(self, other_revision, possible_transports=None):
 
251
        """Set the revision and tree to merge from.
 
252
 
 
253
        This sets the other_tree, other_rev_id, other_basis attributes.
 
254
 
 
255
        :param other_revision: The [path, revision] list to merge from.
 
256
        """
 
257
        self.other_branch, self.other_tree = self._get_tree(other_revision,
 
258
                                                            possible_transports)
499
259
        if other_revision[1] == -1:
500
 
            self.other_rev_id = other_branch.last_revision()
501
 
            if self.other_rev_id is None:
502
 
                raise NoCommits(other_branch)
 
260
            self.other_rev_id = _mod_revision.ensure_null(
 
261
                self.other_branch.last_revision())
 
262
            if _mod_revision.is_null(self.other_rev_id):
 
263
                raise NoCommits(self.other_branch)
503
264
            self.other_basis = self.other_rev_id
504
265
        elif other_revision[1] is not None:
505
 
            self.other_rev_id = other_branch.get_rev_id(other_revision[1])
 
266
            self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])
506
267
            self.other_basis = self.other_rev_id
507
268
        else:
508
269
            self.other_rev_id = None
509
 
            self.other_basis = other_branch.last_revision()
 
270
            self.other_basis = self.other_branch.last_revision()
510
271
            if self.other_basis is None:
511
 
                raise NoCommits(other_branch)
512
 
        fetch(from_branch=other_branch, to_branch=self.this_branch, 
513
 
              last_revision=self.other_basis)
 
272
                raise NoCommits(self.other_branch)
 
273
        if self.other_rev_id is not None:
 
274
            self._cached_trees[self.other_rev_id] = self.other_tree
 
275
        self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)
 
276
 
 
277
    def set_other_revision(self, revision_id, other_branch):
 
278
        """Set 'other' based on a branch and revision id
 
279
 
 
280
        :param revision_id: The revision to use for a tree
 
281
        :param other_branch: The branch containing this tree
 
282
        """
 
283
        self.other_rev_id = revision_id
 
284
        self.other_branch = other_branch
 
285
        self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)
 
286
        self.other_tree = self.revision_tree(revision_id)
 
287
        self.other_basis = revision_id
 
288
 
 
289
    def set_base_revision(self, revision_id, branch):
 
290
        """Set 'base' based on a branch and revision id
 
291
 
 
292
        :param revision_id: The revision to use for a tree
 
293
        :param branch: The branch containing this tree
 
294
        """
 
295
        self.base_rev_id = revision_id
 
296
        self.base_branch = branch
 
297
        self._maybe_fetch(branch, self.this_branch, revision_id)
 
298
        self.base_tree = self.revision_tree(revision_id)
 
299
        self.base_is_ancestor = is_ancestor(self.this_basis,
 
300
                                            self.base_rev_id,
 
301
                                            self.this_branch)
 
302
        self.base_is_other_ancestor = is_ancestor(self.other_basis,
 
303
                                                  self.base_rev_id,
 
304
                                                  self.this_branch)
 
305
 
 
306
    def _maybe_fetch(self, source, target, revision_id):
 
307
        if not source.repository.has_same_location(target.repository):
 
308
            target.fetch(source, revision_id)
 
309
 
 
310
    def find_base(self):
 
311
        this_repo = self.this_branch.repository
 
312
        graph = this_repo.get_graph()
 
313
        revisions = [ensure_null(self.this_basis),
 
314
                     ensure_null(self.other_basis)]
 
315
        if NULL_REVISION in revisions:
 
316
            self.base_rev_id = NULL_REVISION
 
317
        else:
 
318
            self.base_rev_id = graph.find_unique_lca(*revisions)
 
319
            if self.base_rev_id == NULL_REVISION:
 
320
                raise UnrelatedBranches()
 
321
        self.base_tree = self.revision_tree(self.base_rev_id)
 
322
        self.base_is_ancestor = True
 
323
        self.base_is_other_ancestor = True
514
324
 
515
325
    def set_base(self, base_revision):
 
326
        """Set the base revision to use for the merge.
 
327
 
 
328
        :param base_revision: A 2-list containing a path and revision number.
 
329
        """
516
330
        mutter("doing merge() with no base_revision specified")
517
331
        if base_revision == [None, None]:
518
 
            try:
519
 
                self.base_rev_id = common_ancestor(self.this_basis, 
520
 
                                                   self.other_basis, 
521
 
                                                   self.this_branch)
522
 
            except NoCommonAncestor:
523
 
                raise UnrelatedBranches()
524
 
            self.base_tree = get_revid_tree(self.this_branch, self.base_rev_id,
525
 
                                            None)
526
 
            self.base_is_ancestor = True
 
332
            self.find_base()
527
333
        else:
528
 
            base_branch, self.base_tree = get_tree(base_revision)
 
334
            base_branch, self.base_tree = self._get_tree(base_revision)
529
335
            if base_revision[1] == -1:
530
336
                self.base_rev_id = base_branch.last_revision()
531
337
            elif base_revision[1] is None:
532
 
                self.base_rev_id = None
 
338
                self.base_rev_id = _mod_revision.NULL_REVISION
533
339
            else:
534
 
                self.base_rev_id = base_branch.get_rev_id(base_revision[1])
535
 
            fetch(from_branch=base_branch, to_branch=self.this_branch)
 
340
                self.base_rev_id = _mod_revision.ensure_null(
 
341
                    base_branch.get_rev_id(base_revision[1]))
 
342
            self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)
536
343
            self.base_is_ancestor = is_ancestor(self.this_basis, 
537
344
                                                self.base_rev_id,
538
345
                                                self.this_branch)
 
346
            self.base_is_other_ancestor = is_ancestor(self.other_basis,
 
347
                                                      self.base_rev_id,
 
348
                                                      self.this_branch)
539
349
 
540
350
    def do_merge(self):
541
 
        def get_inventory(tree):
542
 
            return tree.inventory
543
 
        
544
 
        inv_changes = merge_flex(self.this_tree, self.base_tree, 
545
 
                                 self.other_tree,
546
 
                                 generate_changeset, get_inventory,
547
 
                                 self.conflict_handler,
548
 
                                 merge_factory=self.merge_factory, 
549
 
                                 interesting_ids=self.interesting_ids)
550
 
 
551
 
        adjust_ids = []
552
 
        for id, path in inv_changes.iteritems():
553
 
            if path is not None:
554
 
                if path == u'.':
555
 
                    path = u''
 
351
        kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,
 
352
                  'other_tree': self.other_tree,
 
353
                  'interesting_ids': self.interesting_ids,
 
354
                  'interesting_files': self.interesting_files,
 
355
                  'pp': self.pp}
 
356
        if self.merge_type.requires_base:
 
357
            kwargs['base_tree'] = self.base_tree
 
358
        if self.merge_type.supports_reprocess:
 
359
            kwargs['reprocess'] = self.reprocess
 
360
        elif self.reprocess:
 
361
            raise BzrError("Conflict reduction is not supported for merge"
 
362
                                  " type %s." % self.merge_type)
 
363
        if self.merge_type.supports_show_base:
 
364
            kwargs['show_base'] = self.show_base
 
365
        elif self.show_base:
 
366
            raise BzrError("Showing base is not supported for this"
 
367
                                  " merge type. %s" % self.merge_type)
 
368
        self.this_tree.lock_tree_write()
 
369
        if self.base_tree is not None:
 
370
            self.base_tree.lock_read()
 
371
        if self.other_tree is not None:
 
372
            self.other_tree.lock_read()
 
373
        try:
 
374
            merge = self.merge_type(pb=self._pb,
 
375
                                    change_reporter=self.change_reporter,
 
376
                                    **kwargs)
 
377
            if self.recurse == 'down':
 
378
                for path, file_id in self.this_tree.iter_references():
 
379
                    sub_tree = self.this_tree.get_nested_tree(file_id, path)
 
380
                    other_revision = self.other_tree.get_reference_revision(
 
381
                        file_id, path)
 
382
                    if  other_revision == sub_tree.last_revision():
 
383
                        continue
 
384
                    sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)
 
385
                    sub_merge.merge_type = self.merge_type
 
386
                    relpath = self.this_tree.relpath(path)
 
387
                    other_branch = self.other_branch.reference_parent(file_id, relpath)
 
388
                    sub_merge.set_other_revision(other_revision, other_branch)
 
389
                    base_revision = self.base_tree.get_reference_revision(file_id)
 
390
                    sub_merge.base_tree = \
 
391
                        sub_tree.branch.repository.revision_tree(base_revision)
 
392
                    sub_merge.do_merge()
 
393
 
 
394
        finally:
 
395
            if self.other_tree is not None:
 
396
                self.other_tree.unlock()
 
397
            if self.base_tree is not None:
 
398
                self.base_tree.unlock()
 
399
            self.this_tree.unlock()
 
400
        if len(merge.cooked_conflicts) == 0:
 
401
            if not self.ignore_zero:
 
402
                note("All changes applied successfully.")
 
403
        else:
 
404
            note("%d conflicts encountered." % len(merge.cooked_conflicts))
 
405
 
 
406
        return len(merge.cooked_conflicts)
 
407
 
 
408
 
 
409
class Merge3Merger(object):
 
410
    """Three-way merger that uses the merge3 text merger"""
 
411
    requires_base = True
 
412
    supports_reprocess = True
 
413
    supports_show_base = True
 
414
    history_based = False
 
415
    winner_idx = {"this": 2, "other": 1, "conflict": 1}
 
416
 
 
417
    def __init__(self, working_tree, this_tree, base_tree, other_tree, 
 
418
                 interesting_ids=None, reprocess=False, show_base=False,
 
419
                 pb=DummyProgress(), pp=None, change_reporter=None,
 
420
                 interesting_files=None):
 
421
        """Initialize the merger object and perform the merge.
 
422
 
 
423
        :param working_tree: The working tree to apply the merge to
 
424
        :param this_tree: The local tree in the merge operation
 
425
        :param base_tree: The common tree in the merge operation
 
426
        :param other_tree: The other other tree to merge changes from
 
427
        :param interesting_ids: The file_ids of files that should be
 
428
            participate in the merge.  May not be combined with
 
429
            interesting_files.
 
430
        :param: reprocess If True, perform conflict-reduction processing.
 
431
        :param show_base: If True, show the base revision in text conflicts.
 
432
            (incompatible with reprocess)
 
433
        :param pb: A Progress bar
 
434
        :param pp: A ProgressPhase object
 
435
        :param change_reporter: An object that should report changes made
 
436
        :param interesting_files: The tree-relative paths of files that should
 
437
            participate in the merge.  If these paths refer to directories,
 
438
            the contents of those directories will also be included.  May not
 
439
            be combined with interesting_ids.  If neither interesting_files nor
 
440
            interesting_ids is specified, all files may participate in the
 
441
            merge.
 
442
        """
 
443
        object.__init__(self)
 
444
        if interesting_files is not None:
 
445
            assert interesting_ids is None
 
446
        self.interesting_ids = interesting_ids
 
447
        self.interesting_files = interesting_files
 
448
        self.this_tree = working_tree
 
449
        self.this_tree.lock_tree_write()
 
450
        self.base_tree = base_tree
 
451
        self.base_tree.lock_read()
 
452
        self.other_tree = other_tree
 
453
        self.other_tree.lock_read()
 
454
        self._raw_conflicts = []
 
455
        self.cooked_conflicts = []
 
456
        self.reprocess = reprocess
 
457
        self.show_base = show_base
 
458
        self.pb = pb
 
459
        self.pp = pp
 
460
        self.change_reporter = change_reporter
 
461
        if self.pp is None:
 
462
            self.pp = ProgressPhase("Merge phase", 3, self.pb)
 
463
 
 
464
        self.tt = TreeTransform(working_tree, self.pb)
 
465
        try:
 
466
            self.pp.next_phase()
 
467
            entries = self._entries3()
 
468
            child_pb = ui.ui_factory.nested_progress_bar()
 
469
            try:
 
470
                for num, (file_id, changed, parents3, names3,
 
471
                          executable3) in enumerate(entries):
 
472
                    child_pb.update('Preparing file merge', num, len(entries))
 
473
                    self._merge_names(file_id, parents3, names3)
 
474
                    if changed:
 
475
                        file_status = self.merge_contents(file_id)
 
476
                    else:
 
477
                        file_status = 'unmodified'
 
478
                    self._merge_executable(file_id,
 
479
                        executable3, file_status)
 
480
            finally:
 
481
                child_pb.finished()
 
482
            self.fix_root()
 
483
            self.pp.next_phase()
 
484
            child_pb = ui.ui_factory.nested_progress_bar()
 
485
            try:
 
486
                fs_conflicts = resolve_conflicts(self.tt, child_pb,
 
487
                    lambda t, c: conflict_pass(t, c, self.other_tree))
 
488
            finally:
 
489
                child_pb.finished()
 
490
            if change_reporter is not None:
 
491
                from bzrlib import delta
 
492
                delta.report_changes(self.tt._iter_changes(), change_reporter)
 
493
            self.cook_conflicts(fs_conflicts)
 
494
            for conflict in self.cooked_conflicts:
 
495
                warning(conflict)
 
496
            self.pp.next_phase()
 
497
            results = self.tt.apply(no_conflicts=True)
 
498
            self.write_modified(results)
 
499
            try:
 
500
                working_tree.add_conflicts(self.cooked_conflicts)
 
501
            except UnsupportedOperation:
 
502
                pass
 
503
        finally:
 
504
            self.tt.finalize()
 
505
            self.other_tree.unlock()
 
506
            self.base_tree.unlock()
 
507
            self.this_tree.unlock()
 
508
            self.pb.clear()
 
509
 
 
510
    def _entries3(self):
 
511
        """Gather data about files modified between three trees.
 
512
 
 
513
        Return a list of tuples of file_id, changed, parents3, names3,
 
514
        executable3.  changed is a boolean indicating whether the file contents
 
515
        or kind were changed.  parents3 is a tuple of parent ids for base,
 
516
        other and this.  names3 is a tuple of names for base, other and this.
 
517
        executable3 is a tuple of execute-bit values for base, other and this.
 
518
        """
 
519
        result = []
 
520
        iterator = self.other_tree._iter_changes(self.base_tree,
 
521
                include_unchanged=True, specific_files=self.interesting_files,
 
522
                extra_trees=[self.this_tree])
 
523
        for (file_id, paths, changed, versioned, parents, names, kind,
 
524
             executable) in iterator:
 
525
            if (self.interesting_ids is not None and
 
526
                file_id not in self.interesting_ids):
 
527
                continue
 
528
            if file_id in self.this_tree.inventory:
 
529
                entry = self.this_tree.inventory[file_id]
 
530
                this_name = entry.name
 
531
                this_parent = entry.parent_id
 
532
                this_executable = entry.executable
 
533
            else:
 
534
                this_name = None
 
535
                this_parent = None
 
536
                this_executable = None
 
537
            parents3 = parents + (this_parent,)
 
538
            names3 = names + (this_name,)
 
539
            executable3 = executable + (this_executable,)
 
540
            result.append((file_id, changed, parents3, names3, executable3))
 
541
        return result
 
542
 
 
543
    def fix_root(self):
 
544
        try:
 
545
            self.tt.final_kind(self.tt.root)
 
546
        except NoSuchFile:
 
547
            self.tt.cancel_deletion(self.tt.root)
 
548
        if self.tt.final_file_id(self.tt.root) is None:
 
549
            self.tt.version_file(self.tt.tree_file_id(self.tt.root), 
 
550
                                 self.tt.root)
 
551
        if self.other_tree.inventory.root is None:
 
552
            return
 
553
        other_root_file_id = self.other_tree.get_root_id()
 
554
        other_root = self.tt.trans_id_file_id(other_root_file_id)
 
555
        if other_root == self.tt.root:
 
556
            return
 
557
        try:
 
558
            self.tt.final_kind(other_root)
 
559
        except NoSuchFile:
 
560
            return
 
561
        self.reparent_children(self.other_tree.inventory.root, self.tt.root)
 
562
        self.tt.cancel_creation(other_root)
 
563
        self.tt.cancel_versioning(other_root)
 
564
 
 
565
    def reparent_children(self, ie, target):
 
566
        for thing, child in ie.children.iteritems():
 
567
            trans_id = self.tt.trans_id_file_id(child.file_id)
 
568
            self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)
 
569
 
 
570
    def write_modified(self, results):
 
571
        modified_hashes = {}
 
572
        for path in results.modified_paths:
 
573
            file_id = self.this_tree.path2id(self.this_tree.relpath(path))
 
574
            if file_id is None:
 
575
                continue
 
576
            hash = self.this_tree.get_file_sha1(file_id)
 
577
            if hash is None:
 
578
                continue
 
579
            modified_hashes[file_id] = hash
 
580
        self.this_tree.set_merge_modified(modified_hashes)
 
581
 
 
582
    @staticmethod
 
583
    def parent(entry, file_id):
 
584
        """Determine the parent for a file_id (used as a key method)"""
 
585
        if entry is None:
 
586
            return None
 
587
        return entry.parent_id
 
588
 
 
589
    @staticmethod
 
590
    def name(entry, file_id):
 
591
        """Determine the name for a file_id (used as a key method)"""
 
592
        if entry is None:
 
593
            return None
 
594
        return entry.name
 
595
    
 
596
    @staticmethod
 
597
    def contents_sha1(tree, file_id):
 
598
        """Determine the sha1 of the file contents (used as a key method)."""
 
599
        if file_id not in tree:
 
600
            return None
 
601
        return tree.get_file_sha1(file_id)
 
602
 
 
603
    @staticmethod
 
604
    def executable(tree, file_id):
 
605
        """Determine the executability of a file-id (used as a key method)."""
 
606
        if file_id not in tree:
 
607
            return None
 
608
        if tree.kind(file_id) != "file":
 
609
            return False
 
610
        return tree.is_executable(file_id)
 
611
 
 
612
    @staticmethod
 
613
    def kind(tree, file_id):
 
614
        """Determine the kind of a file-id (used as a key method)."""
 
615
        if file_id not in tree:
 
616
            return None
 
617
        return tree.kind(file_id)
 
618
 
 
619
    @staticmethod
 
620
    def _three_way(base, other, this):
 
621
        #if base == other, either they all agree, or only THIS has changed.
 
622
        if base == other:
 
623
            return 'this'
 
624
        elif this not in (base, other):
 
625
            return 'conflict'
 
626
        # "Ambiguous clean merge" -- both sides have made the same change.
 
627
        elif this == other:
 
628
            return "this"
 
629
        # this == base: only other has changed.
 
630
        else:
 
631
            return "other"
 
632
 
 
633
    @staticmethod
 
634
    def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):
 
635
        """Do a three-way test on a scalar.
 
636
        Return "this", "other" or "conflict", depending whether a value wins.
 
637
        """
 
638
        key_base = key(base_tree, file_id)
 
639
        key_other = key(other_tree, file_id)
 
640
        #if base == other, either they all agree, or only THIS has changed.
 
641
        if key_base == key_other:
 
642
            return "this"
 
643
        key_this = key(this_tree, file_id)
 
644
        if key_this not in (key_base, key_other):
 
645
            return "conflict"
 
646
        # "Ambiguous clean merge"
 
647
        elif key_this == key_other:
 
648
            return "this"
 
649
        else:
 
650
            assert key_this == key_base
 
651
            return "other"
 
652
 
 
653
    def merge_names(self, file_id):
 
654
        def get_entry(tree):
 
655
            if file_id in tree.inventory:
 
656
                return tree.inventory[file_id]
 
657
            else:
 
658
                return None
 
659
        this_entry = get_entry(self.this_tree)
 
660
        other_entry = get_entry(self.other_tree)
 
661
        base_entry = get_entry(self.base_tree)
 
662
        entries = (base_entry, other_entry, this_entry)
 
663
        names = []
 
664
        parents = []
 
665
        for entry in entries:
 
666
            if entry is None:
 
667
                names.append(None)
 
668
                parents.append(None)
 
669
            else:
 
670
                names.append(entry.name)
 
671
                parents.append(entry.parent_id)
 
672
        return self._merge_names(file_id, parents, names)
 
673
 
 
674
    def _merge_names(self, file_id, parents, names):
 
675
        """Perform a merge on file_id names and parents"""
 
676
        base_name, other_name, this_name = names
 
677
        base_parent, other_parent, this_parent = parents
 
678
 
 
679
        name_winner = self._three_way(*names)
 
680
 
 
681
        parent_id_winner = self._three_way(*parents)
 
682
        if this_name is None:
 
683
            if name_winner == "this":
 
684
                name_winner = "other"
 
685
            if parent_id_winner == "this":
 
686
                parent_id_winner = "other"
 
687
        if name_winner == "this" and parent_id_winner == "this":
 
688
            return
 
689
        if name_winner == "conflict":
 
690
            trans_id = self.tt.trans_id_file_id(file_id)
 
691
            self._raw_conflicts.append(('name conflict', trans_id, 
 
692
                                        this_name, other_name))
 
693
        if parent_id_winner == "conflict":
 
694
            trans_id = self.tt.trans_id_file_id(file_id)
 
695
            self._raw_conflicts.append(('parent conflict', trans_id, 
 
696
                                        this_parent, other_parent))
 
697
        if other_name is None:
 
698
            # it doesn't matter whether the result was 'other' or 
 
699
            # 'conflict'-- if there's no 'other', we leave it alone.
 
700
            return
 
701
        # if we get here, name_winner and parent_winner are set to safe values.
 
702
        trans_id = self.tt.trans_id_file_id(file_id)
 
703
        parent_id = parents[self.winner_idx[parent_id_winner]]
 
704
        if parent_id is not None:
 
705
            parent_trans_id = self.tt.trans_id_file_id(parent_id)
 
706
            self.tt.adjust_path(names[self.winner_idx[name_winner]],
 
707
                                parent_trans_id, trans_id)
 
708
 
 
709
    def merge_contents(self, file_id):
 
710
        """Performa a merge on file_id contents."""
 
711
        def contents_pair(tree):
 
712
            if file_id not in tree:
 
713
                return (None, None)
 
714
            kind = tree.kind(file_id)
 
715
            if kind == "file":
 
716
                contents = tree.get_file_sha1(file_id)
 
717
            elif kind == "symlink":
 
718
                contents = tree.get_symlink_target(file_id)
 
719
            else:
 
720
                contents = None
 
721
            return kind, contents
 
722
 
 
723
        def contents_conflict():
 
724
            trans_id = self.tt.trans_id_file_id(file_id)
 
725
            name = self.tt.final_name(trans_id)
 
726
            parent_id = self.tt.final_parent(trans_id)
 
727
            if file_id in self.this_tree.inventory:
 
728
                self.tt.unversion_file(trans_id)
 
729
                if file_id in self.this_tree:
 
730
                    self.tt.delete_contents(trans_id)
 
731
            file_group = self._dump_conflicts(name, parent_id, file_id, 
 
732
                                              set_version=True)
 
733
            self._raw_conflicts.append(('contents conflict', file_group))
 
734
 
 
735
        # See SPOT run.  run, SPOT, run.
 
736
        # So we're not QUITE repeating ourselves; we do tricky things with
 
737
        # file kind...
 
738
        base_pair = contents_pair(self.base_tree)
 
739
        other_pair = contents_pair(self.other_tree)
 
740
        if base_pair == other_pair:
 
741
            # OTHER introduced no changes
 
742
            return "unmodified"
 
743
        this_pair = contents_pair(self.this_tree)
 
744
        if this_pair == other_pair:
 
745
            # THIS and OTHER introduced the same changes
 
746
            return "unmodified"
 
747
        else:
 
748
            trans_id = self.tt.trans_id_file_id(file_id)
 
749
            if this_pair == base_pair:
 
750
                # only OTHER introduced changes
 
751
                if file_id in self.this_tree:
 
752
                    # Remove any existing contents
 
753
                    self.tt.delete_contents(trans_id)
 
754
                if file_id in self.other_tree:
 
755
                    # OTHER changed the file
 
756
                    create_by_entry(self.tt, 
 
757
                                    self.other_tree.inventory[file_id], 
 
758
                                    self.other_tree, trans_id)
 
759
                    if file_id not in self.this_tree.inventory:
 
760
                        self.tt.version_file(file_id, trans_id)
 
761
                    return "modified"
 
762
                elif file_id in self.this_tree.inventory:
 
763
                    # OTHER deleted the file
 
764
                    self.tt.unversion_file(trans_id)
 
765
                    return "deleted"
 
766
            #BOTH THIS and OTHER introduced changes; scalar conflict
 
767
            elif this_pair[0] == "file" and other_pair[0] == "file":
 
768
                # THIS and OTHER are both files, so text merge.  Either
 
769
                # BASE is a file, or both converted to files, so at least we
 
770
                # have agreement that output should be a file.
 
771
                try:
 
772
                    self.text_merge(file_id, trans_id)
 
773
                except BinaryFile:
 
774
                    return contents_conflict()
 
775
                if file_id not in self.this_tree.inventory:
 
776
                    self.tt.version_file(file_id, trans_id)
 
777
                try:
 
778
                    self.tt.tree_kind(trans_id)
 
779
                    self.tt.delete_contents(trans_id)
 
780
                except NoSuchFile:
 
781
                    pass
 
782
                return "modified"
 
783
            else:
 
784
                # Scalar conflict, can't text merge.  Dump conflicts
 
785
                return contents_conflict()
 
786
 
 
787
    def get_lines(self, tree, file_id):
 
788
        """Return the lines in a file, or an empty list."""
 
789
        if file_id in tree:
 
790
            return tree.get_file(file_id).readlines()
 
791
        else:
 
792
            return []
 
793
 
 
794
    def text_merge(self, file_id, trans_id):
 
795
        """Perform a three-way text merge on a file_id"""
 
796
        # it's possible that we got here with base as a different type.
 
797
        # if so, we just want two-way text conflicts.
 
798
        if file_id in self.base_tree and \
 
799
            self.base_tree.kind(file_id) == "file":
 
800
            base_lines = self.get_lines(self.base_tree, file_id)
 
801
        else:
 
802
            base_lines = []
 
803
        other_lines = self.get_lines(self.other_tree, file_id)
 
804
        this_lines = self.get_lines(self.this_tree, file_id)
 
805
        m3 = Merge3(base_lines, this_lines, other_lines)
 
806
        start_marker = "!START OF MERGE CONFLICT!" + "I HOPE THIS IS UNIQUE"
 
807
        if self.show_base is True:
 
808
            base_marker = '|' * 7
 
809
        else:
 
810
            base_marker = None
 
811
 
 
812
        def iter_merge3(retval):
 
813
            retval["text_conflicts"] = False
 
814
            for line in m3.merge_lines(name_a = "TREE", 
 
815
                                       name_b = "MERGE-SOURCE", 
 
816
                                       name_base = "BASE-REVISION",
 
817
                                       start_marker=start_marker, 
 
818
                                       base_marker=base_marker,
 
819
                                       reprocess=self.reprocess):
 
820
                if line.startswith(start_marker):
 
821
                    retval["text_conflicts"] = True
 
822
                    yield line.replace(start_marker, '<' * 7)
556
823
                else:
557
 
                    assert path.startswith('.' + '/') or path.startswith('.' + '\\'), "path is %s" % path
558
 
                path = path[2:]
559
 
            adjust_ids.append((path, id))
560
 
        if len(adjust_ids) > 0:
561
 
            self.this_branch.working_tree().set_inventory(self.regen_inventory(adjust_ids))
562
 
        conflicts = self.conflict_handler.conflicts
563
 
        self.conflict_handler.finalize()
564
 
        return conflicts
565
 
 
566
 
    def regen_inventory(self, new_entries):
567
 
        old_entries = self.this_branch.working_tree().read_working_inventory()
568
 
        new_inventory = {}
569
 
        by_path = {}
570
 
        new_entries_map = {} 
571
 
        for path, file_id in new_entries:
572
 
            if path is None:
573
 
                continue
574
 
            new_entries_map[file_id] = path
575
 
 
576
 
        def id2path(file_id):
577
 
            path = new_entries_map.get(file_id)
578
 
            if path is not None:
579
 
                return path
580
 
            entry = old_entries[file_id]
581
 
            if entry.parent_id is None:
582
 
                return entry.name
583
 
            return pathjoin(id2path(entry.parent_id), entry.name)
584
 
            
585
 
        for file_id in old_entries:
586
 
            entry = old_entries[file_id]
587
 
            path = id2path(file_id)
588
 
            new_inventory[file_id] = (path, file_id, entry.parent_id, 
589
 
                                      entry.kind)
590
 
            by_path[path] = file_id
591
 
        
592
 
        deletions = 0
593
 
        insertions = 0
594
 
        new_path_list = []
595
 
        for path, file_id in new_entries:
596
 
            if path is None:
597
 
                del new_inventory[file_id]
598
 
                deletions += 1
599
 
            else:
600
 
                new_path_list.append((path, file_id))
601
 
                if file_id not in old_entries:
602
 
                    insertions += 1
603
 
        # Ensure no file is added before its parent
604
 
        new_path_list.sort()
605
 
        for path, file_id in new_path_list:
606
 
            if path == '':
607
 
                parent = None
608
 
            else:
609
 
                parent = by_path[os.path.dirname(path)]
610
 
            abspath = pathjoin(self.this_tree.basedir, path)
611
 
            kind = bzrlib.osutils.file_kind(abspath)
612
 
            new_inventory[file_id] = (path, file_id, parent, kind)
613
 
            by_path[path] = file_id 
614
 
 
615
 
        # Get a list in insertion order
616
 
        new_inventory_list = new_inventory.values()
617
 
        mutter ("""Inventory regeneration:
618
 
    old length: %i insertions: %i deletions: %i new_length: %i"""\
619
 
            % (len(old_entries), insertions, deletions, 
620
 
               len(new_inventory_list)))
621
 
        assert len(new_inventory_list) == len(old_entries) + insertions\
622
 
            - deletions
623
 
        new_inventory_list.sort()
624
 
        return new_inventory_list
625
 
 
626
 
merge_types = {     "merge3": (ApplyMerge3, "Native diff3-style merge"), 
627
 
                     "diff3": (Diff3Merge,  "Merge using external diff3"),
628
 
                     'weave': (WeaveMerge, "Weave-based merge")
629
 
              }
630
 
 
 
824
                    yield line
 
825
        retval = {}
 
826
        merge3_iterator = iter_merge3(retval)
 
827
        self.tt.create_file(merge3_iterator, trans_id)
 
828
        if retval["text_conflicts"] is True:
 
829
            self._raw_conflicts.append(('text conflict', trans_id))
 
830
            name = self.tt.final_name(trans_id)
 
831
            parent_id = self.tt.final_parent(trans_id)
 
832
            file_group = self._dump_conflicts(name, parent_id, file_id, 
 
833
                                              this_lines, base_lines,
 
834
                                              other_lines)
 
835
            file_group.append(trans_id)
 
836
 
 
837
    def _dump_conflicts(self, name, parent_id, file_id, this_lines=None, 
 
838
                        base_lines=None, other_lines=None, set_version=False,
 
839
                        no_base=False):
 
840
        """Emit conflict files.
 
841
        If this_lines, base_lines, or other_lines are omitted, they will be
 
842
        determined automatically.  If set_version is true, the .OTHER, .THIS
 
843
        or .BASE (in that order) will be created as versioned files.
 
844
        """
 
845
        data = [('OTHER', self.other_tree, other_lines), 
 
846
                ('THIS', self.this_tree, this_lines)]
 
847
        if not no_base:
 
848
            data.append(('BASE', self.base_tree, base_lines))
 
849
        versioned = False
 
850
        file_group = []
 
851
        for suffix, tree, lines in data:
 
852
            if file_id in tree:
 
853
                trans_id = self._conflict_file(name, parent_id, tree, file_id,
 
854
                                               suffix, lines)
 
855
                file_group.append(trans_id)
 
856
                if set_version and not versioned:
 
857
                    self.tt.version_file(file_id, trans_id)
 
858
                    versioned = True
 
859
        return file_group
 
860
           
 
861
    def _conflict_file(self, name, parent_id, tree, file_id, suffix, 
 
862
                       lines=None):
 
863
        """Emit a single conflict file."""
 
864
        name = name + '.' + suffix
 
865
        trans_id = self.tt.create_path(name, parent_id)
 
866
        entry = tree.inventory[file_id]
 
867
        create_by_entry(self.tt, entry, tree, trans_id, lines)
 
868
        return trans_id
 
869
 
 
870
    def merge_executable(self, file_id, file_status):
 
871
        """Perform a merge on the execute bit."""
 
872
        executable = [self.executable(t, file_id) for t in (self.base_tree,
 
873
                      self.other_tree, self.this_tree)]
 
874
        self._merge_executable(file_id, executable, file_status)
 
875
 
 
876
    def _merge_executable(self, file_id, executable, file_status):
 
877
        """Perform a merge on the execute bit."""
 
878
        base_executable, other_executable, this_executable = executable
 
879
        if file_status == "deleted":
 
880
            return
 
881
        trans_id = self.tt.trans_id_file_id(file_id)
 
882
        try:
 
883
            if self.tt.final_kind(trans_id) != "file":
 
884
                return
 
885
        except NoSuchFile:
 
886
            return
 
887
        winner = self._three_way(*executable)
 
888
        if winner == "conflict":
 
889
        # There must be a None in here, if we have a conflict, but we
 
890
        # need executability since file status was not deleted.
 
891
            if self.executable(self.other_tree, file_id) is None:
 
892
                winner = "this"
 
893
            else:
 
894
                winner = "other"
 
895
        if winner == "this":
 
896
            if file_status == "modified":
 
897
                executability = this_executable
 
898
                if executability is not None:
 
899
                    trans_id = self.tt.trans_id_file_id(file_id)
 
900
                    self.tt.set_executability(executability, trans_id)
 
901
        else:
 
902
            assert winner == "other"
 
903
            if file_id in self.other_tree:
 
904
                executability = other_executable
 
905
            elif file_id in self.this_tree:
 
906
                executability = this_executable
 
907
            elif file_id in self.base_tree:
 
908
                executability = base_executable
 
909
            if executability is not None:
 
910
                trans_id = self.tt.trans_id_file_id(file_id)
 
911
                self.tt.set_executability(executability, trans_id)
 
912
 
 
913
    def cook_conflicts(self, fs_conflicts):
 
914
        """Convert all conflicts into a form that doesn't depend on trans_id"""
 
915
        from conflicts import Conflict
 
916
        name_conflicts = {}
 
917
        self.cooked_conflicts.extend(cook_conflicts(fs_conflicts, self.tt))
 
918
        fp = FinalPaths(self.tt)
 
919
        for conflict in self._raw_conflicts:
 
920
            conflict_type = conflict[0]
 
921
            if conflict_type in ('name conflict', 'parent conflict'):
 
922
                trans_id = conflict[1]
 
923
                conflict_args = conflict[2:]
 
924
                if trans_id not in name_conflicts:
 
925
                    name_conflicts[trans_id] = {}
 
926
                unique_add(name_conflicts[trans_id], conflict_type, 
 
927
                           conflict_args)
 
928
            if conflict_type == 'contents conflict':
 
929
                for trans_id in conflict[1]:
 
930
                    file_id = self.tt.final_file_id(trans_id)
 
931
                    if file_id is not None:
 
932
                        break
 
933
                path = fp.get_path(trans_id)
 
934
                for suffix in ('.BASE', '.THIS', '.OTHER'):
 
935
                    if path.endswith(suffix):
 
936
                        path = path[:-len(suffix)]
 
937
                        break
 
938
                c = Conflict.factory(conflict_type, path=path, file_id=file_id)
 
939
                self.cooked_conflicts.append(c)
 
940
            if conflict_type == 'text conflict':
 
941
                trans_id = conflict[1]
 
942
                path = fp.get_path(trans_id)
 
943
                file_id = self.tt.final_file_id(trans_id)
 
944
                c = Conflict.factory(conflict_type, path=path, file_id=file_id)
 
945
                self.cooked_conflicts.append(c)
 
946
 
 
947
        for trans_id, conflicts in name_conflicts.iteritems():
 
948
            try:
 
949
                this_parent, other_parent = conflicts['parent conflict']
 
950
                assert this_parent != other_parent
 
951
            except KeyError:
 
952
                this_parent = other_parent = \
 
953
                    self.tt.final_file_id(self.tt.final_parent(trans_id))
 
954
            try:
 
955
                this_name, other_name = conflicts['name conflict']
 
956
                assert this_name != other_name
 
957
            except KeyError:
 
958
                this_name = other_name = self.tt.final_name(trans_id)
 
959
            other_path = fp.get_path(trans_id)
 
960
            if this_parent is not None and this_name is not None:
 
961
                this_parent_path = \
 
962
                    fp.get_path(self.tt.trans_id_file_id(this_parent))
 
963
                this_path = pathjoin(this_parent_path, this_name)
 
964
            else:
 
965
                this_path = "<deleted>"
 
966
            file_id = self.tt.final_file_id(trans_id)
 
967
            c = Conflict.factory('path conflict', path=this_path,
 
968
                                 conflict_path=other_path, file_id=file_id)
 
969
            self.cooked_conflicts.append(c)
 
970
        self.cooked_conflicts.sort(key=Conflict.sort_key)
 
971
 
 
972
 
 
973
class WeaveMerger(Merge3Merger):
 
974
    """Three-way tree merger, text weave merger."""
 
975
    supports_reprocess = True
 
976
    supports_show_base = False
 
977
 
 
978
    def __init__(self, working_tree, this_tree, base_tree, other_tree, 
 
979
                 interesting_ids=None, pb=DummyProgress(), pp=None,
 
980
                 reprocess=False, change_reporter=None,
 
981
                 interesting_files=None):
 
982
        super(WeaveMerger, self).__init__(working_tree, this_tree, 
 
983
                                          base_tree, other_tree, 
 
984
                                          interesting_ids=interesting_ids, 
 
985
                                          pb=pb, pp=pp, reprocess=reprocess,
 
986
                                          change_reporter=change_reporter)
 
987
 
 
988
    def _merged_lines(self, file_id):
 
989
        """Generate the merged lines.
 
990
        There is no distinction between lines that are meant to contain <<<<<<<
 
991
        and conflicts.
 
992
        """
 
993
        plan = self.this_tree.plan_file_merge(file_id, self.other_tree)
 
994
        textmerge = PlanWeaveMerge(plan, '<<<<<<< TREE\n',
 
995
            '>>>>>>> MERGE-SOURCE\n')
 
996
        return textmerge.merge_lines(self.reprocess)
 
997
 
 
998
    def text_merge(self, file_id, trans_id):
 
999
        """Perform a (weave) text merge for a given file and file-id.
 
1000
        If conflicts are encountered, .THIS and .OTHER files will be emitted,
 
1001
        and a conflict will be noted.
 
1002
        """
 
1003
        lines, conflicts = self._merged_lines(file_id)
 
1004
        lines = list(lines)
 
1005
        # Note we're checking whether the OUTPUT is binary in this case, 
 
1006
        # because we don't want to get into weave merge guts.
 
1007
        check_text_lines(lines)
 
1008
        self.tt.create_file(lines, trans_id)
 
1009
        if conflicts:
 
1010
            self._raw_conflicts.append(('text conflict', trans_id))
 
1011
            name = self.tt.final_name(trans_id)
 
1012
            parent_id = self.tt.final_parent(trans_id)
 
1013
            file_group = self._dump_conflicts(name, parent_id, file_id, 
 
1014
                                              no_base=True)
 
1015
            file_group.append(trans_id)
 
1016
 
 
1017
 
 
1018
class Diff3Merger(Merge3Merger):
 
1019
    """Three-way merger using external diff3 for text merging"""
 
1020
 
 
1021
    def dump_file(self, temp_dir, name, tree, file_id):
 
1022
        out_path = pathjoin(temp_dir, name)
 
1023
        out_file = open(out_path, "wb")
 
1024
        try:
 
1025
            in_file = tree.get_file(file_id)
 
1026
            for line in in_file:
 
1027
                out_file.write(line)
 
1028
        finally:
 
1029
            out_file.close()
 
1030
        return out_path
 
1031
 
 
1032
    def text_merge(self, file_id, trans_id):
 
1033
        """Perform a diff3 merge using a specified file-id and trans-id.
 
1034
        If conflicts are encountered, .BASE, .THIS. and .OTHER conflict files
 
1035
        will be dumped, and a will be conflict noted.
 
1036
        """
 
1037
        import bzrlib.patch
 
1038
        temp_dir = osutils.mkdtemp(prefix="bzr-")
 
1039
        try:
 
1040
            new_file = pathjoin(temp_dir, "new")
 
1041
            this = self.dump_file(temp_dir, "this", self.this_tree, file_id)
 
1042
            base = self.dump_file(temp_dir, "base", self.base_tree, file_id)
 
1043
            other = self.dump_file(temp_dir, "other", self.other_tree, file_id)
 
1044
            status = bzrlib.patch.diff3(new_file, this, base, other)
 
1045
            if status not in (0, 1):
 
1046
                raise BzrError("Unhandled diff3 exit code")
 
1047
            f = open(new_file, 'rb')
 
1048
            try:
 
1049
                self.tt.create_file(f, trans_id)
 
1050
            finally:
 
1051
                f.close()
 
1052
            if status == 1:
 
1053
                name = self.tt.final_name(trans_id)
 
1054
                parent_id = self.tt.final_parent(trans_id)
 
1055
                self._dump_conflicts(name, parent_id, file_id)
 
1056
                self._raw_conflicts.append(('text conflict', trans_id))
 
1057
        finally:
 
1058
            osutils.rmtree(temp_dir)
 
1059
 
 
1060
 
 
1061
def merge_inner(this_branch, other_tree, base_tree, ignore_zero=False,
 
1062
                backup_files=False,
 
1063
                merge_type=Merge3Merger,
 
1064
                interesting_ids=None,
 
1065
                show_base=False,
 
1066
                reprocess=False,
 
1067
                other_rev_id=None,
 
1068
                interesting_files=None,
 
1069
                this_tree=None,
 
1070
                pb=DummyProgress(),
 
1071
                change_reporter=None):
 
1072
    """Primary interface for merging. 
 
1073
 
 
1074
        typical use is probably 
 
1075
        'merge_inner(branch, branch.get_revision_tree(other_revision),
 
1076
                     branch.get_revision_tree(base_revision))'
 
1077
        """
 
1078
    if this_tree is None:
 
1079
        raise BzrError("bzrlib.merge.merge_inner requires a this_tree "
 
1080
            "parameter as of bzrlib version 0.8.")
 
1081
    merger = Merger(this_branch, other_tree, base_tree, this_tree=this_tree,
 
1082
                    pb=pb, change_reporter=change_reporter)
 
1083
    merger.backup_files = backup_files
 
1084
    merger.merge_type = merge_type
 
1085
    merger.interesting_ids = interesting_ids
 
1086
    merger.ignore_zero = ignore_zero
 
1087
    if interesting_files:
 
1088
        assert not interesting_ids, ('Only supply interesting_ids'
 
1089
                                     ' or interesting_files')
 
1090
        merger.interesting_files = interesting_files
 
1091
    merger.show_base = show_base
 
1092
    merger.reprocess = reprocess
 
1093
    merger.other_rev_id = other_rev_id
 
1094
    merger.other_basis = other_rev_id
 
1095
    return merger.do_merge()
 
1096
 
 
1097
def get_merge_type_registry():
 
1098
    """Merge type registry is in bzrlib.option to avoid circular imports.
 
1099
 
 
1100
    This method provides a sanctioned way to retrieve it.
 
1101
    """
 
1102
    from bzrlib import option
 
1103
    return option._merge_type_registry
 
1104
 
 
1105
 
 
1106
def _plan_annotate_merge(annotated_a, annotated_b, ancestors_a, ancestors_b):
 
1107
    def status_a(revision, text):
 
1108
        if revision in ancestors_b:
 
1109
            return 'killed-b', text
 
1110
        else:
 
1111
            return 'new-a', text
 
1112
 
 
1113
    def status_b(revision, text):
 
1114
        if revision in ancestors_a:
 
1115
            return 'killed-a', text
 
1116
        else:
 
1117
            return 'new-b', text
 
1118
 
 
1119
    plain_a = [t for (a, t) in annotated_a]
 
1120
    plain_b = [t for (a, t) in annotated_b]
 
1121
    matcher = patiencediff.PatienceSequenceMatcher(None, plain_a, plain_b)
 
1122
    blocks = matcher.get_matching_blocks()
 
1123
    a_cur = 0
 
1124
    b_cur = 0
 
1125
    for ai, bi, l in blocks:
 
1126
        # process all mismatched sections
 
1127
        # (last mismatched section is handled because blocks always
 
1128
        # includes a 0-length last block)
 
1129
        for revision, text in annotated_a[a_cur:ai]:
 
1130
            yield status_a(revision, text)
 
1131
        for revision, text in annotated_b[b_cur:bi]:
 
1132
            yield status_b(revision, text)
 
1133
 
 
1134
        # and now the matched section
 
1135
        a_cur = ai + l
 
1136
        b_cur = bi + l
 
1137
        for text_a, text_b in zip(plain_a[ai:a_cur], plain_b[bi:b_cur]):
 
1138
            assert text_a == text_b
 
1139
            yield "unchanged", text_a