Rollback StringAppendAndOverwrite() - the problem is that StringResizeAndOverwrite has MSAN testing of the entire string. This causes quadratic MSAN verification on small appends. PiperOrigin-RevId: 824629932 Change-Id: Ibefff781f5923c8bd2c1dc364f5b63fcb1d0f5ab
diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index d490e65..4944823 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -293,7 +293,6 @@ "strings/cord_buffer.h" "strings/escaping.cc" "strings/escaping.h" - "strings/internal/append_and_overwrite.h" "strings/internal/charconv_bigint.cc" "strings/internal/charconv_bigint.h" "strings/internal/charconv_parse.cc"
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index c2b00e9..1ecc069 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel
@@ -100,7 +100,6 @@ "string_view.h", ], deps = [ - ":append_and_overwrite", ":charset", ":internal", ":resize_and_overwrite", @@ -171,32 +170,6 @@ ], ) -cc_library( - name = "append_and_overwrite", - hdrs = ["internal/append_and_overwrite.h"], - copts = ABSL_DEFAULT_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - visibility = ["//visibility:private"], - deps = [ - ":resize_and_overwrite", - "//absl/base:config", - "//absl/base:core_headers", - ], -) - -cc_test( - name = "append_and_overwrite_test", - srcs = ["internal/append_and_overwrite_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":append_and_overwrite", - "//absl/log:absl_check", - "@googletest//:gtest", - "@googletest//:gtest_main", - ], -) - cc_test( name = "match_test", size = "small", @@ -652,7 +625,6 @@ copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ - ":append_and_overwrite", ":cord_internal", ":cordz_info", ":cordz_update_scope",
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index b28e569..da44ef7 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt
@@ -76,7 +76,6 @@ ${ABSL_DEFAULT_COPTS} DEPS absl::string_view - absl::strings_append_and_overwrite absl::strings_internal absl::strings_resize_and_overwrite absl::base @@ -171,32 +170,6 @@ GTest::gmock_main ) -absl_cc_library( - NAME - strings_append_and_overwrite - HDRS - "internal/append_and_overwrite.h" - COPTS - ${ABSL_DEFAULT_COPTS} - DEPS - absl::config - absl::core_headers - absl::strings_resize_and_overwrite -) - -absl_cc_test( - NAME - strings_append_and_overwrite_test - SRCS - "internal/append_and_overwrite_test.cc" - COPTS - ${ABSL_TEST_COPTS} - DEPS - absl::strings_resize_and_overwrite - absl::absl_check - GTest::gmock_main -) - absl_cc_test( NAME match_test @@ -1057,7 +1030,6 @@ absl::raw_logging_internal absl::span absl::strings - absl::strings_append_and_overwrite absl::strings_resize_and_overwrite absl::type_traits absl::weakly_mixed_integer
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc index d3014f3..91fcf91 100644 --- a/absl/strings/cord.cc +++ b/absl/strings/cord.cc
@@ -44,13 +44,13 @@ #include "absl/functional/function_ref.h" #include "absl/strings/cord_buffer.h" #include "absl/strings/escaping.h" -#include "absl/strings/internal/append_and_overwrite.h" #include "absl/strings/internal/cord_data_edge.h" #include "absl/strings/internal/cord_internal.h" #include "absl/strings/internal/cord_rep_btree.h" #include "absl/strings/internal/cord_rep_crc.h" #include "absl/strings/internal/cord_rep_flat.h" #include "absl/strings/internal/cordz_update_tracker.h" +#include "absl/strings/internal/resize_uninitialized.h" #include "absl/strings/match.h" #include "absl/strings/resize_and_overwrite.h" #include "absl/strings/str_cat.h" @@ -1065,11 +1065,12 @@ } void AppendCordToString(const Cord& src, std::string* absl_nonnull dst) { - strings_internal::StringAppendAndOverwrite( - *dst, src.size(), [&src](char* buf, size_t buf_size) { - src.CopyToArrayImpl(buf); - return buf_size; - }); + const size_t cur_dst_size = dst->size(); + const size_t new_dst_size = cur_dst_size + src.size(); + absl::strings_internal::STLStringResizeUninitializedAmortized(dst, + new_dst_size); + char* append_ptr = &(*dst)[cur_dst_size]; + src.CopyToArrayImpl(append_ptr); } void Cord::CopyToArraySlowPath(char* absl_nonnull dst) const {
diff --git a/absl/strings/internal/append_and_overwrite.h b/absl/strings/internal/append_and_overwrite.h deleted file mode 100644 index 622e583..0000000 --- a/absl/strings/internal/append_and_overwrite.h +++ /dev/null
@@ -1,76 +0,0 @@ -// Copyright 2025 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. - -#ifndef ABSL_STRINGS_INTERNAL_APPEND_AND_OVERWRITE_H_ -#define ABSL_STRINGS_INTERNAL_APPEND_AND_OVERWRITE_H_ - -#include "absl/base/config.h" -#include "absl/base/macros.h" -#include "absl/base/optimization.h" -#include "absl/strings/resize_and_overwrite.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace strings_internal { - -// An internal-only variant similar to `absl::StringResizeAndOverwrite()` -// optimized for repeated appends to a string that uses exponential growth so -// that the amortized complexity of increasing the string size by a small amount -// is O(1), in contrast to O(str.size()) in the case of precise growth. Use of -// this function is subtle; see https://reviews.llvm.org/D102727 to understand -// the tradeoffs. -// -// Appends at most `append_n` characters to `str`, using the user-provided -// operation `append_op` to modify the possibly indeterminate -// contents. `append_op` must return the length of the buffer appended to `str`. -// -// Invalidates all iterators, pointers, and references into `str`, regardless -// of whether reallocation occurs. -// -// `append_op(value_type* buf, size_t buf_size)` is allowed to write -// `value_type{}` to `buf[buf_size]`, which facilitiates interoperation with -// functions that write a trailing NUL. -template <typename T, typename Op> -void StringAppendAndOverwrite(T& str, typename T::size_type append_n, - Op append_op) { - ABSL_HARDENING_ASSERT(str.size() <= str.max_size() - append_n); - auto old_size = str.size(); - auto resize = old_size + append_n; - - // Make sure to always grow by at least a factor of 2x. - if (resize > str.capacity()) { - if (ABSL_PREDICT_FALSE(str.capacity() > str.max_size() / 2)) { - resize = str.max_size(); - } else if (resize < str.capacity() * 2) { - resize = str.capacity() * 2; - } - } - - StringResizeAndOverwrite( - str, resize, - [old_size, append_n, do_append = std::move(append_op)]( - typename T::value_type* data_ptr, typename T::size_type) mutable { - auto num_appended = - std::move(do_append)(data_ptr + old_size, append_n); - ABSL_HARDENING_ASSERT(num_appended >= 0 && num_appended <= append_n); - return old_size + num_appended; - }); -} - -} // namespace strings_internal -ABSL_NAMESPACE_END -} // namespace absl - - -#endif // ABSL_STRINGS_INTERNAL_APPEND_AND_OVERWRITE_H_
diff --git a/absl/strings/internal/append_and_overwrite_test.cc b/absl/strings/internal/append_and_overwrite_test.cc deleted file mode 100644 index aa9c7a1..0000000 --- a/absl/strings/internal/append_and_overwrite_test.cc +++ /dev/null
@@ -1,95 +0,0 @@ -// Copyright 2025 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 "absl/strings/internal/append_and_overwrite.h" - -#include <algorithm> -#include <cstddef> -#include <string> - -#include "gtest/gtest.h" -#include "absl/log/absl_check.h" - -namespace { - -struct AppendAndOverwriteParam { - size_t initial_size; - size_t append_capacity; - size_t append_size; -}; - -using StringAppendAndOverwriteTest = - ::testing::TestWithParam<AppendAndOverwriteParam>; - -TEST_P(StringAppendAndOverwriteTest, StringAppendAndOverwrite) { - const auto& param = GetParam(); - std::string s(param.initial_size, 'a'); - absl::strings_internal::StringAppendAndOverwrite( - s, param.append_capacity, [&](char* p, size_t n) { - ABSL_CHECK_EQ(n, param.append_capacity); - std::fill_n(p, param.append_size, 'b'); - p[param.append_size] = '\0'; - return param.append_size; - }); - - std::string expected = - std::string(param.initial_size, 'a') + - std::string(param.append_size, - 'b'); - - EXPECT_EQ(s, expected); - EXPECT_EQ(s.c_str()[s.size()], '\0'); -} - -// clang-format off -INSTANTIATE_TEST_SUITE_P(StringAppendAndOverwriteTestSuite, - StringAppendAndOverwriteTest, - ::testing::ValuesIn<AppendAndOverwriteParam>({ - {0, 10, 5}, - {10, 10, 10}, - {10, 15, 15}, - {10, 20, 15}, - {10, 40, 40}, - {10, 50, 40}, - {30, 35, 35}, - {30, 45, 35}, - {10, 30, 15}, - })); -// clang-format on - -TEST(StringAppendAndOverwrite, AmortizedComplexity) { - std::string str; - std::string expected; - size_t prev_cap = str.capacity(); - int cap_increase_count = 0; - for (int i = 0; i < 1000; ++i) { - char c = static_cast<char>('a' + (i % 26)); - absl::strings_internal::StringAppendAndOverwrite( - str, 1, [c](char* buf, size_t buf_size) { - ABSL_CHECK_EQ(buf_size, 1); - buf[0] = c; - return size_t{1}; - }); - expected.push_back(c); - EXPECT_EQ(str, expected); - size_t new_cap = str.capacity(); - if (new_cap > prev_cap) { - ++cap_increase_count; - } - prev_cap = new_cap; - } - EXPECT_LT(cap_increase_count, 50); -} - -} // namespace
diff --git a/absl/strings/str_cat.cc b/absl/strings/str_cat.cc index 546b8ae..99b3a1e 100644 --- a/absl/strings/str_cat.cc +++ b/absl/strings/str_cat.cc
@@ -26,7 +26,7 @@ #include "absl/base/config.h" #include "absl/base/internal/raw_logging.h" #include "absl/base/nullability.h" -#include "absl/strings/internal/append_and_overwrite.h" +#include "absl/strings/internal/resize_uninitialized.h" #include "absl/strings/resize_and_overwrite.h" #include "absl/strings/string_view.h" @@ -53,6 +53,11 @@ return after; } +inline void STLStringAppendUninitializedAmortized(std::string* dest, + size_t to_append) { + strings_internal::AppendUninitializedTraits<std::string>::Append(dest, + to_append); +} } // namespace std::string StrCat(const AlphaNum& a, const AlphaNum& b) { @@ -160,51 +165,49 @@ void AppendPieces(std::string* absl_nonnull dest, std::initializer_list<absl::string_view> pieces) { + size_t old_size = dest->size(); size_t to_append = 0; for (absl::string_view piece : pieces) { ASSERT_NO_OVERLAP(*dest, piece); to_append += piece.size(); } - StringAppendAndOverwrite(*dest, to_append, - [&pieces](char* const buf, size_t buf_size) { - char* out = buf; - for (absl::string_view piece : pieces) { - const size_t this_size = piece.size(); - if (this_size != 0) { - memcpy(out, piece.data(), this_size); - out += this_size; - } - } - assert(out == buf + buf_size); - return buf_size; - }); + STLStringAppendUninitializedAmortized(dest, to_append); + + char* const begin = &(*dest)[0]; + char* out = begin + old_size; + for (absl::string_view piece : pieces) { + const size_t this_size = piece.size(); + if (this_size != 0) { + memcpy(out, piece.data(), this_size); + out += this_size; + } + } + assert(out == begin + dest->size()); } } // namespace strings_internal void StrAppend(std::string* absl_nonnull dest, const AlphaNum& a) { ASSERT_NO_OVERLAP(*dest, a); - strings_internal::StringAppendAndOverwrite( - *dest, a.size(), [&a](char* const buf, size_t buf_size) { - char* out = buf; - out = Append(out, a); - assert(out == buf + buf_size); - return buf_size; - }); + std::string::size_type old_size = dest->size(); + STLStringAppendUninitializedAmortized(dest, a.size()); + char* const begin = &(*dest)[0]; + char* out = begin + old_size; + out = Append(out, a); + assert(out == begin + dest->size()); } void StrAppend(std::string* absl_nonnull dest, const AlphaNum& a, const AlphaNum& b) { ASSERT_NO_OVERLAP(*dest, a); ASSERT_NO_OVERLAP(*dest, b); - strings_internal::StringAppendAndOverwrite( - *dest, a.size() + b.size(), [&a, &b](char* const buf, size_t buf_size) { - char* out = buf; - out = Append(out, a); - out = Append(out, b); - assert(out == buf + buf_size); - return buf_size; - }); + std::string::size_type old_size = dest->size(); + STLStringAppendUninitializedAmortized(dest, a.size() + b.size()); + char* const begin = &(*dest)[0]; + char* out = begin + old_size; + out = Append(out, a); + out = Append(out, b); + assert(out == begin + dest->size()); } void StrAppend(std::string* absl_nonnull dest, const AlphaNum& a, @@ -212,16 +215,14 @@ ASSERT_NO_OVERLAP(*dest, a); ASSERT_NO_OVERLAP(*dest, b); ASSERT_NO_OVERLAP(*dest, c); - strings_internal::StringAppendAndOverwrite( - *dest, a.size() + b.size() + c.size(), - [&a, &b, &c](char* const buf, size_t buf_size) { - char* out = buf; - out = Append(out, a); - out = Append(out, b); - out = Append(out, c); - assert(out == buf + buf_size); - return buf_size; - }); + std::string::size_type old_size = dest->size(); + STLStringAppendUninitializedAmortized(dest, a.size() + b.size() + c.size()); + char* const begin = &(*dest)[0]; + char* out = begin + old_size; + out = Append(out, a); + out = Append(out, b); + out = Append(out, c); + assert(out == begin + dest->size()); } void StrAppend(std::string* absl_nonnull dest, const AlphaNum& a, @@ -230,17 +231,16 @@ ASSERT_NO_OVERLAP(*dest, b); ASSERT_NO_OVERLAP(*dest, c); ASSERT_NO_OVERLAP(*dest, d); - strings_internal::StringAppendAndOverwrite( - *dest, a.size() + b.size() + c.size() + d.size(), - [&a, &b, &c, &d](char* const buf, size_t buf_size) { - char* out = buf; - out = Append(out, a); - out = Append(out, b); - out = Append(out, c); - out = Append(out, d); - assert(out == buf + buf_size); - return buf_size; - }); + std::string::size_type old_size = dest->size(); + STLStringAppendUninitializedAmortized( + dest, a.size() + b.size() + c.size() + d.size()); + char* const begin = &(*dest)[0]; + char* out = begin + old_size; + out = Append(out, a); + out = Append(out, b); + out = Append(out, c); + out = Append(out, d); + assert(out == begin + dest->size()); } ABSL_NAMESPACE_END
diff --git a/absl/strings/substitute.cc b/absl/strings/substitute.cc index f5d600b..3c2ca5d 100644 --- a/absl/strings/substitute.cc +++ b/absl/strings/substitute.cc
@@ -26,7 +26,7 @@ #include "absl/base/nullability.h" #include "absl/strings/ascii.h" #include "absl/strings/escaping.h" -#include "absl/strings/internal/append_and_overwrite.h" +#include "absl/strings/internal/resize_uninitialized.h" #include "absl/strings/numbers.h" #include "absl/strings/str_cat.h" #include "absl/strings/string_view.h" @@ -85,29 +85,29 @@ if (size == 0) return; // Build the string. - ABSL_INTERNAL_CHECK(size <= output->max_size() - output->size(), - "Exceeds std::string::max_size()"); - strings_internal::StringAppendAndOverwrite( - *output, size, [format, args_array](char* const buf, size_t buf_size) { - char* target = buf; - for (size_t i = 0; i < format.size(); i++) { - if (format[i] == '$') { - if (absl::ascii_isdigit( - static_cast<unsigned char>(format[i + 1]))) { - const absl::string_view src = args_array[format[i + 1] - '0']; - target = std::copy(src.begin(), src.end(), target); - ++i; // Skip next char. - } else if (format[i + 1] == '$') { - *target++ = '$'; - ++i; // Skip next char. - } - } else { - *target++ = format[i]; - } - } - assert(target == buf + buf_size); - return buf_size; - }); + size_t original_size = output->size(); + ABSL_INTERNAL_CHECK( + size <= std::numeric_limits<size_t>::max() - original_size, + "size_t overflow"); + strings_internal::STLStringResizeUninitializedAmortized(output, + original_size + size); + char* target = &(*output)[original_size]; + for (size_t i = 0; i < format.size(); i++) { + if (format[i] == '$') { + if (absl::ascii_isdigit(static_cast<unsigned char>(format[i + 1]))) { + const absl::string_view src = args_array[format[i + 1] - '0']; + target = std::copy(src.begin(), src.end(), target); + ++i; // Skip next char. + } else if (format[i + 1] == '$') { + *target++ = '$'; + ++i; // Skip next char. + } + } else { + *target++ = format[i]; + } + } + + assert(target == output->data() + output->size()); } Arg::Arg(const void* absl_nullable value) {