rust-lang / rust-lang/rust

Type resolution on complex type seems to diverge and then crash the compiler

Open
#122,239 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

C-bug I-crash T-compiler
Dominant language
Rust
Stars
119k
Forks
16.1k
PR metrics pending

Description

I tried this code:

struct Succ<T> {
    inner: std::marker::PhantomData<T>,
}

struct Zero;
type One = Succ<Zero>;
type Two = Succ<One>;
type Three = Succ<Two>;

trait Add<T> {
    type Output;
}

impl<U> Add<Zero> for U {
    type Output = U;
}

impl<T, U> Add<Succ<T>> for U
where
    U: Add<T>,
{
    type Output = Succ<<U as Add<T>>::Output>;
}

trait Mult<T> {
    type Output;
}
impl Mult<Zero> for Zero {
    type Output = Zero;
}
impl<U> Mult<Zero> for Succ<U> {
    type Output = Zero;
}

impl<T, U> Mult<Succ<T>> for U
where
    U: Mult<T> + Add<<U as Mult<T>>::Output>,
{
    // (t+1)*u = u*t + u
    type Output = <U as Add<<U as Mult<T>>::Output>>::Output;
}

trait Sub {
    type Output;
}

impl<T> Sub for Succ<T> {
    type Output = T;
}

trait Not {
    type Output;
}

impl Not for Zero {
    type Output = One;
}

impl Not for One {
    type Output = Zero;
}

trait IsEven {
    type Output;
}

impl IsEven for Zero {
    type Output = One;
}

impl<T> IsEven for Succ<T>
where
    T: IsEven,
    <T as IsEven>::Output: Not,
{
    // 1 - IsEven<T>
    type Output = <<T as IsEven>::Output as Not>::Output;
}

trait IsOdd {
    type Output;
}

impl<T> IsOdd for T
where
    T: IsEven,
    <T as IsEven>::Output: Not,
{
    type Output = <<T as IsEven>::Output as Not>::Output;
}

trait Half {
    type Output;
}

impl Half for Zero {
    type Output = Zero;
}

impl Half for One {
    type Output = Zero;
}

impl<T> Half for Succ<Succ<T>>
where
    T: Half,
{
    type Output = Succ<<T as Half>::Output>;
}

trait Syracuse {
    type Output;
}

impl<T> Syracuse for T
where
    T: Half,
    T: IsEven,
    <T as Half>::Output: Mult<<T as IsEven>::Output>,
    T: Mult<Three>,
    T: IsOdd,
    Succ<<T as Mult<Three>>::Output>: Mult<<T as IsOdd>::Output>,
    <Succ<<T as Mult<Succ<Succ<Succ<Zero>>>>>::Output> as Mult<<T as IsOdd>::Output>>::Output:
        Add<<<T as Half>::Output as Mult<<T as IsEven>::Output>>::Output>,
{
    // (3t+1)*isodd(t) + (t/2)*(1-isodd(t))
    type Output =
        <<Succ<<T as Mult<Three>>::Output> as Mult<<T as IsOdd>::Output>>::Output as Add<
            <<T as Half>::Output as Mult<<T as IsEven>::Output>>::Output,
        >>::Output;
}

fn main() {
    println!("{}", std::any::type_name::<<Three as Syracuse>::Output>())
}

It tries to implement the Syracuse sequence using Peano integers and the Rust type system (I know...).

I expected it to compile after maybe adjusting the recursion limit. Instead, I either get a compiler error of the type:

error[E0275]: overflow evaluating the requirement `Succ<_>: Mult<Succ<_>>`
    |
    = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`syracuse2`)
note: required for `Succ<_>` to implement `Mult<Succ<Succ<_>>>`
   --> src/syracuse2.rs:41:12
    |
41  | impl<T, U> Mult<Succ<T>> for U
    |            ^^^^^^^^^^^^^     ^
