# UNDF: UNDF-2026-000000640
# nim-0002: trees.cyclicTreeAux — O(N²) linear visited-seq scan in recursive DFS

## Severity: MEDIUM

## Location
- `compiler/trees.nim:15-24` — `cyclicTreeAux`
- Called from: `compiler/vm.nim:2590` after every macro expansion

## Description
`cyclicTreeAux` detects cycles in a `PNode` AST tree using a depth-first search.
The cycle check is implemented by maintaining a `seq[PNode]` called `visited` (acting
as the DFS path stack) and scanning it linearly with `for v in visited: if v == n`.

For a tree of depth D, at each node the scan is O(D). For a path graph (maximally deep
AST) with N nodes, depth D = N, and the scan at every node costs O(N) → total O(N²).

`cyclicTree` is called by `vm.nim:2590` after **every macro expansion** during
compilation. Nim macros are a first-class language feature; programs using macros
heavily (meta-programming, DSLs, template libraries) trigger this check frequently
with potentially large AST outputs.

## Root Cause
```nim
# trees.nim:15-24
proc cyclicTreeAux(n: PNode, visited: var seq[PNode]): bool =
  result = false
  if n == nil: return
  for v in visited:           # O(D) linear scan of path stack
    if v == n: return true    # pointer equality check
  if not (n.kind in {nkEmpty..nkNilLit}):
    visited.add(n)
    for nSon in n.sons:
      if cyclicTreeAux(nSon, visited): return true
    discard visited.pop()
```

`visited` is a path-stack (add on descent, pop on ascent). The cycle check `for v in
visited` scans all ancestors at every node — O(D) per node, O(N×D) total. For deep
ASTs, D approaches N, giving O(N²).

## Fix
Replace the `seq[PNode]` with a `HashSet[pointer]` (hashing the `PNode` pointer):

```nim
proc cyclicTreeAux(n: PNode, visited: var HashSet[pointer]): bool =
  result = false
  if n == nil: return
  if cast[pointer](n) in visited: return true    # O(1)
  if not (n.kind in {nkEmpty..nkNilLit}):
    visited.incl(cast[pointer](n))
    for nSon in n.sons:
      if cyclicTreeAux(nSon, visited): return true
    visited.excl(cast[pointer](n))
```

`HashSet[pointer]` with `incl`/`excl` for path tracking gives O(1) membership test
at each node → O(N) total.

## Complexity
| | Before | After |
|---|---|---|
| cyclicTreeAux (path graph, N nodes) | O(N²) | O(N) |
| cyclicTree (balanced tree, depth D) | O(N×D) | O(N) |

## Impact
Every macro that returns a large AST triggers O(N²) cycle detection. A macro returning
a 1,000-node AST (common for code generation macros) triggers 1,000,000 comparisons
versus 1,000 hash operations with the fix.
