Protect against overloaded comma in random_shuffle and improve tests

[mclow.lists]

Nice catch. The fix in <algorithm> is exactly right, but I think the tests need more work.

test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp

35

This is not how I would rewrite this test.
I would write a routine that took two "iterators", and called random_shuffle, and then checked for the desired results.

Then call it with pointers. and RA iters, etc.
for example:

template <Class Iter>
void test(Iter first, Iter last, Iter resFirst, Iter resLast);

test(nullptr, nullptr, nullptr, nullptr);
int source[] = {1, 2, 3, 4};
int res      [] = {1, 2, 3, 4};
const unsigned size = sizeof(source)/sizeof(source[0]);

test(source, source + size, res, res+size); 
test(random_access_iterator<int*>(source) .... );

[gribozavr]

test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp

35

I actually thought about this, and it is hard to rewrite it like that for two reasons. First, random_shuffle mutates the elements, so one needs to restore the original sequence between calls to test() (otherwise it is not obvious that it was mutated). Second, this overload of random_shuffle takes randomness from global state, so one can't just specify one expected result in the test. That's why I first check for the initial shuffle exactly, and then only check that the output is a permutation of input.

[gribozavr]

test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp

35

Ping?

[mclow.lists]

test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp

35

Which is why I think that your use of is_permutation is good below.

What do we want to know after calling random_shuffle?

1. The same items are in the range, only in a different order. (right? Can it ever "do nothing")
2. Nothing else is changed.

If you have two collections with the same contents, you should be able to shuffle one over and over, and call is_permutation to compare the two after each call.

Tests that have duplicates are good, too.
[ Yes, I know that your bug report (and fix!) are very localized, but these tests are really lacking ]

If you don't want to do this, I'll rewrite these tests sometime in the next couple weeks, and then we can revisit your patch.

[EricWF]

@gribozavr The tests have changed a bunch since this patch was created. I took the liberty of re-merging the tests. You can find the updated patch here:

https://gist.github.com/EricWF/a69933b79adf8cd61f1daa68c633cc03

Feel free to commit with the new tests.

test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp

35

I think the tests as written are an improvement over the current tests, and I think @gribozavr addressed most of @mclow.lists points above pretty well.

@mclow.lists Feel free to rewrite the tests once this has been committed.

[mclow.lists]

(Finally) committed this as revision 352087.
I cut out most of the random_shuffle_rand.pass.cpp test, because it relied on C++11 features, and didn't work for C++03.
If you want to re-submit the test as a separate patch, I promise to review it in a more timely manner.

include/algorithm

random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef uniform_int_distribution<ptrdiff_t> _Dp;
     typedef typename _Dp::param_type _Pp;
     difference_type __d = __last - __first;
     if (__d > 1)
     {
         _Dp __uid;
         __rs_default __g = __rs_get();
-        for (--__last, --__d; __first < __last; ++__first, --__d)
+        for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
         {
             difference_type __i = __uid(__g, _Pp(0, __d));
             if (__i != difference_type(0))
                 swap(*__first, *(__first + __i));
         }
     }
 }
 
 template <class _RandomAccessIterator, class _RandomNumberGenerator>
 void
 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
                _RandomNumberGenerator&& __rand)
 #else
                _RandomNumberGenerator& __rand)
 #endif
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     difference_type __d = __last - __first;
     if (__d > 1)
     {
-        for (--__last; __first < __last; ++__first, --__d)
+        for (--__last; __first < __last; ++__first, (void) --__d)
         {
             difference_type __i = __rand(__d);
             swap(*__first, *(__first + __i));
         }
     }
 }
 
 template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>

test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle.pass.cpp

 // template<RandomAccessIterator Iter>
 //   requires ShuffleIterator<Iter>
 //   void
 //   random_shuffle(Iter first, Iter last);
 
 #include <algorithm>
 #include <cassert>
 
-int main()
+#include "test_iterators.h"
+
+void test_initial_sequence()
 {
     int ia[] = {1, 2, 3, 4};
     int ia1[] = {1, 4, 3, 2};
     int ia2[] = {4, 1, 2, 3};
     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+
     std::random_shuffle(ia, ia+sa);
     assert(std::equal(ia, ia+sa, ia1));
+
     std::random_shuffle(ia, ia+sa);
     assert(std::equal(ia, ia+sa, ia2));
 }
+
+template <class Iter>
+void
+test_with_iterator()
+{
+    int empty[] = {};
+    std::random_shuffle(Iter(empty), Iter(empty));
+
+    int all_elements[] = {1, 2, 3, 4};
+    int shuffled[] = {1, 2, 3, 4};
+    const unsigned size = sizeof(all_elements)/sizeof(all_elements[0]);
+
+    std::random_shuffle(Iter(shuffled), Iter(shuffled+size));
+    assert(std::is_permutation(shuffled, shuffled+size, all_elements));
+
+    std::random_shuffle(Iter(shuffled), Iter(shuffled+size));
+    assert(std::is_permutation(shuffled, shuffled+size, all_elements));
+}
+
+int main()
+{
+    test_initial_sequence();
+    test_with_iterator<random_access_iterator<int*> >();
+    test_with_iterator<int*>();
+}
+

test/std/algorithms/alg.modifying.operations/alg.random.shuffle/random_shuffle_rand.pass.cpp

 //   requires ShuffleIterator<Iter>
 //         && Convertible<Rand::result_type, Iter::difference_type>
 //   void
 //   random_shuffle(Iter first, Iter last, Rand&& rand);
 
 #include <algorithm>
 #include <cassert>
 
+#include "test_iterators.h"
+
+struct min_swappable {
+    int value;
+    min_swappable(int value) : value(value) {}
+    min_swappable(const min_swappable&) = delete;
+    void operator=(const min_swappable&) = delete;
+
+    static int swaps;
+};
+
+int min_swappable::swaps = 0;
+
+void swap(min_swappable& lhs, min_swappable& rhs)
+{
+    std::swap(lhs.value, rhs.value);
+    ++min_swappable::swaps;
+}
+
+bool operator==(const min_swappable& lhs, const min_swappable& rhs)
+{
+    return lhs.value == rhs.value;
+}
+
+struct init_gen {};
+
 struct gen
 {
+    gen(init_gen) {}
+
+    gen(const gen&) = delete;
+    void operator=(const gen&) = delete;
+
+    static int calls;
+
     int operator()(int n)
     {
+        ++calls;
         return n-1;
     }
 };
 
+int gen::calls = 0;
+
+template <class Iter, class ValueType>
+void
+test_with_iterator()
+{
+    gen::calls = 0;
+
+    ValueType empty[] = {};
+    std::random_shuffle(Iter(empty), Iter(empty));
+    assert(gen::calls == 0);
+
+    ValueType shuffled[] = {{1}, {2}, {3}, {4}};
+    ValueType shuffled1[] = {{4}, {1}, {2}, {3}};
+    ValueType shuffled2[] = {{3}, {4}, {1}, {2}};
+    const unsigned size = sizeof(shuffled)/sizeof(shuffled[0]);
+    gen r(init_gen{});
+
+    std::random_shuffle(Iter(shuffled), Iter(shuffled+size), r);
+    assert(std::equal(shuffled, shuffled+size, shuffled1));
+    assert(gen::calls == 3);
+
+    std::random_shuffle(Iter(shuffled), Iter(shuffled+size), r);
+    assert(std::equal(shuffled, shuffled+size, shuffled2));
+    assert(gen::calls == 6);
+}
+
 int main()
 {
-    int ia[] = {1, 2, 3, 4};
-    int ia1[] = {4, 1, 2, 3};
-    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
-    gen r;
-    std::random_shuffle(ia, ia+sa, r);
-    assert(std::equal(ia, ia+sa, ia1));
+    min_swappable::swaps = 0;
+    test_with_iterator<random_access_iterator<min_swappable*>, min_swappable >();
+    assert(min_swappable::swaps == 6);
+
+    test_with_iterator<random_access_iterator<int*>, int >();
+
+    min_swappable::swaps = 0;
+    test_with_iterator<min_swappable*, min_swappable>();
+    assert(min_swappable::swaps == 6);
+
+    test_with_iterator<int*, int>();
 }
+