PrecedenceRulesGraph.h

Go to the documentation of this file.

/***********************************************************************************\
* (c) Copyright 1998-2026 CERN for the benefit of the LHCb and ATLAS collaborations *
*                                                                                   *
* This software is distributed under the terms of the Apache version 2 licence,     *
* copied verbatim in the file "LICENSE".                                            *
*                                                                                   *
* In applying this licence, CERN does not waive the privileges and immunities       *
* granted to it by virtue of its status as an Intergovernmental Organization        *
* or submit itself to any jurisdiction.                                             *
\***********************************************************************************/
#pragma once
 
// Local includes
#include "../AlgsExecutionStates.h"
#include "../EventSlot.h"
#include "Visitors/IGraphVisitor.h"
 
// Framework includes
#include <Gaudi/Algorithm.h>
#include <GaudiKernel/CommonMessaging.h>
#include <GaudiKernel/DataObject.h>
#include <GaudiKernel/ICondSvc.h>
#include <GaudiKernel/IHiveWhiteBoard.h>
#include <GaudiKernel/ITimelineSvc.h>
#include <GaudiKernel/TaggedBool.h>
#include <GaudiKernel/TimelineEvent.h>
 
// STL includes
#include <algorithm>
#include <filesystem>
#include <memory>
#include <sstream>
#include <unordered_map>
#include <variant>
#include <vector>
 
// Boost includes
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphml.hpp>
 
namespace concurrency {
  using Concurrent     = Gaudi::tagged_bool<class Concurrent_tag>;
  using PromptDecision = Gaudi::tagged_bool<class PromptDecision_tag>;
  using ModeOr         = Gaudi::tagged_bool<class ModeOr_tag>;
  using AllPass        = Gaudi::tagged_bool<class AllPass_tag>;
  using Inverted       = Gaudi::tagged_bool<class Inverted_tag>;
} // namespace concurrency
 
namespace precedence {
 
  // Precedence trace utilities ==============================================
  struct AlgoTraceProps {
    AlgoTraceProps() {}
    AlgoTraceProps( const std::string& name, int index = -1, int rank = -1, long int runtime = -1,
                    long long int start = -1 )
        : m_name( name ), m_index( index ), m_rank( rank ), m_runtime( runtime ), m_start( start ) {}
    std::string   m_name;
    int           m_index{ -1 };
    int           m_rank{ -1 };
    long int      m_runtime{ -1 }; // us
    long long int m_start{ -1 };   // ns
    int           m_eccentricity{ -1 };
  };
 
  using PrecTrace       = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, AlgoTraceProps>;
  using AlgoTraceVertex = boost::graph_traits<PrecTrace>::vertex_descriptor;
 
  // Precedence rules utilities ==============================================
  struct AlgoProps {
    AlgoProps() {}
    AlgoProps( Gaudi::Algorithm* algo, uint nodeIndex, uint algoIndex )
        : m_name( algo->name() )
        , m_nodeIndex( nodeIndex )
        , m_algoIndex( algoIndex )
        , m_algorithm( algo )
        , m_isAsynchronous( algo->isAsynchronous() ) {}
 
    std::string m_name{ "" };
    int         m_nodeIndex{ -1 };
    int         m_algoIndex{ -1 };
    int         m_rank{ -1 };
    Gaudi::Algorithm* m_algorithm{ nullptr };
    bool m_isAsynchronous{ false };
  };
 
  struct DecisionHubProps {
    DecisionHubProps( const std::string& name, uint nodeIndex, concurrency::Concurrent modeConcurrent,
                      concurrency::PromptDecision modePromptDecision, concurrency::ModeOr modeOR,
                      concurrency::AllPass allPass, concurrency::Inverted isInverted )
        : m_name( name )
        , m_nodeIndex( nodeIndex )
        , m_modeConcurrent( modeConcurrent )
        , m_modePromptDecision( modePromptDecision )
        , m_inverted( isInverted )
        , m_modeOR( modeOR )
        , m_allPass( allPass ) {}
 
    std::string m_name;
    uint        m_nodeIndex;

    bool m_modeConcurrent;
    bool m_modePromptDecision;
    bool m_inverted{ false };
    bool m_modeOR;
    bool m_allPass;
  };
 
