Skip to content

Git designed for AI agents.

15.4 KB
Raw Blame
package reftable

import (
	"bytes"
	"encoding/binary"
	"encoding/hex"
	"errors"
	"fmt"
	"hash/crc32"
	"io"
	"math/big"
	"os"
	"path/filepath"
	"regexp"
	"strconv"
	"strings"

	"github.com/feder-cr/git-ai/internal/git"
)

var (
	// magic is the magic value of a reftable header.
	magic = [...]byte{'R', 'E', 'F', 'T'}
	// hashIDSHA1 denotes this reftable uses SHA1.
	hashIDSHA1 = [...]byte{'s', 'h', 'a', '1'}
	// hashIDSHA256 denotes this reftable uses SHA256.
	hashIDSHA256 = [...]byte{'s', '2', '5', '6'}
)

// version represents a reftable version.
type version uint8

// HeaderSize returns the size of the header for this reftable version.
func (v version) HeaderSize() int {
	switch v {
	case 1:
		// The Size is documented at https://git-scm.com/docs/reftable#_header_version_1
		return 24
	case 2:
		// The size  is documented at https://git-scm.com/docs/reftable#_header_version_2
		return 28
	default:
		panic(fmt.Errorf("unsupported version: %d", v))
	}
}

// FooterSize returns the size of the footer for this reftable version.
func (v version) FooterSize() int {
	// The footer sizes are documented at https://git-scm.com/docs/reftable#_footer.
	switch v {
	case 1:
		return 68
	case 2:
		return 72
	default:
		panic(fmt.Errorf("unsupported version: %d", v))
	}
}

// headerV1 is the exact byte layout of a header in reftable version 1.
type headerV1 struct {
	Magic          [4]byte
	Version        version
	BlockSize      [3]byte
	MinUpdateIndex uint64
	MaxUpdateIndex uint64
}

// header is exact byte layout of a header in reftable version 2.
type header struct {
	headerV1
	// HashID is only present if version is 2
	HashID [4]byte
}

// parseHeader parses the header of a reftable. reader should be at the beginning
// of the header.
func parseHeader(reader io.Reader, hdr *header) error {
	if err := binary.Read(reader, binary.BigEndian, &hdr.headerV1); err != nil {
		return fmt.Errorf("reading header: %w", err)
	}

	if hdr.Magic != magic {
		return fmt.Errorf("unexpected magic bytes: %q", hdr.Magic)
	}

	if !(hdr.Version == 1 || hdr.Version == 2) {
		return fmt.Errorf("unsupported version: %d", hdr.Version)
	}

	if hdr.Version == 2 {
		if err := binary.Read(reader, binary.BigEndian, &hdr.HashID); err != nil {
			return fmt.Errorf("read hash id: %w", err)
		}

		if !(hdr.HashID == hashIDSHA1 || hdr.HashID == hashIDSHA256) {
			return fmt.Errorf("unsupported hash id: %q", hdr.HashID)
		}
	}

	return nil
}

// footerEnd is the exact byte layout of the unique fields in the footer after the duplicated header.
type footerEnd struct {
	RefIndexOffset     uint64
	ObjectOffsetAndLen uint64
	ObjectIndexOffset  uint64
	LogOffset          uint64
	LogIndexPosition   uint64
	CRC32              uint32
}

// footer is the exact byte layout of a footer in a reftable.
type footer struct {
	header
	footerEnd
}

// parseFooter parses the footer of a reftable. reader should be at the beginning
// of the footer.
func parseFooter(reader io.Reader, f *footer) error {
	footerBytes, err := io.ReadAll(reader)
	if err != nil {
		return fmt.Errorf("read all: %w", err)
	}

	footerReader := bytes.NewReader(footerBytes)
	if err := parseHeader(footerReader, &f.header); err != nil {
		return fmt.Errorf("parse header: %w", err)
	}

	if err := binary.Read(footerReader, binary.BigEndian, &f.footerEnd); err != nil {
		return fmt.Errorf("parse remainder: %w", err)
	}

	if crc32.ChecksumIEEE(footerBytes[:len(footerBytes)-binary.Size(f.CRC32)]) != f.CRC32 {
		return errors.New("checksum mismatch")
	}

	return nil
}

type block struct {
	BlockStart    uint
	FullBlockSize uint
	HeaderOffset  uint
	RestartCount  uint16
	RestartStart  uint
}

// Table represents .ref table file.
type Table struct {
	blockSize    uint
	footerOffset uint
	src          *os.File
	absolutePath string
	footer       footer
}

