The type parameter is not constrained by the impl trait, self type, or predicates

Question

I am trying to implement a trait for types such that the reference to the type is convertible into an iterator with Item implementing a specific trait

Specifically, consider the following code:

struct Arena;

pub trait Scan {
    fn scan(&self, arena: &mut Arena);
}

impl<'a, 'b, Iterable, Item> Scan for Iterable
where
    &'b Iterable: IntoIterator<Item = Item>,
    Item: Scan + 'a,
{
    fn scan(&self, arena: &mut Arena) {
        for item in (&self).into_iter() {
            item.scan(arena);
        }
    }
}

(See this example in the Playground)

The compiler complains, underlining Item:

the type parameter `Item` is not constrained by the impl trait, self type, or predicates
unconstrained type parameter

I do not really understand for now where am I going in the wrong direction: to me, it looks like if the generic implementation is pretty much constrained by the conditions under where. How do I explain the idea to the compiler?

Sustentacular

See #60766588 – Florous

Answer 1

When you write a generic trait implementation such as

impl<'a, 'b, Iterable, Item> Scan for Iterable

it is required that all the generic types appear in the definition of the type that implements the trait. In your case Iterable is there but Item is not.

But you do not really need Item to be generic. I think you are adding it just to write a constraint on it. Ideally you want to write something like:

impl<'a, 'b, Iterable> Scan for Iterable
where
    &'b Iterable: IntoIterator<Item : Scan + 'a>,

Unfortunately that is still an unstable feature associated_type_bounds.

But fortunately you do not need an associated type bound for that. You can write instead:

impl<'a, 'b, Iterable> Scan for Iterable
where
    &'b Iterable: IntoIterator,
    <&'b Iterable as IntoIterator>::Item : Scan + 'a,

Now the constraints work but the lifetimes fail!

error[E0309]: the parameter type `Iterable` may not live long enough
  --> src/lib.rs:27:19
   |
27 |     &'b Iterable: IntoIterator,
   |                   ^^^^^^^^^^^^ ...so that the reference type `&'b Iterable` does not outlive the data it points at
   |
help: consider adding an explicit lifetime bound...
   |
23 | impl<'a, 'b, Iterable: 'b> Scan for Iterable
   |                      ++++

If you do as the compiler nicely suggests and add Iterable: 'b and... now if fails in the implementation of the function itself:

error: lifetime may not live long enough
  --> src/lib.rs:31:21
   |
23 | impl<'a, 'b, Iterable> Scan for Iterable
   |          -- lifetime `'b` defined here
...
29 |     fn scan(&self, arena: &mut Arena)
   |             - let's call the lifetime of this reference `'1`
30 |     {
31 |         for item in (&self).into_iter() {
   |                     ^^^^^^^^^^^^^^^^^^^ argument requires that `'1` must outlive `'b`

Which is actually expected, as the anonymous lifetime of &self is unrelated to 'b, and you cannot change that because you cannot add constraints to the implementation of a function trait.

The obvious solution for this (without having any other code around, maybe it won't work for you) is to implement the trait for &'b Iterable. This way &self is actually &&'b Iterable and all fits together. Moreover, now Iterable: 'b is implicit and not needed anymore:

impl<'a, 'b, Iterable> Scan for &'b Iterable
where
    &'b Iterable: IntoIterator,
    <&'b Iterable as IntoIterator>::Item : Scan + 'a,
{
    fn scan(&self, arena: &mut Arena)
    {
        for item in self.into_iter() {
            item.scan(arena);
        }
    }
}

BTW, as it is I think the 'a lifetime is mostly useless.

Mccowan

Answer 2

Here's how I would define this implementation:

impl<Iterable> Scan for Iterable
where
    for<'b> &'b Iterable: IntoIterator,
    for<'b> <&'b Iterable as IntoIterator>::Item: Scan,
{
    fn scan(&self, arena: &mut Arena) {
        for item in (&self).into_iter() {
            item.scan(arena);
        }
    }
}

The lifetime annotation 'b is not really relevant for implementing the trait since the trait itself has no generic lifetime bounds nor does the type you're implementing it upon, a simple generic. It is only used for the constraint that &Iterable implements IntoIterator for any lifetime. Using for<_> is called a higher-ranked trait bound.

I also omitted 'a since it looked to have no utility in your implementation.

Hepzi

That you, that seems really nice at first sight. Do you also understand why it stops working at the point when you add an additional impl for RefCell? For now I do not really see why the constraints would be malformed so we could hit the recursion limit – Sustentacular

Well shoot, looks like my solution runs into this issue: Why do I get an "overflow evaluating the requirement" error for a simple trait implementation? – Hepzi