[libc++][format][5/6] Improve format_to_n.

[Mordante]

Summary

Use a specialized buffer wrapper to limit the number of insertions in the
buffer. After the limit has been reached the buffer only needs to count
the number of insertions to return the buffer size required to store the
entire output.

Depends on D110498

[• Quuxplusone]

libcxx/include/__format/buffer.h

283–284

286

Given that you continue incrementing __size_ even after hitting the end of __buffer_, I think it's a bit dangerous to use any type here except size_t. I recommend s/_Size/size_t/g.
I don't see any particular usefulness in continuing to store __n_ as _Size, either. formatted_size() is specced to return size_t, not iter_difference_t<anything>, so I think size_t throughout would make plenty of sense.

[Mordante]

libcxx/include/__format/buffer.h

283–284

Again what clang-format makes of the code.

286

The normal formatted_size indeed returns a size_t, but format_to_n returns

template<class Out> struct format_to_n_result {
  Out out;
  iter_difference_t<Out> size; // This is the formatted_size.
};

So I prefer to keep this the same type as the Standard specified.

[Mordante]

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

[Mordante]

Rebased and adjusted to changes in __put.

[Mordante]

Rebased to test with wchar_t changes.

[Mordante]

Rebased and make changes based on D112361.

[vitaut]

libcxx/include/format

380–381

Similarly to other diffs, let's introduce __vformat_to_n and force inline format_to_n for bloat prevention to actually work.

381–384

Not sure if this branch is worth adding. __format_to_n_buffer should perform reasonably well for this case.

[Mordante]

libcxx/include/format

381–384

I need to guard against __n < 0 since the __n is used as an unsigned capacity in the buffer code. So I thought it was easiest to add the guard here.

[vitaut]

libcxx/include/format

381–384

I understand that you need a check, my comment was that special casing 0 (and negative size) is probably not worth it. I'd suggest keeping it simpler and go through __format_to_n_buffer in all cases.

[Mordante]

Addresses review comments.

[Mordante]

Rebased to trigger CI.

[Mordante]

I investigated the CI issue and it seems to be unrelated to the changes.

[Mordante]

Rebase.

[vitaut]

libcxx/include/__format/buffer.h

23

What is this for?

[Mordante]

libcxx/include/__format/buffer.h

23

This is the libc++ internal header that (among other things) contains iter_difference_t.

[ldionne]

libcxx/include/__format/buffer.h

279

This formatting strikes me as really strange. I'd expect something like:

template <class _OutIt, __formatter::__char_type _CharT, bool>
  requires output_iterator<_OutIt, const _CharT&>
