Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
There is no need to declare the default constructors here.
[simgrid.git] / 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,
43                                     std::optional<node_filter_function> filter = std::nullopt,
44                                     std::optional<size_t> maximum_subset_size  = std::nullopt)
45       : maximal_subsets_iterator(config.get_events(), filter, maximum_subset_size)
46   {
47   }
48   explicit maximal_subsets_iterator(const EventSet& events, std::optional<node_filter_function> filter = std::nullopt,
49                                     std::optional<size_t> maximum_subset_size = std::nullopt);
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<size_t> maximum_subset_size               = std::nullopt;
60   std::optional<EventSet> current_maximal_set             = std::nullopt;
61   std::stack<topological_order_position> backtrack_points = std::stack<topological_order_position>();
62
63   /**
64    * @brief A small class which provides functionality for managing
65    * the "counts" as the iterator proceeds forward in time
66    *
67    * As an instance of the `maximal_subsets_iterator` traverses
68    * the configuration, it keeps track of how many events
69    * further down in the causality tree have been signaled as in-conflict
70    * with events that are its current maximal event set (i.e.
71    * its `current_maximal_set`)
72    */
73   struct bookkeeper {
74   public:
75     using topological_order_position = maximal_subsets_iterator::topological_order_position;
76
77     void mark_included_in_maximal_set(const UnfoldingEvent*);
78     void mark_removed_from_maximal_set(const UnfoldingEvent*);
79     topological_order_position find_next_candidate_event(topological_order_position first,
80                                                          topological_order_position last) const;
81
82   private:
83     std::unordered_map<const UnfoldingEvent*, unsigned> event_counts;
84
85     /// @brief Whether or not the given event, according to the
86     /// bookkeeping that has been done thus far, can be added to the
87     /// current candidate maximal set
88     bool is_candidate_event(const UnfoldingEvent*) const;
89   } bookkeeper;
90
91   void add_element_to_current_maximal_set(const UnfoldingEvent*);
92   void remove_element_from_current_maximal_set(const UnfoldingEvent*);
93
94   /**
95    * @brief Moves to the next node in the topological ordering
96    * by continuing the search in the tree of maximal event sets
97    * from where we currently believe we are in the tree
98    *
99    * At each stage of the iteration, the iterator points to
100    * a maximal event set that can be thought of as `R` + `A`:
101    *
102    * |   R    | A
103    * +--------+
104    *
105    * where `R` is some set of events and `A` is another event.
106    *
107    * The iterator first tries expansion from `R` + `A`. If it finds
108    * node `B` to expand, this means that there is a node in the tree of
109    * maximal event sets of `C` (the configuration traversed) such that
110    * `R` + `A` + `B` needs to be checked.
111    *
112    * If no such node is found, then the iterator must check `R` +
113    * some other node AFTER `A`. The new set of possibilities potentially
114    * includes some of `A`'s dependencies, so their counts are decremented
115    * prior to searching.
116    *
117    * @note: This method is a mutating method: it manipulates the
118    * iterator such that the iterator refers to the next maximal
119    * set sans the element returned. The `increment()` function performs
120    * the rest of the work needed to actually complete the transition
121    *
122    * @returns an iterator poiting to the event that should next
123    * be added to the set of maximal events if such an event exists,
124    * or to the end of the topological ordering if no such event exists
125    */
126   topological_order_position continue_traversal_of_maximal_events_tree();
127
128   /**
129    * @brief: Whether or not the current maximal set can
130    * grow based on the size limit imposed on the maximal
131    * sets that can be produced
132    */
133   bool can_grow_maximal_set() const;
134
135   // boost::iterator_facade<...> interface to implement
136   void increment();
137   bool equal(const maximal_subsets_iterator& other) const { return current_maximal_set == other.current_maximal_set; }
138   const EventSet& dereference() const
139   {
140     static const EventSet empty_set = EventSet();
141     if (current_maximal_set.has_value()) {
142       return current_maximal_set.value();
143     }
144     return empty_set;
145   }
146
147   // Allows boost::iterator_facade<...> to function properly
148   friend class boost::iterator_core_access;
149 };
150
151 template <typename T>
152 using maximal_subsets_iterator_wrapper = simgrid::xbt::iterator_wrapping<maximal_subsets_iterator, const T&>;
153
154 } // namespace simgrid::mc::udpor
155 #endif