8

I'm writing a compile-time parser PoC (compiling a literal string to std::tuple) based on C++20 (or 23 if necessary). Currently gcc, clang, and MSVC all crash for this code, and MSVC gives useful information -- compiler is out of heap space.

Link to Compiler Explorer

#include <string>
#include <string_view>
#include <cstddef>
#include <tuple>
#include <utility>

consteval decltype(auto) tuple_push(auto t, auto e) {
    return std::tuple_cat(t, std::make_tuple(e));
}

consteval decltype(auto) pattern_munch(auto t, std::string_view remaining) {
    if (remaining.empty()) {
        return t;
    }

    switch (remaining.front()) {
    case 'f':
        return pattern_munch(tuple_push(t, 1.f), remaining.substr(1));
    case 'i':
        return pattern_munch(tuple_push(t, 1), remaining.substr(1));
    default:
        throw "unhandled";
    }
}

consteval decltype(auto) compile_pattern(std::string_view pattern) {
    return pattern_munch(std::make_tuple(), pattern);
}

int main() {
    constexpr auto result = compile_pattern("fif");

    static_assert(std::is_same_v<decltype(result), std::tuple<float, int, float>>);
}

Since all functions are consteval, and therefore the arguments should be compile-time knowable, why does the compiler seem to recurse forever? How do I fix/workaround the code?

