launchpad-reviewers team mailing list archive

[Colin Watson <cjwatson@xxxxxxxxxxxxx>]

Colin Watson has proposed merging lp:~cjwatson/turnip/merge-detection into lp:turnip.

Commit message:
Add a merge detection API.

Requested reviews:
  Launchpad code reviewers (launchpad-reviewers)

For more details, see:
https://code.launchpad.net/~cjwatson/turnip/merge-detection/+merge/261639

Add a merge detection API.

After much experimentation, I realised that the existing Bazaar merge detection in Launchpad relies on doing a topological sort of the history first, and thus uses an algorithm that can be ported directly to git and that was much simpler than anything I'd come up with independently.

This performs acceptably, at least for now: the worst case I've constructed is about four seconds, searching for all unmerged Launchpad branches on my overloaded laptop.  I expect it'll be rather faster in production, and in any case this is a bulk interface running in a job context rather than interactively.
-- 
Your team Launchpad code reviewers is requested to review the proposed merge of lp:~cjwatson/turnip/merge-detection into lp:turnip.

=== modified file 'turnip/api/store.py'
--- turnip/api/store.py	2015-06-02 12:52:50 +0000
+++ turnip/api/store.py	2015-06-10 15:28:38 +0000
@@ -19,6 +19,7 @@
     GIT_OBJ_COMMIT,
     GIT_OBJ_TREE,
     GIT_OBJ_TAG,
+    GIT_SORT_TOPOLOGICAL,
     IndexEntry,
     init_repository,
     Repository,
@@ -341,3 +342,32 @@
             except GitError:
                 pass
         return commits
+
+
+def detect_merges(repo_store, repo_name, target_oid, source_oids):
+    """Check whether each of the requested commits has been merged."""
+    with open_repo(repo_store, repo_name) as repo:
+        target = repo.get(target_oid)
+        if target is None:
+            raise GitError('Object {} does not exist in repository {}.'.format(
+                target_oid, repo_name))
+        if not source_oids:
+            return {}
+
+        search_oids = set(source_oids)
+        merge_info = {}
+        last_mainline = target_oid
+        next_mainline = target_oid
+        for commit in repo.walk(target_oid, GIT_SORT_TOPOLOGICAL):
+            if commit.id.hex == next_mainline:
+                last_mainline = commit.id.hex
+                if commit.parent_ids:
+                    next_mainline = commit.parent_ids[0].hex
+                else:
+                    next_mainline = None
+            if commit.id.hex in search_oids:
+                merge_info[commit.id.hex] = last_mainline
+                search_oids.remove(commit.id.hex)
+            if not search_oids:
+                break
+        return merge_info

=== modified file 'turnip/api/tests/test_api.py'
--- turnip/api/tests/test_api.py	2015-06-02 12:52:50 +0000
+++ turnip/api/tests/test_api.py	2015-06-10 15:28:38 +0000
@@ -544,6 +544,78 @@
         self.assertIn(oid.hex, out)
         self.assertIn(oid2.hex, out)
 
