← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/annotate.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2008-04-07 07:52:50 UTC
  • mfrom: (3340.1.1 208418-1.4)
  • Revision ID: pqm@pqm.ubuntu.com-20080407075250-phs53xnslo8boaeo
Return the correct knit serialisation method in _StreamAccess.
        (Andrew Bennetts, Martin Pool, Robert Collins)

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