Compile-time resource exhaustion from type complexity via recursive generic traits

[caomingpei]

I tried this code:

use std::marker::PhantomData;

pub trait Seq {}

pub struct Empty;
impl Seq for Empty {}

// `Branch` to connect Branch<A,B>
pub struct Branch<L: Seq, R: Seq> {
    _p: PhantomData<(L, R)>,
}
impl<L: Seq, R: Seq> Seq for Branch<L, R> {}

// Define L-system rewrite rules
// `A` and `B` are the basic elements of the sequence.
pub struct A;
pub struct B;
impl Seq for A {}
impl Seq for B {}

// `Rewrite` trait defines the rewriting rules
pub trait Rewrite {
    type Result: Seq;
}

// Rule 1: A -> Branch(A, B)
impl Rewrite for A {
    type Result = Branch<A, B>;
}

// Rule 2: B -> A
impl Rewrite for B {
    type Result = A;
}

// Recursively rewrite the entire sequence tree. Similar to L-system concepts:
// N=0: A
// N=1: Branch<A, B>
// N=2: Branch<Rewrite(A), Rewrite(B)> -> Branch<Branch<A, B>, A>
// N=3: Branch<Rewrite(Branch<A, B>), Rewrite(A)> -> Branch<Branch<Branch<A, B>, A>, Branch<A, B>>
// Fibonacci-like growth of the sequence tree.
impl Rewrite for Empty {
    type Result = Empty;
}
impl<L: Seq, R: Seq> Rewrite for Branch<L, R>
where
    L: Rewrite,
    R: Rewrite,
{
    type Result = Branch<<L as Rewrite>::Result, <R as Rewrite>::Result>;
}

// Define traits for iteration and forced evaluation
// `Nat` and `Succ`/`Zero` are used for type-level counting.
// Represents numbers at the type level.
pub trait Nat {}
pub struct Zero;
impl Nat for Zero {}
pub struct Succ<N: Nat>(PhantomData<N>);
impl<N: Nat> Nat for Succ<N> {}

// `ApplyRewrite` trait applies the specified rewriting rules N times.
pub trait ApplyRewrite<N: Nat> {
    type Result: Seq;
}

// Base case: 0 iterations, the result is the type itself.
impl<S: Seq> ApplyRewrite<Zero> for S {
    type Result = S;
}

// Recursive step: N+1 iterations = apply N iterations, then rewrite the result once.
impl<S: Seq, P: Nat> ApplyRewrite<Succ<P>> for S
where
    S: ApplyRewrite<P>,
    <S as ApplyRewrite<P>>::Result: Rewrite,
{
    type Result = <<S as ApplyRewrite<P>>::Result as Rewrite>::Result;
}

// Define a more complex hash calculation trait
/// `SeqHash` trait is used to compute the hash value of a sequence at compile time.
pub trait SeqHash {
    const HASH: u64;
}

//  Define the hash values for the basic elements and branches. (random large primes)
impl SeqHash for Empty {
    const HASH: u64 = 0x9e3779b97f4a7c15;
}
impl SeqHash for A {
    const HASH: u64 = 0x6a09e667f3bcc908;
}
impl SeqHash for B {
    const HASH: u64 = 0xbb67ae8584caa73b;
}

impl<L: Seq, R: Seq> SeqHash for Branch<L, R>
where
    L: SeqHash,
    R: SeqHash,
{
    // Introduce a complex hash calculation method, using various bitwise operations and constants
    const HASH: u64 = ((L::HASH.wrapping_mul(0x94d049bb133111eb).rotate_left(19))
        ^ (R::HASH.wrapping_mul(0xbf58476d1ce4e5b9).rotate_right(23))
            .wrapping_add(0xc4ceb9fe1a85ec53))
    .wrapping_mul(0x9e3779b97f4a7c15) // A large prime constant, Empty
    .rotate_left(37)
    .wrapping_add(L::HASH ^ R::HASH);
}

