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