Skip to content

Commit bca2f0e

Browse files
AimeastAimeast
committed
Enrich the merge base
1. Bind git_merge_base_many and git_merge_base_octopus 2. Drop git_merge_base 3. Introduce enumeration MergeBaseFindingStrategy 4. Refactor the test case
1 parent eb08934 commit bca2f0e

File tree

6 files changed

+173
-120
lines changed

6 files changed

+173
-120
lines changed

‎LibGit2Sharp.Tests/CommitAncestorFixture.cs

Lines changed: 59 additions & 90 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22
using System.Linq;
33
using LibGit2Sharp.Tests.TestHelpers;
44
using Xunit;
5+
using Xunit.Extensions;
56

67
namespace LibGit2Sharp.Tests
78
{
@@ -28,83 +29,86 @@ public class CommitAncestorFixture : BaseFixture
2829
*
2930
*/
3031

31-
[Fact]
32-
public void CanFindCommonAncestorForTwoCommits()
32+
[Theory]
33+
[InlineData("5b5b025afb0b4c913b4c338a42934a3863bf3644", "c47800c", "9fd738e")]
34+
[InlineData("9fd738e8f7967c078dceed8190330fc8648ee56a", "be3563a", "9fd738e")]
35+
[InlineData(null, "be3563a", "-")]
36+
public void FindCommonAncestorForTwoCommits(string result, string sha1, string sha2)
3337
{
3438
using (var repo = new Repository(BareTestRepoPath))
3539
{
36-
var first = repo.Lookup<Commit>("c47800c7266a2be04c571c04d5a6614691ea99bd");
37-
var second = repo.Lookup<Commit>("9fd738e8f7967c078dceed8190330fc8648ee56a");
38-
39-
Commit ancestor = repo.Commits.FindCommonAncestor(first, second);
40-
41-
Assert.NotNull(ancestor);
42-
Assert.Equal("5b5b025afb0b4c913b4c338a42934a3863bf3644", ancestor.Id.Sha);
40+
var first = sha1 == "-" ? CreateOrphanedCommit(repo) : repo.Lookup<Commit>(sha1);
41+
var second = sha2 == "-" ? CreateOrphanedCommit(repo) : repo.Lookup<Commit>(sha2);
42+
43+
Commit ancestor = repo.Commits.FindMergeBase(first, second);
44+
45+
if (result == null)
46+
{
47+
Assert.Null(ancestor);
48+
}
49+
else
50+
{
51+
Assert.NotNull(ancestor);
52+
Assert.Equal(result, ancestor.Id.Sha);
53+
}
4354
}
4455
}
4556

46-
[Fact]
47-
public void CanFindCommonAncestorForTwoCommitsAsEnumerable()
57+
[Theory]
58+
[InlineData("5b5b025afb0b4c913b4c338a42934a3863bf3644", new[] { "c47800c", "9fd738e" }, MergeBaseFindingStrategy.Octopus)]
59+
[InlineData("5b5b025afb0b4c913b4c338a42934a3863bf3644", new[] { "c47800c", "9fd738e" }, MergeBaseFindingStrategy.Standard)]
60+
[InlineData("5b5b025afb0b4c913b4c338a42934a3863bf3644", new[] { "4c062a6", "be3563a", "c47800c", "5b5b025" }, MergeBaseFindingStrategy.Octopus)]
61+
[InlineData("be3563ae3f795b2b4353bcce3a527ad0a4f7f644", new[] { "4c062a6", "be3563a", "c47800c", "5b5b025" }, MergeBaseFindingStrategy.Standard)]
62+
[InlineData(null, new[] { "4c062a6", "be3563a", "-", "c47800c", "5b5b025" }, MergeBaseFindingStrategy.Octopus)]
63+
[InlineData("be3563ae3f795b2b4353bcce3a527ad0a4f7f644", new[] { "4c062a6", "be3563a", "-", "c47800c", "5b5b025" }, MergeBaseFindingStrategy.Standard)]
64+
[InlineData(null, new[] { "4c062a6", "-" }, MergeBaseFindingStrategy.Octopus)]
65+
[InlineData(null, new[] { "4c062a6", "-" }, MergeBaseFindingStrategy.Standard)]
66+
public void FindCommonAncestorForCommitsAsEnumerable(string result, string[] shas, MergeBaseFindingStrategy strategy)
4867
{
4968
using (var repo = new Repository(BareTestRepoPath))
5069
{
51-
var first = repo.Lookup<Commit>("c47800c7266a2be04c571c04d5a6614691ea99bd");
52-
var second = repo.Lookup<Commit>("9fd738e8f7967c078dceed8190330fc8648ee56a");
53-
54-
Commit ancestor = repo.Commits.FindCommonAncestor(new[] { first, second });
55-
56-
Assert.NotNull(ancestor);
57-
Assert.Equal("5b5b025afb0b4c913b4c338a42934a3863bf3644", ancestor.Id.Sha);
70+
var commits = shas.Select(sha => sha == "-" ? CreateOrphanedCommit(repo) : repo.Lookup<Commit>(sha)).ToArray();
71+
72+
Commit ancestor = repo.Commits.FindMergeBase(commits, strategy);
73+
74+
if (result == null)
75+
{
76+
Assert.Null(ancestor);
77+
}
78+
else
79+
{
80+
Assert.NotNull(ancestor);
81+
Assert.Equal(result, ancestor.Id.Sha);
82+
}
5883
}
5984
}
6085

61-
[Fact]
62-
public void CanFindCommonAncestorForSeveralCommits()
86+
[Theory]
87+
[InlineData("4c062a6", "0000000")]
88+
[InlineData("0000000", "4c062a6")]
89+
public void FindCommonAncestorForTwoCommitsThrows(string sha1, string sha2)
6390
{
6491
using (var repo = new Repository(BareTestRepoPath))
6592
{
66-
var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
67-
var second = repo.Lookup<Commit>("be3563ae3f795b2b4353bcce3a527ad0a4f7f644");
68-
var third = repo.Lookup<Commit>("c47800c7266a2be04c571c04d5a6614691ea99bd");
69-
var fourth = repo.Lookup<Commit>("5b5b025afb0b4c913b4c338a42934a3863bf3644");
70-
71-
Commit ancestor = repo.Commits.FindCommonAncestor(new[] { first, second, third, fourth });
72-
73-
Assert.NotNull(ancestor);
74-
Assert.Equal("5b5b025afb0b4c913b4c338a42934a3863bf3644", ancestor.Id.Sha);
75-
}
76-
}
77-
78-
[Fact]
79-
public void CannotFindAncestorForTwoCommmitsWithoutCommonAncestor()
80-
{
81-
string path = CloneBareTestRepo();
82-
using (var repo = new Repository(path))
83-
{
84-
var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
85-
var second = repo.Lookup<Commit>("be3563ae3f795b2b4353bcce3a527ad0a4f7f644");
86-
var third = repo.Lookup<Commit>("c47800c7266a2be04c571c04d5a6614691ea99bd");
87-
var fourth = repo.Lookup<Commit>("5b5b025afb0b4c913b4c338a42934a3863bf3644");
88-
89-
Commit orphanedCommit = CreateOrphanedCommit(repo);
93+
var first = repo.Lookup<Commit>(sha1);
94+
var second = repo.Lookup<Commit>(sha2);
9095

91-
Commit ancestor = repo.Commits.FindCommonAncestor(new[] { first, second, orphanedCommit, third, fourth });
92-
Assert.Null(ancestor);
96+
Assert.Throws<ArgumentNullException>(() => repo.Commits.FindMergeBase(first, second));
9397
}
9498
}
9599

96-
[Fact]
97-
public void CannotFindCommonAncestorForSeveralCommmitsWithoutCommonAncestor()
100+
[Theory]
101+
[InlineData(new[] { "4c062a6" }, MergeBaseFindingStrategy.Octopus)]
102+
[InlineData(new[] { "4c062a6" }, MergeBaseFindingStrategy.Standard)]
103+
[InlineData(new[] { "4c062a6", "be3563a", "000000" }, MergeBaseFindingStrategy.Octopus)]
104+
[InlineData(new[] { "4c062a6", "be3563a", "000000" }, MergeBaseFindingStrategy.Standard)]
105+
public void FindCommonAncestorForCommitsAsEnumerableThrows(string[] shas, MergeBaseFindingStrategy strategy)
98106
{
99-
string path = CloneBareTestRepo();
100-
using (var repo = new Repository(path))
107+
using (var repo = new Repository(BareTestRepoPath))
101108
{
102-
var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
103-
104-
var orphanedCommit = CreateOrphanedCommit(repo);
109+
var commits = shas.Select(sha => sha == "-" ? CreateOrphanedCommit(repo) : repo.Lookup<Commit>(sha)).ToArray();
105110

106-
Commit ancestor = repo.Commits.FindCommonAncestor(first, orphanedCommit);
107-
Assert.Null(ancestor);
111+
Assert.Throws<ArgumentException>(() => repo.Commits.FindMergeBase(commits, strategy));
108112
}
109113
}
110114

@@ -122,40 +126,5 @@ private static Commit CreateOrphanedCommit(IRepository repo)
122126

123127
return orphanedCommit;
124128
}
125-
126-
[Fact]
127-
public void FindCommonAncestorForSingleCommitThrows()
128-
{
129-
using (var repo = new Repository(BareTestRepoPath))
130-
{
131-
var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
132-
133-
Assert.Throws<ArgumentException>(() => repo.Commits.FindCommonAncestor(new[] { first }));
134-
}
135-
}
136-
137-
[Fact]
138-
public void FindCommonAncestorForEnumerableWithNullCommitThrows()
139-
{
140-
using (var repo = new Repository(BareTestRepoPath))
141-
{
142-
var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
143-
var second = repo.Lookup<Commit>("be3563ae3f795b2b4353bcce3a527ad0a4f7f644");
144-
145-
Assert.Throws<ArgumentException>(() => repo.Commits.FindCommonAncestor(new[] { first, second, null }));
146-
}
147-
}
148-
149-
[Fact]
150-
public void FindCommonAncestorForWithNullCommitThrows()
151-
{
152-
using (var repo = new Repository(BareTestRepoPath))
153-
{
154-
var first = repo.Lookup<Commit>("4c062a6361ae6959e06292c1fa5e2822d9c96345");
155-
156-
Assert.Throws<ArgumentNullException>(() => repo.Commits.FindCommonAncestor(first, null));
157-
Assert.Throws<ArgumentNullException>(() => repo.Commits.FindCommonAncestor(null, first));
158-
}
159-
}
160129
}
161130
}

