[libc++][format][3/6] Adds a __container_buffer.

[Mordante]

Summary

Instead of writing every character directly into the container by using
a back_insert_iterator the data is buffered in an array. This buffer
is then inserted to the container by calling its insert member function.

Since there's no guarantee every container's insert behaves properly
containers need to opt-in to this behaviour. The appropriate standard
containers opt-in to this behaviour.

This change improves the performance of the format functions that use a
back_insert_iterator.

Depends on D110495

[Mordante]

Attempt to fix Clang-11 build issue.

[• Quuxplusone]

libcxx/include/__format/buffer.h

109

The machinery to __enable_insertable in a container right now is like 16 lines. You could get it down to 1 line, and no helper headers, and C++11-compatible, if you changed this to

is_same_v<_Container, typename _Container::__enable_format_insertable>

Then the containers (vector, deque, string, list, etc.) would just have to say e.g.

using __enable_format_insertable = vector<_Tp, _Alloc>;

without any extra headers or ifdef-guards or anything.

112

add_pointer_t<typename _Container::value_type> is invariably typename _Container::value_type*, right?

117–139

Rather than lines 129-140, I suggest that you add a member function container_type *back_insert_iterator::__get_container() const to libc++'s back_insert_iterator.
I suppose you still need a partial-specialization-based approach equivalent to lines 117-127, in order to tell you whether the user's iterator type is exactly back_insert_iterator (in which case this optimization is safe) or merely something that slices to back_insert_iterator (in which case this optimization is dubious). But once you know it's exactly back_insert_iterator, you can just ask for its container_type member typedef, and use your new member function to get a pointer to the container; you don't have to use tricks for that part.

171

Why not _CharT __buffer_[__buffer_size];? (What does the std::array dependency buy you? and the zero-initialization?)

libcxx/include/module.modulemap

442

/intertable/insertable/

[Mordante]

Needs to be updated due to the removal of __put in D110495.

[Mordante]

libcxx/include/__format/buffer.h

109

Thanks for the suggestion, this indeed is a lot less intrusive.

117–139

See D110573.

171

I prefer an array just for convenience. I need to know the last element and I like it better to use end().
The zero-initialization isn't needed.

libcxx/include/module.modulemap

442

This is no longer needed due to your earlier suggestions.

[Mordante]

Addresses the review comments.
Temporary include the used part of D110573 to avoid possible Buildkite dependency issues.

[• Quuxplusone]

I think it's up to @ldionne and/or @vitaut to say whether this PR is ultimately a good tradeoff, complexity-and-performance-wise. IMHO we've successfully reached the local optimum, code-wise. :)

libcxx/include/__format/buffer.h

160

Style nit: _CharT* __buffer_it_ = __buffer_.begin(); is easier to read, and equivalent. Could even say __buffer_.data() and then I wouldn't need to consciously avoid looking up on cppreference whether array::iterator is guaranteed to be _CharT*. ;)

libcxx/include/list

868

Style nit: _Tp, _Alloc with a space

libcxx/test/libcxx/utilities/format/enable_insertable.compile.pass.cpp

30–52

FWIW, I think it is not useful to test no_value_type, no_end, or no_insert, because we don't permit users to define such types and we don't expect to define any such types ourselves. Seeing a correct "specialization" of __enable_format_insertable should be enough to indicate that the type author intends the type to be insertable. If it's somehow not insertable, then that's a serious show-stopping bug in the type, not something that <format> should be silently working-around.

69

Also test

struct UserVector : public std::vector<char> {
    using std::vector<char>::vector;
};
static_assert(!std::__format::__insertable<UserVector>);

This is important to test because users are allowed to do stupid things like this. (They shouldn't; it's bad style and has many downsides; but they are allowed to.)

94

What do you expect to happen for std::vector<int> or std::vector<std::string>? On the one hand, int and string are not "char types," right? But on the other hand, vec.insert(vec.end(), charptr, charendptr) will work as expected, so we do want to do the optimization, right?

[Mordante]

Thanks for the feedback, I'll look at these issues when Buildkite is working properly again.

libcxx/test/libcxx/utilities/format/enable_insertable.compile.pass.cpp

94

The format specific functions require a char or wchar_t. So I expect them not to pass this trait. When we want to use this more generic, we can add an std::__insertable and rename the typedef in the containers. I didn't restrain the typedef in the classes; I looked at it but it became quite ugly quite fast. Instead it's constrained in the std::__format::__insertable concept. So it would be quite trivial to add std::__insertable, but I don't have a usecase for it.

