Skip to content

A deeply nested term in the authoring notation overflows the stack instead of LLP2001 (R5) #374

Closed

Description

@afflom

Pinned at 3877351 (release/v0.5 line, lexlean 0.4.0, language 1.2). origin/main 71defb4c6 and origin/release/v0.5 ed549c24f were read, not run; the single check site below is the same on both.

Reproduce

A one-definition module (language = "1.2", default limits, lexicon sources lexlean.std.bool and lexlean.std.nat) whose body nests n times:

definition{
  name: xs,
  parameters: [],
  result: (List Nat),
  body: (cons 1 (cons 1 ... (nil Nat)))
}
n lexlean check
30,000 error[LLT4001]: phase link: invalid semantic-module JSON: recursion limit exceeded ...
50,000 thread 'lexlean-compile' has overflowed its stack, fatal runtime error: stack overflow, aborting, signal 6, exit 134

The source at n = 50,000 is about 450 KB, well inside max_file_bytes. With the closing parentheses removed, n = 20,000 reports LLP2001: expected )``, and n = 100,000 overflows, so the overflow happens while reading the notation, before the JSON decoder.

Expected

SPEC §17.21.6: "nothing in it panics: the notation is read with an explicit nesting bound". R5: user input never panics. The expected result is a registered diagnostic, LLP2001 at the offending token.

Cause (from reading, not tested)

MAX_DEPTH (256, surface/generic.rs) is tested in generic::value and in read_at (surface/semantic.rs:260). terms::read (surface/semantic.rs:1152) passes depth + 1 down through paren but does not test it, so the readable forms of a term have no bound. The existing deep_nesting_is_an_error test is in generic.rs.

Note

Testing depth in terms::read would change the message for terms of 257 to about 30,000 levels from the JSON recursion limit exceeded to the notation's own error. Both are refusals.

Accepted when

  • The module at n = 50,000 is refused with a registered diagnostic and no abort.
  • A negative fixture and register row cover it (R3, R5).

Activity

  1. afflom commented on Nov 3, 2026

    @afflom
    MemberAuthor

    I am taking this fix on release/v0.4, with forward propagation to release/v0.5 after landing. Scope: enforce the existing authoring-notation nesting bound on recursive readable terms and types, return positioned LLP2001 rather than abort, and extend AU-03 regression evidence with a deep-input fixture and boundary checks. This does not lift the semantic JSON reader limit requested in #375.

  2. added this to the LexLean v0.4.1 milestone on Nov 3, 2026
  3. afflom commented on Nov 3, 2026

    @afflom
    MemberAuthor

    Completed through merged PR #403 on release/v0.4, merge 5a44fe49e5d73569c3bb377bb28b56e463ee0547. The final reviewed head 215a9d591 passed all 43 jobs in CI 41658939956, plus honesty 41658939965 and reproducibility 41658939998. Actual merge tree 88d8b657f1ab621bf736b9d7e5d97fcb9c834e5e exactly equals the reviewed/tested head and synthetic merge tree. Explicitly closing this issue because the landing is on a non-default release branch.

  4. added a commit that references this issue on Nov 11, 2026
    bb464d3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions