Typesystem soundness hole involving cyclically-defined associated type in trait, and normalization in trait bounds

@rustbot

This isn't quite trivial, but well… it works.

a “transmute” in safe Rust:

fn main() {
    let s: String = transmute(vec![65_u8, 66, 67]);
    println!("{s}"); // ABC
}

fn transmute<L, R>(x: L) -> R {
    transmute_inner_1::<L, R, RewriteReflRight<FakeRefl<L, R>>>(x)
}

fn transmute_inner_1<L, R, P: TyEq<LHS = L, RHS = R>>(x: L) -> R {
    transmute_inner_2::<<P::ProofIsProofValue as TyEq>::ProofDef, L, R, P::ProofValue, P>(x)
}

fn transmute_inner_2<Rw, L, R, Actual, P: TyEq<LHS = L, RHS = R, ProofValue = Actual>>(x: L) -> R
where
    <Rw as TypeIs<P::ProofValue>>::Is: TyEq<LHS = L, RHS = R>,
{
    transmute_inner_3::<L, R, Actual>(x)
}

fn transmute_inner_3<L, R, P: TyEq<LHS = L, RHS = R>>(x: L) -> R {
    transmute_inner_4::<R, P::ProofDef>(x)
}

fn transmute_inner_4<R, Rw>(x: <Rw as TypeIs<R>>::Is) -> R {
    x
}

trait TypeIs<T> {
    type Is;
}
impl<_Self, T> TypeIs<T> for _Self {
    type Is = T;
}

trait TyEq: TyEqImpl {
    type ProofDef: TypeIs<Self::RHS, Is = Self::LHS>;
}

trait TyEqImpl {
    type LHS;
    type RHS;

    type Proof<_Dummy>: TyEq<LHS = Self::LHS, RHS = Self::RHS>;

    type ProofValue;
    type ProofIsProofValue: TyEq<LHS = Self::Proof<()>, RHS = Self::ProofValue>;
}

trait DeriveEqFromImpl {}
impl<P: TyEqImpl + DeriveEqFromImpl> TyEq for P {
    type ProofDef = <P::Proof<()> as TyEq>::ProofDef;
}

struct Refl<T>(T);
impl<T> TyEqImpl for Refl<T> {
    type LHS = T;
    type RHS = T;

    type Proof<_Dummy> = Refl<T>;

    type ProofValue = Refl<T>;
    type ProofIsProofValue = Refl<Refl<T>>;
}
impl<T> TyEq for Refl<T> {
    type ProofDef = ();
}

struct FakeRefl<L, R>(L, R);
impl<L, R> DeriveEqFromImpl for FakeRefl<L, R> {}
impl<L, R> TyEqImpl for FakeRefl<L, R> {
    type LHS = L;
    type RHS = R;

    type Proof<_Dummy> = FakeRefl<L, R>;

    type ProofValue = FakeRefl<L, R>;
    type ProofIsProofValue = Refl<FakeRefl<L, R>>;
}

struct RewriteReflRight<P>(P);
impl<P> DeriveEqFromImpl for RewriteReflRight<P> {}
impl<P, L, R> TyEqImpl for RewriteReflRight<P>
where
    P: TyEq<LHS = L, RHS = R>,
{
    type LHS = L;
    type RHS = R;

    type Proof<_Dummy: RewriteReflRightHelper> = _Dummy::RewriteRight<Refl<L>, R, P::ProofDef>;

    type ProofValue = Refl<L>;
    type ProofIsProofValue = Refl<Refl<L>>;
}

trait RewriteReflRightHelper {
    type RewriteRight<P, R, Rw>: TyEq<LHS = P::LHS, RHS = R>
    where
        P: TyEq<RHS = <Rw as TypeIs<R>>::Is>;
}

impl<_Dummy> RewriteReflRightHelper for _Dummy {
    type RewriteRight<P, R, Rw>
        = P
    where
        P: TyEq<RHS = <Rw as TypeIs<R>>::Is>;
}

(playground)

Besides this unsoundness, there are also many ICEs. This isn't surprising, since we're not really transmuting, but rather sort-of … convincing the type system that the 2 types were never different in the first place.

fn main() {
    let s: u8 = transmute(());
    println!("{s:?}");
}

Or interesting LLVM-errors

fn main() {
    let s: &() = transmute("hi");
    println!("{s:?}");
}

   Compiling playground v0.0.1 (/playground)
Invalid bitcast
  %7 = bitcast { ptr, i64 } %6 to ptr, !dbg !425
in function _ZN10playground17transmute_inner_317h363424402e6a7153E
rustc-LLVM ERROR: Broken function found, compilation aborted!
error: could not compile `playground` (bin "playground")

Oh… that one on nightly has… the compiler itself execute a SIGILL? (Is that actual UB in the compiler!? Or UB in LLVM? Or can SIGILL be part of a deliberate crash condition?)

From a background of “this works a bit like Coq”, the relevant parts that make this work is how:

