Pathological type-checking time in v1.20 for functions returning large nested struct literals (fixed on main by #15433)

[zachdaniel]

Elixir and Erlang/OTP versions

Slow: Elixir 1.20.0, 1.20.1, 1.20.2, and current v1.20 branch tip (clean build)
Fast: Elixir 1.19.5 and current main (1.21.0-dev)
Erlang/OTP 28 and 29

Operating system

macOS (Apple Silicon)

Current behavior

A single ~7KB module containing one function that returns a list of two deeply nested struct-shaped literals takes ~20 seconds to compile on Elixir 1.20.x, with essentially all of the time spent in Module.Types.Descr (tuple_empty?/map_empty?/literal intersections/BDD operations, observed via stack sampling).

Repro (single file, no dependencies): https://gist.github.com/zachdaniel/06f817e6b5e02d154d528349dff7a678

$ time elixirc type_blowup.ex

Version	Time
1.19.5	0.5s
1.20.0 / 1.20.1 / 1.20.2	~20s
v1.20 branch tip (post-1.20.2, clean build)	~20s
main (1.21.0-dev)	0.4s

Some observations:

• Each of the two literals alone compiles in ~0.4s; the blowup requires the combination — the union of the two element types in one list literal. Two functions each returning one of the literals is also fine, until a third function returns [calc1(), calc2()], which brings the ~20s back.
• infer_signatures: false does not avoid it.
• The struct literals are similar in shape but not equal: both are Ash.Resource.Calculation structs whose :calculation field contains different deeply nested Ash.Query.Call trees (escaped expression ASTs), nesting depth ~10.

Real-world impact: Ash embeds exactly this kind of data in functions generated into user modules, so any Ash resource with two or more inline expression calculations hits this. A user reported a single file taking several minutes to compile (ash-project/ash#2798) — I measured ~7 minutes for that one resource on 1.20.0 vs 0.3s on 1.19.5, since the data appears in several generated functions and is re-checked in the group pass.

I bisected the fix on main: the first fast commit is 9f24a45 ("Provide bare and opt set operations", #15433) — its direct parent still exhibits the ~20s behavior, no skipped builds. None of the Descr commits that were backported to v1.20 (e.g. #15518) help.

Expected behavior

Compile times comparable to 1.19/main on the v1.20 branch.

---

Opened for documentation purposes.

[josevalim]

Unfortunately the fix is quite complex to backport and it may introduce other regressions... perhaps we should just release v1.21 sooner. Other projects, like the Phoenix Router, were also affected.