编译递归consteval函数时编译器堆内存耗尽的原因与解决方法

我正在基于C20（必要时可使用C23）编写一个编译期解析器PoC，目标是将字面量字符串编译为std::tuple。目前gcc、clang和MSVC编译这段代码时均会崩溃，其中MSVC给出提示——“compiler is out of heap space”。

代码如下：

#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>>);
}

疑问：由于所有函数均为consteval，参数应在编译期可知，为何编译器会出现类似无限递归的情况？该如何修复或规避此问题？

核心问题在于**consteval函数的模板实例化爆炸**，而非真正的无限递归。

每次调用tuple_push时，std::tuple_cat会生成一个全新的std::tuple类型——比如第一次是std::tuple<float>，第二次是std::tuple<float, int>，第三次是std::tuple<float, int, float>。而pattern_munch是模板函数，每次传入不同类型的t参数时，都会实例化一个全新的pattern_munch版本。

对于长度为N的字符串，编译器需要实例化O(N²)个模板函数和tuple类型：每个递归步骤都对应一个新的pattern_munch实例，且每个实例都依赖于前一个步骤生成的tuple类型。当字符串长度稍长时，这种实例化数量会指数级增长，迅速耗尽编译器的内存，表现为“堆空间不足”。

虽然逻辑上递归次数是有限的（等于字符串长度），但模板实例化的开销让编译器不堪重负，最终出现崩溃。

要解决这个问题，需要避免每次递归都生成新的tuple类型，转而通过编译期索引序列来构建最终的tuple，让编译器只需要处理单一的模板实例化路径。

方案1：基于编译期索引和类型列表构建tuple #

利用std::index_sequence遍历字符串的每个字符，提前确定每个位置的类型，最后一次性构建tuple：

#include <string_view>
#include <tuple>
#include <utility>

// 单个字符映射到类型
template<char C>
struct char_to_type {
    static_assert(C == 'f' || C == 'i', "invalid character");
    using type = std::conditional_t<C == 'f', float, int>;
};

// 从字符串视图生成类型列表
template<std::string_view SV, typename IdxSeq>
struct pattern_to_types_impl;

template<std::string_view SV, std::size_t... Idxs>
struct pattern_to_types_impl<SV, std::index_sequence<Idxs...>> {
    using type = std::tuple<typename char_to_type<SV[Idxs]>::type...>;
};

template<std::string_view SV>
using pattern_to_types = typename pattern_to_types_impl<SV, std::make_index_sequence<SV.size()>>::type;

// 生成对应类型的tuple（值固定为1/1.f）
consteval auto compile_pattern(std::string_view pattern) {
    return []<std::size_t... Idxs>(std::index_sequence<Idxs...>) {
        return std::tuple(
            []<char C>() -> typename char_to_type<C>::type {
                if constexpr (C == 'f') return 1.f;
                else return 1;
            }.template operator()<pattern[Idxs]>()...
        );
    }(std::make_index_sequence<pattern.size()>());
}

int main() {
    constexpr auto result = compile_pattern("fif");
    static_assert(std::is_same_v<decltype(result), std::tuple<float, int, float>>);
}

方案2：C++23 用std::tuple推导指引+折叠表达式 #

如果可以使用C++23，可简化实现，利用折叠表达式直接生成tuple：

#include <string_view>
#include <tuple>
#include <utility>

consteval auto compile_pattern(std::string_view pattern) {
    return [&]<std::size_t... Idxs>(std::index_sequence<Idxs...>) {
        return std::tuple(
            [](char c) consteval {
                return c == 'f' ? 1.f : 1;
            }(pattern[Idxs])...
        );
    }(std::make_index_sequence<pattern.size()>());
}

int main() {
    constexpr auto result = compile_pattern("fif");
    static_assert(std::is_same_v<decltype(result), std::tuple<float, int, float>>);
}

方案3：保留递归但避免类型膨胀（进阶） #

如果想保留递归结构，可以通过传递类型列表而非已构建的tuple来避免每次递归生成新tuple类型，最后再将类型列表转换为tuple：

#include <string_view>
#include <tuple>
#include <type_traits>

template<typename... Ts>
struct type_list {};

// 递归构建类型列表
consteval auto build_type_list(std::string_view remaining) {
    if (remaining.empty()) {
        return type_list<>{};
    }
    auto head = remaining.front();
    auto tail = remaining.substr(1);
    if constexpr (head == 'f') {
        return type_list<float, typename decltype(build_type_list(tail))::types...>{};
    } else if constexpr (head == 'i') {
        return type_list<int, typename decltype(build_type_list(tail))::types...>{};
    } else {
        throw "unhandled";
    }
}

// 将类型列表转换为tuple
template<typename... Ts>
consteval auto type_list_to_tuple(type_list<Ts...>) {
    return std::tuple(Ts{1}...); // 1自动转换为float/int
}

consteval auto compile_pattern(std::string_view pattern) {
    return type_list_to_tuple(build_type_list(pattern));
}

int main() {
    constexpr auto result = compile_pattern("fif");
    static_assert(std::is_same_v<decltype(result), std::tuple<float, int, float>>);
}

内容的提问来源于stack exchange，提问作者Sprite