Summary
This RFC proposes a MIR-level analysis for flow-directed monomorphization, based on The Simple Essence of Monomorphization. The paper formulates monomorphization as a type-flow problem: collect constraints τ ⊑ α, solve the resulting flow graph, and specialize the finite set of reachable type instances. It shows that higher-rank type polymorphism and existential types are not fundamental obstacles to monomorphization; the actual obstruction is cyclic type flow requiring infinitely many specializations.
The analysis provides a finite-monomorphization criterion for Rust abstractions involving hidden or higher-rank type flow, including opaque types from impl Trait, async fn, TAIT, RPITIT, and closed-world generic methods behind dynamic dispatch. It also turns infinite monomorphization from an operational failure mode into a structural error detected before recursive expansion.
Motivation
Rust’s current monomorphization machinery is demand-driven: rustc discovers reachable mono items and recursively expands the required instances. This works well for ordinary generics, but it gives the compiler no explicit finite-solution criterion for abstractions whose type instantiations are hidden, delayed, or higher-rank.
The most direct application is closed-world generic dynamic dispatch. A generic method such as fn encode<T>(&self, value: T) cannot be represented by a conventional open-world vtable, because the set of possible T is unbounded. In a closed-world setting, however, the compiler may be able to prove a finite solution, for example T ↦ { i32, String, Vec }. That solution gives a concrete lowering strategy: generate encode_i32, encode_String, and encode_Vec_u8 as the complete method family.
The same problem appears in a different form for opaque types. Rust’s impl Trait, async fn, TAIT, and RPITIT all involve hidden but concrete types. These types are not runtime existentials in the usual sense, but they create the same compiler question: how does a hidden concrete type participate in generic instantiation, and does that flow remain finite? A flow graph gives rustc a uniform answer without relying on feature-specific reasoning.
A second application is robustness. For fn f<T>(x: T) { f(Some(x)); }, called as f(0_i32), the compiler requires f::<i32>, f::<Option<i32>>, f::<Option<Option<i32>>>, and so on. The flow graph exposes the cause as i32 ⊑ T and Option<T> ⊑ T, i.e. the growing cycle T --Option--> T. Such a program has no finite monomorphization under this analysis and can be rejected before expansion.
Guide-level explanation
The compiler builds a type-flow graph during MIR monomorphization collection. A constraint τ ⊑ α means that the codegen-relevant type expression τ flows into the generic parameter α.
For an ordinary generic function fn id<T>(x: T) -> T, calls at i32 and String produce i32 ⊑ T and String ⊑ T. The solution is T ↦ { i32, String }, so the required instances are id::<i32> and id::<String>.
For generic forwarding, fn g<U>(x: U) { h::<U>(x); } produces U ⊑ T, where T is the parameter of h. For structured instantiation, f::<Option<U>>(Some(x)) produces Option<U> ⊑ T.
Growing cycles are rejected. The cycle T --Option--> T denotes an infinite sequence of types; the cycle formed by T ⊑ U and U ⊑ T does not, because it merely equates two flow sets.
Lifetimes are erased before graph construction. &'a i32 and &'static i32 both contribute the same codegen-relevant type &i32. Type parameters and const parameters remain specialization dimensions.
Reference-level explanation
Position in rustc
The analysis runs during MIR monomorphization collection, after type checking and borrow checking. It operates on normalized, codegen-relevant types. Regions are erased before constructing graph keys.
The solver computes a finite mapping S(α) = { ρ₁, ρ₂, … }, where each ρ is a lifetime-erased concrete type. Failure to compute such a finite mapping indicates a growing type-flow cycle.
Constraint collection
At each generic instantiation site, rustc emits a flow constraint from the actual type argument to the callee’s generic parameter. A call f::<i32>(0) emits i32 ⊑ T. A call f::<U>(x) emits U ⊑ T. A call f::<Option<U>>(Some(x)) emits Option<U> ⊑ T.
Method-level type parameters are handled the same way. If a generic method is used at i32 and bool, the graph contains i32 ⊑ A and bool ⊑ A. In a closed-world lowering, the solution A ↦ { i32, bool } justifies generating method_i32 and method_bool.
Solving
The solver computes the least finite solution of the collected constraints. A cycle is rejected when returning to the same parameter applies a non-empty type-constructor stack. Thus T --Option--> T is rejected; T ⊑ U and U ⊑ T is accepted.
This gives the central criterion: finite type-flow solution implies finite monomorphization; growing cycle implies no finite monomorphization under this analysis.
Opaque types
Opaque types are represented explicitly in the graph.
Argument-position impl Trait is modeled as an anonymous generic parameter. Thus fn f(x: impl Clone) contributes the same kind of flow as fn f<T: Clone>(x: T).
Return-position impl Trait is modeled as an opaque but concrete result. For fn once<T>(x: T) -> impl Iterator<Item = T> { std::iter::once(x) }, the graph contains ordinary parameter flow into once::T and hidden result flow Once<T> ⊑ once::ReturnOpaque<T>. Calls at i32 and String yield the opaque instances once::ReturnOpaque<i32> and once::ReturnOpaque<String>.
async fn is represented analogously through its opaque future type. RPITIT is represented through the associated opaque types produced by existing lowering.
Higher-rank and existential flow
Higher-rank type parameters become flow targets. A type-polymorphic method used at i32 and bool receives i32 ⊑ A and bool ⊑ A, producing a finite method family when the solution is finite.
Existential packaging is represented by flow from construction to unpacking. Packing at i32 and String contributes i32 ⊑ A and String ⊑ A; unpacking contributes A ⊑ B. This matches the paper’s treatment of existential types as the dual of higher-rank method instantiation.
Rust opaque types are not general runtime existential packages, but they share the relevant static property: a concrete type is hidden at an interface boundary and must still be tracked through generic instantiation.
Proposed implementation
Stage 1 adds a graph builder behind -Z flow-directed-mono. It mirrors existing monomorphization collection and records constraints without changing code generation.
Stage 2 uses the graph to answer finite-lowering queries: whether a closed-world generic method has a finite vtable family, which opaque-type instantiations are reachable, and whether an abstraction requires infinitely many specializations.
Stage 3 uses growing-cycle detection for diagnostics. A cycle such as T --Option--> T produces an error explaining the type-growth path before recursive expansion.
Stage 4 compares the flow-derived instance set with the existing mono-item collector under a debug flag. After validation, selected collection paths may use the solver directly.
Drawbacks
The analysis adds compiler complexity and must interact with MIR, trait selection, opaque types, associated types, codegen units, incremental compilation, drop glue, closures, generators, async lowering, vtables, and shims.
The analysis may over-approximate. Over-approximation is useful for feasibility checks and diagnostics, but direct code generation requires validation against the existing collector.
Rationale and alternatives
Keeping the current collector unchanged preserves the existing implementation but leaves rustc without a static finite-solution criterion for closed-world generic dynamic dispatch and related hidden-type lowering strategies.
Adding only recursion diagnostics would address one symptom, but not the more general problem of deciding whether advanced generic, opaque, higher-rank, or existential-like flows admit finite monomorphization.
Treating each feature independently would duplicate the same reasoning. Flow-directed monomorphization gives a shared criterion: finite solution means finite monomorphization; growing cycle means no finite monomorphization.
LLVM-level analysis is too late, since Rust generics have already been monomorphized before LLVM IR generation.
Prior art and related work
The main prior art is The Simple Essence of Monomorphization, which formalizes monomorphization as type-flow constraint solving, supports higher-rank and existential polymorphism, and characterizes non-monomorphizable programs as growing cycles in type flow.
Related Rust work includes impl Trait, TAIT, RPITIT, and the existing object-safety restrictions around generic methods. These features motivate a compiler-level finite-monomorphization analysis for hidden and higher-rank type flow.
Unresolved questions
The main unresolved question is graph identity: nodes may be keyed by DefId + GenericParamIndex, InstanceDef + GenericArgIndex, MonoItem + GenericArgIndex, or another representation.
Opaque-type representation also needs design work: possible keys include opaque DefId, defining use, revealed hidden type, or opaque identity plus captured arguments. Related questions include when hidden types should be revealed to the solver, how RPITIT appears before and after normalization, and how associated type projections are represented.
The implementation must also define how const generics, drop glue, closures, async futures, generators, and vtable shims appear in the graph; whether growing cycles are rejected before existing recursion limits; and whether upstream crates can expose compact type-flow metadata.
Future work
The primary follow-up is a design for closed-world generic methods behind dynamic dispatch. For trait Encode { fn encode<T>(&self, value: T); }, a closed-world compiler mode could lower the method into encode_i32, encode_String, and encode_Vec_u8 when flow analysis proves that these are the complete required instances.
A second direction is tooling for opaque-type growth, especially in programs using deeply nested iterator combinators, async fn, TAIT, and RPITIT.