perf(formatter): sort imports during IR construction by overlookmotel · Pull Request #22065 · oxc-project/oxc

overlookmotel · 2026-05-02T02:23:42Z

Import sorting operates on IR, rather than AST. Previous attempts to make it pre-sort the AST were abandoned primarily due to difficulties with re-ordering the comments attached to the ImportDeclarations, because AST to IR conversion relies on comments being output in source order.

This PR is a "middle way" approach. Import sorting still operates on IR, but happens during AST to IR conversion, rather than in a separate pass after IR for the whole file has been generated.

The main advantages of this approach:

The sorting transform only has to deal with small sections of IR which contain only import statements (and comments and line breaks surrounding them), rather than searching through the IR for the entire file.
Now when transform runs on a chunk of IR, it's at the end of the buffer, so replacing the unsorted FormatElements with the newly sorted ones is only a matter of popping the old ones off end of the buffer, and pushing the new ones on. This is much faster than copying the entire IR into a new buffer, which is what we had to do previously in order to shuffle up/down all the following FormatElements.

The main disadvantage is that we lose the simplicity and "stand alone" nature of the separate sorting pass. But IMO the perf improvement is probably a good trade off.

In this PR, I've prioritized altering the core sorting logic as little as possible, so that it's easier to review and verify that this change does not alter behavior. The structure of the code is therefore a bit odd (e.g. SortImportsTransform struct would better be replaced by just a free function now), and there's other refactoring and further perf improvements that we can make, but I've left them to follow-ups.

overlookmotel · 2026-05-02T02:23:55Z

How to use the Graphite Merge Queue

Add either label to this PR to merge it via the merge queue:

0-merge - adds this PR to the back of the merge queue
hotfix - for urgent changes, fast-track this PR to the front of the merge queue

You must have a Graphite account in order to use the merge queue. Sign up using this link.

_{An organization admin has enabled the Graphite Merge Queue in this repository.} _{Please do not merge from GitHub as this will restart CI on PRs being processed by the merge queue.}

This stack of pull requests is managed by Graphite. Learn more about stacking.

codspeed-hq · 2026-05-02T02:28:02Z

Merging this PR will improve performance by 24.9%

⚠️

Different runtime environments detected

Some benchmarks with significant performance changes were compared across different runtime environments,
which may affect the accuracy of the results.

Open the report in CodSpeed to investigate

⚡ 8 improved benchmarks
✅ 36 untouched benchmarks
⏩ 7 skipped benchmarks¹

Performance Changes

	Mode	Benchmark	`BASE`	`HEAD`	Efficiency
⚡	Simulation	`formatter[types.ts]`	14.6 ms	14 ms	+4.47%
⚡	Simulation	`formatter[index.tsx]`	4.6 ms	3.9 ms	+16.2%
⚡	Simulation	`formatter[App.tsx]`	49.4 ms	45.3 ms	+9.03%
⚡	Simulation	`formatter[Search.tsx]`	1.9 ms	1.7 ms	+9.82%
⚡	Simulation	`formatter[next.ts]`	2.8 ms	2.4 ms	+18.25%
⚡	Simulation	`formatter[errors.ts]`	776.1 µs	629.6 µs	+23.27%
⚡	Simulation	`formatter[handle-comments.js]`	3.6 ms	2.9 ms	+23.76%
⚡	Simulation	`formatter[core.js]`	2 ms	1.6 ms	+24.9%

_{Comparing om/05-02-perf_formatter_sort_imports_during_ir_construction (c744bdd) with om/05-02-test_formatter_add_tests_for_import_sorting_in_ambient_modules (484b615)}

7 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. ↩

Copilot

Pull request overview

Moves import sorting to happen during AST→IR construction (streaming) rather than as a whole-document post-pass, aiming to reduce IR scanning/copying costs while preserving existing sorting behavior.

Changes:

