[libc++][format] Removes vector dependency.

[Mordante]

Summary

During the review of D140653 it was suggested to use vector in
__retarget_buffer instead of manually managing the memory. Due to the
requirements of the Standard it turns out format needs to include vector
leading to a cycle. Therefore switching back to manual memory
management.

This is a preparation to fix https://llvm.org/PR61314

[philnik]

Do you plan to move this back to vector, or is this a permanent change? If this is permanent, could you maybe elaborate a bit on the exact cycle this creates, and why this can't be resolved by moving the code around a bit?

libcxx/include/__format/buffer.h

554

Why the #ifdef? __allocate_at_least was specifically designed to be able to write auto __alloc_result = std::__allocate_at_least(...). (Although, thinking about it we should just have a converting constructor from allocation_result)

[ldionne]

In D148826#4290117, @philnik wrote:

Do you plan to move this back to vector, or is this a permanent change? If this is permanent, could you maybe elaborate a bit on the exact cycle this creates, and why this can't be resolved by moving the code around a bit?

Mark tried to split <vector> into vector<T> and vector<bool> in another revision I don't have handy right now, and we decided not to go down that route.

libcxx/include/__format/buffer.h

567

A bit subtle otherwise.

594–595

Could you confirm that for char, std::uninitialized_default_construct_n(__ptr_ + __size_, __n); is optimized out?

615–619

Same comment, personally I think auto __result = std::__allocate_at_least(__alloc_, __capacity); would be better, since this is not ABI-sensitive.

If we don't feel comfortable using this trick, then we should change how we designed __allocate_at_least.

620

If this line somehow throws, we'll leak the allocation result above. This is definitely a nitpick cause it should never throw, I guess (those are characters).

I won't feel strongly if you don't think it's worth addressing, however if you do want to address it, I think we could try to modify __allocation_guard so that it plays nicely with __allocate_at_least.

[philnik]

libcxx/include/__format/buffer.h

615–619

P2652R2 changed the interface anyways, so we might as well update it then.

[Mordante]

Addresses review comments.

[Mordante]

Thanks for the reviews!

libcxx/include/__format/buffer.h

554

Changed to this version.

594–595

I verified it -O1 suffices https://godbolt.org/z/Ex5cafPfY

620