  struct DataProps {
    DataProps( const DataObjID& id ) : m_id( id ) {}
 
    DataObjID m_id;
  };
 
  struct CondDataProps : DataProps {
    CondDataProps( const DataObjID& id ) : DataProps( id ) {}
  };
 
  // Vertex unpacking ========================================================
 
  struct VertexName {
    std::string operator()( const AlgoProps& props ) const { return props.m_name; }
 
    std::string operator()( const DecisionHubProps& props ) const { return props.m_name; }
 
    std::string operator()( const DataProps& props ) const { return props.m_id.fullKey(); }
  };
 
  struct GroupMode {
    std::string operator()( const AlgoProps& ) const { return ""; }
 
    std::string operator()( const DecisionHubProps& props ) const {
      return props.m_modeConcurrent ? "Concurrent" : "Sequential";
    }
 
    std::string operator()( const DataProps& ) const { return ""; }
  };
 
  struct GroupLogic {
    std::string operator()( const AlgoProps& ) const { return ""; }
 
    std::string operator()( const DecisionHubProps& props ) const { return props.m_modeOR ? "OR" : "AND"; }
 
    std::string operator()( const DataProps& ) const { return ""; }
  };
 
  struct GroupExit {
    std::string operator()( const AlgoProps& ) const { return ""; }
 
    std::string operator()( const DecisionHubProps& props ) const {
      return props.m_modePromptDecision ? "Early" : "Late";
    }
 
    std::string operator()( const DataProps& ) const { return ""; }
  };
 
  struct DecisionNegation {
    std::string operator()( const AlgoProps& ) const { return ""; }
 
    std::string operator()( const DecisionHubProps& props ) const {
      return props.m_inverted ? "Inverted" : "Non-inverted";
    }
 
    std::string operator()( const DataProps& ) const { return ""; }
  };
 
  struct AllPass {
    std::string operator()( const AlgoProps& ) const { return ""; }
 
    std::string operator()( const DecisionHubProps& props ) const { return props.m_allPass ? "Optimist" : "Realist"; }
 
    std::string operator()( const DataProps& ) const { return ""; }
  };
 
  struct CFDecision {
    CFDecision( const EventSlot& slot ) : m_slot( slot ) {}
 
    std::string operator()( const AlgoProps& props ) const {
      return std::to_string( m_slot.controlFlowState.at( props.m_nodeIndex ) );
    }
 
    std::string operator()( const DecisionHubProps& props ) const {
      return std::to_string( m_slot.controlFlowState.at( props.m_nodeIndex ) );
    }
 
    std::string operator()( const DataProps& ) const { return ""; }
 
    const EventSlot& m_slot;
  };
 
  struct EntityState {
    EntityState( const EventSlot& slot, SmartIF<ISvcLocator>& svcLocator, bool conditionsEnabled )
        : m_slot( slot )
        , m_whiteboard( svcLocator->service<IHiveWhiteBoard>( "EventDataSvc", false ) )
        , m_conditionsEnabled( conditionsEnabled ) {
      SmartIF<IMessageSvc> msgSvc{ svcLocator };
      MsgStream            log{ msgSvc, "EntityState.Getter" };
 
      // Figure if we can discover the data object states
      if ( !m_whiteboard.isValid() ) {
        log << MSG::WARNING << "Failed to locate EventDataSvc: no way to add DO "
            << "states to the TTT dump " << endmsg;
      }
 
      if ( m_conditionsEnabled ) {
        // Figure if we can discover Condition data object states
        m_condSvc = svcLocator->service<ICondSvc>( "CondSvc", false );
        if ( !m_condSvc.isValid() )
          log << MSG::WARNING << "Failed to locate CondSvc: no way to add Condition DO "
              << "states to the TTT dump " << endmsg;
      }
 
      if ( !m_slot.eventContext->valid() )
        log << MSG::WARNING << "Event context is invalid: no way to add DO states"
            << " in the TTT dump" << endmsg;
    }
 
    // Returns algorithm's FSM state
    std::string operator()( const AlgoProps& props ) const {
      std::ostringstream oss;
      oss << m_slot.algsStates[props.m_algoIndex];
      return oss.str();
    }
 
    std::string operator()( const DecisionHubProps& ) const { return ""; }
 
