← Back to branch summary

~bzr/ubuntu/lucid/bzr/beta-ppa

« back to all changes in this revision

Viewing changes to bzrlib/annotate.py

  • Committer: Martin Pool
  • Date: 2010-07-02 07:29:40 UTC
  • mfrom: (129.1.7 packaging-karmic)
  • Revision ID: mbp@sourcefrog.net-20100702072940-hpzq5elg8wjve8rh
http://bugs.debian.org/452024
http://bugs.debian.org/464688
http://bugs.debian.org/523595
http://bugs.debian.org/526233
http://bugs.debian.org/537708
http://bugs.debian.org/555336
http://bugs.debian.org/555343
https://launchpad.net/bugs/249452
https://launchpad.net/bugs/385074
* PPA rebuild.
* PPA rebuild for Karmic.
* PPA rebuild for Jaunty.
* PPA rebuild for Hardy.
* From postinst, actually remove the example bash completion scripts.
  (LP: #249452)
* New upstream release.
* New upstream release.
* New upstream release.
* Revert change to Build-depends: Dapper does not have python-central.
  Should be python-support..
* Target ppa..
* Target ppa..
* Target ppa..
* Target ppa..
* New upstream release.
* Switch to dpkg-source 3.0 (quilt) format.
* Bump standards version to 3.8.4.
* Remove embedded copy of python-configobj. Closes: #555336
* Remove embedded copy of python-elementtree. Closes: #555343
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* debian/control: Fix obsolete-relation-form-in-source
  lintian warning. 
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split out docs into bzr-doc package.
* New upstream release.
* Added John Francesco Ferlito to Uploaders.
* Fix install path to quick-reference guide
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again, again.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to path changes.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Bump standards version to 3.8.3.
* Remove unused patch system.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix copy and paste tab error in .install file
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
 + Fixes compatibility with Python 2.4. Closes: #537708
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream version.
* Bump standards version to 3.8.2.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add python-pyrex to build-deps to ensure C extensions are always build.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix API compatibility version. (Closes: #526233)
* New upstream release.
  + Fixes default format for upgrade command. (Closes: #464688)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add missing dependency on zlib development library. (Closes:
  #523595)
* Add zlib build-depends.
* Add zlib build-depends.
* Add zlib build-depends.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Move to section vcs.
* Bump standards version to 3.8.1.
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Recommend ca-certificates. (Closes: #452024)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Update watch file. bazaar now uses launchpad to host its sources.
* Remove patch for inventory root revision copy, applied upstream.
* New upstream release.
* New upstream release.
* New upstream release
* Force removal of files installed in error to /etc/bash_completion.d/
  (LP: #249452)
* New upstream release.
* New upstream release
* New upstream release.
* Bump standards version.
* Include patch for inventory root revision copy, required for bzr-svn.
* New upstream release.
* Remove unused lintian overrides.
* Correct the package version not to be native.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Final 1.5 release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add myself as a co-maintainer.
* Add a Dm-Upload-Allowed: yes header.
* New upstream bugfix release.
* New upstream release.
* Final 1.3 release.
* New upstream release.
* First release candidate of the upcoming 1.3 release.
* Rebuild to fix the problem caused by a build with a broken python-central.
* New upstream release.
* Rebuild for dapper PPA.
* Apply Lamont's patches to fix build-dependencies on dapper.
  (See: https://bugs.launchpad.net/bzr/+bug/189915)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/annotate.py
 
1
# Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
"""File annotate based on weave storage"""
 
18
 
 
19
# TODO: Choice of more or less verbose formats:
 
20
#
 
21
# interposed: show more details between blocks of modified lines
 
22
 
 
23
# TODO: Show which revision caused a line to merge into the parent
 
24
 
 
25
# TODO: perhaps abbreviate timescales depending on how recent they are
 
26
# e.g. "3:12 Tue", "13 Oct", "Oct 2005", etc.
 
27
 
 
28
import sys
 
29
import time
 
30
 
 
31
from bzrlib import (
 
32
    errors,
 
33
    osutils,
 
34
    patiencediff,
 
35
    tsort,
 
36
    )
 
37
from bzrlib.config import extract_email_address
 
38
from bzrlib.repository import _strip_NULL_ghosts
 
39
from bzrlib.revision import CURRENT_REVISION, Revision
 
40
 
 
41
 
 
42
def annotate_file(branch, rev_id, file_id, verbose=False, full=False,
 
43
                  to_file=None, show_ids=False):
 
44
    """Annotate file_id at revision rev_id in branch.
 
45
 
 
46
    The branch should already be read_locked() when annotate_file is called.
 
47
 
 
48
    :param branch: The branch to look for revision numbers and history from.
 
49
    :param rev_id: The revision id to annotate.
 
50
    :param file_id: The file_id to annotate.
 
51
    :param verbose: Show all details rather than truncating to ensure
 
52
        reasonable text width.
 
53
    :param full: XXXX Not sure what this does.
 
54
    :param to_file: The file to output the annotation to; if None stdout is
 
55
        used.
 
56
    :param show_ids: Show revision ids in the annotation output.
 
57
    """
 
58
    if to_file is None:
 
59
        to_file = sys.stdout
 
60
 
 
61
    # Handle the show_ids case
 
62
    annotations = _annotations(branch.repository, file_id, rev_id)
 
63
    if show_ids:
 
64
        return _show_id_annotations(annotations, to_file, full)
 
65
 
 
66
    # Calculate the lengths of the various columns
 
67
    annotation = list(_expand_annotations(annotations, branch))
 
68
    _print_annotations(annotation, verbose, to_file, full)
 
69
 
 
70
 
 
71
def annotate_file_tree(tree, file_id, to_file, verbose=False, full=False,
 
72
    show_ids=False):
 
73
    """Annotate file_id in a tree.
 
74
 
 
75
    The tree should already be read_locked() when annotate_file_tree is called.
 
76
 
 
77
    :param tree: The tree to look for revision numbers and history from.
 
78
    :param file_id: The file_id to annotate.
 
79
    :param to_file: The file to output the annotation to.
 
80
    :param verbose: Show all details rather than truncating to ensure
 
81
        reasonable text width.
 
82
    :param full: XXXX Not sure what this does.
 
83
    :param show_ids: Show revision ids in the annotation output.
 
84
    """
 
85
    rev_id = tree.last_revision()
 
86
    branch = tree.branch
 
87
 
 
88
    # Handle the show_ids case
 
89
    annotations = list(tree.annotate_iter(file_id))
 
90
    if show_ids:
 
91
        return _show_id_annotations(annotations, to_file, full)
 
92
 
 
93
    # Create a virtual revision to represent the current tree state.
 
94
    # Should get some more pending commit attributes, like pending tags,
 
95
    # bugfixes etc.
 
96
    current_rev = Revision(CURRENT_REVISION)
 
97
    current_rev.parent_ids = tree.get_parent_ids()
 
98
    current_rev.committer = tree.branch.get_config().username()
 
99
    current_rev.message = "?"
 
100
    current_rev.timestamp = round(time.time(), 3)
 
101
    current_rev.timezone = osutils.local_time_offset()
 
102
    annotation = list(_expand_annotations(annotations, tree.branch,
 
103
        current_rev))
 
104
    _print_annotations(annotation, verbose, to_file, full)
 
105
 
 
106
 
 
107
def _print_annotations(annotation, verbose, to_file, full):
 
108
    """Print annotations to to_file.
 
109
 
 
110
    :param to_file: The file to output the annotation to.
 
111
    :param verbose: Show all details rather than truncating to ensure
 
112
        reasonable text width.
 
113
    :param full: XXXX Not sure what this does.
 
114
    """
 
115
    if len(annotation) == 0:
 
116
        max_origin_len = max_revno_len = max_revid_len = 0
 
117
    else:
 
118
        max_origin_len = max(len(x[1]) for x in annotation)
 
119
        max_revno_len = max(len(x[0]) for x in annotation)
 
120
        max_revid_len = max(len(x[3]) for x in annotation)
 
121
    if not verbose:
 
122
        max_revno_len = min(max_revno_len, 12)
 
123
    max_revno_len = max(max_revno_len, 3)
 
124
 
 
125
    # Output the annotations
 
126
    prevanno = ''
 
127
    encoding = getattr(to_file, 'encoding', None) or \
 
128
            osutils.get_terminal_encoding()
 
129
    for (revno_str, author, date_str, line_rev_id, text) in annotation:
 
130
        if verbose:
 
131
            anno = '%-*s %-*s %8s ' % (max_revno_len, revno_str,
 
132
                                       max_origin_len, author, date_str)
 
133
        else:
 
134
            if len(revno_str) > max_revno_len:
 
135
                revno_str = revno_str[:max_revno_len-1] + '>'
 
136
            anno = "%-*s %-7s " % (max_revno_len, revno_str, author[:7])
 
137
        if anno.lstrip() == "" and full:
 
138
            anno = prevanno
 
139
        try:
 
140
            to_file.write(anno)
 
141
        except UnicodeEncodeError:
 
142
            # cmd_annotate should be passing in an 'exact' object, which means
 
143
            # we have a direct handle to sys.stdout or equivalent. It may not
 
144
            # be able to handle the exact Unicode characters, but 'annotate' is
 
145
            # a user function (non-scripting), so shouldn't die because of
 
146
            # unrepresentable annotation characters. So encode using 'replace',
 
147
            # and write them again.
 
148
            to_file.write(anno.encode(encoding, 'replace'))
 
149
        to_file.write('| %s\n' % (text,))
 
150
        prevanno = anno
 
151
 
 
152
 
 
153
def _show_id_annotations(annotations, to_file, full):
 
154
    if not annotations:
 
155
        return
 
156
    last_rev_id = None
 
157
    max_origin_len = max(len(origin) for origin, text in annotations)
 
158
    for origin, text in annotations:
 
159
        if full or last_rev_id != origin:
 
160
            this = origin
 
161
        else:
 
162
            this = ''
 
163
        to_file.write('%*s | %s' % (max_origin_len, this, text))
 
164
        last_rev_id = origin
 
165
    return
 
166
 
 
167
 
 
168
def _annotations(repo, file_id, rev_id):
 
169
    """Return the list of (origin_revision_id, line_text) for a revision of a file in a repository."""
 
170
    annotations = repo.texts.annotate((file_id, rev_id))
 
171
    #
 
172
    return [(key[-1], line) for (key, line) in annotations]
 
173
 
 
174
 
 
175
def _expand_annotations(annotations, branch, current_rev=None):
 
176
    """Expand a file's annotations into command line UI ready tuples.
 
177
 
 
178
    Each tuple includes detailed information, such as the author name, and date
 
179
    string for the commit, rather than just the revision id.
 
180
 
 
181
    :param annotations: The annotations to expand.
 
182
    :param revision_id_to_revno: A map from id to revision numbers.
 
183
    :param branch: A locked branch to query for revision details.
 
184
    """
 
185
    repository = branch.repository
 
186
    if current_rev is not None:
 
187
        # This can probably become a function on MutableTree, get_revno_map there,
 
188
        # or something.
 
189
        last_revision = current_rev.revision_id
 
190
        # XXX: Partially Cloned from branch, uses the old_get_graph, eep.
 
191
        # XXX: The main difficulty is that we need to inject a single new node
 
192
        #      (current_rev) into the graph before it gets numbered, etc.
 
193
        #      Once KnownGraph gets an 'add_node()' function, we can use
 
194
        #      VF.get_known_graph_ancestry().
 
195
        graph = repository.get_graph()
 
196
        revision_graph = dict(((key, value) for key, value in
 
197
            graph.iter_ancestry(current_rev.parent_ids) if value is not None))
 
198
        revision_graph = _strip_NULL_ghosts(revision_graph)
 
199
        revision_graph[last_revision] = current_rev.parent_ids
 
200
        merge_sorted_revisions = tsort.merge_sort(
 
201
            revision_graph,
 
202
            last_revision,
 
203
            None,
 
204
            generate_revno=True)
 
205
        revision_id_to_revno = dict((rev_id, revno)
 
206
            for seq_num, rev_id, depth, revno, end_of_merge in
 
207
                merge_sorted_revisions)
 
208
    else:
 
209
        revision_id_to_revno = branch.get_revision_id_to_revno_map()
 
210
    last_origin = None
 
211
    revision_ids = set(o for o, t in annotations)
 
212
    revisions = {}
 
213
    if CURRENT_REVISION in revision_ids:
 
214
        revision_id_to_revno[CURRENT_REVISION] = (
 
215
            "%d?" % (branch.revno() + 1),)
 
216
        revisions[CURRENT_REVISION] = current_rev
 
217
    revision_ids = [o for o in revision_ids if
 
218
                    repository.has_revision(o)]
 
219
    revisions.update((r.revision_id, r) for r in
 
220
                     repository.get_revisions(revision_ids))
 
221
    for origin, text in annotations:
 
222
        text = text.rstrip('\r\n')
 
223
        if origin == last_origin:
 
224
            (revno_str, author, date_str) = ('','','')
 
225
        else:
 
226
            last_origin = origin
 
227
            if origin not in revisions:
 
228
                (revno_str, author, date_str) = ('?','?','?')
 
229
            else:
 
230
                revno_str = '.'.join(str(i) for i in
 
231
                                            revision_id_to_revno[origin])
 
232
            rev = revisions[origin]
 
233
            tz = rev.timezone or 0
 
234
            date_str = time.strftime('%Y%m%d',
 
235
                                     time.gmtime(rev.timestamp + tz))
 
236
            # a lazy way to get something like the email address
 
237
            # TODO: Get real email address
 
238
            author = rev.get_apparent_authors()[0]
 
239
            try:
 
240
                author = extract_email_address(author)
 
241
            except errors.NoEmailInUsername:
 
242
                pass        # use the whole name
 
243
        yield (revno_str, author, date_str, origin, text)
 
244
 
 
245
 
 
246
def reannotate(parents_lines, new_lines, new_revision_id,
 
247
               _left_matching_blocks=None,
 
248
               heads_provider=None):
 
249
    """Create a new annotated version from new lines and parent annotations.
 
250
 
 
251
    :param parents_lines: List of annotated lines for all parents
 
252
    :param new_lines: The un-annotated new lines
 
253
    :param new_revision_id: The revision-id to associate with new lines
 
254
        (will often be CURRENT_REVISION)
 
255
    :param left_matching_blocks: a hint about which areas are common
 
256
        between the text and its left-hand-parent.  The format is
 
257
        the SequenceMatcher.get_matching_blocks format
 
258
        (start_left, start_right, length_of_match).
 
259
    :param heads_provider: An object which provides a .heads() call to resolve
 
260
        if any revision ids are children of others.
 
261
        If None, then any ancestry disputes will be resolved with
 
262
        new_revision_id
 
263
    """
 
264
    if len(parents_lines) == 0:
 
265
        lines = [(new_revision_id, line) for line in new_lines]
 
266
    elif len(parents_lines) == 1:
 
267
        lines = _reannotate(parents_lines[0], new_lines, new_revision_id,
 
268
                            _left_matching_blocks)
 
269
    elif len(parents_lines) == 2:
 
270
        left = _reannotate(parents_lines[0], new_lines, new_revision_id,
 
271
                           _left_matching_blocks)
 
272
        lines = _reannotate_annotated(parents_lines[1], new_lines,
 
273
                                      new_revision_id, left,
 
274
                                      heads_provider)
 
275
    else:
 
276
        reannotations = [_reannotate(parents_lines[0], new_lines,
 
277
                                     new_revision_id, _left_matching_blocks)]
 
278
        reannotations.extend(_reannotate(p, new_lines, new_revision_id)
 
279
                             for p in parents_lines[1:])
 
280
        lines = []
 
281
        for annos in zip(*reannotations):
 
282
            origins = set(a for a, l in annos)
 
283
            if len(origins) == 1:
 
284
                # All the parents agree, so just return the first one
 
285
                lines.append(annos[0])
 
286
            else:
 
287
                line = annos[0][1]
 
288
                if len(origins) == 2 and new_revision_id in origins:
 
289
                    origins.remove(new_revision_id)
 
290
                if len(origins) == 1:
 
291
                    lines.append((origins.pop(), line))
 
292
                else:
 
293
                    lines.append((new_revision_id, line))
 
294
    return lines
 
295
 
 
296
 
 
297
def _reannotate(parent_lines, new_lines, new_revision_id,
 
298
                matching_blocks=None):
 
299
    new_cur = 0
 
300
    if matching_blocks is None:
 
301
        plain_parent_lines = [l for r, l in parent_lines]
 
302
        matcher = patiencediff.PatienceSequenceMatcher(None,
 
303
            plain_parent_lines, new_lines)
 
304
        matching_blocks = matcher.get_matching_blocks()
 
305
    lines = []
 
306
    for i, j, n in matching_blocks:
 
307
        for line in new_lines[new_cur:j]:
 
308
            lines.append((new_revision_id, line))
 
309
        lines.extend(parent_lines[i:i+n])
 
310
        new_cur = j + n
 
311
    return lines
 
312
 
 
313
 
 
314
def _get_matching_blocks(old, new):
 
315
    matcher = patiencediff.PatienceSequenceMatcher(None,
 
316
        old, new)
 
317
    return matcher.get_matching_blocks()
 
318
 
 
319
 
 
320
_break_annotation_tie = None
 
321
 
 
322
def _old_break_annotation_tie(annotated_lines):
 
323
    """Chose an attribution between several possible ones.
 
324
 
 
325
    :param annotated_lines: A list of tuples ((file_id, rev_id), line) where
 
326
        the lines are identical but the revids different while no parent
 
327
        relation exist between them
 
328
 
 
329
     :return : The "winning" line. This must be one with a revid that
 
330
         guarantees that further criss-cross merges will converge. Failing to
 
331
         do so have performance implications.
 
332
    """
 
333
    # sort lexicographically so that we always get a stable result.
 
334
 
 
335
    # TODO: while 'sort' is the easiest (and nearly the only possible solution)
 
336
    # with the current implementation, chosing the oldest revision is known to
 
337
    # provide better results (as in matching user expectations). The most
 
338
    # common use case being manual cherry-pick from an already existing
 
339
    # revision.
 
340
    return sorted(annotated_lines)[0]
 
341
 
 
342
 
 
343
def _find_matching_unannotated_lines(output_lines, plain_child_lines,
 
344
                                     child_lines, start_child, end_child,
 
345
                                     right_lines, start_right, end_right,
 
346
                                     heads_provider, revision_id):
 
347
    """Find lines in plain_right_lines that match the existing lines.
 
348
 
 
349
    :param output_lines: Append final annotated lines to this list
 
350
    :param plain_child_lines: The unannotated new lines for the child text
 
351
    :param child_lines: Lines for the child text which have been annotated
 
352
        for the left parent
 
353
 
 
354
    :param start_child: Position in plain_child_lines and child_lines to start
 
355
        the match searching
 
356
    :param end_child: Last position in plain_child_lines and child_lines to
 
357
        search for a match
 
358
    :param right_lines: The annotated lines for the whole text for the right
 
359
        parent
 
360
    :param start_right: Position in right_lines to start the match
 
361
    :param end_right: Last position in right_lines to search for a match
 
362
    :param heads_provider: When parents disagree on the lineage of a line, we
 
363
        need to check if one side supersedes the other
 
364
    :param revision_id: The label to give if a line should be labeled 'tip'
 
365
    """
 
366
    output_extend = output_lines.extend
 
367
    output_append = output_lines.append
 
368
    # We need to see if any of the unannotated lines match
 
369
    plain_right_subset = [l for a,l in right_lines[start_right:end_right]]
 
370
    plain_child_subset = plain_child_lines[start_child:end_child]
 
371
    match_blocks = _get_matching_blocks(plain_right_subset, plain_child_subset)
 
372
 
 
373
    last_child_idx = 0
 
374
 
 
375
    for right_idx, child_idx, match_len in match_blocks:
 
376
        # All the lines that don't match are just passed along
 
377
        if child_idx > last_child_idx:
 
378
            output_extend(child_lines[start_child + last_child_idx
 
379
                                      :start_child + child_idx])
 
380
        for offset in xrange(match_len):
 
381
            left = child_lines[start_child+child_idx+offset]
 
382
            right = right_lines[start_right+right_idx+offset]
 
383
            if left[0] == right[0]:
 
384
                # The annotations match, just return the left one
 
385
                output_append(left)
 
386
            elif left[0] == revision_id:
 
387
                # The left parent marked this as unmatched, so let the
 
388
                # right parent claim it
 
389
                output_append(right)
 
390
            else:
 
391
                # Left and Right both claim this line
 
392
                if heads_provider is None:
 
393
                    output_append((revision_id, left[1]))
 
394
                else:
 
395
                    heads = heads_provider.heads((left[0], right[0]))
 
396
                    if len(heads) == 1:
 
397
                        output_append((iter(heads).next(), left[1]))
 
398
                    else:
 
399
                        # Both claim different origins, get a stable result.
 
400
                        # If the result is not stable, there is a risk a
 
401
                        # performance degradation as criss-cross merges will
 
402
                        # flip-flop the attribution.
 
403
                        if _break_annotation_tie is None:
 
404
                            output_append(
 
405
                                _old_break_annotation_tie([left, right]))
 
406
                        else:
 
407
                            output_append(_break_annotation_tie([left, right]))
 
408
        last_child_idx = child_idx + match_len
 
409
 
 
410
 
 
411
def _reannotate_annotated(right_parent_lines, new_lines, new_revision_id,
 
412
                          annotated_lines, heads_provider):
 
413
    """Update the annotations for a node based on another parent.
 
414
 
 
415
    :param right_parent_lines: A list of annotated lines for the right-hand
 
416
        parent.
 
417
    :param new_lines: The unannotated new lines.
 
418
    :param new_revision_id: The revision_id to attribute to lines which are not
 
419
        present in either parent.
 
420
    :param annotated_lines: A list of annotated lines. This should be the
 
421
        annotation of new_lines based on parents seen so far.
 
422
    :param heads_provider: When parents disagree on the lineage of a line, we
 
423
        need to check if one side supersedes the other.
 
424
    """
 
425
    if len(new_lines) != len(annotated_lines):
 
426
        raise AssertionError("mismatched new_lines and annotated_lines")
 
427
    # First compare the newly annotated lines with the right annotated lines.
 
428
    # Lines which were not changed in left or right should match. This tends to
 
429
    # be the bulk of the lines, and they will need no further processing.
 
430
    lines = []
 
431
    lines_extend = lines.extend
 
432
    last_right_idx = 0 # The line just after the last match from the right side
 
433
    last_left_idx = 0
 
434
    matching_left_and_right = _get_matching_blocks(right_parent_lines,
 
435
                                                   annotated_lines)
 
436
    for right_idx, left_idx, match_len in matching_left_and_right:
 
437
        # annotated lines from last_left_idx to left_idx did not match the
 
438
        # lines from last_right_idx to right_idx, the raw lines should be
 
439
        # compared to determine what annotations need to be updated
 
440
        if last_right_idx == right_idx or last_left_idx == left_idx:
 
441
            # One of the sides is empty, so this is a pure insertion
 
442
            lines_extend(annotated_lines[last_left_idx:left_idx])
 
443
        else:
 
444
            # We need to see if any of the unannotated lines match
 
445
            _find_matching_unannotated_lines(lines,
 
446
                                             new_lines, annotated_lines,
 
447
                                             last_left_idx, left_idx,
 
448
                                             right_parent_lines,
 
449
                                             last_right_idx, right_idx,
 
450
                                             heads_provider,
 
451
                                             new_revision_id)
 
452
        last_right_idx = right_idx + match_len
 
453
        last_left_idx = left_idx + match_len
 
454
        # If left and right agree on a range, just push that into the output
 
455
        lines_extend(annotated_lines[left_idx:left_idx + match_len])
 
456
    return lines
 
457
 
 
458
 
 
459
try:
 
460
    from bzrlib._annotator_pyx import Annotator
 
461
except ImportError, e:
 
462
    osutils.failed_to_load_extension(e)
 
463
    from bzrlib._annotator_py import Annotator