diff options
Diffstat (limited to 'src/third_party/abseil-cpp-master')
94 files changed, 2944 insertions, 1312 deletions
diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/CMake/AbseilHelpers.cmake b/src/third_party/abseil-cpp-master/abseil-cpp/CMake/AbseilHelpers.cmake index d4870365639..e4289c11689 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/CMake/AbseilHelpers.cmake +++ b/src/third_party/abseil-cpp-master/abseil-cpp/CMake/AbseilHelpers.cmake @@ -15,6 +15,7 @@ # include(CMakeParseArguments) +include(AbseilConfigureCopts) # The IDE folder for Abseil that will be used if Abseil is included in a CMake # project that sets @@ -48,7 +49,11 @@ function(absl_library) add_library(${_NAME} STATIC ${ABSL_LIB_SOURCES}) - target_compile_options(${_NAME} PRIVATE ${ABSL_LIB_PRIVATE_COMPILE_FLAGS}) + target_compile_options(${_NAME} + PRIVATE + ${ABSL_LIB_PRIVATE_COMPILE_FLAGS} + ${ABSL_DEFAULT_COPTS} + ) target_link_libraries(${_NAME} PUBLIC ${ABSL_LIB_PUBLIC_LIBRARIES}) target_include_directories(${_NAME} PUBLIC ${ABSL_COMMON_INCLUDE_DIRS} ${ABSL_LIB_PUBLIC_INCLUDE_DIRS} @@ -57,12 +62,14 @@ function(absl_library) # Add all Abseil targets to a a folder in the IDE for organization. set_property(TARGET ${_NAME} PROPERTY FOLDER ${ABSL_IDE_FOLDER}) + set_property(TARGET ${_NAME} PROPERTY CXX_STANDARD ${ABSL_CXX_STANDARD}) + set_property(TARGET ${_NAME} PROPERTY CXX_STANDARD_REQUIRED ON) + if(ABSL_LIB_EXPORT_NAME) add_library(absl::${ABSL_LIB_EXPORT_NAME} ALIAS ${_NAME}) endif() endfunction() -# # CMake function to imitate Bazel's cc_library rule. # # Parameters: @@ -74,17 +81,17 @@ endfunction() # DEFINES: List of public defines # LINKOPTS: List of link options # PUBLIC: Add this so that this library will be exported under absl:: (see Note). +# Also in IDE, target will appear in Abseil folder while non PUBLIC will be in Abseil/internal. # TESTONLY: When added, this target will only be built if user passes -DABSL_RUN_TESTS=ON to CMake. # # Note: -# # By default, absl_cc_library will always create a library named absl_internal_${NAME}, -# which means other targets can only depend this library as absl_internal_${NAME}, not ${NAME}. +# and alias target absl::${NAME}. # This is to reduce namespace pollution. # # absl_cc_library( # NAME -# awesome_lib +# awesome # HDRS # "a.h" # SRCS @@ -96,11 +103,11 @@ endfunction() # SRCS # "b.cc" # DEPS -# absl_internal_awesome_lib # not "awesome_lib"! +# absl_internal_awesome # not "awesome"! # ) # # If PUBLIC is set, absl_cc_library will instead create a target named -# absl_${NAME} and an alias absl::${NAME}. +# absl_${NAME} and still an alias absl::${NAME}. # # absl_cc_library( # NAME @@ -112,7 +119,6 @@ endfunction() # User can then use the library as absl::main_lib (although absl_main_lib is defined too). # # TODO: Implement "ALWAYSLINK" - function(absl_cc_library) cmake_parse_arguments(ABSL_CC_LIB "DISABLE_INSTALL;PUBLIC;TESTONLY" @@ -129,7 +135,9 @@ function(absl_cc_library) endif() # Check if this is a header-only library - if ("${ABSL_CC_LIB_SRCS}" STREQUAL "") + set(ABSL_CC_SRCS "${ABSL_CC_LIB_SRCS}") + list(FILTER ABSL_CC_SRCS EXCLUDE REGEX ".*\\.h") + if ("${ABSL_CC_SRCS}" STREQUAL "") set(ABSL_CC_LIB_IS_INTERFACE 1) else() set(ABSL_CC_LIB_IS_INTERFACE 0) @@ -149,23 +157,107 @@ function(absl_cc_library) target_compile_definitions(${_NAME} PUBLIC ${ABSL_CC_LIB_DEFINES}) # Add all Abseil targets to a a folder in the IDE for organization. - set_property(TARGET ${_NAME} PROPERTY FOLDER ${ABSL_IDE_FOLDER}) + if(ABSL_CC_LIB_PUBLIC) + set_property(TARGET ${_NAME} PROPERTY FOLDER ${ABSL_IDE_FOLDER}) + elseif(ABSL_CC_LIB_TESTONLY) + set_property(TARGET ${_NAME} PROPERTY FOLDER ${ABSL_IDE_FOLDER}/test) + else() + set_property(TARGET ${_NAME} PROPERTY FOLDER ${ABSL_IDE_FOLDER}/internal) + endif() + + # INTERFACE libraries can't have the CXX_STANDARD property set + set_property(TARGET ${_NAME} PROPERTY CXX_STANDARD ${ABSL_CXX_STANDARD}) + set_property(TARGET ${_NAME} PROPERTY CXX_STANDARD_REQUIRED ON) else() # Generating header-only library add_library(${_NAME} INTERFACE) - target_include_directories(${_NAME} INTERFACE ${ABSL_COMMON_INCLUDE_DIRS}) + target_include_directories(${_NAME} + INTERFACE ${ABSL_COMMON_INCLUDE_DIRS}) target_link_libraries(${_NAME} INTERFACE ${ABSL_CC_LIB_DEPS} ${ABSL_CC_LIB_LINKOPTS} ) target_compile_definitions(${_NAME} INTERFACE ${ABSL_CC_LIB_DEFINES}) endif() - if(ABSL_CC_LIB_PUBLIC) - add_library(absl::${ABSL_CC_LIB_NAME} ALIAS ${_NAME}) - endif() + add_library(absl::${ABSL_CC_LIB_NAME} ALIAS ${_NAME}) endif() endfunction() +# absl_cc_test() +# +# CMake function to imitate Bazel's cc_test rule. +# +# Parameters: +# NAME: name of target (see Usage below) +# SRCS: List of source files for the binary +# DEPS: List of other libraries to be linked in to the binary targets +# COPTS: List of private compile options +# DEFINES: List of public defines +# LINKOPTS: List of link options +# +# Note: +# By default, absl_cc_test will always create a binary named absl_${NAME}. +# This will also add it to ctest list as absl_${NAME}. +# +# Usage: +# absl_cc_library( +# NAME +# awesome +# HDRS +# "a.h" +# SRCS +# "a.cc" +# PUBLIC +# ) +# +# absl_cc_test( +# NAME +# awesome_test +# SRCS +# "awesome_test.cc" +# DEPS +# absl::awesome +# gmock +# gtest_main +# ) +function(absl_cc_test) + if(NOT ABSL_RUN_TESTS) + return() + endif() + + cmake_parse_arguments(ABSL_CC_TEST + "" + "NAME" + "SRCS;COPTS;DEFINES;LINKOPTS;DEPS" + ${ARGN} + ) + + set(_NAME "absl_${ABSL_CC_TEST_NAME}") + add_executable(${_NAME} "") + target_sources(${_NAME} PRIVATE ${ABSL_CC_TEST_SRCS}) + target_include_directories(${_NAME} + PUBLIC ${ABSL_COMMON_INCLUDE_DIRS} + PRIVATE ${GMOCK_INCLUDE_DIRS} ${GTEST_INCLUDE_DIRS} + ) + target_compile_definitions(${_NAME} + PUBLIC ${ABSL_CC_TEST_DEFINES} + ) + target_compile_options(${_NAME} + PRIVATE ${ABSL_CC_TEST_COPTS} + ) + target_link_libraries(${_NAME} + PUBLIC ${ABSL_CC_TEST_DEPS} + PRIVATE ${ABSL_CC_TEST_LINKOPTS} + ) + # Add all Abseil targets to a a folder in the IDE for organization. + set_property(TARGET ${_NAME} PROPERTY FOLDER ${ABSL_IDE_FOLDER}/test) + + set_property(TARGET ${_NAME} PROPERTY CXX_STANDARD ${ABSL_CXX_STANDARD}) + set_property(TARGET ${_NAME} PROPERTY CXX_STANDARD_REQUIRED ON) + + add_test(NAME ${_NAME} COMMAND ${_NAME}) +endfunction() + # # header only virtual target creation # @@ -205,13 +297,15 @@ function(absl_header_library) # Add all Abseil targets to a a folder in the IDE for organization. set_property(TARGET ${_NAME} PROPERTY FOLDER ${ABSL_IDE_FOLDER}) + set_property(TARGET ${_NAME} PROPERTY CXX_STANDARD ${ABSL_CXX_STANDARD}) + set_property(TARGET ${_NAME} PROPERTY CXX_STANDARD_REQUIRED ON) + if(ABSL_HO_LIB_EXPORT_NAME) add_library(absl::${ABSL_HO_LIB_EXPORT_NAME} ALIAS ${_NAME}) endif() endfunction() - # # create an abseil unit_test and add it to the executed test list # @@ -239,22 +333,29 @@ function(absl_test) if(ABSL_RUN_TESTS) - set(_NAME ${ABSL_TEST_TARGET}) + set(_NAME "absl_${ABSL_TEST_TARGET}") string(TOUPPER ${_NAME} _UPPER_NAME) - add_executable(${_NAME}_bin ${ABSL_TEST_SOURCES}) + add_executable(${_NAME} ${ABSL_TEST_SOURCES}) - target_compile_options(${_NAME}_bin PRIVATE ${ABSL_TEST_PRIVATE_COMPILE_FLAGS}) - target_link_libraries(${_NAME}_bin PUBLIC ${ABSL_TEST_PUBLIC_LIBRARIES} ${ABSL_TEST_COMMON_LIBRARIES}) - target_include_directories(${_NAME}_bin + target_compile_options(${_NAME} + PRIVATE + ${ABSL_TEST_PRIVATE_COMPILE_FLAGS} + ${ABSL_TEST_COPTS} + ) + target_link_libraries(${_NAME} PUBLIC ${ABSL_TEST_PUBLIC_LIBRARIES} ${ABSL_TEST_COMMON_LIBRARIES}) + target_include_directories(${_NAME} PUBLIC ${ABSL_COMMON_INCLUDE_DIRS} ${ABSL_TEST_PUBLIC_INCLUDE_DIRS} PRIVATE ${GMOCK_INCLUDE_DIRS} ${GTEST_INCLUDE_DIRS} ) # Add all Abseil targets to a a folder in the IDE for organization. - set_property(TARGET ${_NAME}_bin PROPERTY FOLDER ${ABSL_IDE_FOLDER}) + set_property(TARGET ${_NAME} PROPERTY FOLDER ${ABSL_IDE_FOLDER}) + + set_property(TARGET ${_NAME} PROPERTY CXX_STANDARD ${ABSL_CXX_STANDARD}) + set_property(TARGET ${_NAME} PROPERTY CXX_STANDARD_REQUIRED ON) - add_test(${_NAME} ${_NAME}_bin) + add_test(NAME ${_NAME} COMMAND ${_NAME}) endif(ABSL_RUN_TESTS) endfunction() diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/CMake/DownloadGTest.cmake b/src/third_party/abseil-cpp-master/abseil-cpp/CMake/DownloadGTest.cmake index 9d4132158b8..3c682aef07f 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/CMake/DownloadGTest.cmake +++ b/src/third_party/abseil-cpp-master/abseil-cpp/CMake/DownloadGTest.cmake @@ -4,7 +4,7 @@ # Download the latest googletest from Github master configure_file( ${CMAKE_CURRENT_LIST_DIR}/CMakeLists.txt.in - googletest-download/CMakeLists.txt + ${CMAKE_BINARY_DIR}/googletest-download/CMakeLists.txt ) # Configure and build the downloaded googletest source diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/algorithm/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/algorithm/BUILD.bazel index d04dc71206e..4314ee86928 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/algorithm/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/algorithm/BUILD.bazel @@ -15,7 +15,7 @@ # load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", ) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/algorithm/container.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/algorithm/container.h index 53ab15686c6..6d5f6630f71 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/algorithm/container.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/algorithm/container.h @@ -46,6 +46,8 @@ #include <iterator> #include <numeric> #include <type_traits> +#include <unordered_map> +#include <unordered_set> #include <utility> #include <vector> @@ -54,7 +56,6 @@ #include "absl/meta/type_traits.h" namespace absl { - namespace container_algorithm_internal { // NOTE: it is important to defer to ADL lookup for building with C++ modules, @@ -101,6 +102,17 @@ ContainerIter<C> c_begin(C& c) { return begin(c); } template <typename C> ContainerIter<C> c_end(C& c) { return end(c); } +template <typename T> +struct IsUnorderedContainer : std::false_type {}; + +template <class Key, class T, class Hash, class KeyEqual, class Allocator> +struct IsUnorderedContainer< + std::unordered_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {}; + +template <class Key, class Hash, class KeyEqual, class Allocator> +struct IsUnorderedContainer<std::unordered_set<Key, Hash, KeyEqual, Allocator>> + : std::true_type {}; + } // namespace container_algorithm_internal // PUBLIC API @@ -1154,7 +1166,13 @@ bool c_includes(const C1& c1, const C2& c2, Compare&& comp) { // Container-based version of the <algorithm> `std::set_union()` function // to return an iterator containing the union of two containers; duplicate // values are not copied into the output. -template <typename C1, typename C2, typename OutputIterator> +template <typename C1, typename C2, typename OutputIterator, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C1>::value, + void>::type, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C2>::value, + void>::type> OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output) { return std::set_union(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), @@ -1164,7 +1182,13 @@ OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output) { // Overload of c_set_union() for performing a merge using a `comp` other than // `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare> +template <typename C1, typename C2, typename OutputIterator, typename Compare, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C1>::value, + void>::type, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C2>::value, + void>::type> OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output, Compare&& comp) { return std::set_union(container_algorithm_internal::c_begin(c1), @@ -1178,7 +1202,13 @@ OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output, // // Container-based version of the <algorithm> `std::set_intersection()` function // to return an iterator containing the intersection of two containers. -template <typename C1, typename C2, typename OutputIterator> +template <typename C1, typename C2, typename OutputIterator, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C1>::value, + void>::type, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C2>::value, + void>::type> OutputIterator c_set_intersection(const C1& c1, const C2& c2, OutputIterator output) { return std::set_intersection(container_algorithm_internal::c_begin(c1), @@ -1189,7 +1219,13 @@ OutputIterator c_set_intersection(const C1& c1, const C2& c2, // Overload of c_set_intersection() for performing a merge using a `comp` other // than `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare> +template <typename C1, typename C2, typename OutputIterator, typename Compare, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C1>::value, + void>::type, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C2>::value, + void>::type> OutputIterator c_set_intersection(const C1& c1, const C2& c2, OutputIterator output, Compare&& comp) { return std::set_intersection(container_algorithm_internal::c_begin(c1), @@ -1204,7 +1240,13 @@ OutputIterator c_set_intersection(const C1& c1, const C2& c2, // Container-based version of the <algorithm> `std::set_difference()` function // to return an iterator containing elements present in the first container but // not in the second. -template <typename C1, typename C2, typename OutputIterator> +template <typename C1, typename C2, typename OutputIterator, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C1>::value, + void>::type, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C2>::value, + void>::type> OutputIterator c_set_difference(const C1& c1, const C2& c2, OutputIterator output) { return std::set_difference(container_algorithm_internal::c_begin(c1), @@ -1215,7 +1257,13 @@ OutputIterator c_set_difference(const C1& c1, const C2& c2, // Overload of c_set_difference() for performing a merge using a `comp` other // than `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare> +template <typename C1, typename C2, typename OutputIterator, typename Compare, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C1>::value, + void>::type, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C2>::value, + void>::type> OutputIterator c_set_difference(const C1& c1, const C2& c2, OutputIterator output, Compare&& comp) { return std::set_difference(container_algorithm_internal::c_begin(c1), @@ -1230,7 +1278,13 @@ OutputIterator c_set_difference(const C1& c1, const C2& c2, // Container-based version of the <algorithm> `std::set_symmetric_difference()` // function to return an iterator containing elements present in either one // container or the other, but not both. -template <typename C1, typename C2, typename OutputIterator> +template <typename C1, typename C2, typename OutputIterator, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C1>::value, + void>::type, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C2>::value, + void>::type> OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, OutputIterator output) { return std::set_symmetric_difference( @@ -1242,7 +1296,13 @@ OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, // Overload of c_set_symmetric_difference() for performing a merge using a // `comp` other than `operator<`. -template <typename C1, typename C2, typename OutputIterator, typename Compare> +template <typename C1, typename C2, typename OutputIterator, typename Compare, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C1>::value, + void>::type, + typename = typename std::enable_if< + !container_algorithm_internal::IsUnorderedContainer<C2>::value, + void>::type> OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, OutputIterator output, Compare&& comp) { diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/BUILD.bazel index 44de05e3e09..2717df0c93a 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/BUILD.bazel @@ -15,7 +15,7 @@ # load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", "ABSL_EXCEPTIONS_FLAG", @@ -67,6 +67,7 @@ cc_library( name = "core_headers", hdrs = [ "attributes.h", + "const_init.h", "macros.h", "optimization.h", "port.h", @@ -107,6 +108,7 @@ cc_library( "internal/identity.h", "internal/inline_variable.h", "internal/invoke.h", + "internal/scheduling_mode.h", ], copts = ABSL_DEFAULT_COPTS, visibility = [ @@ -229,7 +231,6 @@ cc_library( copts = ABSL_TEST_COPTS + ABSL_EXCEPTIONS_FLAG, linkopts = ABSL_EXCEPTIONS_FLAG_LINKOPTS, deps = [ - ":base", ":config", ":pretty_function", "//absl/memory", @@ -314,6 +315,33 @@ cc_test( ) cc_library( + name = "spinlock_benchmark_common", + testonly = 1, + srcs = ["internal/spinlock_benchmark.cc"], + copts = ABSL_DEFAULT_COPTS, + visibility = [ + "//absl/base:__pkg__", + ], + deps = [ + ":base", + ":base_internal", + "//absl/synchronization", + "@com_github_google_benchmark//:benchmark_main", + ], + alwayslink = 1, +) + +cc_binary( + name = "spinlock_benchmark", + testonly = 1, + copts = ABSL_DEFAULT_COPTS, + visibility = ["//visibility:private"], + deps = [ + ":spinlock_benchmark_common", + ], +) + +cc_library( name = "endian", hdrs = [ "internal/endian.h", diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/attributes.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/attributes.h index c44b8828509..291ad89ee78 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/attributes.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/attributes.h @@ -402,17 +402,28 @@ // ABSL_MUST_USE_RESULT // -// Tells the compiler to warn about unused return values for functions declared -// with this macro. The macro must appear as the very first part of a function -// declaration or definition: +// Tells the compiler to warn about unused results. // -// Example: +// When annotating a function, it must appear as the first part of the +// declaration or definition. The compiler will warn if the return value from +// such a function is unused: // // ABSL_MUST_USE_RESULT Sprocket* AllocateSprocket(); +// AllocateSprocket(); // Triggers a warning. +// +// When annotating a class, it is equivalent to annotating every function which +// returns an instance. +// +// class ABSL_MUST_USE_RESULT Sprocket {}; +// Sprocket(); // Triggers a warning. +// +// Sprocket MakeSprocket(); +// MakeSprocket(); // Triggers a warning. +// +// Note that references and pointers are not instances: // -// This placement has the broadest compatibility with GCC, Clang, and MSVC, with -// both defs and decls, and with GCC-style attributes, MSVC declspec, C++11 -// and C++17 attributes. +// Sprocket* SprocketPointer(); +// SprocketPointer(); // Does *not* trigger a warning. // // ABSL_MUST_USE_RESULT allows using cast-to-void to suppress the unused result // warning. For that, warn_unused_result is used only for clang but not for gcc. diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/call_once.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/call_once.h index 532ee2e38bb..f6c8ebb2f79 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/call_once.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/call_once.h @@ -150,12 +150,8 @@ void CallOnceImpl(std::atomic<uint32_t>* control, old_control != kOnceRunning && old_control != kOnceWaiter && old_control != kOnceDone) { - ABSL_RAW_LOG( - FATAL, - "Unexpected value for control word: %lx. Either the control word " - "has non-static storage duration (where GoogleOnceDynamic might " - "be appropriate), or there's been a memory corruption.", - static_cast<unsigned long>(old_control)); // NOLINT + ABSL_RAW_LOG(FATAL, "Unexpected value for control word: 0x%lx", + static_cast<unsigned long>(old_control)); // NOLINT } } #endif // NDEBUG diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/call_once_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/call_once_test.cc index cd58ee19f08..183b92efa32 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/call_once_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/call_once_test.cc @@ -18,6 +18,8 @@ #include <vector> #include "gtest/gtest.h" +#include "absl/base/attributes.h" +#include "absl/base/const_init.h" #include "absl/base/thread_annotations.h" #include "absl/synchronization/mutex.h" @@ -25,7 +27,8 @@ namespace absl { namespace { absl::once_flag once; -Mutex counters_mu; + +ABSL_CONST_INIT Mutex counters_mu(absl::kConstInit); int running_thread_count GUARDED_BY(counters_mu) = 0; int call_once_invoke_count GUARDED_BY(counters_mu) = 0; diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/config.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/config.h index d4eb7d0cbd7..db4c4539022 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/config.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/config.h @@ -139,12 +139,18 @@ #ifdef ABSL_HAVE_THREAD_LOCAL #error ABSL_HAVE_THREAD_LOCAL cannot be directly set #elif defined(__APPLE__) -// Notes: Xcode's clang did not support `thread_local` until version -// 8, and even then not for all iOS < 9.0. Also, Xcode 9.3 started disallowing -// `thread_local` for 32-bit iOS simulator targeting iOS 9.x. -// `__has_feature` is only supported by Clang so it has be inside +// Notes: +// * Xcode's clang did not support `thread_local` until version 8, and +// even then not for all iOS < 9.0. +// * Xcode 9.3 started disallowing `thread_local` for 32-bit iOS simulator +// targeting iOS 9.x. +// * Xcode 10 moves the deployment target check for iOS < 9.0 to link time +// making __has_feature unreliable there. +// +// Otherwise, `__has_feature` is only supported by Clang so it has be inside // `defined(__APPLE__)` check. -#if __has_feature(cxx_thread_local) +#if __has_feature(cxx_thread_local) && \ + !(TARGET_OS_IPHONE && __IPHONE_OS_VERSION_MIN_REQUIRED < __IPHONE_9_0) #define ABSL_HAVE_THREAD_LOCAL 1 #endif #else // !defined(__APPLE__) @@ -268,7 +274,8 @@ #error ABSL_HAVE_MMAP cannot be directly set #elif defined(__linux__) || defined(__APPLE__) || defined(__FreeBSD__) || \ defined(__ros__) || defined(__native_client__) || defined(__asmjs__) || \ - defined(__wasm__) || defined(__Fuchsia__) || defined(__sun) + defined(__wasm__) || defined(__Fuchsia__) || defined(__sun) || \ + defined(__ASYLO__) #define ABSL_HAVE_MMAP 1 #endif @@ -322,6 +329,8 @@ #define ABSL_HAVE_ALARM 1 #elif defined(_MSC_VER) // feature tests for Microsoft's library +#elif defined(__EMSCRIPTEN__) +// emscripten doesn't support signals #elif defined(__native_client__) #else // other standard libraries @@ -356,6 +365,18 @@ #error "absl endian detection needs to be set up for your compiler" #endif +// MacOS 10.13 doesn't let you use <any>, <optional>, or <variant> even though +// the headers exist and are publicly noted to work. See +// https://github.com/abseil/abseil-cpp/issues/207 and +// https://developer.apple.com/documentation/xcode_release_notes/xcode_10_release_notes +#if defined(__APPLE__) && defined(_LIBCPP_VERSION) && \ + defined(__MAC_OS_X_VERSION_MIN_REQUIRED__) && \ + __ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__ >= 101400 +#define ABSL_INTERNAL_MACOS_HAS_CXX_17_TYPES 1 +#else +#define ABSL_INTERNAL_MACOS_HAS_CXX_17_TYPES 0 +#endif + // ABSL_HAVE_STD_ANY // // Checks whether C++17 std::any is available by checking whether <any> exists. @@ -364,7 +385,8 @@ #endif #ifdef __has_include -#if __has_include(<any>) && __cplusplus >= 201703L +#if __has_include(<any>) && __cplusplus >= 201703L && \ + ABSL_INTERNAL_MACOS_HAS_CXX_17_TYPES #define ABSL_HAVE_STD_ANY 1 #endif #endif @@ -377,7 +399,8 @@ #endif #ifdef __has_include -#if __has_include(<optional>) && __cplusplus >= 201703L +#if __has_include(<optional>) && __cplusplus >= 201703L && \ + ABSL_INTERNAL_MACOS_HAS_CXX_17_TYPES #define ABSL_HAVE_STD_OPTIONAL 1 #endif #endif @@ -390,7 +413,8 @@ #endif #ifdef __has_include -#if __has_include(<variant>) && __cplusplus >= 201703L +#if __has_include(<variant>) && __cplusplus >= 201703L && \ + ABSL_INTERNAL_MACOS_HAS_CXX_17_TYPES #define ABSL_HAVE_STD_VARIANT 1 #endif #endif @@ -423,4 +447,12 @@ #define ABSL_HAVE_STD_STRING_VIEW 1 #endif +// In debug mode, MSVC 2017's std::variant throws a EXCEPTION_ACCESS_VIOLATION +// SEH exception from emplace for variant<SomeStruct> when constructing the +// struct can throw. This defeats some of variant_test and +// variant_exception_safety_test. +#if defined(_MSC_VER) && _MSC_VER >= 1700 && defined(_DEBUG) +#define ABSL_INTERNAL_MSVC_2017_DBG_MODE +#endif + #endif // ABSL_BASE_CONFIG_H_ diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/const_init.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/const_init.h new file mode 100644 index 00000000000..fc88b2672e2 --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/const_init.h @@ -0,0 +1,73 @@ +// Copyright 2017 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. +// +// ----------------------------------------------------------------------------- +// kConstInit +// ----------------------------------------------------------------------------- +// +// A constructor tag used to mark an object as safe for use as a global +// variable, avoiding the usual lifetime issues that can affect globals. + +#ifndef ABSL_BASE_CONST_INIT_H_ +#define ABSL_BASE_CONST_INIT_H_ + +// In general, objects with static storage duration (such as global variables) +// can trigger tricky object lifetime situations. Attempting to access them +// from the constructors or destructors of other global objects can result in +// undefined behavior, unless their constructors and destructors are designed +// with this issue in mind. +// +// The normal way to deal with this issue in C++11 is to use constant +// initialization and trivial destructors. +// +// Constant initialization is guaranteed to occur before any other code +// executes. Constructors that are declared 'constexpr' are eligible for +// constant initialization. You can annotate a variable declaration with the +// ABSL_CONST_INIT macro to express this intent. For compilers that support +// it, this annotation will cause a compilation error for declarations that +// aren't subject to constant initialization (perhaps because a runtime value +// was passed as a constructor argument). +// +// On program shutdown, lifetime issues can be avoided on global objects by +// ensuring that they contain trivial destructors. A class has a trivial +// destructor unless it has a user-defined destructor, a virtual method or base +// class, or a data member or base class with a non-trivial destructor of its +// own. Objects with static storage duration and a trivial destructor are not +// cleaned up on program shutdown, and are thus safe to access from other code +// running during shutdown. +// +// For a few core Abseil classes, we make a best effort to allow for safe global +// instances, even though these classes have non-trivial destructors. These +// objects can be created with the absl::kConstInit tag. For example: +// ABSL_CONST_INIT absl::Mutex global_mutex(absl::kConstInit); +// +// The line above declares a global variable of type absl::Mutex which can be +// accessed at any point during startup or shutdown. global_mutex's destructor +// will still run, but will not invalidate the object. Note that C++ specifies +// that accessing an object after its destructor has run results in undefined +// behavior, but this pattern works on the toolchains we support. +// +// The absl::kConstInit tag should only be used to define objects with static +// or thread_local storage duration. +// + +namespace absl { + +enum ConstInitType { + kConstInit, +}; + +} // namespace absl + +#endif // ABSL_BASE_CONST_INIT_H_ diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/direct_mmap.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/direct_mmap.h index 0426e11890b..654a6007270 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/direct_mmap.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/direct_mmap.h @@ -75,7 +75,11 @@ inline void* DirectMmap(void* start, size_t length, int prot, int flags, int fd, // On these architectures, implement mmap with mmap2. static int pagesize = 0; if (pagesize == 0) { +#if defined(__wasm__) || defined(__asmjs__) pagesize = getpagesize(); +#else + pagesize = sysconf(_SC_PAGESIZE); +#endif } if (offset < 0 || offset % pagesize != 0) { errno = EINVAL; diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/low_level_alloc.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/low_level_alloc.cc index 6e636a02c5d..4af9c05da0d 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/low_level_alloc.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/low_level_alloc.cc @@ -208,7 +208,7 @@ struct LowLevelAlloc::Arena { int32_t allocation_count GUARDED_BY(mu); // flags passed to NewArena const uint32_t flags; - // Result of getpagesize() + // Result of sysconf(_SC_PAGESIZE) const size_t pagesize; // Lowest power of two >= max(16, sizeof(AllocList)) const size_t roundup; @@ -324,8 +324,10 @@ size_t GetPageSize() { SYSTEM_INFO system_info; GetSystemInfo(&system_info); return std::max(system_info.dwPageSize, system_info.dwAllocationGranularity); -#else +#elif defined(__wasm__) || defined(__asmjs__) return getpagesize(); +#else + return sysconf(_SC_PAGESIZE); #endif } diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/spinlock.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/spinlock.h index dcce0109223..eb3eec9cd0a 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/spinlock.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/spinlock.h @@ -101,8 +101,8 @@ class LOCKABLE SpinLock { inline void Unlock() UNLOCK_FUNCTION() { ABSL_TSAN_MUTEX_PRE_UNLOCK(this, 0); uint32_t lock_value = lockword_.load(std::memory_order_relaxed); - lockword_.store(lock_value & kSpinLockCooperative, - std::memory_order_release); + lock_value = lockword_.exchange(lock_value & kSpinLockCooperative, + std::memory_order_release); if ((lock_value & kSpinLockDisabledScheduling) != 0) { base_internal::SchedulingGuard::EnableRescheduling(true); diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/spinlock_benchmark.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/spinlock_benchmark.cc new file mode 100644 index 00000000000..907d3e2745b --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/spinlock_benchmark.cc @@ -0,0 +1,52 @@ +// 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. + +// See also //absl/synchronization:mutex_benchmark for a comparison of SpinLock +// and Mutex performance under varying levels of contention. + +#include "absl/base/internal/raw_logging.h" +#include "absl/base/internal/scheduling_mode.h" +#include "absl/base/internal/spinlock.h" +#include "absl/synchronization/internal/create_thread_identity.h" +#include "benchmark/benchmark.h" + +namespace { + +template <absl::base_internal::SchedulingMode scheduling_mode> +static void BM_SpinLock(benchmark::State& state) { + // Ensure a ThreadIdentity is installed. + ABSL_INTERNAL_CHECK( + absl::synchronization_internal::GetOrCreateCurrentThreadIdentity() != + nullptr, + "GetOrCreateCurrentThreadIdentity() failed"); + + static auto* spinlock = new absl::base_internal::SpinLock(scheduling_mode); + for (auto _ : state) { + absl::base_internal::SpinLockHolder holder(spinlock); + } +} + +BENCHMARK_TEMPLATE(BM_SpinLock, + absl::base_internal::SCHEDULE_KERNEL_ONLY) + ->UseRealTime() + ->Threads(1) + ->ThreadPerCpu(); + +BENCHMARK_TEMPLATE(BM_SpinLock, + absl::base_internal::SCHEDULE_COOPERATIVE_AND_KERNEL) + ->UseRealTime() + ->Threads(1) + ->ThreadPerCpu(); + +} // namespace diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/throw_delegate.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/throw_delegate.cc index 46dc573cfa8..1c40efcb3cd 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/throw_delegate.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/base/internal/throw_delegate.cc @@ -30,8 +30,8 @@ template <typename T> #ifdef ABSL_HAVE_EXCEPTIONS throw error; #else - ABSL_RAW_LOG(ERROR, "%s", error.what()); - abort(); + ABSL_RAW_LOG(FATAL, "%s", error.what()); + std::abort(); #endif } } // namespace diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/BUILD.bazel index d75f8916317..55aea3979f4 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/BUILD.bazel @@ -15,11 +15,11 @@ # load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", - "ABSL_TEST_COPTS", "ABSL_EXCEPTIONS_FLAG", "ABSL_EXCEPTIONS_FLAG_LINKOPTS", + "ABSL_TEST_COPTS", ) package(default_visibility = ["//visibility:public"]) @@ -41,6 +41,8 @@ cc_test( copts = ABSL_TEST_COPTS, deps = [ ":compressed_tuple", + "//absl/memory", + "//absl/utility", "@com_google_googletest//:gtest_main", ], ) @@ -212,6 +214,7 @@ cc_library( ":container_memory", ":hash_function_defaults", ":raw_hash_map", + "//absl/algorithm:container", "//absl/memory", ], ) @@ -240,6 +243,7 @@ cc_library( ":container_memory", ":hash_function_defaults", ":raw_hash_set", + "//absl/algorithm:container", "//absl/base:core_headers", "//absl/memory", ], @@ -271,6 +275,7 @@ cc_library( ":hash_function_defaults", ":node_hash_policy", ":raw_hash_map", + "//absl/algorithm:container", "//absl/memory", ], ) @@ -299,6 +304,7 @@ cc_library( ":hash_function_defaults", ":node_hash_policy", ":raw_hash_set", + "//absl/algorithm:container", "//absl/memory", ], ) @@ -458,6 +464,12 @@ cc_library( ) cc_library( + name = "have_sse", + hdrs = ["internal/have_sse.h"], + copts = ABSL_DEFAULT_COPTS, +) + +cc_library( name = "raw_hash_set", srcs = ["internal/raw_hash_set.cc"], hdrs = ["internal/raw_hash_set.h"], @@ -467,6 +479,7 @@ cc_library( ":container_memory", ":hash_policy_traits", ":hashtable_debug_hooks", + ":have_sse", ":layout", "//absl/base:bits", "//absl/base:config", diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/flat_hash_map.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/flat_hash_map.h index de632be2cf2..cc3d8b69b7a 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/flat_hash_map.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/flat_hash_map.h @@ -35,6 +35,7 @@ #include <type_traits> #include <utility> +#include "absl/algorithm/container.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/hash_function_defaults.h" // IWYU pragma: export #include "absl/container/internal/raw_hash_map.h" // IWYU pragma: export @@ -69,7 +70,7 @@ struct FlatHashMapPolicy; // By default, `flat_hash_map` uses the `absl::Hash` hashing framework. // All fundamental and Abseil types that support the `absl::Hash` framework have // a compatible equality operator for comparing insertions into `flat_hash_map`. -// If your type is not yet supported by the `asbl::Hash` framework, see +// If your type is not yet supported by the `absl::Hash` framework, see // absl/hash/hash.h for information on extending Abseil hashing to user-defined // types. // @@ -564,5 +565,16 @@ struct FlatHashMapPolicy { }; } // namespace container_internal + +namespace container_algorithm_internal { + +// Specialization of trait in absl/algorithm/container.h +template <class Key, class T, class Hash, class KeyEqual, class Allocator> +struct IsUnorderedContainer< + absl::flat_hash_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {}; + +} // namespace container_algorithm_internal + } // namespace absl + #endif // ABSL_CONTAINER_FLAT_HASH_MAP_H_ diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/flat_hash_set.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/flat_hash_set.h index a2584d66f8e..84984cc4927 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/flat_hash_set.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/flat_hash_set.h @@ -32,6 +32,7 @@ #include <type_traits> #include <utility> +#include "absl/algorithm/container.h" #include "absl/base/macros.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/hash_function_defaults.h" // IWYU pragma: export @@ -66,7 +67,7 @@ struct FlatHashSetPolicy; // By default, `flat_hash_set` uses the `absl::Hash` hashing framework. All // fundamental and Abseil types that support the `absl::Hash` framework have a // compatible equality operator for comparing insertions into `flat_hash_map`. -// If your type is not yet supported by the `asbl::Hash` framework, see +// If your type is not yet supported by the `absl::Hash` framework, see // absl/hash/hash.h for information on extending Abseil hashing to user-defined // types. // @@ -278,8 +279,7 @@ class flat_hash_set // // The element may be constructed even if there already is an element with the // key in the container, in which case the newly constructed element will be - // destroyed immediately. Prefer `try_emplace()` unless your key is not - // copyable or moveable. + // destroyed immediately. // // If rehashing occurs due to the insertion, all iterators are invalidated. using Base::emplace; @@ -293,8 +293,7 @@ class flat_hash_set // // The element may be constructed even if there already is an element with the // key in the container, in which case the newly constructed element will be - // destroyed immediately. Prefer `try_emplace()` unless your key is not - // copyable or moveable. + // destroyed immediately. // // If rehashing occurs due to the insertion, all iterators are invalidated. using Base::emplace_hint; @@ -475,5 +474,16 @@ struct FlatHashSetPolicy { static size_t space_used(const T*) { return 0; } }; } // namespace container_internal + +namespace container_algorithm_internal { + +// Specialization of trait in absl/algorithm/container.h +template <class Key, class Hash, class KeyEqual, class Allocator> +struct IsUnorderedContainer<absl::flat_hash_set<Key, Hash, KeyEqual, Allocator>> + : std::true_type {}; + +} // namespace container_algorithm_internal + } // namespace absl + #endif // ABSL_CONTAINER_FLAT_HASH_SET_H_ diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/inlined_vector.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/inlined_vector.h index ea8cb02baa6..fe228001bf2 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/inlined_vector.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/inlined_vector.h @@ -20,17 +20,17 @@ // vector" which behaves in an equivalent fashion to a `std::vector`, except // that storage for small sequences of the vector are provided inline without // requiring any heap allocation. - -// An `absl::InlinedVector<T,N>` specifies the size N at which to inline as one -// of its template parameters. Vectors of length <= N are provided inline. -// Typically N is very small (e.g., 4) so that sequences that are expected to be -// short do not require allocations. - -// An `absl::InlinedVector` does not usually require a specific allocator; if +// +// An `absl::InlinedVector<T, N>` specifies the default capacity `N` as one of +// its template parameters. Instances where `size() <= N` hold contained +// elements in inline space. Typically `N` is very small so that sequences that +// are expected to be short do not require allocations. +// +// An `absl::InlinedVector` does not usually require a specific allocator. If // the inlined vector grows beyond its initial constraints, it will need to -// allocate (as any normal `std::vector` would) and it will generally use the -// default allocator in that case; optionally, a custom allocator may be -// specified using an `absl::InlinedVector<T,N,A>` construction. +// allocate (as any normal `std::vector` would). This is usually performed with +// the default allocator (defined as `std::allocator<T>`). Optionally, a custom +// allocator type may be specified as `A` in `absl::InlinedVector<T, N, A>`. #ifndef ABSL_CONTAINER_INLINED_VECTOR_H_ #define ABSL_CONTAINER_INLINED_VECTOR_H_ @@ -61,17 +61,16 @@ namespace absl { // An `absl::InlinedVector` is designed to be a drop-in replacement for // `std::vector` for use cases where the vector's size is sufficiently small // that it can be inlined. If the inlined vector does grow beyond its estimated -// size, it will trigger an initial allocation on the heap, and will behave as a -// `std:vector`. The API of the `absl::InlinedVector` within this file is +// capacity, it will trigger an initial allocation on the heap, and will behave +// as a `std:vector`. The API of the `absl::InlinedVector` within this file is // designed to cover the same API footprint as covered by `std::vector`. template <typename T, size_t N, typename A = std::allocator<T>> class InlinedVector { + static_assert(N > 0, "InlinedVector requires inline capacity greater than 0"); constexpr static typename A::size_type inlined_capacity() { return static_cast<typename A::size_type>(N); } - static_assert(inlined_capacity() > 0, "InlinedVector needs inlined capacity"); - template <typename Iterator> using DisableIfIntegral = absl::enable_if_t<!std::is_integral<Iterator>::value>; @@ -101,7 +100,6 @@ class InlinedVector { using reverse_iterator = std::reverse_iterator<iterator>; using const_reverse_iterator = std::reverse_iterator<const_iterator>; - // --------------------------------------------------------------------------- // InlinedVector Constructors and Destructor // --------------------------------------------------------------------------- @@ -132,55 +130,103 @@ class InlinedVector { InlinedVector(std::initializer_list<value_type> init_list, const allocator_type& alloc = allocator_type()) : allocator_and_tag_(alloc) { - AppendRange(init_list.begin(), init_list.end()); + AppendRange(init_list.begin(), init_list.end(), + IteratorCategory<decltype(init_list.begin())>{}); } - // Creates and initialize with the elements [`first`, `last`). + // Creates an inlined vector with elements constructed from the provided + // Iterator range [`first`, `last`). // // NOTE: The `enable_if` prevents ambiguous interpretation between a call to - // this constructor with two integral arguments and a call to the preceding - // `InlinedVector(n, v)` constructor. + // this constructor with two integral arguments and a call to the above + // `InlinedVector(size_type, const_reference)` constructor. template <typename InputIterator, DisableIfIntegral<InputIterator>* = nullptr> InlinedVector(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()) : allocator_and_tag_(alloc) { - AppendRange(first, last); + AppendRange(first, last, IteratorCategory<InputIterator>{}); } // Creates a copy of `other` using `other`'s allocator. - InlinedVector(const InlinedVector& other); + InlinedVector(const InlinedVector& other) + : InlinedVector(other, other.get_allocator()) {} // Creates a copy of `other` but with a specified allocator. - InlinedVector(const InlinedVector& other, const allocator_type& alloc); + InlinedVector(const InlinedVector& other, const allocator_type& alloc) + : allocator_and_tag_(alloc) { + reserve(other.size()); + if (allocated()) { + UninitializedCopy(other.begin(), other.end(), allocated_space()); + tag().set_allocated_size(other.size()); + } else { + UninitializedCopy(other.begin(), other.end(), inlined_space()); + tag().set_inline_size(other.size()); + } + } - // Creates an inlined vector with the contents of `other`. + // Creates an inlined vector by moving in the contents of `other`. // // NOTE: This move constructor does not allocate and only moves the underlying // objects, so its `noexcept` specification depends on whether moving the - // underlying objects can throw or not. We assume + // underlying objects can throw or not. We assume: // a) move constructors should only throw due to allocation failure and // b) if `value_type`'s move constructor allocates, it uses the same // allocation function as the `InlinedVector`'s allocator, so the move // constructor is non-throwing if the allocator is non-throwing or // `value_type`'s move constructor is specified as `noexcept`. - InlinedVector(InlinedVector&& v) noexcept( + InlinedVector(InlinedVector&& other) noexcept( absl::allocator_is_nothrow<allocator_type>::value || - std::is_nothrow_move_constructible<value_type>::value); + std::is_nothrow_move_constructible<value_type>::value) + : allocator_and_tag_(other.allocator_and_tag_) { + if (other.allocated()) { + // We can just steal the underlying buffer from the source. + // That leaves the source empty, so we clear its size. + init_allocation(other.allocation()); + other.tag() = Tag(); + } else { + UninitializedCopy( + std::make_move_iterator(other.inlined_space()), + std::make_move_iterator(other.inlined_space() + other.size()), + inlined_space()); + } + } - // Creates an inlined vector with the contents of `other`. + // Creates an inlined vector by moving in the contents of `other`. // - // NOTE: This move constructor allocates and also moves the underlying + // NOTE: This move constructor allocates and subsequently moves the underlying // objects, so its `noexcept` specification depends on whether the allocation // can throw and whether moving the underlying objects can throw. Based on the // same assumptions as above, the `noexcept` specification is dominated by // whether the allocation can throw regardless of whether `value_type`'s move // constructor is specified as `noexcept`. - InlinedVector(InlinedVector&& v, const allocator_type& alloc) noexcept( - absl::allocator_is_nothrow<allocator_type>::value); + InlinedVector(InlinedVector&& other, const allocator_type& alloc) noexcept( + absl::allocator_is_nothrow<allocator_type>::value) + : allocator_and_tag_(alloc) { + if (other.allocated()) { + if (alloc == other.allocator()) { + // We can just steal the allocation from the source. + tag() = other.tag(); + init_allocation(other.allocation()); + other.tag() = Tag(); + } else { + // We need to use our own allocator + reserve(other.size()); + UninitializedCopy(std::make_move_iterator(other.begin()), + std::make_move_iterator(other.end()), + allocated_space()); + tag().set_allocated_size(other.size()); + } + } else { + UninitializedCopy( + std::make_move_iterator(other.inlined_space()), + std::make_move_iterator(other.inlined_space() + other.size()), + inlined_space()); + tag().set_inline_size(other.size()); + } + } ~InlinedVector() { clear(); } - // --------------------------------------------------------------------------- // InlinedVector Member Accessors // --------------------------------------------------------------------------- @@ -256,7 +302,7 @@ class InlinedVector { reference at(size_type i) { if (ABSL_PREDICT_FALSE(i >= size())) { base_internal::ThrowStdOutOfRange( - "InlinedVector::at() failed bounds check"); + "`InlinedVector::at(size_type)` failed bounds check"); } return data()[i]; } @@ -266,7 +312,7 @@ class InlinedVector { const_reference at(size_type i) const { if (ABSL_PREDICT_FALSE(i >= size())) { base_internal::ThrowStdOutOfRange( - "InlinedVector::at() failed bounds check"); + "`InlinedVector::at(size_type) const` failed bounds check"); } return data()[i]; } @@ -367,7 +413,6 @@ class InlinedVector { // Returns a copy of the allocator of the inlined vector. allocator_type get_allocator() const { return allocator(); } - // --------------------------------------------------------------------------- // InlinedVector Member Mutators // --------------------------------------------------------------------------- @@ -377,7 +422,8 @@ class InlinedVector { // Replaces the contents of the inlined vector with copies of the elements in // the provided `std::initializer_list`. InlinedVector& operator=(std::initializer_list<value_type> init_list) { - AssignRange(init_list.begin(), init_list.end()); + AssignRange(init_list.begin(), init_list.end(), + IteratorCategory<decltype(init_list.begin())>{}); return *this; } @@ -454,14 +500,15 @@ class InlinedVector { // inlined vector with copies of the values in the provided // `std::initializer_list`. void assign(std::initializer_list<value_type> init_list) { - AssignRange(init_list.begin(), init_list.end()); + AssignRange(init_list.begin(), init_list.end(), + IteratorCategory<decltype(init_list.begin())>{}); } // Overload of `InlinedVector::assign()` to replace the contents of the // inlined vector with values constructed from the range [`first`, `last`). template <typename InputIterator, DisableIfIntegral<InputIterator>* = nullptr> void assign(InputIterator first, InputIterator last) { - AssignRange(first, last); + AssignRange(first, last, IteratorCategory<InputIterator>{}); } // `InlinedVector::resize()` @@ -469,12 +516,46 @@ class InlinedVector { // Resizes the inlined vector to contain `n` elements. If `n` is smaller than // the inlined vector's current size, extra elements are destroyed. If `n` is // larger than the initial size, new elements are value-initialized. - void resize(size_type n); + void resize(size_type n) { + size_type s = size(); + if (n < s) { + erase(begin() + n, end()); + return; + } + reserve(n); + assert(capacity() >= n); + + // Fill new space with elements constructed in-place. + if (allocated()) { + UninitializedFill(allocated_space() + s, allocated_space() + n); + tag().set_allocated_size(n); + } else { + UninitializedFill(inlined_space() + s, inlined_space() + n); + tag().set_inline_size(n); + } + } // Overload of `InlinedVector::resize()` to resize the inlined vector to // contain `n` elements where, if `n` is larger than `size()`, the new values // will be copy-constructed from `v`. - void resize(size_type n, const_reference v); + void resize(size_type n, const_reference v) { + size_type s = size(); + if (n < s) { + erase(begin() + n, end()); + return; + } + reserve(n); + assert(capacity() >= n); + + // Fill new space with copies of `v`. + if (allocated()) { + UninitializedFill(allocated_space() + s, allocated_space() + n, v); + tag().set_allocated_size(n); + } else { + UninitializedFill(inlined_space() + s, inlined_space() + n, v); + tag().set_inline_size(n); + } + } // `InlinedVector::insert()` // @@ -524,7 +605,27 @@ class InlinedVector { // Constructs and inserts an object in the inlined vector at the given // `position`, returning an `iterator` pointing to the newly emplaced element. template <typename... Args> - iterator emplace(const_iterator position, Args&&... args); + iterator emplace(const_iterator position, Args&&... args) { + assert(position >= begin()); + assert(position <= end()); + if (ABSL_PREDICT_FALSE(position == end())) { + emplace_back(std::forward<Args>(args)...); + return end() - 1; + } + + T new_t = T(std::forward<Args>(args)...); + + auto range = ShiftRight(position, 1); + if (range.first == range.second) { + // constructing into uninitialized memory + Construct(range.first, std::move(new_t)); + } else { + // assigning into moved-from object + *range.first = T(std::move(new_t)); + } + + return range.first; + } // `InlinedVector::emplace_back()` // @@ -597,7 +698,30 @@ class InlinedVector { // range [`from`, `to`) in the inlined vector. Returns an `iterator` pointing // to the first element following the range erased or the end iterator if `to` // was the end iterator. - iterator erase(const_iterator from, const_iterator to); + iterator erase(const_iterator from, const_iterator to) { + assert(begin() <= from); + assert(from <= to); + assert(to <= end()); + + iterator range_start = const_cast<iterator>(from); + iterator range_end = const_cast<iterator>(to); + + size_type s = size(); + ptrdiff_t erase_gap = std::distance(range_start, range_end); + if (erase_gap > 0) { + pointer space; + if (allocated()) { + space = allocated_space(); + tag().set_allocated_size(s - erase_gap); + } else { + space = inlined_space(); + tag().set_inline_size(s - erase_gap); + } + std::move(range_end, space + s, range_start); + Destroy(space + s - erase_gap, space + s); + } + return range_start; + } // `InlinedVector::clear()` // @@ -668,16 +792,88 @@ class InlinedVector { // `InlinedVector::swap()` // // Swaps the contents of this inlined vector with the contents of `other`. - void swap(InlinedVector& other); + void swap(InlinedVector& other) { + if (ABSL_PREDICT_FALSE(this == &other)) return; + + using std::swap; // Augment ADL with `std::swap`. + if (allocated() && other.allocated()) { + // Both out of line, so just swap the tag, allocation, and allocator. + swap(tag(), other.tag()); + swap(allocation(), other.allocation()); + swap(allocator(), other.allocator()); + return; + } + if (!allocated() && !other.allocated()) { + // Both inlined: swap up to smaller size, then move remaining elements. + InlinedVector* a = this; + InlinedVector* b = &other; + if (size() < other.size()) { + swap(a, b); + } + + const size_type a_size = a->size(); + const size_type b_size = b->size(); + assert(a_size >= b_size); + // `a` is larger. Swap the elements up to the smaller array size. + std::swap_ranges(a->inlined_space(), a->inlined_space() + b_size, + b->inlined_space()); + + // Move the remaining elements: + // [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b` + b->UninitializedCopy(a->inlined_space() + b_size, + a->inlined_space() + a_size, + b->inlined_space() + b_size); + a->Destroy(a->inlined_space() + b_size, a->inlined_space() + a_size); + + swap(a->tag(), b->tag()); + swap(a->allocator(), b->allocator()); + assert(b->size() == a_size); + assert(a->size() == b_size); + return; + } + + // One is out of line, one is inline. + // We first move the elements from the inlined vector into the + // inlined space in the other vector. We then put the other vector's + // pointer/capacity into the originally inlined vector and swap + // the tags. + InlinedVector* a = this; + InlinedVector* b = &other; + if (a->allocated()) { + swap(a, b); + } + assert(!a->allocated()); + assert(b->allocated()); + const size_type a_size = a->size(); + const size_type b_size = b->size(); + // In an optimized build, `b_size` would be unused. + static_cast<void>(b_size); + + // Made Local copies of `size()`, don't need `tag()` accurate anymore + swap(a->tag(), b->tag()); + + // Copy `b_allocation` out before `b`'s union gets clobbered by + // `inline_space` + Allocation b_allocation = b->allocation(); + + b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size, + b->inlined_space()); + a->Destroy(a->inlined_space(), a->inlined_space() + a_size); + + a->allocation() = b_allocation; + + if (a->allocator() != b->allocator()) { + swap(a->allocator(), b->allocator()); + } - template <typename Hash> - friend Hash AbslHashValue(Hash hash, const InlinedVector& inlined_vector) { - const_pointer p = inlined_vector.data(); - size_type n = inlined_vector.size(); - return Hash::combine(Hash::combine_contiguous(std::move(hash), p, n), n); + assert(b->size() == a_size); + assert(a->size() == b_size); } private: + template <typename Hash, typename OtherT, size_t OtherN, typename OtherA> + friend Hash AbslHashValue(Hash, const InlinedVector<OtherT, OtherN, OtherA>&); + // Holds whether the vector is allocated or not in the lowest bit and the size // in the high bits: // `size_ = (size << 1) | is_allocated;` @@ -774,10 +970,76 @@ class InlinedVector { bool allocated() const { return tag().allocated(); } + void ResetAllocation(Allocation new_allocation, size_type new_size) { + if (allocated()) { + Destroy(allocated_space(), allocated_space() + size()); + assert(begin() == allocated_space()); + allocation().Dealloc(allocator()); + allocation() = new_allocation; + } else { + Destroy(inlined_space(), inlined_space() + size()); + init_allocation(new_allocation); // bug: only init once + } + tag().set_allocated_size(new_size); + } + + template <typename... Args> + reference Construct(pointer p, Args&&... args) { + std::allocator_traits<allocator_type>::construct( + allocator(), p, std::forward<Args>(args)...); + return *p; + } + + template <typename Iterator> + void UninitializedCopy(Iterator src, Iterator src_last, pointer dst) { + for (; src != src_last; ++dst, ++src) Construct(dst, *src); + } + + template <typename... Args> + void UninitializedFill(pointer dst, pointer dst_last, const Args&... args) { + for (; dst != dst_last; ++dst) Construct(dst, args...); + } + + // Destroy [`from`, `to`) in place. + void Destroy(pointer from, pointer to) { + for (pointer cur = from; cur != to; ++cur) { + std::allocator_traits<allocator_type>::destroy(allocator(), cur); + } +#if !defined(NDEBUG) + // Overwrite unused memory with `0xab` so we can catch uninitialized usage. + // Cast to `void*` to tell the compiler that we don't care that we might be + // scribbling on a vtable pointer. + if (from != to) { + auto len = sizeof(value_type) * std::distance(from, to); + std::memset(reinterpret_cast<void*>(from), 0xab, len); + } +#endif // !defined(NDEBUG) + } + // Enlarge the underlying representation so we can store `size_ + delta` elems // in allocated space. The size is not changed, and any newly added memory is // not initialized. - void EnlargeBy(size_type delta); + void EnlargeBy(size_type delta) { + const size_type s = size(); + assert(s <= capacity()); + + size_type target = (std::max)(inlined_capacity(), s + delta); + + // Compute new capacity by repeatedly doubling current capacity + // TODO(psrc): Check and avoid overflow? + size_type new_capacity = capacity(); + while (new_capacity < target) { + new_capacity <<= 1; + } + + Allocation new_allocation(allocator(), new_capacity); + + UninitializedCopy(std::make_move_iterator(data()), + std::make_move_iterator(data() + s), + new_allocation.buffer()); + + ResetAllocation(new_allocation, s); + } // Shift all elements from `position` to `end()` by `n` places to the right. // If the vector needs to be enlarged, memory will be allocated. @@ -788,19 +1050,61 @@ class InlinedVector { // // Updates the size of the InlinedVector internally. std::pair<iterator, iterator> ShiftRight(const_iterator position, - size_type n); + size_type n) { + iterator start_used = const_cast<iterator>(position); + iterator start_raw = const_cast<iterator>(position); + size_type s = size(); + size_type required_size = s + n; - void ResetAllocation(Allocation new_allocation, size_type new_size) { - if (allocated()) { - Destroy(allocated_space(), allocated_space() + size()); - assert(begin() == allocated_space()); - allocation().Dealloc(allocator()); - allocation() = new_allocation; + if (required_size > capacity()) { + // Compute new capacity by repeatedly doubling current capacity + size_type new_capacity = capacity(); + while (new_capacity < required_size) { + new_capacity <<= 1; + } + // Move everyone into the new allocation, leaving a gap of `n` for the + // requested shift. + Allocation new_allocation(allocator(), new_capacity); + size_type index = position - begin(); + UninitializedCopy(std::make_move_iterator(data()), + std::make_move_iterator(data() + index), + new_allocation.buffer()); + UninitializedCopy(std::make_move_iterator(data() + index), + std::make_move_iterator(data() + s), + new_allocation.buffer() + index + n); + ResetAllocation(new_allocation, s); + + // New allocation means our iterator is invalid, so we'll recalculate. + // Since the entire gap is in new space, there's no used space to reuse. + start_raw = begin() + index; + start_used = start_raw; } else { - Destroy(inlined_space(), inlined_space() + size()); - init_allocation(new_allocation); // bug: only init once + // If we had enough space, it's a two-part move. Elements going into + // previously-unoccupied space need an `UninitializedCopy()`. Elements + // going into a previously-occupied space are just a `std::move()`. + iterator pos = const_cast<iterator>(position); + iterator raw_space = end(); + size_type slots_in_used_space = raw_space - pos; + size_type new_elements_in_used_space = (std::min)(n, slots_in_used_space); + size_type new_elements_in_raw_space = n - new_elements_in_used_space; + size_type old_elements_in_used_space = + slots_in_used_space - new_elements_in_used_space; + + UninitializedCopy( + std::make_move_iterator(pos + old_elements_in_used_space), + std::make_move_iterator(raw_space), + raw_space + new_elements_in_raw_space); + std::move_backward(pos, pos + old_elements_in_used_space, raw_space); + + // If the gap is entirely in raw space, the used space starts where the + // raw space starts, leaving no elements in used space. If the gap is + // entirely in used space, the raw space starts at the end of the gap, + // leaving all elements accounted for within the used space. + start_used = pos; + start_raw = pos + new_elements_in_used_space; } - tag().set_allocated_size(new_size); + tag().add_size(n); + return std::make_pair(start_used, start_raw); } template <typename... Args> @@ -821,64 +1125,118 @@ class InlinedVector { return new_element; } - void InitAssign(size_type n); - - void InitAssign(size_type n, const_reference v); - - template <typename... Args> - reference Construct(pointer p, Args&&... args) { - std::allocator_traits<allocator_type>::construct( - allocator(), p, std::forward<Args>(args)...); - return *p; + void InitAssign(size_type n) { + if (n > inlined_capacity()) { + Allocation new_allocation(allocator(), n); + init_allocation(new_allocation); + UninitializedFill(allocated_space(), allocated_space() + n); + tag().set_allocated_size(n); + } else { + UninitializedFill(inlined_space(), inlined_space() + n); + tag().set_inline_size(n); + } } - template <typename Iterator> - void UninitializedCopy(Iterator src, Iterator src_last, pointer dst) { - for (; src != src_last; ++dst, ++src) Construct(dst, *src); + void InitAssign(size_type n, const_reference v) { + if (n > inlined_capacity()) { + Allocation new_allocation(allocator(), n); + init_allocation(new_allocation); + UninitializedFill(allocated_space(), allocated_space() + n, v); + tag().set_allocated_size(n); + } else { + UninitializedFill(inlined_space(), inlined_space() + n, v); + tag().set_inline_size(n); + } } - template <typename... Args> - void UninitializedFill(pointer dst, pointer dst_last, const Args&... args) { - for (; dst != dst_last; ++dst) Construct(dst, args...); + template <typename Iterator> + void AssignRange(Iterator first, Iterator last, std::forward_iterator_tag) { + auto length = std::distance(first, last); + // Prefer reassignment to copy construction for elements. + if (static_cast<size_type>(length) <= size()) { + erase(std::copy(first, last, begin()), end()); + return; + } + reserve(length); + iterator out = begin(); + for (; out != end(); ++first, ++out) *out = *first; + if (allocated()) { + UninitializedCopy(first, last, out); + tag().set_allocated_size(length); + } else { + UninitializedCopy(first, last, out); + tag().set_inline_size(length); + } } - // Destroy [`from`, `to`) in place. - void Destroy(pointer from, pointer to); - template <typename Iterator> - void AppendRange(Iterator first, Iterator last, std::input_iterator_tag) { + void AssignRange(Iterator first, Iterator last, std::input_iterator_tag) { + // Optimized to avoid reallocation. + // Prefer reassignment to copy construction for elements. + iterator out = begin(); + for (; first != last && out != end(); ++first, ++out) { + *out = *first; + } + erase(out, end()); std::copy(first, last, std::back_inserter(*this)); } template <typename Iterator> - void AppendRange(Iterator first, Iterator last, std::forward_iterator_tag); + void AppendRange(Iterator first, Iterator last, std::forward_iterator_tag) { + auto length = std::distance(first, last); + reserve(size() + length); + if (allocated()) { + UninitializedCopy(first, last, allocated_space() + size()); + tag().set_allocated_size(size() + length); + } else { + UninitializedCopy(first, last, inlined_space() + size()); + tag().set_inline_size(size() + length); + } + } template <typename Iterator> - void AppendRange(Iterator first, Iterator last) { - AppendRange(first, last, IteratorCategory<Iterator>()); + void AppendRange(Iterator first, Iterator last, std::input_iterator_tag) { + std::copy(first, last, std::back_inserter(*this)); } - template <typename Iterator> - void AssignRange(Iterator first, Iterator last, std::input_iterator_tag); + iterator InsertWithCount(const_iterator position, size_type n, + const_reference v) { + assert(position >= begin() && position <= end()); + if (ABSL_PREDICT_FALSE(n == 0)) return const_cast<iterator>(position); - template <typename Iterator> - void AssignRange(Iterator first, Iterator last, std::forward_iterator_tag); + value_type copy = v; + std::pair<iterator, iterator> it_pair = ShiftRight(position, n); + std::fill(it_pair.first, it_pair.second, copy); + UninitializedFill(it_pair.second, it_pair.first + n, copy); - template <typename Iterator> - void AssignRange(Iterator first, Iterator last) { - AssignRange(first, last, IteratorCategory<Iterator>()); + return it_pair.first; } - iterator InsertWithCount(const_iterator position, size_type n, - const_reference v); + template <typename ForwardIterator> + iterator InsertWithRange(const_iterator position, ForwardIterator first, + ForwardIterator last, std::forward_iterator_tag) { + assert(position >= begin() && position <= end()); + if (ABSL_PREDICT_FALSE(first == last)) + return const_cast<iterator>(position); + + auto n = std::distance(first, last); + std::pair<iterator, iterator> it_pair = ShiftRight(position, n); + size_type used_spots = it_pair.second - it_pair.first; + ForwardIterator open_spot = std::next(first, used_spots); + std::copy(first, open_spot, it_pair.first); + UninitializedCopy(open_spot, last, it_pair.second); + return it_pair.first; + } template <typename InputIterator> iterator InsertWithRange(const_iterator position, InputIterator first, - InputIterator last, std::input_iterator_tag); - - template <typename ForwardIterator> - iterator InsertWithRange(const_iterator position, ForwardIterator first, - ForwardIterator last, std::forward_iterator_tag); + InputIterator last, std::input_iterator_tag) { + assert(position >= begin() && position <= end()); + size_type index = position - cbegin(); + size_type i = index; + while (first != last) insert(begin() + i++, *first++); + return begin() + index; + } // Stores either the inlined or allocated representation union Rep { @@ -890,7 +1248,7 @@ class InlinedVector { // Structs wrap the buffers to perform indirection that solves a bizarre // compilation error on Visual Studio (all known versions). struct InlinedRep { - ValueTypeBuffer inlined[inlined_capacity()]; + ValueTypeBuffer inlined[N]; }; struct AllocatedRep { AllocationBuffer allocation; @@ -976,477 +1334,19 @@ bool operator>=(const InlinedVector<T, N, A>& a, return !(a < b); } +template <typename Hash, typename T, size_t N, typename A> +Hash AbslHashValue(Hash hash, const InlinedVector<T, N, A>& inlined_vector) { + auto p = inlined_vector.data(); + auto n = inlined_vector.size(); + return Hash::combine(Hash::combine_contiguous(std::move(hash), p, n), n); +} + // ----------------------------------------------------------------------------- // Implementation of InlinedVector // // Do not depend on any below implementation details! // ----------------------------------------------------------------------------- -template <typename T, size_t N, typename A> -InlinedVector<T, N, A>::InlinedVector(const InlinedVector& other) - : allocator_and_tag_(other.allocator()) { - reserve(other.size()); - if (allocated()) { - UninitializedCopy(other.begin(), other.end(), allocated_space()); - tag().set_allocated_size(other.size()); - } else { - UninitializedCopy(other.begin(), other.end(), inlined_space()); - tag().set_inline_size(other.size()); - } -} - -template <typename T, size_t N, typename A> -InlinedVector<T, N, A>::InlinedVector(const InlinedVector& other, - const allocator_type& alloc) - : allocator_and_tag_(alloc) { - reserve(other.size()); - if (allocated()) { - UninitializedCopy(other.begin(), other.end(), allocated_space()); - tag().set_allocated_size(other.size()); - } else { - UninitializedCopy(other.begin(), other.end(), inlined_space()); - tag().set_inline_size(other.size()); - } -} - -template <typename T, size_t N, typename A> -InlinedVector<T, N, A>::InlinedVector(InlinedVector&& other) noexcept( - absl::allocator_is_nothrow<allocator_type>::value || - std::is_nothrow_move_constructible<value_type>::value) - : allocator_and_tag_(other.allocator_and_tag_) { - if (other.allocated()) { - // We can just steal the underlying buffer from the source. - // That leaves the source empty, so we clear its size. - init_allocation(other.allocation()); - other.tag() = Tag(); - } else { - UninitializedCopy( - std::make_move_iterator(other.inlined_space()), - std::make_move_iterator(other.inlined_space() + other.size()), - inlined_space()); - } -} - -template <typename T, size_t N, typename A> -InlinedVector<T, N, A>::InlinedVector(InlinedVector&& other, - const allocator_type& alloc) noexcept( // - absl::allocator_is_nothrow<allocator_type>::value) - : allocator_and_tag_(alloc) { - if (other.allocated()) { - if (alloc == other.allocator()) { - // We can just steal the allocation from the source. - tag() = other.tag(); - init_allocation(other.allocation()); - other.tag() = Tag(); - } else { - // We need to use our own allocator - reserve(other.size()); - UninitializedCopy(std::make_move_iterator(other.begin()), - std::make_move_iterator(other.end()), - allocated_space()); - tag().set_allocated_size(other.size()); - } - } else { - UninitializedCopy( - std::make_move_iterator(other.inlined_space()), - std::make_move_iterator(other.inlined_space() + other.size()), - inlined_space()); - tag().set_inline_size(other.size()); - } -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::InitAssign(size_type n, const_reference v) { - if (n > inlined_capacity()) { - Allocation new_allocation(allocator(), n); - init_allocation(new_allocation); - UninitializedFill(allocated_space(), allocated_space() + n, v); - tag().set_allocated_size(n); - } else { - UninitializedFill(inlined_space(), inlined_space() + n, v); - tag().set_inline_size(n); - } -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::InitAssign(size_type n) { - if (n > inlined_capacity()) { - Allocation new_allocation(allocator(), n); - init_allocation(new_allocation); - UninitializedFill(allocated_space(), allocated_space() + n); - tag().set_allocated_size(n); - } else { - UninitializedFill(inlined_space(), inlined_space() + n); - tag().set_inline_size(n); - } -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::resize(size_type n) { - size_type s = size(); - if (n < s) { - erase(begin() + n, end()); - return; - } - reserve(n); - assert(capacity() >= n); - - // Fill new space with elements constructed in-place. - if (allocated()) { - UninitializedFill(allocated_space() + s, allocated_space() + n); - tag().set_allocated_size(n); - } else { - UninitializedFill(inlined_space() + s, inlined_space() + n); - tag().set_inline_size(n); - } -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::resize(size_type n, const_reference v) { - size_type s = size(); - if (n < s) { - erase(begin() + n, end()); - return; - } - reserve(n); - assert(capacity() >= n); - - // Fill new space with copies of 'v'. - if (allocated()) { - UninitializedFill(allocated_space() + s, allocated_space() + n, v); - tag().set_allocated_size(n); - } else { - UninitializedFill(inlined_space() + s, inlined_space() + n, v); - tag().set_inline_size(n); - } -} - -template <typename T, size_t N, typename A> -template <typename... Args> -auto InlinedVector<T, N, A>::emplace(const_iterator position, Args&&... args) - -> iterator { - assert(position >= begin()); - assert(position <= end()); - if (ABSL_PREDICT_FALSE(position == end())) { - emplace_back(std::forward<Args>(args)...); - return end() - 1; - } - - T new_t = T(std::forward<Args>(args)...); - - auto range = ShiftRight(position, 1); - if (range.first == range.second) { - // constructing into uninitialized memory - Construct(range.first, std::move(new_t)); - } else { - // assigning into moved-from object - *range.first = T(std::move(new_t)); - } - - return range.first; -} - -template <typename T, size_t N, typename A> -auto InlinedVector<T, N, A>::erase(const_iterator from, const_iterator to) - -> iterator { - assert(begin() <= from); - assert(from <= to); - assert(to <= end()); - - iterator range_start = const_cast<iterator>(from); - iterator range_end = const_cast<iterator>(to); - - size_type s = size(); - ptrdiff_t erase_gap = std::distance(range_start, range_end); - if (erase_gap > 0) { - pointer space; - if (allocated()) { - space = allocated_space(); - tag().set_allocated_size(s - erase_gap); - } else { - space = inlined_space(); - tag().set_inline_size(s - erase_gap); - } - std::move(range_end, space + s, range_start); - Destroy(space + s - erase_gap, space + s); - } - return range_start; -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::swap(InlinedVector& other) { - using std::swap; // Augment ADL with `std::swap`. - if (ABSL_PREDICT_FALSE(this == &other)) return; - - if (allocated() && other.allocated()) { - // Both out of line, so just swap the tag, allocation, and allocator. - swap(tag(), other.tag()); - swap(allocation(), other.allocation()); - swap(allocator(), other.allocator()); - return; - } - if (!allocated() && !other.allocated()) { - // Both inlined: swap up to smaller size, then move remaining elements. - InlinedVector* a = this; - InlinedVector* b = &other; - if (size() < other.size()) { - swap(a, b); - } - - const size_type a_size = a->size(); - const size_type b_size = b->size(); - assert(a_size >= b_size); - // `a` is larger. Swap the elements up to the smaller array size. - std::swap_ranges(a->inlined_space(), a->inlined_space() + b_size, - b->inlined_space()); - - // Move the remaining elements: - // [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b` - b->UninitializedCopy(a->inlined_space() + b_size, - a->inlined_space() + a_size, - b->inlined_space() + b_size); - a->Destroy(a->inlined_space() + b_size, a->inlined_space() + a_size); - - swap(a->tag(), b->tag()); - swap(a->allocator(), b->allocator()); - assert(b->size() == a_size); - assert(a->size() == b_size); - return; - } - - // One is out of line, one is inline. - // We first move the elements from the inlined vector into the - // inlined space in the other vector. We then put the other vector's - // pointer/capacity into the originally inlined vector and swap - // the tags. - InlinedVector* a = this; - InlinedVector* b = &other; - if (a->allocated()) { - swap(a, b); - } - assert(!a->allocated()); - assert(b->allocated()); - const size_type a_size = a->size(); - const size_type b_size = b->size(); - // In an optimized build, `b_size` would be unused. - static_cast<void>(b_size); - - // Made Local copies of `size()`, don't need `tag()` accurate anymore - swap(a->tag(), b->tag()); - - // Copy `b_allocation` out before `b`'s union gets clobbered by `inline_space` - Allocation b_allocation = b->allocation(); - - b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size, - b->inlined_space()); - a->Destroy(a->inlined_space(), a->inlined_space() + a_size); - - a->allocation() = b_allocation; - - if (a->allocator() != b->allocator()) { - swap(a->allocator(), b->allocator()); - } - - assert(b->size() == a_size); - assert(a->size() == b_size); -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::EnlargeBy(size_type delta) { - const size_type s = size(); - assert(s <= capacity()); - - size_type target = std::max(inlined_capacity(), s + delta); - - // Compute new capacity by repeatedly doubling current capacity - // TODO(psrc): Check and avoid overflow? - size_type new_capacity = capacity(); - while (new_capacity < target) { - new_capacity <<= 1; - } - - Allocation new_allocation(allocator(), new_capacity); - - UninitializedCopy(std::make_move_iterator(data()), - std::make_move_iterator(data() + s), - new_allocation.buffer()); - - ResetAllocation(new_allocation, s); -} - -template <typename T, size_t N, typename A> -auto InlinedVector<T, N, A>::ShiftRight(const_iterator position, size_type n) - -> std::pair<iterator, iterator> { - iterator start_used = const_cast<iterator>(position); - iterator start_raw = const_cast<iterator>(position); - size_type s = size(); - size_type required_size = s + n; - - if (required_size > capacity()) { - // Compute new capacity by repeatedly doubling current capacity - size_type new_capacity = capacity(); - while (new_capacity < required_size) { - new_capacity <<= 1; - } - // Move everyone into the new allocation, leaving a gap of `n` for the - // requested shift. - Allocation new_allocation(allocator(), new_capacity); - size_type index = position - begin(); - UninitializedCopy(std::make_move_iterator(data()), - std::make_move_iterator(data() + index), - new_allocation.buffer()); - UninitializedCopy(std::make_move_iterator(data() + index), - std::make_move_iterator(data() + s), - new_allocation.buffer() + index + n); - ResetAllocation(new_allocation, s); - - // New allocation means our iterator is invalid, so we'll recalculate. - // Since the entire gap is in new space, there's no used space to reuse. - start_raw = begin() + index; - start_used = start_raw; - } else { - // If we had enough space, it's a two-part move. Elements going into - // previously-unoccupied space need an `UninitializedCopy()`. Elements - // going into a previously-occupied space are just a `std::move()`. - iterator pos = const_cast<iterator>(position); - iterator raw_space = end(); - size_type slots_in_used_space = raw_space - pos; - size_type new_elements_in_used_space = std::min(n, slots_in_used_space); - size_type new_elements_in_raw_space = n - new_elements_in_used_space; - size_type old_elements_in_used_space = - slots_in_used_space - new_elements_in_used_space; - - UninitializedCopy(std::make_move_iterator(pos + old_elements_in_used_space), - std::make_move_iterator(raw_space), - raw_space + new_elements_in_raw_space); - std::move_backward(pos, pos + old_elements_in_used_space, raw_space); - - // If the gap is entirely in raw space, the used space starts where the raw - // space starts, leaving no elements in used space. If the gap is entirely - // in used space, the raw space starts at the end of the gap, leaving all - // elements accounted for within the used space. - start_used = pos; - start_raw = pos + new_elements_in_used_space; - } - tag().add_size(n); - return std::make_pair(start_used, start_raw); -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::Destroy(pointer from, pointer to) { - for (pointer cur = from; cur != to; ++cur) { - std::allocator_traits<allocator_type>::destroy(allocator(), cur); - } -#ifndef NDEBUG - // Overwrite unused memory with `0xab` so we can catch uninitialized usage. - // Cast to `void*` to tell the compiler that we don't care that we might be - // scribbling on a vtable pointer. - if (from != to) { - auto len = sizeof(value_type) * std::distance(from, to); - std::memset(reinterpret_cast<void*>(from), 0xab, len); - } -#endif -} - -template <typename T, size_t N, typename A> -template <typename Iterator> -void InlinedVector<T, N, A>::AppendRange(Iterator first, Iterator last, - std::forward_iterator_tag) { - auto length = std::distance(first, last); - reserve(size() + length); - if (allocated()) { - UninitializedCopy(first, last, allocated_space() + size()); - tag().set_allocated_size(size() + length); - } else { - UninitializedCopy(first, last, inlined_space() + size()); - tag().set_inline_size(size() + length); - } -} - -template <typename T, size_t N, typename A> -template <typename Iterator> -void InlinedVector<T, N, A>::AssignRange(Iterator first, Iterator last, - std::input_iterator_tag) { - // Optimized to avoid reallocation. - // Prefer reassignment to copy construction for elements. - iterator out = begin(); - for (; first != last && out != end(); ++first, ++out) { - *out = *first; - } - erase(out, end()); - std::copy(first, last, std::back_inserter(*this)); -} - -template <typename T, size_t N, typename A> -template <typename Iterator> -void InlinedVector<T, N, A>::AssignRange(Iterator first, Iterator last, - std::forward_iterator_tag) { - auto length = std::distance(first, last); - // Prefer reassignment to copy construction for elements. - if (static_cast<size_type>(length) <= size()) { - erase(std::copy(first, last, begin()), end()); - return; - } - reserve(length); - iterator out = begin(); - for (; out != end(); ++first, ++out) *out = *first; - if (allocated()) { - UninitializedCopy(first, last, out); - tag().set_allocated_size(length); - } else { - UninitializedCopy(first, last, out); - tag().set_inline_size(length); - } -} - -template <typename T, size_t N, typename A> -auto InlinedVector<T, N, A>::InsertWithCount(const_iterator position, - size_type n, const_reference v) - -> iterator { - assert(position >= begin() && position <= end()); - if (ABSL_PREDICT_FALSE(n == 0)) return const_cast<iterator>(position); - - value_type copy = v; - std::pair<iterator, iterator> it_pair = ShiftRight(position, n); - std::fill(it_pair.first, it_pair.second, copy); - UninitializedFill(it_pair.second, it_pair.first + n, copy); - - return it_pair.first; -} - -template <typename T, size_t N, typename A> -template <typename InputIterator> -auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position, - InputIterator first, - InputIterator last, - std::input_iterator_tag) - -> iterator { - assert(position >= begin() && position <= end()); - size_type index = position - cbegin(); - size_type i = index; - while (first != last) insert(begin() + i++, *first++); - return begin() + index; -} - -template <typename T, size_t N, typename A> -template <typename ForwardIterator> -auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position, - ForwardIterator first, - ForwardIterator last, - std::forward_iterator_tag) - -> iterator { - assert(position >= begin() && position <= end()); - if (ABSL_PREDICT_FALSE(first == last)) return const_cast<iterator>(position); - - auto n = std::distance(first, last); - std::pair<iterator, iterator> it_pair = ShiftRight(position, n); - size_type used_spots = it_pair.second - it_pair.first; - ForwardIterator open_spot = std::next(first, used_spots); - std::copy(first, open_spot, it_pair.first); - UninitializedCopy(open_spot, last, it_pair.second); - return it_pair.first; -} - } // namespace absl #endif // ABSL_CONTAINER_INLINED_VECTOR_H_ diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/compressed_tuple.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/compressed_tuple.h index cc52614f5b3..b883ae2657e 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/compressed_tuple.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/compressed_tuple.h @@ -89,8 +89,10 @@ struct Storage { 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; } + constexpr const T& get() const& { return value; } + T& get() & { return value; } + constexpr const T&& get() const&& { return absl::move(*this).value; } + T&& get() && { return std::move(*this).value; } }; template <typename D, size_t I> @@ -99,8 +101,10 @@ struct ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC Storage<D, I, true> 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; } + constexpr const T& get() const& { return *this; } + T& get() & { return *this; } + constexpr const T&& get() const&& { return absl::move(*this); } + T&& get() && { return std::move(*this); } }; template <typename D, typename I> @@ -152,14 +156,26 @@ class ABSL_INTERNAL_COMPRESSED_TUPLE_DECLSPEC CompressedTuple : CompressedTuple::CompressedTupleImpl(absl::forward<Ts>(base)...) {} template <int I> - ElemT<I>& get() { + ElemT<I>& get() & { return internal_compressed_tuple::Storage<CompressedTuple, I>::get(); } template <int I> - constexpr const ElemT<I>& get() const { + constexpr const ElemT<I>& get() const& { return internal_compressed_tuple::Storage<CompressedTuple, I>::get(); } + + template <int I> + ElemT<I>&& get() && { + return std::move(*this) + .internal_compressed_tuple::template Storage<CompressedTuple, I>::get(); + } + + template <int I> + constexpr const ElemT<I>&& get() const&& { + return absl::move(*this) + .internal_compressed_tuple::template Storage<CompressedTuple, I>::get(); + } }; // Explicit specialization for a zero-element tuple diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/compressed_tuple_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/compressed_tuple_test.cc index 45030c675ee..04ead100aa1 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/compressed_tuple_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/compressed_tuple_test.cc @@ -14,17 +14,25 @@ #include "absl/container/internal/compressed_tuple.h" +#include <memory> #include <string> #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "absl/memory/memory.h" +#include "absl/utility/utility.h" namespace absl { namespace container_internal { namespace { +enum class CallType { kConstRef, kConstMove }; + template <int> -struct Empty {}; +struct Empty { + constexpr CallType value() const& { return CallType::kConstRef; } + constexpr CallType value() const&& { return CallType::kConstMove; } +}; template <typename T> struct NotEmpty { @@ -140,15 +148,44 @@ TEST(CompressedTupleTest, NoElements) { EXPECT_TRUE(std::is_empty<CompressedTuple<>>::value); } +TEST(CompressedTupleTest, MoveOnlyElements) { + CompressedTuple<std::unique_ptr<std::string>> str_tup( + absl::make_unique<std::string>("str")); + + CompressedTuple<CompressedTuple<std::unique_ptr<std::string>>, + std::unique_ptr<int>> + x(std::move(str_tup), absl::make_unique<int>(5)); + + EXPECT_EQ(*x.get<0>().get<0>(), "str"); + EXPECT_EQ(*x.get<1>(), 5); + + std::unique_ptr<std::string> x0 = std::move(x.get<0>()).get<0>(); + std::unique_ptr<int> x1 = std::move(x).get<1>(); + + EXPECT_EQ(*x0, "str"); + EXPECT_EQ(*x1, 5); +} + TEST(CompressedTupleTest, Constexpr) { - constexpr CompressedTuple<int, double, CompressedTuple<int>> x( - 7, 1.25, CompressedTuple<int>(5)); + constexpr CompressedTuple<int, double, CompressedTuple<int>, Empty<0>> 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>(); + constexpr CallType x3 = x.get<3>().value(); + EXPECT_EQ(x0, 7); EXPECT_EQ(x1, 1.25); EXPECT_EQ(x2, 5); + EXPECT_EQ(x3, CallType::kConstRef); + +#if defined(__clang__) + // An apparent bug in earlier versions of gcc claims these are ambiguous. + constexpr int x2m = absl::move(x.get<2>()).get<0>(); + constexpr CallType x3m = absl::move(x).get<3>().value(); + EXPECT_EQ(x2m, 5); + EXPECT_EQ(x3m, CallType::kConstMove); +#endif } #if defined(__clang__) || defined(__GNUC__) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_generator_testing.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_generator_testing.cc index 0d6a9df16f8..e0fefbffdfa 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_generator_testing.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_generator_testing.cc @@ -39,9 +39,9 @@ class RandomDeviceSeedSeq { } // namespace -std::mt19937_64* GetThreadLocalRng() { +std::mt19937_64* GetSharedRng() { RandomDeviceSeedSeq seed_seq; - thread_local auto* rng = new std::mt19937_64(seed_seq); + static auto* rng = new std::mt19937_64(seed_seq); return rng; } @@ -51,7 +51,7 @@ std::string Generator<std::string>::operator()() const { std::string res; res.resize(32); std::generate(res.begin(), res.end(), - [&]() { return chars(*GetThreadLocalRng()); }); + [&]() { return chars(*GetSharedRng()); }); return res; } @@ -63,7 +63,7 @@ absl::string_view Generator<absl::string_view>::operator()() const { auto& res = arena->back(); res.resize(32); std::generate(res.begin(), res.end(), - [&]() { return chars(*GetThreadLocalRng()); }); + [&]() { return chars(*GetSharedRng()); }); return res; } diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_generator_testing.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_generator_testing.h index 50d771026c7..6521efe8733 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_generator_testing.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_generator_testing.h @@ -43,7 +43,7 @@ struct IsMap<Map, absl::void_t<typename Map::mapped_type>> : std::true_type {}; } // namespace generator_internal -std::mt19937_64* GetThreadLocalRng(); +std::mt19937_64* GetSharedRng(); enum Enum { kEnumEmpty, @@ -66,7 +66,7 @@ template <class T> struct Generator<T, typename std::enable_if<std::is_integral<T>::value>::type> { T operator()() const { std::uniform_int_distribution<T> dist; - return dist(*GetThreadLocalRng()); + return dist(*GetSharedRng()); } }; @@ -76,7 +76,7 @@ struct Generator<Enum> { std::uniform_int_distribution<typename std::underlying_type<Enum>::type> dist; while (true) { - auto variate = dist(*GetThreadLocalRng()); + auto variate = dist(*GetSharedRng()); if (variate != kEnumEmpty && variate != kEnumDeleted) return static_cast<Enum>(variate); } @@ -90,7 +90,7 @@ struct Generator<EnumClass> { typename std::underlying_type<EnumClass>::type> dist; while (true) { - EnumClass variate = static_cast<EnumClass>(dist(*GetThreadLocalRng())); + EnumClass variate = static_cast<EnumClass>(dist(*GetSharedRng())); if (variate != EnumClass::kEmpty && variate != EnumClass::kDeleted) return static_cast<EnumClass>(variate); } diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_policy_testing.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_policy_testing.h index 38bbec77a2e..7fb819a74d2 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_policy_testing.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hash_policy_testing.h @@ -169,7 +169,11 @@ auto keys(const Set& s) // take allocator arguments. This test is defined ad-hoc for the platforms // we care about (notably Crosstool 17) because libstdcxx's useless // versioning scheme precludes a more principled solution. -#if defined(__GLIBCXX__) && __GLIBCXX__ <= 20140425 +// From GCC-4.9 Changelog: (src: https://gcc.gnu.org/gcc-4.9/changes.html) +// "the unordered associative containers in <unordered_map> and <unordered_set> +// meet the allocator-aware container requirements;" +#if (defined(__GLIBCXX__) && __GLIBCXX__ <= 20140425 ) || \ +( __GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 9 )) #define ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS 0 #else #define ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS 1 diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hashtable_debug.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hashtable_debug.h index c3bd65c9c4e..38050c69f61 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hashtable_debug.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/hashtable_debug.h @@ -60,7 +60,7 @@ std::vector<size_t> GetHashtableDebugNumProbesHistogram(const C& container) { size_t num_probes = GetHashtableDebugNumProbes( container, absl::container_internal::hashtable_debug_internal::GetKey<C>(*it, 0)); - v.resize(std::max(v.size(), num_probes + 1)); + v.resize((std::max)(v.size(), num_probes + 1)); v[num_probes]++; } return v; diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/have_sse.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/have_sse.h new file mode 100644 index 00000000000..293478895b6 --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/have_sse.h @@ -0,0 +1,49 @@ +// 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. +// +// Shared config probing for SSE instructions used in Swiss tables. +#ifndef ABSL_CONTAINER_INTERNAL_HAVE_SSE_H_ +#define ABSL_CONTAINER_INTERNAL_HAVE_SSE_H_ + +#ifndef SWISSTABLE_HAVE_SSE2 +#if defined(__SSE2__) || \ + (defined(_MSC_VER) && \ + (defined(_M_X64) || (defined(_M_IX86) && _M_IX86_FP >= 2))) +#define SWISSTABLE_HAVE_SSE2 1 +#else +#define SWISSTABLE_HAVE_SSE2 0 +#endif +#endif + +#ifndef SWISSTABLE_HAVE_SSSE3 +#ifdef __SSSE3__ +#define SWISSTABLE_HAVE_SSSE3 1 +#else +#define SWISSTABLE_HAVE_SSSE3 0 +#endif +#endif + +#if SWISSTABLE_HAVE_SSSE3 && !SWISSTABLE_HAVE_SSE2 +#error "Bad configuration!" +#endif + +#if SWISSTABLE_HAVE_SSE2 +#include <emmintrin.h> +#endif + +#if SWISSTABLE_HAVE_SSSE3 +#include <tmmintrin.h> +#endif + +#endif // ABSL_CONTAINER_INTERNAL_HAVE_SSE_H_ diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/layout.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/layout.h index 676c7d67ee6..3d21ac963b4 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/layout.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/layout.h @@ -232,13 +232,17 @@ struct SizeOf : NotAligned<T>, std::integral_constant<size_t, sizeof(T)> {}; template <class T, size_t N> struct SizeOf<Aligned<T, N>> : std::integral_constant<size_t, sizeof(T)> {}; +// Note: workaround for https://gcc.gnu.org/PR88115 template <class T> -struct AlignOf : NotAligned<T>, std::integral_constant<size_t, alignof(T)> {}; +struct AlignOf : NotAligned<T> { + static constexpr size_t value = alignof(T); +}; template <class T, size_t N> -struct AlignOf<Aligned<T, N>> : std::integral_constant<size_t, N> { +struct AlignOf<Aligned<T, N>> { static_assert(N % alignof(T) == 0, "Custom alignment can't be lower than the type's alignment"); + static constexpr size_t value = N; }; // Does `Ts...` contain `T`? @@ -249,8 +253,10 @@ template <class From, class To> using CopyConst = typename std::conditional<std::is_const<From>::value, const To, To>::type; +// Note: We're not qualifying this with absl:: because it doesn't compile under +// MSVC. template <class T> -using SliceType = absl::Span<T>; +using SliceType = Span<T>; // This namespace contains no types. It prevents functions defined in it from // being found by ADL. @@ -290,7 +296,7 @@ std::string TypeName() { #ifdef ABSL_INTERNAL_HAS_CXA_DEMANGLE demangled = abi::__cxa_demangle(typeid(T).name(), nullptr, nullptr, &status); #endif - if (status == 0 && demangled != nullptr) { // Demangling succeeeded. + if (status == 0 && demangled != nullptr) { // Demangling succeeded. absl::StrAppend(&out, "<", demangled, ">"); free(demangled); } else { @@ -396,7 +402,7 @@ class LayoutImpl<std::tuple<Elements...>, absl::index_sequence<SizeSeq...>, static_assert(N < NumOffsets, "Index out of bounds"); return adl_barrier::Align( Offset<N - 1>() + SizeOf<ElementType<N - 1>>() * size_[N - 1], - ElementAlignment<N>()); + ElementAlignment<N>::value); } // Offset in bytes of the array with the specified element type. There must @@ -445,7 +451,7 @@ class LayoutImpl<std::tuple<Elements...>, absl::index_sequence<SizeSeq...>, return Size<ElementIndex<T>()>(); } - // The number of elements of all arrays for which they are known. + // The number of elements of all arrays for which they are known. constexpr std::array<size_t, NumSizes> Sizes() const { return {{Size<SizeSeq>()...}}; } @@ -610,7 +616,7 @@ class LayoutImpl<std::tuple<Elements...>, absl::index_sequence<SizeSeq...>, #ifdef ADDRESS_SANITIZER PoisonPadding<Char, N - 1>(p); // The `if` is an optimization. It doesn't affect the observable behaviour. - if (ElementAlignment<N - 1>() % ElementAlignment<N>()) { + if (ElementAlignment<N - 1>::value % ElementAlignment<N>::value) { size_t start = Offset<N - 1>() + SizeOf<ElementType<N - 1>>() * size_[N - 1]; ASAN_POISON_MEMORY_REGION(p + start, Offset<N>() - start); @@ -690,7 +696,7 @@ class Layout : public internal_layout::LayoutType<sizeof...(Ts), Ts...> { // // It's allowed to pass fewer array sizes than the number of arrays. E.g., // if all you need is to the offset of the second array, you only need to - // pass one argument -- the number of elements in the first arrays. + // pass one argument -- the number of elements in the first array. // // // int[3] followed by 4 bytes of padding and an unknown number of // // doubles. diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/layout_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/layout_test.cc index f35157a3bd8..301e9f7808f 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/layout_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/layout_test.cc @@ -45,7 +45,25 @@ Expected Type(Actual val) { return val; } -using Int128 = int64_t[2]; +// Helper classes to test different size and alignments. +struct alignas(8) Int128 { + uint64_t a, b; + friend bool operator==(Int128 lhs, Int128 rhs) { + return std::tie(lhs.a, lhs.b) == std::tie(rhs.a, rhs.b); + } + + static std::string Name() { + return internal_layout::adl_barrier::TypeName<Int128>(); + } +}; + +// int64_t is *not* 8-byte aligned on all platforms! +struct alignas(8) Int64 { + int64_t a; + friend bool operator==(Int64 lhs, Int64 rhs) { + return lhs.a == rhs.a; + } +}; // Properties of types that this test relies on. static_assert(sizeof(int8_t) == 1, ""); @@ -54,6 +72,8 @@ static_assert(sizeof(int16_t) == 2, ""); static_assert(alignof(int16_t) == 2, ""); static_assert(sizeof(int32_t) == 4, ""); static_assert(alignof(int32_t) == 4, ""); +static_assert(sizeof(Int64) == 8, ""); +static_assert(alignof(Int64) == 8, ""); static_assert(sizeof(Int128) == 16, ""); static_assert(alignof(Int128) == 8, ""); @@ -1271,14 +1291,14 @@ TEST(Layout, OverAligned) { TEST(Layout, Alignment) { static_assert(Layout<int8_t>::Alignment() == 1, ""); static_assert(Layout<int32_t>::Alignment() == 4, ""); - static_assert(Layout<int64_t>::Alignment() == 8, ""); + static_assert(Layout<Int64>::Alignment() == 8, ""); static_assert(Layout<Aligned<int8_t, 64>>::Alignment() == 64, ""); - static_assert(Layout<int8_t, int32_t, int64_t>::Alignment() == 8, ""); - static_assert(Layout<int8_t, int64_t, int32_t>::Alignment() == 8, ""); - static_assert(Layout<int32_t, int8_t, int64_t>::Alignment() == 8, ""); - static_assert(Layout<int32_t, int64_t, int8_t>::Alignment() == 8, ""); - static_assert(Layout<int64_t, int8_t, int32_t>::Alignment() == 8, ""); - static_assert(Layout<int64_t, int32_t, int8_t>::Alignment() == 8, ""); + static_assert(Layout<int8_t, int32_t, Int64>::Alignment() == 8, ""); + static_assert(Layout<int8_t, Int64, int32_t>::Alignment() == 8, ""); + static_assert(Layout<int32_t, int8_t, Int64>::Alignment() == 8, ""); + static_assert(Layout<int32_t, Int64, int8_t>::Alignment() == 8, ""); + static_assert(Layout<Int64, int8_t, int32_t>::Alignment() == 8, ""); + static_assert(Layout<Int64, int32_t, int8_t>::Alignment() == 8, ""); } TEST(Layout, ConstexprPartial) { @@ -1313,7 +1333,7 @@ void ExpectPoisoned(const unsigned char (&buf)[N], } TEST(Layout, PoisonPadding) { - using L = Layout<int8_t, int64_t, int32_t, Int128>; + using L = Layout<int8_t, Int64, int32_t, Int128>; constexpr size_t n = L::Partial(1, 2, 3, 4).AllocSize(); { @@ -1361,12 +1381,6 @@ TEST(Layout, PoisonPadding) { } TEST(Layout, DebugString) { - const std::string int64_type = -#ifdef _MSC_VER - "__int64"; -#else // _MSC_VER - std::is_same<int64_t, long long>::value ? "long long" : "long"; // NOLINT -#endif // _MSC_VER { constexpr auto x = Layout<int8_t, int32_t, int8_t, Int128>::Partial(); EXPECT_EQ("@0<signed char>(1)", x.DebugString()); @@ -1384,24 +1398,24 @@ TEST(Layout, DebugString) { constexpr auto x = Layout<int8_t, int32_t, int8_t, Int128>::Partial(1, 2, 3); EXPECT_EQ( "@0<signed char>(1)[1]; @4<int>(4)[2]; @12<signed char>(1)[3]; " - "@16<" + - int64_type + " [2]>(16)", + "@16" + + Int128::Name() + "(16)", x.DebugString()); } { constexpr auto x = Layout<int8_t, int32_t, int8_t, Int128>::Partial(1, 2, 3, 4); EXPECT_EQ( "@0<signed char>(1)[1]; @4<int>(4)[2]; @12<signed char>(1)[3]; " - "@16<" + - int64_type + " [2]>(16)[4]", + "@16" + + Int128::Name() + "(16)[4]", x.DebugString()); } { constexpr Layout<int8_t, int32_t, int8_t, Int128> x(1, 2, 3, 4); EXPECT_EQ( "@0<signed char>(1)[1]; @4<int>(4)[2]; @12<signed char>(1)[3]; " - "@16<" + - int64_type + " [2]>(16)[4]", + "@16" + + Int128::Name() + "(16)[4]", x.DebugString()); } } @@ -1528,8 +1542,7 @@ class CompactString { const char* c_str() const { // Equivalent to reinterpret_cast<char*>(p.get() + sizeof(size_t)). // The argument in Partial(1) specifies that we have size_t[1] in front of - // the - // characters. + // the characters. return L::Partial(1).Pointer<char>(p_.get()); } diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set.cc index 10153129fd1..180d3fe5a91 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set.cc @@ -14,6 +14,7 @@ #include "absl/container/internal/raw_hash_set.h" +#include <atomic> #include <cstddef> #include "absl/base/config.h" @@ -29,7 +30,7 @@ inline size_t RandomSeed() { static thread_local size_t counter = 0; size_t value = ++counter; #else // ABSL_HAVE_THREAD_LOCAL - static std::atomic<size_t> counter; + static std::atomic<size_t> counter(0); size_t value = counter.fetch_add(1, std::memory_order_relaxed); #endif // ABSL_HAVE_THREAD_LOCAL return value ^ static_cast<size_t>(reinterpret_cast<uintptr_t>(&counter)); diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set.h index f23644a1cd5..b7b5ef8c7b4 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set.h @@ -91,36 +91,6 @@ #ifndef ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_ #define ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_ -#ifndef SWISSTABLE_HAVE_SSE2 -#if defined(__SSE2__) || \ - (defined(_MSC_VER) && \ - (defined(_M_X64) || (defined(_M_IX86) && _M_IX86_FP >= 2))) -#define SWISSTABLE_HAVE_SSE2 1 -#else -#define SWISSTABLE_HAVE_SSE2 0 -#endif -#endif - -#ifndef SWISSTABLE_HAVE_SSSE3 -#ifdef __SSSE3__ -#define SWISSTABLE_HAVE_SSSE3 1 -#else -#define SWISSTABLE_HAVE_SSSE3 0 -#endif -#endif - -#if SWISSTABLE_HAVE_SSSE3 && !SWISSTABLE_HAVE_SSE2 -#error "Bad configuration!" -#endif - -#if SWISSTABLE_HAVE_SSE2 -#include <emmintrin.h> -#endif - -#if SWISSTABLE_HAVE_SSSE3 -#include <tmmintrin.h> -#endif - #include <algorithm> #include <cmath> #include <cstdint> @@ -139,6 +109,7 @@ #include "absl/container/internal/container_memory.h" #include "absl/container/internal/hash_policy_traits.h" #include "absl/container/internal/hashtable_debug_hooks.h" +#include "absl/container/internal/have_sse.h" #include "absl/container/internal/layout.h" #include "absl/memory/memory.h" #include "absl/meta/type_traits.h" @@ -403,7 +374,7 @@ struct GroupSse2Impl { } void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const { - auto msbs = _mm_set1_epi8('\x80'); + auto msbs = _mm_set1_epi8(static_cast<char>(-128)); auto x126 = _mm_set1_epi8(126); #if SWISSTABLE_HAVE_SSSE3 auto res = _mm_or_si128(_mm_shuffle_epi8(x126, ctrl), msbs); @@ -1363,7 +1334,7 @@ class raw_hash_set { void rehash(size_t n) { if (n == 0 && capacity_ == 0) return; if (n == 0 && size_ == 0) return destroy_slots(); - auto m = NormalizeCapacity(std::max(n, NumSlotsFast(size()))); + auto m = NormalizeCapacity((std::max)(n, NumSlotsFast(size()))); // n == 0 unconditionally rehashes as per the standard. if (n == 0 || m > capacity_) { resize(m); diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set_test.cc index 9d92e15c520..5ad4904f971 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/internal/raw_hash_set_test.cc @@ -14,7 +14,6 @@ #include "absl/container/internal/raw_hash_set.h" -#include <array> #include <cmath> #include <cstdint> #include <deque> @@ -391,7 +390,8 @@ TEST(Table, Prefetch) { !defined(UNDEFINED_BEHAVIOR_SANITIZER) const auto now = [] { return absl::base_internal::CycleClock::Now(); }; - static constexpr int size = 1000000; + // Make size enough to not fit in L2 cache (16.7 Mb) + static constexpr int size = 1 << 22; for (int i = 0; i < size; ++i) t.insert(i); int64_t no_prefetch = 0, prefetch = 0; @@ -1782,143 +1782,6 @@ TEST(Table, IterationOrderChangesForSmallTables) { FAIL() << "Iteration order remained the same across many attempts."; } -// Fill the table to 3 different load factors (min, median, max) and evaluate -// the percentage of perfect hits using the debug API. -template <class Table, class AddFn> -std::vector<double> CollectPerfectRatios(Table, AddFn add) { - std::vector<double> results(3); - - constexpr size_t kNumTrials = 10; - std::vector<Table> tables(kNumTrials); - - for (Table& t : tables) { - using Key = typename Table::key_type; - - // First, fill enough to have a good distribution. - constexpr size_t kMinSize = 10000; - std::vector<Key> keys; - while (t.size() < kMinSize) keys.push_back(add(t)); - // Then, insert until we reach min load factor. - double lf = t.load_factor(); - while (lf <= t.load_factor()) keys.push_back(add(t)); - - // We are now at min load factor. Take a snapshot. - size_t perfect = 0; - auto update_perfect = [&](Key k) { - perfect += GetHashtableDebugNumProbes(t, k) == 0; - }; - for (const auto& k : keys) update_perfect(k); - - std::vector<double> perfect_ratios; - // Keep going until we hit max load factor. - while (t.load_factor() < .6) { - perfect_ratios.push_back(1.0 * perfect / t.size()); - update_perfect(add(t)); - } - while (t.load_factor() > .5) { - perfect_ratios.push_back(1.0 * perfect / t.size()); - update_perfect(add(t)); - } - - results[0] += perfect_ratios.front(); - results[1] += perfect_ratios[perfect_ratios.size() / 2]; - results[2] += perfect_ratios.back(); - } - - results[0] /= kNumTrials; - results[1] /= kNumTrials; - results[2] /= kNumTrials; - - return results; -} - -std::vector<std::pair<double, double>> StringTablePefectRatios() { - constexpr bool kRandomizesInserts = -#if NDEBUG - false; -#else // NDEBUG - true; -#endif // NDEBUG - - // The effective load factor is larger in non-opt mode because we insert - // elements out of order. - switch (container_internal::Group::kWidth) { - case 8: - if (kRandomizesInserts) { - return {{0.986, 0.02}, {0.95, 0.02}, {0.89, 0.02}}; - } else { - return {{0.995, 0.01}, {0.97, 0.01}, {0.89, 0.02}}; - } - case 16: - if (kRandomizesInserts) { - return {{0.973, 0.01}, {0.965, 0.01}, {0.92, 0.02}}; - } else { - return {{0.995, 0.005}, {0.99, 0.005}, {0.94, 0.01}}; - } - } - ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width"); - return {}; -} - -// This is almost a change detector, but it allows us to know how we are -// affecting the probe distribution. -TEST(Table, EffectiveLoadFactorStrings) { - std::vector<double> perfect_ratios = - CollectPerfectRatios(StringTable(), [](StringTable& t) { - return t.emplace(std::to_string(t.size()), "").first->first; - }); - - auto ratios = StringTablePefectRatios(); - if (ratios.empty()) return; - EXPECT_THAT(perfect_ratios, - ElementsAre(DoubleNear(ratios[0].first, ratios[0].second), - DoubleNear(ratios[1].first, ratios[1].second), - DoubleNear(ratios[2].first, ratios[2].second))); -} - -std::vector<std::pair<double, double>> IntTablePefectRatios() { - constexpr bool kRandomizesInserts = -#ifdef NDEBUG - false; -#else // NDEBUG - true; -#endif // NDEBUG - - // The effective load factor is larger in non-opt mode because we insert - // elements out of order. - switch (container_internal::Group::kWidth) { - case 8: - if (kRandomizesInserts) { - return {{0.99, 0.02}, {0.985, 0.02}, {0.95, 0.05}}; - } else { - return {{0.99, 0.01}, {0.99, 0.01}, {0.95, 0.02}}; - } - case 16: - if (kRandomizesInserts) { - return {{0.98, 0.02}, {0.978, 0.02}, {0.96, 0.02}}; - } else { - return {{0.998, 0.003}, {0.995, 0.01}, {0.975, 0.02}}; - } - } - ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width"); - return {}; -} - -// This is almost a change detector, but it allows us to know how we are -// affecting the probe distribution. -TEST(Table, EffectiveLoadFactorInts) { - std::vector<double> perfect_ratios = CollectPerfectRatios( - IntTable(), [](IntTable& t) { return *t.emplace(t.size()).first; }); - - auto ratios = IntTablePefectRatios(); - if (ratios.empty()) return; - - EXPECT_THAT(perfect_ratios, - ElementsAre(DoubleNear(ratios[0].first, ratios[0].second), - DoubleNear(ratios[1].first, ratios[1].second), - DoubleNear(ratios[2].first, ratios[2].second))); -} - // Confirm that we assert if we try to erase() end(). TEST(TableDeathTest, EraseOfEndAsserts) { // Use an assert with side-effects to figure out if they are actually enabled. diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/node_hash_map.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/node_hash_map.h index 00710e52c57..bd53c590419 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/node_hash_map.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/node_hash_map.h @@ -40,6 +40,7 @@ #include <type_traits> #include <utility> +#include "absl/algorithm/container.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/hash_function_defaults.h" // IWYU pragma: export #include "absl/container/internal/node_hash_policy.h" @@ -71,7 +72,7 @@ class NodeHashMapPolicy; // By default, `node_hash_map` uses the `absl::Hash` hashing framework. // All fundamental and Abseil types that support the `absl::Hash` framework have // a compatible equality operator for comparing insertions into `node_hash_map`. -// If your type is not yet supported by the `asbl::Hash` framework, see +// If your type is not yet supported by the `absl::Hash` framework, see // absl/hash/hash.h for information on extending Abseil hashing to user-defined // types. // @@ -91,7 +92,7 @@ class NodeHashMapPolicy; // std::string search_key = "b"; // auto result = ducks.find(search_key); // if (result != ducks.end()) { -// std::cout << "Result: " << search_key->second << std::endl; +// std::cout << "Result: " << result->second << std::endl; // } template <class Key, class Value, class Hash = absl::container_internal::hash_default_hash<Key>, @@ -566,5 +567,16 @@ class NodeHashMapPolicy static const Value& value(const value_type* elem) { return elem->second; } }; } // namespace container_internal + +namespace container_algorithm_internal { + +// Specialization of trait in absl/algorithm/container.h +template <class Key, class T, class Hash, class KeyEqual, class Allocator> +struct IsUnorderedContainer< + absl::node_hash_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {}; + +} // namespace container_algorithm_internal + } // namespace absl + #endif // ABSL_CONTAINER_NODE_HASH_MAP_H_ diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/node_hash_set.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/node_hash_set.h index 813fdeffce0..843b11aa58a 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/node_hash_set.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/container/node_hash_set.h @@ -37,6 +37,7 @@ #include <type_traits> +#include "absl/algorithm/container.h" #include "absl/container/internal/hash_function_defaults.h" // IWYU pragma: export #include "absl/container/internal/node_hash_policy.h" #include "absl/container/internal/raw_hash_set.h" // IWYU pragma: export @@ -67,7 +68,7 @@ struct NodeHashSetPolicy; // By default, `node_hash_set` uses the `absl::Hash` hashing framework. // All fundamental and Abseil types that support the `absl::Hash` framework have // a compatible equality operator for comparing insertions into `node_hash_set`. -// If your type is not yet supported by the `asbl::Hash` framework, see +// If your type is not yet supported by the `absl::Hash` framework, see // absl/hash/hash.h for information on extending Abseil hashing to user-defined // types. // @@ -272,8 +273,7 @@ class node_hash_set // // The element may be constructed even if there already is an element with the // key in the container, in which case the newly constructed element will be - // destroyed immediately. Prefer `try_emplace()` unless your key is not - // copyable or moveable. + // destroyed immediately. // // If rehashing occurs due to the insertion, all iterators are invalidated. using Base::emplace; @@ -287,8 +287,7 @@ class node_hash_set // // The element may be constructed even if there already is an element with the // key in the container, in which case the newly constructed element will be - // destroyed immediately. Prefer `try_emplace()` unless your key is not - // copyable or moveable. + // destroyed immediately. // // If rehashing occurs due to the insertion, all iterators are invalidated. using Base::emplace_hint; @@ -475,5 +474,15 @@ struct NodeHashSetPolicy static size_t element_space_used(const T*) { return sizeof(T); } }; } // namespace container_internal + +namespace container_algorithm_internal { + +// Specialization of trait in absl/algorithm/container.h +template <class Key, class Hash, class KeyEqual, class Allocator> +struct IsUnorderedContainer<absl::node_hash_set<Key, Hash, KeyEqual, Allocator>> + : std::true_type {}; + +} // namespace container_algorithm_internal } // namespace absl + #endif // ABSL_CONTAINER_NODE_HASH_SET_H_ diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts.bzl b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts.bzl deleted file mode 100644 index 49bb697d6e5..00000000000 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts.bzl +++ /dev/null @@ -1,168 +0,0 @@ -"""absl specific copts. - -Flags specified here must not impact ABI. Code compiled with and without these -opts will be linked together, and in some cases headers compiled with and -without these options will be part of the same program. -""" -GCC_FLAGS = [ - "-Wall", - "-Wextra", - "-Wcast-qual", - "-Wconversion-null", - "-Wmissing-declarations", - "-Woverlength-strings", - "-Wpointer-arith", - "-Wunused-local-typedefs", - "-Wunused-result", - "-Wvarargs", - "-Wvla", # variable-length array - "-Wwrite-strings", - # Google style does not use unsigned integers, though STL containers - # have unsigned types. - "-Wno-sign-compare", -] - -GCC_TEST_FLAGS = [ - "-Wno-conversion-null", - "-Wno-missing-declarations", - "-Wno-sign-compare", - "-Wno-unused-function", - "-Wno-unused-parameter", - "-Wno-unused-private-field", -] - -# Docs on single flags is preceded by a comment. -# Docs on groups of flags is preceded by ###. - -LLVM_FLAGS = [ - "-Wall", - "-Wextra", - "-Weverything", - # Abseil does not support C++98 - "-Wno-c++98-compat-pedantic", - # Turns off all implicit conversion warnings. Most are re-enabled below. - "-Wno-conversion", - "-Wno-covered-switch-default", - "-Wno-deprecated", - "-Wno-disabled-macro-expansion", - "-Wno-double-promotion", - ### - # Turned off as they include valid C++ code. - "-Wno-comma", - "-Wno-extra-semi", - "-Wno-packed", - "-Wno-padded", - ### - # Google style does not use unsigned integers, though STL containers - # have unsigned types. - "-Wno-sign-compare", - ### - "-Wno-float-conversion", - "-Wno-float-equal", - "-Wno-format-nonliteral", - # Too aggressive: warns on Clang extensions enclosed in Clang-only - # compilation paths. - "-Wno-gcc-compat", - ### - # Some internal globals are necessary. Don't do this at home. - "-Wno-global-constructors", - "-Wno-exit-time-destructors", - ### - "-Wno-nested-anon-types", - "-Wno-non-modular-include-in-module", - "-Wno-old-style-cast", - # Warns on preferred usage of non-POD types such as string_view - "-Wno-range-loop-analysis", - "-Wno-reserved-id-macro", - "-Wno-shorten-64-to-32", - "-Wno-switch-enum", - "-Wno-thread-safety-negative", - "-Wno-undef", - "-Wno-unknown-warning-option", - "-Wno-unreachable-code", - # Causes warnings on include guards - "-Wno-unused-macros", - "-Wno-weak-vtables", - ### - # Implicit conversion warnings turned off by -Wno-conversion - # which are re-enabled below. - "-Wbitfield-enum-conversion", - "-Wbool-conversion", - "-Wconstant-conversion", - "-Wenum-conversion", - "-Wint-conversion", - "-Wliteral-conversion", - "-Wnon-literal-null-conversion", - "-Wnull-conversion", - "-Wobjc-literal-conversion", - "-Wno-sign-conversion", - "-Wstring-conversion", - ### -] - -LLVM_TEST_FLAGS = [ - "-Wno-c99-extensions", - "-Wno-missing-noreturn", - "-Wno-missing-prototypes", - "-Wno-missing-variable-declarations", - "-Wno-null-conversion", - "-Wno-shadow", - "-Wno-shift-sign-overflow", - "-Wno-sign-compare", - "-Wno-unused-function", - "-Wno-unused-member-function", - "-Wno-unused-parameter", - "-Wno-unused-private-field", - "-Wno-unused-template", - "-Wno-used-but-marked-unused", - "-Wno-zero-as-null-pointer-constant", - # gtest depends on this GNU extension being offered. - "-Wno-gnu-zero-variadic-macro-arguments", -] - -MSVC_FLAGS = [ - "/W3", - "/wd4005", # macro-redefinition - "/wd4068", # unknown pragma - "/wd4180", # qualifier applied to function type has no meaning; ignored - "/wd4244", # conversion from 'type1' to 'type2', possible loss of data - "/wd4267", # conversion from 'size_t' to 'type', possible loss of data - "/wd4800", # forcing value to bool 'true' or 'false' (performance warning) - "/DNOMINMAX", # Don't define min and max macros (windows.h) - "/DWIN32_LEAN_AND_MEAN", # Don't bloat namespace with incompatible winsock versions. - "/D_CRT_SECURE_NO_WARNINGS", # Don't warn about usage of insecure C functions. - "/D_SCL_SECURE_NO_WARNINGS", # Don't warm when the compiler encounters a function or - # variable that is marked as deprecated (same as /wd4996). - "/D_ENABLE_EXTENDED_ALIGNED_STORAGE", # Introduced in VS 2017 15.8, - # before the member type would non-conformingly have an alignment of only alignof(max_align_t). -] - -MSVC_TEST_FLAGS = [ - "/wd4018", # signed/unsigned mismatch - "/wd4101", # unreferenced local variable - "/wd4503", # decorated name length exceeded, name was truncated -] - -# /Wall with msvc includes unhelpful warnings such as C4711, C4710, ... -ABSL_DEFAULT_COPTS = select({ - "//absl:windows": MSVC_FLAGS, - "//absl:llvm_compiler": LLVM_FLAGS, - "//conditions:default": GCC_FLAGS, -}) - -# in absence of modules (--compiler=gcc or -c opt), cc_tests leak their copts -# to their (included header) dependencies and fail to build outside absl -ABSL_TEST_COPTS = ABSL_DEFAULT_COPTS + select({ - "//absl:windows": MSVC_TEST_FLAGS, - "//absl:llvm_compiler": LLVM_TEST_FLAGS, - "//conditions:default": GCC_TEST_FLAGS, -}) - -ABSL_EXCEPTIONS_FLAG = select({ - "//absl:windows": ["/U_HAS_EXCEPTIONS", "/D_HAS_EXCEPTIONS=1", "/EHsc"], - "//conditions:default": ["-fexceptions"], -}) - -ABSL_EXCEPTIONS_FLAG_LINKOPTS = select({ - "//conditions:default": [], -}) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/AbseilConfigureCopts.cmake b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/AbseilConfigureCopts.cmake new file mode 100644 index 00000000000..6fde7754d10 --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/AbseilConfigureCopts.cmake @@ -0,0 +1,34 @@ +# See absl/copts/copts.py and absl/copts/generate_copts.py +include(GENERATED_AbseilCopts) + +if ("${CMAKE_CXX_COMPILER_ID}" STREQUAL "GNU") + set(ABSL_DEFAULT_COPTS "${GCC_FLAGS}") + set(ABSL_TEST_COPTS "${GCC_FLAGS};${GCC_TEST_FLAGS}") + set(ABSL_EXCEPTIONS_FLAG "${GCC_EXCEPTIONS_FLAGS}") +elseif("${CMAKE_CXX_COMPILER_ID}" MATCHES "Clang") + # MATCHES so we get both Clang and AppleClang + set(ABSL_DEFAULT_COPTS "${LLVM_FLAGS}") + set(ABSL_TEST_COPTS "${LLVM_FLAGS};${LLVM_TEST_FLAGS}") + set(ABSL_EXCEPTIONS_FLAG "${LLVM_EXCEPTIONS_FLAGS}") +elseif("${CMAKE_CXX_COMPILER_ID}" STREQUAL "MSVC") + set(ABSL_DEFAULT_COPTS "${MSVC_FLAGS}") + set(ABSL_TEST_COPTS "${MSVC_FLAGS};${MSVC_TEST_FLAGS}") + set(ABSL_EXCEPTIONS_FLAG "${MSVC_EXCEPTIONS_FLAGS}") +else() + message(WARNING "Unknown compiler: ${CMAKE_CXX_COMPILER}. Building with no default flags") + set(ABSL_DEFAULT_COPTS "") + set(ABSL_TEST_COPTS "") + set(ABSL_EXCEPTIONS_FLAG "") +endif() + +# This flag is used internally for Bazel builds and is kept here for consistency +set(ABSL_EXCEPTIONS_FLAG_LINKOPTS "") + +if("${CMAKE_CXX_STANDARD}" EQUAL 98) + message(FATAL_ERROR "Abseil requires at least C++11") +elseif(NOT "${CMAKE_CXX_STANDARD}") + message(STATUS "No CMAKE_CXX_STANDARD set, assuming 11") + set(ABSL_CXX_STANDARD 11) +else() + set(ABSL_CXX_STANDARD "${CMAKE_CXX_STANDARD}") +endif()
\ No newline at end of file diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/GENERATED_AbseilCopts.cmake b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/GENERATED_AbseilCopts.cmake new file mode 100644 index 00000000000..80c98193076 --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/GENERATED_AbseilCopts.cmake @@ -0,0 +1,131 @@ +# GENERATED! DO NOT MANUALLY EDIT THIS FILE. +# +# (1) Edit absl/copts/copts.py. +# (2) Run `python <path_to_absl>/copts/generate_copts.py`. + +list(APPEND GCC_EXCEPTIONS_FLAGS + "-fexceptions" +) + +list(APPEND GCC_FLAGS + "-Wall" + "-Wextra" + "-Wcast-qual" + "-Wconversion-null" + "-Wmissing-declarations" + "-Woverlength-strings" + "-Wpointer-arith" + "-Wunused-local-typedefs" + "-Wunused-result" + "-Wvarargs" + "-Wvla" + "-Wwrite-strings" + "-Wno-sign-compare" +) + +list(APPEND GCC_TEST_FLAGS + "-Wno-conversion-null" + "-Wno-missing-declarations" + "-Wno-sign-compare" + "-Wno-unused-function" + "-Wno-unused-parameter" + "-Wno-unused-private-field" +) + +list(APPEND LLVM_EXCEPTIONS_FLAGS + "-fexceptions" +) + +list(APPEND LLVM_FLAGS + "-Wall" + "-Wextra" + "-Weverything" + "-Wno-c++98-compat-pedantic" + "-Wno-conversion" + "-Wno-covered-switch-default" + "-Wno-deprecated" + "-Wno-disabled-macro-expansion" + "-Wno-double-promotion" + "-Wno-comma" + "-Wno-extra-semi" + "-Wno-extra-semi-stmt" + "-Wno-packed" + "-Wno-padded" + "-Wno-sign-compare" + "-Wno-float-conversion" + "-Wno-float-equal" + "-Wno-format-nonliteral" + "-Wno-gcc-compat" + "-Wno-global-constructors" + "-Wno-exit-time-destructors" + "-Wno-nested-anon-types" + "-Wno-non-modular-include-in-module" + "-Wno-old-style-cast" + "-Wno-range-loop-analysis" + "-Wno-reserved-id-macro" + "-Wno-shorten-64-to-32" + "-Wno-switch-enum" + "-Wno-thread-safety-negative" + "-Wno-undef" + "-Wno-unknown-warning-option" + "-Wno-unreachable-code" + "-Wno-unused-macros" + "-Wno-weak-vtables" + "-Wbitfield-enum-conversion" + "-Wbool-conversion" + "-Wconstant-conversion" + "-Wenum-conversion" + "-Wint-conversion" + "-Wliteral-conversion" + "-Wnon-literal-null-conversion" + "-Wnull-conversion" + "-Wobjc-literal-conversion" + "-Wno-sign-conversion" + "-Wstring-conversion" +) + +list(APPEND LLVM_TEST_FLAGS + "-Wno-c99-extensions" + "-Wno-missing-noreturn" + "-Wno-missing-prototypes" + "-Wno-missing-variable-declarations" + "-Wno-null-conversion" + "-Wno-shadow" + "-Wno-shift-sign-overflow" + "-Wno-sign-compare" + "-Wno-unused-function" + "-Wno-unused-member-function" + "-Wno-unused-parameter" + "-Wno-unused-private-field" + "-Wno-unused-template" + "-Wno-used-but-marked-unused" + "-Wno-zero-as-null-pointer-constant" + "-Wno-gnu-zero-variadic-macro-arguments" +) + +list(APPEND MSVC_EXCEPTIONS_FLAGS + "/U_HAS_EXCEPTIONS" + "/D_HAS_EXCEPTIONS=1" + "/EHsc" +) + +list(APPEND MSVC_FLAGS + "/W3" + "/wd4005" + "/wd4068" + "/wd4180" + "/wd4244" + "/wd4267" + "/wd4800" + "/DNOMINMAX" + "/DWIN32_LEAN_AND_MEAN" + "/D_CRT_SECURE_NO_WARNINGS" + "/D_SCL_SECURE_NO_WARNINGS" + "/D_ENABLE_EXTENDED_ALIGNED_STORAGE" +) + +list(APPEND MSVC_TEST_FLAGS + "/wd4018" + "/wd4101" + "/wd4503" +) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/GENERATED_copts.bzl b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/GENERATED_copts.bzl new file mode 100644 index 00000000000..a001347d490 --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/GENERATED_copts.bzl @@ -0,0 +1,132 @@ +"""GENERATED! DO NOT MANUALLY EDIT THIS FILE. + +(1) Edit absl/copts/copts.py. +(2) Run `python <path_to_absl>/copts/generate_copts.py`. +""" + +GCC_EXCEPTIONS_FLAGS = [ + "-fexceptions", +] + +GCC_FLAGS = [ + "-Wall", + "-Wextra", + "-Wcast-qual", + "-Wconversion-null", + "-Wmissing-declarations", + "-Woverlength-strings", + "-Wpointer-arith", + "-Wunused-local-typedefs", + "-Wunused-result", + "-Wvarargs", + "-Wvla", + "-Wwrite-strings", + "-Wno-sign-compare", +] + +GCC_TEST_FLAGS = [ + "-Wno-conversion-null", + "-Wno-missing-declarations", + "-Wno-sign-compare", + "-Wno-unused-function", + "-Wno-unused-parameter", + "-Wno-unused-private-field", +] + +LLVM_EXCEPTIONS_FLAGS = [ + "-fexceptions", +] + +LLVM_FLAGS = [ + "-Wall", + "-Wextra", + "-Weverything", + "-Wno-c++98-compat-pedantic", + "-Wno-conversion", + "-Wno-covered-switch-default", + "-Wno-deprecated", + "-Wno-disabled-macro-expansion", + "-Wno-double-promotion", + "-Wno-comma", + "-Wno-extra-semi", + "-Wno-extra-semi-stmt", + "-Wno-packed", + "-Wno-padded", + "-Wno-sign-compare", + "-Wno-float-conversion", + "-Wno-float-equal", + "-Wno-format-nonliteral", + "-Wno-gcc-compat", + "-Wno-global-constructors", + "-Wno-exit-time-destructors", + "-Wno-nested-anon-types", + "-Wno-non-modular-include-in-module", + "-Wno-old-style-cast", + "-Wno-range-loop-analysis", + "-Wno-reserved-id-macro", + "-Wno-shorten-64-to-32", + "-Wno-switch-enum", + "-Wno-thread-safety-negative", + "-Wno-undef", + "-Wno-unknown-warning-option", + "-Wno-unreachable-code", + "-Wno-unused-macros", + "-Wno-weak-vtables", + "-Wbitfield-enum-conversion", + "-Wbool-conversion", + "-Wconstant-conversion", + "-Wenum-conversion", + "-Wint-conversion", + "-Wliteral-conversion", + "-Wnon-literal-null-conversion", + "-Wnull-conversion", + "-Wobjc-literal-conversion", + "-Wno-sign-conversion", + "-Wstring-conversion", +] + +LLVM_TEST_FLAGS = [ + "-Wno-c99-extensions", + "-Wno-missing-noreturn", + "-Wno-missing-prototypes", + "-Wno-missing-variable-declarations", + "-Wno-null-conversion", + "-Wno-shadow", + "-Wno-shift-sign-overflow", + "-Wno-sign-compare", + "-Wno-unused-function", + "-Wno-unused-member-function", + "-Wno-unused-parameter", + "-Wno-unused-private-field", + "-Wno-unused-template", + "-Wno-used-but-marked-unused", + "-Wno-zero-as-null-pointer-constant", + "-Wno-gnu-zero-variadic-macro-arguments", +] + +MSVC_EXCEPTIONS_FLAGS = [ + "/U_HAS_EXCEPTIONS", + "/D_HAS_EXCEPTIONS=1", + "/EHsc", +] + +MSVC_FLAGS = [ + "/W3", + "/wd4005", + "/wd4068", + "/wd4180", + "/wd4244", + "/wd4267", + "/wd4800", + "/DNOMINMAX", + "/DWIN32_LEAN_AND_MEAN", + "/D_CRT_SECURE_NO_WARNINGS", + "/D_SCL_SECURE_NO_WARNINGS", + "/D_ENABLE_EXTENDED_ALIGNED_STORAGE", +] + +MSVC_TEST_FLAGS = [ + "/wd4018", + "/wd4101", + "/wd4503", +] diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/configure_copts.bzl b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/configure_copts.bzl new file mode 100644 index 00000000000..57cd3f62998 --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/configure_copts.bzl @@ -0,0 +1,42 @@ +"""absl specific copts. + +This file simply selects the correct options from the generated files. To +change Abseil copts, edit absl/copts/copts.py +""" + +load( + "//absl:copts/GENERATED_copts.bzl", + "GCC_EXCEPTIONS_FLAGS", + "GCC_FLAGS", + "GCC_TEST_FLAGS", + "LLVM_EXCEPTIONS_FLAGS", + "LLVM_FLAGS", + "LLVM_TEST_FLAGS", + "MSVC_EXCEPTIONS_FLAGS", + "MSVC_FLAGS", + "MSVC_TEST_FLAGS", +) + +ABSL_DEFAULT_COPTS = select({ + "//absl:windows": MSVC_FLAGS, + "//absl:llvm_compiler": LLVM_FLAGS, + "//conditions:default": GCC_FLAGS, +}) + +# in absence of modules (--compiler=gcc or -c opt), cc_tests leak their copts +# to their (included header) dependencies and fail to build outside absl +ABSL_TEST_COPTS = ABSL_DEFAULT_COPTS + select({ + "//absl:windows": MSVC_TEST_FLAGS, + "//absl:llvm_compiler": LLVM_TEST_FLAGS, + "//conditions:default": GCC_TEST_FLAGS, +}) + +ABSL_EXCEPTIONS_FLAG = select({ + "//absl:windows": MSVC_EXCEPTIONS_FLAGS, + "//absl:llvm_compiler": LLVM_EXCEPTIONS_FLAGS, + "//conditions:default": GCC_EXCEPTIONS_FLAGS, +}) + +ABSL_EXCEPTIONS_FLAG_LINKOPTS = select({ + "//conditions:default": [], +}) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/copts.py b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/copts.py new file mode 100644 index 00000000000..40a8062f33b --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/copts.py @@ -0,0 +1,157 @@ +"""Abseil compiler options. + +This is the source of truth for Abseil compiler options. To modify Abseil +compilation options: + + (1) Edit the appropriate list in this file based on the platform the flag is + needed on. + (2) Run `<path_to_absl>/copts/generate_copts.py`. + +The generated copts are consumed by configure_copts.bzl and +AbseilConfigureCopts.cmake. +""" + +import collections # absl:google-only(used for internal flags) +COPT_VARS = { + "GCC_FLAGS": [ + "-Wall", + "-Wextra", + "-Wcast-qual", + "-Wconversion-null", + "-Wmissing-declarations", + "-Woverlength-strings", + "-Wpointer-arith", + "-Wunused-local-typedefs", + "-Wunused-result", + "-Wvarargs", + "-Wvla", # variable-length array + "-Wwrite-strings", + # Google style does not use unsigned integers, though STL containers + # have unsigned types. + "-Wno-sign-compare", + ], + "GCC_TEST_FLAGS": [ + "-Wno-conversion-null", + "-Wno-missing-declarations", + "-Wno-sign-compare", + "-Wno-unused-function", + "-Wno-unused-parameter", + "-Wno-unused-private-field", + ], + "GCC_EXCEPTIONS_FLAGS": ["-fexceptions"], + + # Docs on single flags is preceded by a comment. + # Docs on groups of flags is preceded by ###. + "LLVM_FLAGS": [ + "-Wall", + "-Wextra", + "-Weverything", + # Abseil does not support C++98 + "-Wno-c++98-compat-pedantic", + # Turns off all implicit conversion warnings. Most are re-enabled below. + "-Wno-conversion", + "-Wno-covered-switch-default", + "-Wno-deprecated", + "-Wno-disabled-macro-expansion", + "-Wno-double-promotion", + ### + # Turned off as they include valid C++ code. + "-Wno-comma", + "-Wno-extra-semi", + "-Wno-extra-semi-stmt", + "-Wno-packed", + "-Wno-padded", + ### + # Google style does not use unsigned integers, though STL containers + # have unsigned types. + "-Wno-sign-compare", + ### + "-Wno-float-conversion", + "-Wno-float-equal", + "-Wno-format-nonliteral", + # Too aggressive: warns on Clang extensions enclosed in Clang-only + # compilation paths. + "-Wno-gcc-compat", + ### + # Some internal globals are necessary. Don't do this at home. + "-Wno-global-constructors", + "-Wno-exit-time-destructors", + ### + "-Wno-nested-anon-types", + "-Wno-non-modular-include-in-module", + "-Wno-old-style-cast", + # Warns on preferred usage of non-POD types such as string_view + "-Wno-range-loop-analysis", + "-Wno-reserved-id-macro", + "-Wno-shorten-64-to-32", + "-Wno-switch-enum", + "-Wno-thread-safety-negative", + "-Wno-undef", + "-Wno-unknown-warning-option", + "-Wno-unreachable-code", + # Causes warnings on include guards + "-Wno-unused-macros", + "-Wno-weak-vtables", + ### + # Implicit conversion warnings turned off by -Wno-conversion + # which are re-enabled below. + "-Wbitfield-enum-conversion", + "-Wbool-conversion", + "-Wconstant-conversion", + "-Wenum-conversion", + "-Wint-conversion", + "-Wliteral-conversion", + "-Wnon-literal-null-conversion", + "-Wnull-conversion", + "-Wobjc-literal-conversion", + "-Wno-sign-conversion", + "-Wstring-conversion", + ], + "LLVM_TEST_FLAGS": [ + "-Wno-c99-extensions", + "-Wno-missing-noreturn", + "-Wno-missing-prototypes", + "-Wno-missing-variable-declarations", + "-Wno-null-conversion", + "-Wno-shadow", + "-Wno-shift-sign-overflow", + "-Wno-sign-compare", + "-Wno-unused-function", + "-Wno-unused-member-function", + "-Wno-unused-parameter", + "-Wno-unused-private-field", + "-Wno-unused-template", + "-Wno-used-but-marked-unused", + "-Wno-zero-as-null-pointer-constant", + # gtest depends on this GNU extension being offered. + "-Wno-gnu-zero-variadic-macro-arguments", + ], + "LLVM_EXCEPTIONS_FLAGS": ["-fexceptions"], + # /Wall with msvc includes unhelpful warnings such as C4711, C4710, ... + "MSVC_FLAGS": [ + "/W3", + "/wd4005", # macro-redefinition + "/wd4068", # unknown pragma + "/wd4180", # qualifier applied to function type has no meaning; ignored + "/wd4244", # conversion from 'type1' to 'type2', possible loss of data + "/wd4267", # conversion from 'size_t' to 'type', possible loss of data + # forcing value to bool 'true' or 'false' (performance warning) + "/wd4800", + "/DNOMINMAX", # Don't define min and max macros (windows.h) + # Don't bloat namespace with incompatible winsock versions. + "/DWIN32_LEAN_AND_MEAN", + # Don't warn about usage of insecure C functions. + "/D_CRT_SECURE_NO_WARNINGS", + "/D_SCL_SECURE_NO_WARNINGS", + # Introduced in VS 2017 15.8, allow overaligned types in aligned_storage + "/D_ENABLE_EXTENDED_ALIGNED_STORAGE", + ], + "MSVC_TEST_FLAGS": [ + "/wd4018", # signed/unsigned mismatch + "/wd4101", # unreferenced local variable + "/wd4503", # decorated name length exceeded, name was truncated + ], + "MSVC_EXCEPTIONS_FLAGS": [ + "/U_HAS_EXCEPTIONS", "/D_HAS_EXCEPTIONS=1", "/EHsc" + ] +} diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/generate_copts.py b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/generate_copts.py new file mode 100755 index 00000000000..28b677e0cd3 --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/copts/generate_copts.py @@ -0,0 +1,108 @@ +#!/usr/bin/python +"""Generate Abseil compile compile option configs. + +Usage: <path_to_absl>/copts/generate_copts.py + +The configs are generated from copts.py. +""" + +from os import path +import sys +from copts import COPT_VARS + + +# Helper functions +def file_header_lines(): + return [ + "GENERATED! DO NOT MANUALLY EDIT THIS FILE.", "", + "(1) Edit absl/copts/copts.py.", + "(2) Run `python <path_to_absl>/copts/generate_copts.py`." + ] + + +def flatten(*lists): + return [item for sublist in lists for item in sublist] + + +def relative_filename(filename): + return path.join(path.dirname(__file__), filename) + + +# Style classes. These contain all the syntactic styling needed to generate a +# copt file for different build tools. +class CMakeStyle(object): + """Style object for CMake copts file.""" + + def separator(self): + return "" + + def list_introducer(self, name): + return "list(APPEND " + name + + def list_closer(self): + return ")\n" + + def docstring(self): + return "\n".join((("# " + line).strip() for line in file_header_lines())) + + def filename(self): + return "GENERATED_AbseilCopts.cmake" + + +class StarlarkStyle(object): + """Style object for Starlark copts file.""" + + def separator(self): + return "," + + def list_introducer(self, name): + return name + " = [" + + def list_closer(self): + return "]\n" + + def docstring(self): + docstring_quotes = "\"\"\"" + return docstring_quotes + "\n".join( + flatten(file_header_lines(), [docstring_quotes])) + + def filename(self): + return "GENERATED_copts.bzl" + + +# Copt file generation +def copt_list(name, arg_list, style): + make_line = lambda s: " \"" + s + "\"" + style.separator() + external_str_list = [make_line(s) for s in arg_list] + + return "\n".join( + flatten( + [style.list_introducer(name)], + external_str_list, + [style.list_closer()])) + + +def generate_copt_file(style): + """Creates a generated copt file using the given style object. + + Args: + style: either StarlarkStyle() or CMakeStyle() + """ + with open(relative_filename(style.filename()), "w") as f: + f.write(style.docstring()) + f.write("\n") + for var_name, arg_list in sorted(COPT_VARS.items()): + f.write("\n") + f.write(copt_list(var_name, arg_list, style)) + + +def main(argv): + if len(argv) > 1: + raise RuntimeError("generate_copts needs no command line args") + + generate_copt_file(StarlarkStyle()) + generate_copt_file(CMakeStyle()) + + +if __name__ == "__main__": + main(sys.argv) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/BUILD.bazel index a8ebaea445e..84b994da31e 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/BUILD.bazel @@ -15,7 +15,7 @@ # load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", ) @@ -181,22 +181,8 @@ cc_test( cc_library( name = "leak_check", - srcs = select({ - # The leak checking interface depends on weak function - # declarations that may not necessarily have definitions. - # Windows doesn't support this, and ios requires - # guaranteed definitions for weak symbols. - "//absl:ios": [], - "//absl:windows": [], - "//conditions:default": [ - "leak_check.cc", - ], - }), - hdrs = select({ - "//absl:ios": [], - "//absl:windows": [], - "//conditions:default": ["leak_check.h"], - }), + srcs = ["leak_check.cc"], + hdrs = ["leak_check.h"], deps = ["//absl/base:core_headers"], ) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/failure_signal_handler.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/failure_signal_handler.cc index d4b957bc2e4..c2e56f9d819 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/failure_signal_handler.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/failure_signal_handler.cc @@ -119,7 +119,11 @@ const char* FailureSignalToString(int signo) { #ifndef _WIN32 static bool SetupAlternateStackOnce() { +#if defined(__wasm__) || defined (__asjms__) const size_t page_mask = getpagesize() - 1; +#else + const size_t page_mask = sysconf(_SC_PAGESIZE) - 1; +#endif size_t stack_size = (std::max(SIGSTKSZ, 65536) + page_mask) & ~page_mask; #if defined(ADDRESS_SANITIZER) || defined(MEMORY_SANITIZER) || \ defined(THREAD_SANITIZER) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/internal/demangle.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/internal/demangle.cc index 48354459bc8..3ee3df51438 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/internal/demangle.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/internal/demangle.cc @@ -1636,6 +1636,15 @@ static bool ParseExpression(State *state) { } state->parse_state = copy; + // Pointer-to-member access expressions. This parses the same as a binary + // operator, but it's implemented separately because "ds" shouldn't be + // accepted in other contexts that parse an operator name. + if (ParseTwoCharToken(state, "ds") && ParseExpression(state) && + ParseExpression(state)) { + return true; + } + state->parse_state = copy; + // Parameter pack expansion if (ParseTwoCharToken(state, "sp") && ParseExpression(state)) { return true; diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/symbolize_elf.inc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/symbolize_elf.inc index e21439ce3fa..97d767abf11 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/symbolize_elf.inc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/debugging/symbolize_elf.inc @@ -333,7 +333,11 @@ static std::atomic<Symbolizer *> g_cached_symbolizer; } // namespace static int SymbolizerSize() { +#if defined(__wasm__) || defined(__asmjs__) int pagesize = getpagesize(); +#else + int pagesize = sysconf(_SC_PAGESIZE); +#endif return ((sizeof(Symbolizer) - 1) / pagesize + 1) * pagesize; } diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/hash/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/hash/BUILD.bazel index 4f7c94ceb35..5f24b99977c 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/hash/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/hash/BUILD.bazel @@ -15,7 +15,7 @@ # load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", ) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/hash/internal/hash.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/hash/internal/hash.h index 710607752e3..6c00f35413d 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/hash/internal/hash.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/hash/internal/hash.h @@ -303,13 +303,13 @@ H hash_tuple(H hash_state, const Tuple& t, absl::index_sequence<Is...>) { // AbslHashValue for hashing tuples template <typename H, typename... Ts> -#if _MSC_VER +#if defined(_MSC_VER) // This SFINAE gets MSVC confused under some conditions. Let's just disable it // for now. H -#else +#else // _MSC_VER typename std::enable_if<absl::conjunction<is_hashable<Ts>...>::value, H>::type -#endif +#endif // _MSC_VER AbslHashValue(H hash_state, const std::tuple<Ts...>& t) { return hash_internal::hash_tuple(std::move(hash_state), t, absl::make_index_sequence<sizeof...(Ts)>()); @@ -545,7 +545,7 @@ hash_range_or_bytes(H hash_state, const T* data, size_t size) { // In MSVC we can't probe std::hash or stdext::hash because it triggers a // static_assert instead of failing substitution. #if defined(_MSC_VER) -#undef ABSL_HASH_INTERNAL_CAN_POISON_ +#define ABSL_HASH_INTERNAL_CAN_POISON_ 0 #else // _MSC_VER #define ABSL_HASH_INTERNAL_CAN_POISON_ 1 #endif // _MSC_VER @@ -553,6 +553,8 @@ hash_range_or_bytes(H hash_state, const T* data, size_t size) { #if defined(ABSL_INTERNAL_LEGACY_HASH_NAMESPACE) && \ ABSL_HASH_INTERNAL_CAN_POISON_ #define ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ 1 +#else +#define ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ 0 #endif enum class InvokeHashTag { @@ -773,7 +775,6 @@ class CityHashState : public HashStateBase<CityHashState> { } ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Mix(uint64_t state, uint64_t v) { -#if !defined(_MSC_VER) || !defined(_WIN64) using MultType = absl::conditional_t<sizeof(size_t) == 4, uint64_t, uint128>; // We do the addition in 64-bit space to make sure the 128-bit @@ -783,11 +784,6 @@ class CityHashState : public HashStateBase<CityHashState> { MultType m = state + v; m *= kMul; return static_cast<uint64_t>(m ^ (m >> (sizeof(m) * 8 / 2))); -#else - uint64_t high; - uint64_t low = _umul128(state + v, kMul, &high); - return low ^ high; -#endif } // Seed() diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/memory/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/memory/BUILD.bazel index 89a312eac4b..c0da9ce1d84 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/memory/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/memory/BUILD.bazel @@ -15,7 +15,7 @@ # load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", "ABSL_EXCEPTIONS_FLAG", diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/memory/memory_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/memory/memory_test.cc index 54f920b5496..21fe32f9350 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/memory/memory_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/memory/memory_test.cc @@ -69,6 +69,45 @@ TEST(MakeUniqueTest, Basic) { EXPECT_EQ("hi", *p); } +// InitializationVerifier fills in a pattern when allocated so we can +// distinguish between its default and value initialized states (without +// accessing truly uninitialized memory). +struct InitializationVerifier { + static constexpr int kDefaultScalar = 0x43; + static constexpr int kDefaultArray = 0x4B; + + static void* operator new(size_t n) { + void* ret = ::operator new(n); + memset(ret, kDefaultScalar, n); + return ret; + } + + static void* operator new[](size_t n) { + void* ret = ::operator new[](n); + memset(ret, kDefaultArray, n); + return ret; + } + + int a; + int b; +}; + +TEST(Initialization, MakeUnique) { + auto p = absl::make_unique<InitializationVerifier>(); + + EXPECT_EQ(0, p->a); + EXPECT_EQ(0, p->b); +} + +TEST(Initialization, MakeUniqueArray) { + auto p = absl::make_unique<InitializationVerifier[]>(2); + + EXPECT_EQ(0, p[0].a); + EXPECT_EQ(0, p[0].b); + EXPECT_EQ(0, p[1].a); + EXPECT_EQ(0, p[1].b); +} + struct MoveOnly { MoveOnly() = default; explicit MoveOnly(int i1) : ip1{new int{i1}} {} diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/meta/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/meta/BUILD.bazel index dbc9717ddd3..1c39fa98b63 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/meta/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/meta/BUILD.bazel @@ -1,5 +1,5 @@ load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", ) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/BUILD.bazel index 324ce6695e4..c906b8d750a 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/BUILD.bazel @@ -13,7 +13,7 @@ # limitations under the License. load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", ) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128.h index 5d14a4a8962..9c36c57116c 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128.h @@ -37,6 +37,20 @@ #include "absl/base/macros.h" #include "absl/base/port.h" +#if defined(_MSC_VER) +// In very old versions of MSVC and when the /Zc:wchar_t flag is off, wchar_t is +// a typedef for unsigned short. Otherwise wchar_t is mapped to the __wchar_t +// builtin type. We need to make sure not to define operator wchar_t() +// alongside operator unsigned short() in these instances. +#define ABSL_INTERNAL_WCHAR_T __wchar_t +#if defined(_WIN64) +#include <intrin.h> +#pragma intrinsic(_umul128) +#endif // defined(_WIN64) +#else // defined(_MSC_VER) +#define ABSL_INTERNAL_WCHAR_T wchar_t +#endif // defined(_MSC_VER) + namespace absl { @@ -126,7 +140,7 @@ class constexpr explicit operator unsigned char() const; constexpr explicit operator char16_t() const; constexpr explicit operator char32_t() const; - constexpr explicit operator wchar_t() const; + constexpr explicit operator ABSL_INTERNAL_WCHAR_T() const; constexpr explicit operator short() const; // NOLINT(runtime/int) // NOLINTNEXTLINE(runtime/int) constexpr explicit operator unsigned short() const; @@ -266,9 +280,9 @@ class numeric_limits<absl::uint128> { #endif // ABSL_HAVE_INTRINSIC_INT128 static constexpr bool tinyness_before = false; - static constexpr absl::uint128 min() { return 0; } + static constexpr absl::uint128 (min)() { return 0; } static constexpr absl::uint128 lowest() { return 0; } - static constexpr absl::uint128 max() { return absl::Uint128Max(); } + static constexpr absl::uint128 (max)() { return absl::Uint128Max(); } static constexpr absl::uint128 epsilon() { return 0; } static constexpr absl::uint128 round_error() { return 0; } static constexpr absl::uint128 infinity() { return 0; } @@ -463,8 +477,8 @@ constexpr uint128::operator char32_t() const { return static_cast<char32_t>(lo_); } -constexpr uint128::operator wchar_t() const { - return static_cast<wchar_t>(lo_); +constexpr uint128::operator ABSL_INTERNAL_WCHAR_T() const { + return static_cast<ABSL_INTERNAL_WCHAR_T>(lo_); } // NOLINTNEXTLINE(runtime/int) @@ -661,6 +675,12 @@ inline uint128 operator*(uint128 lhs, uint128 rhs) { // can be used for uint128 storage. return static_cast<unsigned __int128>(lhs) * static_cast<unsigned __int128>(rhs); +#elif defined(_MSC_VER) && defined(_WIN64) + uint64_t carry; + uint64_t low = _umul128(Uint128Low64(lhs), Uint128Low64(rhs), &carry); + return MakeUint128(Uint128Low64(lhs) * Uint128High64(rhs) + + Uint128High64(lhs) * Uint128Low64(rhs) + carry, + low); #else // ABSL_HAVE_INTRINSIC128 uint64_t a32 = Uint128Low64(lhs) >> 32; uint64_t a00 = Uint128Low64(lhs) & 0xffffffff; @@ -708,4 +728,6 @@ inline uint128& uint128::operator--() { } // namespace absl +#undef ABSL_INTERNAL_WCHAR_T + #endif // ABSL_NUMERIC_INT128_H_ diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128_have_intrinsic.inc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128_have_intrinsic.inc index ee2a093018d..0c8164a5444 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128_have_intrinsic.inc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128_have_intrinsic.inc @@ -15,4 +15,4 @@ // This file contains :int128 implementation details that depend on internal // representation when ABSL_HAVE_INTRINSIC_INT128 is defined. This file is -// included by int128.h. +// included by int128.h and relies on ABSL_INTERNAL_WCHAR_T being defined. diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128_no_intrinsic.inc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128_no_intrinsic.inc index 0d0b3cfdeb1..08d68ac3ea5 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128_no_intrinsic.inc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/numeric/int128_no_intrinsic.inc @@ -15,4 +15,4 @@ // This file contains :int128 implementation details that depend on internal // representation when ABSL_HAVE_INTRINSIC_INT128 is *not* defined. This file -// is included by int128.h. +// is included by int128.h and relies on ABSL_INTERNAL_WCHAR_T being defined. diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/BUILD.bazel index 6d7c2619a53..7635a6198ab 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/BUILD.bazel @@ -15,7 +15,7 @@ # load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", "ABSL_EXCEPTIONS_FLAG", @@ -413,6 +413,7 @@ cc_test( copts = ABSL_TEST_COPTS, visibility = ["//visibility:private"], deps = [ + ":pow10_helper", ":strings", "//absl/base", "//absl/base:core_headers", @@ -471,6 +472,8 @@ cc_test( srcs = ["charconv_test.cc"], copts = ABSL_TEST_COPTS, deps = [ + ":pow10_helper", + ":str_format", ":strings", "//absl/base", "@com_google_googletest//:gtest_main", @@ -659,3 +662,23 @@ cc_test( "@com_google_googletest//:gtest_main", ], ) + +cc_library( + name = "pow10_helper", + testonly = True, + srcs = ["internal/pow10_helper.cc"], + hdrs = ["internal/pow10_helper.h"], + visibility = ["//visibility:private"], +) + +cc_test( + name = "pow10_helper_test", + srcs = ["internal/pow10_helper_test.cc"], + copts = ABSL_TEST_COPTS, + visibility = ["//visibility:private"], + deps = [ + ":pow10_helper", + ":str_format", + "@com_google_googletest//:gtest_main", + ], +) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/charconv_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/charconv_test.cc index 89418fe948f..d07537eb590 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/charconv_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/charconv_test.cc @@ -19,7 +19,9 @@ #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "absl/strings/internal/pow10_helper.h" #include "absl/strings/str_cat.h" +#include "absl/strings/str_format.h" #ifdef _MSC_FULL_VER #define ABSL_COMPILER_DOES_EXACT_ROUNDING 0 @@ -31,6 +33,8 @@ namespace { +using absl::strings_internal::Pow10; + #if ABSL_COMPILER_DOES_EXACT_ROUNDING // Tests that the given string is accepted by absl::from_chars, and that it @@ -678,7 +682,8 @@ void TestOverflowAndUnderflow( auto result = absl::from_chars(input.data(), input.data() + input.size(), actual); EXPECT_EQ(result.ec, std::errc()); - EXPECT_EQ(expected, actual); + EXPECT_EQ(expected, actual) + << absl::StrFormat("%a vs %a", expected, actual); } // test legal values near upper_bound for (index = upper_bound, step = 1; index > lower_bound; @@ -690,7 +695,8 @@ void TestOverflowAndUnderflow( auto result = absl::from_chars(input.data(), input.data() + input.size(), actual); EXPECT_EQ(result.ec, std::errc()); - EXPECT_EQ(expected, actual); + EXPECT_EQ(expected, actual) + << absl::StrFormat("%a vs %a", expected, actual); } // Test underflow values below lower_bound for (index = lower_bound - 1, step = 1; index > -1000000; @@ -747,7 +753,7 @@ TEST(FromChars, HexdecimalFloatLimits) { // acceptable exponents in this test. TEST(FromChars, DecimalDoubleLimits) { auto input_gen = [](int index) { return absl::StrCat("1.0e", index); }; - auto expected_gen = [](int index) { return std::pow(10.0, index); }; + auto expected_gen = [](int index) { return Pow10(index); }; TestOverflowAndUnderflow<double>(input_gen, expected_gen, -323, 308); } @@ -759,7 +765,7 @@ TEST(FromChars, DecimalDoubleLimits) { // acceptable exponents in this test. TEST(FromChars, DecimalFloatLimits) { auto input_gen = [](int index) { return absl::StrCat("1.0e", index); }; - auto expected_gen = [](int index) { return std::pow(10.0, index); }; + auto expected_gen = [](int index) { return Pow10(index); }; TestOverflowAndUnderflow<float>(input_gen, expected_gen, -45, 38); } diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/charconv_bigint.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/charconv_bigint.h index 5c579437e52..9d1a1bffe17 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/charconv_bigint.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/charconv_bigint.h @@ -103,12 +103,12 @@ class BigUnsigned { SetToZero(); return; } - size_ = std::min(size_ + word_shift, max_words); + size_ = (std::min)(size_ + word_shift, max_words); count %= 32; if (count == 0) { std::copy_backward(words_, words_ + size_ - word_shift, words_ + size_); } else { - for (int i = std::min(size_, max_words - 1); i > word_shift; --i) { + for (int i = (std::min)(size_, max_words - 1); i > word_shift; --i) { words_[i] = (words_[i - word_shift] << count) | (words_[i - word_shift - 1] >> (32 - count)); } @@ -267,7 +267,7 @@ class BigUnsigned { void MultiplyBy(int other_size, const uint32_t* other_words) { const int original_size = size_; const int first_step = - std::min(original_size + other_size - 2, max_words - 1); + (std::min)(original_size + other_size - 2, max_words - 1); for (int step = first_step; step >= 0; --step) { MultiplyStep(original_size, other_words, other_size, step); } @@ -286,7 +286,7 @@ class BigUnsigned { value = 0; } } - size_ = std::min(max_words, std::max(index + 1, size_)); + size_ = (std::min)(max_words, (std::max)(index + 1, size_)); } } @@ -309,7 +309,7 @@ class BigUnsigned { } else { // Normally 32-bit AddWithCarry() sets size_, but since we don't call // it when `high` is 0, do it ourselves here. - size_ = std::min(max_words, std::max(index + 1, size_)); + size_ = (std::min)(max_words, (std::max)(index + 1, size_)); } } } @@ -348,7 +348,7 @@ class BigUnsigned { // Returns -1 if lhs < rhs, 0 if lhs == rhs, and 1 if lhs > rhs. template <int N, int M> int Compare(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) { - int limit = std::max(lhs.size(), rhs.size()); + int limit = (std::max)(lhs.size(), rhs.size()); for (int i = limit - 1; i >= 0; --i) { const uint32_t lhs_word = lhs.GetWord(i); const uint32_t rhs_word = rhs.GetWord(i); @@ -363,7 +363,7 @@ int Compare(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) { template <int N, int M> bool operator==(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) { - int limit = std::max(lhs.size(), rhs.size()); + int limit = (std::max)(lhs.size(), rhs.size()); for (int i = 0; i < limit; ++i) { if (lhs.GetWord(i) != rhs.GetWord(i)) { return false; diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/pow10_helper.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/pow10_helper.cc new file mode 100644 index 00000000000..66be163f43f --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/pow10_helper.cc @@ -0,0 +1,120 @@ +// 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/strings/internal/pow10_helper.h" + +#include <cmath> + +namespace absl { +namespace strings_internal { + +namespace { + +// The exact value of 1e23 falls precisely halfway between two representable +// doubles. Furthermore, the rounding rules we prefer (break ties by rounding +// to the nearest even) dictate in this case that the number should be rounded +// down, but this is not completely specified for floating-point literals in +// C++. (It just says to use the default rounding mode of the standard +// library.) We ensure the result we want by using a number that has an +// unambiguous correctly rounded answer. +constexpr double k1e23 = 9999999999999999e7; + +constexpr double kPowersOfTen[] = { + 0.0, 1e-323, 1e-322, 1e-321, 1e-320, 1e-319, 1e-318, 1e-317, 1e-316, + 1e-315, 1e-314, 1e-313, 1e-312, 1e-311, 1e-310, 1e-309, 1e-308, 1e-307, + 1e-306, 1e-305, 1e-304, 1e-303, 1e-302, 1e-301, 1e-300, 1e-299, 1e-298, + 1e-297, 1e-296, 1e-295, 1e-294, 1e-293, 1e-292, 1e-291, 1e-290, 1e-289, + 1e-288, 1e-287, 1e-286, 1e-285, 1e-284, 1e-283, 1e-282, 1e-281, 1e-280, + 1e-279, 1e-278, 1e-277, 1e-276, 1e-275, 1e-274, 1e-273, 1e-272, 1e-271, + 1e-270, 1e-269, 1e-268, 1e-267, 1e-266, 1e-265, 1e-264, 1e-263, 1e-262, + 1e-261, 1e-260, 1e-259, 1e-258, 1e-257, 1e-256, 1e-255, 1e-254, 1e-253, + 1e-252, 1e-251, 1e-250, 1e-249, 1e-248, 1e-247, 1e-246, 1e-245, 1e-244, + 1e-243, 1e-242, 1e-241, 1e-240, 1e-239, 1e-238, 1e-237, 1e-236, 1e-235, + 1e-234, 1e-233, 1e-232, 1e-231, 1e-230, 1e-229, 1e-228, 1e-227, 1e-226, + 1e-225, 1e-224, 1e-223, 1e-222, 1e-221, 1e-220, 1e-219, 1e-218, 1e-217, + 1e-216, 1e-215, 1e-214, 1e-213, 1e-212, 1e-211, 1e-210, 1e-209, 1e-208, + 1e-207, 1e-206, 1e-205, 1e-204, 1e-203, 1e-202, 1e-201, 1e-200, 1e-199, + 1e-198, 1e-197, 1e-196, 1e-195, 1e-194, 1e-193, 1e-192, 1e-191, 1e-190, + 1e-189, 1e-188, 1e-187, 1e-186, 1e-185, 1e-184, 1e-183, 1e-182, 1e-181, + 1e-180, 1e-179, 1e-178, 1e-177, 1e-176, 1e-175, 1e-174, 1e-173, 1e-172, + 1e-171, 1e-170, 1e-169, 1e-168, 1e-167, 1e-166, 1e-165, 1e-164, 1e-163, + 1e-162, 1e-161, 1e-160, 1e-159, 1e-158, 1e-157, 1e-156, 1e-155, 1e-154, + 1e-153, 1e-152, 1e-151, 1e-150, 1e-149, 1e-148, 1e-147, 1e-146, 1e-145, + 1e-144, 1e-143, 1e-142, 1e-141, 1e-140, 1e-139, 1e-138, 1e-137, 1e-136, + 1e-135, 1e-134, 1e-133, 1e-132, 1e-131, 1e-130, 1e-129, 1e-128, 1e-127, + 1e-126, 1e-125, 1e-124, 1e-123, 1e-122, 1e-121, 1e-120, 1e-119, 1e-118, + 1e-117, 1e-116, 1e-115, 1e-114, 1e-113, 1e-112, 1e-111, 1e-110, 1e-109, + 1e-108, 1e-107, 1e-106, 1e-105, 1e-104, 1e-103, 1e-102, 1e-101, 1e-100, + 1e-99, 1e-98, 1e-97, 1e-96, 1e-95, 1e-94, 1e-93, 1e-92, 1e-91, + 1e-90, 1e-89, 1e-88, 1e-87, 1e-86, 1e-85, 1e-84, 1e-83, 1e-82, + 1e-81, 1e-80, 1e-79, 1e-78, 1e-77, 1e-76, 1e-75, 1e-74, 1e-73, + 1e-72, 1e-71, 1e-70, 1e-69, 1e-68, 1e-67, 1e-66, 1e-65, 1e-64, + 1e-63, 1e-62, 1e-61, 1e-60, 1e-59, 1e-58, 1e-57, 1e-56, 1e-55, + 1e-54, 1e-53, 1e-52, 1e-51, 1e-50, 1e-49, 1e-48, 1e-47, 1e-46, + 1e-45, 1e-44, 1e-43, 1e-42, 1e-41, 1e-40, 1e-39, 1e-38, 1e-37, + 1e-36, 1e-35, 1e-34, 1e-33, 1e-32, 1e-31, 1e-30, 1e-29, 1e-28, + 1e-27, 1e-26, 1e-25, 1e-24, 1e-23, 1e-22, 1e-21, 1e-20, 1e-19, + 1e-18, 1e-17, 1e-16, 1e-15, 1e-14, 1e-13, 1e-12, 1e-11, 1e-10, + 1e-9, 1e-8, 1e-7, 1e-6, 1e-5, 1e-4, 1e-3, 1e-2, 1e-1, + 1e+0, 1e+1, 1e+2, 1e+3, 1e+4, 1e+5, 1e+6, 1e+7, 1e+8, + 1e+9, 1e+10, 1e+11, 1e+12, 1e+13, 1e+14, 1e+15, 1e+16, 1e+17, + 1e+18, 1e+19, 1e+20, 1e+21, 1e+22, k1e23, 1e+24, 1e+25, 1e+26, + 1e+27, 1e+28, 1e+29, 1e+30, 1e+31, 1e+32, 1e+33, 1e+34, 1e+35, + 1e+36, 1e+37, 1e+38, 1e+39, 1e+40, 1e+41, 1e+42, 1e+43, 1e+44, + 1e+45, 1e+46, 1e+47, 1e+48, 1e+49, 1e+50, 1e+51, 1e+52, 1e+53, + 1e+54, 1e+55, 1e+56, 1e+57, 1e+58, 1e+59, 1e+60, 1e+61, 1e+62, + 1e+63, 1e+64, 1e+65, 1e+66, 1e+67, 1e+68, 1e+69, 1e+70, 1e+71, + 1e+72, 1e+73, 1e+74, 1e+75, 1e+76, 1e+77, 1e+78, 1e+79, 1e+80, + 1e+81, 1e+82, 1e+83, 1e+84, 1e+85, 1e+86, 1e+87, 1e+88, 1e+89, + 1e+90, 1e+91, 1e+92, 1e+93, 1e+94, 1e+95, 1e+96, 1e+97, 1e+98, + 1e+99, 1e+100, 1e+101, 1e+102, 1e+103, 1e+104, 1e+105, 1e+106, 1e+107, + 1e+108, 1e+109, 1e+110, 1e+111, 1e+112, 1e+113, 1e+114, 1e+115, 1e+116, + 1e+117, 1e+118, 1e+119, 1e+120, 1e+121, 1e+122, 1e+123, 1e+124, 1e+125, + 1e+126, 1e+127, 1e+128, 1e+129, 1e+130, 1e+131, 1e+132, 1e+133, 1e+134, + 1e+135, 1e+136, 1e+137, 1e+138, 1e+139, 1e+140, 1e+141, 1e+142, 1e+143, + 1e+144, 1e+145, 1e+146, 1e+147, 1e+148, 1e+149, 1e+150, 1e+151, 1e+152, + 1e+153, 1e+154, 1e+155, 1e+156, 1e+157, 1e+158, 1e+159, 1e+160, 1e+161, + 1e+162, 1e+163, 1e+164, 1e+165, 1e+166, 1e+167, 1e+168, 1e+169, 1e+170, + 1e+171, 1e+172, 1e+173, 1e+174, 1e+175, 1e+176, 1e+177, 1e+178, 1e+179, + 1e+180, 1e+181, 1e+182, 1e+183, 1e+184, 1e+185, 1e+186, 1e+187, 1e+188, + 1e+189, 1e+190, 1e+191, 1e+192, 1e+193, 1e+194, 1e+195, 1e+196, 1e+197, + 1e+198, 1e+199, 1e+200, 1e+201, 1e+202, 1e+203, 1e+204, 1e+205, 1e+206, + 1e+207, 1e+208, 1e+209, 1e+210, 1e+211, 1e+212, 1e+213, 1e+214, 1e+215, + 1e+216, 1e+217, 1e+218, 1e+219, 1e+220, 1e+221, 1e+222, 1e+223, 1e+224, + 1e+225, 1e+226, 1e+227, 1e+228, 1e+229, 1e+230, 1e+231, 1e+232, 1e+233, + 1e+234, 1e+235, 1e+236, 1e+237, 1e+238, 1e+239, 1e+240, 1e+241, 1e+242, + 1e+243, 1e+244, 1e+245, 1e+246, 1e+247, 1e+248, 1e+249, 1e+250, 1e+251, + 1e+252, 1e+253, 1e+254, 1e+255, 1e+256, 1e+257, 1e+258, 1e+259, 1e+260, + 1e+261, 1e+262, 1e+263, 1e+264, 1e+265, 1e+266, 1e+267, 1e+268, 1e+269, + 1e+270, 1e+271, 1e+272, 1e+273, 1e+274, 1e+275, 1e+276, 1e+277, 1e+278, + 1e+279, 1e+280, 1e+281, 1e+282, 1e+283, 1e+284, 1e+285, 1e+286, 1e+287, + 1e+288, 1e+289, 1e+290, 1e+291, 1e+292, 1e+293, 1e+294, 1e+295, 1e+296, + 1e+297, 1e+298, 1e+299, 1e+300, 1e+301, 1e+302, 1e+303, 1e+304, 1e+305, + 1e+306, 1e+307, 1e+308, +}; + +} // namespace + +double Pow10(int exp) { + if (exp < -324) { + return 0.0; + } else if (exp > 308) { + return INFINITY; + } else { + return kPowersOfTen[exp + 324]; + } +} + +} // namespace strings_internal +} // namespace absl diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/pow10_helper.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/pow10_helper.h new file mode 100644 index 00000000000..fe7e735a30b --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/pow10_helper.h @@ -0,0 +1,36 @@ +// +// 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. +// +// This test helper library contains a table of powers of 10, to guarantee +// precise values are computed across the full range of doubles. We can't rely +// on the pow() function, because not all standard libraries ship a version +// that is precise. +#ifndef ABSL_STRINGS_INTERNAL_POW10_HELPER_H_ +#define ABSL_STRINGS_INTERNAL_POW10_HELPER_H_ + +#include <vector> + +namespace absl { +namespace strings_internal { + +// Computes the precise value of 10^exp. (I.e. the nearest representable +// double to the exact value, rounding to nearest-even in the (single) case of +// being exactly halfway between.) +double Pow10(int exp); + +} // namespace strings_internal +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_POW10_HELPER_H_ diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/pow10_helper_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/pow10_helper_test.cc new file mode 100644 index 00000000000..9a13d5240da --- /dev/null +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/pow10_helper_test.cc @@ -0,0 +1,120 @@ +// 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/strings/internal/pow10_helper.h" + +#include <cmath> + +#include "gtest/gtest.h" +#include "absl/strings/str_format.h" + +namespace absl { +namespace strings_internal { + +namespace { + +struct TestCase { + int power; // Testing Pow10(power) + uint64_t significand; // Raw bits of the expected value + int radix; // significand is adjusted by 2^radix +}; + +TEST(Pow10HelperTest, Works) { + // The logic in pow10_helper.cc is so simple that theoretically we don't even + // need a test. However, we're paranoid and believe that there may be + // compilers that don't round floating-point literals correctly, even though + // it is specified by the standard. We check various edge cases, just to be + // sure. + constexpr TestCase kTestCases[] = { + // Subnormals + {-323, 0x2, -1074}, + {-322, 0x14, -1074}, + {-321, 0xca, -1074}, + {-320, 0x7e8, -1074}, + {-319, 0x4f10, -1074}, + {-318, 0x316a2, -1074}, + {-317, 0x1ee257, -1074}, + {-316, 0x134d761, -1074}, + {-315, 0xc1069cd, -1074}, + {-314, 0x78a42205, -1074}, + {-313, 0x4b6695433, -1074}, + {-312, 0x2f201d49fb, -1074}, + {-311, 0x1d74124e3d1, -1074}, + {-310, 0x12688b70e62b, -1074}, + {-309, 0xb8157268fdaf, -1074}, + {-308, 0x730d67819e8d2, -1074}, + // Values that are very close to rounding the other way. + // Comment shows difference of significand from the true value. + {-307, 0x11fa182c40c60d, -1072}, // -.4588 + {-290, 0x18f2b061aea072, -1016}, // .4854 + {-276, 0x11BA03F5B21000, -969}, // .4709 + {-259, 0x1899C2F6732210, -913}, // .4830 + {-252, 0x1D53844EE47DD1, -890}, // -.4743 + {-227, 0x1E5297287C2F45, -807}, // -.4708 + {-198, 0x1322E220A5B17E, -710}, // -.4714 + {-195, 0x12B010D3E1CF56, -700}, // .4928 + {-192, 0x123FF06EEA847A, -690}, // .4968 + {-163, 0x1708D0F84D3DE7, -594}, // -.4977 + {-145, 0x13FAAC3E3FA1F3, -534}, // -.4785 + {-111, 0x133D4032C2C7F5, -421}, // .4774 + {-106, 0x1D5B561574765B, -405}, // -.4869 + {-104, 0x16EF5B40C2FC77, -398}, // -.4741 + {-88, 0x197683DF2F268D, -345}, // -.4738 + {-86, 0x13E497065CD61F, -338}, // .4736 + {-76, 0x17288E1271F513, -305}, // -.4761 + {-63, 0x1A53FC9631D10D, -262}, // .4929 + {-30, 0x14484BFEEBC2A0, -152}, // .4758 + {-21, 0x12E3B40A0E9B4F, -122}, // -.4916 + {-5, 0x14F8B588E368F1, -69}, // .4829 + {23, 0x152D02C7E14AF6, 24}, // -.5000 (exactly, round-to-even) + {29, 0x1431E0FAE6D721, 44}, // -.4870 + {34, 0x1ED09BEAD87C03, 60}, // -.4721 + {70, 0x172EBAD6DDC73D, 180}, // .4733 + {105, 0x1BE7ABD3781ECA, 296}, // -.4850 + {126, 0x17A2ECC414A03F, 366}, // -.4999 + {130, 0x1CDA62055B2D9E, 379}, // .4855 + {165, 0x115D847AD00087, 496}, // -.4913 + {172, 0x14B378469B6732, 519}, // .4818 + {187, 0x1262DFEEBBB0F9, 569}, // -.4805 + {210, 0x18557F31326BBB, 645}, // -.4992 + {212, 0x1302CB5E6F642A, 652}, // -.4838 + {215, 0x1290BA9A38C7D1, 662}, // -.4881 + {236, 0x1F736F9B3494E9, 731}, // .4707 + {244, 0x176EC98994F489, 758}, // .4924 + {250, 0x1658E3AB795204, 778}, // -.4963 + {252, 0x117571DDF6C814, 785}, // .4873 + {254, 0x1B4781EAD1989E, 791}, // -.4887 + {260, 0x1A03FDE214CAF1, 811}, // .4784 + {284, 0x1585041B2C477F, 891}, // .4798 + {304, 0x1D2A1BE4048F90, 957}, // -.4987 + // Out-of-range values + {-324, 0x0, 0}, + {-325, 0x0, 0}, + {-326, 0x0, 0}, + {309, 1, 2000}, + {310, 1, 2000}, + {311, 1, 2000}, + }; + for (const TestCase& test_case : kTestCases) { + EXPECT_EQ(Pow10(test_case.power), + std::ldexp(test_case.significand, test_case.radix)) + << absl::StrFormat("Failure for Pow10(%d): %a vs %a", test_case.power, + Pow10(test_case.power), + std::ldexp(test_case.significand, test_case.radix)); + } +} + +} // namespace +} // namespace strings_internal +} // namespace absl diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/resize_uninitialized.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/resize_uninitialized.h index a94e0547b50..c2da0da9e4a 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/resize_uninitialized.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/resize_uninitialized.h @@ -18,6 +18,7 @@ #define ABSL_STRINGS_INTERNAL_RESIZE_UNINITIALIZED_H_ #include <string> +#include <type_traits> #include <utility> #include "absl/base/port.h" @@ -27,22 +28,24 @@ namespace absl { namespace strings_internal { // Is a subclass of true_type or false_type, depending on whether or not -// T has a resize_uninitialized member. -template <typename T, typename = void> -struct HasResizeUninitialized : std::false_type {}; -template <typename T> -struct HasResizeUninitialized< - T, absl::void_t<decltype(std::declval<T>().resize_uninitialized(237))>> - : std::true_type {}; +// T has a __resize_default_init member. +template <typename string_type, typename = void> +struct ResizeUninitializedTraits { + using HasMember = std::false_type; + static void Resize(string_type* s, size_t new_size) { s->resize(new_size); } +}; +// __resize_default_init is provided by libc++ >= 8.0 and by Google's internal +// ::string implementation. template <typename string_type> -void ResizeUninit(string_type* s, size_t new_size, std::true_type) { - s->resize_uninitialized(new_size); -} -template <typename string_type> -void ResizeUninit(string_type* s, size_t new_size, std::false_type) { - s->resize(new_size); -} +struct ResizeUninitializedTraits< + string_type, absl::void_t<decltype(std::declval<string_type&>() + .__resize_default_init(237))> > { + using HasMember = std::true_type; + static void Resize(string_type* s, size_t new_size) { + s->__resize_default_init(new_size); + } +}; // Returns true if the string implementation supports a resize where // the new characters added to the string are left untouched. @@ -51,7 +54,7 @@ void ResizeUninit(string_type* s, size_t new_size, std::false_type) { // the previous function.) template <typename string_type> inline constexpr bool STLStringSupportsNontrashingResize(string_type*) { - return HasResizeUninitialized<string_type>(); + return ResizeUninitializedTraits<string_type>::HasMember::value; } // Like str->resize(new_size), except any new characters added to "*str" as a @@ -60,7 +63,7 @@ inline constexpr bool STLStringSupportsNontrashingResize(string_type*) { // store of the string with known data. Uses a Google extension to ::string. template <typename string_type, typename = void> inline void STLStringResizeUninitialized(string_type* s, size_t new_size) { - ResizeUninit(s, new_size, HasResizeUninitialized<string_type>()); + ResizeUninitializedTraits<string_type>::Resize(s, new_size); } } // namespace strings_internal diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/resize_uninitialized_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/resize_uninitialized_test.cc index ad282efcd9b..43aece8db10 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/resize_uninitialized_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/resize_uninitialized_test.cc @@ -24,44 +24,44 @@ struct resizable_string { void resize(size_t) { resize_call_count += 1; } }; -int resize_uninitialized_call_count = 0; +int resize_default_init_call_count = 0; -struct resize_uninitializable_string { +struct resize_default_init_string { void resize(size_t) { resize_call_count += 1; } - void resize_uninitialized(size_t) { resize_uninitialized_call_count += 1; } + void __resize_default_init(size_t) { resize_default_init_call_count += 1; } }; TEST(ResizeUninit, WithAndWithout) { resize_call_count = 0; - resize_uninitialized_call_count = 0; + resize_default_init_call_count = 0; { resizable_string rs; EXPECT_EQ(resize_call_count, 0); - EXPECT_EQ(resize_uninitialized_call_count, 0); + EXPECT_EQ(resize_default_init_call_count, 0); EXPECT_FALSE( absl::strings_internal::STLStringSupportsNontrashingResize(&rs)); EXPECT_EQ(resize_call_count, 0); - EXPECT_EQ(resize_uninitialized_call_count, 0); + EXPECT_EQ(resize_default_init_call_count, 0); absl::strings_internal::STLStringResizeUninitialized(&rs, 237); EXPECT_EQ(resize_call_count, 1); - EXPECT_EQ(resize_uninitialized_call_count, 0); + EXPECT_EQ(resize_default_init_call_count, 0); } resize_call_count = 0; - resize_uninitialized_call_count = 0; + resize_default_init_call_count = 0; { - resize_uninitializable_string rus; + resize_default_init_string rus; EXPECT_EQ(resize_call_count, 0); - EXPECT_EQ(resize_uninitialized_call_count, 0); + EXPECT_EQ(resize_default_init_call_count, 0); EXPECT_TRUE( absl::strings_internal::STLStringSupportsNontrashingResize(&rus)); EXPECT_EQ(resize_call_count, 0); - EXPECT_EQ(resize_uninitialized_call_count, 0); + EXPECT_EQ(resize_default_init_call_count, 0); absl::strings_internal::STLStringResizeUninitialized(&rus, 237); EXPECT_EQ(resize_call_count, 0); - EXPECT_EQ(resize_uninitialized_call_count, 1); + EXPECT_EQ(resize_default_init_call_count, 1); } } diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/str_format/arg.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/str_format/arg.h index ec9e6f0063b..ebd40adcd98 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/str_format/arg.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/internal/str_format/arg.h @@ -80,7 +80,7 @@ ConvertResult<Conv::s> FormatConvertImpl(const AbslCord& value, int precision = conv.precision(); if (precision >= 0) - to_write = std::min(to_write, static_cast<size_t>(precision)); + to_write = (std::min)(to_write, static_cast<size_t>(precision)); space_remaining = Excess(to_write, space_remaining); diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/match.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/match.cc index 3d10c57784e..a2e9064c076 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/match.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/match.cc @@ -18,15 +18,6 @@ namespace absl { -namespace { -bool CaseEqual(absl::string_view piece1, absl::string_view piece2) { - return (piece1.size() == piece2.size() && - 0 == strings_internal::memcasecmp(piece1.data(), piece2.data(), - piece1.size())); - // memcasecmp uses ascii_tolower(). -} -} // namespace - bool EqualsIgnoreCase(absl::string_view piece1, absl::string_view piece2) { return (piece1.size() == piece2.size() && 0 == absl::strings_internal::memcasecmp(piece1.data(), piece2.data(), @@ -36,12 +27,12 @@ bool EqualsIgnoreCase(absl::string_view piece1, absl::string_view piece2) { bool StartsWithIgnoreCase(absl::string_view text, absl::string_view prefix) { return (text.size() >= prefix.size()) && - CaseEqual(text.substr(0, prefix.size()), prefix); + EqualsIgnoreCase(text.substr(0, prefix.size()), prefix); } bool EndsWithIgnoreCase(absl::string_view text, absl::string_view suffix) { return (text.size() >= suffix.size()) && - CaseEqual(text.substr(text.size() - suffix.size()), suffix); + EqualsIgnoreCase(text.substr(text.size() - suffix.size()), suffix); } } // namespace absl diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/numbers_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/numbers_test.cc index 36fc0d64fd5..099326c270a 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/numbers_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/numbers_test.cc @@ -39,6 +39,7 @@ #include "absl/strings/str_cat.h" #include "absl/strings/internal/numbers_test_common.h" +#include "absl/strings/internal/pow10_helper.h" namespace { @@ -871,7 +872,7 @@ TEST_F(SimpleDtoaTest, ExhaustiveDoubleToSixDigits) { } for (int exponent = -324; exponent <= 308; ++exponent) { - double powten = pow(10.0, exponent); + double powten = absl::strings_internal::Pow10(exponent); if (powten == 0) powten = 5e-324; if (kFloatNumCases >= 1e9) { // The exhaustive test takes a very long time, so log progress. diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/str_cat.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/str_cat.h index da9ed9a269e..8ba0592fdaa 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/str_cat.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/str_cat.h @@ -97,6 +97,10 @@ enum PadSpec : uint8_t { kZeroPad14, kZeroPad15, kZeroPad16, + kZeroPad17, + kZeroPad18, + kZeroPad19, + kZeroPad20, kSpacePad2 = kZeroPad2 + 64, kSpacePad3, @@ -113,6 +117,10 @@ enum PadSpec : uint8_t { kSpacePad14, kSpacePad15, kSpacePad16, + kSpacePad17, + kSpacePad18, + kSpacePad19, + kSpacePad20, }; // ----------------------------------------------------------------------------- diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/str_cat_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/str_cat_test.cc index 555d8db3eb8..0714107267a 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/str_cat_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/str_cat_test.cc @@ -427,7 +427,7 @@ void CheckHex(IntType v, const char* nopad_format, const char* zeropad_format, snprintf(expected, sizeof(expected), nopad_format, v); EXPECT_EQ(expected, actual) << " decimal value " << v; - for (int spec = absl::kZeroPad2; spec <= absl::kZeroPad16; ++spec) { + for (int spec = absl::kZeroPad2; spec <= absl::kZeroPad20; ++spec) { std::string actual = absl::StrCat(absl::Hex(v, static_cast<absl::PadSpec>(spec))); snprintf(expected, sizeof(expected), zeropad_format, @@ -435,7 +435,7 @@ void CheckHex(IntType v, const char* nopad_format, const char* zeropad_format, EXPECT_EQ(expected, actual) << " decimal value " << v; } - for (int spec = absl::kSpacePad2; spec <= absl::kSpacePad16; ++spec) { + for (int spec = absl::kSpacePad2; spec <= absl::kSpacePad20; ++spec) { std::string actual = absl::StrCat(absl::Hex(v, static_cast<absl::PadSpec>(spec))); snprintf(expected, sizeof(expected), spacepad_format, @@ -453,7 +453,7 @@ void CheckDec(IntType v, const char* nopad_format, const char* zeropad_format, snprintf(expected, sizeof(expected), nopad_format, v); EXPECT_EQ(expected, actual) << " decimal value " << v; - for (int spec = absl::kZeroPad2; spec <= absl::kZeroPad16; ++spec) { + for (int spec = absl::kZeroPad2; spec <= absl::kZeroPad20; ++spec) { std::string actual = absl::StrCat(absl::Dec(v, static_cast<absl::PadSpec>(spec))); snprintf(expected, sizeof(expected), zeropad_format, @@ -463,7 +463,7 @@ void CheckDec(IntType v, const char* nopad_format, const char* zeropad_format, << "' digits " << (spec - absl::kZeroPad2 + 2); } - for (int spec = absl::kSpacePad2; spec <= absl::kSpacePad16; ++spec) { + for (int spec = absl::kSpacePad2; spec <= absl::kSpacePad20; ++spec) { std::string actual = absl::StrCat(absl::Dec(v, static_cast<absl::PadSpec>(spec))); snprintf(expected, sizeof(expected), spacepad_format, diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/string_view.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/string_view.h index 2cc10f522e1..8cd4fa24e2b 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/string_view.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/strings/string_view.h @@ -355,7 +355,7 @@ class string_view { string_view substr(size_type pos, size_type n = npos) const { if (ABSL_PREDICT_FALSE(pos > length_)) base_internal::ThrowStdOutOfRange("absl::string_view::substr"); - n = std::min(n, length_ - pos); + n = (std::min)(n, length_ - pos); return string_view(ptr_ + pos, n); } @@ -368,7 +368,7 @@ class string_view { // on the respective sizes of the two `string_view`s to determine which is // smaller, equal, or greater. int compare(string_view x) const noexcept { - auto min_length = std::min(length_, x.length_); + auto min_length = (std::min)(length_, x.length_); if (min_length > 0) { int r = memcmp(ptr_, x.ptr_, min_length); if (r < 0) return -1; @@ -517,7 +517,7 @@ inline bool operator!=(string_view x, string_view y) noexcept { } inline bool operator<(string_view x, string_view y) noexcept { - auto min_size = std::min(x.size(), y.size()); + auto min_size = (std::min)(x.size(), y.size()); const int r = min_size == 0 ? 0 : memcmp(x.data(), y.data(), min_size); return (r < 0) || (r == 0 && x.size() < y.size()); } @@ -547,7 +547,7 @@ namespace absl { // Provided because std::string_view::substr throws if `pos > size()` inline string_view ClippedSubstr(string_view s, size_t pos, size_t n = string_view::npos) { - pos = std::min(pos, static_cast<size_t>(s.size())); + pos = (std::min)(pos, static_cast<size_t>(s.size())); return s.substr(pos, n); } diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/BUILD.bazel index f52e9d41644..53e7988457e 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/BUILD.bazel @@ -15,7 +15,7 @@ # load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", ) @@ -170,18 +170,31 @@ cc_test( ], ) -cc_test( - name = "mutex_benchmark", +cc_library( + name = "mutex_benchmark_common", + testonly = 1, srcs = ["mutex_benchmark.cc"], - copts = ABSL_TEST_COPTS, - tags = ["benchmark"], - visibility = ["//visibility:private"], + copts = ABSL_DEFAULT_COPTS, + visibility = [ + "//absl/synchronization:__pkg__", + ], deps = [ ":synchronization", ":thread_pool", "//absl/base", "@com_github_google_benchmark//:benchmark_main", ], + alwayslink = 1, +) + +cc_binary( + name = "mutex_benchmark", + testonly = 1, + copts = ABSL_DEFAULT_COPTS, + visibility = ["//visibility:private"], + deps = [ + ":mutex_benchmark_common", + ], ) cc_test( diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/internal/kernel_timeout.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/internal/kernel_timeout.h index 76e7983ae06..9e1eed75d3a 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/internal/kernel_timeout.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/internal/kernel_timeout.h @@ -100,8 +100,8 @@ class KernelTimeout { if (n < 0) n = 0; struct timespec abstime; - int64_t seconds = std::min(n / kNanosPerSecond, - int64_t{(std::numeric_limits<time_t>::max)()}); + int64_t seconds = (std::min)(n / kNanosPerSecond, + int64_t{(std::numeric_limits<time_t>::max)()}); abstime.tv_sec = static_cast<time_t>(seconds); abstime.tv_nsec = static_cast<decltype(abstime.tv_nsec)>(n % kNanosPerSecond); diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/internal/mutex_nonprod.inc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/internal/mutex_nonprod.inc index 0aab3d1314e..b8d5af79ad3 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/internal/mutex_nonprod.inc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/internal/mutex_nonprod.inc @@ -214,6 +214,9 @@ class SynchronizationStorage { // stack) should use this constructor. explicit SynchronizationStorage(base_internal::LinkerInitialized) {} + constexpr explicit SynchronizationStorage(absl::ConstInitType) + : is_dynamic_(false), once_(), space_{{0}} {} + SynchronizationStorage(SynchronizationStorage&) = delete; SynchronizationStorage& operator=(SynchronizationStorage&) = delete; diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/lifetime_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/lifetime_test.cc index 90c9009b18f..8b168e21a31 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/lifetime_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/lifetime_test.cc @@ -17,6 +17,7 @@ #include <type_traits> #include "absl/base/attributes.h" +#include "absl/base/const_init.h" #include "absl/base/internal/raw_logging.h" #include "absl/base/thread_annotations.h" #include "absl/synchronization/mutex.h" @@ -72,23 +73,19 @@ void ThreadTwo(absl::Mutex* mutex, absl::CondVar* condvar, // Launch thread 1 and thread 2, and block on their completion. // If any of 'mutex', 'condvar', or 'notification' is nullptr, use a locally // constructed instance instead. -void RunTests(absl::Mutex* mutex, absl::CondVar* condvar, - absl::Notification* notification) { +void RunTests(absl::Mutex* mutex, absl::CondVar* condvar) { absl::Mutex default_mutex; absl::CondVar default_condvar; - absl::Notification default_notification; + absl::Notification notification; if (!mutex) { mutex = &default_mutex; } if (!condvar) { condvar = &default_condvar; } - if (!notification) { - notification = &default_notification; - } bool state = false; - std::thread thread_one(ThreadOne, mutex, condvar, notification, &state); - std::thread thread_two(ThreadTwo, mutex, condvar, notification, &state); + std::thread thread_one(ThreadOne, mutex, condvar, ¬ification, &state); + std::thread thread_two(ThreadTwo, mutex, condvar, ¬ification, &state); thread_one.join(); thread_two.join(); } @@ -96,10 +93,13 @@ void RunTests(absl::Mutex* mutex, absl::CondVar* condvar, void TestLocals() { absl::Mutex mutex; absl::CondVar condvar; - absl::Notification notification; - RunTests(&mutex, &condvar, ¬ification); + RunTests(&mutex, &condvar); } +// Normal kConstInit usage +ABSL_CONST_INIT absl::Mutex const_init_mutex(absl::kConstInit); +void TestConstInitGlobal() { RunTests(&const_init_mutex, nullptr); } + // Global variables during start and termination // // In a translation unit, static storage duration variables are initialized in @@ -122,10 +122,53 @@ class OnDestruction { Function fn_; }; +// kConstInit +// Test early usage. (Declaration comes first; definitions must appear after +// the test runner.) +extern absl::Mutex early_const_init_mutex; +// (Normally I'd write this +[], to make the cast-to-function-pointer explicit, +// but in some MSVC setups we support, lambdas provide conversion operators to +// different flavors of function pointers, making this trick ambiguous.) +OnConstruction test_early_const_init([] { + RunTests(&early_const_init_mutex, nullptr); +}); +// This definition appears before test_early_const_init, but it should be +// initialized first (due to constant initialization). Test that the object +// actually works when constructed this way. +ABSL_CONST_INIT absl::Mutex early_const_init_mutex(absl::kConstInit); + +// Furthermore, test that the const-init c'tor doesn't stomp over the state of +// a Mutex. Really, this is a test that the platform under test correctly +// supports C++11 constant initialization. (The constant-initialization +// constructors of globals "happen at link time"; memory is pre-initialized, +// before the constructors of either grab_lock or check_still_locked are run.) +extern absl::Mutex const_init_sanity_mutex; +OnConstruction grab_lock([]() NO_THREAD_SAFETY_ANALYSIS { + const_init_sanity_mutex.Lock(); +}); +ABSL_CONST_INIT absl::Mutex const_init_sanity_mutex(absl::kConstInit); +OnConstruction check_still_locked([]() NO_THREAD_SAFETY_ANALYSIS { + const_init_sanity_mutex.AssertHeld(); + const_init_sanity_mutex.Unlock(); +}); + +// Test shutdown usage. (Declarations come first; definitions must appear after +// the test runner.) +extern absl::Mutex late_const_init_mutex; +// OnDestruction is being used here as a global variable, even though it has a +// non-trivial destructor. This is against the style guide. We're violating +// that rule here to check that the exception we allow for kConstInit is safe. +// NOLINTNEXTLINE +OnDestruction test_late_const_init([] { + RunTests(&late_const_init_mutex, nullptr); +}); +ABSL_CONST_INIT absl::Mutex late_const_init_mutex(absl::kConstInit); + } // namespace int main() { TestLocals(); + TestConstInitGlobal(); // Explicitly call exit(0) here, to make it clear that we intend for the // above global object destructors to run. std::exit(0); diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex.cc index 81219798121..f1b42db15f9 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex.cc @@ -1079,7 +1079,7 @@ void Mutex::TryRemove(PerThreadSynch *s) { // if the wait extends past the absolute time specified, even if "s" is still // on the mutex queue. In this case, remove "s" from the queue and return // true, otherwise return false. -void Mutex::Block(PerThreadSynch *s) { +ABSL_XRAY_LOG_ARGS(1) void Mutex::Block(PerThreadSynch *s) { while (s->state.load(std::memory_order_acquire) == PerThreadSynch::kQueued) { if (!DecrementSynchSem(this, s, s->waitp->timeout)) { // After a timeout, we go into a spin loop until we remove ourselves diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex.h index aeef3c95978..4b65e92cb3d 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex.h @@ -61,6 +61,7 @@ #include <cstdint> #include <string> +#include "absl/base/const_init.h" #include "absl/base/internal/identity.h" #include "absl/base/internal/low_level_alloc.h" #include "absl/base/internal/thread_identity.h" @@ -136,7 +137,26 @@ struct SynchWaitParams; class LOCKABLE Mutex { public: + // Creates a `Mutex` that is not held by anyone. This constructor is + // typically used for Mutexes allocated on the heap or the stack. + // + // To create `Mutex` instances with static storage duration + // (e.g. a namespace-scoped or global variable), see + // `Mutex::Mutex(absl::kConstInit)` below instead. Mutex(); + + // Creates a mutex with static storage duration. A global variable + // constructed this way avoids the lifetime issues that can occur on program + // startup and shutdown. (See absl/base/const_init.h.) + // + // For Mutexes allocated on the heap and stack, instead use the default + // constructor, which can interact more fully with the thread sanitizer. + // + // Example usage: + // namespace foo { + // ABSL_CONST_INIT Mutex mu(absl::kConstInit); + // } + explicit constexpr Mutex(absl::ConstInitType); ~Mutex(); // Mutex::Lock() @@ -879,10 +899,12 @@ class SCOPED_LOCKABLE ReleasableMutexLock { }; #ifdef ABSL_INTERNAL_USE_NONPROD_MUTEX +inline constexpr Mutex::Mutex(absl::ConstInitType) : impl_(absl::kConstInit) {} #else inline Mutex::Mutex() : mu_(0) { ABSL_TSAN_MUTEX_CREATE(this, __tsan_mutex_not_static); } +inline constexpr Mutex::Mutex(absl::ConstInitType) : mu_(0) {} inline CondVar::CondVar() : cv_(0) {} #endif diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex_benchmark.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex_benchmark.cc index 1e019e001ae..2652bb974e9 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex_benchmark.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/mutex_benchmark.cc @@ -12,16 +12,154 @@ // See the License for the specific language governing permissions and // limitations under the License. +#include <cstdint> +#include <mutex> // NOLINT(build/c++11) #include <vector> -#include "benchmark/benchmark.h" -#include "absl/base/internal/sysinfo.h" +#include "absl/base/internal/cycleclock.h" +#include "absl/base/internal/spinlock.h" #include "absl/synchronization/blocking_counter.h" #include "absl/synchronization/internal/thread_pool.h" #include "absl/synchronization/mutex.h" +#include "benchmark/benchmark.h" namespace { +void BM_Mutex(benchmark::State& state) { + static absl::Mutex* mu = new absl::Mutex; + for (auto _ : state) { + absl::MutexLock lock(mu); + } +} +BENCHMARK(BM_Mutex)->UseRealTime()->Threads(1)->ThreadPerCpu(); + +static void DelayNs(int64_t ns, int* data) { + int64_t end = absl::base_internal::CycleClock::Now() + + ns * absl::base_internal::CycleClock::Frequency() / 1e9; + while (absl::base_internal::CycleClock::Now() < end) { + ++(*data); + benchmark::DoNotOptimize(*data); + } +} + +template <typename MutexType> +class RaiiLocker { + public: + explicit RaiiLocker(MutexType* mu) : mu_(mu) { mu_->Lock(); } + ~RaiiLocker() { mu_->Unlock(); } + private: + MutexType* mu_; +}; + +template <> +class RaiiLocker<std::mutex> { + public: + explicit RaiiLocker(std::mutex* mu) : mu_(mu) { mu_->lock(); } + ~RaiiLocker() { mu_->unlock(); } + private: + std::mutex* mu_; +}; + +template <typename MutexType> +void BM_Contended(benchmark::State& state) { + struct Shared { + MutexType mu; + int data = 0; + }; + static auto* shared = new Shared; + int local = 0; + for (auto _ : state) { + // Here we model both local work outside of the critical section as well as + // some work inside of the critical section. The idea is to capture some + // more or less realisitic contention levels. + // If contention is too low, the benchmark won't measure anything useful. + // If contention is unrealistically high, the benchmark will favor + // bad mutex implementations that block and otherwise distract threads + // from the mutex and shared state for as much as possible. + // To achieve this amount of local work is multiplied by number of threads + // to keep ratio between local work and critical section approximately + // equal regardless of number of threads. + DelayNs(100 * state.threads, &local); + RaiiLocker<MutexType> locker(&shared->mu); + DelayNs(state.range(0), &shared->data); + } +} + +BENCHMARK_TEMPLATE(BM_Contended, absl::Mutex) + ->UseRealTime() + // ThreadPerCpu poorly handles non-power-of-two CPU counts. + ->Threads(1) + ->Threads(2) + ->Threads(4) + ->Threads(6) + ->Threads(8) + ->Threads(12) + ->Threads(16) + ->Threads(24) + ->Threads(32) + ->Threads(48) + ->Threads(64) + ->Threads(96) + ->Threads(128) + ->Threads(192) + ->Threads(256) + // Some empirically chosen amounts of work in critical section. + // 1 is low contention, 200 is high contention and few values in between. + ->Arg(1) + ->Arg(20) + ->Arg(50) + ->Arg(200); + +BENCHMARK_TEMPLATE(BM_Contended, absl::base_internal::SpinLock) + ->UseRealTime() + // ThreadPerCpu poorly handles non-power-of-two CPU counts. + ->Threads(1) + ->Threads(2) + ->Threads(4) + ->Threads(6) + ->Threads(8) + ->Threads(12) + ->Threads(16) + ->Threads(24) + ->Threads(32) + ->Threads(48) + ->Threads(64) + ->Threads(96) + ->Threads(128) + ->Threads(192) + ->Threads(256) + // Some empirically chosen amounts of work in critical section. + // 1 is low contention, 200 is high contention and few values in between. + ->Arg(1) + ->Arg(20) + ->Arg(50) + ->Arg(200); + +BENCHMARK_TEMPLATE(BM_Contended, std::mutex) + ->UseRealTime() + // ThreadPerCpu poorly handles non-power-of-two CPU counts. + ->Threads(1) + ->Threads(2) + ->Threads(4) + ->Threads(6) + ->Threads(8) + ->Threads(12) + ->Threads(16) + ->Threads(24) + ->Threads(32) + ->Threads(48) + ->Threads(64) + ->Threads(96) + ->Threads(128) + ->Threads(192) + ->Threads(256) + // Some empirically chosen amounts of work in critical section. + // 1 is low contention, 200 is high contention and few values in between. + ->Arg(1) + ->Arg(20) + ->Arg(50) + ->Arg(200); + // Measure the overhead of conditions on mutex release (when they must be // evaluated). Mutex has (some) support for equivalence classes allowing // Conditions with the same function/argument to potentially not be multiply @@ -82,13 +220,4 @@ constexpr int kMaxConditionWaiters = 1024; #endif BENCHMARK(BM_ConditionWaiters)->RangePair(0, 2, 1, kMaxConditionWaiters); -void BM_ContendedMutex(benchmark::State& state) { - static absl::Mutex* mu = new absl::Mutex; - for (auto _ : state) { - absl::MutexLock lock(mu); - } -} -BENCHMARK(BM_ContendedMutex)->Threads(1); -BENCHMARK(BM_ContendedMutex)->ThreadPerCpu(); - } // namespace diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/notification.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/notification.cc index ed8cc906774..cdcbc134fa6 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/notification.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/notification.cc @@ -22,6 +22,7 @@ #include "absl/time/time.h" namespace absl { + void Notification::Notify() { MutexLock l(&this->mutex_); diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/notification.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/notification.h index 107932f2909..f95f4d142a0 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/notification.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/synchronization/notification.h @@ -52,6 +52,7 @@ #include <atomic> +#include "absl/base/macros.h" #include "absl/synchronization/mutex.h" #include "absl/time/time.h" diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/BUILD.bazel index 969ddd2e6ac..2082f52c17a 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/BUILD.bazel @@ -15,7 +15,7 @@ # load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", ) @@ -110,6 +110,7 @@ cc_test( ":test_util", ":time", "//absl/base", + "//absl/hash", "@com_github_google_benchmark//:benchmark_main", ], ) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/civil_time_benchmark.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/civil_time_benchmark.cc index 567c2a33b12..f30f636dccc 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/civil_time_benchmark.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/civil_time_benchmark.cc @@ -14,17 +14,29 @@ #include "absl/time/civil_time.h" +#include <numeric> +#include <vector> + +#include "absl/hash/hash.h" #include "benchmark/benchmark.h" namespace { -// Benchmark Time(ns) CPU(ns) Iterations -// ------------------------------------------------------------------------- -// BM_Difference_Days 20 20 34542508 -// BM_Step_Days 15 15 48098146 -// BM_Format 688 687 1019803 -// BM_Parse 921 920 762788 -// BM_RoundTripFormatParse 1766 1764 396092 +// Run on (12 X 3492 MHz CPUs); 2018-11-05T13:44:29.814239103-08:00 +// CPU: Intel Haswell with HyperThreading (6 cores) dL1:32KB dL2:256KB dL3:15MB +// Benchmark Time(ns) CPU(ns) Iterations +// ---------------------------------------------------------------- +// BM_Difference_Days 14.5 14.5 48531105 +// BM_Step_Days 12.6 12.6 54876006 +// BM_Format 587 587 1000000 +// BM_Parse 692 692 1000000 +// BM_RoundTripFormatParse 1309 1309 532075 +// BM_CivilYearAbslHash 0.710 0.710 976400000 +// BM_CivilMonthAbslHash 1.13 1.13 619500000 +// BM_CivilDayAbslHash 1.70 1.70 426000000 +// BM_CivilHourAbslHash 2.45 2.45 287600000 +// BM_CivilMinuteAbslHash 3.21 3.21 226200000 +// BM_CivilSecondAbslHash 4.10 4.10 171800000 void BM_Difference_Days(benchmark::State& state) { const absl::CivilDay c(2014, 8, 22); @@ -54,4 +66,42 @@ void BM_Format(benchmark::State& state) { } BENCHMARK(BM_Format); +template <typename T> +void BM_CivilTimeAbslHash(benchmark::State& state) { + const int kSize = 100000; + std::vector<T> civil_times(kSize); + std::iota(civil_times.begin(), civil_times.end(), T(2018)); + + absl::Hash<T> absl_hasher; + while (state.KeepRunningBatch(kSize)) { + for (const T civil_time : civil_times) { + benchmark::DoNotOptimize(absl_hasher(civil_time)); + } + } +} +void BM_CivilYearAbslHash(benchmark::State& state) { + BM_CivilTimeAbslHash<absl::CivilYear>(state); +} +void BM_CivilMonthAbslHash(benchmark::State& state) { + BM_CivilTimeAbslHash<absl::CivilMonth>(state); +} +void BM_CivilDayAbslHash(benchmark::State& state) { + BM_CivilTimeAbslHash<absl::CivilDay>(state); +} +void BM_CivilHourAbslHash(benchmark::State& state) { + BM_CivilTimeAbslHash<absl::CivilHour>(state); +} +void BM_CivilMinuteAbslHash(benchmark::State& state) { + BM_CivilTimeAbslHash<absl::CivilMinute>(state); +} +void BM_CivilSecondAbslHash(benchmark::State& state) { + BM_CivilTimeAbslHash<absl::CivilSecond>(state); +} +BENCHMARK(BM_CivilYearAbslHash); +BENCHMARK(BM_CivilMonthAbslHash); +BENCHMARK(BM_CivilDayAbslHash); +BENCHMARK(BM_CivilHourAbslHash); +BENCHMARK(BM_CivilMinuteAbslHash); +BENCHMARK(BM_CivilSecondAbslHash); + } // namespace diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/duration.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/duration.cc index 2950c7cdc63..b77d5ec9006 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/duration.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/duration.cc @@ -78,10 +78,16 @@ constexpr int64_t kint64min = std::numeric_limits<int64_t>::min(); // Can't use std::isinfinite() because it doesn't exist on windows. inline bool IsFinite(double d) { + if (std::isnan(d)) return false; return d != std::numeric_limits<double>::infinity() && d != -std::numeric_limits<double>::infinity(); } +inline bool IsValidDivisor(double d) { + if (std::isnan(d)) return false; + return d != 0.0; +} + // Can't use std::round() because it is only available in C++11. // Note that we ignore the possibility of floating-point over/underflow. template <typename Double> @@ -455,7 +461,7 @@ Duration& Duration::operator/=(int64_t r) { } Duration& Duration::operator/=(double r) { - if (time_internal::IsInfiniteDuration(*this) || r == 0.0) { + if (time_internal::IsInfiniteDuration(*this) || !IsValidDivisor(r)) { const bool is_neg = (std::signbit(r) != 0) != (rep_hi_ < 0); return *this = is_neg ? -InfiniteDuration() : InfiniteDuration(); } diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/duration_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/duration_test.cc index 7ae25dc68f9..61f3c5c07fa 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/duration_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/duration_test.cc @@ -56,6 +56,17 @@ MATCHER_P(TimevalMatcher, tv, "") { return false; } +TEST(Duration, ConstExpr) { + constexpr absl::Duration d0 = absl::ZeroDuration(); + static_assert(d0 == absl::ZeroDuration(), "ZeroDuration()"); + constexpr absl::Duration d1 = absl::Seconds(1); + static_assert(d1 == absl::Seconds(1), "Seconds(1)"); + static_assert(d1 != absl::ZeroDuration(), "Seconds(1)"); + constexpr absl::Duration d2 = absl::InfiniteDuration(); + static_assert(d2 == absl::InfiniteDuration(), "InfiniteDuration()"); + static_assert(d2 != absl::ZeroDuration(), "InfiniteDuration()"); +} + TEST(Duration, ValueSemantics) { // If this compiles, the test passes. constexpr absl::Duration a; // Default construction @@ -792,6 +803,40 @@ TEST(Duration, DivisionByZero) { EXPECT_EQ(-dbl_inf, absl::FDivDuration(-any_dur, zero)); } +TEST(Duration, NaN) { + // Note that IEEE 754 does not define the behavior of a nan's sign when it is + // copied, so the code below allows for either + or - InfiniteDuration. +#define TEST_NAN_HANDLING(NAME, NAN) \ + do { \ + const auto inf = absl::InfiniteDuration(); \ + auto x = NAME(NAN); \ + EXPECT_TRUE(x == inf || x == -inf); \ + auto y = NAME(42); \ + y *= NAN; \ + EXPECT_TRUE(y == inf || y == -inf); \ + auto z = NAME(42); \ + z /= NAN; \ + EXPECT_TRUE(z == inf || z == -inf); \ + } while (0) + + const double nan = std::numeric_limits<double>::quiet_NaN(); + TEST_NAN_HANDLING(absl::Nanoseconds, nan); + TEST_NAN_HANDLING(absl::Microseconds, nan); + TEST_NAN_HANDLING(absl::Milliseconds, nan); + TEST_NAN_HANDLING(absl::Seconds, nan); + TEST_NAN_HANDLING(absl::Minutes, nan); + TEST_NAN_HANDLING(absl::Hours, nan); + + TEST_NAN_HANDLING(absl::Nanoseconds, -nan); + TEST_NAN_HANDLING(absl::Microseconds, -nan); + TEST_NAN_HANDLING(absl::Milliseconds, -nan); + TEST_NAN_HANDLING(absl::Seconds, -nan); + TEST_NAN_HANDLING(absl::Minutes, -nan); + TEST_NAN_HANDLING(absl::Hours, -nan); + +#undef TEST_NAN_HANDLING +} + TEST(Duration, Range) { const absl::Duration range = ApproxYears(100 * 1e9); const absl::Duration range_future = range; diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/format_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/format_test.cc index 40f4c24633c..ac8d5ea303a 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/format_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/format_test.cc @@ -394,7 +394,12 @@ TEST(FormatParse, RoundTrip) { // work. On Windows, `absl::ParseTime()` falls back to std::get_time() which // appears to fail on "%c" (or at least on the "%c" text produced by // `strftime()`). This makes it fail the round-trip test. -#ifndef _MSC_VER + // + // Under the emscripten compiler `absl::ParseTime() falls back to + // `strptime()`, but that ends up using a different definition for "%c" + // compared to `strftime()`, also causing the round-trip test to fail + // (see https://github.com/kripken/emscripten/pull/7491). +#if !defined(_MSC_VER) && !defined(__EMSCRIPTEN__) // Even though we don't know what %c will produce, it should roundtrip, // but only in the 0-offset timezone. { @@ -403,7 +408,7 @@ TEST(FormatParse, RoundTrip) { EXPECT_TRUE(absl::ParseTime("%c", s, &out, &err)) << s << ": " << err; EXPECT_EQ(in, out); } -#endif // _MSC_VER +#endif // !_MSC_VER && !__EMSCRIPTEN__ } TEST(FormatParse, RoundTripDistantFuture) { diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/BUILD.bazel index e913fad33cc..e2cfe801f23 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/BUILD.bazel @@ -12,6 +12,8 @@ # See the License for the specific language governing permissions and # limitations under the License. +package(features = ["-parse_headers"]) + licenses(["notice"]) # Apache License ### libraries diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/include/cctz/civil_time_detail.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/include/cctz/civil_time_detail.h index d7f72717ece..1c5d0970827 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/include/cctz/civil_time_detail.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/include/cctz/civil_time_detail.h @@ -326,6 +326,37 @@ CONSTEXPR_F fields align(year_tag, fields f) noexcept { //////////////////////////////////////////////////////////////////////// +namespace impl { + +template <typename H> +H AbslHashValueImpl(second_tag, H h, fields f) { + return H::combine(std::move(h), f.y, f.m, f.d, f.hh, f.mm, f.ss); +} +template <typename H> +H AbslHashValueImpl(minute_tag, H h, fields f) { + return H::combine(std::move(h), f.y, f.m, f.d, f.hh, f.mm); +} +template <typename H> +H AbslHashValueImpl(hour_tag, H h, fields f) { + return H::combine(std::move(h), f.y, f.m, f.d, f.hh); +} +template <typename H> +H AbslHashValueImpl(day_tag, H h, fields f) { + return H::combine(std::move(h), f.y, f.m, f.d); +} +template <typename H> +H AbslHashValueImpl(month_tag, H h, fields f) { + return H::combine(std::move(h), f.y, f.m); +} +template <typename H> +H AbslHashValueImpl(year_tag, H h, fields f) { + return H::combine(std::move(h), f.y); +} + +} // namespace impl + +//////////////////////////////////////////////////////////////////////// + template <typename T> class civil_time { public: @@ -355,12 +386,12 @@ class civil_time { : civil_time(ct.f_) {} // Factories for the maximum/minimum representable civil_time. - static CONSTEXPR_F civil_time max() { - const auto max_year = std::numeric_limits<std::int_least64_t>::max(); + static CONSTEXPR_F civil_time (max)() { + const auto max_year = (std::numeric_limits<std::int_least64_t>::max)(); return civil_time(max_year, 12, 31, 23, 59, 59); } - static CONSTEXPR_F civil_time min() { - const auto min_year = std::numeric_limits<std::int_least64_t>::min(); + static CONSTEXPR_F civil_time (min)() { + const auto min_year = (std::numeric_limits<std::int_least64_t>::min)(); return civil_time(min_year, 1, 1, 0, 0, 0); } @@ -378,7 +409,7 @@ class civil_time { return *this; } CONSTEXPR_M civil_time& operator-=(diff_t n) noexcept { - if (n != std::numeric_limits<diff_t>::min()) { + if (n != (std::numeric_limits<diff_t>::min)()) { f_ = step(T{}, f_, -n); } else { f_ = step(T{}, step(T{}, f_, -(n + 1)), 1); @@ -418,8 +449,7 @@ class civil_time { template <typename H> friend H AbslHashValue(H h, civil_time a) { - return H::combine(std::move(h), a.f_.y, a.f_.m, a.f_.d, - a.f_.hh, a.f_.mm, a.f_.ss); + return impl::AbslHashValueImpl(T{}, std::move(h), a.f_); } private: @@ -506,9 +536,11 @@ enum class weekday { }; CONSTEXPR_F weekday get_weekday(const civil_day& cd) noexcept { - CONSTEXPR_D weekday k_weekday_by_sun_off[7] = { - weekday::sunday, weekday::monday, weekday::tuesday, - weekday::wednesday, weekday::thursday, weekday::friday, + CONSTEXPR_D weekday k_weekday_by_mon_off[13] = { + weekday::monday, weekday::tuesday, weekday::wednesday, + weekday::thursday, weekday::friday, weekday::saturday, + weekday::sunday, weekday::monday, weekday::tuesday, + weekday::wednesday, weekday::thursday, weekday::friday, weekday::saturday, }; CONSTEXPR_D int k_weekday_offsets[1 + 12] = { @@ -517,7 +549,7 @@ CONSTEXPR_F weekday get_weekday(const civil_day& cd) noexcept { year_t wd = 2400 + (cd.year() % 400) - (cd.month() < 3); wd += wd / 4 - wd / 100 + wd / 400; wd += k_weekday_offsets[cd.month()] + cd.day(); - return k_weekday_by_sun_off[(wd % 7 + 7) % 7]; + return k_weekday_by_mon_off[wd % 7 + 6]; } //////////////////////////////////////////////////////////////////////// diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/src/time_zone_libc.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/src/time_zone_libc.cc index e35fa18b773..6db519e165c 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/src/time_zone_libc.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/src/time_zone_libc.cc @@ -20,6 +20,7 @@ #include <chrono> #include <ctime> +#include <limits> #include <tuple> #include <utility> @@ -85,6 +86,76 @@ OffsetAbbr get_offset_abbr(const T& tm, decltype(&T::__tm_gmtoff) = nullptr, #endif // !defined(__tm_gmtoff) && !defined(__tm_zone) #endif +inline std::tm* gm_time(const std::time_t *timep, std::tm *result) { +#if defined(_WIN32) || defined(_WIN64) + return gmtime_s(result, timep) ? nullptr : result; +#else + return gmtime_r(timep, result); +#endif +} + +inline std::tm* local_time(const std::time_t *timep, std::tm *result) { +#if defined(_WIN32) || defined(_WIN64) + return localtime_s(result, timep) ? nullptr : result; +#else + return localtime_r(timep, result); +#endif +} + +// Converts a civil second and "dst" flag into a time_t and UTC offset. +// Returns false if time_t cannot represent the requested civil second. +// Caller must have already checked that cs.year() will fit into a tm_year. +bool make_time(const civil_second& cs, int is_dst, std::time_t* t, int* off) { + std::tm tm; + tm.tm_year = static_cast<int>(cs.year() - year_t{1900}); + tm.tm_mon = cs.month() - 1; + tm.tm_mday = cs.day(); + tm.tm_hour = cs.hour(); + tm.tm_min = cs.minute(); + tm.tm_sec = cs.second(); + tm.tm_isdst = is_dst; + *t = std::mktime(&tm); + if (*t == std::time_t{-1}) { + std::tm tm2; + const std::tm* tmp = local_time(t, &tm2); + if (tmp == nullptr || tmp->tm_year != tm.tm_year || + tmp->tm_mon != tm.tm_mon || tmp->tm_mday != tm.tm_mday || + tmp->tm_hour != tm.tm_hour || tmp->tm_min != tm.tm_min || + tmp->tm_sec != tm.tm_sec) { + // A true error (not just one second before the epoch). + return false; + } + } + *off = get_offset_abbr(tm).first; + return true; +} + +// Find the least time_t in [lo:hi] where local time matches offset, given: +// (1) lo doesn't match, (2) hi does, and (3) there is only one transition. +std::time_t find_trans(std::time_t lo, std::time_t hi, int offset) { + std::tm tm; + while (lo + 1 != hi) { + const std::time_t mid = lo + (hi - lo) / 2; + if (std::tm* tmp = local_time(&mid, &tm)) { + if (get_offset_abbr(*tmp).first == offset) { + hi = mid; + } else { + lo = mid; + } + } else { + // If std::tm cannot hold some result we resort to a linear search, + // ignoring all failed conversions. Slow, but never really happens. + while (++lo != hi) { + if (std::tm* tmp = local_time(&lo, &tm)) { + if (get_offset_abbr(*tmp).first == offset) break; + } + } + return lo; + } + } + return hi; +} + } // namespace TimeZoneLibC::TimeZoneLibC(const std::string& name) @@ -93,50 +164,107 @@ TimeZoneLibC::TimeZoneLibC(const std::string& name) time_zone::absolute_lookup TimeZoneLibC::BreakTime( const time_point<seconds>& tp) const { time_zone::absolute_lookup al; - std::time_t t = ToUnixSeconds(tp); + al.offset = 0; + al.is_dst = false; + al.abbr = "-00"; + + const std::int_fast64_t s = ToUnixSeconds(tp); + + // If std::time_t cannot hold the input we saturate the output. + if (s < std::numeric_limits<std::time_t>::min()) { + al.cs = civil_second::min(); + return al; + } + if (s > std::numeric_limits<std::time_t>::max()) { + al.cs = civil_second::max(); + return al; + } + + const std::time_t t = static_cast<std::time_t>(s); std::tm tm; - if (local_) { -#if defined(_WIN32) || defined(_WIN64) - localtime_s(&tm, &t); -#else - localtime_r(&t, &tm); -#endif - std::tie(al.offset, al.abbr) = get_offset_abbr(tm); - } else { -#if defined(_WIN32) || defined(_WIN64) - gmtime_s(&tm, &t); -#else - gmtime_r(&t, &tm); -#endif - al.offset = 0; - al.abbr = "UTC"; + std::tm* tmp = local_ ? local_time(&t, &tm) : gm_time(&t, &tm); + + // If std::tm cannot hold the result we saturate the output. + if (tmp == nullptr) { + al.cs = (s < 0) ? civil_second::min() : civil_second::max(); + return al; } - al.cs = civil_second(tm.tm_year + year_t{1900}, tm.tm_mon + 1, tm.tm_mday, - tm.tm_hour, tm.tm_min, tm.tm_sec); - al.is_dst = tm.tm_isdst > 0; + + const year_t year = tmp->tm_year + year_t{1900}; + al.cs = civil_second(year, tmp->tm_mon + 1, tmp->tm_mday, + tmp->tm_hour, tmp->tm_min, tmp->tm_sec); + std::tie(al.offset, al.abbr) = get_offset_abbr(*tmp); + if (!local_) al.abbr = "UTC"; // as expected by cctz + al.is_dst = tmp->tm_isdst > 0; return al; } time_zone::civil_lookup TimeZoneLibC::MakeTime(const civil_second& cs) const { - time_zone::civil_lookup cl; - std::time_t t; - if (local_) { - // Does not handle SKIPPED/AMBIGUOUS or huge years. - std::tm tm; - tm.tm_year = static_cast<int>(cs.year() - 1900); - tm.tm_mon = cs.month() - 1; - tm.tm_mday = cs.day(); - tm.tm_hour = cs.hour(); - tm.tm_min = cs.minute(); - tm.tm_sec = cs.second(); - tm.tm_isdst = -1; - t = std::mktime(&tm); + if (!local_) { + // If time_point<seconds> cannot hold the result we saturate. + static const civil_second min_tp_cs = + civil_second() + ToUnixSeconds(time_point<seconds>::min()); + static const civil_second max_tp_cs = + civil_second() + ToUnixSeconds(time_point<seconds>::max()); + const time_point<seconds> tp = + (cs < min_tp_cs) + ? time_point<seconds>::min() + : (cs > max_tp_cs) ? time_point<seconds>::max() + : FromUnixSeconds(cs - civil_second()); + return {time_zone::civil_lookup::UNIQUE, tp, tp, tp}; + } + + // If tm_year cannot hold the requested year we saturate the result. + if (cs.year() < 0) { + if (cs.year() < std::numeric_limits<int>::min() + year_t{1900}) { + const time_point<seconds> tp = time_point<seconds>::min(); + return {time_zone::civil_lookup::UNIQUE, tp, tp, tp}; + } } else { - t = cs - civil_second(); + if (cs.year() - year_t{1900} > std::numeric_limits<int>::max()) { + const time_point<seconds> tp = time_point<seconds>::max(); + return {time_zone::civil_lookup::UNIQUE, tp, tp, tp}; + } + } + + // We probe with "is_dst" values of 0 and 1 to try to distinguish unique + // civil seconds from skipped or repeated ones. This is not always possible + // however, as the "dst" flag does not change over some offset transitions. + // We are also subject to the vagaries of mktime() implementations. + std::time_t t0, t1; + int offset0, offset1; + if (make_time(cs, 0, &t0, &offset0) && make_time(cs, 1, &t1, &offset1)) { + if (t0 == t1) { + // The civil time was singular (pre == trans == post). + const time_point<seconds> tp = FromUnixSeconds(t0); + return {time_zone::civil_lookup::UNIQUE, tp, tp, tp}; + } + + if (t0 > t1) { + std::swap(t0, t1); + std::swap(offset0, offset1); + } + const std::time_t tt = find_trans(t0, t1, offset1); + const time_point<seconds> trans = FromUnixSeconds(tt); + + if (offset0 < offset1) { + // The civil time did not exist (pre >= trans > post). + const time_point<seconds> pre = FromUnixSeconds(t1); + const time_point<seconds> post = FromUnixSeconds(t0); + return {time_zone::civil_lookup::SKIPPED, pre, trans, post}; + } + + // The civil time was ambiguous (pre < trans <= post). + const time_point<seconds> pre = FromUnixSeconds(t0); + const time_point<seconds> post = FromUnixSeconds(t1); + return {time_zone::civil_lookup::REPEATED, pre, trans, post}; } - cl.kind = time_zone::civil_lookup::UNIQUE; - cl.pre = cl.trans = cl.post = FromUnixSeconds(t); - return cl; + + // make_time() failed somehow so we saturate the result. + const time_point<seconds> tp = (cs < civil_second()) + ? time_point<seconds>::min() + : time_point<seconds>::max(); + return {time_zone::civil_lookup::UNIQUE, tp, tp, tp}; } bool TimeZoneLibC::NextTransition(const time_point<seconds>& tp, diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/src/time_zone_lookup_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/src/time_zone_lookup_test.cc index f28e7f853b6..e84b9469aa0 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/src/time_zone_lookup_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/internal/cctz/src/time_zone_lookup_test.cc @@ -16,7 +16,9 @@ #include <chrono> #include <cstddef> +#include <cstdlib> #include <future> +#include <limits> #include <string> #include <thread> #include <vector> @@ -925,7 +927,7 @@ TEST(MakeTime, Normalization) { EXPECT_EQ(tp, convert(civil_second(2009, 2, 13, 18, 30, 90), tz)); // second } -// NOTE: Run this with --copt=-ftrapv to detect overflow problems. +// NOTE: Run this with -ftrapv to detect overflow problems. TEST(MakeTime, SysSecondsLimits) { const char RFC3339[] = "%Y-%m-%dT%H:%M:%S%Ez"; const time_zone utc = utc_time_zone(); @@ -991,19 +993,107 @@ TEST(MakeTime, SysSecondsLimits) { tp = convert(civil_second::min(), west); EXPECT_EQ(time_point<absl::time_internal::cctz::seconds>::min(), tp); + // Some similar checks for the "libc" time-zone implementation. if (sizeof(std::time_t) >= 8) { // Checks that "tm_year + 1900", as used by the "libc" implementation, // can produce year values beyond the range on an int without overflow. #if defined(_WIN32) || defined(_WIN64) - // localtime_s() and gmtime_s() don't believe in years past 3000. + // localtime_s() and gmtime_s() don't believe in years outside [1970:3000]. #else - const time_zone libc_utc = LoadZone("libc:UTC"); - tp = convert(civil_year(year_t{2147483648}), libc_utc); - EXPECT_EQ("2147483648-01-01T00:00:00+00:00", format(RFC3339, tp, libc_utc)); + const time_zone utc = LoadZone("libc:UTC"); + const year_t max_tm_year = year_t{std::numeric_limits<int>::max()} + 1900; + tp = convert(civil_second(max_tm_year, 12, 31, 23, 59, 59), utc); + EXPECT_EQ("2147485547-12-31T23:59:59+00:00", format(RFC3339, tp, utc)); + const year_t min_tm_year = year_t{std::numeric_limits<int>::min()} + 1900; + tp = convert(civil_second(min_tm_year, 1, 1, 0, 0, 0), utc); + EXPECT_EQ("-2147481748-01-01T00:00:00+00:00", format(RFC3339, tp, utc)); #endif } } +TEST(MakeTime, LocalTimeLibC) { + // Checks that cctz and libc agree on transition points in [1970:2037]. + // + // We limit this test case to environments where: + // 1) we know how to change the time zone used by localtime()/mktime(), + // 2) cctz and localtime()/mktime() will use similar-enough tzdata, and + // 3) we have some idea about how mktime() behaves during transitions. +#if defined(__linux__) + const char* const ep = getenv("TZ"); + std::string tz_name = (ep != nullptr) ? ep : ""; + for (const char* const* np = kTimeZoneNames; *np != nullptr; ++np) { + ASSERT_EQ(0, setenv("TZ", *np, 1)); // change what "localtime" means + const auto zi = local_time_zone(); + const auto lc = LoadZone("libc:localtime"); + time_zone::civil_transition trans; + for (auto tp = zi.lookup(civil_second()).trans; + zi.next_transition(tp, &trans); + tp = zi.lookup(trans.to).trans) { + const auto fcl = zi.lookup(trans.from); + const auto tcl = zi.lookup(trans.to); + civil_second cs; // compare cs in zi and lc + if (fcl.kind == time_zone::civil_lookup::UNIQUE) { + if (tcl.kind == time_zone::civil_lookup::UNIQUE) { + // Both unique; must be an is_dst or abbr change. + ASSERT_EQ(trans.from, trans.to); + const auto trans = fcl.trans; + const auto tal = zi.lookup(trans); + const auto tprev = trans - absl::time_internal::cctz::seconds(1); + const auto pal = zi.lookup(tprev); + if (pal.is_dst == tal.is_dst) { + ASSERT_STRNE(pal.abbr, tal.abbr); + } + continue; + } + ASSERT_EQ(time_zone::civil_lookup::REPEATED, tcl.kind); + cs = trans.to; + } else { + ASSERT_EQ(time_zone::civil_lookup::UNIQUE, tcl.kind); + ASSERT_EQ(time_zone::civil_lookup::SKIPPED, fcl.kind); + cs = trans.from; + } + if (cs.year() > 2037) break; // limit test time (and to 32-bit time_t) + const auto cl_zi = zi.lookup(cs); + if (zi.lookup(cl_zi.pre).is_dst == zi.lookup(cl_zi.post).is_dst) { + // The "libc" implementation cannot correctly classify transitions + // that don't change the "tm_isdst" flag. In Europe/Volgograd, for + // example, there is a SKIPPED transition from +03 to +04 with dst=F + // on both sides ... + // 1540681199 = 2018-10-28 01:59:59 +03:00:00 [dst=F off=10800] + // 1540681200 = 2018-10-28 03:00:00 +04:00:00 [dst=F off=14400] + // but std::mktime(2018-10-28 02:00:00, tm_isdst=0) fails, unlike, + // say, the similar Europe/Chisinau transition from +02 to +03 ... + // 1521935999 = 2018-03-25 01:59:59 +02:00:00 [dst=F off=7200] + // 1521936000 = 2018-03-25 03:00:00 +03:00:00 [dst=T off=10800] + // where std::mktime(2018-03-25 02:00:00, tm_isdst=0) succeeds and + // returns 1521936000. + continue; + } + if (cs == civil_second(2037, 10, 4, 2, 0, 0)) { + const std::string tzname = *np; + if (tzname == "Africa/Casablanca" || tzname == "Africa/El_Aaiun") { + // The "libc" implementation gets this transition wrong (at least + // until 2018g when it was removed), returning an offset of 3600 + // instead of 0. TODO: Revert this when 2018g is ubiquitous. + continue; + } + } + const auto cl_lc = lc.lookup(cs); + SCOPED_TRACE(testing::Message() << "For " << cs << " in " << *np); + EXPECT_EQ(cl_zi.kind, cl_lc.kind); + EXPECT_EQ(cl_zi.pre, cl_lc.pre); + EXPECT_EQ(cl_zi.trans, cl_lc.trans); + EXPECT_EQ(cl_zi.post, cl_lc.post); + } + } + if (ep == nullptr) { + ASSERT_EQ(0, unsetenv("TZ")); + } else { + ASSERT_EQ(0, setenv("TZ", tz_name.c_str(), 1)); + } +#endif +} + TEST(NextTransition, UTC) { const auto tz = utc_time_zone(); time_zone::civil_transition trans; diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/time.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/time.h index e9e989cb056..ae3b3fad853 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/time.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/time/time.h @@ -69,6 +69,7 @@ #include <winsock2.h> #endif #include <chrono> // NOLINT(build/c++11) +#include <cmath> #include <cstdint> #include <ctime> #include <ostream> @@ -153,6 +154,16 @@ class Duration { // Value semantics. constexpr Duration() : rep_hi_(0), rep_lo_(0) {} // zero-length duration + // Copyable. +#if !defined(__clang__) && defined(_MSC_VER) && _MSC_VER < 1910 + // Explicitly defining the constexpr copy constructor avoids an MSVC bug. + constexpr Duration(const Duration& d) + : rep_hi_(d.rep_hi_), rep_lo_(d.rep_lo_) {} +#else + constexpr Duration(const Duration& d) = default; +#endif + Duration& operator=(const Duration& d) = default; + // Compound assignment operators. Duration& operator+=(Duration d); Duration& operator-=(Duration d); @@ -401,10 +412,12 @@ Duration Milliseconds(T n) { } template <typename T, time_internal::EnableIfFloat<T> = 0> Duration Seconds(T n) { - if (n >= 0) { + if (n >= 0) { // Note: `NaN >= 0` is false. if (n >= (std::numeric_limits<int64_t>::max)()) return InfiniteDuration(); return time_internal::MakePosDoubleDuration(n); } else { + if (std::isnan(n)) + return std::signbit(n) ? -InfiniteDuration() : InfiniteDuration(); if (n <= (std::numeric_limits<int64_t>::min)()) return -InfiniteDuration(); return -time_internal::MakePosDoubleDuration(-n); } @@ -584,7 +597,11 @@ class Time { // absl::Time t = absl::Now(); // absl::Time t = absl::TimeFromTimeval(tv); // absl::Time t = absl::InfinitePast(); - constexpr Time() {} + constexpr Time() = default; + + // Copyable. + constexpr Time(const Time& t) = default; + Time& operator=(const Time& t) = default; // Assignment operators. Time& operator+=(Duration d) { @@ -826,6 +843,8 @@ class TimeZone { public: explicit TimeZone(time_internal::cctz::time_zone tz) : cz_(tz) {} TimeZone() = default; // UTC, but prefer UTCTimeZone() to be explicit. + + // Copyable. TimeZone(const TimeZone&) = default; TimeZone& operator=(const TimeZone&) = default; @@ -1320,9 +1339,12 @@ constexpr Duration MakeNormalizedDuration(int64_t sec, int64_t ticks) { return (ticks < 0) ? MakeDuration(sec - 1, ticks + kTicksPerSecond) : MakeDuration(sec, ticks); } + // Provide access to the Duration representation. constexpr int64_t GetRepHi(Duration d) { return d.rep_hi_; } constexpr uint32_t GetRepLo(Duration d) { return d.rep_lo_; } + +// Returns true iff d is positive or negative infinity. constexpr bool IsInfiniteDuration(Duration d) { return GetRepLo(d) == ~0U; } // Returns an infinite Duration with the opposite sign. @@ -1419,10 +1441,10 @@ T ToChronoDuration(Duration d) { using Period = typename T::period; static_assert(IsValidRep64<Rep>(0), "duration::rep is invalid"); if (time_internal::IsInfiniteDuration(d)) - return d < ZeroDuration() ? T::min() : T::max(); + return d < ZeroDuration() ? (T::min)() : (T::max)(); const auto v = ToInt64(d, Period{}); - if (v > (std::numeric_limits<Rep>::max)()) return T::max(); - if (v < (std::numeric_limits<Rep>::min)()) return T::min(); + if (v > (std::numeric_limits<Rep>::max)()) return (T::max)(); + if (v < (std::numeric_limits<Rep>::min)()) return (T::min)(); return T{v}; } diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/BUILD.bazel index 43899ca7ccf..2e490009c39 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/BUILD.bazel @@ -15,7 +15,7 @@ # load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", "ABSL_EXCEPTIONS_FLAG", @@ -287,6 +287,7 @@ cc_test( linkopts = ABSL_EXCEPTIONS_FLAG_LINKOPTS, deps = [ ":variant", + "//absl/base:config", "//absl/base:exception_safety_testing", "//absl/memory", "@com_google_googletest//:gtest_main", diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/internal/variant.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/internal/variant.h index eff4fefed40..477e5895ed7 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/internal/variant.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/internal/variant.h @@ -15,6 +15,7 @@ // Implementation details of absl/types/variant.h, pulled into a // separate file to avoid cluttering the top of the API header with // implementation details. +// #ifndef ABSL_TYPES_variant_internal_H_ #define ABSL_TYPES_variant_internal_H_ @@ -1234,23 +1235,29 @@ using VariantCopyBase = absl::conditional_t< // Base that is dependent on whether or not the move-assign can be trivial. template <class... T> using VariantMoveAssignBase = absl::conditional_t< - absl::disjunction<absl::conjunction<absl::is_move_assignable<Union<T...>>, - std::is_move_constructible<Union<T...>>, - std::is_destructible<Union<T...>>>, - absl::negation<absl::conjunction< - std::is_move_constructible<T>..., - absl::is_move_assignable<T>...>>>::value, + absl::disjunction< + absl::conjunction<absl::is_move_assignable<Union<T...>>, + std::is_move_constructible<Union<T...>>, + std::is_destructible<Union<T...>>>, + absl::negation<absl::conjunction<std::is_move_constructible<T>..., + // Note: We're not qualifying this with + // absl:: because it doesn't compile + // under MSVC. + is_move_assignable<T>...>>>::value, VariantCopyBase<T...>, VariantMoveAssignBaseNontrivial<T...>>; // Base that is dependent on whether or not the copy-assign can be trivial. template <class... T> using VariantCopyAssignBase = absl::conditional_t< - absl::disjunction<absl::conjunction<absl::is_copy_assignable<Union<T...>>, - std::is_copy_constructible<Union<T...>>, - std::is_destructible<Union<T...>>>, - absl::negation<absl::conjunction< - std::is_copy_constructible<T>..., - absl::is_copy_assignable<T>...>>>::value, + absl::disjunction< + absl::conjunction<absl::is_copy_assignable<Union<T...>>, + std::is_copy_constructible<Union<T...>>, + std::is_destructible<Union<T...>>>, + absl::negation<absl::conjunction<std::is_copy_constructible<T>..., + // Note: We're not qualifying this with + // absl:: because it doesn't compile + // under MSVC. + is_copy_assignable<T>...>>>::value, VariantMoveAssignBase<T...>, VariantCopyAssignBaseNontrivial<T...>>; template <class... T> diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant.h b/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant.h index 2f78722f8b7..48c5d7bf2c2 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant.h +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant.h @@ -82,7 +82,7 @@ namespace absl { // absl::variant // ----------------------------------------------------------------------------- // -// An 'absl::variant` type is a form of type-safe union. An `absl::variant` -- +// An `absl::variant` type is a form of type-safe union. An `absl::variant` -- // except in exceptional cases -- always holds a value of one of its alternative // types. // @@ -136,7 +136,7 @@ void swap(variant<Ts...>& v, variant<Ts...>& w) noexcept(noexcept(v.swap(w))) { // variant_size // -// Returns the number of alterative types available for a given `absl::variant` +// Returns the number of alternative types available for a given `absl::variant` // type as a compile-time constant expression. As this is a class template, it // is not generally useful for accessing the number of alternative types of // any given `absl::variant` instance. @@ -399,9 +399,9 @@ constexpr absl::add_pointer_t<const T> get_if( // Calls a provided functor on a given set of variants. `absl::visit()` is // commonly used to conditionally inspect the state of a given variant (or set // of variants). -// Requires: The expression in the Effects: element shall be a valid expression -// of the same type and value category, for all combinations of alternative -// types of all variants. Otherwise, the program is ill-formed. +// +// The functor must return the same type when called with any of the variants' +// alternatives. // // Example: // @@ -414,6 +414,7 @@ constexpr absl::add_pointer_t<const T> get_if( // }; // // // Declare our variant, and call `absl::visit()` on it. +// // Note that `GetVariant()` returns void in either case. // absl::variant<int, std::string> foo = std::string("foo"); // GetVariant visitor; // absl::visit(visitor, foo); // Prints `The variant's value is: foo' @@ -453,7 +454,7 @@ class variant<T0, Tn...> : private variant_internal::VariantBase<T0, Tn...> { std::is_object<Tn>...>::value, "Attempted to instantiate a variant containing a non-object " "type."); - // Intentionally not qualifing `negation` with `absl::` to work around a bug + // Intentionally not qualifying `negation` with `absl::` to work around a bug // in MSVC 2015 with inline namespace and variadic template. static_assert(absl::conjunction<negation<std::is_array<T0> >, negation<std::is_array<Tn> >...>::value, @@ -561,7 +562,7 @@ class variant<T0, Tn...> : private variant_internal::VariantBase<T0, Tn...> { // Assignment Operators - // Copy assignement operator + // Copy assignment operator variant& operator=(const variant& other) = default; // Move assignment operator diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant_exception_safety_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant_exception_safety_test.cc index 58436f07b84..82425dbd190 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant_exception_safety_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant_exception_safety_test.cc @@ -11,6 +11,7 @@ // 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/types/variant.h" #include <iostream> @@ -20,8 +21,11 @@ #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "absl/base/config.h" #include "absl/base/internal/exception_safety_testing.h" #include "absl/memory/memory.h" +// See comment in absl/base/config.h +#if !defined(ABSL_INTERNAL_MSVC_2017_DBG_MODE) namespace absl { namespace { @@ -506,3 +510,5 @@ TEST(VariantExceptionSafetyTest, Swap) { } // namespace } // namespace absl + +#endif // !defined(ABSL_INTERNAL_MSVC_2017_DBG_MODE) diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant_test.cc b/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant_test.cc index 626d5e617ea..f47f3a728dc 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant_test.cc +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/types/variant_test.cc @@ -559,9 +559,14 @@ TEST(VariantTest, TestDtor) { } #ifdef ABSL_HAVE_EXCEPTIONS - +// See comment in absl/base/config.h +#if defined(ABSL_INTERNAL_MSVC_2017_DBG_MODE) +TEST(VariantTest, DISABLED_TestDtorValuelessByException) +#else // Test destruction when in the valueless_by_exception state. -TEST(VariantTest, TestDtorValuelessByException) { +TEST(VariantTest, TestDtorValuelessByException) +#endif +{ int counter = 0; IncrementInDtor counter_adjuster(&counter); diff --git a/src/third_party/abseil-cpp-master/abseil-cpp/absl/utility/BUILD.bazel b/src/third_party/abseil-cpp-master/abseil-cpp/absl/utility/BUILD.bazel index c01b49bc97d..5185ccd8421 100644 --- a/src/third_party/abseil-cpp-master/abseil-cpp/absl/utility/BUILD.bazel +++ b/src/third_party/abseil-cpp-master/abseil-cpp/absl/utility/BUILD.bazel @@ -1,5 +1,5 @@ load( - "//absl:copts.bzl", + "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", "ABSL_TEST_COPTS", ) diff --git a/src/third_party/abseil-cpp-master/patches/0001-Fix-warning-C4309-argument-truncation-of-constant-va.patch b/src/third_party/abseil-cpp-master/patches/0001-Fix-warning-C4309-argument-truncation-of-constant-va.patch deleted file mode 100644 index 8c39d0bde8f..00000000000 --- a/src/third_party/abseil-cpp-master/patches/0001-Fix-warning-C4309-argument-truncation-of-constant-va.patch +++ /dev/null @@ -1,26 +0,0 @@ -From 51d2a5c73814f4e2804754368ab08692d2b139c8 Mon Sep 17 00:00:00 2001 -From: Henrik Edin <henrik.edin@mongodb.com> -Date: Thu, 8 Nov 2018 18:30:03 -0500 -Subject: [PATCH 1/2] Fix warning C4309: 'argument': truncation of constant - value - ---- - absl/container/internal/raw_hash_set.h | 2 +- - 1 file changed, 1 insertion(+), 1 deletion(-) - -diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h -index 10fa3d8..f23644a 100644 ---- a/absl/container/internal/raw_hash_set.h -+++ b/absl/container/internal/raw_hash_set.h -@@ -403,7 +403,7 @@ struct GroupSse2Impl { - } - - void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const { -- auto msbs = _mm_set1_epi8(0x80); -+ auto msbs = _mm_set1_epi8('\x80'); - auto x126 = _mm_set1_epi8(126); - #if SWISSTABLE_HAVE_SSSE3 - auto res = _mm_or_si128(_mm_shuffle_epi8(x126, ctrl), msbs); --- -2.10.1.windows.1 - diff --git a/src/third_party/abseil-cpp-master/patches/0002-Use-_umul128-on-Windows-to-improve-performance-of-Mi.patch b/src/third_party/abseil-cpp-master/patches/0002-Use-_umul128-on-Windows-to-improve-performance-of-Mi.patch deleted file mode 100644 index 1e32bf30cfd..00000000000 --- a/src/third_party/abseil-cpp-master/patches/0002-Use-_umul128-on-Windows-to-improve-performance-of-Mi.patch +++ /dev/null @@ -1,37 +0,0 @@ -From e88fe4c225e9efe5c50d49e2a697edeb20d9ed8c Mon Sep 17 00:00:00 2001 -From: Henrik Edin <henrik.edin@mongodb.com> -Date: Thu, 8 Nov 2018 18:32:09 -0500 -Subject: [PATCH 2/2] Use _umul128 on Windows to improve performance of Mix() - on MSVC. - ---- - absl/hash/internal/hash.h | 6 ++++++ - 1 file changed, 6 insertions(+) - -diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h -index b66cc1b..7106077 100644 ---- a/absl/hash/internal/hash.h -+++ b/absl/hash/internal/hash.h -@@ -773,6 +773,7 @@ class CityHashState : public HashStateBase<CityHashState> { - } - - ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Mix(uint64_t state, uint64_t v) { -+#if !defined(_MSC_VER) || !defined(_WIN64) - using MultType = - absl::conditional_t<sizeof(size_t) == 4, uint64_t, uint128>; - // We do the addition in 64-bit space to make sure the 128-bit -@@ -782,6 +783,11 @@ class CityHashState : public HashStateBase<CityHashState> { - MultType m = state + v; - m *= kMul; - return static_cast<uint64_t>(m ^ (m >> (sizeof(m) * 8 / 2))); -+#else -+ uint64_t high; -+ uint64_t low = _umul128(state + v, kMul, &high); -+ return low ^ high; -+#endif - } - - // Seed() --- -2.10.1.windows.1 - |