From 944861a8dfe85938e84007f399e8ed94acbf5d68 Mon Sep 17 00:00:00 2001 From: Filip Navara Date: Tue, 7 May 2019 11:33:25 +0200 Subject: Add example for commit-graph traversal Signed-off-by: Filip Navara --- _examples/ls/main.go | 268 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 268 insertions(+) create mode 100644 _examples/ls/main.go (limited to '_examples/ls') diff --git a/_examples/ls/main.go b/_examples/ls/main.go new file mode 100644 index 0000000..bbd40d5 --- /dev/null +++ b/_examples/ls/main.go @@ -0,0 +1,268 @@ +package main + +import ( + "fmt" + "io" + "os" + "path" + "strings" + + "github.com/emirpasic/gods/trees/binaryheap" + "gopkg.in/src-d/go-git.v4" + . "gopkg.in/src-d/go-git.v4/_examples" + "gopkg.in/src-d/go-git.v4/plumbing" + "gopkg.in/src-d/go-git.v4/plumbing/cache" + commitgraph_fmt "gopkg.in/src-d/go-git.v4/plumbing/format/commitgraph" + "gopkg.in/src-d/go-git.v4/plumbing/object" + "gopkg.in/src-d/go-git.v4/plumbing/object/commitgraph" + "gopkg.in/src-d/go-git.v4/storage/filesystem" + + "gopkg.in/src-d/go-billy.v4" + "gopkg.in/src-d/go-billy.v4/osfs" +) + +// Example how to resolve a revision into its commit counterpart +func main() { + CheckArgs("", "", "") + + path := os.Args[1] + revision := os.Args[2] + treePath := os.Args[3] + + // We instantiate a new repository targeting the given path (the .git folder) + fs := osfs.New(path) + s := filesystem.NewStorageWithOptions(fs, cache.NewObjectLRUDefault(), filesystem.Options{KeepDescriptors: true}) + r, err := git.Open(s, fs) + CheckIfError(err) + + // Resolve revision into a sha1 commit, only some revisions are resolved + // look at the doc to get more details + Info("git rev-parse %s", revision) + + h, err := r.ResolveRevision(plumbing.Revision(revision)) + CheckIfError(err) + + commit, err := r.CommitObject(*h) + CheckIfError(err) + + tree, err := commit.Tree() + CheckIfError(err) + if treePath != "" { + tree, err = tree.Tree(treePath) + CheckIfError(err) + } + + var paths []string + for _, entry := range tree.Entries { + paths = append(paths, entry.Name) + } + + commitNodeIndex, file := getCommitNodeIndex(r, fs) + if file != nil { + defer file.Close() + } + + commitNode, err := commitNodeIndex.Get(*h) + CheckIfError(err) + + revs, err := getLastCommitForPaths(commitNode, treePath, paths) + CheckIfError(err) + for path, rev := range revs { + // Print one line per file (name hash message) + hash := rev.Hash.String() + line := strings.Split(rev.Message, "\n") + fmt.Println(path, hash[:7], line[0]) + } + + s.Close() +} + +func getCommitNodeIndex(r *git.Repository, fs billy.Filesystem) (commitgraph.CommitNodeIndex, io.ReadCloser) { + file, err := fs.Open(path.Join("objects", "info", "commit-graph")) + if err == nil { + index, err := commitgraph_fmt.OpenFileIndex(file) + if err == nil { + return commitgraph.NewGraphCommitNodeIndex(index, r.Storer), file + } + file.Close() + } + + return commitgraph.NewObjectCommitNodeIndex(r.Storer), nil +} + +type commitAndPaths struct { + commit commitgraph.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 commitgraph.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 getFullPath(treePath, path string) string { + if treePath != "" { + if path != "" { + return treePath + "/" + path + } + return treePath + } + return path +} + +func getFileHashes(c commitgraph.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 getLastCommitForPaths(c commitgraph.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]commitgraph.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 []commitgraph.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 +} -- cgit From 0073a49b9575c2e64676485ca5126641510c6db5 Mon Sep 17 00:00:00 2001 From: Filip Navara Date: Tue, 7 May 2019 12:26:55 +0200 Subject: Allow non-.git path for ls example Signed-off-by: Filip Navara --- _examples/ls/main.go | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to '_examples/ls') diff --git a/_examples/ls/main.go b/_examples/ls/main.go index bbd40d5..bb686f1 100644 --- a/_examples/ls/main.go +++ b/_examples/ls/main.go @@ -31,9 +31,15 @@ func main() { // We instantiate a new repository targeting the given path (the .git folder) fs := osfs.New(path) + if _, err := fs.Stat(git.GitDirName); err == nil { + fs, err = fs.Chroot(git.GitDirName) + CheckIfError(err) + } + s := filesystem.NewStorageWithOptions(fs, cache.NewObjectLRUDefault(), filesystem.Options{KeepDescriptors: true}) r, err := git.Open(s, fs) CheckIfError(err) + defer s.Close() // Resolve revision into a sha1 commit, only some revisions are resolved // look at the doc to get more details @@ -73,8 +79,6 @@ func main() { line := strings.Split(rev.Message, "\n") fmt.Println(path, hash[:7], line[0]) } - - s.Close() } func getCommitNodeIndex(r *git.Repository, fs billy.Filesystem) (commitgraph.CommitNodeIndex, io.ReadCloser) { -- cgit