hir_ty/next_solver/
util.rs

1//! Various utilities for the next-trait-solver.
2
3use std::iter;
4use std::ops::{self, ControlFlow};
5
6use base_db::Crate;
7use hir_def::lang_item::LangItem;
8use hir_def::{BlockId, HasModule, ItemContainerId, Lookup};
9use intern::sym;
10use la_arena::Idx;
11use rustc_abi::{Float, HasDataLayout, Integer, IntegerType, Primitive, ReprOptions};
12use rustc_type_ir::data_structures::IndexMap;
13use rustc_type_ir::inherent::{
14    AdtDef, Const as _, GenericArg as _, GenericArgs as _, ParamEnv as _, Region as _, SliceLike,
15    Ty as _,
16};
17use rustc_type_ir::lang_items::TraitSolverLangItem;
18use rustc_type_ir::solve::SizedTraitKind;
19use rustc_type_ir::{
20    BoundVar, Canonical, DebruijnIndex, GenericArgKind, INNERMOST, Interner, PredicatePolarity,
21    TypeFlags, TypeVisitable, TypeVisitableExt,
22};
23use rustc_type_ir::{
24    ConstKind, CoroutineArgs, FloatTy, IntTy, RegionKind, TypeFolder, TypeSuperFoldable,
25    TypeSuperVisitable, TypeVisitor, UintTy, UniverseIndex, inherent::IntoKind,
26};
27use rustc_type_ir::{InferCtxtLike, TypeFoldable};
28
29use crate::lower_nextsolver::{LifetimeElisionKind, TyLoweringContext};
30use crate::next_solver::infer::InferCtxt;
31use crate::next_solver::{
32    CanonicalVarKind, FxIndexMap, ParamEnv, Placeholder, PlaceholderConst, PlaceholderRegion,
33    TypingMode,
34};
35use crate::{
36    db::HirDatabase,
37    from_foreign_def_id,
38    method_resolution::{TraitImpls, TyFingerprint},
39};
40
41use super::fold::{BoundVarReplacer, FnMutDelegate};
42use super::generics::generics;
43use super::{
44    AliasTerm, AliasTy, Binder, BoundRegion, BoundTy, BoundTyKind, BoundVarKind, BoundVarKinds,
45    CanonicalVars, Clause, ClauseKind, Clauses, Const, DbInterner, EarlyBinder, GenericArg,
46    GenericArgs, Predicate, PredicateKind, ProjectionPredicate, Region, SolverContext, SolverDefId,
47    Term, TraitPredicate, TraitRef, Ty, TyKind,
48};
49
50#[derive(Clone, Debug)]
51pub struct Discr<'db> {
52    /// Bit representation of the discriminant (e.g., `-128i8` is `0xFF_u128`).
53    pub val: u128,
54    pub ty: Ty<'db>,
55}
56
57impl<'db> Discr<'db> {
58    /// Adds `1` to the value and wraps around if the maximum for the type is reached.
59    pub fn wrap_incr(self, interner: DbInterner<'db>) -> Self {
60        self.checked_add(interner, 1).0
61    }
62    pub fn checked_add(self, interner: DbInterner<'db>, n: u128) -> (Self, bool) {
63        let (size, signed) = self.ty.int_size_and_signed(interner);
64        let (val, oflo) = if signed {
65            let min = size.signed_int_min();
66            let max = size.signed_int_max();
67            let val = size.sign_extend(self.val);
68            assert!(n < (i128::MAX as u128));
69            let n = n as i128;
70            let oflo = val > max - n;
71            let val = if oflo { min + (n - (max - val) - 1) } else { val + n };
72            // zero the upper bits
73            let val = val as u128;
74            let val = size.truncate(val);
75            (val, oflo)
76        } else {
77            let max = size.unsigned_int_max();
78            let val = self.val;
79            let oflo = val > max - n;
80            let val = if oflo { n - (max - val) - 1 } else { val + n };
81            (val, oflo)
82        };
83        (Self { val, ty: self.ty }, oflo)
84    }
85}
86
87pub trait IntegerTypeExt {
88    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
89    fn initial_discriminant<'db>(&self, interner: DbInterner<'db>) -> Discr<'db>;
90    fn disr_incr<'db>(
91        &self,
92        interner: DbInterner<'db>,
93        val: Option<Discr<'db>>,
94    ) -> Option<Discr<'db>>;
95}
96
97impl IntegerTypeExt for IntegerType {
98    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
99        match self {
100            IntegerType::Pointer(true) => Ty::new(interner, TyKind::Int(IntTy::Isize)),
101            IntegerType::Pointer(false) => Ty::new(interner, TyKind::Uint(UintTy::Usize)),
102            IntegerType::Fixed(i, s) => i.to_ty(interner, *s),
103        }
104    }
105
106    fn initial_discriminant<'db>(&self, interner: DbInterner<'db>) -> Discr<'db> {
107        Discr { val: 0, ty: self.to_ty(interner) }
108    }
109
110    fn disr_incr<'db>(
111        &self,
112        interner: DbInterner<'db>,
113        val: Option<Discr<'db>>,
114    ) -> Option<Discr<'db>> {
115        if let Some(val) = val {
116            assert_eq!(self.to_ty(interner), val.ty);
117            let (new, oflo) = val.checked_add(interner, 1);
118            if oflo { None } else { Some(new) }
119        } else {
120            Some(self.initial_discriminant(interner))
121        }
122    }
123}
124
125pub trait IntegerExt {
126    fn to_ty<'db>(&self, interner: DbInterner<'db>, signed: bool) -> Ty<'db>;
127    fn from_int_ty<C: HasDataLayout>(cx: &C, ity: IntTy) -> Integer;
128    fn from_uint_ty<C: HasDataLayout>(cx: &C, ity: UintTy) -> Integer;
129    fn repr_discr<'db>(
130        interner: DbInterner<'db>,
131        ty: Ty<'db>,
132        repr: &ReprOptions,
133        min: i128,
134        max: i128,
135    ) -> (Integer, bool);
136}
137
138impl IntegerExt for Integer {
139    #[inline]
140    fn to_ty<'db>(&self, interner: DbInterner<'db>, signed: bool) -> Ty<'db> {
141        use Integer::*;
142        match (*self, signed) {
143            (I8, false) => Ty::new(interner, TyKind::Uint(UintTy::U8)),
144            (I16, false) => Ty::new(interner, TyKind::Uint(UintTy::U16)),
145            (I32, false) => Ty::new(interner, TyKind::Uint(UintTy::U32)),
146            (I64, false) => Ty::new(interner, TyKind::Uint(UintTy::U64)),
147            (I128, false) => Ty::new(interner, TyKind::Uint(UintTy::U128)),
148            (I8, true) => Ty::new(interner, TyKind::Int(IntTy::I8)),
149            (I16, true) => Ty::new(interner, TyKind::Int(IntTy::I16)),
150            (I32, true) => Ty::new(interner, TyKind::Int(IntTy::I32)),
151            (I64, true) => Ty::new(interner, TyKind::Int(IntTy::I64)),
152            (I128, true) => Ty::new(interner, TyKind::Int(IntTy::I128)),
153        }
154    }
155
156    fn from_int_ty<C: HasDataLayout>(cx: &C, ity: IntTy) -> Integer {
157        use Integer::*;
158        match ity {
159            IntTy::I8 => I8,
160            IntTy::I16 => I16,
161            IntTy::I32 => I32,
162            IntTy::I64 => I64,
163            IntTy::I128 => I128,
164            IntTy::Isize => cx.data_layout().ptr_sized_integer(),
165        }
166    }
167    fn from_uint_ty<C: HasDataLayout>(cx: &C, ity: UintTy) -> Integer {
168        use Integer::*;
169        match ity {
170            UintTy::U8 => I8,
171            UintTy::U16 => I16,
172            UintTy::U32 => I32,
173            UintTy::U64 => I64,
174            UintTy::U128 => I128,
175            UintTy::Usize => cx.data_layout().ptr_sized_integer(),
176        }
177    }
178
179    /// Finds the appropriate Integer type and signedness for the given
180    /// signed discriminant range and `#[repr]` attribute.
181    /// N.B.: `u128` values above `i128::MAX` will be treated as signed, but
182    /// that shouldn't affect anything, other than maybe debuginfo.
183    fn repr_discr<'db>(
184        interner: DbInterner<'db>,
185        ty: Ty<'db>,
186        repr: &ReprOptions,
187        min: i128,
188        max: i128,
189    ) -> (Integer, bool) {
190        // Theoretically, negative values could be larger in unsigned representation
191        // than the unsigned representation of the signed minimum. However, if there
192        // are any negative values, the only valid unsigned representation is u128
193        // which can fit all i128 values, so the result remains unaffected.
194        let unsigned_fit = Integer::fit_unsigned(std::cmp::max(min as u128, max as u128));
195        let signed_fit = std::cmp::max(Integer::fit_signed(min), Integer::fit_signed(max));
196
197        if let Some(ity) = repr.int {
198            let discr = Integer::from_attr(&interner, ity);
199            let fit = if ity.is_signed() { signed_fit } else { unsigned_fit };
200            if discr < fit {
201                panic!(
202                    "Integer::repr_discr: `#[repr]` hint too small for \
203                      discriminant range of enum `{ty:?}`"
204                )
205            }
206            return (discr, ity.is_signed());
207        }
208
209        let at_least = if repr.c() {
210            // This is usually I32, however it can be different on some platforms,
211            // notably hexagon and arm-none/thumb-none
212            interner.data_layout().c_enum_min_size
213        } else {
214            // repr(Rust) enums try to be as small as possible
215            Integer::I8
216        };
217
218        // If there are no negative values, we can use the unsigned fit.
219        if min >= 0 {
220            (std::cmp::max(unsigned_fit, at_least), false)
221        } else {
222            (std::cmp::max(signed_fit, at_least), true)
223        }
224    }
225}
226
227pub trait FloatExt {
228    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
229    fn from_float_ty(fty: FloatTy) -> Self;
230}
231
232impl FloatExt for Float {
233    #[inline]
234    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
235        use Float::*;
236        match *self {
237            F16 => Ty::new(interner, TyKind::Float(FloatTy::F16)),
238            F32 => Ty::new(interner, TyKind::Float(FloatTy::F32)),
239            F64 => Ty::new(interner, TyKind::Float(FloatTy::F64)),
240            F128 => Ty::new(interner, TyKind::Float(FloatTy::F128)),
241        }
242    }
243
244    fn from_float_ty(fty: FloatTy) -> Self {
245        use Float::*;
246        match fty {
247            FloatTy::F16 => F16,
248            FloatTy::F32 => F32,
249            FloatTy::F64 => F64,
250            FloatTy::F128 => F128,
251        }
252    }
253}
254
255pub trait PrimitiveExt {
256    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
257    fn to_int_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
258}
259
260impl PrimitiveExt for Primitive {
261    #[inline]
262    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
263        match *self {
264            Primitive::Int(i, signed) => i.to_ty(interner, signed),
265            Primitive::Float(f) => f.to_ty(interner),
266            Primitive::Pointer(_) => Ty::new(
267                interner,
268                TyKind::RawPtr(
269                    Ty::new(interner, TyKind::Tuple(Default::default())),
270                    rustc_ast_ir::Mutability::Mut,
271                ),
272            ),
273        }
274    }
275
276    /// Return an *integer* type matching this primitive.
277    /// Useful in particular when dealing with enum discriminants.
278    #[inline]
279    fn to_int_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
280        match *self {
281            Primitive::Int(i, signed) => i.to_ty(interner, signed),
282            Primitive::Pointer(_) => {
283                let signed = false;
284                interner.data_layout().ptr_sized_integer().to_ty(interner, signed)
285            }
286            Primitive::Float(_) => panic!("floats do not have an int type"),
287        }
288    }
289}
290
291impl<'db> HasDataLayout for DbInterner<'db> {
292    fn data_layout(&self) -> &rustc_abi::TargetDataLayout {
293        unimplemented!()
294    }
295}
296
297pub trait CoroutineArgsExt<'db> {
298    fn discr_ty(&self, interner: DbInterner<'db>) -> Ty<'db>;
299}
300
301impl<'db> CoroutineArgsExt<'db> for CoroutineArgs<DbInterner<'db>> {
302    /// The type of the state discriminant used in the coroutine type.
303    #[inline]
304    fn discr_ty(&self, interner: DbInterner<'db>) -> Ty<'db> {
305        Ty::new(interner, TyKind::Uint(UintTy::U32))
306    }
307}
308
309/// Finds the max universe present
310pub struct MaxUniverse {
311    max_universe: UniverseIndex,
312}
313
314impl Default for MaxUniverse {
315    fn default() -> Self {
316        Self::new()
317    }
318}
319
320impl MaxUniverse {
321    pub fn new() -> Self {
322        MaxUniverse { max_universe: UniverseIndex::ROOT }
323    }
324
325    pub fn max_universe(self) -> UniverseIndex {
326        self.max_universe
327    }
328}
329
330impl<'db> TypeVisitor<DbInterner<'db>> for MaxUniverse {
331    type Result = ();
332
333    fn visit_ty(&mut self, t: Ty<'db>) {
334        if let TyKind::Placeholder(placeholder) = t.kind() {
335            self.max_universe = UniverseIndex::from_u32(
336                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
337            );
338        }
339
340        t.super_visit_with(self)
341    }
342
343    fn visit_const(&mut self, c: Const<'db>) {
344        if let ConstKind::Placeholder(placeholder) = c.kind() {
345            self.max_universe = UniverseIndex::from_u32(
346                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
347            );
348        }
349
350        c.super_visit_with(self)
351    }
352
353    fn visit_region(&mut self, r: Region<'db>) {
354        if let RegionKind::RePlaceholder(placeholder) = r.kind() {
355            self.max_universe = UniverseIndex::from_u32(
356                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
357            );
358        }
359    }
360}
361
362pub struct BottomUpFolder<'db, F, G, H>
363where
364    F: FnMut(Ty<'db>) -> Ty<'db>,
365    G: FnMut(Region<'db>) -> Region<'db>,
366    H: FnMut(Const<'db>) -> Const<'db>,
367{
368    pub interner: DbInterner<'db>,
369    pub ty_op: F,
370    pub lt_op: G,
371    pub ct_op: H,
372}
373
374impl<'db, F, G, H> TypeFolder<DbInterner<'db>> for BottomUpFolder<'db, F, G, H>
375where
376    F: FnMut(Ty<'db>) -> Ty<'db>,
377    G: FnMut(Region<'db>) -> Region<'db>,
378    H: FnMut(Const<'db>) -> Const<'db>,
379{
380    fn cx(&self) -> DbInterner<'db> {
381        self.interner
382    }
383
384    fn fold_ty(&mut self, ty: Ty<'db>) -> Ty<'db> {
385        let t = ty.super_fold_with(self);
386        (self.ty_op)(t)
387    }
388
389    fn fold_region(&mut self, r: Region<'db>) -> Region<'db> {
390        // This one is a little different, because `super_fold_with` is not
391        // implemented on non-recursive `Region`.
392        (self.lt_op)(r)
393    }
394
395    fn fold_const(&mut self, ct: Const<'db>) -> Const<'db> {
396        let ct = ct.super_fold_with(self);
397        (self.ct_op)(ct)
398    }
399}
400
401pub(crate) fn for_trait_impls(
402    db: &dyn HirDatabase,
403    krate: Crate,
404    block: Option<BlockId>,
405    trait_id: hir_def::TraitId,
406    self_ty_fp: Option<TyFingerprint>,
407    mut f: impl FnMut(&TraitImpls) -> ControlFlow<()>,
408) -> ControlFlow<()> {
409    // Note: Since we're using `impls_for_trait` and `impl_provided_for`,
410    // only impls where the trait can be resolved should ever reach Chalk.
411    // `impl_datum` relies on that and will panic if the trait can't be resolved.
412    let in_deps = db.trait_impls_in_deps(krate);
413    let in_self = db.trait_impls_in_crate(krate);
414    let trait_module = trait_id.module(db);
415    let type_module = match self_ty_fp {
416        Some(TyFingerprint::Adt(adt_id)) => Some(adt_id.module(db)),
417        Some(TyFingerprint::ForeignType(type_id)) => Some(from_foreign_def_id(type_id).module(db)),
418        Some(TyFingerprint::Dyn(trait_id)) => Some(trait_id.module(db)),
419        _ => None,
420    };
421
422    let mut def_blocks =
423        [trait_module.containing_block(), type_module.and_then(|it| it.containing_block())];
424
425    let block_impls = iter::successors(block, |&block_id| {
426        cov_mark::hit!(block_local_impls);
427        block_id.loc(db).module.containing_block()
428    })
429    .inspect(|&block_id| {
430        // make sure we don't search the same block twice
431        def_blocks.iter_mut().for_each(|block| {
432            if *block == Some(block_id) {
433                *block = None;
434            }
435        });
436    })
437    .filter_map(|block_id| db.trait_impls_in_block(block_id));
438    f(&in_self)?;
439    for it in in_deps.iter().map(ops::Deref::deref) {
440        f(it)?;
441    }
442    for it in block_impls {
443        f(&it)?;
444    }
445    for it in def_blocks.into_iter().flatten().filter_map(|it| db.trait_impls_in_block(it)) {
446        f(&it)?;
447    }
448    ControlFlow::Continue(())
449}
450
451// FIXME(next-trait-solver): uplift
452pub fn sizedness_constraint_for_ty<'db>(
453    interner: DbInterner<'db>,
454    sizedness: SizedTraitKind,
455    ty: Ty<'db>,
456) -> Option<Ty<'db>> {
457    use rustc_type_ir::TyKind::*;
458
459    match ty.kind() {
460        // these are always sized
461        Bool | Char | Int(..) | Uint(..) | Float(..) | RawPtr(..) | Ref(..) | FnDef(..)
462        | FnPtr(..) | Array(..) | Closure(..) | CoroutineClosure(..) | Coroutine(..)
463        | CoroutineWitness(..) | Never => None,
464
465        // these are never sized
466        Str | Slice(..) | Dynamic(_, _, rustc_type_ir::DynKind::Dyn) => match sizedness {
467            // Never `Sized`
468            SizedTraitKind::Sized => Some(ty),
469            // Always `MetaSized`
470            SizedTraitKind::MetaSized => None,
471        },
472
473        // Maybe `Sized` or `MetaSized`
474        Param(..) | Alias(..) | Error(_) => Some(ty),
475
476        // We cannot instantiate the binder, so just return the *original* type back,
477        // but only if the inner type has a sized constraint. Thus we skip the binder,
478        // but don't actually use the result from `sized_constraint_for_ty`.
479        UnsafeBinder(inner_ty) => {
480            sizedness_constraint_for_ty(interner, sizedness, inner_ty.skip_binder()).map(|_| ty)
481        }
482
483        // Never `MetaSized` or `Sized`
484        Foreign(..) => Some(ty),
485
486        // Recursive cases
487        Pat(ty, _) => sizedness_constraint_for_ty(interner, sizedness, ty),
488
489        Tuple(tys) => tys
490            .into_iter()
491            .last()
492            .and_then(|ty| sizedness_constraint_for_ty(interner, sizedness, ty)),
493
494        Adt(adt, args) => {
495            let tail_ty =
496                EarlyBinder::bind(adt.all_field_tys(interner).skip_binder().into_iter().last()?)
497                    .instantiate(interner, args);
498            sizedness_constraint_for_ty(interner, sizedness, tail_ty)
499        }
500
501        Placeholder(..) | Bound(..) | Infer(..) => {
502            panic!("unexpected type `{ty:?}` in sizedness_constraint_for_ty")
503        }
504    }
505}
506
507pub fn apply_args_to_binder<'db, T: TypeFoldable<DbInterner<'db>>>(
508    b: Binder<'db, T>,
509    args: GenericArgs<'db>,
510    interner: DbInterner<'db>,
511) -> T {
512    let types = &mut |ty: BoundTy| args.as_slice()[ty.var.index()].expect_ty();
513    let regions = &mut |region: BoundRegion| args.as_slice()[region.var.index()].expect_region();
514    let consts = &mut |const_: BoundVar| args.as_slice()[const_.index()].expect_const();
515    let mut instantiate = BoundVarReplacer::new(interner, FnMutDelegate { types, regions, consts });
516    b.skip_binder().fold_with(&mut instantiate)
517}
518
519pub(crate) fn mini_canonicalize<'db, T: TypeFoldable<DbInterner<'db>>>(
520    mut context: SolverContext<'db>,
521    val: T,
522) -> Canonical<DbInterner<'db>, T> {
523    let mut canon = MiniCanonicalizer {
524        context: &mut context,
525        db: DebruijnIndex::ZERO,
526        vars: IndexMap::default(),
527    };
528    let canon_val = val.fold_with(&mut canon);
529    let vars = canon.vars;
530    Canonical {
531        value: canon_val,
532        max_universe: UniverseIndex::from_u32(1),
533        variables: CanonicalVars::new_from_iter(
534            context.cx(),
535            vars.iter().map(|(k, v)| match (*k).kind() {
536                GenericArgKind::Type(ty) => match ty.kind() {
537                    TyKind::Int(..) | TyKind::Uint(..) => {
538                        rustc_type_ir::CanonicalVarKind::Ty(rustc_type_ir::CanonicalTyVarKind::Int)
539                    }
540                    TyKind::Float(..) => rustc_type_ir::CanonicalVarKind::Ty(
541                        rustc_type_ir::CanonicalTyVarKind::Float,
542                    ),
543                    _ => rustc_type_ir::CanonicalVarKind::Ty(
544                        rustc_type_ir::CanonicalTyVarKind::General(UniverseIndex::ZERO),
545                    ),
546                },
547                GenericArgKind::Lifetime(_) => {
548                    rustc_type_ir::CanonicalVarKind::Region(UniverseIndex::ZERO)
549                }
550                GenericArgKind::Const(_) => {
551                    rustc_type_ir::CanonicalVarKind::Const(UniverseIndex::ZERO)
552                }
553            }),
554        ),
555    }
556}
557
558struct MiniCanonicalizer<'a, 'db> {
559    context: &'a mut SolverContext<'db>,
560    db: DebruijnIndex,
561    vars: IndexMap<GenericArg<'db>, usize>,
562}
563
564impl<'db> TypeFolder<DbInterner<'db>> for MiniCanonicalizer<'_, 'db> {
565    fn cx(&self) -> DbInterner<'db> {
566        self.context.cx()
567    }
568
569    fn fold_binder<T: TypeFoldable<DbInterner<'db>>>(
570        &mut self,
571        t: rustc_type_ir::Binder<DbInterner<'db>, T>,
572    ) -> rustc_type_ir::Binder<DbInterner<'db>, T> {
573        self.db.shift_in(1);
574        let res = t.map_bound(|t| t.fold_with(self));
575        self.db.shift_out(1);
576        res
577    }
578
579    fn fold_ty(&mut self, t: Ty<'db>) -> Ty<'db> {
580        match t.kind() {
581            rustc_type_ir::TyKind::Bound(db, _) => {
582                if db >= self.db {
583                    panic!("Unexpected bound var");
584                }
585                t
586            }
587            rustc_type_ir::TyKind::Infer(infer) => {
588                let t = match infer {
589                    rustc_type_ir::InferTy::TyVar(vid) => {
590                        self.context.opportunistic_resolve_ty_var(vid)
591                    }
592                    rustc_type_ir::InferTy::IntVar(vid) => {
593                        self.context.opportunistic_resolve_int_var(vid)
594                    }
595                    rustc_type_ir::InferTy::FloatVar(vid) => {
596                        self.context.opportunistic_resolve_float_var(vid)
597                    }
598                    _ => t,
599                };
600                let len = self.vars.len();
601                let var = *self.vars.entry(t.into()).or_insert(len);
602                Ty::new(
603                    self.cx(),
604                    TyKind::Bound(
605                        self.db,
606                        BoundTy { kind: super::BoundTyKind::Anon, var: BoundVar::from_usize(var) },
607                    ),
608                )
609            }
610            _ => t.super_fold_with(self),
611        }
612    }
613
614    fn fold_region(
615        &mut self,
616        r: <DbInterner<'db> as rustc_type_ir::Interner>::Region,
617    ) -> <DbInterner<'db> as rustc_type_ir::Interner>::Region {
618        match r.kind() {
619            RegionKind::ReBound(db, _) => {
620                if db >= self.db {
621                    panic!("Unexpected bound var");
622                }
623                r
624            }
625            RegionKind::ReVar(vid) => {
626                let len = self.vars.len();
627                let var = *self.vars.entry(r.into()).or_insert(len);
628                Region::new(
629                    self.cx(),
630                    RegionKind::ReBound(
631                        self.db,
632                        BoundRegion {
633                            kind: super::BoundRegionKind::Anon,
634                            var: BoundVar::from_usize(var),
635                        },
636                    ),
637                )
638            }
639            _ => r,
640        }
641    }
642
643    fn fold_const(
644        &mut self,
645        c: <DbInterner<'db> as rustc_type_ir::Interner>::Const,
646    ) -> <DbInterner<'db> as rustc_type_ir::Interner>::Const {
647        match c.kind() {
648            ConstKind::Bound(db, _) => {
649                if db >= self.db {
650                    panic!("Unexpected bound var");
651                }
652                c
653            }
654            ConstKind::Infer(infer) => {
655                let len = self.vars.len();
656                let var = *self.vars.entry(c.into()).or_insert(len);
657                Const::new(self.cx(), ConstKind::Bound(self.db, BoundVar::from_usize(var)))
658            }
659            _ => c.super_fold_with(self),
660        }
661    }
662}
663
664pub fn explicit_item_bounds<'db>(
665    interner: DbInterner<'db>,
666    def_id: SolverDefId,
667) -> EarlyBinder<'db, Clauses<'db>> {
668    let db = interner.db();
669    match def_id {
670        SolverDefId::TypeAliasId(type_alias) => {
671            let trait_ = match type_alias.lookup(db).container {
672                ItemContainerId::TraitId(t) => t,
673                _ => panic!("associated type not in trait"),
674            };
675
676            // Lower bounds -- we could/should maybe move this to a separate query in `lower`
677            let type_alias_data = db.type_alias_signature(type_alias);
678            let generic_params = generics(db, type_alias.into());
679            let resolver = hir_def::resolver::HasResolver::resolver(type_alias, db);
680            let mut ctx = TyLoweringContext::new(
681                db,
682                &resolver,
683                &type_alias_data.store,
684                type_alias.into(),
685                LifetimeElisionKind::AnonymousReportError,
686            );
687
688            let item_args = GenericArgs::identity_for_item(interner, def_id);
689            let interner_ty = Ty::new_projection_from_args(interner, def_id, item_args);
690
691            let mut bounds = Vec::new();
692            for bound in &type_alias_data.bounds {
693                ctx.lower_type_bound(bound, interner_ty, false).for_each(|pred| {
694                    bounds.push(pred);
695                });
696            }
697
698            if !ctx.unsized_types.contains(&interner_ty) {
699                let sized_trait = LangItem::Sized
700                    .resolve_trait(ctx.db, interner.krate.expect("Must have interner.krate"));
701                let sized_bound = sized_trait.map(|trait_id| {
702                    let trait_ref = TraitRef::new_from_args(
703                        interner,
704                        trait_id.into(),
705                        GenericArgs::new_from_iter(interner, [interner_ty.into()]),
706                    );
707                    Clause(Predicate::new(
708                        interner,
709                        Binder::dummy(rustc_type_ir::PredicateKind::Clause(
710                            rustc_type_ir::ClauseKind::Trait(TraitPredicate {
711                                trait_ref,
712                                polarity: rustc_type_ir::PredicatePolarity::Positive,
713                            }),
714                        )),
715                    ))
716                });
717                bounds.extend(sized_bound);
718                bounds.shrink_to_fit();
719            }
720
721            rustc_type_ir::EarlyBinder::bind(Clauses::new_from_iter(interner, bounds))
722        }
723        SolverDefId::InternedOpaqueTyId(id) => {
724            let full_id = db.lookup_intern_impl_trait_id(id);
725            match full_id {
726                crate::ImplTraitId::ReturnTypeImplTrait(func, idx) => {
727                    let datas = db
728                        .return_type_impl_traits_ns(func)
729                        .expect("impl trait id without impl traits");
730                    let datas = (*datas).as_ref().skip_binder();
731                    let data = &datas.impl_traits[Idx::from_raw(idx.into_raw())];
732                    EarlyBinder::bind(Clauses::new_from_iter(interner, data.predicates.clone()))
733                }
734                crate::ImplTraitId::TypeAliasImplTrait(alias, idx) => {
735                    let datas = db
736                        .type_alias_impl_traits_ns(alias)
737                        .expect("impl trait id without impl traits");
738                    let datas = (*datas).as_ref().skip_binder();
739                    let data = &datas.impl_traits[Idx::from_raw(idx.into_raw())];
740                    EarlyBinder::bind(Clauses::new_from_iter(interner, data.predicates.clone()))
741                }
742                crate::ImplTraitId::AsyncBlockTypeImplTrait(..) => {
743                    if let Some((future_trait, future_output)) = LangItem::Future
744                        .resolve_trait(db, interner.krate.expect("Must have interner.krate"))
745                        .and_then(|trait_| {
746                            let alias = trait_.trait_items(db).associated_type_by_name(
747                                &hir_expand::name::Name::new_symbol_root(sym::Output.clone()),
748                            )?;
749                            Some((trait_, alias))
750                        })
751                    {
752                        let args = GenericArgs::identity_for_item(interner, def_id);
753                        let out = args.as_slice()[0];
754                        let mut predicates = vec![];
755
756                        let item_ty = Ty::new_alias(
757                            interner,
758                            rustc_type_ir::AliasTyKind::Opaque,
759                            AliasTy::new_from_args(interner, def_id, args),
760                        );
761
762                        let kind = PredicateKind::Clause(ClauseKind::Trait(TraitPredicate {
763                            polarity: rustc_type_ir::PredicatePolarity::Positive,
764                            trait_ref: TraitRef::new_from_args(
765                                interner,
766                                future_trait.into(),
767                                GenericArgs::new_from_iter(interner, [item_ty.into()]),
768                            ),
769                        }));
770                        predicates.push(Clause(Predicate::new(
771                            interner,
772                            Binder::bind_with_vars(
773                                kind,
774                                BoundVarKinds::new_from_iter(
775                                    interner,
776                                    [BoundVarKind::Ty(BoundTyKind::Anon)],
777                                ),
778                            ),
779                        )));
780                        let sized_trait = LangItem::Sized
781                            .resolve_trait(db, interner.krate.expect("Must have interner.krate"));
782                        if let Some(sized_trait_) = sized_trait {
783                            let kind = PredicateKind::Clause(ClauseKind::Trait(TraitPredicate {
784                                polarity: rustc_type_ir::PredicatePolarity::Positive,
785                                trait_ref: TraitRef::new_from_args(
786                                    interner,
787                                    sized_trait_.into(),
788                                    GenericArgs::new_from_iter(interner, [item_ty.into()]),
789                                ),
790                            }));
791                            predicates.push(Clause(Predicate::new(
792                                interner,
793                                Binder::bind_with_vars(
794                                    kind,
795                                    BoundVarKinds::new_from_iter(
796                                        interner,
797                                        [BoundVarKind::Ty(BoundTyKind::Anon)],
798                                    ),
799                                ),
800                            )));
801                        }
802                        let kind =
803                            PredicateKind::Clause(ClauseKind::Projection(ProjectionPredicate {
804                                projection_term: AliasTerm::new_from_args(
805                                    interner,
806                                    future_output.into(),
807                                    GenericArgs::new_from_iter(interner, [item_ty.into()]),
808                                ),
809                                term: match out.kind() {
810                                    GenericArgKind::Lifetime(lt) => panic!(),
811                                    GenericArgKind::Type(ty) => Term::Ty(ty),
812                                    GenericArgKind::Const(const_) => Term::Const(const_),
813                                },
814                            }));
815                        predicates.push(Clause(Predicate::new(
816                            interner,
817                            Binder::bind_with_vars(
818                                kind,
819                                BoundVarKinds::new_from_iter(
820                                    interner,
821                                    [BoundVarKind::Ty(BoundTyKind::Anon)],
822                                ),
823                            ),
824                        )));
825                        EarlyBinder::bind(Clauses::new_from_iter(interner, predicates))
826                    } else {
827                        // If failed to find Symbol’s value as variable is void: Future::Output, return empty bounds as fallback.
828                        EarlyBinder::bind(Clauses::new_from_iter(interner, []))
829                    }
830                }
831            }
832        }
833        _ => panic!("Unexpected GeneridDefId"),
834    }
835}
836
837pub struct ContainsTypeErrors;
838
839impl<'db> TypeVisitor<DbInterner<'db>> for ContainsTypeErrors {
840    type Result = ControlFlow<()>;
841
842    fn visit_ty(&mut self, t: Ty<'db>) -> Self::Result {
843        match t.kind() {
844            rustc_type_ir::TyKind::Error(_) => ControlFlow::Break(()),
845            _ => t.super_visit_with(self),
846        }
847    }
848}
849
850/// The inverse of [`BoundVarReplacer`]: replaces placeholders with the bound vars from which they came.
851pub struct PlaceholderReplacer<'a, 'db> {
852    infcx: &'a InferCtxt<'db>,
853    mapped_regions: FxIndexMap<PlaceholderRegion, BoundRegion>,
854    mapped_types: FxIndexMap<Placeholder<BoundTy>, BoundTy>,
855    mapped_consts: FxIndexMap<PlaceholderConst, BoundVar>,
856    universe_indices: &'a [Option<UniverseIndex>],
857    current_index: DebruijnIndex,
858}
859
860impl<'a, 'db> PlaceholderReplacer<'a, 'db> {
861    pub fn replace_placeholders<T: TypeFoldable<DbInterner<'db>>>(
862        infcx: &'a InferCtxt<'db>,
863        mapped_regions: FxIndexMap<PlaceholderRegion, BoundRegion>,
864        mapped_types: FxIndexMap<Placeholder<BoundTy>, BoundTy>,
865        mapped_consts: FxIndexMap<PlaceholderConst, BoundVar>,
866        universe_indices: &'a [Option<UniverseIndex>],
867        value: T,
868    ) -> T {
869        let mut replacer = PlaceholderReplacer {
870            infcx,
871            mapped_regions,
872            mapped_types,
873            mapped_consts,
874            universe_indices,
875            current_index: INNERMOST,
876        };
877        value.fold_with(&mut replacer)
878    }
879}
880
881impl<'db> TypeFolder<DbInterner<'db>> for PlaceholderReplacer<'_, 'db> {
882    fn cx(&self) -> DbInterner<'db> {
883        self.infcx.interner
884    }
885
886    fn fold_binder<T: TypeFoldable<DbInterner<'db>>>(
887        &mut self,
888        t: Binder<'db, T>,
889    ) -> Binder<'db, T> {
890        if !t.has_placeholders() && !t.has_infer() {
891            return t;
892        }
893        self.current_index.shift_in(1);
894        let t = t.super_fold_with(self);
895        self.current_index.shift_out(1);
896        t
897    }
898
899    fn fold_region(&mut self, r0: Region<'db>) -> Region<'db> {
900        let r1 = match r0.kind() {
901            RegionKind::ReVar(vid) => self
902                .infcx
903                .inner
904                .borrow_mut()
905                .unwrap_region_constraints()
906                .opportunistic_resolve_var(self.infcx.interner, vid),
907            _ => r0,
908        };
909
910        let r2 = match r1.kind() {
911            RegionKind::RePlaceholder(p) => {
912                let replace_var = self.mapped_regions.get(&p);
913                match replace_var {
914                    Some(replace_var) => {
915                        let index = self
916                            .universe_indices
917                            .iter()
918                            .position(|u| matches!(u, Some(pu) if *pu == p.universe))
919                            .unwrap_or_else(|| panic!("Unexpected placeholder universe."));
920                        let db = DebruijnIndex::from_usize(
921                            self.universe_indices.len() - index + self.current_index.as_usize() - 1,
922                        );
923                        Region::new_bound(self.cx(), db, *replace_var)
924                    }
925                    None => r1,
926                }
927            }
928            _ => r1,
929        };
930
931        tracing::debug!(?r0, ?r1, ?r2, "fold_region");
932
933        r2
934    }
935
936    fn fold_ty(&mut self, ty: Ty<'db>) -> Ty<'db> {
937        let ty = self.infcx.shallow_resolve(ty);
938        match ty.kind() {
939            TyKind::Placeholder(p) => {
940                let replace_var = self.mapped_types.get(&p);
941                match replace_var {
942                    Some(replace_var) => {
943                        let index = self
944                            .universe_indices
945                            .iter()
946                            .position(|u| matches!(u, Some(pu) if *pu == p.universe))
947                            .unwrap_or_else(|| panic!("Unexpected placeholder universe."));
948                        let db = DebruijnIndex::from_usize(
949                            self.universe_indices.len() - index + self.current_index.as_usize() - 1,
950                        );
951                        Ty::new_bound(self.infcx.interner, db, *replace_var)
952                    }
953                    None => {
954                        if ty.has_infer() {
955                            ty.super_fold_with(self)
956                        } else {
957                            ty
958                        }
959                    }
960                }
961            }
962
963            _ if ty.has_placeholders() || ty.has_infer() => ty.super_fold_with(self),
964            _ => ty,
965        }
966    }
967
968    fn fold_const(&mut self, ct: Const<'db>) -> Const<'db> {
969        let ct = self.infcx.shallow_resolve_const(ct);
970        if let ConstKind::Placeholder(p) = ct.kind() {
971            let replace_var = self.mapped_consts.get(&p);
972            match replace_var {
973                Some(replace_var) => {
974                    let index = self
975                        .universe_indices
976                        .iter()
977                        .position(|u| matches!(u, Some(pu) if *pu == p.universe))
978                        .unwrap_or_else(|| panic!("Unexpected placeholder universe."));
979                    let db = DebruijnIndex::from_usize(
980                        self.universe_indices.len() - index + self.current_index.as_usize() - 1,
981                    );
982                    Const::new_bound(self.infcx.interner, db, *replace_var)
983                }
984                None => {
985                    if ct.has_infer() {
986                        ct.super_fold_with(self)
987                    } else {
988                        ct
989                    }
990                }
991            }
992        } else {
993            ct.super_fold_with(self)
994        }
995    }
996}
997
998pub(crate) fn needs_normalization<'db, T: TypeVisitable<DbInterner<'db>>>(
999    infcx: &InferCtxt<'db>,
1000    value: &T,
1001) -> bool {
1002    let mut flags = TypeFlags::HAS_ALIAS;
1003
1004    // Opaques are treated as rigid outside of `TypingMode::PostAnalysis`,
1005    // so we can ignore those.
1006    match infcx.typing_mode() {
1007        // FIXME(#132279): We likely want to reveal opaques during post borrowck analysis
1008        TypingMode::Coherence
1009        | TypingMode::Analysis { .. }
1010        | TypingMode::Borrowck { .. }
1011        | TypingMode::PostBorrowckAnalysis { .. } => flags.remove(TypeFlags::HAS_TY_OPAQUE),
1012        TypingMode::PostAnalysis => {}
1013    }
1014
1015    value.has_type_flags(flags)
1016}
1017
1018pub fn sizedness_fast_path<'db>(
1019    tcx: DbInterner<'db>,
1020    predicate: Predicate<'db>,
1021    param_env: ParamEnv<'db>,
1022) -> bool {
1023    // Proving `Sized`/`MetaSized`, very often on "obviously sized" types like
1024    // `&T`, accounts for about 60% percentage of the predicates we have to prove. No need to
1025    // canonicalize and all that for such cases.
1026    if let PredicateKind::Clause(ClauseKind::Trait(trait_pred)) = predicate.kind().skip_binder()
1027        && trait_pred.polarity == PredicatePolarity::Positive
1028    {
1029        let sizedness = match tcx.as_lang_item(trait_pred.def_id()) {
1030            Some(TraitSolverLangItem::Sized) => SizedTraitKind::Sized,
1031            Some(TraitSolverLangItem::MetaSized) => SizedTraitKind::MetaSized,
1032            _ => return false,
1033        };
1034
1035        // FIXME(sized_hierarchy): this temporarily reverts the `sized_hierarchy` feature
1036        // while a proper fix for `tests/ui/sized-hierarchy/incomplete-inference-issue-143992.rs`
1037        // is pending a proper fix
1038        if matches!(sizedness, SizedTraitKind::MetaSized) {
1039            return true;
1040        }
1041
1042        if trait_pred.self_ty().has_trivial_sizedness(tcx, sizedness) {
1043            tracing::debug!("fast path -- trivial sizedness");
1044            return true;
1045        }
1046
1047        if matches!(trait_pred.self_ty().kind(), TyKind::Param(_) | TyKind::Placeholder(_)) {
1048            for clause in param_env.caller_bounds().iter() {
1049                if let ClauseKind::Trait(clause_pred) = clause.kind().skip_binder()
1050                    && clause_pred.polarity == PredicatePolarity::Positive
1051                    && clause_pred.self_ty() == trait_pred.self_ty()
1052                    && (clause_pred.def_id() == trait_pred.def_id()
1053                        || (sizedness == SizedTraitKind::MetaSized
1054                            && tcx.is_lang_item(clause_pred.def_id(), TraitSolverLangItem::Sized)))
1055                {
1056                    return true;
1057                }
1058            }
1059        }
1060    }
1061
1062    false
1063}
hir_ty/next_solver/util.rs

hir_ty/next_solver/
util.rs
