Heredoc rewind inside unclosed interpolation causes unsigned location length underflow (~4 GB out-of-bounds read)

Start by tracing the EOF handling and heredoc rewind described in the issue, then inspect the parser lexing and statement parsing paths for PM_LEX_EMBEXPR, PM_LEX_HEREDOC, and PM_TOKEN_HEREDOC_END. Reproduce with the supplied Ruby input and verify the resulting AST locations and pm_prettyprint behavior under AddressSanitizer. Done means malformed heredoc interpolation no longer produces underflowed locations or an out-of-bounds read.

Fuzzing find on bdbd482dc.

When an unterminated heredoc contains an unclosed interpolation (#{...) with unclosed inner constructs at EOF (such as <<0\n#{f{ or <<0\n#{{{{s[f{), hitting EOF inside PM_LEX_EMBEXPR pops PM_LEX_EMBEXPR and causes PM_LEX_HEREDOC to emit PM_TOKEN_HEREDOC_END and rewind parser->next_start back to the heredoc opener's line (line 1).

Because PM_TOKEN_HEREDOC_END is not treated as a context terminator for PM_CONTEXT_EMBEXPR (and token_begins_expression_p returns true for PM_TOKEN_HEREDOC_END), inner parser routines on line 2 do not unwind on PM_TOKEN_HEREDOC_END; instead, they skip or consume PM_TOKEN_HEREDOC_END, lex the rewound newline from line 1 (3..4), and leave parser->previous anchored at byte 4 ((2,0)). When those line-2 AST nodes finalize their locations using parser->previous (with end < start), the unsigned 32-bit length calculation U32(end - start) underflows modulo $2^{32}$ to ~4,294,967,295 (0xFFFFFFF...), causing a ~4 GB out-of-bounds heap buffer read in C consumers such as pm_prettyprint.

Reproduction

1. Ruby / ./bin/parse Output on <<0\n#{{{{s[f{ (13 bytes)

Prism.parse("<<0\n\#{{{{s[f{")

Running ./bin/parse on <<0\n#{{{{s[f{ produces the following AST with end column 4294967296 ($2^{32}$) on HashNode, AssocNode, CallNode#message_loc, CallNode, and BlockNode:

@ ProgramNode (location: (1,0)-(1,3))
└── statements:
    @ StatementsNode (location: (1,0)-(1,3))
    └── body: (length: 1)
        └── @ InterpolatedStringNode (location: (1,0)-(1,3))
            ├── opening_loc: (1,0)-(1,3) = "<<0"
            ├── parts: (length: 1)
            │   └── @ EmbeddedStatementsNode (location: (2,0)-(2,0))
            │       ├── opening_loc: (2,0)-(2,2) = "\#{"
            │       ├── statements:
            │       │   @ StatementsNode (location: (2,2)-(2,2))
            │       │   └── body: (length: 1)
            │       │       └── @ HashNode (location: (2,2)-(2,4294967296))
            │       │           ├── opening_loc: (2,2)-(2,3) = "{"
            │       │           ├── elements: (length: 1)
            │       │           │   └── @ AssocNode (location: (2,3)-(2,4294967296))
            │       │           │       ├── key:
            │       │           │       │   @ HashNode (location: (2,3)-(2,4294967296))
            │       │           │       │   ├── opening_loc: (2,3)-(2,4) = "{"
            │       │           │       │   ├── elements: (length: 1)
            │       │           │       │   │   └── @ AssocNode (location: (2,4)-(2,4294967296))
            │       │           │       │   │       ├── key:
            │       │           │       │   │       │   @ HashNode (location: (2,4)-(2,4294967296))
            │       │           │       │   │       │   ├── opening_loc: (2,4)-(2,5) = "{"
            │       │           │       │   │       │   ├── elements: (length: 1)
            │       │           │       │   │       │   │   └── @ AssocNode (location: (2,5)-(2,4294967296))
            │       │           │       │   │       │   │       ├── key:
            │       │           │       │   │       │   │       │   @ CallNode (location: (2,5)-(2,7))
            │       │           │       │   │       │   │       │   ├── name: :[]
            │       │           │       │   │       │   │       │   ├── message_loc: (2,6)-(2,4294967296) = "[f{"
            │       │           │       │   │       │   │       │   ├── opening_loc: (2,6)-(2,7) = "["
            │       │           │       │   │       │   │       │   ├── arguments:
            │       │           │       │   │       │   │       │   │   @ ArgumentsNode (location: (2,7)-(2,7))
            │       │           │       │   │       │   │       │   │   └── arguments: (length: 1)
            │       │           │       │   │       │   │       │   │       └── @ CallNode (location: (2,7)-(2,4294967296))
            │       │           │       │   │       │   │       │   │           ├── name: :f
            │       │           │       │   │       │   │       │   │           ├── message_loc: (2,7)-(2,8) = "f"
            │       │           │       │   │       │   │       │   │           └── block:
            │       │           │       │   │       │   │       │   │               @ BlockNode (location: (2,8)-(2,4294967296))
            │       │           │       │   │       │   │       │   │               ├── body:
            │       │           │       │   │       │   │       │   │               │   @ StatementsNode (location: (1,3)-(2,0))
            │       │           │       │   │       │   │       │   │               │   └── body: (length: 2)
            │       │           │       │   │       │   │       │   │               │       ├── @ ErrorRecoveryNode (location: (2,8)-(2,9))
            │       │           │       │   │       │   │       │   │               │       └── @ ErrorRecoveryNode (location: (1,3)-(2,0))
            │       │           │       │   │       │   │       │   │               ├── opening_loc: (2,8)-(2,9) = "{"
            │       │           │       │   │       │   │       │   │               └── closing_loc: (2,0)-(2,0) = ""

2. C pm_prettyprint Reproduction & AddressSanitizer Output

Passing the parsed AST of "<<0\n#{{{{s[f{" (or the 10-byte "<<0\n#{s[f{") to pm_prettyprint causes pm_buffer_append_source to read (size_t) node->message_loc.length (4,294,967,290 bytes, 0xFFFFFFFA) starting at parser->start + 10:

#include "prism.h"
#include <stdlib.h>
#include <string.h>

int main(void) {
    char *src = strdup("<<0\n#{{{{s[f{");
    pm_arena_t *arena = pm_arena_new();
    pm_parser_t *parser = pm_parser_new(arena, (const uint8_t *) src, strlen(src), NULL);
    pm_node_t *node = pm_parse(parser);
    pm_buffer_t *buf = pm_buffer_new();
    pm_prettyprint(buf, parser, node);
    pm_buffer_free(buf);
    pm_parser_free(parser);
    pm_arena_free(arena);
    free(src);
    return 0;
}

Actual AddressSanitizer Output

=================================================================
==21289==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000095e at pc 0x0001026cbf20 bp 0x00016d6bb860 sp 0x00016d6bb858
READ of size 1 at 0x60200000095e thread T0
    #0 0x0001026cbf1c in pm_buffer_append_source buffer.c:260
    #1 0x0001026e3e44 in prettyprint_node prettyprint.c:1226
    #2 0x0001026dcad0 in prettyprint_node prettyprint.c:491
    #3 0x0001026fa478 in prettyprint_node prettyprint.c:3923
    #4 0x0001026dcad0 in prettyprint_node prettyprint.c:491
    #5 0x0001026fa478 in prettyprint_node prettyprint.c:3923
    #6 0x0001026dcad0 in prettyprint_node prettyprint.c:491
    #7 0x0001026fa478 in prettyprint_node prettyprint.c:3923
    #8 0x000102719c6c in prettyprint_node prettyprint.c:8195
    #9 0x0001026f4de8 in prettyprint_node prettyprint.c:3162
    #10 0x000102705b9c in prettyprint_node prettyprint.c:5416
    #11 0x000102719c6c in prettyprint_node prettyprint.c:8195
    #12 0x000102714030 in prettyprint_node prettyprint.c:7338
    #13 0x0001026d838c in pm_prettyprint prettyprint.c:9020
    #14 0x00010287dba0 in main test.c:11
    #15 0x000194e9fe7c in start+0x1a1c (dyld:arm64e+0x31e7c)

0x60200000095e is located 0 bytes after 14-byte region [0x602000000950,0x60200000095e)
allocated by thread T0 here:
    #0 0x000102f16c28 in strdup+0x108 (libclang_rt.asan_osx_dynamic.dylib:arm64e+0x3ac28)
    #1 0x00010287db40 in main test.c:6
    #2 0x000194e9fe7c in start+0x1a1c (dyld:arm64e+0x31e7c)

SUMMARY: AddressSanitizer: heap-buffer-overflow buffer.c:260 in pm_buffer_append_source
Shadow bytes around the buggy address:
  0x602000000680: fa fa 00 00 fa fa 00 00 fa fa 00 00 fa fa 00 00
  0x602000000700: fa fa 00 00 fa fa 00 00 fa fa 00 00 fa fa 00 00
  0x602000000780: fa fa 00 00 fa fa 00 00 fa fa 00 00 fa fa 00 00
  0x602000000800: fa fa 00 00 fa fa 00 00 fa fa 00 00 fa fa 00 00
  0x602000000880: fa fa 00 00 fa fa 00 00 fa fa 00 00 fa fa 00 fa
=>0x602000000900: fa fa 00 04 fa fa 00 00 fa fa 00[06]fa fa 00 00
  0x602000000980: fa fa fd fa fa fa fd fa fa fa fd fd fa fa fa fa
  0x602000000a00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x602000000a80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x602000000b00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x602000000b80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==21289==ABORTING

Root Cause

Step-by-step trace of "<<0\n#{{{{s[f{" (interactive simulation in Prism Loupe):

• Line 1 (<<0\n, bytes 0..4): Lexing <<0 (PM_TOKEN_HEREDOC_START[0..3]) pushes PM_LEX_HEREDOC onto lex_modes with lex_mode.as.heredoc.next_start = 3 (saving the position of \n on line 1 inside the heredoc frame) while setting parser->next_start = 4 (body_start) so the next parser_lex jumps forward to line 2.

• Line 2 (#{{{{s[f{, bytes 4..13): #{ (PM_TOKEN_EMBEXPR_BEGIN[4..6]) resets parser->next_start = NULL, pushes PM_LEX_EMBEXPR (lex_modes = [EMBEXPR, HEREDOC, DEFAULT]), and enters parse_statements(parser, PM_CONTEXT_EMBEXPR, ...), descending through { (6..7), { (7..8), { (8..9), s[ (parse_aref at 10..11), and f (11..12) into parse_arguments_list with lookahead parser->current = PM_TOKEN_BRACE_LEFT[12..13].

• 1-token lookahead on { (12..13) pops PM_LEX_EMBEXPR and PM_LEX_HEREDOC before parse_block enters: Inside parse_arguments_list (while contexts is still [EMBEXPR, MAIN]), accept2(parser, PM_TOKEN_BRACE_LEFT, ...) consumes { (12..13) and immediately calls parser_lex for lookahead:

  1. At byte 13 >= parser->end (EOF), parser_lex pops PM_LEX_EMBEXPR (lex_modes = [HEREDOC, DEFAULT]) and jumps to switch_lex_modes.
  2. PM_LEX_HEREDOC runs at EOF, records the missing heredoc terminator diagnostic, sets parser->next_start = 3 (from lex_mode.as.heredoc.next_start), sets parser->heredoc_end = 13, sets lex_state = PM_LEX_STATE_END, pops PM_LEX_HEREDOC (lex_modes = [DEFAULT]), and emits parser->current = PM_TOKEN_HEREDOC_END[13..13].
  3. Only after lex_modes has collapsed to [DEFAULT] does parse_arguments_list call parse_block -> parse_statements(parser, PM_CONTEXT_BLOCK_BRACES, ...), pushing PM_CONTEXT_BLOCK_BRACES onto contexts ([BLOCK_BRACES, EMBEXPR, MAIN]).

• Two parse_statements iterations and the 13 -> 3..4 -> 13 HEREDOC_FLUSH bounce:

  1. Iteration 1 (on PM_TOKEN_HEREDOC_END[13..13]): PM_TOKEN_HEREDOC_END is not a context_terminator for PM_CONTEXT_BLOCK_BRACES or PM_CONTEXT_EMBEXPR, so parse_expression_prefix emits a 1st ErrorRecoveryNode (12..13) without setting parser->recovering.
  2. Rewind to byte 3 and parser_flush_heredoc_end: parse_statements skips the unparseable token via parser_lex(parser), jumping to parser->next_start = 3 (\n on line 1). Inside the \n handler, parser->heredoc_end == 13 triggers parser_flush_heredoc_end(parser), which sets parser->next_start = 13 and parser->heredoc_end = NULL while returning parser->current = PM_TOKEN_NEWLINE[3..4] (lex_state = PM_LEX_STATE_BEG).
  3. Bounce back to PM_TOKEN_EOF[13..13]: while (accept2(parser, PM_TOKEN_NEWLINE, PM_TOKEN_SEMICOLON)); accepts PM_TOKEN_NEWLINE[3..4]—moving NEWLINE[3..4] into parser->previous—and calls parser_lex, which follows parser->next_start = 13 right back to parser->current = PM_TOKEN_EOF[13..13].
  4. Iteration 2 (on PM_TOKEN_EOF[13..13]): Because PM_TOKEN_EOF does not directly terminate PM_CONTEXT_BLOCK_BRACES, the parse_statements loop runs a second iteration. context_recoverable sees PM_TOKEN_EOF terminates PM_CONTEXT_MAIN, sets parser->recovering = true, emits a 2nd ErrorRecoveryNode (3..4) without advancing parser->previous, and breaks out of parse_statements.

• Synthesizing PM_TOKEN_NOT_PROVIDED[4..4] and uint32_t underflow during unwinding:

  • In parse_block, expect1_opening(parser, PM_TOKEN_BRACE_RIGHT, ...) fails against PM_TOKEN_EOF[13..13] and synthesizes a zero-width missing token at parser->previous.end: parser->previous = PM_TOKEN_NOT_PROVIDED[4..4] ((2,0), the first byte after \n).
  • Every enclosing construct on line 2 then unwinds under parser->recovering == true with parser->previous = NOT_PROVIDED[4..4] (end = 4). Computing U32(4 - start) underflows uint32_t across 8 AST node base.locations plus CallNode#message_loc on s[f{:

  AST Node / Location	start_offset (Line, Col)	Target End Offset	Signed Diff (end - start)	uint32_t length (U32(diff))
  BlockNode ({)	12 ((2,8))	4 ((2,0))	-8	4294967288 ($2^{32} - 8$)
  CallNode (f{)	11 ((2,7))	4 ((2,0))	-7	4294967289 ($2^{32} - 7$)
  CallNode#message_loc ([f{)*	10 ((2,6))	4 ((2,0))	-6	4294967290 ($2^{32} - 6$)
  Inner AssocNode (s[f{)	9 ((2,5))	4 ((2,0))	-5	4294967291 ($2^{32} - 5$)
  Inner HashNode ({s[f{) & Middle AssocNode	8 ((2,4))	4 ((2,0))	-4	4294967292 ($2^{32} - 4$)
  Middle HashNode ({{s[f{) & Outer AssocNode	7 ((2,3))	4 ((2,0))	-3	4294967293 ($2^{32} - 3$)
  Outer HashNode ({{{s[f{)	6 ((2,2))	4 ((2,0))	-2	4294967294 ($2^{32} - 2$)

  *Note on s[f{'s CallNode (base.location = (2,5)-(2,7), 9..11): Its own base.location does not underflow because in pm_arguments_node_arguments_append, PM_NODE_END(argument) wraps modulo $2^{32}$ (11 + 4294967289 == 4), making PM_NODE_END(node) < PM_NODE_END(argument) (11 < 4) evaluate to false so ArgumentsNode stays 11..11, while pm_call_node_aref_create computes message_loc.length = (4 + 0) - 10 = 4294967290.