The lifetime of the borrowed value is too long

[zeux]

I'm not sure of the correct bug title here, it's based on my limited understanding of the problem :)

I'm trying to write a DB wrapper with a cache. Here's a code sample with two variants of read() function, the DB is using a hash map as well for exposition.

use std::hashmap::HashMap;

#[deriving(Clone)]
struct Data {
    data: ~[u8]
}

struct DB {
    cache: HashMap<int, Data>,
    db: HashMap<int, Data>
}

impl DB {
    pub fn read1<'a>(&'a mut self, key: int) -> Option<&'a Data> {
        match self.cache.find(&key) {
            Some(data) => return Some(data),
            None => ()
        };

        match self.db.find(&key) {
            Some(data) => {
                let result: &Data = self.cache.find_or_insert(key, data.clone());

                Some(result)
            },
            None => None
        }
    }

    pub fn read2<'a>(&'a mut self, key: int) -> Option<&'a Data> {
        match self.cache.find(&key) {
            Some(data) => return Some(data),
            None => {
                match self.db.find(&key) {
                    Some(data) => {
                        let result: &Data = self.cache.find_or_insert(key, data.clone());

                        Some(result)
                    },
                    None => None
                }
            }
        }
    }
}

fn main() {
}

Both read1() and read2() fail to compile with the following error:

db.rs:22:36: 22:46 error: cannot borrow `(*self).cache` as mutable because it is also borrowed as immutable
db.rs:22                 let result: &Data = self.cache.find_or_insert(key, data.clone());
                                             ^~~~~~~~~~
db.rs:15:14: 15:24 note: second borrow of `(*self).cache` occurs here
db.rs:15         match self.cache.find(&key) {
                       ^~~~~~~~~~

Possibly a duplicate of #6393 (although read1 looked like it could solve the problem but did not).

[pnkfelix]

cc @nikomatsakis who is probably best person to address this. I suspect it is indeed a similar problem to that of #6393 (and also #6613, which has a bit more explanation that is probably relevant to this example).

[pnkfelix]

FYI I did try to rewrite your example in a way that would pass the borrow-checker, but I was not successful. I did not go so far as to attempt to layer it all atop a single invocation of self.cache.mangle(..), mainly because I don't think that is quite expressive enough to capture all the cases here, namely the one where we want a None from the db lookup to mean that no entry gets added to self.cache.

[nikomatsakis]

Interesting problem. The reason that read1 doesn't solve the problem is that the borrow scope is 'a, which encompasses the entire function body. I think this is the same as #6393, but it is more convincing than the example given there. At the moment I am not sure how to write this function except to do the less-efficient option of:

if self.cache.contains_key(&key) { return self.cache.get(&key); }

in place of your first match statement.

[pnkfelix]

@nikomatsakis One solution finally came to me today. Rather than try to generalize the borrow checker, we could instead generalize the hashmap API accordingly. In short, when in doubt, try Continuation-Passing-Style. :)

Three step plan:

1. Sketch a new CPS style function for hashmap API,
2. Use the CPS style function to implement the goal function,
3. Prove the CPS style function can itself actually be implemented.

The gory details:

