why not return an error? If you ask for the common ancestor and it does not exist, maybe returning base makes other things fail later, without any hint of why.

An analyzer can be interested on reviewing changes between orphan branches. Couldn't it?

what's the behaviour of git diff base...head if they do not have a common ancestor?

I tried locally, and git diff base...head behaves as .. if there is no shared history between them?

For curiosity, I checked git/git source code, and it seems that ... behaves that way only if there is at least one "merge-base" between base and head; otherwise it seems to fallback as ... Anyhow I'm not used to git codebase.

I don't fully understand the algorithm here so this is only a comment for future improvements.

It seems to me that this is walking the commit tree almost fully several times. This may be ok for small repositories but it may have a penalty for bigger ones like kubernetes. Testing it with a PR in kubernetes would be be interesting.

Thanks @jfontan for your review!!!
Let's see if 👇 this helps you to understand the algorithm.

Yes, the history can potentially be walked as many times as candidates provided for Independents.
But every time a candidate is found as an ancestor of any other, it is removed from the candidates list, so it won't be considered anymore.
The order in which you request the candidates, affects how many times the history is traversed.
In the worst scenario, the history will be traversed as many times as orphan branches are included in the candidates to be analyzed.

given this history:

          o----o----B~2---B^---B
         /         /
--A~4---o---A~2---o---A

---o---C^---C

then:

• (A) Independents(B, B^); 1step; walks the history only once, because starting by B, it reaches in one step B^; once B^ is reached, it is removed from the candidates list, and since there only one candidate left (B), it is returned with no more steps.
• (B)Independents(B, B^, B~2); 2steps; walks only once (as in the previous example), but it requires two steps to reach B^ and then B~2
• (C)Independents(B, A~4); 8steps; walks the history only once (as in the previous example), but it requires many steps to reach A~4
• (D)Independents(B^, B); 1full + 1step; walks the history twice, because first iteration walking from B^ does not reach B after a full walk from B^; then in the second iteration walking from B it is the same case as (A), so it is returned A with only one extra step
• (E) Independents(B, A); 2full; walks the history twice; because during first walk from B it won't be reached A, and during the second walk from A, it won't be reached B
• (F) Independents(B, A, B^); 2full; walks the history twice; first time, it will be found B^ as an ancestor, so it will be removed from candidates list; then it will be the same case than E
• (G) Independents(B, B^, B~2, A, A~2, A~4, C, C^); 3full; because during the first history walk from B it will be removed B^, B~2, A~2, A~4 from the candidates list; then the second iteration will consider only B, A, C and C^, then, walking from A, it won't find any ancestor in the candidates list; the third iteration, starting from C will find (and remove) C^ from the list, so the result will be only A, B and C.

possible optimizations:

• sort the candidates by Committer.When desc before start processing them, so most examples of (D) (Independents(B^, B)) will be converted into (A) cases (Independents(B,B^)); it won't work when Committer.When does not reflect the topological order (in such cases, it will cause the problem tried to be solved, but I think it would be a "strange" case)
• store all traversed commits and exclude them in the next history walk. It will make that (E) Independents(B, A) will require only 1full+2steps instead of 2full because the first iteration (from B) will be used to shortcut the second one (from A) because since A~2, A shares B history.
• minor fix: replace s/commits/res from line 92 to exclude already excluded ancestors.

and thanks to your question, I spotted a bug:

• replace start from line 110 with find(from, res) + 1) (pseudocode), because otherwise the iteration starts from the same place as many times as an ancestor is found from the start position, what is clearly too much, and does not reflect the desired (and described) behavior.