1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___FORMAT_FORMATTER_INTEGRAL_H
11#define _LIBCPP___FORMAT_FORMATTER_INTEGRAL_H
12
13#include <__charconv/to_chars_integral.h>
14#include <__charconv/to_chars_result.h>
15#include <__charconv/traits.h>
16#include <__concepts/arithmetic.h>
17#include <__concepts/same_as.h>
18#include <__config>
19#include <__format/concepts.h>
20#include <__format/format_error.h>
21#include <__format/formatter_output.h>
22#include <__format/parser_std_format_spec.h>
23#include <__iterator/concepts.h>
24#include <__iterator/iterator_traits.h>
25#include <__locale_dir/num.h>
26#include <__memory/pointer_traits.h>
27#include <__system_error/errc.h>
28#include <__type_traits/make_unsigned.h>
29#include <__utility/unreachable.h>
30#include <array>
31#include <cstdint>
32#include <limits>
33#include <string>
34#include <string_view>
35
36#if _LIBCPP_HAS_LOCALIZATION
37# include <__locale_dir/locale.h>
38#endif
39
40#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
41# pragma GCC system_header
42#endif
43
44_LIBCPP_PUSH_MACROS
45#include <__undef_macros>
46
47_LIBCPP_BEGIN_NAMESPACE_STD
48
49#if _LIBCPP_STD_VER >= 20
50
51namespace __formatter {
52
53//
54// Generic
55//
56
57template <contiguous_iterator _Iterator>
58 requires same_as<char, iter_value_t<_Iterator>>
59_LIBCPP_HIDE_FROM_ABI inline _Iterator __insert_sign(_Iterator __buf, bool __negative, __format_spec::__sign __sign) {
60 if (__negative)
61 *__buf++ = '-';
62 else
63 switch (__sign) {
64 case __format_spec::__sign::__default:
65 case __format_spec::__sign::__minus:
66 // No sign added.
67 break;
68 case __format_spec::__sign::__plus:
69 *__buf++ = '+';
70 break;
71 case __format_spec::__sign::__space:
72 *__buf++ = ' ';
73 break;
74 }
75
76 return __buf;
77}
78
79/**
80 * Determines the required grouping based on the size of the input.
81 *
82 * The grouping's last element will be repeated. For simplicity this repeating
83 * is unwrapped based on the length of the input. (When the input is short some
84 * groups are not processed.)
85 *
86 * @returns The size of the groups to write. This means the number of
87 * separator characters written is size() - 1.
88 *
89 * @note Since zero-sized groups cause issues they are silently ignored.
90 *
91 * @note The grouping field of the locale is always a @c std::string,
92 * regardless whether the @c std::numpunct's type is @c char or @c wchar_t.
93 */
94_LIBCPP_HIDE_FROM_ABI inline string __determine_grouping(ptrdiff_t __size, const string& __grouping) {
95 _LIBCPP_ASSERT_INTERNAL(!__grouping.empty() && __size > __grouping[0],
96 "The slow grouping formatting is used while there will be no separators written");
97 string __r;
98 auto __end = __grouping.end() - 1;
99 auto __ptr = __grouping.begin();
100
101 while (true) {
102 __size -= *__ptr;
103 if (__size > 0)
104 __r.push_back(c: *__ptr);
105 else {
106 // __size <= 0 so the value pushed will be <= *__ptr.
107 __r.push_back(c: *__ptr + __size);
108 return __r;
109 }
110
111 // Proceed to the next group.
112 if (__ptr != __end) {
113 do {
114 ++__ptr;
115 // Skip grouping with a width of 0.
116 } while (*__ptr == 0 && __ptr != __end);
117 }
118 }
119
120 __libcpp_unreachable();
121}
122
123//
124// Char
125//
126
127template <__fmt_char_type _CharT>
128_LIBCPP_HIDE_FROM_ABI auto
129__format_char(integral auto __value,
130 output_iterator<const _CharT&> auto __out_it,
131 __format_spec::__parsed_specifications<_CharT> __specs) -> decltype(__out_it) {
132 using _Tp = decltype(__value);
133 if constexpr (!same_as<_CharT, _Tp>) {
134 // cmp_less and cmp_greater can't be used for character types.
135 if constexpr (signed_integral<_CharT> == signed_integral<_Tp>) {
136 if (__value < numeric_limits<_CharT>::min() || __value > numeric_limits<_CharT>::max())
137 std::__throw_format_error(s: "Integral value outside the range of the char type");
138 } else if constexpr (signed_integral<_CharT>) {
139 // _CharT is signed _Tp is unsigned
140 if (__value > static_cast<make_unsigned_t<_CharT>>(numeric_limits<_CharT>::max()))
141 std::__throw_format_error(s: "Integral value outside the range of the char type");
142 } else {
143 // _CharT is unsigned _Tp is signed
144 if (__value < 0 || static_cast<make_unsigned_t<_Tp>>(__value) > numeric_limits<_CharT>::max())
145 std::__throw_format_error(s: "Integral value outside the range of the char type");
146 }
147 }
148
149 const auto __c = static_cast<_CharT>(__value);
150 return __formatter::__write(std::addressof(__c), std::addressof(__c) + 1, std::move(__out_it), __specs);
151}
152
153//
154// Integer
155//
156
157/** Wrapper around @ref to_chars, returning the output iterator. */
158template <contiguous_iterator _Iterator, integral _Tp>
159 requires same_as<char, iter_value_t<_Iterator>>
160_LIBCPP_HIDE_FROM_ABI _Iterator __to_buffer(_Iterator __first, _Iterator __last, _Tp __value, int __base) {
161 // TODO FMT Evaluate code overhead due to not calling the internal function
162 // directly. (Should be zero overhead.)
163 to_chars_result __r = std::to_chars(std::to_address(__first), std::to_address(__last), __value, __base);
164 _LIBCPP_ASSERT_INTERNAL(__r.ec == errc(0), "Internal buffer too small");
165 auto __diff = __r.ptr - std::to_address(__first);
166 return __first + __diff;
167}
168
169/**
170 * Helper to determine the buffer size to output a integer in Base @em x.
171 *
172 * There are several overloads for the supported bases. The function uses the
173 * base as template argument so it can be used in a constant expression.
174 */
175template <unsigned_integral _Tp, size_t _Base>
176consteval size_t __buffer_size() noexcept
177 requires(_Base == 2)
178{
179 return numeric_limits<_Tp>::digits // The number of binary digits.
180 + 2 // Reserve space for the '0[Bb]' prefix.
181 + 1; // Reserve space for the sign.
182}
183
184template <unsigned_integral _Tp, size_t _Base>
185consteval size_t __buffer_size() noexcept
186 requires(_Base == 8)
187{
188 return numeric_limits<_Tp>::digits // The number of binary digits.
189 / 3 // Adjust to octal.
190 + 1 // Turn floor to ceil.
191 + 1 // Reserve space for the '0' prefix.
192 + 1; // Reserve space for the sign.
193}
194
195template <unsigned_integral _Tp, size_t _Base>
196consteval size_t __buffer_size() noexcept
197 requires(_Base == 10)
198{
199 return numeric_limits<_Tp>::digits10 // The floored value.
200 + 1 // Turn floor to ceil.
201 + 1; // Reserve space for the sign.
202}
203
204template <unsigned_integral _Tp, size_t _Base>
205consteval size_t __buffer_size() noexcept
206 requires(_Base == 16)
207{
208 return numeric_limits<_Tp>::digits // The number of binary digits.
209 / 4 // Adjust to hexadecimal.
210 + 2 // Reserve space for the '0[Xx]' prefix.
211 + 1; // Reserve space for the sign.
212}
213
214template <class _OutIt, contiguous_iterator _Iterator, class _CharT>
215 requires same_as<char, iter_value_t<_Iterator>>
216_LIBCPP_HIDE_FROM_ABI _OutIt __write_using_decimal_separators(
217 _OutIt __out_it,
218 _Iterator __begin,
219 _Iterator __first,
220 _Iterator __last,
221 string&& __grouping,
222 _CharT __sep,
223 __format_spec::__parsed_specifications<_CharT> __specs) {
224 int __size = (__first - __begin) + // [sign][prefix]
225 (__last - __first) + // data
226 (__grouping.size() - 1); // number of separator characters
227
228 __padding_size_result __padding = {0, 0};
229 if (__specs.__alignment_ == __format_spec::__alignment::__zero_padding) {
230 // Write [sign][prefix].
231 __out_it = __formatter::__copy(__begin, __first, std::move(__out_it));
232
233 if (__specs.__width_ > __size) {
234 // Write zero padding.
235 __padding.__before_ = __specs.__width_ - __size;
236 __out_it = __formatter::__fill(std::move(__out_it), __specs.__width_ - __size, _CharT('0'));
237 }
238 } else {
239 if (__specs.__width_ > __size) {
240 // Determine padding and write padding.
241 __padding = __formatter::__padding_size(__size, width: __specs.__width_, align: __specs.__alignment_);
242
243 __out_it = __formatter::__fill(std::move(__out_it), __padding.__before_, __specs.__fill_);
244 }
245 // Write [sign][prefix].
246 __out_it = __formatter::__copy(__begin, __first, std::move(__out_it));
247 }
248
249 auto __r = __grouping.rbegin();
250 auto __e = __grouping.rend() - 1;
251 _LIBCPP_ASSERT_INTERNAL(
252 __r != __e, "The slow grouping formatting is used while there will be no separators written.");
253 // The output is divided in small groups of numbers to write:
254 // - A group before the first separator.
255 // - A separator and a group, repeated for the number of separators.
256 // - A group after the last separator.
257 // This loop achieves that process by testing the termination condition
258 // midway in the loop.
259 //
260 // TODO FMT This loop evaluates the loop invariant `__parser.__type !=
261 // _Flags::_Type::__hexadecimal_upper_case` for every iteration. (This test
262 // happens in the __write call.) Benchmark whether making two loops and
263 // hoisting the invariant is worth the effort.
264 while (true) {
265 if (__specs.__std_.__type_ == __format_spec::__type::__hexadecimal_upper_case) {
266 __last = __first + *__r;
267 __out_it = __formatter::__transform(__first, __last, std::move(__out_it), __hex_to_upper);
268 __first = __last;
269 } else {
270 __out_it = __formatter::__copy(__first, *__r, std::move(__out_it));
271 __first += *__r;
272 }
273
274 if (__r == __e)
275 break;
276
277 ++__r;
278 *__out_it++ = __sep;
279 }
280
281 return __formatter::__fill(std::move(__out_it), __padding.__after_, __specs.__fill_);
282}
283
284template <unsigned_integral _Tp, contiguous_iterator _Iterator, class _CharT, class _FormatContext>
285 requires same_as<char, iter_value_t<_Iterator>>
286_LIBCPP_HIDE_FROM_ABI typename _FormatContext::iterator __format_integer(
287 _Tp __value,
288 _FormatContext& __ctx,
289 __format_spec::__parsed_specifications<_CharT> __specs,
290 bool __negative,
291 _Iterator __begin,
292 _Iterator __end,
293 const char* __prefix,
294 int __base) {
295 _Iterator __first = __formatter::__insert_sign(__begin, __negative, __specs.__std_.__sign_);
296 if (__specs.__std_.__alternate_form_ && __prefix)
297 while (*__prefix)
298 *__first++ = *__prefix++;
299
300 _Iterator __last = __formatter::__to_buffer(__first, __end, __value, __base);
301
302# if _LIBCPP_HAS_LOCALIZATION
303 if (__specs.__std_.__locale_specific_form_) {
304 const auto& __np = std::use_facet<numpunct<_CharT>>(__ctx.locale());
305 string __grouping = __np.grouping();
306 ptrdiff_t __size = __last - __first;
307 // Writing the grouped form has more overhead than the normal output
308 // routines. If there will be no separators written the locale-specific
309 // form is identical to the normal routine. Test whether to grouped form
310 // is required.
311 if (!__grouping.empty() && __size > __grouping[0])
312 return __formatter::__write_using_decimal_separators(
313 __ctx.out(),
314 __begin,
315 __first,
316 __last,
317 __formatter::__determine_grouping(__size, __grouping),
318 __np.thousands_sep(),
319 __specs);
320 }
321# endif
322 auto __out_it = __ctx.out();
323 if (__specs.__alignment_ != __format_spec::__alignment::__zero_padding)
324 __first = __begin;
325 else {
326 // __buf contains [sign][prefix]data
327 // ^ location of __first
328 // The zero padding is done like:
329 // - Write [sign][prefix]
330 // - Write data right aligned with '0' as fill character.
331 __out_it = __formatter::__copy(__begin, __first, std::move(__out_it));
332 __specs.__alignment_ = __format_spec::__alignment::__right;
333 __specs.__fill_.__data[0] = _CharT('0');
334 int32_t __size = __first - __begin;
335
336 __specs.__width_ -= std::min(__size, __specs.__width_);
337 }
338
339 if (__specs.__std_.__type_ != __format_spec::__type::__hexadecimal_upper_case) [[likely]]
340 return __formatter::__write(__first, __last, __ctx.out(), __specs);
341
342 return __formatter::__write_transformed(__first, __last, __ctx.out(), __specs, std::__hex_to_upper);
343}
344
345template <unsigned_integral _Tp, class _CharT, class _FormatContext>
346_LIBCPP_HIDE_FROM_ABI typename _FormatContext::iterator
347__format_integer(_Tp __value,
348 _FormatContext& __ctx,
349 __format_spec::__parsed_specifications<_CharT> __specs,
350 bool __negative = false) {
351 switch (__specs.__std_.__type_) {
352 case __format_spec::__type::__binary_lower_case: {
353 array<char, __formatter::__buffer_size<decltype(__value), 2>()> __array;
354 return __formatter::__format_integer(__value, __ctx, __specs, __negative, __array.begin(), __array.end(), "0b", 2);
355 }
356 case __format_spec::__type::__binary_upper_case: {
357 array<char, __formatter::__buffer_size<decltype(__value), 2>()> __array;
358 return __formatter::__format_integer(__value, __ctx, __specs, __negative, __array.begin(), __array.end(), "0B", 2);
359 }
360 case __format_spec::__type::__octal: {
361 // Octal is special; if __value == 0 there's no prefix.
362 array<char, __formatter::__buffer_size<decltype(__value), 8>()> __array;
363 return __formatter::__format_integer(
364 __value, __ctx, __specs, __negative, __array.begin(), __array.end(), __value != 0 ? "0" : nullptr, 8);
365 }
366 case __format_spec::__type::__default:
367 case __format_spec::__type::__decimal: {
368 array<char, __formatter::__buffer_size<decltype(__value), 10>()> __array;
369 return __formatter::__format_integer(
370 __value, __ctx, __specs, __negative, __array.begin(), __array.end(), nullptr, 10);
371 }
372 case __format_spec::__type::__hexadecimal_lower_case: {
373 array<char, __formatter::__buffer_size<decltype(__value), 16>()> __array;
374 return __formatter::__format_integer(__value, __ctx, __specs, __negative, __array.begin(), __array.end(), "0x", 16);
375 }
376 case __format_spec::__type::__hexadecimal_upper_case: {
377 array<char, __formatter::__buffer_size<decltype(__value), 16>()> __array;
378 return __formatter::__format_integer(__value, __ctx, __specs, __negative, __array.begin(), __array.end(), "0X", 16);
379 }
380 default:
381 _LIBCPP_ASSERT_INTERNAL(false, "The parse function should have validated the type");
382 __libcpp_unreachable();
383 }
384}
385
386template <signed_integral _Tp, class _CharT, class _FormatContext>
387_LIBCPP_HIDE_FROM_ABI typename _FormatContext::iterator
388__format_integer(_Tp __value, _FormatContext& __ctx, __format_spec::__parsed_specifications<_CharT> __specs) {
389 // Depending on the std-format-spec string the sign and the value
390 // might not be outputted together:
391 // - alternate form may insert a prefix string.
392 // - zero-padding may insert additional '0' characters.
393 // Therefore the value is processed as a positive unsigned value.
394 // The function @ref __insert_sign will a '-' when the value was negative.
395 auto __r = std::__to_unsigned_like(__value);
396 bool __negative = __value < 0;
397 if (__negative)
398 __r = std::__complement(__r);
399
400 return __formatter::__format_integer(__r, __ctx, __specs, __negative);
401}
402
403//
404// Formatter arithmetic (bool)
405//
406
407template <class _CharT>
408struct __bool_strings;
409
410template <>
411struct __bool_strings<char> {
412 static constexpr string_view __true{"true"};
413 static constexpr string_view __false{"false"};
414};
415
416# if _LIBCPP_HAS_WIDE_CHARACTERS
417template <>
418struct __bool_strings<wchar_t> {
419 static constexpr wstring_view __true{L"true"};
420 static constexpr wstring_view __false{L"false"};
421};
422# endif
423
424template <class _CharT, class _FormatContext>
425_LIBCPP_HIDE_FROM_ABI typename _FormatContext::iterator
426__format_bool(bool __value, _FormatContext& __ctx, __format_spec::__parsed_specifications<_CharT> __specs) {
427# if _LIBCPP_HAS_LOCALIZATION
428 if (__specs.__std_.__locale_specific_form_) {
429 const auto& __np = std::use_facet<numpunct<_CharT>>(__ctx.locale());
430 basic_string<_CharT> __str = __value ? __np.truename() : __np.falsename();
431 return __formatter::__write_string_no_precision(basic_string_view<_CharT>{__str}, __ctx.out(), __specs);
432 }
433# endif
434 basic_string_view<_CharT> __str =
435 __value ? __formatter::__bool_strings<_CharT>::__true : __formatter::__bool_strings<_CharT>::__false;
436 return __formatter::__write(__str.begin(), __str.end(), __ctx.out(), __specs);
437}
438
439} // namespace __formatter
440
441#endif // _LIBCPP_STD_VER >= 20
442
443_LIBCPP_END_NAMESPACE_STD
444
445_LIBCPP_POP_MACROS
446
447#endif // _LIBCPP___FORMAT_FORMATTER_INTEGRAL_H
448