Skip to content

Instantly share code, notes, and snippets.

@filipnavara

filipnavara/commitgraph.go

Created September 25, 2018 17:24
Show Gist options
  • Save filipnavara/2b0fb82014a5aee732c44a40ad77e29d to your computer and use it in GitHub Desktop.
Save filipnavara/2b0fb82014a5aee732c44a40ad77e29d to your computer and use it in GitHub Desktop.
Download ZIP
Raw
commitgraph.go
package commitgraph
import (
"bytes"
"errors"
"io"
"math"
"time"
"gopkg.in/src-d/go-git.v4/plumbing"
"gopkg.in/src-d/go-git.v4/utils/binary"
)
// Node is a reduced representation of Commit as presented in the commit graph
// file. It is merely useful as an optimization for walking the commit graphs.
type Node struct {
// TreeHash is the hash of the root tree of the commit.
TreeHash plumbing.Hash
// ParentHashes are the hashes of the parent commits of the commit.
ParentIndexes []uint32
// Generation number is the pre-computed generation in the commit graph
// or zero if not available
Generation uint32
// When is the timestamp of the commit.
When time.Time
}
// Index represents a representation of commit graph that allows indexed
// access to the nodes using commit object hash
type Index interface {
// GetNodeByHash gets the commit node from the commit graph using its hash, if available
GetNodeByHash(h plumbing.Hash) (*Node, error)
// GetNodeByIndex gets the commit node from the commit graph using index
// obtained from child node, if available
GetNodeByIndex(i uint32) (*Node, error)
}
var (
// ErrUnsupportedVersion is returned by OpenFileIndex when the commit graph
// file version is not supported.
ErrUnsupportedVersion = errors.New("Unsuported version")
// ErrUnsupportedHash is returned by OpenFileIndex when the commit graph
// hash function is not supported. Currently only SHA-1 is defined and
// supported
ErrUnsupportedHash = errors.New("Unsuported hash algorithm")
// ErrMalformedCommitGraphFile is returned by OpenFileIndex when the commit
// graph file is corrupted.
ErrMalformedCommitGraphFile = errors.New("Malformed commit graph file")
commitFileSignature = []byte{'C', 'G', 'P', 'H'}
oidFanoutSignature = []byte{'O', 'I', 'D', 'F'}
oidLookupSignature = []byte{'O', 'I', 'D', 'L'}
commitDataSignature = []byte{'C', 'D', 'A', 'T'}
largeEdgeListSignature = []byte{'E', 'D', 'G', 'E'}
parentNone = uint32(0x70000000)
parentOctopusUsed = uint32(0x80000000)
parentOctopusMask = uint32(0x7fffffff)
parentLast = uint32(0x80000000)
)
type fileIndex struct {
reader io.ReaderAt
fanout [256]uint32
oidLookupOffset int64
commitDataOffset int64
largeEdgeListOffset int64
}
// OpenFileIndex opens a serialized commit graph file
// in the format described at
// https://github.com/git/git/blob/master/Documentation/technical/commit-graph-format.txt
func OpenFileIndex(reader io.ReaderAt) (Index, error) {
// Verify file signature
var signature = make([]byte, 4)
if _, err := reader.ReadAt(signature, 0); err != nil {
return nil, err
}
if !bytes.Equal(signature, commitFileSignature) {
return nil, ErrMalformedCommitGraphFile
}
// Read and verify the file header
var header = make([]byte, 4)
if _, err := reader.ReadAt(header, 4); err != nil {
return nil, err
}
if header[0] != 1 {
return nil, ErrUnsupportedVersion
}
if header[1] != 1 {
return nil, ErrUnsupportedHash
}
// Read chunk headers
var chunkID = make([]byte, 4)
var oidFanoutOffset int64
var oidLookupOffset int64
var commitDataOffset int64
var largeEdgeListOffset int64
chunkCount := int(header[2])
for i := 0; i < chunkCount; i++ {
chunkHeader := io.NewSectionReader(reader, 8+(int64(i)*12), 12)
if _, err := io.ReadAtLeast(chunkHeader, chunkID, 4); err != nil {
return nil, err
}
chunkOffset, err := binary.ReadUint64(chunkHeader)
if err != nil {
return nil, err
}
if bytes.Equal(chunkID, oidFanoutSignature) {
oidFanoutOffset = int64(chunkOffset)
} else if bytes.Equal(chunkID, oidLookupSignature) {
oidLookupOffset = int64(chunkOffset)
} else if bytes.Equal(chunkID, commitDataSignature) {
commitDataOffset = int64(chunkOffset)
} else if bytes.Equal(chunkID, largeEdgeListSignature) {
largeEdgeListOffset = int64(chunkOffset)
}
}
if oidFanoutOffset <= 0 || oidLookupOffset <= 0 || commitDataOffset <= 0 {
return nil, ErrMalformedCommitGraphFile
}
// Read fanout table and calculate the file offsets into the lookup table
fanoutReader := io.NewSectionReader(reader, oidFanoutOffset, 256*4)
var fanout [256]uint32
for i := 0; i < 256; i++ {
var err error
if fanout[i], err = binary.ReadUint32(fanoutReader); err != nil {
return nil, err
}
}
return &fileIndex{reader, fanout, oidLookupOffset, commitDataOffset, largeEdgeListOffset}, nil
}
func (fi *fileIndex) findHashIndex(h plumbing.Hash) (uint32, bool) {
oid := make([]byte, 20)
// Find the hash in the oid lookup table
var low uint32
if h[0] == 0 {
low = 0
} else {
low = fi.fanout[h[0]-1]
}
high := fi.fanout[h[0]]
for low < high {
mid := (low + high) >> 1
offset := fi.oidLookupOffset + int64(mid)*20
if _, err := fi.reader.ReadAt(oid, offset); err != nil {
return 0, false
}
cmp := bytes.Compare(h[:], oid)
if cmp < 0 {
high = mid
} else if cmp == 0 {
return mid, true
} else {
low = mid + 1
}
}
return 0, false
}
func (fi *fileIndex) GetNodeByHash(h plumbing.Hash) (*Node, error) {
idx, found := fi.findHashIndex(h)
if !found {
return nil, nil
}
return fi.GetNodeByIndex(idx)
}
func (fi *fileIndex) GetNodeByIndex(idx uint32) (*Node, error) {
offset := fi.commitDataOffset + int64(idx)*36
commitDataReader := io.NewSectionReader(fi.reader, offset, 36)
treeHash, err := binary.ReadHash(commitDataReader)
if err != nil {
return nil, err
}
parent1, err := binary.ReadUint32(commitDataReader)
if err != nil {
return nil, err
}
parent2, err := binary.ReadUint32(commitDataReader)
if err != nil {
return nil, err
}
genAndTime, err := binary.ReadUint64(commitDataReader)
if err != nil {
return nil, err
}
var parentIndexes []uint32
if parent2&parentOctopusUsed == parentOctopusUsed {
// Octopus merge
parentIndexes = append(parentIndexes, parent1)
offset := fi.largeEdgeListOffset + 4*int64(parent2&parentOctopusMask)
parentReader := io.NewSectionReader(fi.reader, offset, math.MaxInt64)
for {
parent, err := binary.ReadUint32(parentReader)
if err != nil {
return nil, err
}
parentIndexes = append(parentIndexes, parent1&parentOctopusMask)
if parent&parentLast == parentLast {
break
}
}
} else if parent2 != parentNone {
parentIndexes = append(parentIndexes, parent1)
parentIndexes = append(parentIndexes, parent2)
} else if parent1 != parentNone {
parentIndexes = append(parentIndexes, parent1)
}
return &Node{
TreeHash: treeHash,
ParentIndexes: parentIndexes,
Generation: uint32(genAndTime >> 34),
When: time.Unix(int64(genAndTime&0x3FFFFFFFF), 0),
}, nil
}
@filipnavara
Copy link
Author

Usage:

	reader, err := mmap.Open("C:\\Projects\\testgit\\.git\\objects\\info\\commit-graph")
	c.Assert(err, IsNil)
	index, err := commitgraph.OpenFileIndex(reader)
	c.Assert(err, IsNil)

	node, err := index.GetNodeByHash(plumbing.NewHash("5aa811d3c2f6d5d6e928a4acacd15248928c26d0"))
	c.Assert(err, IsNil)
	c.Assert(len(node.ParentIndexes), Equals, 0)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment