54 lines
1.9 KiB
Markdown
54 lines
1.9 KiB
Markdown
# 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.
|