merge_base.go

package object

import (
	"fmt"
	"sort"

	"github.com/realab/go-git-thread-safe/v5/plumbing"
	"github.com/realab/go-git-thread-safe/v5/plumbing/storer"
)

// errIsReachable is thrown when first commit is an ancestor of the second
var errIsReachable = fmt.Errorf("first is reachable from second")

// MergeBase mimics the behavior of `git merge-base actual other`, returning the
// best common ancestor between the actual and the passed one.
// The best common ancestors can not be reached from other common ancestors.
func (c *Commit) MergeBase(other *Commit) ([]*Commit, error) {
	// use sortedByCommitDateDesc strategy
	sorted := sortByCommitDateDesc(c, other)
	newer := sorted[0]
	older := sorted[1]

	newerHistory, err := ancestorsIndex(older, newer)
	if err == errIsReachable {
		return []*Commit{older}, nil
	}

	if err != nil {
		return nil, err
	}

	var res []*Commit
	inNewerHistory := isInIndexCommitFilter(newerHistory)
	resIter := NewFilterCommitIter(older, &inNewerHistory, &inNewerHistory)
	_ = resIter.ForEach(func(commit *Commit) error {
		res = append(res, commit)
		return nil
	})

	return Independents(res)
}

// IsAncestor returns true if the actual commit is ancestor of the passed one.
// It returns an error if the history is not transversable
// It mimics the behavior of `git merge --is-ancestor actual other`
func (c *Commit) IsAncestor(other *Commit) (bool, error) {
	found := false
	iter := NewCommitPreorderIter(other, nil, nil)
	err := iter.ForEach(func(comm *Commit) error {
		if comm.Hash != c.Hash {
			return nil
		}

		found = true
		return storer.ErrStop
	})

	return found, err
}

// ancestorsIndex returns a map with the ancestors of the starting commit if the
// excluded one is not one of them. It returns errIsReachable if the excluded commit
// is ancestor of the starting, or another error if the history is not traversable.
func ancestorsIndex(excluded, starting *Commit) (map[plumbing.Hash]struct{}, error) {
	if excluded.Hash.String() == starting.Hash.String() {
		return nil, errIsReachable
	}

	startingHistory := map[plumbing.Hash]struct{}{}
	startingIter := NewCommitIterBSF(starting, nil, nil)
	err := startingIter.ForEach(func(commit *Commit) error {
		if commit.Hash == excluded.Hash {
			return errIsReachable
		}

		startingHistory[commit.Hash] = struct{}{}
		return nil
	})

	if err != nil {
		return nil, err
	}

	return startingHistory, nil
}

// Independents returns a subset of the passed commits, that are not reachable the others
// It mimics the behavior of `git merge-base --independent commit...`.
func Independents(commits []*Commit) ([]*Commit, error) {
	// use sortedByCommitDateDesc strategy
	candidates := sortByCommitDateDesc(commits...)
	candidates = removeDuplicated(candidates)

	seen := map[plumbing.Hash]struct{}{}
	var isLimit CommitFilter = func(commit *Commit) bool {
		_, ok := seen[commit.Hash]
		return ok
	}

	if len(candidates) < 2 {
		return candidates, nil
	}

	pos := 0
	for {
		from := candidates[pos]
		others := remove(candidates, from)
		fromHistoryIter := NewFilterCommitIter(from, nil, &isLimit)
		err := fromHistoryIter.ForEach(func(fromAncestor *Commit) error {
			for _, other := range others {
				if fromAncestor.Hash == other.Hash {
					candidates = remove(candidates, other)
					others = remove(others, other)
				}
			}

			if len(candidates) == 1 {
				return storer.ErrStop
			}

			seen[fromAncestor.Hash] = struct{}{}
			return nil
		})

		if err != nil {
			return nil, err
		}

		nextPos := indexOf(candidates, from) + 1
		if nextPos >= len(candidates) {
			break
		}

		pos = nextPos
	}

	return candidates, nil
}

// sortByCommitDateDesc returns the passed commits, sorted by `committer.When desc`
//
// Following this strategy, it is tried to reduce the time needed when walking
// the history from one commit to reach the others. It is assumed that ancestors
// use to be committed before its descendant;
// That way `Independents(A^, A)` will be processed as being `Independents(A, A^)`;
// so starting by `A` it will be reached `A^` way sooner than walking from `A^`
// to the initial commit, and then from `A` to `A^`.
func sortByCommitDateDesc(commits ...*Commit) []*Commit {
	sorted := make([]*Commit, len(commits))
	copy(sorted, commits)
	sort.Slice(sorted, func(i, j int) bool {
		return sorted[i].Committer.When.After(sorted[j].Committer.When)
	})

	return sorted
}

// indexOf returns the first position where target was found in the passed commits
func indexOf(commits []*Commit, target *Commit) int {
	for i, commit := range commits {
		if target.Hash == commit.Hash {
			return i
		}
	}

	return -1
}

// remove returns the passed commits excluding the commit toDelete
func remove(commits []*Commit, toDelete *Commit) []*Commit {
	res := make([]*Commit, len(commits))
	j := 0
	for _, commit := range commits {
		if commit.Hash == toDelete.Hash {
			continue
		}

		res[j] = commit
		j++
	}

	return res[:j]
}

// removeDuplicated removes duplicated commits from the passed slice of commits
func removeDuplicated(commits []*Commit) []*Commit {
	seen := make(map[plumbing.Hash]struct{}, len(commits))
	res := make([]*Commit, len(commits))
	j := 0
	for _, commit := range commits {
		if _, ok := seen[commit.Hash]; ok {
			continue
		}

		seen[commit.Hash] = struct{}{}
		res[j] = commit
		j++
	}

	return res[:j]
}

// isInIndexCommitFilter returns a commitFilter that returns true
// if the commit is in the passed index.
func isInIndexCommitFilter(index map[plumbing.Hash]struct{}) CommitFilter {
	return func(c *Commit) bool {
		_, ok := index[c.Hash]
		return ok
	}
}