7 files changed, 358 insertions, 37 deletions

diff --git a/crates/ide_db/src/defs.rs b/crates/ide_db/src/defs.rs
index d68fe42b0..231e886a9 100644
--- a/crates/ide_db/src/defs.rs
+++ b/crates/ide_db/src/defs.rs
@@ -10,7 +10,7 @@ use hir::{
     Module, ModuleDef, Name, PathResolution, Semantics, Visibility,
 };
 use syntax::{
-    ast::{self, AstNode},
+    ast::{self, AstNode, PathSegmentKind},
     match_ast, SyntaxKind, SyntaxNode,
 };
 
@@ -117,6 +117,13 @@ impl NameClass {
         }
     }
 
+    pub fn classify_self_param(
+        sema: &Semantics<RootDatabase>,
+        self_param: &ast::SelfParam,
+    ) -> Option<NameClass> {
+        sema.to_def(self_param).map(Definition::Local).map(NameClass::Definition)
+    }
+
     pub fn classify(sema: &Semantics<RootDatabase>, name: &ast::Name) -> Option<NameClass> {
         let _p = profile::span("classify_name");
 
@@ -135,24 +142,26 @@ impl NameClass {
                         let path = use_tree.path()?;
                         let path_segment = path.segment()?;
                         let name_ref_class = path_segment
-                            .name_ref()
-                            // The rename might be from a `self` token, so fallback to the name higher
-                            // in the use tree.
-                            .or_else(||{
-                                if path_segment.self_token().is_none() {
-                                    return None;
+                            .kind()
+                            .and_then(|kind| {
+                                match kind {
+                                    // The rename might be from a `self` token, so fallback to the name higher
+                                    // in the use tree.
+                                    PathSegmentKind::SelfKw => {
+                                        let use_tree = use_tree
+                                            .syntax()
+                                            .parent()
+                                            .as_ref()
+                                            // Skip over UseTreeList
+                                            .and_then(SyntaxNode::parent)
+                                            .and_then(ast::UseTree::cast)?;
+                                        let path = use_tree.path()?;
+                                        let path_segment = path.segment()?;
+                                        path_segment.name_ref()
+                                    },
+                                    PathSegmentKind::Name(name_ref) => Some(name_ref),
+                                    _ => return None,
                                 }
-
-                                let use_tree = use_tree
-                                    .syntax()
-                                    .parent()
-                                    .as_ref()
-                                    // Skip over UseTreeList
-                                    .and_then(SyntaxNode::parent)
-                                    .and_then(ast::UseTree::cast)?;
-                                let path = use_tree.path()?;
-                                let path_segment = path.segment()?;
-                                path_segment.name_ref()
                             })
                             .and_then(|name_ref| NameRefClass::classify(sema, &name_ref))?;
 
diff --git a/crates/ide_db/src/helpers.rs b/crates/ide_db/src/helpers.rs
index c6763ae36..0dcc4dd29 100644
--- a/crates/ide_db/src/helpers.rs
+++ b/crates/ide_db/src/helpers.rs
@@ -1,5 +1,6 @@
 //! A module with ide helpers for high-level ide features.
 pub mod insert_use;
+pub mod import_assets;
 
 use hir::{Crate, Enum, Module, ScopeDef, Semantics, Trait};
 use syntax::ast::{self, make};
diff --git a/crates/ide_db/src/helpers/import_assets.rs b/crates/ide_db/src/helpers/import_assets.rs
new file mode 100644
index 000000000..edc3da318
--- /dev/null
+++ b/crates/ide_db/src/helpers/import_assets.rs
@@ -0,0 +1,267 @@
+//! Look up accessible paths for items.
+use either::Either;
+use hir::{AsAssocItem, AssocItemContainer, ModuleDef, Semantics};
+use rustc_hash::FxHashSet;
+use syntax::{ast, AstNode, SyntaxNode};
+
+use crate::{imports_locator, RootDatabase};
+
+use super::insert_use::InsertUseConfig;
+
+#[derive(Debug)]
+pub enum ImportCandidate {
+    // A path, qualified (`std::collections::HashMap`) or not (`HashMap`).
+    Path(PathImportCandidate),
+    /// A trait associated function (with no self parameter) or associated constant.
+    /// For 'test_mod::TestEnum::test_function', `ty` is the `test_mod::TestEnum` expression type
+    /// and `name` is the `test_function`
+    TraitAssocItem(TraitImportCandidate),
+    /// A trait method with self parameter.
+    /// For 'test_enum.test_method()', `ty` is the `test_enum` expression type
+    /// and `name` is the `test_method`
+    TraitMethod(TraitImportCandidate),
+}
+
+#[derive(Debug)]
+pub struct TraitImportCandidate {
+    pub ty: hir::Type,
+    pub name: ast::NameRef,
+}
+
+#[derive(Debug)]
+pub struct PathImportCandidate {
+    pub qualifier: Option<ast::Path>,
+    pub name: ast::NameRef,
+}
+
+#[derive(Debug)]
+pub struct ImportAssets {
+    import_candidate: ImportCandidate,
+    module_with_name_to_import: hir::Module,
+    syntax_under_caret: SyntaxNode,
+}
+
+impl ImportAssets {
+    pub fn for_method_call(
+        method_call: ast::MethodCallExpr,
+        sema: &Semantics<RootDatabase>,
+    ) -> Option<Self> {
+        let syntax_under_caret = method_call.syntax().to_owned();
+        let module_with_name_to_import = sema.scope(&syntax_under_caret).module()?;
+        Some(Self {
+            import_candidate: ImportCandidate::for_method_call(sema, &method_call)?,
+            module_with_name_to_import,
+            syntax_under_caret,
+        })
+    }
+
+    pub fn for_regular_path(
+        path_under_caret: ast::Path,
+        sema: &Semantics<RootDatabase>,
+    ) -> Option<Self> {
+        let syntax_under_caret = path_under_caret.syntax().to_owned();
+        if syntax_under_caret.ancestors().find_map(ast::Use::cast).is_some() {
+            return None;
+        }
+
+        let module_with_name_to_import = sema.scope(&syntax_under_caret).module()?;
+        Some(Self {
+            import_candidate: ImportCandidate::for_regular_path(sema, &path_under_caret)?,
+            module_with_name_to_import,
+            syntax_under_caret,
+        })
+    }
+
+    pub fn syntax_under_caret(&self) -> &SyntaxNode {
+        &self.syntax_under_caret
+    }
+
+    pub fn import_candidate(&self) -> &ImportCandidate {
+        &self.import_candidate
+    }
+
+    fn get_search_query(&self) -> &str {
+        match &self.import_candidate {
+            ImportCandidate::Path(candidate) => candidate.name.text(),
+            ImportCandidate::TraitAssocItem(candidate)
+            | ImportCandidate::TraitMethod(candidate) => candidate.name.text(),
+        }
+    }
+
+    pub fn search_for_imports(
+        &self,
+        sema: &Semantics<RootDatabase>,
+        config: &InsertUseConfig,
+    ) -> Vec<(hir::ModPath, hir::ItemInNs)> {
+        let _p = profile::span("import_assists::search_for_imports");
+        self.search_for(sema, Some(config.prefix_kind))
+    }
+
+    /// This may return non-absolute paths if a part of the returned path is already imported into scope.
+    #[allow(dead_code)]
+    pub fn search_for_relative_paths(
+        &self,
+        sema: &Semantics<RootDatabase>,
+    ) -> Vec<(hir::ModPath, hir::ItemInNs)> {
+        let _p = profile::span("import_assists::search_for_relative_paths");
+        self.search_for(sema, None)
+    }
+
+    fn search_for(
+        &self,
+        sema: &Semantics<RootDatabase>,
+        prefixed: Option<hir::PrefixKind>,
+    ) -> Vec<(hir::ModPath, hir::ItemInNs)> {
+        let db = sema.db;
+        let mut trait_candidates = FxHashSet::default();
+        let current_crate = self.module_with_name_to_import.krate();
+
+        let filter = |candidate: Either<hir::ModuleDef, hir::MacroDef>| {
+            trait_candidates.clear();
+            match &self.import_candidate {
+                ImportCandidate::TraitAssocItem(trait_candidate) => {
+                    let located_assoc_item = match candidate {
+                        Either::Left(ModuleDef::Function(located_function)) => {
+                            located_function.as_assoc_item(db)
+                        }
+                        Either::Left(ModuleDef::Const(located_const)) => {
+                            located_const.as_assoc_item(db)
+                        }
+                        _ => None,
+                    }
+                    .map(|assoc| assoc.container(db))
+                    .and_then(Self::assoc_to_trait)?;
+
+                    trait_candidates.insert(located_assoc_item.into());
+
+                    trait_candidate
+                        .ty
+                        .iterate_path_candidates(
+                            db,
+                            current_crate,
+                            &trait_candidates,
+                            None,
+                            |_, assoc| Self::assoc_to_trait(assoc.container(db)),
+                        )
+                        .map(ModuleDef::from)
+                        .map(Either::Left)
+                }
+                ImportCandidate::TraitMethod(trait_candidate) => {
+                    let located_assoc_item =
+                        if let Either::Left(ModuleDef::Function(located_function)) = candidate {
+                            located_function
+                                .as_assoc_item(db)
+                                .map(|assoc| assoc.container(db))
+                                .and_then(Self::assoc_to_trait)
+                        } else {
+                            None
+                        }?;
+
+                    trait_candidates.insert(located_assoc_item.into());
+
+                    trait_candidate
+                        .ty
+                        .iterate_method_candidates(
+                            db,
+                            current_crate,
+                            &trait_candidates,
+                            None,
+                            |_, function| {
+                                Self::assoc_to_trait(function.as_assoc_item(db)?.container(db))
+                            },
+                        )
+                        .map(ModuleDef::from)
+                        .map(Either::Left)
+                }
+                _ => Some(candidate),
+            }
+        };
+
+        let mut res = imports_locator::find_exact_imports(
+            sema,
+            current_crate,
+            self.get_search_query().to_string(),
+        )
+        .filter_map(filter)
+        .filter_map(|candidate| {
+            let item: hir::ItemInNs = candidate.either(Into::into, Into::into);
+            if let Some(prefix_kind) = prefixed {
+                self.module_with_name_to_import.find_use_path_prefixed(db, item, prefix_kind)
+            } else {
+                self.module_with_name_to_import.find_use_path(db, item)
+            }
+            .map(|path| (path, item))
+        })
+        .filter(|(use_path, _)| use_path.len() > 1)
+        .take(20)
+        .collect::<Vec<_>>();
+        res.sort_by_key(|(path, _)| path.clone());
+        res
+    }
+
+    fn assoc_to_trait(assoc: AssocItemContainer) -> Option<hir::Trait> {
+        if let AssocItemContainer::Trait(extracted_trait) = assoc {
+            Some(extracted_trait)
+        } else {
+            None
+        }
+    }
+}
+
+impl ImportCandidate {
+    fn for_method_call(
+        sema: &Semantics<RootDatabase>,
+        method_call: &ast::MethodCallExpr,
+    ) -> Option<Self> {
+        match sema.resolve_method_call(method_call) {
+            Some(_) => None,
+            None => Some(Self::TraitMethod(TraitImportCandidate {
+                ty: sema.type_of_expr(&method_call.receiver()?)?,
+                name: method_call.name_ref()?,
+            })),
+        }
+    }
+
+    fn for_regular_path(
+        sema: &Semantics<RootDatabase>,
+        path_under_caret: &ast::Path,
+    ) -> Option<Self> {
+        if sema.resolve_path(path_under_caret).is_some() {
+            return None;
+        }
+
+        let segment = path_under_caret.segment()?;
+        let candidate = if let Some(qualifier) = path_under_caret.qualifier() {
+            let qualifier_start = qualifier.syntax().descendants().find_map(ast::NameRef::cast)?;
+            let qualifier_start_path =
+                qualifier_start.syntax().ancestors().find_map(ast::Path::cast)?;
+            if let Some(qualifier_start_resolution) = sema.resolve_path(&qualifier_start_path) {
+                let qualifier_resolution = if qualifier_start_path == qualifier {
+                    qualifier_start_resolution
+                } else {
+                    sema.resolve_path(&qualifier)?
+                };
+                match qualifier_resolution {
+                    hir::PathResolution::Def(hir::ModuleDef::Adt(assoc_item_path)) => {
+                        ImportCandidate::TraitAssocItem(TraitImportCandidate {
+                            ty: assoc_item_path.ty(sema.db),
+                            name: segment.name_ref()?,
+                        })
+                    }
+                    _ => return None,
+                }
+            } else {
+                ImportCandidate::Path(PathImportCandidate {
+                    qualifier: Some(qualifier),
+                    name: qualifier_start,
+                })
+            }
+        } else {
+            ImportCandidate::Path(PathImportCandidate {
+                qualifier: None,
+                name: segment.syntax().descendants().find_map(ast::NameRef::cast)?,
+            })
+        };
+        Some(candidate)
+    }
+}
diff --git a/crates/ide_db/src/helpers/insert_use.rs b/crates/ide_db/src/helpers/insert_use.rs
index d6b498be3..877d4f1c7 100644
--- a/crates/ide_db/src/helpers/insert_use.rs
+++ b/crates/ide_db/src/helpers/insert_use.rs
@@ -15,6 +15,12 @@ use syntax::{
 };
 use test_utils::mark;
 
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+pub struct InsertUseConfig {
+    pub merge: Option<MergeBehavior>,
+    pub prefix_kind: hir::PrefixKind,
+}
+
 #[derive(Debug, Clone)]
 pub enum ImportScope {
     File(ast::SourceFile),
@@ -97,7 +103,7 @@ pub fn insert_use<'a>(
 ) -> SyntaxRewriter<'a> {
     let _p = profile::span("insert_use");
     let mut rewriter = SyntaxRewriter::default();
-    let use_item = make::use_(make::use_tree(path.clone(), None, None, false));
+    let use_item = make::use_(None, 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) {
@@ -444,8 +450,14 @@ fn use_tree_path_cmp(a: &ast::Path, a_has_tl: bool, b: &ast::Path, b_has_tl: boo
 }
 
 fn path_segment_cmp(a: &ast::PathSegment, b: &ast::PathSegment) -> Ordering {
-    let a = a.name_ref();
-    let b = b.name_ref();
+    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))
 }
 
diff --git a/crates/ide_db/src/imports_locator.rs b/crates/ide_db/src/imports_locator.rs
index e9f23adf8..d111fba92 100644
--- a/crates/ide_db/src/imports_locator.rs
+++ b/crates/ide_db/src/imports_locator.rs
@@ -12,6 +12,8 @@ use crate::{
 use either::Either;
 use rustc_hash::FxHashSet;
 
+const QUERY_SEARCH_LIMIT: usize = 40;
+
 pub fn find_exact_imports<'a>(
     sema: &Semantics<'a, RootDatabase>,
     krate: Crate,
@@ -24,11 +26,11 @@ pub fn find_exact_imports<'a>(
         {
             let mut local_query = symbol_index::Query::new(name_to_import.clone());
             local_query.exact();
-            local_query.limit(40);
+            local_query.limit(QUERY_SEARCH_LIMIT);
             local_query
         },
         import_map::Query::new(name_to_import)
-            .limit(40)
+            .limit(QUERY_SEARCH_LIMIT)
             .name_only()
             .search_mode(import_map::SearchMode::Equals)
             .case_sensitive(),
diff --git a/crates/ide_db/src/search.rs b/crates/ide_db/src/search.rs
index b5fa46642..0ecb13a64 100644
--- a/crates/ide_db/src/search.rs
+++ b/crates/ide_db/src/search.rs
@@ -65,7 +65,7 @@ pub enum ReferenceKind {
     FieldShorthandForLocal,
     StructLiteral,
     RecordFieldExprOrPat,
-    SelfKw,
+    SelfParam,
     EnumLiteral,
     Lifetime,
     Other,
diff --git a/crates/ide_db/src/source_change.rs b/crates/ide_db/src/source_change.rs
index 10c0abdac..b1f87731b 100644
--- a/crates/ide_db/src/source_change.rs
+++ b/crates/ide_db/src/source_change.rs
@@ -3,12 +3,19 @@
 //!
 //! It can be viewed as a dual for `AnalysisChange`.
 
+use std::{
+    collections::hash_map::Entry,
+    iter::{self, FromIterator},
+};
+
 use base_db::{AnchoredPathBuf, FileId};
+use rustc_hash::FxHashMap;
+use stdx::assert_never;
 use text_edit::TextEdit;
 
 #[derive(Default, Debug, Clone)]
 pub struct SourceChange {
-    pub source_file_edits: Vec<SourceFileEdit>,
+    pub source_file_edits: FxHashMap<FileId, TextEdit>,
     pub file_system_edits: Vec<FileSystemEdit>,
     pub is_snippet: bool,
 }
@@ -17,27 +24,50 @@ impl SourceChange {
     /// Creates a new SourceChange with the given label
     /// from the edits.
     pub fn from_edits(
-        source_file_edits: Vec<SourceFileEdit>,
+        source_file_edits: FxHashMap<FileId, TextEdit>,
         file_system_edits: Vec<FileSystemEdit>,
     ) -> Self {
         SourceChange { source_file_edits, file_system_edits, is_snippet: false }
     }
-}
 
-#[derive(Debug, Clone)]
-pub struct SourceFileEdit {
-    pub file_id: FileId,
-    pub edit: TextEdit,
+    pub fn from_text_edit(file_id: FileId, edit: TextEdit) -> Self {
+        SourceChange {
+            source_file_edits: FxHashMap::from_iter(iter::once((file_id, edit))),
+            ..Default::default()
+        }
+    }
+
+    pub fn insert_source_edit(&mut self, file_id: FileId, edit: TextEdit) {
+        match self.source_file_edits.entry(file_id) {
+            Entry::Occupied(mut entry) => {
+                assert_never!(
+                    entry.get_mut().union(edit).is_err(),
+                    "overlapping edits for same file"
+                );
+            }
+            Entry::Vacant(entry) => {
+                entry.insert(edit);
+            }
+        }
+    }
+
+    pub fn push_file_system_edit(&mut self, edit: FileSystemEdit) {
+        self.file_system_edits.push(edit);
+    }
+
+    pub fn get_source_edit(&self, file_id: FileId) -> Option<&TextEdit> {
+        self.source_file_edits.get(&file_id)
+    }
 }
 
-impl From<SourceFileEdit> for SourceChange {
-    fn from(edit: SourceFileEdit) -> SourceChange {
-        vec![edit].into()
+impl Extend<(FileId, TextEdit)> for SourceChange {
+    fn extend<T: IntoIterator<Item = (FileId, TextEdit)>>(&mut self, iter: T) {
+        iter.into_iter().for_each(|(file_id, edit)| self.insert_source_edit(file_id, edit));
     }
 }
 
-impl From<Vec<SourceFileEdit>> for SourceChange {
-    fn from(source_file_edits: Vec<SourceFileEdit>) -> SourceChange {
+impl From<FxHashMap<FileId, TextEdit>> for SourceChange {
+    fn from(source_file_edits: FxHashMap<FileId, TextEdit>) -> SourceChange {
         SourceChange { source_file_edits, file_system_edits: Vec::new(), is_snippet: false }
     }
 }
@@ -51,7 +81,7 @@ pub enum FileSystemEdit {
 impl From<FileSystemEdit> for SourceChange {
     fn from(edit: FileSystemEdit) -> SourceChange {
         SourceChange {
-            source_file_edits: Vec::new(),
+            source_file_edits: Default::default(),
             file_system_edits: vec![edit],
             is_snippet: false,
         }