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_FORMAT_STRING_H
11#define _LIBCPP___FORMAT_FORMAT_STRING_H
12
13#include <__assert>
14#include <__config>
15#include <__cstddef/size_t.h>
16#include <__format/format_error.h>
17#include <__iterator/concepts.h>
18#include <__iterator/iterator_traits.h> // iter_value_t
19#include <cstdint>
20
21#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
22# pragma GCC system_header
23#endif
24
25_LIBCPP_BEGIN_NAMESPACE_STD
26
27#if _LIBCPP_STD_VER >= 20
28
29namespace __format {
30
31template <contiguous_iterator _Iterator>
32struct __parse_number_result {
33 _Iterator __last;
34 uint32_t __value;
35};
36
37template <contiguous_iterator _Iterator>
38__parse_number_result(_Iterator, uint32_t) -> __parse_number_result<_Iterator>;
39
40template <contiguous_iterator _Iterator>
41constexpr __parse_number_result<_Iterator> __parse_number(_Iterator __begin, _Iterator __end);
42
43/**
44 * The maximum value of a numeric argument.
45 *
46 * This is used for:
47 * * arg-id
48 * * width as value or arg-id.
49 * * precision as value or arg-id.
50 *
51 * The value is compatible with the maximum formatting width and precision
52 * using the `%*` syntax on a 32-bit system.
53 */
54inline constexpr uint32_t __number_max = INT32_MAX;
55
56namespace __detail {
57template <contiguous_iterator _Iterator>
58constexpr __parse_number_result<_Iterator> __parse_zero(_Iterator __begin, _Iterator, auto& __parse_ctx) {
59 __parse_ctx.check_arg_id(0);
60 return {++__begin, 0}; // can never be larger than the maximum.
61}
62
63template <contiguous_iterator _Iterator>
64constexpr __parse_number_result<_Iterator> __parse_automatic(_Iterator __begin, _Iterator, auto& __parse_ctx) {
65 size_t __value = __parse_ctx.next_arg_id();
66 _LIBCPP_ASSERT_UNCATEGORIZED(__value <= __number_max, "Compilers don't support this number of arguments");
67
68 return {__begin, uint32_t(__value)};
69}
70
71template <contiguous_iterator _Iterator>
72constexpr __parse_number_result<_Iterator> __parse_manual(_Iterator __begin, _Iterator __end, auto& __parse_ctx) {
73 __parse_number_result<_Iterator> __r = __format::__parse_number(__begin, __end);
74 __parse_ctx.check_arg_id(__r.__value);
75 return __r;
76}
77
78} // namespace __detail
79
80/**
81 * Parses a number.
82 *
83 * The number is used for the 31-bit values @em width and @em precision. This
84 * allows a maximum value of 2147483647.
85 */
86template <contiguous_iterator _Iterator>
87constexpr __parse_number_result<_Iterator> __parse_number(_Iterator __begin, _Iterator __end_input) {
88 using _CharT = iter_value_t<_Iterator>;
89 static_assert(__format::__number_max == INT32_MAX, "The algorithm is implemented based on this value.");
90 /*
91 * Limit the input to 9 digits, otherwise we need two checks during every
92 * iteration:
93 * - Are we at the end of the input?
94 * - Does the value exceed width of an uint32_t? (Switching to uint64_t would
95 * have the same issue, but with a higher maximum.)
96 */
97 _Iterator __end = __end_input - __begin > 9 ? __begin + 9 : __end_input;
98 uint32_t __value = *__begin - _CharT('0');
99 while (++__begin != __end) {
100 if (*__begin < _CharT('0') || *__begin > _CharT('9'))
101 return {__begin, __value};
102
103 __value = __value * 10 + *__begin - _CharT('0');
104 }
105
106 if (__begin != __end_input && *__begin >= _CharT('0') && *__begin <= _CharT('9')) {
107 /*
108 * There are more than 9 digits, do additional validations:
109 * - Does the 10th digit exceed the maximum allowed value?
110 * - Are there more than 10 digits?
111 * (More than 10 digits always overflows the maximum.)
112 */
113 uint64_t __v = uint64_t(__value) * 10 + *__begin++ - _CharT('0');
114 if (__v > __number_max || (__begin != __end_input && *__begin >= _CharT('0') && *__begin <= _CharT('9')))
115 std::__throw_format_error(s: "The numeric value of the format specifier is too large");
116
117 __value = __v;
118 }
119
120 return {__begin, __value};
121}
122
123/**
124 * Multiplexer for all parse functions.
125 *
126 * The parser will return a pointer beyond the last consumed character. This
127 * should be the closing '}' of the arg-id.
128 */
129template <contiguous_iterator _Iterator>
130constexpr __parse_number_result<_Iterator> __parse_arg_id(_Iterator __begin, _Iterator __end, auto& __parse_ctx) {
131 using _CharT = iter_value_t<_Iterator>;
132 switch (*__begin) {
133 case _CharT('0'):
134 return __detail::__parse_zero(__begin, __end, __parse_ctx);
135
136 case _CharT(':'):
137 // This case is conditionally valid. It's allowed in an arg-id in the
138 // replacement-field, but not in the std-format-spec. The caller can
139 // provide a better diagnostic, so accept it here unconditionally.
140 case _CharT('}'):
141 return __detail::__parse_automatic(__begin, __end, __parse_ctx);
142 }
143 if (*__begin < _CharT('0') || *__begin > _CharT('9'))
144 std::__throw_format_error(s: "The argument index starts with an invalid character");
145
146 return __detail::__parse_manual(__begin, __end, __parse_ctx);
147}
148
149} // namespace __format
150
151#endif // _LIBCPP_STD_VER >= 20
152
153_LIBCPP_END_NAMESPACE_STD
154
155#endif // _LIBCPP___FORMAT_FORMAT_STRING_H
156