4

I have a problem with self borrowing in a match expression:

fn add_once(&'t mut self, p_name: &'t str) -> Box<Element> {
    match self.get(p_name) {
        Some(x) => Box::new(*x),
        None => self.add(p_name),
    }
}

The signature of the get() and add() functions are:

fn get(&self, p_name: &str) -> Option<&Element>
fn add(&'t mut self, p_name: &'t str) -> Box<Element>

The compiler refuses this code:

error[E0502]: cannot borrow `*self` as mutable because it is also borrowed as immutable
  --> src/main.rs:38:21
   |
36 |         match self.get(p_name) {
   |               ---- immutable borrow occurs here
37 |             Some(x) => Box::new(*x),
38 |             None => self.add(p_name),
   |                     ^^^^ mutable borrow occurs here
39 |         }
40 |     }
   |     - immutable borrow ends here

I get that, but I don't see how I can rewrite the match expression.

In a related question, it was solved by having the match return a value and then calling the function. However, that doesn't work here because the meaning of the conditional is not to choose a value but selectively execute an action.

The full code sample is below:

struct Element<'e> {
    name: &'e str, 
}

impl<'e> Element<'e> {
    fn new(p_name: &str) -> Element {
        Element { name: p_name }
    }
}

struct Top<'t> {
    list: Vec<Element<'t>>,
}

impl<'t> Top<'t> {
    fn new() -> Top<'t> {
        Top { list: vec![] }
    }

    fn get(&self, p_name: &str) -> Option<&Element> {
        for element in self.list.iter() {
            if element.name == p_name {
                return Some(element);
            }
        }
        None
    }

    fn add(&'t mut self, p_name: &'t str) -> Box<Element> {
        let new_element = Box::new(Element::new(p_name));
        self.list.push(*new_element);
        return new_element;
    }

    fn add_once(&'t mut self, p_name: &'t str) -> Box<Element> {
        match self.get(p_name) {
            Some(x) => Box::new(*x),
            None => self.add(p_name),
        }
    }
}

fn main() {
    let mut t = Top::new();
    let plop1 = t.add_once("plop1");
    let plop2 = t.add_once("plop1");
}
Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
Tifauv'
  • 81
  • 1
  • 8
  • Even without the mutable error, you would still have a type-unification issue. Both branches of `match` should return the same type. Similarly, I am surprised that `add` compiles as you first `push` into the vector and then return; however it seems to me that pushing into the vector should invalidate (move) the content of the box... Shouldn't `add` return `&Element` and the result of `add_once` be `&Element` ? – Matthieu M. Nov 13 '14 at 12:17
  • @MatthieuM., it works because `Element` is `Copy`, so `*new_element` returns a copy of the element. – Vladimir Matveev Nov 13 '14 at 12:22
  • @VladimirMatveev: ah yes, I had forgotten `Copy` was not yet opt-in. Still, it seems to me this indicate a design flaw: `Top` seems like it should be generic, and work on non-`Copy` types. – Matthieu M. Nov 13 '14 at 12:27
  • I'm very new to Rust, so there are probably design errors. Top should indeed work on non-`Copy` types. – Tifauv' Nov 13 '14 at 15:55
  • @MatthieuM. Initially, I wanted `add` and `add_once` to return `&Element`, but couldn't get it working. – Tifauv' Nov 13 '14 at 16:02

1 Answers1

3

Let's fix the design issues first. The main issue is lifetime conflation:

struct Top<'t> {
    list: Vec<Element<'t>>,
}

impl<'t> Top<'t> {
    fn add(&'t mut self, p_name: &'t str) -> Box<Element>;
    fn add_once(&'t mut self, p_name: &'t str) -> Box<Element>;
}

You assert that self should live at least as long as 't, which is itself the lifetime bound of the references it will contain. It is not actually what you need, self should live less than 't to guarantee that any &'t is still alive and kicking until self dies.

If we change this, we can painlessly return references to Element:

impl<'t> Top<'t> {
    fn add<'a>(&'a mut self, p_name: &'t str) -> &'a Element<'t>;
    fn add_once<'a>(&'a mut self, p_name: &'t str) -> &'a Element<'t>;
}

Note that the lifetime 'a of the reference to Element is different (and actually will be shorter) than the lifetime 't of its contained reference.

With that out of the way, this should fix the functions:

fn position(&self, p_name: &str) -> Option<usize> {
    self.list.iter().position(|e| e.name == p_name)
}

fn add<'a>(&'a mut self, p_name: &'t str) -> &'a Element<'t> {
    self.list.push(Element::new(p_name));
    &self.list[self.list.len() - 1]
}

fn add_once<'a>(&'a mut self, p_name: &'t str) -> &'a Element<'t> {
    if let Some(p) = self.position(p_name) {
        return &self.list[p];
    }
    self.add(p_name)
}

And position can be reused for get:

fn get<'a>(&'a self, p_name: &str) -> Option<&'a Element<'t>> {
    self.position(p_name).map(|pos| &self.list[pos])
}

I would expect the following to work in a perfect world:

fn add_once<'a>(&'a mut self, p_name: &'t str) -> &'a Element<'t> {
    match self.get(p_name) {
        Some(x) => x,
        None => self.add(p_name)
    }
}

However, I recall a discussion in which it was determined that the borrow-checker was not lax enough: the scope of the borrow induced by self.get is computed to be the entire match expression even though in the None branch the temporary cannot be accessed.

This should be fixed once "Non-Lexical Lifetimes" are incorporated in Rust, which is a work in progress.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
  • You are entirely correct in your "perfect world" remark. This does not work because borrows are lexical, but they will probably become non-lexical in future, which would allow such pattern. As far as I remember, this was one of the main reasons of introducing `Entry` API in maps in `libstd` (the other one is the desire to reduce amount of lookups, of course). – Vladimir Matveev Nov 13 '14 at 18:05
  • @VladimirMatveev: I hope it will be extended, the use of irrefutable patterns in `if` is a good work-around, but it means losing the exhaustiveness check of `match`. – Matthieu M. Nov 13 '14 at 18:35
  • @MatthieuM. Thanks, I understand lifetimes a bit more. In fact, `add` and `add_once` return references that have a different lifetime from the element itself. Needs a little brain-gym, but seems nice. However, the compiler complains on `fn<'a>`, shouldn't it be `fn add<'a>` ? Or is it a new syntax ? Furthermore, the `if let` syntax is experimental in v0.12. The syntax with `match` looked really clean. – Tifauv' Nov 14 '14 at 11:03
  • @Tifauv': Sorry for the `fn<'a>` the lifetime is after the function name indeed. I agree the `match` syntax is cleaner, however it does not work at the moment as explained in my note. – Matthieu M. Nov 14 '14 at 11:26
  • Wouldn't it be possible to have a race condition between the `push` and `index` ? If `Vec.push` returned the inserted element, it would be more simple. – Tifauv' Nov 14 '14 at 11:35
  • @Tifauv': It would be simpler but it is not possible (yet), as for race conditions there is no worry because a `&mut T` pointer guarantees that no-one else is reading/writing to the object at the moment (there is no other alias in use). It's a guarantee that is very peculiar to the Rust ownership system. – Matthieu M. Nov 14 '14 at 12:25
  • @MatthieuM. OK, I forgot about the `&mut T`. Rust has some unique concepts that take some time to get right. I tried the modifications you proposed, and it still doesn't compile. First, in `add`, `Vec.index` takes a reference to the index, not the index itself so I first create `let idx = self.list.len() - 1;` then call `self.list.index(&idx)`. However, the compiler still refuses the `if let Some(x) = self.get(p_name) {` with the message **cannot infer an appropriate lifetime for autoref due to conflicting requirements**. Maybe it works with nightly build and not 0.12 ? – Tifauv' Nov 14 '14 at 14:47
  • @Tifauv': I am not compiling actually, as I don't have 0.12 handy anyway. Since `Option` contains a reference, you might need a `Some(ref x)` to indicate that `x` is a reference. – Matthieu M. Nov 14 '14 at 15:48
  • @MatthieuM. That didn't work. `x` is indeed a reference, and is what I want to return, so I had to modify the return line as `return *x`. I get the same error as in my previous message. – Tifauv' Nov 17 '14 at 10:18