Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2025-04-30 22:24:09

0001 #include "FWCore/Framework/interface/PathsAndConsumesOfModules.h"
0002 
0003 #include "FWCore/Framework/interface/ESProducer.h"
0004 #include "FWCore/Framework/interface/EventSetupProvider.h"
0005 #include "FWCore/Framework/interface/EventSetupRecordProvider.h"
0006 #include "FWCore/Framework/interface/Schedule.h"
0007 #include "FWCore/Framework/interface/maker/Worker.h"
0008 #include "FWCore/Framework/interface/ESModuleProducesInfo.h"
0009 #include "FWCore/Framework/interface/ESModuleConsumesMinimalInfo.h"
0010 #include "FWCore/Framework/interface/EventSetupRecordKey.h"
0011 #include "FWCore/ServiceRegistry/interface/ESModuleConsumesInfo.h"
0012 #include "FWCore/ServiceRegistry/interface/ModuleConsumesESInfo.h"
0013 #include "FWCore/ServiceRegistry/interface/ModuleConsumesInfo.h"
0014 #include "FWCore/Utilities/interface/EDMException.h"
0015 #include "DataFormats/Provenance/interface/ProductResolverIndexHelper.h"
0016 #include "DataFormats/Provenance/interface/ProductRegistry.h"
0017 #include <algorithm>
0018 #include <limits>
0019 #include <unordered_set>
0020 #include <utility>
0021 #include <set>
0022 
0023 #include <iostream>  // for debugging
0024 
0025 namespace edm {
0026 
0027   namespace {
0028     void insertFoundModuleLabel(edm::KindOfType consumedTypeKind,
0029                                 edm::TypeID consumedType,
0030                                 const char* consumedModuleLabel,
0031                                 const char* consumedProductInstance,
0032                                 std::vector<ModuleDescription const*>& modules,
0033                                 std::set<std::string>& alreadyFound,
0034                                 std::map<std::string, ModuleDescription const*> const& labelsToDesc,
0035                                 ProductRegistry const& preg) {
0036       // Convert from label string to module description, eliminate duplicates,
0037       // then insert into the vector of modules
0038       if (auto it = labelsToDesc.find(consumedModuleLabel); it != labelsToDesc.end()) {
0039         if (alreadyFound.insert(consumedModuleLabel).second) {
0040           modules.push_back(it->second);
0041         }
0042         return;
0043       }
0044       // Deal with EDAlias's by converting to the original module label first
0045       if (auto aliasToModuleLabels =
0046               preg.aliasToModules(consumedTypeKind, consumedType, consumedModuleLabel, consumedProductInstance);
0047           not aliasToModuleLabels.empty()) {
0048         bool foundInLabelsToDesc = false;
0049         for (auto const& label : aliasToModuleLabels) {
0050           if (auto it = labelsToDesc.find(label); it != labelsToDesc.end()) {
0051             if (alreadyFound.insert(label).second) {
0052               modules.push_back(it->second);
0053             }
0054             foundInLabelsToDesc = true;
0055           } else {
0056             if (label == "source") {
0057               foundInLabelsToDesc = true;
0058             }
0059           }
0060         }
0061         if (foundInLabelsToDesc) {
0062           return;
0063         }
0064       }
0065       // Ignore the source products, we are only interested in module products.
0066       // As far as I know, it should never be anything else so throw if something
0067       // unknown gets passed in.
0068       if (std::string_view(consumedModuleLabel) != "source") {
0069         throw cms::Exception("EDConsumerBase", "insertFoundModuleLabel")
0070             << "Couldn't find ModuleDescription for the consumed product type: '" << consumedType.className()
0071             << "' module label: '" << consumedModuleLabel << "' product instance name: '" << consumedProductInstance
0072             << "'";
0073       }
0074     }
0075 
0076     void modulesWhoseProductsAreConsumed(Worker* iWorker,
0077                                          std::array<std::vector<ModuleDescription const*>*, NumBranchTypes>& modulesAll,
0078                                          ProductRegistry const& preg,
0079                                          std::map<std::string, ModuleDescription const*> const& labelsToDesc,
0080                                          std::string const& processName) {
0081       std::set<std::string> alreadyFound;
0082 
0083       for (ModuleConsumesInfo const& consumesInfo : iWorker->moduleConsumesInfos()) {
0084         ProductResolverIndexHelper const& helper = *preg.productLookup(consumesInfo.branchType());
0085         std::vector<ModuleDescription const*>& modules = *modulesAll[consumesInfo.branchType()];
0086 
0087         auto consumedModuleLabel = consumesInfo.label();
0088         auto consumedProductInstance = consumesInfo.instance();
0089         auto consumedProcessName = consumesInfo.process();
0090         auto kind = consumesInfo.kindOfType();
0091         auto const& typeID = consumesInfo.type();
0092 
0093         if (not consumesInfo.skipCurrentProcess()) {
0094           // consumesMany used to create empty labels before we removed consumesMany
0095           assert(*consumedModuleLabel.data() != '\0');
0096           if (*consumedProcessName.data() != '\0') {  // process name is specified in consumes call
0097             if (helper.index(kind,
0098                              typeID,
0099                              consumedModuleLabel.data(),
0100                              consumedProductInstance.data(),
0101                              consumedProcessName.data()) != ProductResolverIndexInvalid) {
0102               if (processName == consumedProcessName) {
0103                 insertFoundModuleLabel(kind,
0104                                        typeID,
0105                                        consumedModuleLabel.data(),
0106                                        consumedProductInstance.data(),
0107                                        modules,
0108                                        alreadyFound,
0109                                        labelsToDesc,
0110                                        preg);
0111               }
0112             }
0113           } else {  // process name was empty
0114             auto matches =
0115                 helper.relatedIndexes(kind, typeID, consumedModuleLabel.data(), consumedProductInstance.data());
0116             for (unsigned int j = 0; j < matches.numberOfMatches(); ++j) {
0117               if (processName == matches.processName(j)) {
0118                 insertFoundModuleLabel(kind,
0119                                        typeID,
0120                                        consumedModuleLabel.data(),
0121                                        consumedProductInstance.data(),
0122                                        modules,
0123                                        alreadyFound,
0124                                        labelsToDesc,
0125                                        preg);
0126               }
0127             }
0128           }
0129         }
0130       };
0131     }
0132     void fillModuleAndConsumesInfo(Schedule::AllWorkers const& allWorkers,
0133                                    std::vector<ModuleDescription const*>& allModuleDescriptions,
0134                                    std::vector<std::pair<unsigned int, unsigned int>>& moduleIDToIndex,
0135                                    std::array<std::vector<std::vector<ModuleDescription const*>>, NumBranchTypes>&
0136                                        modulesWhoseProductsAreConsumedBy,
0137                                    ProductRegistry const& preg) {
0138       allModuleDescriptions.clear();
0139       moduleIDToIndex.clear();
0140       for (auto iBranchType = 0U; iBranchType < NumBranchTypes; ++iBranchType) {
0141         modulesWhoseProductsAreConsumedBy[iBranchType].clear();
0142       }
0143 
0144       allModuleDescriptions.reserve(allWorkers.size());
0145       moduleIDToIndex.reserve(allWorkers.size());
0146       for (auto iBranchType = 0U; iBranchType < NumBranchTypes; ++iBranchType) {
0147         modulesWhoseProductsAreConsumedBy[iBranchType].resize(allWorkers.size());
0148       }
0149 
0150       std::map<std::string, ModuleDescription const*> labelToDesc;
0151       unsigned int i = 0;
0152       for (auto const& worker : allWorkers) {
0153         ModuleDescription const* p = worker->description();
0154         allModuleDescriptions.push_back(p);
0155         moduleIDToIndex.push_back(std::pair<unsigned int, unsigned int>(p->id(), i));
0156         labelToDesc[p->moduleLabel()] = p;
0157         ++i;
0158       }
0159       sort_all(moduleIDToIndex);
0160 
0161       i = 0;
0162       for (auto const& worker : allWorkers) {
0163         std::array<std::vector<ModuleDescription const*>*, NumBranchTypes> modules;
0164         for (auto iBranchType = 0U; iBranchType < NumBranchTypes; ++iBranchType) {
0165           modules[iBranchType] = &modulesWhoseProductsAreConsumedBy[iBranchType].at(i);
0166         }
0167         try {
0168           modulesWhoseProductsAreConsumed(worker, modules, preg, labelToDesc, worker->description()->processName());
0169         } catch (cms::Exception& ex) {
0170           ex.addContext("Calling Worker::modulesWhoseProductsAreConsumed() for module " +
0171                         worker->description()->moduleLabel());
0172           throw;
0173         }
0174         ++i;
0175       }
0176     }
0177   }  // namespace
0178 
0179   void PathsAndConsumesOfModules::initialize(Schedule const* schedule, std::shared_ptr<ProductRegistry const> preg) {
0180     schedule_ = schedule;
0181     preg_ = preg;
0182 
0183     paths_.clear();
0184     schedule->triggerPaths(paths_);
0185 
0186     endPaths_.clear();
0187     schedule->endPaths(endPaths_);
0188 
0189     modulesOnPaths_.resize(paths_.size());
0190     unsigned int i = 0;
0191     unsigned int hint = 0;
0192     for (auto const& path : paths_) {
0193       schedule->moduleDescriptionsInPath(path, modulesOnPaths_.at(i), hint);
0194       if (!modulesOnPaths_.at(i).empty())
0195         ++hint;
0196       ++i;
0197     }
0198 
0199     modulesOnEndPaths_.resize(endPaths_.size());
0200     i = 0;
0201     hint = 0;
0202     for (auto const& endpath : endPaths_) {
0203       schedule->moduleDescriptionsInEndPath(endpath, modulesOnEndPaths_.at(i), hint);
0204       if (!modulesOnEndPaths_.at(i).empty())
0205         ++hint;
0206       ++i;
0207     }
0208 
0209     fillModuleAndConsumesInfo(
0210         schedule_->allWorkers(), allModuleDescriptions_, moduleIDToIndex_, modulesWhoseProductsAreConsumedBy_, *preg);
0211   }
0212 
0213   using ProducedByESModule = PathsAndConsumesOfModules::ProducedByESModule;
0214   namespace {
0215     void esModulesWhoseProductsAreConsumed(
0216         Worker* worker,
0217         std::array<std::vector<eventsetup::ComponentDescription const*>*, kNumberOfEventSetupTransitions>& esModules,
0218         ProducedByESModule const& producedByESModule) {
0219       std::array<std::set<std::string>, kNumberOfEventSetupTransitions> alreadyFound;
0220 
0221       for (auto const& info : worker->moduleConsumesMinimalESInfos()) {
0222         auto const& recordInfo = producedByESModule.find(info.record_);
0223         if (recordInfo != producedByESModule.end()) {
0224           auto itFound = recordInfo->second.find(info.dataKey_);
0225           if (itFound != recordInfo->second.end()) {
0226             auto const& componentDescription = itFound->second.componentDescription_;
0227             if (componentDescription) {
0228               std::string const& moduleLabel =
0229                   componentDescription->label_.empty() ? componentDescription->type_ : componentDescription->label_;
0230               //check for matching labels if required
0231               if (info.componentLabel_.empty() || info.componentLabel_ == moduleLabel) {
0232                 auto transitionIndex = static_cast<unsigned int>(info.transition_);
0233                 if (alreadyFound[transitionIndex].insert(moduleLabel).second) {
0234                   esModules[transitionIndex]->push_back(componentDescription);
0235                 }
0236               }
0237             }
0238           }
0239         }
0240       }
0241     }
0242 
0243     std::array<std::vector<std::vector<eventsetup::ComponentDescription const*>>, kNumberOfEventSetupTransitions>
0244     esModulesWhoseProductsAreConsumedByCreate(Schedule::AllWorkers const& allWorkers,
0245                                               ProducedByESModule const& producedByESModule) {
0246       std::array<std::vector<std::vector<eventsetup::ComponentDescription const*>>, kNumberOfEventSetupTransitions>
0247           esModulesWhoseProductsAreConsumedBy;
0248 
0249       for (auto& item : esModulesWhoseProductsAreConsumedBy) {
0250         item.resize(allWorkers.size());
0251       }
0252 
0253       for (unsigned int i = 0; auto const& worker : allWorkers) {
0254         std::array<std::vector<eventsetup::ComponentDescription const*>*, kNumberOfEventSetupTransitions> esModules;
0255         for (auto transition = 0U; transition < kNumberOfEventSetupTransitions; ++transition) {
0256           esModules[transition] = &esModulesWhoseProductsAreConsumedBy[transition].at(i);
0257         }
0258         try {
0259           esModulesWhoseProductsAreConsumed(worker, esModules, producedByESModule);
0260         } catch (cms::Exception& ex) {
0261           ex.addContext("Calling Worker::esModulesWhoseProductsAreConsumed() for module " +
0262                         worker->description()->moduleLabel());
0263           throw;
0264         }
0265         ++i;
0266       }
0267       return esModulesWhoseProductsAreConsumedBy;
0268     }
0269 
0270     ProducedByESModule fillProducedByESModule(eventsetup::EventSetupProvider const& esProvider) {
0271       ProducedByESModule producedByESModule;
0272 
0273       std::set<eventsetup::EventSetupRecordKey> keys;
0274       esProvider.fillKeys(keys);
0275 
0276       for (auto const& recordKey : keys) {
0277         auto const* providers = esProvider.tryToGetRecordProvider(recordKey);
0278         if (providers) {
0279           auto const& datakeys = providers->registeredDataKeys();
0280           auto const& componentsForDataKeys = providers->componentsForRegisteredDataKeys();
0281           auto const& produceMethodIDs = providers->produceMethodIDsForRegisteredDataKeys();
0282           assert(datakeys.size() == componentsForDataKeys.size());
0283           assert(datakeys.size() == produceMethodIDs.size());
0284           for (unsigned int i = 0; i < datakeys.size(); ++i) {
0285             auto const& dataKey = datakeys[i];
0286             auto const* componentDescription = componentsForDataKeys[i];
0287             auto produceMethodID = produceMethodIDs[i];
0288             producedByESModule[recordKey][dataKey] = {componentDescription, produceMethodID};
0289           }
0290         }
0291       }
0292       return producedByESModule;
0293     }
0294 
0295     std::vector<std::vector<eventsetup::ComponentDescription const*>> esModulesWhoseProductsAreConsumedByESModuleCreate(
0296         std::vector<const eventsetup::ESProductResolverProvider*> const& allESProductResolverProviders,
0297         ProducedByESModule const& producedByESModule) {
0298       std::vector<std::vector<eventsetup::ComponentDescription const*>> retValue;
0299 
0300       retValue.resize(allESProductResolverProviders.size());
0301       auto it = retValue.begin();
0302       for (auto& provider : allESProductResolverProviders) {
0303         ESProducer const* esProducer = dynamic_cast<ESProducer const*>(provider);
0304         if (esProducer) {
0305           std::set<unsigned int> alreadyFound;
0306           auto const& consumesInfo = esProducer->esModuleConsumesMinimalInfos();
0307           for (auto const& info : consumesInfo) {
0308             auto const& recordKey = info.recordForDataKey_;
0309             auto const& dataKey = info.dataKey_;
0310             auto itFound = producedByESModule.find(recordKey);
0311             if (itFound != producedByESModule.end()) {
0312               if (dataKey.name() == "@mayConsume") {
0313                 // This is a "may consume" case, we need to find all components that may produce this dataKey
0314                 for (auto const& [dataKey, produceInfo] : itFound->second) {
0315                   auto componentDescription = produceInfo.componentDescription_;
0316                   if (dataKey.type() == info.dataKey_.type()) {
0317                     if (componentDescription and alreadyFound.find(componentDescription->id_) == alreadyFound.end()) {
0318                       alreadyFound.insert(componentDescription->id_);
0319                       it->push_back(componentDescription);
0320                     }
0321                   }
0322                 }
0323               } else {
0324                 // This is a normal case, we need to find the specific component that produces this dataKey
0325                 auto itDataKey = itFound->second.find(dataKey);
0326                 if (itDataKey != itFound->second.end()) {
0327                   eventsetup::ComponentDescription const* componentDescription =
0328                       itDataKey->second.componentDescription_;
0329                   if (componentDescription and alreadyFound.find(componentDescription->id_) == alreadyFound.end()) {
0330                     //an empty label matches any label, else we need an exact match
0331                     if (info.componentLabel_.empty() || info.componentLabel_ == componentDescription->label_) {
0332                       alreadyFound.insert(componentDescription->id_);
0333                       it->push_back(componentDescription);
0334                     }
0335                   }
0336                 }
0337               }
0338             }
0339           }
0340         }
0341         ++it;
0342       }
0343       return retValue;
0344     }
0345 
0346   }  // namespace
0347 
0348   void PathsAndConsumesOfModules::initializeForEventSetup(eventsetup::EventSetupProvider const& eventSetupProvider) {
0349     eventSetupProvider.fillAllESProductResolverProviders(allESProductResolverProviders_);
0350 
0351     producedByESModule_ = fillProducedByESModule(eventSetupProvider);
0352 
0353     esModulesWhoseProductsAreConsumedBy_ =
0354         esModulesWhoseProductsAreConsumedByCreate(schedule_->allWorkers(), producedByESModule_);
0355 
0356     for (unsigned int i = 0; i < allESProductResolverProviders_.size(); ++i) {
0357       eventsetup::ComponentDescription const& componentDescription = allESProductResolverProviders_[i]->description();
0358       esModuleIDToIndex_.emplace_back(componentDescription.id_, i);
0359       allComponentDescriptions_.push_back(&componentDescription);
0360     }
0361     sort_all(esModuleIDToIndex_);
0362 
0363     esModulesWhoseProductsAreConsumedByESModule_ =
0364         esModulesWhoseProductsAreConsumedByESModuleCreate(allESProductResolverProviders_, producedByESModule_);
0365     eventSetupInfoInitialized_ = true;
0366   }
0367 
0368   void PathsAndConsumesOfModules::checkEventSetupInitialization() const {
0369     // It is our intent to eventually migrate all Services using PathsAndConsumesOfModules
0370     // to use the LookupInitializationComplete signal and eliminate that argument from
0371     // the interface of the functions called for preBeginRun. Then everything related to
0372     // this function can be deleted.
0373     if (!eventSetupInfoInitialized_) {
0374       throw cms::Exception("LogicError")
0375           << "In PathsAndConsumesOfModules, a function used to access EventSetup information\n"
0376              "was called before the EventSetup information was initialized. The most likely\n"
0377              "fix for this is for the Service trying to access the information to use the\n"
0378              "LookupInitializationComplete signal instead of the PreBeginJob signal to get\n"
0379              "access to the PathsAndConsumesOfModules object. The EventSetup information is\n"
0380              "not initialized yet at preBeginJob.\n";
0381     }
0382   }
0383 
0384   void PathsAndConsumesOfModules::removeModules(std::vector<ModuleDescription const*> const& modules) {
0385     // First check that no modules on Paths are removed
0386     auto checkPath = [&modules](auto const& paths) {
0387       for (auto const& path : paths) {
0388         for (auto const& description : path) {
0389           if (std::find(modules.begin(), modules.end(), description) != modules.end()) {
0390             throw cms::Exception("Assert")
0391                 << "PathsAndConsumesOfModules::removeModules() is trying to remove a module with label "
0392                 << description->moduleLabel() << " id " << description->id() << " from a Path, this should not happen.";
0393           }
0394         }
0395       }
0396     };
0397     checkPath(modulesOnPaths_);
0398     checkPath(modulesOnEndPaths_);
0399 
0400     // Remove the modules and adjust the indices in idToIndex map
0401     for (auto iModule = 0U; iModule != allModuleDescriptions_.size(); ++iModule) {
0402       auto found = std::find(modules.begin(), modules.end(), allModuleDescriptions_[iModule]);
0403       if (found != modules.end()) {
0404         allModuleDescriptions_.erase(allModuleDescriptions_.begin() + iModule);
0405         for (auto iBranchType = 0U; iBranchType != NumBranchTypes; ++iBranchType) {
0406           modulesWhoseProductsAreConsumedBy_[iBranchType].erase(
0407               modulesWhoseProductsAreConsumedBy_[iBranchType].begin() + iModule);
0408         }
0409         for (auto& idToIndex : moduleIDToIndex_) {
0410           if (idToIndex.second >= iModule) {
0411             idToIndex.second--;
0412           }
0413         }
0414         --iModule;
0415       }
0416     }
0417   }
0418 
0419   std::vector<std::string> const& PathsAndConsumesOfModules::doPaths() const { return paths_; }
0420   std::vector<std::string> const& PathsAndConsumesOfModules::doEndPaths() const { return endPaths_; }
0421 
0422   std::vector<ModuleDescription const*> const& PathsAndConsumesOfModules::doAllModules() const {
0423     return allModuleDescriptions_;
0424   }
0425 
0426   ModuleDescription const* PathsAndConsumesOfModules::doModuleDescription(unsigned int moduleID) const {
0427     unsigned int dummy = 0;
0428     auto target = std::make_pair(moduleID, dummy);
0429     std::vector<std::pair<unsigned int, unsigned int>>::const_iterator iter =
0430         std::lower_bound(moduleIDToIndex_.begin(), moduleIDToIndex_.end(), target);
0431     if (iter == moduleIDToIndex_.end() || iter->first != moduleID) {
0432       throw Exception(errors::LogicError)
0433           << "PathsAndConsumesOfModules::moduleDescription: Unknown moduleID " << moduleID << "\n";
0434     }
0435     return allModuleDescriptions_.at(iter->second);
0436   }
0437 
0438   std::vector<ModuleDescription const*> const& PathsAndConsumesOfModules::doModulesOnPath(unsigned int pathIndex) const {
0439     return modulesOnPaths_.at(pathIndex);
0440   }
0441 
0442   std::vector<ModuleDescription const*> const& PathsAndConsumesOfModules::doModulesOnEndPath(
0443       unsigned int endPathIndex) const {
0444     return modulesOnEndPaths_.at(endPathIndex);
0445   }
0446 
0447   std::vector<ModuleDescription const*> const& PathsAndConsumesOfModules::doModulesWhoseProductsAreConsumedBy(
0448       unsigned int moduleID, BranchType branchType) const {
0449     return modulesWhoseProductsAreConsumedBy_[branchType].at(moduleIndex(moduleID));
0450   }
0451 
0452   std::vector<eventsetup::ComponentDescription const*> const&
0453   PathsAndConsumesOfModules::doESModulesWhoseProductsAreConsumedBy(unsigned int moduleID, Transition transition) const {
0454     checkEventSetupInitialization();
0455     return esModulesWhoseProductsAreConsumedBy_[static_cast<unsigned int>(transition)].at(moduleIndex(moduleID));
0456   }
0457 
0458   std::vector<ModuleConsumesInfo> PathsAndConsumesOfModules::doModuleConsumesInfos(unsigned int moduleID) const {
0459     Worker const* worker = schedule_->allWorkers().at(moduleIndex(moduleID));
0460     return worker->moduleConsumesInfos();
0461   }
0462 
0463   auto const& labelForComponentDescription(eventsetup::ComponentDescription const* description) {
0464     if (description->label_.empty()) {
0465       return description->type_;
0466     }
0467     return description->label_;
0468   }
0469 
0470   std::vector<ModuleConsumesESInfo> PathsAndConsumesOfModules::doModuleConsumesESInfos(unsigned int moduleID) const {
0471     checkEventSetupInitialization();
0472     Worker const* worker = schedule_->allWorkers().at(moduleIndex(moduleID));
0473     auto const& minConsumesESInfos = worker->moduleConsumesMinimalESInfos();
0474     std::vector<ModuleConsumesESInfo> result;
0475     result.reserve(minConsumesESInfos.size());
0476     for (auto const& minInfo : minConsumesESInfos) {
0477       ModuleConsumesESInfo info;
0478       info.eventSetupRecordType_ = minInfo.record_.name();
0479       info.productType_ = minInfo.dataKey_.type().name();
0480       //Moving this to a string_view is safe as the minInfo.dataKey_ does not own the memory
0481       info.productLabel_ = minInfo.dataKey_.name().value();
0482       info.requestedModuleLabel_ = minInfo.componentLabel_;
0483       info.transitionOfConsumer_ = minInfo.transition_;
0484       if (not info.requestedModuleLabel_.empty()) {
0485         auto itRec = producedByESModule_.find(minInfo.record_);
0486         if (itRec != producedByESModule_.end()) {
0487           auto itDataKeyInfo = itRec->second.find(minInfo.dataKey_);
0488           if (itDataKeyInfo != itRec->second.end()) {
0489             info.moduleLabelMismatch_ =
0490                 labelForComponentDescription(itDataKeyInfo->second.componentDescription_) != info.requestedModuleLabel_;
0491           }
0492         }
0493       }
0494 
0495       // Initial values used in the case where there isn't an EventSetup
0496       // module to produce the requested data. Test whether moduleType
0497       // is empty to identify this case because it will be empty if and
0498       // only if this is true.
0499       info.moduleType_ = {};
0500       info.moduleLabel_ = {};
0501       info.produceMethodIDOfProducer_ = 0;
0502       info.isSource_ = false;
0503       info.isLooper_ = false;
0504 
0505       auto itRec = producedByESModule_.find(minInfo.record_);
0506       if (itRec != producedByESModule_.end()) {
0507         auto itDataKeyInfo = itRec->second.find(minInfo.dataKey_);
0508         if (itDataKeyInfo != itRec->second.end()) {
0509           auto produceMethodID = itDataKeyInfo->second.produceMethodID_;
0510           auto componentDescription = itDataKeyInfo->second.componentDescription_;
0511           if (componentDescription) {
0512             info.moduleType_ = componentDescription->type_;
0513             info.moduleLabel_ =
0514                 componentDescription->label_.empty() ? componentDescription->type_ : componentDescription->label_;
0515             info.produceMethodIDOfProducer_ = produceMethodID;
0516             info.isSource_ = componentDescription->isSource_;
0517             info.isLooper_ = componentDescription->isLooper_;
0518           }
0519         }
0520       }
0521       result.emplace_back(info);
0522     };
0523     return result;
0524   }
0525 
0526   unsigned int PathsAndConsumesOfModules::doLargestModuleID() const {
0527     // moduleIDToIndex_ is sorted, so last element has the largest ID
0528     return moduleIDToIndex_.empty() ? 0 : moduleIDToIndex_.back().first;
0529   }
0530 
0531   std::vector<eventsetup::ComponentDescription const*> const& PathsAndConsumesOfModules::doAllESModules() const {
0532     checkEventSetupInitialization();
0533     return allComponentDescriptions_;
0534   }
0535 
0536   eventsetup::ComponentDescription const* PathsAndConsumesOfModules::doComponentDescription(
0537       unsigned int esModuleID) const {
0538     return allComponentDescriptions_.at(esModuleIndex(esModuleID));
0539   }
0540 
0541   std::vector<std::vector<eventsetup::ComponentDescription const*>> const&
0542   PathsAndConsumesOfModules::doESModulesWhoseProductsAreConsumedByESModule() const {
0543     checkEventSetupInitialization();
0544     return esModulesWhoseProductsAreConsumedByESModule_;
0545   }
0546 
0547   namespace {
0548     std::vector<std::vector<ESModuleConsumesInfo>> esModuleConsumesInfosCreate(
0549         ESProducer const& esProducer, ProducedByESModule const& producedByESModule) {
0550       auto const& consumesInfos = esProducer.esModuleConsumesMinimalInfos();
0551       std::vector<std::vector<ESModuleConsumesInfo>> result;
0552       // The outer vector has an entry per produce method ID
0553       unsigned int largestProduceMethodID = 0;
0554       for (auto const& produced : esProducer.producesInfo()) {
0555         if (produced.produceMethodID() > largestProduceMethodID) {
0556           largestProduceMethodID = produced.produceMethodID();
0557         }
0558       }
0559       result.resize(largestProduceMethodID + 1);
0560       if (consumesInfos.empty()) {
0561         return result;
0562       }
0563       result.resize(consumesInfos.back().produceMethodID_ + 1);
0564 
0565       for (auto const& esConsumesInfo : consumesInfos) {
0566         auto& resultForTransition = result[esConsumesInfo.produceMethodID_];
0567 
0568         ESModuleConsumesInfo info;
0569         info.produceMethodIDOfConsumer_ = esConsumesInfo.produceMethodID_;
0570         info.eventSetupRecordType_ = esConsumesInfo.recordForDataKey_.name();
0571         info.productType_ = esConsumesInfo.dataKey_.type().name();
0572         info.moduleType_ = {};
0573         info.moduleLabel_ = {};
0574         info.produceMethodIDOfProducer_ = 0;
0575         info.isSource_ = false;
0576         info.isLooper_ = false;
0577         info.moduleLabelMismatch_ = false;
0578 
0579         // If there is a chooser this is the special case of a "may consumes"
0580         if (esConsumesInfo.dataKey_.name() == "@mayConsume") {
0581           info.requestedModuleLabel_ = {};
0582           info.mayConsumes_ = true;
0583           info.mayConsumesFirstEntry_ = true;
0584 
0585           //look for matches
0586           auto itRec = producedByESModule.find(esConsumesInfo.recordForDataKey_);
0587           if (itRec == producedByESModule.end()) {
0588             // No producers for this record, so no products can be consumed
0589             info.productLabel_ = {};
0590             info.mayConsumesNoProducts_ = true;
0591             resultForTransition.push_back(info);
0592             continue;
0593           }
0594           // In the "may consumes" case, we iterate over all the possible data products
0595           // the EventSetup can produce with matching record type and product type.
0596           // With the current design of the mayConsumes feature, there is no way to
0597           // know in advance which productLabel or moduleLabel will be requested.
0598           // Maybe none will be. requestedModuleLabel and moduleLabelMismatch
0599           // are meaningless for "may consumes" cases.
0600 
0601           auto const nPreMayConsumes = resultForTransition.size();
0602           for (auto const& products : itRec->second) {
0603             if (products.first.type() == esConsumesInfo.dataKey_.type()) {
0604               // This is a "may consume" case, we need to find all components that may produce this dataKey
0605               auto const& componentDescription = products.second.componentDescription_;
0606               if (componentDescription) {
0607                 info.productLabel_ = products.first.name().value();
0608                 info.moduleType_ = componentDescription->type_;
0609                 info.moduleLabel_ = labelForComponentDescription(componentDescription);
0610                 info.mayConsumesNoProducts_ = false;
0611 
0612                 info.produceMethodIDOfProducer_ = products.second.produceMethodID_;
0613                 info.isSource_ = componentDescription->isSource_;
0614                 info.isLooper_ = componentDescription->isLooper_;
0615                 resultForTransition.push_back(info);
0616                 info.mayConsumesFirstEntry_ = false;
0617               }
0618             }
0619           }
0620           if (resultForTransition.size() == nPreMayConsumes) {
0621             // No products can be consumed, so we add an empty entry
0622             // to indicate that this is a "may consumes" case with no products
0623             info.productLabel_ = {};
0624             info.mayConsumesNoProducts_ = true;
0625             resultForTransition.push_back(info);
0626           }
0627           // Handle cases not involving "may consumes"
0628         } else {
0629           //look for matches
0630           info.productLabel_ = esConsumesInfo.dataKey_.name().value();
0631           info.requestedModuleLabel_ = esConsumesInfo.componentLabel_;
0632           auto itRec = producedByESModule.find(esConsumesInfo.recordForDataKey_);
0633           if (itRec != producedByESModule.end()) {
0634             auto itProduceInfo = itRec->second.find(esConsumesInfo.dataKey_);
0635             if (itProduceInfo != itRec->second.end()) {
0636               auto const componentDescription = itProduceInfo->second.componentDescription_;
0637               info.moduleLabelMismatch_ =
0638                   ((componentDescription) and (not esConsumesInfo.componentLabel_.empty()) and
0639                    esConsumesInfo.componentLabel_ != labelForComponentDescription(componentDescription));
0640               info.mayConsumes_ = false;
0641               info.mayConsumesFirstEntry_ = false;
0642               info.mayConsumesNoProducts_ = false;
0643 
0644               if (componentDescription) {
0645                 info.moduleType_ = componentDescription->type_;
0646                 info.moduleLabel_ = labelForComponentDescription(componentDescription);
0647                 info.produceMethodIDOfProducer_ = itProduceInfo->second.produceMethodID_;
0648                 info.isSource_ = componentDescription->isSource_;
0649                 info.isLooper_ = componentDescription->isLooper_;
0650               }
0651             }
0652           }
0653           resultForTransition.push_back(info);
0654         }
0655       }
0656       return result;
0657     }
0658 
0659   }  // namespace
0660   std::vector<std::vector<ESModuleConsumesInfo>> PathsAndConsumesOfModules::doESModuleConsumesInfos(
0661       unsigned int esModuleID) const {
0662     checkEventSetupInitialization();
0663     eventsetup::ESProductResolverProvider const* provider =
0664         allESProductResolverProviders_.at(esModuleIndex(esModuleID));
0665     ESProducer const* esProducer = dynamic_cast<ESProducer const*>(provider);
0666     if (esProducer) {
0667       return esModuleConsumesInfosCreate(*esProducer, producedByESModule_);
0668     }
0669     return {};
0670   }
0671 
0672   unsigned int PathsAndConsumesOfModules::moduleIndex(unsigned int moduleID) const {
0673     unsigned int dummy = 0;
0674     auto target = std::make_pair(moduleID, dummy);
0675     std::vector<std::pair<unsigned int, unsigned int>>::const_iterator iter =
0676         std::lower_bound(moduleIDToIndex_.begin(), moduleIDToIndex_.end(), target);
0677     if (iter == moduleIDToIndex_.end() || iter->first != moduleID) {
0678       throw Exception(errors::LogicError)
0679           << "PathsAndConsumesOfModules::moduleIndex: Unknown moduleID " << moduleID << "\n";
0680     }
0681     return iter->second;
0682   }
0683 
0684   unsigned int PathsAndConsumesOfModules::esModuleIndex(unsigned int esModuleID) const {
0685     unsigned int dummy = 0;
0686     auto target = std::make_pair(esModuleID, dummy);
0687     std::vector<std::pair<unsigned int, unsigned int>>::const_iterator iter =
0688         std::lower_bound(esModuleIDToIndex_.begin(), esModuleIDToIndex_.end(), target);
0689     if (iter == esModuleIDToIndex_.end() || iter->first != esModuleID) {
0690       throw Exception(errors::LogicError)
0691           << "PathsAndConsumesOfModules::moduleIndex: Unknown esModuleID " << esModuleID << "\n";
0692     }
0693     return iter->second;
0694   }
0695 }  // namespace edm
0696 
0697 namespace {
0698   // helper function for nonConsumedUnscheduledModules,
0699   void findAllConsumedModules(edm::PathsAndConsumesOfModulesBase const& iPnC,
0700                               edm::ModuleDescription const* module,
0701                               std::unordered_set<unsigned int>& consumedModules) {
0702     // If this node of the DAG has been processed already, no need to
0703     // reprocess again
0704     if (consumedModules.find(module->id()) != consumedModules.end()) {
0705       return;
0706     }
0707     consumedModules.insert(module->id());
0708     for (auto iBranchType = 0U; iBranchType != edm::NumBranchTypes; ++iBranchType) {
0709       for (auto const& c :
0710            iPnC.modulesWhoseProductsAreConsumedBy(module->id(), static_cast<edm::BranchType>(iBranchType))) {
0711         findAllConsumedModules(iPnC, c, consumedModules);
0712       }
0713     }
0714   }
0715 }  // namespace
0716 
0717 namespace edm {
0718   std::vector<ModuleDescription const*> nonConsumedUnscheduledModules(edm::PathsAndConsumesOfModulesBase const& iPnC) {
0719     const std::string kTriggerResults("TriggerResults");
0720 
0721     std::vector<std::string> pathNames = iPnC.paths();
0722     const unsigned int kFirstEndPathIndex = pathNames.size();
0723     pathNames.insert(pathNames.end(), iPnC.endPaths().begin(), iPnC.endPaths().end());
0724 
0725     // The goal is to find modules that are not depended upon by
0726     // scheduled modules. To do that, we identify all modules that are
0727     // depended upon by scheduled modules, and do a set subtraction.
0728     //
0729     // First, denote all scheduled modules (i.e. in Paths and
0730     // EndPaths) as "consumers".
0731     std::vector<ModuleDescription const*> consumerModules;
0732     for (unsigned int pathIndex = 0; pathIndex != pathNames.size(); ++pathIndex) {
0733       std::vector<ModuleDescription const*> const* moduleDescriptions;
0734       if (pathIndex < kFirstEndPathIndex) {
0735         moduleDescriptions = &(iPnC.modulesOnPath(pathIndex));
0736       } else {
0737         moduleDescriptions = &(iPnC.modulesOnEndPath(pathIndex - kFirstEndPathIndex));
0738       }
0739       std::copy(moduleDescriptions->begin(), moduleDescriptions->end(), std::back_inserter(consumerModules));
0740     }
0741 
0742     // Then add TriggerResults, and all Paths and EndPaths themselves
0743     // to the set of "consumers" (even if they don't depend on any
0744     // data products, they must not be deleted). Also add anything
0745     // consumed by child SubProcesses to the set of "consumers".
0746     auto const& allModules = iPnC.allModules();
0747     for (auto const& description : allModules) {
0748       if (description->moduleLabel() == kTriggerResults or
0749           std::find(pathNames.begin(), pathNames.end(), description->moduleLabel()) != pathNames.end()) {
0750         consumerModules.push_back(description);
0751       }
0752     }
0753 
0754     // Find modules that have any data dependence path to any module
0755     // in consumerModules.
0756     std::unordered_set<unsigned int> consumedModules;
0757     for (auto& description : consumerModules) {
0758       findAllConsumedModules(iPnC, description, consumedModules);
0759     }
0760 
0761     // All other modules will then be classified as non-consumed, even
0762     // if they would have dependencies within them.
0763     std::vector<ModuleDescription const*> unusedModules;
0764     std::copy_if(allModules.begin(),
0765                  allModules.end(),
0766                  std::back_inserter(unusedModules),
0767                  [&consumedModules](ModuleDescription const* description) {
0768                    return consumedModules.find(description->id()) == consumedModules.end();
0769                  });
0770     return unusedModules;
0771   }
0772 
0773   //====================================
0774   // checkForCorrectness algorithm
0775   //
0776   // The code creates a 'dependency' graph between all
0777   // modules. A module depends on another module if
0778   // 1) it 'consumes' data produced by that module
0779   // 2) it appears directly after the module within a Path
0780   //
0781   // If there is a cycle in the 'dependency' graph then
0782   // the schedule may be unrunnable. The schedule is still
0783   // runnable if all cycles have at least two edges which
0784   // connect modules only by Path dependencies (i.e. not
0785   // linked by a data dependency).
0786   //
0787   //  Example 1:
0788   //  C consumes data from B
0789   //  Path 1: A + B + C
0790   //  Path 2: B + C + A
0791   //
0792   //  Cycle: A after C [p2], C consumes B, B after A [p1]
0793   //  Since this cycle has 2 path only edges it is OK since
0794   //  A and (B+C) are independent so their run order doesn't matter
0795   //
0796   //  Example 2:
0797   //  B consumes A
0798   //  C consumes B
0799   //  Path: C + A
0800   //
0801   //  Cycle: A after C [p], C consumes B, B consumes A
0802   //  Since this cycle has 1 path only edge it is unrunnable.
0803   //
0804   //  Example 3:
0805   //  A consumes B
0806   //  B consumes C
0807   //  C consumes A
0808   //  (no Path since unscheduled execution)
0809   //
0810   //  Cycle: A consumes B, B consumes C, C consumes A
0811   //  Since this cycle has 0 path only edges it is unrunnable.
0812   //====================================
0813 
0814   namespace {
0815     struct ModuleStatus {
0816       std::vector<unsigned int> dependsOn_;
0817       std::vector<unsigned int> pathsOn_;
0818       unsigned long long lastSearch = 0;
0819       bool onPath_ = false;
0820       bool wasRun_ = false;
0821     };
0822 
0823     struct PathStatus {
0824       std::vector<unsigned int> modulesOnPath_;
0825       unsigned long int activeModuleSlot_ = 0;
0826       unsigned long int nModules_ = 0;
0827       unsigned int index_ = 0;
0828       bool endPath_ = false;
0829     };
0830 
0831     class CircularDependencyException {};
0832 
0833     bool checkIfCanRun(unsigned long long searchIndex,
0834                        unsigned int iModuleToCheckID,
0835                        std::vector<ModuleStatus>& iModules,
0836                        std::vector<unsigned int>& stackTrace) {
0837       auto& status = iModules[iModuleToCheckID];
0838       if (status.wasRun_) {
0839         return true;
0840       }
0841 
0842       if (status.lastSearch == searchIndex) {
0843         //check to see if the module is already on the stack
0844         // checking searchIndex is insufficient as multiple modules
0845         // in this search may be dependent upon the same module
0846         auto itFound = std::find(stackTrace.begin(), stackTrace.end(), iModuleToCheckID);
0847         if (itFound != stackTrace.end()) {
0848           stackTrace.push_back(iModuleToCheckID);
0849           throw CircularDependencyException();
0850         }
0851         //we have already checked this module's dependencies during this search
0852         return false;
0853       }
0854       stackTrace.push_back(iModuleToCheckID);
0855       status.lastSearch = searchIndex;
0856 
0857       bool allDependenciesRan = true;
0858       for (auto index : status.dependsOn_) {
0859         auto& dep = iModules[index];
0860         if (dep.onPath_) {
0861           if (not dep.wasRun_) {
0862             allDependenciesRan = false;
0863           }
0864         } else if (not checkIfCanRun(searchIndex, index, iModules, stackTrace)) {
0865           allDependenciesRan = false;
0866         }
0867       }
0868       if (allDependenciesRan) {
0869         status.wasRun_ = true;
0870       }
0871       stackTrace.pop_back();
0872 
0873       return allDependenciesRan;
0874     }
0875 
0876     void findAllDependenciesForModule(unsigned int iModID,
0877                                       std::vector<ModuleStatus> const& iStatus,
0878                                       std::vector<std::unordered_set<unsigned int>>& oDependencies) {
0879       auto const& dependsOn = iStatus[iModID].dependsOn_;
0880       if (dependsOn.empty() or !oDependencies[iModID].empty()) {
0881         return;
0882       }
0883       oDependencies[iModID].insert(dependsOn.begin(), dependsOn.end());
0884       for (auto dep : dependsOn) {
0885         findAllDependenciesForModule(dep, iStatus, oDependencies);
0886         oDependencies[iModID].merge(oDependencies[dep]);
0887       }
0888     }
0889     std::vector<std::unordered_set<unsigned int>> findAllDependenciesForModules(
0890         std::vector<ModuleStatus> const& iStatus) {
0891       std::vector<std::unordered_set<unsigned int>> ret(iStatus.size());
0892       for (unsigned int id = 0; id < iStatus.size(); ++id) {
0893         findAllDependenciesForModule(id, iStatus, ret);
0894       }
0895       return ret;
0896     }
0897   }  // namespace
0898   void checkForModuleDependencyCorrectness(edm::PathsAndConsumesOfModulesBase const& iPnC, bool iPrintDependencies) {
0899     constexpr auto kInvalidIndex = std::numeric_limits<unsigned int>::max();
0900 
0901     //Need to lookup ids to names quickly
0902     std::unordered_map<unsigned int, std::string> moduleIndexToNames;
0903 
0904     std::unordered_map<std::string, unsigned int> pathStatusInserterModuleLabelToModuleID;
0905 
0906     //for testing, state that TriggerResults is at the end of all paths
0907     const std::string kTriggerResults("TriggerResults");
0908     const std::string kPathStatusInserter("PathStatusInserter");
0909     const std::string kEndPathStatusInserter("EndPathStatusInserter");
0910     unsigned int kTriggerResultsIndex = kInvalidIndex;
0911     ModuleStatus triggerResultsStatus;
0912     unsigned int largestIndex = 0;
0913     for (auto const& description : iPnC.allModules()) {
0914       moduleIndexToNames.insert(std::make_pair(description->id(), description->moduleLabel()));
0915       if (kTriggerResults == description->moduleLabel()) {
0916         kTriggerResultsIndex = description->id();
0917       }
0918       if (description->id() > largestIndex) {
0919         largestIndex = description->id();
0920       }
0921       if (description->moduleName() == kPathStatusInserter) {
0922         triggerResultsStatus.dependsOn_.push_back(description->id());
0923       }
0924       if (description->moduleName() == kPathStatusInserter || description->moduleName() == kEndPathStatusInserter) {
0925         pathStatusInserterModuleLabelToModuleID[description->moduleLabel()] = description->id();
0926       }
0927     }
0928 
0929     std::vector<ModuleStatus> statusOfModules(largestIndex + 1);
0930     for (auto const& nameID : pathStatusInserterModuleLabelToModuleID) {
0931       statusOfModules[nameID.second].onPath_ = true;
0932       unsigned int pathIndex;
0933       auto const& paths = iPnC.paths();
0934       auto itFound = std::find(paths.begin(), paths.end(), nameID.first);
0935       if (itFound != paths.end()) {
0936         pathIndex = itFound - paths.begin();
0937       } else {
0938         auto const& endPaths = iPnC.endPaths();
0939         itFound = std::find(endPaths.begin(), endPaths.end(), nameID.first);
0940         assert(itFound != endPaths.end());
0941         pathIndex = itFound - endPaths.begin() + iPnC.paths().size();
0942       }
0943       statusOfModules[nameID.second].pathsOn_.push_back(pathIndex);
0944     }
0945     if (kTriggerResultsIndex != kInvalidIndex) {
0946       statusOfModules[kTriggerResultsIndex] = std::move(triggerResultsStatus);
0947     }
0948 
0949     std::vector<PathStatus> statusOfPaths(iPnC.paths().size() + iPnC.endPaths().size());
0950 
0951     //If there are no paths, no modules will run so nothing to check
0952     if (statusOfPaths.empty()) {
0953       return;
0954     }
0955 
0956     {
0957       auto nPaths = iPnC.paths().size();
0958       for (unsigned int p = 0; p < nPaths; ++p) {
0959         auto& status = statusOfPaths[p];
0960         status.index_ = p;
0961         status.modulesOnPath_.reserve(iPnC.modulesOnPath(p).size() + 1);
0962         std::unordered_set<unsigned int> uniqueModules;
0963         for (auto const& mod : iPnC.modulesOnPath(p)) {
0964           if (uniqueModules.insert(mod->id()).second) {
0965             status.modulesOnPath_.push_back(mod->id());
0966             statusOfModules[mod->id()].onPath_ = true;
0967             statusOfModules[mod->id()].pathsOn_.push_back(p);
0968           }
0969         }
0970         status.nModules_ = uniqueModules.size() + 1;
0971 
0972         //add the PathStatusInserter at the end
0973         auto found = pathStatusInserterModuleLabelToModuleID.find(iPnC.paths()[p]);
0974         assert(found != pathStatusInserterModuleLabelToModuleID.end());
0975         status.modulesOnPath_.push_back(found->second);
0976       }
0977     }
0978     {
0979       auto offset = iPnC.paths().size();
0980       auto nPaths = iPnC.endPaths().size();
0981       for (unsigned int p = 0; p < nPaths; ++p) {
0982         auto& status = statusOfPaths[p + offset];
0983         status.endPath_ = true;
0984         status.index_ = p;
0985         status.modulesOnPath_.reserve(iPnC.modulesOnEndPath(p).size() + 1);
0986         std::unordered_set<unsigned int> uniqueModules;
0987         for (auto const& mod : iPnC.modulesOnEndPath(p)) {
0988           if (uniqueModules.insert(mod->id()).second) {
0989             status.modulesOnPath_.push_back(mod->id());
0990             statusOfModules[mod->id()].onPath_ = true;
0991             statusOfModules[mod->id()].pathsOn_.push_back(p + offset);
0992           }
0993         }
0994         status.nModules_ = uniqueModules.size();
0995 
0996         //add the EndPathStatusInserter at the end
0997         auto found = pathStatusInserterModuleLabelToModuleID.find(iPnC.endPaths()[p]);
0998         if (found != pathStatusInserterModuleLabelToModuleID.end()) {
0999           status.modulesOnPath_.push_back(found->second);
1000           ++status.nModules_;
1001         }
1002       }
1003     }
1004 
1005     for (auto const& description : iPnC.allModules()) {
1006       unsigned int const moduleIndex = description->id();
1007       auto const& dependentModules = iPnC.modulesWhoseProductsAreConsumedBy(moduleIndex);
1008       auto& deps = statusOfModules[moduleIndex];
1009       deps.dependsOn_.reserve(dependentModules.size());
1010       for (auto const& depDescription : dependentModules) {
1011         if (iPrintDependencies) {
1012           edm::LogAbsolute("ModuleDependency")
1013               << "ModuleDependency '" << description->moduleLabel() << "' depends on data products from module '"
1014               << depDescription->moduleLabel() << "'";
1015         }
1016         deps.dependsOn_.push_back(depDescription->id());
1017       }
1018     }
1019 
1020     unsigned int nPathsFinished = 0;
1021     for (auto const& status : statusOfPaths) {
1022       if (status.nModules_ == 0) {
1023         ++nPathsFinished;
1024       }
1025     }
1026 
1027     //if a circular dependency exception happens, stackTrace has the info
1028     std::vector<unsigned int> stackTrace;
1029     bool madeForwardProgress = true;
1030     try {
1031       //'simulate' the running of the paths. On each step mark each module as 'run'
1032       // if all the module's dependencies were fulfilled in a previous step
1033       unsigned long long searchIndex = 0;
1034       while (madeForwardProgress and nPathsFinished != statusOfPaths.size()) {
1035         madeForwardProgress = false;
1036         for (auto& p : statusOfPaths) {
1037           //the path has already completed in an earlier pass
1038           if (p.activeModuleSlot_ == p.nModules_) {
1039             continue;
1040           }
1041           ++searchIndex;
1042           bool didRun = checkIfCanRun(searchIndex, p.modulesOnPath_[p.activeModuleSlot_], statusOfModules, stackTrace);
1043           if (didRun) {
1044             madeForwardProgress = true;
1045             ++p.activeModuleSlot_;
1046             if (p.activeModuleSlot_ == p.nModules_) {
1047               ++nPathsFinished;
1048             }
1049           }
1050         }
1051       }
1052     } catch (CircularDependencyException const&) {
1053       //the last element in stackTrace must appear somewhere earlier in stackTrace
1054       std::ostringstream oStr;
1055 
1056       unsigned int lastIndex = stackTrace.front();
1057       bool firstSkipped = false;
1058       for (auto id : stackTrace) {
1059         if (firstSkipped) {
1060           oStr << "  module '" << moduleIndexToNames[lastIndex] << "' depends on " << moduleIndexToNames[id] << "\n";
1061         } else {
1062           firstSkipped = true;
1063         }
1064         lastIndex = id;
1065       }
1066       throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
1067           << "Circular module dependency found in configuration\n"
1068           << oStr.str();
1069     }
1070 
1071     auto pathName = [&](PathStatus const& iP) {
1072       if (iP.endPath_) {
1073         return iPnC.endPaths()[iP.index_];
1074       }
1075       return iPnC.paths()[iP.index_];
1076     };
1077 
1078     //The program would deadlock
1079     if (not madeForwardProgress) {
1080       std::ostringstream oStr;
1081       auto modIndex = std::numeric_limits<unsigned int>::max();
1082       unsigned int presentPath;
1083       for (auto itP = statusOfPaths.begin(); itP != statusOfPaths.end(); ++itP) {
1084         auto const& p = *itP;
1085         if (p.activeModuleSlot_ == p.nModules_) {
1086           continue;
1087         }
1088         //this path is stuck
1089         modIndex = p.modulesOnPath_[p.activeModuleSlot_];
1090         presentPath = itP - statusOfPaths.begin();
1091         break;
1092       }
1093       //NOTE the following should always be true as at least 1 path should be stuc.
1094       // I've added the condition just to be paranoid.
1095       if (modIndex != std::numeric_limits<unsigned int>::max()) {
1096         struct ProgressInfo {
1097           ProgressInfo(unsigned int iMod, unsigned int iPath, bool iPreceeds = false)
1098               : moduleIndex_(iMod), pathIndex_(iPath), preceeds_(iPreceeds) {}
1099 
1100           ProgressInfo(unsigned int iMod) : moduleIndex_(iMod), pathIndex_{}, preceeds_(false) {}
1101 
1102           unsigned int moduleIndex_ = std::numeric_limits<unsigned int>::max();
1103           std::optional<unsigned int> pathIndex_;
1104           bool preceeds_;
1105 
1106           bool operator==(ProgressInfo const& iOther) const {
1107             return moduleIndex_ == iOther.moduleIndex_ and pathIndex_ == iOther.pathIndex_;
1108           }
1109         };
1110 
1111         std::vector<ProgressInfo> progressTrace;
1112         progressTrace.emplace_back(modIndex, presentPath);
1113 
1114         //The following starts from the first found unrun module on a path. It then finds
1115         // the first modules it depends on that was not run. If that module is on a Task
1116         // it then repeats the check for that module's dependencies. If that module is on
1117         // a path, it checks to see if that module is the first unrun module of a path
1118         // and if so it repeats the check for that module's dependencies, if not it
1119         // checks the dependencies of the stuck module on that path.
1120         // Eventually, all these checks should allow us to find a cycle of modules.
1121 
1122         //NOTE: the only way foundUnrunModule should ever by false by the end of the
1123         // do{}while loop is if there is a bug in the algorithm. I've included it to
1124         // try to avoid that case causing an infinite loop in the program.
1125         bool foundUnrunModule;
1126         do {
1127           //check dependencies looking for stuff not run and on a path
1128           foundUnrunModule = false;
1129           for (auto depMod : statusOfModules[modIndex].dependsOn_) {
1130             auto const& depStatus = statusOfModules[depMod];
1131             if (not depStatus.wasRun_ and depStatus.onPath_) {
1132               foundUnrunModule = true;
1133               //last run on a path?
1134               bool lastOnPath = false;
1135               unsigned int foundPath;
1136               for (auto pathOn : depStatus.pathsOn_) {
1137                 auto const& depPaths = statusOfPaths[pathOn];
1138                 if (depPaths.modulesOnPath_[depPaths.activeModuleSlot_] == depMod) {
1139                   lastOnPath = true;
1140                   foundPath = pathOn;
1141                   break;
1142                 }
1143               }
1144               if (lastOnPath) {
1145                 modIndex = depMod;
1146                 progressTrace.emplace_back(modIndex, foundPath);
1147               } else {
1148                 //some earlier module on the same path is stuck
1149                 progressTrace.emplace_back(depMod, depStatus.pathsOn_[0]);
1150                 auto const& depPath = statusOfPaths[depStatus.pathsOn_[0]];
1151                 modIndex = depPath.modulesOnPath_[depPath.activeModuleSlot_];
1152                 progressTrace.emplace_back(modIndex, depStatus.pathsOn_[0], true);
1153               }
1154               break;
1155             }
1156           }
1157           if (not foundUnrunModule) {
1158             //check unscheduled modules
1159             for (auto depMod : statusOfModules[modIndex].dependsOn_) {
1160               auto const& depStatus = statusOfModules[depMod];
1161               if (not depStatus.wasRun_ and not depStatus.onPath_) {
1162                 foundUnrunModule = true;
1163                 progressTrace.emplace_back(depMod);
1164                 modIndex = depMod;
1165                 break;
1166               }
1167             }
1168           }
1169         } while (foundUnrunModule and (0 == std::count(progressTrace.begin(),
1170                                                        progressTrace.begin() + progressTrace.size() - 1,
1171                                                        progressTrace.back())));
1172 
1173         auto printTrace = [&](auto& oStr, auto itBegin, auto itEnd) {
1174           for (auto itTrace = itBegin; itTrace != itEnd; ++itTrace) {
1175             if (itTrace != itBegin) {
1176               if (itTrace->preceeds_) {
1177                 oStr << " and follows module '" << moduleIndexToNames[itTrace->moduleIndex_] << "' on the path\n";
1178               } else {
1179                 oStr << " and depends on module '" << moduleIndexToNames[itTrace->moduleIndex_] << "'\n";
1180               }
1181             }
1182             if (itTrace + 1 != itEnd) {
1183               if (itTrace->pathIndex_) {
1184                 oStr << "  module '" << moduleIndexToNames[itTrace->moduleIndex_] << "' is on path '"
1185                      << pathName(statusOfPaths[*itTrace->pathIndex_]) << "'";
1186               } else {
1187                 oStr << "  module '" << moduleIndexToNames[itTrace->moduleIndex_] << "' is in a task";
1188               }
1189             }
1190           }
1191         };
1192 
1193         if (not foundUnrunModule) {
1194           //If we get here, this suggests a problem with either the algorithm that finds problems or the algorithm
1195           // that attempts to report the problem
1196           oStr << "Algorithm Error, unable to find problem. Contact framework group.\n Traced problem this far\n";
1197           printTrace(oStr, progressTrace.begin(), progressTrace.end());
1198         } else {
1199           printTrace(
1200               oStr, std::find(progressTrace.begin(), progressTrace.end(), progressTrace.back()), progressTrace.end());
1201         }
1202       }
1203       //the schedule deadlocked
1204       throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
1205           << "The Path/EndPath configuration could cause the job to deadlock\n"
1206           << oStr.str();
1207     }
1208 
1209     //NOTE: although the following conditions are not needed for safe running, they are
1210     // policy choices the collaboration has made.
1211 
1212     //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
1213     // as module A then B must appear on ALL paths that have A.
1214     unsigned int modIndex = 0;
1215     for (auto& mod : statusOfModules) {
1216       for (auto& depIndex : mod.dependsOn_) {
1217         std::size_t count = 0;
1218         std::size_t nonEndPaths = 0;
1219         for (auto modPathID : mod.pathsOn_) {
1220           if (statusOfPaths[modPathID].endPath_) {
1221             continue;
1222           }
1223           ++nonEndPaths;
1224           for (auto depPathID : statusOfModules[depIndex].pathsOn_) {
1225             if (depPathID == modPathID) {
1226               ++count;
1227               break;
1228             }
1229           }
1230         }
1231         if (count != 0 and count != nonEndPaths) {
1232           std::ostringstream onStr;
1233           std::ostringstream missingStr;
1234 
1235           for (auto modPathID : mod.pathsOn_) {
1236             if (statusOfPaths[modPathID].endPath_) {
1237               continue;
1238             }
1239             bool found = false;
1240             for (auto depPathID : statusOfModules[depIndex].pathsOn_) {
1241               if (depPathID == modPathID) {
1242                 found = true;
1243               }
1244             }
1245             auto& s = statusOfPaths[modPathID];
1246             if (found) {
1247               onStr << pathName(s) << " ";
1248             } else {
1249               missingStr << pathName(s) << " ";
1250             }
1251           }
1252           throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
1253               << "Paths are non consistent\n"
1254               << "  module '" << moduleIndexToNames[modIndex] << "' depends on '" << moduleIndexToNames[depIndex]
1255               << "' which appears on paths\n  " << onStr.str() << "\nbut is missing from\n  " << missingStr.str();
1256         }
1257       }
1258       ++modIndex;
1259     }
1260 
1261     //Check to see if for each path if the order of the modules is correct based on dependencies
1262     auto allDependencies = findAllDependenciesForModules(statusOfModules);
1263     for (auto& p : statusOfPaths) {
1264       for (unsigned long int i = 0; p.nModules_ > 0 and i < p.nModules_ - 1; ++i) {
1265         auto moduleID = p.modulesOnPath_[i];
1266         if (not allDependencies[moduleID].empty()) {
1267           for (unsigned long int j = i + 1; j < p.nModules_; ++j) {
1268             auto testModuleID = p.modulesOnPath_[j];
1269             if (allDependencies[moduleID].find(testModuleID) != allDependencies[moduleID].end()) {
1270               throw edm::Exception(edm::errors::ScheduleExecutionFailure, "Unrunnable schedule\n")
1271                   << "Dependent module later on Path\n"
1272                   << "  module '" << moduleIndexToNames[moduleID] << "' depends on '"
1273                   << moduleIndexToNames[testModuleID] << "' which is later on path " << pathName(p);
1274             }
1275           }
1276         }
1277       }
1278     }
1279   }
1280 }  // namespace edm