Infinite loop or segmentation fault on grammar with many binary operators

[Gismo359]

ctpg::parser does not build properly with lots of binary operators. Depending on whether the parser is constexpr you see two results:

• If yes, the compiler emits note: constexpr evaluation hit maximum step limit; possible infinite loop?. The stacktrace afterwards is different depending on how many operators I add, but it is always somewhere in sa.analyze_states().
• If no, it will cause a segmentation fault/bus error when entering ctpg::parser's constructor because it is hitting the stack limit.

If I increase the stack size, then it will run and produce the correct result, but I have to make it absolutely huge (~1024x the default!):

❯ ulimit -s 8388608

Default size:

❯ ulimit -s
8192

Library version used:

❯ yay ctpg
1 aur/ctpg-git 1.3.7.r12.g0482730-1 (+0 0.00) (Installed: 1.3.7.r14.g624b4d1-1

Compiler used:

❯ clang++ --version
clang version 20.1.8
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin

Example to reproduce:

#include <ctpg/ctpg.hpp>

constexpr ctpg::nterm<std::string> expr{"expr"};

static constexpr ctpg::parser p(
    expr,
    ctpg::terms(
        "+=",
        "-=",
        "*=",
        "/=",
        "<<=",
        ">>=",
        "<<",
        ">>",
        "<",
        ">",
        "<=",
        ">=",
        "==",
        "!=",
        "&",
        "|",
        "^",
        "&&",
        "||",
        "+",
        "-",
        "*",
        "/",
        "%",
        "x"
    ),
    ctpg::nterms(expr),
    ctpg::rules(
        expr(expr, "+=", expr) >>= std::identity{},
        expr(expr, "-=", expr) >>= std::identity{},
        expr(expr, "*=", expr) >>= std::identity{},
        expr(expr, "/=", expr) >>= std::identity{},
        expr(expr, "<<=", expr) >>= std::identity{},
        expr(expr, ">>=", expr) >>= std::identity{},
        expr(expr, "<<", expr) >>= std::identity{},
        expr(expr, ">>", expr) >>= std::identity{},
        expr(expr, "<", expr) >>= std::identity{},
        expr(expr, ">", expr) >>= std::identity{},
        expr(expr, "<=", expr) >>= std::identity{},
        expr(expr, ">=", expr) >>= std::identity{},
        expr(expr, "==", expr) >>= std::identity{},
        expr(expr, "!=", expr) >>= std::identity{},
        expr(expr, "&", expr) >>= std::identity{},
        expr(expr, "|", expr) >>= std::identity{},
        expr(expr, "^", expr) >>= std::identity{},
        expr(expr, "&&", expr) >>= std::identity{},
        expr(expr, "||", expr) >>= std::identity{},
        expr(expr, "+", expr) >>= std::identity{},
        expr(expr, "-", expr) >>= std::identity{},
        expr(expr, "*", expr) >>= std::identity{},
        expr(expr, "/", expr) >>= std::identity{},
        expr(expr, "%", expr) >>= std::identity{},
        expr("x") >>= std::identity{}
    )
);

[Gismo359]

In this case it is enough to allocate ctpg::state_scanner on the heap to resolve the segmentation fault:

index 6631ecc..702617c 100644
--- a/include/ctpg/ctpg.hpp
+++ b/include/ctpg/ctpg.hpp
@@ -1911,8 +1911,8 @@ public:
         analyze_error_recovery_token();
         analyze_rules(std::make_index_sequence<std::tuple_size_v<rule_tuple_type>>{}, grammar_root);
 
-        state_analyzer sa(gi, states, parse_table);
-        state_count = sa.analyze_states();
+        auto sa = std::make_unique<state_analyzer>(gi, states, parse_table);
+        state_count = sa->analyze_states();
 
         create_lexer(seq_for_terms);
     }

[peter-winter]

Heap allocation is not constexpr in c++17, which this library is demanding at the moment, so this fix is not an option. Simply change the maximum number of constexpr operations, for clang this is -fconstexpr-steps=enough_number. This will unfortunately increase the RAM usage of clang, possibly to the point of termination, but it is worth trying.

[Gismo359]

The heap allocation is a workaround for sure, but it's required if we want to do it in runtime (allocating ctpg::parser is not enough as the scanner is a stack variable in the constructor)

I'm surprised the compiler is hitting the limit with a relatively simple grammar even with LR(1). The state_scanner::add_situation() function is called ~160k times to result in ~70 states!

Do you think something could be done to reduce the work done (at least in constexpr)? Maybe supporting LALR or another similar algorithm?

[peter-winter]

For sure. I have ideas. There is a branch called 'term_groups' which is not building for Windows (no idea why, probably a msvc compiler bug) which allows for grouping similar terminals. In you case this would be perfect solution.

The final number of states in not the problem, it is the temporary state of the algorithm structures that are bloated in the process of finding these 70 states. I have an idea to improve the algorithm itself. Unfortunately I have absolutely no time to maintain it at the moment.