PrecedenceRulesGraph.h

Go to the documentation of this file.

/***********************************************************************************\
* (c) Copyright 1998-2019 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.                                             *
\***********************************************************************************/
#ifndef GAUDIHIVE_PRECEDENCERULESGRAPH_H
#define GAUDIHIVE_PRECEDENCERULESGRAPH_H

// std includes
#include <algorithm>
#include <memory>
#include <sstream>
#include <unordered_map>
#include <variant>
#include <vector>

#include <boost/filesystem.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphml.hpp>

// fwk includes
#include "../AlgsExecutionStates.h"
#include "../EventSlot.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 "Visitors/IGraphVisitor.h"
#include <Gaudi/Algorithm.h>

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, int rank, double runtime )
        : m_name( name ), m_index( index ), m_rank( rank ), m_runtime( runtime ) {}
    std::string m_name;
    int         m_index{-1};
    int         m_rank{-1};
    int         m_runtime{-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, bool inverted, bool allPass )
        : m_name( algo->name() )
        , m_nodeIndex( nodeIndex )
        , m_algoIndex( algoIndex )
        , m_algorithm( algo )
        , m_inverted( inverted )
        , m_allPass( allPass )
        , m_isIOBound( algo->isIOBound() ) {}

    std::string m_name{""};
    int         m_nodeIndex{-1};
    int         m_algoIndex{-1};
    int         m_rank{-1};
    Gaudi::Algorithm* m_algorithm{nullptr};

    bool m_inverted{false};
    bool m_allPass{false};
    bool m_isIOBound{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& props ) const { return props.m_inverted ? "Inverted" : "Non-inverted"; }

    std::string operator()( const DecisionHubProps& ) const { return ""; }

    std::string operator()( const DataProps& ) const { return ""; }
  };

  struct AllPass {
    std::string operator()( const AlgoProps& props ) const { return props.m_allPass ? "Optimist" : "Realist"; }

    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_conditionsEnabled( conditionsEnabled ) {
      SmartIF<IMessageSvc> msgSvc{svcLocator};
      MsgStream            log{msgSvc, "EntityState.Getter"};

      // Figure if we can discover the data object states
      m_whiteboard = svcLocator->service<IHiveWhiteBoard>( "EventDataSvc", false );
      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 ) {
      SmartIF<IMessageSvc> msgSvc{svcLocator};
      MsgStream            log{msgSvc, "StartTime.Getter"};

      // Figure if we can discover the algorithm timings
      m_timelineSvc = svcLocator->service<ITimelineSvc>( "TimelineSvc", false );
      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->getTimelineEvent( 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 ) {
      SmartIF<IMessageSvc> msgSvc{svcLocator};
      MsgStream            log{msgSvc, "EndTime.Getter"};

      // Figure if we can discover the algorithm timings
      m_timelineSvc = svcLocator->service<ITimelineSvc>( "TimelineSvc", false );
      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->getTimelineEvent( 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 ) {
      SmartIF<IMessageSvc> msgSvc{svcLocator};
      MsgStream            log{msgSvc, "Duration.Getter"};

      // Figure if we can discover the algorithm timings
      m_timelineSvc = svcLocator->service<ITimelineSvc>( "TimelineSvc", false );
      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();

        m_timelineSvc->getTimelineEvent( te );
        time = std::to_string( std::chrono::duration_cast<std::chrono::nanoseconds>( te.end - te.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_isIOBound ? "IO-bound" : "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, bool inverted, bool allPass )
        : ControlFlowNode( graph, nodeIndex, algoPtr->name() )
        , m_algorithm( algoPtr )
        , m_algoIndex( algoIndex )
        , m_algoName( algoPtr->name() )
        , m_inverted( inverted )
        , m_allPass( allPass )
        , m_isIOBound( algoPtr->isIOBound() ){};

    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; }
    const float& getRank() const { return m_rank; }

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

    void setIOBound( bool value ) { m_isIOBound = value; }
    bool isIOBound() const { return m_isIOBound; }

    bool isOptimist() const { return m_allPass; };
    bool isLiar() const { return m_inverted; };

    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;
    bool m_inverted;
    bool m_allPass;
    float m_rank = -1;
    bool m_isIOBound;

    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, bool inverted,
                                 bool allPass );
    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 {
      if ( slot.parentSlot ) {
        // Start at sub-slot entry point
        m_decisionNameToDecisionHubMap.at( slot.entryPoint )->printState( output, slot, recursionLevel );
      } else {
        // Start at the head node for whole-event slots
        m_headNode->printState( output, slot, recursionLevel );
      }
    }

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

    std::string dumpDataFlow() const;
    std::string dumpControlFlow() const;
    void dumpPrecRules( const boost::filesystem::path&, const EventSlot& slot );
    void dumpPrecTrace( const boost::filesystem::path& );
    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
#endif