How to return reference to value in Rc or RefCell

[quinedot]

I think you would find this blog post informative.

[Shri333]

Ok. Thank you so much for your help. I have one remaining confusion. How does the compiler know that the reference inside my_option lives longer than my_option?

struct Foo {
    data: Option<String>
}

impl Foo {
    fn bar(&self) -> &String {
        let my_option = self.data.as_ref();
        return my_option.unwrap();
    }
}

fn main() {
    let foo = Foo { data: Some("hello".to_owned()) };
    println!("{}", foo.bar());
}

[chrefr]

If we annotate the lifetime:

fn bar<'a>(&'a self) -> &'a String

Then &self.data -> &'a Option<String>. self.data.as_ref() is actually Option::as_ref(&self.data), and the signature for as_ref() (desugared) is:

fn as_ref<'b>(&'b Option<T>) -> Option<&'b T>

So it produces Option<&'a String>. Unwraping it gives &'a String, which is the correct type.

[Shri333]

OK, thank you so much for the help. So, the following example would compile because the lifetime of hi is directly related to that of &self.data, but if I write something like this: let hello = Rc::clone(&self.data); return &*hello, it would not compile because the lifetime information would disappear when I call clone.

use std::rc::Rc;

struct Foo {
    data: Rc<String>
}

impl Foo {
    fn bar(&self) -> &String {
        let hi = &*self.data;
        return hi;
    }
}

fn main() {
    let foo = Foo { data: Rc::new("hello".to_owned()) };
    println!("{}", foo.bar());
}

Is the line of reasoning above correct?

[chrefr]

Yes. The compiler does not know about the sharing nature of Rc; it thinks of it as an owned type.

[Shri333]

Ok, thank you so much for your help. You helped clarify a lot of misconceptions I had.

[quinedot]

This is an interesting case to think about, really. Maybe this will lend some insight (I hope so).

First a couple basics that are pretty trivial.

This doesn't compile:

fn borrow_from_owned<T>(rc: Rc<T>) -> &T {
    &*rc
}

The compiler doesn't like that the lifetime of the returned reference "came out of nowhere", which is already a big clue. We can tell it, hey, don't mind that:

fn borrow_from_owned<'any, T>(rc: Rc<T>) -> &'any T {
    &*rc
}

But it will still fail, because you can't borrow from a local and return a reference to it. And that's definitely correct here too! If that rc is the only one still pointing at the contents, the contents will drop when rc drops. Good, fine, makes sense.

---

This compiles just fine:

fn borrow_from_borrow<'rc, T>(rc: &'rc Rc<T>) -> &'rc T {
    &*rc
}

It's very much like a field access, or borrowing a &str from a &String. Good, fine, makes sense.

---

Now the interesting one. Knowing how Rc works, you may expect this to work:

fn borrow_from_clone<'rc, T>(rc: &'rc Rc<T>) -> &'rc T {
    let clone = Rc::clone(rc);
    &*clone
}

And as was explained, the compiler doesn't understand that the returned reference is just fine, because it really pointing at someting owned by rc. Let's take it in slow motion and point out a few reasons why it "has" to be this way (without Rc becoming very, very special-cased by the language).

First, let's be a little more explicit about the clone type.

fn borrow_from_clone<'rc, T>(rc: &'rc Rc<T>) -> &'rc T {
    let clone: Rc<T> = Rc::clone(rc);
    &*clone
}

That Rc<T> of clone has no lifetime on it. There's nothing on the language level still connecting it to rc. This is similar to the first case, where a lifetime is going to have to come "out of nowhere".

Let's imagine there's a way to overcome that though, and be more explicit about the returned value too. Maybe the compiler will get that they're related.

fn borrow_from_clone<'rc, T>(rc: &'rc Rc<T>) -> &'rc T {
    let clone: Rc<T> = Rc::clone(rc);
    let borrow: &'rc T = &*clone;
    borrow
}

Nope, it's not buying it. Here, we get a whole new error about 'rc being too long. This comes up occasionally in other situations: When you have a function with a lifetime parameter, that lifetime is chosen by the caller of the function. Within the function, it could be almost anything -- the main thing you know is that it lasts longer than the function body (it lasts at least as long as the call site expression). ^[1]

But clone is a local, so you can't borrow it for longer than the function body.

