repository: Add full-traversal benchmark

3 files changed, 143 insertions, 37 deletions

diff --git a/repository/traversal_bench_test.go b/repository/traversal_bench_test.go
new file mode 100644
index 00000000..508527cb
--- /dev/null
+++ b/repository/traversal_bench_test.go
@@ -0,0 +1,60 @@
+package repository_test
+
+import (
+	"os"
+	"strings"
+	"testing"
+
+	"codeberg.org/lindenii/furgit/object"
+	"codeberg.org/lindenii/furgit/repository"
+)
+
+const benchRepoPathEnv = "FURGIT_BENCH_REPO"
+
+// BenchmarkTraverseHeadTree measures iterative traversal of HEAD's root tree.
+//
+// Set FURGIT_BENCH_REPO to a repository path (typically .git or a bare repo)
+// before running this benchmark.
+func BenchmarkTraverseHeadTree(b *testing.B) {
+	repoPath := strings.TrimSpace(os.Getenv(benchRepoPathEnv))
+	if repoPath == "" {
+		b.Fatalf("missing %s", benchRepoPathEnv)
+	}
+
+	repo, err := repository.Open(repoPath)
+	if err != nil {
+		b.Fatalf("repository.Open(%q): %v", repoPath, err)
+	}
+	b.Cleanup(func() {
+		_ = repo.Close()
+	})
+
+	head, err := repo.ResolveRefFully("HEAD")
+	if err != nil {
+		b.Fatalf("ResolveRefFully(HEAD): %v", err)
+	}
+	stored, err := repo.ReadStored(head.ID)
+	if err != nil {
+		b.Fatalf("ReadStored(%s): %v", head.ID, err)
+	}
+	commit, ok := stored.Object().(*object.Commit)
+	if !ok {
+		b.Fatalf("HEAD object type %T, want *object.Commit", stored.Object())
+	}
+
+	b.ReportAllocs()
+	b.ResetTimer()
+
+	var lastCount int
+	for range b.N {
+		lastCount, err = traverseTreeIter(repo, commit.Tree)
+		if err != nil {
+			b.Fatalf("traverseTreeIter: %v", err)
+		}
+	}
+
+	b.StopTimer()
+	if lastCount <= 0 {
+		b.Fatalf("traverseTreeIter count = %d, want > 0", lastCount)
+	}
+}
diff --git a/repository/traversal_helpers_test.go b/repository/traversal_helpers_test.go
new file mode 100644
index 00000000..09cd61bd
--- /dev/null
+++ b/repository/traversal_helpers_test.go
@@ -0,0 +1,79 @@
+package repository_test
+
+import (
+	"codeberg.org/lindenii/furgit/object"
+	"codeberg.org/lindenii/furgit/objectid"
+	"codeberg.org/lindenii/furgit/repository"
+)
+
+func traverseTreeIter(repo *repository.Repository, root objectid.ObjectID) (int, error) {
+	stack := []objectid.ObjectID{root}
+	total := 0
+
+	for len(stack) > 0 {
+		id := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+
+		stored, err := repo.ReadStored(id)
+		if err != nil {
+			return 0, err
+		}
+		total++
+
+		tree, ok := stored.Object().(*object.Tree)
+		if !ok {
+			continue
+		}
+		for i := len(tree.Entries) - 1; i >= 0; i-- {
+			entry := tree.Entries[i]
+			if entry.Mode == object.FileModeGitlink {
+				continue
+			}
+			stack = append(stack, entry.ID)
+		}
+	}
+
+	return total, nil
+}
+
+func traverseReachableIter(repo *repository.Repository, root objectid.ObjectID) (int, error) {
+	stack := []objectid.ObjectID{root}
+	visited := make(map[objectid.ObjectID]struct{})
+	total := 0
+
+	for len(stack) > 0 {
+		id := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+		if _, ok := visited[id]; ok {
+			continue
+		}
+		visited[id] = struct{}{}
+
+		stored, err := repo.ReadStored(id)
+		if err != nil {
+			return 0, err
+		}
+		total++
+
+		switch obj := stored.Object().(type) {
+		case *object.Commit:
+			stack = append(stack, obj.Tree)
+			stack = append(stack, obj.Parents...)
+		case *object.Tree:
+			for i := len(obj.Entries) - 1; i >= 0; i-- {
+				entry := obj.Entries[i]
+				if entry.Mode == object.FileModeGitlink {
+					continue
+				}
+				stack = append(stack, entry.ID)
+			}
+		case *object.Tag:
+			stack = append(stack, obj.Target)
+		case *object.Blob:
+		default:
+			// Unknown parsed object variants are treated as leaves.
+		}
+	}
+
+	return total, nil
+}
diff --git a/repository/traversal_test.go b/repository/traversal_test.go
index 2627f711..e6e3445a 100644
--- a/repository/traversal_test.go
+++ b/repository/traversal_test.go
@@ -8,7 +8,6 @@ import (
 	"testing"
 
 	"codeberg.org/lindenii/furgit/internal/testgit"
-	"codeberg.org/lindenii/furgit/object"
 	"codeberg.org/lindenii/furgit/objectid"
 	"codeberg.org/lindenii/furgit/repository"
 )
@@ -103,43 +102,11 @@ func walkRepositoryFromHead(t *testing.T, repoPath string) {
 	if err != nil {
 		t.Fatalf("ResolveRefFully(HEAD): %v", err)
 	}
-
-	visited := make(map[objectid.ObjectID]bool)
-	queue := []objectid.ObjectID{head.ID}
-	objectsRead := 0
-
-	for len(queue) > 0 {
-		id := queue[0]
-		queue = queue[1:]
-
-		if visited[id] {
-			continue
-		}
-		visited[id] = true
-
-		stored, err := repo.ReadStored(id)
-		if err != nil {
-			t.Fatalf("ReadStored(%s): %v", id, err)
-		}
-		objectsRead++
-
-		switch obj := stored.Object().(type) {
-		case *object.Commit:
-			queue = append(queue, obj.Tree)
-			queue = append(queue, obj.Parents...)
-		case *object.Tree:
-			for _, entry := range obj.Entries {
-				queue = append(queue, entry.ID)
-			}
-		case *object.Tag:
-			queue = append(queue, obj.Target)
-		case *object.Blob:
-		default:
-			t.Fatalf("unexpected object type: %T", obj)
-		}
+	objectsRead, err := traverseReachableIter(repo, head.ID)
+	if err != nil {
+		t.Fatalf("traverseReachableIter(%s): %v", head.ID, err)
 	}
-
-	if objectsRead == 0 {
+	if objectsRead <= 0 {
 		t.Fatalf("no objects were enumerated from HEAD (%s)", fmt.Sprintf("%q", repoPath))
 	}
 }