Overflow for trait implemented recursively on references

[hban]

Consider this snippet [playpen]:

trait Foo {}

impl<'a> Foo for &'a usize {}

// Ok when this impl is commented-out.
impl<'a, T> Foo for &'a Vec<T> where &'a T: Foo {}

fn foo<T>(_: T) where for<'a> &'a T: Foo {}

fn main() {
    foo(0);
}

error[E0275]: overflow evaluating the requirement `_: std::marker::Sized`
  --> <anon>:11:5
   |
11 |     foo(0);
   |     ^^^
   |
   = note: consider adding a `#![recursion_limit="128"]` attribute to your crate
   = note: required because of the requirements on the impl of `for<'a> Foo` for `&'a std::vec::Vec<_>`
   = note: required because of the requirements on the impl of `for<'a> Foo` for `&'a std::vec::Vec<std::vec::Vec<_>>`
   = note: required because of the requirements on the impl of `for<'a> Foo` for `&'a std::vec::Vec<std::vec::Vec<std::vec::Vec<_>>>`
   [ and so on... ]
   = note: required by `foo`

There is no issue when trait implementation for &'a Vec<T> is commented-out, even though Vec isn't actually used anywhere when calling foo method.

[steveklabnik]

Triage: still a bug

[lcdr]

I ran into a similar case which I believe is related:

#![recursion_limit="10"]

trait Trait {}

struct Foo<X>(X) where for<'a> &'a X: Trait;

impl<X> Foo<X> where for<'a> &'a X: Trait {
    fn new(x: X) -> Foo<X> {
        Foo(x)
    }
}

struct Bar<Y>(Y);

impl<Y> Trait for &Bar<Y> where for<'a> &'a Y: Trait {}

This also gives an overflow, but compiles fine with any of the following changes:

• The Bar impl's where clause is removed

• The Foo struct's where clause is removed

• Foo(x) is changed to Foo::<X>(x)

• Foo(x) is changed to Self(x).

I'm kind of surprised that the type of Self gets inferred correctly but Foo(x) doesn't. Maybe this could help with finding the cause.

[extrawurst]

Ran into this too now. Unfortunately my project is a rather big backend service using warp. hard to boil down a reproduction. it started to appear wafter upgrading to rust 1.53

[497e0bdf29873]

I ran into a similar issue trying to define custom container types that implement standard vector space operations when the contained type implements them (that for some odd reason—maybe this reason—the standard arrays do not). The following code that tries to implement all ref/noref combinations of multiplication with f64 for A<T> completely fails:

use std::ops::*;

struct A<T> {
    v : T
}

impl<T> Mul<f64> for A<T> where T : Mul<f64> {
    type Output = A<<T as Mul<f64>>::Output>;
    fn mul(self, w : f64) -> Self::Output { A{ v : self.v * w} }
}

impl<T> Mul<A<T>> for f64 where f64 : Mul<T> {
    type Output = A<<f64 as Mul<T>>::Output>;
    fn mul(self, x : A<T>) -> Self::Output { A{ v : self * x.v} }
}

impl<'a, T> Mul<f64> for &'a A<T> where &'a T : Mul<f64> {
    type Output = A<<&'a T as Mul<f64>>::Output>;
    fn mul(self, w : f64) -> Self::Output { A{ v : &(self.v) * w} }
}

// If you remove this
impl<'b, T> Mul<&'b A<T>> for f64 where f64 : Mul<&'b T> {
    type Output = A<<f64 as Mul<&'b T>>::Output>;
    fn mul(self, x : &'b A<T>) -> Self::Output { A { v : self * &(x.v) } }
}

fn main() {
    let t = A{v : 1.0};
    let _b = 3.0*&t; // ... and this, then it compiles.
    let _c = &t*3.0;
}

The code compiles perfectly fine if the last (fourth) impl is removed, as is the _b-line from main. The analogous third impl causes no problem. Removing impls 1–3 doesn't help with the fourth impl, so there's something special going on with its handling, which is not problem with 1 & 2 (that do not use references), or 3 (that has reference on the LHS).

If I do complete type annotation for the selection of Mul, the code works, even with nested A:

use std::ops::*;

struct A<T>  {
    v : T
}

impl<T> Mul<f64> for A<T> where T : Mul<f64> {
    type Output = A<<T as Mul<f64>>::Output>;
    fn mul(self, w : f64) -> Self::Output { A{ v : <T as Mul<f64>>::mul(self.v, w) } }
}

impl<T> Mul<A<T>> for f64 where f64 : Mul<T> {
    type Output = A<<f64 as Mul<T>>::Output>;
    fn mul(self, x : A<T>) -> Self::Output { A{ v : <f64 as Mul<T>>::mul(self, x.v) } }
}

