]>
Commit | Line | Data |
---|---|---|
064997fb FG |
1 | //! Unification and canonicalization logic. |
2 | ||
fe692bf9 | 3 | use std::{fmt, iter, mem}; |
064997fb FG |
4 | |
5 | use chalk_ir::{ | |
6 | cast::Cast, fold::TypeFoldable, interner::HasInterner, zip::Zip, CanonicalVarKind, FloatTy, | |
2b03887a | 7 | IntTy, TyVariableKind, UniverseIndex, |
064997fb FG |
8 | }; |
9 | use chalk_solve::infer::ParameterEnaVariableExt; | |
fe692bf9 | 10 | use either::Either; |
064997fb FG |
11 | use ena::unify::UnifyKey; |
12 | use hir_expand::name; | |
13 | use stdx::never; | |
fe692bf9 | 14 | use triomphe::Arc; |
064997fb FG |
15 | |
16 | use super::{InferOk, InferResult, InferenceContext, TypeError}; | |
17 | use crate::{ | |
fe692bf9 FG |
18 | consteval::unknown_const, db::HirDatabase, fold_tys_and_consts, static_lifetime, |
19 | to_chalk_trait_id, traits::FnTrait, AliasEq, AliasTy, BoundVar, Canonical, Const, ConstValue, | |
20 | DebruijnIndex, GenericArg, GenericArgData, Goal, Guidance, InEnvironment, InferenceVar, | |
21 | Interner, Lifetime, ParamKind, ProjectionTy, ProjectionTyExt, Scalar, Solution, Substitution, | |
22 | TraitEnvironment, Ty, TyBuilder, TyExt, TyKind, VariableKind, | |
064997fb FG |
23 | }; |
24 | ||
add651ee | 25 | impl InferenceContext<'_> { |
064997fb FG |
26 | pub(super) fn canonicalize<T: TypeFoldable<Interner> + HasInterner<Interner = Interner>>( |
27 | &mut self, | |
28 | t: T, | |
29 | ) -> Canonicalized<T> | |
30 | where | |
31 | T: HasInterner<Interner = Interner>, | |
32 | { | |
33 | self.table.canonicalize(t) | |
34 | } | |
35 | } | |
36 | ||
37 | #[derive(Debug, Clone)] | |
38 | pub(crate) struct Canonicalized<T> | |
39 | where | |
40 | T: HasInterner<Interner = Interner>, | |
41 | { | |
42 | pub(crate) value: Canonical<T>, | |
43 | free_vars: Vec<GenericArg>, | |
44 | } | |
45 | ||
46 | impl<T: HasInterner<Interner = Interner>> Canonicalized<T> { | |
47 | pub(super) fn apply_solution( | |
48 | &self, | |
49 | ctx: &mut InferenceTable<'_>, | |
50 | solution: Canonical<Substitution>, | |
51 | ) { | |
52 | // the solution may contain new variables, which we need to convert to new inference vars | |
53 | let new_vars = Substitution::from_iter( | |
54 | Interner, | |
55 | solution.binders.iter(Interner).map(|k| match &k.kind { | |
56 | VariableKind::Ty(TyVariableKind::General) => ctx.new_type_var().cast(Interner), | |
57 | VariableKind::Ty(TyVariableKind::Integer) => ctx.new_integer_var().cast(Interner), | |
58 | VariableKind::Ty(TyVariableKind::Float) => ctx.new_float_var().cast(Interner), | |
59 | // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere | |
60 | VariableKind::Lifetime => static_lifetime().cast(Interner), | |
61 | VariableKind::Const(ty) => ctx.new_const_var(ty.clone()).cast(Interner), | |
62 | }), | |
63 | ); | |
64 | for (i, v) in solution.value.iter(Interner).enumerate() { | |
65 | let var = self.free_vars[i].clone(); | |
66 | if let Some(ty) = v.ty(Interner) { | |
67 | // eagerly replace projections in the type; we may be getting types | |
68 | // e.g. from where clauses where this hasn't happened yet | |
69 | let ty = ctx.normalize_associated_types_in(new_vars.apply(ty.clone(), Interner)); | |
70 | ctx.unify(var.assert_ty_ref(Interner), &ty); | |
71 | } else { | |
72 | let _ = ctx.try_unify(&var, &new_vars.apply(v.clone(), Interner)); | |
73 | } | |
74 | } | |
75 | } | |
76 | } | |
77 | ||
78 | pub fn could_unify( | |
79 | db: &dyn HirDatabase, | |
80 | env: Arc<TraitEnvironment>, | |
81 | tys: &Canonical<(Ty, Ty)>, | |
82 | ) -> bool { | |
83 | unify(db, env, tys).is_some() | |
84 | } | |
85 | ||
86 | pub(crate) fn unify( | |
87 | db: &dyn HirDatabase, | |
88 | env: Arc<TraitEnvironment>, | |
89 | tys: &Canonical<(Ty, Ty)>, | |
90 | ) -> Option<Substitution> { | |
91 | let mut table = InferenceTable::new(db, env); | |
92 | let vars = Substitution::from_iter( | |
93 | Interner, | |
add651ee | 94 | tys.binders.iter(Interner).map(|it| match &it.kind { |
064997fb FG |
95 | chalk_ir::VariableKind::Ty(_) => { |
96 | GenericArgData::Ty(table.new_type_var()).intern(Interner) | |
97 | } | |
98 | chalk_ir::VariableKind::Lifetime => { | |
99 | GenericArgData::Ty(table.new_type_var()).intern(Interner) | |
100 | } // FIXME: maybe wrong? | |
101 | chalk_ir::VariableKind::Const(ty) => { | |
102 | GenericArgData::Const(table.new_const_var(ty.clone())).intern(Interner) | |
103 | } | |
104 | }), | |
105 | ); | |
106 | let ty1_with_vars = vars.apply(tys.value.0.clone(), Interner); | |
107 | let ty2_with_vars = vars.apply(tys.value.1.clone(), Interner); | |
108 | if !table.unify(&ty1_with_vars, &ty2_with_vars) { | |
109 | return None; | |
110 | } | |
111 | // default any type vars that weren't unified back to their original bound vars | |
112 | // (kind of hacky) | |
113 | let find_var = |iv| { | |
114 | vars.iter(Interner).position(|v| match v.interned() { | |
115 | chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(Interner), | |
116 | chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(Interner), | |
117 | chalk_ir::GenericArgData::Const(c) => c.inference_var(Interner), | |
118 | } == Some(iv)) | |
119 | }; | |
120 | let fallback = |iv, kind, default, binder| match kind { | |
121 | chalk_ir::VariableKind::Ty(_ty_kind) => find_var(iv) | |
122 | .map_or(default, |i| BoundVar::new(binder, i).to_ty(Interner).cast(Interner)), | |
123 | chalk_ir::VariableKind::Lifetime => find_var(iv) | |
124 | .map_or(default, |i| BoundVar::new(binder, i).to_lifetime(Interner).cast(Interner)), | |
125 | chalk_ir::VariableKind::Const(ty) => find_var(iv) | |
126 | .map_or(default, |i| BoundVar::new(binder, i).to_const(Interner, ty).cast(Interner)), | |
127 | }; | |
128 | Some(Substitution::from_iter( | |
129 | Interner, | |
130 | vars.iter(Interner).map(|v| table.resolve_with_fallback(v.clone(), &fallback)), | |
131 | )) | |
132 | } | |
133 | ||
9c376795 | 134 | bitflags::bitflags! { |
fe692bf9 | 135 | #[derive(Default, Clone, Copy)] |
9c376795 FG |
136 | pub(crate) struct TypeVariableFlags: u8 { |
137 | const DIVERGING = 1 << 0; | |
138 | const INTEGER = 1 << 1; | |
139 | const FLOAT = 1 << 2; | |
140 | } | |
064997fb FG |
141 | } |
142 | ||
143 | type ChalkInferenceTable = chalk_solve::infer::InferenceTable<Interner>; | |
144 | ||
145 | #[derive(Clone)] | |
146 | pub(crate) struct InferenceTable<'a> { | |
147 | pub(crate) db: &'a dyn HirDatabase, | |
148 | pub(crate) trait_env: Arc<TraitEnvironment>, | |
149 | var_unification_table: ChalkInferenceTable, | |
9c376795 | 150 | type_variable_table: Vec<TypeVariableFlags>, |
064997fb FG |
151 | pending_obligations: Vec<Canonicalized<InEnvironment<Goal>>>, |
152 | } | |
153 | ||
154 | pub(crate) struct InferenceTableSnapshot { | |
155 | var_table_snapshot: chalk_solve::infer::InferenceSnapshot<Interner>, | |
156 | pending_obligations: Vec<Canonicalized<InEnvironment<Goal>>>, | |
9c376795 | 157 | type_variable_table_snapshot: Vec<TypeVariableFlags>, |
064997fb FG |
158 | } |
159 | ||
160 | impl<'a> InferenceTable<'a> { | |
161 | pub(crate) fn new(db: &'a dyn HirDatabase, trait_env: Arc<TraitEnvironment>) -> Self { | |
162 | InferenceTable { | |
163 | db, | |
164 | trait_env, | |
165 | var_unification_table: ChalkInferenceTable::new(), | |
166 | type_variable_table: Vec::new(), | |
167 | pending_obligations: Vec::new(), | |
168 | } | |
169 | } | |
170 | ||
171 | /// Chalk doesn't know about the `diverging` flag, so when it unifies two | |
172 | /// type variables of which one is diverging, the chosen root might not be | |
173 | /// diverging and we have no way of marking it as such at that time. This | |
174 | /// function goes through all type variables and make sure their root is | |
175 | /// marked as diverging if necessary, so that resolving them gives the right | |
176 | /// result. | |
177 | pub(super) fn propagate_diverging_flag(&mut self) { | |
178 | for i in 0..self.type_variable_table.len() { | |
9c376795 | 179 | if !self.type_variable_table[i].contains(TypeVariableFlags::DIVERGING) { |
064997fb FG |
180 | continue; |
181 | } | |
182 | let v = InferenceVar::from(i as u32); | |
183 | let root = self.var_unification_table.inference_var_root(v); | |
184 | if let Some(data) = self.type_variable_table.get_mut(root.index() as usize) { | |
9c376795 | 185 | *data |= TypeVariableFlags::DIVERGING; |
064997fb FG |
186 | } |
187 | } | |
188 | } | |
189 | ||
190 | pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) { | |
9c376795 | 191 | self.type_variable_table[iv.index() as usize].set(TypeVariableFlags::DIVERGING, diverging); |
064997fb FG |
192 | } |
193 | ||
194 | fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty { | |
195 | match kind { | |
196 | _ if self | |
197 | .type_variable_table | |
198 | .get(iv.index() as usize) | |
9c376795 | 199 | .map_or(false, |data| data.contains(TypeVariableFlags::DIVERGING)) => |
064997fb FG |
200 | { |
201 | TyKind::Never | |
202 | } | |
203 | TyVariableKind::General => TyKind::Error, | |
204 | TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)), | |
205 | TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)), | |
206 | } | |
207 | .intern(Interner) | |
208 | } | |
209 | ||
210 | pub(crate) fn canonicalize<T: TypeFoldable<Interner> + HasInterner<Interner = Interner>>( | |
211 | &mut self, | |
212 | t: T, | |
213 | ) -> Canonicalized<T> | |
214 | where | |
215 | T: HasInterner<Interner = Interner>, | |
216 | { | |
217 | // try to resolve obligations before canonicalizing, since this might | |
218 | // result in new knowledge about variables | |
219 | self.resolve_obligations_as_possible(); | |
220 | let result = self.var_unification_table.canonicalize(Interner, t); | |
221 | let free_vars = result | |
222 | .free_vars | |
223 | .into_iter() | |
224 | .map(|free_var| free_var.to_generic_arg(Interner)) | |
225 | .collect(); | |
226 | Canonicalized { value: result.quantified, free_vars } | |
227 | } | |
228 | ||
229 | /// Recurses through the given type, normalizing associated types mentioned | |
230 | /// in it by replacing them by type variables and registering obligations to | |
231 | /// resolve later. This should be done once for every type we get from some | |
232 | /// type annotation (e.g. from a let type annotation, field type or function | |
233 | /// call). `make_ty` handles this already, but e.g. for field types we need | |
234 | /// to do it as well. | |
fe692bf9 FG |
235 | pub(crate) fn normalize_associated_types_in<T>(&mut self, ty: T) -> T |
236 | where | |
237 | T: HasInterner<Interner = Interner> + TypeFoldable<Interner>, | |
238 | { | |
239 | fold_tys_and_consts( | |
064997fb | 240 | ty, |
fe692bf9 FG |
241 | |e, _| match e { |
242 | Either::Left(ty) => Either::Left(match ty.kind(Interner) { | |
243 | TyKind::Alias(AliasTy::Projection(proj_ty)) => { | |
244 | self.normalize_projection_ty(proj_ty.clone()) | |
245 | } | |
246 | _ => ty, | |
247 | }), | |
248 | Either::Right(c) => Either::Right(match &c.data(Interner).value { | |
249 | chalk_ir::ConstValue::Concrete(cc) => match &cc.interned { | |
250 | crate::ConstScalar::UnevaluatedConst(c_id, subst) => { | |
251 | // FIXME: Ideally here we should do everything that we do with type alias, i.e. adding a variable | |
252 | // and registering an obligation. But it needs chalk support, so we handle the most basic | |
253 | // case (a non associated const without generic parameters) manually. | |
254 | if subst.len(Interner) == 0 { | |
add651ee FG |
255 | if let Ok(eval) = |
256 | self.db.const_eval((*c_id).into(), subst.clone(), None) | |
fe692bf9 FG |
257 | { |
258 | eval | |
259 | } else { | |
260 | unknown_const(c.data(Interner).ty.clone()) | |
261 | } | |
262 | } else { | |
263 | unknown_const(c.data(Interner).ty.clone()) | |
264 | } | |
265 | } | |
266 | _ => c, | |
267 | }, | |
268 | _ => c, | |
269 | }), | |
064997fb FG |
270 | }, |
271 | DebruijnIndex::INNERMOST, | |
272 | ) | |
273 | } | |
274 | ||
275 | pub(crate) fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty { | |
276 | let var = self.new_type_var(); | |
277 | let alias_eq = AliasEq { alias: AliasTy::Projection(proj_ty), ty: var.clone() }; | |
278 | let obligation = alias_eq.cast(Interner); | |
279 | self.register_obligation(obligation); | |
280 | var | |
281 | } | |
282 | ||
283 | fn extend_type_variable_table(&mut self, to_index: usize) { | |
9c376795 FG |
284 | let count = to_index - self.type_variable_table.len() + 1; |
285 | self.type_variable_table.extend(iter::repeat(TypeVariableFlags::default()).take(count)); | |
064997fb FG |
286 | } |
287 | ||
288 | fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty { | |
289 | let var = self.var_unification_table.new_variable(UniverseIndex::ROOT); | |
290 | // Chalk might have created some type variables for its own purposes that we don't know about... | |
291 | self.extend_type_variable_table(var.index() as usize); | |
292 | assert_eq!(var.index() as usize, self.type_variable_table.len() - 1); | |
9c376795 FG |
293 | let flags = self.type_variable_table.get_mut(var.index() as usize).unwrap(); |
294 | if diverging { | |
295 | *flags |= TypeVariableFlags::DIVERGING; | |
296 | } | |
297 | if matches!(kind, TyVariableKind::Integer) { | |
298 | *flags |= TypeVariableFlags::INTEGER; | |
299 | } else if matches!(kind, TyVariableKind::Float) { | |
300 | *flags |= TypeVariableFlags::FLOAT; | |
301 | } | |
064997fb FG |
302 | var.to_ty_with_kind(Interner, kind) |
303 | } | |
304 | ||
305 | pub(crate) fn new_type_var(&mut self) -> Ty { | |
306 | self.new_var(TyVariableKind::General, false) | |
307 | } | |
308 | ||
309 | pub(crate) fn new_integer_var(&mut self) -> Ty { | |
310 | self.new_var(TyVariableKind::Integer, false) | |
311 | } | |
312 | ||
313 | pub(crate) fn new_float_var(&mut self) -> Ty { | |
314 | self.new_var(TyVariableKind::Float, false) | |
315 | } | |
316 | ||
317 | pub(crate) fn new_maybe_never_var(&mut self) -> Ty { | |
318 | self.new_var(TyVariableKind::General, true) | |
319 | } | |
320 | ||
321 | pub(crate) fn new_const_var(&mut self, ty: Ty) -> Const { | |
322 | let var = self.var_unification_table.new_variable(UniverseIndex::ROOT); | |
323 | var.to_const(Interner, ty) | |
324 | } | |
325 | ||
326 | pub(crate) fn new_lifetime_var(&mut self) -> Lifetime { | |
327 | let var = self.var_unification_table.new_variable(UniverseIndex::ROOT); | |
328 | var.to_lifetime(Interner) | |
329 | } | |
330 | ||
331 | pub(crate) fn resolve_with_fallback<T>( | |
332 | &mut self, | |
333 | t: T, | |
334 | fallback: &dyn Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, | |
335 | ) -> T | |
336 | where | |
337 | T: HasInterner<Interner = Interner> + TypeFoldable<Interner>, | |
338 | { | |
339 | self.resolve_with_fallback_inner(&mut Vec::new(), t, &fallback) | |
340 | } | |
341 | ||
342 | pub(crate) fn fresh_subst(&mut self, binders: &[CanonicalVarKind<Interner>]) -> Substitution { | |
343 | Substitution::from_iter( | |
344 | Interner, | |
345 | binders.iter().map(|kind| { | |
346 | let param_infer_var = | |
347 | kind.map_ref(|&ui| self.var_unification_table.new_variable(ui)); | |
348 | param_infer_var.to_generic_arg(Interner) | |
349 | }), | |
350 | ) | |
351 | } | |
352 | ||
353 | pub(crate) fn instantiate_canonical<T>(&mut self, canonical: Canonical<T>) -> T | |
354 | where | |
355 | T: HasInterner<Interner = Interner> + TypeFoldable<Interner> + std::fmt::Debug, | |
356 | { | |
357 | let subst = self.fresh_subst(canonical.binders.as_slice(Interner)); | |
358 | subst.apply(canonical.value, Interner) | |
359 | } | |
360 | ||
361 | fn resolve_with_fallback_inner<T>( | |
362 | &mut self, | |
363 | var_stack: &mut Vec<InferenceVar>, | |
364 | t: T, | |
365 | fallback: &dyn Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, | |
366 | ) -> T | |
367 | where | |
368 | T: HasInterner<Interner = Interner> + TypeFoldable<Interner>, | |
369 | { | |
370 | t.fold_with( | |
371 | &mut resolve::Resolver { table: self, var_stack, fallback }, | |
372 | DebruijnIndex::INNERMOST, | |
373 | ) | |
064997fb FG |
374 | } |
375 | ||
376 | pub(crate) fn resolve_completely<T>(&mut self, t: T) -> T | |
377 | where | |
378 | T: HasInterner<Interner = Interner> + TypeFoldable<Interner>, | |
379 | { | |
380 | self.resolve_with_fallback(t, &|_, _, d, _| d) | |
381 | } | |
382 | ||
9c376795 FG |
383 | /// Apply a fallback to unresolved scalar types. Integer type variables and float type |
384 | /// variables are replaced with i32 and f64, respectively. | |
385 | /// | |
386 | /// This method is only intended to be called just before returning inference results (i.e. in | |
387 | /// `InferenceContext::resolve_all()`). | |
388 | /// | |
389 | /// FIXME: This method currently doesn't apply fallback to unconstrained general type variables | |
390 | /// whereas rustc replaces them with `()` or `!`. | |
391 | pub(super) fn fallback_if_possible(&mut self) { | |
392 | let int_fallback = TyKind::Scalar(Scalar::Int(IntTy::I32)).intern(Interner); | |
393 | let float_fallback = TyKind::Scalar(Scalar::Float(FloatTy::F64)).intern(Interner); | |
394 | ||
395 | let scalar_vars: Vec<_> = self | |
396 | .type_variable_table | |
397 | .iter() | |
398 | .enumerate() | |
399 | .filter_map(|(index, flags)| { | |
400 | let kind = if flags.contains(TypeVariableFlags::INTEGER) { | |
401 | TyVariableKind::Integer | |
402 | } else if flags.contains(TypeVariableFlags::FLOAT) { | |
403 | TyVariableKind::Float | |
404 | } else { | |
405 | return None; | |
406 | }; | |
407 | ||
408 | // FIXME: This is not really the nicest way to get `InferenceVar`s. Can we get them | |
409 | // without directly constructing them from `index`? | |
410 | let var = InferenceVar::from(index as u32).to_ty(Interner, kind); | |
411 | Some(var) | |
412 | }) | |
413 | .collect(); | |
414 | ||
415 | for var in scalar_vars { | |
416 | let maybe_resolved = self.resolve_ty_shallow(&var); | |
417 | if let TyKind::InferenceVar(_, kind) = maybe_resolved.kind(Interner) { | |
418 | let fallback = match kind { | |
419 | TyVariableKind::Integer => &int_fallback, | |
420 | TyVariableKind::Float => &float_fallback, | |
421 | TyVariableKind::General => unreachable!(), | |
422 | }; | |
423 | self.unify(&var, fallback); | |
424 | } | |
425 | } | |
426 | } | |
427 | ||
487cf647 FG |
428 | /// Unify two relatable values (e.g. `Ty`) and register new trait goals that arise from that. |
429 | pub(crate) fn unify<T: ?Sized + Zip<Interner>>(&mut self, ty1: &T, ty2: &T) -> bool { | |
064997fb FG |
430 | let result = match self.try_unify(ty1, ty2) { |
431 | Ok(r) => r, | |
432 | Err(_) => return false, | |
433 | }; | |
434 | self.register_infer_ok(result); | |
435 | true | |
436 | } | |
437 | ||
487cf647 | 438 | /// Unify two relatable values (e.g. `Ty`) and return new trait goals arising from it, so the |
064997fb | 439 | /// caller needs to deal with them. |
487cf647 FG |
440 | pub(crate) fn try_unify<T: ?Sized + Zip<Interner>>( |
441 | &mut self, | |
442 | t1: &T, | |
443 | t2: &T, | |
444 | ) -> InferResult<()> { | |
064997fb FG |
445 | match self.var_unification_table.relate( |
446 | Interner, | |
447 | &self.db, | |
448 | &self.trait_env.env, | |
449 | chalk_ir::Variance::Invariant, | |
450 | t1, | |
451 | t2, | |
452 | ) { | |
453 | Ok(result) => Ok(InferOk { goals: result.goals, value: () }), | |
454 | Err(chalk_ir::NoSolution) => Err(TypeError), | |
455 | } | |
456 | } | |
457 | ||
458 | /// If `ty` is a type variable with known type, returns that type; | |
459 | /// otherwise, return ty. | |
460 | pub(crate) fn resolve_ty_shallow(&mut self, ty: &Ty) -> Ty { | |
461 | self.resolve_obligations_as_possible(); | |
462 | self.var_unification_table.normalize_ty_shallow(Interner, ty).unwrap_or_else(|| ty.clone()) | |
463 | } | |
464 | ||
465 | pub(crate) fn snapshot(&mut self) -> InferenceTableSnapshot { | |
466 | let var_table_snapshot = self.var_unification_table.snapshot(); | |
467 | let type_variable_table_snapshot = self.type_variable_table.clone(); | |
468 | let pending_obligations = self.pending_obligations.clone(); | |
469 | InferenceTableSnapshot { | |
470 | var_table_snapshot, | |
471 | pending_obligations, | |
472 | type_variable_table_snapshot, | |
473 | } | |
474 | } | |
475 | ||
476 | pub(crate) fn rollback_to(&mut self, snapshot: InferenceTableSnapshot) { | |
477 | self.var_unification_table.rollback_to(snapshot.var_table_snapshot); | |
478 | self.type_variable_table = snapshot.type_variable_table_snapshot; | |
479 | self.pending_obligations = snapshot.pending_obligations; | |
480 | } | |
481 | ||
482 | pub(crate) fn run_in_snapshot<T>(&mut self, f: impl FnOnce(&mut InferenceTable<'_>) -> T) -> T { | |
483 | let snapshot = self.snapshot(); | |
484 | let result = f(self); | |
485 | self.rollback_to(snapshot); | |
486 | result | |
487 | } | |
488 | ||
489 | /// Checks an obligation without registering it. Useful mostly to check | |
490 | /// whether a trait *might* be implemented before deciding to 'lock in' the | |
491 | /// choice (during e.g. method resolution or deref). | |
492 | pub(crate) fn try_obligation(&mut self, goal: Goal) -> Option<Solution> { | |
493 | let in_env = InEnvironment::new(&self.trait_env.env, goal); | |
494 | let canonicalized = self.canonicalize(in_env); | |
fe692bf9 FG |
495 | let solution = |
496 | self.db.trait_solve(self.trait_env.krate, self.trait_env.block, canonicalized.value); | |
064997fb FG |
497 | solution |
498 | } | |
499 | ||
500 | pub(crate) fn register_obligation(&mut self, goal: Goal) { | |
501 | let in_env = InEnvironment::new(&self.trait_env.env, goal); | |
502 | self.register_obligation_in_env(in_env) | |
503 | } | |
504 | ||
505 | fn register_obligation_in_env(&mut self, goal: InEnvironment<Goal>) { | |
506 | let canonicalized = self.canonicalize(goal); | |
507 | if !self.try_resolve_obligation(&canonicalized) { | |
508 | self.pending_obligations.push(canonicalized); | |
509 | } | |
510 | } | |
511 | ||
512 | pub(crate) fn register_infer_ok<T>(&mut self, infer_ok: InferOk<T>) { | |
513 | infer_ok.goals.into_iter().for_each(|goal| self.register_obligation_in_env(goal)); | |
514 | } | |
515 | ||
516 | pub(crate) fn resolve_obligations_as_possible(&mut self) { | |
517 | let _span = profile::span("resolve_obligations_as_possible"); | |
518 | let mut changed = true; | |
519 | let mut obligations = Vec::new(); | |
520 | while changed { | |
521 | changed = false; | |
522 | mem::swap(&mut self.pending_obligations, &mut obligations); | |
523 | for canonicalized in obligations.drain(..) { | |
524 | if !self.check_changed(&canonicalized) { | |
525 | self.pending_obligations.push(canonicalized); | |
526 | continue; | |
527 | } | |
528 | changed = true; | |
529 | let uncanonical = chalk_ir::Substitute::apply( | |
530 | &canonicalized.free_vars, | |
531 | canonicalized.value.value, | |
532 | Interner, | |
533 | ); | |
534 | self.register_obligation_in_env(uncanonical); | |
535 | } | |
536 | } | |
537 | } | |
538 | ||
539 | pub(crate) fn fudge_inference<T: TypeFoldable<Interner>>( | |
540 | &mut self, | |
541 | f: impl FnOnce(&mut Self) -> T, | |
542 | ) -> T { | |
543 | use chalk_ir::fold::TypeFolder; | |
2b03887a FG |
544 | |
545 | #[derive(chalk_derive::FallibleTypeFolder)] | |
546 | #[has_interner(Interner)] | |
064997fb FG |
547 | struct VarFudger<'a, 'b> { |
548 | table: &'a mut InferenceTable<'b>, | |
549 | highest_known_var: InferenceVar, | |
550 | } | |
add651ee | 551 | impl TypeFolder<Interner> for VarFudger<'_, '_> { |
064997fb FG |
552 | fn as_dyn(&mut self) -> &mut dyn TypeFolder<Interner, Error = Self::Error> { |
553 | self | |
554 | } | |
555 | ||
556 | fn interner(&self) -> Interner { | |
557 | Interner | |
558 | } | |
559 | ||
560 | fn fold_inference_ty( | |
561 | &mut self, | |
562 | var: chalk_ir::InferenceVar, | |
563 | kind: TyVariableKind, | |
564 | _outer_binder: chalk_ir::DebruijnIndex, | |
2b03887a FG |
565 | ) -> chalk_ir::Ty<Interner> { |
566 | if var < self.highest_known_var { | |
064997fb FG |
567 | var.to_ty(Interner, kind) |
568 | } else { | |
569 | self.table.new_type_var() | |
2b03887a | 570 | } |
064997fb FG |
571 | } |
572 | ||
573 | fn fold_inference_lifetime( | |
574 | &mut self, | |
575 | var: chalk_ir::InferenceVar, | |
576 | _outer_binder: chalk_ir::DebruijnIndex, | |
2b03887a FG |
577 | ) -> chalk_ir::Lifetime<Interner> { |
578 | if var < self.highest_known_var { | |
064997fb FG |
579 | var.to_lifetime(Interner) |
580 | } else { | |
581 | self.table.new_lifetime_var() | |
2b03887a | 582 | } |
064997fb FG |
583 | } |
584 | ||
585 | fn fold_inference_const( | |
586 | &mut self, | |
587 | ty: chalk_ir::Ty<Interner>, | |
588 | var: chalk_ir::InferenceVar, | |
589 | _outer_binder: chalk_ir::DebruijnIndex, | |
2b03887a FG |
590 | ) -> chalk_ir::Const<Interner> { |
591 | if var < self.highest_known_var { | |
064997fb FG |
592 | var.to_const(Interner, ty) |
593 | } else { | |
594 | self.table.new_const_var(ty) | |
2b03887a | 595 | } |
064997fb FG |
596 | } |
597 | } | |
598 | ||
599 | let snapshot = self.snapshot(); | |
600 | let highest_known_var = self.new_type_var().inference_var(Interner).expect("inference_var"); | |
601 | let result = f(self); | |
602 | self.rollback_to(snapshot); | |
603 | result | |
604 | .fold_with(&mut VarFudger { table: self, highest_known_var }, DebruijnIndex::INNERMOST) | |
064997fb FG |
605 | } |
606 | ||
607 | /// This checks whether any of the free variables in the `canonicalized` | |
608 | /// have changed (either been unified with another variable, or with a | |
609 | /// value). If this is not the case, we don't need to try to solve the goal | |
610 | /// again -- it'll give the same result as last time. | |
611 | fn check_changed(&mut self, canonicalized: &Canonicalized<InEnvironment<Goal>>) -> bool { | |
612 | canonicalized.free_vars.iter().any(|var| { | |
613 | let iv = match var.data(Interner) { | |
614 | chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(Interner), | |
615 | chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(Interner), | |
616 | chalk_ir::GenericArgData::Const(c) => c.inference_var(Interner), | |
617 | } | |
618 | .expect("free var is not inference var"); | |
619 | if self.var_unification_table.probe_var(iv).is_some() { | |
620 | return true; | |
621 | } | |
622 | let root = self.var_unification_table.inference_var_root(iv); | |
623 | iv != root | |
624 | }) | |
625 | } | |
626 | ||
627 | fn try_resolve_obligation( | |
628 | &mut self, | |
629 | canonicalized: &Canonicalized<InEnvironment<Goal>>, | |
630 | ) -> bool { | |
fe692bf9 FG |
631 | let solution = self.db.trait_solve( |
632 | self.trait_env.krate, | |
633 | self.trait_env.block, | |
634 | canonicalized.value.clone(), | |
635 | ); | |
064997fb FG |
636 | |
637 | match solution { | |
638 | Some(Solution::Unique(canonical_subst)) => { | |
639 | canonicalized.apply_solution( | |
640 | self, | |
641 | Canonical { | |
642 | binders: canonical_subst.binders, | |
643 | // FIXME: handle constraints | |
644 | value: canonical_subst.value.subst, | |
645 | }, | |
646 | ); | |
647 | true | |
648 | } | |
649 | Some(Solution::Ambig(Guidance::Definite(substs))) => { | |
650 | canonicalized.apply_solution(self, substs); | |
651 | false | |
652 | } | |
653 | Some(_) => { | |
654 | // FIXME use this when trying to resolve everything at the end | |
655 | false | |
656 | } | |
657 | None => { | |
658 | // FIXME obligation cannot be fulfilled => diagnostic | |
659 | true | |
660 | } | |
661 | } | |
662 | } | |
663 | ||
9ffffee4 FG |
664 | pub(crate) fn callable_sig( |
665 | &mut self, | |
666 | ty: &Ty, | |
667 | num_args: usize, | |
fe692bf9 | 668 | ) -> Option<(Option<FnTrait>, Vec<Ty>, Ty)> { |
064997fb | 669 | match ty.callable_sig(self.db) { |
9ffffee4 | 670 | Some(sig) => Some((None, sig.params().to_vec(), sig.ret().clone())), |
fe692bf9 FG |
671 | None => { |
672 | let (f, args_ty, return_ty) = self.callable_sig_from_fn_trait(ty, num_args)?; | |
673 | Some((Some(f), args_ty, return_ty)) | |
674 | } | |
064997fb FG |
675 | } |
676 | } | |
677 | ||
9ffffee4 FG |
678 | fn callable_sig_from_fn_trait( |
679 | &mut self, | |
680 | ty: &Ty, | |
681 | num_args: usize, | |
fe692bf9 | 682 | ) -> Option<(FnTrait, Vec<Ty>, Ty)> { |
064997fb FG |
683 | let krate = self.trait_env.krate; |
684 | let fn_once_trait = FnTrait::FnOnce.get_id(self.db, krate)?; | |
9ffffee4 FG |
685 | let trait_data = self.db.trait_data(fn_once_trait); |
686 | let output_assoc_type = trait_data.associated_type_by_name(&name![Output])?; | |
064997fb FG |
687 | |
688 | let mut arg_tys = vec![]; | |
689 | let arg_ty = TyBuilder::tuple(num_args) | |
add651ee FG |
690 | .fill(|it| { |
691 | let arg = match it { | |
064997fb FG |
692 | ParamKind::Type => self.new_type_var(), |
693 | ParamKind::Const(ty) => { | |
694 | never!("Tuple with const parameter"); | |
695 | return GenericArgData::Const(self.new_const_var(ty.clone())) | |
696 | .intern(Interner); | |
697 | } | |
698 | }; | |
699 | arg_tys.push(arg.clone()); | |
700 | GenericArgData::Ty(arg).intern(Interner) | |
701 | }) | |
702 | .build(); | |
703 | ||
704 | let projection = { | |
2b03887a | 705 | let b = TyBuilder::subst_for_def(self.db, fn_once_trait, None); |
064997fb FG |
706 | if b.remaining() != 2 { |
707 | return None; | |
708 | } | |
2b03887a FG |
709 | let fn_once_subst = b.push(ty.clone()).push(arg_ty).build(); |
710 | ||
711 | TyBuilder::assoc_type_projection(self.db, output_assoc_type, Some(fn_once_subst)) | |
712 | .build() | |
064997fb FG |
713 | }; |
714 | ||
715 | let trait_env = self.trait_env.env.clone(); | |
fe692bf9 | 716 | let mut trait_ref = projection.trait_ref(self.db); |
064997fb | 717 | let obligation = InEnvironment { |
fe692bf9 FG |
718 | goal: trait_ref.clone().cast(Interner), |
719 | environment: trait_env.clone(), | |
064997fb FG |
720 | }; |
721 | let canonical = self.canonicalize(obligation.clone()); | |
fe692bf9 FG |
722 | if self |
723 | .db | |
724 | .trait_solve(krate, self.trait_env.block, canonical.value.cast(Interner)) | |
725 | .is_some() | |
726 | { | |
064997fb FG |
727 | self.register_obligation(obligation.goal); |
728 | let return_ty = self.normalize_projection_ty(projection); | |
fe692bf9 FG |
729 | for fn_x in [FnTrait::Fn, FnTrait::FnMut, FnTrait::FnOnce] { |
730 | let fn_x_trait = fn_x.get_id(self.db, krate)?; | |
731 | trait_ref.trait_id = to_chalk_trait_id(fn_x_trait); | |
732 | let obligation: chalk_ir::InEnvironment<chalk_ir::Goal<Interner>> = InEnvironment { | |
733 | goal: trait_ref.clone().cast(Interner), | |
734 | environment: trait_env.clone(), | |
735 | }; | |
736 | let canonical = self.canonicalize(obligation.clone()); | |
737 | if self | |
738 | .db | |
739 | .trait_solve(krate, self.trait_env.block, canonical.value.cast(Interner)) | |
740 | .is_some() | |
741 | { | |
742 | return Some((fn_x, arg_tys, return_ty)); | |
743 | } | |
744 | } | |
745 | unreachable!("It should at least implement FnOnce at this point"); | |
064997fb FG |
746 | } else { |
747 | None | |
748 | } | |
749 | } | |
fe692bf9 FG |
750 | |
751 | pub(super) fn insert_type_vars<T>(&mut self, ty: T) -> T | |
752 | where | |
753 | T: HasInterner<Interner = Interner> + TypeFoldable<Interner>, | |
754 | { | |
755 | fold_tys_and_consts( | |
756 | ty, | |
add651ee | 757 | |it, _| match it { |
fe692bf9 FG |
758 | Either::Left(ty) => Either::Left(self.insert_type_vars_shallow(ty)), |
759 | Either::Right(c) => Either::Right(self.insert_const_vars_shallow(c)), | |
760 | }, | |
761 | DebruijnIndex::INNERMOST, | |
762 | ) | |
763 | } | |
764 | ||
765 | /// Replaces `Ty::Error` by a new type var, so we can maybe still infer it. | |
766 | pub(super) fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty { | |
767 | match ty.kind(Interner) { | |
768 | TyKind::Error => self.new_type_var(), | |
769 | TyKind::InferenceVar(..) => { | |
770 | let ty_resolved = self.resolve_ty_shallow(&ty); | |
771 | if ty_resolved.is_unknown() { | |
772 | self.new_type_var() | |
773 | } else { | |
774 | ty | |
775 | } | |
776 | } | |
777 | _ => ty, | |
778 | } | |
779 | } | |
780 | ||
781 | /// Replaces ConstScalar::Unknown by a new type var, so we can maybe still infer it. | |
782 | pub(super) fn insert_const_vars_shallow(&mut self, c: Const) -> Const { | |
783 | let data = c.data(Interner); | |
784 | match &data.value { | |
785 | ConstValue::Concrete(cc) => match &cc.interned { | |
786 | crate::ConstScalar::Unknown => self.new_const_var(data.ty.clone()), | |
787 | // try to evaluate unevaluated const. Replace with new var if const eval failed. | |
788 | crate::ConstScalar::UnevaluatedConst(id, subst) => { | |
add651ee | 789 | if let Ok(eval) = self.db.const_eval(*id, subst.clone(), None) { |
fe692bf9 FG |
790 | eval |
791 | } else { | |
792 | self.new_const_var(data.ty.clone()) | |
793 | } | |
794 | } | |
795 | _ => c, | |
796 | }, | |
797 | _ => c, | |
798 | } | |
799 | } | |
064997fb FG |
800 | } |
801 | ||
add651ee | 802 | impl fmt::Debug for InferenceTable<'_> { |
064997fb FG |
803 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
804 | f.debug_struct("InferenceTable").field("num_vars", &self.type_variable_table.len()).finish() | |
805 | } | |
806 | } | |
807 | ||
808 | mod resolve { | |
809 | use super::InferenceTable; | |
810 | use crate::{ | |
353b0b11 FG |
811 | ConcreteConst, Const, ConstData, ConstScalar, ConstValue, DebruijnIndex, GenericArg, |
812 | InferenceVar, Interner, Lifetime, Ty, TyVariableKind, VariableKind, | |
064997fb FG |
813 | }; |
814 | use chalk_ir::{ | |
815 | cast::Cast, | |
816 | fold::{TypeFoldable, TypeFolder}, | |
064997fb | 817 | }; |
064997fb | 818 | |
2b03887a FG |
819 | #[derive(chalk_derive::FallibleTypeFolder)] |
820 | #[has_interner(Interner)] | |
821 | pub(super) struct Resolver< | |
822 | 'a, | |
823 | 'b, | |
824 | F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, | |
825 | > { | |
064997fb FG |
826 | pub(super) table: &'a mut InferenceTable<'b>, |
827 | pub(super) var_stack: &'a mut Vec<InferenceVar>, | |
828 | pub(super) fallback: F, | |
829 | } | |
add651ee | 830 | impl<F> TypeFolder<Interner> for Resolver<'_, '_, F> |
064997fb | 831 | where |
2b03887a | 832 | F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, |
064997fb | 833 | { |
064997fb FG |
834 | fn as_dyn(&mut self) -> &mut dyn TypeFolder<Interner, Error = Self::Error> { |
835 | self | |
836 | } | |
837 | ||
838 | fn interner(&self) -> Interner { | |
839 | Interner | |
840 | } | |
841 | ||
842 | fn fold_inference_ty( | |
843 | &mut self, | |
844 | var: InferenceVar, | |
845 | kind: TyVariableKind, | |
846 | outer_binder: DebruijnIndex, | |
2b03887a | 847 | ) -> Ty { |
064997fb FG |
848 | let var = self.table.var_unification_table.inference_var_root(var); |
849 | if self.var_stack.contains(&var) { | |
850 | // recursive type | |
851 | let default = self.table.fallback_value(var, kind).cast(Interner); | |
2b03887a | 852 | return (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) |
064997fb | 853 | .assert_ty_ref(Interner) |
2b03887a | 854 | .clone(); |
064997fb FG |
855 | } |
856 | let result = if let Some(known_ty) = self.table.var_unification_table.probe_var(var) { | |
857 | // known_ty may contain other variables that are known by now | |
858 | self.var_stack.push(var); | |
2b03887a | 859 | let result = known_ty.fold_with(self, outer_binder); |
064997fb FG |
860 | self.var_stack.pop(); |
861 | result.assert_ty_ref(Interner).clone() | |
862 | } else { | |
863 | let default = self.table.fallback_value(var, kind).cast(Interner); | |
864 | (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) | |
865 | .assert_ty_ref(Interner) | |
866 | .clone() | |
867 | }; | |
2b03887a | 868 | result |
064997fb FG |
869 | } |
870 | ||
871 | fn fold_inference_const( | |
872 | &mut self, | |
873 | ty: Ty, | |
874 | var: InferenceVar, | |
875 | outer_binder: DebruijnIndex, | |
2b03887a | 876 | ) -> Const { |
064997fb FG |
877 | let var = self.table.var_unification_table.inference_var_root(var); |
878 | let default = ConstData { | |
879 | ty: ty.clone(), | |
880 | value: ConstValue::Concrete(ConcreteConst { interned: ConstScalar::Unknown }), | |
881 | } | |
882 | .intern(Interner) | |
883 | .cast(Interner); | |
884 | if self.var_stack.contains(&var) { | |
885 | // recursive | |
2b03887a | 886 | return (self.fallback)(var, VariableKind::Const(ty), default, outer_binder) |
064997fb | 887 | .assert_const_ref(Interner) |
2b03887a | 888 | .clone(); |
064997fb | 889 | } |
2b03887a | 890 | if let Some(known_ty) = self.table.var_unification_table.probe_var(var) { |
064997fb FG |
891 | // known_ty may contain other variables that are known by now |
892 | self.var_stack.push(var); | |
2b03887a | 893 | let result = known_ty.fold_with(self, outer_binder); |
064997fb FG |
894 | self.var_stack.pop(); |
895 | result.assert_const_ref(Interner).clone() | |
896 | } else { | |
897 | (self.fallback)(var, VariableKind::Const(ty), default, outer_binder) | |
898 | .assert_const_ref(Interner) | |
899 | .clone() | |
2b03887a | 900 | } |
064997fb FG |
901 | } |
902 | ||
903 | fn fold_inference_lifetime( | |
904 | &mut self, | |
905 | _var: InferenceVar, | |
906 | _outer_binder: DebruijnIndex, | |
2b03887a | 907 | ) -> Lifetime { |
064997fb FG |
908 | // fall back all lifetimes to 'static -- currently we don't deal |
909 | // with any lifetimes, but we can sometimes get some lifetime | |
910 | // variables through Chalk's unification, and this at least makes | |
911 | // sure we don't leak them outside of inference | |
2b03887a | 912 | crate::static_lifetime() |
064997fb FG |
913 | } |
914 | } | |
915 | } |