Adventures in returning value-dependent type

Hello, everyone. Long time no post. Hopefully, it won’t be another two years before I post again.

The ask

A few nights ago a friend asked me if I had any idea how to make his magic macro work. The general idea behind it was simple: for strings known at the compile time, return type parametrized on the string hash; otherwise return a runtime type. He even provided the type trait he uses to determine if we’re dealing with a string literal. It works well for his case and its potential wrongness is not the point of this article.

Code

The point was something else: let us define a macro NAME and classes Const<size_t> and Runtime, such that the following is valid code:

std::string runtime;
std::cin >> runtime;
 
auto c = NAME("KrzaQ");
auto r = NAME(runtime);
 
// 9546715638267443724UL is fnv1a64("KrzaQ");
static_assert(std::is_same<decltype(c), Const<9546715638267443724UL>>{});
static_assert(std::is_same<decltype(r), Runtime<std::string>>{});

Always willing to help, I sat down to show him how the C++20 solution would like, then how to do a simple tag-dispatch, and to see if the macro could be replaced with a function call.

Or so I thought.

The dream C++@@ solution

My first instinct was to say “here’s how you do it in C++20”:

template<typename T>
constexpr auto name(T&& t)
{
    if constexpr(std::is_constant_evaluated()) {
        return Const<fnv1a64(t)>{};
    } else {
        return Runtime{std::forward<T>(t)};
    }
}

Simple, readable and just overall pretty great. Except for one thing: this code does not work. And more than that – this does not work on multiple levels:

  • if constexpr and std::is_constant_evaluated() do not play well together. If you want this check to be actually meaningful, you have to lose constexpr. And then, you must return the same type…
  • t is not a constant expression. (before you ask: I tried proxying this to a consteval function, but I had no luck making it work)
  • You can’t go back from value to type (as far as I know). Even if the value is constant, you can’t make it a type parameter anymore.

What about good ol’ tag dispatch?

Okay, so maybe the C++20 solution is not up to par. Let’s try a simple tag-dispatch solution:

namespace detail
{
 
template<typename T>
constexpr auto name(T&&, std::true_type)
{
    // placeholder
    return Const<0>{};
}
 
template<typename T>
auto name(T&& t, std::false_type)
{
    return Runtime{std::forward<T>(t)};
}
 
}
 
tempalte<typename T>
auto name(T&& t)
{
    using tag = detail::IsStringLiteral<T>;
    return detail::name(std::forward<T>(t), tag{});
}

… wait. At this point, I am hitting the chicken and egg problem. To return Const<hash_value> I must pass it through the tag (I cannot use the value to compute it and have it affect the return type). But if I have it in the tag, I don’t need the dispatched function in the first place! And I can’t compute this hash in the parent function, because it’s impossible to do it for run-time strings.

Back to the beginning

Let’s re-examine the code I received from my friend.

The string literal detector (note: this is not the focus of this article. I understand it can be cheated):

template< typename T >
struct IsStringLiteral :
    std::is_same<
        T,
        std::add_lvalue_reference_t<
            const char[std::extent<std::remove_reference_t<T>>{}]
        >
    >
{};

and the macro (code slightly anonymized):

#define NAME(x) \
    std::conditional_t< \
        detail::IsStringLiteral<decltype(x)>{}, \
        ConstBuilder<CalculateHash64(x)>, \
        RuntimeBuilder \
    >::Build(x)

This version hits the problem of having to instantiate the ConstBuilder type, which requires calculation of the hash. That is not possible for runtime strings. To combat this problem, we should delay hash computation until after the conditional has done its job.

Okay, so let’s define two classes: ConstBuilder and RuntimeBuilder, that offer the same interface, but with different behavior. The usage would be as follows: Builder::make<Builder::hash(x)>(x). The template parameter to provide the hash value for the constant option, and the function parameter to pass the value for the runtime strings. The constant builder class would compute the true hash value and ignore the value parameter, while the runtime builder would always return 0 for the hash (or any number, since it doesn’t matter), and construct a Runtime object, passing it the actual value.

The implementation is fairly simple:

struct ConstBuilder
{
    template<typename T>
    constexpr static size_t hash(T&& t) {
        return ::hash(std::forward<T>(t));
    }
 
    template<size_t N>
    using type = Const<N>;
 
    template<size_t N, typename T>
    static constexpr type<N> make(T&&) {
        return {};
    }
};
 
struct RuntimeBuilder
{
    template<typename T>
    constexpr static size_t hash(T&&) {
        return 0;
    }
 
    template<typename T>
    using type = Runtime<T>;
 
    template<size_t N, typename T>
    static type<decay_t<T>> make(T&& t) {
        return { std::forward<T>(t) };
    }
};

And the macro:

#define NAME( x ) \
    std::conditional_t< \
        detail::IsStringLiteral< decltype( x ) >{}, \
        detail::ConstBuilder, \
        detail::RuntimeBuilder \
    >::make< \
        std::conditional_t< \
            detail::IsStringLiteral< decltype( x ) >{}, \
            detail::ConstBuilder, \
            detail::RuntimeBuilder \
        >::hash(x) \
    >(x)
auto main() -> int
{
    std::string rt = "RT";
    auto a = NAME("CT");
    auto b = NAME(rt);
 
    // debug_type(a);
    static_assert(is_same<decltype(a), Const<42>>{});
    static_assert(is_same<decltype(b), Runtime<std::string>>{});
    DBG(a.value);
    DBG(b.value);
}

Success!

Let’s make the macro more readable by wrapping it in a lambda to alias the builder type:

#define NAME( x ) [&] {\
    using builder = std::conditional_t< \
        detail::IsStringLiteral< decltype( x ) >{}, \
        detail::ConstBuilder, \
        detail::RuntimeBuilder \
    >; \
    return builder::make<builder::hash(x)>(x); \
}()

