src/mc/explo/udpor/maximal_subsets_iterator.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_MAXIMAL_SUBSETS_ITERATOR_HPP
   7 #define SIMGRID_MC_UDPOR_MAXIMAL_SUBSETS_ITERATOR_HPP
   8
   9 #include "src/mc/explo/udpor/Configuration.hpp"
  10 #include "src/xbt/utils/iter/iterator_wrapping.hpp"
  11
  12 #include <boost/iterator/iterator_facade.hpp>
  13 #include <functional>
  14 #include <optional>
  15 #include <stack>
  16 #include <unordered_map>
  17
  18 namespace simgrid::mc::udpor {
  19
  20 /**
  21  * @brief An iterator over the tree of sets of (non-empty) maximal events that
  22  * can be generated from a given set of events
  23  *
  24  * This iterator traverses all possible sets of maximal events that
  25  * can be formed from some subset of events of an unfolding,
  26  * each of which satisfy a predicate.
  27  *
  28  * Iteration over the maximal events of a configuration is an important
  29  * step in computing the extension set of a configuration for an action
  30  * whose identity is not "exploitable" (i.e. one whose type information cannot
  31  * help us narrow down our search).
  32  */
  33 struct maximal_subsets_iterator
  34     : public boost::iterator_facade<maximal_subsets_iterator, const EventSet, boost::forward_traversal_tag> {
  35 public:
  36   // A function which answers the question "do I need to consider maximal sets
  37   // that contain this node?"
  38   using node_filter_function       = std::function<bool(const UnfoldingEvent*)>;
  39   using topological_order_position = std::vector<const UnfoldingEvent*>::const_iterator;
  40
  41   maximal_subsets_iterator() = default;
  42   explicit maximal_subsets_iterator(const Configuration& config) : maximal_subsets_iterator(config.get_events()) {}
  43   explicit maximal_subsets_iterator(const EventSet& events) : maximal_subsets_iterator(events, std::nullopt) {}
  44
  45   maximal_subsets_iterator(const Configuration& config, std::optional<node_filter_function> filter)
  46       : maximal_subsets_iterator(config.get_events(), filter)
  47   {
  48   }
  49   maximal_subsets_iterator(const EventSet& events, std::optional<node_filter_function> filter);
  50
  51 private:
  52   std::vector<const UnfoldingEvent*> topological_ordering;
  53
  54   // The boolean is a bit of an annoyance, but it works. Effectively,
  55   // there's no way to distinguish between "we're starting the search
  56   // after the empty set" and "we've finished the search" since the resulting
  57   // maximal set and backtracking point stack will both be empty in both cases
  58   bool has_started_searching                              = false;
  59   std::optional<EventSet> current_maximal_set             = std::nullopt;
  60   std::stack<topological_order_position> backtrack_points = std::stack<topological_order_position>();
  61
  62   /**
  63    * @brief A small class which provides functionality for managing
  64    * the "counts" as the iterator proceeds forward in time
  65    *
  66    * As an instance of the `maximal_subsets_iterator` traverses
  67    * the configuration, it keeps track of how many events
  68    * further down in the causality tree have been signaled as in-conflict
  69    * with events that are its current maximal event set (i.e.
  70    * its `current_maximal_set`)
  71    */
  72   struct bookkeeper {
  73   public:
  74     using topological_order_position = maximal_subsets_iterator::topological_order_position;
  75
  76     void mark_included_in_maximal_set(const UnfoldingEvent*);
  77     void mark_removed_from_maximal_set(const UnfoldingEvent*);
  78     topological_order_position find_next_candidate_event(topological_order_position first,
  79                                                          topological_order_position last) const;
  80
  81   private:
  82     std::unordered_map<const UnfoldingEvent*, unsigned> event_counts;
  83
  84     /// @brief Whether or not the given event, according to the
  85     /// bookkeeping that has been done thus far, can be added to the
  86     /// current candidate maximal set
  87     bool is_candidate_event(const UnfoldingEvent*) const;
  88   } bookkeeper;
  89
  90   void add_element_to_current_maximal_set(const UnfoldingEvent*);
  91   void remove_element_from_current_maximal_set(const UnfoldingEvent*);
  92
  93   /**
  94    * @brief Moves to the next node in the topological ordering
  95    * by continuing the search in the tree of maximal event sets
  96    * from where we currently believe we are in the tree
  97    *
  98    * At each stage of the iteration, the iterator points to
  99    * a maximal event set that can be thought of as `R` + `A`:
 100    *
 101    * |   R    | A
 102    * +--------+
 103    *
 104    * where `R` is some set of events and `A` is another event.
 105    *
 106    * The iterator first tries expansion from `R` + `A`. If it finds
 107    * node `B` to expand, this means that there is a node in the tree of
 108    * maximal event sets of `C` (the configuration traversed) such that
 109    * `R` + `A` + `B` needs to be checked.
 110    *
 111    * If no such node is found, then the iterator must check `R` +
 112    * some other node AFTER `A`. The new set of possibilities potentially
 113    * includes some of `A`'s dependencies, so their counts are decremented
 114    * prior to searching.
 115    *
 116    * @note: This method is a mutating method: it manipulates the
 117    * iterator such that the iterator refers to the next maximal
 118    * set sans the element returned. The `increment()` function performs
 119    * the rest of the work needed to actually complete the transition
 120    *
 121    * @returns an iterator poiting to the event that should next
 122    * be added to the set of maximal events if such an event exists,
 123    * or to the end of the topological ordering if no such event exists
 124    */
 125   topological_order_position continue_traversal_of_maximal_events_tree();
 126
 127   // boost::iterator_facade<...> interface to implement
 128   void increment();
 129   bool equal(const maximal_subsets_iterator& other) const { return current_maximal_set == other.current_maximal_set; }
 130   const EventSet& dereference() const
 131   {
 132     static const EventSet empty_set = EventSet();
 133     if (current_maximal_set.has_value()) {
 134       return current_maximal_set.value();
 135     }
 136     return empty_set;
 137   }
 138
 139   // Allows boost::iterator_facade<...> to function properly
 140   friend class boost::iterator_core_access;
 141 };
 142
 143 using maximal_subsets_iterator_wrapper =
 144     simgrid::xbt::iterator_wrapping<maximal_subsets_iterator, const Configuration&>;
 145
 146 } // namespace simgrid::mc::udpor
 147 #endif