path: root/commitgraph_read.go

package furgit

import (
	"bufio"
	"bytes"
	"encoding/binary"
	"errors"
	"fmt"
	"os"
	"path/filepath"
	"strings"
	"sync"
	"syscall"

	"codeberg.org/lindenii/furgit/internal/bloom"
)

const (
	commitGraphSignature = 0x43475048 // "CGPH"
	commitGraphVersion   = 1
)

const (
	commitGraphChunkOIDF = 0x4f494446 // "OIDF"
	commitGraphChunkOIDL = 0x4f49444c // "OIDL"
	commitGraphChunkCDAT = 0x43444154 // "CDAT"
	commitGraphChunkGDA2 = 0x47444132 // "GDA2"
	commitGraphChunkGDO2 = 0x47444f32 // "GDO2"
	commitGraphChunkEDGE = 0x45444745 // "EDGE"
	commitGraphChunkBIDX = 0x42494458 // "BIDX"
	commitGraphChunkBDAT = 0x42444154 // "BDAT"
	commitGraphChunkBASE = 0x42415345 // "BASE"
)

const (
	commitGraphHeaderSize     = 8
	commitGraphChunkEntrySize = 12
	commitGraphFanoutSize     = 256 * 4
)

type commitGraph struct {
	repo *Repository

	filename string
	data     []byte
	dataLen  int

	numChunks uint8
	numBase   uint8
	hashAlgo  hashAlgorithm

	numCommits       uint32
	numCommitsInBase uint32

	base *commitGraph

	chunkOIDFanout []byte
	chunkOIDLookup []byte
	chunkCommit    []byte

	chunkGeneration   []byte
	chunkGenerationOv []byte
	readGeneration    bool

	chunkExtraEdges []byte

	chunkBloomIndex []byte
	chunkBloomData  []byte

	chunkBaseGraphs []byte

	bloomSettings *bloom.Settings

	closeOnce sync.Once
}

func (cg *commitGraph) Close() error {
	if cg == nil {
		return nil
	}
	var closeErr error
	cg.closeOnce.Do(func() {
		if len(cg.data) > 0 {
			if err := syscall.Munmap(cg.data); closeErr == nil {
				closeErr = err
			}
			cg.data = nil
		}
	})
	if cg.base != nil {
		_ = cg.base.Close()
	}
	return closeErr
}

func (repo *Repository) CommitGraph() (*commitGraph, error) {
	if repo == nil {
		return nil, ErrInvalidObject
	}
	repo.commitGraphOnce.Do(func() {
		repo.commitGraph, repo.commitGraphErr = repo.loadCommitGraph()
	})
	return repo.commitGraph, repo.commitGraphErr
}

func (repo *Repository) loadCommitGraph() (*commitGraph, error) {
	cg, err := repo.loadCommitGraphSingle()
	if err == nil {
		return cg, nil
	}
	if !errors.Is(err, ErrNotFound) {
		return nil, err
	}
	return repo.loadCommitGraphChain()
}

func (repo *Repository) loadCommitGraphSingle() (*commitGraph, error) {
	path := repo.repoPath(filepath.Join("objects", "info", "commit-graph"))
	return repo.loadCommitGraphFile(path)
}

func (repo *Repository) loadCommitGraphChain() (*commitGraph, error) {
	chainPath := repo.repoPath(filepath.Join("objects", "info", "commit-graphs", "commit-graph-chain"))
	f, err := os.Open(chainPath)
	if err != nil {
		if os.IsNotExist(err) {
			return nil, ErrNotFound
		}
		return nil, err
	}
	defer func() { _ = f.Close() }()

	var hashes []string
	scanner := bufio.NewScanner(f)
	for scanner.Scan() {
		line := strings.TrimSpace(scanner.Text())
		if line == "" {
			continue
		}
		hashes = append(hashes, line)
	}
	if err := scanner.Err(); err != nil {
		return nil, err
	}
	if len(hashes) == 0 {
		return nil, ErrNotFound
	}

	var chain *commitGraph
	for i, h := range hashes {
		graphPath := repo.repoPath(filepath.Join("objects", "info", "commit-graphs", fmt.Sprintf("graph-%s.graph", h)))
		g, err := repo.loadCommitGraphFile(graphPath)
		if err != nil {
			return nil, err
		}
		if i > 0 {
			if g.chunkBaseGraphs == nil {
				return nil, ErrInvalidObject
			}
			if len(g.chunkBaseGraphs) < i*repo.hashAlgo.Size() {
				return nil, ErrInvalidObject
			}
			for j := 0; j < i; j++ {
				want := hashes[j]
				start := j * repo.hashAlgo.Size()
				end := start + repo.hashAlgo.Size()
				got := hexEncode(g.chunkBaseGraphs[start:end])
				if got != want {
					return nil, ErrInvalidObject
				}
			}
		}
		if chain != nil {
			if chain.numCommits+chain.numCommitsInBase > ^uint32(0) {
				return nil, ErrInvalidObject
			}
			g.numCommitsInBase = chain.numCommits + chain.numCommitsInBase
		}
		g.base = chain
		chain = g
	}
	validateCommitGraphChain(chain)
	return chain, nil
}

