1

I had the idea to use a pinus::sync::PineMap (GitHub) to make all references of equivalent objects actually reference the same object in memory (the "one" object would be a PineMap-owned value). I'm trying out PineMap for this because its insert will not move its items in memory (its insert borrows &self not &mut self too) so references to its values will stay valid even when adding more entries to the PineMap, and I can build self-referential items.

I have some kind of lifetimes issue:

#[derive(Eq, PartialEq, Ord, PartialOrd)]
enum List<'a> {
    Cons(isize, &'a List<'a>),
    Nil,
}

fn main() {
    use List::*;
    use pinus::{prelude::*, sync::PineMap};
    let mut table = PineMap::new();
    table.insert(Nil, Nil);
    {
        let nil = table.get(&Nil).unwrap();
        table.insert(Cons(1, nil), Cons(1, nil));
    }
    table.clear();
}

error[E0597]: `table` does not live long enough
  --> src/main.rs:13:19
   |
13 |         let nil = table.get(&Nil).unwrap();
   |                   ^^^^^^^^^^^^^^^ borrowed value does not live long enough
...
17 | }
   | -
   | |
   | `table` dropped here while still borrowed
   | borrow might be used here, when `table` is dropped and runs the `Drop` code for type `PineMap`

error[E0502]: cannot borrow `table` as mutable because it is also borrowed as immutable
  --> src/main.rs:16:5
   |
13 |         let nil = table.get(&Nil).unwrap();
   |                   --------------- immutable borrow occurs here
...
16 |     table.clear();
   |     ^^^^^^^^^^^^^ mutable borrow occurs here
17 | }
   | - immutable borrow might be used here, when `table` is dropped and runs the `Drop` code for type `PineMap`

I thought declaring nil in an inner scope would have resolved all my lifetime problems, because I understand this makes it have a shorter lifetime than table, so it shouldn't be borrowing table anymore by the time table itself goes out of scope.

Why does it look like the inner variable is borrowing an outer variable for longer than the inner variable is in scope?

And in general if this is an unfixable approach, how might I be able to solve my original problem of collecting lots of references to the same object based on object equivalency? If an object O is created, I want to look up "has O been seen before?" If it has, then get a reference to the "cached" O, if it has not, then cache it and be the first to get a reference to the newly cached object.

theonlygusti
  • 11,032
  • 11
  • 64
  • 119
  • What if you remove `table.clear()`? – PitaJ Dec 01 '22 at 15:33
  • Everything in `table` still has to live longer than `table`, a reference to `table` can't outlive `table` though. Or in other words, you can't store references to `table` inside of `table`. – cafce25 Dec 01 '22 at 15:39
  • @PitaJ I still get the first error. – theonlygusti Dec 01 '22 at 15:40
  • @cafce25 that's what i thought the `table.clear()` would help solve. To make sure there actually is nothing in the table when `table` gets dropped – theonlygusti Dec 01 '22 at 15:40
  • 1
    Why a map? It looks like what you need is an arena. – Chayim Friedman Dec 01 '22 at 15:41
  • But `table.clear()` requires an exclusive reference to table (i.e. you can't have references to table when you call it), which makes sense since all other references would otherwise become dangling. It's a little bit of a hen & egg problem. – cafce25 Dec 01 '22 at 15:42
  • [`bumpalo`](https://docs.rs/bumpalo) is a good arena crate. – Chayim Friedman Dec 01 '22 at 15:46
  • @ChayimFriedman I haven't heard of arenas before. Thanks for the tip, I'll read up on them – theonlygusti Dec 01 '22 at 15:49
  • @cafce25 using two `table.drop_entry` in a row, in reverse order, also doesn't work, which surprises me. Especially since I'm placing them outside of the inner scope where `nil` is, and the table-referencing `Cons` entry is dropped first. – theonlygusti Dec 01 '22 at 15:58
  • 1
    The borrow checker only sees that `table` is borrowed for as long as `table` is around from the point you put a self reference in and disallowes `table.drop_entry` it doesn't know that only the last entry in `table` is borrowing from `table` – cafce25 Dec 01 '22 at 16:00
  • 1
    Also since you put a copy of `nil` inside `table` it doesn't matter that `nil` goes out of scope for as long as `table` doesn't. All copies of `nil` have to go out of scope for you to be able to exclusively (`mut`) borrow `table` again. – cafce25 Dec 01 '22 at 16:19

1 Answers1

2

The problem is you're making table self referential. Inserting a reference to table (nil) into table here,

let nil = table.get(&Nil).unwrap();
table.insert(Cons(1, nil), Cons(1, nil));

Means from this point onwards the borrow checker has to enforce that table outlives table which obviously is impossible.

You can't call any of

table.clear();
table.drop_entry();

to get out of this mess either since both need exclusive access to table (they take &mut self) and for as long as there is a shared reference to table inside of itself the borrow checker is not going to allow it.

cafce25
  • 15,907
  • 4
  • 25
  • 31
  • I guess technically `nil` is a reference to something `table` owns (not `table` itself) right? And because `table` owns what `nil` is referencing, `table` must outlive the reference `nil` represents... but that reference is put back into the table, which gives `table` ownership of the reference, so that reference (to something else that `table` owns) will live as long as table now. Is this correct? – theonlygusti Dec 01 '22 at 17:00
  • Well though `nil` is only part of `table` borrowing through methods always borrows the whole thing for the lifetime. – cafce25 Dec 01 '22 at 17:01
  • Does only the compiler consider the whole thing borrowed, or does runtime also suffer from lots of indirection? – theonlygusti Dec 01 '22 at 17:05