Compiler error with generic impls and traits

[nventuro]

Aim

This is a minimal reproduction of an issue I encountered while trying to write tests for aztec-nr libraries. The libraries have generic types, and in my tests I needed to use concrete types with them. This broke the build as unrelated callsites started complaining about mismatching types. Not being an expert in the language, this seems like a bug.

Expected Behavior

I expected to be able to have generic functions and to be able to call them using concrete types.

Bug

The following does not compile:

// This is some trait
trait Trait {
    fn new() -> Self;
}

// This is a library function over a type that impls the trait
pub fn library_fn<TypeThatImpls>() -> TypeThatImpls where TypeThatImpls: Trait {
    TypeThatImpls::new()
}

// This is a concrete struct
struct ConcreteTraitImpl;

// That impls the trait expected by library_fn
impl Trait for ConcreteTraitImpl {
    fn new() -> Self {
        ConcreteTraitImpl {}
    }
}

// This is a generic struct
struct LibraryUser<SomeType>;

// This is a generic impl for the generic struct
impl<SomeType> LibraryUser<SomeType> {

    // The following function causes a compiler error. Comment it out to compile.
   // This calls the original library function with a generic type. I imagine library_fn's generic 
   // type TypeThatImpls is made the same as SomeType because of the return type.
    fn call_library_fn() -> SomeType {
        library_fn()
    }
}

fn main() { }

The error is the following:

25 │     fn call_library_fn() -> SomeType {
   │                             -------- expected SomeType because of return type
26 │         library_fn()
   │         ------------ ConcreteTraitImpl returned here

I'm confused as to why ConcreteTraitImpl suddenly shows up as the return type. Maybe because it is the only type that impls the trait? Even then this seems very odd to me (though again, far from an expert).

I expected the error to go away if I deleted ConcreteTraitImpl, but get a different one instead:

17 │         library_fn()
   │         ---------- No impl for `SomeType: Trait`

This seems to hint at me missing something, though I don't really know how to interpret this. Sure, there's no impl for that trait, but I'm not trying to instantiate the struct, call the function, etc., so why does this matter at this stage?

Project Impact

Blocker

Installation Method

Compiled from source

Nargo Version

nargo version = 0.24.0 noirc version = 0.24.0+6522738a781fcff2353d1edca4402c0978a62653 (git version hash: 6522738a781fcff2353d1edca4402c0978a62653, is dirty: false)

[nventuro]

For what it's worth, the above code compiles in Rust (with minor modifications: Rust requires that we use the type parameter somewhere for SomeType, and also that we further constrain SomeType to implement Trait, which it implicitly should due to SomeType == TypeThatImpls as mentioned above).

[TomAFrench]

I've noticed that you don't have a trait bound on the impl of Library user. library_fn can't know that SomeType will satisfy the bound on its return type. Looks like we don't support this currently.

[nventuro]

Something worth mentioning is that in the original aztec-nr scenario, this was triggered when I added a concrete implementation (in the same crate). I am not sure why this example does not work even when there is no concrete implementation - perhaps there's some other detail missing.

[jfecher]

25 │     fn call_library_fn() -> SomeType {
   │                             -------- expected SomeType because of return type
26 │         library_fn()
   │         ------------ ConcreteTraitImpl returned here

This is odd, I wonder if this is related to #4450.

17 │         library_fn()
   │         ---------- No impl for `SomeType: Trait`

This is the expected error, your call_library_fn is generic over any type SomeType, so we don't know if this type implements Trait or not. You need to restrict this method to be generic over not all types, but only types that implement Trait:

impl<SomeType> LibraryUser<SomeType> {
    // The following function causes a compiler error. Comment it out to compile.
   // This calls the original library function with a generic type. I imagine library_fn's generic 
   // type TypeThatImpls is made the same as SomeType because of the return type.
    fn call_library_fn() -> SomeType where SomeType: Trait {
        library_fn()
    }
}

[nventuro]

This is the expected error, your call_library_fn is generic over any type SomeType, so we don't know if this type implements Trait or not. You need to restrict this method to be generic over not all types, but only types that implement Trait:

Ahhh so it's the same error as in Rust, I didn't realize this from the error message. Theirs is quite clear:

error[E0277]: the trait bound `SomeType: Trait` is not satisfied
  --> src/main.rs:33:9
   |
33 |         library_fn()
   |         ^^^^^^^^^^ the trait `Trait` is not implemented for `SomeType`
   |
note: required by a bound in `library_fn`
  --> src/main.rs:7:74
   |
7  | pub fn library_fn<TypeThatImpls>() -> TypeThatImpls where TypeThatImpls: Trait {
   |                                                                          ^^^^^ required by this bound in `library_fn`
help: consider restricting type parameter `SomeType`
   |
27 | impl<SomeType: Trait> LibraryUser<SomeType>  {
   |              +++++++

As a side note, it'd be convenient if I could apply the where clause to the entire impl and not just that function. In our actual aztec-nr library that where is currently repeated 8 times.

[jfecher]

@nventuro do you mind creating an issue for the where clause on an impl? It is mentioned in the Epic: #2568 under "Implement trait constraints" .. "free impl blocks" but we don't have an issue yet for it. Since it is just syntactic sugar it's helpful to know how much it is wanted.

An issue for an error message that can be improved would be helpful as well.

[nventuro]

Sure, created #4508 and #4509. I didn't want to spam you with random requests, but I'm happy to do things that way in the future!

[sklppy88]

Had a call w/ @nventuro we think there's another use case where it fails under similar conditions. Would be happy to supply more doc if this minimal reproduction needs extension. This was a weird blocker that lead me down a few rabbit-holes 😅