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