leanprover / leanprover/lean4

Lean.Json.parse panics with "Nat.pow exponent is too big" on large exponents

Open
#13,987 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug P-low
Dominant language
Lean
Stars
9.2k
Forks
990
Avg merge
1d 17h
Merged PRs (30d)
175

Description

Prerequisites
Description

Lean.Json.parse crashes the whole program with INTERNAL PANIC: Nat.pow exponent is too big when given a JSON number with a large positive exponent such as 3E9999999993. This is not a recoverable parse error — the panic cannot be caught via the Except result, so the program aborts even though the caller handles both the .ok and .error cases. Since JSON input often comes from untrusted sources, this can be used to crash any program that parses external JSON.

Context

3E9999999993 is in fact valid JSON; Python and JavaScript both parse it to Infinity. Interestingly, an even larger exponent like 3E99999999999999999999999999999 does not crash and is correctly rejected with Invalid JSON: offset 31: exp too large, so only exponents in a specific range trigger the panic.

Steps to Reproduce
import Lean.Data.Json

def main : IO Unit := do
  let input := "3E9999999993"
  match Lean.Json.parse input with
  | .ok _    => IO.println "Valid JSON"
  | .error e => IO.println s!"Invalid JSON: {e}"
  -- This line should always be reached
  IO.println "End of program reached"

Expected behavior: Lean.Json.parse either succeeds or returns an .error, so that "End of program reached" is always printed.

Actual behavior: The program aborts with INTERNAL PANIC: Nat.pow exponent is too big and the final IO.println is never reached.

Versions

Lean 4.30.0, reproduced on latest nightly (live.lean-lang.org).

Additional Information

The cause appears to be in Lean.Json's exponent parsing. In exponent, positive exponents are bounded only by:

if n > USize.size then fail "exp too large"

For 3E9999999993 we have n = 9999999993, which is far below USize.size = 2^64, so the check passes and value.shiftl n is executed:

protected def shiftl : JsonNumber → Nat → JsonNumber
  | ⟨m, e⟩, s => ⟨m * (10 ^ (s - e) : Nat), e - s⟩

This evaluates 3 * 10 ^ 9999999993, and Nat.pow panics because the exponent exceeds its internal limit. (This also explains why a much larger exponent works: it exceeds USize.size and is rejected by the bounds check before shiftl is ever reached.)

The bound n > USize.size is far too loose. It should be checked against a realistic limit — either the actual Nat.pow limit, or, preferably, a much smaller threshold, since a JSON parser should not spend time and memory materializing numbers like 10 ^ 10000 even when Nat.pow could in principle handle them. For comparison, CPython caps the exponent at roughly n = 308.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in Lean.Json exponent parsing, particularly exponent and JsonNumber.shiftl, using the provided 3E9999999993 reproduction. Trace how the current USize.size check permits the panic and add coverage for large positive exponents. Done means Lean.Json.parse returns an error or succeeds without aborting, and the caller reaches the final output.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.