src/mc/explo/udpor/History.hpp

   1 /* Copyright (c) 2007-2023. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #ifndef SIMGRID_MC_UDPOR_HISTORY_HPP
   7 #define SIMGRID_MC_UDPOR_HISTORY_HPP
   8
   9 #include "src/mc/explo/udpor/Configuration.hpp"
  10 #include "src/mc/explo/udpor/EventSet.hpp"
  11 #include "src/mc/explo/udpor/udpor_forward.hpp"
  12
  13 #include <boost/iterator/iterator_facade.hpp>
  14 #include <functional>
  15 #include <optional>
  16
  17 namespace simgrid::mc::udpor {
  18
  19 /**
  20  * @brief Conceptually describes the local configuration(s) of
  21  * an event or a collection of events, encoding the history of
  22  * the events without needing to actually fully compute all of
  23  * the events contained in the history
  24  *
  25  * When you create an instance of `History`, you are effectively
  26  * making a "lazy" configuration whose elements are the set of
  27  * causes of a given event (if the `History` constists of a single
  28  * event) or the union of all causes of all events (if the
  29  * `History` consists of a set of events).
  30  *
  31  * Using a `History` object to represent the history of a set of
  32  * events is more efficient (and reads more easily) than first
  33  * computing the entire history of each of the events separately
  34  * and combining the results. The former can take advantage of the
  35  * fact that the histories of a set of events overlap greatly, and
  36  * thus only a single BFS/DFS search over the event structure needs
  37  * to be performed instead of many isolated searches for each event.
  38  *
  39  * The same observation also allows you to compute the difference between
  40  * a configuration and a history of a set of events. This is used
  41  * in UDPOR, for example, when determing the difference J / C and
  42  * when using K-partial alternatives (which computes J as the union
  43  * of histories of events)
  44  */
  45 class History {
  46 private:
  47   /**
  48    * @brief The events whose history this instance describes
  49    */
  50   EventSet events_;
  51
  52 public:
  53   History(const History&)            = default;
  54   History& operator=(History const&) = default;
  55   History(History&&)                 = default;
  56
  57   explicit History(EventSet event_set = EventSet()) : events_(std::move(event_set)) {}
  58   explicit History(const UnfoldingEvent* e) : events_({e}) {}
  59
  60   auto begin() const { return Iterator(events_); }
  61   auto end() const { return Iterator(EventSet()); }
  62
  63   /**
  64    * @brief Whether or not the given event is contained in the history
  65    *
  66    * @note If you only need to determine whether a few events are contained
  67    * in a history, prefer this method. If, however, you wish to repeatedly
  68    * determine over time (e.g. over the course of a computation) whether
  69    * some event is part of the history, it may be better to first compute
  70    * all events (see `History::get_all_events()`) and reuse this set
  71    *
  72    * @param e the event to check
  73    * @returns whether or not `e` is contained in the collection
  74    */
  75   bool contains(const UnfoldingEvent* e) const;
  76
  77   /**
  78    * @brief Computes all events in the history described by this instance
  79    *
  80    * Sometimes, it is useful to compute the entire set of events that
  81    * comprise the history of some event `e` of some set of events `E`.
  82    * This method performs that computation.
  83    *
  84    * @returns the set of all causal dependencies of all events this
  85    * history represents. Equivalently, the method returns the full
  86    * dependency graph for all events in this history
  87    */
  88   EventSet get_all_events() const;
  89
  90   /**
  91    * @brief Computes all events in the history described by this instance
  92    * which are maximal (intuitively, those events which cause no others
  93    * or are the "most recent")
  94    */
  95   EventSet get_all_maximal_events() const;
  96
  97   EventSet get_event_diff_with(const Configuration& config) const;
  98
  99 private:
 100   /**
 101    * @brief An iterator which traverses the history of a set of events
 102    */
 103   struct Iterator : boost::iterator_facade<Iterator, const UnfoldingEvent* const, boost::forward_traversal_tag> {
 104   public:
 105     using optional_configuration = std::optional<std::reference_wrapper<const Configuration>>;
 106     Iterator(const EventSet& initial_events, optional_configuration config = std::nullopt);
 107
 108   private:
 109     /// @brief Points in the graph from where to continue the search
 110     EventSet frontier;
 111
 112     /// @brief What the iterator currently believes to be the
 113     /// entire history of the events in the graph it traverses
 114     EventSet current_history = EventSet();
 115
 116     /// @brief What the iterator currently believes
 117     // to be the set of maximal events
 118     EventSet maximal_events;
 119     optional_configuration configuration;
 120
 121     // boost::iterator_facade<...> interface to implement
 122     void increment();
 123     bool equal(const Iterator& other) const;
 124
 125     const UnfoldingEvent* const& dereference() const;
 126
 127     // Allows boost::iterator_facade<...> to function properly
 128     friend class boost::iterator_core_access;
 129
 130     // Allow the `History` class to use some of the
 131     // computation of the iterator
 132     friend History;
 133   };
 134 };
 135
 136 } // namespace simgrid::mc::udpor
 137 #endif