FakeRefl<L, R> is a “proof” that L and R are the same types, which doesn't terminate (i.e. it is cyclically defined in terms of itself)
- unlike true proof assistants, Rust's trait system does allow some stuff to be defined in a somewhat cyclical manner, especially pre-monomorphization
overflow during monomorphization is avoided anyways by:
- introducing the Rewrite… step which rewrites Refl<L> (a proof of TyEq<LHS = L, RHS = R>) using this FakeRefl proof
- at the same time also tracking that the proof term itself doesn't actually change with the rewrite
- using this tracked meta-information in order to eliminate the usage of FakeRefl before its (indirectly and cyclically defined) ProofDef type ever ends up being instantiated

Of course, this is just my intuitive description from a user perspective :-)

I have no idea which part of this code to blame exactly. Perhaps someone else with better knowledge of the theory behind Rust's typesystem and trait system could have a better clue here.

~~I'm not quite sure if~~ this can perhaps be "simplified" to remove the need for GATs

Update: It can be "simplified" to remove the need for GATs. (playground)

Update2: It's even possible to rework this into working since Rust 1.1

(this section has become somewhat outdated due to this update, click to expand anyway)

I'm not quite sure if this can perhaps be "simplified" to remove the need for GATs; however, I wasn't able to the Rewrite… stuff to work without this trick

type Proof<_Dummy: RewriteReflRightHelper> = _Dummy::RewriteRight<Refl<L>, R, P::ProofDef>;

