Feature discussion: formatting at compile-time

[alexezeder]

Recently I tried to use {fmt} in compile-time, not some FMT_STRING compile-time checking or FMT_COMPILE compile-time format string, but using fmt::format_to with arguments in compile-time, like this:

#include <fmt/format.h>

constexpr auto get_formatted_string() {
    std::array<char, 30> buffer{};
    fmt::format_to(buffer.data(), "The answer = {}", 42);
    return buffer;
}

int main() {
    constexpr auto formatted_string = get_formatted_string();
    printf("%s", formatted_string.data());
    return 0;
}

In this example compiler should just format "The answer = {}" with argument 42 into formatted_string array at compile-time. But since {fmt} probably was not planned to be used that way there are plenty of compilation errors with this example.

By adding a constexpr keyword where it's needed, replacing some std:: entities to constexpred self-written ones and using C++20 std::is_constant_evaluated to eliminate usages of non-constexpr functions, I was able to format integers and strings into the buffer at compile-time. But then I tried to format a floating point number and realized that code for floating point formatting, besides of using maybe not compile-time friendly algorithms, uses dynamically growing memory_buffer.

Despite I am pretty sure that I will be able to force floating point formatting to work at compile-time some time later, I decide to pause my work on this to get some feedback in advance.

So, will this ability be useful for everyone, or not? Because I was just experimenting, there is no need for me to do formatting in compile time. Are there any similar or worse pitfalls you can think of?

[vitaut]

Floating-point formatting doesn't allocate in the common case. memory_buffer is mostly used for convenience. In general, however, it's hard to make FP formatting constexpr as you'll need to handle all the weird FP formats. {fmt} has the infra to do this even in the general case (multiprecision arithmetic) but it's still a ton of work.

So, will this ability be useful for everyone, or not?

I don't think it will be useful for everyone, but it will probably be useful for someone =). I can think of some use cases, e.g. compile-time error reporting.

Are there any similar or worse pitfalls you can think of?

FP is the most difficult case but pointers and user-defined types will also be problematic.

[alexezeder]

So, will this ability be useful for everyone, or not?

supposed to be anyone, not everyone

Anyway, I will continue my efforts as far as I can. Right now I don't bother to use any checks whatsoever: constexpr (not FMT_CONSTEXPR), std::is_constant_evaluated() without __cpp_lib_is_constant_evaluated check, duplicating some of basic_data fields to make them constexpr and so on, but when I have a version with most of formatting features working, I will redo my work with all this checks and create a pull request (maybe a draft).

And yeah, this would be definitely a C++20 feature, because of std::is_constant_evaluated() and maybe some other compile-time features in this standard. Also because of std::bit_cast(), but yesterday I found out that neither GCC 10 nor Clang 10 have std::bit_cast() implemented, only MSVC has and it doesn't work with trivial pointer-to-uintptr_t-casting code.

[alexezeder]

