"Outlived by" bound for higher-ranked lifetimes

[apasel422]

The following code yields a compilation error:

trait Foo<'a> {
    fn foo(&'a mut self);
}

impl<'a, T: 'a> Foo<'a> for Vec<T> {
    fn foo(&'a mut self) {}
}

fn bar<F>(x: &mut F) where F: for<'a> Foo<'a> {
    x.foo();
}

fn main() {
    let a = ();
    let mut v = vec![&a]; //~  ERROR `a` does not live long enough
                          //~^ reference must be valid for the static lifetime
    bar(&mut v);
}

This is the correct behavior, as v clearly does not implement Foo<'a> for all 'a.

I would like to use something like the following instead, but there is no way to achieve it:

fn bar<'x, F>(x: &'x mut F) where F: for<'a outlived by 'x> Foo<'a> { ... }

[Stebalien]

Well, in this case you don't technically need the for:

trait Foo<'a> {
    fn foo(&'a mut self);
}

impl<'a, T: 'a> Foo<'a> for Vec<T> {
    fn foo(&'a mut self) {}
}

fn bar<'a, 'b: 'a, F>(x: &'a mut F) where F: Foo<'a> {
    x.foo();
}

fn main() {
    let a = ();
    let mut v = vec![&a];
    bar(&mut v);
}

[apasel422]

@Stebalien Try calling x.foo(); twice inside bar.

[Stebalien]

Good point. Really I think we want where clauses for higher ranked bounds but that gets ugly fast.

[apasel422]

Yes, full where clauses would also work here, as we could say where F: for<'a> Foo<'a> where 'x: 'a.

[bluss]

+1! I think this is exactly what I tried to express in a discussion on the user forum.

It's needed to express, for example, iterator-returning methods in a trait, in a way that allows composably passing down values that implement said trait and interchangeably mutate and use the trait's iterators. Any IntoIterator based solution requires holding a borrow from the moment you “enter“ the trait-abstraction-using section, which is only composable with read-only operations.

[apasel422]

@bluss Yes, that's the same thing. I definitely prefer the HKT approach for the iterator stuff and for my EntryMap trait, which was the original inspiration for me to file this issue.

[reem]

I've also just run into this limitation when trying to work with scoped threads.

Here's the real-world use case:

#[macro_use]
extern crate scopeguard; // for defer!, https://github.com/bluss/scopeguard
extern crate scoped_pool; // https://github.com/reem/rust-scoped-pool
use scoped_pool::{Scope, Pool};

#[derive(Default)]
pub struct Fs {
     blah: Vec<u8> // details
}

impl Fs {
    fn init<'fs>(&'fs self, scope: &Scope<'fs>) {
        // Pass off (self, scope) to an internal type which spawns a bunch of worker
        // threads that operate on self - this function does not block.
    }

    // Starts a threadpool, creates Fs, passes it to F, takes care to clean up on panic etc.
    fn run<F, R>(threads: usize, fun: F) -> R
    where F: for<'fs> FnOnce(&'fs Fs, &Scope<'fs>) -> R { // Problematic clause
         let pool = Pool::new(threads);
         defer!(pool.shutdown());

         let fs = &Fs::default();
         pool.scoped(move |scope| {
              fs.init(scope); // Start threadpool.
              defer!(fs.shutdown());
              fun(fs, scope)
         })
     }

     // Stops worker threads started by init
     fn shutdown(&self) { }
}

// The F: for<'fs> FnOnce(&'fs Fs, &Scope<'fs>) -> R bound is bad here, since it 
// doesn't properly bound 'fs (anything the closure tries to pass to scope.execute will 
// have to be 'static, since 'fs could be 'static under this clause). What we actually want 
// to do is add another lifetime ('a for instance) to the definition of fn run, then write:
// F: for<'fs> FnOnce(&'fs Fs, &Scope<'fs>) -> R + 'a where 'a: 'fs, which puts an
// upper bound on the 'fs lifetime that we can choose as the caller to run, allowing us
// to capture and use references of lifetime 'a within closures we pass to 
// scope.execute.

