← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/annotate.py

  • Committer: Andrew Bennetts
  • Date: 2007-03-26 06:24:01 UTC
  • mto: This revision was merged to the branch mainline in revision 2376.
  • Revision ID: andrew.bennetts@canonical.com-20070326062401-k3nbefzje5332jaf
Deal with review comments from Robert:

  * Add my name to the NEWS file
  * Move the test case to a new module in branch_implementations
  * Remove revision_history cruft from identitymap and test_identitymap
  * Improve some docstrings

Also, this fixes a bug where revision_history was not returning a copy of the
cached data, allowing the cache to be corrupted.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/annotate.py
30
30
 
31
31
from bzrlib import (
32
32
    errors,
33
 
    osutils,
34
33
    patiencediff,
35
34
    tsort,
36
35
    )
39
38
 
40
39
def annotate_file(branch, rev_id, file_id, verbose=False, full=False,
41
40
                  to_file=None, show_ids=False):
42
 
    """Annotate file_id at revision rev_id in branch.
43
 
 
44
 
    The branch should already be read_locked() when annotate_file is called.
45
 
 
46
 
    :param branch: The branch to look for revision numbers and history from.
47
 
    :param rev_id: The revision id to annotate.
48
 
    :param file_id: The file_id to annotate.
49
 
    :param verbose: Show all details rather than truncating to ensure
50
 
        reasonable text width.
51
 
    :param full: XXXX Not sure what this does.
52
 
    :param to_file: The file to output the annotation to; if None stdout is
53
 
        used.
54
 
    :param show_ids: Show revision ids in the annotation output.
55
 
    """
56
41
    if to_file is None:
57
42
        to_file = sys.stdout
58
43
 
59
 
    # Handle the show_ids case
 
44
    prevanno=''
60
45
    last_rev_id = None
61
46
    if show_ids:
62
 
        annotations = _annotations(branch.repository, file_id, rev_id)
 
47
        w = branch.repository.weave_store.get_weave(file_id,
 
48
            branch.repository.get_transaction())
 
49
        annotations = list(w.annotate_iter(rev_id))
63
50
        max_origin_len = max(len(origin) for origin, text in annotations)
64
51
        for origin, text in annotations:
65
52
            if full or last_rev_id != origin:
70
57
            last_rev_id = origin
71
58
        return
72
59
 
73
 
    # Calculate the lengths of the various columns
74
60
    annotation = list(_annotate_file(branch, rev_id, file_id))
75
61
    if len(annotation) == 0:
76
62
        max_origin_len = max_revno_len = max_revid_len = 0
78
64
        max_origin_len = max(len(x[1]) for x in annotation)
79
65
        max_revno_len = max(len(x[0]) for x in annotation)
80
66
        max_revid_len = max(len(x[3]) for x in annotation)
 
67
 
81
68
    if not verbose:
82
69
        max_revno_len = min(max_revno_len, 12)
83
70
    max_revno_len = max(max_revno_len, 3)
84
71
 
85
 
    # Output the annotations
86
 
    prevanno = ''
87
 
    encoding = getattr(to_file, 'encoding', None) or \
88
 
            osutils.get_terminal_encoding()
89
72
    for (revno_str, author, date_str, line_rev_id, text) in annotation:
90
73
        if verbose:
