Add Catch::Detail::is_permutation that supports sentinels

Also split out helpers for testing matcher ranges (types whose
begin/end/empty/etc require ADL lookup, types whose iteration
uses iterator + sentinel pair, etc) into their own file.

5 files changed, 309 insertions, 203 deletions

diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
index 023f478b..7be57abe 100644
--- a/tests/CMakeLists.txt
+++ b/tests/CMakeLists.txt
@@ -77,6 +77,7 @@ endif(MSVC) #Temporary workaround
 # Please keep these ordered alphabetically
 set(TEST_SOURCES
         ${SELF_TEST_DIR}/TestRegistrations.cpp
+        ${SELF_TEST_DIR}/IntrospectiveTests/Algorithms.tests.cpp
         ${SELF_TEST_DIR}/IntrospectiveTests/Clara.tests.cpp
         ${SELF_TEST_DIR}/IntrospectiveTests/CmdLine.tests.cpp
         ${SELF_TEST_DIR}/IntrospectiveTests/CmdLineHelpers.tests.cpp
@@ -134,6 +135,7 @@ set(TEST_SOURCES
 
 set(TEST_HEADERS
   ${SELF_TEST_DIR}/helpers/parse_test_spec.hpp
+  ${SELF_TEST_DIR}/helpers/range_test_helpers.hpp
   ${SELF_TEST_DIR}/helpers/type_with_lit_0_comparisons.hpp
 )
 
diff --git a/tests/SelfTest/IntrospectiveTests/Algorithms.tests.cpp b/tests/SelfTest/IntrospectiveTests/Algorithms.tests.cpp
new file mode 100644
index 00000000..fa17cf82
--- /dev/null
+++ b/tests/SelfTest/IntrospectiveTests/Algorithms.tests.cpp
@@ -0,0 +1,94 @@
+
+//              Copyright Catch2 Authors
+// Distributed under the Boost Software License, Version 1.0.
+//   (See accompanying file LICENSE.txt or copy at
+//        https://www.boost.org/LICENSE_1_0.txt)
+
+// SPDX-License-Identifier: BSL-1.0
+
+#include <catch2/catch_test_macros.hpp>
+#include <catch2/internal/catch_is_permutation.hpp>
+
+#include <helpers/range_test_helpers.hpp>
+
+#include <array>
+
+namespace {
+    template <typename Range1, typename Range2>
+    static bool is_permutation(Range1 const& r1, Range2 const& r2) {
+        using std::begin; using std::end;
+        return Catch::Detail::is_permutation(
+            begin( r1 ), end( r1 ), begin( r2 ), end( r2 ), std::equal_to<>{} );
+    }
+}
+
+TEST_CASE("is_permutation", "[algorithms][approvals]") {
+    SECTION( "Handle empty ranges" ) {
+        std::array<int, 0> empty;
+        std::array<int, 2> non_empty{ { 2, 3 } };
+        REQUIRE( is_permutation( empty, empty ) );
+        REQUIRE_FALSE( is_permutation( empty, non_empty ) );
+        REQUIRE_FALSE( is_permutation( non_empty, empty ) );
+    }
+    SECTION( "Different length ranges" ) {
+        std::array<int, 6> arr1{ { 1, 3, 5, 7, 8, 9 } };
+        // arr2 is prefix of arr1
+        std::array<int, 4> arr2{ { 1, 3, 5, 7 } };
+        // arr3 shares prefix with arr1 and arr2, but is not a permutation
+        std::array<int, 5> arr3{ { 1, 3, 5, 9, 8 } };
+        REQUIRE_FALSE( is_permutation( arr1, arr2 ) );
+        REQUIRE_FALSE( is_permutation( arr1, arr3 ) );
+        REQUIRE_FALSE( is_permutation( arr2, arr3 ) );
+    }
+    SECTION( "Same length ranges" ) {
+        SECTION( "Shared elements, but different counts" ) {
+            const std::array<int, 6>
+                arr1{ { 1, 1, 1, 1, 2, 2 } },
+                arr2{ { 1, 1, 2, 2, 2, 2 } };
+            REQUIRE_FALSE( is_permutation( arr1, arr2 ) );
+        }
+        SECTION( "Identical ranges" ) {
+            const std::array<int, 6>
+                arr1{ { 1, 1, 1, 1, 2, 2 } },
+                arr2{ { 1, 1, 2, 2, 2, 2 } };
+            REQUIRE( is_permutation( arr1, arr1 ) );
+            REQUIRE( is_permutation( arr2, arr2 ) );
+        }
+        SECTION( "Completely distinct elements" ) {
+            // Completely distinct elements
+            const std::array<int, 4>
+                arr1{ { 1, 2, 3, 4 } },
+                arr2{ { 10, 20, 30, 40 } };
+            REQUIRE_FALSE( is_permutation( arr1, arr2 ) );
+        }
+        SECTION( "Reverse ranges" ) {
+            const std::array<int, 5>
+                arr1{ { 1, 2, 3, 4, 5 } },
+                arr2{ { 5, 4, 3, 2, 1 } };
+            REQUIRE( is_permutation( arr1, arr2 ) );
+        }
+        SECTION( "Shared prefix & permuted elements" ) {
+            const std::array<int, 5>
+                arr1{ { 1, 1, 2, 3, 4 } },
+                arr2{ { 1, 1, 4, 2, 3 } };
+            REQUIRE( is_permutation( arr1, arr2 ) );
+        }
+        SECTION( "Permutations with element count > 1" ) {
+            const std::array<int, 7>
+                arr1{ { 2, 2, 3, 3, 3, 1, 1 } },
+                arr2{ { 3, 2, 1, 3, 2, 1, 3 } };
+            REQUIRE( is_permutation( arr1, arr2 ) );
+        }
+    }
+}
+
+TEST_CASE("is_permutation supports iterator + sentinel pairs",
+          "[algorithms][is-permutation][approvals]") {
+    const has_different_begin_end_types<int>
+        range_1{ 1, 2, 3, 4 },
+        range_2{ 4, 3, 2, 1 };
+    REQUIRE( is_permutation( range_1, range_2 ) );
+
+    const has_different_begin_end_types<int> range_3{ 3, 3, 2, 1 };
+    REQUIRE_FALSE( is_permutation( range_1, range_3 ) );
+}
diff --git a/tests/SelfTest/UsageTests/MatchersRanges.tests.cpp b/tests/SelfTest/UsageTests/MatchersRanges.tests.cpp
index 4ca1ead8..651e84e6 100644
--- a/tests/SelfTest/UsageTests/MatchersRanges.tests.cpp
+++ b/tests/SelfTest/UsageTests/MatchersRanges.tests.cpp
@@ -15,195 +15,15 @@
 #include <catch2/matchers/catch_matchers_predicate.hpp>
 #include <catch2/matchers/catch_matchers_string.hpp>
 
+#include <helpers/range_test_helpers.hpp>
+
 #include <cmath>
-#include <initializer_list>
 #include <list>
 #include <map>
 #include <type_traits>
 #include <vector>
 #include <memory>
 
-namespace {
-
-namespace unrelated {
-    template <typename T>
-    class needs_ADL_begin {
-        std::vector<T> m_elements;
-    public:
-        using iterator = typename std::vector<T>::iterator;
-        using const_iterator = typename std::vector<T>::const_iterator;
-
-        needs_ADL_begin(std::initializer_list<T> init) : m_elements(init) {}
-
-        const_iterator Begin() const { return m_elements.begin(); }
-        const_iterator End() const { return m_elements.end(); }
-
-        friend const_iterator begin(needs_ADL_begin const& lhs) {
-            return lhs.Begin();
-        }
-        friend const_iterator end(needs_ADL_begin const& rhs) {
-            return rhs.End();
-        }
-    };
-} // end unrelated namespace
-
-#if defined(__clang__)
-#  pragma clang diagnostic push
-#  pragma clang diagnostic ignored "-Wunused-function"
-#endif
-
-template <typename T>
-class has_different_begin_end_types {
-    // Using std::vector<T> leads to annoying issues when T is bool
-    // so we just use list because the perf is not critical and ugh.
-    std::list<T> m_elements;
-
-    // Different type for the "end" iterator
-    struct iterator_end {};
-    // Fake-ish forward iterator that only compares to a different type
-    class iterator {
-        using underlying_iter = typename std::list<T>::const_iterator;
-        underlying_iter m_start;
-        underlying_iter m_end;
-
-    public:
-        iterator( underlying_iter start, underlying_iter end ):
-            m_start( start ), m_end( end ) {}
-
-        using iterator_category = std::forward_iterator_tag;
-        using difference_type = std::ptrdiff_t;
-        using value_type = T;
-        using const_reference = T const&;
-        using pointer = T const*;
-
-
-        friend bool operator==( iterator iter, iterator_end ) {
-            return iter.m_start == iter.m_end;
-        }
-        friend bool operator!=( iterator iter, iterator_end ) {
-            return iter.m_start != iter.m_end;
-        }
-        iterator& operator++() {
-            ++m_start;
-            return *this;
-        }
-        iterator operator++(int) {
-            auto tmp(*this);
-            ++m_start;
-            return tmp;
-        }
-        const_reference operator*() const {
-            return *m_start;
-        }
-        pointer operator->() const {
-            return m_start;
-        }
-    };
-
-
-public:
-    explicit has_different_begin_end_types( std::initializer_list<T> init ):
-        m_elements( init ) {}
-
-    iterator begin() const {
-        return { m_elements.begin(), m_elements.end() };
-    }
-
-    iterator_end end() const {
-        return {};
-    }
-};
-
-#if defined(__clang__)
-#  pragma clang diagnostic pop
-#endif
-
-template <typename T> struct with_mocked_iterator_access {
-    std::vector<T> m_elements;
-
-    // use plain arrays to have nicer printouts with CHECK(...)
-    mutable std::unique_ptr<bool[]> m_derefed;
-
-    // We want to check which elements were dereferenced when iterating, so
-    // we can check whether iterator-using code traverses range correctly
-    template <bool is_const> class basic_iterator {
-        template <typename U>
-        using constify_t = std::conditional_t<is_const, std::add_const_t<U>, U>;
-
-        constify_t<with_mocked_iterator_access>* m_origin;
-        size_t m_origin_idx;
-
-    public:
-        using iterator_category = std::forward_iterator_tag;
-        using difference_type = std::ptrdiff_t;
-        using value_type = constify_t<T>;
-        using const_reference = typename std::vector<T>::const_reference;
-        using reference = typename std::vector<T>::reference;
-        using pointer = typename std::vector<T>::pointer;
-
-        basic_iterator( constify_t<with_mocked_iterator_access>* origin,
-                        std::size_t origin_idx ):
-            m_origin{ origin }, m_origin_idx{ origin_idx } {}
-
-        friend bool operator==( basic_iterator lhs, basic_iterator rhs ) {
-            return lhs.m_origin == rhs.m_origin &&
-                   lhs.m_origin_idx == rhs.m_origin_idx;
-        }
-        friend bool operator!=( basic_iterator lhs, basic_iterator rhs ) {
-            return !( lhs == rhs );
-        }
-        basic_iterator& operator++() {
-            ++m_origin_idx;
-            return *this;
-        }
-        basic_iterator operator++( int ) {
-            auto tmp( *this );
-            ++( *this );
-            return tmp;
-        }
-        const_reference operator*() const {
-            assert( m_origin_idx < m_origin->m_elements.size() && "Attempted to deref invalid position" );
-            m_origin->m_derefed[m_origin_idx] = true;
-            return m_origin->m_elements[m_origin_idx];
-        }
-        pointer operator->() const {
-            assert( m_origin_idx < m_origin->m_elements.size() && "Attempted to deref invalid position" );
-            return &m_origin->m_elements[m_origin_idx];
-        }
-    };
-
-    using iterator = basic_iterator<false>;
-    using const_iterator = basic_iterator<true>;
-
-    with_mocked_iterator_access( std::initializer_list<T> init ):
-        m_elements( init ),
-        m_derefed( std::make_unique<bool[]>( m_elements.size() ) ) {}
-
-    const_iterator begin() const { return { this, 0 }; }
-    const_iterator end() const { return { this, m_elements.size() }; }
-    iterator begin() { return { this, 0 }; }
-    iterator end() { return { this, m_elements.size() }; }
-};
-
-} // end anon namespace
-
-namespace Catch {
-    // make sure with_mocked_iterator_access is not considered a range by Catch,
-    // so that below StringMaker is used instead of the default one for ranges
-    template <typename T>
-    struct is_range<with_mocked_iterator_access<T>> : std::false_type {};
-
-    template <typename T>
-    struct StringMaker<with_mocked_iterator_access<T>> {
-        static std::string
-        convert( with_mocked_iterator_access<T> const& access ) {
-            // We have to avoid the type's iterators, because we check
-            // their use in tests
-            return ::Catch::Detail::stringify( access.m_elements );
-        }
-    };
-} // namespace Catch
-
 struct MoveOnlyTestElement {
     int num = 0;
     MoveOnlyTestElement(int n) :num(n) {}
@@ -287,16 +107,6 @@ namespace {
         bool empty() const { return false; }
     };
 
-namespace unrelated {
-    struct ADL_empty {
-        bool Empty() const { return true; }
-
-        friend bool empty(ADL_empty e) {
-            return e.Empty();
-        }
-    };
-
-} // end namespace unrelated
 } // end unnamed namespace
 
 TEST_CASE("Basic use of the Empty range matcher", "[matchers][templated][empty]") {
@@ -346,17 +156,6 @@ namespace {
         return LessThanMatcher{ sz };
     }
 
-    namespace unrelated {
-        struct ADL_size {
-            size_t sz() const {
-                return 12;
-            }
-            friend size_t size(ADL_size s) {
-                return s.sz();
-            }
-        };
-    } // end namespace unrelated
-
     struct has_size {
         size_t size() const {
             return 13;
diff --git a/tests/SelfTest/helpers/range_test_helpers.hpp b/tests/SelfTest/helpers/range_test_helpers.hpp
new file mode 100644
index 00000000..22c2c3cd
--- /dev/null
+++ b/tests/SelfTest/helpers/range_test_helpers.hpp
@@ -0,0 +1,210 @@
+
+//              Copyright Catch2 Authors
+// Distributed under the Boost Software License, Version 1.0.
+//   (See accompanying file LICENSE.txt or copy at
+//        https://www.boost.org/LICENSE_1_0.txt)
+
+// SPDX-License-Identifier: BSL-1.0
+
+#ifndef CATCH_TEST_HELPERS_RANGE_TEST_HELPERS_HPP_INCLUDED
+#define CATCH_TEST_HELPERS_RANGE_TEST_HELPERS_HPP_INCLUDED
+
+#include <catch2/catch_tostring.hpp>
+
+#include <initializer_list>
+#include <list>
+#include <memory>
+#include <vector>
+
+namespace unrelated {
+    template <typename T>
+    class needs_ADL_begin {
+        std::vector<T> m_elements;
+
+    public:
+        using iterator = typename std::vector<T>::iterator;
+        using const_iterator = typename std::vector<T>::const_iterator;
+
+        needs_ADL_begin( std::initializer_list<T> init ): m_elements( init ) {}
+
+        const_iterator Begin() const { return m_elements.begin(); }
+        const_iterator End() const { return m_elements.end(); }
+
+        friend const_iterator begin( needs_ADL_begin const& lhs ) {
+            return lhs.Begin();
+        }
+        friend const_iterator end( needs_ADL_begin const& rhs ) {
+            return rhs.End();
+        }
+    };
+
+    struct ADL_empty {
+        bool Empty() const { return true; }
+
+        friend bool empty( ADL_empty e ) { return e.Empty(); }
+    };
+
+    struct ADL_size {
+        size_t sz() const { return 12; }
+        friend size_t size( ADL_size s ) { return s.sz(); }
+    };
+
+} // namespace unrelated
+
+#if defined( __clang__ )
+#    pragma clang diagnostic push
+#    pragma clang diagnostic ignored "-Wunused-function"
+#endif
+
+template <typename T>
+class has_different_begin_end_types {
+    // Using std::vector<T> leads to annoying issues when T is bool
+    // so we just use list because the perf is not critical and ugh.
+    std::list<T> m_elements;
+
+    // Different type for the "end" iterator
+    struct iterator_end {};
+    // Fake-ish forward iterator that only compares to a different type
+    class iterator {
+        using underlying_iter = typename std::list<T>::const_iterator;
+        underlying_iter m_start;
+        underlying_iter m_end;
+
+    public:
+        iterator( underlying_iter start, underlying_iter end ):
+            m_start( start ), m_end( end ) {}
+
+        using iterator_category = std::forward_iterator_tag;
+        using difference_type = std::ptrdiff_t;
+        using value_type = T;
+        using const_reference = T const&;
+        using pointer = T const*;
+
+        friend bool operator==( iterator iter, iterator_end ) {
+            return iter.m_start == iter.m_end;
+        }
+        friend bool operator==(iterator lhs, iterator rhs) {
+            return lhs.m_start == rhs.m_start && lhs.m_end == rhs.m_end;
+        }
+        friend bool operator!=( iterator iter, iterator_end ) {
+            return iter.m_start != iter.m_end;
+        }
+        friend bool operator!=( iterator lhs, iterator rhs ) {
+            return !( lhs == rhs );
+        }
+        iterator& operator++() {
+            ++m_start;
+            return *this;
+        }
+        iterator operator++( int ) {
+            auto tmp( *this );
+            ++m_start;
+            return tmp;
+        }
+        const_reference operator*() const { return *m_start; }
+        pointer operator->() const { return m_start; }
+    };
+
+public:
+    explicit has_different_begin_end_types( std::initializer_list<T> init ):
+        m_elements( init ) {}
+
+    iterator begin() const { return { m_elements.begin(), m_elements.end() }; }
+
+    iterator_end end() const { return {}; }
+};
+
+#if defined( __clang__ )
+#    pragma clang diagnostic pop
+#endif
+
+template <typename T>
+struct with_mocked_iterator_access {
+    std::vector<T> m_elements;
+
+    // use plain arrays to have nicer printouts with CHECK(...)
+    mutable std::unique_ptr<bool[]> m_derefed;
+
+    // We want to check which elements were dereferenced when iterating, so
+    // we can check whether iterator-using code traverses range correctly
+    template <bool is_const>
+    class basic_iterator {
+        template <typename U>
+        using constify_t = std::conditional_t<is_const, std::add_const_t<U>, U>;
+
+        constify_t<with_mocked_iterator_access>* m_origin;
+        size_t m_origin_idx;
+
+    public:
+        using iterator_category = std::forward_iterator_tag;
+        using difference_type = std::ptrdiff_t;
+        using value_type = constify_t<T>;
+        using const_reference = typename std::vector<T>::const_reference;
+        using reference = typename std::vector<T>::reference;
+        using pointer = typename std::vector<T>::pointer;
+
+        basic_iterator( constify_t<with_mocked_iterator_access>* origin,
+                        std::size_t origin_idx ):
+            m_origin{ origin }, m_origin_idx{ origin_idx } {}
+
+        friend bool operator==( basic_iterator lhs, basic_iterator rhs ) {
+            return lhs.m_origin == rhs.m_origin &&
+                   lhs.m_origin_idx == rhs.m_origin_idx;
+        }
+        friend bool operator!=( basic_iterator lhs, basic_iterator rhs ) {
+            return !( lhs == rhs );
+        }
+        basic_iterator& operator++() {
+            ++m_origin_idx;
+            return *this;
+        }
+        basic_iterator operator++( int ) {
+            auto tmp( *this );
+            ++( *this );
+            return tmp;
+        }
+        const_reference operator*() const {
+            assert( m_origin_idx < m_origin->m_elements.size() &&
+                    "Attempted to deref invalid position" );
+            m_origin->m_derefed[m_origin_idx] = true;
+            return m_origin->m_elements[m_origin_idx];
+        }
+        pointer operator->() const {
+            assert( m_origin_idx < m_origin->m_elements.size() &&
+                    "Attempted to deref invalid position" );
+            return &m_origin->m_elements[m_origin_idx];
+        }
+    };
+
+    using iterator = basic_iterator<false>;
+    using const_iterator = basic_iterator<true>;
+
+    with_mocked_iterator_access( std::initializer_list<T> init ):
+        m_elements( init ),
+        m_derefed( std::make_unique<bool[]>( m_elements.size() ) ) {}
+
+    const_iterator begin() const { return { this, 0 }; }
+    const_iterator end() const { return { this, m_elements.size() }; }
+    iterator begin() { return { this, 0 }; }
+    iterator end() { return { this, m_elements.size() }; }
+};
+
+
+namespace Catch {
+    // make sure with_mocked_iterator_access is not considered a range by Catch,
+    // so that below StringMaker is used instead of the default one for ranges
+    template <typename T>
+    struct is_range<with_mocked_iterator_access<T>> : std::false_type {};
+
+    template <typename T>
+    struct StringMaker<with_mocked_iterator_access<T>> {
+        static std::string
+        convert( with_mocked_iterator_access<T> const& access ) {
+            // We have to avoid the type's iterators, because we check
+            // their use in tests
+            return ::Catch::Detail::stringify( access.m_elements );
+        }
+    };
+} // namespace Catch
+
+#endif // CATCH_TEST_HELPERS_RANGE_TEST_HELPERS_HPP_INCLUDED
diff --git a/tests/meson.build b/tests/meson.build
index c8bdfb4b..f525f041 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -9,6 +9,7 @@
 # Please keep these ordered alphabetically
 self_test_sources = files(
   'SelfTest/helpers/parse_test_spec.cpp',
+  'SelfTest/IntrospectiveTests/Algorithms.tests.cpp',
   'SelfTest/IntrospectiveTests/Clara.tests.cpp',
   'SelfTest/IntrospectiveTests/CmdLine.tests.cpp',
   'SelfTest/IntrospectiveTests/CmdLineHelpers.tests.cpp',