fmcmac opened a new pull request, #2440: URL: https://github.com/apache/datafusion-sqlparser-rs/pull/2440
## Problem `RecursionCounter` is charged at five sites today — `parse_statement`, `parse_subexpr`, `parse_query`, `parse_table_factor`, and `parse_interval` (added in #2422). Each was added in response to a specific report, and nothing asserts they cover every recursive path. Where they don't, `with_recursion_limit` is silently **inert** and input recurses until the stack runs out. Demonstrated directly on current `main`, 2 MB stack, release build, `Parser::parse_sql` only. Each of these fails to return within 10 s: | shape | SQL | |---|---| | recursive types | `SELECT CAST(1 AS Nullable(Nullable(…)))` — also `LowCardinality`, `Map`, `Tuple`, `Nested`, `ARRAY<…>`, `STRUCT<…>` | | MATCH_RECOGNIZE | `MATCH_RECOGNIZE(PATTERN ((((…))))` | | JSON_TABLE | `JSON_TABLE(… NESTED PATH … COLUMNS(…))` | | Snowflake options | `COPY_OPTIONS=(a=(b=(…)))` | | parens-less joins | `SELECT * FROM t JOIN t JOIN t …` (Snowflake) — this one **stack-overflows** | 2000 nested `Nullable(` is about 2 KB of SQL. `with_recursion_limit(5)` does not stop any of them. ## Method Audited rather than patched by example — fixing the shapes someone happened to report is what produced the current state. I built the call graph over every `Parser` method, deleted the counted functions, and recomputed the strongly connected components. Anything still recursive is a cycle that can spin without ever reaching a guard. On current `main` that finds **eight** such cycle groups. Each is now either counted or carries a comment recording why it cannot recur on input. ## Newly counted `parse_data_type_helper`, `parse_pattern`, `parse_json_table_column_def`, `parse_key_value_options`, `parse_joins`. Two of these are worth calling out: **`parse_data_type_helper`, not `parse_data_type`.** The obvious place is the public `parse_data_type`, but `ARRAY<…>` and `STRUCT<…>` recurse into the helper *directly* in order to thread `MatchedTrailingBracket` through. A guard on `parse_data_type` alone leaves both angle-bracket forms uncounted. **`parse_joins`.** It's tempting to argue the self-call is already charged, since reaching it requires a `parse_table_factor` and that takes a guard. That reasoning is wrong: `DepthGuard` releases on drop, and `parse_table_factor` has already returned by the time `parse_joins` recurses, so nothing accumulates. Deliberately **not** counted, with the reason in a comment: `parse_remaining_set_exprs`. It cycles with `parse_query_body` but cannot recur on input — the left side is consumed by a loop (so long same-precedence chains stay iterative) and the right side only recurses on increasing precedence, of which there are two levels. ## Second defect: the guard's own error was discarded `parse_prefix` matched only the `Ok` arm of a `maybe_parse` fallback, dropping `RecursionLimitExceeded` and **retrying the same span** under a second interpretation. `maybe_parse` re-raises that error precisely so callers can propagate it. Two consequences, both on an already-*counted* path: 1. **Exponential.** The retry re-descends the same input once per level. Nested `CAST(…)` did not return at ~650 bytes of SQL. 2. **Silent AST corruption.** When the retry happened to succeed, the same SQL parsed to a *different tree* at different recursion limits, returned as `Ok`. Six nested `CASE` rendered with 2, 5 or 6 `END`s at limits 5, 8 and 12. (2) is a correctness bug independent of any resource concern, and is what `recursion_limit_does_not_change_the_parsed_ast` pins. ## Results Every shape above now denies with `RecursionLimitExceeded` in under 2 ms. Not made too eager: `INT[][]…[]` ×5000 and a 20,000-operand `UNION` chain are assembled iteratively and still parse. The cliff is remaining stack, not input size — 5000-deep `Nullable(` completed in 1.8 ms at an 8 MB stack while wedging at 2 MB. None of the numbers above should be treated as thresholds. ## Tests Tests assert the clean `RecursionLimitExceeded` rather than merely that parsing finished, and run each parse on its own thread with a timeout, so a regression fails loudly instead of hanging CI. Successful parses are `mem::forget`-ed, because the derived `Drop` on the AST is itself recursive and dropping a deep tree performs the very descent under test. Full suite passes (1592 tests). `cargo fmt` clean; no new clippy warnings. ## Note Reaching the default limit of 50 itself costs stack: the `parse_prefix → parse_cast_expr → parse_expr → parse_subexpr` chain runs ~85 KB per level unoptimised, so a debug build wants ~5 MB of headroom before the guard can fire. Documented on `with_recursion_limit`. I have not changed `DEFAULT_REMAINING_DEPTH` — that's a judgement call for maintainers. One further finding I did **not** act on: the audit reports a cycle `parse_object_name → parse_object_name_inner → parse_function_args → function_arg_expr_from_wildcard → parse_wildcard_additional_options → parse_optional_select_item_exclude → parse_object_name` that exists on `main` but not in v0.61. I could not construct an input that drives it, so I have left it alone rather than guess at a guard. Flagging it in case someone recognises a shape that reaches it. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
