Rev 3181: Change reannotate to special case the 2-parent case. in http://bzr.arbash-meinel.com/branches/bzr/1.2-dev/optim_annotate

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/1.2-dev/optim_annotate

------------------------------------------------------------
revno: 3181
revision-id:john at arbash-meinel.com-20080124225422-atibw1m93vdmtjw9
parent: pqm at pqm.ubuntu.com-20080115003405-jfuumkpctmvl2e4r
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: optim_annotate
timestamp: Thu 2008-01-24 16:54:22 -0600
message:
  Change reannotate to special case the 2-parent case.
  This allows a few cheap optimizations which saves a lot of time for annotate.
modified:
  bzrlib/annotate.py             annotate.py-20050922133147-7c60541d2614f022
-------------- next part --------------
=== modified file 'bzrlib/annotate.py'
--- a/bzrlib/annotate.py	2007-11-21 21:57:11 +0000
+++ b/bzrlib/annotate.py	2008-01-24 22:54:22 +0000
@@ -168,25 +168,48 @@
         the SequenceMatcher.get_matching_blocks format.
     """
     if len(parents_lines) == 0:
-        for line in new_lines:
-            yield new_revision_id, line
+        lines = [(new_revision_id, line) for line in new_lines]
     elif len(parents_lines) == 1:
-        for data in _reannotate(parents_lines[0], new_lines, new_revision_id,
-                                _left_matching_blocks):
-            yield data
+        lines = _reannotate(parents_lines[0], new_lines, new_revision_id,
+                            _left_matching_blocks)
+    elif len(parents_lines) == 2:
+        left = _reannotate(parents_lines[0], new_lines, new_revision_id,
+                           _left_matching_blocks)
+        right = _reannotate(parents_lines[1], new_lines, new_revision_id)
+        lines = []
+        for idx in xrange(len(new_lines)):
+            if left[idx][0] == right[idx][0]:
+                # The annotations match, just return the left one
+                lines.append(left[idx])
+            elif left[idx][0] == new_revision_id:
+                # The left parent claims a new value, return the right one
+                lines.append(right[idx])
+            elif right[idx][0] == new_revision_id:
+                # The right parent claims a new value, return the left one
+                lines.append(left[idx])
+            else:
+                # Both claim different origins
+                lines.append((new_revision_id, left[idx][1]))
     else:
-        block_list = [_left_matching_blocks] + [None] * len(parents_lines)
-        reannotations = [list(_reannotate(p, new_lines, new_revision_id, b))
-                         for p, b in zip(parents_lines, block_list)]
+        reannotations = [_reannotate(parents_lines[0], new_lines,
+                                     new_revision_id, _left_matching_blocks)]
+        reannotations.extend(_reannotate(p, new_lines, new_revision_id)
+                             for p in parents_lines[1:])
+        lines = []
         for annos in zip(*reannotations):
             origins = set(a for a, l in annos)
-            line = annos[0][1]
             if len(origins) == 1:
-                yield iter(origins).next(), line
-            elif len(origins) == 2 and new_revision_id in origins:
-                yield (x for x in origins if x != new_revision_id).next(), line
+                # All the parents agree, so just return the first one
+                lines.append(annos[0])
             else:
-                yield new_revision_id, line
+                line = annos[0][1]
+                if len(origins) == 2 and new_revision_id in origins:
+                    origins.remove(new_revision_id)
+                if len(origins) == 1:
+                    lines.append(origins.pop(), line))
+                else:
+                    lines.append((new_revision_id, line))
+    return lines
 
 
 def _reannotate(parent_lines, new_lines, new_revision_id,
@@ -197,9 +220,10 @@
         matcher = patiencediff.PatienceSequenceMatcher(None,
             plain_parent_lines, new_lines)
         matching_blocks = matcher.get_matching_blocks()
+    lines = []
     for i, j, n in matching_blocks:
         for line in new_lines[new_cur:j]:
-            yield new_revision_id, line
-        for data in parent_lines[i:i+n]:
-            yield data
+            lines.append((new_revision_id, line))
+        lines.extend(parent_lines[i:i+n])
         new_cur = j + n
+    return lines