Rust generally wont just take our word that things are okay. You make assertions like that by using unsafe and taking on the responsibilities to uphold Rust's safety guarantees yourself.

---

Finally, I'd like to outline another way to think of this situation. Disclaimer: it's a bit more hand-wavey than the rest, and it's possible Rust will find ways to grow beyond this mental model. Anyway, the general idea is to think of a chain of exclusive access.

First note that shared references are very flexible -- you can Copy them, so you can even copy a &'long T out of a &'short &long T, and so forth. For example, if I have a &String, and then I create some &str from that, and then I use the &String again, I can keep on using the &str. No problem.

The exclusive nature of &mut make it much more rigid, though. You can only move or reborrow them, not copy them, and you cannot get a &'long mut T from a &'short mut &'long mut T. And if I have a &mut Vec<T>, and I create a &mut [T] or even &[T] from that, and then I use the &mut Vec<T> again... my &[T] sub-borrow gets "cancelled". This makes sense -- maybe my use of &mut Vec<T> was to call .clear() after all.

And the same is true if you have a &T you got from an owned value, and then use the owned value again. You can do anything with owned values that you can with a &mut T and more, after all. The semantics for ownership are at least as strong.

Beyond a single borrow, a chain of exclusive access back to the owned, borrowed object must remain "unbroken".

let mut owned = String::new();
let a = &mut owned;
let b = &mut *a;
let c = &mut *b;
let d = &mut *c;

// This use of `b` makes both `c` and `d` unusable.
// But `b` is still ok to use,
// - and so is `a` (but using it makes `b` unusable),
// - and so is `owned` (but using it makes all borrows unusable)
println!("{b}");

So with that in mind, consider this function:

fn borrow_unique(i: &mut Holder<i32>) -> &mut i32 {
    let mut h: Holder<&mut i32> = Holder(&mut i.0);
    let h = &mut h;
    
    &mut *h.0
}

It fails, while the shared version succeeds. We can talk about why in terms of lifetimes and borrowing and copying shared references -- we've created some &'local mut Holder<&'foreign i32> value, and you can't get a &'long mut T from inside a &'short mut &'long mut T and so on.

But we can also reason about it in terms of the chain of exclusive access. When our local goes out of scope at the end of this function, we break the chain of exclusive access -- an intermediate link is invalid, so our returned value has no path back to the owned value, and it too must be invalid.

With that viewpoint, you can forget about lifetimes per se and see how borrow_from_clone is analogous to borrow_unique in some way: you stuck the data behind something the language considers exclusive (an owned Rc) and then borrowed through that exclusive thing. Once the exclusive thing is gone, so is your access.

---

1. The lifetimes also have to make sense for the types, so here: fn foo<'a, 'b>(_: &'a &'b str) {} you know that 'b: 'a. ↩︎

[Mng12345]

You can make the type of data to Rc<T>

use std::{
    cell::RefCell,
    rc::{Rc, Weak},
};

const INDEX_OUT_OF_BOUNDS: &str = "Error: index is out of bounds.";

type StrongListNode<T> = Option<Rc<RefCell<ListNode<T>>>>;
type WeakListNode<T> = Option<Weak<RefCell<ListNode<T>>>>;

pub struct LinkedList<T> {
    head: StrongListNode<T>,
    tail: StrongListNode<T>,
    size: usize,
}

struct ListNode<T> {
    data: Rc<T>,
    prev: WeakListNode<T>,
    next: StrongListNode<T>,
}

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        LinkedList {
            head: None,
            tail: None,
            size: 0,
        }
    }

    pub fn get(&self, index: usize) -> Result<Rc<T>, &str> {
        if index >= self.size {
            return Err(INDEX_OUT_OF_BOUNDS);
        }

        let mut curr = Rc::clone(self.head.as_ref().unwrap());
        for _ in 0..index {
            let temp = curr;
            curr = Rc::clone(temp.borrow().next.as_ref().unwrap());
        }
        // get value step by step, you can write it into one step
        let a = Rc::as_ref(&curr);
        let b = a.borrow();
        let c = &*b;
        let d = c.data.clone();
        Ok(d.clone())
    }
}

[H2CO3]

@Shri333

what about the Rc? Why does dereferencing the Rc result in the owned type rather than a reference to the value inside the Rc?

