E0275: Overflow evaluating the requirement with a generic impl

Hi,
I'm trying to design a highly generic AST, which allows each expression/statement/etc. to have user-specified associated data, as well as user-specified IR statements and expressions. The general design I have is:

  • A trait for functionality that is required from the associated data (how to Visit it with the visitor pattern) (AssociatedData).
  • A trait consisting of associated types, one for each of the several IR items and associated data types (AstAssociations).
  • Downstream crates create an empty struct that implements AstAssociations.
  • This crate provides a handy EmptyNode struct, indicating the absence of associated data or IR items. It
  • This crate also provides a special AssocBase, which has configurable associated data (defaulting to empty), and is restricted to empty IR items.

However, I'm running into a compiler error, stating that there is an overflow when evaluating a trait requirement. However, that requirement should obviously be satisfied. I just can't seem to understand where the overflow comes from.

Here is the code:

#![recursion_limit = "1024"]

use std::marker::PhantomData;

trait AssociatedData<A: AstAssociations + ?Sized> { 
    // Left empty in this Gist. However, it will have behaviour
    // that is guided by the generic A, for instance, Visitor
    // pattern helpers.
}
trait AstAssociations {
    type ExprAssociatedData: AssociatedData<Self>;
}
struct AssocBase<ExprAssociatedData = EmptyNode>(PhantomData<ExprAssociatedData>);

impl<ExprAssociatedData> AstAssociations for AssocBase<ExprAssociatedData>
where
    ExprAssociatedData: AssociatedData<Self>,
{
    type ExprAssociatedData = ExprAssociatedData;
}

struct EmptyNode;
impl<Assoc: AstAssociations + ?Sized> AssociatedData<Assoc> for EmptyNode {}

struct Statement<Assoc: AstAssociations + ?Sized>(PhantomData<Assoc>);
impl<Assoc: AstAssociations + ?Sized> Statement<Assoc> {
    fn zoop() { }
}

fn main() {
    let s: Statement<AssocBase> = Statement(PhantomData);
    s.zoop()
}

And the compiler output is here:

error[E0275]: overflow evaluating the requirement `EmptyNode: AssociatedData<AssocBase>`
  --> src/main.rs:29:12
   |
29 |     let s: Statement<AssocBase> = Statement(PhantomData);
   |            ^^^^^^^^^^^^^^^^^^^^
   |
note: required because of the requirements on the impl of `AstAssociations` for `AssocBase`
  --> src/main.rs:12:26
   |
12 | impl<ExprAssociatedData> AstAssociations for AssocBase<ExprAssociatedData>
   |                          ^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: required by a bound in `Statement`
  --> src/main.rs:22:25
   |
22 | struct Statement<Assoc: AstAssociations + ?Sized>(PhantomData<Assoc>);
   |                         ^^^^^^^^^^^^^^^ required by this bound in `Statement`

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

For reference, here's my Rust playground:

Let's call this "impl A":

impl<ExprAssociatedData> AstAssociations for AssocBase<ExprAssociatedData>
where
    ExprAssociatedData: AssociatedData<Self>,
{
    type ExprAssociatedData = ExprAssociatedData;
}

And let's call this "impl B":

impl<Assoc: AstAssociations + ?Sized> AssociatedData<Assoc> for EmptyNode {}

Then this statement:

    let s: Statement<AssocBase> = Statement(PhantomData);

Has the following requirements.

  • Declaration s: Statement<AssocBase<EmptyNode>>
    • Just restoring elided type defaults
  • Requires AssocBase<EmptyNode>: AstAssociations<EAD=?>
    • By Statement declaration (and for zoop to be defined)
  • Requires EmptyNode: AssociatedData< AssocBase<EmptyNode> >
    • Via impl A
  • Requires AssocBase<EmptyNode>: AstAssociations<EAD=?>
    • Via impl B

The last top-level bullet is looping to the second top-level bullet.


The Self in impl A is a bit suspicious. It refers to the trait implementer, in any implementation, in case that wasn't clear. I tried changing it to

ExprAssociatedData: AssociatedData<ExprAssociatedData>

And then as per compiler hint to

ExprAssociatedData: AssociatedData<ExprAssociatedData> + AstAssociations

but that didn't get me anywhere. I don't really understand how all your parts are supposed to play together, so I stopped there.

1 Like

Hi, thanks for the help. Your bullet point explanation has helped me understand the underlying problem and its design implications.

My approach might be a little unorthodox. AstAssociations is meant to be a trait that contains "type references", so to speak, to all the IR types and such, that are used by one concrete AST type. So, instead of having

enum Statement<ExprAssoc, StatementAssoc, IRExpr, IRStatement>
where
    ExprAssoc: AssociatedData<ExprAssoc, StatementAssoc, IRExpr, IRStatement>,
    IRExpr: AssociatedData<ExprAssoc, StatementAssoc, IRExpr, IRStatement>,
    // etc.
{
    IR(IRStatement),
    ExpressionStatement(Expr<ExprAssoc, StatementAssoc, IRExpr, IRStatement>),
}

I would simply have

enum Statement<Assoc: AstAssocations + ?Sized> {
    IR(Assoc::IRStatement),
    ExprStatement(Expr<Assoc>),
}

So, it would be functioning as a nice shorthand.

AssociatedData<A>, on the other hand, might need to be aware of the types used by an AST, even other than itself. What if an IRStatement wants to contain any AstAssociations::IRExpr, and call its methods? This is why impl A does the suspicious type parameter.

Anyway, your highly helpful bullet point explanation will make me re-evaluate my API design a bit here.

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.