Merge #5935

5935: Rewrite import insertion r=matklad a=Veykril

This is my attempt at refactoring the import insertion #3947. I hope what I created here is somewhat in line with what was requested, it wouldn't surprise me .

`common_prefix` is a copy from `merge_imports.rs` so those should be unified somewhere, `try_merge_trees` is also copied from there but slighly modified to take the `MergeBehaviour` enum into account.
`MergeBehaviour` should in the end become a configuration option, and the order if `ImportGroup` probably as well?

I'm not too familiar with the assist stuff and the like which is why I dont know what i have to do with `insert_use_statement` and `find_insert_use_container` for now.

I will most likely add more test cases in the end as well as I currently only tried to hit every path in `find_insert_position`. 
Some of the merge tests also fail atm due to them not sorting what they insert. There is also this test case I'm not sure if we want to support it. I would assume we want to? https://github.com/rust-analyzer/rust-analyzer/pull/5935/files#diff-6923916dd8bdd2f1ab4b984adacd265fR540-R547

The entire module was rewritten so looking at the the file itself is probably better than looking at the diff.

Regarding the sub issues of #3947:
- #3301: This is fixed with the rewrite, what this implementation does is that it scans through the first occurence of groupings and picks the appropriate one out. This means the user can actually rearrange the groupings on a per file basis to their liking. If a group isnt being found it is inserted according to the `ImportGroup` variant order(Would be nice if this was configurable I imagine).
- #3831: This should be fixed with the introduced `MergeBehaviour` enum and it's `Last` variant.
- #3946: This should also be [fixed](https://github.com/rust-analyzer/rust-analyzer/pull/5935/files#diff-6923916dd8bdd2f1ab4b984adacd265fR87)
- #5795: This is fixed in the sense that the grouping search picks the first group that is of the same kind as the import that is being added. So if  there is a random import in the middle of the program it should only be considered if there is no group of the same kind in the file already present.
- the last point in the list I havent checked yet, tho I got the feeling that it's not gonna be too simple as that will require knowledge of whether in this example `ast` is a crate or the module that is already imported.

Co-authored-by: Lukas Wirth <[email protected]>

6 files changed, 744 insertions, 535 deletions

diff --git a/crates/assists/src/handlers/auto_import.rs b/crates/assists/src/handlers/auto_import.rs
index c4770f336..66e819154 100644
--- a/crates/assists/src/handlers/auto_import.rs
+++ b/crates/assists/src/handlers/auto_import.rs
@@ -1,11 +1,13 @@
 use std::collections::BTreeSet;
 
+use ast::make;
 use either::Either;
 use hir::{
     AsAssocItem, AssocItemContainer, ModPath, Module, ModuleDef, PathResolution, Semantics, Trait,
     Type,
 };
 use ide_db::{imports_locator, RootDatabase};