// MinUpdateIndex is the minimum update index in the table.
func (t *Table) MinUpdateIndex() uint64 {
	return t.footer.MinUpdateIndex
}

// MaxUpdateIndex is the maximum update index in the table.
func (t *Table) MaxUpdateIndex() uint64 {
	return t.footer.MaxUpdateIndex
}

// shaFormat maps reftable sha format to Gitaly's hash object.
func (t *Table) shaFormat() git.ObjectHash {
	if t.footer.Version == 2 && t.footer.HashID == hashIDSHA256 {
		return git.ObjectHashSHA256
	}
	return git.ObjectHashSHA1
}

// parseUInt24 parses a big endian encoded uint24 into a uint.
func parseUint24(data [3]byte) uint {
	return uint(data[2]) | uint(data[1])<<8 | uint(data[0])<<16
}

// getBlockRange provides the abs block range if the block is smaller
// than the table.
func (t *Table) getBlockRange(offset, size uint) (uint, uint) {
	if offset >= t.footerOffset {
		return 0, 0
	}

	if offset+size > t.footerOffset {
		size = t.footerOffset - offset
	}

	return offset, offset + size
}

// extractBlockLen extracts the block length from a given location.
func (t *Table) extractBlockLen(src []byte, blockStart uint) uint {
	return uint(big.NewInt(0).SetBytes(src[blockStart+1 : blockStart+4]).Uint64())
}

// getVarInt parses a variable int and increases the index.
func (t *Table) getVarInt(src []byte, start uint, blockEnd uint) (uint, uint, error) {
	var val uint

	val = uint(src[start]) & 0x7f

	for (uint(src[start]) & 0x80) > 0 {
		start++
		if start > blockEnd {
			return 0, 0, fmt.Errorf("exceeded block length")
		}

		val = ((val + 1) << 7) | (uint(src[start]) & 0x7f)
	}

	return start + 1, val, nil
}

// getRefsFromBlock provides the ref udpates from a reference block.
func (t *Table) getRefsFromBlock(src []byte, b *block) ([]git.Reference, error) {
	var references []git.Reference

	prefix := ""

	// Skip the block_type and block_len
	idx := b.BlockStart + 4

	for idx < b.RestartStart {
		var prefixLength, suffixLength, updateIndexDelta uint
		var err error

		idx, prefixLength, err = t.getVarInt(src, idx, b.RestartStart)
		if err != nil {
			return nil, fmt.Errorf("getting prefix length: %w", err)
		}

		idx, suffixLength, err = t.getVarInt(src, idx, b.RestartStart)
		if err != nil {
			return nil, fmt.Errorf("getting suffix length: %w", err)
		}

		extra := (suffixLength & 0x7)
		suffixLength >>= 3

		refname := prefix[:prefixLength] + string(src[idx:idx+suffixLength])
		idx = idx + suffixLength

		idx, updateIndexDelta, err = t.getVarInt(src, idx, b.FullBlockSize)
		if err != nil {
			return nil, fmt.Errorf("getting update index delta: %w", err)
		}
		// we don't use this for now
		_ = updateIndexDelta

		reference := git.Reference{
			Name: git.ReferenceName(refname),
		}

		switch extra {
		case 0:
			// Deletion, no value
			reference.Target = t.shaFormat().ZeroOID.String()
		case 1:
			// Regular reference
			hashSize := t.shaFormat().Hash().Size()
			reference.Target = git.ObjectID(hex.EncodeToString(src[idx : idx+uint(hashSize)])).String()

			idx += uint(hashSize)
		case 2:
			// Peeled Tag
			hashSize := t.shaFormat().Hash().Size()
			reference.Target = git.ObjectID(hex.EncodeToString(src[idx : idx+uint(hashSize)])).String()

			idx += uint(hashSize)

			// For now we don't need the peeledOID, but we still need
			// to skip the index.
			// peeledOID := ObjectID(bytesToHex(t.src[idx : idx+uint(hashSize)]))
			idx += uint(hashSize)
		case 3:
			// Symref
			var size uint
			idx, size, err = t.getVarInt(src, idx, b.FullBlockSize)
			if err != nil {
				return nil, fmt.Errorf("getting symref size: %w", err)
			}

			reference.Target = git.ReferenceName(src[idx : idx+size]).String()
			reference.IsSymbolic = true
			idx = idx + size
		}

		prefix = refname

		references = append(references, reference)
	}

	return references, nil
}

