shithub: furgit

--- a/ancestor/ancestor.go

+++ /dev/null

@@ -1,45 +1,0 @@

-// Package ancestor answers commit ancestry queries.

-package ancestor

-import (

-	commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read"

-	"codeberg.org/lindenii/furgit/internal/commitquery"

-	"codeberg.org/lindenii/furgit/internal/peel"

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

-	"codeberg.org/lindenii/furgit/objectstore"

-)

-// Is reports whether ancestor is reachable from descendant through commit

-// parent edges.

-//

-// Both inputs are peeled through annotated tags before commit traversal.

-func Is(

-	store objectstore.Store,

-	graph *commitgraphread.Reader,

-	ancestor objectid.ObjectID,

-	descendant objectid.ObjectID,

-) (bool, error) {

-	ancestorCommit, err := peel.ToCommit(store, ancestor)

-	if err != nil {

-		return false, err

-	}

-	descendantCommit, err := peel.ToCommit(store, descendant)

-	if err != nil {

-		return false, err

-	}

-	ctx := commitquery.NewContext(store, graph)

-	ancestorIdx, err := ctx.ResolveOID(ancestorCommit)

-	if err != nil {

-		return false, err

-	}

-	descendantIdx, err := ctx.ResolveOID(descendantCommit)

-	if err != nil {

-		return false, err

-	}

-	return commitquery.IsAncestor(ctx, ancestorIdx, descendantIdx)

-}

--- a/ancestor/integration_test.go

+++ /dev/null

@@ -1,133 +1,0 @@

-package ancestor_test

-import (

-	"errors"

-	"testing"

-	giterrors "codeberg.org/lindenii/furgit/errors"

-	"codeberg.org/lindenii/furgit/internal/testgit"

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

-	"codeberg.org/lindenii/furgit/ancestor"

-)

-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 := ancestor.Is(store, nil, 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 = ancestor.Is(store, nil, 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 := ancestor.Is(store, graph, 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 := ancestor.Is(store, nil, 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()

-}

--- a/ancestor/unit_test.go

+++ /dev/null

@@ -1,117 +1,0 @@

-package ancestor_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/ancestor"

-)

-// 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)

-}

-// 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

-}

-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, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{

-			Mode: object.FileModeRegular,

-			Name: []byte("f"),

-			ID:   blob,

-		}}}))

-		c1 := store.AddObject(objecttype.TypeCommit, commitBody(tree))

-		c2 := store.AddObject(objecttype.TypeCommit, commitBody(tree, c1))

-		otherBlob := store.AddObject(objecttype.TypeBlob, []byte("other-blob\n"))

-		otherTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &object.Tree{Entries: []object.TreeEntry{{

-			Mode: object.FileModeRegular,

-			Name: []byte("g"),

-			ID:   otherBlob,

-		}}}))

-		c3 := store.AddObject(objecttype.TypeCommit, commitBody(otherTree))

-		tag := store.AddObject(objecttype.TypeTag, tagBody(c2, objecttype.TypeCommit))

-		ok, err := ancestor.Is(store, nil, 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 = ancestor.Is(store, nil, 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, 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))

-		_, err := ancestor.Is(store, nil, 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)

-		}

-	})

-}

--- /dev/null

+++ b/commitquery/ancestor.go

@@ -1,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

+}

--- /dev/null

+++ b/commitquery/ancestor_integration_test.go

@@ -1,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()

+}

--- /dev/null

+++ b/commitquery/ancestor_unit_test.go

@@ -1,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)

+		}

+	})

+}

--- /dev/null

+++ b/commitquery/bits.go

@@ -1,0 +1,14 @@

+package commitquery

+type markBits uint8

+const (

+	markLeft markBits = 1 << iota

+	markRight

+	markStale

+	markResult

+)

+const (

+	allMarks = markLeft | markRight | markStale | markResult

+)

--- /dev/null

+++ b/commitquery/commit.go

@@ -1,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

+}

--- /dev/null

+++ b/commitquery/compare.go

@@ -1,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)

+}

--- /dev/null

+++ b/commitquery/context.go

