Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2024-01-13 02:35:03

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 
0332     void findAllDependenciesForModule(unsigned int iModID,
0333                                       std::vector<ModuleStatus> const& iStatus,
0334                                       std::vector<std::unordered_set<unsigned int>>& oDependencies) {
0335       auto const& dependsOn = iStatus[iModID].dependsOn_;
0336       if (dependsOn.empty() or !oDependencies[iModID].empty()) {
0337         return;
0338       }
0339       oDependencies[iModID].insert(dependsOn.begin(), dependsOn.end());
0340       for (auto dep : dependsOn) {
0341         findAllDependenciesForModule(dep, iStatus, oDependencies);
0342         oDependencies[iModID].merge(oDependencies[dep]);
0343       }
0344     }
0345     std::vector<std::unordered_set<unsigned int>> findAllDependenciesForModules(
0346         std::vector<ModuleStatus> const& iStatus) {
0347       std::vector<std::unordered_set<unsigned int>> ret(iStatus.size());
0348       for (unsigned int id = 0; id < iStatus.size(); ++id) {
0349         findAllDependenciesForModule(id, iStatus, ret);
0350       }
0351       return ret;
0352     }
0353   }  // namespace
0354   void checkForModuleDependencyCorrectness(edm::PathsAndConsumesOfModulesBase const& iPnC, bool iPrintDependencies) {
0355     constexpr auto kInvalidIndex = std::numeric_limits<unsigned int>::max();
0356 
0357     //Need to lookup ids to names quickly
0358     std::unordered_map<unsigned int, std::string> moduleIndexToNames;
0359 
0360     std::unordered_map<std::string, unsigned int> pathStatusInserterModuleLabelToModuleID;
0361 
0362     //for testing, state that TriggerResults is at the end of all paths
0363     const std::string kTriggerResults("TriggerResults");
0364     const std::string kPathStatusInserter("PathStatusInserter");
0365     const std::string kEndPathStatusInserter("EndPathStatusInserter");
0366     unsigned int kTriggerResultsIndex = kInvalidIndex;
0367     ModuleStatus triggerResultsStatus;
0368     unsigned int largestIndex = 0;
0369     for (auto const& description : iPnC.allModules()) {
0370       moduleIndexToNames.insert(std::make_pair(description->id(), description->moduleLabel()));
0371       if (kTriggerResults == description->moduleLabel()) {
0372         kTriggerResultsIndex = description->id();
0373       }
0374       if (description->id() > largestIndex) {
0375         largestIndex = description->id();
0376       }
0377       if (description->moduleName() == kPathStatusInserter) {
0378         triggerResultsStatus.dependsOn_.push_back(description->id());
0379       }
0380       if (description->moduleName() == kPathStatusInserter || description->moduleName() == kEndPathStatusInserter) {
0381         pathStatusInserterModuleLabelToModuleID[description->moduleLabel()] = description->id();
0382       }
0383     }
0384 
0385     std::vector<ModuleStatus> statusOfModules(largestIndex + 1);
0386     for (auto const& nameID : pathStatusInserterModuleLabelToModuleID) {
0387       statusOfModules[nameID.second].onPath_ = true;
0388       unsigned int pathIndex;
0389       auto const& paths = iPnC.paths();
0390       auto itFound = std::find(paths.begin(), paths.end(), nameID.first);
0391       if (itFound != paths.end()) {
0392         pathIndex = itFound - paths.begin();
0393       } else {
0394         auto const& endPaths = iPnC.endPaths();
0395         itFound = std::find(endPaths.begin(), endPaths.end(), nameID.first);
0396         assert(itFound != endPaths.end());
0397         pathIndex = itFound - endPaths.begin() + iPnC.paths().size();
0398       }
0399       statusOfModules[nameID.second].pathsOn_.push_back(pathIndex);
0400     }
0401     if (kTriggerResultsIndex != kInvalidIndex) {
0402       statusOfModules[kTriggerResultsIndex] = std::move(triggerResultsStatus);
0403     }
0404 
0405     std::vector<PathStatus> statusOfPaths(iPnC.paths().size() + iPnC.endPaths().size());
0406 
0407     //If there are no paths, no modules will run so nothing to check
0408     if (statusOfPaths.empty()) {
0409       return;
0410     }
0411 
0412     {
0413       auto nPaths = iPnC.paths().size();
0414       for (unsigned int p = 0; p < nPaths; ++p) {
0415         auto& status = statusOfPaths[p];
0416         status.index_ = p;
0417         status.modulesOnPath_.reserve(iPnC.modulesOnPath(p).size() + 1);
0418         std::unordered_set<unsigned int> uniqueModules;
0419         for (auto const& mod : iPnC.modulesOnPath(p)) {
0420           if (uniqueModules.insert(mod->id()).second) {
0421             status.modulesOnPath_.push_back(mod->id());
0422             statusOfModules[mod->id()].onPath_ = true;
0423             statusOfModules[mod->id()].pathsOn_.push_back(p);
0424           }
0425         }
0426         status.nModules_ = uniqueModules.size() + 1;
0427 
0428         //add the PathStatusInserter at the end
0429         auto found = pathStatusInserterModuleLabelToModuleID.find(iPnC.paths()[p]);
0430         assert(found != pathStatusInserterModuleLabelToModuleID.end());
0431         status.modulesOnPath_.push_back(found->second);
0432       }
0433     }
0434     {
0435       auto offset = iPnC.paths().size();
0436       auto nPaths = iPnC.endPaths().size();
0437       for (unsigned int p = 0; p < nPaths; ++p) {
0438         auto& status = statusOfPaths[p + offset];
0439         status.endPath_ = true;
0440         status.index_ = p;
0441         status.modulesOnPath_.reserve(iPnC.modulesOnEndPath(p).size() + 1);
0442         std::unordered_set<unsigned int> uniqueModules;
0443         for (auto const& mod : iPnC.modulesOnEndPath(p)) {
0444           if (uniqueModules.insert(mod->id()).second) {
0445             status.modulesOnPath_.push_back(mod->id());
0446             statusOfModules[mod->id()].onPath_ = true;
0447             statusOfModules[mod->id()].pathsOn_.push_back(p + offset);
0448           }
0449         }
0450         status.nModules_ = uniqueModules.size();
0451 
0452         //add the EndPathStatusInserter at the end
0453         auto found = pathStatusInserterModuleLabelToModuleID.find(iPnC.endPaths()[p]);
0454         if (found != pathStatusInserterModuleLabelToModuleID.end()) {
0455           status.modulesOnPath_.push_back(found->second);
0456           ++status.nModules_;
0457         }
0458       }
0459     }
0460 
0461     for (auto const& description : iPnC.allModules()) {
0462       unsigned int const moduleIndex = description->id();
0463       auto const& dependentModules = iPnC.modulesWhoseProductsAreConsumedBy(moduleIndex);
0464       auto& deps = statusOfModules[moduleIndex];
0465       deps.dependsOn_.reserve(dependentModules.size());
0466       for (auto const& depDescription : dependentModules) {
0467         if (iPrintDependencies) {
0468           edm::LogAbsolute("ModuleDependency")
0469               << "ModuleDependency '" << description->moduleLabel() << "' depends on data products from module '"
0470               << depDescription->moduleLabel() << "'";
0471         }
0472         deps.dependsOn_.push_back(depDescription->id());
0473       }
0474     }
0475 
0476     unsigned int nPathsFinished = 0;
0477     for (auto const& status : statusOfPaths) {
0478       if (status.nModules_ == 0) {
0479         ++nPathsFinished;
0480       }
0481     }
0482 
0483     //if a circular dependency exception happens, stackTrace has the info
0484     std::vector<unsigned int> stackTrace;
0485     bool madeForwardProgress = true;
0486     try {
0487       //'simulate' the running of the paths. On each step mark each module as 'run'
0488       // if all the module's dependencies were fulfilled in a previous step
0489       unsigned long long searchIndex = 0;
0490       while (madeForwardProgress and nPathsFinished != statusOfPaths.size()) {
0491         madeForwardProgress = false;
0492         for (auto& p : statusOfPaths) {
0493           //the path has already completed in an earlier pass
0494           if (p.activeModuleSlot_ == p.nModules_) {
0495             continue;
0496           }
0497           ++searchIndex;
0498           bool didRun = checkIfCanRun(searchIndex, p.modulesOnPath_[p.activeModuleSlot_], statusOfModules, stackTrace);
0499           if (didRun) {
0500             madeForwardProgress = true;
0501             ++p.activeModuleSlot_;
0502             if (p.activeModuleSlot_ == p.nModules_) {
0503               ++nPathsFinished;
0504             }
0505           }
0506         }
0507       }
0508     } catch (CircularDependencyException const&) {
0509       //the last element in stackTrace must appear somewhere earlier in stackTrace
0510       std::ostringstream oStr;
0511 
0512       unsigned int lastIndex = stackTrace.front();
0513       bool firstSkipped = false;
0514       for (auto id : stackTrace) {
0515         if (firstSkipped) {
0516           oStr << "  module '" << moduleIndexToNames[lastIndex] << "' depends on " << moduleIndexToNames[id] << "\n";
0517         } else {
0518           firstSkipped = true;
0519         }
0520         lastIndex = id;
0521       }
0522       throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
0523           << "Circular module dependency found in configuration\n"
0524           << oStr.str();
0525     }
0526 
0527     auto pathName = [&](PathStatus const& iP) {
0528       if (iP.endPath_) {
0529         return iPnC.endPaths()[iP.index_];
0530       }
0531       return iPnC.paths()[iP.index_];
0532     };
0533 
0534     //The program would deadlock
0535     if (not madeForwardProgress) {
0536       std::ostringstream oStr;
0537       auto modIndex = std::numeric_limits<unsigned int>::max();
0538       unsigned int presentPath;
0539       for (auto itP = statusOfPaths.begin(); itP != statusOfPaths.end(); ++itP) {
0540         auto const& p = *itP;
0541         if (p.activeModuleSlot_ == p.nModules_) {
0542           continue;
0543         }
0544         //this path is stuck
0545         modIndex = p.modulesOnPath_[p.activeModuleSlot_];
0546         presentPath = itP - statusOfPaths.begin();
0547         break;
0548       }
0549       //NOTE the following should always be true as at least 1 path should be stuc.
0550       // I've added the condition just to be paranoid.
0551       if (modIndex != std::numeric_limits<unsigned int>::max()) {
0552         struct ProgressInfo {
0553           ProgressInfo(unsigned int iMod, unsigned int iPath, bool iPreceeds = false)
0554               : moduleIndex_(iMod), pathIndex_(iPath), preceeds_(iPreceeds) {}
0555 
0556           ProgressInfo(unsigned int iMod) : moduleIndex_(iMod), pathIndex_{}, preceeds_(false) {}
0557 
0558           unsigned int moduleIndex_ = std::numeric_limits<unsigned int>::max();
0559           std::optional<unsigned int> pathIndex_;
0560           bool preceeds_;
0561 
0562           bool operator==(ProgressInfo const& iOther) const {
0563             return moduleIndex_ == iOther.moduleIndex_ and pathIndex_ == iOther.pathIndex_;
0564           }
0565         };
0566 
0567         std::vector<ProgressInfo> progressTrace;
0568         progressTrace.emplace_back(modIndex, presentPath);
0569 
0570         //The following starts from the first found unrun module on a path. It then finds
0571         // the first modules it depends on that was not run. If that module is on a Task
0572         // it then repeats the check for that module's dependencies. If that module is on
0573         // a path, it checks to see if that module is the first unrun module of a path
0574         // and if so it repeats the check for that module's dependencies, if not it
0575         // checks the dependencies of the stuck module on that path.
0576         // Eventually, all these checks should allow us to find a cycle of modules.
0577 
0578         //NOTE: the only way foundUnrunModule should ever by false by the end of the
0579         // do{}while loop is if there is a bug in the algorithm. I've included it to
0580         // try to avoid that case causing an infinite loop in the program.
0581         bool foundUnrunModule;
0582         do {
0583           //check dependencies looking for stuff not run and on a path
0584           foundUnrunModule = false;
0585           for (auto depMod : statusOfModules[modIndex].dependsOn_) {
0586             auto const& depStatus = statusOfModules[depMod];
0587             if (not depStatus.wasRun_ and depStatus.onPath_) {
0588               foundUnrunModule = true;
0589               //last run on a path?
0590               bool lastOnPath = false;
0591               unsigned int foundPath;
0592               for (auto pathOn : depStatus.pathsOn_) {
0593                 auto const& depPaths = statusOfPaths[pathOn];
0594                 if (depPaths.modulesOnPath_[depPaths.activeModuleSlot_] == depMod) {
0595                   lastOnPath = true;
0596                   foundPath = pathOn;
0597                   break;
0598                 }
0599               }
0600               if (lastOnPath) {
0601                 modIndex = depMod;
0602                 progressTrace.emplace_back(modIndex, foundPath);
0603               } else {
0604                 //some earlier module on the same path is stuck
0605                 progressTrace.emplace_back(depMod, depStatus.pathsOn_[0]);
0606                 auto const& depPath = statusOfPaths[depStatus.pathsOn_[0]];
0607                 modIndex = depPath.modulesOnPath_[depPath.activeModuleSlot_];
0608                 progressTrace.emplace_back(modIndex, depStatus.pathsOn_[0], true);
0609               }
0610               break;
0611             }
0612           }
0613           if (not foundUnrunModule) {
0614             //check unscheduled modules
0615             for (auto depMod : statusOfModules[modIndex].dependsOn_) {
0616               auto const& depStatus = statusOfModules[depMod];
0617               if (not depStatus.wasRun_ and not depStatus.onPath_) {
0618                 foundUnrunModule = true;
0619                 progressTrace.emplace_back(depMod);
0620                 modIndex = depMod;
0621                 break;
0622               }
0623             }
0624           }
0625         } while (foundUnrunModule and (0 == std::count(progressTrace.begin(),
0626                                                        progressTrace.begin() + progressTrace.size() - 1,
0627                                                        progressTrace.back())));
0628 
0629         auto printTrace = [&](auto& oStr, auto itBegin, auto itEnd) {
0630           for (auto itTrace = itBegin; itTrace != itEnd; ++itTrace) {
0631             if (itTrace != itBegin) {
0632               if (itTrace->preceeds_) {
0633                 oStr << " and follows module '" << moduleIndexToNames[itTrace->moduleIndex_] << "' on the path\n";
0634               } else {
0635                 oStr << " and depends on module '" << moduleIndexToNames[itTrace->moduleIndex_] << "'\n";
0636               }
0637             }
0638             if (itTrace + 1 != itEnd) {
0639               if (itTrace->pathIndex_) {
0640                 oStr << "  module '" << moduleIndexToNames[itTrace->moduleIndex_] << "' is on path '"
0641                      << pathName(statusOfPaths[*itTrace->pathIndex_]) << "'";
0642               } else {
0643                 oStr << "  module '" << moduleIndexToNames[itTrace->moduleIndex_] << "' is in a task";
0644               }
0645             }
0646           }
0647         };
0648 
0649         if (not foundUnrunModule) {
0650           //If we get here, this suggests a problem with either the algorithm that finds problems or the algorithm
0651           // that attempts to report the problem
0652           oStr << "Algorithm Error, unable to find problem. Contact framework group.\n Traced problem this far\n";
0653           printTrace(oStr, progressTrace.begin(), progressTrace.end());
0654         } else {
0655           printTrace(
0656               oStr, std::find(progressTrace.begin(), progressTrace.end(), progressTrace.back()), progressTrace.end());
0657         }
0658       }
0659       //the schedule deadlocked
0660       throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
0661           << "The Path/EndPath configuration could cause the job to deadlock\n"
0662           << oStr.str();
0663     }
0664 
0665     //NOTE: although the following conditions are not needed for safe running, they are
0666     // policy choices the collaboration has made.
0667 
0668     //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
0669     // as module A then B must appear on ALL paths that have A.
0670     unsigned int modIndex = 0;
0671     for (auto& mod : statusOfModules) {
0672       for (auto& depIndex : mod.dependsOn_) {
0673         std::size_t count = 0;
0674         std::size_t nonEndPaths = 0;
0675         for (auto modPathID : mod.pathsOn_) {
0676           if (statusOfPaths[modPathID].endPath_) {
0677             continue;
0678           }
0679           ++nonEndPaths;
0680           for (auto depPathID : statusOfModules[depIndex].pathsOn_) {
0681             if (depPathID == modPathID) {
0682               ++count;
0683               break;
0684             }
0685           }
0686         }
0687         if (count != 0 and count != nonEndPaths) {
0688           std::ostringstream onStr;
0689           std::ostringstream missingStr;
0690 
0691           for (auto modPathID : mod.pathsOn_) {
0692             if (statusOfPaths[modPathID].endPath_) {
0693               continue;
0694             }
0695             bool found = false;
0696             for (auto depPathID : statusOfModules[depIndex].pathsOn_) {
0697               if (depPathID == modPathID) {
0698                 found = true;
0699               }
0700             }
0701             auto& s = statusOfPaths[modPathID];
0702             if (found) {
0703               onStr << pathName(s) << " ";
0704             } else {
0705               missingStr << pathName(s) << " ";
0706             }
0707           }
0708           throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
0709               << "Paths are non consistent\n"
0710               << "  module '" << moduleIndexToNames[modIndex] << "' depends on '" << moduleIndexToNames[depIndex]
0711               << "' which appears on paths\n  " << onStr.str() << "\nbut is missing from\n  " << missingStr.str();
0712         }
0713       }
0714       ++modIndex;
0715     }
0716 
0717     //Check to see if for each path if the order of the modules is correct based on dependencies
0718     auto allDependencies = findAllDependenciesForModules(statusOfModules);
0719     for (auto& p : statusOfPaths) {
0720       for (unsigned long int i = 0; p.nModules_ > 0 and i < p.nModules_ - 1; ++i) {
0721         auto moduleID = p.modulesOnPath_[i];
0722         if (not allDependencies[moduleID].empty()) {
0723           for (unsigned long int j = i + 1; j < p.nModules_; ++j) {
0724             auto testModuleID = p.modulesOnPath_[j];
0725             if (allDependencies[moduleID].find(testModuleID) != allDependencies[moduleID].end()) {
0726               throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
0727                   << "Dependent module later on Path\n"
0728                   << "  module '" << moduleIndexToNames[moduleID] << "' depends on '"
0729                   << moduleIndexToNames[testModuleID] << "' which is later on path " << pathName(p);
0730             }
0731           }
0732         }
0733       }
0734     }
0735   }
0736 }  // namespace edm