Urgh I made some wrong amends and I'm too tired to separate the commits out this time

ancestor: Split out of reachability
mergebase: Add merge base routines
internal/commitquery: Add commit query context engine thingy
internal/peel: Shared tag peeling
errors: Shared object query errors
internal/testgit: Add rooted repo helpers; remove raw path access
objectstore/memory: Add in-memory object store
objectid: Add Compare helper

27 files changed, 1317 insertions, 12 deletions

diff --git a/internal/commitquery/ancestor.go b/internal/commitquery/ancestor.go
new file mode 100644
index 00000000..78149c6a
--- /dev/null
+++ b/internal/commitquery/ancestor.go
@@ -0,0 +1,30 @@
+package commitquery
+
+// IsAncestor reports whether ancestor is reachable from descendant through
+// commit parent edges.
+func IsAncestor(ctx *Context, ancestor, descendant NodeIndex) (bool, error) {
+	if ancestor == descendant {
+		return true, nil
+	}
+
+	ancestorGeneration := ctx.EffectiveGeneration(ancestor)
+	descendantGeneration := ctx.EffectiveGeneration(descendant)
+
+	if ancestorGeneration != generationInfinity &&
+		descendantGeneration != generationInfinity &&
+		ancestorGeneration > descendantGeneration {
+		return false, nil
+	}
+
+	minGeneration := uint64(0)
+	if ancestorGeneration != generationInfinity {
+		minGeneration = ancestorGeneration
+	}
+
+	_, err := paintDownToCommon(ctx, ancestor, []NodeIndex{descendant}, minGeneration)
+	if err != nil {
+		return false, err
+	}
+
+	return ctx.HasAnyMarks(ancestor, markRight), nil
+}
diff --git a/internal/commitquery/bits.go b/internal/commitquery/bits.go
new file mode 100644
index 00000000..36ffff29
--- /dev/null
+++ b/internal/commitquery/bits.go
@@ -0,0 +1,14 @@
+package commitquery
+
+type markBits uint8
+
+const (
+	markLeft markBits = 1 << iota
+	markRight
+	markStale
+	markResult
+)
+
+const (
+	allMarks = markLeft | markRight | markStale | markResult
+)
diff --git a/internal/commitquery/commit.go b/internal/commitquery/commit.go
new file mode 100644
index 00000000..548aae4d
--- /dev/null
+++ b/internal/commitquery/commit.go
@@ -0,0 +1,17 @@
+package commitquery
+
+import (
+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// Commit stores the metadata needed by commit-domain queries.
+type Commit struct {
+	ID            objectid.ObjectID
+	Parents       []Parent
+	CommitTime    int64
+	Generation    uint64
+	HasGeneration bool
+	GraphPos      commitgraphread.Position
+	HasGraphPos   bool
+}
diff --git a/internal/commitquery/compare.go b/internal/commitquery/compare.go
new file mode 100644
index 00000000..748ef712
--- /dev/null
+++ b/internal/commitquery/compare.go
@@ -0,0 +1,25 @@
+package commitquery
+
+import "codeberg.org/lindenii/furgit/objectid"
+
+// Compare compares two internal nodes using merge-base queue ordering.
+func (ctx *Context) Compare(left, right NodeIndex) int {
+	leftGeneration := ctx.EffectiveGeneration(left)
+	rightGeneration := ctx.EffectiveGeneration(right)
+
+	switch {
+	case leftGeneration < rightGeneration:
+		return -1
+	case leftGeneration > rightGeneration:
+		return 1
+	}
+
+	switch {
+	case ctx.nodes[left].commitTime < ctx.nodes[right].commitTime:
+		return -1
+	case ctx.nodes[left].commitTime > ctx.nodes[right].commitTime:
+		return 1
+	}
+
+	return objectid.Compare(ctx.nodes[left].id, ctx.nodes[right].id)
+}
diff --git a/internal/commitquery/context.go b/internal/commitquery/context.go
new file mode 100644
index 00000000..f39c32c8
--- /dev/null
+++ b/internal/commitquery/context.go
@@ -0,0 +1,32 @@
+// Package commitquery provides private commit-domain query routines.
+package commitquery
+
+import (
+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objectstore"
+)
+
+// Context owns the mutable node arena for one commit query.
+type Context struct {
+	store objectstore.Store
+	graph *commitgraphread.Reader
+
+	nodes []node
+
+	byOID      map[objectid.ObjectID]NodeIndex
+	byGraphPos map[commitgraphread.Position]NodeIndex
+
+	markPhase uint32
+	touched   []NodeIndex
+}
+
+// NewContext builds one empty query context over one object store and optional commit-graph reader.
+func NewContext(store objectstore.Store, graph *commitgraphread.Reader) *Context {
+	return &Context{
+		store:      store,
+		graph:      graph,
+		byOID:      make(map[objectid.ObjectID]NodeIndex),
+		byGraphPos: make(map[commitgraphread.Position]NodeIndex),
+	}
+}
diff --git a/internal/commitquery/errors.go b/internal/commitquery/errors.go
new file mode 100644
index 00000000..e99011d0
--- /dev/null
+++ b/internal/commitquery/errors.go
@@ -0,0 +1,5 @@
+package commitquery
+
+import "errors"
+
+var errBadGenerationOrder = errors.New("commitquery: priority queue violated generation ordering")
diff --git a/internal/commitquery/generation.go b/internal/commitquery/generation.go
new file mode 100644
index 00000000..c5edcd9f
--- /dev/null
+++ b/internal/commitquery/generation.go
@@ -0,0 +1,43 @@
+package commitquery
+
+import (
+	"math"
+
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// EffectiveGeneration returns one node's generation value.
+func (ctx *Context) EffectiveGeneration(idx NodeIndex) uint64 {
+	if !ctx.nodes[idx].hasGeneration {
+		return generationInfinity
+	}
+
+	return ctx.nodes[idx].generation
+}
+
+const (
+	generationInfinity = uint64(math.MaxUint64)
+)
+
+func compareByGeneration(ctx *Context) func(NodeIndex, NodeIndex) int {
+	return func(left, right NodeIndex) int {
+		leftGeneration := ctx.EffectiveGeneration(left)
+		rightGeneration := ctx.EffectiveGeneration(right)
+
+		switch {
+		case leftGeneration < rightGeneration:
+			return -1
+		case leftGeneration > rightGeneration:
+			return 1
+		}
+
+		switch {
+		case ctx.nodes[left].commitTime < ctx.nodes[right].commitTime:
+			return -1
+		case ctx.nodes[left].commitTime > ctx.nodes[right].commitTime:
+			return 1
+		}
+
+		return objectid.Compare(ctx.nodes[left].id, ctx.nodes[right].id)
+	}
+}
diff --git a/internal/commitquery/graph_pos.go b/internal/commitquery/graph_pos.go
new file mode 100644
index 00000000..2031e3d8
--- /dev/null
+++ b/internal/commitquery/graph_pos.go
@@ -0,0 +1,107 @@
+package commitquery
+
+import commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+
+// ResolveGraphPos resolves one commit-graph position to one internal query node.
+func (ctx *Context) ResolveGraphPos(pos commitgraphread.Position) (NodeIndex, error) {
+	idx, ok := ctx.byGraphPos[pos]
+	if ok {
+		err := ctx.ensureLoaded(idx)
+		if err != nil {
+			return 0, err
+		}
+
+		return idx, nil
+	}
+
+	commit, err := ctx.graph.CommitAt(pos)
+	if err != nil {
+		return 0, err
+	}
+
+	idx, ok = ctx.byOID[commit.OID]
+	if !ok {
+		idx = ctx.newNode(commit.OID)
+		ctx.byOID[commit.OID] = idx
+	}
+
+	ctx.byGraphPos[pos] = idx
+	ctx.nodes[idx].graphPos = pos
+	ctx.nodes[idx].hasGraphPos = true
+
+	err = ctx.loadCommitAtGraphPos(idx, pos)
+	if err != nil {
+		delete(ctx.byGraphPos, pos)
+
+		return 0, err
+	}
+
+	return idx, nil
+}
+
+// loadByGraphPos populates one node from a commit-graph position.
+func (ctx *Context) loadByGraphPos(idx NodeIndex) error {
+	pos := ctx.nodes[idx].graphPos
+
+	return ctx.loadCommitAtGraphPos(idx, pos)
+}
+
+func (ctx *Context) loadCommitAtGraphPos(idx NodeIndex, pos commitgraphread.Position) error {
+	commit, err := ctx.graph.CommitAt(pos)
+	if err != nil {
+		return err
+	}
+
+	parents := make([]Parent, 0, 2+len(commit.ExtraParents))
+
+	if commit.Parent1.Valid {
+		parentOID, err := ctx.graph.OIDAt(commit.Parent1.Pos)
+		if err != nil {
+			return err
+		}
+
+		parents = append(parents, Parent{
+			ID:          parentOID,
+			GraphPos:    commit.Parent1.Pos,
+			HasGraphPos: true,
+		})
+	}
+
+	if commit.Parent2.Valid {
+		parentOID, err := ctx.graph.OIDAt(commit.Parent2.Pos)
+		if err != nil {
+			return err
+		}
+
+		parents = append(parents, Parent{
+			ID:          parentOID,
+			GraphPos:    commit.Parent2.Pos,
+			HasGraphPos: true,
+		})
+	}
+
+	for _, parentPos := range commit.ExtraParents {
+		parentOID, err := ctx.graph.OIDAt(parentPos)
+		if err != nil {
+			return err
+		}
+
+		parents = append(parents, Parent{
+			ID:          parentOID,
+			GraphPos:    parentPos,
+			HasGraphPos: true,
+		})
+	}
+
+	data := Commit{
+		ID:            commit.OID,
+		Parents:       parents,
+		CommitTime:    commit.CommitTimeUnix,
+		Generation:    commit.GenerationV2,
+		HasGeneration: commit.GenerationV2 != 0,
+		GraphPos:      pos,
+		HasGraphPos:   true,
+	}
+
+	return ctx.populateNode(idx, data)
+}
diff --git a/internal/commitquery/load.go b/internal/commitquery/load.go
new file mode 100644
index 00000000..b795f7d9
--- /dev/null
+++ b/internal/commitquery/load.go
@@ -0,0 +1,14 @@
+package commitquery
+
+// ensureLoaded completes one node's metadata load if it has not been loaded yet.
+func (ctx *Context) ensureLoaded(idx NodeIndex) error {
+	if ctx.nodes[idx].loaded {
+		return nil
+	}
+
+	if ctx.nodes[idx].hasGraphPos {
+		return ctx.loadByGraphPos(idx)
+	}
+
+	return ctx.loadByOID(idx)
+}
diff --git a/internal/commitquery/marks.go b/internal/commitquery/marks.go
new file mode 100644
index 00000000..f88fdf25
--- /dev/null
+++ b/internal/commitquery/marks.go
@@ -0,0 +1,67 @@
+package commitquery
+
+// Marks returns the mark bits of one internal node.
+func (ctx *Context) Marks(idx NodeIndex) markBits {
+	return ctx.nodes[idx].marks
+}
+
+// HasAnyMarks reports whether one internal node has any requested bit.
+func (ctx *Context) HasAnyMarks(idx NodeIndex, bits markBits) bool {
+	return ctx.nodes[idx].marks&bits != 0
+}
+
+// HasAllMarks reports whether one internal node already has all requested bits.
+func (ctx *Context) HasAllMarks(idx NodeIndex, bits markBits) bool {
+	return ctx.nodes[idx].marks&bits == bits
+}
+
+// SetMarks ORs one set of mark bits into one internal node.
+func (ctx *Context) SetMarks(idx NodeIndex, bits markBits) {
+	newBits := bits &^ ctx.nodes[idx].marks
+	if newBits == 0 {
+		return
+	}
+
+	ctx.trackTouched(idx)
+	ctx.nodes[idx].marks |= bits
+}
+
+// ClearMarks removes one set of mark bits from one internal node.
+func (ctx *Context) ClearMarks(idx NodeIndex, bits markBits) {
+	if ctx.nodes[idx].marks&bits == 0 {
+		return
+	}
+
+	ctx.trackTouched(idx)
+	ctx.nodes[idx].marks &^= bits
+}
+
+// BeginMarkPhase starts one tracked mark-mutation phase.
+func (ctx *Context) BeginMarkPhase() {
+	ctx.markPhase++
+	if ctx.markPhase == 0 {
+		ctx.markPhase++
+		for i := range ctx.nodes {
+			ctx.nodes[i].touchedPhase = 0
+		}
+	}
+
+	ctx.touched = ctx.touched[:0]
+}
+
+// ClearTouchedMarks clears the provided bits from all nodes touched in the
+// current mark phase.
+func (ctx *Context) ClearTouchedMarks(bits markBits) {
+	for _, idx := range ctx.touched {
+		ctx.nodes[idx].marks &^= bits
+	}
+}
+
+func (ctx *Context) trackTouched(idx NodeIndex) {
+	if ctx.nodes[idx].touchedPhase == ctx.markPhase {
+		return
+	}
+
+	ctx.nodes[idx].touchedPhase = ctx.markPhase
+	ctx.touched = append(ctx.touched, idx)
+}
diff --git a/internal/commitquery/merge_bases.go b/internal/commitquery/merge_bases.go
new file mode 100644
index 00000000..b0171f5e
--- /dev/null
+++ b/internal/commitquery/merge_bases.go
@@ -0,0 +1,105 @@
+package commitquery
+
+import "slices"
+
+// MergeBases computes fully reduced merge bases using one query context.
+func MergeBases(ctx *Context, left, right NodeIndex) ([]NodeIndex, error) {
+	if left == right {
+		return []NodeIndex{left}, nil
+	}
+
+	candidates, err := paintDownToCommon(ctx, left, []NodeIndex{right}, 0)
+	if err != nil {
+		return nil, err
+	}
+
+	if len(candidates) <= 1 {
+		slices.SortFunc(candidates, ctx.Compare)
+
+		return candidates, nil
+	}
+
+	ctx.ClearTouchedMarks(allMarks)
+
+	reduced, err := removeRedundant(ctx, candidates)
+	if err != nil {
+		return nil, err
+	}
+
+	slices.SortFunc(reduced, ctx.Compare)
+
+	return reduced, nil
+}
+
+func paintDownToCommon(ctx *Context, left NodeIndex, rights []NodeIndex, minGeneration uint64) ([]NodeIndex, error) {
+	ctx.BeginMarkPhase()
+
+	ctx.SetMarks(left, markLeft)
+
+	if len(rights) == 0 {
+		return []NodeIndex{left}, nil
+	}
+
+	queue := NewPriorityQueue(ctx)
+	queue.PushNode(left)
+
+	for _, right := range rights {
+		ctx.SetMarks(right, markRight)
+		queue.PushNode(right)
+	}
+
+	lastGeneration := generationInfinity
+	results := make([]NodeIndex, 0, 4)
+
+	for queueHasNonStale(ctx, queue) {
+		idx := queue.PopNode()
+
+		generation := ctx.EffectiveGeneration(idx)
+		if generation > lastGeneration {
+			return nil, errBadGenerationOrder
+		}
+
+		lastGeneration = generation
+		if generation < minGeneration {
+			break
+		}
+
+		flags := ctx.Marks(idx) & (markLeft | markRight | markStale)
+		if flags == (markLeft | markRight) {
+			if !ctx.HasAnyMarks(idx, markResult) {
+				ctx.SetMarks(idx, markResult)
+				results = append(results, idx)
+			}
+
+			flags |= markStale
+		}
+
+		for _, parent := range ctx.Parents(idx) {
+			if ctx.HasAllMarks(parent, flags) {
+				continue
+			}
+
+			ctx.SetMarks(parent, flags)
+			queue.PushNode(parent)
+		}
+	}
+
+	out := results[:0]
+	for _, idx := range results {
+		if !ctx.HasAnyMarks(idx, markStale) {
+			out = append(out, idx)
+		}
+	}
+
+	return out, nil
+}
+
+func queueHasNonStale(ctx *Context, queue *PriorityQueue) bool {
+	for _, idx := range queue.items {
+		if !ctx.HasAnyMarks(idx, markStale) {
+			return true
+		}
+	}
+
+	return false
+}
diff --git a/internal/commitquery/node.go b/internal/commitquery/node.go
new file mode 100644
index 00000000..7abf381d
--- /dev/null
+++ b/internal/commitquery/node.go
@@ -0,0 +1,39 @@
+package commitquery
+
+import (
+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// NodeIndex identifies one internal query node.
+type NodeIndex int
+
+// node stores one mutable commit traversal node.
+type node struct {
+	id objectid.ObjectID
+
+	parents []NodeIndex
+
+	commitTime int64
+	generation uint64
+
+	hasGeneration bool
+	hasGraphPos   bool
+	loaded        bool
+
+	graphPos commitgraphread.Position
+	marks    markBits
+
+	touchedPhase uint32
+}
+
+// newNode allocates one empty internal node.
+func (ctx *Context) newNode(id objectid.ObjectID) NodeIndex {
+	count := len(ctx.nodes)
+
+	idx := NodeIndex(count)
+
+	ctx.nodes = append(ctx.nodes, node{id: id})
+
+	return idx
+}
diff --git a/internal/commitquery/oid.go b/internal/commitquery/oid.go
new file mode 100644
index 00000000..7ba05eb5
--- /dev/null
+++ b/internal/commitquery/oid.go
@@ -0,0 +1,95 @@
+package commitquery
+
+import (
+	stderrors "errors"
+
+	giterrors "codeberg.org/lindenii/furgit/errors"
+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+	"codeberg.org/lindenii/furgit/object"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objectstore"
+	"codeberg.org/lindenii/furgit/objecttype"
+)
+
+// ID returns the canonical object ID of one internal node.
+func (ctx *Context) ID(idx NodeIndex) objectid.ObjectID {
+	return ctx.nodes[idx].id
+}
+
+// CommitTime returns the committer timestamp used for one internal node.
+func (ctx *Context) CommitTime(idx NodeIndex) int64 {
+	return ctx.nodes[idx].commitTime
+}
+
+// ResolveOID resolves one commit object ID to one internal query node.
+func (ctx *Context) ResolveOID(id objectid.ObjectID) (NodeIndex, error) {
+	idx, ok := ctx.byOID[id]
+	if ok {
+		err := ctx.ensureLoaded(idx)
+		if err != nil {
+			return 0, err
+		}
+
+		return idx, nil
+	}
+
+	idx = ctx.newNode(id)
+	ctx.byOID[id] = idx
+
+	err := ctx.loadByOID(idx)
+	if err != nil {
+		delete(ctx.byOID, id)
+
+		return 0, err
+	}
+
+	return idx, nil
+}
+
+// loadByOID populates one node from an object ID.
+func (ctx *Context) loadByOID(idx NodeIndex) error {
+	id := ctx.nodes[idx].id
+
+	if ctx.graph != nil {
+		pos, err := ctx.graph.Lookup(id)
+		if err != nil {
+			var notFound *commitgraphread.NotFoundError
+			if !stderrors.As(err, &notFound) {
+				return err
+			}
+		} else {
+			return ctx.loadCommitAtGraphPos(idx, pos)
+		}
+	}
+
+	ty, content, err := ctx.store.ReadBytesContent(id)
+	if err != nil {
+		if stderrors.Is(err, objectstore.ErrObjectNotFound) {
+			return &giterrors.ObjectMissingError{OID: id}
+		}
+
+		return err
+	}
+
+	if ty != objecttype.TypeCommit {
+		return &giterrors.ObjectTypeError{OID: id, Got: ty, Want: objecttype.TypeCommit}
+	}
+
+	commitObj, err := object.ParseCommit(content, id.Algorithm())
+	if err != nil {
+		return err
+	}
+
+	parents := make([]Parent, 0, len(commitObj.Parents))
+	for _, parentID := range commitObj.Parents {
+		parents = append(parents, Parent{ID: parentID})
+	}
+
+	commit := Commit{
+		ID:         id,
+		Parents:    parents,
+		CommitTime: commitObj.Committer.WhenUnix,
+	}
+
+	return ctx.populateNode(idx, commit)
+}
diff --git a/internal/commitquery/parent.go b/internal/commitquery/parent.go
new file mode 100644
index 00000000..17695e09
--- /dev/null
+++ b/internal/commitquery/parent.go
@@ -0,0 +1,27 @@
+package commitquery
+
+import (
+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// Parent references one commit parent.
+type Parent struct {
+	ID          objectid.ObjectID
+	GraphPos    commitgraphread.Position
+	HasGraphPos bool
+}
+
+// Parents returns resolved parent node indices for one internal node.
+func (ctx *Context) Parents(idx NodeIndex) []NodeIndex {
+	return ctx.nodes[idx].parents
+}
+
+// resolveParent resolves one parent descriptor to one internal node.
+func (ctx *Context) resolveParent(parent Parent) (NodeIndex, error) {
+	if parent.HasGraphPos {
+		return ctx.ResolveGraphPos(parent.GraphPos)
+	}
+
+	return ctx.ResolveOID(parent.ID)
+}
diff --git a/internal/commitquery/populate.go b/internal/commitquery/populate.go
new file mode 100644
index 00000000..87d65bf8
--- /dev/null
+++ b/internal/commitquery/populate.go
@@ -0,0 +1,42 @@
+package commitquery
+
+import "fmt"
+
+// populateNode fills one node's metadata and resolves its parents.
+func (ctx *Context) populateNode(idx NodeIndex, commit Commit) error {
+	if ctx.nodes[idx].loaded {
+		if ctx.nodes[idx].id != commit.ID {
+			return fmt.Errorf("commitquery: node identity mismatch: have %s, got %s", ctx.nodes[idx].id, commit.ID)
+		}
+
+		return nil
+	}
+
+	ctx.nodes[idx].id = commit.ID
+	ctx.nodes[idx].commitTime = commit.CommitTime
+	ctx.nodes[idx].generation = commit.Generation
+	ctx.nodes[idx].hasGeneration = commit.HasGeneration
+
+	if commit.HasGraphPos {
+		ctx.nodes[idx].graphPos = commit.GraphPos
+		ctx.nodes[idx].hasGraphPos = true
+		ctx.byGraphPos[commit.GraphPos] = idx
+	}
+
+	ctx.nodes[idx].loaded = true
+	ctx.nodes[idx].parents = ctx.nodes[idx].parents[:0]
+
+	for _, parent := range commit.Parents {
+		parentIdx, err := ctx.resolveParent(parent)
+		if err != nil {
+			ctx.nodes[idx].loaded = false
+			ctx.nodes[idx].parents = nil
+
+			return err
+		}
+
+		ctx.nodes[idx].parents = append(ctx.nodes[idx].parents, parentIdx)
+	}
+
+	return nil
+}
diff --git a/internal/commitquery/priority_queue.go b/internal/commitquery/priority_queue.go
new file mode 100644
index 00000000..a7a4876e
--- /dev/null
+++ b/internal/commitquery/priority_queue.go
@@ -0,0 +1,68 @@
+package commitquery
+
+import "container/heap"
+
+// PriorityQueue orders internal nodes using one query context's comparator.
+type PriorityQueue struct {
+	ctx   *Context
+	items []NodeIndex
+}
+
+// NewPriorityQueue builds one empty priority queue over one query context.
+func NewPriorityQueue(ctx *Context) *PriorityQueue {
+	queue := &PriorityQueue{ctx: ctx}
+	heap.Init(queue)
+
+	return queue
+}
+
+// Len reports the number of queued items.
+func (queue *PriorityQueue) Len() int {
+	return len(queue.items)
+}
+
+// Less reports whether one heap slot sorts ahead of another.
+func (queue *PriorityQueue) Less(left, right int) bool {
+	return queue.ctx.Compare(queue.items[left], queue.items[right]) > 0
+}
+
+// Swap exchanges two heap slots.
+func (queue *PriorityQueue) Swap(left, right int) {
+	queue.items[left], queue.items[right] = queue.items[right], queue.items[left]
+}
+
+// Push appends one heap element.
+func (queue *PriorityQueue) Push(item any) {
+	idx, ok := item.(NodeIndex)
+	if !ok {
+		panic("commitquery: heap push item is not a NodeIndex")
+	}
+
+	queue.items = append(queue.items, idx)
+}
+
+// Pop removes one heap element.
+func (queue *PriorityQueue) Pop() any {
+	last := len(queue.items) - 1
+	item := queue.items[last]
+	queue.items = queue.items[:last]
+
+	return item
+}
+
+// PushNode inserts one internal node.
+func (queue *PriorityQueue) PushNode(idx NodeIndex) {
+	heap.Push(queue, idx)
+}
+
+// PopNode removes the highest-priority internal node.
+func (queue *PriorityQueue) PopNode() NodeIndex {
+	item := heap.Pop(queue)
+
+	idx, ok := item.(NodeIndex)
+	if !ok {
+		panic("commitquery: heap pop item is not a NodeIndex")
+	}
+
+	return idx
+}
diff --git a/internal/commitquery/reduce.go b/internal/commitquery/reduce.go
new file mode 100644
index 00000000..497ff443
--- /dev/null
+++ b/internal/commitquery/reduce.go
@@ -0,0 +1,166 @@
+package commitquery
+
+import (
+	"slices"
+)
+
+// removeRedundant removes redundant merge-base candidates.
+func removeRedundant(ctx *Context, candidates []NodeIndex) ([]NodeIndex, error) {
+	for _, idx := range candidates {
+		if ctx.EffectiveGeneration(idx) != generationInfinity {
+			return removeRedundantWithGen(ctx, candidates), nil
+		}
+	}
+
+	return removeRedundantNoGen(ctx, candidates)
+}
+
+func removeRedundantNoGen(ctx *Context, candidates []NodeIndex) ([]NodeIndex, error) {
+	redundant := make([]bool, len(candidates))
+	work := make([]NodeIndex, 0, len(candidates)-1)
+	filledIndex := make([]int, 0, len(candidates)-1)
+
+	for i, candidate := range candidates {
+		if redundant[i] {
+			continue
+		}
+
+		work = work[:0]
+		filledIndex = filledIndex[:0]
+
+		minGeneration := ctx.EffectiveGeneration(candidate)
+
+		for j, other := range candidates {
+			if i == j || redundant[j] {
+				continue
+			}
+
+			work = append(work, other)
+			filledIndex = append(filledIndex, j)
+
+			otherGeneration := ctx.EffectiveGeneration(other)
+			if otherGeneration < minGeneration {
+				minGeneration = otherGeneration
+			}
+		}
+
+		_, err := paintDownToCommon(ctx, candidate, work, minGeneration)
+		if err != nil {
+			return nil, err
+		}
+
+		if ctx.HasAnyMarks(candidate, markRight) {
+			redundant[i] = true
+		}
+
+		for j, other := range work {
+			if ctx.HasAnyMarks(other, markLeft) {
+				redundant[filledIndex[j]] = true
+			}
+		}
+
+		ctx.ClearTouchedMarks(allMarks)
+	}
+
+	out := make([]NodeIndex, 0, len(candidates))
+	for i, idx := range candidates {
+		if !redundant[i] {
+			out = append(out, idx)
+		}
+	}
+
+	return out, nil
+}
+
+func removeRedundantWithGen(ctx *Context, candidates []NodeIndex) []NodeIndex {
+	sorted := append([]NodeIndex(nil), candidates...)
+	slices.SortFunc(sorted, compareByGeneration(ctx))
+
+	minGeneration := ctx.EffectiveGeneration(sorted[0])
+	minGenPos := 0
+	countStillIndependent := len(candidates)
+
+	ctx.BeginMarkPhase()
+
+	walkStart := make([]NodeIndex, 0, len(candidates)*2)
+
+	for _, idx := range candidates {
+		ctx.SetMarks(idx, markResult)
+
+		for _, parent := range ctx.Parents(idx) {
+			if ctx.HasAnyMarks(parent, markStale) {
+				continue
+			}
+
+			ctx.SetMarks(parent, markStale)
+			walkStart = append(walkStart, parent)
+		}
+	}
+
+	slices.SortFunc(walkStart, compareByGeneration(ctx))
+
+	for _, idx := range walkStart {
+		ctx.ClearMarks(idx, markStale)
+	}
+
+	for i := len(walkStart) - 1; i >= 0 && countStillIndependent > 1; i-- {
+		stack := []NodeIndex{walkStart[i]}
+		ctx.SetMarks(walkStart[i], markStale)
+
+		for len(stack) > 0 {
+			top := stack[len(stack)-1]
+
+			if ctx.HasAnyMarks(top, markResult) {
+				ctx.ClearMarks(top, markResult)
+
+				countStillIndependent--
+				if countStillIndependent <= 1 {
+					break
+				}
+
+				if top == sorted[minGenPos] {
+					for minGenPos < len(sorted)-1 && ctx.HasAnyMarks(sorted[minGenPos], markStale) {
+						minGenPos++
+					}
+
+					minGeneration = ctx.EffectiveGeneration(sorted[minGenPos])
+				}
+			}
+
+			if ctx.EffectiveGeneration(top) < minGeneration {
+				stack = stack[:len(stack)-1]
+
+				continue
+			}
+
+			pushed := false
+
+			for _, parent := range ctx.Parents(top) {
+				if ctx.HasAnyMarks(parent, markStale) {
+					continue
+				}
+
+				ctx.SetMarks(parent, markStale)
+				stack = append(stack, parent)
+				pushed = true
+
+				break
+			}
+
+			if !pushed {
+				stack = stack[:len(stack)-1]
+			}
+		}
+	}
+
+	out := make([]NodeIndex, 0, len(candidates))
+	for _, idx := range candidates {
+		if !ctx.HasAnyMarks(idx, markStale) {
+			out = append(out, idx)
+		}
+	}
+
+	ctx.ClearTouchedMarks(markStale | markResult)
+
+	return out
+}
diff --git a/internal/peel/peel.go b/internal/peel/peel.go
new file mode 100644
index 00000000..a3e84b8d
--- /dev/null
+++ b/internal/peel/peel.go
@@ -0,0 +1,50 @@
+// Package peel peels Git object references through annotated tags.
+package peel
+
+import (
+	stderrors "errors"
+
+	giterrors "codeberg.org/lindenii/furgit/errors"
+	"codeberg.org/lindenii/furgit/object"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objectstore"
+	"codeberg.org/lindenii/furgit/objecttype"
+)
+
+// ToCommit peels annotated tags transitively until a commit is reached.
+func ToCommit(store objectstore.Store, id objectid.ObjectID) (objectid.ObjectID, error) {
+	for {
+		ty, _, err := store.ReadHeader(id)
+		if err != nil {
+			if stderrors.Is(err, objectstore.ErrObjectNotFound) {
+				return objectid.ObjectID{}, &giterrors.ObjectMissingError{OID: id}
+			}
+
+			return objectid.ObjectID{}, err
+		}
+
+		if ty != objecttype.TypeTag {
+			if ty != objecttype.TypeCommit {
+				return objectid.ObjectID{}, &giterrors.ObjectTypeError{OID: id, Got: ty, Want: objecttype.TypeCommit}
+			}
+
+			return id, nil
+		}
+
+		_, content, err := store.ReadBytesContent(id)
+		if err != nil {
+			if stderrors.Is(err, objectstore.ErrObjectNotFound) {
+				return objectid.ObjectID{}, &giterrors.ObjectMissingError{OID: id}
+			}
+
+			return objectid.ObjectID{}, err
+		}
+
+		tag, err := object.ParseTag(content, id.Algorithm())
+		if err != nil {
+			return objectid.ObjectID{}, err
+		}
+
+		id = tag.Target
+	}
+}
diff --git a/internal/testgit/repo_commit_tree_env.go b/internal/testgit/repo_commit_tree_env.go
new file mode 100644
index 00000000..ee949b5c
--- /dev/null
+++ b/internal/testgit/repo_commit_tree_env.go
@@ -0,0 +1,51 @@
+package testgit
+
+import (
+	"slices"
+	"strings"
+	"testing"
+
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// CommitTreeWithEnv creates one commit from a tree and message, optionally with
+// parents, using additional environment variables for the git subprocess.
+func (testRepo *TestRepo) CommitTreeWithEnv(
+	tb testing.TB,
+	extraEnv []string,
+	tree objectid.ObjectID,
+	message string,
+	parents ...objectid.ObjectID,
+) objectid.ObjectID {
+	tb.Helper()
+
+	args := make([]string, 0, 2+2*len(parents)+2)
+
+	args = append(args, "commit-tree", tree.String())
+	for _, parent := range parents {
+		args = append(args, "-p", parent.String())
+	}
+
+	args = append(args, "-m", message)
+	hex := testRepo.runWithExtraEnv(tb, extraEnv, args...)
+
+	id, err := objectid.ParseHex(testRepo.algo, hex)
+	if err != nil {
+		tb.Fatalf("parse commit-tree output %q: %v", hex, err)
+	}
+
+	return id
+}
+
+func (testRepo *TestRepo) runWithExtraEnv(tb testing.TB, extraEnv []string, args ...string) string {
+	tb.Helper()
+
+	env := slices.Concat(testRepo.env, extraEnv)
+
+	out, err := testRepo.runBytesWithEnv(tb, nil, testRepo.dir, env, args...)
+	if err != nil {
+		tb.Fatalf("git %v failed: %v\n%s", args, err, out)
+	}
+
+	return strings.TrimSpace(string(out))
+}
diff --git a/internal/testgit/repo_fs.go b/internal/testgit/repo_fs.go
new file mode 100644
index 00000000..56acbfcf
--- /dev/null
+++ b/internal/testgit/repo_fs.go
@@ -0,0 +1,86 @@
+package testgit
+
+import (
+	"os"
+	"path/filepath"
+	"testing"
+)
+
+// OpenFile opens one file relative to the repository root.
+func (testRepo *TestRepo) OpenFile(tb testing.TB, name string) *os.File {
+	tb.Helper()
+
+	root := testRepo.OpenRoot(tb)
+
+	file, err := root.Open(name)
+	if err != nil {
+		tb.Fatalf("Open(%q): %v", name, err)
+	}
+
+	return file
+}
+
+// ReadFile reads one file relative to the repository root.
+func (testRepo *TestRepo) ReadFile(tb testing.TB, name string) []byte {
+	tb.Helper()
+
+	root := testRepo.OpenRoot(tb)
+
+	data, err := root.ReadFile(name)
+	if err != nil {
+		tb.Fatalf("ReadFile(%q): %v", name, err)
+	}
+
+	return data
+}
+
+// WriteFile writes one file relative to the repository root.
+func (testRepo *TestRepo) WriteFile(tb testing.TB, name string, data []byte, perm os.FileMode) {
+	tb.Helper()
+
+	root := testRepo.OpenRoot(tb)
+
+	err := root.WriteFile(name, data, perm)
+	if err != nil {
+		tb.Fatalf("WriteFile(%q): %v", name, err)
+	}
+}
+
+// WriteFileAll writes one file relative to the repository root, creating any
+// missing parent directories first.
+func (testRepo *TestRepo) WriteFileAll(
+	tb testing.TB,
+	name string,
+	data []byte,
+	dirPerm os.FileMode,
+	filePerm os.FileMode,
+) {
+	tb.Helper()
+
+	root := testRepo.OpenRoot(tb)
+
+	dir := filepath.Dir(name)
+	if dir != "." {
+		err := root.MkdirAll(dir, dirPerm)
+		if err != nil {
+			tb.Fatalf("MkdirAll(%q): %v", dir, err)
+		}
+	}
+
+	err := root.WriteFile(name, data, filePerm)
+	if err != nil {
+		tb.Fatalf("WriteFile(%q): %v", name, err)
+	}
+}
+
+// Remove removes one path relative to the repository root.
+func (testRepo *TestRepo) Remove(tb testing.TB, name string) {
+	tb.Helper()
+
+	root := testRepo.OpenRoot(tb)
+
+	err := root.Remove(name)
+	if err != nil {
+		tb.Fatalf("Remove(%q): %v", name, err)
+	}
+}
diff --git a/internal/testgit/repo_open_commit_graph.go b/internal/testgit/repo_open_commit_graph.go
new file mode 100644
index 00000000..4db7261b
--- /dev/null
+++ b/internal/testgit/repo_open_commit_graph.go
@@ -0,0 +1,26 @@
+package testgit
+
+import (
+	"testing"
+
+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+)
+
+// OpenCommitGraph opens the repository commit-graph and registers cleanup on
+// the caller.
+func (testRepo *TestRepo) OpenCommitGraph(tb testing.TB) *commitgraphread.Reader {
+	tb.Helper()
+
+	objectsRoot := testRepo.OpenObjectsRoot(tb)
+
+	graph, err := commitgraphread.Open(objectsRoot, testRepo.Algorithm(), commitgraphread.OpenSingle)
+	if err != nil {
+		tb.Fatalf("commitgraphread.Open: %v", err)
+	}
+
+	tb.Cleanup(func() {
+		_ = graph.Close()
+	})
+
+	return graph
+}
diff --git a/internal/testgit/repo_open_object_store.go b/internal/testgit/repo_open_object_store.go
new file mode 100644
index 00000000..aac71d60
--- /dev/null
+++ b/internal/testgit/repo_open_object_store.go
@@ -0,0 +1,29 @@
+package testgit
+
+import (
+	"testing"
+
+	"codeberg.org/lindenii/furgit/objectstore"
+	"codeberg.org/lindenii/furgit/repository"
+)
+
+// OpenObjectStore opens the repository object store and registers cleanup on
+// the caller.
+//
+//nolint:ireturn
+func (testRepo *TestRepo) OpenObjectStore(tb testing.TB) objectstore.Store {
+	tb.Helper()
+
+	root := testRepo.OpenGitRoot(tb)
+
+	repo, err := repository.Open(root)
+	if err != nil {
+		tb.Fatalf("repository.Open: %v", err)
+	}
+
+	tb.Cleanup(func() {
+		_ = repo.Close()
+	})
+
+	return repo.Objects()
+}
diff --git a/internal/testgit/repo_open_repository.go b/internal/testgit/repo_open_repository.go
new file mode 100644
index 00000000..fbc98383
--- /dev/null
+++ b/internal/testgit/repo_open_repository.go
@@ -0,0 +1,25 @@
+package testgit
+
+import (
+	"testing"
+
+	"codeberg.org/lindenii/furgit/repository"
+)
+
+// OpenRepository opens the repository and registers cleanup on the caller.
+func (testRepo *TestRepo) OpenRepository(tb testing.TB) *repository.Repository {
+	tb.Helper()
+
+	root := testRepo.OpenGitRoot(tb)
+
+	repo, err := repository.Open(root)
+	if err != nil {
+		tb.Fatalf("repository.Open: %v", err)
+	}
+
+	tb.Cleanup(func() {
+		_ = repo.Close()
+	})
+
+	return repo
+}
diff --git a/internal/testgit/repo_open_root.go b/internal/testgit/repo_open_root.go
new file mode 100644
index 00000000..4530c604
--- /dev/null
+++ b/internal/testgit/repo_open_root.go
@@ -0,0 +1,87 @@
+package testgit
+
+import (
+	"errors"
+	"os"
+	"testing"
+)
+
+// OpenRoot opens the repository root directory and registers cleanup on the
+// caller.
+func (testRepo *TestRepo) OpenRoot(tb testing.TB) *os.Root {
+	tb.Helper()
+
+	root, err := os.OpenRoot(testRepo.dir)
+	if err != nil {
+		tb.Fatalf("os.OpenRoot: %v", err)
+	}
+
+	tb.Cleanup(func() {
+		_ = root.Close()
+	})
+
+	return root
+}
+
+// OpenGitRoot opens the repository gitdir and registers cleanup on the caller.
+//
+// For bare repositories, this is the repository root itself. For non-bare
+// repositories, this is the .git directory under the worktree root.
+func (testRepo *TestRepo) OpenGitRoot(tb testing.TB) *os.Root {
+	tb.Helper()
+
+	repoRoot := testRepo.OpenRoot(tb)
+
+	gitRoot, err := repoRoot.OpenRoot(".git")
+	if err == nil {
+		tb.Cleanup(func() {
+			_ = gitRoot.Close()
+		})
+
+		return gitRoot
+	}
+
+	if !errors.Is(err, os.ErrNotExist) {
+		tb.Fatalf("OpenRoot(.git): %v", err)
+	}
+
+	return repoRoot
+}
+
+// OpenObjectsRoot opens the objects directory and registers cleanup on the
+// caller.
+func (testRepo *TestRepo) OpenObjectsRoot(tb testing.TB) *os.Root {
+	tb.Helper()
+
+	gitRoot := testRepo.OpenGitRoot(tb)
+
+	objectsRoot, err := gitRoot.OpenRoot("objects")
+	if err != nil {
+		tb.Fatalf("OpenRoot(objects): %v", err)
+	}
+
+	tb.Cleanup(func() {
+		_ = objectsRoot.Close()
+	})
+
+	return objectsRoot
+}
+
+// OpenPackRoot opens the objects/pack directory and registers cleanup on the
+// caller.
+func (testRepo *TestRepo) OpenPackRoot(tb testing.TB) *os.Root {
+	tb.Helper()
+
+	objectsRoot := testRepo.OpenObjectsRoot(tb)
+
+	packRoot, err := objectsRoot.OpenRoot("pack")
+	if err != nil {
+		tb.Fatalf("OpenRoot(pack): %v", err)
+	}
+
+	tb.Cleanup(func() {
+		_ = packRoot.Close()
+	})
+
+	return packRoot
+}
diff --git a/internal/testgit/repo_properties.go b/internal/testgit/repo_properties.go
index 3a489124..703cef1c 100644
--- a/internal/testgit/repo_properties.go
+++ b/internal/testgit/repo_properties.go
@@ -2,11 +2,6 @@ package testgit
 
 import "codeberg.org/lindenii/furgit/objectid"
 
-// Dir returns the repository directory path.
-func (testRepo *TestRepo) Dir() string {
-	return testRepo.dir
-}
-
 // Algorithm returns the object ID algorithm configured for this repository.
 func (testRepo *TestRepo) Algorithm() objectid.Algorithm {
 	return testRepo.algo
diff --git a/internal/testgit/repo_remove_loose_object.go b/internal/testgit/repo_remove_loose_object.go
new file mode 100644
index 00000000..ec3d8c2d
--- /dev/null
+++ b/internal/testgit/repo_remove_loose_object.go
@@ -0,0 +1,22 @@
+package testgit
+
+import (
+	"fmt"
+	"testing"
+
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// RemoveLooseObject removes one loose object file from the repository.
+func (testRepo *TestRepo) RemoveLooseObject(tb testing.TB, id objectid.ObjectID) {
+	tb.Helper()
+
+	root := testRepo.OpenObjectsRoot(tb)
+	hex := id.String()
+	path := fmt.Sprintf("%s/%s", hex[:2], hex[2:])
+
+	err := root.Remove(path)
+	if err != nil {
+		tb.Fatalf("remove loose object %s: %v", id, err)
+	}
+}
diff --git a/internal/testgit/repo_run.go b/internal/testgit/repo_run.go
index 162a0d72..448b88f0 100644
--- a/internal/testgit/repo_run.go
+++ b/internal/testgit/repo_run.go
@@ -22,6 +22,15 @@ func (testRepo *TestRepo) RunBytes(tb testing.TB, args ...string) []byte {
 	return testRepo.runBytes(tb, nil, testRepo.dir, args...)
 }
 
+// RunE executes git and returns trimmed textual output plus any command error.
+func (testRepo *TestRepo) RunE(tb testing.TB, args ...string) (string, error) {
+	tb.Helper()
+
+	out, err := testRepo.runBytesE(nil, testRepo.dir, args...)
+
+	return strings.TrimSpace(string(out)), err
+}
+
 // RunInput executes git with stdin and returns trimmed textual output.
 func (testRepo *TestRepo) RunInput(tb testing.TB, stdin []byte, args ...string) string {
 	tb.Helper()
@@ -39,19 +48,48 @@ func (testRepo *TestRepo) RunInputBytes(tb testing.TB, stdin []byte, args ...str
 
 func (testRepo *TestRepo) runBytes(tb testing.TB, stdin []byte, dir string, args ...string) []byte {
 	tb.Helper()
+
+	out, err := testRepo.runBytesE(stdin, dir, args...)
+	if err != nil {
+		tb.Fatalf("git %v failed: %v\n%s", args, err, out)
+	}
+
+	return out
+}
+
+func (testRepo *TestRepo) runBytesE(stdin []byte, dir string, args ...string) ([]byte, error) {
+	return testRepo.runBytesWithEnvNoHelper(stdin, dir, testRepo.env, args...)
+}
+
+// runBytesWithEnv executes git using the supplied environment.
+func (testRepo *TestRepo) runBytesWithEnv(
+	tb testing.TB,
+	stdin []byte,
+	dir string,
+	env []string,
+	args ...string,
+) ([]byte, error) {
+	tb.Helper()
+
+	return testRepo.runBytesWithEnvNoHelper(stdin, dir, env, args...)
+}
+
+// runBytesWithEnvNoHelper executes git using the supplied environment without
+// touching testing helper state.
+func (testRepo *TestRepo) runBytesWithEnvNoHelper(
+	stdin []byte,
+	dir string,
+	env []string,
+	args ...string,
+) ([]byte, error) {
 	//nolint:noctx
 	cmd := exec.Command("git", args...) //#nosec G204
 	cmd.Dir = dir
 
-	cmd.Env = testRepo.env
+	cmd.Env = env
 	if stdin != nil {
 		cmd.Stdin = bytes.NewReader(stdin)
 	}
 
-	out, err := cmd.CombinedOutput()
-	if err != nil {
-		tb.Fatalf("git %v failed: %v\n%s", args, err, out)
-	}
-
-	return out
+	return cmd.CombinedOutput()
 }