← 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: 2007-11-04 18:51:39 UTC
  • mfrom: (2961.1.1 trunk)
  • Revision ID: pqm@pqm.ubuntu.com-20071104185139-kaio3sneodg2kp71
Authentication ring implementation (read-only)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/annotate.py
39
39
 
40
40
def annotate_file(branch, rev_id, file_id, verbose=False, full=False,
41
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
 
    """
56
42
    if to_file is None:
57
43
        to_file = sys.stdout
58
44
 
111
97
 
112
98
 
113
99
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]
 
100
    """Return the list of (origin,text) for a revision of a file in a repository."""
 
101
    w = repo.weave_store.get_weave(file_id, repo.get_transaction())
 
102
    return list(w.annotate_iter(rev_id))
118
103
 
119
104
 
120
105
def _annotate_file(branch, rev_id, file_id):
157
142
 
158
143
 
159
144
def reannotate(parents_lines, new_lines, new_revision_id,
160
 
               _left_matching_blocks=None,
161
 
               heads_provider=None):
 
145
               _left_matching_blocks=None):
162
146
    """Create a new annotated version from new lines and parent annotations.
163
147
    
164
148
    :param parents_lines: List of annotated lines for all parents
167
151
        (will often be CURRENT_REVISION)
168
152
    :param left_matching_blocks: a hint about which areas are common
169
153
        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
 
154
        the SequenceMatcher.get_matching_blocks format.
176
155
    """
177
156
    if len(parents_lines) == 0:
178
 
        lines = [(new_revision_id, line) for line in new_lines]
 
157
        for line in new_lines:
 
158
            yield new_revision_id, line
179
159
    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)
 
160
        for data in _reannotate(parents_lines[0], new_lines, new_revision_id,
 
161
                                _left_matching_blocks):
 
162
            yield data
188
163
    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 = []
 
164
        block_list = [_left_matching_blocks] + [None] * len(parents_lines)
 
165
        reannotations = [list(_reannotate(p, new_lines, new_revision_id, b))
 
166
                         for p, b in zip(parents_lines, block_list)]
194
167
        for annos in zip(*reannotations):
195
168
            origins = set(a for a, l in annos)
 
169
            line = annos[0][1]
196
170
            if len(origins) == 1:
197
 
                # All the parents agree, so just return the first one
198
 
                lines.append(annos[0])
 
171
                yield iter(origins).next(), line
 
172
            elif len(origins) == 2 and new_revision_id in origins:
 
173
                yield (x for x in origins if x != new_revision_id).next(), line
199
174
            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
 
175
                yield new_revision_id, line
208
176
 
209
177
 
210
178
def _reannotate(parent_lines, new_lines, new_revision_id,
215
183
        matcher = patiencediff.PatienceSequenceMatcher(None,
216
184
            plain_parent_lines, new_lines)
217
185
        matching_blocks = matcher.get_matching_blocks()
218
 
    lines = []
219
186
    for i, j, n in matching_blocks:
220
187
        for line in new_lines[new_cur:j]:
221
 
            lines.append((new_revision_id, line))
222
 
        lines.extend(parent_lines[i:i+n])
 
188
            yield new_revision_id, line
 
189
        for data in parent_lines[i:i+n]:
 
190
            yield data
223
191
        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, sort lexicographically
289
 
                        # so that we always get a stable result.
290
 
                        output_append(sorted([left, right])[0])
291
 
        last_child_idx = child_idx + match_len
292
 
 
293
 
 
294
 
def _reannotate_annotated(right_parent_lines, new_lines, new_revision_id,
295
 
                          annotated_lines, heads_provider):
296
 
    """Update the annotations for a node based on another parent.
297
 
 
298
 
    :param right_parent_lines: A list of annotated lines for the right-hand
299
 
        parent.
300
 
    :param new_lines: The unannotated new lines.
301
 
    :param new_revision_id: The revision_id to attribute to lines which are not
302
 
        present in either parent.
303
 
    :param annotated_lines: A list of annotated lines. This should be the
304
 
        annotation of new_lines based on parents seen so far.
305
 
    :param heads_provider: When parents disagree on the lineage of a line, we
306
 
        need to check if one side supersedes the other.
307
 
    """
308
 
    if len(new_lines) != len(annotated_lines):
309
 
        raise AssertionError("mismatched new_lines and annotated_lines")
310
 
    # First compare the newly annotated lines with the right annotated lines.
311
 
    # Lines which were not changed in left or right should match. This tends to
312
 
    # be the bulk of the lines, and they will need no further processing.
313
 
    lines = []
314
 
    lines_extend = lines.extend
315
 
    last_right_idx = 0 # The line just after the last match from the right side
316
 
    last_left_idx = 0
317
 
    matching_left_and_right = _get_matching_blocks(right_parent_lines,
318
 
                                                   annotated_lines)
319
 
    for right_idx, left_idx, match_len in matching_left_and_right:
320
 
        # annotated lines from last_left_idx to left_idx did not match the lines from
321
 
        # last_right_idx
322
 
        # to right_idx, the raw lines should be compared to determine what annotations
323
 
        # need to be updated
324
 
        if last_right_idx == right_idx or last_left_idx == left_idx:
325
 
            # One of the sides is empty, so this is a pure insertion
326
 
            lines_extend(annotated_lines[last_left_idx:left_idx])
327
 
        else:
328
 
            # We need to see if any of the unannotated lines match
329
 
            _find_matching_unannotated_lines(lines,
330
 
                                             new_lines, annotated_lines,
331
 
                                             last_left_idx, left_idx,
332
 
                                             right_parent_lines,
333
 
                                             last_right_idx, right_idx,
334
 
                                             heads_provider,
335
 
                                             new_revision_id)
336
 
        last_right_idx = right_idx + match_len
337
 
        last_left_idx = left_idx + match_len
338
 
        # If left and right agree on a range, just push that into the output
339
 
        lines_extend(annotated_lines[left_idx:left_idx + match_len])
340
 
    return lines