diff options
1057 files changed, 40275 insertions, 7092 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 39ff0a29dcdf..a57e36fddcde 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -27,7 +27,7 @@ if (CMAKE_SOURCE_DIR STREQUAL CMAKE_CURRENT_SOURCE_DIR) project(libcxx CXX C) set(PACKAGE_NAME libcxx) - set(PACKAGE_VERSION 7.0.0svn) + set(PACKAGE_VERSION 8.0.0svn) set(PACKAGE_STRING "${PACKAGE_NAME} ${PACKAGE_VERSION}") set(PACKAGE_BUGREPORT "llvm-bugs@lists.llvm.org") @@ -50,9 +50,14 @@ MACRO_ENSURE_OUT_OF_SOURCE_BUILD( "${PROJECT_NAME} requires an out of source build. Please create a separate build directory and run 'cmake /path/to/${PROJECT_NAME} [options]' there." ) +if("${CMAKE_CXX_COMPILER_ID}" STREQUAL "Clang" AND "${CMAKE_CXX_SIMULATE_ID}" STREQUAL "MSVC") + message(STATUS "Configuring for clang-cl") + set(LIBCXX_TARGETING_CLANG_CL ON) +endif() if (MSVC) set(LIBCXX_TARGETING_MSVC ON) + message(STATUS "Configuring for MSVC") else() set(LIBCXX_TARGETING_MSVC OFF) endif() @@ -77,7 +82,12 @@ option(LIBCXX_ENABLE_FILESYSTEM "Build filesystem as part of libc++fs.a" option(LIBCXX_INCLUDE_TESTS "Build the libc++ tests." ${LLVM_INCLUDE_TESTS}) # Benchmark options ----------------------------------------------------------- -option(LIBCXX_INCLUDE_BENCHMARKS "Build the libc++ benchmarks and their dependancies" ON) +option(LIBCXX_INCLUDE_BENCHMARKS "Build the libc++ benchmarks and their dependencies" ON) + +set(LIBCXX_BENCHMARK_TEST_ARGS_DEFAULT --benchmark_min_time=0.01) +set(LIBCXX_BENCHMARK_TEST_ARGS "${LIBCXX_BENCHMARK_TEST_ARGS_DEFAULT}" CACHE STRING + "Arguments to pass when running the benchmarks using check-cxx-benchmarks") + set(LIBCXX_BENCHMARK_NATIVE_STDLIB "" CACHE STRING "Build the benchmarks against the specified native STL. The value must be one of libc++/libstdc++") @@ -111,15 +121,12 @@ cmake_dependent_option(LIBCXX_INSTALL_FILESYSTEM_LIBRARY "Install libc++fs.a" ON "LIBCXX_ENABLE_FILESYSTEM;LIBCXX_INSTALL_LIBRARY" OFF) -if (FUCHSIA) - set(DEFAULT_ABI_VERSION 2) -else() - set(DEFAULT_ABI_VERSION 1) -endif() -set(LIBCXX_ABI_VERSION ${DEFAULT_ABI_VERSION} CACHE STRING "ABI version of libc++.") +set(LIBCXX_ABI_VERSION "1" CACHE STRING "ABI version of libc++. Can be either 1 or 2, where 2 is currently not stable. Defaults to 1.") +set(LIBCXX_ABI_NAMESPACE "" CACHE STRING "The inline ABI namespace used by libc++. It defaults to __n where `n` is the current ABI version.") option(LIBCXX_ABI_UNSTABLE "Unstable ABI of libc++." OFF) option(LIBCXX_ABI_FORCE_ITANIUM "Ignore auto-detection and force use of the Itanium ABI.") option(LIBCXX_ABI_FORCE_MICROSOFT "Ignore auto-detection and force use of the Microsoft ABI.") +option(LIBCXX_HIDE_FROM_ABI_PER_TU_BY_DEFAULT "Enable per TU ABI insulation by default. To be used by vendors." OFF) set(LIBCXX_ABI_DEFINES "" CACHE STRING "A semicolon separated list of ABI macros to define in the site config header.") option(LIBCXX_USE_COMPILER_RT "Use compiler-rt instead of libgcc" OFF) @@ -175,7 +182,7 @@ cmake_dependent_option(LIBCXX_STATICALLY_LINK_ABI_IN_STATIC_LIBRARY cmake_dependent_option(LIBCXX_STATICALLY_LINK_ABI_IN_SHARED_LIBRARY "Statically link the ABI library to shared library" ON - "LIBCXX_ENABLE_STATIC_ABI_LIBRARY;LIBCXX_ENABLE_STATIC" OFF) + "LIBCXX_ENABLE_STATIC_ABI_LIBRARY;LIBCXX_ENABLE_SHARED" OFF) # Generate and install a linker script inplace of libc++.so. The linker script # will link libc++ to the correct ABI library. This option is on by default @@ -276,6 +283,9 @@ endif() option(LIBCXX_CONFIGURE_IDE "Configure libcxx for use within an IDE" ${LIBCXX_CONFIGURE_IDE_DEFAULT}) +option(LIBCXX_HERMETIC_STATIC_LIBRARY + "Do not export any symbols from the static library." OFF) + #=============================================================================== # Check option configurations #=============================================================================== @@ -502,14 +512,16 @@ remove_flags(-Wno-pedantic -pedantic-errors -pedantic) # Required flags ============================================================== set(LIBCXX_STANDARD_VER c++11 CACHE INTERNAL "internal option to change build dialect") -if (LIBCXX_HAS_MUSL_LIBC) +if (LIBCXX_HAS_MUSL_LIBC OR LIBCXX_TARGETING_CLANG_CL) # musl's pthread implementations uses volatile types in their structs which is # not a constexpr in C++11 but is in C++14, so we use C++14 with musl. set(LIBCXX_STANDARD_VER c++14 CACHE INTERNAL "internal option to change build dialect") endif() add_compile_flags_if_supported(-std=${LIBCXX_STANDARD_VER}) +add_compile_flags_if_supported("/std:${LIBCXX_STANDARD_VER}") mangle_name("LIBCXX_SUPPORTS_STD_EQ_${LIBCXX_STANDARD_VER}_FLAG" SUPPORTS_DIALECT_NAME) -if(NOT ${SUPPORTS_DIALECT_NAME}) +mangle_name("LIBCXX_SUPPORTS_STD_COLON_${LIBCXX_STANDARD_VER}_FLAG" SUPPORTS_DIALECT_NAME_MSVC) +if(NOT ${SUPPORTS_DIALECT_NAME} AND NOT ${SUPPORTS_DIALECT_NAME_MSVC}) if(NOT "${CMAKE_CXX_COMPILER_ID}" STREQUAL "MSVC" AND NOT "${CMAKE_CXX_SIMULATE_ID}" STREQUAL "MSVC") message(FATAL_ERROR "C++11 or greater is required but the compiler does not support ${LIBCXX_STANDARD_VER}") endif() @@ -544,11 +556,29 @@ add_definitions(-D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) add_compile_flags_if_supported( -Wall -Wextra -W -Wwrite-strings -Wno-unused-parameter -Wno-long-long - -Werror=return-type) + -Werror=return-type -Wextra-semi) if ("${CMAKE_CXX_COMPILER_ID}" MATCHES "Clang") add_compile_flags_if_supported( -Wno-user-defined-literals -Wno-covered-switch-default) + if (LIBCXX_TARGETING_CLANG_CL) + add_compile_flags_if_supported( + -Wno-c++98-compat + -Wno-c++98-compat-pedantic + -Wno-c++11-compat + -Wno-undef + -Wno-reserved-id-macro + -Wno-gnu-include-next + -Wno-gcc-compat # For ignoring "'diagnose_if' is a clang extension" warnings + -Wno-zero-as-null-pointer-constant # FIXME: Remove this and fix all occurrences. + -Wno-deprecated-dynamic-exception-spec # For auto_ptr + -Wno-sign-conversion + -Wno-old-style-cast + -Wno-deprecated # FIXME: Remove this and fix all occurrences. + -Wno-shift-sign-overflow # FIXME: Why do we need this with clang-cl but not clang? + -Wno-double-promotion # FIXME: remove me + ) + endif() elseif("${CMAKE_CXX_COMPILER_ID}" MATCHES "GNU") add_compile_flags_if_supported( -Wno-literal-suffix @@ -621,47 +651,67 @@ endif() # Sanitizer flags ============================================================= -# Configure for sanitizers. If LIBCXX_STANDALONE_BUILD then we have to do -# the flag translation ourselves. Othewise LLVM's CMakeList.txt will handle it. -if (LIBCXX_STANDALONE_BUILD) - set(LLVM_USE_SANITIZER "" CACHE STRING - "Define the sanitizer used to build the library and tests") +function(get_sanitizer_flags OUT_VAR USE_SANITIZER) + set(SANITIZER_FLAGS) + set(USE_SANITIZER "${USE_SANITIZER}") # NOTE: LLVM_USE_SANITIZER checks for a UNIX like system instead of MSVC. # But we don't have LLVM_ON_UNIX so checking for MSVC is the best we can do. - if (LLVM_USE_SANITIZER AND NOT MSVC) - add_flags_if_supported("-fno-omit-frame-pointer") - add_flags_if_supported("-gline-tables-only") + if (USE_SANITIZER AND NOT MSVC) + append_flags_if_supported(SANITIZER_FLAGS "-fno-omit-frame-pointer") + append_flags_if_supported(SANITIZER_FLAGS "-gline-tables-only") if (NOT uppercase_CMAKE_BUILD_TYPE STREQUAL "DEBUG" AND - NOT uppercase_CMAKE_BUILD_TYPE STREQUAL "RELWITHDEBINFO") - add_flags_if_supported("-gline-tables-only") + NOT uppercase_CMAKE_BUILD_TYPE STREQUAL "RELWITHDEBINFO") + append_flags_if_supported(SANITIZER_FLAGS "-gline-tables-only") endif() - if (LLVM_USE_SANITIZER STREQUAL "Address") - add_flags("-fsanitize=address") - elseif (LLVM_USE_SANITIZER MATCHES "Memory(WithOrigins)?") - add_flags(-fsanitize=memory) - if (LLVM_USE_SANITIZER STREQUAL "MemoryWithOrigins") - add_flags("-fsanitize-memory-track-origins") + if (USE_SANITIZER STREQUAL "Address") + append_flags(SANITIZER_FLAGS "-fsanitize=address") + elseif (USE_SANITIZER MATCHES "Memory(WithOrigins)?") + append_flags(SANITIZER_FLAGS -fsanitize=memory) + if (USE_SANITIZER STREQUAL "MemoryWithOrigins") + append_flags(SANITIZER_FLAGS "-fsanitize-memory-track-origins") endif() - elseif (LLVM_USE_SANITIZER STREQUAL "Undefined") - add_flags("-fsanitize=undefined -fno-sanitize=vptr,function -fno-sanitize-recover=all") - elseif (LLVM_USE_SANITIZER STREQUAL "Thread") - add_flags(-fsanitize=thread) + elseif (USE_SANITIZER STREQUAL "Undefined") + append_flags(SANITIZER_FLAGS "-fsanitize=undefined -fno-sanitize=vptr,function -fno-sanitize-recover=all") + elseif (USE_SANITIZER STREQUAL "Thread") + append_flags(SANITIZER_FLAGS -fsanitize=thread) else() - message(WARNING "Unsupported value of LLVM_USE_SANITIZER: ${LLVM_USE_SANITIZER}") + message(WARNING "Unsupported value of LLVM_USE_SANITIZER: ${USE_SANITIZER}") endif() - elseif(LLVM_USE_SANITIZER AND MSVC) + elseif(USE_SANITIZER AND MSVC) message(WARNING "LLVM_USE_SANITIZER is not supported on this platform.") endif() + set(${OUT_VAR} "${SANITIZER_FLAGS}" PARENT_SCOPE) +endfunction() + +# Configure for sanitizers. If LIBCXX_STANDALONE_BUILD then we have to do +# the flag translation ourselves. Othewise LLVM's CMakeList.txt will handle it. +if (LIBCXX_STANDALONE_BUILD) + set(LLVM_USE_SANITIZER "" CACHE STRING + "Define the sanitizer used to build the library and tests") +endif() +get_sanitizer_flags(SANITIZER_FLAGS "${LLVM_USE_SANITIZER}") +if (LIBCXX_STANDALONE_BUILD AND SANITIZER_FLAGS) + add_flags(${SANITIZER_FLAGS}) endif() # Configuration file flags ===================================================== -if (NOT LIBCXX_ABI_VERSION EQUAL DEFAULT_ABI_VERSION) +if (NOT LIBCXX_ABI_VERSION EQUAL 1) config_define(${LIBCXX_ABI_VERSION} _LIBCPP_ABI_VERSION) endif() +if (NOT LIBCXX_ABI_NAMESPACE STREQUAL "") + if (NOT LIBCXX_ABI_NAMESPACE MATCHES "__.*") + message(WARNING "LIBCXX_ABI_NAMESPACE must be a reserved identifier.") + endif() + if (LIBCXX_ABI_NAMESPACE MATCHES "__[0-9]+$") + message(FATAL_ERROR "LIBCXX_ABI_NAMESPACE '${LIBCXX_ABI_NAMESPACE}' is reserved for use by libc++.") + endif() + config_define(${LIBCXX_ABI_NAMESPACE} _LIBCPP_ABI_NAMESPACE) +endif() config_define_if(LIBCXX_ABI_UNSTABLE _LIBCPP_ABI_UNSTABLE) config_define_if(LIBCXX_ABI_FORCE_ITANIUM _LIBCPP_ABI_FORCE_ITANIUM) config_define_if(LIBCXX_ABI_FORCE_MICROSOFT _LIBCPP_ABI_FORCE_MICROSOFT) +config_define_if(LIBCXX_HIDE_FROM_ABI_PER_TU_BY_DEFAULT _LIBCPP_HIDE_FROM_ABI_PER_TU_BY_DEFAULT) config_define_if_not(LIBCXX_ENABLE_GLOBAL_FILESYSTEM_NAMESPACE _LIBCPP_HAS_NO_GLOBAL_FILESYSTEM_NAMESPACE) config_define_if_not(LIBCXX_ENABLE_STDIN _LIBCPP_HAS_NO_STDIN) @@ -724,6 +774,18 @@ include_directories(include) add_subdirectory(include) add_subdirectory(lib) +set(LIBCXX_TEST_DEPS "") + +if (LIBCXX_ENABLE_EXPERIMENTAL_LIBRARY) + list(APPEND LIBCXX_TEST_DEPS cxx_experimental) +endif() +if (LIBCXX_ENABLE_FILESYSTEM) + list(APPEND LIBCXX_TEST_DEPS cxx_filesystem) +endif() + +if (LIBCXX_BUILD_EXTERNAL_THREAD_LIBRARY) + list(APPEND LIBCXX_TEST_DEPS cxx_external_threads) +endif() if (LIBCXX_INCLUDE_BENCHMARKS) add_subdirectory(benchmarks) diff --git a/LICENSE.TXT b/LICENSE.TXT index c278f2c92833..190d9394d517 100644 --- a/LICENSE.TXT +++ b/LICENSE.TXT @@ -14,7 +14,7 @@ Full text of the relevant licenses is included below. University of Illinois/NCSA Open Source License -Copyright (c) 2009-2017 by the contributors listed in CREDITS.TXT +Copyright (c) 2009-2019 by the contributors listed in CREDITS.TXT All rights reserved. diff --git a/appveyor-reqs-install.cmd b/appveyor-reqs-install.cmd index a4160110aa5f..02c939ebc8c3 100644 --- a/appveyor-reqs-install.cmd +++ b/appveyor-reqs-install.cmd @@ -9,7 +9,7 @@ cd C:\projects\deps :: Setup Compiler ::########################################################################### if NOT EXIST llvm-installer.exe ( - appveyor DownloadFile http://prereleases.llvm.org/win-snapshots/LLVM-7.0.0-r325576-win32.exe -FileName llvm-installer.exe + appveyor DownloadFile https://prereleases.llvm.org/win-snapshots/LLVM-8.0.0-r345380-win32.exe -FileName llvm-installer.exe ) if "%CLANG_VERSION%"=="ToT" ( START /WAIT llvm-installer.exe /S /D=C:\"Program Files\LLVM" diff --git a/appveyor.yml b/appveyor.yml index be69a555d778..0154abbffa9d 100644 --- a/appveyor.yml +++ b/appveyor.yml @@ -19,14 +19,6 @@ environment: MAKE_PROGRAM: ninja APPVEYOR_SAVE_CACHE_ON_ERROR: true - APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2015 - CMAKE_OPTIONS: -DCMAKE_C_COMPILER=clang-cl.exe -DCMAKE_CXX_COMPILER=clang-cl.exe - CLANG_VERSION: 4 - MSVC_SETUP_PATH: C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\vcvarsall.bat - MSVC_SETUP_ARG: x86_amd64 - GENERATOR: Ninja - MAKE_PROGRAM: ninja - APPVEYOR_SAVE_CACHE_ON_ERROR: true - - APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2015 MINGW_PATH: C:\mingw-w64\i686-6.3.0-posix-dwarf-rt_v5-rev1\mingw32\bin GENERATOR: MinGW Makefiles MAKE_PROGRAM: mingw32-make diff --git a/benchmarks/CMakeLists.txt b/benchmarks/CMakeLists.txt index f557d4aea39a..3823b87b39e0 100644 --- a/benchmarks/CMakeLists.txt +++ b/benchmarks/CMakeLists.txt @@ -11,17 +11,21 @@ set(BENCHMARK_LIBCXX_COMPILE_FLAGS -isystem ${LIBCXX_SOURCE_DIR}/include -L${LIBCXX_LIBRARY_DIR} -Wl,-rpath,${LIBCXX_LIBRARY_DIR} + ${SANITIZER_FLAGS} ) if (DEFINED LIBCXX_CXX_ABI_LIBRARY_PATH) list(APPEND BENCHMARK_LIBCXX_COMPILE_FLAGS -L${LIBCXX_CXX_ABI_LIBRARY_PATH} -Wl,-rpath,${LIBCXX_CXX_ABI_LIBRARY_PATH}) endif() +if (LIBCXX_NEEDS_SITE_CONFIG) + list(APPEND BENCHMARK_LIBCXX_COMPILE_FLAGS -include "${LIBCXX_BINARY_DIR}/__config_site") +endif() split_list(BENCHMARK_LIBCXX_COMPILE_FLAGS) ExternalProject_Add(google-benchmark-libcxx EXCLUDE_FROM_ALL ON - DEPENDS cxx + DEPENDS cxx cxx-headers PREFIX benchmark-libcxx SOURCE_DIR ${LIBCXX_SOURCE_DIR}/utils/google-benchmark INSTALL_DIR ${CMAKE_CURRENT_BINARY_DIR}/benchmark-libcxx @@ -67,8 +71,19 @@ add_custom_target(cxx-benchmarks) set(BENCHMARK_OUTPUT_DIR ${CMAKE_CURRENT_BINARY_DIR}) set(BENCHMARK_LIBCXX_INSTALL ${CMAKE_CURRENT_BINARY_DIR}/benchmark-libcxx) set(BENCHMARK_NATIVE_INSTALL ${CMAKE_CURRENT_BINARY_DIR}/benchmark-native) + +check_flag_supported("-std=c++17") +mangle_name("LIBCXX_SUPPORTS_STD_EQ_c++17_FLAG" BENCHMARK_SUPPORTS_STD_CXX17_FLAG) +if (${BENCHMARK_SUPPORTS_STD_CXX17_FLAG}) + set(BENCHMARK_DIALECT_FLAG "-std=c++17") +else() + # If the compiler doesn't support -std=c++17, attempt to fall back to -std=c++1z while still + # requiring C++17 language features. + set(BENCHMARK_DIALECT_FLAG "-std=c++1z") +endif() + set(BENCHMARK_TEST_COMPILE_FLAGS - -std=c++17 -O2 + ${BENCHMARK_DIALECT_FLAG} -O2 -I${BENCHMARK_LIBCXX_INSTALL}/include -I${LIBCXX_SOURCE_DIR}/test/support ) @@ -76,11 +91,18 @@ set(BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS -nostdinc++ -isystem ${LIBCXX_SOURCE_DIR}/include ${BENCHMARK_TEST_COMPILE_FLAGS} + ${SANITIZER_FLAGS} -Wno-user-defined-literals ) +if (LIBCXX_NEEDS_SITE_CONFIG) + list(APPEND BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS + -include "${LIBCXX_BINARY_DIR}/__config_site") +endif() + set(BENCHMARK_TEST_LIBCXX_LINK_FLAGS -nodefaultlibs -L${BENCHMARK_LIBCXX_INSTALL}/lib/ + ${SANITIZER_FLAGS} ) set(BENCHMARK_TEST_NATIVE_COMPILE_FLAGS ${BENCHMARK_NATIVE_TARGET_FLAGS} @@ -95,10 +117,25 @@ split_list(BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS) split_list(BENCHMARK_TEST_LIBCXX_LINK_FLAGS) split_list(BENCHMARK_TEST_NATIVE_COMPILE_FLAGS) split_list(BENCHMARK_TEST_NATIVE_LINK_FLAGS) -macro(add_benchmark_test name source_file) + +if (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libstdc++") + find_library(LIBSTDCXX_FILESYSTEM_TEST stdc++fs + PATHS ${LIBCXX_BENCHMARK_NATIVE_GCC_TOOLCHAIN} + PATH_SUFFIXES lib lib64 + DOC "The libstdc++ filesystem library used by the benchmarks" + ) + if (NOT "${LIBSTDCXX_FILESYSTEM_TEST}" STREQUAL "LIBSTDCXX_FILESYSTEM_TEST-NOTFOUND") + set(LIBSTDCXX_FILESYSTEM_LIB "stdc++fs") + endif() +endif() + +set(libcxx_benchmark_targets) + +function(add_benchmark_test name source_file) set(libcxx_target ${name}_libcxx) + list(APPEND libcxx_benchmark_targets ${libcxx_target}) add_executable(${libcxx_target} EXCLUDE_FROM_ALL ${source_file}) - add_dependencies(${libcxx_target} cxx google-benchmark-libcxx) + add_dependencies(${libcxx_target} cxx cxx-headers google-benchmark-libcxx) add_dependencies(cxx-benchmarks ${libcxx_target}) if (LIBCXX_ENABLE_SHARED) target_link_libraries(${libcxx_target} cxx_shared) @@ -108,7 +145,13 @@ macro(add_benchmark_test name source_file) if (TARGET cxx_experimental) target_link_libraries(${libcxx_target} cxx_experimental) endif() + if (TARGET cxx_filesystem) + target_link_libraries(${libcxx_target} cxx_filesystem) + endif() target_link_libraries(${libcxx_target} -lbenchmark) + if (LLVM_USE_SANITIZER) + target_link_libraries(${libcxx_target} -ldl) + endif() set_target_properties(${libcxx_target} PROPERTIES OUTPUT_NAME "${name}.libcxx.out" @@ -116,15 +159,19 @@ macro(add_benchmark_test name source_file) COMPILE_FLAGS "${BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS}" LINK_FLAGS "${BENCHMARK_TEST_LIBCXX_LINK_FLAGS}") if (LIBCXX_BENCHMARK_NATIVE_STDLIB) + if (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libstdc++" AND NOT DEFINED LIBSTDCXX_FILESYSTEM_LIB + AND "${name}" STREQUAL "filesystem") + return() + endif() set(native_target ${name}_native) add_executable(${native_target} EXCLUDE_FROM_ALL ${source_file}) add_dependencies(${native_target} google-benchmark-native google-benchmark-libcxx) target_link_libraries(${native_target} -lbenchmark) if (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libstdc++") - target_link_libraries(${native_target} -lstdc++fs) + target_link_libraries(${native_target} ${LIBSTDCXX_FILESYSTEM_LIB}) elseif (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libc++") - target_link_libraries(${native_target} -lc++experimental) + target_link_libraries(${native_target} -lc++fs -lc++experimental) endif() if (LIBCXX_HAS_PTHREAD_LIB) target_link_libraries(${native_target} -pthread) @@ -138,7 +185,7 @@ macro(add_benchmark_test name source_file) COMPILE_FLAGS "${BENCHMARK_TEST_NATIVE_COMPILE_FLAGS}" LINK_FLAGS "${BENCHMARK_TEST_NATIVE_LINK_FLAGS}") endif() -endmacro() +endfunction() #============================================================================== @@ -155,3 +202,23 @@ foreach(test_path ${BENCHMARK_TESTS}) endif() add_benchmark_test(${test_name} ${test_file}) endforeach() + +if (LIBCXX_INCLUDE_TESTS) + include(AddLLVM) + + if (NOT DEFINED LIBCXX_TEST_DEPS) + message(FATAL_ERROR "Expected LIBCXX_TEST_DEPS to be defined") + endif() + + configure_lit_site_cfg( + ${CMAKE_CURRENT_SOURCE_DIR}/lit.site.cfg.py.in + ${CMAKE_CURRENT_BINARY_DIR}/lit.site.cfg.py) + + set(BENCHMARK_LIT_ARGS "--show-all --show-xfail --show-unsupported ${LIT_ARGS_DEFAULT}") + + add_lit_target(check-cxx-benchmarks + "Running libcxx benchmarks tests" + ${CMAKE_CURRENT_BINARY_DIR} + DEPENDS cxx-benchmarks ${LIBCXX_TEST_DEPS} + ARGS ${BENCHMARK_LIT_ARGS}) +endif() diff --git a/benchmarks/CartesianBenchmarks.hpp b/benchmarks/CartesianBenchmarks.hpp new file mode 100644 index 000000000000..88a994c55512 --- /dev/null +++ b/benchmarks/CartesianBenchmarks.hpp @@ -0,0 +1,135 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + + +#include <string> +#include <tuple> +#include <type_traits> +#include <vector> + +#include "benchmark/benchmark.h" +#include "test_macros.h" + +namespace internal { + +template <class D, class E, size_t I> +struct EnumValue : std::integral_constant<E, static_cast<E>(I)> { + static std::string name() { return std::string("_") + D::Names[I]; } +}; + +template <class D, class E, size_t ...Idxs> +constexpr auto makeEnumValueTuple(std::index_sequence<Idxs...>) { + return std::make_tuple(EnumValue<D, E, Idxs>{}...); +} + +template <class B> +static auto skip(const B& Bench, int) -> decltype(Bench.skip()) { + return Bench.skip(); +} +template <class B> +static auto skip(const B& Bench, char) { + return false; +} + +template <class B, class Args, size_t... Is> +void makeBenchmarkFromValuesImpl(const Args& A, std::index_sequence<Is...>) { + for (auto& V : A) { + B Bench{std::get<Is>(V)...}; + if (!internal::skip(Bench, 0)) { + benchmark::RegisterBenchmark(Bench.name().c_str(), + [=](benchmark::State& S) { Bench.run(S); }); + } + } +} + +template <class B, class... Args> +void makeBenchmarkFromValues(const std::vector<std::tuple<Args...> >& A) { + makeBenchmarkFromValuesImpl<B>(A, std::index_sequence_for<Args...>()); +} + +template <template <class...> class B, class Args, class... U> +void makeBenchmarkImpl(const Args& A, std::tuple<U...> t) { + makeBenchmarkFromValues<B<U...> >(A); +} + +template <template <class...> class B, class Args, class... U, + class... T, class... Tuples> +void makeBenchmarkImpl(const Args& A, std::tuple<U...>, std::tuple<T...>, + Tuples... rest) { + (internal::makeBenchmarkImpl<B>(A, std::tuple<U..., T>(), rest...), ...); +} + +template <class R, class T> +void allValueCombinations(R& Result, const T& Final) { + return Result.push_back(Final); +} + +template <class R, class T, class V, class... Vs> +void allValueCombinations(R& Result, const T& Prev, const V& Value, + const Vs&... Values) { + for (const auto& E : Value) { + allValueCombinations(Result, std::tuple_cat(Prev, std::make_tuple(E)), + Values...); + } +} + +} // namespace internal + +// CRTP class that enables using enum types as a dimension for +// makeCartesianProductBenchmark below. +// The type passed to `B` will be a std::integral_constant<E, e>, with the +// additional static function `name()` that returns the stringified name of the +// label. +// +// Eg: +// enum class MyEnum { A, B }; +// struct AllMyEnum : EnumValuesAsTuple<AllMyEnum, MyEnum, 2> { +// static constexpr absl::string_view Names[] = {"A", "B"}; +// }; +template <class Derived, class EnumType, size_t NumLabels> +using EnumValuesAsTuple = + decltype(internal::makeEnumValueTuple<Derived, EnumType>( + std::make_index_sequence<NumLabels>{})); + +// Instantiates B<T0, T1, ..., TN> where <Ti...> are the combinations in the +// cartesian product of `Tuples...`, and pass (arg0, ..., argN) as constructor +// arguments where `(argi...)` are the combination in the cartesian product of +// the runtime values of `A...`. +// B<T...> requires: +// - std::string name(args...): The name of the benchmark. +// - void run(benchmark::State&, args...): The body of the benchmark. +// It can also optionally provide: +// - bool skip(args...): When `true`, skips the combination. Default is false. +// +// Returns int to facilitate registration. The return value is unspecified. +template <template <class...> class B, class... Tuples, class... Args> +int makeCartesianProductBenchmark(const Args&... A) { + std::vector<std::tuple<typename Args::value_type...> > V; + internal::allValueCombinations(V, std::tuple<>(), A...); + internal::makeBenchmarkImpl<B>(V, std::tuple<>(), Tuples()...); + return 0; +} + +template <class B, class... Args> +int makeCartesianProductBenchmark(const Args&... A) { + std::vector<std::tuple<typename Args::value_type...> > V; + internal::allValueCombinations(V, std::tuple<>(), A...); + internal::makeBenchmarkFromValues<B>(V); + return 0; +} + +// When `opaque` is true, this function hides the runtime state of `value` from +// the optimizer. +// It returns `value`. +template <class T> +TEST_ALWAYS_INLINE inline T maybeOpaque(T value, bool opaque) { + if (opaque) benchmark::DoNotOptimize(value); + return value; +} + diff --git a/benchmarks/algorithms.bench.cpp b/benchmarks/algorithms.bench.cpp index 86315390e0d2..eee8a4da2ab0 100644 --- a/benchmarks/algorithms.bench.cpp +++ b/benchmarks/algorithms.bench.cpp @@ -1,62 +1,270 @@ -#include <unordered_set> -#include <vector> + +#include <algorithm> #include <cstdint> +#include <map> +#include <random> +#include <string> +#include <utility> +#include <vector> -#include "benchmark/benchmark.h" +#include "CartesianBenchmarks.hpp" #include "GenerateInput.hpp" +#include "benchmark/benchmark.h" +#include "test_macros.h" + +namespace { + +enum class ValueType { Uint32, String }; +struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 2> { + static constexpr const char* Names[] = {"uint32", "string"}; +}; + +template <class V> +using Value = + std::conditional_t<V() == ValueType::Uint32, uint32_t, std::string>; + +enum class Order { + Random, + Ascending, + Descending, + SingleElement, + PipeOrgan, + Heap +}; +struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> { + static constexpr const char* Names[] = {"Random", "Ascending", + "Descending", "SingleElement", + "PipeOrgan", "Heap"}; +}; + +void fillValues(std::vector<uint32_t>& V, size_t N, Order O) { + if (O == Order::SingleElement) { + V.resize(N, 0); + } else { + while (V.size() < N) + V.push_back(V.size()); + } +} + +void fillValues(std::vector<std::string>& V, size_t N, Order O) { + + if (O == Order::SingleElement) { + V.resize(N, getRandomString(1024)); + } else { + while (V.size() < N) + V.push_back(getRandomString(1024)); + } +} + +template <class T> +void sortValues(T& V, Order O) { + assert(std::is_sorted(V.begin(), V.end())); + switch (O) { + case Order::Random: { + std::random_device R; + std::mt19937 M(R()); + std::shuffle(V.begin(), V.end(), M); + break; + } + case Order::Ascending: + std::sort(V.begin(), V.end()); + break; + case Order::Descending: + std::sort(V.begin(), V.end(), std::greater<>()); + break; + case Order::SingleElement: + // Nothing to do + break; + case Order::PipeOrgan: + std::sort(V.begin(), V.end()); + std::reverse(V.begin() + V.size() / 2, V.end()); + break; + case Order::Heap: + std::make_heap(V.begin(), V.end()); + break; + } +} + +template <class ValueType> +std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N, + Order O) { + // Let's make sure that all random sequences of the same size are the same. + // That way we can compare the different algorithms with the same input. + static std::map<std::pair<size_t, Order>, std::vector<Value<ValueType> > > + Cached; -constexpr std::size_t TestNumInputs = 1024; - -template <class GenInputs> -void BM_Sort(benchmark::State& st, GenInputs gen) { - using ValueType = typename decltype(gen(0))::value_type; - const auto in = gen(st.range(0)); - std::vector<ValueType> inputs[5]; - auto reset_inputs = [&]() { - for (auto& C : inputs) { - C = in; - benchmark::DoNotOptimize(C.data()); - } - }; - reset_inputs(); - while (st.KeepRunning()) { - for (auto& I : inputs) { - std::sort(I.data(), I.data() + I.size()); - benchmark::DoNotOptimize(I.data()); - } - st.PauseTiming(); - reset_inputs(); - benchmark::ClobberMemory(); - st.ResumeTiming(); + auto& Values = Cached[{N, O}]; + if (Values.empty()) { + fillValues(Values, N, O); + sortValues(Values, O); + }; + const size_t NumCopies = std::max(size_t{1}, 1000 / N); + return { NumCopies, Values }; +} + +template <class T, class U> +TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies, + U& Orig) { + state.PauseTiming(); + for (auto& Copy : Copies) + Copy = Orig; + state.ResumeTiming(); +} + +template <class ValueType, class F> +void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O, + bool CountElements, F f) { + auto Copies = makeOrderedValues<ValueType>(Quantity, O); + const auto Orig = Copies[0]; + + const size_t Batch = CountElements ? Copies.size() * Quantity : Copies.size(); + while (state.KeepRunningBatch(Batch)) { + for (auto& Copy : Copies) { + f(Copy); + benchmark::DoNotOptimize(Copy); } + resetCopies(state, Copies, Orig); + } } -BENCHMARK_CAPTURE(BM_Sort, random_uint32, - getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs); +template <class ValueType, class Order> +struct Sort { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { + std::sort(Copy.begin(), Copy.end()); + }); + } + + bool skip() const { return Order() == ::Order::Heap; } + + std::string name() const { + return "BM_Sort" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; + +template <class ValueType, class Order> +struct StableSort { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { + std::stable_sort(Copy.begin(), Copy.end()); + }); + } + + bool skip() const { return Order() == ::Order::Heap; } + + std::string name() const { + return "BM_StableSort" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; + +template <class ValueType, class Order> +struct MakeHeap { + size_t Quantity; -BENCHMARK_CAPTURE(BM_Sort, sorted_ascending_uint32, - getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { + std::make_heap(Copy.begin(), Copy.end()); + }); + } -BENCHMARK_CAPTURE(BM_Sort, sorted_descending_uint32, - getReverseSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); + std::string name() const { + return "BM_MakeHeap" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; -BENCHMARK_CAPTURE(BM_Sort, single_element_uint32, - getDuplicateIntegerInputs<uint32_t>)->Arg(TestNumInputs); +template <class ValueType> +struct SortHeap { + size_t Quantity; -BENCHMARK_CAPTURE(BM_Sort, pipe_organ_uint32, - getPipeOrganIntegerInputs<uint32_t>)->Arg(TestNumInputs); + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>( + state, Quantity, Order::Heap, false, + [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); }); + } -BENCHMARK_CAPTURE(BM_Sort, random_strings, - getRandomStringInputs)->Arg(TestNumInputs); + std::string name() const { + return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity); + }; +}; -BENCHMARK_CAPTURE(BM_Sort, sorted_ascending_strings, - getSortedStringInputs)->Arg(TestNumInputs); +template <class ValueType, class Order> +struct MakeThenSortHeap { + size_t Quantity; -BENCHMARK_CAPTURE(BM_Sort, sorted_descending_strings, - getReverseSortedStringInputs)->Arg(TestNumInputs); + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) { + std::make_heap(Copy.begin(), Copy.end()); + std::sort_heap(Copy.begin(), Copy.end()); + }); + } -BENCHMARK_CAPTURE(BM_Sort, single_element_strings, - getDuplicateStringInputs)->Arg(TestNumInputs); + std::string name() const { + return "BM_MakeThenSortHeap" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; +template <class ValueType, class Order> +struct PushHeap { + size_t Quantity; -BENCHMARK_MAIN(); + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) { + for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) { + std::push_heap(Copy.begin(), I + 1); + } + }); + } + + bool skip() const { return Order() == ::Order::Heap; } + + std::string name() const { + return "BM_PushHeap" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; + +template <class ValueType> +struct PopHeap { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) { + for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) { + std::pop_heap(B, I); + } + }); + } + + std::string name() const { + return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity); + }; +}; + +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + const std::vector<size_t> Quantities = {1 << 0, 1 << 2, 1 << 4, 1 << 6, + 1 << 8, 1 << 10, 1 << 14, 1 << 18}; + makeCartesianProductBenchmark<Sort, AllValueTypes, AllOrders>(Quantities); + makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>( + Quantities); + makeCartesianProductBenchmark<MakeHeap, AllValueTypes, AllOrders>(Quantities); + makeCartesianProductBenchmark<SortHeap, AllValueTypes>(Quantities); + makeCartesianProductBenchmark<MakeThenSortHeap, AllValueTypes, AllOrders>( + Quantities); + makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities); + makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/benchmarks/algorithms.partition_point.bench.cpp b/benchmarks/algorithms.partition_point.bench.cpp new file mode 100644 index 000000000000..00a3bb272672 --- /dev/null +++ b/benchmarks/algorithms.partition_point.bench.cpp @@ -0,0 +1,124 @@ +#include <array> +#include <algorithm> +#include <cassert> +#include <cstdint> +#include <tuple> +#include <vector> + +#include "benchmark/benchmark.h" + +#include "CartesianBenchmarks.hpp" +#include "GenerateInput.hpp" + +namespace { + +template <typename I, typename N> +std::array<I, 10> every_10th_percentile_N(I first, N n) { + N step = n / 10; + std::array<I, 10> res; + + for (size_t i = 0; i < 10; ++i) { + res[i] = first; + std::advance(first, step); + } + + return res; +} + +template <class IntT> +struct TestIntBase { + static std::vector<IntT> generateInput(size_t size) { + std::vector<IntT> Res(size); + std::generate(Res.begin(), Res.end(), + [] { return getRandomInteger<IntT>(); }); + return Res; + } +}; + +struct TestInt32 : TestIntBase<std::int32_t> { + static constexpr const char* Name = "TestInt32"; +}; + +struct TestInt64 : TestIntBase<std::int64_t> { + static constexpr const char* Name = "TestInt64"; +}; + +struct TestUint32 : TestIntBase<std::uint32_t> { + static constexpr const char* Name = "TestUint32"; +}; + +struct TestMediumString { + static constexpr const char* Name = "TestMediumString"; + static constexpr size_t StringSize = 32; + + static std::vector<std::string> generateInput(size_t size) { + std::vector<std::string> Res(size); + std::generate(Res.begin(), Res.end(), [] { return getRandomString(StringSize); }); + return Res; + } +}; + +using AllTestTypes = std::tuple<TestInt32, TestInt64, TestUint32, TestMediumString>; + +struct LowerBoundAlg { + template <class I, class V> + I operator()(I first, I last, const V& value) const { + return std::lower_bound(first, last, value); + } + + static constexpr const char* Name = "LowerBoundAlg"; +}; + +struct UpperBoundAlg { + template <class I, class V> + I operator()(I first, I last, const V& value) const { + return std::upper_bound(first, last, value); + } + + static constexpr const char* Name = "UpperBoundAlg"; +}; + +struct EqualRangeAlg { + template <class I, class V> + std::pair<I, I> operator()(I first, I last, const V& value) const { + return std::equal_range(first, last, value); + } + + static constexpr const char* Name = "EqualRangeAlg"; +}; + +using AllAlgs = std::tuple<LowerBoundAlg, UpperBoundAlg, EqualRangeAlg>; + +template <class Alg, class TestType> +struct PartitionPointBench { + size_t Quantity; + + std::string name() const { + return std::string("PartitionPointBench_") + Alg::Name + "_" + + TestType::Name + '/' + std::to_string(Quantity); + } + + void run(benchmark::State& state) const { + auto Data = TestType::generateInput(Quantity); + std::sort(Data.begin(), Data.end()); + auto Every10Percentile = every_10th_percentile_N(Data.begin(), Data.size()); + + for (auto _ : state) { + for (auto Test : Every10Percentile) + benchmark::DoNotOptimize(Alg{}(Data.begin(), Data.end(), *Test)); + } + } +}; + +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + const std::vector<size_t> Quantities = {1 << 8, 1 << 10, 1 << 20}; + makeCartesianProductBenchmark<PartitionPointBench, AllAlgs, AllTestTypes>( + Quantities); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/benchmarks/function.bench.cpp b/benchmarks/function.bench.cpp new file mode 100644 index 000000000000..4f0e1fd80fa3 --- /dev/null +++ b/benchmarks/function.bench.cpp @@ -0,0 +1,232 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include <cstdint> +#include <functional> +#include <memory> +#include <string> + +#include "CartesianBenchmarks.hpp" +#include "benchmark/benchmark.h" +#include "test_macros.h" + +namespace { + +enum class FunctionType { + Null, + FunctionPointer, + MemberFunctionPointer, + MemberPointer, + SmallTrivialFunctor, + SmallNonTrivialFunctor, + LargeTrivialFunctor, + LargeNonTrivialFunctor +}; + +struct AllFunctionTypes : EnumValuesAsTuple<AllFunctionTypes, FunctionType, 8> { + static constexpr const char* Names[] = {"Null", + "FuncPtr", + "MemFuncPtr", + "MemPtr", + "SmallTrivialFunctor", + "SmallNonTrivialFunctor", + "LargeTrivialFunctor", + "LargeNonTrivialFunctor"}; +}; + +enum class Opacity { kOpaque, kTransparent }; + +struct AllOpacity : EnumValuesAsTuple<AllOpacity, Opacity, 2> { + static constexpr const char* Names[] = {"Opaque", "Transparent"}; +}; + +struct S { + int function() const { return 0; } + int field = 0; +}; + +int FunctionWithS(const S*) { return 0; } + +struct SmallTrivialFunctor { + int operator()(const S*) const { return 0; } +}; +struct SmallNonTrivialFunctor { + SmallNonTrivialFunctor() {} + SmallNonTrivialFunctor(const SmallNonTrivialFunctor&) {} + ~SmallNonTrivialFunctor() {} + int operator()(const S*) const { return 0; } +}; +struct LargeTrivialFunctor { + LargeTrivialFunctor() { + // Do not spend time initializing the padding. + } + int padding[16]; + int operator()(const S*) const { return 0; } +}; +struct LargeNonTrivialFunctor { + int padding[16]; + LargeNonTrivialFunctor() { + // Do not spend time initializing the padding. + } + LargeNonTrivialFunctor(const LargeNonTrivialFunctor&) {} + ~LargeNonTrivialFunctor() {} + int operator()(const S*) const { return 0; } +}; + +using Function = std::function<int(const S*)>; + +TEST_ALWAYS_INLINE +inline Function MakeFunction(FunctionType type, bool opaque = false) { + switch (type) { + case FunctionType::Null: + return nullptr; + case FunctionType::FunctionPointer: + return maybeOpaque(FunctionWithS, opaque); + case FunctionType::MemberFunctionPointer: + return maybeOpaque(&S::function, opaque); + case FunctionType::MemberPointer: + return maybeOpaque(&S::field, opaque); + case FunctionType::SmallTrivialFunctor: + return maybeOpaque(SmallTrivialFunctor{}, opaque); + case FunctionType::SmallNonTrivialFunctor: + return maybeOpaque(SmallNonTrivialFunctor{}, opaque); + case FunctionType::LargeTrivialFunctor: + return maybeOpaque(LargeTrivialFunctor{}, opaque); + case FunctionType::LargeNonTrivialFunctor: + return maybeOpaque(LargeNonTrivialFunctor{}, opaque); + } +} + +template <class Opacity, class FunctionType> +struct ConstructAndDestroy { + static void run(benchmark::State& state) { + for (auto _ : state) { + if (Opacity() == ::Opacity::kOpaque) { + benchmark::DoNotOptimize(MakeFunction(FunctionType(), true)); + } else { + MakeFunction(FunctionType()); + } + } + } + + static std::string name() { + return "BM_ConstructAndDestroy" + FunctionType::name() + Opacity::name(); + } +}; + +template <class FunctionType> +struct Copy { + static void run(benchmark::State& state) { + auto value = MakeFunction(FunctionType()); + for (auto _ : state) { + benchmark::DoNotOptimize(value); + auto copy = value; // NOLINT + benchmark::DoNotOptimize(copy); + } + } + + static std::string name() { return "BM_Copy" + FunctionType::name(); } +}; + +template <class FunctionType> +struct Move { + static void run(benchmark::State& state) { + Function values[2] = {MakeFunction(FunctionType())}; + int i = 0; + for (auto _ : state) { + benchmark::DoNotOptimize(values); + benchmark::DoNotOptimize(values[i ^ 1] = std::move(values[i])); + i ^= 1; + } + } + + static std::string name() { + return "BM_Move" + FunctionType::name(); + } +}; + +template <class Function1, class Function2> +struct Swap { + static void run(benchmark::State& state) { + Function values[2] = {MakeFunction(Function1()), MakeFunction(Function2())}; + for (auto _ : state) { + benchmark::DoNotOptimize(values); + values[0].swap(values[1]); + } + } + + static bool skip() { return Function1() > Function2(); } + + static std::string name() { + return "BM_Swap" + Function1::name() + Function2::name(); + } +}; + +template <class FunctionType> +struct OperatorBool { + static void run(benchmark::State& state) { + auto f = MakeFunction(FunctionType()); + for (auto _ : state) { + benchmark::DoNotOptimize(f); + benchmark::DoNotOptimize(static_cast<bool>(f)); + } + } + + static std::string name() { return "BM_OperatorBool" + FunctionType::name(); } +}; + +template <class FunctionType> +struct Invoke { + static void run(benchmark::State& state) { + S s; + const auto value = MakeFunction(FunctionType()); + for (auto _ : state) { + benchmark::DoNotOptimize(value); + benchmark::DoNotOptimize(value(&s)); + } + } + + static bool skip() { return FunctionType() == ::FunctionType::Null; } + + static std::string name() { return "BM_Invoke" + FunctionType::name(); } +}; + +template <class FunctionType> +struct InvokeInlined { + static void run(benchmark::State& state) { + S s; + for (auto _ : state) { + MakeFunction(FunctionType())(&s); + } + } + + static bool skip() { return FunctionType() == ::FunctionType::Null; } + + static std::string name() { + return "BM_InvokeInlined" + FunctionType::name(); + } +}; + +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + makeCartesianProductBenchmark<ConstructAndDestroy, AllOpacity, + AllFunctionTypes>(); + makeCartesianProductBenchmark<Copy, AllFunctionTypes>(); + makeCartesianProductBenchmark<Move, AllFunctionTypes>(); + makeCartesianProductBenchmark<Swap, AllFunctionTypes, AllFunctionTypes>(); + makeCartesianProductBenchmark<OperatorBool, AllFunctionTypes>(); + makeCartesianProductBenchmark<Invoke, AllFunctionTypes>(); + makeCartesianProductBenchmark<InvokeInlined, AllFunctionTypes>(); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/benchmarks/lit.cfg.py b/benchmarks/lit.cfg.py new file mode 100644 index 000000000000..84857d570d7a --- /dev/null +++ b/benchmarks/lit.cfg.py @@ -0,0 +1,23 @@ +# -*- Python -*- vim: set ft=python ts=4 sw=4 expandtab tw=79: +# Configuration file for the 'lit' test runner. +import os +import site + +site.addsitedir(os.path.join(os.path.dirname(os.path.dirname(__file__)), 'utils')) +from libcxx.test.googlebenchmark import GoogleBenchmark + +# Tell pylint that we know config and lit_config exist somewhere. +if 'PYLINT_IMPORT' in os.environ: + config = object() + lit_config = object() + +# name: The name of this test suite. +config.name = 'libc++ benchmarks' +config.suffixes = [] + +config.test_exec_root = os.path.join(config.libcxx_obj_root, 'benchmarks') +config.test_source_root = config.test_exec_root + +config.test_format = GoogleBenchmark(test_sub_dirs='.', + test_suffix='.libcxx.out', + benchmark_args=config.benchmark_args)
\ No newline at end of file diff --git a/benchmarks/lit.site.cfg.py.in b/benchmarks/lit.site.cfg.py.in new file mode 100644 index 000000000000..e3ce8b22263e --- /dev/null +++ b/benchmarks/lit.site.cfg.py.in @@ -0,0 +1,10 @@ +@LIT_SITE_CFG_IN_HEADER@ + +import sys + +config.libcxx_src_root = "@LIBCXX_SOURCE_DIR@" +config.libcxx_obj_root = "@LIBCXX_BINARY_DIR@" +config.benchmark_args = "@LIBCXX_BENCHMARK_TEST_ARGS@".split(';') + +# Let the main config do the real work. +lit_config.load_config(config, "@LIBCXX_SOURCE_DIR@/benchmarks/lit.cfg.py")
\ No newline at end of file diff --git a/benchmarks/ordered_set.bench.cpp b/benchmarks/ordered_set.bench.cpp new file mode 100644 index 000000000000..b2ef0725b7ba --- /dev/null +++ b/benchmarks/ordered_set.bench.cpp @@ -0,0 +1,249 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include <algorithm> +#include <cstdint> +#include <memory> +#include <random> +#include <set> +#include <string> +#include <vector> + +#include "CartesianBenchmarks.hpp" +#include "benchmark/benchmark.h" +#include "test_macros.h" + +namespace { + +enum class HitType { Hit, Miss }; + +struct AllHitTypes : EnumValuesAsTuple<AllHitTypes, HitType, 2> { + static constexpr const char* Names[] = {"Hit", "Miss"}; +}; + +enum class AccessPattern { Ordered, Random }; + +struct AllAccessPattern + : EnumValuesAsTuple<AllAccessPattern, AccessPattern, 2> { + static constexpr const char* Names[] = {"Ordered", "Random"}; +}; + +void sortKeysBy(std::vector<uint64_t>& Keys, AccessPattern AP) { + if (AP == AccessPattern::Random) { + std::random_device R; + std::mt19937 M(R()); + std::shuffle(std::begin(Keys), std::end(Keys), M); + } +} + +struct TestSets { + std::vector<std::set<uint64_t> > Sets; + std::vector<uint64_t> Keys; +}; + +TestSets makeTestingSets(size_t TableSize, size_t NumTables, HitType Hit, + AccessPattern Access) { + TestSets R; + R.Sets.resize(1); + + for (uint64_t I = 0; I < TableSize; ++I) { + R.Sets[0].insert(2 * I); + R.Keys.push_back(Hit == HitType::Hit ? 2 * I : 2 * I + 1); + } + R.Sets.resize(NumTables, R.Sets[0]); + sortKeysBy(R.Keys, Access); + + return R; +} + +struct Base { + size_t TableSize; + size_t NumTables; + Base(size_t T, size_t N) : TableSize(T), NumTables(N) {} + + bool skip() const { + size_t Total = TableSize * NumTables; + return Total < 100 || Total > 1000000; + } + + std::string baseName() const { + return "_TableSize" + std::to_string(TableSize) + "_NumTables" + + std::to_string(NumTables); + } +}; + +template <class Access> +struct Create : Base { + using Base::Base; + + void run(benchmark::State& State) const { + std::vector<uint64_t> Keys(TableSize); + std::iota(Keys.begin(), Keys.end(), uint64_t{0}); + sortKeysBy(Keys, Access()); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + std::vector<std::set<uint64_t>> Sets(NumTables); + for (auto K : Keys) { + for (auto& Set : Sets) { + benchmark::DoNotOptimize(Set.insert(K)); + } + } + } + } + + std::string name() const { + return "BM_Create" + Access::name() + baseName(); + } +}; + +template <class Hit, class Access> +struct Find : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access()); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto K : Data.Keys) { + for (auto& Set : Data.Sets) { + benchmark::DoNotOptimize(Set.find(K)); + } + } + } + } + + std::string name() const { + return "BM_Find" + Hit::name() + Access::name() + baseName(); + } +}; + +template <class Hit, class Access> +struct FindNeEnd : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access()); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto K : Data.Keys) { + for (auto& Set : Data.Sets) { + benchmark::DoNotOptimize(Set.find(K) != Set.end()); + } + } + } + } + + std::string name() const { + return "BM_FindNeEnd" + Hit::name() + Access::name() + baseName(); + } +}; + +template <class Access> +struct InsertHit : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, HitType::Hit, Access()); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto K : Data.Keys) { + for (auto& Set : Data.Sets) { + benchmark::DoNotOptimize(Set.insert(K)); + } + } + } + } + + std::string name() const { + return "BM_InsertHit" + Access::name() + baseName(); + } +}; + +template <class Access> +struct InsertMissAndErase : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, Access()); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto K : Data.Keys) { + for (auto& Set : Data.Sets) { + benchmark::DoNotOptimize(Set.erase(Set.insert(K).first)); + } + } + } + } + + std::string name() const { + return "BM_InsertMissAndErase" + Access::name() + baseName(); + } +}; + +struct IterateRangeFor : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, + AccessPattern::Ordered); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto& Set : Data.Sets) { + for (auto& V : Set) { + benchmark::DoNotOptimize(V); + } + } + } + } + + std::string name() const { return "BM_IterateRangeFor" + baseName(); } +}; + +struct IterateBeginEnd : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, + AccessPattern::Ordered); + + while (State.KeepRunningBatch(TableSize * NumTables)) { + for (auto& Set : Data.Sets) { + for (auto it = Set.begin(); it != Set.end(); ++it) { + benchmark::DoNotOptimize(*it); + } + } + } + } + + std::string name() const { return "BM_IterateBeginEnd" + baseName(); } +}; + +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + const std::vector<size_t> TableSize{1, 10, 100, 1000, 10000, 100000, 1000000}; + const std::vector<size_t> NumTables{1, 10, 100, 1000, 10000, 100000, 1000000}; + + makeCartesianProductBenchmark<Create, AllAccessPattern>(TableSize, NumTables); + makeCartesianProductBenchmark<Find, AllHitTypes, AllAccessPattern>( + TableSize, NumTables); + makeCartesianProductBenchmark<FindNeEnd, AllHitTypes, AllAccessPattern>( + TableSize, NumTables); + makeCartesianProductBenchmark<InsertHit, AllAccessPattern>( + TableSize, NumTables); + makeCartesianProductBenchmark<InsertMissAndErase, AllAccessPattern>( + TableSize, NumTables); + makeCartesianProductBenchmark<IterateRangeFor>(TableSize, NumTables); + makeCartesianProductBenchmark<IterateBeginEnd>(TableSize, NumTables); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/benchmarks/string.bench.cpp b/benchmarks/string.bench.cpp index 8a09e738d9b6..b8f97e6e2c12 100644 --- a/benchmarks/string.bench.cpp +++ b/benchmarks/string.bench.cpp @@ -1,9 +1,12 @@ -#include <unordered_set> -#include <vector> + #include <cstdint> +#include <new> +#include <vector> -#include "benchmark/benchmark.h" +#include "CartesianBenchmarks.hpp" #include "GenerateInput.hpp" +#include "benchmark/benchmark.h" +#include "test_macros.h" constexpr std::size_t MAX_STRING_LEN = 8 << 14; @@ -11,7 +14,7 @@ constexpr std::size_t MAX_STRING_LEN = 8 << 14; static void BM_StringFindNoMatch(benchmark::State &state) { std::string s1(state.range(0), '-'); std::string s2(8, '*'); - while (state.KeepRunning()) + for (auto _ : state) benchmark::DoNotOptimize(s1.find(s2)); } BENCHMARK(BM_StringFindNoMatch)->Range(10, MAX_STRING_LEN); @@ -20,7 +23,7 @@ BENCHMARK(BM_StringFindNoMatch)->Range(10, MAX_STRING_LEN); static void BM_StringFindAllMatch(benchmark::State &state) { std::string s1(MAX_STRING_LEN, '-'); std::string s2(state.range(0), '-'); - while (state.KeepRunning()) + for (auto _ : state) benchmark::DoNotOptimize(s1.find(s2)); } BENCHMARK(BM_StringFindAllMatch)->Range(1, MAX_STRING_LEN); @@ -30,7 +33,7 @@ static void BM_StringFindMatch1(benchmark::State &state) { std::string s1(MAX_STRING_LEN / 2, '*'); s1 += std::string(state.range(0), '-'); std::string s2(state.range(0), '-'); - while (state.KeepRunning()) + for (auto _ : state) benchmark::DoNotOptimize(s1.find(s2)); } BENCHMARK(BM_StringFindMatch1)->Range(1, MAX_STRING_LEN / 4); @@ -41,30 +44,332 @@ static void BM_StringFindMatch2(benchmark::State &state) { s1 += std::string(state.range(0), '-'); s1 += std::string(state.range(0), '*'); std::string s2(state.range(0), '-'); - while (state.KeepRunning()) + for (auto _ : state) benchmark::DoNotOptimize(s1.find(s2)); } BENCHMARK(BM_StringFindMatch2)->Range(1, MAX_STRING_LEN / 4); static void BM_StringCtorDefault(benchmark::State &state) { - while (state.KeepRunning()) { - for (unsigned I=0; I < 1000; ++I) { - std::string Default; - benchmark::DoNotOptimize(Default.c_str()); - } + for (auto _ : state) { + std::string Default; + benchmark::DoNotOptimize(Default); } } BENCHMARK(BM_StringCtorDefault); -static void BM_StringCtorCStr(benchmark::State &state) { - std::string Input = getRandomString(state.range(0)); - const char *Str = Input.c_str(); - benchmark::DoNotOptimize(Str); - while (state.KeepRunning()) { - std::string Tmp(Str); - benchmark::DoNotOptimize(Tmp.c_str()); +enum class Length { Empty, Small, Large, Huge }; +struct AllLengths : EnumValuesAsTuple<AllLengths, Length, 4> { + static constexpr const char* Names[] = {"Empty", "Small", "Large", "Huge"}; +}; + +enum class Opacity { Opaque, Transparent }; +struct AllOpacity : EnumValuesAsTuple<AllOpacity, Opacity, 2> { + static constexpr const char* Names[] = {"Opaque", "Transparent"}; +}; + +enum class DiffType { Control, ChangeFirst, ChangeMiddle, ChangeLast }; +struct AllDiffTypes : EnumValuesAsTuple<AllDiffTypes, DiffType, 4> { + static constexpr const char* Names[] = {"Control", "ChangeFirst", + "ChangeMiddle", "ChangeLast"}; +}; + +TEST_ALWAYS_INLINE const char* getSmallString(DiffType D) { + switch (D) { + case DiffType::Control: + return "0123456"; + case DiffType::ChangeFirst: + return "-123456"; + case DiffType::ChangeMiddle: + return "012-456"; + case DiffType::ChangeLast: + return "012345-"; + } +} + +TEST_ALWAYS_INLINE const char* getLargeString(DiffType D) { +#define LARGE_STRING_FIRST "123456789012345678901234567890" +#define LARGE_STRING_SECOND "234567890123456789012345678901" + switch (D) { + case DiffType::Control: + return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2"; + case DiffType::ChangeFirst: + return "-" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2"; + case DiffType::ChangeMiddle: + return "0" LARGE_STRING_FIRST "-" LARGE_STRING_SECOND "2"; + case DiffType::ChangeLast: + return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "-"; + } +} + +TEST_ALWAYS_INLINE const char* getHugeString(DiffType D) { +#define HUGE_STRING0 "0123456789" +#define HUGE_STRING1 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0 +#define HUGE_STRING2 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1 +#define HUGE_STRING3 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2 +#define HUGE_STRING4 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3 + switch (D) { + case DiffType::Control: + return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789"; + case DiffType::ChangeFirst: + return "-123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789"; + case DiffType::ChangeMiddle: + return "0123456789" HUGE_STRING4 "01234-6789" HUGE_STRING4 "0123456789"; + case DiffType::ChangeLast: + return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "012345678-"; + } +} + +TEST_ALWAYS_INLINE std::string makeString(Length L, + DiffType D = DiffType::Control, + Opacity O = Opacity::Transparent) { + switch (L) { + case Length::Empty: + return maybeOpaque("", O == Opacity::Opaque); + case Length::Small: + return maybeOpaque(getSmallString(D), O == Opacity::Opaque); + case Length::Large: + return maybeOpaque(getLargeString(D), O == Opacity::Opaque); + case Length::Huge: + return maybeOpaque(getHugeString(D), O == Opacity::Opaque); + } +} + +template <class Length, class Opaque> +struct StringConstructDestroyCStr { + static void run(benchmark::State& state) { + for (auto _ : state) { + benchmark::DoNotOptimize( + makeString(Length(), DiffType::Control, Opaque())); + } + } + + static std::string name() { + return "BM_StringConstructDestroyCStr" + Length::name() + Opaque::name(); + } +}; + +template <class Length, bool MeasureCopy, bool MeasureDestroy> +static void StringCopyAndDestroy(benchmark::State& state) { + static constexpr size_t NumStrings = 1024; + auto Orig = makeString(Length()); + std::aligned_storage<sizeof(std::string)>::type Storage[NumStrings]; + + while (state.KeepRunningBatch(NumStrings)) { + if (!MeasureCopy) + state.PauseTiming(); + for (size_t I = 0; I < NumStrings; ++I) { + ::new (static_cast<void*>(Storage + I)) std::string(Orig); + } + if (!MeasureCopy) + state.ResumeTiming(); + if (!MeasureDestroy) + state.PauseTiming(); + for (size_t I = 0; I < NumStrings; ++I) { + using S = std::string; + reinterpret_cast<S*>(Storage + I)->~S(); + } + if (!MeasureDestroy) + state.ResumeTiming(); + } +} + +template <class Length> +struct StringCopy { + static void run(benchmark::State& state) { + StringCopyAndDestroy<Length, true, false>(state); + } + + static std::string name() { return "BM_StringCopy" + Length::name(); } +}; + +template <class Length> +struct StringDestroy { + static void run(benchmark::State& state) { + StringCopyAndDestroy<Length, false, true>(state); + } + + static std::string name() { return "BM_StringDestroy" + Length::name(); } +}; + +template <class Length> +struct StringMove { + static void run(benchmark::State& state) { + // Keep two object locations and move construct back and forth. + std::aligned_storage<sizeof(std::string), alignof(std::string)>::type Storage[2]; + using S = std::string; + size_t I = 0; + S *newS = new (static_cast<void*>(Storage)) std::string(makeString(Length())); + for (auto _ : state) { + // Switch locations. + I ^= 1; + benchmark::DoNotOptimize(Storage); + // Move construct into the new location, + S *tmpS = new (static_cast<void*>(Storage + I)) S(std::move(*newS)); + // then destroy the old one. + newS->~S(); + newS = tmpS; + } + newS->~S(); + } + + static std::string name() { return "BM_StringMove" + Length::name(); } +}; + +enum class Relation { Eq, Less, Compare }; +struct AllRelations : EnumValuesAsTuple<AllRelations, Relation, 3> { + static constexpr const char* Names[] = {"Eq", "Less", "Compare"}; +}; + +template <class Rel, class LHLength, class RHLength, class DiffType> +struct StringRelational { + static void run(benchmark::State& state) { + auto Lhs = makeString(RHLength()); + auto Rhs = makeString(LHLength(), DiffType()); + for (auto _ : state) { + benchmark::DoNotOptimize(Lhs); + benchmark::DoNotOptimize(Rhs); + switch (Rel()) { + case Relation::Eq: + benchmark::DoNotOptimize(Lhs == Rhs); + break; + case Relation::Less: + benchmark::DoNotOptimize(Lhs < Rhs); + break; + case Relation::Compare: + benchmark::DoNotOptimize(Lhs.compare(Rhs)); + break; + } + } + } + + static bool skip() { + // Eq is commutative, so skip half the matrix. + if (Rel() == Relation::Eq && LHLength() > RHLength()) + return true; + // We only care about control when the lengths differ. + if (LHLength() != RHLength() && DiffType() != ::DiffType::Control) + return true; + // For empty, only control matters. + if (LHLength() == Length::Empty && DiffType() != ::DiffType::Control) + return true; + return false; + } + + static std::string name() { + return "BM_StringRelational" + Rel::name() + LHLength::name() + + RHLength::name() + DiffType::name(); + } +}; + +enum class Depth { Shallow, Deep }; +struct AllDepths : EnumValuesAsTuple<AllDepths, Depth, 2> { + static constexpr const char* Names[] = {"Shallow", "Deep"}; +}; + +enum class Temperature { Hot, Cold }; +struct AllTemperatures : EnumValuesAsTuple<AllTemperatures, Temperature, 2> { + static constexpr const char* Names[] = {"Hot", "Cold"}; +}; + +template <class Temperature, class Depth, class Length> +struct StringRead { + void run(benchmark::State& state) const { + static constexpr size_t NumStrings = + Temperature() == ::Temperature::Hot + ? 1 << 10 + : /* Enough strings to overflow the cache */ 1 << 20; + static_assert((NumStrings & (NumStrings - 1)) == 0, + "NumStrings should be a power of two to reduce overhead."); + + std::vector<std::string> Values(NumStrings, makeString(Length())); + size_t I = 0; + for (auto _ : state) { + // Jump long enough to defeat cache locality, and use a value that is + // coprime with NumStrings to ensure we visit every element. + I = (I + 17) % NumStrings; + const auto& V = Values[I]; + + // Read everything first. Escaping data() through DoNotOptimize might + // cause the compiler to have to recalculate information about `V` due to + // aliasing. + const char* const Data = V.data(); + const size_t Size = V.size(); + benchmark::DoNotOptimize(Data); + benchmark::DoNotOptimize(Size); + if (Depth() == ::Depth::Deep) { + // Read into the payload. This mainly shows the benefit of SSO when the + // data is cold. + benchmark::DoNotOptimize(*Data); + } + } + } + + static bool skip() { + // Huge does not give us anything that Large doesn't have. Skip it. + if (Length() == ::Length::Huge) { + return true; + } + return false; + } + + std::string name() const { + return "BM_StringRead" + Temperature::name() + Depth::name() + + Length::name(); + } +}; + +void sanityCheckGeneratedStrings() { + for (auto Lhs : {Length::Empty, Length::Small, Length::Large, Length::Huge}) { + const auto LhsString = makeString(Lhs); + for (auto Rhs : + {Length::Empty, Length::Small, Length::Large, Length::Huge}) { + if (Lhs > Rhs) + continue; + const auto RhsString = makeString(Rhs); + + // The smaller one must be a prefix of the larger one. + if (RhsString.find(LhsString) != 0) { + fprintf(stderr, "Invalid autogenerated strings for sizes (%d,%d).\n", + static_cast<int>(Lhs), static_cast<int>(Rhs)); + std::abort(); + } + } + } + // Verify the autogenerated diffs + for (auto L : {Length::Small, Length::Large, Length::Huge}) { + const auto Control = makeString(L); + const auto Verify = [&](std::string Exp, size_t Pos) { + // Only change on the Pos char. + if (Control[Pos] != Exp[Pos]) { + Exp[Pos] = Control[Pos]; + if (Control == Exp) + return; + } + fprintf(stderr, "Invalid autogenerated diff with size %d\n", + static_cast<int>(L)); + std::abort(); + }; + Verify(makeString(L, DiffType::ChangeFirst), 0); + Verify(makeString(L, DiffType::ChangeMiddle), Control.size() / 2); + Verify(makeString(L, DiffType::ChangeLast), Control.size() - 1); } } -BENCHMARK(BM_StringCtorCStr)->Arg(1)->Arg(8)->Range(16, MAX_STRING_LEN / 4); -BENCHMARK_MAIN(); +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + sanityCheckGeneratedStrings(); + + makeCartesianProductBenchmark<StringConstructDestroyCStr, AllLengths, + AllOpacity>(); + makeCartesianProductBenchmark<StringCopy, AllLengths>(); + makeCartesianProductBenchmark<StringMove, AllLengths>(); + makeCartesianProductBenchmark<StringDestroy, AllLengths>(); + makeCartesianProductBenchmark<StringRelational, AllRelations, AllLengths, + AllLengths, AllDiffTypes>(); + makeCartesianProductBenchmark<StringRead, AllTemperatures, AllDepths, + AllLengths>(); + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/benchmarks/stringstream.bench.cpp b/benchmarks/stringstream.bench.cpp index 75a7a284e072..828ef4b405f4 100644 --- a/benchmarks/stringstream.bench.cpp +++ b/benchmarks/stringstream.bench.cpp @@ -1,7 +1,9 @@ #include "benchmark/benchmark.h" +#include "test_macros.h" #include <sstream> -double __attribute__((noinline)) istream_numbers(); + +TEST_NOINLINE double istream_numbers(); double istream_numbers() { const char *a[] = { diff --git a/benchmarks/unordered_set_operations.bench.cpp b/benchmarks/unordered_set_operations.bench.cpp index ee0ea29b8d21..1fee6d362c41 100644 --- a/benchmarks/unordered_set_operations.bench.cpp +++ b/benchmarks/unordered_set_operations.bench.cpp @@ -9,25 +9,26 @@ #include "ContainerBenchmarks.hpp" #include "GenerateInput.hpp" +#include "test_macros.h" using namespace ContainerBenchmarks; constexpr std::size_t TestNumInputs = 1024; template <class _Size> -inline __attribute__((__always_inline__)) +inline TEST_ALWAYS_INLINE _Size loadword(const void* __p) { _Size __r; std::memcpy(&__r, __p, sizeof(__r)); return __r; } -inline __attribute__((__always_inline__)) +inline TEST_ALWAYS_INLINE std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) { return (__val >> __shift) | (__val << (64 - __shift)); } -inline __attribute__((__always_inline__)) +inline TEST_ALWAYS_INLINE std::size_t hash_len_16(std::size_t __u, std::size_t __v) { const std::size_t __mul = 0x9ddfea08eb382d69ULL; std::size_t __a = (__u ^ __v) * __mul; @@ -40,7 +41,7 @@ std::size_t hash_len_16(std::size_t __u, std::size_t __v) { template <std::size_t _Len> -inline __attribute__((__always_inline__)) +inline TEST_ALWAYS_INLINE std::size_t hash_len_0_to_8(const char* __s) { static_assert(_Len == 4 || _Len == 8, ""); const uint64_t __a = loadword<uint32_t>(__s); @@ -50,7 +51,7 @@ std::size_t hash_len_0_to_8(const char* __s) { struct UInt32Hash { UInt32Hash() = default; - inline __attribute__((__always_inline__)) + inline TEST_ALWAYS_INLINE std::size_t operator()(uint32_t data) const { return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data)); } @@ -58,7 +59,7 @@ struct UInt32Hash { struct UInt64Hash { UInt64Hash() = default; - inline __attribute__((__always_inline__)) + inline TEST_ALWAYS_INLINE std::size_t operator()(uint64_t data) const { return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data)); } @@ -66,7 +67,7 @@ struct UInt64Hash { struct UInt128Hash { UInt128Hash() = default; - inline __attribute__((__always_inline__)) + inline TEST_ALWAYS_INLINE std::size_t operator()(__uint128_t data) const { const __uint128_t __mask = static_cast<std::size_t>(-1); const std::size_t __a = (std::size_t)(data & __mask); @@ -77,7 +78,7 @@ struct UInt128Hash { struct UInt32Hash2 { UInt32Hash2() = default; - inline __attribute__((__always_inline__)) + inline TEST_ALWAYS_INLINE std::size_t operator()(uint32_t data) const { const uint32_t __m = 0x5bd1e995; const uint32_t __r = 24; @@ -97,7 +98,7 @@ struct UInt32Hash2 { struct UInt64Hash2 { UInt64Hash2() = default; - inline __attribute__((__always_inline__)) + inline TEST_ALWAYS_INLINE std::size_t operator()(uint64_t data) const { return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data)); } diff --git a/cmake/Modules/HandleCompilerRT.cmake b/cmake/Modules/HandleCompilerRT.cmake index 2e0e69e5e085..1ce256574941 100644 --- a/cmake/Modules/HandleCompilerRT.cmake +++ b/cmake/Modules/HandleCompilerRT.cmake @@ -8,6 +8,9 @@ function(find_compiler_rt_library name dest) if (CMAKE_CXX_COMPILER_ID MATCHES Clang AND CMAKE_CXX_COMPILER_TARGET) list(APPEND CLANG_COMMAND "--target=${CMAKE_CXX_COMPILER_TARGET}") endif() + get_property(LIBCXX_CXX_FLAGS CACHE CMAKE_CXX_FLAGS PROPERTY VALUE) + string(REPLACE " " ";" LIBCXX_CXX_FLAGS "${LIBCXX_CXX_FLAGS}") + list(APPEND CLANG_COMMAND ${LIBCXX_CXX_FLAGS}) execute_process( COMMAND ${CLANG_COMMAND} RESULT_VARIABLE HAD_ERROR diff --git a/cmake/Modules/HandleLibCXXABI.cmake b/cmake/Modules/HandleLibCXXABI.cmake index ef3b4f5dde22..1c19d7e01af7 100644 --- a/cmake/Modules/HandleLibCXXABI.cmake +++ b/cmake/Modules/HandleLibCXXABI.cmake @@ -41,7 +41,7 @@ macro(setup_abi_lib abidefines abilib abifiles abidirs) get_filename_component(ifile ${fpath} NAME) set(src ${incpath}/${fpath}) - set(dst ${LIBCXX_BINARY_INCLUDE_DIR}/${dstdir}/${fpath}) + set(dst ${LIBCXX_BINARY_INCLUDE_DIR}/${dstdir}/${ifile}) add_custom_command(OUTPUT ${dst} DEPENDS ${src} COMMAND ${CMAKE_COMMAND} -E copy_if_different ${src} ${dst} diff --git a/cmake/Modules/HandleLibcxxFlags.cmake b/cmake/Modules/HandleLibcxxFlags.cmake index 65f7d187f3bd..fb60318a330d 100644 --- a/cmake/Modules/HandleLibcxxFlags.cmake +++ b/cmake/Modules/HandleLibcxxFlags.cmake @@ -16,6 +16,7 @@ macro(mangle_name str output) string(REGEX REPLACE "^-+" "" strippedStr "${strippedStr}") string(REGEX REPLACE "-+$" "" strippedStr "${strippedStr}") string(REPLACE "-" "_" strippedStr "${strippedStr}") + string(REPLACE ":" "_COLON_" strippedStr "${strippedStr}") string(REPLACE "=" "_EQ_" strippedStr "${strippedStr}") string(REPLACE "+" "X" strippedStr "${strippedStr}") string(TOUPPER "${strippedStr}" ${output}) @@ -44,6 +45,29 @@ macro(check_flag_supported flag) check_cxx_compiler_flag("${flag}" "LIBCXX_SUPPORTS_${flagname}_FLAG") endmacro() +macro(append_flags DEST) + foreach(value ${ARGN}) + list(APPEND ${DEST} ${value}) + list(APPEND ${DEST} ${value}) + endforeach() +endmacro() + +# If the specified 'condition' is true then append the specified list of flags to DEST +macro(append_flags_if condition DEST) + if (${condition}) + list(APPEND ${DEST} ${ARGN}) + endif() +endmacro() + +# Add each flag in the list specified by DEST if that flag is supported by the current compiler. +macro(append_flags_if_supported DEST) + foreach(flag ${ARGN}) + mangle_name("${flag}" flagname) + check_cxx_compiler_flag("${flag}" "LIBCXX_SUPPORTS_${flagname}_FLAG") + append_flags_if(LIBCXX_SUPPORTS_${flagname}_FLAG ${DEST} ${flag}) + endforeach() +endmacro() + # Add a macro definition if condition is true. macro(define_if condition def) if (${condition}) diff --git a/docs/BuildingLibcxx.rst b/docs/BuildingLibcxx.rst index d0b03c675c8b..a498c0027bd1 100644 --- a/docs/BuildingLibcxx.rst +++ b/docs/BuildingLibcxx.rst @@ -222,6 +222,15 @@ libc++ specific options Define libc++ destination prefix. +.. option:: LIBCXX_HERMETIC_STATIC_LIBRARY:BOOL + + **Default**: ``OFF`` + + Do not export any symbols from the static libc++ library. This is useful when + This is useful when the static libc++ library is being linked into shared + libraries that may be used in with other shared libraries that use different + C++ library. We want to avoid avoid exporting any libc++ symbols in that case. + .. _libc++experimental options: libc++experimental Specific Options @@ -316,6 +325,15 @@ libc++ Feature Options Build the libc++ benchmark tests and the Google Benchmark library needed to support them. +.. option:: LIBCXX_BENCHMARK_TEST_ARGS:STRING + + **Default**: ``--benchmark_min_time=0.01`` + + A semicolon list of arguments to pass when running the libc++ benchmarks using the + ``check-cxx-benchmarks`` rule. By default we run the benchmarks for a very short amount of time, + since the primary use of ``check-cxx-benchmarks`` is to get test and sanitizer coverage, not to + get accurate measurements. + .. option:: LIBCXX_BENCHMARK_NATIVE_STDLIB:STRING **Default**:: ``""`` @@ -332,6 +350,15 @@ libc++ Feature Options Use the specified GCC toolchain and standard library when building the native stdlib benchmark tests. +.. option:: LIBCXX_HIDE_FROM_ABI_PER_TU_BY_DEFAULT:BOOL + + **Default**: ``OFF`` + + Pick the default for whether to constrain ABI-unstable symbols to + each individual translation unit. This setting controls whether + `_LIBCPP_HIDE_FROM_ABI_PER_TU_BY_DEFAULT` is defined by default -- + see the documentation of that macro for details. + libc++ ABI Feature Options -------------------------- @@ -351,6 +378,20 @@ The following options allow building libc++ for a different ABI version. Build the "unstable" ABI version of libc++. Includes all ABI changing features on top of the current stable version. +.. option:: LIBCXX_ABI_NAMESPACE:STRING + + **Default**: ``__n`` where ``n`` is the current ABI version. + + This option defines the name of the inline ABI versioning namespace. It can be used for building + custom versions of libc++ with unique symbol names in order to prevent conflicts or ODR issues + with other libc++ versions. + + .. warning:: + When providing a custom namespace, it's the users responsibility to ensure the name won't cause + conflicts with other names defined by libc++, both now and in the future. In particular, inline + namespaces of the form ``__[0-9]+`` are strictly reserved by libc++ and may not be used by users. + Doing otherwise could cause conflicts and hinder libc++ ABI evolution. + .. option:: LIBCXX_ABI_DEFINES:STRING **Default**: ``""`` diff --git a/docs/DesignDocs/AvailabilityMarkup.rst b/docs/DesignDocs/AvailabilityMarkup.rst index b8b44509790d..4e6d80b50bf8 100644 --- a/docs/DesignDocs/AvailabilityMarkup.rst +++ b/docs/DesignDocs/AvailabilityMarkup.rst @@ -24,11 +24,11 @@ systems. For example:: // Define availability macros. #if defined(_LIBCPP_USE_AVAILABILITY_APPLE) - #define _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS __attribute__((unavailable)) + # define _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS __attribute__((unavailable)) #else if defined(_LIBCPP_USE_AVAILABILITY_SOME_OTHER_VENDOR) - #define _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS __attribute__((unavailable)) - #else - #define _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS + # define _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS __attribute__((unavailable)) + #else + # define _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS #endif When the library is updated by the platform vendor, the markup can be updated. @@ -43,9 +43,9 @@ For example:: In the source code, the macro can be added on a class if the full class requires type info from the library for example:: - _LIBCPP_BEGIN_NAMESPACE_EXPERIMENTAL - class _LIBCPP_EXCEPTION_ABI _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS bad_optional_access - : public std::logic_error { + _LIBCPP_BEGIN_NAMESPACE_EXPERIMENTAL + class _LIBCPP_EXCEPTION_ABI _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS bad_optional_access + : public std::logic_error { or on a particular symbol: @@ -55,7 +55,7 @@ or on a particular symbol: Testing ======= -Some parameters can be passed to lit to run the test-suite and exercising the +Some parameters can be passed to lit to run the test-suite and exercise the availability. * The `platform` parameter controls the deployment target. For example lit can @@ -65,14 +65,11 @@ availability. the test-suite against the host system library. Alternatively a path to the directory containing a specific prebuilt libc++ can be used, for example: `--param=use_system_cxx_lib=/path/to/macOS/10.8/`. -* The `with_availability` boolean parameter enables the availability markup. Tests can be marked as XFAIL based on multiple features made available by lit: -* if either `use_system_cxx_lib` or `with_availability` is passed to lit, - assuming `--param=platform=macosx10.8` is passed as well the following - features will be available: +* if `--param=platform=macosx10.8` is passed, the following features will be available: - availability - availability=x86_64 @@ -81,11 +78,11 @@ Tests can be marked as XFAIL based on multiple features made available by lit: - availability=x86_64-apple-macosx10.8 - availability=macosx10.8 - This feature is used to XFAIL a test that *is* using a class of a method marked + This feature is used to XFAIL a test that *is* using a class or a method marked as unavailable *and* that is expected to *fail* if deployed on an older system. -* if `use_system_cxx_lib` is passed to lit, the following features will also - be available: +* if `use_system_cxx_lib` and `--param=platform=macosx10.8` are passed to lit, + the following features will also be available: - with_system_cxx_lib - with_system_cxx_lib=x86_64 @@ -94,21 +91,9 @@ Tests can be marked as XFAIL based on multiple features made available by lit: - with_system_cxx_lib=x86_64-apple-macosx10.8 - with_system_cxx_lib=macosx10.8 - This feature is used to XFAIL a test that is *not* using a class of a method + This feature is used to XFAIL a test that is *not* using a class or a method marked as unavailable *but* that is expected to fail if deployed on an older - system. For example if we know that it exhibits a but in the libc on a - particular system version. - -* if `with_availability` is passed to lit, the following features will also - be available: - - - availability_markup - - availability_markup=x86_64 - - availability_markup=macosx - - availability_markup=x86_64-macosx - - availability_markup=x86_64-apple-macosx10.8 - - availability_markup=macosx10.8 - - This feature is used to XFAIL a test that *is* using a class of a method - marked as unavailable *but* that is expected to *pass* if deployed on an older - system. For example if it is using a symbol in a statically evaluated context. + system. For example, if the test exhibits a bug in the libc on a particular + system version, or if the test uses a symbol that is not available on an + older version of the dylib (but for which there is no availability markup, + otherwise the XFAIL should use `availability` above). diff --git a/docs/DesignDocs/CapturingConfigInfo.rst b/docs/DesignDocs/CapturingConfigInfo.rst index 88102251d932..29156bff8bc9 100644 --- a/docs/DesignDocs/CapturingConfigInfo.rst +++ b/docs/DesignDocs/CapturingConfigInfo.rst @@ -28,7 +28,7 @@ Design Goals It makes developers lives harder if they have to regenerate the libc++ headers every time they are modified. -* The solution should not make any of the libc++ headers dependant on +* The solution should not make any of the libc++ headers dependent on files generated by the build system. The headers should be able to compile out of the box without any modification. diff --git a/docs/DesignDocs/FeatureTestMacros.rst b/docs/DesignDocs/FeatureTestMacros.rst new file mode 100644 index 000000000000..d55af96c6749 --- /dev/null +++ b/docs/DesignDocs/FeatureTestMacros.rst @@ -0,0 +1,44 @@ +=================== +Feature Test Macros +=================== + +.. contents:: + :local: + +Overview +======== + +Libc++ implements the C++ feature test macros as specified in the C++2a standard, +and before that in non-normative guiding documents (`See cppreference <https://en.cppreference.com/w/User:D41D8CD98F/feature_testing_macros>`) + +Design +====== + +Feature test macros are tricky to track, implement, test, and document correctly. +They must be available from a list of headers, they may have different values in +different dialects, and they may or may not be implemented by libc++. In order to +track all of these conditions correctly and easily, we want a Single Source of +Truth (SSoT) that defines each feature test macro, its values, the headers it +lives in, and whether or not is is implemented by libc++. From this SSoA we +have enough information to automatically generate the `<version>` header, +the tests, and the documentation. + +Therefore we maintain a SSoA in +`libcxx/test/std/language.support/support.limits/support.limits.general/generate_feature_test_macro_components.py` +which doubles as a script to generate the following components: + +* The `<version>` header. +* The version tests under `support.limits.general`. +* Documentation of libc++'s implementation of each macro. + +Usage +===== + +The `generate_feature_test_macro_components.py` script is used to track and +update feature test macros in libc++. + +Whenever a feature test macro is added or changed, the table should be updated +and the script should be re-ran. The script will clobber the existing test files +and the documentation and it will generate a new `<version>` header as a +temporary file. The generated `<version>` header should be merged with the +existing one.
\ No newline at end of file diff --git a/docs/DesignDocs/VisibilityMacros.rst b/docs/DesignDocs/VisibilityMacros.rst index 878566ea0bc1..d0d4f0adb220 100644 --- a/docs/DesignDocs/VisibilityMacros.rst +++ b/docs/DesignDocs/VisibilityMacros.rst @@ -22,11 +22,11 @@ Visibility Macros Mark a symbol as being exported by the libc++ library. This attribute must be applied to the declaration of all functions exported by the libc++ dylib. -**_LIBCPP_EXTERN_VIS** +**_LIBCPP_EXPORTED_FROM_ABI** Mark a symbol as being exported by the libc++ library. This attribute may - only be applied to objects defined in the libc++ library. On Windows this - macro applies `dllimport`/`dllexport` to the symbol. On all other platforms - this macro has no effect. + only be applied to objects defined in the libc++ runtime library. On Windows, + this macro applies `dllimport`/`dllexport` to the symbol, and on other + platforms it gives the symbol default visibility. **_LIBCPP_OVERRIDABLE_FUNC_VIS** Mark a symbol as being exported by the libc++ library, but allow it to be @@ -42,9 +42,57 @@ Visibility Macros **_LIBCPP_HIDE_FROM_ABI** Mark a function as not being part of the ABI of any final linked image that - uses it, and also as being internal to each TU that uses that function. In - other words, the address of a function marked with this attribute is not - guaranteed to be the same across translation units. + uses it. + +**_LIBCPP_HIDE_FROM_ABI_AFTER_V1** + Mark a function as being hidden from the ABI (per `_LIBCPP_HIDE_FROM_ABI`) + when libc++ is built with an ABI version after ABI v1. This macro is used to + maintain ABI compatibility for symbols that have been historically exported + by libc++ in v1 of the ABI, but that we don't want to export in the future. + + This macro works as follows. When we build libc++, we either hide the symbol + from the ABI (if the symbol is not part of the ABI in the version we're + building), or we leave it included. From user code (i.e. when we're not + building libc++), the macro always marks symbols as internal so that programs + built using new libc++ headers stop relying on symbols that are removed from + the ABI in a future version. Each time we release a new stable version of the + ABI, we should create a new _LIBCPP_HIDE_FROM_ABI_AFTER_XXX macro, and we can + use it to start removing symbols from the ABI after that stable version. + +**_LIBCPP_HIDE_FROM_ABI_PER_TU** + This macro controls whether symbols hidden from the ABI with `_LIBCPP_HIDE_FROM_ABI` + are local to each translation unit in addition to being local to each final + linked image. This macro is defined to either 0 or 1. When it is defined to + 1, translation units compiled with different versions of libc++ can be linked + together, since all non ABI-facing functions are local to each translation unit. + This allows static archives built with different versions of libc++ to be linked + together. This also means that functions marked with `_LIBCPP_HIDE_FROM_ABI` + are not guaranteed to have the same address across translation unit boundaries. + + When the macro is defined to 0, there is no guarantee that translation units + compiled with different versions of libc++ can interoperate. However, this + leads to code size improvements, since non ABI-facing functions can be + deduplicated across translation unit boundaries. + + This macro can be defined by users to control the behavior they want from + libc++. The default value of this macro (0 or 1) is controlled by whether + `_LIBCPP_HIDE_FROM_ABI_PER_TU_BY_DEFAULT` is defined, which is intended to + be used by vendors only (see below). + +**_LIBCPP_HIDE_FROM_ABI_PER_TU_BY_DEFAULT** + This macro controls the default value for `_LIBCPP_HIDE_FROM_ABI_PER_TU`. + When the macro is defined, per TU ABI insulation is enabled by default, and + `_LIBCPP_HIDE_FROM_ABI_PER_TU` is defined to 1 unless overridden by users. + Otherwise, per TU ABI insulation is disabled by default, and + `_LIBCPP_HIDE_FROM_ABI_PER_TU` is defined to 0 unless overridden by users. + + This macro is intended for vendors to control whether they want to ship + libc++ with per TU ABI insulation enabled by default. Users can always + control the behavior they want by defining `_LIBCPP_HIDE_FROM_ABI_PER_TU` + appropriately. + + By default, this macro is not defined, which means that per TU ABI insulation + is not provided unless explicitly overridden by users. **_LIBCPP_TYPE_VIS** Mark a type's typeinfo, vtable and members as having default visibility. @@ -139,15 +187,6 @@ Visibility Macros against the libc++ headers after making `_LIBCPP_TYPE_VIS` and `_LIBCPP_EXTERN_TEMPLATE_TYPE_VIS` expand to default visibility. -**_LIBCPP_EXTERN_TEMPLATE_INLINE_VISIBILITY** - Mark a member function of a class template as visible and always inline. This - macro should only be applied to member functions of class templates that are - externally instantiated. It is important that these symbols are not marked - as hidden as that will prevent the dylib definition from being found. - - This macro is used to maintain ABI compatibility for symbols that have been - historically exported by the libc++ library but are now marked inline. - **_LIBCPP_EXCEPTION_ABI** Mark the member functions, typeinfo, and vtable of the type as being exported by the libc++ library. This macro must be applied to all *exception types*. diff --git a/docs/FeatureTestMacroTable.rst b/docs/FeatureTestMacroTable.rst new file mode 100644 index 000000000000..d900497eba70 --- /dev/null +++ b/docs/FeatureTestMacroTable.rst @@ -0,0 +1,200 @@ +.. _FeatureTestMacroTable: + +========================== +Feature Test Macro Support +========================== + +.. contents:: + :local: + +Overview +======== + +This file documents the feature test macros currently supported by libc++. + +.. _feature-status: + +Status +====== + +.. table:: Current Status + :name: feature-status-table + :widths: auto + + ================================================= ================= + Macro Name Value + ================================================= ================= + **C++ 14** + ------------------------------------------------------------------- + ``__cpp_lib_chrono_udls`` ``201304L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_complex_udls`` ``201309L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_exchange_function`` ``201304L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_generic_associative_lookup`` ``201304L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_integer_sequence`` ``201304L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_integral_constant_callable`` ``201304L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_is_final`` ``201402L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_is_null_pointer`` ``201309L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_make_reverse_iterator`` ``201402L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_make_unique`` ``201304L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_null_iterators`` ``201304L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_quoted_string_io`` ``201304L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_result_of_sfinae`` ``201210L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_robust_nonmodifying_seq_ops`` ``201304L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_shared_timed_mutex`` ``201402L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_string_udls`` ``201304L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_transformation_trait_aliases`` ``201304L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_transparent_operators`` ``201210L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_tuple_element_t`` ``201402L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_tuples_by_type`` ``201304L`` + ------------------------------------------------- ----------------- + **C++ 17** + ------------------------------------------------------------------- + ``__cpp_lib_addressof_constexpr`` ``201603L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_allocator_traits_is_always_equal`` ``201411L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_any`` ``201606L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_apply`` ``201603L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_array_constexpr`` ``201603L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_as_const`` ``201510L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_atomic_is_always_lock_free`` ``201603L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_bool_constant`` ``201505L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_boyer_moore_searcher`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_byte`` ``201603L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_chrono`` ``201611L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_clamp`` ``201603L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_enable_shared_from_this`` ``201603L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_execution`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_filesystem`` ``201703L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_gcd_lcm`` ``201606L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_hardware_interference_size`` ``201703L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_has_unique_object_representations`` ``201606L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_hypot`` ``201603L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_incomplete_container_elements`` ``201505L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_invoke`` ``201411L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_is_aggregate`` ``201703L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_is_invocable`` ``201703L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_is_swappable`` ``201603L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_launder`` ``201606L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_logical_traits`` ``201510L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_make_from_tuple`` ``201606L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_map_try_emplace`` ``201411L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_math_special_functions`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_memory_resource`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_node_extract`` ``201606L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_nonmember_container_access`` ``201411L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_not_fn`` ``201603L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_optional`` ``201606L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_parallel_algorithm`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_raw_memory_algorithms`` ``201606L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_sample`` ``201603L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_scoped_lock`` ``201703L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_shared_mutex`` ``201505L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_shared_ptr_arrays`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_shared_ptr_weak_type`` ``201606L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_string_view`` ``201606L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_to_chars`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_transparent_operators`` ``201510L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_type_trait_variable_templates`` ``201510L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_uncaught_exceptions`` ``201411L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_unordered_map_try_emplace`` ``201411L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_variant`` ``201606L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_void_t`` ``201411L`` + ------------------------------------------------- ----------------- + **C++ 2a** + ------------------------------------------------------------------- + ``__cpp_lib_atomic_ref`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_bind_front`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_bit_cast`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_char8_t`` ``201811L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_concepts`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_constexpr_misc`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_constexpr_swap_algorithms`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_destroying_delete`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_erase_if`` ``201811L`` + ------------------------------------------------- ----------------- + ``__cpp_lib_generic_unordered_lookup`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_is_constant_evaluated`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_list_remove_return_type`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_ranges`` *unimplemented* + ------------------------------------------------- ----------------- + ``__cpp_lib_three_way_comparison`` *unimplemented* + ================================================= ================= + + diff --git a/docs/ReleaseNotes.rst b/docs/ReleaseNotes.rst new file mode 100644 index 000000000000..20be9f627ef8 --- /dev/null +++ b/docs/ReleaseNotes.rst @@ -0,0 +1,62 @@ +======================================== +Libc++ 8.0.0 (In-Progress) Release Notes +======================================== + +.. contents:: + :local: + :depth: 2 + +Written by the `Libc++ Team <https://libcxx.llvm.org>`_ + +.. warning:: + + These are in-progress notes for the upcoming libc++ 8 release. + Release notes for previous releases can be found on + `the Download Page <https://releases.llvm.org/download.html>`_. + +Introduction +============ + +This document contains the release notes for the libc++ C++ Standard Library, +part of the LLVM Compiler Infrastructure, release 8.0.0. Here we describe the +status of libc++ in some detail, including major improvements from the previous +release and new feature work. For the general LLVM release notes, see `the LLVM +documentation <https://llvm.org/docs/ReleaseNotes.html>`_. All LLVM releases may +be downloaded from the `LLVM releases web site <https://llvm.org/releases/>`_. + +For more information about libc++, please see the `Libc++ Web Site +<https://libcxx.llvm.org>`_ or the `LLVM Web Site <https://llvm.org>`_. + +Note that if you are reading this file from a Subversion checkout or the +main Libc++ web page, this document applies to the *next* release, not +the current one. To see the release notes for a specific release, please +see the `releases page <https://llvm.org/releases/>`_. + +What's New in Libc++ 8.0.0? +=========================== + +New Features +------------ + +API Changes +----------- +- Building libc++ for Mac OSX 10.6 is not supported anymore. +- Starting with LLVM 8.0.0, users that wish to link together translation units + built with different versions of libc++'s headers into the same final linked + image MUST define the _LIBCPP_HIDE_FROM_ABI_PER_TU macro to 1 when building + those translation units. Not defining _LIBCPP_HIDE_FROM_ABI_PER_TU to 1 and + linking translation units built with different versions of libc++'s headers + together may lead to ODR violations and ABI issues. On the flipside, code + size improvements should be expected for everyone not defining the macro. +- Starting with LLVM 8.0.0, std::dynarray has been removed from the library. + std::dynarray was a feature proposed for C++14 that was pulled from the + Standard at the last minute and was never standardized. Since there are no + plans to standardize this facility it is being removed. +- Starting with LLVM 8.0.0, std::bad_array_length has been removed from the + library. std::bad_array_length was a feature proposed for C++14 alongside + std::dynarray, but it never actually made it into the C++ Standard. There + are no plans to standardize this feature at this time. Formally speaking, + this removal constitutes an ABI break because the symbols were shipped in + the shared library. However, on macOS systems, the feature was not usable + because it was hidden behind availability annotations. We do not expect + any actual breakage to happen from this change. diff --git a/docs/TestingLibcxx.rst b/docs/TestingLibcxx.rst index 43c0684dc7de..ebbbf628ac04 100644 --- a/docs/TestingLibcxx.rst +++ b/docs/TestingLibcxx.rst @@ -138,8 +138,7 @@ configuration. Passing the option on the command line will override the default. Specify the directory of the libc++ library to use at runtime. This directory is not added to the linkers search path. This can be used to compile tests against one version of libc++ and run them using another. The default value - for this option is `cxx_library_root`. This option cannot be used - when use_system_cxx_lib is provided. + for this option is `cxx_library_root`. .. option:: use_system_cxx_lib=<bool> @@ -155,14 +154,6 @@ configuration. Passing the option on the command line will override the default. the default value. Otherwise the default value is True on Windows and False on every other platform. -.. option:: no_default_flags=<bool> - - **Default**: False - - Disable all default compile and link flags from being added. When this - option is used only flags specified using the compile_flags and link_flags - will be used. - .. option:: compile_flags="<list-of-args>" Specify additional compile flags as a space delimited string. diff --git a/docs/UsingLibcxx.rst b/docs/UsingLibcxx.rst index e10a27c598a1..899656cca1d5 100644 --- a/docs/UsingLibcxx.rst +++ b/docs/UsingLibcxx.rst @@ -203,8 +203,10 @@ thread safety annotations. This macro disables the additional diagnostics generated by libc++ using the `diagnose_if` attribute. These additional diagnostics include checks for: - * Giving `set`, `map`, `multiset`, `multimap` a comparator which is not - const callable. + * Giving `set`, `map`, `multiset`, `multimap` and their `unordered_` + counterparts a comparator which is not const callable. + * Giving an unordered associative container a hasher that is not const + callable. **_LIBCPP_NO_VCRUNTIME**: Microsoft's C and C++ headers are fairly entangled, and some of their C++ @@ -226,6 +228,26 @@ thread safety annotations. replacement scenarios from working, e.g. replacing `operator new` and expecting a non-replaced `operator new[]` to call the replaced `operator new`. +**_LIBCPP_ENABLE_NODISCARD**: + Allow the library to add ``[[nodiscard]]`` attributes to entities not specified + as ``[[nodiscard]]`` by the current language dialect. This includes + backporting applications of ``[[nodiscard]]`` from newer dialects and + additional extended applications at the discretion of the library. All + additional applications of ``[[nodiscard]]`` are disabled by default. + See :ref:`Extended Applications of [[nodiscard]] <nodiscard extension>` for + more information. + +**_LIBCPP_DISABLE_NODISCARD_EXT**: + This macro prevents the library from applying ``[[nodiscard]]`` to entities + purely as an extension. See :ref:`Extended Applications of [[nodiscard]] <nodiscard extension>` + for more information. + +**_LIBCPP_ENABLE_DEPRECATION_WARNINGS**: + This macro enables warnings when using deprecated components. For example, + when compiling in C++11 mode, using `std::auto_ptr` with the macro defined + will trigger a warning saying that `std::auto_ptr` is deprecated. By default, + this macro is not defined. + C++17 Specific Configuration Macros ----------------------------------- **_LIBCPP_ENABLE_CXX17_REMOVED_FEATURES**: @@ -238,3 +260,58 @@ C++17 Specific Configuration Macros **_LIBCPP_ENABLE_CXX17_REMOVED_AUTO_PTR**: This macro is used to re-enable `std::auto_ptr` in C++17. + +C++2a Specific Configuration Macros: +------------------------------------ +**_LIBCPP_DISABLE_NODISCARD_AFTER_CXX17**: + This macro can be used to disable diagnostics emitted from functions marked + ``[[nodiscard]]`` in dialects after C++17. See :ref:`Extended Applications of [[nodiscard]] <nodiscard extension>` + for more information. + + +Libc++ Extensions +================= + +This section documents various extensions provided by libc++, how they're +provided, and any information regarding how to use them. + +.. _nodiscard extension: + +Extended applications of ``[[nodiscard]]`` +------------------------------------------ + +The ``[[nodiscard]]`` attribute is intended to help users find bugs where +function return values are ignored when they shouldn't be. After C++17 the +C++ standard has started to declared such library functions as ``[[nodiscard]]``. +However, this application is limited and applies only to dialects after C++17. +Users who want help diagnosing misuses of STL functions may desire a more +liberal application of ``[[nodiscard]]``. + +For this reason libc++ provides an extension that does just that! The +extension must be enabled by defining ``_LIBCPP_ENABLE_NODISCARD``. The extended +applications of ``[[nodiscard]]`` takes two forms: + +1. Backporting ``[[nodiscard]]`` to entities declared as such by the + standard in newer dialects, but not in the present one. + +2. Extended applications of ``[[nodiscard]]``, at the libraries discretion, + applied to entities never declared as such by the standard. + +Users may also opt-out of additional applications ``[[nodiscard]]`` using +additional macros. + +Applications of the first form, which backport ``[[nodiscard]]`` from a newer +dialect may be disabled using macros specific to the dialect it was added. For +example ``_LIBCPP_DISABLE_NODISCARD_AFTER_CXX17``. + +Applications of the second form, which are pure extensions, may be disabled +by defining ``_LIBCPP_DISABLE_NODISCARD_EXT``. + + +Entities declared with ``_LIBCPP_NODISCARD_EXT`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +This section lists all extended applications of ``[[nodiscard]]`` to entities +which no dialect declares as such (See the second form described above). + +* ``get_temporary_buffer`` diff --git a/docs/conf.py b/docs/conf.py index 4c1ea3653cdb..50b372cf84e2 100644 --- a/docs/conf.py +++ b/docs/conf.py @@ -40,16 +40,16 @@ master_doc = 'index' # General information about the project. project = u'libc++' -copyright = u'2011-2017, LLVM Project' +copyright = u'2011-2018, LLVM Project' # The version info for the project you're documenting, acts as replacement for # |version| and |release|, also used in various other places throughout the # built documents. # # The short X.Y version. -version = '7.0' +version = '8.0' # The full version, including alpha/beta/rc tags. -release = '7.0' +release = '8.0' # The language for content autogenerated by Sphinx. Refer to documentation # for a list of supported languages. @@ -241,7 +241,7 @@ texinfo_documents = [ #texinfo_show_urls = 'footnote' -# FIXME: Define intersphinx configration. +# FIXME: Define intersphinx configuration. intersphinx_mapping = {} diff --git a/docs/index.rst b/docs/index.rst index e4b3a879da94..fddf74b66a98 100644 --- a/docs/index.rst +++ b/docs/index.rst @@ -34,11 +34,17 @@ Getting Started with libc++ .. toctree:: :maxdepth: 2 + ReleaseNotes UsingLibcxx BuildingLibcxx TestingLibcxx +.. toctree:: + :hidden: + + FeatureTestMacroTable + Current Status -------------- @@ -79,8 +85,8 @@ reasons, but some of the major ones are: Platform and Compiler Support ----------------------------- -libc++ is known to work on the following platforms, using gcc-4.2 and -clang (lack of C++11 language support disables some functionality). +libc++ is known to work on the following platforms, using gcc and +clang. Note that functionality provided by ``<atomic>`` is only functional with clang and GCC. @@ -104,8 +110,9 @@ C++ Dialect Support * C++11 - Complete * `C++14 - Complete <http://libcxx.llvm.org/cxx1y_status.html>`__ -* `C++1z - In Progress <http://libcxx.llvm.org/cxx1z_status.html>`__ +* `C++17 - In Progress <http://libcxx.llvm.org/cxx1z_status.html>`__ * `Post C++14 Technical Specifications - In Progress <http://libcxx.llvm.org/ts1z_status.html>`__ +* :ref:`C++ Feature Test Macro Status <feature-status>` Notes and Known Issues ---------------------- @@ -135,6 +142,7 @@ Design Documents DesignDocs/VisibilityMacros DesignDocs/ThreadingSupportAPI DesignDocs/FileTimeType + DesignDocs/FeatureTestMacros * `<atomic> design <http://libcxx.llvm.org/atomic_design.html>`_ * `<type_traits> design <http://libcxx.llvm.org/type_traits_design.html>`_ @@ -160,21 +168,18 @@ and `Getting started with LLVM <http://llvm.org/docs/GettingStarted.html>`__. If you think you've found a bug in libc++, please report it using the `LLVM Bugzilla`_. If you're not sure, you -can post a message to the `cfe-dev mailing list`_ or on IRC. -Please include "libc++" in your subject. +can post a message to the `libcxx-dev mailing list`_ or on IRC. **Patches** If you want to contribute a patch to libc++, the best place for that is -`Phabricator <http://llvm.org/docs/Phabricator.html>`_. Please include [libcxx] in the subject and -add `cfe-commits` as a subscriber. Also make sure you are subscribed to the -`cfe-commits mailing list <http://lists.llvm.org/mailman/listinfo/cfe-commits>`_. +`Phabricator <http://llvm.org/docs/Phabricator.html>`_. Please add `libcxx-commits` as a subscriber. +Also make sure you are subscribed to the `libcxx-commits mailing list <http://lists.llvm.org/mailman/listinfo/libcxx-commits>`_. **Discussion and Questions** Send discussions and questions to the -`cfe-dev mailing list <http://lists.llvm.org/mailman/listinfo/cfe-dev>`_. -Please include [libcxx] in the subject. +`libcxx-dev mailing list <http://lists.llvm.org/mailman/listinfo/libcxx-dev>`_. @@ -183,7 +188,7 @@ Quick Links * `LLVM Homepage <http://llvm.org/>`_ * `libc++abi Homepage <http://libcxxabi.llvm.org/>`_ * `LLVM Bugzilla <https://bugs.llvm.org/>`_ -* `cfe-commits Mailing List`_ -* `cfe-dev Mailing List`_ +* `libcxx-commits Mailing List`_ +* `libcxx-dev Mailing List`_ * `Browse libc++ -- SVN <http://llvm.org/svn/llvm-project/libcxx/trunk/>`_ * `Browse libc++ -- ViewVC <http://llvm.org/viewvc/llvm-project/libcxx/trunk/>`_ diff --git a/fuzzing/fuzzing.cpp b/fuzzing/fuzzing.cpp index 8888cbeac72e..ad377bcac467 100644 --- a/fuzzing/fuzzing.cpp +++ b/fuzzing/fuzzing.cpp @@ -8,18 +8,18 @@ // //===----------------------------------------------------------------------===// -// A set of routines to use when fuzzing the algorithms in libc++ -// Each one tests a single algorithm. +// A set of routines to use when fuzzing the algorithms in libc++ +// Each one tests a single algorithm. // -// They all have the form of: -// int `algorithm`(const uint8_t *data, size_t size); +// They all have the form of: +// int `algorithm`(const uint8_t *data, size_t size); // -// They perform the operation, and then check to see if the results are correct. -// If so, they return zero, and non-zero otherwise. +// They perform the operation, and then check to see if the results are correct. +// If so, they return zero, and non-zero otherwise. // -// For example, sort calls std::sort, then checks two things: -// (1) The resulting vector is sorted -// (2) The resulting vector contains the same elements as the original data. +// For example, sort calls std::sort, then checks two things: +// (1) The resulting vector is sorted +// (2) The resulting vector contains the same elements as the original data. @@ -32,574 +32,587 @@ #include <iostream> -// If we had C++14, we could use the four iterator version of is_permutation and equal +// If we had C++14, we could use the four iterator version of is_permutation and equal namespace fuzzing { -// This is a struct we can use to test the stable_XXX algorithms. -// perform the operation on the key, then check the order of the payload. +// This is a struct we can use to test the stable_XXX algorithms. +// perform the operation on the key, then check the order of the payload. struct stable_test { - uint8_t key; - size_t payload; - - stable_test(uint8_t k) : key(k), payload(0) {} - stable_test(uint8_t k, size_t p) : key(k), payload(p) {} - }; + uint8_t key; + size_t payload; + + stable_test(uint8_t k) : key(k), payload(0) {} + stable_test(uint8_t k, size_t p) : key(k), payload(p) {} + }; void swap(stable_test &lhs, stable_test &rhs) { - using std::swap; - swap(lhs.key, rhs.key); - swap(lhs.payload, rhs.payload); + using std::swap; + swap(lhs.key, rhs.key); + swap(lhs.payload, rhs.payload); } struct key_less { - bool operator () (const stable_test &lhs, const stable_test &rhs) const - { - return lhs.key < rhs.key; - } + bool operator () (const stable_test &lhs, const stable_test &rhs) const + { + return lhs.key < rhs.key; + } }; struct payload_less { - bool operator () (const stable_test &lhs, const stable_test &rhs) const - { - return lhs.payload < rhs.payload; - } + bool operator () (const stable_test &lhs, const stable_test &rhs) const + { + return lhs.payload < rhs.payload; + } }; struct total_less { - bool operator () (const stable_test &lhs, const stable_test &rhs) const - { - return lhs.key == rhs.key ? lhs.payload < rhs.payload : lhs.key < rhs.key; - } + bool operator () (const stable_test &lhs, const stable_test &rhs) const + { + return lhs.key == rhs.key ? lhs.payload < rhs.payload : lhs.key < rhs.key; + } }; bool operator==(const stable_test &lhs, const stable_test &rhs) -{ - return lhs.key == rhs.key && lhs.payload == rhs.payload; +{ + return lhs.key == rhs.key && lhs.payload == rhs.payload; } template<typename T> struct is_even { - bool operator () (const T &t) const - { - return t % 2 == 0; - } + bool operator () (const T &t) const + { + return t % 2 == 0; + } }; template<> struct is_even<stable_test> { - bool operator () (const stable_test &t) const - { - return t.key % 2 == 0; - } + bool operator () (const stable_test &t) const + { + return t.key % 2 == 0; + } }; typedef std::vector<uint8_t> Vec; typedef std::vector<stable_test> StableVec; typedef StableVec::const_iterator SVIter; -// Cheap version of is_permutation -// Builds a set of buckets for each of the key values. -// Sums all the payloads. -// Not 100% perfect, but _way_ faster +// Cheap version of is_permutation +// Builds a set of buckets for each of the key values. +// Sums all the payloads. +// Not 100% perfect, but _way_ faster bool is_permutation(SVIter first1, SVIter last1, SVIter first2) { - size_t xBuckets[256] = {0}; - size_t xPayloads[256] = {0}; - size_t yBuckets[256] = {0}; - size_t yPayloads[256] = {0}; - - for (; first1 != last1; ++first1, ++first2) - { - xBuckets [first1->key]++; - xPayloads[first1->key] += first1->payload; - - yBuckets [first2->key]++; - yPayloads[first2->key] += first2->payload; - } - - for (size_t i = 0; i < 256; ++i) - { - if (xBuckets[i] != yBuckets[i]) - return false; - if (xPayloads[i] != yPayloads[i]) - return false; - } - - return true; + size_t xBuckets[256] = {0}; + size_t xPayloads[256] = {0}; + size_t yBuckets[256] = {0}; + size_t yPayloads[256] = {0}; + + for (; first1 != last1; ++first1, ++first2) + { + xBuckets [first1->key]++; + xPayloads[first1->key] += first1->payload; + + yBuckets [first2->key]++; + yPayloads[first2->key] += first2->payload; + } + + for (size_t i = 0; i < 256; ++i) + { + if (xBuckets[i] != yBuckets[i]) + return false; + if (xPayloads[i] != yPayloads[i]) + return false; + } + + return true; } template <typename Iter1, typename Iter2> bool is_permutation(Iter1 first1, Iter1 last1, Iter2 first2) { - static_assert((std::is_same<typename std::iterator_traits<Iter1>::value_type, uint8_t>::value), ""); - static_assert((std::is_same<typename std::iterator_traits<Iter2>::value_type, uint8_t>::value), ""); - - size_t xBuckets[256] = {0}; - size_t yBuckets[256] = {0}; - - for (; first1 != last1; ++first1, ++first2) - { - xBuckets [*first1]++; - yBuckets [*first2]++; - } - - for (size_t i = 0; i < 256; ++i) - if (xBuckets[i] != yBuckets[i]) - return false; - - return true; + static_assert((std::is_same<typename std::iterator_traits<Iter1>::value_type, uint8_t>::value), ""); + static_assert((std::is_same<typename std::iterator_traits<Iter2>::value_type, uint8_t>::value), ""); + + size_t xBuckets[256] = {0}; + size_t yBuckets[256] = {0}; + + for (; first1 != last1; ++first1, ++first2) + { + xBuckets [*first1]++; + yBuckets [*first2]++; + } + + for (size_t i = 0; i < 256; ++i) + if (xBuckets[i] != yBuckets[i]) + return false; + + return true; } -// == sort == +// == sort == int sort(const uint8_t *data, size_t size) { - Vec working(data, data + size); - std::sort(working.begin(), working.end()); + Vec working(data, data + size); + std::sort(working.begin(), working.end()); - if (!std::is_sorted(working.begin(), working.end())) return 1; - if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99; - return 0; + if (!std::is_sorted(working.begin(), working.end())) return 1; + if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99; + return 0; } -// == stable_sort == +// == stable_sort == int stable_sort(const uint8_t *data, size_t size) { - StableVec input; - for (size_t i = 0; i < size; ++i) - input.push_back(stable_test(data[i], i)); - StableVec working = input; - std::stable_sort(working.begin(), working.end(), key_less()); - - if (!std::is_sorted(working.begin(), working.end(), key_less())) return 1; - auto iter = working.begin(); - while (iter != working.end()) - { - auto range = std::equal_range(iter, working.end(), *iter, key_less()); - if (!std::is_sorted(range.first, range.second, total_less())) return 2; - iter = range.second; - } - if (!fuzzing::is_permutation(input.cbegin(), input.cend(), working.cbegin())) return 99; - return 0; + StableVec input; + for (size_t i = 0; i < size; ++i) + input.push_back(stable_test(data[i], i)); + StableVec working = input; + std::stable_sort(working.begin(), working.end(), key_less()); + + if (!std::is_sorted(working.begin(), working.end(), key_less())) return 1; + auto iter = working.begin(); + while (iter != working.end()) + { + auto range = std::equal_range(iter, working.end(), *iter, key_less()); + if (!std::is_sorted(range.first, range.second, total_less())) return 2; + iter = range.second; + } + if (!fuzzing::is_permutation(input.cbegin(), input.cend(), working.cbegin())) return 99; + return 0; } -// == partition == +// == partition == int partition(const uint8_t *data, size_t size) { - Vec working(data, data + size); - auto iter = std::partition(working.begin(), working.end(), is_even<uint8_t>()); + Vec working(data, data + size); + auto iter = std::partition(working.begin(), working.end(), is_even<uint8_t>()); - if (!std::all_of (working.begin(), iter, is_even<uint8_t>())) return 1; - if (!std::none_of(iter, working.end(), is_even<uint8_t>())) return 2; - if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99; - return 0; + if (!std::all_of (working.begin(), iter, is_even<uint8_t>())) return 1; + if (!std::none_of(iter, working.end(), is_even<uint8_t>())) return 2; + if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99; + return 0; } -// == partition_copy == +// == partition_copy == int partition_copy(const uint8_t *data, size_t size) { - Vec v1, v2; - auto iter = std::partition_copy(data, data + size, - std::back_inserter<Vec>(v1), std::back_inserter<Vec>(v2), - is_even<uint8_t>()); - -// The two vectors should add up to the original size - if (v1.size() + v2.size() != size) return 1; - -// All of the even values should be in the first vector, and none in the second - if (!std::all_of (v1.begin(), v1.end(), is_even<uint8_t>())) return 2; - if (!std::none_of(v2.begin(), v2.end(), is_even<uint8_t>())) return 3; - -// Every value in both vectors has to be in the original - for (auto v: v1) - if (std::find(data, data + size, v) == data + size) return 4; - - for (auto v: v2) - if (std::find(data, data + size, v) == data + size) return 5; - - return 0; + Vec v1, v2; + auto iter = std::partition_copy(data, data + size, + std::back_inserter<Vec>(v1), std::back_inserter<Vec>(v2), + is_even<uint8_t>()); + +// The two vectors should add up to the original size + if (v1.size() + v2.size() != size) return 1; + +// All of the even values should be in the first vector, and none in the second + if (!std::all_of (v1.begin(), v1.end(), is_even<uint8_t>())) return 2; + if (!std::none_of(v2.begin(), v2.end(), is_even<uint8_t>())) return 3; + +// Every value in both vectors has to be in the original + +// Make a copy of the input, and sort it + Vec v0{data, data + size}; + std::sort(v0.begin(), v0.end()); + +// Sort each vector and ensure that all of the elements appear in the original input + std::sort(v1.begin(), v1.end()); + if (!std::includes(v0.begin(), v0.end(), v1.begin(), v1.end())) return 4; + + std::sort(v2.begin(), v2.end()); + if (!std::includes(v0.begin(), v0.end(), v2.begin(), v2.end())) return 5; + +// This, while simple, is really slow - 20 seconds on a 500K element input. +// for (auto v: v1) +// if (std::find(data, data + size, v) == data + size) return 4; +// +// for (auto v: v2) +// if (std::find(data, data + size, v) == data + size) return 5; + + return 0; } -// == stable_partition == +// == stable_partition == int stable_partition (const uint8_t *data, size_t size) { - StableVec input; - for (size_t i = 0; i < size; ++i) - input.push_back(stable_test(data[i], i)); - StableVec working = input; - auto iter = std::stable_partition(working.begin(), working.end(), is_even<stable_test>()); - - if (!std::all_of (working.begin(), iter, is_even<stable_test>())) return 1; - if (!std::none_of(iter, working.end(), is_even<stable_test>())) return 2; - if (!std::is_sorted(working.begin(), iter, payload_less())) return 3; - if (!std::is_sorted(iter, working.end(), payload_less())) return 4; - if (!fuzzing::is_permutation(input.cbegin(), input.cend(), working.cbegin())) return 99; - return 0; + StableVec input; + for (size_t i = 0; i < size; ++i) + input.push_back(stable_test(data[i], i)); + StableVec working = input; + auto iter = std::stable_partition(working.begin(), working.end(), is_even<stable_test>()); + + if (!std::all_of (working.begin(), iter, is_even<stable_test>())) return 1; + if (!std::none_of(iter, working.end(), is_even<stable_test>())) return 2; + if (!std::is_sorted(working.begin(), iter, payload_less())) return 3; + if (!std::is_sorted(iter, working.end(), payload_less())) return 4; + if (!fuzzing::is_permutation(input.cbegin(), input.cend(), working.cbegin())) return 99; + return 0; } -// == nth_element == -// use the first element as a position into the data +// == nth_element == +// use the first element as a position into the data int nth_element (const uint8_t *data, size_t size) { - if (size <= 1) return 0; - const size_t partition_point = data[0] % size; - Vec working(data + 1, data + size); - const auto partition_iter = working.begin() + partition_point; - std::nth_element(working.begin(), partition_iter, working.end()); - -// nth may be the end iterator, in this case nth_element has no effect. - if (partition_iter == working.end()) - { - if (!std::equal(data + 1, data + size, working.begin())) return 98; - } - else - { - const uint8_t nth = *partition_iter; - if (!std::all_of(working.begin(), partition_iter, [=](uint8_t v) { return v <= nth; })) - return 1; - if (!std::all_of(partition_iter, working.end(), [=](uint8_t v) { return v >= nth; })) - return 2; - if (!fuzzing::is_permutation(data + 1, data + size, working.cbegin())) return 99; - } - - return 0; + if (size <= 1) return 0; + const size_t partition_point = data[0] % size; + Vec working(data + 1, data + size); + const auto partition_iter = working.begin() + partition_point; + std::nth_element(working.begin(), partition_iter, working.end()); + +// nth may be the end iterator, in this case nth_element has no effect. + if (partition_iter == working.end()) + { + if (!std::equal(data + 1, data + size, working.begin())) return 98; + } + else + { + const uint8_t nth = *partition_iter; + if (!std::all_of(working.begin(), partition_iter, [=](uint8_t v) { return v <= nth; })) + return 1; + if (!std::all_of(partition_iter, working.end(), [=](uint8_t v) { return v >= nth; })) + return 2; + if (!fuzzing::is_permutation(data + 1, data + size, working.cbegin())) return 99; + } + + return 0; } -// == partial_sort == -// use the first element as a position into the data +// == partial_sort == +// use the first element as a position into the data int partial_sort (const uint8_t *data, size_t size) { - if (size <= 1) return 0; - const size_t sort_point = data[0] % size; - Vec working(data + 1, data + size); - const auto sort_iter = working.begin() + sort_point; - std::partial_sort(working.begin(), sort_iter, working.end()); - - if (sort_iter != working.end()) - { - const uint8_t nth = *std::min_element(sort_iter, working.end()); - if (!std::all_of(working.begin(), sort_iter, [=](uint8_t v) { return v <= nth; })) - return 1; - if (!std::all_of(sort_iter, working.end(), [=](uint8_t v) { return v >= nth; })) - return 2; - } - if (!std::is_sorted(working.begin(), sort_iter)) return 3; - if (!fuzzing::is_permutation(data + 1, data + size, working.cbegin())) return 99; - - return 0; + if (size <= 1) return 0; + const size_t sort_point = data[0] % size; + Vec working(data + 1, data + size); + const auto sort_iter = working.begin() + sort_point; + std::partial_sort(working.begin(), sort_iter, working.end()); + + if (sort_iter != working.end()) + { + const uint8_t nth = *std::min_element(sort_iter, working.end()); + if (!std::all_of(working.begin(), sort_iter, [=](uint8_t v) { return v <= nth; })) + return 1; + if (!std::all_of(sort_iter, working.end(), [=](uint8_t v) { return v >= nth; })) + return 2; + } + if (!std::is_sorted(working.begin(), sort_iter)) return 3; + if (!fuzzing::is_permutation(data + 1, data + size, working.cbegin())) return 99; + + return 0; } -// == partial_sort_copy == -// use the first element as a count +// == partial_sort_copy == +// use the first element as a count int partial_sort_copy (const uint8_t *data, size_t size) { - if (size <= 1) return 0; - const size_t num_results = data[0] % size; - Vec results(num_results); - (void) std::partial_sort_copy(data + 1, data + size, results.begin(), results.end()); - -// The results have to be sorted - if (!std::is_sorted(results.begin(), results.end())) return 1; -// All the values in results have to be in the original data - for (auto v: results) - if (std::find(data + 1, data + size, v) == data + size) return 2; - -// The things in results have to be the smallest N in the original data - Vec sorted(data + 1, data + size); - std::sort(sorted.begin(), sorted.end()); - if (!std::equal(results.begin(), results.end(), sorted.begin())) return 3; - return 0; + if (size <= 1) return 0; + const size_t num_results = data[0] % size; + Vec results(num_results); + (void) std::partial_sort_copy(data + 1, data + size, results.begin(), results.end()); + +// The results have to be sorted + if (!std::is_sorted(results.begin(), results.end())) return 1; +// All the values in results have to be in the original data + for (auto v: results) + if (std::find(data + 1, data + size, v) == data + size) return 2; + +// The things in results have to be the smallest N in the original data + Vec sorted(data + 1, data + size); + std::sort(sorted.begin(), sorted.end()); + if (!std::equal(results.begin(), results.end(), sorted.begin())) return 3; + return 0; } -// The second sequence has been "uniqued" +// The second sequence has been "uniqued" template <typename Iter1, typename Iter2> static bool compare_unique(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2) { - assert(first1 != last1 && first2 != last2); - if (*first1 != *first2) return false; - - uint8_t last_value = *first1; - ++first1; ++first2; - while(first1 != last1 && first2 != last2) - { - // Skip over dups in the first sequence - while (*first1 == last_value) - if (++first1 == last1) return false; - if (*first1 != *first2) return false; - last_value = *first1; - ++first1; ++first2; - } - -// Still stuff left in the 'uniqued' sequence - oops - if (first1 == last1 && first2 != last2) return false; - -// Still stuff left in the original sequence - better be all the same - while (first1 != last1) - { - if (*first1 != last_value) return false; - ++first1; - } - return true; + assert(first1 != last1 && first2 != last2); + if (*first1 != *first2) return false; + + uint8_t last_value = *first1; + ++first1; ++first2; + while(first1 != last1 && first2 != last2) + { + // Skip over dups in the first sequence + while (*first1 == last_value) + if (++first1 == last1) return false; + if (*first1 != *first2) return false; + last_value = *first1; + ++first1; ++first2; + } + +// Still stuff left in the 'uniqued' sequence - oops + if (first1 == last1 && first2 != last2) return false; + +// Still stuff left in the original sequence - better be all the same + while (first1 != last1) + { + if (*first1 != last_value) return false; + ++first1; + } + return true; } -// == unique == +// == unique == int unique (const uint8_t *data, size_t size) { - Vec working(data, data + size); - std::sort(working.begin(), working.end()); - Vec results = working; - Vec::iterator new_end = std::unique(results.begin(), results.end()); - Vec::iterator it; // scratch iterator - -// Check the size of the unique'd sequence. -// it should only be zero if the input sequence was empty. - if (results.begin() == new_end) - return working.size() == 0 ? 0 : 1; - -// 'results' is sorted - if (!std::is_sorted(results.begin(), new_end)) return 2; - -// All the elements in 'results' must be different - it = results.begin(); - uint8_t prev_value = *it++; - for (; it != new_end; ++it) - { - if (*it == prev_value) return 3; - prev_value = *it; - } - -// Every element in 'results' must be in 'working' - for (it = results.begin(); it != new_end; ++it) - if (std::find(working.begin(), working.end(), *it) == working.end()) - return 4; - -// Every element in 'working' must be in 'results' - for (auto v : working) - if (std::find(results.begin(), new_end, v) == new_end) - return 5; - - return 0; + Vec working(data, data + size); + std::sort(working.begin(), working.end()); + Vec results = working; + Vec::iterator new_end = std::unique(results.begin(), results.end()); + Vec::iterator it; // scratch iterator + +// Check the size of the unique'd sequence. +// it should only be zero if the input sequence was empty. + if (results.begin() == new_end) + return working.size() == 0 ? 0 : 1; + +// 'results' is sorted + if (!std::is_sorted(results.begin(), new_end)) return 2; + +// All the elements in 'results' must be different + it = results.begin(); + uint8_t prev_value = *it++; + for (; it != new_end; ++it) + { + if (*it == prev_value) return 3; + prev_value = *it; + } + +// Every element in 'results' must be in 'working' + for (it = results.begin(); it != new_end; ++it) + if (std::find(working.begin(), working.end(), *it) == working.end()) + return 4; + +// Every element in 'working' must be in 'results' + for (auto v : working) + if (std::find(results.begin(), new_end, v) == new_end) + return 5; + + return 0; } -// == unique_copy == +// == unique_copy == int unique_copy (const uint8_t *data, size_t size) { - Vec working(data, data + size); - std::sort(working.begin(), working.end()); - Vec results; - (void) std::unique_copy(working.begin(), working.end(), - std::back_inserter<Vec>(results)); - Vec::iterator it; // scratch iterator - -// Check the size of the unique'd sequence. -// it should only be zero if the input sequence was empty. - if (results.size() == 0) - return working.size() == 0 ? 0 : 1; - -// 'results' is sorted - if (!std::is_sorted(results.begin(), results.end())) return 2; - -// All the elements in 'results' must be different - it = results.begin(); - uint8_t prev_value = *it++; - for (; it != results.end(); ++it) - { - if (*it == prev_value) return 3; - prev_value = *it; - } - -// Every element in 'results' must be in 'working' - for (auto v : results) - if (std::find(working.begin(), working.end(), v) == working.end()) - return 4; - -// Every element in 'working' must be in 'results' - for (auto v : working) - if (std::find(results.begin(), results.end(), v) == results.end()) - return 5; - - return 0; + Vec working(data, data + size); + std::sort(working.begin(), working.end()); + Vec results; + (void) std::unique_copy(working.begin(), working.end(), + std::back_inserter<Vec>(results)); + Vec::iterator it; // scratch iterator + +// Check the size of the unique'd sequence. +// it should only be zero if the input sequence was empty. + if (results.size() == 0) + return working.size() == 0 ? 0 : 1; + +// 'results' is sorted + if (!std::is_sorted(results.begin(), results.end())) return 2; + +// All the elements in 'results' must be different + it = results.begin(); + uint8_t prev_value = *it++; + for (; it != results.end(); ++it) + { + if (*it == prev_value) return 3; + prev_value = *it; + } + +// Every element in 'results' must be in 'working' + for (auto v : results) + if (std::find(working.begin(), working.end(), v) == working.end()) + return 4; + +// Every element in 'working' must be in 'results' + for (auto v : working) + if (std::find(results.begin(), results.end(), v) == results.end()) + return 5; + + return 0; } -// -- regex fuzzers +// -- regex fuzzers static int regex_helper(const uint8_t *data, size_t size, std::regex::flag_type flag) { - if (size > 0) - { - try - { - std::string s((const char *)data, size); - std::regex re(s, flag); - return std::regex_match(s, re) ? 1 : 0; - } - catch (std::regex_error &ex) {} - } - return 0; + if (size > 0) + { + try + { + std::string s((const char *)data, size); + std::regex re(s, flag); + return std::regex_match(s, re) ? 1 : 0; + } + catch (std::regex_error &ex) {} + } + return 0; } int regex_ECMAScript (const uint8_t *data, size_t size) { - (void) regex_helper(data, size, std::regex_constants::ECMAScript); - return 0; + (void) regex_helper(data, size, std::regex_constants::ECMAScript); + return 0; } int regex_POSIX (const uint8_t *data, size_t size) { - (void) regex_helper(data, size, std::regex_constants::basic); - return 0; + (void) regex_helper(data, size, std::regex_constants::basic); + return 0; } int regex_extended (const uint8_t *data, size_t size) { - (void) regex_helper(data, size, std::regex_constants::extended); - return 0; + (void) regex_helper(data, size, std::regex_constants::extended); + return 0; } int regex_awk (const uint8_t *data, size_t size) { - (void) regex_helper(data, size, std::regex_constants::awk); - return 0; + (void) regex_helper(data, size, std::regex_constants::awk); + return 0; } int regex_grep (const uint8_t *data, size_t size) { - (void) regex_helper(data, size, std::regex_constants::grep); - return 0; + (void) regex_helper(data, size, std::regex_constants::grep); + return 0; } int regex_egrep (const uint8_t *data, size_t size) { - (void) regex_helper(data, size, std::regex_constants::egrep); - return 0; + (void) regex_helper(data, size, std::regex_constants::egrep); + return 0; } -// -- heap fuzzers +// -- heap fuzzers int make_heap (const uint8_t *data, size_t size) { - Vec working(data, data + size); - std::make_heap(working.begin(), working.end()); + Vec working(data, data + size); + std::make_heap(working.begin(), working.end()); - if (!std::is_heap(working.begin(), working.end())) return 1; - if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99; - return 0; + if (!std::is_heap(working.begin(), working.end())) return 1; + if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99; + return 0; } int push_heap (const uint8_t *data, size_t size) { - if (size < 2) return 0; + if (size < 2) return 0; -// Make a heap from the first half of the data - Vec working(data, data + size); - auto iter = working.begin() + (size / 2); - std::make_heap(working.begin(), iter); - if (!std::is_heap(working.begin(), iter)) return 1; +// Make a heap from the first half of the data + Vec working(data, data + size); + auto iter = working.begin() + (size / 2); + std::make_heap(working.begin(), iter); + if (!std::is_heap(working.begin(), iter)) return 1; -// Now push the rest onto the heap, one at a time - ++iter; - for (; iter != working.end(); ++iter) { - std::push_heap(working.begin(), iter); - if (!std::is_heap(working.begin(), iter)) return 2; - } +// Now push the rest onto the heap, one at a time + ++iter; + for (; iter != working.end(); ++iter) { + std::push_heap(working.begin(), iter); + if (!std::is_heap(working.begin(), iter)) return 2; + } - if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99; - return 0; + if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99; + return 0; } int pop_heap (const uint8_t *data, size_t size) { - if (size < 2) return 0; - Vec working(data, data + size); - std::make_heap(working.begin(), working.end()); + if (size < 2) return 0; + Vec working(data, data + size); + std::make_heap(working.begin(), working.end()); -// Pop things off, one at a time - auto iter = --working.end(); - while (iter != working.begin()) { - std::pop_heap(working.begin(), iter); - if (!std::is_heap(working.begin(), --iter)) return 2; - } +// Pop things off, one at a time + auto iter = --working.end(); + while (iter != working.begin()) { + std::pop_heap(working.begin(), iter); + if (!std::is_heap(working.begin(), --iter)) return 2; + } - return 0; + return 0; } -// -- search fuzzers +// -- search fuzzers int search (const uint8_t *data, size_t size) { - if (size < 2) return 0; - - const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max(); - assert(pat_size <= size - 1); - const uint8_t *pat_begin = data + 1; - const uint8_t *pat_end = pat_begin + pat_size; - const uint8_t *data_end = data + size; - assert(pat_end <= data_end); -// std::cerr << "data[0] = " << size_t(data[0]) << " "; -// std::cerr << "Pattern size = " << pat_size << "; corpus is " << size - 1 << std::endl; - auto it = std::search(pat_end, data_end, pat_begin, pat_end); - if (it != data_end) // not found - if (!std::equal(pat_begin, pat_end, it)) - return 1; - return 0; + if (size < 2) return 0; + + const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max(); + assert(pat_size <= size - 1); + const uint8_t *pat_begin = data + 1; + const uint8_t *pat_end = pat_begin + pat_size; + const uint8_t *data_end = data + size; + assert(pat_end <= data_end); +// std::cerr << "data[0] = " << size_t(data[0]) << " "; +// std::cerr << "Pattern size = " << pat_size << "; corpus is " << size - 1 << std::endl; + auto it = std::search(pat_end, data_end, pat_begin, pat_end); + if (it != data_end) // not found + if (!std::equal(pat_begin, pat_end, it)) + return 1; + return 0; } template <typename S> static int search_helper (const uint8_t *data, size_t size) { - if (size < 2) return 0; - - const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max(); - const uint8_t *pat_begin = data + 1; - const uint8_t *pat_end = pat_begin + pat_size; - const uint8_t *data_end = data + size; - - auto it = std::search(pat_end, data_end, S(pat_begin, pat_end)); - if (it != data_end) // not found - if (!std::equal(pat_begin, pat_end, it)) - return 1; - return 0; + if (size < 2) return 0; + + const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max(); + const uint8_t *pat_begin = data + 1; + const uint8_t *pat_end = pat_begin + pat_size; + const uint8_t *data_end = data + size; + + auto it = std::search(pat_end, data_end, S(pat_begin, pat_end)); + if (it != data_end) // not found + if (!std::equal(pat_begin, pat_end, it)) + return 1; + return 0; } -// These are still in std::experimental +// These are still in std::experimental // int search_boyer_moore (const uint8_t *data, size_t size) // { -// return search_helper<std::boyer_moore_searcher<const uint8_t *>>(data, size); +// return search_helper<std::boyer_moore_searcher<const uint8_t *>>(data, size); // } -// +// // int search_boyer_moore_horspool (const uint8_t *data, size_t size) // { -// return search_helper<std::boyer_moore_horspool_searcher<const uint8_t *>>(data, size); +// return search_helper<std::boyer_moore_horspool_searcher<const uint8_t *>>(data, size); // } -// -- set operation fuzzers +// -- set operation fuzzers template <typename S> static void set_helper (const uint8_t *data, size_t size, Vec &v1, Vec &v2) { - assert(size > 1); - - const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max(); - const uint8_t *pat_begin = data + 1; - const uint8_t *pat_end = pat_begin + pat_size; - const uint8_t *data_end = data + size; - v1.assign(pat_begin, pat_end); - v2.assign(pat_end, data_end); - - std::sort(v1.begin(), v1.end()); - std::sort(v2.begin(), v2.end()); + assert(size > 1); + + const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max(); + const uint8_t *pat_begin = data + 1; + const uint8_t *pat_end = pat_begin + pat_size; + const uint8_t *data_end = data + size; + v1.assign(pat_begin, pat_end); + v2.assign(pat_end, data_end); + + std::sort(v1.begin(), v1.end()); + std::sort(v2.begin(), v2.end()); } } // namespace fuzzing diff --git a/include/CMakeLists.txt b/include/CMakeLists.txt index d9def18d725c..73f7cfc4d8e3 100644 --- a/include/CMakeLists.txt +++ b/include/CMakeLists.txt @@ -25,6 +25,7 @@ set(files any array atomic + bit bitset cassert ccomplex @@ -68,7 +69,6 @@ set(files experimental/chrono experimental/coroutine experimental/deque - experimental/dynarray experimental/filesystem experimental/forward_list experimental/functional diff --git a/include/__bit_reference b/include/__bit_reference index 3e4a21d261ff..c208af2b4d76 100644 --- a/include/__bit_reference +++ b/include/__bit_reference @@ -12,6 +12,7 @@ #define _LIBCPP___BIT_REFERENCE #include <__config> +#include <bit> #include <algorithm> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -254,18 +255,18 @@ __count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); __storage_type __dn = _VSTD::min(__clz_f, __n); __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - __r = _VSTD::__pop_count(*__first.__seg_ & __m); + __r = _VSTD::__popcount(*__first.__seg_ & __m); __n -= __dn; ++__first.__seg_; } // do middle whole words for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) - __r += _VSTD::__pop_count(*__first.__seg_); + __r += _VSTD::__popcount(*__first.__seg_); // do last partial word if (__n > 0) { __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - __r += _VSTD::__pop_count(*__first.__seg_ & __m); + __r += _VSTD::__popcount(*__first.__seg_ & __m); } return __r; } @@ -285,18 +286,18 @@ __count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_typ __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); __storage_type __dn = _VSTD::min(__clz_f, __n); __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - __r = _VSTD::__pop_count(~*__first.__seg_ & __m); + __r = _VSTD::__popcount(~*__first.__seg_ & __m); __n -= __dn; ++__first.__seg_; } // do middle whole words for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) - __r += _VSTD::__pop_count(~*__first.__seg_); + __r += _VSTD::__popcount(~*__first.__seg_); // do last partial word if (__n > 0) { __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - __r += _VSTD::__pop_count(~*__first.__seg_ & __m); + __r += _VSTD::__popcount(~*__first.__seg_ & __m); } return __r; } diff --git a/include/__config b/include/__config index 639d06c9f5d7..f0bc3483facd 100644 --- a/include/__config +++ b/include/__config @@ -33,14 +33,10 @@ # define _GNUC_VER_NEW 0 #endif -#define _LIBCPP_VERSION 7000 +#define _LIBCPP_VERSION 8000 #ifndef _LIBCPP_ABI_VERSION -# ifdef __Fuchsia__ -# define _LIBCPP_ABI_VERSION 2 -# else -# define _LIBCPP_ABI_VERSION 1 -# endif +# define _LIBCPP_ABI_VERSION 1 #endif #ifndef _LIBCPP_STD_VER @@ -99,6 +95,8 @@ // Use the smallest possible integer type to represent the index of the variant. // Previously libc++ used "unsigned int" exclusivly. # define _LIBCPP_ABI_VARIANT_INDEX_TYPE_OPTIMIZATION +// Unstable attempt to provide a more optimized std::function +# define _LIBCPP_ABI_OPTIMIZED_FUNCTION #elif _LIBCPP_ABI_VERSION == 1 # if !defined(_LIBCPP_OBJECT_FORMAT_COFF) // Enable compiling copies of now inline methods into the dylib to support @@ -123,7 +121,9 @@ #define _LIBCPP_CONCAT1(_LIBCPP_X,_LIBCPP_Y) _LIBCPP_X##_LIBCPP_Y #define _LIBCPP_CONCAT(_LIBCPP_X,_LIBCPP_Y) _LIBCPP_CONCAT1(_LIBCPP_X,_LIBCPP_Y) -#define _LIBCPP_NAMESPACE _LIBCPP_CONCAT(__,_LIBCPP_ABI_VERSION) +#ifndef _LIBCPP_ABI_NAMESPACE +# define _LIBCPP_ABI_NAMESPACE _LIBCPP_CONCAT(__,_LIBCPP_ABI_VERSION) +#endif #if __cplusplus < 201103L #define _LIBCPP_CXX03_LANG @@ -328,6 +328,43 @@ # define _LIBCPP_NO_CFI #endif +#if __ISO_C_VISIBLE >= 2011 || __cplusplus >= 201103L +# if defined(__FreeBSD__) +# define _LIBCPP_HAS_QUICK_EXIT +# define _LIBCPP_HAS_C11_FEATURES +# elif defined(__Fuchsia__) +# define _LIBCPP_HAS_QUICK_EXIT +# define _LIBCPP_HAS_TIMESPEC_GET +# define _LIBCPP_HAS_C11_FEATURES +# elif defined(__linux__) +# if !defined(_LIBCPP_HAS_MUSL_LIBC) +# if _LIBCPP_GLIBC_PREREQ(2, 15) || defined(__BIONIC__) +# define _LIBCPP_HAS_QUICK_EXIT +# endif +# if _LIBCPP_GLIBC_PREREQ(2, 17) +# define _LIBCPP_HAS_C11_FEATURES +# define _LIBCPP_HAS_TIMESPEC_GET +# endif +# else // defined(_LIBCPP_HAS_MUSL_LIBC) +# define _LIBCPP_HAS_QUICK_EXIT +# define _LIBCPP_HAS_TIMESPEC_GET +# define _LIBCPP_HAS_C11_FEATURES +# endif +# endif // __linux__ +#endif + +#ifndef _LIBCPP_CXX03_LANG +# define _LIBCPP_ALIGNOF(_Tp) alignof(_Tp) +#elif defined(_LIBCPP_COMPILER_CLANG) +# define _LIBCPP_ALIGNOF(_Tp) _Alignof(_Tp) +#else +// This definition is potentially buggy, but it's only taken with GCC in C++03, +// which we barely support anyway. See llvm.org/PR39713 +# define _LIBCPP_ALIGNOF(_Tp) __alignof(_Tp) +#endif + +#define _LIBCPP_PREFERRED_ALIGNOF(_Tp) __alignof(_Tp) + #if defined(_LIBCPP_COMPILER_CLANG) // _LIBCPP_ALTERNATE_STRING_LAYOUT is an old name for @@ -342,7 +379,7 @@ # define _ALIGNAS_TYPE(x) alignas(x) # define _ALIGNAS(x) alignas(x) #else -# define _ALIGNAS_TYPE(x) __attribute__((__aligned__(__alignof(x)))) +# define _ALIGNAS_TYPE(x) __attribute__((__aligned__(_LIBCPP_ALIGNOF(x)))) # define _ALIGNAS(x) __attribute__((__aligned__(x))) #endif @@ -430,28 +467,6 @@ typedef __char32_t char32_t; #define _LIBCPP_HAS_NO_VARIABLE_TEMPLATES #endif -#if __ISO_C_VISIBLE >= 2011 || __cplusplus >= 201103L -# if defined(__FreeBSD__) -# define _LIBCPP_HAS_QUICK_EXIT -# define _LIBCPP_HAS_C11_FEATURES -# elif defined(__Fuchsia__) -# define _LIBCPP_HAS_QUICK_EXIT -# define _LIBCPP_HAS_C11_FEATURES -# elif defined(__linux__) -# if !defined(_LIBCPP_HAS_MUSL_LIBC) -# if _LIBCPP_GLIBC_PREREQ(2, 15) || defined(__BIONIC__) -# define _LIBCPP_HAS_QUICK_EXIT -# endif -# if _LIBCPP_GLIBC_PREREQ(2, 17) -# define _LIBCPP_HAS_C11_FEATURES -# endif -# else // defined(_LIBCPP_HAS_MUSL_LIBC) -# define _LIBCPP_HAS_QUICK_EXIT -# define _LIBCPP_HAS_C11_FEATURES -# endif -# endif // __linux__ -#endif - #if !(__has_feature(cxx_noexcept)) #define _LIBCPP_HAS_NO_NOEXCEPT #endif @@ -464,16 +479,6 @@ typedef __char32_t char32_t; #define _LIBCPP_IS_LITERAL(T) __is_literal(T) #endif -// Inline namespaces are available in Clang regardless of C++ dialect. -#define _LIBCPP_BEGIN_NAMESPACE_STD namespace std {inline namespace _LIBCPP_NAMESPACE { -#define _LIBCPP_END_NAMESPACE_STD } } -#define _VSTD std::_LIBCPP_NAMESPACE - -namespace std { - inline namespace _LIBCPP_NAMESPACE { - } -} - #if !defined(_LIBCPP_HAS_NO_ASAN) && !__has_feature(address_sanitizer) #define _LIBCPP_HAS_NO_ASAN #endif @@ -493,10 +498,15 @@ namespace std { #define _LIBCPP_ALWAYS_INLINE __attribute__ ((__always_inline__)) +// No apple compilers support ""d and ""y at this time. +#if _LIBCPP_CLANG_VER < 800 || defined(__apple_build_version__) +#define _LIBCPP_HAS_NO_CXX20_CHRONO_LITERALS +#endif + #elif defined(_LIBCPP_COMPILER_GCC) #define _ALIGNAS(x) __attribute__((__aligned__(x))) -#define _ALIGNAS_TYPE(x) __attribute__((__aligned__(__alignof(x)))) +#define _ALIGNAS_TYPE(x) __attribute__((__aligned__(_LIBCPP_ALIGNOF(x)))) #define _LIBCPP_NORETURN __attribute__((noreturn)) @@ -563,15 +573,6 @@ namespace std { #endif // __GXX_EXPERIMENTAL_CXX0X__ -#define _LIBCPP_BEGIN_NAMESPACE_STD namespace std { inline namespace _LIBCPP_NAMESPACE { -#define _LIBCPP_END_NAMESPACE_STD } } -#define _VSTD std::_LIBCPP_NAMESPACE - -namespace std { - inline namespace _LIBCPP_NAMESPACE { - } -} - #if !defined(_LIBCPP_HAS_NO_ASAN) && !defined(__SANITIZE_ADDRESS__) #define _LIBCPP_HAS_NO_ASAN #endif @@ -607,13 +608,6 @@ namespace std { #define _ALIGNAS_TYPE(x) alignas(x) #define _LIBCPP_HAS_NO_VARIADICS -#define _LIBCPP_BEGIN_NAMESPACE_STD namespace std { -#define _LIBCPP_END_NAMESPACE_STD } -#define _VSTD std - -namespace std { -} - #define _LIBCPP_WEAK #define _LIBCPP_HAS_NO_ASAN @@ -625,7 +619,7 @@ namespace std { #elif defined(_LIBCPP_COMPILER_IBM) #define _ALIGNAS(x) __attribute__((__aligned__(x))) -#define _ALIGNAS_TYPE(x) __attribute__((__aligned__(__alignof(x)))) +#define _ALIGNAS_TYPE(x) __attribute__((__aligned__(_LIBCPP_ALIGNOF(x)))) #define _ATTRIBUTE(x) __attribute__((x)) #define _LIBCPP_NORETURN __attribute__((noreturn)) @@ -641,15 +635,6 @@ namespace std { #define __MULTILOCALE_API #endif -#define _LIBCPP_BEGIN_NAMESPACE_STD namespace std {inline namespace _LIBCPP_NAMESPACE { -#define _LIBCPP_END_NAMESPACE_STD } } -#define _VSTD std::_LIBCPP_NAMESPACE - -namespace std { - inline namespace _LIBCPP_NAMESPACE { - } -} - #define _LIBCPP_HAS_NO_ASAN #define _LIBCPP_ALWAYS_INLINE __attribute__ ((__always_inline__)) @@ -658,20 +643,6 @@ namespace std { #endif // _LIBCPP_COMPILER_[CLANG|GCC|MSVC|IBM] -#if _LIBCPP_STD_VER >= 17 -#define _LIBCPP_BEGIN_NAMESPACE_FILESYSTEM \ - _LIBCPP_BEGIN_NAMESPACE_STD inline namespace __fs { namespace filesystem { -#else -#define _LIBCPP_BEGIN_NAMESPACE_FILESYSTEM \ - _LIBCPP_BEGIN_NAMESPACE_STD namespace __fs { namespace filesystem { -#endif - -#define _LIBCPP_END_NAMESPACE_FILESYSTEM \ - _LIBCPP_END_NAMESPACE_STD } } - -#define _VSTD_FS _VSTD::__fs::filesystem - - #if defined(_LIBCPP_OBJECT_FORMAT_COFF) #ifdef _DLL @@ -685,33 +656,29 @@ namespace std { # define _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS # define _LIBCPP_CLASS_TEMPLATE_INSTANTIATION_VIS # define _LIBCPP_OVERRIDABLE_FUNC_VIS +# define _LIBCPP_EXPORTED_FROM_ABI #elif defined(_LIBCPP_BUILDING_LIBRARY) # define _LIBCPP_DLL_VIS __declspec(dllexport) # define _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS # define _LIBCPP_CLASS_TEMPLATE_INSTANTIATION_VIS _LIBCPP_DLL_VIS # define _LIBCPP_OVERRIDABLE_FUNC_VIS _LIBCPP_DLL_VIS +# define _LIBCPP_EXPORTED_FROM_ABI __declspec(dllexport) #else # define _LIBCPP_DLL_VIS __declspec(dllimport) # define _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS _LIBCPP_DLL_VIS # define _LIBCPP_CLASS_TEMPLATE_INSTANTIATION_VIS # define _LIBCPP_OVERRIDABLE_FUNC_VIS +# define _LIBCPP_EXPORTED_FROM_ABI __declspec(dllimport) #endif #define _LIBCPP_TYPE_VIS _LIBCPP_DLL_VIS #define _LIBCPP_FUNC_VIS _LIBCPP_DLL_VIS -#define _LIBCPP_EXTERN_VIS _LIBCPP_DLL_VIS #define _LIBCPP_EXCEPTION_ABI _LIBCPP_DLL_VIS #define _LIBCPP_HIDDEN #define _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS #define _LIBCPP_TEMPLATE_VIS #define _LIBCPP_ENUM_VIS -#if defined(_LIBCPP_COMPILER_MSVC) -# define _LIBCPP_EXTERN_TEMPLATE_INLINE_VISIBILITY __forceinline -#else -# define _LIBCPP_EXTERN_TEMPLATE_INLINE_VISIBILITY __attribute__ ((__always_inline__)) -#endif - #endif // defined(_LIBCPP_OBJECT_FORMAT_COFF) #ifndef _LIBCPP_HIDDEN @@ -759,8 +726,12 @@ namespace std { # endif #endif -#ifndef _LIBCPP_EXTERN_VIS -#define _LIBCPP_EXTERN_VIS +#ifndef _LIBCPP_EXPORTED_FROM_ABI +# if !defined(_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS) +# define _LIBCPP_EXPORTED_FROM_ABI __attribute__((__visibility__("default"))) +# else +# define _LIBCPP_EXPORTED_FROM_ABI +# endif #endif #ifndef _LIBCPP_OVERRIDABLE_FUNC_VIS @@ -801,21 +772,63 @@ namespace std { # define _LIBCPP_INTERNAL_LINKAGE _LIBCPP_ALWAYS_INLINE #endif -#ifndef _LIBCPP_HIDE_FROM_ABI -# define _LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDDEN _LIBCPP_INTERNAL_LINKAGE +#if __has_attribute(exclude_from_explicit_instantiation) +# define _LIBCPP_EXCLUDE_FROM_EXPLICIT_INSTANTIATION __attribute__ ((__exclude_from_explicit_instantiation__)) +#else + // Try to approximate the effect of exclude_from_explicit_instantiation + // (which is that entities are not assumed to be provided by explicit + // template instantitations in the dylib) by always inlining those entities. +# define _LIBCPP_EXCLUDE_FROM_EXPLICIT_INSTANTIATION _LIBCPP_ALWAYS_INLINE #endif -// Just so we can migrate to _LIBCPP_HIDE_FROM_ABI gradually. -#define _LIBCPP_INLINE_VISIBILITY _LIBCPP_HIDE_FROM_ABI +#ifndef _LIBCPP_HIDE_FROM_ABI_PER_TU +# ifndef _LIBCPP_HIDE_FROM_ABI_PER_TU_BY_DEFAULT +# define _LIBCPP_HIDE_FROM_ABI_PER_TU 0 +# else +# define _LIBCPP_HIDE_FROM_ABI_PER_TU 1 +# endif +#endif -#ifndef _LIBCPP_EXTERN_TEMPLATE_INLINE_VISIBILITY -# if !defined(_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS) -# define _LIBCPP_EXTERN_TEMPLATE_INLINE_VISIBILITY __attribute__((__visibility__("default"), __always_inline__)) +#ifndef _LIBCPP_HIDE_FROM_ABI +# if _LIBCPP_HIDE_FROM_ABI_PER_TU +# define _LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDDEN _LIBCPP_INTERNAL_LINKAGE # else -# define _LIBCPP_EXTERN_TEMPLATE_INLINE_VISIBILITY __attribute__((__always_inline__)) +# define _LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDDEN _LIBCPP_EXCLUDE_FROM_EXPLICIT_INSTANTIATION # endif #endif +#ifdef _LIBCPP_BUILDING_LIBRARY +# if _LIBCPP_ABI_VERSION > 1 +# define _LIBCPP_HIDE_FROM_ABI_AFTER_V1 _LIBCPP_HIDE_FROM_ABI +# else +# define _LIBCPP_HIDE_FROM_ABI_AFTER_V1 +# endif +#else +# define _LIBCPP_HIDE_FROM_ABI_AFTER_V1 _LIBCPP_HIDE_FROM_ABI +#endif + +// Just so we can migrate to the new macros gradually. +#define _LIBCPP_INLINE_VISIBILITY _LIBCPP_HIDE_FROM_ABI + +// Inline namespaces are available in Clang/GCC/MSVC regardless of C++ dialect. +#define _LIBCPP_BEGIN_NAMESPACE_STD namespace std { inline namespace _LIBCPP_ABI_NAMESPACE { +#define _LIBCPP_END_NAMESPACE_STD } } +#define _VSTD std::_LIBCPP_ABI_NAMESPACE +_LIBCPP_BEGIN_NAMESPACE_STD _LIBCPP_END_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 17 +#define _LIBCPP_BEGIN_NAMESPACE_FILESYSTEM \ + _LIBCPP_BEGIN_NAMESPACE_STD inline namespace __fs { namespace filesystem { +#else +#define _LIBCPP_BEGIN_NAMESPACE_FILESYSTEM \ + _LIBCPP_BEGIN_NAMESPACE_STD namespace __fs { namespace filesystem { +#endif + +#define _LIBCPP_END_NAMESPACE_FILESYSTEM \ + _LIBCPP_END_NAMESPACE_STD } } + +#define _VSTD_FS _VSTD::__fs::filesystem + #ifndef _LIBCPP_PREFERRED_OVERLOAD # if __has_attribute(__enable_if__) # define _LIBCPP_PREFERRED_OVERLOAD __attribute__ ((__enable_if__(true, ""))) @@ -976,7 +989,14 @@ template <unsigned> struct __static_assert_check {}; // If we are getting operator new from the MSVC CRT, then allocation overloads // for align_val_t were added in 19.12, aka VS 2017 version 15.3. #if defined(_LIBCPP_MSVCRT) && defined(_MSC_VER) && _MSC_VER < 1912 -#define _LIBCPP_HAS_NO_ALIGNED_ALLOCATION +# define _LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION +#elif defined(_LIBCPP_ABI_MICROSOFT) && !defined(_LIBCPP_NO_VCRUNTIME) +# define _LIBCPP_DEFER_NEW_TO_VCRUNTIME +# if !defined(__cpp_aligned_new) + // We're defering to Microsoft's STL to provide aligned new et al. We don't + // have it unless the language feature test macro is defined. +# define _LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION +# endif #endif #if defined(__APPLE__) @@ -984,13 +1004,13 @@ template <unsigned> struct __static_assert_check {}; defined(__ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__) # define __MAC_OS_X_VERSION_MIN_REQUIRED __ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__ # endif -# if defined(__MAC_OS_X_VERSION_MIN_REQUIRED) -# if __MAC_OS_X_VERSION_MIN_REQUIRED < 1060 -# define _LIBCPP_HAS_NO_ALIGNED_ALLOCATION -# endif -# endif #endif // defined(__APPLE__) +#if !defined(_LIBCPP_HAS_NO_ALIGNED_ALLOCATION) && \ + (defined(_LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION) || \ + (!defined(__cpp_aligned_new) || __cpp_aligned_new < 201606)) +# define _LIBCPP_HAS_NO_ALIGNED_ALLOCATION +#endif #if defined(__APPLE__) || defined(__FreeBSD__) #define _LIBCPP_HAS_DEFAULTRUNELOCALE @@ -1000,18 +1020,46 @@ template <unsigned> struct __static_assert_check {}; #define _LIBCPP_WCTYPE_IS_MASK #endif -#if _LIBCPP_STD_VER > 11 -# define _LIBCPP_DEPRECATED [[deprecated]] +#if _LIBCPP_STD_VER <= 17 || !defined(__cpp_char8_t) +#define _LIBCPP_NO_HAS_CHAR8_T +#endif + +// Deprecation macros. +// Deprecations warnings are only enabled when _LIBCPP_ENABLE_DEPRECATION_WARNINGS is defined. +#if defined(_LIBCPP_ENABLE_DEPRECATION_WARNINGS) +# if __has_attribute(deprecated) +# define _LIBCPP_DEPRECATED __attribute__ ((deprecated)) +# elif _LIBCPP_STD_VER > 11 +# define _LIBCPP_DEPRECATED [[deprecated]] +# else +# define _LIBCPP_DEPRECATED +# endif #else # define _LIBCPP_DEPRECATED #endif +#if !defined(_LIBCPP_CXX03_LANG) +# define _LIBCPP_DEPRECATED_IN_CXX11 _LIBCPP_DEPRECATED +#else +# define _LIBCPP_DEPRECATED_IN_CXX11 +#endif + +#if _LIBCPP_STD_VER >= 14 +# define _LIBCPP_DEPRECATED_IN_CXX14 _LIBCPP_DEPRECATED +#else +# define _LIBCPP_DEPRECATED_IN_CXX14 +#endif + +#if _LIBCPP_STD_VER >= 17 +# define _LIBCPP_DEPRECATED_IN_CXX17 _LIBCPP_DEPRECATED +#else +# define _LIBCPP_DEPRECATED_IN_CXX17 +#endif + #if _LIBCPP_STD_VER <= 11 # define _LIBCPP_EXPLICIT_AFTER_CXX11 -# define _LIBCPP_DEPRECATED_AFTER_CXX11 #else # define _LIBCPP_EXPLICIT_AFTER_CXX11 explicit -# define _LIBCPP_DEPRECATED_AFTER_CXX11 [[deprecated]] #endif #if _LIBCPP_STD_VER > 11 && !defined(_LIBCPP_HAS_NO_CXX14_CONSTEXPR) @@ -1032,8 +1080,30 @@ template <unsigned> struct __static_assert_check {}; # define _LIBCPP_CONSTEXPR_AFTER_CXX17 #endif -#if __has_cpp_attribute(nodiscard) && _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_DISABLE_NODISCARD_AFTER_CXX17) -# define _LIBCPP_NODISCARD_AFTER_CXX17 [[nodiscard]] +// The _LIBCPP_NODISCARD_ATTRIBUTE should only be used to define other +// NODISCARD macros to the correct attribute. +#if __has_cpp_attribute(nodiscard) || defined(_LIBCPP_COMPILER_MSVC) +# define _LIBCPP_NODISCARD_ATTRIBUTE [[nodiscard]] +#elif defined(_LIBCPP_COMPILER_CLANG) && !defined(_LIBCPP_CXX03_LANG) +# define _LIBCPP_NODISCARD_ATTRIBUTE [[clang::warn_unused_result]] +#else +// We can't use GCC's [[gnu::warn_unused_result]] and +// __attribute__((warn_unused_result)), because GCC does not silence them via +// (void) cast. +# define _LIBCPP_NODISCARD_ATTRIBUTE +#endif + +// _LIBCPP_NODISCARD_EXT may be used to apply [[nodiscard]] to entities not +// specified as such as an extension. +#if defined(_LIBCPP_ENABLE_NODISCARD) && !defined(_LIBCPP_DISABLE_NODISCARD_EXT) +# define _LIBCPP_NODISCARD_EXT _LIBCPP_NODISCARD_ATTRIBUTE +#else +# define _LIBCPP_NODISCARD_EXT +#endif + +#if !defined(_LIBCPP_DISABLE_NODISCARD_AFTER_CXX17) && \ + (_LIBCPP_STD_VER > 17 || defined(_LIBCPP_ENABLE_NODISCARD)) +# define _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_NODISCARD_ATTRIBUTE #else # define _LIBCPP_NODISCARD_AFTER_CXX17 #endif @@ -1090,6 +1160,7 @@ _LIBCPP_FUNC_VIS extern "C" void __sanitizer_annotate_contiguous_container( defined(__Fuchsia__) || \ defined(__NetBSD__) || \ defined(__linux__) || \ + defined(__GNU__) || \ defined(__APPLE__) || \ defined(__CloudABI__) || \ defined(__sun__) || \ @@ -1195,8 +1266,12 @@ _LIBCPP_FUNC_VIS extern "C" void __sanitizer_annotate_contiguous_container( # define _LIBCPP_DIAGNOSE_ERROR(...) #endif -#if __has_attribute(fallthough) || _GNUC_VER >= 700 // Use a function like macro to imply that it must be followed by a semicolon +#if __cplusplus > 201402L && __has_cpp_attribute(fallthrough) +# define _LIBCPP_FALLTHROUGH() [[fallthrough]] +#elif __has_cpp_attribute(clang::fallthrough) +# define _LIBCPP_FALLTHROUGH() [[clang::fallthrough]] +#elif __has_attribute(fallthough) || _GNUC_VER >= 700 # define _LIBCPP_FALLTHROUGH() __attribute__((__fallthrough__)) #else # define _LIBCPP_FALLTHROUGH() ((void)0) @@ -1250,9 +1325,15 @@ _LIBCPP_FUNC_VIS extern "C" void __sanitizer_annotate_contiguous_container( __attribute__((availability(ios,strict,introduced=10.0))) \ __attribute__((availability(tvos,strict,introduced=10.0))) \ __attribute__((availability(watchos,strict,introduced=3.0))) -# define _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS __attribute__((unavailable)) -# define _LIBCPP_AVAILABILITY_BAD_ARRAY_LENGTH __attribute__((unavailable)) -# define _LIBCPP_AVAILABILITY_BAD_ANY_CAST __attribute__((unavailable)) +# define _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS \ + __attribute__((availability(macosx,strict,introduced=10.14))) \ + __attribute__((availability(ios,strict,introduced=12.0))) \ + __attribute__((availability(tvos,strict,introduced=12.0))) \ + __attribute__((availability(watchos,strict,introduced=5.0))) +# define _LIBCPP_AVAILABILITY_BAD_VARIANT_ACCESS \ + _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS +# define _LIBCPP_AVAILABILITY_BAD_ANY_CAST \ + _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS # define _LIBCPP_AVAILABILITY_UNCAUGHT_EXCEPTIONS \ __attribute__((availability(macosx,strict,introduced=10.12))) \ __attribute__((availability(ios,strict,introduced=10.0))) \ @@ -1276,8 +1357,8 @@ _LIBCPP_FUNC_VIS extern "C" void __sanitizer_annotate_contiguous_container( __attribute__((availability(ios,strict,introduced=7.0))) #else # define _LIBCPP_AVAILABILITY_SHARED_MUTEX +# define _LIBCPP_AVAILABILITY_BAD_VARIANT_ACCESS # define _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS -# define _LIBCPP_AVAILABILITY_BAD_ARRAY_LENGTH # define _LIBCPP_AVAILABILITY_BAD_ANY_CAST # define _LIBCPP_AVAILABILITY_UNCAUGHT_EXCEPTIONS # define _LIBCPP_AVAILABILITY_SIZED_NEW_DELETE @@ -1289,26 +1370,30 @@ _LIBCPP_FUNC_VIS extern "C" void __sanitizer_annotate_contiguous_container( // Define availability that depends on _LIBCPP_NO_EXCEPTIONS. #ifdef _LIBCPP_NO_EXCEPTIONS -# define _LIBCPP_AVAILABILITY_DYNARRAY # define _LIBCPP_AVAILABILITY_FUTURE # define _LIBCPP_AVAILABILITY_THROW_BAD_ANY_CAST +# define _LIBCPP_AVAILABILITY_THROW_BAD_OPTIONAL_ACCESS +# define _LIBCPP_AVAILABILITY_THROW_BAD_VARIANT_ACCESS #else -# define _LIBCPP_AVAILABILITY_DYNARRAY _LIBCPP_AVAILABILITY_BAD_ARRAY_LENGTH -# define _LIBCPP_AVAILABILITY_FUTURE _LIBCPP_AVAILABILITY_FUTURE_ERROR -# define _LIBCPP_AVAILABILITY_THROW_BAD_ANY_CAST \ - _LIBCPP_AVAILABILITY_BAD_ANY_CAST -#endif - -// Availability of stream API in the dylib got dropped and re-added. The -// extern template should effectively be available at: -// availability(macosx,introduced=10.9) -// availability(ios,introduced=7.0) -#if defined(_LIBCPP_USE_AVAILABILITY_APPLE) && \ +# define _LIBCPP_AVAILABILITY_FUTURE _LIBCPP_AVAILABILITY_FUTURE_ERROR +# define _LIBCPP_AVAILABILITY_THROW_BAD_ANY_CAST _LIBCPP_AVAILABILITY_BAD_ANY_CAST +# define _LIBCPP_AVAILABILITY_THROW_BAD_OPTIONAL_ACCESS _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS +# define _LIBCPP_AVAILABILITY_THROW_BAD_VARIANT_ACCESS _LIBCPP_AVAILABILITY_BAD_VARIANT_ACCESS +#endif + +// The stream API was dropped and re-added in the dylib shipped on macOS +// and iOS. We can only assume the dylib to provide these definitions for +// macosx >= 10.9 and ios >= 7.0. Otherwise, the definitions are available +// from the headers, but not from the dylib. Explicit instantiation +// declarations for streams exist conditionally to this; if we provide +// an explicit instantiation declaration and we try to deploy to a dylib +// that does not provide those symbols, we'll get a load-time error. +#if !defined(_LIBCPP_BUILDING_LIBRARY) && \ ((defined(__ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__) && \ __ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__ < 1090) || \ (defined(__ENVIRONMENT_IPHONE_OS_VERSION_MIN_REQUIRED__) && \ __ENVIRONMENT_IPHONE_OS_VERSION_MIN_REQUIRED__ < 70000)) -#define _LIBCPP_AVAILABILITY_NO_STREAMS_EXTERN_TEMPLATE +# define _LIBCPP_DO_NOT_ASSUME_STREAMS_EXPLICIT_INSTANTIATION_IN_DYLIB #endif #if defined(_LIBCPP_COMPILER_IBM) @@ -1351,6 +1436,8 @@ _LIBCPP_FUNC_VIS extern "C" void __sanitizer_annotate_contiguous_container( # endif // defined(_LIBCPP_ABI_MICROSOFT) && !defined(_LIBCPP_BUILDING_LIBRARY) #endif // _LIBCPP_NO_AUTO_LINK +#define _LIBCPP_UNUSED_VAR(x) ((void)(x)) + #endif // __cplusplus #endif // _LIBCPP_CONFIG diff --git a/include/__config_site.in b/include/__config_site.in index 8d980ff57cc8..580a6aa4c07b 100644 --- a/include/__config_site.in +++ b/include/__config_site.in @@ -14,6 +14,7 @@ #cmakedefine _LIBCPP_ABI_UNSTABLE #cmakedefine _LIBCPP_ABI_FORCE_ITANIUM #cmakedefine _LIBCPP_ABI_FORCE_MICROSOFT +#cmakedefine _LIBCPP_HIDE_FROM_ABI_PER_TU_BY_DEFAULT #cmakedefine _LIBCPP_HAS_NO_GLOBAL_FILESYSTEM_NAMESPACE #cmakedefine _LIBCPP_HAS_NO_STDIN #cmakedefine _LIBCPP_HAS_NO_STDOUT @@ -27,6 +28,7 @@ #cmakedefine _LIBCPP_HAS_THREAD_LIBRARY_EXTERNAL #cmakedefine _LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS #cmakedefine _LIBCPP_NO_VCRUNTIME +#cmakedefine _LIBCPP_ABI_NAMESPACE @_LIBCPP_ABI_NAMESPACE@ @_LIBCPP_ABI_DEFINES@ diff --git a/include/__debug b/include/__debug index d01bacdf7edc..a8788f68f8f4 100644 --- a/include/__debug +++ b/include/__debug @@ -74,7 +74,7 @@ typedef void(*__libcpp_debug_function_type)(__libcpp_debug_info const&); /// __libcpp_debug_function - The handler function called when a _LIBCPP_ASSERT /// fails. -extern _LIBCPP_EXTERN_VIS __libcpp_debug_function_type __libcpp_debug_function; +extern _LIBCPP_EXPORTED_FROM_ABI __libcpp_debug_function_type __libcpp_debug_function; /// __libcpp_abort_debug_function - A debug handler that aborts when called. _LIBCPP_NORETURN _LIBCPP_FUNC_VIS diff --git a/include/__functional_base b/include/__functional_base index 57fdf2b9f663..032be99bf6a5 100644 --- a/include/__functional_base +++ b/include/__functional_base @@ -50,7 +50,7 @@ template <class _Tp> #endif struct _LIBCPP_TEMPLATE_VIS less : binary_function<_Tp, _Tp, bool> { - _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY + _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY bool operator()(const _Tp& __x, const _Tp& __y) const {return __x < __y;} }; @@ -59,7 +59,7 @@ struct _LIBCPP_TEMPLATE_VIS less : binary_function<_Tp, _Tp, bool> template <> struct _LIBCPP_TEMPLATE_VIS less<void> { - template <class _T1, class _T2> + template <class _T1, class _T2> _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY auto operator()(_T1&& __t, _T2&& __u) const _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) < _VSTD::forward<_T2>(__u))) @@ -552,7 +552,7 @@ template <class _Tp, class, class = void> struct __is_transparent : false_type {}; template <class _Tp, class _Up> -struct __is_transparent<_Tp, _Up, +struct __is_transparent<_Tp, _Up, typename __void_t<typename _Tp::is_transparent>::type> : true_type {}; #endif @@ -562,7 +562,7 @@ struct __is_transparent<_Tp, _Up, struct _LIBCPP_TEMPLATE_VIS allocator_arg_t { }; #if defined(_LIBCPP_CXX03_LANG) || defined(_LIBCPP_BUILDING_LIBRARY) -extern const allocator_arg_t allocator_arg; +extern _LIBCPP_EXPORTED_FROM_ABI const allocator_arg_t allocator_arg; #else /* _LIBCPP_INLINE_VAR */ constexpr allocator_arg_t allocator_arg = allocator_arg_t(); #endif diff --git a/include/__hash_table b/include/__hash_table index c77de961be6b..6f5b183105e6 100644 --- a/include/__hash_table +++ b/include/__hash_table @@ -35,15 +35,6 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Key, class _Tp> struct __hash_value_type; -template <class _Key, class _Cp, class _Hash, - bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value> -class __unordered_map_hasher; - -template <class _Key, class _Cp, class _Pred, - bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value - > -class __unordered_map_equal; - #ifndef _LIBCPP_CXX03_LANG template <class _Tp> struct __is_hash_value_type_imp : false_type {}; @@ -418,7 +409,7 @@ public: _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this)); } - _LIBCPP_INLINE_VISIBILITY + _LIBCPP_INLINE_VISIBILITY __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT : __node_(__x.__node_) { @@ -871,35 +862,32 @@ struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc> }; #endif +template <class _Key, class _Hash, class _Equal> +struct __enforce_unordered_container_requirements { #ifndef _LIBCPP_CXX03_LANG -template <class _Key, class _Hash, class _Equal, class _Alloc> -struct __diagnose_hash_table_helper { - static constexpr bool __trigger_diagnostics() - _LIBCPP_DIAGNOSE_WARNING(__check_hash_requirements<_Key, _Hash>::value - && !__invokable<_Hash const&, _Key const&>::value, - "the specified hash functor does not provide a const call operator") - _LIBCPP_DIAGNOSE_WARNING(is_copy_constructible<_Equal>::value - && !__invokable<_Equal const&, _Key const&, _Key const&>::value, - "the specified comparator type does not provide a const call operator") - { static_assert(__check_hash_requirements<_Key, _Hash>::value, - "the specified hash does not meet the Hash requirements"); + "the specified hash does not meet the Hash requirements"); static_assert(is_copy_constructible<_Equal>::value, - "the specified comparator is required to be copy constructible"); - return true; - } + "the specified comparator is required to be copy constructible"); +#endif + typedef int type; }; -template <class _Key, class _Value, class _Hash, class _Equal, class _Alloc> -struct __diagnose_hash_table_helper< - __hash_value_type<_Key, _Value>, - __unordered_map_hasher<_Key, __hash_value_type<_Key, _Value>, _Hash>, - __unordered_map_equal<_Key, __hash_value_type<_Key, _Value>, _Equal>, - _Alloc> -: __diagnose_hash_table_helper<_Key, _Hash, _Equal, _Alloc> -{ -}; -#endif // _LIBCPP_CXX03_LANG +template <class _Key, class _Hash, class _Equal> +#ifndef _LIBCPP_CXX03_LANG + _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value, + "the specified comparator type does not provide a const call operator") + _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value, + "the specified hash functor does not provide a const call operator") +#endif +typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type +__diagnose_unordered_container_requirements(int); + +// This dummy overload is used so that the compiler won't emit a spurious +// "no matching function for call to __diagnose_unordered_xxx" diagnostic +// when the overload above causes a hard error. +template <class _Key, class _Hash, class _Equal> +int __diagnose_unordered_container_requirements(void*); template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table @@ -963,10 +951,6 @@ private: typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; -#ifndef _LIBCPP_CXX03_LANG - static_assert(__diagnose_hash_table_helper<_Tp, _Hash, _Equal, _Alloc>::__trigger_diagnostics(), ""); -#endif - // --- Member data begin --- __bucket_list __bucket_list_; __compressed_pair<__first_node, __node_allocator> __p1_; @@ -1058,8 +1042,26 @@ public: ); } +private: + _LIBCPP_INLINE_VISIBILITY + __next_pointer __node_insert_multi_prepare(size_t __cp_hash, + value_type& __cp_val); + _LIBCPP_INLINE_VISIBILITY + void __node_insert_multi_perform(__node_pointer __cp, + __next_pointer __pn) _NOEXCEPT; + + _LIBCPP_INLINE_VISIBILITY + __next_pointer __node_insert_unique_prepare(size_t __nd_hash, + value_type& __nd_val); + _LIBCPP_INLINE_VISIBILITY + void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT; + +public: + _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __node_insert_unique(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); @@ -1170,6 +1172,9 @@ public: _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh); + template <class _Table> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Table& __source); template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -1177,6 +1182,9 @@ public: template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh); + template <class _Table> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Table& __source); template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -1849,73 +1857,112 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT } } + +// Prepare the container for an insertion of the value __value with the hash +// __hash. This does a lookup into the container to see if __value is already +// present, and performs a rehash if necessary. Returns a pointer to the +// existing element if it exists, otherwise nullptr. +// +// Note that this function does forward exceptions if key_eq() throws, and never +// mutates __value or actually inserts into the map. template <class _Tp, class _Hash, class _Equal, class _Alloc> -pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) +_LIBCPP_INLINE_VISIBILITY +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare( + size_t __hash, value_type& __value) { - __nd->__hash_ = hash_function()(__nd->__value_); size_type __bc = bucket_count(); - bool __inserted = false; - __next_pointer __ndptr; - size_t __chash; + if (__bc != 0) { - __chash = __constrain_hash(__nd->__hash_, __bc); - __ndptr = __bucket_list_[__chash]; + size_t __chash = __constrain_hash(__hash, __bc); + __next_pointer __ndptr = __bucket_list_[__chash]; if (__ndptr != nullptr) { for (__ndptr = __ndptr->__next_; __ndptr != nullptr && __constrain_hash(__ndptr->__hash(), __bc) == __chash; __ndptr = __ndptr->__next_) { - if (key_eq()(__ndptr->__upcast()->__value_, __nd->__value_)) - goto __done; + if (key_eq()(__ndptr->__upcast()->__value_, __value)) + return __ndptr; } } } + if (size()+1 > __bc * max_load_factor() || __bc == 0) { - if (size()+1 > __bc * max_load_factor() || __bc == 0) - { - rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), - size_type(ceil(float(size() + 1) / max_load_factor())))); - __bc = bucket_count(); - __chash = __constrain_hash(__nd->__hash_, __bc); - } - // insert_after __bucket_list_[__chash], or __first_node if bucket is null - __next_pointer __pn = __bucket_list_[__chash]; - if (__pn == nullptr) - { - __pn =__p1_.first().__ptr(); - __nd->__next_ = __pn->__next_; - __pn->__next_ = __nd->__ptr(); - // fix up __bucket_list_ - __bucket_list_[__chash] = __pn; - if (__nd->__next_ != nullptr) - __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr(); - } - else - { - __nd->__next_ = __pn->__next_; - __pn->__next_ = __nd->__ptr(); - } - __ndptr = __nd->__ptr(); - // increment size - ++size(); + rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), + size_type(ceil(float(size() + 1) / max_load_factor())))); + } + return nullptr; +} + +// Insert the node __nd into the container by pushing it into the right bucket, +// and updating size(). Assumes that __nd->__hash is up-to-date, and that +// rehashing has already occurred and that no element with the same key exists +// in the map. +template <class _Tp, class _Hash, class _Equal, class _Alloc> +_LIBCPP_INLINE_VISIBILITY +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform( + __node_pointer __nd) _NOEXCEPT +{ + size_type __bc = bucket_count(); + size_t __chash = __constrain_hash(__nd->__hash(), __bc); + // insert_after __bucket_list_[__chash], or __first_node if bucket is null + __next_pointer __pn = __bucket_list_[__chash]; + if (__pn == nullptr) + { + __pn =__p1_.first().__ptr(); + __nd->__next_ = __pn->__next_; + __pn->__next_ = __nd->__ptr(); + // fix up __bucket_list_ + __bucket_list_[__chash] = __pn; + if (__nd->__next_ != nullptr) + __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr(); + } + else + { + __nd->__next_ = __pn->__next_; + __pn->__next_ = __nd->__ptr(); + } + ++size(); +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) +{ + __nd->__hash_ = hash_function()(__nd->__value_); + __next_pointer __existing_node = + __node_insert_unique_prepare(__nd->__hash(), __nd->__value_); + + // Insert the node, unless it already exists in the container. + bool __inserted = false; + if (__existing_node == nullptr) + { + __node_insert_unique_perform(__nd); + __existing_node = __nd->__ptr(); __inserted = true; } -__done: #if _LIBCPP_DEBUG_LEVEL >= 2 - return pair<iterator, bool>(iterator(__ndptr, this), __inserted); + return pair<iterator, bool>(iterator(__existing_node, this), __inserted); #else - return pair<iterator, bool>(iterator(__ndptr), __inserted); + return pair<iterator, bool>(iterator(__existing_node), __inserted); #endif } +// Prepare the container for an insertion of the value __cp_val with the hash +// __cp_hash. This does a lookup into the container to see if __cp_value is +// already present, and performs a rehash if necessary. Returns a pointer to the +// last occurance of __cp_val in the map. +// +// Note that this function does forward exceptions if key_eq() throws, and never +// mutates __value or actually inserts into the map. template <class _Tp, class _Hash, class _Equal, class _Alloc> -typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( + size_t __cp_hash, value_type& __cp_val) { - __cp->__hash_ = hash_function()(__cp->__value_); size_type __bc = bucket_count(); if (size()+1 > __bc * max_load_factor() || __bc == 0) { @@ -1923,20 +1970,9 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c size_type(ceil(float(size() + 1) / max_load_factor())))); __bc = bucket_count(); } - size_t __chash = __constrain_hash(__cp->__hash_, __bc); + size_t __chash = __constrain_hash(__cp_hash, __bc); __next_pointer __pn = __bucket_list_[__chash]; - if (__pn == nullptr) - { - __pn =__p1_.first().__ptr(); - __cp->__next_ = __pn->__next_; - __pn->__next_ = __cp->__ptr(); - // fix up __bucket_list_ - __bucket_list_[__chash] = __pn; - if (__cp->__next_ != nullptr) - __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)] - = __cp->__ptr(); - } - else + if (__pn != nullptr) { for (bool __found = false; __pn->__next_ != nullptr && __constrain_hash(__pn->__next_->__hash(), __bc) == __chash; @@ -1947,8 +1983,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c // true true loop // false true set __found to true // true false break - if (__found != (__pn->__next_->__hash() == __cp->__hash_ && - key_eq()(__pn->__next_->__upcast()->__value_, __cp->__value_))) + if (__found != (__pn->__next_->__hash() == __cp_hash && + key_eq()(__pn->__next_->__upcast()->__value_, __cp_val))) { if (!__found) __found = true; @@ -1956,6 +1992,35 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c break; } } + } + return __pn; +} + +// Insert the node __cp into the container after __pn (which is the last node in +// the bucket that compares equal to __cp). Rehashing, and checking for +// uniqueness has already been performed (in __node_insert_multi_prepare), so +// all we need to do is update the bucket and size(). Assumes that __cp->__hash +// is up-to-date. +template <class _Tp, class _Hash, class _Equal, class _Alloc> +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform( + __node_pointer __cp, __next_pointer __pn) _NOEXCEPT +{ + size_type __bc = bucket_count(); + size_t __chash = __constrain_hash(__cp->__hash_, __bc); + if (__pn == nullptr) + { + __pn =__p1_.first().__ptr(); + __cp->__next_ = __pn->__next_; + __pn->__next_ = __cp->__ptr(); + // fix up __bucket_list_ + __bucket_list_[__chash] = __pn; + if (__cp->__next_ != nullptr) + __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)] + = __cp->__ptr(); + } + else + { __cp->__next_ = __pn->__next_; __pn->__next_ = __cp->__ptr(); if (__cp->__next_ != nullptr) @@ -1966,6 +2031,17 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c } } ++size(); +} + + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) +{ + __cp->__hash_ = hash_function()(__cp->__value_); + __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__value_); + __node_insert_multi_perform(__cp, __pn); + #if _LIBCPP_DEBUG_LEVEL >= 2 return iterator(__cp->__ptr(), this); #else @@ -2217,6 +2293,32 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( } template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _Table> +_LIBCPP_INLINE_VISIBILITY +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique( + _Table& __source) +{ + static_assert(is_same<__node, typename _Table::__node>::value, ""); + + for (typename _Table::iterator __it = __source.begin(); + __it != __source.end();) + { + __node_pointer __src_ptr = __it.__node_->__upcast(); + size_t __hash = hash_function()(__src_ptr->__value_); + __next_pointer __existing_node = + __node_insert_unique_prepare(__hash, __src_ptr->__value_); + auto __prev_iter = __it++; + if (__existing_node == nullptr) + { + (void)__source.remove(__prev_iter).release(); + __src_ptr->__hash_ = __hash; + __node_insert_unique_perform(__src_ptr); + } + } +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator @@ -2244,6 +2346,27 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( return __result; } +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _Table> +_LIBCPP_INLINE_VISIBILITY +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi( + _Table& __source) +{ + static_assert(is_same<typename _Table::__node, __node>::value, ""); + + for (typename _Table::iterator __it = __source.begin(); + __it != __source.end();) + { + __node_pointer __src_ptr = __it.__node_->__upcast(); + size_t __src_hash = hash_function()(__src_ptr->__value_); + __next_pointer __pn = + __node_insert_multi_prepare(__src_hash, __src_ptr->__value_); + (void)__source.remove(__it++).release(); + __src_ptr->__hash_ = __src_hash; + __node_insert_multi_perform(__src_ptr, __pn); + } +} #endif // _LIBCPP_STD_VER > 14 template <class _Tp, class _Hash, class _Equal, class _Alloc> diff --git a/include/__libcpp_version b/include/__libcpp_version index 2bdc6533bec7..e002b3628b34 100644 --- a/include/__libcpp_version +++ b/include/__libcpp_version @@ -1 +1 @@ -7000 +8000 diff --git a/include/__locale b/include/__locale index f43e7b4303d3..cde9cc85f6b5 100644 --- a/include/__locale +++ b/include/__locale @@ -1255,13 +1255,13 @@ struct __narrow_to_utf8<8> }; template <> -struct __narrow_to_utf8<16> +struct _LIBCPP_TEMPLATE_VIS __narrow_to_utf8<16> : public codecvt<char16_t, char, mbstate_t> { _LIBCPP_INLINE_VISIBILITY __narrow_to_utf8() : codecvt<char16_t, char, mbstate_t>(1) {} - ~__narrow_to_utf8(); + _LIBCPP_EXPORTED_FROM_ABI ~__narrow_to_utf8(); template <class _OutputIterator, class _CharT> _LIBCPP_INLINE_VISIBILITY @@ -1289,13 +1289,13 @@ struct __narrow_to_utf8<16> }; template <> -struct __narrow_to_utf8<32> +struct _LIBCPP_TEMPLATE_VIS __narrow_to_utf8<32> : public codecvt<char32_t, char, mbstate_t> { _LIBCPP_INLINE_VISIBILITY __narrow_to_utf8() : codecvt<char32_t, char, mbstate_t>(1) {} - ~__narrow_to_utf8(); + _LIBCPP_EXPORTED_FROM_ABI ~__narrow_to_utf8(); template <class _OutputIterator, class _CharT> _LIBCPP_INLINE_VISIBILITY @@ -1345,13 +1345,13 @@ struct __widen_from_utf8<8> }; template <> -struct __widen_from_utf8<16> +struct _LIBCPP_TEMPLATE_VIS __widen_from_utf8<16> : public codecvt<char16_t, char, mbstate_t> { _LIBCPP_INLINE_VISIBILITY __widen_from_utf8() : codecvt<char16_t, char, mbstate_t>(1) {} - ~__widen_from_utf8(); + _LIBCPP_EXPORTED_FROM_ABI ~__widen_from_utf8(); template <class _OutputIterator> _LIBCPP_INLINE_VISIBILITY @@ -1379,13 +1379,13 @@ struct __widen_from_utf8<16> }; template <> -struct __widen_from_utf8<32> +struct _LIBCPP_TEMPLATE_VIS __widen_from_utf8<32> : public codecvt<char32_t, char, mbstate_t> { _LIBCPP_INLINE_VISIBILITY __widen_from_utf8() : codecvt<char32_t, char, mbstate_t>(1) {} - ~__widen_from_utf8(); + _LIBCPP_EXPORTED_FROM_ABI ~__widen_from_utf8(); template <class _OutputIterator> _LIBCPP_INLINE_VISIBILITY diff --git a/include/__mutex_base b/include/__mutex_base index 4659ca9298c9..da21a5f8eb6a 100644 --- a/include/__mutex_base +++ b/include/__mutex_base @@ -76,9 +76,9 @@ struct _LIBCPP_TYPE_VIS adopt_lock_t {}; #if defined(_LIBCPP_CXX03_LANG) || defined(_LIBCPP_BUILDING_LIBRARY) -extern const defer_lock_t defer_lock; -extern const try_to_lock_t try_to_lock; -extern const adopt_lock_t adopt_lock; +extern _LIBCPP_EXPORTED_FROM_ABI const defer_lock_t defer_lock; +extern _LIBCPP_EXPORTED_FROM_ABI const try_to_lock_t try_to_lock; +extern _LIBCPP_EXPORTED_FROM_ABI const adopt_lock_t adopt_lock; #else diff --git a/include/__node_handle b/include/__node_handle index fe09f3c1e51c..a9cf3b7217a3 100644 --- a/include/__node_handle +++ b/include/__node_handle @@ -26,8 +26,6 @@ _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER > 14 -#define __cpp_lib_node_extract 201606L - // Specialized in __tree & __hash_table for their _NodeType. template <class _NodeType, class _Alloc> struct __generic_container_node_destructor; diff --git a/include/__sso_allocator b/include/__sso_allocator index 40027363a185..8aca0495d756 100644 --- a/include/__sso_allocator +++ b/include/__sso_allocator @@ -55,14 +55,14 @@ public: __allocated_ = true; return (pointer)&buf_; } - return static_cast<pointer>(_VSTD::__libcpp_allocate(__n * sizeof(_Tp), __alignof(_Tp))); + return static_cast<pointer>(_VSTD::__libcpp_allocate(__n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp))); } - _LIBCPP_INLINE_VISIBILITY void deallocate(pointer __p, size_type) + _LIBCPP_INLINE_VISIBILITY void deallocate(pointer __p, size_type __n) { if (__p == (pointer)&buf_) __allocated_ = false; else - _VSTD::__libcpp_deallocate(__p, __alignof(_Tp)); + _VSTD::__libcpp_deallocate(__p, __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp)); } _LIBCPP_INLINE_VISIBILITY size_type max_size() const throw() {return size_type(~0) / sizeof(_Tp);} diff --git a/include/__string b/include/__string index 44c55987f9f7..1ddeec7149fb 100644 --- a/include/__string +++ b/include/__string @@ -47,6 +47,7 @@ struct char_traits template <> struct char_traits<char>; template <> struct char_traits<wchar_t>; +template <> struct char_traits<char8_t>; // c++20 } // std @@ -389,6 +390,102 @@ char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __ } +#ifndef _LIBCPP_NO_HAS_CHAR8_T + +template <> +struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t> +{ + typedef char8_t char_type; + typedef unsigned int int_type; + typedef streamoff off_type; + typedef u8streampos pos_type; + typedef mbstate_t state_type; + + static inline constexpr void assign(char_type& __c1, const char_type& __c2) noexcept + {__c1 = __c2;} + static inline constexpr bool eq(char_type __c1, char_type __c2) noexcept + {return __c1 == __c2;} + static inline constexpr bool lt(char_type __c1, char_type __c2) noexcept + {return __c1 < __c2;} + + static constexpr + int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT; + + static constexpr + size_t length(const char_type* __s) _NOEXCEPT; + + _LIBCPP_INLINE_VISIBILITY static constexpr + const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT; + + static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT + {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);} + + static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT + { + _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range"); + return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n); + } + + static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT + {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);} + + static inline constexpr int_type not_eof(int_type __c) noexcept + {return eq_int_type(__c, eof()) ? ~eof() : __c;} + static inline constexpr char_type to_char_type(int_type __c) noexcept + {return char_type(__c);} + static inline constexpr int_type to_int_type(char_type __c) noexcept + {return int_type(__c);} + static inline constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept + {return __c1 == __c2;} + static inline constexpr int_type eof() noexcept + {return int_type(EOF);} +}; + +// TODO use '__builtin_strlen' if it ever supports char8_t ?? +inline constexpr +size_t +char_traits<char8_t>::length(const char_type* __s) _NOEXCEPT +{ + size_t __len = 0; + for (; !eq(*__s, char_type(0)); ++__s) + ++__len; + return __len; +} + +inline constexpr +int +char_traits<char8_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT +{ +#if __has_feature(cxx_constexpr_string_builtins) + return __builtin_memcmp(__s1, __s2, __n); +#else + for (; __n; --__n, ++__s1, ++__s2) + { + if (lt(*__s1, *__s2)) + return -1; + if (lt(*__s2, *__s1)) + return 1; + } + return 0; +#endif +} + +// TODO use '__builtin_char_memchr' if it ever supports char8_t ?? +inline constexpr +const char8_t* +char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT +{ + for (; __n; --__n) + { + if (eq(*__s, __a)) + return __s; + ++__s; + } + return 0; +} + +#endif // #_LIBCPP_NO_HAS_CHAR8_T + #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS template <> diff --git a/include/__threading_support b/include/__threading_support index 3c1eff22f530..202490062729 100644 --- a/include/__threading_support +++ b/include/__threading_support @@ -70,7 +70,7 @@ typedef pthread_t __libcpp_thread_id; typedef pthread_t __libcpp_thread_t; -// Thrad Local Storage +// Thread Local Storage typedef pthread_key_t __libcpp_tls_key; #define _LIBCPP_TLS_DESTRUCTOR_CC diff --git a/include/__tree b/include/__tree index af9b9616df8a..814851085b98 100644 --- a/include/__tree +++ b/include/__tree @@ -40,10 +40,6 @@ template <class _Tp, class _VoidPtr> class __tree_node; template <class _Key, class _Value> struct __value_type; -template <class _Key, class _CP, class _Compare, - bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value> -class __map_value_compare; - template <class _Allocator> class __map_node_destructor; template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_iterator; template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_const_iterator; @@ -857,7 +853,7 @@ public: __tree_iterator operator--(int) {__tree_iterator __t(*this); --(*this); return __t;} - friend _LIBCPP_INLINE_VISIBILITY + friend _LIBCPP_INLINE_VISIBILITY bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) {return __x.__ptr_ == __y.__ptr_;} friend _LIBCPP_INLINE_VISIBILITY @@ -966,24 +962,12 @@ private: }; +template<class _Tp, class _Compare> #ifndef _LIBCPP_CXX03_LANG -template <class _Tp, class _Compare, class _Allocator> -struct __diagnose_tree_helper { - static constexpr bool __trigger_diagnostics() - _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Compare const&, _Tp const&, _Tp const&>::value, - "the specified comparator type does not provide a const call operator") - { return true; } -}; - -template <class _Key, class _Value, class _KeyComp, class _Alloc> -struct __diagnose_tree_helper< - __value_type<_Key, _Value>, - __map_value_compare<_Key, __value_type<_Key, _Value>, _KeyComp>, - _Alloc -> : __diagnose_tree_helper<_Key, _KeyComp, _Alloc> -{ -}; -#endif // !_LIBCPP_CXX03_LANG + _LIBCPP_DIAGNOSE_WARNING(!std::__invokable<_Compare const&, _Tp const&, _Tp const&>::value, + "the specified comparator type does not provide a const call operator") +#endif +int __diagnose_non_const_comparator(); template <class _Tp, class _Compare, class _Allocator> class __tree @@ -1341,15 +1325,20 @@ public: #endif // !_LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __node_insert_unique(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_unique(const_iterator __p, __node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); - _LIBCPP_INLINE_VISIBILITY iterator __remove_node_pointer(__node_pointer); + _LIBCPP_INLINE_VISIBILITY iterator + __remove_node_pointer(__node_pointer) _NOEXCEPT; #if _LIBCPP_STD_VER > 14 template <class _NodeHandle, class _InsertReturnType> @@ -1358,6 +1347,9 @@ public: template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); + template <class _Tree> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Tree& __source); template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -1365,6 +1357,9 @@ public: template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); + template <class _Tree> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Tree& __source); template <class _NodeHandle> @@ -1384,7 +1379,7 @@ public: void __insert_node_at(__parent_pointer __parent, __node_base_pointer& __child, - __node_base_pointer __new_node); + __node_base_pointer __new_node) _NOEXCEPT; template <class _Key> iterator find(const _Key& __v); @@ -1488,7 +1483,7 @@ private: void __copy_assign_alloc(const __tree& __t, true_type) { if (__node_alloc() != __t.__node_alloc()) - clear(); + clear(); __node_alloc() = __t.__node_alloc(); } _LIBCPP_INLINE_VISIBILITY @@ -1830,7 +1825,7 @@ __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) __node_traits::propagate_on_container_move_assignment::value && is_nothrow_move_assignable<value_compare>::value && is_nothrow_move_assignable<__node_allocator>::value) - + { __move_assign(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>()); @@ -1844,10 +1839,6 @@ __tree<_Tp, _Compare, _Allocator>::~__tree() { static_assert((is_copy_constructible<value_compare>::value), "Comparator must be copy-constructible."); -#ifndef _LIBCPP_CXX03_LANG - static_assert((__diagnose_tree_helper<_Tp, _Compare, _Allocator>:: - __trigger_diagnostics()), ""); -#endif destroy(__root()); } @@ -2129,10 +2120,9 @@ __tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, } template <class _Tp, class _Compare, class _Allocator> -void -__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__parent_pointer __parent, - __node_base_pointer& __child, - __node_base_pointer __new_node) +void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( + __parent_pointer __parent, __node_base_pointer& __child, + __node_base_pointer __new_node) _NOEXCEPT { __new_node->__left_ = nullptr; __new_node->__right_ = nullptr; @@ -2384,7 +2374,7 @@ __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) +__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT { iterator __r(__ptr); ++__r; @@ -2472,6 +2462,30 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p) } template <class _Tp, class _Compare, class _Allocator> +template <class _Tree> +_LIBCPP_INLINE_VISIBILITY +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) +{ + static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); + + for (typename _Tree::iterator __i = __source.begin(); + __i != __source.end();) + { + __node_pointer __src_ptr = __i.__get_np(); + __parent_pointer __parent; + __node_base_pointer& __child = + __find_equal(__parent, _NodeTypes::__get_key(__src_ptr->__value_)); + ++__i; + if (__child != nullptr) + continue; + __source.__remove_node_pointer(__src_ptr); + __insert_node_at(__parent, __child, + static_cast<__node_base_pointer>(__src_ptr)); + } +} + +template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY typename __tree<_Tp, _Compare, _Allocator>::iterator @@ -2507,6 +2521,28 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi( return iterator(__ptr); } +template <class _Tp, class _Compare, class _Allocator> +template <class _Tree> +_LIBCPP_INLINE_VISIBILITY +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) +{ + static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); + + for (typename _Tree::iterator __i = __source.begin(); + __i != __source.end();) + { + __node_pointer __src_ptr = __i.__get_np(); + __parent_pointer __parent; + __node_base_pointer& __child = __find_leaf_high( + __parent, _NodeTypes::__get_key(__src_ptr->__value_)); + ++__i; + __source.__remove_node_pointer(__src_ptr); + __insert_node_at(__parent, __child, + static_cast<__node_base_pointer>(__src_ptr)); + } +} + #endif // _LIBCPP_STD_VER > 14 template <class _Tp, class _Compare, class _Allocator> diff --git a/include/__tuple b/include/__tuple index 69d6ee961113..3b23d78afa1b 100644 --- a/include/__tuple +++ b/include/__tuple @@ -22,36 +22,36 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _Tp> class _LIBCPP_TEMPLATE_VIS tuple_size; +template <class _Tp> struct _LIBCPP_TEMPLATE_VIS tuple_size; #if !defined(_LIBCPP_CXX03_LANG) template <class _Tp, class...> using __enable_if_tuple_size_imp = _Tp; template <class _Tp> -class _LIBCPP_TEMPLATE_VIS tuple_size<__enable_if_tuple_size_imp< +struct _LIBCPP_TEMPLATE_VIS tuple_size<__enable_if_tuple_size_imp< const _Tp, typename enable_if<!is_volatile<_Tp>::value>::type, integral_constant<size_t, sizeof(tuple_size<_Tp>)>>> : public integral_constant<size_t, tuple_size<_Tp>::value> {}; template <class _Tp> -class _LIBCPP_TEMPLATE_VIS tuple_size<__enable_if_tuple_size_imp< +struct _LIBCPP_TEMPLATE_VIS tuple_size<__enable_if_tuple_size_imp< volatile _Tp, typename enable_if<!is_const<_Tp>::value>::type, integral_constant<size_t, sizeof(tuple_size<_Tp>)>>> : public integral_constant<size_t, tuple_size<_Tp>::value> {}; template <class _Tp> -class _LIBCPP_TEMPLATE_VIS tuple_size<__enable_if_tuple_size_imp< +struct _LIBCPP_TEMPLATE_VIS tuple_size<__enable_if_tuple_size_imp< const volatile _Tp, integral_constant<size_t, sizeof(tuple_size<_Tp>)>>> : public integral_constant<size_t, tuple_size<_Tp>::value> {}; #else -template <class _Tp> class _LIBCPP_TEMPLATE_VIS tuple_size<const _Tp> : public tuple_size<_Tp> {}; -template <class _Tp> class _LIBCPP_TEMPLATE_VIS tuple_size<volatile _Tp> : public tuple_size<_Tp> {}; -template <class _Tp> class _LIBCPP_TEMPLATE_VIS tuple_size<const volatile _Tp> : public tuple_size<_Tp> {}; +template <class _Tp> struct _LIBCPP_TEMPLATE_VIS tuple_size<const _Tp> : public tuple_size<_Tp> {}; +template <class _Tp> struct _LIBCPP_TEMPLATE_VIS tuple_size<volatile _Tp> : public tuple_size<_Tp> {}; +template <class _Tp> struct _LIBCPP_TEMPLATE_VIS tuple_size<const volatile _Tp> : public tuple_size<_Tp> {}; #endif template <size_t _Ip, class _Tp> class _LIBCPP_TEMPLATE_VIS tuple_element; @@ -165,7 +165,7 @@ template <class ..._Tp> class _LIBCPP_TEMPLATE_VIS tuple; template <class... _Tp> struct __tuple_like<tuple<_Tp...> > : true_type {}; template <class ..._Tp> -class _LIBCPP_TEMPLATE_VIS tuple_size<tuple<_Tp...> > +struct _LIBCPP_TEMPLATE_VIS tuple_size<tuple<_Tp...> > : public integral_constant<size_t, sizeof...(_Tp)> { }; @@ -291,7 +291,7 @@ public: template <class ..._Tp> -class _LIBCPP_TEMPLATE_VIS tuple_size<__tuple_types<_Tp...> > +struct _LIBCPP_TEMPLATE_VIS tuple_size<__tuple_types<_Tp...> > : public integral_constant<size_t, sizeof...(_Tp)> { }; diff --git a/include/algorithm b/include/algorithm index 90f1d246c63d..d102899f2dfc 100644 --- a/include/algorithm +++ b/include/algorithm @@ -645,13 +645,8 @@ template <class BidirectionalIterator, class Compare> #include <functional> #include <iterator> #include <cstddef> - -#if defined(__IBMCPP__) -#include "support/ibm/support.h" -#endif -#if defined(_LIBCPP_COMPILER_MSVC) -#include <intrin.h> -#endif +#include <bit> +#include <version> #include <__debug> @@ -755,6 +750,32 @@ public: bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);} }; +// Perform division by two quickly for positive integers (llvm.org/PR39129) + +template <typename _Integral> +_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +typename enable_if +< + is_integral<_Integral>::value, + _Integral +>::type +__half_positive(_Integral __value) +{ + return static_cast<_Integral>(static_cast<typename make_unsigned<_Integral>::type>(__value) / 2); +} + +template <typename _Tp> +_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +typename enable_if +< + !is_integral<_Tp>::value, + _Tp +>::type +__half_positive(_Tp __value) +{ + return __value / 2; +} + #ifdef _LIBCPP_DEBUG template <class _Compare> @@ -788,135 +809,6 @@ struct __debug_less #endif // _LIBCPP_DEBUG -// Precondition: __x != 0 -inline _LIBCPP_INLINE_VISIBILITY -unsigned __ctz(unsigned __x) { -#ifndef _LIBCPP_COMPILER_MSVC - return static_cast<unsigned>(__builtin_ctz(__x)); -#else - static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); - static_assert(sizeof(unsigned long) == 4, ""); - unsigned long where; - // Search from LSB to MSB for first set bit. - // Returns zero if no set bit is found. - if (_BitScanForward(&where, __x)) - return where; - return 32; -#endif -} - -inline _LIBCPP_INLINE_VISIBILITY -unsigned long __ctz(unsigned long __x) { -#ifndef _LIBCPP_COMPILER_MSVC - return static_cast<unsigned long>(__builtin_ctzl(__x)); -#else - static_assert(sizeof(unsigned long) == sizeof(unsigned), ""); - return __ctz(static_cast<unsigned>(__x)); -#endif -} - -inline _LIBCPP_INLINE_VISIBILITY -unsigned long long __ctz(unsigned long long __x) { -#ifndef _LIBCPP_COMPILER_MSVC - return static_cast<unsigned long long>(__builtin_ctzll(__x)); -#else - unsigned long where; -// Search from LSB to MSB for first set bit. -// Returns zero if no set bit is found. -#if defined(_LIBCPP_HAS_BITSCAN64) - (defined(_M_AMD64) || defined(__x86_64__)) - if (_BitScanForward64(&where, __x)) - return static_cast<int>(where); -#else - // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls. - // Scan the Low Word. - if (_BitScanForward(&where, static_cast<unsigned long>(__x))) - return where; - // Scan the High Word. - if (_BitScanForward(&where, static_cast<unsigned long>(__x >> 32))) - return where + 32; // Create a bit offset from the LSB. -#endif - return 64; -#endif // _LIBCPP_COMPILER_MSVC -} - -// Precondition: __x != 0 -inline _LIBCPP_INLINE_VISIBILITY -unsigned __clz(unsigned __x) { -#ifndef _LIBCPP_COMPILER_MSVC - return static_cast<unsigned>(__builtin_clz(__x)); -#else - static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); - static_assert(sizeof(unsigned long) == 4, ""); - unsigned long where; - // Search from LSB to MSB for first set bit. - // Returns zero if no set bit is found. - if (_BitScanReverse(&where, __x)) - return 31 - where; - return 32; // Undefined Behavior. -#endif -} - -inline _LIBCPP_INLINE_VISIBILITY -unsigned long __clz(unsigned long __x) { -#ifndef _LIBCPP_COMPILER_MSVC - return static_cast<unsigned long>(__builtin_clzl (__x)); -#else - static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); - return __clz(static_cast<unsigned>(__x)); -#endif -} - -inline _LIBCPP_INLINE_VISIBILITY -unsigned long long __clz(unsigned long long __x) { -#ifndef _LIBCPP_COMPILER_MSVC - return static_cast<unsigned long long>(__builtin_clzll(__x)); -#else - unsigned long where; -// BitScanReverse scans from MSB to LSB for first set bit. -// Returns 0 if no set bit is found. -#if defined(_LIBCPP_HAS_BITSCAN64) - if (_BitScanReverse64(&where, __x)) - return static_cast<int>(63 - where); -#else - // Scan the high 32 bits. - if (_BitScanReverse(&where, static_cast<unsigned long>(__x >> 32))) - return 63 - (where + 32); // Create a bit offset from the MSB. - // Scan the low 32 bits. - if (_BitScanReverse(&where, static_cast<unsigned long>(__x))) - return 63 - where; -#endif - return 64; // Undefined Behavior. -#endif // _LIBCPP_COMPILER_MSVC -} - -inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) { -#ifndef _LIBCPP_COMPILER_MSVC - return __builtin_popcount (__x); -#else - static_assert(sizeof(unsigned) == 4, ""); - return __popcnt(__x); -#endif -} - -inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) { -#ifndef _LIBCPP_COMPILER_MSVC - return __builtin_popcountl (__x); -#else - static_assert(sizeof(unsigned long) == 4, ""); - return __popcnt(__x); -#endif -} - -inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) { -#ifndef _LIBCPP_COMPILER_MSVC - return __builtin_popcountll(__x); -#else - static_assert(sizeof(unsigned long long) == 8, ""); - return __popcnt64(__x); -#endif -} - // all_of template <class _InputIterator, class _Predicate> @@ -2533,6 +2425,8 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { + static_assert(__is_forward_iterator<_ForwardIterator>::value, + "std::min_element requires a ForwardIterator"); if (__first != __last) { _ForwardIterator __i = __first; @@ -2597,6 +2491,8 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { + static_assert(__is_forward_iterator<_ForwardIterator>::value, + "std::max_element requires a ForwardIterator"); if (__first != __last) { _ForwardIterator __i = __first; @@ -2683,6 +2579,8 @@ _LIBCPP_CONSTEXPR_AFTER_CXX11 std::pair<_ForwardIterator, _ForwardIterator> minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { + static_assert(__is_forward_iterator<_ForwardIterator>::value, + "std::minmax_element requires a ForwardIterator"); std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first); if (__first != __last) { @@ -3027,10 +2925,11 @@ template<class _IntType> template<class _URNG> typename uniform_int_distribution<_IntType>::result_type uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p) +_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK { typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t), uint32_t, uint64_t>::type _UIntType; - const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1); + const _UIntType _Rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1); if (_Rp == 1) return __p.a(); const size_t _Dt = numeric_limits<_UIntType>::digits; @@ -3080,7 +2979,7 @@ public: _LIBCPP_FUNC_VIS __rs_default __rs_get(); template <class _RandomAccessIterator> -void +_LIBCPP_DEPRECATED_IN_CXX14 void random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; @@ -3101,7 +3000,7 @@ random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) } template <class _RandomAccessIterator, class _RandomNumberGenerator> -void +_LIBCPP_DEPRECATED_IN_CXX14 void random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, #ifndef _LIBCPP_CXX03_LANG _RandomNumberGenerator&& __rand) @@ -3116,7 +3015,8 @@ random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, for (--__last; __first < __last; ++__first, --__d) { difference_type __i = __rand(__d); - swap(*__first, *(__first + __i)); + if (__i != difference_type(0)) + swap(*__first, *(__first + __i)); } } } @@ -3328,7 +3228,7 @@ partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __ difference_type __len = _VSTD::distance(__first, __last); while (__len != 0) { - difference_type __l2 = __len / 2; + difference_type __l2 = _VSTD::__half_positive(__len); _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); if (__pred(*__m)) @@ -3737,6 +3637,7 @@ __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, // stable, 4-10 compares, 0-9 swaps template <class _Compare, class _ForwardIterator> +_LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) @@ -4195,7 +4096,7 @@ __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va difference_type __len = _VSTD::distance(__first, __last); while (__len != 0) { - difference_type __l2 = __len / 2; + difference_type __l2 = _VSTD::__half_positive(__len); _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); if (__comp(*__m, __value_)) @@ -4214,14 +4115,8 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { -#ifdef _LIBCPP_DEBUG - typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; - __debug_less<_Compare> __c(__comp); - return __lower_bound<_Comp_ref>(__first, __last, __value_, __c); -#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp); -#endif // _LIBCPP_DEBUG } template <class _ForwardIterator, class _Tp> @@ -4243,7 +4138,7 @@ __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va difference_type __len = _VSTD::distance(__first, __last); while (__len != 0) { - difference_type __l2 = __len / 2; + difference_type __l2 = _VSTD::__half_positive(__len); _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); if (__comp(__value_, *__m)) @@ -4262,14 +4157,8 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { -#ifdef _LIBCPP_DEBUG - typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; - __debug_less<_Compare> __c(__comp); - return __upper_bound<_Comp_ref>(__first, __last, __value_, __c); -#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp); -#endif // _LIBCPP_DEBUG } template <class _ForwardIterator, class _Tp> @@ -4291,7 +4180,7 @@ __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va difference_type __len = _VSTD::distance(__first, __last); while (__len != 0) { - difference_type __l2 = __len / 2; + difference_type __l2 = _VSTD::__half_positive(__len); _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); if (__comp(*__m, __value_)) diff --git a/include/any b/include/any index 9bd2f53c5601..781eee7869c0 100644 --- a/include/any +++ b/include/any @@ -87,13 +87,14 @@ namespace std { #include <typeinfo> #include <type_traits> #include <cstdlib> +#include <version> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif namespace std { -class _LIBCPP_EXCEPTION_ABI bad_any_cast : public bad_cast +class _LIBCPP_EXCEPTION_ABI _LIBCPP_AVAILABILITY_BAD_ANY_CAST bad_any_cast : public bad_cast { public: virtual const char* what() const _NOEXCEPT; @@ -105,12 +106,13 @@ _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER > 14 _LIBCPP_NORETURN inline _LIBCPP_INLINE_VISIBILITY +_LIBCPP_AVAILABILITY_THROW_BAD_ANY_CAST void __throw_bad_any_cast() { #ifndef _LIBCPP_NO_EXCEPTIONS throw bad_any_cast(); #else - _VSTD::abort(); + _VSTD::abort(); #endif } @@ -576,6 +578,7 @@ any make_any(initializer_list<_Up> __il, _Args&&... __args) { template <class _ValueType> inline _LIBCPP_INLINE_VISIBILITY +_LIBCPP_AVAILABILITY_THROW_BAD_ANY_CAST _ValueType any_cast(any const & __v) { using _RawValueType = __uncvref_t<_ValueType>; @@ -590,6 +593,7 @@ _ValueType any_cast(any const & __v) template <class _ValueType> inline _LIBCPP_INLINE_VISIBILITY +_LIBCPP_AVAILABILITY_THROW_BAD_ANY_CAST _ValueType any_cast(any & __v) { using _RawValueType = __uncvref_t<_ValueType>; @@ -604,6 +608,7 @@ _ValueType any_cast(any & __v) template <class _ValueType> inline _LIBCPP_INLINE_VISIBILITY +_LIBCPP_AVAILABILITY_THROW_BAD_ANY_CAST _ValueType any_cast(any && __v) { using _RawValueType = __uncvref_t<_ValueType>; diff --git a/include/array b/include/array index 1e6a650198b5..56f6887655aa 100644 --- a/include/array +++ b/include/array @@ -91,7 +91,7 @@ template <class T, size_t N> template <class T, size_t N > void swap(array<T,N>& x, array<T,N>& y) noexcept(noexcept(x.swap(y))); // C++17 -template <class T> class tuple_size; +template <class T> struct tuple_size; template <size_t I, class T> class tuple_element; template <class T, size_t N> struct tuple_size<array<T, N>>; template <size_t I, class T, size_t N> struct tuple_element<I, array<T, N>>; @@ -112,6 +112,7 @@ template <size_t I, class T, size_t N> const T&& get(const array<T, N>&&) noexce #include <algorithm> #include <stdexcept> #include <cstdlib> // for _LIBCPP_UNREACHABLE +#include <version> #include <__debug> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -367,7 +368,7 @@ array(_Tp, _Args...) template <class _Tp, size_t _Size> inline _LIBCPP_INLINE_VISIBILITY -bool +_LIBCPP_CONSTEXPR_AFTER_CXX17 bool operator==(const array<_Tp, _Size>& __x, const array<_Tp, _Size>& __y) { return _VSTD::equal(__x.begin(), __x.end(), __y.begin()); @@ -375,7 +376,7 @@ operator==(const array<_Tp, _Size>& __x, const array<_Tp, _Size>& __y) template <class _Tp, size_t _Size> inline _LIBCPP_INLINE_VISIBILITY -bool +_LIBCPP_CONSTEXPR_AFTER_CXX17 bool operator!=(const array<_Tp, _Size>& __x, const array<_Tp, _Size>& __y) { return !(__x == __y); @@ -383,7 +384,7 @@ operator!=(const array<_Tp, _Size>& __x, const array<_Tp, _Size>& __y) template <class _Tp, size_t _Size> inline _LIBCPP_INLINE_VISIBILITY -bool +_LIBCPP_CONSTEXPR_AFTER_CXX17 bool operator<(const array<_Tp, _Size>& __x, const array<_Tp, _Size>& __y) { return _VSTD::lexicographical_compare(__x.begin(), __x.end(), @@ -392,7 +393,7 @@ operator<(const array<_Tp, _Size>& __x, const array<_Tp, _Size>& __y) template <class _Tp, size_t _Size> inline _LIBCPP_INLINE_VISIBILITY -bool +_LIBCPP_CONSTEXPR_AFTER_CXX17 bool operator>(const array<_Tp, _Size>& __x, const array<_Tp, _Size>& __y) { return __y < __x; @@ -400,7 +401,7 @@ operator>(const array<_Tp, _Size>& __x, const array<_Tp, _Size>& __y) template <class _Tp, size_t _Size> inline _LIBCPP_INLINE_VISIBILITY -bool +_LIBCPP_CONSTEXPR_AFTER_CXX17 bool operator<=(const array<_Tp, _Size>& __x, const array<_Tp, _Size>& __y) { return !(__y < __x); @@ -408,7 +409,7 @@ operator<=(const array<_Tp, _Size>& __x, const array<_Tp, _Size>& __y) template <class _Tp, size_t _Size> inline _LIBCPP_INLINE_VISIBILITY -bool +_LIBCPP_CONSTEXPR_AFTER_CXX17 bool operator>=(const array<_Tp, _Size>& __x, const array<_Tp, _Size>& __y) { return !(__x < __y); @@ -429,7 +430,7 @@ swap(array<_Tp, _Size>& __x, array<_Tp, _Size>& __y) } template <class _Tp, size_t _Size> -class _LIBCPP_TEMPLATE_VIS tuple_size<array<_Tp, _Size> > +struct _LIBCPP_TEMPLATE_VIS tuple_size<array<_Tp, _Size> > : public integral_constant<size_t, _Size> {}; template <size_t _Ip, class _Tp, size_t _Size> diff --git a/include/atomic b/include/atomic index 809f78a06d36..d37e7b4b035c 100644 --- a/include/atomic +++ b/include/atomic @@ -544,6 +544,7 @@ void atomic_signal_fence(memory_order m) noexcept; #include <cstddef> #include <cstdint> #include <type_traits> +#include <version> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header @@ -559,10 +560,6 @@ void atomic_signal_fence(memory_order m) noexcept; #error C++ standard library is incompatible with <stdatomic.h> #endif -#if _LIBCPP_STD_VER > 14 -# define __cpp_lib_atomic_is_always_lock_free 201603L -#endif - #define _LIBCPP_CHECK_STORE_MEMORY_ORDER(__m) \ _LIBCPP_DIAGNOSE_WARNING(__m == memory_order_consume || \ __m == memory_order_acquire || \ diff --git a/include/bit b/include/bit new file mode 100644 index 000000000000..db3812e5b5b2 --- /dev/null +++ b/include/bit @@ -0,0 +1,158 @@ +// -*- C++ -*- +//===------------------------------ bit ----------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===---------------------------------------------------------------------===// + +#ifndef _LIBCPP_BIT +#define _LIBCPP_BIT + +/* + bit synopsis + +namespace std { + +} // namespace std + +*/ + +#include <__config> +#include <version> + +#if defined(__IBMCPP__) +#include "support/ibm/support.h" +#endif +#if defined(_LIBCPP_COMPILER_MSVC) +#include <intrin.h> +#endif + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#ifndef _LIBCPP_COMPILER_MSVC + +inline _LIBCPP_INLINE_VISIBILITY +int __ctz(unsigned __x) { return __builtin_ctz(__x); } + +inline _LIBCPP_INLINE_VISIBILITY +int __ctz(unsigned long __x) { return __builtin_ctzl(__x); } + +inline _LIBCPP_INLINE_VISIBILITY +int __ctz(unsigned long long __x) { return __builtin_ctzll(__x); } + + +inline _LIBCPP_INLINE_VISIBILITY +int __clz(unsigned __x) { return __builtin_clz(__x); } + +inline _LIBCPP_INLINE_VISIBILITY +int __clz(unsigned long __x) { return __builtin_clzl(__x); } + +inline _LIBCPP_INLINE_VISIBILITY +int __clz(unsigned long long __x) { return __builtin_clzll(__x); } + + +inline _LIBCPP_INLINE_VISIBILITY +int __popcount(unsigned __x) { return __builtin_popcount(__x); } + +inline _LIBCPP_INLINE_VISIBILITY +int __popcount(unsigned long __x) { return __builtin_popcountl(__x); } + +inline _LIBCPP_INLINE_VISIBILITY +int __popcount(unsigned long long __x) { return __builtin_popcountll(__x); } + +#else // _LIBCPP_COMPILER_MSVC + +// Precondition: __x != 0 +inline _LIBCPP_INLINE_VISIBILITY +int __ctz(unsigned __x) { + static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); + static_assert(sizeof(unsigned long) == 4, ""); + unsigned long __where; + if (_BitScanForward(&__where, __x)) + return static_cast<int>(__where); + return 32; +} + +inline _LIBCPP_INLINE_VISIBILITY +int __ctz(unsigned long __x) { + static_assert(sizeof(unsigned long) == sizeof(unsigned), ""); + return __ctz(static_cast<unsigned>(__x)); +} + +inline _LIBCPP_INLINE_VISIBILITY +int __ctz(unsigned long long __x) { + unsigned long __where; +#if defined(_LIBCPP_HAS_BITSCAN64) + (defined(_M_AMD64) || defined(__x86_64__)) + if (_BitScanForward64(&__where, __x)) + return static_cast<int>(__where); +#else + // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls. + if (_BitScanForward(&__where, static_cast<unsigned long>(__x))) + return static_cast<int>(__where); + if (_BitScanForward(&__where, static_cast<unsigned long>(__x >> 32))) + return static_cast<int>(__where + 32); +#endif + return 64; +} + +// Precondition: __x != 0 +inline _LIBCPP_INLINE_VISIBILITY +int __clz(unsigned __x) { + static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); + static_assert(sizeof(unsigned long) == 4, ""); + unsigned long __where; + if (_BitScanReverse(&__where, __x)) + return static_cast<int>(31 - __where); + return 32; // Undefined Behavior. +} + +inline _LIBCPP_INLINE_VISIBILITY +int __clz(unsigned long __x) { + static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); + return __clz(static_cast<unsigned>(__x)); +} + +inline _LIBCPP_INLINE_VISIBILITY +int __clz(unsigned long long __x) { + unsigned long __where; +#if defined(_LIBCPP_HAS_BITSCAN64) + if (_BitScanReverse64(&__where, __x)) + return static_cast<int>(63 - __where); +#else + // Win32 doesn't have _BitScanReverse64 so emulate it with two 32 bit calls. + if (_BitScanReverse(&__where, static_cast<unsigned long>(__x >> 32))) + return static_cast<int>(63 - (__where + 32)); + if (_BitScanReverse(&__where, static_cast<unsigned long>(__x))) + return static_cast<int>(63 - __where); +#endif + return 64; // Undefined Behavior. +} + +inline _LIBCPP_INLINE_VISIBILITY int __popcount(unsigned __x) { + static_assert(sizeof(unsigned) == 4, ""); + return __popcnt(__x); +} + +inline _LIBCPP_INLINE_VISIBILITY int __popcount(unsigned long __x) { + static_assert(sizeof(unsigned long) == 4, ""); + return __popcnt(__x); +} + +inline _LIBCPP_INLINE_VISIBILITY int __popcount(unsigned long long __x) { + static_assert(sizeof(unsigned long long) == 8, ""); + return __popcnt64(__x); +} + +#endif // _LIBCPP_COMPILER_MSVC + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_BIT diff --git a/include/bitset b/include/bitset index cd6c289b4c48..98947e027c1c 100644 --- a/include/bitset +++ b/include/bitset @@ -238,9 +238,9 @@ __bitset<_N_words, _Size>::__init(unsigned long long __v, false_type) _NOEXCEPT size_t __sz = _Size; for (size_t __i = 0; __i < sizeof(__t)/sizeof(__t[0]); ++__i, __v >>= __bits_per_word, __sz -= __bits_per_word ) if ( __sz < __bits_per_word) - __t[__i] = static_cast<__storage_type>(__v) & ( 1ULL << __sz ) - 1; + __t[__i] = static_cast<__storage_type>(__v) & ( 1ULL << __sz ) - 1; else - __t[__i] = static_cast<__storage_type>(__v); + __t[__i] = static_cast<__storage_type>(__v); _VSTD::copy(__t, __t + sizeof(__t)/sizeof(__t[0]), __first_); _VSTD::fill(__first_ + sizeof(__t)/sizeof(__t[0]), __first_ + sizeof(__first_)/sizeof(__first_[0]), @@ -254,7 +254,7 @@ __bitset<_N_words, _Size>::__init(unsigned long long __v, true_type) _NOEXCEPT { __first_[0] = __v; if (_Size < __bits_per_word) - __first_[0] &= ( 1ULL << _Size ) - 1; + __first_[0] &= ( 1ULL << _Size ) - 1; _VSTD::fill(__first_ + 1, __first_ + sizeof(__first_)/sizeof(__first_[0]), __storage_type(0)); } @@ -269,9 +269,9 @@ __bitset<_N_words, _Size>::__bitset(unsigned long long __v) _NOEXCEPT #if __SIZEOF_SIZE_T__ == 8 : __first_{__v} #elif __SIZEOF_SIZE_T__ == 4 - : __first_{static_cast<__storage_type>(__v), - _Size >= 2 * __bits_per_word ? static_cast<__storage_type>(__v >> __bits_per_word) - : static_cast<__storage_type>((__v >> __bits_per_word) & (__storage_type(1) << (_Size - __bits_per_word)) - 1)} + : __first_{static_cast<__storage_type>(__v), + _Size >= 2 * __bits_per_word ? static_cast<__storage_type>(__v >> __bits_per_word) + : static_cast<__storage_type>((__v >> __bits_per_word) & (__storage_type(1) << (_Size - __bits_per_word)) - 1)} #else #error This constructor has not been ported to this platform #endif @@ -991,7 +991,7 @@ inline size_t bitset<_Size>::count() const _NOEXCEPT { - return static_cast<size_t>(_VSTD::count(base::__make_iter(0), base::__make_iter(_Size), true)); + return static_cast<size_t>(__count_bool_true(base::__make_iter(0), _Size)); } template <size_t _Size> diff --git a/include/charconv b/include/charconv index 7cb790e1beec..064f2e11c3f3 100644 --- a/include/charconv +++ b/include/charconv @@ -87,8 +87,16 @@ namespace std { #pragma GCC system_header #endif +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + _LIBCPP_BEGIN_NAMESPACE_STD +namespace __itoa { +_LIBCPP_FUNC_VIS char* __u64toa(uint64_t __value, char* __buffer); +_LIBCPP_FUNC_VIS char* __u32toa(uint32_t __value, char* __buffer); +} + #if _LIBCPP_STD_VER > 11 enum class _LIBCPP_ENUM_VIS chars_format @@ -147,9 +155,6 @@ static constexpr uint32_t __pow10_32[] = { UINT32_C(1000000000), }; -_LIBCPP_FUNC_VIS char* __u64toa(uint64_t __value, char* __buffer); -_LIBCPP_FUNC_VIS char* __u32toa(uint32_t __value, char* __buffer); - template <typename _Tp, typename = void> struct _LIBCPP_HIDDEN __traits_base { @@ -607,4 +612,6 @@ from_chars(const char* __first, const char* __last, _Tp& __value, int __base) _LIBCPP_END_NAMESPACE_STD +_LIBCPP_POP_MACROS + #endif // _LIBCPP_CHARCONV diff --git a/include/chrono b/include/chrono index f6a6f4b24343..96759f9860ee 100644 --- a/include/chrono +++ b/include/chrono @@ -33,9 +33,9 @@ template <class Rep> struct duration_values { public: - static constexpr Rep zero(); - static constexpr Rep max(); - static constexpr Rep min(); + static constexpr Rep zero(); // noexcept in C++20 + static constexpr Rep max(); // noexcept in C++20 + static constexpr Rep min(); // noexcept in C++20 }; // duration @@ -77,22 +77,24 @@ public: constexpr common_type<duration>::type operator+() const; constexpr common_type<duration>::type operator-() const; - constexpr duration& operator++(); - constexpr duration operator++(int); - constexpr duration& operator--(); - constexpr duration operator--(int); + constexpr duration& operator++(); // constexpr in C++17 + constexpr duration operator++(int); // constexpr in C++17 + constexpr duration& operator--(); // constexpr in C++17 + constexpr duration operator--(int); // constexpr in C++17 - constexpr duration& operator+=(const duration& d); - constexpr duration& operator-=(const duration& d); + constexpr duration& operator+=(const duration& d); // constexpr in C++17 + constexpr duration& operator-=(const duration& d); // constexpr in C++17 - duration& operator*=(const rep& rhs); - duration& operator/=(const rep& rhs); + duration& operator*=(const rep& rhs); // constexpr in C++17 + duration& operator/=(const rep& rhs); // constexpr in C++17 + duration& operator%=(const rep& rhs); // constexpr in C++17 + duration& operator%=(const duration& rhs); // constexpr in C++17 // special values - static constexpr duration zero(); - static constexpr duration min(); - static constexpr duration max(); + static constexpr duration zero(); // noexcept in C++20 + static constexpr duration min(); // noexcept in C++20 + static constexpr duration max(); // noexcept in C++20 }; typedef duration<long long, nano> nanoseconds; @@ -127,13 +129,13 @@ public: // arithmetic - time_point& operator+=(const duration& d); - time_point& operator-=(const duration& d); + time_point& operator+=(const duration& d); // constexpr in C++17 + time_point& operator-=(const duration& d); // constexpr in C++17 // special values - static constexpr time_point min(); - static constexpr time_point max(); + static constexpr time_point min(); // noexcept in C++20 + static constexpr time_point max(); // noexcept in C++20 }; } // chrono @@ -323,7 +325,7 @@ struct clock_time_conversion; template<class DestClock, class SourceClock, class Duration> auto clock_cast(const time_point<SourceClock, Duration>& t); - + // 25.8.2, class last_spec // C++20 struct last_spec; @@ -528,7 +530,7 @@ constexpr year_month_weekday_last operator-(const year_month_weekday_last& ymwdl, const months& dm) noexcept; constexpr year_month_weekday_last operator-(const year_month_weekday_last& ymwdl, const years& dy) noexcept; - + // 25.8.18, civil calendar conventional syntax operators // C++20 constexpr year_month operator/(const year& y, const month& m) noexcept; @@ -609,7 +611,7 @@ constexpr year_month_weekday_last constexpr year_month_weekday_last operator/(const month_weekday_last& mwdl, const year& y) noexcept; constexpr year_month_weekday_last - operator/(const month_weekday_last& mwdl, int y) noexcept; + operator/(const month_weekday_last& mwdl, int y) noexcept; // 25.9, class template time_of_day // C++20 template<class Duration> class time_of_day; @@ -640,7 +642,7 @@ class ambiguous_local_time; // 25.10.4, information classes // C++20 struct sys_info; struct local_info; - + // 25.10.5, class time_zone // C++20 enum class choose {earliest, latest}; class time_zone; @@ -650,7 +652,7 @@ bool operator<(const time_zone& x, const time_zone& y) noexcept; bool operator>(const time_zone& x, const time_zone& y) noexcept; bool operator<=(const time_zone& x, const time_zone& y) noexcept; bool operator>=(const time_zone& x, const time_zone& y) noexcept; - + // 25.10.6, class template zoned_traits // C++20 template<class T> struct zoned_traits; @@ -724,7 +726,7 @@ template<class charT, class traits, class Alloc, class Streamable> template<class charT, class traits, class Alloc, class Streamable> basic_string<charT, traits, Alloc> format(const locale& loc, const basic_string<charT, traits, Alloc>& fmt, - const Streamable& s); + const Streamable& s); // 25.12, parsing // C++20 template<class charT, class traits, class Alloc, class Parsable> @@ -746,7 +748,8 @@ unspecified parse(const basic_string<charT, traits, Alloc>& format, Parsable& tp, basic_string<charT, traits, Alloc>& abbrev, minutes& offset); -inline constexpr last_spec last{}; // C++20 +// calendrical constants +inline constexpr last_spec last{}; // C++20 inline constexpr chrono::weekday Sunday{0}; // C++20 inline constexpr chrono::weekday Monday{1}; // C++20 inline constexpr chrono::weekday Tuesday{2}; // C++20 @@ -796,6 +799,7 @@ constexpr chrono::year operator ""y(unsigned lo #include <type_traits> #include <ratio> #include <limits> +#include <version> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header @@ -804,6 +808,11 @@ constexpr chrono::year operator ""y(unsigned lo _LIBCPP_PUSH_MACROS #include <__undef_macros> +#ifndef _LIBCPP_CXX03_LANG +_LIBCPP_BEGIN_NAMESPACE_FILESYSTEM +struct _FilesystemClock; +_LIBCPP_END_NAMESPACE_FILESYSTEM +#endif // !_LIBCPP_CXX03_LANG _LIBCPP_BEGIN_NAMESPACE_STD @@ -920,9 +929,9 @@ template <class _Rep> struct _LIBCPP_TEMPLATE_VIS duration_values { public: - _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR _Rep zero() {return _Rep(0);} - _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR _Rep max() {return numeric_limits<_Rep>::max();} - _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR _Rep min() {return numeric_limits<_Rep>::lowest();} + _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR _Rep zero() _NOEXCEPT {return _Rep(0);} + _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR _Rep max() _NOEXCEPT {return numeric_limits<_Rep>::max();} + _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR _Rep min() _NOEXCEPT {return numeric_limits<_Rep>::lowest();} }; #if _LIBCPP_STD_VER > 14 @@ -1015,7 +1024,7 @@ class _LIBCPP_TEMPLATE_VIS duration typedef ratio<__mul<__n1, __d2, !value>::value, __mul<__n2, __d1, !value>::value> type; }; - + public: typedef _Rep rep; typedef typename _Period::type period; @@ -1077,9 +1086,9 @@ public: // special values - _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR duration zero() {return duration(duration_values<rep>::zero());} - _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR duration min() {return duration(duration_values<rep>::min());} - _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR duration max() {return duration(duration_values<rep>::max());} + _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR duration zero() _NOEXCEPT {return duration(duration_values<rep>::zero());} + _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR duration min() _NOEXCEPT {return duration(duration_values<rep>::min());} + _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR duration max() _NOEXCEPT {return duration(duration_values<rep>::max());} }; typedef duration<long long, nano> nanoseconds; @@ -1088,7 +1097,12 @@ typedef duration<long long, milli> milliseconds; typedef duration<long long > seconds; typedef duration< long, ratio< 60> > minutes; typedef duration< long, ratio<3600> > hours; - +#if _LIBCPP_STD_VER > 17 +typedef duration< int, ratio_multiply<ratio<24>, hours::period>> days; +typedef duration< int, ratio_multiply<ratio<7>, days::period>> weeks; +typedef duration< int, ratio_multiply<ratio<146097, 400>, days::period>> years; +typedef duration< int, ratio_divide<years::period, ratio<12>>> months; +#endif // Duration == template <class _LhsDuration, class _RhsDuration> @@ -1355,13 +1369,13 @@ public: // arithmetic - _LIBCPP_INLINE_VISIBILITY time_point& operator+=(const duration& __d) {__d_ += __d; return *this;} - _LIBCPP_INLINE_VISIBILITY time_point& operator-=(const duration& __d) {__d_ -= __d; return *this;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 time_point& operator+=(const duration& __d) {__d_ += __d; return *this;} + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 time_point& operator-=(const duration& __d) {__d_ -= __d; return *this;} // special values - _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR time_point min() {return time_point(duration::min());} - _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR time_point max() {return time_point(duration::max());} + _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR time_point min() _NOEXCEPT {return time_point(duration::min());} + _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR time_point max() _NOEXCEPT {return time_point(duration::max());} }; } // chrono @@ -1571,12 +1585,1158 @@ typedef steady_clock high_resolution_clock; typedef system_clock high_resolution_clock; #endif +#if _LIBCPP_STD_VER > 17 +// [time.clock.file], type file_clock +using file_clock = _VSTD_FS::_FilesystemClock; + +template<class _Duration> +using file_time = time_point<file_clock, _Duration>; + + +template <class _Duration> +using sys_time = time_point<system_clock, _Duration>; +using sys_seconds = sys_time<seconds>; +using sys_days = sys_time<days>; + +struct local_t {}; +template<class Duration> +using local_time = time_point<local_t, Duration>; +using local_seconds = local_time<seconds>; +using local_days = local_time<days>; + + +struct _LIBCPP_TYPE_VIS last_spec { explicit last_spec() = default; }; + +class _LIBCPP_TYPE_VIS day { +private: + unsigned char __d; +public: + day() = default; + explicit inline constexpr day(unsigned __val) noexcept : __d(static_cast<unsigned char>(__val)) {} + inline constexpr day& operator++() noexcept { ++__d; return *this; } + inline constexpr day operator++(int) noexcept { day __tmp = *this; ++(*this); return __tmp; } + inline constexpr day& operator--() noexcept { --__d; return *this; } + inline constexpr day operator--(int) noexcept { day __tmp = *this; --(*this); return __tmp; } + constexpr day& operator+=(const days& __dd) noexcept; + constexpr day& operator-=(const days& __dd) noexcept; + explicit inline constexpr operator unsigned() const noexcept { return __d; } + inline constexpr bool ok() const noexcept { return __d >= 1 && __d <= 31; } + }; + + +inline constexpr +bool operator==(const day& __lhs, const day& __rhs) noexcept +{ return static_cast<unsigned>(__lhs) == static_cast<unsigned>(__rhs); } + +inline constexpr +bool operator!=(const day& __lhs, const day& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +bool operator< (const day& __lhs, const day& __rhs) noexcept +{ return static_cast<unsigned>(__lhs) < static_cast<unsigned>(__rhs); } + +inline constexpr +bool operator> (const day& __lhs, const day& __rhs) noexcept +{ return __rhs < __lhs; } + +inline constexpr +bool operator<=(const day& __lhs, const day& __rhs) noexcept +{ return !(__rhs < __lhs);} + +inline constexpr +bool operator>=(const day& __lhs, const day& __rhs) noexcept +{ return !(__lhs < __rhs); } + +inline constexpr +day operator+ (const day& __lhs, const days& __rhs) noexcept +{ return day(static_cast<unsigned>(__lhs) + __rhs.count()); } + +inline constexpr +day operator+ (const days& __lhs, const day& __rhs) noexcept +{ return __rhs + __lhs; } + +inline constexpr +day operator- (const day& __lhs, const days& __rhs) noexcept +{ return __lhs + -__rhs; } + +inline constexpr +days operator-(const day& __lhs, const day& __rhs) noexcept +{ return days(static_cast<int>(static_cast<unsigned>(__lhs)) - + static_cast<int>(static_cast<unsigned>(__rhs))); } + +inline constexpr day& day::operator+=(const days& __dd) noexcept +{ *this = *this + __dd; return *this; } + +inline constexpr day& day::operator-=(const days& __dd) noexcept +{ *this = *this - __dd; return *this; } + + +class _LIBCPP_TYPE_VIS month { +private: + unsigned char __m; +public: + month() = default; + explicit inline constexpr month(unsigned __val) noexcept : __m(static_cast<unsigned char>(__val)) {} + inline constexpr month& operator++() noexcept { ++__m; return *this; } + inline constexpr month operator++(int) noexcept { month __tmp = *this; ++(*this); return __tmp; } + inline constexpr month& operator--() noexcept { --__m; return *this; } + inline constexpr month operator--(int) noexcept { month __tmp = *this; --(*this); return __tmp; } + constexpr month& operator+=(const months& __m1) noexcept; + constexpr month& operator-=(const months& __m1) noexcept; + explicit inline constexpr operator unsigned() const noexcept { return __m; } + inline constexpr bool ok() const noexcept { return __m >= 1 && __m <= 12; } +}; + + +inline constexpr +bool operator==(const month& __lhs, const month& __rhs) noexcept +{ return static_cast<unsigned>(__lhs) == static_cast<unsigned>(__rhs); } + +inline constexpr +bool operator!=(const month& __lhs, const month& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +bool operator< (const month& __lhs, const month& __rhs) noexcept +{ return static_cast<unsigned>(__lhs) < static_cast<unsigned>(__rhs); } + +inline constexpr +bool operator> (const month& __lhs, const month& __rhs) noexcept +{ return __rhs < __lhs; } + +inline constexpr +bool operator<=(const month& __lhs, const month& __rhs) noexcept +{ return !(__rhs < __lhs); } + +inline constexpr +bool operator>=(const month& __lhs, const month& __rhs) noexcept +{ return !(__lhs < __rhs); } + +inline constexpr +month operator+ (const month& __lhs, const months& __rhs) noexcept +{ + auto const __mu = static_cast<long long>(static_cast<unsigned>(__lhs)) + (__rhs.count() - 1); + auto const __yr = (__mu >= 0 ? __mu : __mu - 11) / 12; + return month{static_cast<unsigned>(__mu - __yr * 12 + 1)}; +} + +inline constexpr +month operator+ (const months& __lhs, const month& __rhs) noexcept +{ return __rhs + __lhs; } + +inline constexpr +month operator- (const month& __lhs, const months& __rhs) noexcept +{ return __lhs + -__rhs; } + +inline constexpr +months operator-(const month& __lhs, const month& __rhs) noexcept +{ + auto const __dm = static_cast<unsigned>(__lhs) - static_cast<unsigned>(__rhs); + return months(__dm <= 11 ? __dm : __dm + 12); +} + +inline constexpr month& month::operator+=(const months& __dm) noexcept +{ *this = *this + __dm; return *this; } + +inline constexpr month& month::operator-=(const months& __dm) noexcept +{ *this = *this - __dm; return *this; } + + +class _LIBCPP_TYPE_VIS year { +private: + short __y; +public: + year() = default; + explicit inline constexpr year(int __val) noexcept : __y(static_cast<short>(__val)) {} + + inline constexpr year& operator++() noexcept { ++__y; return *this; }; + inline constexpr year operator++(int) noexcept { year __tmp = *this; ++(*this); return __tmp; }; + inline constexpr year& operator--() noexcept { --__y; return *this; }; + inline constexpr year operator--(int) noexcept { year __tmp = *this; --(*this); return __tmp; }; + constexpr year& operator+=(const years& __dy) noexcept; + constexpr year& operator-=(const years& __dy) noexcept; + inline constexpr year operator+() const noexcept { return *this; } + inline constexpr year operator-() const noexcept { return year{-__y}; }; + + inline constexpr bool is_leap() const noexcept { return __y % 4 == 0 && (__y % 100 != 0 || __y % 400 == 0); } + explicit inline constexpr operator int() const noexcept { return __y; } + constexpr bool ok() const noexcept; + static inline constexpr year min() noexcept { return year{-32767}; } + static inline constexpr year max() noexcept { return year{ 32767}; } +}; + + +inline constexpr +bool operator==(const year& __lhs, const year& __rhs) noexcept +{ return static_cast<int>(__lhs) == static_cast<int>(__rhs); } + +inline constexpr +bool operator!=(const year& __lhs, const year& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +bool operator< (const year& __lhs, const year& __rhs) noexcept +{ return static_cast<int>(__lhs) < static_cast<int>(__rhs); } + +inline constexpr +bool operator> (const year& __lhs, const year& __rhs) noexcept +{ return __rhs < __lhs; } + +inline constexpr +bool operator<=(const year& __lhs, const year& __rhs) noexcept +{ return !(__rhs < __lhs); } + +inline constexpr +bool operator>=(const year& __lhs, const year& __rhs) noexcept +{ return !(__lhs < __rhs); } + +inline constexpr +year operator+ (const year& __lhs, const years& __rhs) noexcept +{ return year(static_cast<int>(__lhs) + __rhs.count()); } + +inline constexpr +year operator+ (const years& __lhs, const year& __rhs) noexcept +{ return __rhs + __lhs; } + +inline constexpr +year operator- (const year& __lhs, const years& __rhs) noexcept +{ return __lhs + -__rhs; } + +inline constexpr +years operator-(const year& __lhs, const year& __rhs) noexcept +{ return years{static_cast<int>(__lhs) - static_cast<int>(__rhs)}; } + + +inline constexpr year& year::operator+=(const years& __dy) noexcept +{ *this = *this + __dy; return *this; } + +inline constexpr year& year::operator-=(const years& __dy) noexcept +{ *this = *this - __dy; return *this; } + +inline constexpr bool year::ok() const noexcept +{ return static_cast<int>(min()) <= __y && __y <= static_cast<int>(max()); } + +class _LIBCPP_TYPE_VIS weekday_indexed; +class _LIBCPP_TYPE_VIS weekday_last; + +class _LIBCPP_TYPE_VIS weekday { +private: + unsigned char __wd; +public: + weekday() = default; + inline explicit constexpr weekday(unsigned __val) noexcept : __wd(static_cast<unsigned char>(__val)) {} + inline constexpr weekday(const sys_days& __sysd) noexcept + : __wd(__weekday_from_days(__sysd.time_since_epoch().count())) {} + inline explicit constexpr weekday(const local_days& __locd) noexcept + : __wd(__weekday_from_days(__locd.time_since_epoch().count())) {} + + inline constexpr weekday& operator++() noexcept { __wd = (__wd == 6 ? 0 : __wd + 1); return *this; } + inline constexpr weekday operator++(int) noexcept { weekday __tmp = *this; ++(*this); return __tmp; } + inline constexpr weekday& operator--() noexcept { __wd = (__wd == 0 ? 6 : __wd - 1); return *this; } + inline constexpr weekday operator--(int) noexcept { weekday __tmp = *this; --(*this); return __tmp; } + constexpr weekday& operator+=(const days& __dd) noexcept; + constexpr weekday& operator-=(const days& __dd) noexcept; + inline explicit constexpr operator unsigned() const noexcept { return __wd; } + inline constexpr bool ok() const noexcept { return __wd <= 6; } + constexpr weekday_indexed operator[](unsigned __index) const noexcept; + constexpr weekday_last operator[](last_spec) const noexcept; + + static constexpr unsigned char __weekday_from_days(int __days) noexcept; +}; + + +// https://howardhinnant.github.io/date_algorithms.html#weekday_from_days +inline constexpr +unsigned char weekday::__weekday_from_days(int __days) noexcept +{ + return static_cast<unsigned char>( + static_cast<unsigned>(__days >= -4 ? (__days+4) % 7 : (__days+5) % 7 + 6) + ); +} + +inline constexpr +bool operator==(const weekday& __lhs, const weekday& __rhs) noexcept +{ return static_cast<unsigned>(__lhs) == static_cast<unsigned>(__rhs); } + +inline constexpr +bool operator!=(const weekday& __lhs, const weekday& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +bool operator< (const weekday& __lhs, const weekday& __rhs) noexcept +{ return static_cast<unsigned>(__lhs) < static_cast<unsigned>(__rhs); } + +inline constexpr +bool operator> (const weekday& __lhs, const weekday& __rhs) noexcept +{ return __rhs < __lhs; } + +inline constexpr +bool operator<=(const weekday& __lhs, const weekday& __rhs) noexcept +{ return !(__rhs < __lhs);} + +inline constexpr +bool operator>=(const weekday& __lhs, const weekday& __rhs) noexcept +{ return !(__lhs < __rhs); } + +constexpr weekday operator+(const weekday& __lhs, const days& __rhs) noexcept +{ + auto const __mu = static_cast<long long>(static_cast<unsigned>(__lhs)) + __rhs.count(); + auto const __yr = (__mu >= 0 ? __mu : __mu - 6) / 7; + return weekday{static_cast<unsigned>(__mu - __yr * 7)}; +} + +constexpr weekday operator+(const days& __lhs, const weekday& __rhs) noexcept +{ return __rhs + __lhs; } + +constexpr weekday operator-(const weekday& __lhs, const days& __rhs) noexcept +{ return __lhs + -__rhs; } + +constexpr days operator-(const weekday& __lhs, const weekday& __rhs) noexcept +{ + const int __wdu = static_cast<unsigned>(__lhs) - static_cast<unsigned>(__rhs); + const int __wk = (__wdu >= 0 ? __wdu : __wdu-6) / 7; + return days{__wdu - __wk * 7}; +} + +inline constexpr weekday& weekday::operator+=(const days& __dd) noexcept +{ *this = *this + __dd; return *this; } + +inline constexpr weekday& weekday::operator-=(const days& __dd) noexcept +{ *this = *this - __dd; return *this; } + + +class _LIBCPP_TYPE_VIS weekday_indexed { +private: + _VSTD::chrono::weekday __wd; + unsigned char __idx; +public: + weekday_indexed() = default; + inline constexpr weekday_indexed(const _VSTD::chrono::weekday& __wdval, unsigned __idxval) noexcept + : __wd{__wdval}, __idx(__idxval) {} + inline constexpr _VSTD::chrono::weekday weekday() const noexcept { return __wd; } + inline constexpr unsigned index() const noexcept { return __idx; } + inline constexpr bool ok() const noexcept { return __wd.ok() && __idx >= 1 && __idx <= 5; } +}; + +inline constexpr +bool operator==(const weekday_indexed& __lhs, const weekday_indexed& __rhs) noexcept +{ return __lhs.weekday() == __rhs.weekday() && __lhs.index() == __rhs.index(); } + +inline constexpr +bool operator!=(const weekday_indexed& __lhs, const weekday_indexed& __rhs) noexcept +{ return !(__lhs == __rhs); } + + +class _LIBCPP_TYPE_VIS weekday_last { +private: + _VSTD::chrono::weekday __wd; +public: + explicit constexpr weekday_last(const _VSTD::chrono::weekday& __val) noexcept + : __wd{__val} {} + constexpr _VSTD::chrono::weekday weekday() const noexcept { return __wd; } + constexpr bool ok() const noexcept { return __wd.ok(); } +}; + +inline constexpr +bool operator==(const weekday_last& __lhs, const weekday_last& __rhs) noexcept +{ return __lhs.weekday() == __rhs.weekday(); } + +inline constexpr +bool operator!=(const weekday_last& __lhs, const weekday_last& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +weekday_indexed weekday::operator[](unsigned __index) const noexcept { return weekday_indexed{*this, __index}; } + +inline constexpr +weekday_last weekday::operator[](last_spec) const noexcept { return weekday_last{*this}; } + + +inline constexpr last_spec last{}; +inline constexpr weekday Sunday{0}; +inline constexpr weekday Monday{1}; +inline constexpr weekday Tuesday{2}; +inline constexpr weekday Wednesday{3}; +inline constexpr weekday Thursday{4}; +inline constexpr weekday Friday{5}; +inline constexpr weekday Saturday{6}; + +inline constexpr month January{1}; +inline constexpr month February{2}; +inline constexpr month March{3}; +inline constexpr month April{4}; +inline constexpr month May{5}; +inline constexpr month June{6}; +inline constexpr month July{7}; +inline constexpr month August{8}; +inline constexpr month September{9}; +inline constexpr month October{10}; +inline constexpr month November{11}; +inline constexpr month December{12}; + + +class _LIBCPP_TYPE_VIS month_day { +private: + chrono::month __m; + chrono::day __d; +public: + month_day() = default; + constexpr month_day(const chrono::month& __mval, const chrono::day& __dval) noexcept + : __m{__mval}, __d{__dval} {} + inline constexpr chrono::month month() const noexcept { return __m; } + inline constexpr chrono::day day() const noexcept { return __d; } + constexpr bool ok() const noexcept; +}; + +inline constexpr +bool month_day::ok() const noexcept +{ + if (!__m.ok()) return false; + const unsigned __dval = static_cast<unsigned>(__d); + if (__dval < 1 || __dval > 31) return false; + if (__dval <= 29) return true; +// Now we've got either 30 or 31 + const unsigned __mval = static_cast<unsigned>(__m); + if (__mval == 2) return false; + if (__mval == 4 || __mval == 6 || __mval == 9 || __mval == 11) + return __dval == 30; + return true; +} + +inline constexpr +bool operator==(const month_day& __lhs, const month_day& __rhs) noexcept +{ return __lhs.month() == __rhs.month() && __lhs.day() == __rhs.day(); } + +inline constexpr +bool operator!=(const month_day& __lhs, const month_day& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +month_day operator/(const month& __lhs, const day& __rhs) noexcept +{ return month_day{__lhs, __rhs}; } + +constexpr +month_day operator/(const day& __lhs, const month& __rhs) noexcept +{ return __rhs / __lhs; } + +inline constexpr +month_day operator/(const month& __lhs, int __rhs) noexcept +{ return __lhs / day(__rhs); } + +constexpr +month_day operator/(int __lhs, const day& __rhs) noexcept +{ return month(__lhs) / __rhs; } + +constexpr +month_day operator/(const day& __lhs, int __rhs) noexcept +{ return month(__rhs) / __lhs; } + + +inline constexpr +bool operator< (const month_day& __lhs, const month_day& __rhs) noexcept +{ return __lhs.month() != __rhs.month() ? __lhs.month() < __rhs.month() : __lhs.day() < __rhs.day(); } + +inline constexpr +bool operator> (const month_day& __lhs, const month_day& __rhs) noexcept +{ return __rhs < __lhs; } + +inline constexpr +bool operator<=(const month_day& __lhs, const month_day& __rhs) noexcept +{ return !(__rhs < __lhs);} + +inline constexpr +bool operator>=(const month_day& __lhs, const month_day& __rhs) noexcept +{ return !(__lhs < __rhs); } + + + +class _LIBCPP_TYPE_VIS month_day_last { +private: + chrono::month __m; +public: + explicit constexpr month_day_last(const chrono::month& __val) noexcept + : __m{__val} {} + inline constexpr chrono::month month() const noexcept { return __m; } + inline constexpr bool ok() const noexcept { return __m.ok(); } +}; + +inline constexpr +bool operator==(const month_day_last& __lhs, const month_day_last& __rhs) noexcept +{ return __lhs.month() == __rhs.month(); } + +inline constexpr +bool operator!=(const month_day_last& __lhs, const month_day_last& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +bool operator< (const month_day_last& __lhs, const month_day_last& __rhs) noexcept +{ return __lhs.month() < __rhs.month(); } + +inline constexpr +bool operator> (const month_day_last& __lhs, const month_day_last& __rhs) noexcept +{ return __rhs < __lhs; } + +inline constexpr +bool operator<=(const month_day_last& __lhs, const month_day_last& __rhs) noexcept +{ return !(__rhs < __lhs);} + +inline constexpr +bool operator>=(const month_day_last& __lhs, const month_day_last& __rhs) noexcept +{ return !(__lhs < __rhs); } + +inline constexpr +month_day_last operator/(const month& __lhs, last_spec) noexcept +{ return month_day_last{__lhs}; } + +inline constexpr +month_day_last operator/(last_spec, const month& __rhs) noexcept +{ return month_day_last{__rhs}; } + +inline constexpr +month_day_last operator/(int __lhs, last_spec) noexcept +{ return month_day_last{month(__lhs)}; } + +inline constexpr +month_day_last operator/(last_spec, int __rhs) noexcept +{ return month_day_last{month(__rhs)}; } + + +class _LIBCPP_TYPE_VIS month_weekday { +private: + chrono::month __m; + chrono::weekday_indexed __wdi; +public: + month_weekday() = default; + constexpr month_weekday(const chrono::month& __mval, const chrono::weekday_indexed& __wdival) noexcept + : __m{__mval}, __wdi{__wdival} {} + inline constexpr chrono::month month() const noexcept { return __m; } + inline constexpr chrono::weekday_indexed weekday_indexed() const noexcept { return __wdi; } + inline constexpr bool ok() const noexcept { return __m.ok() && __wdi.ok(); } +}; + +inline constexpr +bool operator==(const month_weekday& __lhs, const month_weekday& __rhs) noexcept +{ return __lhs.month() == __rhs.month() && __lhs.weekday_indexed() == __rhs.weekday_indexed(); } + +inline constexpr +bool operator!=(const month_weekday& __lhs, const month_weekday& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +month_weekday operator/(const month& __lhs, const weekday_indexed& __rhs) noexcept +{ return month_weekday{__lhs, __rhs}; } + +inline constexpr +month_weekday operator/(int __lhs, const weekday_indexed& __rhs) noexcept +{ return month_weekday{month(__lhs), __rhs}; } + +inline constexpr +month_weekday operator/(const weekday_indexed& __lhs, const month& __rhs) noexcept +{ return month_weekday{__rhs, __lhs}; } + +inline constexpr +month_weekday operator/(const weekday_indexed& __lhs, int __rhs) noexcept +{ return month_weekday{month(__rhs), __lhs}; } + + +class _LIBCPP_TYPE_VIS month_weekday_last { + chrono::month __m; + chrono::weekday_last __wdl; + public: + constexpr month_weekday_last(const chrono::month& __mval, const chrono::weekday_last& __wdlval) noexcept + : __m{__mval}, __wdl{__wdlval} {} + inline constexpr chrono::month month() const noexcept { return __m; } + inline constexpr chrono::weekday_last weekday_last() const noexcept { return __wdl; } + inline constexpr bool ok() const noexcept { return __m.ok() && __wdl.ok(); } +}; + +inline constexpr +bool operator==(const month_weekday_last& __lhs, const month_weekday_last& __rhs) noexcept +{ return __lhs.month() == __rhs.month() && __lhs.weekday_last() == __rhs.weekday_last(); } + +inline constexpr +bool operator!=(const month_weekday_last& __lhs, const month_weekday_last& __rhs) noexcept +{ return !(__lhs == __rhs); } + + +inline constexpr +month_weekday_last operator/(const month& __lhs, const weekday_last& __rhs) noexcept +{ return month_weekday_last{__lhs, __rhs}; } + +inline constexpr +month_weekday_last operator/(int __lhs, const weekday_last& __rhs) noexcept +{ return month_weekday_last{month(__lhs), __rhs}; } + +inline constexpr +month_weekday_last operator/(const weekday_last& __lhs, const month& __rhs) noexcept +{ return month_weekday_last{__rhs, __lhs}; } + +inline constexpr +month_weekday_last operator/(const weekday_last& __lhs, int __rhs) noexcept +{ return month_weekday_last{month(__rhs), __lhs}; } + + +class _LIBCPP_TYPE_VIS year_month { + chrono::year __y; + chrono::month __m; +public: + year_month() = default; + constexpr year_month(const chrono::year& __yval, const chrono::month& __mval) noexcept + : __y{__yval}, __m{__mval} {} + inline constexpr chrono::year year() const noexcept { return __y; } + inline constexpr chrono::month month() const noexcept { return __m; } + inline constexpr year_month& operator+=(const months& __dm) noexcept { this->__m += __dm; return *this; } + inline constexpr year_month& operator-=(const months& __dm) noexcept { this->__m -= __dm; return *this; } + inline constexpr year_month& operator+=(const years& __dy) noexcept { this->__y += __dy; return *this; } + inline constexpr year_month& operator-=(const years& __dy) noexcept { this->__y -= __dy; return *this; } + inline constexpr bool ok() const noexcept { return __y.ok() && __m.ok(); } +}; + +inline constexpr +year_month operator/(const year& __y, const month& __m) noexcept { return year_month{__y, __m}; } + +inline constexpr +year_month operator/(const year& __y, int __m) noexcept { return year_month{__y, month(__m)}; } + +inline constexpr +bool operator==(const year_month& __lhs, const year_month& __rhs) noexcept +{ return __lhs.year() == __rhs.year() && __lhs.month() == __rhs.month(); } + +inline constexpr +bool operator!=(const year_month& __lhs, const year_month& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +bool operator< (const year_month& __lhs, const year_month& __rhs) noexcept +{ return __lhs.year() != __rhs.year() ? __lhs.year() < __rhs.year() : __lhs.month() < __rhs.month(); } + +inline constexpr +bool operator> (const year_month& __lhs, const year_month& __rhs) noexcept +{ return __rhs < __lhs; } + +inline constexpr +bool operator<=(const year_month& __lhs, const year_month& __rhs) noexcept +{ return !(__rhs < __lhs);} + +inline constexpr +bool operator>=(const year_month& __lhs, const year_month& __rhs) noexcept +{ return !(__lhs < __rhs); } + +constexpr year_month operator+(const year_month& __lhs, const months& __rhs) noexcept +{ + int __dmi = static_cast<int>(static_cast<unsigned>(__lhs.month())) - 1 + __rhs.count(); + const int __dy = (__dmi >= 0 ? __dmi : __dmi-11) / 12; + __dmi = __dmi - __dy * 12 + 1; + return (__lhs.year() + years(__dy)) / month(static_cast<unsigned>(__dmi)); +} + +constexpr year_month operator+(const months& __lhs, const year_month& __rhs) noexcept +{ return __rhs + __lhs; } + +constexpr year_month operator+(const year_month& __lhs, const years& __rhs) noexcept +{ return (__lhs.year() + __rhs) / __lhs.month(); } + +constexpr year_month operator+(const years& __lhs, const year_month& __rhs) noexcept +{ return __rhs + __lhs; } + +constexpr months operator-(const year_month& __lhs, const year_month& __rhs) noexcept +{ return (__lhs.year() - __rhs.year()) + months(static_cast<unsigned>(__lhs.month()) - static_cast<unsigned>(__rhs.month())); } + +constexpr year_month operator-(const year_month& __lhs, const months& __rhs) noexcept +{ return __lhs + -__rhs; } + +constexpr year_month operator-(const year_month& __lhs, const years& __rhs) noexcept +{ return __lhs + -__rhs; } + +class year_month_day_last; + +class _LIBCPP_TYPE_VIS year_month_day { +private: + chrono::year __y; + chrono::month __m; + chrono::day __d; +public: + year_month_day() = default; + inline constexpr year_month_day( + const chrono::year& __yval, const chrono::month& __mval, const chrono::day& __dval) noexcept + : __y{__yval}, __m{__mval}, __d{__dval} {} + constexpr year_month_day(const year_month_day_last& __ymdl) noexcept; + inline constexpr year_month_day(const sys_days& __sysd) noexcept + : year_month_day(__from_days(__sysd.time_since_epoch())) {} + inline explicit constexpr year_month_day(const local_days& __locd) noexcept + : year_month_day(__from_days(__locd.time_since_epoch())) {} + + constexpr year_month_day& operator+=(const months& __dm) noexcept; + constexpr year_month_day& operator-=(const months& __dm) noexcept; + constexpr year_month_day& operator+=(const years& __dy) noexcept; + constexpr year_month_day& operator-=(const years& __dy) noexcept; + + inline constexpr chrono::year year() const noexcept { return __y; } + inline constexpr chrono::month month() const noexcept { return __m; } + inline constexpr chrono::day day() const noexcept { return __d; } + inline constexpr operator sys_days() const noexcept { return sys_days{__to_days()}; } + inline explicit constexpr operator local_days() const noexcept { return local_days{__to_days()}; } + + constexpr bool ok() const noexcept; + + static constexpr year_month_day __from_days(days __d) noexcept; + constexpr days __to_days() const noexcept; +}; + + +// https://howardhinnant.github.io/date_algorithms.html#civil_from_days +inline constexpr +year_month_day +year_month_day::__from_days(days __d) noexcept +{ + static_assert(std::numeric_limits<unsigned>::digits >= 18, ""); + static_assert(std::numeric_limits<int>::digits >= 20 , ""); + const int __z = __d.count() + 719468; + const int __era = (__z >= 0 ? __z : __z - 146096) / 146097; + const unsigned __doe = static_cast<unsigned>(__z - __era * 146097); // [0, 146096] + const unsigned __yoe = (__doe - __doe/1460 + __doe/36524 - __doe/146096) / 365; // [0, 399] + const int __yr = static_cast<int>(__yoe) + __era * 400; + const unsigned __doy = __doe - (365 * __yoe + __yoe/4 - __yoe/100); // [0, 365] + const unsigned __mp = (5 * __doy + 2)/153; // [0, 11] + const unsigned __dy = __doy - (153 * __mp + 2)/5 + 1; // [1, 31] + const unsigned __mth = __mp + (__mp < 10 ? 3 : -9); // [1, 12] + return year_month_day{chrono::year{__yr + (__mth <= 2)}, chrono::month{__mth}, chrono::day{__dy}}; +} + +// https://howardhinnant.github.io/date_algorithms.html#days_from_civil +inline constexpr days year_month_day::__to_days() const noexcept +{ + static_assert(std::numeric_limits<unsigned>::digits >= 18, ""); + static_assert(std::numeric_limits<int>::digits >= 20 , ""); + + const int __yr = static_cast<int>(__y) - (__m <= February); + const unsigned __mth = static_cast<unsigned>(__m); + const unsigned __dy = static_cast<unsigned>(__d); + + const int __era = (__yr >= 0 ? __yr : __yr - 399) / 400; + const unsigned __yoe = static_cast<unsigned>(__yr - __era * 400); // [0, 399] + const unsigned __doy = (153 * (__mth + (__mth > 2 ? -3 : 9)) + 2) / 5 + __dy-1; // [0, 365] + const unsigned __doe = __yoe * 365 + __yoe/4 - __yoe/100 + __doy; // [0, 146096] + return days{__era * 146097 + static_cast<int>(__doe) - 719468}; +} + +inline constexpr +bool operator==(const year_month_day& __lhs, const year_month_day& __rhs) noexcept +{ return __lhs.year() == __rhs.year() && __lhs.month() == __rhs.month() && __lhs.day() == __rhs.day(); } + +inline constexpr +bool operator!=(const year_month_day& __lhs, const year_month_day& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +bool operator< (const year_month_day& __lhs, const year_month_day& __rhs) noexcept +{ + if (__lhs.year() < __rhs.year()) return true; + if (__lhs.year() > __rhs.year()) return false; + if (__lhs.month() < __rhs.month()) return true; + if (__lhs.month() > __rhs.month()) return false; + return __lhs.day() < __rhs.day(); +} + +inline constexpr +bool operator> (const year_month_day& __lhs, const year_month_day& __rhs) noexcept +{ return __rhs < __lhs; } + +inline constexpr +bool operator<=(const year_month_day& __lhs, const year_month_day& __rhs) noexcept +{ return !(__rhs < __lhs);} + +inline constexpr +bool operator>=(const year_month_day& __lhs, const year_month_day& __rhs) noexcept +{ return !(__lhs < __rhs); } + +inline constexpr +year_month_day operator/(const year_month& __lhs, const day& __rhs) noexcept +{ return year_month_day{__lhs.year(), __lhs.month(), __rhs}; } + +inline constexpr +year_month_day operator/(const year_month& __lhs, int __rhs) noexcept +{ return __lhs / day(__rhs); } + +inline constexpr +year_month_day operator/(const year& __lhs, const month_day& __rhs) noexcept +{ return __lhs / __rhs.month() / __rhs.day(); } + +inline constexpr +year_month_day operator/(int __lhs, const month_day& __rhs) noexcept +{ return year(__lhs) / __rhs; } + +inline constexpr +year_month_day operator/(const month_day& __lhs, const year& __rhs) noexcept +{ return __rhs / __lhs; } + +inline constexpr +year_month_day operator/(const month_day& __lhs, int __rhs) noexcept +{ return year(__rhs) / __lhs; } + + +inline constexpr +year_month_day operator+(const year_month_day& __lhs, const months& __rhs) noexcept +{ return (__lhs.year()/__lhs.month() + __rhs)/__lhs.day(); } + +inline constexpr +year_month_day operator+(const months& __lhs, const year_month_day& __rhs) noexcept +{ return __rhs + __lhs; } + +inline constexpr +year_month_day operator-(const year_month_day& __lhs, const months& __rhs) noexcept +{ return __lhs + -__rhs; } + +inline constexpr +year_month_day operator+(const year_month_day& __lhs, const years& __rhs) noexcept +{ return (__lhs.year() + __rhs) / __lhs.month() / __lhs.day(); } + +inline constexpr +year_month_day operator+(const years& __lhs, const year_month_day& __rhs) noexcept +{ return __rhs + __lhs; } + +inline constexpr +year_month_day operator-(const year_month_day& __lhs, const years& __rhs) noexcept +{ return __lhs + -__rhs; } + +inline constexpr year_month_day& year_month_day::operator+=(const months& __dm) noexcept { *this = *this + __dm; return *this; } +inline constexpr year_month_day& year_month_day::operator-=(const months& __dm) noexcept { *this = *this - __dm; return *this; } +inline constexpr year_month_day& year_month_day::operator+=(const years& __dy) noexcept { *this = *this + __dy; return *this; } +inline constexpr year_month_day& year_month_day::operator-=(const years& __dy) noexcept { *this = *this - __dy; return *this; } + +class _LIBCPP_TYPE_VIS year_month_day_last { +private: + chrono::year __y; + chrono::month_day_last __mdl; +public: + constexpr year_month_day_last(const year& __yval, const month_day_last& __mdlval) noexcept + : __y{__yval}, __mdl{__mdlval} {} + + constexpr year_month_day_last& operator+=(const months& __m) noexcept; + constexpr year_month_day_last& operator-=(const months& __m) noexcept; + constexpr year_month_day_last& operator+=(const years& __y) noexcept; + constexpr year_month_day_last& operator-=(const years& __y) noexcept; + + inline constexpr chrono::year year() const noexcept { return __y; } + inline constexpr chrono::month month() const noexcept { return __mdl.month(); } + inline constexpr chrono::month_day_last month_day_last() const noexcept { return __mdl; } + constexpr chrono::day day() const noexcept; + inline constexpr operator sys_days() const noexcept { return sys_days{year()/month()/day()}; } + inline explicit constexpr operator local_days() const noexcept { return local_days{year()/month()/day()}; } + inline constexpr bool ok() const noexcept { return __y.ok() && __mdl.ok(); } +}; + +inline constexpr +chrono::day year_month_day_last::day() const noexcept +{ + constexpr chrono::day __d[] = + { + chrono::day(31), chrono::day(28), chrono::day(31), + chrono::day(30), chrono::day(31), chrono::day(30), + chrono::day(31), chrono::day(31), chrono::day(30), + chrono::day(31), chrono::day(30), chrono::day(31) + }; + return month() != February || !__y.is_leap() ? + __d[static_cast<unsigned>(month()) - 1] : chrono::day{29}; +} + +inline constexpr +bool operator==(const year_month_day_last& __lhs, const year_month_day_last& __rhs) noexcept +{ return __lhs.year() == __rhs.year() && __lhs.month_day_last() == __rhs.month_day_last(); } + +inline constexpr +bool operator!=(const year_month_day_last& __lhs, const year_month_day_last& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +bool operator< (const year_month_day_last& __lhs, const year_month_day_last& __rhs) noexcept +{ + if (__lhs.year() < __rhs.year()) return true; + if (__lhs.year() > __rhs.year()) return false; + return __lhs.month_day_last() < __rhs.month_day_last(); +} + +inline constexpr +bool operator> (const year_month_day_last& __lhs, const year_month_day_last& __rhs) noexcept +{ return __rhs < __lhs; } + +inline constexpr +bool operator<=(const year_month_day_last& __lhs, const year_month_day_last& __rhs) noexcept +{ return !(__rhs < __lhs);} + +inline constexpr +bool operator>=(const year_month_day_last& __lhs, const year_month_day_last& __rhs) noexcept +{ return !(__lhs < __rhs); } + +inline constexpr year_month_day_last operator/(const year_month& __lhs, last_spec) noexcept +{ return year_month_day_last{__lhs.year(), month_day_last{__lhs.month()}}; } + +inline constexpr year_month_day_last operator/(const year& __lhs, const month_day_last& __rhs) noexcept +{ return year_month_day_last{__lhs, __rhs}; } + +inline constexpr year_month_day_last operator/(int __lhs, const month_day_last& __rhs) noexcept +{ return year_month_day_last{year{__lhs}, __rhs}; } + +inline constexpr year_month_day_last operator/(const month_day_last& __lhs, const year& __rhs) noexcept +{ return __rhs / __lhs; } + +inline constexpr year_month_day_last operator/(const month_day_last& __lhs, int __rhs) noexcept +{ return year{__rhs} / __lhs; } + + +inline constexpr +year_month_day_last operator+(const year_month_day_last& __lhs, const months& __rhs) noexcept +{ return (__lhs.year() / __lhs.month() + __rhs) / last; } + +inline constexpr +year_month_day_last operator+(const months& __lhs, const year_month_day_last& __rhs) noexcept +{ return __rhs + __lhs; } + +inline constexpr +year_month_day_last operator-(const year_month_day_last& __lhs, const months& __rhs) noexcept +{ return __lhs + (-__rhs); } + +inline constexpr +year_month_day_last operator+(const year_month_day_last& __lhs, const years& __rhs) noexcept +{ return year_month_day_last{__lhs.year() + __rhs, __lhs.month_day_last()}; } + +inline constexpr +year_month_day_last operator+(const years& __lhs, const year_month_day_last& __rhs) noexcept +{ return __rhs + __lhs; } + +inline constexpr +year_month_day_last operator-(const year_month_day_last& __lhs, const years& __rhs) noexcept +{ return __lhs + (-__rhs); } + +inline constexpr year_month_day_last& year_month_day_last::operator+=(const months& __dm) noexcept { *this = *this + __dm; return *this; } +inline constexpr year_month_day_last& year_month_day_last::operator-=(const months& __dm) noexcept { *this = *this - __dm; return *this; } +inline constexpr year_month_day_last& year_month_day_last::operator+=(const years& __dy) noexcept { *this = *this + __dy; return *this; } +inline constexpr year_month_day_last& year_month_day_last::operator-=(const years& __dy) noexcept { *this = *this - __dy; return *this; } + +inline constexpr year_month_day::year_month_day(const year_month_day_last& __ymdl) noexcept + : __y{__ymdl.year()}, __m{__ymdl.month()}, __d{__ymdl.day()} {} + +inline constexpr bool year_month_day::ok() const noexcept +{ + if (!__y.ok() || !__m.ok()) return false; + return chrono::day{1} <= __d && __d <= (__y / __m / last).day(); +} + +class _LIBCPP_TYPE_VIS year_month_weekday { + chrono::year __y; + chrono::month __m; + chrono::weekday_indexed __wdi; +public: + year_month_weekday() = default; + constexpr year_month_weekday(const chrono::year& __yval, const chrono::month& __mval, + const chrono::weekday_indexed& __wdival) noexcept + : __y{__yval}, __m{__mval}, __wdi{__wdival} {} + constexpr year_month_weekday(const sys_days& __sysd) noexcept + : year_month_weekday(__from_days(__sysd.time_since_epoch())) {} + inline explicit constexpr year_month_weekday(const local_days& __locd) noexcept + : year_month_weekday(__from_days(__locd.time_since_epoch())) {} + constexpr year_month_weekday& operator+=(const months& m) noexcept; + constexpr year_month_weekday& operator-=(const months& m) noexcept; + constexpr year_month_weekday& operator+=(const years& y) noexcept; + constexpr year_month_weekday& operator-=(const years& y) noexcept; + + inline constexpr chrono::year year() const noexcept { return __y; } + inline constexpr chrono::month month() const noexcept { return __m; } + inline constexpr chrono::weekday weekday() const noexcept { return __wdi.weekday(); } + inline constexpr unsigned index() const noexcept { return __wdi.index(); } + inline constexpr chrono::weekday_indexed weekday_indexed() const noexcept { return __wdi; } + + inline constexpr operator sys_days() const noexcept { return sys_days{__to_days()}; } + inline explicit constexpr operator local_days() const noexcept { return local_days{__to_days()}; } + inline constexpr bool ok() const noexcept + { + if (!__y.ok() || !__m.ok() || !__wdi.ok()) return false; + // TODO: make sure it's a valid date + return true; + } + + static constexpr year_month_weekday __from_days(days __d) noexcept; + constexpr days __to_days() const noexcept; +}; + +inline constexpr +year_month_weekday year_month_weekday::__from_days(days __d) noexcept +{ + const sys_days __sysd{__d}; + const chrono::weekday __wd = chrono::weekday(__sysd); + const year_month_day __ymd = year_month_day(__sysd); + return year_month_weekday{__ymd.year(), __ymd.month(), + __wd[(static_cast<unsigned>(__ymd.day())-1)/7+1]}; +} + +inline constexpr +days year_month_weekday::__to_days() const noexcept +{ + const sys_days __sysd = sys_days(__y/__m/1); + return (__sysd + (__wdi.weekday() - chrono::weekday(__sysd) + days{(__wdi.index()-1)*7})) + .time_since_epoch(); +} + +inline constexpr +bool operator==(const year_month_weekday& __lhs, const year_month_weekday& __rhs) noexcept +{ return __lhs.year() == __rhs.year() && __lhs.month() == __rhs.month() && __lhs.weekday_indexed() == __rhs.weekday_indexed(); } + +inline constexpr +bool operator!=(const year_month_weekday& __lhs, const year_month_weekday& __rhs) noexcept +{ return !(__lhs == __rhs); } + +inline constexpr +year_month_weekday operator/(const year_month& __lhs, const weekday_indexed& __rhs) noexcept +{ return year_month_weekday{__lhs.year(), __lhs.month(), __rhs}; } + +inline constexpr +year_month_weekday operator/(const year& __lhs, const month_weekday& __rhs) noexcept +{ return year_month_weekday{__lhs, __rhs.month(), __rhs.weekday_indexed()}; } + +inline constexpr +year_month_weekday operator/(int __lhs, const month_weekday& __rhs) noexcept +{ return year(__lhs) / __rhs; } + +inline constexpr +year_month_weekday operator/(const month_weekday& __lhs, const year& __rhs) noexcept +{ return __rhs / __lhs; } + +inline constexpr +year_month_weekday operator/(const month_weekday& __lhs, int __rhs) noexcept +{ return year(__rhs) / __lhs; } + + +inline constexpr +year_month_weekday operator+(const year_month_weekday& __lhs, const months& __rhs) noexcept +{ return (__lhs.year() / __lhs.month() + __rhs) / __lhs.weekday_indexed(); } + +inline constexpr +year_month_weekday operator+(const months& __lhs, const year_month_weekday& __rhs) noexcept +{ return __rhs + __lhs; } + +inline constexpr +year_month_weekday operator-(const year_month_weekday& __lhs, const months& __rhs) noexcept +{ return __lhs + (-__rhs); } + +inline constexpr +year_month_weekday operator+(const year_month_weekday& __lhs, const years& __rhs) noexcept +{ return year_month_weekday{__lhs.year() + __rhs, __lhs.month(), __lhs.weekday_indexed()}; } + +inline constexpr +year_month_weekday operator+(const years& __lhs, const year_month_weekday& __rhs) noexcept +{ return __rhs + __lhs; } + +inline constexpr +year_month_weekday operator-(const year_month_weekday& __lhs, const years& __rhs) noexcept +{ return __lhs + (-__rhs); } + + +inline constexpr year_month_weekday& year_month_weekday::operator+=(const months& __dm) noexcept { *this = *this + __dm; return *this; } +inline constexpr year_month_weekday& year_month_weekday::operator-=(const months& __dm) noexcept { *this = *this - __dm; return *this; } +inline constexpr year_month_weekday& year_month_weekday::operator+=(const years& __dy) noexcept { *this = *this + __dy; return *this; } +inline constexpr year_month_weekday& year_month_weekday::operator-=(const years& __dy) noexcept { *this = *this - __dy; return *this; } + +class _LIBCPP_TYPE_VIS year_month_weekday_last { +private: + chrono::year __y; + chrono::month __m; + chrono::weekday_last __wdl; +public: + constexpr year_month_weekday_last(const chrono::year& __yval, const chrono::month& __mval, + const chrono::weekday_last& __wdlval) noexcept + : __y{__yval}, __m{__mval}, __wdl{__wdlval} {} + constexpr year_month_weekday_last& operator+=(const months& __dm) noexcept; + constexpr year_month_weekday_last& operator-=(const months& __dm) noexcept; + constexpr year_month_weekday_last& operator+=(const years& __dy) noexcept; + constexpr year_month_weekday_last& operator-=(const years& __dy) noexcept; + + inline constexpr chrono::year year() const noexcept { return __y; } + inline constexpr chrono::month month() const noexcept { return __m; } + inline constexpr chrono::weekday weekday() const noexcept { return __wdl.weekday(); } + inline constexpr chrono::weekday_last weekday_last() const noexcept { return __wdl; } + inline constexpr operator sys_days() const noexcept { return sys_days{__to_days()}; } + inline explicit constexpr operator local_days() const noexcept { return local_days{__to_days()}; } + inline constexpr bool ok() const noexcept { return __y.ok() && __m.ok() && __wdl.ok(); } + + constexpr days __to_days() const noexcept; + +}; + +inline constexpr +days year_month_weekday_last::__to_days() const noexcept +{ + const sys_days __last = sys_days{__y/__m/last}; + return (__last - (chrono::weekday{__last} - __wdl.weekday())).time_since_epoch(); |