rust-lang / rust-lang/rust

Exponential compile time increase with generic_const_exprs and recursive trait bounds

Open
#159,934 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

C-bug needs-triage
Dominant language
Rust
Stars
119k
Forks
16.1k
PR merge metrics
PR metrics pending

Description

Tried to use generic const expressions to create a function that guarantees to unroll a loop:

#![allow(incomplete_features)]
#![feature(generic_const_exprs, explicit_tail_calls)]
#![recursion_limit = "1024"]

pub struct IterationCount<const TOTAL: usize, const LEFT: usize>;

trait IsTrue {}

struct Assert<const VAL: bool>;

impl IsTrue for Assert<true> {}

pub trait Unrollable {
    fn do_iteration(fun: impl FnMut(usize));
}

impl<const TOTAL: usize> Unrollable for IterationCount<TOTAL, 0> {
    #[inline(always)]
    fn do_iteration(_fun: impl FnMut(usize)) {}
}

impl<const TOTAL: usize, const LEFT: usize> Unrollable for IterationCount<TOTAL, LEFT>
where
    Assert<{ LEFT > 0 }>: IsTrue,
    IterationCount<TOTAL, { LEFT - 1 }>: Unrollable,
{
    #[inline(always)]
    fn do_iteration(mut fun: impl FnMut(usize)) {
        fun(TOTAL - LEFT);
        become IterationCount::<TOTAL, { LEFT - 1 }>::do_iteration(fun);
    }
}

#[inline(always)]
pub fn unroll<const N: usize>(fun: impl FnMut(usize))
where
    IterationCount<N, N>: Unrollable,
{
    become IterationCount::<N, N>::do_iteration(fun);
}

#[inline(always)]
fn iteration(i: usize)
{
    println!("iter: {i}");
}

fn main() {
    unroll::<300>( iteration);
}

If I increase the number of iterations to 500, the compiler hangs.
I suspect the issue is the usage of recursive trait bounds.

rustc --version --verbose:

rustc 1.99.0-nightly (da86f4d07 2026-07-24)
binary: rustc
commit-hash: da86f4d0726be475afbbffe40cb2f65741c51ad3
commit-date: 2026-07-24
host: aarch64-apple-darwin
release: 1.99.0-nightly
LLVM version: 22.1.8

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the provided generic_const_exprs and recursive trait-bound reproducer, compiling it with the nightly rustc version shown by rustc --version --verbose. Compare compilation behavior at 300 and 500 iterations, then investigate the recursive Unrollable bounds and const expressions. Done means the compiler no longer exhibits exponential compile-time growth or hangs on the reported case.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.