crates/ide_db/src/helpers/merge_imports.rs

   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 imports from the same crate into a single use statement.
  13     Crate,
  14     /// Merge imports from the same module into a single use statement.
  15     Module,
  16 }
  17
  18 impl MergeBehavior {
  19     #[inline]
  20     fn is_tree_allowed(&self, tree: &ast::UseTree) -> bool {
  21         match self {
  22             MergeBehavior::Crate => true,
  23             // only simple single segment paths are allowed
  24             MergeBehavior::Module => {
  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::use_tree_glob());
 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::Module
 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 }