Merge lp:~thumper/launchpad/scanner-awesomeness into lp:launchpad

[Tim Penhey]

Record the merged_revno in the scanner.

This branch records the merged revno for branches that have been merged. It only looks for the landing candidates as it uses the merge sorted graph, and we don't want to do that for the possible landing targets.

Since there may be many landing candidates for a series branch, and the merge sorted graph is a non-trivial thing to generate, I added a caching iterator. This allows the code to be written in a more natural way, but without multiple generations of the merge sorted graph.

tests:
  TestFindMergedRevno
  TestCachingIterator
  TestAutoMergeDetectionForMergeProposals

[Michael Hudson-Doyle (mwhudson)]

I pointed out a couple of typos on IRC.

I think a test of CachedIterator that iterated two iterators in parallel like so:

ci = CachedIterator([...])
i1 = iter(ci)
assert i1.next() == ...
i2 = iter(ci)
assert i2.next() == ...
assert i1.next() == ...

I think it'll pass fine, but it's something my devious mind wants to see tested.

CachingIterator needs some blank lines between its members.

Otherwise it all looks nice, and will be a nice change!

review: Approve

[Andrew Bennetts (spiv)]

Michael Hudson wrote:
> Review: Approve
> I pointed out a couple of typos on IRC.
>
> I think a test of CachedIterator that iterated two iterators in parallel like so:
>
> ci = CachedIterator([...])
> i1 = iter(ci)
> assert i1.next() == ...
> i2 = iter(ci)
> assert i2.next() == ...
> assert i1.next() == ...
>
> I think it'll pass fine, but it's something my devious mind wants to see tested.

You need to be more devious than that: the assumption CachedIterator is making
is that its __iter__ will never call itself. You'd think that's a reasonable
assumption, but I've seen code that accidentally does it. The more interacting
layers of code you have, with lazy DB iterators and so forth, the more likely it
is...

And boy is it confusing as hell when it does happen and you get “impossible”
results from apparently simple code.

So, try this:

class EvilIterator(object):
    def __init__(self):
        self.elem_source = iter('abcdef')
    def next(self):
        e = self.elem_source.next()
        if e == 'c':
            print 'evil:', list(ci)
        return e

ci = CachingIterator(EvilIterator())
i1 = iter(ci)
i2 = iter(ci)
for elem in i1:
    print '1:', elem
for elem in i2:
    print '2:', elem

-Andrew.

=== modified file 'lib/lp/codehosting/scanner/mergedetection.py'
--- lib/lp/codehosting/scanner/mergedetection.py	2010-03-02 19:30:18 +0000
+++ lib/lp/codehosting/scanner/mergedetection.py	2010-04-12 10:04:37 +0000
@@ -17,6 +17,7 @@
 from lp.code.interfaces.branchcollection import IAllBranches
 from lp.code.interfaces.branchmergeproposal import (
     BRANCH_MERGE_PROPOSAL_FINAL_STATES, notify_modified)
+from lp.services.utils import CachingIterator
 
 
 def is_series_branch(branch):
@@ -47,7 +48,7 @@
     branch.lifecycle_status = BranchLifecycleStatus.MERGED
 
 
-def merge_detected(logger, source, target, proposal=None):
+def merge_detected(logger, source, target, proposal=None, merge_revno=None):
     """Handle the merge of source into target."""
     # If the target branch is not the development focus, then don't update
     # the status of the source branch.
@@ -60,7 +61,7 @@
         if is_development_focus(target):
             mark_branch_merged(logger, source)
     else:
-        notify_modified(proposal, proposal.markAsMerged)
+        notify_modified(proposal, proposal.markAsMerged, merge_revno)
         # If there is an explicit merge proposal, change the branch's
         # status when it's been merged into a development focus or any
         # other series branch.
@@ -114,6 +115,27 @@
             merge_detected(logger, branch, db_branch)
 
 
+def find_merged_revno(merge_sorted, tip_rev_id):
+    """Find the mainline revno that merged tip_rev_id.
+
+    This method traverses the merge sorted graph looking for the first
+    """
+    last_mainline = None
+    iterator = iter(merge_sorted)
+    while True:
+        try:
+            rev_id, depth, revno, ignored = iterator.next()
+        except StopIteration:
+            break
+        if depth == 0:
+            last_mainline = revno[0]
+        if rev_id == tip_rev_id:
+            return last_mainline
+    # The only reason we get here is that the tip_rev_id isn't in the merge
+    # sorted graph.
+    return None
+
+
 def auto_merge_proposals(scan_completed):
     """Detect merged proposals."""
     db_branch = scan_completed.db_branch
