path: root/refstore/reftable/lookup.go

package reftable

import (
	"encoding/binary"
	"fmt"
	"strings"

	"codeberg.org/lindenii/furgit/objectid"
)

// resolveRecord resolves one ref name inside a single table file.
func (table *tableFile) resolveRecord(name string) (recordValue, bool, error) {
	if table.refIndexPos != 0 {
		pos, ok, err := table.resolveRefBlockPosFromIndex(name, int(table.refIndexPos))
		if err != nil {
			return recordValue{}, false, err
		}
		if !ok {
			return recordValue{}, false, nil
		}
		return table.lookupInRefBlock(name, pos)
	}

	// Without a ref index, fall back to scanning ref blocks in order.
	pos := table.headerLen
	for pos < table.refEnd {
		for pos < table.refEnd && table.data[pos] == 0 {
			pos++
		}
		if pos >= table.refEnd {
			break
		}
		if table.data[pos] != blockTypeRef {
			return recordValue{}, false, fmt.Errorf("refstore/reftable: table %q: unexpected block type %q in ref section", table.name, table.data[pos])
		}
		block, blockEnd, err := table.readBlockAt(pos)
		if err != nil {
			return recordValue{}, false, err
		}
		found, done, rec, err := lookupRecordInRefBlock(table, block, name)
		if err != nil {
			return recordValue{}, false, err
		}
		if found {
			return rec, true, nil
		}
		if done {
			return recordValue{}, false, nil
		}
		pos = table.nextBlockPos(blockEnd)
	}
	return recordValue{}, false, nil
}

// resolveRefBlockPosFromIndex resolves a candidate ref block position via index blocks.
func (table *tableFile) resolveRefBlockPosFromIndex(name string, indexPos int) (int, bool, error) {
	block, _, err := table.readBlockAt(indexPos)
	if err != nil {
		return 0, false, err
	}
	if block.blockType != blockTypeIndex {
		return 0, false, fmt.Errorf("refstore/reftable: table %q: ref index root is not index block", table.name)
	}
	childPos, ok, err := lookupChildPosInIndexBlock(block, name)
	if err != nil {
		return 0, false, err
	}
	if !ok {
		return 0, false, nil
	}
	if childPos < 0 || childPos >= len(table.data) {
		return 0, false, fmt.Errorf("refstore/reftable: table %q: index child position out of range", table.name)
	}

	childType := table.data[childPos]
	switch childType {
	case blockTypeRef:
		return childPos, true, nil
	case blockTypeIndex:
		return table.resolveRefBlockPosFromIndex(name, childPos)
	default:
		return 0, false, fmt.Errorf("refstore/reftable: table %q: unexpected child block type %q", table.name, childType)
	}
}

// lookupInRefBlock searches one ref block by full ref name.
func (table *tableFile) lookupInRefBlock(name string, pos int) (recordValue, bool, error) {
	block, _, err := table.readBlockAt(pos)
	if err != nil {
		return recordValue{}, false, err
	}
	if block.blockType != blockTypeRef {
		return recordValue{}, false, fmt.Errorf("refstore/reftable: table %q: expected ref block at %d", table.name, pos)
	}
	found, _, rec, err := lookupRecordInRefBlock(table, block, name)
	if err != nil {
		return recordValue{}, false, err
	}
	return rec, found, nil
}

// forEachRecord iterates all ref records in this table in lexical order.
func (table *tableFile) forEachRecord(fn func(name string, rec recordValue) error) error {
	pos := table.headerLen
	prevLast := ""
	for pos < table.refEnd {
		for pos < table.refEnd && table.data[pos] == 0 {
			pos++
		}
		if pos >= table.refEnd {
			break
		}
		if table.data[pos] != blockTypeRef {
			return fmt.Errorf("refstore/reftable: table %q: unexpected block type %q in ref section", table.name, table.data[pos])
		}

		block, blockEnd, err := table.readBlockAt(pos)
		if err != nil {
			return err
		}
		var first, last string
		err = forEachRecordInRefBlock(table, block, func(name string, rec recordValue) error {
			if first == "" {
				first = name
			}
			last = name
			return fn(name, rec)
		})
		if err != nil {
			return err
		}
		if prevLast != "" && first != "" && strings.Compare(first, prevLast) <= 0 {
			return fmt.Errorf("refstore/reftable: table %q: ref blocks are not strictly ordered", table.name)
		}
		if last != "" {
			prevLast = last
		}
		pos = table.nextBlockPos(blockEnd)
	}
	return nil
}

// blockView is one decoded block boundary within the mapped table bytes.
type blockView struct {
	blockType byte
	start     int
	end       int
	first     bool
	payload   []byte
}

// readBlockAt validates and returns a block view starting at pos.
func (table *tableFile) readBlockAt(pos int) (blockView, int, error) {
	if pos < 0 || pos+4 > len(table.data) {
		return blockView{}, 0, fmt.Errorf("refstore/reftable: table %q: block header out of range", table.name)
	}
	blockLen := int(readUint24(table.data[pos+1 : pos+4]))
	effectiveLen := blockLen
	if pos == table.headerLen {
		if blockLen < table.headerLen {
			return blockView{}, 0, fmt.Errorf("refstore/reftable: table %q: invalid first block length", table.name)
		}
		effectiveLen = blockLen - table.headerLen
	}
	if effectiveLen < 4 {
		return blockView{}, 0, fmt.Errorf("refstore/reftable: table %q: invalid block length", table.name)
	}
	end := pos + effectiveLen
	if end > len(table.data) {
		return blockView{}, 0, fmt.Errorf("refstore/reftable: table %q: block out of range", table.name)
	}
	view := blockView{blockType: table.data[pos], start: pos, end: end, first: pos == table.headerLen, payload: table.data[pos:end]}
	return view, end, nil
}

// nextBlockPos computes the next block start from current block end.
func (table *tableFile) nextBlockPos(blockEnd int) int {
	if table.blockSize > 0 {
		return alignUp(blockEnd, table.blockSize)
	}
	return blockEnd
}

// lookupChildPosInIndexBlock selects a child block position for key.
func lookupChildPosInIndexBlock(block blockView, key string) (int, bool, error) {
	off, recordsEnd, restarts, err := parseBlockLayout(block)
	if err != nil {
		return 0, false, err
	}
	if err := validateRestarts(block, restarts, off, recordsEnd, true); err != nil {
		return 0, false, err
	}
	prev := ""
	for off < recordsEnd {
		name, v, nextOff, err := parseKeyedRecord(block.payload, off, recordsEnd, prev)
		if err != nil {
			return 0, false, err
		}
		if (v & 0x7) != 0 {
			return 0, false, fmt.Errorf("index value_type must be 0")
		}
		childPos, nextOff, err := readVarint(block.payload, nextOff, recordsEnd)
		if err != nil {
			return 0, false, err
		}
		if strings.Compare(key, name) <= 0 {
			if childPos > uint64(int(^uint(0)>>1)) {
				return 0, false, fmt.Errorf("index child position overflows int")
			}
			return int(childPos), true, nil
		}
		prev = name
		off = nextOff
	}
	if off != recordsEnd {
		return 0, false, fmt.Errorf("malformed index block")
	}
	return 0, false, nil
}

// lookupRecordInRefBlock searches one ref block and may short-circuit by sort order.
func lookupRecordInRefBlock(table *tableFile, block blockView, key string) (found bool, done bool, rec recordValue, err error) {
	off, recordsEnd, restarts, err := parseBlockLayout(block)
	if err != nil {
		return false, false, recordValue{}, err
	}
	if err := validateRestarts(block, restarts, off, recordsEnd, true); err != nil {
		return false, false, recordValue{}, err
	}
	prev := ""
	for off < recordsEnd {
		name, v, nextOff, err := parseKeyedRecord(block.payload, off, recordsEnd, prev)
		if err != nil {
			return false, false, recordValue{}, err
		}
		typeBits := byte(v & 0x7)
		_, nextOff, err = readVarint(block.payload, nextOff, recordsEnd)
		if err != nil {
			return false, false, recordValue{}, err
		}
		recVal, nextOff, err := parseRefValue(block.payload, nextOff, recordsEnd, table.algo, typeBits)
		if err != nil {
			return false, false, recordValue{}, err
		}
		cmp := strings.Compare(name, key)
		if cmp == 0 {
			return true, true, recVal, nil
		}
		if cmp > 0 {
			return false, true, recordValue{}, nil
		}
		prev = name
		off = nextOff
	}
	if off != recordsEnd {
		return false, false, recordValue{}, fmt.Errorf("malformed ref block")
	}
	return false, false, recordValue{}, nil
}

// forEachRecordInRefBlock iterates all records in one ref block.
func forEachRecordInRefBlock(table *tableFile, block blockView, fn func(name string, rec recordValue) error) error {
	off, recordsEnd, restarts, err := parseBlockLayout(block)
	if err != nil {
		return err
	}
	if err := validateRestarts(block, restarts, off, recordsEnd, true); err != nil {
		return err
	}
	prev := ""
	for off < recordsEnd {
		name, v, nextOff, err := parseKeyedRecord(block.payload, off, recordsEnd, prev)
		if err != nil {
			return err
		}
		typeBits := byte(v & 0x7)
		_, nextOff, err = readVarint(block.payload, nextOff, recordsEnd)
		if err != nil {
			return err
		}
		recVal, nextOff, err := parseRefValue(block.payload, nextOff, recordsEnd, table.algo, typeBits)
		if err != nil {
			return err
		}
		if err := fn(name, recVal); err != nil {
			return err
		}
		prev = name
		off = nextOff
	}
	if off != recordsEnd {
		return fmt.Errorf("malformed ref block")
	}
	return nil
}

// parseBlockLayout parses common record/restart regions for ref and index blocks.
func parseBlockLayout(block blockView) (recordsStart int, recordsEnd int, restarts []int, err error) {
	if len(block.payload) < 6 {
		return 0, 0, nil, fmt.Errorf("short block")
	}
	restartCount := int(binary.BigEndian.Uint16(block.payload[len(block.payload)-2:]))
	if restartCount <= 0 {
		return 0, 0, nil, fmt.Errorf("invalid restart count")
	}
	restarts = make([]int, restartCount)
	restartBytes := restartCount * 3
	restartsStart := len(block.payload) - 2 - restartBytes
	if restartsStart < 4 {
		return 0, 0, nil, fmt.Errorf("invalid restart table")
	}
	for i := 0; i < restartCount; i++ {
		off := restartsStart + i*3
		rel := int(readUint24(block.payload[off : off+3]))
		base := block.start
		if block.first {
			// In the first block, restart offsets are relative to file start.
			base = 0
		}
		abs := base + rel
		restarts[i] = abs - block.start
	}
	return 4, restartsStart, restarts, nil
}

// validateRestarts validates restart monotonicity, bounds and record-prefix invariants.
func validateRestarts(block blockView, restarts []int, recordsStart, recordsEnd int, requirePrefixZero bool) error {
	prev := -1
	for _, off := range restarts {
		if off < recordsStart || off >= recordsEnd {
			return fmt.Errorf("restart offset out of range")
		}
		if off <= prev {
			return fmt.Errorf("restart offsets not strictly increasing")
		}
		prev = off
		if requirePrefixZero {
			prefix, _, err := readVarint(block.payload, off, recordsEnd)
			if err != nil {
				return err
			}
			if prefix != 0 {
				return fmt.Errorf("restart record prefix length must be zero")
			}
		}
	}
	return nil
}

// parseKeyedRecord parses one prefix-compressed key record header.
func parseKeyedRecord(buf []byte, off, end int, prev string) (name string, rawType uint64, next int, err error) {
	prefixLen, next, err := readVarint(buf, off, end)
	if err != nil {
		return "", 0, 0, err
	}
	suffixAndType, next, err := readVarint(buf, next, end)
	if err != nil {
		return "", 0, 0, err
	}
	suffixLen := int(suffixAndType >> 3)
	if suffixLen < 0 || next+suffixLen > end {
		return "", 0, 0, fmt.Errorf("invalid suffix length")
	}
	if int(prefixLen) > len(prev) {
		return "", 0, 0, fmt.Errorf("invalid prefix length")
	}
	name = prev[:prefixLen] + string(buf[next:next+suffixLen])
	next += suffixLen
	if prev != "" && strings.Compare(name, prev) <= 0 {
		return "", 0, 0, fmt.Errorf("keys not strictly increasing")
	}
	return name, suffixAndType, next, nil
}

// parseRefValue parses one ref-record value payload according to value_type.
func parseRefValue(buf []byte, off, end int, algo objectid.Algorithm, valueType byte) (recordValue, int, error) {
	switch valueType {
	case 0x0:
		return recordValue{deleted: true}, off, nil
	case 0x1:
		id, next, err := readObjectID(buf, off, end, algo)
		if err != nil {
			return recordValue{}, 0, err
		}
		return recordValue{detachedID: id, hasDetached: true}, next, nil
	case 0x2:
		id, next, err := readObjectID(buf, off, end, algo)
		if err != nil {
			return recordValue{}, 0, err
		}
		peeled, next, err := readObjectID(buf, next, end, algo)
		if err != nil {
			return recordValue{}, 0, err
		}
		peeledCopy := peeled
		return recordValue{detachedID: id, hasDetached: true, peeled: &peeledCopy}, next, nil
	case 0x3:
		targetLen, next, err := readVarint(buf, off, end)
		if err != nil {
			return recordValue{}, 0, err
		}
		if targetLen > uint64(end-next) {
			return recordValue{}, 0, fmt.Errorf("invalid symref target length")
		}
		target := string(buf[next : next+int(targetLen)])
		next += int(targetLen)
		return recordValue{symbolicTarget: target}, next, nil
	default:
		return recordValue{}, 0, fmt.Errorf("unsupported ref value type %d", valueType)
	}
}

// readObjectID reads one object ID using the table algorithm width.
func readObjectID(buf []byte, off, end int, algo objectid.Algorithm) (objectid.ObjectID, int, error) {
	sz := algo.Size()
	if off < 0 || sz < 0 || off+sz > end {
		return objectid.ObjectID{}, 0, fmt.Errorf("truncated object id")
	}
	id, err := objectid.FromBytes(algo, buf[off:off+sz])
	if err != nil {
		return objectid.ObjectID{}, 0, err
	}
	return id, off + sz, nil
}