# UNDF: UNDF-2026-000000639
# nim-0001: sequtils.deduplicate — O(N²) result.contains in for loop

## Severity: HIGH

## Location
- `lib/pure/collections/sequtils.nim:236-237`
- Public stdlib API: `import std/sequtils; deduplicate(seq)`

## Description
`deduplicate[T](s: openArray[T], isSorted: bool = false): seq[T]` deduplicates a
sequence by building the result array one element at a time. For each input element
`itm`, it calls `result.contains(itm)` — which is an O(N) linear scan of the
result array — before deciding to append. This makes the unsorted path O(N²).

The function is public stdlib API used throughout the Nim ecosystem. The `isSorted`
fast path exists (O(N) via adjacent comparison) but the default `isSorted = false`
path is always O(N²). Users who don't pass `isSorted = true` or who have unsortable
types get quadratic behavior silently.

The Nim compiler itself calls `deduplicate` (via `nimsets.nim:713`) during enum set
deduplication in type-checking.

## Root Cause
```nim
# sequtils.nim:226-237
result = @[]
if s.len > 0:
  if isSorted:
    var prev = s[0]
    result.add(prev)
    for i in 1..s.high:
      if s[i] != prev:
        prev = s[i]
        result.add(prev)
  else:
    for itm in items(s):
      if not result.contains(itm): result.add(itm)  # O(N) scan, O(N) outer = O(N²)
```

`result.contains(itm)` on a `seq[T]` is O(len(result)) linear scan.
Called for every element in the input → O(N²) total.

## Fix
For hashable types, use a `HashSet` as a seen-tracker alongside the result:

```nim
else:
  var seen = initHashSet[T]()
  for itm in items(s):
    if itm notin seen:
      seen.incl(itm)
      result.add(itm)
```

For non-hashable types (no `hash` proc), sorting then deduplicating is O(N log N).
A two-overload approach can dispatch at compile time using `when compiles(hash(s[0]))`.

## Complexity
| | Before | After |
|---|---|---|
| deduplicate (unsorted, hashable) | O(N²) | O(N) |
| deduplicate (unsorted, non-hashable) | O(N²) | O(N log N) |
| deduplicate (isSorted = true) | O(N) | O(N) unchanged |

## Impact
Any Nim code that calls `deduplicate` on a sequence of N elements without passing
`isSorted = true` incurs O(N²) cost. At N=10,000 that is 100 million comparisons
versus 10,000 hash lookups. Affected: all code using `import std/sequtils` and
calling `deduplicate` on unsorted data.
