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

7 files changed, 832 insertions, 0 deletions

diff --git a/mergebase/base.go b/mergebase/base.go
new file mode 100644
index 00000000..ee0473b3
--- /dev/null
+++ b/mergebase/base.go
@@ -0,0 +1,43 @@
+package mergebase
+
+import (
+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objectstore"
+)
+
+// Base reports one merge base between left and right, if any.
+//
+// Both inputs are peeled through annotated tags before commit traversal.
+func Base(
+	store objectstore.Store,
+	graph *commitgraphread.Reader,
+	left objectid.ObjectID,
+	right objectid.ObjectID,
+) (objectid.ObjectID, bool, error) {
+	query := Query(store, graph, left, right)
+	seq := query.Seq()
+
+	var (
+		first objectid.ObjectID
+		ok    bool
+	)
+
+	seq(func(id objectid.ObjectID) bool {
+		first = id
+		ok = true
+
+		return false
+	})
+
+	err := query.Err()
+	if err != nil {
+		return objectid.ObjectID{}, false, err
+	}
+
+	if !ok {
+		return objectid.ObjectID{}, false, nil
+	}
+
+	return first, true, nil
+}
diff --git a/mergebase/compute.go b/mergebase/compute.go
new file mode 100644
index 00000000..0fae0aed
--- /dev/null
+++ b/mergebase/compute.go
@@ -0,0 +1,56 @@
+package mergebase
+
+import (
+	"slices"
+
+	"codeberg.org/lindenii/furgit/internal/commitquery"
+	"codeberg.org/lindenii/furgit/internal/peel"
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+func (query *Bases) compute() ([]objectid.ObjectID, error) {
+	leftCommit, err := peel.ToCommit(query.store, query.left)
+	if err != nil {
+		return nil, err
+	}
+
+	rightCommit, err := peel.ToCommit(query.store, query.right)
+	if err != nil {
+		return nil, err
+	}
+
+	ctx := commitquery.NewContext(query.store, query.graph)
+
+	leftIdx, err := ctx.ResolveOID(leftCommit)
+	if err != nil {
+		return nil, err
+	}
+
+	rightIdx, err := ctx.ResolveOID(rightCommit)
+	if err != nil {
+		return nil, err
+	}
+
+	candidates, err := commitquery.MergeBases(ctx, leftIdx, rightIdx)
+	if err != nil {
+		return nil, err
+	}
+
+	slices.SortFunc(candidates, func(left, right commitquery.NodeIndex) int {
+		switch {
+		case ctx.CommitTime(left) > ctx.CommitTime(right):
+			return -1
+		case ctx.CommitTime(left) < ctx.CommitTime(right):
+			return 1
+		default:
+			return objectid.Compare(ctx.ID(left), ctx.ID(right))
+		}
+	})
+
+	out := make([]objectid.ObjectID, 0, len(candidates))
+	for _, idx := range candidates {
+		out = append(out, ctx.ID(idx))
+	}
+
+	return out, nil
+}
diff --git a/mergebase/integration_test.go b/mergebase/integration_test.go
new file mode 100644
index 00000000..07180159
--- /dev/null
+++ b/mergebase/integration_test.go
@@ -0,0 +1,308 @@
+package mergebase_test
+
+import (
+	"maps"
+	"slices"
+	"strings"
+	"testing"
+
+	"codeberg.org/lindenii/furgit/internal/testgit"
+	"codeberg.org/lindenii/furgit/mergebase"
+	"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 := mergebase.Query(store, nil, left, tag)
+		got := oidSetFromSeq(query.Seq())
+
+		err := query.Err()
+		if err != nil {
+			t.Fatalf("query.Err(): %v", err)
+		}
+
+		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 := mergebase.Query(store, nil, left, right)
+		got := oidSetFromSeq(query.Seq())
+
+		err := query.Err()
+		if err != nil {
+			t.Fatalf("query.Err(): %v", err)
+		}
+
+		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 := mergebase.Base(store, nil, 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 := mergebase.Query(store, graph, left, right)
+		got := oidSetFromSeq(query.Seq())
+
+		err := query.Err()
+		if err != nil {
+			t.Fatalf("query.Err(): %v", err)
+		}
+
+		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 := mergebase.Base(store, graph, 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)
+
+		got, ok, err := mergebase.Base(store, nil, 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 = mergebase.Base(store, graph, 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)
+		}
+	})
+}
+
+// oidSetFromSeq collects one object ID sequence into a set.
+func oidSetFromSeq(seq func(func(objectid.ObjectID) bool)) map[objectid.ObjectID]struct{} {
+	out := make(map[objectid.ObjectID]struct{})
+
+	seq(func(id objectid.ObjectID) bool {
+		out[id] = struct{}{}
+
+		return true
+	})
+
+	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/mergebase/mergebase.go b/mergebase/mergebase.go
new file mode 100644
index 00000000..dc0bcf6c
--- /dev/null
+++ b/mergebase/mergebase.go
@@ -0,0 +1,19 @@
+// Package mergebase computes best common ancestors between commits.
+package mergebase
+
+import (
+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objectstore"
+)
+
+// Bases is one iterator merge-base query.
+type Bases struct {
+	store objectstore.Store
+	graph *commitgraphread.Reader
+	left  objectid.ObjectID
+	right objectid.ObjectID
+
+	seqUsed bool
+	err     error
+}
diff --git a/mergebase/query.go b/mergebase/query.go
new file mode 100644
index 00000000..e2c7e54f
--- /dev/null
+++ b/mergebase/query.go
@@ -0,0 +1,24 @@
+package mergebase
+
+import (
+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objectstore"
+)
+
+// Query builds one single-use merge-base query over two commit roots.
+//
+// Both inputs are peeled through annotated tags before commit traversal.
+func Query(
+	store objectstore.Store,
+	graph *commitgraphread.Reader,
+	left objectid.ObjectID,
+	right objectid.ObjectID,
+) *Bases {
+	return &Bases{
+		store: store,
+		graph: graph,
+		left:  left,
+		right: right,
+	}
+}
diff --git a/mergebase/seq.go b/mergebase/seq.go
new file mode 100644
index 00000000..e7891737
--- /dev/null
+++ b/mergebase/seq.go
@@ -0,0 +1,47 @@
+package mergebase
+
+import (
+	"errors"
+	"iter"
+
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// Seq returns the merge-base sequence. It is single-use.
+func (query *Bases) Seq() iter.Seq[objectid.ObjectID] {
+	if query.seqUsed {
+		return func(yield func(objectid.ObjectID) bool) {
+			_ = yield
+
+			if query.err == nil {
+				query.err = errors.New("mergebase: sequence already consumed")
+			}
+		}
+	}
+
+	query.seqUsed = true
+
+	return func(yield func(objectid.ObjectID) bool) {
+		if query.err != nil {
+			return
+		}
+
+		bases, err := query.compute()
+		if err != nil {
+			query.err = err
+
+			return
+		}
+
+		for _, id := range bases {
+			if !yield(id) {
+				return
+			}
+		}
+	}
+}
+
+// Err returns the terminal error, if any, once Seq has been consumed.
+func (query *Bases) Err() error {
+	return query.err
+}
diff --git a/mergebase/unit_test.go b/mergebase/unit_test.go
new file mode 100644
index 00000000..55c7c9ae
--- /dev/null
+++ b/mergebase/unit_test.go
@@ -0,0 +1,335 @@
+package mergebase_test
+
+import (
+	"errors"
+	"fmt"
+	"maps"
+	"slices"
+	"testing"
+
+	giterrors "codeberg.org/lindenii/furgit/errors"
+	"codeberg.org/lindenii/furgit/internal/testgit"
+	"codeberg.org/lindenii/furgit/mergebase"
+	"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)
+}
+
+// collectSeq collects one object ID sequence into a slice.
+func collectSeq(seq func(func(objectid.ObjectID) bool)) []objectid.ObjectID {
+	var out []objectid.ObjectID
+
+	seq(func(id objectid.ObjectID) bool {
+		out = append(out, id)
+
+		return true
+	})
+
+	return out
+}
+
+// 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 := mergebase.Query(store, nil, left, right)
+		got := collectSeq(query.Seq())
+
+		err := query.Err()
+		if err != nil {
+			t.Fatalf("query.Err(): %v", err)
+		}
+
+		if !slices.Equal(got, []objectid.ObjectID{left}) {
+			t.Fatalf("Query(left, right)=%v, want [%s]", got, left)
+		}
+
+		first, ok, err := mergebase.Base(store, nil, 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 := mergebase.Query(store, nil, left, tag)
+		got := collectSeq(query.Seq())
+
+		err := query.Err()
+		if err != nil {
+			t.Fatalf("query.Err(): %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 := mergebase.Query(store, nil, left, right)
+		got := toSet(collectSeq(query.Seq()))
+
+		err := query.Err()
+		if err != nil {
+			t.Fatalf("query.Err(): %v", err)
+		}
+
+		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 := mergebase.Base(store, nil, 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 := mergebase.Query(store, nil, left, right)
+		got := collectSeq(query.Seq())
+
+		err := query.Err()
+		if err != nil {
+			t.Fatalf("query.Err(): %v", err)
+		}
+
+		if len(got) != 0 {
+			t.Fatalf("Query(left, right)=%v, want no results", got)
+		}
+
+		_, ok, err := mergebase.Base(store, nil, 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 := mergebase.Query(store, nil, commit, tagToTree)
+		_ = collectSeq(query.Seq())
+
+		err := query.Err()
+		if err == nil {
+			t.Fatal("expected error")
+		}
+
+		var typeErr *giterrors.ObjectTypeError
+		if !errors.As(err, &typeErr) {
+			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 TestQuerySeqSingleUse(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 := mergebase.Query(store, nil, left, right)
+
+		_ = collectSeq(query.Seq())
+		again := collectSeq(query.Seq())
+
+		if len(again) != 0 {
+			t.Fatalf("second Seq() unexpectedly yielded %v", again)
+		}
+
+		err := query.Err()
+		if err == nil {
+			t.Fatal("expected error after second Seq()")
+		}
+
+		if err.Error() != "mergebase: sequence already consumed" {
+			t.Fatalf("unexpected error: %v", err)
+		}
+	})
+}