← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/annotate.py

  • Committer: John Arbash Meinel
  • Date: 2008-03-15 13:51:09 UTC
  • mfrom: (3280 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3281.
  • Revision ID: john@arbash-meinel.com-20080315135109-7v9gimdidd1s7llr
[merge] bzr.dev 3280

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/annotate.py
156
156
 
157
157
 
158
158
def reannotate(parents_lines, new_lines, new_revision_id,
159
 
               _left_matching_blocks=None):
 
159
               _left_matching_blocks=None,
 
160
               heads_provider=None):
160
161
    """Create a new annotated version from new lines and parent annotations.
161
162
    
162
163
    :param parents_lines: List of annotated lines for all parents
165
166
        (will often be CURRENT_REVISION)
166
167
    :param left_matching_blocks: a hint about which areas are common
167
168
        between the text and its left-hand-parent.  The format is
168
 
        the SequenceMatcher.get_matching_blocks format.
 
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
169
175
    """
170
176
    if len(parents_lines) == 0:
171
177
        lines = [(new_revision_id, line) for line in new_lines]
175
181
    elif len(parents_lines) == 2:
176
182
        left = _reannotate(parents_lines[0], new_lines, new_revision_id,
177
183
                           _left_matching_blocks)
178
 
        right = _reannotate(parents_lines[1], new_lines, new_revision_id)
179
 
        lines = []
180
 
        for idx in xrange(len(new_lines)):
181
 
            if left[idx][0] == right[idx][0]:
182
 
                # The annotations match, just return the left one
183
 
                lines.append(left[idx])
184
 
            elif left[idx][0] == new_revision_id:
185
 
                # The left parent claims a new value, return the right one
186
 
                lines.append(right[idx])
187
 
            elif right[idx][0] == new_revision_id:
188
 
                # The right parent claims a new value, return the left one
189
 
                lines.append(left[idx])
190
 
            else:
191
 
                # Both claim different origins
192
 
                lines.append((new_revision_id, left[idx][1]))
 
184
        lines = _reannotate_annotated(parents_lines[1], new_lines,
 
185
                                      new_revision_id, left,
 
186
                                      heads_provider)
193
187
    else:
194
188
        reannotations = [_reannotate(parents_lines[0], new_lines,
195
189
                                     new_revision_id, _left_matching_blocks)]
227
221
        lines.extend(parent_lines[i:i+n])
228
222
        new_cur = j + n
229
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