‎LibGit2Sharp/CommitLog.cs

Lines changed: 63 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -87,26 +87,49 @@ public ICommitLog QueryBy(CommitFilter filter)
8787
/// <param name="first">The first <see cref="Commit"/>.</param>
8888
/// <param name="second">The second <see cref="Commit"/>.</param>
8989
/// <returns>The common ancestor or null if none found.</returns>
90+
[Obsolete("This method will be removed in the next release. Please use FindMergeBase(Commit, Commit).")]
9091
public Commit FindCommonAncestor(Commit first, Commit second)
9192
{
92-
Ensure.ArgumentNotNull(first, "first");
93-
Ensure.ArgumentNotNull(second, "second");
94-
95-
ObjectId id = Proxy.git_merge_base(repo.Handle, first, second);
96-
97-
return id == null ? null : repo.Lookup<Commit>(id);
93+
return FindMergeBase(first, second);
9894
}
9995

10096
/// <summary>
10197
/// Find the best possible common ancestor given two or more <see cref="Commit"/>.
10298
/// </summary>
10399
/// <param name="commits">The <see cref="Commit"/>s for which to find the common ancestor.</param>
104100
/// <returns>The common ancestor or null if none found.</returns>
101+
[Obsolete("This method will be removed in the next release. Please use FindMergeBase(IEnumerable<Commit>, MergeBaseFindingStrategy).")]
105102
public Commit FindCommonAncestor(IEnumerable<Commit> commits)
103+
{
104+
return FindMergeBase(commits, MergeBaseFindingStrategy.Octopus);
105+
}
106+
107+
/// <summary>
108+
/// Find the best possible merge base given two <see cref="Commit"/>s.
109+
/// </summary>
110+
/// <param name="first">The first <see cref="Commit"/>.</param>
111+
/// <param name="second">The second <see cref="Commit"/>.</param>
112+
/// <returns>The merge base or null if none found.</returns>
113+
public Commit FindMergeBase(Commit first, Commit second)
114+
{
115+
Ensure.ArgumentNotNull(first, "first");
116+
Ensure.ArgumentNotNull(second, "second");
117+
118+
return FindMergeBase(new[] { first, second }, MergeBaseFindingStrategy.Standard);
119+
}
120+
121+
/// <summary>
122+
/// Find the best possible merge base given two or more <see cref="Commit"/> according to the <see cref="MergeBaseFindingStrategy"/>.
123+
/// </summary>
124+
/// <param name="commits">The <see cref="Commit"/>s for which to find the merge base.</param>
125+
/// <param name="strategy">The strategy to leverage in order to find the merge base.</param>
126+
/// <returns>The merge base or null if none found.</returns>
127+
public Commit FindMergeBase(IEnumerable<Commit> commits, MergeBaseFindingStrategy strategy)
106128
{
107129
Ensure.ArgumentNotNull(commits, "commits");
108130

109-
Commit ret = null;
131+
ObjectId id;
132+
List<GitOid> ids = new List<GitOid>(8);
110133
int count = 0;
111134

112135
foreach (var commit in commits)
@@ -115,28 +138,28 @@ public Commit FindCommonAncestor(IEnumerable<Commit> commits)
115138
{
116139
throw new ArgumentException("Enumerable contains null at position: " + count.ToString(CultureInfo.InvariantCulture), "commits");
117140
}
118-
141+
ids.Add(commit.Id.Oid);
119142
count++;
120-
121-
if (count == 1)
122-
{
123-
ret = commit;
124-
continue;
125-
}
126-
127-
ret = FindCommonAncestor(ret, commit);
128-
if (ret == null)
129-
{
130-
break;
131-
}
132143
}
133144

