Internal references as a separate type

[Tom-Phinney]

@comex

Basically, @Tom-Phinney suggested that in addition to relative pointers, another viable option was having real pointers which the compiler would relocate on move.

Incidentally, that was not my suggestion; it was a reply to post 18 up-thread, where that alternative was suggested.

[comex]

@Tom-Phinney

I didn't dismiss the need. I've seen a number of cases where a struct header has an array index or field offset to the "next" field of the struct to be processed. However, I've never encountered a case where the lifetime of the pointee differed from the lifetime of the containing structure

Well, to the extent I misinterpreted your posts, I apologize. I know relocation wasn't originally your suggestion, but you argued it was possible ("I don't see why the past has to dictate the future") and had some potential benefits ("less impactful to code generation").

@atagunov

@comex, are any of these the existential lifetimes you referred to? Couldn't find much talk about them..

Yes, that's the kind of thing I'm envisioning. In fact, you can translate the first example pretty straightforwardly to rental, and what I call 'existential lifetimes' largely boils down to "rental but without the closures".

That said, as you pointed out, there are some fundamental limitations to what this approach can accomplish. In your example:

struct Graph {
    nodes : Vec<Node>,
    edges : Vec<Edge<'nodes>>,
}

This can be safe only if nodes is immutable as long as edges exists. After all, if you remove a node, there's no way to prove to the compiler that there aren't any edges left pointing to it. Even if you add a node, Vec could reallocate and invalidate the node pointers, though this limitation can be avoided if you use a true arena data structure rather than Vec.

So arguably, there's not much benefit to using self-references here, as opposed to just storing array indices, which would let you freely mutate both arrays.

[Nokel81]

Or instead of storing indices (which carry no type safely with them) some form of type based areana pointer that can "invalidate itself" when what it is pointing to goes out of scope. Sort of like Rc without the double heap allocation (and only one "strong" reference)

[crlf0710]

@atagunov

P.S. above structures could be easily created when one knows the number of nodes in advance; otherwise they seem a bit painful to construct or extend..

@Nokel81

Or instead of storing indices (which carry no type safely with them) some form of type based areana pointer that can "invalidate itself" when what it is pointing to goes out of scope. Sort of like Rc without the double heap allocation (and only one "strong" reference)

Indeed, recently i've created a crate called repository for my own use.

Using it, this example can be written as

struct Graph {
     repo: Repo,
     nodes: Vec<EntityPtr<Node, Graph>>,
     edges: Vec<EntityPtr<Edge, Graph>>,
}

struct Node {..}
struct Edge {
      start: EntityPtr<Node, Graph>,
      end: EntityPtr<Node, Graph>,
}

And it seems without bothering with lifetimes, it can work quite smoothly as well.

EDIT: Fixed the link!