Created
September 25, 2018 17:24
-
-
Save filipnavara/2b0fb82014a5aee732c44a40ad77e29d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Usage: