Unable to make code compile with generic associated lifetimes

help
1

So I am currently experimenting a bit with gals and I got stuck with this piece of code which I can not get to work:

#![feature(generic_associated_types)]

use core::hash::Hash;
use core::borrow::Borrow;
use core::marker::PhantomData;

pub trait ToIter<T> {
    type Iter<'b>: Iterator<Item = &'b T>
    // Why must one constrain T to live for 'b?
    // this is implied by &'b T !
    where
        T: 'b;

    /// Returns an immutable iterator over the remaining items in the
    /// iterator.
    fn iter(&self) -> Self::Iter<'_>;
}

pub trait Set<T> {
    type Iter<'a>: Iterator<Item = &'a T> where T: 'a;
    
    fn iter(&self) -> Self::Iter<'_>;
    
    /// Returns true if the value is in the set, false if it is not.
    #[must_use]
    fn contains<Q: ?Sized>(&self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Hash + Eq;
}

/// This iterator returns all elements that are in a but not in b.
/// In math one writes it as `A \ B`
pub struct Difference<'a, T, A: Set<T>, B: Set<T>>
where
    T: 'a,
{
    a: A::Iter<'a>,
    b: &'a B,
    _p: PhantomData<T>,
}

impl<'a, T: Hash + Eq, A: Set<T>, B: Set<T>> Iterator for Difference<'a, T, A, B> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        // implementation is relatively straight forward
        for element in self.a.by_ref() {
            if !self.b.contains(element) {
                return Some(element);
            }
        }

        None
    }
}

// this is where things get confusing
// either the compiler is not smart enough or I am not smart enough to see
// the problem
impl<'a, T: Hash + Eq, A: Set<T>, B: Set<T>> ToIter<T> for Difference<'a, T, A, B>
where
    A::Iter<'a>: Clone,
{
    type Iter<'b>
    where
        T: 'b,
        B: 'b,
        A: 'b,
    = Difference<'b, T, A, B>;

    fn iter(&self) -> Self::Iter<'_> {
        Difference {
            a: self.a.clone(),
            b: self.b,
            _p: PhantomData,
        }
    }
}

playground

   Compiling playground v0.0.1 (/playground)
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter `'a` due to conflicting requirements
  --> src/main.rs:90:9
   |
90 |         Difference {
   |         ^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime defined on the method body at 89:13...
  --> src/main.rs:89:13
   |
89 |     fn iter(&self) -> Difference<'_, T, A, B> {
   |             ^^^^^
note: ...so that the types are compatible
  --> src/main.rs:90:9
   |
90 | /         Difference {
91 | |             a: self.a.clone(),
92 | |             b: self.b,
93 | |             _p: PhantomData,
94 | |         }
   | |_________^
   = note: expected `Difference<'_, _, _, _>`
              found `Difference<'_, _, _, _>`
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 85:6...
  --> src/main.rs:85:6
   |
85 | impl<'a, T: Hash + Eq, A: Set<T>, B: Set<T>> Difference<'a, T, A, B>
   |      ^^
note: ...so that the expression is assignable
  --> src/main.rs:91:16
   |
91 |             a: self.a.clone(),
   |                ^^^^^^^^^^^^^^
   = note: expected `<A as Set<T>>::Iter<'_>`
              found `<A as Set<T>>::Iter<'a>`

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

It seems like the A::Iter<'a>: Clone is the problem, because it creates a copy with the same lifetime and not with the lifetime of 'b, but how can this be solved?

1 Like
2

Subtyping and variance

Traits are always invariant in their type and lifetime parameters. This is because you don't know the variance of the implementing type so you have to assume invariance, which is the most conservative option.

Therefore, self.a is a A::Iter<'a>, and self.a.clone() gives you another A::Iter<'a>. It does not give you a A::Iter<'_> where the '_ can be filled in with the lifetime of self. self.b works fine, because &'a B is covariant in 'a, so the 'a can be shortened to the (anonymous) lifetime of self. But the lifetime of A::Iter<'_> can't be shortened because A is generic and the variance of A::Iter is not known.

In principle you could add a fn reborrow<'from: 'to, 'to>(Self::Iter<'from>) -> Self::Iter<'to> associated function (which would only be implementable for covariant Iter) to trait Set<T> and use that to convert the lifetime. However when I tried that it did not resolve all the lifetime issues, so perhaps variance is not the only problem here.

Note that you do not need PhantomData because T is used inside Difference (implicitly, as A::Iter is desugared to <A as Set<T>>::Iter).

Also, note that the duplication of Iter and iter inside ToIter and Set can be removed by making ToIter<T> a supertrait of Set<T>.

2 Likes
3

Traits used to have variance but this was ditched due to... implementation problems? It's unclear to me, really. Anyway, the RFC was never updated and the invariance of trait parameters is under-documented IMO.

I tried to work around it for your case by adding this method to Set<T> (as @trentj suggested):

fn reborrow<'outer: 'inner, 'inner>(iter: Self::Iter<'outer>) -> Self::Iter<'inner>;

