What do you think about relative pointers?

When using Rust, sometimes I wished I could have in a struct reference to some other member of the struct itself, some kind of 'self lifetime.

Then I worked in a C++ project and found out why that is such a terrible idea. The C++ class was move-only, with defaults move constructor and move assignment, and obviously I got a segmentation fault when the object moved, because the address of all the members changed, but not the value of the self-referencing pointer.

My first idea to solve it was to place the values I could reference in an array, and store the index, but then I had an epiphany, and for the first time in my life I found an use for the very obscure pointer to member variable.

You see, an array index is kind of a relative pointer, it gives you the position from the start of the array. Then it occurred to me that pointer to member variable is pretty much the same thing, but for the structs/classes: it gives me the relative position of a field from the start of the object. It is the C++ type safe equivalent of C offsetof macro. That solved my problem completely, because I could move my object as much as I want, and the pointer would still be valid.

I figure this "relative pointer" solution fits rust move semantics perfectly, and would allow the user to create references to struct fields in the struct itself.

Is there anything like it already proposed or implemented in rust?

Do you think it is possible to implement it as a crate? (I guess probably, with macros and unsafe tricks, akin to C's offsetof). EDIT: nevermind, just found crate field-offset.

What do you think of it for a language feature?

8 Likes

rkyv has an implementation of relative pointers. It's a key part of its architecture.

1 Like

Do you have an usecase for this?

AFAIK most of the time you don't just want to store a reference to a field, but a reference to something borrowed from that field. This is problematic because this reference is not guaranteed to be relative to self (imagine for example it was a reference to the contents of a Box field)

1 Like

In the C++ code I mentioned, there was a class that had to proxy properties from one of two inner objects, so I used the field InnerClass ProxyClass::* selected_inner; to choose between them. The borrowing would happen only at the moment I dereference selected_inner through some ProxyClass object.

Besides this one example, it seems such a thing is important to rkyv and users of crate field-offset. But sure, the uses are rare, that is probably why it is almost never used in C++.

I've done something like this in the past (not in Rust) for data structures that were in shared memory, but not necessarily mapped at the same base address.

https://sourceware.org/git/?p=systemtap.git;a=blob;f=runtime/dyninst/offptr.h;hb=HEAD

There are two separate problems that need to be solved here:

  1. The actual pointer representation. For this, you can use a relative pointer, or you can use an absolute pointer and pin the data structure.

  2. The lifetime representation in the Rust type system. For this, we need self-referential lifetimes, which I do very much hope we have one day. I know that @nikomatsakis is enthusiastic about that possibility as well, and has thought hard about that problem.

5 Likes

There is no need to change the lifetime rules if we use relative pointers. The actual borrowing only happens when you dereference it from a valid base object reference, so ordinary borrow and lifetime rules applies.

That assumes you have to supply the base pointer along with the relative pointer when you dereference, rather than having the base pointer implied.

1 Like

Yes, that is how C++ pointers to member variables and the crate I found works.

You always have to do this; that’s what makes it relative. You can make different choices for the base, but you can avoid passing it separately if you make the base be &self of the method that resolves the relative pointer. Which can be the relative pointer offset storage itself, or the base of some containing object; as long as it’s enforced that everything in the relative graph has the same lifetime, it works out.

If you want it to be the base object in the entire archive, then yeah, you end passing an extra argument. Which is also fine, just more to keep track of, as you pointed out.

Note that this all applies to immutable object graphs. I do think it’d be harder to do a mutable one. But I think that’s expected anyway; anything that supports mutation can either support offset adjusting, which would have be done on a global level across an entire archive, or it could ban mutations that require offset adjustments.

1 Like

As pointed out above, this is an alternative to pinning.

It seems like a much more natural fit in Rust compared to the complexity of an additional dimension of pinning to Rust's sementics.

Has this been considered for async, futures, generators etc? It would certainly simplify the API surface of these features.

1 Like

What about pointers which could point to either another part of the future or something outside of the future? The former would need to be a relative pointer while the later would need to be an absolute pointer. There is no way to know whether such a pointer should be interpreted as relative or as absolute pointer.

See offset-based solutions in blog series on async design by @withoutboats.

4 Likes

This is why I previously said:

This is exactly what happens in futures. You don't just have local variables that hold references to other local variables (which is just what a relative pointer would be able to express), instead they could be wrapped in other types, and/or they could point inside other types, and this isn't even fixed per-variable (i.e. a single variable could be created conditionally with a reference of one kind or the other).

7 Likes