@@ -1,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),

+	}

+}

--- /dev/null

+++ b/commitquery/errors.go

@@ -1,0 +1,5 @@

+package commitquery

+import "errors"

+var errBadGenerationOrder = errors.New("commitquery: priority queue violated generation ordering")

--- /dev/null

+++ b/commitquery/generation.go

@@ -1,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)

+	}

+}

--- /dev/null

+++ b/commitquery/graph_pos.go

@@ -1,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)

+}

--- /dev/null

+++ b/commitquery/load.go

@@ -1,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)

+}

--- /dev/null

+++ b/commitquery/marks.go

@@ -1,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)

+}

--- /dev/null

+++ b/commitquery/merge_bases.go

@@ -1,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

+}

--- /dev/null

+++ b/commitquery/mergebase_integration_test.go

@@ -1,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

+}

--- /dev/null

+++ b/commitquery/mergebase_unit_test.go

@@ -1,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")

+		}

+	})

+}

--- /dev/null

+++ b/commitquery/node.go

@@ -1,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

+}

--- /dev/null

+++ b/commitquery/oid.go

@@ -1,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)

+}

--- /dev/null

+++ b/commitquery/parent.go

@@ -1,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)

+}

--- /dev/null

+++ b/commitquery/populate.go

@@ -1,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

+}

--- /dev/null

+++ b/commitquery/priority_queue.go

@@ -1,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

+}

--- /dev/null

+++ b/commitquery/reduce.go

@@ -1,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

+}

--- a/internal/commitquery/ancestor.go

+++ /dev/null

@@ -1,30 +1,0 @@

-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

-}

--- a/internal/commitquery/bits.go

+++ /dev/null

@@ -1,14 +1,0 @@

-package commitquery

-type markBits uint8

-const (

-	markLeft markBits = 1 << iota

-	markRight

-	markStale

-	markResult

-)

-const (

-	allMarks = markLeft | markRight | markStale | markResult

-)

--- a/internal/commitquery/commit.go

+++ /dev/null

@@ -1,17 +1,0 @@

-package commitquery

-import (

-	commitgraphread "codeberg.org/lindenii/furgit/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

-}

--- a/internal/commitquery/compare.go

+++ /dev/null

@@ -1,25 +1,0 @@

-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)

-}

--- a/internal/commitquery/context.go

+++ /dev/null

@@ -1,32 +1,0 @@

-// Package commitquery provides private commit-domain query routines.

-package commitquery

-import (

-	commitgraphread "codeberg.org/lindenii/furgit/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),

-	}

-}

--- a/internal/commitquery/errors.go

+++ /dev/null

@@ -1,5 +1,0 @@

-package commitquery

-import "errors"

-var errBadGenerationOrder = errors.New("commitquery: priority queue violated generation ordering")

--- a/internal/commitquery/generation.go

+++ /dev/null

@@ -1,43 +1,0 @@

-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)

-	}

-}

--- a/internal/commitquery/graph_pos.go

+++ /dev/null

@@ -1,107 +1,0 @@

-package commitquery

-import commitgraphread "codeberg.org/lindenii/furgit/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)

-}

--- a/internal/commitquery/load.go

+++ /dev/null

@@ -1,14 +1,0 @@

-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)

-}

--- a/internal/commitquery/marks.go

+++ /dev/null

@@ -1,67 +1,0 @@

-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)

-}

--- a/internal/commitquery/merge_bases.go

+++ /dev/null

@@ -1,116 +1,0 @@

-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

-	}

-	err := paintDownToCommon(ctx, left, []NodeIndex{right}, 0)

-	if err != nil {

-		return nil, err

-	}

-	candidates := collectMarkedResults(ctx)