// EDIT to include a potential workaround that doesn't work either:
// We can't even get around this problem by taking another argument of some generic type
// T and injecting it into the closure (so it would take (T, &Fs, &Scope)), since we can't tell
// rustc that T: 'fs.

Let me know if something is unclear in the example, and I can attempt to clear it up.

EDIT: Added self-contained reproduction: https://gist.github.com/reem/c4ba083c624607f279e0

[nikomatsakis]

First, @apasel422 your original example can be written more simply by just removing the T: 'a bound from the impl:

trait Foo<'a> {
    fn foo(&'a mut self);
}

impl<'a, T> Foo<'a> for Vec<T> {
    fn foo(&'a mut self) {}
}

fn bar<F>(x: &mut F) where F: for<'a> Foo<'a> {
    x.foo();
}

fn main() {
    let a = ();
    let mut v = vec![&a];
    bar(&mut v);
}

The reason that this is OK is a bit subtle. Basically, you never needed the T: 'a for the impl itself. There are no references like &'a T in any of the types that appear in the impl header, and even if there were, the implied bounds rules would then let the impl assume that T: 'a.

impl<'a, T> Foo<'a> for Vec<T> { ... }

Now, you might be surprised that the method passes now that you have removed T: 'a:

    fn foo(&'a mut self) {}

but in fact this is fine, precisely because of implied bounds. Basically, we KNOW that T: 'a holds in the method body because the caller would not have been able to form the &'a mut Vec<T> reference otherwise.

I'm still working through @reem's example.

(Modulo rust-lang/rust#25860, which we really need to fix.)

[nikomatsakis]

OK, so @reem supplied me with this gist which helped me to understand his problem (though now that I grok it, his explanation is pretty clear).

Basically, the problem arises when you try to use the run API, like so:

fn foo() {
    let m = &::std::sync::Mutex::new(());
    Fs::run(12, |fs, scope| {
        scope.execute(move || {
            let _l = m.lock().unwrap(); // <-- error, lifetime doesn't live long enough
        });
}

The problem here is that, as @reem said, the closure is supposed to be able to handle scopes for any lifetime 'fs -- including e.g. 'static. So when we try to hand the scope scope a closure that closes over m, the lifetime on that closure can't outlive the body of foo -- it certainly can't live for 'static. So we wind up with an error:

src/lib.rs:44:22: 44:49 error: borrowed value does not live long enough
src/lib.rs:44         let mut m = &::std::sync::Mutex::new(());
                                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

You can workaround this problem by leveraging implied bounds yet again. The basic idea is to change the signature of Fs::run to include some extra "passthrough" state of type T:

    pub fn run<T, F, R>(shared: &mut T, threads: usize, fun: F) -> R
        where F: for<'fs> FnOnce(&'fs mut T, &'fs Fs, &Scope<'fs>) -> R
    {
        // ... same as before ... 
        pool.scoped(move |scope| {
            // ... same as before ... 
            fun(shared, fs, scope) // <-- now pass 3 arguments
        })
    }

Note that I am now passing in a shared reference &mut T, and I am passing that same reference onto the closure, which now takes three arguments. But I am telling the closure that this data has a lifetime &'fs mut T. So now, while the closure still doesn't know what 'fs is, it DOES know that T: 'fs, whatever it is. This type-checks here because run DOES know what 'fs is, and so it knows that the T lives long enough.

Now the caller can thread the reference to m through from the outer stack frame to the inner one like so:

        let mut m = &::std::sync::Mutex::new(());

        Fs::run(&mut m, 12, |m, fs, scope| {
            //  ^~~~~~       ^
            scope.execute(move || {
                let _l = m.lock().unwrap();
            });
        });

I highlighted the two changes. Basically we pass in &mut m and then we let that get passed to us. Now when we refer to m in the closure we are referring to this version that was given to us, and we know that it outlives 'fs.

So, this type checks, but it's obviously not ideal. As @reem said, it'd be nice if we could communicate to the closure some kind of bound on 'fs -- I am effectively doing this here, but it requires an extra argument. Another way to express the bound that @reem wanted would be something like for<'fs, where F: 'fs> F: FnOnce(...).

I am pretty nervous about trying to add general where clauses to for types etc, though it could be very useful in dealing with #25860 and a few other things. But it definitely opens the door to a lot of complexity, both for users in terms of surface syntax etc and in the implementation. So I want to ponder @reem's example in particular to think if I see another route (at least in the short term).

I also ran into that limitation when wanting to write a library producing trait objects that will typically work on a single type provided by the user and known at compilation time.

A simple example would be:

// My crate
pub trait MyTrait { ... }
pub fn generate_closure<C: MyTrait>() -> Box<for <'a> Fn(&'a C) { ... }

// User crate
struct Context { ... }
impl MyTrait for Context { ... }

fn main() {
    // Early in program
    let closure = generate_closure::<Context>();

    // Later on
    let context = Context::new();
    closure(&context);
}

This currently only works if Context can live longer than the closure (typically means 'static).

Your proposed solution would I think fix it, as I could write Box<for<'a, where C:'a> Fn(&'a C)>

[nikomatsakis]

@Vaelden can you maybe spell out the example a bit more? I'd like to gather up some more concrete examples, since the "lazy WF" approach we take for handling the C: 'a bounds often means that things people think would not work in fact do work (for example, what you wrote seems like it ought to work, so I am guessing that there are more details I am not considering).

[lambda]

@nikomatsakis There are threads on Reddit and StackOverflow where @Vaelden first tried asking about this, with a minimized example that demonstrate the problem:

struct Parameter<'a> {
    s: &'a str,
}

fn main() {
    let closure = generate_closure_gen();
    let string = String::from("Hello World!");
    let parameter = Parameter { s: &string }; // Error: string does not live long enough
    closure(&parameter);
}

// This one works fine
// Desugared version for Box<Fn(&Parameter)>
fn generate_closure() -> Box<for <'a, 'r> Fn(&'r Parameter<'a>)> {
    Box::new(|c: &Parameter| {})
}

// This one gives lifetime errors
fn generate_closure_gen<C>() -> Box<Fn(&C)> {
    Box::new(|c: &C| {})
}

If you move the declaration of closure to after the declaration of string, it works fine; or if you replace generate_closure_gen with the concrete generate_closure it works fine; but I don't think anyone involved in those threads has been able to find a way to get generate_closure_gen to work properly.

Indeed. My understanding was that for my generate_closure_gen function to work like the concrete version, I would need to write something like this:

fn generate_closure_gen<C>() -> Box<for <'r, 'a where C: 'a> Fn(&'r C)>

[nikomatsakis]

On Wed, Mar 02, 2016 at 01:16:05PM -0800, Brian Campbell wrote:

If you move the declaration of closure to after the declaration of string, it works fine; or if you replace generate_closure_gen with the concrete generate_closure it works fine; but I don't think anyone involved in those threads has been able to find a way to get generate_closure_gen to work properly.

I see. This is actually quite a separate issue. The problem here is
that the type C appears free in the second case, but in the first
function it is a type that includes bound regions ('b,
specifically). Put another way, when you reference
generate_closure_gen, you must instantiate C with some specific
type, and that type must in turn outlive closure. Now you wind up
with errors because string does not outlive closure -- this is why
reordering things helps. But in the case of generate_closure, the
two regions are "late-bound", meaning that they are not specified
until the closure is called.

To type this example, what you would really need is something more
sophisticated; ideally you'd have higher-ranked types. We can't have
them in their full generality, because that is not compatible with
monomorphization, but maybe one could imagine some subset that
would work for types that only vary in their lifetimes.