[Mordante]

Addresses review comments.

libcxx/include/__format/buffer.h

160

I prefer the begin() since that conveys the intended usage better.

libcxx/include/list

868

Interesting clang-format didn't catch that for me.

libcxx/test/libcxx/utilities/format/enable_insertable.compile.pass.cpp

30–52

I not entirely convinced that removing them is a good idea. I'd like to hear @ldionne's opinion.

[Mordante]

Rebased to test with wchar_t changes.

[Mordante]

Fixes wide char build.

[vitaut]

Since there's no guarantee every container's insert behaves properly

What does behaving properly mean? Could you give an example of a container's insert that doesn't behave properly?

libcxx/include/__format/buffer.h

104

replace -> replaced

106

opt-in to -> "opt in to" or "opt into"

[vitaut]

Character-by-character output, especially type erased one introduced in D110494 doesn't seem efficient. As commented on the the previous diff the buffer and corresponding output iterator should provide access to a contiguous buffer and type erase the reallocation, not character output.

[• Quuxplusone]

Character by character output doesn't seem efficient

Right, IIUC, this would end up rebased on top of D112361 or the like.

libcxx/include/__format/buffer.h

106

In D110497#3098970, @vitaut wrote:

Since there's no guarantee every container's insert behaves properly

What does behaving properly mean? Could you give an example of a container's insert that doesn't behave properly?

User-defined containers can make their insert do arbitrary things, e.g.

struct Evil : std::string {
    void insert(std::string::iterator, char *, char *) { /*no-op*/ }
};
Evil e;
auto evil_it = std::back_inserter(e);  // uses e.push_back, which is fine

