format/commitgraph: Add initial commit-graph support

1 files changed, 484 insertions, 0 deletions

diff --git a/format/commitgraph/layers.go b/format/commitgraph/layers.go
new file mode 100644
index 00000000..bdab6b79
--- /dev/null
+++ b/format/commitgraph/layers.go
@@ -0,0 +1,484 @@
+package commitgraph
+
+import (
+	"bytes"
+	"encoding/binary"
+	"os"
+	"syscall"
+
+	"codeberg.org/lindenii/furgit/format/commitgraph/bloom"
+	"codeberg.org/lindenii/furgit/internal/intconv"
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// LayerInfo describes one loaded commit-graph layer.
+type LayerInfo struct {
+	Path      string
+	BaseCount uint32
+	Commits   uint32
+}
+
+type layer struct {
+	path       string
+	file       *os.File
+	data       []byte
+	numCommits uint32
+	baseCount  uint32
+	globalFrom uint32
+
+	chunkOIDFanout    []byte
+	chunkOIDLookup    []byte
+	chunkCommit       []byte
+	chunkGeneration   []byte
+	chunkGenerationOv []byte
+	chunkExtraEdges   []byte
+	chunkBloomIndex   []byte
+	chunkBloomData    []byte
+	chunkBaseGraphs   []byte
+
+	bloomSettings *bloom.Settings
+}
+
+// Layers returns loaded layer metadata in native chain order.
+func (reader *Reader) Layers() []LayerInfo {
+	out := make([]LayerInfo, 0, len(reader.layers))
+	for i := range reader.layers {
+		layer := reader.layers[i]
+		out = append(out, LayerInfo{
+			Path:      layer.path,
+			BaseCount: layer.baseCount,
+			Commits:   layer.numCommits,
+		})
+	}
+
+	return out
+}
+
+func (reader *Reader) layerByPosition(pos Position) (*layer, error) {
+	graphIdx, err := intconv.Uint64ToInt(uint64(pos.Graph))
+	if err != nil {
+		return nil, err
+	}
+
+	if graphIdx < 0 || graphIdx >= len(reader.layers) {
+		return nil, &ErrPositionOutOfRange{Pos: pos}
+	}
+
+	layer := &reader.layers[graphIdx]
+	if pos.Index >= layer.numCommits {
+		return nil, &ErrPositionOutOfRange{Pos: pos}
+	}
+
+	return layer, nil
+}
+
+func layerLookup(layer *layer, oid objectid.ObjectID) (uint32, bool) {
+	hashSize := oid.Size()
+	first := int(oid.RawBytes()[0])
+
+	var lo uint32
+	if first > 0 {
+		lo = binary.BigEndian.Uint32(layer.chunkOIDFanout[(first-1)*4 : first*4])
+	}
+
+	hi := binary.BigEndian.Uint32(layer.chunkOIDFanout[first*4 : (first+1)*4])
+	if hi == 0 || lo >= hi {
+		return 0, false
+	}
+
+	target := oid.RawBytes()
+	left := int(lo)
+
+	right := int(hi) - 1
+	for left <= right {
+		mid := left + (right-left)/2
+		start := mid * hashSize
+		end := start + hashSize
+
+		current := layer.chunkOIDLookup[start:end]
+
+		cmp := bytes.Compare(current, target)
+		switch {
+		case cmp == 0:
+			pos, err := intconv.IntToUint32(mid)
+			if err != nil {
+				return 0, false
+			}
+
+			return pos, true
+		case cmp < 0:
+			left = mid + 1
+		default:
+			right = mid - 1
+		}
+	}
+
+	return 0, false
+}
+
+func openLayer(root *os.Root, relPath string, algo objectid.Algorithm) (*layer, error) {
+	file, err := root.Open(relPath)
+	if err != nil {
+		return nil, err
+	}
+
+	info, err := file.Stat()
+	if err != nil {
+		_ = file.Close()
+
+		return nil, err
+	}
+
+	size := info.Size()
+	if size < int64(headerSize+fanoutSize+algo.Size()) {
+		_ = file.Close()
+
+		return nil, &ErrMalformed{Path: relPath, Reason: "file too short"}
+	}
+
+	mapLen, err := intconv.Int64ToUint64(size)
+	if err != nil {
+		_ = file.Close()
+
+		return nil, err
+	}
+
+	mapLenInt, err := intconv.Uint64ToInt(mapLen)
+	if err != nil {
+		_ = file.Close()
+
+		return nil, err
+	}
+
+	fd, err := intconv.UintptrToInt(file.Fd())
+	if err != nil {
+		_ = file.Close()
+
+		return nil, err
+	}
+
+	data, err := syscall.Mmap(fd, 0, mapLenInt, syscall.PROT_READ, syscall.MAP_PRIVATE)
+	if err != nil {
+		_ = file.Close()
+
+		return nil, err
+	}
+
+	out := &layer{
+		path: relPath,
+		file: file,
+		data: data,
+	}
+
+	parseErr := parseLayer(out, algo)
+	if parseErr != nil {
+		_ = out.close()
+
+		return nil, parseErr
+	}
+
+	verifyErr := verifyTrailerHash(out.data, algo, relPath)
+	if verifyErr != nil {
+		_ = out.close()
+
+		return nil, verifyErr
+	}
+
+	return out, nil
+}
+
+func parseLayer(layer *layer, algo objectid.Algorithm) error { //nolint:maintidx
+	if len(layer.data) < headerSize {
+		return &ErrMalformed{Path: layer.path, Reason: "file too short"}
+	}
+
+	header := layer.data[:headerSize]
+
+	signature := binary.BigEndian.Uint32(header[:4])
+	if signature != fileSignature {
+		return &ErrMalformed{Path: layer.path, Reason: "invalid signature"}
+	}
+
+	version := header[4]
+	if version != fileVersion {
+		return &ErrUnsupportedVersion{Version: version}
+	}
+
+	expectedHashVersion, err := intconv.Uint32ToUint8(algo.PackHashID())
+	if err != nil {
+		return err
+	}
+
+	hashVersion := header[5]
+	if hashVersion != expectedHashVersion {
+		return &ErrMalformed{Path: layer.path, Reason: "hash version does not match object format"}
+	}
+
+	numChunks := int(header[6])
+	baseCount := uint32(header[7])
+
+	tocLen := (numChunks + 1) * chunkEntrySize
+	tocStart := headerSize
+
+	tocEnd := tocStart + tocLen
+	if tocEnd > len(layer.data) {
+		return &ErrMalformed{Path: layer.path, Reason: "truncated chunk table"}
+	}
+
+	type tocEntry struct {
+		id     uint32
+		offset uint64
+	}
+
+	entries := make([]tocEntry, 0, numChunks+1)
+	for i := range numChunks + 1 {
+		entryOff := tocStart + i*chunkEntrySize
+		entryData := layer.data[entryOff : entryOff+chunkEntrySize]
+
+		entry := tocEntry{
+			id:     binary.BigEndian.Uint32(entryData[:4]),
+			offset: binary.BigEndian.Uint64(entryData[4:]),
+		}
+		entries = append(entries, entry)
+	}
+
+	if entries[len(entries)-1].id != 0 {
+		return &ErrMalformed{Path: layer.path, Reason: "missing chunk table terminator"}
+	}
+
+	trailerStart := len(layer.data) - algo.Size()
+
+	chunks := make(map[uint32][]byte, numChunks)
+	for i := range numChunks {
+		entry := entries[i]
+		if entry.id == 0 {
+			return &ErrMalformed{Path: layer.path, Reason: "early chunk table terminator"}
+		}
+
+		next := entries[i+1]
+
+		start, err := intconv.Uint64ToInt(entry.offset)
+		if err != nil {
+			return err
+		}
+
+		end, err := intconv.Uint64ToInt(next.offset)
+		if err != nil {
+			return err
+		}
+
+		if start < tocEnd || end < start || end > trailerStart {
+			return &ErrMalformed{Path: layer.path, Reason: "invalid chunk offsets"}
+		}
+
+		if _, exists := chunks[entry.id]; exists {
+			return &ErrMalformed{Path: layer.path, Reason: "duplicate chunk id"}
+		}
+
+		chunks[entry.id] = layer.data[start:end]
+	}
+
+	oidf := chunks[chunkOIDF]
+	if len(oidf) != fanoutSize {
+		return &ErrMalformed{Path: layer.path, Reason: "invalid OIDF length"}
+	}
+
+	layer.chunkOIDFanout = oidf
+	layer.numCommits = binary.BigEndian.Uint32(oidf[fanoutSize-4:])
+
+	for i := range 255 {
+		cur := binary.BigEndian.Uint32(oidf[i*4 : (i+1)*4])
+
+		next := binary.BigEndian.Uint32(oidf[(i+1)*4 : (i+2)*4])
+		if cur > next {
+			return &ErrMalformed{Path: layer.path, Reason: "non-monotonic OIDF fanout"}
+		}
+	}
+
+	hashSize := algo.Size()
+
+	hashSizeU64, err := intconv.IntToUint64(hashSize)
+	if err != nil {
+		return err
+	}
+
+	oidl := chunks[chunkOIDL]
+	oidlWantLen64 := uint64(layer.numCommits) * hashSizeU64
+
+	oidlWantLen, err := intconv.Uint64ToInt(oidlWantLen64)
+	if err != nil {
+		return err
+	}
+
+	if len(oidl) != oidlWantLen {
+		return &ErrMalformed{Path: layer.path, Reason: "invalid OIDL length"}
+	}
+
+	layer.chunkOIDLookup = oidl
+
+	stride := hashSize + 16
+
+	strideU64, err := intconv.IntToUint64(stride)
+	if err != nil {
+		return err
+	}
+
+	cdat := chunks[chunkCDAT]
+	cdatWantLen64 := uint64(layer.numCommits) * strideU64
+
+	cdatWantLen, err := intconv.Uint64ToInt(cdatWantLen64)
+	if err != nil {
+		return err
+	}
+
+	if len(cdat) != cdatWantLen {
+		return &ErrMalformed{Path: layer.path, Reason: "invalid CDAT length"}
+	}
+
+	layer.chunkCommit = cdat
+
+	gda2 := chunks[chunkGDA2]
+	if len(gda2) != 0 {
+		wantLen64 := uint64(layer.numCommits) * 4
+
+		wantLen, err := intconv.Uint64ToInt(wantLen64)
+		if err != nil {
+			return err
+		}
+
+		if len(gda2) != wantLen {
+			return &ErrMalformed{Path: layer.path, Reason: "invalid GDA2 length"}
+		}
+
+		layer.chunkGeneration = gda2
+	}
+
+	gdo2 := chunks[chunkGDO2]
+	if len(gdo2) != 0 {
+		if len(gdo2)%8 != 0 {
+			return &ErrMalformed{Path: layer.path, Reason: "invalid GDO2 length"}
+		}
+
+		layer.chunkGenerationOv = gdo2
+	}
+
+	edge := chunks[chunkEDGE]
+	if len(edge) != 0 {
+		if len(edge)%4 != 0 {
+			return &ErrMalformed{Path: layer.path, Reason: "invalid EDGE length"}
+		}
+
+		layer.chunkExtraEdges = edge
+	}
+
+	base := chunks[chunkBASE]
+	if baseCount == 0 {
+		if len(base) != 0 {
+			return &ErrMalformed{Path: layer.path, Reason: "unexpected BASE chunk"}
+		}
+	} else {
+		wantLen64 := uint64(baseCount) * hashSizeU64
+
+		wantLen, err := intconv.Uint64ToInt(wantLen64)
+		if err != nil {
+			return err
+		}
+
+		if len(base) != wantLen {
+			return &ErrMalformed{Path: layer.path, Reason: "invalid BASE length"}
+		}
+
+		layer.chunkBaseGraphs = base
+	}
+
+	layer.baseCount = baseCount
+
+	bidx := chunks[chunkBIDX]
+
+	bdat := chunks[chunkBDAT]
+	if len(bidx) != 0 || len(bdat) != 0 { //nolint:nestif
+		if len(bidx) == 0 || len(bdat) == 0 {
+			return &ErrMalformed{Path: layer.path, Reason: "BIDX/BDAT must both be present"}
+		}
+
+		bidxWantLen64 := uint64(layer.numCommits) * 4
+
+		bidxWantLen, err := intconv.Uint64ToInt(bidxWantLen64)
+		if err != nil {
+			return err
+		}
+
+		if len(bidx) != bidxWantLen {
+			return &ErrMalformed{Path: layer.path, Reason: "invalid BIDX length"}
+		}
+
+		if len(bdat) < bloom.DataHeaderSize {
+			return &ErrMalformed{Path: layer.path, Reason: "invalid BDAT length"}
+		}
+
+		settings, err := bloom.ParseSettings(bdat)
+		if err != nil {
+			return err
+		}
+
+		prev := uint32(0)
+
+		for i := range layer.numCommits {
+			off := int(i) * 4
+
+			cur := binary.BigEndian.Uint32(bidx[off : off+4])
+			if i > 0 && cur < prev {
+				return &ErrMalformed{Path: layer.path, Reason: "non-monotonic BIDX"}
+			}
+
+			bdatDataLen := len(bdat) - bloom.DataHeaderSize
+
+			bdatDataLenU32, err := intconv.IntToUint32(bdatDataLen)
+			if err != nil {
+				return err
+			}
+
+			if cur > bdatDataLenU32 {
+				return &ErrMalformed{Path: layer.path, Reason: "BIDX offset out of range"}
+			}
+
+			prev = cur
+		}
+
+		layer.chunkBloomIndex = bidx
+		layer.chunkBloomData = bdat
+		layer.bloomSettings = settings
+	}
+
+	return nil
+}
+
+func closeLayers(layers []layer) {
+	for i := len(layers) - 1; i >= 0; i-- {
+		_ = layers[i].close()
+	}
+}
+
+func (layer *layer) close() error {
+	var closeErr error
+
+	if layer.data != nil {
+		err := syscall.Munmap(layer.data)
+		if err != nil {
+			closeErr = err
+		}
+
+		layer.data = nil
+	}
+
+	if layer.file != nil {
+		err := layer.file.Close()
+		if err != nil && closeErr == nil {
+			closeErr = err
+		}
+
+		layer.file = nil
+	}
+
+	return closeErr
+}