impl<'a, T> Mul<f64> for &'a A<T> where &'a T : Mul<f64> {
    type Output = A<<&'a T as Mul<f64>>::Output>;
    fn mul(self, w : f64) -> Self::Output { A{ v : <&'a T as Mul<f64>>::mul(&(self.v), w)} }
}

impl<'b, T> Mul<&'b A<T>> for f64 where f64 : Mul<&'b T> { 
    type Output = A<<f64 as Mul<&'b T>>::Output>;
    fn mul(self, x : &'b A<T>) -> Self::Output { A { v : <f64 as Mul<&'b T>>::mul(self, &(x.v)) } }
}

fn main() {
    let t = A{ v : A{v : 1.0 } };
    let _a = <f64 as Mul<&A<A<f64>>>>::mul(3.0, &t); // This explicit typing works
    //let _b = 3.0*(&t); //  If you uncomment this, the compiler overflows.
    let _c = &t*3.0;
}

Such is, of course, not practical in daily use. Removing the type annotations in the “daily use ” lines in main, i.e., enabling the _b-line, causes the compilation again to fail with

error[E0275]: overflow evaluating the requirement `f64: std::ops::Mul<&A<_>>`

Simply based on the error message, without knowing much about the compiler internals, it seems as if it is looking for Mul<&A<_>> for an arbitrary type _ instead of Mul<&A<A<f64>>>. But it should know that t : A<A<f64>>. Adding that explicit type annotation does not help the _b-line.

[497e0bdf29873]

As I posted on stack oveflow, I came up with a few workarounds that do not require major changes to architecture, just adding some level counting to nested structures at the type system level. Maybe they will further help pinpoint the issue, so I'm posting them here as well.

Both workrounds are based on a “nesting level counting multiplication trait”. For brevity I only include f64 * &A<T>; for version 2 &A<T> * f64, f64 * A<T>, and A<T>*64 are unchanged from https://github.com/rust-lang/rust/issues/37748#issuecomment-1003557517 above, as they do not require the level-counting workaround. For version 1 the extra level type parameter of A should be handled in those as well.

Version 2

This version is very non-invasive with regard to code that should work without the compiler bug. It only implements a “shadow” variant of the original (multiplication) function that counts nesting levels at the type system level.

use std::ops::*;

// Our nested data structure
struct A<T> {
    v : T
}

// Nesting level counting structs and traits
struct L0 {}
struct Succ<L> { _prev : L }
trait Nested { type Level; }

// Primitives like f64 are at nesting level zero
impl Nested for f64 { type Level = L0; }
// A<T> always increases nesting level
impl<T> Nested for A<T> where T : Nested { type Level=Succ<T::Level>; }

// Nested multiplication trait. Default implementation is standard multiplication.
trait NestedMul<T, L> : Mul<T>  + Sized {
    fn nested_mul(self, a : T) -> Self::Output { self * a}
}
// Auto-implement it at level 0
impl<'b,S,T> NestedMul<&'b T,L0> for S where T : Nested<Level=L0>, S : Mul<&'b T> + Sized {}

// Special implementation of NestedMul for A, bypassing Mul
impl<'b, T : Nested> NestedMul<&'b A<T>, Succ<T::Level>> for f64 where f64 : NestedMul<&'b T, T::Level> {
    fn nested_mul(self, a : &'b A<T>) -> Self::Output {  A { v : self.nested_mul(&(a.v))  } }
}

// The “interface” : when A is multiplied in plain code, we pass to level-counting nested
// multiplication to avoid compiler overflow. 
//
// Version 1: this would be for all nesting structures. Not allowed by Rust as it involves
// no local structs. Similarly f64 has to be hard-coded here / this whole impl macro-generated
// when generalising to other types.
//
//impl<'b, T : Nested> Mul<&'b T> for f64 where f64 : NestedMul<T, T::Level>  { 
//    type Output=<f64 as Mul<&'b T>>::Output;
//    fn mul(self, a : &'b A<T>) -> Self::Output { self.nested_mul(a) }
//}
//
// Version 2: specifically for A<T>. A minor optimisation as bypasses one level of
// nested_mul:
impl<'b, T : Nested> Mul<&'b A<T>> for f64 where f64 : NestedMul<&'b T, T::Level> { 
   type Output=A<<f64 as Mul<&'b T>>::Output>;
   fn mul(self, a : &'b A<T>) -> Self::Output {  A { v : self.nested_mul(&(a.v)) } }
 }

fn main() {
    let t : A<A<f64>> = A{ v : A{v : 1.0 } };
    let _b = 3.0*&t;
}

Version 1

The first version used PhantomData and a type parameter addition to the nesting structure A, so is a bit more invasive. Since type inference in main is not completely automatic using basic struct constructors, a little bit more work would be needed to write constructors for which inference works.

use std::ops::*;
use std::marker::PhantomData;

// Define type-level integers
struct L0 {}
struct Succ<L> { _prev : L }
type L1 = Succ<L0>;
type L2 = Succ<L1>;