func validateCommitGraphChain(head *commitGraph) {
	if head == nil {
		return
	}
	readGeneration := true
	for g := head; g != nil; g = g.base {
		readGeneration = readGeneration && g.readGeneration
	}
	if !readGeneration {
		for g := head; g != nil; g = g.base {
			g.readGeneration = false
		}
	}

	var settings *bloom.Settings
	for g := head; g != nil; g = g.base {
		if g.bloomSettings == nil {
			continue
		}
		if settings == nil {
			settings = g.bloomSettings
			continue
		}
		if settings.HashVersion != g.bloomSettings.HashVersion ||
			settings.NumHashes != g.bloomSettings.NumHashes ||
			settings.BitsPerEntry != g.bloomSettings.BitsPerEntry {
			g.chunkBloomIndex = nil
			g.chunkBloomData = nil
			g.bloomSettings = nil
		}
	}
}

func (repo *Repository) loadCommitGraphFile(path string) (*commitGraph, error) {
	f, err := os.Open(path)
	if err != nil {
		if os.IsNotExist(err) {
			return nil, ErrNotFound
		}
		return nil, err
	}
	stat, err := f.Stat()
	if err != nil {
		_ = f.Close()
		return nil, err
	}
	if stat.Size() < int64(commitGraphHeaderSize+commitGraphFanoutSize) {
		_ = f.Close()
		return nil, ErrInvalidObject
	}
	region, err := syscall.Mmap(
		int(f.Fd()),
		0,
		int(stat.Size()),
		syscall.PROT_READ,
		syscall.MAP_PRIVATE,
	)
	if err != nil {
		_ = f.Close()
		return nil, err
	}
	err = f.Close()
	if err != nil {
		_ = syscall.Munmap(region)
		return nil, err
	}
	cg, err := parseCommitGraph(repo, path, region)
	if err != nil {
		_ = syscall.Munmap(region)
		return nil, err
	}
	cg.data = region
	return cg, nil
}

