include src/xbt/unit-tests_main.cpp
include src/xbt/utils/iter/LazyKSubsets.hpp
include src/xbt/utils/iter/LazyPowerset.hpp
+include src/xbt/utils/iter/iterator_wrapping.hpp
include src/xbt/utils/iter/powerset.hpp
include src/xbt/utils/iter/subsets.hpp
include src/xbt/utils/iter/subsets_tests.cpp
+include src/xbt/utils/iter/variable_for_loop.hpp
include src/xbt/xbt_log_appender_file.cpp
include src/xbt/xbt_log_layout_format.cpp
include src/xbt/xbt_log_layout_simple.cpp
#include "src/mc/explo/udpor/Configuration.hpp"
#include "src/mc/explo/udpor/History.hpp"
#include "src/mc/explo/udpor/UnfoldingEvent.hpp"
+#include "src/mc/explo/udpor/maximal_subsets_iterator.hpp"
#include "xbt/asserts.h"
#include <algorithm>
std::vector<const UnfoldingEvent*> Configuration::get_topologically_sorted_events() const
{
+ // This is essentially an implementation of detecting cycles
+ // in a graph with coloring, except it makes a topological
+ // ordering out of it
+
if (events_.empty()) {
return std::vector<const UnfoldingEvent*>();
}
if (not temporarily_marked_events.contains(evt)) {
// If this event hasn't yet been marked, do
- // so now so that if we see it again in a child we can
- // detect a cycle and if we see it again here
- // we can detect that the node is re-processed
+ // so now so that if we both see it
+ // again in a child we can detect a cycle
temporarily_marked_events.insert(evt);
EventSet immediate_causes = evt->get_immediate_causes();
}
immediate_causes.subtract(discovered_events);
immediate_causes.subtract(permanently_marked_events);
- const EventSet undiscovered_causes = std::move(immediate_causes);
-
- for (const auto cause : undiscovered_causes) {
- event_stack.push(cause);
- }
+ std::for_each(immediate_causes.begin(), immediate_causes.end(),
+ [&event_stack](const UnfoldingEvent* cause) { event_stack.push(cause); });
} else {
- // Mark this event as:
- // 1. discovered across all DFSs performed
- // 2. permanently marked
- // 3. part of the topological search
unknown_events.remove(evt);
temporarily_marked_events.remove(evt);
permanently_marked_events.insert(evt);
topological_ordering.push_back(evt);
// Only now do we remove the event, i.e. once
- // we've processed the same event again
+ // we've processed the same event twice
event_stack.pop();
}
}
std::vector<const UnfoldingEvent*> Configuration::get_topologically_sorted_events_of_reverse_graph() const
{
- // The method exploits the property that
+ // The implementation exploits the property that
// a topological sorting S^R of the reverse graph G^R
// of some graph G is simply the reverse of any
// topological sorting S of G.
return topological_events;
}
+EventSet Configuration::get_minimally_reproducible_events() const
+{
+ // The implementation exploits the following observations:
+ //
+ // To select the smallest reproducible set of events, we want
+ // to pick events that "knock out" a lot of others. Furthermore,
+ // we need to ensure that the events furthest down in the
+ // causality graph are also selected. If you combine these ideas,
+ // you're basically left with traversing the set of maximal
+ // subsets of C! And we have an iterator for that already!
+ //
+ // The next observation is that the moment we don't increase in size
+ // the current maximal set (or decrease the number of events),
+ // we know that the prior set `S` covered the entire history of C and
+ // was maximal. Subsequent sets will miss events earlier in the
+ // topological ordering that appear in `S`
+ EventSet minimally_reproducible_events = EventSet();
+
+ for (const auto& maximal_set : maximal_subsets_iterator_wrapper(*this)) {
+ if (maximal_set.size() > minimally_reproducible_events.size()) {
+ minimally_reproducible_events = maximal_set;
+ } else {
+ // The moment we see the iterator generate a set of size
+ // that is not monotonically increasing, we can stop:
+ // the set prior was the minimally-reproducible one
+ return minimally_reproducible_events;
+ }
+ }
+ return minimally_reproducible_events;
+}
+
} // namespace simgrid::mc::udpor
#include "src/mc/explo/udpor/EventSet.hpp"
#include "src/mc/explo/udpor/udpor_forward.hpp"
-#include <boost/iterator/iterator_facade.hpp>
-#include <functional>
-#include <initializer_list>
-#include <optional>
-#include <vector>
-
namespace simgrid::mc::udpor {
class Configuration {
*/
std::vector<const UnfoldingEvent*> get_topologically_sorted_events_of_reverse_graph() const;
+ /**
+ * @brief Computes the smallest set of events whose collective histories
+ * capture all events of this configuration
+ *
+ * @invariant The set of all events in the collective histories
+ * of the events returned by this method is equal to the set of events
+ * in this configuration
+ *
+ * @returns the smallest set of events whose events generates this configuration
+ * (denoted `config(E)`)
+ */
+ EventSet get_minimally_reproducible_events() const;
+
private:
/**
* @brief The most recent event added to the configuration
#define SIMGRID_MC_UDPOR_MAXIMAL_SUBSETS_ITERATOR_HPP
#include "src/mc/explo/udpor/Configuration.hpp"
+#include "src/xbt/utils/iter/iterator_wrapping.hpp"
#include <boost/iterator/iterator_facade.hpp>
+#include <functional>
#include <optional>
#include <stack>
#include <unordered_map>
friend class boost::iterator_core_access;
};
+using maximal_subsets_iterator_wrapper =
+ simgrid::xbt::iterator_wrapping<maximal_subsets_iterator, const Configuration&>;
+
} // namespace simgrid::mc::udpor
#endif
class History;
class Unfolding;
class UnfoldingEvent;
+class maximal_subsets_iterator;
} // namespace simgrid::mc::udpor
#ifndef XBT_UTILS_LAZY_POWER_SET_HPP
#define XBT_UTILS_LAZY_POWER_SET_HPP
+#include "src/xbt/utils/iter/iterator_wrapping.hpp"
#include "src/xbt/utils/iter/powerset.hpp"
namespace simgrid::xbt {
-template <class Iterable> class LazyPowerset;
-template <class Iterable> LazyPowerset<Iterable> make_powerset_iter(const Iterable& container);
-
-/**
- * @brief A container which "contains" all subsets of
- * size `k` of some other container `WrapperContainer`
- *
- * @note: You should not store instances of this class directly,
- * as it acts more like a simply wrapping around another iterable
- * type to make it more convenient to iterate over subsets of
- * some iterable type.
- *
- * @class Iterable: The container from which
- * the subsets "contained" by this container are derived
- */
-template <class Iterable> class LazyPowerset final {
-public:
- auto begin() const { return powerset_iterator<typename Iterable::const_iterator>(iterable.begin(), iterable.end()); }
- auto end() const { return powerset_iterator<typename Iterable::const_iterator>(); }
-
-private:
- const Iterable& iterable;
- LazyPowerset(const Iterable& iterable) : iterable(iterable) {}
- template <class IterableType> friend LazyPowerset<IterableType> make_powerset_iter(const IterableType& iterable);
-};
-
-template <class Iterable> LazyPowerset<Iterable> make_powerset_iter(const Iterable& container)
+template <class Iterable, class... Args>
+using LazyPowerset = iterator_wrapping<powerset_iterator<typename Iterable::const_iterator>, Args...>;
+
+template <class Iterable> constexpr auto make_powerset_iter(const Iterable& container)
{
- return LazyPowerset<Iterable>(container);
+ return make_iterator_wrapping<powerset_iterator<typename Iterable::const_iterator>>(container.begin(),
+ container.end());
}
} // namespace simgrid::xbt
--- /dev/null
+/* Copyright (c) 2004-2023 The SimGrid Team. All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+#ifndef XBT_UTILS_ITER_ITERATOR_WRAPPING_HPP
+#define XBT_UTILS_ITER_ITERATOR_WRAPPING_HPP
+
+#include <tuple>
+#include <type_traits>
+
+namespace simgrid::xbt {
+
+template <typename T> struct ref_or_value {
+ using type = std::conditional_t<std::is_lvalue_reference<T>::value,
+ std::reference_wrapper<typename std::remove_reference<T>::type>, T>;
+};
+template <typename T> using ref_or_value_t = typename ref_or_value<T>::type;
+
+/**
+ * @brief A container which simply forwards its arguments to an
+ * iterator to begin traversal over another collection
+ *
+ * An `iterator_wrapping` acts as a proxy to the collection that it
+ * wraps. You create an `iterator_wrapping` as a convenience to needing
+ * to manually check stop and end conditions when constructing iterators
+ * directly, e.g. in a for-loop. With an `iterator_wrapping`, you can
+ * simply act as if the iterator were a collection and use it e.g. in
+ * auto-based for-loops.
+ *
+ * @class Iterator: The type of the iterator that is constructed to
+ * traverse the container.
+ *
+ * @note The wrapping only works correctly if the iterator type (Iterator)
+ * that is constructed can be default constructed, and only if the default-constructed
+ * iterate is a valid representation of the "end()" of any iterator type.
+ * That is, if you must supply additional arguments to indicate the end of a collection,
+ * you'll have to construct is manually.
+ */
+template <typename Iterator, typename... Args> struct iterator_wrapping {
+private:
+ std::tuple<ref_or_value_t<Args>...> m_args;
+
+ template <typename IteratorType, typename... Arguments>
+ friend constexpr iterator_wrapping<IteratorType, Arguments...> make_iterator_wrapping(Arguments&&... args);
+
+ template <typename IteratorType, typename... Arguments>
+ friend constexpr iterator_wrapping<IteratorType, Arguments...> make_iterator_wrapping_explicit(Arguments... args);
+
+public:
+ iterator_wrapping(Args&&... begin_iteration) : m_args(std::forward<ref_or_value_t<Args>>(begin_iteration)...) {}
+ iterator_wrapping(const iterator_wrapping&) = delete;
+ iterator_wrapping(iterator_wrapping&&) = delete;
+ iterator_wrapping& operator=(const iterator_wrapping&) = delete;
+ iterator_wrapping& operator=(iterator_wrapping&&) = delete;
+
+ Iterator begin() const
+ {
+ return std::apply([](auto&... args) { return Iterator(args...); }, m_args);
+ }
+ Iterator end() const { return Iterator(); }
+};
+
+template <typename Iterator, typename... Args>
+constexpr iterator_wrapping<Iterator, Args...> make_iterator_wrapping(Args&&... args)
+{
+ return iterator_wrapping<Iterator, Args...>(std::forward<Args>(args)...);
+}
+
+template <typename Iterator, typename... Args>
+constexpr iterator_wrapping<Iterator, Args...> make_iterator_wrapping_explicit(Args... args)
+{
+ return iterator_wrapping<Iterator, Args...>(std::forward<Args>(args)...);
+}
+
+} // namespace simgrid::xbt
+
+#endif
#include "src/3rd-party/catch.hpp"
#include "src/xbt/utils/iter/LazyKSubsets.hpp"
#include "src/xbt/utils/iter/LazyPowerset.hpp"
+#include "src/xbt/utils/iter/variable_for_loop.hpp"
#include <unordered_map>
#include <unordered_set>
{
std::vector<int> example_vec{0, 1, 2, 3, 4, 5, 6, 7};
- SECTION("Each element of each subset is distinct and appears half of the time")
+ SECTION("Each element of each subset is distinct")
{
for (unsigned k = 0; static_cast<size_t>(k) < example_vec.size(); k++) {
for (auto& subset : make_k_subsets_iter(k, example_vec)) {
REQUIRE(iter.second == expected_count);
}
}
+}
+
+TEST_CASE("simgrid::xbt::variable_for_loop: Edge Cases")
+{
+ // Note the extra `{}` in the tests. This constructs a
+ // `std::reference_wrapper` to the specified collection
+ std::vector<int> outer_loop1{0, 1, 2, 3, 4};
+ std::vector<int> outer_loop2{0, 1, 6, 7};
+ std::vector<int> outer_loop3{1, 2};
+ std::vector<int> empty_set;
+
+ SECTION("Iterations without effect")
+ {
+ SECTION("Iteration over no collections")
+ {
+ variable_for_loop<std::vector<int>> first;
+ variable_for_loop<std::vector<int>> last;
+ REQUIRE(first == last);
+ }
+
+ SECTION("Iteration with an empty collection")
+ {
+ variable_for_loop<std::vector<int>> last;
+ REQUIRE(variable_for_loop<std::vector<int>>{{empty_set}} == last);
+ REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop1}, {empty_set}} == last);
+ REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop1}, {outer_loop2}, {empty_set}} == last);
+ REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop1}, {outer_loop2}, {outer_loop3}, {empty_set}} == last);
+ REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop3}, {empty_set}} == last);
+ }
+
+ SECTION("Iteration with multiple empty collections")
+ {
+ variable_for_loop<std::vector<int>> last;
+ REQUIRE(variable_for_loop<std::vector<int>>{{empty_set}} == last);
+ REQUIRE(variable_for_loop<std::vector<int>>{{empty_set}, {empty_set}} == last);
+ REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop1}, {outer_loop2}, {empty_set}} == last);
+ REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop1}, {outer_loop2}, {empty_set}, {empty_set}} == last);
+ REQUIRE(variable_for_loop<std::vector<int>>{
+ {outer_loop1}, {outer_loop2}, {outer_loop3}, {empty_set}, {empty_set}} == last);
+ }
+ }
+
+ SECTION("Iteration with effects")
+ {
+ SECTION("Iteration over a single collection yields the collection")
+ {
+ variable_for_loop<std::vector<int>> first{{outer_loop1}};
+ variable_for_loop<std::vector<int>> last;
+
+ std::vector<int> elements_seen;
+
+ for (; first != last; ++first) {
+ const auto& elements = *first;
+ REQUIRE(elements.size() == 1);
+ elements_seen.push_back(*elements[0]);
+ }
+
+ REQUIRE(elements_seen == outer_loop1);
+ }
+
+ SECTION("Iteration over two collections yields all pairs")
+ {
+ variable_for_loop<std::vector<int>> first{{outer_loop1, outer_loop2}};
+ variable_for_loop<std::vector<int>> last;
+
+ std::vector<std::pair<int, int>> pairs_seen;
+ for (; first != last; ++first) {
+ const auto& elements = *first;
+ REQUIRE(elements.size() == 2);
+ pairs_seen.push_back(std::make_pair(*elements[0], *elements[1]));
+ }
+
+ std::vector<std::pair<int, int>> expected_pairs{{0, 0}, {0, 1}, {0, 6}, {0, 7}, {1, 0}, {1, 1}, {1, 6},
+ {1, 7}, {2, 0}, {2, 1}, {2, 6}, {2, 7}, {3, 0}, {3, 1},
+ {3, 6}, {3, 7}, {4, 0}, {4, 1}, {4, 6}, {4, 7}};
+ REQUIRE(pairs_seen == expected_pairs);
+ }
+
+ SECTION("Iteration over three collections yields all triples")
+ {
+ variable_for_loop<std::vector<int>> first{{outer_loop3, outer_loop1, outer_loop2}};
+ variable_for_loop<std::vector<int>> last;
+
+ std::vector<std::tuple<int, int, int>> triples_seen;
+ for (; first != last; ++first) {
+ const auto& elements = *first;
+ REQUIRE(elements.size() == 3);
+ triples_seen.push_back(std::make_tuple(*elements[0], *elements[1], *elements[2]));
+ }
+
+ std::vector<std::tuple<int, int, int>> expected_triples{
+ {1, 0, 0}, {1, 0, 1}, {1, 0, 6}, {1, 0, 7}, {1, 1, 0}, {1, 1, 1}, {1, 1, 6}, {1, 1, 7}, {1, 2, 0}, {1, 2, 1},
+ {1, 2, 6}, {1, 2, 7}, {1, 3, 0}, {1, 3, 1}, {1, 3, 6}, {1, 3, 7}, {1, 4, 0}, {1, 4, 1}, {1, 4, 6}, {1, 4, 7},
+
+ {2, 0, 0}, {2, 0, 1}, {2, 0, 6}, {2, 0, 7}, {2, 1, 0}, {2, 1, 1}, {2, 1, 6}, {2, 1, 7}, {2, 2, 0}, {2, 2, 1},
+ {2, 2, 6}, {2, 2, 7}, {2, 3, 0}, {2, 3, 1}, {2, 3, 6}, {2, 3, 7}, {2, 4, 0}, {2, 4, 1}, {2, 4, 6}, {2, 4, 7}};
+
+ REQUIRE(triples_seen == expected_triples);
+ }
+
+ SECTION("Iteration over all collections yields all combinations")
+ {
+ std::vector<int> outer_loop4{1, 5};
+ std::vector<int> outer_loop5{1, 8};
+
+ variable_for_loop<std::vector<int>> first{
+ {outer_loop1}, {outer_loop2}, {outer_loop3}, {outer_loop4}, {outer_loop5}};
+ variable_for_loop<std::vector<int>> last;
+
+ size_t total_iterations = 0;
+ for (; first != last; ++first, ++total_iterations) {
+ const auto& elements = *first;
+ REQUIRE(elements.size() == 5);
+ }
+ REQUIRE(total_iterations ==
+ (outer_loop1.size() * outer_loop2.size() * outer_loop3.size() * outer_loop4.size() * outer_loop5.size()));
+ }
+ }
}
\ No newline at end of file
--- /dev/null
+/* Copyright (c) 2004-2023 The SimGrid Team. All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+#ifndef XBT_UTILS_ITER_VARIABLE_FOR_LOOP_HPP
+#define XBT_UTILS_ITER_VARIABLE_FOR_LOOP_HPP
+
+#include <algorithm>
+#include <boost/iterator/iterator_facade.hpp>
+#include <functional>
+#include <initializer_list>
+#include <limits>
+#include <optional>
+
+namespace simgrid::xbt {
+
+/**
+ * @brief A higher-order forward-iterator which traverses all possible
+ * combinations of selections of elements from a collection of iterable
+ * sequences
+ *
+ * This iterator provides a means of iteratively traversing all combinations
+ * of elements of `k` collections (albeit of a single type), selecting a
+ * single element from each of the `k` collections in the same way a
+ * nested for-loop may select a set of elements. The benefit is that
+ * you do not need to actually physically write the for-loop statements
+ * directly, and you can dynamically adjust the number of levels of the
+ * for-loop according to the situation
+ *
+ * @class IterableType: The collections from which this iterator
+ * selects elements
+ */
+template <class IterableType>
+struct variable_for_loop : public boost::iterator_facade<variable_for_loop<IterableType>,
+ const std::vector<typename IterableType::const_iterator>,
+ boost::forward_traversal_tag> {
+public:
+ using underlying_iterator = typename IterableType::const_iterator;
+
+ variable_for_loop() = default;
+ explicit variable_for_loop(std::initializer_list<std::reference_wrapper<IterableType>> initializer_list)
+ : variable_for_loop(std::vector<std::reference_wrapper<IterableType>>(initializer_list))
+ {
+ }
+ explicit variable_for_loop(std::vector<std::reference_wrapper<IterableType>> collections)
+ {
+ // All collections should be non-empty: if one is empty, the
+ // for-loop has no effect (since there would be no way to choose
+ // one element from the empty collection(s))
+ const auto has_effect =
+ std::none_of(collections.begin(), collections.end(), [](const auto& c) { return c.get().empty(); });
+
+ if (has_effect and (not collections.empty())) {
+ std::transform(collections.begin(), collections.end(), std::back_inserter(current_subset),
+ [](const auto& c) { return c.get().begin(); });
+ underlying_collections = std::move(collections);
+ }
+ // Otherwise leave `underlying_collections` as default-initialized (i.e. empty)
+ }
+
+private:
+ std::vector<std::reference_wrapper<IterableType>> underlying_collections;
+ std::vector<underlying_iterator> current_subset;
+
+ // boost::iterator_facade<...> interface to implement
+ void increment();
+ bool equal(const variable_for_loop<IterableType>& other) const { return current_subset == other.current_subset; }
+ const std::vector<underlying_iterator>& dereference() const { return current_subset; }
+
+ // Allows boost::iterator_facade<...> to function properly
+ friend class boost::iterator_core_access;
+};
+
+template <typename IterableType> void variable_for_loop<IterableType>::increment()
+{
+ // Termination occurs when `current_subset := the empty set`
+ // or if we have nothing to iterate over
+ if (current_subset.empty() or underlying_collections.empty()) {
+ return;
+ }
+
+ bool completed_iteration = true;
+ const size_t k = underlying_collections.size() - 1;
+
+ for (auto j = k; j != std::numeric_limits<size_t>::max(); j--) {
+ // Attempt to move to the next element of the `j`th collection
+ const auto& new_position = ++current_subset[j];
+
+ // If the `j`th element has reached its own end, reset it
+ // back to the beginning and keep moving forward
+ if (new_position == underlying_collections[j].get().end()) {
+ current_subset[j] = underlying_collections[j].get().begin();
+ } else {
+ // Otherwise we've found the largest element which needed to
+ // be moved down. Everyone else before us has been reset
+ // to properly to point at their beginnings
+ completed_iteration = false;
+ break;
+ }
+ }
+
+ if (completed_iteration) {
+ // We've iterated over all subsets at this point:
+ // set the termination condition
+ current_subset.clear();
+ return;
+ }
+}
+
+} // namespace simgrid::xbt
+
+#endif
src/xbt/xbt_parse_units.cpp
src/xbt/xbt_replay.cpp
src/xbt/xbt_str.cpp
+ src/xbt/utils/iter/iterator_wrapping.hpp
src/xbt/utils/iter/subsets.hpp
src/xbt/utils/iter/powerset.hpp
+ src/xbt/utils/iter/variable_for_loop.hpp
src/xbt/utils/iter/LazyKSubsets.hpp
src/xbt/utils/iter/LazyPowerset.hpp
)
