Lifetime bounds for an iterator of generic wrapped associated types

I am having trouble with lifetime bounds in the following code.
There is a Space type with an Element associated type and a function do_stuff that takes an IntoIterator of element references. I am trying to implement a generic OptionSpace whose elements are Option<S::Element> for S: Space.

In the implementation for OptionSpace<S>::do_stuff, the compiler complains that it wants S::Element: 'a in order to guarantee that Option<S::Element>: 'a even though I have bounded Self::Element: 'a and Self::Element = Option<S::Element>. If I change the bounds to S::Element: 'a then the method interface is different, which is also an error.

pub trait Space {
    type Element;

    fn do_stuff<'a, I>(&self, elements: I)
    where
        I: IntoIterator<Item = &'a Self::Element>,
        Self::Element: 'a;
}

pub struct OptionSpace<S> {
    pub inner: S,
}

impl<S: Space> Space for OptionSpace<S> {
    type Element = Option<<S as Space>::Element>;
    // type Element = Vec<<S as Space>::Element>; // Also fails
    // type Element = <S as Space>::Element; // Works
    
    fn do_stuff<'a, I>(&self, _elements: I)
    where
        I: IntoIterator<Item = &'a Self::Element>,
        Self::Element: 'a,
        // <Self as Space>::Element: 'a, // same error
        // Option<<S as Space>::Element>: 'a, // same error
    {
    }
}

(Playground)

This results in

error[E0309]: the associated type `<S as Space>::Element` may not live long enough
  --> src/main.rs:21:25
   |
21 |         I: IntoIterator<Item = &'a Self::Element>,
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = help: consider adding an explicit lifetime bound `<S as Space>::Element: 'a`...
   = note: ...so that the reference type `&'a Option<<S as Space>::Element>` does not outlive the data it points at

I get that S::Element might not live for 'a at the impl-level but since Self::Element: 'a is part of the bound on do_stuff shouldn't that just mean that do_stuff won't be available?

Some things that I have tried

  • (Fails, interface mismatch) Replacing / adding the suggested <S as Space>::Element: 'a bound.
  • (Fails, same lifetime error) Use Element = Vec<S::Element> instead of Option<...>.
  • (Works) Use Element = S::Element instead of Option<...>.
  • (Works) Taking a single &'a Self::Element as an argument instead of an iterator
  • (Works) Use a concrete inner type instead of generic S, e.g. Element = Option<i64>
// This works fine
pub struct OptionIntSpace;

impl Space for OptionIntSpace {
    type Element = Option<i64>;
    
    fn do_stuff<'a, I>(&self, _elements: I)
    where
        I: IntoIterator<Item = &'a Self::Element>,
        Self::Element: 'a {}
}

Is anyone able to help me understand what is going wrong or how I can get it to work?
If it is the case that the lifetime bounds on Space::do_stuff should be expressed differently, it might be helpful to know that in my actual code do_stuff returns a value but that value does not depend on 'a.

Thanks for taking the time to read this!

You aren’t doing anything wrong AFAICT, this is just the rust compiler acting stupid around lifetime bounds.

1 Like

Sometimes using PhantomData<&'a T> arguments works better than using T: 'a bounds. So here’s an approach that works:

use std::marker::PhantomData;

pub trait SpaceImplementationHelper {
    type TheElementType;

    fn the_do_stuff_implementation<'a, I>(
        this: &Self,
        elements: I,
        _marker: PhantomData<&'a Self::TheElementType>,
    ) where
        I: IntoIterator<Item = &'a Self::TheElementType>;
}

impl<S: ?Sized> Space for S
where
    S: SpaceImplementationHelper,
{
    type Element = S::TheElementType;

    fn do_stuff<'a, I>(&self, elements: I)
    where
        I: IntoIterator<Item = &'a Self::Element>,
        Self::Element: 'a,
    {
        Self::the_do_stuff_implementation(self, elements, PhantomData)
    }
}

impl<S: Space> SpaceImplementationHelper for OptionSpace<S> {
    type TheElementType = Option<<S as Space>::Element>;

    fn the_do_stuff_implementation<'a, I>(
        this: &Self,
        elements: I,
        _marker: PhantomData<&'a Self::TheElementType>,
    ) where
        I: IntoIterator<Item = &'a Self::TheElementType>,
    {
        // your implementation here
    }
}
2 Likes

Interesting, thanks for the work-around!

So is it the case that the compiler infers X: 'a when you have Something<&'a X> as an argument but not when Something<&'a X> &'a X is part of a trait bound? And your fix is to take advantage of that automatic inference?

Edit: Scratch that, there's no Something<&'a X> in the trait bound.