(Serendipitously, Charlie Barto, of the MSVC STL, also mentioned the need to guard against this possibility in his CppCon talk "Why does std::format do that?" on Thursday. https://cppcon.digital-medium.co.uk/thursday-recordings/ )

[vitaut]

libcxx/include/__format/buffer.h

106

Makes sense, thanks for clarifying.

[Mordante]

In D110497#3098973, @vitaut wrote:

Character-by-character output, especially type erased one introduced in D110494 doesn't seem efficient. As commented on the the previous diff the buffer and corresponding output iterator should provide access to a contiguous buffer and type erase the reallocation, not character output.

Yes I first want to get a good solution in D112361 and then update this patch with these changes.

libcxx/include/__format/buffer.h

106

In D110497#3098970, @vitaut wrote:

Since there's no guarantee every container's insert behaves properly

What does behaving properly mean? Could you give an example of a container's insert that doesn't behave properly?

User-defined containers can make their insert do arbitrary things, e.g.

struct Evil : std::string {
    void insert(std::string::iterator, char *, char *) { /*no-op*/ }
};
Evil e;
auto evil_it = std::back_inserter(e);  // uses e.push_back, which is fine

(Serendipitously, Charlie Barto, of the MSVC STL, also mentioned the need to guard against this possibility in his CppCon talk "Why does std::format do that?" on Thursday. https://cppcon.digital-medium.co.uk/thursday-recordings/ )

Yes that's the reason, interesting to see Charlie did the same. I'm looking forward to watching this talk.

[Mordante]

Rebased and make changes based on D112361.
Addresses review comments.

[Mordante]

Rebased.

[Mordante]

Rebased tp trigger CI.

[vitaut]

Same as D110495:

As commented, I'm very skeptical about this approach because it has extra buffering for common cases but I defer to libc++ maintainers the decision whether they want to land this as is or optimize buffering now.

[ldionne]

libcxx/include/__format/buffer.h

90–97

Is there any reason why this isn't implemented as a bool variable template that containers specialize or something similar? IMO it would be nice to keep containers free of a __enable_format_insertable typedef used for this sole purpose.

Requiring a specialization also makes it slightly less likely that users are going to do it for their own containers, which IMO is a good thing (we really don't want users to start depending on this unless the Standard commits to providing this functionality).

[Reading some other comments, I get the feeling this might have been how it was implemented in previous diffs, please let me know if that's the case]

[Mordante]

libcxx/include/__format/buffer.h

90–97

That was my initial approach https://reviews.llvm.org/D110497?vs=on&id=375096#toc
when you too like that better I can switch back to that approach.

[Mordante]

Rebase and remove concepts guards.

[ldionne]

LGTM with a comment I'd like to see addressed, but I don't think I need to see this again. IIUC, @vitaut 's concern about character-by-character output has been resolved since this was rebased. We are still buffering too much to @vitaut 's liking, but @Mordante 's telling me that he'll investigate that in the future, before we ship this.

Also, this should be rebased onto the __get_container() patch.

libcxx/include/__format/buffer.h

90–97

Yeah, I think it would be better to have a less intrusive mechanism. We can specialize it for various containers in this header instead of having to touch vector & friends directly.

[Mordante]

libcxx/include/__format/buffer.h

90–97

In that case format pulls in several unrelated headers. In the original approach these container headers pull in one small header. So I think that's the better solution.

[Mordante]

• Rebased
• Updated to recent upstream cheanges
• Address review comments

[Mordante]

Forgot to format last patch.

[Mordante]

Fix a typo in the module map.

[Mordante]

Fix CI.

libcxx/include/CMakeLists.txt

set(files
   __concepts/same_as.h
   __concepts/semiregular.h
   __concepts/swappable.h
   __concepts/totally_ordered.h
   __config
   __debug
   __errc
   __format/buffer.h
+  __format/enable_insertable.h
   __format/format_arg.h
   __format/format_args.h
   __format/format_context.h
   __format/format_error.h
   __format/format_fwd.h
   __format/format_parse_context.h
   __format/format_string.h
   __format/formatter.h

libcxx/include/__format/buffer.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___FORMAT_BUFFER_H
 #define _LIBCPP___FORMAT_BUFFER_H
 
 #include <__config>
+#include <__format/enable_insertable.h>
 #include <__format/formatter.h> // for __char_type TODO FMT Move the concept?
+#include <__iterator/back_insert_iterator.h>
 #include <__iterator/concepts.h>
 #include <__utility/move.h>
+#include <array>
 #include <cstddef>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 

 ///
 /// This helper is specialized for all different output iterators used in the
 /// format function. Together with the @ref __output_iterator this offers a
 /// type erasure, reducing the number of formatter specializations.
 template <class _OutIt, __formatter::__char_type _CharT>
 requires(output_iterator<_OutIt, const _CharT&>) class _LIBCPP_TEMPLATE_VIS
     __iterator_wrapper_buffer {
 public:
   _LIBCPP_HIDE_FROM_ABI explicit __iterator_wrapper_buffer(_OutIt __it)
       : __it_(_VSTD::move(__it)) {}
 
   _LIBCPP_HIDE_FROM_ABI void put(_CharT __c) { *__it_++ = __c; }
 
   _LIBCPP_HIDE_FROM_ABI _OutIt out() { return __it_; }
 
 private:
   _OutIt __it_;
 };
 
+/// Concept to see whether a \a _Container is insertable.
+///
+/// The concept is used to validate whether multiple calls to a
+/// \ref back_insert_iterator can be replace by a call to \c _Container::insert.
+///
+/// \note a \a _Container needs to opt-in to the concept by specializing
+/// \ref __enable_insertable.
+template <class _Container>
+concept __insertable = __enable_insertable<_Container> &&
+    __formatter::__char_type<typename _Container::value_type> &&
+    requires(_Container& __t,
+             add_pointer_t<typename _Container::value_type> __first,
+             add_pointer_t<typename _Container::value_type> __last) {
+  __t.insert(__t.end(), __first, __last);
+};
+
+/// Extract the container type of a \ref back_insert_iterator.
+template <class _It>
+struct _LIBCPP_TEMPLATE_VIS __back_insert_iterator_container {
+  using type = void;
+};
+
+template <__insertable _Container>
+struct _LIBCPP_TEMPLATE_VIS
+    __back_insert_iterator_container<back_insert_iterator<_Container>> {
+  using type = _Container;
+};
+
+/// Helper to get the container of a \ref back_insert_iterator.
+template <class _Container>
+class _LIBCPP_TEMPLATE_VIS __container_extractor
+    : private back_insert_iterator<_Container> {
+public:
+  _LIBCPP_HIDE_FROM_ABI explicit __container_extractor(
+      back_insert_iterator<_Container> __it)
+      : back_insert_iterator<_Container>(__it) {}
+
+  _LIBCPP_HIDE_FROM_ABI _Container* get() { return this->container; }
+};
+
+/// A buffer that wraps a \ref back_insert_iterator for a \a _Container.
+template <class _Container>
+class _LIBCPP_TEMPLATE_VIS __container_buffer {
+public:
+  using _CharT = typename _Container::value_type;
+
+  _LIBCPP_HIDE_FROM_ABI explicit __container_buffer(
+      back_insert_iterator<_Container> __it)
+      : __container_(__container_extractor{__it}.get()) {}
+
+  _LIBCPP_HIDE_FROM_ABI void put(_CharT __c) {
+    *__buffer_it_++ = __c;
+    // Profiling showed flushing after adding is more efficient than flushing
+    // when entering the function.
+    if (__buffer_it_ == __buffer_.end())
+      __flush();
+  }
+
+  _LIBCPP_HIDE_FROM_ABI auto out() {
+    __flush();
+    return back_inserter(*__container_);
+  }
+
+private:
+  /// The size of the internal buffer.
+  ///
+  /// Profiling shows a 256 byte buffer seems optimal.
+  /// (256 elements for a char buffer and 64 elements for a 4-byte wchar_t)
+  static constexpr size_t __buffer_size = 256 / sizeof(_CharT);
+
+  array<_CharT, __buffer_size> __buffer_{};
+  _CharT* __buffer_it_{__buffer_.begin()};
+  _Container* __container_;
+
+  void __flush() {
+    // Use __buffer_it_ instead of end() since the buffer might be partly filled.
+    __container_->insert(__container_->end(), __buffer_.begin(), __buffer_it_);
+    __buffer_it_ = __buffer_.begin();
+  }
+};
+
+/// Selects the type of the buffer for the output iterator.
+template <class _OutIt, class _CharT>
+class _LIBCPP_TEMPLATE_VIS __buffer_selector {
+  using _Iterator = typename __back_insert_iterator_container<_OutIt>::type;
+
+public:
+  using type = conditional_t<same_as<_Iterator, void>,
+                             __iterator_wrapper_buffer<_OutIt, _CharT>,
+                             __container_buffer<_Iterator>>;
+};
+
 } // namespace __format
 
 #endif // !defined(_LIBCPP_HAS_NO_CONCEPTS)
 #endif //_LIBCPP_STD_VER > 17
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___FORMAT_BUFFER_H

libcxx/include/__format/enable_insertable.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___FORMAT_ENABLE_INSERTABLE_H
+#define _LIBCPP___FORMAT_ENABLE_INSERTABLE_H
+
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 17
+
+namespace __format {
+
+/// Opt-in to enable \ref __insertable for a \a _Container.
+template <class _Container>
+inline constexpr bool __enable_insertable = false;
+
+} // namespace __format
+
+#endif //_LIBCPP_STD_VER > 17
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___FORMAT_ENABLE_INSERTABLE_H

libcxx/include/deque

template <class T, class Allocator, class Predicate>
     erase_if(deque<T, Allocator>& c, Predicate pred);    // C++20
 
 }  // std
 
 */
 
 #include <__config>
 #include <__debug>
+#include <__format/enable_insertable.h>
 #include <__split_buffer>
 #include <__utility/forward.h>
 #include <algorithm>
 #include <compare>
 #include <initializer_list>
 #include <iterator>
 #include <limits>
 #include <stdexcept>

 
 template <class _Tp, class _Allocator, class _Predicate>
 inline _LIBCPP_INLINE_VISIBILITY typename deque<_Tp, _Allocator>::size_type
 erase_if(deque<_Tp, _Allocator>& __c, _Predicate __pred) {
   auto __old_size = __c.size();
   __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end());
   return __old_size - __c.size();
 }
+
+// TODO FMT Remove this once we require compilers with proper C++20 support.
+// If the compiler has no concepts support, the format header will be disabled.
+// Without concepts support enable_if needs to be used and that too much effort
+// to support compilers with partial C++20 support.
+# if !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
+template <>
+inline constexpr bool __format::__enable_insertable<std::deque<char>> = true;
+template <>
+inline constexpr bool __format::__enable_insertable<std::deque<wchar_t>> = true;
+
+# endif // !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
 #endif
 
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP_DEQUE

libcxx/include/format

 // Make sure all feature-test macros are available.
 #include <version>
 // Enable the contents of the header only when libc++ was built with LIBCXX_ENABLE_INCOMPLETE_FEATURES.
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_FORMAT)
 
 #include <__config>
 #include <__debug>
 #include <__format/buffer.h>
+#include <__format/enable_insertable.h>
 #include <__format/format_arg.h>
 #include <__format/format_args.h>
 #include <__format/format_context.h>
 #include <__format/format_error.h>
 #include <__format/format_fwd.h>
 #include <__format/format_parse_context.h>
 #include <__format/format_string.h>
 #include <__format/formatter.h>

 } // namespace __format
 
 template <class _OutIt, class _CharT, class _FormatOutIt>
 requires(output_iterator<_OutIt, const _CharT&>) _LIBCPP_HIDE_FROM_ABI _OutIt
     __vformat_to_wrapped(
         _OutIt __out_it, basic_string_view<_CharT> __fmt,
         basic_format_args<basic_format_context<_FormatOutIt, _CharT>> __args) {
 
-  using _Buffer = __format::__iterator_wrapper_buffer<_OutIt, _CharT>;
+  using _Buffer = typename __format::__buffer_selector<_OutIt, _CharT>::type;
   _Buffer __buffer{_VSTD::move(__out_it)};
   _VSTD::__format::__vformat_to(
       basic_format_parse_context{__fmt, __args.__size()},
       _VSTD::__format_context_create(
           _VSTD::__format::__output_iterator<_CharT>{
               &__format::__put<_Buffer, _CharT>, &__buffer},
           __args));
   return __buffer.out();

 #ifndef _LIBCPP_HAS_NO_LOCALIZATION
 
 template <class _OutIt, class _CharT, class _FormatOutIt>
 requires(output_iterator<_OutIt, const _CharT&>) _LIBCPP_HIDE_FROM_ABI _OutIt
     __vformat_to_wrapped(
         _OutIt __out_it, locale __loc, basic_string_view<_CharT> __fmt,
         basic_format_args<basic_format_context<_FormatOutIt, _CharT>> __args) {
 
-  using _Buffer = __format::__iterator_wrapper_buffer<_OutIt, _CharT>;
+  using _Buffer = typename __format::__buffer_selector<_OutIt, _CharT>::type;
   _Buffer __buffer{_VSTD::move(__out_it)};
   _VSTD::__format::__vformat_to(
       basic_format_parse_context{__fmt, __args.__size()},
       _VSTD::__format_context_create(
           _VSTD::__format::__output_iterator<_CharT>{
               &__format::__put<_Buffer, _CharT>, &__buffer},
           __args, _VSTD::move(__loc)));
   return __buffer.out();

libcxx/include/list

template <class T, class Allocator, class Predicate>
     erase_if(list<T, Allocator>& c, Predicate pred);    // C++20
 
 }  // std
 
 */
 
 #include <__config>
 #include <__debug>
+#include <__format/enable_insertable.h>
 #include <__utility/forward.h>
 #include <algorithm>
 #include <initializer_list>
 #include <iterator>
 #include <limits>
 #include <memory>
 #include <type_traits>
 #include <version>
public:
     typedef typename base::const_iterator            const_iterator;
     typedef _VSTD::reverse_iterator<iterator>         reverse_iterator;
     typedef _VSTD::reverse_iterator<const_iterator>   const_reverse_iterator;
 #if _LIBCPP_STD_VER > 17
     typedef size_type                                __remove_return_type;
 #else
     typedef void                                     __remove_return_type;
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     list()
         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
     {
 #if _LIBCPP_DEBUG_LEVEL == 2
         __get_db()->__insert_c(this);
 #endif
     }
erase_if(list<_Tp, _Allocator>& __c, _Predicate __pred) {
   return __c.remove_if(__pred);
 }
 
 template <class _Tp, class _Allocator, class _Up>
 inline _LIBCPP_INLINE_VISIBILITY typename list<_Tp, _Allocator>::size_type
 erase(list<_Tp, _Allocator>& __c, const _Up& __v) {
   return _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; });
 }
