Schedule systems based on their declared dependencies

[libs/game.git] / source / game / systemscheduler.cpp

diff --git a/source/game/systemscheduler.cpp b/source/game/systemscheduler.cpp
new file mode 100644 (file)
index 0000000..d6fb9a5
--- /dev/null
+++ b/source/game/systemscheduler.cpp
@@ -0,0 +1,154 @@
+#include "systemscheduler.h"
+#include <limits>
+#include <msp/core/algorithm.h>
+#include <msp/strings/format.h>
+#include "system.h"
+
+using namespace std;
+
+namespace Msp::Game {
+
+SystemScheduler::SystemScheduler(Reflection::Reflector &r):
+       reflector(r)
+{ }
+
+void SystemScheduler::add_system(System &s)
+{
+       nodes.emplace_back(&s, reflector.find_class(typeid(s)));
+}
+
+void SystemScheduler::remove_system(System &s)
+{
+       erase_if(nodes, [&s](const GraphNode &n){ return n.system==&s; });
+       for(auto i=groups.begin(); i!=groups.end(); )
+       {
+               erase_if(i->systems, [&s](System *gs){ return gs==&s; });
+               if(i->systems.empty())
+                       i = groups.erase(i);
+               else
+                       ++i;
+       }
+}
+
+void SystemScheduler::schedule()
+{
+       for(GraphNode &n: nodes)
+       {
+               n.scheduled_order = ~0U;
+               n.predecessors.clear();
+       }
+
+       for(auto i=nodes.begin(); i!=nodes.end(); ++i)
+               for(auto j=i; ++j!=nodes.end(); )
+               {
+                       int order = get_order(*i, *j);
+                       if(order<0)
+                               j->predecessors.push_back(&*i);
+                       else if(order>0)
+                               i->predecessors.push_back(&*j);
+               }
+
+       groups.clear();
+       unsigned unscheduled_count = nodes.size();
+       while(unscheduled_count)
+       {
+               unsigned order = groups.size();
+               Group &group = groups.emplace_back();
+               for(GraphNode &n: nodes)
+                       if(!~n.scheduled_order && ranges::all_of(n.predecessors, [order](GraphNode *p){ return p->scheduled_order<order; }))
+                       {
+                               group.systems.push_back(n.system);
+                               n.scheduled_order = order;
+                               --unscheduled_count;
+                       }
+       }
+}
+
+int SystemScheduler::get_order(const GraphNode &node1, const GraphNode &node2)
+{
+       if(int order = get_explicit_order(node1, node2))
+               return order;
+       return get_data_order(node1, node2);
+}
+
+int SystemScheduler::get_explicit_order(const GraphNode &node1, const GraphNode &node2)
+{
+       const vector<System::Dependency> &deps1 = node1.system->get_dependencies();
+       const vector<System::Dependency> &deps2 = node2.system->get_dependencies();
+
+       auto get_dep_type = [](const System::Dependency &d){ return &d.get_type(); };
+       auto i = ranges::find(deps1, node2.type, get_dep_type);
+       int flags1 = (i!=deps1.end() ? i->get_flags()&System::ORDER_MASK : 0);
+       i = ranges::find(deps2, node1.type, get_dep_type);
+       int flags2 = (i!=deps2.end() ? i->get_flags()&System::ORDER_MASK : 0);
+       if(flags1&flags2)
+               throw scheduling_error(format("Conflicting ordering between %s and %s", node1.type->get_name(), node2.type->get_name()));
+       else if(flags1==System::RUN_BEFORE || flags2==System::RUN_AFTER)
+               return -1;
+       else if(flags1==System::RUN_AFTER || flags2==System::RUN_BEFORE)
+               return 1;
+       else
+               return 0;
+}
+
+int SystemScheduler::get_data_order(const GraphNode &node1, const GraphNode &node2)
+{
+       int data_order = 0;
+       const Reflection::ClassBase *ordered_data = nullptr;
+       const Reflection::ClassBase *unordered_data = nullptr;
+       for(const System::Dependency &d1: node1.system->get_dependencies())
+       {
+               int flags1 = d1.get_flags()&System::DATA_MASK;
+               if(!flags1)
+                       continue;
+
+               for(const System::Dependency &d2: node2.system->get_dependencies())
+               {
+                       int flags2 = d2.get_flags()&System::DATA_MASK;
+                       if(!flags2)
+                               continue;
+
+                       const Reflection::ClassBase *common_type = nullptr;
+                       if(&d1.get_type()==&d2.get_type() || d1.get_type().is_base_of(d2.get_type()))
+                               common_type = &d1.get_type();
+                       else if(d2.get_type().is_base_of(d1.get_type()))
+                               common_type = &d2.get_type();
+                       else
+                               continue;
+
+                       int order = 0;
+                       // Read-only access to old data always comes first
+                       if(flags1==System::READ_OLD)
+                               order = -1;
+                       else if(flags2==System::READ_OLD)
+                               order = 1;
+                       // Read-only access to fresh data always comes last
+                       else if(flags1==System::READ_FRESH)
+                               order = 1;
+                       else if(flags2==System::READ_FRESH)
+                               order = -1;
+                       // Chained updates always come after non-chained writes
+                       else if(flags1==System::CHAINED_UPDATE && (flags2==System::WRITE || flags2==System::UPDATE))
+                               order = 1;
+                       else if(flags2==System::CHAINED_UPDATE && (flags1==System::WRITE || flags1==System::UPDATE))
+                               order = -1;
+                       else
+                               unordered_data = common_type;
+
+                       if(order && data_order && order!=data_order)
+                               throw scheduling_error(format("Ambiguous data ordering between %s and %s, accessing %s and %s",
+                                       node1.type->get_name(), node2.type->get_name(), ordered_data->get_name(), common_type->get_name()));
+
+                       data_order = order;
+                       ordered_data = common_type;
+               }
+       }
+
+       if(!data_order && unordered_data)
+               throw scheduling_error(format("Ambiguous data ordering between %s and %s, accessing %s",
+                       node1.type->get_name(), node2.type->get_name(), unordered_data->get_name()));
+
+       return data_order;
+}
+
+} // namespace Msp::Game