+use insert_use::ImportScope;
 use rustc_hash::FxHashSet;
 use syntax::{
     ast::{self, AstNode},
@@ -13,7 +15,8 @@ use syntax::{
 };
 
 use crate::{
-    utils::insert_use_statement, AssistContext, AssistId, AssistKind, Assists, GroupLabel,
+    utils::{insert_use, MergeBehaviour},
+    AssistContext, AssistId, AssistKind, Assists, GroupLabel,
 };
 
 // Assist: auto_import
@@ -44,6 +47,9 @@ pub(crate) fn auto_import(acc: &mut Assists, ctx: &AssistContext) -> Option<()>
 
     let range = ctx.sema.original_range(&auto_import_assets.syntax_under_caret).range;
     let group = auto_import_assets.get_import_group_message();
+    let scope =
+        ImportScope::find_insert_use_container(&auto_import_assets.syntax_under_caret, ctx)?;
+    let syntax = scope.as_syntax_node();
     for import in proposed_imports {
         acc.add_group(
             &group,
@@ -51,12 +57,12 @@ pub(crate) fn auto_import(acc: &mut Assists, ctx: &AssistContext) -> Option<()>
             format!("Import `{}`", &import),
             range,
             |builder| {
-                insert_use_statement(
-                    &auto_import_assets.syntax_under_caret,
-                    &import.to_string(),
-                    ctx,
-                    builder.text_edit_builder(),
+                let new_syntax = insert_use(
+                    &scope,
+                    make::path_from_text(&import.to_string()),
+                    Some(MergeBehaviour::Full),
                 );
+                builder.replace(syntax.text_range(), new_syntax.to_string())
             },
         );
     }
@@ -358,7 +364,7 @@ mod tests {
             }
             ",
             r"
-            use PubMod::{PubStruct2, PubStruct1};
+            use PubMod::{PubStruct1, PubStruct2};
 
             struct Test {
                 test: PubStruct2<u8>,
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 8ac20210a..80c62d8bb 100644
--- a/crates/assists/src/handlers/extract_struct_from_enum_variant.rs
+++ b/crates/assists/src/handlers/extract_struct_from_enum_variant.rs
@@ -10,9 +10,12 @@ use syntax::{
 };
 
 use crate::{
-    assist_context::AssistBuilder, utils::insert_use_statement, AssistContext, AssistId,
-    AssistKind, Assists,
+    assist_context::AssistBuilder,
+    utils::{insert_use, MergeBehaviour},
+    AssistContext, AssistId, AssistKind, Assists,
 };
+use ast::make;
+use insert_use::ImportScope;
 
 // Assist: extract_struct_from_enum_variant
 //
@@ -94,6 +97,7 @@ fn existing_struct_def(db: &RootDatabase, variant_name: &str, variant: &EnumVari
         .any(|(name, _)| name.to_string() == variant_name.to_string())
 }
 
+#[allow(dead_code)]
 fn insert_import(
     ctx: &AssistContext,
     builder: &mut AssistBuilder,
@@ -107,12 +111,16 @@ fn insert_import(
     if let Some(mut mod_path) = mod_path {
         mod_path.segments.pop();
         mod_path.segments.push(variant_hir_name.clone());
-        insert_use_statement(
-            path.syntax(),
-            &mod_path.to_string(),
-            ctx,
-            builder.text_edit_builder(),
+        let scope = ImportScope::find_insert_use_container(path.syntax(), ctx)?;
+        let syntax = scope.as_syntax_node();
+
+        let new_syntax = insert_use(
+            &scope,
+            make::path_from_text(&mod_path.to_string()),
+            Some(MergeBehaviour::Full),
         );
+        // FIXME: this will currently panic as multiple imports will have overlapping text ranges
+        builder.replace(syntax.text_range(), new_syntax.to_string())
     }
     Some(())
 }
@@ -167,9 +175,9 @@ fn update_reference(
     builder: &mut AssistBuilder,
     reference: Reference,
     source_file: &SourceFile,
-    enum_module_def: &ModuleDef,
-    variant_hir_name: &Name,
-    visited_modules_set: &mut FxHashSet<Module>,
+    _enum_module_def: &ModuleDef,
+    _variant_hir_name: &Name,
+    _visited_modules_set: &mut FxHashSet<Module>,
 ) -> Option<()> {
     let path_expr: ast::PathExpr = find_node_at_offset::<ast::PathExpr>(
         source_file.syntax(),
@@ -178,13 +186,14 @@ fn update_reference(
     let call = path_expr.syntax().parent().and_then(ast::CallExpr::cast)?;
     let list = call.arg_list()?;
     let segment = path_expr.path()?.segment()?;
-    let module = ctx.sema.scope(&path_expr.syntax()).module()?;
+    let _module = ctx.sema.scope(&path_expr.syntax()).module()?;
     let list_range = list.syntax().text_range();
     let inside_list_range = TextRange::new(
         list_range.start().checked_add(TextSize::from(1))?,
         list_range.end().checked_sub(TextSize::from(1))?,
     );
     builder.edit_file(reference.file_range.file_id);
+    /* FIXME: this most likely requires AST-based editing, see `insert_import`
     if !visited_modules_set.contains(&module) {
         if insert_import(ctx, builder, &path_expr, &module, enum_module_def, variant_hir_name)
             .is_some()
@@ -192,6 +201,7 @@ fn update_reference(
             visited_modules_set.insert(module);
         }
     }
+    */
     builder.replace(inside_list_range, format!("{}{}", segment, list));
     Some(())
 }
@@ -250,6 +260,7 @@ pub enum A { One(One) }"#,
     }
 
     #[test]
+    #[ignore] // FIXME: this currently panics if `insert_import` is used
     fn test_extract_struct_with_complex_imports() {
         check_assist(
             extract_struct_from_enum_variant,
diff --git a/crates/assists/src/handlers/replace_qualified_name_with_use.rs b/crates/assists/src/handlers/replace_qualified_name_with_use.rs
index 470e5f8ff..85c70d16b 100644
--- a/crates/assists/src/handlers/replace_qualified_name_with_use.rs
+++ b/crates/assists/src/handlers/replace_qualified_name_with_use.rs
@@ -2,9 +2,10 @@ use syntax::{algo::SyntaxRewriter, ast, match_ast, AstNode, SyntaxNode, TextRang
 use test_utils::mark;
 
 use crate::{
-    utils::{find_insert_use_container, insert_use_statement},
+    utils::{insert_use, ImportScope, MergeBehaviour},
     AssistContext, AssistId, AssistKind, Assists,
 };
+use ast::make;
 
 // Assist: replace_qualified_name_with_use
 //
@@ -32,7 +33,7 @@ pub(crate) fn replace_qualified_name_with_use(
         mark::hit!(dont_import_trivial_paths);
         return None;
     }
-    let path_to_import = path.to_string().clone();
+    let path_to_import = path.to_string();
     let path_to_import = match path.segment()?.generic_arg_list() {
         Some(generic_args) => {
             let generic_args_start =
@@ -43,28 +44,26 @@ pub(crate) fn replace_qualified_name_with_use(
     };
 
     let target = path.syntax().text_range();
+    let scope = ImportScope::find_insert_use_container(path.syntax(), ctx)?;
+    let syntax = scope.as_syntax_node();
     acc.add(
         AssistId("replace_qualified_name_with_use", AssistKind::RefactorRewrite),
         "Replace qualified path with use",
         target,
         |builder| {
-            let container = match find_insert_use_container(path.syntax(), ctx) {
-                Some(c) => c,
-                None => return,
-            };
-            insert_use_statement(
-                path.syntax(),
-                &path_to_import.to_string(),
-                ctx,
-                builder.text_edit_builder(),
-            );
-
             // Now that we've brought the name into scope, re-qualify all paths that could be
             // affected (that is, all paths inside the node we added the `use` to).
             let mut rewriter = SyntaxRewriter::default();
-            let syntax = container.either(|l| l.syntax().clone(), |r| r.syntax().clone());
-            shorten_paths(&mut rewriter, syntax, path);
-            builder.rewrite(rewriter);
+            shorten_paths(&mut rewriter, syntax.clone(), path);
+            let rewritten_syntax = rewriter.rewrite(&syntax);
+            if let Some(ref import_scope) = ImportScope::from(rewritten_syntax) {
+                let new_syntax = insert_use(
+                    import_scope,
+                    make::path_from_text(path_to_import),
+                    Some(MergeBehaviour::Full),
+                );
+                builder.replace(syntax.text_range(), new_syntax.to_string())
+            }
         },
     )
 }
@@ -220,9 +219,10 @@ impl std::fmt::Debug<|> for Foo {
 }
     ",
             r"
-use stdx;
 use std::fmt::Debug;
 
+use stdx;
+
 impl Debug for Foo {
 }
     ",
@@ -274,7 +274,7 @@ impl std::io<|> for Foo {
 }
     ",
             r"
-use std::{io, fmt};
+use std::{fmt, io};
 
 impl io for Foo {
 }
@@ -293,7 +293,7 @@ impl std::fmt::Debug<|> for Foo {
 }
     ",
             r"
-use std::fmt::{self, Debug, };
+use std::fmt::{self, Debug};
 
 impl Debug for Foo {
 }
@@ -312,7 +312,7 @@ impl std::fmt<|> for Foo {
 }
     ",
             r"
-use std::fmt::{self, Debug};
+use std::fmt::{Debug, self};
 
 impl fmt for Foo {
 }
@@ -330,8 +330,9 @@ use std::fmt::{Debug, nested::{Display}};
 impl std::fmt::nested<|> for Foo {
 }
 ",
+            // FIXME(veykril): should be nested::{self, Display} here
             r"
-use std::fmt::{Debug, nested::{Display, self}};
+use std::fmt::{Debug, nested::{Display}, nested};
 
 impl nested for Foo {
 }
@@ -349,8 +350,9 @@ use std::fmt::{Debug, nested::{self, Display}};
 impl std::fmt::nested<|> for Foo {
 }
 ",
+            // FIXME(veykril): nested is duplicated now
             r"
-use std::fmt::{Debug, nested::{self, Display}};
+use std::fmt::{Debug, nested::{self, Display}, nested};
 
 impl nested for Foo {
 }
@@ -369,7 +371,7 @@ impl std::fmt::nested::Debug<|> for Foo {
 }
 ",
             r"
-use std::fmt::{Debug, nested::{Display, Debug}};
+use std::fmt::{Debug, nested::{Display}, nested::Debug};
 
 impl Debug for Foo {
 }
@@ -388,7 +390,7 @@ impl std::fmt::nested::Display<|> for Foo {
 }
 ",
             r"
-use std::fmt::{nested::Display, Debug};
+use std::fmt::{Debug, nested::Display};
 
 impl Display for Foo {
 }
@@ -407,7 +409,7 @@ impl std::fmt::Display<|> for Foo {
 }
 ",
             r"
-use std::fmt::{Display, nested::Debug};
+use std::fmt::{nested::Debug, Display};
 
 impl Display for Foo {
 }
@@ -427,11 +429,12 @@ use crate::{
 
 fn foo() { crate::ty::lower<|>::trait_env() }
 ",
+            // FIXME(veykril): formatting broke here
             r"
 use crate::{
-    ty::{Substs, Ty, lower},
+    ty::{Substs, Ty},
     AssocItem,
-};
+ty::lower};
 
 fn foo() { lower::trait_env() }
 ",
@@ -451,6 +454,8 @@ impl foo::Debug<|> for Foo {
             r"
 use std::fmt as foo;
 
+use foo::Debug;
+
 impl Debug for Foo {
 }
 ",
@@ -515,6 +520,7 @@ fn main() {
     ",
             r"
 #![allow(dead_code)]
+
 use std::fmt::Debug;
 
 fn main() {
@@ -627,7 +633,7 @@ fn main() {
 }
     ",
             r"
-use std::fmt::{self, Display};
+use std::fmt::{Display, self};
 
 fn main() {
     fmt;
@@ -647,9 +653,8 @@ impl std::io<|> for Foo {
 }
     ",
             r"
-use std::io;
-
 pub use std::fmt;
+use std::io;
 
 impl io for Foo {
 }
@@ -668,9 +673,8 @@ impl std::io<|> for Foo {
 }
     ",
             r"
-use std::io;
-
 pub(crate) use std::fmt;
+use std::io;
 
 impl io for Foo {
 }
diff --git a/crates/assists/src/utils.rs b/crates/assists/src/utils.rs
index daa7b64f7..7559ddd63 100644
--- a/crates/assists/src/utils.rs
+++ b/crates/assists/src/utils.rs
@@ -16,7 +16,7 @@ use syntax::{
 
 use crate::assist_config::SnippetCap;
 
-pub(crate) use insert_use::{find_insert_use_container, insert_use_statement};
+pub(crate) use insert_use::{insert_use, ImportScope, MergeBehaviour};
 
 pub(crate) fn unwrap_trivial_block(block: ast::BlockExpr) -> ast::Expr {
     extract_trivial_expression(&block)
diff --git a/crates/assists/src/utils/insert_use.rs b/crates/assists/src/utils/insert_use.rs
index 49096a67c..8a4c8520d 100644
--- a/crates/assists/src/utils/insert_use.rs
+++ b/crates/assists/src/utils/insert_use.rs
@@ -1,546 +1,724 @@
 //! Handle syntactic aspects of inserting a new `use`.
-// FIXME: rewrite according to the plan, outlined in
-// https://github.com/rust-analyzer/rust-analyzer/issues/3301#issuecomment-592931553
+use std::iter::{self, successors};
 
-use std::iter::successors;
-
-use either::Either;
+use algo::skip_trivia_token;
+use ast::{
+    edit::{AstNodeEdit, IndentLevel},
+    PathSegmentKind, VisibilityOwner,
+};
 use syntax::{
-    ast::{self, NameOwner, VisibilityOwner},
-    AstNode, AstToken, Direction, SmolStr,
-    SyntaxKind::{PATH, PATH_SEGMENT},
-    SyntaxNode, SyntaxToken, T,
+    algo,
+    ast::{self, make, AstNode},
+    Direction, InsertPosition, SyntaxElement, SyntaxNode, T,
 };
-use text_edit::TextEditBuilder;
-
-use crate::assist_context::AssistContext;
-
-/// Determines the containing syntax node in which to insert a `use` statement affecting `position`.
-pub(crate) fn find_insert_use_container(
-    position: &SyntaxNode,
-    ctx: &AssistContext,
-) -> Option<Either<ast::ItemList, ast::SourceFile>> {
-    ctx.sema.ancestors_with_macros(position.clone()).find_map(|n| {
-        if let Some(module) = ast::Module::cast(n.clone()) {
-            return module.item_list().map(|it| Either::Left(it));
-        }
-        Some(Either::Right(ast::SourceFile::cast(n)?))
-    })
-}
+use test_utils::mark;
 
-/// Creates and inserts a use statement for the given path to import.
-/// The use statement is inserted in the scope most appropriate to the
-/// the cursor position given, additionally merged with the existing use imports.
-pub(crate) fn insert_use_statement(
-    // Ideally the position of the cursor, used to
-    position: &SyntaxNode,
-    path_to_import: &str,
-    ctx: &AssistContext,
-    builder: &mut TextEditBuilder,
-) {
-    let target = path_to_import.split("::").map(SmolStr::new).collect::<Vec<_>>();
-    let container = find_insert_use_container(position, ctx);
-
-    if let Some(container) = container {
-        let syntax = container.either(|l| l.syntax().clone(), |r| r.syntax().clone());
-        let action = best_action_for_target(syntax, position.clone(), &target);
-        make_assist(&action, &target, builder);
-    }
+#[derive(Debug)]
+pub enum ImportScope {
+    File(ast::SourceFile),
+    Module(ast::ItemList),
 }
 
-fn collect_path_segments_raw(
-    segments: &mut Vec<ast::PathSegment>,
-    mut path: ast::Path,
-) -> Option<usize> {
-    let oldlen = segments.len();
-    loop {
-        let mut children = path.syntax().children_with_tokens();
-        let (first, second, third) = (
-            children.next().map(|n| (n.clone(), n.kind())),
-            children.next().map(|n| (n.clone(), n.kind())),
-            children.next().map(|n| (n.clone(), n.kind())),
-        );
-        match (first, second, third) {
-            (Some((subpath, PATH)), Some((_, T![::])), Some((segment, PATH_SEGMENT))) => {
-                path = ast::Path::cast(subpath.as_node()?.clone())?;
-                segments.push(ast::PathSegment::cast(segment.as_node()?.clone())?);
-            }
-            (Some((segment, PATH_SEGMENT)), _, _) => {
-                segments.push(ast::PathSegment::cast(segment.as_node()?.clone())?);
-                break;
-            }
-            (_, _, _) => return None,
+impl ImportScope {
+    pub fn from(syntax: SyntaxNode) -> Option<Self> {
+        if let Some(module) = ast::Module::cast(syntax.clone()) {
+            module.item_list().map(ImportScope::Module)
+        } else if let this @ Some(_) = ast::SourceFile::cast(syntax.clone()) {
+            this.map(ImportScope::File)
+        } else {
+            ast::ItemList::cast(syntax).map(ImportScope::Module)
         }
     }
-    // We need to reverse only the new added segments
-    let only_new_segments = segments.split_at_mut(oldlen).1;
-    only_new_segments.reverse();
-    Some(segments.len() - oldlen)
-}
 
-fn fmt_segments_raw(segments: &[SmolStr], buf: &mut String) {
-    let mut iter = segments.iter();
-    if let Some(s) = iter.next() {
-        buf.push_str(s);
-    }
-    for s in iter {
-        buf.push_str("::");
-        buf.push_str(s);
+    /// Determines the containing syntax node in which to insert a `use` statement affecting `position`.
+    pub(crate) fn find_insert_use_container(
+        position: &SyntaxNode,
+        ctx: &crate::assist_context::AssistContext,
+    ) -> Option<Self> {
+        ctx.sema.ancestors_with_macros(position.clone()).find_map(Self::from)
     }
-}
-
-/// Returns the number of common segments.
-fn compare_path_segments(left: &[SmolStr], right: &[ast::PathSegment]) -> usize {
-    left.iter().zip(right).take_while(|(l, r)| compare_path_segment(l, r)).count()
-}
 
-fn compare_path_segment(a: &SmolStr, b: &ast::PathSegment) -> bool {
-    if let Some(kb) = b.kind() {
-        match kb {
-            ast::PathSegmentKind::Name(nameref_b) => a == nameref_b.text(),
-            ast::PathSegmentKind::SelfKw => a == "self",
-            ast::PathSegmentKind::SuperKw => a == "super",
-            ast::PathSegmentKind::CrateKw => a == "crate",
-            ast::PathSegmentKind::Type { .. } => false, // not allowed in imports
+    pub(crate) fn as_syntax_node(&self) -> &SyntaxNode {
+        match self {
+            ImportScope::File(file) => file.syntax(),
+            ImportScope::Module(item_list) => item_list.syntax(),
         }
-    } else {
-        false
     }
-}
-
-fn compare_path_segment_with_name(a: &SmolStr, b: &ast::Name) -> bool {
-    a == b.text()
-}
-
-#[derive(Clone, Debug)]
-enum ImportAction {
-    Nothing,
-    // Add a brand new use statement.
-    AddNewUse {
-        anchor: Option<SyntaxNode>, // anchor node
-        add_after_anchor: bool,
-    },
-
-    // To split an existing use statement creating a nested import.
-    AddNestedImport {
-        // how may segments matched with the target path
-        common_segments: usize,
-        path_to_split: ast::Path,
-        // the first segment of path_to_split we want to add into the new nested list
-        first_segment_to_split: Option<ast::PathSegment>,
-        // Wether to add 'self' in addition to the target path
-        add_self: bool,
-    },
-    // To add the target path to an existing nested import tree list.
-    AddInTreeList {
-        common_segments: usize,
-        // The UseTreeList where to add the target path
-        tree_list: ast::UseTreeList,
-        add_self: bool,
-    },
-}
 
-impl ImportAction {
-    fn add_new_use(anchor: Option<SyntaxNode>, add_after_anchor: bool) -> Self {
-        ImportAction::AddNewUse { anchor, add_after_anchor }
-    }
-
-    fn add_nested_import(
-        common_segments: usize,
-        path_to_split: ast::Path,
-        first_segment_to_split: Option<ast::PathSegment>,
-        add_self: bool,
-    ) -> Self {
-        ImportAction::AddNestedImport {
-            common_segments,
-            path_to_split,
-            first_segment_to_split,
-            add_self,
+    fn indent_level(&self) -> IndentLevel {
+        match self {
+            ImportScope::File(file) => file.indent_level(),
+            ImportScope::Module(item_list) => item_list.indent_level() + 1,
         }
     }
 
-    fn add_in_tree_list(
-        common_segments: usize,
-        tree_list: ast::UseTreeList,
-        add_self: bool,
-    ) -> Self {
-        ImportAction::AddInTreeList { common_segments, tree_list, add_self }
-    }
-
-    fn better(left: ImportAction, right: ImportAction) -> ImportAction {
-        if left.is_better(&right) {
-            left
-        } else {
-            right
+    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 is_better(&self, other: &ImportAction) -> bool {
-        match (self, other) {
-            (ImportAction::Nothing, _) => true,
-            (ImportAction::AddInTreeList { .. }, ImportAction::Nothing) => false,
-            (
-                ImportAction::AddNestedImport { common_segments: n, .. },
-                ImportAction::AddInTreeList { common_segments: m, .. },
-            )
-            | (
-                ImportAction::AddInTreeList { common_segments: n, .. },
-                ImportAction::AddNestedImport { common_segments: m, .. },
-            )
-            | (
-                ImportAction::AddInTreeList { common_segments: n, .. },
-                ImportAction::AddInTreeList { common_segments: m, .. },
-            )
-            | (
-                ImportAction::AddNestedImport { common_segments: n, .. },
-                ImportAction::AddNestedImport { common_segments: m, .. },
-            ) => n > m,
-            (ImportAction::AddInTreeList { .. }, _) => true,
-            (ImportAction::AddNestedImport { .. }, ImportAction::Nothing) => false,
-            (ImportAction::AddNestedImport { .. }, _) => true,
-            (ImportAction::AddNewUse { .. }, _) => false,
+    fn insert_pos_after_inner_attribute(&self) -> (InsertPosition<SyntaxElement>, AddBlankLine) {
+        // check if the scope has inner attributes, we dont want to insert in front of them
+        match self
+            .as_syntax_node()
+            .children()
+            // no flat_map here cause we want to short circuit the iterator
+            .map(ast::Attr::cast)
+            .take_while(|attr| {
+                attr.as_ref().map(|attr| attr.kind() == ast::AttrKind::Inner).unwrap_or(false)
+            })
+            .last()
+            .flatten()
+        {
+            Some(attr) => {
+                (InsertPosition::After(attr.syntax().clone().into()), AddBlankLine::BeforeTwice)
+            }
+            None => self.first_insert_pos(),
         }
     }
 }
 
-// Find out the best ImportAction to import target path against current_use_tree.
-// If current_use_tree has a nested import the function gets called recursively on every UseTree inside a UseTreeList.
-fn walk_use_tree_for_best_action(
-    current_path_segments: &mut Vec<ast::PathSegment>, // buffer containing path segments
-    current_parent_use_tree_list: Option<ast::UseTreeList>, // will be Some value if we are in a nested import
-    current_use_tree: ast::UseTree, // the use tree we are currently examinating
-    target: &[SmolStr],             // the path we want to import
-) -> ImportAction {
-    // We save the number of segments in the buffer so we can restore the correct segments
-    // before returning. Recursive call will add segments so we need to delete them.
-    let prev_len = current_path_segments.len();
-
-    let tree_list = current_use_tree.use_tree_list();
-    let alias = current_use_tree.rename();
-
-    let path = match current_use_tree.path() {
-        Some(path) => path,
-        None => {
-            // If the use item don't have a path, it means it's broken (syntax error)
-            return ImportAction::add_new_use(
-                current_use_tree
-                    .syntax()
-                    .ancestors()
-                    .find_map(ast::Use::cast)
-                    .map(|it| it.syntax().clone()),
-                true,
-            );
-        }
-    };
-
-    // This can happen only if current_use_tree is a direct child of a UseItem
-    if let Some(name) = alias.and_then(|it| it.name()) {
-        if compare_path_segment_with_name(&target[0], &name) {
-            return ImportAction::Nothing;
+/// Insert an import path into the given file/node. A `merge` value of none indicates that no import merging is allowed to occur.
+pub(crate) fn insert_use(
+    scope: &ImportScope,
+    path: ast::Path,
+    merge: Option<MergeBehaviour>,
+) -> SyntaxNode {
+    let use_item = make::use_(make::use_tree(path.clone(), None, None, false));
+    // merge into existing imports if possible
+    if let Some(mb) = 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) {
+                let to_delete: SyntaxElement = existing_use.syntax().clone().into();
+                let to_delete = to_delete.clone()..=to_delete;
+                let to_insert = iter::once(merged.syntax().clone().into());
+                return algo::replace_children(scope.as_syntax_node(), to_delete, to_insert);
+            }
         }
     }
 
-    collect_path_segments_raw(current_path_segments, path.clone());
-
-    // We compare only the new segments added in the line just above.
-    // The first prev_len segments were already compared in 'parent' recursive calls.
-    let left = target.split_at(prev_len).1;
-    let right = current_path_segments.split_at(prev_len).1;
-    let common = compare_path_segments(left, &right);
-    let mut action = match common {
-        0 => ImportAction::add_new_use(
-            // e.g: target is std::fmt and we can have
-            // use foo::bar
-            // We add a brand new use statement
-            current_use_tree
-                .syntax()
-                .ancestors()
-                .find_map(ast::Use::cast)
-                .map(|it| it.syntax().clone()),
-            true,
-        ),
-        common if common == left.len() && left.len() == right.len() => {
-            // e.g: target is std::fmt and we can have
-            // 1- use std::fmt;
-            // 2- use std::fmt::{ ... }
-            if let Some(list) = tree_list {
-                // In case 2 we need to add self to the nested list
-                // unless it's already there
-                let has_self = list.use_trees().map(|it| it.path()).any(|p| {
-                    p.and_then(|it| it.segment())
-                        .and_then(|it| it.kind())
-                        .filter(|k| *k == ast::PathSegmentKind::SelfKw)
-                        .is_some()
-                });
-
-                if has_self {
-                    ImportAction::Nothing
-                } else {
-                    ImportAction::add_in_tree_list(current_path_segments.len(), list, true)
-                }
-            } else {
-                // Case 1
-                ImportAction::Nothing
+    // 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);
+
+    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()),
+            _ => (),
         }
-        common if common != left.len() && left.len() == right.len() => {
-            // e.g: target is std::fmt and we have
-            // use std::io;
-            // We need to split.
-            let segments_to_split = current_path_segments.split_at(prev_len + common).1;
-            ImportAction::add_nested_import(
-                prev_len + common,
-                path,
-                Some(segments_to_split[0].clone()),
-                false,
-            )
+
+        if let ident_level @ 1..=usize::MAX = scope.indent_level().0 as usize {
+            // FIXME: this alone doesnt properly re-align all cases
+            buf.push(make::tokens::whitespace(&" ".repeat(4 * ident_level)).into());
         }
-        common if common == right.len() && left.len() > right.len() => {
-            // e.g: target is std::fmt and we can have
-            // 1- use std;
-            // 2- use std::{ ... };
-
-            // fallback action
-            let mut better_action = ImportAction::add_new_use(
-                current_use_tree
-                    .syntax()
-                    .ancestors()
-                    .find_map(ast::Use::cast)
-                    .map(|it| it.syntax().clone()),
-                true,
-            );
-            if let Some(list) = tree_list {
-                // Case 2, check recursively if the path is already imported in the nested list
-                for u in list.use_trees() {
-                    let child_action = walk_use_tree_for_best_action(
-                        current_path_segments,
-                        Some(list.clone()),
-                        u,
-                        target,
-                    );
-                    if child_action.is_better(&better_action) {
-                        better_action = child_action;
-                        if let ImportAction::Nothing = better_action {
-                            return better_action;
-                        }
-                    }
-                }
-            } else {
-                // Case 1, split adding self
-                better_action = ImportAction::add_nested_import(prev_len + common, path, None, true)
+        buf.push(use_item.syntax().clone().into());
+
+        match add_blank {
+            AddBlankLine::After | AddBlankLine::Around => {
+                buf.push(make::tokens::single_newline().into())
             }
-            better_action
-        }
-        common if common == left.len() && left.len() < right.len() => {
-            // e.g: target is std::fmt and we can have
-            // use std::fmt::Debug;
-            let segments_to_split = current_path_segments.split_at(prev_len + common).1;
-            ImportAction::add_nested_import(
-                prev_len + common,
-                path,
-                Some(segments_to_split[0].clone()),
-                true,
-            )
-        }
-        common if common < left.len() && common < right.len() => {
-            // e.g: target is std::fmt::nested::Debug
-            // use std::fmt::Display
-            let segments_to_split = current_path_segments.split_at(prev_len + common).1;
-            ImportAction::add_nested_import(
-                prev_len + common,
-                path,
-                Some(segments_to_split[0].clone()),
-                false,
-            )
+            AddBlankLine::AfterTwice => buf.push(make::tokens::blank_line().into()),
+            _ => (),
         }
-        _ => unreachable!(),
-    };
 
-    // If we are inside a UseTreeList adding a use statement become adding to the existing
-    // tree list.
-    action = match (current_parent_use_tree_list, action.clone()) {
-        (Some(use_tree_list), ImportAction::AddNewUse { .. }) => {
-            ImportAction::add_in_tree_list(prev_len, use_tree_list, false)
-        }
-        (_, _) => action,
+        buf
     };
 
-    // We remove the segments added
-    current_path_segments.truncate(prev_len);
-    action
+    algo::insert_children(scope.as_syntax_node(), insert_position, to_insert)
 }
 
-fn best_action_for_target(
-    container: SyntaxNode,
-    anchor: SyntaxNode,
-    target: &[SmolStr],
-) -> ImportAction {
-    let mut storage = Vec::with_capacity(16); // this should be the only allocation
-    let best_action = container
-        .children()
-        .filter_map(ast::Use::cast)
-        .filter(|u| u.visibility().is_none())
-        .filter_map(|it| it.use_tree())
-        .map(|u| walk_use_tree_for_best_action(&mut storage, None, u, target))
-        .fold(None, |best, a| match best {
-            Some(best) => Some(ImportAction::better(best, a)),
-            None => Some(a),
-        });
+fn try_merge_imports(
+    old: &ast::Use,
+    new: &ast::Use,
+    merge_behaviour: MergeBehaviour,
+) -> Option<ast::Use> {
+    // don't merge into re-exports
+    if old.visibility().and_then(|vis| vis.pub_token()).is_some() {
+        return None;
+    }
+    let old_tree = old.use_tree()?;
+    let new_tree = new.use_tree()?;
+    let merged = try_merge_trees(&old_tree, &new_tree, merge_behaviour)?;
+    Some(old.with_use_tree(merged))
+}
 
-    match best_action {
-        Some(action) => action,
-        None => {
-            // We have no action and no UseItem was found in container so we find
-            // another item and we use it as anchor.
-            // If there are no items above, we choose the target path itself as anchor.
-            // todo: we should include even whitespace blocks as anchor candidates
-            let anchor = container.children().next().or_else(|| Some(anchor));
+/// Simple function that checks if a UseTreeList is deeper than one level
+fn use_tree_list_is_nested(tl: &ast::UseTreeList) -> bool {
+    tl.use_trees().any(|use_tree| {
+        use_tree.use_tree_list().is_some() || use_tree.path().and_then(|p| p.qualifier()).is_some()
+    })
+}
 
-            let add_after_anchor = anchor
-                .clone()
-                .and_then(ast::Attr::cast)
-                .map(|attr| attr.kind() == ast::AttrKind::Inner)
-                .unwrap_or(false);
-            ImportAction::add_new_use(anchor, add_after_anchor)
-        }
+// FIXME: currently this merely prepends the new tree into old, ideally it would insert the items in a sorted fashion
+pub fn try_merge_trees(
+    old: &ast::UseTree,
+    new: &ast::UseTree,
+    merge_behaviour: MergeBehaviour,
+) -> Option<ast::UseTree> {
+    let lhs_path = old.path()?;
+    let rhs_path = new.path()?;
+
+    let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
+    let lhs = old.split_prefix(&lhs_prefix);
+    let rhs = new.split_prefix(&rhs_prefix);
+    let lhs_tl = lhs.use_tree_list()?;
+    let rhs_tl = rhs.use_tree_list()?;
+
+    // if we are only allowed to merge the last level check if the split off paths are only one level deep
+    if merge_behaviour == MergeBehaviour::Last
+        && (use_tree_list_is_nested(&lhs_tl) || use_tree_list_is_nested(&rhs_tl))
+    {
+        mark::hit!(test_last_merge_too_long);
+        return None;
     }
-}
 
-fn make_assist(action: &ImportAction, target: &[SmolStr], edit: &mut TextEditBuilder) {
-    match action {
-        ImportAction::AddNewUse { anchor, add_after_anchor } => {
-            make_assist_add_new_use(anchor, *add_after_anchor, target, edit)
-        }
-        ImportAction::AddInTreeList { common_segments, tree_list, add_self } => {
-            // We know that the fist n segments already exists in the use statement we want
-            // to modify, so we want to add only the last target.len() - n segments.
-            let segments_to_add = target.split_at(*common_segments).1;
-            make_assist_add_in_tree_list(tree_list, segments_to_add, *add_self, edit)
-        }
-        ImportAction::AddNestedImport {
-            common_segments,
-            path_to_split,
-            first_segment_to_split,
-            add_self,
-        } => {
-            let segments_to_add = target.split_at(*common_segments).1;
-            make_assist_add_nested_import(
-                path_to_split,
-                first_segment_to_split,
-                segments_to_add,
-                *add_self,
-                edit,
-            )
-        }
-        _ => {}
+    let should_insert_comma = lhs_tl
+        .r_curly_token()
+        .and_then(|it| skip_trivia_token(it.prev_token()?, Direction::Prev))
+        .map(|it| it.kind())
+        != Some(T![,]);
+    let mut to_insert: Vec<SyntaxElement> = Vec::new();
+    if should_insert_comma {
+        to_insert.push(make::token(T![,]).into());
+        to_insert.push(make::tokens::single_space().into());
     }
+    to_insert.extend(
+        rhs_tl.syntax().children_with_tokens().filter(|it| !matches!(it.kind(), T!['{'] | T!['}'])),
+    );
+    let pos = InsertPosition::Before(lhs_tl.r_curly_token()?.into());
+    let use_tree_list = lhs_tl.insert_children(pos, to_insert);
+    Some(lhs.with_use_tree_list(use_tree_list))
 }
 
-fn make_assist_add_new_use(
-    anchor: &Option<SyntaxNode>,
-    after: bool,
-    target: &[SmolStr],
-    edit: &mut TextEditBuilder,
-) {
-    if let Some(anchor) = anchor {
-        let indent = leading_indent(anchor);
-        let mut buf = String::new();
-        if after {
-            buf.push_str("\n");
-            if let Some(spaces) = &indent {
-                buf.push_str(spaces);
-            }
+/// 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,
         }
-        buf.push_str("use ");
-        fmt_segments_raw(target, &mut buf);
-        buf.push_str(";");
-        if !after {
-            buf.push_str("\n\n");
-            if let Some(spaces) = &indent {
-                buf.push_str(&spaces);
+        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,
         }
-        let position = if after { anchor.text_range().end() } else { anchor.text_range().start() };
-        edit.insert(position, buf);
     }
+
+    res
 }
 
-fn make_assist_add_in_tree_list(
-    tree_list: &ast::UseTreeList,
-    target: &[SmolStr],
-    add_self: bool,
-    edit: &mut TextEditBuilder,
-) {
-    let last = tree_list.use_trees().last();
-    if let Some(last) = last {
-        let mut buf = String::new();
-        let comma = last.syntax().siblings(Direction::Next).find(|n| n.kind() == T![,]);
-        let offset = if let Some(comma) = comma {
-            comma.text_range().end()
-        } else {
-            buf.push_str(",");
-            last.syntax().text_range().end()
-        };
-        if add_self {
-            buf.push_str(" self")
-        } else {
-            buf.push_str(" ");
-        }
-        fmt_segments_raw(target, &mut buf);
-        edit.insert(offset, buf);
-    } else {
-    }
+/// What type of merges are allowed.
+#[derive(Copy, Clone, PartialEq, Eq)]
+pub enum MergeBehaviour {
+    /// Merge everything together creating deeply nested imports.
+    Full,
+    /// Only merge the last import level, doesn't allow import nesting.
+    Last,
 }
 
-fn make_assist_add_nested_import(
-    path: &ast::Path,
-    first_segment_to_split: &Option<ast::PathSegment>,
-    target: &[SmolStr],
-    add_self: bool,
-    edit: &mut TextEditBuilder,
-) {
-    let use_tree = path.syntax().ancestors().find_map(ast::UseTree::cast);
-    if let Some(use_tree) = use_tree {
-        let (start, add_colon_colon) = if let Some(first_segment_to_split) = first_segment_to_split
-        {
-            (first_segment_to_split.syntax().text_range().start(), false)
-        } else {
-            (use_tree.syntax().text_range().end(), true)
+#[derive(Eq, PartialEq, PartialOrd, Ord)]
+enum ImportGroup {
+    // the order here defines the order of new group inserts
+    Std,
+    ExternCrate,
+    ThisCrate,
+    ThisModule,
+    SuperModule,
+}
+
+impl ImportGroup {
+    fn new(path: &ast::Path) -> ImportGroup {
+        let default = ImportGroup::ExternCrate;
+
+        let first_segment = match first_segment(path) {
+            Some(it) => it,
+            None => return default,
         };
-        let end = use_tree.syntax().text_range().end();
 
-        let mut buf = String::new();
-        if add_colon_colon {
-            buf.push_str("::");
-        }
-        buf.push_str("{");
-        if add_self {
-            buf.push_str("self, ");
-        }
-        fmt_segments_raw(target, &mut buf);
-        if !target.is_empty() {
-            buf.push_str(", ");
+        let kind = first_segment.kind().unwrap_or(PathSegmentKind::SelfKw);
+        match kind {
+            PathSegmentKind::SelfKw => ImportGroup::ThisModule,
+            PathSegmentKind::SuperKw => ImportGroup::SuperModule,
+            PathSegmentKind::CrateKw => ImportGroup::ThisCrate,
+            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!(),
         }
-        edit.insert(start, buf);
-        edit.insert(end, "}".to_string());
     }
 }
 
-/// If the node is on the beginning of the line, calculate indent.
-fn leading_indent(node: &SyntaxNode) -> Option<SmolStr> {
-    for token in prev_tokens(node.first_token()?) {
-        if let Some(ws) = ast::Whitespace::cast(token.clone()) {
-            let ws_text = ws.text();
-            if let Some(pos) = ws_text.rfind('\n') {
-                return Some(ws_text[pos + 1..].into());
+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 {
+    path.syntax().children().flat_map(ast::PathSegment::cast)
+}
+
+#[derive(PartialEq, Eq)]
+enum AddBlankLine {
+    Before,
+    BeforeTwice,
+    Around,
+    After,
+    AfterTwice,
+}
+
+fn find_insert_position(
+    scope: &ImportScope,
+    insert_path: ast::Path,
+) -> (InsertPosition<SyntaxElement>, AddBlankLine) {
+    let group = ImportGroup::new(&insert_path);
+    let path_node_iter = scope
+        .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)));
+    // 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);
+
+    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())
+        });
+    match post_insert {
+        // insert our import before that element
+        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),
+            // the group we were looking for actually doesnt exist, so insert
+            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_inner_attribute(),
+                    },
+                }
             }
-        }
-        if token.text().contains('\n') {
-            break;
-        }
+        },
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    use test_utils::assert_eq_text;
+
+    #[test]
+    fn insert_start() {
+        check_none(
+            "std::bar::AA",
+            r"
+use std::bar::B;
+use std::bar::D;
+use std::bar::F;
+use std::bar::G;",
+            r"
+use std::bar::AA;
+use std::bar::B;
+use std::bar::D;
+use std::bar::F;
+use std::bar::G;",
+        )
+    }
+
+    #[test]
+    fn insert_middle() {
+        check_none(
+            "std::bar::EE",
+            r"
+use std::bar::A;
+use std::bar::D;
+use std::bar::F;
+use std::bar::G;",
+            r"
+use std::bar::A;
+use std::bar::D;
+use std::bar::EE;
+use std::bar::F;
+use std::bar::G;",
+        )
+    }
+
+    #[test]
+    fn insert_end() {
+        check_none(
+            "std::bar::ZZ",
+            r"
+use std::bar::A;
+use std::bar::D;
+use std::bar::F;
+use std::bar::G;",
+            r"
+use std::bar::A;
+use std::bar::D;
+use std::bar::F;
+use std::bar::G;
+use std::bar::ZZ;",
+        )
+    }
+
+    #[test]
+    fn insert_middle_nested() {
+        check_none(
+            "std::bar::EE",
+            r"
+use std::bar::A;
+use std::bar::{D, Z}; // example of weird imports due to user
+use std::bar::F;
+use std::bar::G;",
+            r"
+use std::bar::A;
+use std::bar::EE;
+use std::bar::{D, Z}; // example of weird imports due to user
+use std::bar::F;
+use std::bar::G;",
+        )
+    }
+
+    #[test]
+    fn insert_middle_groups() {
+        check_none(
+            "foo::bar::GG",
+            r"
+use std::bar::A;
+use std::bar::D;
+
+use foo::bar::F;
+use foo::bar::H;",
+            r"
+use std::bar::A;
+use std::bar::D;
+
+use foo::bar::F;
+use foo::bar::GG;
+use foo::bar::H;",
+        )
+    }
+
+    #[test]
+    fn insert_first_matching_group() {
+        check_none(
+            "foo::bar::GG",
+            r"
+use foo::bar::A;
+use foo::bar::D;
+
+use std;
+
+use foo::bar::F;
+use foo::bar::H;",
+            r"
+use foo::bar::A;
+use foo::bar::D;
+use foo::bar::GG;
+
+use std;
+
+use foo::bar::F;
+use foo::bar::H;",
+        )
+    }
+
+    #[test]
+    fn insert_missing_group_std() {
+        check_none(
+            "std::fmt",
+            r"
+use foo::bar::A;
+use foo::bar::D;",
+            r"
+use std::fmt;
+
+use foo::bar::A;
+use foo::bar::D;",
+        )
+    }
+
+    #[test]
+    fn insert_missing_group_self() {
+        check_none(
+            "self::fmt",
+            r"
+use foo::bar::A;
+use foo::bar::D;",
+            r"
+use foo::bar::A;
+use foo::bar::D;
+
+use self::fmt;",
+        )
+    }
+
+    #[test]
+    fn insert_no_imports() {
+        check_full(
+            "foo::bar",
+            "fn main() {}",
+            r"use foo::bar;
+
+fn main() {}",
+        )
+    }
+
+    #[test]
+    fn insert_empty_file() {
+        // empty files will get two trailing newlines
+        // this is due to the test case insert_no_imports above
+        check_full(
+            "foo::bar",
+            "",
+            r"use foo::bar;
+
+",
+        )
+    }
+
+    #[test]
+    fn insert_after_inner_attr() {
+        check_full(
+            "foo::bar",
+            r"#![allow(unused_imports)]",
+            r"#![allow(unused_imports)]
+
+use foo::bar;",
+        )
     }
-    return None;
-    fn prev_tokens(token: SyntaxToken) -> impl Iterator<Item = SyntaxToken> {
-        successors(token.prev_token(), |token| token.prev_token())
+
+    #[test]
+    fn insert_after_inner_attr2() {
+        check_full(
+            "foo::bar",
+            r"#![allow(unused_imports)]
+
+fn main() {}",
+            r"#![allow(unused_imports)]
+
+use foo::bar;
+
+fn main() {}",
+        )
+    }
+
+    #[test]
+    fn merge_groups() {
+        check_last("std::io", r"use std::fmt;", r"use std::{fmt, io};")
+    }
+
+    #[test]
+    fn merge_groups_last() {
+        check_last(
+            "std::io",
+            r"use std::fmt::{Result, Display};",
+            r"use std::fmt::{Result, Display};
+use std::io;",
+        )
+    }
+
+    #[test]
+    fn merge_groups_full() {
+        check_full(
+            "std::io",
+            r"use std::fmt::{Result, Display};",
+            r"use std::{fmt::{Result, Display}, io};",
+        )
+    }
+
+    #[test]
+    fn merge_groups_long_full() {
+        check_full(
+            "std::foo::bar::Baz",
+            r"use std::foo::bar::Qux;",
+            r"use std::foo::bar::{Qux, Baz};",
+        )
+    }
+
+    #[test]
+    fn merge_groups_long_last() {
+        check_last(
+            "std::foo::bar::Baz",
+            r"use std::foo::bar::Qux;",
+            r"use std::foo::bar::{Qux, Baz};",
+        )
+    }
+
+    #[test]
+    fn merge_groups_long_full_list() {
+        check_full(
+            "std::foo::bar::Baz",
+            r"use std::foo::bar::{Qux, Quux};",
+            r"use std::foo::bar::{Qux, Quux, Baz};",
+        )
+    }
+
+    #[test]
+    fn merge_groups_long_last_list() {
+        check_last(
+            "std::foo::bar::Baz",
+            r"use std::foo::bar::{Qux, Quux};",
+            r"use std::foo::bar::{Qux, Quux, Baz};",
+        )
+    }
+
+    #[test]
+    fn merge_groups_long_full_nested() {
+        check_full(
+            "std::foo::bar::Baz",
+            r"use std::foo::bar::{Qux, quux::{Fez, Fizz}};",
+            r"use std::foo::bar::{Qux, quux::{Fez, Fizz}, Baz};",
+        )
+    }
+
+    #[test]
+    fn merge_groups_long_last_nested() {
+        check_last(
+            "std::foo::bar::Baz",
+            r"use std::foo::bar::{Qux, quux::{Fez, Fizz}};",
+            r"use std::foo::bar::Baz;
+use std::foo::bar::{Qux, quux::{Fez, Fizz}};",
+        )
+    }
+
+    #[test]
+    fn merge_groups_skip_pub() {
+        check_full(
+            "std::io",
+            r"pub use std::fmt::{Result, Display};",
+            r"pub use std::fmt::{Result, Display};
+use std::io;",
+        )
+    }
+
+    #[test]
+    fn merge_groups_skip_pub_crate() {
+        check_full(
+            "std::io",
+            r"pub(crate) use std::fmt::{Result, Display};",
+            r"pub(crate) use std::fmt::{Result, Display};
+use std::io;",
+        )
+    }
+
+    #[test]
+    #[ignore] // FIXME: Support this
+    fn split_out_merge() {
+        check_last(
+            "std::fmt::Result",
+            r"use std::{fmt, io};",
+            r"use std::{self, fmt::Result};
+use std::io;",
+        )
+    }
+
+    #[test]
+    fn merge_groups_self() {
+        check_full("std::fmt::Debug", r"use std::fmt;", r"use std::fmt::{self, Debug};")
+    }
+
+    #[test]
+    fn merge_self_glob() {
+        check_full(
+            "token::TokenKind",
+            r"use token::TokenKind::*;",
+            r"use token::TokenKind::{self::*, self};",
+        )
+    }
+
+    #[test]
+    fn merge_last_too_long() {
+        mark::check!(test_last_merge_too_long);
+        check_last(
+            "foo::bar",
+            r"use foo::bar::baz::Qux;",
+            r"use foo::bar::baz::Qux;
+use foo::bar;",
+        );
+    }
+
+    fn check(
+        path: &str,
+        ra_fixture_before: &str,
+        ra_fixture_after: &str,
+        mb: Option<MergeBehaviour>,
+    ) {
+        let file = super::ImportScope::from(
+            ast::SourceFile::parse(ra_fixture_before).tree().syntax().clone(),
+        )
+        .unwrap();
+        let path = ast::SourceFile::parse(&format!("use {};", path))
+            .tree()
+            .syntax()
+            .descendants()
+            .find_map(ast::Path::cast)
+            .unwrap();
+
+        let result = insert_use(&file, path, mb).to_string();
+        assert_eq_text!(&result, ra_fixture_after);
+    }
+
+    fn check_full(path: &str, ra_fixture_before: &str, ra_fixture_after: &str) {
+        check(path, ra_fixture_before, ra_fixture_after, Some(MergeBehaviour::Full))
+    }
+
+    fn check_last(path: &str, ra_fixture_before: &str, ra_fixture_after: &str) {
+        check(path, ra_fixture_before, ra_fixture_after, Some(MergeBehaviour::Last))
+    }
+
+    fn check_none(path: &str, ra_fixture_before: &str, ra_fixture_after: &str) {
+        check(path, ra_fixture_before, ra_fixture_after, None)
     }
 }
diff --git a/crates/syntax/src/ast/make.rs b/crates/syntax/src/ast/make.rs
index c2c938ad1..33f1ad7b3 100644
--- a/crates/syntax/src/ast/make.rs
+++ b/crates/syntax/src/ast/make.rs
@@ -339,7 +339,7 @@ pub mod tokens {
     use crate::{ast, AstNode, Parse, SourceFile, SyntaxKind::*, SyntaxToken};
 
     pub(super) static SOURCE_FILE: Lazy<Parse<SourceFile>> =
-        Lazy::new(|| SourceFile::parse("const C: <()>::Item = (1 != 1, 2 == 2, !true)\n;"));
+        Lazy::new(|| SourceFile::parse("const C: <()>::Item = (1 != 1, 2 == 2, !true)\n;\n\n"));
 
     pub fn single_space() -> SyntaxToken {
         SOURCE_FILE
@@ -379,6 +379,16 @@ pub mod tokens {
             .unwrap()
     }
 
+    pub fn blank_line() -> SyntaxToken {
+        SOURCE_FILE
+            .tree()
+            .syntax()
+            .descendants_with_tokens()
+            .filter_map(|it| it.into_token())
+            .find(|it| it.kind() == WHITESPACE && it.text().as_str() == "\n\n")
+            .unwrap()
+    }
+
     pub struct WsBuilder(SourceFile);
 
     impl WsBuilder {