shithub: furgit

--- a/commitquery/ancestor.go

+++ /dev/null

@@ -1,48 +1,0 @@

-package commitquery

-import objectid "codeberg.org/lindenii/furgit/object/id"

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

-}

--- a/commitquery/ancestor_integration_test.go

+++ /dev/null

@@ -1,132 +1,0 @@

-package commitquery_test

-import (

-	"errors"

-	"testing"

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

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

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

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

-)

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

-}

--- a/commitquery/ancestor_unit_test.go

+++ /dev/null

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

-package commitquery_test

-import (

-	"errors"

-	"fmt"

-	"testing"

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

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

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

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

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

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

-	"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 := targetType.Name()

-	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 *objecttree.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, &objecttree.Tree{Entries: []objecttree.TreeEntry{{

-			Mode: objecttree.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, &objecttree.Tree{Entries: []objecttree.TreeEntry{{

-			Mode: objecttree.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, &objecttree.Tree{Entries: []objecttree.TreeEntry{{

-			Mode: objecttree.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)

-		}

-	})

-}

--- a/commitquery/commit.go

+++ /dev/null

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

-package commitquery

-import (

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

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

-)

-// 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/commit_data.go

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

+package commitquery

+import (

+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"

+	objectid "codeberg.org/lindenii/furgit/object/id"

+)

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

+}

--- a/commitquery/errors.go

+++ b/commitquery/errors.go

@@ -2,4 +2,5 @@

 import "errors"

+// errBadGenerationOrder reports an invalid priority-queue ordering.

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

--- a/commitquery/graph_pos.go

+++ /dev/null

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

-package commitquery

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

-}

--- a/commitquery/load.go

+++ /dev/null

@@ -1,71 +1,0 @@

-package commitquery

-import (

-	stderrors "errors"

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

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

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

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

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

-)

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

-}

-// 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 := objectcommit.Parse(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/mark_bits.go

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

+package commitquery

+// markBits stores one set of traversal marks on one node.

+type markBits uint8

+// markLeft, markRight, markStale, and markResult track traversal state.

+const (

+	markLeft markBits = 1 << iota

+	markRight

+	markStale

+	markResult

+)

+// allMarks is the union of all defined mark bits.

+const (

+	allMarks = markLeft | markRight | markStale | markResult

+)

--- a/commitquery/marks.go

+++ /dev/null

@@ -1,102 +1,0 @@

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

-}

-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

-}

-type markBits uint8

-const (

-	markLeft markBits = 1 << iota

-	markRight

-	markStale

-	markResult

-)

-const (

-	allMarks = markLeft | markRight | markStale | markResult

-)

--- a/commitquery/merge_bases.go

+++ /dev/null

@@ -1,89 +1,0 @@

-package commitquery

-import (

-	"slices"

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

-)

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

-}

--- a/commitquery/mergebase_integration_test.go

+++ /dev/null

@@ -1,311 +1,0 @@

-package commitquery_test

-import (

-	"maps"

-	"slices"

-	"strings"

-	"testing"

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

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

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

-)

-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

-}

--- a/commitquery/mergebase_unit_test.go

+++ /dev/null

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

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

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

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

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

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

-)

-// 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 := targetType.Name()

-	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 *tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

-			Mode: tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

-			Mode: tree.FileModeRegular,

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

-			ID:   blob,

-		}}}))

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

-			Mode: tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

-			Mode: tree.FileModeRegular,

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

-			ID:   blob,

-		}}}))

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

-			Mode: tree.FileModeRegular,

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

-			ID:   blob,

-		}}}))

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

-			Mode: tree.FileModeRegular,

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

-			ID:   blob,

-		}}}))

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

-			Mode: tree.FileModeRegular,

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

-			ID:   blob,

-		}}}))

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

-			Mode: tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

-			Mode: tree.FileModeRegular,

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

-			ID:   leftBlob,

-		}}}))

-		rightBlob := store.AddObject(objecttype.TypeBlob, []byte("right\n"))

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

-			Mode: tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

-			Mode: tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

-			Mode: tree.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")

-		}

-	})

-}

--- a/commitquery/node_commit_time.go

+++ b/commitquery/node_commit_time.go

@@ -1,5 +1,6 @@

 package commitquery