    std::string operator()( const DataProps& props ) const {
      std::string state;
 
      if ( m_whiteboard.isValid() && m_slot.eventContext->valid() )
        if ( m_whiteboard->selectStore( m_slot.eventContext->slot() ).isSuccess() )
          state = m_whiteboard->exists( props.m_id ) ? "Produced" : "Missing";
 
      return state;
    }
 
    std::string operator()( const CondDataProps& props ) const {
      std::string state;
 
      if ( m_condSvc.isValid() && m_slot.eventContext->valid() )
        state = m_condSvc->isValidID( *( m_slot.eventContext ), props.m_id ) ? "Produced" : "Missing";
 
      return state;
    }
 
    const EventSlot& m_slot;
 
    SmartIF<IHiveWhiteBoard> m_whiteboard;
    SmartIF<ICondSvc>        m_condSvc;
    bool                     m_conditionsEnabled{ false };
  };
 
  struct StartTime {
    StartTime( const EventSlot& slot, SmartIF<ISvcLocator>& svcLocator )
        : m_slot( slot ), m_timelineSvc( svcLocator->service<ITimelineSvc>( "TimelineSvc", false ) ) {
      SmartIF<IMessageSvc> msgSvc{ svcLocator };
      MsgStream            log{ msgSvc, "StartTime.Getter" };
 
      // Figure if we can discover the algorithm timings
      if ( !m_timelineSvc.isValid() ) {
        log << MSG::WARNING << "Failed to locate the TimelineSvc: no way to "
            << "add algorithm start time to the TTT dumps" << endmsg;
      }
    }
 
    std::string operator()( const AlgoProps& props ) const {
 
      std::string startTime;
 
      if ( m_timelineSvc.isValid() ) {
 
        TimelineEvent te{};
        te.algorithm = props.m_name;
        te.slot      = m_slot.eventContext->slot();
        te.event     = m_slot.eventContext->evt();
 
        m_timelineSvc->getFirstMatching( te );
        startTime = std::to_string(
            std::chrono::duration_cast<std::chrono::nanoseconds>( te.start.time_since_epoch() ).count() );
      }
 
      return startTime;
    }
 
    std::string operator()( const DecisionHubProps& ) const { return ""; }
 
    std::string operator()( const DataProps& ) const { return ""; }
 
    const EventSlot&      m_slot;
    SmartIF<ITimelineSvc> m_timelineSvc;
  };
 
  struct EndTime {
    EndTime( const EventSlot& slot, SmartIF<ISvcLocator>& svcLocator )
        : m_slot( slot ), m_timelineSvc( svcLocator->service<ITimelineSvc>( "TimelineSvc", false ) ) {
      SmartIF<IMessageSvc> msgSvc{ svcLocator };
      MsgStream            log{ msgSvc, "EndTime.Getter" };
 
      // Figure if we can discover the algorithm timings
      if ( !m_timelineSvc.isValid() )
        log << MSG::WARNING << "Failed to locate the TimelineSvc: no way to add "
            << "algorithm completion time to the TTT dumps" << endmsg;
    }
 
    std::string operator()( const AlgoProps& props ) const {
 
      std::string endTime;
 
      if ( m_timelineSvc.isValid() ) {
 
        TimelineEvent te{};
        te.algorithm = props.m_name;
        te.slot      = m_slot.eventContext->slot();
        te.event     = m_slot.eventContext->evt();
 
        m_timelineSvc->getLastMatching( te );
        endTime =
            std::to_string( std::chrono::duration_cast<std::chrono::nanoseconds>( te.end.time_since_epoch() ).count() );
      }
 
      return endTime;
    }
 
    std::string operator()( const DecisionHubProps& ) const { return ""; }
 
    std::string operator()( const DataProps& ) const { return ""; }
 
    const EventSlot&      m_slot;
    SmartIF<ITimelineSvc> m_timelineSvc;
  };
 
