hir_ty/
traits.rs

1//! Trait solving using next trait solver.
2
3use std::{cell::OnceCell, hash::Hash};
4
5use base_db::Crate;
6use hir_def::{
7    AdtId, AssocItemId, ExpressionStoreOwnerId, GenericDefId, HasModule, ImplId, Lookup, TraitId,
8    expr_store::ExpressionStore,
9    hir::generics::WherePredicate,
10    lang_item::LangItems,
11    nameres::DefMap,
12    resolver::Resolver,
13    signatures::{
14        ConstFlags, ConstSignature, EnumFlags, EnumSignature, FnFlags, FunctionSignature,
15        StructFlags, StructSignature, TraitFlags, TraitSignature, TypeAliasFlags,
16        TypeAliasSignature, UnionSignature,
17    },
18};
19use hir_expand::name::Name;
20use intern::sym;
21use rustc_type_ir::{
22    TypeVisitableExt, TypingMode,
23    inherent::{BoundExistentialPredicates, IntoKind, Ty as _},
24};
25
26use crate::{
27    LifetimeElisionKind, LifetimeLoweringMode, Span, TyLoweringContext,
28    db::HirDatabase,
29    generics::Generics,
30    lower::LoweringMode,
31    next_solver::{
32        DbInterner, GenericArgs, ParamEnv, StoredClauses, Ty, TyKind,
33        infer::{
34            DbInternerInferExt, InferCtxt,
35            select::EvaluationResult,
36            traits::{Obligation, ObligationCause},
37        },
38        obligation_ctxt::ObligationCtxt,
39    },
40};
41
42/// Type for `hir`, because commonly we want both param env and a crate in an exported API.
43#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
44pub struct ParamEnvAndCrate<'db> {
45    pub param_env: ParamEnv<'db>,
46    pub krate: Crate,
47}
48
49impl<'db> ParamEnvAndCrate<'db> {
50    #[inline]
51    pub fn store(self) -> StoredParamEnvAndCrate {
52        StoredParamEnvAndCrate { param_env: self.param_env.clauses.store(), krate: self.krate }
53    }
54}
55
56#[derive(Debug, Clone, PartialEq, Eq, Hash)]
57pub struct StoredParamEnvAndCrate {
58    param_env: StoredClauses,
59    pub krate: Crate,
60}
61
62impl StoredParamEnvAndCrate {
63    #[inline]
64    pub fn param_env<'db>(&self, _db: &'db dyn HirDatabase) -> ParamEnv<'db> {
65        ParamEnv { clauses: self.param_env.as_ref() }
66    }
67
68    #[inline]
69    pub fn as_ref<'db>(&self, db: &'db dyn HirDatabase) -> ParamEnvAndCrate<'db> {
70        ParamEnvAndCrate { param_env: self.param_env(db), krate: self.krate }
71    }
72}
73
74/// This should be used in `hir` only.
75pub fn structurally_normalize_ty<'db>(
76    infcx: &InferCtxt<'db>,
77    ty: Ty<'db>,
78    env: ParamEnv<'db>,
79) -> Ty<'db> {
80    let TyKind::Alias(..) = ty.kind() else { return ty };
81    let mut ocx = ObligationCtxt::new(infcx);
82    let ty = ocx.structurally_normalize_ty(&ObligationCause::dummy(), env, ty).unwrap_or(ty);
83    ty.replace_infer_with_error(infcx.interner)
84}
85
86#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, salsa::Update)]
87pub enum FnTrait {
88    // Warning: Order is important. If something implements `x` it should also implement
89    // `y` if `y <= x`.
90    FnOnce,
91    FnMut,
92    Fn,
93
94    AsyncFnOnce,
95    AsyncFnMut,
96    AsyncFn,
97}
98
99impl FnTrait {
100    pub fn method_name(self) -> Name {
101        match self {
102            FnTrait::FnOnce => Name::new_symbol_root(sym::call_once),
103            FnTrait::FnMut => Name::new_symbol_root(sym::call_mut),
104            FnTrait::Fn => Name::new_symbol_root(sym::call),
105            FnTrait::AsyncFnOnce => Name::new_symbol_root(sym::async_call_once),
106            FnTrait::AsyncFnMut => Name::new_symbol_root(sym::async_call_mut),
107            FnTrait::AsyncFn => Name::new_symbol_root(sym::async_call),
108        }
109    }
110
111    pub fn get_id(self, lang_items: &LangItems) -> Option<TraitId> {
112        match self {
113            FnTrait::FnOnce => lang_items.FnOnce,
114            FnTrait::FnMut => lang_items.FnMut,
115            FnTrait::Fn => lang_items.Fn,
116            FnTrait::AsyncFnOnce => lang_items.AsyncFnOnce,
117            FnTrait::AsyncFnMut => lang_items.AsyncFnMut,
118            FnTrait::AsyncFn => lang_items.AsyncFn,
119        }
120    }
121}
122
123/// This should not be used in `hir-ty`, only in `hir`.
124pub fn implements_trait_unique<'db>(
125    ty: Ty<'db>,
126    db: &'db dyn HirDatabase,
127    env: ParamEnvAndCrate<'db>,
128    trait_: TraitId,
129) -> bool {
130    implements_trait_unique_with_infcx(db, env, trait_, &mut |infcx| {
131        infcx.fill_rest_fresh_args(Span::Dummy, trait_.into(), [ty.into()])
132    })
133}
134
135/// This should not be used in `hir-ty`, only in `hir`.
136pub fn implements_trait_unique_with_args<'db>(
137    db: &'db dyn HirDatabase,
138    env: ParamEnvAndCrate<'db>,
139    trait_: TraitId,
140    args: GenericArgs<'db>,
141) -> bool {
142    implements_trait_unique_with_infcx(db, env, trait_, &mut |_| args)
143}
144
145pub fn implements_trait_unique_with_infcx<'db>(
146    db: &'db dyn HirDatabase,
147    env: ParamEnvAndCrate<'db>,
148    trait_: TraitId,
149    create_args: &mut dyn FnMut(&InferCtxt<'db>) -> GenericArgs<'db>,
150) -> bool {
151    let interner = DbInterner::new_with(db, env.krate);
152    // FIXME(next-solver): I believe this should be `PostAnalysis`.
153    let infcx = interner.infer_ctxt().build(TypingMode::non_body_analysis());
154
155    let args = create_args(&infcx);
156    let trait_ref = rustc_type_ir::TraitRef::new_from_args(interner, trait_.into(), args);
157    if trait_ref.self_ty().is_ty_error() {
158        return false;
159    }
160
161    let obligation = Obligation::new(interner, ObligationCause::dummy(), env.param_env, trait_ref);
162    infcx.predicate_must_hold_modulo_regions(&obligation)
163}
164
165#[derive(Debug, Clone, Copy, PartialEq, Eq)]
166pub enum WherePredicateEvaluation {
167    Holds,
168    NotProven,
169    HasErrors,
170    NoObligations,
171}
172
173/// This should not be used in `hir-ty`, only in `hir`.
174/// This is exposed to allow the IDE to evaluate arbitrary predicates.
175pub fn where_predicate_must_hold<'db>(
176    db: &'db dyn HirDatabase,
177    resolver: &Resolver<'db>,
178    store: &'db ExpressionStore,
179    def: ExpressionStoreOwnerId,
180    generic_def: GenericDefId,
181    env: ParamEnvAndCrate<'db>,
182    predicate: &WherePredicate,
183) -> WherePredicateEvaluation {
184    let interner = DbInterner::new_with(db, env.krate);
185    let infcx = interner.infer_ctxt().build(TypingMode::PostAnalysis);
186    let generics = OnceCell::<Generics<'db>>::new();
187    let mut ctx = TyLoweringContext::new(
188        db,
189        resolver,
190        store,
191        def,
192        generic_def,
193        &generics,
194        LifetimeElisionKind::Infer,
195        LifetimeLoweringMode::Bound,
196    )
197    .with_interning_mode(LoweringMode::Ide);
198    let clauses =
199        ctx.lower_where_predicate(predicate, false).map(|(clause, _)| clause).collect::<Vec<_>>();
200
201    if !ctx.diagnostics.is_empty()
202        || clauses.iter().any(|clause| clause.as_predicate().references_error())
203    {
204        return WherePredicateEvaluation::HasErrors;
205    }
206
207    if clauses.is_empty() {
208        return if ctx.unsized_types.is_empty() {
209            WherePredicateEvaluation::HasErrors
210        } else {
211            WherePredicateEvaluation::NoObligations
212        };
213    }
214
215    let result = infcx.probe(|snapshot| {
216        let mut ocx = ObligationCtxt::new(&infcx);
217        for clause in clauses {
218            let obligation = Obligation::new(
219                interner,
220                ObligationCause::dummy(),
221                env.param_env,
222                clause.as_predicate(),
223            );
224            ocx.register_obligation(obligation);
225        }
226
227        let mut result = EvaluationResult::EvaluatedToOk;
228        for error in ocx.evaluate_obligations_error_on_ambiguity() {
229            if error.is_true_error() {
230                return EvaluationResult::EvaluatedToErr;
231            }
232            result = result.max(EvaluationResult::EvaluatedToAmbig);
233        }
234        if infcx.opaque_types_added_in_snapshot(snapshot) {
235            result.max(EvaluationResult::EvaluatedToOkModuloOpaqueTypes)
236        } else if infcx.region_constraints_added_in_snapshot(snapshot) {
237            result.max(EvaluationResult::EvaluatedToOkModuloRegions)
238        } else {
239            result
240        }
241    });
242
243    if result.must_apply_modulo_regions() {
244        WherePredicateEvaluation::Holds
245    } else {
246        WherePredicateEvaluation::NotProven
247    }
248}
249
250pub fn is_inherent_impl_coherent(db: &dyn HirDatabase, def_map: &DefMap, impl_id: ImplId) -> bool {
251    let self_ty = db.impl_self_ty(impl_id).instantiate_identity().skip_norm_wip();
252    let self_ty = self_ty.kind();
253    let impl_allowed = match self_ty {
254        TyKind::Tuple(_)
255        | TyKind::FnDef(_, _)
256        | TyKind::Array(_, _)
257        | TyKind::Never
258        | TyKind::RawPtr(_, _)
259        | TyKind::Ref(_, _, _)
260        | TyKind::Slice(_)
261        | TyKind::Str
262        | TyKind::Bool
263        | TyKind::Char
264        | TyKind::Int(_)
265        | TyKind::Uint(_)
266        | TyKind::Float(_) => def_map.is_rustc_coherence_is_core(),
267
268        TyKind::Adt(adt_def, _) => adt_def.def_id().module(db).krate(db) == def_map.krate(),
269        TyKind::Dynamic(it, _) => it
270            .principal_def_id()
271            .is_some_and(|trait_id| trait_id.0.module(db).krate(db) == def_map.krate()),
272
273        _ => true,
274    };
275    impl_allowed || {
276        let rustc_has_incoherent_inherent_impls = match self_ty {
277            TyKind::Tuple(_)
278            | TyKind::FnDef(_, _)
279            | TyKind::Array(_, _)
280            | TyKind::Never
281            | TyKind::RawPtr(_, _)
282            | TyKind::Ref(_, _, _)
283            | TyKind::Slice(_)
284            | TyKind::Str
285            | TyKind::Bool
286            | TyKind::Char
287            | TyKind::Int(_)
288            | TyKind::Uint(_)
289            | TyKind::Float(_) => true,
290
291            TyKind::Adt(adt_def, _) => match adt_def.def_id() {
292                hir_def::AdtId::StructId(id) => StructSignature::of(db, id)
293                    .flags
294                    .contains(StructFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS),
295                hir_def::AdtId::UnionId(id) => UnionSignature::of(db, id)
296                    .flags
297                    .contains(StructFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS),
298                hir_def::AdtId::EnumId(it) => EnumSignature::of(db, it)
299                    .flags
300                    .contains(EnumFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS),
301            },
302            TyKind::Dynamic(it, _) => it.principal_def_id().is_some_and(|trait_id| {
303                TraitSignature::of(db, trait_id.0)
304                    .flags
305                    .contains(TraitFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS)
306            }),
307
308            _ => false,
309        };
310        let items = impl_id.impl_items(db);
311        rustc_has_incoherent_inherent_impls
312            && !items.items.is_empty()
313            && items.items.iter().all(|&(_, assoc)| match assoc {
314                AssocItemId::FunctionId(it) => FunctionSignature::of(db, it)
315                    .flags
316                    .contains(FnFlags::RUSTC_ALLOW_INCOHERENT_IMPL),
317                AssocItemId::ConstId(it) => ConstSignature::of(db, it)
318                    .flags
319                    .contains(ConstFlags::RUSTC_ALLOW_INCOHERENT_IMPL),
320                AssocItemId::TypeAliasId(it) => TypeAliasSignature::of(db, it)
321                    .flags
322                    .contains(TypeAliasFlags::RUSTC_ALLOW_INCOHERENT_IMPL),
323            })
324    }
325}
326
327/// Checks whether the impl satisfies the orphan rules.
328///
329/// Given `impl<P1..=Pn> Trait<T1..=Tn> for T0`, an `impl` is valid only if at least one of the following is true:
330/// - Trait is a local trait
331/// - All of
332///   - At least one of the types `T0..=Tn` must be a local type. Let `Ti` be the first such type.
333///   - No uncovered type parameters `P1..=Pn` may appear in `T0..Ti` (excluding `Ti`)
334pub fn check_orphan_rules<'db>(db: &'db dyn HirDatabase, impl_: ImplId) -> bool {
335    let Some(impl_trait) = db.impl_trait(impl_) else {
336        // not a trait impl
337        return true;
338    };
339
340    let local_crate = impl_.lookup(db).container.krate(db);
341    let is_local = |tgt_crate| tgt_crate == local_crate;
342
343    let trait_ref = impl_trait.instantiate_identity().skip_norm_wip();
344    let trait_id = trait_ref.def_id.0;
345    if is_local(trait_id.module(db).krate(db)) {
346        // trait to be implemented is local
347        return true;
348    }
349
350    let unwrap_fundamental = |mut ty: Ty<'db>| {
351        // Unwrap all layers of fundamental types with a loop.
352        loop {
353            match ty.kind() {
354                TyKind::Ref(_, referenced, _) => ty = referenced,
355                TyKind::Adt(adt_def, subs) => {
356                    let AdtId::StructId(s) = adt_def.def_id() else {
357                        break ty;
358                    };
359                    let struct_signature = StructSignature::of(db, s);
360                    if struct_signature.flags.contains(StructFlags::FUNDAMENTAL) {
361                        let next = subs.types().next();
362                        match next {
363                            Some(it) => ty = it,
364                            None => break ty,
365                        }
366                    } else {
367                        break ty;
368                    }
369                }
370                _ => break ty,
371            }
372        }
373    };
374    //   - At least one of the types `T0..=Tn` must be a local type. Let `Ti` be the first such type.
375
376    // FIXME: param coverage
377    //   - No uncovered type parameters `P1..=Pn` may appear in `T0..Ti` (excluding `Ti`)
378    let is_not_orphan = trait_ref.args.types().any(|ty| match unwrap_fundamental(ty).kind() {
379        TyKind::Adt(adt_def, _) => is_local(adt_def.def_id().module(db).krate(db)),
380        TyKind::Error(_) => true,
381        TyKind::Dynamic(it, _) => {
382            it.principal_def_id().is_some_and(|trait_id| is_local(trait_id.0.module(db).krate(db)))
383        }
384        _ => false,
385    });
386    #[allow(clippy::let_and_return)]
387    is_not_orphan
388}
hir_ty/traits.rs

hir_ty/
traits.rs
