Recursive generic types: overflow evaluating the requirement

help
1

Hi,

I am having trouble with recursive types involving generics. This is the minimal example I was able to create:

trait Expr {
    fn eval(&self) -> i64;
}

struct Const(i64);
impl Expr for Const {
    fn eval(&self) -> i64 { self.0 }
}

enum Either<A,B> { Left(A), Right(B) }
impl<A,B> Expr for Either<A,B> where A: Expr, B: Expr {
    fn eval(&self) -> i64 {
        match self {
            Either::Left(x) => x.eval(),
            Either::Right(x) => x.eval()
        }
    }
}

trait Func {
    type Output;
    fn call(&self, n: i64) -> Self::Output;
}
impl<F,X> Func for F where F: Fn(i64) -> X {
    type Output = X;
    fn call(&self, n: i64) -> Self::Output { self(n) }
}

struct Defer<F>(F,i64);
// Try to comment out this impl (along with the 'number' function) and uncomment the specific one below
impl<F> Expr for Defer<F> where F: Func, F::Output: Expr {
    fn eval(&self) -> i64 { self.0.call(self.1).eval() }
}

fn number(n: i64) -> impl Expr {
    if n <= 0 {
        Either::Left(Const(0))
    } else {
        Either::Right(Defer(number, n-1))
    }
}

struct Number;
impl Func for Number {
    type Output = Either<Const, Defer<Number>>;
    fn call(&self, n: i64) -> Self::Output {
        if n <= 0 {
            Either::Left(Const(0))
        } else {
            Either::Right(Defer(Number, n-1))
        }
    }
}
// Try to uncomment this impl and comment out the generic one above
// impl Expr for Defer<Number> {
//     fn eval(&self) -> i64 { self.0.call(self.1).eval() }
// }

#[derive(Clone, Debug)]
struct Foo(Option<Box<Foo>>);

fn main() {
    // Try to uncomment this line
    // println!("{}", Number.call(7).eval());
    println!("{}", number(7).eval());
    println!("{:?}", Foo(Some(Box::new(Foo(None)))).clone());
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0275]: overflow evaluating the requirement `Either<Const, Defer<fn(i64) -> impl Expr {number}>>: Expr`
   |
note: required for `Defer<fn(i64) -> impl Expr {number}>` to implement `Expr`
  --> src/main.rs:31:9
   |
