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::{
   6     ast::{self, make, AstNode, AttrsOwner, PathSegmentKind, VisibilityOwner},
   7     ted,
   8 };
   9
  10 /// What type of merges are allowed.
  11 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  12 pub enum MergeBehavior {
  13     /// Merge imports from the same crate into a single use statement.
  14     Crate,
  15     /// Merge imports from the same module into a single use statement.
  16     Module,
  17 }
  18
  19 impl MergeBehavior {
  20     #[inline]
  21     fn is_tree_allowed(&self, tree: &ast::UseTree) -> bool {
  22         match self {
  23             MergeBehavior::Crate => true,
  24             // only simple single segment paths are allowed
  25             MergeBehavior::Module => {
  26                 tree.use_tree_list().is_none() && tree.path().map(path_len) <= Some(1)
  27             }
  28         }
  29     }
  30 }
  31
  32 pub fn try_merge_imports(
  33     lhs: &ast::Use,
  34     rhs: &ast::Use,
  35     merge_behavior: MergeBehavior,
  36 ) -> Option<ast::Use> {
  37     // don't merge imports with different visibilities
  38     if !eq_visibility(lhs.visibility(), rhs.visibility()) {
  39         return None;
  40     }
  41     if !eq_attrs(lhs.attrs(), rhs.attrs()) {
  42         return None;
  43     }
  44
  45     let lhs = lhs.clone_subtree().clone_for_update();
  46     let lhs_tree = lhs.use_tree()?;
  47     let rhs_tree = rhs.use_tree()?;
  48     let merged = try_merge_trees(&lhs_tree, &rhs_tree, merge_behavior)?;
  49     ted::replace(lhs_tree.syntax(), merged.syntax());
  50     Some(lhs)
  51 }
  52
  53 pub fn try_merge_trees(
  54     lhs: &ast::UseTree,
  55     rhs: &ast::UseTree,
  56     merge: MergeBehavior,
  57 ) -> Option<ast::UseTree> {
  58     let lhs_path = lhs.path()?;
  59     let rhs_path = rhs.path()?;
  60
  61     let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
  62     let (lhs, rhs) = if lhs.is_simple_path()
  63         && rhs.is_simple_path()
  64         && lhs_path == lhs_prefix
  65         && rhs_path == rhs_prefix
  66     {
  67         (lhs.clone(), rhs.clone())
  68     } else {
  69         (lhs.split_prefix(&lhs_prefix), rhs.split_prefix(&rhs_prefix))
  70     };
  71     recursive_merge(&lhs, &rhs, merge).map(|it| it.clone_for_update())
  72 }
  73
  74 /// Recursively "zips" together lhs and rhs.
  75 fn recursive_merge(
  76     lhs: &ast::UseTree,
  77     rhs: &ast::UseTree,
  78     merge: MergeBehavior,
  79 ) -> Option<ast::UseTree> {
  80     let mut use_trees = lhs
  81         .use_tree_list()
  82         .into_iter()
  83         .flat_map(|list| list.use_trees())
  84         // We use Option here to early return from this function(this is not the
  85         // same as a `filter` op).
  86         .map(|tree| match merge.is_tree_allowed(&tree) {
  87             true => Some(tree),
  88             false => None,
  89         })
  90         .collect::<Option<Vec<_>>>()?;
  91     use_trees.sort_unstable_by(|a, b| path_cmp_for_sort(a.path(), b.path()));
  92     for rhs_t in rhs.use_tree_list().into_iter().flat_map(|list| list.use_trees()) {
  93         if !merge.is_tree_allowed(&rhs_t) {
  94             return None;
  95         }
  96         let rhs_path = rhs_t.path();
  97         match use_trees.binary_search_by(|lhs_t| {
  98             let (lhs_t, rhs_t) = match lhs_t
  99                 .path()
 100                 .zip(rhs_path.clone())
 101                 .and_then(|(lhs, rhs)| common_prefix(&lhs, &rhs))
 102             {
 103                 Some((lhs_p, rhs_p)) => (lhs_t.split_prefix(&lhs_p), rhs_t.split_prefix(&rhs_p)),
 104                 None => (lhs_t.clone(), rhs_t.clone()),
 105             };
 106
 107             path_cmp_bin_search(lhs_t.path(), rhs_t.path())
 108         }) {
 109             Ok(idx) => {
 110                 let lhs_t = &mut use_trees[idx];
 111                 let lhs_path = lhs_t.path()?;
 112                 let rhs_path = rhs_path?;
 113                 let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
 114                 if lhs_prefix == lhs_path && rhs_prefix == rhs_path {
 115                     let tree_is_self = |tree: ast::UseTree| {
 116                         tree.path().as_ref().map(path_is_self).unwrap_or(false)
 117                     };
 118                     // Check if only one of the two trees has a tree list, and
 119                     // whether that then contains `self` or not. If this is the
 120                     // case we can skip this iteration since the path without
 121                     // the list is already included in the other one via `self`.
 122                     let tree_contains_self = |tree: &ast::UseTree| {
 123                         tree.use_tree_list()
 124                             .map(|tree_list| tree_list.use_trees().any(tree_is_self))
 125                             .unwrap_or(false)
 126                     };
 127                     match (tree_contains_self(&lhs_t), tree_contains_self(&rhs_t)) {
 128                         (true, false) => continue,
 129                         (false, true) => {
 130                             *lhs_t = rhs_t;
 131                             continue;
 132                         }
 133                         _ => (),
 134                     }
 135
 136                     // Glob imports aren't part of the use-tree lists so we need
 137                     // to special handle them here as well this special handling
 138                     // is only required for when we merge a module import into a
 139                     // glob import of said module see the `merge_self_glob` or
 140                     // `merge_mod_into_glob` tests.
 141                     if lhs_t.star_token().is_some() || rhs_t.star_token().is_some() {
 142                         *lhs_t = make::use_tree(
 143                             make::path_unqualified(make::path_segment_self()),
 144                             None,
 145                             None,
 146                             false,
 147                         );
 148                         use_trees.insert(idx, make::use_tree_glob());
 149                         continue;
 150                     }
 151
 152                     if lhs_t.use_tree_list().is_none() && rhs_t.use_tree_list().is_none() {
 153                         continue;
 154                     }
 155                 }
 156                 let lhs = lhs_t.split_prefix(&lhs_prefix);
 157                 let rhs = rhs_t.split_prefix(&rhs_prefix);
 158                 match recursive_merge(&lhs, &rhs, merge) {
 159                     Some(use_tree) => use_trees[idx] = use_tree,
 160                     None => return None,
 161                 }
 162             }
 163             Err(_)
 164                 if merge == MergeBehavior::Module
 165                     && use_trees.len() > 0
 166                     && rhs_t.use_tree_list().is_some() =>
 167             {
 168                 return None
 169             }
 170             Err(idx) => {
 171                 use_trees.insert(idx, rhs_t);
 172             }
 173         }
 174     }
 175
 176     let lhs = lhs.clone_subtree().clone_for_update();
 177     if let Some(old) = lhs.use_tree_list() {
 178         ted::replace(old.syntax(), make::use_tree_list(use_trees).syntax().clone_for_update());
 179     }
 180     ast::UseTree::cast(lhs.syntax().clone_subtree())
 181 }
 182
 183 /// Traverses both paths until they differ, returning the common prefix of both.
 184 pub fn common_prefix(lhs: &ast::Path, rhs: &ast::Path) -> Option<(ast::Path, ast::Path)> {
 185     let mut res = None;
 186     let mut lhs_curr = lhs.first_qualifier_or_self();
 187     let mut rhs_curr = rhs.first_qualifier_or_self();
 188     loop {
 189         match (lhs_curr.segment(), rhs_curr.segment()) {
 190             (Some(lhs), Some(rhs)) if lhs.syntax().text() == rhs.syntax().text() => (),
 191             _ => break res,
 192         }
 193         res = Some((lhs_curr.clone(), rhs_curr.clone()));
 194
 195         match lhs_curr.parent_path().zip(rhs_curr.parent_path()) {
 196             Some((lhs, rhs)) => {
 197                 lhs_curr = lhs;
 198                 rhs_curr = rhs;
 199             }
 200             _ => break res,
 201         }
 202     }
 203 }
 204
 205 /// Orders paths in the following way:
 206 /// the sole self token comes first, after that come uppercase identifiers, then lowercase identifiers
 207 // FIXME: rustfmt sorts lowercase idents before uppercase, in general we want to have the same ordering rustfmt has
 208 // which is `self` and `super` first, then identifier imports with lowercase ones first, then glob imports and at last list imports.
 209 // Example foo::{self, foo, baz, Baz, Qux, *, {Bar}}
 210 fn path_cmp_for_sort(a: Option<ast::Path>, b: Option<ast::Path>) -> Ordering {
 211     match (a, b) {
 212         (None, None) => Ordering::Equal,
 213         (None, Some(_)) => Ordering::Less,
 214         (Some(_), None) => Ordering::Greater,
 215         (Some(ref a), Some(ref b)) => match (path_is_self(a), path_is_self(b)) {
 216             (true, true) => Ordering::Equal,
 217             (true, false) => Ordering::Less,
 218             (false, true) => Ordering::Greater,
 219             (false, false) => path_cmp_short(a, b),
 220         },
 221     }
 222 }
 223
 224 /// Path comparison func for binary searching for merging.
 225 fn path_cmp_bin_search(lhs: Option<ast::Path>, rhs: Option<ast::Path>) -> Ordering {
 226     match (
 227         lhs.as_ref().and_then(ast::Path::first_segment),
 228         rhs.as_ref().and_then(ast::Path::first_segment),
 229     ) {
 230         (None, None) => Ordering::Equal,
 231         (None, Some(_)) => Ordering::Less,
 232         (Some(_), None) => Ordering::Greater,
 233         (Some(ref a), Some(ref b)) => path_segment_cmp(a, b),
 234     }
 235 }
 236
 237 /// Short circuiting comparison, if both paths are equal until one of them ends they are considered
 238 /// equal
 239 fn path_cmp_short(a: &ast::Path, b: &ast::Path) -> Ordering {
 240     let a = a.segments();
 241     let b = b.segments();
 242     // cmp_by would be useful for us here but that is currently unstable
 243     // cmp doesn't work due the lifetimes on text's return type
 244     a.zip(b)
 245         .find_map(|(a, b)| match path_segment_cmp(&a, &b) {
 246             Ordering::Equal => None,
 247             ord => Some(ord),
 248         })
 249         .unwrap_or(Ordering::Equal)
 250 }
 251
 252 /// Compares two paths, if one ends earlier than the other the has_tl parameters decide which is
 253 /// greater as a a path that has a tree list should be greater, while one that just ends without
 254 /// a tree list should be considered less.
 255 pub(super) fn use_tree_path_cmp(
 256     a: &ast::Path,
 257     a_has_tl: bool,
 258     b: &ast::Path,
 259     b_has_tl: bool,
 260 ) -> Ordering {
 261     let a_segments = a.segments();
 262     let b_segments = b.segments();
 263     // cmp_by would be useful for us here but that is currently unstable
 264     // cmp doesn't work due the lifetimes on text's return type
 265     a_segments
 266         .zip_longest(b_segments)
 267         .find_map(|zipped| match zipped {
 268             EitherOrBoth::Both(ref a, ref b) => match path_segment_cmp(a, b) {
 269                 Ordering::Equal => None,
 270                 ord => Some(ord),
 271             },
 272             EitherOrBoth::Left(_) if !b_has_tl => Some(Ordering::Greater),
 273             EitherOrBoth::Left(_) => Some(Ordering::Less),
 274             EitherOrBoth::Right(_) if !a_has_tl => Some(Ordering::Less),
 275             EitherOrBoth::Right(_) => Some(Ordering::Greater),
 276         })
 277         .unwrap_or(Ordering::Equal)
 278 }
 279
 280 fn path_segment_cmp(a: &ast::PathSegment, b: &ast::PathSegment) -> Ordering {
 281     let a = a.kind().and_then(|kind| match kind {
 282         PathSegmentKind::Name(name_ref) => Some(name_ref),
 283         _ => None,
 284     });
 285     let b = b.kind().and_then(|kind| match kind {
 286         PathSegmentKind::Name(name_ref) => Some(name_ref),
 287         _ => None,
 288     });
 289     a.as_ref().map(ast::NameRef::text).cmp(&b.as_ref().map(ast::NameRef::text))
 290 }
 291
 292 pub fn eq_visibility(vis0: Option<ast::Visibility>, vis1: Option<ast::Visibility>) -> bool {
 293     match (vis0, vis1) {
 294         (None, None) => true,
 295         (Some(vis0), Some(vis1)) => vis0.is_eq_to(&vis1),
 296         _ => false,
 297     }
 298 }
 299
 300 pub fn eq_attrs(
 301     attrs0: impl Iterator<Item = ast::Attr>,
 302     attrs1: impl Iterator<Item = ast::Attr>,
 303 ) -> bool {
 304     // FIXME order of attributes should not matter
 305     let attrs0 = attrs0
 306         .flat_map(|attr| attr.syntax().descendants_with_tokens())
 307         .flat_map(|it| it.into_token());
 308     let attrs1 = attrs1
 309         .flat_map(|attr| attr.syntax().descendants_with_tokens())
 310         .flat_map(|it| it.into_token());
 311     stdx::iter_eq_by(attrs0, attrs1, |tok, tok2| tok.text() == tok2.text())
 312 }
 313
 314 fn path_is_self(path: &ast::Path) -> bool {
 315     path.segment().and_then(|seg| seg.self_token()).is_some() && path.qualifier().is_none()
 316 }
 317
 318 fn path_len(path: ast::Path) -> usize {
 319     path.segments().count()
 320 }