Add `#[recursive]`

[blaginin]

Closes https://github.com/apache/datafusion-sqlparser-rs/issues/984, related to https://github.com/apache/datafusion/issues/9375#issuecomment-2469909998

Todo:

• [x] Test the performance overhead on large queries. If it's too high, move it to a separate feature to allow opting out

[blaginin]

I was wondering if we should remove RecursionCounter with this PR. In my opinion, we shouldn't, because the ability to limit max recursion might be useful for some users still

[blaginin]

It seems this PR doesn't have any significant performance impact.

critcmp main recursive                        
group                                                    main                                   recursive
-----                                                    ----                                   ---------
sqlparser-rs parsing benchmark/format_large_statement    1.00   309.1±12.72µs        ? ?/sec    1.01    312.4±7.45µs        ? ?/sec
sqlparser-rs parsing benchmark/parse_large_statement     1.02      6.3±0.35ms        ? ?/sec    1.00      6.2±0.40ms        ? ?/sec
sqlparser-rs parsing benchmark/parse_sql_large_query     1.00      6.1±0.23ms        ? ?/sec  
sqlparser-rs parsing benchmark/sqlparser::select         1.02  1893.8±82.19ns        ? ?/sec    1.00  1855.1±25.08ns        ? ?/sec
sqlparser-rs parsing benchmark/sqlparser::with_select    1.03     11.7±1.20µs        ? ?/sec    1.00     11.4±0.28µs        ? ?/sec

[blaginin]

FYI, I marked this ready for review. @peter-toth @Eason0729, if you guys want to take a look 🌻

[iffyio]

@blaginin thanks for looking to fix this!

Currently the preference is to avoid a third-party dependency for this issue, ideally fixing up the parser behavior instead to properly handle deeply nested input. See comment here for a bit more context on rationale From a quick look at recursive it seems to be a procmacro on top of the stacker library so that the same considerations should apply I imagine.

[peter-toth]

Currently the preference is to avoid a third-party dependency for this issue, ideally fixing up the parser behavior instead to properly handle deeply nested input. See comment here for a bit more context on rationale From a quick look at recursive it seems to be a procmacro on top of the stacker library so that the same considerations should apply I imagine.

@iffyio, we had done some research on stacker / recursive in https://github.com/apache/datafusion/pull/13310 to verify concerns before we added it to datafusion: https://github.com/apache/datafusion/pull/13310#pullrequestreview-2424590466 / https://github.com/apache/datafusion/pull/13177#issuecomment-2465457730

[Eason0729]

Currently the preference is to avoid a third-party dependency for this issue, ideally fixing up the parser behavior instead to properly handle deeply nested input. See comment here for a bit more context on rationale From a quick look at recursive it seems to be a procmacro on top of the stacker library so that the same considerations should apply I imagine.

@iffyio, we had done some research on stacker / recursive in https://github.com/apache/datafusion/pull/13310 to verify concerns before we added it to datafusion: https://github.com/apache/datafusion/pull/13310#pullrequestreview-2424590466 / https://github.com/apache/datafusion/pull/13177#issuecomment-2465457730

Sorry for missing that context when reviewing. So we would like to avoid using recursive for stablility, maybe try...

1. vender the code from recursive
2. use stacker directly, like https://github.com/apache/datafusion-sqlparser-rs/pull/1468

[blaginin]

Thanks for the review!! 🙂

Sorry for missing that context when reviewing. So we would like to avoid using recursive for stablility, maybe try...

We ended up using #[recursive] in Datafusion, as Peter highlighted. Feels like it’s good to stay consistent across projects?

[iffyio]

Ah I see, thanks for the context @peter-toth!

cc @alamb for overall thoughts on adding this dependency to sqlparser?