11 files changed, 278 insertions, 82 deletions

diff --git a/crates/ra_hir_def/src/find_path.rs b/crates/ra_hir_def/src/find_path.rs
index 8cc2fb160..43b9b124a 100644
--- a/crates/ra_hir_def/src/find_path.rs
+++ b/crates/ra_hir_def/src/find_path.rs
@@ -7,10 +7,39 @@ use crate::{
     visibility::Visibility,
     CrateId, ModuleDefId, ModuleId,
 };
-use hir_expand::name::Name;
+use hir_expand::name::{known, Name};
+use test_utils::tested_by;
 
 const MAX_PATH_LEN: usize = 15;
 
+impl ModPath {
+    fn starts_with_std(&self) -> bool {
+        self.segments.first().filter(|&first_segment| first_segment == &known::std).is_some()
+    }
+
+    // When std library is present, paths starting with `std::`
+    // should be preferred over paths starting with `core::` and `alloc::`
+    fn should_start_with_std(&self) -> bool {
+        self.segments
+            .first()
+            .filter(|&first_segment| {
+                first_segment == &known::alloc || first_segment == &known::core
+            })
+            .is_some()
+    }
+
+    fn len(&self) -> usize {
+        self.segments.len()
+            + match self.kind {
+                PathKind::Plain => 0,
+                PathKind::Super(i) => i as usize,
+                PathKind::Crate => 1,
+                PathKind::Abs => 0,
+                PathKind::DollarCrate(_) => 1,
+            }
+    }
+}
+
 // FIXME: handle local items
 
 /// Find a path that can be used to refer to a certain item. This can depend on
@@ -112,23 +141,27 @@ fn find_path_inner(
             Some(path) => path,
         };
         path.segments.push(name);
-        if path_len(&path) < best_path_len {
-            best_path_len = path_len(&path);
-            best_path = Some(path);
-        }
+
+        let new_path =
+            if let Some(best_path) = best_path { select_best_path(best_path, path) } else { path };
+        best_path_len = new_path.len();
+        best_path = Some(new_path);
     }
     best_path
 }
 
