Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2022-01-24 01:11:35

0001 #include "FWCore/Framework/interface/PathsAndConsumesOfModules.h"
0002 
0003 #include "FWCore/Framework/interface/Schedule.h"
0004 #include "FWCore/Framework/interface/ModuleProcessName.h"
0005 #include "FWCore/Framework/interface/maker/Worker.h"
0006 
0007 #include "FWCore/Utilities/interface/EDMException.h"
0008 
0009 #include <algorithm>
0010 #include <limits>
0011 #include <unordered_set>
0012 namespace edm {
0013 
0014   PathsAndConsumesOfModules::PathsAndConsumesOfModules() = default;
0015   PathsAndConsumesOfModules::~PathsAndConsumesOfModules() = default;
0016 
0017   void PathsAndConsumesOfModules::initialize(Schedule const* schedule, std::shared_ptr<ProductRegistry const> preg) {
0018     schedule_ = schedule;
0019     preg_ = preg;
0020 
0021     paths_.clear();
0022     schedule->triggerPaths(paths_);
0023 
0024     endPaths_.clear();
0025     schedule->endPaths(endPaths_);
0026 
0027     modulesOnPaths_.resize(paths_.size());
0028     unsigned int i = 0;
0029     unsigned int hint = 0;
0030     for (auto const& path : paths_) {
0031       schedule->moduleDescriptionsInPath(path, modulesOnPaths_.at(i), hint);
0032       if (!modulesOnPaths_.at(i).empty())
0033         ++hint;
0034       ++i;
0035     }
0036 
0037     modulesOnEndPaths_.resize(endPaths_.size());
0038     i = 0;
0039     hint = 0;
0040     for (auto const& endpath : endPaths_) {
0041       schedule->moduleDescriptionsInEndPath(endpath, modulesOnEndPaths_.at(i), hint);
0042       if (!modulesOnEndPaths_.at(i).empty())
0043         ++hint;
0044       ++i;
0045     }
0046 
0047     schedule->fillModuleAndConsumesInfo(allModuleDescriptions_,
0048                                         moduleIDToIndex_,
0049                                         modulesWhoseProductsAreConsumedBy_,
0050                                         modulesInPreviousProcessesWhoseProductsAreConsumedBy_,
0051                                         *preg);
0052   }
0053 
0054   void PathsAndConsumesOfModules::removeModules(std::vector<ModuleDescription const*> const& modules) {
0055     // First check that no modules on Paths are removed
0056     auto checkPath = [&modules](auto const& paths) {
0057       for (auto const& path : paths) {
0058         for (auto const& description : path) {
0059           if (std::find(modules.begin(), modules.end(), description) != modules.end()) {
0060             throw cms::Exception("Assert")
0061                 << "PathsAndConsumesOfModules::removeModules() is trying to remove a module with label "
0062                 << description->moduleLabel() << " id " << description->id() << " from a Path, this should not happen.";
0063           }
0064         }
0065       }
0066     };
0067     checkPath(modulesOnPaths_);
0068     checkPath(modulesOnEndPaths_);
0069 
0070     // Remove the modules and adjust the indices in idToIndex map
0071     for (auto iModule = 0U; iModule != allModuleDescriptions_.size(); ++iModule) {
0072       auto found = std::find(modules.begin(), modules.end(), allModuleDescriptions_[iModule]);
0073       if (found != modules.end()) {
0074         allModuleDescriptions_.erase(allModuleDescriptions_.begin() + iModule);
0075         for (auto iBranchType = 0U; iBranchType != NumBranchTypes; ++iBranchType) {
0076           modulesWhoseProductsAreConsumedBy_[iBranchType].erase(
0077               modulesWhoseProductsAreConsumedBy_[iBranchType].begin() + iModule);
0078         }
0079         modulesInPreviousProcessesWhoseProductsAreConsumedBy_.erase(
0080             modulesInPreviousProcessesWhoseProductsAreConsumedBy_.begin() + iModule);
0081         for (auto& idToIndex : moduleIDToIndex_) {
0082           if (idToIndex.second >= iModule) {
0083             idToIndex.second--;
0084           }
0085         }
0086         --iModule;
0087       }
0088     }
0089   }
0090 
0091   std::vector<ModuleProcessName> const& PathsAndConsumesOfModules::modulesInPreviousProcessesWhoseProductsAreConsumedBy(
0092       unsigned int moduleID) const {
0093     return modulesInPreviousProcessesWhoseProductsAreConsumedBy_.at(moduleIndex(moduleID));
0094   }
0095 
0096   ModuleDescription const* PathsAndConsumesOfModules::doModuleDescription(unsigned int moduleID) const {
0097     unsigned int dummy = 0;
0098     auto target = std::make_pair(moduleID, dummy);
0099     std::vector<std::pair<unsigned int, unsigned int>>::const_iterator iter =
0100         std::lower_bound(moduleIDToIndex_.begin(), moduleIDToIndex_.end(), target);
0101     if (iter == moduleIDToIndex_.end() || iter->first != moduleID) {
0102       throw Exception(errors::LogicError)
0103           << "PathsAndConsumesOfModules::moduleDescription: Unknown moduleID " << moduleID << "\n";
0104     }
0105     return allModuleDescriptions_.at(iter->second);
0106   }
0107 
0108   std::vector<ModuleDescription const*> const& PathsAndConsumesOfModules::doModulesOnPath(unsigned int pathIndex) const {
0109     return modulesOnPaths_.at(pathIndex);
0110   }
0111 
0112   std::vector<ModuleDescription const*> const& PathsAndConsumesOfModules::doModulesOnEndPath(
0113       unsigned int endPathIndex) const {
0114     return modulesOnEndPaths_.at(endPathIndex);
0115   }
0116 
0117   std::vector<ModuleDescription const*> const& PathsAndConsumesOfModules::doModulesWhoseProductsAreConsumedBy(
0118       unsigned int moduleID, BranchType branchType) const {
0119     return modulesWhoseProductsAreConsumedBy_[branchType].at(moduleIndex(moduleID));
0120   }
0121 
0122   std::vector<ConsumesInfo> PathsAndConsumesOfModules::doConsumesInfo(unsigned int moduleID) const {
0123     Worker const* worker = schedule_->allWorkers().at(moduleIndex(moduleID));
0124     return worker->consumesInfo();
0125   }
0126 
0127   unsigned int PathsAndConsumesOfModules::doLargestModuleID() const {
0128     // moduleIDToIndex_ is sorted, so last element has the largest ID
0129     return moduleIDToIndex_.empty() ? 0 : moduleIDToIndex_.back().first;
0130   }
0131 
0132   unsigned int PathsAndConsumesOfModules::moduleIndex(unsigned int moduleID) const {
0133     unsigned int dummy = 0;
0134     auto target = std::make_pair(moduleID, dummy);
0135     std::vector<std::pair<unsigned int, unsigned int>>::const_iterator iter =
0136         std::lower_bound(moduleIDToIndex_.begin(), moduleIDToIndex_.end(), target);
0137     if (iter == moduleIDToIndex_.end() || iter->first != moduleID) {
0138       throw Exception(errors::LogicError)
0139           << "PathsAndConsumesOfModules::moduleIndex: Unknown moduleID " << moduleID << "\n";
0140     }
0141     return iter->second;
0142   }
0143 }  // namespace edm
0144 
0145 namespace {
0146   // helper function for nonConsumedUnscheduledModules,
0147   void findAllConsumedModules(edm::PathsAndConsumesOfModulesBase const& iPnC,
0148                               edm::ModuleDescription const* module,
0149                               std::unordered_set<unsigned int>& consumedModules) {
0150     // If this node of the DAG has been processed already, no need to
0151     // reprocess again
0152     if (consumedModules.find(module->id()) != consumedModules.end()) {
0153       return;
0154     }
0155     consumedModules.insert(module->id());
0156     for (auto iBranchType = 0U; iBranchType != edm::NumBranchTypes; ++iBranchType) {
0157       for (auto const& c :
0158            iPnC.modulesWhoseProductsAreConsumedBy(module->id(), static_cast<edm::BranchType>(iBranchType))) {
0159         findAllConsumedModules(iPnC, c, consumedModules);
0160       }
0161     }
0162   }
0163 }  // namespace
0164 
0165 namespace edm {
0166   std::vector<ModuleDescription const*> nonConsumedUnscheduledModules(
0167       edm::PathsAndConsumesOfModulesBase const& iPnC, std::vector<ModuleProcessName>& consumedByChildren) {
0168     const std::string kTriggerResults("TriggerResults");
0169 
0170     std::vector<std::string> pathNames = iPnC.paths();
0171     const unsigned int kFirstEndPathIndex = pathNames.size();
0172     pathNames.insert(pathNames.end(), iPnC.endPaths().begin(), iPnC.endPaths().end());
0173 
0174     // The goal is to find modules that are not depended upon by
0175     // scheduled modules. To do that, we identify all modules that are
0176     // depended upon by scheduled modules, and do a set subtraction.
0177     //
0178     // First, denote all scheduled modules (i.e. in Paths and
0179     // EndPaths) as "consumers".
0180     std::vector<ModuleDescription const*> consumerModules;
0181     for (unsigned int pathIndex = 0; pathIndex != pathNames.size(); ++pathIndex) {
0182       std::vector<ModuleDescription const*> const* moduleDescriptions;
0183       if (pathIndex < kFirstEndPathIndex) {
0184         moduleDescriptions = &(iPnC.modulesOnPath(pathIndex));
0185       } else {
0186         moduleDescriptions = &(iPnC.modulesOnEndPath(pathIndex - kFirstEndPathIndex));
0187       }
0188       std::copy(moduleDescriptions->begin(), moduleDescriptions->end(), std::back_inserter(consumerModules));
0189     }
0190 
0191     // Then add TriggerResults, and all Paths and EndPaths themselves
0192     // to the set of "consumers" (even if they don't depend on any
0193     // data products, they must not be deleted). Also add anything
0194     // consumed by child SubProcesses to the set of "consumers".
0195     auto const& allModules = iPnC.allModules();
0196     for (auto const& description : allModules) {
0197       if (description->moduleLabel() == kTriggerResults or
0198           std::find(pathNames.begin(), pathNames.end(), description->moduleLabel()) != pathNames.end()) {
0199         consumerModules.push_back(description);
0200       } else if (std::binary_search(consumedByChildren.begin(),
0201                                     consumedByChildren.end(),
0202                                     ModuleProcessName{description->moduleLabel(), description->processName()}) or
0203                  std::binary_search(consumedByChildren.begin(),
0204                                     consumedByChildren.end(),
0205                                     ModuleProcessName{description->moduleLabel(), ""})) {
0206         consumerModules.push_back(description);
0207       }
0208     }
0209 
0210     // Find modules that have any data dependence path to any module
0211     // in consumerModules.
0212     std::unordered_set<unsigned int> consumedModules;
0213     for (auto& description : consumerModules) {
0214       findAllConsumedModules(iPnC, description, consumedModules);
0215     }
0216 
0217     // All other modules will then be classified as non-consumed, even
0218     // if they would have dependencies within them.
0219     std::vector<ModuleDescription const*> unusedModules;
0220     std::copy_if(allModules.begin(),
0221                  allModules.end(),
0222                  std::back_inserter(unusedModules),
0223                  [&consumedModules](ModuleDescription const* description) {
0224                    return consumedModules.find(description->id()) == consumedModules.end();
0225                  });
0226     return unusedModules;
0227   }
0228 
0229   //====================================
0230   // checkForCorrectness algorithm
0231   //
0232   // The code creates a 'dependency' graph between all
0233   // modules. A module depends on another module if
0234   // 1) it 'consumes' data produced by that module
0235   // 2) it appears directly after the module within a Path
0236   //
0237   // If there is a cycle in the 'dependency' graph then
0238   // the schedule may be unrunnable. The schedule is still
0239   // runnable if all cycles have at least two edges which
0240   // connect modules only by Path dependencies (i.e. not
0241   // linked by a data dependency).
0242   //
0243   //  Example 1:
0244   //  C consumes data from B
0245   //  Path 1: A + B + C
0246   //  Path 2: B + C + A
0247   //
0248   //  Cycle: A after C [p2], C consumes B, B after A [p1]
0249   //  Since this cycle has 2 path only edges it is OK since
0250   //  A and (B+C) are independent so their run order doesn't matter
0251   //
0252   //  Example 2:
0253   //  B consumes A
0254   //  C consumes B
0255   //  Path: C + A
0256   //
0257   //  Cycle: A after C [p], C consumes B, B consumes A
0258   //  Since this cycle has 1 path only edge it is unrunnable.
0259   //
0260   //  Example 3:
0261   //  A consumes B
0262   //  B consumes C
0263   //  C consumes A
0264   //  (no Path since unscheduled execution)
0265   //
0266   //  Cycle: A consumes B, B consumes C, C consumes A
0267   //  Since this cycle has 0 path only edges it is unrunnable.
0268   //====================================
0269 
0270   namespace {
0271     struct ModuleStatus {
0272       std::vector<unsigned int> dependsOn_;
0273       std::vector<unsigned int> pathsOn_;
0274       unsigned long long lastSearch = 0;
0275       bool onPath_ = false;
0276       bool wasRun_ = false;
0277     };
0278 
0279     struct PathStatus {
0280       std::vector<unsigned int> modulesOnPath_;
0281       unsigned long int activeModuleSlot_ = 0;
0282       unsigned long int nModules_ = 0;
0283       unsigned int index_ = 0;
0284       bool endPath_ = false;
0285     };
0286 
0287     class CircularDependencyException {};
0288 
0289     bool checkIfCanRun(unsigned long long searchIndex,
0290                        unsigned int iModuleToCheckID,
0291                        std::vector<ModuleStatus>& iModules,
0292                        std::vector<unsigned int>& stackTrace) {
0293       auto& status = iModules[iModuleToCheckID];
0294       if (status.wasRun_) {
0295         return true;
0296       }
0297 
0298       if (status.lastSearch == searchIndex) {
0299         //check to see if the module is already on the stack
0300         // checking searchIndex is insufficient as multiple modules
0301         // in this search may be dependent upon the same module
0302         auto itFound = std::find(stackTrace.begin(), stackTrace.end(), iModuleToCheckID);
0303         if (itFound != stackTrace.end()) {
0304           stackTrace.push_back(iModuleToCheckID);
0305           throw CircularDependencyException();
0306         }
0307         //we have already checked this module's dependencies during this search
0308         return false;
0309       }
0310       stackTrace.push_back(iModuleToCheckID);
0311       status.lastSearch = searchIndex;
0312 
0313       bool allDependenciesRan = true;
0314       for (auto index : status.dependsOn_) {
0315         auto& dep = iModules[index];
0316         if (dep.onPath_) {
0317           if (not dep.wasRun_) {
0318             allDependenciesRan = false;
0319           }
0320         } else if (not checkIfCanRun(searchIndex, index, iModules, stackTrace)) {
0321           allDependenciesRan = false;
0322         }
0323       }
0324       if (allDependenciesRan) {
0325         status.wasRun_ = true;
0326       }
0327       stackTrace.pop_back();
0328 
0329       return allDependenciesRan;
0330     }
0331   }  // namespace
0332   void checkForModuleDependencyCorrectness(edm::PathsAndConsumesOfModulesBase const& iPnC, bool iPrintDependencies) {
0333     constexpr auto kInvalidIndex = std::numeric_limits<unsigned int>::max();
0334 
0335     //Need to lookup ids to names quickly
0336     std::unordered_map<unsigned int, std::string> moduleIndexToNames;
0337 
0338     std::unordered_map<std::string, unsigned int> pathStatusInserterModuleLabelToModuleID;
0339 
0340     //for testing, state that TriggerResults is at the end of all paths
0341     const std::string kTriggerResults("TriggerResults");
0342     const std::string kPathStatusInserter("PathStatusInserter");
0343     const std::string kEndPathStatusInserter("EndPathStatusInserter");
0344     unsigned int kTriggerResultsIndex = kInvalidIndex;
0345     ModuleStatus triggerResultsStatus;
0346     unsigned int largestIndex = 0;
0347     for (auto const& description : iPnC.allModules()) {
0348       moduleIndexToNames.insert(std::make_pair(description->id(), description->moduleLabel()));
0349       if (kTriggerResults == description->moduleLabel()) {
0350         kTriggerResultsIndex = description->id();
0351       }
0352       if (description->id() > largestIndex) {
0353         largestIndex = description->id();
0354       }
0355       if (description->moduleName() == kPathStatusInserter) {
0356         triggerResultsStatus.dependsOn_.push_back(description->id());
0357       }
0358       if (description->moduleName() == kPathStatusInserter || description->moduleName() == kEndPathStatusInserter) {
0359         pathStatusInserterModuleLabelToModuleID[description->moduleLabel()] = description->id();
0360       }
0361     }
0362 
0363     std::vector<ModuleStatus> statusOfModules(largestIndex + 1);
0364     for (auto const& nameID : pathStatusInserterModuleLabelToModuleID) {
0365       statusOfModules[nameID.second].onPath_ = true;
0366       unsigned int pathIndex;
0367       auto const& paths = iPnC.paths();
0368       auto itFound = std::find(paths.begin(), paths.end(), nameID.first);
0369       if (itFound != paths.end()) {
0370         pathIndex = itFound - paths.begin();
0371       } else {
0372         auto const& endPaths = iPnC.endPaths();
0373         itFound = std::find(endPaths.begin(), endPaths.end(), nameID.first);
0374         assert(itFound != endPaths.end());
0375         pathIndex = itFound - endPaths.begin() + iPnC.paths().size();
0376       }
0377       statusOfModules[nameID.second].pathsOn_.push_back(pathIndex);
0378     }
0379     if (kTriggerResultsIndex != kInvalidIndex) {
0380       statusOfModules[kTriggerResultsIndex] = std::move(triggerResultsStatus);
0381     }
0382 
0383     std::vector<PathStatus> statusOfPaths(iPnC.paths().size() + iPnC.endPaths().size());
0384 
0385     //If there are no paths, no modules will run so nothing to check
0386     if (statusOfPaths.empty()) {
0387       return;
0388     }
0389 
0390     {
0391       auto nPaths = iPnC.paths().size();
0392       for (unsigned int p = 0; p < nPaths; ++p) {
0393         auto& status = statusOfPaths[p];
0394         status.index_ = p;
0395         status.modulesOnPath_.reserve(iPnC.modulesOnPath(p).size() + 1);
0396         std::unordered_set<unsigned int> uniqueModules;
0397         for (auto const& mod : iPnC.modulesOnPath(p)) {
0398           if (uniqueModules.insert(mod->id()).second) {
0399             status.modulesOnPath_.push_back(mod->id());
0400             statusOfModules[mod->id()].onPath_ = true;
0401             statusOfModules[mod->id()].pathsOn_.push_back(p);
0402           }
0403         }
0404         status.nModules_ = uniqueModules.size() + 1;
0405 
0406         //add the PathStatusInserter at the end
0407         auto found = pathStatusInserterModuleLabelToModuleID.find(iPnC.paths()[p]);
0408         assert(found != pathStatusInserterModuleLabelToModuleID.end());
0409         status.modulesOnPath_.push_back(found->second);
0410       }
0411     }
0412     {
0413       auto offset = iPnC.paths().size();
0414       auto nPaths = iPnC.endPaths().size();
0415       for (unsigned int p = 0; p < nPaths; ++p) {
0416         auto& status = statusOfPaths[p + offset];
0417         status.endPath_ = true;
0418         status.index_ = p;
0419         status.modulesOnPath_.reserve(iPnC.modulesOnEndPath(p).size() + 1);
0420         std::unordered_set<unsigned int> uniqueModules;
0421         for (auto const& mod : iPnC.modulesOnEndPath(p)) {
0422           if (uniqueModules.insert(mod->id()).second) {
0423             status.modulesOnPath_.push_back(mod->id());
0424             statusOfModules[mod->id()].onPath_ = true;
0425             statusOfModules[mod->id()].pathsOn_.push_back(p + offset);
0426           }
0427         }
0428         status.nModules_ = uniqueModules.size() + 1;
0429 
0430         //add the EndPathStatusInserter at the end
0431         auto found = pathStatusInserterModuleLabelToModuleID.find(iPnC.endPaths()[p]);
0432         assert(found != pathStatusInserterModuleLabelToModuleID.end());
0433         status.modulesOnPath_.push_back(found->second);
0434       }
0435     }
0436 
0437     for (auto const& description : iPnC.allModules()) {
0438       unsigned int const moduleIndex = description->id();
0439       auto const& dependentModules = iPnC.modulesWhoseProductsAreConsumedBy(moduleIndex);
0440       auto& deps = statusOfModules[moduleIndex];
0441       deps.dependsOn_.reserve(dependentModules.size());
0442       for (auto const& depDescription : dependentModules) {
0443         if (iPrintDependencies) {
0444           edm::LogAbsolute("ModuleDependency")
0445               << "ModuleDependency '" << description->moduleLabel() << "' depends on data products from module '"
0446               << depDescription->moduleLabel() << "'";
0447         }
0448         deps.dependsOn_.push_back(depDescription->id());
0449       }
0450     }
0451 
0452     unsigned int nPathsFinished = 0;
0453 
0454     //if a circular dependency exception happens, stackTrace has the info
0455     std::vector<unsigned int> stackTrace;
0456     bool madeForwardProgress = true;
0457     try {
0458       //'simulate' the running of the paths. On each step mark each module as 'run'
0459       // if all the module's dependencies were fulfilled in a previous step
0460       unsigned long long searchIndex = 0;
0461       while (madeForwardProgress and nPathsFinished != statusOfPaths.size()) {
0462         madeForwardProgress = false;
0463         for (auto& p : statusOfPaths) {
0464           //the path has already completed in an earlier pass
0465           if (p.activeModuleSlot_ == p.nModules_) {
0466             continue;
0467           }
0468           ++searchIndex;
0469           bool didRun = checkIfCanRun(searchIndex, p.modulesOnPath_[p.activeModuleSlot_], statusOfModules, stackTrace);
0470           if (didRun) {
0471             madeForwardProgress = true;
0472             ++p.activeModuleSlot_;
0473             if (p.activeModuleSlot_ == p.nModules_) {
0474               ++nPathsFinished;
0475             }
0476           }
0477         }
0478       }
0479     } catch (CircularDependencyException const&) {
0480       //the last element in stackTrace must appear somewhere earlier in stackTrace
0481       std::ostringstream oStr;
0482 
0483       unsigned int lastIndex = stackTrace.front();
0484       bool firstSkipped = false;
0485       for (auto id : stackTrace) {
0486         if (firstSkipped) {
0487           oStr << "  module '" << moduleIndexToNames[lastIndex] << "' depends on " << moduleIndexToNames[id] << "\n";
0488         } else {
0489           firstSkipped = true;
0490         }
0491         lastIndex = id;
0492       }
0493       throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
0494           << "Circular module dependency found in configuration\n"
0495           << oStr.str();
0496     }
0497 
0498     auto pathName = [&](PathStatus const& iP) {
0499       if (iP.endPath_) {
0500         return iPnC.endPaths()[iP.index_];
0501       }
0502       return iPnC.paths()[iP.index_];
0503     };
0504 
0505     //The program would deadlock
0506     if (not madeForwardProgress) {
0507       std::ostringstream oStr;
0508       auto modIndex = std::numeric_limits<unsigned int>::max();
0509       unsigned int presentPath;
0510       for (auto itP = statusOfPaths.begin(); itP != statusOfPaths.end(); ++itP) {
0511         auto const& p = *itP;
0512         if (p.activeModuleSlot_ == p.nModules_) {
0513           continue;
0514         }
0515         //this path is stuck
0516         modIndex = p.modulesOnPath_[p.activeModuleSlot_];
0517         presentPath = itP - statusOfPaths.begin();
0518         break;
0519       }
0520       //NOTE the following should always be true as at least 1 path should be stuc.
0521       // I've added the condition just to be paranoid.
0522       if (modIndex != std::numeric_limits<unsigned int>::max()) {
0523         struct ProgressInfo {
0524           ProgressInfo(unsigned int iMod, unsigned int iPath, bool iPreceeds = false)
0525               : moduleIndex_(iMod), pathIndex_(iPath), preceeds_(iPreceeds) {}
0526 
0527           ProgressInfo(unsigned int iMod) : moduleIndex_(iMod), pathIndex_{}, preceeds_(false) {}
0528 
0529           unsigned int moduleIndex_ = std::numeric_limits<unsigned int>::max();
0530           std::optional<unsigned int> pathIndex_;
0531           bool preceeds_;
0532 
0533           bool operator==(ProgressInfo const& iOther) const {
0534             return moduleIndex_ == iOther.moduleIndex_ and pathIndex_ == iOther.pathIndex_;
0535           }
0536         };
0537 
0538         std::vector<ProgressInfo> progressTrace;
0539         progressTrace.emplace_back(modIndex, presentPath);
0540 
0541         //The following starts from the first found unrun module on a path. It then finds
0542         // the first modules it depends on that was not run. If that module is on a Task
0543         // it then repeats the check for that module's dependencies. If that module is on
0544         // a path, it checks to see if that module is the first unrun module of a path
0545         // and if so it repeats the check for that module's dependencies, if not it
0546         // checks the dependencies of the stuck module on that path.
0547         // Eventually, all these checks should allow us to find a cycle of modules.
0548 
0549         //NOTE: the only way foundUnrunModule should ever by false by the end of the
0550         // do{}while loop is if there is a bug in the algorithm. I've included it to
0551         // try to avoid that case causing an infinite loop in the program.
0552         bool foundUnrunModule;
0553         do {
0554           //check dependencies looking for stuff not run and on a path
0555           foundUnrunModule = false;
0556           for (auto depMod : statusOfModules[modIndex].dependsOn_) {
0557             auto const& depStatus = statusOfModules[depMod];
0558             if (not depStatus.wasRun_ and depStatus.onPath_) {
0559               foundUnrunModule = true;
0560               //last run on a path?
0561               bool lastOnPath = false;
0562               unsigned int foundPath;
0563               for (auto pathOn : depStatus.pathsOn_) {
0564                 auto const& depPaths = statusOfPaths[pathOn];
0565                 if (depPaths.modulesOnPath_[depPaths.activeModuleSlot_] == depMod) {
0566                   lastOnPath = true;
0567                   foundPath = pathOn;
0568                   break;
0569                 }
0570               }
0571               if (lastOnPath) {
0572                 modIndex = depMod;
0573                 progressTrace.emplace_back(modIndex, foundPath);
0574               } else {
0575                 //some earlier module on the same path is stuck
0576                 progressTrace.emplace_back(depMod, depStatus.pathsOn_[0]);
0577                 auto const& depPath = statusOfPaths[depStatus.pathsOn_[0]];
0578                 modIndex = depPath.modulesOnPath_[depPath.activeModuleSlot_];
0579                 progressTrace.emplace_back(modIndex, depStatus.pathsOn_[0], true);
0580               }
0581               break;
0582             }
0583           }
0584           if (not foundUnrunModule) {
0585             //check unscheduled modules
0586             for (auto depMod : statusOfModules[modIndex].dependsOn_) {
0587               auto const& depStatus = statusOfModules[depMod];
0588               if (not depStatus.wasRun_ and not depStatus.onPath_) {
0589                 foundUnrunModule = true;
0590                 progressTrace.emplace_back(depMod);
0591                 modIndex = depMod;
0592                 break;
0593               }
0594             }
0595           }
0596         } while (foundUnrunModule and (0 == std::count(progressTrace.begin(),
0597                                                        progressTrace.begin() + progressTrace.size() - 1,
0598                                                        progressTrace.back())));
0599 
0600         auto printTrace = [&](auto& oStr, auto itBegin, auto itEnd) {
0601           for (auto itTrace = itBegin; itTrace != itEnd; ++itTrace) {
0602             if (itTrace != itBegin) {
0603               if (itTrace->preceeds_) {
0604                 oStr << " and follows module '" << moduleIndexToNames[itTrace->moduleIndex_] << "' on the path\n";
0605               } else {
0606                 oStr << " and depends on module '" << moduleIndexToNames[itTrace->moduleIndex_] << "'\n";
0607               }
0608             }
0609             if (itTrace + 1 != itEnd) {
0610               if (itTrace->pathIndex_) {
0611                 oStr << "  module '" << moduleIndexToNames[itTrace->moduleIndex_] << "' is on path '"
0612                      << pathName(statusOfPaths[*itTrace->pathIndex_]) << "'";
0613               } else {
0614                 oStr << "  module '" << moduleIndexToNames[itTrace->moduleIndex_] << "' is in a task";
0615               }
0616             }
0617           }
0618         };
0619 
0620         if (not foundUnrunModule) {
0621           //If we get here, this suggests a problem with either the algorithm that finds problems or the algorithm
0622           // that attempts to report the problem
0623           oStr << "Algorithm Error, unable to find problem. Contact framework group.\n Traced problem this far\n";
0624           printTrace(oStr, progressTrace.begin(), progressTrace.end());
0625         } else {
0626           printTrace(
0627               oStr, std::find(progressTrace.begin(), progressTrace.end(), progressTrace.back()), progressTrace.end());
0628         }
0629       }
0630       //the schedule deadlocked
0631       throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
0632           << "The Path/EndPath configuration could cause the job to deadlock\n"
0633           << oStr.str();
0634     }
0635 
0636     //NOTE: although the following conditions are not needed for safe running, they are
0637     // policy choices the collaboration has made.
0638 
0639     //Check to see if for each path if the order of the modules is correct based on dependencies
0640     for (auto& p : statusOfPaths) {
0641       for (unsigned long int i = 0; p.nModules_ > 0 and i < p.nModules_ - 1; ++i) {
0642         auto moduleID = p.modulesOnPath_[i];
0643         if (not statusOfModules[moduleID].dependsOn_.empty()) {
0644           for (unsigned long int j = i + 1; j < p.nModules_; ++j) {
0645             auto testModuleID = p.modulesOnPath_[j];
0646             for (auto depModuleID : statusOfModules[moduleID].dependsOn_) {
0647               if (depModuleID == testModuleID) {
0648                 throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
0649                     << "Dependent module later on Path\n"
0650                     << "  module '" << moduleIndexToNames[moduleID] << "' depends on '"
0651                     << moduleIndexToNames[depModuleID] << "' which is later on path " << pathName(p);
0652               }
0653             }
0654           }
0655         }
0656       }
0657     }
0658 
0659     //HLT wants all paths to be equivalent. If a path has a module A that needs data from module B and module B appears on one path
0660     // as module A then B must appear on ALL paths that have A.
0661     unsigned int modIndex = 0;
0662     for (auto& mod : statusOfModules) {
0663       for (auto& depIndex : mod.dependsOn_) {
0664         std::size_t count = 0;
0665         std::size_t nonEndPaths = 0;
0666         for (auto modPathID : mod.pathsOn_) {
0667           if (statusOfPaths[modPathID].endPath_) {
0668             continue;
0669           }
0670           ++nonEndPaths;
0671           for (auto depPathID : statusOfModules[depIndex].pathsOn_) {
0672             if (depPathID == modPathID) {
0673               ++count;
0674               break;
0675             }
0676           }
0677         }
0678         if (count != 0 and count != nonEndPaths) {
0679           std::ostringstream onStr;
0680           std::ostringstream missingStr;
0681 
0682           for (auto modPathID : mod.pathsOn_) {
0683             if (statusOfPaths[modPathID].endPath_) {
0684               continue;
0685             }
0686             bool found = false;
0687             for (auto depPathID : statusOfModules[depIndex].pathsOn_) {
0688               if (depPathID == modPathID) {
0689                 found = true;
0690               }
0691             }
0692             auto& s = statusOfPaths[modPathID];
0693             if (found) {
0694               onStr << pathName(s) << " ";
0695             } else {
0696               missingStr << pathName(s) << " ";
0697             }
0698           }
0699           throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
0700               << "Paths are non consistent\n"
0701               << "  module '" << moduleIndexToNames[modIndex] << "' depends on '" << moduleIndexToNames[depIndex]
0702               << "' which appears on paths\n  " << onStr.str() << "\nbut is missing from\n  " << missingStr.str();
0703         }
0704       }
0705       ++modIndex;
0706     }
0707   }
0708 }  // namespace edm