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_OUTPUT_H
11 #define _LIBCPP___FORMAT_FORMATTER_OUTPUT_H
12 
13 #include <__algorithm/copy.h>
14 #include <__algorithm/copy_n.h>
15 #include <__algorithm/fill_n.h>
16 #include <__algorithm/transform.h>
17 #include <__config>
18 #include <__format/formatter.h>
19 #include <__format/parser_std_format_spec.h>
20 #include <__utility/move.h>
21 #include <__utility/unreachable.h>
22 #include <cstddef>
23 #include <string>
24 #include <string_view>
25 
26 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
27 #  pragma GCC system_header
28 #endif
29 
30 _LIBCPP_BEGIN_NAMESPACE_STD
31 
32 #if _LIBCPP_STD_VER > 17
33 
34 namespace __formatter {
35 
36 _LIBCPP_HIDE_FROM_ABI constexpr char __hex_to_upper(char __c) {
37   switch (__c) {
38   case 'a':
39     return 'A';
40   case 'b':
41     return 'B';
42   case 'c':
43     return 'C';
44   case 'd':
45     return 'D';
46   case 'e':
47     return 'E';
48   case 'f':
49     return 'F';
50   }
51   return __c;
52 }
53 
54 struct _LIBCPP_TYPE_VIS __padding_size_result {
55   size_t __before_;
56   size_t __after_;
57 };
58 
59 _LIBCPP_HIDE_FROM_ABI constexpr __padding_size_result
60 __padding_size(size_t __size, size_t __width, __format_spec::__alignment __align) {
61   _LIBCPP_ASSERT(__width > __size, "don't call this function when no padding is required");
62   _LIBCPP_ASSERT(__align != __format_spec::__alignment::__zero_padding,
63                  "the caller should have handled the zero-padding");
64 
65   size_t __fill = __width - __size;
66   switch (__align) {
67   case __format_spec::__alignment::__zero_padding:
68     __libcpp_unreachable();
69 
70   case __format_spec::__alignment::__left:
71     return {0, __fill};
72 
73   case __format_spec::__alignment::__center: {
74     // The extra padding is divided per [format.string.std]/3
75     // __before = floor(__fill, 2);
76     // __after = ceil(__fill, 2);
77     size_t __before = __fill / 2;
78     size_t __after = __fill - __before;
79     return {__before, __after};
80   }
81   case __format_spec::__alignment::__default:
82   case __format_spec::__alignment::__right:
83     return {__fill, 0};
84   }
85   __libcpp_unreachable();
86 }
87 
88 template <class _OutIt, class _CharT>
89 _LIBCPP_HIDE_FROM_ABI _OutIt __write_using_decimal_separators(_OutIt __out_it, const char* __begin, const char* __first,
90                                                               const char* __last, string&& __grouping, _CharT __sep,
91                                                               __format_spec::__parsed_specifications<_CharT> __specs) {
92   int __size = (__first - __begin) +    // [sign][prefix]
93                (__last - __first) +     // data
94                (__grouping.size() - 1); // number of separator characters
95 
96   __padding_size_result __padding = {0, 0};
97   if (__specs.__alignment_ == __format_spec::__alignment::__zero_padding) {
98     // Write [sign][prefix].
99     __out_it = _VSTD::copy(__begin, __first, _VSTD::move(__out_it));
100 
101     if (__specs.__width_ > __size) {
102       // Write zero padding.
103       __padding.__before_ = __specs.__width_ - __size;
104       __out_it = _VSTD::fill_n(_VSTD::move(__out_it), __specs.__width_ - __size, _CharT('0'));
105     }
106   } else {
107     if (__specs.__width_ > __size) {
108       // Determine padding and write padding.
109       __padding = __padding_size(__size, __specs.__width_, __specs.__alignment_);
110 
111       __out_it = _VSTD::fill_n(_VSTD::move(__out_it), __padding.__before_, __specs.__fill_);
112     }
113     // Write [sign][prefix].
114     __out_it = _VSTD::copy(__begin, __first, _VSTD::move(__out_it));
115   }
116 
117   auto __r = __grouping.rbegin();
118   auto __e = __grouping.rend() - 1;
119   _LIBCPP_ASSERT(__r != __e, "The slow grouping formatting is used while "
120                              "there will be no separators written.");
121   // The output is divided in small groups of numbers to write:
122   // - A group before the first separator.
123   // - A separator and a group, repeated for the number of separators.
124   // - A group after the last separator.
125   // This loop achieves that process by testing the termination condition
126   // midway in the loop.
127   //
128   // TODO FMT This loop evaluates the loop invariant `__parser.__type !=
129   // _Flags::_Type::__hexadecimal_upper_case` for every iteration. (This test
130   // happens in the __write call.) Benchmark whether making two loops and
131   // hoisting the invariant is worth the effort.
132   while (true) {
133     if (__specs.__std_.__type_ == __format_spec::__type::__hexadecimal_upper_case) {
134       __last = __first + *__r;
135       __out_it = _VSTD::transform(__first, __last, _VSTD::move(__out_it), __hex_to_upper);
136       __first = __last;
137     } else {
138       __out_it = _VSTD::copy_n(__first, *__r, _VSTD::move(__out_it));
139       __first += *__r;
140     }
141 
142     if (__r == __e)
143       break;
144 
145     ++__r;
146     *__out_it++ = __sep;
147   }
148 
149   return _VSTD::fill_n(_VSTD::move(__out_it), __padding.__after_, __specs.__fill_);
150 }
151 
152 /// Writes the input to the output with the required padding.
153 ///
154 /// Since the output column width is specified the function can be used for
155 /// ASCII and Unicode output.
156 ///
157 /// \pre [\a __first, \a __last) is a valid range.
158 /// \pre \a __size <= \a __width. Using this function when this pre-condition
159 ///      doesn't hold incurs an unwanted overhead.
160 ///
161 /// \param __first     Pointer to the first element to write.
162 /// \param __last      Pointer beyond the last element to write.
163 /// \param __out_it    The output iterator to write to.
164 /// \param __specs     The parsed formatting specifications.
165 /// \param __size      The (estimated) output column width. When the elements
166 ///                    to be written are ASCII the following condition holds
167 ///                    \a __size == \a __last - \a __first.
168 ///
169 /// \returns           An iterator pointing beyond the last element written.
170 ///
171 /// \note The type of the elements in range [\a __first, \a __last) can differ
172 /// from the type of \a __specs. Integer output uses \c std::to_chars for its
173 /// conversion, which means the [\a __first, \a __last) always contains elements
174 /// of the type \c char.
175 template <class _CharT, class _ParserCharT>
176 _LIBCPP_HIDE_FROM_ABI auto __write(const _CharT* __first, const _CharT* __last,
177                                    output_iterator<const _CharT&> auto __out_it,
178                                    __format_spec::__parsed_specifications<_ParserCharT> __specs, ptrdiff_t __size)
179     -> decltype(__out_it) {
180   _LIBCPP_ASSERT(__first <= __last, "Not a valid range");
181 
182   if (__size >= __specs.__width_)
183     return _VSTD::copy(__first, __last, _VSTD::move(__out_it));
184 
185   __padding_size_result __padding = __formatter::__padding_size(__size, __specs.__width_, __specs.__std_.__alignment_);
186   __out_it = _VSTD::fill_n(_VSTD::move(__out_it), __padding.__before_, __specs.__fill_);
187   __out_it = _VSTD::copy(__first, __last, _VSTD::move(__out_it));
188   return _VSTD::fill_n(_VSTD::move(__out_it), __padding.__after_, __specs.__fill_);
189 }
190 
191 /// \overload
192 /// Calls the function above where \a __size = \a __last - \a __first.
193 template <class _CharT, class _ParserCharT>
194 _LIBCPP_HIDE_FROM_ABI auto __write(const _CharT* __first, const _CharT* __last,
195                                    output_iterator<const _CharT&> auto __out_it,
196                                    __format_spec::__parsed_specifications<_ParserCharT> __specs) -> decltype(__out_it) {
197   return __write(__first, __last, _VSTD::move(__out_it), __specs, __last - __first);
198 }
199 
200 template <class _CharT, class _ParserCharT, class _UnaryOperation>
201 _LIBCPP_HIDE_FROM_ABI auto __write_transformed(const _CharT* __first, const _CharT* __last,
202                                                output_iterator<const _CharT&> auto __out_it,
203                                                __format_spec::__parsed_specifications<_ParserCharT> __specs,
204                                                _UnaryOperation __op) -> decltype(__out_it) {
205   _LIBCPP_ASSERT(__first <= __last, "Not a valid range");
206 
207   ptrdiff_t __size = __last - __first;
208   if (__size >= __specs.__width_)
209     return _VSTD::transform(__first, __last, _VSTD::move(__out_it), __op);
210 
211   __padding_size_result __padding = __padding_size(__size, __specs.__width_, __specs.__alignment_);
212   __out_it = _VSTD::fill_n(_VSTD::move(__out_it), __padding.__before_, __specs.__fill_);
213   __out_it = _VSTD::transform(__first, __last, _VSTD::move(__out_it), __op);
214   return _VSTD::fill_n(_VSTD::move(__out_it), __padding.__after_, __specs.__fill_);
215 }
216 
217 /// Writes additional zero's for the precision before the exponent.
218 /// This is used when the precision requested in the format string is larger
219 /// than the maximum precision of the floating-point type. These precision
220 /// digits are always 0.
221 ///
222 /// \param __exponent           The location of the exponent character.
223 /// \param __num_trailing_zeros The number of 0's to write before the exponent
224 ///                             character.
225 template <class _CharT, class _ParserCharT>
226 _LIBCPP_HIDE_FROM_ABI auto __write_using_trailing_zeros(
227     const _CharT* __first,
228     const _CharT* __last,
229     output_iterator<const _CharT&> auto __out_it,
230     __format_spec::__parsed_specifications<_ParserCharT> __specs,
231     size_t __size,
232     const _CharT* __exponent,
233     size_t __num_trailing_zeros) -> decltype(__out_it) {
234   _LIBCPP_ASSERT(__first <= __last, "Not a valid range");
235   _LIBCPP_ASSERT(__num_trailing_zeros > 0, "The overload not writing trailing zeros should have been used");
236 
237   __padding_size_result __padding =
238       __padding_size(__size + __num_trailing_zeros, __specs.__width_, __specs.__alignment_);
239   __out_it = _VSTD::fill_n(_VSTD::move(__out_it), __padding.__before_, __specs.__fill_);
240   __out_it = _VSTD::copy(__first, __exponent, _VSTD::move(__out_it));
241   __out_it = _VSTD::fill_n(_VSTD::move(__out_it), __num_trailing_zeros, _CharT('0'));
242   __out_it = _VSTD::copy(__exponent, __last, _VSTD::move(__out_it));
243   return _VSTD::fill_n(_VSTD::move(__out_it), __padding.__after_, __specs.__fill_);
244 }
245 
246 #  ifndef _LIBCPP_HAS_NO_UNICODE
247 template <class _CharT>
248 _LIBCPP_HIDE_FROM_ABI auto __write_unicode_no_precision(basic_string_view<_CharT> __str,
249                                                         output_iterator<const _CharT&> auto __out_it,
250                                                         __format_spec::__parsed_specifications<_CharT> __specs)
251     -> decltype(__out_it) {
252 
253   _LIBCPP_ASSERT(!__specs.__has_precision(), "use __write_unicode");
254   // No padding -> copy the string
255   if (!__specs.__has_width())
256     return _VSTD::copy(__str.begin(), __str.end(), _VSTD::move(__out_it));
257 
258   // Non Unicode part larger than width -> copy the string
259   auto __last = __format_spec::__detail::__estimate_column_width_fast(__str.begin(), __str.end());
260   ptrdiff_t __size = __last - __str.begin();
261   if (__size >= __specs.__width_)
262     return _VSTD::copy(__str.begin(), __str.end(), _VSTD::move(__out_it));
263 
264   // Is there a non Unicode part?
265   if (__last != __str.end()) {
266     // Non Unicode and Unicode part larger than width -> copy the string
267     __format_spec::__detail::__column_width_result __column_width =
268         __format_spec::__detail::__estimate_column_width(__last, __str.end(), __specs.__width_);
269     __size += __column_width.__width; // Note this new size is used when __size < __specs.__width_
270     if (__size >= __specs.__width_)
271       return _VSTD::copy(__str.begin(), __str.end(), _VSTD::move(__out_it));
272   }
273 
274   return __formatter::__write(__str.begin(), __str.end(), _VSTD::move(__out_it), __specs, __size);
275 }
276 #  endif
277 
278 template <class _CharT>
279 _LIBCPP_HIDE_FROM_ABI auto __write_unicode(basic_string_view<_CharT> __str,
280                                            output_iterator<const _CharT&> auto __out_it,
281                                            __format_spec::__parsed_specifications<_CharT> __specs)
282     -> decltype(__out_it) {
283 #  ifndef _LIBCPP_HAS_NO_UNICODE
284   if (!__specs.__has_precision())
285     return __formatter::__write_unicode_no_precision(__str, _VSTD::move(__out_it), __specs);
286 
287   // Non unicode part larger than precision -> truncate the output and use the normal write operation.
288   auto __last = __format_spec::__detail::__estimate_column_width_fast(__str.begin(), __str.end());
289   ptrdiff_t __size = __last - __str.begin();
290   if (__size >= __specs.__precision_)
291     return __formatter::__write(__str.begin(), __str.begin() + __specs.__precision_, _VSTD::move(__out_it), __specs,
292                                 __specs.__precision_);
293 
294   // No non Unicode part, implies __size <  __specs.__precision_ -> use normal write operation
295   if (__last == __str.end())
296     return __formatter::__write(__str.begin(), __str.end(), _VSTD::move(__out_it), __specs, __str.size());
297 
298   __format_spec::__detail::__column_width_result __column_width =
299       __format_spec::__detail::__estimate_column_width(__last, __str.end(), __specs.__precision_ - __size);
300   __size += __column_width.__width;
301   // Truncate the output
302   if (__column_width.__ptr != __str.end())
303     __str.remove_suffix(__str.end() - __column_width.__ptr);
304 
305   return __formatter::__write(__str.begin(), __str.end(), _VSTD::move(__out_it), __specs, __size);
306 
307 #  else
308   if (__specs.__has_precision()) {
309     ptrdiff_t __size = __str.size();
310     if (__size > __specs.__precision_)
311       return __formatter::__write(__str.begin(), __str.begin() + __specs.__precision_, _VSTD::move(__out_it), __specs,
312                                   __specs.__precision_);
313   }
314   return __formatter::__write(__str.begin(), __str.end(), _VSTD::move(__out_it), __specs, __str.size());
315 
316 #  endif
317 }
318 
319 } // namespace __formatter
320 
321 #endif //_LIBCPP_STD_VER > 17
322 
323 _LIBCPP_END_NAMESPACE_STD
324 
325 #endif // _LIBCPP___FORMAT_FORMATTER_OUTPUT_H
326