func parseCommitGraph(repo *Repository, filename string, data []byte) (*commitGraph, error) {
	if len(data) < commitGraphHeaderSize {
		return nil, ErrInvalidObject
	}
	sig := binary.BigEndian.Uint32(data[0:4])
	if sig != commitGraphSignature {
		return nil, ErrInvalidObject
	}
	version := data[4]
	if version != commitGraphVersion {
		return nil, ErrInvalidObject
	}
	hashVersion := data[5]
	if hashVersion != hashAlgoVersion(repo.hashAlgo) {
		return nil, ErrInvalidObject
	}
	numChunks := data[6]
	numBase := data[7]

	tocStart := commitGraphHeaderSize
	tocLen := (int(numChunks) + 1) * commitGraphChunkEntrySize
	if len(data) < tocStart+tocLen+repo.hashAlgo.Size() {
		return nil, ErrInvalidObject
	}

	trailerStart := len(data) - repo.hashAlgo.Size()

	type chunkEntry struct {
		id     uint32
		offset uint64
	}
	entries := make([]chunkEntry, 0, numChunks+1)
	for i := 0; i < int(numChunks)+1; i++ {
		pos := tocStart + i*commitGraphChunkEntrySize
		id := binary.BigEndian.Uint32(data[pos : pos+4])
		offset := binary.BigEndian.Uint64(data[pos+4 : pos+12])
		entries = append(entries, chunkEntry{id: id, offset: offset})
	}

	chunks := map[uint32][]byte{}
	for i := 0; i < len(entries)-1; i++ {
		id := entries[i].id
		if id == 0 {
			break
		}
		start := int(entries[i].offset)
		end := int(entries[i+1].offset)
		if start < tocStart+tocLen || end < start || end > trailerStart {
			return nil, ErrInvalidObject
		}
		chunks[id] = data[start:end]
	}

	cg := &commitGraph{
		repo:      repo,
		filename:  filename,
		dataLen:   len(data),
		hashAlgo:  repo.hashAlgo,
		numChunks: numChunks,
		numBase:   numBase,
	}

	oidf := chunks[commitGraphChunkOIDF]
	if len(oidf) != commitGraphFanoutSize {
		return nil, ErrInvalidObject
	}
	cg.chunkOIDFanout = oidf
	cg.numCommits = binary.BigEndian.Uint32(oidf[len(oidf)-4:])
	for i := 0; i < 255; i++ {
		if binary.BigEndian.Uint32(oidf[i*4:(i+1)*4]) >
			binary.BigEndian.Uint32(oidf[(i+1)*4:(i+2)*4]) {
			return nil, ErrInvalidObject
		}
	}

	oidl := chunks[commitGraphChunkOIDL]
	if len(oidl) != int(cg.numCommits)*repo.hashAlgo.Size() {
		return nil, ErrInvalidObject
	}
	cg.chunkOIDLookup = oidl

	cdat := chunks[commitGraphChunkCDAT]
	if len(cdat) != int(cg.numCommits)*commitGraphCommitDataSize(repo.hashAlgo) {
		return nil, ErrInvalidObject
	}
	cg.chunkCommit = cdat

	if gda2 := chunks[commitGraphChunkGDA2]; len(gda2) != 0 {
		if len(gda2) != int(cg.numCommits)*4 {
			return nil, ErrInvalidObject
		}
		cg.chunkGeneration = gda2
		cg.readGeneration = true
	}
	if gdo2 := chunks[commitGraphChunkGDO2]; len(gdo2) != 0 {
		cg.chunkGenerationOv = gdo2
	}

	if edge := chunks[commitGraphChunkEDGE]; len(edge) != 0 {
		if len(edge)%4 != 0 {
			return nil, ErrInvalidObject
		}
		cg.chunkExtraEdges = edge
	}

	if base := chunks[commitGraphChunkBASE]; len(base) != 0 {
		if numBase == 0 {
			return nil, ErrInvalidObject
		}
		if len(base) != int(numBase)*repo.hashAlgo.Size() {
			return nil, ErrInvalidObject
		}
		cg.chunkBaseGraphs = base
	} else if numBase != 0 {
		return nil, ErrInvalidObject
	}

	if bidx := chunks[commitGraphChunkBIDX]; len(bidx) != 0 {
		if len(bidx) != int(cg.numCommits)*4 {
			return nil, ErrInvalidObject
		}
		cg.chunkBloomIndex = bidx
	}
	if bdat := chunks[commitGraphChunkBDAT]; len(bdat) != 0 {
		if len(bdat) < bloom.DataHeaderSize {
			return nil, ErrInvalidObject
		}
		cg.chunkBloomData = bdat
		settings, err := bloom.ParseSettings(bdat)
		if err != nil {
			return nil, err
		}
		cg.bloomSettings = settings
	}

	if (cg.chunkBloomIndex != nil) != (cg.chunkBloomData != nil) {
		cg.chunkBloomIndex = nil
		cg.chunkBloomData = nil
		cg.bloomSettings = nil
	}
	if cg.chunkBloomIndex != nil && cg.chunkBloomData != nil {
		for i := 0; i < int(cg.numCommits); i++ {
			cur := binary.BigEndian.Uint32(cg.chunkBloomIndex[i*4 : i*4+4])
			if i > 0 {
				prev := binary.BigEndian.Uint32(cg.chunkBloomIndex[(i-1)*4 : i*4])
				if cur < prev {
					return nil, ErrInvalidObject
				}
			}
			if int(cur) > len(cg.chunkBloomData)-bloom.DataHeaderSize {
				return nil, ErrInvalidObject
			}
		}
	}

	if err := verifyCommitGraphTrailer(repo, data); err != nil {
		return nil, err
	}

	return cg, nil
}

func commitGraphCommitDataSize(algo hashAlgorithm) int {
	return algo.Size() + 16
}

func hashAlgoVersion(algo hashAlgorithm) byte {
	switch algo {
	case hashAlgoSHA1:
		return 1
	case hashAlgoSHA256:
		return 2
	default:
		return 0
	}
}

func verifyCommitGraphTrailer(repo *Repository, data []byte) error {
	if repo == nil {
		return ErrInvalidObject
	}
	hashSize := repo.hashAlgo.Size()
	if len(data) < hashSize {
		return ErrInvalidObject
	}
	want := data[len(data)-hashSize:]
	h, err := repo.hashAlgo.New()
	if err != nil {
		return err
	}
	_, _ = h.Write(data[:len(data)-hashSize])
	got := h.Sum(nil)
	if !bytes.Equal(got, want) {
		return ErrInvalidObject
	}
	return nil
}

