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