/src/abseil-cpp/absl/strings/internal/append_and_overwrite.h

Source
// 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/internal/throw_delegate.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) {
  if (ABSL_PREDICT_FALSE(append_n > str.max_size() - str.size())) {
    absl::base_internal::ThrowStdLengthError(
        "absl::strings_internal::StringAppendAndOverwrite");
  }

  auto old_size = str.size();
  auto resize = old_size + append_n;

  if (resize > str.capacity()) {
    // Make sure to always grow by at least a factor of 2x.
    const auto min_growth = str.capacity();
    if (ABSL_PREDICT_FALSE(str.capacity() > str.max_size() - min_growth)) {
      resize = str.max_size();
    } else if (resize < str.capacity() + min_growth) {
      resize = str.capacity() + min_growth;
    }
  } else {
    resize = str.capacity();
  }

  // Avoid calling StringResizeAndOverwrite() here since it does an MSAN
  // verification on the entire string. StringResizeAndOverwriteImpl() is
  // StringResizeAndOverwrite() without the MSAN verification.
  StringResizeAndOverwriteImpl(
      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;
      });

#if defined(ABSL_HAVE_MEMORY_SANITIZER)
  // Only check the region appended to. Checking the entire string would cause
  // pathological quadratic verfication on repeated small appends.
  __msan_check_mem_is_initialized(str.data() + old_size, str.size() - old_size);
#endif
}

}  // namespace strings_internal
ABSL_NAMESPACE_END
}  // namespace absl


#endif  // ABSL_STRINGS_INTERNAL_APPEND_AND_OVERWRITE_H_

