Get the `merge-base` of 2 refs trough the API

This adds an endpoint to get the common ancestor of 2 refs from the API.

7 files changed, 291 insertions, 3 deletions

diff --git a/changelogs/unreleased/bvl-merge-base-api.yml b/changelogs/unreleased/bvl-merge-base-api.yml
new file mode 100644
index 00000000000..78fb3ce0897
--- /dev/null
+++ b/changelogs/unreleased/bvl-merge-base-api.yml
@@ -0,0 +1,5 @@
+---
+title: Get the merge base of two refs through the API
+merge_request: 20929
+author:
+type: added
diff --git a/doc/api/repositories.md b/doc/api/repositories.md
index cb816bbd712..a4fdeca162e 100644
--- a/doc/api/repositories.md
+++ b/doc/api/repositories.md
@@ -204,3 +204,39 @@ Response:
   "deletions": 244
 }]
 ```
+
+## Merge Base
+
+Get the common ancestor for 2 refs (commit SHAs, branch names or tags).
+
+```
+GET /projects/:id/repository/merge_base
+```
+
+| Attribute | Type | Required | Description |
+| --------- | ---- | -------- | ----------- |
+| `id` | integer/string | yes | The ID or [URL-encoded path of the project](README.md#namespaced-path-encoding) |
+| `refs` | array | yes | The refs to find the common ancestor of, for now only 2 refs are supported |
+
+```bash
+curl --header "PRIVATE-TOKEN: 9koXpg98eAheJpvBs5tK" "https://gitlab.example.com/api/v4/projects/5/repository/merge_base?refs[]=304d257dcb821665ab5110318fc58a007bd104ed&refs[]=0031876facac3f2b2702a0e53a26e89939a42209"
+```
+
+Example response:
+
+```json
+{
+	"id": "1a0b36b3cdad1d2ee32457c102a8c0b7056fa863",
+	"short_id": "1a0b36b3",
+	"title": "Initial commit",
+	"created_at": "2014-02-27T08:03:18.000Z",
+	"parent_ids": [],
+	"message": "Initial commit\n",
+	"author_name": "Dmitriy Zaporozhets",
+	"author_email": "dmitriy.zaporozhets@gmail.com",
+	"authored_date": "2014-02-27T08:03:18.000Z",
+	"committer_name": "Dmitriy Zaporozhets",
+	"committer_email": "dmitriy.zaporozhets@gmail.com",
+	"committed_date": "2014-02-27T08:03:18.000Z"
+}
+```
diff --git a/lib/api/repositories.rb b/lib/api/repositories.rb
index 33a9646ac3b..79736107bbb 100644
--- a/lib/api/repositories.rb
+++ b/lib/api/repositories.rb
@@ -123,6 +123,39 @@ module API
           not_found!
         end
       end
+
+      desc 'Get the common ancestor between commits' do
+        success Entities::Commit
+      end
+      params do
+        # For now we just support 2 refs passed, but `merge-base` supports
+        # multiple defining this as an Array instead of 2 separate params will
+        # make sure we don't need to deprecate this API in favor of one
+        # supporting multiple commits when this functionality gets added to
+        # Gitaly
+        requires :refs, type: Array[String]
+      end
+      get ':id/repository/merge_base' do
+        refs = params[:refs]
+
+        unless refs.size == 2
+          render_api_error!('Provide exactly 2 refs', 400)
+        end
+
+        merge_base = Gitlab::Git::MergeBase.new(user_project.repository, refs)
+
+        if merge_base.unknown_refs.any?
+          ref_noun = 'ref'.pluralize(merge_base.unknown_refs.size)
+          message = "Could not find #{ref_noun}: #{merge_base.unknown_refs.join(', ')}"
+          render_api_error!(message, 400)
+        end
+
+        if merge_base.commit
+          present merge_base.commit, with: Entities::Commit
+        else
+          not_found!("Merge Base")
+        end
+      end
     end
   end
 end
diff --git a/lib/gitlab/git.rb b/lib/gitlab/git.rb
index 55236a1122f..2913a3e416d 100644
--- a/lib/gitlab/git.rb
+++ b/lib/gitlab/git.rb
@@ -10,9 +10,11 @@ module Gitlab
     TAG_REF_PREFIX = "refs/tags/".freeze
     BRANCH_REF_PREFIX = "refs/heads/".freeze
 
-    CommandError = Class.new(StandardError)
-    CommitError = Class.new(StandardError)
-    OSError = Class.new(StandardError)
+    BaseError = Class.new(StandardError)
+    CommandError = Class.new(BaseError)
+    CommitError = Class.new(BaseError)
+    OSError = Class.new(BaseError)
+    UnknownRef = Class.new(BaseError)
 
     class << self
       include Gitlab::EncodingHelper
diff --git a/lib/gitlab/git/merge_base.rb b/lib/gitlab/git/merge_base.rb
new file mode 100644
index 00000000000..b27f7038c26
--- /dev/null
+++ b/lib/gitlab/git/merge_base.rb
@@ -0,0 +1,44 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Git
+    class MergeBase
+      include Gitlab::Utils::StrongMemoize
+
+      def initialize(repository, refs)
+        @repository, @refs = repository, refs
+      end
+
+      # Returns the SHA of the first common ancestor
+      def sha
+        if unknown_refs.any?
+          raise UnknownRef, "Can't find merge base for unknown refs: #{unknown_refs.inspect}"
+        end
+
+        strong_memoize(:sha) do
+          @repository.merge_base(*commits_for_refs)
+        end
+      end
+
+      # Returns the merge base as a Gitlab::Git::Commit
+      def commit
+        return unless sha
+
+        @commit ||= @repository.commit_by(oid: sha)
+      end
+
+      # Returns the refs passed on initialization that aren't found in
+      # the repository, and thus cannot be used to find a merge base.
+      def unknown_refs
+        @unknown_refs ||= Hash[@refs.zip(commits_for_refs)]
+                            .select { |ref, commit| commit.nil? }.keys
+      end
+
+      private
+
+      def commits_for_refs
+        @commits_for_refs ||= @repository.commits_by(oids: @refs)
+      end
+    end
+  end
+end
diff --git a/spec/lib/gitlab/git/merge_base_spec.rb b/spec/lib/gitlab/git/merge_base_spec.rb
new file mode 100644
index 00000000000..2f4e043a20f
--- /dev/null
+++ b/spec/lib/gitlab/git/merge_base_spec.rb
@@ -0,0 +1,95 @@
+# frozen_string_literal: true
+
+require 'spec_helper'
+
+describe Gitlab::Git::MergeBase do
+  set(:project) { create(:project, :repository) }
+  let(:repository) { project.repository }
+  subject(:merge_base) { described_class.new(repository, refs) }
+
+  shared_context 'existing refs with a merge base', :existing_refs do
+    let(:refs) do
+      %w(304d257dcb821665ab5110318fc58a007bd104ed 0031876facac3f2b2702a0e53a26e89939a42209)
+    end
+  end
+
+  shared_context 'when passing a missing ref', :missing_ref do
+    let(:refs) do
+      %w(304d257dcb821665ab5110318fc58a007bd104ed aaaa)
+    end
+  end
+
+  shared_context 'when passing refs that do not have a common ancestor', :no_common_ancestor do
+    let(:refs) { ['304d257dcb821665ab5110318fc58a007bd104ed', TestEnv::BRANCH_SHA['orphaned-branch']] }
+  end
+
+  describe '#sha' do
+    context 'when the refs exist', :existing_refs do
+      it 'returns the SHA of the merge base' do
+        expect(merge_base.sha).not_to be_nil
+      end
+
+      it 'memoizes the result' do
+        expect(repository).to receive(:merge_base).once.and_call_original
+
+        2.times { merge_base.sha }
+      end
+    end
+
+    context 'when passing a missing ref', :missing_ref do
+      it 'does not call merge_base on the repository but raises an error' do
+        expect(repository).not_to receive(:merge_base)
+
+        expect { merge_base.sha }.to raise_error(Gitlab::Git::UnknownRef)
+      end
+    end
+
+    it 'returns `nil` when the refs do not have a common ancestor', :no_common_ancestor do
+      expect(merge_base.sha).to be_nil
+    end
+
+    it 'returns a merge base when passing 2 branch names' do
+      merge_base = described_class.new(repository, %w(master feature))
+
+      expect(merge_base.sha).to be_present
+    end
+
+    it 'returns a merge base when passing a tag name' do
+      merge_base = described_class.new(repository, %w(master v1.0.0))
+
+      expect(merge_base.sha).to be_present
+    end
+  end
+
+  describe '#commit' do
+    context 'for existing refs with a merge base', :existing_refs  do
+      it 'finds the commit for the merge base' do
+        expect(merge_base.commit).to be_a(Commit)
+      end
+
+      it 'only looks up the commit once' do
+        expect(repository).to receive(:commit_by).once.and_call_original
+
+        2.times { merge_base.commit }
+      end
+    end
+
+    it 'does not try to find the commit when there is no sha', :no_common_ancestor do
+      expect(repository).not_to receive(:commit_by)
+
+      merge_base.commit
+    end
+  end
+
+  describe '#unknown_refs', :missing_ref do
+    it 'returns the the refs passed that are not part of the repository' do
+      expect(merge_base.unknown_refs).to contain_exactly('aaaa')
+    end
+
+    it 'only looks up the commits once' do
+      expect(merge_base).to receive(:commits_for_refs).once.and_call_original
+
+      2.times { merge_base.unknown_refs }
+    end
+  end
+end
diff --git a/spec/requests/api/repositories_spec.rb b/spec/requests/api/repositories_spec.rb
index 6063afc213d..519638ebb82 100644
--- a/spec/requests/api/repositories_spec.rb
+++ b/spec/requests/api/repositories_spec.rb
@@ -465,4 +465,77 @@ describe API::Repositories do
       end
     end
   end
+
+  describe 'GET :id/repository/merge_base' do
+    let(:refs) do
+      %w(304d257dcb821665ab5110318fc58a007bd104ed 0031876facac3f2b2702a0e53a26e89939a42209)
+    end
+
+    subject(:request) do
+      get(api("/projects/#{project.id}/repository/merge_base", current_user), refs: refs)
+    end
+
+    shared_examples 'merge base' do
+      it 'returns the common ancestor' do
+        request
+
+        expect(response).to have_gitlab_http_status(:success)
+        expect(json_response['id']).to be_present
+      end
+    end
+
+    context 'when unauthenticated', 'and project is public' do
+      it_behaves_like 'merge base' do
+        let(:project) { create(:project, :public, :repository) }
+        let(:current_user) { nil }
+      end
+    end
+
+    context 'when unauthenticated', 'and project is private' do
+      it_behaves_like '404 response' do
+        let(:current_user) { nil }
+        let(:message) { '404 Project Not Found' }
+      end
+    end
+
+    context 'when authenticated', 'as a developer' do
+      it_behaves_like 'merge base' do
+        let(:current_user) { user }
+      end
+    end
+
+    context 'when authenticated', 'as a guest' do
+      it_behaves_like '403 response' do
+        let(:current_user) { guest }
+      end
+    end
+
+    context 'when passing refs that do not exist' do
+      it_behaves_like '400 response' do
+        let(:refs) { %w(304d257dcb821665ab5110318fc58a007bd104ed missing) }
+        let(:current_user) { user }
+        let(:message) { 'Could not find ref: missing' }
+      end
+    end
+
+    context 'when passing refs that do not have a merge base' do
+      it_behaves_like '404 response' do
+        let(:refs) { ['304d257dcb821665ab5110318fc58a007bd104ed', TestEnv::BRANCH_SHA['orphaned-branch']] }
+        let(:current_user) { user }
+        let(:message) { '404 Merge Base Not Found' }
+      end
+    end
+
+    context 'when not enough refs are passed' do
+      let(:refs) { %w(only-one) }
+      let(:current_user) { user }
+
+      it 'renders a bad request error' do
+        request
+
+        expect(response).to have_gitlab_http_status(:bad_request)
+        expect(json_response['message']).to eq('Provide exactly 2 refs')
+      end
+    end
+  end
 end