@@ -127,12 +149,24 @@
     # At this stage we are not going to worry about the revno
     # which introduced the change, that will either be set through the web
     # ui by a person, or by PQM once it is integrated.
+
+    if scan_completed.bzr_branch is None:
+        # Only happens in tests.
+        merge_sorted = []
+    else:
+        merge_sorted = CachingIterator(
+            scan_completed.bzr_branch.iter_merge_sorted_revisions())
     for proposal in db_branch.landing_candidates:
-        if proposal.source_branch.last_scanned_id in bzr_ancestry:
+        tip_rev_id = proposal.source_branch.last_scanned_id
+        if tip_rev_id in bzr_ancestry:
+            merged_revno = find_merged_revno(merge_sorted, tip_rev_id)
+            # Remember so we can find the merged revision number.
             merge_detected(
-                logger, proposal.source_branch, db_branch, proposal)
+                logger, proposal.source_branch, db_branch, proposal,
+                merged_revno)
 
-    # Now check the landing targets.
+    # Now check the landing targets.  We should probably get rid of this,
+    # especially if we are trying to get rid of the branch revision table.
     final_states = BRANCH_MERGE_PROPOSAL_FINAL_STATES
     tip_rev_id = db_branch.last_scanned_id
     for proposal in db_branch.landing_targets:

=== modified file 'lib/lp/codehosting/scanner/tests/test_mergedetection.py'
--- lib/lp/codehosting/scanner/tests/test_mergedetection.py	2010-03-02 18:56:25 +0000
+++ lib/lp/codehosting/scanner/tests/test_mergedetection.py	2010-04-12 10:04:37 +0000
@@ -21,7 +21,7 @@
 from canonical.config import config
 from lp.code.enums import BranchLifecycleStatus, BranchMergeProposalStatus
 from lp.code.interfaces.branchlookup import IBranchLookup
-from lp.testing import TestCaseWithFactory
+from lp.testing import TestCase, TestCaseWithFactory
 from lp.testing.mail_helpers import pop_notifications
 from canonical.testing import LaunchpadZopelessLayer
 
@@ -35,7 +35,7 @@
     @run_as_db_user(config.launchpad.dbuser)
     def createProposal(self, source, target):
         # The scanner doesn't have insert rights, so do it here.
-        proposal = source.addLandingTarget(source.owner, target)
+        source.addLandingTarget(source.owner, target)
         transaction.commit()
 
     def _createBranchesAndProposal(self):
@@ -69,6 +69,7 @@
         self.assertEqual(
             BranchMergeProposalStatus.MERGED,
             proposal.queue_status)
+        self.assertEqual(3, proposal.merged_revno)
 
     def test_auto_merge_proposals_real_merge_target_scanned_first(self):
         # If there is a merge proposal where the tip of the source is in the
@@ -210,7 +211,7 @@
         # Other branches for the product are checked, but if the tip revision
         # of the branch is not yet been set no merge event is emitted for that
         # branch.
-        source = self.factory.makeProductBranch(product=self.product)
+        self.factory.makeProductBranch(product=self.product)
         self.autoMergeBranches(self.db_branch, ['revid'])
         self.assertEqual([], self.merges)
 
@@ -333,5 +334,45 @@
             BranchLifecycleStatus.MERGED, source.lifecycle_status)
 
 
+class TestFindMergedRevno(TestCase):
+    """Tests for find_merged_revno."""
+
+    def get_merge_graph(self):
+        # Create a fake merge graph.
+        return [
+            ('rev-3', 0, (3,), False),
+            ('rev-3a', 1, (15, 4, 8), False),
+            ('rev-3b', 1, (15, 4, 7), False),
+            ('rev-3c', 1, (15, 4, 6), False),
+            ('rev-2', 0, (2,), False),
+            ('rev-2a', 1, (4, 4, 8), False),
+            ('rev-2b', 1, (4, 4, 7), False),
+            ('rev-2-1a', 2, (7, 2, 47), False),
+            ('rev-2-1b', 2, (7, 2, 45), False),
+            ('rev-2-1c', 2, (7, 2, 42), False),
+            ('rev-2c', 1, (4, 4, 6), False),
+            ('rev-1', 0, (1,), False),
+            ]
+
+    def assertFoundRevisionNumber(self, expected, rev_id):
+        merge_sorted = self.get_merge_graph()
+        revno = mergedetection.find_merged_revno(merge_sorted, rev_id)
+        if expected is None:
+            self.assertIs(None, revno)
+        else:
+            self.assertEqual(expected, revno)
+
+    def test_not_found(self):
+        # If the rev_id passed into the function isn't in the merge sorted
+        # graph, None is returned.
+        self.assertFoundRevisionNumber(None, 'not-there')
+
+    def test_existing_revision(self):
+        # If a revision is found, the last mainline revision is returned.
+        self.assertFoundRevisionNumber(3, 'rev-3b')
+        self.assertFoundRevisionNumber(2, 'rev-2-1c')
+        self.assertFoundRevisionNumber(1, 'rev-1')
+
+
 def test_suite():
     return unittest.TestLoader().loadTestsFromName(__name__)

