hir_ty/next_solver/
util.rs

1//! Various utilities for the next-trait-solver.
2
3use std::ops::ControlFlow;
4
5use hir_def::{HasModule, ImplId, TraitId, TypeAliasId};
6use rustc_abi::{Float, HasDataLayout, Integer, IntegerType, Primitive, ReprOptions};
7use rustc_hash::FxHashSet;
8use rustc_type_ir::{
9    ConstKind, CoroutineArgs, DebruijnIndex, FloatTy, INNERMOST, IntTy, Interner,
10    PredicatePolarity, RegionKind, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeSuperVisitable,
11    TypeVisitableExt, TypeVisitor, UintTy, UniverseIndex, Upcast,
12    elaborate::{self, elaborate},
13    inherent::{AdtDef, GenericArg as _, IntoKind, ParamEnv as _, SliceLike, Ty as _},
14    lang_items::SolverTraitLangItem,
15    solve::SizedTraitKind,
16};
17use stdx::impl_from;
18
19use crate::{
20    ImplTraitId,
21    db::{HirDatabase, InternedOpaqueTyId},
22    next_solver::{
23        BoundConst, Clauses, FxIndexMap, ParamEnv, PlaceholderConst, PlaceholderRegion,
24        PlaceholderType, PolyTraitRef, StoredClauses, StoredEarlyBinder,
25        infer::{
26            InferCtxt,
27            traits::{Obligation, ObligationCause, PredicateObligation},
28        },
29    },
30    representability::Representability,
31};
32
33use super::{
34    Binder, BoundRegion, BoundTy, Clause, ClauseKind, Const, DbInterner, EarlyBinder, GenericArgs,
35    Predicate, PredicateKind, Region, SolverDefId, Ty, TyKind,
36    fold::{BoundVarReplacer, FnMutDelegate},
37};
38
39#[derive(Clone, Debug)]
40pub struct Discr<'db> {
41    /// Bit representation of the discriminant (e.g., `-128i8` is `0xFF_u128`).
42    pub val: u128,
43    pub ty: Ty<'db>,
44}
45
46impl<'db> Discr<'db> {
47    /// Adds `1` to the value and wraps around if the maximum for the type is reached.
48    pub fn wrap_incr(self, interner: DbInterner<'db>) -> Self {
49        self.checked_add(interner, 1).0
50    }
51    pub fn checked_add(self, interner: DbInterner<'db>, n: u128) -> (Self, bool) {
52        let (size, signed) = self.ty.int_size_and_signed(interner);
53        let (val, oflo) = if signed {
54            let min = size.signed_int_min();
55            let max = size.signed_int_max();
56            let val = size.sign_extend(self.val);
57            assert!(n < (i128::MAX as u128));
58            let n = n as i128;
59            let oflo = val > max - n;
60            let val = if oflo { min + (n - (max - val) - 1) } else { val + n };
61            // zero the upper bits
62            let val = val as u128;
63            let val = size.truncate(val);
64            (val, oflo)
65        } else {
66            let max = size.unsigned_int_max();
67            let val = self.val;
68            let oflo = val > max - n;
69            let val = if oflo { n - (max - val) - 1 } else { val + n };
70            (val, oflo)
71        };
72        (Self { val, ty: self.ty }, oflo)
73    }
74}
75
76pub trait IntegerTypeExt {
77    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
78    fn initial_discriminant<'db>(&self, interner: DbInterner<'db>) -> Discr<'db>;
79    fn disr_incr<'db>(
80        &self,
81        interner: DbInterner<'db>,
82        val: Option<Discr<'db>>,
83    ) -> Option<Discr<'db>>;
84}
85
86impl IntegerTypeExt for IntegerType {
87    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
88        let types = interner.default_types();
89        match self {
90            IntegerType::Pointer(true) => types.types.isize,
91            IntegerType::Pointer(false) => types.types.usize,
92            IntegerType::Fixed(i, s) => i.to_ty(interner, *s),
93        }
94    }
95
96    fn initial_discriminant<'db>(&self, interner: DbInterner<'db>) -> Discr<'db> {
97        Discr { val: 0, ty: self.to_ty(interner) }
98    }
99
100    fn disr_incr<'db>(
101        &self,
102        interner: DbInterner<'db>,
103        val: Option<Discr<'db>>,
104    ) -> Option<Discr<'db>> {
105        if let Some(val) = val {
106            assert_eq!(self.to_ty(interner), val.ty);
107            let (new, oflo) = val.checked_add(interner, 1);
108            if oflo { None } else { Some(new) }
109        } else {
110            Some(self.initial_discriminant(interner))
111        }
112    }
113}
114
115pub trait IntegerExt {
116    fn to_ty<'db>(&self, interner: DbInterner<'db>, signed: bool) -> Ty<'db>;
117    fn from_int_ty<C: HasDataLayout>(cx: &C, ity: IntTy) -> Integer;
118    fn from_uint_ty<C: HasDataLayout>(cx: &C, ity: UintTy) -> Integer;
119    fn repr_discr<'db>(
120        interner: DbInterner<'db>,
121        ty: Ty<'db>,
122        repr: &ReprOptions,
123        min: i128,
124        max: i128,
125    ) -> (Integer, bool);
126}
127
128impl IntegerExt for Integer {
129    #[inline]
130    fn to_ty<'db>(&self, interner: DbInterner<'db>, signed: bool) -> Ty<'db> {
131        use Integer::*;
132        let types = interner.default_types();
133        match (*self, signed) {
134            (I8, false) => types.types.u8,
135            (I16, false) => types.types.u16,
136            (I32, false) => types.types.u32,
137            (I64, false) => types.types.u64,
138            (I128, false) => types.types.u128,
139            (I8, true) => types.types.i8,
140            (I16, true) => types.types.i16,
141            (I32, true) => types.types.i32,
142            (I64, true) => types.types.i64,
143            (I128, true) => types.types.i128,
144        }
145    }
146
147    fn from_int_ty<C: HasDataLayout>(cx: &C, ity: IntTy) -> Integer {
148        use Integer::*;
149        match ity {
150            IntTy::I8 => I8,
151            IntTy::I16 => I16,
152            IntTy::I32 => I32,
153            IntTy::I64 => I64,
154            IntTy::I128 => I128,
155            IntTy::Isize => cx.data_layout().ptr_sized_integer(),
156        }
157    }
158    fn from_uint_ty<C: HasDataLayout>(cx: &C, ity: UintTy) -> Integer {
159        use Integer::*;
160        match ity {
161            UintTy::U8 => I8,
162            UintTy::U16 => I16,
163            UintTy::U32 => I32,
164            UintTy::U64 => I64,
165            UintTy::U128 => I128,
166            UintTy::Usize => cx.data_layout().ptr_sized_integer(),
167        }
168    }
169
170    /// Finds the appropriate Integer type and signedness for the given
171    /// signed discriminant range and `#[repr]` attribute.
172    /// N.B.: `u128` values above `i128::MAX` will be treated as signed, but
173    /// that shouldn't affect anything, other than maybe debuginfo.
174    fn repr_discr<'db>(
175        interner: DbInterner<'db>,
176        ty: Ty<'db>,
177        repr: &ReprOptions,
178        min: i128,
179        max: i128,
180    ) -> (Integer, bool) {
181        // Theoretically, negative values could be larger in unsigned representation
182        // than the unsigned representation of the signed minimum. However, if there
183        // are any negative values, the only valid unsigned representation is u128
184        // which can fit all i128 values, so the result remains unaffected.
185        let unsigned_fit = Integer::fit_unsigned(std::cmp::max(min as u128, max as u128));
186        let signed_fit = std::cmp::max(Integer::fit_signed(min), Integer::fit_signed(max));
187
188        if let Some(ity) = repr.int {
189            let discr = Integer::from_attr(&interner, ity);
190            let fit = if ity.is_signed() { signed_fit } else { unsigned_fit };
191            if discr < fit {
192                panic!(
193                    "Integer::repr_discr: `#[repr]` hint too small for \
194                      discriminant range of enum `{ty:?}`"
195                )
196            }
197            return (discr, ity.is_signed());
198        }
199
200        let at_least = if repr.c() {
201            // This is usually I32, however it can be different on some platforms,
202            // notably hexagon and arm-none/thumb-none
203            interner.data_layout().c_enum_min_size
204        } else {
205            // repr(Rust) enums try to be as small as possible
206            Integer::I8
207        };
208
209        // If there are no negative values, we can use the unsigned fit.
210        if min >= 0 {
211            (std::cmp::max(unsigned_fit, at_least), false)
212        } else {
213            (std::cmp::max(signed_fit, at_least), true)
214        }
215    }
216}
217
218pub trait FloatExt {
219    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
220    fn from_float_ty(fty: FloatTy) -> Self;
221}
222
223impl FloatExt for Float {
224    #[inline]
225    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
226        use Float::*;
227        let types = interner.default_types();
228        match *self {
229            F16 => types.types.f16,
230            F32 => types.types.f32,
231            F64 => types.types.f64,
232            F128 => types.types.f128,
233        }
234    }
235
236    fn from_float_ty(fty: FloatTy) -> Self {
237        use Float::*;
238        match fty {
239            FloatTy::F16 => F16,
240            FloatTy::F32 => F32,
241            FloatTy::F64 => F64,
242            FloatTy::F128 => F128,
243        }
244    }
245}
246
247pub trait PrimitiveExt {
248    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
249    fn to_int_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
250}
251
252impl PrimitiveExt for Primitive {
253    #[inline]
254    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
255        match *self {
256            Primitive::Int(i, signed) => i.to_ty(interner, signed),
257            Primitive::Float(f) => f.to_ty(interner),
258            Primitive::Pointer(_) => interner.default_types().types.mut_unit_ptr,
259        }
260    }
261
262    /// Return an *integer* type matching this primitive.
263    /// Useful in particular when dealing with enum discriminants.
264    #[inline]
265    fn to_int_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
266        match *self {
267            Primitive::Int(i, signed) => i.to_ty(interner, signed),
268            Primitive::Pointer(_) => {
269                let signed = false;
270                interner.data_layout().ptr_sized_integer().to_ty(interner, signed)
271            }
272            Primitive::Float(_) => panic!("floats do not have an int type"),
273        }
274    }
275}
276
277impl<'db> HasDataLayout for DbInterner<'db> {
278    fn data_layout(&self) -> &rustc_abi::TargetDataLayout {
279        unimplemented!()
280    }
281}
282
283pub trait CoroutineArgsExt<'db> {
284    fn discr_ty(&self, interner: DbInterner<'db>) -> Ty<'db>;
285}
286
287impl<'db> CoroutineArgsExt<'db> for CoroutineArgs<DbInterner<'db>> {
288    /// The type of the state discriminant used in the coroutine type.
289    #[inline]
290    fn discr_ty(&self, interner: DbInterner<'db>) -> Ty<'db> {
291        interner.default_types().types.u32
292    }
293}
294
295/// Finds the max universe present
296pub struct MaxUniverse {
297    max_universe: UniverseIndex,
298}
299
300impl Default for MaxUniverse {
301    fn default() -> Self {
302        Self::new()
303    }
304}
305
306impl MaxUniverse {
307    pub fn new() -> Self {
308        MaxUniverse { max_universe: UniverseIndex::ROOT }
309    }
310
311    pub fn max_universe(self) -> UniverseIndex {
312        self.max_universe
313    }
314}
315
316impl<'db> TypeVisitor<DbInterner<'db>> for MaxUniverse {
317    type Result = ();
318
319    fn visit_ty(&mut self, t: Ty<'db>) {
320        if let TyKind::Placeholder(placeholder) = t.kind() {
321            self.max_universe = UniverseIndex::from_u32(
322                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
323            );
324        }
325
326        t.super_visit_with(self)
327    }
328
329    fn visit_const(&mut self, c: Const<'db>) {
330        if let ConstKind::Placeholder(placeholder) = c.kind() {
331            self.max_universe = UniverseIndex::from_u32(
332                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
333            );
334        }
335
336        c.super_visit_with(self)
337    }
338
339    fn visit_region(&mut self, r: Region<'db>) {
340        if let RegionKind::RePlaceholder(placeholder) = r.kind() {
341            self.max_universe = UniverseIndex::from_u32(
342                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
343            );
344        }
345    }
346}
347
348pub struct BottomUpFolder<'db, F, G, H>
349where
350    F: FnMut(Ty<'db>) -> Ty<'db>,
351    G: FnMut(Region<'db>) -> Region<'db>,
352    H: FnMut(Const<'db>) -> Const<'db>,
353{
354    pub interner: DbInterner<'db>,
355    pub ty_op: F,
356    pub lt_op: G,
357    pub ct_op: H,
358}
359
360impl<'db, F, G, H> TypeFolder<DbInterner<'db>> for BottomUpFolder<'db, F, G, H>
361where
362    F: FnMut(Ty<'db>) -> Ty<'db>,
363    G: FnMut(Region<'db>) -> Region<'db>,
364    H: FnMut(Const<'db>) -> Const<'db>,
365{
366    fn cx(&self) -> DbInterner<'db> {
367        self.interner
368    }
369
370    fn fold_ty(&mut self, ty: Ty<'db>) -> Ty<'db> {
371        let t = ty.super_fold_with(self);
372        (self.ty_op)(t)
373    }
374
375    fn fold_region(&mut self, r: Region<'db>) -> Region<'db> {
376        // This one is a little different, because `super_fold_with` is not
377        // implemented on non-recursive `Region`.
378        (self.lt_op)(r)
379    }
380
381    fn fold_const(&mut self, ct: Const<'db>) -> Const<'db> {
382        let ct = ct.super_fold_with(self);
383        (self.ct_op)(ct)
384    }
385}
386
387// FIXME(next-trait-solver): uplift
388pub fn sizedness_constraint_for_ty<'db>(
389    interner: DbInterner<'db>,
390    sizedness: SizedTraitKind,
391    ty: Ty<'db>,
392) -> Option<Ty<'db>> {
393    use rustc_type_ir::TyKind::*;
394
395    match ty.kind() {
396        // these are always sized
397        Bool | Char | Int(..) | Uint(..) | Float(..) | RawPtr(..) | Ref(..) | FnDef(..)
398        | FnPtr(..) | Array(..) | Closure(..) | CoroutineClosure(..) | Coroutine(..)
399        | CoroutineWitness(..) | Never => None,
400
401        // these are never sized
402        Str | Slice(..) | Dynamic(_, _) => match sizedness {
403            // Never `Sized`
404            SizedTraitKind::Sized => Some(ty),
405            // Always `MetaSized`
406            SizedTraitKind::MetaSized => None,
407        },
408
409        // Maybe `Sized` or `MetaSized`
410        Param(..) | Alias(..) | Error(_) => Some(ty),
411
412        // We cannot instantiate the binder, so just return the *original* type back,
413        // but only if the inner type has a sized constraint. Thus we skip the binder,
414        // but don't actually use the result from `sized_constraint_for_ty`.
415        UnsafeBinder(inner_ty) => {
416            sizedness_constraint_for_ty(interner, sizedness, inner_ty.skip_binder()).map(|_| ty)
417        }
418
419        // Never `MetaSized` or `Sized`
420        Foreign(..) => Some(ty),
421
422        // Recursive cases
423        Pat(ty, _) => sizedness_constraint_for_ty(interner, sizedness, ty),
424
425        Tuple(tys) => tys
426            .into_iter()
427            .next_back()
428            .and_then(|ty| sizedness_constraint_for_ty(interner, sizedness, ty)),
429
430        Adt(adt, args) => {
431            if crate::representability::representability(interner.db, adt.def_id())
432                == Representability::Infinite
433            {
434                return None;
435            }
436
437            adt.struct_tail_ty(interner).and_then(|tail_ty| {
438                let tail_ty = tail_ty.instantiate(interner, args).skip_norm_wip();
439                sizedness_constraint_for_ty(interner, sizedness, tail_ty)
440            })
441        }
442
443        Placeholder(..) | Bound(..) | Infer(..) => {
444            panic!("unexpected type `{ty:?}` in sizedness_constraint_for_ty")
445        }
446    }
447}
448
449pub fn apply_args_to_binder<'db, T: TypeFoldable<DbInterner<'db>>>(
450    b: Binder<'db, T>,
451    args: GenericArgs<'db>,
452    interner: DbInterner<'db>,
453) -> T {
454    let types = &mut |ty: BoundTy<'db>| args.as_slice()[ty.var.index()].expect_ty();
455    let regions =
456        &mut |region: BoundRegion<'db>| args.as_slice()[region.var.index()].expect_region();
457    let consts = &mut |const_: BoundConst<'db>| args.as_slice()[const_.var.index()].expect_const();
458    let mut instantiate = BoundVarReplacer::new(interner, FnMutDelegate { types, regions, consts });
459    b.skip_binder().fold_with(&mut instantiate)
460}
461
462#[derive(salsa::Supertype)]
463pub(crate) enum ItemWithBounds<'db> {
464    TypeAliasId(TypeAliasId),
465    InternedOpaqueTyId(InternedOpaqueTyId<'db>),
466}
467impl_from!(impl<'db> TypeAliasId, InternedOpaqueTyId<'db> for ItemWithBounds<'db>);
468
469#[derive(Debug, PartialEq, Eq)]
470pub(crate) struct ItemBounds {
471    bounds: StoredEarlyBinder<StoredClauses>,
472    non_self_bounds_start: u32,
473}
474
475impl ItemBounds {
476    #[inline]
477    pub(crate) fn of_solver_def<'db>(
478        db: &'db dyn HirDatabase,
479        def_id: SolverDefId<'db>,
480    ) -> &'db ItemBounds {
481        let def_id = match def_id {
482            SolverDefId::TypeAliasId(def_id) => def_id.into(),
483            SolverDefId::InternedOpaqueTyId(def_id) => def_id.into(),
484            _ => panic!("unexpected SolverDefId"),
485        };
486        ItemBounds::of(db, def_id)
487    }
488
489    #[inline]
490    pub(crate) fn all_bounds(&self) -> EarlyBinder<'_, impl Iterator<Item = Clause<'_>>> {
491        self.bounds.get().map_bound(|it| it.iter())
492    }
493
494    #[inline]
495    pub(crate) fn self_bounds(&self) -> EarlyBinder<'_, impl Iterator<Item = Clause<'_>>> {
496        self.bounds
497            .get()
498            .map_bound(|it| it.as_slice()[..self.non_self_bounds_start as usize].iter().copied())
499    }
500
501    #[inline]
502    pub(crate) fn non_self_bounds(&self) -> EarlyBinder<'_, impl Iterator<Item = Clause<'_>>> {
503        self.bounds
504            .get()
505            .map_bound(|it| it.as_slice()[self.non_self_bounds_start as usize..].iter().copied())
506    }
507}
508
509#[salsa::tracked]
510impl ItemBounds {
511    #[allow(
512        clippy::drop_non_drop,
513        reason = "this happens in a Salsa macro, not sure why only here"
514    )]
515    #[salsa::tracked]
516    fn of(db: &dyn HirDatabase, def_id: ItemWithBounds<'_>) -> ItemBounds {
517        let (krate, explicit_bounds) = match def_id {
518            ItemWithBounds::TypeAliasId(type_alias) => (
519                type_alias.krate(db),
520                &crate::lower::type_alias_bounds_with_diagnostics(db, type_alias).value,
521            ),
522            ItemWithBounds::InternedOpaqueTyId(id) => {
523                let loc = id.loc(db);
524                let krate = match loc {
525                    ImplTraitId::ReturnTypeImplTrait(def, _) => def.krate(db),
526                    ImplTraitId::TypeAliasImplTrait(def, _) => def.krate(db),
527                };
528                (krate, loc.bounds(db))
529            }
530        };
531        let interner = DbInterner::new_with(db, krate);
532
533        let all_bounds =
534            elaborate(interner, explicit_bounds.all_bounds().skip_binder().iter().copied());
535        let self_bounds =
536            elaborate(interner, explicit_bounds.self_bounds().skip_binder().iter().copied())
537                .filter_only_self();
538
539        let self_bounds = FxHashSet::from_iter(self_bounds);
540        let non_self_bounds = all_bounds.filter(|bound| !self_bounds.contains(bound));
541
542        let non_self_bounds_start = self_bounds.len() as u32;
543        let bounds = StoredEarlyBinder::bind(
544            Clauses::new_from_iter(self_bounds.iter().copied().chain(non_self_bounds)).store(),
545        );
546
547        ItemBounds { bounds, non_self_bounds_start }
548    }
549}
550
551#[salsa::tracked]
552pub(crate) fn impl_super_outlives(
553    db: &dyn HirDatabase,
554    impl_: ImplId,
555) -> StoredEarlyBinder<StoredClauses> {
556    let interner = DbInterner::new_with(db, impl_.krate(db));
557    let trait_ref = db.impl_trait(impl_).expect("invalid impl passed to trait solver");
558    let result = trait_ref.map_bound(|trait_ref| {
559        let clause: Clause<'_> = trait_ref.upcast(interner);
560        elaborate(interner, [clause]).filter(|clause| {
561            matches!(
562                clause.kind().skip_binder(),
563                ClauseKind::TypeOutlives(_) | ClauseKind::RegionOutlives(_)
564            )
565        })
566    });
567    StoredEarlyBinder::bind(Clauses::new_from_iter(result.skip_binder()).store())
568}
569
570pub struct ContainsTypeErrors;
571
572impl<'db> TypeVisitor<DbInterner<'db>> for ContainsTypeErrors {
573    type Result = ControlFlow<()>;
574
575    fn visit_ty(&mut self, t: Ty<'db>) -> Self::Result {
576        match t.kind() {
577            rustc_type_ir::TyKind::Error(_) => ControlFlow::Break(()),
578            _ => t.super_visit_with(self),
579        }
580    }
581}
582
583/// The inverse of [`BoundVarReplacer`]: replaces placeholders with the bound vars from which they came.
584pub struct PlaceholderReplacer<'a, 'db> {
585    infcx: &'a InferCtxt<'db>,
586    mapped_regions: FxIndexMap<PlaceholderRegion<'db>, BoundRegion<'db>>,
587    mapped_types: FxIndexMap<PlaceholderType<'db>, BoundTy<'db>>,
588    mapped_consts: FxIndexMap<PlaceholderConst<'db>, BoundConst<'db>>,
589    universe_indices: &'a [Option<UniverseIndex>],
590    current_index: DebruijnIndex,
591}
592
593impl<'a, 'db> PlaceholderReplacer<'a, 'db> {
594    pub fn replace_placeholders<T: TypeFoldable<DbInterner<'db>>>(
595        infcx: &'a InferCtxt<'db>,
596        mapped_regions: FxIndexMap<PlaceholderRegion<'db>, BoundRegion<'db>>,
597        mapped_types: FxIndexMap<PlaceholderType<'db>, BoundTy<'db>>,
598        mapped_consts: FxIndexMap<PlaceholderConst<'db>, BoundConst<'db>>,
599        universe_indices: &'a [Option<UniverseIndex>],
600        value: T,
601    ) -> T {
602        let mut replacer = PlaceholderReplacer {
603            infcx,
604            mapped_regions,
605            mapped_types,
606            mapped_consts,
607            universe_indices,
608            current_index: INNERMOST,
609        };
610        value.fold_with(&mut replacer)
611    }
612}
613
614impl<'db> TypeFolder<DbInterner<'db>> for PlaceholderReplacer<'_, 'db> {
615    fn cx(&self) -> DbInterner<'db> {
616        self.infcx.interner
617    }
618
619    fn fold_binder<T: TypeFoldable<DbInterner<'db>>>(
620        &mut self,
621        t: Binder<'db, T>,
622    ) -> Binder<'db, T> {
623        if !t.has_placeholders() && !t.has_infer() {
624            return t;
625        }
626        self.current_index.shift_in(1);
627        let t = t.super_fold_with(self);
628        self.current_index.shift_out(1);
629        t
630    }
631
632    fn fold_region(&mut self, r0: Region<'db>) -> Region<'db> {
633        let r1 = match r0.kind() {
634            RegionKind::ReVar(vid) => self
635                .infcx
636                .inner
637                .borrow_mut()
638                .unwrap_region_constraints()
639                .opportunistic_resolve_var(self.infcx.interner, vid),
640            _ => r0,
641        };
642
643        let r2 = match r1.kind() {
644            RegionKind::RePlaceholder(p) => {
645                let replace_var = self.mapped_regions.get(&p);
646                match replace_var {
647                    Some(replace_var) => {
648                        let index = self
649                            .universe_indices
650                            .iter()
651                            .position(|u| matches!(u, Some(pu) if *pu == p.universe))
652                            .unwrap_or_else(|| panic!("Unexpected placeholder universe."));
653                        let db = DebruijnIndex::from_usize(
654                            self.universe_indices.len() - index + self.current_index.as_usize() - 1,
655                        );
656                        Region::new_bound(self.cx(), db, *replace_var)
657                    }
658                    None => r1,
659                }
660            }
661            _ => r1,
662        };
663
664        tracing::debug!(?r0, ?r1, ?r2, "fold_region");
665
666        r2
667    }
668
669    fn fold_ty(&mut self, ty: Ty<'db>) -> Ty<'db> {
670        let ty = self.infcx.shallow_resolve(ty);
671        match ty.kind() {
672            TyKind::Placeholder(p) => {
673                let replace_var = self.mapped_types.get(&p);
674                match replace_var {
675                    Some(replace_var) => {
676                        let index = self
677                            .universe_indices
678                            .iter()
679                            .position(|u| matches!(u, Some(pu) if *pu == p.universe))
680                            .unwrap_or_else(|| panic!("Unexpected placeholder universe."));
681                        let db = DebruijnIndex::from_usize(
682                            self.universe_indices.len() - index + self.current_index.as_usize() - 1,
683                        );
684                        Ty::new_bound(self.infcx.interner, db, *replace_var)
685                    }
686                    None => {
687                        if ty.has_infer() {
688                            ty.super_fold_with(self)
689                        } else {
690                            ty
691                        }
692                    }
693                }
694            }
695
696            _ if ty.has_placeholders() || ty.has_infer() => ty.super_fold_with(self),
697            _ => ty,
698        }
699    }
700
701    fn fold_const(&mut self, ct: Const<'db>) -> Const<'db> {
702        let ct = self.infcx.shallow_resolve_const(ct);
703        if let ConstKind::Placeholder(p) = ct.kind() {
704            let replace_var = self.mapped_consts.get(&p);
705            match replace_var {
706                Some(replace_var) => {
707                    let index = self
708                        .universe_indices
709                        .iter()
710                        .position(|u| matches!(u, Some(pu) if *pu == p.universe))
711                        .unwrap_or_else(|| panic!("Unexpected placeholder universe."));
712                    let db = DebruijnIndex::from_usize(
713                        self.universe_indices.len() - index + self.current_index.as_usize() - 1,
714                    );
715                    Const::new_bound(self.infcx.interner, db, *replace_var)
716                }
717                None => {
718                    if ct.has_infer() {
719                        ct.super_fold_with(self)
720                    } else {
721                        ct
722                    }
723                }
724            }
725        } else {
726            ct.super_fold_with(self)
727        }
728    }
729}
730
731pub fn sizedness_fast_path<'db>(
732    tcx: DbInterner<'db>,
733    predicate: Predicate<'db>,
734    param_env: ParamEnv<'db>,
735) -> bool {
736    // Proving `Sized`/`MetaSized`, very often on "obviously sized" types like
737    // `&T`, accounts for about 60% percentage of the predicates we have to prove. No need to
738    // canonicalize and all that for such cases.
739    if let PredicateKind::Clause(ClauseKind::Trait(trait_pred)) = predicate.kind().skip_binder()
740        && trait_pred.polarity == PredicatePolarity::Positive
741    {
742        let sizedness = match tcx.as_trait_lang_item(trait_pred.def_id()) {
743            Some(SolverTraitLangItem::Sized) => SizedTraitKind::Sized,
744            Some(SolverTraitLangItem::MetaSized) => SizedTraitKind::MetaSized,
745            _ => return false,
746        };
747
748        // FIXME(sized_hierarchy): this temporarily reverts the `sized_hierarchy` feature
749        // while a proper fix for `tests/ui/sized-hierarchy/incomplete-inference-issue-143992.rs`
750        // is pending a proper fix
751        if matches!(sizedness, SizedTraitKind::MetaSized) {
752            return true;
753        }
754
755        if trait_pred.self_ty().has_trivial_sizedness(tcx, sizedness) {
756            tracing::debug!("fast path -- trivial sizedness");
757            return true;
758        }
759
760        if matches!(trait_pred.self_ty().kind(), TyKind::Param(_) | TyKind::Placeholder(_)) {
761            for clause in param_env.caller_bounds().iter() {
762                if let ClauseKind::Trait(clause_pred) = clause.kind().skip_binder()
763                    && clause_pred.polarity == PredicatePolarity::Positive
764                    && clause_pred.self_ty() == trait_pred.self_ty()
765                    && (clause_pred.def_id() == trait_pred.def_id()
766                        || (sizedness == SizedTraitKind::MetaSized
767                            && tcx.is_trait_lang_item(
768                                clause_pred.def_id(),
769                                SolverTraitLangItem::Sized,
770                            )))
771                {
772                    return true;
773                }
774            }
775        }
776    }
777
778    false
779}
780
781/// Casts a trait reference into a reference to one of its super
782/// traits; returns `None` if `target_trait_def_id` is not a
783/// supertrait.
784pub(crate) fn upcast_choices<'db>(
785    interner: DbInterner<'db>,
786    source_trait_ref: PolyTraitRef<'db>,
787    target_trait_def_id: TraitId,
788) -> Vec<PolyTraitRef<'db>> {
789    if source_trait_ref.def_id().0 == target_trait_def_id {
790        return vec![source_trait_ref]; // Shortcut the most common case.
791    }
792
793    elaborate::supertraits(interner, source_trait_ref)
794        .filter(|r| r.def_id().0 == target_trait_def_id)
795        .collect()
796}
797
798#[inline]
799pub(crate) fn clauses_as_obligations<'db>(
800    clauses: impl IntoIterator<Item = Clause<'db>>,
801    cause: ObligationCause,
802    param_env: ParamEnv<'db>,
803) -> impl Iterator<Item = PredicateObligation<'db>> {
804    clauses.into_iter().map(move |clause| Obligation {
805        cause,
806        param_env,
807        predicate: clause.as_predicate(),
808        recursion_depth: 0,
809    })
810}
hir_ty/next_solver/util.rs

hir_ty/next_solver/
util.rs