struct _LIBCPP_TEMPLATE_VIS __format_to_n_buffer_base {

The current formatting for this declaration is somewhat difficult to read IMO.

libcxx/include/format

374

You probably want to use std:: instead of _VSTD::

524–527

I would rather not use _LIBCPP_ALWAYS_INLINE I would let the compiler make the right call here -- _LIBCPP_ALWAYS_INLINE has a negative impact on various optimizations and on the debugging experience, so we should steer clear of it unless we have a specific reason to. A function being a one-liner isn't a sufficient reason -- the optimizer should be able to figure out whether it is worth actually generating a function call (most likely not).

[Mordante]

Thanks for the review! I'll address the comment shortly.

libcxx/include/__format/buffer.h

279

I tend to use clang-format and that's what clang-format made of it. I've filed some bug reports. I'm quite sure ToT clang-format will format it as you suggested.

libcxx/include/format

374

Actually, for consistency, I prefer to use _VSTD::. This patch predates the changes to use std::. On my TODO list I have an item to do s/_VSTD/std for all format related code.

524–527

This was suggested by @vitaut. I don't mind to remove it. I still want to look closer at the codegen after P2216 and P2418 are done. (I already identified code bloat in the parser code, which is on my list for P2216 and P2418.)

[vitaut]

libcxx/include/format

524–527

Functions like this should be inlined, otherwise you'll get a new instantiation for every call with different argument types which is a disaster. Compilers are terrible at dealing with this sort of things.

[Mordante]

libcxx/include/format

524–527

Thanks for the additional information. I've added a TODO to investigate this and when needed file a bug report.

[Mordante]

Rebased and address review comments.

[vitaut]

libcxx/include/format

524–527

If you are referring to my comment then there is no bug to report. I was mostly explaining why this function must be forced inlined. A compiler doesn't have information to figure it out on its own.

[Mordante]

libcxx/include/format

524–527

No it's a TODO for me. In general we dislike to add compiler work-arounds in our code. If we need it we often file a bug report, where it hopefully gets fixed.

[vitaut]

libcxx/include/format

524–527

I would argue that it's not a workaround but a part of the design of std::format and the whole reason why we have v* functions in the first place.

[ldionne]

libcxx/include/__format/buffer.h

295

It strikes me that perhaps __internal_storage::capacity() should be renamed to __internal_storage::size(). capacity() makes it look like it's not something we can write to (like std::vector::capacity()). No action for this patch, and this is just a suggestion.

315

Why do we unwrap_iter here? If the iterator is something that e.g. checks the bounds, it seems like it would be useful to keep it wrapped to get this checking?

libcxx/include/format

524–527

I'm swayed by @vitaut's explanation. _LIBCPP_ALWAYS_INLINE is definitely reasonable here then, IMO.

[philnik]

libcxx/include/format

524–527

Could you add a comment explaining the _LIBCPP_ALWAYS_INLINE? We've got a few of these around the code base and most of them look to me like they don't actually belong there. I think it would be nice if we could have the reasoning right in the code and not have to hunt it down (assuming there is one to find). I didn't feel like looking into the other _LIBCPP_ALWAYS_INLINE yet, but I want to do that at some point and potentially remove some of them.

[Mordante]

Thanks for the reviews!

libcxx/include/__format/buffer.h

295

I see your point, but to bike-shed I'm not too fond of size() since the storage doesn't really keep track of the number of elements stored. I think, maybe remove the function and make __buffer_size_ public instead. I'll look at that in a followup patch.

315

Unwrapping gives a raw pointer, which allows certain optimizations. For example when using std::string::iterator. This is only done when the checks are disabled. The concept on line 119 is used to select this __format_to_n_buffer_base specialization.

template <class _OutIt, class _CharT>
concept __enable_direct_output = __formatter::__char_type<_CharT> &&
    (same_as<_OutIt, _CharT*>
#if _LIBCPP_DEBUG_LEVEL < 2
     || same_as<_OutIt, __wrap_iter<_CharT*>>
#endif
    );

When this concept isn't true __out_it will not be unwrapped.

libcxx/include/format

524–527

I already added that to my todo list after I read Louis' comment yesterday ;-) However it seems I already added a comment :-)
I have moved it to the first occurrence (only once since I see no value in duplicating the comment).

[Mordante]

Rebased and improved some comment.

[vitaut]

libcxx/include/format

307–309

"to" looks out of place. Also I don't think it's clang-specific so opening bug report just for this compiler won't help.

[vitaut]

LGTM, just one minor comment inline.

[Mordante]

Address review comments.

[Mordante]

libcxx/include/format

307–309

s/to/the.

I want to look whether I can file a nice bug report since we in general want to do that when we need to manually aid the compiler. Before removing the annotations we need to look at whether all supported compilers do the right thing. (I don't expect that will happen soon.)

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 <__algorithm/copy_n.h>
+#include <__algorithm/max.h>
+#include <__algorithm/min.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__config>
 #include <__format/enable_insertable.h>
+#include <__format/format_to_n_result.h>
 #include <__format/formatter.h> // for __char_type TODO FMT Move the concept?
 #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 <__utility/move.h>
 #include <concepts>
 #include <cstddef>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER > 17
 
 namespace __format {
 
 /// A "buffer" that handles writing to the proper iterator.
 ///
public:
   }
 
 private:
   __internal_storage<_CharT> __storage_;
   __output_buffer<_CharT> __output_{__storage_.begin(), __storage_.capacity(), this};
   size_t __size_{0};
 };
 
+/// The base of a buffer that counts and limits the number of insertions.
+template <class _OutIt, __formatter::__char_type _CharT, bool>
+  requires(output_iterator<_OutIt, const _CharT&>)
+struct _LIBCPP_TEMPLATE_VIS __format_to_n_buffer_base {
+  using _Size = iter_difference_t<_OutIt>;
+
+public:
+  _LIBCPP_HIDE_FROM_ABI explicit __format_to_n_buffer_base(_OutIt __out_it, _Size __n)
+      : __writer_(_VSTD::move(__out_it)), __n_(_VSTD::max(_Size(0), __n)) {}
+
+  _LIBCPP_HIDE_FROM_ABI void flush(_CharT* __ptr, size_t __size) {
+    if (_Size(__size_) <= __n_)
+      __writer_.flush(__ptr, _VSTD::min(_Size(__size), __n_ - __size_));
+    __size_ += __size;
+  }
+
+protected:
+  __internal_storage<_CharT> __storage_;
+  __output_buffer<_CharT> __output_{__storage_.begin(), __storage_.capacity(), this};
+  typename __writer_selector<_OutIt, _CharT>::type __writer_;
+
+  _Size __n_;
+  _Size __size_{0};
+};
+
+/// The base of a buffer that counts and limits the number of insertions.
+///
+/// This version is used when \c __enable_direct_output<_OutIt, _CharT> == true.
+///
+/// This class limits the size available the the direct writer so it will not
+/// exceed the maximum number of code units.
+template <class _OutIt, __formatter::__char_type _CharT>
+  requires(output_iterator<_OutIt, const _CharT&>)
+class _LIBCPP_TEMPLATE_VIS __format_to_n_buffer_base<_OutIt, _CharT, true> {
+  using _Size = iter_difference_t<_OutIt>;
+
+public:
+  _LIBCPP_HIDE_FROM_ABI explicit __format_to_n_buffer_base(_OutIt __out_it, _Size __n)
+      : __output_(_VSTD::__unwrap_iter(__out_it), __n, this), __writer_(_VSTD::move(__out_it)) {
+    if (__n <= 0) [[unlikely]]
+      __output_.reset(__storage_.begin(), __storage_.capacity());
+  }
+
+  _LIBCPP_HIDE_FROM_ABI void flush(_CharT* __ptr, size_t __size) {
+    // A flush to the direct writer happens in two occasions:
+    // - The format function has written the maximum number of allowed code
+    //   units. At this point it's no longer valid to write to this writer. So
+    //   switch to the internal storage. This internal storage doesn't need to
+    //   be written anywhere so the flush for that storage writes no output.
+    // - The format_to_n function is finished. In this case there's no need to
+    //   switch the buffer, but for simplicity the buffers are still switched.
+    // When the __n <= 0 the constructor already switched the buffers.
+    if (__size_ == 0 && __ptr != __storage_.begin()) {
+      __writer_.flush(__ptr, __size);
+      __output_.reset(__storage_.begin(), __storage_.capacity());
+    }
+
+    __size_ += __size;
+  }
+
+protected:
+  __internal_storage<_CharT> __storage_;
+  __output_buffer<_CharT> __output_;
+  __writer_direct<_OutIt, _CharT> __writer_;
+
+  _Size __size_{0};
+};
+
+/// The buffer that counts and limits the number of insertions.
+template <class _OutIt, __formatter::__char_type _CharT>
+  requires(output_iterator<_OutIt, const _CharT&>)
+struct _LIBCPP_TEMPLATE_VIS __format_to_n_buffer final
+    : public __format_to_n_buffer_base< _OutIt, _CharT, __enable_direct_output<_OutIt, _CharT>> {
+  using _Base = __format_to_n_buffer_base<_OutIt, _CharT, __enable_direct_output<_OutIt, _CharT>>;
+  using _Size = iter_difference_t<_OutIt>;
+
+public:
+  _LIBCPP_HIDE_FROM_ABI explicit __format_to_n_buffer(_OutIt __out_it, _Size __n) : _Base(_VSTD::move(__out_it), __n) {}
+  _LIBCPP_HIDE_FROM_ABI auto make_output_iterator() { return this->__output_.make_output_iterator(); }
+
+  _LIBCPP_HIDE_FROM_ABI format_to_n_result<_OutIt> result() && {
+    this->__output_.flush();
+    return {_VSTD::move(this->__writer_).out(), this->__size_};
+  }
+};
 } // namespace __format
 
 #endif //_LIBCPP_STD_VER > 17
 
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif // _LIBCPP___FORMAT_BUFFER_H

