Use commit graph files for listing pages (#7314)

* Experimental support for git commit graph files and bloom filter index

Signed-off-by: Filip Navara <filip.navara@gmail.com>

* Force vendor of commitgraph

Signed-off-by: Filip Navara <filip.navara@gmail.com>

* Remove bloom filter experiment and debug prints

* Remove old code for building commit graphs

* Remove unused function

* Remove mmap usage

* gofmt

* sort vendor/modules.txt

* Add copyright header and log commit-graph error

3 files changed, 73 insertions, 12 deletions

diff --git a/modules/git/commit_info.go b/modules/git/commit_info.go
index 9270878c7f..8417226f8b 100644
--- a/modules/git/commit_info.go
+++ b/modules/git/commit_info.go
@@ -8,6 +8,7 @@ import (
 	"github.com/emirpasic/gods/trees/binaryheap"
 	"gopkg.in/src-d/go-git.v4/plumbing"
 	"gopkg.in/src-d/go-git.v4/plumbing/object"
+	cgobject "gopkg.in/src-d/go-git.v4/plumbing/object/commitgraph"
 )
 
 // GetCommitsInfo gets information of all commits that are corresponding to these entries
@@ -19,7 +20,12 @@ func (tes Entries) GetCommitsInfo(commit *Commit, treePath string, cache LastCom
 		entryPaths[i+1] = entry.Name()
 	}
 
-	c, err := commit.repo.gogitRepo.CommitObject(plumbing.Hash(commit.ID))
+	commitNodeIndex, commitGraphFile := commit.repo.CommitNodeIndex()
+	if commitGraphFile != nil {
+		defer commitGraphFile.Close()
+	}
+
+	c, err := commitNodeIndex.Get(plumbing.Hash(commit.ID))
 	if err != nil {
 		return nil, nil, err
 	}
@@ -69,14 +75,14 @@ func (tes Entries) GetCommitsInfo(commit *Commit, treePath string, cache LastCom
 }
 
 type commitAndPaths struct {
-	commit *object.Commit
+	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 *object.Commit, treePath string) (*object.Tree, error) {
+func getCommitTree(c cgobject.CommitNode, treePath string) (*object.Tree, error) {
 	tree, err := c.Tree()
 	if err != nil {
 		return nil, err
@@ -93,7 +99,7 @@ func getCommitTree(c *object.Commit, treePath string) (*object.Tree, error) {
 	return tree, nil
 }
 
-func getFileHashes(c *object.Commit, treePath string, paths []string) (map[string]plumbing.Hash, error) {
+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
@@ -118,16 +124,16 @@ func getFileHashes(c *object.Commit, treePath string, paths []string) (map[strin
 	return hashes, nil
 }
 
-func getLastCommitForPaths(c *object.Commit, treePath string, paths []string) (map[string]*object.Commit, error) {
+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.Committer.When.Before(b.(*commitAndPaths).commit.Committer.When) {
+		if a.(*commitAndPaths).commit.CommitTime().Before(b.(*commitAndPaths).commit.CommitTime()) {
 			return 1
 		}
 		return -1
 	})
 
-	result := make(map[string]*object.Commit)
+	resultNodes := make(map[string]cgobject.CommitNode)
 	initialHashes, err := getFileHashes(c, treePath, paths)
 	if err != nil {
 		return nil, err
@@ -145,9 +151,9 @@ func getLastCommitForPaths(c *object.Commit, treePath string, paths []string) (m
 
 		// Load the parent commits for the one we are currently examining
 		numParents := current.commit.NumParents()
-		var parents []*object.Commit
+		var parents []cgobject.CommitNode
 		for i := 0; i < numParents; i++ {
-			parent, err := current.commit.Parent(i)
+			parent, err := current.commit.ParentNode(i)
 			if err != nil {
 				break
 			}
@@ -174,7 +180,7 @@ func getLastCommitForPaths(c *object.Commit, treePath string, paths []string) (m
 		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 result[path] == nil {
+			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.
@@ -188,7 +194,7 @@ func getLastCommitForPaths(c *object.Commit, treePath string, paths []string) (m
 					// - 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.
-					result[path] = current.commit
+					resultNodes[path] = current.commit
 				}
 			}
 		}
@@ -222,5 +228,15 @@ func getLastCommitForPaths(c *object.Commit, treePath string, paths []string) (m
 		}
 	}
 
+	// 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
 }
diff --git a/modules/git/notes.go b/modules/git/notes.go
index 7aa5d89a79..a62c558787 100644
--- a/modules/git/notes.go
+++ b/modules/git/notes.go
@@ -50,7 +50,17 @@ func GetNote(repo *Repository, commitID string, note *Note) error {
 		return err
 	}
 
-	lastCommits, err := getLastCommitForPaths(commit, "", []string{commitID})
+	commitNodeIndex, commitGraphFile := repo.CommitNodeIndex()
+	if commitGraphFile != nil {
+		defer commitGraphFile.Close()
+	}
+
+	commitNode, err := commitNodeIndex.Get(commit.Hash)
+	if err != nil {
+		return nil
+	}
+
+	lastCommits, err := getLastCommitForPaths(commitNode, "", []string{commitID})
 	if err != nil {
 		return err
 	}
diff --git a/modules/git/repo_commitgraph.go b/modules/git/repo_commitgraph.go
new file mode 100644
index 0000000000..52263852dc
--- /dev/null
+++ b/modules/git/repo_commitgraph.go
@@ -0,0 +1,35 @@
+// Copyright 2019 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.
+
+package git
+
+import (
+	"os"
+	"path"
+
+	gitealog "code.gitea.io/gitea/modules/log"
+	"gopkg.in/src-d/go-git.v4/plumbing/format/commitgraph"
+	cgobject "gopkg.in/src-d/go-git.v4/plumbing/object/commitgraph"
+)
+
+// CommitNodeIndex returns the index for walking commit graph
+func (r *Repository) CommitNodeIndex() (cgobject.CommitNodeIndex, *os.File) {
+	indexPath := path.Join(r.Path, "objects", "info", "commit-graph")
+
+	file, err := os.Open(indexPath)
+	if err == nil {
+		var index commitgraph.Index
+		index, err = commitgraph.OpenFileIndex(file)
+		if err == nil {
+			return cgobject.NewGraphCommitNodeIndex(index, r.gogitRepo.Storer), file
+		}
+	}
+
+	if !os.IsNotExist(err) {
+		gitealog.Warn("Unable to read commit-graph for %s: %v", r.Path, err)
+	}
+
+	return cgobject.NewObjectCommitNodeIndex(r.gogitRepo.Storer), nil
+}