134145
if (count < 2)
135146
{
136147
throw new ArgumentException("The enumerable must contains at least two commits.", "commits");
137148
}
138149

139-
return ret;
150+
switch (strategy)
151+
{
152+
case MergeBaseFindingStrategy.Standard:
153+
id = Proxy.git_merge_base_many(repo.Handle, ids.ToArray());
154+
break;
155+
case MergeBaseFindingStrategy.Octopus:
156+
id = Proxy.git_merge_base_octopus(repo.Handle, ids.ToArray());
157+
break;
158+
default:
159+
throw new ArgumentException("", "strategy");
160+
}
161+
162+
return id == null ? null : repo.Lookup<Commit>(id);
140163
}
141164

142165
private class CommitEnumerator : IEnumerator<Commit>
@@ -241,5 +264,24 @@ private void FirstParentOnly(bool firstParent)
241264
}
242265
}
243266
}
267+
268+
}
269+
270+
/// <summary>
271+
/// Determines the finding strategy of merge base.
272+
/// </summary>
273+
public enum MergeBaseFindingStrategy
274+
{
275+
/// <summary>
276+
/// Compute the best common ancestor between some commits to use in a three-way merge.
277+
/// <para>
278+
/// When more than two commits are provided, the computation is performed between the first commit and a hypothetical merge commit across all the remaining commits.
279+
/// </para>
280+
/// </summary>
281+
Standard,
282+
/// <summary>
283+
/// Compute the best common ancestor of all supplied commits, in preparation for an n-way merge.
284+
/// </summary>
285+
Octopus,
244286
}
245287
}

