Add CommitCollection.FindCommonAncestor()

Fix issue #149

5 files changed, 257 insertions, 1 deletions

diff --git a/LibGit2Sharp.Tests/CommitAncestorFixture.cs b/LibGit2Sharp.Tests/CommitAncestorFixture.cs
new file mode 100644
index 00000000..d8e523c1
--- /dev/null
+++ b/LibGit2Sharp.Tests/CommitAncestorFixture.cs
@@ -0,0 +1,162 @@
+using System;
+using System.Linq;
+using LibGit2Sharp.Tests.TestHelpers;
+using Xunit;
+
+namespace LibGit2Sharp.Tests
+{
+    public class CommitAncestorFixture : BaseFixture
+    {
+        /*
+         * BareTestRepoPath structure
+         *
+         *  * commit 4c062a6361ae6959e06292c1fa5e2822d9c96345
+         *  |
+         *  *   commit be3563ae3f795b2b4353bcce3a527ad0a4f7f644
+         *  |\
+         *  | |
+         *  | * commit c47800c7266a2be04c571c04d5a6614691ea99bd
+         *  | |
+         *  * | commit 9fd738e8f7967c078dceed8190330fc8648ee56a
+         *  | |
+         *  * | commit 4a202b346bb0fb0db7eff3cffeb3c70babbd2045
+         *  |/
+         *  |
+         *  * commit 5b5b025afb0b4c913b4c338a42934a3863bf3644
+         *  |
+         *  * commit 8496071c1b46c854b31185ea97743be6a877447
+         *
+        */
+
+        [Fact]
+        public void CanFindCommonAncestorForTwoCommits()
+        {
+            using (var repo = new Repository(BareTestRepoPath))
+            {
+                var first = repo.Lookup<Commit>("c47800c7266a2be04c571c04d5a6614691ea99bd");
+                var second = repo.Lookup<Commit>("9fd738e8f7967c078dceed8190330fc8648ee56a");
+
+                Commit ancestor = repo.Commits.FindCommonAncestor(first, second);
+
+                Assert.NotNull(ancestor);
+                ancestor.Id.Sha.ShouldEqual("5b5b025afb0b4c913b4c338a42934a3863bf3644");
+            }
+        }
+
+        [Fact]
+        public void CanFindCommonAncestorForTwoCommitsAsEnumerable()
+        {
+            using (var repo = new Repository(BareTestRepoPath))
+            {
+                var first = repo.Lookup<Commit>("c47800c7266a2be04c571c04d5a6614691ea99bd");
+                var second = repo.Lookup<Commit>("9fd738e8f7967c078dceed8190330fc8648ee56a");
+
+                Commit ancestor = repo.Commits.FindCommonAncestor(new[] { first, second });
+
+                Assert.NotNull(ancestor);
+                ancestor.Id.Sha.ShouldEqual("5b5b025afb0b4c913b4c338a42934a3863bf3644");
+            }
+        }
+
+        [Fact]
+        public void CanFindCommonAncestorForSeveralCommits()
+        {
+            using (var repo = new Repository(BareTestRepoPath))
+            {
+                var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
+                var second = repo.Lookup<Commit>("be3563ae3f795b2b4353bcce3a527ad0a4f7f644");
+                var third = repo.Lookup<Commit>("c47800c7266a2be04c571c04d5a6614691ea99bd");
+                var fourth = repo.Lookup<Commit>("5b5b025afb0b4c913b4c338a42934a3863bf3644");
+
+                Commit ancestor = repo.Commits.FindCommonAncestor(new[] { first, second, third, fourth });
+
+                Assert.NotNull(ancestor);
+                ancestor.Id.Sha.ShouldEqual("5b5b025afb0b4c913b4c338a42934a3863bf3644");
+            }
+        }
+
+        [Fact]
+        public void CannotFindAncestorForTwoCommmitsWithoutCommonAncestor()
+        {
+            var scd = BuildTemporaryCloneOfTestRepo();
+
+            using (var repo = new Repository(scd.RepositoryPath))
+            {
+                var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
+                var second = repo.Lookup<Commit>("be3563ae3f795b2b4353bcce3a527ad0a4f7f644");
+                var third = repo.Lookup<Commit>("c47800c7266a2be04c571c04d5a6614691ea99bd");
+                var fourth = repo.Lookup<Commit>("5b5b025afb0b4c913b4c338a42934a3863bf3644");
+
+                Commit orphanedCommit = CreateOrphanedCommit(repo);
+
+                Commit ancestor = repo.Commits.FindCommonAncestor(new[] { first, second, orphanedCommit, third, fourth });
+                Assert.Null(ancestor);
+            }
+        }
+
+        [Fact]
+        public void CannotFindCommonAncestorForSeveralCommmitsWithoutCommonAncestor()
+        {
+            var scd = BuildTemporaryCloneOfTestRepo();
+
+            using (var repo = new Repository(scd.RepositoryPath))
+            {
+                var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
+
+                var orphanedCommit = CreateOrphanedCommit(repo);
+
+                Commit ancestor = repo.Commits.FindCommonAncestor(first, orphanedCommit);
+                Assert.Null(ancestor);
+            }
+        }
+
+        private static Commit CreateOrphanedCommit(Repository repo)
+        {
+            Commit random = repo.Head.Tip;
+
+            Commit orphanedCommit = repo.ObjectDatabase.CreateCommit(
+                "This is a test commit created by 'CommitFixture.CannotFindCommonAncestorForCommmitsWithoutCommonAncestor'",
+                random.Author,
+                random.Committer,
+                random.Tree,
+                Enumerable.Empty<Commit>());
+
+            return orphanedCommit;
+        }
+
+        [Fact]
+        public void FindCommonAncestorForSingleCommitThrows()
+        {
+            using (var repo = new Repository(BareTestRepoPath))
+            {
+                var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
+
+                Assert.Throws<ArgumentException>(() => repo.Commits.FindCommonAncestor(new[] { first }));
+            }
+        }
+
+        [Fact]
+        public void FindCommonAncestorForEnumerableWithNullCommitThrows()
+        {
+            using (var repo = new Repository(BareTestRepoPath))
+            {
+                var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
+                var second = repo.Lookup<Commit>("be3563ae3f795b2b4353bcce3a527ad0a4f7f644");
+
+                Assert.Throws<ArgumentException>(() => repo.Commits.FindCommonAncestor(new[] { first, second, null }));
+            }
+        }
+
+        [Fact]
+        public void FindCommonAncestorForWithNullCommitThrows()
+        {
+            using (var repo = new Repository(BareTestRepoPath))
+            {
+                var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
+
+                Assert.Throws<ArgumentNullException>(() => repo.Commits.FindCommonAncestor(first, null));
+                Assert.Throws<ArgumentNullException>(() => repo.Commits.FindCommonAncestor(null, first));
+            }
+        }
+    }
+}
diff --git a/LibGit2Sharp.Tests/LibGit2Sharp.Tests.csproj b/LibGit2Sharp.Tests/LibGit2Sharp.Tests.csproj
index 52b8cbe7..acc31284 100644
--- a/LibGit2Sharp.Tests/LibGit2Sharp.Tests.csproj
+++ b/LibGit2Sharp.Tests/LibGit2Sharp.Tests.csproj
@@ -45,6 +45,7 @@
   <ItemGroup>
     <Compile Include="ConfigurationFixture.cs" />
     <Compile Include="AttributesFixture.cs" />