  struct Duration {
    Duration( const EventSlot& slot, SmartIF<ISvcLocator>& svcLocator )
        : m_slot( slot ), m_timelineSvc( svcLocator->service<ITimelineSvc>( "TimelineSvc", false ) ) {
      SmartIF<IMessageSvc> msgSvc{ svcLocator };
      MsgStream            log{ msgSvc, "Duration.Getter" };
 
      // Figure if we can discover the algorithm timings
      if ( !m_timelineSvc.isValid() )
        log << MSG::WARNING << "Failed to locate the TimelineSvc: no way to add "
            << "algorithm's runtimes to the TTT dumps" << endmsg;
    }
 
    std::string operator()( const AlgoProps& props ) const {
 
      std::string time;
 
      if ( m_timelineSvc.isValid() ) {
 
        TimelineEvent te;
        te.algorithm = props.m_name;
        te.slot      = m_slot.eventContext->slot();
        te.event     = m_slot.eventContext->evt();
 
        // Calculate duration that is the difference between stop and and start for given algorithm. Asynchronous
        // algorithms will have multiple TimelineEvents, so the start should be taken from the first and the end from
        // the last.
        m_timelineSvc->getFirstMatching( te );
        auto start = te.start;
        m_timelineSvc->getLastMatching( te );
        auto end = te.end;
        time     = std::to_string( std::chrono::duration_cast<std::chrono::nanoseconds>( end - start ).count() );
      }
 
      return time;
    }
 
    std::string operator()( const DecisionHubProps& ) const { return ""; }
 
    std::string operator()( const DataProps& ) const { return ""; }
 
    const EventSlot&      m_slot;
    SmartIF<ITimelineSvc> m_timelineSvc;
  };
 
  struct Operations {
    std::string operator()( const AlgoProps& props ) const {
      return props.m_isAsynchronous ? "Asynchronous" : "CPU-bound";
    }
 
    std::string operator()( const DecisionHubProps& ) const { return ""; }
 
    std::string operator()( const DataProps& ) const { return ""; }
  };
 
  static inline std::ostream& operator<<( std::ostream& os, const AlgoProps& ) { return os << "Algorithm"; }
  static inline std::ostream& operator<<( std::ostream& os, const DecisionHubProps& ) { return os << "DecisionHub"; }
  static inline std::ostream& operator<<( std::ostream& os, const DataProps& ) { return os << "Data"; }
  static inline std::ostream& operator<<( std::ostream& os, const CondDataProps& ) { return os << "ConditionData"; }
 
  //=========================================================================
 
  using VariantVertexProps = std::variant<AlgoProps, DecisionHubProps, DataProps, CondDataProps>;
  using PRGraph            = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VariantVertexProps>;
  using PRVertexDesc       = boost::graph_traits<PRGraph>::vertex_descriptor;
 
} // namespace precedence
 
struct Cause final {
  enum class source { Root, Task };
 
  source      m_source;
  std::string m_sourceName;
};
 
namespace concurrency {
  class PrecedenceRulesGraph;
 
  using precedence::AlgoProps;
  using precedence::CondDataProps;
  using precedence::DataProps;
  using precedence::DecisionHubProps;
  using precedence::PRVertexDesc;
  using precedence::VariantVertexProps;
 
  // ==========================================================================
  class ControlFlowNode {
  public:
    ControlFlowNode( PrecedenceRulesGraph& graph, unsigned int nodeIndex, const std::string& name )
        : m_graph( &graph ), m_nodeIndex( nodeIndex ), m_nodeName( name ) {}

    virtual ~ControlFlowNode() = default;

    virtual bool accept( IGraphVisitor& visitor ) = 0;
    virtual void printState( std::stringstream& output, EventSlot& slot, const unsigned int& recursionLevel ) const = 0;
    const unsigned int& getNodeIndex() const { return m_nodeIndex; }
    const std::string& name() const { return m_nodeName; }
 
  public:
    PrecedenceRulesGraph* m_graph;
 
  protected:
    unsigned int m_nodeIndex;
    std::string  m_nodeName;
  };
 
  class DecisionNode final : public ControlFlowNode {
  public:
    DecisionNode( PrecedenceRulesGraph& graph, unsigned int nodeIndex, const std::string& name,
                  Concurrent modeConcurrent, PromptDecision modePromptDecision, ModeOr modeOR, AllPass allPass,
                  Inverted isInverted )
        : ControlFlowNode( graph, nodeIndex, name )
        , m_modeConcurrent( modeConcurrent )
        , m_modePromptDecision( modePromptDecision )
        , m_modeOR( modeOR )
        , m_allPass( allPass )
        , m_inverted( isInverted ) {}

