Skip to content

Use a flat Python AST in Ruff and ty - #29817

Draft
MichaReiser wants to merge 47 commits into
micha/boxed-mapping-pattern-itemsfrom
micha/flat-python-ast
Draft

MichaReiser wants to merge 47 commits into
micha/boxed-mapping-pattern-itemsfrom
micha/flat-python-ast

Conversation

@MichaReiser

@MichaReiser MichaReiser commented Oct 29, 2026 •

Copy link
Copy Markdown
Member

Summary

Ruff and ty parse Python into 24-byte rows linked by four-byte node IDs. Typed nodes borrow fields from the parsed module, lint fixes build replacement syntax in an arena, and ty stores row IDs without a separate node-numbering pass. Python AST storage and traversal

Review order

The PR starts at the boxed mapping-pattern layout in #29889. The first five commits migrate the AST and its consumers. The remaining 41 isolate subsequent changes. Both Ruff and ty build at the fifth commit. Boxed parent 0f8d2da79c.

  1. Replace boxed Python AST nodes with named arena views. 466cd822cc
  2. Parse and cache Python modules in a flat AST. a19708bfa5
  3. Run Ruff lint rules and build fixes from arena nodes. 16cfcafc3a
  4. Format Python directly from arena nodes. 1863efdc04
  5. Read the flat AST in semantic and IDE queries. 37db863a96

Performance

The boxed and flat revisions both contain #29916, which resolves a call’s qualified name once for the applicable lint rules. Both use source offsets for Ruff’s name-binding map. These measurements predate the comparison optimizations at the base of the stack. The measured flat executable used Git tree 2f1051bec9. Boxed 48b74912c7 · Flat d28e863169.

Ruff lint

The five repository fixtures run with the default rules, all stable rules and all rules including preview. The benchmark parses each module before the timed lint call. Each row sums the same 15 jobs. Expression checking runs inside check_ast, so these scopes overlap.

Scope Boxed Flat Change
Lint instructions before parsed-module destruction 147,763,734 152,327,272 +3.09%
Instructions in check_ast 111,651,743 115,944,765 +3.85%
Instructions in expression checks and their callees 54,240,752 59,145,713 +9.04%
Instructions to drop the parsed module 4,299,969 81,527 −98.10%
All timed lint instructions 152,063,703 152,408,799 +0.23%
Simulated L1 instruction-cache misses in check_ast 4,797,539 5,469,977 +14.02%
Simulated L1 instruction-cache misses in expression checks 2,848,002 3,269,487 +14.80%
Simulated L1 instruction-cache misses in the full lint call 4,888,425 5,558,886 +13.72%

Both checkers dispatched 26,613 expressions. Among rules with matching native call counts on every fixture, 175 call rules account for 2,120,584 additional instructions and 17 comparison rules for 902,616. The shared callee-name resolution itself ran 2,925 times in each build and cost 22,413 additional instructions. Inlining prevents a separate count for every rule.

For client.send(), S201 checks whether the method name is run, and S610 checks whether it is extra. Each rule receives the decoded call fields. Each still reads the attribute’s identifier. The boxed attribute embeds the identifier. The flat attribute holds a four-byte ID, so the getter loads the ID and resolves the identifier row. S201 · S610

Lint instructions by fixture and rule selection, excluding parsed-module destruction
Workload Boxed Flat Change
numpy/globals.py · Default 325,415 343,804 +5.65%
numpy/globals.py · All stable 842,195 870,555 +3.37%
numpy/globals.py · All with preview 967,922 1,005,134 +3.84%
numpy/ctypeslib.py · Default 3,579,185 3,695,833 +3.26%
numpy/ctypeslib.py · All stable 7,267,614 7,479,487 +2.92%
numpy/ctypeslib.py · All with preview 8,940,307 9,182,057 +2.70%
unicode/pypinyin.py · Default 1,051,677 1,108,285 +5.38%
unicode/pypinyin.py · All stable 2,975,627 3,079,842 +3.50%
unicode/pypinyin.py · All with preview 3,467,273 3,574,212 +3.08%
pydantic/types.py · Default 7,508,874 7,917,573 +5.44%
pydantic/types.py · All stable 14,112,344 14,686,003 +4.06%
pydantic/types.py · All with preview 17,482,955 18,055,002 +3.27%
large/dataset.py · Default 14,097,604 14,626,100 +3.75%
large/dataset.py · All stable 28,556,834 29,358,466 +2.81%
large/dataset.py · All with preview 36,587,908 37,344,919 +2.07%