+
+// TODO FMT Remove this once we require compilers with proper C++20 support.
+// If the compiler has no concepts support, the format header will be disabled.
+// Without concepts support enable_if needs to be used and that too much effort
+// to support compilers with partial C++20 support.
+# if !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
+template <>
+inline constexpr bool __format::__enable_insertable<std::list<char>> = true;
+template <>
+inline constexpr bool __format::__enable_insertable<std::list<wchar_t>> = true;
+
+# endif // !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
 #endif
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP_LIST

libcxx/include/module.modulemap

module __format {
       module format_arg             { private header "__format/format_arg.h"           }
       module format_args            { private header "__format/format_args.h"          }
       module format_context {
         private header "__format/format_context.h"
         export optional
         export locale
       }
       module buffer                 { private header "__format/buffer.h"                 }
+      module enable_intertable      { private header "__format/enable_insertable.h"      }
       module format_error           { private header "__format/format_error.h"           }
       module format_fwd             { private header "__format/format_fwd.h"             }
       module format_parse_context   { private header "__format/format_parse_context.h"   }
       module format_string          { private header "__format/format_string.h"          }
       module formatter              { private header "__format/formatter.h"              }
       module formatter_bool         { private header "__format/formatter_bool.h"         }
       module formatter_char         { private header "__format/formatter_char.h"         }
       module formatter_integer      { private header "__format/formatter_integer.h"      }

libcxx/include/string

 
 }  // std
 
 */
 
 #include <__config>
 #include <__debug>
 #include <__functional_base>
