# UNDF: UNDF-2026-000000528
# UNDF: (pending)
# erlang-0004: edlin_type_suggestion print_type — Visited list O(D²) membership scan

## CWE-407 — Algorithmic Complexity: O(D²) linear scan in type variable chain traversal

| Field        | Value |
|--------------|-------|
| ID           | erlang-0004 |
| Severity     | LOW |
| Ecosystem    | erlang |
| Package      | stdlib |
| File         | `lib/stdlib/src/edlin_type_suggestion.erl` |
| Lines        | 443–450 |
| Complexity   | O(D²) total for type variable aliasing chain of depth D |
| Hot path     | Erlang shell REPL autocompletion — called per tab-completion event |

## Defect

`print_type/4` resolves type variable constraints recursively. It tracks already-visited
type variables in `Visited`, a plain Erlang list. At each recursion step it scans
the entire list with `lists:member(Var, Visited)` — an O(D) scan — then prepends
the new variable with `[Var | Visited]`. For a chain of D aliased type variables
(A :: B, B :: C, C :: D, ...) the total scan cost is O(D²).

```erlang
%% Line 443–450 (DEFECT: O(D) scan per step, O(D²) for chain depth D)
print_type({var, Name}=Var, Constraints, Visited, Options) ->
    case lists:member(Var, Visited) of          %% O(D) linear scan
        true -> atom_to_list(Name);
        false ->
            case get_constraint(Var, Constraints) of
                {constraint, _, T2} ->
                    print_type(T2, Constraints, [Var| Visited], Options);  %% prepend
                _ -> atom_to_list(Name)
            end
    end;
```

The two public wrappers initialize `Visited` to `[]`:

```erlang
print_type(Type, Constraints) ->
    lists:flatten(print_type(Type, Constraints, [], [])).
print_type(Type, Constraints, Options) ->
    lists:flatten(print_type(Type, Constraints, [], Options)).
```

## Fix

Replace the list-based `Visited` accumulator with an Erlang `sets` set.
The wrappers initialize `sets:new()`; the recursive clause uses
`sets:is_element/2` (O(1)) and `sets:add_element/2`.
All other `print_type/4` clauses pass `V` through unchanged — they are
unaffected by the type change.

```erlang
%% AFTER — O(D) total
print_type(Type, Constraints) ->
    lists:flatten(print_type(Type, Constraints, sets:new(), [])).
print_type(Type, Constraints, Options) ->
    lists:flatten(print_type(Type, Constraints, sets:new(), Options)).

print_type({var, Name}=Var, Constraints, Visited, Options) ->
    case sets:is_element(Var, Visited) of       %% O(1)
        true -> atom_to_list(Name);
        false ->
            case get_constraint(Var, Constraints) of
                {constraint, _, T2} ->
                    print_type(T2, Constraints, sets:add_element(Var, Visited), Options);
                _ -> atom_to_list(Name)
            end
    end;
```

## Speedup

| Chain depth (D) | Before (comparisons) | After (comparisons) | Speedup |
|----------------|---------------------|---------------------|---------|
| 10             | 55                  | 10                  | 5.5×    |
| 50             | 1,275               | 50                  | 25.5×   |
| 100            | 5,050               | 100                 | 50.5×   |
| 1,000          | 500,500             | 1,000               | 500×    |

Growth before: O(D²). Growth after: O(D).

## Notes

- Practical D for type-variable aliasing chains is small (typically ≤ 5); the
  structural defect exists regardless and can be triggered by crafted type specs.
- Severity is LOW: this path is only exercised during REPL shell autocompletion,
  not in production Erlang applications.
