reachability: Use commit-graph

Might need to reconsider this sometime.

1 files changed, 97 insertions, 0 deletions

diff --git a/reachability/reachability.go b/reachability/reachability.go
index 12f672e3..9126ee84 100644
--- a/reachability/reachability.go
+++ b/reachability/reachability.go
@@ -2,6 +2,9 @@
 package reachability
 
 import (
+	"errors"
+
+	"codeberg.org/lindenii/furgit/format/commitgraph"
 	"codeberg.org/lindenii/furgit/objectid"
 	"codeberg.org/lindenii/furgit/objectstore"
 )
@@ -11,6 +14,7 @@ import (
 // It is not safe for concurrent use.
 type Reachability struct {
 	store objectstore.Store
+	graph *commitgraph.Reader
 }
 
 // New builds a Reachability  over one object store.
@@ -18,6 +22,12 @@ func New(store objectstore.Store) *Reachability {
 	return &Reachability{store: store}
 }
 
+// NewWithCommitGraph builds a Reachability over one object store with an
+// optional commit-graph reader for faster commit-domain traversal.
+func NewWithCommitGraph(store objectstore.Store, graph *commitgraph.Reader) *Reachability {
+	return &Reachability{store: store, graph: graph}
+}
+
 // IsAncestor reports whether ancestor is reachable from descendant via commit
 // parent edges.
 //
@@ -37,6 +47,15 @@ func (r *Reachability) IsAncestor(ancestor, descendant objectid.ObjectID) (bool,
 		return true, nil
 	}
 
+	graphResult, graphUsed, err := r.isAncestorGraph(ancestorCommit, descendantCommit)
+	if err != nil {
+		return false, err
+	}
+
+	if graphUsed {
+		return graphResult, nil
+	}
+
 	walk := r.Walk(DomainCommits, nil, map[objectid.ObjectID]struct{}{descendantCommit: {}})
 	for id := range walk.Seq() {
 		if id == ancestorCommit {
@@ -52,11 +71,86 @@ func (r *Reachability) IsAncestor(ancestor, descendant objectid.ObjectID) (bool,
 	return false, nil
 }
 
+func (r *Reachability) isAncestorGraph(ancestor, descendant objectid.ObjectID) (bool, bool, error) {
+	if r.graph == nil {
+		return false, false, nil
+	}
+
+	ancestorPos, err := r.graph.Lookup(ancestor)
+	if err != nil {
+		var notFound *commitgraph.ErrNotFound
+		if errors.As(err, &notFound) {
+			return false, false, nil
+		}
+
+		return false, true, err
+	}
+
+	descendantPos, err := r.graph.Lookup(descendant)
+	if err != nil {
+		var notFound *commitgraph.ErrNotFound
+		if errors.As(err, &notFound) {
+			return false, false, nil
+		}
+
+		return false, true, err
+	}
+
+	ancestorCommit, err := r.graph.CommitAt(ancestorPos)
+	if err != nil {
+		return false, true, err
+	}
+
+	ancestorGeneration := ancestorCommit.GenerationV2
+	stack := []commitgraph.Position{descendantPos}
+	visited := make(map[commitgraph.Position]struct{}, 64)
+
+	for len(stack) > 0 {
+		pos := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+
+		if _, ok := visited[pos]; ok {
+			continue
+		}
+
+		visited[pos] = struct{}{}
+
+		if pos == ancestorPos {
+			return true, true, nil
+		}
+
+		commit, err := r.graph.CommitAt(pos)
+		if err != nil {
+			return false, true, err
+		}
+
+		if commit.GenerationV2 < ancestorGeneration {
+			continue
+		}
+
+		if commit.Parent1.Valid {
+			stack = append(stack, commit.Parent1.Pos)
+		}
+
+		if commit.Parent2.Valid {
+			stack = append(stack, commit.Parent2.Pos)
+		}
+
+		stack = append(stack, commit.ExtraParents...)
+	}
+
+	return false, true, nil
+}
+
 // CheckConnected verifies that all objects reachable from wants (under the
 // selected domain) can be fully traversed without missing-object/type/parse
 // errors, excluding subgraphs rooted at haves.
+//
+// Even with commit-graph acceleration available, each visited commit is
+// still validated against the object store.
 func (r *Reachability) CheckConnected(domain Domain, haves, wants map[objectid.ObjectID]struct{}) error {
 	walk := r.Walk(domain, haves, wants)
+	walk.strict = true
 	for range walk.Seq() {
 	}
 
@@ -64,6 +158,9 @@ func (r *Reachability) CheckConnected(domain Domain, haves, wants map[objectid.O
 }
 
 // Walk creates one single-use traversal over the selected domain.
+//
+// In DomainCommits, when a commit-graph reader is attached, parent expansion
+// may use commit-graph metadata for speed.
 func (r *Reachability) Walk(domain Domain, haves, wants map[objectid.ObjectID]struct{}) *Walk {
 	walk := &Walk{
 		reachability: r,