PrecedenceRulesGraph.h

Go to the documentation of this file.

#ifndef GAUDIHIVE_PRECEDENCERULESGRAPH_H
#define GAUDIHIVE_PRECEDENCERULESGRAPH_H

// std includes
#include <algorithm>
#include <chrono>
#include <sstream>
#include <unordered_map>
#include <vector>

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

// fwk includes
#include "AlgsExecutionStates.h"
#include "EventSlot.h"
#include "GaudiKernel/Algorithm.h"
#include "GaudiKernel/CommonMessaging.h"
#include "GaudiKernel/ICondSvc.h"
#include "GaudiKernel/ITimelineSvc.h"
#include "IGraphVisitor.h"

namespace precedence
{
  using boost::static_visitor;

  // 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( 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};
    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, bool modeConcurrent, bool modePromptDecision,
                      bool modeOR, bool allPass )
        : m_name( name )
        , m_nodeIndex( nodeIndex )
        , m_modeConcurrent( modeConcurrent )
        , m_modePromptDecision( modePromptDecision )
        , m_modeOR( modeOR )
        , m_allPass( allPass )
    {
    }

    std::string m_name;
    uint m_nodeIndex;

    bool m_modeConcurrent;
    bool m_modePromptDecision;
    bool m_modeOR;
    bool m_allPass;
  };

  struct DataProps {
    DataProps( const DataObjID& id ) : m_id( id ) {}

    DataObjID m_id;
  };

  // Vertex unpacking ========================================================

  struct VertexName : static_visitor<std::string> {
    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 : static_visitor<std::string> {
    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 : static_visitor<std::string> {
    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 : static_visitor<std::string> {
    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 : static_visitor<std::string> {
    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 : static_visitor<std::string> {
    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 : static_visitor<std::string> {
    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 ""; }

    EventSlot m_slot;
  };

  struct FSMState : static_visitor<std::string> {
    FSMState( const EventSlot& slot ) : m_slot( slot ) {}

    std::string operator()( const AlgoProps& props ) const
    {
      using State = AlgsExecutionStates::State;
      State state = m_slot.algsStates[props.m_algoIndex];
      switch ( state ) {
      case State::INITIAL:
        return "INITIAL";
      case State::CONTROLREADY:
        return "CONTROLREADY";
      case State::DATAREADY:
        return "DATAREADY";
      case State::EVTACCEPTED:
        return "EVTACCEPTED";
      case State::EVTREJECTED:
        return "EVTREJECTED";
      case State::ERROR:
        return "ERROR";
      default:
        return "UKNOWN";
      }
    }

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

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

    EventSlot m_slot;
  };

  struct StartTime : static_visitor<std::string> {
    StartTime( SmartIF<ITimelineSvc> timelineSvc ) : m_timelineSvc( timelineSvc ) {}

    std::string operator()( const AlgoProps& props ) const
    {

      std::string startTime = "UKNOWN";

      if ( m_timelineSvc.isValid() ) {

        TimelineEvent te{};
        te.algorithm = props.m_name;
        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 ""; }

    SmartIF<ITimelineSvc> m_timelineSvc;
  };

  struct EndTime : static_visitor<std::string> {
    EndTime( SmartIF<ITimelineSvc> timelineSvc ) : m_timelineSvc( timelineSvc ) {}

    std::string operator()( const AlgoProps& props ) const
    {

      std::string endTime = "UKNOWN";

      if ( m_timelineSvc.isValid() ) {

        TimelineEvent te{};
        te.algorithm = props.m_name;
        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 ""; }

    SmartIF<ITimelineSvc> m_timelineSvc;
  };

  struct Duration : static_visitor<std::string> {
    Duration( SmartIF<ITimelineSvc> timelineSvc ) : m_timelineSvc( timelineSvc ) {}

    std::string operator()( const AlgoProps& props ) const
    {

      std::string time = "UKNOWN";

      if ( m_timelineSvc.isValid() ) {

        TimelineEvent te;
        te.algorithm = props.m_name;
        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 ""; }

    SmartIF<ITimelineSvc> m_timelineSvc;
  };

  struct Operations : static_visitor<std::string> {
    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 << "Algo"; }
  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"; }

  //=========================================================================

  using VariantVertexProps = boost::variant<AlgoProps, DecisionHubProps, DataProps>;
  using PRGraph            = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VariantVertexProps>;
  using PRVertexDesc       = boost::graph_traits<PRGraph>::vertex_descriptor;

} // namespace prules

struct Cause {
  enum class source { Root, Task };

  source m_source;
  std::string m_sourceName;
};

namespace concurrency
{

  using State = AlgsExecutionStates::State;
  class PrecedenceRulesGraph;

  using precedence::PRVertexDesc;
  using precedence::AlgoProps;
  using precedence::DecisionHubProps;
  using precedence::DataProps;
  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() {}

    virtual bool accept( IGraphVisitor& visitor ) = 0;
    virtual void printState( std::stringstream& output, AlgsExecutionStates& states,
                             const std::vector<int>& node_decisions, const unsigned int& recursionLevel ) const = 0;
    const unsigned int& getNodeIndex() const { return m_nodeIndex; }
    const std::string& getNodeName() const { return m_nodeName; }

  public:
    PrecedenceRulesGraph* m_graph;

  protected:
    std::string stateToString( const int& stateId ) const;
    unsigned int m_nodeIndex;
    std::string m_nodeName;
  };

  class DecisionNode : public ControlFlowNode
  {
  public:
    DecisionNode( PrecedenceRulesGraph& graph, unsigned int nodeIndex, const std::string& name, bool modeConcurrent,
                  bool modePromptDecision, bool modeOR, bool allPass )
        : ControlFlowNode( graph, nodeIndex, name )
        , m_modeConcurrent( modeConcurrent )
        , m_modePromptDecision( modePromptDecision )
        , m_modeOR( modeOR )
        , m_allPass( allPass )
        , m_children()
    {
    }

    ~DecisionNode() override;

    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, AlgsExecutionStates& states, const std::vector<int>& node_decisions,
                     const unsigned int& recursionLevel ) const override;

  public:
    bool m_modeConcurrent;
    bool m_modePromptDecision;
    bool m_modeOR;
    bool m_allPass;
    std::vector<ControlFlowNode*> m_children;
    std::vector<DecisionNode*> m_parents;
  };

  // ==========================================================================
  class DataNode;

  class AlgorithmNode : public ControlFlowNode
  {
  public:
    AlgorithmNode( PrecedenceRulesGraph& graph, 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_rank( -1 )
        , m_isIOBound( algoPtr->isIOBound() ){};
    ~AlgorithmNode();

    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; }

    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, AlgsExecutionStates& states, const std::vector<int>& node_decisions,
                     const unsigned int& recursionLevel ) const override;

  public:
    std::vector<DecisionNode*> m_parents;

  private:
    Algorithm* m_algorithm;
    unsigned int m_algoIndex;
    std::string m_algoName;
    bool m_inverted;
    bool m_allPass;
    float m_rank;
    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 ) {}

    const DataObjID& getPath() { return m_data_object_path; }

    bool accept( IGraphVisitor& visitor )
    {
      if ( visitor.visitEnter( *this ) ) return visitor.visit( *this );
      return 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 : public DataNode
  {
  public:
    ConditionNode( PrecedenceRulesGraph& graph, const DataObjID& path, SmartIF<ICondSvc> condSvc )
        : DataNode( graph, path ), m_condSvc( condSvc )
    {
    }

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

  public:
    // Service for Conditions handling
    SmartIF<ICondSvc> m_condSvc;
  };

  // ==========================================================================
  using AlgoNodesMap    = std::unordered_map<std::string, AlgorithmNode*>;
  using DecisionHubsMap = std::unordered_map<std::string, DecisionNode*>;
  using DataNodesMap    = std::unordered_map<DataObjID, DataNode*, DataObjID_Hasher>;

  using AlgoInputsMap  = std::unordered_map<std::string, DataObjIDColl>;
  using AlgoOutputsMap = std::unordered_map<std::string, DataObjIDColl>;

  struct IPrecedenceRulesGraph {
    virtual ~IPrecedenceRulesGraph() = default;
  };

  class PrecedenceRulesGraph : public CommonMessaging<IPrecedenceRulesGraph>
  {
  public:
    PrecedenceRulesGraph( const std::string& name, SmartIF<ISvcLocator> svc )
        : m_headNode( 0 )
        , m_nodeCounter( 0 )
        , m_algoCounter( 0 )
        , m_svcLocator( svc )
        , m_name( name )
        , m_initTime( std::chrono::system_clock::now() )
    {
    }
    ~PrecedenceRulesGraph() override
    {
      if ( m_headNode != 0 ) delete m_headNode;
    }

    StatusCode initialize();

    void accept( const std::string& algo_name, IGraphVisitor& visitor ) const;

    StatusCode addDataNode( const DataObjID& dataPath );
    DataNode* getDataNode( const DataObjID& dataPath ) const;
    void registerIODataObjects( const Algorithm* algo );
    StatusCode buildDataDependenciesRealm();

    void addHeadNode( const std::string& headName, bool modeConcurrent, bool modePromptDecision, bool modeOR,
                      bool allPass );
    DecisionNode* getHeadNode() const { return m_headNode; };
    StatusCode addAlgorithmNode( Algorithm* daughterAlgo, const std::string& parentName, bool inverted, bool allPass );
    AlgorithmNode* getAlgorithmNode( const std::string& algoName ) const;
    StatusCode addDecisionHubNode( Algorithm* daughterAlgo, const std::string& parentName, bool modeConcurrent,
                                   bool modePromptDecision, bool modeOR, bool allPass );
    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; }
    const std::chrono::system_clock::time_point getInitTime() const { return m_initTime; }

    void printState( std::stringstream& output, AlgsExecutionStates& states, const std::vector<int>& node_decisions,
                     const unsigned int& recursionLevel ) const
    {
      m_headNode->printState( output, states, node_decisions, recursionLevel );
    }

    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;
    AlgoNodesMap m_algoNameToAlgoNodeMap;
    DecisionHubsMap m_decisionNameToDecisionHubMap;
    DataNodesMap m_dataPathToDataNodeMap;
    AlgoInputsMap m_algoNameToAlgoInputsMap;
    AlgoOutputsMap m_algoNameToAlgoOutputsMap;

    unsigned int m_nodeCounter;
    unsigned int m_algoCounter;

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

    const std::chrono::system_clock::time_point m_initTime;

    precedence::PrecTrace m_precTrace;
    std::map<std::string, precedence::AlgoTraceVertex> m_prec_trace_map;
    precedence::PRGraph m_PRGraph;

    bool m_conditionsRealmEnabled{false};
  };

} // namespace concurrency
#endif