plumbing: commitgraph, fix types and handle commit-graph-chains

Unfortunately the original variant makes some incorrect typing
assumptions about commit-graphs which make handling graph chains
difficult to do correctly. This creates a new subpackage and deprecates
the old one. It then adds support commit graph chains.

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

4 files changed, 335 insertions, 328 deletions

diff --git a/plumbing/object/commitgraph/commitnode_graph.go b/plumbing/object/commitgraph/commitnode_graph.go
index 8e5d4e3..252b518 100644
--- a/plumbing/object/commitgraph/commitnode_graph.go
+++ b/plumbing/object/commitgraph/commitnode_graph.go
@@ -1,131 +1,133 @@
-package commitgraph

-

-import (

-	"fmt"

-	"time"

-

-	"github.com/go-git/go-git/v5/plumbing"

-	"github.com/go-git/go-git/v5/plumbing/format/commitgraph"

-	"github.com/go-git/go-git/v5/plumbing/object"

-	"github.com/go-git/go-git/v5/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 := object.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() (*object.Tree, error) {

-	return object.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, object.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() (*object.Commit, error) {

-	return object.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(object.DateFormat),

-	)

-}

+package commitgraph
+
+import (
+	"fmt"
+	"time"
+
+	"github.com/go-git/go-git/v5/plumbing"
+	commitgraph "github.com/go-git/go-git/v5/plumbing/format/commitgraph/v2"
+	"github.com/go-git/go-git/v5/plumbing/object"
+	"github.com/go-git/go-git/v5/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 uint32
+
+	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) {
+	if gci.commitGraph != nil {
+		// 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 := object.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() (*object.Tree, error) {
+	return object.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, object.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 c.commitData.Generation
+}
+
+func (c *graphCommitNode) Commit() (*object.Commit, error) {
+	return object.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(object.DateFormat),
+	)
+}
diff --git a/plumbing/object/commitgraph/commitnode_object.go b/plumbing/object/commitgraph/commitnode_object.go
index bdf8cb7..1bd37e3 100644
--- a/plumbing/object/commitgraph/commitnode_object.go
+++ b/plumbing/object/commitgraph/commitnode_object.go
@@ -1,90 +1,90 @@
-package commitgraph

-

-import (

-	"math"

-	"time"

-

-	"github.com/go-git/go-git/v5/plumbing"

-	"github.com/go-git/go-git/v5/plumbing/object"

-	"github.com/go-git/go-git/v5/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    *object.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 := object.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() (*object.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, object.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() (*object.Commit, error) {

-	return c.commit, nil

-}

+package commitgraph
+
+import (
+	"math"
+	"time"
+
+	"github.com/go-git/go-git/v5/plumbing"
+	"github.com/go-git/go-git/v5/plumbing/object"
+	"github.com/go-git/go-git/v5/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    *object.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 := object.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() (*object.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, object.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() (*object.Commit, error) {
+	return c.commit, nil
+}
diff --git a/plumbing/object/commitgraph/commitnode_test.go b/plumbing/object/commitgraph/commitnode_test.go
index 91fb211..441ff6f 100644
--- a/plumbing/object/commitgraph/commitnode_test.go
+++ b/plumbing/object/commitgraph/commitnode_test.go
@@ -6,7 +6,7 @@ import (
 
 	"github.com/go-git/go-git/v5/plumbing"
 	"github.com/go-git/go-git/v5/plumbing/cache"
-	"github.com/go-git/go-git/v5/plumbing/format/commitgraph"
+	commitgraph "github.com/go-git/go-git/v5/plumbing/format/commitgraph/v2"
 	"github.com/go-git/go-git/v5/plumbing/format/packfile"
 	"github.com/go-git/go-git/v5/storage/filesystem"
 
@@ -115,6 +115,7 @@ func (s *CommitNodeSuite) TestCommitGraph(c *C) {
 	defer reader.Close()
 	index, err := commitgraph.OpenFileIndex(reader)
 	c.Assert(err, IsNil)
+	defer index.Close()
 
 	nodeIndex := NewGraphCommitNodeIndex(index, storer)
 	testWalker(c, nodeIndex)
@@ -132,10 +133,14 @@ func (s *CommitNodeSuite) TestMixedGraph(c *C) {
 	defer reader.Close()
 	fileIndex, err := commitgraph.OpenFileIndex(reader)
 	c.Assert(err, IsNil)
+	defer fileIndex.Close()
+
 	memoryIndex := commitgraph.NewMemoryIndex()
+	defer memoryIndex.Close()
+
 	for i, hash := range fileIndex.Hashes() {
 		if hash.String() != "b9d69064b190e7aedccf84731ca1d917871f8a1c" {
-			node, err := fileIndex.GetCommitDataByIndex(i)
+			node, err := fileIndex.GetCommitDataByIndex(uint32(i))
 			c.Assert(err, IsNil)
 			memoryIndex.Add(hash, node)
 		}
diff --git a/plumbing/object/commitgraph/commitnode_walker_ctime.go b/plumbing/object/commitgraph/commitnode_walker_ctime.go
index 281f10b..c26873c 100644
--- a/plumbing/object/commitgraph/commitnode_walker_ctime.go
+++ b/plumbing/object/commitgraph/commitnode_walker_ctime.go
@@ -1,105 +1,105 @@
-package commitgraph

-

-import (

-	"io"

-

-	"github.com/go-git/go-git/v5/plumbing"

-	"github.com/go-git/go-git/v5/plumbing/storer"

-

-	"github.com/emirpasic/gods/trees/binaryheap"

-)

-

-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() {}

+package commitgraph
+
+import (
+	"io"
+
+	"github.com/go-git/go-git/v5/plumbing"
+	"github.com/go-git/go-git/v5/plumbing/storer"
+
+	"github.com/emirpasic/gods/trees/binaryheap"
+)
+
+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() {}