diff options
author | Abseil Team <absl-team@google.com> | 2018-08-01 04:34:12 -0700 |
---|---|---|
committer | Derek Mauro <dmauro@google.com> | 2018-08-01 13:27:57 -0400 |
commit | 2125e6444a9de9e41f21ecdc674dd7d8759c149d (patch) | |
tree | dd0498a26dcbf4453df9c913fc805650b64916ef /absl | |
parent | 9acad869d21731f5bc50430a33fe61cc0ffcbb0b (diff) |
Export of internal Abseil changes.
--
ac7508120c60dfe689c40929e416b6a486f83ee3 by Gennadiy Rozental <rogeeff@google.com>:
Internal change
PiperOrigin-RevId: 206912089
--
bd709faba88565367b6d337466e6456481b5f3e8 by Matt Calabrese <calabrese@google.com>:
Implement `std::experimental::is_detected` in type_traits internals and move `is_detected_convertible` from variant's internals to type_traits internals. This is in preparation of creating workarounds for broken standard traits.
PiperOrigin-RevId: 206825598
--
0dbddea569370eb9b6348cee172d1874f9046eb4 by Jorg Brown <jorg@google.com>:
Support users who turn on floating-point conversion warnings
PiperOrigin-RevId: 206813209
--
30991f757c8f0100584619d8a9c41897d029f112 by Jorg Brown <jorg@google.com>:
Speed up the absl::Seconds() function for floating-point values, roughly by 4.5x, since
we can take advantage of the fact that we're just taking a floating-point number and
splitting it into its integral and fractional parts.
PiperOrigin-RevId: 206806270
--
6883837176838aa5a517e7a8cb4c99afd24c0d12 by Jon Cohen <cohenjon@google.com>:
Remove the DISABLE_INSTALL from absl_container. It doesn't do anything.
PiperOrigin-RevId: 206802544
--
92ab14fed06e6dd1f01a0284bd7f95d3e2c0c3d8 by Jon Cohen <cohenjon@google.com>:
Internal change
PiperOrigin-RevId: 206776244
--
17b76c7f364ac562d9e0faeca0320f63aa3fdb85 by Jorg Brown <jorg@google.com>:
Fix absl/strings:numbers_test flakiness due to exceeding the 1-minute timeout
PiperOrigin-RevId: 206763175
--
6637843f2e198b8efd90e5577fbc86bdea43b2cc by Abseil Team <absl-team@google.com>:
Adds templated allocator to absl::FixedArray with corresponding tests
PiperOrigin-RevId: 206354178
--
bced22f81add828c9b4c60eb45554d36c22e2f96 by Abseil Team <absl-team@google.com>:
Adds templated allocator to absl::FixedArray with corresponding tests
PiperOrigin-RevId: 206347377
--
75be14a71d2d5e335812d5b7670120271fb5bd79 by Abseil Team <absl-team@google.com>:
Internal change.
PiperOrigin-RevId: 206326935
--
6929e43f4c7898b1f51e441911a19092a06fbf97 by Abseil Team <absl-team@google.com>:
Adds templated allocator to absl::FixedArray with corresponding tests
PiperOrigin-RevId: 206326368
--
55ae34b75ff029eb267f9519e577bab8a575b487 by Abseil Team <absl-team@google.com>:
Internal change.
PiperOrigin-RevId: 206233448
--
6950a8ccddf35d451eec2d02cd28a797c8b7cf6a by Matt Kulukundis <kfm@google.com>:
Internal change
PiperOrigin-RevId: 206035613
GitOrigin-RevId: ac7508120c60dfe689c40929e416b6a486f83ee3
Change-Id: I675605abbedab6b3ac9aa82195cbd059ff7c82b1
Diffstat (limited to 'absl')
-rw-r--r-- | absl/container/BUILD.bazel | 20 | ||||
-rw-r--r-- | absl/container/CMakeLists.txt | 1 | ||||
-rw-r--r-- | absl/container/fixed_array.h | 154 | ||||
-rw-r--r-- | absl/container/fixed_array_test.cc | 213 | ||||
-rw-r--r-- | absl/container/internal/compressed_tuple.h | 175 | ||||
-rw-r--r-- | absl/container/internal/compressed_tuple_test.cc | 166 | ||||
-rw-r--r-- | absl/memory/memory.h | 56 | ||||
-rw-r--r-- | absl/memory/memory_exception_safety_test.cc | 11 | ||||
-rw-r--r-- | absl/memory/memory_test.cc | 43 | ||||
-rw-r--r-- | absl/meta/type_traits.h | 44 | ||||
-rw-r--r-- | absl/meta/type_traits_test.cc | 81 | ||||
-rw-r--r-- | absl/strings/numbers_test.cc | 7 | ||||
-rw-r--r-- | absl/time/duration.cc | 5 | ||||
-rw-r--r-- | absl/time/duration_benchmark.cc | 78 | ||||
-rw-r--r-- | absl/time/duration_test.cc | 124 | ||||
-rw-r--r-- | absl/time/time.h | 97 | ||||
-rw-r--r-- | absl/types/internal/variant.h | 28 |
17 files changed, 1066 insertions, 237 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 07df3675..6d5c958f 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -26,10 +26,30 @@ package(default_visibility = ["//visibility:public"]) licenses(["notice"]) # Apache 2.0 cc_library( + name = "compressed_tuple", + hdrs = ["internal/compressed_tuple.h"], + copts = ABSL_DEFAULT_COPTS, + deps = [ + "//absl/utility", + ], +) + +cc_test( + name = "compressed_tuple_test", + srcs = ["internal/compressed_tuple_test.cc"], + copts = ABSL_TEST_COPTS, + deps = [ + ":compressed_tuple", + "@com_google_googletest//:gtest_main", + ], +) + +cc_library( name = "fixed_array", hdrs = ["fixed_array.h"], copts = ABSL_DEFAULT_COPTS, deps = [ + ":compressed_tuple", "//absl/algorithm", "//absl/base:core_headers", "//absl/base:dynamic_annotations", diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index d580b489..123e4c48 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -52,7 +52,6 @@ absl_library( ${TEST_INSTANCE_TRACKER_LIB_SRC} PUBLIC_LIBRARIES absl::container - DISABLE_INSTALL ) diff --git a/absl/container/fixed_array.h b/absl/container/fixed_array.h index 62600df0..f480047a 100644 --- a/absl/container/fixed_array.h +++ b/absl/container/fixed_array.h @@ -47,6 +47,7 @@ #include "absl/base/macros.h" #include "absl/base/optimization.h" #include "absl/base/port.h" +#include "absl/container/internal/compressed_tuple.h" #include "absl/memory/memory.h" namespace absl { @@ -76,73 +77,99 @@ constexpr static auto kFixedArrayUseDefault = static_cast<size_t>(-1); // heap allocation, it will do so with global `::operator new[]()` and // `::operator delete[]()`, even if T provides class-scope overrides for these // operators. -template <typename T, size_t inlined = kFixedArrayUseDefault> +template <typename T, size_t N = kFixedArrayUseDefault, + typename A = std::allocator<T>> class FixedArray { static_assert(!std::is_array<T>::value || std::extent<T>::value > 0, "Arrays with unknown bounds cannot be used with FixedArray."); + static constexpr size_t kInlineBytesDefault = 256; + using AllocatorTraits = std::allocator_traits<A>; // std::iterator_traits isn't guaranteed to be SFINAE-friendly until C++17, // but this seems to be mostly pedantic. template <typename Iterator> using EnableIfForwardIterator = absl::enable_if_t<std::is_convertible< typename std::iterator_traits<Iterator>::iterator_category, std::forward_iterator_tag>::value>; + static constexpr bool NoexceptCopyable() { + return std::is_nothrow_copy_constructible<StorageElement>::value && + absl::allocator_is_nothrow<allocator_type>::value; + } + static constexpr bool NoexceptMovable() { + return std::is_nothrow_move_constructible<StorageElement>::value && + absl::allocator_is_nothrow<allocator_type>::value; + } + static constexpr bool DefaultConstructorIsNonTrivial() { + return !absl::is_trivially_default_constructible<StorageElement>::value; + } public: - using value_type = T; - using iterator = T*; - using const_iterator = const T*; + using allocator_type = typename AllocatorTraits::allocator_type; + using value_type = typename allocator_type::value_type; + using pointer = typename allocator_type::pointer; + using const_pointer = typename allocator_type::const_pointer; + using reference = typename allocator_type::reference; + using const_reference = typename allocator_type::const_reference; + using size_type = typename allocator_type::size_type; + using difference_type = typename allocator_type::difference_type; + using iterator = pointer; + using const_iterator = const_pointer; using reverse_iterator = std::reverse_iterator<iterator>; using const_reverse_iterator = std::reverse_iterator<const_iterator>; - using reference = T&; - using const_reference = const T&; - using pointer = T*; - using const_pointer = const T*; - using difference_type = ptrdiff_t; - using size_type = size_t; static constexpr size_type inline_elements = - inlined == kFixedArrayUseDefault - ? kInlineBytesDefault / sizeof(value_type) - : inlined; + (N == kFixedArrayUseDefault ? kInlineBytesDefault / sizeof(value_type) + : static_cast<size_type>(N)); - FixedArray(const FixedArray& other) - : FixedArray(other.begin(), other.end()) {} + FixedArray( + const FixedArray& other, + const allocator_type& a = allocator_type()) noexcept(NoexceptCopyable()) + : FixedArray(other.begin(), other.end(), a) {} - FixedArray(FixedArray&& other) noexcept( - absl::conjunction<absl::allocator_is_nothrow<std::allocator<value_type>>, - std::is_nothrow_move_constructible<value_type>>::value) + FixedArray( + FixedArray&& other, + const allocator_type& a = allocator_type()) noexcept(NoexceptMovable()) : FixedArray(std::make_move_iterator(other.begin()), - std::make_move_iterator(other.end())) {} + std::make_move_iterator(other.end()), a) {} // Creates an array object that can store `n` elements. // Note that trivially constructible elements will be uninitialized. - explicit FixedArray(size_type n) : storage_(n) { - absl::memory_internal::uninitialized_default_construct_n(storage_.begin(), - size()); + explicit FixedArray(size_type n, const allocator_type& a = allocator_type()) + : storage_(n, a) { + if (DefaultConstructorIsNonTrivial()) { + memory_internal::ConstructStorage(storage_.alloc(), storage_.begin(), + storage_.end()); + } } // Creates an array initialized with `n` copies of `val`. - FixedArray(size_type n, const value_type& val) : storage_(n) { - std::uninitialized_fill_n(data(), size(), val); + FixedArray(size_type n, const value_type& val, + const allocator_type& a = allocator_type()) + : storage_(n, a) { + memory_internal::ConstructStorage(storage_.alloc(), storage_.begin(), + storage_.end(), val); } + // Creates an array initialized with the size and contents of `init_list`. + FixedArray(std::initializer_list<value_type> init_list, + const allocator_type& a = allocator_type()) + : FixedArray(init_list.begin(), init_list.end(), a) {} + // Creates an array initialized with the elements from the input // range. The array's size will always be `std::distance(first, last)`. // REQUIRES: Iterator must be a forward_iterator or better. template <typename Iterator, EnableIfForwardIterator<Iterator>* = nullptr> - FixedArray(Iterator first, Iterator last) - : storage_(std::distance(first, last)) { - std::uninitialized_copy(first, last, data()); + FixedArray(Iterator first, Iterator last, + const allocator_type& a = allocator_type()) + : storage_(std::distance(first, last), a) { + memory_internal::CopyToStorageFromRange(storage_.alloc(), storage_.begin(), + first, last); } - FixedArray(std::initializer_list<value_type> init_list) - : FixedArray(init_list.begin(), init_list.end()) {} - ~FixedArray() noexcept { - for (const StorageElement& cur : storage_) { - cur.~StorageElement(); + for (auto* cur = storage_.begin(); cur != storage_.end(); ++cur) { + AllocatorTraits::destroy(*storage_.alloc(), cur); } } @@ -332,7 +359,6 @@ class FixedArray { friend bool operator>=(const FixedArray& lhs, const FixedArray& rhs) { return !(lhs < rhs); } - private: // StorageElement // @@ -364,6 +390,8 @@ class FixedArray { using StorageElement = absl::conditional_t<std::is_array<value_type>::value, StorageElementWrapper<value_type>, value_type>; + using StorageElementBuffer = + absl::aligned_storage_t<sizeof(StorageElement), alignof(StorageElement)>; static pointer AsValueType(pointer ptr) { return ptr; } static pointer AsValueType(StorageElementWrapper<value_type>* ptr) { @@ -374,9 +402,6 @@ class FixedArray { static_assert(alignof(StorageElement) == alignof(value_type), ""); struct NonEmptyInlinedStorage { - using StorageElementBuffer = - absl::aligned_storage_t<sizeof(StorageElement), - alignof(StorageElement)>; StorageElement* data() { return reinterpret_cast<StorageElement*>(inlined_storage_.data()); } @@ -386,8 +411,8 @@ class FixedArray { void* RedzoneEnd() { return &redzone_end_ + 1; } #endif // ADDRESS_SANITIZER - void AnnotateConstruct(size_t); - void AnnotateDestruct(size_t); + void AnnotateConstruct(size_type); + void AnnotateDestruct(size_type); ADDRESS_SANITIZER_REDZONE(redzone_begin_); std::array<StorageElementBuffer, inline_elements> inlined_storage_; @@ -396,8 +421,8 @@ class FixedArray { struct EmptyInlinedStorage { StorageElement* data() { return nullptr; } - void AnnotateConstruct(size_t) {} - void AnnotateDestruct(size_t) {} + void AnnotateConstruct(size_type) {} + void AnnotateDestruct(size_type) {} }; using InlinedStorage = @@ -414,48 +439,57 @@ class FixedArray { // class Storage : public InlinedStorage { public: - explicit Storage(size_type n) : data_(CreateStorage(n)), size_(n) {} + Storage(size_type n, const allocator_type& a) + : size_alloc_(n, a), data_(InitializeData()) {} + ~Storage() noexcept { if (UsingInlinedStorage(size())) { - this->AnnotateDestruct(size()); + InlinedStorage::AnnotateDestruct(size()); } else { - std::allocator<StorageElement>().deallocate(begin(), size()); + AllocatorTraits::deallocate(*alloc(), AsValueType(begin()), size()); } } - size_type size() const { return size_; } + size_type size() const { return size_alloc_.template get<0>(); } StorageElement* begin() const { return data_; } StorageElement* end() const { return begin() + size(); } + allocator_type* alloc() { + return std::addressof(size_alloc_.template get<1>()); + } private: static bool UsingInlinedStorage(size_type n) { return n <= inline_elements; } - StorageElement* CreateStorage(size_type n) { - if (UsingInlinedStorage(n)) { - this->AnnotateConstruct(n); + StorageElement* InitializeData() { + if (UsingInlinedStorage(size())) { + InlinedStorage::AnnotateConstruct(size()); return InlinedStorage::data(); } else { - return std::allocator<StorageElement>().allocate(n); + return reinterpret_cast<StorageElement*>( + AllocatorTraits::allocate(*alloc(), size())); } } - StorageElement* const data_; - const size_type size_; + // `CompressedTuple` takes advantage of EBCO for stateless `allocator_type`s + container_internal::CompressedTuple<size_type, allocator_type> size_alloc_; + StorageElement* data_; }; - const Storage storage_; + Storage storage_; }; -template <typename T, size_t N> -constexpr size_t FixedArray<T, N>::inline_elements; +template <typename T, size_t N, typename A> +constexpr size_t FixedArray<T, N, A>::kInlineBytesDefault; -template <typename T, size_t N> -constexpr size_t FixedArray<T, N>::kInlineBytesDefault; +template <typename T, size_t N, typename A> +constexpr typename FixedArray<T, N, A>::size_type + FixedArray<T, N, A>::inline_elements; -template <typename T, size_t N> -void FixedArray<T, N>::NonEmptyInlinedStorage::AnnotateConstruct(size_t n) { +template <typename T, size_t N, typename A> +void FixedArray<T, N, A>::NonEmptyInlinedStorage::AnnotateConstruct( + typename FixedArray<T, N, A>::size_type n) { #ifdef ADDRESS_SANITIZER if (!n) return; ANNOTATE_CONTIGUOUS_CONTAINER(data(), RedzoneEnd(), RedzoneEnd(), data() + n); @@ -464,8 +498,9 @@ void FixedArray<T, N>::NonEmptyInlinedStorage::AnnotateConstruct(size_t n) { static_cast<void>(n); // Mark used when not in asan mode } -template <typename T, size_t N> -void FixedArray<T, N>::NonEmptyInlinedStorage::AnnotateDestruct(size_t n) { +template <typename T, size_t N, typename A> +void FixedArray<T, N, A>::NonEmptyInlinedStorage::AnnotateDestruct( + typename FixedArray<T, N, A>::size_type n) { #ifdef ADDRESS_SANITIZER if (!n) return; ANNOTATE_CONTIGUOUS_CONTAINER(data(), RedzoneEnd(), data() + n, RedzoneEnd()); @@ -473,6 +508,5 @@ void FixedArray<T, N>::NonEmptyInlinedStorage::AnnotateDestruct(size_t n) { #endif // ADDRESS_SANITIZER static_cast<void>(n); // Mark used when not in asan mode } - } // namespace absl #endif // ABSL_CONTAINER_FIXED_ARRAY_H_ diff --git a/absl/container/fixed_array_test.cc b/absl/container/fixed_array_test.cc index 2142132d..b07ebcb6 100644 --- a/absl/container/fixed_array_test.cc +++ b/absl/container/fixed_array_test.cc @@ -15,9 +15,11 @@ #include "absl/container/fixed_array.h" #include <stdio.h> +#include <cstring> #include <list> #include <memory> #include <numeric> +#include <scoped_allocator> #include <stdexcept> #include <string> #include <vector> @@ -607,6 +609,216 @@ TEST(FixedArrayTest, Fill) { empty.fill(fill_val); } +// TODO(johnsoncj): Investigate InlinedStorage default initialization in GCC 4.x +#ifndef __GNUC__ +TEST(FixedArrayTest, DefaultCtorDoesNotValueInit) { + using T = char; + constexpr auto capacity = 10; + using FixedArrType = absl::FixedArray<T, capacity>; + using FixedArrBuffType = + absl::aligned_storage_t<sizeof(FixedArrType), alignof(FixedArrType)>; + constexpr auto scrubbed_bits = 0x95; + constexpr auto length = capacity / 2; + + FixedArrBuffType buff; + std::memset(std::addressof(buff), scrubbed_bits, sizeof(FixedArrBuffType)); + + FixedArrType* arr = + ::new (static_cast<void*>(std::addressof(buff))) FixedArrType(length); + EXPECT_THAT(*arr, testing::Each(scrubbed_bits)); + arr->~FixedArrType(); +} +#endif // __GNUC__ + +// This is a stateful allocator, but the state lives outside of the +// allocator (in whatever test is using the allocator). This is odd +// but helps in tests where the allocator is propagated into nested +// containers - that chain of allocators uses the same state and is +// thus easier to query for aggregate allocation information. +template <typename T> +class CountingAllocator : public std::allocator<T> { + public: + using Alloc = std::allocator<T>; + using pointer = typename Alloc::pointer; + using size_type = typename Alloc::size_type; + + CountingAllocator() : bytes_used_(nullptr), instance_count_(nullptr) {} + explicit CountingAllocator(int64_t* b) + : bytes_used_(b), instance_count_(nullptr) {} + CountingAllocator(int64_t* b, int64_t* a) + : bytes_used_(b), instance_count_(a) {} + + template <typename U> + explicit CountingAllocator(const CountingAllocator<U>& x) + : Alloc(x), + bytes_used_(x.bytes_used_), + instance_count_(x.instance_count_) {} + + pointer allocate(size_type n, const void* const hint = nullptr) { + assert(bytes_used_ != nullptr); + *bytes_used_ += n * sizeof(T); + return Alloc::allocate(n, hint); + } + + void deallocate(pointer p, size_type n) { + Alloc::deallocate(p, n); + assert(bytes_used_ != nullptr); + *bytes_used_ -= n * sizeof(T); + } + + template <typename... Args> + void construct(pointer p, Args&&... args) { + Alloc::construct(p, absl::forward<Args>(args)...); + if (instance_count_) { + *instance_count_ += 1; + } + } + + void destroy(pointer p) { + Alloc::destroy(p); + if (instance_count_) { + *instance_count_ -= 1; + } + } + + template <typename U> + class rebind { + public: + using other = CountingAllocator<U>; + }; + + int64_t* bytes_used_; + int64_t* instance_count_; +}; + +TEST(AllocatorSupportTest, CountInlineAllocations) { + constexpr size_t inlined_size = 4; + using Alloc = CountingAllocator<int>; + using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>; + + int64_t allocated = 0; + int64_t active_instances = 0; + + { + const int ia[] = {0, 1, 2, 3, 4, 5, 6, 7}; + + Alloc alloc(&allocated, &active_instances); + + AllocFxdArr arr(ia, ia + inlined_size, alloc); + static_cast<void>(arr); + } + + EXPECT_EQ(allocated, 0); + EXPECT_EQ(active_instances, 0); +} + +TEST(AllocatorSupportTest, CountOutoflineAllocations) { + constexpr size_t inlined_size = 4; + using Alloc = CountingAllocator<int>; + using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>; + + int64_t allocated = 0; + int64_t active_instances = 0; + + { + const int ia[] = {0, 1, 2, 3, 4, 5, 6, 7}; + Alloc alloc(&allocated, &active_instances); + + AllocFxdArr arr(ia, ia + ABSL_ARRAYSIZE(ia), alloc); + + EXPECT_EQ(allocated, arr.size() * sizeof(int)); + static_cast<void>(arr); + } + + EXPECT_EQ(active_instances, 0); +} + +TEST(AllocatorSupportTest, CountCopyInlineAllocations) { + constexpr size_t inlined_size = 4; + using Alloc = CountingAllocator<int>; + using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>; + + int64_t allocated1 = 0; + int64_t allocated2 = 0; + int64_t active_instances = 0; + Alloc alloc(&allocated1, &active_instances); + Alloc alloc2(&allocated2, &active_instances); + + { + int initial_value = 1; + + AllocFxdArr arr1(inlined_size / 2, initial_value, alloc); + + EXPECT_EQ(allocated1, 0); + + AllocFxdArr arr2(arr1, alloc2); + + EXPECT_EQ(allocated2, 0); + static_cast<void>(arr1); + static_cast<void>(arr2); + } + + EXPECT_EQ(active_instances, 0); +} + +TEST(AllocatorSupportTest, CountCopyOutoflineAllocations) { + constexpr size_t inlined_size = 4; + using Alloc = CountingAllocator<int>; + using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>; + + int64_t allocated1 = 0; + int64_t allocated2 = 0; + int64_t active_instances = 0; + Alloc alloc(&allocated1, &active_instances); + Alloc alloc2(&allocated2, &active_instances); + + { + int initial_value = 1; + + AllocFxdArr arr1(inlined_size * 2, initial_value, alloc); + + EXPECT_EQ(allocated1, arr1.size() * sizeof(int)); + + AllocFxdArr arr2(arr1, alloc2); + + EXPECT_EQ(allocated2, inlined_size * 2 * sizeof(int)); + static_cast<void>(arr1); + static_cast<void>(arr2); + } + + EXPECT_EQ(active_instances, 0); +} + +TEST(AllocatorSupportTest, SizeValAllocConstructor) { + using testing::AllOf; + using testing::Each; + using testing::SizeIs; + + constexpr size_t inlined_size = 4; + using Alloc = CountingAllocator<int>; + using AllocFxdArr = absl::FixedArray<int, inlined_size, Alloc>; + + { + auto len = inlined_size / 2; + auto val = 0; + int64_t allocated = 0; + AllocFxdArr arr(len, val, Alloc(&allocated)); + + EXPECT_EQ(allocated, 0); + EXPECT_THAT(arr, AllOf(SizeIs(len), Each(0))); + } + + { + auto len = inlined_size * 2; + auto val = 0; + int64_t allocated = 0; + AllocFxdArr arr(len, val, Alloc(&allocated)); + + EXPECT_EQ(allocated, len * sizeof(int)); + EXPECT_THAT(arr, AllOf(SizeIs(len), Each(0))); + } +} + #ifdef ADDRESS_SANITIZER TEST(FixedArrayTest, AddressSanitizerAnnotations1) { absl::FixedArray<int, 32> a(10); @@ -655,5 +867,4 @@ TEST(FixedArrayTest, AddressSanitizerAnnotations4) { EXPECT_DEATH(raw[21] = ThreeInts(), "container-overflow"); } #endif // ADDRESS_SANITIZER - } // namespace diff --git a/absl/container/internal/compressed_tuple.h b/absl/container/internal/compressed_tuple.h new file mode 100644 index 00000000..cc52614f --- /dev/null +++ b/absl/container/internal/compressed_tuple.h @@ -0,0 +1,175 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// +// Helper class to perform the Empty Base Optimization. +// Ts can contain classes and non-classes, empty or not. For the ones that +// are empty classes, we perform the optimization. If all types in Ts are empty +// classes, then CompressedTuple<Ts...> is itself an empty class. +// +// To access the members, use member get<N>() function. +// +// Eg: +// absl::container_internal::CompressedTuple<int, T1, T2, T3> value(7, t1, t2, +// t3); +// assert(value.get<0>() == 7); +// T1& t1 = value.get<1>(); +// const T2& t2 = value.get<2>(); +// ... +// +// http://en.cppreference.com/w/cpp/language/ebo + +#ifndef ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_ +#define ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_ + +#include <tuple> +#include <type_traits> +#include <utility> + +#include "absl/utility/utility.h" + +#ifdef _MSC_VER +// We need to mark these classes with this declspec to ensure that +// CompressedTuple happens. +#define ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC __declspec(empty_bases) +#else // _MSC_VER +#define ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC +#endif // _MSC_VER + +namespace absl { +namespace container_internal { + +template <typename... Ts> +class CompressedTuple; + +namespace internal_compressed_tuple { + +template <typename D, size_t I> +struct Elem; +template <typename... B, size_t I> +struct Elem<CompressedTuple<B...>, I> + : std::tuple_element<I, std::tuple<B...>> {}; +template <typename D, size_t I> +using ElemT = typename Elem<D, I>::type; + +// Use the __is_final intrinsic if available. Where it's not available, classes +// declared with the 'final' specifier cannot be used as CompressedTuple +// elements. +// TODO(sbenza): Replace this with std::is_final in C++14. +template <typename T> +constexpr bool IsFinal() { +#if defined(__clang__) || defined(__GNUC__) + return __is_final(T); +#else + return false; +#endif +} + +template <typename T> +constexpr bool ShouldUseBase() { + return std::is_class<T>::value && std::is_empty<T>::value && !IsFinal<T>(); +} + +// The storage class provides two specializations: +// - For empty classes, it stores T as a base class. +// - For everything else, it stores T as a member. +template <typename D, size_t I, bool = ShouldUseBase<ElemT<D, I>>()> +struct Storage { + using T = ElemT<D, I>; + T value; + constexpr Storage() = default; + explicit constexpr Storage(T&& v) : value(absl::forward<T>(v)) {} + constexpr const T& get() const { return value; } + T& get() { return value; } +}; + +template <typename D, size_t I> +struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC Storage<D, I, true> + : ElemT<D, I> { + using T = internal_compressed_tuple::ElemT<D, I>; + constexpr Storage() = default; + explicit constexpr Storage(T&& v) : T(absl::forward<T>(v)) {} + constexpr const T& get() const { return *this; } + T& get() { return *this; } +}; + +template <typename D, typename I> +struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTupleImpl; + +template <typename... Ts, size_t... I> +struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC + CompressedTupleImpl<CompressedTuple<Ts...>, absl::index_sequence<I...>> + // We use the dummy identity function through std::integral_constant to + // convince MSVC of accepting and expanding I in that context. Without it + // you would get: + // error C3548: 'I': parameter pack cannot be used in this context + : Storage<CompressedTuple<Ts...>, + std::integral_constant<size_t, I>::value>... { + constexpr CompressedTupleImpl() = default; + explicit constexpr CompressedTupleImpl(Ts&&... args) + : Storage<CompressedTuple<Ts...>, I>(absl::forward<Ts>(args))... {} +}; + +} // namespace internal_compressed_tuple + +// Helper class to perform the Empty Base Class Optimization. +// Ts can contain classes and non-classes, empty or not. For the ones that +// are empty classes, we perform the CompressedTuple. If all types in Ts are +// empty classes, then CompressedTuple<Ts...> is itself an empty class. +// +// To access the members, use member .get<N>() function. +// +// Eg: +// absl::container_internal::CompressedTuple<int, T1, T2, T3> value(7, t1, t2, +// t3); +// assert(value.get<0>() == 7); +// T1& t1 = value.get<1>(); +// const T2& t2 = value.get<2>(); +// ... +// +// http://en.cppreference.com/w/cpp/language/ebo +template <typename... Ts> +class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple + : private internal_compressed_tuple::CompressedTupleImpl< + CompressedTuple<Ts...>, absl::index_sequence_for<Ts...>> { + private: + template <int I> + using ElemT = internal_compressed_tuple::ElemT<CompressedTuple, I>; + + public: + constexpr CompressedTuple() = default; + explicit constexpr CompressedTuple(Ts... base) + : CompressedTuple::CompressedTupleImpl(absl::forward<Ts>(base)...) {} + + template <int I> + ElemT<I>& get() { + return internal_compressed_tuple::Storage<CompressedTuple, I>::get(); + } + + template <int I> + constexpr const ElemT<I>& get() const { + return internal_compressed_tuple::Storage<CompressedTuple, I>::get(); + } +}; + +// Explicit specialization for a zero-element tuple +// (needed to avoid ambiguous overloads for the default constructor). +template <> +class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple<> {}; + +} // namespace container_internal +} // namespace absl + +#undef ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC + +#endif // ABSL_CONTAINER_INTERNAL_COMPRESSED_TUPLE_H_ diff --git a/absl/container/internal/compressed_tuple_test.cc b/absl/container/internal/compressed_tuple_test.cc new file mode 100644 index 00000000..45030c67 --- /dev/null +++ b/absl/container/internal/compressed_tuple_test.cc @@ -0,0 +1,166 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/container/internal/compressed_tuple.h" + +#include <string> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +namespace absl { +namespace container_internal { +namespace { + +template <int> +struct Empty {}; + +template <typename T> +struct NotEmpty { + T value; +}; + +template <typename T, typename U> +struct TwoValues { + T value1; + U value2; +}; + +TEST(CompressedTupleTest, Sizeof) { + EXPECT_EQ(sizeof(int), sizeof(CompressedTuple<int>)); + EXPECT_EQ(sizeof(int), sizeof(CompressedTuple<int, Empty<0>>)); + EXPECT_EQ(sizeof(int), sizeof(CompressedTuple<int, Empty<0>, Empty<1>>)); + EXPECT_EQ(sizeof(int), + sizeof(CompressedTuple<int, Empty<0>, Empty<1>, Empty<2>>)); + + EXPECT_EQ(sizeof(TwoValues<int, double>), + sizeof(CompressedTuple<int, NotEmpty<double>>)); + EXPECT_EQ(sizeof(TwoValues<int, double>), + sizeof(CompressedTuple<int, Empty<0>, NotEmpty<double>>)); + EXPECT_EQ(sizeof(TwoValues<int, double>), + sizeof(CompressedTuple<int, Empty<0>, NotEmpty<double>, Empty<1>>)); +} + +TEST(CompressedTupleTest, Access) { + struct S { + std::string x; + }; + CompressedTuple<int, Empty<0>, S> x(7, {}, S{"ABC"}); + EXPECT_EQ(sizeof(x), sizeof(TwoValues<int, S>)); + EXPECT_EQ(7, x.get<0>()); + EXPECT_EQ("ABC", x.get<2>().x); +} + +TEST(CompressedTupleTest, NonClasses) { + CompressedTuple<int, const char*> x(7, "ABC"); + EXPECT_EQ(7, x.get<0>()); + EXPECT_STREQ("ABC", x.get<1>()); +} + +TEST(CompressedTupleTest, MixClassAndNonClass) { + CompressedTuple<int, const char*, Empty<0>, NotEmpty<double>> x(7, "ABC", {}, + {1.25}); + struct Mock { + int v; + const char* p; + double d; + }; + EXPECT_EQ(sizeof(x), sizeof(Mock)); + EXPECT_EQ(7, x.get<0>()); + EXPECT_STREQ("ABC", x.get<1>()); + EXPECT_EQ(1.25, x.get<3>().value); +} + +TEST(CompressedTupleTest, Nested) { + CompressedTuple<int, CompressedTuple<int>, + CompressedTuple<int, CompressedTuple<int>>> + x(1, CompressedTuple<int>(2), + CompressedTuple<int, CompressedTuple<int>>(3, CompressedTuple<int>(4))); + EXPECT_EQ(1, x.get<0>()); + EXPECT_EQ(2, x.get<1>().get<0>()); + EXPECT_EQ(3, x.get<2>().get<0>()); + EXPECT_EQ(4, x.get<2>().get<1>().get<0>()); + + CompressedTuple<Empty<0>, Empty<0>, + CompressedTuple<Empty<0>, CompressedTuple<Empty<0>>>> + y; + std::set<Empty<0>*> empties{&y.get<0>(), &y.get<1>(), &y.get<2>().get<0>(), + &y.get<2>().get<1>().get<0>()}; +#ifdef _MSC_VER + // MSVC has a bug where many instances of the same base class are layed out in + // the same address when using __declspec(empty_bases). + // This will be fixed in a future version of MSVC. + int expected = 1; +#else + int expected = 4; +#endif + EXPECT_EQ(expected, sizeof(y)); + EXPECT_EQ(expected, empties.size()); + EXPECT_EQ(sizeof(y), sizeof(Empty<0>) * empties.size()); + + EXPECT_EQ(4 * sizeof(char), + sizeof(CompressedTuple<CompressedTuple<char, char>, + CompressedTuple<char, char>>)); + EXPECT_TRUE( + (std::is_empty<CompressedTuple<CompressedTuple<Empty<0>>, + CompressedTuple<Empty<1>>>>::value)); +} + +TEST(CompressedTupleTest, Reference) { + int i = 7; + std::string s = "Very long std::string that goes in the heap"; + CompressedTuple<int, int&, std::string, std::string&> x(i, i, s, s); + + // Sanity check. We should have not moved from `s` + EXPECT_EQ(s, "Very long std::string that goes in the heap"); + + EXPECT_EQ(x.get<0>(), x.get<1>()); + EXPECT_NE(&x.get<0>(), &x.get<1>()); + EXPECT_EQ(&x.get<1>(), &i); + + EXPECT_EQ(x.get<2>(), x.get<3>()); + EXPECT_NE(&x.get<2>(), &x.get<3>()); + EXPECT_EQ(&x.get<3>(), &s); +} + +TEST(CompressedTupleTest, NoElements) { + CompressedTuple<> x; + static_cast<void>(x); // Silence -Wunused-variable. + EXPECT_TRUE(std::is_empty<CompressedTuple<>>::value); +} + +TEST(CompressedTupleTest, Constexpr) { + constexpr CompressedTuple<int, double, CompressedTuple<int>> x( + 7, 1.25, CompressedTuple<int>(5)); + constexpr int x0 = x.get<0>(); + constexpr double x1 = x.get<1>(); + constexpr int x2 = x.get<2>().get<0>(); + EXPECT_EQ(x0, 7); + EXPECT_EQ(x1, 1.25); + EXPECT_EQ(x2, 5); +} + +#if defined(__clang__) || defined(__GNUC__) +TEST(CompressedTupleTest, EmptyFinalClass) { + struct S final { + int f() const { return 5; } + }; + CompressedTuple<S> x; + EXPECT_EQ(x.get<0>().f(), 5); +} +#endif + +} // namespace +} // namespace container_internal +} // namespace absl diff --git a/absl/memory/memory.h b/absl/memory/memory.h index f207169a..c7caf8b9 100644 --- a/absl/memory/memory.h +++ b/absl/memory/memory.h @@ -641,38 +641,56 @@ struct default_allocator_is_nothrow : std::false_type {}; #endif namespace memory_internal { -// TODO(b110200014): Implement proper backports -template <typename ForwardIt> -void DefaultConstruct(ForwardIt it) { - using value_type = typename std::iterator_traits<ForwardIt>::value_type; - ::new (static_cast<void*>(std::addressof(*it))) value_type; -} // namespace memory_internal - #ifdef ABSL_HAVE_EXCEPTIONS -template <typename ForwardIt, typename Size> -void uninitialized_default_construct_n(ForwardIt first, Size size) { - for (ForwardIt cur = first; size > 0; static_cast<void>(++cur), --size) { +template <typename Allocator, typename StorageElement, typename... Args> +void ConstructStorage(Allocator* alloc, StorageElement* first, + StorageElement* last, const Args&... args) { + for (StorageElement* cur = first; cur != last; ++cur) { + try { + std::allocator_traits<Allocator>::construct(*alloc, cur, args...); + } catch (...) { + while (cur != first) { + --cur; + std::allocator_traits<Allocator>::destroy(*alloc, cur); + } + throw; + } + } +} +template <typename Allocator, typename StorageElement, typename Iterator> +void CopyToStorageFromRange(Allocator* alloc, StorageElement* destination, + Iterator first, Iterator last) { + for (StorageElement* cur = destination; first != last; + static_cast<void>(++cur), static_cast<void>(++first)) { try { - absl::memory_internal::DefaultConstruct(cur); + std::allocator_traits<Allocator>::construct(*alloc, cur, *first); } catch (...) { - using value_type = typename std::iterator_traits<ForwardIt>::value_type; - for (; first != cur; ++first) { - first->~value_type(); + while (cur != destination) { + --cur; + std::allocator_traits<Allocator>::destroy(*alloc, cur); } throw; } } } #else // ABSL_HAVE_EXCEPTIONS -template <typename ForwardIt, typename Size> -void uninitialized_default_construct_n(ForwardIt first, Size size) { - for (; size > 0; static_cast<void>(++first), --size) { - absl::memory_internal::DefaultConstruct(first); +template <typename Allocator, typename StorageElement, typename... Args> +void ConstructStorage(Allocator* alloc, StorageElement* first, + StorageElement* last, const Args&... args) { + for (; first != last; ++first) { + std::allocator_traits<Allocator>::construct(*alloc, first, args...); + } +} +template <typename Allocator, typename StorageElement, typename Iterator> +void CopyToStorageFromRange(Allocator* alloc, StorageElement* destination, + Iterator first, Iterator last) { + for (; first != last; + static_cast<void>(++destination), static_cast<void>(++first)) { + std::allocator_traits<Allocator>::construct(*alloc, destination, *first); } } #endif // ABSL_HAVE_EXCEPTIONS } // namespace memory_internal - } // namespace absl #endif // ABSL_MEMORY_MEMORY_H_ diff --git a/absl/memory/memory_exception_safety_test.cc b/absl/memory/memory_exception_safety_test.cc index fb8b561d..d1f6e84f 100644 --- a/absl/memory/memory_exception_safety_test.cc +++ b/absl/memory/memory_exception_safety_test.cc @@ -48,16 +48,5 @@ TEST(MakeUnique, CheckForLeaks) { })); } -TEST(MemoryInternal, UninitDefaultConstructNNonTrivial) { - EXPECT_TRUE(testing::MakeExceptionSafetyTester() - .WithInitialValue(ThrowerList{}) - .WithOperation([&](ThrowerList* list_ptr) { - absl::memory_internal::uninitialized_default_construct_n( - list_ptr->data(), kLength); - }) - .WithInvariants([&](...) { return true; }) - .Test()); -} - } // namespace } // namespace absl diff --git a/absl/memory/memory_test.cc b/absl/memory/memory_test.cc index 8ff1945d..dee9b486 100644 --- a/absl/memory/memory_test.cc +++ b/absl/memory/memory_test.cc @@ -611,47 +611,4 @@ TEST(AllocatorNoThrowTest, CustomAllocator) { EXPECT_FALSE(absl::allocator_is_nothrow<UnspecifiedAllocator>::value); } -TEST(MemoryInternal, UninitDefaultConstructNTrivial) { - constexpr int kInitialValue = 123; - constexpr int kExpectedValue = kInitialValue; // Expect no-op behavior - constexpr int len = 5; - - struct TestObj { - int val; - }; - static_assert(absl::is_trivially_default_constructible<TestObj>::value, ""); - static_assert(absl::is_trivially_destructible<TestObj>::value, ""); - - TestObj objs[len]; - for (auto& obj : objs) { - obj.val = kInitialValue; - } - - absl::memory_internal::uninitialized_default_construct_n(objs, len); - for (auto& obj : objs) { - EXPECT_EQ(obj.val, kExpectedValue); - } -} - -TEST(MemoryInternal, UninitDefaultConstructNNonTrivial) { - constexpr int kInitialValue = 123; - constexpr int kExpectedValue = 0; // Expect value-construction behavior - constexpr int len = 5; - - struct TestObj { - int val{kExpectedValue}; - }; - static_assert(absl::is_trivially_destructible<TestObj>::value, ""); - - TestObj objs[len]; - for (auto& obj : objs) { - obj.val = kInitialValue; - } - - absl::memory_internal::uninitialized_default_construct_n(objs, len); - for (auto& obj : objs) { - EXPECT_EQ(obj.val, kExpectedValue); - } -} - } // namespace diff --git a/absl/meta/type_traits.h b/absl/meta/type_traits.h index 8d3264f1..457b8908 100644 --- a/absl/meta/type_traits.h +++ b/absl/meta/type_traits.h @@ -44,6 +44,7 @@ namespace absl { namespace type_traits_internal { + template <typename... Ts> struct VoidTImpl { using type = void; @@ -61,6 +62,49 @@ struct default_alignment_of_aligned_storage<Len, static constexpr size_t value = Align; }; +//////////////////////////////// +// Library Fundamentals V2 TS // +//////////////////////////////// + +// NOTE: The `is_detected` family of templates here differ from the library +// fundamentals specification in that for library fundamentals, `Op<Args...>` is +// evaluated as soon as the type `is_detected<Op, Args...>` undergoes +// substitution, regardless of whether or not the `::value` is accessed. That +// is inconsistent with all other standard traits and prevents lazy evaluation +// in larger contexts (such as if the `is_detected` check is a trailing argument +// of a `conjunction`. This implementation opts to instead be lazy in the same +// way that the standard traits are (this "defect" of the detection idiom +// specifications has been reported). + +template <class Enabler, template <class...> class Op, class... Args> +struct is_detected_impl { + using type = std::false_type; +}; + +template <template <class...> class Op, class... Args> +struct is_detected_impl<typename VoidTImpl<Op<Args...>>::type, Op, Args...> { + using type = std::true_type; +}; + +template <template <class...> class Op, class... Args> +struct is_detected : is_detected_impl<void, Op, Args...>::type {}; + +template <class Enabler, class To, template <class...> class Op, class... Args> +struct is_detected_convertible_impl { + using type = std::false_type; +}; + +template <class To, template <class...> class Op, class... Args> +struct is_detected_convertible_impl< + typename std::enable_if<std::is_convertible<Op<Args...>, To>::value>::type, + To, Op, Args...> { + using type = std::true_type; +}; + +template <class To, template <class...> class Op, class... Args> +struct is_detected_convertible + : is_detected_convertible_impl<void, To, Op, Args...>::type {}; + } // namespace type_traits_internal // void_t() diff --git a/absl/meta/type_traits_test.cc b/absl/meta/type_traits_test.cc index 9dd95429..81b4bd32 100644 --- a/absl/meta/type_traits_test.cc +++ b/absl/meta/type_traits_test.cc @@ -34,6 +34,83 @@ struct simple_pair { struct Dummy {}; +struct ReturnType {}; +struct ConvertibleToReturnType { + operator ReturnType() const; // NOLINT +}; + +// Unique types used as parameter types for testing the detection idiom. +struct StructA {}; +struct StructB {}; +struct StructC {}; + +struct TypeWithBarFunction { + template <class T, + absl::enable_if_t<std::is_same<T&&, StructA&>::value, int> = 0> + ReturnType bar(T&&, const StructB&, StructC&&) &&; // NOLINT +}; + +struct TypeWithBarFunctionAndConvertibleReturnType { + template <class T, + absl::enable_if_t<std::is_same<T&&, StructA&>::value, int> = 0> + ConvertibleToReturnType bar(T&&, const StructB&, StructC&&) &&; // NOLINT +}; + +template <class Class, class... Ts> +using BarIsCallableImpl = + decltype(std::declval<Class>().bar(std::declval<Ts>()...)); + +template <class Class, class... T> +using BarIsCallable = + absl::type_traits_internal::is_detected<BarIsCallableImpl, Class, T...>; + +template <class Class, class... T> +using BarIsCallableConv = absl::type_traits_internal::is_detected_convertible< + ReturnType, BarIsCallableImpl, Class, T...>; + +// NOTE: Test of detail type_traits_internal::is_detected. +TEST(IsDetectedTest, BasicUsage) { + EXPECT_TRUE((BarIsCallable<TypeWithBarFunction, StructA&, const StructB&, + StructC>::value)); + EXPECT_TRUE( + (BarIsCallable<TypeWithBarFunction, StructA&, StructB&, StructC>::value)); + EXPECT_TRUE( + (BarIsCallable<TypeWithBarFunction, StructA&, StructB, StructC>::value)); + + EXPECT_FALSE((BarIsCallable<int, StructA&, const StructB&, StructC>::value)); + EXPECT_FALSE((BarIsCallable<TypeWithBarFunction&, StructA&, const StructB&, + StructC>::value)); + EXPECT_FALSE((BarIsCallable<TypeWithBarFunction, StructA, const StructB&, + StructC>::value)); +} + +// NOTE: Test of detail type_traits_internal::is_detected_convertible. +TEST(IsDetectedConvertibleTest, BasicUsage) { + EXPECT_TRUE((BarIsCallableConv<TypeWithBarFunction, StructA&, const StructB&, + StructC>::value)); + EXPECT_TRUE((BarIsCallableConv<TypeWithBarFunction, StructA&, StructB&, + StructC>::value)); + EXPECT_TRUE((BarIsCallableConv<TypeWithBarFunction, StructA&, StructB, + StructC>::value)); + EXPECT_TRUE((BarIsCallableConv<TypeWithBarFunctionAndConvertibleReturnType, + StructA&, const StructB&, StructC>::value)); + EXPECT_TRUE((BarIsCallableConv<TypeWithBarFunctionAndConvertibleReturnType, + StructA&, StructB&, StructC>::value)); + EXPECT_TRUE((BarIsCallableConv<TypeWithBarFunctionAndConvertibleReturnType, + StructA&, StructB, StructC>::value)); + + EXPECT_FALSE( + (BarIsCallableConv<int, StructA&, const StructB&, StructC>::value)); + EXPECT_FALSE((BarIsCallableConv<TypeWithBarFunction&, StructA&, + const StructB&, StructC>::value)); + EXPECT_FALSE((BarIsCallableConv<TypeWithBarFunction, StructA, const StructB&, + StructC>::value)); + EXPECT_FALSE((BarIsCallableConv<TypeWithBarFunctionAndConvertibleReturnType&, + StructA&, const StructB&, StructC>::value)); + EXPECT_FALSE((BarIsCallableConv<TypeWithBarFunctionAndConvertibleReturnType, + StructA, const StructB&, StructC>::value)); +} + TEST(VoidTTest, BasicUsage) { StaticAssertTypeEq<void, absl::void_t<Dummy>>(); StaticAssertTypeEq<void, absl::void_t<Dummy, Dummy, Dummy>>(); @@ -718,8 +795,8 @@ TEST(TypeTraitsTest, TestDecay) { ABSL_INTERNAL_EXPECT_ALIAS_EQUIVALENCE(decay, int[][1]); ABSL_INTERNAL_EXPECT_ALIAS_EQUIVALENCE(decay, int()); - ABSL_INTERNAL_EXPECT_ALIAS_EQUIVALENCE(decay, int(float)); - ABSL_INTERNAL_EXPECT_ALIAS_EQUIVALENCE(decay, int(char, ...)); + ABSL_INTERNAL_EXPECT_ALIAS_EQUIVALENCE(decay, int(float)); // NOLINT + ABSL_INTERNAL_EXPECT_ALIAS_EQUIVALENCE(decay, int(char, ...)); // NOLINT } struct TypeA {}; diff --git a/absl/strings/numbers_test.cc b/absl/strings/numbers_test.cc index 24e7138c..8ebb090e 100644 --- a/absl/strings/numbers_test.cc +++ b/absl/strings/numbers_test.cc @@ -56,16 +56,11 @@ using testing::Eq; using testing::MatchesRegex; // Number of floats to test with. -// 10,000,000 is a reasonable default for a test that only takes a few seconds. +// 5,000,000 is a reasonable default for a test that only takes a few seconds. // 1,000,000,000+ triggers checking for all possible mantissa values for // double-precision tests. 2,000,000,000+ triggers checking for every possible // single-precision float. -#ifdef _MSC_VER -// Use a smaller number on MSVC to avoid test time out (1 min) const int kFloatNumCases = 5000000; -#else -const int kFloatNumCases = 10000000; -#endif // This is a slow, brute-force routine to compute the exact base-10 // representation of a double-precision floating-point number. It diff --git a/absl/time/duration.cc b/absl/time/duration.cc index c13fa79b..f402137b 100644 --- a/absl/time/duration.cc +++ b/absl/time/duration.cc @@ -895,13 +895,10 @@ bool ParseDuration(const std::string& dur_string, Duration* d) { *d = dur; return true; } - bool ParseFlag(const std::string& text, Duration* dst, std::string* ) { return ParseDuration(text, dst); } -std::string UnparseFlag(Duration d) { - return FormatDuration(d); -} +std::string UnparseFlag(Duration d) { return FormatDuration(d); } } // namespace absl diff --git a/absl/time/duration_benchmark.cc b/absl/time/duration_benchmark.cc index 54f89a1f..d5657bd5 100644 --- a/absl/time/duration_benchmark.cc +++ b/absl/time/duration_benchmark.cc @@ -27,47 +27,113 @@ namespace { // void BM_Duration_Factory_Nanoseconds(benchmark::State& state) { + int64_t i = 0; while (state.KeepRunning()) { - benchmark::DoNotOptimize(absl::Nanoseconds(1)); + benchmark::DoNotOptimize(absl::Nanoseconds(i)); + i += 314159; } } BENCHMARK(BM_Duration_Factory_Nanoseconds); void BM_Duration_Factory_Microseconds(benchmark::State& state) { + int64_t i = 0; while (state.KeepRunning()) { - benchmark::DoNotOptimize(absl::Microseconds(1)); + benchmark::DoNotOptimize(absl::Microseconds(i)); + i += 314; } } BENCHMARK(BM_Duration_Factory_Microseconds); void BM_Duration_Factory_Milliseconds(benchmark::State& state) { + int64_t i = 0; while (state.KeepRunning()) { - benchmark::DoNotOptimize(absl::Milliseconds(1)); + benchmark::DoNotOptimize(absl::Milliseconds(i)); + i += 1; } } BENCHMARK(BM_Duration_Factory_Milliseconds); void BM_Duration_Factory_Seconds(benchmark::State& state) { + int64_t i = 0; while (state.KeepRunning()) { - benchmark::DoNotOptimize(absl::Seconds(1)); + benchmark::DoNotOptimize(absl::Seconds(i)); + i += 1; } } BENCHMARK(BM_Duration_Factory_Seconds); void BM_Duration_Factory_Minutes(benchmark::State& state) { + int64_t i = 0; while (state.KeepRunning()) { - benchmark::DoNotOptimize(absl::Minutes(1)); + benchmark::DoNotOptimize(absl::Minutes(i)); + i += 1; } } BENCHMARK(BM_Duration_Factory_Minutes); void BM_Duration_Factory_Hours(benchmark::State& state) { + int64_t i = 0; while (state.KeepRunning()) { - benchmark::DoNotOptimize(absl::Hours(1)); + benchmark::DoNotOptimize(absl::Hours(i)); + i += 1; } } BENCHMARK(BM_Duration_Factory_Hours); +void BM_Duration_Factory_DoubleNanoseconds(benchmark::State& state) { + double d = 1; + while (state.KeepRunning()) { + benchmark::DoNotOptimize(absl::Nanoseconds(d)); + d = d * 1.00000001 + 1; + } +} +BENCHMARK(BM_Duration_Factory_DoubleNanoseconds); + +void BM_Duration_Factory_DoubleMicroseconds(benchmark::State& state) { + double d = 1e-3; + while (state.KeepRunning()) { + benchmark::DoNotOptimize(absl::Microseconds(d)); + d = d * 1.00000001 + 1e-3; + } +} +BENCHMARK(BM_Duration_Factory_DoubleMicroseconds); + +void BM_Duration_Factory_DoubleMilliseconds(benchmark::State& state) { + double d = 1e-6; + while (state.KeepRunning()) { + benchmark::DoNotOptimize(absl::Milliseconds(d)); + d = d * 1.00000001 + 1e-6; + } +} +BENCHMARK(BM_Duration_Factory_DoubleMilliseconds); + +void BM_Duration_Factory_DoubleSeconds(benchmark::State& state) { + double d = 1e-9; + while (state.KeepRunning()) { + benchmark::DoNotOptimize(absl::Seconds(d)); + d = d * 1.00000001 + 1e-9; + } +} +BENCHMARK(BM_Duration_Factory_DoubleSeconds); + +void BM_Duration_Factory_DoubleMinutes(benchmark::State& state) { + double d = 1e-9; + while (state.KeepRunning()) { + benchmark::DoNotOptimize(absl::Minutes(d)); + d = d * 1.00000001 + 1e-9; + } +} +BENCHMARK(BM_Duration_Factory_DoubleMinutes); + +void BM_Duration_Factory_DoubleHours(benchmark::State& state) { + double d = 1e-9; + while (state.KeepRunning()) { + benchmark::DoNotOptimize(absl::Hours(d)); + d = d * 1.00000001 + 1e-9; + } +} +BENCHMARK(BM_Duration_Factory_DoubleHours); + // // Arithmetic // diff --git a/absl/time/duration_test.cc b/absl/time/duration_test.cc index 704684ed..7ae25dc6 100644 --- a/absl/time/duration_test.cc +++ b/absl/time/duration_test.cc @@ -16,7 +16,9 @@ #include <cmath> #include <cstdint> #include <ctime> +#include <iomanip> #include <limits> +#include <random> #include <string> #include "gmock/gmock.h" @@ -105,22 +107,22 @@ TEST(Duration, Factories) { } TEST(Duration, ToConversion) { -#define TEST_DURATION_CONVERSION(UNIT) \ - do { \ - const absl::Duration d = absl::UNIT(1.5); \ - const absl::Duration z = absl::ZeroDuration(); \ - const absl::Duration inf = absl::InfiniteDuration(); \ - const double dbl_inf = std::numeric_limits<double>::infinity(); \ - EXPECT_EQ(kint64min, absl::ToInt64##UNIT(-inf)); \ - EXPECT_EQ(-1, absl::ToInt64##UNIT(-d)); \ - EXPECT_EQ(0, absl::ToInt64##UNIT(z)); \ - EXPECT_EQ(1, absl::ToInt64##UNIT(d)); \ - EXPECT_EQ(kint64max, absl::ToInt64##UNIT(inf)); \ - EXPECT_EQ(-dbl_inf, absl::ToDouble##UNIT(-inf)); \ - EXPECT_EQ(-1.5, absl::ToDouble##UNIT(-d)); \ - EXPECT_EQ(0, absl::ToDouble##UNIT(z)); \ - EXPECT_EQ(1.5, absl::ToDouble##UNIT(d)); \ - EXPECT_EQ(dbl_inf, absl::ToDouble##UNIT(inf)); \ +#define TEST_DURATION_CONVERSION(UNIT) \ + do { \ + const absl::Duration d = absl::UNIT(1.5); \ + constexpr absl::Duration z = absl::ZeroDuration(); \ + constexpr absl::Duration inf = absl::InfiniteDuration(); \ + constexpr double dbl_inf = std::numeric_limits<double>::infinity(); \ + EXPECT_EQ(kint64min, absl::ToInt64##UNIT(-inf)); \ + EXPECT_EQ(-1, absl::ToInt64##UNIT(-d)); \ + EXPECT_EQ(0, absl::ToInt64##UNIT(z)); \ + EXPECT_EQ(1, absl::ToInt64##UNIT(d)); \ + EXPECT_EQ(kint64max, absl::ToInt64##UNIT(inf)); \ + EXPECT_EQ(-dbl_inf, absl::ToDouble##UNIT(-inf)); \ + EXPECT_EQ(-1.5, absl::ToDouble##UNIT(-d)); \ + EXPECT_EQ(0, absl::ToDouble##UNIT(z)); \ + EXPECT_EQ(1.5, absl::ToDouble##UNIT(d)); \ + EXPECT_EQ(dbl_inf, absl::ToDouble##UNIT(inf)); \ } while (0) TEST_DURATION_CONVERSION(Nanoseconds); @@ -1284,6 +1286,16 @@ TEST(Duration, SmallConversions) { EXPECT_EQ(absl::Nanoseconds(1), absl::Seconds(0.875e-9)); EXPECT_EQ(absl::Nanoseconds(1), absl::Seconds(1.000e-9)); + EXPECT_EQ(absl::ZeroDuration(), absl::Seconds(-0.124999999e-9)); + EXPECT_EQ(-absl::Nanoseconds(1) / 4, absl::Seconds(-0.125e-9)); + EXPECT_EQ(-absl::Nanoseconds(1) / 4, absl::Seconds(-0.250e-9)); + EXPECT_EQ(-absl::Nanoseconds(1) / 2, absl::Seconds(-0.375e-9)); + EXPECT_EQ(-absl::Nanoseconds(1) / 2, absl::Seconds(-0.500e-9)); + EXPECT_EQ(-absl::Nanoseconds(3) / 4, absl::Seconds(-0.625e-9)); + EXPECT_EQ(-absl::Nanoseconds(3) / 4, absl::Seconds(-0.750e-9)); + EXPECT_EQ(-absl::Nanoseconds(1), absl::Seconds(-0.875e-9)); + EXPECT_EQ(-absl::Nanoseconds(1), absl::Seconds(-1.000e-9)); + timespec ts; ts.tv_sec = 0; ts.tv_nsec = 0; @@ -1313,6 +1325,86 @@ TEST(Duration, SmallConversions) { EXPECT_THAT(ToTimeval(absl::Nanoseconds(2000)), TimevalMatcher(tv)); } +void VerifySameAsMul(double time_as_seconds, int* const misses) { + auto direct_seconds = absl::Seconds(time_as_seconds); + auto mul_by_one_second = time_as_seconds * absl::Seconds(1); + if (direct_seconds != mul_by_one_second) { + if (*misses > 10) return; + ASSERT_LE(++(*misses), 10) << "Too many errors, not reporting more."; + EXPECT_EQ(direct_seconds, mul_by_one_second) + << "given double time_as_seconds = " << std::setprecision(17) + << time_as_seconds; + } +} + +// For a variety of interesting durations, we find the exact point +// where one double converts to that duration, and the very next double +// converts to the next duration. For both of those points, verify that +// Seconds(point) returns the same duration as point * Seconds(1.0) +TEST(Duration, ToDoubleSecondsCheckEdgeCases) { + constexpr uint32_t kTicksPerSecond = absl::time_internal::kTicksPerSecond; + constexpr auto duration_tick = absl::time_internal::MakeDuration(0, 1u); + int misses = 0; + for (int64_t seconds = 0; seconds < 99; ++seconds) { + uint32_t tick_vals[] = {0, +999, +999999, +999999999, kTicksPerSecond - 1, + 0, 1000, 1000000, 1000000000, kTicksPerSecond, + 1, 1001, 1000001, 1000000001, kTicksPerSecond + 1, + 2, 1002, 1000002, 1000000002, kTicksPerSecond + 2, + 3, 1003, 1000003, 1000000003, kTicksPerSecond + 3, + 4, 1004, 1000004, 1000000004, kTicksPerSecond + 4, + 5, 6, 7, 8, 9}; + for (uint32_t ticks : tick_vals) { + absl::Duration s_plus_t = absl::Seconds(seconds) + ticks * duration_tick; + for (absl::Duration d : {s_plus_t, -s_plus_t}) { + absl::Duration after_d = d + duration_tick; + EXPECT_NE(d, after_d); + EXPECT_EQ(after_d - d, duration_tick); + + double low_edge = ToDoubleSeconds(d); + EXPECT_EQ(d, absl::Seconds(low_edge)); + + double high_edge = ToDoubleSeconds(after_d); + EXPECT_EQ(after_d, absl::Seconds(high_edge)); + + for (;;) { + double midpoint = low_edge + (high_edge - low_edge) / 2; + if (midpoint == low_edge || midpoint == high_edge) break; + absl::Duration mid_duration = absl::Seconds(midpoint); + if (mid_duration == d) { + low_edge = midpoint; + } else { + EXPECT_EQ(mid_duration, after_d); + high_edge = midpoint; + } + } + // Now low_edge is the highest double that converts to Duration d, + // and high_edge is the lowest double that converts to Duration after_d. + VerifySameAsMul(low_edge, &misses); + VerifySameAsMul(high_edge, &misses); + } + } + } +} + +TEST(Duration, ToDoubleSecondsCheckRandom) { + std::random_device rd; + std::seed_seq seed({rd(), rd(), rd(), rd(), rd(), rd(), rd(), rd()}); + std::mt19937_64 gen(seed); + // We want doubles distributed from 1/8ns up to 2^63, where + // as many values are tested from 1ns to 2ns as from 1sec to 2sec, + // so even distribute along a log-scale of those values, and + // exponentiate before using them. (9.223377e+18 is just slightly + // out of bounds for absl::Duration.) + std::uniform_real_distribution<double> uniform(std::log(0.125e-9), + std::log(9.223377e+18)); + int misses = 0; + for (int i = 0; i < 1000000; ++i) { + double d = std::exp(uniform(gen)); + VerifySameAsMul(d, &misses); + VerifySameAsMul(-d, &misses); + } +} + TEST(Duration, ConversionSaturation) { absl::Duration d; diff --git a/absl/time/time.h b/absl/time/time.h index 880fc783..c41cb89c 100644 --- a/absl/time/time.h +++ b/absl/time/time.h @@ -81,6 +81,7 @@ constexpr int64_t GetRepHi(Duration d); constexpr uint32_t GetRepLo(Duration d); constexpr Duration MakeDuration(int64_t hi, uint32_t lo); constexpr Duration MakeDuration(int64_t hi, int64_t lo); +inline Duration MakePosDoubleDuration(double n); constexpr int64_t kTicksPerNanosecond = 4; constexpr int64_t kTicksPerSecond = 1000 * 1000 * 1000 * kTicksPerNanosecond; template <std::intmax_t N> @@ -295,6 +296,39 @@ Duration Floor(Duration d, Duration unit); // absl::Duration c = absl::Ceil(d, absl::Microseconds(1)); // 123457us Duration Ceil(Duration d, Duration unit); +// InfiniteDuration() +// +// Returns an infinite `Duration`. To get a `Duration` representing negative +// infinity, use `-InfiniteDuration()`. +// +// Duration arithmetic overflows to +/- infinity and saturates. In general, +// arithmetic with `Duration` infinities is similar to IEEE 754 infinities +// except where IEEE 754 NaN would be involved, in which case +/- +// `InfiniteDuration()` is used in place of a "nan" Duration. +// +// Examples: +// +// constexpr absl::Duration inf = absl::InfiniteDuration(); +// const absl::Duration d = ... any finite duration ... +// +// inf == inf + inf +// inf == inf + d +// inf == inf - inf +// -inf == d - inf +// +// inf == d * 1e100 +// inf == inf / 2 +// 0 == d / inf +// INT64_MAX == inf / d +// +// // Division by zero returns infinity, or INT64_MIN/MAX where appropriate. +// inf == d / 0 +// INT64_MAX == d / absl::ZeroDuration() +// +// The examples involving the `/` operator above also apply to `IDivDuration()` +// and `FDivDuration()`. +constexpr Duration InfiniteDuration(); + // Nanoseconds() // Microseconds() // Milliseconds() @@ -344,7 +378,13 @@ Duration Milliseconds(T n) { } template <typename T, time_internal::EnableIfFloat<T> = 0> Duration Seconds(T n) { - return n * Seconds(1); + if (n >= 0) { + if (n >= std::numeric_limits<int64_t>::max()) return InfiniteDuration(); + return time_internal::MakePosDoubleDuration(n); + } else { + if (n <= std::numeric_limits<int64_t>::min()) return -InfiniteDuration(); + return -time_internal::MakePosDoubleDuration(-n); + } } template <typename T, time_internal::EnableIfFloat<T> = 0> Duration Minutes(T n) { @@ -439,39 +479,6 @@ std::chrono::seconds ToChronoSeconds(Duration d); std::chrono::minutes ToChronoMinutes(Duration d); std::chrono::hours ToChronoHours(Duration d); -// InfiniteDuration() -// -// Returns an infinite `Duration`. To get a `Duration` representing negative -// infinity, use `-InfiniteDuration()`. -// -// Duration arithmetic overflows to +/- infinity and saturates. In general, -// arithmetic with `Duration` infinities is similar to IEEE 754 infinities -// except where IEEE 754 NaN would be involved, in which case +/- -// `InfiniteDuration()` is used in place of a "nan" Duration. -// -// Examples: -// -// constexpr absl::Duration inf = absl::InfiniteDuration(); -// const absl::Duration d = ... any finite duration ... -// -// inf == inf + inf -// inf == inf + d -// inf == inf - inf -// -inf == d - inf -// -// inf == d * 1e100 -// inf == inf / 2 -// 0 == d / inf -// INT64_MAX == inf / d -// -// // Division by zero returns infinity, or INT64_MIN/MAX where appropriate. -// inf == d / 0 -// INT64_MAX == d / absl::ZeroDuration() -// -// The examples involving the `/` operator above also apply to `IDivDuration()` -// and `FDivDuration()`. -constexpr Duration InfiniteDuration(); - // FormatDuration() // // Returns a std::string representing the duration in the form "72h3m0.5s". @@ -492,12 +499,9 @@ inline std::ostream& operator<<(std::ostream& os, Duration d) { // `ZeroDuration()`. Parses "inf" and "-inf" as +/- `InfiniteDuration()`. bool ParseDuration(const std::string& dur_string, Duration* d); -// ParseFlag() -// +// Support for flag values of type Duration. Duration flags must be specified +// in a format that is valid input for absl::ParseDuration(). bool ParseFlag(const std::string& text, Duration* dst, std::string* error); - -// UnparseFlag() -// std::string UnparseFlag(Duration d); // Time @@ -991,9 +995,6 @@ bool ParseTime(const std::string& format, const std::string& input, Time* time, bool ParseTime(const std::string& format, const std::string& input, TimeZone tz, Time* time, std::string* err); -// ParseFlag() -// UnparseFlag() -// // Support for flag values of type Time. Time flags must be specified in a // format that matches absl::RFC3339_full. For example: // @@ -1114,6 +1115,18 @@ constexpr Duration MakeDuration(int64_t hi, int64_t lo) { return MakeDuration(hi, static_cast<uint32_t>(lo)); } +// Make a Duration value from a floating-point number, as long as that number +// is in the range [ 0 .. numeric_limits<int64_t>::max ), that is, as long as +// it's positive and can be converted to int64_t without risk of UB. +inline Duration MakePosDoubleDuration(double n) { + const int64_t int_secs = static_cast<int64_t>(n); + const uint32_t ticks = + static_cast<uint32_t>((n - int_secs) * kTicksPerSecond + 0.5); + return ticks < kTicksPerSecond + ? MakeDuration(int_secs, ticks) + : MakeDuration(int_secs + 1, ticks - kTicksPerSecond); +} + // Creates a normalized Duration from an almost-normalized (sec,ticks) // pair. sec may be positive or negative. ticks must be in the range // -kTicksPerSecond < *ticks < kTicksPerSecond. If ticks is negative it diff --git a/absl/types/internal/variant.h b/absl/types/internal/variant.h index 7db5e053..7708e67c 100644 --- a/absl/types/internal/variant.h +++ b/absl/types/internal/variant.h @@ -1062,32 +1062,6 @@ struct OverloadSet<> { static void Overload(...); }; -//////////////////////////////// -// Library Fundamentals V2 TS // -//////////////////////////////// - -// TODO(calabrese): Consider moving this to absl/meta/type_traits.h - -// The following is a rough implementation of parts of the detection idiom. -// It is used for the comparison operator checks. - -template <class Enabler, class To, template <class...> class Op, class... Args> -struct is_detected_convertible_impl { - using type = std::false_type; -}; - -template <class To, template <class...> class Op, class... Args> -struct is_detected_convertible_impl< - absl::enable_if_t<std::is_convertible<Op<Args...>, To>::value>, To, Op, - Args...> { - using type = std::true_type; -}; - -// NOTE: This differs from library fundamentals by being lazy. -template <class To, template <class...> class Op, class... Args> -struct is_detected_convertible - : is_detected_convertible_impl<void, To, Op, Args...>::type {}; - template <class T> using LessThanResult = decltype(std::declval<T>() < std::declval<T>()); @@ -1107,6 +1081,8 @@ using EqualResult = decltype(std::declval<T>() == std::declval<T>()); template <class T> using NotEqualResult = decltype(std::declval<T>() != std::declval<T>()); +using type_traits_internal::is_detected_convertible; + template <class... T> using RequireAllHaveEqualT = absl::enable_if_t< absl::conjunction<is_detected_convertible<bool, EqualResult, T>...>::value, |