4 files changed, 172 insertions, 110 deletions

diff --git a/crates/assists/src/ast_transform.rs b/crates/assists/src/ast_transform.rs
index 835da3bb2..4307e0191 100644
--- a/crates/assists/src/ast_transform.rs
+++ b/crates/assists/src/ast_transform.rs
@@ -5,12 +5,13 @@ use hir::{HirDisplay, PathResolution, SemanticsScope};
 use syntax::{
     algo::SyntaxRewriter,
     ast::{self, AstNode},
+    SyntaxNode,
 };
 
 pub fn apply<'a, N: AstNode>(transformer: &dyn AstTransform<'a>, node: N) -> N {
     SyntaxRewriter::from_fn(|element| match element {
         syntax::SyntaxElement::Node(n) => {
-            let replacement = transformer.get_substitution(&n)?;
+            let replacement = transformer.get_substitution(&n, transformer)?;
             Some(replacement.into())
         }
         _ => None,
@@ -47,32 +48,35 @@ pub fn apply<'a, N: AstNode>(transformer: &dyn AstTransform<'a>, node: N) -> N {
 /// We'd want to somehow express this concept simpler, but so far nobody got to
 /// simplifying this!
 pub trait AstTransform<'a> {
-    fn get_substitution(&self, node: &syntax::SyntaxNode) -> Option<syntax::SyntaxNode>;
+    fn get_substitution(
+        &self,
+        node: &SyntaxNode,
+        recur: &dyn AstTransform<'a>,
+    ) -> Option<SyntaxNode>;
 
-    fn chain_before(self, other: Box<dyn AstTransform<'a> + 'a>) -> Box<dyn AstTransform<'a> + 'a>;
     fn or<T: AstTransform<'a> + 'a>(self, other: T) -> Box<dyn AstTransform<'a> + 'a>
     where
         Self: Sized + 'a,
     {
-        self.chain_before(Box::new(other))
+        Box::new(Or(Box::new(self), Box::new(other)))
     }
 }
 
-struct NullTransformer;
+struct Or<'a>(Box<dyn AstTransform<'a> + 'a>, Box<dyn AstTransform<'a> + 'a>);
 
-impl<'a> AstTransform<'a> for NullTransformer {
-    fn get_substitution(&self, _node: &syntax::SyntaxNode) -> Option<syntax::SyntaxNode> {
-        None
-    }
-    fn chain_before(self, other: Box<dyn AstTransform<'a> + 'a>) -> Box<dyn AstTransform<'a> + 'a> {
-        other
+impl<'a> AstTransform<'a> for Or<'a> {
+    fn get_substitution(
+        &self,
+        node: &SyntaxNode,
+        recur: &dyn AstTransform<'a>,
+    ) -> Option<SyntaxNode> {
+        self.0.get_substitution(node, recur).or_else(|| self.1.get_substitution(node, recur))
     }
 }
 
 pub struct SubstituteTypeParams<'a> {
     source_scope: &'a SemanticsScope<'a>,
     substs: FxHashMap<hir::TypeParam, ast::Type>,
-    previous: Box<dyn AstTransform<'a> + 'a>,
 }
 
 impl<'a> SubstituteTypeParams<'a> {
@@ -111,11 +115,7 @@ impl<'a> SubstituteTypeParams<'a> {
                 }
             })
             .collect();
-        return SubstituteTypeParams {
-            source_scope,
-            substs: substs_by_param,
-            previous: Box::new(NullTransformer),
-        };
+        return SubstituteTypeParams { source_scope, substs: substs_by_param };
 
         // FIXME: It would probably be nicer if we could get this via HIR (i.e. get the
         // trait ref, and then go from the types in the substs back to the syntax).
@@ -140,7 +140,14 @@ impl<'a> SubstituteTypeParams<'a> {
             Some(result)
         }
     }
-    fn get_substitution_inner(&self, node: &syntax::SyntaxNode) -> Option<syntax::SyntaxNode> {
+}
+
+impl<'a> AstTransform<'a> for SubstituteTypeParams<'a> {
+    fn get_substitution(
+        &self,
+        node: &SyntaxNode,
+        _recur: &dyn AstTransform<'a>,
+    ) -> Option<SyntaxNode> {
         let type_ref = ast::Type::cast(node.clone())?;
         let path = match &type_ref {
             ast::Type::PathType(path_type) => path_type.path()?,
@@ -154,27 +161,23 @@ impl<'a> SubstituteTypeParams<'a> {
     }
 }
 
-impl<'a> AstTransform<'a> for SubstituteTypeParams<'a> {
-    fn get_substitution(&self, node: &syntax::SyntaxNode) -> Option<syntax::SyntaxNode> {
-        self.get_substitution_inner(node).or_else(|| self.previous.get_substitution(node))
-    }
-    fn chain_before(self, other: Box<dyn AstTransform<'a> + 'a>) -> Box<dyn AstTransform<'a> + 'a> {
-        Box::new(SubstituteTypeParams { previous: other, ..self })
-    }
-}
-
 pub struct QualifyPaths<'a> {
     target_scope: &'a SemanticsScope<'a>,
     source_scope: &'a SemanticsScope<'a>,
