Merge #2396

2396: Switch to variant-granularity field type inference r=flodiebold a=matklad

r? @flodiebold 

Previously, we had a `ty` query for each field. This PR switcthes to a query per struct, which returns an `ArenaMap` with `Ty`s. 

I don't know which approach is better. What is bugging me about the original approach is that, if we do all queries on the "leaf" defs, in practice we get a ton of queries which repeatedly reach into the parent definition to compute module, resolver, etc. This *seems* wasteful (but I don't think this is really what causes any perf problems for us). 

At the same time, I've been looking at Kotlin, and they seem to use the general pattern of analyzing the *parent* definition, and storing info about children into a `BindingContext`. 

I don't really which way is preferable. I think I want to try this approach, where query granularity generally mirrors the data granularity. The primary motivation for me here is probably just hope that we can avoid adding a ton of helpers to a `StructField`, and maybe in general avoid the need to switch to a global `StructField`, using `LocalStructFieldId` most of the time internally. 

For external API (ie, for `ra_ide_api`), I think we should continue with fine-grained `StructField::ty` approach, which internally fetches the table for the whole struct and indexes into it.

In terms of actual memory savings, the results are as follows:

```
This PR:
   142kb FieldTypesQuery (deps)
    38kb FieldTypesQuery

Status Quo:
   208kb TypeForFieldQuery (deps)
    18kb TypeForFieldQuery
```

Note how the table itself occupies more than twice as much space! I don't have an explanation for this: a plausible hypothesis is that single-field structs are very common and for them the table is a pessimisation. 

THere's noticiable wallclock time difference.

Co-authored-by: Aleksey Kladov <[email protected]>

10 files changed, 68 insertions, 42 deletions

diff --git a/crates/ra_arena/src/lib.rs b/crates/ra_arena/src/lib.rs
index 984e1eec3..fc0f7c12f 100644
--- a/crates/ra_arena/src/lib.rs
+++ b/crates/ra_arena/src/lib.rs
@@ -85,7 +85,7 @@ impl<ID: ArenaId, T> Arena<ID, T> {
         self.data.push(value);
         ID::from_raw(id)
     }
-    pub fn iter(&self) -> impl Iterator<Item = (ID, &T)> + ExactSizeIterator {
+    pub fn iter(&self) -> impl Iterator<Item = (ID, &T)> + ExactSizeIterator + DoubleEndedIterator {
         self.data.iter().enumerate().map(|(idx, value)| (ID::from_raw(RawId(idx as u32)), value))
     }
 }
diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index ab0544a4c..3f44a50c4 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -305,7 +305,7 @@ impl StructField {
     }
 
     pub fn ty(&self, db: &impl HirDatabase) -> Ty {
-        db.type_for_field(*self)
+        db.field_types(self.parent.into())[self.id].clone()
     }
 
     pub fn parent_def(&self, _db: &impl HirDatabase) -> VariantDef {
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index a9dab2d25..5084bbacf 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -2,6 +2,7 @@
 
 use std::sync::Arc;
 
+use ra_arena::map::ArenaMap;
 use ra_db::salsa;
 
 use crate::{
@@ -11,15 +12,19 @@ use crate::{
         CallableDef, FnSig, GenericPredicate, InferenceResult, Namespace, Substs, Ty, TypableDef,
         TypeCtor,
     },
-    Crate, DefWithBody, GenericDef, ImplBlock, StructField, Trait,
+    Crate, DefWithBody, GenericDef, ImplBlock, Trait,
 };
 
-pub use hir_def::db::{
-    BodyQuery, BodyWithSourceMapQuery, ConstDataQuery, CrateDefMapQuery, CrateLangItemsQuery,
-    DefDatabase, DefDatabaseStorage, DocumentationQuery, EnumDataQuery, ExprScopesQuery,
-    FunctionDataQuery, GenericParamsQuery, ImplDataQuery, InternDatabase, InternDatabaseStorage,
-    LangItemQuery, ModuleLangItemsQuery, RawItemsQuery, RawItemsWithSourceMapQuery,
-    StaticDataQuery, StructDataQuery, TraitDataQuery, TypeAliasDataQuery,
+pub use hir_def::{
+    db::{
+        BodyQuery, BodyWithSourceMapQuery, ConstDataQuery, CrateDefMapQuery, CrateLangItemsQuery,
+        DefDatabase, DefDatabaseStorage, DocumentationQuery, EnumDataQuery, ExprScopesQuery,
+        FunctionDataQuery, GenericParamsQuery, ImplDataQuery, InternDatabase,
+        InternDatabaseStorage, LangItemQuery, ModuleLangItemsQuery, RawItemsQuery,
+        RawItemsWithSourceMapQuery, StaticDataQuery, StructDataQuery, TraitDataQuery,
+        TypeAliasDataQuery,
+    },
+    LocalStructFieldId, VariantId,
 };
 pub use hir_expand::db::{
     AstDatabase, AstDatabaseStorage, AstIdMapQuery, MacroArgQuery, MacroDefQuery, MacroExpandQuery,
@@ -35,8 +40,8 @@ pub trait HirDatabase: DefDatabase {
     #[salsa::invoke(crate::ty::type_for_def)]
     fn type_for_def(&self, def: TypableDef, ns: Namespace) -> Ty;
 
-    #[salsa::invoke(crate::ty::type_for_field)]
-    fn type_for_field(&self, field: StructField) -> Ty;
+    #[salsa::invoke(crate::ty::field_types_query)]
+    fn field_types(&self, var: VariantId) -> Arc<ArenaMap<LocalStructFieldId, Ty>>;
 
     #[salsa::invoke(crate::ty::callable_item_sig)]
     fn callable_item_signature(&self, def: CallableDef) -> FnSig;
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 309bd2727..f62316c1f 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -30,8 +30,9 @@ pub(crate) use autoderef::autoderef;
 pub(crate) use infer::{infer_query, InferTy, InferenceResult};
 pub use lower::CallableDef;
 pub(crate) use lower::{
-    callable_item_sig, generic_defaults_query, generic_predicates_for_param_query,
-    generic_predicates_query, type_for_def, type_for_field, Namespace, TypableDef,
+    callable_item_sig, field_types_query, generic_defaults_query,
+    generic_predicates_for_param_query, generic_predicates_query, type_for_def, Namespace,
+    TypableDef,
 };
 pub(crate) use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment};
 
diff --git a/crates/ra_hir/src/ty/infer/coerce.rs b/crates/ra_hir/src/ty/infer/coerce.rs
index 4ea038d99..54765da35 100644
--- a/crates/ra_hir/src/ty/infer/coerce.rs
+++ b/crates/ra_hir/src/ty/infer/coerce.rs
@@ -245,14 +245,17 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 ty_app!(TypeCtor::Adt(Adt::Struct(struct1)), st1),
                 ty_app!(TypeCtor::Adt(Adt::Struct(struct2)), st2),
             ) if struct1 == struct2 => {
-                let fields = struct1.fields(self.db);
-                let (last_field, prev_fields) = fields.split_last()?;
+                let field_tys = self.db.field_types(struct1.id.into());
+                let struct_data = self.db.struct_data(struct1.id.0);
+
+                let mut fields = struct_data.variant_data.fields().iter();
+                let (last_field_id, _data) = fields.next_back()?;
 
                 // Get the generic parameter involved in the last field.
                 let unsize_generic_index = {
                     let mut index = None;
                     let mut multiple_param = false;
-                    last_field.ty(self.db).walk(&mut |ty| match ty {
+                    field_tys[last_field_id].walk(&mut |ty| match ty {
                         &Ty::Param { idx, .. } => {
                             if index.is_none() {
                                 index = Some(idx);
@@ -271,8 +274,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
 
                 // Check other fields do not involve it.
                 let mut multiple_used = false;
-                prev_fields.iter().for_each(|field| {
-                    field.ty(self.db).walk(&mut |ty| match ty {
+                fields.for_each(|(field_id, _data)| {
+                    field_tys[field_id].walk(&mut |ty| match ty {
                         &Ty::Param { idx, .. } if idx == unsize_generic_index => {
                             multiple_used = true
                         }
diff --git a/crates/ra_hir/src/ty/infer/expr.rs b/crates/ra_hir/src/ty/infer/expr.rs
index 2996920c6..663ff9435 100644
--- a/crates/ra_hir/src/ty/infer/expr.rs
+++ b/crates/ra_hir/src/ty/infer/expr.rs
@@ -214,6 +214,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 self.unify(&ty, &expected.ty);
 
                 let substs = ty.substs().unwrap_or_else(Substs::empty);
+                let field_types =
+                    def_id.map(|it| self.db.field_types(it.into())).unwrap_or_default();
                 for (field_idx, field) in fields.iter().enumerate() {
                     let field_def = def_id.and_then(|it| match it.field(self.db, &field.name) {
                         Some(field) => Some(field),
@@ -228,8 +230,9 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                     if let Some(field_def) = field_def {
                         self.result.record_field_resolutions.insert(field.expr, field_def);
                     }
-                    let field_ty =
-                        field_def.map_or(Ty::Unknown, |field| field.ty(self.db)).subst(&substs);
+                    let field_ty = field_def
+                        .map_or(Ty::Unknown, |it| field_types[it.id].clone())
+                        .subst(&substs);
                     self.infer_expr_coerce(field.expr, &Expectation::has_type(field_ty));
                 }
                 if let Some(expr) = spread {
@@ -252,7 +255,9 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                             .and_then(|idx| a_ty.parameters.0.get(idx).cloned()),
                         TypeCtor::Adt(Adt::Struct(s)) => s.field(self.db, name).map(|field| {
                             self.write_field_resolution(tgt_expr, field);
-                            field.ty(self.db).subst(&a_ty.parameters)
+                            self.db.field_types(s.id.into())[field.id]
+                                .clone()
+                                .subst(&a_ty.parameters)
                         }),
                         _ => None,
                     },
diff --git a/crates/ra_hir/src/ty/infer/pat.rs b/crates/ra_hir/src/ty/infer/pat.rs
index c125ddfbc..641d61e87 100644
--- a/crates/ra_hir/src/ty/infer/pat.rs
+++ b/crates/ra_hir/src/ty/infer/pat.rs
@@ -27,10 +27,11 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
 
         let substs = ty.substs().unwrap_or_else(Substs::empty);
 
+        let field_tys = def.map(|it| self.db.field_types(it.into())).unwrap_or_default();
         for (i, &subpat) in subpats.iter().enumerate() {
             let expected_ty = def
                 .and_then(|d| d.field(self.db, &Name::new_tuple_field(i)))
-                .map_or(Ty::Unknown, |field| field.ty(self.db))
+                .map_or(Ty::Unknown, |field| field_tys[field.id].clone())
                 .subst(&substs);
             let expected_ty = self.normalize_associated_types_in(expected_ty);
             self.infer_pat(subpat, &expected_ty, default_bm);
@@ -56,10 +57,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
 
         let substs = ty.substs().unwrap_or_else(Substs::empty);
 
+        let field_tys = def.map(|it| self.db.field_types(it.into())).unwrap_or_default();
         for subpat in subpats {
             let matching_field = def.and_then(|it| it.field(self.db, &subpat.name));
-            let expected_ty =
-                matching_field.map_or(Ty::Unknown, |field| field.ty(self.db)).subst(&substs);
+            let expected_ty = matching_field
+                .map_or(Ty::Unknown, |field| field_tys[field.id].clone())
+                .subst(&substs);
             let expected_ty = self.normalize_associated_types_in(expected_ty);
             self.infer_pat(subpat.pat, &expected_ty, default_bm);
         }
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 2b40cb07d..a39beb2a0 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -14,8 +14,9 @@ use hir_def::{
     path::{GenericArg, PathSegment},
     resolver::{HasResolver, Resolver, TypeNs},
     type_ref::{TypeBound, TypeRef},
-    AdtId, GenericDefId,
+    AdtId, GenericDefId, LocalStructFieldId, VariantId,
 };
+use ra_arena::map::ArenaMap;
 
 use super::{
     FnSig, GenericPredicate, ProjectionPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor,
@@ -29,7 +30,7 @@ use crate::{
     },
     util::make_mut_slice,
     Const, Enum, EnumVariant, Function, GenericDef, ImplBlock, ModuleDef, Path, Static, Struct,
-    StructField, Trait, TypeAlias, Union, VariantDef,
+    Trait, TypeAlias, Union,
 };
 
 // FIXME: this is only really used in `type_for_def`, which contains a bunch of
@@ -549,16 +550,23 @@ pub(crate) fn callable_item_sig(db: &impl HirDatabase, def: CallableDef) -> FnSi
     }
 }
 
-/// Build the type of a specific field of a struct or enum variant.
-pub(crate) fn type_for_field(db: &impl HirDatabase, field: StructField) -> Ty {
-    let parent_def = field.parent_def(db);
-    let resolver = match parent_def {
-        VariantDef::Struct(it) => it.id.resolver(db),
-        VariantDef::EnumVariant(it) => it.parent.id.resolver(db),
+/// Build the type of all specific fields of a struct or enum variant.
+pub(crate) fn field_types_query(
+    db: &impl HirDatabase,
+    variant_id: VariantId,
+) -> Arc<ArenaMap<LocalStructFieldId, Ty>> {
+    let (resolver, var_data) = match variant_id {
+        VariantId::StructId(it) => (it.resolver(db), db.struct_data(it.0).variant_data.clone()),
+        VariantId::EnumVariantId(it) => (
+            it.parent.resolver(db),
+            db.enum_data(it.parent).variants[it.local_id].variant_data.clone(),
+        ),
     };
-    let var_data = parent_def.variant_data(db);
-    let type_ref = &var_data.fields()[field.id].type_ref;
-    Ty::from_hir(db, &resolver, type_ref)
+    let mut res = ArenaMap::default();
+    for (field_id, field_data) in var_data.fields().iter() {
+        res.insert(field_id, Ty::from_hir(db, &resolver, &field_data.type_ref))
+    }
+    Arc::new(res)
 }
 
 /// This query exists only to be used when resolving short-hand associated types
diff --git a/crates/ra_hir_def/src/lib.rs b/crates/ra_hir_def/src/lib.rs
index 5bc9ffc0d..8e8c2d749 100644
--- a/crates/ra_hir_def/src/lib.rs
+++ b/crates/ra_hir_def/src/lib.rs
@@ -192,12 +192,6 @@ pub struct LocalEnumVariantId(RawId);
 impl_arena_id!(LocalEnumVariantId);
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
-pub enum VariantId {
-    EnumVariantId(EnumVariantId),
-    StructId(StructId),
-}
-
-#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct StructFieldId {
     pub parent: VariantId,
     pub local_id: LocalStructFieldId,
@@ -437,6 +431,13 @@ impl_froms!(
     ImplId
 );
 
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub enum VariantId {
+    EnumVariantId(EnumVariantId),
+    StructId(StructId),
+}
+impl_froms!(VariantId: EnumVariantId, StructId);
+
 trait Intern {
     type ID;
     fn intern(self, db: &impl db::DefDatabase) -> Self::ID;
diff --git a/crates/ra_ide_api/src/change.rs b/crates/ra_ide_api/src/change.rs
index 8a05b287f..0f692460d 100644
--- a/crates/ra_ide_api/src/change.rs
+++ b/crates/ra_ide_api/src/change.rs
@@ -324,7 +324,7 @@ impl RootDatabase {
             hir::db::ExprScopesQuery
             hir::db::InferQuery
             hir::db::TypeForDefQuery
-            hir::db::TypeForFieldQuery
+            hir::db::FieldTypesQuery
             hir::db::CallableItemSignatureQuery
             hir::db::GenericPredicatesQuery
             hir::db::GenericDefaultsQuery