+#include <__format/enable_insertable.h>
 #include <__iterator/wrap_iter.h>
 #include <algorithm>
 #include <compare>
 #include <cstdio>  // EOF
 #include <cstdlib>
 #include <cstring>
 #include <cwchar>
 #include <initializer_list>
#endif
     basic_string<char32_t> operator "" s( const char32_t *__str, size_t __len )
     {
         return basic_string<char32_t> (__str, __len);
     }
   }
 }
 #endif
 
+#if _LIBCPP_STD_VER > 17
+
+// TODO FMT Remove this once we require compilers with proper C++20 support.
+// If the compiler has no concepts support, the format header will be disabled.
+// Without concepts support enable_if needs to be used and that too much effort
+// to support compilers with partial C++20 support.
+# if !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
+template <>
+inline constexpr bool __format::__enable_insertable<std::basic_string<char>> = true;
+template <>
+inline constexpr bool __format::__enable_insertable<std::basic_string<wchar_t>> = true;
+
+# endif // !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
+#endif //_LIBCPP_STD_VER > 17
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP_STRING

libcxx/include/vector

 
 }  // std
 
 */
 
 #include <__config>
 #include <__bit_reference>
 #include <__debug>
+#include <__format/enable_insertable.h>
 #include <__functional_base>
 #include <__iterator/wrap_iter.h>
 #include <__split_buffer>
 #include <__utility/forward.h>
 #include <algorithm>
 #include <climits>
 #include <compare>
 #include <cstdlib>

 inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::size_type
 erase_if(vector<_Tp, _Allocator>& __c, _Predicate __pred) {
   auto __old_size = __c.size();
   __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end());
   return __old_size - __c.size();
 }
 #endif
 