Sort import “chunks” while formatting statements (top-level Program and TSModuleBlock) by flushing/sorting the just-emitted IR tail.
Add buffer support for tail splicing (replace_end) and expose JoinNodesBuilder accessors needed by the streaming sorter.
Refactor SortImportsTransform to operate on &[FormatElement] slices (chunk-based) instead of a full Document.

Reviewed changes

Copilot reviewed 7 out of 7 changed files in this pull request and generated 2 comments.

Show a summary per file

File	Description
crates/oxc_formatter/src/print/program.rs	Introduces `FormatStatementsWithImports` to detect import runs and sort them during statement formatting.
crates/oxc_formatter/src/print/mod.rs	Uses `FormatStatementsWithImports` inside `TSModuleBlock` so ambient-module imports can be sorted.
crates/oxc_formatter/src/lib.rs	Removes the whole-document `SortImportsTransform` post-pass from `Formatter::format_with_external_callbacks`.
crates/oxc_formatter/src/ir_transform/sort_imports/mod.rs	Adds `sort_imports_chunk` and refactors transform to accept element slices.
crates/oxc_formatter/src/formatter/formatter.rs	Plumbs `replace_end` through `Formatter`’s `Buffer` implementation.
crates/oxc_formatter/src/formatter/builders.rs	Adds `fmt()` / `fmt_mut()` and `separator_no_entry` to support streaming chunk boundaries.
crates/oxc_formatter/src/formatter/buffer.rs	Extends `Buffer` with `replace_end` and implements it for `VecBuffer` (wrappers `unreachable!()`).

leaysgur

Impressive! Thank you~! (as always)

Looking back at the time when I implemented this as a completely extra step:

The work on the formatter itself was still being progressed by Dunqing, and I just wanted to avoid any conflicts at all
My own understanding of the formatter itself was also shallow

Now, I can say that this will not be a problem.

(I still support performing the sorting itself in the IR, though. The code related to comment placement is extremely complex, so I would prefer to leave them as is. 😓)

overlookmotel · 2026-05-03T20:42:59Z

Merge activity

May 3, 8:42 PM UTC: The merge label '0-merge' was detected. This PR will be added to the Graphite merge queue once it meets the requirements.
May 3, 8:43 PM UTC: overlookmotel added this pull request to the Graphite merge queue.
May 3, 8:48 PM UTC: Merged by the Graphite merge queue.

Import sorting operates on IR, rather than AST. Previous attempts to make it pre-sort the AST were abandoned primarily due to difficulties with re-ordering the comments attached to the `ImportDeclaration`s, because AST to IR conversion relies on comments being output in source order. This PR is a "middle way" approach. Import sorting still operates on IR, but happens during AST to IR conversion, rather than in a separate pass after IR for the whole file has been generated. The main advantages of this approach: - The sorting transform only has to deal with small sections of IR which contain only import statements (and comments and line breaks surrounding them), rather than searching through the IR for the entire file. - Now when transform runs on a chunk of IR, it's at the end of the buffer, so replacing the unsorted `FormatElement`s with the newly sorted ones is only a matter of popping the old ones off end of the buffer, and pushing the new ones on. This is much faster than copying the entire IR into a new buffer, which is what we had to do previously in order to shuffle up/down all the following `FormatElements`. The main disadvantage is that we lose the simplicity and "stand alone" nature of the separate sorting pass. But IMO the perf improvement is probably a good trade off. In this PR, I've prioritized altering the core sorting logic as little as possible, so that it's easier to review and verify that this change does not alter behavior. The structure of the code is therefore a bit odd (e.g. `SortImportsTransform` struct would better be replaced by just a free function now), and there's other refactoring and further perf improvements that we can make, but I've left them to follow-ups.