// parseRefBlock parses a block and if it is a ref block, provides
// all the reference updates.
func (t *Table) parseRefBlock(src []byte, headerOffset, blockStart, blockEnd uint) ([]git.Reference, error) {
	currentBS := t.extractBlockLen(src, blockStart+headerOffset)

	fullBlockSize := t.blockSize
	if fullBlockSize == 0 {
		fullBlockSize = currentBS
	} else if currentBS < fullBlockSize && currentBS < (blockEnd-blockStart) && src[blockStart+currentBS] != 0 {
		fullBlockSize = currentBS
	}

	b := &block{
		BlockStart:    blockStart + headerOffset,
		FullBlockSize: fullBlockSize,
	}

	if err := binary.Read(bytes.NewBuffer(src[blockStart+currentBS-2:]), binary.BigEndian, &b.RestartCount); err != nil {
		return nil, fmt.Errorf("reading restart count: %w", err)
	}

	b.RestartStart = blockStart + currentBS - 2 - 3*uint(b.RestartCount)

	return t.getRefsFromBlock(src, b)
}

// GetReferences returns all references from the table.
func (t *Table) GetReferences() ([]git.Reference, error) {
	headerOffset := uint(t.footer.Version.HeaderSize())
	offset := uint(0)
	var allRefs []git.Reference

	if _, err := t.src.Seek(0, io.SeekStart); err != nil {
		return nil, fmt.Errorf("seek start: %w", err)
	}

	src, err := io.ReadAll(t.src)
	if err != nil {
		return nil, fmt.Errorf("read all: %w", err)
	}

	for offset < t.footerOffset {
		blockStart, blockEnd := t.getBlockRange(offset, t.blockSize)
		if blockStart == 0 && blockEnd == 0 {
			break
		}

		// If we run out of ref blocks, we can stop the iteration.
		if src[blockStart+headerOffset] != 'r' {
			return allRefs, nil
		}

		references, err := t.parseRefBlock(src, headerOffset, blockStart, blockEnd)
		if err != nil {
			return nil, fmt.Errorf("parsing block: %w", err)
		}

		if len(references) == 0 {
			break
		}

		allRefs = append(allRefs, references...)

		offset = blockEnd
	}

	return allRefs, nil
}

// PatchUpdateIndexes patches in-place the update indexes stored in the table's
// header and footer, and syncs the file to the disk.
func (t *Table) PatchUpdateIndexes(min, max uint64) (returnedErr error) {
	// Table typically opens the file with read-only permissions. The update index
	// patching is an exception, and the only case when we should be modifying tables.
	// Typically the table files would not be modified, and the files in the storage
	// are read-only to prevent accidental modifications. Due to the default read-only
	// permissions, we'd fail to open most of the files in the storage for writes.
	//
	// Open a separate descriptor with write permissions to handle this special case
	// of patching update indexes.
	file, err := os.OpenFile(t.absolutePath, os.O_RDWR, 0)
	if err != nil {
		return fmt.Errorf("open file: %w", err)
	}

	defer func() {
		if err := file.Close(); err != nil {
			returnedErr = errors.Join(err, fmt.Errorf("close: %w", err))
		}
	}()

	t.footer.headerV1.MinUpdateIndex = min
	t.footer.headerV1.MaxUpdateIndex = max

	// Construct a buffer that contains the full footer with patched values.
	//
	// The footer contains the header as well. First serialize the header.
	buffer := bytes.NewBuffer(make([]byte, 0, t.footer.Version.FooterSize()))
	if err := binary.Write(buffer, binary.BigEndian, t.footer.headerV1); err != nil {
		return fmt.Errorf("write header: %w", err)
	}

	// Only the version two header contains the HashID.
	if t.footer.header.Version == 2 {
		if err := binary.Write(buffer, binary.BigEndian, t.footer.HashID); err != nil {
			return fmt.Errorf("write hash ID: %w", err)
		}
	}

	// After the header, serialize the remaining footer values. This will also serialize
	// the old CRC32 into the footer, but we'll patch it below.
	if err := binary.Write(buffer, binary.BigEndian, t.footer.footerEnd); err != nil {
		return fmt.Errorf("write footer: %w", err)
	}

	// The footer ends with a CRC32 that covers everything in the footer except the checksum
	// itself. Compute the checksum and override the old value that was written above when
	// we serialized the footer with the patched update indexes.
	footerWithoutChecksum := buffer.Bytes()[:buffer.Len()-crc32.Size]
	t.footer.CRC32 = crc32.ChecksumIEEE(footerWithoutChecksum)

	footerBytes := binary.BigEndian.AppendUint32(footerWithoutChecksum, t.footer.CRC32)

	// Finally, write the updated header and footer into the file.
	if _, err := file.WriteAt(footerBytes[:t.footer.Version.HeaderSize()], 0); err != nil {
		return fmt.Errorf("patch header: %w", err)
	}

	if _, err := file.WriteAt(footerBytes, int64(t.footerOffset)); err != nil {
		return fmt.Errorf("patch footer: %w", err)
	}

	if err := file.Sync(); err != nil {
		return fmt.Errorf("sync: %w", err)
	}

	return nil
}