libcxx/include/format

else {
     _VSTD::__format::__vformat_to(
         basic_format_parse_context{__fmt, __args.__size()},
         _VSTD::__format_context_create(__buffer.make_output_iterator(),
                                        __args));
     return _VSTD::move(__buffer).out();
   }
 }
 
 template <output_iterator<const char&> _OutIt>
 _LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT _OutIt
 vformat_to(_OutIt __out_it, string_view __fmt, format_args __args) {
   return _VSTD::__vformat_to(_VSTD::move(__out_it), __fmt, __args);
 }
 
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 template <output_iterator<const wchar_t&> _OutIt>
 _LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT _OutIt
 vformat_to(_OutIt __out_it, wstring_view __fmt, wformat_args __args) {
   return _VSTD::__vformat_to(_VSTD::move(__out_it), __fmt, __args);

 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 template <class... _Args>
 _LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT wstring
 format(wstring_view __fmt, const _Args&... __args) {
   return _VSTD::vformat(__fmt, _VSTD::make_wformat_args(__args...));
 }
 #endif
 
+template <class _Context, class _OutIt, class _CharT>
+_LIBCPP_HIDE_FROM_ABI format_to_n_result<_OutIt> __vformat_to_n(_OutIt __out_it, iter_difference_t<_OutIt> __n,
+                                                                basic_string_view<_CharT> __fmt,
+                                                                basic_format_args<_Context> __args) {
+  __format::__format_to_n_buffer<_OutIt, _CharT> __buffer{_VSTD::move(__out_it), __n};
+  _VSTD::__format::__vformat_to(basic_format_parse_context{__fmt, __args.__size()},
+                                _VSTD::__format_context_create(__buffer.make_output_iterator(), __args));
+  return _VSTD::move(__buffer).result();
+}
+
+// The function is _LIBCPP_ALWAYS_INLINE since to compiler is bad at inlining
+// https://reviews.llvm.org/D110499#inline-1180704
+// TODO FMT Valudate whether this is still true, if so file a bug report.
 template <output_iterator<const char&> _OutIt, class... _Args>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT format_to_n_result<_OutIt>
-format_to_n(_OutIt __out_it, iter_difference_t<_OutIt> __n, string_view __fmt,
-            const _Args&... __args) {
-  // TODO FMT Improve PoC: using std::string is inefficient.
-  string __str = _VSTD::vformat(__fmt, _VSTD::make_format_args(__args...));
-  iter_difference_t<_OutIt> __s = __str.size();
-  iter_difference_t<_OutIt> __m =
-      _VSTD::clamp(__n, iter_difference_t<_OutIt>(0), __s);
-  __out_it = _VSTD::copy_n(__str.begin(), __m, _VSTD::move(__out_it));
-  return {_VSTD::move(__out_it), __s};
+_LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT format_to_n_result<_OutIt>
+format_to_n(_OutIt __out_it, iter_difference_t<_OutIt> __n, string_view __fmt, const _Args&... __args) {
+  return _VSTD::__vformat_to_n<format_context>(_VSTD::move(__out_it), __n, __fmt, _VSTD::make_format_args(__args...));
 }
 
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 template <output_iterator<const wchar_t&> _OutIt, class... _Args>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT format_to_n_result<_OutIt>
-format_to_n(_OutIt __out_it, iter_difference_t<_OutIt> __n, wstring_view __fmt,
-            const _Args&... __args) {
-  // TODO FMT Improve PoC: using std::string is inefficient.
-  wstring __str = _VSTD::vformat(__fmt, _VSTD::make_wformat_args(__args...));
-  iter_difference_t<_OutIt> __s = __str.size();
-  iter_difference_t<_OutIt> __m =
-      _VSTD::clamp(__n, iter_difference_t<_OutIt>(0), __s);
-  __out_it = _VSTD::copy_n(__str.begin(), __m, _VSTD::move(__out_it));
-  return {_VSTD::move(__out_it), __s};
+_LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT format_to_n_result<_OutIt>
+format_to_n(_OutIt __out_it, iter_difference_t<_OutIt> __n, wstring_view __fmt, const _Args&... __args) {
+  return _VSTD::__vformat_to_n<wformat_context>(_VSTD::move(__out_it), __n, __fmt, _VSTD::make_wformat_args(__args...));
 }
 #endif
 
 template <class _CharT>
 _LIBCPP_HIDE_FROM_ABI size_t __vformatted_size(basic_string_view<_CharT> __fmt, auto __args) {
   __format::__formatted_size_buffer<_CharT> __buffer;
   _VSTD::__format::__vformat_to(basic_format_parse_context{__fmt, __args.__size()},
                                 _VSTD::__format_context_create(__buffer.make_output_iterator(), __args));

 template <class... _Args>
 _LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT wstring
 format(locale __loc, wstring_view __fmt, const _Args&... __args) {
   return _VSTD::vformat(_VSTD::move(__loc), __fmt,
                         _VSTD::make_wformat_args(__args...));
 }
 #endif
 
+template <class _Context, class _OutIt, class _CharT>
+_LIBCPP_HIDE_FROM_ABI format_to_n_result<_OutIt> __vformat_to_n(_OutIt __out_it, iter_difference_t<_OutIt> __n,
+                                                                locale __loc, basic_string_view<_CharT> __fmt,
+                                                                basic_format_args<_Context> __args) {
+  __format::__format_to_n_buffer<_OutIt, _CharT> __buffer{_VSTD::move(__out_it), __n};
+  _VSTD::__format::__vformat_to(
+      basic_format_parse_context{__fmt, __args.__size()},
+      _VSTD::__format_context_create(__buffer.make_output_iterator(), __args, _VSTD::move(__loc)));
+  return _VSTD::move(__buffer).result();
+}
+
 template <output_iterator<const char&> _OutIt, class... _Args>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT format_to_n_result<_OutIt>
-format_to_n(_OutIt __out_it, iter_difference_t<_OutIt> __n, locale __loc,
-            string_view __fmt, const _Args&... __args) {
-  // TODO FMT Improve PoC: using std::string is inefficient.
-  string __str = _VSTD::vformat(_VSTD::move(__loc), __fmt,
+_LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT format_to_n_result<_OutIt>
+format_to_n(_OutIt __out_it, iter_difference_t<_OutIt> __n, locale __loc, string_view __fmt, const _Args&... __args) {
+  return _VSTD::__vformat_to_n<format_context>(_VSTD::move(__out_it), __n, _VSTD::move(__loc), __fmt,
                                                _VSTD::make_format_args(__args...));
-  iter_difference_t<_OutIt> __s = __str.size();
-  iter_difference_t<_OutIt> __m =
-      _VSTD::clamp(__n, iter_difference_t<_OutIt>(0), __s);
-  __out_it = _VSTD::copy_n(__str.begin(), __m, _VSTD::move(__out_it));
-  return {_VSTD::move(__out_it), __s};
 }
 
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 template <output_iterator<const wchar_t&> _OutIt, class... _Args>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT format_to_n_result<_OutIt>
-format_to_n(_OutIt __out_it, iter_difference_t<_OutIt> __n, locale __loc,
-            wstring_view __fmt, const _Args&... __args) {
-  // TODO FMT Improve PoC: using std::string is inefficient.
-  wstring __str = _VSTD::vformat(_VSTD::move(__loc), __fmt,
+_LIBCPP_ALWAYS_INLINE _LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT format_to_n_result<_OutIt>
+format_to_n(_OutIt __out_it, iter_difference_t<_OutIt> __n, locale __loc, wstring_view __fmt, const _Args&... __args) {
+  return _VSTD::__vformat_to_n<wformat_context>(_VSTD::move(__out_it), __n, _VSTD::move(__loc), __fmt,
                                                 _VSTD::make_wformat_args(__args...));
-  iter_difference_t<_OutIt> __s = __str.size();
-  iter_difference_t<_OutIt> __m =
-      _VSTD::clamp(__n, iter_difference_t<_OutIt>(0), __s);
-  __out_it = _VSTD::copy_n(__str.begin(), __m, _VSTD::move(__out_it));
-  return {_VSTD::move(__out_it), __s};
 }
 #endif
 
 template <class _CharT>
 _LIBCPP_HIDE_FROM_ABI size_t __vformatted_size(locale __loc, basic_string_view<_CharT> __fmt, auto __args) {
   __format::__formatted_size_buffer<_CharT> __buffer;
   _VSTD::__format::__vformat_to(
       basic_format_parse_context{__fmt, __args.__size()},