hir_ty/
autoderef.rs

1//! In certain situations, rust automatically inserts derefs as necessary: for
2//! example, field accesses `foo.bar` still work when `foo` is actually a
3//! reference to a type with the field `bar`. This is an approximation of the
4//! logic in rustc (which lives in rustc_hir_analysis/check/autoderef.rs).
5
6use std::fmt;
7
8use hir_def::{TraitId, TypeAliasId};
9use rustc_type_ir::inherent::{IntoKind, Ty as _};
10use tracing::debug;
11
12use crate::{
13    ParamEnvAndCrate,
14    db::HirDatabase,
15    infer::InferenceContext,
16    next_solver::{
17        Canonical, DbInterner, ParamEnv, TraitRef, Ty, TyKind, TypingMode,
18        infer::{
19            DbInternerInferExt, InferCtxt,
20            traits::{Obligation, ObligationCause, PredicateObligations},
21        },
22        obligation_ctxt::ObligationCtxt,
23    },
24};
25
26const AUTODEREF_RECURSION_LIMIT: usize = 20;
27
28/// Returns types that `ty` transitively dereferences to. This function is only meant to be used
29/// outside `hir-ty`.
30///
31/// It is guaranteed that:
32/// - the yielded types don't contain inference variables (but may contain `TyKind::Error`).
33/// - a type won't be yielded more than once; in other words, the returned iterator will stop if it
34///   detects a cycle in the deref chain.
35pub fn autoderef<'db>(
36    db: &'db dyn HirDatabase,
37    env: ParamEnvAndCrate<'db>,
38    ty: Canonical<'db, Ty<'db>>,
39) -> impl Iterator<Item = Ty<'db>> + use<'db> {
40    let interner = DbInterner::new_with(db, env.krate);
41    let infcx = interner.infer_ctxt().build(TypingMode::PostAnalysis);
42    let (ty, _) = infcx.instantiate_canonical(&ty);
43    let autoderef = Autoderef::new(&infcx, env.param_env, ty);
44    let mut v = Vec::new();
45    for (ty, _steps) in autoderef {
46        // `ty` may contain unresolved inference variables. Since there's no chance they would be
47        // resolved, just replace with fallback type.
48        let resolved = infcx.resolve_vars_if_possible(ty).replace_infer_with_error(interner);
49
50        // If the deref chain contains a cycle (e.g. `A` derefs to `B` and `B` derefs to `A`), we
51        // would revisit some already visited types. Stop here to avoid duplication.
52        //
53        // XXX: The recursion limit for `Autoderef` is currently 20, so `Vec::contains()` shouldn't
54        // be too expensive. Replace this duplicate check with `FxHashSet` if it proves to be more
55        // performant.
56        if v.contains(&resolved) {
57            break;
58        }
59        v.push(resolved);
60    }
61    v.into_iter()
62}
63
64pub(crate) trait TrackAutoderefSteps<'db>: Default + fmt::Debug {
65    fn len(&self) -> usize;
66    fn push(&mut self, ty: Ty<'db>, kind: AutoderefKind);
67}
68
69impl<'db> TrackAutoderefSteps<'db> for usize {
70    fn len(&self) -> usize {
71        *self
72    }
73    fn push(&mut self, _: Ty<'db>, _: AutoderefKind) {
74        *self += 1;
75    }
76}
77impl<'db> TrackAutoderefSteps<'db> for Vec<(Ty<'db>, AutoderefKind)> {
78    fn len(&self) -> usize {
79        self.len()
80    }
81    fn push(&mut self, ty: Ty<'db>, kind: AutoderefKind) {
82        self.push((ty, kind));
83    }
84}
85
86#[derive(Copy, Clone, Debug)]
87pub(crate) enum AutoderefKind {
88    /// A true pointer type, such as `&T` and `*mut T`.
89    Builtin,
90    /// A type which must dispatch to a `Deref` implementation.
91    Overloaded,
92}
93
94struct AutoderefSnapshot<'db, Steps> {
95    at_start: bool,
96    reached_recursion_limit: bool,
97    steps: Steps,
98    cur_ty: Ty<'db>,
99    obligations: PredicateObligations<'db>,
100}
101
102#[derive(Clone, Copy)]
103struct AutoderefTraits {
104    trait_: TraitId,
105    trait_target: TypeAliasId,
106}
107
108// We use a trait here and a generic implementation unfortunately, because sometimes (specifically
109// in place_op.rs), you need to have mutable access to the `InferenceContext` while the `Autoderef`
110// borrows it.
111pub(crate) trait AutoderefCtx<'db> {
112    fn infcx(&self) -> &InferCtxt<'db>;
113    fn param_env(&self) -> ParamEnv<'db>;
114}
115
116pub(crate) struct DefaultAutoderefCtx<'a, 'db> {
117    infcx: &'a InferCtxt<'db>,
118    param_env: ParamEnv<'db>,
119}
120impl<'db> AutoderefCtx<'db> for DefaultAutoderefCtx<'_, 'db> {
121    #[inline]
122    fn infcx(&self) -> &InferCtxt<'db> {
123        self.infcx
124    }
125    #[inline]
126    fn param_env(&self) -> ParamEnv<'db> {
127        self.param_env
128    }
129}
130
131pub(crate) struct InferenceContextAutoderefCtx<'a, 'b, 'db>(&'a mut InferenceContext<'b, 'db>);
132impl<'db> AutoderefCtx<'db> for InferenceContextAutoderefCtx<'_, '_, 'db> {
133    #[inline]
134    fn infcx(&self) -> &InferCtxt<'db> {
135        &self.0.table.infer_ctxt
136    }
137    #[inline]
138    fn param_env(&self) -> ParamEnv<'db> {
139        self.0.table.param_env
140    }
141}
142
143/// Recursively dereference a type, considering both built-in
144/// dereferences (`*`) and the `Deref` trait.
145/// Although called `Autoderef` it can be configured to use the
146/// `Receiver` trait instead of the `Deref` trait.
147pub(crate) struct GeneralAutoderef<'db, Ctx, Steps = Vec<(Ty<'db>, AutoderefKind)>> {
148    // Meta infos:
149    ctx: Ctx,
150    traits: Option<AutoderefTraits>,
151
152    // Current state:
153    state: AutoderefSnapshot<'db, Steps>,
154
155    // Configurations:
156    include_raw_pointers: bool,
157    use_receiver_trait: bool,
158}
159
160pub(crate) type Autoderef<'a, 'db, Steps = Vec<(Ty<'db>, AutoderefKind)>> =
161    GeneralAutoderef<'db, DefaultAutoderefCtx<'a, 'db>, Steps>;
162pub(crate) type InferenceContextAutoderef<'a, 'b, 'db, Steps = Vec<(Ty<'db>, AutoderefKind)>> =
163    GeneralAutoderef<'db, InferenceContextAutoderefCtx<'a, 'b, 'db>, Steps>;
164
165impl<'db, Ctx, Steps> Iterator for GeneralAutoderef<'db, Ctx, Steps>
166where
167    Ctx: AutoderefCtx<'db>,
168    Steps: TrackAutoderefSteps<'db>,
169{
170    type Item = (Ty<'db>, usize);
171
172    fn next(&mut self) -> Option<Self::Item> {
173        debug!("autoderef: steps={:?}, cur_ty={:?}", self.state.steps, self.state.cur_ty);
174        if self.state.at_start {
175            self.state.at_start = false;
176            debug!("autoderef stage #0 is {:?}", self.state.cur_ty);
177            return Some((self.state.cur_ty, 0));
178        }
179
180        // If we have reached the recursion limit, error gracefully.
181        if self.state.steps.len() >= AUTODEREF_RECURSION_LIMIT {
182            self.state.reached_recursion_limit = true;
183            return None;
184        }
185
186        if self.state.cur_ty.is_ty_var() {
187            return None;
188        }
189
190        // Otherwise, deref if type is derefable:
191        // NOTE: in the case of self.use_receiver_trait = true, you might think it would
192        // be better to skip this clause and use the Overloaded case only, since &T
193        // and &mut T implement Receiver. But built-in derefs apply equally to Receiver
194        // and Deref, and this has benefits for const and the emitted MIR.
195        let (kind, new_ty) =
196            if let Some(ty) = self.state.cur_ty.builtin_deref(self.include_raw_pointers) {
197                debug_assert_eq!(ty, self.infcx().resolve_vars_if_possible(ty));
198                // NOTE: we may still need to normalize the built-in deref in case
199                // we have some type like `&<Ty as Trait>::Assoc`, since users of
200                // autoderef expect this type to have been structurally normalized.
201                if let TyKind::Alias(..) = ty.kind() {
202                    let (normalized_ty, obligations) =
203                        structurally_normalize_ty(self.infcx(), self.param_env(), ty)?;
204                    self.state.obligations.extend(obligations);
205                    (AutoderefKind::Builtin, normalized_ty)
206                } else {
207                    (AutoderefKind::Builtin, ty)
208                }
209            } else if let Some(ty) = self.overloaded_deref_ty(self.state.cur_ty) {
210                // The overloaded deref check already normalizes the pointee type.
211                (AutoderefKind::Overloaded, ty)
212            } else {
213                return None;
214            };
215
216        self.state.steps.push(self.state.cur_ty, kind);
217        debug!(
218            "autoderef stage #{:?} is {:?} from {:?}",
219            self.step_count(),
220            new_ty,
221            (self.state.cur_ty, kind)
222        );
223        self.state.cur_ty = new_ty;
224
225        Some((self.state.cur_ty, self.step_count()))
226    }
227}
228
229impl<'a, 'db> Autoderef<'a, 'db> {
230    #[inline]
231    pub(crate) fn new_with_tracking(
232        infcx: &'a InferCtxt<'db>,
233        param_env: ParamEnv<'db>,
234        base_ty: Ty<'db>,
235    ) -> Self {
236        Self::new_impl(DefaultAutoderefCtx { infcx, param_env }, base_ty)
237    }
238}
239
240impl<'a, 'b, 'db> InferenceContextAutoderef<'a, 'b, 'db> {
241    #[inline]
242    pub(crate) fn new_from_inference_context(
243        ctx: &'a mut InferenceContext<'b, 'db>,
244        base_ty: Ty<'db>,
245    ) -> Self {
246        Self::new_impl(InferenceContextAutoderefCtx(ctx), base_ty)
247    }
248
249    #[inline]
250    pub(crate) fn ctx(&mut self) -> &mut InferenceContext<'b, 'db> {
251        self.ctx.0
252    }
253}
254
255impl<'a, 'db> Autoderef<'a, 'db, usize> {
256    #[inline]
257    pub(crate) fn new(
258        infcx: &'a InferCtxt<'db>,
259        param_env: ParamEnv<'db>,
260        base_ty: Ty<'db>,
261    ) -> Self {
262        Self::new_impl(DefaultAutoderefCtx { infcx, param_env }, base_ty)
263    }
264}
265
266impl<'db, Ctx, Steps> GeneralAutoderef<'db, Ctx, Steps>
267where
268    Ctx: AutoderefCtx<'db>,
269    Steps: TrackAutoderefSteps<'db>,
270{
271    #[inline]
272    fn new_impl(ctx: Ctx, base_ty: Ty<'db>) -> Self {
273        GeneralAutoderef {
274            state: AutoderefSnapshot {
275                steps: Steps::default(),
276                cur_ty: ctx.infcx().resolve_vars_if_possible(base_ty),
277                obligations: PredicateObligations::new(),
278                at_start: true,
279                reached_recursion_limit: false,
280            },
281            ctx,
282            traits: None,
283            include_raw_pointers: false,
284            use_receiver_trait: false,
285        }
286    }
287
288    #[inline]
289    fn infcx(&self) -> &InferCtxt<'db> {
290        self.ctx.infcx()
291    }
292
293    #[inline]
294    fn param_env(&self) -> ParamEnv<'db> {
295        self.ctx.param_env()
296    }
297
298    #[inline]
299    fn interner(&self) -> DbInterner<'db> {
300        self.infcx().interner
301    }
302
303    fn autoderef_traits(&mut self) -> Option<AutoderefTraits> {
304        let lang_items = self.interner().lang_items();
305        match &mut self.traits {
306            Some(it) => Some(*it),
307            None => {
308                let traits = if self.use_receiver_trait {
309                    (|| {
310                        Some(AutoderefTraits {
311                            trait_: lang_items.Receiver?,
312                            trait_target: lang_items.ReceiverTarget?,
313                        })
314                    })()
315                    .or_else(|| {
316                        Some(AutoderefTraits {
317                            trait_: lang_items.Deref?,
318                            trait_target: lang_items.DerefTarget?,
319                        })
320                    })?
321                } else {
322                    AutoderefTraits {
323                        trait_: lang_items.Deref?,
324                        trait_target: lang_items.DerefTarget?,
325                    }
326                };
327                Some(*self.traits.insert(traits))
328            }
329        }
330    }
331
332    fn overloaded_deref_ty(&mut self, ty: Ty<'db>) -> Option<Ty<'db>> {
333        debug!("overloaded_deref_ty({:?})", ty);
334        let interner = self.interner();
335
336        // <ty as Deref>, or whatever the equivalent trait is that we've been asked to walk.
337        let AutoderefTraits { trait_, trait_target } = self.autoderef_traits()?;
338
339        let trait_ref = TraitRef::new(interner, trait_.into(), [ty]);
340        let obligation =
341            Obligation::new(interner, ObligationCause::new(), self.param_env(), trait_ref);
342        // We detect whether the self type implements `Deref` before trying to
343        // structurally normalize. We use `predicate_may_hold_opaque_types_jank`
344        // to support not-yet-defined opaque types. It will succeed for `impl Deref`
345        // but fail for `impl OtherTrait`.
346        if !self.infcx().predicate_may_hold_opaque_types_jank(&obligation) {
347            debug!("overloaded_deref_ty: cannot match obligation");
348            return None;
349        }
350
351        let (normalized_ty, obligations) = structurally_normalize_ty(
352            self.infcx(),
353            self.param_env(),
354            Ty::new_projection(interner, trait_target.into(), [ty]),
355        )?;
356        debug!("overloaded_deref_ty({:?}) = ({:?}, {:?})", ty, normalized_ty, obligations);
357        self.state.obligations.extend(obligations);
358
359        Some(self.infcx().resolve_vars_if_possible(normalized_ty))
360    }
361
362    /// Returns the final type we ended up with, which may be an unresolved
363    /// inference variable.
364    pub(crate) fn final_ty(&self) -> Ty<'db> {
365        self.state.cur_ty
366    }
367
368    pub(crate) fn step_count(&self) -> usize {
369        self.state.steps.len()
370    }
371
372    pub(crate) fn take_obligations(&mut self) -> PredicateObligations<'db> {
373        std::mem::take(&mut self.state.obligations)
374    }
375
376    pub(crate) fn steps(&self) -> &Steps {
377        &self.state.steps
378    }
379
380    pub(crate) fn reached_recursion_limit(&self) -> bool {
381        self.state.reached_recursion_limit
382    }
383
384    /// also dereference through raw pointer types
385    /// e.g., assuming ptr_to_Foo is the type `*const Foo`
386    /// fcx.autoderef(span, ptr_to_Foo)  => [*const Foo]
387    /// fcx.autoderef(span, ptr_to_Foo).include_raw_ptrs() => [*const Foo, Foo]
388    pub(crate) fn include_raw_pointers(mut self) -> Self {
389        self.include_raw_pointers = true;
390        self
391    }
392
393    /// Use `core::ops::Receiver` and `core::ops::Receiver::Target` as
394    /// the trait and associated type to iterate, instead of
395    /// `core::ops::Deref` and `core::ops::Deref::Target`
396    pub(crate) fn use_receiver_trait(mut self) -> Self {
397        self.use_receiver_trait = true;
398        self
399    }
400}
401
402fn structurally_normalize_ty<'db>(
403    infcx: &InferCtxt<'db>,
404    param_env: ParamEnv<'db>,
405    ty: Ty<'db>,
406) -> Option<(Ty<'db>, PredicateObligations<'db>)> {
407    let mut ocx = ObligationCtxt::new(infcx);
408    let Ok(normalized_ty) = ocx.structurally_normalize_ty(&ObligationCause::misc(), param_env, ty)
409    else {
410        // We shouldn't have errors here in the old solver, except for
411        // evaluate/fulfill mismatches, but that's not a reason for an ICE.
412        return None;
413    };
414    let errors = ocx.try_evaluate_obligations();
415    if !errors.is_empty() {
416        unreachable!();
417    }
418
419    Some((normalized_ty, ocx.into_pending_obligations()))
420}
hir_ty/autoderef.rs

hir_ty/
autoderef.rs
