Heredoc and outer-context recovery at recursion depth / stack budget limit causes location underflow

Start in src/prism.c at parse_expression, parse_pattern, parse_heredoc, and parse_expression_prefix; trace how depth and stack exhaustion interact with heredoc lex modes and context recovery. Use the C reproducer in the issue to check node bounds at the limits. Done means the reported cases no longer produce out-of-bounds node locations or recurse past the configured limits.

Fuzzing find on https://github.com/ruby/prism/commit/bdbd482dc09839c15392d95d1df35d208cf7b0c6.

When parse_expression or parse_pattern hits PRISM_DEPTH_MAXIMUM (10000) or exhausts parser->stack_budget (pm_parser_stack_exhausted(parser)), returning PM_ERROR_RECOVERY_NODE directly interacts badly with heredoc lexing and enclosing context recovery in three ways in src/prism.c:

1. Stranded PM_LEX_HEREDOC mode on PM_TOKEN_HEREDOC_START: When lex_heredoc_start returns PM_TOKEN_HEREDOC_START, PM_LEX_HEREDOC has already been pushed onto parser->lex_modes. Returning PM_ERROR_RECOVERY_NODE at the depth/stack limit without calling parse_heredoc leaves PM_LEX_HEREDOC on the lex mode stack without a matching parse_heredoc frame; parse_statements then calls parser_lex(parser) directly into the heredoc body and later pops PM_LEX_HEREDOC without restoring parser->previous to the heredoc opening token on an earlier line, causing subsequent nodes to compute inverted (start > end) locations.
2. Missing depth and stack_budget guard in parse_heredoc: Once PM_TOKEN_HEREDOC_START delegates to parse_heredoc at the depth/stack limit (and when parse_string_part encounters PM_TOKEN_HEREDOC_START during recovery and calls parse_heredoc(parser, depth + 1), which calls parse_string_part(parser, depth + 2)), parse_heredoc itself has no depth >= PRISM_DEPTH_MAXIMUM || pm_parser_stack_exhausted(parser) check, allowing nested heredoc interpolations to recurse past PRISM_DEPTH_MAXIMUM and parser->stack_budget.
3. Missing parser->recovering = true when context_recoverable matches at the depth/stack limit: At normal depth, parse_expression_prefix checks context_recoverable(parser, &parser->current) and sets parser->recovering = true so inner constructs unwind without consuming a token that closes an enclosing outer context (such as ) closing ( or PM_TOKEN_HEREDOC_END closing PM_CONTEXT_EMBEXPR). At PRISM_DEPTH_MAXIMUM or stack_budget, parse_expression and parse_pattern return PM_ERROR_RECOVERY_NODE with parser->recovering == false, causing inner parse_statements recovery to call parser_lex(parser), consume the outer terminator, and rewind parser->next_start to line 1 while nodes on line 2 are still open.

Reproduction

Contrastive C Reproducer (pm_parse + pm_parser_line_offsets + pm_visit_node)

Each pair below parses the same construct first just below the stack/depth limit ([OK]), and then right at stack_budget or PRISM_DEPTH_MAXIMUM (10000) ([FAIL]):

#include <inttypes.h>
#include <prism.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    size_t size;
    size_t oob_nodes;
    pm_node_type_t first_type;
    uint32_t first_start;
    uint32_t first_length;
} check_result_t;

static pm_visit_result_t
check_node_bounds(const pm_node_t *node, void *data) {
    check_result_t *res = (check_result_t *) data;
    if (node->location.start > res->size || node->location.length > res->size - node->location.start) {
        if (res->oob_nodes == 0) {
            res->first_type = PM_NODE_TYPE(node);
            res->first_start = node->location.start;
            res->first_length = node->location.length;
        }
        res->oob_nodes++;
    }
    return PM_VISIT_DESCEND;
}

static size_t
run_case(const char *label, const uint8_t *source, size_t size, const pm_options_t *options) {
    pm_arena_t *arena = pm_arena_new();
    pm_parser_t *parser = pm_parser_new(arena, source, size, options);
    pm_node_t *root = pm_parse(parser);

    const pm_line_offset_list_t *line_offsets = pm_parser_line_offsets(parser);
    size_t bad_line_offsets = 0;
    if (line_offsets->size == 0 || line_offsets->offsets[0] != 0 ||
        line_offsets->offsets[line_offsets->size - 1] > size) {
        bad_line_offsets++;
    }
    for (size_t i = 1; i < line_offsets->size; i++) {
        if (line_offsets->offsets[i] <= line_offsets->offsets[i - 1]) {
            bad_line_offsets++;
        }
    }

    check_result_t res = { .size = size };
    pm_visit_node(root, check_node_bounds, &res);

    if (res.oob_nodes == 0 && bad_line_offsets == 0) {
        printf("[OK]   %-54s (size=%zu)\n", label, size);
    } else {
        printf(
            "[FAIL] %-54s (size=%zu): oob_nodes=%zu bad_line_offsets=%zu",
            label,
            size,
            res.oob_nodes,
            bad_line_offsets
        );
        if (res.oob_nodes > 0) {
            printf(
                " (first: %s start=%" PRIu32 " length=%" PRIu32 " [0x%08" PRIx32 "])",
                pm_node_type(res.first_type),
                res.first_start,
                res.first_length,
                res.first_length
            );
        }
        printf("\n");
    }

    pm_parser_free(parser);
    pm_arena_free(arena);
    return (res.oob_nodes > 0 || bad_line_offsets > 0) ? 1 : 0;
}