I do not really like to modify the __allocation_guard IMO we have an ___exception_guard which can do the same without additional effort. (In fact it seems __allocation_guard is only used once.

This too is optimized away https://godbolt.org/z/c71GzE63o so I added it.

[Mordante]

Trigger CI.

[Mordante]

Trigger CI.

[Mordante]

Rebased and updated transitive includes.

[Mordante]

CI fixes.

libcxx/include/__format/buffer.h

 #include <__format/enable_insertable.h>
 #include <__format/format_to_n_result.h>
 #include <__iterator/back_insert_iterator.h>
 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/wrap_iter.h>
 #include <__memory/addressof.h>
+#include <__memory/allocate_at_least.h>
+#include <__memory/allocator_traits.h>
+#include <__memory/construct_at.h>
+#include <__memory/ranges_construct_at.h>
+#include <__memory/uninitialized_algorithms.h>
 #include <__type_traits/add_pointer.h>
 #include <__type_traits/conditional.h>
+#include <__utility/exception_guard.h>
 #include <__utility/move.h>
 #include <cstddef>
 #include <string_view>
-#include <vector>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

 // buffer and that buffer is formatted as a string.
 //
 // There is an issue with that approach, the format context used in
 // std::formatter<T>::format contains the output iterator used as part of its
 // type. So using this output iterator means there needs to be a new format
 // context and the format arguments need to be retargeted to the new context.
 // This retargeting is done by a basic_format_context specialized for the
 // __iterator of this container.
+//
+// This class uses its own buffer management, since using vector
+// would lead to a circular include with formatter for vector<bool>.
 template <__fmt_char_type _CharT>
 class _LIBCPP_TEMPLATE_VIS __retarget_buffer {
+  using _Alloc = allocator<_CharT>;
+
 public:
   using value_type = _CharT;
 
   struct __iterator {
     using difference_type = ptrdiff_t;
 
     _LIBCPP_HIDE_FROM_ABI constexpr explicit __iterator(__retarget_buffer& __buffer)
         : __buffer_(std::addressof(__buffer)) {}
     _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator=(const _CharT& __c) {
       __buffer_->push_back(__c);
       return *this;
     }
     _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator=(_CharT&& __c) {
       __buffer_->push_back(__c);
       return *this;
     }
 
     _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator*() { return *this; }
     _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() { return *this; }
     _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) { return *this; }
     __retarget_buffer* __buffer_;
   };
 
-  _LIBCPP_HIDE_FROM_ABI explicit __retarget_buffer(size_t __size_hint) { __buffer_.reserve(__size_hint); }
+  __retarget_buffer(const __retarget_buffer&)            = delete;
+  __retarget_buffer& operator=(const __retarget_buffer&) = delete;
+
+  _LIBCPP_HIDE_FROM_ABI explicit __retarget_buffer(size_t __size_hint) {
+    auto __result = std::__allocate_at_least(__alloc_, __size_hint ? __size_hint : 256 / sizeof(_CharT));
+    __ptr_        = __result.ptr;
+    __capacity_   = __result.count;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI ~__retarget_buffer() {
+    ranges::destroy_n(__ptr_, __size_);
+    allocator_traits<_Alloc>::deallocate(__alloc_, __ptr_, __capacity_);
+  }
 
   _LIBCPP_HIDE_FROM_ABI __iterator __make_output_iterator() { return __iterator{*this}; }
 
-  _LIBCPP_HIDE_FROM_ABI void push_back(_CharT __c) { __buffer_.push_back(__c); }
+  _LIBCPP_HIDE_FROM_ABI void push_back(_CharT __c) {
+    std::construct_at(__ptr_ + __size_, __c);
+    ++__size_;
+
+    if (__size_ == __capacity_)
+      __grow_buffer();
+  }
 
   template <__fmt_char_type _InCharT>
   _LIBCPP_HIDE_FROM_ABI void __copy(basic_string_view<_InCharT> __str) {
-    __buffer_.insert(__buffer_.end(), __str.begin(), __str.end());
+    size_t __n = __str.size();
+    if (__size_ + __n >= __capacity_)
+      // Push_back requires the buffer to have room for at least one character.
+      __grow_buffer(__size_ + __n + 1);
+
+    std::uninitialized_copy_n(__str.data(), __n, __ptr_ + __size_);
+    __size_ += __n;
   }
 
   template <__fmt_char_type _InCharT, class _UnaryOperation>
   _LIBCPP_HIDE_FROM_ABI void __transform(const _InCharT* __first, const _InCharT* __last, _UnaryOperation __operation) {
     _LIBCPP_ASSERT(__first <= __last, "not a valid range");
-    std::transform(__first, __last, std::back_inserter(__buffer_), std::move(__operation));
+
+    size_t __n = static_cast<size_t>(__last - __first);
+    if (__size_ + __n >= __capacity_)
+      // Push_back requires the buffer to have room for at least one character.
+      __grow_buffer(__size_ + __n + 1);
+
+    std::uninitialized_default_construct_n(__ptr_ + __size_, __n);
+    std::transform(__first, __last, __ptr_ + __size_, std::move(__operation));
+    __size_ += __n;
   }
 
-  _LIBCPP_HIDE_FROM_ABI void __fill(size_t __n, _CharT __value) { __buffer_.insert(__buffer_.end(), __n, __value); }
+  _LIBCPP_HIDE_FROM_ABI void __fill(size_t __n, _CharT __value) {
+    if (__size_ + __n >= __capacity_)
+      // Push_back requires the buffer to have room for at least one character.
+      __grow_buffer(__size_ + __n + 1);
 
-  _LIBCPP_HIDE_FROM_ABI basic_string_view<_CharT> __view() { return {__buffer_.data(), __buffer_.size()}; }
+    std::uninitialized_fill_n(__ptr_ + __size_, __n, __value);
+    __size_ += __n;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI basic_string_view<_CharT> __view() { return {__ptr_, __size_}; }
 
 private:
-  // Use vector instead of string to avoid adding zeros after every append
-  // operation. The buffer is exposed as a string_view and not as a c-string.
-  vector<_CharT> __buffer_;
+  _LIBCPP_HIDE_FROM_ABI void __grow_buffer() { __grow_buffer(__capacity_ * 1.6); }
+
+  _LIBCPP_HIDE_FROM_ABI void __grow_buffer(size_t __capacity) {
+    _LIBCPP_ASSERT(__capacity > __capacity_, "the buffer must grow");
+    auto __result = std::__allocate_at_least(__alloc_, __capacity);
+    auto __guard  = std::__make_exception_guard([&] {
+      allocator_traits<_Alloc>::deallocate(__alloc_, __result.ptr, __result.count);
+    });
+    // This shouldn't throw, but just to be safe. Not that at -O1 this
+    // guard is optimized away so there is no runtime overhead.
+    std::uninitialized_move_n(__ptr_, __size_, __result.ptr);
+    __guard.__complete();
+    ranges::destroy_n(__ptr_, __size_);
+    allocator_traits<_Alloc>::deallocate(__alloc_, __ptr_, __capacity_);
+
+    __ptr_      = __result.ptr;
+    __capacity_ = __result.count;
+  }
+  _LIBCPP_NO_UNIQUE_ADDRESS _Alloc __alloc_;
+  _CharT* __ptr_;
+  size_t __capacity_;
+  size_t __size_{0};
 };
 
 } // namespace __format
 
 #endif //_LIBCPP_STD_VER >= 20
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___FORMAT_BUFFER_H

libcxx/test/libcxx/transitive_includes/cxx03.csv

 format locale
 format optional
 format queue
 format stack
 format stdexcept
 format string
 format string_view
 format tuple
-format vector
 format version
 forward_list algorithm
 forward_list atomic
 forward_list compare
 forward_list concepts
 forward_list cstddef
 forward_list cstdint
 forward_list cstdlib

 thread new
 thread ratio
 thread stdexcept
 thread string
 thread string_view
 thread system_error
 thread tuple
 thread type_traits
-thread vector
 thread version
 tuple compare
 tuple cstddef
 tuple exception
 tuple iosfwd
 tuple new
 tuple type_traits
 tuple typeinfo

libcxx/test/libcxx/transitive_includes/cxx11.csv

 format locale
 format optional
 format queue
 format stack
 format stdexcept
 format string
 format string_view
 format tuple
-format vector
 format version
 forward_list algorithm
 forward_list atomic
 forward_list compare
 forward_list concepts
 forward_list cstddef
 forward_list cstdint
 forward_list cstdlib

 thread new
 thread ratio
 thread stdexcept
 thread string
 thread string_view
 thread system_error
 thread tuple
 thread type_traits
-thread vector
 thread version
 tuple compare
 tuple cstddef
 tuple exception
 tuple iosfwd
 tuple new
 tuple type_traits
 tuple typeinfo

libcxx/test/libcxx/transitive_includes/cxx14.csv

 format locale
 format optional
 format queue
 format stack
 format stdexcept
 format string
 format string_view
 format tuple
-format vector
 format version
 forward_list algorithm
 forward_list atomic
 forward_list compare
 forward_list concepts
 forward_list cstddef
 forward_list cstdint
 forward_list cstdlib

 thread new
 thread ratio
 thread stdexcept
 thread string
 thread string_view
 thread system_error
 thread tuple
 thread type_traits
-thread vector
 thread version
 tuple compare
 tuple cstddef
 tuple exception
 tuple iosfwd
 tuple new
 tuple type_traits
 tuple typeinfo

libcxx/test/libcxx/transitive_includes/cxx17.csv

 format locale
 format optional
 format queue
 format stack
 format stdexcept
 format string
 format string_view
 format tuple
-format vector
 format version
 forward_list algorithm
 forward_list atomic
 forward_list compare
 forward_list concepts
 forward_list cstddef
 forward_list cstdint
 forward_list cstdlib

 thread new
 thread ratio
 thread stdexcept
 thread string
 thread string_view
 thread system_error
 thread tuple
 thread type_traits
-thread vector
 thread version
 tuple compare
 tuple cstddef
 tuple exception
 tuple iosfwd
 tuple new
 tuple type_traits
 tuple typeinfo

libcxx/test/libcxx/transitive_includes/cxx20.csv

 chrono ostream
 chrono ratio
 chrono sstream
 chrono stdexcept
 chrono string
 chrono string_view
 chrono tuple
 chrono type_traits
-chrono vector
 chrono version
 cinttypes cstdint
 cmath type_traits
 cmath version
 codecvt atomic
 codecvt cctype
 codecvt clocale
 codecvt concepts

 format locale
 format optional
 format queue
 format stack
 format stdexcept
 format string
 format string_view
 format tuple
-format vector
 format version
 forward_list algorithm
 forward_list atomic
 forward_list compare
 forward_list concepts
 forward_list cstddef
 forward_list cstdint
 forward_list cstdlib

 thread new
 thread ratio
 thread stdexcept
 thread string
 thread string_view
 thread system_error
 thread tuple
 thread type_traits
-thread vector
 thread version
 tuple compare
 tuple cstddef
 tuple exception
 tuple iosfwd
 tuple new
 tuple type_traits
 tuple typeinfo

libcxx/test/libcxx/transitive_includes/cxx2b.csv

 chrono compare
 chrono cstddef
 chrono cstdint
 chrono cstdlib
 chrono ctime
 chrono initializer_list
 chrono limits
 chrono locale
+chrono new
 chrono optional
 chrono ostream
 chrono ratio
 chrono sstream
 chrono stdexcept
 chrono string
 chrono string_view
 chrono tuple
-chrono vector
 chrono version
 cinttypes cstdint
 cmath version
 codecvt cctype
 codecvt clocale
 codecvt cstddef
 codecvt cstdint
 codecvt cstdlib

 format array
 format cmath
 format cstddef
 format cstdint
 format cstdlib
 format initializer_list
 format limits
 format locale
+format new
 format optional
 format queue
 format stack
 format stdexcept
 format string
 format string_view
 format tuple
-format vector
 format version
 forward_list compare
 forward_list cstddef
 forward_list cstdint
 forward_list cstring
 forward_list initializer_list
 forward_list limits
 forward_list new

 thread compare
 thread cstddef
 thread cstdint
 thread cstdlib
 thread ctime
 thread iosfwd
 thread limits
 thread locale
+thread new
 thread ratio
 thread stdexcept
 thread string
 thread string_view
 thread tuple
-thread vector
 thread version
 tuple compare
 tuple cstddef
 tuple version
 type_traits cstddef
 type_traits cstdint
 type_traits version
 typeindex compare