‎LibGit2Sharp/Core/NativeMethods.cs

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -572,11 +572,18 @@ internal static extern int git_index_remove_bypath(
572572
internal static extern int git_index_write_tree(out GitOid treeOid, IndexSafeHandle index);
573573

574574
[DllImport(libgit2)]
575-
internal static extern int git_merge_base(
575+
internal static extern int git_merge_base_many(
576576
out GitOid mergeBase,
577577
RepositorySafeHandle repo,
578-
GitObjectSafeHandle one,
579-
GitObjectSafeHandle two);
578+
int length,
579+
[In] GitOid[] input_array);
580+
581+
[DllImport(libgit2)]
582+
internal static extern int git_merge_base_octopus(
583+
out GitOid mergeBase,
584+
RepositorySafeHandle repo,
585+
int length,
586+
[In] GitOid[] input_array);
580587

581588
[DllImport(libgit2)]
582589
internal static extern int git_merge_head_from_ref(

‎LibGit2Sharp/Core/Proxy.cs

Lines changed: 20 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -928,14 +928,30 @@ public static ObjectId git_tree_create_fromindex(Index index)
928928

929929
#region git_merge_
930930

931-
public static ObjectId git_merge_base(RepositorySafeHandle repo, Commit first, Commit second)
931+
public static ObjectId git_merge_base_many(RepositorySafeHandle repo, GitOid[] commitIds)
932932
{
933933
using (ThreadAffinity())
934-
using (var osw1 = new ObjectSafeWrapper(first.Id, repo))
935-
using (var osw2 = new ObjectSafeWrapper(second.Id, repo))
936934
{
937935
GitOid ret;
938-
int res = NativeMethods.git_merge_base(out ret, repo, osw1.ObjectPtr, osw2.ObjectPtr);
936+
int res = NativeMethods.git_merge_base_many(out ret, repo, commitIds.Length, commitIds);
937+
938+
if (res == (int)GitErrorCode.NotFound)
939+
{
940+
return null;
941+
}
942+
943+
Ensure.ZeroResult(res);
944+
945+
return ret;
946+
}
947+
}
948+
949+
public static ObjectId git_merge_base_octopus(RepositorySafeHandle repo, GitOid[] commitIds)
950+
{
951+
using (ThreadAffinity())
952+
{
953+
GitOid ret;
954+
int res = NativeMethods.git_merge_base_octopus(out ret, repo, commitIds.Length, commitIds);
939955

940956
if (res == (int)GitErrorCode.NotFound)
941957
{

‎LibGit2Sharp/HistoryDivergence.cs

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ protected HistoryDivergence()
1919

2020
internal HistoryDivergence(Repository repo, Commit one, Commit another)
2121
{
22-
commonAncestor = new Lazy<Commit>(() => repo.Commits.FindCommonAncestor(one, another));
22+
commonAncestor = new Lazy<Commit>(() => repo.Commits.FindMergeBase(one, another));
2323
Tuple<int?, int?> div = Proxy.git_graph_ahead_behind(repo.Handle, another, one);
2424

2525
One = one;

0 commit comments

Comments
 (0)