[libcxx] adds `complexity_iterator`, `complexity_invocable`, and `test_algorithm`

[cjdb]

Summary

complexity_iterator is an iterator adaptor that's used to measure
the number of applications of a predicate/projection when there's no
predicate to measure (e.g. ranges::find).

complexity_invocable is an invocable adaptor that's used to measure
the number of calls to a predicate or projection. It differs from
unary_counting_predicate and binary_counting_predicate in two
ways:

1. Most importantly, it isn't limited to predicates, and so works with invocables returning something other than Boolean values.
2. It can store lambdas and works in constexpr contexts (this is secondary, but worth noting).

test_algorithm is an overload set that simplifies individual algorithm
test files. While working implementing ranges::lower_bound, I realised
that all test cases follow a strict pattern, for all implemented algos so
far (sometimes it can be simplified):

1. set up subrange
2. set up complexity instrumentation
3. get iterator result
4. check iterator result
5. check complexity results
6. reset subrange (if input iterators allowed)
7. reset complexity instrumentation
8. check range result matches iterator result
9. check complexity results

A lot of this code can be factored out. In particular, this commit
abstracts away all the set-up and complexity-check stages. This in
turn elides the reset stages, individual leaving tests to focus on:

1. get iterator result
2. check iterator result
3. check range result matches iterator result

An optional step 2.5 might creep in, where we check complexity results
for special cases (i.e. cases where that activate certain
optimisations).

The test_algorithm overload set isn't complete yet, but remaining
overloads can be added on an as-needed basis.

Depends on D105205.

[cjdb]

D105795 is an example of test_algorithm in action.

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[cjdb]

rebasing to activate CI

[ldionne]

I would suggest that you move complexity_iterator to the ranges::find patch so that it's added in the same patch that starts using it.

libcxx/test/support/test_iterators.h

1055

Remove [[nodiscard]]?

1084

This isn't needed, I think the default CTAD should work?

[cjdb]

In D105791#2898081, @ldionne wrote:

I would suggest that you move complexity_iterator to the ranges::find patch so that it's added in the same patch that starts using it.

Ack. Should I move the complexity_invocable stuff to the first algorithm patch it's used in too? Then we just need to make a decision about the test_algorithm stuff, and I'll inject where it's necessary so D105791 can be abandoned :)

[ldionne]

In D105791#2898198, @cjdb wrote:

In D105791#2898081, @ldionne wrote:

I would suggest that you move complexity_iterator to the ranges::find patch so that it's added in the same patch that starts using it.

Ack. Should I move the complexity_invocable stuff to the first algorithm patch it's used in too? Then we just need to make a decision about the test_algorithm stuff, and I'll inject where it's necessary so D105791 can be abandoned :)

Yup, that would be my preference!

[cjdb]

• complexity_iterator and complexity_invocable subsumed by D105456.
• Abandoning test_algorithm since the feedback from ranges::find introduced a lot of complexity I don't want to add.

libcxx/test/support/test_algorithm.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
+//
+//===----------------------------------------------------------------------===//
+#ifndef LIBCXX_TEST_SUPPORT_TEST_ALGORITHM_H
+#define LIBCXX_TEST_SUPPORT_TEST_ALGORITHM_H
+
+#include "test_macros.h"
+
+#if TEST_STD_VER < 20
+#error This file requires -std=c++20 or later.
+#endif
+
+#include <cassert>
+#include <concepts>
+#include <cstddef>
+#include <functional>
+#include <ranges>
+#include <utility>
+#include <type_traits>
+
+#include "counting_predicates.h"
+#include "test_iterators.h"
+
+template<class F>
+class complexity_invocable {
+public:
+  constexpr complexity_invocable(F f)
+  : f_(std::move(f))
+  {}
+
+  template<class... Args>
+  requires std::invocable<F&, Args...>
+  constexpr decltype(auto) operator()(Args&&... args) noexcept(std::is_nothrow_invocable_v<F, Args...>)
+  {
+    ++count_;
+    return std::invoke(f_, std::forward<Args>(args)...);
+  }
+
+  constexpr std::ptrdiff_t count() const
+  {
+    return count_;
+  }
+private:
+  F f_;
+  std::ptrdiff_t count_ = 0;
+};
+
+// This must be defined in each test case.
+template<std::ranges::range R>
+constexpr void check_complexity(R&& r, std::ptrdiff_t x);
+
+template<template<class...> class I, std::ranges::range R, class Case>
+constexpr void test_algorithm(R&& r, Case test_case) {
+  auto input = std::ranges::subrange(complexity_iterator(I(r.begin())), sentinel_wrapper(r.end()));
+  test_case(input);
+
+  check_complexity(r, input.begin().count());
+}
+
+template<template<class...> class I, std::ranges::range R, class F1, class Case>
+constexpr void test_algorithm(R&& r, F1 f1, Case test_case) {
+  auto input = std::ranges::subrange(I(r.begin()), sentinel_wrapper(r.end()));
+  auto instrumented_f1 = complexity_invocable(f1);
+  test_case(input, instrumented_f1);
+
+  check_complexity(r, instrumented_f1.count());
+}
+
+template<template<class...> class I, std::ranges::range R, class F1, class Proj, class Case>
+constexpr void test_algorithm(R&& r, F1 f1, Proj proj, Case test_case) {
+  auto input = std::ranges::subrange(I(r.begin()), sentinel_wrapper(r.end()));
+  auto instrumented_f1 = complexity_invocable(f1);
+  auto instrumented_proj = complexity_invocable(proj);
+  test_case(input, instrumented_f1, instrumented_proj);
+
+  check_complexity(r, instrumented_f1.count());
+  check_complexity(r, instrumented_proj.count());
+}
+
+constexpr std::ptrdiff_t libcxx_log2(std::ptrdiff_t const x) {
+  assert(x > 0);
+  auto n = std::ptrdiff_t(0);
+  for (auto i = std::ptrdiff_t(1); i <= x; i *= 2) {
+    ++n;
+  }
+  return n - 1;
+}
+static_assert(libcxx_log2(1) == 0);
+static_assert(libcxx_log2(2) == 1);
+static_assert(libcxx_log2(3) == 1);
+static_assert(libcxx_log2(4) == 2);
+static_assert(libcxx_log2(6) == 2);
+static_assert(libcxx_log2(7) == 2);
+static_assert(libcxx_log2(8) == 3);
+static_assert(libcxx_log2(13) == 3);
+static_assert(libcxx_log2(15) == 3);
+static_assert(libcxx_log2(16) == 4);
+static_assert(libcxx_log2(22) == 4);
+static_assert(libcxx_log2(31) == 4);
+static_assert(libcxx_log2(32) == 5);
+static_assert(libcxx_log2(54) == 5);
+static_assert(libcxx_log2(63) == 5);
+
+#endif // LIBCXX_TEST_SUPPORT_TEST_ALGORITHM_H

