Inferred struct lifetime bounds result in rejection of valid lifetimes

davidhalter commented 2 years ago

I have skimmed about 100+ "similar" issues here and could find one that matches this issue, so apologies if this was already reported. The issue that seems most similar is this one: https://github.com/rust-lang/rust/issues/87241.

I have tried to reduce this lifetime issue as much as possible to the essentials, but it's unfortunately still a bit of code:

fn main() {
}

struct Impl<'db> {
    some_trait: &'db dyn Trait<'db>,
}

impl<'db> Trait<'db> for Impl<'db> {
    fn foo(&self, s: &mut State<'db, '_>) {
        Car::new(s).debug(s, &mut |s| {
            self.some_trait.foo(s);
        });
    }
}

trait Trait<'db> {
    fn foo(&self, s: &mut State<'db, '_>);
}

struct State<'db, 'a> {
    car: &'a Car<'db>,
}

struct Car<'db> {
    foo: &'db u128,
}

impl<'db> Car<'db> {
    fn new(s: &mut State<'db, '_>) -> Self {
        todo!()
    }

    fn debug(
        &self,
        s: &mut State<'db, '_>,
        callable: &mut impl Fn(&mut State<'db, '_>),
    ) {
        todo!()
    }
}

I expected this to pass the borrow checker (cannot infer an appropriate lifetime...; see below). The problem could be that 'db: 'a is inferred for struct State, because if you rewrite that struct into this piece of code:

struct State<'db, 'a> {
    car: &'db Car<'db>,
    bar: &'a Car<'a>,
}

the borrow checker is happy. However the borrow checker is also happy if I'm using some_trait: &'db Impl<'db>, so it feels like this is really an issue and not me misunderstanding lifetimes. I have tried various approaches like using HRTBs and a lot of complicated where: with explicit lifetimes, but nothing helped.

I run a lot of similar code that passes, but this one doesn't, because the closure is using self.some_trait and not something given by the closure (in which case everything would work great!).

So again, sorry for the "long" code piece, but I have tried to reduce it for hours and couldn't really get further. I hope I do not waste your time with this.

The actual long-form error:

$ RUST_BACKTRACE=1 ca
rgo build
   Compiling zuban_python v0.1.0 (/home/dave/source/rust/issues/lifetimev4/zuban_python)
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> zuban_python/src/lib.rs:11:29
   |
11 |             self.some_trait.foo(s);
   |                             ^^^
   |
note: first, the lifetime cannot outlive the lifetime `'db` as defined on the impl at 8:6...
  --> zuban_python/src/lib.rs:8:6
   |
8  | impl<'db> Trait<'db> for Impl<'db> {
   |      ^^^
note: ...so that the declared lifetime parameter bounds are satisfied
  --> zuban_python/src/lib.rs:11:29
   |
11 |             self.some_trait.foo(s);
   |                             ^^^
note: but, the lifetime must be valid for the anonymous lifetime #2 defined on the body at 10:35...
  --> zuban_python/src/lib.rs:10:35
   |
10 |           Car::new(s).debug(s, &mut |s| {
   |  ___________________________________^
11 | |             self.some_trait.foo(s);
12 | |         });
   | |_________^
note: ...so that the expression is assignable
  --> zuban_python/src/lib.rs:11:33
   |
11 |             self.some_trait.foo(s);
   |                                 ^
   = note: expected `&mut State<'db, '_>`
              found `&mut State<'_, '_>`

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

Meta

rustc --version --verbose:

rustc 1.56.0 (09c42c458 2021-10-18)
binary: rustc
commit-hash: 09c42c45858d5f3aedfa670698275303a3d19afa
commit-date: 2021-10-18
host: x86_64-unknown-linux-gnu
release: 1.56.0
LLVM version: 13.0.0

Patrick-Poitras commented 2 years ago

@rustbot label +A-lifetimes

BGR360 commented 2 years ago

Looks like this is due to the invariance of &mut State<'db, 'a> with respect to 'db and 'a.

Variance is a somewhat advanced and confusing topic in Rust. I recommend you give this page a read: https://doc.rust-lang.org/nomicon/subtyping.html#variance. In short, though, mutable references have stricter effects on the pointee type's associated lifetime(s) than immutable references do.

I tested this hypothesis by changing all of the &mut State to &State, and it compiled. Playground

Knowing this, my next thought was that you need to put an explicit lifetime in place of at least one of those '_ placeholders. And indeed, this is the problematic line:

fn debug(
    &self,
    s: &mut State<'db, '_>,
    callable: &mut impl Fn(&mut State<'db, '_>),  // <-----
)

As written, I think that line really translates to:

callable: &'1 mut impl Fn(&mut State<'db, '1>)

Because of the invariance of &mut State<'db, '1> with respect to '1, the &mut Fn and the &Car inside State need to have exactly the same lifetime; the former can't just be greater than or equal to the latter. This is an impossible constraint to satisfy.

That is my understanding, at least. I don't claim to be an expert on this.

To fix it, you need to put an explicit lifetime in place of '_ there:

fn debug<'a>(
    &self,
    s: &mut State<'db, '_>,
    callable: &mut impl Fn(&mut State<'db, 'a>),
)

Playground

As far as I know, this is expected behavior and not a bug. I do think, though, that there is a lot of improvement that we can make to these diagnostics when invariance is at play. It is absolutely a stumbling block, and not just for beginners.