Note that this is not an arbitrary decision, and you shouldn't expect anything else, basically. The desugaring of Deref very deliberately includes dereferencing the returned (&Deref::Target) type. That is the point (and the definition) of dereferencing: it removes a layer of indirection. Converting a reference of one type into a reference of another type (possibly to one of its fields) definitely does not count as "dereferencing".

To compare it with a simpler example: an Rc is a pointer. If you expected to get a &T when you dereference an Rc<T>, then by the same line of thought, you should also expect a simple reference, &T, to yield the exact same reference, &T when "dereferenced". But that would be useless – it would mean there is no way to get (or mutate) a value from behind a reference.

[Shri333]

Thank you so much for the detailed response. It was quite illuminating. The only thing I am confused about in your response is the semantics of referencing a dereference. For example, the following code (based on your example would compile):

let mut owned = String::new();
let a = &mut owned;
let b = &mut *a;
println!("{a}");

However, the following code would not:

let mut owned = String::new();
let a = &mut owned;
let b = &mut owned;
println!("{a}");

Why is there a difference? In both examples, isn't b technically mutably borrowing from owner (albeit in the first example, it's through the dereference)? I am a bit confused about the semantics of referencing a dereference here. I also am not familiar with this "chain of exclusive access" concept.

[Shri333]

Yeah, that makes sense. I was just trying to get a reference to the value inside an Rc, so I was wondering if I could exploit deref in some way to do that.

[quinedot]

@Shri333

Why is there a difference? In both examples, isn't b technically mutably borrowing from owner (albeit in the first example, it's through the dereference)? I am a bit confused about the semantics of referencing a dereference here. I also am not familiar with this "chain of exclusive access" concept.

The rule when stated briefly is "memory reachable through a &mut cannot be aliased", or un-jargoned, "&mut implies unique access". That's just a core part of the language, upon which the memory safety guarantees rely. Thus violating the rule is instant undefined behavior, and since Rust doesn't have UB in safe code, if the compiler can't prove to itself your code obeys the rules, it throws an error.

The rule is sometimes phrased as "you can't have two &mut at the same time", or "you can't have a &mut and a & at the same time", but as the working examples illustrate, that phrasing is a bit too simplistic. It's really more like, "you can't have two active at the same time." This is what allows reborrowing, which is sort of like a sub-borrow:

let a = &mut owned;
let b = &mut *a;
// We're both `&mut String` but `b`'s borrow depends on `a`'s borrow.
//    We didn't move `a` to get the reborrow,
//    And the lifetime for `b` might be shorter than that of `a`
//
// `a` is unusable (inactive) while `b` is active, but not dead yet.
// Or alternatively put, using `a` again "kills" `b`'s [sub-]borrow
// (and any use of `b` thereafter emits a compiler error)
// ((And both are borrows of `owned`, so using that kills both))

These reborrows are actually all over the place: when you call a method that takes &mut, a reborrow is performed, otherwise you couldn't do something like

fn foo(v: &mut Vec<i32>) {
    v.push(0); // Vec::push takes `&mut self`
    println!("{v}");
}

Because &mut can only be moved, not copied. So you get a reborrow here whose lifetime is only as long as the call to push, and can use v again afterwards. The reborrow here is implicit; &mut *a is just the explicit way to write it. You can also reborrow only parts of the original borrow.

let v2 = &mut v[0..5];     // [] acts like a * dereference
let field = &mut object.f; // So does field access

---

Fine then, what exactly determines this "active or not" quality? Unfortunately, there is no formal specification. The closest thing that's been proposed so far is stacked borrows. However, stacked borrows doesn't quite cover everything Rust allows today, and will probably be expanded at some point. ^[1] (If you run Miri, ^[2] it uses a version of stacked borrows which has already evolved a bit from the paper.)

In terms of what we have discussed here,

let mut owned = String::new();
let a = &mut owned;
let b = &mut *a;
println!("{a}");

owned has a conceptual stack, creating a pushes an exclusive access based on owned, creating b pushes an exclusive access based on a, and then using a pops b (killing its borrow) so that a can be on the top of the stack again and get used. Because it got popped, b can no longer be used. Using owned would have popped everything.

Where as here

let mut owned = String::new();
let a = &mut owned;
let b = &mut owned;
println!("{a}");

In order to create b, owned must be at the top of the stack, so a gets popped and it's an error to use it afterwards. ^[3]