-	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) error {

-	ctx.BeginMarkPhase()

-	ctx.SetMarks(left, markLeft)

-	if len(rights) == 0 {

-		ctx.SetMarks(left, markResult)

-		return nil

-	}

-	queue := newPriorityQueue(ctx)

-	queue.PushNode(left)

-	for _, right := range rights {

-		ctx.SetMarks(right, markRight)

-		queue.PushNode(right)

-	}

-	lastGeneration := generationInfinity

-	for queueHasNonStale(ctx, queue) {

-		idx := queue.PopNode()

-		generation := ctx.EffectiveGeneration(idx)

-		if generation > lastGeneration {

-			return errBadGenerationOrder

-		}

-		lastGeneration = generation

-		if generation < minGeneration {

-			break

-		}

-		flags := ctx.Marks(idx) & (markLeft | markRight | markStale)

-		if flags == (markLeft | markRight) {

-			ctx.SetMarks(idx, markResult)

-			flags |= markStale

-		}

-		for _, parent := range ctx.Parents(idx) {

-			if ctx.HasAllMarks(parent, flags) {

-				continue

-			}

-			ctx.SetMarks(parent, flags)

-			queue.PushNode(parent)

-		}

-	}

-	return nil

-}

-func queueHasNonStale(ctx *Context, queue *priorityQueue) bool {

-	for _, idx := range queue.items {

-		if !ctx.HasAnyMarks(idx, markStale) {

-			return true

-		}

-	}

-	return false

-}

-func collectMarkedResults(ctx *Context) []NodeIndex {

-	out := make([]NodeIndex, 0, 4)

-	for _, idx := range ctx.touched {

-		if !ctx.HasAnyMarks(idx, markResult) {

-			continue

-		}

-		if ctx.HasAnyMarks(idx, markStale) {

-			continue

-		}

-		out = append(out, idx)

-	}

-	return out

-}

--- a/internal/commitquery/node.go

+++ /dev/null

@@ -1,39 +1,0 @@

-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 (ctx *Context) newNode(id objectid.ObjectID) NodeIndex {

-	count := len(ctx.nodes)

-	idx := NodeIndex(count)

-	ctx.nodes = append(ctx.nodes, node{id: id})

-	return idx

-}

--- a/internal/commitquery/oid.go

+++ /dev/null

@@ -1,94 +1,0 @@

-package commitquery

-import (

-	stderrors "errors"

-	commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read"

-	giterrors "codeberg.org/lindenii/furgit/errors"

-	"codeberg.org/lindenii/furgit/object"

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

-	"codeberg.org/lindenii/furgit/objectstore"

-	"codeberg.org/lindenii/furgit/objecttype"

-)

-// 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 {

-			if _, ok := stderrors.AsType[*commitgraphread.NotFoundError](err); !ok {

-				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)

-}

--- a/internal/commitquery/parent.go

+++ /dev/null

@@ -1,27 +1,0 @@

-package commitquery

-import (

-	commitgraphread "codeberg.org/lindenii/furgit/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)

-}

--- a/internal/commitquery/populate.go

+++ /dev/null

@@ -1,42 +1,0 @@

-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

-}

--- a/internal/commitquery/priority_queue.go

+++ /dev/null

@@ -1,68 +1,0 @@

-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

-}

--- a/internal/commitquery/reduce.go

+++ /dev/null

@@ -1,166 +1,0 @@

-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

-}

--- a/mergebase/base.go

+++ /dev/null

@@ -1,30 +1,0 @@

-package mergebase

-import (

-	commitgraphread "codeberg.org/lindenii/furgit/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)

-	bases, err := query.All()

-	if err != nil {

-		return objectid.ObjectID{}, false, err

-	}

-	if len(bases) == 0 {

-		return objectid.ObjectID{}, false, nil

-	}

-	return bases[0], true, nil

-}

--- a/mergebase/compute.go

+++ /dev/null

@@ -1,73 +1,0 @@

-package mergebase

-import (

-	"slices"

-	"codeberg.org/lindenii/furgit/internal/commitquery"

-	"codeberg.org/lindenii/furgit/internal/peel"

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

-)

-// All returns all merge bases in Git's merge-base --all order.

