The future of path reflection in bevy

[nicopap]

Time to unveil my grand vision for the next level of perfection for reflection.

GetPath evolution

In the past, bevy only supported &str as path as argument to the GetPath trait methods.

Then, we introduced ParsedPath, this allowed pre-parsing paths in order to not have to parse a &str each time the field is accessed.

Then, we introduced ReflectPath, a trait to abstract over the path used in GetPath trait methods.

What is the way forward? What's next?

Remove heap allocation

ParsedPath is a Box<[(Access, usize)]>. It requires heap allocation. But in truth, most paths created in bevy are single field accessors.

We could convert the Box<[(Access, usize)]> into a SmallVec<[Access; 1]> (IMO the usize is a heavy cost we absolutely do not need to pay), but then, what if someone wants a ParsedPath that works mostly well with 2+ elements?

Instead, we generalize ParsedPath over the storage medium. This way, we let users decide what kind of optimization they want.

Offset-based accessors

But there is even better. We got rid of one level of indirection by using a stack-allocated array. But there is still a few indirections involved.

A problem of ParsedPath (and the &str-based GetPath) is that it calls a method on a trait object (on &dyn Reflect to be precise). It is not slow, but it's still the overhead of a table lookup, and a mandatory function call, even if the function body is tinny.

Take an animation system, it might do several hundreds — if not thousands — of field accesses per frames. Now suddenly this tinny overhead is a massive headache!

But we don't need to call the trait object method. We could just… you know… build the pointer. Basically, we take the address of the parent object, we add the offset of the field to it, and we have the address of the field.

Even better: a field of a field of a field is their offsets added together! We don't even need an array to represent path access.

Well, there are caveats. Pointers, for one. The address of the value of a Box<T> is not an offset from the struct containing it, it is the value of the field within the struct (ok, it's a bit complicated to explain at this point. If you are confused, the Kernighan and Ritchie "C programming language" is a good starting point)

Another caveat: With the trait object approach, we are always guaranteed to have the right accessors for our types. If we store an offset (a mere usize), we "erase" the type, we've no idea what type we should be accessing and what type the field we are accessing is. This is pretty bad, using an accessor with the wrong type is like using transmute willy-nilly!

There are a few ways to make sure we use accessors with the correct types:

• Associate the offset-based accessor with the type it accesses and dereferences with an additional PhantomData<(Src, Trgt)> field, allowing to encode the association in the type system
• Make a lot of assumptions and use unsafes, but swearing you know what you are doing, you know?
• Associate the accessor with two TypeIds (Source and Target), check at runtime we are accessing the correct types.

In truth. each approach has advantages and tradeoffs. Depending on the use-case, one is better than the other, and vis-versa. In fact ¿Por qué not los tres? We have ReflectPath, if they all implement ReflectPath, they are drop-in replacement for each other.

Pretty neat eh?

The path to the new path

• We need to add offset and "is this a pointer" information to our reflection API. There is a few discussions on how it is possible to access this information in stable rust.
• With that information available, moving to the next step of path reflection is just a very small jump

In fact, at one point, I had a fork of bevy with this idea partially implemented, but I must have mislaid it.

[MrGVSV]

I think the animation use-case is super important here since, so others are aware, it's been proposed to have reflection power animation. And this seems like it could help improve performance by a lot.

I'll be honest, I'm not much of a low level programmer so I don't fully understand the tradeoffs and limitations. How do we access the offset information? And how do we know that the offset is correct? For example, are there any concerns around padding, #[repr] types, build targets, or anything like that?

You also mentioned pointers being the caveat to the pure-offset pattern. How would we want to handle those for things like nested fields (e.g. like, offset -> pointer -> offset)? And are there other types that might be an issue like maps or linked lists?

Lastly, do you have any pseudo code of the basic architecture of what you're thinking? It might help my tiny brain others understand what's really being proposed. Especially for the needed reflection API changes.

[nicopap]

I wrote this post in the context of designing an animation system. But I found another interesting option (for my use-case)

Alternative animation implementation

Specifically, I am focusing on f32 animations.

• Have a trait Point<const N: usize> trait, with a fn to_array(self) -> [f32; N] method.
• Have a trait Projection<const N: usize> with a fn(n: [f32; N], component: &mut T) method, to update a T based on a specific point in the animation timeline.

Now, combining the two traits, I can have a fairly efficient setup for animations! But it depends on rust code, and you can't really serialize the "projection" (ie: how a curve is applied to components). Which I think is a pretty compelling feature.

---

I think offset-based paths are fundamentally more limited than the reflection-based ones. I don't think it's possible to apply it to all kind of types. I imagine a new method on NamedField and UnnamedField that returns the offset.

Something like the following (click text to expand):

Trial implementation of OffsetPath

In a proper implementation, I would extract the tail offset in its own field, so that OffsetPath works like a non-empty list.

// The N - 1 first elements of SmallVec are offsets to pointers to dereference
// while the last element is the offset of the final field.
struct OffsetPath<Src, Trg>(SmallVec<[usize; 2]>, PhantomData<fn(Src) -> Trg>);

impl<Src, Trg> OffsetPath<Src, Trg> {
    fn get(&self, src: &Src) -> &Trg {
        let trg_ptr = src as *const _;
        let mut trg_ptr = trg_ptr.cast::<u8>();
        let (&field_offset, dereference_offsets) = self.0.split_last().unwrap();
        for &offset in dereference_offsets {
            trg_ptr = unsafe { trg_ptr.add(offset) };
            trg_ptr = unsafe { ptr::read(trg_ptr) };
        }
        trg_ptr = unsafe { trg_ptr.add(field_offset) };
        unsafe { trg_ptr.cast::<Trg>().as_ref().unwrap_unchecked() }
    }
}
// Src: source type, Trg: ~~tardigrade~~ target type
fn offset_path<Src: Typed, Trg>(path: &[Access], reg: &TypeRegistry) -> Option<OffsetPath<Src, Trg>> {
    let mut offsets = SmallVec::new();
    let mut current_offset = 0;
    let mut src_type = Src::type_info();
    for (i, access) in path.iter().enumerate() {
        match (acces, src_type) {
            (Access::Field(field), TypeInfo::Struct(info)) => {
                let info = info.field(field).unwrap();
                // new method: NamedField::offset
                match info.offset() {
                    Offset::Inline(offset) => current_offset += offset,
                    Offset::PtrAt(offset) if i == path.len() - 1 => current_offset += offset,
                    Offset::PtrAt(ptr_offset) => {
                        offsets.push(current_offset + ptr_offset);
                        current_offset = 0;
                    }
                    Offset::Unaddressable => return None,
                }
                src_type = reg.get_type_info(info.type_id()).unwrap();

            }
            // This would work for Struct, TupleStruct, Array, Tuple
            // Note that we do not check the enum variant in OffsetPath::get
            // we could imagine a different type that does runtime check
            // for enums though
        }
    }
    assert!(src_type.type_id() == std::any::TypeId::of::<Trg>());
    offsets.push(current_offset);
    Some(Self(offsets, PhantomData))
}

---

This is the version that uses the type system to ensure safety. The version that uses the TypeId would store the soruce and target type's ids, accept a &dyn Reflect and verify the output of .type_id().

Finally, the fully unsafe version would ignore all of those and only expose an unsafe method to access the fields.

As of how to get the offset. It's actually possible.

Here is how you get the offset in stable rust

It looks unsound, but as far as I can tell, it's safe 🙈

/// An expression that get the offset of provided `field` in `reflect_struct`.
///
/// ## Is this safe?
///
/// The [type-layout reference page] mentions that type layouts may change
/// between compilation runs, but doesn't explicitly state that it may change
/// within the same compilation run.
///
/// With this code, we do compute the offset per compilation run. And there is
/// no safe way to get access to the offset value. So we are fine on the
/// aspect of inter-compilation layout.
///
/// We use `MaybeUninit` to avoid creating an initial value to compute the offset.
/// This way, we do not need a `Default` value that may be semantically wrong or costly to generate.
///
/// The [`MaybeUninit` docs] specifically describes how to do this safely, and
/// this is how we get that offset.
///
/// [type-layout reference page]: https://doc.rust-lang.org/reference/type-layout.html
/// [`MaybeUninit` docs]: https://doc.rust-lang.org/stable/std/mem/union.MaybeUninit.html#initializing-a-struct-field-by-field
fn field_offset(field: &StructField) -> TokenStream2 {
    let access = ident_or_index(field.data.ident.as_ref(), field.index);
    quote! {{
        let uninit = #FQMaybeUninit::<Self>::uninit();
        let struct_ptr = uninit.as_ptr();
        // TODO: the docs recommends this, so it's probably safe
        let field_ptr = unsafe { ::core::ptr::addr_of!((*struct_ptr).#access) };

        let struct_ptr = struct_ptr as *const u8;
        let field_ptr = field_ptr as *const u8;

        // SAFETY (https://doc.rust-lang.org/stable/std/primitive.pointer.html#safety-5):
        // - field_ptr and struct_ptr are from the `uninit` allocated object
        // - the pointers are `*const u8` therefor, their value is always a multiple of 1,
        //   the size of a `u8`.
        // - This is a derive on a rust struct, therefore the difference
        //   between struct_ptr and field_ptr never exceeds `isize`
        unsafe { field_ptr.offset_from(struct_ptr) }
    }}
}

---

There should be no issue with padding and repr. It should work with any rust type. I give the caveats in the comments of the field_offset code.

Also note that it would be impossible to deal with non-owned fields, (such as non-static references) because there is now way to keep track of any lifetime outside of the one of the whole struct.

I don't think supporting hash maps is possible, since the address of the same key can change at runtime. Linked lists do not make sense due to the enum limitation. In any case, it's the same problem as with hash maps: the address of the same key can change at runtime. For arrays or Vecs, it seems possible to have offset of the Vec's pointer field THEN size_of::<T>() * index. For fixed size stack arrays like [f32; 32], it works like a field.

More fine-grained accessors

We can also imagine a OffsetPath that do not support pointer dereferencing, in which case we can encode them as a single usize. And it would make the compiler very happy, as now it is a single instruction to go from base struct to the accessed field. Another OffsetPath could keep track of enum variant and check them, to add support for enums etc.

For an animation system, I expect we would want the non-dereferencing OffsetPath, as animated fields and components are usually plain-old-data, and we want the least amount of instructions for going from component to field (1 being exactly the minimal amount).