reachability: Refactor v0.1.41

8 files changed, 344 insertions, 313 deletions

diff --git a/reachability/domain.go b/reachability/domain.go
new file mode 100644
index 00000000..9fcf721e
--- /dev/null
+++ b/reachability/domain.go
@@ -0,0 +1,11 @@
+package reachability
+
+// Domain specifies which graph edges are traversed.
+type Domain uint8
+
+const (
+	// DomainCommits traverses commit-parent edges and annotated-tag target edges.
+	DomainCommits Domain = iota
+	// DomainObjects traverses full commit/tree/blob objects.
+	DomainObjects
+)
diff --git a/reachability/errors.go b/reachability/errors.go
new file mode 100644
index 00000000..e52bf0a4
--- /dev/null
+++ b/reachability/errors.go
@@ -0,0 +1,37 @@
+package reachability
+
+import (
+	"fmt"
+
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objecttype"
+)
+
+// ErrObjectMissing indicates that a referenced object is absent from the store.
+type ErrObjectMissing struct {
+	OID objectid.ObjectID
+}
+
+func (e *ErrObjectMissing) Error() string {
+	return fmt.Sprintf("reachability: missing object %s", e.OID)
+}
+
+// ErrObjectType indicates that a referenced object has a different type than
+// what traversal expected on that edge.
+type ErrObjectType struct {
+	OID  objectid.ObjectID
+	Got  objecttype.Type
+	Want objecttype.Type
+}
+
+func (e *ErrObjectType) Error() string {
+	gotName, gotOK := objecttype.Name(e.Got)
+	if !gotOK {
+		gotName = fmt.Sprintf("type(%d)", e.Got)
+	}
+	wantName, wantOK := objecttype.Name(e.Want)
+	if !wantOK {
+		wantName = fmt.Sprintf("type(%d)", e.Want)
+	}
+	return fmt.Sprintf("reachability: object %s has type %s, want %s", e.OID, gotName, wantName)
+}
diff --git a/reachability/helpers.go b/reachability/helpers.go
new file mode 100644
index 00000000..1368a3f1
--- /dev/null
+++ b/reachability/helpers.go
@@ -0,0 +1,64 @@
+package reachability
+
+import (
+	"errors"
+	"fmt"
+
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objectstore"
+	"codeberg.org/lindenii/furgit/objecttype"
+)
+
+func validateDomain(domain Domain) error {
+	switch domain {
+	case DomainCommits, DomainObjects:
+		return nil
+	default:
+		return fmt.Errorf("reachability: invalid domain %d", domain)
+	}
+}
+
+func containsOID(set map[objectid.ObjectID]struct{}, id objectid.ObjectID) bool {
+	if len(set) == 0 {
+		return false
+	}
+	_, ok := set[id]
+	return ok
+}
+
+// The following helpers exist because we don't have unified error handling across the entire project.
+// This will be fixed later.
+
+func (walk *Walk) readHeaderType(id objectid.ObjectID) (objecttype.Type, error) {
+	return walk.reachability.readHeaderType(id)
+}
+
+func (r *Reachability) readHeaderType(id objectid.ObjectID) (objecttype.Type, error) {
+	ty, _, err := r.store.ReadHeader(id)
+	if err != nil {
+		if errors.Is(err, objectstore.ErrObjectNotFound) {
+			return objecttype.TypeInvalid, &ErrObjectMissing{OID: id}
+		}
+		return objecttype.TypeInvalid, err
+	}
+	return ty, nil
+}
+
+func (walk *Walk) readBytesContent(id objectid.ObjectID) ([]byte, error) {
+	content, err := walk.reachability.readBytesContent(id)
+	if err != nil {
+		return nil, err
+	}
+	return content, nil
+}
+
+func (r *Reachability) readBytesContent(id objectid.ObjectID) ([]byte, error) {
+	_, content, err := r.store.ReadBytesContent(id)
+	if err != nil {
+		if errors.Is(err, objectstore.ErrObjectNotFound) {
+			return nil, &ErrObjectMissing{OID: id}
+		}
+		return nil, err
+	}
+	return content, nil
+}
diff --git a/reachability/reachability_integration_test.go b/reachability/integration_test.go
index 10668006..10668006 100644
--- a/reachability/reachability_integration_test.go
+++ b/reachability/integration_test.go
diff --git a/reachability/peel.go b/reachability/peel.go
new file mode 100644
index 00000000..9df9bb4d
--- /dev/null
+++ b/reachability/peel.go
@@ -0,0 +1,35 @@
+package reachability
+
+import (
+	"codeberg.org/lindenii/furgit/object"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objecttype"
+)
+
+func (r *Reachability) peelRootToDomain(id objectid.ObjectID, domain Domain) (objectid.ObjectID, error) {
+	if err := validateDomain(domain); err != nil {
+		return objectid.ObjectID{}, err
+	}
+	for {
+		ty, err := r.readHeaderType(id)
+		if err != nil {
+			return objectid.ObjectID{}, err
+		}
+		if ty != objecttype.TypeTag {
+			if domain == DomainCommits && ty != objecttype.TypeCommit {
+				return objectid.ObjectID{}, &ErrObjectType{OID: id, Got: ty, Want: objecttype.TypeCommit}
+			}
+			return id, nil
+		}
+
+		content, err := r.readBytesContent(id)
+		if err != nil {
+			return objectid.ObjectID{}, err
+		}
+		tag, err := object.ParseTag(content, id.Algorithm())
+		if err != nil {
+			return objectid.ObjectID{}, err
+		}
+		id = tag.Target
+	}
+}
diff --git a/reachability/reachability.go b/reachability/reachability.go
index 5ab41944..0bec055f 100644
--- a/reachability/reachability.go
+++ b/reachability/reachability.go
@@ -1,36 +1,20 @@
 package reachability
 
 import (
-	"errors"
-	"fmt"
-	"iter"
-
-	"codeberg.org/lindenii/furgit/object"
 	"codeberg.org/lindenii/furgit/objectid"
 	"codeberg.org/lindenii/furgit/objectstore"
-	"codeberg.org/lindenii/furgit/objecttype"
-)
-
-// Domain specifies which graph edges are traversed.
-type Domain uint8
-
-const (
-	// DomainCommits traverses commit-parent edges and annotated-tag target edges.
-	DomainCommits Domain = iota
-	// DomainObjects traverses full commit/tree/blob objects.
-	DomainObjects
 )
 
 // Reachability provides graph traversal over objects in one object store.
 //
 // It is not safe for concurrent use.
 type Reachability struct {
-	Store objectstore.Store
+	store objectstore.Store
 }
 
 // New builds a Reachability  over one object store.
 func New(store objectstore.Store) *Reachability {
-	return &Reachability{Store: store}
+	return &Reachability{store: store}
 }
 
 // IsAncestor reports whether ancestor is reachable from descendant via commit