/* Pair 1: Stranded PM_LEX_HEREDOC via stack_budget on identical source */
static size_t
check_stranded_heredoc_stack_budget_pair(void) {
    static const uint8_t src[] = "f{f{f{<<0\n#{}}}\nclass";
    size_t failures = 0;

    failures += run_case("1a. stranded heredoc (unlimited stack)", src, sizeof(src) - 1, NULL);

    pm_options_t *options = pm_options_new();
    pm_options_stack_budget_set(options, 2048);
    failures += run_case("1b. stranded heredoc (stack_budget=2048)", src, sizeof(src) - 1, options);
    pm_options_free(options);

    return failures;
}

/* Pair 2: Stranded PM_LEX_HEREDOC just below vs. at PRISM_DEPTH_MAXIMUM (10000) */
static size_t
check_stranded_heredoc_depth_pair(void) {
    size_t failures = 0;
    const char mid[] = "<<0\n#{";
    const char tail[] = "\nclass";

    for (size_t blocks = 2499; blocks <= 2500; blocks++) {
        size_t size = (blocks * 2) + (sizeof(mid) - 1) + blocks + (sizeof(tail) - 1);
        uint8_t *src = malloc(size);
        for (size_t i = 0; i < blocks; i++) {
            src[2 * i] = 'f';
            src[2 * i + 1] = '{';
        }
        memcpy(src + (blocks * 2), mid, sizeof(mid) - 1);
        memset(src + (blocks * 2) + (sizeof(mid) - 1), '}', blocks);
        memcpy(src + (blocks * 2) + (sizeof(mid) - 1) + blocks, tail, sizeof(tail) - 1);

        char label[64];
        snprintf(
            label,
            sizeof(label),
            "2%c. stranded heredoc (blocks=%zu, %s)",
            blocks == 2499 ? 'a' : 'b',
            blocks,
            blocks == 2499 ? "depth < max" : "depth == max"
        );
        failures += run_case(label, src, size, NULL);
        free(src);
    }

    return failures;
}

/* Pair 3: Missing outer-context recovery via stack_budget on identical source */
static size_t
check_context_recovery_stack_budget_pair(void) {
    static const uint8_t src[] = "(<<0%\n#{[[[[[[v{)";
    size_t failures = 0;

    failures += run_case("3a. outer ')' recovery (unlimited stack)", src, sizeof(src) - 1, NULL);

    pm_options_t *options = pm_options_new();
    pm_options_stack_budget_set(options, 2048);
    failures += run_case("3b. outer ')' recovery (stack_budget=2048)", src, sizeof(src) - 1, options);
    pm_options_free(options);

    return failures;
}

/* Pair 4: Missing outer-context recovery just below vs. at PRISM_DEPTH_MAXIMUM (10000) */
static size_t
check_context_recovery_depth_pair(void) {
    size_t failures = 0;
    const char prefix[] = "(<<0%\n#{";
    const char suffix[] = "v{)";

    for (size_t brackets = 9990; brackets <= 9991; brackets++) {
        size_t size = (sizeof(prefix) - 1) + brackets + (sizeof(suffix) - 1);
        uint8_t *src = malloc(size);
        memcpy(src, prefix, sizeof(prefix) - 1);
        memset(src + (sizeof(prefix) - 1), '[', brackets);
        memcpy(src + (sizeof(prefix) - 1) + brackets, suffix, sizeof(suffix) - 1);

        char label[64];
        snprintf(
            label,
            sizeof(label),
            "4%c. outer ')' recovery (brackets=%zu, %s)",
            brackets == 9990 ? 'a' : 'b',
            brackets,
            brackets == 9990 ? "depth < max" : "depth == max"
        );
        failures += run_case(label, src, size, NULL);
        free(src);
    }

    return failures;
}