# Oxlint ### 🚀 Features - 1d40d60 linter: Implement SARIF formatter (#22067) (camchenry) - c0982fe linter/eslint: Implement no-restricted-properties rule (#22080) (AJ Bienz) - 5699d53 linter: Add help text to `agent` formatter (#22064) (camchenry) - fe7194d oxlint: Add agent output mode (#21955) (Jovi De Croock) - fb2f052 linter: Suggest moving shared branch code (#22022) (camc314) - 5868335 linter/no-else-return: Improve nested if diagnostic spans (#22009) (camc314) - 8b4829b linter: Split `no-negated-condition` rule to unicorn & eslint (#21998) (Sysix) - fea301a linter: Split jest/prefer-to-be into separate vitest rule (#21977) (camchenry) - 44aa0d6 linter: Split jest/prefer-strict-equal into separate vitest rule (#21976) (camchenry) - 2262b27 linter: Split jest/prefer-spy-on into separate vitest rule (#21975) (camchenry) - fef9143 linter: Split jest/prefer-mock-return-shorthand into separate vitest rule (#21974) (camchenry) - 2bda504 linter: Split jest/prefer-mock-promise-shorthand into separate vitest rule (#21973) (camchenry) - 6ef6c7d linter: Split jest/prefer-lowercase into separate vitest rule (#21972) (camchenry) - f4d2498 linter: Split jest/prefer-hooks-on-top into separate vitest rule (#21971) (camchenry) - fb8e366 linter: Split jest/prefer-hooks-in-order into separate vitest rule (#21970) (camchenry) - adcd85c linter: Split jest/prefer-expect-resolves into separate vitest rule (#21969) (camchenry) - 8ddc7ec linter: Split jest/prefer-equality-matcher into separate vitest rule (#21968) (camchenry) - 46bb1f3 linter: Split jest/prefer-each into separate vitest rule (#21967) (camchenry) - bdbff66 linter: Implement interactive-supports-focus (#21767) (mehm8128) - 733b094 linter: Split `prefer-to-have-been-called-times` rule (#21898) (Said Atrahouch) - 8804425 linter/eslint: Implement `logical-assignment-operators` rule (#21900) (Mikhail Baev) - 296d147 linter: Split jest/prefer-comparison-matcher into separate vitest rule (#21929) (camchenry) - 38146b6 linter: Split jest/prefer-called-with into separate vitest rule (#21927) (camchenry) - 6f86175 linter/vue: Implement return-in-computed-property rule (#21909) (bab) - dc2d0e4 linter: Split jest/no-unneeded-async-expect-function into separate vitest rule (#21878) (camchenry) - a03fc37 linter: Split jest/no-test-return-statement into separate vitest rule (#21877) (camchenry) - f11313e linter: Split jest/no-test-prefixes into separate vitest rule (#21876) (camchenry) - 4380812 linter: Split `prefer-to-have-length` rule (#21893) (Said Atrahouch) - 511bcc1 linter: Split jest `require-hook` rule (#21889) (Said Atrahouch) - 64a8180 linter: Split `jest/prefer-snapshot-hint` into a Jest rule and a Vitest rule. (#21881) (connorshea) - ae7924a linter/vue: Implement no-deprecated-model-definition rule (#21886) (bab) - 0dfe8b3 linter: Split `jest/require-to-throw-message` into Jest and Vitest rules. (#21879) (connorshea) - 51229ff linter: Split jest `valid-describe-callback` rule (#21882) (Said Atrahouch) - 2d102fd linter: Split `no-standalone-expect` rule into jest and vitest (#21862) (Sysix) - ee46a29 linter: Split `no-restricted-matchers` rule into jest and vitest (#21860) (Sysix) - 1f29459 linter: Split `no-restricted-jest-methods` rule into jest and vitest (#21859) (Sysix) - e7f8d55 linter: Remove eslint prefixes from plugin names in diagnostics (#21806) (Connor Shea) - 89fff8b linter: Split valid-expect-in-promise/jest rule into jest and vitest rules (#21854) (Said Atrahouch) ### 🐛 Bug Fixes - 0b48848 linter/prefer-array-some: Make find rewrite a suggestion (#22103) (camc314) - d24027e linter/prefer-array-some: Preserve find comparison fixes (#22094) (camc314) - af2d26c linter/astro: Handle js `---` after frontmatter in .astro files (#22091) (Andrew Powell) - 78d4ff0 linter/jsdoc/require-returns: Only look at the nearest jsdoc block (#22077) (camc314) - fa88857 linter/no-map-spread: Use default codegen options for fix (#22074) (camc314) - 2047a35 linter: Treat adjacent fixes as overlapping (#22071) (camc314) - 75fc551 linter: Handle no-extra-boolean-cast edge cases (#22031) (camc314) - e9d5284 linter/sort-keys: Don't autofix if comment could be misplaced (#22052) (Amund Eggen Svandal) - d7230b0 linter/no-constant-condition: Handle generator yields (#22046) (camc314) - e8dbc56 linter/array-type: Enable edge case tests (#22047) (camc314) - d57b51f linter/no-constant-condition: Propagate config errors (#22045) (camc314) - bdb6d95 linter/typescript: Remove duplicate rule tests (#22044) (camc314) - 0beaffc linter: Print resolved extended config (#22040) (camc314) - 192ad0e linter/react/only-export-components: Align rule with upstream cases (#22039) (camc314) - cdf4c53 linter/only-export-components: Support tanstack router (#21937) (camc314) - 893e18f linter: Stop gitignore lookup at repo boundary (#22033) (camc314) - 7100712 linter/constructor-super: Clarify duplicate super diagnostics (#22035) (camc314) - fce5b7c linter/constructor-super: Improve invalid `super` calls diagnostic (#22032) (camc314) - b3de93c linter/rules-of-hooks: Clarify conditional diagnostics (#22030) (camc314) - 4f9f629 linter/rules-of-hooks: Clarify loop diagnostics (#22029) (camc314) - e6f0978 linter/rules-of-hooks: Clarify async component diagnostics (#22024) (camc314) - e262f51 linter/rules-of-hooks: Improve diagnostic for hook inside class component (#22023) (camc314) - 7b71b0d linter/no-restricted-imports: Report once per import declaration (#22021) (camc314) - 3d5ae3d linter/vitest/require-mock-type-parameters: Handle chained typed mocks (#22019) (camc314) - 959a2db linter/reporter/github: Omit empty `file` annotations (#22017) (camc314) - 16003a1 linter/unicorn: Remove duplicate rule tests (#22018) (camc314) - 86b7547 linter/no-unreachable: Suppress nested unreachable diagnostics (#22011) (camc314) - 1d92ae8 linter/oxc: Remove duplicate rule tests (#22013) (camc314) - f270246 linter/branches-sharing-code: Ignore empty statements (#22012) (camc314) - f1c25dd linter: Stabilize debug diagnostic comparison (#22010) (camc314) - b6bc421 linter: Skip linting astro scripts with non JS script types (#21954) (camc314) - a77547d linter: Support plugin-qualified disable directives (#21999) (camc314) - 079cfdd linter: Match disable directive rule names exactly, not by substring (#21906) (Christian Vuerings) - 11a4e67 linter: Comptibles rules need to be disabled in jest and vitest at same time (#21982) (Said Atrahouch) - ce62f16 linter: `jsx-a11y/prefer-tag-over-role` detect more roles (#21933) (bab) - 024c390 linter/jest/vitest: Padding around after all blocks not working as expected (#21952) (kapobajza) - 05a8f75 linter/jest/no-standalone-expect: False positive with expect in an `ObjectProperty` (#21948) (Said Atrahouch) - 6a37c98 linter/no-unused-vars: Report unused re-exported imports (#21938) (camc314) - 2d5fc16 linter: `jsx-a11y/media-has-caption` report only once for self-closing tags (#21934) (bab) - 5adca29 linter: `jsx-a11y/no-autofocus` ignore `false` attribute values (#21918) (Sysix) - 2e5c18e linter/max-nested-describe: Reset nested describe depth (#21891) (camc314) ### ⚡ Performance - a77f0f7 linter/require-returns: Avoid jsdoc tag vec allocation (#22081) (camc314) - d9a1b32 linter/plugins: Avoid array lookups where possible in CFG visitor (#21940) (overlookmotel) - fefefd8 linter/plugins: Replace addition with bitwise OR in CFG visitor (#21939) (overlookmotel) ### 📚 Documentation - d58f594 oxlint/lsp: Auto generate docs for LSP options (#22082) (Sysix) - 9adc3b3 linter/no-misused-new: Clarify construct signatures behaviour (#22016) (camc314) - 1caf5ad linter/plugins: Reformat comments (#21873) (overlookmotel) # Oxfmt ### 🐛 Bug Fixes - ef0db6b formatter: Sequence expression in arrow function body collapses onto one line (#21183) (Justin Mecham) - 5d5d808 formatter: Preserve blank line after directive with trailing comment (#21153) (Justin Mecham) ### ⚡ Performance - 2fd907d formatter: Sort imports during IR construction (#22065) (overlookmotel) --------- Co-authored-by: Boshen <[email protected]> Co-authored-by: Cameron Clark <[email protected]>

