Explore alternatives to RustPython for Python AST parsing

[charliermarsh]

trafficstars

RustPython has been a good foundation, but Ruff is currently limited by what the RustPython parser does and does not support. See: #282, #54, #245.

Since we only need the parser (and RustPython is more ambitious -- they're trying to build an entire runtime / interpreter), there may be better options. RustPython is also going to be limited by their use of an LL(1) parser.

We could consider using the following:

• https://github.com/tree-sitter/tree-sitter-python
• https://github.com/pest-parser/pest
• https://github.com/kevinmehall/rust-peg

[charliermarsh]

Alternatively, could we use the CPython AST parser directly? It's written in C, AFAIK it should be very fast (perhaps even faster than the RustPython parser).

[charliermarsh]

Alternatively, we could try to continue merging improvements back to RustPython.

[charliermarsh]

Alternatively, we could revisit the use of LibCST.

[charliermarsh]

LibCST will also likely be required for auto-formatting.

[charliermarsh]

tree-sitter is an interesting option (demo in #295). It produces a CST, so we could use it to power auto-formatting. It's slower than RustPython but still quite fast (~350ms to iterate over the CPython codebase vs. ~230ms with RustPython). Because it's based on S-expressions, it has a whole pattern-matching syntax built-in, which we could use to power plugins...

I think the ergonomics on our end won't be great, because it just exposes a single Node type with a kind: &str field, and so we'd have to do all pattern-matching on string identifiers rather than encoding the AST in a type system. It also may not map 1:1 with the abstract grammar, I'm not certain.

Going to explore a few other options, but I'm intrigued...

[charliermarsh]

There's also rust-python-parser, which is based on nom.

[charliermarsh]

There's also rust-sitter, which sits on top of tree-sitter and lets you define the grammar on the Rust side via macros. In return, you get semantically meaningful structs when you generate the parse tree. The downside is that we'd have to re-write the Python grammar ourselves.

[charliermarsh]

If we were to use tree-sitter, we may want to write code to transform the generated tree into AST types on the Rust side, similar to the RustPython AST. (That would have to be closer to a CST, though.)

[charliermarsh]

rust-python-parser takes ~480ms (vs. 280ms for RustPython's parser) and fails on these files:

resources/test/cpython/Lib/_compression.py
resources/test/cpython/Lib/ast.py
resources/test/cpython/Lib/contextlib.py
resources/test/cpython/Lib/distutils/tests/test_sysconfig.py
resources/test/cpython/Lib/idlelib/colorizer.py
resources/test/cpython/Lib/idlelib/idle_test/mock_tk.py
resources/test/cpython/Lib/idlelib/pyparse.py
resources/test/cpython/Lib/idlelib/replace.py
resources/test/cpython/Lib/idlelib/run.py
resources/test/cpython/Lib/importlib/_bootstrap.py
resources/test/cpython/Lib/lib2to3/tests/data/py3_test_grammar.py
resources/test/cpython/Lib/linecache.py
resources/test/cpython/Lib/logging/__init__.py
resources/test/cpython/Lib/test/coding20731.py
resources/test/cpython/Lib/test/test_asyncio/test_locks.py
resources/test/cpython/Lib/test/test_asyncio/test_pep492.py
resources/test/cpython/Lib/test/test_asyncio/test_server.py
resources/test/cpython/Lib/test/test_contextlib_async.py
resources/test/cpython/Lib/test/test_coroutines.py
resources/test/cpython/Lib/test/test_dis.py
resources/test/cpython/Lib/test/test_format.py
resources/test/cpython/Lib/test/test_pkgutil.py
resources/test/cpython/Lib/test/test_sys_settrace.py
resources/test/cpython/Lib/test/test_types.py
resources/test/cpython/Lib/test/test_typing.py
resources/test/cpython/Lib/unittest/test/testmock/testasync.py
resources/test/cpython/Lib/zoneinfo/_zoneinfo.py
resources/test/cpython/Tools/c-analyzer/c_parser/preprocessor/__init__.py
resources/test/cpython/Tools/scripts/stable_abi.py
resources/test/cpython/Tools/unicode/makeunicodedata.py

[charliermarsh]

Ok, time for me to revive this thread and start thinking on the right long-term parser strategy. We need to support the 3.10 constructs!

[charliermarsh]

I'm strongly considering writing a new parser atop rust-peg or nom that adheres to the RustPython AST interface.

[charliermarsh]

@Seamooo - Do you have any thoughts on or interest in working on this too?

[Seamooo]

Definitely have some interest in this area. A couple of comments as I've been going down various rabbit holes of python parser implementations:

• The parser should be built from the CPython PEG, directly transpiled into either an equivalent grammar or used via proc_macro to generate the parser
  • Run into a lot of grammar specifications with weird FIXMEs about multiple edge cases because their grammar attempted to be a superset of CPython's, that didn't quite reduce down to the same grammar.
• proc_macro gives the ability to generate a perfect hash function for a set of keywords at compile time
• rust-peg seems to be an excellent compromise between exploiting the lower-bound time complexity for Packrat parsers without explicitly requiring caching every match, allowing multiple matches rather than lookups for manual performance tuning
• rust-peg also has the necessary extensions to the formalised PEG grammar such that implementing the python grammar is possible

[Seamooo]

Ideally when https://github.com/charliermarsh/ruff/pull/742 becomes mergeable, implementing those traits for the IR output by the parser would make it immediately useable.

[charliermarsh]

Yeah rust-peg does look good, and I believe that's what LibCST uses. My only hesitation there is that the LibCST parser is really slow compared to the RustPython parser? But I don't know how much, if any, of that is due to rust-peg. This is just based on the fixtures in the LibCST codebase:

rust_python_parse/all   time:   [289.30 µs 289.96 µs 290.64 µs]
                        change: [-4.8537% -4.5331% -4.2286%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 23 outliers among 100 measurements (23.00%)
  11 (11.00%) low mild
  2 (2.00%) high mild
  10 (10.00%) high severe

parse/all               time:   [1.7676 ms 1.7953 ms 1.8408 ms]
                        change: [-7.9448% -7.2284% -6.1601%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 10 outliers among 100 measurements (10.00%)
  7 (7.00%) high mild
  3 (3.00%) high severe

parse_into_cst/all      time:   [2.2262 ms 2.2477 ms 2.2723 ms]
                        change: [-2.7483% -0.8482% +0.8620%] (p = 0.40 > 0.05)
                        No change in performance detected.
Found 3 outliers among 100 measurements (3.00%)
  2 (2.00%) high mild
  1 (1.00%) high severe

(rust_python_parse/all is the RustPython parser, parse/all is the LibCST parser without inflation, and parse_into_cst/all is the LibCST parser with inflation.)

[charliermarsh]

(And agreed on #742.)

[charliermarsh]

Perhaps we could extend pegen with a Rust target based on rust-peg.

[isidentical]

CC: @davidhalter (I think you were working on a Rust-based Fast Python Parser [?])

[charliermarsh]

I'm going to start playing around with a straight port of pegen to Rust. (Or, more specifically, modifying pegen to output a Rust target, which IIUC will also require rewriting the Python code from data/python.gram in Rust.)

[davidhalter]

Thanks for bringing this up @isidentical.

I have indeed written a Python parser in Rust. But I do not feel comfortable sharing it yet. While it's faster than any other Python parser I have seen, it's a bit rough around error recovery and few other things, but generally parses all valid 3.10 Python programs (AFAIK). So if I ever release it, I'm happy to let you guys know.

[charliermarsh]

Thanks @davidhalter! Super cool. Would love to see it if you ever release it.

If you don't mind sharing: did you write it from scratch? Or is it built atop a parser generator?

[charliermarsh]

(I started on this in earnest tonight, I don't know if it will prove to be the right approach but the lower bound is that I learn a lot.)

[davidhalter]

@charliermarsh Yes I wrote it from scratch, it is a kind of weird mixture of LL and PEG, it's also a parser generator. I essentially pass it a slightly modified version of the official EBNF grammar.

I personally love writing parser generators, so when the opportunity presented itself, I took it :)

[charliermarsh]

@Seamooo - Do you have any interest in collaborating w/ me on the Rust port of pegen? It's a private repo right now but would be happy to add you and talk about how I'm iterating on it.

[Seamooo]

Definitely would be interested

[charliermarsh]

@Seamooo - Added you, repo is rough but your help is very welcome!

[ljodal]

I'd love (read) access as well, if possible. I don't think I'm much help in contributing, but I've been looking at rust-peg to generate a Python-compatible ast. My rust knowledge isn't there yet though, so I'm finding it a bit hard to get going (I have a working POC with a few manually defined nodes, but I don't think that'll tell us anything useful about the performance hit).

[charliermarsh]

@ljodal - Added! Would love to have any help / feedback.

(Anyone is welcome to be added, I'm just avoiding making it totally public while it's still in such an incomplete state.)

[DimitrisJim]

Anyone is welcome to be added

I'd like to take you up on that invitation if the attempt is still ongoing :-). We've recently been thinking of doing the same with RustPython's parser, porting pegen would just reduce the differences between grammar files between it and CPython, making syncing with it much easier. Not sure how much time I have lying around but I'd help as I could.

[charliermarsh]

@DimitrisJim - Added! You'll be able to tell from the contribution dates, but I haven't been able to push on it as much as I'd like lately (just other Ruff work taking priority). Any / all help or feedback welcome.

While you're here: to be clear, my preference would be to continue using the RustPython parser :) The goal of this task is, implicitly, to remove the parser as the bottleneck for what Ruff can support, i.e., to get us to a point where the parser can support all current language features.