# UNDF: UNDF-2026-000000698
# elixir-0002: Kernel.Typespec — used_type_pairs list O(T²) compile-time membership scan

## Severity: MEDIUM

## Location
- `lib/elixir/lib/kernel/typespec.ex:234` — initial state: `used_type_pairs: []`
- `lib/elixir/lib/kernel/typespec.ex:928` — `if :lists.member({name, arity}, state.used_type_pairs)`
- `lib/elixir/lib/kernel/typespec.ex:931` — `%{state | used_type_pairs: [{name, arity} | state.used_type_pairs]}`
- `lib/elixir/lib/kernel/typespec.ex:296` — `if not export and not :lists.member(type_pair, state.used_type_pairs)`

## Description

`Kernel.Typespec` tracks which private type definitions are referenced during
module compilation using `state.used_type_pairs`, initialized as an empty list `[]`
at line 234.

During type-spec translation (`typespec/4`), each `@type` reference triggers a check:

```elixir
# typespec.ex:928
if :lists.member({name, arity}, state.used_type_pairs) do
  state
else
  %{state | used_type_pairs: [{name, arity} | state.used_type_pairs]}
end
```

`typespec/4` is a recursive descent over type ASTs — it is called for every node in
every `@type`, `@spec`, `@callback`, and `@macrocallback` definition. Each call that
encounters a type reference (`:user_type`) does an O(T) `:lists.member/2` scan where
T = `length(state.used_type_pairs)`, which grows up to the number of distinct private
types referenced.

At the end of compilation, `filter_used_types/2` also calls `:lists.member/2` once per
type, repeating the O(T) scan for each of T types = another O(T²) pass:

```elixir
# typespec.ex:296
if not export and not :lists.member(type_pair, state.used_type_pairs) do
```

**Total compile-time complexity: O(R × T)** where R = total type references in the
module's specs and T = number of distinct private types — effectively O(T²) when R
grows proportionally to T.

## Root Cause

`used_type_pairs` is stored as an Elixir list. `:lists.member/2` is O(N). The list
grows with every new distinct type reference encountered. In large generated modules
(e.g. protobuf-generated Elixir code, large NimbleOptions schemas, or modules with
hundreds of private types), this causes measurable compile-time slowdowns.

## Fix

Replace the list with a `MapSet`, giving O(log N) membership checks and O(log N)
insertion:

```diff
--- a/lib/elixir/lib/kernel/typespec.ex
+++ b/lib/elixir/lib/kernel/typespec.ex
@@ -231,7 +231,7 @@ defmodule Kernel.Typespec do
       defined_type_pairs: %{},
       used_type_pairs: [],
+      used_type_pairs: MapSet.new(),
       ...
```

```diff
@@ -925,9 +925,9 @@ defmodule Kernel.Typespec do
-          if :lists.member({name, arity}, state.used_type_pairs) do
+          if MapSet.member?(state.used_type_pairs, {name, arity}) do
             state
           else
-            %{state | used_type_pairs: [{name, arity} | state.used_type_pairs]}
+            %{state | used_type_pairs: MapSet.put(state.used_type_pairs, {name, arity})}
           end
```

```diff
@@ -293,7 +293,7 @@ defmodule Kernel.Typespec do
-      if not export and not :lists.member(type_pair, state.used_type_pairs) do
+      if not export and not MapSet.member?(state.used_type_pairs, type_pair) do
```

## Complexity

| N private types | Before (list) | After (MapSet) |
|-----------------|---------------|----------------|
| 50              | ~1,250 checks | ~300 checks    |
| 200             | ~20,000 checks| ~1,400 checks  |
| 500             | ~125,000 checks | ~4,500 checks |
| speedup at 500  | —             | ~28×           |

## Impact

Any module with more than ~20 private types and many cross-references sees
superlinear compile overhead. The most affected use cases are:

- Protobuf-generated Elixir modules (hundreds of `@type` definitions)
- Large NimbleOptions or Ecto schema modules
- Phoenix LiveView helpers with many callback typespecs
- Hex packages that expose rich typespec APIs

For a module with 200 private types, each referenced 5 times on average, the
current code performs ~20,000 membership checks; the fix reduces this to ~1,400.