+// commitTime returns one node's commit time.

 func (query *query) commitTime(idx nodeIndex) int64 {

 	return query.nodes[idx].commitTime

--- a/commitquery/node_compare.go

+++ b/commitquery/node_compare.go

@@ -2,7 +2,7 @@

 import objectid "codeberg.org/lindenii/furgit/object/id"

-// Compare compares two internal nodes using merge-base queue ordering.

+// compare orders two internal nodes using merge-base queue ordering.

 func (query *query) compare(left, right nodeIndex) int {

 	leftGeneration := query.effectiveGeneration(left)

 	rightGeneration := query.effectiveGeneration(right)

--- a/commitquery/node_generation.go

+++ b/commitquery/node_generation.go

@@ -6,7 +6,7 @@

 	objectid "codeberg.org/lindenii/furgit/object/id"

-// EffectiveGeneration returns one node's generation value.

+// effectiveGeneration returns one node's generation value.

 func (query *query) effectiveGeneration(idx nodeIndex) uint64 {

 	if !query.nodes[idx].hasGeneration {

 		return generationInfinity

@@ -15,10 +15,12 @@

 	return query.nodes[idx].generation

+// generationInfinity sorts nodes without a known generation last.

 const (

 	generationInfinity = uint64(math.MaxUint64)

+// compareByGeneration builds one comparator ordered by generation first.

 func (query *query) compareByGeneration() func(nodeIndex, nodeIndex) int {

 	return func(left, right nodeIndex) int {

 		leftGeneration := query.effectiveGeneration(left)

--- a/commitquery/node_id.go

+++ b/commitquery/node_id.go

@@ -2,6 +2,7 @@

 import objectid "codeberg.org/lindenii/furgit/object/id"

+// id returns one node's object ID.

 func (query *query) id(idx nodeIndex) objectid.ObjectID {

 	return query.nodes[idx].id

--- a/commitquery/node_paint_down_to_common.go

+++ /dev/null

@@ -1,66 +1,0 @@

-package commitquery

-import "codeberg.org/lindenii/furgit/internal/priorityqueue"

-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 := priorityqueue.New(func(left, right nodeIndex) bool {

-		return query.compare(left, right) > 0

-	})

-	queue.Push(left)

-	for _, right := range rights {

-		query.setMarks(right, markRight)

-		queue.Push(right)

-	}

-	lastGeneration := generationInfinity

-	for queue.Len() > 0 {

-		idx, ok := queue.Pop()

-		if !ok {

-			break

-		}

-		if query.hasAnyMarks(idx, markStale) {

-			continue

-		}

-		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.Push(parent)

-		}

-	}

-	return nil

-}

--- a/commitquery/node_parent.go

+++ /dev/null

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

-package commitquery

-import (

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

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

-)

-// Parents returns resolved parent node indices for one internal node.

-func (query *query) parents(idx nodeIndex) []nodeIndex {

-	return query.nodes[idx].parents

-}

-// parentRef references one commit parent.

-type parentRef struct {

-	ID          objectid.ObjectID

-	GraphPos    commitgraphread.Position

-	HasGraphPos bool

-}

-// 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/node_parents.go

@@ -1,0 +1,6 @@

+package commitquery

+// parents returns resolved parent node indices for one internal node.

+func (query *query) parents(idx nodeIndex) []nodeIndex {

+	return query.nodes[idx].parents

+}

--- /dev/null

+++ b/commitquery/parent_ref.go

@@ -1,0 +1,13 @@

+package commitquery

+import (

+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"

+	objectid "codeberg.org/lindenii/furgit/object/id"

+)

+// parentRef references one commit parent.

+type parentRef struct {

+	ID          objectid.ObjectID

+	GraphPos    commitgraphread.Position

+	HasGraphPos bool

+}

--- a/commitquery/queries_acquire.go

+++ b/commitquery/queries_acquire.go

@@ -1,5 +1,6 @@

 package commitquery

+// acquire removes one worker from the idle pool or allocates one new worker.

 func (queries *Queries) acquire() *query {

 	queries.mu.Lock()

 	defer queries.mu.Unlock()

--- a/commitquery/queries_ancestor.go

+++ /dev/null

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

-package commitquery

-import objectid "codeberg.org/lindenii/furgit/object/id"

-// IsAncestor reports whether ancestor is reachable from descendant through

-// commit parent edges.

-//

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

-func (queries *Queries) IsAncestor(ancestor, descendant objectid.ObjectID) (bool, error) {

-	query := queries.acquire()

-	defer queries.release(query)

-	return query.IsAncestor(ancestor, descendant)

-}

--- /dev/null

+++ b/commitquery/queries_is_ancestor.go

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

+package commitquery

+import objectid "codeberg.org/lindenii/furgit/object/id"

+// IsAncestor reports whether ancestor is reachable from descendant through

+// commit parent edges.

+//

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

+func (queries *Queries) IsAncestor(ancestor, descendant objectid.ObjectID) (bool, error) {

+	query := queries.acquire()

+	defer queries.release(query)

+	return query.IsAncestor(ancestor, descendant)

+}

--- /dev/null

+++ b/commitquery/queries_is_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"

+	objectid "codeberg.org/lindenii/furgit/object/id"

+)

+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/queries_is_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"

+	objectid "codeberg.org/lindenii/furgit/object/id"

+	"codeberg.org/lindenii/furgit/object/store/memory"

+	objecttree "codeberg.org/lindenii/furgit/object/tree"

+	objecttype "codeberg.org/lindenii/furgit/object/type"

+	"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 := targetType.Name()

+	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 *objecttree.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, &objecttree.Tree{Entries: []objecttree.TreeEntry{{

+			Mode: objecttree.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, &objecttree.Tree{Entries: []objecttree.TreeEntry{{

+			Mode: objecttree.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, &objecttree.Tree{Entries: []objecttree.TreeEntry{{

+			Mode: objecttree.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/queries_merge_base.go

@@ -1,0 +1,11 @@

+package commitquery

+import objectid "codeberg.org/lindenii/furgit/object/id"

+// MergeBase reports one merge base between left and right, if any.

+func (queries *Queries) MergeBase(left, right objectid.ObjectID) (objectid.ObjectID, bool, error) {

+	query := queries.acquire()

+	defer queries.release(query)

+	return query.MergeBase(left, right)

+}

--- /dev/null

+++ b/commitquery/queries_merge_bases.go

@@ -1,0 +1,13 @@

+package commitquery

+import objectid "codeberg.org/lindenii/furgit/object/id"

+// MergeBases reports all merge bases in Git's merge-base --all order.

+//

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

+func (queries *Queries) MergeBases(left, right objectid.ObjectID) ([]objectid.ObjectID, error) {

+	query := queries.acquire()

+	defer queries.release(query)

+	return query.MergeBases(left, right)

+}

--- /dev/null

+++ b/commitquery/queries_merge_bases_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"

+	objectid "codeberg.org/lindenii/furgit/object/id"

+)

+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/queries_merge_bases_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"

+	objectid "codeberg.org/lindenii/furgit/object/id"

+	"codeberg.org/lindenii/furgit/object/store/memory"

+	"codeberg.org/lindenii/furgit/object/tree"

+	objecttype "codeberg.org/lindenii/furgit/object/type"

+)

+// 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 := targetType.Name()

+	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 *tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.FileModeRegular,

+			Name: []byte("left"),

+			ID:   blob,

+		}}}))

+		rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.FileModeRegular,

+			Name: []byte("root"),

+			ID:   blob,

+		}}}))

+		base1Tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.FileModeRegular,

+			Name: []byte("base1"),

+			ID:   blob,

+		}}}))

