aboutsummaryrefslogtreecommitdiff
path: root/crates/assists
diff options
context:
space:
mode:
authorbors[bot] <26634292+bors[bot]@users.noreply.github.com>2020-10-02 10:30:25 +0100
committerGitHub <[email protected]>2020-10-02 10:30:25 +0100
commit40a028c9a837f4f189b7db82cd4034536af87322 (patch)
tree6bf5fdbdef305be4122b2e8a0f8eabef2e6e37fc /crates/assists
parentc01cd6e3ed0763f8e773c34dc76db0e39396133d (diff)
parent95ea23cdef74aa8dc194d54db4d884df8ec3567d (diff)
Merge #6105
6105: Fix path comparison not comparing paths correctly with unequal lengths r=matklad a=Veykril ~~This PR includes the commit from #6102 there as I found a bug while writing that(so either merging this or both in order works) so I included a test there already which was just ignored.~~ This PR fixes that, basically inserting imports didn't consider path length for equality, so depending on the order it might insert the path before or after another import if they only differ in segment length. ~~Diff without the commit of #6102 https://github.com/rust-analyzer/rust-analyzer/commit/2d90d3937d71f9a00f3d44c15b20679215311637~~ Co-authored-by: Lukas Wirth <[email protected]>
Diffstat (limited to 'crates/assists')
-rw-r--r--crates/assists/src/utils/insert_use.rs133
1 files changed, 85 insertions, 48 deletions
diff --git a/crates/assists/src/utils/insert_use.rs b/crates/assists/src/utils/insert_use.rs
index 8dd4fe607..f6025c99a 100644
--- a/crates/assists/src/utils/insert_use.rs
+++ b/crates/assists/src/utils/insert_use.rs
@@ -4,13 +4,14 @@ use std::{
4 iter::{self, successors}, 4 iter::{self, successors},
5}; 5};
6 6
7use ast::{ 7use itertools::{EitherOrBoth, Itertools};
8 edit::{AstNodeEdit, IndentLevel},
9 PathSegmentKind, VisibilityOwner,
10};
11use syntax::{ 8use syntax::{
12 algo, 9 algo,
13 ast::{self, make, AstNode}, 10 ast::{
11 self,
12 edit::{AstNodeEdit, IndentLevel},
13 make, AstNode, PathSegmentKind, VisibilityOwner,
14 },
14 InsertPosition, SyntaxElement, SyntaxNode, 15 InsertPosition, SyntaxElement, SyntaxNode,
15}; 16};
16 17
@@ -193,13 +194,13 @@ fn recursive_merge(
193 false => None, 194 false => None,
194 }) 195 })
195 .collect::<Option<Vec<_>>>()?; 196 .collect::<Option<Vec<_>>>()?;
196 use_trees.sort_unstable_by(|a, b| path_cmp_opt(a.path(), b.path())); 197 use_trees.sort_unstable_by(|a, b| path_cmp_for_sort(a.path(), b.path()));
197 for rhs_t in rhs.use_tree_list().into_iter().flat_map(|list| list.use_trees()) { 198 for rhs_t in rhs.use_tree_list().into_iter().flat_map(|list| list.use_trees()) {
198 if !merge.is_tree_allowed(&rhs_t) { 199 if !merge.is_tree_allowed(&rhs_t) {
199 return None; 200 return None;
200 } 201 }
201 let rhs_path = rhs_t.path(); 202 let rhs_path = rhs_t.path();
202 match use_trees.binary_search_by(|p| path_cmp_opt(p.path(), rhs_path.clone())) { 203 match use_trees.binary_search_by(|p| path_cmp_bin_search(p.path(), rhs_path.clone())) {
203 Ok(idx) => { 204 Ok(idx) => {
204 let lhs_t = &mut use_trees[idx]; 205 let lhs_t = &mut use_trees[idx];
205 let lhs_path = lhs_t.path()?; 206 let lhs_path = lhs_t.path()?;
@@ -307,39 +308,77 @@ fn path_len(path: ast::Path) -> usize {
307 308
308/// Orders paths in the following way: 309/// Orders paths in the following way:
309/// the sole self token comes first, after that come uppercase identifiers, then lowercase identifiers 310/// the sole self token comes first, after that come uppercase identifiers, then lowercase identifiers
310// FIXME: rustfmt sort lowercase idents before uppercase, in general we want to have the same ordering rustfmt has 311// FIXME: rustfmt sorts lowercase idents before uppercase, in general we want to have the same ordering rustfmt has
311// which is `self` and `super` first, then identifier imports with lowercase ones first, then glob imports and at last list imports. 312// which is `self` and `super` first, then identifier imports with lowercase ones first, then glob imports and at last list imports.
312// Example foo::{self, foo, baz, Baz, Qux, *, {Bar}} 313// Example foo::{self, foo, baz, Baz, Qux, *, {Bar}}
313fn path_cmp(a: &ast::Path, b: &ast::Path) -> Ordering { 314fn path_cmp_for_sort(a: Option<ast::Path>, b: Option<ast::Path>) -> Ordering {
314 match (path_is_self(a), path_is_self(b)) { 315 match (a, b) {
315 (true, true) => Ordering::Equal, 316 (None, None) => Ordering::Equal,
316 (true, false) => Ordering::Less, 317 (None, Some(_)) => Ordering::Less,
317 (false, true) => Ordering::Greater, 318 (Some(_), None) => Ordering::Greater,
318 (false, false) => { 319 (Some(ref a), Some(ref b)) => match (path_is_self(a), path_is_self(b)) {
319 let a = segment_iter(a); 320 (true, true) => Ordering::Equal,
320 let b = segment_iter(b); 321 (true, false) => Ordering::Less,
321 // cmp_by would be useful for us here but that is currently unstable 322 (false, true) => Ordering::Greater,
322 // cmp doesnt work due the lifetimes on text's return type 323 (false, false) => path_cmp_short(a, b),
323 a.zip(b) 324 },
324 .flat_map(|(seg, seg2)| seg.name_ref().zip(seg2.name_ref()))
325 .find_map(|(a, b)| match a.text().cmp(b.text()) {
326 ord @ Ordering::Greater | ord @ Ordering::Less => Some(ord),
327 Ordering::Equal => None,
328 })
329 .unwrap_or(Ordering::Equal)
330 }
331 } 325 }
332} 326}
333 327
334fn path_cmp_opt(a: Option<ast::Path>, b: Option<ast::Path>) -> Ordering { 328/// Path comparison func for binary searching for merging.
335 match (a, b) { 329fn path_cmp_bin_search(lhs: Option<ast::Path>, rhs: Option<ast::Path>) -> Ordering {
330 match (lhs, rhs) {
336 (None, None) => Ordering::Equal, 331 (None, None) => Ordering::Equal,
337 (None, Some(_)) => Ordering::Less, 332 (None, Some(_)) => Ordering::Less,
338 (Some(_), None) => Ordering::Greater, 333 (Some(_), None) => Ordering::Greater,
339 (Some(a), Some(b)) => path_cmp(&a, &b), 334 (Some(ref a), Some(ref b)) => path_cmp_short(a, b),
340 } 335 }
341} 336}
342 337
338/// Short circuiting comparison, if both paths are equal until one of them ends they are considered
339/// equal
340fn path_cmp_short(a: &ast::Path, b: &ast::Path) -> Ordering {
341 let a = segment_iter(a);
342 let b = segment_iter(b);
343 // cmp_by would be useful for us here but that is currently unstable
344 // cmp doesnt work due the lifetimes on text's return type
345 a.zip(b)
346 .find_map(|(a, b)| match path_segment_cmp(&a, &b) {
347 Ordering::Equal => None,
348 ord => Some(ord),
349 })
350 .unwrap_or(Ordering::Equal)
351}
352
353/// Compares to paths, if one ends earlier than the other the has_tl parameters decide which is
354/// greater as a a path that has a tree list should be greater, while one that just ends without
355/// a tree list should be considered less.
356fn use_tree_path_cmp(a: &ast::Path, a_has_tl: bool, b: &ast::Path, b_has_tl: bool) -> Ordering {
357 let a_segments = segment_iter(a);
358 let b_segments = segment_iter(b);
359 // cmp_by would be useful for us here but that is currently unstable
360 // cmp doesnt work due the lifetimes on text's return type
361 a_segments
362 .zip_longest(b_segments)
363 .find_map(|zipped| match zipped {
364 EitherOrBoth::Both(ref a, ref b) => match path_segment_cmp(a, b) {
365 Ordering::Equal => None,
366 ord => Some(ord),
367 },
368 EitherOrBoth::Left(_) if !b_has_tl => Some(Ordering::Greater),
369 EitherOrBoth::Left(_) => Some(Ordering::Less),
370 EitherOrBoth::Right(_) if !a_has_tl => Some(Ordering::Less),
371 EitherOrBoth::Right(_) => Some(Ordering::Greater),
372 })
373 .unwrap_or(Ordering::Equal)
374}
375
376fn path_segment_cmp(a: &ast::PathSegment, b: &ast::PathSegment) -> Ordering {
377 let a = a.name_ref();
378 let b = b.name_ref();
379 a.as_ref().map(ast::NameRef::text).cmp(&b.as_ref().map(ast::NameRef::text))
380}
381
343/// What type of merges are allowed. 382/// What type of merges are allowed.
344#[derive(Copy, Clone, Debug, PartialEq, Eq)] 383#[derive(Copy, Clone, Debug, PartialEq, Eq)]
345pub enum MergeBehaviour { 384pub enum MergeBehaviour {
@@ -389,7 +428,6 @@ impl ImportGroup {
389 PathSegmentKind::Name(name) => match name.text().as_str() { 428 PathSegmentKind::Name(name) => match name.text().as_str() {
390 "std" => ImportGroup::Std, 429 "std" => ImportGroup::Std,
391 "core" => ImportGroup::Std, 430 "core" => ImportGroup::Std,
392 // FIXME: can be ThisModule as well
393 _ => ImportGroup::ExternCrate, 431 _ => ImportGroup::ExternCrate,
394 }, 432 },
395 PathSegmentKind::Type { .. } => unreachable!(), 433 PathSegmentKind::Type { .. } => unreachable!(),
@@ -415,30 +453,30 @@ fn find_insert_position(
415 .as_syntax_node() 453 .as_syntax_node()
416 .children() 454 .children()
417 .filter_map(|node| ast::Use::cast(node.clone()).zip(Some(node))) 455 .filter_map(|node| ast::Use::cast(node.clone()).zip(Some(node)))
418 .flat_map(|(use_, node)| use_.use_tree().and_then(|tree| tree.path()).zip(Some(node))); 456 .flat_map(|(use_, node)| {
457 let tree = use_.use_tree()?;
458 let path = tree.path()?;
459 let has_tl = tree.use_tree_list().is_some();
460 Some((path, has_tl, node))
461 });
419 // Iterator that discards anything thats not in the required grouping 462 // Iterator that discards anything thats not in the required grouping
420 // This implementation allows the user to rearrange their import groups as this only takes the first group that fits 463 // This implementation allows the user to rearrange their import groups as this only takes the first group that fits
421 let group_iter = path_node_iter 464 let group_iter = path_node_iter
422 .clone() 465 .clone()
423 .skip_while(|(path, _)| ImportGroup::new(path) != group) 466 .skip_while(|(path, ..)| ImportGroup::new(path) != group)
424 .take_while(|(path, _)| ImportGroup::new(path) == group); 467 .take_while(|(path, ..)| ImportGroup::new(path) == group);
425 468
426 let segments = segment_iter(&insert_path);
427 // 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 469 // 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
428 let mut last = None; 470 let mut last = None;
429 // find the element that would come directly after our new import 471 // find the element that would come directly after our new import
430 let post_insert = 472 let post_insert = group_iter.inspect(|(.., node)| last = Some(node.clone())).find(
431 group_iter.inspect(|(_, node)| last = Some(node.clone())).find(|(path, _)| { 473 |&(ref path, has_tl, _)| {
432 let check_segments = segment_iter(&path); 474 use_tree_path_cmp(&insert_path, false, path, has_tl) != Ordering::Greater
433 segments 475 },
434 .clone() 476 );
435 .zip(check_segments)
436 .flat_map(|(seg, seg2)| seg.name_ref().zip(seg2.name_ref()))
437 .all(|(l, r)| l.text() <= r.text())
438 });
439 match post_insert { 477 match post_insert {
440 // insert our import before that element 478 // insert our import before that element
441 Some((_, node)) => (InsertPosition::Before(node.into()), AddBlankLine::After), 479 Some((.., node)) => (InsertPosition::Before(node.into()), AddBlankLine::After),
442 // there is no element after our new import, so append it to the end of the group 480 // there is no element after our new import, so append it to the end of the group
443 None => match last { 481 None => match last {
444 Some(node) => (InsertPosition::After(node.into()), AddBlankLine::Before), 482 Some(node) => (InsertPosition::After(node.into()), AddBlankLine::Before),
@@ -448,10 +486,10 @@ fn find_insert_position(
448 let mut last = None; 486 let mut last = None;
449 // find the group that comes after where we want to insert 487 // find the group that comes after where we want to insert
450 let post_group = path_node_iter 488 let post_group = path_node_iter
451 .inspect(|(_, node)| last = Some(node.clone())) 489 .inspect(|(.., node)| last = Some(node.clone()))
452 .find(|(p, _)| ImportGroup::new(p) > group); 490 .find(|(p, ..)| ImportGroup::new(p) > group);
453 match post_group { 491 match post_group {
454 Some((_, node)) => { 492 Some((.., node)) => {
455 (InsertPosition::Before(node.into()), AddBlankLine::AfterTwice) 493 (InsertPosition::Before(node.into()), AddBlankLine::AfterTwice)
456 } 494 }
457 // there is no such group, so append after the last one 495 // there is no such group, so append after the last one
@@ -844,7 +882,6 @@ use foo::bar::baz::Qux;",
844 } 882 }
845 883
846 #[test] 884 #[test]
847 #[ignore] // FIXME: Order changes when switching lhs and rhs
848 fn skip_merge_last_too_long2() { 885 fn skip_merge_last_too_long2() {
849 check_last( 886 check_last(
850 "foo::bar::baz::Qux", 887 "foo::bar::baz::Qux",