Yes, that’s basically correct. As you noticed, the compiler isn’t too well-behaved around these so-called “implied bounds”, your code is a perfect example of that. There’s even soundness issues in the compiler related to implied bounds (e.g. #80176 or #84591). There’s also a work-in-progress more principled (re-)interpretation of Rust’s trait system called Chalk that will probably/hopefully eventually solve shortcomings such as the one you ran into here, once it’s fully featured and stable (which may still take quite a while).

1 Like

Looking at this again, it's wild that the compiler is OK with Element = S::Element or Element = S::TheElementType but not Element = Option<S::Element> with the exact same bounds for do_stuff. Why would it be inspecting the structure of Self::Element like that...
Well, I'm looking forward to Chalk!

In my actual code, there was another generic implementation for Space so I couldn't use

impl<S: ?Sized> Space for S
where
    S: SpaceImplementationHelper

but fortunately

impl<S> Space for OptionSpace<S>
where
    OptionSpace<S>: SpaceImplementationHelper,

works as well.

And Element and do_stuff are actually part of separate traits so I didn't end up having to make a phony TheElementType either (so much for my theory that that was helping hide the structure).

In the end my solution looks like this:

use std::marker::PhantomData;

pub trait Space {
    type Element;
}

pub trait DoStuff: Space {
    fn do_stuff<'a, I>(&self, elements: I)
    where
        I: IntoIterator<Item = &'a Self::Element>,
        Self::Element: 'a;
}

pub struct OptionSpace<S> {
    pub inner: S,
}

impl<S: Space> Space for OptionSpace<S> {
    type Element = Option<<S as Space>::Element>;
}

impl<S: Space> PhantomDoStuff for OptionSpace<S> {
    fn phantom_do_stuff<'a, I>(
        &self, 
        _elements: I,
        _marker: PhantomData<&'a Self::Element>)
    where
        I: IntoIterator<Item = &'a Self::Element>,
        Self::Element: 'a,
    {
        // Implementation here
    }
}

impl<S: Space> DoStuff for OptionSpace<S>
where
    OptionSpace<S>: PhantomDoStuff
{
    fn do_stuff<'a, I>(&self, elements: I)
    where
        I: IntoIterator<Item = &'a Self::Element>,
        Self::Element: 'a
    {
        self.phantom_do_stuff(elements, PhantomData)
    }
}

pub trait PhantomDoStuff: Space {
    fn phantom_do_stuff<'a, I>(
        &self,
        elements: I,
        _marker: PhantomData<&'a Self::Element>)
    where
        I: IntoIterator<Item = &'a Self::Element>,
        Self::Element: 'a;
}

(playground)

Edit: Actually this doesn't work. The interface type-checks but Self::Element is treated as arbitrary not as a an Option<_>. And OptionSpace<S> : Space<Element = Option<<S as Space>::Element>> just brings back the original lifetime error. Back to using PhantomData.

I've found an even better work-around for the case of separate Space and DoStuff traits. No PhantomData necessary!
It turns out that all it takes is adding OptionSpace<S>: Space in impl<S> DoStuff for Space.
:roll_eyes:

pub trait Space {
    type Element;
}

pub trait DoStuff: Space {
    fn do_stuff<'a, I>(&self, elements: I)
    where
        I: IntoIterator<Item = &'a Self::Element>,
        Self::Element: 'a;
}

pub struct OptionSpace<S> {
    pub inner: S,
}

impl<S: Space> Space for OptionSpace<S> {
    type Element = Option<<S as Space>::Element>;
}

impl<S: Space> DoStuff for OptionSpace<S>
where
    OptionSpace<S>: Space
{
    fn do_stuff<'a, I>(&self, _elements: I)
    where
        I: IntoIterator<Item = &'a Self::Element>,
        Self::Element: 'a
    {
        // Implementation here
    }
}

(playground)

I think I have a more complete understanding now of why steffahn's solution works. (Posting here for the sake of anyone else who might run into a similar issue, and in order to be corrected if I'm wrong).

So there are two parts. The first part is to write down an implementation for do_stuff that compiles, but with a different interface. This is SpaceImplementationHelper::the_do_stuff_implementation. It adds _marker: PhantomData<&'a Self::TheElementType> in order to solve the compiler's lifetime complaint.
This works because the compiler automatically infers lifetimes bounds for references that appear in the argument list. Originally the reference only appeared as a trait bound so the lifetime bound wasn't inferred automatically, and a bug/flaw in the compiler means it would not accept the lifetime bound given explicitly.

The second part is to connect this implementation with a trait implementation for Space (or DoStuff in the two-trait version) under the original interface. For whatever reason, rust only refuses to accept a lifetime bound for Self::Element if it knows that Self::Element = Option<_>. So the trick to successfully compile an implementation for Space (DoStuff) is to hide the structure of Self::Element from the compiler.

In steffahn's solution, this is accomplished by

impl<S> Space for S
where
    S: SpaceImplementationHelper
{
    type Element = S::TheElementType;

As far as the compiler is concerned, SpaceImplementationHelper::TheElementType could be anything, so Element can also be anything, and is not known to be Option<_>. It might also be the case that even if TheElementType were known to be Option<_>, the assignment type Element = S::TheElementType without any wrapping types would be enough to avoid triggering the lifetime bug. I'm not sure about this part.

In any case, in the implementation of Space::do_stuff, the compiler doesn't know that Self::Element is Option<_> so it accepts the bound Self::Element: 'a and the code compiles.

My first two-trait solution (the one that works) shows that it's not necessary to have a separate TheElementType trait to obfuscate the structure of Self::Element from the compiler, adding Option<S>: PhantomDoStuff works instead.

impl<S: Space> DoStuff for OptionSpace<S>
where
    OptionSpace<S>: PhantomDoStuff

I think what's going on here is that usually rust sees impl DoStuff for OptionSpace<S> using Self::Element, finds impl Space for OptionSpace<S> and knows that Element = Option<<S as Space>::Element>, triggering the bug. However, with OptionSpace<S>: PhantomDoStuff it just treats PhantomDoStuff as a generic bound without considering any pre-existing relationships/impls. As a generic bound PhantomDoStuff: Space so PhantomDoStuff implies the existence of the associated type Element, but without any particular structure (because existing impls are ignored here). Finally, the Self::Element implied by OptionSpace<S>: PhantomDoStuff (aka Self: PhantomDoStuff) takes precedence over the Self::Element implied by impl Space for OptionSpace<S>. This means that when we get to the implementation for Space::do_stuff, rust just thinks that Self::Element has no internal structure, which avoids triggering the bug and allows the code to compile.