int
main(void) {
    size_t failures = 0;
    failures += check_stranded_heredoc_stack_budget_pair();
    failures += check_stranded_heredoc_depth_pair();
    failures += check_context_recovery_stack_budget_pair();
    failures += check_context_recovery_depth_pair();
    return failures == 0 ? 0 : 1;
}

Building and running against libprism.a:

cc -std=c99 -02 -Iinclude check.c build/libprism.a -o check && ./check

Output:

[OK]   1a. stranded heredoc (unlimited stack)                 (size=21)
[FAIL] 1b. stranded heredoc (stack_budget=2048)               (size=21): oob_nodes=1 bad_line_offsets=0 (first: PM_CLASS_NODE start=16 length=4294967290 [0xfffffffa])
[OK]   2a. stranded heredoc (blocks=2499, depth < max)        (size=7509)
[FAIL] 2b. stranded heredoc (blocks=2500, depth == max)       (size=7512): oob_nodes=1 bad_line_offsets=0 (first: PM_CLASS_NODE start=7507 length=4294964793 [0xfffff639])
[OK]   3a. outer ')' recovery (unlimited stack)               (size=17)
[FAIL] 3b. outer ')' recovery (stack_budget=2048)             (size=17): oob_nodes=3 bad_line_offsets=0 (first: PM_EMBEDDED_STATEMENTS_NODE start=6 length=4294967295 [0xffffffff])
[OK]   4a. outer ')' recovery (brackets=9990, depth < max)    (size=10001)
[FAIL] 4b. outer ')' recovery (brackets=9991, depth == max)   (size=10002): oob_nodes=9994 bad_line_offsets=0 (first: PM_EMBEDDED_STATEMENTS_NODE start=6 length=4294967295 [0xffffffff])

Root Cause

1. Stranded PM_LEX_HEREDOC When PM_TOKEN_HEREDOC_START Hits the Depth or Stack Limit

In parse_expression (src/prism.c:22894-22903) and parse_pattern (src/prism.c:17921-17928):

if (PRISM_UNLIKELY(depth >= PRISM_DEPTH_MAXIMUM || pm_parser_stack_exhausted(parser))) {
    if (depth >= PRISM_DEPTH_MAXIMUM) {
        pm_parser_err_current(parser, PM_ERR_NESTING_TOO_DEEP);
    } else {
        pm_parser_err_stack_exhausted(parser, PM_TOKEN_START(parser, &parser->current), PM_TOKEN_LENGTH(&parser->current));
    }

    return UP(pm_error_recovery_node_create(parser, PM_TOKEN_START(parser, &parser->current), PM_TOKEN_LENGTH(&parser->current)));
}

When parser->current is PM_TOKEN_HEREDOC_START (<<0), lex_heredoc_start has already pushed PM_LEX_HEREDOC onto parser->lex_modes. Returning PM_ERROR_RECOVERY_NODE back to parse_statements (src/prism.c:13808-13809) runs:

if (PM_NODE_TYPE_P(node, PM_ERROR_RECOVERY_NODE)) {
    parser_lex(parser);

which advances past PM_TOKEN_HEREDOC_START without calling parse_heredoc. PM_LEX_HEREDOC stays stranded on parser->lex_modes while the enclosing blocks unwind, so when EOF later pops PM_LEX_HEREDOC, parser->next_start rewinds to line 1 in the middle of parsing later top-level statements (class on line 3).

2. Missing Depth and Stack Budget Check in parse_heredoc

parse_heredoc (src/prism.c:19484) does not check depth >= PRISM_DEPTH_MAXIMUM || pm_parser_stack_exhausted(parser). If parse_expression, parse_pattern, parse_statements, or parse_string_part delegates PM_TOKEN_HEREDOC_START to parse_heredoc at the depth/stack limit, parse_heredoc will still lex # interpolations (PM_TOKEN_EMBEXPR_BEGIN, PM_TOKEN_EMBVAR) and recurse back into parse_string_part -> parse_heredoc, bypassing both PRISM_DEPTH_MAXIMUM and parser->stack_budget.

3. Missing parser->recovering = true on context_recoverable at the Depth or Stack Limit

At normal depth, parse_expression_prefix checks if (context_recoverable(parser, &parser->current)) and sets parser->recovering = true so inner statement/array/block loops break out cleanly without consuming the outer context's closing token. Because the early return at depth >= PRISM_DEPTH_MAXIMUM || pm_parser_stack_exhausted(parser) in parse_expression and parse_pattern leaves parser->recovering == false, the innermost parse_statements loop calls parser_lex(parser) and consumes the outer terminator (such as ) or PM_TOKEN_HEREDOC_END), rewinding parser->next_start to line 1 before the inner line-2 nodes finish computing their end locations.