Lifetime bounds for an iterator of generic wrapped associated types

edlanglois · May 18, 2021, 8:38pm

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!

steffahn · May 18, 2021, 8:48pm

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

steffahn · May 18, 2021, 8:58pm

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
    }
}

edlanglois · May 18, 2021, 9:11pm

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.

steffahn · May 18, 2021, 9:50pm

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).

edlanglois · May 20, 2021, 4:20am

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!

edlanglois · May 20, 2021, 5:46am

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)

edlanglois · May 20, 2021, 6:04pm

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.

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)

edlanglois · May 22, 2021, 2:00am

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.

system · August 20, 2021, 2:00am

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.

Topic		Replies	Views
Implied lifetime bound of associated types help	3	125	August 13, 2025
Problem with lifetime on Trait in impl help	2	1226	January 12, 2023
Associated type in trait bounded by Iterator	4	381	November 24, 2023
How to specify lifetime for associated type	6	7057	January 12, 2023
Confusion on lifetime bounds on type parameters	24	1034	April 8, 2021

Lifetime bounds for an iterator of generic wrapped associated types

Related topics