First-class place expressions

Crazy thought: what if we had first-class place expressions in the language?

&(mut) currently enjoys a very special status. You can turn &struct into &struct.field, which is a map &'a Struct -> &'a Field, but it is impossible to express that map in the language. If we wanted to make it a function, what would it even act on? Similarly, it's impossible to express its basic constructor t -> &t as a function T -> &'a T. It doesn't act on a value, it acts on a place expression.

This built-in magic behaviour is desirable for other smart pointers, but currently cannot be ergonomically and safely expressed in the language.

What if there was some opaque compiler-provided place expression object, which could be passed around in user code? A place expression to an object of type T could implement some trait Place<T>.

In its object form dyn Place<T> it would basically be represented as a pointer *mut T, with the distinction that we would know that it's in "dereferenced" form. In other words, place: *const dyn Place<T> is just *const T with the known type T and no dyn metadata (similarly, place: *mut dyn Place<T> is just *mut T).

In the compile-time generic parameter form fn foo<P: Place<T>>(place: P, ..) the place would carry compiler-provided metadata, which would allow a richer API. A place would know its provenance, so that we could check that e.g. field_place is really a place to a field in struct_place. Perhaps it should be possible to go from a field place to its parent struct place. This would allow to avoid dealing with explicit offsets of fields in structs in order to perform that operation.

A smart pointer type, e.g. Ref<Struct>, would be able to provide the place of its contained data, i.e. a mapping impl Place<Ref<Struct>> -> impl Place<Struct> (it would basically just return the dereferenced inner pointer, as a place). Given s: Place<Struct>, we can get s.f: Place<Field>, which can be passed into

Ref::restrict(self: impl Place<Ref<Struct>>, field: impl Place<Field>) -> impl Place<Ref<Field>>

The instance of Ref can be recovered by converting place expression into a value expression, as usual. But if so desired, you could convert &Ref<Struct> into &Ref<Field> with the same function and a referencing.

Since the compiler has full information about both places, it can check that field is really a place in the inner struct and not just some stray pointer. This means that the restriction function can be entirely safe. With a pointer-based or offset-based definition of restrict, I just don't see a way to make a safe API.

Composability becomes easy. To turn Ref<MaybeUninit<Struct>> into Ref<MaybeUninit<Field>>, we first extract the place of the field via

Place<Ref<MaybeUninit<Struct>>> -> Place<MaybeUninit<Struct>> -> Place<Struct> -> Place<Field>

We get the required instance of Ref<MaybeUninit<Field>> by spinning that process in reverse with restrict functions, i.e.

MaybeUninit::restrict(impl Place<MaybeUninit<Struct>>, impl Place<Field>) -> impl Place<MaybeUninit<Field>>

Ref::restrict(impl Place<Ref<MaybeUninit<Struct>>>, impl Place<MaybeUninit<Field>>) -> impl Place<Ref<MaybeUninit<Field>>>

The last line is valid since we track the place provenance, and so we know that the given field: Place<MaybeUninit<Field>> is really a place within struct: Place<MaybeUninit<Struct>>. Also note that you can't turn impl Place<Struct> into e.g. RefMut<Struct>, since RefMut doesn't provide a corresponding constructor, and the RefMut::restrict method requires already having a valid RefMut to restrict.


First-class place expressions would also be able to solve many (most? all?) cases of proliferation of get/get_mut or iter/iter_mut methods, which really don't care about the mutability, and can be essentially generated by a macro. With first-class place expression, we would have a function

fn get_place(self: impl Place<[T]>, n: usize) -> impl Place<T>

which computes the resulting place directly operating on the places of the slice (currently all operations differ only in pervasive const/mut dichotomy). Similarly, we would have

fn iter_place(self: impl Place<[T]>) -> impl Iterator<Item=impl Place<T>>

and the end-user would choose the desired value iterator by applying the corresponding smart pointer constructor. It could be &T or &mut T iterators as usual, but also *const T, Option<&T> or even &MaybeUninit<T>, if some unsafe trickery requires it.

11 Likes

A very interesting proposal, here are some of the things that I noticed:

  • What would be the use case for *const dyn Place<T>?
  • Does Box<dyn Place<T>> make sense? If yes, then we can get &dyn Place<dyn Place<T>>, this seems weird?
  • What can I do in fn foo(p: impl Place<T>)? Is it equivalent to fn foo(p: T)?

This should be a new operator, because it would be a rather common occurrence. I will use ~ in this thread (e.g. let _: &dyn Place<T> = &~Box::new(t)).

I do not like that this is not represented in the function signature/types. "It will cause a compile error when field is not a field of self" only in the docs seems like a bad idea, when writing docs is not a requirement [1].

Here you describe that it is possible to Place<MaybeUninit<T>> -> Place<T>, but that seems to be unsound, becaues I could do:

let data: MaybeUninit<Foo> = MaybeUninit::uninit();
let inner: &dyn Place<Foo> = &~data;
println!("{:?}", inner);

  1. I do not know how one would encode this, maybe a a trait bound Field: ContainedBy<Struct>? ↩︎

I think this reflects that the second Place actually ought to be a different trait. It's not a place, but mapping from one kind of place to another.

Maybe trait MapPlace<Source, Dest>?

Then MaybeUninit::restrict would become

MaybeUninit::restrict(impl Place<MaybeUninit<Struct>>, impl MapPlace<Struct, Field>) -> impl Place<MaybeUninit<Field>>

Continuing with ~ as our operator we could have ~.field mean "a field on an inferred type and ~Struct.field mean a field on type Struct

Then you could call restrict like

let value = MaybeUninit::<Struct>::uninit();

// Source is inferred in this map.
let field: &MaybeUninit<Field> = &MaybeUninit::restrict(~value, ~.field); 
// Source is explicitly Struct.
let field: &MaybeUninit<Field> = &MaybeUninit::restrict(~value, ~Struct.field); 

You might be able to get away with a closure instead of a new trait too? I'm not sure.

1 Like

This is a very interesting idea, but it needs fleshing out. One thing that immediately caught my eye is that Place<T> does not specify whether it owns T, borrows it mutably or immutably. That might not be a problem since it is a trait and could abstract over these "modes". So there could be different structs MutableRefPlace<'a, T>, SharedRefPlace<'a, T> and OwnedPlace<T> that all implement Place<T>. What bugs me is that you haven't shown what the trait looks like, and you also didn't provide the implementation of get_place and iter_place, which makes me doubtful that they can be implemented safely.

Note that the get_place method returns a Place<T> instance with no bounds, so it could return an OwnedPlace<T> when only a SharedRefPlace<'a, T> was provided:

If you had something very different in mind, I'd appreciate if you could explain it in more detail.

2 Likes

I think Herb Sutter's draft proposal for adding in/inout/out parameters to C++ seems relevant here: it's an attempt to abstract the C++ parameter passing into a bit more of a type-state approach where it knows a parameter must be assigned to, or can be passed in as either by value or reference at the compilers discretion

Here it seems like you would want to have a similar sort of definite assignment(/moved from) analysis, which implies these types shouldn't cross function boundaries (but what do I know)

Otherwise this just seems like the C++ reference type: which while handy there doesn't seem like it would work well in Rust, since it's essentially an invisible borrow.

2 Likes

Note this is also the feature being discussed as needed for Simple postfix macros by joshtriplett · Pull Request #2442 · rust-lang/rfcs · GitHub -- it wants to be able to capture something as a place if it's a place, including putting the result of an expression into a temporary place if needed, in order to be able to call methods on it naturally.

This could also be useful for fields in traits: a field in a trait could just be a const trait method that returns a place.