From: Maxwell Pirtle Date: Mon, 6 Mar 2023 14:28:05 +0000 (+0100) Subject: Fix edge cases in variable_for_loop X-Git-Tag: v3.34~362^2~2 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/16d193aba087abf10fa87f418a11fc9406bdf476 Fix edge cases in variable_for_loop Some tests were added which detected an off-by-one error in the implementation logic of the variable_for_loop. Subsequent commits will add more tests to the iterator for further verification --- diff --git a/src/xbt/utils/iter/subsets_tests.cpp b/src/xbt/utils/iter/subsets_tests.cpp index 2415a16657..45908d7953 100644 --- a/src/xbt/utils/iter/subsets_tests.cpp +++ b/src/xbt/utils/iter/subsets_tests.cpp @@ -73,11 +73,60 @@ TEST_CASE("simgrid::xbt::powerset_iterator: Iteration General Properties") 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 outer_loop1{0, 1, 2, 3, 4, 5, 6, 7}; + std::vector outer_loop2{0, 1, 6, 7}; + std::vector outer_loop3{0}; + std::vector empty_set; SECTION("Iterations without effect") { - SECTION("Iteration over no collections") {} + SECTION("Iteration over no collections") + { + variable_for_loop> first; + variable_for_loop> last; + REQUIRE(first == last); + } + + SECTION("Iteration with an empty collection") + { + variable_for_loop> last; + REQUIRE(variable_for_loop>{{empty_set}} == last); + REQUIRE(variable_for_loop>{{outer_loop1}, {empty_set}} == last); + REQUIRE(variable_for_loop>{{outer_loop1}, {outer_loop2}, {empty_set}} == last); + REQUIRE(variable_for_loop>{{outer_loop1}, {outer_loop2}, {outer_loop3}, {empty_set}} == last); + REQUIRE(variable_for_loop>{{outer_loop3}, {empty_set}} == last); + } + + SECTION("Iteration with multiple empty collections") + { + variable_for_loop> last; + REQUIRE(variable_for_loop>{{empty_set}} == last); + REQUIRE(variable_for_loop>{{empty_set}, {empty_set}} == last); + REQUIRE(variable_for_loop>{{outer_loop1}, {outer_loop2}, {empty_set}} == last); + REQUIRE(variable_for_loop>{{outer_loop1}, {outer_loop2}, {empty_set}, {empty_set}} == last); + REQUIRE(variable_for_loop>{ + {outer_loop1}, {outer_loop2}, {outer_loop3}, {empty_set}, {empty_set}} == last); + } + } - SECTION("Iteration with an empty collection") {} + SECTION("Iteration with effects") + { + SECTION("Iteration over a single collection yields the collection") + { + variable_for_loop> first{{outer_loop1}}; + variable_for_loop> last; + + std::vector 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); + } } } \ No newline at end of file diff --git a/src/xbt/utils/iter/variable_for_loop.hpp b/src/xbt/utils/iter/variable_for_loop.hpp index fbb88dbc62..75c4b5478f 100644 --- a/src/xbt/utils/iter/variable_for_loop.hpp +++ b/src/xbt/utils/iter/variable_for_loop.hpp @@ -9,6 +9,7 @@ #include #include #include +#include #include #include @@ -38,25 +39,28 @@ public: using underlying_iterator = typename IterableType::const_iterator; variable_for_loop() = default; + explicit variable_for_loop(std::initializer_list> initializer_list) + : variable_for_loop(std::vector>(initializer_list)) + { + } explicit variable_for_loop(std::vector> 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.empty(); }); + 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); - std::copy(collections.begin(), collections.end(), std::back_inserter(current_subset), - [](const auto c) { return c.begin(); }); } // Otherwise leave `underlying_collections` as default-initialized (i.e. empty) } private: std::vector> underlying_collections; - std::vector current_subset; // boost::iterator_facade<...> interface to implement @@ -76,27 +80,27 @@ template void variable_for_loop::increment return; } - size_t l = 0; - const size_t k = underlying_collections.size() - 1; + bool completed_iteration = true; + const size_t k = underlying_collections.size() - 1; - for (auto j = k - 1; j != std::numeric_limits::max(); j--) { + for (auto j = k; j != std::numeric_limits::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].end()) { - current_subset[j] = underlying_collections[j].begin(); + 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, and everyone else before us has been reset + // be moved down. Everyone else before us has been reset // to properly to point at their beginnings - l = j; + completed_iteration = false; break; } } - if (l == 0) { + if (completed_iteration) { // We've iterated over all subsets at this point: // set the termination condition current_subset.clear();