Drop Glue Gets Four Times the Budget: rustc's Monomorphisation Recursion Hack

TL;DR: rustc’s monomorphiser has a recursion limit to catch fn f<T>() { f::<Vec<T>>() } style infinite expansion. But dropping a Vec<T> requires drop glue for T, which may require drop glue for a field of T, and for a self-referential type that recursion is legitimate. So rustc divides the effective depth by four for drop glue only, giving it four times the budget while leaving the real counter untouched.

Monomorphisation is the process of turning a generic function into specialised copies for each concrete set of type arguments. It is recursive by nature: instantiating f::<T> may instantiate g::<T> inside it, which may instantiate h::<T>, and so on. Some of that recursion is legitimate; some of it is an infinite loop.

The limit

// compiler/rustc_monomorphize/src/collector.rs:655-686

fn check_recursion_limit<'tcx>(
    tcx: TyCtxt<'tcx>,
    instance: Instance<'tcx>,
    span: Span,
    recursion_depths: &mut DefIdMap<usize>,
    recursion_limit: Limit,
) -> (DefId, usize) {
    let def_id = instance.def_id();
    let recursion_depth = recursion_depths.get(&def_id).cloned().unwrap_or(0);
    debug!(" => recursion depth={}", recursion_depth);

    let adjusted_recursion_depth = if tcx.is_lang_item(def_id, LangItem::DropGlue) {
        // HACK: `drop_glue` creates tight monomorphization loops. Give
        // it more margin.
        recursion_depth / 4
    } else {
        recursion_depth
    };

    // Code that needs to instantiate the same function recursively
    // more than the recursion limit is assumed to be causing an
    // infinite expansion.
    if !recursion_limit.value_within_limit(adjusted_recursion_depth) {
        let def_span = tcx.def_span(def_id);
        let def_path_str = tcx.def_path_str(def_id);
        tcx.dcx().emit_fatal(RecursionLimit { span, instance, def_span, def_path_str });
    }

    recursion_depths.insert(def_id, recursion_depth + 1);

    (def_id, recursion_depth)
}

Three lines do all the work:

1. The depth is tracked per DefId, in a DefIdMap<usize> — not per full instance. So f::<u8> calling f::<u32> counts as depth 2 for f, but f::<u8> calling f::<u8> is also depth 2. The counter is about “how deep are we in this function”, not “how many distinct instances exist”.

2. For drop glue, the depth used for the comparison is divided by four. The stored counter is still incremented by one — so the limit fires at 4× the nominal depth for drop glue, and 1× for everything else.

3. The comment says HACK, and it is honest about being a hack.

Why drop glue needs it

Consider:

struct Node {
    next: Option<Box<Node>>,
    data: String,
}

To drop a Node, rustc needs drop glue for Node. The glue drops next: Option<Box<Node>>, which needs drop glue for Box<Node>, which needs drop glue for Node… The recursion is legitimate and finite, but it is one level deep per type in the cycle.

Similarly, dropping a Vec<Vec<Vec<u8>>> recurses three levels; dropping a HashMap<K, V> recurses into V.

The naive fix — raise the global recursion limit — has two bad consequences:

• genuine infinite monomorphisation (fn f<T>() { f::<Vec<T>>() }) takes 4× longer to detect, and builds a much larger intermediate state before erroring;
• the error message for the genuine case is delayed by seconds.

The other naive fix — count only distinct DefIds — breaks on a chain of distinct functions: f1 calls f2 calls f3 calls … never repeats a DefId, so a distinct-counting limit never trips, and you get an out-of-memory instead of a nice error.

The per-DefId depth map plus a per-kind scale factor gives you both properties: infinite recursion through one function trips quickly, and legitimate recursion through the type structure gets room.

The same hack appears elsewhere in rustc

This is a recurring pattern: give a specific, known-benign recursion a better deal than the general case.

In the MIR inliner, the call-graph walker uses an eighth of the trait solver’s recursion limit, so the cheap analysis gives up first:

// compiler/rustc_mir_transform/src/inline/cycle.rs:161-168
let recursion_limit = tcx.recursion_limit() / 8;

In the trait solver, the recursion budget is divided by four after an overflow:

// compiler/rustc_next_trait_solver/src/solve/search_graph.rs:43
const DIVIDE_AVAILABLE_DEPTH_ON_OVERFLOW: usize = 4;

Three different places, three different constants, one idea: a limit that is uniform across unrelated situations is always wrong for at least one of them.

Demand-driven collection

The other interesting thing about the monomorphiser is how it finds work. It is not a scan over all items; it is a demand-driven walk:

// compiler/rustc_monomorphize/src/collector.rs:355-374

fn collect_items_root<'tcx>(
    tcx: TyCtxt<'tcx>,
    starting_item: Spanned<MonoItem<'tcx>>,
    state: &SharedState<'tcx>,
    recursion_limit: Limit,
) {
    if !state.visited.lock().insert(starting_item.node) {
        // We've been here already, no need to search again.
        return;
    }
    let mut recursion_depths = DefIdMap::default();
    collect_items_rec(
        tcx,
        starting_item,
        state,
        &mut recursion_depths,
        recursion_limit,
        CollectionMode::UsedItems,
    );
}

The visited set is the worklist: an item that has been visited is not scanned again. Because visited is shared and locked, roots can be collected in parallel.

And because parallel traversal produces a nondeterministic order, the final list is sorted with a stable hashing context:

// compiler/rustc_monomorphize/src/collector.rs:1915-1959

// The set of MonoItems was created in an inherently indeterministic order because
// of parallelism. We sort it here to ensure that the output is deterministic.
let mono_items = tcx.with_stable_hashing_context(move |mut hcx| {
    state.visited.into_inner().into_sorted(&mut hcx, true)
});

That matters more than it looks: a nondeterministic monomorphisation order means a nondeterministic set of CGU contents, which means different object files, which breaks reproducible builds and makes incremental caches miss.

Used vs. mentioned

There is also a distinction between items that are used and items merely mentioned:

// In `mentioned_items` we collect items that were mentioned in this MIR but possibly do not
// need to be monomorphized. This is done to ensure that optimizing away function calls does not
// hide const-eval errors that those calls would otherwise have triggered.

If a const-evaluating call is optimized away, a const_eval_select error inside it would vanish — so the item is still “mentioned” and its constant is still evaluated. That is a nice example of a compiler choosing to do more work to preserve error reporting.

Where it lives

• compiler/rustc_monomorphize/src/collector.rs — check_recursion_limit, collect_items_root, the used/mentioned split, the stable sort.
• compiler/rustc_mir_transform/src/inline/cycle.rs — the sibling /8 hack.
• compiler/rustc_next_trait_solver/src/solve/search_graph.rs — the sibling /4 hack.

Takeaway

Recursion limits are a blunt instrument, and the usual way to use them is to pick one number and hope. rustc instead keeps a per-site counter and scales the comparison for the one case that is known to be legitimately deep — drop glue — which turns a false positive (a compile error on valid code) into a non-event, without making the true positive any slower.