aboutsummaryrefslogtreecommitdiff
path: root/crates/ide_db
diff options
context:
space:
mode:
authorbors[bot] <26634292+bors[bot]@users.noreply.github.com>2020-11-28 14:33:57 +0000
committerGitHub <[email protected]>2020-11-28 14:33:57 +0000
commitb7ece77af49ce59762fc3246a4c721411efe637e (patch)
tree81c617c2df781e27b0c16c10515ebcf588cb376e /crates/ide_db
parentfe2ac4480bd71c9cf25d2c21bda82b33558d27a4 (diff)
parent3f612d37c68a6e4c09e407b7cd2ad8a1d17ab4e6 (diff)
Merge #6650
6650: Make completion and assists module independent r=matklad a=SomeoneToIgnore A follow-up of https://github.com/rust-analyzer/rust-analyzer/pull/6553#discussion_r524402907 Move the common code for both assists and completion modules into a separate crate. Co-authored-by: Kirill Bulatov <[email protected]>
Diffstat (limited to 'crates/ide_db')
-rw-r--r--crates/ide_db/Cargo.toml3
-rw-r--r--crates/ide_db/src/helpers.rs203
-rw-r--r--crates/ide_db/src/helpers/insert_use.rs1204
-rw-r--r--crates/ide_db/src/lib.rs1
4 files changed, 1410 insertions, 1 deletions
diff --git a/crates/ide_db/Cargo.toml b/crates/ide_db/Cargo.toml
index 72a9212f1..0ad6e1000 100644
--- a/crates/ide_db/Cargo.toml
+++ b/crates/ide_db/Cargo.toml
@@ -18,7 +18,8 @@ rayon = "1.5.0"
18fst = { version = "0.4", default-features = false } 18fst = { version = "0.4", default-features = false }
19rustc-hash = "1.1.0" 19rustc-hash = "1.1.0"
20once_cell = "1.3.1" 20once_cell = "1.3.1"
21either = "1.5.3" 21either = "1.6.1"
22itertools = "0.9.0"
22 23
23stdx = { path = "../stdx", version = "0.0.0" } 24stdx = { path = "../stdx", version = "0.0.0" }
24syntax = { path = "../syntax", version = "0.0.0" } 25syntax = { path = "../syntax", version = "0.0.0" }
diff --git a/crates/ide_db/src/helpers.rs b/crates/ide_db/src/helpers.rs
new file mode 100644
index 000000000..d988588ff
--- /dev/null
+++ b/crates/ide_db/src/helpers.rs
@@ -0,0 +1,203 @@
1//! A module with ide helpers for high-level ide features.
2use crate::RootDatabase;
3use hir::{Crate, Enum, Module, ScopeDef, Semantics, Trait};
4use syntax::ast::{self, make};
5
6pub mod insert_use;
7
8/// Converts the mod path struct into its ast representation.
9pub fn mod_path_to_ast(path: &hir::ModPath) -> ast::Path {
10 let _p = profile::span("mod_path_to_ast");
11
12 let mut segments = Vec::new();
13 let mut is_abs = false;
14 match path.kind {
15 hir::PathKind::Plain => {}
16 hir::PathKind::Super(0) => segments.push(make::path_segment_self()),
17 hir::PathKind::Super(n) => segments.extend((0..n).map(|_| make::path_segment_super())),
18 hir::PathKind::DollarCrate(_) | hir::PathKind::Crate => {
19 segments.push(make::path_segment_crate())
20 }
21 hir::PathKind::Abs => is_abs = true,
22 }
23
24 segments.extend(
25 path.segments
26 .iter()
27 .map(|segment| make::path_segment(make::name_ref(&segment.to_string()))),
28 );
29 make::path_from_segments(segments, is_abs)
30}
31
32/// Helps with finding well-know things inside the standard library. This is
33/// somewhat similar to the known paths infra inside hir, but it different; We
34/// want to make sure that IDE specific paths don't become interesting inside
35/// the compiler itself as well.
36pub struct FamousDefs<'a, 'b>(pub &'a Semantics<'b, RootDatabase>, pub Option<Crate>);
37
38#[allow(non_snake_case)]
39impl FamousDefs<'_, '_> {
40 pub const FIXTURE: &'static str = r#"//- /libcore.rs crate:core
41pub mod convert {
42 pub trait From<T> {
43 fn from(t: T) -> Self;
44 }
45}
46
47pub mod default {
48 pub trait Default {
49 fn default() -> Self;
50 }
51}
52
53pub mod iter {
54 pub use self::traits::{collect::IntoIterator, iterator::Iterator};
55 mod traits {
56 pub(crate) mod iterator {
57 use crate::option::Option;
58 pub trait Iterator {
59 type Item;
60 fn next(&mut self) -> Option<Self::Item>;
61 fn by_ref(&mut self) -> &mut Self {
62 self
63 }
64 fn take(self, n: usize) -> crate::iter::Take<Self> {
65 crate::iter::Take { inner: self }
66 }
67 }
68
69 impl<I: Iterator> Iterator for &mut I {
70 type Item = I::Item;
71 fn next(&mut self) -> Option<I::Item> {
72 (**self).next()
73 }
74 }
75 }
76 pub(crate) mod collect {
77 pub trait IntoIterator {
78 type Item;
79 }
80 }
81 }
82
83 pub use self::sources::*;
84 pub(crate) mod sources {
85 use super::Iterator;
86 use crate::option::Option::{self, *};
87 pub struct Repeat<A> {
88 element: A,
89 }
90
91 pub fn repeat<T>(elt: T) -> Repeat<T> {
92 Repeat { element: elt }
93 }
94
95 impl<A> Iterator for Repeat<A> {
96 type Item = A;
97
98 fn next(&mut self) -> Option<A> {
99 None
100 }
101 }
102 }
103
104 pub use self::adapters::*;
105 pub(crate) mod adapters {
106 use super::Iterator;
107 use crate::option::Option::{self, *};
108 pub struct Take<I> { pub(crate) inner: I }
109 impl<I> Iterator for Take<I> where I: Iterator {
110 type Item = <I as Iterator>::Item;
111 fn next(&mut self) -> Option<<I as Iterator>::Item> {
112 None
113 }
114 }
115 }
116}
117
118pub mod option {
119 pub enum Option<T> { None, Some(T)}
120}
121
122pub mod prelude {
123 pub use crate::{convert::From, iter::{IntoIterator, Iterator}, option::Option::{self, *}, default::Default};
124}
125#[prelude_import]
126pub use prelude::*;
127"#;
128
129 pub fn core(&self) -> Option<Crate> {
130 self.find_crate("core")
131 }
132
133 pub fn core_convert_From(&self) -> Option<Trait> {
134 self.find_trait("core:convert:From")
135 }
136
137 pub fn core_option_Option(&self) -> Option<Enum> {
138 self.find_enum("core:option:Option")
139 }
140
141 pub fn core_default_Default(&self) -> Option<Trait> {
142 self.find_trait("core:default:Default")
143 }
144
145 pub fn core_iter_Iterator(&self) -> Option<Trait> {
146 self.find_trait("core:iter:traits:iterator:Iterator")
147 }
148
149 pub fn core_iter(&self) -> Option<Module> {
150 self.find_module("core:iter")
151 }
152
153 fn find_trait(&self, path: &str) -> Option<Trait> {
154 match self.find_def(path)? {
155 hir::ScopeDef::ModuleDef(hir::ModuleDef::Trait(it)) => Some(it),
156 _ => None,
157 }
158 }
159
160 fn find_enum(&self, path: &str) -> Option<Enum> {
161 match self.find_def(path)? {
162 hir::ScopeDef::ModuleDef(hir::ModuleDef::Adt(hir::Adt::Enum(it))) => Some(it),
163 _ => None,
164 }
165 }
166
167 fn find_module(&self, path: &str) -> Option<Module> {
168 match self.find_def(path)? {
169 hir::ScopeDef::ModuleDef(hir::ModuleDef::Module(it)) => Some(it),
170 _ => None,
171 }
172 }
173
174 fn find_crate(&self, name: &str) -> Option<Crate> {
175 let krate = self.1?;
176 let db = self.0.db;
177 let res =
178 krate.dependencies(db).into_iter().find(|dep| dep.name.to_string() == name)?.krate;
179 Some(res)
180 }
181
182 fn find_def(&self, path: &str) -> Option<ScopeDef> {
183 let db = self.0.db;
184 let mut path = path.split(':');
185 let trait_ = path.next_back()?;
186 let std_crate = path.next()?;
187 let std_crate = self.find_crate(std_crate)?;
188 let mut module = std_crate.root_module(db);
189 for segment in path {
190 module = module.children(db).find_map(|child| {
191 let name = child.name(db)?;
192 if name.to_string() == segment {
193 Some(child)
194 } else {
195 None
196 }
197 })?;
198 }
199 let def =
200 module.scope(db, None).into_iter().find(|(name, _def)| name.to_string() == trait_)?.1;
201 Some(def)
202 }
203}
diff --git a/crates/ide_db/src/helpers/insert_use.rs b/crates/ide_db/src/helpers/insert_use.rs
new file mode 100644
index 000000000..67e800fad
--- /dev/null
+++ b/crates/ide_db/src/helpers/insert_use.rs
@@ -0,0 +1,1204 @@
1//! Handle syntactic aspects of inserting a new `use`.
2use std::{cmp::Ordering, iter::successors};
3
4use crate::RootDatabase;
5use hir::Semantics;
6use itertools::{EitherOrBoth, Itertools};
7use syntax::{
8 algo::SyntaxRewriter,
9 ast::{
10 self,
11 edit::{AstNodeEdit, IndentLevel},
12 make, AstNode, PathSegmentKind, VisibilityOwner,
13 },
14 AstToken, InsertPosition, NodeOrToken, SyntaxElement, SyntaxNode, SyntaxToken,
15};
16use test_utils::mark;
17
18#[derive(Debug, Clone)]
19pub enum ImportScope {
20 File(ast::SourceFile),
21 Module(ast::ItemList),
22}
23
24impl ImportScope {
25 pub fn from(syntax: SyntaxNode) -> Option<Self> {
26 if let Some(module) = ast::Module::cast(syntax.clone()) {
27 module.item_list().map(ImportScope::Module)
28 } else if let this @ Some(_) = ast::SourceFile::cast(syntax.clone()) {
29 this.map(ImportScope::File)
30 } else {
31 ast::ItemList::cast(syntax).map(ImportScope::Module)
32 }
33 }
34
35 /// Determines the containing syntax node in which to insert a `use` statement affecting `position`.
36 pub fn find_insert_use_container(
37 position: &SyntaxNode,
38 sema: &Semantics<'_, RootDatabase>,
39 ) -> Option<Self> {
40 sema.ancestors_with_macros(position.clone()).find_map(Self::from)
41 }
42
43 pub fn as_syntax_node(&self) -> &SyntaxNode {
44 match self {
45 ImportScope::File(file) => file.syntax(),
46 ImportScope::Module(item_list) => item_list.syntax(),
47 }
48 }
49
50 fn indent_level(&self) -> IndentLevel {
51 match self {
52 ImportScope::File(file) => file.indent_level(),
53 ImportScope::Module(item_list) => item_list.indent_level() + 1,
54 }
55 }
56
57 fn first_insert_pos(&self) -> (InsertPosition<SyntaxElement>, AddBlankLine) {
58 match self {
59 ImportScope::File(_) => (InsertPosition::First, AddBlankLine::AfterTwice),
60 // don't insert the imports before the item list's opening curly brace
61 ImportScope::Module(item_list) => item_list
62 .l_curly_token()
63 .map(|b| (InsertPosition::After(b.into()), AddBlankLine::Around))
64 .unwrap_or((InsertPosition::First, AddBlankLine::AfterTwice)),
65 }
66 }
67
68 fn insert_pos_after_last_inner_element(&self) -> (InsertPosition<SyntaxElement>, AddBlankLine) {
69 self.as_syntax_node()
70 .children_with_tokens()
71 .filter(|child| match child {
72 NodeOrToken::Node(node) => is_inner_attribute(node.clone()),
73 NodeOrToken::Token(token) => is_inner_comment(token.clone()),
74 })
75 .last()
76 .map(|last_inner_element| {
77 (InsertPosition::After(last_inner_element.into()), AddBlankLine::BeforeTwice)
78 })
79 .unwrap_or_else(|| self.first_insert_pos())
80 }
81}
82
83fn is_inner_attribute(node: SyntaxNode) -> bool {
84 ast::Attr::cast(node).map(|attr| attr.kind()) == Some(ast::AttrKind::Inner)
85}
86
87fn is_inner_comment(token: SyntaxToken) -> bool {
88 ast::Comment::cast(token).and_then(|comment| comment.kind().doc)
89 == Some(ast::CommentPlacement::Inner)
90}
91
92/// Insert an import path into the given file/node. A `merge` value of none indicates that no import merging is allowed to occur.
93pub fn insert_use<'a>(
94 scope: &ImportScope,
95 path: ast::Path,
96 merge: Option<MergeBehaviour>,
97) -> SyntaxRewriter<'a> {
98 let _p = profile::span("insert_use");
99 let mut rewriter = SyntaxRewriter::default();
100 let use_item = make::use_(make::use_tree(path.clone(), None, None, false));
101 // merge into existing imports if possible
102 if let Some(mb) = merge {
103 for existing_use in scope.as_syntax_node().children().filter_map(ast::Use::cast) {
104 if let Some(merged) = try_merge_imports(&existing_use, &use_item, mb) {
105 rewriter.replace(existing_use.syntax(), merged.syntax());
106 return rewriter;
107 }
108 }
109 }
110
111 // either we weren't allowed to merge or there is no import that fits the merge conditions
112 // so look for the place we have to insert to
113 let (insert_position, add_blank) = find_insert_position(scope, path);
114
115 let indent = if let ident_level @ 1..=usize::MAX = scope.indent_level().0 as usize {
116 Some(make::tokens::whitespace(&" ".repeat(4 * ident_level)).into())
117 } else {
118 None
119 };
120
121 let to_insert: Vec<SyntaxElement> = {
122 let mut buf = Vec::new();
123
124 match add_blank {
125 AddBlankLine::Before | AddBlankLine::Around => {
126 buf.push(make::tokens::single_newline().into())
127 }
128 AddBlankLine::BeforeTwice => buf.push(make::tokens::blank_line().into()),
129 _ => (),
130 }
131
132 if add_blank.has_before() {
133 if let Some(indent) = indent.clone() {
134 mark::hit!(insert_use_indent_before);
135 buf.push(indent);
136 }
137 }
138
139 buf.push(use_item.syntax().clone().into());
140
141 match add_blank {
142 AddBlankLine::After | AddBlankLine::Around => {
143 buf.push(make::tokens::single_newline().into())
144 }
145 AddBlankLine::AfterTwice => buf.push(make::tokens::blank_line().into()),
146 _ => (),
147 }
148
149 // only add indentation *after* our stuff if there's another node directly after it
150 if add_blank.has_after() && matches!(insert_position, InsertPosition::Before(_)) {
151 if let Some(indent) = indent {
152 mark::hit!(insert_use_indent_after);
153 buf.push(indent);
154 }
155 } else if add_blank.has_after() && matches!(insert_position, InsertPosition::After(_)) {
156 mark::hit!(insert_use_no_indent_after);
157 }
158
159 buf
160 };
161
162 match insert_position {
163 InsertPosition::First => {
164 rewriter.insert_many_as_first_children(scope.as_syntax_node(), to_insert)
165 }
166 InsertPosition::Last => return rewriter, // actually unreachable
167 InsertPosition::Before(anchor) => rewriter.insert_many_before(&anchor, to_insert),
168 InsertPosition::After(anchor) => rewriter.insert_many_after(&anchor, to_insert),
169 }
170 rewriter
171}
172
173fn eq_visibility(vis0: Option<ast::Visibility>, vis1: Option<ast::Visibility>) -> bool {
174 match (vis0, vis1) {
175 (None, None) => true,
176 // FIXME: Don't use the string representation to check for equality
177 // spaces inside of the node would break this comparison
178 (Some(vis0), Some(vis1)) => vis0.to_string() == vis1.to_string(),
179 _ => false,
180 }
181}
182
183pub fn try_merge_imports(
184 lhs: &ast::Use,
185 rhs: &ast::Use,
186 merge_behaviour: MergeBehaviour,
187) -> Option<ast::Use> {
188 // don't merge imports with different visibilities
189 if !eq_visibility(lhs.visibility(), rhs.visibility()) {
190 return None;
191 }
192 let lhs_tree = lhs.use_tree()?;
193 let rhs_tree = rhs.use_tree()?;
194 let merged = try_merge_trees(&lhs_tree, &rhs_tree, merge_behaviour)?;
195 Some(lhs.with_use_tree(merged))
196}
197
198pub fn try_merge_trees(
199 lhs: &ast::UseTree,
200 rhs: &ast::UseTree,
201 merge: MergeBehaviour,
202) -> Option<ast::UseTree> {
203 let lhs_path = lhs.path()?;
204 let rhs_path = rhs.path()?;
205
206 let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
207 let (lhs, rhs) = if is_simple_path(lhs)
208 && is_simple_path(rhs)
209 && lhs_path == lhs_prefix
210 && rhs_path == rhs_prefix
211 {
212 (lhs.clone(), rhs.clone())
213 } else {
214 (lhs.split_prefix(&lhs_prefix), rhs.split_prefix(&rhs_prefix))
215 };
216 recursive_merge(&lhs, &rhs, merge)
217}
218
219/// Recursively "zips" together lhs and rhs.
220fn recursive_merge(
221 lhs: &ast::UseTree,
222 rhs: &ast::UseTree,
223 merge: MergeBehaviour,
224) -> Option<ast::UseTree> {
225 let mut use_trees = lhs
226 .use_tree_list()
227 .into_iter()
228 .flat_map(|list| list.use_trees())
229 // we use Option here to early return from this function(this is not the same as a `filter` op)
230 .map(|tree| match merge.is_tree_allowed(&tree) {
231 true => Some(tree),
232 false => None,
233 })
234 .collect::<Option<Vec<_>>>()?;
235 use_trees.sort_unstable_by(|a, b| path_cmp_for_sort(a.path(), b.path()));
236 for rhs_t in rhs.use_tree_list().into_iter().flat_map(|list| list.use_trees()) {
237 if !merge.is_tree_allowed(&rhs_t) {
238 return None;
239 }
240 let rhs_path = rhs_t.path();
241 match use_trees.binary_search_by(|lhs_t| {
242 let (lhs_t, rhs_t) = match lhs_t
243 .path()
244 .zip(rhs_path.clone())
245 .and_then(|(lhs, rhs)| common_prefix(&lhs, &rhs))
246 {
247 Some((lhs_p, rhs_p)) => (lhs_t.split_prefix(&lhs_p), rhs_t.split_prefix(&rhs_p)),
248 None => (lhs_t.clone(), rhs_t.clone()),
249 };
250
251 path_cmp_bin_search(lhs_t.path(), rhs_t.path())
252 }) {
253 Ok(idx) => {
254 let lhs_t = &mut use_trees[idx];
255 let lhs_path = lhs_t.path()?;
256 let rhs_path = rhs_path?;
257 let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
258 if lhs_prefix == lhs_path && rhs_prefix == rhs_path {
259 let tree_is_self = |tree: ast::UseTree| {
260 tree.path().as_ref().map(path_is_self).unwrap_or(false)
261 };
262 // check if only one of the two trees has a tree list, and whether that then contains `self` or not.
263 // 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`
264 let tree_contains_self = |tree: &ast::UseTree| {
265 tree.use_tree_list()
266 .map(|tree_list| tree_list.use_trees().any(tree_is_self))
267 .unwrap_or(false)
268 };
269 match (tree_contains_self(&lhs_t), tree_contains_self(&rhs_t)) {
270 (true, false) => continue,
271 (false, true) => {
272 *lhs_t = rhs_t;
273 continue;
274 }
275 _ => (),
276 }
277
278 // glob imports arent part of the use-tree lists so we need to special handle them here as well
279 // this special handling is only required for when we merge a module import into a glob import of said module
280 // see the `merge_self_glob` or `merge_mod_into_glob` tests
281 if lhs_t.star_token().is_some() || rhs_t.star_token().is_some() {
282 *lhs_t = make::use_tree(
283 make::path_unqualified(make::path_segment_self()),
284 None,
285 None,
286 false,
287 );
288 use_trees.insert(idx, make::glob_use_tree());
289 continue;
290 }
291
292 if lhs_t.use_tree_list().is_none() && rhs_t.use_tree_list().is_none() {
293 continue;
294 }
295 }
296 let lhs = lhs_t.split_prefix(&lhs_prefix);
297 let rhs = rhs_t.split_prefix(&rhs_prefix);
298 match recursive_merge(&lhs, &rhs, merge) {
299 Some(use_tree) => use_trees[idx] = use_tree,
300 None => return None,
301 }
302 }
303 Err(_)
304 if merge == MergeBehaviour::Last
305 && use_trees.len() > 0
306 && rhs_t.use_tree_list().is_some() =>
307 {
308 return None
309 }
310 Err(idx) => {
311 use_trees.insert(idx, rhs_t);
312 }
313 }
314 }
315 Some(lhs.with_use_tree_list(make::use_tree_list(use_trees)))
316}
317
318/// Traverses both paths until they differ, returning the common prefix of both.
319fn common_prefix(lhs: &ast::Path, rhs: &ast::Path) -> Option<(ast::Path, ast::Path)> {
320 let mut res = None;
321 let mut lhs_curr = first_path(&lhs);
322 let mut rhs_curr = first_path(&rhs);
323 loop {
324 match (lhs_curr.segment(), rhs_curr.segment()) {
325 (Some(lhs), Some(rhs)) if lhs.syntax().text() == rhs.syntax().text() => (),
326 _ => break res,
327 }
328 res = Some((lhs_curr.clone(), rhs_curr.clone()));
329
330 match lhs_curr.parent_path().zip(rhs_curr.parent_path()) {
331 Some((lhs, rhs)) => {
332 lhs_curr = lhs;
333 rhs_curr = rhs;
334 }
335 _ => break res,
336 }
337 }
338}
339
340fn is_simple_path(use_tree: &ast::UseTree) -> bool {
341 use_tree.use_tree_list().is_none() && use_tree.star_token().is_none()
342}
343
344fn path_is_self(path: &ast::Path) -> bool {
345 path.segment().and_then(|seg| seg.self_token()).is_some() && path.qualifier().is_none()
346}
347
348#[inline]
349fn first_segment(path: &ast::Path) -> Option<ast::PathSegment> {
350 first_path(path).segment()
351}
352
353fn first_path(path: &ast::Path) -> ast::Path {
354 successors(Some(path.clone()), ast::Path::qualifier).last().unwrap()
355}
356
357fn segment_iter(path: &ast::Path) -> impl Iterator<Item = ast::PathSegment> + Clone {
358 // cant make use of SyntaxNode::siblings, because the returned Iterator is not clone
359 successors(first_segment(path), |p| p.parent_path().parent_path().and_then(|p| p.segment()))
360}
361
362fn path_len(path: ast::Path) -> usize {
363 segment_iter(&path).count()
364}
365
366/// Orders paths in the following way:
367/// the sole self token comes first, after that come uppercase identifiers, then lowercase identifiers
368// FIXME: rustfmt sorts lowercase idents before uppercase, in general we want to have the same ordering rustfmt has
369// which is `self` and `super` first, then identifier imports with lowercase ones first, then glob imports and at last list imports.
370// Example foo::{self, foo, baz, Baz, Qux, *, {Bar}}
371fn path_cmp_for_sort(a: Option<ast::Path>, b: Option<ast::Path>) -> Ordering {
372 match (a, b) {
373 (None, None) => Ordering::Equal,
374 (None, Some(_)) => Ordering::Less,
375 (Some(_), None) => Ordering::Greater,
376 (Some(ref a), Some(ref b)) => match (path_is_self(a), path_is_self(b)) {
377 (true, true) => Ordering::Equal,
378 (true, false) => Ordering::Less,
379 (false, true) => Ordering::Greater,
380 (false, false) => path_cmp_short(a, b),
381 },
382 }
383}
384
385/// Path comparison func for binary searching for merging.
386fn path_cmp_bin_search(lhs: Option<ast::Path>, rhs: Option<ast::Path>) -> Ordering {
387 match (lhs.and_then(|path| path.segment()), rhs.and_then(|path| path.segment())) {
388 (None, None) => Ordering::Equal,
389 (None, Some(_)) => Ordering::Less,
390 (Some(_), None) => Ordering::Greater,
391 (Some(ref a), Some(ref b)) => path_segment_cmp(a, b),
392 }
393}
394
395/// Short circuiting comparison, if both paths are equal until one of them ends they are considered
396/// equal
397fn path_cmp_short(a: &ast::Path, b: &ast::Path) -> Ordering {
398 let a = segment_iter(a);
399 let b = segment_iter(b);
400 // cmp_by would be useful for us here but that is currently unstable
401 // cmp doesnt work due the lifetimes on text's return type
402 a.zip(b)
403 .find_map(|(a, b)| match path_segment_cmp(&a, &b) {
404 Ordering::Equal => None,
405 ord => Some(ord),
406 })
407 .unwrap_or(Ordering::Equal)
408}
409
410/// Compares to paths, if one ends earlier than the other the has_tl parameters decide which is
411/// greater as a a path that has a tree list should be greater, while one that just ends without
412/// a tree list should be considered less.
413fn use_tree_path_cmp(a: &ast::Path, a_has_tl: bool, b: &ast::Path, b_has_tl: bool) -> Ordering {
414 let a_segments = segment_iter(a);
415 let b_segments = segment_iter(b);
416 // cmp_by would be useful for us here but that is currently unstable
417 // cmp doesnt work due the lifetimes on text's return type
418 a_segments
419 .zip_longest(b_segments)
420 .find_map(|zipped| match zipped {
421 EitherOrBoth::Both(ref a, ref b) => match path_segment_cmp(a, b) {
422 Ordering::Equal => None,
423 ord => Some(ord),
424 },
425 EitherOrBoth::Left(_) if !b_has_tl => Some(Ordering::Greater),
426 EitherOrBoth::Left(_) => Some(Ordering::Less),
427 EitherOrBoth::Right(_) if !a_has_tl => Some(Ordering::Less),
428 EitherOrBoth::Right(_) => Some(Ordering::Greater),
429 })
430 .unwrap_or(Ordering::Equal)
431}
432
433fn path_segment_cmp(a: &ast::PathSegment, b: &ast::PathSegment) -> Ordering {
434 let a = a.name_ref();
435 let b = b.name_ref();
436 a.as_ref().map(ast::NameRef::text).cmp(&b.as_ref().map(ast::NameRef::text))
437}
438
439/// What type of merges are allowed.
440#[derive(Copy, Clone, Debug, PartialEq, Eq)]
441pub enum MergeBehaviour {
442 /// Merge everything together creating deeply nested imports.
443 Full,
444 /// Only merge the last import level, doesn't allow import nesting.
445 Last,
446}
447
448impl MergeBehaviour {
449 #[inline]
450 fn is_tree_allowed(&self, tree: &ast::UseTree) -> bool {
451 match self {
452 MergeBehaviour::Full => true,
453 // only simple single segment paths are allowed
454 MergeBehaviour::Last => {
455 tree.use_tree_list().is_none() && tree.path().map(path_len) <= Some(1)
456 }
457 }
458 }
459}
460
461#[derive(Eq, PartialEq, PartialOrd, Ord)]
462enum ImportGroup {
463 // the order here defines the order of new group inserts
464 Std,
465 ExternCrate,
466 ThisCrate,
467 ThisModule,
468 SuperModule,
469}
470
471impl ImportGroup {
472 fn new(path: &ast::Path) -> ImportGroup {
473 let default = ImportGroup::ExternCrate;
474
475 let first_segment = match first_segment(path) {
476 Some(it) => it,
477 None => return default,
478 };
479
480 let kind = first_segment.kind().unwrap_or(PathSegmentKind::SelfKw);
481 match kind {
482 PathSegmentKind::SelfKw => ImportGroup::ThisModule,
483 PathSegmentKind::SuperKw => ImportGroup::SuperModule,
484 PathSegmentKind::CrateKw => ImportGroup::ThisCrate,
485 PathSegmentKind::Name(name) => match name.text().as_str() {
486 "std" => ImportGroup::Std,
487 "core" => ImportGroup::Std,
488 _ => ImportGroup::ExternCrate,
489 },
490 PathSegmentKind::Type { .. } => unreachable!(),
491 }
492 }
493}
494
495#[derive(PartialEq, Eq)]
496enum AddBlankLine {
497 Before,
498 BeforeTwice,
499 Around,
500 After,
501 AfterTwice,
502}
503
504impl AddBlankLine {
505 fn has_before(&self) -> bool {
506 matches!(self, AddBlankLine::Before | AddBlankLine::BeforeTwice | AddBlankLine::Around)
507 }
508 fn has_after(&self) -> bool {
509 matches!(self, AddBlankLine::After | AddBlankLine::AfterTwice | AddBlankLine::Around)
510 }
511}
512
513fn find_insert_position(
514 scope: &ImportScope,
515 insert_path: ast::Path,
516) -> (InsertPosition<SyntaxElement>, AddBlankLine) {
517 let group = ImportGroup::new(&insert_path);
518 let path_node_iter = scope
519 .as_syntax_node()
520 .children()
521 .filter_map(|node| ast::Use::cast(node.clone()).zip(Some(node)))
522 .flat_map(|(use_, node)| {
523 let tree = use_.use_tree()?;
524 let path = tree.path()?;
525 let has_tl = tree.use_tree_list().is_some();
526 Some((path, has_tl, node))
527 });
528 // Iterator that discards anything thats not in the required grouping
529 // This implementation allows the user to rearrange their import groups as this only takes the first group that fits
530 let group_iter = path_node_iter
531 .clone()
532 .skip_while(|(path, ..)| ImportGroup::new(path) != group)
533 .take_while(|(path, ..)| ImportGroup::new(path) == group);
534
535 // track the last element we iterated over, if this is still None after the iteration then that means we never iterated in the first place
536 let mut last = None;
537 // find the element that would come directly after our new import
538 let post_insert = group_iter.inspect(|(.., node)| last = Some(node.clone())).find(
539 |&(ref path, has_tl, _)| {
540 use_tree_path_cmp(&insert_path, false, path, has_tl) != Ordering::Greater
541 },
542 );
543 match post_insert {
544 // insert our import before that element
545 Some((.., node)) => (InsertPosition::Before(node.into()), AddBlankLine::After),
546 // there is no element after our new import, so append it to the end of the group
547 None => match last {
548 Some(node) => (InsertPosition::After(node.into()), AddBlankLine::Before),
549 // the group we were looking for actually doesnt exist, so insert
550 None => {
551 // similar concept here to the `last` from above
552 let mut last = None;
553 // find the group that comes after where we want to insert
554 let post_group = path_node_iter
555 .inspect(|(.., node)| last = Some(node.clone()))
556 .find(|(p, ..)| ImportGroup::new(p) > group);
557 match post_group {
558 Some((.., node)) => {
559 (InsertPosition::Before(node.into()), AddBlankLine::AfterTwice)
560 }
561 // there is no such group, so append after the last one
562 None => match last {
563 Some(node) => {
564 (InsertPosition::After(node.into()), AddBlankLine::BeforeTwice)
565 }
566 // there are no imports in this file at all
567 None => scope.insert_pos_after_last_inner_element(),
568 },
569 }
570 }
571 },
572 }
573}
574
575#[cfg(test)]
576mod tests {
577 use super::*;
578
579 use test_utils::assert_eq_text;
580
581 #[test]
582 fn insert_existing() {
583 check_full("std::fs", "use std::fs;", "use std::fs;")
584 }
585
586 #[test]
587 fn insert_start() {
588 check_none(
589 "std::bar::AA",
590 r"
591use std::bar::B;
592use std::bar::D;
593use std::bar::F;
594use std::bar::G;",
595 r"
596use std::bar::AA;
597use std::bar::B;
598use std::bar::D;
599use std::bar::F;
600use std::bar::G;",
601 )
602 }
603
604 #[test]
605 fn insert_start_indent() {
606 mark::check!(insert_use_indent_after);
607 check_none(
608 "std::bar::AA",
609 r"
610 use std::bar::B;
611 use std::bar::D;",
612 r"
613 use std::bar::AA;
614 use std::bar::B;
615 use std::bar::D;",
616 )
617 }
618
619 #[test]
620 fn insert_middle() {
621 check_none(
622 "std::bar::EE",
623 r"
624use std::bar::A;
625use std::bar::D;
626use std::bar::F;
627use std::bar::G;",
628 r"
629use std::bar::A;
630use std::bar::D;
631use std::bar::EE;
632use std::bar::F;
633use std::bar::G;",
634 )
635 }
636
637 #[test]
638 fn insert_middle_indent() {
639 check_none(
640 "std::bar::EE",
641 r"
642 use std::bar::A;
643 use std::bar::D;
644 use std::bar::F;
645 use std::bar::G;",
646 r"
647 use std::bar::A;
648 use std::bar::D;
649 use std::bar::EE;
650 use std::bar::F;
651 use std::bar::G;",
652 )
653 }
654
655 #[test]
656 fn insert_end() {
657 check_none(
658 "std::bar::ZZ",
659 r"
660use std::bar::A;
661use std::bar::D;
662use std::bar::F;
663use std::bar::G;",
664 r"
665use std::bar::A;
666use std::bar::D;
667use std::bar::F;
668use std::bar::G;
669use std::bar::ZZ;",
670 )
671 }
672
673 #[test]
674 fn insert_end_indent() {
675 mark::check!(insert_use_indent_before);
676 check_none(
677 "std::bar::ZZ",
678 r"
679 use std::bar::A;
680 use std::bar::D;
681 use std::bar::F;
682 use std::bar::G;",
683 r"
684 use std::bar::A;
685 use std::bar::D;
686 use std::bar::F;
687 use std::bar::G;
688 use std::bar::ZZ;",
689 )
690 }
691
692 #[test]
693 fn insert_middle_nested() {
694 check_none(
695 "std::bar::EE",
696 r"
697use std::bar::A;
698use std::bar::{D, Z}; // example of weird imports due to user
699use std::bar::F;
700use std::bar::G;",
701 r"
702use std::bar::A;
703use std::bar::EE;
704use std::bar::{D, Z}; // example of weird imports due to user
705use std::bar::F;
706use std::bar::G;",
707 )
708 }
709
710 #[test]
711 fn insert_middle_groups() {
712 check_none(
713 "foo::bar::GG",
714 r"
715 use std::bar::A;
716 use std::bar::D;
717
718 use foo::bar::F;
719 use foo::bar::H;",
720 r"
721 use std::bar::A;
722 use std::bar::D;
723
724 use foo::bar::F;
725 use foo::bar::GG;
726 use foo::bar::H;",
727 )
728 }
729
730 #[test]
731 fn insert_first_matching_group() {
732 check_none(
733 "foo::bar::GG",
734 r"
735 use foo::bar::A;
736 use foo::bar::D;
737
738 use std;
739
740 use foo::bar::F;
741 use foo::bar::H;",
742 r"
743 use foo::bar::A;
744 use foo::bar::D;
745 use foo::bar::GG;
746
747 use std;
748
749 use foo::bar::F;
750 use foo::bar::H;",
751 )
752 }
753
754 #[test]
755 fn insert_missing_group_std() {
756 check_none(
757 "std::fmt",
758 r"
759 use foo::bar::A;
760 use foo::bar::D;",
761 r"
762 use std::fmt;
763
764 use foo::bar::A;
765 use foo::bar::D;",
766 )
767 }
768
769 #[test]
770 fn insert_missing_group_self() {
771 check_none(
772 "self::fmt",
773 r"
774use foo::bar::A;
775use foo::bar::D;",
776 r"
777use foo::bar::A;
778use foo::bar::D;
779
780use self::fmt;",
781 )
782 }
783
784 #[test]
785 fn insert_no_imports() {
786 check_full(
787 "foo::bar",
788 "fn main() {}",
789 r"use foo::bar;
790
791fn main() {}",
792 )
793 }
794
795 #[test]
796 fn insert_empty_file() {
797 // empty files will get two trailing newlines
798 // this is due to the test case insert_no_imports above
799 check_full(
800 "foo::bar",
801 "",
802 r"use foo::bar;
803
804",
805 )
806 }
807
808 #[test]
809 fn insert_empty_module() {
810 mark::check!(insert_use_no_indent_after);
811 check(
812 "foo::bar",
813 "mod x {}",
814 r"{
815 use foo::bar;
816}",
817 None,
818 true,
819 )
820 }
821
822 #[test]
823 fn insert_after_inner_attr() {
824 check_full(
825 "foo::bar",
826 r"#![allow(unused_imports)]",
827 r"#![allow(unused_imports)]
828
829use foo::bar;",
830 )
831 }
832
833 #[test]
834 fn insert_after_inner_attr2() {
835 check_full(
836 "foo::bar",
837 r"#![allow(unused_imports)]
838
839#![no_std]
840fn main() {}",
841 r"#![allow(unused_imports)]
842
843#![no_std]
844
845use foo::bar;
846fn main() {}",
847 );
848 }
849
850 #[test]
851 fn inserts_after_single_line_inner_comments() {
852 check_none(
853 "foo::bar::Baz",
854 "//! Single line inner comments do not allow any code before them.",
855 r#"//! Single line inner comments do not allow any code before them.
856
857use foo::bar::Baz;"#,
858 );
859 }
860
861 #[test]
862 fn inserts_after_multiline_inner_comments() {
863 check_none(
864 "foo::bar::Baz",
865 r#"/*! Multiline inner comments do not allow any code before them. */
866
867/*! Still an inner comment, cannot place any code before. */
868fn main() {}"#,
869 r#"/*! Multiline inner comments do not allow any code before them. */
870
871/*! Still an inner comment, cannot place any code before. */
872
873use foo::bar::Baz;
874fn main() {}"#,
875 )
876 }
877
878 #[test]
879 fn inserts_after_all_inner_items() {
880 check_none(
881 "foo::bar::Baz",
882 r#"#![allow(unused_imports)]
883/*! Multiline line comment 2 */
884
885
886//! Single line comment 1
887#![no_std]
888//! Single line comment 2
889fn main() {}"#,
890 r#"#![allow(unused_imports)]
891/*! Multiline line comment 2 */
892
893
894//! Single line comment 1
895#![no_std]
896//! Single line comment 2
897
898use foo::bar::Baz;
899fn main() {}"#,
900 )
901 }
902
903 #[test]
904 fn merge_groups() {
905 check_last("std::io", r"use std::fmt;", r"use std::{fmt, io};")
906 }
907
908 #[test]
909 fn merge_groups_last() {
910 check_last(
911 "std::io",
912 r"use std::fmt::{Result, Display};",
913 r"use std::fmt::{Result, Display};
914use std::io;",
915 )
916 }
917
918 #[test]
919 fn merge_last_into_self() {
920 check_last("foo::bar::baz", r"use foo::bar;", r"use foo::bar::{self, baz};");
921 }
922
923 #[test]
924 fn merge_groups_full() {
925 check_full(
926 "std::io",
927 r"use std::fmt::{Result, Display};",
928 r"use std::{fmt::{Result, Display}, io};",
929 )
930 }
931
932 #[test]
933 fn merge_groups_long_full() {
934 check_full(
935 "std::foo::bar::Baz",
936 r"use std::foo::bar::Qux;",
937 r"use std::foo::bar::{Baz, Qux};",
938 )
939 }
940
941 #[test]
942 fn merge_groups_long_last() {
943 check_last(
944 "std::foo::bar::Baz",
945 r"use std::foo::bar::Qux;",
946 r"use std::foo::bar::{Baz, Qux};",
947 )
948 }
949
950 #[test]
951 fn merge_groups_long_full_list() {
952 check_full(
953 "std::foo::bar::Baz",
954 r"use std::foo::bar::{Qux, Quux};",
955 r"use std::foo::bar::{Baz, Quux, Qux};",
956 )
957 }
958
959 #[test]
960 fn merge_groups_long_last_list() {
961 check_last(
962 "std::foo::bar::Baz",
963 r"use std::foo::bar::{Qux, Quux};",
964 r"use std::foo::bar::{Baz, Quux, Qux};",
965 )
966 }
967
968 #[test]
969 fn merge_groups_long_full_nested() {
970 check_full(
971 "std::foo::bar::Baz",
972 r"use std::foo::bar::{Qux, quux::{Fez, Fizz}};",
973 r"use std::foo::bar::{Baz, Qux, quux::{Fez, Fizz}};",
974 )
975 }
976
977 #[test]
978 fn merge_groups_long_last_nested() {
979 check_last(
980 "std::foo::bar::Baz",
981 r"use std::foo::bar::{Qux, quux::{Fez, Fizz}};",
982 r"use std::foo::bar::Baz;
983use std::foo::bar::{Qux, quux::{Fez, Fizz}};",
984 )
985 }
986
987 #[test]
988 fn merge_groups_full_nested_deep() {
989 check_full(
990 "std::foo::bar::quux::Baz",
991 r"use std::foo::bar::{Qux, quux::{Fez, Fizz}};",
992 r"use std::foo::bar::{Qux, quux::{Baz, Fez, Fizz}};",
993 )
994 }
995
996 #[test]
997 fn merge_groups_full_nested_long() {
998 check_full(
999 "std::foo::bar::Baz",
1000 r"use std::{foo::bar::Qux};",
1001 r"use std::{foo::bar::{Baz, Qux}};",
1002 );
1003 }
1004
1005 #[test]
1006 fn merge_groups_last_nested_long() {
1007 check_full(
1008 "std::foo::bar::Baz",
1009 r"use std::{foo::bar::Qux};",
1010 r"use std::{foo::bar::{Baz, Qux}};",
1011 );
1012 }
1013
1014 #[test]
1015 fn merge_groups_skip_pub() {
1016 check_full(
1017 "std::io",
1018 r"pub use std::fmt::{Result, Display};",
1019 r"pub use std::fmt::{Result, Display};
1020use std::io;",
1021 )
1022 }
1023
1024 #[test]
1025 fn merge_groups_skip_pub_crate() {
1026 check_full(
1027 "std::io",
1028 r"pub(crate) use std::fmt::{Result, Display};",
1029 r"pub(crate) use std::fmt::{Result, Display};
1030use std::io;",
1031 )
1032 }
1033
1034 #[test]
1035 #[ignore] // FIXME: Support this
1036 fn split_out_merge() {
1037 check_last(
1038 "std::fmt::Result",
1039 r"use std::{fmt, io};",
1040 r"use std::fmt::{self, Result};
1041use std::io;",
1042 )
1043 }
1044
1045 #[test]
1046 fn merge_into_module_import() {
1047 check_full(
1048 "std::fmt::Result",
1049 r"use std::{fmt, io};",
1050 r"use std::{fmt::{self, Result}, io};",
1051 )
1052 }
1053
1054 #[test]
1055 fn merge_groups_self() {
1056 check_full("std::fmt::Debug", r"use std::fmt;", r"use std::fmt::{self, Debug};")
1057 }
1058
1059 #[test]
1060 fn merge_mod_into_glob() {
1061 check_full(
1062 "token::TokenKind",
1063 r"use token::TokenKind::*;",
1064 r"use token::TokenKind::{*, self};",
1065 )
1066 // FIXME: have it emit `use token::TokenKind::{self, *}`?
1067 }
1068
1069 #[test]
1070 fn merge_self_glob() {
1071 check_full("self", r"use self::*;", r"use self::{*, self};")
1072 // FIXME: have it emit `use {self, *}`?
1073 }
1074
1075 #[test]
1076 fn merge_glob_nested() {
1077 check_full(
1078 "foo::bar::quux::Fez",
1079 r"use foo::bar::{Baz, quux::*};",
1080 r"use foo::bar::{Baz, quux::{self::*, Fez}};",
1081 )
1082 }
1083
1084 #[test]
1085 fn skip_merge_last_too_long() {
1086 check_last(
1087 "foo::bar",
1088 r"use foo::bar::baz::Qux;",
1089 r"use foo::bar;
1090use foo::bar::baz::Qux;",
1091 );
1092 }
1093
1094 #[test]
1095 fn skip_merge_last_too_long2() {
1096 check_last(
1097 "foo::bar::baz::Qux",
1098 r"use foo::bar;",
1099 r"use foo::bar;
1100use foo::bar::baz::Qux;",
1101 );
1102 }
1103
1104 #[test]
1105 fn insert_short_before_long() {
1106 check_none(
1107 "foo::bar",
1108 r"use foo::bar::baz::Qux;",
1109 r"use foo::bar;
1110use foo::bar::baz::Qux;",
1111 );
1112 }
1113
1114 #[test]
1115 fn merge_last_fail() {
1116 check_merge_only_fail(
1117 r"use foo::bar::{baz::{Qux, Fez}};",
1118 r"use foo::bar::{baaz::{Quux, Feez}};",
1119 MergeBehaviour::Last,
1120 );
1121 }
1122
1123 #[test]
1124 fn merge_last_fail1() {
1125 check_merge_only_fail(
1126 r"use foo::bar::{baz::{Qux, Fez}};",
1127 r"use foo::bar::baaz::{Quux, Feez};",
1128 MergeBehaviour::Last,
1129 );
1130 }
1131
1132 #[test]
1133 fn merge_last_fail2() {
1134 check_merge_only_fail(
1135 r"use foo::bar::baz::{Qux, Fez};",
1136 r"use foo::bar::{baaz::{Quux, Feez}};",
1137 MergeBehaviour::Last,
1138 );
1139 }
1140
1141 #[test]
1142 fn merge_last_fail3() {
1143 check_merge_only_fail(
1144 r"use foo::bar::baz::{Qux, Fez};",
1145 r"use foo::bar::baaz::{Quux, Feez};",
1146 MergeBehaviour::Last,
1147 );
1148 }
1149
1150 fn check(
1151 path: &str,
1152 ra_fixture_before: &str,
1153 ra_fixture_after: &str,
1154 mb: Option<MergeBehaviour>,
1155 module: bool,
1156 ) {
1157 let mut syntax = ast::SourceFile::parse(ra_fixture_before).tree().syntax().clone();
1158 if module {
1159 syntax = syntax.descendants().find_map(ast::Module::cast).unwrap().syntax().clone();
1160 }
1161 let file = super::ImportScope::from(syntax).unwrap();
1162 let path = ast::SourceFile::parse(&format!("use {};", path))
1163 .tree()
1164 .syntax()
1165 .descendants()
1166 .find_map(ast::Path::cast)
1167 .unwrap();
1168
1169 let rewriter = insert_use(&file, path, mb);
1170 let result = rewriter.rewrite(file.as_syntax_node()).to_string();
1171 assert_eq_text!(&result, ra_fixture_after);
1172 }
1173
1174 fn check_full(path: &str, ra_fixture_before: &str, ra_fixture_after: &str) {
1175 check(path, ra_fixture_before, ra_fixture_after, Some(MergeBehaviour::Full), false)
1176 }
1177
1178 fn check_last(path: &str, ra_fixture_before: &str, ra_fixture_after: &str) {
1179 check(path, ra_fixture_before, ra_fixture_after, Some(MergeBehaviour::Last), false)
1180 }
1181
1182 fn check_none(path: &str, ra_fixture_before: &str, ra_fixture_after: &str) {
1183 check(path, ra_fixture_before, ra_fixture_after, None, false)
1184 }
1185
1186 fn check_merge_only_fail(ra_fixture0: &str, ra_fixture1: &str, mb: MergeBehaviour) {
1187 let use0 = ast::SourceFile::parse(ra_fixture0)
1188 .tree()
1189 .syntax()
1190 .descendants()
1191 .find_map(ast::Use::cast)
1192 .unwrap();
1193
1194 let use1 = ast::SourceFile::parse(ra_fixture1)
1195 .tree()
1196 .syntax()
1197 .descendants()
1198 .find_map(ast::Use::cast)
1199 .unwrap();
1200
1201 let result = try_merge_imports(&use0, &use1, mb);
1202 assert_eq!(result.map(|u| u.to_string()), None);
1203 }
1204}
diff --git a/crates/ide_db/src/lib.rs b/crates/ide_db/src/lib.rs
index 05139a651..fceaa089a 100644
--- a/crates/ide_db/src/lib.rs
+++ b/crates/ide_db/src/lib.rs
@@ -13,6 +13,7 @@ pub mod source_change;
13pub mod ty_filter; 13pub mod ty_filter;
14pub mod traits; 14pub mod traits;
15pub mod call_info; 15pub mod call_info;
16pub mod helpers;
16 17
17use std::{fmt, sync::Arc}; 18use std::{fmt, sync::Arc};
18 19