Line	Count	Source
1		// Copyright 2025 The Abseil Authors
2		//
3		// Licensed under the Apache License, Version 2.0 (the "License");
4		// you may not use this file except in compliance with the License.
5		// You may obtain a copy of the License at
6		//
7		// https://www.apache.org/licenses/LICENSE-2.0
8		//
9		// Unless required by applicable law or agreed to in writing, software
10		// distributed under the License is distributed on an "AS IS" BASIS,
11		// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12		// See the License for the specific language governing permissions and
13		// limitations under the License.
14
15		#ifndef ABSL_STRINGS_INTERNAL_APPEND_AND_OVERWRITE_H_
16		#define ABSL_STRINGS_INTERNAL_APPEND_AND_OVERWRITE_H_
17
18		#include "absl/base/config.h"
19		#include "absl/base/internal/throw_delegate.h"
20		#include "absl/base/macros.h"
21		#include "absl/base/optimization.h"
22		#include "absl/strings/resize_and_overwrite.h"
23
24		namespace absl {
25		ABSL_NAMESPACE_BEGIN
26		namespace strings_internal {
27
28		// An internal-only variant similar to `absl::StringResizeAndOverwrite()`
29		// optimized for repeated appends to a string that uses exponential growth so
30		// that the amortized complexity of increasing the string size by a small amount
31		// is O(1), in contrast to O(str.size()) in the case of precise growth. Use of
32		// this function is subtle; see https://reviews.llvm.org/D102727 to understand
33		// the tradeoffs.
34		//
35		// Appends at most `append_n` characters to `str`, using the user-provided
36		// operation `append_op` to modify the possibly indeterminate
37		// contents. `append_op` must return the length of the buffer appended to `str`.
38		//
39		// Invalidates all iterators, pointers, and references into `str`, regardless
40		// of whether reallocation occurs.
41		//
42		// `append_op(value_type* buf, size_t buf_size)` is allowed to write
43		// `value_type{}` to `buf[buf_size]`, which facilitiates interoperation with
44		// functions that write a trailing NUL.
45		template <typename T, typename Op>
46		void StringAppendAndOverwrite(T& str, typename T::size_type append_n,
47	0	Op append_op) {
48	0	if (ABSL_PREDICT_FALSE(append_n > str.max_size() - str.size())) {
49	0	absl::base_internal::ThrowStdLengthError(
50	0	"absl::strings_internal::StringAppendAndOverwrite");
51	0	}
52
53	0	auto old_size = str.size();
54	0	auto resize = old_size + append_n;
55
56	0	if (resize > str.capacity()) {
57		// Make sure to always grow by at least a factor of 2x.
58	0	const auto min_growth = str.capacity();
59	0	if (ABSL_PREDICT_FALSE(str.capacity() > str.max_size() - min_growth)) {
60	0	resize = str.max_size();
61	0	} else if (resize < str.capacity() + min_growth) {
62	0	resize = str.capacity() + min_growth;
63	0	}
64	0	} else {
65	0	resize = str.capacity();
66	0	}
67
68		// Avoid calling StringResizeAndOverwrite() here since it does an MSAN
69		// verification on the entire string. StringResizeAndOverwriteImpl() is
70		// StringResizeAndOverwrite() without the MSAN verification.
71	0	StringResizeAndOverwriteImpl(
72	0	str, resize,
73	0	[old_size, append_n, do_append = std::move(append_op)](
74	0	typename T::value_type* data_ptr, typename T::size_type) mutable {
75	0	auto num_appended =
76	0	std::move(do_append)(data_ptr + old_size, append_n);
77	0	ABSL_HARDENING_ASSERT(num_appended >= 0 && num_appended <= append_n); Unexecuted instantiation: str_cat.cc:absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::strings_internal::AppendPieces(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::initializer_list<std::__1::basic_string_view<char, std::__1::char_traits<char> > >)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::strings_internal::AppendPieces(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::initializer_list<std::__1::basic_string_view<char, std::__1::char_traits<char> > >)::$_0)::{lambda(char, unsigned long)#1}::operator()(char, unsigned long)::{lambda()#1}::operator()() const Unexecuted instantiation: str_cat.cc:absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&)::$_0)::{lambda(char, unsigned long)#1}::operator()(char, unsigned long)::{lambda()#1}::operator()() const Unexecuted instantiation: str_cat.cc:absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&)::$_0)::{lambda(char, unsigned long)#1}::operator()(char, unsigned long)::{lambda()#1}::operator()() const Unexecuted instantiation: str_cat.cc:absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0)::{lambda(char, unsigned long)#1}::operator()(char, unsigned long)::{lambda()#1}::operator()() const Unexecuted instantiation: str_cat.cc:absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0)::{lambda(char, unsigned long)#1}::operator()(char, unsigned long)::{lambda()#1}::operator()() const
78	0	return old_size + num_appended;
79	0	}); Unexecuted instantiation: str_cat.cc:absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::strings_internal::AppendPieces(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::initializer_list<std::__1::basic_string_view<char, std::__1::char_traits<char> > >)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::strings_internal::AppendPieces(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::initializer_list<std::__1::basic_string_view<char, std::__1::char_traits<char> > >)::$_0)::{lambda(char, unsigned long)#1}::operator()(char, unsigned long) Unexecuted instantiation: str_cat.cc:absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&)::$_0)::{lambda(char, unsigned long)#1}::operator()(char, unsigned long) Unexecuted instantiation: str_cat.cc:absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&)::$_0)::{lambda(char, unsigned long)#1}::operator()(char, unsigned long) Unexecuted instantiation: str_cat.cc:absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0)::{lambda(char, unsigned long)#1}::operator()(char, unsigned long) Unexecuted instantiation: str_cat.cc:absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0)::{lambda(char, unsigned long)#1}::operator()(char, unsigned long)
80
81		#if defined(ABSL_HAVE_MEMORY_SANITIZER)
82		// Only check the region appended to. Checking the entire string would cause
83		// pathological quadratic verfication on repeated small appends.
84		__msan_check_mem_is_initialized(str.data() + old_size, str.size() - old_size);
85		#endif
86	0	} Unexecuted instantiation: str_cat.cc:void absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::strings_internal::AppendPieces(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::initializer_list<std::__1::basic_string_view<char, std::__1::char_traits<char> > >)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::strings_internal::AppendPieces(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::initializer_list<std::__1::basic_string_view<char, std::__1::char_traits<char> > >)::$_0) Unexecuted instantiation: str_cat.cc:void absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&)::$_0) Unexecuted instantiation: str_cat.cc:void absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&)::$_0) Unexecuted instantiation: str_cat.cc:void absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0) Unexecuted instantiation: str_cat.cc:void absl::strings_internal::StringAppendAndOverwrite<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0>(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::size_type, absl::StrAppend(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&, absl::AlphaNum const&)::$_0)
87
88		} // namespace strings_internal
89		ABSL_NAMESPACE_END
90		} // namespace absl
91
92
93		#endif // ABSL_STRINGS_INTERNAL_APPEND_AND_OVERWRITE_H_

Coverage Report

Created: 2025-11-15 06:18