Auto merge of #127718 - cjgillot:find_field, r=compiler-errors

find_field does not need to be a query.

The current implementation is quadratic in the number of nested fields.

r? `@davidtwco` as you reviewed https://github.com/rust-lang/rust/pull/115367
Fixes https://github.com/rust-lang/rust/issues/121755

4 files changed, 73 insertions, 55 deletions

diff --git a/compiler/rustc_hir_analysis/src/collect.rs b/compiler/rustc_hir_analysis/src/collect.rs
index 0acc119115a..e0aad299163 100644
--- a/compiler/rustc_hir_analysis/src/collect.rs
+++ b/compiler/rustc_hir_analysis/src/collect.rs
@@ -35,7 +35,6 @@ use rustc_middle::ty::{self, AdtKind, Const, IsSuggestable, Ty, TyCtxt, Upcast};
 use rustc_middle::{bug, span_bug};
 use rustc_span::symbol::{kw, sym, Ident, Symbol};
 use rustc_span::{Span, DUMMY_SP};
-use rustc_target::abi::FieldIdx;
 use rustc_target::spec::abi;
 use rustc_trait_selection::error_reporting::traits::suggestions::NextTypeParamName;
 use rustc_trait_selection::infer::InferCtxtExt;
@@ -85,7 +84,6 @@ pub fn provide(providers: &mut Providers) {
         coroutine_kind,
         coroutine_for_closure,
         is_type_alias_impl_trait,
-        find_field,
         ..*providers
     };
 }
@@ -914,23 +912,6 @@ fn lower_enum_variant_types(tcx: TyCtxt<'_>, def_id: DefId) {
     }
 }
 