+		base2Tree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.FileModeRegular,

+			Name: []byte("base2"),

+			ID:   blob,

+		}}}))

+		leftTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.FileModeRegular,

+			Name: []byte("left"),

+			ID:   blob,

+		}}}))

+		rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.FileModeRegular,

+			Name: []byte("left"),

+			ID:   leftBlob,

+		}}}))

+		rightBlob := store.AddObject(objecttype.TypeBlob, []byte("right\n"))

+		rightTree := store.AddObject(objecttype.TypeTree, mustSerializeTree(t, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.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, &tree.Tree{Entries: []tree.TreeEntry{{

+			Mode: tree.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")

+		}

+	})

+}

--- a/commitquery/queries_mergebase.go

+++ /dev/null

@@ -1,21 +1,0 @@

-package commitquery

-import objectid "codeberg.org/lindenii/furgit/object/id"

-// MergeBases reports all merge bases in Git's merge-base --all order.

-//

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

-func (queries *Queries) MergeBases(left, right objectid.ObjectID) ([]objectid.ObjectID, error) {

-	query := queries.acquire()

-	defer queries.release(query)

-	return query.MergeBases(left, right)

-}

-// MergeBase reports one merge base between left and right, if any.

-func (queries *Queries) MergeBase(left, right objectid.ObjectID) (objectid.ObjectID, bool, error) {

-	query := queries.acquire()

-	defer queries.release(query)

-	return query.MergeBase(left, right)

-}

--- a/commitquery/queries_release.go

+++ b/commitquery/queries_release.go

@@ -1,5 +1,6 @@

 package commitquery

+// release resets one worker and returns it to the idle pool if there is room.

 func (queries *Queries) release(q *query) {

 	q.resetForReuse()

--- /dev/null

+++ b/commitquery/query.go

@@ -1,0 +1,23 @@

+package commitquery

+import (

+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"

+	objectid "codeberg.org/lindenii/furgit/object/id"

+	objectstore "codeberg.org/lindenii/furgit/object/store"

+)

+// query stores one mutable reusable worker and its cached node arena.

+//

+// Labels: MT-Unsafe.

+type query struct {

+	store objectstore.ReadingStore

+	graph *commitgraphread.Reader

+	nodes []node

+	byOID      map[objectid.ObjectID]nodeIndex

+	byGraphPos map[commitgraphread.Position]nodeIndex

+	markPhase uint32

+	touched   []nodeIndex

+}

--- /dev/null

+++ b/commitquery/query_collect_marked_results.go

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

+package commitquery

+// collectMarkedResults returns touched nodes marked as non-stale results.

+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/query_ensure_loaded.go

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

+package commitquery

+// ensureLoaded completes one node's metadata load if it is not 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/query_has_marks.go

@@ -1,0 +1,11 @@

+package commitquery

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

+}

--- /dev/null

+++ b/commitquery/query_is_ancestor.go

@@ -1,0 +1,49 @@

+package commitquery

+import objectid "codeberg.org/lindenii/furgit/object/id"

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

+}

