[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

192–193

195

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

192–193

Again what clang-format makes of the code.

195

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

598

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

600–607

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

[Mordante]

libcxx/include/format

600–607

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

600–607

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

17

What is this for?

[Mordante]

libcxx/include/__format/buffer.h

17

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

[ldionne]

libcxx/include/__format/buffer.h

188

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

597

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

768–775

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

188

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

597

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.

768–775

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

768–775

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

768–775

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

768–775

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

768–775

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

768–775

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

204

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.

224

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

768–775

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

[philnik]

libcxx/include/format

768–775

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

204

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.

224

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

768–775

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

530–532

"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

530–532

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 <__config>
 #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
public:
   _LIBCPP_HIDE_FROM_ABI size_t formatted_size() const noexcept {
     return __size_;
   }
 
 private:
   size_t __size_{0};
 };
 
+/// A buffer that counts and limits the number of insertions.
+///
+/// This buffer holds another buffer to do the actual insertions until the
+/// requested maximum has been reached. Once the maximum is reached it only
+/// keeps track of the number of additional insertions.
+template <class _OutIt, __formatter::__char_type _CharT>
+requires(output_iterator<_OutIt, const _CharT&>) class _LIBCPP_TEMPLATE_VIS
+    __format_to_n_buffer {
+  using _Buffer = typename __buffer_selector<_OutIt, _CharT>::type;
+  using _Size = iter_difference_t<_OutIt>;
+
+public:
+  _LIBCPP_HIDE_FROM_ABI explicit __format_to_n_buffer(_OutIt __out_it,
+                                                      _Size __n)
+      : __buffer_(_VSTD::move(__out_it)), __n_(__n) {}
+
+  _LIBCPP_HIDE_FROM_ABI void put(_CharT __c) {
+    ++__size_;
+    if (__size_ <= __n_)
+      __buffer_.put(__c);
+  }
+
+  _LIBCPP_HIDE_FROM_ABI _OutIt out() { return __buffer_.out(); }
+
+  _LIBCPP_HIDE_FROM_ABI _Size formatted_size() const noexcept {
+    return __size_;
+  }
+
+private:
+  _Buffer __buffer_;
+  _Size __n_;
+  _Size __size_{0};
+};
+
 } // 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

requires(output_iterator<_OutIt, const _CharT&>) _LIBCPP_HIDE_FROM_ABI _OutIt
   if constexpr (same_as<_OutIt, _FormatOutIt>)
     return _VSTD::__format::__vformat_to(
         basic_format_parse_context{__fmt, __args.__size()},
         _VSTD::__format_context_create(_VSTD::move(__out_it), __args));
   else
     return _VSTD::__vformat_to_wrapped(_VSTD::move(__out_it), __fmt, __args);
 }
 
 template <output_iterator<const char&> _OutIt>
 _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_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);

 
 template <class _OutIt>
 struct _LIBCPP_TEMPLATE_VIS format_to_n_result {
   _OutIt out;
   iter_difference_t<_OutIt> size;
 };
 
 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};
+
+  using _Buffer = __format::__format_to_n_buffer<_OutIt, char>;
+  _Buffer __buffer{_VSTD::move(__out_it), __n};
+  _VSTD::__vformat_to(
+      __format::__output_iterator<char>{_VSTD::addressof(__buffer)}, __fmt,
+      basic_format_args{_VSTD::make_format_args(__args...)});
+  return {__buffer.out(), __buffer.formatted_size()};
 }
 
 #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};
+
+  using _Buffer = __format::__format_to_n_buffer<_OutIt, wchar_t>;
+  _Buffer __buffer{_VSTD::move(__out_it), __n};
+  _VSTD::__vformat_to(
+      __format::__output_iterator<wchar_t>{_VSTD::addressof(__buffer)}, __fmt,
+      basic_format_args{_VSTD::make_wformat_args(__args...)});
+  return {__buffer.out(), __buffer.formatted_size()};
 }
 #endif
 
 template <class... _Args>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT size_t
 formatted_size(string_view __fmt, const _Args&... __args) {
   using _Buffer = __format::__formatted_size_buffer<char>;
   _Buffer __buffer;
return _VSTD::vformat(_VSTD::move(__loc), __fmt,
                         _VSTD::make_wformat_args(__args...));
 }
 #endif
 
 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,
-                                _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};
+
+  using _Buffer = __format::__format_to_n_buffer<_OutIt, char>;
+  _Buffer __buffer{_VSTD::move(__out_it), __n};
+  _VSTD::__vformat_to(
+      __format::__output_iterator<char>{_VSTD::addressof(__buffer)},
+      _VSTD::move(__loc), __fmt,
+      basic_format_args{_VSTD::make_format_args(__args...)});
+  return {__buffer.out(), __buffer.formatted_size()};
 }
 
 #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,
-                                 _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};
+
+  using _Buffer = __format::__format_to_n_buffer<_OutIt, wchar_t>;
+  _Buffer __buffer{_VSTD::move(__out_it), __n};
+  _VSTD::__vformat_to(
+      __format::__output_iterator<wchar_t>{_VSTD::addressof(__buffer)},
+      _VSTD::move(__loc), __fmt,
+      basic_format_args{_VSTD::make_wformat_args(__args...)});
+  return {__buffer.out(), __buffer.formatted_size()};
 }
 #endif
 
 template <class... _Args>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_AVAILABILITY_FORMAT size_t
 formatted_size(locale __loc, string_view __fmt, const _Args&... __args) {
   using _Buffer = __format::__formatted_size_buffer<char>;
   _Buffer __buffer;