# UNDF: UNDF-2026-000000493
# opentofu-0002: readConfigSnapshot manifest validation O(M²) linear scan

## Classification
- **Severity**: LOW-MEDIUM
- **CWE**: CWE-407 (Algorithmic Complexity — Inefficient Algorithmic Complexity)
- **Component**: `internal/plans/planfile/config_snapshot.go`

## Location
`internal/plans/planfile/config_snapshot.go`, function `readConfigSnapshot()`, lines 133–144

```go
// Finally, we'll make sure we don't have any errant files for modules that
// aren't in the manifest.
for k := range snap.Modules {
    found := false
    for _, record := range manifest {   // O(R) scan per module key
        if record.Key == k {
            found = true
            break
        }
    }
    if !found {
        return nil, fmt.Errorf("found files for module %q that isn't recorded in the manifest", k)
    }
}
```

## Pattern
For each of M module keys in `snap.Modules`, a linear scan through R manifest records is performed. Total complexity: O(M × R). In practice M ≈ R (every module has a manifest entry), making this O(M²).

The manifest was already processed in the loop at line 108 to populate `snap.Modules` — the key set from the manifest is already implicitly known. A single pass to build a `map[string]bool` of manifest keys eliminates the inner scan entirely.

## Speedup
At M=R=200 modules: 40,000 comparisons → 400 comparisons (100x reduction)

## Patch

```diff
--- a/internal/plans/planfile/config_snapshot.go
+++ b/internal/plans/planfile/config_snapshot.go
@@ -102,6 +102,12 @@ func readConfigSnapshot(z *zip.Reader) (*configload.Snapshot, error) {
 	var manifest configSnapshotModuleManifest
 	err := json.Unmarshal(manifestSrc, &manifest)

+	// Build a set of manifest keys for O(1) lookup below
+	manifestKeys := make(map[string]bool, len(manifest))
 	for _, record := range manifest {
+		manifestKeys[record.Key] = true
+	}
+
+	for _, record := range manifest {
 		modSnap, exists := snap.Modules[record.Key]
 		...
 	}
@@ -131,11 +137,7 @@ func readConfigSnapshot(z *zip.Reader) (*configload.Snapshot, error) {
 	// aren't in the manifest.
 	for k := range snap.Modules {
-		found := false
-		for _, record := range manifest {
-			if record.Key == k {
-				found = true
-				break
-			}
-		}
-		if !found {
+		if !manifestKeys[k] {
 			return nil, fmt.Errorf("found files for module %q that isn't recorded in the manifest", k)
 		}
 	}
```

## Complexity
- Before: O(M × R) ≈ O(M²) — M modules, R manifest records
- After: O(M + R) — one pass to build set, one pass to validate
