rust-lang / rust-lang/rust

How should try_as_dyn handle inductive cycles?

Open
#151,440 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-coinduction A-trait-system C-bug F-try_as_dyn T-compiler T-libs T-types
Dominant language
Rust
Stars
119k
Forks
16.1k
PR merge metrics
PR metrics pending

Description

An inductive cycle is when proving whether a type implements a trait or not relies on whether that same type implements that same trait.

Currently, under normal circumstances, trying to rely on an inductive cycle results in an "overflow evaluating the requirement" error, which is the same behavior as exceeding the recursion limit via other means.

Example code and error from a normal inductive cycle
struct Thing<T>(T);
trait Trait {}
impl<T> Trait for Thing<T> where Thing<T>: Trait {}

fn main() {
    require_trait::<Thing<i32>>();
}

fn require_trait<T: Trait>() {}
error[E0275]: overflow evaluating the requirement `Thing<i32>: Trait`
 --> src/main.rs:6:5
  |
6 |     require_trait::<Thing<i32>>();
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
note: required by a bound in `require_trait`
 --> src/main.rs:9:21
  |
9 | fn require_trait<T: Trait>() {}
  |                     ^^^^^ required by this bound in `require_trait`

For more information about this error, try `rustc --explain E0275`.

Without inductive cycles, try_as_dyn can cause post-mono errors by exceeding the recursion limit via non-inductive-cycle means, if the relevant function gets to codegen. This is intended.

Example code and error from try_as_dyn exceeding the recursion limit
#![feature(try_as_dyn)]
#![recursion_limit = "8"]

use std::any::try_as_dyn;

struct Wrap<T>(T);
struct Indirect<T>(T);

trait Trait {}

impl<T> Trait for Wrap<T> where Indirect<Indirect<T>>: Trait {}
impl<T> Trait for Indirect<T> where T: Trait {}
impl Trait for i32 {}

// Uncommenting the below line makes the code compile
// #[inline]
pub fn weird() {
    let x = Wrap(Wrap(Wrap(Wrap(1i32))));
    let b = try_as_dyn::<Wrap<Wrap<Wrap<Wrap<i32>>>>, dyn Trait>(&x).is_some();
    println!("{b}");
}
error[E0275]: overflow evaluating the requirement `Indirect<Indirect<Wrap<i32>>>: Trait`
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "16"]` attribute to your crate (`playground`)
note: required for `Wrap<Wrap<i32>>` to implement `Trait`
  --> src/lib.rs:11:9
   |
11 | impl<T> Trait for Wrap<T> where Indirect<Indirect<T>>: Trait {}
   |         ^^^^^     ^^^^^^^                              ----- unsatisfied trait bound introduced here
   = note: 6 redundant requirements hidden
   = note: required for `Wrap<Wrap<Wrap<Wrap<i32>>>>` to implement `Trait`

For more information about this error, try `rustc --explain E0275`.
Another example code and error from try_as_dyn exceeding the recursion limit
#![feature(try_as_dyn)]
use std::any::try_as_dyn;

trait Marker {
    type Assoc;
}
impl<T> Marker for T {
    type Assoc = Option<T>;
}

struct Thing<T>(T);
trait Trait {}
impl<T> Trait for Thing<T> where Thing<<T as Marker>::Assoc>: Trait {}

fn main() {
    try_as_dyn::<_, dyn Trait>(&Thing(0i32)).unwrap();
}
error[E0275]: overflow evaluating the requirement `Thing<Option<Option<Option<Option<Option<Option<...>>>>>>>: Trait`
  --> src/main.rs:13:63
   |
13 | impl<T> Trait for Thing<T> where Thing<<T as Marker>::Assoc>: Trait {}
   |                                                               ^^^^^
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`playground`)
note: required for `Thing<Option<Option<Option<Option<Option<Option<Option<...>>>>>>>>` to implement `Trait`
  --> src/main.rs:13:9
   |
13 | impl<T> Trait for Thing<T> where Thing<<T as Marker>::Assoc>: Trait {}
   |         ^^^^^     ^^^^^^^^                                    ----- unsatisfied trait bound introduced here
   = note: 125 redundant requirements hidden
   = note: required for `Thing<Option<T>>` to implement `Trait`
   = note: the full name for the type has been written to '/playground/target/debug/deps/playground-1025e5d410fc3651.long-type-10312360702417460169.txt'
   = note: consider using `--verbose` to print the full type name to the console

For more information about this error, try `rustc --explain E0275`.

However, try_as_dyn, for some reason, seems to treat inductive cycles as "the type doesn't implement the trait".

Example code and error with try_as_dyn and an inductive cycle
#![feature(try_as_dyn)]
use std::any::try_as_dyn;

struct Thing<T>(T);
trait Trait {}
impl<T> Trait for Thing<T> where Thing<T>: Trait {}

fn main() {
    try_as_dyn::<_, dyn Trait>(&Thing(0i32)).unwrap();
}
thread 'main' (12) panicked at src/main.rs:9:46:
called `Option::unwrap()` on a `None` value
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

That is, under normal circumstances, inductive cycles are treated like the recursion limit being exceeded normally. However, try_as_dyn treats a coinductive cycle as if the type just not implementing the trait. This seems inconsistent.

Furthermore, inductive cycles can sometimes be only discovered after monomorphization. (See #150508.) As a result, it is possible to have a T: Trait generic type that try_as_dyn reports as not implementing Trait. This seems undesirable.

Example code and error with post-mono inductive cycle interacting with try_as_dyn
#![feature(try_as_dyn)]

use std::any::try_as_dyn;
trait Apply {
    type Output<T: Trait>: Trait;
}
struct Identity;
impl Apply for Identity {
    type Output<T: Trait> = T;
}

struct Thing<A: Apply>(A);

trait Trait {}

impl<A: Apply> Trait for Thing<A> where <A as Apply>::Output<Self>: Trait {}

/*
effectively:
impl Trait for Thing<Identity> where Thing<Identity>: Trait {}
*/

fn foo<T: Trait + 'static>(x: T) {
    // This panics even though we have T: Trait
    let _ = try_as_dyn::<_, dyn Trait>(&x).unwrap();
}

fn bar<A: Apply + 'static>(a: A) {
    foo(Thing(a));
}

fn main() {
    bar(Identity);
}
thread 'main' (41) panicked at src/main.rs:25:44:
called `Option::unwrap()` on a `None` value
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Note that specialization is also currently broken in the presence of inductive cycles. See #147507.

Tracking issue for try_as_dyn: #144361

cc @oli-obk @lcnr

Meta

Reproducible on the playground with version 1.95.0-nightly (2026-01-19 d940e56841ddcc05671e)

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 supplied try_as_dyn examples, starting with the inductive-cycle case and comparing it with ordinary overflow behavior. Review tracking issue #144361 and related issues #150508 and #147507 to determine the intended semantics; done means an agreed treatment of inductive cycles, including post-monomorphization cases, with regression coverage.

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.