[BUG] Parse time grows super-linearly on long dotted-name chains and nested parentheses (phase-2 lookahead), StackOverflowError at nesting depth ~2000 #2519

AI disclosure: this issue was prepared with AI coding agents, reviewed and revised line by line by me.

Two adversarial statements of around 4 KB each make CCJSqlParserUtil.parse burn seconds of CPU on current master. These shapes do not occur in hand-written or ORM-generated SQL; the exposure is services that parse SQL they do not fully control (query gateways, SQL auditing and firewalling, BI endpoints, data-lineage scanners) plus tools that open SQL files from untrusted sources. Public GitHub alone shows ~3000 files calling CCJSqlParserUtil.parse, so that consumer class is not hypothetical.

Measured impact on master 9a32ff5:

• The default Feature.timeOut (8000 ms) applies per attempt: a statement that times out in the simple pass is retried in the complex pass when its nesting depth allows it, so one crafted chain burns two full budgets (16 s wall clock, measured; 8 s with withAllowComplexParsing(false), measured).
• parse(String) runs each statement on a fresh single-thread executor, so concurrent crafted statements each hold their own core (measured: four 8k-part chains, 1.88 s each serial, completed in 1.88 s wall total).
• Callers supplying a shared executor get head-of-line blocking: a SELECT 1 submitted 100 ms behind a crafted statement waited 15.9 s (measured).
• Callers invoking the parser directly (new CCJSqlParser(...).Statement()) get no timeout at all; with quadratic growth a few hundred KB of chain means minutes of CPU per statement.

1. Long dotted-name chain: quadratic

SELECT a + .b x N + FROM t (a single column, parses fine):

Clean x3.5-x4 per doubling. Control: a comma-separated list of the same length parses flat (74 ms at 8000 items), so it is the dotted chain, not the statement size.

2. Nested parentheses: super-quadratic + StackOverflowError

SELECT + ( x N + 1 + ) x N:

Control: statement-level parentheses at the same depth 2000 parse in 23 ms, so the cost is specific to the parenthesized-expression path.

Both families burn in the SIMPLE pass: timings with withAllowComplexParsing(false) are identical to the defaults (the chain parses OK in simple mode, so the complex retry never runs; the parenthesis family is blocked from the retry by allowedNestingDepth(10) anyway).

Root-cause split (ablation)

Hot-stack sampling during both families bottoms out in the same chain: jj_3R_PrimaryExpression -> jj_3R_SimpleExpression -> jj_3R_Condition -> jj_3 -> jj_2_*, with isFunctionAhead() / isAllTableColumnsAhead() / isNestedSetOperationAhead() on top.

Two layers contribute:

1. Predicate layer (grammar side). isFunctionAhead() and isAllTableColumnsAhead() walk the whole remaining dotted chain unbounded, and the phase-2 routines re-evaluate them at every simulated position. I isolated this layer by memoizing both walks (cache keyed by start token, one walk filling every eligible chain part, measured walk work 2n+3 = linear). Chain parse time improved ~2.4x (8000 parts: 1847 -> 775 ms) but stayed quadratic (16000: 3613 ms), which leaves the second layer as the dominant cost.
2. Engine layer (generated code). With the predicates eliminated as a variable, the residual super-linear time sits in the phase-2 lookahead itself. Every jj_2_* invocation restarts the scan and re-runs the full simulation from the current token:

private boolean jj_2_107(final int xla) {
    jj_la = xla;
    jj_lastpos = jj_scanpos = token;
    ...
    final boolean _la_failed = jj_3_107();
    if (_la_failed) {
        jj_save(106, xla);
    }

There is no result memoization across invocations; jj_save (skipped on success since javacc-8-java 7fe8021) is backtracking bookkeeping only. The super-linearity persists on 8.1.2.1941, which already includes that optimization. In the parenthesis family the same re-simulation re-descends one level per parenthesis, which is also what exhausts the stack around depth 2000.

#1576 covered a deparse-side toString() recursion and is unrelated. #2489 / #2495 fixed the same predicate-walk class in Server / OracleHint.

Possible directions (your call)

1. Engine side, structural - and not memoization: I tested both obvious caches by hand-patching the generated code. Memoizing jj_2 outcomes by (routine, la, token) never hits (no repeated identical queries); memoizing jj_3R results by (routine, scan position, jj_la) hits ~37% yet leaves the asymptotics unchanged, because the number of DISTINCT probes itself grows super-linearly (37,459 misses at depth 300 -> 98,184 at depth 500). The cost is the choice structure generating super-linearly many lookahead probes, not recomputation. The pattern the project used in the feat: add support SELECT all columns from function result #2207 implementation - replacing a speculative syntactic lookahead with a bounded semantic follower check - looks like the right tool for the parenthesis-path choice points my stack samples point at. The StackOverflowError is orthogonal and cheap to fix in-repo: a depth counter in the parenthesized productions with a configurable clean bail, plus a larger stackSize on the parse worker thread (both strict improvements: nothing that parses today would fail, and today's SO depths would parse).
2. Grammar side, available today: I have a threshold-gated predicate memoization (walk aborts past 8 parts, restarts through the per-token cache). Measured: chains ~2.4x, walk work linear, full suite 4979/0 unchanged, no benchmark regression (interleaved jmh, 100 samples per run: 3.769/3.767 vs 3.783/3.799 ms/op, CIs overlap). Happy to turn it into a PR if you want it independently of (1); it only removes the predicate-layer share. If (1) lands and makes it redundant, closing that PR is fine.

Software Information

• JSqlParser master 9a32ff5
• JDK 17, plain CCJSqlParserUtil.parse with defaults

Reproducer

CCJSqlParserUtil.parse("SELECT a" + ".b".repeat(8000) + " FROM t");        // ~1.8 s
CCJSqlParserUtil.parse("SELECT " + "(".repeat(2000) + "1" + ")".repeat(2000)); // ~5.4 s, then StackOverflowError