A lifetime understanding in the HashMap and match pattern

#1

I just read Niko Matsakis’s blog

Non-lexical Lifetimes: Introduction

I can not understand well the following code, even Niko gives some explain.

I just do not understand well why in the first function, the borrow in the match will last until end of the function.

Can someone give more detail explain?


fn get_default1<'m,K,V:Default>(map: &'m mut HashMap<K,V>,
                                key: K)
                                -> &'m mut V {
    match map.get_mut(&key) { // -------------+ 'm
        Some(value) => return value,       // |
        None => { }                        // |
    }                                      // |
    map.insert(key, V::default());         // |
    //  ^~~~~~ ERROR (still)                  |
    map.get_mut(&key).unwrap()             // |
}   



fn get_default2<'m,K,V:Default>(map: &'m mut HashMap<K,V>,
                                key: K)
                                -> &'m mut V {
    if map.contains(&key) {
    // ^~~~~~~~~~~~~~~~~~ 'n
        return match map.get_mut(&key) { // + 'm
            Some(value) => value,        // |
            None => unreachable!()       // |
        };                               // v
    }

    // At this point, `map.get_mut` was never
    // called! (As opposed to having been called,
    // but its result no longer being in use.)
    map.insert(key, V::default()); // OK now.
    map.get_mut(&key).unwrap()
}
#2

The current borrowchecker algorithm doesn’t understand branching, and early return is a form of branching. Consider this rewrite:

match map.get_mut(&key) {
    Some(v) => v,
    None    => {
        map.insert(key, V::default());
        map.get_mut(&key).unwrap()
    }
}

The borrowchecker treats these as essentially the same, because it just doesn’t understand the idea of a lifetime with multiple exits. Every lifetime has exactly one point it begins and one point it ends, and returning a variable with a lifetime means that lifetime must last until the end of the function.

#3

Thanks !

the algorithm is not obviously for the beginner, is there any material about the borrowchecker algorithm?

#4

I think that unfortunately the algorithm is not meant to be understandable by beginners. For one thing, I certainly don’t understand how it works for real. However in practice I find that my intuition about the lifetimes aligns pretty well with the implementation (this case is one notable exception). So, in some sense, you don’t need to understand lifetimes to use Rust.

There are some docs in the borrowck and regionck compiler modules, but I don’t know if they are up to date.

#5

Yeah. This one confuses me, the other useage of lifetime seems Ok now.

Thanks again!

#6

If you can imagine how you would rewrite the function as a single expression without changing its control flow, you can sort of see how the lifetimes shake out. Some important facts about the way lifetimes work right now that are pobably not obvious:

  • They always have a single entrance and exit (the point at which they begin and end)
  • The relationship between two lifetimes is always either: a) one lifetime completely contains the other (begins before it and ends after it), or b) they do not overlap at all. A lifetime can’t start in the middle of another one and then outlive it.