package gitclient
import (
"bufio"
"bytes"
"compress/zlib"
"crypto/sha1"
"crypto/sha256"
"encoding/binary"
"encoding/hex"
"errors"
"fmt"
"hash"
"io"
"strconv"
)
type Kind int
const (
KindCommit Kind = iota + 1
KindTree
KindBlob
KindTag
)
var kindNames = [...]string{KindCommit: "commit", KindTree: "tree", KindBlob: "blob", KindTag: "tag"}
type Object struct {
Kind Kind
Data []byte
}
type Objects map[Oid]Object
const (
maxObjects = 1 << 14
maxInflated = 64 << 20 // per object and for the whole pack
)
const (
packOfsDelta = 6
packRefDelta = 7
)
type packEntry struct {
kind Kind // 0 until a delta is resolved
data []byte
baseOff int64 // ofs delta
baseOid Oid // ref delta
}
// counts consumed bytes for ofs deltas; flate takes the ByteReader as is, so
// it never reads past an entry's zlib stream
type countingReader struct {
r *bufio.Reader
off int64
}
func (c *countingReader) Read(b []byte) (int, error) {
n, err := c.r.Read(b)
c.off += int64(n)
return n, err
}
func (c *countingReader) ReadByte() (byte, error) {
b, err := c.r.ReadByte()
if err == nil {
c.off++
}
return b, err
}
// whole pack into memory with ofs/ref deltas resolved; fine for the handful of
// trees and blobs a ReadDir asks for
func readPack(r io.Reader, objectFormat string) (Objects, error) {
hashLen := oidLen(objectFormat) / 2
cr := &countingReader{r: bufio.NewReader(r)}
var hdr [12]byte
if _, err := io.ReadFull(cr, hdr[:]); err != nil {
return nil, fmt.Errorf("pack header: %w", err)
}
if string(hdr[:4]) != "PACK" {
return nil, errors.New("not a pack")
}
if v := binary.BigEndian.Uint32(hdr[4:8]); v != 2 && v != 3 {
return nil, fmt.Errorf("pack version %d", v)
}
count := binary.BigEndian.Uint32(hdr[8:])
if count > maxObjects {
return nil, fmt.Errorf("%w: %d objects", ErrTooLarge, count)
}
entries := make([]packEntry, count)
byOff := make(map[int64]int, count)
var budget int64 = maxInflated
for i := range entries {
off := cr.off
byOff[off] = i
c, err := cr.ReadByte()
if err != nil {
return nil, fmt.Errorf("pack entry: %w", err)
}
typ := int(c>>4) & 7
size := int64(c & 15)
for shift := 4; c&0x80 != 0; shift += 7 {
if shift > 56 {
return nil, errors.New("pack entry size overflows")
}
if c, err = cr.ReadByte(); err != nil {
return nil, err
}
size |= int64(c&0x7f) << shift
}
e := &entries[i]
switch typ {
case 1, 2, 3, 4:
e.kind = Kind(typ)
case packOfsDelta:
if c, err = cr.ReadByte(); err != nil {
return nil, err
}
rel := int64(c & 0x7f)
for c&0x80 != 0 {
if rel > 1<<48 {
return nil, errors.New("ofs delta offset overflows")
}
if c, err = cr.ReadByte(); err != nil {
return nil, err
}
rel = (rel+1)<<7 | int64(c&0x7f)
}
e.baseOff = off - rel
if rel == 0 || e.baseOff < 0 {
return nil, errors.New("bad ofs delta offset")
}
case packRefDelta:
raw := make([]byte, hashLen)
if _, err := io.ReadFull(cr, raw); err != nil {
return nil, err
}
e.baseOid = Oid(hex.EncodeToString(raw))
default:
return nil, fmt.Errorf("bad pack entry type %d", typ)
}
if size > budget {
return nil, fmt.Errorf("%w: inflated objects", ErrTooLarge)
}
budget -= size
if e.data, err = inflate(cr, size); err != nil {
return nil, err
}
}
objs := make(Objects, count)
oidAt := make(map[int]Oid, count)
for i, e := range entries {
if e.kind != 0 {
oid := hashObject(e.kind, e.data, objectFormat)
objs[oid] = Object{e.kind, e.data}
oidAt[i] = oid
}
}
// ofs bases precede their deltas, so one pass in pack order resolves
// ofs chains; extra passes only for ref deltas pointing forward
for progress := true; progress; {
progress = false
for i := range entries {
e := &entries[i]
if e.kind != 0 {
continue
}
var base Object
if e.baseOid != "" {
var ok bool
if base, ok = objs[e.baseOid]; !ok {
continue
}
} else {
j, ok := byOff[e.baseOff]
if !ok {
return nil, errors.New("ofs delta base isn't an entry")
}
if entries[j].kind == 0 {
continue
}
base = Object{entries[j].kind, entries[j].data}
}
data, err := applyDelta(base.Data, e.data)
if err != nil {
return nil, err
}
if budget -= int64(len(data)); budget < 0 {
return nil, fmt.Errorf("%w: inflated objects", ErrTooLarge)
}
e.kind, e.data = base.Kind, data
oid := hashObject(e.kind, e.data, objectFormat)
objs[oid] = Object{e.kind, e.data}
oidAt[i] = oid
progress = true
}
}
if len(oidAt) != len(entries) {
return nil, errors.New("pack has deltas with missing bases")
}
return objs, nil
}
func inflate(r *countingReader, size int64) ([]byte, error) {
zr, err := zlib.NewReader(r)
if err != nil {
return nil, fmt.Errorf("pack entry: %w", err)
}
// reading to EOF also checks the adler32 trailer
data, err := io.ReadAll(io.LimitReader(zr, size+1))
if err != nil {
return nil, fmt.Errorf("pack entry: %w", err)
}
if int64(len(data)) != size {
return nil, errors.New("pack entry size mismatch")
}
return data, nil
}
func deltaSize(d []byte) (int64, []byte, error) {
var n int64
for shift := 0; ; shift += 7 {
if len(d) == 0 || shift > 56 {
return 0, nil, errors.New("bad delta header")
}
c := d[0]
d = d[1:]
n |= int64(c&0x7f) << shift
if c&0x80 == 0 {
return n, d, nil
}
}
}
func applyDelta(base, delta []byte) ([]byte, error) {
srcSize, delta, err := deltaSize(delta)
if err != nil {
return nil, err
}
if srcSize != int64(len(base)) {
return nil, errors.New("delta base size mismatch")
}
dstSize, delta, err := deltaSize(delta)
if err != nil {
return nil, err
}
if dstSize > maxInflated {
return nil, fmt.Errorf("%w: delta result", ErrTooLarge)
}
out := make([]byte, 0, dstSize)
for len(delta) > 0 {
op := delta[0]
delta = delta[1:]
switch {
case op&0x80 != 0:
var off, n int64
for bit := range 7 {
if op&(1<<bit) == 0 {
continue
}
if len(delta) == 0 {
return nil, errors.New("truncated delta copy")
}
if bit < 4 {
off |= int64(delta[0]) << (8 * bit)
} else {
n |= int64(delta[0]) << (8 * (bit - 4))
}
delta = delta[1:]
}
if n == 0 {
n = 0x10000
}
if off+n > int64(len(base)) || int64(len(out))+n > dstSize {
return nil, errors.New("delta copy out of bounds")
}
out = append(out, base[off:off+n]...)
case op != 0:
if int(op) > len(delta) || int64(len(out))+int64(op) > dstSize {
return nil, errors.New("delta insert out of bounds")
}
out = append(out, delta[:op]...)
delta = delta[op:]
default:
return nil, errors.New("delta opcode 0")
}
}
if int64(len(out)) != dstSize {
return nil, errors.New("delta result size mismatch")
}
return out, nil
}
func newHash(objectFormat string) hash.Hash {
if objectFormat == "sha256" {
return sha256.New()
}
return sha1.New()
}
// hex length
func oidLen(objectFormat string) int {
return newHash(objectFormat).Size() * 2
}
func hashObject(kind Kind, data []byte, objectFormat string) Oid {
h := newHash(objectFormat)
h.Write([]byte(kindNames[kind] + " " + strconv.Itoa(len(data)) + "\x00"))
h.Write(data)
return Oid(hex.EncodeToString(h.Sum(nil)))
}
type treeEntry struct {
Mode string
Name string
Oid Oid
}
func parseTree(data []byte, objectFormat string) ([]treeEntry, error) {
hashLen := oidLen(objectFormat) / 2
var entries []treeEntry
for len(data) > 0 {
mode, rest, ok := bytes.Cut(data, []byte(" "))
if !ok {
return nil, errors.New("bad tree entry")
}
name, rest, ok := bytes.Cut(rest, []byte{0})
if !ok || len(rest) < hashLen {
return nil, errors.New("bad tree entry")
}
entries = append(entries, treeEntry{
Mode: string(mode),
Name: string(name),
Oid: Oid(hex.EncodeToString(rest[:hashLen])),
})
data = rest[hashLen:]
}
return entries, nil
}
func commitTree(data []byte) (Oid, error) {
line, _, _ := bytes.Cut(data, []byte("\n"))
tree, ok := bytes.CutPrefix(line, []byte("tree "))
if !ok || !isOid(string(tree)) {
return "", errors.New("commit has no tree line")
}
return Oid(tree), nil
}
func isOid(s string) bool {
if len(s) != 40 && len(s) != 64 {
return false
}
for _, c := range s {
if !('0' <= c && c <= '9' || 'a' <= c && c <= 'f') {
return false
}
}
return true
}