Extensible Schedule Graphs

[ItsDoot]

Schedules are a great tool for executing a graph of systems. In their current form, however, schedules impose a specific execution model: systems grouped into system sets with order constraints and run conditions. We should extend the scheduling API to become reusable in more scenarios.

Motivation

These problem domains involve a system graph, but have a different execution model:

• bevy_render's RenderGraph and Node APIs are shaped very similarly to a system graph, but differ in their execution model: nodes have read-only access to the world and can be executed fully in parallel, but their commands must be applied in-order. Therefore, the scheduling API cannot (yet) be reused to implement them as a system graph.
• Observers are a kind of system graph, but focusing on entities. Reusing the scheduling API would provide a more consistent API surface, and easily enable things like observer ordering (if warranted).
• My utility AI library links systems' output scores to other systems' inputs for score aggregation. Additionally, all systems have read-only access. I've copied quite a lot of the scheduling API's surface, and would love to not need to maintain it myself.
• @urben1680 has a crate for reversible schedules that could be vastly simplified if it didn't have to work around the scheduling API's imposed execution model.
• Users have occasionally shown interest in statically-dispatched schedules, and while this is easy to do with repeated calls to run_system_cached, the UX could be improved by reusing some of the scheduling API.

There are a few more examples that verge on the theoretical, but as you can see this is an open problem space.

Goals

• Provide reusable building blocks for:
  • creating and updating system graphs
  • creating serial and parallel schedule executors
• Minimize boilerplate for the most common cases.
• Enable dynamic schedule modification
• Remove barriers for building schedule inspection tooling

Non-Goals

• Provide first party solutions for all third party use cases.

Roadmap (very rough)

• Clean up bevy_ecs::schedule
  • Thoroughly document UninitializedId semantics #20080
  • Remove SystemSetNode #20100
  • Improve node encapsulation in ScheduleGraph #20119
  • Change flattened dependency graph from DiGraph<NodeId> to DiGraph<SystemKey> #20172
  • Clean up NodeId kind fetching #20196
  • Better ScheduleBuildError introspection and handling #20256
  • Move toposorting onto DiGraph directly, and cleanup error handling #21608
  • Move more functions off of ScheduleGraph #21817
  • Tidy up old SystemCondition trait hierarchy #21844
  • Pull Schedules::ignored_scheduling_ambiguities into a separate resource and avoid unnecessary allocation #21929
  • Replace BTreeMap with IndexMap for stored ScheduleBuildPasses #21930
  • Accept boxed conditions for run_if, and cleanup IntoScheduleConfigs #21977
• Improve performance of Schedule-related functions, like building.
  • Preallocate more things #21964
• Increase structure for schedule executors to reduce boilerplate and ensure consistency #18453
• Run individual SystemSets in Schedules #21893
• Expose generic system container and graph primitives
• Provide user-implementable traits to allow custom execution models
• Provide primitives for constructing serial and parallel executors for custom execution models
• Switch bevy_render to a render-graph-as-systems approach
• Support systems with In parameters in schedules #21658 / Run schedules where all systems take a certain Input type. #10335

[alice-i-cecile]

I went over this earlier today and I'm on board with this. #18453 is closely related and should be tackled before we do more complex refactors.

[urben1680]

@urben1680 has a crate for reversible schedules that could be vastly simplified if it didn't have to work around the scheduling API's imposed execution model.

To give more insight what I am doing until I actually release the crate:

• The reversible schedule can be ran in three modes: Forward, BackwardLog, ForwardLog
• Under the hood the two forward variants are one set of systems, the backward variant another set
• A new api to add to schedules with that purpose does the following:
  • Put the system into a Arc<Mutex>
  • One clone goes into the forward set
  • Another clone goes into the backward set
  • A third clone goes into the backward set too, but not as a system but as commands-emitting noop system that undoes commands that are issued by the forward system, which happens right before the actual backward system
• The api to set the system ordering and set configurations also does an equivalent but reverse config to the backward set
• Systems in both sets share their state via the Arc<Mutex> but otherwise need to bring the logic themself to run "forward" or "backward"
• A resource controls the execution direction the systems can read for their logic

The crate is intended for gameplay that is able to smoothly rewind what happened, so if there is a way to reverse a schedule (graph) by "rebuilding" it, that probably is too expensive/intrusive. What I would be interested in here is if a graph can be designed by me to be ready-to-use in both directions.