This "I'm still on the stack" property is the same thing I was trying to convey with the "I have a chain of exclusivity back to the owner" discussion. Both are mental models to reason about why you get the errors you do, by approximating the analysis the compiler actually does.

---

For much more technical discussion, but also in my opinion much harder to reason about one, you can read the NLL RFC. We have most of NLL today. ^[4] The borrow errors you get today are actually from the NLL implementation.

Or for a different approach with the same goal, you can read the Polonius ^[5] blog posts

• one
• two
• three

Polonius handles NLL Problem Case #3, and the plan is for it to replace the current NLL implementation eventually, but it's a work in progress. ^[6]

---

1. That's why I said Rust might grow beyond the "chain of access" model. ↩︎

2. you can do this in the playground under Tools ↩︎

3. Now, one could imagine this particular case being accepted -- if b is never used, or maybe b could be allowed to activate after a, etc. I.e. this is another case where Rust could evolve and break these mental models. The trick will be both getting it right (not creating soundness bugs) and not making it something too complicated for humans to reason about. ↩︎

4. We don't have the piece that solves problem case #3 yet. ↩︎

5. a next-generation borrow checker ↩︎

6. You can use it on nightly with -Zpolonius. ↩︎

[Shri333]

That makes sense. Thank you so much for the detailed response. The concept of stacked borrows resonates well in my mind (as you can probably tell by my profile picture ).

[Shri333]

Actually, now I that I think about it more, the borrowing examples you mentioned makes sense in terms of using a stack as a mental model, but I still don't understand how the compiler analyzes lifetimes. I know that it is based on usage of the reference, but that's as far as how my understanding goes.

For example, in the example below, the lifetime of a is extends from lines 3 - 4, and the lifetime of b is limited to line 5. Since these lifetimes are non-intersecting, this code compiles cleanly with no errors.

But, in the code snippet below, the lifetime of a extends from lines 3 - 5, and the lifetime of b is limited to line 4. Since these lifetimes are intersecting, the code does not compile.

However, in the code snippet below, the lifetime of a extends from liens 3 - 5, and the lifetime of b is limited to line 4. These lifetimes are intersecting, but why code does compile? Is it because the compiler treats *a and owned as different entities?

If that's the case, then how can the compiler detect the behavior below? What would be the lifetimes of each of these references?

[quinedot]

@Shri333

However, in the code snippet below, the lifetime of a extends from liens 3 - 5, and the lifetime of b is limited to line 4. These lifetimes are intersecting, but why code does compile? Is it because the compiler treats *a and owned as different entities?

The compiler knows that b is a reborrow of a's borrow, yeah. The compiler doesn't used stacked borrows, but let's look at it through that lens, as it's easier to understand.

Here's a playground with the four examples. A lifetime is valid for portions where it's on the stack. ^[1]

You seem to be thinking of the first two examples as (contiguous?) regions that do or don't overlap, and that model works for explaining why they compile or don't. But it's not taking into account the "stacking" nature of reborrows, which is what let's example 3 compile.

In example 3, 'b is a reborrow of 'a -- it's stacked above 'a. So it's still okay to use 'a -- although you'll have to pop 'b to do so.

Therefore, the stacking model allows for more uses than the "any intersection is bad" version.

In example 4, stacked borrows keeps tracks of all of these reborrows. Once you use a, the stack gets popped a bunch, killing 'b, 'c, and 'd. Then it's an error when you try to use d again.

---

Another formulation of how a stack works is to consider things to be well-nested. This is pretty simple at the single-borrow level: I create a borrow of owned, and all uses of that borrow have to be before the next use of owned [and the drop of owned or end of its lifetime is a "use"]. A valid borrow must be nested within the uses of what is borrowed.

It's a little more complicated with deeper layers: Every use of a reborrow has to be before the next use of whatever we reborrowed from, and transtively anything they borrowed or reborrowed from.

The pattern to avoid is a break in the nesting: AXBX where X borrows or reborrows from A, and B is A or something A transitively is a borrow or reborrow of.

In nesting terms,

• Example 1
  • a is used on lines [3..=4], nested between uses of owned on [3..=5]
  • b is used on line 5, nested between uses of owned on [5..=6]
• Example 2
  • a is used on lines 3 and 5 and that is not nested between uses of owned on [3..=4]
  • b is nested on line 4 (in [4..=6]) but that doesn't matter due to the above
