From c6954897f7ece5011f0126db9117361dc1a6ff36 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 12 Mar 2020 09:41:33 -0700 Subject: Export of internal Abseil changes -- 66a0a46462692378f77518f9db766a218bfac40b by Derek Mauro : Internal change PiperOrigin-RevId: 300565981 -- 2a1ad67662b2e22beec7d3be019e6bba23c41c7f by Derek Mauro : Fix CompressedTuple move constructor on MSVC Imports GitHub #637 PiperOrigin-RevId: 300545840 -- a3ee3ad036bbb6b0031121fd58299e5c59a243e1 by Derek Mauro : Disable LLVM's XRay instrumentation on Android Fixes #626 PiperOrigin-RevId: 300540906 -- 87999244b1f825e585ec12a431086cb60daeb24f by Gennadiy Rozental : Increase max cord depth by 2. After reviewing of the paper we can prove that the algorithm in fact can lead to slightly larger max depth. PiperOrigin-RevId: 300422376 -- 98de175ee8ad33290ef883c167c2de4414a11007 by Abseil Team : Use *opt/opt-> instead of opt.value() in an example, after checking the optional has a value. PiperOrigin-RevId: 300253502 -- 1107aa0acf0fe743ef50173e02e48f0d4eb572ef by Derek Mauro : Stop overriding the default system C++ dialect in CMake CMake on MacOS has some very strange defaults, like Wno-c++11-extensions, and doesn't seem to respect CMAKE_CXX_STANDARD, so use CMAKE_CXX_FLAGS instead. PiperOrigin-RevId: 300180753 GitOrigin-RevId: 66a0a46462692378f77518f9db766a218bfac40b Change-Id: Icd7b84c49306441b012cb87f244cc92a11697db8 --- absl/base/attributes.h | 4 +++- absl/copts/AbseilConfigureCopts.cmake | 9 --------- absl/strings/cord.cc | 21 ++++++++++--------- absl/strings/cord.h | 38 +++++++++-------------------------- absl/strings/cord_test.cc | 10 ++++++--- absl/types/optional.h | 2 +- ci/macos_xcode_cmake.sh | 2 +- 7 files changed, 33 insertions(+), 53 deletions(-) diff --git a/absl/base/attributes.h b/absl/base/attributes.h index ff138629d1f1..b4bb6cf873ca 100644 --- a/absl/base/attributes.h +++ b/absl/base/attributes.h @@ -507,8 +507,10 @@ // packages/targets, as this may lead to conflicting definitions of functions at // link-time. // +// XRay isn't currently supported on Android: +// https://github.com/android/ndk/issues/368 #if ABSL_HAVE_CPP_ATTRIBUTE(clang::xray_always_instrument) && \ - !defined(ABSL_NO_XRAY_ATTRIBUTES) + !defined(ABSL_NO_XRAY_ATTRIBUTES) && !defined(__ANDROID__) #define ABSL_XRAY_ALWAYS_INSTRUMENT [[clang::xray_always_instrument]] #define ABSL_XRAY_NEVER_INSTRUMENT [[clang::xray_never_instrument]] #if ABSL_HAVE_CPP_ATTRIBUTE(clang::xray_log_args) diff --git a/absl/copts/AbseilConfigureCopts.cmake b/absl/copts/AbseilConfigureCopts.cmake index 77d4ace8be42..390a07a02549 100644 --- a/absl/copts/AbseilConfigureCopts.cmake +++ b/absl/copts/AbseilConfigureCopts.cmake @@ -63,12 +63,3 @@ else() set(ABSL_DEFAULT_COPTS "") set(ABSL_TEST_COPTS "") endif() - -if("${CMAKE_CXX_STANDARD}" EQUAL 98) - message(FATAL_ERROR "Abseil requires at least C++11") -elseif(NOT "${CMAKE_CXX_STANDARD}") - message(STATUS "No CMAKE_CXX_STANDARD set, assuming 11") - set(ABSL_CXX_STANDARD 11) -else() - set(ABSL_CXX_STANDARD "${CMAKE_CXX_STANDARD}") -endif() diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc index 9b32b3cc46b6..415b239b0e9c 100644 --- a/absl/strings/cord.cc +++ b/absl/strings/cord.cc @@ -187,19 +187,20 @@ static constexpr size_t TagToLength(uint8_t tag) { // Enforce that kMaxFlatSize maps to a well-known exact tag value. static_assert(TagToAllocatedSize(224) == kMaxFlatSize, "Bad tag logic"); -constexpr uint64_t Fibonacci(uint8_t n, uint64_t a = 0, uint64_t b = 1) { - return n == 0 ? a : n == 1 ? b : Fibonacci(n - 1, b, a + b); +constexpr size_t Fibonacci(uint8_t n, const size_t a = 0, const size_t b = 1) { + return n == 0 + ? a + : n == 1 ? b + : Fibonacci(n - 1, b, + (a > (size_t(-1) - b)) ? size_t(-1) : a + b); } -static_assert(Fibonacci(63) == 6557470319842, - "Fibonacci values computed incorrectly"); - // Minimum length required for a given depth tree -- a tree is considered // balanced if // length(t) >= kMinLength[depth(t)] // The node depth is allowed to become larger to reduce rebalancing // for larger strings (see ShouldRebalance). -constexpr uint64_t kMinLength[] = { +constexpr size_t kMinLength[] = { Fibonacci(2), Fibonacci(3), Fibonacci(4), Fibonacci(5), Fibonacci(6), Fibonacci(7), Fibonacci(8), Fibonacci(9), Fibonacci(10), Fibonacci(11), Fibonacci(12), Fibonacci(13), Fibonacci(14), Fibonacci(15), Fibonacci(16), @@ -218,9 +219,9 @@ constexpr uint64_t kMinLength[] = { Fibonacci(77), Fibonacci(78), Fibonacci(79), Fibonacci(80), Fibonacci(81), Fibonacci(82), Fibonacci(83), Fibonacci(84), Fibonacci(85), Fibonacci(86), Fibonacci(87), Fibonacci(88), Fibonacci(89), Fibonacci(90), Fibonacci(91), - Fibonacci(92), Fibonacci(93)}; + Fibonacci(92), Fibonacci(93), Fibonacci(94), Fibonacci(95)}; -static_assert(sizeof(kMinLength) / sizeof(uint64_t) == +static_assert(sizeof(kMinLength) / sizeof(size_t) >= (cord_internal::MaxCordDepth() + 1), "Not enough elements in kMinLength array to cover all the " "supported Cord depth(s)"); @@ -1169,9 +1170,9 @@ class CordForest { void AddNode(CordRep* node) { CordRep* sum = nullptr; - // Collect together everything with which we will merge node + // Collect together everything with which we will merge with node int i = 0; - for (; node->length > kMinLength[i + 1]; ++i) { + for (; node->length >= kMinLength[i + 1]; ++i) { auto& tree_at_i = trees_[i]; if (tree_at_i == nullptr) continue; diff --git a/absl/strings/cord.h b/absl/strings/cord.h index 3941f19c3451..eb236e50e22e 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h @@ -72,39 +72,21 @@ namespace cord_internal { // It's expensive to keep a tree perfectly balanced, so instead we keep trees // approximately balanced. A tree node N of depth D(N) that contains a string // of L(N) characters is considered balanced if L >= Fibonacci(D + 2). -// The "+ 2" is used to ensure that every leaf node contains at least one -// character. Here we presume that +// The "+ 2" is used to ensure that every balanced leaf node contains at least +// one character. Here we presume that // Fibonacci(0) = 0 // Fibonacci(1) = 1 // Fibonacci(2) = 1 // Fibonacci(3) = 2 // ... -// -// Fibonacci numbers are convenient because it means when two balanced trees of -// the same depth are made the children of a new node, the resulting tree is -// guaranteed to also be balanced: -// -// -// L(left) >= Fibonacci(D(left) + 2) -// L(right) >= Fibonacci(D(right) + 2) -// -// L(left) + L(right) >= Fibonacci(D(left) + 2) + Fibonacci(D(right) + 2) -// L(left) + L(right) == L(new_tree) -// -// L(new_tree) >= 2 * Fibonacci(D(child) + 2) -// D(child) == D(new_tree) - 1 -// -// L(new_tree) >= 2 * Fibonacci(D(new_tree) + 1) -// 2 * Fibonacci(N) >= Fibonacci(N + 1) -// -// L(new_tree) >= Fibonacci(D(new_tree) + 2) -// -// -// The 93rd Fibonacci number is the largest Fibonacci number that can be -// represented in 64 bits, so the size of a balanced Cord of depth 92 is too big -// for an unsigned 64 bit integer to hold. Therefore we can safely assume that -// the maximum depth of a Cord is 91. -constexpr size_t MaxCordDepth() { return 91; } +// The algorithm is based on paper by Hans Boehm et al: +// https://www.cs.rit.edu/usr/local/pub/jeh/courses/QUARTERS/FP/Labs/CedarRope/rope-paper.pdf +// In this paper authors shows that rebalancing based on cord forest of already +// balanced subtrees can be proven to never produce tree of depth larger than +// largest Fibonacci number representable in the same integral type as cord size +// For 64 bit integers this is the 93rd Fibonacci number. For 32 bit integrals +// this is 47th Fibonacci number. +constexpr size_t MaxCordDepth() { return sizeof(size_t) == 8 ? 93 : 47; } // This class models fixed max size stack of CordRep pointers. // The elements are being pushed back and popped from the back. diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc index d6e091f8b24e..f2d81d4c40d0 100644 --- a/absl/strings/cord_test.cc +++ b/absl/strings/cord_test.cc @@ -1403,12 +1403,16 @@ TEST(CordChunkIterator, Operations) { } TEST(CordChunkIterator, MaxLengthFullTree) { + // Start with a 1-byte cord, and then double its length in a loop. We should + // be able to do this until the point where we would overflow size_t. + absl::Cord cord; size_t size = 1; AddExternalMemory("x", &cord); EXPECT_EQ(cord.size(), size); - for (int i = 0; i < 63; ++i) { + const int kCordLengthDoublingLimit = std::numeric_limits::digits - 1; + for (int i = 0; i < kCordLengthDoublingLimit; ++i) { cord.Prepend(absl::Cord(cord)); size <<= 1; @@ -1431,7 +1435,7 @@ TEST(CordChunkIterator, MaxDepth) { AddExternalMemory("x", &left_child); absl::Cord root = left_child; - for (int i = 0; i < 91; ++i) { + for (int i = 0; i < absl::cord_internal::MaxCordDepth() - 2; ++i) { size_t new_size = left_child.size() + root.size(); root.Prepend(left_child); EXPECT_EQ(root.size(), new_size); @@ -1442,7 +1446,7 @@ TEST(CordChunkIterator, MaxDepth) { std::swap(left_child, root); } - EXPECT_DEATH_IF_SUPPORTED(root.Prepend(left_child), "Cord depth exceeds max"); + EXPECT_DEATH_IF_SUPPORTED(root.Prepend(left_child), "Cord is too long"); } TEST(CordCharIterator, Traits) { diff --git a/absl/types/optional.h b/absl/types/optional.h index 2025e29f86a9..01d747d78bb2 100644 --- a/absl/types/optional.h +++ b/absl/types/optional.h @@ -444,7 +444,7 @@ class optional : private optional_internal::optional_data, // Returns false if and only if the `optional` is empty. // // if (opt) { - // // do something with opt.value(); + // // do something with *opt or opt->; // } else { // // opt is empty. // } diff --git a/ci/macos_xcode_cmake.sh b/ci/macos_xcode_cmake.sh index a1f4a857be3f..aa9ee15d6430 100755 --- a/ci/macos_xcode_cmake.sh +++ b/ci/macos_xcode_cmake.sh @@ -36,7 +36,7 @@ for compilation_mode in ${ABSL_CMAKE_BUILD_TYPES}; do time cmake ${ABSEIL_ROOT} \ -GXcode \ -DCMAKE_BUILD_TYPE=${compilation_mode} \ - -DCMAKE_CXX_STANDARD=11 \ + -DCMAKE_CXX_FLAGS=-std=c++14 \ -DABSL_USE_GOOGLETEST_HEAD=ON \ -DABSL_RUN_TESTS=ON time cmake --build . -- cgit 1.4.1