diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 18f4f33..8abab5d 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -724,10 +724,18 @@ "status_matchers" ) -include(CheckCXXSourceCompiles) +if(DEFINED CMAKE_CXX_STANDARD AND CMAKE_CXX_STANDARD_REQUIRED) + if(CMAKE_CXX_STANDARD GREATER_EQUAL 20) + set(ABSL_INTERNAL_AT_LEAST_CXX20 ON) + set(ABSL_INTERNAL_AT_LEAST_CXX17 ON) + elseif(CMAKE_CXX_STANDARD GREATER_EQUAL 17) + set(ABSL_INTERNAL_AT_LEAST_CXX17 ON) + endif() +else() + include(CheckCXXSourceCompiles) -check_cxx_source_compiles( - [==[ + check_cxx_source_compiles( + [==[ #ifdef _MSC_VER # if _MSVC_LANG < 201703L # error "The compiler defaults or is configured for C++ < 17" @@ -737,10 +745,10 @@ #endif int main() { return 0; } ]==] - ABSL_INTERNAL_AT_LEAST_CXX17) + ABSL_INTERNAL_AT_LEAST_CXX17) -check_cxx_source_compiles( - [==[ + check_cxx_source_compiles( + [==[ #ifdef _MSC_VER # if _MSVC_LANG < 202002L # error "The compiler defaults or is configured for C++ < 20" @@ -750,7 +758,8 @@ #endif int main() { return 0; } ]==] - ABSL_INTERNAL_AT_LEAST_CXX20) + ABSL_INTERNAL_AT_LEAST_CXX20) +endif() if(ABSL_INTERNAL_AT_LEAST_CXX20) set(ABSL_INTERNAL_CXX_STD_FEATURE cxx_std_20)
diff --git a/absl/algorithm/container_test.cc b/absl/algorithm/container_test.cc index 2d2fec1..7778dce 100644 --- a/absl/algorithm/container_test.cc +++ b/absl/algorithm/container_test.cc
@@ -111,8 +111,7 @@ static_cast<size_t>(absl::c_distance(container_))); EXPECT_EQ(sequence_.size(), static_cast<size_t>(absl::c_distance(sequence_))); EXPECT_EQ(vector_.size(), static_cast<size_t>(absl::c_distance(vector_))); - EXPECT_EQ(ABSL_ARRAYSIZE(array_), - static_cast<size_t>(absl::c_distance(array_))); + EXPECT_EQ(std::size(array_), static_cast<size_t>(absl::c_distance(array_))); // Works with a temporary argument. EXPECT_EQ(vector_.size(),
diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index 2ecb1a6..6bbddd4 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel
@@ -1093,8 +1093,8 @@ "@do_not_use_for_gloop_visibility_only//gloop/perftools/tracing:__subpackages__", ], deps = [ - "//absl/base:config", - "//absl/base:core_headers", + ":config", + ":core_headers", ], )
diff --git a/absl/base/bit_cast_test.cc b/absl/base/bit_cast_test.cc index 8a3a41e..8bded1d 100644 --- a/absl/base/bit_cast_test.cc +++ b/absl/base/bit_cast_test.cc
@@ -16,10 +16,10 @@ #include <cstdint> #include <cstring> +#include <iterator> #include "gtest/gtest.h" #include "absl/base/casts.h" -#include "absl/base/macros.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -62,25 +62,25 @@ TEST(BitCast, Bool) { static const bool bool_list[] = { false, true }; - TestMarshall<bool>(bool_list, ABSL_ARRAYSIZE(bool_list)); + TestMarshall<bool>(bool_list, std::size(bool_list)); } TEST(BitCast, Int32) { static const int32_t int_list[] = { 0, 1, 100, 2147483647, -1, -100, -2147483647, -2147483647-1 }; - TestMarshall<int32_t>(int_list, ABSL_ARRAYSIZE(int_list)); + TestMarshall<int32_t>(int_list, std::size(int_list)); } TEST(BitCast, Int64) { static const int64_t int64_list[] = { 0, 1, 1LL << 40, -1, -(1LL<<40) }; - TestMarshall<int64_t>(int64_list, ABSL_ARRAYSIZE(int64_list)); + TestMarshall<int64_t>(int64_list, std::size(int64_list)); } TEST(BitCast, Uint64) { static const uint64_t uint64_list[] = { 0, 1, 1LLU << 40, 1LLU << 63 }; - TestMarshall<uint64_t>(uint64_list, ABSL_ARRAYSIZE(uint64_list)); + TestMarshall<uint64_t>(uint64_list, std::size(uint64_list)); } TEST(BitCast, Float) { @@ -88,9 +88,9 @@ { 0.0f, 1.0f, -1.0f, 10.0f, -10.0f, 1e10f, 1e20f, 1e-10f, 1e-20f, 2.71828f, 3.14159f }; - TestMarshall<float>(float_list, ABSL_ARRAYSIZE(float_list)); - TestIntegral<float, int>(float_list, ABSL_ARRAYSIZE(float_list)); - TestIntegral<float, unsigned>(float_list, ABSL_ARRAYSIZE(float_list)); + TestMarshall<float>(float_list, std::size(float_list)); + TestIntegral<float, int>(float_list, std::size(float_list)); + TestIntegral<float, unsigned>(float_list, std::size(float_list)); } TEST(BitCast, Double) { @@ -99,9 +99,9 @@ 1e10, 1e100, 1e-10, 1e-100, 2.718281828459045, 3.141592653589793238462643383279502884197169399375105820974944 }; - TestMarshall<double>(double_list, ABSL_ARRAYSIZE(double_list)); - TestIntegral<double, int64_t>(double_list, ABSL_ARRAYSIZE(double_list)); - TestIntegral<double, uint64_t>(double_list, ABSL_ARRAYSIZE(double_list)); + TestMarshall<double>(double_list, std::size(double_list)); + TestIntegral<double, int64_t>(double_list, std::size(double_list)); + TestIntegral<double, uint64_t>(double_list, std::size(double_list)); } } // namespace
diff --git a/absl/base/call_once.h b/absl/base/call_once.h index 1abac86..77852d1 100644 --- a/absl/base/call_once.h +++ b/absl/base/call_once.h
@@ -29,6 +29,7 @@ #include <atomic> #include <cstdint> #include <functional> +#include <iterator> #include <type_traits> #include <utility> @@ -38,7 +39,6 @@ #include "absl/base/internal/raw_logging.h" #include "absl/base/internal/scheduling_mode.h" #include "absl/base/internal/spinlock_wait.h" -#include "absl/base/macros.h" #include "absl/base/nullability.h" #include "absl/base/optimization.h" #include "absl/base/port.h" @@ -180,7 +180,7 @@ uint32_t old_control = kOnceInit; if (control->compare_exchange_strong(old_control, kOnceRunning, std::memory_order_relaxed) || - base_internal::SpinLockWait(control, ABSL_ARRAYSIZE(trans), trans, + base_internal::SpinLockWait(control, std::size(trans), trans, scheduling_mode) == kOnceInit) { std::invoke(std::forward<Callable>(fn), std::forward<Args>(args)...); old_control =
diff --git a/absl/base/fast_type_id_test.cc b/absl/base/fast_type_id_test.cc index d27d9fa..a957d70 100644 --- a/absl/base/fast_type_id_test.cc +++ b/absl/base/fast_type_id_test.cc
@@ -16,6 +16,7 @@ #include <cstddef> #include <cstdint> +#include <iterator> #include <map> #include <vector> @@ -61,7 +62,7 @@ }; // clang-format on - for (size_t i = 0; i < ABSL_ARRAYSIZE(kTypeIds); ++i) { + for (size_t i = 0; i < std::size(kTypeIds); ++i) { EXPECT_EQ(kTypeIds[i], kTypeIds[i]); for (size_t j = 0; j < i; ++j) { EXPECT_NE(kTypeIds[i], kTypeIds[j]); @@ -97,7 +98,7 @@ }; // clang-format on - for (size_t i = 0; i < ABSL_ARRAYSIZE(kTypeIds); ++i) { + for (size_t i = 0; i < std::size(kTypeIds); ++i) { EXPECT_EQ(kTypeIds[i], kTypeIds[i]); for (size_t j = 0; j < i; ++j) { EXPECT_NE(kTypeIds[i], kTypeIds[j]);
diff --git a/absl/base/macros.h b/absl/base/macros.h index 46432f0..c435ebc 100644 --- a/absl/base/macros.h +++ b/absl/base/macros.h
@@ -43,6 +43,9 @@ // Returns the number of elements in an array as a compile-time constant, which // can be used in defining new arrays. If you use this macro on a pointer by // mistake, you will get a compile-time error. +// +// NOTE: Avoid using this macro. Instead, use std::size(a) if possible, or +// std::extent_v<decltype(a)> otherwise. #define ABSL_ARRAYSIZE(array) \ (sizeof(::absl::macros_internal::ArraySizeHelper(array)))
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index e535d9e..4138d99 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -1287,8 +1287,8 @@ "//absl/container:__pkg__", ], deps = [ + ":test_instance_tracker", "//absl/base:config", - "//absl/container:test_instance_tracker", "@googletest//:gtest", ], ) @@ -1301,9 +1301,9 @@ visibility = ["//visibility:public"], deps = [ ":common", + ":flat_hash_set", "//absl/base:config", "//absl/base:core_headers", - "//absl/container:flat_hash_set", ], ) @@ -1313,17 +1313,17 @@ copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ + ":hash_generator_testing", + ":hash_policy_testing", ":heterogeneous_lookup_testing", ":linked_hash_set", ":test_allocator", + ":test_instance_tracker", + ":unordered_set_constructor_test", + ":unordered_set_lookup_test", + ":unordered_set_members_test", + ":unordered_set_modifiers_test", "//absl/base:config", - "//absl/container:hash_generator_testing", - "//absl/container:hash_policy_testing", - "//absl/container:test_instance_tracker", - "//absl/container:unordered_set_constructor_test", - "//absl/container:unordered_set_lookup_test", - "//absl/container:unordered_set_members_test", - "//absl/container:unordered_set_modifiers_test", "//absl/strings:string_view", "@googletest//:gtest", "@googletest//:gtest_main", @@ -1355,10 +1355,10 @@ visibility = ["//visibility:public"], deps = [ ":common", + ":flat_hash_set", "//absl/base:config", "//absl/base:core_headers", "//absl/base:throw_delegate", - "//absl/container:flat_hash_set", ], ) @@ -1368,18 +1368,18 @@ copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ + ":hash_generator_testing", + ":hash_policy_testing", ":heterogeneous_lookup_testing", ":linked_hash_map", ":test_allocator", + ":test_instance_tracker", + ":unordered_map_constructor_test", + ":unordered_map_lookup_test", + ":unordered_map_members_test", + ":unordered_map_modifiers_test", "//absl/base:config", "//absl/base:exception_testing", - "//absl/container:hash_generator_testing", - "//absl/container:hash_policy_testing", - "//absl/container:test_instance_tracker", - "//absl/container:unordered_map_constructor_test", - "//absl/container:unordered_map_lookup_test", - "//absl/container:unordered_map_members_test", - "//absl/container:unordered_map_modifiers_test", "//absl/strings:string_view", "@googletest//:gtest", "@googletest//:gtest_main",
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index 8668777..b2e1f4c 100644 --- a/absl/container/btree_test.cc +++ b/absl/container/btree_test.cc
@@ -766,15 +766,12 @@ } }; -template <typename T> -bool CanEraseWithEmptyBrace(T t, decltype(t.erase({})) *) { - return true; -} +template <class T, class = void> +struct CanEraseWithEmptyBrace : std::false_type {}; -template <typename T> -bool CanEraseWithEmptyBrace(T, ...) { - return false; -} +template <class T> +struct CanEraseWithEmptyBrace< + T, std::void_t<decltype(std::declval<T>().erase({}))*>> : std::true_type {}; template <typename T> void TestHeterogeneous(T table) { @@ -819,7 +816,7 @@ EXPECT_EQ(table.size() - 1, copy.size()); copy.erase({"5"}); EXPECT_EQ(table.size() - 2, copy.size()); - EXPECT_FALSE(CanEraseWithEmptyBrace(table, nullptr)); + EXPECT_FALSE(CanEraseWithEmptyBrace<T>::value); // Also run it with const T&. if (std::is_class<T>()) TestHeterogeneous<const T &>(table); @@ -1110,7 +1107,7 @@ struct Key {}; struct Cmp { template <typename T> - bool operator()(T, T) const { + [[maybe_unused]] bool operator()(T, T) const { return false; } };
diff --git a/absl/container/fixed_array_test.cc b/absl/container/fixed_array_test.cc index 81fb0e5..da2f170 100644 --- a/absl/container/fixed_array_test.cc +++ b/absl/container/fixed_array_test.cc
@@ -18,6 +18,7 @@ #include <cstring> #include <forward_list> +#include <iterator> #include <list> #include <memory> #include <numeric> @@ -361,20 +362,20 @@ TEST(IteratorConstructorTest, NonInline) { int const kInput[] = {2, 3, 5, 7, 11, 13, 17}; - absl::FixedArray<int, ABSL_ARRAYSIZE(kInput) - 1> const fixed( - kInput, kInput + ABSL_ARRAYSIZE(kInput)); - ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size()); - for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) { + absl::FixedArray<int, std::size(kInput) - 1> const fixed( + kInput, kInput + std::size(kInput)); + ASSERT_EQ(std::size(kInput), fixed.size()); + for (size_t i = 0; i < std::size(kInput); ++i) { ASSERT_EQ(kInput[i], fixed[i]); } } TEST(IteratorConstructorTest, Inline) { int const kInput[] = {2, 3, 5, 7, 11, 13, 17}; - absl::FixedArray<int, ABSL_ARRAYSIZE(kInput)> const fixed( - kInput, kInput + ABSL_ARRAYSIZE(kInput)); - ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size()); - for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) { + absl::FixedArray<int, std::size(kInput)> const fixed( + kInput, kInput + std::size(kInput)); + ASSERT_EQ(std::size(kInput), fixed.size()); + for (size_t i = 0; i < std::size(kInput); ++i) { ASSERT_EQ(kInput[i], fixed[i]); } } @@ -382,10 +383,9 @@ TEST(IteratorConstructorTest, NonPod) { char const* kInput[] = {"red", "orange", "yellow", "green", "blue", "indigo", "violet"}; - absl::FixedArray<std::string> const fixed(kInput, - kInput + ABSL_ARRAYSIZE(kInput)); - ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size()); - for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) { + absl::FixedArray<std::string> const fixed(kInput, kInput + std::size(kInput)); + ASSERT_EQ(std::size(kInput), fixed.size()); + for (size_t i = 0; i < std::size(kInput); ++i) { ASSERT_EQ(kInput[i], fixed[i]); } } @@ -399,7 +399,7 @@ TEST(IteratorConstructorTest, FromNonEmptyVector) { int const kInput[] = {2, 3, 5, 7, 11, 13, 17}; - std::vector<int> const items(kInput, kInput + ABSL_ARRAYSIZE(kInput)); + std::vector<int> const items(kInput, kInput + std::size(kInput)); absl::FixedArray<int> const fixed(items.begin(), items.end()); ASSERT_EQ(items.size(), fixed.size()); for (size_t i = 0; i < items.size(); ++i) { @@ -409,7 +409,7 @@ TEST(IteratorConstructorTest, FromBidirectionalIteratorRange) { int const kInput[] = {2, 3, 5, 7, 11, 13, 17}; - std::list<int> const items(kInput, kInput + ABSL_ARRAYSIZE(kInput)); + std::list<int> const items(kInput, kInput + std::size(kInput)); absl::FixedArray<int> const fixed(items.begin(), items.end()); EXPECT_THAT(fixed, testing::ElementsAreArray(kInput)); } @@ -695,7 +695,7 @@ const int ia[] = {0, 1, 2, 3, 4, 5, 6, 7}; Alloc alloc(&allocated, &active_instances); - AllocFxdArr arr(ia, ia + ABSL_ARRAYSIZE(ia), alloc); + AllocFxdArr arr(ia, ia + std::size(ia), alloc); EXPECT_EQ(allocated, arr.size() * sizeof(int)); static_cast<void>(arr);
diff --git a/absl/container/inlined_vector_test.cc b/absl/container/inlined_vector_test.cc index c9af35d..a175ea5 100644 --- a/absl/container/inlined_vector_test.cc +++ b/absl/container/inlined_vector_test.cc
@@ -1806,7 +1806,9 @@ MyAlloc alloc(&allocated); { AllocVec ABSL_ATTRIBUTE_UNUSED v; } { AllocVec ABSL_ATTRIBUTE_UNUSED v(alloc); } - { AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + ABSL_ARRAYSIZE(ia), alloc); } + { + AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + std::size(ia), alloc); + } { AllocVec ABSL_ATTRIBUTE_UNUSED v({1, 2, 3}, alloc); } AllocVec v2; @@ -1829,7 +1831,7 @@ EXPECT_THAT(bytes_allocated, Eq(0)); EXPECT_THAT(instance_count, Eq(0)); { - AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + ABSL_ARRAYSIZE(ia), alloc); + AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + std::size(ia), alloc); EXPECT_THAT(bytes_allocated, Eq(static_cast<int64_t>(v.size() * sizeof(int)))); EXPECT_THAT(instance_count, Eq(static_cast<int64_t>(v.size()))); @@ -1904,8 +1906,8 @@ const int ia2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8}; MyAlloc a1(&allocated1); MyAlloc a2(&allocated2); - AllocVec v1(ia1, ia1 + ABSL_ARRAYSIZE(ia1), a1); - AllocVec v2(ia2, ia2 + ABSL_ARRAYSIZE(ia2), a2); + AllocVec v1(ia1, ia1 + std::size(ia1), a1); + AllocVec v2(ia2, ia2 + std::size(ia2), a2); EXPECT_LT(v1.capacity(), v2.capacity()); EXPECT_THAT(allocated1, Eq(static_cast<int64_t>(v1.capacity() * sizeof(int)))); @@ -1933,8 +1935,8 @@ const int ia2[] = {0, 1, 2, 3}; MyAlloc a1(&allocated1); MyAlloc a2(&allocated2); - AllocVec v1(ia1, ia1 + ABSL_ARRAYSIZE(ia1), a1); - AllocVec v2(ia2, ia2 + ABSL_ARRAYSIZE(ia2), a2); + AllocVec v1(ia1, ia1 + std::size(ia1), a1); + AllocVec v2(ia2, ia2 + std::size(ia2), a2); EXPECT_THAT(allocated1, Eq(static_cast<int64_t>(v1.capacity() * sizeof(int)))); EXPECT_THAT(allocated2, Eq(0));
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 7fb5f03..5a4fce8 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -431,19 +431,22 @@ // General notes on capacity/growth methods below: // - We use 7/8th as maximum load factor. For 16-wide groups, that gives an // average of two empty slots per group. -// - For (capacity+1) >= Group::kWidth, growth is 7/8*capacity. // - For (capacity+1) < Group::kWidth, growth == capacity. In this case, we // never need to probe (the whole table fits in one group) so we don't need a // load factor less than 1. +// - For tables with capacity <= kMaxCapacityForLoadFactorOne, we leave one +// empty slot. +// - For capacity > kMaxCapacityForLoadFactorOne, growth is 7/8*capacity. +constexpr inline size_t kMaxCapacityForLoadFactorOne = Group::kWidth * 4 - 1; // Given `capacity`, applies the load factor; i.e., it returns the maximum // number of values we should put into the table before a resizing rehash. constexpr size_t CapacityToGrowth(size_t capacity) { ABSL_SWISSTABLE_ASSERT(IsValidCapacity(capacity)); // `capacity*7/8` - if (Group::kWidth == 8 && capacity == 7) { - // x-x/8 does not work when x==7. - return 6; + if (capacity <= kMaxCapacityForLoadFactorOne) { + // For small capacities we leave at most one empty slot. + return capacity - (capacity >= Group::kWidth - 1); } return capacity - capacity / 8; } @@ -460,7 +463,13 @@ // The minimum possible capacity is NormalizeCapacity(size). // Shifting right `~size_t{}` by `leading_zeros` yields // NormalizeCapacity(size). - int leading_zeros = absl::countl_zero(size); + int leading_zeros = absl::countl_zero( + size + + // Tables larger than half a group require at least one empty slot. + (size >= Group::kWidth / 2)); + if (size < kMaxCapacityForLoadFactorOne) { + return (~size_t{}) >> leading_zeros; + } constexpr size_t kLast3Bits = size_t{7} << (sizeof(size_t) * 8 - 3); // max_size_for_next_capacity = max_load_factor * next_capacity // = (7/8) * (~size_t{} >> leading_zeros) @@ -469,10 +478,6 @@ size_t max_size_for_next_capacity = kLast3Bits >> leading_zeros; // Decrease shift if size is too big for the minimum capacity. leading_zeros -= static_cast<int>(size > max_size_for_next_capacity); - if constexpr (Group::kWidth == 8) { - // Formula doesn't work when size==7 for 8-wide groups. - leading_zeros -= (size == 7); - } return (~size_t{}) >> leading_zeros; } @@ -620,6 +625,45 @@ const IntType seed_; }; +// Represents blocked elements info: log2_period and tail_blocked. +// Every `2**log2_period` is a blocked slot. The first blocked slot is at +// index `2**log2_period-1`. E.g. if log2_period is 2, then every 4th slot +// is blocked: 0, 1, 2, X, 4, 5, 6, X, ... +// +// tail_blocked is the number of blocked slots at the end in addition. +// E.g., log2_period = 2 and tail_blocked = 3, then there are 6 blocked for +// capacity = 15. +// slots: 0, 1, 2, X, 4, 5, 6, X, 8, 9, 10, X, X, X, X, S. (S = sentinel) +class BlockedInfo { + public: + constexpr BlockedInfo(uint8_t log2_period, uint8_t tail_blocked) + : log2_period_(log2_period), tail_blocked_(tail_blocked) { + ABSL_ASSUME(log2_period < 64); + } + + // Returns the log2 of the period for blocked elements. + // Every `2**K` element is blocked starting from index `2**K - 1`. + constexpr uint8_t log2_period() const { return log2_period_; } + // Returns the number of blocked elements at the end of the table. + constexpr uint8_t tail_blocked() const { return tail_blocked_; } + + // Returns the number of blocked elements before the given index. + // Doesn't account for tail_blocked because there are no useful indices in + // the blocked tail. + constexpr size_t blocked_before(size_t index) const { + return index >> log2_period(); + } + + // Returns the number of blocked elements in the table. + constexpr size_t total_blocked_count(size_t capacity) const { + return blocked_before(capacity) + tail_blocked(); + } + + private: + uint8_t log2_period_; + uint8_t tail_blocked_; +}; + // Capacity, size and also has additionally // 1) one bit that stores whether we have infoz. // 2) kBlockedElementsBitCount bits that stores number of blocked elements in
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 0e82471..469341e 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -252,6 +252,60 @@ #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) } +TEST(BlockedInfoTest, ConstructFromComponents) { + constexpr BlockedInfo info(10, 2); + EXPECT_EQ(info.log2_period(), 10); + EXPECT_EQ(info.tail_blocked(), 2); + + constexpr BlockedInfo info_zero(0, 0); + EXPECT_EQ(info_zero.log2_period(), 0); + EXPECT_EQ(info_zero.tail_blocked(), 0); + + constexpr BlockedInfo info_max(63, 3); + EXPECT_EQ(info_max.log2_period(), 63); + EXPECT_EQ(info_max.tail_blocked(), 3); +} + +TEST(BlockedInfoTest, BlockedBefore) { + constexpr BlockedInfo info3(3, 0); + EXPECT_EQ(info3.blocked_before(0), 0); + EXPECT_EQ(info3.blocked_before(7), 0); + EXPECT_EQ(info3.blocked_before(8), 1); + EXPECT_EQ(info3.blocked_before(15), 1); + EXPECT_EQ(info3.blocked_before(16), 2); + EXPECT_EQ(info3.blocked_before(24), 3); + EXPECT_EQ(info3.blocked_before(100), 12); + + constexpr BlockedInfo info0(0, 0); + EXPECT_EQ(info0.blocked_before(0), 0); + EXPECT_EQ(info0.blocked_before(5), 5); + EXPECT_EQ(info0.blocked_before(10), 10); + + constexpr BlockedInfo info4(4, 1); + EXPECT_EQ(info4.blocked_before(0), 0); + EXPECT_EQ(info4.blocked_before(15), 0); + EXPECT_EQ(info4.blocked_before(16), 1); + EXPECT_EQ(info4.blocked_before(31), 1); + EXPECT_EQ(info4.blocked_before(32), 2); +} + +TEST(BlockedInfoTest, TotalBlockedCount) { + constexpr BlockedInfo info(3, 2); + EXPECT_EQ(info.total_blocked_count(0), 2); + EXPECT_EQ(info.total_blocked_count(7), 2); + EXPECT_EQ(info.total_blocked_count(8), 3); + EXPECT_EQ(info.total_blocked_count(15), 3); + EXPECT_EQ(info.total_blocked_count(31), 5); + + constexpr BlockedInfo info_zero(0, 0); + EXPECT_EQ(info_zero.total_blocked_count(0), 0); + EXPECT_EQ(info_zero.total_blocked_count(15), 15); + + constexpr BlockedInfo info_tail(5, 3); + EXPECT_EQ(info_tail.total_blocked_count(31), 3); + EXPECT_EQ(info_tail.total_blocked_count(63), 4); +} + class GrowthInfoAllocator { public: explicit GrowthInfoAllocator(size_t capacity) { @@ -582,25 +636,49 @@ EXPECT_EQ(SizeToCapacity(4), 7); EXPECT_EQ(SizeToCapacity(5), 7); EXPECT_EQ(SizeToCapacity(6), 7); + EXPECT_EQ(SizeToCapacity(14), 15); + EXPECT_EQ(SizeToCapacity(15), 31); + EXPECT_EQ(SizeToCapacity(28), 31); + EXPECT_EQ(SizeToCapacity(29), 31); + EXPECT_EQ(SizeToCapacity(30), 31); + EXPECT_EQ(SizeToCapacity(31), 63); + EXPECT_EQ(SizeToCapacity(56), 63); if (Group::kWidth == 16) { EXPECT_EQ(SizeToCapacity(7), 7); - EXPECT_EQ(SizeToCapacity(14), 15); + EXPECT_EQ(SizeToCapacity(57), 63); + EXPECT_EQ(SizeToCapacity(60), 63); + EXPECT_EQ(SizeToCapacity(61), 63); + EXPECT_EQ(SizeToCapacity(62), 63); } else { EXPECT_EQ(SizeToCapacity(7), 15); + EXPECT_EQ(SizeToCapacity(57), 127); } } TEST(Util, CapacityToGrowthSmallValues) { EXPECT_EQ(CapacityToGrowth(1), 1); EXPECT_EQ(CapacityToGrowth(3), 3); + EXPECT_EQ(CapacityToGrowth(15), 14); + EXPECT_EQ(CapacityToGrowth(31), 30); if (Group::kWidth == 16) { EXPECT_EQ(CapacityToGrowth(7), 7); + EXPECT_EQ(CapacityToGrowth(31), 30); + EXPECT_EQ(CapacityToGrowth(63), 62); } else { EXPECT_EQ(CapacityToGrowth(7), 6); + EXPECT_EQ(CapacityToGrowth(63), 56); } - EXPECT_EQ(CapacityToGrowth(15), 14); - EXPECT_EQ(CapacityToGrowth(31), 28); - EXPECT_EQ(CapacityToGrowth(63), 56); + EXPECT_EQ(CapacityToGrowth(127), 112); +} + +TEST(Table, ReserveGroupWidthCapacity) { + absl::flat_hash_set<int> set; + set.reserve(Group::kWidth * 2 - 2); + EXPECT_EQ(set.capacity(), Group::kWidth * 2 - 1); + set.reserve(Group::kWidth * 2 - 1); + EXPECT_EQ(set.capacity(), Group::kWidth * 4 - 1); + set.reserve(Group::kWidth * 4 - 2); + EXPECT_EQ(set.capacity(), Group::kWidth * 4 - 1); } TEST(Util, GrowthAndCapacity) {
diff --git a/absl/crc/internal/crc.cc b/absl/crc/internal/crc.cc index 6262dd2..ec6a031 100644 --- a/absl/crc/internal/crc.cc +++ b/absl/crc/internal/crc.cc
@@ -41,7 +41,9 @@ #include "absl/crc/internal/crc.h" +#include <cstddef> #include <cstdint> +#include <iterator> #include "absl/base/internal/endian.h" #include "absl/base/internal/raw_logging.h" @@ -206,7 +208,7 @@ } int j = FillZeroesTable(kCrc32cPoly, t); - ABSL_RAW_CHECK(j <= static_cast<int>(ABSL_ARRAYSIZE(this->zeroes_)), ""); + ABSL_RAW_CHECK(j <= static_cast<int>(std::size(this->zeroes_)), ""); for (int i = 0; i < j; i++) { this->zeroes_[i] = t[0][i]; } @@ -250,8 +252,7 @@ FillWordTable(kCrc32cUnextendPoly, kCrc32cUnextendPoly, 1, &reverse_table0_); j = FillZeroesTable(kCrc32cUnextendPoly, &reverse_zeroes_); - ABSL_RAW_CHECK(j <= static_cast<int>(ABSL_ARRAYSIZE(this->reverse_zeroes_)), - ""); + ABSL_RAW_CHECK(j <= static_cast<int>(std::size(this->reverse_zeroes_)), ""); } void CRC32::Extend(uint32_t* crc, const void* bytes, size_t length) const {
diff --git a/absl/crc/internal/crc_x86_arm_combined.cc b/absl/crc/internal/crc_x86_arm_combined.cc index 5e9ef3d..de2af4f 100644 --- a/absl/crc/internal/crc_x86_arm_combined.cc +++ b/absl/crc/internal/crc_x86_arm_combined.cc
@@ -214,11 +214,10 @@ 0x19fb2a8b0, 0x02178513a, 0x1a0f717c4, 0x0170076fa, }; -enum class CutoffStrategy { - // Use 3 CRC streams to fold into 1. - Fold3, - // Unroll CRC instructions for 64 bytes. - Unroll64CRC, +enum class PclmulStreamType { + PCLMUL, + VPCLMUL, + NEON_PCLMUL, }; // Base class for CRC32AcceleratedX86ARMCombinedMultipleStreams containing the @@ -234,6 +233,90 @@ // Computation for Generic Polynomials Using PCLMULQDQ Instruction" // https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf // We are applying it to CRC32C polynomial. +#if defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesNeonPclmul( + const uint8_t* p, V128* partialCRC) const { + V128 loopMultiplicands = + V128_Load(reinterpret_cast<const V128*>(kFoldAcross512Bits)); + + V128 partialCRC1 = partialCRC[0]; + V128 partialCRC2 = partialCRC[1]; + V128 partialCRC3 = partialCRC[2]; + V128 partialCRC4 = partialCRC[3]; + + V128 tmp1 = V128_PMulHi(partialCRC1, loopMultiplicands); + V128 tmp2 = V128_PMulHi(partialCRC2, loopMultiplicands); + V128 tmp3 = V128_PMulHi(partialCRC3, loopMultiplicands); + V128 tmp4 = V128_PMulHi(partialCRC4, loopMultiplicands); + V128 data1 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 0)); + V128 data2 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 1)); + V128 data3 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 2)); + V128 data4 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 3)); + partialCRC1 = V128_PMulLow(partialCRC1, loopMultiplicands); + partialCRC2 = V128_PMulLow(partialCRC2, loopMultiplicands); + partialCRC3 = V128_PMulLow(partialCRC3, loopMultiplicands); + partialCRC4 = V128_PMulLow(partialCRC4, loopMultiplicands); + partialCRC1 = V128_Xor(tmp1, partialCRC1); + partialCRC2 = V128_Xor(tmp2, partialCRC2); + partialCRC3 = V128_Xor(tmp3, partialCRC3); + partialCRC4 = V128_Xor(tmp4, partialCRC4); + partialCRC1 = V128_Xor(partialCRC1, data1); + partialCRC2 = V128_Xor(partialCRC2, data2); + partialCRC3 = V128_Xor(partialCRC3, data3); + partialCRC4 = V128_Xor(partialCRC4, data4); + partialCRC[0] = partialCRC1; + partialCRC[1] = partialCRC2; + partialCRC[2] = partialCRC3; + partialCRC[3] = partialCRC4; + } + + // Reduce partialCRC produced by Process64BytesNeonPclmul into a single value, + // that represents crc checksum of all the processed bytes. + ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + FinalizeNeonPclmulStream(V128* partialCRC) const { + V128 partialCRC1 = partialCRC[0]; + V128 partialCRC2 = partialCRC[1]; + V128 partialCRC3 = partialCRC[2]; + V128 partialCRC4 = partialCRC[3]; + + // Combine 4 vectors of partial crc into a single vector. + V128 reductionMultiplicands = + V128_Load(reinterpret_cast<const V128*>(kFoldAcross256Bits)); + + V128 low = V128_PMulLow(reductionMultiplicands, partialCRC1); + V128 high = V128_PMulHi(reductionMultiplicands, partialCRC1); + + partialCRC1 = V128_Xor(low, high); + partialCRC1 = V128_Xor(partialCRC1, partialCRC3); + + low = V128_PMulLow(reductionMultiplicands, partialCRC2); + high = V128_PMulHi(reductionMultiplicands, partialCRC2); + + partialCRC2 = V128_Xor(low, high); + partialCRC2 = V128_Xor(partialCRC2, partialCRC4); + + reductionMultiplicands = + V128_Load(reinterpret_cast<const V128*>(kFoldAcross128Bits)); + + low = V128_PMulLow(reductionMultiplicands, partialCRC1); + high = V128_PMulHi(reductionMultiplicands, partialCRC1); + V128 fullCRC = V128_Xor(low, high); + fullCRC = V128_Xor(fullCRC, partialCRC2); + + // Reduce fullCRC into scalar value. + uint32_t crc = 0; + crc = CRC32_u64(crc, V128_Extract64<0>(fullCRC)); + crc = CRC32_u64(crc, V128_Extract64<1>(fullCRC)); + return crc; + } + + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul(const uint8_t*, + V128*) const {} + + ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizePclmulStream(V128*) const { + return 0; + } +#else ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul( const uint8_t* p, V128* partialCRC) const { V128 loopMultiplicands = @@ -310,6 +393,14 @@ return crc; } + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesNeonPclmul(const uint8_t*, + V128*) const {} + + ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizeNeonPclmulStream(V128*) const { + return 0; + } +#endif + // Update crc with 64 bytes of data from p. ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t Process64BytesCRC(const uint8_t* p, uint64_t crc) const { @@ -457,7 +548,7 @@ }; template <size_t num_crc_streams, size_t num_pclmul_streams, - size_t num_vpclmul_streams, CutoffStrategy strategy> + PclmulStreamType pclmul_stream_type> class CRC32AcceleratedX86ARMCombinedMultipleStreams : public CRC32AcceleratedX86ARMCombinedMultipleStreamsBase { ABSL_ATTRIBUTE_HOT @@ -467,9 +558,6 @@ "Invalid number of crc streams"); static_assert(num_pclmul_streams >= 0 && num_pclmul_streams <= kMaxStreams, "Invalid number of pclmul streams"); - static_assert( - num_vpclmul_streams >= 0 && num_vpclmul_streams <= kMaxStreams, - "Invalid number of vpclmul streams"); const uint8_t* p = static_cast<const uint8_t*>(bytes); const uint8_t* e = p + length; uint32_t l = *crc; @@ -477,15 +565,15 @@ // For small blocks just run simple loop, because cost of combining multiple // streams is significant. - if (strategy != CutoffStrategy::Unroll64CRC && (length < kSmallCutoff)) { + if (num_crc_streams > 1 && (length < kSmallCutoff)) { // fallthrough; Use the same strategy as we do for processing the // remaining bytes after any other strategy. - } else if (length < kMediumCutoff) { + } else if (length < kMediumCutoff) { // For medium blocks we run 3 crc streams and combine them as described in // Intel paper above. Running 4th stream doesn't help, because crc // instruction has latency 3 and throughput 1. l64 = l; - if (strategy == CutoffStrategy::Fold3) { + if (num_crc_streams > 1) { uint64_t l641 = 0; uint64_t l642 = 0; const size_t blockSize = 32; @@ -526,7 +614,7 @@ l64 = CRC32_u64(static_cast<uint32_t>(l642), l64); p = p2 + 8; - } else if (strategy == CutoffStrategy::Unroll64CRC) { + } else { while ((e - p) >= 64) { l64 = Process64BytesCRC(p, l64); p += 64; @@ -548,8 +636,7 @@ } size_t bs = static_cast<size_t>(e - p) / - (num_crc_streams + num_pclmul_streams + num_vpclmul_streams) / - 64; + (num_crc_streams + num_pclmul_streams) / 64; const uint8_t* stream_start = p; const uint8_t* crc_streams[kMaxStreams]; for (size_t i = 0; i < num_crc_streams; i++) { @@ -561,11 +648,6 @@ pclmul_streams[i] = stream_start; stream_start += bs * 64; } - const uint8_t* vpclmul_streams[kMaxStreams]; - for (size_t i = 0; i < num_vpclmul_streams; i++) { - vpclmul_streams[i] = stream_start; - stream_start += bs * 64; - } // Per stream crc sums. uint64_t l64_crc[kMaxStreams] = {l}; @@ -587,29 +669,10 @@ crc_streams[2] += 16 * 4; } - V128 partialCRC[kMaxStreams][4]; + // Align to 32 bytes for vpclmul implementation. + alignas(32) V128 partialCRC[kMaxStreams][4]; for (size_t i = 0; i < num_pclmul_streams; i++) { - partialCRC[i][0] = V128_LoadU( - reinterpret_cast<const V128*>(pclmul_streams[i] + 16 * 0)); - partialCRC[i][1] = V128_LoadU( - reinterpret_cast<const V128*>(pclmul_streams[i] + 16 * 1)); - partialCRC[i][2] = V128_LoadU( - reinterpret_cast<const V128*>(pclmul_streams[i] + 16 * 2)); - partialCRC[i][3] = V128_LoadU( - reinterpret_cast<const V128*>(pclmul_streams[i] + 16 * 3)); - pclmul_streams[i] += 16 * 4; - } - - V256 vpartialCRC[kMaxStreams][2]; - V256 loopMultiplicands{}; - loopMultiplicands = - V256_Broadcast128(reinterpret_cast<const V128*>(kFoldAcross512Bits)); - for (size_t i = 0; i < num_vpclmul_streams; i++) { - vpartialCRC[i][0] = V256_LoadU( - reinterpret_cast<const V256*>(vpclmul_streams[i] + 32 * 0)); - vpartialCRC[i][1] = V256_LoadU( - reinterpret_cast<const V256*>(vpclmul_streams[i] + 32 * 1)); - vpclmul_streams[i] += 16 * 4; + InitPclmulStream(&pclmul_streams[i], partialCRC[i]); } for (size_t i = 1; i < bs; i++) { @@ -622,10 +685,6 @@ PrefetchToLocalCache(reinterpret_cast<const char*>(pclmul_streams[j] + kPrefetchHorizon)); } - for (size_t j = 0; j < num_vpclmul_streams; j++) { - PrefetchToLocalCache(reinterpret_cast<const char*>( - vpclmul_streams[j] + kPrefetchHorizon)); - } // We process each stream in 64 byte blocks. This can be written as // for (int i = 0; i < num_pclmul_streams; i++) { @@ -652,23 +711,8 @@ crc_streams[1] += 16 * 4; crc_streams[2] += 16 * 4; } - if (num_pclmul_streams > 0) { - Process64BytesPclmul(pclmul_streams[0], partialCRC[0]); - pclmul_streams[0] += 16 * 4; - } - if (num_pclmul_streams > 1) { - Process64BytesPclmul(pclmul_streams[1], partialCRC[1]); - pclmul_streams[1] += 16 * 4; - } - if (num_pclmul_streams > 2) { - Process64BytesPclmul(pclmul_streams[2], partialCRC[2]); - pclmul_streams[2] += 16 * 4; - } - - if constexpr (num_vpclmul_streams > 0) { - Process64BytesVpclmul(vpclmul_streams[0], vpartialCRC[0], - loopMultiplicands); - vpclmul_streams[0] += 16 * 4; + for (size_t j = 0; j < num_pclmul_streams; j++) { + ProcessPclmulStream(&pclmul_streams[j], partialCRC[j]); } } @@ -678,13 +722,6 @@ l64_pclmul[i] = FinalizePclmulStream(partialCRC[i]); } - uint64_t l64_vpclmul[kMaxStreams] = {0}; - if constexpr (num_vpclmul_streams > 0) { - for (size_t i = 0; i < num_vpclmul_streams; i++) { - l64_vpclmul[i] = FinalizeVpclmulStream(vpartialCRC[i]); - } - } - // Combine all streams into single result. static_assert(64 % (1 << kNumDroppedBits) == 0); uint32_t magic = ComputeZeroConstant(bs * 64); @@ -697,15 +734,9 @@ l64 = MultiplyWithExtraX33(static_cast<uint32_t>(l64), magic); l64 ^= l64_pclmul[i]; } - for (size_t i = 0; i < num_vpclmul_streams; i++) { - l64 = MultiplyWithExtraX33(static_cast<uint32_t>(l64), magic); - l64 ^= l64_vpclmul[i]; - } // Update p. - if constexpr (num_vpclmul_streams > 0) { - p = vpclmul_streams[num_vpclmul_streams - 1]; - } else if constexpr (num_pclmul_streams > 0) { + if constexpr (num_pclmul_streams > 0) { p = pclmul_streams[num_pclmul_streams - 1]; } else { p = crc_streams[num_crc_streams - 1]; @@ -735,6 +766,55 @@ *crc = l; } + + private: + ABSL_ATTRIBUTE_ALWAYS_INLINE void InitPclmulStream( + const uint8_t** pclmul_stream, V128* partialCRC) const { + if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { + V256* vpartialCRC = reinterpret_cast<V256*>(partialCRC); + vpartialCRC[0] = + V256_LoadU(reinterpret_cast<const V256*>(*pclmul_stream + 32 * 0)); + vpartialCRC[1] = + V256_LoadU(reinterpret_cast<const V256*>(*pclmul_stream + 32 * 1)); + } else { + partialCRC[0] = + V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 0)); + partialCRC[1] = + V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 1)); + partialCRC[2] = + V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 2)); + partialCRC[3] = + V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 3)); + } + *pclmul_stream += 16 * 4; + } + + ABSL_ATTRIBUTE_ALWAYS_INLINE void ProcessPclmulStream( + const uint8_t** pclmul_stream, V128* partialCRC) const { + if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { + V256 loopMultiplicands = + V256_Broadcast128(reinterpret_cast<const V128*>(kFoldAcross512Bits)); + Process64BytesVpclmul(*pclmul_stream, reinterpret_cast<V256*>(partialCRC), + loopMultiplicands); + } else if constexpr (pclmul_stream_type == PclmulStreamType::NEON_PCLMUL) { + Process64BytesNeonPclmul(*pclmul_stream, partialCRC); + } else { + Process64BytesPclmul(*pclmul_stream, partialCRC); + } + *pclmul_stream += 16 * 4; + } + + ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + FinalizePclmulStream(V128* partialCRC) const { + if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { + return FinalizeVpclmulStream(reinterpret_cast<V256*>(partialCRC)); + } else if constexpr (pclmul_stream_type == PclmulStreamType::NEON_PCLMUL) { + return FinalizeNeonPclmulStream(partialCRC); + } else { + return CRC32AcceleratedX86ARMCombinedMultipleStreamsBase:: + FinalizePclmulStream(partialCRC); + } + } }; #undef ABSL_INTERNAL_STEP8BY3 @@ -753,11 +833,11 @@ switch (type) { case CpuType::kAmdRome: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 0, 0, CutoffStrategy::Fold3>(); + 3, 0, PclmulStreamType::PCLMUL>(); case CpuType::kIntelHaswell: case CpuType::kAmdNaples: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 1, 0, CutoffStrategy::Fold3>(); + 3, 1, PclmulStreamType::PCLMUL>(); case CpuType::kAmdMilan: case CpuType::kAmdGenoa: case CpuType::kAmdTurin: @@ -766,10 +846,10 @@ // We don't have vector pclmul on arm, but this still needs to // compile. return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 0, 1, CutoffStrategy::Fold3>(); + 3, 1, PclmulStreamType::VPCLMUL>(); #else return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 1, 0, CutoffStrategy::Fold3>(); + 3, 1, PclmulStreamType::PCLMUL>(); #endif // PCLMULQDQ is fast, use combined PCLMULQDQ + CRC implementation. case CpuType::kIntelCascadelakeXeon: @@ -781,33 +861,33 @@ case CpuType::kIntelEmeraldrapids: case CpuType::kIntelGraniterapids: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 2, 0, CutoffStrategy::Fold3>(); + 3, 2, PclmulStreamType::PCLMUL>(); // PCLMULQDQ is slow, don't use it. case CpuType::kIntelIvybridge: case CpuType::kIntelSandybridge: case CpuType::kIntelWestmere: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 0, 0, CutoffStrategy::Fold3>(); + 3, 0, PclmulStreamType::PCLMUL>(); case CpuType::kArmNeoverseN1: case CpuType::kArmNeoverseN2: case CpuType::kArmNeoverseV1: case CpuType::kArmNeoverseN3: case CpuType::kNvidiaGrace: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 1, 1, 0, CutoffStrategy::Unroll64CRC>(); + 1, 1, PclmulStreamType::NEON_PCLMUL>(); case CpuType::kAmpereSiryn: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 2, 0, CutoffStrategy::Fold3>(); + 3, 2, PclmulStreamType::NEON_PCLMUL>(); case CpuType::kArmNeoverseV2: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 1, 2, 0, CutoffStrategy::Unroll64CRC>(); + 1, 2, PclmulStreamType::NEON_PCLMUL>(); #if defined(__aarch64__) default: // Not all ARM processors support the needed instructions, so check here // before trying to use an accelerated implementation. if (SupportsArmCRC32PMULL()) { return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 1, 1, 0, CutoffStrategy::Unroll64CRC>(); + 1, 1, PclmulStreamType::NEON_PCLMUL>(); } else { return nullptr; } @@ -815,7 +895,7 @@ default: // Something else, play it safe and assume slow PCLMULQDQ. return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 0, 0, CutoffStrategy::Fold3>(); + 3, 0, PclmulStreamType::PCLMUL>(); #endif } }
diff --git a/absl/debugging/internal/demangle.cc b/absl/debugging/internal/demangle.cc index 5b2d623..c82274f 100644 --- a/absl/debugging/internal/demangle.cc +++ b/absl/debugging/internal/demangle.cc
@@ -973,6 +973,7 @@ // Unnamed type local to function or class. if (ParseTwoCharToken(state, "Ut") && Optional(ParseNumber(state, &which)) && + which >= -1 && // Don't print garbage. which <= std::numeric_limits<int>::max() - 2 && // Don't overflow. ParseOneCharToken(state, '_')) { MaybeAppend(state, "{unnamed type#"); @@ -988,6 +989,7 @@ ZeroOrMore(ParseTemplateParamDecl, state) && OneOrMore(ParseType, state) && RestoreAppend(state, copy.append) && ParseOneCharToken(state, 'E') && Optional(ParseNumber(state, &which)) && + which >= -1 && // Don't print garbage. which <= std::numeric_limits<int>::max() - 2 && // Don't overflow. ParseOneCharToken(state, '_')) { MaybeAppend(state, "{lambda()#");
diff --git a/absl/debugging/internal/demangle_rust.cc b/absl/debugging/internal/demangle_rust.cc index 75c46ec..6ca481b 100644 --- a/absl/debugging/internal/demangle_rust.cc +++ b/absl/debugging/internal/demangle_rust.cc
@@ -720,14 +720,30 @@ if (!ParseDecimalNumber(num_bytes)) return false; (void)Eat('_'); // optional separator, needed if a digit follows if (is_punycoded) { - DecodeRustPunycodeOptions options; - options.punycode_begin = &encoding_[pos_]; - options.punycode_end = &encoding_[pos_] + num_bytes; - options.out_begin = out_; - options.out_end = out_end_; - out_ = DecodeRustPunycode(options); - if (out_ == nullptr) return false; - pos_ += static_cast<size_t>(num_bytes); + // A length exceeding the remaining input would make punycode_end point + // past the end of the buffer, forming an out-of-bounds pointer. + if (static_cast<size_t>(num_bytes) > std::strlen(&encoding_[pos_])) { + return false; + } + if (silence_depth_ == 0) { + DecodeRustPunycodeOptions options; + options.punycode_begin = &encoding_[pos_]; + options.punycode_end = &encoding_[pos_] + num_bytes; + options.out_begin = out_; + options.out_end = out_end_; + out_ = DecodeRustPunycode(options); + if (out_ == nullptr) return false; + pos_ += static_cast<size_t>(num_bytes); + } else { + // Output is silenced, so like EmitChar and Emit we produce nothing and + // use no output space. Still consume the identifier's encoded bytes, + // stopping at a premature NUL exactly as the raw-bytes branch below + // does, so a suppressed punycoded identifier (e.g. a punycoded + // fn-signature abi) cannot leak into the demangling. + for (int i = 0; i < num_bytes; ++i) { + if (Take() == '\0') return false; + } + } } // Emit the beginnings of braced forms like {shim:vtable#0}.
diff --git a/absl/debugging/internal/demangle_rust_test.cc b/absl/debugging/internal/demangle_rust_test.cc index 110700e..3f0a904 100644 --- a/absl/debugging/internal/demangle_rust_test.cc +++ b/absl/debugging/internal/demangle_rust_test.cc
@@ -118,6 +118,11 @@ "ice_cap::Eyjafjallajökull"); EXPECT_DEMANGLING("_RNvC7ice_caps_u19Eyjafjallajkull_jtb", "ice_cap::Eyjafjallajökull"); + + // A punycode byte count larger than the remaining input is rejected instead + // of running the decoder past the end of the buffer. + EXPECT_DEMANGLING_FAILS("_RNvC7ice_caps_u2000000000Eyjafjallajkull_jtb"); + EXPECT_DEMANGLING_FAILS("_RNvC7ice_caps_u99Eyj_a"); } TEST(DemangleRust, FunctionInModule) { @@ -524,6 +529,15 @@ "<fn... as c::t>::f"); } +TEST(DemangleRust, ExternPunycodedAbiIsSuppressed) { + // The abi is part of the silenced function signature, so a punycoded abi must + // be suppressed like any other identifier; its decoded form must not leak + // into the output. + EXPECT_DEMANGLING( + // <extern "Eyjafjallajökull" fn() as c::t>::f + "_RNvYFKu19Eyjafjallajkull_jtbEuNtC1c1t1f", "<fn... as c::t>::f"); +} + TEST(DemangleRust, Unsafe) { EXPECT_DEMANGLING("_RNvYFUEuNtC1c1t1f", // <unsafe fn() as c::t>::f "<fn... as c::t>::f");
diff --git a/absl/debugging/internal/demangle_test.cc b/absl/debugging/internal/demangle_test.cc index 7238fd0..50e4359 100644 --- a/absl/debugging/internal/demangle_test.cc +++ b/absl/debugging/internal/demangle_test.cc
@@ -471,6 +471,31 @@ EXPECT_STREQ(tmp, "S::f()::{default arg#1}::{lambda()#1}::operator()()"); } +TEST(Demangle, NegativeUnnamedTypeNumbers) { + char tmp[100]; + + // An omitted <number> denotes index 1 and is left as the -1 sentinel. + ASSERT_TRUE(Demangle("_ZUt_", tmp, sizeof(tmp))); + EXPECT_STREQ(tmp, "{unnamed type#1}"); + ASSERT_TRUE(Demangle("_ZUlvE_", tmp, sizeof(tmp))); + EXPECT_STREQ(tmp, "{lambda()#1}"); + + // Reject an explicitly negative <number>. Left unstrained, <number> + 2 is + // negative, and MaybeAppendDecimal emits (val % 10) + '0' per digit, which + // for a negative val yields characters below '0'. + ASSERT_FALSE(Demangle("_ZUtn3_", tmp, sizeof(tmp))); + ASSERT_FALSE(Demangle("_ZUlvEn3_", tmp, sizeof(tmp))); + + // ParseNumber truncates to int, so an in-range-looking <number> can also + // arrive negative. + ASSERT_FALSE(Demangle("_ZUt2147483648_", tmp, sizeof(tmp))); + ASSERT_FALSE(Demangle("_ZUlvE2147483648_", tmp, sizeof(tmp))); + + // The largest <number> whose index still fits in an int is unaffected. + ASSERT_TRUE(Demangle("_ZUt2147483645_", tmp, sizeof(tmp))); + EXPECT_STREQ(tmp, "{unnamed type#2147483647}"); +} + TEST(Demangle, SubstpackNotationForTroublesomeTemplatePack) { char tmp[100];
diff --git a/absl/debugging/internal/examine_stack.cc b/absl/debugging/internal/examine_stack.cc index a871b04..cf18a51 100644 --- a/absl/debugging/internal/examine_stack.cc +++ b/absl/debugging/internal/examine_stack.cc
@@ -16,6 +16,8 @@ #include "absl/debugging/internal/examine_stack.h" +#include <iterator> + #ifndef _WIN32 #include <unistd.h> #endif @@ -167,7 +169,7 @@ #elif defined(__hppa__) return reinterpret_cast<void*>(context->uc_mcontext.sc_iaoq[0]); #elif defined(__i386__) - if (14 < ABSL_ARRAYSIZE(context->uc_mcontext.gregs)) + if (14 < std::size(context->uc_mcontext.gregs)) return reinterpret_cast<void*>(context->uc_mcontext.gregs[14]); #elif defined(__ia64__) return reinterpret_cast<void*>(context->uc_mcontext.sc_ip); @@ -192,7 +194,7 @@ #elif defined(__sparc__) && defined(__arch64__) return reinterpret_cast<void*>(context->uc_mcontext.mc_gregs[19]); #elif defined(__x86_64__) - if (16 < ABSL_ARRAYSIZE(context->uc_mcontext.gregs)) + if (16 < std::size(context->uc_mcontext.gregs)) return reinterpret_cast<void*>(context->uc_mcontext.gregs[16]); #elif defined(__e2k__) return reinterpret_cast<void*>(context->uc_mcontext.cr0_hi);
diff --git a/absl/debugging/internal/stacktrace_x86-inl.inc b/absl/debugging/internal/stacktrace_x86-inl.inc index 27ee32a..6aa3146 100644 --- a/absl/debugging/internal/stacktrace_x86-inl.inc +++ b/absl/debugging/internal/stacktrace_x86-inl.inc
@@ -17,6 +17,7 @@ #ifndef ABSL_DEBUGGING_INTERNAL_STACKTRACE_X86_INL_INC_ #define ABSL_DEBUGGING_INTERNAL_STACKTRACE_X86_INL_INC_ +#include <cstddef> #if defined(__linux__) && (defined(__i386__) || defined(__x86_64__)) #include <ucontext.h> // for ucontext_t #endif
diff --git a/absl/debugging/symbolize_elf.inc b/absl/debugging/symbolize_elf.inc index 56f31af..06c5634 100644 --- a/absl/debugging/symbolize_elf.inc +++ b/absl/debugging/symbolize_elf.inc
@@ -67,6 +67,7 @@ #include <cstdio> #include <cstdlib> #include <cstring> +#include <iterator> #include <memory> #include "absl/base/casts.h" @@ -712,7 +713,7 @@ // If one of the symbols is weak and the other is not, pick the one // this is not a weak symbol. char bind1 = ELF_ST_BIND(symbol1.st_info); - char bind2 = ELF_ST_BIND(symbol1.st_info); + char bind2 = ELF_ST_BIND(symbol2.st_info); if (bind1 == STB_WEAK && bind2 != STB_WEAK) return false; if (bind2 == STB_WEAK && bind1 != STB_WEAK) return true; @@ -728,7 +729,7 @@ // If one of the symbols has no type and the other is not, pick the // one that has a type. char type1 = ELF_ST_TYPE(symbol1.st_info); - char type2 = ELF_ST_TYPE(symbol1.st_info); + char type2 = ELF_ST_TYPE(symbol2.st_info); if (type1 != STT_NOTYPE && type2 == STT_NOTYPE) { return true; } @@ -1320,7 +1321,7 @@ if (pc == nullptr) return nullptr; SymbolCacheLine *line = GetCacheLine(pc); - for (size_t i = 0; i < ABSL_ARRAYSIZE(line->pc); ++i) { + for (size_t i = 0; i < std::size(line->pc); ++i) { if (line->pc[i] == pc) { AgeSymbols(line); line->age[i] = 0; @@ -1338,7 +1339,7 @@ uint32_t max_age = 0; size_t oldest_index = 0; bool found_oldest_index = false; - for (size_t i = 0; i < ABSL_ARRAYSIZE(line->pc); ++i) { + for (size_t i = 0; i < std::size(line->pc); ++i) { if (line->pc[i] == nullptr) { AgeSymbols(line); line->pc[i] = pc;
diff --git a/absl/flags/flag_test.cc b/absl/flags/flag_test.cc index d303c8d..1dd2f5c 100644 --- a/absl/flags/flag_test.cc +++ b/absl/flags/flag_test.cc
@@ -19,6 +19,7 @@ #include <stdint.h> #include <atomic> +#include <iterator> #include <optional> #include <string> #include <thread> // NOLINT @@ -690,10 +691,10 @@ }); } absl::Time end_time = absl::Now() + absl::Seconds(1); - int i = 0; + size_t i = 0; while (absl::Now() < end_time) { absl::SetFlag(&FLAGS_test_flag_12, - kValidDurations[i++ % ABSL_ARRAYSIZE(kValidDurations)]); + kValidDurations[i++ % std::size(kValidDurations)]); } stop.store(true, std::memory_order_relaxed); for (auto& t : threads) t.join();
diff --git a/absl/flags/internal/parse.h b/absl/flags/internal/parse.h index 10c531b..aa29dea 100644 --- a/absl/flags/internal/parse.h +++ b/absl/flags/internal/parse.h
@@ -63,6 +63,12 @@ // misspellings. std::vector<std::string> GetMisspellingHints(absl::string_view flag); +// IsIndirectFlagExpansionEnabled() +// +// If DisableFlagfileAndEnvParsing() has been called, returns false. Otherwise, +// returns true. +[[nodiscard]] bool IsIndirectFlagExpansionEnabled(); + } // namespace flags_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/flags/parse.cc b/absl/flags/parse.cc index 4961930..736dc8b 100644 --- a/absl/flags/parse.cc +++ b/absl/flags/parse.cc
@@ -18,6 +18,7 @@ #include <stdlib.h> #include <algorithm> +#include <atomic> #include <cstdint> #include <cstdlib> #include <fstream> @@ -64,6 +65,8 @@ namespace flags_internal { namespace { +ABSL_CONST_INIT std::atomic<bool> g_disable_indirect_flag_expansion(false); + absl::Mutex& ProcessingChecksMutex() { static absl::NoDestructor<absl::Mutex> mutex; return *mutex; @@ -354,6 +357,12 @@ // etc. bool ReadFlagfiles(const std::vector<std::string>& flagfiles, std::vector<ArgsList>& input_args) { + if (!flags_internal::IsIndirectFlagExpansionEnabled()) { + flags_internal::ReportUsageError( + "Skipping expansion of --flagfile as it is disabled.", false); + return true; + } + bool success = true; for (auto it = flagfiles.rbegin(); it != flagfiles.rend(); ++it) { ArgsList al; @@ -376,6 +385,13 @@ bool ReadFlagsFromEnv(const std::vector<std::string>& flag_names, std::vector<ArgsList>& input_args, bool fail_on_absent_in_env) { + if (!flags_internal::IsIndirectFlagExpansionEnabled()) { + flags_internal::ReportUsageError( + "Skipping expansion of --fromenv/--tryfromenv as it is disabled.", + false); + return true; + } + bool success = true; std::vector<std::string> args; @@ -921,8 +937,16 @@ : HelpMode::kNone; } +bool IsIndirectFlagExpansionEnabled() { + return !g_disable_indirect_flag_expansion; +} + } // namespace flags_internal +void DisableFlagfileAndEnvParsing() { + flags_internal::g_disable_indirect_flag_expansion = true; +} + void ParseAbseilFlagsOnly(int argc, char* argv[], std::vector<char*>& positional_args, std::vector<UnrecognizedFlag>& unrecognized_flags) {
diff --git a/absl/flags/parse.h b/absl/flags/parse.h index f2a5cb1..fdb3d1e 100644 --- a/absl/flags/parse.h +++ b/absl/flags/parse.h
@@ -124,6 +124,21 @@ // `ParseAbseilFlagsOnly`. std::vector<char*> ParseCommandLine(int argc, char* argv[]); +// DisableFlagfileAndEnvParsing() +// +// Disables the processing of flags that load values from secondary sources, +// specifically `--flagfile`, `--fromenv`, and `--tryfromenv`. When disabled, +// occurrences of these flags on the command line are skipped without opening +// files or inspecting environment variables, and a warning is printed to +// stderr. Direct command-line flags passed via argv are still parsed normally. +// +// This is primarily intended as a security precaution for privileged or setuid +// processes parsing untrusted command lines prior to dropping privileges. +// +// Should only be called in `main()` before calling `absl::ParseCommandLine()` +// or `absl::ParseAbseilFlagsOnly()`. +void DisableFlagfileAndEnvParsing(); + ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/flags/parse_test.cc b/absl/flags/parse_test.cc index 08eb81a..138cf6e 100644 --- a/absl/flags/parse_test.cc +++ b/absl/flags/parse_test.cc
@@ -1091,4 +1091,65 @@ // -------------------------------------------------------------------- +TEST_F(ParseDeathTest, DisableFlagfileAndEnvParsing) { + EXPECT_EXIT( + ([]() { + absl::DisableFlagfileAndEnvParsing(); + std::string flagfile_flag; + const char* args[] = { + "testbin", + "--string_flag=abc", + GetFlagfileFlag({{"parse_test.ff_disabled", {"--int_flag=123"}}}, + flagfile_flag), + }; + InvokeParse(args); + exit(absl::GetFlag(FLAGS_int_flag) == 123 || + absl::GetFlag(FLAGS_string_flag) != "abc" + ? 1 + : 0); + })(), + testing::ExitedWithCode(0), + "Skipping expansion of --flagfile as it is disabled"); + + EXPECT_EXIT(([]() { + absl::DisableFlagfileAndEnvParsing(); + ScopedSetEnv set_int_flag("FLAGS_int_flag", "123"); + const char* args[] = {"testbin", "--string_flag=abc", + "--fromenv=int_flag"}; + InvokeParse(args); + exit(absl::GetFlag(FLAGS_int_flag) == 123 || + absl::GetFlag(FLAGS_string_flag) != "abc" + ? 1 + : 0); + })(), + testing::ExitedWithCode(0), + "Skipping expansion of --fromenv/--tryfromenv as it is disabled"); + + EXPECT_EXIT(([]() { + absl::DisableFlagfileAndEnvParsing(); + ScopedSetEnv set_int_flag("FLAGS_int_flag", "123"); + const char* args[] = {"testbin", "--string_flag=abc", + "--tryfromenv=int_flag"}; + InvokeParse(args); + exit(absl::GetFlag(FLAGS_int_flag) == 123 || + absl::GetFlag(FLAGS_string_flag) != "abc" + ? 1 + : 0); + })(), + testing::ExitedWithCode(0), + "Skipping expansion of --fromenv/--tryfromenv as it is disabled"); +} + +TEST_F(ParseDeathTest, IsIndirectFlagExpansionEnabledWorks) { + EXPECT_EXIT( + ([]() { + if (!absl::flags_internal::IsIndirectFlagExpansionEnabled()) { + exit(1); + } + absl::DisableFlagfileAndEnvParsing(); + exit(absl::flags_internal::IsIndirectFlagExpansionEnabled() ? 2 : 0); + })(), + testing::ExitedWithCode(0), ""); +} + } // namespace
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index 6842a2e..d20b296 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc
@@ -1264,6 +1264,9 @@ #if defined(__wasm__) GTEST_SKIP() << "Fails flakily on wasm due to no ASLR and 32-bit size_t."; #endif +#if defined(__ANDROID__) && defined(__arm__) + GTEST_SKIP() << "Fails on 32-bit Android due to layout changes."; +#endif std::string s1 = "00"; std::string s2 = "000"; constexpr char kMinChar = 0;
diff --git a/absl/log/BUILD.bazel b/absl/log/BUILD.bazel index f44b1c0..5008d88 100644 --- a/absl/log/BUILD.bazel +++ b/absl/log/BUILD.bazel
@@ -466,11 +466,11 @@ textual_hdrs = ["log_basic_test_impl.inc"], visibility = ["//visibility:private"], deps = [ + ":globals", + ":log_entry", + ":scoped_mock_log", "//absl/base", "//absl/base:log_severity", - "//absl/log:globals", - "//absl/log:log_entry", - "//absl/log:scoped_mock_log", "//absl/log/internal:globals", "//absl/log/internal:test_actions", "//absl/log/internal:test_helpers",
diff --git a/absl/profiling/internal/sample_recorder.h b/absl/profiling/internal/sample_recorder.h index 88a4b27..c0e4ebc 100644 --- a/absl/profiling/internal/sample_recorder.h +++ b/absl/profiling/internal/sample_recorder.h
@@ -168,7 +168,7 @@ template <typename T> template <typename... Targs> T* SampleRecorder<T>::PopDead(Targs... args) { - absl::MutexLock graveyard_lock(graveyard_.init_mu); + absl::ReleasableMutexLock graveyard_lock(graveyard_.init_mu); // The list is circular, so eventually it collapses down to // graveyard_.dead == &graveyard_ @@ -178,6 +178,11 @@ absl::MutexLock sample_lock(sample->init_mu); graveyard_.dead = sample->dead; + // Release the global graveyard lock early, before the potentially slow + // preparation. + graveyard_lock.Release(); + // Prepare the sample while still holding the per-sample lock. + // `Iterate` will wait for the lock to be released. sample->dead = nullptr; sample->PrepareForSampling(std::forward<Targs>(args)...); return sample;
diff --git a/absl/random/benchmarks.cc b/absl/random/benchmarks.cc index 4cb16e6..c89388b 100644 --- a/absl/random/benchmarks.cc +++ b/absl/random/benchmarks.cc
@@ -74,13 +74,13 @@ static size_t idx = 0; for (; begin != end; begin++) { *begin = kSeedData[idx++]; - if (idx >= ABSL_ARRAYSIZE(kSeedData)) { + if (idx >= std::size(kSeedData)) { idx = 0; } } } - size_t size() const { return ABSL_ARRAYSIZE(kSeedData); } + size_t size() const { return std::size(kSeedData); } template <typename OutIterator> void param(OutIterator out) const {
diff --git a/absl/random/internal/chi_square_test.cc b/absl/random/internal/chi_square_test.cc index 8e02f7a..964cd22 100644 --- a/absl/random/internal/chi_square_test.cc +++ b/absl/random/internal/chi_square_test.cc
@@ -161,7 +161,7 @@ for (const auto& spec : specs) { SCOPED_TRACE(spec.line); double chi_square = 0; - for (int i = 0; i < spec.expected.size(); ++i) { + for (size_t i = 0; i < spec.expected.size(); ++i) { const double diff = spec.actual[i] - spec.expected[i]; chi_square += (diff * diff) / spec.expected[i]; } @@ -295,7 +295,7 @@ /*100*/ {118.498, 124.342, 129.561, 135.807, 149.449} /**/}; // 0.90 0.95 0.975 0.99 0.999 - for (int i = 0; i < ABSL_ARRAYSIZE(data); i++) { + for (size_t i = 0; i < std::size(data); i++) { const double E = 0.0001; EXPECT_NEAR(ChiSquarePValue(data[i][0], i + 1), 0.10, E) << i << " " << data[i][0];
diff --git a/absl/random/internal/explicit_seed_seq_test.cc b/absl/random/internal/explicit_seed_seq_test.cc index 1cf6806..0052d41 100644 --- a/absl/random/internal/explicit_seed_seq_test.cc +++ b/absl/random/internal/explicit_seed_seq_test.cc
@@ -48,13 +48,13 @@ // Check that param() and size() return state provided to constructor. { uint32_t init_array[] = {1, 2, 3, 4, 5}; - Sseq seq(init_array, &init_array[ABSL_ARRAYSIZE(init_array)]); - EXPECT_EQ(seq.size(), ABSL_ARRAYSIZE(init_array)); + Sseq seq(init_array, &init_array[std::size(init_array)]); + EXPECT_EQ(seq.size(), std::size(init_array)); - uint32_t state_array[ABSL_ARRAYSIZE(init_array)]; + uint32_t state_array[std::size(init_array)]; seq.param(state_array); - for (int i = 0; i < ABSL_ARRAYSIZE(state_array); i++) { + for (int i = 0; i < std::size(state_array); i++) { EXPECT_EQ(state_array[i], i + 1); } } @@ -63,7 +63,7 @@ Sseq seq; uint32_t seeds[5]; - seq.generate(seeds, &seeds[ABSL_ARRAYSIZE(seeds)]); + seq.generate(seeds, &seeds[std::size(seeds)]); } return true; }
diff --git a/absl/random/internal/gaussian_distribution_gentables.cc b/absl/random/internal/gaussian_distribution_gentables.cc index 2132450..967a327 100644 --- a/absl/random/internal/gaussian_distribution_gentables.cc +++ b/absl/random/internal/gaussian_distribution_gentables.cc
@@ -21,6 +21,7 @@ #include <iostream> #include <limits> #include <string> +#include <type_traits> #include "absl/base/config.h" #include "absl/base/macros.h" @@ -80,10 +81,11 @@ // The constants here should match the values in gaussian_distribution.h static constexpr int kC = kMask + 1; - static_assert((ABSL_ARRAYSIZE(tables_.x) == kC + 1), + static_assert((std::extent_v<decltype(tables_.x)> == kC + 1), "xArray must be length kMask + 2"); - static_assert((ABSL_ARRAYSIZE(tables_.x) == ABSL_ARRAYSIZE(tables_.f)), + static_assert((std::extent_v<decltype(tables_.x)> == + std::extent_v<decltype(tables_.f)>), "fx and x arrays must be identical length"); auto f = [](double x) { return std::exp(-0.5 * x * x); };
diff --git a/absl/random/internal/randen_detect.cc b/absl/random/internal/randen_detect.cc index a613cf0..7d42c6d 100644 --- a/absl/random/internal/randen_detect.cc +++ b/absl/random/internal/randen_detect.cc
@@ -90,6 +90,8 @@ #if defined(ABSL_INTERNAL_USE_ANDROID_GETAUXVAL) #include <dlfcn.h> +#include <cstring> + static uint32_t GetAuxval(uint32_t hwcap_type) { // NOLINTNEXTLINE(runtime/int) typedef unsigned long (*getauxval_func_t)(unsigned long);
diff --git a/absl/random/internal/salted_seed_seq_test.cc b/absl/random/internal/salted_seed_seq_test.cc index dd862f2..3e8dfeb 100644 --- a/absl/random/internal/salted_seed_seq_test.cc +++ b/absl/random/internal/salted_seed_seq_test.cc
@@ -53,12 +53,12 @@ { uint32_t init_array[] = {1, 2, 3, 4, 5}; Sseq seq(std::begin(init_array), std::end(init_array)); - EXPECT_EQ(seq.size(), ABSL_ARRAYSIZE(init_array)); + EXPECT_EQ(seq.size(), std::size(init_array)); std::vector<uint32_t> state_vector; seq.param(std::back_inserter(state_vector)); - EXPECT_EQ(state_vector.size(), ABSL_ARRAYSIZE(init_array)); + EXPECT_EQ(state_vector.size(), std::size(init_array)); for (int i = 0; i < state_vector.size(); i++) { EXPECT_EQ(state_vector[i], i + 1); }
diff --git a/absl/status/internal/status_internal.cc b/absl/status/internal/status_internal.cc index 3f24621..77f3ff7 100644 --- a/absl/status/internal/status_internal.cc +++ b/absl/status/internal/status_internal.cc
@@ -20,6 +20,7 @@ #include <cstdint> #include <cstdio> #include <cstring> +#include <iterator> #include <memory> #include <optional> #include <string>
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 48efd69..15c13f1 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel
@@ -217,6 +217,20 @@ ], ) +cc_binary( + name = "match_benchmark", + testonly = True, + srcs = ["match_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":strings", + "//absl/base:raw_logging_internal", + "@google_benchmark//:benchmark_main", + ], +) + cc_test( name = "escaping_test", size = "small", @@ -330,7 +344,7 @@ ], copts = ABSL_TEST_COPTS, deps = [ - "//absl/strings", + ":strings", "@googletest//:gtest", "@googletest//:gtest_main", ], @@ -454,10 +468,10 @@ copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ + ":str_format", ":string_view", ":stringify_stream", "//absl/base:config", - "//absl/strings:str_format", "@googletest//:gtest", "@googletest//:gtest_main", ],
diff --git a/absl/strings/ascii_test.cc b/absl/strings/ascii_test.cc index fe1083a..6afae49 100644 --- a/absl/strings/ascii_test.cc +++ b/absl/strings/ascii_test.cc
@@ -18,6 +18,7 @@ #include <cctype> #include <clocale> #include <cstring> +#include <iterator> #include <string> #include "gtest/gtest.h" @@ -362,7 +363,7 @@ "", "a\nb", }; - const int NUM_TESTS = ABSL_ARRAYSIZE(inputs); + const int NUM_TESTS = std::size(inputs); for (int i = 0; i < NUM_TESTS; i++) { std::string s(inputs[i]);
diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc index d748ff0..cf65453 100644 --- a/absl/strings/cord_test.cc +++ b/absl/strings/cord_test.cc
@@ -1629,8 +1629,8 @@ for (int i = 0; i < kIters; i++) { absl::Cord c, d; for (int j = 0; j < (i % 7) + 1; j++) { - c.Append(a[GetUniformRandomUpTo(&rng, ABSL_ARRAYSIZE(a))]); - d.Append(a[GetUniformRandomUpTo(&rng, ABSL_ARRAYSIZE(a))]); + c.Append(a[GetUniformRandomUpTo(&rng, std::size(a))]); + d.Append(a[GetUniformRandomUpTo(&rng, std::size(a))]); } std::bernoulli_distribution coin_flip(0.5); MaybeHarden(c);
diff --git a/absl/strings/escaping_test.cc b/absl/strings/escaping_test.cc index a564e83..e4a3868 100644 --- a/absl/strings/escaping_test.cc +++ b/absl/strings/escaping_test.cc
@@ -19,6 +19,7 @@ #include <cstdio> #include <cstring> #include <initializer_list> +#include <iterator> #include <memory> #include <optional> #include <string>
diff --git a/absl/strings/internal/str_format/parser_test.cc b/absl/strings/internal/str_format/parser_test.cc index e2225c6..b62742e 100644 --- a/absl/strings/internal/str_format/parser_test.cc +++ b/absl/strings/internal/str_format/parser_test.cc
@@ -15,15 +15,16 @@ #include "absl/strings/internal/str_format/parser.h" #include <string.h> + #include <algorithm> #include <initializer_list> +#include <iterator> #include <string> #include <utility> #include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/base/config.h" -#include "absl/base/macros.h" #include "absl/strings/internal/str_format/constexpr_parser.h" #include "absl/strings/internal/str_format/extension.h" #include "absl/strings/string_view.h" @@ -54,7 +55,7 @@ {__LINE__, LengthMod::t, "t" }, {__LINE__, LengthMod::q, "q" }, }; - EXPECT_EQ(ABSL_ARRAYSIZE(kExpect), 10); + EXPECT_EQ(std::size(kExpect), 10); for (auto e : kExpect) { SCOPED_TRACE(e.line); EXPECT_EQ(e.name, LengthModToString(e.mod)); @@ -275,7 +276,7 @@ TEST_F(ConsumeUnboundConversionTest, Flags) { static const char kAllFlags[] = "-+ #0"; - static const int kNumFlags = ABSL_ARRAYSIZE(kAllFlags) - 1; + static const int kNumFlags = std::size(kAllFlags) - 1; for (int rev = 0; rev < 2; ++rev) { for (int i = 0; i < 1 << kNumFlags; ++i) { std::string fmt;
diff --git a/absl/strings/match.cc b/absl/strings/match.cc index 72ae6a4..ac7cf0d 100644 --- a/absl/strings/match.cc +++ b/absl/strings/match.cc
@@ -15,8 +15,10 @@ #include "absl/strings/match.h" #include <algorithm> +#include <cstddef> #include <cstdint> +#include "absl/base/attributes.h" #include "absl/base/config.h" #include "absl/base/internal/endian.h" #include "absl/base/optimization.h" @@ -36,25 +38,118 @@ // memcasecmp uses absl::ascii_tolower(). } -bool StrContainsIgnoreCase(absl::string_view haystack, - absl::string_view needle) noexcept { - while (haystack.size() >= needle.size()) { - if (StartsWithIgnoreCase(haystack, needle)) return true; - haystack.remove_prefix(1); +namespace { + +// For larger haystacks (n >= 256), Case-Insensitive Boyer-Moore-Horspool +// provides sub-linear O(N / M) average-case performance, although it still has +// O(N * M) theoretical worst-case scaling. +// Scans the haystack from left to right using a search window of size `m`. +// For each window offset, Horspool inspects the rightmost character of the +// window (`haystack[pos + m - 1]`) first, enabling multi-byte shifts when +// mismatches occur and reducing average search time to O(N / M). +ABSL_ATTRIBUTE_NOINLINE bool StrContainsIgnoreCaseBMH( + absl::string_view haystack, absl::string_view needle) noexcept { + const size_t n = haystack.size(); + const size_t m = needle.size(); + + // Step 1: Initialize the 256-entry shift table. + // Unknown characters default to full window shift of `m` bytes. + size_t shift[256]; + for (size_t i = 0; i < 256; ++i) { + shift[i] = m; + } + + // Populate shift distances for needle[0..m-2]. Dual assignment for + // ascii_tolower and ascii_toupper stores distance from rightmost occurrence + // to end of needle. + for (size_t i = 0; i < m - 1; ++i) { + const unsigned char c = static_cast<unsigned char>(needle[i]); + shift[static_cast<unsigned char>(absl::ascii_tolower(c))] = m - 1 - i; + shift[static_cast<unsigned char>(absl::ascii_toupper(c))] = m - 1 - i; + } + + // Step 2: Search loop across candidate window offsets. + size_t pos = 0; + while (pos <= n - m) { + const unsigned char last_hay = + static_cast<unsigned char>(haystack[pos + m - 1]); + const unsigned char last_needle = static_cast<unsigned char>(needle[m - 1]); + + // Check 1: Inspect right-most character of window first. + if (last_hay == last_needle || + absl::ascii_tolower(last_hay) == absl::ascii_tolower(last_needle)) { + // Check 2: Pre-filter on first character of window. + const unsigned char first_hay = static_cast<unsigned char>(haystack[pos]); + const unsigned char first_needle = static_cast<unsigned char>(needle[0]); + if (first_hay == first_needle || + absl::ascii_tolower(first_hay) == absl::ascii_tolower(first_needle)) { + // Check 3: Compare interior (m - 2) bytes. + if (EqualsIgnoreCase(haystack.substr(pos + 1, m - 2), + needle.substr(1, m - 2))) { + return true; + } + } + } + + // Advance window by shift distance determined by right-most haystack byte. + pos += shift[last_hay]; } return false; } +} // namespace + +bool StrContainsIgnoreCase(absl::string_view haystack, + absl::string_view needle) noexcept { + const size_t n = haystack.size(); + const size_t m = needle.size(); + if (m == 0) return true; + if (n < m) return false; + if (m == 1) return StrContainsIgnoreCase(haystack, needle[0]); + + // For short haystacks (n < 256) or small needles (m == 2), avoid the + // initialization overhead of a 256-entry shift table. Instead, use a fast + // first-and-last character prefilter before inspecting interior bytes. + if (n < 256 || m == 2) { + const char first_needle = + absl::ascii_tolower(static_cast<unsigned char>(needle[0])); + const char last_needle = + absl::ascii_tolower(static_cast<unsigned char>(needle[m - 1])); + + for (size_t pos = 0; pos <= n - m; ++pos) { + const unsigned char first_hay = static_cast<unsigned char>(haystack[pos]); + if (absl::ascii_tolower(first_hay) != first_needle) continue; + + const unsigned char last_hay = + static_cast<unsigned char>(haystack[pos + m - 1]); + if (absl::ascii_tolower(last_hay) != last_needle) continue; + + if (m == 2 || EqualsIgnoreCase(haystack.substr(pos + 1, m - 2), + needle.substr(1, m - 2))) { + return true; + } + } + return false; + } + + return StrContainsIgnoreCaseBMH(haystack, needle); +} + bool StrContainsIgnoreCase(absl::string_view haystack, char needle) noexcept { char upper_needle = absl::ascii_toupper(static_cast<unsigned char>(needle)); char lower_needle = absl::ascii_tolower(static_cast<unsigned char>(needle)); if (upper_needle == lower_needle) { return StrContains(haystack, needle); - } else { - const char both_cstr[3] = {lower_needle, upper_needle, '\0'}; - return haystack.find_first_of(both_cstr) != absl::string_view::npos; } + if (haystack.size() < 64) { + for (char c : haystack) { + if (c == lower_needle || c == upper_needle) return true; + } + return false; + } + const char both_cstr[3] = {lower_needle, upper_needle, '\0'}; + return haystack.find_first_of(both_cstr) != absl::string_view::npos; } bool StartsWithIgnoreCase(absl::string_view text,
diff --git a/absl/strings/match_benchmark.cc b/absl/strings/match_benchmark.cc new file mode 100644 index 0000000..d2c32c0 --- /dev/null +++ b/absl/strings/match_benchmark.cc
@@ -0,0 +1,97 @@ +// Copyright 2026 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include <cstddef> +#include <cstdint> +#include <string> + +#include "absl/base/internal/raw_logging.h" +#include "absl/strings/match.h" +#include "benchmark/benchmark.h" + +namespace { + +void BM_ContainsIgnoreCase_Match(benchmark::State& state) { + const size_t haystack_size = static_cast<size_t>(state.range(0)); + const size_t needle_size = static_cast<size_t>(state.range(1)); + std::string haystack(haystack_size, 'a'); + std::string needle(needle_size, 'b'); + + // Place a case-insensitive match at the very end of the haystack + haystack.replace(haystack_size - needle_size, needle_size, needle_size, 'B'); + + ABSL_RAW_CHECK(absl::StrContainsIgnoreCase(haystack, needle), + "BM_ContainsIgnoreCase_Match must return true"); + + for (auto _ : state) { + benchmark::DoNotOptimize(absl::StrContainsIgnoreCase(haystack, needle)); + } + state.SetBytesProcessed(static_cast<int64_t>(state.iterations()) * + static_cast<int64_t>(haystack_size)); +} +BENCHMARK(BM_ContainsIgnoreCase_Match) + ->Args({4, 1}) + ->Args({64, 1}) + ->Args({64, 8}) + ->Args({1024, 16}) + ->Args({65536, 1}) + ->Args({65536, 64}) + ->Args({65536, 1024}) + ->Args({65536, 16384}); + +void BM_ContainsIgnoreCase_Mismatch(benchmark::State& state) { + const size_t haystack_size = static_cast<size_t>(state.range(0)); + const size_t needle_size = static_cast<size_t>(state.range(1)); + const std::string haystack(haystack_size, 'a'); + const std::string needle(needle_size, 'b'); + + ABSL_RAW_CHECK(!absl::StrContainsIgnoreCase(haystack, needle), + "BM_ContainsIgnoreCase_Mismatch must return false"); + + for (auto _ : state) { + benchmark::DoNotOptimize(absl::StrContainsIgnoreCase(haystack, needle)); + } + state.SetBytesProcessed(static_cast<int64_t>(state.iterations()) * + static_cast<int64_t>(haystack_size)); +} +BENCHMARK(BM_ContainsIgnoreCase_Mismatch) + ->Args({4, 1}) + ->Args({64, 1}) + ->Args({64, 8}) + ->Args({1024, 16}) + ->Args({65536, 1}) + ->Args({65536, 64}) + ->Args({65536, 1024}) + ->Args({65536, 16384}); + +void BM_ContainsIgnoreCase_Adversarial(benchmark::State& state) { + const size_t haystack_size = static_cast<size_t>(state.range(0)); + const std::string haystack(haystack_size, 'a'); + std::string needle(haystack_size / 2, 'a'); + + // Make the needle not match the haystack due to just the last character. + needle.push_back('b'); + + ABSL_RAW_CHECK(!absl::StrContainsIgnoreCase(haystack, needle), + "BM_ContainsIgnoreCase_Adversarial must return false"); + + for (auto _ : state) { + benchmark::DoNotOptimize(absl::StrContainsIgnoreCase(haystack, needle)); + } + state.SetBytesProcessed(static_cast<int64_t>(state.iterations()) * + static_cast<int64_t>(haystack_size)); +} +BENCHMARK(BM_ContainsIgnoreCase_Adversarial)->Range(16 << 10, 128 << 10); + +} // namespace
diff --git a/absl/strings/match_test.cc b/absl/strings/match_test.cc index 6218ce4..76bad73 100644 --- a/absl/strings/match_test.cc +++ b/absl/strings/match_test.cc
@@ -14,9 +14,11 @@ #include "absl/strings/match.h" +#include <cstddef> #include <string> #include "gtest/gtest.h" +#include "absl/strings/ascii.h" #include "absl/strings/string_view.h" namespace { @@ -171,6 +173,261 @@ EXPECT_FALSE(absl::StrContainsIgnoreCase("", '0')); } +TEST(MatchTest, ContainsIgnoreCaseLinearScaling) { + // Adversarial case where naive shift-by-one substring scan exhibits + // quadratic O(N * M) time: haystack = 'a' * N, needle = 'a' * (M - 1) + 'b'. + // + // Boyer-Moore-Horspool inspects the last byte first, immediately detecting + // the mismatch ('a' != 'b') at each window offset and shifting by 1, + // completing in linear O(N) time. + const std::string haystack(1 << 17, 'a'); // 128 KiB + std::string needle(1 << 16, 'a'); // 64 KiB + needle.push_back('b'); + + EXPECT_FALSE(absl::StrContainsIgnoreCase(haystack, needle)); + + std::string matching_needle(1 << 16, 'A'); + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, matching_needle)); +} + +std::string MakeBMHNeedle(size_t m) { + std::string needle(m, 'y'); + for (size_t i = 0; i < m; i += 2) { + needle[i] = static_cast<char>('A' + (i % 26)); + needle[i + 1] = static_cast<char>('a' + ((i + 1) % 26)); + } + return needle; +} + +TEST(MatchTest, ContainsIgnoreCaseBMHMatchAtStart) { + // Test BMH search (N >= 256, M >= 256) when match occurs at pos == 0. + constexpr size_t n = 1000; + constexpr size_t m = 300; + std::string needle = MakeBMHNeedle(m); + std::string haystack(n, 'x'); + haystack.replace(0, m, needle); + + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, needle)); +} + +TEST(MatchTest, ContainsIgnoreCaseBMHMatchInMiddle) { + // Test BMH search (N >= 256, M >= 256) when match occurs in the middle of + // haystack. + constexpr size_t n = 1000; + constexpr size_t m = 300; + std::string needle = MakeBMHNeedle(m); + std::string haystack(n, 'x'); + haystack.replace(200, m, needle); + + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, needle)); +} + +TEST(MatchTest, ContainsIgnoreCaseBMHMatchAtEnd) { + // Test BMH search (N >= 256, M >= 256) when match occurs at the very end (pos + // == n - m). Verifies that while (pos <= n - m) boundary condition includes + // the final window. + constexpr size_t n = 1000; + constexpr size_t m = 300; + std::string needle = MakeBMHNeedle(m); + std::string haystack(n, 'x'); + haystack.replace(n - m, m, needle); + + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, needle)); +} + +TEST(MatchTest, ContainsIgnoreCaseBMHMismatchAtEnd) { + // Test BMH search (N >= 256, M >= 256) when needle is placed at pos == n - m + // but fails on the last character. + constexpr size_t n = 1000; + constexpr size_t m = 300; + std::string needle = MakeBMHNeedle(m); + std::string haystack(n, 'x'); + haystack.replace(n - m, m, needle); + haystack.back() = 'Z'; + + EXPECT_FALSE(absl::StrContainsIgnoreCase(haystack, needle)); +} + +TEST(MatchTest, ContainsIgnoreCaseBMHInteriorMismatch) { + // Test BMH search (N >= 256, M >= 256) when the first and last characters + // of a window match, but interior bytes mismatch. + // This exercises the false branch of EqualsIgnoreCase(...) inside BMH, + // falling through line 91 to advance the window. + constexpr size_t n = 1000; + constexpr size_t m = 300; + std::string needle = MakeBMHNeedle(m); + + // 1. First and last chars match at pos == 100, but interior byte 10 + // mismatches. + std::string haystack(n, 'x'); + haystack.replace(100, m, needle); + haystack[100 + 10] = (needle[10] == 'Q') ? 'W' : 'Q'; + + EXPECT_FALSE(absl::StrContainsIgnoreCase(haystack, needle)); + + // 2. Add a valid match at the end to verify BMH continues scanning after + // falling through an interior mismatch. + haystack.replace(n - m, m, needle); + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, needle)); +} + +TEST(MatchTest, ContainsIgnoreCaseBMHMixedCaseAndShifts) { + // Test large needle (M >= 256) with mixed casing and partial matches + // triggering multi-byte skip shifts during BMH scanning. + std::string needle; + needle.reserve(300); + for (size_t i = 0; i < 300; ++i) { + needle.push_back(static_cast<char>('a' + (i % 10))); + } + + std::string haystack; + haystack.reserve(2000); + for (int i = 0; i < 5; ++i) { + haystack.append(needle.substr(0, 250)); + haystack.append("XYZ"); + } + + std::string needle_upper = needle; + for (char& c : needle_upper) { + c = static_cast<char>(absl::ascii_toupper(static_cast<unsigned char>(c))); + } + + EXPECT_FALSE(absl::StrContainsIgnoreCase(haystack, needle_upper)); + + haystack.append(needle_upper); + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, needle)); +} + +TEST(MatchTest, ContainsIgnoreCaseHaystackThresholdBoundary) { + // Test haystack threshold boundary N = 255 (prefilter branch) vs N = 256 (BMH + // branch). + std::string needle = "AbC"; + + // N = 255 (prefilter branch) + std::string h255(255, '.'); + h255.replace(100, 3, "aBc"); + EXPECT_TRUE(absl::StrContainsIgnoreCase(h255, needle)); + EXPECT_TRUE(absl::StrContainsIgnoreCase(h255, "abc")); + EXPECT_FALSE(absl::StrContainsIgnoreCase(std::string(255, '.'), needle)); + + // N = 256 (BMH branch) + std::string h256(256, '.'); + h256.replace(100, 3, "aBc"); + EXPECT_TRUE(absl::StrContainsIgnoreCase(h256, needle)); + EXPECT_TRUE(absl::StrContainsIgnoreCase(h256, "abc")); + EXPECT_FALSE(absl::StrContainsIgnoreCase(std::string(256, '.'), needle)); +} + +TEST(MatchTest, ContainsIgnoreCaseSmallNeedleFastPath) { + // Test small needle (M = 2) fast path, which uses prefilter regardless of + // haystack size (N >= 256). + std::string needle = "xY"; + std::string h1000(1000, 'a'); + + // Match at start + h1000.replace(0, 2, "Xy"); + EXPECT_TRUE(absl::StrContainsIgnoreCase(h1000, needle)); + + // Match at end (pos == 998) + h1000 = std::string(1000, 'a'); + h1000.replace(998, 2, "Xy"); + EXPECT_TRUE(absl::StrContainsIgnoreCase(h1000, needle)); + + // Mismatch + h1000 = std::string(1000, 'a'); + EXPECT_FALSE(absl::StrContainsIgnoreCase(h1000, needle)); +} + +TEST(MatchTest, ContainsIgnoreCaseNeedleThresholdBoundary) { + // Test needle length boundaries M = 255, M = 256, and M = 257 in N = 300 + // haystack. + std::string h300(300, 'a'); + std::string n255(255, 'A'); + std::string n256(256, 'A'); + std::string n257(257, 'A'); + + EXPECT_TRUE(absl::StrContainsIgnoreCase(h300, n255)); + EXPECT_TRUE(absl::StrContainsIgnoreCase(h300, n256)); + EXPECT_TRUE(absl::StrContainsIgnoreCase(h300, n257)); + + n255.back() = 'B'; + n256.back() = 'B'; + n257.back() = 'B'; + + EXPECT_FALSE(absl::StrContainsIgnoreCase(h300, n255)); + EXPECT_FALSE(absl::StrContainsIgnoreCase(h300, n256)); + EXPECT_FALSE(absl::StrContainsIgnoreCase(h300, n257)); +} + +TEST(MatchTest, ContainsIgnoreCaseBMHNonAsciiBytes) { + // Test BMH algorithm handling of high-bit non-ASCII bytes (values > 127) in + // needle and haystack. + std::string needle(300, '\0'); + for (size_t i = 0; i < 300; ++i) { + needle[i] = static_cast<char>(128 + (i % 128)); + } + std::string haystack(1000, '\x7F'); + haystack.replace(500, 300, needle); + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, needle)); + + haystack[799] = '\x00'; + EXPECT_FALSE(absl::StrContainsIgnoreCase(haystack, needle)); +} + +TEST(MatchTest, ContainsIgnoreCaseBMHExactLengthMatch) { + // Test BMH search when haystack size equals needle size (N == M == 300). + std::string needle(300, 'X'); + std::string haystack(300, 'x'); + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, needle)); + + haystack.back() = 'y'; + EXPECT_FALSE(absl::StrContainsIgnoreCase(haystack, needle)); +} + +TEST(MatchTest, ContainsIgnoreCaseBMHAllIdenticalCharNeedle) { + // Test BMH search with needle consisting of all identical characters (M >= + // 256). + std::string needle(300, 'K'); + std::string haystack(1000, 'k'); + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, needle)); + + std::string short_haystack(299, 'k'); + EXPECT_FALSE(absl::StrContainsIgnoreCase(short_haystack, needle)); +} + +TEST(MatchTest, ContainsCharIgnoreCaseLargeHaystack) { + // Test StrContainsIgnoreCase(haystack, char) for N >= 64, exercising the + // find_first_of fallback branch. + constexpr size_t sizes[] = {64, 100, 1000}; + for (size_t n : sizes) { + std::string haystack(n, '.'); + + // 1. Alphabetic character (exercises find_first_of fallback branch) + haystack[0] = 'z'; + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, 'Z')); + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, 'z')); + + haystack = std::string(n, '.'); + haystack[n / 2] = 'Z'; + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, 'z')); + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, 'Z')); + + haystack = std::string(n, '.'); + haystack[n - 1] = 'z'; + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, 'Z')); + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, 'z')); + + haystack = std::string(n, '.'); + EXPECT_FALSE(absl::StrContainsIgnoreCase(haystack, 'z')); + EXPECT_FALSE(absl::StrContainsIgnoreCase(haystack, 'Z')); + + // 2. Non-alphabetic character (upper_needle == lower_needle) + haystack[n / 2] = '9'; + EXPECT_TRUE(absl::StrContainsIgnoreCase(haystack, '9')); + EXPECT_FALSE(absl::StrContainsIgnoreCase(haystack, '8')); + } +} + TEST(MatchTest, FindLongestCommonPrefix) { EXPECT_EQ(absl::FindLongestCommonPrefix("", ""), ""); EXPECT_EQ(absl::FindLongestCommonPrefix("", "abc"), "");
diff --git a/absl/strings/str_format_test.cc b/absl/strings/str_format_test.cc index a4c877a..019284b 100644 --- a/absl/strings/str_format_test.cc +++ b/absl/strings/str_format_test.cc
@@ -18,6 +18,7 @@ #include <cstdarg> #include <cstdint> #include <cstdio> +#include <iterator> #include <ostream> #include <sstream> #include <string> @@ -300,7 +301,7 @@ }; std::string buf(4096, '\0'); - for (auto i = 0; i < ABSL_ARRAYSIZE(formats); ++i) { + for (auto i = 0; i < std::size(formats); ++i) { const auto parsed = ParsedFormat<'v', 'u', 'c', 'v', 'f', 'v'>::NewAllowIgnored(formats[i]); std::ostringstream oss;
diff --git a/absl/strings/str_join_test.cc b/absl/strings/str_join_test.cc index 1c0ffe1..6657248 100644 --- a/absl/strings/str_join_test.cc +++ b/absl/strings/str_join_test.cc
@@ -94,7 +94,7 @@ { // Array of ints const int a[] = {1, 2, 3, -4}; - EXPECT_EQ("1-2-3--4", absl::StrJoin(a, a + ABSL_ARRAYSIZE(a), "-")); + EXPECT_EQ("1-2-3--4", absl::StrJoin(a, a + std::size(a), "-")); } {
diff --git a/absl/strings/str_replace.h b/absl/strings/str_replace.h index 91b920b..4106c24 100644 --- a/absl/strings/str_replace.h +++ b/absl/strings/str_replace.h
@@ -160,7 +160,7 @@ std::vector<ViableSubstitution> FindSubstitutions( absl::string_view s, const StrToStrMapping& replacements) { std::vector<ViableSubstitution> subs; - subs.reserve(replacements.size()); + subs.reserve(std::size(replacements)); for (const auto& rep : replacements) { using std::get;
diff --git a/absl/strings/str_replace_test.cc b/absl/strings/str_replace_test.cc index 04b23af..8922856 100644 --- a/absl/strings/str_replace_test.cc +++ b/absl/strings/str_replace_test.cc
@@ -156,6 +156,14 @@ EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s); } +TEST(StrReplaceAll, ManyReplacementsInArray) { + std::pair<std::string, std::string> replacements[] = { + {"$who", "Bob"}, {"$count", "5"}, {"#Noun", "Apples"}}; + std::string s = absl::StrReplaceAll("$who bought $count #Noun. Thanks $who!", + replacements); + EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s); +} + TEST(StrReplaceAll, ReplacementsInPlace) { std::string s = std::string("$who bought $count #Noun. Thanks $who!"); int count; @@ -178,6 +186,16 @@ EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s); } +TEST(StrReplaceAll, ReplacementsInPlaceInArray) { + std::string s = std::string("$who bought $count #Noun. Thanks $who!"); + std::pair<std::string, std::string> replacements[] = { + {"$who", "Bob"}, {"$count", "5"}, {"#Noun", "Apples"}}; + int count; + count = absl::StrReplaceAll(replacements, &s); + EXPECT_EQ(count, 4); + EXPECT_EQ("Bob bought 5 Apples. Thanks Bob!", s); +} + struct Cont { Cont() = default; explicit Cont(absl::string_view src) : data(src) {}
diff --git a/absl/strings/str_split_test.cc b/absl/strings/str_split_test.cc index aa22ca4..57aa87e 100644 --- a/absl/strings/str_split_test.cc +++ b/absl/strings/str_split_test.cc
@@ -19,6 +19,7 @@ #include <cstdint> #include <deque> #include <initializer_list> +#include <iterator> #include <list> #include <map> #include <memory> @@ -666,7 +667,7 @@ // destroyed, if the splitter keeps a reference to the string's contents, // it'll reference freed memory instead of just dead on-stack memory. const char input[] = "a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u"; - EXPECT_LT(sizeof(std::string), ABSL_ARRAYSIZE(input)) + EXPECT_LT(sizeof(std::string), std::size(input)) << "Input should be larger than fits on the stack."; // This happens more often in C++11 as part of a range-based for loop.
diff --git a/absl/strings/substitute.h b/absl/strings/substitute.h index 626d52d..7461c2f 100644 --- a/absl/strings/substitute.h +++ b/absl/strings/substitute.h
@@ -73,6 +73,7 @@ #define ABSL_STRINGS_SUBSTITUTE_H_ #include <cstring> +#include <iterator> #include <string> #include <type_traits> #include <vector> @@ -283,7 +284,7 @@ const substitute_internal::Arg& a0) { const absl::string_view args[] = {a0.piece()}; substitute_internal::SubstituteAndAppendArray(output, format, args, - ABSL_ARRAYSIZE(args)); + std::size(args)); } inline void SubstituteAndAppend(std::string* absl_nonnull output, @@ -292,7 +293,7 @@ const substitute_internal::Arg& a1) { const absl::string_view args[] = {a0.piece(), a1.piece()}; substitute_internal::SubstituteAndAppendArray(output, format, args, - ABSL_ARRAYSIZE(args)); + std::size(args)); } inline void SubstituteAndAppend(std::string* absl_nonnull output, @@ -302,7 +303,7 @@ const substitute_internal::Arg& a2) { const absl::string_view args[] = {a0.piece(), a1.piece(), a2.piece()}; substitute_internal::SubstituteAndAppendArray(output, format, args, - ABSL_ARRAYSIZE(args)); + std::size(args)); } inline void SubstituteAndAppend(std::string* absl_nonnull output, @@ -314,7 +315,7 @@ const absl::string_view args[] = {a0.piece(), a1.piece(), a2.piece(), a3.piece()}; substitute_internal::SubstituteAndAppendArray(output, format, args, - ABSL_ARRAYSIZE(args)); + std::size(args)); } inline void SubstituteAndAppend(std::string* absl_nonnull output, @@ -327,7 +328,7 @@ const absl::string_view args[] = {a0.piece(), a1.piece(), a2.piece(), a3.piece(), a4.piece()}; substitute_internal::SubstituteAndAppendArray(output, format, args, - ABSL_ARRAYSIZE(args)); + std::size(args)); } inline void SubstituteAndAppend( @@ -338,7 +339,7 @@ const absl::string_view args[] = {a0.piece(), a1.piece(), a2.piece(), a3.piece(), a4.piece(), a5.piece()}; substitute_internal::SubstituteAndAppendArray(output, format, args, - ABSL_ARRAYSIZE(args)); + std::size(args)); } inline void SubstituteAndAppend( @@ -351,7 +352,7 @@ a3.piece(), a4.piece(), a5.piece(), a6.piece()}; substitute_internal::SubstituteAndAppendArray(output, format, args, - ABSL_ARRAYSIZE(args)); + std::size(args)); } inline void SubstituteAndAppend( @@ -364,7 +365,7 @@ a3.piece(), a4.piece(), a5.piece(), a6.piece(), a7.piece()}; substitute_internal::SubstituteAndAppendArray(output, format, args, - ABSL_ARRAYSIZE(args)); + std::size(args)); } inline void SubstituteAndAppend( @@ -378,7 +379,7 @@ a3.piece(), a4.piece(), a5.piece(), a6.piece(), a7.piece(), a8.piece()}; substitute_internal::SubstituteAndAppendArray(output, format, args, - ABSL_ARRAYSIZE(args)); + std::size(args)); } inline void SubstituteAndAppend( @@ -392,7 +393,7 @@ a0.piece(), a1.piece(), a2.piece(), a3.piece(), a4.piece(), a5.piece(), a6.piece(), a7.piece(), a8.piece(), a9.piece()}; substitute_internal::SubstituteAndAppendArray(output, format, args, - ABSL_ARRAYSIZE(args)); + std::size(args)); } #if defined(ABSL_BAD_CALL_IF)
diff --git a/absl/synchronization/internal/graphcycles.cc b/absl/synchronization/internal/graphcycles.cc index f58fb0a..3f8bb3a 100644 --- a/absl/synchronization/internal/graphcycles.cc +++ b/absl/synchronization/internal/graphcycles.cc
@@ -28,6 +28,9 @@ // (2) When a new edge (x->y) is inserted, do nothing if rank[x] < rank[y]. // (3) Otherwise: adjust ranks in the neighborhood of x and y. +#include <cstddef> +#include <iterator> + #include "absl/base/attributes.h" // This file is a no-op if the required LowLevelAlloc support is missing. #include "absl/base/internal/low_level_alloc.h" @@ -692,7 +695,8 @@ if (n == nullptr || n->priority >= priority) { return; } - n->nstack = (*get_stack_trace)(n->stack, ABSL_ARRAYSIZE(n->stack)); + n->nstack = + (*get_stack_trace)(n->stack, static_cast<int>(std::size(n->stack))); n->priority = priority; }
diff --git a/absl/synchronization/internal/graphcycles_test.cc b/absl/synchronization/internal/graphcycles_test.cc index b7988c4..4f1a485 100644 --- a/absl/synchronization/internal/graphcycles_test.cc +++ b/absl/synchronization/internal/graphcycles_test.cc
@@ -16,6 +16,7 @@ #include <climits> #include <cstdint> +#include <iterator> #include <map> #include <random> #include <unordered_set> @@ -284,7 +285,7 @@ int to = RandomNode(&rng, &nodes); GraphId path[2*kMaxNodes]; int path_len = graph_cycles.FindPath(id[nodes[from]], id[nodes[to]], - ABSL_ARRAYSIZE(path), path); + std::size(path), path); std::unordered_set<int> seen; bool reachable = IsReachable(&edges, nodes[from], nodes[to], &seen); bool gc_reachable = @@ -388,10 +389,10 @@ std::string Path(int x, int y) { GraphId path[5]; - int np = g_.FindPath(Get(id_, x), Get(id_, y), ABSL_ARRAYSIZE(path), path); + int np = g_.FindPath(Get(id_, x), Get(id_, y), std::size(path), path); std::string result; for (int i = 0; i < np; i++) { - if (i >= ABSL_ARRAYSIZE(path)) { + if (i >= int{std::size(path)}) { result += " ..."; break; }
diff --git a/absl/synchronization/internal/per_thread_sem.h b/absl/synchronization/internal/per_thread_sem.h index 704f3da..7d1099e 100644 --- a/absl/synchronization/internal/per_thread_sem.h +++ b/absl/synchronization/internal/per_thread_sem.h
@@ -30,6 +30,7 @@ #include "absl/base/internal/thread_identity.h" #include "absl/synchronization/internal/create_thread_identity.h" #include "absl/synchronization/internal/kernel_timeout.h" +#include "absl/time/time.h" namespace gloop_do_not_use { struct SynchronizationBenchmarkPeer; @@ -78,6 +79,10 @@ // !t.has_timeout() => Wait(t) will return true. static inline bool Wait(KernelTimeout t); + // Waits until either our count > 0 or the absolute time t has passed. + // If count > 0, decrements count and returns true. Otherwise returns false. + static inline bool WaitAbsolute(absl::Time t); + // Permitted callers. friend class PerThreadSemTest; friend class absl::Mutex; @@ -121,4 +126,8 @@ return ABSL_INTERNAL_C_SYMBOL(AbslInternalPerThreadSemWait)(t); } +bool absl::synchronization_internal::PerThreadSem::WaitAbsolute(absl::Time t) { + return Wait(KernelTimeout(t)); +} + #endif // ABSL_SYNCHRONIZATION_INTERNAL_PER_THREAD_SEM_H_
diff --git a/absl/synchronization/internal/per_thread_sem_test.cc b/absl/synchronization/internal/per_thread_sem_test.cc index e3cf41d..46f903a 100644 --- a/absl/synchronization/internal/per_thread_sem_test.cc +++ b/absl/synchronization/internal/per_thread_sem_test.cc
@@ -132,9 +132,9 @@ return PerThreadSem::Wait(t); } - // convenience overload + // absl::Time overload, absolute expiry static bool Wait(absl::Time t) { - return Wait(KernelTimeout(t)); + return PerThreadSem::WaitAbsolute(t); } static void Tick(base_internal::ThreadIdentity *identity) {
diff --git a/absl/synchronization/mutex.cc b/absl/synchronization/mutex.cc index 2016435..63414bb 100644 --- a/absl/synchronization/mutex.cc +++ b/absl/synchronization/mutex.cc
@@ -14,6 +14,7 @@ #include "absl/synchronization/mutex.h" + #ifdef _WIN32 #include <windows.h> #ifdef ERROR
diff --git a/absl/time/BUILD.bazel b/absl/time/BUILD.bazel index cca77da..073c229 100644 --- a/absl/time/BUILD.bazel +++ b/absl/time/BUILD.bazel
@@ -148,6 +148,7 @@ "//absl/hash:hash_testing", "//absl/numeric:int128", "//absl/random", + "//absl/strings", "//absl/strings:str_format", "//absl/time/internal/cctz:time_zone", "@googletest//:gtest",
diff --git a/absl/time/civil_time.h b/absl/time/civil_time.h index d1d0d95..865a99b 100644 --- a/absl/time/civil_time.h +++ b/absl/time/civil_time.h
@@ -462,32 +462,6 @@ std::string FormatCivilTime(CivilMonth c); std::string FormatCivilTime(CivilYear c); -// Support for StrFormat(), StrCat(), etc -template <typename Sink> -void AbslStringify(Sink& sink, CivilSecond c) { - sink.Append(FormatCivilTime(c)); -} -template <typename Sink> -void AbslStringify(Sink& sink, CivilMinute c) { - sink.Append(FormatCivilTime(c)); -} -template <typename Sink> -void AbslStringify(Sink& sink, CivilHour c) { - sink.Append(FormatCivilTime(c)); -} -template <typename Sink> -void AbslStringify(Sink& sink, CivilDay c) { - sink.Append(FormatCivilTime(c)); -} -template <typename Sink> -void AbslStringify(Sink& sink, CivilMonth c) { - sink.Append(FormatCivilTime(c)); -} -template <typename Sink> -void AbslStringify(Sink& sink, CivilYear c) { - sink.Append(FormatCivilTime(c)); -} - // absl::ParseCivilTime() // // Parses a civil-time value from the specified `absl::string_view` into the @@ -551,6 +525,32 @@ namespace time_internal { // For functions found via ADL on civil-time tags. +// Support for StrFormat(), StrCat(), etc +template <typename Sink> +void AbslStringify(Sink& sink, CivilSecond c) { + sink.Append(FormatCivilTime(c)); +} +template <typename Sink> +void AbslStringify(Sink& sink, CivilMinute c) { + sink.Append(FormatCivilTime(c)); +} +template <typename Sink> +void AbslStringify(Sink& sink, CivilHour c) { + sink.Append(FormatCivilTime(c)); +} +template <typename Sink> +void AbslStringify(Sink& sink, CivilDay c) { + sink.Append(FormatCivilTime(c)); +} +template <typename Sink> +void AbslStringify(Sink& sink, CivilMonth c) { + sink.Append(FormatCivilTime(c)); +} +template <typename Sink> +void AbslStringify(Sink& sink, CivilYear c) { + sink.Append(FormatCivilTime(c)); +} + // Streaming Operators // // Each civil-time type may be sent to an output stream using operator<<().
diff --git a/absl/time/civil_time_test.cc b/absl/time/civil_time_test.cc index 3ad8e14..f6d1682 100644 --- a/absl/time/civil_time_test.cc +++ b/absl/time/civil_time_test.cc
@@ -14,14 +14,17 @@ #include "absl/time/civil_time.h" +#include <cstddef> #include <iomanip> +#include <iterator> #include <limits> #include <sstream> #include <type_traits> #include "gtest/gtest.h" -#include "absl/base/macros.h" #include "absl/hash/hash_testing.h" +#include "absl/strings/has_absl_stringify.h" +#include "absl/strings/str_cat.h" #include "absl/strings/str_format.h" namespace { @@ -870,19 +873,34 @@ } TEST(CivilTime, AbslStringify) { + static_assert(absl::HasAbslStringify<absl::CivilSecond>::value); + static_assert(absl::HasAbslStringify<absl::CivilMinute>::value); + static_assert(absl::HasAbslStringify<absl::CivilHour>::value); + static_assert(absl::HasAbslStringify<absl::CivilDay>::value); + static_assert(absl::HasAbslStringify<absl::CivilMonth>::value); + static_assert(absl::HasAbslStringify<absl::CivilYear>::value); + + EXPECT_EQ("2015-01-02T03:04:05", + absl::StrCat(absl::CivilSecond(2015, 1, 2, 3, 4, 5))); EXPECT_EQ("2015-01-02T03:04:05", absl::StrFormat("%v", absl::CivilSecond(2015, 1, 2, 3, 4, 5))); EXPECT_EQ("2015-01-02T03:04", + absl::StrCat(absl::CivilMinute(2015, 1, 2, 3, 4))); + EXPECT_EQ("2015-01-02T03:04", absl::StrFormat("%v", absl::CivilMinute(2015, 1, 2, 3, 4))); + EXPECT_EQ("2015-01-02T03", absl::StrCat(absl::CivilHour(2015, 1, 2, 3))); EXPECT_EQ("2015-01-02T03", absl::StrFormat("%v", absl::CivilHour(2015, 1, 2, 3))); + EXPECT_EQ("2015-01-02", absl::StrCat(absl::CivilDay(2015, 1, 2))); EXPECT_EQ("2015-01-02", absl::StrFormat("%v", absl::CivilDay(2015, 1, 2))); + EXPECT_EQ("2015-01", absl::StrCat(absl::CivilMonth(2015, 1))); EXPECT_EQ("2015-01", absl::StrFormat("%v", absl::CivilMonth(2015, 1))); + EXPECT_EQ("2015", absl::StrCat(absl::CivilYear(2015))); EXPECT_EQ("2015", absl::StrFormat("%v", absl::CivilYear(2015))); } @@ -1188,7 +1206,7 @@ {2009, 365, {3, 1}}, {2100, 365, {3, 1}}, }; - for (int i = 0; i < ABSL_ARRAYSIZE(kLeapYearTable); ++i) { + for (size_t i = 0; i < std::size(kLeapYearTable); ++i) { const int y = kLeapYearTable[i].year; const int m = kLeapYearTable[i].leap_day.month; const int d = kLeapYearTable[i].leap_day.day;
diff --git a/absl/time/duration_benchmark.cc b/absl/time/duration_benchmark.cc index e2dd4d2..5a33c65 100644 --- a/absl/time/duration_benchmark.cc +++ b/absl/time/duration_benchmark.cc
@@ -15,6 +15,7 @@ #include <cstddef> #include <cstdint> #include <ctime> +#include <iterator> #include <string> #include "absl/base/attributes.h" @@ -571,7 +572,7 @@ "-2h3m4.005006007s", // 3 "2562047788015215h30m7.99999999975s", // 4 }; -const int kNumDurations = sizeof(kDurations) / sizeof(kDurations[0]); +const int kNumDurations = std::size(kDurations); void BM_Duration_FormatDuration(benchmark::State& state) { const std::string s = kDurations[state.range(0)];
diff --git a/absl/time/format_benchmark.cc b/absl/time/format_benchmark.cc index 19e481d..45109fa 100644 --- a/absl/time/format_benchmark.cc +++ b/absl/time/format_benchmark.cc
@@ -12,6 +12,7 @@ // limitations under the License. #include <cstddef> +#include <iterator> #include <string> #include "absl/time/internal/test_util.h" @@ -29,7 +30,7 @@ "%Y-%m-%d%ET%H:%M:%S", // 4 "%Y-%m-%d", // 5 }; -const int kNumFormats = sizeof(kFormats) / sizeof(kFormats[0]); +const int kNumFormats = std::size(kFormats); } // namespace void BM_Format_FormatTime(benchmark::State& state) {
diff --git a/absl/time/internal/cctz/BUILD.bazel b/absl/time/internal/cctz/BUILD.bazel index 3b47877..edec282 100644 --- a/absl/time/internal/cctz/BUILD.bazel +++ b/absl/time/internal/cctz/BUILD.bazel
@@ -140,7 +140,10 @@ name = "time_zone_lookup_test", size = "small", timeout = "moderate", - srcs = ["src/time_zone_lookup_test.cc"], + srcs = [ + "src/time_zone_lookup_test.cc", + "src/tzfile.h", + ], copts = ABSL_TEST_COPTS, data = [":zoneinfo"], linkopts = ABSL_DEFAULT_LINKOPTS, @@ -177,6 +180,24 @@ ], ) +cc_test( + name = "time_zone_posix_test", + size = "small", + srcs = [ + "src/time_zone_posix.h", + "src/time_zone_posix_test.cc", + ], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":civil_time", + ":time_zone", + "//absl/base:config", + "@googletest//:gtest", + "@googletest//:gtest_main", + ], +) + ### benchmarks cc_test(
diff --git a/absl/time/internal/cctz/src/cctz_benchmark.cc b/absl/time/internal/cctz/src/cctz_benchmark.cc index ce27818..17ff576 100644 --- a/absl/time/internal/cctz/src/cctz_benchmark.cc +++ b/absl/time/internal/cctz/src/cctz_benchmark.cc
@@ -28,6 +28,7 @@ namespace { +// SKIP_ABSL_INLINE_NAMESPACE_CHECK namespace cctz = absl::time_internal::cctz; void BM_Difference_Days(benchmark::State& state) {
diff --git a/absl/time/internal/cctz/src/time_zone_fixed.cc b/absl/time/internal/cctz/src/time_zone_fixed.cc index ed7f9cb..b33410d 100644 --- a/absl/time/internal/cctz/src/time_zone_fixed.cc +++ b/absl/time/internal/cctz/src/time_zone_fixed.cc
@@ -40,12 +40,19 @@ return p; } +// Returns the value of the decimal digit ch, or -1 if ch is not a digit. +// Note that std::strchr() also matches kDigits' terminating '\0', which +// would otherwise be taken for a tenth digit. +int ParseDigit(char ch) { + const char* const dp = std::strchr(kDigits, ch); + return (dp == nullptr || *dp == '\0') ? -1 : static_cast<int>(dp - kDigits); +} + int Parse02d(const char* p) { - if (const char* ap = std::strchr(kDigits, *p)) { - int v = static_cast<int>(ap - kDigits); - if (const char* bp = std::strchr(kDigits, *++p)) { - return (v * 10) + static_cast<int>(bp - kDigits); - } + const int hi = ParseDigit(p[0]); + if (hi >= 0) { + const int lo = ParseDigit(p[1]); + if (lo >= 0) return (hi * 10) + lo; } return -1; }
diff --git a/absl/time/internal/cctz/src/time_zone_format.cc b/absl/time/internal/cctz/src/time_zone_format.cc index 91b4621..f97de2f 100644 --- a/absl/time/internal/cctz/src/time_zone_format.cc +++ b/absl/time/internal/cctz/src/time_zone_format.cc
@@ -58,6 +58,16 @@ namespace { +// The ctype functions have undefined behavior for negative char values, +// so these helpers ensure the argument is always in the unsigned-char domain. +bool isdigit(char ch) { + return std::isdigit(static_cast<unsigned char>(ch)) != 0; +} + +bool isspace(char ch) { + return std::isspace(static_cast<unsigned char>(ch)) != 0; +} + #if !HAS_STRPTIME // Build a strptime() using C++11's std::get_time(). char* strptime(const char* s, const char* fmt, std::tm* tm) { @@ -553,7 +563,7 @@ bp = Format64(ep, 4, al.cs.year()); result.append(bp, ep); pending = cur += 2; - } else if (std::isdigit(*cur)) { + } else if (isdigit(*cur)) { // Possibly found %E#S or %E#f. int n = 0; if (const char* np = ParseInt(cur, 0, 0, 1024, &n)) { @@ -620,7 +630,7 @@ const char* ParseZone(const char* dp, std::string* zone) { zone->clear(); if (dp != nullptr) { - while (*dp != '\0' && !std::isspace(*dp)) zone->push_back(*dp++); + while (*dp != '\0' && !isspace(*dp)) zone->push_back(*dp++); if (zone->empty()) dp = nullptr; } return dp; @@ -706,7 +716,7 @@ const char* const edata = data + input.size(); // Skips leading whitespace. - while (std::isspace(*data)) ++data; + while (isspace(*data)) ++data; const year_t kyearmax = std::numeric_limits<year_t>::max(); const year_t kyearmin = std::numeric_limits<year_t>::min(); @@ -744,9 +754,9 @@ // Steps through format, one specifier at a time. while (data != nullptr && fmt != efmt) { - if (std::isspace(*fmt)) { - while (std::isspace(*data)) ++data; - while (std::isspace(*++fmt)) continue; + if (isspace(*fmt)) { + while (isspace(*data)) ++data; + while (isspace(*++fmt)) continue; continue; } @@ -898,7 +908,7 @@ continue; } if (fmt[0] == '*' && fmt[1] == 'f') { - if (data != nullptr && std::isdigit(*data)) { + if (data != nullptr && isdigit(*data)) { data = ParseSubSeconds(data, &subseconds); } fmt += 2; @@ -917,7 +927,7 @@ fmt += 2; continue; } - if (std::isdigit(*fmt)) { + if (isdigit(*fmt)) { int n = 0; // value ignored if (const char* np = ParseInt(fmt, 0, 0, 1024, &n)) { if (*np == 'S') { @@ -929,7 +939,7 @@ continue; } if (*np == 'f') { - if (data != nullptr && std::isdigit(*data)) { + if (data != nullptr && isdigit(*data)) { data = ParseSubSeconds(data, &subseconds); } fmt = ++np; @@ -977,7 +987,7 @@ } // Skip any remaining whitespace. - while (std::isspace(*data)) ++data; + while (isspace(*data)) ++data; // parse() must consume the entire input string. if (data != edata) {
diff --git a/absl/time/internal/cctz/src/time_zone_format_test.cc b/absl/time/internal/cctz/src/time_zone_format_test.cc index f047d93..8793a80 100644 --- a/absl/time/internal/cctz/src/time_zone_format_test.cc +++ b/absl/time/internal/cctz/src/time_zone_format_test.cc
@@ -1002,6 +1002,27 @@ EXPECT_FALSE(parse("%Ez", "-00:-0", tz, &tp)); } +TEST(Parse, NonAsciiInput) { + const time_zone tz = utc_time_zone(); + auto tp = chrono::system_clock::from_time_t(0); + + // High-bit-set bytes reach the ctype functions during parsing. 0xA0 is not + // ASCII whitespace, so the leading-whitespace skip must not consume it and + // the parse must fail rather than pass a negative char to std::isspace(). + EXPECT_FALSE(parse("%Y-%m-%d", + "\xA0" + "2016-01-02", + tz, &tp)); + EXPECT_FALSE(parse("%Y", + "\xA0" + "2016", + tz, &tp)); + + // A leading ASCII space is still skipped as before. + EXPECT_TRUE(parse("%Y-%m-%d", " 2016-01-02", tz, &tp)); + EXPECT_EQ(2016, convert(tp, utc_time_zone()).year()); +} + TEST(Parse, PosixConversions) { time_zone tz = utc_time_zone(); auto tp = chrono::system_clock::from_time_t(0);
diff --git a/absl/time/internal/cctz/src/time_zone_impl.cc b/absl/time/internal/cctz/src/time_zone_impl.cc index 5f2f49e..5cf38e7 100644 --- a/absl/time/internal/cctz/src/time_zone_impl.cc +++ b/absl/time/internal/cctz/src/time_zone_impl.cc
@@ -76,9 +76,18 @@ // Add the new time zone to the map. std::lock_guard<std::mutex> lock(TimeZoneMutex()); if (time_zone_map == nullptr) time_zone_map = new TimeZoneImplByName; + if (!new_impl->zone_) { + // Load failed, but a successful insertion may have happened concurrently. + // Check it now that we have the lock. Otherwise, avoid caching negative + // entries to avoid unbounded growth and DoS attacks. + auto itr = time_zone_map->find(name); + const Impl* impl = (itr != time_zone_map->end()) ? itr->second : utc_impl; + *tz = time_zone(impl); + return impl != utc_impl; + } const Impl*& impl = (*time_zone_map)[name]; if (impl == nullptr) { // this thread won any load race - impl = new_impl->zone_ ? new_impl.release() : utc_impl; + impl = new_impl.release(); } *tz = time_zone(impl); return impl != utc_impl;
diff --git a/absl/time/internal/cctz/src/time_zone_info.cc b/absl/time/internal/cctz/src/time_zone_info.cc index f8484c9..f7ed379 100644 --- a/absl/time/internal/cctz/src/time_zone_info.cc +++ b/absl/time/internal/cctz/src/time_zone_info.cc
@@ -32,6 +32,14 @@ #include "absl/time/internal/cctz/src/time_zone_info.h" +#include "absl/base/config.h" + +#if !defined(_MSC_VER) +#include <fcntl.h> +#include <sys/stat.h> +#include <unistd.h> +#endif + #include <algorithm> #include <cassert> #include <chrono> @@ -41,16 +49,17 @@ #include <cstring> #include <fstream> #include <functional> +#include <limits> #include <memory> #include <sstream> #include <string> #include <utility> #include <vector> -#include "absl/base/config.h" #include "absl/time/internal/cctz/include/cctz/civil_time.h" #include "absl/time/internal/cctz/src/time_zone_fixed.h" #include "absl/time/internal/cctz/src/time_zone_posix.h" +#include "absl/time/internal/cctz/src/tzfile.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -338,6 +347,14 @@ return EquivTransitions(transitions_.back().type_index, dst_ti); } + // We require that zoneinfo data with a rule for future transitions + // ends with a non-negative transition. This removes the need to add + // any "second-half" transition to ensure differences between adjacent + // transitions are always representable, while also guaranteeing that + // the arithmetic used to shift between 400-year cycles never overflows. + // All valid zones easily meet this requirement. + if (transitions_.back().unix_time < 0) return false; + // Extend the transitions for an additional 401 years using the future // specification. Years beyond those can be handled by mapping back to // a cycle-equivalent year within that range. Note that we need 401 @@ -382,16 +399,46 @@ using FilePtr = std::unique_ptr<FILE, int (*)(FILE*)>; -// fopen(3) adaptor. -inline FilePtr FOpen(const char* path, const char* mode) { +// fopen(3) adaptor for reading zoneinfo files (read-only binary mode). +inline FilePtr FOpen(const char* path) { #if defined(_MSC_VER) FILE* fp; - if (fopen_s(&fp, path, mode) != 0) fp = nullptr; + if (fopen_s(&fp, path, "rb") != 0) fp = nullptr; return FilePtr(fp, fclose); #else - // TODO: Enable the close-on-exec flag. - return FilePtr(fopen(path, mode), fclose); + // Open non-blocking and verify the target is a regular file before handing it + // to stdio. Zone names are potentially attacker-controlled, and a plain + // fopen() on a FIFO or device node (reachable via the "file:" prefix or an + // absolute path) would block indefinitely or read unbounded data. +#ifndef O_CLOEXEC +#define O_CLOEXEC 0 #endif + const int fd = open(path, O_RDONLY | O_NONBLOCK | O_CLOEXEC); + if (fd >= 0) { + struct stat st; + if (fstat(fd, &st) == 0 && S_ISREG(st.st_mode)) { + FILE* fp = fdopen(fd, "rb"); + if (fp != nullptr) return FilePtr(fp, fclose); + } + close(fd); + } + return FilePtr(nullptr, fclose); +#endif +} + +// Returns true if the zone name starting at pos contains an unsafe path. +inline bool UnsafePath(const std::string& name, std::size_t pos) { + // Path traversal: exact match ".." + if (name.compare(pos, std::string::npos, "..") == 0) return true; + // Path traversal: leading component "../" + if (name.compare(pos, 3, "../") == 0) return true; + // Path traversal: interior component "/../" + if (name.find("/../", pos) != std::string::npos) return true; + // Path traversal: trailing component "/.." + if (name.size() - pos >= 3 && name.compare(name.size() - 3, 3, "/..") == 0) { + return true; + } + return false; } // A stdio(3)-backed implementation of ZoneInfoSource. @@ -431,6 +478,11 @@ // Use of the "file:" prefix is intended for testing purposes only. const std::size_t pos = (name.compare(0, 5, "file:") == 0) ? 5 : 0; + // Reject unsafe paths (e.g., "../../etc/passwd"). + if (UnsafePath(name, pos)) { + return nullptr; + } + // Map the time-zone name to a path name. std::string path; if (pos == name.size() || name[pos] != '/') { @@ -451,7 +503,7 @@ path.append(name, pos, std::string::npos); // Open the zoneinfo file. - auto fp = FOpen(path.c_str(), "rb"); + auto fp = FOpen(path.c_str()); if (fp == nullptr) return nullptr; return std::unique_ptr<ZoneInfoSource>(new FileZoneInfoSource(std::move(fp))); } @@ -477,7 +529,7 @@ for (const char* tzdata : {"/apex/com.android.tzdata/etc/tz/tzdata", "/data/misc/zoneinfo/current/tzdata", "/system/usr/share/zoneinfo/tzdata"}) { - auto fp = FOpen(tzdata, "rb"); + auto fp = FOpen(tzdata); if (fp == nullptr) continue; char hbuf[24]; // covers header.zonetab_offset too @@ -497,9 +549,12 @@ if (zonecnt * sizeof(ebuf) != index_size) continue; for (std::size_t i = 0; i != zonecnt; ++i) { if (fread(ebuf, 1, sizeof(ebuf), fp.get()) != sizeof(ebuf)) break; - const std::int_fast32_t start = data_offset + Decode32(ebuf + 40); + const std::int_fast64_t start = + std::int_fast64_t{data_offset} + Decode32(ebuf + 40); const std::int_fast32_t length = Decode32(ebuf + 44); if (start < 0 || length < 0) break; + // fseek() takes a long + if (start > std::numeric_limits<long>::max()) break; ebuf[40] = '\0'; // ensure zone name is NUL terminated if (strcmp(name.c_str() + pos, ebuf) == 0) { if (fseek(fp.get(), static_cast<long>(start), SEEK_SET) != 0) break; @@ -537,6 +592,11 @@ // Use of the "file:" prefix is intended for testing purposes only. const std::size_t pos = (name.compare(0, 5, "file:") == 0) ? 5 : 0; + // Reject unsafe paths (e.g., "../../etc/passwd"). + if (UnsafePath(name, pos)) { + return nullptr; + } + // Prefixes where a Fuchsia component might find zoneinfo files, // in descending order of preference. const auto kTzdataPrefixes = { @@ -561,7 +621,7 @@ if (!prefix.empty()) path += "zoneinfo/tzif2/"; // format path.append(name, pos, std::string::npos); - auto fp = FOpen(path.c_str(), "rb"); + auto fp = FOpen(path.c_str()); if (fp == nullptr) continue; std::string version; @@ -662,6 +722,12 @@ if (hdr.ttisstdcnt != 0 && hdr.ttisstdcnt != hdr.typecnt) return false; if (hdr.ttisutcnt != 0 && hdr.ttisutcnt != hdr.typecnt) return false; + // Bound the header counts before sizing tbuf so that a hostile TZif blob + // cannot force a very large zero-filled allocation from a tiny input. + if (hdr.timecnt > TZ_MAX_TIMES) return false; + if (hdr.typecnt > TZ_MAX_TYPES) return false; + if (hdr.charcnt > TZ_MAX_CHARS) return false; + // Read the data into a local buffer. std::size_t len = hdr.DataLength(time_len); std::vector<char> tbuf(len); @@ -674,6 +740,14 @@ for (std::size_t i = 0; i != hdr.timecnt; ++i) { transitions_[i].unix_time = (time_len == 4) ? Decode32(bp) : Decode64(bp); bp += time_len; + // A valid zoneinfo file keeps transition times far from the int64 limits. + // A hostile one can place them at the extremes, where the + // reverse-conversion arithmetic in MakeTime() (tr.unix_time +/- a sub-day + // civil delta, see MakeSkipped()/MakeRepeated()) overflows. Bound them to + // +/-(1<<59), the times used by the no-op transitions added below. + if (transitions_[i].unix_time < -(1LL << 59) || + transitions_[i].unix_time > (1LL << 59)) + return false; // out of range if (i != 0) { // Check that the transitions are ordered by time (as zic guarantees). if (!Transition::ByUnixTime()(transitions_[i - 1], transitions_[i])) @@ -705,16 +779,22 @@ // Determine the before-first-transition type. default_transition_type_ = 0; if (seen_type_0 && hdr.timecnt != 0) { - std::uint_fast8_t index = 0; + std::size_t index = 0; if (transition_types_[0].is_dst) { index = transitions_[0].type_index; while (index != 0 && transition_types_[index].is_dst) --index; } while (index != hdr.typecnt && transition_types_[index].is_dst) ++index; - if (index != hdr.typecnt) default_transition_type_ = index; + if (index != hdr.typecnt) + default_transition_type_ = static_cast<std::uint_fast8_t>(index); } - // Copy all the abbreviations. + // Copy all the abbreviations. The area holds NUL-terminated strings, and + // LocalTime() hands out a pointer into it, so the final abbreviation has + // to be terminated within the area itself. Otherwise an abbreviation runs + // on into whatever ExtendTransitions() later appends. (hdr.charcnt != 0 + // because every abbr_index was validated to be less than it.) + if (bp[hdr.charcnt - 1] != '\0') return false; abbreviations_.reserve(hdr.charcnt + 10); abbreviations_.assign(bp, hdr.charcnt); bp += hdr.charcnt; @@ -771,6 +851,7 @@ // previous transition is always representable, without overflow. const Transition& last(transitions_.back()); if (last.unix_time < 0) { + assert(!extended_); const std::uint_fast8_t type_index = last.type_index; Transition& tr(*transitions_.emplace(transitions_.end())); tr.unix_time = 2147483647; // 2038-01-19T03:14:07+00:00
diff --git a/absl/time/internal/cctz/src/time_zone_lookup_test.cc b/absl/time/internal/cctz/src/time_zone_lookup_test.cc index cd08a35..1147e93 100644 --- a/absl/time/internal/cctz/src/time_zone_lookup_test.cc +++ b/absl/time/internal/cctz/src/time_zone_lookup_test.cc
@@ -15,21 +15,27 @@ #include <chrono> #include <cstddef> #include <cstdlib> +#include <cstring> #include <future> #include <limits> +#include <memory> #include <string> #include <thread> +#include <utility> #include <vector> #include "absl/base/config.h" #include "absl/time/internal/cctz/include/cctz/time_zone.h" + #if defined(__linux__) #include <features.h> #endif #include "gtest/gtest.h" #include "absl/time/internal/cctz/include/cctz/civil_time.h" +#include "absl/time/internal/cctz/include/cctz/zone_info_source.h" #include "absl/time/internal/cctz/src/test_time_zone_names.h" +#include "absl/time/internal/cctz/src/tzfile.h" namespace chrono = std::chrono; @@ -180,6 +186,24 @@ EXPECT_FALSE(load_time_zone("", &tz)); EXPECT_EQ(chrono::system_clock::from_time_t(0), convert(civil_second(1970, 1, 1, 0, 0, 0), tz)); // UTC + + // Reject path-traversal components. + EXPECT_FALSE(load_time_zone("file:../etc/passwd", &tz)); + EXPECT_FALSE(load_time_zone("file:../../etc/passwd", &tz)); + EXPECT_FALSE(load_time_zone("file:/../etc/passwd", &tz)); + EXPECT_FALSE(load_time_zone("file:America/../America/Los_Angeles", &tz)); + + // Reject a fixed-offset name with a NUL where a digit belongs. + for (const int i : {10, 11, 13, 14, 16, 17}) { + std::string name = "Fixed/UTC+00:00:00"; + name[static_cast<std::size_t>(i)] = '\0'; + EXPECT_FALSE(load_time_zone(name, &tz)) << "NUL at offset " << i; + } + + // Reject non-regular files and directories. + EXPECT_FALSE(load_time_zone("file:/dev/null", &tz)); + EXPECT_FALSE(load_time_zone("file:/dev/stdin", &tz)); + EXPECT_FALSE(load_time_zone("file:/tmp", &tz)); } TEST(TimeZone, Equality) { @@ -912,6 +936,181 @@ ExpectTime(tp, tz, 10000, 1, 1, 0, 0, 0, 0 * 3600, false, "UTC"); } +// A ZoneInfoSource implementation backed by an in-memory string buffer. +class StringZoneInfoSource : public ZoneInfoSource { + public: + explicit StringZoneInfoSource(std::string data) + : data_(std::move(data)), offset_(0) {} + + std::size_t Read(void* ptr, std::size_t size) override { + std::size_t n = (std::min)(size, data_.size() - offset_); + std::memcpy(ptr, data_.data() + offset_, n); + offset_ += n; + return n; + } + + int Skip(std::size_t offset) override { + if (offset > data_.size() - offset_) return -1; + offset_ += offset; + return 0; + } + + private: + std::string data_; + std::size_t offset_; +}; + +// Constructs a minimal TZif2 string with a single 64-bit transition +// at the given transition time and a future POSIX rule. The abbreviation +// area holds abbr verbatim, so a valid file's abbr must include the +// trailing '\0' (e.g., std::string{"EST", 4}). +std::string MakeExtendedTzif(std::int_fast64_t unix_time, + std::int_fast32_t utc_offset, + const std::string& abbr, + const std::string& future_spec) { + std::string s; + auto append32 = [&s](std::int_fast32_t v) { + const std::int_fast32_t s32max = 0x7fffffff; + const auto s32maxU = static_cast<std::uint_fast32_t>(s32max); + std::uint_fast32_t uv; + if (v >= 0) { + uv = static_cast<std::uint_fast32_t>(v); + } else { + uv = static_cast<std::uint_fast32_t>(v + s32max + 1) + s32maxU + 1; + } + for (int i = 3; i >= 0; --i) { + s.push_back(static_cast<char>((uv >> (i * 8)) & 0xff)); + } + }; + auto append64 = [&s](std::int_fast64_t v) { + const std::int_fast64_t s64max = 0x7fffffffffffffff; + const auto s64maxU = static_cast<std::uint_fast64_t>(s64max); + std::uint_fast64_t uv; + if (v >= 0) { + uv = static_cast<std::uint_fast64_t>(v); + } else { + uv = static_cast<std::uint_fast64_t>(v + s64max + 1) + s64maxU + 1; + } + for (int i = 7; i >= 0; --i) { + s.push_back(static_cast<char>((uv >> (i * 8)) & 0xff)); + } + }; + + const std::size_t charcnt = abbr.size(); + + // 32-bit header + s.append(TZ_MAGIC, 4); + s.push_back('2'); // tzh_version + s.append(15, '\0'); // tzh_reserved + append32(0); // tzh_ttisutcnt + append32(0); // tzh_ttisstdcnt + append32(0); // tzh_leapcnt + append32(0); // tzh_timecnt (0 32-bit transitions) + append32(1); // tzh_typecnt (1 ttinfo record) + append32(static_cast<std::int_fast32_t>(charcnt)); // tzh_charcnt + + // 32-bit data block + append32(utc_offset); // tt_utoff + s.push_back(0); // tt_isdst (standard time) + s.push_back(0); // tt_desigidx + s.append(abbr); // abbreviation table + + // 64-bit header + s.append(TZ_MAGIC, 4); + s.push_back('2'); // tzh_version + s.append(15, '\0'); // tzh_reserved + append32(0); // tzh_ttisutcnt + append32(0); // tzh_ttisstdcnt + append32(0); // tzh_leapcnt + append32(1); // tzh_timecnt (1 64-bit transition) + append32(1); // tzh_typecnt (1 ttinfo record) + append32(static_cast<std::int_fast32_t>(charcnt)); // tzh_charcnt + + // 64-bit data block + append64(unix_time); // transition time + s.push_back(0); // type index for transition + append32(utc_offset); // tt_utoff + s.push_back(0); // tt_isdst (standard time) + s.push_back(0); // tt_desigidx + s.append(abbr); // abbreviation table + + // POSIX footer + s.push_back('\n'); + s.append(future_spec); + s.push_back('\n'); + return s; +} + +std::unique_ptr<ZoneInfoSource> ExtendedTestFactory( + const std::string& name, + const std::function<std::unique_ptr<ZoneInfoSource>(const std::string&)>& + fallback) { + if (name == "test:ExtendedBeforeEpoch") { + // -1 (1969-12-31T23:59:59Z) is the latest final transition before the + // epoch, so the zone is rejected despite the future specification. + return std::unique_ptr<ZoneInfoSource>( + new StringZoneInfoSource(MakeExtendedTzif( + -1, -5 * 3600, std::string{"EST", 4}, "EST5EDT,M3.2.0,M11.1.0"))); + } + if (name == "test:ExtendedFarFuture") { + // 0 (1970-01-01T00:00:00Z) is the earliest final transition an extended + // zone may have, which maximizes the 400-year shift that BreakTime() + // needs for a lookup at the maximum time. + return std::unique_ptr<ZoneInfoSource>( + new StringZoneInfoSource(MakeExtendedTzif( + 0, -5 * 3600, std::string{"EST", 4}, "EST5EDT,M3.2.0,M11.1.0"))); + } + if (name == "test:UnterminatedAbbreviation") { + // The abbreviation area is missing its final NUL, so the abbreviation + // would run into whatever ExtendTransitions() appends behind it. + return std::unique_ptr<ZoneInfoSource>(new StringZoneInfoSource( + MakeExtendedTzif(0, -5 * 3600, "EST", "EST5EDT,M3.2.0,M11.1.0"))); + } + return fallback(name); +} + +// Tests that a TZif file whose abbreviation area is not NUL-terminated +// is rejected. +TEST(TimeZoneEdgeCase, UnterminatedAbbreviation) { + auto prev_factory = cctz_extension::zone_info_source_factory; + cctz_extension::zone_info_source_factory = ExtendedTestFactory; + + time_zone tz; + EXPECT_FALSE(load_time_zone("test:UnterminatedAbbreviation", &tz)); + + cctz_extension::zone_info_source_factory = prev_factory; +} + +// Tests that a TZif file whose explicit transitions end before epoch +// is rejected when it has a POSIX DST footer string. +TEST(TimeZoneEdgeCase, ExtendedBeforeEpoch) { + auto prev_factory = cctz_extension::zone_info_source_factory; + cctz_extension::zone_info_source_factory = ExtendedTestFactory; + + // Extended zones must end with a non-negative explicit transition. + time_zone tz; + EXPECT_FALSE(load_time_zone("test:ExtendedBeforeEpoch", &tz)); + + cctz_extension::zone_info_source_factory = prev_factory; +} + +// Looking up the maximum time in an extended zone must fold back through the +// 400-year cycle without overflowing when BreakTime() computes the shift. +TEST(TimeZoneEdgeCase, ExtendedFarFuture) { + auto prev_factory = cctz_extension::zone_info_source_factory; + cctz_extension::zone_info_source_factory = ExtendedTestFactory; + + time_zone tz; + ASSERT_TRUE(load_time_zone("test:ExtendedFarFuture", &tz)); + + auto tp_max = time_point<absl::time_internal::cctz::seconds>::max(); + ExpectTime(tp_max, tz, 292277026596, 12, 4, 10, 30, 7, -5 * 3600, false, + "EST"); + EXPECT_STREQ("EST", tz.lookup(tp_max).abbr); + + cctz_extension::zone_info_source_factory = prev_factory; +} + } // namespace cctz } // namespace time_internal ABSL_NAMESPACE_END
diff --git a/absl/time/internal/cctz/src/time_zone_posix.cc b/absl/time/internal/cctz/src/time_zone_posix.cc index efea080..c60f98b 100644 --- a/absl/time/internal/cctz/src/time_zone_posix.cc +++ b/absl/time/internal/cctz/src/time_zone_posix.cc
@@ -92,14 +92,17 @@ return p; } -// datetime = ( Jn | n | Mm.w.d ) [ / offset ] +// datetime = , ( Jn | n | Mm.w.d ) [ / offset ] const char* ParseDateTime(const char* p, PosixTransition* res) { - if (p != nullptr && *p == ',') { + if (p != nullptr) { + if (*p != ',') return nullptr; if (*++p == 'M') { int month = 0; - if ((p = ParseInt(p + 1, 1, 12, &month)) != nullptr && *p == '.') { + if ((p = ParseInt(p + 1, 1, 12, &month)) != nullptr) { + if (*p != '.') return nullptr; int week = 0; - if ((p = ParseInt(p + 1, 1, 5, &week)) != nullptr && *p == '.') { + if ((p = ParseInt(p + 1, 1, 5, &week)) != nullptr) { + if (*p != '.') return nullptr; int weekday = 0; if ((p = ParseInt(p + 1, 0, 6, &weekday)) != nullptr) { res->date.fmt = PosixTransition::M; @@ -122,17 +125,17 @@ res->date.n.day = static_cast<std::int_fast16_t>(day); } } - } - if (p != nullptr) { - res->time.offset = 2 * 60 * 60; // default offset is 02:00:00 - if (*p == '/') p = ParseOffset(p + 1, -167, 167, 1, &res->time.offset); + if (p != nullptr) { + res->time.offset = 2 * 60 * 60; // default offset is 02:00:00 + if (*p == '/') p = ParseOffset(p + 1, -167, 167, 1, &res->time.offset); + } } return p; } } // namespace -// spec = std offset [ dst [ offset ] , datetime , datetime ] +// spec = std offset [ dst [ offset ] datetime datetime ] bool ParsePosixSpec(const std::string& spec, PosixTimeZone* res) { const char* p = spec.c_str(); if (*p == ':') return false;
diff --git a/absl/time/internal/cctz/src/time_zone_posix.h b/absl/time/internal/cctz/src/time_zone_posix.h index 7fd2b9e..23f5699 100644 --- a/absl/time/internal/cctz/src/time_zone_posix.h +++ b/absl/time/internal/cctz/src/time_zone_posix.h
@@ -13,7 +13,7 @@ // limitations under the License. // Parsing of a POSIX zone spec as described in the TZ part of section 8.3 in -// http://pubs.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap08.html. +// https://pubs.opengroup.org/onlinepubs/9799919799/basedefs/V1_chap08.html. // // The current POSIX spec for America/Los_Angeles is "PST8PDT,M3.2.0,M11.1.0", // which would be broken down as ...
diff --git a/absl/time/internal/cctz/src/time_zone_posix_test.cc b/absl/time/internal/cctz/src/time_zone_posix_test.cc new file mode 100644 index 0000000..8e429f7 --- /dev/null +++ b/absl/time/internal/cctz/src/time_zone_posix_test.cc
@@ -0,0 +1,195 @@ +// Copyright 2026 Google Inc. All Rights Reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/time/internal/cctz/src/time_zone_posix.h" + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/config.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace time_internal { +namespace cctz { + +using ::testing::Eq; +using ::testing::IsEmpty; + +// We only support the second POSIX format (that is, neither the +// "first character is a <colon>" format, nor the "geographical +// or a special timezone" format). We also require DST start/end +// rules whenever a DST abbreviation is given (zic always provides +// them). So, ... +// +// spec = abbr offset [ abbr [ offset ] datetime datetime ] +// abbr = <.*?> | [^-+,\d]{3,} +// offset = [+|-]hh[:mm[:ss]] +// datetime = , ( Jn | n | Mm.w.d ) [ / offset ] + +TEST(ParsePosixSpec, UnsupportedFormats) { + PosixTimeZone zone; + EXPECT_FALSE(ParsePosixSpec(":characters", &zone)); + EXPECT_FALSE(ParsePosixSpec("Area/Location", &zone)); +} + +TEST(ParsePosixSpec, StdOnly) { + PosixTimeZone zone; + + // America/Cancun + EXPECT_TRUE(ParsePosixSpec("EST5", &zone)); + EXPECT_THAT(zone.std_abbr, Eq("EST")); + EXPECT_THAT(zone.std_offset, Eq(-5 * 60 * 60)); + EXPECT_THAT(zone.dst_abbr, IsEmpty()); + + // Australia/Darwin + EXPECT_TRUE(ParsePosixSpec("ACST-9:30", &zone)); + EXPECT_THAT(zone.std_abbr, Eq("ACST")); + EXPECT_THAT(zone.std_offset, Eq((9 * 60 + 30) * 60)); + EXPECT_THAT(zone.dst_abbr, IsEmpty()); + + // Australia/Eucla + EXPECT_TRUE(ParsePosixSpec("<+0845>-8:45", &zone)); + EXPECT_THAT(zone.std_abbr, Eq("+0845")); + EXPECT_THAT(zone.std_offset, Eq((8 * 60 + 45) * 60)); + EXPECT_THAT(zone.dst_abbr, IsEmpty()); +} + +TEST(ParsePosixSpec, WithDst) { + PosixTimeZone zone; + + // America/New_York + EXPECT_TRUE(ParsePosixSpec("EST5EDT,M3.2.0,M11.1.0", &zone)); + EXPECT_THAT(zone.std_abbr, Eq("EST")); + EXPECT_THAT(zone.std_offset, Eq(-5 * 60 * 60)); + EXPECT_THAT(zone.dst_abbr, Eq("EDT")); + EXPECT_THAT(zone.dst_offset, Eq(-4 * 60 * 60)); + EXPECT_THAT(zone.dst_start.date.fmt, Eq(PosixTransition::M)); + EXPECT_THAT(zone.dst_start.date.m.month, Eq(3)); + EXPECT_THAT(zone.dst_start.date.m.week, Eq(2)); + EXPECT_THAT(zone.dst_start.date.m.weekday, Eq(0)); + EXPECT_THAT(zone.dst_start.time.offset, Eq(2 * 60 * 60)); + EXPECT_THAT(zone.dst_end.date.fmt, Eq(PosixTransition::M)); + EXPECT_THAT(zone.dst_end.date.m.month, Eq(11)); + EXPECT_THAT(zone.dst_end.date.m.week, Eq(1)); + EXPECT_THAT(zone.dst_end.date.m.weekday, Eq(0)); + EXPECT_THAT(zone.dst_end.time.offset, Eq(2 * 60 * 60)); + + // Australia/Adelaide + EXPECT_TRUE(ParsePosixSpec("ACST-9:30ACDT,M10.1.0,M4.1.0/3", &zone)); + EXPECT_THAT(zone.std_abbr, Eq("ACST")); + EXPECT_THAT(zone.std_offset, Eq((9 * 60 + 30) * 60)); + EXPECT_THAT(zone.dst_abbr, Eq("ACDT")); + EXPECT_THAT(zone.dst_offset, Eq((10 * 60 + 30) * 60)); + EXPECT_THAT(zone.dst_start.date.fmt, Eq(PosixTransition::M)); + EXPECT_THAT(zone.dst_start.date.m.month, Eq(10)); + EXPECT_THAT(zone.dst_start.date.m.week, Eq(1)); + EXPECT_THAT(zone.dst_start.date.m.weekday, Eq(0)); + EXPECT_THAT(zone.dst_start.time.offset, Eq(2 * 60 * 60)); + EXPECT_THAT(zone.dst_end.date.fmt, Eq(PosixTransition::M)); + EXPECT_THAT(zone.dst_end.date.m.month, Eq(4)); + EXPECT_THAT(zone.dst_end.date.m.week, Eq(1)); + EXPECT_THAT(zone.dst_end.date.m.weekday, Eq(0)); + EXPECT_THAT(zone.dst_end.time.offset, Eq(3 * 60 * 60)); + + // Australia/Lord_Howe + EXPECT_TRUE(ParsePosixSpec("<+1030>-10:30<+11>-11,M10.1.0,M4.1.0", &zone)); + EXPECT_THAT(zone.std_abbr, Eq("+1030")); + EXPECT_THAT(zone.std_offset, Eq((10 * 60 + 30) * 60)); + EXPECT_THAT(zone.dst_abbr, Eq("+11")); + EXPECT_THAT(zone.dst_offset, Eq(11 * 60 * 60)); + EXPECT_THAT(zone.dst_start.date.fmt, Eq(PosixTransition::M)); + EXPECT_THAT(zone.dst_start.date.m.month, Eq(10)); + EXPECT_THAT(zone.dst_start.date.m.week, Eq(1)); + EXPECT_THAT(zone.dst_start.date.m.weekday, Eq(0)); + EXPECT_THAT(zone.dst_start.time.offset, Eq(2 * 60 * 60)); + EXPECT_THAT(zone.dst_end.date.fmt, Eq(PosixTransition::M)); + EXPECT_THAT(zone.dst_end.date.m.month, Eq(4)); + EXPECT_THAT(zone.dst_end.date.m.week, Eq(1)); + EXPECT_THAT(zone.dst_end.date.m.weekday, Eq(0)); + EXPECT_THAT(zone.dst_end.time.offset, Eq(2 * 60 * 60)); + + // Africa/Casablanca (year-round DST) + EXPECT_TRUE(ParsePosixSpec("<+00>0<+01>,0/0,J365/25", &zone)); + EXPECT_THAT(zone.std_abbr, Eq("+00")); + EXPECT_THAT(zone.std_offset, Eq(0)); + EXPECT_THAT(zone.dst_abbr, Eq("+01")); + EXPECT_THAT(zone.dst_offset, Eq(1 * 60 * 60)); + EXPECT_THAT(zone.dst_start.date.fmt, Eq(PosixTransition::N)); + EXPECT_THAT(zone.dst_start.date.n.day, Eq(0)); + EXPECT_THAT(zone.dst_start.time.offset, Eq(0)); + EXPECT_THAT(zone.dst_end.date.fmt, Eq(PosixTransition::J)); + EXPECT_THAT(zone.dst_end.date.n.day, Eq(365)); + EXPECT_THAT(zone.dst_end.time.offset, Eq(25 * 60 * 60)); +} + +TEST(TimeZonePosix, ParseErrors) { + PosixTimeZone zone; + + // STD abbreviation errors. + EXPECT_FALSE(ParsePosixSpec("ET5", &zone)); + EXPECT_FALSE(ParsePosixSpec("ET+", &zone)); + EXPECT_FALSE(ParsePosixSpec("ET-", &zone)); + EXPECT_FALSE(ParsePosixSpec("ET,", &zone)); + EXPECT_FALSE(ParsePosixSpec("<00", &zone)); + + // STD offset errors. + EXPECT_FALSE(ParsePosixSpec("<00>", &zone)); + EXPECT_FALSE(ParsePosixSpec("<00>+", &zone)); + EXPECT_FALSE(ParsePosixSpec("<00>-", &zone)); + EXPECT_FALSE(ParsePosixSpec("<00>?", &zone)); + + // DST abbreviation errors. + EXPECT_FALSE(ParsePosixSpec("EST5DT,M3.2.0,M11.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT+,M3.2.0,M11.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT-,M3.2.0,M11.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("<00>0<-01", &zone)); + + // DST offset errors. + EXPECT_FALSE(ParsePosixSpec("<01>1<00>?,0,0", &zone)); + EXPECT_FALSE(ParsePosixSpec("<01>1<00>+?,0,0", &zone)); + EXPECT_FALSE(ParsePosixSpec("<01>1<00>-?,0,0", &zone)); + + // Malformed DST start date/time. + EXPECT_FALSE(ParsePosixSpec("EST5EDT", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M13.2.0,M11.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.6.0,M11.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.7,M11.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,J0,M11.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,366,M11.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0/,M11.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0/?,M11.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0/1:?,M11.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0/1:2:?,M11.1.0", &zone)); + + // Malformed DST end date/time. + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0,M?.1.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0,M11.?.0", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0,M11.1.?", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0,J?", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0,?", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0,M11.1.0/", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0,M11.1.0/168", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0,M11.1.0/167:60", &zone)); + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0,M11.1.0/167:59:60", &zone)); + + // Trailing data. + EXPECT_FALSE(ParsePosixSpec("EST5EDT,M3.2.0,M11.1.0junk", &zone)); +} + +} // namespace cctz +} // namespace time_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/time/internal/cctz/testdata/version b/absl/time/internal/cctz/testdata/version index 75d34ee..9217a2d 100644 --- a/absl/time/internal/cctz/testdata/version +++ b/absl/time/internal/cctz/testdata/version
@@ -1 +1 @@ -2026b +2026c
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/Africa/Casablanca b/absl/time/internal/cctz/testdata/zoneinfo/Africa/Casablanca index 240ebb2..fb2f5cc 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/Africa/Casablanca +++ b/absl/time/internal/cctz/testdata/zoneinfo/Africa/Casablanca Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/Africa/El_Aaiun b/absl/time/internal/cctz/testdata/zoneinfo/Africa/El_Aaiun index 909c5f9..46286b9 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/Africa/El_Aaiun +++ b/absl/time/internal/cctz/testdata/zoneinfo/Africa/El_Aaiun Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/America/Edmonton b/absl/time/internal/cctz/testdata/zoneinfo/America/Edmonton index 645ee94..379e365 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/America/Edmonton +++ b/absl/time/internal/cctz/testdata/zoneinfo/America/Edmonton Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/America/Yellowknife b/absl/time/internal/cctz/testdata/zoneinfo/America/Yellowknife index 645ee94..379e365 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/America/Yellowknife +++ b/absl/time/internal/cctz/testdata/zoneinfo/America/Yellowknife Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/Canada/Mountain b/absl/time/internal/cctz/testdata/zoneinfo/Canada/Mountain index 645ee94..379e365 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/Canada/Mountain +++ b/absl/time/internal/cctz/testdata/zoneinfo/Canada/Mountain Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/zone1970.tab b/absl/time/internal/cctz/testdata/zoneinfo/zone1970.tab index a9b47bc..635eabc 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/zone1970.tab +++ b/absl/time/internal/cctz/testdata/zoneinfo/zone1970.tab
@@ -112,7 +112,7 @@ CA +624900-0920459 America/Rankin_Inlet Central - NU (central) CA +5024-10439 America/Regina CST - SK (most areas) CA +5017-10750 America/Swift_Current CST - SK (midwest) -CA +5333-11328 America/Edmonton Mountain - AB, BC(E), NT(E), SK(W) +CA +5333-11328 America/Edmonton CST - AB, BC(E), NT(E), SK(W) CA +690650-1050310 America/Cambridge_Bay Mountain - NU (west) CA +682059-1334300 America/Inuvik Mountain - NT (west) CA +4916-12307 America/Vancouver MST - BC (most areas)
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/zonenow.tab b/absl/time/internal/cctz/testdata/zoneinfo/zonenow.tab index 54e4485..9c3a8cf 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/zonenow.tab +++ b/absl/time/internal/cctz/testdata/zoneinfo/zonenow.tab
@@ -56,16 +56,19 @@ XX -2504-13005 Pacific/Pitcairn Pitcairn # # -08/-07 - PST/PDT (North America DST) -XX +340308-1181434 America/Los_Angeles Pacific (PST/PDT) - US & Canada; Mexico near US border +XX +340308-1181434 America/Los_Angeles Pacific (PST/PDT) - US; Mexico near US border # # -08/-07 - PST/PDT (North America DST) until 2026-11-01 02:00; then MST -XX +4916-12307 America/Vancouver MST - BC (most areas) +XX +4916-12307 America/Vancouver Mountain Standard (MST) - British Columbia (most areas) # # -07 - MST XX +332654-1120424 America/Phoenix Mountain Standard (MST) - Arizona; western Mexico; Yukon # # -07/-06 - MST/MDT (North America DST) -XX +394421-1045903 America/Denver Mountain (MST/MDT) - US & Canada; Mexico near US border +XX +394421-1045903 America/Denver Mountain (MST/MDT) - US; Mexico near US border; northern Canada +# +# -07/-06 - MST/MDT (North America DST) until 2026-11-01 02:00; then CST +XX +5333-11328 America/Edmonton Central Standard (CST) - Alberta and some neighbors # # -06 XX -0054-08936 Pacific/Galapagos Galápagos