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

hir_ty/
autoderef.rs