+#if _LIBCPP_STD_VER > 17
+
+// TODO FMT Remove this once we require compilers with proper C++20 support.
+// If the compiler has no concepts support, the format header will be disabled.
+// Without concepts support enable_if needs to be used and that too much effort
+// to support compilers with partial C++20 support.
+# if !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
+template <>
+inline constexpr bool __format::__enable_insertable<std::vector<char>> = true;
+template <>
+inline constexpr bool __format::__enable_insertable<std::vector<wchar_t>> = true;
+
+# endif // !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
+#endif //_LIBCPP_STD_VER > 17
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP_VECTOR

libcxx/test/libcxx/diagnostics/detail.headers/format/enable_insertable.module.verify.cpp

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__format/enable_insertable.h'}}
+#include <__format/enable_insertable.h>

libcxx/test/libcxx/utilities/format/enable_insertable.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: libcpp-has-no-incomplete-format
+
+// <format>
+
+#include <format>
+#include <array>
+#include <deque>
+#include <forward_list>
+#include <list>
+#include <map>
+#include <queue>
+#include <set>
+#include <span>
+#include <stack>
+#include <string>
+#include <string_view>
+
+#include "test_macros.h"
+
+template <class CharT>
+struct no_value_type {
+  using iterator = CharT*;
+  iterator end();
+  void insert(iterator, CharT*, CharT*);
+};
+
+template <class CharT>
+struct no_end {
+  using value_type = CharT;
+  using iterator = CharT*;
+  void insert(iterator, CharT*, CharT*);
+};
+
+template <class CharT>
+struct no_insert {
+  using value_type = CharT;
+  using iterator = CharT*;
+  iterator end();
+};
+
+template <class CharT>
+struct no_specialization {
+  using value_type = CharT;
+  using iterator = CharT*;
+  iterator end();
+  void insert(iterator, CharT*, CharT*);
+};
+
+template <class CharT>
+struct valid {
+  using value_type = CharT;
+  using iterator = CharT*;
+  iterator end();
+  void insert(iterator, CharT*, CharT*);
+};
+
+namespace std::__format {
+template <>
+inline constexpr bool __enable_insertable<no_value_type<char>> = true;
+template <>
+inline constexpr bool __enable_insertable<no_value_type<wchar_t>> = true;
+template <>
+inline constexpr bool __enable_insertable<no_end<char>> = true;
+template <>
+inline constexpr bool __enable_insertable<no_end<wchar_t>> = true;
+template <>
+inline constexpr bool __enable_insertable<no_insert<char>> = true;
+template <>
+inline constexpr bool __enable_insertable<no_insert<wchar_t>> = true;
+template <>
+inline constexpr bool __enable_insertable<valid<char>> = true;
+template <>
+inline constexpr bool __enable_insertable<valid<wchar_t>> = true;
+} // namespace std::__format
+
+static_assert(!std::__format::__insertable<no_value_type<char>>);
+static_assert(!std::__format::__insertable<no_value_type<wchar_t>>);
+static_assert(!std::__format::__insertable<no_end<char>>);
+static_assert(!std::__format::__insertable<no_end<wchar_t>>);
+static_assert(!std::__format::__insertable<no_insert<char>>);
+static_assert(!std::__format::__insertable<no_insert<wchar_t>>);
+static_assert(!std::__format::__insertable<no_specialization<char>>);
+static_assert(!std::__format::__insertable<no_specialization<wchar_t>>);
+static_assert(std::__format::__insertable<valid<char>>);
+static_assert(std::__format::__insertable<valid<wchar_t>>);
+
+namespace std::__format {
+template <>
+inline constexpr bool __enable_insertable<valid<signed char>> = true;
+template <>
+inline constexpr bool __enable_insertable<valid<unsigned char>> = true;
+} // namespace std::__format
+
+static_assert(!std::__format::__insertable<valid<signed char>>);
+static_assert(!std::__format::__insertable<valid<unsigned char>>);
+
+static_assert(std::__format::__insertable<std::string>);
+static_assert(std::__format::__insertable<std::wstring>);
+static_assert(!std::__format::__insertable<std::string_view>);
+static_assert(!std::__format::__insertable<std::wstring_view>);
+
+static_assert(!std::__format::__insertable<std::array<char, 1>>);
+static_assert(!std::__format::__insertable<std::array<wchar_t, 1>>);
+
+static_assert(std::__format::__insertable<std::vector<char>>);
+static_assert(std::__format::__insertable<std::vector<wchar_t>>);
+static_assert(std::__format::__insertable<std::deque<char>>);
+static_assert(std::__format::__insertable<std::deque<wchar_t>>);
+static_assert(!std::__format::__insertable<std::forward_list<char>>);
+static_assert(!std::__format::__insertable<std::forward_list<wchar_t>>);
+static_assert(std::__format::__insertable<std::list<char>>);
+static_assert(std::__format::__insertable<std::list<wchar_t>>);
+
+static_assert(!std::__format::__insertable<std::set<char>>);
+static_assert(!std::__format::__insertable<std::set<wchar_t>>);
+static_assert(!std::__format::__insertable<std::map<char, char>>);
+static_assert(!std::__format::__insertable<std::map<wchar_t, wchar_t>>);
+static_assert(!std::__format::__insertable<std::multiset<char>>);
+static_assert(!std::__format::__insertable<std::multiset<wchar_t>>);
+static_assert(!std::__format::__insertable<std::multimap<char, char>>);
+static_assert(!std::__format::__insertable<std::multimap<wchar_t, wchar_t>>);
+
+static_assert(!std::__format::__insertable<std::stack<char>>);
+static_assert(!std::__format::__insertable<std::stack<wchar_t>>);
+static_assert(!std::__format::__insertable<std::queue<char>>);
+static_assert(!std::__format::__insertable<std::queue<wchar_t>>);
+static_assert(!std::__format::__insertable<std::priority_queue<char>>);
+static_assert(!std::__format::__insertable<std::priority_queue<wchar_t>>);
+
+static_assert(!std::__format::__insertable<std::span<char>>);
+static_assert(!std::__format::__insertable<std::span<wchar_t>>);