6 files changed, 508 insertions, 494 deletions

diff --git a/crates/ide_db/src/helpers/famous_defs_fixture.rs b/crates/ide_db/src/helpers/famous_defs_fixture.rs
index 4d79e064e..29ae12dcf 100644
--- a/crates/ide_db/src/helpers/famous_defs_fixture.rs
+++ b/crates/ide_db/src/helpers/famous_defs_fixture.rs
@@ -112,6 +112,12 @@ pub mod ops {
         type Output;
         extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
     }
+
+    #[lang = "deref"]
+    pub trait Deref {
+        type Target: ?Sized;
+        fn deref(&self) -> &Self::Target;
+    }
 }
 
 pub mod option {
@@ -141,3 +147,5 @@ mod return_keyword {}
 
 /// Docs for prim_str
 mod prim_str {}
+
+pub use core::ops;
\ No newline at end of file
diff --git a/crates/ide_db/src/helpers/import_assets.rs b/crates/ide_db/src/helpers/import_assets.rs
index 8ce648367..91d6a4665 100644
--- a/crates/ide_db/src/helpers/import_assets.rs
+++ b/crates/ide_db/src/helpers/import_assets.rs
@@ -436,6 +436,8 @@ fn trait_applicable_items(
     })
     .collect();
 
+    let related_dyn_traits =
+        trait_candidate.receiver_ty.applicable_inherent_traits(db).collect::<FxHashSet<_>>();
     let mut located_imports = FxHashSet::default();
 
     if trait_assoc_item {
@@ -451,12 +453,16 @@ fn trait_applicable_items(
                             return None;
                         }
                     }
+                    let located_trait = assoc.containing_trait(db)?;
+                    if related_dyn_traits.contains(&located_trait) {
+                        return None;
+                    }
 
-                    let item = ItemInNs::from(ModuleDef::from(assoc.containing_trait(db)?));
+                    let trait_item = ItemInNs::from(ModuleDef::from(located_trait));
                     let original_item = assoc_to_item(assoc);
                     located_imports.insert(LocatedImport::new(
-                        mod_path(item)?,
-                        item,
+                        mod_path(trait_item)?,
+                        trait_item,
                         original_item,
                         mod_path(original_item),
                     ));
