Services/plugins/DependencyGraph.cc

0001 /*
0002  * Simple Service to make a GraphViz graph of the modules runtime dependencies:
0003  *   - draw hard dependencies according to the "consumes" dependencies;
0004  *     (only event dependences included, not run/lumi/process block dependences)
0005  *   - draw soft dependencies to reflect the order of scheduled modules in each path;
0006  *
0007  * Use GraphViz dot to generate an SVG representation of the dependencies:
0008  *
0009  *   dot -v -Tsvg dependency.dot -o dependency.svg
0010  *
0011  */
0012
0013 #include <cstddef>
0014 #include <fstream>
0015 #include <limits>
0016 #include <map>
0017 #include <string>
0018 #include <type_traits>
0019 #include <unordered_set>
0020 #include <utility>
0021 #include <vector>
0022
0023 // boost optional (used by boost graph) results in some false positives with -Wmaybe-uninitialized
0024 #pragma GCC diagnostic push
0025 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
0026 #include <boost/graph/adjacency_list.hpp>
0027 #include <boost/graph/graphviz.hpp>
0028 #include <boost/graph/lookup_edge.hpp>
0029 #pragma GCC diagnostic pop
0030
0031 #include "DataFormats/Provenance/interface/ModuleDescription.h"
0032 #include "FWCore/ParameterSet/interface/ConfigurationDescriptions.h"
0033 #include "FWCore/ParameterSet/interface/ParameterSet.h"
0034 #include "FWCore/ParameterSet/interface/ParameterSetDescription.h"
0035 #include "FWCore/ParameterSet/interface/Registry.h"
0036 #include "FWCore/ServiceRegistry/interface/ActivityRegistry.h"
0037 #include "FWCore/ServiceRegistry/interface/PathsAndConsumesOfModulesBase.h"
0038 #include "FWCore/ServiceRegistry/interface/ProcessContext.h"
0039 #include "FWCore/MessageLogger/interface/MessageLogger.h"
0040
0041 using namespace edm;
0042 using namespace edm::service;
0043
0044 namespace {
0045   namespace {
0046
0047     constexpr std::size_t kInvalidVertex = std::numeric_limits<std::size_t>::max();
0048
0049     template <typename T>
0050     std::unordered_set<T> make_unordered_set(std::vector<T> &&entries) {
0051       std::unordered_set<T> u;
0052       for (T &entry : entries)
0053         u.insert(std::move(entry));
0054       return u;
0055     }
0056
0057   }  // namespace
0058 }  // namespace
0059
0060 class DependencyGraph {
0061 public:
0062   DependencyGraph(const ParameterSet &, ActivityRegistry &);
0063
0064   static void fillDescriptions(edm::ConfigurationDescriptions &);
0065
0066   void preSourceConstruction(ModuleDescription const &);
0067   void lookupInitializationComplete(PathsAndConsumesOfModulesBase const &, ProcessContext const &);
0068
0069 private:
0070   bool highlighted(std::string const &module) { return (m_highlightModules.find(module) != m_highlightModules.end()); }
0071
0072   enum class EDMModuleType { Unknown, Source, ESSource, ESProducer, EDAnalyzer, EDProducer, EDFilter, OutputModule };
0073
0074   static constexpr const char *module_type_desc[]{
0075       "Unknown", "Source", "ESSource", "ESProducer", "EDAnalyzer", "EDProducer", "EDFilter", "OutputModule"};
0076
0077   static constexpr const char *shapes[]{
0078       "note",      // Unknown
0079       "oval",      // Source
0080       "cylinder",  // ESSource
0081       "cylinder",  // ESProducer
0082       "oval",      // EDAnalyzer
0083       "box",       // EDProducer
0084       "diamond",   // EDFilter
0085       "oval",      // OutputModule
0086   };
0087
0088   static EDMModuleType edmModuleTypeEnum(edm::ModuleDescription const &module);
0089
0090   static const char *edmModuleType(edm::ModuleDescription const &module);
0091
0092   struct node {
0093     std::string label;
0094     std::string class_;
0095     unsigned int id;
0096     EDMModuleType type;
0097     bool scheduled;
0098   };
0099
0100   using GraphvizAttributes = std::map<std::string, std::string>;
0101
0102   // directed graph, with `node` properties attached to each vertex
0103   using GraphType = boost::subgraph<boost::adjacency_list<
0104       // edge list
0105       boost::vecS,
0106       // vertex list
0107       boost::vecS,
0108       boost::directedS,
0109       // vertex properties
0110       boost::property<boost::vertex_attribute_t,
0111                       GraphvizAttributes,  // Graphviz vertex attributes
0112                       node>,
0113       // edge propoerties
0114       boost::property<boost::edge_index_t,
0115                       int,  // used internally by boost::subgraph
0116                       boost::property<boost::edge_attribute_t, GraphvizAttributes>>,  // Graphviz edge attributes
0117       // graph properties
0118       boost::property<
0119           boost::graph_name_t,
0120           std::string,  // name each boost::subgraph
0121           boost::property<boost::graph_graph_attribute_t,
0122                           GraphvizAttributes,  // Graphviz graph attributes
0123                           boost::property<boost::graph_vertex_attribute_t,
0124                                           GraphvizAttributes,
0125                                           boost::property<boost::graph_edge_attribute_t, GraphvizAttributes>>>>>>;
0126   GraphType m_graph;
0127
0128   std::string m_filename;
0129   std::unordered_set<std::string> m_highlightModules;
0130
0131   bool m_showPathDependencies;
0132
0133   std::vector<std::size_t> m_moduleIDToGraphIndex;
0134   std::size_t m_nextGraphIndexToAdd = 0;
0135 };
0136
0137 constexpr const char *DependencyGraph::module_type_desc[];
0138
0139 constexpr const char *DependencyGraph::shapes[];
0140
0141 DependencyGraph::EDMModuleType DependencyGraph::edmModuleTypeEnum(edm::ModuleDescription const &module) {
0142   auto const &registry = *edm::pset::Registry::instance();
0143   auto const &pset = *registry.getMapped(module.parameterSetID());
0144
0145   if (not pset.existsAs<std::string>("@module_edm_type"))
0146     return EDMModuleType::Unknown;
0147
0148   std::string const &t = pset.getParameter<std::string>("@module_edm_type");
0149   for (EDMModuleType v : {EDMModuleType::Source,
0150                           EDMModuleType::ESSource,
0151                           EDMModuleType::ESProducer,
0152                           EDMModuleType::EDAnalyzer,
0153                           EDMModuleType::EDProducer,
0154                           EDMModuleType::EDFilter,
0155                           EDMModuleType::OutputModule}) {
0156     if (t == module_type_desc[static_cast<std::underlying_type_t<EDMModuleType>>(v)])
0157       return v;
0158   }
0159   return EDMModuleType::Unknown;
0160 }
0161
0162 const char *DependencyGraph::edmModuleType(edm::ModuleDescription const &module) {
0163   return module_type_desc[static_cast<std::underlying_type_t<EDMModuleType>>(edmModuleTypeEnum(module))];
0164 }
0165
0166 void DependencyGraph::fillDescriptions(edm::ConfigurationDescriptions &descriptions) {
0167   edm::ParameterSetDescription desc;
0168   desc.addUntracked<std::string>("fileName", "dependency.dot");
0169   desc.addUntracked<std::vector<std::string>>("highlightModules", {});
0170   desc.addUntracked<bool>("showPathDependencies", true);
0171   descriptions.add("DependencyGraph", desc);
0172 }
0173
0174 DependencyGraph::DependencyGraph(ParameterSet const &config, ActivityRegistry &registry)
0175     : m_filename(config.getUntrackedParameter<std::string>("fileName")),
0176       m_highlightModules(
0177           make_unordered_set(config.getUntrackedParameter<std::vector<std::string>>("highlightModules"))),
0178       m_showPathDependencies(config.getUntrackedParameter<bool>("showPathDependencies")) {
0179   registry.watchPreSourceConstruction(this, &DependencyGraph::preSourceConstruction);
0180   registry.watchLookupInitializationComplete(this, &DependencyGraph::lookupInitializationComplete);
0181 }
0182
0183 // adaptor to use range-based for loops with boost::graph edges(...) and vertices(...) functions
0184 template <typename I>
0185 struct iterator_pair_as_a_range : std::pair<I, I> {
0186 public:
0187   using std::pair<I, I>::pair;
0188
0189   I begin() { return this->first; }
0190   I end() { return this->second; }
0191 };
0192
0193 template <typename I>
0194 iterator_pair_as_a_range<I> make_range(std::pair<I, I> p) {
0195   return iterator_pair_as_a_range<I>(p);
0196 }
0197
0198 void DependencyGraph::preSourceConstruction(ModuleDescription const &module) {
0199   if (module.id() >= m_moduleIDToGraphIndex.size()) {
0200     m_moduleIDToGraphIndex.resize(module.id() + 1, kInvalidVertex);
0201   }
0202   m_moduleIDToGraphIndex[module.id()] = m_nextGraphIndexToAdd;
0203   ++m_nextGraphIndexToAdd;
0204
0205   auto graphIndex = m_moduleIDToGraphIndex[module.id()];
0206
0207   // Create graph vertex for the source module and fill its attributes
0208   boost::add_vertex(m_graph);
0209   m_graph.m_graph[graphIndex] =
0210       node{module.moduleLabel(), module.moduleName(), module.id(), EDMModuleType::Source, true};
0211   auto &attributes = boost::get(boost::get(boost::vertex_attribute, m_graph), graphIndex);
0212   attributes["label"] = module.moduleLabel();
0213   attributes["tooltip"] = module.moduleName();
0214   attributes["shape"] = shapes[static_cast<std::underlying_type_t<EDMModuleType>>(EDMModuleType::Source)];
0215   attributes["style"] = "filled";
0216   attributes["color"] = "black";
0217   attributes["fillcolor"] = highlighted(module.moduleLabel()) ? "lightgreen" : "white";
0218 }
0219
0220 void DependencyGraph::lookupInitializationComplete(PathsAndConsumesOfModulesBase const &pathsAndConsumes,
0221                                                    ProcessContext const &context) {
0222   // set the graph name property to the process name
0223   boost::get_property(m_graph, boost::graph_name) = context.processName();
0224   boost::get_property(m_graph, boost::graph_graph_attribute)["label"] = "process " + context.processName();
0225   boost::get_property(m_graph, boost::graph_graph_attribute)["labelloc"] = "top";
0226
0227   if (pathsAndConsumes.largestModuleID() >= m_moduleIDToGraphIndex.size()) {
0228     m_moduleIDToGraphIndex.resize(pathsAndConsumes.largestModuleID() + 1, kInvalidVertex);
0229   }
0230
0231   auto numberOfSourceGraphVertexes = m_nextGraphIndexToAdd;
0232   for (edm::ModuleDescription const *module : pathsAndConsumes.allModules()) {
0233     m_moduleIDToGraphIndex[module->id()] = m_nextGraphIndexToAdd;
0234     ++m_nextGraphIndexToAdd;
0235   }
0236   auto numberOfGraphVertexes = m_nextGraphIndexToAdd;
0237
0238   // Create graph vertices associated to all modules in the process.
0239   // Note that we skip over source vertexes that were already made
0240   // (currently always 1 source but possibly in the future there
0241   // might be more than 1 source)
0242   for (std::size_t i = numberOfSourceGraphVertexes; i < numberOfGraphVertexes; ++i) {
0243     boost::add_vertex(m_graph);
0244   }
0245
0246   // set the vertices properties (use the module id as the global index into the graph)
0247   for (edm::ModuleDescription const *module : pathsAndConsumes.allModules()) {
0248     auto graphIndex = m_moduleIDToGraphIndex[module->id()];
0249
0250     m_graph.m_graph[graphIndex] = {
0251         module->moduleLabel(), module->moduleName(), module->id(), edmModuleTypeEnum(*module), false};
0252
0253     auto &attributes = boost::get(boost::get(boost::vertex_attribute, m_graph), graphIndex);
0254     attributes["label"] = module->moduleLabel();
0255     attributes["tooltip"] = module->moduleName();
0256     attributes["shape"] = shapes[static_cast<std::underlying_type_t<EDMModuleType>>(edmModuleTypeEnum(*module))];
0257     attributes["style"] = "filled";
0258     attributes["color"] = "black";
0259     attributes["fillcolor"] = highlighted(module->moduleLabel()) ? "green" : "lightgrey";
0260   }
0261
0262   // paths and endpaths
0263   auto const &paths = pathsAndConsumes.paths();
0264   auto const &endps = pathsAndConsumes.endPaths();
0265
0266   // add graph edges associated to module dependencies
0267   for (edm::ModuleDescription const *consumer : pathsAndConsumes.allModules()) {
0268     for (edm::ModuleDescription const *module : pathsAndConsumes.modulesWhoseProductsAreConsumedBy(consumer->id())) {
0269       edm::LogInfo("DependencyGraph") << "module " << consumer->moduleLabel() << " depends on module "
0270                                       << module->moduleLabel();
0271       auto edge_status =
0272           boost::add_edge(m_moduleIDToGraphIndex[consumer->id()], m_moduleIDToGraphIndex[module->id()], m_graph);
0273       // highlight the edge between highlighted nodes
0274       if (highlighted(module->moduleLabel()) and highlighted(consumer->moduleLabel())) {
0275         auto const &edge = edge_status.first;
0276         auto &attributes = boost::get(boost::get(boost::edge_attribute, m_graph), edge);
0277         attributes["color"] = "darkgreen";
0278       }
0279     }
0280   }
0281
0282   // save each Path and EndPath as a Graphviz subgraph
0283   for (unsigned int i = 0; i < paths.size(); ++i) {
0284     // create a subgraph to match the Path
0285     auto &graph = m_graph.create_subgraph();
0286
0287     // set the subgraph name property to the Path name
0288     boost::get_property(graph, boost::graph_name) = paths[i];
0289     boost::get_property(graph, boost::graph_graph_attribute)["label"] = "Path " + paths[i];
0290     boost::get_property(graph, boost::graph_graph_attribute)["labelloc"] = "bottom";
0291
0292     // add to the subgraph the node corresponding to the scheduled modules on the Path
0293     for (edm::ModuleDescription const *module : pathsAndConsumes.modulesOnPath(i)) {
0294       boost::add_vertex(m_moduleIDToGraphIndex[module->id()], graph);
0295     }
0296   }
0297   for (unsigned int i = 0; i < endps.size(); ++i) {
0298     // create a subgraph to match the EndPath
0299     auto &graph = m_graph.create_subgraph();
0300
0301     // set the subgraph name property to the EndPath name
0302     boost::get_property(graph, boost::graph_name) = endps[i];
0303     boost::get_property(graph, boost::graph_graph_attribute)["label"] = "EndPath " + endps[i];
0304     boost::get_property(graph, boost::graph_graph_attribute)["labelloc"] = "bottom";
0305
0306     // add to the subgraph the node corresponding to the scheduled modules on the EndPath
0307     for (edm::ModuleDescription const *module : pathsAndConsumes.modulesOnEndPath(i)) {
0308       boost::add_vertex(m_moduleIDToGraphIndex[module->id()], graph);
0309     }
0310   }
0311
0312   // optionally, add a dependency of the TriggerResults module on the PathStatusInserter modules
0313   const int size = boost::num_vertices(m_graph);
0314   int triggerResults = -1;
0315   bool highlightTriggerResults = false;
0316   for (int i = 0; i < size; ++i) {
0317     if (m_graph.m_graph[i].label == "TriggerResults") {
0318       triggerResults = i;
0319       highlightTriggerResults = highlighted("TriggerResults");
0320       break;
0321     }
0322   }
0323
0324   // mark the modules in the paths as scheduled, and add a soft dependency to reflect the order of modules along each path
0325   edm::ModuleDescription const *previous;
0326   for (unsigned int i = 0; i < paths.size(); ++i) {
0327     previous = nullptr;
0328     for (edm::ModuleDescription const *module : pathsAndConsumes.modulesOnPath(i)) {
0329       auto graphIndex = m_moduleIDToGraphIndex[module->id()];
0330       m_graph.m_graph[graphIndex].scheduled = true;
0331       auto &attributes = boost::get(boost::get(boost::vertex_attribute, m_graph), graphIndex);
0332       attributes["fillcolor"] = highlighted(module->moduleLabel()) ? "lightgreen" : "white";
0333       if (previous and m_showPathDependencies) {
0334         auto previousGraphIndex = m_moduleIDToGraphIndex[previous->id()];
0335         edm::LogInfo("DependencyGraph") << "module " << module->moduleLabel() << " follows module "
0336                                         << previous->moduleLabel() << " in Path " << paths[i];
0337         auto edge_status = boost::lookup_edge(graphIndex, previousGraphIndex, m_graph);
0338         bool found = edge_status.second;
0339         if (not found) {
0340           edge_status = boost::add_edge(graphIndex, previousGraphIndex, m_graph);
0341           auto const &edge = edge_status.first;
0342           auto &edgeAttributes = boost::get(boost::get(boost::edge_attribute, m_graph), edge);
0343           edgeAttributes["style"] = "dashed";
0344           // highlight the edge between highlighted nodes
0345           if (highlighted(module->moduleLabel()) and highlighted(previous->moduleLabel()))
0346             edgeAttributes["color"] = "darkgreen";
0347         }
0348       }
0349       previous = module;
0350     }
0351     // previous points to the last scheduled module on the path
0352     if (previous and m_showPathDependencies) {
0353       // look for the PathStatusInserter module corresponding to this path
0354       for (int j = 0; j < size; ++j) {
0355         if (m_graph.m_graph[j].label == paths[i]) {
0356           edm::LogInfo("DependencyGraph") << "module " << paths[i] << " implicitly follows module "
0357                                           << previous->moduleLabel() << " in Path " << paths[i];
0358           // add an edge from the PathStatusInserter module to the last module scheduled on the path
0359           auto edge_status = boost::add_edge(j, m_moduleIDToGraphIndex[previous->id()], m_graph);
0360           auto const &edge = edge_status.first;
0361           auto &edgeAttributes = boost::get(boost::get(boost::edge_attribute, m_graph), edge);
0362           edgeAttributes["style"] = "dashed";
0363           // highlight the edge between highlighted nodes
0364           bool highlightedPath = highlighted(paths[i]);
0365           if (highlightedPath and highlighted(previous->moduleLabel()))
0366             edgeAttributes["color"] = "darkgreen";
0367           if (triggerResults > 0) {
0368             // add an edge from the TriggerResults module to the PathStatusInserter module
0369             auto edge_status = boost::add_edge(triggerResults, j, m_graph);
0370             auto const &edge = edge_status.first;
0371             auto &edgeAttributes = boost::get(boost::get(boost::edge_attribute, m_graph), edge);
0372             edgeAttributes["style"] = "dashed";
0373             // highlight the edge between highlighted nodes
0374             if (highlightedPath and highlightTriggerResults)
0375               edgeAttributes["color"] = "darkgreen";
0376           }
0377           break;
0378         }
0379       }
0380     }
0381   }
0382
0383   // mark the modules in the endpaths as scheduled, and add a soft dependency to reflect the order of modules along each endpath
0384   for (unsigned int i = 0; i < endps.size(); ++i) {
0385     previous = nullptr;
0386     for (edm::ModuleDescription const *module : pathsAndConsumes.modulesOnEndPath(i)) {
0387       auto graphIndex = m_moduleIDToGraphIndex[module->id()];
0388       m_graph.m_graph[graphIndex].scheduled = true;
0389       auto &attributes = boost::get(boost::get(boost::vertex_attribute, m_graph), graphIndex);
0390       attributes["fillcolor"] = highlighted(module->moduleLabel()) ? "lightgreen" : "white";
0391       if (previous and m_showPathDependencies) {
0392         auto previousGraphIndex = m_moduleIDToGraphIndex[previous->id()];
0393         edm::LogInfo("DependencyGraph") << "module " << module->moduleLabel() << " follows module "
0394                                         << previous->moduleLabel() << " in EndPath " << i;
0395         auto edge_status = boost::lookup_edge(graphIndex, previousGraphIndex, m_graph);
0396         bool found = edge_status.second;
0397         if (not found) {
0398           edge_status = boost::add_edge(graphIndex, previousGraphIndex, m_graph);
0399           auto const &edge = edge_status.first;
0400           auto &edgeAttributes = boost::get(boost::get(boost::edge_attribute, m_graph), edge);
0401           edgeAttributes["style"] = "dashed";
0402           // highlight the edge between highlighted nodes
0403           if (highlighted(module->moduleLabel()) and highlighted(previous->moduleLabel()))
0404             edgeAttributes["color"] = "darkgreen";
0405         }
0406       }
0407       previous = module;
0408     }
0409   }
0410
0411   // draw the dependency graph
0412   std::ofstream out(m_filename);
0413   boost::write_graphviz(out, m_graph);
0414   out.close();
0415 }
0416
0417 // define as a framework servie
0418 #include "FWCore/ServiceRegistry/interface/ServiceMaker.h"
0419 DEFINE_FWK_SERVICE(DependencyGraph);