+    <Compile Include="CommitAncestorFixture.cs" />
     <Compile Include="DiffBlobToBlobFixture.cs" />
     <Compile Include="ObjectDatabaseFixture.cs" />
     <Compile Include="DiffTreeToTreeFixture.cs" />
diff --git a/LibGit2Sharp/CommitCollection.cs b/LibGit2Sharp/CommitCollection.cs
index 6d6186df..d58a9f40 100644
--- a/LibGit2Sharp/CommitCollection.cs
+++ b/LibGit2Sharp/CommitCollection.cs
@@ -125,6 +125,75 @@ namespace LibGit2Sharp
         }
 
         /// <summary>
+        ///   Find the best possible common ancestor given two <see cref = "Commit"/>s.
+        /// </summary>
+        /// <param name = "first">The first <see cref = "Commit"/>.</param>
+        /// <param name = "second">The second <see cref = "Commit"/>.</param>
+        /// <returns>The common ancestor or null if none found.</returns>
+        public Commit FindCommonAncestor(Commit first, Commit second)
+        {
+            Ensure.ArgumentNotNull(first, "first");
+            Ensure.ArgumentNotNull(second, "second");
+
+            using (var osw1 = new ObjectSafeWrapper(first.Id, repo))
+            using (var osw2 = new ObjectSafeWrapper(second.Id, repo))
+            {
+                GitOid ret;
+                int result = NativeMethods.git_merge_base(out ret, repo.Handle, osw1.ObjectPtr, osw2.ObjectPtr);
+
+                if (result == (int)GitErrorCode.GIT_ENOTFOUND)
+                {
+                    return null;
+                }
+
+                Ensure.Success(result);
+
+                return repo.Lookup<Commit>(new ObjectId(ret));
+            }
+        }
+
+        /// <summary>
+        ///   Find the best possible common ancestor given two or more <see cref="Commit"/>.
+        /// </summary>
+        /// <param name = "commits">The <see cref = "Commit"/>s for which to find the common ancestor.</param>
+        /// <returns>The common ancestor or null if none found.</returns>
+        public Commit FindCommonAncestor(IEnumerable<Commit> commits)
+        {
+            Ensure.ArgumentNotNull(commits, "commits");
+            Commit ret = null;
+            int count = 0;
+
+            foreach (var commit in commits)
+            {
+                if (commit == null)
+                {
+                    throw new ArgumentException("Enumerable contains null at position: " + count.ToString(CultureInfo.InvariantCulture), "commits");
+                }
+
+                count++;
+
+                if (count == 1)
+                {
+                    ret = commit;
+                    continue;
+                }
+
+                ret = FindCommonAncestor(ret, commit);
+                if (ret == null)
+                {
+                    break;
+                }
+            }
+
+            if (count < 2)
+            {
+                throw new ArgumentException("The enumerable must contains at least two commits.", "commits");
+            }
+
+            return ret;
+        }
+
+        /// <summary>
         ///   Stores the content of the <see cref = "Repository.Index" /> as a new <see cref = "Commit" /> into the repository.
         ///   The tip of the <see cref = "Repository.Head"/> will be used as the parent of this new Commit.
         ///   Once the commit is created, the <see cref = "Repository.Head"/> will move forward to point at it.
