src/mc/explo/udpor/maximal_subsets_iterator.cpp

   1 #include "src/mc/explo/udpor/maximal_subsets_iterator.hpp"
   2 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
   3 #include "xbt/asserts.h"
   4
   5 #include <algorithm>
   6
   7 namespace simgrid::mc::udpor {
   8
   9 maximal_subsets_iterator::maximal_subsets_iterator(const EventSet& events,
  10                                                    const std::optional<node_filter_function>& filter,
  11                                                    std::optional<size_t> maximum_subset_size)
  12     : maximum_subset_size(maximum_subset_size), current_maximal_set({EventSet()})
  13 {
  14   auto candidate_ordering = events.get_topological_ordering_of_reverse_graph();
  15   if (filter.has_value()) {
  16     // Only store the events in the ordering that "matter" to us
  17     std::copy_if(std::move_iterator(candidate_ordering.begin()), std::move_iterator(candidate_ordering.end()),
  18                  std::back_inserter(topological_ordering), filter.value());
  19   } else {
  20     topological_ordering = std::move(candidate_ordering);
  21   }
  22 }
  23
  24 void maximal_subsets_iterator::increment()
  25 {
  26   // Termination condition
  27   if (current_maximal_set == std::nullopt) {
  28     return;
  29   }
  30
  31   // Stop immediately if there's nothing to search
  32   if (topological_ordering.empty()) {
  33     current_maximal_set = std::nullopt;
  34     return;
  35   }
  36
  37   const auto next_event_ref = [&]() {
  38     if (not has_started_searching) {
  39       has_started_searching = true;
  40       return bookkeeper.find_next_candidate_event(topological_ordering.begin(), topological_ordering.end());
  41     } else {
  42       return continue_traversal_of_maximal_events_tree();
  43     }
  44   }();
  45
  46   // Out of events: we've finished
  47   if (next_event_ref == topological_ordering.end()) {
  48     current_maximal_set = std::nullopt;
  49     return;
  50   }
  51
  52   // We found some other event `e'` which is not in causally related with anything
  53   // that currently exists in `current_maximal_set`, so add it in
  54   add_element_to_current_maximal_set(*next_event_ref);
  55   backtrack_points.push(next_event_ref);
  56 }
  57
  58 maximal_subsets_iterator::topological_order_position
  59 maximal_subsets_iterator::continue_traversal_of_maximal_events_tree()
  60 {
  61   // Nothing needs to be done if there isn't anyone to search for...
  62   if (backtrack_points.empty()) {
  63     return topological_ordering.end();
  64   }
  65
  66   xbt_assert(current_maximal_set.has_value(), "Traversal continued even after the termination condition "
  67                                               "was met. Please verify that the termination condition "
  68                                               "of the iterator has not been modified");
  69
  70   // 1. First, check if we can keep expanding from the
  71   // maximal set that we currently have
  72   if (can_grow_maximal_set()) {
  73     // This is an iterator which points to the latest event `e` that
  74     // was added to what is currently the maximal set
  75     const auto latest_event_ref = backtrack_points.top();
  76
  77     // Look for the next event to test with what we currently
  78     // have based on the conflicts we've already kept track of.
  79     //
  80     // NOTE: We only need to search FROM `e` and not
  81     // from the beginning of the topological sort. The fact that the
  82     // set is topologically ordered ensures that removing `e`
  83     // will not change whether or not to now allow someone before `e`
  84     // in the ordering (otherwise, they would have to be in `e`'s history
  85     // and therefore would come after `e`)
  86     const auto next_event_ref = bookkeeper.find_next_candidate_event(latest_event_ref, topological_ordering.end());
  87
  88     // If we can expand from what we currently have, we can stop
  89     if (next_event_ref != topological_ordering.end()) {
  90       return next_event_ref;
  91     }
  92   }
  93
  94   // Otherwise, we backtrack: we repeatedly pop off events that we know we
  95   // are finished with
  96   while (not backtrack_points.empty()) {
  97     // Note: it is important to remove the element FIRST before performing
  98     // the search, as removal may enable dependencies of `e` to be selected
  99     const auto latest_event_ref = backtrack_points.top();
 100     remove_element_from_current_maximal_set(*latest_event_ref);
 101     backtrack_points.pop();
 102
 103     // We begin the search AFTER the event we popped: we only want
 104     // to consider those events that could be added AFTER `e` and
 105     // not `e` itself again
 106     const auto next_event_ref = bookkeeper.find_next_candidate_event(latest_event_ref + 1, topological_ordering.end());
 107     if (next_event_ref != topological_ordering.end()) {
 108       return next_event_ref;
 109     }
 110   }
 111   return topological_ordering.end();
 112 }
 113
 114 bool maximal_subsets_iterator::Bookkeeper::is_candidate_event(const UnfoldingEvent* e) const
 115 {
 116   if (const auto e_count = event_counts.find(e); e_count != event_counts.end()) {
 117     return e_count->second == 0;
 118   }
 119   return true;
 120 }
 121
 122 void maximal_subsets_iterator::add_element_to_current_maximal_set(const UnfoldingEvent* e)
 123 {
 124   xbt_assert(can_grow_maximal_set(), "Attempting to add an event to the maximal set "
 125                                      "when doing so would increase the size past the "
 126                                      "prescribed limit. This indicates that detecting when "
 127                                      "to stop growing the maximal set when continuing the "
 128                                      "search is broken");
 129   xbt_assert(current_maximal_set.has_value(), "Attempting to add an event to the maximal set "
 130                                               "when iteration has completed. This indicates that "
 131                                               "the termination condition for the iterator is broken");
 132   current_maximal_set.value().insert(e);
 133   bookkeeper.mark_included_in_maximal_set(e);
 134 }
 135
 136 void maximal_subsets_iterator::remove_element_from_current_maximal_set(const UnfoldingEvent* e)
 137 {
 138   xbt_assert(current_maximal_set.has_value(), "Attempting to remove an event to the maximal set "
 139                                               "when iteration has completed. This indicates that "
 140                                               "the termination condition for the iterator is broken");
 141   current_maximal_set.value().remove(e);
 142   bookkeeper.mark_removed_from_maximal_set(e);
 143 }
 144
 145 bool maximal_subsets_iterator::can_grow_maximal_set() const
 146 {
 147   if (not current_maximal_set.has_value()) {
 148     return true;
 149   }
 150   if (maximum_subset_size.has_value()) {
 151     return current_maximal_set.value().size() < maximum_subset_size.value();
 152   }
 153   return true;
 154 }
 155
 156 maximal_subsets_iterator::topological_order_position
 157 maximal_subsets_iterator::Bookkeeper::find_next_candidate_event(topological_order_position first,
 158                                                                 topological_order_position last) const
 159 {
 160   return std::find_if(first, last, [&](const UnfoldingEvent* e) { return is_candidate_event(e); });
 161 }
 162
 163 void maximal_subsets_iterator::Bookkeeper::mark_included_in_maximal_set(const UnfoldingEvent* e)
 164 {
 165   const auto e_local_config = e->get_local_config();
 166   for (const auto* e_hist : e_local_config) {
 167     event_counts[e_hist]++;
 168   }
 169 }
 170
 171 void maximal_subsets_iterator::Bookkeeper::mark_removed_from_maximal_set(const UnfoldingEvent* e)
 172 {
 173   const auto e_local_config = e->get_local_config();
 174   for (const auto* e_hist : e_local_config) {
 175     xbt_assert(event_counts.find(e_hist) != event_counts.end(),
 176                "Invariant Violation: Attempted to remove an event which was not previously added");
 177     xbt_assert(event_counts[e_hist] > 0, "Invariant Violation: An event `e` had a count of `0` at this point "
 178                                          "of the bookkeeping, which means that it is a candidate maximal event. "
 179                                          "Yet some event that `e'` which contains `e` in its history was removed "
 180                                          "first. This incidates that the topological sorting of events of the "
 181                                          "configuration has failed and should be investigated first");
 182     event_counts[e_hist]--;
 183   }
 184 }
 185
 186 } // namespace simgrid::mc::udpor