42  | where
43  |     U: Mult<T> + Add<<U as Mult<T>>::Output>,
    |                  --------------------------- unsatisfied trait bound introduced here
    = note: 126 redundant requirements hidden
    = note: required for `Succ<_>` to implement `Mult<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<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<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<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<_>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
note: required for `Self` to implement `Syracuse`
   --> src/syracuse2.rs:121:9
    |
121 | impl<T> Syracuse for T
    |         ^^^^^^^^     ^
...
130 |         Add<<<T as Half>::Output as Mult<<T as IsEven>::Output>>::Output>,
    |         ----------------------------------------------------------------- unsatisfied trait bound introduced here

For more information about this error, try `rustc --explain E0275`.
error: could not compile `syracuse` (bin "syracuse2") due to 1 previous error

Or, after increasing the recursion limit, after around 690, I get an ICE instead:

error: rustc interrupted by SIGSEGV, printing backtrace

/home/username/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-766f7798aafe0dd0.so(+0x2e7b2b3)[0x7b2822c7b2b3]
/lib/x86_64-linux-gnu/libc.so.6(+0x42520)[0x7b281fa42520]
/home/username/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-766f7798aafe0dd0.so(+0x422e6e7)[0x7b282402e6e7]

### cycle encountered after 3 frames with period 4
/home/username/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-766f7798aafe0dd0.so(+0x422e9ef)[0x7b282402e9ef]
/home/username/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-766f7798aafe0dd0.so(+0x422e9ef)[0x7b282402e9ef]
/home/username/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-766f7798aafe0dd0.so(+0x422e9ef)[0x7b282402e9ef]
/home/username/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-766f7798aafe0dd0.so(+0x422e9ef)[0x7b282402e9ef]
### recursed 63 times

/home/username/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-766f7798aafe0dd0.so(+0x422e9ef)[0x7b282402e9ef]

note: rustc unexpectedly overflowed its stack! this is a bug
note: maximum backtrace depth reached, frames may have been lost
note: we would appreciate a report at https://github.com/rust-lang/rust
error: could not compile `syracuse` (bin "syracuse2")

Caused by:
  process didn't exit successfully: `/home/username/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/rustc --crate-name syracuse2 --edition=2021 src/syracuse2.rs --error-format=json --json=diagnostic-rendered-ansi,artifacts,future-incompat --diagnostic-width=129 --crate-type bin --emit=dep-info,link -C embed-bitcode=no -C debuginfo=2 -C metadata=df84f5d7ccac5ffc -C extra-filename=-df84f5d7ccac5ffc --out-dir <REDACTED>/target/debug/deps -C incremental=<REDACTED>/target/debug/incremental -L dependency=<REDACTED>target/debug/deps` (signal: 11, SIGSEGV: invalid memory reference)

Strangely enough, when factoring out the two parts of the final addition, the compiler happily compiles my code:

struct Succ<T> {
    inner: std::marker::PhantomData<T>,
}

struct Zero;
type One = Succ<Zero>;
type Two = Succ<One>;
type Three = Succ<Two>;

trait Add<T> {
    type Output;
}

impl<U> Add<Zero> for U {
    type Output = U;
}

impl<T, U> Add<Succ<T>> for U
where
    U: Add<T>,
{
    type Output = Succ<<U as Add<T>>::Output>;
}

trait Mult<T> {
    type Output;
}
impl Mult<Zero> for Zero {
    type Output = Zero;
}
impl<U> Mult<Zero> for Succ<U> {
    type Output = Zero;
}

impl<T, U> Mult<Succ<T>> for U
where
    U: Mult<T> + Add<<U as Mult<T>>::Output>,
{
    // (t+1)*u = u*t + u
    type Output = <U as Add<<U as Mult<T>>::Output>>::Output;
}

trait Sub {
    type Output;
}

impl<T> Sub for Succ<T> {
    type Output = T;
}

trait Not {
    type Output;
}

impl Not for Zero {
    type Output = One;
}

impl Not for One {
    type Output = Zero;
}

trait IsEven {
    type Output;
}

impl IsEven for Zero {
    type Output = One;
}

impl<T> IsEven for Succ<T>
where
    T: IsEven,
    <T as IsEven>::Output: Not,
{
    // 1 - IsEven<T>
    type Output = <<T as IsEven>::Output as Not>::Output;
}

trait IsOdd {
    type Output;
}

impl<T> IsOdd for T
where
    T: IsEven,
    <T as IsEven>::Output: Not,
{
    type Output = <<T as IsEven>::Output as Not>::Output;
}

trait Half {
    type Output;
}

impl Half for Zero {
    type Output = Zero;
}

impl Half for One {
    type Output = Zero;
}

impl<T> Half for Succ<Succ<T>>
where
    T: Half,
{
    type Output = Succ<<T as Half>::Output>;
}

trait SyracuseEven {
    type Output;
}

impl<T> SyracuseEven for T
where
    T: Half,
    T: IsEven,
    <T as Half>::Output: Mult<<T as IsEven>::Output>,
{
    type Output = <<T as Half>::Output as Mult<<T as IsEven>::Output>>::Output;
}

trait SyracuseOdd {
    type Output;
}

impl<T> SyracuseOdd for T
where
    T: Mult<Three>,
    T: IsOdd,
    Succ<<T as Mult<Three>>::Output>: Mult<<T as IsOdd>::Output>,
{
    type Output = <Succ<<T as Mult<Three>>::Output> as Mult<<T as IsOdd>::Output>>::Output;
}

trait Syracuse: SyracuseEven + SyracuseOdd {
    type Output;
}

impl<T> Syracuse for T
where
    T: SyracuseEven + SyracuseOdd,
    <T as SyracuseEven>::Output: Add<<T as SyracuseOdd>::Output>,
{
    type Output = <<T as SyracuseEven>::Output as Add<<T as SyracuseOdd>::Output>>::Output;
}

fn main() {
    println!("{}", std::any::type_name::<<Three as Syracuse>::Output>()) // This compiles and gives the expected output, i.e. 10
}

I still get the same ICE when trying to compile with larger numbers and adjusting the recursion limit, though.

Meta

rustc --version --verbose:
Tested using

rustc 1.76.0 (07dca489a 2024-02-04)
binary: rustc
commit-hash: 07dca489ac2d933c78d3c5158e3f43beefeb02ce
commit-date: 2024-02-04
host: x86_64-unknown-linux-gnu
release: 1.76.0
LLVM version: 17.0.6

as well as

rustc 1.78.0-nightly (9c3ad802d 2024-03-07)
binary: rustc
commit-hash: 9c3ad802d9b9633d60d3a74668eb1be819212d34
commit-date: 2024-03-07
host: x86_64-unknown-linux-gnu
release: 1.78.0-nightly
LLVM version: 18.1.0

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

Reproduce the issue with the provided program in src/syracuse2.rs using the reported stable and nightly rustc versions, first at the default recursion limit and then with the increased limit. Compare the overflow diagnostic with the SIGSEGV and stack-overflow behavior; done means the compiler no longer crashes on this input and produces a controlled result.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.