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

# 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):

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.

2.5 KiB Raw Permalink Blame History Unescape Escape