-func (query *Bases) All() ([]objectid.ObjectID, error) {

-	if query.computed {

-		return slices.Clone(query.bases), query.err

-	}

-	query.computed = true

-	leftCommit, err := peel.ToCommit(query.store, query.left)

-	if err != nil {

-		query.err = err

-		return nil, err

-	}

-	rightCommit, err := peel.ToCommit(query.store, query.right)

-	if err != nil {

-		query.err = err

-		return nil, err

-	}

-	ctx := commitquery.NewContext(query.store, query.graph)

-	leftIdx, err := ctx.ResolveOID(leftCommit)

-	if err != nil {

-		query.err = err

-		return nil, err

-	}

-	rightIdx, err := ctx.ResolveOID(rightCommit)

-	if err != nil {

-		query.err = err

-		return nil, err

-	}

-	candidates, err := commitquery.MergeBases(ctx, leftIdx, rightIdx)

-	if err != nil {

-		query.err = err

-		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))

-		}

-	})

-	query.bases = make([]objectid.ObjectID, 0, len(candidates))

-	for _, idx := range candidates {

-		query.bases = append(query.bases, ctx.ID(idx))

-	}

-	return slices.Clone(query.bases), nil

-}

--- a/mergebase/integration_test.go

+++ /dev/null

@@ -1,309 +1,0 @@

-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)

-		all, err := query.All()

-		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 := mergebase.Query(store, nil, left, right)

-		all, err := query.All()

-		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 := 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)

-		all, err := query.All()

-		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 := 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)

-		}

-	})

-}

-// 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

-}

--- a/mergebase/mergebase.go

+++ /dev/null

@@ -1,20 +1,0 @@

-// Package mergebase computes best common ancestors between commits.

-package mergebase

-import (

-	commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read"

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

-	"codeberg.org/lindenii/furgit/objectstore"

-)

-// Bases is one merge-base query over two commit roots.

-type Bases struct {

-	store objectstore.Store

-	graph *commitgraphread.Reader

-	left  objectid.ObjectID

-	right objectid.ObjectID

-	computed bool

-	bases    []objectid.ObjectID

-	err      error

-}

--- a/mergebase/query.go

+++ /dev/null

@@ -1,24 +1,0 @@

-package mergebase

-import (

-	commitgraphread "codeberg.org/lindenii/furgit/commitgraph/read"

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

-	"codeberg.org/lindenii/furgit/objectstore"

-)

-// Query builds one 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,

-	}

-}

--- a/mergebase/unit_test.go

+++ /dev/null

@@ -1,332 +1,0 @@

-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)

-}

-// 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, err := query.All()

-		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 := 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, err := query.All()

-		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 := mergebase.Query(store, nil, left, right)

-		all, err := query.All()

-		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 := 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, err := query.All()

-		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 := 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)

-		_, err := query.All()

-		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 := mergebase.Query(store, nil, left, right)

-		first, err := query.All()

-		if err != nil {

-			t.Fatalf("query.All() first call: %v", err)

-		}

-		again, err := query.All()

-		if err != nil {

-			t.Fatalf("query.All() 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 All() unexpectedly returned no results")

-		}

-		first[0] = objectid.ObjectID{}

-		third, err := query.All()

-		if err != nil {

-			t.Fatalf("query.All() third call: %v", err)

-		}

-		if third[0] == (objectid.ObjectID{}) {

-			t.Fatal("query.All() exposed internal slice state")

-		}

-	})

-}

--- a/receivepack/hooks/reject_force_push.go

+++ b/receivepack/hooks/reject_force_push.go

@@ -5,7 +5,7 @@

 	"errors"

 	"fmt"

-	"codeberg.org/lindenii/furgit/ancestor"

+	"codeberg.org/lindenii/furgit/commitquery"

 	"codeberg.org/lindenii/furgit/objectid"

 	objectmix "codeberg.org/lindenii/furgit/objectstore/mix"

 	receivepack "codeberg.org/lindenii/furgit/receivepack"

@@ -46,7 +46,7 @@

 				continue

-			ok, err := ancestor.Is(objects, nil, current.ID, update.NewID)

+			ok, err := commitquery.New(objects, nil).IsAncestor(current.ID, update.NewID)

 			if err != nil {

 				return nil, fmt.Errorf("check fast-forward %s: %w", update.Name, err)

--

⑨