Tainted\\Coders

Building Bevy

Bevy version: 0.14Last updated:
  1. Dependency injection
  2. Starting from scratch
  3. Creating callable systems
  4. Handling variadic generics
  5. Calling systems generically
  6. Erasing types
  7. Converting functions to systems
  8. Handling mutable borrowing
  9. Unlocking unlimited parameters

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

Bevy has a highly ergonomic way of us adding systems. They look like normal rust functions with some special parameter types:

// 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 {
    // ...
  }
}

We then schedule these systems into our App which will run them at a specific part of our main loop:

fn main() {
  App::new()
    .add_plugins(DefaultPlugins)
    .add_systems(Update, movement_system)
    .run();
}

Interestingly, we never provided the query explicitly to our movement_system. Somehow our App knows to pass that query with those specific components to our system at runtime.

This post is an exploration of how exactly Bevy accomplishes this using a technique called dependency injection.

Dependency injection

Before we said that our systems are normal rust functions, but that's not quite true. Each system takes only parameters that implement the SystemParam trait.

Every SystemParam has two associated types:

  1. State which is used to store persistent data
  2. Item which is what gets returned when constructing the system param

When your game loops, Bevy will use the Item to construct another instance of your system parameter with new lifetimes. The item is extending the lifetimes that are bound to your SystemParam.

So instead of us initializing this state within our functions, Bevy passes them in. It figures out how to construct them from the types we specify.

To actually implement dependency injection in Rust we would use traits. For example, lets create a logger trait:

trait Logger {
  fn log(&self, message: &str);
}

Then we can have as many implementations of a logger that we want:

struct ConsoleLogger;

impl Logger for ConsoleLogger {
  fn log(&self, message: &str) {
    println!("{}", message);
  }
}

Later, we can imagine something that needs a logger:

struct DoSomething<T: Logger> {
  logger: T,
}

impl<T: Logger> DoSomething<T> {
  fn new(logger: T) -> Self {
    Self { logger }
  }

  fn perform_action(&self) {
    self.logger.log("Action performed.");
  }
}

The important part is that the DoSomething implementation does not depend on any specific Logger, just that whatever it receives acts as a logger.

This is dependency injection.

Starting from scratch

To start, we need a place to store our systems and resources. Let's call it a Scheduler:

use std::any::{Any, TypeId};
use std::collections::HashMap;

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

struct StoredSystem;

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 ().

Creating callable systems

To allow us to pass our systems around and have them be callable we will need to implement FnMut.

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
}

Implementing FnMut turns the Counter struct into something callable. Exactly the kind of behavior we would want from our System.

This seems simple enough, but we quickly run into one of the core limitations of rust: no variadic generics. So we can't have generic types with a variable number of arguments.

Handling variadic generics

So unfortunately, we would need to create implementations for each number of generic arguments we want our systems 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 {}

// etc...

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);
// ... etc

This macro will be expanded at compile time to become exactly what we had before. When we make any changes we only have to change the macro, and not each of the implementations.

Calling systems generically

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 by providing a single parameter that satisfies all implementations. That way our caller doesn't have to care about the specific types of each system.

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),+)?
        );
      }
    }
  }
}

Now our systems can be called without knowing their specific parameter types.

We would also like to be able to to use Box<dyn System> instead of Box<dyn Any>.

The dyn Any just means we want some kind of object that implements the Any trait, but we won't know the exact type until runtime.

std::Any type has a 'static requirement, which makes moving to parallel systems 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 physically typed out the different versions. The generic implementation would inline the methods into the newly generated concrete type.

Erasing types

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

// https://gist.github.com/335g/42f61a8ca0fbb845e134db675d13cc7b
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());
}

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:

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>;

Converting functions to systems

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...

Handling mutable borrowing

Assuming we chose to have our .run return resource references, our current implementation would fail:

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

We don't get this error when we write a system that uses only read-only references, only mutable borrowing will trigger the error.

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 as many parameters as we want.

Unlocking 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