func hexEncode(b []byte) string {
	const hex = "0123456789abcdef"
	out := make([]byte, len(b)*2)
	for i, v := range b {
		out[i*2] = hex[v>>4]
		out[i*2+1] = hex[v&0x0f]
	}
	return string(out)
}

func (cg *commitGraph) lookupOID(id Hash) (uint32, bool) {
	if cg == nil {
		return 0, false
	}
	return commitGraphBsearchOID(cg, id)
}

func commitGraphBsearchOID(cg *commitGraph, id Hash) (uint32, bool) {
	if cg == nil || len(cg.chunkOIDLookup) == 0 {
		return 0, false
	}
	hashSize := cg.hashAlgo.Size()
	first := int(id.data[0])
	fanout := cg.chunkOIDFanout
	var start uint32
	if first > 0 {
		start = binary.BigEndian.Uint32(fanout[(first-1)*4 : first*4])
	}
	end := binary.BigEndian.Uint32(fanout[first*4 : (first+1)*4])
	lo := int(start)
	hi := int(end) - 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		pos := mid * hashSize
		cmp := bytes.Compare(cg.chunkOIDLookup[pos:pos+hashSize], id.data[:hashSize])
		if cmp == 0 {
			return uint32(mid) + cg.numCommitsInBase, true
		}
		if cmp < 0 {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	if cg.base != nil {
		return commitGraphBsearchOID(cg.base, id)
	}
	return 0, false
}

func (cg *commitGraph) loadOID(pos uint32) (Hash, error) {
	g := cg
	for g != nil && pos < g.numCommitsInBase {
		g = g.base
	}
	if g == nil {
		return Hash{}, ErrInvalidObject
	}
	if pos >= g.numCommits+g.numCommitsInBase {
		return Hash{}, ErrInvalidObject
	}
	lex := pos - g.numCommitsInBase
	hashSize := g.hashAlgo.Size()
	start := int(lex) * hashSize
	end := start + hashSize
	var out Hash
	copy(out.data[:], g.chunkOIDLookup[start:end])
	out.algo = g.hashAlgo
	return out, nil
}

func (cg *commitGraph) commitDataAt(pos uint32) (*commitGraphCommit, error) {
	g := cg
	for g != nil && pos < g.numCommitsInBase {
		g = g.base
	}
	if g == nil {
		return nil, ErrInvalidObject
	}
	if pos >= g.numCommits+g.numCommitsInBase {
		return nil, ErrInvalidObject
	}
	lex := pos - g.numCommitsInBase
	stride := commitGraphCommitDataSize(g.hashAlgo)
	start := int(lex) * stride
	end := start + stride
	if end > len(g.chunkCommit) {
		return nil, ErrInvalidObject
	}
	buf := g.chunkCommit[start:end]

	var tree Hash
	hashSize := g.hashAlgo.Size()
	copy(tree.data[:], buf[:hashSize])
	tree.algo = g.hashAlgo

	p1 := binary.BigEndian.Uint32(buf[hashSize : hashSize+4])
	p2 := binary.BigEndian.Uint32(buf[hashSize+4 : hashSize+8])

	genTime := binary.BigEndian.Uint32(buf[hashSize+8 : hashSize+12])
	timeLow := binary.BigEndian.Uint32(buf[hashSize+12 : hashSize+16])

	timeHigh := genTime & 0x3
	commitTime := (uint64(timeHigh) << 32) | uint64(timeLow)
	generation := uint64(genTime >> 2)

	if g.readGeneration {
		genOffset := binary.BigEndian.Uint32(g.chunkGeneration[int(lex)*4:])
		if genOffset&correctedGenerationOverflow != 0 {
			off := genOffset ^ correctedGenerationOverflow
			idx := int(off) * 8
			if g.chunkGenerationOv == nil || idx+8 > len(g.chunkGenerationOv) {
				return nil, ErrInvalidObject
			}
			offset := binary.BigEndian.Uint64(g.chunkGenerationOv[idx : idx+8])
			generation = commitTime + offset
		} else {
			generation = commitTime + uint64(genOffset)
		}
	}

	var parents []uint32
	var err error
	parents, err = commitGraphAppendParent(parents, g, p1)
	if err != nil {
		return nil, err
	}
	parents, err = commitGraphAppendParent(parents, g, p2)
	if err != nil {
		return nil, err
	}

	return &commitGraphCommit{
		Position:    pos,
		Tree:        tree,
		Parents:     parents,
		CommitTime:  commitTime,
		Generation:  generation,
		Graph:       g,
		graphLexPos: lex,
	}, nil
}