1 #include "src/mc/explo/udpor/maximal_subsets_iterator.hpp"
2 #include "src/mc/explo/udpor/UnfoldingEvent.hpp"
3 #include "xbt/asserts.h"
7 namespace simgrid::mc::udpor {
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()})
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());
20 topological_ordering = std::move(candidate_ordering);
24 void maximal_subsets_iterator::increment()
26 // Termination condition
27 if (current_maximal_set == std::nullopt) {
31 // Stop immediately if there's nothing to search
32 if (topological_ordering.empty()) {
33 current_maximal_set = std::nullopt;
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());
42 return continue_traversal_of_maximal_events_tree();
46 // Out of events: we've finished
47 if (next_event_ref == topological_ordering.end()) {
48 current_maximal_set = std::nullopt;
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);
58 maximal_subsets_iterator::topological_order_position
59 maximal_subsets_iterator::continue_traversal_of_maximal_events_tree()
61 // Nothing needs to be done if there isn't anyone to search for...
62 if (backtrack_points.empty()) {
63 return topological_ordering.end();
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");
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();
77 // Look for the next event to test with what we currently
78 // have based on the conflicts we've already kept track of.
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());
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;
94 // Otherwise, we backtrack: we repeatedly pop off events that we know we
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();
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;
111 return topological_ordering.end();
114 bool maximal_subsets_iterator::Bookkeeper::is_candidate_event(const UnfoldingEvent* e) const
116 if (const auto e_count = event_counts.find(e); e_count != event_counts.end()) {
117 return e_count->second == 0;
122 void maximal_subsets_iterator::add_element_to_current_maximal_set(const UnfoldingEvent* e)
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 "
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);
136 void maximal_subsets_iterator::remove_element_from_current_maximal_set(const UnfoldingEvent* e)
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);
145 bool maximal_subsets_iterator::can_grow_maximal_set() const
147 if (not current_maximal_set.has_value()) {
150 if (maximum_subset_size.has_value()) {
151 return current_maximal_set.value().size() < maximum_subset_size.value();
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
160 return std::find_if(first, last, [&](const UnfoldingEvent* e) { return is_candidate_event(e); });
163 void maximal_subsets_iterator::Bookkeeper::mark_included_in_maximal_set(const UnfoldingEvent* e)
165 const auto e_local_config = e->get_local_config();
166 for (const auto* e_hist : e_local_config) {
167 event_counts[e_hist]++;
171 void maximal_subsets_iterator::Bookkeeper::mark_removed_from_maximal_set(const UnfoldingEvent* e)
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]--;
186 } // namespace simgrid::mc::udpor