…ot `Option<Vec>` (#22073) After #22065, the "return `None` if empty file" case can never fire, since it's only ever called with a segment of IR containing at least one `ImportDeclaration`. So remove the check, and make `transform` return `Vec<FormatElement>`, instead of `Option<Vec<FormatElement>>`.

Pure refactor. After #22065, `SortImportsTransform` serves no purpose. Convert its only method `transform` to a free function. No substantive changes - the PR purely makes that one change and removes a level of indentation. Only exception is fixing a typo in 1 comment ("fush" -> "flush").

Follow-on after #22065. Small perf optimization to collecting `ImportDeclaration`s for sorting. Previously, `FormatStatementsWithImports::fmt` had a loop where it checked each statement for whether it's an `ImportDeclaration`, and also checked every _other_ statement to see if it's the first statement _after_ an `ImportDeclaration`. `ImportDeclaration`s comprise a minority of the statements in a file. So instead have 2 nested loops: 1. Main loop over `Statement`s. 2. Inner loop which consumes a run of `ImportDeclaration`s, before yielding back to the main loop. This has the following effects: - Avoids the "am I the first statement after an `ImportDeclaration`?" check on all other statements. - Makes the flow more predictable for the branch predictor. - Moves processing a chunk of `ImportDeclaration`s into its own function, making the logic clearer. We could build on this new structure, if we chose, by: 1. Skipping sorting imports if there's only 1 import in a chunk. 2. Collecting info about imports (e.g. specifiers) at AST level, instead of the sorting transform having to figure it out by sifting through the IR. 3. Doing first-pass formatting of imports into a temporary buffer, so that sorted imports can be output directly into the main buffer, avoiding copying them all twice, which is what we do now (format into buffer, copy into temp `Vec`, copy back into buffer).

…#22201) This is no longer necessary, as the target IR now contains nothing but import statements by #22065.

overlookmotel marked this pull request as ready for review May 2, 2026 02:44

Copilot AI review requested due to automatic review settings May 2, 2026 02:44

overlookmotel requested review from Dunqing and leaysgur as code owners May 2, 2026 02:44

Copilot started reviewing on behalf of overlookmotel May 2, 2026 02:45 View session

overlookmotel assigned leaysgur May 2, 2026

Copilot AI reviewed May 2, 2026

View reviewed changes

Comment thread crates/oxc_formatter/src/ir_transform/sort_imports/mod.rs

Comment thread crates/oxc_formatter/src/print/mod.rs

overlookmotel force-pushed the om/05-02-perf_formatter_sort_imports_during_ir_construction branch from 0b781c3 to f581959 Compare May 2, 2026 02:54

overlookmotel changed the base branch from main to graphite-base/22065 May 2, 2026 10:43

overlookmotel force-pushed the om/05-02-perf_formatter_sort_imports_during_ir_construction branch from f581959 to 331ffe6 Compare May 2, 2026 10:43

overlookmotel changed the base branch from graphite-base/22065 to om/05-02-test_formatter_add_tests_for_import_sorting_in_ambient_modules May 2, 2026 10:43

overlookmotel mentioned this pull request May 2, 2026

test(formatter): add tests for import sorting in ambient modules #22072

Merged

overlookmotel added C-performance Category - Solution not expected to change functional behavior, only performance A-formatter Area - Formatter labels May 2, 2026

This was referenced May 2, 2026

refactor(formatter): SortImportsTransform::transform return Vec not Option<Vec> #22073

Merged

refactor(formatter): remove SortImportsTransform abstraction #22075

Merged

perf(formatter): process ImportDeclarations in a run #22079

Merged

overlookmotel force-pushed the om/05-02-test_formatter_add_tests_for_import_sorting_in_ambient_modules branch from 4705d36 to 484b615 Compare May 2, 2026 12:50

overlookmotel force-pushed the om/05-02-perf_formatter_sort_imports_during_ir_construction branch from 331ffe6 to c744bdd Compare May 2, 2026 12:50

leaysgur approved these changes May 3, 2026

View reviewed changes

overlookmotel added the 0-merge Merge with Graphite Merge Queue label May 3, 2026

graphite-app Bot force-pushed the om/05-02-test_formatter_add_tests_for_import_sorting_in_ambient_modules branch from 484b615 to 2c7a2ea Compare May 3, 2026 20:44

graphite-app Bot force-pushed the om/05-02-perf_formatter_sort_imports_during_ir_construction branch from c744bdd to 2fd907d Compare May 3, 2026 20:44

Base automatically changed from om/05-02-test_formatter_add_tests_for_import_sorting_in_ambient_modules to main May 3, 2026 20:47

graphite-app Bot removed the 0-merge Merge with Graphite Merge Queue label May 3, 2026

graphite-app Bot merged commit 2fd907d into main May 3, 2026
28 checks passed

graphite-app Bot deleted the om/05-02-perf_formatter_sort_imports_during_ir_construction branch May 3, 2026 20:48

oxc-guard Bot mentioned this pull request May 4, 2026

release(apps): oxlint v1.63.0 && oxfmt v0.48.0 #22109

Merged

graphite-app Bot pushed a commit that referenced this pull request May 7, 2026

refactor(formatter/sort_imports): Remove SourceLine::Others variant (…

01f7836

…#22201) This is no longer necessary, as the target IR now contains nothing but import statements by #22065.

leaysgur mentioned this pull request May 7, 2026

refactor(formatter/sort_imports): Remove SourceLine::Others variant #22201

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

perf(formatter): sort imports during IR construction#22065

perf(formatter): sort imports during IR construction#22065
graphite-app[bot] merged 1 commit into
mainfrom
om/05-02-perf_formatter_sort_imports_during_ir_construction

overlookmotel commented May 2, 2026 •

edited

Loading

Uh oh!

overlookmotel commented May 2, 2026 •

edited

Loading

Uh oh!

codspeed-hq Bot commented May 2, 2026 •

edited

Loading

Uh oh!

Copilot AI left a comment

Uh oh!

Uh oh!

Uh oh!

leaysgur left a comment

Uh oh!

overlookmotel commented May 3, 2026 •

edited by graphite-app Bot

Loading

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Uh oh!

Uh oh!

Conversation

overlookmotel commented May 2, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

overlookmotel commented May 2, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

How to use the Graphite Merge Queue

Uh oh!

codspeed-hq Bot commented May 2, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Merging this PR will improve performance by 24.9%

Performance Changes

Footnotes

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Reviewed changes

Uh oh!

Uh oh!

Uh oh!

leaysgur left a comment

Choose a reason for hiding this comment

Uh oh!

overlookmotel commented May 3, 2026 • edited by graphite-app Bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Merge activity

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

overlookmotel commented May 2, 2026 •

edited

Loading

overlookmotel commented May 2, 2026 •

edited

Loading

codspeed-hq Bot commented May 2, 2026 •

edited

Loading

overlookmotel commented May 3, 2026 •

edited by graphite-app Bot

Loading