Small update about remaining non-implemented compile-time formatting features.
There are two features (I'm aware of) that do not work right now - pointers formatting and floating-point formatting.

Pointers

I was hoping for C++20 constexpr std::bit_cast(), but what a bummer it does not work with pointers:

This function template is constexpr if and only if each of To, From and the types of all subobjects of To and From:

• is not a union type;
• is not a pointer type;
• is not a pointer to member type;
• is not a volatile-qualified type; and
• has no non-static data member of reference type.

As far as I know, there are no other options to bit-cast anything at compile-time, so it seems no pointer formatting at compile-time. But I doubt that it's a handy feature.

Floating-point

There were several problems when I started:

• bit_cast() usages - it's not a problem now, for example, GCC trunk has constexpr std::bit_cast() implemented, so fmt::detail::bit_cast() can be constexpr too.
• constexpr allocations/deallocations for memory_buffer usages - again, no problem, both Clang 11 and GCC trunk are able to do this.
• lack of constexpr specifier - this is the main problem here because functions can be marked with constexpr easily, as well as some additional initialization can be added under is_constant_evaluated(), but all static data members are the reason why FP formatting is not implemented yet.

For the latter problem I can propose 3 solutions:

1. Enable FP formatting at compile-time only if FMT_HEADER_ONLY (or some specific) flag is set. It means that {fmt} without this flag won't be able to format FP at compile-time. But when the flag is set, then static data members would be constexpr and their definitions would be placed in format.h.
2. Something similar can be achieved by using duplicates of data fields in functions where some of these fields are needed. I tried to do that in my PRs - Basics of formatting at compile-time based on compile-time API #2019 (comment).
3. Use some fallback FP formatting function. I don't know is it worth it or not to introduce another FP formatting function, but all FP formatting functions in {fmt} I've seen cannot be used as fallbacks: snprintf - not constexpr, Grisu - depends on data, Dragonbox - depends on data, that's all I found. But one thing I'm pretty sure about: this function is gonna be huge to support all presentation types.

This is why I don't really know what to do with this task right now.

Also, I have some thoughts about the current FP formatting implementation in {fmt}, the Grisu one, that is used with almost all specs. I took a quick look at this implementation and I cannot find a reason to format a significant part to separate buffer, considering that a bit later this separate buffer will be copied to the final output buffer with some minor changes. Of course, maybe I just overlooked something.

[vitaut]

Regarding constexpr FP formatting, I think the most feasible approach is to use Dragon4 for everything:

fmt/include/fmt/format-inl.h

Lines 2305 to 2306 in 308510e

	void fallback_format(Double d, int num_digits, bool binary32, buffer<char>& buf,
	int& exp10) {

It will mostly require making bigint constexpr and adding long double support.

I cannot find a reason to format a significant part to separate buffer

We need to allocate the exact amount in the output which is not possible until after we generated digits. It also doesn't matter because the digits are moved around anyway.

[alexezeder]

Hm... looks like I got this function wrong, because for some reason I assumed that snprintf_float() is fallback_format() 🤦.
Nice, at first glance, it looks pretty trivial, and I can work with that 😄.
But does fallback_format() function use Dragon4? I mean, I'm a bit confused because there are Grisu and Dragonbox mentions in code (and a mention of Dragon4, but only in one comment). Also, the link in the comment for fallback_format() is dead, maybe there was some info about that algorithm.

We need to allocate the exact amount in the output which is not possible until after we generated digits.

Sad to say, I didn't research the FP formatting completely, mostly because it seems non-trivial, this is probably why I have these thoughts. Anyway, I just thought maybe digits could be generated on-demand, if there is no dependency between digits, of course. In that case, there would be only one pass instead of two right now: generation of digits and applying format for these digits. Probably I'm not the first person who has this cool optimization idea, but besides that, I'm ignorant of this topic, that's why I don't see a reason to have 2 passes.

[vitaut]

I assumed that snprintf_float() is fallback_format()

snprintf_float() is another kind of fallback =) which we will hopefully get rid one day.

But does fallback_format() function use Dragon4?

Yes, it's Dragon4 with minor tweaks.

the link in the comment for fallback_format() is dead

Fixed, thanks.

digits could be generated on-demand

The problem is that we need to know the number of digits which for the shortest representation is almost as hard to compute as generating the digits themselves. It could be possible to do something for fixed precision representations but I'm not sure it's worth the increased complexity.

[alexezeder]

I'm writing down here my observations about constexpr FP formatting. I started work on this a long time ago in my fork, but I stuck with some problems around the same time. Since I didn't come up with some nifty solutions for these problems yet - I'm sharing these problems here, otherwise, my work would be probably wasted.

• Works only with FMT_HEADER_ONLY
  There are few issues that made me choose to enable constexpr FP formatting only in header-only mode but all of them have one thing in common - they are defined in format-inl.h. They are:
  • format_float()
  • fallback_format()
  • pow10_significands and pow10_exponents
  • class fp
  • etc.
    In other words, many entities related to FP formatting, which were hidden in format-inl.h (probably) to avoid polluting format.h, are required in format.h to be used at compile-time.
• -NaN check with std::signbit doesn't work at compile-time, because std::signbit is not marked as constexpr. Of course, bits & (uint(1) << (num_bits<uint>() - 1)) can be used at compile-time, but it doesn't work for long double for some reason. So only IEC 559 float and double types would be supported.

[vitaut]

Thanks for writing this down.

I think it's OK to initially restrict the feature to the header-only mode. We are moving towards modules anyway so the distinction will eventually become irrelevant.

The reason why the sign check doesn't work for long double is, quoting https://en.wikipedia.org/wiki/Long_double:

On the x86 architecture, most C compilers implement long double as the 80-bit extended precision type supported by x86 hardware (generally stored as 12 or 16 bytes to maintain data structure alignment), as specified in the C99 / C11 standards (IEC 60559 floating-point arithmetic (Annex F)).

So the sign is bit 79, not 127.

[alexezeder]

I keep experimenting with constexprifying {fmt}, and here is another interesting observation. As I mentioned before, theoretically, we can format string at compile-time not once (using the same technique already used in compile-test) but several times. Why you may ask, why not I can answer. Actually, I started working on this because I was disappointed that we can't both precompile some format and use it with the compile-time API, like this:

template <typename Integer> std::string format(Integer value) {
  constexpr auto precompiled_format = test_format<8>(
      FMT_COMPILE("{{:0{}b}}"), std::numeric_limits<Integer>::digits);

  fmt::format(precompiled_format, value);  // doesn't compile,
                                           // but even with some fixes it uses
                                           // runtime API, not compile-time
}

In this particular case, a simple fmt::format with FMT_COMPILE("{{:0{}b}}") call can be used, but it doesn't optimize everything at compile-time, I've checked:

Benchmark                                    Time             CPU   Iterations
------------------------------------------------------------------------------
precompiled_and_compile_time_API/42       19.5 ns         19.5 ns     36298528
precompiled_and_runtime_API/42             118 ns          118 ns      6017488
just_compile_time_API/42                  24.4 ns         24.4 ns     28552738

Here is how the code can look for precompiled formats:

constexpr auto compiled_format0 = FMT_COMPILE("{{:0{}b}}");
  // holds "{{:0{}b}}", nothing interesting here

constexpr auto compiled_format1 = FMT_COMPILE_FORMAT(7, compiled_format0, 8);
  // holds "{:08b}", and it can be passed to fmt::format() directly (compile-time API is used for it)

constexpr auto compiled_format2 = FMT_COMPILE_FORMAT(9, compiled_format1, 3);
  // holds "00000011", there is no much sense to pass it to fmt::format(), but it can be passed 😏

where FMT_COMPILE_FORMAT is:

#  define FMT_COMPILE_FORMAT(buffer_size, format, ...)                        \
    [&]() {                                                                   \
      struct static_compiled_format : fmt::detail::compiled_string {          \
        using underlying_type = decltype(format);                             \
        using char_type = underlying_type::char_type;                         \
                                                                              \
        std::array<char_type, buffer_size> buffer;                            \
                                                                              \
        constexpr static_compiled_format()                                    \
            : buffer([]() {                                                   \
                auto temp_buffer = decltype(buffer){};                        \
                fmt::format_to(temp_buffer.data(), underlying_type{},         \
                               __VA_ARGS__);                                  \
                return temp_buffer;                                           \
              }()) {}                                                         \
                                                                              \
        constexpr explicit operator fmt::basic_string_view<char_type>()       \
            const {                                                           \
          return {buffer.data(), buffer.size()};                              \
        }                                                                     \
                                                                              \
        [[nodiscard]] constexpr static_compiled_format to_str() const {       \
          return {};                                                          \
        }                                                                     \
                                                                              \
        [[nodiscard]] constexpr size_t size() const { return buffer.size(); } \
                                                                              \
        constexpr auto operator[](size_t pos) const -> const char_type& {     \
          return buffer[pos];                                                 \
        }                                                                     \
      };                                                                      \
      return static_compiled_format{};                                        \
    }()

As you can see, there are some new methods for handling this class inside compile-time API, since we can work at compile-time with string literals easily, but not with static char buffers 🤦. The most important method here is to_str() since it has to be added for all compiled_strings, for string literals, it just returns their pointers, for everything else, it returns a new instance of this static buffer. For example, here is this method for FMT_STRING_IMPL and udl_compiled_string classes:

  [[nodiscard]] constexpr auto to_str() const {
    return fmt::basic_string_view<char_type>(*this);
  }

AFAICS there are no more straightforward examples for this functionality. There is how it looks right now, it has some workarounds, but they can be fixed later. Anyway, I don't know if it's even worth adding, or maybe it can be implemented in a much better way.

[vitaut]

Interesting idea. Does FMT_COMPILE_FORMAT have to be a macro?

[alexezeder]

Sorry, I didn't have time to check it out and answer earlier.

Does FMT_COMPILE_FORMAT have to be a macro?

This idea can actually be implemented using templates instead of macros, thanks to non-type template parameters. In this case usages look something like:

constexpr auto compiled_format0 = FMT_COMPILE("{{:0{}b}}");
constexpr auto compiled_format_1 =
    templaty_compiled_format<7, compiled_format0, 8>{};
constexpr auto compiled_format_2 =
    templaty_compiled_format<9, compiled_format_templaty_1, 3>{};

where templaty_compiled_format (the name is subject to change 😏) looks like this:

template <size_t buffer_size, auto format_string, auto... args>
struct templaty_compiled_format : fmt::detail::compiled_string {
  using format_string_type = decltype(format_string);
  using char_type = format_string_type::char_type;

  static constexpr auto buffer = []() {
    auto temp_buffer = std::array<char_type, buffer_size>{};
    fmt::format_to(temp_buffer.data(), format_string_type{}, args...);
    return temp_buffer;
  }();

  // remaining methods look the same as in the macro version
};

For me, it looks cleaner than the macro version. I guess it's mainly because of having the formatted result in the static constexpr variable instead of recreating it inside the constructor. But the macro version cannot have a static constexpr variable inside, since the macro defines a local class.

BUT! As I already mentioned, this implementation is based on non-type template parameters that have some quirks. Here is an example:

constexpr auto cf0 = FMT_COMPILE("{}{}");

// this works fine
constexpr auto cf1 = FMT_COMPILE_FORMAT(7, cf0, "foo", "bar");

// this doesn't compile because pointers to string literals are not allowed in template-parameters
constexpr auto cf1 = templaty_compiled_format<7, cf0, "foo", "bar">{};

// this may work, but `fixed_string` should become formattable first
using namespace fmt::detail_exported;
constexpr auto cf1 = templaty_compiled_format<7, cf0, fixed_string("foo"), fixed_string("bar")>{};

Also, non-type template parameters can be only literal types with additional restrictions, from cppreference:

A non-type template parameter must have a structural type, which is one of the following types (optionally cv-qualified, the qualifiers are ignored):

• a literal class type with the following properties:
  • all base classes and non-static data members are public and non-mutable and
  • the types of all base classes and non-static data members are structural types or (possibly multi-dimensional) array thereof.

So it really limits the types that could be passed as arguments for formatting. This way, some custom types would be unavailable, while the macro version theoretically works with them fine.

Anyway, this templaty version already works just fine, but of course, with the same workarounds as the macro version does right now, and only for trivial types.