commitquery: Merge from ancestor and mergebases

21 files changed, 1884 insertions, 0 deletions

diff --git a/commitquery/ancestor.go b/commitquery/ancestor.go
new file mode 100644
index 00000000..671ea460
--- /dev/null
+++ b/commitquery/ancestor.go
@@ -0,0 +1,48 @@
+package commitquery
+
+import "codeberg.org/lindenii/furgit/objectid"
+
+// IsAncestor reports whether ancestor is reachable from descendant through
+// commit parent edges.
+//
+// Both inputs are peeled through annotated tags before commit traversal.
+func (query *Query) IsAncestor(ancestor, descendant objectid.ObjectID) (bool, error) {
+	ancestorIdx, err := query.resolveCommitish(ancestor)
+	if err != nil {
+		return false, err
+	}
+
+	descendantIdx, err := query.resolveCommitish(descendant)
+	if err != nil {
+		return false, err
+	}
+
+	return query.isAncestor(ancestorIdx, descendantIdx)
+}
+
+func (query *Query) isAncestor(ancestor, descendant nodeIndex) (bool, error) {
+	if ancestor == descendant {
+		return true, nil
+	}
+
+	ancestorGeneration := query.effectiveGeneration(ancestor)
+	descendantGeneration := query.effectiveGeneration(descendant)
+
+	if ancestorGeneration != generationInfinity &&
+		descendantGeneration != generationInfinity &&
+		ancestorGeneration > descendantGeneration {
+		return false, nil
+	}
+
+	minGeneration := uint64(0)
+	if ancestorGeneration != generationInfinity {
+		minGeneration = ancestorGeneration
+	}
+
+	err := query.paintDownToCommon(ancestor, []nodeIndex{descendant}, minGeneration)
+	if err != nil {
+		return false, err
+	}
+
+	return query.hasAnyMarks(ancestor, markRight), nil
+}
diff --git a/commitquery/ancestor_integration_test.go b/commitquery/ancestor_integration_test.go
new file mode 100644
index 00000000..a25697aa
--- /dev/null
+++ b/commitquery/ancestor_integration_test.go
@@ -0,0 +1,132 @@
+package commitquery_test
+
+import (
+	"errors"
+	"testing"
+
+	"codeberg.org/lindenii/furgit/commitquery"
+	giterrors "codeberg.org/lindenii/furgit/errors"
+	"codeberg.org/lindenii/furgit/internal/testgit"
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+func TestIsMatchesGitMergeBase(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		testRepo := testgit.NewRepo(t, testgit.RepoOptions{
+			ObjectFormat: algo,
+			Bare:         true,
+			RefFormat:    "files",
+		})
+
+		_, tree1 := testRepo.MakeSingleFileTree(t, "one.txt", []byte("one\n"))
+		c1 := testRepo.CommitTree(t, tree1, "c1")
+
+		_, tree2 := testRepo.MakeSingleFileTree(t, "two.txt", []byte("two\n"))
+		c2 := testRepo.CommitTree(t, tree2, "c2", c1)
+
+		_, tree3 := testRepo.MakeSingleFileTree(t, "three.txt", []byte("three\n"))
+		c3 := testRepo.CommitTree(t, tree3, "c3", c2)
+
+		tag := testRepo.TagAnnotated(t, "tip", c2, "tip")
+
+		store := testRepo.OpenObjectStore(t)
+
+		got, err := commitquery.New(store, nil).IsAncestor(c1, tag)
+		if err != nil {
+			t.Fatalf("Is(c1, tag): %v", err)
+		}
+
+		want := gitMergeBaseIsAncestor(t, testRepo, c1, c2)
+		if got != want {
+			t.Fatalf("Is(c1, tag)=%v, want %v", got, want)
+		}
+
+		got, err = commitquery.New(store, nil).IsAncestor(c3, c2)
+		if err != nil {
+			t.Fatalf("Is(c3, c2): %v", err)
+		}
+
+		want = gitMergeBaseIsAncestor(t, testRepo, c3, c2)
+		if got != want {
+			t.Fatalf("Is(c3, c2)=%v, want %v", got, want)
+		}
+	})
+}
+
+func TestIsMatchesGitMergeBaseWithCommitGraph(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		testRepo := testgit.NewRepo(t, testgit.RepoOptions{
+			ObjectFormat: algo,
+			Bare:         true,
+			RefFormat:    "files",
+		})
+
+		_, tree1 := testRepo.MakeSingleFileTree(t, "one.txt", []byte("one\n"))
+		c1 := testRepo.CommitTree(t, tree1, "c1")
+
+		_, tree2 := testRepo.MakeSingleFileTree(t, "two.txt", []byte("two\n"))
+		c2 := testRepo.CommitTree(t, tree2, "c2", c1)
+
+		testRepo.UpdateRef(t, "refs/heads/main", c2)
+		testRepo.SymbolicRef(t, "HEAD", "refs/heads/main")
+		testRepo.CommitGraphWrite(t, "--reachable")
+
+		store := testRepo.OpenObjectStore(t)
+		graph := testRepo.OpenCommitGraph(t)
+
+		got, err := commitquery.New(store, graph).IsAncestor(c1, c2)
+		if err != nil {
+			t.Fatalf("Is(c1, c2): %v", err)
+		}
+
+		want := gitMergeBaseIsAncestor(t, testRepo, c1, c2)
+		if got != want {
+			t.Fatalf("Is(c1, c2)=%v, want %v", got, want)
+		}
+	})
+}
+
+func TestIsMissingObject(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		testRepo := testgit.NewRepo(t, testgit.RepoOptions{
+			ObjectFormat: algo,
+			Bare:         true,
+			RefFormat:    "files",
+		})
+
+		_, treeID, commitID := testRepo.MakeCommit(t, "missing")
+
+		testRepo.RemoveLooseObject(t, treeID)
+
+		store := testRepo.OpenObjectStore(t)
+
+		_, err := commitquery.New(store, nil).IsAncestor(treeID, commitID)
+		if err == nil {
+			t.Fatal("expected error")
+		}
+
+		missing, ok := errors.AsType[*giterrors.ObjectMissingError](err)
+		if !ok {
+			t.Fatalf("expected ObjectMissingError, got %T (%v)", err, err)
+		}
+
+		if missing.OID != treeID {
+			t.Fatalf("missing oid = %s, want %s", missing.OID, treeID)
+		}
+	})
+}
+
+// gitMergeBaseIsAncestor reports Git's merge-base ancestry answer.
+func gitMergeBaseIsAncestor(t *testing.T, testRepo *testgit.TestRepo, left, right objectid.ObjectID) bool {
+	t.Helper()
+
+	out := testRepo.Run(t, "merge-base", left.String(), right.String())
+
+	return out == left.String()
+}
diff --git a/commitquery/ancestor_unit_test.go b/commitquery/ancestor_unit_test.go
new file mode 100644
index 00000000..6edb05be
--- /dev/null
+++ b/commitquery/ancestor_unit_test.go
@@ -0,0 +1,117 @@
+package commitquery_test
+
+import (
+	"errors"
+	"fmt"
+	"testing"
+
+	giterrors "codeberg.org/lindenii/furgit/errors"
+	"codeberg.org/lindenii/furgit/internal/testgit"
+	"codeberg.org/lindenii/furgit/object"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objectstore/memory"
+	"codeberg.org/lindenii/furgit/objecttype"
+
+	"codeberg.org/lindenii/furgit/commitquery"
+)
+
+// ancestorCommitBody serializes one minimal commit body.
+func ancestorCommitBody(tree objectid.ObjectID, parents ...objectid.ObjectID) []byte {
+	buf := fmt.Appendf(nil, "tree %s\n", tree.String())
+	for _, parent := range parents {
+		buf = append(buf, fmt.Appendf(nil, "parent %s\n", parent.String())...)
+	}
+
+	buf = append(buf, []byte("\nmsg\n")...)
+
+	return buf
+}
+
+// ancestorTagBody serializes one minimal annotated tag body.
+func ancestorTagBody(target objectid.ObjectID, targetType objecttype.Type) []byte {
+	targetName, ok := objecttype.Name(targetType)
+	if !ok {
+		panic("invalid tag target type")
+	}
+
+	return fmt.Appendf(nil, "object %s\ntype %s\ntag t\n\nmsg\n", target.String(), targetName)
+}
+
+// mustSerializeAncestorTree serializes one tree or fails the test.
+func mustSerializeAncestorTree(tb testing.TB, tree *object.Tree) []byte {
+	tb.Helper()
+
+	body, err := tree.SerializeWithoutHeader()
+	if err != nil {
+		tb.Fatalf("SerializeWithoutHeader: %v", err)
+	}
+
+	return body
+}
+
+func TestIs(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		store := memory.New(algo)
+		blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n"))
+		tree := store.AddObject(objecttype.TypeTree, mustSerializeAncestorTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("f"),
+			ID:   blob,
+		}}}))
+		c1 := store.AddObject(objecttype.TypeCommit, ancestorCommitBody(tree))
+		c2 := store.AddObject(objecttype.TypeCommit, ancestorCommitBody(tree, c1))
+		otherBlob := store.AddObject(objecttype.TypeBlob, []byte("other-blob\n"))
+		otherTree := store.AddObject(objecttype.TypeTree, mustSerializeAncestorTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("g"),
+			ID:   otherBlob,
+		}}}))
+		c3 := store.AddObject(objecttype.TypeCommit, ancestorCommitBody(otherTree))
+		tag := store.AddObject(objecttype.TypeTag, ancestorTagBody(c2, objecttype.TypeCommit))
+
+		ok, err := commitquery.New(store, nil).IsAncestor(c1, tag)
+		if err != nil {
+			t.Fatalf("Is(c1, tag): %v", err)
+		}
+
+		if !ok {
+			t.Fatal("expected c1 to be ancestor of tag->c2")
+		}
+
+		ok, err = commitquery.New(store, nil).IsAncestor(c3, c2)
+		if err != nil {
+			t.Fatalf("Is(c3, c2): %v", err)
+		}
+
+		if ok {
+			t.Fatal("did not expect c3 to be ancestor of c2")
+		}
+	})
+}
+
+func TestIsRejectsNonCommitAfterPeel(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		store := memory.New(algo)
+		blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n"))
+		tree := store.AddObject(objecttype.TypeTree, mustSerializeAncestorTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("f"),
+			ID:   blob,
+		}}}))
+		commit := store.AddObject(objecttype.TypeCommit, ancestorCommitBody(tree))
+		tagToTree := store.AddObject(objecttype.TypeTag, ancestorTagBody(tree, objecttype.TypeTree))
+
+		_, err := commitquery.New(store, nil).IsAncestor(commit, tagToTree)
+		if err == nil {
+			t.Fatal("expected error")
+		}
+
+		if _, ok := errors.AsType[*giterrors.ObjectTypeError](err); !ok {
+			t.Fatalf("expected ObjectTypeError, got %T (%v)", err, err)
+		}
+	})
+}
diff --git a/commitquery/bits.go b/commitquery/bits.go
new file mode 100644
index 00000000..36ffff29
--- /dev/null
+++ b/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/commitquery/commit.go b/commitquery/commit.go
new file mode 100644
index 00000000..f4709270
--- /dev/null
+++ b/commitquery/commit.go
@@ -0,0 +1,17 @@
+package commitquery
+
+import (
+	commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read"
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// commitData stores the metadata needed by commit-domain queries.
+type commitData struct {
+	ID            objectid.ObjectID
+	Parents       []parentRef
+	CommitTime    int64
+	Generation    uint64
+	HasGeneration bool
+	GraphPos      commitgraphread.Position
+	HasGraphPos   bool
+}
diff --git a/commitquery/compare.go b/commitquery/compare.go
new file mode 100644
index 00000000..f64b5b3f
--- /dev/null
+++ b/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 (query *Query) compare(left, right nodeIndex) int {
+	leftGeneration := query.effectiveGeneration(left)
+	rightGeneration := query.effectiveGeneration(right)
+
+	switch {
+	case leftGeneration < rightGeneration:
+		return -1
+	case leftGeneration > rightGeneration:
+		return 1
+	}
+
+	switch {
+	case query.nodes[left].commitTime < query.nodes[right].commitTime:
+		return -1
+	case query.nodes[left].commitTime > query.nodes[right].commitTime:
+		return 1
+	}
+
+	return objectid.Compare(query.nodes[left].id, query.nodes[right].id)
+}
diff --git a/commitquery/context.go b/commitquery/context.go
new file mode 100644
index 00000000..8e19138e
--- /dev/null
+++ b/commitquery/context.go
@@ -0,0 +1,34 @@
+// Package commitquery answers commit ancestry and merge-base queries.
+package commitquery
+
+import (
+	commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objectstore"
+)
+
+// Query owns the mutable node arena for commit-domain queries over one object
+// store.
+type Query struct {
+	store objectstore.Store
+	graph *commitgraphread.Reader
+
+	nodes []node
+
+	byOID      map[objectid.ObjectID]nodeIndex
+	byGraphPos map[commitgraphread.Position]nodeIndex
+
+	markPhase uint32
+	touched   []nodeIndex
+}
+
+// New builds one reusable commit query arena over one object store and optional
+// commit-graph reader.
+func New(store objectstore.Store, graph *commitgraphread.Reader) *Query {
+	return &Query{
+		store:      store,
+		graph:      graph,
+		byOID:      make(map[objectid.ObjectID]nodeIndex),
+		byGraphPos: make(map[commitgraphread.Position]nodeIndex),
+	}
+}
diff --git a/commitquery/errors.go b/commitquery/errors.go
new file mode 100644
index 00000000..e99011d0
--- /dev/null
+++ b/commitquery/errors.go
@@ -0,0 +1,5 @@
+package commitquery
+
+import "errors"
+
+var errBadGenerationOrder = errors.New("commitquery: priority queue violated generation ordering")
diff --git a/commitquery/generation.go b/commitquery/generation.go
new file mode 100644
index 00000000..05228b29
--- /dev/null
+++ b/commitquery/generation.go
@@ -0,0 +1,43 @@
+package commitquery
+
+import (
+	"math"
+
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// EffectiveGeneration returns one node's generation value.
+func (query *Query) effectiveGeneration(idx nodeIndex) uint64 {
+	if !query.nodes[idx].hasGeneration {
+		return generationInfinity
+	}
+
+	return query.nodes[idx].generation
+}
+
+const (
+	generationInfinity = uint64(math.MaxUint64)
+)
+
+func compareByGeneration(query *Query) func(nodeIndex, nodeIndex) int {
+	return func(left, right nodeIndex) int {
+		leftGeneration := query.effectiveGeneration(left)
+		rightGeneration := query.effectiveGeneration(right)
+
+		switch {
+		case leftGeneration < rightGeneration:
+			return -1
+		case leftGeneration > rightGeneration:
+			return 1
+		}
+
+		switch {
+		case query.nodes[left].commitTime < query.nodes[right].commitTime:
+			return -1
+		case query.nodes[left].commitTime > query.nodes[right].commitTime:
+			return 1
+		}
+
+		return objectid.Compare(query.nodes[left].id, query.nodes[right].id)
+	}
+}
diff --git a/commitquery/graph_pos.go b/commitquery/graph_pos.go
new file mode 100644
index 00000000..b1d27129
--- /dev/null
+++ b/commitquery/graph_pos.go
@@ -0,0 +1,107 @@
+package commitquery
+
+import commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read"
+
+// resolveGraphPos resolves one commit-graph position to one internal query node.
+func (query *Query) resolveGraphPos(pos commitgraphread.Position) (nodeIndex, error) {
+	idx, ok := query.byGraphPos[pos]
+	if ok {
+		err := query.ensureLoaded(idx)
+		if err != nil {
+			return 0, err
+		}
+
+		return idx, nil
+	}
+
+	commit, err := query.graph.CommitAt(pos)
+	if err != nil {
+		return 0, err
+	}
+
+	idx, ok = query.byOID[commit.OID]
+	if !ok {
+		idx = query.newNode(commit.OID)
+		query.byOID[commit.OID] = idx
+	}
+
+	query.byGraphPos[pos] = idx
+	query.nodes[idx].graphPos = pos
+	query.nodes[idx].hasGraphPos = true
+
+	err = query.loadCommitAtGraphPos(idx, pos)
+	if err != nil {
+		delete(query.byGraphPos, pos)
+
+		return 0, err
+	}
+
+	return idx, nil
+}
+
+// loadByGraphPos populates one node from a commit-graph position.
+func (query *Query) loadByGraphPos(idx nodeIndex) error {
+	pos := query.nodes[idx].graphPos
+
+	return query.loadCommitAtGraphPos(idx, pos)
+}
+
+func (query *Query) loadCommitAtGraphPos(idx nodeIndex, pos commitgraphread.Position) error {
+	commit, err := query.graph.CommitAt(pos)
+	if err != nil {
+		return err
+	}
+
+	parents := make([]parentRef, 0, 2+len(commit.ExtraParents))
+
+	if commit.Parent1.Valid {
+		parentOID, err := query.graph.OIDAt(commit.Parent1.Pos)
+		if err != nil {
+			return err
+		}
+
+		parents = append(parents, parentRef{
+			ID:          parentOID,
+			GraphPos:    commit.Parent1.Pos,
+			HasGraphPos: true,
+		})
+	}
+
+	if commit.Parent2.Valid {
+		parentOID, err := query.graph.OIDAt(commit.Parent2.Pos)
+		if err != nil {
+			return err
+		}
+
+		parents = append(parents, parentRef{
+			ID:          parentOID,
+			GraphPos:    commit.Parent2.Pos,
+			HasGraphPos: true,
+		})
+	}
+
+	for _, parentPos := range commit.ExtraParents {
+		parentOID, err := query.graph.OIDAt(parentPos)
+		if err != nil {
+			return err
+		}
+
+		parents = append(parents, parentRef{
+			ID:          parentOID,
+			GraphPos:    parentPos,
+			HasGraphPos: true,
+		})
+	}
+
+	data := commitData{
+		ID:            commit.OID,
+		Parents:       parents,
+		CommitTime:    commit.CommitTimeUnix,
+		Generation:    commit.GenerationV2,
+		HasGeneration: commit.GenerationV2 != 0,
+		GraphPos:      pos,
+		HasGraphPos:   true,
+	}
+
+	return query.populateNode(idx, data)
+}
diff --git a/commitquery/load.go b/commitquery/load.go
new file mode 100644
index 00000000..58ed7bf3
--- /dev/null
+++ b/commitquery/load.go
@@ -0,0 +1,14 @@
+package commitquery
+
+// ensureLoaded completes one node's metadata load if it has not been loaded yet.
+func (query *Query) ensureLoaded(idx nodeIndex) error {
+	if query.nodes[idx].loaded {
+		return nil
+	}
+
+	if query.nodes[idx].hasGraphPos {
+		return query.loadByGraphPos(idx)
+	}
+
+	return query.loadByOID(idx)
+}
diff --git a/commitquery/marks.go b/commitquery/marks.go
new file mode 100644
index 00000000..de008789
--- /dev/null
+++ b/commitquery/marks.go
@@ -0,0 +1,71 @@
+package commitquery
+
+// Marks returns the mark bits of one internal node.
+func (query *Query) marks(idx nodeIndex) markBits {
+	return query.nodes[idx].marks
+}
+
+// HasAnyMarks reports whether one internal node has any requested bit.
+func (query *Query) hasAnyMarks(idx nodeIndex, bits markBits) bool {
+	return query.nodes[idx].marks&bits != 0
+}
+
+// HasAllMarks reports whether one internal node already has all requested bits.
+func (query *Query) hasAllMarks(idx nodeIndex, bits markBits) bool {
+	return query.nodes[idx].marks&bits == bits
+}
+
+// SetMarks ORs one set of mark bits into one internal node.
+func (query *Query) setMarks(idx nodeIndex, bits markBits) {
+	newBits := bits &^ query.nodes[idx].marks
+	if newBits == 0 {
+		return
+	}
+
+	query.trackTouched(idx)
+	query.nodes[idx].marks |= bits
+}
+
+// ClearMarks removes one set of mark bits from one internal node.
+func (query *Query) clearMarks(idx nodeIndex, bits markBits) {
+	if query.nodes[idx].marks&bits == 0 {
+		return
+	}
+
+	query.trackTouched(idx)
+	query.nodes[idx].marks &^= bits
+}
+
+// BeginMarkPhase starts one tracked mark-mutation phase.
+func (query *Query) beginMarkPhase() {
+	for _, idx := range query.touched {
+		query.nodes[idx].marks = 0
+	}
+
+	query.markPhase++
+	if query.markPhase == 0 {
+		query.markPhase++
+		for i := range query.nodes {
+			query.nodes[i].touchedPhase = 0
+		}
+	}
+
+	query.touched = query.touched[:0]
+}
+
+// ClearTouchedMarks clears the provided bits from all nodes touched in the
+// current mark phase.
+func (query *Query) clearTouchedMarks(bits markBits) {
+	for _, idx := range query.touched {
+		query.nodes[idx].marks &^= bits
+	}
+}
+
+func (query *Query) trackTouched(idx nodeIndex) {
+	if query.nodes[idx].touchedPhase == query.markPhase {
+		return
+	}
+
+	query.nodes[idx].touchedPhase = query.markPhase
+	query.touched = append(query.touched, idx)
+}
diff --git a/commitquery/merge_bases.go b/commitquery/merge_bases.go
new file mode 100644
index 00000000..c63bb82f
--- /dev/null
+++ b/commitquery/merge_bases.go
@@ -0,0 +1,171 @@
+package commitquery
+
+import (
+	"slices"
+
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// MergeBases reports all merge bases in Git's merge-base --all order.
+//
+// Both inputs are peeled through annotated tags before commit traversal.
+func (query *Query) MergeBases(left, right objectid.ObjectID) ([]objectid.ObjectID, error) {
+	leftIdx, err := query.resolveCommitish(left)
+	if err != nil {
+		return nil, err
+	}
+
+	rightIdx, err := query.resolveCommitish(right)
+	if err != nil {
+		return nil, err
+	}
+
+	candidates, err := query.mergeBases(leftIdx, rightIdx)
+	if err != nil {
+		return nil, err
+	}
+
+	slices.SortFunc(candidates, func(left, right nodeIndex) int {
+		switch {
+		case query.commitTime(left) > query.commitTime(right):
+			return -1
+		case query.commitTime(left) < query.commitTime(right):
+			return 1
+		default:
+			return objectid.Compare(query.id(left), query.id(right))
+		}
+	})
+
+	out := make([]objectid.ObjectID, 0, len(candidates))
+	for _, idx := range candidates {
+		out = append(out, query.id(idx))
+	}
+
+	return out, nil
+}
+
+// MergeBase reports one merge base between left and right, if any.
+func (query *Query) MergeBase(left, right objectid.ObjectID) (objectid.ObjectID, bool, error) {
+	bases, err := query.MergeBases(left, right)
+	if err != nil {
+		return objectid.ObjectID{}, false, err
+	}
+
+	if len(bases) == 0 {
+		return objectid.ObjectID{}, false, nil
+	}
+
+	return bases[0], true, nil
+}
+
+func (query *Query) mergeBases(left, right nodeIndex) ([]nodeIndex, error) {
+	if left == right {
+		return []nodeIndex{left}, nil
+	}
+
+	err := query.paintDownToCommon(left, []nodeIndex{right}, 0)
+	if err != nil {
+		return nil, err
+	}
+
+	candidates := query.collectMarkedResults()
+
+	if len(candidates) <= 1 {
+		slices.SortFunc(candidates, query.compare)
+
+		return candidates, nil
+	}
+
+	query.clearTouchedMarks(allMarks)
+
+	reduced, err := removeRedundant(query, candidates)
+	if err != nil {
+		return nil, err
+	}
+
+	slices.SortFunc(reduced, query.compare)
+
+	return reduced, nil
+}
+
+func (query *Query) paintDownToCommon(left nodeIndex, rights []nodeIndex, minGeneration uint64) error {
+	query.beginMarkPhase()
+
+	query.setMarks(left, markLeft)
+
+	if len(rights) == 0 {
+		query.setMarks(left, markResult)
+
+		return nil
+	}
+
+	queue := newPriorityQueue(query)
+	queue.PushNode(left)
+
+	for _, right := range rights {
+		query.setMarks(right, markRight)
+		queue.PushNode(right)
+	}
+
+	lastGeneration := generationInfinity
+
+	for query.queueHasNonStale(queue) {
+		idx := queue.PopNode()
+
+		generation := query.effectiveGeneration(idx)
+		if generation > lastGeneration {
+			return errBadGenerationOrder
+		}
+
+		lastGeneration = generation
+		if generation < minGeneration {
+			break
+		}
+
+		flags := query.marks(idx) & (markLeft | markRight | markStale)
+		if flags == (markLeft | markRight) {
+			query.setMarks(idx, markResult)
+
+			flags |= markStale
+		}
+
+		for _, parent := range query.parents(idx) {
+			if query.hasAllMarks(parent, flags) {
+				continue
+			}
+
+			query.setMarks(parent, flags)
+			queue.PushNode(parent)
+		}
+	}
+
+	return nil
+}
+
+func (query *Query) queueHasNonStale(queue *priorityQueue) bool {
+	for _, idx := range queue.items {
+		if !query.hasAnyMarks(idx, markStale) {
+			return true
+		}
+	}
+
+	return false
+}
+
+func (query *Query) collectMarkedResults() []nodeIndex {
+	out := make([]nodeIndex, 0, 4)
+
+	for _, idx := range query.touched {
+		if !query.hasAnyMarks(idx, markResult) {
+			continue
+		}
+
+		if query.hasAnyMarks(idx, markStale) {
+			continue
+		}
+
+		out = append(out, idx)
+	}
+
+	return out
+}
diff --git a/commitquery/mergebase_integration_test.go b/commitquery/mergebase_integration_test.go
new file mode 100644
index 00000000..30477454
--- /dev/null
+++ b/commitquery/mergebase_integration_test.go
@@ -0,0 +1,311 @@
+package commitquery_test
+
+import (
+	"maps"
+	"slices"
+	"strings"
+	"testing"
+
+	"codeberg.org/lindenii/furgit/commitquery"
+	"codeberg.org/lindenii/furgit/internal/testgit"
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+func TestQueryMatchesGitMergeBaseAll(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		testRepo := testgit.NewRepo(t, testgit.RepoOptions{
+			ObjectFormat: algo,
+			Bare:         true,
+			RefFormat:    "files",
+		})
+
+		_, tree1 := testRepo.MakeSingleFileTree(t, "base.txt", []byte("base\n"))
+		base := testRepo.CommitTree(t, tree1, "base")
+
+		_, tree2 := testRepo.MakeSingleFileTree(t, "left.txt", []byte("left\n"))
+		left := testRepo.CommitTree(t, tree2, "left", base)
+
+		_, tree3 := testRepo.MakeSingleFileTree(t, "right.txt", []byte("right\n"))
+		right := testRepo.CommitTree(t, tree3, "right", base)
+
+		tag := testRepo.TagAnnotated(t, "right-tag", right, "right-tag")
+
+		store := testRepo.OpenObjectStore(t)
+
+		query := commitquery.New(store, nil)
+
+		all, err := query.MergeBases(left, tag)
+		if err != nil {
+			t.Fatalf("query.All(): %v", err)
+		}
+
+		got := oidSetFromSlice(all)
+
+		want := gitMergeBaseAllSet(t, testRepo, left, tag)
+		if !maps.Equal(got, want) {
+			t.Fatalf("Query(left, tag) mismatch:\n got=%v\nwant=%v", sortedOIDStrings(got), sortedOIDStrings(want))
+		}
+	})
+}
+
+func TestQueryCrissCrossMatchesGitMergeBaseAll(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		testRepo := testgit.NewRepo(t, testgit.RepoOptions{
+			ObjectFormat: algo,
+			Bare:         true,
+			RefFormat:    "files",
+		})
+
+		_, tree1 := testRepo.MakeSingleFileTree(t, "root.txt", []byte("root\n"))
+		root := testRepo.CommitTree(t, tree1, "root")
+
+		_, tree2 := testRepo.MakeSingleFileTree(t, "base1.txt", []byte("base1\n"))
+		base1 := testRepo.CommitTree(t, tree2, "base1", root)
+
+		_, tree3 := testRepo.MakeSingleFileTree(t, "base2.txt", []byte("base2\n"))
+		base2 := testRepo.CommitTree(t, tree3, "base2", root)
+
+		_, tree4 := testRepo.MakeSingleFileTree(t, "left.txt", []byte("left\n"))
+		left := testRepo.CommitTree(t, tree4, "left", base1, base2)
+
+		_, tree5 := testRepo.MakeSingleFileTree(t, "right.txt", []byte("right\n"))
+		right := testRepo.CommitTree(t, tree5, "right", base2, base1)
+
+		store := testRepo.OpenObjectStore(t)
+
+		query := commitquery.New(store, nil)
+
+		all, err := query.MergeBases(left, right)
+		if err != nil {
+			t.Fatalf("query.All(): %v", err)
+		}
+
+		got := oidSetFromSlice(all)
+
+		want := gitMergeBaseAllSet(t, testRepo, left, right)
+		if !maps.Equal(got, want) {
+			t.Fatalf("Query(left, right) mismatch:\n got=%v\nwant=%v", sortedOIDStrings(got), sortedOIDStrings(want))
+		}
+
+		first, ok, err := query.MergeBase(left, right)
+		if err != nil {
+			t.Fatalf("Base(left, right): %v", err)
+		}
+
+		if !ok {
+			t.Fatal("Base(left, right) unexpectedly reported no base")
+		}
+
+		if !containsID(want, first) {
+			t.Fatalf("Base(left, right)=%s, want one of %v", first, slices.Collect(maps.Keys(want)))
+		}
+	})
+}
+
+func TestQueryMatchesGitMergeBaseAllWithCommitGraph(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		testRepo := testgit.NewRepo(t, testgit.RepoOptions{
+			ObjectFormat: algo,
+			Bare:         true,
+			RefFormat:    "files",
+		})
+
+		_, tree1 := testRepo.MakeSingleFileTree(t, "root.txt", []byte("root\n"))
+		root := testRepo.CommitTree(t, tree1, "root")
+
+		_, tree2 := testRepo.MakeSingleFileTree(t, "base1.txt", []byte("base1\n"))
+		base1 := testRepo.CommitTree(t, tree2, "base1", root)
+
+		_, tree3 := testRepo.MakeSingleFileTree(t, "base2.txt", []byte("base2\n"))
+		base2 := testRepo.CommitTree(t, tree3, "base2", root)
+
+		_, tree4 := testRepo.MakeSingleFileTree(t, "left.txt", []byte("left\n"))
+		left := testRepo.CommitTree(t, tree4, "left", base1, base2)
+
+		_, tree5 := testRepo.MakeSingleFileTree(t, "right.txt", []byte("right\n"))
+		right := testRepo.CommitTree(t, tree5, "right", base2, base1)
+
+		testRepo.UpdateRef(t, "refs/heads/main", right)
+		testRepo.SymbolicRef(t, "HEAD", "refs/heads/main")
+		testRepo.CommitGraphWrite(t, "--reachable")
+
+		store := testRepo.OpenObjectStore(t)
+		graph := testRepo.OpenCommitGraph(t)
+
+		query := commitquery.New(store, graph)
+
+		all, err := query.MergeBases(left, right)
+		if err != nil {
+			t.Fatalf("query.All(): %v", err)
+		}
+
+		got := oidSetFromSlice(all)
+
+		want := gitMergeBaseAllSet(t, testRepo, left, right)
+		if !maps.Equal(got, want) {
+			t.Fatalf("Query(left, right) with commit-graph mismatch:\n got=%v\nwant=%v", sortedOIDStrings(got), sortedOIDStrings(want))
+		}
+
+		first, ok, err := query.MergeBase(left, right)
+		if err != nil {
+			t.Fatalf("Base(left, right): %v", err)
+		}
+
+		if !ok {
+			t.Fatal("Base(left, right) unexpectedly reported no base")
+		}
+
+		if !containsID(want, first) {
+			t.Fatalf("Base(left, right)=%s, want one of %v", first, slices.Collect(maps.Keys(want)))
+		}
+	})
+}
+
+func TestBaseMatchesGitMergeBaseWithoutAll(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		testRepo := testgit.NewRepo(t, testgit.RepoOptions{
+			ObjectFormat: algo,
+			Bare:         true,
+			RefFormat:    "files",
+		})
+
+		_, tree1 := testRepo.MakeSingleFileTree(t, "root.txt", []byte("root\n"))
+		root := testRepo.CommitTree(t, tree1, "root")
+
+		_, tree2 := testRepo.MakeSingleFileTree(t, "base1.txt", []byte("base1\n"))
+		base1 := testRepo.CommitTreeWithEnv(t, []string{
+			"GIT_AUTHOR_DATE=1234567890 +0000",
+			"GIT_COMMITTER_DATE=1234567890 +0000",
+		}, tree2, "base1", root)
+
+		_, tree3 := testRepo.MakeSingleFileTree(t, "base2.txt", []byte("base2\n"))
+		base2 := testRepo.CommitTreeWithEnv(t, []string{
+			"GIT_AUTHOR_DATE=1234567990 +0000",
+			"GIT_COMMITTER_DATE=1234567990 +0000",
+		}, tree3, "base2", root)
+
+		_, tree4 := testRepo.MakeSingleFileTree(t, "left.txt", []byte("left\n"))
+		left := testRepo.CommitTree(t, tree4, "left", base1, base2)
+
+		_, tree5 := testRepo.MakeSingleFileTree(t, "right.txt", []byte("right\n"))
+		right := testRepo.CommitTree(t, tree5, "right", base2, base1)
+
+		store := testRepo.OpenObjectStore(t)
+
+		query := commitquery.New(store, nil)
+
+		got, ok, err := query.MergeBase(left, right)
+		if err != nil {
+			t.Fatalf("Base(left, right): %v", err)
+		}
+
+		if !ok {
+			t.Fatal("Base(left, right) unexpectedly reported no base")
+		}
+
+		want := gitMergeBaseOne(t, testRepo, left, right)
+		if got != want {
+			t.Fatalf("Base(left, right)=%s, want %s", got, want)
+		}
+
+		testRepo.UpdateRef(t, "refs/heads/main", right)
+		testRepo.SymbolicRef(t, "HEAD", "refs/heads/main")
+		testRepo.CommitGraphWrite(t, "--reachable")
+
+		graph := testRepo.OpenCommitGraph(t)
+
+		got, ok, err = commitquery.New(store, graph).MergeBase(left, right)
+		if err != nil {
+			t.Fatalf("Base(left, right) with commit-graph: %v", err)
+		}
+
+		if !ok {
+			t.Fatal("Base(left, right) with commit-graph unexpectedly reported no base")
+		}
+
+		if got != want {
+			t.Fatalf("Base(left, right) with commit-graph=%s, want %s", got, want)
+		}
+	})
+}
+
+// oidSetFromSlice collects one object ID slice into a set.
+func oidSetFromSlice(ids []objectid.ObjectID) map[objectid.ObjectID]struct{} {
+	out := make(map[objectid.ObjectID]struct{})
+
+	for _, id := range ids {
+		out[id] = struct{}{}
+	}
+
+	return out
+}
+
+// gitMergeBaseAllSet returns Git's merge-base --all output as a set.
+func gitMergeBaseAllSet(
+	t *testing.T,
+	testRepo *testgit.TestRepo,
+	left objectid.ObjectID,
+	right objectid.ObjectID,
+) map[objectid.ObjectID]struct{} {
+	t.Helper()
+
+	out := testRepo.Run(t, "merge-base", "--all", left.String(), right.String())
+	set := make(map[objectid.ObjectID]struct{})
+
+	for line := range strings.SplitSeq(strings.TrimSpace(out), "\n") {
+		line = strings.TrimSpace(line)
+		if line == "" {
+			continue
+		}
+
+		id, err := objectid.ParseHex(testRepo.Algorithm(), line)
+		if err != nil {
+			t.Fatalf("parse merge-base oid %q: %v", line, err)
+		}
+
+		set[id] = struct{}{}
+	}
+
+	return set
+}
+
+// gitMergeBaseOne returns Git's merge-base output without --all.
+func gitMergeBaseOne(
+	t *testing.T,
+	testRepo *testgit.TestRepo,
+	left objectid.ObjectID,
+	right objectid.ObjectID,
+) objectid.ObjectID {
+	t.Helper()
+
+	out := strings.TrimSpace(testRepo.Run(t, "merge-base", left.String(), right.String()))
+	if out == "" {
+		t.Fatal("git merge-base returned no output")
+	}
+
+	id, err := objectid.ParseHex(testRepo.Algorithm(), out)
+	if err != nil {
+		t.Fatalf("parse merge-base oid %q: %v", out, err)
+	}
+
+	return id
+}
+
+func sortedOIDStrings(set map[objectid.ObjectID]struct{}) []string {
+	out := make([]string, 0, len(set))
+	for id := range set {
+		out = append(out, id.String())
+	}
+
+	slices.Sort(out)
+
+	return out
+}
diff --git a/commitquery/mergebase_unit_test.go b/commitquery/mergebase_unit_test.go
new file mode 100644
index 00000000..daa3c3c6
--- /dev/null
+++ b/commitquery/mergebase_unit_test.go
@@ -0,0 +1,332 @@
+package commitquery_test
+
+import (
+	"errors"
+	"fmt"
+	"maps"
+	"slices"
+	"testing"
+
+	"codeberg.org/lindenii/furgit/commitquery"
+	giterrors "codeberg.org/lindenii/furgit/errors"
+	"codeberg.org/lindenii/furgit/internal/testgit"
+	"codeberg.org/lindenii/furgit/object"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objectstore/memory"
+	"codeberg.org/lindenii/furgit/objecttype"
+)
+
+// commitBody serializes one minimal commit body.
+func commitBody(tree objectid.ObjectID, parents ...objectid.ObjectID) []byte {
+	buf := fmt.Appendf(nil, "tree %s\n", tree.String())
+	for _, parent := range parents {
+		buf = append(buf, fmt.Appendf(nil, "parent %s\n", parent.String())...)
+	}
+
+	buf = append(buf, []byte("\nmsg\n")...)
+
+	return buf
+}
+
+// tagBody serializes one minimal annotated tag body.
+func tagBody(target objectid.ObjectID, targetType objecttype.Type) []byte {
+	targetName, ok := objecttype.Name(targetType)
+	if !ok {
+		panic("invalid tag target type")
+	}
+
+	return fmt.Appendf(nil, "object %s\ntype %s\ntag t\n\nmsg\n", target.String(), targetName)
+}
+
+// toSet converts one slice of object IDs into a set.
+func toSet(ids []objectid.ObjectID) map[objectid.ObjectID]struct{} {
+	set := make(map[objectid.ObjectID]struct{}, len(ids))
+	for _, id := range ids {
+		set[id] = struct{}{}
+	}
+
+	return set
+}
+
+// containsID reports whether one set contains one object ID.
+func containsID(set map[objectid.ObjectID]struct{}, id objectid.ObjectID) bool {
+	_, ok := set[id]
+
+	return ok
+}
+
+// mustSerializeTree serializes one tree or fails the test.
+func mustSerializeTree(tb testing.TB, tree *object.Tree) []byte {
+	tb.Helper()
+
+	body, err := tree.SerializeWithoutHeader()
+	if err != nil {
+		tb.Fatalf("SerializeWithoutHeader: %v", err)
+	}
+
+	return body
+}
+
+// TestQueryLinearHistory reports one linear-history merge base.
+func TestQueryLinearHistory(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		store := memory.New(algo)
+		blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n"))
+		tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("f"),
+			ID:   blob,
+		}}}))
+		base := store.AddObject(objecttype.TypeCommit, commitBody(tree))
+		left := store.AddObject(objecttype.TypeCommit, commitBody(tree, base))
+		right := store.AddObject(objecttype.TypeCommit, commitBody(tree, left))
+
+		query := commitquery.New(store, nil)
+
+		got, err := query.MergeBases(left, right)
+		if err != nil {
+			t.Fatalf("query.All(): %v", err)
+		}
+
+		if !slices.Equal(got, []objectid.ObjectID{left}) {
+			t.Fatalf("Query(left, right)=%v, want [%s]", got, left)
+		}
+
+		first, ok, err := query.MergeBase(left, right)
+		if err != nil {
+			t.Fatalf("Base(left, right): %v", err)
+		}
+
+		if !ok {
+			t.Fatal("Base(left, right) unexpectedly reported no base")
+		}
+
+		if first != left {
+			t.Fatalf("Base(left, right)=%s, want %s", first, left)
+		}
+	})
+}
+
+func TestQueryPeelsAnnotatedTags(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		store := memory.New(algo)
+		blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n"))
+		leftTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("left"),
+			ID:   blob,
+		}}}))
+		rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("right"),
+			ID:   blob,
+		}}}))
+		base := store.AddObject(objecttype.TypeCommit, commitBody(leftTree))
+		left := store.AddObject(objecttype.TypeCommit, commitBody(leftTree, base))
+		right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree, base))
+		tag := store.AddObject(objecttype.TypeTag, tagBody(right, objecttype.TypeCommit))
+
+		query := commitquery.New(store, nil)
+
+		got, err := query.MergeBases(left, tag)
+		if err != nil {
+			t.Fatalf("query.All(): %v", err)
+		}
+
+		if !slices.Equal(got, []objectid.ObjectID{base}) {
+			t.Fatalf("Query(left, tag)=%v, want [%s]", got, base)
+		}
+	})
+}
+
+func TestQueryCrissCrossReturnsAllBestCommonAncestors(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		store := memory.New(algo)
+		blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n"))
+		rootTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("root"),
+			ID:   blob,
+		}}}))
+		base1Tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("base1"),
+			ID:   blob,
+		}}}))
+		base2Tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("base2"),
+			ID:   blob,
+		}}}))
+		leftTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("left"),
+			ID:   blob,
+		}}}))
+		rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("right"),
+			ID:   blob,
+		}}}))
+		root := store.AddObject(objecttype.TypeCommit, commitBody(rootTree))
+		base1 := store.AddObject(objecttype.TypeCommit, commitBody(base1Tree, root))
+		base2 := store.AddObject(objecttype.TypeCommit, commitBody(base2Tree, root))
+		left := store.AddObject(objecttype.TypeCommit, commitBody(leftTree, base1, base2))
+		right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree, base2, base1))
+
+		query := commitquery.New(store, nil)
+
+		all, err := query.MergeBases(left, right)
+		if err != nil {
+			t.Fatalf("query.All(): %v", err)
+		}
+
+		got := toSet(all)
+
+		want := map[objectid.ObjectID]struct{}{base1: {}, base2: {}}
+		if !maps.Equal(got, want) {
+			t.Fatalf("Query(left, right)=%v, want %v", slices.Collect(maps.Keys(got)), slices.Collect(maps.Keys(want)))
+		}
+
+		first, ok, err := query.MergeBase(left, right)
+		if err != nil {
+			t.Fatalf("Base(left, right): %v", err)
+		}
+
+		if !ok {
+			t.Fatal("Base(left, right) unexpectedly reported no base")
+		}
+
+		if !containsID(want, first) {
+			t.Fatalf("Base(left, right)=%s, want one of %v", first, slices.Collect(maps.Keys(want)))
+		}
+	})
+}
+
+func TestQueryReturnsNoResultWhenNoCommonAncestorExists(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		store := memory.New(algo)
+		leftBlob := store.AddObject(objecttype.TypeBlob, []byte("left\n"))
+		leftTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("left"),
+			ID:   leftBlob,
+		}}}))
+		rightBlob := store.AddObject(objecttype.TypeBlob, []byte("right\n"))
+		rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("right"),
+			ID:   rightBlob,
+		}}}))
+		left := store.AddObject(objecttype.TypeCommit, commitBody(leftTree))
+		right := store.AddObject(objecttype.TypeCommit, commitBody(rightTree))
+
+		query := commitquery.New(store, nil)
+
+		got, err := query.MergeBases(left, right)
+		if err != nil {
+			t.Fatalf("query.All(): %v", err)
+		}
+
+		if len(got) != 0 {
+			t.Fatalf("Query(left, right)=%v, want no results", got)
+		}
+
+		_, ok, err := query.MergeBase(left, right)
+		if err != nil {
+			t.Fatalf("Base(left, right): %v", err)
+		}
+
+		if ok {
+			t.Fatal("Base(left, right) unexpectedly reported a base")
+		}
+	})
+}
+
+func TestQueryRejectsNonCommitAfterPeel(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		store := memory.New(algo)
+		blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n"))
+		tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("f"),
+			ID:   blob,
+		}}}))
+		commit := store.AddObject(objecttype.TypeCommit, commitBody(tree))
+		tagToTree := store.AddObject(objecttype.TypeTag, tagBody(tree, objecttype.TypeTree))
+
+		query := commitquery.New(store, nil)
+
+		_, err := query.MergeBases(commit, tagToTree)
+		if err == nil {
+			t.Fatal("expected error")
+		}
+
+		typeErr, ok := errors.AsType[*giterrors.ObjectTypeError](err)
+		if !ok {
+			t.Fatalf("expected ObjectTypeError, got %T (%v)", err, err)
+		}
+
+		if typeErr.Got != objecttype.TypeTree || typeErr.Want != objecttype.TypeCommit {
+			t.Fatalf("unexpected type error: %+v", typeErr)
+		}
+	})
+}
+
+func TestQueryAllIsRepeatable(t *testing.T) {
+	t.Parallel()
+
+	testgit.ForEachAlgorithm(t, func(t *testing.T, algo objectid.Algorithm) { //nolint:thelper
+		store := memory.New(algo)
+		blob := store.AddObject(objecttype.TypeBlob, []byte("blob\n"))
+		tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{
+			Mode: object.FileModeRegular,
+			Name: []byte("f"),
+			ID:   blob,
+		}}}))
+		base := store.AddObject(objecttype.TypeCommit, commitBody(tree))
+		left := store.AddObject(objecttype.TypeCommit, commitBody(tree, base))
+		right := store.AddObject(objecttype.TypeCommit, commitBody(tree, left))
+
+		query := commitquery.New(store, nil)
+
+		first, err := query.MergeBases(left, right)
+		if err != nil {
+			t.Fatalf("query.MergeBases() first call: %v", err)
+		}
+
+		again, err := query.MergeBases(left, right)
+		if err != nil {
+			t.Fatalf("query.MergeBases() second call: %v", err)
+		}
+
+		if !slices.Equal(again, first) {
+			t.Fatalf("second All()=%v, want %v", again, first)
+		}
+
+		if len(first) == 0 {
+			t.Fatal("first MergeBases() unexpectedly returned no results")
+		}
+
+		first[0] = objectid.ObjectID{}
+
+		third, err := query.MergeBases(left, right)
+		if err != nil {
+			t.Fatalf("query.MergeBases() third call: %v", err)
+		}
+
+		if third[0] == (objectid.ObjectID{}) {
+			t.Fatal("query.MergeBases() exposed internal slice state")
+		}
+	})
+}
diff --git a/commitquery/node.go b/commitquery/node.go
new file mode 100644
index 00000000..cd357631
--- /dev/null
+++ b/commitquery/node.go
@@ -0,0 +1,39 @@
+package commitquery
+
+import (
+	commitgraphread "codeberg.org/lindenii/furgit/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 (query *Query) newNode(id objectid.ObjectID) nodeIndex {
+	count := len(query.nodes)
+
+	idx := nodeIndex(count)
+
+	query.nodes = append(query.nodes, node{id: id})
+
+	return idx
+}
diff --git a/commitquery/oid.go b/commitquery/oid.go
new file mode 100644
index 00000000..68adbf5d
--- /dev/null
+++ b/commitquery/oid.go
@@ -0,0 +1,101 @@
+package commitquery
+
+import (
+	stderrors "errors"
+
+	commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read"
+	giterrors "codeberg.org/lindenii/furgit/errors"
+	"codeberg.org/lindenii/furgit/internal/peel"
+	"codeberg.org/lindenii/furgit/object"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objectstore"
+	"codeberg.org/lindenii/furgit/objecttype"
+)
+
+func (query *Query) id(idx nodeIndex) objectid.ObjectID {
+	return query.nodes[idx].id
+}
+
+func (query *Query) commitTime(idx nodeIndex) int64 {
+	return query.nodes[idx].commitTime
+}
+
+func (query *Query) resolveOID(id objectid.ObjectID) (nodeIndex, error) {
+	idx, ok := query.byOID[id]
+	if ok {
+		err := query.ensureLoaded(idx)
+		if err != nil {
+			return 0, err
+		}
+
+		return idx, nil
+	}
+
+	idx = query.newNode(id)
+	query.byOID[id] = idx
+
+	err := query.loadByOID(idx)
+	if err != nil {
+		delete(query.byOID, id)
+
+		return 0, err
+	}
+
+	return idx, nil
+}
+
+func (query *Query) resolveCommitish(id objectid.ObjectID) (nodeIndex, error) {
+	commitID, err := peel.ToCommit(query.store, id)
+	if err != nil {
+		return 0, err
+	}
+
+	return query.resolveOID(commitID)
+}
+
+// loadByOID populates one node from an object ID.
+func (query *Query) loadByOID(idx nodeIndex) error {
+	id := query.nodes[idx].id
+
+	if query.graph != nil {
+		pos, err := query.graph.Lookup(id)
+		if err != nil {
+			if _, ok := stderrors.AsType[*commitgraphread.NotFoundError](err); !ok {
+				return err
+			}
+		} else {
+			return query.loadCommitAtGraphPos(idx, pos)
+		}
+	}
+
+	ty, content, err := query.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([]parentRef, 0, len(commitObj.Parents))
+	for _, parentID := range commitObj.Parents {
+		parents = append(parents, parentRef{ID: parentID})
+	}
+
+	commit := commitData{
+		ID:         id,
+		Parents:    parents,
+		CommitTime: commitObj.Committer.WhenUnix,
+	}
+
+	return query.populateNode(idx, commit)
+}
diff --git a/commitquery/parent.go b/commitquery/parent.go
new file mode 100644
index 00000000..1c59e102
--- /dev/null
+++ b/commitquery/parent.go
@@ -0,0 +1,27 @@
+package commitquery
+
+import (
+	commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read"
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// parentRef references one commit parent.
+type parentRef struct {
+	ID          objectid.ObjectID
+	GraphPos    commitgraphread.Position
+	HasGraphPos bool
+}
+
+// Parents returns resolved parent node indices for one internal node.
+func (query *Query) parents(idx nodeIndex) []nodeIndex {
+	return query.nodes[idx].parents
+}
+
+// resolveParent resolves one parent descriptor to one internal node.
+func (query *Query) resolveParent(parent parentRef) (nodeIndex, error) {
+	if parent.HasGraphPos {
+		return query.resolveGraphPos(parent.GraphPos)
+	}
+
+	return query.resolveOID(parent.ID)
+}
diff --git a/commitquery/populate.go b/commitquery/populate.go
new file mode 100644
index 00000000..cc71955f
--- /dev/null
+++ b/commitquery/populate.go
@@ -0,0 +1,42 @@
+package commitquery
+
+import "fmt"
+
+// populateNode fills one node's metadata and resolves its parents.
+func (query *Query) populateNode(idx nodeIndex, commit commitData) error {
+	if query.nodes[idx].loaded {
+		if query.nodes[idx].id != commit.ID {
+			return fmt.Errorf("commitquery: node identity mismatch: have %s, got %s", query.nodes[idx].id, commit.ID)
+		}
+
+		return nil
+	}
+
+	query.nodes[idx].id = commit.ID
+	query.nodes[idx].commitTime = commit.CommitTime
+	query.nodes[idx].generation = commit.Generation
+	query.nodes[idx].hasGeneration = commit.HasGeneration
+
+	if commit.HasGraphPos {
+		query.nodes[idx].graphPos = commit.GraphPos
+		query.nodes[idx].hasGraphPos = true
+		query.byGraphPos[commit.GraphPos] = idx
+	}
+
+	query.nodes[idx].loaded = true
+	query.nodes[idx].parents = query.nodes[idx].parents[:0]
+
+	for _, parent := range commit.Parents {
+		parentIdx, err := query.resolveParent(parent)
+		if err != nil {
+			query.nodes[idx].loaded = false
+			query.nodes[idx].parents = nil
+
+			return err
+		}
+
+		query.nodes[idx].parents = append(query.nodes[idx].parents, parentIdx)
+	}
+
+	return nil
+}
diff --git a/commitquery/priority_queue.go b/commitquery/priority_queue.go
new file mode 100644
index 00000000..0ca57f7d
--- /dev/null
+++ b/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 {
+	query *Query
+	items []nodeIndex
+}
+
+// newPriorityQueue builds one empty priority queue over one query context.
+func newPriorityQueue(query *Query) *priorityQueue {
+	queue := &priorityQueue{query: query}
+	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.query.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/commitquery/reduce.go b/commitquery/reduce.go
new file mode 100644
index 00000000..ac85d619
--- /dev/null
+++ b/commitquery/reduce.go
@@ -0,0 +1,166 @@
+package commitquery
+
+import (
+	"slices"
+)
+
+// removeRedundant removes redundant merge-base candidates.
+func removeRedundant(query *Query, candidates []nodeIndex) ([]nodeIndex, error) {
+	for _, idx := range candidates {
+		if query.effectiveGeneration(idx) != generationInfinity {
+			return removeRedundantWithGen(query, candidates), nil
+		}
+	}
+
+	return removeRedundantNoGen(query, candidates)
+}
+
+func removeRedundantNoGen(query *Query, 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 := query.effectiveGeneration(candidate)
+
+		for j, other := range candidates {
+			if i == j || redundant[j] {
+				continue
+			}
+
+			work = append(work, other)
+			filledIndex = append(filledIndex, j)
+
+			otherGeneration := query.effectiveGeneration(other)
+			if otherGeneration < minGeneration {
+				minGeneration = otherGeneration
+			}
+		}
+
+		err := query.paintDownToCommon(candidate, work, minGeneration)
+		if err != nil {
+			return nil, err
+		}
+
+		if query.hasAnyMarks(candidate, markRight) {
+			redundant[i] = true
+		}
+
+		for j, other := range work {
+			if query.hasAnyMarks(other, markLeft) {
+				redundant[filledIndex[j]] = true
+			}
+		}
+
+		query.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(query *Query, candidates []nodeIndex) []nodeIndex {
+	sorted := append([]nodeIndex(nil), candidates...)
+	slices.SortFunc(sorted, compareByGeneration(query))
+
+	minGeneration := query.effectiveGeneration(sorted[0])
+	minGenPos := 0
+	countStillIndependent := len(candidates)
+
+	query.beginMarkPhase()
+
+	walkStart := make([]nodeIndex, 0, len(candidates)*2)
+
+	for _, idx := range candidates {
+		query.setMarks(idx, markResult)
+
+		for _, parent := range query.parents(idx) {
+			if query.hasAnyMarks(parent, markStale) {
+				continue
+			}
+
+			query.setMarks(parent, markStale)
+			walkStart = append(walkStart, parent)
+		}
+	}
+
+	slices.SortFunc(walkStart, compareByGeneration(query))
+
+	for _, idx := range walkStart {
+		query.clearMarks(idx, markStale)
+	}
+
+	for i := len(walkStart) - 1; i >= 0 && countStillIndependent > 1; i-- {
+		stack := []nodeIndex{walkStart[i]}
+		query.setMarks(walkStart[i], markStale)
+
+		for len(stack) > 0 {
+			top := stack[len(stack)-1]
+
+			if query.hasAnyMarks(top, markResult) {
+				query.clearMarks(top, markResult)
+
+				countStillIndependent--
+				if countStillIndependent <= 1 {
+					break
+				}
+
+				if top == sorted[minGenPos] {
+					for minGenPos < len(sorted)-1 && query.hasAnyMarks(sorted[minGenPos], markStale) {
+						minGenPos++
+					}
+
+					minGeneration = query.effectiveGeneration(sorted[minGenPos])
+				}
+			}
+
+			if query.effectiveGeneration(top) < minGeneration {
+				stack = stack[:len(stack)-1]
+
+				continue
+			}
+
+			pushed := false
+
+			for _, parent := range query.parents(top) {
+				if query.hasAnyMarks(parent, markStale) {
+					continue
+				}
+
+				query.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 !query.hasAnyMarks(idx, markStale) {
+			out = append(out, idx)
+		}
+	}
+
+	query.clearTouchedMarks(markStale | markResult)
+
+	return out
+}