The first complete flat migration used 161,812,123 instructions before destruction (+9.51% versus boxed). The subsequent commits reduced this to 152,327,272 (−5.86% versus the first flat version). 85f8507b0e

Lint instructions after each of the final five changes
Flat version Before destruction Change from preceding row Simulated L1I misses in the checker
Pass borrowed AST fields to lint rules. 117e774f6f 153,367,040 — 5,508,683
Reuse decoded call fields in comprehension rules. b2ba50093f 153,191,177 −175,863 0
Read method parameters after matching new. 7436ae13a8 153,180,900 −10,277 0
Keep keyword and positional searches together in call argument lookup. 4e0503771c 153,030,973 −149,927 0
Reserve room for small expressions in the AST builder. c72ee7afd8 152,869,183 −161,790 0
Iterate parameters from the stored list of node IDs. d28e863169 152,327,272 −541,911 5,469,977
Compare the two boxed layout PRs and the flat AST on the same 15 lint jobs
Revision Instructions before destruction Change from boxed main Simulated L1I misses in the checker Instructions including destruction
Boxed main d71685096a 148,090,315 — 4,784,764 152,385,916
Boxed with DictItem fd8861c839 147,685,674 −0.27% 4,815,095 151,983,841
Boxed with both layout PRs 48b74912c7 147,763,734 −0.22% 4,797,539 152,063,703
First complete flat AST 85f8507b0e 161,812,123 +9.27% 5,780,218 161,890,527
Final flat AST d28e863169 152,327,272 +2.86% 5,469,977 152,408,799

Complete Ruff and ty commands

These profiling builds run the actual CLI commands with one worker. The before-destruction columns subtract the instructions in the parsed-module destructor from the same process. Both variants produced identical Ruff diagnostics, edits, formatter output and ty diagnostics.

Command Boxed instructions before destruction Flat instructions before destruction Change before destruction Change including destruction
Ruff lint, CPython default 2,677,589,506 2,769,739,054 +3.44% +0.40%
Ruff lint, Jinja2 default 169,500,048 177,088,072 +4.48% +1.53%
Ruff lint, Pygments all stable 2,886,686,226 2,899,463,571 +0.44% −0.61%
Ruff format, stdlib 10,399,807,146 10,369,784,860 −0.29% −1.07%
ty, Jinja2 2,228,591,924 2,168,164,728 −2.71% −2.93%
ty, Pygments 7,969,608,697 7,792,314,876 −2.22% −2.60%
ty, stdlib 18,878,516,926 18,495,761,323 −2.03% −2.45%

The lint projects contain 568 CPython files, 25 Jinja2 files and 321 Pygments files. The formatter row uses the median whole-command result from three runs per layout on 568 files. Each ty project uses one matched pair.

Whole-command instructions and parsed-module destruction
Command Boxed total Flat total Boxed destruction Flat destruction
Ruff lint, CPython default 2,761,197,642 2,772,240,080 83,608,136 2,501,026
Ruff lint, Jinja2 default 174,542,133 177,220,223 5,042,085 132,151
Ruff lint, Pygments all stable 2,917,956,791 2,900,177,927 31,270,565 714,356
Ruff format, stdlib 10,483,958,267 10,372,241,064 84,151,121 2,456,204
ty, Jinja2 2,233,689,913 2,168,337,276 5,097,989 172,548
ty, Pygments 8,000,727,268 7,792,962,969 31,118,571 648,093
ty, stdlib 18,963,120,293 18,497,602,667 84,603,367 1,841,344
Complete Ruff lint commands compared directly with boxed main

Plain boxed main, the boxed parent with both layout changes and the flat head use the same inputs. All three produced byte-identical CLI output.

Project Boxed main before destruction Boxed parent before destruction Flat before destruction Flat versus main
CPython default 2,679,446,632 2,677,589,506 2,769,739,054 +3.37%
Jinja2 default 169,664,484 169,500,048 177,088,072 +4.38%
Pygments all stable 2,892,102,210 2,886,686,226 2,899,463,571 +0.25%

Hosted CodSpeed

CodSpeed compared flat d28e863169 with its boxed parent 48b74912c7. Its three reported regressions are CPU simulations of linting numpy/globals.py. Across all instruments it reported 167 improvements, 118 unchanged benchmarks and 14 skipped. The report flags different runner hardware for 127 benchmarks with significant changes. Hosted results

The local columns repeat the corresponding repository lint benchmark on the same fixture, including destruction of the parsed module. CodSpeed's CPU simulation models both executed instructions and cache-miss penalties. CPU simulation

NumPy lint rule selection Hosted CPU efficiency Boxed instructions Flat instructions Boxed L1 instruction-cache misses Flat L1 instruction-cache misses
Default −5.60% 333,041 344,343 12,123 13,890
All stable −5.09% 849,821 871,094 22,767 25,380
All with preview −6.73% 975,548 1,005,673 24,551 28,066

In the preview benchmark, check_ast accounts for 3,328 of the 3,515 additional L1 instruction-cache misses. L1 data-read misses fall from 2,636 to 2,408.

How instruction-cache capacity affects the same file in the Ruff CLI

These runs collect instructions inside check_path in an isolated, single-file CLI invocation. Each pair produced identical diagnostics. The cache simulations use the same profiling binaries, eight-way instruction caches with 64-byte lines, and fixed data and last-level caches.

Rule selection Distinct machine instructions executed, boxed Distinct machine instructions executed, flat Extra flat L1 instruction misses, 32 KiB Extra flat L1 instruction misses, 256 KiB Extra flat L1 instruction misses, 4 MiB
Default 47,438 53,139 1,947 710 516
All stable 105,766 115,249 3,216 1,759 847
All with preview 116,512 126,911 3,630 1,927 882

Increasing the cache from 32 KiB to 4 MiB removed 74–76% of the extra misses. Holding capacity at 32 KiB and making the cache fully associative left gaps of 1,903, 3,892 and 3,408 misses, respectively. The flat CLI executes a larger set of machine instructions, and the smaller cache repeatedly fetches some of that code. These measurements establish the effect of capacity in the simulator. Quantifying how much inlining contributes would require a separate comparison.

Review the 41 commits after the basic migration
  • Store compact AST IDs in Ruff’s semantic node table. 4671a24d28
  • Share the list boundary between comparison operators and operands. b28d6670e2
  • Read the operator of a single comparison directly from its row. 9197d82ec1
  • Cache recently interned Python identifier spellings while parsing. 5df7b12170
  • Reserve initial AST buffers from the source length. 0744f8273a
  • Estimate arena growth from the rows emitted during parsing. d727ad2b49
  • Reserve AST row zero so child IDs index their arena directly. 7ae6500979
  • Align Python AST rows to eight bytes. 03d630d026
  • Read and write AST row fields through a typed payload union. 8206b084bf
  • [ty] Resolve persisted AST references by parser row and remove the node-index pass. b07cd8977a
  • Record function body rows for scope-aware return and yield checks. 18af1be6ea
  • Skip generator lint-rule walks when function rows contain no yield. f7c968677e
  • Keep ordinary parameter lists inline in AST rows. 24b2e68768
  • Store parameters in source order in the AST. d3ca11300a
  • Write parsed parameters into the arena directly from parser scratch storage. 0c6de85d0d
  • Store call arguments in source order. eb56d0de96
  • Store class pattern arguments in source order. a604949e30
  • Borrow remaining child lists during descendant traversal. 69ddb091c7
  • Borrow adjacent child IDs directly from AST rows. 6308082813
  • Store conditional expression fields in source order. 6d969ef5ba
  • [ty] Skip semantic reference walks when no AST keyword label matches. 7c32da470d
  • Construct child iterators from the known type of a borrowed node. b881497b3d
  • Use child endpoints and statement traversal in the formatter. 5a1a58efaf
  • Read expression fields directly when comparing AST nodes. 0d1aecd042
  • Read version-check literals through their node getters. ebe7c2f704
  • Write positional arguments immediately before keyword arguments in the arena. 1ac46df1cc
  • Keep the first assignment target on the stack. ffb5aee129
  • Keep the first parsed comparison on the stack. 30a2b7ce29
  • Forward indexed argument lookups to the source-order iterator. 2e9277139d
  • Bound speculative reservations for AST rows and side tables. 7f761cdc1c
  • Decode Python literals directly into the AST buffers. c1dc702ec3
  • Read formatter predicates through typed AST getters. 2dc5c50184
  • Read lint rule inputs through typed AST getters. 8b85abcec6
  • [ty] Read inference and IDE inputs through typed AST getters. 86268ac880
  • Keep borrowed AST nodes in Ruff’s semantic model. 77b925149c
  • Pass borrowed AST fields to lint rules. 0047cd0beb
  • Reuse decoded call fields in comprehension rules. 8e9db15765
  • Read method parameters after matching new. c423b19c27
  • Keep keyword and positional searches together in call argument lookup. 97b87a9352
  • Reserve room for small expressions in the AST builder. 1717bf5c83
  • Iterate parameters from the stored list of node IDs. 1890f9a1bd

Test coverage

Parser fixtures and the existing lint and formatter suites exercise the arena through its consumers. Traversal tests cover source order for valid and recovered syntax. ty’s semantic tests cover resolving stored node IDs, including in quoted annotations.

A boxed-versus-flat check over 1,731 fixture and rule-setting pairs matched all 66,678 diagnostics and 29,731 fixes. A separate check exercised all 70 rules in the shared callee dispatch using direct, aliased, unresolved and shadowed callees and per-file ignores. All 228 diagnostics and 138 fixes matched, including applicability and edit text.

@MichaReiser MichaReiser added performance Potential performance improvement parser Related to the parser ty The ty type checker memory An issue regarding poor memory usage, or a PR improving memory usage labels Oct 29, 2026
@astral-automations-bot

astral-automations-bot Bot commented Oct 29, 2026 •

Copy link
Copy Markdown
Contributor

Typing conformance results

No changes detected ✅

Current numbers
The percentage of diagnostics emitted that were expected errors held steady at 98.60%. The percentage of expected errors that received a diagnostic held steady at 98.86%. The number of fully passing files held steady at 137/146.

Results for 0936621 · Workflow run

@astral-automations-bot

astral-automations-bot Bot commented Oct 29, 2026 •

Copy link
Copy Markdown
Contributor

Memory usage report

Summary

Project Old New Diff Outcome
flake8 38.07MB 33.28MB -12.58% (4.79MB) ⬇️
trio 91.97MB 84.72MB -7.88% (7.25MB) ⬇️
sphinx 185.42MB 170.70MB -7.94% (14.72MB) ⬇️
prefect 455.47MB 426.37MB -6.39% (29.09MB) ⬇️

Significant changes

Click to expand detailed breakdown

flake8

Name Old New Diff Outcome
parsed_module 14.47MB 9.88MB -31.73% (4.59MB) ⬇️
semantic_index 9.27MB 9.07MB -2.14% (202.97kB) ⬇️

trio

Name Old New Diff Outcome
parsed_module 22.00MB 15.12MB -31.25% (6.87MB) ⬇️
semantic_index 18.57MB 18.20MB -2.01% (382.01kB) ⬇️

sphinx

Name Old New Diff Outcome
parsed_module 44.49MB 30.53MB -31.38% (13.96MB) ⬇️
semantic_index 35.06MB 34.30MB -2.17% (777.89kB) ⬇️

prefect

Name Old New Diff Outcome
parsed_module 87.51MB 60.27MB -31.12% (27.24MB) ⬇️
semantic_index 87.41MB 85.55MB -2.13% (1.86MB) ⬇️

Results for 0936621 · Workflow run

@astral-automations-bot

astral-automations-bot Bot commented Oct 29, 2026 •

Copy link
Copy Markdown
Contributor

ecosystem-analyzer results

No diagnostic changes detected ✅

Full report with detailed diff · Timing results


Results for 0936621 · Workflow run

@astral-automations-bot

astral-automations-bot Bot commented Oct 29, 2026 •

Copy link
Copy Markdown
Contributor

ruff-ecosystem results

Linter (stable)

✅ ecosystem check detected no linter changes.

Linter (preview)

✅ ecosystem check detected no linter changes.

Formatter (stable)

✅ ecosystem check detected no format changes.

Formatter (preview)

✅ ecosystem check detected no format changes.

Linter (stable) · Linter (preview) · Formatter (stable) · Formatter (preview)


Results for 0936621 · Workflow run

Comment on lines +9 to +10
let rewritten = owned_pattern_to_expr(pattern.view(storage).to_owned_node());
let id = ast::flat::Lower::lower(&rewritten, storage);

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

[P3] Avoid retaining entire subtrees during pattern recovery

A malformed class pattern whose head is a sequence reaches this conversion at each nesting level. to_owned_node() copies the entire previously recovered subtree, and Lower::lower appends its literal bytes to the same Builder without reclaiming the originals. Nesting around one large string therefore retains memory proportional to literal size × nesting depth, allowing an attacker-controlled file in an untrusted language-server workspace to exhaust host memory. The previous implementation moved owned children. Construct the recovery nodes using existing child handles to avoid retaining these repeated copies.

@codspeed

codspeed Bot commented Oct 29, 2026 •

Copy link
Copy Markdown

Merging this PR will regress 5 benchmarks

1 warning

⚠️ 112 benchmarks with a significant change ran on different hardware

Their base and head results were measured on machines with a different CPU, core count or memory, so the changes might not come from the code. Run base and head on the same runner type.

Learn more about Macro Runners

See affected benchmarks

⚡ 176 improved benchmarks
❌ 5 regressed benchmarks
✅ 113 untouched benchmarks
⏩ 14 skipped benchmarks1

Warning

Please fix the performance issues or acknowledge them on CodSpeed.

Performance Changes

Mode Benchmark BASE HEAD Efficiency
❌ CPU Simulation linter/all-with-preview-rules[numpy/globals.py] 1.3 ms 1.4 ms -7.68%
❌ CPU Simulation linter/default-rules[numpy/globals.py] 617.4 µs 659.5 µs -6.39%
❌ CPU Simulation linter/all-rules[numpy/globals.py] 1.2 ms 1.2 ms -6.2%
❌ CPU Simulation linter/default-rules[pydantic/types.py] 8.5 ms 8.9 ms -4.63%
❌ CPU Simulation linter/all-with-preview-rules[pydantic/types.py] 17.6 ms 18.4 ms -4.53%
⚡ Memory parser[numpy/globals.py] 16.7 KB 11.4 KB +47.28%
⚡ Memory parser[unicode/pypinyin.py] 44.6 KB 33.8 KB +31.84%
⚡ Memory parser[pydantic/types.py] 281.7 KB 218.1 KB +29.12%
⚡ Memory parser[large/dataset.py] 645.4 KB 513.3 KB +25.73%
⚡ Walltime auto_imports[namespace-package/repeated-request] 2.8 ms 2.2 ms +23.59%
⚡ Walltime auto_imports[regular-package/repeated-request] 2.9 ms 2.3 ms +23.37%
⚡ Memory parser[numpy/ctypeslib.py] 134.9 KB 109.8 KB +22.88%
⚡ Walltime auto_imports[regular-package/first-request] 73.9 ms 61.6 ms +19.99%
⚡ Walltime auto_imports[namespace-package/first-request] 75.8 ms 63.7 ms +18.85%
⚡ Memory ty_micro[pandas_tdd] 26.6 MB 23.1 MB +15.29%
⚡ Walltime auto_imports[regular-package/after-module-create] 4 ms 3.5 ms +15.14%
⚡ Memory ty_micro[very_large_tuple] 7.4 MB 6.4 MB +14.49%
⚡ Memory ty_micro[async_context_manager_recursive_protocol] 7.8 MB 6.9 MB +14.02%
⚡ Memory ty_micro[complex_constrained_attributes_3] 7.6 MB 6.7 MB +13.85%
⚡ Memory ty_micro[split_literal_union_1024] 4.8 MB 4.2 MB +13.66%
... ... ... ... ... ...

ℹ️ Only the first 20 benchmarks are displayed. Go to the app to view all benchmarks.

Tip

Investigate this regression by commenting @codspeedbot fix this regression on this PR, or directly use the CodSpeed MCP with your agent.


Comparing micha/flat-python-ast (0936621) with micha/boxed-mapping-pattern-items (3c2225d)

Open in CodSpeed

Footnotes

  1. 14 benchmarks were skipped, so the baseline results were used instead. If they were deleted from the codebase, click here and archive them to remove them from the performance reports. ↩

@AlexWaygood AlexWaygood changed the title [ty] Use a flat Python AST in Ruff and ty Use a flat Python AST in Ruff and ty Oct 29, 2026
@AlexWaygood AlexWaygood removed the ty The ty type checker label Oct 29, 2026
@MichaReiser
MichaReiser force-pushed the micha/flat-python-ast branch from bd231d4 to 59e0aa9 Compare October 29, 2026 19:19
@dcreager

Copy link
Copy Markdown
Member

YES

Reuse the expression or statement kind across checker dispatch and child traversal. Visitors that specialize a node can forward the kind they already matched. Pattern and type-parameter walkers use the same convention, and the exception-handler walker accepts its concrete node.

Keep the capture name across pattern traversal so mapping patterns look up their rest capture once while preserving binding order.

This branch was previously deployed

1 inactive deployment
automations — 0936621a Deployed Nov 4, 2026 by MichaReiser via security-review / security review #97198
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

memory An issue regarding poor memory usage, or a PR improving memory usage parser Related to the parser performance Potential performance improvement

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants