If the trunk branch points to a commit that is an ancestor of a branch to be adopted, this will be relatively fast as ancestorsIndex will stop at the commit that the trunk branch points to. However, if it's diverged, it can go all the way up to the beginning of the history.
This has been a problem in git, and recently, cgit addressed this issue by having a generation number (https://git-scm.com/docs/commit-graph). This allows an efficient topo-order traversal, which we need for efficient merge base calculation.
In https://github.com/aviator-co/av/blob/d74f1e1103e0e7e2eef3f8f3c7a3a08c38e81aa2/internal/treedetector/detector.go#L129-L153, we try to get the common ancestor with the trunk. This uses go-git's MergeBase implementation.
https://github.com/go-git/go-git/blob/ec133065ea1201a4488bbc793ccd9337b6c06877/plumbing/object/merge_base.go#L17
If the trunk branch points to a commit that is an ancestor of a branch to be adopted, this will be relatively fast as
ancestorsIndexwill stop at the commit that the trunk branch points to. However, if it's diverged, it can go all the way up to the beginning of the history.This has been a problem in git, and recently, cgit addressed this issue by having a generation number (https://git-scm.com/docs/commit-graph). This allows an efficient topo-order traversal, which we need for efficient merge base calculation.
go-git has an experimental commit-graph implementation (https://github.com/go-git/go-git/tree/ec133065ea1201a4488bbc793ccd9337b6c06877/plumbing/object/commitgraph), but it's still experimental. Until it becomes prod-ready, we can use c-git's merge-base https://git-scm.com/docs/git-merge-base for faster merge base calculation.