From e5bd6313f034b682a83e7372af2c6d78f2608524 Mon Sep 17 00:00:00 2001 From: "Arend van Beelen jr." Date: Fri, 11 Jul 2025 23:33:21 +0200 Subject: [PATCH] perf: optimise noImportCycles --- .changeset/cyclic-checks-charge.md | 5 ++ Cargo.lock | 1 + .../src/lint/nursery/no_import_cycles.rs | 27 ++++------ crates/biome_module_graph/Cargo.toml | 1 + .../biome_module_graph/src/js_module_info.rs | 47 +++++++++-------- .../src/js_module_info/collector.rs | 19 +++---- ...const_type_declaration_with_namespace.snap | 6 +-- .../snapshots/test_resolve_export_types.snap | 6 +-- .../tests/snapshots/test_resolve_exports.snap | 30 +++++------ .../snapshots/test_resolve_merged_types.snap | 12 ++--- .../test_resolve_multiple_reexports.snap | 6 +-- ...esolve_recursive_looking_country_info.snap | 8 +-- .../test_resolve_recursive_looking_vfile.snap | 50 +++++++++---------- crates/biome_module_graph/tests/spec_tests.rs | 4 +- 14 files changed, 114 insertions(+), 108 deletions(-) create mode 100644 .changeset/cyclic-checks-charge.md diff --git a/.changeset/cyclic-checks-charge.md b/.changeset/cyclic-checks-charge.md new file mode 100644 index 000000000000..fccebf9eb8ae --- /dev/null +++ b/.changeset/cyclic-checks-charge.md @@ -0,0 +1,5 @@ +--- +"@biomejs/biome": patch +--- + +Improved the performance of `noImportCycles` by ~30%. diff --git a/Cargo.lock b/Cargo.lock index 70177347bb3e..ddf333f91e0e 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -1267,6 +1267,7 @@ dependencies = [ "camino", "cfg-if", "codspeed-criterion-compat", + "indexmap", "insta", "mimalloc", "once_cell", diff --git a/crates/biome_js_analyze/src/lint/nursery/no_import_cycles.rs b/crates/biome_js_analyze/src/lint/nursery/no_import_cycles.rs index 802d54f5c88f..7a19f160386b 100644 --- a/crates/biome_js_analyze/src/lint/nursery/no_import_cycles.rs +++ b/crates/biome_js_analyze/src/lint/nursery/no_import_cycles.rs @@ -1,5 +1,3 @@ -use std::collections::HashSet; - use biome_analyze::{ Rule, RuleDiagnostic, RuleDomain, RuleSource, context::RuleContext, declare_lint_rule, }; @@ -10,6 +8,7 @@ use biome_module_graph::{JsModuleInfo, ResolvedPath}; use biome_rowan::AstNode; use biome_rule_options::no_import_cycles::NoImportCyclesOptions; use camino::{Utf8Path, Utf8PathBuf}; +use rustc_hash::FxHashSet; use crate::services::module_graph::ResolvedImports; @@ -166,36 +165,32 @@ fn find_cycle( start_path: &Utf8Path, mut module_info: JsModuleInfo, ) -> Option]>> { - let mut seen = HashSet::new(); + let mut seen = FxHashSet::default(); let mut stack: Vec<(Box, JsModuleInfo)> = Vec::new(); 'outer: loop { for resolved_path in module_info.all_import_paths() { - let Some(resolved_path) = resolved_path.as_path() else { + let Some(path) = resolved_path.as_path() else { continue; }; - if resolved_path == ctx.file_path() { + if !seen.insert(resolved_path.clone()) { + continue; + } + + if path == ctx.file_path() { // Return all the paths from `start_path` to `resolved_path`: let paths = Some(start_path.as_str()) .into_iter() .map(Box::from) .chain(stack.into_iter().map(|(path, _)| path)) - .chain(Some(Box::from(resolved_path.as_str()))) + .chain(Some(Box::from(path.as_str()))) .collect(); return Some(paths); } - // FIXME: Use `get_or_insert_with()` once it's stabilized. - // See: https://github.com/rust-lang/rust/issues/60896 - if seen.contains(resolved_path.as_str()) { - continue; - } - - seen.insert(resolved_path.to_string()); - - if let Some(next_module_info) = ctx.module_info_for_path(resolved_path) { - stack.push((resolved_path.as_str().into(), module_info)); + if let Some(next_module_info) = ctx.module_info_for_path(path) { + stack.push((path.as_str().into(), module_info)); module_info = next_module_info; continue 'outer; } diff --git a/crates/biome_module_graph/Cargo.toml b/crates/biome_module_graph/Cargo.toml index afd2e3acc770..09dca3d7189a 100644 --- a/crates/biome_module_graph/Cargo.toml +++ b/crates/biome_module_graph/Cargo.toml @@ -26,6 +26,7 @@ biome_resolver = { workspace = true } biome_rowan = { workspace = true } camino = { workspace = true } cfg-if = { workspace = true } +indexmap = { workspace = true } once_cell = "1.21.3" # Use `std::sync::OnceLock::get_or_try_init` when it is stable. papaya = { workspace = true } rust-lapper = { workspace = true } diff --git a/crates/biome_module_graph/src/js_module_info.rs b/crates/biome_module_graph/src/js_module_info.rs index 3552c8b3b2a5..b95c714d3380 100644 --- a/crates/biome_module_graph/src/js_module_info.rs +++ b/crates/biome_module_graph/src/js_module_info.rs @@ -4,13 +4,14 @@ mod module_resolver; mod scope; mod visitor; -use std::{collections::BTreeMap, ops::Deref, sync::Arc}; +use std::{ops::Deref, sync::Arc}; use biome_js_syntax::AnyJsImportLike; use biome_js_type_info::{BindingId, ImportSymbol, ResolvedTypeId, ScopeId, TypeData}; use biome_jsdoc_comment::JsdocComment; use biome_resolver::ResolvedPath; use biome_rowan::{Text, TextRange}; +use indexmap::IndexMap; use rust_lapper::Lapper; use rustc_hash::FxHashMap; @@ -38,10 +39,9 @@ impl JsModuleInfo { /// Returns an iterator over all the static and dynamic imports in this /// module. pub fn all_import_paths(&self) -> impl Iterator + use<> { - let module_info = self.0.as_ref(); ImportPathIterator { - static_import_paths: module_info.static_import_paths.clone(), - dynamic_import_paths: module_info.dynamic_import_paths.clone(), + module_info: self.clone(), + index: 0, } } @@ -105,7 +105,7 @@ pub struct JsModuleInfoInner { /// absolute path it resolves to. The resolved path may be looked up as key /// in the [ModuleGraph::data] map, although it is not required to exist /// (for instance, if the path is outside the project's scope). - pub static_import_paths: BTreeMap, + pub static_import_paths: IndexMap, /// Map of all dynamic import paths found in the module for which the import /// specifier could be statically determined. @@ -121,7 +121,7 @@ pub struct JsModuleInfoInner { /// /// Paths found in `require()` expressions in CommonJS sources are also /// included with the dynamic import paths. - pub dynamic_import_paths: BTreeMap, + pub dynamic_import_paths: IndexMap, /// Map of exports from the module. /// @@ -156,10 +156,10 @@ pub struct JsModuleInfoInner { } #[derive(Debug, Default)] -pub struct Exports(pub(crate) BTreeMap); +pub struct Exports(pub(crate) IndexMap); impl Deref for Exports { - type Target = BTreeMap; + type Target = IndexMap; fn deref(&self) -> &Self::Target { &self.0 @@ -167,10 +167,11 @@ impl Deref for Exports { } #[derive(Debug, Default)] -pub struct Imports(pub(crate) BTreeMap); +pub struct Imports(pub(crate) IndexMap); impl Deref for Imports { - type Target = BTreeMap; + type Target = IndexMap; + fn deref(&self) -> &Self::Target { &self.0 } @@ -307,23 +308,29 @@ pub struct JsReexport { } struct ImportPathIterator { - static_import_paths: BTreeMap, - dynamic_import_paths: BTreeMap, + module_info: JsModuleInfo, + index: usize, } impl Iterator for ImportPathIterator { type Item = ResolvedPath; fn next(&mut self) -> Option { - if self.static_import_paths.is_empty() { - self.dynamic_import_paths - .pop_first() - .map(|(_source, path)| path) + let num_static_imports = self.module_info.static_import_paths.len(); + let resolved_path = if self.index < num_static_imports { + let resolved_path = &self.module_info.static_import_paths[self.index]; + self.index += 1; + resolved_path + } else if self.index < self.module_info.dynamic_import_paths.len() + num_static_imports { + let resolved_path = + &self.module_info.dynamic_import_paths[self.index - num_static_imports]; + self.index += 1; + resolved_path } else { - self.static_import_paths - .pop_first() - .map(|(_identifier, path)| path) - } + return None; + }; + + Some(resolved_path.clone()) } } diff --git a/crates/biome_module_graph/src/js_module_info/collector.rs b/crates/biome_module_graph/src/js_module_info/collector.rs index 82964cc8fef6..78a7611e9b0c 100644 --- a/crates/biome_module_graph/src/js_module_info/collector.rs +++ b/crates/biome_module_graph/src/js_module_info/collector.rs @@ -1,8 +1,4 @@ -use std::{ - borrow::Cow, - collections::{BTreeMap, BTreeSet}, - sync::Arc, -}; +use std::{borrow::Cow, collections::BTreeSet, sync::Arc}; use biome_js_semantic::{SemanticEvent, SemanticEventExtractor}; use biome_js_syntax::{ @@ -19,6 +15,7 @@ use biome_js_type_info::{ }; use biome_jsdoc_comment::JsdocComment; use biome_rowan::{AstNode, Text, TextRange, TextSize, TokenText}; +use indexmap::IndexMap; use rust_lapper::{Interval, Lapper}; use rustc_hash::FxHashMap; @@ -77,11 +74,11 @@ pub(super) struct JsModuleInfoCollector { /// Map with all static import paths, from the source specifier to the /// resolved path. - static_import_paths: BTreeMap, + static_import_paths: IndexMap, /// Map with all dynamic import paths, from the import source to the /// resolved path. - dynamic_import_paths: BTreeMap, + dynamic_import_paths: IndexMap, /// All collected exports. /// @@ -96,7 +93,7 @@ pub(super) struct JsModuleInfoCollector { types: TypeStore, /// Static imports mapped from the local name of the binding being imported. - static_imports: BTreeMap, + static_imports: IndexMap, } /// Intermediary representation for an exported symbol. @@ -519,7 +516,7 @@ impl JsModuleInfoCollector { } } - fn finalise(&mut self) -> (BTreeMap, Lapper) { + fn finalise(&mut self) -> (IndexMap, Lapper) { let scope_by_range = Lapper::new( self.scope_range_by_start .iter() @@ -767,8 +764,8 @@ impl JsModuleInfoCollector { } } - fn collect_exports(&mut self) -> BTreeMap { - let mut finalised_exports = BTreeMap::new(); + fn collect_exports(&mut self) -> IndexMap { + let mut finalised_exports = IndexMap::new(); let exports = std::mem::take(&mut self.exports); for export in exports { diff --git a/crates/biome_module_graph/tests/snapshots/test_export_const_type_declaration_with_namespace.snap b/crates/biome_module_graph/tests/snapshots/test_export_const_type_declaration_with_namespace.snap index f788460b4a78..d7c7bc8f74bb 100644 --- a/crates/biome_module_graph/tests/snapshots/test_export_const_type_declaration_with_namespace.snap +++ b/crates/biome_module_graph/tests/snapshots/test_export_const_type_declaration_with_namespace.snap @@ -22,12 +22,12 @@ export = shared; ``` Exports { - "default" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(3)) - } "foo" => { ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(1)) } + "default" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(3)) + } } Imports { No imports diff --git a/crates/biome_module_graph/tests/snapshots/test_resolve_export_types.snap b/crates/biome_module_graph/tests/snapshots/test_resolve_export_types.snap index a69255fb2754..fb33b175b956 100644 --- a/crates/biome_module_graph/tests/snapshots/test_resolve_export_types.snap +++ b/crates/biome_module_graph/tests/snapshots/test_resolve_export_types.snap @@ -42,12 +42,12 @@ export const superComputer = new DeepThought(); ``` Exports { - "superComputer" => { - ExportOwnExport => JsOwnExport::Binding(3) - } "theAnswer" => { ExportOwnExport => JsOwnExport::Binding(0) } + "superComputer" => { + ExportOwnExport => JsOwnExport::Binding(3) + } } Imports { No imports diff --git a/crates/biome_module_graph/tests/snapshots/test_resolve_exports.snap b/crates/biome_module_graph/tests/snapshots/test_resolve_exports.snap index 370a37ed63b0..6c955d4b3b53 100644 --- a/crates/biome_module_graph/tests/snapshots/test_resolve_exports.snap +++ b/crates/biome_module_graph/tests/snapshots/test_resolve_exports.snap @@ -60,29 +60,35 @@ export * as renamed2 from "./renamed-reexports"; ``` Exports { - "a" => { - ExportOwnExport => JsOwnExport::Binding(5) + "foo" => { + ExportOwnExport => JsOwnExport::Binding(0) } - "b" => { - ExportOwnExport => JsOwnExport::Binding(6) + "qux" => { + ExportOwnExport => JsOwnExport::Binding(4) } "bar" => { ExportOwnExport => JsOwnExport::Binding(1) } + "quz" => { + ExportOwnExport => JsOwnExport::Binding(2) + } "baz" => { ExportOwnExport => JsOwnExport::Binding(3) } + "a" => { + ExportOwnExport => JsOwnExport::Binding(5) + } + "b" => { + ExportOwnExport => JsOwnExport::Binding(6) + } "d" => { ExportOwnExport => JsOwnExport::Binding(7) } - "default" => { - ExportOwnExport => JsOwnExport::Binding(11) - } "e" => { ExportOwnExport => JsOwnExport::Binding(8) } - "foo" => { - ExportOwnExport => JsOwnExport::Binding(0) + "default" => { + ExportOwnExport => JsOwnExport::Binding(11) } "oh\nno" => { ExportReexport => Reexport( @@ -91,12 +97,6 @@ Exports { Import Symbol: ohNo ) } - "qux" => { - ExportOwnExport => JsOwnExport::Binding(4) - } - "quz" => { - ExportOwnExport => JsOwnExport::Binding(2) - } "renamed2" => { ExportReexport => Reexport( Specifier: "./renamed-reexports" diff --git a/crates/biome_module_graph/tests/snapshots/test_resolve_merged_types.snap b/crates/biome_module_graph/tests/snapshots/test_resolve_merged_types.snap index b5dafe59381f..c6f3cb642e11 100644 --- a/crates/biome_module_graph/tests/snapshots/test_resolve_merged_types.snap +++ b/crates/biome_module_graph/tests/snapshots/test_resolve_merged_types.snap @@ -25,18 +25,18 @@ export { A, B }; ``` Exports { - "A" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(2)) - } - "B" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(10)) - } "Union" => { ExportOwnExport => JsOwnExport::Binding(3) } "Union2" => { ExportOwnExport => JsOwnExport::Binding(7) } + "A" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(2)) + } + "B" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(10)) + } } Imports { No imports diff --git a/crates/biome_module_graph/tests/snapshots/test_resolve_multiple_reexports.snap b/crates/biome_module_graph/tests/snapshots/test_resolve_multiple_reexports.snap index ce4f05743432..9caf6ec9f8eb 100644 --- a/crates/biome_module_graph/tests/snapshots/test_resolve_multiple_reexports.snap +++ b/crates/biome_module_graph/tests/snapshots/test_resolve_multiple_reexports.snap @@ -2,7 +2,7 @@ source: crates/biome_module_graph/tests/snap/mod.rs expression: content --- -# `/src/bar.ts` (Module 2) +# `/src/bar.ts` (Module 3) ## Source @@ -95,7 +95,7 @@ Module TypeId(3) => Module(0) TypeId(2).bar Module TypeId(4) => Call Module(0) TypeId(3)(No parameters) ``` -# `/src/foo.ts` (Module 3) +# `/src/foo.ts` (Module 2) ## Source @@ -174,7 +174,7 @@ Full TypeId(1) => namespace for ModuleId(2) Full TypeId(2) => namespace for ModuleId(3) -Full TypeId(3) => Module(3) TypeId(1) +Full TypeId(3) => Module(2) TypeId(1) Full TypeId(4) => number diff --git a/crates/biome_module_graph/tests/snapshots/test_resolve_recursive_looking_country_info.snap b/crates/biome_module_graph/tests/snapshots/test_resolve_recursive_looking_country_info.snap index b26ac5d65504..7a1588952420 100644 --- a/crates/biome_module_graph/tests/snapshots/test_resolve_recursive_looking_country_info.snap +++ b/crates/biome_module_graph/tests/snapshots/test_resolve_recursive_looking_country_info.snap @@ -72,8 +72,8 @@ Exports { "SubdivisionInfo" => { ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(14)) } - "codes" => { - ExportOwnExport => JsOwnExport::Binding(18) + "subdivision" => { + ExportOwnExport => JsOwnExport::Binding(12) } "country" => { ExportOwnExport => JsOwnExport::Binding(15) @@ -81,8 +81,8 @@ Exports { "data" => { ExportOwnExport => JsOwnExport::Binding(17) } - "subdivision" => { - ExportOwnExport => JsOwnExport::Binding(12) + "codes" => { + ExportOwnExport => JsOwnExport::Binding(18) } } Imports { diff --git a/crates/biome_module_graph/tests/snapshots/test_resolve_recursive_looking_vfile.snap b/crates/biome_module_graph/tests/snapshots/test_resolve_recursive_looking_vfile.snap index a98d66b33482..46c80306afe0 100644 --- a/crates/biome_module_graph/tests/snapshots/test_resolve_recursive_looking_vfile.snap +++ b/crates/biome_module_graph/tests/snapshots/test_resolve_recursive_looking_vfile.snap @@ -174,50 +174,50 @@ export = vfile; ``` Exports { - "basename" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(26)) + "history" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(49)) + } + "data" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(34)) + } + "messages" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(35)) } "contents" => { ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(44)) } - "cwd" => { - ExportOwnExport => JsOwnExport::Type(string) + "path" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(26)) } - "data" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(34)) + "dirname" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(26)) } - "default" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(6)) + "basename" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(26)) } - "dirname" => { + "stem" => { ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(26)) } "extname" => { ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(26)) } - "fail" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(40)) - } - "history" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(49)) + "cwd" => { + ExportOwnExport => JsOwnExport::Type(string) } - "info" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(38)) + "toString" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(36)) } "message" => { ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(38)) } - "messages" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(35)) - } - "path" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(26)) + "fail" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(40)) } - "stem" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(26)) + "info" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(38)) } - "toString" => { - ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(36)) + "default" => { + ExportOwnExport => JsOwnExport::Type(Module(0) TypeId(6)) } } Imports { diff --git a/crates/biome_module_graph/tests/spec_tests.rs b/crates/biome_module_graph/tests/spec_tests.rs index 32a6179fb892..8a576fb94208 100644 --- a/crates/biome_module_graph/tests/spec_tests.rs +++ b/crates/biome_module_graph/tests/spec_tests.rs @@ -454,7 +454,7 @@ fn test_resolve_exports() { // Remove this entry, or the Windows tests fail on the path in the snapshot below: assert_eq!( - exports.remove(&Text::Static("oh\nno")), + exports.swap_remove(&Text::Static("oh\nno")), Some(JsExport::Reexport(JsReexport { import: JsImport { specifier: "./renamed-reexports".into(), @@ -465,7 +465,7 @@ fn test_resolve_exports() { })) ); assert_eq!( - exports.remove(&Text::Static("renamed2")), + exports.swap_remove(&Text::Static("renamed2")), Some(JsExport::Reexport(JsReexport { import: JsImport { specifier: "./renamed-reexports".into(),