From 050c69c19dd8004c8dfc92dbff86a42fac022e6e Mon Sep 17 00:00:00 2001 From: Lukas Wirth Date: Sat, 24 Apr 2021 13:31:16 +0200 Subject: Split out merge_imports module from helpers::insert_use --- crates/ide_db/src/helpers/insert_use.rs | 324 +---------------------------- crates/ide_db/src/helpers/merge_imports.rs | 309 +++++++++++++++++++++++++++ 2 files changed, 316 insertions(+), 317 deletions(-) create mode 100644 crates/ide_db/src/helpers/merge_imports.rs (limited to 'crates/ide_db/src/helpers') 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 @@ //! Handle syntactic aspects of inserting a new `use`. -use std::{cmp::Ordering, iter::successors}; +use std::cmp::Ordering; use hir::Semantics; -use itertools::{EitherOrBoth, Itertools}; use syntax::{ algo, - ast::{self, edit::AstNodeEdit, make, AstNode, AttrsOwner, PathSegmentKind, VisibilityOwner}, + ast::{self, make, AstNode, PathSegmentKind}, ted, AstToken, Direction, NodeOrToken, SyntaxNode, SyntaxToken, }; -use crate::RootDatabase; +use crate::{ + helpers::merge_imports::{try_merge_imports, use_tree_path_cmp, MergeBehavior}, + RootDatabase, +}; pub use hir::PrefixKind; @@ -85,318 +87,6 @@ pub fn insert_use<'a>(scope: &ImportScope, path: ast::Path, cfg: InsertUseConfig insert_use_(scope, path, cfg.group, use_item); } -fn eq_visibility(vis0: Option, vis1: Option) -> bool { - match (vis0, vis1) { - (None, None) => true, - // FIXME: Don't use the string representation to check for equality - // spaces inside of the node would break this comparison - (Some(vis0), Some(vis1)) => vis0.to_string() == vis1.to_string(), - _ => false, - } -} - -fn eq_attrs( - attrs0: impl Iterator, - attrs1: impl Iterator, -) -> bool { - let attrs0 = attrs0.map(|attr| attr.to_string()); - let attrs1 = attrs1.map(|attr| attr.to_string()); - attrs0.eq(attrs1) -} - -pub fn try_merge_imports( - lhs: &ast::Use, - rhs: &ast::Use, - merge_behavior: MergeBehavior, -) -> Option { - // don't merge imports with different visibilities - if !eq_visibility(lhs.visibility(), rhs.visibility()) { - return None; - } - if !eq_attrs(lhs.attrs(), rhs.attrs()) { - return None; - } - - let lhs_tree = lhs.use_tree()?; - let rhs_tree = rhs.use_tree()?; - let merged = try_merge_trees(&lhs_tree, &rhs_tree, merge_behavior)?; - Some(lhs.with_use_tree(merged).clone_for_update()) -} - -pub fn try_merge_trees( - lhs: &ast::UseTree, - rhs: &ast::UseTree, - merge: MergeBehavior, -) -> Option { - let lhs_path = lhs.path()?; - let rhs_path = rhs.path()?; - - let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?; - let (lhs, rhs) = if is_simple_path(lhs) - && is_simple_path(rhs) - && lhs_path == lhs_prefix - && rhs_path == rhs_prefix - { - (lhs.clone(), rhs.clone()) - } else { - (lhs.split_prefix(&lhs_prefix), rhs.split_prefix(&rhs_prefix)) - }; - recursive_merge(&lhs, &rhs, merge) -} - -/// Recursively "zips" together lhs and rhs. -fn recursive_merge( - lhs: &ast::UseTree, - rhs: &ast::UseTree, - merge: MergeBehavior, -) -> Option { - let mut use_trees = lhs - .use_tree_list() - .into_iter() - .flat_map(|list| list.use_trees()) - // we use Option here to early return from this function(this is not the same as a `filter` op) - .map(|tree| match merge.is_tree_allowed(&tree) { - true => Some(tree), - false => None, - }) - .collect::>>()?; - use_trees.sort_unstable_by(|a, b| path_cmp_for_sort(a.path(), b.path())); - for rhs_t in rhs.use_tree_list().into_iter().flat_map(|list| list.use_trees()) { - if !merge.is_tree_allowed(&rhs_t) { - return None; - } - let rhs_path = rhs_t.path(); - match use_trees.binary_search_by(|lhs_t| { - let (lhs_t, rhs_t) = match lhs_t - .path() - .zip(rhs_path.clone()) - .and_then(|(lhs, rhs)| common_prefix(&lhs, &rhs)) - { - Some((lhs_p, rhs_p)) => (lhs_t.split_prefix(&lhs_p), rhs_t.split_prefix(&rhs_p)), - None => (lhs_t.clone(), rhs_t.clone()), - }; - - path_cmp_bin_search(lhs_t.path(), rhs_t.path()) - }) { - Ok(idx) => { - let lhs_t = &mut use_trees[idx]; - let lhs_path = lhs_t.path()?; - let rhs_path = rhs_path?; - let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?; - if lhs_prefix == lhs_path && rhs_prefix == rhs_path { - let tree_is_self = |tree: ast::UseTree| { - tree.path().as_ref().map(path_is_self).unwrap_or(false) - }; - // check if only one of the two trees has a tree list, and whether that then contains `self` or not. - // 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` - let tree_contains_self = |tree: &ast::UseTree| { - tree.use_tree_list() - .map(|tree_list| tree_list.use_trees().any(tree_is_self)) - .unwrap_or(false) - }; - match (tree_contains_self(&lhs_t), tree_contains_self(&rhs_t)) { - (true, false) => continue, - (false, true) => { - *lhs_t = rhs_t; - continue; - } - _ => (), - } - - // glob imports arent part of the use-tree lists so we need to special handle them here as well - // this special handling is only required for when we merge a module import into a glob import of said module - // see the `merge_self_glob` or `merge_mod_into_glob` tests - if lhs_t.star_token().is_some() || rhs_t.star_token().is_some() { - *lhs_t = make::use_tree( - make::path_unqualified(make::path_segment_self()), - None, - None, - false, - ); - use_trees.insert(idx, make::glob_use_tree()); - continue; - } - - if lhs_t.use_tree_list().is_none() && rhs_t.use_tree_list().is_none() { - continue; - } - } - let lhs = lhs_t.split_prefix(&lhs_prefix); - let rhs = rhs_t.split_prefix(&rhs_prefix); - match recursive_merge(&lhs, &rhs, merge) { - Some(use_tree) => use_trees[idx] = use_tree, - None => return None, - } - } - Err(_) - if merge == MergeBehavior::Last - && use_trees.len() > 0 - && rhs_t.use_tree_list().is_some() => - { - return None - } - Err(idx) => { - use_trees.insert(idx, rhs_t); - } - } - } - - Some(if let Some(old) = lhs.use_tree_list() { - lhs.replace_descendant(old, make::use_tree_list(use_trees)).clone_for_update() - } else { - lhs.clone() - }) -} - -/// Traverses both paths until they differ, returning the common prefix of both. -fn common_prefix(lhs: &ast::Path, rhs: &ast::Path) -> Option<(ast::Path, ast::Path)> { - let mut res = None; - let mut lhs_curr = first_path(&lhs); - let mut rhs_curr = first_path(&rhs); - loop { - match (lhs_curr.segment(), rhs_curr.segment()) { - (Some(lhs), Some(rhs)) if lhs.syntax().text() == rhs.syntax().text() => (), - _ => break res, - } - res = Some((lhs_curr.clone(), rhs_curr.clone())); - - match lhs_curr.parent_path().zip(rhs_curr.parent_path()) { - Some((lhs, rhs)) => { - lhs_curr = lhs; - rhs_curr = rhs; - } - _ => break res, - } - } -} - -fn is_simple_path(use_tree: &ast::UseTree) -> bool { - use_tree.use_tree_list().is_none() && use_tree.star_token().is_none() -} - -fn path_is_self(path: &ast::Path) -> bool { - path.segment().and_then(|seg| seg.self_token()).is_some() && path.qualifier().is_none() -} - -#[inline] -fn first_segment(path: &ast::Path) -> Option { - first_path(path).segment() -} - -fn first_path(path: &ast::Path) -> ast::Path { - successors(Some(path.clone()), ast::Path::qualifier).last().unwrap() -} - -fn segment_iter(path: &ast::Path) -> impl Iterator + Clone { - // cant make use of SyntaxNode::siblings, because the returned Iterator is not clone - successors(first_segment(path), |p| p.parent_path().parent_path().and_then(|p| p.segment())) -} - -fn path_len(path: ast::Path) -> usize { - segment_iter(&path).count() -} - -/// Orders paths in the following way: -/// the sole self token comes first, after that come uppercase identifiers, then lowercase identifiers -// FIXME: rustfmt sorts lowercase idents before uppercase, in general we want to have the same ordering rustfmt has -// which is `self` and `super` first, then identifier imports with lowercase ones first, then glob imports and at last list imports. -// Example foo::{self, foo, baz, Baz, Qux, *, {Bar}} -fn path_cmp_for_sort(a: Option, b: Option) -> Ordering { - match (a, b) { - (None, None) => Ordering::Equal, - (None, Some(_)) => Ordering::Less, - (Some(_), None) => Ordering::Greater, - (Some(ref a), Some(ref b)) => match (path_is_self(a), path_is_self(b)) { - (true, true) => Ordering::Equal, - (true, false) => Ordering::Less, - (false, true) => Ordering::Greater, - (false, false) => path_cmp_short(a, b), - }, - } -} - -/// Path comparison func for binary searching for merging. -fn path_cmp_bin_search(lhs: Option, rhs: Option) -> Ordering { - match (lhs.as_ref().and_then(first_segment), rhs.as_ref().and_then(first_segment)) { - (None, None) => Ordering::Equal, - (None, Some(_)) => Ordering::Less, - (Some(_), None) => Ordering::Greater, - (Some(ref a), Some(ref b)) => path_segment_cmp(a, b), - } -} - -/// Short circuiting comparison, if both paths are equal until one of them ends they are considered -/// equal -fn path_cmp_short(a: &ast::Path, b: &ast::Path) -> Ordering { - let a = segment_iter(a); - let b = segment_iter(b); - // cmp_by would be useful for us here but that is currently unstable - // cmp doesnt work due the lifetimes on text's return type - a.zip(b) - .find_map(|(a, b)| match path_segment_cmp(&a, &b) { - Ordering::Equal => None, - ord => Some(ord), - }) - .unwrap_or(Ordering::Equal) -} - -/// Compares to paths, if one ends earlier than the other the has_tl parameters decide which is -/// greater as a a path that has a tree list should be greater, while one that just ends without -/// a tree list should be considered less. -fn use_tree_path_cmp(a: &ast::Path, a_has_tl: bool, b: &ast::Path, b_has_tl: bool) -> Ordering { - let a_segments = segment_iter(a); - let b_segments = segment_iter(b); - // cmp_by would be useful for us here but that is currently unstable - // cmp doesnt work due the lifetimes on text's return type - a_segments - .zip_longest(b_segments) - .find_map(|zipped| match zipped { - EitherOrBoth::Both(ref a, ref b) => match path_segment_cmp(a, b) { - Ordering::Equal => None, - ord => Some(ord), - }, - EitherOrBoth::Left(_) if !b_has_tl => Some(Ordering::Greater), - EitherOrBoth::Left(_) => Some(Ordering::Less), - EitherOrBoth::Right(_) if !a_has_tl => Some(Ordering::Less), - EitherOrBoth::Right(_) => Some(Ordering::Greater), - }) - .unwrap_or(Ordering::Equal) -} - -fn path_segment_cmp(a: &ast::PathSegment, b: &ast::PathSegment) -> Ordering { - let a = a.kind().and_then(|kind| match kind { - PathSegmentKind::Name(name_ref) => Some(name_ref), - _ => None, - }); - let b = b.kind().and_then(|kind| match kind { - PathSegmentKind::Name(name_ref) => Some(name_ref), - _ => None, - }); - a.as_ref().map(ast::NameRef::text).cmp(&b.as_ref().map(ast::NameRef::text)) -} - -/// What type of merges are allowed. -#[derive(Copy, Clone, Debug, PartialEq, Eq)] -pub enum MergeBehavior { - /// Merge everything together creating deeply nested imports. - Full, - /// Only merge the last import level, doesn't allow import nesting. - Last, -} - -impl MergeBehavior { - #[inline] - fn is_tree_allowed(&self, tree: &ast::UseTree) -> bool { - match self { - MergeBehavior::Full => true, - // only simple single segment paths are allowed - MergeBehavior::Last => { - tree.use_tree_list().is_none() && tree.path().map(path_len) <= Some(1) - } - } - } -} - #[derive(Eq, PartialEq, PartialOrd, Ord)] enum ImportGroup { // the order here defines the order of new group inserts @@ -411,7 +101,7 @@ impl ImportGroup { fn new(path: &ast::Path) -> ImportGroup { let default = ImportGroup::ExternCrate; - let first_segment = match first_segment(path) { + let first_segment = match path.first_segment() { Some(it) => it, None => return default, }; 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 @@ +//! Handle syntactic aspects of merging UseTrees. +use std::cmp::Ordering; + +use itertools::{EitherOrBoth, Itertools}; +use syntax::ast::{ + self, edit::AstNodeEdit, make, AstNode, AttrsOwner, PathSegmentKind, VisibilityOwner, +}; + +/// What type of merges are allowed. +#[derive(Copy, Clone, Debug, PartialEq, Eq)] +pub enum MergeBehavior { + /// Merge everything together creating deeply nested imports. + Full, + /// Only merge the last import level, doesn't allow import nesting. + Last, +} + +impl MergeBehavior { + #[inline] + fn is_tree_allowed(&self, tree: &ast::UseTree) -> bool { + match self { + MergeBehavior::Full => true, + // only simple single segment paths are allowed + MergeBehavior::Last => { + tree.use_tree_list().is_none() && tree.path().map(path_len) <= Some(1) + } + } + } +} + +pub fn try_merge_imports( + lhs: &ast::Use, + rhs: &ast::Use, + merge_behavior: MergeBehavior, +) -> Option { + // don't merge imports with different visibilities + if !eq_visibility(lhs.visibility(), rhs.visibility()) { + return None; + } + if !eq_attrs(lhs.attrs(), rhs.attrs()) { + return None; + } + + let lhs_tree = lhs.use_tree()?; + let rhs_tree = rhs.use_tree()?; + let merged = try_merge_trees(&lhs_tree, &rhs_tree, merge_behavior)?; + Some(lhs.with_use_tree(merged).clone_for_update()) +} + +pub fn try_merge_trees( + lhs: &ast::UseTree, + rhs: &ast::UseTree, + merge: MergeBehavior, +) -> Option { + let lhs_path = lhs.path()?; + let rhs_path = rhs.path()?; + + let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?; + let (lhs, rhs) = if lhs.is_simple_path() + && rhs.is_simple_path() + && lhs_path == lhs_prefix + && rhs_path == rhs_prefix + { + (lhs.clone(), rhs.clone()) + } else { + (lhs.split_prefix(&lhs_prefix), rhs.split_prefix(&rhs_prefix)) + }; + recursive_merge(&lhs, &rhs, merge) +} + +/// Recursively "zips" together lhs and rhs. +fn recursive_merge( + lhs: &ast::UseTree, + rhs: &ast::UseTree, + merge: MergeBehavior, +) -> Option { + let mut use_trees = lhs + .use_tree_list() + .into_iter() + .flat_map(|list| list.use_trees()) + // we use Option here to early return from this function(this is not the same as a `filter` op) + .map(|tree| match merge.is_tree_allowed(&tree) { + true => Some(tree), + false => None, + }) + .collect::>>()?; + use_trees.sort_unstable_by(|a, b| path_cmp_for_sort(a.path(), b.path())); + for rhs_t in rhs.use_tree_list().into_iter().flat_map(|list| list.use_trees()) { + if !merge.is_tree_allowed(&rhs_t) { + return None; + } + let rhs_path = rhs_t.path(); + match use_trees.binary_search_by(|lhs_t| { + let (lhs_t, rhs_t) = match lhs_t + .path() + .zip(rhs_path.clone()) + .and_then(|(lhs, rhs)| common_prefix(&lhs, &rhs)) + { + Some((lhs_p, rhs_p)) => (lhs_t.split_prefix(&lhs_p), rhs_t.split_prefix(&rhs_p)), + None => (lhs_t.clone(), rhs_t.clone()), + }; + + path_cmp_bin_search(lhs_t.path(), rhs_t.path()) + }) { + Ok(idx) => { + let lhs_t = &mut use_trees[idx]; + let lhs_path = lhs_t.path()?; + let rhs_path = rhs_path?; + let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?; + if lhs_prefix == lhs_path && rhs_prefix == rhs_path { + let tree_is_self = |tree: ast::UseTree| { + tree.path().as_ref().map(path_is_self).unwrap_or(false) + }; + // check if only one of the two trees has a tree list, and whether that then contains `self` or not. + // 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` + let tree_contains_self = |tree: &ast::UseTree| { + tree.use_tree_list() + .map(|tree_list| tree_list.use_trees().any(tree_is_self)) + .unwrap_or(false) + }; + match (tree_contains_self(&lhs_t), tree_contains_self(&rhs_t)) { + (true, false) => continue, + (false, true) => { + *lhs_t = rhs_t; + continue; + } + _ => (), + } + + // glob imports arent part of the use-tree lists so we need to special handle them here as well + // this special handling is only required for when we merge a module import into a glob import of said module + // see the `merge_self_glob` or `merge_mod_into_glob` tests + if lhs_t.star_token().is_some() || rhs_t.star_token().is_some() { + *lhs_t = make::use_tree( + make::path_unqualified(make::path_segment_self()), + None, + None, + false, + ); + use_trees.insert(idx, make::glob_use_tree()); + continue; + } + + if lhs_t.use_tree_list().is_none() && rhs_t.use_tree_list().is_none() { + continue; + } + } + let lhs = lhs_t.split_prefix(&lhs_prefix); + let rhs = rhs_t.split_prefix(&rhs_prefix); + match recursive_merge(&lhs, &rhs, merge) { + Some(use_tree) => use_trees[idx] = use_tree, + None => return None, + } + } + Err(_) + if merge == MergeBehavior::Last + && use_trees.len() > 0 + && rhs_t.use_tree_list().is_some() => + { + return None + } + Err(idx) => { + use_trees.insert(idx, rhs_t); + } + } + } + + Some(if let Some(old) = lhs.use_tree_list() { + lhs.replace_descendant(old, make::use_tree_list(use_trees)).clone_for_update() + } else { + lhs.clone() + }) +} + +/// Traverses both paths until they differ, returning the common prefix of both. +fn common_prefix(lhs: &ast::Path, rhs: &ast::Path) -> Option<(ast::Path, ast::Path)> { + let mut res = None; + let mut lhs_curr = lhs.first_qualifier_or_self(); + let mut rhs_curr = rhs.first_qualifier_or_self(); + loop { + match (lhs_curr.segment(), rhs_curr.segment()) { + (Some(lhs), Some(rhs)) if lhs.syntax().text() == rhs.syntax().text() => (), + _ => break res, + } + res = Some((lhs_curr.clone(), rhs_curr.clone())); + + match lhs_curr.parent_path().zip(rhs_curr.parent_path()) { + Some((lhs, rhs)) => { + lhs_curr = lhs; + rhs_curr = rhs; + } + _ => break res, + } + } +} + +/// Orders paths in the following way: +/// the sole self token comes first, after that come uppercase identifiers, then lowercase identifiers +// FIXME: rustfmt sorts lowercase idents before uppercase, in general we want to have the same ordering rustfmt has +// which is `self` and `super` first, then identifier imports with lowercase ones first, then glob imports and at last list imports. +// Example foo::{self, foo, baz, Baz, Qux, *, {Bar}} +fn path_cmp_for_sort(a: Option, b: Option) -> Ordering { + match (a, b) { + (None, None) => Ordering::Equal, + (None, Some(_)) => Ordering::Less, + (Some(_), None) => Ordering::Greater, + (Some(ref a), Some(ref b)) => match (path_is_self(a), path_is_self(b)) { + (true, true) => Ordering::Equal, + (true, false) => Ordering::Less, + (false, true) => Ordering::Greater, + (false, false) => path_cmp_short(a, b), + }, + } +} + +/// Path comparison func for binary searching for merging. +fn path_cmp_bin_search(lhs: Option, rhs: Option) -> Ordering { + match ( + lhs.as_ref().and_then(ast::Path::first_segment), + rhs.as_ref().and_then(ast::Path::first_segment), + ) { + (None, None) => Ordering::Equal, + (None, Some(_)) => Ordering::Less, + (Some(_), None) => Ordering::Greater, + (Some(ref a), Some(ref b)) => path_segment_cmp(a, b), + } +} + +/// Short circuiting comparison, if both paths are equal until one of them ends they are considered +/// equal +fn path_cmp_short(a: &ast::Path, b: &ast::Path) -> Ordering { + let a = a.segments(); + let b = b.segments(); + // cmp_by would be useful for us here but that is currently unstable + // cmp doesn't work due the lifetimes on text's return type + a.zip(b) + .find_map(|(a, b)| match path_segment_cmp(&a, &b) { + Ordering::Equal => None, + ord => Some(ord), + }) + .unwrap_or(Ordering::Equal) +} + +/// Compares two paths, if one ends earlier than the other the has_tl parameters decide which is +/// greater as a a path that has a tree list should be greater, while one that just ends without +/// a tree list should be considered less. +pub(super) fn use_tree_path_cmp( + a: &ast::Path, + a_has_tl: bool, + b: &ast::Path, + b_has_tl: bool, +) -> Ordering { + let a_segments = a.segments(); + let b_segments = b.segments(); + // cmp_by would be useful for us here but that is currently unstable + // cmp doesn't work due the lifetimes on text's return type + a_segments + .zip_longest(b_segments) + .find_map(|zipped| match zipped { + EitherOrBoth::Both(ref a, ref b) => match path_segment_cmp(a, b) { + Ordering::Equal => None, + ord => Some(ord), + }, + EitherOrBoth::Left(_) if !b_has_tl => Some(Ordering::Greater), + EitherOrBoth::Left(_) => Some(Ordering::Less), + EitherOrBoth::Right(_) if !a_has_tl => Some(Ordering::Less), + EitherOrBoth::Right(_) => Some(Ordering::Greater), + }) + .unwrap_or(Ordering::Equal) +} + +fn path_segment_cmp(a: &ast::PathSegment, b: &ast::PathSegment) -> Ordering { + let a = a.kind().and_then(|kind| match kind { + PathSegmentKind::Name(name_ref) => Some(name_ref), + _ => None, + }); + let b = b.kind().and_then(|kind| match kind { + PathSegmentKind::Name(name_ref) => Some(name_ref), + _ => None, + }); + a.as_ref().map(ast::NameRef::text).cmp(&b.as_ref().map(ast::NameRef::text)) +} + +fn eq_visibility(vis0: Option, vis1: Option) -> bool { + match (vis0, vis1) { + (None, None) => true, + // FIXME: Don't use the string representation to check for equality + // spaces inside of the node would break this comparison + (Some(vis0), Some(vis1)) => vis0.to_string() == vis1.to_string(), + _ => false, + } +} + +fn eq_attrs( + attrs0: impl Iterator, + attrs1: impl Iterator, +) -> bool { + let attrs0 = attrs0.map(|attr| attr.to_string()); + let attrs1 = attrs1.map(|attr| attr.to_string()); + attrs0.eq(attrs1) +} + +fn path_is_self(path: &ast::Path) -> bool { + path.segment().and_then(|seg| seg.self_token()).is_some() && path.qualifier().is_none() +} + +fn path_len(path: ast::Path) -> usize { + path.segments().count() +} -- cgit v1.2.3