Issues setting lifetimes in functions of Traits

Question

I have a trait Atom that has many associated types, of which one is an owned version OP and the other is a borrow version O of essentially the same data. I have a function to_pow_view that creates a view from an owned version and I have an equality operator.

Below is an attempt:

pub trait Atom: PartialEq {
    // variants truncated for this example
    type P<'a>: Pow<'a, R = Self>;
    type OP: OwnedPow<R = Self>;
}

pub trait Pow<'a>: Clone + PartialEq {
    type R: Atom;
}

#[derive(Debug, Copy, Clone)]
pub enum AtomView<'a, R: Atom> {
    Pow(R::P<'a>),
}

#[derive(Debug, Copy, Clone, PartialEq)]
pub enum OwnedAtom<R: Atom> {
    Pow(R::OP),
}

pub trait OwnedPow {
    type R: Atom;

    fn some_mutable_fn(&mut self);

    fn to_pow_view<'a>(&'a self) -> <Self::R as Atom>::P<'a>;

    // compiler said I should add 'a: 'b
    fn test<'a: 'b, 'b>(&'a mut self, other: <Self::R as Atom>::P<'b>) {
        if self.to_pow_view().eq(&other) {
            self.some_mutable_fn();
        }
    }
}

impl<R: Atom> OwnedAtom<R> {
    // compiler said I should add 'a: 'b, why?
    pub fn eq<'a: 'b, 'b>(&'a self, other: AtomView<'b, R>) -> bool {
        let a: AtomView<'_, R> = match self {
            OwnedAtom::Pow(p) => {
                let pp = p.to_pow_view();
                AtomView::Pow(pp)
            }
        };

        match (&a, &other) {
            (AtomView::Pow(l0), AtomView::Pow(r0)) => l0 == r0,
        }
    }
}

// implementation

#[derive(Debug, Copy, Clone, PartialEq)]
struct Rep {}

impl Atom for Rep {
    type P<'a> = PowD<'a>;
    type OP = OwnedPowD;
}

#[derive(Debug, Copy, Clone, PartialEq)]
struct PowD<'a> {
    data: &'a [u8],
}

impl<'a> Pow<'a> for PowD<'a> {
    type R = Rep;
}

struct OwnedPowD {
    data: Vec<u8>,
}

impl OwnedPow for OwnedPowD {
    type R = Rep;

    fn some_mutable_fn(&mut self) {
        todo!()
    }

    fn to_pow_view<'a>(&'a self) -> <Self::R as Atom>::P<'a> {
        PowD { data: &self.data }
    }
}

fn main() {}

This code gives the error:

27 |     fn test<'a: 'b, 'b>(&'a mut self, other: <Self::R as Atom>::P<'b>) {
   |                     -- lifetime `'b` defined here
28 |         if self.to_pow_view().eq(&other) {
   |            ------------------
   |            |
   |            immutable borrow occurs here
   |            argument requires that `*self` is borrowed for `'b`
29 |             self.some_mutable_fn();
   |             ^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

I expect this to work, since the immutable borrow should be dropped right after the eq function evaluates.

Something in the setting of the lifetimes is wrong in this code, already in the equality function eq: I would expect that there is no relation between 'a and 'b; they should just live long enough to do the comparison. However, the compiler tells me that I should add 'a: 'b and I do not understand why. The same thing happened for the function test.

These problems lead me to believe that the lifetimes in to_pow_view are wrong, but no modification I tried made it work (except for removing the 'a lifetime on &'a self, but then the OwnedPowD does not compile anymore).

Link to playground

Can someone help understand what is going on?

Answer 1

Here's the point: you constrained Pow to be PartialEq. However, PartialEq is PartialEq<Self>. In other words, Pow<'a> only implements PartialEq<Pow<'a>> for the same 'a.

This is usually the case for any type with lifetime and PartialEq, so why does it always work but not here?

It usually works because if we compare T<'a> == T<'b>, the compiler can shrink the lifetimes to the shortest of the two and compare that.

However, Pow is a trait. Traits are invariant over their lifetime, in other words, it must stay exactly as is, not longer nor shorter. This is because they may be used with invariant types, for example Cell<&'a i32>. Here's an example of how it could be exploited if this was allowed:

use std::cell::Cell;

struct Evil<'a> {
    v: Cell<&'a i32>,
}

impl PartialEq for Evil<'_> {
    fn eq(&self, other: &Self) -> bool {
        // We asserted the lifetimes are the same, so we can do that.
        self.v.set(other.v.get());
        false
    }
}

fn main() {
    let foo = Evil { v: Cell::new(&123) };
    {
        let has_short_lifetime = 456;
        _ = foo == Evil { v: Cell::new(&has_short_lifetime) };
    }
    // Now `foo` contains a dangling reference to `has_short_lifetime`!
    dbg!(foo.v.get());
}

The above code does not compile, because Evil is invariant over 'a, but if it would, it would contain UB in safe code. For that reason, traits, that may contain types such as Evil, are also invariant over their lifetimes.

Because of that, the compiler cannot shrink the lifetime of other. It can shrink the lifetime of self.to_pow_view() (in test(), eq() is similar), because it doesn't really shrink it, it just picks a shorter lifetime for to_pow_view()'s self. But because PartialEq is only implemented for types with the same lifetime, it means that the Pow resulting from self.to_pow_view() must have the same lifetime of other. Because of that, (a) 'a must be greater than or equal to 'b, so we can pick 'b out of it, and (b) by comparing, we borrow self for potentially whole 'a, because it may be that 'a == 'b and therefore the comparison borrows self for 'a, so it is still borrowed immutably while we borrow it mutably for some_mutable_fn().

Once we understood the problem, we can think about the solution. Either we require that Pow is covariant over 'a (can be shrinked), or we require that it implements PartialEq<Pow<'b>> for any lifetime 'b. The first is impossible in Rust, but the second is possible:

pub trait Pow<'a>: Clone + for<'b> PartialEq<<Self::R as Atom>::P<'b>> {
    type R: Atom;
}

This triggers an error, because the automatically-derived PartialEq does not satisfy this requirement:

error: implementation of `PartialEq` is not general enough
  --> src/main.rs:73:10
   |
73 | impl<'a> Pow<'a> for PowD<'a> {
   |          ^^^^^^^ implementation of `PartialEq` is not general enough
   |
   = note: `PartialEq<PowD<'0>>` would have to be implemented for the type `PowD<'a>`, for any lifetime `'0`...
   = note: ...but `PartialEq` is actually implemented for the type `PowD<'1>`, for some specific lifetime `'1`

So we need to implement PartialEq manually:

impl<'a, 'b> PartialEq<PowD<'b>> for PowD<'a> {
    fn eq(&self, other: &PowD<'b>) -> bool {
        self.data == other.data
    }
}

And now it works.