91
74
            anno = '%-*s %-*s %8s ' % (max_revno_len, revno_str,
94
77
            if len(revno_str) > max_revno_len:
95
78
                revno_str = revno_str[:max_revno_len-1] + '>'
96
79
            anno = "%-*s %-7s " % (max_revno_len, revno_str, author[:7])
97
 
        if anno.lstrip() == "" and full:
98
 
            anno = prevanno
99
 
        try:
100
 
            to_file.write(anno)
101
 
        except UnicodeEncodeError:
102
 
            # cmd_annotate should be passing in an 'exact' object, which means
103
 
            # we have a direct handle to sys.stdout or equivalent. It may not
104
 
            # be able to handle the exact Unicode characters, but 'annotate' is
105
 
            # a user function (non-scripting), so shouldn't die because of
106
 
            # unrepresentable annotation characters. So encode using 'replace',
107
 
            # and write them again.
108
 
            to_file.write(anno.encode(encoding, 'replace'))
109
 
        to_file.write('| %s\n' % (text,))
110
 
        prevanno = anno
111
 
 
112
 
 
113
 
def _annotations(repo, file_id, rev_id):
114
 
    """Return the list of (origin_revision_id, line_text) for a revision of a file in a repository."""
115
 
    annotations = repo.texts.annotate((file_id, rev_id))
116
 
    # 
117
 
    return [(key[-1], line) for (key, line) in annotations]
 
80
 
 
81
        if anno.lstrip() == "" and full: anno = prevanno
 
82
        print >>to_file, '%s| %s' % (anno, text)
 
83
        prevanno=anno
118
84
 
119
85
 
120
86
def _annotate_file(branch, rev_id, file_id):
121
87
    """Yield the origins for each line of a file.
122
88
 
123
 
    This includes detailed information, such as the author name, and
 
89
    This includes detailed information, such as the committer name, and
124
90
    date string for the commit, rather than just the revision id.
125
91
    """
126
 
    revision_id_to_revno = branch.get_revision_id_to_revno_map()
127
 
    annotations = _annotations(branch.repository, file_id, rev_id)
 
92
    branch_last_revision = branch.last_revision()
 
93
    revision_graph = branch.repository.get_revision_graph(branch_last_revision)
 
94
    merge_sorted_revisions = tsort.merge_sort(
 
95
        revision_graph,
 
96
        branch_last_revision,
 
97
        None,
 
98
        generate_revno=True)
 
99
    revision_id_to_revno = dict((rev_id, revno)
 
100
                                for seq_num, rev_id, depth, revno, end_of_merge
 
101
                                 in merge_sorted_revisions)
 
102
    w = branch.repository.weave_store.get_weave(file_id,
 
103
        branch.repository.get_transaction())
128
104
    last_origin = None
 
105
    annotations = list(w.annotate_iter(rev_id))
129
106
    revision_ids = set(o for o, t in annotations)
130
107
    revision_ids = [o for o in revision_ids if 
131
108
                    branch.repository.has_revision(o)]
148
125
                                     time.gmtime(rev.timestamp + tz))
149
126
            # a lazy way to get something like the email address
150
127
            # TODO: Get real email address
151
 
            author = rev.get_apparent_author()
 
128
            author = rev.committer
152
129
            try:
153
130
                author = extract_email_address(author)
154
131
            except errors.NoEmailInUsername:
156
133
        yield (revno_str, author, date_str, origin, text)
157
134
 
158
135
 
159
 
def reannotate(parents_lines, new_lines, new_revision_id,
160
 
               _left_matching_blocks=None,
161
 
               heads_provider=None):
 
136
def reannotate(parents_lines, new_lines, new_revision_id):
162
137
    """Create a new annotated version from new lines and parent annotations.
163
138
    
164
139
    :param parents_lines: List of annotated lines for all parents
165
140
    :param new_lines: The un-annotated new lines
166
141
    :param new_revision_id: The revision-id to associate with new lines
167
142
        (will often be CURRENT_REVISION)
168
 
    :param left_matching_blocks: a hint about which areas are common
169
 
        between the text and its left-hand-parent.  The format is
170
 
        the SequenceMatcher.get_matching_blocks format
171
 
        (start_left, start_right, length_of_match).
172
 
    :param heads_provider: An object which provids a .heads() call to resolve
173
 
        if any revision ids are children of others.
174
 
        If None, then any ancestry disputes will be resolved with
175
 
        new_revision_id
176
143
    """
177
 
    if len(parents_lines) == 0:
178
 
        lines = [(new_revision_id, line) for line in new_lines]
179
 
    elif len(parents_lines) == 1:
180
 
        lines = _reannotate(parents_lines[0], new_lines, new_revision_id,
181
 
                            _left_matching_blocks)
182
 
    elif len(parents_lines) == 2:
183
 
        left = _reannotate(parents_lines[0], new_lines, new_revision_id,
184
 
                           _left_matching_blocks)
185
 
        lines = _reannotate_annotated(parents_lines[1], new_lines,
186
 
                                      new_revision_id, left,
187
 
                                      heads_provider)
 
144
    if len(parents_lines) == 1:
 
145
        for data in _reannotate(parents_lines[0], new_lines, new_revision_id):
 
146
            yield data
188
147
    else:
189
 
        reannotations = [_reannotate(parents_lines[0], new_lines,
190
 
                                     new_revision_id, _left_matching_blocks)]
191
 
        reannotations.extend(_reannotate(p, new_lines, new_revision_id)
192
 
                             for p in parents_lines[1:])
193
 
        lines = []
 
148
        reannotations = [list(_reannotate(p, new_lines, new_revision_id)) for
 
149
                         p in parents_lines]
194
150
        for annos in zip(*reannotations):
195
151
            origins = set(a for a, l in annos)
 
152
            line = annos[0][1]
196
153
            if len(origins) == 1:
197
 
                # All the parents agree, so just return the first one
198
 
                lines.append(annos[0])
 
154
                yield iter(origins).next(), line
 
155
            elif len(origins) == 2 and new_revision_id in origins:
 
156
                yield (x for x in origins if x != new_revision_id).next(), line
199
157
            else:
200
 
                line = annos[0][1]
201
 
                if len(origins) == 2 and new_revision_id in origins:
202
 
                    origins.remove(new_revision_id)
203
 
                if len(origins) == 1:
204
 
                    lines.append((origins.pop(), line))
205
 
                else:
206
 
                    lines.append((new_revision_id, line))
207
 
    return lines
208
 
 
209
 
 
210
 
def _reannotate(parent_lines, new_lines, new_revision_id,
211
 
                matching_blocks=None):
 
158
                yield new_revision_id, line
 
159
 
 
160
 
 
161
def _reannotate(parent_lines, new_lines, new_revision_id):
 
162
    plain_parent_lines = [l for r, l in parent_lines]
 
163
    matcher = patiencediff.PatienceSequenceMatcher(None, plain_parent_lines,
 
164
                                                   new_lines)
212
165
    new_cur = 0
213
 
    if matching_blocks is None:
214
 
        plain_parent_lines = [l for r, l in parent_lines]
215
 
        matcher = patiencediff.PatienceSequenceMatcher(None,
216
 
            plain_parent_lines, new_lines)
217
 
        matching_blocks = matcher.get_matching_blocks()
218
 
    lines = []
219
 
    for i, j, n in matching_blocks:
 
166
    for i, j, n in matcher.get_matching_blocks():
220
167
        for line in new_lines[new_cur:j]:
221
 
            lines.append((new_revision_id, line))
222
 
        lines.extend(parent_lines[i:i+n])
 
168
            yield new_revision_id, line
 
169
        for data in parent_lines[i:i+n]:
 
170
            yield data
223
171
        new_cur = j + n
224
 
    return lines
225
 
 
226
 
 
227
 
def _get_matching_blocks(old, new):
228
 
    matcher = patiencediff.PatienceSequenceMatcher(None,
229
 
        old, new)
230
 
    return matcher.get_matching_blocks()
231
 
 
232
 
 
233
 
def _find_matching_unannotated_lines(output_lines, plain_child_lines,
234
 
                                     child_lines, start_child, end_child,
235
 
                                     right_lines, start_right, end_right,
236
 
                                     heads_provider, revision_id):
237
 
    """Find lines in plain_right_lines that match the existing lines.
238
 
 
239
 
    :param output_lines: Append final annotated lines to this list
240
 
    :param plain_child_lines: The unannotated new lines for the child text
241
 
    :param child_lines: Lines for the child text which have been annotated
242
 
        for the left parent
243
 
    :param start_child: Position in plain_child_lines and child_lines to start the
244
 
        match searching
245
 
    :param end_child: Last position in plain_child_lines and child_lines to search
246
 
        for a match
247
 
    :param right_lines: The annotated lines for the whole text for the right
248
 
        parent
249
 
    :param start_right: Position in right_lines to start the match
250
 
    :param end_right: Last position in right_lines to search for a match
251
 
    :param heads_provider: When parents disagree on the lineage of a line, we
252
 
        need to check if one side supersedes the other
253
 
    :param revision_id: The label to give if a line should be labeled 'tip'
254
 
    """
255
 
    output_extend = output_lines.extend
256
 
    output_append = output_lines.append
257
 
    # We need to see if any of the unannotated lines match
258
 
    plain_right_subset = [l for a,l in right_lines[start_right:end_right]]
259
 
    plain_child_subset = plain_child_lines[start_child:end_child]
