JANA/Utils/JCallGraphRecorder.cc

0001 //
0002 // Created by Nathan Brei on 10/25/21.
0003 //
0004
0005 #include "JCallGraphRecorder.h"
0006
0007 #include <JANA/JLogger.h>
0008
0009 #include <algorithm>
0010 #include <map>
0011 #include <queue>
0012 #include <sstream>
0013
0014
0015 void JCallGraphRecorder::Reset() {
0016     m_call_graph.clear();
0017     m_call_stack.clear();
0018     m_error_call_stack.clear();
0019 }
0020
0021 void JCallGraphRecorder::PrintErrorCallStack() const {
0022
0023     // Create a list of the call strings while finding the longest one
0024     std::vector<std::string> routines;
0025     unsigned int max_length = 0;
0026     for(unsigned int i=0; i<m_error_call_stack.size(); i++){
0027         std::string routine = m_error_call_stack[i].factory_name;
0028         if(m_error_call_stack[i].tag.length()){
0029             routine = routine + ":" + m_error_call_stack[i].tag;
0030         }
0031         if(routine.size()>max_length) max_length = routine.size();
0032         routines.push_back(routine);
0033     }
0034
0035     std::stringstream sstr;
0036     sstr<<" Factory Call Stack"<<std::endl;
0037     sstr<<"============================"<<std::endl;
0038     for(unsigned int i=0; i<m_error_call_stack.size(); i++){
0039         std::string routine = routines[i];
0040         sstr<<" "<<routine<<std::string(max_length+2 - routine.size(),' ');
0041         if(m_error_call_stack[i].filename){
0042             sstr<<"--  "<<" line:"<<m_error_call_stack[i].line<<"  "<<m_error_call_stack[i].filename;
0043         }
0044         sstr<<std::endl;
0045     }
0046     sstr<<"----------------------------"<<std::endl;
0047
0048     jout<<sstr.str();
0049
0050 }
0051
0052 std::vector<std::pair<std::string, std::string>> JCallGraphRecorder::TopologicalSort() const {
0053     // The JCallGraphNodes are _probably_ already in topological order, but we cannot assume
0054     // that because the user is allowed to add whatever JCallGraphNodes they wish.
0055     // This uses Kahn's algorithm because it is simple. Furthermore, it uses string comparisons instead of int
0056     // comparisons, which are slow. We can make this faster if we find it is necessary.
0057
0058     using FacName = std::pair<std::string, std::string>;
0059     struct FacEdges {
0060         std::vector<FacName> incoming;
0061         std::vector<FacName> outgoing;
0062     };
0063
0064     // Build adjacency matrix
0065     std::map<FacName, FacEdges> adjacency;
0066     for (const JCallGraphNode& node : m_call_graph) {
0067
0068         adjacency[{node.caller_name, node.caller_tag}].incoming.emplace_back(node.callee_name, node.callee_tag);
0069         adjacency[{node.callee_name, node.callee_tag}].outgoing.emplace_back(node.caller_name, node.caller_tag);
0070     }
0071
0072     std::vector<FacName> sorted;
0073     std::queue<FacName> ready;
0074
0075     // Populate frontier of "ready" elements with no incoming edges
0076     for (auto& p : adjacency) {
0077         if (p.second.incoming.empty()) ready.push(p.first);
0078     }
0079
0080     // Process each ready element
0081     while (!ready.empty()) {
0082         auto n = ready.front();
0083         ready.pop();
0084         sorted.push_back(n);
0085         for (auto& m : adjacency[n].outgoing) {
0086             auto& incoming = adjacency[m].incoming;
0087             incoming.erase(std::remove(incoming.begin(), incoming.end(), n), incoming.end());
0088             if (incoming.empty()) {
0089                 ready.push(m);
0090             }
0091         }
0092     }
0093     return sorted;
0094 }