libcxx/test/support/test_iterators.h

public:
     friend TEST_CONSTEXPR_CXX14
     difference_type operator-(const three_way_contiguous_iterator& x, const three_way_contiguous_iterator& y) {
         return x.base() - y.base();
     }
 
     friend auto operator<=>(const three_way_contiguous_iterator&, const three_way_contiguous_iterator&) = default;
 };
 
+template<std::input_iterator I>
+class complexity_iterator {
+public:
+  using value_type = std::iter_value_t<I>;
+  using difference_type = std::iter_difference_t<I>;
+  using iterator_concept = iterator_concept_t<I>;
+
+  constexpr complexity_iterator() requires std::default_initializable<I> = default;
+
+  constexpr explicit complexity_iterator(I i)
+  : base_(std::move(i))
+  {}
+
+  [[nodiscard]] constexpr difference_type count() const
+  {
+    return dereference_count_;
+  }
+
+  constexpr I const& base() const&
+  {
+    return base_;
+  }
+
+  constexpr I base() &&
+  {
+    return std::move(base_);
+  }
+
+  constexpr std::iter_reference_t<I> operator*() const
+  {
+    ++dereference_count_;
+    return *base_;
+  }
+
+  constexpr std::iter_reference_t<I> operator[](difference_type const n) const
+  requires std::random_access_iterator<I>
+  {
+    ++dereference_count_;
+    return base_[n];
+  }
+
+  constexpr complexity_iterator& operator++()
+  {
+    ++base_;
+    return *this;
+  }
+
+  constexpr void operator++(int) { ++*this; }
+
+  constexpr complexity_iterator operator++(int)
+  requires std::forward_iterator<I>
+  {
+    auto temp = *this;
+    ++*this;
+    return temp;
+  }
+
+  constexpr complexity_iterator& operator--()
+  requires std::bidirectional_iterator<I>
+  {
+    --base_;
+    return *this;
+  }
+
+  constexpr complexity_iterator operator--(int)
+  requires std::bidirectional_iterator<I>
+  {
+    auto temp = *this;
+    --*this;
+    return temp;
+  }
+
+  constexpr complexity_iterator& operator+=(difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    base_ += n;
+    return *this;
+  }
+
+  constexpr complexity_iterator& operator-=(difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    base_ -= n;
+    return *this;
+  }
+
+  constexpr friend complexity_iterator operator+(complexity_iterator i, difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    return i += n;
+  }
+
+  constexpr friend complexity_iterator operator+(difference_type const n, complexity_iterator i)
+  requires std::random_access_iterator<I>
+  {
+    return i += n;
+  }
+
+  constexpr friend complexity_iterator operator-(complexity_iterator i, difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    return i -= n;
+  }
+
+  constexpr friend difference_type operator-(complexity_iterator const& x, complexity_iterator const& y)
+  requires std::sized_sentinel_for<I, I>
+  {
+    return x - y;
+  }
+
+  constexpr bool operator==(complexity_iterator const& other) const requires std::sentinel_for<I, I>
+  {
+    return base_ == other.base_;
+  }
+
+  template<std::sentinel_for<I> S>
+  constexpr bool operator==(S const last) const
+  {
+      return base_ == last;
+  }
+
+  [[nodiscard]] constexpr friend bool operator<(complexity_iterator const& x, complexity_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return x.base_ < y.base_;
+  }
+
+  constexpr friend bool operator>(complexity_iterator const& x, complexity_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return y < x;
+  }
+
+  constexpr friend bool operator<=(complexity_iterator const& x, complexity_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return !(y < x);
+  }
+
+  constexpr friend bool operator>=(complexity_iterator const& x, complexity_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return !(x < y);
+  }
+private:
+  I base_;
+  mutable difference_type dereference_count_ = 0;
+};
+
+template<class I>
+complexity_iterator(I) -> complexity_iterator<I>;
+
 // clang-format on
 
 #endif // TEST_STD_VER > 17 && defined(__cpp_lib_concepts)
 
 #undef DELETE_FUNCTION
 
 #endif // ITERATORS_H