# Nim — CWE-407 Disclosure Brief

**Project:** Nim
**Disclosure date:** 2026-03-27
**Severity:** HIGH
**Speedup:** 749×
**Status:** PATCHED

---

## Finding

Nim contains two independent quadratic-complexity defects. The standard library's `deduplicate()` procedure in `sequtils` uses a linear `contains` scan inside a loop, producing O(N²) deduplication. The compiler itself has a separate O(N²) DFS visited-node check in `compiler/ast.nim` that uses a linear scan over a `seq` instead of a hash set. Both defects compound in compilation of Nim programs that process or generate large sequences.

## The Defect(s)

| ID | Location | Pattern | Complexity |
|----|----------|---------|------------|
| nim-0001 | `lib/pure/sequtils.nim` | `result.contains(itm)` O(N) scan inside `for item in seq` loop | O(N²) |
| nim-0002 | `compiler/ast.nim` | `for v in visited: if v == n` O(N) scan per DFS frame in cyclic-tree check | O(N²) |

## Complexity Proof

**nim-0001** — Let N = length of the input sequence.

`deduplicate()` iterates over every element and checks `result.contains(itm)`, which is a sequential scan of the result list built so far. At step i, result holds up to i unique elements, making the check O(i):

```
Step 1: scan up to 1 element
Step 2: scan up to 2 elements
...
Step N: scan up to N elements
Total: 1 + 2 + ... + N = N(N+1)/2 = O(N²)
```

A `HashSet` shadow reduces each membership test to O(1) amortized, making the full pass O(N). Measured speedup at N = 10,000: 749×.

**nim-0002** — Let N = number of AST nodes visited during a DFS traversal.

Each DFS frame checks whether the current node `n` has already been visited by iterating `for v in visited: if v == n`. The `visited` collection is a `seq[PNode]` with linear scan. In the worst case (long linear chain), each of the N frames scans up to N entries:

```
Total comparisons ≤ 1 + 2 + ... + N = N(N+1)/2 = O(N²)
```

Replacing `visited` with a `HashSet[PNode]` (keyed by pointer identity) reduces each check to O(1), making the DFS O(N+E).

## Impact

**nim-0001** affects any Nim program or library using `sequtils.deduplicate` on sequences of non-trivial length. This is a standard-library primitive, so the impact is broad. Nim programs doing data deduplication — parsers, compilers written in Nim, data processing pipelines — all regress quadratically with input size.

**nim-0002** affects the Nim compiler itself during AST traversal of recursive or deeply nested type graphs. Projects using complex generic instantiation, macro expansion over large ASTs, or deep inheritance hierarchies trigger this path. Compilation time for such projects grows quadratically with AST depth.

## The Fix

**nim-0001:** Add a `HashSet` shadow alongside the result sequence. Before appending to `result`, check membership in the set (O(1)); on append, insert into both.

**nim-0002:** Replace the `seq[PNode]` visited collection with a `HashSet[PNode]` using pointer-identity hashing. The `containsOrIncl` operation is O(1) amortized.

## Patch

```diff
# nim-0001: lib/pure/sequtils.nim
- proc deduplicate*[T](s: openArray[T]): seq[T] =
-   result = @[]
-   for item in s:
-     if not result.contains(item):
-       result.add(item)
+ proc deduplicate*[T](s: openArray[T]): seq[T] =
+   result = @[]
+   var seen = initHashSet[T]()
+   for item in s:
+     if not seen.containsOrIncl(item):
+       result.add(item)

# nim-0002: compiler/ast.nim
- var visited: seq[PNode] = @[]
- ...
- for v in visited:
-   if v == n: return
- visited.add(n)
+ var visited = initHashSet[PNode]()
+ ...
+ if n in visited: return
+ visited.incl(n)
```

## What We Ask

Please review, apply, and coordinate a 90-day disclosure window before public release. Reply to security@undefect.com.

---

*This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com*