diff --git a/LibGit2Sharp/Core/NativeMethods.cs b/LibGit2Sharp/Core/NativeMethods.cs
index 845e147f..0b7a11cf 100644
--- a/LibGit2Sharp/Core/NativeMethods.cs
+++ b/LibGit2Sharp/Core/NativeMethods.cs
@@ -331,6 +331,13 @@ namespace LibGit2Sharp.Core
         public static extern int git_index_write(IndexSafeHandle index);
 
         [DllImport(libgit2)]
+        public static extern int git_merge_base(
+            out GitOid mergeBase,
+            RepositorySafeHandle repo,
+            GitObjectSafeHandle one,
+            GitObjectSafeHandle two);
+
+        [DllImport(libgit2)]
         public static extern int git_odb_exists(ObjectDatabaseSafeHandle odb, ref GitOid id);
 
         [DllImport(libgit2)]
diff --git a/LibGit2Sharp/IQueryableCommitCollection.cs b/LibGit2Sharp/IQueryableCommitCollection.cs
index d596d77a..a57c12ec 100644
--- a/LibGit2Sharp/IQueryableCommitCollection.cs
+++ b/LibGit2Sharp/IQueryableCommitCollection.cs
@@ -1,4 +1,6 @@
-namespace LibGit2Sharp
+using System.Collections.Generic;
+
+namespace LibGit2Sharp
 {
     public interface IQueryableCommitCollection : ICommitCollection //TODO: Find a name that's more explicit than IQueryableCommitCollection
     {
@@ -20,5 +22,20 @@
         /// <param name = "amendPreviousCommit">True to amend the current <see cref = "Commit"/> pointed at by <see cref = "Repository.Head"/>, false otherwise.</param>
         /// <returns>The generated <see cref = "Commit" />.</returns>
         Commit Create(string message, Signature author, Signature committer, bool amendPreviousCommit);
+
+        /// <summary>
+        ///   Find the best possible common ancestor given two <see cref = "Commit"/>s.
+        /// </summary>
+        /// <param name = "first">The first <see cref = "Commit"/>.</param>
+        /// <param name = "second">The second <see cref = "Commit"/>.</param>
+        /// <returns>The common ancestor or null if none found.</returns>
+        Commit FindCommonAncestor(Commit first, Commit second);
+
+        /// <summary>
+        ///   Find the best possible common ancestor given two or more <see cref = "Commit"/>s.
+        /// </summary>
+        /// <param name = "commits">The <see cref = "Commit"/> for which to find the common ancestor.</param>
+        /// <returns>The common ancestor or null if none found.</returns>
+        Commit FindCommonAncestor(IEnumerable<Commit> commits);
     }
 }