Also success!

Unfortunately, the success has been short-lived. This code broke for NAME(rt.c_str()). I’m not quite sure why this makes a difference for the compiler, but whatever the reason, I was at the square one.

Okay, so what now?

I admit feeling a bit disheartened at this point. There were two major obstacles that ruined my ideas:

  • You can’t go from value to type (I know I’m getting repetitive)
  • Your constexpr function will not be constexpr if the parameter passed is not known at compile-time, even if it’s taken by a reference and never used

I did try wrapping the hashing expression in a decltype to force it into an unevaluated context, but that did not help me any.

In the end, I was between a rock and a hard place: on one hand I absolutely had to have the hash calculation as template parameter for the constant, and I could not have the string in the template parameter at all for the run-time.

If only there was a way to only make it a template for the constant path…

Well…

Well…

Deal with the Devil

Well…

If you invert that sentence, you would say if only there was a way to make it not a template for the run-time path…

And yes, you can. If you abandon all that is Holy and embark on a journey straight into the depths of Hell, going well past Fields of if(this), through the Nets of Financial Floats, and even past the Valley of Overloaded Keywords, you’ll arrive at the Pits of Token Reuse.

Okay, maybe I am being a tad dramatic, but this idea is about as crazy as I am happy for thinking about it. What we need is an expression that will be a template in one circumstance, and not a template in another. For that, we are going to abuse one of C++’s syntactical ambiguities.

Let’s consider this code:

foo<bar>(baz)

I’m might be oversimplifying the description, but for the purpose of this article if foo is a template, then <bar> is the first template parameter. But if said foo is a value, then we have an expression (foo < bar) > baz. Of course, in the latter case bar cannot be a type, but if we control everything in the expression, we’ll be fine.

Let’s adjust the above expression to suit our needs:

using hash = decltype(
    builder::wrap<builder::hash(x)>(detail::magic)
);

If we get this to work, then we can simply call builder::make<hash{}>(x);.

Const Builder

For the constant path, we want to set hash to an integral constant of the hash value. Esstentially, it should be
std::integral_constant<fnv1a64(x)>(). The detail::magic parameter needs to be ignored, but it is not a problem if we make it constexpr.

struct magic_t{};
constexpr static magic_t magic;
 
template<size_t N>
struct my_magic_wrap : integral_constant<size_t, N>
{
    template<typename... Ts>
    constexpr my_magic_wrap(Ts&&...){}
};
 
struct ConstBuilder
{
    template<typename T>
    constexpr static size_t hash(T&& t) {
        return fnv1a64(std::forward<T>(t));
    }
 
    template<size_t N>
    using wrap = my_magic_wrap<N>;
 
    template<size_t N, typename T>
    static constexpr Const<N> make(T&&) {
        return {};
    }
};

Run-time

For the run-time path, wrap can be 0 and the builder::hash(x) expression must yield a compatible type. But the most important magic happens near the detail::magic object: we overload its operator> to return a type compatible with std::integral_constant:

struct IAmZiobro : integral_constant<size_t, 0>
{
    template<typename... Ts>
    constexpr IAmZiobro(Ts&&...){}
};
 
constexpr IAmZiobro operator>(bool, magic_t)
{
    return {};
}
 
struct RuntimeBuilder
{
    using hash = IAmZiobro;
 
    static constexpr size_t wrap = IAmZiobro{};
 
    template<size_t N, typename T>
    static Runtime<decay_t<T>> make(T&& t) {
        return { std::forward<T>(t) };
    }
};

Macro

#define NAME( x ) [&] {\
    using builder = std::conditional_t< \
        detail::IsStringLiteral<decltype(x)>{},\
        detail::ConstBuilder, \
        detail::RuntimeBuilder \
    >; \
    using hash = decltype( \
        builder::wrap<builder::hash(x)>(detail::magic) \
    ); \
    return builder::make<hash{}>(x); \
}()

Success!

auto main() -> int
{
    std::string str = "krzaq";
    static_assert(
        std::is_same<decltype(NAME("KrzaQ")), Const<9546715638267443724UL>>{}
    );
    static_assert(
        std::is_same<decltype(NAME("krzaq")), Const<14037438815281584140UL>>{}
    );
 
    auto a = NAME("KrzaQ");
    static_assert(
        std::is_same<decltype(a), Const<9546715638267443724UL>>{}
    );
    DBG(a.value);
 
    auto b = NAME(str);
    static_assert(
        std::is_same<decltype(b), Runtime<std::string>>{}
    );
    DBG(b.value);
 
    auto c = NAME(str.c_str());
    static_assert(
        std::is_same<decltype(c), Runtime<const char*>>{}
    );
    DBG(c.value);
}

Success!

Or at least I hope so. I do fear that I missed something obvious, or maybe a much simpler and saner solution.

As for my friend, he had this to say (cut and translated by yours truly):

<satirev> I owe you a 4-pack of [cheap beer] for this action ; p
<satirev> getting back to the code
<satirev> respect
<satirev> I’ll try this tomorrow on our code base
<satirev> but I won’t use it anyway ; p
<satirev> because [expl.] let’s have some self-respect ; D

I agree. It was a great lot of fun to explore this hack, but that is what it is – a hack. My friend did the right thing and did not try to incorporate it into his code, opting to use two macros instead.

One thought on “Adventures in returning value-dependent type

  1. Your first solution was discarded by the fact that it didn’t work with str.c_str(). What was the issue there, it seems like it should work, as pointer isn’t a type of literal string?

Leave a Reply to Kamil Cancel reply

Your email address will not be published.