hir_ty/
traits.rs

1//! Trait solving using Chalk.
2
3use core::fmt;
4
5use chalk_ir::{DebruijnIndex, GoalData, fold::TypeFoldable};
6use chalk_solve::rust_ir;
7
8use base_db::Crate;
9use hir_def::{BlockId, TraitId, lang_item::LangItem};
10use hir_expand::name::Name;
11use intern::sym;
12use rustc_next_trait_solver::solve::{HasChanged, SolverDelegateEvalExt};
13use rustc_type_ir::{
14    InferCtxtLike, TypingMode,
15    inherent::{SliceLike, Span as _},
16    solve::Certainty,
17};
18use span::Edition;
19use stdx::never;
20use triomphe::Arc;
21
22use crate::{
23    AliasEq, AliasTy, Canonical, DomainGoal, Goal, InEnvironment, Interner, ProjectionTy,
24    ProjectionTyExt, TraitRefExt, Ty, TyKind, TypeFlags, WhereClause,
25    db::HirDatabase,
26    infer::unify::InferenceTable,
27    next_solver::{
28        DbInterner, GenericArg, SolverContext, Span,
29        infer::{DbInternerInferExt, InferCtxt},
30        mapping::{ChalkToNextSolver, convert_canonical_args_for_result},
31        util::mini_canonicalize,
32    },
33    utils::UnevaluatedConstEvaluatorFolder,
34};
35
36/// A set of clauses that we assume to be true. E.g. if we are inside this function:
37/// ```rust
38/// fn foo<T: Default>(t: T) {}
39/// ```
40/// we assume that `T: Default`.
41#[derive(Debug, Clone, PartialEq, Eq, Hash)]
42pub struct TraitEnvironment {
43    pub krate: Crate,
44    pub block: Option<BlockId>,
45    // FIXME make this a BTreeMap
46    traits_from_clauses: Box<[(Ty, TraitId)]>,
47    pub env: chalk_ir::Environment<Interner>,
48}
49
50impl TraitEnvironment {
51    pub fn empty(krate: Crate) -> Arc<Self> {
52        Arc::new(TraitEnvironment {
53            krate,
54            block: None,
55            traits_from_clauses: Box::default(),
56            env: chalk_ir::Environment::new(Interner),
57        })
58    }
59
60    pub fn new(
61        krate: Crate,
62        block: Option<BlockId>,
63        traits_from_clauses: Box<[(Ty, TraitId)]>,
64        env: chalk_ir::Environment<Interner>,
65    ) -> Arc<Self> {
66        Arc::new(TraitEnvironment { krate, block, traits_from_clauses, env })
67    }
68
69    // pub fn with_block(self: &mut Arc<Self>, block: BlockId) {
70    pub fn with_block(this: &mut Arc<Self>, block: BlockId) {
71        Arc::make_mut(this).block = Some(block);
72    }
73
74    pub fn traits_in_scope_from_clauses(&self, ty: Ty) -> impl Iterator<Item = TraitId> + '_ {
75        self.traits_from_clauses
76            .iter()
77            .filter_map(move |(self_ty, trait_id)| (*self_ty == ty).then_some(*trait_id))
78    }
79}
80
81pub(crate) fn normalize_projection_query(
82    db: &dyn HirDatabase,
83    projection: ProjectionTy,
84    env: Arc<TraitEnvironment>,
85) -> Ty {
86    if projection.substitution.iter(Interner).any(|arg| {
87        arg.ty(Interner)
88            .is_some_and(|ty| ty.data(Interner).flags.intersects(TypeFlags::HAS_TY_INFER))
89    }) {
90        never!(
91            "Invoking `normalize_projection_query` with a projection type containing inference var"
92        );
93        return TyKind::Error.intern(Interner);
94    }
95
96    let mut table = InferenceTable::new(db, env);
97    let ty = table.normalize_projection_ty(projection);
98    table.resolve_completely(ty)
99}
100
101fn identity_subst(
102    binders: chalk_ir::CanonicalVarKinds<Interner>,
103) -> chalk_ir::Canonical<chalk_ir::Substitution<Interner>> {
104    let identity_subst = chalk_ir::Substitution::from_iter(
105        Interner,
106        binders.iter(Interner).enumerate().map(|(index, c)| {
107            let index_db = chalk_ir::BoundVar::new(DebruijnIndex::INNERMOST, index);
108            match &c.kind {
109                chalk_ir::VariableKind::Ty(_) => {
110                    chalk_ir::GenericArgData::Ty(TyKind::BoundVar(index_db).intern(Interner))
111                        .intern(Interner)
112                }
113                chalk_ir::VariableKind::Lifetime => chalk_ir::GenericArgData::Lifetime(
114                    chalk_ir::LifetimeData::BoundVar(index_db).intern(Interner),
115                )
116                .intern(Interner),
117                chalk_ir::VariableKind::Const(ty) => chalk_ir::GenericArgData::Const(
118                    chalk_ir::ConstData {
119                        ty: ty.clone(),
120                        value: chalk_ir::ConstValue::BoundVar(index_db),
121                    }
122                    .intern(Interner),
123                )
124                .intern(Interner),
125            }
126        }),
127    );
128    chalk_ir::Canonical { binders, value: identity_subst }
129}
130
131/// Solve a trait goal using Chalk.
132pub(crate) fn trait_solve_query(
133    db: &dyn HirDatabase,
134    krate: Crate,
135    block: Option<BlockId>,
136    goal: Canonical<InEnvironment<Goal>>,
137) -> NextTraitSolveResult {
138    let _p = tracing::info_span!("trait_solve_query", detail = ?match &goal.value.goal.data(Interner) {
139        GoalData::DomainGoal(DomainGoal::Holds(WhereClause::Implemented(it))) => db
140            .trait_signature(it.hir_trait_id())
141            .name
142            .display(db, Edition::LATEST)
143            .to_string(),
144        GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(_))) => "alias_eq".to_owned(),
145        _ => "??".to_owned(),
146    })
147    .entered();
148
149    if let GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(AliasEq {
150        alias: AliasTy::Projection(projection_ty),
151        ..
152    }))) = &goal.value.goal.data(Interner)
153        && let TyKind::BoundVar(_) = projection_ty.self_type_parameter(db).kind(Interner)
154    {
155        // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible
156        return NextTraitSolveResult::Uncertain(identity_subst(goal.binders.clone()));
157    }
158
159    // Chalk see `UnevaluatedConst` as a unique concrete value, but we see it as an alias for another const. So
160    // we should get rid of it when talking to chalk.
161    let goal = goal
162        .try_fold_with(&mut UnevaluatedConstEvaluatorFolder { db }, DebruijnIndex::INNERMOST)
163        .unwrap();
164
165    // We currently don't deal with universes (I think / hope they're not yet
166    // relevant for our use cases?)
167    next_trait_solve(db, krate, block, goal)
168}
169
170fn solve_nextsolver<'db>(
171    db: &'db dyn HirDatabase,
172    krate: Crate,
173    block: Option<BlockId>,
174    goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal<Interner>>>,
175) -> Result<
176    (HasChanged, Certainty, rustc_type_ir::Canonical<DbInterner<'db>, Vec<GenericArg<'db>>>),
177    rustc_type_ir::solve::NoSolution,
178> {
179    // FIXME: should use analysis_in_body, but that needs GenericDefId::Block
180    let context = SolverContext(
181        DbInterner::new_with(db, Some(krate), block)
182            .infer_ctxt()
183            .build(TypingMode::non_body_analysis()),
184    );
185
186    match goal.canonical.value.goal.data(Interner) {
187        // FIXME: args here should be...what? not empty
188        GoalData::All(goals) if goals.is_empty(Interner) => {
189            return Ok((HasChanged::No, Certainty::Yes, mini_canonicalize(context, vec![])));
190        }
191        _ => {}
192    }
193
194    let goal = goal.canonical.to_nextsolver(context.cx());
195    tracing::info!(?goal);
196
197    let (goal, var_values) = context.instantiate_canonical(&goal);
198    tracing::info!(?var_values);
199
200    let res = context.evaluate_root_goal(goal, Span::dummy(), None);
201
202    let vars =
203        var_values.var_values.iter().map(|g| context.0.resolve_vars_if_possible(g)).collect();
204    let canonical_var_values = mini_canonicalize(context, vars);
205
206    let res = res.map(|r| (r.has_changed, r.certainty, canonical_var_values));
207
208    tracing::debug!("solve_nextsolver({:?}) => {:?}", goal, res);
209
210    res
211}
212
213#[derive(Clone, Debug, PartialEq)]
214pub enum NextTraitSolveResult {
215    Certain(chalk_ir::Canonical<chalk_ir::ConstrainedSubst<Interner>>),
216    Uncertain(chalk_ir::Canonical<chalk_ir::Substitution<Interner>>),
217    NoSolution,
218}
219
220impl NextTraitSolveResult {
221    pub fn no_solution(&self) -> bool {
222        matches!(self, NextTraitSolveResult::NoSolution)
223    }
224
225    pub fn certain(&self) -> bool {
226        matches!(self, NextTraitSolveResult::Certain(..))
227    }
228
229    pub fn uncertain(&self) -> bool {
230        matches!(self, NextTraitSolveResult::Uncertain(..))
231    }
232}
233
234/// Solve a trait goal using Chalk.
235pub fn next_trait_solve(
236    db: &dyn HirDatabase,
237    krate: Crate,
238    block: Option<BlockId>,
239    goal: Canonical<InEnvironment<Goal>>,
240) -> NextTraitSolveResult {
241    let detail = match &goal.value.goal.data(Interner) {
242        GoalData::DomainGoal(DomainGoal::Holds(WhereClause::Implemented(it))) => {
243            db.trait_signature(it.hir_trait_id()).name.display(db, Edition::LATEST).to_string()
244        }
245        GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(_))) => "alias_eq".to_owned(),
246        _ => "??".to_owned(),
247    };
248    let _p = tracing::info_span!("next_trait_solve", ?detail).entered();
249    tracing::info!("next_trait_solve({:?})", goal.value.goal);
250
251    if let GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(AliasEq {
252        alias: AliasTy::Projection(projection_ty),
253        ..
254    }))) = &goal.value.goal.data(Interner)
255        && let TyKind::BoundVar(_) = projection_ty.self_type_parameter(db).kind(Interner)
256    {
257        // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible
258        // FIXME
259        return NextTraitSolveResult::Uncertain(identity_subst(goal.binders.clone()));
260    }
261
262    // Chalk see `UnevaluatedConst` as a unique concrete value, but we see it as an alias for another const. So
263    // we should get rid of it when talking to chalk.
264    let goal = goal
265        .try_fold_with(&mut UnevaluatedConstEvaluatorFolder { db }, DebruijnIndex::INNERMOST)
266        .unwrap();
267
268    // We currently don't deal with universes (I think / hope they're not yet
269    // relevant for our use cases?)
270    let u_canonical = chalk_ir::UCanonical { canonical: goal, universes: 1 };
271    tracing::info!(?u_canonical);
272
273    let next_solver_res = solve_nextsolver(db, krate, block, &u_canonical);
274
275    match next_solver_res {
276        Err(_) => NextTraitSolveResult::NoSolution,
277        Ok((_, Certainty::Yes, args)) => NextTraitSolveResult::Certain(
278            convert_canonical_args_for_result(DbInterner::new_with(db, Some(krate), block), args),
279        ),
280        Ok((_, Certainty::Maybe(_), args)) => {
281            let subst = convert_canonical_args_for_result(
282                DbInterner::new_with(db, Some(krate), block),
283                args,
284            );
285            NextTraitSolveResult::Uncertain(chalk_ir::Canonical {
286                binders: subst.binders,
287                value: subst.value.subst,
288            })
289        }
290    }
291}
292
293/// Solve a trait goal using Chalk.
294pub fn next_trait_solve_in_ctxt<'db, 'a>(
295    infer_ctxt: &'a InferCtxt<'db>,
296    goal: crate::next_solver::Goal<'db, crate::next_solver::Predicate<'db>>,
297) -> Result<(HasChanged, Certainty), rustc_type_ir::solve::NoSolution> {
298    tracing::info!(?goal);
299
300    let context = <&SolverContext<'db>>::from(infer_ctxt);
301
302    let res = context.evaluate_root_goal(goal, Span::dummy(), None);
303
304    let res = res.map(|r| (r.has_changed, r.certainty));
305
306    tracing::debug!("solve_nextsolver({:?}) => {:?}", goal, res);
307
308    res
309}
310
311#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
312pub enum FnTrait {
313    // Warning: Order is important. If something implements `x` it should also implement
314    // `y` if `y <= x`.
315    FnOnce,
316    FnMut,
317    Fn,
318
319    AsyncFnOnce,
320    AsyncFnMut,
321    AsyncFn,
322}
323
324impl fmt::Display for FnTrait {
325    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
326        match self {
327            FnTrait::FnOnce => write!(f, "FnOnce"),
328            FnTrait::FnMut => write!(f, "FnMut"),
329            FnTrait::Fn => write!(f, "Fn"),
330            FnTrait::AsyncFnOnce => write!(f, "AsyncFnOnce"),
331            FnTrait::AsyncFnMut => write!(f, "AsyncFnMut"),
332            FnTrait::AsyncFn => write!(f, "AsyncFn"),
333        }
334    }
335}
336
337impl FnTrait {
338    pub const fn function_name(&self) -> &'static str {
339        match self {
340            FnTrait::FnOnce => "call_once",
341            FnTrait::FnMut => "call_mut",
342            FnTrait::Fn => "call",
343            FnTrait::AsyncFnOnce => "async_call_once",
344            FnTrait::AsyncFnMut => "async_call_mut",
345            FnTrait::AsyncFn => "async_call",
346        }
347    }
348
349    const fn lang_item(self) -> LangItem {
350        match self {
351            FnTrait::FnOnce => LangItem::FnOnce,
352            FnTrait::FnMut => LangItem::FnMut,
353            FnTrait::Fn => LangItem::Fn,
354            FnTrait::AsyncFnOnce => LangItem::AsyncFnOnce,
355            FnTrait::AsyncFnMut => LangItem::AsyncFnMut,
356            FnTrait::AsyncFn => LangItem::AsyncFn,
357        }
358    }
359
360    pub const fn from_lang_item(lang_item: LangItem) -> Option<Self> {
361        match lang_item {
362            LangItem::FnOnce => Some(FnTrait::FnOnce),
363            LangItem::FnMut => Some(FnTrait::FnMut),
364            LangItem::Fn => Some(FnTrait::Fn),
365            LangItem::AsyncFnOnce => Some(FnTrait::AsyncFnOnce),
366            LangItem::AsyncFnMut => Some(FnTrait::AsyncFnMut),
367            LangItem::AsyncFn => Some(FnTrait::AsyncFn),
368            _ => None,
369        }
370    }
371
372    pub const fn to_chalk_ir(self) -> rust_ir::ClosureKind {
373        // Chalk doesn't support async fn traits.
374        match self {
375            FnTrait::AsyncFnOnce | FnTrait::FnOnce => rust_ir::ClosureKind::FnOnce,
376            FnTrait::AsyncFnMut | FnTrait::FnMut => rust_ir::ClosureKind::FnMut,
377            FnTrait::AsyncFn | FnTrait::Fn => rust_ir::ClosureKind::Fn,
378        }
379    }
380
381    pub fn method_name(self) -> Name {
382        match self {
383            FnTrait::FnOnce => Name::new_symbol_root(sym::call_once),
384            FnTrait::FnMut => Name::new_symbol_root(sym::call_mut),
385            FnTrait::Fn => Name::new_symbol_root(sym::call),
386            FnTrait::AsyncFnOnce => Name::new_symbol_root(sym::async_call_once),
387            FnTrait::AsyncFnMut => Name::new_symbol_root(sym::async_call_mut),
388            FnTrait::AsyncFn => Name::new_symbol_root(sym::async_call),
389        }
390    }
391
392    pub fn get_id(self, db: &dyn HirDatabase, krate: Crate) -> Option<TraitId> {
393        self.lang_item().resolve_trait(db, krate)
394    }
395
396    #[inline]
397    pub(crate) fn is_async(self) -> bool {
398        matches!(self, FnTrait::AsyncFn | FnTrait::AsyncFnMut | FnTrait::AsyncFnOnce)
399    }
400}
hir_ty/traits.rs

hir_ty/
traits.rs