where the (vacuous) _Dummy: RewriteReflRightHelper restriction prevents the compiler from already knowing the concrete RewriteReflRightHelper impl. (If you worry about the syntactical mismatch of

type Proof<_Dummy: RewriteReflRightHelper>

here vs

type Proof<_Dummy>: TyEq<LHS = Self::LHS, RHS = Self::RHS>;

without bounds on _Dummy in the trait definition: that's actually avoidable (<- see this playground on how the bound can be repeated everywhere and the impl RewriteReflRightHelper for … can even be for a concrete type only).

So for now, I would conjecture that this soundness hole does require GATs.

Edit: I completely forgot about the (generous) usage of GATs inside of RewriteReflRightHelper ~ so, yes, GATs seem fairly integral to this.

Edit2: Nevermind, those can all be eliminated leaving only a single GAT.

(end of somewhat outdated section)

This is not a regression. It also isn't influenced by -Znext-solver.

This is a relatively clean typesystem hole, on stable Rust, without many of the other known-problematic features such as HRTBs, lifetimes, variance, trait objects, or implicitly defined trait impls for functions/closures/etc…

@rustbot label I-unsound, I-ICE, I-crash, T-types, A-type-system, A-trait-system, A-associated-items

related issues

Circularly defined GAT is somehow allowed and ICEs Miri #149898

@nikic

Oh… that one on nightly has… the compiler itself execute a SIGILL? (Is that actual UB in the compiler!? Or UB in LLVM? Or can SIGILL be part of a deliberate crash condition?)

With LLVM assertions enabled, I get this instead of just a SIGILL:

rustc: /checkout/src/llvm-project/llvm/lib/IR/Instructions.cpp:2974: static CastInst *llvm::CastInst::Create(Instruction::CastOps, Value *, Type *, const Twine &, InsertPosition): Assertion `castIsValid(op, S, Ty) && "Invalid cast!"' failed.

and if I pass -Zverify-llvm-ir, I get the same nice error:

Invalid bitcast
  %5 = bitcast { ptr, i64 } %4 to ptr
rustc-LLVM ERROR: Broken module found, compilation aborted!

I believe the difference you're observing on nightly is #133499 cc @nikic

Oh oops, we document that IR is not verified by default, so it's definitely intentional that on nightly we crash somewhat incoherently with invalid IR.

@steffahn

@steffahn Can you (or anyone else having context here) please provide a digestible summary of this issue? What is happening that shouldn't?

This is not a more recent regression (i.e. it "works" ever since GATs were introduced). It also isn't influenced by -Znext-solver.

By reading this sentence I infer that it's not a simple regression. Would you like the appropriate team to discuss this?

Thank you from the triage.

It's not really a regression at all in the conventional sense.

Is this more “minimal”? I don’t know… but it’s certainly more concise… more dense… anyway 😅

trait Tr: Sized {
    type Eq<T>;
    type EqLPrf<R>: Tr<Eq<Self> = Self::Prf<Self, R>>;
    type Prf<L, R>: Tr<Eq<L> = R>;
    type Rw<L: Tr<Eq<L> = <<R as Tr>::Prf<R, L> as Tr>::Eq<R>>, R>: Tr<Eq<L> = R>;
    fn transmute<R>(self) -> R;
}
impl<L_> Tr for L_ {
    type Eq<T> = T;
    type EqLPrf<R: Tr> = L_;
    type Prf<L: Tr<Eq<L> = L>, R: Tr> = L::Rw<L, R>;
    type Rw<L: Tr<Eq<L> = R>, R> = L;
    fn transmute<R: Tr>(self) -> <<R::EqLPrf<L_> as Tr>::Eq<R> as Tr>::Eq<R> {
        self
    }
}
fn main() {
    let s: String = vec![65_u8, 66, 67].transmute();
    println!("{}", s); // ABC
}

Edit: Eliminating/combining some more types…

trait Tr: Sized {
    type Eq<T>;
    type Prf<L, R>: Tr<Eq<L> = R>;
    fn transmute<L: Tr, R>(l: L) -> R;
}
impl<__> Tr for __ {
    type Eq<T> = T;
    type Prf<L: Tr<Eq<<R::Prf<R, L> as Tr>::Eq<R>> = R>, R: Tr> = L;
    fn transmute<L, R: Tr>(l: L) -> <R::Prf<R, L> as Tr>::Eq<R> {
        l
    }
}
fn main() {
    let s: String = <()>::transmute(vec![65_u8, 66, 67]);
    println!("{}", s); // ABC
}

I'll make this one into a follow-up because it's getting a bit wild; only one (generic) associated type is enough

trait Tr: Sized {
    type Prf<L, R>: Tr<Prf<L, ()> = R>;
    fn transmute<R>(self) -> R;
}
impl<L_> Tr for L_ {
    type Prf<L: Tr<Prf<<R::Prf<R, L> as Tr>::Prf<R, ()>, ()> = R>, R: Tr> = L;
    fn transmute<R: Tr>(self) -> <R::Prf<R, L_> as Tr>::Prf<R, ()> { self }
}
fn main() {
    let s: String = vec![65_u8, 66, 67].transmute();
    println!("{}", s); // ABC
}

or, with a bit less , ()… things:

trait Tr: Sized { type Prf<R>: Tr<Prf<R> = Self>; }
impl<L> Tr for L {
    type Prf<R: Tr<Prf<R> = <L::Prf<R> as Tr>::Prf<R>>> = R where L: Tr;
}
fn transmute<L: Tr, R>(r: L) -> <L::Prf<R> as Tr>::Prf<R> { r }
fn main() {
    let s: String = transmute::<_, String>(vec![65_u8, 66, 67]);
    println!("{}", s); // ABC
}

the R can be a trait parameter, too

trait Tr<R>: Sized { type Prf: Tr<R, Prf = Self>; }
impl<L, R> Tr<R> for L {
    type Prf = R where L: Tr<R>, R: Tr<R, Prf = <L::Prf as Tr<R>>::Prf>;
}
fn transmute<L: Tr<R>, R>(r: L) -> <L::Prf as Tr<R>>::Prf { r }
fn main() {
    let s: String = transmute::<_, String>(vec![65_u8, 66, 67]);
    println!("{}", s); // ABC
}

trait Tr<R>: Sized { type Prf: Tr<R, Prf = Self>; }
impl<L, R> Tr<R> for L {
    type Prf = R where L: Tr<R>, R: Tr<R, Prf = <L::Prf as Tr<R>>::Prf>;
}
fn transmute<L: Tr<R>, R>(r: L) -> <L::Prf as Tr<R>>::Prf { r }
fn main() {
    let s: String = transmute::<_, String>(vec![65_u8, 66, 67]);
    println!("{}", s); // ABC
}

that minization is actually a separate unsoundness (or at least what I intend to do to fix the original is insufficient there 💀). That sure is something

// We only check that GAT where-clauses of the *trait* while normalizing;
// normalizing `<T as Trait<U>>::Proof` to `U` trivially succeeds.
trait Trait<R>: Sized {
    type Proof: Trait<R, Proof = Self>;
}
impl<L, R> Trait<R> for L {
    // We prove that the impl item is compatible with the trait in the
    // env of the trait, which is pretty much empty.
    //
    // `L: Trait<R>` is trivial
    // `R: Trait<R, Proof = <L::Proof as Trait<R>>::Proof>` normalizes to
    // `R: Trait<R, Proof = <R as Trait<R>>::Proof>` normalizes to
    // `R: Trait<R, Proof = R>` is trivial
    //
    // Proving the item-bound holds assumes the *impl where-bounds*.
    // We normalize the where-bound `R: Trait<R, Proof = <L::Proof as Trait<R>>::Proof>`
    // by using the item-bound of `L::Proof`: `R: Trait<R, Proof = L>` 💀¹. Proving the
    // item-bound of `<L as Trait<R>>::Proof` is now trivial.
    type Proof
        = R
    where
        L: Trait<R>,
        R: Trait<R, Proof = <L::Proof as Trait<R>>::Proof>;
}

What's happening at ¹ is that proving that the item-bounds of an associated type is able
to assume the item-bounds of exactly that associated type. This is non-productive cyclic reasoning.

You've found a new way to exploit rust-lang/trait-system-refactor-initiative#62, answering the question posed in rust-lang/trait-system-refactor-initiative#116 😊

My perspective of the original unsoundness is that we're able to rely on the item-bounds of an associated type while never actually normalizing the associated type, which is unsound in case it diverges.

While your new minimization does not actually have any associated type which diverges. We're able to normalize <L::Proof as Trait<R>>::Proof to R without issues. The problem is the cyclic reasoning when proving that the item-bounds are actually valid.

that minization is actually a separate unsoundness (or at least what I intend to do to fix the original is insufficient there 💀). That sure is something

Oh… that’s interesting! I didn’t even really pay attention to the fact that it’s no longer containing containing any “cyclically defined ATIT”, at least for certain notions of “cyclically defined”. I got there (to the minimization) in a relatively incremental/step-by-step manner; but that certainly explains why I was having a hard time [i.e. not succeeding in] trying to translate the last version back into one without ATIT-where-bounds 🙃

@nikomatsakis

Alright, have a minimization I am happy with now and feel like I properly understand this bug:
https://rust.godbolt.org/z/Y6K3aKGGq

// Always applicable impls. Using two separate traits
// for clarity/simplicity.
trait IdA {
    type This;
}
impl<T> IdA for T {
    type This = T;
}
trait IdB {
    type This;
}
impl<T> IdB for T {
    type This = T;
}
trait Trivial {
    type Usize;
}
impl<T> Trivial for T {
    type Usize = usize;
}

// A diverging associated type whose item-bound must not apply
// and differs from an always applicable impl.
trait Diverges<T> {
    type Diverge<Recur: Diverges<T>>: Trivial<Usize = T>;
}
impl<T> Diverges<T> for () {
    type Diverge<Recur: Diverges<T>> = Recur::Diverge<()>;
}

// An impl with a where-clause which is normalized using the blanket impl when
// checking that its item-bounds hold. We then prove that where-clause via the
// incorrect item-bound from above.
//
// This allows us to transfer the item-bound to a concrete type while only
// using the diverging associated type in a generic context.
//
// Concretely, this is impl is well-formed as `<T as IdA>::This` normalizes to
// `<Recur as Trivial>::Usize` which is then normalized to `usize` by using
// the blanket impl. This means `<T as IdA>::This: IdB<This: Copy>` trivially
// holds.
//
// This means it should only be possible to instantiate it with `usize` itself.
// Instantiating `Recur` with `<D as Diverges<T>>::Diverge<()>` causes it to apply
// for all `T` instead.
trait Apply<D> {
    type Assoc: IdB<This: Copy>;
}
impl<T: IdA<This = <Recur as Trivial>::Usize>, Recur> Apply<Recur> for T {
    type Assoc = <T as IdA>::This;
}

fn copy_me<T, D: Diverges<T>>(x: T) {
    // Need to prove the where-bounds of `provide_where_bound` in a generic context
    // as normalizing `D::Diverge<()>` would otherwise overflow.
    //
    // Using the impl of `Apply` requires `T: IdA<This = <D::Diverge<()> as Trivial>::Usize>`.
    // We normalize `<D::Diverge<()> as Trivial>::Usize` to `T` using the item-bound of
    // `D::Diverge<()>` at which point the impl trivially applies.
    provide_where_bound::<D, T>(x)
}

fn provide_where_bound<D: Diverges<T>, T>(x: T)
where
    T: IdA<This = <T as Apply<D::Diverge<()>>>::Assoc>,
    T: Apply<D::Diverge<()>>,
{
    // Inside of this function `<T as Apply<D::Diverge<()>>>::Assoc` is rigid,
    // allowing us to use its incorrect item-bound.
    //
    // <<T as IdA>::This as IdB>::This: Copy
    // ------------------------------------- normalize `<T as IdA>::This` via where-bound
    // <<T as Apply<D::Diverge<()>>>::Assoc as IdB>::This: Copy
    // -------------------------------------------------------- prove via item-bound
    apply_where_bound::<T>(x)
}

fn apply_where_bound<T>(x: T)
where
    <<T as IdA>::This as IdB>::This: Copy,
{
    // We simply normalize `<<T as IdA>::This as IdB>::This` to `T` inside of this
    // function.
    dup(x, x)
}

fn dup<T>(_x: T, _y: T) {}

pub fn main() {
    copy_me::<String, ()>(String::from("hello there"));
}

As mentioned by @nikomatsakis in rust-lang/project-dictionary-passing#7 (comment) we've got a few ways forward here. I expect that the most likely approach will be to make sure we recheck where-clauses of functions during monomorphization to trigger the overflow at this point. Eagerly detecting potentially diverging associated types feels impossible to me without breaking too much existing code. @compiler-errors has implemented this in #135216 for a crater run.

Landing this may be blocked on the new solver as it will likely cause new overflow errors due to hitting the recursion limit. These are fatal with the old trait solver.

Small note that may be of interest: this also works:

trait Diverges<T> {
    type Diverge<Recur: Diverges<T>>: Trivial<Usize = T>;
}
impl<T> Diverges<T> for () {
    type Diverge<Recur: Diverges<T>> = Recur::Diverge<Recur>; // `::Diverge<Recur>` instead of `::Diverge<()>`
}

In other words, there's no need for a self-recursive trait impl for this. This is in fact the classic exploit for how to construct a non-terminating term in a language that allows for non-positive recursion (impl Diverges for () is ω from the link and the rest of the exploit is about carefully applying it to itself).

Also tiny simplification: you don't need to involve T in the Apply impl, this suffices:

impl<Recur> Apply<Recur> for () {
    type Assoc = <Recur as Trivial>::Usize;
}

I made my own version of this to help me understand.

I've tried to minimize a GAT-free version (and no where on associated types, which stabilized at the same time), this one works since 1.49 again. I might also try to minimize for a version that still supports all the way to Rust 1.1.

trait Rewrite<R>: Sized {
    type Result: Multi<(), Simpl = Self>;
}

impl<L, R, E> Rewrite<R> for L
where
    <E as Equal<<L as Equal<R>>::To>>::To: Multi<(), Simpl = L>,
    R: Multi<L, Cyclic = E>,
{
    type Result = <L as Equal<R>>::To;
}

trait Equal<R>: Sized {
    type To: Multi<Self>;
}
impl<L, R> Equal<R> for L {
    type To = R;
}

trait Multi<L>: Sized {
    type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
    type Simpl: Multi<(), Simpl = <L as Rewrite<Self>>::Result>;
}

impl<L, R> Multi<L> for R
where
    L: Equal<R>,
{
    type Cyclic = <L::To as Multi<L>>::Cyclic;
    type Simpl = L::To;
}

fn transmute<L, R>(x: L) -> R
where
    R: Multi<L, Simpl = R>,
{
    transmute_inner_1::<L, R>(x)
}

fn transmute_inner_1<L, R>(x: L) -> <R as Multi<L>>::Simpl
where
    R: Multi<L>,
    L: Rewrite<R>,
{
    transmute_inner_2::<<R as Multi<L>>::Simpl>(x)
}

fn transmute_inner_2<R>(x: <<R as Multi<()>>::Simpl as Multi<()>>::Simpl) -> R {
    x
}

fn main() {
    let s: String = transmute(vec![65_u8, 66, 67]);
    println!("{:?}", s); // ABC
}

(on 1.49 in compiler-explorer)

This is rather minimized for "size" (fewer traits, fewer associated types), not for ease of understanding. Which also means traits and types get dual use and are hard to name; like Equal being used for Proof: Equal<T1, To = T2> to mean that Proof guarantees T1 and T2 are the same, but also it has a trait bound ans is used to defined the cyclically defined type Cyclic in Multi; which in turn however also contains another associated type Simpl which itself has dual-use; one being that T1: Multi<(), Simpl = T2> serves as another way to write: T1 and T2 are the same type; and the other relates to the : Multi… bound on it – in this function, it corresponds most closely to the role of ProofIsProofValue in the original post.

Of course, given the 1.1 version exists, that’s not a full soundness regression at that point, but it still seems interesting 1.49 keeps coming up here. So I was curious where exactly the relevant change was lying:

Bisection this points to #80246 being relevant… which also explains the remarkably confusing bisection behavior, lol. (I had to go 2 release cycles newer than the anticipated nightly range; but the PR apparently was beta-backported very close before a release).

It’s funny that the PR description reads like the change was mainly about becoming more restrictive, but apparently for this code, effectively the compiler became more lenient instead?

Edit: There’s a second relevant bisection point. The code between stable versions goes from not compiling due to a (huge) list of overflow and mismatch errors

(this is rather lengthy… click to expand)

error[E0275]: overflow evaluating the requirement `Self: Rewrite<R>`
 --> src/main.rs:1:1
  |
1 | / trait Rewrite<R>: Sized {
2 | |     type Result: Multi<(), Simpl = Self>;
3 | | }
  | |_^
  |
  = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`playbisect`)

error[E0271]: type mismatch resolving `<E as Equal<R>>::To == L`
  --> src/main.rs:8:17
   |
5  | impl<L, R, E> Rewrite<R> for L
   |      -  - found type parameter
   |      |
   |      expected type parameter
...
8  |     R: Multi<L, Cyclic = E>,
   |                 ^^^^^^^^^^ expected type parameter `L`, found type parameter `R`
...
20 | trait Multi<L>: Sized {
   |       ----- required by a bound in this
21 |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
   |                                                ------ required by this bound in `Multi`
   |
   = note: expected type parameter `L`
                        found type `R`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

error[E0271]: type mismatch resolving `<<R as Multi<()>>::Cyclic as Equal<R>>::To == ()`
  --> src/main.rs:7:54
   |
5  | impl<L, R, E> Rewrite<R> for L
   |         - this type parameter
6  | where
7  |     <E as Equal<<L as Equal<R>>::To>>::To: Multi<(), Simpl = L>,
   |                                                      ^^^^^^^^^ expected `()`, found type parameter `R`
...
20 | trait Multi<L>: Sized {
   |       ----- required by a bound in this
21 |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
   |                                                ------ required by this bound in `Multi`
   |
   = note: expected unit type `()`
                   found type `R`

error[E0271]: type mismatch resolving `<L as Multi<()>>::Simpl == R`
  --> src/main.rs:7:54
   |
5  | impl<L, R, E> Rewrite<R> for L
   |      -  - expected type parameter
   |      |
   |      found type parameter
6  | where
7  |     <E as Equal<<L as Equal<R>>::To>>::To: Multi<(), Simpl = L>,
   |                                                      ^^^^^^^^^ expected type parameter `R`, found type parameter `L`
...
20 | trait Multi<L>: Sized {
   |       ----- required by a bound in this
21 |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
22 |     type Simpl: Multi<(), Simpl = <L as Rewrite<Self>>::Result>;
   |                           ------------------------------------ required by this bound in `Multi`
   |
   = note: expected type parameter `R`
                        found type `L`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

error[E0271]: type mismatch resolving `<R as Multi<()>>::Simpl == ()`
 --> src/main.rs:7:54
  |
5 | impl<L, R, E> Rewrite<R> for L
  |      - this type parameter
6 | where
7 |     <E as Equal<<L as Equal<R>>::To>>::To: Multi<(), Simpl = L>,
  |                                                      ^^^^^^^^^ expected type parameter `L`, found `()`
  |
  = note: expected type parameter `L`
                  found unit type `()`
  = note: required because of the requirements on the impl of `Rewrite<R>` for `()`

error[E0271]: type mismatch resolving `<R as Multi<()>>::Simpl == ()`
 --> src/main.rs:7:44
  |
5 | impl<L, R, E> Rewrite<R> for L
  |      - this type parameter
6 | where
7 |     <E as Equal<<L as Equal<R>>::To>>::To: Multi<(), Simpl = L>,
  |                                            ^^^^^^^^^^^^^^^^^^^^ expected type parameter `L`, found `()`
  |
  = note: expected type parameter `L`
                  found unit type `()`
  = note: required because of the requirements on the impl of `Rewrite<R>` for `()`

error[E0271]: type mismatch resolving `<<<Self as Equal<R>>::To as Multi<Self>>::Cyclic as Equal<<Self as Equal<R>>::To>>::To == Self`
  --> src/main.rs:14:14
   |
13 | / trait Equal<R>: Sized {
14 | |     type To: Multi<Self>;
   | |              ^^^^^^^^^^^ expected type parameter `Self`, found associated type
15 | | }
   | |_- this type parameter
...
20 |   trait Multi<L>: Sized {
   |         ----- required by a bound in this
21 |       type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
   |                                                  ------ required by this bound in `Multi`
   |
   = note: expected type parameter `Self`
                        found type `<Self as Equal<R>>::To`
   = note: you might be missing a type parameter or trait bound

error[E0271]: type mismatch resolving `<<Self as Equal<R>>::To as Multi<()>>::Simpl == Self`
  --> src/main.rs:14:14
   |
13 | / trait Equal<R>: Sized {
14 | |     type To: Multi<Self>;
   | |              ^^^^^^^^^^^ expected associated type, found type parameter `Self`
15 | | }
   | |_- this type parameter
   |
   = note:        expected type `<Self as Equal<R>>::To`
           found type parameter `Self`
   = note: you might be missing a type parameter or trait bound
   = note: required because of the requirements on the impl of `Rewrite<<Self as Equal<R>>::To>` for `Self`

error[E0271]: type mismatch resolving `<Self as Multi<()>>::Simpl == L`
  --> src/main.rs:20:1
   |
20 | / trait Multi<L>: Sized {
21 | |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
22 | |     type Simpl: Multi<(), Simpl = <L as Rewrite<Self>>::Result>;
23 | | }
   | |_^ expected type parameter `Self`, found type parameter `L`
   |
   = note:        expected type `Self`
           found type parameter `L`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters
   = note: required because of the requirements on the impl of `Rewrite<Self>` for `L`

error[E0271]: type mismatch resolving `<<<Self as Multi<L>>::Simpl as Multi<()>>::Cyclic as Equal<<Self as Multi<L>>::Simpl>>::To == ()`
  --> src/main.rs:22:17
   |
20 | trait Multi<L>: Sized {
   |       ----- required by a bound in this
21 |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
   |                                                ------ required by this bound in `Multi`
22 |     type Simpl: Multi<(), Simpl = <L as Rewrite<Self>>::Result>;
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected `()`, found associated type
   |
   = note: expected unit type `()`
                   found type `<Self as Multi<L>>::Simpl`
   = help: consider constraining the associated type `<Self as Multi<L>>::Simpl` to `()`
   = note: for more information, visit https://doc.rust-lang.org/book/ch19-03-advanced-traits.html

error[E0271]: type mismatch resolving `<Self as Multi<()>>::Simpl == <Self as Multi<L>>::Simpl`
  --> src/main.rs:22:17
   |
20 |   trait Multi<L>: Sized {
   |   -     ----- required by a bound in this
   |  _|
   | |
21 | |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
22 | |     type Simpl: Multi<(), Simpl = <L as Rewrite<Self>>::Result>;
   | |                 ^^^^^^^^^^------------------------------------^
   | |                 |         |
   | |                 |         required by this bound in `Multi`
   | |                 expected associated type, found type parameter `Self`
23 | | }
   | |_- this type parameter
   |
   = note: expected associated type `<Self as Multi<L>>::Simpl`
                         found type `Self`
   = note: you might be missing a type parameter or trait bound

error[E0271]: type mismatch resolving `<<Self as Multi<L>>::Simpl as Multi<()>>::Simpl == ()`
  --> src/main.rs:22:17
   |
20 | / trait Multi<L>: Sized {
21 | |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
22 | |     type Simpl: Multi<(), Simpl = <L as Rewrite<Self>>::Result>;
   | |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `Self`, found `()`
23 | | }
   | |_- this type parameter
   |
   = note:   expected type `Self`
           found unit type `()`
   = note: required because of the requirements on the impl of `Rewrite<<Self as Multi<L>>::Simpl>` for `()`

error[E0271]: type mismatch resolving `<<Self as Multi<L>>::Cyclic as Equal<Self>>::To == L`
  --> src/main.rs:20:1
   |
20 |   trait Multi<L>: Sized {
   |   -^^^^^-----^^^^^^^^^^
   |   |     |
   |   |     required by a bound in this
   |  _expected type parameter `L`, found type parameter `Self`
   | |
21 | |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
   | |                                                ------ required by this bound in `Multi`
22 | |     type Simpl: Multi<(), Simpl = <L as Rewrite<Self>>::Result>;
23 | | }
   | |_- found type parameter
   |
   = note: expected type parameter `L`
                        found type `Self`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

error[E0271]: type mismatch resolving `<Self as Multi<()>>::Simpl == L`
  --> src/main.rs:21:5
   |
20 |   trait Multi<L>: Sized {
   |   -           - found type parameter
   |  _|
   | |
21 | |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
   | |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `Self`, found type parameter `L`
22 | |     type Simpl: Multi<(), Simpl = <L as Rewrite<Self>>::Result>;
23 | | }
   | |_- expected type parameter
   |
   = note:        expected type `Self`
           found type parameter `L`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters
   = note: required because of the requirements on the impl of `Rewrite<Self>` for `L`

error[E0271]: type mismatch resolving `<<Self as Multi<L>>::Cyclic as Equal<Self>>::To == L`
  --> src/main.rs:21:5
   |
20 |   trait Multi<L>: Sized {
   |   -     ----- - expected type parameter
   |   |     |
   |  _|     required by a bound in this
   | |
21 | |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
   | |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^------^^
   | |     |                                          |
   | |     |                                          required by this bound in `Multi`
   | |     expected type parameter `L`, found type parameter `Self`
22 | |     type Simpl: Multi<(), Simpl = <L as Rewrite<Self>>::Result>;
23 | | }
   | |_- found type parameter
   |
   = note: expected type parameter `L`
                        found type `Self`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

error[E0271]: type mismatch resolving `<<Self as Multi<L>>::Simpl as Multi<()>>::Simpl == ()`
  --> src/main.rs:22:27
   |
20 | / trait Multi<L>: Sized {
21 | |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
22 | |     type Simpl: Multi<(), Simpl = <L as Rewrite<Self>>::Result>;
   | |                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `Self`, found `()`
23 | | }
   | |_- this type parameter
   |
   = note:   expected type `Self`
           found unit type `()`
   = note: required because of the requirements on the impl of `Rewrite<<Self as Multi<L>>::Simpl>` for `()`

error[E0271]: type mismatch resolving `<<L as Equal<R>>::To as Multi<()>>::Simpl == L`
  --> src/main.rs:25:12
   |
25 | impl<L, R> Multi<L> for R
   |      -     ^^^^^^^^ expected associated type, found type parameter `L`
   |      |
   |      this type parameter
   |
   = note:        expected type `<L as Equal<R>>::To`
           found type parameter `L`
   = note: required because of the requirements on the impl of `Rewrite<R>` for `L`
help: consider further restricting this bound
   |
27 |     L: Equal<R> + Equal<R, To = L>,
   |                 ^^^^^^^^^^^^^^^^^^

error[E0271]: type mismatch resolving `<<<L as Equal<R>>::To as Multi<L>>::Cyclic as Equal<<L as Equal<R>>::To>>::To == L`
  --> src/main.rs:25:12
   |
25 | impl<L, R> Multi<L> for R
   |      -     ^^^^^^^^ expected associated type, found type parameter `L`
   |      |
   |      this type parameter
   |
   = note:        expected type `<L as Equal<R>>::To`
           found type parameter `L`
help: consider further restricting this bound
   |
27 |     L: Equal<R> + Equal<R, To = L>,
   |                 ^^^^^^^^^^^^^^^^^^

error[E0271]: type mismatch resolving `<<R as Multi<L>>::Cyclic as Equal<R>>::To == L`
  --> src/main.rs:35:8
   |
20 | trait Multi<L>: Sized {
   |       ----- required by a bound in this
21 |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
   |                                                ------ required by this bound in `Multi`
...
33 | fn transmute<L, R>(x: L) -> R
   |              -  - found type parameter
   |              |
   |              expected type parameter
34 | where
35 |     R: Multi<L, Simpl = R>,
   |        ^^^^^^^^^^^^^^^^^^^ expected type parameter `L`, found type parameter `R`
   |
   = note: expected type parameter `L`
                        found type `R`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

error[E0271]: type mismatch resolving `<R as Multi<()>>::Simpl == L`
  --> src/main.rs:35:8
   |
33 | fn transmute<L, R>(x: L) -> R
   |              -  - expected type parameter
   |              |
   |              found type parameter
34 | where
35 |     R: Multi<L, Simpl = R>,
   |        ^^^^^^^^^^^^^^^^^^^ expected type parameter `R`, found type parameter `L`
   |
   = note:        expected type `R`
           found type parameter `L`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters
   = note: required because of the requirements on the impl of `Rewrite<R>` for `L`

error[E0271]: type mismatch resolving `<R as Multi<()>>::Simpl == L`
  --> src/main.rs:35:17
   |
33 | fn transmute<L, R>(x: L) -> R
   |              -  - expected type parameter
   |              |
   |              found type parameter
34 | where
35 |     R: Multi<L, Simpl = R>,
   |                 ^^^^^^^^^ expected type parameter `R`, found type parameter `L`
   |
   = note:        expected type `R`
           found type parameter `L`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters
   = note: required because of the requirements on the impl of `Rewrite<R>` for `L`

error[E0271]: type mismatch resolving `<<R as Multi<L>>::Cyclic as Equal<R>>::To == L`
  --> src/main.rs:42:8
   |
20 | trait Multi<L>: Sized {
   |       ----- required by a bound in this
21 |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
   |                                                ------ required by this bound in `Multi`
...
40 | fn transmute_inner_1<L, R>(x: L) -> <R as Multi<L>>::Simpl
   |                      -  - found type parameter
   |                      |
   |                      expected type parameter
41 | where
42 |     R: Multi<L>,
   |        ^^^^^^^^ expected type parameter `L`, found type parameter `R`
   |
   = note: expected type parameter `L`
                        found type `R`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

error[E0271]: type mismatch resolving `<<R as Multi<L>>::Cyclic as Equal<R>>::To == L`
  --> src/main.rs:40:37
   |
20 | trait Multi<L>: Sized {
   |       ----- required by a bound in this
21 |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
   |                                                ------ required by this bound in `Multi`
...
40 | fn transmute_inner_1<L, R>(x: L) -> <R as Multi<L>>::Simpl
   |                      -  -           ^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `L`, found type parameter `R`
   |                      |  |
   |                      |  found type parameter
   |                      expected type parameter
   |
   = note: expected type parameter `L`
                        found type `R`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

error[E0275]: overflow evaluating the requirement `Self: Rewrite<R>`
 --> src/main.rs:2:5
  |
2 |     type Result: Multi<(), Simpl = Self>;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`playbisect`)

error[E0271]: type mismatch resolving `<Self as Multi<()>>::Simpl == L`
  --> src/main.rs:22:5
   |
20 |   trait Multi<L>: Sized {
   |   -           - found type parameter
   |  _|
   | |
21 | |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
22 | |     type Simpl: Multi<(), Simpl = <L as Rewrite<Self>>::Result>;
   | |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `Self`, found type parameter `L`
23 | | }
   | |_- expected type parameter
   |
   = note:        expected type `Self`
           found type parameter `L`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters
   = note: required because of the requirements on the impl of `Rewrite<Self>` for `L`

error[E0271]: type mismatch resolving `<<<L as Equal<R>>::To as Multi<L>>::Cyclic as Equal<<L as Equal<R>>::To>>::To == L`
  --> src/main.rs:29:5
   |
20 | trait Multi<L>: Sized {
   |       ----- required by a bound in this
21 |     type Cyclic: Equal<<L as Equal<Self>>::To, To = L>;
   |                                                ------ required by this bound in `Multi`
...
25 | impl<L, R> Multi<L> for R
   |      - this type parameter
...
29 |     type Cyclic = <L::To as Multi<L>>::Cyclic;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `L`, found associated type
   |
   = note: expected type parameter `L`
                        found type `<L as Equal<R>>::To`
help: consider further restricting this bound
   |
27 |     L: Equal<R> + Equal<R, To = L>,
   |                 ^^^^^^^^^^^^^^^^^^

error[E0271]: type mismatch resolving `<<L as Equal<R>>::To as Multi<()>>::Simpl == L`
  --> src/main.rs:29:5
   |
25 | impl<L, R> Multi<L> for R
   |      - this type parameter
...
29 |     type Cyclic = <L::To as Multi<L>>::Cyclic;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected associated type, found type parameter `L`
   |
   = note:        expected type `<L as Equal<R>>::To`
           found type parameter `L`
   = note: required because of the requirements on the impl of `Rewrite<<L as Equal<R>>::To>` for `L`
help: consider further restricting this bound
   |
27 |     L: Equal<R> + Equal<R, To = L>,
   |                 ^^^^^^^^^^^^^^^^^^

error: aborting due to 27 previous errors

directly to the code working.

On nightly, there’s an intermediate step, where it returns a different, shorter error

error[E0275]: overflow evaluating the requirement `Self: Rewrite<R>`
 --> src/main.rs:1:1
  |
1 | trait Rewrite<R>: Sized {
  | ^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Rewrite`
  |
  = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`playbisect`)

error[E0275]: overflow evaluating the requirement `Self: Rewrite<R>`
 --> src/main.rs:2:5
  |
2 |     type Result: Multi<(), Simpl = Self>;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`playbisect`)

error: aborting due to 2 previous errors

which goes away with the abovementioned #80246.

Out of curiosity, I've bisected this earlier point of change now as well, and the relevant PR appears to be #73905

Test rejection of rust-lang/rust#135011

Navigation Menu

Repository navigation

Typesystem soundness hole involving cyclically-defined associated type in trait, and normalization in trait bounds #135011

18 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Typesystem soundness hole involving cyclically-defined associated type in trait, and normalization in trait bounds #135011

Description

Activity

saethlin commented on Jan 2, 2025

apiraino commented on Jan 2, 2025

workingjubilee commented on Jan 2, 2025

18 remaining items

steffahn commented on Jan 7, 2025

steffahn commented on Jan 7, 2025

lcnr commented on Jan 7, 2025

lcnr commented on Jan 7, 2025

lcnr commented on Jan 7, 2025

steffahn commented on Jan 7, 2025

lcnr commented on Jan 8, 2025

Nadrieril commented on Jan 10, 2025

steffahn commented on Jan 14, 2025

steffahn commented on Jan 14, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions