llvm/pstl/test/support/utils.h

// -*- C++ -*-
//===-- utils.h -----------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

// File contains common utilities that tests rely on

// Do not #include <algorithm>, because if we do we will not detect accidental dependencies.
#include <atomic>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <iterator>
#include <memory>
#include <sstream>
#include <vector>

#include "pstl_test_config.h"

namespace TestUtils
{

float64_t;
float32_t;

template <class T, std::size_t N>
constexpr size_t
const_size(const T (&)[N]) noexcept
{ … }

template <typename T>
class Sequence;

// Handy macros for error reporting
#define EXPECT_TRUE(condition, message) …
#define EXPECT_FALSE(condition, message) …

// Check that expected and actual are equal and have the same type.
#define EXPECT_EQ(expected, actual, message) …

// Check that sequences started with expected and actual and have had size n are equal and have the same type.
#define EXPECT_EQ_N(expected, actual, n, message) …

// Issue error message from outstr, adding a newline.
// Real purpose of this routine is to have a place to hang a breakpoint.
inline void
issue_error_message(std::stringstream& outstr)
{ … }

inline void
expect(bool expected, bool condition, const char* file, int32_t line, const char* message)
{ … }

// Do not change signature to const T&.
// Function must be able to detect const differences between expected and actual.
template <typename T>
void
expect_equal(T& expected, T& actual, const char* file, int32_t line, const char* message)
{ … }

template <typename T>
void
expect_equal(Sequence<T>& expected, Sequence<T>& actual, const char* file, int32_t line, const char* message)
{ … }

template <typename Iterator1, typename Iterator2, typename Size>
void
expect_equal(Iterator1 expected_first, Iterator2 actual_first, Size n, const char* file, int32_t line,
             const char* message)
{ … }

// ForwardIterator is like type Iterator, but restricted to be a forward iterator.
// Only the forward iterator signatures that are necessary for tests are present.
// Post-increment in particular is deliberatly omitted since our templates should avoid using it
// because of efficiency considerations.
template <typename Iterator, typename IteratorTag>
class ForwardIterator
{ … };

template <typename Iterator, typename IteratorTag>
class BidirectionalIterator : public ForwardIterator<Iterator, IteratorTag>
{ … };

template <typename Iterator, typename F>
void
fill_data(Iterator first, Iterator last, F f)
{ … }

struct MemoryChecker { … };

std::atomic<std::int64_t> MemoryChecker::alive_object_counter{ … };

std::ostream& operator<<(std::ostream& os, const MemoryChecker& val) { … }
bool operator==(const MemoryChecker& v1, const MemoryChecker& v2) { … }
bool operator<(const MemoryChecker& v1, const MemoryChecker& v2) { … }

// Sequence<T> is a container of a sequence of T with lots of kinds of iterators.
// Prefixes on begin/end mean:
//      c = "const"
//      f = "forward"
// No prefix indicates non-const random-access iterator.
template <typename T>
class Sequence
{ … };

template <typename T>
void
Sequence<T>::print() const
{ … }

// Predicates for algorithms
template <typename DataType>
struct is_equal_to
{ … };

// Low-quality hash function, returns value between 0 and (1<<bits)-1
// Warning: low-order bits are quite predictable.
inline size_t
HashBits(size_t i, size_t bits)
{ … }

// Stateful unary op
template <typename T, typename U>
class Complement
{ … };

// Tag used to prevent accidental use of converting constructor, even if use is explicit.
struct OddTag
{ … };

class Sum;

// Type with limited set of operations.  Not default-constructible.
// Only available operator is "==".
// Typically used as value type in tests.
class Number
{ … };

// Stateful predicate for Number.  Not default-constructible.
class IsMultiple
{ … };

// Stateful equivalence-class predicate for Number.  Not default-constructible.
class Congruent
{ … };

// Stateful reduction operation for Number
class Add
{ … };

// Class similar to Number, but has default constructor and +.
class Sum : public Number
{ … };

// Type with limited set of operations, which includes an associative but not commutative operation.
// Not default-constructible.
// Typically used as value type in tests involving "GENERALIZED_NONCOMMUTATIVE_SUM".
class MonoidElement
{ … };

// Stateful associative op for MonoidElement
// It's not really a monoid since the operation is not allowed for any two elements.
// But it's good enough for testing.
class AssocOp
{ … };

// Multiplication of matrix is an associative but not commutative operation
// Typically used as value type in tests involving "GENERALIZED_NONCOMMUTATIVE_SUM".
template <typename T>
struct Matrix2x2
{ … };

template <typename T>
bool
operator==(const Matrix2x2<T>& left, const Matrix2x2<T>& right)
{ … }

template <typename T>
Matrix2x2<T>
multiply_matrix(const Matrix2x2<T>& left, const Matrix2x2<T>& right)
{ … }

//============================================================================
// Adapters for creating different types of iterators.
//
// In this block we implemented some adapters for creating differnet types of iterators.
// It's needed for extending the unit testing of Parallel STL algorithms.
// We have adapters for iterators with different tags (forward_iterator_tag, bidirectional_iterator_tag), reverse iterators.
// The input iterator should be const or non-const, non-reverse random access iterator.
// Iterator creates in "MakeIterator":
// firstly, iterator is "packed" by "IteratorTypeAdapter" (creating forward or bidirectional iterator)
// then iterator is "packed" by "ReverseAdapter" (if it's possible)
// So, from input iterator we may create, for example, reverse bidirectional iterator.
// "Main" functor for testing iterators is named "invoke_on_all_iterator_types".

// Base adapter
template <typename Iterator>
struct BaseAdapter
{ … };

// Check if the iterator is reverse iterator
// Note: it works only for iterators that created by std::reverse_iterator
template <typename NotReverseIterator>
struct isReverse : std::false_type
{ … };

isReverse<std::reverse_iterator<Iterator>>;

// Reverse adapter
template <typename Iterator, typename IsReverse>
struct ReverseAdapter
{ … };

// Non-reverse adapter
ReverseAdapter<Iterator, std::false_type>;

// Iterator adapter by type (by default std::random_access_iterator_tag)
template <typename Iterator, typename IteratorTag>
struct IteratorTypeAdapter : BaseAdapter<Iterator>
{ … };

// Iterator adapter for forward iterator
IteratorTypeAdapter<Iterator, std::forward_iterator_tag>;

// Iterator adapter for bidirectional iterator
IteratorTypeAdapter<Iterator, std::bidirectional_iterator_tag>;

//For creating iterator with new type
template <typename InputIterator, typename IteratorTag, typename IsReverse>
struct MakeIterator
{ … };

// Useful constant variables
constexpr std::size_t GuardSize = …;
constexpr std::ptrdiff_t sizeLimit = …;

template <typename Iter, typename Void = void> // local iterator_traits for non-iterators
struct iterator_traits_
{ … };

iterator_traits_<Iter, typename std::enable_if<!std::is_void<typename Iter::iterator_category>::value, void>::type>;

template <typename T> // For pointers
struct iterator_traits_<T*>
{
    typedef std::random_access_iterator_tag iterator_category;
};

// is iterator Iter has tag Tag
template <typename Iter, typename Tag>
using is_same_iterator_category = std::is_same<typename iterator_traits_<Iter>::iterator_category, Tag>;

// if we run with reverse or const iterators we shouldn't test the large range
template <typename IsReverse, typename IsConst>
struct invoke_if_
{ … };
template <>
struct invoke_if_<std::false_type, std::false_type>
{ … };

// Base non_const_wrapper struct. It is used to distinguish non_const testcases
// from a regular one. For non_const testcases only compilation is checked.
struct non_const_wrapper
{ … };

// Generic wrapper to specify iterator type to execute callable Op on.
// The condition can be either positive(Op is executed only with IteratorTag)
// or negative(Op is executed with every type of iterators except IteratorTag)
template <typename Op, typename IteratorTag, bool IsPositiveCondition = true>
struct non_const_wrapper_tagged : non_const_wrapper
{ … };

// These run_for_* structures specify with which types of iterators callable object Op
// should be executed.
template <typename Op>
struct run_for_rnd : non_const_wrapper_tagged<Op, std::random_access_iterator_tag>
{ … };

template <typename Op>
struct run_for_rnd_bi : non_const_wrapper_tagged<Op, std::forward_iterator_tag, false>
{ … };

template <typename Op>
struct run_for_rnd_fw : non_const_wrapper_tagged<Op, std::bidirectional_iterator_tag, false>
{ … };

// Invoker for different types of iterators.
template <typename IteratorTag, typename IsReverse>
struct iterator_invoker
{ … };

// Invoker for reverse iterators only
// Note: if we run with reverse iterators we shouldn't test the large range
iterator_invoker<IteratorTag, std::true_type>;

// We can't create reverse iterator from forward iterator
template <>
struct iterator_invoker<std::forward_iterator_tag, /*isReverse=*/std::true_type>
{ … };

template <typename IsReverse>
struct reverse_invoker
{ … };

struct invoke_on_all_iterator_types
{ … };
//============================================================================

// Invoke op(policy,rest...) for each possible policy.
template <typename Op, typename... T>
void
invoke_on_all_policies(Op op, T&&... rest)
{ … }

template <typename F>
struct NonConstAdapter
{ … };

template <typename F>
NonConstAdapter<F>
non_const(const F& f)
{ … }

// Wrapper for types. It's need for counting of constructing and destructing objects
template <typename T>
class Wrapper
{ … };

template <typename T>
std::atomic<size_t> Wrapper<T>::my_count = …;

template <typename T>
std::atomic<size_t> Wrapper<T>::move_count = …;

template <typename InputIterator, typename T, typename BinaryOperation, typename UnaryOperation>
T
transform_reduce_serial(InputIterator first, InputIterator last, T init, BinaryOperation binary_op,
                        UnaryOperation unary_op) noexcept
{ … }

static const char*
done()
{ … }

// test_algo_basic_* functions are used to execute
// f on a very basic sequence of elements of type T.

// Should be used with unary predicate
template <typename T, typename F>
static void
test_algo_basic_single(F&& f)
{ … }

// Should be used with binary predicate
template <typename T, typename F>
static void
test_algo_basic_double(F&& f)
{ … }

template <typename Policy, typename F>
static void
invoke_if(Policy&&, F f)
{ … }

} /* namespace TestUtils */