Repository: rust-lang/rust-analyzer
Pull request #17457 (2024-06-19 15:31:57)

fix: ensure there are no cycles in the source_root_parent_map
See #17409

We can view the connections between roots as a graph. The problem is that this graph may contain cycles, so when adding edges, it is necessary to check whether it will lead to a cycle.

Since we ensure that each node has at most one outgoing edge (because each SourceRoot can have only one parent), we can use a disjoint-set to maintain the connectivity between nodes. If an edge’s two nodes belong to the same set, they are already connected.

Additionally, this PR includes the following three changes:

1. Removed the workaround from #17409.
2. Added an optimization: If `map.contains_key(&SourceRootId(*root_id as u32))`, we can skip the current loop iteration since we have already found its parent.
3. Modified the inner loop to iterate in reverse order with `roots[..idx].iter().rev()` at line 319. This ensures that if we are looking for the parent of `a/b/c`, and both `a` and `a/b` meet the criteria, we will choose the longer match (`a/b`).


Patch:
diff --git a/crates/ide-completion/src/completions/item_list.rs b/crates/ide-completion/src/completions/item_list.rs
index 02298b1e9b..44c6199def 100644
--- a/crates/ide-completion/src/completions/item_list.rs
+++ b/crates/ide-completion/src/completions/item_list.rs
@@ -100,7 +100,6 @@ fn add_keywords(acc: &mut Completions, ctx: &CompletionContext<'_>, kind: Option
             add_keyword("enum", "enum $1 {\n    $0\n}");
             add_keyword("mod", "mod $0");
             add_keyword("static", "static $0");
-            add_keyword("async", "async $0");
             add_keyword("struct", "struct $0");
             add_keyword("trait", "trait $1 {\n    $0\n}");
             add_keyword("union", "union $1 {\n    $0\n}");
diff --git a/crates/load-cargo/src/lib.rs b/crates/load-cargo/src/lib.rs
index cb785195a0..de68b86714 100644
--- a/crates/load-cargo/src/lib.rs
+++ b/crates/load-cargo/src/lib.rs
@@ -285,28 +285,54 @@ impl SourceRootConfig {
     /// If a `SourceRoot` doesn't have a parent and is local then it is not contained in this mapping but it can be asserted that it is a root `SourceRoot`.
     pub fn source_root_parent_map(&self) -> FxHashMap<SourceRootId, SourceRootId> {
         let roots = self.fsc.roots();
-        roots
-            .iter()
-            .enumerate()
-            .filter(|(_, (_, id))| self.local_filesets.contains(id))
-            .filter_map(|(idx, (root, root_id))| {
-                // We are interested in parents if they are also local source roots.
-                // So instead of a non-local parent we may take a local ancestor as a parent to a node.
-                //
-                // Here paths in roots are sorted lexicographically, so if a root
-                // is a parent of another root, it will be before it in the list.
-                roots[..idx].iter().find_map(|(root2, root2_id)| {
-                    if self.local_filesets.contains(root2_id)
-                        && root.starts_with(root2)
-                        && root_id != root2_id
-                    {
-                        return Some((root_id, root2_id));
+
+        let mut map = FxHashMap::default();
+
+        // See https://github.com/rust-lang/rust-analyzer/issues/17409
+        //
+        // We can view the connections between roots as a graph. The problem is
+        // that this graph may contain cycles, so when adding edges, it is necessary
+        // to check whether it will lead to a cycle.
+        //
+        // Since we ensure that each node has at most one outgoing edge (because
+        // each SourceRoot can have only one parent), we can use a disjoint-set to
+        // maintain the connectivity between nodes. If an edge’s two nodes belong
+        // to the same set, they are already connected.
+        let mut dsu = FxHashMap::default();
+        fn find_parent(dsu: &mut FxHashMap<u64, u64>, id: u64) -> u64 {
+            if let Some(&parent) = dsu.get(&id) {
+                let parent = find_parent(dsu, parent);
+                dsu.insert(id, parent);
+                parent
+            } else {
+                id
+            }
+        }
+
+        for (idx, (root, root_id)) in roots.iter().enumerate() {
+            if !self.local_filesets.contains(root_id)
+                || map.contains_key(&SourceRootId(*root_id as u32))
+            {
+                continue;
+            }
+
+            for (root2, root2_id) in roots[..idx].iter().rev() {
+                if self.local_filesets.contains(root2_id)
+                    && root_id != root2_id
+                    && root.starts_with(root2)
+                {
+                    // check if the edge will create a cycle
+                    if find_parent(&mut dsu, *root_id) != find_parent(&mut dsu, *root2_id) {
+                        map.insert(SourceRootId(*root_id as u32), SourceRootId(*root2_id as u32));
+                        dsu.insert(*root_id, *root2_id);
                     }
-                    None
-                })
-            })
-            .map(|(&child, &parent)| (SourceRootId(child as u32), SourceRootId(parent as u32)))
-            .collect()
+
+                    break;
+                }
+            }
+        }
+
+        map
     }
 }
 
@@ -592,4 +618,20 @@ mod tests {
 
         assert_eq!(vc, vec![(SourceRootId(1), SourceRootId(0)),])
     }
+
+    #[test]
+    fn circular_reference() {
+        let mut builder = FileSetConfigBuilder::default();
+        builder.add_file_set(vec![
+            VfsPath::new_virtual_path("/ROOT/def".to_owned()),
+            VfsPath::new_virtual_path("/ROOT/def/abc/def".to_owned()),
+        ]);
+        builder.add_file_set(vec![VfsPath::new_virtual_path("/ROOT/def/abc".to_owned())]);
+        let fsc = builder.build();
+        let src = SourceRootConfig { fsc, local_filesets: vec![0, 1] };
+        let mut vc = src.source_root_parent_map().into_iter().collect::<Vec<_>>();
+        vc.sort_by(|x, y| x.0 .0.cmp(&y.0 .0));
+
+        assert_eq!(vc, vec![(SourceRootId(1), SourceRootId(0)),])
+    }
 }
diff --git a/crates/rust-analyzer/src/config.rs b/crates/rust-analyzer/src/config.rs
index ef890fa3e6..e8504979be 100644
--- a/crates/rust-analyzer/src/config.rs
+++ b/crates/rust-analyzer/src/config.rs
@@ -2531,7 +2531,6 @@ macro_rules! _impl_for_config_data {
                 #[allow(non_snake_case)]
                 $vis fn $field(&self, source_root: Option<SourceRootId>) -> &$ty {
                     let mut par: Option<SourceRootId> = source_root;
-                    let mut traversals = 0;
                     while let Some(source_root_id) = par {
                         par = self.source_root_parent_map.get(&source_root_id).copied();
                         if let Some((config, _)) = self.ratoml_files.get(&source_root_id) {
@@ -2539,14 +2538,6 @@ macro_rules! _impl_for_config_data {
                                 return value;
                             }
                         }
-                        // Prevent infinite loops caused by cycles by giving up when it's
-                        // clear that we must have either visited all source roots or
-                        // encountered a cycle.
-                        traversals += 1;
-                        if traversals >= self.source_root_parent_map.len() {
-                            // i.e. no source root contains the config we're looking for
-                            break;
-                        }
                     }
 
                     if let Some((root_path_ratoml, _)) = self.root_ratoml.as_ref() {


Test patch:
diff --git a/crates/ide-completion/src/tests/expression.rs b/crates/ide-completion/src/tests/expression.rs
index 545c2a2a8a..a653314233 100644
--- a/crates/ide-completion/src/tests/expression.rs
+++ b/crates/ide-completion/src/tests/expression.rs
@@ -141,7 +141,6 @@ impl Unit {
             un Union        Union
             ev TupleV(…)    TupleV(u32)
             bt u32          u32
-            kw async
             kw const
             kw crate::
             kw enum
@@ -218,7 +217,6 @@ fn complete_in_block() {
         expect![[r#"
             fn foo()       fn()
             bt u32         u32
-            kw async
             kw const
             kw crate::
             kw enum
@@ -266,7 +264,6 @@ fn complete_after_if_expr() {
         expect![[r#"
             fn foo()       fn()
             bt u32         u32
-            kw async
             kw const
             kw crate::
             kw else
@@ -339,7 +336,6 @@ fn completes_in_loop_ctx() {
         expect![[r#"
             fn my()        fn()
             bt u32         u32
-            kw async
             kw break
             kw const
             kw continue
@@ -803,7 +799,6 @@ fn foo() { if foo {} $0 }
         expect![[r#"
             fn foo()       fn()
             bt u32         u32
-            kw async
             kw const
             kw crate::
             kw else
@@ -844,7 +839,6 @@ fn foo() { if foo {} el$0 }
         expect![[r#"
             fn foo()       fn()
             bt u32         u32
-            kw async
             kw const
             kw crate::
             kw else
@@ -933,7 +927,6 @@ fn foo() { if foo {} $0 let x = 92; }
         expect![[r#"
             fn foo()       fn()
             bt u32         u32
-            kw async
             kw const
             kw crate::
             kw else
@@ -974,7 +967,6 @@ fn foo() { if foo {} el$0 let x = 92; }
         expect![[r#"
             fn foo()       fn()
             bt u32         u32
-            kw async
             kw const
             kw crate::
             kw else
@@ -1015,7 +1007,6 @@ fn foo() { if foo {} el$0 { let x = 92; } }
         expect![[r#"
             fn foo()       fn()
             bt u32         u32
-            kw async
             kw const
             kw crate::
             kw else
@@ -1068,7 +1059,6 @@ pub struct UnstableThisShouldNotBeListed;
             fn main()      fn()
             md std
             bt u32         u32
-            kw async
             kw const
             kw crate::
             kw enum
@@ -1121,7 +1111,6 @@ pub struct UnstableButWeAreOnNightlyAnyway;
             md std
             st UnstableButWeAreOnNightlyAnyway UnstableButWeAreOnNightlyAnyway
             bt u32                    u32
-            kw async
             kw const
             kw crate::
             kw enum
diff --git a/crates/ide-completion/src/tests/item_list.rs b/crates/ide-completion/src/tests/item_list.rs
index c37900478e..2b5b4dd773 100644
--- a/crates/ide-completion/src/tests/item_list.rs
+++ b/crates/ide-completion/src/tests/item_list.rs
@@ -14,7 +14,6 @@ fn in_mod_item_list() {
         r#"mod tests { $0 }"#,
         expect![[r#"
             ma makro!(…)           macro_rules! makro
-            kw async
             kw const
             kw crate::
             kw enum
@@ -48,7 +47,6 @@ fn in_source_file_item_list() {
         expect![[r#"
             ma makro!(…)           macro_rules! makro
             md module
-            kw async
             kw const
             kw crate::
             kw enum
@@ -81,7 +79,6 @@ fn in_item_list_after_attr() {
         expect![[r#"
             ma makro!(…)           macro_rules! makro
             md module
-            kw async
             kw const
             kw crate::
             kw enum
@@ -135,7 +132,6 @@ fn after_visibility() {
     check(
         r#"pub $0"#,
         expect![[r#"
-            kw async
             kw const
             kw enum
             kw extern
@@ -360,7 +356,6 @@ fn after_unit_struct() {
         expect![[r#"
             ma makro!(…)           macro_rules! makro
             md module
-            kw async
             kw const
             kw crate::
             kw enum
diff --git a/crates/ide-completion/src/tests/special.rs b/crates/ide-completion/src/tests/special.rs
index 2ae7d37889..69d8fe9104 100644
--- a/crates/ide-completion/src/tests/special.rs
+++ b/crates/ide-completion/src/tests/special.rs
@@ -1017,7 +1017,6 @@ fn here_we_go() {
             fn here_we_go()    fn()
             st Foo (alias Bar) Foo
             bt u32             u32
-            kw async
             kw const
             kw crate::
             kw enum
@@ -1067,7 +1066,6 @@ fn here_we_go() {
             fn here_we_go()           fn()
             st Foo (alias Bar, Qux, Baz) Foo
             bt u32                    u32
-            kw async
             kw const
             kw crate::
             kw enum
@@ -1190,7 +1188,6 @@ fn bar() { qu$0 }
             fn bar()             fn()
             fn foo() (alias qux) fn()
             bt u32               u32
-            kw async
             kw const
             kw crate::
             kw enum
@@ -1446,7 +1443,6 @@ fn foo() {
         expect![[r#"
             fn foo()       fn()
             bt u32         u32
-            kw async
             kw const
             kw crate::
             kw enum