aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorbors[bot] <26634292+bors[bot]@users.noreply.github.com>2021-04-24 12:39:50 +0100
committerGitHub <[email protected]>2021-04-24 12:39:50 +0100
commit1b4defd2409d6a6120b40a0730e9822a819e971d (patch)
tree558c6d18d829a5a0b954654df5b232772839c86f
parent4d110dd118e42a355ca8db41c7fdbf4371c45105 (diff)
parent050c69c19dd8004c8dfc92dbff86a42fac022e6e (diff)
Merge #8647
8647: internal: Split out merge_imports module from helpers::insert_use r=Veykril a=Veykril bors r+ Co-authored-by: Lukas Wirth <[email protected]>
-rw-r--r--crates/ide_assists/src/handlers/merge_imports.rs2
-rw-r--r--crates/ide_assists/src/tests.rs5
-rw-r--r--crates/ide_completion/src/test_utils.rs5
-rw-r--r--crates/ide_db/src/helpers.rs3
-rw-r--r--crates/ide_db/src/helpers/insert_use.rs324
-rw-r--r--crates/ide_db/src/helpers/merge_imports.rs309
-rw-r--r--crates/rust-analyzer/src/config.rs3
-rw-r--r--crates/syntax/src/ast/node_ext.rs22
8 files changed, 344 insertions, 329 deletions
diff --git a/crates/ide_assists/src/handlers/merge_imports.rs b/crates/ide_assists/src/handlers/merge_imports.rs
index 8e0794218..add7b8e37 100644
--- a/crates/ide_assists/src/handlers/merge_imports.rs
+++ b/crates/ide_assists/src/handlers/merge_imports.rs
@@ -1,4 +1,4 @@
1use ide_db::helpers::insert_use::{try_merge_imports, try_merge_trees, MergeBehavior}; 1use ide_db::helpers::merge_imports::{try_merge_imports, try_merge_trees, MergeBehavior};
2use syntax::{algo::neighbor, ast, ted, AstNode}; 2use syntax::{algo::neighbor, ast, ted, AstNode};
3 3
4use crate::{ 4use crate::{
diff --git a/crates/ide_assists/src/tests.rs b/crates/ide_assists/src/tests.rs
index 49533e7d2..6f4f97361 100644
--- a/crates/ide_assists/src/tests.rs
+++ b/crates/ide_assists/src/tests.rs
@@ -4,10 +4,7 @@ use expect_test::expect;
4use hir::Semantics; 4use hir::Semantics;
5use ide_db::{ 5use ide_db::{
6 base_db::{fixture::WithFixture, FileId, FileRange, SourceDatabaseExt}, 6 base_db::{fixture::WithFixture, FileId, FileRange, SourceDatabaseExt},
7 helpers::{ 7 helpers::{insert_use::InsertUseConfig, merge_imports::MergeBehavior, SnippetCap},
8 insert_use::{InsertUseConfig, MergeBehavior},
9 SnippetCap,
10 },
11 source_change::FileSystemEdit, 8 source_change::FileSystemEdit,
12 RootDatabase, 9 RootDatabase,
13}; 10};
diff --git a/crates/ide_completion/src/test_utils.rs b/crates/ide_completion/src/test_utils.rs
index 9da844031..c9857ec5f 100644
--- a/crates/ide_completion/src/test_utils.rs
+++ b/crates/ide_completion/src/test_utils.rs
@@ -3,10 +3,7 @@
3use hir::{PrefixKind, Semantics}; 3use hir::{PrefixKind, Semantics};
4use ide_db::{ 4use ide_db::{
5 base_db::{fixture::ChangeFixture, FileLoader, FilePosition}, 5 base_db::{fixture::ChangeFixture, FileLoader, FilePosition},
6 helpers::{ 6 helpers::{insert_use::InsertUseConfig, merge_imports::MergeBehavior, SnippetCap},
7 insert_use::{InsertUseConfig, MergeBehavior},
8 SnippetCap,
9 },
10 RootDatabase, 7 RootDatabase,
11}; 8};
12use itertools::Itertools; 9use itertools::Itertools;
diff --git a/crates/ide_db/src/helpers.rs b/crates/ide_db/src/helpers.rs
index 720de0d1f..21b48237a 100644
--- a/crates/ide_db/src/helpers.rs
+++ b/crates/ide_db/src/helpers.rs
@@ -1,6 +1,7 @@
1//! A module with ide helpers for high-level ide features. 1//! A module with ide helpers for high-level ide features.
2pub mod insert_use;
3pub mod import_assets; 2pub mod import_assets;
3pub mod insert_use;
4pub mod merge_imports;
4pub mod rust_doc; 5pub mod rust_doc;
5 6
6use std::collections::VecDeque; 7use std::collections::VecDeque;
diff --git a/crates/ide_db/src/helpers/insert_use.rs b/crates/ide_db/src/helpers/insert_use.rs
index a43504a27..55cdc4da3 100644
--- a/crates/ide_db/src/helpers/insert_use.rs
+++ b/crates/ide_db/src/helpers/insert_use.rs
@@ -1,15 +1,17 @@
1//! Handle syntactic aspects of inserting a new `use`. 1//! Handle syntactic aspects of inserting a new `use`.
2use std::{cmp::Ordering, iter::successors}; 2use std::cmp::Ordering;
3 3
4use hir::Semantics; 4use hir::Semantics;
5use itertools::{EitherOrBoth, Itertools};
6use syntax::{ 5use syntax::{
7 algo, 6 algo,
8 ast::{self, edit::AstNodeEdit, make, AstNode, AttrsOwner, PathSegmentKind, VisibilityOwner}, 7 ast::{self, make, AstNode, PathSegmentKind},
9 ted, AstToken, Direction, NodeOrToken, SyntaxNode, SyntaxToken, 8 ted, AstToken, Direction, NodeOrToken, SyntaxNode, SyntaxToken,
10}; 9};
11 10
12use crate::RootDatabase; 11use crate::{
12 helpers::merge_imports::{try_merge_imports, use_tree_path_cmp, MergeBehavior},
13 RootDatabase,
14};
13 15
14pub use hir::PrefixKind; 16pub use hir::PrefixKind;
15 17
@@ -85,318 +87,6 @@ pub fn insert_use<'a>(scope: &ImportScope, path: ast::Path, cfg: InsertUseConfig
85 insert_use_(scope, path, cfg.group, use_item); 87 insert_use_(scope, path, cfg.group, use_item);
86} 88}
87 89
88fn eq_visibility(vis0: Option<ast::Visibility>, vis1: Option<ast::Visibility>) -> bool {
89 match (vis0, vis1) {
90 (None, None) => true,
91 // FIXME: Don't use the string representation to check for equality
92 // spaces inside of the node would break this comparison
93 (Some(vis0), Some(vis1)) => vis0.to_string() == vis1.to_string(),
94 _ => false,
95 }
96}
97
98fn eq_attrs(
99 attrs0: impl Iterator<Item = ast::Attr>,
100 attrs1: impl Iterator<Item = ast::Attr>,
101) -> bool {
102 let attrs0 = attrs0.map(|attr| attr.to_string());
103 let attrs1 = attrs1.map(|attr| attr.to_string());
104 attrs0.eq(attrs1)
105}
106
107pub fn try_merge_imports(
108 lhs: &ast::Use,
109 rhs: &ast::Use,
110 merge_behavior: MergeBehavior,
111) -> Option<ast::Use> {
112 // don't merge imports with different visibilities
113 if !eq_visibility(lhs.visibility(), rhs.visibility()) {
114 return None;
115 }
116 if !eq_attrs(lhs.attrs(), rhs.attrs()) {
117 return None;
118 }
119
120 let lhs_tree = lhs.use_tree()?;
121 let rhs_tree = rhs.use_tree()?;
122 let merged = try_merge_trees(&lhs_tree, &rhs_tree, merge_behavior)?;
123 Some(lhs.with_use_tree(merged).clone_for_update())
124}
125
126pub fn try_merge_trees(
127 lhs: &ast::UseTree,
128 rhs: &ast::UseTree,
129 merge: MergeBehavior,
130) -> Option<ast::UseTree> {
131 let lhs_path = lhs.path()?;
132 let rhs_path = rhs.path()?;
133
134 let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
135 let (lhs, rhs) = if is_simple_path(lhs)
136 && is_simple_path(rhs)
137 && lhs_path == lhs_prefix
138 && rhs_path == rhs_prefix
139 {
140 (lhs.clone(), rhs.clone())
141 } else {
142 (lhs.split_prefix(&lhs_prefix), rhs.split_prefix(&rhs_prefix))
143 };
144 recursive_merge(&lhs, &rhs, merge)
145}
146
147/// Recursively "zips" together lhs and rhs.
148fn recursive_merge(
149 lhs: &ast::UseTree,
150 rhs: &ast::UseTree,
151 merge: MergeBehavior,
152) -> Option<ast::UseTree> {
153 let mut use_trees = lhs
154 .use_tree_list()
155 .into_iter()
156 .flat_map(|list| list.use_trees())
157 // we use Option here to early return from this function(this is not the same as a `filter` op)
158 .map(|tree| match merge.is_tree_allowed(&tree) {
159 true => Some(tree),
160 false => None,
161 })
162 .collect::<Option<Vec<_>>>()?;
163 use_trees.sort_unstable_by(|a, b| path_cmp_for_sort(a.path(), b.path()));
164 for rhs_t in rhs.use_tree_list().into_iter().flat_map(|list| list.use_trees()) {
165 if !merge.is_tree_allowed(&rhs_t) {
166 return None;
167 }
168 let rhs_path = rhs_t.path();
169 match use_trees.binary_search_by(|lhs_t| {
170 let (lhs_t, rhs_t) = match lhs_t
171 .path()
172 .zip(rhs_path.clone())
173 .and_then(|(lhs, rhs)| common_prefix(&lhs, &rhs))
174 {
175 Some((lhs_p, rhs_p)) => (lhs_t.split_prefix(&lhs_p), rhs_t.split_prefix(&rhs_p)),
176 None => (lhs_t.clone(), rhs_t.clone()),
177 };
178
179 path_cmp_bin_search(lhs_t.path(), rhs_t.path())
180 }) {
181 Ok(idx) => {
182 let lhs_t = &mut use_trees[idx];
183 let lhs_path = lhs_t.path()?;
184 let rhs_path = rhs_path?;
185 let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
186 if lhs_prefix == lhs_path && rhs_prefix == rhs_path {
187 let tree_is_self = |tree: ast::UseTree| {
188 tree.path().as_ref().map(path_is_self).unwrap_or(false)
189 };
190 // check if only one of the two trees has a tree list, and whether that then contains `self` or not.
191 // If this is the case we can skip this iteration since the path without the list is already included in the other one via `self`
192 let tree_contains_self = |tree: &ast::UseTree| {
193 tree.use_tree_list()
194 .map(|tree_list| tree_list.use_trees().any(tree_is_self))
195 .unwrap_or(false)
196 };
197 match (tree_contains_self(&lhs_t), tree_contains_self(&rhs_t)) {
198 (true, false) => continue,
199 (false, true) => {
200 *lhs_t = rhs_t;
201 continue;
202 }
203 _ => (),
204 }
205
206 // glob imports arent part of the use-tree lists so we need to special handle them here as well
207 // this special handling is only required for when we merge a module import into a glob import of said module
208 // see the `merge_self_glob` or `merge_mod_into_glob` tests
209 if lhs_t.star_token().is_some() || rhs_t.star_token().is_some() {
210 *lhs_t = make::use_tree(
211 make::path_unqualified(make::path_segment_self()),
212 None,
213 None,
214 false,
215 );
216 use_trees.insert(idx, make::glob_use_tree());
217 continue;
218 }
219
220 if lhs_t.use_tree_list().is_none() && rhs_t.use_tree_list().is_none() {
221 continue;
222 }
223 }
224 let lhs = lhs_t.split_prefix(&lhs_prefix);
225 let rhs = rhs_t.split_prefix(&rhs_prefix);
226 match recursive_merge(&lhs, &rhs, merge) {
227 Some(use_tree) => use_trees[idx] = use_tree,
228 None => return None,
229 }
230 }
231 Err(_)
232 if merge == MergeBehavior::Last
233 && use_trees.len() > 0
234 && rhs_t.use_tree_list().is_some() =>
235 {
236 return None
237 }
238 Err(idx) => {
239 use_trees.insert(idx, rhs_t);
240 }
241 }
242 }
243
244 Some(if let Some(old) = lhs.use_tree_list() {
245 lhs.replace_descendant(old, make::use_tree_list(use_trees)).clone_for_update()
246 } else {
247 lhs.clone()
248 })
249}
250
251/// Traverses both paths until they differ, returning the common prefix of both.
252fn common_prefix(lhs: &ast::Path, rhs: &ast::Path) -> Option<(ast::Path, ast::Path)> {
253 let mut res = None;
254 let mut lhs_curr = first_path(&lhs);
255 let mut rhs_curr = first_path(&rhs);
256 loop {
257 match (lhs_curr.segment(), rhs_curr.segment()) {
258 (Some(lhs), Some(rhs)) if lhs.syntax().text() == rhs.syntax().text() => (),
259 _ => break res,
260 }
261 res = Some((lhs_curr.clone(), rhs_curr.clone()));
262
263 match lhs_curr.parent_path().zip(rhs_curr.parent_path()) {
264 Some((lhs, rhs)) => {
265 lhs_curr = lhs;
266 rhs_curr = rhs;
267 }
268 _ => break res,
269 }
270 }
271}
272
273fn is_simple_path(use_tree: &ast::UseTree) -> bool {
274 use_tree.use_tree_list().is_none() && use_tree.star_token().is_none()
275}
276
277fn path_is_self(path: &ast::Path) -> bool {
278 path.segment().and_then(|seg| seg.self_token()).is_some() && path.qualifier().is_none()
279}
280
281#[inline]
282fn first_segment(path: &ast::Path) -> Option<ast::PathSegment> {
283 first_path(path).segment()
284}
285
286fn first_path(path: &ast::Path) -> ast::Path {
287 successors(Some(path.clone()), ast::Path::qualifier).last().unwrap()
288}
289
290fn segment_iter(path: &ast::Path) -> impl Iterator<Item = ast::PathSegment> + Clone {
291 // cant make use of SyntaxNode::siblings, because the returned Iterator is not clone
292 successors(first_segment(path), |p| p.parent_path().parent_path().and_then(|p| p.segment()))
293}
294
295fn path_len(path: ast::Path) -> usize {
296 segment_iter(&path).count()
297}
298
299/// Orders paths in the following way:
300/// the sole self token comes first, after that come uppercase identifiers, then lowercase identifiers
301// FIXME: rustfmt sorts lowercase idents before uppercase, in general we want to have the same ordering rustfmt has
302// which is `self` and `super` first, then identifier imports with lowercase ones first, then glob imports and at last list imports.
303// Example foo::{self, foo, baz, Baz, Qux, *, {Bar}}
304fn path_cmp_for_sort(a: Option<ast::Path>, b: Option<ast::Path>) -> Ordering {
305 match (a, b) {
306 (None, None) => Ordering::Equal,
307 (None, Some(_)) => Ordering::Less,
308 (Some(_), None) => Ordering::Greater,
309 (Some(ref a), Some(ref b)) => match (path_is_self(a), path_is_self(b)) {
310 (true, true) => Ordering::Equal,
311 (true, false) => Ordering::Less,
312 (false, true) => Ordering::Greater,
313 (false, false) => path_cmp_short(a, b),
314 },
315 }
316}
317
318/// Path comparison func for binary searching for merging.
319fn path_cmp_bin_search(lhs: Option<ast::Path>, rhs: Option<ast::Path>) -> Ordering {
320 match (lhs.as_ref().and_then(first_segment), rhs.as_ref().and_then(first_segment)) {
321 (None, None) => Ordering::Equal,
322 (None, Some(_)) => Ordering::Less,
323 (Some(_), None) => Ordering::Greater,
324 (Some(ref a), Some(ref b)) => path_segment_cmp(a, b),
325 }
326}
327
328/// Short circuiting comparison, if both paths are equal until one of them ends they are considered
329/// equal
330fn path_cmp_short(a: &ast::Path, b: &ast::Path) -> Ordering {
331 let a = segment_iter(a);
332 let b = segment_iter(b);
333 // cmp_by would be useful for us here but that is currently unstable
334 // cmp doesnt work due the lifetimes on text's return type
335 a.zip(b)
336 .find_map(|(a, b)| match path_segment_cmp(&a, &b) {
337 Ordering::Equal => None,
338 ord => Some(ord),
339 })
340 .unwrap_or(Ordering::Equal)
341}
342
343/// Compares to paths, if one ends earlier than the other the has_tl parameters decide which is
344/// greater as a a path that has a tree list should be greater, while one that just ends without
345/// a tree list should be considered less.
346fn use_tree_path_cmp(a: &ast::Path, a_has_tl: bool, b: &ast::Path, b_has_tl: bool) -> Ordering {
347 let a_segments = segment_iter(a);
348 let b_segments = segment_iter(b);
349 // cmp_by would be useful for us here but that is currently unstable
350 // cmp doesnt work due the lifetimes on text's return type
351 a_segments
352 .zip_longest(b_segments)
353 .find_map(|zipped| match zipped {
354 EitherOrBoth::Both(ref a, ref b) => match path_segment_cmp(a, b) {
355 Ordering::Equal => None,
356 ord => Some(ord),
357 },
358 EitherOrBoth::Left(_) if !b_has_tl => Some(Ordering::Greater),
359 EitherOrBoth::Left(_) => Some(Ordering::Less),
360 EitherOrBoth::Right(_) if !a_has_tl => Some(Ordering::Less),
361 EitherOrBoth::Right(_) => Some(Ordering::Greater),
362 })
363 .unwrap_or(Ordering::Equal)
364}
365
366fn path_segment_cmp(a: &ast::PathSegment, b: &ast::PathSegment) -> Ordering {
367 let a = a.kind().and_then(|kind| match kind {
368 PathSegmentKind::Name(name_ref) => Some(name_ref),
369 _ => None,
370 });
371 let b = b.kind().and_then(|kind| match kind {
372 PathSegmentKind::Name(name_ref) => Some(name_ref),
373 _ => None,
374 });
375 a.as_ref().map(ast::NameRef::text).cmp(&b.as_ref().map(ast::NameRef::text))
376}
377
378/// What type of merges are allowed.
379#[derive(Copy, Clone, Debug, PartialEq, Eq)]
380pub enum MergeBehavior {
381 /// Merge everything together creating deeply nested imports.
382 Full,
383 /// Only merge the last import level, doesn't allow import nesting.
384 Last,
385}
386
387impl MergeBehavior {
388 #[inline]
389 fn is_tree_allowed(&self, tree: &ast::UseTree) -> bool {
390 match self {
391 MergeBehavior::Full => true,
392 // only simple single segment paths are allowed
393 MergeBehavior::Last => {
394 tree.use_tree_list().is_none() && tree.path().map(path_len) <= Some(1)
395 }
396 }
397 }
398}
399
400#[derive(Eq, PartialEq, PartialOrd, Ord)] 90#[derive(Eq, PartialEq, PartialOrd, Ord)]
401enum ImportGroup { 91enum ImportGroup {
402 // the order here defines the order of new group inserts 92 // the order here defines the order of new group inserts
@@ -411,7 +101,7 @@ impl ImportGroup {
411 fn new(path: &ast::Path) -> ImportGroup { 101 fn new(path: &ast::Path) -> ImportGroup {
412 let default = ImportGroup::ExternCrate; 102 let default = ImportGroup::ExternCrate;
413 103
414 let first_segment = match first_segment(path) { 104 let first_segment = match path.first_segment() {
415 Some(it) => it, 105 Some(it) => it,
416 None => return default, 106 None => return default,
417 }; 107 };
diff --git a/crates/ide_db/src/helpers/merge_imports.rs b/crates/ide_db/src/helpers/merge_imports.rs
new file mode 100644
index 000000000..3f5bbef7f
--- /dev/null
+++ b/crates/ide_db/src/helpers/merge_imports.rs
@@ -0,0 +1,309 @@
1//! Handle syntactic aspects of merging UseTrees.
2use std::cmp::Ordering;
3
4use itertools::{EitherOrBoth, Itertools};
5use syntax::ast::{
6 self, edit::AstNodeEdit, make, AstNode, AttrsOwner, PathSegmentKind, VisibilityOwner,
7};
8
9/// What type of merges are allowed.
10#[derive(Copy, Clone, Debug, PartialEq, Eq)]
11pub enum MergeBehavior {
12 /// Merge everything together creating deeply nested imports.
13 Full,
14 /// Only merge the last import level, doesn't allow import nesting.
15 Last,
16}
17
18impl MergeBehavior {
19 #[inline]
20 fn is_tree_allowed(&self, tree: &ast::UseTree) -> bool {
21 match self {
22 MergeBehavior::Full => true,
23 // only simple single segment paths are allowed
24 MergeBehavior::Last => {
25 tree.use_tree_list().is_none() && tree.path().map(path_len) <= Some(1)
26 }
27 }
28 }
29}
30
31pub fn try_merge_imports(
32 lhs: &ast::Use,
33 rhs: &ast::Use,
34 merge_behavior: MergeBehavior,
35) -> Option<ast::Use> {
36 // don't merge imports with different visibilities
37 if !eq_visibility(lhs.visibility(), rhs.visibility()) {
38 return None;
39 }
40 if !eq_attrs(lhs.attrs(), rhs.attrs()) {
41 return None;
42 }
43
44 let lhs_tree = lhs.use_tree()?;
45 let rhs_tree = rhs.use_tree()?;
46 let merged = try_merge_trees(&lhs_tree, &rhs_tree, merge_behavior)?;
47 Some(lhs.with_use_tree(merged).clone_for_update())
48}
49
50pub fn try_merge_trees(
51 lhs: &ast::UseTree,
52 rhs: &ast::UseTree,
53 merge: MergeBehavior,
54) -> Option<ast::UseTree> {
55 let lhs_path = lhs.path()?;
56 let rhs_path = rhs.path()?;
57
58 let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
59 let (lhs, rhs) = if lhs.is_simple_path()
60 && rhs.is_simple_path()
61 && lhs_path == lhs_prefix
62 && rhs_path == rhs_prefix
63 {
64 (lhs.clone(), rhs.clone())
65 } else {
66 (lhs.split_prefix(&lhs_prefix), rhs.split_prefix(&rhs_prefix))
67 };
68 recursive_merge(&lhs, &rhs, merge)
69}
70
71/// Recursively "zips" together lhs and rhs.
72fn recursive_merge(
73 lhs: &ast::UseTree,
74 rhs: &ast::UseTree,
75 merge: MergeBehavior,
76) -> Option<ast::UseTree> {
77 let mut use_trees = lhs
78 .use_tree_list()
79 .into_iter()
80 .flat_map(|list| list.use_trees())
81 // we use Option here to early return from this function(this is not the same as a `filter` op)
82 .map(|tree| match merge.is_tree_allowed(&tree) {
83 true => Some(tree),
84 false => None,
85 })
86 .collect::<Option<Vec<_>>>()?;
87 use_trees.sort_unstable_by(|a, b| path_cmp_for_sort(a.path(), b.path()));
88 for rhs_t in rhs.use_tree_list().into_iter().flat_map(|list| list.use_trees()) {
89 if !merge.is_tree_allowed(&rhs_t) {
90 return None;
91 }
92 let rhs_path = rhs_t.path();
93 match use_trees.binary_search_by(|lhs_t| {
94 let (lhs_t, rhs_t) = match lhs_t
95 .path()
96 .zip(rhs_path.clone())
97 .and_then(|(lhs, rhs)| common_prefix(&lhs, &rhs))
98 {
99 Some((lhs_p, rhs_p)) => (lhs_t.split_prefix(&lhs_p), rhs_t.split_prefix(&rhs_p)),
100 None => (lhs_t.clone(), rhs_t.clone()),
101 };
102
103 path_cmp_bin_search(lhs_t.path(), rhs_t.path())
104 }) {
105 Ok(idx) => {
106 let lhs_t = &mut use_trees[idx];
107 let lhs_path = lhs_t.path()?;
108 let rhs_path = rhs_path?;
109 let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
110 if lhs_prefix == lhs_path && rhs_prefix == rhs_path {
111 let tree_is_self = |tree: ast::UseTree| {
112 tree.path().as_ref().map(path_is_self).unwrap_or(false)
113 };
114 // check if only one of the two trees has a tree list, and whether that then contains `self` or not.
115 // If this is the case we can skip this iteration since the path without the list is already included in the other one via `self`
116 let tree_contains_self = |tree: &ast::UseTree| {
117 tree.use_tree_list()
118 .map(|tree_list| tree_list.use_trees().any(tree_is_self))
119 .unwrap_or(false)
120 };
121 match (tree_contains_self(&lhs_t), tree_contains_self(&rhs_t)) {
122 (true, false) => continue,
123 (false, true) => {
124 *lhs_t = rhs_t;
125 continue;
126 }
127 _ => (),
128 }
129
130 // glob imports arent part of the use-tree lists so we need to special handle them here as well
131 // this special handling is only required for when we merge a module import into a glob import of said module
132 // see the `merge_self_glob` or `merge_mod_into_glob` tests
133 if lhs_t.star_token().is_some() || rhs_t.star_token().is_some() {
134 *lhs_t = make::use_tree(
135 make::path_unqualified(make::path_segment_self()),
136 None,
137 None,
138 false,
139 );
140 use_trees.insert(idx, make::glob_use_tree());
141 continue;
142 }
143
144 if lhs_t.use_tree_list().is_none() && rhs_t.use_tree_list().is_none() {
145 continue;
146 }
147 }
148 let lhs = lhs_t.split_prefix(&lhs_prefix);
149 let rhs = rhs_t.split_prefix(&rhs_prefix);
150 match recursive_merge(&lhs, &rhs, merge) {
151 Some(use_tree) => use_trees[idx] = use_tree,
152 None => return None,
153 }
154 }
155 Err(_)
156 if merge == MergeBehavior::Last
157 && use_trees.len() > 0
158 && rhs_t.use_tree_list().is_some() =>
159 {
160 return None
161 }
162 Err(idx) => {
163 use_trees.insert(idx, rhs_t);
164 }
165 }
166 }
167
168 Some(if let Some(old) = lhs.use_tree_list() {
169 lhs.replace_descendant(old, make::use_tree_list(use_trees)).clone_for_update()
170 } else {
171 lhs.clone()
172 })
173}
174
175/// Traverses both paths until they differ, returning the common prefix of both.
176fn common_prefix(lhs: &ast::Path, rhs: &ast::Path) -> Option<(ast::Path, ast::Path)> {
177 let mut res = None;
178 let mut lhs_curr = lhs.first_qualifier_or_self();
179 let mut rhs_curr = rhs.first_qualifier_or_self();
180 loop {
181 match (lhs_curr.segment(), rhs_curr.segment()) {
182 (Some(lhs), Some(rhs)) if lhs.syntax().text() == rhs.syntax().text() => (),
183 _ => break res,
184 }
185 res = Some((lhs_curr.clone(), rhs_curr.clone()));
186
187 match lhs_curr.parent_path().zip(rhs_curr.parent_path()) {
188 Some((lhs, rhs)) => {
189 lhs_curr = lhs;
190 rhs_curr = rhs;
191 }
192 _ => break res,
193 }
194 }
195}
196
197/// Orders paths in the following way:
198/// the sole self token comes first, after that come uppercase identifiers, then lowercase identifiers
199// FIXME: rustfmt sorts lowercase idents before uppercase, in general we want to have the same ordering rustfmt has
200// which is `self` and `super` first, then identifier imports with lowercase ones first, then glob imports and at last list imports.
201// Example foo::{self, foo, baz, Baz, Qux, *, {Bar}}
202fn path_cmp_for_sort(a: Option<ast::Path>, b: Option<ast::Path>) -> Ordering {
203 match (a, b) {
204 (None, None) => Ordering::Equal,
205 (None, Some(_)) => Ordering::Less,
206 (Some(_), None) => Ordering::Greater,
207 (Some(ref a), Some(ref b)) => match (path_is_self(a), path_is_self(b)) {
208 (true, true) => Ordering::Equal,
209 (true, false) => Ordering::Less,
210 (false, true) => Ordering::Greater,
211 (false, false) => path_cmp_short(a, b),
212 },
213 }
214}
215
216/// Path comparison func for binary searching for merging.
217fn path_cmp_bin_search(lhs: Option<ast::Path>, rhs: Option<ast::Path>) -> Ordering {
218 match (
219 lhs.as_ref().and_then(ast::Path::first_segment),
220 rhs.as_ref().and_then(ast::Path::first_segment),
221 ) {
222 (None, None) => Ordering::Equal,
223 (None, Some(_)) => Ordering::Less,
224 (Some(_), None) => Ordering::Greater,
225 (Some(ref a), Some(ref b)) => path_segment_cmp(a, b),
226 }
227}
228
229/// Short circuiting comparison, if both paths are equal until one of them ends they are considered
230/// equal
231fn path_cmp_short(a: &ast::Path, b: &ast::Path) -> Ordering {
232 let a = a.segments();
233 let b = b.segments();
234 // cmp_by would be useful for us here but that is currently unstable
235 // cmp doesn't work due the lifetimes on text's return type
236 a.zip(b)
237 .find_map(|(a, b)| match path_segment_cmp(&a, &b) {
238 Ordering::Equal => None,
239 ord => Some(ord),
240 })
241 .unwrap_or(Ordering::Equal)
242}
243
244/// Compares two paths, if one ends earlier than the other the has_tl parameters decide which is
245/// greater as a a path that has a tree list should be greater, while one that just ends without
246/// a tree list should be considered less.
247pub(super) fn use_tree_path_cmp(
248 a: &ast::Path,
249 a_has_tl: bool,
250 b: &ast::Path,
251 b_has_tl: bool,
252) -> Ordering {
253 let a_segments = a.segments();
254 let b_segments = b.segments();
255 // cmp_by would be useful for us here but that is currently unstable
256 // cmp doesn't work due the lifetimes on text's return type
257 a_segments
258 .zip_longest(b_segments)
259 .find_map(|zipped| match zipped {
260 EitherOrBoth::Both(ref a, ref b) => match path_segment_cmp(a, b) {
261 Ordering::Equal => None,
262 ord => Some(ord),
263 },
264 EitherOrBoth::Left(_) if !b_has_tl => Some(Ordering::Greater),
265 EitherOrBoth::Left(_) => Some(Ordering::Less),
266 EitherOrBoth::Right(_) if !a_has_tl => Some(Ordering::Less),
267 EitherOrBoth::Right(_) => Some(Ordering::Greater),
268 })
269 .unwrap_or(Ordering::Equal)
270}
271
272fn path_segment_cmp(a: &ast::PathSegment, b: &ast::PathSegment) -> Ordering {
273 let a = a.kind().and_then(|kind| match kind {
274 PathSegmentKind::Name(name_ref) => Some(name_ref),
275 _ => None,
276 });
277 let b = b.kind().and_then(|kind| match kind {
278 PathSegmentKind::Name(name_ref) => Some(name_ref),
279 _ => None,
280 });
281 a.as_ref().map(ast::NameRef::text).cmp(&b.as_ref().map(ast::NameRef::text))
282}
283
284fn eq_visibility(vis0: Option<ast::Visibility>, vis1: Option<ast::Visibility>) -> bool {
285 match (vis0, vis1) {
286 (None, None) => true,
287 // FIXME: Don't use the string representation to check for equality
288 // spaces inside of the node would break this comparison
289 (Some(vis0), Some(vis1)) => vis0.to_string() == vis1.to_string(),
290 _ => false,
291 }
292}
293
294fn eq_attrs(
295 attrs0: impl Iterator<Item = ast::Attr>,
296 attrs1: impl Iterator<Item = ast::Attr>,
297) -> bool {
298 let attrs0 = attrs0.map(|attr| attr.to_string());
299 let attrs1 = attrs1.map(|attr| attr.to_string());
300 attrs0.eq(attrs1)
301}
302
303fn path_is_self(path: &ast::Path) -> bool {
304 path.segment().and_then(|seg| seg.self_token()).is_some() && path.qualifier().is_none()
305}
306
307fn path_len(path: ast::Path) -> usize {
308 path.segments().count()
309}
diff --git a/crates/rust-analyzer/src/config.rs b/crates/rust-analyzer/src/config.rs
index 1109d2daf..d81ee94ee 100644
--- a/crates/rust-analyzer/src/config.rs
+++ b/crates/rust-analyzer/src/config.rs
@@ -12,7 +12,8 @@ use std::{ffi::OsString, iter, path::PathBuf};
12use flycheck::FlycheckConfig; 12use flycheck::FlycheckConfig;
13use ide::{AssistConfig, CompletionConfig, DiagnosticsConfig, HoverConfig, InlayHintsConfig}; 13use ide::{AssistConfig, CompletionConfig, DiagnosticsConfig, HoverConfig, InlayHintsConfig};
14use ide_db::helpers::{ 14use ide_db::helpers::{
15 insert_use::{InsertUseConfig, MergeBehavior, PrefixKind}, 15 insert_use::{InsertUseConfig, PrefixKind},
16 merge_imports::MergeBehavior,
16 SnippetCap, 17 SnippetCap,
17}; 18};
18use lsp_types::{ClientCapabilities, MarkupKind}; 19use lsp_types::{ClientCapabilities, MarkupKind};
diff --git a/crates/syntax/src/ast/node_ext.rs b/crates/syntax/src/ast/node_ext.rs
index 171099661..492fbc4a0 100644
--- a/crates/syntax/src/ast/node_ext.rs
+++ b/crates/syntax/src/ast/node_ext.rs
@@ -1,7 +1,7 @@
1//! Various extension methods to ast Nodes, which are hard to code-generate. 1//! Various extension methods to ast Nodes, which are hard to code-generate.
2//! Extensions for various expressions live in a sibling `expr_extensions` module. 2//! Extensions for various expressions live in a sibling `expr_extensions` module.
3 3
4use std::fmt; 4use std::{fmt, iter::successors};
5 5
6use itertools::Itertools; 6use itertools::Itertools;
7use parser::SyntaxKind; 7use parser::SyntaxKind;
@@ -237,6 +237,26 @@ impl ast::Path {
237 None => self.segment(), 237 None => self.segment(),
238 } 238 }
239 } 239 }
240
241 pub fn first_qualifier_or_self(&self) -> ast::Path {
242 successors(Some(self.clone()), ast::Path::qualifier).last().unwrap()
243 }
244
245 pub fn first_segment(&self) -> Option<ast::PathSegment> {
246 self.first_qualifier_or_self().segment()
247 }
248
249 pub fn segments(&self) -> impl Iterator<Item = ast::PathSegment> + Clone {
250 // cant make use of SyntaxNode::siblings, because the returned Iterator is not clone
251 successors(self.first_segment(), |p| {
252 p.parent_path().parent_path().and_then(|p| p.segment())
253 })
254 }
255}
256impl ast::UseTree {
257 pub fn is_simple_path(&self) -> bool {
258 self.use_tree_list().is_none() && self.star_token().is_none()
259 }
240} 260}
241 261
242impl ast::UseTreeList { 262impl ast::UseTreeList {