1 //! Handle syntactic aspects of merging UseTrees.
2 use std::cmp::Ordering;
4 use itertools::{EitherOrBoth, Itertools};
6 ast::{self, AstNode, HasAttrs, HasVisibility, PathSegmentKind},
10 use crate::syntax_helpers::node_ext::vis_eq;
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.
17 /// Merge imports from the same module into a single use statement.
22 fn is_tree_allowed(&self, tree: &ast::UseTree) -> bool {
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)
33 /// Merge `rhs` into `lhs` keeping both intact.
34 /// Returned AST is mutable.
35 pub fn try_merge_imports(
38 merge_behavior: MergeBehavior,
39 ) -> Option<ast::Use> {
40 // don't merge imports with different visibilities
41 if !eq_visibility(lhs.visibility(), rhs.visibility()) {
44 if !eq_attrs(lhs.attrs(), rhs.attrs()) {
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)?;
56 /// Merge `rhs` into `lhs` keeping both intact.
57 /// Returned AST is mutable.
58 pub fn try_merge_trees(
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)?;
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()?;
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)
79 lhs.split_prefix(&lhs_prefix);
80 rhs.split_prefix(&rhs_prefix);
82 recursive_merge(lhs, rhs, merge)
85 /// Recursively merges rhs to lhs
87 fn recursive_merge(lhs: &ast::UseTree, rhs: &ast::UseTree, merge: MergeBehavior) -> Option<()> {
88 let mut use_trees: Vec<ast::UseTree> = lhs
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) {
101 let rhs_path = rhs_t.path();
104 .binary_search_by(|lhs_t| path_cmp_bin_search(lhs_t.path(), rhs_path.as_ref()))
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)
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| {
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))
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());
136 if lhs_t.is_simple_path() && rhs_t.is_simple_path() {
140 lhs_t.split_prefix(&lhs_prefix);
141 rhs_t.split_prefix(&rhs_prefix);
142 recursive_merge(lhs_t, &rhs_t, merge)?;
145 if merge == MergeBehavior::Module
146 && !use_trees.is_empty()
147 && rhs_t.use_tree_list().is_some() =>
152 use_trees.insert(idx, rhs_t.clone());
153 lhs.get_or_create_use_tree_list().add_use_tree(rhs_t);
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)> {
163 let mut lhs_curr = lhs.first_qualifier_or_self();
164 let mut rhs_curr = rhs.first_qualifier_or_self();
166 match (lhs_curr.segment(), rhs_curr.segment()) {
167 (Some(lhs), Some(rhs)) if lhs.syntax().text() == rhs.syntax().text() => (),
170 res = Some((lhs_curr.clone(), rhs_curr.clone()));
172 match lhs_curr.parent_path().zip(rhs_curr.parent_path()) {
173 Some((lhs, rhs)) => {
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 {
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),
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))
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),
212 /// Short circuiting comparison, if both paths are equal until one of them ends they are considered
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
220 .find_map(|(a, b)| match path_segment_cmp(&a, &b) {
221 Ordering::Equal => None,
224 .unwrap_or(Ordering::Equal)
227 /// Compares two paths, if one ends earlier than the other the has_tl parameters decide which is
228 /// greater as a 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(
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
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,
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),
252 .unwrap_or(Ordering::Equal)
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),
260 let b = b.kind().and_then(|kind| match kind {
261 PathSegmentKind::Name(name_ref) => Some(name_ref),
264 a.as_ref().map(ast::NameRef::text).cmp(&b.as_ref().map(ast::NameRef::text))
267 pub fn eq_visibility(vis0: Option<ast::Visibility>, vis1: Option<ast::Visibility>) -> bool {
269 (None, None) => true,
270 (Some(vis0), Some(vis1)) => vis_eq(&vis0, &vis1),
276 attrs0: impl Iterator<Item = ast::Attr>,
277 attrs1: impl Iterator<Item = ast::Attr>,
279 // FIXME order of attributes should not matter
281 .flat_map(|attr| attr.syntax().descendants_with_tokens())
282 .flat_map(|it| it.into_token());
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())
289 fn path_is_self(path: &ast::Path) -> bool {
290 path.segment().and_then(|seg| seg.self_token()).is_some() && path.qualifier().is_none()
293 fn path_len(path: ast::Path) -> usize {
294 path.segments().count()