• Example 3
  • a is used on lines [3..=5], nested between uses of owned on [3..=6]
  • b is used line 4, nested between uses of owned or a on [4..=5]
    • This is a transitive case but we didn't need the transitivity, just the relation to a
• Example 4
  • a is on lines [3..=4] and 7, nested in [3..=9] (owned)
  • b is on lines [4..=5], nested in [4..=7] (owned, a)
  • c is on lines [5..=6], nested in [5..=7] (owned, a, b)
  • d is on lines 6 and 8, not nested in [6..=7] (owned, a, b, c)

Graphically on a timeline, you can draw arcs between

• Borrows or reborrows and what is being borrowed or reborrowed from
• Subsequent uses of the borrow

And if all the arcs are nested, you're fine; if there is an intersection, that's an error.

It's a pain to do with code comments (especially once you get into loops), so here's a drawn version.

(Uses are in (...).)

In terms of "chains of exclusivity", valid uses of borrows have a non-intersection path back to the owned data ^[2], and the use of something like (a) or (drop S) kills all chains under the arc that lead back to the left endpoint (so in example 4, (a) killed b c and d).

---

1. I'm ignoring shared borrows and everything except exclusive borrows in this whole post. ↩︎

2. shared endpoints aren't intersections ↩︎

[Shri333]

@quinedot

Every use of a reborrow has to be before the next use of whatever we reborrowed from, and transtively anything they borrowed or reborrowed from.

Thank you so much for the detailed response. I think this line is key. The concept of stacked borrows makes more sense now. I think I fell into the trap of clinging too hard to the "any intersection is bad" version because of what I learned in the book (no complex examples of reborrowing were given in the book). If I have it right, any use of a borrow should be used before another use of what that borrow is borrowing OR if what that borrow is borrowing is borrowing something else, it also should also be used before another use of that (transitive nesting). Otherwise, the borrow becomes invalid. I have one final question (I promise ): are there any obscure examples where this mental model fails to explain why certain code compiles/does not compile?

[H2CO3]

@Shri333

I fell into the trap of clinging too hard to the "any intersection is bad" version

I don't think that "any intersection (mutable aliasing) is disallowed" is a bad mental model, you just have to extend it a little bit in the context of reborrowing. When you have a mutable reference a and you reborrow it creating mutable reference b, then as long as b is in use, the original a is "frozen", ie. you are temporarily banned from accessing it. In this manner, there will be no real (usable/exploitable) mutable aliasing.

[quinedot]

@Shri333

I have one final question (I promise ): are there any obscure examples where this mental model fails to explain why certain code compiles/does not compile?

Yes, for a few reasons:

• Stacked borrows is a bit more complicated than has been summarized here due to shared borrows and interior mutability, so you would have to work that in to your model
  • It also gets messy when you start mixing diferrent data types together, in terms of diagramming things out anyway
• Even then, there are some Rust features like two-phase borrows that it didn't handle, and has evolved since the paper and no longer has strict stack discipline
• And even then the idea of stacked borrows is to be a runtime analysis which is sort of an "upper bound" on Rust's (not formally defined) aliasing model, regardless of the current implementation
  • And thus can only ever be an approximation of the compiler's static analysis
  • E.g. NLL Problem Case #3 will give you an error today, but is actually sound and accepted by Polonius, and if you forced it with unsafe I believe Miri would be fine with it
• More generally, a main idea of unsafe is that sometimes the compiler cannot prove some safe code is sound (e.g. obeys the aliasing model) when it is

So ultimately it's just a tool, but I've found it to be a pretty good one. The only way to fully know why certain code compiles or doesn't compile is to fully understand the compiler. So understanding the NLL RFC or perhaps the Polonius approach will arguably get you closer to the technical reason why (as those are the static analysis that the compiler performs), but if I can see an error and trace it to a nesting violation or whatever, it's almost certainly unsound and I can just go "ah yeah fine, here's at least part of the probelm" and get to work trying to find a solution. At least personally, I find that easier than trying to reason about a shifting set of loans and regions in a flow graph.

---

It would be neat if there was something that could output an annotated version of your code with the compiler's lifetime / borrow analysis though. If it exists already and I'm just unaware, I'd love to hear about it.

[Shri333]

Thanks for the detailed response. It's been a little bit frustrating with the compiler when you think that some code should or should not compile (esp. as a beginner), but I guess more experience and a rigorous understanding of Rust internals will help a lot.