31 | impl<F> Expr for Defer<F> where F: Func, F::Output: Expr {
   |         ^^^^     ^^^^^^^^                           ---- unsatisfied trait bound introduced here
   = note: 1 redundant requirement hidden
   = note: required for `Either<Const, Defer<fn(i64) -> impl Expr {number}>>` to implement `Expr`

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

Yes, there is a cyclic dependency (Defer<Number>: Expr depends on itself), but I do not understand why that is a problem (simpler recursive types (like struct Foo(Option<Box<Foo>>) seem to work fine).

Also I tried to use struct Number instead of fn number (so I can name the types and experiment with annotations) and it gave me different error message (about Expr not being implemented for Defer<Number> or something else along the cycle).

However when I provide the specific impl Expr for Defer<Number> (and comment out the generic one) the code complies and runs well. This last case convinced me that there is probably nothing fundamentally wrong (like infinite type name or infinitely sized type) and it is all about that cyclic dependency.

I think I have some vague idea on what is going on. If we ask the question "Does Defer<Number> implement Expr?" we can answer "No" and there is no contradiction. However if we answer "Yes" that also yields no contradiction. So the compiler perhaps looks for a minimal solution or something like that. But that does not explain why struct Foo(Option<Box<Foo>>) can implement Clone, Debug and such. The reasoning would be the same: If it does not then it does not, there is nothing to force it. Except ...

The impl Clone for Foo has no (direct) trait bounds. So I think there are two "classes" of "requirements":

#1: Those used to determine which impls to choose to satisfy a trait requirement and
#2: Those that are checked after eveything is resolved.

That would explain what happens here. The one unconditional impl Clone for Foo is chosen and then checked, but no impl Expr for Defer<Number> is ever chosen because none is "supported" (i.e. there are no "base cases" which it could depend on, not as in "Rust does not support it").

However if this is correct, the followup question would be: How to tell compiler which bounds are #1 and which are #2. For example I would like the compiler to always choose the given impl Expr for Defer<F> and only then check if F: Func and F::Output: Expr. Is it possible? Or am I completely wrong? Is there any way around this?

Tom

(sorry for long post, but I wanted to provide full information of what my problem is)

1 Like
2

I'm not familiar with the exact implementation details of the compiler around constraints, but I don't think this is correct. Trait bounds aren't inherently checked before or after "impls are chosen" (I'm not sure what you mean by that), nor are they evaluated in a specific order in relation to each other. They are all considered as a complete set of constraints to be solved. If the solution exists and is unique, then your code compiles; if it's unsatisfiable or ambiguous, you get an error.

Now it's possible that the trait solver happens to apply an iterative procedure and you are observing artefacts of that, but this is at least not something that's either intentional or has any deeper meaning, to the best of my knowledge.

3

I think one potential problem with allowing trait definitions that depend on the selves in such a manner is that a trait with an associate type could then pass of this type definition recursively. The Expr trait doesn't actually have any associated types, but there are consistency arguments to be made.

Also, yes, you do seem to correctly identify that the logic that applies here allows both "yes the type implements the trait" and "no the type doesn't implement the trait to be valid solutions. I wouldn't say the compiler goes with the minimal solution though. As far as I understand it doesn't decide at all (which of course also means that you cannot depend on the impl, so it's more similar to it not existing than existing) but I'd at least conjecture that what's going on here isn't as much the compiler telling you the trait isn't implemented and more that it gave up trying to figure out whether or not it was. One indicator that it really didn't conclude that no there isn't an Defer<Number>: Expr implementation already is the adding such an impl results in a conflicting implementations error. It's only an indicator though since the conflicting impls checker is sometimes more conservative than it would need to be.

Whether or not it's desirable to resolve such a situation where it's logically underspecicified whether or not a trait impl exists in a different way (e. g. always say yes, or always say no) is a different question, and I haven't thought that one through.

Regarding the example with Clone, that's different. The only recursive thing there is the function implementation, not the bounds on the implementation itself.

The derived impl of Clone for

struct Foo(Option<Box<Foo>>);

does not contain a where Option<Box<Foo>>: Clone clause. Instead it simply calls the Option::<Box<Foo>>::clone() method (resulting in mutual recursion) without having it's existence required by a where clause. Inside of a impl Foo for Bar implementation, the question that Bar: Foo is already settled. (Yes it does, as long as the where clauses, if any, are met.) Type checking the function bodies of the implementations then is a subsequent and independent step that will already have full knowledge of all implementations of all traits for all types, including the implementation it serves to define.

So the part of figuring out the implementation is not cyclic. Clone for Foo is an unconditional impl. Based on that one, the generic impls for Option and Box give rise to Option<Box<Foo>>: Clone. End of that story. And then this implementation is known to exist at the point where the function body of <Foo as Clone>::clone is type checked. This is all sound because the function body type checking or not cannot have any influence anymore on the question whether or not Foo: Clone is true in the first place. Only on the question whether or not the code-base compiles successfully.

2 Likes
4

What I meant is this:

When you consider the code (supposed expansion of the derive(Clone) macro)

impl Clone for Foo {
    fn clone(&self) -> Self { Self(self.0.clone()) }
}

someone has to check if Option<Box<Foo>> (the type of self.0) implements Clone. It is not written explicitly as a where bound, but it must be checked anyway.

Similarly if you consider

impl<F> Expr for Defer<F> where F: Func, F::Output: Expr {
    fn eval(&self) -> i64 { self.0.call(self.1).eval() }
}

someone has to check (among other things) if F::Output (the type of self.0.call(self.1)) implements Expr. But now it is written explicitly as a where bound.

It seems to be that the two cases are treated differently. If you add a where Option<Box<Foo>>: Clone bound, the error will appear again. (That actually happened to me when I was trying to implement a recursive data structure generic over the pointer type.) Even if it (the bound) seems completely redundant, the compiler is going to check it anyway, but somehow adding this (seemingly) redundant condition causes there to be no or non-unique solution.

5

Well ... in my actual code the Expr trait has associated types, I just removed them (and plenty of other stuff) to minimize the example. So are you saying more troubles are waiting for me? :slight_smile:

Hmm ... the error messages for fn number and struct Number are very different. The one for fn number does look to me like the compiler gave up figuring out a solution, but the one for struct Number seems like the compiler is pretty sure there is no impl Expr for a bunch of types.

Also I do not understand why the messages are so different. The two cases should be (almost) equivalent, don't they?

So I would (probably) like to achieve the same effect for my generic impl<F> Expr for Defer<F>. Like "Use this impl always please and check for F: Func, F::Output: Expr later. If the check fails, well, reject the program as not-well-typed, but this is the impl to use."

6

I think, following this approach would probably mean more of something like "use this impl for all types F and reject the program if it isn't the case that all rust types F implement Func" which, well, not all types implement Func so it would fail to compile.

7

In this case you mean something like

impl<F> Expr for Defer<F> where F: Func, F::Output: Expr {
    fn eval(&self) -> i64 { self.0.call(self.1).eval() }
}

fn number(n: i64) -> impl Expr {
    if n <= 0 {
        Either::Left(Const(0))
    } else {
        Either::Right(Defer(Number, n-1))
        //                  ^^^^^^
    }
}

correct? Then for the opaque return type to meet its bound, we have to prove:

  • Either<Const, Defer<Number>>: Expr
    • Const: Expr :white_check_mark:
    • Defer<Number>: Expr
      • Number: Func :white_check_mark:
      • Number::Output: Expr
        • Either<Const, Defer<Number>>: Expr :repeat:

And this is what is referred to as a inductive cycle: the constraint depends on itself. Also as I understand it, in the general case, any inductive cycle is considered an error today -- your beloved E0275 -- and the bound is considered unprovable.

However, there are exceptions! These are referred to as coinductive traits or bounds -- if they depend on themselves, they are considered to be satisfied. That's a property you wish you had, but with today's compiler, you do not.

What traits do have this quality?

Why do I keep saying "today"? Rust may get a coinductive trait solver eventually. While I've seen this referred to a number of times (like in that issue), there's no RFC or other guide about what exactly that would mean, as far as I know. Maybe it would mean your example compiles.

For the numbers(n: i64) -> impl Expr case, things are a little murkier to me. In this case, the opaque return type is a recursive or infinitely sized type if we try to get rid of the opaqueness. It could be that the opaqueness is "strong" enough that this doesn't matter to the compiler and it's another coinductive situation, or it could be problematic in other ways; I'm not sure which.

Well, this worked, so probably it's just the coninductive situation.

4 Likes
8

Not sure of how much use this may or may not be for your case, but here’s something that does work:

trait Expr {
    fn eval(&self) -> i64;
}

struct Const(i64);
impl Expr for Const {
    fn eval(&self) -> i64 { self.0 }
}

enum Either<A,B> { Left(A), Right(B) }
impl<A,B> Expr for Either<A,B> where A: Expr, B: Expr {
    fn eval(&self) -> i64 {
        match self {
            Either::Left(x) => x.eval(),
            Either::Right(x) => x.eval()
        }
    }
}

trait Func {
    type Output: Expr;
    fn call(&self, n: i64) -> Self::Output;
}

struct Defer<F>(F, i64);
impl<F> Expr for Defer<F> where F: Func {
    fn eval(&self) -> i64 { self.0.call(self.1).eval() }
}

struct Number;
impl Func for Number {
    type Output = Either<Const, Defer<Number>>;
    fn call(&self, n: i64) -> Self::Output {
        if n <= 0 {
            Either::Left(Const(0))
        } else {
            Either::Right(Defer(Number, n-1))
        }
    }
}

fn main() {
    println!("{}", Number.call(7).eval());
}

The approach here is that Func itself already requires Output to implement Expr. The fn number(n: i64) -> impl Expr, I removed, because it still would’ve led to compilation errors in this framework, when compiled. (Incidentally, only now I’ve noticed the “fun” discrepancy between cargo check and cargo build behavior on your original playground, too).

This simplifies the situation, which is not simply

  • Number: Func is still simply true
  • now, Defer<Number> only requires Number: Func, which is also non-recursive, so it’s true

(that’s it)

The subsequent check for the contents of the trait impls to be correct is then what checks that Number::Output: Expr must hold, which it does, because now we know the Defer<Number>: Expr implementation and can work with it to further deduce Either<Const, Defer<Number>>: Expr without issues.

2 Likes
9

That is a step in the right direction for me, but it would be even better if Number::Output could be inferred. But that would be too close to my original approach, so I am afraid it would not work. (Is that one inference the only actual difference between the fn number(i64) -> impl Expr and the impl Func for Number (in your example)?)

But now that I think of it, isn't there a way to stop the recursion even in my first exmple?

The reasoning would be as follows:

  1. let {number} be the name of the type of the fn number(i64) -> impl Expr { code } function and {number::Output} be the name of it's opaque return type. (I assume the compiler does assign internal names to such unnameable types.)
  2. We have {number}: Fn(i64) -> {number::Output} and {number::Output}: Expr. These are given by the header of the function. The body of the function will need to be checked if its inferred return type actually implements Expr, but form outside of the function we do not care (and cannot care) what exactly it is.
  3. Given that, the bounds on impl<F,X> Func for F where F: Fn(i64) -> X, X: Expr are satisfied for F = {number}, X = {number::Output}, so we have {number}: Func and <{number} as Func>::Output = {number::Output}
  4. Given that, the bounds on impl<F> Expr for Defer<F> where F: Func, F::Output: Expr are satisfied for F = {number}, so we have Defer<{number}>: Expr
  5. Now we can conclude (some easy steps omitted) that Either<Const, Defer<{number}>>: Expr
  6. We still need to typecheck the body of the number function and infer its return type:
    5.1. type of number is {number}
    5.2. type of Defer(number, n-1) is Defer<{number}>
    5.3. type of Either::Right(Defer(number, n-1)) is Either<_, Defer<{number}>>
    5.4. type of Either::Left(Const(0)) is Either<Const, _>
    5.5. unifying the two we obtain Either<Const, Defer<{number}>> which does indeed implement Expr as we have seen.

I see no cycle in this reasoning. The point is the function header can be used as a boundary to break the cycle.

So ... did I miss something? Is there a way to make it work?

[edit: fixed typos]

10

I’m not sure entirely how exactly the impl Trait return types work, but I believe this is already where your argument falls down. These “opaque” types are not actually fully distinct types. I’ve experimented a bit with versions of the example code at hand, and cannot help but come to the conclusion that cargo check does fully agree with considering them distinct types sufficiently to follow your reasoning, but then it looks like during code-gen the compile seems to re-check (or re-trace?) the trait bounds in a way that doesn’t involve the opaque types anymore (presumably in the kind of code that would ultimately find the right actual monomorphization of function to call), and it’s that step that leads to an overflow.

I’ve tried everything from introducing trait boundaries to lots of explicit type-alias-impl-trait. You can get something like

#![feature(type_alias_impl_trait)]

pub trait Expr {
    fn eval(&self) -> i64;
}

pub struct Const(i64);
impl Expr for Const {
    fn eval(&self) -> i64 {
        self.0
    }
}

pub enum Either<A, B> {
    Left(A),
    Right(B),
}
impl<A, B> Expr for Either<A, B>
where
    A: Expr,
    B: Expr,
{
    fn eval(&self) -> i64 {
        match self {
            Either::Left(x) => x.eval(),
            Either::Right(x) => x.eval(),
        }
    }
}

pub trait Func {
    type Output: Expr;
    fn call(&self, n: i64) -> Self::Output;
}

pub struct Defer<F>(F, i64);
impl<F> Expr for Defer<F>
where
    F: Func,
{
    fn eval(&self) -> i64 {
        self.0.call(self.1).eval()
    }
}

impl<F, X> Func for F
where
    F: Fn(i64) -> X,
    X: Expr,
{
    type Output = X;
    fn call(&self, n: i64) -> Self::Output {
        self(n)
    }
}

pub struct Number;
impl Func for Number {
    type Output = Either<Const, Defer<Number>>;
    fn call(&self, n: i64) -> Self::Output {
        if n <= 0 {
            Either::Left(Const(0))
        } else {
            Either::Right(Defer(Number, n - 1))
        }
    }
}

pub type NumRet = impl Expr;
pub fn number(n: i64) -> NumRet {
    if n <= 0 {
        Either::Left(Const(0))
    } else {
        Either::Right(Defer(number, n - 1))
    }
}
pub type Num = impl Fn(i64) -> NumRet;
pub const NUM: Num = number;

fn test<F: Fn(i64) -> X, X: Expr>(f: F) {
    // f.call(7).eval();
}
pub fn demo() {
    test::<Num, _>(NUM);
}

fn main() {
    println!("{}", Number.call(7).eval());
    number(7);
    demo();
}

to run, but once you uncomment the call in test to f.call(7).eval(); it fails, even though it makes use of nothing but the F: Fn(i64) -> X, X: Expr implementations that are very clearly established in the function itself, and of course cargo check (or cargo run if test is never called, or called only with more straightforward implementors) doesn’t complain about anything.

11

Hmm .. interesting, so the overflow happens during monomorphization/instantiation. That would explain why only the call to eval method triggers the error. However I still don't understand how that happens as I see only finitely many types in the program. Noone showed me an infinite list of instances that would be generated (not even the compiler; is there an option to do so?).

After some experimentation I managed to get this to run:

#![feature(return_position_impl_trait_in_trait)]

trait Expr {
    fn eval(&self) -> i64;
}

struct Const(i64);
impl Expr for Const {
    fn eval(&self) -> i64 { self.0 }
}

enum Either<A,B> { Left(A), Right(B) }
impl<A,B> Expr for Either<A,B> where A: Expr, B: Expr {
    fn eval(&self) -> i64 {
        match self {
            Either::Left(x) => x.eval(),
            Either::Right(x) => x.eval()
        }
    }
}

trait Func {
    fn call(&self, n: i64) -> impl Expr;
}
impl<F,X> Func for F where F: Fn(i64) -> X, X: Expr {
    fn call(&self, n: i64) -> impl Expr { self(n) }
}

struct Defer<F>(F,i64);
impl<F> Expr for Defer<F> where F: Func {
    fn eval(&self) -> i64 { self.0.call(self.1).eval() }
}

fn number(n: i64) -> impl Expr {
    if n <= 0 {
        Either::Left(Const(0))
    } else {
        Either::Right(Defer(number, n-1))
    }
}

struct Number;
impl Func for Number {
    fn call(&self, n: i64) -> impl Expr {
        if n <= 0 {
            Either::Left(Const(0))
        } else {
            Either::Right(Defer(Number, n-1))
        }
    }
}

fn main() {
    println!("{}", Number.call(7).eval());
    let seven = number(7);
    // println!("{}", seven.eval());
}

It is based on your previous example, but with impl Traits in traits. There is slightly more "ceremony" but it allows me to write my recursive function without the need to explicitly name the return type. Except it is not stable :frowning:

And I do not understand why this works:

struct Number;
impl Func for Number {
    fn call(&self, n: i64) -> impl Expr {
        if n <= 0 {
            Either::Left(Const(0))
        } else {
            Either::Right(Defer(Number, n-1))
        }
    }
}

and this doesn't:

fn number(n: i64) -> impl Expr {
    if n <= 0 {
        Either::Left(Const(0))
    } else {
        Either::Right(Defer(number, n-1))
    }
}

The only difference is that the latter goes through the impl<F,X> Func for F where F: Fn(i64) -> X, X: Expr. And maybe the impl Traits in traits behave differently from those on inherent functions? But should they?

12

I tried to implement your suggestion in my project and unfortunately it did not work. That said, in my project the situation is more complex that the example I have given. There are more generic parameters, traits and associated types involved. So maybe now there is an infinite type somewhere (although I tried to avoid it) or I just did it wrong.

But anyway, I am giving up on this approach and I will just use dynamic dispatch for recursive cases. I don't like it much, so I will probably revisit this later, but for now I want to move on.

Thank you for your time and effort.

13

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.