plumbing: commitgraph, Add generation v2 support

This PR adds in support for generation v2 support and a couple of new
walkers to match --date-order etc options on log. This PR also fixes a
bug in the chain code and adds more tests.

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

6 files changed, 255 insertions, 54 deletions

diff --git a/plumbing/format/commitgraph/v2/chunk.go b/plumbing/format/commitgraph/v2/chunk.go
index ab24320..11f4d31 100644
--- a/plumbing/format/commitgraph/v2/chunk.go
+++ b/plumbing/format/commitgraph/v2/chunk.go
@@ -3,7 +3,7 @@ package v2
 import "bytes"
 
 const (
-	chunkSigLen    = 4 // Length of a chunk signature
+	szChunkSig     = 4 // Length of a chunk signature
 	chunkSigOffset = 4 // Offset of each chunk signature in chunkSignatures
 )
 
@@ -28,14 +28,15 @@ const (
 	BaseGraphsListChunk                          // "BASE"
 	ZeroChunk                                    // "\000\000\000\000"
 )
+const lenChunks = int(ZeroChunk) // ZeroChunk is not a valid chunk type, but it is used to determine the length of the chunk type list.
 
 // Signature returns the byte signature for the chunk type.
 func (ct ChunkType) Signature() []byte {
 	if ct >= BaseGraphsListChunk || ct < 0 { // not a valid chunk type just return ZeroChunk
-		return chunkSignatures[ZeroChunk*chunkSigOffset : ZeroChunk*chunkSigOffset+chunkSigLen]
+		return chunkSignatures[ZeroChunk*chunkSigOffset : ZeroChunk*chunkSigOffset+szChunkSig]
 	}
 
-	return chunkSignatures[ct*chunkSigOffset : ct*chunkSigOffset+chunkSigLen]
+	return chunkSignatures[ct*chunkSigOffset : ct*chunkSigOffset+szChunkSig]
 }
 
 // ChunkTypeFromBytes returns the chunk type for the given byte signature.
