Something went wrong. Try again.
Monorepo for Tangled tangled.org
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366package 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 streamtype 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 forfunc 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 lengthfunc 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}