// Our nested data structure that includes the nesting level.
struct A<T,L> {
    v : T,
    lev : PhantomData<L>
}

// Nested multiplication trait. Default implementation is standard multiplication.
trait NestedMul<T, L> : Mul<T>  + Sized {
    fn nested_mul(self, a : T) -> Self::Output { self * a }
}

// Implement it for f64 using defaults.
impl<'b,T> NestedMul<T, L0> for f64 where f64 : Mul<T> { }

// Special implementation of NestedMul for A, bypassing Mul
impl<'b,L,T> NestedMul<&'b A<T,Succ<L>>,Succ<L>> for f64 where f64 : NestedMul<&'b T, L> {
    fn nested_mul(self, a : &'b A<T,Succ<L>>) -> Self::Output {
        A { v : self.nested_mul(&(a.v)), lev : PhantomData  }
    }
}

// The “interface” : when A is multiplied in plain code, we pass to level-counting nested
// multiplication to avoid compiler overflow. 
impl<'b, T, L> Mul<&'b A<T, Succ<L>>> for f64 where f64 : NestedMul<&'b T, L> { 
    type Output=A<<f64 as Mul<&'b T>>::Output, Succ<L>>;
    fn mul(self, a : &'b A<T,Succ<L>>) -> Self::Output {
        A { v : self.nested_mul(&(a.v)), lev : PhantomData }
    }
}

fn main() {
    let t : A<A<f64,L1>,L2> = A{ v : A{v : 1.0, lev : PhantomData }, lev : PhantomData };
    let _b = 3.0*&t;
}

[vihdzp]

In the original snippet, writing foo::<usize>(0) seems to alleviate the issue. I ran into a similar issue and was able to fix it temporarily with explicit type annotations. However, my codebase grew and I eventually ended up adding some trait implementation that made the issue pop up again. Can't figure out how to minimize this example, but I think it's worth noting that this isn't an actual fix.

[mccolljr]

I was attempting to implement a wrapper for std::fmt::Write, and ran into what I believe is this issue.

This is the most minimal reproduction I could find:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=797bea3e1d91ae53f5c939437046a60c

fn write_wrapped<W>(mut w: W, s: &str, recurse: bool) -> std::fmt::Result
where
    W: std::fmt::Write,
{
    if recurse {
        write_wrapped(&mut w, s, false)
    } else {
        w.write_str(s)
    }
}

fn main() {
    let mut s = String::new();
    write_wrapped(&mut s, "test", true).unwrap();
    println!("{:?}", s);
}

It is interesting, because:

1. Running the above code with MIRI works.
2. Selecting the Build option (instead of Run) on the playground successfully compiles this code without the complaint

However, running the code with the Run option on the playground results in

Compiling playground v0.0.1 (/playground)
error: reached the recursion limit while instantiating `write_wrapped::<&mut &mut &mut &...&mut &mut &mut &mut &mut String>`
 --> src/main.rs:6:9
  |
6 |         write_wrapped(&mut w, s, false)
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
note: `write_wrapped` defined here
 --> src/main.rs:1:1
  |
1 | / fn write_wrapped<W>(mut w: W, s: &str, recurse: bool) -> std::fmt::Result
2 | | where
3 | |     W: std::fmt::Write,
  | |_______________________^
  = note: the full type name has been written to '/playground/target/debug/deps/playground-dd2e0560d12456cf.long-type.txt'

error: could not compile `playground` due to previous error

[mozhewen]

Any progress about this issue? I ran into the same issue also when implementing traits for a newtype:

struct Wrap<T>(T);

trait Foo {}

impl Foo for Wrap<usize> {}

// Ok when this impl is commented-out.
impl<T> Foo for Wrap<Vec<T>> where Wrap<T>: Foo {}

fn foo<T>(_: T) where Wrap<T>: Foo {}

fn main() {
    foo(0);  // won’t compile
}

In the original snippet, writing foo::<usize>(0) seems to alleviate the issue. I ran into a similar issue and was able to fix it temporarily with explicit type annotations. However, my codebase grew and I eventually ended up adding some trait implementation that made the issue pop up again. Can't figure out how to minimize this example, but I think it's worth noting that this isn't an actual fix.

This does solve the problem, but is apparently less elegant as mentioned.

An almost identical version in Haskell works very well:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE FlexibleContexts #-}

newtype Wrap t = Wrap t

class Foo a where
    method :: a -> Int
    method _ = 123

instance Foo (Wrap Bool)

instance (Foo (Wrap t)) => Foo (Wrap [t])

foo :: (Foo (Wrap t)) => t -> ()
foo _ = ()

foo2 :: (Foo (Wrap t)) => t -> Int
foo2 t = method (Wrap [t])

main :: IO ()
main = do

    print $ foo True
    print $ foo2 True

-- Output:
-- ()
-- 123