Faster parser

[JukkaL]

Mypy uses the Python stdlib ast module for parsing. Currently parsing can take from 20% to 30% of the runtime when type checking without using the incremental cache. When processing third-party dependencies, the fraction tends to be higher, since function bodies get processed during parsing but won't be type checked.

A Python-level AST is currently constructed more than once. First the ast module constructs an AST, and this is converted into a mypy AST. If we'd use a different parser, we could only build a Python-level AST once. (ast also first constructs a C-level AST, but this is probably relatively fast.)

It seems to me that the most promising approach is to adapt an existing parser library written in a lower-level language such as C or Rust (I will call this the "low-level parser"). We'd generate a serialized AST in the low-level parser using the efficient binary format we now support for incremental cache files, and mypy would deserialize the output directly into a mypy AST. I'm hoping that this would improve parsing efficiency (including time needed to build the mypy AST) by 50-100%. Overall mypy performance would be improved by roughly 5% to 15%, and possibly more once we further optimize other parts of mypy.

The deserialization based approach also has a few other benefits:

• We can run the low-level parser in parallel by using the threading module, on all supported Python versions, since it doesn't need to hold the GIL during parsing.
• If the low-level parser can also produce a list of reachable import statements, we can build a module dependency graph without building a mypy AST. This would simplify parallel type checking using multiple processes.
• It will be easy to only deserialize a subset of the AST for a module. We could perhaps use this to lazily process imported modules, or to implement incremental parsing in mypy daemon.
• We can hopefully drop most function and method bodies in third-party dependencies without allocating a Python AST for them.

The Ruff parser and tree-sitter are the low-level parser options I've looked at so far. Based on some quick benchmarking, the Ruff parser appears to be much faster. The tree-sitter parser seems slow enough that it might not bring us significant performance gains (at least without multi-threading).

Integrating a new parser will be a substantial amount of work, so we should first do some prototyping to make sure the performance gains are feasible.

[JukkaL]

There are a few other implementation approaches I'm ignoring for now.

Implement a custom parser in C/Rust. Writing a recursive descent parser is not super complicated, but it will take effort to handle every corner case correctly (and it sounds a bit redundant, since parsers have been implemented multiple times for Python already). And it's not clear if we can make this much faster end-to-end than the Ruff parser, for example, even if we tune this to our use case. If using an existing parser doesn't work out for some reason, we will always have this option as a fallback.

Implement a custom parser in Python and compile it using mypyc. This would require some new mypyc features that are still not available to be efficient, and even then there will be some performance hit compared to C/Rust (and it's very hard to predict the level of performance until mypyc has all these new features). An interpreted version would also likely be quite slow, which could slow tests.

[A5rocks]

It would be a shame to put this much work into a parser and not support:

• mypy-specific type ignores
• parsing newer versions of Python than mypy is currently running on

(Both of these have issues open, and depend on having a custom parser)

I'm not sure whether we would want to have these in a first draft, but whatever we choose should be able to support both IMO. (And then we can have more justification for our own parser!)

[JukkaL]

It would be a shame to put this much work into a parser and not support:

mypy-specific type ignores
parsing newer versions of Python than mypy is currently running on

All of the options I discussed above should be able to support these. Even if reuse an existing parser, we can fork it and add support for mypy-specific type ignores. And since the parser wouldn't be implemented in Python, we don't need to restrict Python version support based on the Python version mypy is running on.

[JukkaL]

I've done some prototyping, and have PoC that supports a tiny subset of Python syntax. Based on the prototype, single-threaded performance seems significantly better -- maybe 1.5x to 2x parsing speed compared to current perf (when compiled). With parallelism the impact should be bigger. Even if using an interpreted mypy, the performance might get a little better.

Next steps:

• Prototype import reachability analysis (semantic analysis pass 1 -- this would have to be reimplemented in Rust).
• Finalize the serialization format. We have still plans to change the binary cache serialization format, and the AST serialization format will use a similar approach.
• Figure out a good way to report line/column information efficiently.
• Make sure we can get all the information we'll need, including type comments.

[A5rocks]

For number 4 maybe we could use some regex thing? It's probably harder to attach type-ignores to a relevant AST node than to just worry about line numbers. (this might make the case that for number 3 we just need a function that transforms an array of character positions into line/col numbers)

For number 2, does the AST really have to be serialized? I assume the cache only matters if a) the file was not edited and b) something the file depends on was edited. Probably that's not that common?

I've done some prototyping, and have PoC that supports a tiny subset of Python syntax.

What strategy did you use? (just curious about how easy it could be to eventually make some sort of recoverable parser...)

[JukkaL]

What strategy did you use?

I'm using the Ruff parser. It's currently a Rust command-line utility that writes a serialized Ruff AST to stdout and it's called from Python using subprocess -- it's very much a PoC :-)

The Ruff parser seems to provide error recovery (produce an AST even if there are syntax errors), and it can probably be adapted for incremental parsing by just parsing the whole source code and throwing away unmodified parts of the AST -- it seems fast enough for that.

For number 2, does the AST really have to be serialized?

That seems to be the easiest way to support fast parallel type checking using multiple processes. We don't want to construct a mypy AST twice, first in the main coordinator process (to build a dependency graph), and another time in the worker process (to actually type check the code). Now we can just use the serialized form in the main process and send the serialized bytes to the worker, which is much faster than constructing two ASTs.

Also this way the Rust part doesn't need to call into mypy. It would be tricky to get the Rust extension to construct mypy AST node instances directly (and efficiently). This is the only alternative I can think of that would provide similar (or better) performance without writing a fully custom parser.

I assume the cache only matters if a) the file was not edited and b) something the file depends on was edited. Probably that's not that common?

We are not going to cache/store the serialized AST, at least initially. It will just be used to transfer data from Rust to Python efficiently, and it will be immediately thrown away afterwards. The reference to caching above was about mypy incremental caching, which is otherwise unrelated but can use a similar implementation technique as AST serialization (but the incremental cache effectively caches symbol tables, not full ASTs).

this might make the case that for number 3 we just need a function that transforms an array of character positions into line/col numbers

Ruff already has something that is almost what we want, but my first impression is that it doesn't produce column numbers but byte offsets from line start (which is significant for UTF-8 files), but this shouldn't be hard to tweak.