17 files changed, 896 insertions, 0 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
+}