diff options
Diffstat (limited to 'plumbing/object')
| -rw-r--r-- | plumbing/object/commitnode.go | 97 | ||||
| -rw-r--r-- | plumbing/object/commitnode_graph.go | 130 | ||||
| -rw-r--r-- | plumbing/object/commitnode_object.go | 89 | ||||
| -rw-r--r-- | plumbing/object/commitnode_test.go | 144 | ||||
| -rw-r--r-- | plumbing/object/commitnode_walker_ctime.go | 105 |
5 files changed, 565 insertions, 0 deletions
diff --git a/plumbing/object/commitnode.go b/plumbing/object/commitnode.go new file mode 100644 index 0000000..ce25487 --- /dev/null +++ b/plumbing/object/commitnode.go @@ -0,0 +1,97 @@ +package object
+
+import (
+ "io"
+ "time"
+
+ "gopkg.in/src-d/go-git.v4/plumbing"
+ "gopkg.in/src-d/go-git.v4/plumbing/storer"
+)
+
+// CommitNode is generic interface encapsulating a lightweight commit object retrieved
+// from CommitNodeIndex
+type CommitNode interface {
+ // ID returns the Commit object id referenced by the commit graph node.
+ ID() plumbing.Hash
+ // Tree returns the Tree referenced by the commit graph node.
+ Tree() (*Tree, error)
+ // CommitTime returns the Commiter.When time of the Commit referenced by the commit graph node.
+ CommitTime() time.Time
+ // NumParents returns the number of parents in a commit.
+ NumParents() int
+ // ParentNodes return a CommitNodeIter for parents of specified node.
+ ParentNodes() CommitNodeIter
+ // ParentNode returns the ith parent of a commit.
+ ParentNode(i int) (CommitNode, error)
+ // ParentHashes returns hashes of the parent commits for a specified node
+ ParentHashes() []plumbing.Hash
+ // Generation returns the generation of the commit for reachability analysis.
+ // Objects with newer generation are not reachable from objects of older generation.
+ Generation() uint64
+ // Commit returns the full commit object from the node
+ Commit() (*Commit, error)
+}
+
+// CommitNodeIndex is generic interface encapsulating an index of CommitNode objects
+type CommitNodeIndex interface {
+ // Get returns a commit node from a commit hash
+ Get(hash plumbing.Hash) (CommitNode, error)
+}
+
+// CommitNodeIter is a generic closable interface for iterating over commit nodes.
+type CommitNodeIter interface {
+ Next() (CommitNode, error)
+ ForEach(func(CommitNode) error) error
+ Close()
+}
+
+// parentCommitNodeIter provides an iterator for parent commits from associated CommitNodeIndex.
+type parentCommitNodeIter struct {
+ node CommitNode
+ i int
+}
+
+func newParentgraphCommitNodeIter(node CommitNode) CommitNodeIter {
+ return &parentCommitNodeIter{node, 0}
+}
+
+// Next moves the iterator to the next commit and returns a pointer to it. If
+// there are no more commits, it returns io.EOF.
+func (iter *parentCommitNodeIter) Next() (CommitNode, error) {
+ obj, err := iter.node.ParentNode(iter.i)
+ if err == ErrParentNotFound {
+ return nil, io.EOF
+ }
+ if err == nil {
+ iter.i++
+ }
+
+ return obj, err
+}
+
+// ForEach call the cb function for each commit contained on this iter until
+// an error appends or the end of the iter is reached. If ErrStop is sent
+// the iteration is stopped but no error is returned. The iterator is closed.
+func (iter *parentCommitNodeIter) ForEach(cb func(CommitNode) error) error {
+ for {
+ obj, err := iter.Next()
+ if err != nil {
+ if err == io.EOF {
+ return nil
+ }
+
+ return err
+ }
+
+ if err := cb(obj); err != nil {
+ if err == storer.ErrStop {
+ return nil
+ }
+
+ return err
+ }
+ }
+}
+
+func (iter *parentCommitNodeIter) Close() {
+}
diff --git a/plumbing/object/commitnode_graph.go b/plumbing/object/commitnode_graph.go new file mode 100644 index 0000000..ac790ab --- /dev/null +++ b/plumbing/object/commitnode_graph.go @@ -0,0 +1,130 @@ +package object
+
+import (
+ "fmt"
+ "time"
+
+ "gopkg.in/src-d/go-git.v4/plumbing"
+ "gopkg.in/src-d/go-git.v4/plumbing/format/commitgraph"
+ "gopkg.in/src-d/go-git.v4/plumbing/storer"
+)
+
+// graphCommitNode is a reduced representation of Commit as presented in the commit
+// graph file (commitgraph.Node). It is merely useful as an optimization for walking
+// the commit graphs.
+//
+// graphCommitNode implements the CommitNode interface.
+type graphCommitNode struct {
+ // Hash for the Commit object
+ hash plumbing.Hash
+ // Index of the node in the commit graph file
+ index int
+
+ commitData *commitgraph.CommitData
+ gci *graphCommitNodeIndex
+}
+
+// graphCommitNodeIndex is an index that can load CommitNode objects from both the commit
+// graph files and the object store.
+//
+// graphCommitNodeIndex implements the CommitNodeIndex interface
+type graphCommitNodeIndex struct {
+ commitGraph commitgraph.Index
+ s storer.EncodedObjectStorer
+}
+
+// NewGraphCommitNodeIndex returns CommitNodeIndex implementation that uses commit-graph
+// files as backing storage and falls back to object storage when necessary
+func NewGraphCommitNodeIndex(commitGraph commitgraph.Index, s storer.EncodedObjectStorer) CommitNodeIndex {
+ return &graphCommitNodeIndex{commitGraph, s}
+}
+
+func (gci *graphCommitNodeIndex) Get(hash plumbing.Hash) (CommitNode, error) {
+ // Check the commit graph first
+ parentIndex, err := gci.commitGraph.GetIndexByHash(hash)
+ if err == nil {
+ parent, err := gci.commitGraph.GetCommitDataByIndex(parentIndex)
+ if err != nil {
+ return nil, err
+ }
+
+ return &graphCommitNode{
+ hash: hash,
+ index: parentIndex,
+ commitData: parent,
+ gci: gci,
+ }, nil
+ }
+
+ // Fallback to loading full commit object
+ commit, err := GetCommit(gci.s, hash)
+ if err != nil {
+ return nil, err
+ }
+
+ return &objectCommitNode{
+ nodeIndex: gci,
+ commit: commit,
+ }, nil
+}
+
+func (c *graphCommitNode) ID() plumbing.Hash {
+ return c.hash
+}
+
+func (c *graphCommitNode) Tree() (*Tree, error) {
+ return GetTree(c.gci.s, c.commitData.TreeHash)
+}
+
+func (c *graphCommitNode) CommitTime() time.Time {
+ return c.commitData.When
+}
+
+func (c *graphCommitNode) NumParents() int {
+ return len(c.commitData.ParentIndexes)
+}
+
+func (c *graphCommitNode) ParentNodes() CommitNodeIter {
+ return newParentgraphCommitNodeIter(c)
+}
+
+func (c *graphCommitNode) ParentNode(i int) (CommitNode, error) {
+ if i < 0 || i >= len(c.commitData.ParentIndexes) {
+ return nil, ErrParentNotFound
+ }
+
+ parent, err := c.gci.commitGraph.GetCommitDataByIndex(c.commitData.ParentIndexes[i])
+ if err != nil {
+ return nil, err
+ }
+
+ return &graphCommitNode{
+ hash: c.commitData.ParentHashes[i],
+ index: c.commitData.ParentIndexes[i],
+ commitData: parent,
+ gci: c.gci,
+ }, nil
+}
+
+func (c *graphCommitNode) ParentHashes() []plumbing.Hash {
+ return c.commitData.ParentHashes
+}
+
+func (c *graphCommitNode) Generation() uint64 {
+ // If the commit-graph file was generated with older Git version that
+ // set the generation to zero for every commit the generation assumption
+ // is still valid. It is just less useful.
+ return uint64(c.commitData.Generation)
+}
+
+func (c *graphCommitNode) Commit() (*Commit, error) {
+ return GetCommit(c.gci.s, c.hash)
+}
+
+func (c *graphCommitNode) String() string {
+ return fmt.Sprintf(
+ "%s %s\nDate: %s",
+ plumbing.CommitObject, c.ID(),
+ c.CommitTime().Format(DateFormat),
+ )
+}
diff --git a/plumbing/object/commitnode_object.go b/plumbing/object/commitnode_object.go new file mode 100644 index 0000000..9ac42d2 --- /dev/null +++ b/plumbing/object/commitnode_object.go @@ -0,0 +1,89 @@ +package object
+
+import (
+ "math"
+ "time"
+
+ "gopkg.in/src-d/go-git.v4/plumbing"
+ "gopkg.in/src-d/go-git.v4/plumbing/storer"
+)
+
+// objectCommitNode is a representation of Commit as presented in the GIT object format.
+//
+// objectCommitNode implements the CommitNode interface.
+type objectCommitNode struct {
+ nodeIndex CommitNodeIndex
+ commit *Commit
+}
+
+// NewObjectCommitNodeIndex returns CommitNodeIndex implementation that uses
+// only object storage to load the nodes
+func NewObjectCommitNodeIndex(s storer.EncodedObjectStorer) CommitNodeIndex {
+ return &objectCommitNodeIndex{s}
+}
+
+func (oci *objectCommitNodeIndex) Get(hash plumbing.Hash) (CommitNode, error) {
+ commit, err := GetCommit(oci.s, hash)
+ if err != nil {
+ return nil, err
+ }
+
+ return &objectCommitNode{
+ nodeIndex: oci,
+ commit: commit,
+ }, nil
+}
+
+// objectCommitNodeIndex is an index that can load CommitNode objects only from the
+// object store.
+//
+// objectCommitNodeIndex implements the CommitNodeIndex interface
+type objectCommitNodeIndex struct {
+ s storer.EncodedObjectStorer
+}
+
+func (c *objectCommitNode) CommitTime() time.Time {
+ return c.commit.Committer.When
+}
+
+func (c *objectCommitNode) ID() plumbing.Hash {
+ return c.commit.ID()
+}
+
+func (c *objectCommitNode) Tree() (*Tree, error) {
+ return c.commit.Tree()
+}
+
+func (c *objectCommitNode) NumParents() int {
+ return c.commit.NumParents()
+}
+
+func (c *objectCommitNode) ParentNodes() CommitNodeIter {
+ return newParentgraphCommitNodeIter(c)
+}
+
+func (c *objectCommitNode) ParentNode(i int) (CommitNode, error) {
+ if i < 0 || i >= len(c.commit.ParentHashes) {
+ return nil, ErrParentNotFound
+ }
+
+ // Note: It's necessary to go through CommitNodeIndex here to ensure
+ // that if the commit-graph file covers only part of the history we
+ // start using it when that part is reached.
+ return c.nodeIndex.Get(c.commit.ParentHashes[i])
+}
+
+func (c *objectCommitNode) ParentHashes() []plumbing.Hash {
+ return c.commit.ParentHashes
+}
+
+func (c *objectCommitNode) Generation() uint64 {
+ // Commit nodes representing objects outside of the commit graph can never
+ // be reached by objects from the commit-graph thus we return the highest
+ // possible value.
+ return math.MaxUint64
+}
+
+func (c *objectCommitNode) Commit() (*Commit, error) {
+ return c.commit, nil
+}
diff --git a/plumbing/object/commitnode_test.go b/plumbing/object/commitnode_test.go new file mode 100644 index 0000000..a295b8b --- /dev/null +++ b/plumbing/object/commitnode_test.go @@ -0,0 +1,144 @@ +package object
+
+import (
+ "path"
+
+ . "gopkg.in/check.v1"
+ fixtures "gopkg.in/src-d/go-git-fixtures.v3"
+ "gopkg.in/src-d/go-git.v4/plumbing"
+ "gopkg.in/src-d/go-git.v4/plumbing/cache"
+ "gopkg.in/src-d/go-git.v4/plumbing/format/commitgraph"
+ "gopkg.in/src-d/go-git.v4/plumbing/format/packfile"
+ "gopkg.in/src-d/go-git.v4/storage/filesystem"
+)
+
+type CommitNodeSuite struct {
+ fixtures.Suite
+}
+
+var _ = Suite(&CommitNodeSuite{})
+
+func unpackRepositry(f *fixtures.Fixture) *filesystem.Storage {
+ storer := filesystem.NewStorage(f.DotGit(), cache.NewObjectLRUDefault())
+ p := f.Packfile()
+ defer p.Close()
+ packfile.UpdateObjectStorage(storer, p)
+ return storer
+}
+
+func testWalker(c *C, nodeIndex CommitNodeIndex) {
+ head, err := nodeIndex.Get(plumbing.NewHash("b9d69064b190e7aedccf84731ca1d917871f8a1c"))
+ c.Assert(err, IsNil)
+
+ iter := NewCommitNodeIterCTime(
+ head,
+ nil,
+ nil,
+ )
+
+ var commits []CommitNode
+ iter.ForEach(func(c CommitNode) error {
+ commits = append(commits, c)
+ return nil
+ })
+
+ c.Assert(commits, HasLen, 9)
+
+ expected := []string{
+ "b9d69064b190e7aedccf84731ca1d917871f8a1c",
+ "6f6c5d2be7852c782be1dd13e36496dd7ad39560",
+ "a45273fe2d63300e1962a9e26a6b15c276cd7082",
+ "c0edf780dd0da6a65a7a49a86032fcf8a0c2d467",
+ "bb13916df33ed23004c3ce9ed3b8487528e655c1",
+ "03d2c021ff68954cf3ef0a36825e194a4b98f981",
+ "ce275064ad67d51e99f026084e20827901a8361c",
+ "e713b52d7e13807e87a002e812041f248db3f643",
+ "347c91919944a68e9413581a1bc15519550a3afe",
+ }
+ for i, commit := range commits {
+ c.Assert(commit.ID().String(), Equals, expected[i])
+ }
+}
+
+func testParents(c *C, nodeIndex CommitNodeIndex) {
+ merge3, err := nodeIndex.Get(plumbing.NewHash("6f6c5d2be7852c782be1dd13e36496dd7ad39560"))
+ c.Assert(err, IsNil)
+
+ var parents []CommitNode
+ merge3.ParentNodes().ForEach(func(c CommitNode) error {
+ parents = append(parents, c)
+ return nil
+ })
+
+ c.Assert(parents, HasLen, 3)
+
+ expected := []string{
+ "ce275064ad67d51e99f026084e20827901a8361c",
+ "bb13916df33ed23004c3ce9ed3b8487528e655c1",
+ "a45273fe2d63300e1962a9e26a6b15c276cd7082",
+ }
+ for i, parent := range parents {
+ c.Assert(parent.ID().String(), Equals, expected[i])
+ }
+}
+
+func testCommitAndTree(c *C, nodeIndex CommitNodeIndex) {
+ merge3node, err := nodeIndex.Get(plumbing.NewHash("6f6c5d2be7852c782be1dd13e36496dd7ad39560"))
+ c.Assert(err, IsNil)
+ merge3commit, err := merge3node.Commit()
+ c.Assert(err, IsNil)
+ c.Assert(merge3node.ID().String(), Equals, merge3commit.ID().String())
+ tree, err := merge3node.Tree()
+ c.Assert(err, IsNil)
+ c.Assert(tree.ID().String(), Equals, merge3commit.TreeHash.String())
+}
+
+func (s *CommitNodeSuite) TestObjectGraph(c *C) {
+ f := fixtures.ByTag("commit-graph").One()
+ storer := unpackRepositry(f)
+
+ nodeIndex := NewObjectCommitNodeIndex(storer)
+ testWalker(c, nodeIndex)
+ testParents(c, nodeIndex)
+ testCommitAndTree(c, nodeIndex)
+}
+
+func (s *CommitNodeSuite) TestCommitGraph(c *C) {
+ f := fixtures.ByTag("commit-graph").One()
+ storer := unpackRepositry(f)
+ reader, err := storer.Filesystem().Open(path.Join("objects", "info", "commit-graph"))
+ c.Assert(err, IsNil)
+ defer reader.Close()
+ index, err := commitgraph.OpenFileIndex(reader)
+ c.Assert(err, IsNil)
+
+ nodeIndex := NewGraphCommitNodeIndex(index, storer)
+ testWalker(c, nodeIndex)
+ testParents(c, nodeIndex)
+ testCommitAndTree(c, nodeIndex)
+}
+
+func (s *CommitNodeSuite) TestMixedGraph(c *C) {
+ f := fixtures.ByTag("commit-graph").One()
+ storer := unpackRepositry(f)
+
+ // Take the commit-graph file and copy it to memory index without the last commit
+ reader, err := storer.Filesystem().Open(path.Join("objects", "info", "commit-graph"))
+ c.Assert(err, IsNil)
+ defer reader.Close()
+ fileIndex, err := commitgraph.OpenFileIndex(reader)
+ c.Assert(err, IsNil)
+ memoryIndex := commitgraph.NewMemoryIndex()
+ for i, hash := range fileIndex.Hashes() {
+ if hash.String() != "b9d69064b190e7aedccf84731ca1d917871f8a1c" {
+ node, err := fileIndex.GetCommitDataByIndex(i)
+ c.Assert(err, IsNil)
+ memoryIndex.Add(hash, node)
+ }
+ }
+
+ nodeIndex := NewGraphCommitNodeIndex(memoryIndex, storer)
+ testWalker(c, nodeIndex)
+ testParents(c, nodeIndex)
+ testCommitAndTree(c, nodeIndex)
+}
diff --git a/plumbing/object/commitnode_walker_ctime.go b/plumbing/object/commitnode_walker_ctime.go new file mode 100644 index 0000000..e55b4ad --- /dev/null +++ b/plumbing/object/commitnode_walker_ctime.go @@ -0,0 +1,105 @@ +package object
+
+import (
+ "io"
+
+ "github.com/emirpasic/gods/trees/binaryheap"
+
+ "gopkg.in/src-d/go-git.v4/plumbing"
+ "gopkg.in/src-d/go-git.v4/plumbing/storer"
+)
+
+type commitNodeIteratorByCTime struct {
+ heap *binaryheap.Heap
+ seenExternal map[plumbing.Hash]bool
+ seen map[plumbing.Hash]bool
+}
+
+// NewCommitNodeIterCTime returns a CommitNodeIter that walks the commit history,
+// starting at the given commit and visiting its parents while preserving Committer Time order.
+// this appears to be the closest order to `git log`
+// The given callback will be called for each visited commit. Each commit will
+// be visited only once. If the callback returns an error, walking will stop
+// and will return the error. Other errors might be returned if the history
+// cannot be traversed (e.g. missing objects). Ignore allows to skip some
+// commits from being iterated.
+func NewCommitNodeIterCTime(
+ c CommitNode,
+ seenExternal map[plumbing.Hash]bool,
+ ignore []plumbing.Hash,
+) CommitNodeIter {
+ seen := make(map[plumbing.Hash]bool)
+ for _, h := range ignore {
+ seen[h] = true
+ }
+
+ heap := binaryheap.NewWith(func(a, b interface{}) int {
+ if a.(CommitNode).CommitTime().Before(b.(CommitNode).CommitTime()) {
+ return 1
+ }
+ return -1
+ })
+
+ heap.Push(c)
+
+ return &commitNodeIteratorByCTime{
+ heap: heap,
+ seenExternal: seenExternal,
+ seen: seen,
+ }
+}
+
+func (w *commitNodeIteratorByCTime) Next() (CommitNode, error) {
+ var c CommitNode
+ for {
+ cIn, ok := w.heap.Pop()
+ if !ok {
+ return nil, io.EOF
+ }
+ c = cIn.(CommitNode)
+ cID := c.ID()
+
+ if w.seen[cID] || w.seenExternal[cID] {
+ continue
+ }
+
+ w.seen[cID] = true
+
+ for i, h := range c.ParentHashes() {
+ if w.seen[h] || w.seenExternal[h] {
+ continue
+ }
+ pc, err := c.ParentNode(i)
+ if err != nil {
+ return nil, err
+ }
+ w.heap.Push(pc)
+ }
+
+ return c, nil
+ }
+}
+
+func (w *commitNodeIteratorByCTime) ForEach(cb func(CommitNode) error) error {
+ for {
+ c, err := w.Next()
+ if err == io.EOF {
+ break
+ }
+ if err != nil {
+ return err
+ }
+
+ err = cb(c)
+ if err == storer.ErrStop {
+ break
+ }
+ if err != nil {
+ return err
+ }
+ }
+
+ return nil
+}
+
+func (w *commitNodeIteratorByCTime) Close() {}
|