+// isAncestor answers one ancestry query between two resolved internal nodes.

+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/query_load_by_graph_pos.go

@@ -1,0 +1,8 @@

+package commitquery

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

+}

--- /dev/null

+++ b/commitquery/query_load_by_oid.go

@@ -1,0 +1,58 @@

+package commitquery

+import (

+	stderrors "errors"

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

+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"

+	objectcommit "codeberg.org/lindenii/furgit/object/commit"

+	objectstore "codeberg.org/lindenii/furgit/object/store"

+	objecttype "codeberg.org/lindenii/furgit/object/type"

+)

+// 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 := objectcommit.Parse(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/query_load_commit_at_graph_pos.go

@@ -1,0 +1,64 @@

+package commitquery

+import commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"

+// loadCommitAtGraphPos populates one node from one commit-graph record.

+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/query_mark_phase.go

@@ -1,0 +1,36 @@

+package commitquery

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

+	}

+}

+// trackTouched records one node in the current mark phase.

+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/query_marks_get.go

@@ -1,0 +1,6 @@

+package commitquery

+// marks returns the mark bits of one internal node.

+func (query *query) marks(idx nodeIndex) markBits {

+	return query.nodes[idx].marks

+}

--- /dev/null

+++ b/commitquery/query_merge_base.go

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

+package commitquery

+import objectid "codeberg.org/lindenii/furgit/object/id"

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

+}

--- /dev/null

+++ b/commitquery/query_merge_bases.go

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

+package commitquery

+import (

+	"slices"

+	objectid "codeberg.org/lindenii/furgit/object/id"

+)

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

+}

--- /dev/null

+++ b/commitquery/query_merge_bases_internal.go

@@ -1,0 +1,34 @@

+package commitquery

+import "slices"

+// mergeBases returns internal merge-base candidates for two resolved nodes.

+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

+}

--- /dev/null

+++ b/commitquery/query_new.go

@@ -1,0 +1,19 @@

+package commitquery