-    previous: Box<dyn AstTransform<'a> + 'a>,
 }
 
 impl<'a> QualifyPaths<'a> {
     pub fn new(target_scope: &'a SemanticsScope<'a>, source_scope: &'a SemanticsScope<'a>) -> Self {
-        Self { target_scope, source_scope, previous: Box::new(NullTransformer) }
+        Self { target_scope, source_scope }
     }
+}
 
-    fn get_substitution_inner(&self, node: &syntax::SyntaxNode) -> Option<syntax::SyntaxNode> {
+impl<'a> AstTransform<'a> for QualifyPaths<'a> {
+    fn get_substitution(
+        &self,
+        node: &SyntaxNode,
+        recur: &dyn AstTransform<'a>,
+    ) -> Option<SyntaxNode> {
         // FIXME handle value ns?
         let from = self.target_scope.module()?;
         let p = ast::Path::cast(node.clone())?;
@@ -191,7 +194,7 @@ impl<'a> QualifyPaths<'a> {
                 let type_args = p
                     .segment()
                     .and_then(|s| s.generic_arg_list())
-                    .map(|arg_list| apply(self, arg_list));
+                    .map(|arg_list| apply(recur, arg_list));
                 if let Some(type_args) = type_args {
                     let last_segment = path.segment().unwrap();
                     path = path.with_segment(last_segment.with_generic_args(type_args))
@@ -208,15 +211,6 @@ impl<'a> QualifyPaths<'a> {
     }
 }
 
-impl<'a> AstTransform<'a> for QualifyPaths<'a> {
-    fn get_substitution(&self, node: &syntax::SyntaxNode) -> Option<syntax::SyntaxNode> {
-        self.get_substitution_inner(node).or_else(|| self.previous.get_substitution(node))
-    }
-    fn chain_before(self, other: Box<dyn AstTransform<'a> + 'a>) -> Box<dyn AstTransform<'a> + 'a> {
-        Box::new(QualifyPaths { previous: other, ..self })
-    }
-}
-
 pub(crate) fn path_to_ast(path: hir::ModPath) -> ast::Path {
     let parse = ast::SourceFile::parse(&path.to_string());
     parse
diff --git a/crates/assists/src/handlers/add_missing_impl_members.rs b/crates/assists/src/handlers/add_missing_impl_members.rs
index 1ac5fefd6..51b5a2eb0 100644
--- a/crates/assists/src/handlers/add_missing_impl_members.rs
+++ b/crates/assists/src/handlers/add_missing_impl_members.rs
@@ -146,7 +146,7 @@ fn add_missing_impl_members_inner(
 
     let target = impl_def.syntax().text_range();
     acc.add(AssistId(assist_id, AssistKind::QuickFix), label, target, |builder| {
-        let impl_item_list = impl_def.assoc_item_list().unwrap_or(make::assoc_item_list());
+        let impl_item_list = impl_def.assoc_item_list().unwrap_or_else(make::assoc_item_list);
 
         let n_existing_items = impl_item_list.assoc_items().count();
         let source_scope = ctx.sema.scope_for_def(trait_);
diff --git a/crates/assists/src/handlers/extract_struct_from_enum_variant.rs b/crates/assists/src/handlers/extract_struct_from_enum_variant.rs
index d1eadaa99..f5f03ef36 100644
--- a/crates/assists/src/handlers/extract_struct_from_enum_variant.rs
+++ b/crates/assists/src/handlers/extract_struct_from_enum_variant.rs
@@ -91,7 +91,7 @@ fn existing_struct_def(db: &RootDatabase, variant_name: &str, variant: &EnumVari
         .module(db)
         .scope(db, None)
         .into_iter()
-        .any(|(name, _)| name.to_string() == variant_name.to_string())
+        .any(|(name, _)| name.to_string() == variant_name)
 }
 
 #[allow(dead_code)]
diff --git a/crates/assists/src/utils/insert_use.rs b/crates/assists/src/utils/insert_use.rs
index 5719b06af..f6025c99a 100644
--- a/crates/assists/src/utils/insert_use.rs
+++ b/crates/assists/src/utils/insert_use.rs
@@ -4,13 +4,14 @@ use std::{
     iter::{self, successors},
 };
 
-use ast::{
-    edit::{AstNodeEdit, IndentLevel},
-    PathSegmentKind, VisibilityOwner,
-};
+use itertools::{EitherOrBoth, Itertools};
 use syntax::{
     algo,
-    ast::{self, make, AstNode},
+    ast::{
+        self,
+        edit::{AstNodeEdit, IndentLevel},
+        make, AstNode, PathSegmentKind, VisibilityOwner,
+    },
     InsertPosition, SyntaxElement, SyntaxNode,
 };
 
@@ -174,7 +175,7 @@ pub(crate) fn try_merge_trees(
     let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
     let lhs = lhs.split_prefix(&lhs_prefix);
     let rhs = rhs.split_prefix(&rhs_prefix);
-    recursive_merge(&lhs, &rhs, merge).map(|(merged, _)| merged)
+    recursive_merge(&lhs, &rhs, merge)
 }
 
 /// Recursively "zips" together lhs and rhs.
@@ -182,22 +183,24 @@ fn recursive_merge(
     lhs: &ast::UseTree,
     rhs: &ast::UseTree,
     merge: MergeBehaviour,
-) -> Option<(ast::UseTree, bool)> {
+) -> Option<ast::UseTree> {
     let mut use_trees = lhs
         .use_tree_list()
         .into_iter()
         .flat_map(|list| list.use_trees())
-        // check if any of the use trees are nested, if they are and the behaviour is `last` we are not allowed to merge this
-        // so early exit the iterator by using Option's Intoiterator impl
-        .map(|tree| match merge == MergeBehaviour::Last && tree.use_tree_list().is_some() {
-            true => None,
-            false => Some(tree),
+        // 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::<Option<Vec<_>>>()?;
-    use_trees.sort_unstable_by(|a, b| path_cmp_opt(a.path(), b.path()));
+    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(|p| path_cmp_opt(p.path(), rhs_path.clone())) {
+        match use_trees.binary_search_by(|p| path_cmp_bin_search(p.path(), rhs_path.clone())) {
             Ok(idx) => {
                 let lhs_t = &mut use_trees[idx];
                 let lhs_path = lhs_t.path()?;
@@ -239,17 +242,9 @@ fn recursive_merge(
                 }
                 let lhs = lhs_t.split_prefix(&lhs_prefix);
                 let rhs = rhs_t.split_prefix(&rhs_prefix);
-                let this_has_children = use_trees.len() > 0;
                 match recursive_merge(&lhs, &rhs, merge) {
-                    Some((_, has_multiple_children))
-                        if merge == MergeBehaviour::Last
-                            && this_has_children
-                            && has_multiple_children =>
-                    {
-                        return None
-                    }
-                    Some((use_tree, _)) => use_trees[idx] = use_tree,
-                    None => use_trees.insert(idx, rhs_t),
+                    Some(use_tree) => use_trees[idx] = use_tree,
+                    None => return None,
                 }
             }
             Err(_)
@@ -264,8 +259,7 @@ fn recursive_merge(
             }
         }
     }
-    let has_multiple_children = use_trees.len() > 1;
-    Some((lhs.with_use_tree_list(make::use_tree_list(use_trees)), has_multiple_children))
+    Some(lhs.with_use_tree_list(make::use_tree_list(use_trees)))
 }
 
 /// Traverses both paths until they differ, returning the common prefix of both.
@@ -308,41 +302,83 @@ fn segment_iter(path: &ast::Path) -> impl Iterator<Item = ast::PathSegment> + Cl
     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 sort lowercase idents before uppercase, in general we want to have the same ordering rustfmt has
+// 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(a: &ast::Path, b: &ast::Path) -> Ordering {
-    match (path_is_self(a), path_is_self(b)) {
-        (true, true) => Ordering::Equal,
-        (true, false) => Ordering::Less,
-        (false, true) => Ordering::Greater,
-        (false, false) => {
-            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)
-                .flat_map(|(seg, seg2)| seg.name_ref().zip(seg2.name_ref()))
-                .find_map(|(a, b)| match a.text().cmp(b.text()) {
-                    ord @ Ordering::Greater | ord @ Ordering::Less => Some(ord),
-                    Ordering::Equal => None,
-                })
-                .unwrap_or(Ordering::Equal)
-        }
+fn path_cmp_for_sort(a: Option<ast::Path>, b: Option<ast::Path>) -> 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),
+        },
     }
 }
 
-fn path_cmp_opt(a: Option<ast::Path>, b: Option<ast::Path>) -> Ordering {
-    match (a, b) {
+/// Path comparison func for binary searching for merging.
+fn path_cmp_bin_search(lhs: Option<ast::Path>, rhs: Option<ast::Path>) -> Ordering {
+    match (lhs, rhs) {
         (None, None) => Ordering::Equal,
         (None, Some(_)) => Ordering::Less,
         (Some(_), None) => Ordering::Greater,
-        (Some(a), Some(b)) => path_cmp(&a, &b),
+        (Some(ref a), Some(ref b)) => path_cmp_short(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.name_ref();
+    let b = b.name_ref();
+    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 MergeBehaviour {
@@ -352,6 +388,19 @@ pub enum MergeBehaviour {
     Last,
 }
 
+impl MergeBehaviour {
+    #[inline]
+    fn is_tree_allowed(&self, tree: &ast::UseTree) -> bool {
+        match self {
+            MergeBehaviour::Full => true,
+            // only simple single segment paths are allowed
+            MergeBehaviour::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
@@ -379,7 +428,6 @@ impl ImportGroup {
             PathSegmentKind::Name(name) => match name.text().as_str() {
                 "std" => ImportGroup::Std,
                 "core" => ImportGroup::Std,
-                // FIXME: can be ThisModule as well
                 _ => ImportGroup::ExternCrate,
             },
             PathSegmentKind::Type { .. } => unreachable!(),
@@ -405,30 +453,30 @@ fn find_insert_position(
         .as_syntax_node()
         .children()
         .filter_map(|node| ast::Use::cast(node.clone()).zip(Some(node)))
-        .flat_map(|(use_, node)| use_.use_tree().and_then(|tree| tree.path()).zip(Some(node)));
+        .flat_map(|(use_, node)| {
+            let tree = use_.use_tree()?;
+            let path = tree.path()?;
+            let has_tl = tree.use_tree_list().is_some();
+            Some((path, has_tl, node))
+        });
     // Iterator that discards anything thats not in the required grouping
     // This implementation allows the user to rearrange their import groups as this only takes the first group that fits
     let group_iter = path_node_iter
         .clone()
-        .skip_while(|(path, _)| ImportGroup::new(path) != group)
-        .take_while(|(path, _)| ImportGroup::new(path) == group);
+        .skip_while(|(path, ..)| ImportGroup::new(path) != group)
+        .take_while(|(path, ..)| ImportGroup::new(path) == group);
 
-    let segments = segment_iter(&insert_path);
     // track the last element we iterated over, if this is still None after the iteration then that means we never iterated in the first place
     let mut last = None;
     // find the element that would come directly after our new import
-    let post_insert =
-        group_iter.inspect(|(_, node)| last = Some(node.clone())).find(|(path, _)| {
-            let check_segments = segment_iter(&path);
-            segments
-                .clone()
-                .zip(check_segments)
-                .flat_map(|(seg, seg2)| seg.name_ref().zip(seg2.name_ref()))
-                .all(|(l, r)| l.text() <= r.text())
-        });
+    let post_insert = group_iter.inspect(|(.., node)| last = Some(node.clone())).find(
+        |&(ref path, has_tl, _)| {
+            use_tree_path_cmp(&insert_path, false, path, has_tl) != Ordering::Greater
+        },
+    );
     match post_insert {
         // insert our import before that element
-        Some((_, node)) => (InsertPosition::Before(node.into()), AddBlankLine::After),
+        Some((.., node)) => (InsertPosition::Before(node.into()), AddBlankLine::After),
         // there is no element after our new import, so append it to the end of the group
         None => match last {
             Some(node) => (InsertPosition::After(node.into()), AddBlankLine::Before),
@@ -438,10 +486,10 @@ fn find_insert_position(
                 let mut last = None;
                 // find the group that comes after where we want to insert
                 let post_group = path_node_iter
-                    .inspect(|(_, node)| last = Some(node.clone()))
-                    .find(|(p, _)| ImportGroup::new(p) > group);
+                    .inspect(|(.., node)| last = Some(node.clone()))
+                    .find(|(p, ..)| ImportGroup::new(p) > group);
                 match post_group {
-                    Some((_, node)) => {
+                    Some((.., node)) => {
                         (InsertPosition::Before(node.into()), AddBlankLine::AfterTwice)
                     }
                     // there is no such group, so append after the last one
@@ -676,6 +724,11 @@ use std::io;",
     }
 
     #[test]
+    fn merge_last_into_self() {
+        check_last("foo::bar::baz", r"use foo::bar;", r"use foo::bar::{self, baz};");
+    }
+
+    #[test]
     fn merge_groups_full() {
         check_full(
             "std::io",
@@ -819,8 +872,23 @@ use std::io;",
     }
 
     #[test]
-    fn merge_last_too_long() {
-        check_last("foo::bar", r"use foo::bar::baz::Qux;", r"use foo::bar::{self, baz::Qux};");
+    fn skip_merge_last_too_long() {
+        check_last(
+            "foo::bar",
+            r"use foo::bar::baz::Qux;",
+            r"use foo::bar;
+use foo::bar::baz::Qux;",
+        );
+    }
+
+    #[test]
+    fn skip_merge_last_too_long2() {
+        check_last(
+            "foo::bar::baz::Qux",
+            r"use foo::bar;",
+            r"use foo::bar;
+use foo::bar::baz::Qux;",
+        );
     }
 
     #[test]