Merge ~cjwatson/launchpad:faster-detect-merges into launchpad:master

[Colin Watson]

Speed up merge detection in repositories with deep history

Merge detection can be very slow for repositories with deep history, because as currently defined it has to walk through the whole ancestry of a given target commit looking for "mainline" (first parent only) commits that introduce a merge of any of the given source commits. In particular, this often times out for Linux kernel repositories.

However, we can do much better. Merge proposals are normally only created in Launchpad once the target branch has been scanned, and we can reasonably assume that when a merge proposal is created it won't yet have been merged. This means that Launchpad can tell turnip's `detect-merges` API to stop walking through history whenever it encounters the commit that it had previously scanned on the target branch, and then we only have to look through the changes introduced by a push rather than the entire history of the branch. This should be much less likely to time out.

(See also https://code.launchpad.net/~cjwatson/turnip/+git/turnip/+merge/445341.)

[Simone Pelosi (pelpsi)]

LGTM!

review: Approve

diff --git a/lib/lp/code/interfaces/githosting.py b/lib/lp/code/interfaces/githosting.py
index 03cdcab..5486efa 100644
--- a/lib/lp/code/interfaces/githosting.py
+++ b/lib/lp/code/interfaces/githosting.py
@@ -105,12 +105,14 @@ class IGitHostingClient(Interface):
             to a list of conflicted paths.
         """
 
-    def detectMerges(path, target, sources, logger=None):
+    def detectMerges(path, target, sources, previous_target=None, logger=None):
         """Detect merges of any of 'sources' into 'target'.
 
         :param path: Physical path of the repository on the hosting service.
         :param target: The OID of the merge proposal target commit.
         :param sources: The OIDs of the merge proposal source commits.
+        :param previous_target: If not None, stop walking back through
+            history upon reaching this commit.
         :param logger: An optional logger.
         :return: A dict mapping merged commit OIDs from 'sources' to the
             first commit OID in the left-hand (first parent only) history of
diff --git a/lib/lp/code/interfaces/gitrepository.py b/lib/lp/code/interfaces/gitrepository.py
index 4f57972..354d2df 100644
--- a/lib/lp/code/interfaces/gitrepository.py
+++ b/lib/lp/code/interfaces/gitrepository.py
@@ -826,12 +826,15 @@ class IGitRepositoryView(IHasRecipes):
             based on one of these paths will be marked as stale.
         """
 
-    def detectMerges(paths, logger=None):
+    def detectMerges(paths, previous_targets, logger=None):
         """Detect merges of landing candidates.
 
         :param paths: A list of reference paths.  Any merge proposals whose
             target is this repository and one of these paths will be
             checked.
+        :param previous_targets: A dictionary mapping merge proposal IDs to
+            their previous target commit IDs, before the current ref scan
+            job updated them.
         :param logger: An optional logger.
         """
 
diff --git a/lib/lp/code/model/githosting.py b/lib/lp/code/model/githosting.py
index 0679bb0..5ed215a 100644
--- a/lib/lp/code/model/githosting.py
+++ b/lib/lp/code/model/githosting.py
@@ -261,18 +261,28 @@ class GitHostingClient:
                 "Failed to get merge diff from Git repository: %s" % str(e)
             )
 
-    def detectMerges(self, path, target, sources, logger=None):
+    def detectMerges(
+        self, path, target, sources, previous_target=None, logger=None
+    ):
         """See `IGitHostingClient`."""
         sources = list(sources)
+        stop = [] if previous_target is None else [previous_target]
         try:
             if logger is not None:
                 logger.info(
-                    "Detecting merges for %s from %s to %s"
-                    % (path, sources, target)
+                    "Detecting merges for %s from %s to %s%s"
+                    % (
+                        path,
+                        sources,
+                        target,
+                        ""
+                        if previous_target is None
+                        else " (stopping at %s)" % previous_target,
+                    )
                 )
             return self._post(
                 "/repo/%s/detect-merges/%s" % (path, quote(target)),
-                json={"sources": sources},
+                json={"sources": sources, "stop": stop},
             )
         except requests.RequestException as e:
             raise GitRepositoryScanFault(
diff --git a/lib/lp/code/model/gitrepository.py b/lib/lp/code/model/gitrepository.py
index a91df2e..85240eb 100644
--- a/lib/lp/code/model/gitrepository.py
+++ b/lib/lp/code/model/gitrepository.py
@@ -1550,7 +1550,7 @@ class GitRepository(
         with BranchMergeProposalNoPreviewDiffDelta.monitor(proposal):
             proposal.markAsMerged(merged_revision_id=merged_revision_id)
 
-    def detectMerges(self, paths, logger=None):
+    def detectMerges(self, paths, previous_targets, logger=None):
         """See `IGitRepository`."""
         hosting_client = getUtility(IGitHostingClient)
         all_proposals = self.getActiveLandingCandidates(paths).order_by(
@@ -1562,6 +1562,7 @@ class GitRepository(
                 self.getInternalPath(),
                 proposals[0].target_git_commit_sha1,
                 {proposal.source_git_commit_sha1 for proposal in proposals},
+                previous_target=previous_targets.get(proposals[0].id),
             )
             for proposal in proposals:
                 merged_revision_id = merges.get(
diff --git a/lib/lp/code/model/tests/test_githosting.py b/lib/lp/code/model/tests/test_githosting.py
index af50950..0f5cf62 100644
--- a/lib/lp/code/model/tests/test_githosting.py
+++ b/lib/lp/code/model/tests/test_githosting.py
@@ -443,7 +443,19 @@ class TestGitHostingClient(TestCase):
         self.assertRequest(
             "repo/123/detect-merges/a",
             method="POST",
-            json_data={"sources": ["b", "c"]},
+            json_data={"sources": ["b", "c"], "stop": []},
+        )
+
+    def test_detectMerges_previous_target(self):
+        with self.mockRequests("POST", json={"b": "0"}):
+            merges = self.client.detectMerges(
+                "123", "a", ["b", "c"], previous_target="d"
+            )
+        self.assertEqual({"b": "0"}, merges)
+        self.assertRequest(
+            "repo/123/detect-merges/a",
+            method="POST",
+            json_data={"sources": ["b", "c"], "stop": ["d"]},
         )
 
     def test_detectMerges_failure(self):
diff --git a/lib/lp/code/model/tests/test_gitrepository.py b/lib/lp/code/model/tests/test_gitrepository.py
index 6f05eb7..29e8d59 100644
--- a/lib/lp/code/model/tests/test_gitrepository.py
+++ b/lib/lp/code/model/tests/test_gitrepository.py
@@ -3937,6 +3937,9 @@ class TestGitRepositoryDetectMerges(TestCaseWithFactory):
         bmp3 = self.factory.makeBranchMergeProposalForGit(
             target_ref=target_2, source_ref=source_1
         )
+        previous_targets = {
+            bmp.id: bmp.target_git_commit_sha1 for bmp in (bmp1, bmp2, bmp3)
+        }
         hosting_fixture = self.useFixture(
             GitHostingFixture(merges={source_1.commit_sha1: "0" * 40})
         )
@@ -3958,20 +3961,26 @@ class TestGitRepositoryDetectMerges(TestCaseWithFactory):
         _, events = self.assertNotifies(
             expected_events, True, repository.createOrUpdateRefs, refs_info
         )
-        expected_args = [
+        expected_calls = [
             (
-                repository.getInternalPath(),
-                target_1.commit_sha1,
-                {source_1.commit_sha1, source_2.commit_sha1},
+                (
+                    repository.getInternalPath(),
+                    target_1.commit_sha1,
+                    {source_1.commit_sha1, source_2.commit_sha1},
+                ),
+                {"previous_target": previous_targets[bmp1.id]},
             ),
             (
-                repository.getInternalPath(),
-                target_2.commit_sha1,
-                {source_1.commit_sha1},
+                (
+                    repository.getInternalPath(),
+                    target_2.commit_sha1,
+                    {source_1.commit_sha1},
+                ),
+                {"previous_target": previous_targets[bmp3.id]},
             ),
         ]
         self.assertContentEqual(
-            expected_args, hosting_fixture.detectMerges.extract_args()
+            expected_calls, hosting_fixture.detectMerges.calls
         )
         self.assertEqual(BranchMergeProposalStatus.MERGED, bmp1.queue_status)
         self.assertEqual("0" * 40, bmp1.merged_revision_id)
diff --git a/lib/lp/code/subscribers/git.py b/lib/lp/code/subscribers/git.py
index 99c4643..8fc11fb 100644
--- a/lib/lp/code/subscribers/git.py
+++ b/lib/lp/code/subscribers/git.py
@@ -21,10 +21,17 @@ def refs_created(repository, event):
 
 def refs_updated(repository, event):
     """Some references in a Git repository have been updated."""
+    # Remember the previous target commit IDs so that detectMerges can know
+    # how far back in history it needs to search.
+    previous_targets = {
+        bmp.id: bmp.target_git_commit_sha1
+        for bmp in repository.getActiveLandingCandidates(event.paths)
+    }
+
     repository.updateMergeCommitIDs(event.paths)
     repository.updateLandingTargets(event.paths)
     repository.markRecipesStale(event.paths)
     repository.markSnapsStale(event.paths)
     repository.markCharmRecipesStale(event.paths)
-    repository.detectMerges(event.paths, logger=event.logger)
+    repository.detectMerges(event.paths, previous_targets, logger=event.logger)
     _request_ci_builds(repository, event)