+import (

+	commitgraphread "codeberg.org/lindenii/furgit/format/commitgraph/read"

+	objectid "codeberg.org/lindenii/furgit/object/id"

+	objectstore "codeberg.org/lindenii/furgit/object/store"

+)

+// newQuery builds one empty mutable worker over one object store and graph.

+//

+// Labels: Deps-Borrowed, Life-Parent.

+func newQuery(store objectstore.ReadingStore, 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/query_paint_down_to_common.go

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

+package commitquery

+import "codeberg.org/lindenii/furgit/internal/priorityqueue"

+// paintDownToCommon propagates left and right marks downward until common nodes.

+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 := priorityqueue.New(func(left, right nodeIndex) bool {

+		return query.compare(left, right) > 0

+	})

+	queue.Push(left)

+	for _, right := range rights {

+		query.setMarks(right, markRight)

+		queue.Push(right)

+	}

+	lastGeneration := generationInfinity

+	for queue.Len() > 0 {

+		idx, ok := queue.Pop()

+		if !ok {

+			break

+		}

+		if query.hasAnyMarks(idx, markStale) {

+			continue

+		}

+		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.Push(parent)

+		}

+	}

+	return nil

+}

--- /dev/null

+++ b/commitquery/query_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)

+}

+// removeRedundantNoGen removes redundant candidates without generation data.

+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

+}

+// removeRedundantWithGen removes redundant candidates using generation data.

+func removeRedundantWithGen(query *query, candidates []nodeIndex) []nodeIndex {

+	sorted := append([]nodeIndex(nil), candidates...)

+	slices.SortFunc(sorted, query.compareByGeneration())

+	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, query.compareByGeneration())

+	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

+}

--- /dev/null

+++ b/commitquery/query_reset.go

@@ -1,0 +1,10 @@

+package commitquery

+// resetForReuse clears transient state before one worker returns to the pool.

+func (query *query) resetForReuse() {

+	for _, idx := range query.touched {

+		query.nodes[idx].marks = 0

+	}

+	query.touched = query.touched[:0]

+}

--- /dev/null

+++ b/commitquery/query_resolve_commitish.go

@@ -1,0 +1,16 @@

+package commitquery

+import (

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

+	objectid "codeberg.org/lindenii/furgit/object/id"

+)

+// resolveCommitish peels one commit-ish object ID and resolves the commit.

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

+}

--- /dev/null

+++ b/commitquery/query_resolve_graph_pos.go

@@ -1,0 +1,40 @@

+package commitquery

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

+}

--- /dev/null

+++ b/commitquery/query_resolve_oid.go

@@ -1,0 +1,28 @@

+package commitquery

+import objectid "codeberg.org/lindenii/furgit/object/id"

+// resolveOID resolves one commit object ID to one internal query node.

+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

+}

--- /dev/null

+++ b/commitquery/query_resolve_parent.go

@@ -1,0 +1,10 @@

+package commitquery

+// 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/query_set_clear_marks.go

@@ -1,0 +1,22 @@

+package commitquery

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

+}

--- a/commitquery/reduce.go

+++ /dev/null

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

-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, query.compareByGeneration())

-	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, query.compareByGeneration())

-	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/commitquery/reset.go

+++ /dev/null

@@ -1,37 +1,0 @@

-package commitquery

-import (

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

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

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

-)

-type query struct {

-	store objectstore.ReadingStore

-	graph *commitgraphread.Reader

-	nodes []node

-	byOID      map[objectid.ObjectID]nodeIndex

-	byGraphPos map[commitgraphread.Position]nodeIndex

-	markPhase uint32

-	touched   []nodeIndex

-}

-func newQuery(store objectstore.ReadingStore, graph *commitgraphread.Reader) *query {

-	return &query{

-		store:      store,

-		graph:      graph,

-		byOID:      make(map[objectid.ObjectID]nodeIndex),

-		byGraphPos: make(map[commitgraphread.Position]nodeIndex),

-	}

-}

-func (query *query) resetForReuse() {

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

-		query.nodes[idx].marks = 0

-	}

-	query.touched = query.touched[:0]

-}

--- a/commitquery/resolve.go

+++ /dev/null

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

-package commitquery

-import (

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

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

-)

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

-}

--

⑨