source/game/systemscheduler.cpp

   1 #include "systemscheduler.h"
   2 #include <limits>
   3 #include <msp/core/algorithm.h>
   4 #include <msp/strings/format.h>
   5 #include "system.h"
   6
   7 using namespace std;
   8
   9 namespace Msp::Game {
  10
  11 SystemScheduler::SystemScheduler(Reflection::Reflector &r):
  12         reflector(r)
  13 { }
  14
  15 void SystemScheduler::add_system(System &s)
  16 {
  17         nodes.emplace_back(&s, reflector.find_class(typeid(s)));
  18 }
  19
  20 void SystemScheduler::remove_system(System &s)
  21 {
  22         erase_if(nodes, [&s](const GraphNode &n){ return n.system==&s; });
  23         for(auto i=groups.begin(); i!=groups.end(); )
  24         {
  25                 erase_if(i->systems, [&s](System *gs){ return gs==&s; });
  26                 if(i->systems.empty())
  27                         i = groups.erase(i);
  28                 else
  29                         ++i;
  30         }
  31 }
  32
  33 void SystemScheduler::schedule()
  34 {
  35         for(GraphNode &n: nodes)
  36         {
  37                 n.scheduled_order = ~0U;
  38                 n.predecessors.clear();
  39         }
  40
  41         for(auto i=nodes.begin(); i!=nodes.end(); ++i)
  42                 for(auto j=i; ++j!=nodes.end(); )
  43                 {
  44                         int order = get_order(*i, *j);
  45                         if(order<0)
  46                                 j->predecessors.push_back(&*i);
  47                         else if(order>0)
  48                                 i->predecessors.push_back(&*j);
  49                 }
  50
  51         groups.clear();
  52         unsigned unscheduled_count = nodes.size();
  53         while(unscheduled_count)
  54         {
  55                 unsigned order = groups.size();
  56                 Group &group = groups.emplace_back();
  57                 for(GraphNode &n: nodes)
  58                         if(!~n.scheduled_order && ranges::all_of(n.predecessors, [order](GraphNode *p){ return p->scheduled_order<order; }))
  59                         {
  60                                 group.systems.push_back(n.system);
  61                                 n.scheduled_order = order;
  62                                 --unscheduled_count;
  63                         }
  64         }
  65 }
  66
  67 int SystemScheduler::get_order(const GraphNode &node1, const GraphNode &node2)
  68 {
  69         if(int order = get_explicit_order(node1, node2))
  70                 return order;
  71         return get_data_order(node1, node2);
  72 }
  73
  74 int SystemScheduler::get_explicit_order(const GraphNode &node1, const GraphNode &node2)
  75 {
  76         const vector<System::Dependency> &deps1 = node1.system->get_dependencies();
  77         const vector<System::Dependency> &deps2 = node2.system->get_dependencies();
  78
  79         auto get_dep_type = [](const System::Dependency &d){ return &d.get_type(); };
  80         auto i = ranges::find(deps1, node2.type, get_dep_type);
  81         int flags1 = (i!=deps1.end() ? i->get_flags()&System::ORDER_MASK : 0);
  82         i = ranges::find(deps2, node1.type, get_dep_type);
  83         int flags2 = (i!=deps2.end() ? i->get_flags()&System::ORDER_MASK : 0);
  84         if(flags1&flags2)
  85                 throw scheduling_error(format("Conflicting ordering between %s and %s", node1.type->get_name(), node2.type->get_name()));
  86         else if(flags1==System::RUN_BEFORE || flags2==System::RUN_AFTER)
  87                 return -1;
  88         else if(flags1==System::RUN_AFTER || flags2==System::RUN_BEFORE)
  89                 return 1;
  90         else
  91                 return 0;
  92 }
  93
  94 int SystemScheduler::get_data_order(const GraphNode &node1, const GraphNode &node2)
  95 {
  96         int data_order = 0;
  97         const Reflection::ClassBase *ordered_data = nullptr;
  98         const Reflection::ClassBase *unordered_data = nullptr;
  99         for(const System::Dependency &d1: node1.system->get_dependencies())
 100         {
 101                 int flags1 = d1.get_flags()&System::DATA_MASK;
 102                 if(!flags1)
 103                         continue;
 104
 105                 for(const System::Dependency &d2: node2.system->get_dependencies())
 106                 {
 107                         int flags2 = d2.get_flags()&System::DATA_MASK;
 108                         if(!flags2)
 109                                 continue;
 110
 111                         const Reflection::ClassBase *common_type = nullptr;
 112                         if(&d1.get_type()==&d2.get_type() || d1.get_type().is_base_of(d2.get_type()))
 113                                 common_type = &d1.get_type();
 114                         else if(d2.get_type().is_base_of(d1.get_type()))
 115                                 common_type = &d2.get_type();
 116                         else
 117                                 continue;
 118
 119                         int order = 0;
 120                         // Read-only access to old data always comes first
 121                         if(flags1==System::READ_OLD)
 122                                 order = -1;
 123                         else if(flags2==System::READ_OLD)
 124                                 order = 1;
 125                         // Read-only access to fresh data always comes last
 126                         else if(flags1==System::READ_FRESH)
 127                                 order = 1;
 128                         else if(flags2==System::READ_FRESH)
 129                                 order = -1;
 130                         // Chained updates always come after non-chained writes
 131                         else if(flags1==System::CHAINED_UPDATE && (flags2==System::WRITE || flags2==System::UPDATE))
 132                                 order = 1;
 133                         else if(flags2==System::CHAINED_UPDATE && (flags1==System::WRITE || flags1==System::UPDATE))
 134                                 order = -1;
 135                         else
 136                                 unordered_data = common_type;
 137
 138                         if(order && data_order && order!=data_order)
 139                                 throw scheduling_error(format("Ambiguous data ordering between %s and %s, accessing %s and %s",
 140                                         node1.type->get_name(), node2.type->get_name(), ordered_data->get_name(), common_type->get_name()));
 141
 142                         data_order = order;
 143                         ordered_data = common_type;
 144                 }
 145         }
 146
 147         if(!data_order && unordered_data)
 148                 throw scheduling_error(format("Ambiguous data ordering between %s and %s, accessing %s",
 149                         node1.type->get_name(), node2.type->get_name(), unordered_data->get_name()));
 150
 151         return data_order;
 152 }
 153
 154 } // namespace Msp::Game