Improve this question
12
  • It has nothing to do with constant evaluation (remove all consteval and observe how the compiler goes out of space just the same). Commented May 13 at 10:03
  • I appreciate the attempt for this compile time parser from a challenge point of view, but from a practical point of view I wonder how much this makes sense. You have a compile-time string and recompile it to a compile-time type with an initial value mainly for a simpler writing. A custom class to handle the initial value and a using fif =MyClass<float, int, float>;` could achieve the same. Commented May 13 at 10:13
  • return type cannot depend of value of parameter, even for consteval function... Commented May 13 at 10:20
  • 2
    "The type of the parameter t and the return type may not be the same". With decltype(auto)(/auto), the type is deduced from the first return with is return t;, so the same. you would want if constexpr, but it is not possible as-is. Commented May 13 at 12:26
  • 1
    @edrezen: overloads would then even be a better mapping Demo Commented May 14 at 7:28

2 Answers 2

Reset to default
9

Since all functions are consteval, and therefore the arguments should be compile-time knowable.

Even if consteval function, parameters are not contant expression. I think that the rational is that return type cannot depend of value of parameter.

How do I fix/workaround the code?

You might use char_sequence instead of string_view

template <char c>
consteval decltype(auto) pattern_munch() {
    if constexpr (c == 'f') { return 1.f; }
    else if constexpr (c == 'i') { return 1; }
    else { static_assert(false); }
}

template <char... Cs>
consteval decltype(auto) compile_pattern(char_sequence<Cs...>) {
    return std::tuple(pattern_munch<Cs>()...);
}

Now, to construct the char_sequence, you might use clang/gcc extension

// That template uses the extension
template<typename Char, Char... Cs>
constexpr auto operator"" _cs() -> std::integer_sequence<Char, Cs...> {
    return {};
}

See my answer from String-interning at compiletime for profiling to have MAKE_STRING macro if you cannot used the extension (Really more verbose, and hard coded limit for accepted string length).

and then

constexpr auto result_extension = compile_pattern("fif"_cs);
constexpr auto result_macro = compile_pattern(MAKE_STRING("fif"));

or, since C++20, use a literal class type as template parameter:

template <std::size_t N>
struct LiteralString
{
    consteval LiteralString(const char (&s)[N]) { std::copy(s, s + N, &data[0]); }

    static constexpr std::size_t size = N;
    std::array<char, N> data{};
};

template <auto S>
constexpr auto compile_pattern()
{
    return []<std::size_t...Is>(std::index_sequence<Is...>) {
        return std::tuple(pattern_munch<S.data[Is]>()...);
    }(std::make_index_sequence<std::size(S.data) - 1>());
}

/*constexpr*/ auto t = compile_pattern<LiteralString("fif")>();
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

5

The problem is that in

consteval decltype(auto) pattern_munch(auto t, std::string_view remaining) {
    if (remaining.empty()) {
        return t;
    }

    switch (remaining.front()) {
    case 'f':
        return pattern_munch(tuple_push(t, 1.f), remaining.substr(1));
    case 'i':
        return pattern_munch(tuple_push(t, 1), remaining.substr(1));
    default:
        throw "unhandled";
    }
}

the compiler compile all three return case, also when the remaining string is empty.

You could solve the problem with if constexpr, but remaining isn't a template argument.

What about using a template argument instead of remaining, so you can use if constexpr and cut the compilation of unused functions?

If you define a Foo class as follows

template <std::size_t Dim>
struct Foo
{
  std::array<char, Dim-1u>  data;

  template <std::size_t ... Is>
  constexpr Foo (const char (&init)[Dim], std::index_sequence<Is...>)
    : data{init[Is]...}
  { }

  constexpr Foo (const char (&init)[Dim])
    : Foo{init, std::make_index_sequence<Dim-1u>{}}
  { }

  constexpr std::size_t size () const
  { return data.size(); }

  constexpr char get_char (std::size_t ind) const
  { return data.at(ind); }
};

and a _foo literal that uses Foo

template <Foo str>
constexpr auto operator"" _foo()
{ return str; }

You can write your pattern_munch() and compile_pattern() as follows (EDIT: but see also the Jarod42's solution to see how avoid the recursion)

template <Foo Val, std::size_t Ind>
constexpr auto pattern_munch (auto t) {
  if constexpr ( Ind == Val.size() )
    return t;
  else if constexpr ( Val.get_char(Ind) == 'f' ) 
    return pattern_munch<Val, Ind+1u>(tuple_push(t, 1.f));
  else if constexpr ( Val.get_char(Ind) == 'i' ) 
    return pattern_munch<Val, Ind+1u>(tuple_push(t, 1));
  else 
    throw "unhandled";
}

template <Foo val>
constexpr auto compile_pattern () {
  return pattern_munch<val, 0u>(std::make_tuple());
}

and you can invoke compile_pattern() this way

constexpr auto result = compile_pattern<"fif"_foo>();

The following is a full C++20 compiling example


#include <array>
#include <tuple>
#include <iostream>
#include <algorithm>


template <std::size_t Dim>
struct Foo
{
  std::array<char, Dim-1u>  data;

  template <std::size_t ... Is>
  constexpr Foo (const char (&init)[Dim], std::index_sequence<Is...>)
    : data{init[Is]...}
  { }

  constexpr Foo (const char (&init)[Dim])
    : Foo{init, std::make_index_sequence<Dim-1u>{}}
  { }

  constexpr std::size_t size () const
  { return data.size(); }

  constexpr char get_char (std::size_t ind) const
  { return data.at(ind); }
};

template <Foo str>
constexpr auto operator"" _foo()
{ return str; }

constexpr auto tuple_push(auto t, auto e) {
  return std::tuple_cat(t, std::make_tuple(e));
}

template <Foo Val, std::size_t Ind>
constexpr auto pattern_munch (auto t) {
  if constexpr ( Ind == Val.size() )
    return t;
  else if constexpr ( Val.get_char(Ind) == 'f' ) 
    return pattern_munch<Val, Ind+1u>(tuple_push(t, 1.f));
  else if constexpr ( Val.get_char(Ind) == 'i' ) 
    return pattern_munch<Val, Ind+1u>(tuple_push(t, 1));
  else 
    throw "unhandled";
}

template <Foo val>
constexpr auto compile_pattern () {
  return pattern_munch<val, 0u>(std::make_tuple());
}

int main() {
  constexpr auto result = compile_pattern<"fif"_foo>();

  static_assert(std::is_same_v<decltype(result),
                               std::tuple<float, int, float> const>);
}
Improve this answer

4 Comments

OP's code can even be simplified with std::index_sequence to avoid recursion and tuple concatenation.
@Jarod42 - Yes... I've seen your answer (wonderful solution)
+rep, both answers are great, I really hope SO supports tagging multiple answers :)
@Sprite - Thanks. But Jarod42's answer is better

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.