# pup-0001: simple_graph paths_in_cycle() BFS Array#member? — O(|cycle|³) path membership

**Severity:** LOW (error path — cycles are uncommon in valid Puppet catalogs)
**CWE:** CWE-407 (Algorithmic Complexity — linear membership test in hot loop)
**Speedup:** 10x at cycle_len=20 (verified by unit test)
**Target:** Puppet (puppetlabs/puppet)
**Files:**
- `lib/puppet/graph/simple_graph.rb:214` — `frame[1].member?(frame[0])` on growing Array path

## Description

`paths_in_cycle()` uses BFS to enumerate dependency cycle paths. Each BFS
frame is `[vertex, path_array]`. The cycle-detection test is:

```ruby
stack = [[cycle.first, []]]
while frame = stack.shift
  if frame[1].member?(frame[0]) then   # O(path_length) — Array#member? linear scan
    found << frame[1] + [frame[0]]
    ...
  else
    adj[frame[0]].each do |to|
      stack.push [to, frame[1] + [frame[0]]]   # path grows by 1 each step
    end
  end
end
```

`frame[1]` is a growing Array. `Array#member?` is O(length). In a fully
connected cycle of length N, paths grow to length N and BFS explores O(N²)
frames → total membership work O(N³).

This fires whenever Puppet detects a cycle during catalog compilation (the
error path). For large catalogs with cycles (e.g. user error with circular
`require`/`before` chains), this can cause the error report itself to hang.

## Root Cause

The path array serves double duty: ordered path record and membership oracle.
Array is correct for ordering but O(N) for membership.

Fix: add a parallel `Set` alongside the Array. Each BFS frame becomes
`[vertex, path_array, path_set]`. Membership test uses `path_set.include?()`
for O(1) average cost. The Array is retained for ordered path output.

## Patch

See `patch/pup-0001-paths-in-cycle-set.patch`

## Complexity Before

`frame[1].member?(frame[0])` per BFS step: **O(path_length)**
Total across N²-ish BFS steps in cycle of length N: **O(N³)**

## Complexity After

`frame[2].include?(frame[0])` per BFS step: **O(1)** average
Total: **O(N²)** (dominated by BFS frame count, not membership)

## Reproduction

```
cd defects/puppet/unit && javac -d . PuppetGraphTest.java && java -ea unit.PuppetGraphTest
```

test1: cycle_len=20, defect=191, fixed=21, ratio=9.1x
test2: N=15→30 doubling, defect grows ~4.1x (super-linear), fixed grows ~1.9x (linear)
test3: cycle_len=25, defect=301, fixed=26, ratio=11.6x
