Update contrib/restricted/abseil-cpp to 20220623.0

11 files changed, 134 insertions, 102 deletions

diff --git a/contrib/restricted/abseil-cpp/absl/random/bernoulli_distribution.h b/contrib/restricted/abseil-cpp/absl/random/bernoulli_distribution.h
index 25bd0d5ca4..d81b6ae6b1 100644
--- a/contrib/restricted/abseil-cpp/absl/random/bernoulli_distribution.h
+++ b/contrib/restricted/abseil-cpp/absl/random/bernoulli_distribution.h
@@ -138,16 +138,16 @@ bool bernoulli_distribution::Generate(double p,
     // 64 bits.
     //
     // Second, `c` is constructed by first casting explicitly to a signed
-    // integer and then converting implicitly to an unsigned integer of the same
+    // integer and then casting explicitly to an unsigned integer of the same
     // size.  This is done because the hardware conversion instructions produce
     // signed integers from double; if taken as a uint64_t the conversion would
     // be wrong for doubles greater than 2^63 (not relevant in this use-case).
     // If converted directly to an unsigned integer, the compiler would end up
     // emitting code to handle such large values that are not relevant due to
     // the known bounds on `c`.  To avoid these extra instructions this
-    // implementation converts first to the signed type and then use the
-    // implicit conversion to unsigned (which is a no-op).
-    const uint64_t c = static_cast<int64_t>(p * kP32);
+    // implementation converts first to the signed type and then convert to
+    // unsigned (which is a no-op).
+    const uint64_t c = static_cast<uint64_t>(static_cast<int64_t>(p * kP32));
     const uint32_t v = fast_u32(g);
     // FAST PATH: this path fails with probability 1/2^32.  Note that simply
     // returning v <= c would approximate P very well (up to an absolute error
diff --git a/contrib/restricted/abseil-cpp/absl/random/internal/chi_square.cc b/contrib/restricted/abseil-cpp/absl/random/internal/chi_square.cc
index 640d48cea6..fbe0173299 100644
--- a/contrib/restricted/abseil-cpp/absl/random/internal/chi_square.cc
+++ b/contrib/restricted/abseil-cpp/absl/random/internal/chi_square.cc
@@ -125,7 +125,8 @@ double ChiSquareValue(int dof, double p) {
     const double variance = 2.0 / (9 * dof);
     // Cannot use this method if the variance is 0.
     if (variance != 0) {
-      return std::pow(z * std::sqrt(variance) + mean, 3.0) * dof;
+      double term = z * std::sqrt(variance) + mean;
+      return dof * (term * term * term);
     }
   }
 
diff --git a/contrib/restricted/abseil-cpp/absl/random/internal/fast_uniform_bits.h b/contrib/restricted/abseil-cpp/absl/random/internal/fast_uniform_bits.h
index 425aaf7d83..f3a5c00f39 100644
--- a/contrib/restricted/abseil-cpp/absl/random/internal/fast_uniform_bits.h
+++ b/contrib/restricted/abseil-cpp/absl/random/internal/fast_uniform_bits.h
@@ -22,6 +22,7 @@
 
 #include "absl/base/config.h"
 #include "absl/meta/type_traits.h"
+#include "absl/random/internal/traits.h"
 
 namespace absl {
 ABSL_NAMESPACE_BEGIN
@@ -98,7 +99,7 @@ class FastUniformBits {
   result_type operator()(URBG& g);  // NOLINT(runtime/references)
 
  private:
-  static_assert(std::is_unsigned<UIntType>::value,
+  static_assert(IsUnsigned<UIntType>::value,
                 "Class-template FastUniformBits<> must be parameterized using "
                 "an unsigned type.");
 
diff --git a/contrib/restricted/abseil-cpp/absl/random/internal/generate_real.h b/contrib/restricted/abseil-cpp/absl/random/internal/generate_real.h
index d5fbb44c24..b569450cf7 100644
--- a/contrib/restricted/abseil-cpp/absl/random/internal/generate_real.h
+++ b/contrib/restricted/abseil-cpp/absl/random/internal/generate_real.h
@@ -50,10 +50,10 @@ struct GenerateSignedTag {};
 // inputs, otherwise it never returns 0.
 //
 // When a value in U(0,1) is required, use:
-//   Uniform64ToReal<double, PositiveValueT, true>;
+//   GenerateRealFromBits<double, PositiveValueT, true>;
 //
 // When a value in U(-1,1) is required, use:
-//   Uniform64ToReal<double, SignedValueT, false>;
+//   GenerateRealFromBits<double, SignedValueT, false>;
 //
 //   This generates more distinct values than the mathematical equivalent
 //   `U(0, 1) * 2.0 - 1.0`.
diff --git a/contrib/restricted/abseil-cpp/absl/random/internal/randen.h b/contrib/restricted/abseil-cpp/absl/random/internal/randen.h
index 9a3840b8f1..9ff4a7a554 100644
--- a/contrib/restricted/abseil-cpp/absl/random/internal/randen.h
+++ b/contrib/restricted/abseil-cpp/absl/random/internal/randen.h
@@ -43,10 +43,8 @@ class Randen {
 
   // Generate updates the randen sponge. The outer portion of the sponge
   // (kCapacityBytes .. kStateBytes) may be consumed as PRNG state.
-  template <typename T, size_t N>
-  void Generate(T (&state)[N]) const {
-    static_assert(N * sizeof(T) == kStateBytes,
-                  "Randen::Generate() requires kStateBytes of state");
+  // REQUIRES: state points to kStateBytes of state.
+  inline void Generate(void* state) const {
 #if ABSL_RANDOM_INTERNAL_AES_DISPATCH
     // HW AES Dispatch.
     if (has_crypto_) {
@@ -65,13 +63,9 @@ class Randen {
 
   // Absorb incorporates additional seed material into the randen sponge.  After
   // absorb returns, Generate must be called before the state may be consumed.
-  template <typename S, size_t M, typename T, size_t N>
-  void Absorb(const S (&seed)[M], T (&state)[N]) const {
-    static_assert(M * sizeof(S) == RandenTraits::kSeedBytes,
-                  "Randen::Absorb() requires kSeedBytes of seed");
-
-    static_assert(N * sizeof(T) == RandenTraits::kStateBytes,
-                  "Randen::Absorb() requires kStateBytes of state");
+  // REQUIRES: seed points to kSeedBytes of seed.
+  // REQUIRES: state points to kStateBytes of state.
+  inline void Absorb(const void* seed, void* state) const {
 #if ABSL_RANDOM_INTERNAL_AES_DISPATCH
     // HW AES Dispatch.
     if (has_crypto_) {
diff --git a/contrib/restricted/abseil-cpp/absl/random/internal/randen_detect.cc b/contrib/restricted/abseil-cpp/absl/random/internal/randen_detect.cc
index bbe7b96532..6dababa351 100644
--- a/contrib/restricted/abseil-cpp/absl/random/internal/randen_detect.cc
+++ b/contrib/restricted/abseil-cpp/absl/random/internal/randen_detect.cc
@@ -24,6 +24,11 @@
 
 #include "absl/random/internal/platform.h"
 
+#if !defined(__UCLIBC__) && defined(__GLIBC__) && \
+    (__GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 16))
+#define ABSL_HAVE_GETAUXVAL
+#endif
+
 #if defined(ABSL_ARCH_X86_64)
 #define ABSL_INTERNAL_USE_X86_CPUID
 #elif defined(ABSL_ARCH_PPC) || defined(ABSL_ARCH_ARM) || \
@@ -31,7 +36,7 @@
 #if defined(__ANDROID__)
 #define ABSL_INTERNAL_USE_ANDROID_GETAUXVAL
 #define ABSL_INTERNAL_USE_GETAUXVAL
-#elif defined(__linux__)
+#elif defined(__linux__) && defined(ABSL_HAVE_GETAUXVAL)
 #define ABSL_INTERNAL_USE_LINUX_GETAUXVAL
 #define ABSL_INTERNAL_USE_GETAUXVAL
 #endif
@@ -40,7 +45,6 @@
 #if defined(ABSL_INTERNAL_USE_X86_CPUID)
 #if defined(_WIN32) || defined(_WIN64)
 #include <intrin.h>  // NOLINT(build/include_order)
-#pragma intrinsic(__cpuid)
 #else
 // MSVC-equivalent __cpuid intrinsic function.
 static void __cpuid(int cpu_info[4], int info_type) {
diff --git a/contrib/restricted/abseil-cpp/absl/random/internal/salted_seed_seq.h b/contrib/restricted/abseil-cpp/absl/random/internal/salted_seed_seq.h
index 5953a090f8..06291865e3 100644
--- a/contrib/restricted/abseil-cpp/absl/random/internal/salted_seed_seq.h
+++ b/contrib/restricted/abseil-cpp/absl/random/internal/salted_seed_seq.h
@@ -22,6 +22,7 @@
 #include <memory>
 #include <type_traits>
 #include <utility>
+#include <vector>
 
 #include "absl/container/inlined_vector.h"
 #include "absl/meta/type_traits.h"
@@ -65,15 +66,19 @@ class SaltedSeedSeq {
 
   template <typename RandomAccessIterator>
   void generate(RandomAccessIterator begin, RandomAccessIterator end) {
+    using U = typename std::iterator_traits<RandomAccessIterator>::value_type;
+
     // The common case is that generate is called with ContiguousIterators
     // to uint arrays. Such contiguous memory regions may be optimized,
     // which we detect here.
-    using tag = absl::conditional_t<
-        (std::is_pointer<RandomAccessIterator>::value &&
-         std::is_same<absl::decay_t<decltype(*begin)>, uint32_t>::value),
+    using TagType = absl::conditional_t<
+        (std::is_same<U, uint32_t>::value &&
+         (std::is_pointer<RandomAccessIterator>::value ||
+          std::is_same<RandomAccessIterator,
+                       typename std::vector<U>::iterator>::value)),
         ContiguousAndUint32Tag, DefaultTag>;
     if (begin != end) {
-      generate_impl(begin, end, tag{});
+      generate_impl(TagType{}, begin, end, std::distance(begin, end));
     }
   }
 
@@ -89,8 +94,15 @@ class SaltedSeedSeq {
   struct DefaultTag {};
 
   // Generate which requires the iterators are contiguous pointers to uint32_t.
-  void generate_impl(uint32_t* begin, uint32_t* end, ContiguousAndUint32Tag) {
-    generate_contiguous(absl::MakeSpan(begin, end));
+  // Fills the initial seed buffer the underlying SSeq::generate() call,
+  // then mixes in the salt material.
+  template <typename Contiguous>
+  void generate_impl(ContiguousAndUint32Tag, Contiguous begin, Contiguous end,
+                     size_t n) {
+    seq_->generate(begin, end);
+    const uint32_t salt = absl::random_internal::GetSaltMaterial().value_or(0);
+    auto span = absl::Span<uint32_t>(&*begin, n);
+    MixIntoSeedMaterial(absl::MakeConstSpan(&salt, 1), span);
   }
 
   // The uncommon case for generate is that it is called with iterators over
@@ -98,27 +110,13 @@ class SaltedSeedSeq {
   // case we allocate a temporary 32-bit buffer and then copy-assign back
   // to the initial inputs.
   template <typename RandomAccessIterator>
-  void generate_impl(RandomAccessIterator begin, RandomAccessIterator end,
-                     DefaultTag) {
-    return generate_and_copy(std::distance(begin, end), begin);
-  }
-
-  // Fills the initial seed buffer the underlying SSeq::generate() call,
-  // mixing in the salt material.
-  void generate_contiguous(absl::Span<uint32_t> buffer) {
-    seq_->generate(buffer.begin(), buffer.end());
-    const uint32_t salt = absl::random_internal::GetSaltMaterial().value_or(0);
-    MixIntoSeedMaterial(absl::MakeConstSpan(&salt, 1), buffer);
-  }
-
-  // Allocates a seed buffer of `n` elements, generates the seed, then
-  // copies the result into the `out` iterator.
-  template <typename Iterator>
-  void generate_and_copy(size_t n, Iterator out) {
-    // Allocate a temporary buffer, generate, and then copy.
+  void generate_impl(DefaultTag, RandomAccessIterator begin,
+                     RandomAccessIterator, size_t n) {
+    // Allocates a seed buffer of `n` elements, generates the seed, then
+    // copies the result into the `out` iterator.
     absl::InlinedVector<uint32_t, 8> data(n, 0);
-    generate_contiguous(absl::MakeSpan(data.data(), data.size()));
-    std::copy(data.begin(), data.end(), out);
+    generate_impl(ContiguousAndUint32Tag{}, data.begin(), data.end(), n);
+    std::copy(data.begin(), data.end(), begin);
   }
 
   // Because [rand.req.seedseq] is not required to be copy-constructible,
diff --git a/contrib/restricted/abseil-cpp/absl/random/internal/traits.h b/contrib/restricted/abseil-cpp/absl/random/internal/traits.h
index 75772bd9ab..f874a0f78b 100644
--- a/contrib/restricted/abseil-cpp/absl/random/internal/traits.h
+++ b/contrib/restricted/abseil-cpp/absl/random/internal/traits.h
@@ -20,6 +20,8 @@
 #include <type_traits>
 
 #include "absl/base/config.h"
+#include "absl/numeric/bits.h"
+#include "absl/numeric/int128.h"
 
 namespace absl {
 ABSL_NAMESPACE_BEGIN
@@ -59,6 +61,31 @@ class is_widening_convertible {
       rank<A>() <= rank<B>();
 };
 
+template <typename T>
+struct IsIntegral : std::is_integral<T> {};
+template <>
+struct IsIntegral<absl::int128> : std::true_type {};
+template <>
+struct IsIntegral<absl::uint128> : std::true_type {};
+
+template <typename T>
+struct MakeUnsigned : std::make_unsigned<T> {};
+template <>
+struct MakeUnsigned<absl::int128> {
+  using type = absl::uint128;
+};
+template <>
+struct MakeUnsigned<absl::uint128> {
+  using type = absl::uint128;
+};
+
+template <typename T>
+struct IsUnsigned : std::is_unsigned<T> {};
+template <>
+struct IsUnsigned<absl::int128> : std::false_type {};
+template <>
+struct IsUnsigned<absl::uint128> : std::true_type {};
+
 // unsigned_bits<N>::type returns the unsigned int type with the indicated
 // number of bits.
 template <size_t N>
@@ -81,19 +108,40 @@ struct unsigned_bits<64> {
   using type = uint64_t;
 };
 
-#ifdef ABSL_HAVE_INTRINSIC_INT128
 template <>
 struct unsigned_bits<128> {
-  using type = __uint128_t;
+  using type = absl::uint128;
+};
+
+// 256-bit wrapper for wide multiplications.
+struct U256 {
+  uint128 hi;
+  uint128 lo;
+};
+template <>
+struct unsigned_bits<256> {
+  using type = U256;
 };
-#endif
 
 template <typename IntType>
 struct make_unsigned_bits {
-  using type = typename unsigned_bits<std::numeric_limits<
-      typename std::make_unsigned<IntType>::type>::digits>::type;
+  using type = typename unsigned_bits<
+      std::numeric_limits<typename MakeUnsigned<IntType>::type>::digits>::type;
 };
 
+template <typename T>
+int BitWidth(T v) {
+  // Workaround for bit_width not supporting int128.
+  // Don't hardcode `64` to make sure this code does not trigger compiler
+  // warnings in smaller types.
+  constexpr int half_bits = sizeof(T) * 8 / 2;
+  if (sizeof(T) == 16 && (v >> half_bits) != 0) {
+    return bit_width(static_cast<uint64_t>(v >> half_bits)) + half_bits;
+  } else {
+    return bit_width(static_cast<uint64_t>(v));
+  }
+}
+
 }  // namespace random_internal
 ABSL_NAMESPACE_END
 }  // namespace absl
diff --git a/contrib/restricted/abseil-cpp/absl/random/internal/wide_multiply.h b/contrib/restricted/abseil-cpp/absl/random/internal/wide_multiply.h
index b6e6c4b6aa..891e3630b7 100644
--- a/contrib/restricted/abseil-cpp/absl/random/internal/wide_multiply.h
+++ b/contrib/restricted/abseil-cpp/absl/random/internal/wide_multiply.h
@@ -34,43 +34,6 @@ namespace absl {
 ABSL_NAMESPACE_BEGIN
 namespace random_internal {
 
-// Helper object to multiply two 64-bit values to a 128-bit value.
-// MultiplyU64ToU128 multiplies two 64-bit values to a 128-bit value.
-// If an intrinsic is available, it is used, otherwise use native 32-bit
-// multiplies to construct the result.
-inline absl::uint128 MultiplyU64ToU128(uint64_t a, uint64_t b) {
-#if defined(ABSL_HAVE_INTRINSIC_INT128)
-  return absl::uint128(static_cast<__uint128_t>(a) * b);
-#elif defined(ABSL_INTERNAL_USE_UMUL128)
-  // uint64_t * uint64_t => uint128 multiply using imul intrinsic on MSVC.
-  uint64_t high = 0;
-  const uint64_t low = _umul128(a, b, &high);
-  return absl::MakeUint128(high, low);
-#else
-  // uint128(a) * uint128(b) in emulated mode computes a full 128-bit x 128-bit
-  // multiply.  However there are many cases where that is not necessary, and it
-  // is only necessary to support a 64-bit x 64-bit = 128-bit multiply.  This is
-  // for those cases.
-  const uint64_t a00 = static_cast<uint32_t>(a);
-  const uint64_t a32 = a >> 32;
-  const uint64_t b00 = static_cast<uint32_t>(b);
-  const uint64_t b32 = b >> 32;
-
-  const uint64_t c00 = a00 * b00;
-  const uint64_t c32a = a00 * b32;
-  const uint64_t c32b = a32 * b00;
-  const uint64_t c64 = a32 * b32;
-
-  const uint32_t carry =
-      static_cast<uint32_t>(((c00 >> 32) + static_cast<uint32_t>(c32a) +
-                             static_cast<uint32_t>(c32b)) >>
-                            32);
-
-  return absl::MakeUint128(c64 + (c32a >> 32) + (c32b >> 32) + carry,
-                           c00 + (c32a << 32) + (c32b << 32));
-#endif
-}
-
 // wide_multiply<T> multiplies two N-bit values to a 2N-bit result.
 template <typename UIntType>
 struct wide_multiply {
@@ -82,27 +45,49 @@ struct wide_multiply {
     return static_cast<result_type>(a) * b;
   }
 
-  static input_type hi(result_type r) { return r >> kN; }
-  static input_type lo(result_type r) { return r; }
+  static input_type hi(result_type r) {
+    return static_cast<input_type>(r >> kN);
+  }
+  static input_type lo(result_type r) { return static_cast<input_type>(r); }
 
   static_assert(std::is_unsigned<UIntType>::value,
                 "Class-template wide_multiply<> argument must be unsigned.");
 };
 
-#ifndef ABSL_HAVE_INTRINSIC_INT128
+// MultiplyU128ToU256 multiplies two 128-bit values to a 256-bit value.
+inline U256 MultiplyU128ToU256(uint128 a, uint128 b) {
+  const uint128 a00 = static_cast<uint64_t>(a);
+  const uint128 a64 = a >> 64;
+  const uint128 b00 = static_cast<uint64_t>(b);
+  const uint128 b64 = b >> 64;
+
+  const uint128 c00 = a00 * b00;
+  const uint128 c64a = a00 * b64;
+  const uint128 c64b = a64 * b00;
+  const uint128 c128 = a64 * b64;
+
+  const uint64_t carry =
+      static_cast<uint64_t>(((c00 >> 64) + static_cast<uint64_t>(c64a) +
+                             static_cast<uint64_t>(c64b)) >>
+                            64);
+
+  return {c128 + (c64a >> 64) + (c64b >> 64) + carry,
+          c00 + (c64a << 64) + (c64b << 64)};
+}
+
+
 template <>
-struct wide_multiply<uint64_t> {
-  using input_type = uint64_t;
-  using result_type = absl::uint128;
+struct wide_multiply<uint128> {
+  using input_type = uint128;
+  using result_type = U256;
 
-  static result_type multiply(uint64_t a, uint64_t b) {
-    return MultiplyU64ToU128(a, b);
+  static result_type multiply(input_type a, input_type b) {
+    return MultiplyU128ToU256(a, b);
   }
 
-  static uint64_t hi(result_type r) { return absl::Uint128High64(r); }
-  static uint64_t lo(result_type r) { return absl::Uint128Low64(r); }
+  static input_type hi(result_type r) { return r.hi; }
+  static input_type lo(result_type r) { return r.lo; }
 };
-#endif
 
 }  // namespace random_internal
 ABSL_NAMESPACE_END
diff --git a/contrib/restricted/abseil-cpp/absl/random/seed_sequences.h b/contrib/restricted/abseil-cpp/absl/random/seed_sequences.h
index ff1340cc8e..c3af4b00a4 100644
--- a/contrib/restricted/abseil-cpp/absl/random/seed_sequences.h
+++ b/contrib/restricted/abseil-cpp/absl/random/seed_sequences.h
@@ -28,6 +28,7 @@
 #include <iterator>
 #include <random>
 
+#include "absl/base/config.h"
 #include "absl/random/internal/salted_seed_seq.h"
 #include "absl/random/internal/seed_material.h"
 #include "absl/random/seed_gen_exception.h"
diff --git a/contrib/restricted/abseil-cpp/absl/random/uniform_int_distribution.h b/contrib/restricted/abseil-cpp/absl/random/uniform_int_distribution.h
index c1f54ccebc..fae80252e3 100644
--- a/contrib/restricted/abseil-cpp/absl/random/uniform_int_distribution.h
+++ b/contrib/restricted/abseil-cpp/absl/random/uniform_int_distribution.h
@@ -97,7 +97,7 @@ class uniform_int_distribution {
     result_type lo_;
     unsigned_type range_;
 
-    static_assert(std::is_integral<result_type>::value,
+    static_assert(random_internal::IsIntegral<result_type>::value,
                   "Class-template absl::uniform_int_distribution<> must be "
                   "parameterized using an integral type.");
   };  // param_type
@@ -125,7 +125,7 @@ class uniform_int_distribution {
   template <typename URBG>
   result_type operator()(
       URBG& gen, const param_type& param) {  // NOLINT(runtime/references)
-    return param.a() + Generate(gen, param.range());
+    return static_cast<result_type>(param.a() + Generate(gen, param.range()));
   }
 
   result_type a() const { return param_.a(); }