fix: Don't rely on lang items to find primitive impls

rustc has removed the use of lang items to mark the primitive impls, so
just look through the crate graph for them (this should be fine
performance-wise since we cache the crates that contain these impls).

Fixes #11876.

3 files changed, 92 insertions, 90 deletions

diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs
index 467dcfa33ea..de4c1535902 100644
--- a/crates/hir_ty/src/db.rs
+++ b/crates/hir_ty/src/db.rs
@@ -3,6 +3,7 @@
 
 use std::sync::Arc;
 
+use arrayvec::ArrayVec;
 use base_db::{impl_intern_key, salsa, CrateId, Upcast};
 use hir_def::{
     db::DefDatabase, expr::ExprId, BlockId, ConstId, ConstParamId, DefWithBodyId, FunctionId,
@@ -13,7 +14,7 @@ use la_arena::ArenaMap;
 use crate::{
     chalk_db,
     consteval::{ComputedExpr, ConstEvalError},
-    method_resolution::{InherentImpls, TraitImpls},
+    method_resolution::{InherentImpls, TraitImpls, TyFingerprint},
     Binders, CallableDefId, FnDefId, GenericArg, ImplTraitId, InferenceResult, Interner, PolyFnSig,
     QuantifiedWhereClause, ReturnTypeImplTraits, TraitRef, Ty, TyDefId, ValueTyDefId,
 };
@@ -86,6 +87,12 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
     #[salsa::invoke(InherentImpls::inherent_impls_in_block_query)]
     fn inherent_impls_in_block(&self, block: BlockId) -> Option<Arc<InherentImpls>>;
 
+    /// Collects all crates in the dependency graph that have impls for the
+    /// given fingerprint. This is only used for primitive types; for
+    /// user-defined types we just look at the crate where the type is defined.
+    #[salsa::invoke(crate::method_resolution::inherent_impl_crates_query)]
+    fn inherent_impl_crates(&self, krate: CrateId, fp: TyFingerprint) -> ArrayVec<CrateId, 2>;
+
     #[salsa::invoke(TraitImpls::trait_impls_in_crate_query)]
     fn trait_impls_in_crate(&self, krate: CrateId) -> Arc<TraitImpls>;
 
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index 768772d5c34..d5285c17106 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -8,9 +8,8 @@ use arrayvec::ArrayVec;
 use base_db::{CrateId, Edition};
 use chalk_ir::{cast::Cast, Mutability, UniverseIndex};
 use hir_def::{
-    item_scope::ItemScope, lang_item::LangItemTarget, nameres::DefMap, AssocItemId, BlockId,
-    ConstId, FunctionId, GenericDefId, HasModule, ImplId, ItemContainerId, Lookup, ModuleDefId,
-    ModuleId, TraitId,
+    item_scope::ItemScope, nameres::DefMap, AssocItemId, BlockId, ConstId, FunctionId,
+    GenericDefId, HasModule, ImplId, ItemContainerId, Lookup, ModuleDefId, ModuleId, TraitId,
 };
 use hir_expand::name::Name;
 use rustc_hash::{FxHashMap, FxHashSet};
@@ -21,7 +20,7 @@ use crate::{
     db::HirDatabase,
     from_foreign_def_id,
     infer::{unify::InferenceTable, Adjust, Adjustment, AutoBorrow, OverloadedDeref, PointerCast},
-    primitive::{self, FloatTy, IntTy, UintTy},
+    primitive::{FloatTy, IntTy, UintTy},
     static_lifetime,
     utils::all_super_traits,
     AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, ForeignDefId, InEnvironment, Interner,
@@ -337,6 +336,30 @@ impl InherentImpls {
     }
 }
 
+pub fn inherent_impl_crates_query(
+    db: &dyn HirDatabase,
+    krate: CrateId,
+    fp: TyFingerprint,
+) -> ArrayVec<CrateId, 2> {
+    let _p = profile::span("inherent_impl_crates_query");
+    let mut res = ArrayVec::new();
+    let crate_graph = db.crate_graph();
+
+    for krate in crate_graph.transitive_deps(krate) {
+        if res.is_full() {
+            // we don't currently look for or store more than two crates here,
+            // so don't needlessly look at more crates than necessary.
+            break;
+        }
+        let impls = db.inherent_impls_in_crate(krate);
+        if impls.map.get(&fp).map_or(false, |v| !v.is_empty()) {
+            res.push(krate);
+        }
+    }
+
+    res
+}
+
 fn collect_unnamed_consts<'a>(
     db: &'a dyn HirDatabase,
     scope: &'a ItemScope,
@@ -370,63 +393,30 @@ pub fn def_crates(
     ty: &Ty,
     cur_crate: CrateId,
 ) -> Option<ArrayVec<CrateId, 2>> {
-    // Types like slice can have inherent impls in several crates, (core and alloc).
-    // The corresponding impls are marked with lang items, so we can use them to find the required crates.
-    macro_rules! lang_item_crate {
-            ($($name:expr),+ $(,)?) => {{
-                let mut v = ArrayVec::<LangItemTarget, 2>::new();
-                $(
-                    v.extend(db.lang_item(cur_crate, $name.into()));
-                )+
-                v
-            }};
-        }
-
     let mod_to_crate_ids = |module: ModuleId| Some(iter::once(module.krate()).collect());
 
-    let lang_item_targets = match ty.kind(Interner) {
-        TyKind::Adt(AdtId(def_id), _) => {
-            return mod_to_crate_ids(def_id.module(db.upcast()));
-        }
+    let fp = TyFingerprint::for_inherent_impl(ty);
+
+    match ty.kind(Interner) {
+        TyKind::Adt(AdtId(def_id), _) => mod_to_crate_ids(def_id.module(db.upcast())),
         TyKind::Foreign(id) => {
-            return mod_to_crate_ids(
-                from_foreign_def_id(*id).lookup(db.upcast()).module(db.upcast()),
-            );
-        }
-        TyKind::Scalar(Scalar::Bool) => lang_item_crate!("bool"),
-        TyKind::Scalar(Scalar::Char) => lang_item_crate!("char"),
-        TyKind::Scalar(Scalar::Float(f)) => match f {
-            // There are two lang items: one in libcore (fXX) and one in libstd (fXX_runtime)
-            FloatTy::F32 => lang_item_crate!("f32", "f32_runtime"),
-            FloatTy::F64 => lang_item_crate!("f64", "f64_runtime"),
-        },
-        &TyKind::Scalar(Scalar::Int(t)) => {
-            lang_item_crate!(primitive::int_ty_to_string(t))
+            mod_to_crate_ids(from_foreign_def_id(*id).lookup(db.upcast()).module(db.upcast()))
         }
-        &TyKind::Scalar(Scalar::Uint(t)) => {
-            lang_item_crate!(primitive::uint_ty_to_string(t))
-        }
-        TyKind::Str => lang_item_crate!("str_alloc", "str"),
-        TyKind::Slice(_) => lang_item_crate!("slice_alloc", "slice"),
-        TyKind::Array(..) => lang_item_crate!("array"),
-        TyKind::Raw(Mutability::Not, _) => lang_item_crate!("const_ptr"),
-        TyKind::Raw(Mutability::Mut, _) => lang_item_crate!("mut_ptr"),
-        TyKind::Dyn(_) => {
-            return ty.dyn_trait().and_then(|trait_| {
-                mod_to_crate_ids(GenericDefId::TraitId(trait_).module(db.upcast()))
-            });
+        TyKind::Dyn(_) => ty
+            .dyn_trait()
+            .and_then(|trait_| mod_to_crate_ids(GenericDefId::TraitId(trait_).module(db.upcast()))),
+        // for primitives, there may be impls in various places (core and alloc
+        // mostly). We just check the whole crate graph for crates with impls
+        // (cached behind a query).
+        TyKind::Scalar(_)
+        | TyKind::Str
+        | TyKind::Slice(_)
+        | TyKind::Array(..)
+        | TyKind::Raw(..) => {
+            Some(db.inherent_impl_crates(cur_crate, fp.expect("fingerprint for primitive")))
         }
         _ => return None,
-    };
-    let res = lang_item_targets
-        .into_iter()
-        .filter_map(|it| match it {
-            LangItemTarget::ImplDefId(it) => Some(it),
-            _ => None,
-        })
-        .map(|it| it.lookup(db.upcast()).container.krate())
-        .collect();
-    Some(res)
+    }
 }
 
 /// Look up the method with the given name.
diff --git a/crates/hir_ty/src/tests/method_resolution.rs b/crates/hir_ty/src/tests/method_resolution.rs
index 011347e5c45..d97147541ad 100644
--- a/crates/hir_ty/src/tests/method_resolution.rs
+++ b/crates/hir_ty/src/tests/method_resolution.rs
@@ -6,33 +6,39 @@ use super::{check_infer, check_no_mismatches, check_types};
 
 #[test]
 fn infer_slice_method() {
-    check_infer(
+    check_types(
         r#"
-        #[lang = "slice"]
-        impl<T> [T] {
-            fn foo(&self) -> T {
-                loop {}
-            }
-        }
-
-        #[lang = "slice_alloc"]
-        impl<T> [T] {}
+impl<T> [T] {
+    fn foo(&self) -> T {
+        loop {}
+    }
+}
 
-        fn test(x: &[u8]) {
-            <[_]>::foo(x);
-        }
+fn test(x: &[u8]) {
+    <[_]>::foo(x);
+  //^^^^^^^^^^^^^ u8
+}
         "#,
-        expect![[r#"
-            44..48 'self': &[T]
-            55..78 '{     ...     }': T
-            65..72 'loop {}': !
-            70..72 '{}': ()
-            130..131 'x': &[u8]
-            140..162 '{     ...(x); }': ()
-            146..156 '<[_]>::foo': fn foo<u8>(&[u8]) -> u8
-            146..159 '<[_]>::foo(x)': u8
-            157..158 'x': &[u8]
-        "#]],
+    );
+}
+
+#[test]
+fn cross_crate_primitive_method() {
+    check_types(
+        r#"
+//- /main.rs crate:main deps:other_crate
+fn test() {
+    let x = 1f32;
+    x.foo();
+} //^^^^^^^ f32
+
+//- /lib.rs crate:other_crate
+mod foo {
+    impl f32 {
+        pub fn foo(self) -> f32 { 0. }
+    }
+}
+"#,
     );
 }
 
@@ -40,16 +46,15 @@ fn infer_slice_method() {
 fn infer_array_inherent_impl() {
     check_types(
         r#"
-        #[lang = "array"]
-        impl<T, const N: usize> [T; N] {
-            fn foo(&self) -> T {
-                loop {}
-            }
-        }
-        fn test(x: &[u8; 0]) {
-            <[_; 0]>::foo(x);
-          //^^^^^^^^^^^^^^^^ u8
-        }
+impl<T, const N: usize> [T; N] {
+    fn foo(&self) -> T {
+        loop {}
+    }
+}
+fn test(x: &[u8; 0]) {
+    <[_; 0]>::foo(x);
+  //^^^^^^^^^^^^^^^^ u8
+}
         "#,
     );
 }