However, when trying to use it like so:

    fn iter<'s>(&'s self) -> Self::Iter<'s> {
        let a = A::reborrow::<'a, 's>(self.a.clone());
        let b = &self.b;
        Difference { a, b, _p: PhantomData }
    }
I get this weird error (mentioning `Sized`) which probably deserves a bug report: 
   Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
  --> src/main.rs:93:13
   |
93 |         let a = A::reborrow::<'a, 's>(self.a.clone());
   |             ^ lifetime mismatch
   |
   = note: expected type `Sized`
              found type `Sized`
note: the lifetime `'s` as defined on the method body at 92:13...
  --> src/main.rs:92:13
   |
92 |     fn iter<'s>(&'s self) -> Self::Iter<'s> {
   |             ^^
note: ...does not necessarily outlive the lifetime `'a` as defined on the impl at 81:6
  --> src/main.rs:81:6
   |
81 | impl<'a, T: Hash + Eq, A: Set<T>, B: Set<T>> ToIter<T> for Difference<'a, T, A, B>
   |      ^^

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

So I forged ahead with this covariant-expressing trait:

// Basically `Into` but coherence makes that unusable here
trait Shorten<Covar> {
    fn shorten(self) -> Covar;
}

impl<'outer, 'inner, T, A, B> Shorten<Difference<'inner, T, A, B>> for Difference<'outer, T, A, B>
where
    A: Set<T>,
    B: Set<T>,
    'outer: 'inner,
{
    fn shorten(self) -> Difference<'inner, T, A, B> {
        let Difference { a, b, .. } = self;
        Difference {
            a: A::reborrow(a),
            b: &*b,
            _p: PhantomData,
        }
    }
}

And that apparently works around the error from earlier:

    // compiles
    fn iter<'s>(&'s self) -> Self::Iter<'s> {
        let a = self.a.clone();
        let b = &self.b;
        let diff: Difference<'a, T, A, B> = Difference { a, b, _p: PhantomData };
        let diff: Difference<'s, T, A, B> = diff.shorten();
        diff
    }

Playground. Notes:

  • I changed some other minor(?) things like some ToIter bounds
  • I added more lifetimes than necessary probably and didn't bother cleaning that up (or anything else really) after finding an apparent solution
  • Nothing implements Set<T> in this example so maybe this isn't even really a solution
  • None of the other suggestions were applied
  • The weird error version is still in there, commented out
3 Likes
4

Filed #89352.

5

Thank you both for your responses.

Kinda weird that this works:

use core::marker::PhantomData;

#[derive(Debug)]
pub struct Value<'a> {
    _p: PhantomData<&'a str>,
}

impl<'a> Value<'a> {
    pub fn new() -> Self {
        Self { _p: PhantomData }
    }
}

fn coerce<'longer, 'shorter>(value: Value<'longer>) -> Value<'shorter>
where
    // this bound should gurantee that 'longer outlives 'shorter
    'longer: 'shorter,
{
    value
}


fn main() {
    let value: Value<'static> = Value::new();
    
    {
        let shorter = coerce(value);
        dbg!(shorter);
    }
}

but this does not work:

#![feature(generic_associated_types)]

pub trait SomeTrait {
    type Associated<'a>;
}

fn coerce<'longer, 'shorter, V>(value: V::Associated<'longer>) -> V::Associated<'shorter>
where
    V: SomeTrait,
    // this bound may be redundant?
    V::Associated<'longer>: 'shorter,
    'longer: 'shorter,
{
    value
}

fn main() {}

Seems like this has not yet been thought of/implemented for gats?

6

This would be unsound, unless you can find some way to require that Associated<'a> be covariant in 'a (which is not currently possible in Rust, AFAIK)

Consider this code, which uses coerce to return a dangling reference to a local variable:

struct RcCell {}

impl SomeTrait for RcCell {
    type Associated<'long> = Rc<Cell<&'long i32>>;
}

fn oops<'short, 'long: 'short>(value: Rc<Cell<&'long i32>>) -> Rc<Cell<&'short i32>> {
    coerce::<RcCell>(value)
}

fn return_local_reference() -> &'static i32 {
    let local = 4;
    let ret: Rc<Cell<&'static i32>> = Rc::new(Cell::new(&10)); // static promotion
    oops(Rc::clone(&ret)).set(&local); // shortening the inner lifetime allows us to put `&'local` in a value typed `&'static`
    ret.get() // which is then returned from the function via the other Rc
}
2 Likes
7

You can require that the implementer provide a function for this:

pub trait SomeTrait {
    type Associated<'a>;
    fn shorten_lifetime<'a, 'b: 'a>(x: Self::Associated<'b>) -> Self::Associated<'a>;
}

impl SomeTrait for Foo {
    type Associated<'a> = &'a str;

    fn shorten_lifetime<'a, 'b: 'a>(x: Self::Associated<'b>) -> Self::Associated<'a> {
        x
    }
}

(credit for this approach goes to dtolnay, who mentioned it in an IRLO post)

8

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.