Conflicting lifetime


#1

Having a problem compiling this piece of code:

use std::collections::HashMap;

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

struct Foo<'a> {
    s: String,

    nodes: HashMap<u64, Node<'a>>,
}

impl<'a> Foo<'a> {
    fn new() -> Foo<'a> {
        let mut f = Foo {
            s: String::new(),
            nodes: Default::default(),
        };

        f.make_root();
        return f;
    }

    fn make_root(&mut self) {
        let n = Node { s: &self.s };
        self.nodes.insert(0, n);
    }
}

fn main() {
    let f = Foo::new();
}

the error is:

$ rustc test.rs
error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> test.rs:25:27
   |
25 |         let n = Node { s: &self.s };
   |                           ^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the body at 24:28...
  --> test.rs:24:29
   |
24 |       fn make_root(&mut self) {
   |  _____________________________^
25 | |         let n = Node { s: &self.s };
26 | |         self.nodes.insert(0, n);
27 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> test.rs:25:27
   |
25 |         let n = Node { s: &self.s };
   |                           ^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the body at 24:28...
  --> test.rs:24:29
   |
24 |       fn make_root(&mut self) {
   |  _____________________________^
25 | |         let n = Node { s: &self.s };
26 | |         self.nodes.insert(0, n);
27 | |     }
   | |_____^
note: ...so that expression is assignable (expected Node<'a>, found Node<'_>)
  --> test.rs:26:30
   |
26 |         self.nodes.insert(0, n);
   |                              

How should I resolve this? Why does n in make_root() not have the correct lifetime type?


#2

It’s not possible for a struct to contain a reference to something in itself. You can’t put Foo’s &s in Foo’s other fields (that’s because Rust can’t guarantee you won’t move or replace only one field of the struct, making others invalid)

You will need to use Rc or make the reference passed from outside new(), so it will live in caller’s stack, not in Foo.


#3

Thanks for the suggested workaround. I think I understand the rationale but could you elaborate on “Rust can’t guarantee you won’t move or replace only one field of the struct, making others invalid”?


#4

so I tried to change the code to as follow:

use std::collections::HashMap;

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

impl<'a> Node<'a> {
    fn new(s: &'a AsRef<str>) -> Node<'a> {
        return Node { s: s.as_ref() };
    }
}

struct Foo<'a> {
    s: &'a str,

    nodes: HashMap<u64, Node<'a>>,
}

impl<'a> Foo<'a> {
    fn new(s: &'a AsRef<str>) -> Foo<'a> {
        let mut f = Foo {
            s: s.as_ref(),
            nodes: Default::default(),
        };

        f.make_root();
        return f;
    }

    fn make_root(&mut self) {
        self.nodes.insert(0, Node::new(&self.s));
    }
}

fn main() {
    let s = "foo".to_string();
    let f = Foo::new(&s);
}

but I am getting similar error as before. If I make Node::new() take &str instead of &AsRef then the code compiles. Any idea why?


#5

When you write

        self.nodes.insert(0, Node::new(&self.s));

The lifetime associated with &'a str is the lifetime of the reference &self.s. Which only lives for as long as the make_root function call. This means that the reference wont live long enough to be stored in Foo. You really want self.s, but I bet you ran into some problems with str not being Sized. You can fix this by replacing:

    fn new(s: &'a AsRef<str>) -> Node<'a> {

with

    fn new<'s, S: AsRef<str> + ?Sized>(s: &'s S) -> Node<'s> {

Also note that the second example uses a generic, and not a trait object. This is probably what you want. I do worry about this design however. Please be aware that everything you place into Foo must live longer than Foo. In particular, look at this example found here.


#6

Thanks @cbreeden. The bit about Sized makes sense and solves my problem. I am still trying to find a way to express what I want though, which is that Foo owns the String and Node has a reference to Foo’s String. Moving up the ownership to the stack like @kornel suggested is difficult because there can be more than one Foo. Changing everything to use Rc is possible too but seems like a hammer as Node will never live longer than Foo.


#7

Can you flip it? Let every Node own their String, and the Foo can lookup the root (0) as needed.


#8

No, because all the Node’s strings are the same.


#9

Maybe rental will work for this, but I don’t have much experience with it.

The thing is, while it may be obvious to you, the compiler can’t prove this. In this function:

    fn make_root(&mut self) {
        self.nodes.insert(0, Node::new(&self.s));
    }

You would be absolutely free to change self.s before you inserted anything, because the &mut self promises that you have exclusive access to all of self. But once the function returns, we don’t know anymore, so that’s where its borrowed lifetime ends. You would be allowed to call this again, or any other mutating method, and self.s is not protected.

Proving that you never change self.s anywhere would require global analysis, but Rust is checked per-function. If you use Rc, then that indirection provides shared immutable ownership we can prove.


#10

if only I could mark certain fields in a struct to be const!


#11

Even if fields could be const, you’d also have to make sure that Foo itself doesn’t get moved around, changing the addresses of its fields. It happens to be OK for String borrowing &str, since it already has heap indirection to its buffer. That’s not really represented in the type system, but there’s a StableDeref implemented for some such types. (This is what rental uses.)


#12

Thanks for giving me an excuse to play with rental – this is probably not optimal, but it works:

#[macro_use]
extern crate rental;

use std::collections::HashMap;

rental! {
    mod foo_rental {
        use super::*;

        #[rental]
        pub(super) struct FooRental {
            s: String,
            nodes: HashMap<u64, Node<'s>>,
        }
    }
}

use foo_rental::FooRental;

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


struct Foo {
    rental: FooRental,
}

impl Foo {
    fn new() -> Foo {
        let mut f = Foo {
            rental: FooRental::new(String::new(), |_| Default::default()),
        };

        f.make_root();
        return f;
    }

    fn make_root(&mut self) {
        self.rental.rent_all_mut(|rental| {
            let n = Node { s: &rental.s };
            rental.nodes.insert(0, n);
        })
    }
}

fn main() {
    let f = Foo::new();
}

#13

Rust considers it unsafe, because it doesn’t have a mechanism to prevent move of a struct with internal references. Such logic could perhaps be added in the future, but in Rust currently a struct owning its own references could be unsafe if moved:

let tmp = Foo::new(); // Foo.s is on the stack
let foo = Box::new(tmp); // Foo is memcpy'd to heap, so address of Foo.s has changed
// Error: nodes now point to the stack where there is no String any more

Rc adds a level of indirection that makes move of Foo, or replacement of Foo.s safe. If that string is not performance critical and you just want to get on with it, then that’s a good solution.

Holding &s somewhere else means it won’t be moved/freed when Foo is moved/changed, so it’s safe too.

Another way is to create nodes without the string reference, and make nodes’ functions take Foo as an argument (so that they read the up-to-date &Foo.s address even if it’s moved). That’s probably the most practical low-overhead solution you can get in safe-only Rust.

And there are solutions involving unsafe:

  • if you’re 100% sure the address of Foo.s won’t change for the lifetime of nodes, and the object won’t be replaced, then you can use unsafe *const String pointers to bypass the safety checks.

  • You can take reference to the string (&str), unsafely cast it to &'static str and mem::forget(s) the String to leak its memory, so that you have a reference that lives forever, which can be used without restrictions.


#14

thanks for the detailed explanation @kornel ! In my case, there’s only one instance of Foo in the main program but I use many of them in test, so I am just going to allocate Foo.s in main()'s stack. In test, I am using *const String and transmute it to 'static to create Foo. I know where my test ends so it’s easy to Box the string again to free it. I understand that Rc is fast but it feels weird to use it because like I said there’s normally only one Foo.