Inconsistent recursive fn call elimination

I tried this code:

#[inline(never)]
#[no_mangle]
const fn deep(n: usize) {
    match n {
        0 => (),
        _ => deep(n - 1),
    }
}

#[inline(always)]
const fn inf() -> ! {
    inf()
}

fn main() {
    deep(usize::MAX);
    println!("✅");
    inf();
}

I expected to see this happen: prints "✅" fast and successfully, then hangs in an infinite loop.

Instead, this happened: prints "✅" fast and panics with stderr:

   Compiling playground v0.0.1 (/playground)
    Finished `release` profile [optimized] target(s) in 0.38s
     Running `target/release/playground`

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

It seems commenting-out the attributes is no-op here.

Meta

https://play.rust-lang.org/?version=nightly&mode=release&edition=2021&gist=ed0941cd328e49d8737fdff01cd4a4aa

rustc --version --verbose:

1.80.0-nightly

(2024-05-28 da159eb331b27df52818)

Backtrace

<no diff>

Apologies in advance, if this issue is a dupe. I tried my best to find similar ones

This seems to be a duplicate of #102952 and many others like that one.

Weirdly enough, I tried this with #112788

#![feature(explicit_tail_calls)]
const fn inf() -> ! {
    become inf()
}

fn main() {
    inf();
}

It still overflows the stack! Even though the (unofficial) docs claim it must not.

I've been reading about the RFC, and it seems the syntax is the only thing that got implemented

interesting.

The llvm ir correctly contains

; playground::inf
; Function Attrs: nofree noreturn nosync nounwind nonlazybind memory(none) uwtable
define internal fastcc void @_ZN10playground3inf17hbbe49911b1985149E() unnamed_addr #3 {
start:
; call playground::inf
  tail call fastcc void @_ZN10playground3inf17hbbe49911b1985149E() #7
  unreachable
}

weird.

In my view, the code behavior initially mentioned in the issue is reasonable. I want to know why you expect it won't overflow the stack, inline(always) doesn't guarantee that inline will definitely occur.

The behavior in #125698 (comment) is definitively wrong. It uses become which should force a tail call, yet doesn't get tail called.

The tail call feature (#112788) is still in progress, e.g. #113128 has not been merged yet.

why you expect it won't overflow the stack

What I actually find surprising is that the compiler was eager to obliterate deep(usize::MAX) as if it was never there, but inf() didn't get ~~the same~~ similar treatment.

inline(always) doesn't guarantee that inline will definitely occur.

I know, I just wanted to "add emphasis" (I'm unsure if this is the correct terminology?)

The tail call feature (#112788) is still in progress, e.g. #113128 has not been merged yet.

Also note that #113128 by itself won't implement the feature correctly either, since it does not include llvm lowering.

why you expect it won't overflow the stack

What I actually find surprising is that the compiler was eager to obliterate deep(usize::MAX) as if it was never there, but inf() didn't get ~~the same~~ similar treatment.

Although both will result in a stack overflow at runtime, deep is a non-infinite recursive function without side effects, which the compiler can completely eliminate.

inline(always) doesn't guarantee that inline will definitely occur.

I know, I just wanted to "add emphasis" (I'm unsure if this is the correct terminology?)

I think maybe your meaning is similar. inline(always) means to inline whenever possible. inline should adjust the threshold for the inlining cost.

deep is a non-infinite recursive function without side effects

Correct! It makes sense. But (I may be getting into philosophical territory here) an OOM panic could be considered a side-effect, at least from the POV of a system (doesn't apply to no_std lib crates).

From the POV of a Rust program, OOM panics can't exist (in the same way ! is a "never type") so Rust as a lang is allowed to "ignore" them. But rustc should know that a call-stack cannot have the same size as the entire address-space of any target-triple (except Harvard machines), otherwise the program itself cannot fit in memory, so an OOM panic should happen anyways.

inline should adjust the threshold for the inlining cost.

Thanks for explaining! I just had some problems communicating my thoughts. My intention was to add "emphasis" both for humans and rustc, if that makes sense 😅

From the POV of a Rust program, OOM panics can't exist (in the same way ! is a "never type") so Rust as a lang is allowed to "ignore" them.

That's not really true at all. We have a defined set of behaviors in response to out-of-memory errors. The language has semantics for allocations, and it has a semantic for failing to allocate (some of the APIs represent this as returning nullptr, some of them as Result). You are referring to the behavior of very specific datatypes which effectively .unwrap() those Results. No one says "unwrap() can't exist". Instead, things that don't exist in Rust include the set of, e.g.

dereferenced null pointers
individual allocations larger than isize::MAX bytes
two active &mut T to the same T

some of them as Result

Indeed, I've just read about try_reserve, and this crate which has try_push (I wish that was in std)

No one says "unwrap() can't exist"

I should've said something along the lines of "unreachable code", since a guaranteed panic is equivalent to FnOnce() -> !. Thanks for the correction 👍

  tail call fastcc void @_ZN10playground3inf17hbbe49911b1985149E() #7

tail means it may or may not become a tail call; to require LLVM to generate a tail call, you need to use musttail call ... instead

Weirdly enough, I tried this with #112788
#![feature(explicit_tail_calls)]
const fn inf() -> ! {
    become inf()
}

fn main() {
    inf();
}
It still overflows the stack! Even though the (unofficial) docs claim it must not.

I've been reading about the RFC, and it seems the syntax is the only thing that got implemented

This example now no longer overflows. We have a test for the bounded variant here, I'll make a PR to check the codegen for the infinite loop, it also no longer grows the stack: https://godbolt.org/z/7eKbnePx5

Rollup merge of rust-lang#148907 - folkertdev:tail-call-infinite-recu…

Unrolled build for #148907

Navigation Menu

Repository navigation

Inconsistent recursive fn call elimination #125698

Meta

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Inconsistent recursive fn call elimination #125698

Description

Meta

Activity

workingjubilee commented on May 29, 2024

Rudxain commented on May 29, 2024

workingjubilee commented on May 29, 2024

bjorn3 commented on May 29, 2024

workingjubilee commented on May 29, 2024

dianqk commented on May 29, 2024

bjorn3 commented on May 29, 2024

the8472 commented on May 29, 2024

Rudxain commented on May 29, 2024

WaffleLapkin commented on May 29, 2024

dianqk commented on May 31, 2024

Rudxain commented on May 31, 2024

workingjubilee commented on Jun 1, 2024

Rudxain commented on Jun 1, 2024

programmerjake commented on Jun 13, 2024

folkertdev commented on Nov 13, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions