Building Bevy

This article is a personal rewriting with some substantial addition of an original tutorial.

Bevy is highly ergonomic, and coming from a language like Ruby, its interesting to explore how domain specific languages are created in more structured compile time languages like Rust.

Dependency injection

When an app is created its provided with a bunch of System which are called automatically.

These systems have many SystemParam which are what we specify in the parameters of our systems. The SystemParam each system needs are provided by the App. The App is injecting these dependencies to each System.

Dependency injection is what allows you to specify your systems as plain rust functions and declare the parameters you want injected in:

// Here we declared a `query` which is injected in by our App during a game tick
fn movement_system(query: Query<(&mut Position, &Velocity)>) {
    for (mut position, velocity) in query.iter_mut() {
        // ...
    }
}

Starting from scratch

A scheduler stores systems. We can think about them like:

struct Scheduler {
    systems: Vec<StoredSystem>,
    resources: HashMap<TypeId, Box<dyn Any>>,
}

struct StoredSystem;

One of the best features of Bevy is the fact that systems are plain rust functions:

fn hello_world_system() {
    println!("Hello world");
}

fn main() {
    App::new()
        .add_systems(Update, hello_world_system)
        .run();
}

We can imagine a simplified type signature of .add_system would be:

fn add_system<S: System>(fn: S) -> App {}

The scheduler will take these systems and try and run them in parallel to reduce the time each tick of the game takes. It does this by allowing systems that share readonly references of components to execute at the same time on different threads.

To simplify our initial scope we won’t do any borrowing types just yet. Instead we will start with just the 'static lifetime for all parameters of our systems.

Systems will be any function that takes parameters with a 'static lifetime and returns (). They will need to implement the FnMut trait as our systems will need to be passed into our application and called multiple times.

When we implment something like FnMut on a struct we are saying the System can be treated as a mutable function or closure.

A simple example of implementing FnMut would look like:

// Define a struct that implements `FnMut`
struct Counter {
    count: u32,
}

impl FnMut<()> for Counter {
    // Define the `call_mut` method required by `FnMut`
    extern "rust-call" fn call_mut(&mut self, _: ()) -> u32 {
        self.count += 1;
        self.count
    }
}

fn main() {
    let mut counter = Counter { count: 0 };

    // Call the `Counter` instance as if it were a function
    let result = counter(());

    println!("Result: {}", result); // Output: Result: 1
}

Which turns Counter the struct into something callable. Exactly the kind of behaviour we would want from our System.

A problem arises early though, rust does not allow variadic generics (generics that take a variable number of arguments). So we would have to create implementations for each number of generic arguments we would want to take:

trait System<Input> {}

// An implementation of systems that take no parameters:
impl<F: FnMut()> System<()> for F {}

// Here we implement our system with a single parameter:
impl<F: FnMut(T1), T1: 'static> System<(T1,)> for F {}

To do this in a way where we can define a single source of truth we will use a macro:

macro_rules! impl_system {
    (
        $(
            $($params:ident),+
        )?
    ) => {
        impl<
            F: FnMut(
                $( $($params),+ )?
            ) 
            $(, $($params: 'static),+ )?
        > 
        System<( 
            $( $($params,)+ )? 
        )> for F {}
    }
}

impl_system!();
impl_system!(T1);
impl_system!(T1, T2);
impl_system!(T1, T2, T3);
impl_system!(T1, T2, T3, T4);

So we can choose how many arguments we want to support using macros to define the arity of our arguments.

For our scheduler to be able to call our systems generically we would need a common interface to invoke them.

How can we have one function signature that can call any of these systems? We need to expose some way to flatten our input.

If give every system one parameter that can satisfy all of their requirements we can pass it in to every system without caring about the differences in their types.

So lets define a .run method that takes a unified resources parameter:

trait System<Input> {
    fn run(&mut self, resources: &mut HashMap<TypeId, Box<dyn Any>>);
}

Which we can then add to our macro implementation:

macro_rules! impl_system {
    (
        $(
            $($params:ident),+
        )?
    ) => {
        #[allow(non_snake_case, unused)]
        impl<
            F: FnMut(
                $( $($params),+ )?
            )
            $(, $($params: 'static),+ )?
        > 
        System<(
            $( $($params,)+ )?
        )> for F {
            fn run(&mut self, resources: &mut HashMap<TypeId, Box<dyn Any>>) {
                $($(
                    let $params = resources.remove(&TypeId::of::<$params>()).unwrap();
                )+)?

                (self)(
                    $($(params),+)?
                );
            }
        }
    }
}

So now our systems can be called without knowing their specific parameter types. Although because of our .remove call on resources we can only call each system once.

We would also like to be able to to use Box<dyn System> instead of Box<dyn Any>. One reason for this is that the std::Any type has a 'static requirement. Moving to parallel systems this way would be impossible.

However any traits we dynamically dispatch to in a Box cannot themselves be generic. So we could not do Box<dyn System<Input>>.

Every time we use a generic argument in rust like System<(T1,)> the compiler generates code specialized to the concrete type parameters you called e.g: System<(i32,)>.

Each instantiation will have their functions generated as though you handwrote the different versions. The generic implementation would inline the methods into the newly generated concrete type.

We could instead reduce this monomorphization by treating the stored type opaquely using a technique called type erasure:

trait AnimalExt {
    fn eat(&self, food: String);
}

struct Dog;

impl AnimalExt for Dog {
    fn eat(&self, food: String) {
        println!("dog: {:?}", food);
    }
}

// Instead of a generic argument we are using a smart pointer to a function.
// This way we have erased the pointer to a concrete type and are instead
// storing type-erased smart pointers (on the heap instead of the stack)
struct AnyAnimal {
    eat: Box<Fn(String)>,
}

impl AnyAnimal {
    fn new<A>(animal: A) -> Self 
    where
        A: AnimalExt + 'static,
    {
        AnyAnimal {
            eat: Box::new(move |s| animal.eat(s))
        }
    }
}

// Here we implement the trait which invokes the type-erased pointer
impl AnimalExt for AnyAnimal {
    fn eat(&self, food: String) {
        (self.eat)(food);   // ok
        // self.eat(food) <- fatal runtime error: stack overflow 
    }
}

fn main() {
    let a = AnyAnimal::new(Dog);
    a.eat("aaa".to_string());
}

Source

The idea of using a wrapper struct like AnyAnimal from the example above will also prevent inlining of the implementations of AnimalExt on any generic arguments to AnyAnimal. Its also going to provide a type-safe wrapper around it.

So now you could hold Box<AnyAnimal> instead of using Box<dyn Any>.

We could try the same thing with our own systems:

trait System<Input> {
   fn run(&mut self, resources: &mut HashMap<TypeId, Box<dyn Any>>);
}
trait ErasedSystem {
    fn run(&mut self, resources: &mut HashMap<TypeId, Box<dyn Any>>);
}

impl<S: System<I>, I> ErasedSystem for S {
    fn run(&mut self, resources: &mut HashMap<TypeId, Box<dyn Any>>) {
        <Self as System<I>>::run(self);
    }
}

However we would get a type error:

error[E0207]: the type parameter I is not constrained by the impl trait,
self type, or predicates

In Rust, when defining a generic type or function, you need to specify the constraints on the generic type parameters. These constraints limit the types we can pass as a generic argument.

In our code above we are trying to implement the ErasedSystem trait for any type S that implements the System<I> trait where I is a generic type parameter. However because we don’t have any constraints on I the compiler cannot guarantee the implementation is valid for all possible types of I.

Because our systems can implement multiple traits such as FnMut(T) or FnMut(T, U) we would need to be specific about which one I could be.

Looking back at our original system definition:

trait System<Input> {}

// An implementation of systems that take no parameters:
impl<F: FnMut()> System<()> for F {}

// Here we implement our system with a single parameter:
impl<F: FnMut(T1), T1: 'static> System<(T1,)> for F {}

Remember that I is the Input of our system, which is a tuple of one or more types, representing the arguments our system will declare and want to be fed in.

While F can implement multiple FnMut traits, if we wrap F in a struct then that struct can “select” a specific implementation. In this way the compiler is not generating variations of the implementation depending on F but is instead dynamically invoking the argument F which would erase the type requirement from our System and move it into the new struct.

The implementation the struct chooses is whichever matches the struct’s generic parameters, which only one implementation can do.

struct FunctionSystem<Input, F> {
    f: F,
    // we need a marker because otherwise we're not using `Input`.
    // fn() -> Input is chosen because just using Input would not be `Send` + `Sync`,
    // but the fnptr is always `Send` + `Sync`.
    marker: PhantomData<fn() -> Input>,
}

Now let’s move System from being on the function itself to FunctionSystem:

trait System {
    fn run(&mut self, resources: &mut HashMap<TypeId, Box<dyn Any>>);
}

macro_rules! impl_system {
    (
        $( 
            $($params:ident),+
        )?
    ) => {
        #[allow(non_snake_case, unused)]
        impl<
            F: FnMut(
                $( $($params),+ )?
            ) 
            $(, $($params: 'static),+ )?
        > System for FunctionSystem<($( $($params,)+ )?), F> {
            fn run(&mut self, resources: &mut HashMap<TypeId, Box<dyn Any>>) {
                $($(
                    let $params = *resources.remove(&TypeId::of::<$params>()).unwrap().downcast::<$params>().unwrap();
                )+)?

                (self.f)(
                    $($($params),+)?
                );
            }
        }
    }
}

Now that System takes no associated types or generic parameters, we can box it easily:

trait System {}
type StoredSystem = Box<dyn System>;

We’ll also want to be able to convert FnMut(...) to a system easily instead of manually initializing our FunctionSystem struct each time:

trait IntoSystem<Input> {
    type System: System;

    // Wrap ourself into the type of System above
    fn into_system(self) -> Self::System;
}

// Example output:
// impl<F: FnMut(T1), T1> IntoSystem<(T1,)> for F {
//     type System = FunctionSystem<(T1,), Self>;

//     fn into_system(self) -> Self::System {
//         FunctionSystem {
//             f: self,
//             marker: Default::default(),
//         }
//     }
// }

macro_rules! impl_into_system {
    (
        $($(
                $params:ident
        ),+)?
    ) => {
        impl<F: FnMut($($($params),+)?) $(, $($params: 'static),+ )?> IntoSystem<( $($($params,)+)? )> for F {
            type System = FunctionSystem<( $($($params,)+)? ), Self>;

            fn into_system(self) -> Self::System {
                FunctionSystem {
                    f: self,
                    marker: Default::default(),
                }
            }
        }
    }
}

impl_into_system!();
impl_into_system!(T1);
impl_into_system!(T1, T2);
impl_into_system!(T1, T2, T3);
impl_into_system!(T1, T2, T3, T4);

Now we can start to define the public API of our scheduler to add these systems to our game loop:

struct Scheduler {
   systems: Vec<StoredSystem>,
   resources: HashMap<TypeId, Box<dyn Any>>,
}

trait IntoSystem<Input> {
   type System: System;

   fn into_system(self) -> Self::System;
}

impl Scheduler {
    pub fn run(&mut self) {
        for system in self.systems.iter_mut() {
            system.run(&mut self.resources);
        }
    }

    pub fn add_system<I, S: System + 'static>(&mut self, system: impl IntoSystem<I, System = S>) {
        self.systems.push(Box::new(system.into_system()));
    }

    pub fn add_resource<R: 'static>(&mut self, res: R) {
        self.resources.insert(TypeId::of::<R>(), Box::new(res));
    }
}

This would let us define our first real working system:

fn main() {
    let mut scheduler = Scheduler {
        systems: vec![],
        resources: HashMap::default(),
    };

    scheduler.add_system(foo);
    scheduler.add_resource(12i32);

    scheduler.run();
}

fn foo(int: i32) {
    println!("int! {int}");
}

However we still cannot use borrowed types. As it stands resources are consumed every game tick. If we lifted our maximum limit on system parameters…

We could start by changing .run to return resource references:

let $params = resources.get(&TypeId::of::<$params>()).unwrap().downcast_ref::<$params>().unwrap();

// We would also need to change our impl on IntoSystem

//  adding & here v
impl<F: FnMut($($(& $params),+)?) $(, $($params: 'static),+ )?> IntoSystem<( $($($params,)+)? )> for F { ... }

But our function definition above would fail:

error[E0277]: the trait bound fn(i32) {foo}: IntoSystem<_> is not satisfied

Which we could fix this by using only readonly references according to our new IntoSystem definition:

fn foo(int: &i32) {
    println!("int! {int}");
}

But this would again break if we introduced mutable references. Manually implementing the possible combinations would be 3^n for every n parameters we would want to support. Even with macros this would become unreasonable (by increasing the compile time and size of the program).

Instead we could try to abstract over all possible system parameters:

trait SystemParam {
    fn retrieve(resources: &mut HashMap<TypeId, Box<dyn Any>>) -> Self;
}

struct Res<'a, T: 'static> {
    value: &'a T,
}

impl<'a, T: 'static> SystemParam for Res<'a, T> {
    fn retrieve(resources: &mut HashMap<TypeId, Box<dyn Any>>) -> Self {
        let value = resources.get(&TypeId::of::<T>()).unwrap().downcast_ref::<T>().unwrap();
        Res { value }
    }
}

struct ResMut<'a, T: 'static> {
    value: &'a mut T,
}

impl<'a, T: 'static> SystemParam for ResMut<'a, T> {
    fn retrieve(resources: &mut HashMap<TypeId, Box<dyn Any>>) -> Self {
        let value = resources.get_mut(&TypeId::of::<T>()).unwrap().downcast_mut::<T>().unwrap();
        ResMut { value }
    }
}

struct ResOwned<T: 'static> {
    value: T
}

impl<T: 'static> SystemParam for ResOwned<T> {
    fn retrieve(resources: &mut HashMap<TypeId, Box<dyn Any>>) -> Self {
        let value = *resources.remove(&TypeId::of::<T>()).unwrap().downcast::<T>().unwrap();
        ResOwned { value }
    }
}

Here we are using different types to implement our non-generic trait SystemParam.

However compiling and trying to use a borrowed reference will give us:

error: lifetime may not live long enough

We could introduce lifetimes to our implementations of SystemParam but that would change the signature to:

trait SystemParam<'a> {
    fn retrieve(resources: &'a mut HashMap<TypeId, Box<dyn Any>>) -> Self;
}

Which would then require lifetimes introduced for System, IntoSystem, StoredSystem and .add_system.

But because we are mutably borrowing resources multiple times for variants with > 1 parameters, we would get a borrowing error:

error[E0499]: cannot borrow *resources as mutable more than once at a time

And implementing something like:

impl<'a, T: 'static> SystemParam<'a> for Res<'a, T> {
    fn retrieve(resources: &'a HashMap<TypeId, Box<dyn Any>>) -> Self {
        let value = resources.get(&TypeId::of::<T>()).unwrap().downcast_ref::<T>().unwrap();
        Res { value }
    }
}

pub fn add_system<I, S: for<'a> System<'a> + 'static>(&mut self, system: impl for<'a> IntoSystem<'a, I, System = S>) {
    self.systems.push(Box::new(system.into_system()));
}

Would lead to an error of:

error: implementation of System is not general enough

Because our .add_system defines the system parameter as impl for<'a> IntoSystem<'a, I, System = S> the for<'a> implies that IntoSystem<'a, I, System = S> must outlive all lifetimes, including 'static'.

As of October, 2022 the Rust community is working on these kind of lifetime problems: https://blog.rust-lang.org/2022/10/28/gats-stabilization.html

Lets have a look at what Bevy does to get around these kinds of problems:

pub unsafe trait SystemParam: Sized {
    // Used to store data which persists across invocations of a system.
    type State: Send + Sync + 'static;

    // The item type returned when constructing this system param.
    // The value of this associated type should be `Self`, instantiated with new lifetimes.
    //
    // You could think of `SystemParam::Item<'w, 's>` as being an *operation* that changes the lifetimes bound to `Self`.
    type Item<'world, 'state>: SystemParam<State = Self::State>;

    // ...
}

So SystemParam is using a GAT called Item which is itself a SystemParam, but it has a different lifetime. That means we are taking the functions lifetime and giving it the new lifetime of the passed resource.

Generic associated types (GAT) allow you to have generics (type, lifetime, or const) on associated types.

So we can use the same kind of trick for our simplified version:

trait SystemParam {
    type Item<'new>;

    fn retrieve<'r>(resources: &'r HashMap<TypeId, Box<dyn Any>>) -> Self::Item<'r>;
}

impl<'res, T: 'static> SystemParam for Res<'res, T> {
    type Item<'new> = Res<'new, T>;

    fn retrieve<'r>(resources: &'r HashMap<TypeId, Box<dyn Any>>) -> Self::Item<'r> {
        Res { value: resources.get(&TypeId::of::<T>()).unwrap().downcast_ref().unwrap() }
    }
}

macro_rules! impl_system {
    (
        $($params:ident),*
    ) => {
        #[allow(non_snake_case)]
        #[allow(unused)]
        impl<F, $($params: SystemParam),*> System for FunctionSystem<($($params,)*), F> 
            where
                for<'a, 'b> &'a mut F: 
                    FnMut( $($params),* ) + 
                    FnMut( $(<$params as SystemParam>::Item<'b>),* )
        {
            fn run(&mut self, resources: &mut HashMap<TypeId, Box<dyn Any>>) {
                // This call_inner is necessary to tell rust which function impl
                // to call
                fn call_inner<$($params),*>(
                    mut f: impl FnMut($($params),*),
                    $($params: $params),*
                ) {
                    f($($params),*)
                }

                $(
                    let $params = $params::retrieve(resources);
                )*

                call_inner(&mut self.f, $($params),*)
            }
        }
    }
}

macro_rules! impl_into_system {
    (
        $($params:ident),*
    ) => {
        impl<F, $($params: SystemParam),*> IntoSystem<($($params,)*)> for F 
            where
                for<'a, 'b> &'a mut F: 
                    FnMut( $($params),* ) + 
                    FnMut( $(<$params as SystemParam>::Item<'b>),* )
        {
            type System = FunctionSystem<($($params,)*), Self>;

            fn into_system(self) -> Self::System {
                FunctionSystem {
                    f: self,
                    marker: Default::default(),
                }
            }
        }
    }
}

Now that we have SystemParam in place, it’ll be easy to expand this to work with unlimited parameters.

We just need one crucial idea: what if a tuple of SystemParam is, itself, a SystemParam? Let’s implement:

impl<T1: SystemParam, T2: SystemParam> SystemParam for (T1, T2) {
    type Item<'new> = (T1::Item<'new>, T2::Item<'new>);

    fn retrieve<'r>(resources: &'r HashMap<TypeId, Box<dyn Any>>) -> Self::Item<'r> {
        (
            T1::retrieve(resources),
            T2::retrieve(resources),
        )
    }
}

fn foo(int: (Res<i32>, Res<u32>)) {
    println!("int! {} uint! {}", int.0.value, int.1.value);
}

Even though it looks like we have defined an implementation for a tuple of two SystemParam, the recursion actually allows us to have unlimited:

fn foo(int: (Res<One>, (Res<Two>, (Res<Three>, (Res<Four>))))) {
    // ...
}

It would however be a bit cumbersome to only allow nested tuples and a max of two positional arguments, so we should update our macro and choose exactly how many arguments to support (Bevy chose 15):

macro_rules! impl_system_param {
    (
        $($params:ident),*
    ) => {
        #[allow(unused)]
        impl<$($params: SystemParam),*> SystemParam for ($($params,)*) {
            type Item<'new> = ($($params::Item<'new>,)*);

            fn retrieve<'r>(resources: &'r HashMap<TypeId, Box<dyn Any>>) -> Self::Item<'r> {
                (
                    $($params::retrieve(resources),)*
                )
            }
        }
    }
}

impl_system_param!();
impl_system_param!(T1);
impl_system_param!(T1, T2);
impl_system_param!(T1, T2, T3);
// and so on

https://promethia-27.github.io/dependency_injection_like_bevy_from_scratch/introductions.html

Tainted ^\_\ `Coders`

Building Bevy

Dependency injection

Starting from scratch

Read more