260
 
    match_blocks = _get_matching_blocks(plain_right_subset, plain_child_subset)
261
 
 
262
 
    last_child_idx = 0
263
 
 
264
 
    for right_idx, child_idx, match_len in match_blocks:
265
 
        # All the lines that don't match are just passed along
266
 
        if child_idx > last_child_idx:
267
 
            output_extend(child_lines[start_child + last_child_idx
268
 
                                      :start_child + child_idx])
269
 
        for offset in xrange(match_len):
270
 
            left = child_lines[start_child+child_idx+offset]
271
 
            right = right_lines[start_right+right_idx+offset]
272
 
            if left[0] == right[0]:
273
 
                # The annotations match, just return the left one
274
 
                output_append(left)
275
 
            elif left[0] == revision_id:
276
 
                # The left parent marked this as unmatched, so let the
277
 
                # right parent claim it
278
 
                output_append(right)
279
 
            else:
280
 
                # Left and Right both claim this line
281
 
                if heads_provider is None:
282
 
                    output_append((revision_id, left[1]))
283
 
                else:
284
 
                    heads = heads_provider.heads((left[0], right[0]))
285
 
                    if len(heads) == 1:
286
 
                        output_append((iter(heads).next(), left[1]))
287
 
                    else:
288
 
                        # Both claim different origins
289
 
                        output_append((revision_id, left[1]))
290
 
                        # We know that revision_id is the head for
291
 
                        # left and right, so cache it
292
 
                        heads_provider.cache(
293
 
                            (revision_id, left[0]),
294
 
                            (revision_id,))
295
 
                        heads_provider.cache(
296
 
                            (revision_id, right[0]),
297
 
                            (revision_id,))
298
 
        last_child_idx = child_idx + match_len
299
 
 
300
 
 
301
 
def _reannotate_annotated(right_parent_lines, new_lines, new_revision_id,
302
 
                          annotated_lines, heads_provider):
303
 
    """Update the annotations for a node based on another parent.
304
 
 
305
 
    :param right_parent_lines: A list of annotated lines for the right-hand
306
 
        parent.
307
 
    :param new_lines: The unannotated new lines.
308
 
    :param new_revision_id: The revision_id to attribute to lines which are not
309
 
        present in either parent.
310
 
    :param annotated_lines: A list of annotated lines. This should be the
311
 
        annotation of new_lines based on parents seen so far.
312
 
    :param heads_provider: When parents disagree on the lineage of a line, we
313
 
        need to check if one side supersedes the other.
314
 
    """
315
 
    if len(new_lines) != len(annotated_lines):
316
 
        raise AssertionError("mismatched new_lines and annotated_lines")
317
 
    # First compare the newly annotated lines with the right annotated lines.
318
 
    # Lines which were not changed in left or right should match. This tends to
319
 
    # be the bulk of the lines, and they will need no further processing.
320
 
    lines = []
321
 
    lines_extend = lines.extend
322
 
    last_right_idx = 0 # The line just after the last match from the right side
323
 
    last_left_idx = 0
324
 
    matching_left_and_right = _get_matching_blocks(right_parent_lines,
325
 
                                                   annotated_lines)
326
 
    for right_idx, left_idx, match_len in matching_left_and_right:
327
 
        # annotated lines from last_left_idx to left_idx did not match the lines from
328
 
        # last_right_idx
329
 
        # to right_idx, the raw lines should be compared to determine what annotations
330
 
        # need to be updated
331
 
        if last_right_idx == right_idx or last_left_idx == left_idx:
332
 
            # One of the sides is empty, so this is a pure insertion
333
 
            lines_extend(annotated_lines[last_left_idx:left_idx])
334
 
        else:
335
 
            # We need to see if any of the unannotated lines match
336
 
            _find_matching_unannotated_lines(lines,
337
 
                                             new_lines, annotated_lines,
338
 
                                             last_left_idx, left_idx,
339
 
                                             right_parent_lines,
340
 
                                             last_right_idx, right_idx,
341
 
                                             heads_provider,
342
 
                                             new_revision_id)
343
 
        last_right_idx = right_idx + match_len
344
 
        last_left_idx = left_idx + match_len
345
 
        # If left and right agree on a range, just push that into the output
346
 
        lines_extend(annotated_lines[left_idx:left_idx + match_len])
347
 
    return lines