# UNDF: UNDF-2026-000000631
# elixir-0001: Mix.Dep.Converger.topological_sort — O(N²) Enum.find in Enum.map

## Severity: HIGH

## Location
- `lib/mix/lib/mix/dep/converger.ex:33-35`
- Called from: `converge/4` at line 76, `Mix.Dep.Umbrella.converger.ex:75`

## Description
`topological_sort/1` takes the sorted atom list returned by `:digraph_utils.topsort/1`
and reconstructs the ordered `Mix.Dep` struct list by calling `Enum.find/2` (O(N) linear
scan) inside `Enum.map/2` (O(N) loop). The result is O(N²) where N = total flattened
dependency count for the Mix project.

`topological_sort` is called on every invocation of `Mix.Dep.Converger.converge/4`,
which runs during `mix deps.get`, `mix deps.compile`, `mix compile`, and umbrella builds.
For large Mix projects with hundreds of transitive dependencies (common in Erlang/Elixir
umbrella apps), this is a visible compilation bottleneck.

## Root Cause
```elixir
# converger.ex:32-35
if apps = :digraph_utils.topsort(graph) do
  Enum.map(apps, fn app ->
    Enum.find(deps, fn %Mix.Dep{app: other_app} -> app == other_app end)  # O(N) per app
  end)
```

`:digraph_utils.topsort/1` returns a list of atom application names.
`deps` is a list of N `Mix.Dep` structs.
For each of the N apps, `Enum.find` walks up to N deps → O(N²) total.

## Fix
Build a map from app atom to dep struct before the loop, then do O(1) lookups:

```elixir
if apps = :digraph_utils.topsort(graph) do
  dep_index = Map.new(deps, fn %Mix.Dep{app: app} = dep -> {app, dep} end)
  Enum.map(apps, fn app -> dep_index[app] end)
```

`Map.new/2` is O(N), `dep_index[app]` is O(1), total O(N).

## Complexity
| | Before | After |
|---|---|---|
| topological_sort | O(N²) | O(N) |
| per mix compile | O(N²) | O(N) |

## Impact
A Mix umbrella application with 200 apps triggers 200 × 200 = 40,000 comparisons per
compile. With N=500 (Nerves embedded frameworks, large Phoenix monorepos) that is
250,000 comparisons. The fix reduces this to 500 comparisons.