diff options
Diffstat (limited to 'crates/ide_db/src/helpers/merge_imports.rs')
-rw-r--r-- | crates/ide_db/src/helpers/merge_imports.rs | 309 |
1 files changed, 309 insertions, 0 deletions
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. | ||
2 | use std::cmp::Ordering; | ||
3 | |||
4 | use itertools::{EitherOrBoth, Itertools}; | ||
5 | use 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)] | ||
11 | pub 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 | |||
18 | impl 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 | |||
31 | pub 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 | |||
50 | pub 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. | ||
72 | fn 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. | ||
176 | fn 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}} | ||
202 | fn 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. | ||
217 | fn 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 | ||
231 | fn 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. | ||
247 | pub(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 | |||
272 | fn 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 | |||
284 | fn 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 | |||
294 | fn 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 | |||
303 | fn path_is_self(path: &ast::Path) -> bool { | ||
304 | path.segment().and_then(|seg| seg.self_token()).is_some() && path.qualifier().is_none() | ||
305 | } | ||
306 | |||
307 | fn path_len(path: ast::Path) -> usize { | ||
308 | path.segments().count() | ||
309 | } | ||