// main function to trigger the compile-time evaluation.
fn main() {
    // Define initial state.
    type InitialState = A;

    // Note: the following is harmful. Set iteration count to N=40.
    // Complex successor tree
    // Result: Compilation bomb! Compilation leads to OOM, takes a very long time, and causes a Denial of Service.
    type N40 = Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Zero>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;

    // Generate final result type.
    type FinalState = <InitialState as ApplyRewrite<N40>>::Result;

    // Force the compiler to evaluate and traverse the type.
    const FINAL_HASH: u64 = <FinalState as SeqHash>::HASH;

    // Print the result to ensure it won't be optimized away.
    println!(
        "Compilation succeeded! The final complex hash calculated at compile-time is: {}",
        FINAL_HASH
    );
}

I expected to see this happen: compile finished

Instead, this happened: compile stuck

Meta

rustc --version --verbose:

rustc 1.87.0 (17067e9ac 2025-05-09)
binary: rustc
commit-hash: 17067e9ac6d7ecb70e50f92c1944e545188d2359
commit-date: 2025-05-09
host: aarch64-apple-darwin
release: 1.87.0
LLVM version: 20.1.1

Backtrace

<backtrace>

[fmease]

(not fixed by the next-gen solver at the time of writing)

[fmease]

Side note: You probably meant well, but there's no need to explain why the compiler never terminating is a bad thing, even less so in 333 words and with a huge image.

Every maintainer of and contributor to this repository already knows that. Moreover it takes a lot of vertical space everybody needs to skip to reach the comment section. Therefore I've now hidden that explainer.

Thanks for your understanding and for reporting this issue!

[cyrgani]

somewhat smaller:

struct Branch<L, R>(L, R);

struct A;

trait Rewrite {
    type Result;
}

impl Rewrite for A {
    type Result = Branch<A, A>;
}

impl<L, R> Rewrite for Branch<L, R>
where
    L: Rewrite,
{
    type Result = Branch<<L as Rewrite>::Result, <L as Rewrite>::Result>;
}

struct Zero;
struct Succ<N>(N);

trait ApplyRewrite<N> {
    type Result;
}

impl<S> ApplyRewrite<Zero> for S {
    type Result = S;
}

impl<S, P> ApplyRewrite<Succ<P>> for S
where
    S: ApplyRewrite<P>,
    <S as ApplyRewrite<P>>::Result: Rewrite,
{
    type Result = <<S as ApplyRewrite<P>>::Result as Rewrite>::Result;
}

trait SeqHash {}
impl<L, R> SeqHash for Branch<L, R> {}

type N40 = Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Zero>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;

type FinalState = <A as ApplyRewrite<N40>>::Result;

fn main() {
    f::<FinalState>();
}

fn f<T: SeqHash>() {}

[workingjubilee]

@caomingpei Specifically, to augment what @fmease said: We do not consider running the Rust compiler exposed to the public network and without enforcing timeouts to be a supported use-case. It is trivially possible for the use of a procedural macro or const evaluation to occupy infinite time, though we do apply lints on such. So we do not accept "DoS vulnerability" reports, as this cannot be a security issue. We try to avoid unnecessary hangs as a matter of quality.

If you believe you have discovered a genuine security vulnerability, then please follow coordinated disclosure practices. Otherwise, please avoid using security vulnerability terms for non-security-issue reports.

[pietroalbini]

This was indeed reported to security@rust-lang.org, but given it's not a security vulnerability we asked them to open a public issue 🙂

[hkBst]

Looking at the code from @cyrgani (#142840 (comment)):

• there is a type-level integer N40 presumably with value 40 (I didn't count),
• the FinalState type for Zero is just A, for Succ<Zero> it's Branch<A, A>, for Succ<Succ<Zero>> it's Branch<Branch<A, A>, Branch<A, A>> and we can see the binary tree of height 40 appear. Since 2**10 is about a thousand, this tree has about a million million (EU billion, US trillion) leaves.

So if each leaf's type is stored in a byte, storing all leaves' types would take 1TB of memory.