Lexical binding lifetime limitation


#1
use std::collections::HashMap;


fn main() {
    let vec = vec!["a", "b", "c", "c"];
    let mut hashmap: HashMap<&'static str, i32> = HashMap::new();
    let result = vec.into_iter()
        .map(|x| hashmap.entry(x))
        .last()
        .unwrap();
    println!("{:?}", result);
}

Here is the result: http://play.integer32.com/?gist=03fe294a6c319f93a4a47dd3bbcef12e&version=stable. hashmap's lifetime is long enough, but the compiler can not infer the lifetime automatically, and I have no ideas to make it passed the compile.


#2

What exactly are you trying to do? The compiler is complaining that it cannot figure out how to “autoref” (i.e. how to borrow) hashmap; it needs to borrow hashmap mutably for just the closure block to call entry but then the map closure is also returning the Entry object which is extending the mutable borrow beyond the closure - so hence conflicting requirements.

There’s probably a better way to accomplish your goal though, if you clarify it.


#4

I just want to return an entry outside closure.


#5

This case doesn’t have any practicability, I just want to understand why it not passed the compile checking and how lifetime checking works (the error message is “cannot infer an appropriate lifetime for autoref”).


#6

I have found that Entry object holds a mutable borrow to hashmap, but hashmap object’s lifetime is long enough to allow returning Entry object to top-level.


#7

Yeah, the hashmap is live for the entire chain, but recall that a mutable borrow is also a unique borrow. When you map to create an iterator adapter in your example, there’s a “temporary” mutable borrow inside the closure but then the mutable borrow needs to be extended beyond the closure because the value is returned. But, the rest of the iterator chain wouldn’t preserve that unique borrow aspect because as far as it’s concerned, it’s iterating (and consuming) an owned Vec only.

Don’t know if the above makes sense or clarifies, but let me know - maybe I can try harder :slight_smile:.


#8

I agree your explanation, I think the problem is: at present lifetime is tied to lexical, so closure’s mutable borrowing must be given back when leaving closure scope, but in this case, it is obvious that closure’s mutable borrowing can live across the closure.

So, I think that’s a limitation of the lexical binding lifetime, if lifetime checking and lexical are decoupled, the lifetime inferring can become more correct.


#9

I don’t think non-lexical lifetimes would help here (maybe I’m wrong though?). The problem here is that the Iterator API just doesn’t support the case. If you look at this signature:

fn next(&mut self) -> Option<Self::Item>

You see that nothing connects Self::Item with self. That has the benefit that all iterators can be collected. If you encounter Rust complaining about something related to the iterators, you should always ask yourself a question: Is it safe to collect the items of your “iterator”?.

In your case, the answer is no – (if you’d collect the iterator after map) you’d have possible two simultaneous mutable borrows to the hashmap entry for "c". The API that would work in your case is called a “Streaming Iterator” – it differs from the Iterator that the self is borrowed while the Item is alive – this prevents collect, but allows your case. Unfortunately, there’s no such thing in std, although I think there’s a crate for that. The reason streaming iterators are not popular and not supported in std is that Rust is not expressive enough to implement they in a nice way – that would require feature called Associated Type Constructors (you can find an RFC for that):

trait StreamingIterator {
    type Item<'a>;
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

Of course, your particular problem could be solved by swapping the order map and last, but I guess the code here is just an example.


#10

That’s an excellent explanation.


#11

I think if I fixed liftetime trouble, finally I would get an error as you explanation. But at present, according to compiler giving error messages, it is another problem I think.


#12

I am sure that if I call collect collector, I will get this error: two entry objects borrowed multiple mutable reference, but last collector just return single entry object.


#13

Unfortunately, it doesn’t really matter. It’s a limitation of Iterator API that all iterators has to be collectable, always. Since collect (which calls FromIterator::from_iterator) is implemented for all types implementing Iterator (with no additional bounds), that means that all Iterators have to be collectible.

TL;DR: FnMut closure can’t return anything borrowed from its environment.
(FnOnce can though, so .last().map(...) works).

You’re right. I didn’t look closely at the error message. (my previous explanation is still somewhat valid though). The exact reason for the error message lies in the FnMut definition – if you look at the map method’s sigature, you’ll see that it takes a closure that implements FnMut. Now, the FnMut definition looks like this:

pub trait FnMut<Args> {
    type Output;
    fn call_mut(&mut self, args: Args) -> Self::Output;
}

(I’ve cleaned it up a little, here’s the real one)

Let’s call your closure Closure. Since it uses a hashmap mutably, you can imagine its definition to look like this:

struct Closure<'env> {
    hm: &'env mut HashMap<&'static str, i32>
}

impl<'env> FnMut<(&'static str,)> for Closure<'env> {
    type Output = Entry<'?, &'static str, i32>;
    fn call_mut(&mut self, (x,): (&'static str,)) -> Entry<'?, &'static str, i32> {
        self.hm.entry(x)
    }
}

You see that you don’t really know what to put as '? in the Entry's lifetime parameter. What you’d want in this case would be:

    fn call_mut<'a>(&'a mut self, (x,): (&'static str,)) -> Entry<'a, &'static str, i32>;

That means to tie the returned Entry's lifetime to lifetime of the self (remember that the self here refers to the closure itself). But this doesn’t fit the definition of FnMut. In the definition, the type Output has to be one single type, but in that call_mut<'a> signature, each call_mut returns a different type of Entry. I’m sorry if that’s getting too technical :slight_smile: Anyway, if your code would compile, that would mean your closure would be a valid FnMut, and you could easily cause violation of the “no two &muts” rule and other Bad Things.

I also want to add why swapping last and map works in this case (have you tried it?) – the Option::Map takes only FnOnce, which is defined like this:

pub trait FnOnce<Args> {
    type Output;
    extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
}

in this case, the FnOnce implementation can be desugared to:

impl<'env> FnOnce<(&'static str,)> for Closure<'env> {
    type Output = Entry<'env, &'static str, i32>;
    fn call_once(self, args: (&'static str,)) -> Entry<'env, &'static str, i32> { ... }
}

In this case it works, because the closure can be called at most once, so we can precisely define the Output type here, including the 'env parameter.


@vitalyd So that thing I said that with streaming iterators it would work was not entirely true. In addition to defining new StreamingIterator trait, Rust would also have to support yet another type of closure FnMutReturningBorrowFromEnvironment (and that closure could be used in StreamingIterator::map, but not in Iterator::map).


#14

Thank you, you give me a detailed and nice explanation.


#15

You mean to decouple the mutable borrow of self (iterator) from any borrow captured in the environment? Yeah, I think I know what you’re saying.