+    def test_repo_detect_merges_missing_target(self):
+        """A non-existent target OID returns HTTP 404."""
+        factory = RepoFactory(self.repo_store)
+        resp = self.app.post_json('/repo/{}/detect-merges/{}'.format(
+            self.repo_path, factory.nonexistent_oid()),
+            {'sources': []}, expect_errors=True)
+        self.assertEqual(404, resp.status_code)
+
+    def test_repo_detect_merges_missing_source(self):
+        """A non-existent source commit is ignored."""
+        factory = RepoFactory(self.repo_store)
+        # A---B
+        a = factory.add_commit('a\n', 'file')
+        b = factory.add_commit('b\n', 'file', parents=[a])
+        resp = self.app.post_json('/repo/{}/detect-merges/{}'.format(
+            self.repo_path, b),
+            {'sources': [factory.nonexistent_oid()]})
+        self.assertEqual(200, resp.status_code)
+        self.assertEqual({}, resp.json)
+
+    def test_repo_detect_merges_unmerged(self):
+        """An unmerged commit is not returned."""
+        factory = RepoFactory(self.repo_store)
+        # A---B
+        #  \
+        #   C
+        a = factory.add_commit('a\n', 'file')
+        b = factory.add_commit('b\n', 'file', parents=[a])
+        c = factory.add_commit('c\n', 'file', parents=[a])
+        resp = self.app.post_json('/repo/{}/detect-merges/{}'.format(
+            self.repo_path, b),
+            {'sources': [c.hex]})
+        self.assertEqual(200, resp.status_code)
+        self.assertEqual({}, resp.json)
+
+    def test_repo_detect_merges_pulled(self):
+        """Commits that were pulled (fast-forward) are their own merge
+        points."""
+        factory = RepoFactory(self.repo_store)
+        # A---B---C
+        a = factory.add_commit('a\n', 'file')
+        b = factory.add_commit('b\n', 'file', parents=[a])
+        c = factory.add_commit('c\n', 'file', parents=[b])
+        # The start commit would never be the source of a merge proposal,
+        # but include it anyway to test boundary conditions.
+        resp = self.app.post_json('/repo/{}/detect-merges/{}'.format(
+            self.repo_path, c),
+            {'sources': [a.hex, b.hex, c.hex]})
+        self.assertEqual(200, resp.status_code)
+        self.assertEqual({a.hex: a.hex, b.hex: b.hex, c.hex: c.hex}, resp.json)
+
+    def test_repo_detect_merges_merged(self):
+        """Commits that were merged have sensible merge points."""
+        factory = RepoFactory(self.repo_store)
+        # A---C---D---G---H
+        #  \ /       /
+        #   B---E---F---I
+        a = factory.add_commit('a\n', 'file')
+        b = factory.add_commit('b\n', 'file', parents=[a])
+        c = factory.add_commit('c\n', 'file', parents=[a, b])
+        d = factory.add_commit('d\n', 'file', parents=[c])
+        e = factory.add_commit('e\n', 'file', parents=[b])
+        f = factory.add_commit('f\n', 'file', parents=[e])
+        g = factory.add_commit('g\n', 'file', parents=[d, f])
+        h = factory.add_commit('h\n', 'file', parents=[g])
+        i = factory.add_commit('i\n', 'file', parents=[f])
+        resp = self.app.post_json('/repo/{}/detect-merges/{}'.format(
+            self.repo_path, h),
+            {'sources': [b.hex, e.hex, i.hex]})
+        self.assertEqual(200, resp.status_code)
+        self.assertEqual({b.hex: c.hex, e.hex: g.hex}, resp.json)
+
 
 if __name__ == '__main__':
     unittest.main()

=== modified file 'turnip/api/views.py'
--- turnip/api/views.py	2015-06-02 12:52:50 +0000
+++ turnip/api/views.py	2015-06-10 15:28:38 +0000
@@ -289,3 +289,32 @@
         except GitError:
             return exc.HTTPNotFound()
         return log
+
+
+@resource(path='/repo/{name}/detect-merges/{target}')
+class DetectMergesAPI(BaseAPI):
+    """Provides HTTP API for detecting merges."""
+
+    def __init__(self, request):
+        super(DetectMergesAPI, self).__init__()
+        self.request = request
+
+    @validate_path
+    def post(self, repo_store, repo_name):
+        """Check whether each of the requested commits has been merged.
+
+        The JSON request dictionary should contain a 'sources' key whose
+        value is a list of source commit OIDs.  The response is a dictionary
+        mapping merged source commit OIDs to the first commit OID in the
+        left-hand (first parent only) history of the target commit that is a
+        descendant of the corresponding source commit.  Unmerged commits are
+        omitted from the response.
+        """
+        target = self.request.matchdict['target']
+        sources = extract_json_data(self.request).get('sources')
+        try:
+            merges = store.detect_merges(
+                repo_store, repo_name, target, sources)
+        except GitError:
+            return exc.HTTPNotFound()
+        return merges