1 // Formatting library for C++ - experimental format string compilation
2 //
3 // Copyright (c) 2012 - present, Victor Zverovich and fmt contributors
4 // All rights reserved.
5 //
6 // For the license information refer to format.h.
7
8 #ifndef FMT_COMPILE_H_
9 #define FMT_COMPILE_H_
10
11 #include <vector>
12
13 #include "format.h"
14
15 FMT_BEGIN_NAMESPACE
16 namespace internal {
17
18 // Part of a compiled format string. It can be either literal text or a
19 // replacement field.
20 template <typename Char> struct format_part {
21 enum class kind { arg_index, arg_name, text, replacement };
22
23 struct replacement {
24 arg_ref<Char> arg_id;
25 dynamic_format_specs<Char> specs;
26 };
27
28 kind part_kind;
29 union value {
30 int arg_index;
31 basic_string_view<Char> str;
32 replacement repl;
33
arg_index(index)34 FMT_CONSTEXPR value(int index = 0) : arg_index(index) {}
value(basic_string_view<Char> s)35 FMT_CONSTEXPR value(basic_string_view<Char> s) : str(s) {}
value(replacement r)36 FMT_CONSTEXPR value(replacement r) : repl(r) {}
37 } val;
38 // Position past the end of the argument id.
39 const Char* arg_id_end = nullptr;
40
41 FMT_CONSTEXPR format_part(kind k = kind::arg_index, value v = {})
part_kindformat_part42 : part_kind(k), val(v) {}
43
make_arg_indexformat_part44 static FMT_CONSTEXPR format_part make_arg_index(int index) {
45 return format_part(kind::arg_index, index);
46 }
make_arg_nameformat_part47 static FMT_CONSTEXPR format_part make_arg_name(basic_string_view<Char> name) {
48 return format_part(kind::arg_name, name);
49 }
make_textformat_part50 static FMT_CONSTEXPR format_part make_text(basic_string_view<Char> text) {
51 return format_part(kind::text, text);
52 }
make_replacementformat_part53 static FMT_CONSTEXPR format_part make_replacement(replacement repl) {
54 return format_part(kind::replacement, repl);
55 }
56 };
57
58 template <typename Char> struct part_counter {
59 unsigned num_parts = 0;
60
on_textpart_counter61 FMT_CONSTEXPR void on_text(const Char* begin, const Char* end) {
62 if (begin != end) ++num_parts;
63 }
64
on_arg_idpart_counter65 FMT_CONSTEXPR void on_arg_id() { ++num_parts; }
on_arg_idpart_counter66 FMT_CONSTEXPR void on_arg_id(int) { ++num_parts; }
on_arg_idpart_counter67 FMT_CONSTEXPR void on_arg_id(basic_string_view<Char>) { ++num_parts; }
68
on_replacement_fieldpart_counter69 FMT_CONSTEXPR void on_replacement_field(const Char*) {}
70
on_format_specspart_counter71 FMT_CONSTEXPR const Char* on_format_specs(const Char* begin,
72 const Char* end) {
73 // Find the matching brace.
74 unsigned brace_counter = 0;
75 for (; begin != end; ++begin) {
76 if (*begin == '{') {
77 ++brace_counter;
78 } else if (*begin == '}') {
79 if (brace_counter == 0u) break;
80 --brace_counter;
81 }
82 }
83 return begin;
84 }
85
on_errorpart_counter86 FMT_CONSTEXPR void on_error(const char*) {}
87 };
88
89 // Counts the number of parts in a format string.
90 template <typename Char>
count_parts(basic_string_view<Char> format_str)91 FMT_CONSTEXPR unsigned count_parts(basic_string_view<Char> format_str) {
92 part_counter<Char> counter;
93 parse_format_string<true>(format_str, counter);
94 return counter.num_parts;
95 }
96
97 template <typename Char, typename PartHandler>
98 class format_string_compiler : public error_handler {
99 private:
100 using part = format_part<Char>;
101
102 PartHandler handler_;
103 part part_;
104 basic_string_view<Char> format_str_;
105 basic_format_parse_context<Char> parse_context_;
106
107 public:
format_string_compiler(basic_string_view<Char> format_str,PartHandler handler)108 FMT_CONSTEXPR format_string_compiler(basic_string_view<Char> format_str,
109 PartHandler handler)
110 : handler_(handler),
111 format_str_(format_str),
112 parse_context_(format_str) {}
113
on_text(const Char * begin,const Char * end)114 FMT_CONSTEXPR void on_text(const Char* begin, const Char* end) {
115 if (begin != end)
116 handler_(part::make_text({begin, to_unsigned(end - begin)}));
117 }
118
on_arg_id()119 FMT_CONSTEXPR void on_arg_id() {
120 part_ = part::make_arg_index(parse_context_.next_arg_id());
121 }
122
on_arg_id(int id)123 FMT_CONSTEXPR void on_arg_id(int id) {
124 parse_context_.check_arg_id(id);
125 part_ = part::make_arg_index(id);
126 }
127
on_arg_id(basic_string_view<Char> id)128 FMT_CONSTEXPR void on_arg_id(basic_string_view<Char> id) {
129 part_ = part::make_arg_name(id);
130 }
131
on_replacement_field(const Char * ptr)132 FMT_CONSTEXPR void on_replacement_field(const Char* ptr) {
133 part_.arg_id_end = ptr;
134 handler_(part_);
135 }
136
on_format_specs(const Char * begin,const Char * end)137 FMT_CONSTEXPR const Char* on_format_specs(const Char* begin,
138 const Char* end) {
139 auto repl = typename part::replacement();
140 dynamic_specs_handler<basic_format_parse_context<Char>> handler(
141 repl.specs, parse_context_);
142 auto it = parse_format_specs(begin, end, handler);
143 if (*it != '}') on_error("missing '}' in format string");
144 repl.arg_id = part_.part_kind == part::kind::arg_index
145 ? arg_ref<Char>(part_.val.arg_index)
146 : arg_ref<Char>(part_.val.str);
147 auto part = part::make_replacement(repl);
148 part.arg_id_end = begin;
149 handler_(part);
150 return it;
151 }
152 };
153
154 // Compiles a format string and invokes handler(part) for each parsed part.
155 template <bool IS_CONSTEXPR, typename Char, typename PartHandler>
compile_format_string(basic_string_view<Char> format_str,PartHandler handler)156 FMT_CONSTEXPR void compile_format_string(basic_string_view<Char> format_str,
157 PartHandler handler) {
158 parse_format_string<IS_CONSTEXPR>(
159 format_str,
160 format_string_compiler<Char, PartHandler>(format_str, handler));
161 }
162
163 template <typename Range, typename Context, typename Id>
format_arg(basic_format_parse_context<typename Range::value_type> & parse_ctx,Context & ctx,Id arg_id)164 void format_arg(
165 basic_format_parse_context<typename Range::value_type>& parse_ctx,
166 Context& ctx, Id arg_id) {
167 ctx.advance_to(
168 visit_format_arg(arg_formatter<Range>(ctx, &parse_ctx), ctx.arg(arg_id)));
169 }
170
171 // vformat_to is defined in a subnamespace to prevent ADL.
172 namespace cf {
173 template <typename Context, typename Range, typename CompiledFormat>
174 auto vformat_to(Range out, CompiledFormat& cf, basic_format_args<Context> args)
175 -> typename Context::iterator {
176 using char_type = typename Context::char_type;
177 basic_format_parse_context<char_type> parse_ctx(
178 to_string_view(cf.format_str_));
179 Context ctx(out.begin(), args);
180
181 const auto& parts = cf.parts();
182 for (auto part_it = std::begin(parts); part_it != std::end(parts);
183 ++part_it) {
184 const auto& part = *part_it;
185 const auto& value = part.val;
186
187 using format_part_t = format_part<char_type>;
188 switch (part.part_kind) {
189 case format_part_t::kind::text: {
190 const auto text = value.str;
191 auto output = ctx.out();
192 auto&& it = reserve(output, text.size());
193 it = std::copy_n(text.begin(), text.size(), it);
194 ctx.advance_to(output);
195 break;
196 }
197
198 case format_part_t::kind::arg_index:
199 advance_to(parse_ctx, part.arg_id_end);
200 internal::format_arg<Range>(parse_ctx, ctx, value.arg_index);
201 break;
202
203 case format_part_t::kind::arg_name:
204 advance_to(parse_ctx, part.arg_id_end);
205 internal::format_arg<Range>(parse_ctx, ctx, value.str);
206 break;
207
208 case format_part_t::kind::replacement: {
209 const auto& arg_id_value = value.repl.arg_id.val;
210 const auto arg = value.repl.arg_id.kind == arg_id_kind::index
211 ? ctx.arg(arg_id_value.index)
212 : ctx.arg(arg_id_value.name);
213
214 auto specs = value.repl.specs;
215
216 handle_dynamic_spec<width_checker>(specs.width, specs.width_ref, ctx);
217 handle_dynamic_spec<precision_checker>(specs.precision,
218 specs.precision_ref, ctx);
219
220 error_handler h;
221 numeric_specs_checker<error_handler> checker(h, arg.type());
222 if (specs.align == align::numeric) checker.require_numeric_argument();
223 if (specs.sign != sign::none) checker.check_sign();
224 if (specs.alt) checker.require_numeric_argument();
225 if (specs.precision >= 0) checker.check_precision();
226
227 advance_to(parse_ctx, part.arg_id_end);
228 ctx.advance_to(
229 visit_format_arg(arg_formatter<Range>(ctx, nullptr, &specs), arg));
230 break;
231 }
232 }
233 }
234 return ctx.out();
235 }
236 } // namespace cf
237
238 struct basic_compiled_format {};
239
240 template <typename S, typename = void>
241 struct compiled_format_base : basic_compiled_format {
242 using char_type = char_t<S>;
243 using parts_container = std::vector<internal::format_part<char_type>>;
244
245 parts_container compiled_parts;
246
compiled_format_basecompiled_format_base247 explicit compiled_format_base(basic_string_view<char_type> format_str) {
248 compile_format_string<false>(format_str,
249 [this](const format_part<char_type>& part) {
250 compiled_parts.push_back(part);
251 });
252 }
253
partscompiled_format_base254 const parts_container& parts() const { return compiled_parts; }
255 };
256
257 template <typename Char, unsigned N> struct format_part_array {
258 format_part<Char> data[N] = {};
259 FMT_CONSTEXPR format_part_array() = default;
260 };
261
262 template <typename Char, unsigned N>
compile_to_parts(basic_string_view<Char> format_str)263 FMT_CONSTEXPR format_part_array<Char, N> compile_to_parts(
264 basic_string_view<Char> format_str) {
265 format_part_array<Char, N> parts;
266 unsigned counter = 0;
267 // This is not a lambda for compatibility with older compilers.
268 struct {
269 format_part<Char>* parts;
270 unsigned* counter;
271 FMT_CONSTEXPR void operator()(const format_part<Char>& part) {
272 parts[(*counter)++] = part;
273 }
274 } collector{parts.data, &counter};
275 compile_format_string<true>(format_str, collector);
276 if (counter < N) {
277 parts.data[counter] =
278 format_part<Char>::make_text(basic_string_view<Char>());
279 }
280 return parts;
281 }
282
constexpr_max(const T & a,const T & b)283 template <typename T> constexpr const T& constexpr_max(const T& a, const T& b) {
284 return (a < b) ? b : a;
285 }
286
287 template <typename S>
288 struct compiled_format_base<S, enable_if_t<is_compile_string<S>::value>>
289 : basic_compiled_format {
290 using char_type = char_t<S>;
291
292 FMT_CONSTEXPR explicit compiled_format_base(basic_string_view<char_type>) {}
293
294 // Workaround for old compilers. Format string compilation will not be
295 // performed there anyway.
296 #if FMT_USE_CONSTEXPR
297 static FMT_CONSTEXPR_DECL const unsigned num_format_parts =
298 constexpr_max(count_parts(to_string_view(S())), 1u);
299 #else
300 static const unsigned num_format_parts = 1;
301 #endif
302
303 using parts_container = format_part<char_type>[num_format_parts];
304
305 const parts_container& parts() const {
306 static FMT_CONSTEXPR_DECL const auto compiled_parts =
307 compile_to_parts<char_type, num_format_parts>(
308 internal::to_string_view(S()));
309 return compiled_parts.data;
310 }
311 };
312
313 template <typename S, typename... Args>
314 class compiled_format : private compiled_format_base<S> {
315 public:
316 using typename compiled_format_base<S>::char_type;
317
318 private:
319 basic_string_view<char_type> format_str_;
320
321 template <typename Context, typename Range, typename CompiledFormat>
322 friend auto cf::vformat_to(Range out, CompiledFormat& cf,
323 basic_format_args<Context> args) ->
324 typename Context::iterator;
325
326 public:
327 compiled_format() = delete;
328 explicit constexpr compiled_format(basic_string_view<char_type> format_str)
329 : compiled_format_base<S>(format_str), format_str_(format_str) {}
330 };
331
332 #ifdef __cpp_if_constexpr
333 template <typename... Args> struct type_list {};
334
335 // Returns a reference to the argument at index N from [first, rest...].
336 template <int N, typename T, typename... Args>
337 constexpr const auto& get(const T& first, const Args&... rest) {
338 static_assert(N < 1 + sizeof...(Args), "index is out of bounds");
339 if constexpr (N == 0)
340 return first;
341 else
342 return get<N - 1>(rest...);
343 }
344
345 template <int N, typename> struct get_type_impl;
346
347 template <int N, typename... Args> struct get_type_impl<N, type_list<Args...>> {
348 using type = remove_cvref_t<decltype(get<N>(std::declval<Args>()...))>;
349 };
350
351 template <int N, typename T>
352 using get_type = typename get_type_impl<N, T>::type;
353
354 template <typename T> struct is_compiled_format : std::false_type {};
355
356 template <typename Char> struct text {
357 basic_string_view<Char> data;
358 using char_type = Char;
359
360 template <typename OutputIt, typename... Args>
361 OutputIt format(OutputIt out, const Args&...) const {
362 // TODO: reserve
363 return copy_str<Char>(data.begin(), data.end(), out);
364 }
365 };
366
367 template <typename Char>
368 struct is_compiled_format<text<Char>> : std::true_type {};
369
370 template <typename Char>
371 constexpr text<Char> make_text(basic_string_view<Char> s, size_t pos,
372 size_t size) {
373 return {{&s[pos], size}};
374 }
375
376 template <typename Char, typename OutputIt, typename T,
377 std::enable_if_t<std::is_integral_v<T>, int> = 0>
378 OutputIt format_default(OutputIt out, T value) {
379 // TODO: reserve
380 format_int fi(value);
381 return std::copy(fi.data(), fi.data() + fi.size(), out);
382 }
383
384 template <typename Char, typename OutputIt>
385 OutputIt format_default(OutputIt out, double value) {
386 writer w(out);
387 w.write(value);
388 return w.out();
389 }
390
391 template <typename Char, typename OutputIt>
392 OutputIt format_default(OutputIt out, Char value) {
393 *out++ = value;
394 return out;
395 }
396
397 template <typename Char, typename OutputIt>
398 OutputIt format_default(OutputIt out, const Char* value) {
399 auto length = std::char_traits<Char>::length(value);
400 return copy_str<Char>(value, value + length, out);
401 }
402
403 // A replacement field that refers to argument N.
404 template <typename Char, typename T, int N> struct field {
405 using char_type = Char;
406
407 template <typename OutputIt, typename... Args>
408 OutputIt format(OutputIt out, const Args&... args) const {
409 // This ensures that the argument type is convertile to `const T&`.
410 const T& arg = get<N>(args...);
411 return format_default<Char>(out, arg);
412 }
413 };
414
415 template <typename Char, typename T, int N>
416 struct is_compiled_format<field<Char, T, N>> : std::true_type {};
417
418 template <typename L, typename R> struct concat {
419 L lhs;
420 R rhs;
421 using char_type = typename L::char_type;
422
423 template <typename OutputIt, typename... Args>
424 OutputIt format(OutputIt out, const Args&... args) const {
425 out = lhs.format(out, args...);
426 return rhs.format(out, args...);
427 }
428 };
429
430 template <typename L, typename R>
431 struct is_compiled_format<concat<L, R>> : std::true_type {};
432
433 template <typename L, typename R>
434 constexpr concat<L, R> make_concat(L lhs, R rhs) {
435 return {lhs, rhs};
436 }
437
438 struct unknown_format {};
439
440 template <typename Char>
441 constexpr size_t parse_text(basic_string_view<Char> str, size_t pos) {
442 for (size_t size = str.size(); pos != size; ++pos) {
443 if (str[pos] == '{' || str[pos] == '}') break;
444 }
445 return pos;
446 }
447
448 template <typename Args, size_t POS, int ID, typename S>
449 constexpr auto compile_format_string(S format_str);
450
451 template <typename Args, size_t POS, int ID, typename T, typename S>
452 constexpr auto parse_tail(T head, S format_str) {
453 if constexpr (POS != to_string_view(format_str).size()) {
454 constexpr auto tail = compile_format_string<Args, POS, ID>(format_str);
455 if constexpr (std::is_same<remove_cvref_t<decltype(tail)>,
456 unknown_format>())
457 return tail;
458 else
459 return make_concat(head, tail);
460 } else {
461 return head;
462 }
463 }
464
465 // Compiles a non-empty format string and returns the compiled representation
466 // or unknown_format() on unrecognized input.
467 template <typename Args, size_t POS, int ID, typename S>
468 constexpr auto compile_format_string(S format_str) {
469 using char_type = typename S::char_type;
470 constexpr basic_string_view<char_type> str = format_str;
471 if constexpr (str[POS] == '{') {
472 if (POS + 1 == str.size())
473 throw format_error("unmatched '{' in format string");
474 if constexpr (str[POS + 1] == '{') {
475 return parse_tail<Args, POS + 2, ID>(make_text(str, POS, 1), format_str);
476 } else if constexpr (str[POS + 1] == '}') {
477 using type = get_type<ID, Args>;
478 if constexpr (std::is_same<type, int>::value) {
479 return parse_tail<Args, POS + 2, ID + 1>(field<char_type, type, ID>(),
480 format_str);
481 } else {
482 return unknown_format();
483 }
484 } else {
485 return unknown_format();
486 }
487 } else if constexpr (str[POS] == '}') {
488 if (POS + 1 == str.size())
489 throw format_error("unmatched '}' in format string");
490 return parse_tail<Args, POS + 2, ID>(make_text(str, POS, 1), format_str);
491 } else {
492 constexpr auto end = parse_text(str, POS + 1);
493 return parse_tail<Args, end, ID>(make_text(str, POS, end - POS),
494 format_str);
495 }
496 }
497 #endif // __cpp_if_constexpr
498 } // namespace internal
499
500 #if FMT_USE_CONSTEXPR
501 # ifdef __cpp_if_constexpr
502 template <typename... Args, typename S,
503 FMT_ENABLE_IF(is_compile_string<S>::value)>
504 constexpr auto compile(S format_str) {
505 constexpr basic_string_view<typename S::char_type> str = format_str;
506 if constexpr (str.size() == 0) {
507 return internal::make_text(str, 0, 0);
508 } else {
509 constexpr auto result =
510 internal::compile_format_string<internal::type_list<Args...>, 0, 0>(
511 format_str);
512 if constexpr (std::is_same<remove_cvref_t<decltype(result)>,
513 internal::unknown_format>()) {
514 return internal::compiled_format<S, Args...>(to_string_view(format_str));
515 } else {
516 return result;
517 }
518 }
519 }
520
521 template <typename CompiledFormat, typename... Args,
522 typename Char = typename CompiledFormat::char_type,
523 FMT_ENABLE_IF(internal::is_compiled_format<CompiledFormat>::value)>
524 std::basic_string<Char> format(const CompiledFormat& cf, const Args&... args) {
525 basic_memory_buffer<Char> buffer;
526 cf.format(std::back_inserter(buffer), args...);
527 return to_string(buffer);
528 }
529
530 template <typename OutputIt, typename CompiledFormat, typename... Args,
531 FMT_ENABLE_IF(internal::is_compiled_format<CompiledFormat>::value)>
532 OutputIt format_to(OutputIt out, const CompiledFormat& cf,
533 const Args&... args) {
534 return cf.format(out, args...);
535 }
536 # else
537 template <typename... Args, typename S,
538 FMT_ENABLE_IF(is_compile_string<S>::value)>
539 constexpr auto compile(S format_str) -> internal::compiled_format<S, Args...> {
540 return internal::compiled_format<S, Args...>(to_string_view(format_str));
541 }
542 # endif // __cpp_if_constexpr
543 #endif // FMT_USE_CONSTEXPR
544
545 // Compiles the format string which must be a string literal.
546 template <typename... Args, typename Char, size_t N>
547 auto compile(const Char (&format_str)[N])
548 -> internal::compiled_format<const Char*, Args...> {
549 return internal::compiled_format<const Char*, Args...>(
550 basic_string_view<Char>(format_str, N - 1));
551 }
552
553 template <typename CompiledFormat, typename... Args,
554 typename Char = typename CompiledFormat::char_type,
555 FMT_ENABLE_IF(std::is_base_of<internal::basic_compiled_format,
556 CompiledFormat>::value)>
557 std::basic_string<Char> format(const CompiledFormat& cf, const Args&... args) {
558 basic_memory_buffer<Char> buffer;
559 using range = buffer_range<Char>;
560 using context = buffer_context<Char>;
561 internal::cf::vformat_to<context>(range(buffer), cf,
562 make_format_args<context>(args...));
563 return to_string(buffer);
564 }
565
566 template <typename OutputIt, typename CompiledFormat, typename... Args,
567 FMT_ENABLE_IF(std::is_base_of<internal::basic_compiled_format,
568 CompiledFormat>::value)>
569 OutputIt format_to(OutputIt out, const CompiledFormat& cf,
570 const Args&... args) {
571 using char_type = typename CompiledFormat::char_type;
572 using range = internal::output_range<OutputIt, char_type>;
573 using context = format_context_t<OutputIt, char_type>;
574 return internal::cf::vformat_to<context>(range(out), cf,
575 make_format_args<context>(args...));
576 }
577
578 template <typename OutputIt, typename CompiledFormat, typename... Args,
579 FMT_ENABLE_IF(internal::is_output_iterator<OutputIt>::value)>
580 format_to_n_result<OutputIt> format_to_n(OutputIt out, size_t n,
581 const CompiledFormat& cf,
582 const Args&... args) {
583 auto it =
584 format_to(internal::truncating_iterator<OutputIt>(out, n), cf, args...);
585 return {it.base(), it.count()};
586 }
587
588 template <typename CompiledFormat, typename... Args>
589 std::size_t formatted_size(const CompiledFormat& cf, const Args&... args) {
590 return format_to(internal::counting_iterator(), cf, args...).count();
591 }
592
593 FMT_END_NAMESPACE
594
595 #endif // FMT_COMPILE_H_
596