-fn find_field(tcx: TyCtxt<'_>, (def_id, ident): (DefId, Ident)) -> Option<FieldIdx> {
-    let adt = tcx.adt_def(def_id);
-    if adt.is_enum() {
-        return None;
-    }
-
-    adt.non_enum_variant().fields.iter_enumerated().find_map(|(idx, field)| {
-        if field.is_unnamed() {
-            let field_ty = tcx.type_of(field.did).instantiate_identity();
-            let adt_def = field_ty.ty_adt_def().expect("expect Adt for unnamed field");
-            tcx.find_field((adt_def.did(), ident)).map(|_| idx)
-        } else {
-            (field.ident(tcx).normalize_to_macros_2_0() == ident).then_some(idx)
-        }
-    })
-}
-
 #[derive(Clone, Copy)]
 struct NestedSpan {
     span: Span,
diff --git a/compiler/rustc_hir_typeck/src/expr.rs b/compiler/rustc_hir_typeck/src/expr.rs
index f057dbc013f..035a3429ed7 100644
--- a/compiler/rustc_hir_typeck/src/expr.rs
+++ b/compiler/rustc_hir_typeck/src/expr.rs
@@ -59,6 +59,8 @@ use rustc_trait_selection::infer::InferCtxtExt;
 use rustc_trait_selection::traits::ObligationCtxt;
 use rustc_trait_selection::traits::{self, ObligationCauseCode};
 
+use smallvec::SmallVec;
+
 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     pub fn check_expr_has_type_or_error(
         &self,
@@ -2318,6 +2320,44 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         display
     }
 
+    /// Find the position of a field named `ident` in `base_def`, accounting for unnammed fields.
+    /// Return whether such a field has been found. The path to it is stored in `nested_fields`.
+    /// `ident` must have been adjusted beforehand.
+    fn find_adt_field(
+        &self,
+        base_def: ty::AdtDef<'tcx>,
+        ident: Ident,
+        nested_fields: &mut SmallVec<[(FieldIdx, &'tcx ty::FieldDef); 1]>,
+    ) -> bool {
+        // No way to find a field in an enum.
+        if base_def.is_enum() {
+            return false;
+        }
+
+        for (field_idx, field) in base_def.non_enum_variant().fields.iter_enumerated() {
+            if field.is_unnamed() {
+                // We have an unnamed field, recurse into the nested ADT to find `ident`.
+                // If we find it there, return immediately, and `nested_fields` will contain the
+                // correct path.
+                nested_fields.push((field_idx, field));
+
+                let field_ty = self.tcx.type_of(field.did).instantiate_identity();
+                let adt_def = field_ty.ty_adt_def().expect("expect Adt for unnamed field");
+                if self.find_adt_field(adt_def, ident, &mut *nested_fields) {
+                    return true;
+                }
+
+                nested_fields.pop();
+            } else if field.ident(self.tcx).normalize_to_macros_2_0() == ident {
+                // We found the field we wanted.
+                nested_fields.push((field_idx, field));
+                return true;
+            }
+        }
+
+        false
+    }
+
     // Check field access expressions
     fn check_field(
         &self,
@@ -2339,44 +2379,44 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                     let body_hir_id = self.tcx.local_def_id_to_hir_id(self.body_id);
                     let (ident, def_scope) =
                         self.tcx.adjust_ident_and_get_scope(field, base_def.did(), body_hir_id);
-                    let mut adt_def = *base_def;
-                    let mut last_ty = None;
-                    let mut nested_fields = Vec::new();
-                    let mut index = None;
 
                     // we don't care to report errors for a struct if the struct itself is tainted
-                    if let Err(guar) = adt_def.non_enum_variant().has_errors() {
+                    if let Err(guar) = base_def.non_enum_variant().has_errors() {
                         return Ty::new_error(self.tcx(), guar);
                     }
-                    while let Some(idx) = self.tcx.find_field((adt_def.did(), ident)) {
-                        let &mut first_idx = index.get_or_insert(idx);
-                        let field = &adt_def.non_enum_variant().fields[idx];
-                        let field_ty = self.field_ty(expr.span, field, args);
-                        if let Some(ty) = last_ty {
-                            nested_fields.push((ty, idx));
-                        }
-                        if field.ident(self.tcx).normalize_to_macros_2_0() == ident {
-                            // Save the index of all fields regardless of their visibility in case
-                            // of error recovery.
-                            self.write_field_index(expr.hir_id, first_idx, nested_fields);
-                            let adjustments = self.adjust_steps(&autoderef);
-                            if field.vis.is_accessible_from(def_scope, self.tcx) {
-                                self.apply_adjustments(base, adjustments);
-                                self.register_predicates(autoderef.into_obligations());
 
-                                self.tcx.check_stability(
-                                    field.did,
-                                    Some(expr.hir_id),
-                                    expr.span,
-                                    None,
-                                );
-                                return field_ty;
-                            }
-                            private_candidate = Some((adjustments, base_def.did()));
-                            break;
+                    let mut field_path = SmallVec::new();
+                    if self.find_adt_field(*base_def, ident, &mut field_path) {
+                        let (first_idx, _) = field_path[0];
+                        let (_, last_field) = field_path.last().unwrap();
+
+                        // Save the index of all fields regardless of their visibility in case
+                        // of error recovery.
+                        let nested_fields = field_path[..]
+                            .array_windows()
+                            .map(|[(_, outer), (inner_idx, _)]| {
+                                let outer_ty = self.field_ty(expr.span, outer, args);
+                                (outer_ty, *inner_idx)
+                            })
+                            .collect();
+                        self.write_field_index(expr.hir_id, first_idx, nested_fields);
+
+                        let adjustments = self.adjust_steps(&autoderef);
+                        if last_field.vis.is_accessible_from(def_scope, self.tcx) {
+                            self.apply_adjustments(base, adjustments);
+                            self.register_predicates(autoderef.into_obligations());
+
+                            self.tcx.check_stability(
+                                last_field.did,
+                                Some(expr.hir_id),
+                                expr.span,
+                                None,
+                            );
+                            return self.field_ty(expr.span, last_field, args);
                         }
-                        last_ty = Some(field_ty);
-                        adt_def = field_ty.ty_adt_def().expect("expect Adt for unnamed field");
+
+                        // The field is not accessible, fall through to error reporting.
+                        private_candidate = Some((adjustments, base_def.did()));
                     }
                 }
                 ty::Tuple(tys) => {
diff --git a/compiler/rustc_hir_typeck/src/lib.rs b/compiler/rustc_hir_typeck/src/lib.rs
index a87ee7b4554..bdbdcee6446 100644
--- a/compiler/rustc_hir_typeck/src/lib.rs
+++ b/compiler/rustc_hir_typeck/src/lib.rs
@@ -1,6 +1,7 @@
 // tidy-alphabetical-start
 #![allow(rustc::diagnostic_outside_of_impl)]
 #![allow(rustc::untranslatable_diagnostic)]
+#![feature(array_windows)]
 #![feature(box_patterns)]
 #![feature(control_flow_enum)]
 #![feature(if_let_guard)]
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index 33c27d41d86..817c7157b68 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -2280,10 +2280,6 @@ rustc_queries! {
         desc { "whether the item should be made inlinable across crates" }
         separate_provide_extern
     }
-
-    query find_field((def_id, ident): (DefId, rustc_span::symbol::Ident)) -> Option<rustc_target::abi::FieldIdx> {
-        desc { |tcx| "find the index of maybe nested field `{ident}` in `{}`", tcx.def_path_str(def_id) }
-    }
 }
 
 rustc_query_append! { define_callbacks! }