ConstantExpressions.hpp
Go to the documentation of this file.
1 // Distributed under the MIT License.
2 // See LICENSE.txt for details.
3 
4 /// \file
5 /// Define simple functions for constant expressions.
6 
7 #pragma once
8 
9 #include <algorithm>
10 #include <array>
11 #include <blaze/math/typetraits/IsVector.h> // IWYU pragma: keep
12 #include <cassert>
13 #include <cstddef>
14 #include <cstdint>
15 #include <functional>
16 #include <initializer_list>
17 #include <utility>
18 
21 #include "Utilities/Requires.hpp"
22 #include "Utilities/TMPL.hpp"
23 #include "Utilities/TypeTraits.hpp"
24 
25 // IWYU pragma: no_include "DataStructures/DataVector.hpp"
26 
27 /// \ingroup ConstantExpressionsGroup
28 /// Compute 2 to the n for integral types.
29 ///
30 /// \param n the power of two to compute.
31 /// \return 2^n
32 template <typename T,
33  Requires<tt::is_integer_v<T> and cpp17::is_unsigned_v<T>> = nullptr>
35  return T(1) << n;
36 }
37 
38 /// \ingroup ConstantExpressionsGroup
39 /// Get the nth bit from the right, counting from zero.
40 ///
41 /// \param i the value to be acted on.
42 /// \param N which place to extract the bit
43 /// \return the value of the bit at that place.
44 SPECTRE_ALWAYS_INLINE constexpr size_t get_nth_bit(const size_t i,
45  const size_t N) {
46  return (i >> N) % 2;
47 }
48 
49 /// \ingroup ConstantExpressionsGroup
50 /// \brief Compute the square of `x`
51 template <typename T>
52 SPECTRE_ALWAYS_INLINE constexpr decltype(auto) square(const T& x) {
53  return x * x;
54 }
55 
56 /// \ingroup ConstantExpressionsGroup
57 /// \brief Compute the cube of `x`
58 template <typename T>
59 SPECTRE_ALWAYS_INLINE constexpr decltype(auto) cube(const T& x) {
60  return x * x * x;
61 }
62 
63 /*!
64  * \ingroup ConstantExpressionsGroup
65  * \brief Compute the falling factorial of \f$(x)_{n}\f$
66  *
67  * See http://mathworld.wolfram.com/FallingFactorial.html
68  * \note The largest representable factorial is 20!. It is up to the user to
69  * ensure this is satisfied
70  */
71 constexpr uint64_t falling_factorial(const uint64_t x,
72  const uint64_t n) noexcept {
73  // clang-tidy: don't warn about STL internals, I can't fix them
74  assert(n <= x); // NOLINT
75  uint64_t r = 1;
76  for (uint64_t k = 0; k < n; ++k) {
77  r *= (x - k);
78  }
79  return r;
80 }
81 
82 /*!
83  * \ingroup ConstantExpressionsGroup
84  * \brief Compute the factorial of \f$n!\f$
85  */
86 constexpr uint64_t factorial(const uint64_t n) noexcept {
87  assert(n <= 20); // NOLINT
88  return falling_factorial(n, n);
89 }
90 
91 /// \ingroup ConstantExpressionsGroup
93 
94 // Implementation functions for the pow template function below which computes
95 // optimized powers where the exponent is a compile-time integer
96 
97 // base case power 0: Returns 1.0. This will need to be overloaded for types for
98 // which the simple return is inappropriate.
99 template <typename T>
100 SPECTRE_ALWAYS_INLINE constexpr decltype(auto) pow_impl(
101  const T& /*t*/, std::integral_constant<int, 0> /*meta*/,
102  cpp17::bool_constant<true> /*exponent_was_positive*/) noexcept {
103  return static_cast<tt::get_fundamental_type_t<T>>(1.0);
104 }
105 
106 // special case power 1: acts as a direct identity function for efficiency
107 template <typename T>
108 SPECTRE_ALWAYS_INLINE constexpr decltype(auto) pow_impl(
109  const T& t, std::integral_constant<int, 1> /*meta*/,
110  cpp17::bool_constant<true> /*exponent_was_positive*/) noexcept {
111  return t;
112 }
113 
114 // general case for positive powers: return the power via recursive inline call,
115 // which expands to a series of multiplication operations.
116 template <int N, typename T>
117 SPECTRE_ALWAYS_INLINE constexpr decltype(auto) pow_impl(
118  const T& t, std::integral_constant<int, N> /*meta*/,
119  cpp17::bool_constant<true> /*exponent_was_positive*/) noexcept {
120  return t * pow_impl(t, std::integral_constant<int, N - 1>{},
122 }
123 
124 // general case for negative powers: return the multiplicative inverse of the
125 // result from the recursive inline call, which expands to a series of
126 // multiplication operations. This assumes that division is supported with
127 // tt::get_fundamental_type_t<T> and T. If not, this utility will need further
128 // specialization.
129 template <int N, typename T>
130 SPECTRE_ALWAYS_INLINE constexpr decltype(auto) pow_impl(
131  const T& t, std::integral_constant<int, N> /*meta*/,
132  cpp17::bool_constant<false> /*exponent_was_positive*/) noexcept {
133  return static_cast<tt::get_fundamental_type_t<T>>(1) /
134  (pow_impl(t, std::integral_constant<int, -N>{},
136 }
137 } // namespace ConstantExpressions_detail
138 
139 /// \ingroup ConstantExpressionsGroup
140 /// \brief Compute t^N where N is an integer (positive or negative)
141 ///
142 /// \warning If passing an integer this will do integer arithmetic, e.g.
143 /// `pow<-10>(2) == 0` evaluates to `true`
144 ///
145 /// \warning For optimization, it is assumed that the `pow<0>` of a vector type
146 /// (e.g. `DataVector`) will not be used for initialization or directly indexed,
147 /// so `pow<0>` returns simply `1.0`. In the case of use for initialization, a
148 /// constructor should be used instead, and in the case of a direct index, the
149 /// expression may be simplifyable to avoid the use of `pow<0>` altogether. If a
150 /// more complete treatment of `pow<0>` is required, further overloads may be
151 /// added to the `ConstantExpressions_detail` namespace.
152 ///
153 /// \tparam N the integer power being raised to in \f$t^N\f$
154 /// \param t the value being exponentiated
155 /// \return value \f$t^N\f$ determined via repeated multiplication
156 template <int N, typename T>
157 SPECTRE_ALWAYS_INLINE constexpr decltype(auto) pow(const T& t) noexcept {
158  return ConstantExpressions_detail::pow_impl(
160 }
161 
162 /// \ingroup ConstantExpressionsGroup
163 /// \brief Compute the absolute value of of its argument
164 ///
165 /// The argument must be comparable to an int and must be negatable.
166 template <typename T, Requires<tt::is_integer_v<T> or
167  cpp17::is_floating_point_v<T>> = nullptr>
168 SPECTRE_ALWAYS_INLINE constexpr T ce_abs(const T& x) noexcept(
169  noexcept(x < 0 ? -x : x)) {
170  return x < 0 ? -x : x;
171 }
172 
173 /// \cond
174 template <>
175 SPECTRE_ALWAYS_INLINE constexpr double ce_abs(const double& x) noexcept {
176  return __builtin_fabs(x);
177 }
178 
179 template <>
180 SPECTRE_ALWAYS_INLINE constexpr float ce_abs(const float& x) noexcept {
181  return __builtin_fabsf(x);
182 }
183 /// \endcond
184 
185 /// \ingroup ConstantExpressionsGroup
186 /// \brief Compute the absolute value of its argument
187 constexpr SPECTRE_ALWAYS_INLINE double ce_fabs(const double x) noexcept {
188  return __builtin_fabs(x);
189 }
190 
191 constexpr SPECTRE_ALWAYS_INLINE float ce_fabs(const float x) noexcept {
192  return __builtin_fabsf(x);
193 }
194 
195 namespace ConstantExpressions_detail {
196 struct CompareByMagnitude {
197  template <typename T>
198  constexpr bool operator()(const T& a, const T& b) {
199  return ce_abs(a) < ce_abs(b);
200  }
201 };
202 } // namespace ConstantExpressions_detail
203 
204 /// \ingroup ConstantExpressionsGroup
205 /// \brief Return the argument with the largest magnitude
206 ///
207 /// Magnitude is determined by constexpr_abs. In case of a tie,
208 /// returns the leftmost of the tied values.
209 //@{
210 template <typename T>
211 constexpr const T& max_by_magnitude(const T& a, const T& b) {
212  return std::max(a, b, ConstantExpressions_detail::CompareByMagnitude{});
213 }
214 
215 template <typename T>
217  return std::max(std::move(ilist),
218  ConstantExpressions_detail::CompareByMagnitude{});
219 }
220 //@}
221 
222 /// \ingroup ConstantExpressionsGroup
223 /// \brief Return the argument with the smallest magnitude
224 ///
225 /// Magnitude is determined by constexpr_abs. In case of a tie,
226 /// returns the leftmost of the tied values.
227 //@{
228 template <typename T>
229 constexpr const T& min_by_magnitude(const T& a, const T& b) {
230  return std::min(a, b, ConstantExpressions_detail::CompareByMagnitude{});
231 }
232 
233 template <typename T>
235  return std::min(std::move(ilist),
236  ConstantExpressions_detail::CompareByMagnitude{});
237 }
238 //@}
239 
240 namespace cpp17 {
241 /// \ingroup ConstantExpressionsGroup
242 /// \brief Clamps the value between lo and hi
243 ///
244 /// If v compares less than lo, returns lo; otherwise if hi compares less than
245 /// v, returns hi; otherwise returns v.
246 template <class T, class Compare = std::less<>>
247 constexpr const T& clamp(const T& v, const T& lo, const T& hi,
248  Compare comp = Compare()) {
249  // reason for NOLINT: the warning below occurs despite no instances of an
250  // array in the clamp calls. This warning occurs sometime during the assert
251  // macro expansion rather than being due to an implementation error.
252  // "warning: do not implicitly decay an array into a pointer; consider using
253  // gsl::array_view or an explicit cast instead
254  // [cppcoreguidelines-pro-bounds-array-to-pointer-decay]"
255  return assert(!comp(hi, lo)), // NOLINT
256  comp(v, lo) ? lo : comp(hi, v) ? hi : v;
257 }
258 } // namespace cpp17
259 
260 /// \ingroup ConstantExpressionsGroup
261 /// \brief Returns `f(ic<0>{}) + f(ic<1>{}) + ... + f(ic<NumTerms-1>{})`
262 /// where `ic<N>` stands for `std::integral_constant<size_t, N>`.
263 /// This function allows the result types of each operation to be
264 /// different, and so works efficiently with expression templates.
265 /// \note When summing expression templates one must be careful of
266 /// referring to temporaries in `f`.
267 template <size_t NumTerms, typename Function, Requires<NumTerms == 1> = nullptr>
268 constexpr decltype(auto) constexpr_sum(Function&& f) noexcept {
270 }
271 
272 /// \cond HIDDEN_SYMBOLS
273 template <size_t NumTerms, typename Function,
274  Requires<(NumTerms > 1)> = nullptr>
275 constexpr decltype(auto) constexpr_sum(Function&& f) noexcept {
276  return constexpr_sum<NumTerms - 1>(f) +
278 }
279 /// \endcond
280 
281 namespace detail {
282 template <typename List, size_t... indices,
285  tmpl::size<List>::value>
286  make_array_from_list_helper(
289  tmpl::size<List>::value>{
290  {tmpl::at<List, tmpl::size_t<indices>>::value...}};
291 }
292 } // namespace detail
293 
294 /// \ingroup ConstantExpressionsGroup
295 /// Make an array from a typelist that holds std::integral_constant's all of
296 /// which have the same `value_type`
297 ///
298 /// \tparam List the typelist of std::integral_constant's
299 /// \return array of integral values from the typelist
300 template <typename List,
302 inline constexpr auto make_array_from_list()
304  tmpl::size<List>::value> {
305  return detail::make_array_from_list_helper<List>(
307 }
308 
309 template <typename TypeForZero,
311 inline constexpr std::array<std::decay_t<TypeForZero>, 0>
313  return std::array<std::decay_t<TypeForZero>, 0>{{}};
314 }
315 
316 namespace detail {
317 template <typename List, size_t... indices,
319 inline constexpr std::array<
320  std::decay_t<
321  decltype(make_array_from_list<tmpl::at<List, tmpl::size_t<0>>>())>,
322  tmpl::size<List>::value>
323  make_array_from_list_helper(
326  tmpl::at<List, tmpl::size_t<0>>>())>,
327  tmpl::size<List>::value>{
328  {make_array_from_list_helper<tmpl::at<List, tmpl::size_t<indices>>>(
330  size_t,
331  tmpl::size<tmpl::at<List, tmpl::size_t<indices>>>::value>{})...}};
332 }
333 } // namespace detail
334 
335 /// \ingroup ConstantExpressionsGroup
336 ///
337 /// Make an array of arrays from a typelist that holds typelists of
338 /// std::integral_constant's all of which have the same `value_type`
339 ///
340 /// \tparam List the typelist of typelists of std::integral_constant's
341 /// \return array of arrays of integral values from the typelists
342 template <typename List,
344 inline constexpr auto make_array_from_list() {
345  return detail::make_array_from_list_helper<List>(
347 }
348 
349 /// \ingroup ConstantExpressionsGroup
350 /// \brief Compute the length of a const char* at compile time
352  const char* str) noexcept {
353  // clang-tidy: do not use pointer arithmetic
354  return *str != 0 ? 1 + cstring_length(str + 1) : 0; // NOLINT
355 }
356 
357 /// \ingroup ConstantExpressionsGroup
358 /// \brief Compute a hash of a const char* at compile time
359 SPECTRE_ALWAYS_INLINE constexpr size_t cstring_hash(const char* str) noexcept {
360  // clang-tidy: do not use pointer arithmetic
361  return *str != 0
362  ? (cstring_hash(str + 1) * 33) ^ // NOLINT
363  static_cast<size_t>(*str)
364  : 5381;
365 }
366 
367 namespace ConstantExpression_detail {
368 template <typename T, size_t Size, size_t... I, size_t... J>
369 inline constexpr std::array<std::decay_t<T>, Size> replace_at_helper(
370  const std::array<T, Size>& arr, const T& value, const size_t i,
373  // clang-tidy: Cannot use gsl::at because we want constexpr evaluation and
374  // Parallel::abort violates this
375  return std::array<std::decay_t<T>, Size>{
376  {arr[I]..., value, arr[i + J]...}}; // NOLINT
377 }
378 } // namespace ConstantExpression_detail
379 
380 /// \ingroup ConstantExpressionsGroup
381 /// Replace at compile time the `I`th entry in the array with `value`
382 template <size_t I, typename T, size_t Size>
383 inline constexpr std::array<std::decay_t<T>, Size> replace_at(
384  const std::array<T, Size>& arr, T value) {
385  return ConstantExpression_detail::replace_at_helper(
386  arr, std::forward<T>(value), I + 1,
388  std::make_integer_sequence<size_t, Size - I - 1>{});
389 }
390 
391 /// \ingroup ConstantExpressionsGroup
392 /// Check at compile time if two `std::array`s are equal
393 template <typename T, typename S, size_t size>
394 inline constexpr bool array_equal(const std::array<T, size>& lhs,
395  const std::array<S, size>& rhs,
396  const size_t i = 0) noexcept {
397  // clang-tidy: Cannot use gsl::at because we want constexpr evaluation and
398  // Parallel::abort violates this
399  return i < size ? (lhs[i] == rhs[i] // NOLINT
400  and array_equal(lhs, rhs, i + 1))
401  : true;
402 }
403 
404 namespace cpp17 {
405 /// \ingroup ConstantExpressionsGroup
406 /// \brief Returns a const reference to its argument.
407 template <typename T>
408 constexpr const T& as_const(const T& t) noexcept {
409  return t;
410 }
411 } // namespace cpp17
constexpr size_t get_nth_bit(const size_t i, const size_t N)
Get the nth bit from the right, counting from zero.
Definition: ConstantExpressions.hpp:44
constexpr const T & max_by_magnitude(const T &a, const T &b)
Return the argument with the largest magnitude.
Definition: ConstantExpressions.hpp:211
constexpr const T & min_by_magnitude(const T &a, const T &b)
Return the argument with the smallest magnitude.
Definition: ConstantExpressions.hpp:229
constexpr std::array< std::decay_t< T >, Size > replace_at(const std::array< T, Size > &arr, T value)
Replace at compile time the Ith entry in the array with value
Definition: ConstantExpressions.hpp:383
Definition: ConstantExpressions.hpp:92
decltype(auto) constexpr cube(const T &x)
Compute the cube of x
Definition: ConstantExpressions.hpp:59
constexpr const T & as_const(const T &t) noexcept
Returns a const reference to its argument.
Definition: ConstantExpressions.hpp:408
Defines the type alias Requires.
Definition: Determinant.hpp:11
constexpr bool array_equal(const std::array< T, size > &lhs, const std::array< S, size > &rhs, const size_t i=0) noexcept
Check at compile time if two std::arrays are equal.
Definition: ConstantExpressions.hpp:394
#define SPECTRE_ALWAYS_INLINE
Always inline a function. Only use this if you benchmarked the code.
Definition: ForceInline.hpp:20
constexpr uint64_t falling_factorial(const uint64_t x, const uint64_t n) noexcept
Compute the falling factorial of .
Definition: ConstantExpressions.hpp:71
constexpr T ce_abs(const T &x) noexcept(noexcept(x< 0 ? -x :x))
Compute the absolute value of of its argument.
Definition: ConstantExpressions.hpp:168
constexpr T two_to_the(T n)
Compute 2 to the n for integral types.
Definition: ConstantExpressions.hpp:34
Defines macro to always inline a function.
constexpr const T & clamp(const T &v, const T &lo, const T &hi, Compare comp=Compare())
Clamps the value between lo and hi.
Definition: ConstantExpressions.hpp:247
constexpr size_t cstring_length(const char *str) noexcept
Compute the length of a const char* at compile time.
Definition: ConstantExpressions.hpp:351
constexpr uint64_t factorial(const uint64_t n) noexcept
Compute the factorial of .
Definition: ConstantExpressions.hpp:86
Wraps the template metaprogramming library used (brigand)
constexpr double ce_fabs(const double x) noexcept
Compute the absolute value of its argument.
Definition: ConstantExpressions.hpp:187
constexpr auto make_array_from_list() -> std::array< std::decay_t< decltype(tmpl::front< List >::value)>, tmpl::size< List >::value >
Make an array from a typelist that holds std::integral_constant&#39;s all of which have the same value_ty...
Definition: ConstantExpressions.hpp:302
decltype(auto) constexpr constexpr_sum(Function &&f) noexcept
Returns f(ic<0>{}) + f(ic<1>{}) + ... + f(ic<NumTerms-1>{}) where ic<N> stands for std::integral_cons...
Definition: ConstantExpressions.hpp:268
typename Requires_detail::requires_impl< B >::template_error_type_failed_to_meet_requirements_on_template_parameters Requires
Express requirements on the template parameters of a function or class, replaces std::enable_if_t ...
Definition: Requires.hpp:67
C++ STL code present in C++17.
Definition: Array.hpp:16
Defines type traits, some of which are future STL type_traits header.
Definition: ConstantExpressions.hpp:367
decltype(auto) constexpr square(const T &x)
Compute the square of x
Definition: ConstantExpressions.hpp:52
decltype(auto) constexpr pow(const T &t) noexcept
Compute t^N where N is an integer (positive or negative)
Definition: ConstantExpressions.hpp:157
constexpr size_t cstring_hash(const char *str) noexcept
Compute a hash of a const char* at compile time.
Definition: ConstantExpressions.hpp:359
Defines make_with_value.
constexpr T & at(std::array< T, N > &arr, Size index)
Retrieve a entry from a container, with checks in Debug mode that the index being retrieved is valid...
Definition: Gsl.hpp:124