reachability: Split walk files

1 files changed, 69 insertions, 0 deletions

diff --git a/reachability/walk_seq.go b/reachability/walk_seq.go
new file mode 100644
index 00000000..ad3415d1
--- /dev/null
+++ b/reachability/walk_seq.go
@@ -0,0 +1,69 @@
+package reachability
+
+import (
+	"errors"
+	"iter"
+
+	"codeberg.org/lindenii/furgit/objectid"
+)
+
+// 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
+}