@rustbot label -C-bug +C-enhancement +A-diagnostics +D-newcomer-roadblock +D-terse +D-confusing

Aaron1011 commented 2 years ago

See https://github.com/rust-lang/rust/pull/89336 for some work towards improving diagnostics around variance

danielhenrymantilla commented 2 years ago

Reduction:

struct WithLt<'lt> (
    &'lt (),
);

impl<'db> WithLt<'db> {
    fn check (_: impl FnOnce(*mut &'_ &'db ()))
    {}
}

fn _for<'db> (
    f: impl FnOnce(*mut &'_ &'db ()),
)
{
    WithLt::<'db>::check(move |s| f(s))
}

Playground

Can be further "reduced" to:

struct WithLt<'lt> (
    &'lt (),
);

impl<'db> WithLt<'db> {
    fn check (f: impl FnOnce(*mut &'_ &'db ()))
    {
        Self::check(move |s| f(s))
    }
}

Using f rather than move |s| f(s) circumvents the issue, so it's a matter of the literal closure there being given an incorrect HRTB signature, I'd say. Variance (or lack thereof) just makes it easier (harder) to circumvent the issue, but there is a genuine issue here.

danielhenrymantilla commented 2 years ago

Curiously, uncommenting the following turbofish annotation fixes the reduced example:

struct WithLt<'lt> (
    &'lt (),
);

impl<'db> WithLt<'db> {
    fn check<'lt> (f: impl FnOnce(*mut &'_ &'lt ()))
    where
        'static : 'lt, // make it turbofishable
    {
        Self::check
            // ::<'lt> /* compilation passes if uncommented */
        (move |s| f(s))
    }
}

danielhenrymantilla commented 2 years ago

Thanks to this, a HRTB-signature-nudging funnel can be written, which palliates the issue:

+ fn funnel<'lt> (f: impl Fn(&mut State<'lt, '_>))
+   -> impl Fn(&mut State<'lt, '_>)
+ where
+     'static : 'lt, // make it turbofishable
+ {
+     f
+ }

  impl<'db> Trait<'db> for Impl<'db> {
      fn foo(&self, s: &mut State<'db, '_>) {
-         Car::new(s).debug(s, &mut (|s| {
+         Car::new(s).debug(s, &mut funnel::<'db>(|s| {
              self.some_trait.foo(s);
          }));
      }
  }

Playground

BGR360 commented 2 years ago

@danielhenrymantilla can you elaborate more on how you arrived at that reduction? I'm a little lost as to why you changed the things you did and how they result in the same problem.

Also, how is that 'static: 'lt bound helpful? Doesn't that restrict 'lt to living at least as long as 'static?

danielhenrymantilla commented 2 years ago

The 'static : 'lt is a trivial bound, since it means that 'static needs to live at least as long as 'lt, which it obviously always does. It would have been similar to a 'lt : 'lt bound, whereby we would have constrained 'lt to being greater than or equal to 'lt.

So, inside that function, it does not add any property nor restrict anything. It does, however, allow callers to turbofish that lifetime parameter (for "reasons" related to early bound vs late bound lifetimes), which is a nice thing to have for these "investigations", since sometimes the diagnostics can be improved. In this instance it happened to be serendipitous, since it allowed to feature a workaround!

Regarding the reduction, it's hard to describe the steps that lead there: since literal closure expressions are known to sometimes be given incorrect signatures w.r.t. lifetime quantification, I suspected that part since the beginning, and just kept stripping all the other elements, as well as simplifying the types to involve the same variance and drop glue.

davidhalter commented 2 years ago

@danielhenrymantilla Wow, thanks a lot for coming up with this. I still have to work on a funnel that works for my own use case, but this is at least a good way to investigate this further.

since literal closure expressions are known to sometimes be given incorrect signatures w.r.t. lifetime quantification

Isn't that a bug though? It just feels wrong that you have to wrap a closure in such a complex way. I understand that this might not be something that is immediately fixed, but it still feels like a compiler bug to me.

davidhalter commented 2 years ago

@BGR360 I hope you do not mind me removing the diagnostic labels. The reason for this is that @danielhenrymantilla brought up the funnel, which kind of proves that there is something wrong here.

It does, however, allow callers to turbofish that lifetime parameter

@danielhenrymantilla It seems like that this is not necessary for the turbofish syntax?! If I remove the 'static bound it still compiles. I'd still be interested in a more thorough explanation, because I feel like you have a better understanding about this than me.

@rustbot label +C-bug -C-enhancement -A-diagnostics -D-newcomer-roadblock -D-terse -D-confusing

danielhenrymantilla commented 2 years ago

@davidhalter you're right, the 'static : "hack" is not needed here; if I had to guess it would be due to the impl Fn(… 'lt …) which already act as making Rust consider the 'lt parameter is "non trivial" which is when it gets to be early-bound (rather than late-bound), which allows turbofishing it:

Here is a Playground showcasing differences between early-bound and late-bound lifetime parameters
Here is a Playground showcasing that impl Fn(…'lt…) seems to act as a "bound regarding 'lt" which results in that 'lt parameter being early-bound (and thus) turbofishable.

So, indeed, I did not need to add that "extra dummy bound" 👍

rust-lang / rust

Inferred struct lifetime bounds result in rejection of valid lifetimes #91942

Meta