    bool accept( IGraphVisitor& visitor ) override;
    void addParentNode( DecisionNode* node );
    void addDaughterNode( ControlFlowNode* node );
    const std::vector<ControlFlowNode*>& getDaughters() const { return m_children; }
    void printState( std::stringstream& output, EventSlot& slot, const unsigned int& recursionLevel ) const override;
 
  public:
    bool m_modeConcurrent;
    bool m_modePromptDecision;
    bool m_modeOR;
    bool m_allPass;
    bool m_inverted{ false };
    std::vector<ControlFlowNode*> m_children;
    std::vector<DecisionNode*> m_parents;
  };
 
  // ==========================================================================
  class DataNode;
 
  class AlgorithmNode final : public ControlFlowNode {
  public:
    AlgorithmNode( PrecedenceRulesGraph& graph, Gaudi::Algorithm* algoPtr, unsigned int nodeIndex,
                   unsigned int algoIndex )
        : ControlFlowNode( graph, nodeIndex, algoPtr->name() )
        , m_algorithm( algoPtr )
        , m_algoIndex( algoIndex )
        , m_algoName( algoPtr->name() )
        , m_isAsynchronous( algoPtr->isAsynchronous() ) {}

    bool accept( IGraphVisitor& visitor ) override;

    void addParentNode( DecisionNode* node );
    const std::vector<DecisionNode*>& getParentDecisionHubs() const { return m_parents; }

    void addOutputDataNode( DataNode* node );
    void addInputDataNode( DataNode* node );
    const std::vector<DataNode*>& getOutputDataNodes() const { return m_outputs; }
    const std::vector<DataNode*>& getInputDataNodes() const { return m_inputs; }

    void setRank( float rank ) { m_rank = rank; }
    float getRank() const { return m_rank; }

    Gaudi::Algorithm* getAlgorithm() const { return m_algorithm; }
    unsigned int getAlgoIndex() const { return m_algoIndex; }

    void setAsynchronous( bool value ) { m_isAsynchronous = value; }
    bool isAsynchronous() const { return m_isAsynchronous; }

    void printState( std::stringstream& output, EventSlot& slot, const unsigned int& recursionLevel ) const override;
 
  public:
    std::vector<DecisionNode*> m_parents;
 
  private:
    Gaudi::Algorithm* m_algorithm;
    unsigned int m_algoIndex;
    std::string m_algoName;
    float m_rank = -1;
    bool m_isAsynchronous;

    std::vector<DataNode*> m_outputs;
    std::vector<DataNode*> m_inputs;
  };
 
  // ==========================================================================
  class DataNode {
  public:
    DataNode( PrecedenceRulesGraph& graph, const DataObjID& path ) : m_graph( &graph ), m_data_object_path( path ) {}

    virtual ~DataNode() = default;
 
    const DataObjID& name() const { return m_data_object_path; }

    virtual bool accept( IGraphVisitor& visitor ) {
      return visitor.visitEnter( *this ) ? visitor.visit( *this ) : true;
    }

    void addProducerNode( AlgorithmNode* node ) {
      if ( std::find( m_producers.begin(), m_producers.end(), node ) == m_producers.end() )
        m_producers.push_back( node );
    }

    void addConsumerNode( AlgorithmNode* node ) {
      if ( std::find( m_consumers.begin(), m_consumers.end(), node ) == m_consumers.end() )
        m_consumers.push_back( node );
    }

    const std::vector<AlgorithmNode*>& getProducers() const { return m_producers; }
    const std::vector<AlgorithmNode*>& getConsumers() const { return m_consumers; }
 
  public:
    PrecedenceRulesGraph* m_graph;
 
  private:
    DataObjID                   m_data_object_path;
    std::vector<AlgorithmNode*> m_producers;
    std::vector<AlgorithmNode*> m_consumers;
  };
 
  class ConditionNode final : public DataNode {
  public:
    ConditionNode( PrecedenceRulesGraph& graph, const DataObjID& path, SmartIF<ICondSvc> condSvc )
        : DataNode( graph, path ), m_condSvc( condSvc ) {}