@@ -473,11 +479,15 @@ fn trait_applicable_items(
             |_, function| {
                 let assoc = function.as_assoc_item(db)?;
                 if required_assoc_items.contains(&assoc) {
-                    let item = ItemInNs::from(ModuleDef::from(assoc.containing_trait(db)?));
+                    let located_trait = assoc.containing_trait(db)?;
+                    if related_dyn_traits.contains(&located_trait) {
+                        return None;
+                    }
+                    let trait_item = ItemInNs::from(ModuleDef::from(located_trait));
                     let original_item = assoc_to_item(assoc);
                     located_imports.insert(LocatedImport::new(
-                        mod_path(item)?,
-                        item,
+                        mod_path(trait_item)?,
+                        trait_item,
                         original_item,
                         mod_path(original_item),
                     ));
diff --git a/crates/ide_db/src/helpers/insert_use.rs b/crates/ide_db/src/helpers/insert_use.rs
index be3a22725..55cdc4da3 100644
--- a/crates/ide_db/src/helpers/insert_use.rs
+++ b/crates/ide_db/src/helpers/insert_use.rs
@@ -1,19 +1,17 @@
 //! Handle syntactic aspects of inserting a new `use`.
-use std::{cmp::Ordering, iter::successors};
+use std::cmp::Ordering;
 
 use hir::Semantics;
-use itertools::{EitherOrBoth, Itertools};
 use syntax::{
-    algo::SyntaxRewriter,
-    ast::{
-        self,
-        edit::{AstNodeEdit, IndentLevel},
-        make, AstNode, AttrsOwner, PathSegmentKind, VisibilityOwner,
-    },
-    AstToken, InsertPosition, NodeOrToken, SyntaxElement, SyntaxNode, SyntaxToken,
+    algo,
+    ast::{self, make, AstNode, PathSegmentKind},
+    ted, AstToken, Direction, NodeOrToken, SyntaxNode, SyntaxToken,
 };
 
-use crate::RootDatabase;
+use crate::{
+    helpers::merge_imports::{try_merge_imports, use_tree_path_cmp, MergeBehavior},
+    RootDatabase,
+};
 
 pub use hir::PrefixKind;
 
@@ -42,13 +40,18 @@ impl ImportScope {
     }
 
     /// Determines the containing syntax node in which to insert a `use` statement affecting `position`.
-    pub fn find_insert_use_container(
+    pub fn find_insert_use_container_with_macros(
         position: &SyntaxNode,
         sema: &Semantics<'_, RootDatabase>,
     ) -> Option<Self> {
         sema.ancestors_with_macros(position.clone()).find_map(Self::from)
     }
 
+    /// Determines the containing syntax node in which to insert a `use` statement affecting `position`.
+    pub fn find_insert_use_container(position: &SyntaxNode) -> Option<Self> {
+        std::iter::successors(Some(position.clone()), SyntaxNode::parent).find_map(Self::from)
+    }
+
     pub fn as_syntax_node(&self) -> &SyntaxNode {
         match self {
             ImportScope::File(file) => file.syntax(),
@@ -56,434 +59,32 @@ impl ImportScope {
         }
     }
 
-    fn indent_level(&self) -> IndentLevel {
+    pub fn clone_for_update(&self) -> Self {
         match self {
-            ImportScope::File(file) => file.indent_level(),
-            ImportScope::Module(item_list) => item_list.indent_level() + 1,
+            ImportScope::File(file) => ImportScope::File(file.clone_for_update()),
+            ImportScope::Module(item_list) => ImportScope::Module(item_list.clone_for_update()),
         }
     }
-
-    fn first_insert_pos(&self) -> (InsertPosition<SyntaxElement>, AddBlankLine) {
-        match self {
-            ImportScope::File(_) => (InsertPosition::First, AddBlankLine::AfterTwice),
-            // don't insert the imports before the item list's opening curly brace
-            ImportScope::Module(item_list) => item_list
-                .l_curly_token()
-                .map(|b| (InsertPosition::After(b.into()), AddBlankLine::Around))
-                .unwrap_or((InsertPosition::First, AddBlankLine::AfterTwice)),
-        }
-    }
-
-    fn insert_pos_after_last_inner_element(&self) -> (InsertPosition<SyntaxElement>, AddBlankLine) {
-        self.as_syntax_node()
-            .children_with_tokens()
-            .filter(|child| match child {
-                NodeOrToken::Node(node) => is_inner_attribute(node.clone()),
-                NodeOrToken::Token(token) => is_inner_comment(token.clone()),
-            })
-            .last()
-            .map(|last_inner_element| {
-                (InsertPosition::After(last_inner_element), AddBlankLine::BeforeTwice)
-            })
-            .unwrap_or_else(|| self.first_insert_pos())
-    }
-}
-
-fn is_inner_attribute(node: SyntaxNode) -> bool {
-    ast::Attr::cast(node).map(|attr| attr.kind()) == Some(ast::AttrKind::Inner)
-}
-
-fn is_inner_comment(token: SyntaxToken) -> bool {
-    ast::Comment::cast(token).and_then(|comment| comment.kind().doc)
-        == Some(ast::CommentPlacement::Inner)
 }
 
 /// Insert an import path into the given file/node. A `merge` value of none indicates that no import merging is allowed to occur.
-pub fn insert_use<'a>(
-    scope: &ImportScope,
-    path: ast::Path,
-    cfg: InsertUseConfig,
-) -> SyntaxRewriter<'a> {
+pub fn insert_use<'a>(scope: &ImportScope, path: ast::Path, cfg: InsertUseConfig) {
     let _p = profile::span("insert_use");
-    let mut rewriter = SyntaxRewriter::default();
-    let use_item = make::use_(None, make::use_tree(path.clone(), None, None, false));
+    let use_item =
+        make::use_(None, make::use_tree(path.clone(), None, None, false)).clone_for_update();
     // merge into existing imports if possible
     if let Some(mb) = cfg.merge {
         for existing_use in scope.as_syntax_node().children().filter_map(ast::Use::cast) {
             if let Some(merged) = try_merge_imports(&existing_use, &use_item, mb) {
-                rewriter.replace(existing_use.syntax(), merged.syntax());
-                return rewriter;
+                ted::replace(existing_use.syntax(), merged.syntax());
+                return;
             }
         }
     }
 
     // either we weren't allowed to merge or there is no import that fits the merge conditions
     // so look for the place we have to insert to
-    let (insert_position, add_blank) = find_insert_position(scope, path, cfg.group);
-
-    let indent = if let ident_level @ 1..=usize::MAX = scope.indent_level().0 as usize {
-        Some(make::tokens::whitespace(&" ".repeat(4 * ident_level)).into())
-    } else {
-        None
-    };
-
-    let to_insert: Vec<SyntaxElement> = {
-        let mut buf = Vec::new();
-
-        match add_blank {
-            AddBlankLine::Before | AddBlankLine::Around => {
-                buf.push(make::tokens::single_newline().into())
-            }
-            AddBlankLine::BeforeTwice => buf.push(make::tokens::blank_line().into()),
-            _ => (),
-        }
-
-        if add_blank.has_before() {
-            if let Some(indent) = indent.clone() {
-                cov_mark::hit!(insert_use_indent_before);
-                buf.push(indent);
-            }
-        }
-
-        buf.push(use_item.syntax().clone().into());
-
-        match add_blank {
-            AddBlankLine::After | AddBlankLine::Around => {
-                buf.push(make::tokens::single_newline().into())
-            }
-            AddBlankLine::AfterTwice => buf.push(make::tokens::blank_line().into()),
-            _ => (),
-        }
-
-        // only add indentation *after* our stuff if there's another node directly after it
-        if add_blank.has_after() && matches!(insert_position, InsertPosition::Before(_)) {
-            if let Some(indent) = indent {
-                cov_mark::hit!(insert_use_indent_after);
-                buf.push(indent);
-            }
-        } else if add_blank.has_after() && matches!(insert_position, InsertPosition::After(_)) {
-            cov_mark::hit!(insert_use_no_indent_after);
-        }
-
-        buf
-    };
-
-    match insert_position {
-        InsertPosition::First => {
-            rewriter.insert_many_as_first_children(scope.as_syntax_node(), to_insert)
-        }
-        InsertPosition::Last => return rewriter, // actually unreachable
-        InsertPosition::Before(anchor) => rewriter.insert_many_before(&anchor, to_insert),
-        InsertPosition::After(anchor) => rewriter.insert_many_after(&anchor, to_insert),
-    }
-    rewriter
-}
-
-fn eq_visibility(vis0: Option<ast::Visibility>, vis1: Option<ast::Visibility>) -> bool {
-    match (vis0, vis1) {
-        (None, None) => true,
-        // FIXME: Don't use the string representation to check for equality
-        // spaces inside of the node would break this comparison
-        (Some(vis0), Some(vis1)) => vis0.to_string() == vis1.to_string(),
-        _ => false,
-    }
-}
-
-fn eq_attrs(
-    attrs0: impl Iterator<Item = ast::Attr>,
-    attrs1: impl Iterator<Item = ast::Attr>,
-) -> bool {
-    let attrs0 = attrs0.map(|attr| attr.to_string());
-    let attrs1 = attrs1.map(|attr| attr.to_string());
-    attrs0.eq(attrs1)
-}
-
-pub fn try_merge_imports(
-    lhs: &ast::Use,
-    rhs: &ast::Use,
-    merge_behavior: MergeBehavior,
-) -> Option<ast::Use> {
-    // don't merge imports with different visibilities
-    if !eq_visibility(lhs.visibility(), rhs.visibility()) {
-        return None;
-    }
-    if !eq_attrs(lhs.attrs(), rhs.attrs()) {
-        return None;
-    }
-
-    let lhs_tree = lhs.use_tree()?;
-    let rhs_tree = rhs.use_tree()?;
-    let merged = try_merge_trees(&lhs_tree, &rhs_tree, merge_behavior)?;
-    Some(lhs.with_use_tree(merged).clone_for_update())
-}
-
-pub fn try_merge_trees(
-    lhs: &ast::UseTree,
-    rhs: &ast::UseTree,
-    merge: MergeBehavior,
-) -> Option<ast::UseTree> {
-    let lhs_path = lhs.path()?;
-    let rhs_path = rhs.path()?;
-
-    let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
-    let (lhs, rhs) = if is_simple_path(lhs)
-        && is_simple_path(rhs)
-        && lhs_path == lhs_prefix
-        && rhs_path == rhs_prefix
-    {
-        (lhs.clone(), rhs.clone())
-    } else {
-        (lhs.split_prefix(&lhs_prefix), rhs.split_prefix(&rhs_prefix))
-    };
-    recursive_merge(&lhs, &rhs, merge).map(|it| it.clone_for_update())
-}
-
-/// Recursively "zips" together lhs and rhs.
-fn recursive_merge(
-    lhs: &ast::UseTree,
-    rhs: &ast::UseTree,
-    merge: MergeBehavior,
-) -> Option<ast::UseTree> {
-    let mut use_trees = lhs
-        .use_tree_list()
-        .into_iter()
-        .flat_map(|list| list.use_trees())
-        // 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_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(|lhs_t| {
-            let (lhs_t, rhs_t) = match lhs_t
-                .path()
-                .zip(rhs_path.clone())
-                .and_then(|(lhs, rhs)| common_prefix(&lhs, &rhs))
-            {
-                Some((lhs_p, rhs_p)) => (lhs_t.split_prefix(&lhs_p), rhs_t.split_prefix(&rhs_p)),
-                None => (lhs_t.clone(), rhs_t.clone()),
-            };
-
-            path_cmp_bin_search(lhs_t.path(), rhs_t.path())
-        }) {
-            Ok(idx) => {
-                let lhs_t = &mut use_trees[idx];
-                let lhs_path = lhs_t.path()?;
-                let rhs_path = rhs_path?;
-                let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
-                if lhs_prefix == lhs_path && rhs_prefix == rhs_path {
-                    let tree_is_self = |tree: ast::UseTree| {
-                        tree.path().as_ref().map(path_is_self).unwrap_or(false)
-                    };
-                    // check if only one of the two trees has a tree list, and whether that then contains `self` or not.
-                    // 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`
-                    let tree_contains_self = |tree: &ast::UseTree| {
-                        tree.use_tree_list()
-                            .map(|tree_list| tree_list.use_trees().any(tree_is_self))
-                            .unwrap_or(false)
-                    };
-                    match (tree_contains_self(&lhs_t), tree_contains_self(&rhs_t)) {
-                        (true, false) => continue,
-                        (false, true) => {
-                            *lhs_t = rhs_t;
-                            continue;
-                        }
-                        _ => (),
-                    }
-
-                    // glob imports arent part of the use-tree lists so we need to special handle them here as well
-                    // this special handling is only required for when we merge a module import into a glob import of said module
-                    // see the `merge_self_glob` or `merge_mod_into_glob` tests
-                    if lhs_t.star_token().is_some() || rhs_t.star_token().is_some() {
-                        *lhs_t = make::use_tree(
-                            make::path_unqualified(make::path_segment_self()),
-                            None,
-                            None,
-                            false,
-                        );
-                        use_trees.insert(idx, make::glob_use_tree());
-                        continue;
-                    }
-
-                    if lhs_t.use_tree_list().is_none() && rhs_t.use_tree_list().is_none() {
-                        continue;
-                    }
-                }
-                let lhs = lhs_t.split_prefix(&lhs_prefix);
-                let rhs = rhs_t.split_prefix(&rhs_prefix);
-                match recursive_merge(&lhs, &rhs, merge) {
-                    Some(use_tree) => use_trees[idx] = use_tree,
-                    None => return None,
-                }
-            }
-            Err(_)
-                if merge == MergeBehavior::Last
-                    && use_trees.len() > 0
-                    && rhs_t.use_tree_list().is_some() =>
-            {
-                return None
-            }
-            Err(idx) => {
-                use_trees.insert(idx, rhs_t);
-            }
-        }
-    }
-    Some(lhs.with_use_tree_list(make::use_tree_list(use_trees)))
-}
-
-/// Traverses both paths until they differ, returning the common prefix of both.
-fn common_prefix(lhs: &ast::Path, rhs: &ast::Path) -> Option<(ast::Path, ast::Path)> {
-    let mut res = None;
-    let mut lhs_curr = first_path(&lhs);
-    let mut rhs_curr = first_path(&rhs);
-    loop {
-        match (lhs_curr.segment(), rhs_curr.segment()) {
-            (Some(lhs), Some(rhs)) if lhs.syntax().text() == rhs.syntax().text() => (),
-            _ => break res,
-        }
-        res = Some((lhs_curr.clone(), rhs_curr.clone()));
-
-        match lhs_curr.parent_path().zip(rhs_curr.parent_path()) {
-            Some((lhs, rhs)) => {
-                lhs_curr = lhs;
-                rhs_curr = rhs;
-            }
-            _ => break res,
-        }
-    }
-}
-
-fn is_simple_path(use_tree: &ast::UseTree) -> bool {
-    use_tree.use_tree_list().is_none() && use_tree.star_token().is_none()
-}
-
-fn path_is_self(path: &ast::Path) -> bool {
-    path.segment().and_then(|seg| seg.self_token()).is_some() && path.qualifier().is_none()
-}
-
-#[inline]
-fn first_segment(path: &ast::Path) -> Option<ast::PathSegment> {
-    first_path(path).segment()
-}
-
-fn first_path(path: &ast::Path) -> ast::Path {
-    successors(Some(path.clone()), ast::Path::qualifier).last().unwrap()
-}
-
-fn segment_iter(path: &ast::Path) -> impl Iterator<Item = ast::PathSegment> + Clone {
-    // cant make use of SyntaxNode::siblings, because the returned Iterator is not clone
-    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 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_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),
-        },
-    }
-}
-
-/// Path comparison func for binary searching for merging.
-fn path_cmp_bin_search(lhs: Option<ast::Path>, rhs: Option<ast::Path>) -> Ordering {
-    match (lhs.as_ref().and_then(first_segment), rhs.as_ref().and_then(first_segment)) {
-        (None, None) => Ordering::Equal,
-        (None, Some(_)) => Ordering::Less,
-        (Some(_), None) => Ordering::Greater,
-        (Some(ref a), Some(ref b)) => path_segment_cmp(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.kind().and_then(|kind| match kind {
-        PathSegmentKind::Name(name_ref) => Some(name_ref),
-        _ => None,
-    });
-    let b = b.kind().and_then(|kind| match kind {
-        PathSegmentKind::Name(name_ref) => Some(name_ref),
-        _ => None,
-    });
-    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 MergeBehavior {
-    /// Merge everything together creating deeply nested imports.
-    Full,
-    /// Only merge the last import level, doesn't allow import nesting.
-    Last,
-}
-
-impl MergeBehavior {
-    #[inline]
-    fn is_tree_allowed(&self, tree: &ast::UseTree) -> bool {
-        match self {
-            MergeBehavior::Full => true,
-            // only simple single segment paths are allowed
-            MergeBehavior::Last => {
-                tree.use_tree_list().is_none() && tree.path().map(path_len) <= Some(1)
-            }
-        }
-    }
+    insert_use_(scope, path, cfg.group, use_item);
 }
 
 #[derive(Eq, PartialEq, PartialOrd, Ord)]
@@ -500,7 +101,7 @@ impl ImportGroup {
     fn new(path: &ast::Path) -> ImportGroup {
         let default = ImportGroup::ExternCrate;
 
-        let first_segment = match first_segment(path) {
+        let first_segment = match path.first_segment() {
             Some(it) => it,
             None => return default,
         };
@@ -520,32 +121,15 @@ impl ImportGroup {
     }
 }
 
-#[derive(PartialEq, Eq)]
-enum AddBlankLine {
-    Before,
-    BeforeTwice,
-    Around,
-    After,
-    AfterTwice,
-}
-
-impl AddBlankLine {
-    fn has_before(&self) -> bool {
-        matches!(self, AddBlankLine::Before | AddBlankLine::BeforeTwice | AddBlankLine::Around)
-    }
-    fn has_after(&self) -> bool {
-        matches!(self, AddBlankLine::After | AddBlankLine::AfterTwice | AddBlankLine::Around)
-    }
-}
-
-fn find_insert_position(
+fn insert_use_(
     scope: &ImportScope,
     insert_path: ast::Path,
     group_imports: bool,
-) -> (InsertPosition<SyntaxElement>, AddBlankLine) {
+    use_item: ast::Use,
+) {
+    let scope_syntax = scope.as_syntax_node();
     let group = ImportGroup::new(&insert_path);
-    let path_node_iter = scope
-        .as_syntax_node()
+    let path_node_iter = scope_syntax
         .children()
         .filter_map(|node| ast::Use::cast(node.clone()).zip(Some(node)))
         .flat_map(|(use_, node)| {
@@ -557,9 +141,14 @@ fn find_insert_position(
 
     if !group_imports {
         if let Some((_, _, node)) = path_node_iter.last() {
-            return (InsertPosition::After(node.into()), AddBlankLine::Before);
+            cov_mark::hit!(insert_no_grouping_last);
+            ted::insert(ted::Position::after(node), use_item.syntax());
+        } else {
+            cov_mark::hit!(insert_no_grouping_last2);
+            ted::insert(ted::Position::first_child_of(scope_syntax), make::tokens::blank_line());
+            ted::insert(ted::Position::first_child_of(scope_syntax), use_item.syntax());
         }
-        return (InsertPosition::First, AddBlankLine::AfterTwice);
+        return;
     }
 
     // Iterator that discards anything thats not in the required grouping
@@ -572,43 +161,91 @@ fn find_insert_position(
     // 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(
-        |&(ref path, has_tl, _)| {
+    let post_insert: Option<(_, _, SyntaxNode)> = 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 {
+    if let Some((.., node)) = post_insert {
+        cov_mark::hit!(insert_group);
         // insert our import before that element
-        Some((.., node)) => (InsertPosition::Before(node.into()), AddBlankLine::After),
+        return ted::insert(ted::Position::before(node), use_item.syntax());
+    }
+    if let Some(node) = last {
+        cov_mark::hit!(insert_group_last);
         // 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),
-            // the group we were looking for actually doesnt exist, so insert
+        return ted::insert(ted::Position::after(node), use_item.syntax());
+    }
+
+    // the group we were looking for actually doesn't exist, so insert
+
+    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);
+    if let Some((.., node)) = post_group {
+        cov_mark::hit!(insert_group_new_group);
+        ted::insert(ted::Position::before(&node), use_item.syntax());
+        if let Some(node) = algo::non_trivia_sibling(node.into(), Direction::Prev) {
+            ted::insert(ted::Position::after(node), make::tokens::single_newline());
+        }
+        return;
+    }
+    // there is no such group, so append after the last one
+    if let Some(node) = last {
+        cov_mark::hit!(insert_group_no_group);
+        ted::insert(ted::Position::after(&node), use_item.syntax());
+        ted::insert(ted::Position::after(node), make::tokens::single_newline());
+        return;
+    }
+    // there are no imports in this file at all
+    if let Some(last_inner_element) = scope_syntax
+        .children_with_tokens()
+        .filter(|child| match child {
+            NodeOrToken::Node(node) => is_inner_attribute(node.clone()),
+            NodeOrToken::Token(token) => is_inner_comment(token.clone()),
+        })
+        .last()
+    {
+        cov_mark::hit!(insert_group_empty_inner_attr);
+        ted::insert(ted::Position::after(&last_inner_element), use_item.syntax());
+        ted::insert(ted::Position::after(last_inner_element), make::tokens::single_newline());
+        return;
+    }
+    match scope {
+        ImportScope::File(_) => {
+            cov_mark::hit!(insert_group_empty_file);
+            ted::insert(ted::Position::first_child_of(scope_syntax), make::tokens::blank_line());
+            ted::insert(ted::Position::first_child_of(scope_syntax), use_item.syntax())
+        }
+        // don't insert the imports before the item list's opening curly brace
+        ImportScope::Module(item_list) => match item_list.l_curly_token() {
+            Some(b) => {
+                cov_mark::hit!(insert_group_empty_module);
+                ted::insert(ted::Position::after(&b), make::tokens::single_newline());
+                ted::insert(ted::Position::after(&b), use_item.syntax());
+            }
             None => {
-                // similar concept here to the `last` from above
-                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);
-                match post_group {
-                    Some((.., node)) => {
-                        (InsertPosition::Before(node.into()), AddBlankLine::AfterTwice)
-                    }
-                    // there is no such group, so append after the last one
-                    None => match last {
-                        Some(node) => {
-                            (InsertPosition::After(node.into()), AddBlankLine::BeforeTwice)
-                        }
-                        // there are no imports in this file at all
-                        None => scope.insert_pos_after_last_inner_element(),
-                    },
-                }
+                // This should never happens, broken module syntax node
+                ted::insert(
+                    ted::Position::first_child_of(scope_syntax),
+                    make::tokens::blank_line(),
+                );
+                ted::insert(ted::Position::first_child_of(scope_syntax), use_item.syntax());
             }
         },
     }
 }
 
+fn is_inner_attribute(node: SyntaxNode) -> bool {
+    ast::Attr::cast(node).map(|attr| attr.kind()) == Some(ast::AttrKind::Inner)
+}
+
+fn is_inner_comment(token: SyntaxToken) -> bool {
+    ast::Comment::cast(token).and_then(|comment| comment.kind().doc)
+        == Some(ast::CommentPlacement::Inner)
+}
 #[cfg(test)]
 mod tests;
diff --git a/crates/ide_db/src/helpers/insert_use/tests.rs b/crates/ide_db/src/helpers/insert_use/tests.rs
index 3d151e629..048c213e2 100644
--- a/crates/ide_db/src/helpers/insert_use/tests.rs
+++ b/crates/ide_db/src/helpers/insert_use/tests.rs
@@ -5,6 +5,7 @@ use test_utils::assert_eq_text;
 
 #[test]
 fn insert_not_group() {
+    cov_mark::check!(insert_no_grouping_last);
     check(
         "use external_crate2::bar::A",
         r"
@@ -27,6 +28,21 @@ use external_crate2::bar::A;",
 }
 
 #[test]
+fn insert_not_group_empty() {
+    cov_mark::check!(insert_no_grouping_last2);
+    check(
+        "use external_crate2::bar::A",
+        r"",
+        r"use external_crate2::bar::A;
+
+",
+        None,
+        false,
+        false,
+    );
+}
+
+#[test]
 fn insert_existing() {
     check_full("std::fs", "use std::fs;", "use std::fs;")
 }
@@ -51,21 +67,21 @@ use std::bar::G;",
 
 #[test]
 fn insert_start_indent() {
-    cov_mark::check!(insert_use_indent_after);
     check_none(
         "std::bar::AA",
         r"
     use std::bar::B;
-    use std::bar::D;",
+    use std::bar::C;",
         r"
     use std::bar::AA;
     use std::bar::B;
-    use std::bar::D;",
-    )
+    use std::bar::C;",
+    );
 }
 
 #[test]
 fn insert_middle() {
+    cov_mark::check!(insert_group);
     check_none(
         "std::bar::EE",
         r"
@@ -102,6 +118,7 @@ fn insert_middle_indent() {
 
 #[test]
 fn insert_end() {
+    cov_mark::check!(insert_group_last);
     check_none(
         "std::bar::ZZ",
         r"
@@ -120,7 +137,6 @@ use std::bar::ZZ;",
 
 #[test]
 fn insert_end_indent() {
-    cov_mark::check!(insert_use_indent_before);
     check_none(
         "std::bar::ZZ",
         r"
@@ -201,6 +217,7 @@ fn insert_first_matching_group() {
 
 #[test]
 fn insert_missing_group_std() {
+    cov_mark::check!(insert_group_new_group);
     check_none(
         "std::fmt",
         r"
@@ -216,6 +233,7 @@ fn insert_missing_group_std() {
 
 #[test]
 fn insert_missing_group_self() {
+    cov_mark::check!(insert_group_no_group);
     check_none(
         "self::fmt",
         r"
@@ -242,6 +260,7 @@ fn main() {}",
 
 #[test]
 fn insert_empty_file() {
+    cov_mark::check!(insert_group_empty_file);
     // empty files will get two trailing newlines
     // this is due to the test case insert_no_imports above
     check_full(
@@ -255,7 +274,7 @@ fn insert_empty_file() {
 
 #[test]
 fn insert_empty_module() {
-    cov_mark::check!(insert_use_no_indent_after);
+    cov_mark::check!(insert_group_empty_module);
     check(
         "foo::bar",
         "mod x {}",
@@ -270,6 +289,7 @@ fn insert_empty_module() {
 
 #[test]
 fn insert_after_inner_attr() {
+    cov_mark::check!(insert_group_empty_inner_attr);
     check_full(
         "foo::bar",
         r"#![allow(unused_imports)]",
@@ -615,7 +635,7 @@ fn check(
     if module {
         syntax = syntax.descendants().find_map(ast::Module::cast).unwrap().syntax().clone();
     }
-    let file = super::ImportScope::from(syntax).unwrap();
+    let file = super::ImportScope::from(syntax.clone_for_update()).unwrap();
     let path = ast::SourceFile::parse(&format!("use {};", path))
         .tree()
         .syntax()
@@ -623,12 +643,8 @@ fn check(
         .find_map(ast::Path::cast)
         .unwrap();
 
-    let rewriter = insert_use(
-        &file,
-        path,
-        InsertUseConfig { merge: mb, prefix_kind: PrefixKind::Plain, group },
-    );
-    let result = rewriter.rewrite(file.as_syntax_node()).to_string();
+    insert_use(&file, path, InsertUseConfig { merge: mb, prefix_kind: PrefixKind::Plain, group });
+    let result = file.as_syntax_node().to_string();
     assert_eq_text!(ra_fixture_after, &result);
 }
 
diff --git a/crates/ide_db/src/helpers/merge_imports.rs b/crates/ide_db/src/helpers/merge_imports.rs
new file mode 100644
index 000000000..3f5bbef7f
--- /dev/null
+++ b/crates/ide_db/src/helpers/merge_imports.rs
@@ -0,0 +1,309 @@
+//! Handle syntactic aspects of merging UseTrees.
+use std::cmp::Ordering;
+
+use itertools::{EitherOrBoth, Itertools};
+use syntax::ast::{
+    self, edit::AstNodeEdit, make, AstNode, AttrsOwner, PathSegmentKind, VisibilityOwner,
+};
+
+/// What type of merges are allowed.
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub enum MergeBehavior {
+    /// Merge everything together creating deeply nested imports.
+    Full,
+    /// Only merge the last import level, doesn't allow import nesting.
+    Last,
+}
+
+impl MergeBehavior {
+    #[inline]
+    fn is_tree_allowed(&self, tree: &ast::UseTree) -> bool {
+        match self {
+            MergeBehavior::Full => true,
+            // only simple single segment paths are allowed
+            MergeBehavior::Last => {
+                tree.use_tree_list().is_none() && tree.path().map(path_len) <= Some(1)
+            }
+        }
+    }
+}
+
+pub fn try_merge_imports(
+    lhs: &ast::Use,
+    rhs: &ast::Use,
+    merge_behavior: MergeBehavior,
+) -> Option<ast::Use> {
+    // don't merge imports with different visibilities
+    if !eq_visibility(lhs.visibility(), rhs.visibility()) {
+        return None;
+    }
+    if !eq_attrs(lhs.attrs(), rhs.attrs()) {
+        return None;
+    }
+
+    let lhs_tree = lhs.use_tree()?;
+    let rhs_tree = rhs.use_tree()?;
+    let merged = try_merge_trees(&lhs_tree, &rhs_tree, merge_behavior)?;
+    Some(lhs.with_use_tree(merged).clone_for_update())
+}
+
+pub fn try_merge_trees(
+    lhs: &ast::UseTree,
+    rhs: &ast::UseTree,
+    merge: MergeBehavior,
+) -> Option<ast::UseTree> {
+    let lhs_path = lhs.path()?;
+    let rhs_path = rhs.path()?;
+
+    let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
+    let (lhs, rhs) = if lhs.is_simple_path()
+        && rhs.is_simple_path()
+        && lhs_path == lhs_prefix
+        && rhs_path == rhs_prefix
+    {
+        (lhs.clone(), rhs.clone())
+    } else {
+        (lhs.split_prefix(&lhs_prefix), rhs.split_prefix(&rhs_prefix))
+    };
+    recursive_merge(&lhs, &rhs, merge)
+}
+
+/// Recursively "zips" together lhs and rhs.
+fn recursive_merge(
+    lhs: &ast::UseTree,
+    rhs: &ast::UseTree,
+    merge: MergeBehavior,
+) -> Option<ast::UseTree> {
+    let mut use_trees = lhs
+        .use_tree_list()
+        .into_iter()
+        .flat_map(|list| list.use_trees())
+        // 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_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(|lhs_t| {
+            let (lhs_t, rhs_t) = match lhs_t
+                .path()
+                .zip(rhs_path.clone())
+                .and_then(|(lhs, rhs)| common_prefix(&lhs, &rhs))
+            {
+                Some((lhs_p, rhs_p)) => (lhs_t.split_prefix(&lhs_p), rhs_t.split_prefix(&rhs_p)),
+                None => (lhs_t.clone(), rhs_t.clone()),
+            };
+
+            path_cmp_bin_search(lhs_t.path(), rhs_t.path())
+        }) {
+            Ok(idx) => {
+                let lhs_t = &mut use_trees[idx];
+                let lhs_path = lhs_t.path()?;
+                let rhs_path = rhs_path?;
+                let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
+                if lhs_prefix == lhs_path && rhs_prefix == rhs_path {
+                    let tree_is_self = |tree: ast::UseTree| {
+                        tree.path().as_ref().map(path_is_self).unwrap_or(false)
+                    };
+                    // check if only one of the two trees has a tree list, and whether that then contains `self` or not.
+                    // 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`
+                    let tree_contains_self = |tree: &ast::UseTree| {
+                        tree.use_tree_list()
+                            .map(|tree_list| tree_list.use_trees().any(tree_is_self))
+                            .unwrap_or(false)
+                    };
+                    match (tree_contains_self(&lhs_t), tree_contains_self(&rhs_t)) {
+                        (true, false) => continue,
+                        (false, true) => {
+                            *lhs_t = rhs_t;
+                            continue;
+                        }
+                        _ => (),
+                    }
+
+                    // glob imports arent part of the use-tree lists so we need to special handle them here as well
+                    // this special handling is only required for when we merge a module import into a glob import of said module
+                    // see the `merge_self_glob` or `merge_mod_into_glob` tests
+                    if lhs_t.star_token().is_some() || rhs_t.star_token().is_some() {
+                        *lhs_t = make::use_tree(
+                            make::path_unqualified(make::path_segment_self()),
+                            None,
+                            None,
+                            false,
+                        );
+                        use_trees.insert(idx, make::glob_use_tree());
+                        continue;
+                    }
+
+                    if lhs_t.use_tree_list().is_none() && rhs_t.use_tree_list().is_none() {
+                        continue;
+                    }
+                }
+                let lhs = lhs_t.split_prefix(&lhs_prefix);
+                let rhs = rhs_t.split_prefix(&rhs_prefix);
+                match recursive_merge(&lhs, &rhs, merge) {
+                    Some(use_tree) => use_trees[idx] = use_tree,
+                    None => return None,
+                }
+            }
+            Err(_)
+                if merge == MergeBehavior::Last
+                    && use_trees.len() > 0
+                    && rhs_t.use_tree_list().is_some() =>
+            {
+                return None
+            }
+            Err(idx) => {
+                use_trees.insert(idx, rhs_t);
+            }
+        }
+    }
+
+    Some(if let Some(old) = lhs.use_tree_list() {
+        lhs.replace_descendant(old, make::use_tree_list(use_trees)).clone_for_update()
+    } else {
+        lhs.clone()
+    })
+}
+
+/// Traverses both paths until they differ, returning the common prefix of both.
+fn common_prefix(lhs: &ast::Path, rhs: &ast::Path) -> Option<(ast::Path, ast::Path)> {
+    let mut res = None;
+    let mut lhs_curr = lhs.first_qualifier_or_self();
+    let mut rhs_curr = rhs.first_qualifier_or_self();
+    loop {
+        match (lhs_curr.segment(), rhs_curr.segment()) {
+            (Some(lhs), Some(rhs)) if lhs.syntax().text() == rhs.syntax().text() => (),
+            _ => break res,
+        }
+        res = Some((lhs_curr.clone(), rhs_curr.clone()));
+
+        match lhs_curr.parent_path().zip(rhs_curr.parent_path()) {
+            Some((lhs, rhs)) => {
+                lhs_curr = lhs;
+                rhs_curr = rhs;
+            }
+            _ => break res,
+        }
+    }
+}
+
+/// Orders paths in the following way:
+/// the sole self token comes first, after that come uppercase identifiers, then lowercase identifiers
+// 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_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),
+        },
+    }
+}
+
+/// Path comparison func for binary searching for merging.
+fn path_cmp_bin_search(lhs: Option<ast::Path>, rhs: Option<ast::Path>) -> Ordering {
+    match (
+        lhs.as_ref().and_then(ast::Path::first_segment),
+        rhs.as_ref().and_then(ast::Path::first_segment),
+    ) {
+        (None, None) => Ordering::Equal,
+        (None, Some(_)) => Ordering::Less,
+        (Some(_), None) => Ordering::Greater,
+        (Some(ref a), Some(ref b)) => path_segment_cmp(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 = a.segments();
+    let b = b.segments();
+    // cmp_by would be useful for us here but that is currently unstable
+    // cmp doesn't 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 two 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.
+pub(super) fn use_tree_path_cmp(
+    a: &ast::Path,
+    a_has_tl: bool,
+    b: &ast::Path,
+    b_has_tl: bool,
+) -> Ordering {
+    let a_segments = a.segments();
+    let b_segments = b.segments();
+    // cmp_by would be useful for us here but that is currently unstable
+    // cmp doesn't 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.kind().and_then(|kind| match kind {
+        PathSegmentKind::Name(name_ref) => Some(name_ref),
+        _ => None,
+    });
+    let b = b.kind().and_then(|kind| match kind {
+        PathSegmentKind::Name(name_ref) => Some(name_ref),
+        _ => None,
+    });
+    a.as_ref().map(ast::NameRef::text).cmp(&b.as_ref().map(ast::NameRef::text))
+}
+
+fn eq_visibility(vis0: Option<ast::Visibility>, vis1: Option<ast::Visibility>) -> bool {
+    match (vis0, vis1) {
+        (None, None) => true,
+        // FIXME: Don't use the string representation to check for equality
+        // spaces inside of the node would break this comparison
+        (Some(vis0), Some(vis1)) => vis0.to_string() == vis1.to_string(),
+        _ => false,
+    }
+}
+
+fn eq_attrs(
+    attrs0: impl Iterator<Item = ast::Attr>,
+    attrs1: impl Iterator<Item = ast::Attr>,
+) -> bool {
+    let attrs0 = attrs0.map(|attr| attr.to_string());
+    let attrs1 = attrs1.map(|attr| attr.to_string());
+    attrs0.eq(attrs1)
+}
+
+fn path_is_self(path: &ast::Path) -> bool {
+    path.segment().and_then(|seg| seg.self_token()).is_some() && path.qualifier().is_none()
+}
+
+fn path_len(path: ast::Path) -> usize {
+    path.segments().count()
+}
diff --git a/crates/ide_db/src/helpers/rust_doc.rs b/crates/ide_db/src/helpers/rust_doc.rs
new file mode 100644
index 000000000..e27e23867
--- /dev/null
+++ b/crates/ide_db/src/helpers/rust_doc.rs
@@ -0,0 +1,34 @@
+//! Rustdoc specific doc comment handling
+
+// stripped down version of https://github.com/rust-lang/rust/blob/392ba2ba1a7d6c542d2459fb8133bebf62a4a423/src/librustdoc/html/markdown.rs#L810-L933
+pub fn is_rust_fence(s: &str) -> bool {
+    let mut seen_rust_tags = false;
+    let mut seen_other_tags = false;
+
+    let tokens = s
+        .trim()
+        .split(|c| c == ',' || c == ' ' || c == '\t')
+        .map(str::trim)
+        .filter(|t| !t.is_empty());
+
+    for token in tokens {
+        match token {
+            "should_panic" | "no_run" | "ignore" | "allow_fail" => {
+                seen_rust_tags = !seen_other_tags
+            }
+            "rust" => seen_rust_tags = true,
+            "test_harness" | "compile_fail" => seen_rust_tags = !seen_other_tags || seen_rust_tags,
+            x if x.starts_with("edition") => {}
+            x if x.starts_with('E') && x.len() == 5 => {
+                if x[1..].parse::<u32>().is_ok() {
+                    seen_rust_tags = !seen_other_tags || seen_rust_tags;
+                } else {
+                    seen_other_tags = true;
+                }
+            }
+            _ => seen_other_tags = true,
+        }
+    }
+
+    !seen_other_tags || seen_rust_tags
+}