Use native git variants by default with go-git variants as build tag (#13673)

* Move last commit cache back into modules/git

Signed-off-by: Andrew Thornton <art27@cantab.net>

* Remove go-git from the interface for last commit cache

Signed-off-by: Andrew Thornton <art27@cantab.net>

* move cacheref to last_commit_cache

Signed-off-by: Andrew Thornton <art27@cantab.net>

* Remove go-git from routers/private/hook

Signed-off-by: Andrew Thornton <art27@cantab.net>

* Move FindLFSFiles to pipeline

Signed-off-by: Andrew Thornton <art27@cantab.net>

* Make no-go-git variants

Signed-off-by: Andrew Thornton <art27@cantab.net>

* Submodule RefID

Signed-off-by: Andrew Thornton <art27@cantab.net>

* fix issue with GetCommitsInfo

Signed-off-by: Andrew Thornton <art27@cantab.net>

* fix GetLastCommitForPaths

Signed-off-by: Andrew Thornton <art27@cantab.net>

* Improve efficiency

Signed-off-by: Andrew Thornton <art27@cantab.net>

* More efficiency

Signed-off-by: Andrew Thornton <art27@cantab.net>

* even faster

Signed-off-by: Andrew Thornton <art27@cantab.net>

* Reduce duplication

* As per @lunny

Signed-off-by: Andrew Thornton <art27@cantab.net>

* attempt to fix drone

Signed-off-by: Andrew Thornton <art27@cantab.net>

* fix test-tags

Signed-off-by: Andrew Thornton <art27@cantab.net>

* default to use no-go-git variants and add gogit build tag

Signed-off-by: Andrew Thornton <art27@cantab.net>

* placate lint

Signed-off-by: Andrew Thornton <art27@cantab.net>

* as per @6543

Signed-off-by: Andrew Thornton <art27@cantab.net>

Co-authored-by: 6543 <6543@obermui.de>
Co-authored-by: techknowlogick <techknowlogick@gitea.io>

1 files changed, 291 insertions, 0 deletions

diff --git a/modules/git/commit_info_gogit.go b/modules/git/commit_info_gogit.go
new file mode 100644
index 0000000000..6d95e22d0c
--- /dev/null
+++ b/modules/git/commit_info_gogit.go
@@ -0,0 +1,291 @@
+// Copyright 2017 The Gitea Authors. All rights reserved.
+// Use of this source code is governed by a MIT-style
+// license that can be found in the LICENSE file.
+
+// +build gogit
+
+package git
+
+import (
+	"path"
+
+	"github.com/emirpasic/gods/trees/binaryheap"
+	"github.com/go-git/go-git/v5/plumbing"
+	"github.com/go-git/go-git/v5/plumbing/object"
+	cgobject "github.com/go-git/go-git/v5/plumbing/object/commitgraph"
+)
+
+// GetCommitsInfo gets information of all commits that are corresponding to these entries
+func (tes Entries) GetCommitsInfo(commit *Commit, treePath string, cache *LastCommitCache) ([]CommitInfo, *Commit, error) {
+	entryPaths := make([]string, len(tes)+1)
+	// Get the commit for the treePath itself
+	entryPaths[0] = ""
+	for i, entry := range tes {
+		entryPaths[i+1] = entry.Name()
+	}
+
+	commitNodeIndex, commitGraphFile := commit.repo.CommitNodeIndex()
+	if commitGraphFile != nil {
+		defer commitGraphFile.Close()
+	}
+
+	c, err := commitNodeIndex.Get(commit.ID)
+	if err != nil {
+		return nil, nil, err
+	}
+
+	var revs map[string]*object.Commit
+	if cache != nil {
+		var unHitPaths []string
+		revs, unHitPaths, err = getLastCommitForPathsByCache(commit.ID.String(), treePath, entryPaths, cache)
+		if err != nil {
+			return nil, nil, err
+		}
+		if len(unHitPaths) > 0 {
+			revs2, err := GetLastCommitForPaths(c, treePath, unHitPaths)
+			if err != nil {
+				return nil, nil, err
+			}
+
+			for k, v := range revs2 {
+				if err := cache.Put(commit.ID.String(), path.Join(treePath, k), v.ID().String()); err != nil {
+					return nil, nil, err
+				}
+				revs[k] = v
+			}
+		}
+	} else {
+		revs, err = GetLastCommitForPaths(c, treePath, entryPaths)
+	}
+	if err != nil {
+		return nil, nil, err
+	}
+
+	commit.repo.gogitStorage.Close()
+
+	commitsInfo := make([]CommitInfo, len(tes))
+	for i, entry := range tes {
+		commitsInfo[i] = CommitInfo{
+			Entry: entry,
+		}
+		if rev, ok := revs[entry.Name()]; ok {
+			entryCommit := convertCommit(rev)
+			commitsInfo[i].Commit = entryCommit
+			if entry.IsSubModule() {
+				subModuleURL := ""
+				var fullPath string
+				if len(treePath) > 0 {
+					fullPath = treePath + "/" + entry.Name()
+				} else {
+					fullPath = entry.Name()
+				}
+				if subModule, err := commit.GetSubModule(fullPath); err != nil {
+					return nil, nil, err
+				} else if subModule != nil {
+					subModuleURL = subModule.URL
+				}
+				subModuleFile := NewSubModuleFile(entryCommit, subModuleURL, entry.ID.String())
+				commitsInfo[i].SubModuleFile = subModuleFile
+			}
+		}
+	}
+
+	// Retrieve the commit for the treePath itself (see above). We basically
+	// get it for free during the tree traversal and it's used for listing
+	// pages to display information about newest commit for a given path.
+	var treeCommit *Commit
+	if treePath == "" {
+		treeCommit = commit
+	} else if rev, ok := revs[""]; ok {
+		treeCommit = convertCommit(rev)
+		treeCommit.repo = commit.repo
+	}
+	return commitsInfo, treeCommit, nil
+}
+
+type commitAndPaths struct {
+	commit cgobject.CommitNode
+	// Paths that are still on the branch represented by commit
+	paths []string
+	// Set of hashes for the paths
+	hashes map[string]plumbing.Hash
+}
+
+func getCommitTree(c cgobject.CommitNode, treePath string) (*object.Tree, error) {
+	tree, err := c.Tree()
+	if err != nil {
+		return nil, err
+	}
+
+	// Optimize deep traversals by focusing only on the specific tree
+	if treePath != "" {
+		tree, err = tree.Tree(treePath)
+		if err != nil {
+			return nil, err
+		}
+	}
+
+	return tree, nil
+}
+
+func getFileHashes(c cgobject.CommitNode, treePath string, paths []string) (map[string]plumbing.Hash, error) {
+	tree, err := getCommitTree(c, treePath)
+	if err == object.ErrDirectoryNotFound {
+		// The whole tree didn't exist, so return empty map
+		return make(map[string]plumbing.Hash), nil
+	}
+	if err != nil {
+		return nil, err
+	}
+
+	hashes := make(map[string]plumbing.Hash)
+	for _, path := range paths {
+		if path != "" {
+			entry, err := tree.FindEntry(path)
+			if err == nil {
+				hashes[path] = entry.Hash
+			}
+		} else {
+			hashes[path] = tree.Hash
+		}
+	}
+
+	return hashes, nil
+}
+
+func getLastCommitForPathsByCache(commitID, treePath string, paths []string, cache *LastCommitCache) (map[string]*object.Commit, []string, error) {
+	var unHitEntryPaths []string
+	var results = make(map[string]*object.Commit)
+	for _, p := range paths {
+		lastCommit, err := cache.Get(commitID, path.Join(treePath, p))
+		if err != nil {
+			return nil, nil, err
+		}
+		if lastCommit != nil {
+			results[p] = lastCommit.(*object.Commit)
+			continue
+		}
+
+		unHitEntryPaths = append(unHitEntryPaths, p)
+	}
+
+	return results, unHitEntryPaths, nil
+}
+
+// GetLastCommitForPaths returns last commit information
+func GetLastCommitForPaths(c cgobject.CommitNode, treePath string, paths []string) (map[string]*object.Commit, error) {
+	// We do a tree traversal with nodes sorted by commit time
+	heap := binaryheap.NewWith(func(a, b interface{}) int {
+		if a.(*commitAndPaths).commit.CommitTime().Before(b.(*commitAndPaths).commit.CommitTime()) {
+			return 1
+		}
+		return -1
+	})
+
+	resultNodes := make(map[string]cgobject.CommitNode)
+	initialHashes, err := getFileHashes(c, treePath, paths)
+	if err != nil {
+		return nil, err
+	}
+
+	// Start search from the root commit and with full set of paths
+	heap.Push(&commitAndPaths{c, paths, initialHashes})
+
+	for {
+		cIn, ok := heap.Pop()
+		if !ok {
+			break
+		}
+		current := cIn.(*commitAndPaths)
+
+		// Load the parent commits for the one we are currently examining
+		numParents := current.commit.NumParents()
+		var parents []cgobject.CommitNode
+		for i := 0; i < numParents; i++ {
+			parent, err := current.commit.ParentNode(i)
+			if err != nil {
+				break
+			}
+			parents = append(parents, parent)
+		}
+
+		// Examine the current commit and set of interesting paths
+		pathUnchanged := make([]bool, len(current.paths))
+		parentHashes := make([]map[string]plumbing.Hash, len(parents))
+		for j, parent := range parents {
+			parentHashes[j], err = getFileHashes(parent, treePath, current.paths)
+			if err != nil {
+				break
+			}
+
+			for i, path := range current.paths {
+				if parentHashes[j][path] == current.hashes[path] {
+					pathUnchanged[i] = true
+				}
+			}
+		}
+
+		var remainingPaths []string
+		for i, path := range current.paths {
+			// The results could already contain some newer change for the same path,
+			// so don't override that and bail out on the file early.
+			if resultNodes[path] == nil {
+				if pathUnchanged[i] {
+					// The path existed with the same hash in at least one parent so it could
+					// not have been changed in this commit directly.
+					remainingPaths = append(remainingPaths, path)
+				} else {
+					// There are few possible cases how can we get here:
+					// - The path didn't exist in any parent, so it must have been created by
+					//   this commit.
+					// - The path did exist in the parent commit, but the hash of the file has
+					//   changed.
+					// - We are looking at a merge commit and the hash of the file doesn't
+					//   match any of the hashes being merged. This is more common for directories,
+					//   but it can also happen if a file is changed through conflict resolution.
+					resultNodes[path] = current.commit
+				}
+			}
+		}
+
+		if len(remainingPaths) > 0 {
+			// Add the parent nodes along with remaining paths to the heap for further
+			// processing.
+			for j, parent := range parents {
+				// Combine remainingPath with paths available on the parent branch
+				// and make union of them
+				remainingPathsForParent := make([]string, 0, len(remainingPaths))
+				newRemainingPaths := make([]string, 0, len(remainingPaths))
+				for _, path := range remainingPaths {
+					if parentHashes[j][path] == current.hashes[path] {
+						remainingPathsForParent = append(remainingPathsForParent, path)
+					} else {
+						newRemainingPaths = append(newRemainingPaths, path)
+					}
+				}
+
+				if remainingPathsForParent != nil {
+					heap.Push(&commitAndPaths{parent, remainingPathsForParent, parentHashes[j]})
+				}
+
+				if len(newRemainingPaths) == 0 {
+					break
+				} else {
+					remainingPaths = newRemainingPaths
+				}
+			}
+		}
+	}
+
+	// Post-processing
+	result := make(map[string]*object.Commit)
+	for path, commitNode := range resultNodes {
+		var err error
+		result[path], err = commitNode.Commit()
+		if err != nil {
+			return nil, err
+		}
+	}
+
+	return result, nil
+}