Repository: rust-analyzer/rust-analyzer
Pull request #10976 (2021-12-09 18:19:38)

fix: Show case-insensitive exact matches instead of fuzzy flyimport for short paths
And raise the fuzzy trigger from 2 to 3 chars. This way we keep the ability of flyimporting short names like `Rc`.
Fixes https://github.com/rust-analyzer/rust-analyzer/issues/6917
bors r+

bors[bot]: Build failed:
  * [Rust (ubuntu-latest)](https://github.com/rust-analyzer/rust-analyzer/runs/4474514692?check_suite_focus=true)

Patch:
diff --git a/crates/hir/src/display.rs b/crates/hir/src/display.rs
index 17465dc2b0..38bbf41797 100644
--- a/crates/hir/src/display.rs
+++ b/crates/hir/src/display.rs
@@ -12,10 +12,7 @@ use hir_ty::{
     },
     Interner, TraitRefExt, WhereClause,
 };
-use syntax::{
-    ast::{self, HasName},
-    SmolStr,
-};
+use syntax::ast::{self, HasName};
 
 use crate::{
     Adt, Const, ConstParam, Enum, Field, Function, GenericParam, HasCrate, HasVisibility,
@@ -250,8 +247,7 @@ impl HirDisplay for TypeParam {
             bounds.iter().cloned().map(|b| b.substitute(&Interner, &substs)).collect();
         let krate = self.id.parent.krate(f.db).id;
         let sized_trait =
-            f.db.lang_item(krate, SmolStr::new_inline("sized"))
-                .and_then(|lang_item| lang_item.as_trait());
+            f.db.lang_item(krate, "sized".into()).and_then(|lang_item| lang_item.as_trait());
         let has_only_sized_bound = predicates.iter().all(move |pred| match pred.skip_binders() {
             WhereClause::Implemented(it) => Some(it.hir_trait_id()) == sized_trait,
             _ => false,
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index 7add0f4a43..3e04ea8da9 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -2427,7 +2427,7 @@ impl Type {
         let krate = self.krate;
 
         let std_future_trait =
-            db.lang_item(krate, SmolStr::new_inline("future_trait")).and_then(|it| it.as_trait());
+            db.lang_item(krate, "future_trait".into()).and_then(|it| it.as_trait());
         let std_future_trait = match std_future_trait {
             Some(it) => it,
             None => return false,
@@ -2516,7 +2516,7 @@ impl Type {
     }
 
     pub fn is_copy(&self, db: &dyn HirDatabase) -> bool {
-        let lang_item = db.lang_item(self.krate, SmolStr::new_inline("copy"));
+        let lang_item = db.lang_item(self.krate, SmolStr::new("copy"));
         let copy_trait = match lang_item {
             Some(LangItemTarget::TraitId(it)) => it,
             _ => return false,
@@ -2623,15 +2623,13 @@ impl Type {
     }
 
     pub fn autoderef<'a>(&'a self, db: &'a dyn HirDatabase) -> impl Iterator<Item = Type> + 'a {
-        self.autoderef_(db).map(move |ty| self.derived(ty))
-    }
-
-    pub fn autoderef_<'a>(&'a self, db: &'a dyn HirDatabase) -> impl Iterator<Item = Ty> + 'a {
         // There should be no inference vars in types passed here
         let canonical = hir_ty::replace_errors_with_variables(&self.ty);
         let environment = self.env.env.clone();
         let ty = InEnvironment { goal: canonical, environment };
-        autoderef(db, Some(self.krate), ty).map(|canonical| canonical.value)
+        autoderef(db, Some(self.krate), ty)
+            .map(|canonical| canonical.value)
+            .map(move |ty| self.derived(ty))
     }
 
     // This would be nicer if it just returned an iterator, but that runs into
@@ -2810,32 +2808,22 @@ impl Type {
         db: &'a dyn HirDatabase,
     ) -> impl Iterator<Item = Trait> + 'a {
         let _p = profile::span("applicable_inherent_traits");
-        self.autoderef_(db)
-            .filter_map(|ty| ty.dyn_trait())
+        self.autoderef(db)
+            .filter_map(|derefed_type| derefed_type.ty.dyn_trait())
             .flat_map(move |dyn_trait_id| hir_ty::all_super_traits(db.upcast(), dyn_trait_id))
             .map(Trait::from)
     }
 
-    pub fn env_traits<'a>(&'a self, db: &'a dyn HirDatabase) -> impl Iterator<Item = Trait> + 'a {
-        let _p = profile::span("env_traits");
-        self.autoderef_(db)
-            .filter(|ty| matches!(ty.kind(&Interner), TyKind::Placeholder(_)))
-            .flat_map(|ty| {
-                self.env
-                    .traits_in_scope_from_clauses(ty)
-                    .flat_map(|t| hir_ty::all_super_traits(db.upcast(), t))
-            })
-            .map(Trait::from)
-    }
-
-    pub fn as_impl_traits(&self, db: &dyn HirDatabase) -> Option<impl Iterator<Item = Trait>> {
+    pub fn as_impl_traits(&self, db: &dyn HirDatabase) -> Option<Vec<Trait>> {
         self.ty.impl_trait_bounds(db).map(|it| {
-            it.into_iter().filter_map(|pred| match pred.skip_binders() {
-                hir_ty::WhereClause::Implemented(trait_ref) => {
-                    Some(Trait::from(trait_ref.hir_trait_id()))
-                }
-                _ => None,
-            })
+            it.into_iter()
+                .filter_map(|pred| match pred.skip_binders() {
+                    hir_ty::WhereClause::Implemented(trait_ref) => {
+                        Some(Trait::from(trait_ref.hir_trait_id()))
+                    }
+                    _ => None,
+                })
+                .collect()
         })
     }
 
diff --git a/crates/hir_expand/src/builtin_fn_macro.rs b/crates/hir_expand/src/builtin_fn_macro.rs
index 57e66e5cc4..3add4c1103 100644
--- a/crates/hir_expand/src/builtin_fn_macro.rs
+++ b/crates/hir_expand/src/builtin_fn_macro.rs
@@ -386,18 +386,7 @@ fn concat_expand(
 ) -> ExpandResult<Option<ExpandedEager>> {
     let mut err = None;
     let mut text = String::new();
-    for (i, mut t) in tt.token_trees.iter().enumerate() {
-        // FIXME: hack on top of a hack: `$e:expr` captures get surrounded in parentheses
-        // to ensure the right parsing order, so skip the parentheses here. Ideally we'd
-        // implement rustc's model. cc https://github.com/rust-analyzer/rust-analyzer/pull/10623
-        if let tt::TokenTree::Subtree(tt::Subtree { delimiter: Some(delim), token_trees }) = t {
-            if let [tt] = &**token_trees {
-                if delim.kind == tt::DelimiterKind::Parenthesis {
-                    t = tt;
-                }
-            }
-        }
-
+    for (i, t) in tt.token_trees.iter().enumerate() {
         match t {
             tt::TokenTree::Leaf(tt::Leaf::Literal(it)) if i % 2 == 0 => {
                 // concat works with string and char literals, so remove any quotes.
diff --git a/crates/hir_ty/src/autoderef.rs b/crates/hir_ty/src/autoderef.rs
index 2d3d16cda0..1eb5490507 100644
--- a/crates/hir_ty/src/autoderef.rs
+++ b/crates/hir_ty/src/autoderef.rs
@@ -10,7 +10,6 @@ use chalk_ir::{cast::Cast, fold::Fold, interner::HasInterner, VariableKind};
 use hir_def::lang_item::LangItemTarget;
 use hir_expand::name::name;
 use limit::Limit;
-use syntax::SmolStr;
 use tracing::{info, warn};
 
 use crate::{
@@ -72,10 +71,7 @@ impl Iterator for Autoderef<'_> {
         }
 
         let (kind, new_ty) = if let Some(derefed) = builtin_deref(&self.ty.value) {
-            (
-                AutoderefKind::Builtin,
-                Canonical { value: derefed.clone(), binders: self.ty.binders.clone() },
-            )
+            (AutoderefKind::Builtin, Canonical { value: derefed, binders: self.ty.binders.clone() })
         } else {
             (
                 AutoderefKind::Overloaded,
@@ -114,17 +110,15 @@ pub(crate) fn deref(
 ) -> Option<Canonical<Ty>> {
     let _p = profile::span("deref");
     match builtin_deref(&ty.goal.value) {
-        Some(derefed) => {
-            Some(Canonical { value: derefed.clone(), binders: ty.goal.binders.clone() })
-        }
+        Some(derefed) => Some(Canonical { value: derefed, binders: ty.goal.binders.clone() }),
         None => deref_by_trait(db, krate, ty),
     }
 }
 
-fn builtin_deref(ty: &Ty) -> Option<&Ty> {
+fn builtin_deref(ty: &Ty) -> Option<Ty> {
     match ty.kind(&Interner) {
-        TyKind::Ref(.., ty) => Some(ty),
-        TyKind::Raw(.., ty) => Some(ty),
+        TyKind::Ref(.., ty) => Some(ty.clone()),
+        TyKind::Raw(.., ty) => Some(ty.clone()),
         _ => None,
     }
 }
@@ -135,7 +129,7 @@ fn deref_by_trait(
     ty: InEnvironment<&Canonical<Ty>>,
 ) -> Option<Canonical<Ty>> {
     let _p = profile::span("deref_by_trait");
-    let deref_trait = match db.lang_item(krate, SmolStr::new_inline("deref"))? {
+    let deref_trait = match db.lang_item(krate, "deref".into())? {
         LangItemTarget::TraitId(it) => it,
         _ => return None,
     };
diff --git a/crates/hir_ty/src/chalk_db.rs b/crates/hir_ty/src/chalk_db.rs
index 4a7b2d7363..dc5dcd163c 100644
--- a/crates/hir_ty/src/chalk_db.rs
+++ b/crates/hir_ty/src/chalk_db.rs
@@ -3,7 +3,6 @@
 use std::sync::Arc;
 
 use cov_mark::hit;
-use syntax::SmolStr;
 use tracing::debug;
 
 use chalk_ir::{cast::Cast, fold::shift::Shift, CanonicalVarKinds};
@@ -214,7 +213,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
             crate::ImplTraitId::AsyncBlockTypeImplTrait(..) => {
                 if let Some((future_trait, future_output)) = self
                     .db
-                    .lang_item(self.krate, SmolStr::new_inline("future_trait"))
+                    .lang_item(self.krate, "future_trait".into())
                     .and_then(|item| item.as_trait())
                     .and_then(|trait_| {
                         let alias =
@@ -420,7 +419,7 @@ pub(crate) fn associated_ty_data_query(
     if !ctx.unsized_types.borrow().contains(&self_ty) {
         let sized_trait = resolver
             .krate()
-            .and_then(|krate| db.lang_item(krate, SmolStr::new_inline("sized")))
+            .and_then(|krate| db.lang_item(krate, "sized".into()))
             .and_then(|lang_item| lang_item.as_trait().map(to_chalk_trait_id));
         let sized_bound = sized_trait.into_iter().map(|sized_trait| {
             let trait_bound =
diff --git a/crates/hir_ty/src/chalk_ext.rs b/crates/hir_ty/src/chalk_ext.rs
index 97d1ad0f9c..653c4d5ec8 100644
--- a/crates/hir_ty/src/chalk_ext.rs
+++ b/crates/hir_ty/src/chalk_ext.rs
@@ -6,7 +6,6 @@ use hir_def::{
     type_ref::Rawness,
     FunctionId, GenericDefId, HasModule, ItemContainerId, Lookup, TraitId,
 };
-use syntax::SmolStr;
 
 use crate::{
     db::HirDatabase, from_assoc_type_id, from_chalk_trait_id, from_foreign_def_id,
@@ -188,7 +187,7 @@ impl TyExt for Ty {
                     ImplTraitId::AsyncBlockTypeImplTrait(def, _expr) => {
                         let krate = def.module(db.upcast()).krate();
                         if let Some(future_trait) = db
-                            .lang_item(krate, SmolStr::new_inline("future_trait"))
+                            .lang_item(krate, "future_trait".into())
                             .and_then(|item| item.as_trait())
                         {
                             // This is only used by type walking.
diff --git a/crates/hir_ty/src/diagnostics/match_check/deconstruct_pat.rs b/crates/hir_ty/src/diagnostics/match_check/deconstruct_pat.rs
index f268746809..f9439c706e 100644
--- a/crates/hir_ty/src/diagnostics/match_check/deconstruct_pat.rs
+++ b/crates/hir_ty/src/diagnostics/match_check/deconstruct_pat.rs
@@ -50,7 +50,6 @@ use std::{
 use hir_def::{EnumVariantId, HasModule, LocalFieldId, VariantId};
 use smallvec::{smallvec, SmallVec};
 use stdx::never;
-use syntax::SmolStr;
 
 use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind};
 
@@ -906,7 +905,7 @@ fn is_field_list_non_exhaustive(variant_id: VariantId, cx: &MatchCheckCtx<'_>) -
 
 fn adt_is_box(adt: hir_def::AdtId, cx: &MatchCheckCtx<'_>) -> bool {
     use hir_def::lang_item::LangItemTarget;
-    match cx.db.lang_item(cx.module.krate(), SmolStr::new_inline("owned_box")) {
+    match cx.db.lang_item(cx.module.krate(), "owned_box".into()) {
         Some(LangItemTarget::StructId(box_id)) => adt == box_id.into(),
         _ => false,
     }
diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs
index c09f8db86e..307323690a 100644
--- a/crates/hir_ty/src/display.rs
+++ b/crates/hir_ty/src/display.rs
@@ -20,7 +20,6 @@ use hir_def::{
 };
 use hir_expand::{hygiene::Hygiene, name::Name};
 use itertools::Itertools;
-use syntax::SmolStr;
 
 use crate::{
     const_from_placeholder_idx,
@@ -775,9 +774,8 @@ impl SizedByDefault {
         match self {
             Self::NotSized => false,
             Self::Sized { anchor } => {
-                let sized_trait = db
-                    .lang_item(anchor, SmolStr::new_inline("sized"))
-                    .and_then(|lang_item| lang_item.as_trait());
+                let sized_trait =
+                    db.lang_item(anchor, "sized".into()).and_then(|lang_item| lang_item.as_trait());
                 Some(trait_) == sized_trait
             }
         }
diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs
index aebff59113..4d7ac6fd85 100644
--- a/crates/hir_ty/src/infer/coerce.rs
+++ b/crates/hir_ty/src/infer/coerce.rs
@@ -10,7 +10,6 @@ use std::iter;
 use chalk_ir::{cast::Cast, Goal, Mutability, TyVariableKind};
 use hir_def::{expr::ExprId, lang_item::LangItemTarget};
 use stdx::always;
-use syntax::SmolStr;
 
 use crate::{
     autoderef::{Autoderef, AutoderefKind},
@@ -537,11 +536,10 @@ impl<'a> InferenceContext<'a> {
             reborrow.as_ref().map_or_else(|| from_ty.clone(), |(_, adj)| adj.target.clone());
 
         let krate = self.resolver.krate().unwrap();
-        let coerce_unsized_trait =
-            match self.db.lang_item(krate, SmolStr::new_inline("coerce_unsized")) {
-                Some(LangItemTarget::TraitId(trait_)) => trait_,
-                _ => return Err(TypeError),
-            };
+        let coerce_unsized_trait = match self.db.lang_item(krate, "coerce_unsized".into()) {
+            Some(LangItemTarget::TraitId(trait_)) => trait_,
+            _ => return Err(TypeError),
+        };
 
         let coerce_unsized_tref = {
             let b = TyBuilder::trait_ref(self.db, coerce_unsized_trait);
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index 7373c9eb8b..f7e2af46d2 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -28,7 +28,7 @@ use la_arena::ArenaMap;
 use rustc_hash::FxHashSet;
 use smallvec::SmallVec;
 use stdx::impl_from;
-use syntax::{ast, SmolStr};
+use syntax::ast;
 
 use crate::all_super_traits;
 use crate::{
@@ -797,7 +797,7 @@ impl<'a> TyLoweringContext<'a> {
                 let sized_trait = self
                     .resolver
                     .krate()
-                    .and_then(|krate| self.db.lang_item(krate, SmolStr::new_inline("sized")))
+                    .and_then(|krate| self.db.lang_item(krate, "sized".into()))
                     .and_then(|lang_item| lang_item.as_trait());
                 // Don't lower associated type bindings as the only possible relaxed trait bound
                 // `?Sized` has no of them.
@@ -895,7 +895,7 @@ impl<'a> TyLoweringContext<'a> {
                 let krate = func.lookup(ctx.db.upcast()).module(ctx.db.upcast()).krate();
                 let sized_trait = ctx
                     .db
-                    .lang_item(krate, SmolStr::new_inline("sized"))
+                    .lang_item(krate, "sized".into())
                     .and_then(|lang_item| lang_item.as_trait().map(to_chalk_trait_id));
                 let sized_clause = sized_trait.map(|trait_id| {
                     let clause = WhereClause::Implemented(TraitRef {
@@ -1200,7 +1200,7 @@ fn implicitly_sized_clauses<'a>(
     let generic_args = &substitution.as_slice(&Interner)[is_trait_def as usize..];
     let sized_trait = resolver
         .krate()
-        .and_then(|krate| db.lang_item(krate, SmolStr::new_inline("sized")))
+        .and_then(|krate| db.lang_item(krate, "sized".into()))
         .and_then(|lang_item| lang_item.as_trait().map(to_chalk_trait_id));
 
     sized_trait.into_iter().flat_map(move |sized_trait| {
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index 1549a40c91..3fbb6fea19 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -541,10 +541,9 @@ pub fn iterate_method_candidates_dyn(
             // types*.
 
             let deref_chain = autoderef_method_receiver(db, krate, ty);
-            let mut deref_chains = stdx::slice_tails(&deref_chain);
-            deref_chains.try_for_each(|deref_chain| {
+            for i in 0..deref_chain.len() {
                 iterate_method_candidates_with_autoref(
-                    deref_chain,
+                    &deref_chain[i..],
                     db,
                     env.clone(),
                     krate,
@@ -552,8 +551,9 @@ pub fn iterate_method_candidates_dyn(
                     visible_from_module,
                     name,
                     callback,
-                )
-            })
+                )?;
+            }
+            ControlFlow::Continue(())
         }
         LookupMode::Path => {
             // No autoderef for path lookups
@@ -716,14 +716,15 @@ fn iterate_trait_method_candidates(
     // if ty is `dyn Trait`, the trait doesn't need to be in scope
     let inherent_trait =
         self_ty.value.dyn_trait().into_iter().flat_map(|t| all_super_traits(db.upcast(), t));
-    let env_traits = matches!(self_ty.value.kind(&Interner), TyKind::Placeholder(_))
-        // if we have `T: Trait` in the param env, the trait doesn't need to be in scope
-        .then(|| {
-            env.traits_in_scope_from_clauses(self_ty.value.clone())
+    let env_traits = match self_ty.value.kind(&Interner) {
+        TyKind::Placeholder(_) => {
+            // if we have `T: Trait` in the param env, the trait doesn't need to be in scope
+            env.traits_in_scope_from_clauses(&self_ty.value)
                 .flat_map(|t| all_super_traits(db.upcast(), t))
-        })
-        .into_iter()
-        .flatten();
+                .collect()
+        }
+        _ => Vec::new(),
+    };
     let traits = inherent_trait.chain(env_traits).chain(traits_in_scope.iter().copied());
 
     'traits: for t in traits {
@@ -746,10 +747,10 @@ fn iterate_trait_method_candidates(
         // trait, but if we find out it doesn't, we'll skip the rest of the
         // iteration
         let mut known_implemented = false;
-        for &(_, item) in data.items.iter() {
+        for (_name, item) in data.items.iter() {
             // Don't pass a `visible_from_module` down to `is_valid_candidate`,
             // since only inherent methods should be included into visibility checking.
-            if !is_valid_candidate(db, env.clone(), name, receiver_ty, item, self_ty, None) {
+            if !is_valid_candidate(db, env.clone(), name, receiver_ty, *item, self_ty, None) {
                 continue;
             }
             if !known_implemented {
@@ -760,7 +761,7 @@ fn iterate_trait_method_candidates(
             }
             known_implemented = true;
             // FIXME: we shouldn't be ignoring the binders here
-            callback(self_ty, item)?
+            callback(self_ty, *item)?
         }
     }
     ControlFlow::Continue(())
@@ -773,14 +774,18 @@ fn filter_inherent_impls_for_self_ty<'i>(
     // inherent methods on arrays are fingerprinted as [T; {unknown}], so we must also consider them when
     // resolving a method call on an array with a known len
     let array_impls = {
-        match self_ty.kind(&Interner) {
-            TyKind::Array(parameters, array_len) if !array_len.is_unknown() => {
+        if let TyKind::Array(parameters, array_len) = self_ty.kind(&Interner) {
+            if !array_len.is_unknown() {
                 let unknown_array_len_ty =
-                    TyKind::Array(parameters.clone(), consteval::usize_const(None));
+                    TyKind::Array(parameters.clone(), consteval::usize_const(None))
+                        .intern(&Interner);
 
-                Some(impls.for_self_ty(&unknown_array_len_ty.intern(&Interner)))
+                Some(impls.for_self_ty(&unknown_array_len_ty))
+            } else {
+                None
             }
-            _ => None,
+        } else {
+            None
         }
     }
     .into_iter()
diff --git a/crates/hir_ty/src/traits.rs b/crates/hir_ty/src/traits.rs
index 0d135651c7..4b89fd5a85 100644
--- a/crates/hir_ty/src/traits.rs
+++ b/crates/hir_ty/src/traits.rs
@@ -9,7 +9,6 @@ use chalk_solve::{logging_db::LoggingRustIrDatabase, Solver};
 use base_db::CrateId;
 use hir_def::{lang_item::LangItemTarget, TraitId};
 use stdx::panic_context;
-use syntax::SmolStr;
 
 use crate::{
     db::HirDatabase, AliasEq, AliasTy, Canonical, DomainGoal, Goal, Guidance, InEnvironment,
@@ -55,13 +54,17 @@ impl TraitEnvironment {
         }
     }
 
-    pub fn traits_in_scope_from_clauses<'a>(
+    pub(crate) fn traits_in_scope_from_clauses<'a>(
         &'a self,
-        ty: Ty,
+        ty: &'a Ty,
     ) -> impl Iterator<Item = TraitId> + 'a {
-        self.traits_from_clauses
-            .iter()
-            .filter_map(move |(self_ty, trait_id)| (*self_ty == ty).then(|| *trait_id))
+        self.traits_from_clauses.iter().filter_map(move |(self_ty, trait_id)| {
+            if self_ty == ty {
+                Some(*trait_id)
+            } else {
+                None
+            }
+        })
     }
 }
 
@@ -170,7 +173,7 @@ pub enum FnTrait {
 }
 
 impl FnTrait {
-    const fn lang_item_name(self) -> &'static str {
+    fn lang_item_name(self) -> &'static str {
         match self {
             FnTrait::FnOnce => "fn_once",
             FnTrait::FnMut => "fn_mut",
@@ -179,7 +182,7 @@ impl FnTrait {
     }
 
     pub fn get_id(&self, db: &dyn HirDatabase, krate: CrateId) -> Option<TraitId> {
-        let target = db.lang_item(krate, SmolStr::new_inline(self.lang_item_name()))?;
+        let target = db.lang_item(krate, self.lang_item_name().into())?;
         match target {
             LangItemTarget::TraitId(t) => Some(t),
             _ => None,
diff --git a/crates/hir_ty/src/utils.rs b/crates/hir_ty/src/utils.rs
index f36a5f8987..a0837377c6 100644
--- a/crates/hir_ty/src/utils.rs
+++ b/crates/hir_ty/src/utils.rs
@@ -18,8 +18,6 @@ use hir_def::{
 };
 use hir_expand::name::{name, Name};
 use rustc_hash::FxHashSet;
-use smallvec::{smallvec, SmallVec};
-use syntax::SmolStr;
 
 use crate::{
     db::HirDatabase, ChalkTraitId, Interner, Substitution, TraitRef, TraitRefExt, TyKind,
@@ -28,16 +26,16 @@ use crate::{
 
 pub(crate) fn fn_traits(db: &dyn DefDatabase, krate: CrateId) -> impl Iterator<Item = TraitId> {
     [
-        db.lang_item(krate, SmolStr::new_inline("fn")),
-        db.lang_item(krate, SmolStr::new_inline("fn_mut")),
-        db.lang_item(krate, SmolStr::new_inline("fn_once")),
+        db.lang_item(krate, "fn".into()),
+        db.lang_item(krate, "fn_mut".into()),
+        db.lang_item(krate, "fn_once".into()),
     ]
     .into_iter()
     .flatten()
     .flat_map(|it| it.as_trait())
 }
 
-fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> SmallVec<[TraitId; 4]> {
+fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
     let resolver = trait_.resolver(db);
     // returning the iterator directly doesn't easily work because of
     // lifetime problems, but since there usually shouldn't be more than a
@@ -102,13 +100,13 @@ fn direct_super_trait_refs(db: &dyn HirDatabase, trait_ref: &TraitRef) -> Vec<Tr
 
 /// Returns an iterator over the whole super trait hierarchy (including the
 /// trait itself).
-pub fn all_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> SmallVec<[TraitId; 4]> {
+pub fn all_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
     // we need to take care a bit here to avoid infinite loops in case of cycles
     // (i.e. if we have `trait A: B; trait B: A;`)
-
-    let mut result = smallvec![trait_];
+    let mut result = vec![trait_];
     let mut i = 0;
-    while let Some(&t) = result.get(i) {
+    while i < result.len() {
+        let t = result[i];
         // yeah this is quadratic, but trait hierarchies should be flat
         // enough that this doesn't matter
         for tt in direct_super_traits(db, t) {
diff --git a/crates/ide/src/goto_type_definition.rs b/crates/ide/src/goto_type_definition.rs
index 55cdb3200e..031c4af0de 100644
--- a/crates/ide/src/goto_type_definition.rs
+++ b/crates/ide/src/goto_type_definition.rs
@@ -75,7 +75,7 @@ pub(crate) fn goto_type_definition(
                 } else if let Some(trait_) = t.as_dyn_trait() {
                     push(trait_.into());
                 } else if let Some(traits) = t.as_impl_traits(db) {
-                    traits.for_each(|it| push(it.into()));
+                    traits.into_iter().for_each(|it| push(it.into()));
                 } else if let Some(trait_) = t.as_associated_type_parent_trait(db) {
                     push(trait_.into());
                 }
diff --git a/crates/ide/src/hover.rs b/crates/ide/src/hover.rs
index 7d5cfaa937..dd77dd3e4b 100644
--- a/crates/ide/src/hover.rs
+++ b/crates/ide/src/hover.rs
@@ -337,7 +337,7 @@ fn walk_and_push_ty(
         } else if let Some(trait_) = t.as_dyn_trait() {
             push_new_def(trait_.into());
         } else if let Some(traits) = t.as_impl_traits(db) {
-            traits.for_each(|it| push_new_def(it.into()));
+            traits.into_iter().for_each(|it| push_new_def(it.into()));
         } else if let Some(trait_) = t.as_associated_type_parent_trait(db) {
             push_new_def(trait_.into());
         }
diff --git a/crates/ide/src/prime_caches.rs b/crates/ide/src/prime_caches.rs
index 5eba1d1e27..41e48c4ba5 100644
--- a/crates/ide/src/prime_caches.rs
+++ b/crates/ide/src/prime_caches.rs
@@ -4,7 +4,7 @@
 //! various caches, it's not really advanced at the moment.
 
 use hir::db::DefDatabase;
-use ide_db::base_db::{SourceDatabase, SourceDatabaseExt};
+use ide_db::base_db::{CrateGraph, CrateId, SourceDatabase, SourceDatabaseExt};
 use rustc_hash::FxHashSet;
 
 use crate::RootDatabase;
@@ -20,10 +20,7 @@ pub struct PrimeCachesProgress {
 pub(crate) fn prime_caches(db: &RootDatabase, cb: &(dyn Fn(PrimeCachesProgress) + Sync)) {
     let _p = profile::span("prime_caches");
     let graph = db.crate_graph();
-    // We're only interested in the workspace crates and the `ImportMap`s of their direct
-    // dependencies, though in practice the latter also compute the `DefMap`s.
-    // We don't prime transitive dependencies because they're generally not visible in
-    // the current workspace.
+    // We're only interested in the transitive dependencies of all workspace crates.
     let to_prime: FxHashSet<_> = graph
         .iter()
         .filter(|&id| {
@@ -31,18 +28,32 @@ pub(crate) fn prime_caches(db: &RootDatabase, cb: &(dyn Fn(PrimeCachesProgress)
             let root_id = db.file_source_root(file_id);
             !db.source_root(root_id).is_library
         })
-        .flat_map(|id| graph[id].dependencies.iter().map(|krate| krate.crate_id))
+        .flat_map(|id| graph.transitive_deps(id))
         .collect();
 
+    let topo = toposort(&graph, &to_prime);
+
     // FIXME: This would be easy to parallelize, since it's in the ideal ordering for that.
     // Unfortunately rayon prevents panics from propagation out of a `scope`, which breaks
     // cancellation, so we cannot use rayon.
-    let n_total = to_prime.len();
-    for (n_done, &crate_id) in to_prime.iter().enumerate() {
+    for (i, &crate_id) in topo.iter().enumerate() {
         let crate_name = graph[crate_id].display_name.as_deref().unwrap_or_default().to_string();
 
-        cb(PrimeCachesProgress { on_crate: crate_name, n_done, n_total });
-        // This also computes the DefMap
+        cb(PrimeCachesProgress { on_crate: crate_name, n_done: i, n_total: topo.len() });
+        db.crate_def_map(crate_id);
         db.import_map(crate_id);
     }
 }
+
+fn toposort(graph: &CrateGraph, crates: &FxHashSet<CrateId>) -> Vec<CrateId> {
+    // Just subset the full topologically sorted set for simplicity.
+
+    let all = graph.crates_in_topological_order();
+    let mut result = Vec::with_capacity(crates.len());
+    for krate in all {
+        if crates.contains(&krate) {
+            result.push(krate);
+        }
+    }
+    result
+}
diff --git a/crates/ide_assists/src/handlers/replace_derive_with_manual_impl.rs b/crates/ide_assists/src/handlers/replace_derive_with_manual_impl.rs
index 3e33c62144..46bf4d7b46 100644
--- a/crates/ide_assists/src/handlers/replace_derive_with_manual_impl.rs
+++ b/crates/ide_assists/src/handlers/replace_derive_with_manual_impl.rs
@@ -65,7 +65,7 @@ pub(crate) fn replace_derive_with_manual_impl(
     let found_traits = items_locator::items_with_name(
         &ctx.sema,
         current_crate,
-        NameToImport::Exact(trait_path.segments().last()?.to_string()),
+        NameToImport::exact_case_sensitive(trait_path.segments().last()?.to_string()),
         items_locator::AssocItemSearch::Exclude,
         Some(items_locator::DEFAULT_QUERY_SEARCH_LIMIT.inner()),
     )
diff --git a/crates/ide_assists/src/utils/suggest_name.rs b/crates/ide_assists/src/utils/suggest_name.rs
index 2021db3aba..74523234b0 100644
--- a/crates/ide_assists/src/utils/suggest_name.rs
+++ b/crates/ide_assists/src/utils/suggest_name.rs
@@ -243,7 +243,7 @@ fn name_of_type(ty: &hir::Type, db: &RootDatabase) -> Option<String> {
     } else if let Some(trait_) = ty.as_dyn_trait() {
         trait_name(&trait_, db)?
     } else if let Some(traits) = ty.as_impl_traits(db) {
-        let mut iter = traits.filter_map(|t| trait_name(&t, db));
+        let mut iter = traits.into_iter().filter_map(|t| trait_name(&t, db));
         let name = iter.next()?;
         if iter.next().is_some() {
             return None;
diff --git a/crates/ide_completion/src/completions/flyimport.rs b/crates/ide_completion/src/completions/flyimport.rs
index 3a9c1b3beb..8994c25475 100644
--- a/crates/ide_completion/src/completions/flyimport.rs
+++ b/crates/ide_completion/src/completions/flyimport.rs
@@ -227,22 +227,18 @@ fn import_assets(ctx: &CompletionContext, fuzzy_name: String) -> Option<ImportAs
         )
     } else {
         let fuzzy_name_length = fuzzy_name.len();
-        let assets_for_path = ImportAssets::for_fuzzy_path(
+        let mut assets_for_path = ImportAssets::for_fuzzy_path(
             current_module,
             ctx.path_qual().cloned(),
             fuzzy_name,
             &ctx.sema,
             ctx.token.parent()?,
         )?;
-
-        if matches!(assets_for_path.import_candidate(), ImportCandidate::Path(_))
-            && fuzzy_name_length < 2
-        {
-            cov_mark::hit!(ignore_short_input_for_path);
-            None
-        } else {
-            Some(assets_for_path)
+        if fuzzy_name_length < 3 {
+            cov_mark::hit!(flyimport_exact_on_short_path);
+            assets_for_path.path_fuzzy_name_to_exact(false);
         }
+        Some(assets_for_path)
     }
 }
 
diff --git a/crates/ide_completion/src/completions/pattern.rs b/crates/ide_completion/src/completions/pattern.rs
index b3b27f251f..0476590142 100644
--- a/crates/ide_completion/src/completions/pattern.rs
+++ b/crates/ide_completion/src/completions/pattern.rs
@@ -1,7 +1,5 @@
 //! Completes constants and paths in unqualified patterns.
 
-use hir::db::DefDatabase;
-
 use crate::{
     context::{PatternContext, PatternRefutability},
     CompletionContext, Completions,
@@ -15,12 +13,11 @@ pub(crate) fn complete_pattern(acc: &mut Completions, ctx: &CompletionContext) {
         }
         _ => return,
     };
-    let single_variant_enum = |enum_: hir::Enum| ctx.db.enum_data(enum_.into()).variants.len() == 1;
 
-    if let Some(hir::Adt::Enum(e)) =
-        ctx.expected_type.as_ref().and_then(|ty| ty.strip_references().as_adt())
-    {
-        if refutable || single_variant_enum(e) {
+    if refutable {
+        if let Some(hir::Adt::Enum(e)) =
+            ctx.expected_type.as_ref().and_then(|ty| ty.strip_references().as_adt())
+        {
             super::enum_variants_with_paths(acc, ctx, e, |acc, ctx, variant, path| {
                 acc.add_qualified_variant_pat(ctx, variant, path.clone());
                 acc.add_qualified_enum_variant(ctx, variant, path);
@@ -31,20 +28,20 @@ pub(crate) fn complete_pattern(acc: &mut Completions, ctx: &CompletionContext) {
     // FIXME: ideally, we should look at the type we are matching against and
     // suggest variants + auto-imports
     ctx.process_all_names(&mut |name, res| {
-        let add_resolution = match res {
+        let add_resolution = match &res {
             hir::ScopeDef::ModuleDef(def) => match def {
                 hir::ModuleDef::Adt(hir::Adt::Struct(strukt)) => {
-                    acc.add_struct_pat(ctx, strukt, Some(name.clone()));
+                    acc.add_struct_pat(ctx, *strukt, Some(name.clone()));
                     true
                 }
-                hir::ModuleDef::Variant(variant)
-                    if refutable || single_variant_enum(variant.parent_enum(ctx.db)) =>
-                {
-                    acc.add_variant_pat(ctx, variant, Some(name.clone()));
+                hir::ModuleDef::Variant(variant) if refutable => {
+                    acc.add_variant_pat(ctx, *variant, Some(name.clone()));
                     true
                 }
-                hir::ModuleDef::Adt(hir::Adt::Enum(e)) => refutable || single_variant_enum(e),
-                hir::ModuleDef::Const(..) | hir::ModuleDef::Module(..) => refutable,
+                hir::ModuleDef::Adt(hir::Adt::Enum(..))
+                | hir::ModuleDef::Variant(..)
+                | hir::ModuleDef::Const(..)
+                | hir::ModuleDef::Module(..) => refutable,
                 _ => false,
             },
             hir::ScopeDef::MacroDef(mac) => mac.is_fn_like(),
diff --git a/crates/ide_completion/src/lib.rs b/crates/ide_completion/src/lib.rs
index d9618642c4..6a087edc4f 100644
--- a/crates/ide_completion/src/lib.rs
+++ b/crates/ide_completion/src/lib.rs
@@ -195,7 +195,7 @@ pub fn resolve_completion_edits(
         let items_with_name = items_locator::items_with_name(
             &ctx.sema,
             current_crate,
-            NameToImport::Exact(imported_name),
+            NameToImport::exact_case_sensitive(imported_name),
             items_locator::AssocItemSearch::Include,
             Some(items_locator::DEFAULT_QUERY_SEARCH_LIMIT.inner()),
         );
diff --git a/crates/ide_db/src/helpers/import_assets.rs b/crates/ide_db/src/helpers/import_assets.rs
index ac0ccfa63f..024e0c9f81 100644
--- a/crates/ide_db/src/helpers/import_assets.rs
+++ b/crates/ide_db/src/helpers/import_assets.rs
@@ -68,17 +68,23 @@ pub struct FirstSegmentUnresolved {
 /// A name that will be used during item lookups.
 #[derive(Debug, Clone)]
 pub enum NameToImport {
-    /// Requires items with names that exactly match the given string, case-sensitive.
-    Exact(String),
+    /// Requires items with names that exactly match the given string, bool indicatse case-sensitivity.
+    Exact(String, bool),
     /// Requires items with names that case-insensitively contain all letters from the string,
     /// in the same order, but not necessary adjacent.
     Fuzzy(String),
 }
 
+impl NameToImport {
+    pub fn exact_case_sensitive(s: String) -> NameToImport {
+        NameToImport::Exact(s, true)
+    }
+}
+
 impl NameToImport {
     pub fn text(&self) -> &str {
         match self {
-            NameToImport::Exact(text) => text.as_str(),
+            NameToImport::Exact(text, _) => text.as_str(),
             NameToImport::Fuzzy(text) => text.as_str(),
         }
     }
@@ -140,7 +146,7 @@ impl ImportAssets {
         if let Some(_) = path.qualifier() {
             return None;
         }
-        let name = NameToImport::Exact(path.segment()?.name_ref()?.to_string());
+        let name = NameToImport::exact_case_sensitive(path.segment()?.name_ref()?.to_string());
         let candidate_node = attr.syntax().clone();
         Some(Self {
             import_candidate: ImportCandidate::Path(PathImportCandidate { qualifier: None, name }),
@@ -230,6 +236,18 @@ impl ImportAssets {
         self.search_for(sema, None)
     }
 
+    pub fn path_fuzzy_name_to_exact(&mut self, case_sensitive: bool) {
+        if let ImportCandidate::Path(PathImportCandidate { name: to_import, .. }) =
+            &mut self.import_candidate
+        {
+            let name = match to_import {
+                NameToImport::Fuzzy(name) => std::mem::take(name),
+                _ => return,
+            };
+            *to_import = NameToImport::Exact(name, case_sensitive);
+        }
+    }
+
     fn search_for(
         &self,
         sema: &Semantics<RootDatabase>,
@@ -454,10 +472,8 @@ fn trait_applicable_items(
 
     let db = sema.db;
 
-    let inherent_traits = trait_candidate.receiver_ty.applicable_inherent_traits(db);
-    let env_traits = trait_candidate.receiver_ty.env_traits(db);
-    let related_traits = inherent_traits.chain(env_traits).collect::<FxHashSet<_>>();
-
+    let related_dyn_traits =
+        trait_candidate.receiver_ty.applicable_inherent_traits(db).collect::<FxHashSet<_>>();
     let mut required_assoc_items = FxHashSet::default();
     let trait_candidates = items_locator::items_with_name(
         sema,
@@ -469,7 +485,7 @@ fn trait_applicable_items(
     .filter_map(|input| item_as_assoc(db, input))
     .filter_map(|assoc| {
         let assoc_item_trait = assoc.containing_trait(db)?;
-        if related_traits.contains(&assoc_item_trait) {
+        if related_dyn_traits.contains(&assoc_item_trait) {
             None
         } else {
             required_assoc_items.insert(assoc);
@@ -563,7 +579,9 @@ impl ImportCandidate {
             Some(_) => None,
             None => Some(Self::TraitMethod(TraitImportCandidate {
                 receiver_ty: sema.type_of_expr(&method_call.receiver()?)?.adjusted(),
-                assoc_item_name: NameToImport::Exact(method_call.name_ref()?.to_string()),
+                assoc_item_name: NameToImport::exact_case_sensitive(
+                    method_call.name_ref()?.to_string(),
+                ),
             })),
         }
     }
@@ -575,7 +593,7 @@ impl ImportCandidate {
         path_import_candidate(
             sema,
             path.qualifier(),
-            NameToImport::Exact(path.segment()?.name_ref()?.to_string()),
+            NameToImport::exact_case_sensitive(path.segment()?.name_ref()?.to_string()),
         )
     }
 
@@ -589,7 +607,7 @@ impl ImportCandidate {
         }
         Some(ImportCandidate::Path(PathImportCandidate {
             qualifier: None,
-            name: NameToImport::Exact(name.to_string()),
+            name: NameToImport::exact_case_sensitive(name.to_string()),
         }))
     }
 
diff --git a/crates/ide_db/src/items_locator.rs b/crates/ide_db/src/items_locator.rs
index e0dbe6caf0..ca8266b6d2 100644
--- a/crates/ide_db/src/items_locator.rs
+++ b/crates/ide_db/src/items_locator.rs
@@ -50,16 +50,18 @@ pub fn items_with_name<'a>(
     });
 
     let (mut local_query, mut external_query) = match name {
-        NameToImport::Exact(exact_name) => {
+        NameToImport::Exact(exact_name, case_sensitive) => {
             let mut local_query = symbol_index::Query::new(exact_name.clone());
             local_query.exact();
 
             let external_query = import_map::Query::new(exact_name)
                 .name_only()
-                .search_mode(import_map::SearchMode::Equals)
-                .case_sensitive();
+                .search_mode(import_map::SearchMode::Equals);
 
-            (local_query, external_query)
+            (
+                local_query,
+                if case_sensitive { external_query.case_sensitive() } else { external_query },
+            )
         }
         NameToImport::Fuzzy(fuzzy_search_string) => {
             let mut local_query = symbol_index::Query::new(fuzzy_search_string.clone());
diff --git a/crates/stdx/src/lib.rs b/crates/stdx/src/lib.rs
index e33b45cc8e..ee23f57934 100644
--- a/crates/stdx/src/lib.rs
+++ b/crates/stdx/src/lib.rs
@@ -193,11 +193,6 @@ where
     }
 }
 
-/// Returns all final segments of the argument, longest first.
-pub fn slice_tails<T>(this: &[T]) -> impl Iterator<Item = &[T]> {
-    (0..this.len()).map(|i| &this[i..])
-}
-
 #[cfg(test)]
 mod tests {
     use super::*;


Test patch:
diff --git a/crates/hir_def/src/macro_expansion_tests/builtin_fn_macro.rs b/crates/hir_def/src/macro_expansion_tests/builtin_fn_macro.rs
index 6e91301ecd..06039e95c5 100644
--- a/crates/hir_def/src/macro_expansion_tests/builtin_fn_macro.rs
+++ b/crates/hir_def/src/macro_expansion_tests/builtin_fn_macro.rs
@@ -313,40 +313,6 @@ fn main() { "foor0bar\nfalse"; }
     );
 }
 
-#[test]
-fn test_concat_with_captured_expr() {
-    check(
-        r##"
-#[rustc_builtin_macro]
-macro_rules! concat {}
-
-macro_rules! surprise {
-    () => { "s" };
-}
-
-macro_rules! stuff {
-    ($string:expr) => { concat!($string) };
-}
-
-fn main() { concat!(surprise!()); }
-"##,
-        expect![[r##"
-#[rustc_builtin_macro]
-macro_rules! concat {}
-
-macro_rules! surprise {
-    () => { "s" };
-}
-
-macro_rules! stuff {
-    ($string:expr) => { concat!($string) };
-}
-
-fn main() { "s"; }
-"##]],
-    );
-}
-
 #[test]
 fn test_concat_idents_expand() {
     check(
diff --git a/crates/ide_completion/src/tests/flyimport.rs b/crates/ide_completion/src/tests/flyimport.rs
index 1f96e122f9..f40df62ece 100644
--- a/crates/ide_completion/src/tests/flyimport.rs
+++ b/crates/ide_completion/src/tests/flyimport.rs
@@ -96,25 +96,29 @@ fn main() {
 
 #[test]
 fn short_paths_are_ignored() {
-    cov_mark::check!(ignore_short_input_for_path);
+    cov_mark::check!(flyimport_exact_on_short_path);
 
     check(
         r#"
 //- /lib.rs crate:dep
-pub struct FirstStruct;
+pub struct Bar;
+pub struct Rcar;
+pub struct Rc;
 pub mod some_module {
-    pub struct SecondStruct;
-    pub struct ThirdStruct;
+    pub struct Bar;
+    pub struct Rcar;
+    pub struct Rc;
 }
 
 //- /main.rs crate:main deps:dep
-use dep::{FirstStruct, some_module::SecondStruct};
-
 fn main() {
-    t$0
+    rc$0
 }
 "#,
-        expect![[r#""#]],
+        expect![[r#"
+            st Rc (use dep::Rc)
+            st Rc (use dep::some_module::Rc)
+        "#]],
     );
 }
 
@@ -772,7 +776,7 @@ mod foo {
 }
 
 fn main() {
-    TE$0
+    TES$0
 }"#,
         expect![[r#"
         ct TEST_CONST (use foo::TEST_CONST)
@@ -789,7 +793,7 @@ mod foo {
 }
 
 fn main() {
-    te$0
+    tes$0
 }"#,
         expect![[r#"
         ct TEST_CONST (use foo::TEST_CONST)
@@ -846,7 +850,7 @@ struct Foo {
     some_field: i32,
 }
 fn main() {
-    let _ = Foo { some_field: so$0 };
+    let _ = Foo { some_field: som$0 };
 }
 "#,
         expect![[r#"
@@ -924,44 +928,6 @@ mod bar {
             "#,
         expect![[r#""#]],
     );
-    check(
-        r#"
-mod baz {
-    pub trait DefDatabase {
-        fn method1(&self);
-    }
-    pub trait HirDatabase: DefDatabase {
-        fn method2(&self);
-    }
-}
-
-mod bar {
-    fn test(db: &impl crate::baz::HirDatabase) {
-        db.metho$0
-    }
-}
-"#,
-        expect![[r#""#]],
-    );
-    check(
-        r#"
-mod baz {
-    pub trait DefDatabase {
-        fn method1(&self);
-    }
-    pub trait HirDatabase: DefDatabase {
-        fn method2(&self);
-    }
-}
-
-mod bar {
-    fn test<T: crate::baz::HirDatabase>(db: T) {
-        db.metho$0
-    }
-}
-"#,
-        expect![[r#""#]],
-    );
 }
 
 #[test]
diff --git a/crates/ide_completion/src/tests/pattern.rs b/crates/ide_completion/src/tests/pattern.rs
index 99e20b6ed0..81c45c64cc 100644
--- a/crates/ide_completion/src/tests/pattern.rs
+++ b/crates/ide_completion/src/tests/pattern.rs
@@ -130,24 +130,18 @@ fn foo() {
 fn irrefutable() {
     check(
         r#"
-enum SingleVariantEnum {
-    Variant
-}
-use SingleVariantEnum::Variant;
 fn foo() {
    let a$0
 }
 "#,
         expect![[r##"
             kw mut
-            bn Record            Record { field$1 }$0
+            bn Record    Record { field$1 }$0
             st Record
-            bn Tuple             Tuple($1)$0
+            bn Tuple     Tuple($1)$0
             st Tuple
-            ev Variant
-            en SingleVariantEnum
             st Unit
-            ma makro!(…)         #[macro_export] macro_rules! makro
+            ma makro!(…) #[macro_export] macro_rules! makro
         "##]],
     );
 }