@@ -85,298 +69,3 @@ func (r *Reachability) Walk(domain Domain, haves, wants map[objectid.ObjectID]st
 	}
 	return walk
 }
-
-// ErrObjectMissing indicates that a referenced object is absent from the store.
-type ErrObjectMissing struct {
-	OID objectid.ObjectID
-}
-
-func (e *ErrObjectMissing) Error() string {
-	return fmt.Sprintf("reachability: missing object %s", e.OID)
-}
-
-// ErrObjectType indicates that a referenced object has a different type than
-// what traversal expected on that edge.
-type ErrObjectType struct {
-	OID  objectid.ObjectID
-	Got  objecttype.Type
-	Want objecttype.Type
-}
-
-func (e *ErrObjectType) Error() string {
-	gotName, gotOK := objecttype.Name(e.Got)
-	if !gotOK {
-		gotName = fmt.Sprintf("type(%d)", e.Got)
-	}
-	wantName, wantOK := objecttype.Name(e.Want)
-	if !wantOK {
-		wantName = fmt.Sprintf("type(%d)", e.Want)
-	}
-	return fmt.Sprintf("reachability: object %s has type %s, want %s", e.OID, gotName, wantName)
-}
-
-// Walk is one single-use iterator-style traversal.
-type Walk struct {
-	reachability *Reachability
-	domain       Domain
-	haves        map[objectid.ObjectID]struct{}
-	wants        map[objectid.ObjectID]struct{}
-
-	seqUsed bool
-	err     error
-}
-
-// Seq returns the traversal sequence. It is single-use.
-func (walk *Walk) Seq() iter.Seq[objectid.ObjectID] {
-	if walk.seqUsed {
-		return func(yield func(objectid.ObjectID) bool) {
-			_ = yield
-			if walk.err == nil {
-				walk.err = errors.New("reachability: walk sequence already consumed")
-			}
-		}
-	}
-	walk.seqUsed = true
-	return func(yield func(objectid.ObjectID) bool) {
-		if walk.err != nil {
-			return
-		}
-		stack := walk.initialStack()
-		var err error
-		visited := make(map[objectid.ObjectID]struct{}, len(stack))
-		for len(stack) > 0 {
-			item := stack[len(stack)-1]
-			stack = stack[:len(stack)-1]
-
-			if containsOID(walk.haves, item.id) {
-				continue
-			}
-			if _, ok := visited[item.id]; ok {
-				continue
-			}
-			visited[item.id] = struct{}{}
-
-			var next []walkItem
-			next, err = walk.expand(item)
-			if err != nil {
-				walk.err = err
-				return
-			}
-			if !yield(item.id) {
-				return
-			}
-			stack = append(stack, next...)
-		}
-	}
-}
-
-// Err returns the terminal error, if any, once Seq has been consumed.
-func (walk *Walk) Err() error {
-	return walk.err
-}
-
-type walkItem struct {
-	id   objectid.ObjectID
-	want objecttype.Type
-}
-
-func (walk *Walk) initialStack() []walkItem {
-	if len(walk.wants) == 0 {
-		return nil
-	}
-	stack := make([]walkItem, 0, len(walk.wants))
-	for want := range walk.wants {
-		stack = append(stack, walkItem{id: want, want: objecttype.TypeInvalid})
-	}
-	return stack
-}
-
-func (walk *Walk) expand(item walkItem) ([]walkItem, error) {
-	if walk.domain == DomainCommits {
-		return walk.expandCommits(item)
-	}
-	return walk.expandObjects(item)
-}
-
-func (walk *Walk) expandCommits(item walkItem) ([]walkItem, error) {
-	ty, err := walk.readHeaderType(item.id)
-	if err != nil {
-		return nil, err
-	}
-	switch ty {
-	case objecttype.TypeCommit:
-		content, err := walk.readBytesContent(item.id)
-		if err != nil {
-			return nil, err
-		}
-		commit, err := object.ParseCommit(content, item.id.Algorithm())
-		if err != nil {
-			return nil, err
-		}
-		next := make([]walkItem, 0, len(commit.Parents))
-		for _, parent := range commit.Parents {
-			next = append(next, walkItem{id: parent, want: objecttype.TypeInvalid})
-		}
-		return next, nil
-	case objecttype.TypeTag:
-		content, err := walk.readBytesContent(item.id)
-		if err != nil {
-			return nil, err
-		}
-		tag, err := object.ParseTag(content, item.id.Algorithm())
-		if err != nil {
-			return nil, err
-		}
-		return []walkItem{{id: tag.Target, want: objecttype.TypeInvalid}}, nil
-	case objecttype.TypeTree, objecttype.TypeBlob, objecttype.TypeInvalid,
-		objecttype.TypeFuture, objecttype.TypeOfsDelta, objecttype.TypeRefDelta:
-		return nil, &ErrObjectType{OID: item.id, Got: ty, Want: objecttype.TypeCommit}
-	}
-	return nil, fmt.Errorf("reachability: unreachable object type %d", ty)
-}
-
-func (walk *Walk) expandObjects(item walkItem) ([]walkItem, error) {
-	ty, err := walk.readHeaderType(item.id)
-	if err != nil {
-		return nil, err
-	}
-	if item.want != objecttype.TypeInvalid && ty != item.want {
-		return nil, &ErrObjectType{OID: item.id, Got: ty, Want: item.want}
-	}
-
-	switch ty {
-	case objecttype.TypeBlob:
-		return nil, nil
-	case objecttype.TypeCommit:
-		content, err := walk.readBytesContent(item.id)
-		if err != nil {
-			return nil, err
-		}
-		commit, err := object.ParseCommit(content, item.id.Algorithm())
-		if err != nil {
-			return nil, err
-		}
-		next := make([]walkItem, 0, len(commit.Parents)+1)
-		next = append(next, walkItem{id: commit.Tree, want: objecttype.TypeTree})
-		for _, parent := range commit.Parents {
-			next = append(next, walkItem{id: parent, want: objecttype.TypeCommit})
-		}
-		return next, nil
-	case objecttype.TypeTree:
-		content, err := walk.readBytesContent(item.id)
-		if err != nil {
-			return nil, err
-		}
-		tree, err := object.ParseTree(content, item.id.Algorithm())
-		if err != nil {
-			return nil, err
-		}
-		next := make([]walkItem, 0, len(tree.Entries))
-		for _, entry := range tree.Entries {
-			switch entry.Mode {
-			case object.FileModeGitlink:
-				continue
-			case object.FileModeDir:
-				next = append(next, walkItem{id: entry.ID, want: objecttype.TypeTree})
-			case object.FileModeRegular, object.FileModeExecutable, object.FileModeSymlink:
-				next = append(next, walkItem{id: entry.ID, want: objecttype.TypeBlob})
-			}
-		}
-		return next, nil
-	case objecttype.TypeTag:
-		content, err := walk.readBytesContent(item.id)
-		if err != nil {
-			return nil, err
-		}
-		tag, err := object.ParseTag(content, item.id.Algorithm())
-		if err != nil {
-			return nil, err
-		}
-		return []walkItem{{id: tag.Target, want: tag.TargetType}}, nil
-	case objecttype.TypeInvalid, objecttype.TypeFuture, objecttype.TypeOfsDelta, objecttype.TypeRefDelta:
-		return nil, &ErrObjectType{OID: item.id, Got: ty, Want: item.want}
-	}
-	return nil, fmt.Errorf("reachability: unreachable object type %d", ty)
-}
-
-func (r *Reachability) peelRootToDomain(id objectid.ObjectID, domain Domain) (objectid.ObjectID, error) {
-	if err := validateDomain(domain); err != nil {
-		return objectid.ObjectID{}, err
-	}
-	for {
-		ty, err := r.readHeaderType(id)
-		if err != nil {
-			return objectid.ObjectID{}, err
-		}
-		if ty != objecttype.TypeTag {
-			if domain == DomainCommits && ty != objecttype.TypeCommit {
-				return objectid.ObjectID{}, &ErrObjectType{OID: id, Got: ty, Want: objecttype.TypeCommit}
-			}
-			return id, nil
-		}
-
-		content, err := r.readBytesContent(id)
-		if err != nil {
-			return objectid.ObjectID{}, err
-		}
-		tag, err := object.ParseTag(content, id.Algorithm())
-		if err != nil {
-			return objectid.ObjectID{}, err
-		}
-		id = tag.Target
-	}
-}
-
-func validateDomain(domain Domain) error {
-	switch domain {
-	case DomainCommits, DomainObjects:
-		return nil
-	default:
-		return fmt.Errorf("reachability: invalid domain %d", domain)
-	}
-}
-
-func containsOID(set map[objectid.ObjectID]struct{}, id objectid.ObjectID) bool {
-	if len(set) == 0 {
-		return false
-	}
-	_, ok := set[id]
-	return ok
-}
-
-// The following helpers exist because we don't have unified error handling across the entire project.
-// This will be fixed later.
-
-func (walk *Walk) readHeaderType(id objectid.ObjectID) (objecttype.Type, error) {
-	return walk.reachability.readHeaderType(id)
-}
-
-func (r *Reachability) readHeaderType(id objectid.ObjectID) (objecttype.Type, error) {
-	ty, _, err := r.Store.ReadHeader(id)
-	if err != nil {
-		if errors.Is(err, objectstore.ErrObjectNotFound) {
-			return objecttype.TypeInvalid, &ErrObjectMissing{OID: id}
-		}
-		return objecttype.TypeInvalid, err
-	}
-	return ty, nil
-}
-
-func (walk *Walk) readBytesContent(id objectid.ObjectID) ([]byte, error) {
-	content, err := walk.reachability.readBytesContent(id)
-	if err != nil {
-		return nil, err
-	}
-	return content, nil
-}
-
-func (r *Reachability) readBytesContent(id objectid.ObjectID) ([]byte, error) {
-	_, content, err := r.Store.ReadBytesContent(id)
-	if err != nil {
-		if errors.Is(err, objectstore.ErrObjectNotFound) {
-			return nil, &ErrObjectMissing{OID: id}
-		}
-		return nil, err
-	}
-	return content, nil
-}
diff --git a/reachability/reachability_unit_test.go b/reachability/unit_test.go
index ec177938..ec177938 100644
--- a/reachability/reachability_unit_test.go
+++ b/reachability/unit_test.go
diff --git a/reachability/walk.go b/reachability/walk.go
new file mode 100644
index 00000000..2b592a45
--- /dev/null
+++ b/reachability/walk.go
@@ -0,0 +1,195 @@
+package reachability
+
+import (
+	"errors"
+	"fmt"
+	"iter"
+
+	"codeberg.org/lindenii/furgit/object"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/objecttype"
+)
+
+// Walk is one single-use iterator-style traversal.
+type Walk struct {
+	reachability *Reachability
+	domain       Domain
+	haves        map[objectid.ObjectID]struct{}
+	wants        map[objectid.ObjectID]struct{}
+
+	seqUsed bool
+	err     error
+}
+
+// Seq returns the traversal sequence. It is single-use.
+func (walk *Walk) Seq() iter.Seq[objectid.ObjectID] {
+	if walk.seqUsed {
+		return func(yield func(objectid.ObjectID) bool) {
+			_ = yield
+			if walk.err == nil {
+				walk.err = errors.New("reachability: walk sequence already consumed")
+			}
+		}
+	}
+	walk.seqUsed = true
+	return func(yield func(objectid.ObjectID) bool) {
+		if walk.err != nil {
+			return
+		}
+		stack := walk.initialStack()
+		var err error
+		visited := make(map[objectid.ObjectID]struct{}, len(stack))
+		for len(stack) > 0 {
+			item := stack[len(stack)-1]
+			stack = stack[:len(stack)-1]
+
+			if containsOID(walk.haves, item.id) {
+				continue
+			}
+			if _, ok := visited[item.id]; ok {
+				continue
+			}
+			visited[item.id] = struct{}{}
+
+			var next []walkItem
+			next, err = walk.expand(item)
+			if err != nil {
+				walk.err = err
+				return
+			}
+			if !yield(item.id) {
+				return
+			}
+			stack = append(stack, next...)
+		}
+	}
+}
+
+// Err returns the terminal error, if any, once Seq has been consumed.
+func (walk *Walk) Err() error {
+	return walk.err
+}
+
+type walkItem struct {
+	id   objectid.ObjectID
+	want objecttype.Type
+}
+
+func (walk *Walk) initialStack() []walkItem {
+	if len(walk.wants) == 0 {
+		return nil
+	}
+	stack := make([]walkItem, 0, len(walk.wants))
+	for want := range walk.wants {
+		stack = append(stack, walkItem{id: want, want: objecttype.TypeInvalid})
+	}
+	return stack
+}
+
+func (walk *Walk) expand(item walkItem) ([]walkItem, error) {
+	if walk.domain == DomainCommits {
+		return walk.expandCommits(item)
+	}
+	return walk.expandObjects(item)
+}
+
+func (walk *Walk) expandCommits(item walkItem) ([]walkItem, error) {
+	ty, err := walk.readHeaderType(item.id)
+	if err != nil {
+		return nil, err
+	}
+	switch ty {
+	case objecttype.TypeCommit:
+		content, err := walk.readBytesContent(item.id)
+		if err != nil {
+			return nil, err
+		}
+		commit, err := object.ParseCommit(content, item.id.Algorithm())
+		if err != nil {
+			return nil, err
+		}
+		next := make([]walkItem, 0, len(commit.Parents))
+		for _, parent := range commit.Parents {
+			next = append(next, walkItem{id: parent, want: objecttype.TypeInvalid})
+		}
+		return next, nil
+	case objecttype.TypeTag:
+		content, err := walk.readBytesContent(item.id)
+		if err != nil {
+			return nil, err
+		}
+		tag, err := object.ParseTag(content, item.id.Algorithm())
+		if err != nil {
+			return nil, err
+		}
+		return []walkItem{{id: tag.Target, want: objecttype.TypeInvalid}}, nil
+	case objecttype.TypeTree, objecttype.TypeBlob, objecttype.TypeInvalid,
+		objecttype.TypeFuture, objecttype.TypeOfsDelta, objecttype.TypeRefDelta:
+		return nil, &ErrObjectType{OID: item.id, Got: ty, Want: objecttype.TypeCommit}
+	}
+	return nil, fmt.Errorf("reachability: unreachable object type %d", ty)
+}
+
+func (walk *Walk) expandObjects(item walkItem) ([]walkItem, error) {
+	ty, err := walk.readHeaderType(item.id)
+	if err != nil {
+		return nil, err
+	}
+	if item.want != objecttype.TypeInvalid && ty != item.want {
+		return nil, &ErrObjectType{OID: item.id, Got: ty, Want: item.want}
+	}
+
+	switch ty {
+	case objecttype.TypeBlob:
+		return nil, nil
+	case objecttype.TypeCommit:
+		content, err := walk.readBytesContent(item.id)
+		if err != nil {
+			return nil, err
+		}
+		commit, err := object.ParseCommit(content, item.id.Algorithm())
+		if err != nil {
+			return nil, err
+		}
+		next := make([]walkItem, 0, len(commit.Parents)+1)
+		next = append(next, walkItem{id: commit.Tree, want: objecttype.TypeTree})
+		for _, parent := range commit.Parents {
+			next = append(next, walkItem{id: parent, want: objecttype.TypeCommit})
+		}
+		return next, nil
+	case objecttype.TypeTree:
+		content, err := walk.readBytesContent(item.id)
+		if err != nil {
+			return nil, err
+		}
+		tree, err := object.ParseTree(content, item.id.Algorithm())
+		if err != nil {
+			return nil, err
+		}
+		next := make([]walkItem, 0, len(tree.Entries))
+		for _, entry := range tree.Entries {
+			switch entry.Mode {
+			case object.FileModeGitlink:
+				continue
+			case object.FileModeDir:
+				next = append(next, walkItem{id: entry.ID, want: objecttype.TypeTree})
+			case object.FileModeRegular, object.FileModeExecutable, object.FileModeSymlink:
+				next = append(next, walkItem{id: entry.ID, want: objecttype.TypeBlob})
+			}
+		}
+		return next, nil
+	case objecttype.TypeTag:
+		content, err := walk.readBytesContent(item.id)
+		if err != nil {
+			return nil, err
+		}
+		tag, err := object.ParseTag(content, item.id.Algorithm())
+		if err != nil {
+			return nil, err
+		}
+		return []walkItem{{id: tag.Target, want: tag.TargetType}}, nil
+	case objecttype.TypeInvalid, objecttype.TypeFuture, objecttype.TypeOfsDelta, objecttype.TypeRefDelta:
+		return nil, &ErrObjectType{OID: item.id, Got: ty, Want: item.want}
+	}
+	return nil, fmt.Errorf("reachability: unreachable object type %d", ty)
+}