// Close closes the table's associated file.
func (t *Table) Close() error {
	return t.src.Close()
}

// ParseTable opens the table at the given path and parses it. Close must be called
// once the table is no longer used to close the associated file.
func ParseTable(absolutePath string) (_ *Table, returnedErr error) {
	src, err := os.Open(absolutePath)
	if err != nil {
		return nil, fmt.Errorf("open: %w", err)
	}

	defer func() {
		if returnedErr != nil {
			if err := src.Close(); err != nil {
				returnedErr = errors.Join(returnedErr, fmt.Errorf("close: %w", err))
			}
		}
	}()

	t := &Table{src: src, absolutePath: absolutePath}

	var h header
	if err := parseHeader(src, &h); err != nil {
		return nil, fmt.Errorf("parse header: %w", err)
	}

	footerOffset, err := src.Seek(int64(-h.Version.FooterSize()), io.SeekEnd)
	if err != nil {
		return nil, fmt.Errorf("seek footer: %w", err)
	}

	t.footerOffset = uint(footerOffset)

	if err := parseFooter(src, &t.footer); err != nil {
		return nil, fmt.Errorf("parse footer: %w", err)
	}

	if h != t.footer.header {
		return nil, fmt.Errorf("footer doesn't match header")
	}

	t.blockSize = parseUint24(t.footer.BlockSize)

	return t, nil
}

// ReadTablesList returns a list of tables in the "tables.list" for the
// reftable backend.
func ReadTablesList(repoPath string) ([]Name, error) {
	tablesListPath := filepath.Join(repoPath, "reftable", "tables.list")

	data, err := os.ReadFile(tablesListPath)
	if err != nil {
		return nil, fmt.Errorf("reading tables.list: %w", err)
	}

	lines := strings.Split(strings.TrimRight(string(data), "\n"), "\n")
	names := make([]Name, len(lines))
	for i, line := range lines {
		if names[i], err = ParseName(line); err != nil {
			return nil, fmt.Errorf("parse name: %w", err)
		}
	}

	return names, nil
}

// Name contains the structured information in the name of a .ref file.
type Name struct {
	// MinUpdateIndex is the minimum update index contained in the file.
	MinUpdateIndex uint64
	// MinUpdateIndex is the maximum update index contained in the file.
	MaxUpdateIndex uint64
	// Suffix is the random suffix in the table's name.
	Suffix string
}

// String returns the string representation of the reftable name.
func (n Name) String() string {
	return fmt.Sprintf("0x%012x-0x%012x-%s.ref", n.MinUpdateIndex, n.MaxUpdateIndex, n.Suffix)
}

// nameRegex is a regex for matching reftable names
// e.g. 0x000000000001-0x00000000000a-b54f3b59.ref would result in the following submatches:
//   - 000000000001 (UpdateIndexMin)
//   - 00000000000a (UpdateIndexMax)
//   - b54f3b59     (Suffix)
//
// See the reftable documentation at https://www.git-scm.com/docs/reftable#_layout for more
// information.
var nameRegex = regexp.MustCompile("^0x([[:xdigit:]]{12,16})-0x([[:xdigit:]]{12,16})-([0-9a-zA-Z]{8}).ref$")

// ParseName parses the name of a reftable file.
func ParseName(reftableName string) (Name, error) {
	matches := nameRegex.FindStringSubmatch(reftableName)
	if len(matches) == 0 {
		return Name{}, fmt.Errorf("reftable name %q malformed", reftableName)
	}

	minIndex, err := strconv.ParseUint(matches[1], 16, 64)
	if err != nil {
		return Name{}, fmt.Errorf("parsing min index: %w", err)
	}

	maxIndex, err := strconv.ParseUint(matches[2], 16, 64)
	if err != nil {
		return Name{}, fmt.Errorf("parsing max index: %w", err)
	}

	return Name{
		MinUpdateIndex: minIndex,
		MaxUpdateIndex: maxIndex,
		Suffix:         matches[3],
	}, nil
}