-fn path_len(path: &ModPath) -> usize {
-    path.segments.len()
-        + match path.kind {
-            PathKind::Plain => 0,
-            PathKind::Super(i) => i as usize,
-            PathKind::Crate => 1,
-            PathKind::Abs => 0,
-            PathKind::DollarCrate(_) => 1,
-        }
+fn select_best_path(old_path: ModPath, new_path: ModPath) -> ModPath {
+    if old_path.starts_with_std() && new_path.should_start_with_std() {
+        tested_by!(prefer_std_paths);
+        old_path
+    } else if new_path.starts_with_std() && old_path.should_start_with_std() {
+        tested_by!(prefer_std_paths);
+        new_path
+    } else if new_path.len() < old_path.len() {
+        new_path
+    } else {
+        old_path
+    }
 }
 
 fn find_importable_locations(
@@ -201,6 +234,7 @@ mod tests {
     use hir_expand::hygiene::Hygiene;
     use ra_db::fixture::WithFixture;
     use ra_syntax::ast::AstNode;
+    use test_utils::covers;
 
     /// `code` needs to contain a cursor marker; checks that `find_path` for the
     /// item the `path` refers to returns that same path when called from the
@@ -452,4 +486,41 @@ mod tests {
         "#;
         check_found_path(code, "crate::foo::S");
     }
+
+    #[test]
+    fn prefer_std_paths_over_alloc() {
+        covers!(prefer_std_paths);
+        let code = r#"
+        //- /main.rs crate:main deps:alloc,std
+        <|>
+
+        //- /std.rs crate:std deps:alloc
+        pub mod sync {
+            pub use alloc::sync::Arc;
+        }
+
+        //- /zzz.rs crate:alloc
+        pub mod sync {
+            pub struct Arc;
+        }
+        "#;
+        check_found_path(code, "std::sync::Arc");
+    }
+
+    #[test]
+    fn prefer_shorter_paths_if_not_alloc() {
+        let code = r#"
+        //- /main.rs crate:main deps:megaalloc,std
+        <|>
+
+        //- /std.rs crate:std deps:megaalloc
+        pub mod sync {
+            pub use megaalloc::sync::Arc;
+        }
+
+        //- /zzz.rs crate:megaalloc
+        pub struct Arc;
+        "#;
+        check_found_path(code, "megaalloc::Arc");
+    }
 }
diff --git a/crates/ra_hir_def/src/generics.rs b/crates/ra_hir_def/src/generics.rs
index e9c28c730..f765e6edc 100644
--- a/crates/ra_hir_def/src/generics.rs
+++ b/crates/ra_hir_def/src/generics.rs
@@ -27,8 +27,16 @@ use crate::{
 /// Data about a generic parameter (to a function, struct, impl, ...).
 #[derive(Clone, PartialEq, Eq, Debug)]
 pub struct TypeParamData {
-    pub name: Name,
+    pub name: Option<Name>,
     pub default: Option<TypeRef>,
+    pub provenance: TypeParamProvenance,
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Debug)]
+pub enum TypeParamProvenance {
+    TypeParamList,
+    TraitSelf,
+    ArgumentImplTrait,
 }
 
 /// Data about the generic parameters of a function, struct, impl, etc.
@@ -45,10 +53,17 @@ pub struct GenericParams {
 /// associated type bindings like `Iterator<Item = u32>`.
 #[derive(Clone, PartialEq, Eq, Debug)]
 pub struct WherePredicate {
-    pub type_ref: TypeRef,
+    pub target: WherePredicateTarget,
     pub bound: TypeBound,
 }
 
+#[derive(Clone, PartialEq, Eq, Debug)]
+pub enum WherePredicateTarget {
+    TypeRef(TypeRef),
+    /// For desugared where predicates that can directly refer to a type param.
+    TypeParam(LocalTypeParamId),
+}
+
 type SourceMap = ArenaMap<LocalTypeParamId, Either<ast::TraitDef, ast::TypeParam>>;
 
 impl GenericParams {
@@ -68,6 +83,11 @@ impl GenericParams {
             GenericDefId::FunctionId(it) => {
                 let src = it.lookup(db).source(db);
                 generics.fill(&mut sm, &src.value);
+                // lower `impl Trait` in arguments
+                let data = db.function_data(it);
+                for param in &data.params {
+                    generics.fill_implicit_impl_trait_args(param);
+                }
                 src.file_id
             }
             GenericDefId::AdtId(AdtId::StructId(it)) => {
@@ -89,8 +109,11 @@ impl GenericParams {
                 let src = it.lookup(db).source(db);
 
                 // traits get the Self type as an implicit first type parameter
-                let self_param_id =
-                    generics.types.alloc(TypeParamData { name: name![Self], default: None });
+                let self_param_id = generics.types.alloc(TypeParamData {
+                    name: Some(name![Self]),
+                    default: None,
+                    provenance: TypeParamProvenance::TraitSelf,
+                });
                 sm.insert(self_param_id, Either::Left(src.value.clone()));
                 // add super traits as bounds on Self
                 // i.e., trait Foo: Bar is equivalent to trait Foo where Self: Bar
@@ -142,7 +165,11 @@ impl GenericParams {
             let name = type_param.name().map_or_else(Name::missing, |it| it.as_name());
             // FIXME: Use `Path::from_src`
             let default = type_param.default_type().map(TypeRef::from_ast);
-            let param = TypeParamData { name: name.clone(), default };
+            let param = TypeParamData {
+                name: Some(name.clone()),
+                default,
+                provenance: TypeParamProvenance::TypeParamList,
+            };
             let param_id = self.types.alloc(param);
             sm.insert(param_id, Either::Right(type_param.clone()));
 
@@ -170,11 +197,43 @@ impl GenericParams {
             return;
         }
         let bound = TypeBound::from_ast(bound);
-        self.where_predicates.push(WherePredicate { type_ref, bound });
+        self.where_predicates
+            .push(WherePredicate { target: WherePredicateTarget::TypeRef(type_ref), bound });
+    }
+
+    fn fill_implicit_impl_trait_args(&mut self, type_ref: &TypeRef) {
+        type_ref.walk(&mut |type_ref| {
+            if let TypeRef::ImplTrait(bounds) = type_ref {
+                let param = TypeParamData {
+                    name: None,
+                    default: None,
+                    provenance: TypeParamProvenance::ArgumentImplTrait,
+                };
+                let param_id = self.types.alloc(param);
+                for bound in bounds {
+                    self.where_predicates.push(WherePredicate {
+                        target: WherePredicateTarget::TypeParam(param_id),
+                        bound: bound.clone(),
+                    });
+                }
+            }
+        });
     }
 
     pub fn find_by_name(&self, name: &Name) -> Option<LocalTypeParamId> {
-        self.types.iter().find_map(|(id, p)| if &p.name == name { Some(id) } else { None })
+        self.types
+            .iter()
+            .find_map(|(id, p)| if p.name.as_ref() == Some(name) { Some(id) } else { None })
+    }
+
+    pub fn find_trait_self_param(&self) -> Option<LocalTypeParamId> {
+        self.types.iter().find_map(|(id, p)| {
+            if p.provenance == TypeParamProvenance::TraitSelf {
+                Some(id)
+            } else {
+                None
+            }
+        })
     }
 }
 
diff --git a/crates/ra_hir_def/src/marks.rs b/crates/ra_hir_def/src/marks.rs
index 457ba4abe..daa49d5f1 100644
--- a/crates/ra_hir_def/src/marks.rs
+++ b/crates/ra_hir_def/src/marks.rs
@@ -13,4 +13,5 @@ test_utils::marks!(
     macro_dollar_crate_self
     macro_dollar_crate_other
     infer_resolve_while_let
+    prefer_std_paths
 );
diff --git a/crates/ra_hir_def/src/nameres.rs b/crates/ra_hir_def/src/nameres.rs
index 27c12e46c..852304dd0 100644
--- a/crates/ra_hir_def/src/nameres.rs
+++ b/crates/ra_hir_def/src/nameres.rs
@@ -229,6 +229,46 @@ impl CrateDefMap {
             self.resolve_path_fp_with_macro(db, ResolveMode::Other, original_module, path, shadow);
         (res.resolved_def, res.segment_index)
     }
+
+    // FIXME: this can use some more human-readable format (ideally, an IR
+    // even), as this should be a great debugging aid.
+    pub fn dump(&self) -> String {
+        let mut buf = String::new();
+        go(&mut buf, self, "\ncrate", self.root);
+        return buf.trim().to_string();
+
+        fn go(buf: &mut String, map: &CrateDefMap, path: &str, module: LocalModuleId) {
+            *buf += path;
+            *buf += "\n";
+
+            let mut entries: Vec<_> = map.modules[module].scope.resolutions().collect();
+            entries.sort_by_key(|(name, _)| name.clone());
+
+            for (name, def) in entries {
+                *buf += &format!("{}:", name);
+
+                if def.types.is_some() {
+                    *buf += " t";
+                }
+                if def.values.is_some() {
+                    *buf += " v";
+                }
+                if def.macros.is_some() {
+                    *buf += " m";
+                }
+                if def.is_none() {
+                    *buf += " _";
+                }
+
+                *buf += "\n";
+            }
+
+            for (name, child) in map.modules[module].children.iter() {
+                let path = path.to_string() + &format!("::{}", name);
+                go(buf, map, &path, *child);
+            }
+        }
+    }
 }
 
 impl ModuleData {
diff --git a/crates/ra_hir_def/src/nameres/collector.rs b/crates/ra_hir_def/src/nameres/collector.rs
index 7499dff31..6352c71ef 100644
--- a/crates/ra_hir_def/src/nameres/collector.rs
+++ b/crates/ra_hir_def/src/nameres/collector.rs
@@ -22,7 +22,7 @@ use crate::{
         diagnostics::DefDiagnostic, mod_resolution::ModDir, path_resolution::ReachedFixedPoint,
         raw, BuiltinShadowMode, CrateDefMap, ModuleData, ModuleOrigin, ResolveMode,
     },
-    path::{ModPath, PathKind},
+    path::{ImportAlias, ModPath, PathKind},
     per_ns::PerNs,
     visibility::Visibility,
     AdtId, AstId, ConstLoc, ContainerId, EnumLoc, EnumVariantId, FunctionLoc, ImplLoc, Intern,
@@ -438,7 +438,11 @@ where
         } else {
             match import.path.segments.last() {
                 Some(last_segment) => {
-                    let name = import.alias.clone().unwrap_or_else(|| last_segment.clone());
+                    let name = match &import.alias {
+                        Some(ImportAlias::Alias(name)) => name.clone(),
+                        Some(ImportAlias::Underscore) => last_segment.clone(), // FIXME rust-analyzer#2736
+                        None => last_segment.clone(),
+                    };
                     log::debug!("resolved import {:?} ({:?}) to {:?}", name, import, def);
 
                     // extern crates in the crate root are special-cased to insert entries into the extern prelude: rust-lang/rust#54658
diff --git a/crates/ra_hir_def/src/nameres/raw.rs b/crates/ra_hir_def/src/nameres/raw.rs
index fac1169ef..650cf1f98 100644
--- a/crates/ra_hir_def/src/nameres/raw.rs
+++ b/crates/ra_hir_def/src/nameres/raw.rs
@@ -22,8 +22,11 @@ use ra_syntax::{
 use test_utils::tested_by;
 
 use crate::{
-    attr::Attrs, db::DefDatabase, path::ModPath, visibility::RawVisibility, FileAstId, HirFileId,
-    InFile,
+    attr::Attrs,
+    db::DefDatabase,
+    path::{ImportAlias, ModPath},
+    visibility::RawVisibility,
+    FileAstId, HirFileId, InFile,
 };
 
 /// `RawItems` is a set of top-level items in a file (except for impls).
@@ -145,7 +148,7 @@ impl_arena_id!(Import);
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct ImportData {
     pub(super) path: ModPath,
-    pub(super) alias: Option<Name>,
+    pub(super) alias: Option<ImportAlias>,
     pub(super) is_glob: bool,
     pub(super) is_prelude: bool,
     pub(super) is_extern_crate: bool,
@@ -353,7 +356,11 @@ impl RawItemsCollector {
             let path = ModPath::from_name_ref(&name_ref);
             let visibility =
                 RawVisibility::from_ast_with_hygiene(extern_crate.visibility(), &self.hygiene);
-            let alias = extern_crate.alias().and_then(|a| a.name()).map(|it| it.as_name());
+            let alias = extern_crate.alias().map(|a| {
+                a.name()
+                    .map(|it| it.as_name())
+                    .map_or(ImportAlias::Underscore, |a| ImportAlias::Alias(a))
+            });
             let attrs = self.parse_attrs(&extern_crate);
             // FIXME: cfg_attr
             let is_macro_use = extern_crate.has_atom_attr("macro_use");
diff --git a/crates/ra_hir_def/src/nameres/tests.rs b/crates/ra_hir_def/src/nameres/tests.rs
index 78bcdc850..82f0f835c 100644
--- a/crates/ra_hir_def/src/nameres/tests.rs
+++ b/crates/ra_hir_def/src/nameres/tests.rs
@@ -10,11 +10,10 @@ use insta::assert_snapshot;
 use ra_db::{fixture::WithFixture, SourceDatabase};
 use test_utils::covers;
 
-use crate::{db::DefDatabase, nameres::*, test_db::TestDB, LocalModuleId};
+use crate::{db::DefDatabase, nameres::*, test_db::TestDB};
 
 fn def_map(fixture: &str) -> String {
-    let dm = compute_crate_def_map(fixture);
-    render_crate_def_map(&dm)
+    compute_crate_def_map(fixture).dump()
 }
 
 fn compute_crate_def_map(fixture: &str) -> Arc<CrateDefMap> {
@@ -23,44 +22,6 @@ fn compute_crate_def_map(fixture: &str) -> Arc<CrateDefMap> {
     db.crate_def_map(krate)
 }
 
-fn render_crate_def_map(map: &CrateDefMap) -> String {
-    let mut buf = String::new();
-    go(&mut buf, map, "\ncrate", map.root);
-    return buf.trim().to_string();
-
-    fn go(buf: &mut String, map: &CrateDefMap, path: &str, module: LocalModuleId) {
-        *buf += path;
-        *buf += "\n";
-
-        let mut entries: Vec<_> = map.modules[module].scope.resolutions().collect();
-        entries.sort_by_key(|(name, _)| name.clone());
-
-        for (name, def) in entries {
-            *buf += &format!("{}:", name);
-
-            if def.types.is_some() {
-                *buf += " t";
-            }
-            if def.values.is_some() {
-                *buf += " v";
-            }
-            if def.macros.is_some() {
-                *buf += " m";
-            }
-            if def.is_none() {
-                *buf += " _";
-            }
-
-            *buf += "\n";
-        }
-
-        for (name, child) in map.modules[module].children.iter() {
-            let path = path.to_string() + &format!("::{}", name);
-            go(buf, map, &path, *child);
-        }
-    }
-}
-
 #[test]
 fn crate_def_map_smoke_test() {
     let map = def_map(
diff --git a/crates/ra_hir_def/src/path.rs b/crates/ra_hir_def/src/path.rs
index ab290e2c9..246032c13 100644
--- a/crates/ra_hir_def/src/path.rs
+++ b/crates/ra_hir_def/src/path.rs
@@ -16,13 +16,13 @@ use ra_syntax::ast;
 
 use crate::{type_ref::TypeRef, InFile};
 
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub struct ModPath {
     pub kind: PathKind,
     pub segments: Vec<Name>,
 }
 
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub enum PathKind {
     Plain,
     /// `self::` is `Super(0)`
@@ -34,6 +34,14 @@ pub enum PathKind {
     DollarCrate(CrateId),
 }
 
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub enum ImportAlias {
+    /// Unnamed alias, as in `use Foo as _;`
+    Underscore,
+    /// Named alias
+    Alias(Name),
+}
+
 impl ModPath {
     pub fn from_src(path: ast::Path, hygiene: &Hygiene) -> Option<ModPath> {
         lower::lower_path(path, hygiene).map(|it| it.mod_path)
@@ -57,7 +65,7 @@ impl ModPath {
     pub(crate) fn expand_use_item(
         item_src: InFile<ast::UseItem>,
         hygiene: &Hygiene,
-        mut cb: impl FnMut(ModPath, &ast::UseTree, /* is_glob */ bool, Option<Name>),
+        mut cb: impl FnMut(ModPath, &ast::UseTree, /* is_glob */ bool, Option<ImportAlias>),
     ) {
         if let Some(tree) = item_src.value.use_tree() {
             lower::lower_use_tree(None, tree, hygiene, &mut cb);
diff --git a/crates/ra_hir_def/src/path/lower/lower_use.rs b/crates/ra_hir_def/src/path/lower/lower_use.rs
index 531878174..d2bc9d193 100644
--- a/crates/ra_hir_def/src/path/lower/lower_use.rs
+++ b/crates/ra_hir_def/src/path/lower/lower_use.rs
@@ -4,20 +4,17 @@
 use std::iter;
 
 use either::Either;
-use hir_expand::{
-    hygiene::Hygiene,
-    name::{AsName, Name},
-};
+use hir_expand::{hygiene::Hygiene, name::AsName};
 use ra_syntax::ast::{self, NameOwner};
 use test_utils::tested_by;
 
-use crate::path::{ModPath, PathKind};
+use crate::path::{ImportAlias, ModPath, PathKind};
 
 pub(crate) fn lower_use_tree(
     prefix: Option<ModPath>,
     tree: ast::UseTree,
     hygiene: &Hygiene,
-    cb: &mut dyn FnMut(ModPath, &ast::UseTree, bool, Option<Name>),
+    cb: &mut dyn FnMut(ModPath, &ast::UseTree, bool, Option<ImportAlias>),
 ) {
     if let Some(use_tree_list) = tree.use_tree_list() {
         let prefix = match tree.path() {
@@ -34,7 +31,11 @@ pub(crate) fn lower_use_tree(
             lower_use_tree(prefix.clone(), child_tree, hygiene, cb);
         }
     } else {
-        let alias = tree.alias().and_then(|a| a.name()).map(|a| a.as_name());
+        let alias = tree.alias().map(|a| {
+            a.name()
+                .map(|it| it.as_name())
+                .map_or(ImportAlias::Underscore, |a| ImportAlias::Alias(a))
+        });
         let is_glob = tree.has_star();
         if let Some(ast_path) = tree.path() {
             // Handle self in a path.
diff --git a/crates/ra_hir_def/src/resolver.rs b/crates/ra_hir_def/src/resolver.rs
index f7bac5801..05cf4646a 100644
--- a/crates/ra_hir_def/src/resolver.rs
+++ b/crates/ra_hir_def/src/resolver.rs
@@ -490,10 +490,12 @@ impl Scope {
             }
             Scope::GenericParams { params, def } => {
                 for (local_id, param) in params.types.iter() {
-                    f(
-                        param.name.clone(),
-                        ScopeDef::GenericParam(TypeParamId { local_id, parent: *def }),
-                    )
+                    if let Some(name) = &param.name {
+                        f(
+                            name.clone(),
+                            ScopeDef::GenericParam(TypeParamId { local_id, parent: *def }),
+                        )
+                    }
                 }
             }
             Scope::ImplBlockScope(i) => {
diff --git a/crates/ra_hir_def/src/type_ref.rs b/crates/ra_hir_def/src/type_ref.rs
index 5f10e9a88..102fdb13d 100644
--- a/crates/ra_hir_def/src/type_ref.rs
+++ b/crates/ra_hir_def/src/type_ref.rs
@@ -124,6 +124,48 @@ impl TypeRef {
     pub(crate) fn unit() -> TypeRef {
         TypeRef::Tuple(Vec::new())
     }
+
+    pub fn walk(&self, f: &mut impl FnMut(&TypeRef)) {
+        go(self, f);
+
+        fn go(type_ref: &TypeRef, f: &mut impl FnMut(&TypeRef)) {
+            f(type_ref);
+            match type_ref {
+                TypeRef::Fn(types) | TypeRef::Tuple(types) => types.iter().for_each(|t| go(t, f)),
+                TypeRef::RawPtr(type_ref, _)
+                | TypeRef::Reference(type_ref, _)
+                | TypeRef::Array(type_ref)
+                | TypeRef::Slice(type_ref) => go(&type_ref, f),
+                TypeRef::ImplTrait(bounds) | TypeRef::DynTrait(bounds) => {
+                    for bound in bounds {
+                        match bound {
+                            TypeBound::Path(path) => go_path(path, f),
+                            TypeBound::Error => (),
+                        }
+                    }
+                }
+                TypeRef::Path(path) => go_path(path, f),
+                TypeRef::Never | TypeRef::Placeholder | TypeRef::Error => {}
+            };
+        }
+
+        fn go_path(path: &Path, f: &mut impl FnMut(&TypeRef)) {
+            if let Some(type_ref) = path.type_anchor() {
+                go(type_ref, f);
+            }
+            for segment in path.segments().iter() {
+                if let Some(args_and_bindings) = segment.args_and_bindings {
+                    for arg in &args_and_bindings.args {
+                        let crate::path::GenericArg::Type(type_ref) = arg;
+                        go(type_ref, f);
+                    }
+                    for (_, type_ref) in &args_and_bindings.bindings {
+                        go(type_ref, f);
+                    }
+                }
+            }
+        }
+    }
 }
 
 pub(crate) fn type_bounds_from_ast(type_bounds_opt: Option<ast::TypeBoundList>) -> Vec<TypeBound> {