merge_base_many produces different outcomes depending on argument order.

I'm not sure if this is a bug report per-se, given that there have been test cases in libgit2 for the last 12 years which confirm this behavior.

I've been making use of merge_base_many in GitButler to find the common merge base between N commits. However, while writing tests cases I found some unexpected behavior, and the source seems to be the fact that merge_base_many returns different results depending on the order of the arguments! My understanding was that it should always return the commit that is a shared base among all of them.

Here is my rust code in case I'm making some daft mistake:

// commit_tree writes takes a list of files and writes them into a
// tree, and then commits that tree with the provided commit as
// the parent.
// commit_tree gives each commit a unique name.
let base_commit = test_repository.commit_tree(None, &[]);
let m = test_repository.commit_tree(Some(&base_commit), &[]);
let n = test_repository.commit_tree(Some(&m), &[]);

let a = test_repository.commit_tree(Some(&base_commit), &[]);
let b = test_repository.commit_tree(Some(&a), &[]);

// imagine someone on the remote rebased local_a
let x = test_repository.commit_tree(Some(&n), &[]);
let y = test_repository.commit_tree(Some(&x), &[]);
let z = test_repository.commit_tree(Some(&y), &[]);

dbg!(test_repository
    .repository
    .merge_base_many(&[n.id(), b.id(), z.id()])
    .unwrap()); // Returns n (unexpected)

dbg!(test_repository
    .repository
    .merge_base_many(&[b.id(), z.id(), n.id()])
    .unwrap()); // Returns base_commit (expected)

dbg!(test_repository
    .repository
    .merge_base_many(&[z.id(), n.id(), b.id()])
    .unwrap()); // Returns n (unexpected)

But, I've also laid out the scenario a little nicer:

Setup:
(z)
 |
 y
 |
 x
 |
(n) (b)
 |   |
 m   a
 \   /
  base_commit

merge_base_many([n, b, z]) = n
merge_base_many([b, z, n]) = base_commit
merge_base_many([z, n, b]) = n

There however seems to be test cases that indicate that there might be intended behavior going on here? https://github.com/libgit2/libgit2/blob/main/tests/libgit2/revwalk/mergebase.c#L243-L245 (PR: https://github.com/libgit2/libgit2/pull/753)

If this is intended, it would be great if it could be documented, because this was rather unexpected to me.

I'll talk to Scott about this tomorrow as well in case my understanding is flawed, and come back to update here and the docs if it turns out I'm expecting the wrong behavior, so others don't get confused buy the behavior.

Version of libgit2 (release number or SHA1)

git2-rs 0.19 / 1.8.1 (but tests in the repo HEAD indicate the "issue" is still in place, and has been around for a while)

Thanks for the great work on libgit2 btw!!

libgit2 / libgit2

merge_base_many produces different outcomes depending on argument order. #6899

Version of libgit2 (release number or SHA1)