Mutable Borrow Lasts Forever when struct contains fn(&'a T) -> &'a T

[agrif]

I ran in to this snippet of code that the borrow checker doesn't like, and I can't work out why:

struct Foo<'a> {
    func: fn(&'a ()) -> &'a (),
}

impl<'a> Foo<'a> {
    fn bar(&'a mut self) {}
}

fn main() {
    let mut f = Foo { func: |x| x };
    f.bar();
    f.bar();
}

Playground link.

The mutable borrow when calling f.bar() seems to last forever, and I can't convince rust otherwise. What's going on here? I suspect it has something to do with the fact that Foo<'a> is invariant over 'a, but I can't figure out what sort of mischief Foo could get up to that means a mutable borrow lasts forever.

FWIW, this came up in the context of trying to write an iterator that parses structs out of an owned byte vector with a nom parser. Here's a slightly more detailed mockup of the problem as it occurs there.

[Yandros]

• Your Foo<'a> struct is invariant over its lifetime parameter 'a, which is a fancy way of saying that 'a cannot be shrunk nor expanded on usage.

• On fn bar(self: &'a mut Self), you are requiring:

  • an exclusive borrow over *self : Foo<'a>,

  • that this borrow last for (span until the end of) the lifetime 'a (instead of it spanning over some anonymous / unconstrained lifetime / free lifetime parameter).

This is problematic since by doing that, the lifetime of the borrow from the first call to bar is equal to some lifetime 'a, and so is that of the second call. And since two things equal to a same third thing are equal between themselves (or "equality is transitive (and symmetrical)"), this means that both calls have a borrow that span over this same lifetime. They thus overlap, which contradicts the exclusivity stated by the usage of &mut exclusive references.

So the main solution is to start fixing that method signature. A good rule of thumb is to avoid naming the lifetimes explicitely, unless necessary, and when naming those, to use:

• distinct names at each position unless the compiler complains;

• expressive names to understand what's going on ('a is thus a poor lifetime name, sadly that anti-pattern is promoted by most official docs).

  impl<'a> Foo<'a> {
-     fn bar(&'a mut self) {}
+     fn bar(&'_ mut self) {}
  }

• which is sugar for

  fn bar<'bar> (&'bar mut self) {}
  

  That is, a free / unconstrained / etc. lifetime parameter that will thus span over the call to .bar() itself (hence my naming it 'bar).

Finally, although this is a bit more advanced, the definition of Foo and func is over-constraining too.

• Example:

  struct Foo<'a> {
      func: fn(&'a ()) -> &'a (),
  }
  
  impl Foo<'_> {
      fn example (&self)
      {
          let local = ();
          (self.func)(&local); // Error
      }
  }
  

  • Playground

• The solution is to use what is called a "higher-order lifetime", which, although with a scary name, and more subtle semantics, can, be very easily achieved by, again, not naming the lifetime

  struct Foo {
      func: fn(&'_ ()) -> &'_ (),
  }
  

[mbrubeck]

Your more detailed example is tricky. I think you really do need for<'a>, because otherwise the closure can only work for exactly one lifetime, and that lifetime must span all the calls to next. But you also need the return type T to vary with the input lifetime.

Your example compiles if you replace T with &T in the return type: Playground. (I also had to make parser into a function rather than a closure because of some type inference problem I don't fully understand.) However, I assume that this will not work in your real-world code because you will sometimes need to return types that are not references to the input.

Maybe generic associated types would help here.

[agrif]

@Yandros Ah, that makes sense. The error is because lifetime 'a is tied specifically to the type of f, and can't vary between calls to f.bar(), so they will always overlap. That makes sense, although it looks like it doesn't actually have anything to do with invariance like we both guessed.

Unfortunately your suggested fixes to the code won't help in the non-toy version of this code I'm working on. Check out the more detailed playground link to see why -- I really really want a universally-quantified lifetime on func, but I don't think I can do it that way if one of the return types needs to depend on that lifetime. And if I have to name a lifetime there, I also have to re-use it in bar() (or next()) or I can't ever call it, as in your example.

[agrif]

@mbrubeck You're right: in my real code I need T to unify with something like PacketHeader<'a>, not just &[u8]. I was hoping to be able to do this without nightly features, and even if GATs help, that means I need to make a whole trait and implement it for each struct I want to parse.

From @Yandros's observation that the borrow problem is because the lifetime is fixed inside the type of Foo, I've come up with a reasonable solution for the detailed example. Mostly it involves moving the lifetime (and T that depends on it) into the call to next, not the type itself. Now it is allowed to change each time it's invoked.

One thing that I still don't understand: on line 37/38, this code works fine with functions, but not closures. I think this is exactly the problem @mbrubeck ran into. It won't matter for my specific use case, but it is confusing...

[mbrubeck]

@agrif

One thing that I still don't understand: on line 37/38, this code works fine with functions, but not closures.

I think this is related to these bugs about lifetime elision/inference and closures:

Can’t declare lifetime for closure that returns a reference

Confusing lifetime error with closure

Annotating higher-ranked lifetimes on closures is arduous

[Yandros]

The following works:

/// With GATs this would be:
/// ```
/// trait WithLifetime { type T<'__>; }
/// ```
trait WithLifetime<'__> {
    type T;
}

/// Convenience trait alias.
trait TakesLifetime
    : for<'any> WithLifetime<'any>
{
    const __: () = {
        impl<T : ?Sized> TakesLifetime for T where Self
            : for<'any> WithLifetime<'any>
        {}
    };
}


// iterator that parses data from an owned vector, one at a time
struct ParseFrom<F, T : TakesLifetime> {
    parser: F,
    data: Vec<u8>,
    offset: usize,
    marker: ::core::marker::PhantomData<fn(&()) -> <T as WithLifetime<'_>>::T>,
}

// need to specify lifetime 'a manually in F, so that T can also use it
// (otherwise we'd get forall<'a>, which is not what we want!)
impl<'a, F, T : TakesLifetime> ParseFrom<F, T>
where
    F : Fn(&'a [u8]) -> Option<(&'a [u8], <T as WithLifetime<'a>>::T)>,
{
    fn next (self: &'a mut Self)
      -> Option<<T as WithLifetime<'a>>::T>
    {
        if let Some((rest, x)) = (self.parser)(&self.data[self.offset..]) {
            self.offset += self.data.len() - rest.len();
            Some(x)
        } else {
            None
        }
    }
}

// simple parser: take n-byte slices
fn take<const COUNT: usize> (input: &'_ [u8])
  -> Option<(&'_ [u8], &'_ [u8])>
{
    if input.len() >= COUNT {
        Some((&input[COUNT ..], &input[0 .. COUNT]))
    } else {
        None
    }
}

fn main ()
{
    /// `&Referee`
    struct Ref_<Referee : ?Sized + 'static>(
        ::core::marker::PhantomData<Referee>,
    );
    impl<'lt, Referee : ?Sized> WithLifetime<'lt> for Ref_<Referee> {
        type T = &'lt Referee;
    }

    let mut p = ParseFrom::<_, Ref_<_>> {
        // take 1-byte slices
        parser: take::<1>,
        data: vec![42, 27, 0, 0, 0],
        offset: 0,
        marker: std::marker::PhantomData,
    };
    
    println!("parsed: {:?}", p.next());
    println!("parsed: {:?}", p.next());
}

• Playground (stable Rust version)

• Also note that at this point the 'a lifetime in the trait impl should be usable in higher-order position (impl<F, T>… where F : for<'a> …), but when that many higher-order lifetimes and bounds are involved, the current trait solver gets confused and starts spitting out non-sense / refusing to compile correct code, so it turns out that having the 'a lifetime not be higher-order in the impl is a convenient way to circumvent that .