    bool accept( IGraphVisitor& visitor ) override {
      return visitor.visitEnter( *this ) ? visitor.visit( *this ) : true;
    }
 
  public:
    // Service for Conditions handling
    SmartIF<ICondSvc> m_condSvc;
  };
 
  // ==========================================================================
 
  struct IPrecedenceRulesGraph {
    virtual ~IPrecedenceRulesGraph() = default;
  };
 
  template <typename T>
  struct CompareNodes {
    bool operator()( const T& a, const T& b ) const { return a->name() < b->name(); }
  };
 
  class PrecedenceRulesGraph : public CommonMessaging<IPrecedenceRulesGraph> {
  public:
    PrecedenceRulesGraph( const std::string& name, SmartIF<ISvcLocator> svc ) : m_svcLocator( svc ), m_name( name ) {
      // make sure that CommonMessaging is initialized
      setUpMessaging();
    }

    StatusCode initialize();

    void accept( IGraphVisitor& visitor ) const;

    StatusCode addDataNode( const DataObjID& dataPath );
    DataNode* getDataNode( const DataObjID& dataPath ) const { return m_dataPathToDataNodeMap.at( dataPath ).get(); }
    void registerIODataObjects( const Gaudi::Algorithm* algo );
    StatusCode buildDataDependenciesRealm();

    void addHeadNode( const std::string& headName, concurrency::Concurrent, concurrency::PromptDecision,
                      concurrency::ModeOr, concurrency::AllPass, concurrency::Inverted );
    DecisionNode* getHeadNode() const { return m_headNode; }
    StatusCode addAlgorithmNode( Gaudi::Algorithm* daughterAlgo, const std::string& parentName );
    AlgorithmNode* getAlgorithmNode( const std::string& algoName ) const {
      return m_algoNameToAlgoNodeMap.at( algoName ).get();
    }

    StatusCode addDecisionHubNode( Gaudi::Algorithm* daughterAlgo, const std::string& parentName,
                                   concurrency::Concurrent, concurrency::PromptDecision, concurrency::ModeOr,
                                   concurrency::AllPass, concurrency::Inverted );
    unsigned int getControlFlowNodeCounter() const { return m_nodeCounter; }

    void rankAlgorithms( IGraphVisitor& ranker ) const;

    const std::string& name() const override { return m_name; }
    SmartIF<ISvcLocator>& serviceLocator() const override { return m_svcLocator; }
    void printState( std::stringstream& output, EventSlot& slot, const unsigned int& recursionLevel ) const;

    void         enableAnalysis() { m_enableAnalysis = true; }
    PRVertexDesc node( const std::string& ) const;

    std::string dumpDataFlow() const;
    std::string dumpControlFlow() const;
    void dumpPrecRules( const std::filesystem::path&, const EventSlot& slot );
    void dumpPrecTrace( const std::filesystem::path&, const EventSlot& slot );
    void addEdgeToPrecTrace( const AlgorithmNode* u, const AlgorithmNode* v );
    void dumpControlFlow( std::ostringstream&, ControlFlowNode*, const int& ) const;
 
  private:
    DecisionNode* m_headNode = nullptr;
    std::unordered_map<std::string, std::unique_ptr<AlgorithmNode>> m_algoNameToAlgoNodeMap;
    std::unordered_map<std::string, std::unique_ptr<DecisionNode>> m_decisionNameToDecisionHubMap;
    std::unordered_map<DataObjID, std::unique_ptr<DataNode>, DataObjID_Hasher> m_dataPathToDataNodeMap;
    std::unordered_map<std::string, DataObjIDColl> m_algoNameToAlgoInputsMap;
    std::unordered_map<std::string, DataObjIDColl> m_algoNameToAlgoOutputsMap;

    unsigned int m_nodeCounter = 0;
    unsigned int m_algoCounter = 0;

    mutable SmartIF<ISvcLocator> m_svcLocator;
    const std::string            m_name;

    precedence::PrecTrace                              m_precTrace;
    std::map<std::string, precedence::AlgoTraceVertex> m_prec_trace_map;
    bool                                               m_enableAnalysis{ false };
    precedence::PRGraph m_PRGraph;

    bool m_conditionsRealmEnabled{ false };
  };
 
} // namespace concurrency