diff --git a/plumbing/format/commitgraph/v2/commitgraph.go b/plumbing/format/commitgraph/v2/commitgraph.go
index 7c67b63..9c89cd9 100644
--- a/plumbing/format/commitgraph/v2/commitgraph.go
+++ b/plumbing/format/commitgraph/v2/commitgraph.go
@@ -2,6 +2,7 @@ package v2
 
 import (
 	"io"
+	"math"
 	"time"
 
 	"github.com/go-git/go-git/v5/plumbing"
@@ -19,10 +20,22 @@ type CommitData struct {
 	// Generation number is the pre-computed generation in the commit graph
 	// or zero if not available.
 	Generation uint64
+	// GenerationV2 stores the corrected commit date for the commits
+	// It combines the contents of the GDA2 and GDO2 sections of the commit-graph
+	// with the commit time portion of the CDAT section.
+	GenerationV2 uint64
 	// When is the timestamp of the commit.
 	When time.Time
 }
 
+// GenerationV2Data returns the corrected commit date for the commits
+func (c *CommitData) GenerationV2Data() uint64 {
+	if c.GenerationV2 == 0 || c.GenerationV2 == math.MaxUint64 {
+		return 0
+	}
+	return c.GenerationV2 - uint64(c.When.Unix())
+}
+
 // Index represents a representation of commit graph that allows indexed
 // access to the nodes using commit object hash
 type Index interface {
@@ -35,6 +48,10 @@ type Index interface {
 	GetCommitDataByIndex(i uint32) (*CommitData, error)
 	// Hashes returns all the hashes that are available in the index
 	Hashes() []plumbing.Hash
+	// HasGenerationV2 returns true if the commit graph has the corrected commit date data
+	HasGenerationV2() bool
+	// MaximumNumberOfHashes returns the maximum number of hashes within the index
+	MaximumNumberOfHashes() uint32
 
 	io.Closer
 }
diff --git a/plumbing/format/commitgraph/v2/commitgraph_test.go b/plumbing/format/commitgraph/v2/commitgraph_test.go
index 69fdcd9..1278405 100644
--- a/plumbing/format/commitgraph/v2/commitgraph_test.go
+++ b/plumbing/format/commitgraph/v2/commitgraph_test.go
@@ -7,7 +7,11 @@ import (
 	"github.com/go-git/go-billy/v5"

 	"github.com/go-git/go-billy/v5/util"

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

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

 	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/plumbing/object"

+	"github.com/go-git/go-git/v5/storage/filesystem"

 

 	fixtures "github.com/go-git/go-git-fixtures/v4"

 	. "gopkg.in/check.v1"

@@ -76,6 +80,37 @@ func testDecodeHelper(c *C, index commitgraph.Index) {
 	c.Assert(hashes[10].String(), Equals, "e713b52d7e13807e87a002e812041f248db3f643")

 }

 

+func (s *CommitgraphSuite) TestDecodeMultiChain(c *C) {

+	fixtures.ByTag("commit-graph-chain-2").Test(c, func(f *fixtures.Fixture) {

+		dotgit := f.DotGit()

+		index, err := commitgraph.OpenChainOrFileIndex(dotgit)

+		c.Assert(err, IsNil)

+		defer index.Close()

+		storer := filesystem.NewStorage(f.DotGit(), cache.NewObjectLRUDefault())

+		p := f.Packfile()

+		defer p.Close()

+		packfile.UpdateObjectStorage(storer, p)

+

+		for idx, hash := range index.Hashes() {

+			idx2, err := index.GetIndexByHash(hash)

+			c.Assert(err, IsNil)

+			c.Assert(idx2, Equals, uint32(idx))

+			hash2, err := index.GetHashByIndex(idx2)

+			c.Assert(err, IsNil)

+			c.Assert(hash2.String(), Equals, hash.String())

+

+			commitData, err := index.GetCommitDataByIndex(uint32(idx))

+			c.Assert(err, IsNil)

+			commit, err := object.GetCommit(storer, hash)

+			c.Assert(err, IsNil)

+

+			for i, parent := range commit.ParentHashes {

+				c.Assert(hash.String()+":"+parent.String(), Equals, hash.String()+":"+commitData.ParentHashes[i].String())

+			}

+		}

+	})

+}

+

 func (s *CommitgraphSuite) TestDecode(c *C) {

 	fixtures.ByTag("commit-graph").Test(c, func(f *fixtures.Fixture) {

 		dotgit := f.DotGit()

diff --git a/plumbing/format/commitgraph/v2/encoder.go b/plumbing/format/commitgraph/v2/encoder.go
index d1e41f8..b79bc77 100644
--- a/plumbing/format/commitgraph/v2/encoder.go
+++ b/plumbing/format/commitgraph/v2/encoder.go
@@ -3,6 +3,7 @@ package v2
 import (
 	"crypto"
 	"io"
+	"math"
 
 	"github.com/go-git/go-git/v5/plumbing"
 	"github.com/go-git/go-git/v5/plumbing/hash"
@@ -28,13 +29,21 @@ func (e *Encoder) Encode(idx Index) error {
 	hashes := idx.Hashes()
 
 	// Sort the inout and prepare helper structures we'll need for encoding
-	hashToIndex, fanout, extraEdgesCount := e.prepare(idx, hashes)
+	hashToIndex, fanout, extraEdgesCount, generationV2OverflowCount := e.prepare(idx, hashes)
 
 	chunkSignatures := [][]byte{OIDFanoutChunk.Signature(), OIDLookupChunk.Signature(), CommitDataChunk.Signature()}
-	chunkSizes := []uint64{4 * 256, uint64(len(hashes)) * hash.Size, uint64(len(hashes)) * (hash.Size + commitDataSize)}
+	chunkSizes := []uint64{szUint32 * lenFanout, uint64(len(hashes)) * hash.Size, uint64(len(hashes)) * (hash.Size + szCommitData)}
 	if extraEdgesCount > 0 {
 		chunkSignatures = append(chunkSignatures, ExtraEdgeListChunk.Signature())
-		chunkSizes = append(chunkSizes, uint64(extraEdgesCount)*4)
+		chunkSizes = append(chunkSizes, uint64(extraEdgesCount)*szUint32)
+	}
+	if idx.HasGenerationV2() {
+		chunkSignatures = append(chunkSignatures, GenerationDataChunk.Signature())
+		chunkSizes = append(chunkSizes, uint64(len(hashes))*szUint32)
+		if generationV2OverflowCount > 0 {
+			chunkSignatures = append(chunkSignatures, GenerationDataOverflowChunk.Signature())
+			chunkSizes = append(chunkSizes, uint64(generationV2OverflowCount)*szUint64)
+		}
 	}
 
 	if err := e.encodeFileHeader(len(chunkSignatures)); err != nil {
@@ -49,38 +58,52 @@ func (e *Encoder) Encode(idx Index) error {
 	if err := e.encodeOidLookup(hashes); err != nil {
 		return err
 	}
-	if extraEdges, err := e.encodeCommitData(hashes, hashToIndex, idx); err == nil {
-		if err = e.encodeExtraEdges(extraEdges); err != nil {
+
+	extraEdges, generationV2Data, err := e.encodeCommitData(hashes, hashToIndex, idx)
+	if err != nil {
+		return err
+	}
+	if err = e.encodeExtraEdges(extraEdges); err != nil {
+		return err
+	}
+	if idx.HasGenerationV2() {
+		overflows, err := e.encodeGenerationV2Data(generationV2Data)
+		if err != nil {
+			return err
+		}
+		if err = e.encodeGenerationV2Overflow(overflows); err != nil {
 			return err
 		}
-	} else {
-		return err
 	}
 
 	return e.encodeChecksum()
 }
 
-func (e *Encoder) prepare(idx Index, hashes []plumbing.Hash) (hashToIndex map[plumbing.Hash]uint32, fanout []uint32, extraEdgesCount uint32) {
+func (e *Encoder) prepare(idx Index, hashes []plumbing.Hash) (hashToIndex map[plumbing.Hash]uint32, fanout []uint32, extraEdgesCount uint32, generationV2OverflowCount uint32) {
 	// Sort the hashes and build our index
 	plumbing.HashesSort(hashes)
 	hashToIndex = make(map[plumbing.Hash]uint32)
-	fanout = make([]uint32, 256)
+	fanout = make([]uint32, lenFanout)
 	for i, hash := range hashes {
 		hashToIndex[hash] = uint32(i)
 		fanout[hash[0]]++
 	}
 
 	// Convert the fanout to cumulative values
-	for i := 1; i <= 0xff; i++ {
+	for i := 1; i < lenFanout; i++ {
 		fanout[i] += fanout[i-1]
 	}
 
+	hasGenerationV2 := idx.HasGenerationV2()
+
 	// Find out if we will need extra edge table
 	for i := 0; i < len(hashes); i++ {
 		v, _ := idx.GetCommitDataByIndex(uint32(i))
 		if len(v.ParentHashes) > 2 {
 			extraEdgesCount += uint32(len(v.ParentHashes) - 1)
-			break
+		}
+		if hasGenerationV2 && v.GenerationV2Data() > math.MaxUint32 {
+			generationV2OverflowCount++
 		}
 	}
 
@@ -100,7 +123,7 @@ func (e *Encoder) encodeFileHeader(chunkCount int) (err error) {
 
 func (e *Encoder) encodeChunkHeaders(chunkSignatures [][]byte, chunkSizes []uint64) (err error) {
 	// 8 bytes of file header, 12 bytes for each chunk header and 12 byte for terminator
-	offset := uint64(8 + len(chunkSignatures)*12 + 12)
+	offset := uint64(szSignature + szHeader + (len(chunkSignatures)+1)*(szChunkSig+szUint64))
 	for i, signature := range chunkSignatures {
 		if _, err = e.Write(signature); err == nil {
 			err = binary.WriteUint64(e, offset)
@@ -134,7 +157,10 @@ func (e *Encoder) encodeOidLookup(hashes []plumbing.Hash) (err error) {
 	return
 }
 
-func (e *Encoder) encodeCommitData(hashes []plumbing.Hash, hashToIndex map[plumbing.Hash]uint32, idx Index) (extraEdges []uint32, err error) {
+func (e *Encoder) encodeCommitData(hashes []plumbing.Hash, hashToIndex map[plumbing.Hash]uint32, idx Index) (extraEdges []uint32, generationV2Data []uint64, err error) {
+	if idx.HasGenerationV2() {
+		generationV2Data = make([]uint64, 0, len(hashes))
+	}
 	for _, hash := range hashes {
 		origIndex, _ := idx.GetIndexByHash(hash)
 		commitData, _ := idx.GetCommitDataByIndex(origIndex)
@@ -173,6 +199,9 @@ func (e *Encoder) encodeCommitData(hashes []plumbing.Hash, hashToIndex map[plumb
 		if err = binary.WriteUint64(e, unixTime); err != nil {
 			return
 		}
+		if generationV2Data != nil {
+			generationV2Data = append(generationV2Data, commitData.GenerationV2Data())
+		}
 	}
 	return
 }
@@ -186,6 +215,35 @@ func (e *Encoder) encodeExtraEdges(extraEdges []uint32) (err error) {
 	return
 }
 
+func (e *Encoder) encodeGenerationV2Data(generationV2Data []uint64) (overflows []uint64, err error) {
+	head := 0
+	for _, data := range generationV2Data {
+		if data >= 0x80000000 {
+			// overflow
+			if err = binary.WriteUint32(e, uint32(head)|0x80000000); err != nil {
+				return nil, err
+			}
+			generationV2Data[head] = data
+			head++
+			continue
+		}
+		if err = binary.WriteUint32(e, uint32(data)); err != nil {
+			return nil, err
+		}
+	}
+
+	return generationV2Data[:head], nil
+}
+
+func (e *Encoder) encodeGenerationV2Overflow(overflows []uint64) (err error) {
+	for _, overflow := range overflows {
+		if err = binary.WriteUint64(e, overflow); err != nil {
+			return
+		}
+	}
+	return
+}
+
 func (e *Encoder) encodeChecksum() error {
 	_, err := e.Write(e.hash.Sum(nil)[:hash.Size])
 	return err
diff --git a/plumbing/format/commitgraph/v2/file.go b/plumbing/format/commitgraph/v2/file.go
index 69e0250..c5f61e4 100644
--- a/plumbing/format/commitgraph/v2/file.go
+++ b/plumbing/format/commitgraph/v2/file.go
@@ -34,14 +34,23 @@ var (
 )
 
 const (
-	commitDataSize = 16
+	szUint32 = 4
+	szUint64 = 8
+
+	szSignature  = 4
+	szHeader     = 4
+	szCommitData = 2*szUint32 + szUint64
+
+	lenFanout = 256
 )
 
 type fileIndex struct {
-	reader  ReaderAtCloser
-	fanout  [256]uint32
-	offsets [9]int64
-	parent  Index
+	reader                ReaderAtCloser
+	fanout                [lenFanout]uint32
+	offsets               [lenChunks]int64
+	parent                Index
+	hasGenerationV2       bool
+	minimumNumberOfHashes uint32
 }
 
 // ReaderAtCloser is an interface that combines io.ReaderAt and io.Closer.
@@ -74,6 +83,15 @@ func OpenFileIndexWithParent(reader ReaderAtCloser, parent Index) (Index, error)
 		return nil, err
 	}
 
+	fi.hasGenerationV2 = fi.offsets[GenerationDataChunk] > 0
+	if fi.parent != nil {
+		fi.hasGenerationV2 = fi.hasGenerationV2 && fi.parent.HasGenerationV2()
+	}
+
+	if fi.parent != nil {
+		fi.minimumNumberOfHashes = fi.parent.MaximumNumberOfHashes()
+	}
+
 	return fi, nil
 }
 
@@ -94,7 +112,7 @@ func (fi *fileIndex) Close() (err error) {
 
 func (fi *fileIndex) verifyFileHeader() error {
 	// Verify file signature
-	signature := make([]byte, 4)
+	signature := make([]byte, szSignature)
 	if _, err := fi.reader.ReadAt(signature, 0); err != nil {
 		return err
 	}
@@ -103,8 +121,8 @@ func (fi *fileIndex) verifyFileHeader() error {
 	}
 
 	// Read and verify the file header
-	header := make([]byte, 4)
-	if _, err := fi.reader.ReadAt(header, 4); err != nil {
+	header := make([]byte, szHeader)
+	if _, err := fi.reader.ReadAt(header, szHeader); err != nil {
 		return err
 	}
 	if header[0] != 1 {
@@ -120,10 +138,11 @@ func (fi *fileIndex) verifyFileHeader() error {
 }
 
 func (fi *fileIndex) readChunkHeaders() error {
-	chunkID := make([]byte, 4)
+	// The chunk table is a list of 4-byte chunk signatures and uint64 offsets into the file
+	chunkID := make([]byte, szChunkSig)
 	for i := 0; ; i++ {
-		chunkHeader := io.NewSectionReader(fi.reader, 8+(int64(i)*12), 12)
-		if _, err := io.ReadAtLeast(chunkHeader, chunkID, 4); err != nil {
+		chunkHeader := io.NewSectionReader(fi.reader, szSignature+szHeader+(int64(i)*(szChunkSig+szUint64)), szChunkSig+szUint64)
+		if _, err := io.ReadAtLeast(chunkHeader, chunkID, szChunkSig); err != nil {
 			return err
 		}
 		chunkOffset, err := binary.ReadUint64(chunkHeader)
@@ -149,7 +168,9 @@ func (fi *fileIndex) readChunkHeaders() error {
 }
 
 func (fi *fileIndex) readFanout() error {
-	fanoutReader := io.NewSectionReader(fi.reader, fi.offsets[OIDFanoutChunk], 256*4)
+	// The Fanout table is a 256 entry table of the number (as uint32) of OIDs with first byte at most i.
+	// Thus F[255] stores the total number of commits (N)
+	fanoutReader := io.NewSectionReader(fi.reader, fi.offsets[OIDFanoutChunk], lenFanout*szUint32)
 	for i := 0; i < 256; i++ {
 		fanoutValue, err := binary.ReadUint32(fanoutReader)
 		if err != nil {
@@ -185,7 +206,7 @@ func (fi *fileIndex) GetIndexByHash(h plumbing.Hash) (uint32, error) {
 		if cmp < 0 {
 			high = mid
 		} else if cmp == 0 {
-			return mid, nil
+			return mid + fi.minimumNumberOfHashes, nil
 		} else {
 			low = mid + 1
 		}
@@ -196,7 +217,7 @@ func (fi *fileIndex) GetIndexByHash(h plumbing.Hash) (uint32, error) {
 		if err != nil {
 			return 0, err
 		}
-		return idx + fi.fanout[0xff], nil
+		return idx, nil
 	}
 
 	return 0, plumbing.ErrObjectNotFound
@@ -204,23 +225,24 @@ func (fi *fileIndex) GetIndexByHash(h plumbing.Hash) (uint32, error) {
 
 // GetCommitDataByIndex returns the commit data for the given index in the commit-graph.
 func (fi *fileIndex) GetCommitDataByIndex(idx uint32) (*CommitData, error) {
-	if idx >= fi.fanout[0xff] {
+	if idx < fi.minimumNumberOfHashes {
 		if fi.parent != nil {
-			data, err := fi.parent.GetCommitDataByIndex(idx - fi.fanout[0xff])
+			data, err := fi.parent.GetCommitDataByIndex(idx)
 			if err != nil {
 				return nil, err
 			}
-			for i := range data.ParentIndexes {
-				data.ParentIndexes[i] += fi.fanout[0xff]
-			}
 			return data, nil
 		}
 
 		return nil, plumbing.ErrObjectNotFound
 	}
+	idx -= fi.minimumNumberOfHashes
+	if idx >= fi.fanout[0xff] {
+		return nil, plumbing.ErrObjectNotFound
+	}
 
-	offset := fi.offsets[CommitDataChunk] + int64(idx)*(hash.Size+commitDataSize)
-	commitDataReader := io.NewSectionReader(fi.reader, offset, hash.Size+commitDataSize)
+	offset := fi.offsets[CommitDataChunk] + int64(idx)*(hash.Size+szCommitData)
+	commitDataReader := io.NewSectionReader(fi.reader, offset, hash.Size+szCommitData)
 
 	treeHash, err := binary.ReadHash(commitDataReader)
 	if err != nil {
@@ -241,10 +263,11 @@ func (fi *fileIndex) GetCommitDataByIndex(idx uint32) (*CommitData, error) {
 
 	var parentIndexes []uint32
 	if parent2&parentOctopusUsed == parentOctopusUsed {
-		// Octopus merge
+		// Octopus merge - Look-up the extra parents from the extra edge list
+		// The extra edge list is a list of uint32s, each of which is an index into the Commit Data table, terminated by a index with the most significant bit on.
 		parentIndexes = []uint32{parent1 & parentOctopusMask}
-		offset := fi.offsets[ExtraEdgeListChunk] + 4*int64(parent2&parentOctopusMask)
-		buf := make([]byte, 4)
+		offset := fi.offsets[ExtraEdgeListChunk] + szUint32*int64(parent2&parentOctopusMask)
+		buf := make([]byte, szUint32)
 		for {
 			_, err := fi.reader.ReadAt(buf, offset)
 			if err != nil {
@@ -252,7 +275,7 @@ func (fi *fileIndex) GetCommitDataByIndex(idx uint32) (*CommitData, error) {
 			}
 
 			parent := encbin.BigEndian.Uint32(buf)
-			offset += 4
+			offset += szUint32
 			parentIndexes = append(parentIndexes, parent&parentOctopusMask)
 			if parent&parentLast == parentLast {
 				break
@@ -269,23 +292,57 @@ func (fi *fileIndex) GetCommitDataByIndex(idx uint32) (*CommitData, error) {
 		return nil, err
 	}
 
+	generationV2 := uint64(0)
+
+	if fi.hasGenerationV2 {
+		// set the GenerationV2 result to the commit time
+		generationV2 = uint64(genAndTime & 0x3FFFFFFFF)
+
+		// Next read the generation (offset) data from the generation data chunk
+		offset := fi.offsets[GenerationDataChunk] + int64(idx)*szUint32
+		buf := make([]byte, szUint32)
+		if _, err := fi.reader.ReadAt(buf, offset); err != nil {
+			return nil, err
+		}
+		genV2Data := encbin.BigEndian.Uint32(buf)
+
+		// check if the data is an overflow that needs to be looked up in the overflow chunk
+		if genV2Data&0x80000000 > 0 {
+			// Overflow
+			offset := fi.offsets[GenerationDataOverflowChunk] + int64(genV2Data&0x7fffffff)*szUint64
+			buf := make([]byte, 8)
+			if _, err := fi.reader.ReadAt(buf, offset); err != nil {
+				return nil, err
+			}
+
+			generationV2 += encbin.BigEndian.Uint64(buf)
+		} else {
+			generationV2 += uint64(genV2Data)
+		}
+	}
+
 	return &CommitData{
 		TreeHash:      treeHash,
 		ParentIndexes: parentIndexes,
 		ParentHashes:  parentHashes,
 		Generation:    genAndTime >> 34,
+		GenerationV2:  generationV2,
 		When:          time.Unix(int64(genAndTime&0x3FFFFFFFF), 0),
 	}, nil
 }
 
 // GetHashByIndex looks up the hash for the given index in the commit-graph.
 func (fi *fileIndex) GetHashByIndex(idx uint32) (found plumbing.Hash, err error) {
-	if idx >= fi.fanout[0xff] {
+	if idx < fi.minimumNumberOfHashes {
 		if fi.parent != nil {
-			return fi.parent.GetHashByIndex(idx - fi.fanout[0xff])
+			return fi.parent.GetHashByIndex(idx)
 		}
 		return found, ErrMalformedCommitGraphFile
 	}
+	idx -= fi.minimumNumberOfHashes
+	if idx >= fi.fanout[0xff] {
+		return found, ErrMalformedCommitGraphFile
+	}
 
 	offset := fi.offsets[OIDLookupChunk] + int64(idx)*hash.Size
 	if _, err := fi.reader.ReadAt(found[:], offset); err != nil {
@@ -299,9 +356,9 @@ func (fi *fileIndex) getHashesFromIndexes(indexes []uint32) ([]plumbing.Hash, er
 	hashes := make([]plumbing.Hash, len(indexes))
 
 	for i, idx := range indexes {
-		if idx >= fi.fanout[0xff] {
+		if idx < fi.minimumNumberOfHashes {
 			if fi.parent != nil {
-				hash, err := fi.parent.GetHashByIndex(idx - fi.fanout[0xff])
+				hash, err := fi.parent.GetHashByIndex(idx)
 				if err != nil {
 					return nil, err
 				}
@@ -312,6 +369,11 @@ func (fi *fileIndex) getHashesFromIndexes(indexes []uint32) ([]plumbing.Hash, er
 			return nil, ErrMalformedCommitGraphFile
 		}
 
+		idx -= fi.minimumNumberOfHashes
+		if idx >= fi.fanout[0xff] {
+			return nil, ErrMalformedCommitGraphFile
+		}
+
 		offset := fi.offsets[OIDLookupChunk] + int64(idx)*hash.Size
 		if _, err := fi.reader.ReadAt(hashes[i][:], offset); err != nil {
 			return nil, err
@@ -323,16 +385,28 @@ func (fi *fileIndex) getHashesFromIndexes(indexes []uint32) ([]plumbing.Hash, er
 
 // Hashes returns all the hashes that are available in the index.
 func (fi *fileIndex) Hashes() []plumbing.Hash {
-	hashes := make([]plumbing.Hash, fi.fanout[0xff])
+	hashes := make([]plumbing.Hash, fi.fanout[0xff]+fi.minimumNumberOfHashes)
+	for i := uint32(0); i < fi.minimumNumberOfHashes; i++ {
+		hash, err := fi.parent.GetHashByIndex(i)
+		if err != nil {
+			return nil
+		}
+		hashes[i] = hash
+	}
+
 	for i := uint32(0); i < fi.fanout[0xff]; i++ {
 		offset := fi.offsets[OIDLookupChunk] + int64(i)*hash.Size
-		if n, err := fi.reader.ReadAt(hashes[i][:], offset); err != nil || n < hash.Size {
+		if n, err := fi.reader.ReadAt(hashes[i+fi.minimumNumberOfHashes][:], offset); err != nil || n < hash.Size {
 			return nil
 		}
 	}
-	if fi.parent != nil {
-		parentHashes := fi.parent.Hashes()
-		hashes = append(hashes, parentHashes...)
-	}
 	return hashes
 }
+
+func (fi *fileIndex) HasGenerationV2() bool {
+	return fi.hasGenerationV2
+}
+
+func (fi *fileIndex) MaximumNumberOfHashes() uint32 {
+	return fi.minimumNumberOfHashes + fi.fanout[0xff]
+}
diff --git a/plumbing/format/commitgraph/v2/memory.go b/plumbing/format/commitgraph/v2/memory.go
index ab7ddfa..8de0c5f 100644
--- a/plumbing/format/commitgraph/v2/memory.go
+++ b/plumbing/format/commitgraph/v2/memory.go
@@ -1,14 +1,17 @@
 package v2
 
 import (
+	"math"
+
 	"github.com/go-git/go-git/v5/plumbing"
 )
 
 // MemoryIndex provides a way to build the commit-graph in memory
 // for later encoding to file.
 type MemoryIndex struct {
-	commitData []commitData
-	indexMap   map[plumbing.Hash]uint32
+	commitData      []commitData
+	indexMap        map[plumbing.Hash]uint32
+	hasGenerationV2 bool
 }
 
 type commitData struct {
@@ -19,7 +22,8 @@ type commitData struct {
 // NewMemoryIndex creates in-memory commit graph representation
 func NewMemoryIndex() *MemoryIndex {
 	return &MemoryIndex{
-		indexMap: make(map[plumbing.Hash]uint32),
+		indexMap:        make(map[plumbing.Hash]uint32),
+		hasGenerationV2: true,
 	}
 }
 
@@ -83,9 +87,21 @@ func (mi *MemoryIndex) Add(hash plumbing.Hash, data *CommitData) {
 	data.ParentIndexes = nil
 	mi.indexMap[hash] = uint32(len(mi.commitData))
 	mi.commitData = append(mi.commitData, commitData{Hash: hash, CommitData: data})
+	if data.GenerationV2 == math.MaxUint64 { // if GenerationV2 is not available reset it to zero
+		data.GenerationV2 = 0
+	}
+	mi.hasGenerationV2 = mi.hasGenerationV2 && data.GenerationV2 != 0
+}
+
+func (mi *MemoryIndex) HasGenerationV2() bool {
+	return mi.hasGenerationV2
 }
 
 // Close closes the index
 func (mi *MemoryIndex) Close() error {
 	return nil
 }
+
+func (mi *MemoryIndex) MaximumNumberOfHashes() uint32 {
+	return uint32(len(mi.indexMap))
+}