=== modified file 'lib/lp/services/tests/test_utils.py'
--- lib/lp/services/tests/test_utils.py	2009-10-19 05:40:52 +0000
+++ lib/lp/services/tests/test_utils.py	2010-04-12 10:04:37 +0000
@@ -5,9 +5,10 @@
 
 __metaclass__ = type
 
+import itertools
 import unittest
 
-from lp.services.utils import iter_split
+from lp.services.utils import CachingIterator, iter_split
 from lp.testing import TestCase
 
 
@@ -28,5 +29,43 @@
             list(iter_split('one/two/three', '/')))
 
 
+class TestCachingIterator(TestCase):
+    """Tests for CachingIterator."""
+
+    def test_reuse(self):
+        # The same iterator can be used multiple times.
+        iterator = CachingIterator(itertools.count())
+        self.assertEqual(
+            [0,1,2,3,4], list(itertools.islice(iterator, 0, 5)))
+        self.assertEqual(
+            [0,1,2,3,4], list(itertools.islice(iterator, 0, 5)))
+
+    def test_more_values(self):
+        # If a subsequent call to iter causes more values to be fetched, they
+        # are also cached.
+        iterator = CachingIterator(itertools.count())
+        self.assertEqual(
+            [0,1,2], list(itertools.islice(iterator, 0, 3)))
+        self.assertEqual(
+            [0,1,2,3,4], list(itertools.islice(iterator, 0, 5)))
+
+    def test_limited_iterator(self):
+        # Make sure that StopIteration is handled correctly.
+        iterator = CachingIterator(iter([0,1,2,3,4]))
+        self.assertEqual(
+            [0,1,2], list(itertools.islice(iterator, 0, 3)))
+        self.assertEqual([0,1,2,3,4], list(iterator))
+
+    def test_parallel_iteration(self):
+        # There can be parallel iterators over the CachingIterator.
+        ci = CachingIterator(iter([0,1,2,3,4]))
+        i1 = iter(ci)
+        i2 = iter(ci)
+        self.assertEqual(0, i1.next())
+        self.assertEqual(0, i2.next())
+        self.assertEqual([1,2,3,4], list(i2))
+        self.assertEqual([1,2,3,4], list(i1))
+
+
 def test_suite():
     return unittest.TestLoader().loadTestsFromName(__name__)

=== modified file 'lib/lp/services/utils.py'
--- lib/lp/services/utils.py	2010-04-09 12:45:48 +0000
+++ lib/lp/services/utils.py	2010-04-12 10:04:37 +0000
@@ -9,12 +9,14 @@
 
 __metaclass__ = type
 __all__ = [
+    'CachingIterator',
     'iter_split',
     'synchronize',
     'text_delta',
     'value_string',
     ]
 
+import itertools
 
 from lazr.enum import BaseItem
 from zope.security.proxy import isinstance as zope_isinstance
@@ -101,3 +103,41 @@
             output.append('')
         output.append('%s changed to:\n\n%s' % (title, delta))
     return '\n'.join(output)
+
+
+class CachingIterator:
+    """Remember the items extracted from the iterator for the next iteration.
+
+    Some generators and iterators are expensive to calculate, like calculating
+    the merge sorted revision graph for a bazaar branch, so you don't want to
+    call them too often.  Rearranging the code so it doesn't call the
+    expensive iterator can make the code awkward.  This class provides a way
+    to have the iterator called once, and the results stored.  The results
+    can then be iterated over again, and more values retrieved from the
+    iterator if necessary.
+    """
+
+    def __init__(self, iterator):
+        self.iterator = iterator
+        self.data = []
+
+    def __iter__(self):
+        index = itertools.count()
+        while True:
+            pos = index.next()
+            try:
+                yield self.data[pos]
+            except IndexError:
+                # Defer to the iterator.
+                pass
+            else:
+                continue
+            if self.iterator is None:
+                break
+            try:
+                item = self.iterator.next()
+            except StopIteration:
+                self.iterator = None
+                break
+            self.data.append(item)
+            yield item