1. We add (at least) one new function, find_or_fallback_with to hashmap.rs (and possibly also to the Map trait).
   Signature:

    pub fn find_or_fallback_with<'a,A,T>(
        &'a mut self,
        k: K,
        a: A,
        found: &fn(&K, &'a mut V, A) -> T,
        fallback: &fn(&'a mut HashMap<K, V>, &K, A) -> T) -> T;

The crucial detail is that, upon failure, we pass along the &'a mut ref to the hashmap along to the fallback, so that the closure can update it accordingly in that narrowed scope.

---

2. Skipping ahead to the fun stuff, here's what @zeux's function now looks like:

    pub fn read3<'a>(&'a mut self, key: int) -> Option<&'a Data> {
        self.cache.find_or_fallback_with(
            key,
            (),

            // found:
            |_key, data, _a| { let data : &'a Data = data; Some(data) },

            // fallback:
            |cache, _key, _a| {
                match self.db.find(&key) {
                    Some(data) => {
                        let result: &Data = cache.find_or_insert(key, data.clone());
                        Some(result)
                    },
                    None => None
                }
            })
    }

(We might clean this up via do or some such, not sure, my initial experiments with do did not look too great since the found closure is not quite trivial enough to be a single expression.)

---

3. Just to complete the whole picture, here is the find_or_fallback_with function we'd have to add to hashmap.rs:

(But its a direct adaptation of the existing mangle function; we'd presumably want to try to unify the two internally to hashmap.rs if possible.)

    pub fn find_or_fallback_with<'a,A,T>(
        &'a mut self,
        k: K,
        a: A,
        found: &fn(&K, &'a mut V, A) -> T,
        fallback: &fn(&'a mut HashMap<K, V>, &K, A) -> T) -> T {
        if self.size >= self.resize_at {
            // n.b.: We could also do this after searching, so
            // that we do not resize if this call to insert is
            // simply going to update a key in place.  My sense
            // though is that it's worse to have to search through
            // buckets to find the right spot twice than to just
            // resize in this corner case.
            self.expand();
        }

        let hash = k.hash_keyed(self.k0, self.k1) as uint;
        match self.bucket_for_key_with_hash(hash, &k) {
            TableFull => fail!("Internal logic error"),
            FoundEntry(idx) => {
                found(&k, self.mut_value_for_bucket(idx), a)
            }
            FoundHole(_) => {
                fallback(self, &k, a)
            }
        }
    }

(Obviously I did not need the accumulator A parameter for this example, but I figure better to follow the precedent set by mangle and include that here.)

[zeux]

My gut feeling is that this is not a problem of HashMap, but instead a problem of a borrow checker. CPS seems way less idiomatic, and this problem will occur in similar places (should all "containers" with find/insert include a CPS solution? Should I rewrite the function to use CPS if I need an extra caching layer?)

Right now I'm using the extra contains_key check; while it's possible to fix HashMap to not require the check, I'd rather see the read2() work. For me borrow checks add enough extra burden in terms of thinking about the code that the better borrowck works the happier I am.

[pnkfelix]

For me borrow checks add enough extra burden in terms of thinking about the code that the better borrowck works the happier I am.

In my opinion: this is the argument for the CPS solution. Complicating the borrow-checker rules would not solve the problem of it being hard to understand the reasoning of the borrow-checker. Conversely, the CPS solution (idiomatic or not), enables the borrow-checker (and thus the human being reasoning about the borrow checker), to explain the borrow checker's reasoning in terms of lexical scopes. (End of "In my opinion.")

Having said all that, I'm pretty sure that @nikomatsakis and others have made the argument in the past that we do want to support idioms much like the one zeux described. So we will see.

(My main goal was to prove to myself that one can still express the desired control flow here, given the appropriate library API.)

[zeux]

From my perspective (take everything that I'm saying with a grain of salt, I'm very new to Rust) it's about simplifying borrowck behavior (even if it requires complicating borrowck logic).

In the None arm, there is no accessible borrowed pointer that came from borrowing mut self. So for the user (me), it does not make much sense that the code does not compile.

I would go so far as to say that in the Some arm, removing the usage of the value should let us borrow mut self again - since in some cases it will be important (i.e. if I'm returning Option<(&Chunk, float)>, but I'm only interested in the float part in Some branch - I want to be able to borrow mut self again.

This is my opinion as a user; the call is obviously yours, but I hope the opinion is useful :)

[nikomatsakis]

This is definitely a dup of #6393, going to close.

[viesturz]

Please fix the Borrow checker. Do not add new collections methods just to deal with this.
I love the potential of borrows, we just need to make compiler smart(er).

The greatest benefit is that a simple match is easy to read and write.
Not so for a bunch of specific methods and their signatures to remember.