aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir_ty')
-rw-r--r--crates/hir_ty/src/builder.rs16
-rw-r--r--crates/hir_ty/src/chalk_db.rs15
-rw-r--r--crates/hir_ty/src/chalk_ext.rs5
-rw-r--r--crates/hir_ty/src/db.rs10
-rw-r--r--crates/hir_ty/src/infer.rs192
-rw-r--r--crates/hir_ty/src/infer/coerce.rs480
-rw-r--r--crates/hir_ty/src/infer/expr.rs142
-rw-r--r--crates/hir_ty/src/infer/pat.rs19
-rw-r--r--crates/hir_ty/src/infer/path.rs6
-rw-r--r--crates/hir_ty/src/infer/unify.rs861
-rw-r--r--crates/hir_ty/src/interner.rs49
-rw-r--r--crates/hir_ty/src/lib.rs71
-rw-r--r--crates/hir_ty/src/lower.rs4
-rw-r--r--crates/hir_ty/src/method_resolution.rs47
-rw-r--r--crates/hir_ty/src/tests/coercion.rs56
-rw-r--r--crates/hir_ty/src/tests/patterns.rs2
-rw-r--r--crates/hir_ty/src/tests/regression.rs69
-rw-r--r--crates/hir_ty/src/tests/simple.rs36
-rw-r--r--crates/hir_ty/src/tests/traits.rs2
-rw-r--r--crates/hir_ty/src/tls.rs138
-rw-r--r--crates/hir_ty/src/traits.rs40
21 files changed, 1195 insertions, 1065 deletions
diff --git a/crates/hir_ty/src/builder.rs b/crates/hir_ty/src/builder.rs
index e25ef866d..893e727c2 100644
--- a/crates/hir_ty/src/builder.rs
+++ b/crates/hir_ty/src/builder.rs
@@ -6,15 +6,15 @@ use chalk_ir::{
6 cast::{Cast, CastTo, Caster}, 6 cast::{Cast, CastTo, Caster},
7 fold::Fold, 7 fold::Fold,
8 interner::HasInterner, 8 interner::HasInterner,
9 AdtId, BoundVar, DebruijnIndex, Safety, Scalar, 9 AdtId, BoundVar, DebruijnIndex, Scalar,
10}; 10};
11use hir_def::{builtin_type::BuiltinType, GenericDefId, TraitId, TypeAliasId}; 11use hir_def::{builtin_type::BuiltinType, GenericDefId, TraitId, TypeAliasId};
12use smallvec::SmallVec; 12use smallvec::SmallVec;
13 13
14use crate::{ 14use crate::{
15 db::HirDatabase, primitive, to_assoc_type_id, to_chalk_trait_id, utils::generics, Binders, 15 db::HirDatabase, primitive, to_assoc_type_id, to_chalk_trait_id, utils::generics, Binders,
16 CallableSig, FnPointer, FnSig, FnSubst, GenericArg, Interner, ProjectionTy, Substitution, 16 CallableSig, GenericArg, Interner, ProjectionTy, Substitution, TraitRef, Ty, TyDefId, TyExt,
17 TraitRef, Ty, TyDefId, TyExt, TyKind, ValueTyDefId, 17 TyKind, ValueTyDefId,
18}; 18};
19 19
20/// This is a builder for `Ty` or anything that needs a `Substitution`. 20/// This is a builder for `Ty` or anything that needs a `Substitution`.
@@ -77,15 +77,7 @@ impl TyBuilder<()> {
77 } 77 }
78 78
79 pub fn fn_ptr(sig: CallableSig) -> Ty { 79 pub fn fn_ptr(sig: CallableSig) -> Ty {
80 TyKind::Function(FnPointer { 80 TyKind::Function(sig.to_fn_ptr()).intern(&Interner)
81 num_binders: 0,
82 sig: FnSig { abi: (), safety: Safety::Safe, variadic: sig.is_varargs },
83 substitution: FnSubst(Substitution::from_iter(
84 &Interner,
85 sig.params_and_return.iter().cloned(),
86 )),
87 })
88 .intern(&Interner)
89 } 81 }
90 82
91 pub fn builtin(builtin: BuiltinType) -> Ty { 83 pub fn builtin(builtin: BuiltinType) -> Ty {
diff --git a/crates/hir_ty/src/chalk_db.rs b/crates/hir_ty/src/chalk_db.rs
index 8f054d06b..b108fd559 100644
--- a/crates/hir_ty/src/chalk_db.rs
+++ b/crates/hir_ty/src/chalk_db.rs
@@ -344,20 +344,20 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
344 } 344 }
345 345
346 fn unification_database(&self) -> &dyn chalk_ir::UnificationDatabase<Interner> { 346 fn unification_database(&self) -> &dyn chalk_ir::UnificationDatabase<Interner> {
347 self 347 &self.db
348 } 348 }
349} 349}
350 350
351impl<'a> chalk_ir::UnificationDatabase<Interner> for ChalkContext<'a> { 351impl<'a> chalk_ir::UnificationDatabase<Interner> for &'a dyn HirDatabase {
352 fn fn_def_variance( 352 fn fn_def_variance(
353 &self, 353 &self,
354 fn_def_id: chalk_ir::FnDefId<Interner>, 354 fn_def_id: chalk_ir::FnDefId<Interner>,
355 ) -> chalk_ir::Variances<Interner> { 355 ) -> chalk_ir::Variances<Interner> {
356 self.db.fn_def_variance(self.krate, fn_def_id) 356 HirDatabase::fn_def_variance(*self, fn_def_id)
357 } 357 }
358 358
359 fn adt_variance(&self, adt_id: chalk_ir::AdtId<Interner>) -> chalk_ir::Variances<Interner> { 359 fn adt_variance(&self, adt_id: chalk_ir::AdtId<Interner>) -> chalk_ir::Variances<Interner> {
360 self.db.adt_variance(self.krate, adt_id) 360 HirDatabase::adt_variance(*self, adt_id)
361 } 361 }
362} 362}
363 363
@@ -651,11 +651,7 @@ pub(crate) fn fn_def_datum_query(
651 Arc::new(datum) 651 Arc::new(datum)
652} 652}
653 653
654pub(crate) fn fn_def_variance_query( 654pub(crate) fn fn_def_variance_query(db: &dyn HirDatabase, fn_def_id: FnDefId) -> Variances {
655 db: &dyn HirDatabase,
656 _krate: CrateId,
657 fn_def_id: FnDefId,
658) -> Variances {
659 let callable_def: CallableDefId = from_chalk(db, fn_def_id); 655 let callable_def: CallableDefId = from_chalk(db, fn_def_id);
660 let generic_params = generics(db.upcast(), callable_def.into()); 656 let generic_params = generics(db.upcast(), callable_def.into());
661 Variances::from_iter( 657 Variances::from_iter(
@@ -666,7 +662,6 @@ pub(crate) fn fn_def_variance_query(
666 662
667pub(crate) fn adt_variance_query( 663pub(crate) fn adt_variance_query(
668 db: &dyn HirDatabase, 664 db: &dyn HirDatabase,
669 _krate: CrateId,
670 chalk_ir::AdtId(adt_id): AdtId, 665 chalk_ir::AdtId(adt_id): AdtId,
671) -> Variances { 666) -> Variances {
672 let generic_params = generics(db.upcast(), adt_id.into()); 667 let generic_params = generics(db.upcast(), adt_id.into());
diff --git a/crates/hir_ty/src/chalk_ext.rs b/crates/hir_ty/src/chalk_ext.rs
index 5232a7d80..df340a6ca 100644
--- a/crates/hir_ty/src/chalk_ext.rs
+++ b/crates/hir_ty/src/chalk_ext.rs
@@ -18,6 +18,7 @@ pub trait TyExt {
18 fn is_unit(&self) -> bool; 18 fn is_unit(&self) -> bool;
19 fn is_never(&self) -> bool; 19 fn is_never(&self) -> bool;
20 fn is_unknown(&self) -> bool; 20 fn is_unknown(&self) -> bool;
21 fn is_ty_var(&self) -> bool;
21 22
22 fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)>; 23 fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)>;
23 fn as_builtin(&self) -> Option<BuiltinType>; 24 fn as_builtin(&self) -> Option<BuiltinType>;
@@ -55,6 +56,10 @@ impl TyExt for Ty {
55 matches!(self.kind(&Interner), TyKind::Error) 56 matches!(self.kind(&Interner), TyKind::Error)
56 } 57 }
57 58
59 fn is_ty_var(&self) -> bool {
60 matches!(self.kind(&Interner), TyKind::InferenceVar(_, _))
61 }
62
58 fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)> { 63 fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)> {
59 match self.kind(&Interner) { 64 match self.kind(&Interner) {
60 TyKind::Adt(AdtId(adt), parameters) => Some((*adt, parameters)), 65 TyKind::Adt(AdtId(adt), parameters) => Some((*adt, parameters)),
diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs
index 9da0a02e3..be5b9110e 100644
--- a/crates/hir_ty/src/db.rs
+++ b/crates/hir_ty/src/db.rs
@@ -117,10 +117,10 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
117 fn fn_def_datum(&self, krate: CrateId, fn_def_id: FnDefId) -> Arc<chalk_db::FnDefDatum>; 117 fn fn_def_datum(&self, krate: CrateId, fn_def_id: FnDefId) -> Arc<chalk_db::FnDefDatum>;
118 118
119 #[salsa::invoke(chalk_db::fn_def_variance_query)] 119 #[salsa::invoke(chalk_db::fn_def_variance_query)]
120 fn fn_def_variance(&self, krate: CrateId, fn_def_id: FnDefId) -> chalk_db::Variances; 120 fn fn_def_variance(&self, fn_def_id: FnDefId) -> chalk_db::Variances;
121 121
122 #[salsa::invoke(chalk_db::adt_variance_query)] 122 #[salsa::invoke(chalk_db::adt_variance_query)]
123 fn adt_variance(&self, krate: CrateId, adt_id: chalk_db::AdtId) -> chalk_db::Variances; 123 fn adt_variance(&self, adt_id: chalk_db::AdtId) -> chalk_db::Variances;
124 124
125 #[salsa::invoke(chalk_db::associated_ty_value_query)] 125 #[salsa::invoke(chalk_db::associated_ty_value_query)]
126 fn associated_ty_value( 126 fn associated_ty_value(
@@ -134,14 +134,14 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
134 fn trait_solve( 134 fn trait_solve(
135 &self, 135 &self,
136 krate: CrateId, 136 krate: CrateId,
137 goal: crate::Canonical<crate::InEnvironment<crate::DomainGoal>>, 137 goal: crate::Canonical<crate::InEnvironment<crate::Goal>>,
138 ) -> Option<crate::Solution>; 138 ) -> Option<crate::Solution>;
139 139
140 #[salsa::invoke(crate::traits::trait_solve_query)] 140 #[salsa::invoke(crate::traits::trait_solve_query)]
141 fn trait_solve_query( 141 fn trait_solve_query(
142 &self, 142 &self,
143 krate: CrateId, 143 krate: CrateId,
144 goal: crate::Canonical<crate::InEnvironment<crate::DomainGoal>>, 144 goal: crate::Canonical<crate::InEnvironment<crate::Goal>>,
145 ) -> Option<crate::Solution>; 145 ) -> Option<crate::Solution>;
146 146
147 #[salsa::invoke(chalk_db::program_clauses_for_chalk_env_query)] 147 #[salsa::invoke(chalk_db::program_clauses_for_chalk_env_query)]
@@ -168,7 +168,7 @@ fn infer_wait(db: &dyn HirDatabase, def: DefWithBodyId) -> Arc<InferenceResult>
168fn trait_solve_wait( 168fn trait_solve_wait(
169 db: &dyn HirDatabase, 169 db: &dyn HirDatabase,
170 krate: CrateId, 170 krate: CrateId,
171 goal: crate::Canonical<crate::InEnvironment<crate::DomainGoal>>, 171 goal: crate::Canonical<crate::InEnvironment<crate::Goal>>,
172) -> Option<crate::Solution> { 172) -> Option<crate::Solution> {
173 let _p = profile::span("trait_solve::wait"); 173 let _p = profile::span("trait_solve::wait");
174 db.trait_solve_query(krate, goal) 174 db.trait_solve_query(krate, goal)
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index 0ee851a74..f1cebbdb9 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -13,8 +13,6 @@
13//! to certain types. To record this, we use the union-find implementation from 13//! to certain types. To record this, we use the union-find implementation from
14//! the `ena` crate, which is extracted from rustc. 14//! the `ena` crate, which is extracted from rustc.
15 15
16use std::borrow::Cow;
17use std::mem;
18use std::ops::Index; 16use std::ops::Index;
19use std::sync::Arc; 17use std::sync::Arc;
20 18
@@ -27,8 +25,8 @@ use hir_def::{
27 path::{path, Path}, 25 path::{path, Path},
28 resolver::{HasResolver, Resolver, TypeNs}, 26 resolver::{HasResolver, Resolver, TypeNs},
29 type_ref::TypeRef, 27 type_ref::TypeRef,
30 AdtId, AssocItemId, DefWithBodyId, EnumVariantId, FieldId, FunctionId, Lookup, TraitId, 28 AdtId, AssocItemId, DefWithBodyId, EnumVariantId, FieldId, FunctionId, HasModule, Lookup,
31 TypeAliasId, VariantId, 29 TraitId, TypeAliasId, VariantId,
32}; 30};
33use hir_expand::{diagnostics::DiagnosticSink, name::name}; 31use hir_expand::{diagnostics::DiagnosticSink, name::name};
34use la_arena::ArenaMap; 32use la_arena::ArenaMap;
@@ -36,13 +34,11 @@ use rustc_hash::FxHashMap;
36use stdx::impl_from; 34use stdx::impl_from;
37use syntax::SmolStr; 35use syntax::SmolStr;
38 36
39use super::{ 37use super::{DomainGoal, InEnvironment, ProjectionTy, TraitEnvironment, TraitRef, Ty};
40 DomainGoal, Guidance, InEnvironment, ProjectionTy, Solution, TraitEnvironment, TraitRef, Ty,
41};
42use crate::{ 38use crate::{
43 db::HirDatabase, fold_tys, infer::diagnostics::InferenceDiagnostic, 39 db::HirDatabase, fold_tys, infer::diagnostics::InferenceDiagnostic,
44 lower::ImplTraitLoweringMode, to_assoc_type_id, AliasEq, AliasTy, Canonical, Interner, 40 lower::ImplTraitLoweringMode, to_assoc_type_id, AliasEq, AliasTy, Goal, Interner, TyBuilder,
45 TyBuilder, TyExt, TyKind, 41 TyExt, TyKind,
46}; 42};
47 43
48// This lint has a false positive here. See the link below for details. 44// This lint has a false positive here. See the link below for details.
@@ -106,6 +102,14 @@ impl Default for BindingMode {
106 } 102 }
107} 103}
108 104
105#[derive(Debug)]
106pub(crate) struct InferOk {
107 goals: Vec<InEnvironment<Goal>>,
108}
109#[derive(Debug)]
110pub(crate) struct TypeError;
111pub(crate) type InferResult = Result<InferOk, TypeError>;
112
109/// A mismatch between an expected and an inferred type. 113/// A mismatch between an expected and an inferred type.
110#[derive(Clone, PartialEq, Eq, Debug, Hash)] 114#[derive(Clone, PartialEq, Eq, Debug, Hash)]
111pub struct TypeMismatch { 115pub struct TypeMismatch {
@@ -217,10 +221,8 @@ struct InferenceContext<'a> {
217 owner: DefWithBodyId, 221 owner: DefWithBodyId,
218 body: Arc<Body>, 222 body: Arc<Body>,
219 resolver: Resolver, 223 resolver: Resolver,
220 table: unify::InferenceTable, 224 table: unify::InferenceTable<'a>,
221 trait_env: Arc<TraitEnvironment>, 225 trait_env: Arc<TraitEnvironment>,
222 obligations: Vec<DomainGoal>,
223 last_obligations_check: Option<u32>,
224 result: InferenceResult, 226 result: InferenceResult,
225 /// The return type of the function being inferred, or the closure if we're 227 /// The return type of the function being inferred, or the closure if we're
226 /// currently within one. 228 /// currently within one.
@@ -252,15 +254,15 @@ fn find_breakable<'c>(
252 254
253impl<'a> InferenceContext<'a> { 255impl<'a> InferenceContext<'a> {
254 fn new(db: &'a dyn HirDatabase, owner: DefWithBodyId, resolver: Resolver) -> Self { 256 fn new(db: &'a dyn HirDatabase, owner: DefWithBodyId, resolver: Resolver) -> Self {
257 let krate = owner.module(db.upcast()).krate();
258 let trait_env = owner
259 .as_generic_def_id()
260 .map_or_else(|| Arc::new(TraitEnvironment::empty(krate)), |d| db.trait_environment(d));
255 InferenceContext { 261 InferenceContext {
256 result: InferenceResult::default(), 262 result: InferenceResult::default(),
257 table: unify::InferenceTable::new(), 263 table: unify::InferenceTable::new(db, trait_env.clone()),
258 obligations: Vec::default(), 264 trait_env,
259 last_obligations_check: None,
260 return_ty: TyKind::Error.intern(&Interner), // set in collect_fn_signature 265 return_ty: TyKind::Error.intern(&Interner), // set in collect_fn_signature
261 trait_env: owner
262 .as_generic_def_id()
263 .map_or_else(Default::default, |d| db.trait_environment(d)),
264 db, 266 db,
265 owner, 267 owner,
266 body: db.body(owner), 268 body: db.body(owner),
@@ -271,19 +273,25 @@ impl<'a> InferenceContext<'a> {
271 } 273 }
272 274
273 fn err_ty(&self) -> Ty { 275 fn err_ty(&self) -> Ty {
274 TyKind::Error.intern(&Interner) 276 self.result.standard_types.unknown.clone()
275 } 277 }
276 278
277 fn resolve_all(mut self) -> InferenceResult { 279 fn resolve_all(mut self) -> InferenceResult {
278 // FIXME resolve obligations as well (use Guidance if necessary) 280 // FIXME resolve obligations as well (use Guidance if necessary)
281 self.table.resolve_obligations_as_possible();
282
283 // make sure diverging type variables are marked as such
284 self.table.propagate_diverging_flag();
279 let mut result = std::mem::take(&mut self.result); 285 let mut result = std::mem::take(&mut self.result);
280 for ty in result.type_of_expr.values_mut() { 286 for ty in result.type_of_expr.values_mut() {
281 let resolved = self.table.resolve_ty_completely(ty.clone()); 287 *ty = self.table.resolve_ty_completely(ty.clone());
282 *ty = resolved;
283 } 288 }
284 for ty in result.type_of_pat.values_mut() { 289 for ty in result.type_of_pat.values_mut() {
285 let resolved = self.table.resolve_ty_completely(ty.clone()); 290 *ty = self.table.resolve_ty_completely(ty.clone());
286 *ty = resolved; 291 }
292 for mismatch in result.type_mismatches.values_mut() {
293 mismatch.expected = self.table.resolve_ty_completely(mismatch.expected.clone());
294 mismatch.actual = self.table.resolve_ty_completely(mismatch.actual.clone());
287 } 295 }
288 result 296 result
289 } 297 }
@@ -337,6 +345,14 @@ impl<'a> InferenceContext<'a> {
337 fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty { 345 fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty {
338 match ty.kind(&Interner) { 346 match ty.kind(&Interner) {
339 TyKind::Error => self.table.new_type_var(), 347 TyKind::Error => self.table.new_type_var(),
348 TyKind::InferenceVar(..) => {
349 let ty_resolved = self.resolve_ty_shallow(&ty);
350 if ty_resolved.is_unknown() {
351 self.table.new_type_var()
352 } else {
353 ty
354 }
355 }
340 _ => ty, 356 _ => ty,
341 } 357 }
342 } 358 }
@@ -346,66 +362,19 @@ impl<'a> InferenceContext<'a> {
346 } 362 }
347 363
348 fn resolve_obligations_as_possible(&mut self) { 364 fn resolve_obligations_as_possible(&mut self) {
349 if self.last_obligations_check == Some(self.table.revision) { 365 self.table.resolve_obligations_as_possible();
350 // no change
351 return;
352 }
353 let _span = profile::span("resolve_obligations_as_possible");
354
355 self.last_obligations_check = Some(self.table.revision);
356 let obligations = mem::replace(&mut self.obligations, Vec::new());
357 for obligation in obligations {
358 let in_env = InEnvironment::new(&self.trait_env.env, obligation.clone());
359 let canonicalized = self.canonicalizer().canonicalize_obligation(in_env);
360 let solution =
361 self.db.trait_solve(self.resolver.krate().unwrap(), canonicalized.value.clone());
362
363 match solution {
364 Some(Solution::Unique(canonical_subst)) => {
365 canonicalized.apply_solution(
366 self,
367 Canonical {
368 binders: canonical_subst.binders,
369 // FIXME: handle constraints
370 value: canonical_subst.value.subst,
371 },
372 );
373 }
374 Some(Solution::Ambig(Guidance::Definite(substs))) => {
375 canonicalized.apply_solution(self, substs);
376 self.obligations.push(obligation);
377 }
378 Some(_) => {
379 // FIXME use this when trying to resolve everything at the end
380 self.obligations.push(obligation);
381 }
382 None => {
383 // FIXME obligation cannot be fulfilled => diagnostic
384 }
385 };
386 }
387 } 366 }
388 367
389 fn push_obligation(&mut self, o: DomainGoal) { 368 fn push_obligation(&mut self, o: DomainGoal) {
390 self.obligations.push(o); 369 self.table.register_obligation(o.cast(&Interner));
391 self.last_obligations_check = None;
392 } 370 }
393 371
394 fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { 372 fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
395 self.table.unify(ty1, ty2) 373 self.table.unify(ty1, ty2)
396 } 374 }
397 375
398 /// Resolves the type as far as currently possible, replacing type variables 376 fn resolve_ty_shallow(&mut self, ty: &Ty) -> Ty {
399 /// by their known types. All types returned by the infer_* functions should
400 /// be resolved as far as possible, i.e. contain no type variables with
401 /// known type.
402 fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty {
403 self.resolve_obligations_as_possible(); 377 self.resolve_obligations_as_possible();
404
405 self.table.resolve_ty_as_possible(ty)
406 }
407
408 fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
409 self.table.resolve_ty_shallow(ty) 378 self.table.resolve_ty_shallow(ty)
410 } 379 }
411 380
@@ -439,7 +408,7 @@ impl<'a> InferenceContext<'a> {
439 }; 408 };
440 self.push_obligation(trait_ref.cast(&Interner)); 409 self.push_obligation(trait_ref.cast(&Interner));
441 self.push_obligation(alias_eq.cast(&Interner)); 410 self.push_obligation(alias_eq.cast(&Interner));
442 self.resolve_ty_as_possible(ty) 411 ty
443 } 412 }
444 None => self.err_ty(), 413 None => self.err_ty(),
445 } 414 }
@@ -452,25 +421,7 @@ impl<'a> InferenceContext<'a> {
452 /// call). `make_ty` handles this already, but e.g. for field types we need 421 /// call). `make_ty` handles this already, but e.g. for field types we need
453 /// to do it as well. 422 /// to do it as well.
454 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty { 423 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
455 let ty = self.resolve_ty_as_possible(ty); 424 self.table.normalize_associated_types_in(ty)
456 fold_tys(
457 ty,
458 |ty, _| match ty.kind(&Interner) {
459 TyKind::Alias(AliasTy::Projection(proj_ty)) => {
460 self.normalize_projection_ty(proj_ty.clone())
461 }
462 _ => ty,
463 },
464 DebruijnIndex::INNERMOST,
465 )
466 }
467
468 fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
469 let var = self.table.new_type_var();
470 let alias_eq = AliasEq { alias: AliasTy::Projection(proj_ty), ty: var.clone() };
471 let obligation = alias_eq.cast(&Interner);
472 self.push_obligation(obligation);
473 var
474 } 425 }
475 426
476 fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) { 427 fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) {
@@ -720,17 +671,23 @@ impl<'a> InferenceContext<'a> {
720/// When inferring an expression, we propagate downward whatever type hint we 671/// When inferring an expression, we propagate downward whatever type hint we
721/// are able in the form of an `Expectation`. 672/// are able in the form of an `Expectation`.
722#[derive(Clone, PartialEq, Eq, Debug)] 673#[derive(Clone, PartialEq, Eq, Debug)]
723struct Expectation { 674enum Expectation {
724 ty: Ty, 675 None,
725 /// See the `rvalue_hint` method. 676 HasType(Ty),
726 rvalue_hint: bool, 677 // Castable(Ty), // rustc has this, we currently just don't propagate an expectation for casts
678 RValueLikeUnsized(Ty),
727} 679}
728 680
729impl Expectation { 681impl Expectation {
730 /// The expectation that the type of the expression needs to equal the given 682 /// The expectation that the type of the expression needs to equal the given
731 /// type. 683 /// type.
732 fn has_type(ty: Ty) -> Self { 684 fn has_type(ty: Ty) -> Self {
733 Expectation { ty, rvalue_hint: false } 685 if ty.is_unknown() {
686 // FIXME: get rid of this?
687 Expectation::None
688 } else {
689 Expectation::HasType(ty)
690 }
734 } 691 }
735 692
736 /// The following explanation is copied straight from rustc: 693 /// The following explanation is copied straight from rustc:
@@ -754,24 +711,41 @@ impl Expectation {
754 /// See the test case `test/ui/coerce-expect-unsized.rs` and #20169 711 /// See the test case `test/ui/coerce-expect-unsized.rs` and #20169
755 /// for examples of where this comes up,. 712 /// for examples of where this comes up,.
756 fn rvalue_hint(ty: Ty) -> Self { 713 fn rvalue_hint(ty: Ty) -> Self {
757 Expectation { ty, rvalue_hint: true } 714 match ty.strip_references().kind(&Interner) {
715 TyKind::Slice(_) | TyKind::Str | TyKind::Dyn(_) => Expectation::RValueLikeUnsized(ty),
716 _ => Expectation::has_type(ty),
717 }
758 } 718 }
759 719
760 /// This expresses no expectation on the type. 720 /// This expresses no expectation on the type.
761 fn none() -> Self { 721 fn none() -> Self {
762 Expectation { 722 Expectation::None
763 // FIXME 723 }
764 ty: TyKind::Error.intern(&Interner), 724
765 rvalue_hint: false, 725 fn resolve(&self, table: &mut unify::InferenceTable) -> Expectation {
726 match self {
727 Expectation::None => Expectation::None,
728 Expectation::HasType(t) => Expectation::HasType(table.resolve_ty_shallow(t)),
729 Expectation::RValueLikeUnsized(t) => {
730 Expectation::RValueLikeUnsized(table.resolve_ty_shallow(t))
731 }
766 } 732 }
767 } 733 }
768 734
769 fn coercion_target(&self) -> Ty { 735 fn to_option(&self, table: &mut unify::InferenceTable) -> Option<Ty> {
770 if self.rvalue_hint { 736 match self.resolve(table) {
771 // FIXME 737 Expectation::None => None,
772 TyKind::Error.intern(&Interner) 738 Expectation::HasType(t) |
773 } else { 739 // Expectation::Castable(t) |
774 self.ty.clone() 740 Expectation::RValueLikeUnsized(t) => Some(t),
741 }
742 }
743
744 fn only_has_type(&self, table: &mut unify::InferenceTable) -> Option<Ty> {
745 match self {
746 Expectation::HasType(t) => Some(table.resolve_ty_shallow(t)),
747 // Expectation::Castable(_) |
748 Expectation::RValueLikeUnsized(_) | Expectation::None => None,
775 } 749 }
776 } 750 }
777} 751}
diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs
index 1f463a425..765a02b1c 100644
--- a/crates/hir_ty/src/infer/coerce.rs
+++ b/crates/hir_ty/src/infer/coerce.rs
@@ -2,156 +2,414 @@
2//! happen in certain places, e.g. weakening `&mut` to `&` or deref coercions 2//! happen in certain places, e.g. weakening `&mut` to `&` or deref coercions
3//! like going from `&Vec<T>` to `&[T]`. 3//! like going from `&Vec<T>` to `&[T]`.
4//! 4//!
5//! See: https://doc.rust-lang.org/nomicon/coercions.html 5//! See https://doc.rust-lang.org/nomicon/coercions.html and
6//! librustc_typeck/check/coercion.rs.
6 7
7use chalk_ir::{cast::Cast, Mutability, TyVariableKind}; 8use chalk_ir::{cast::Cast, Mutability, TyVariableKind};
8use hir_def::lang_item::LangItemTarget; 9use hir_def::{expr::ExprId, lang_item::LangItemTarget};
9 10
10use crate::{autoderef, Canonical, Interner, Solution, Ty, TyBuilder, TyExt, TyKind}; 11use crate::{
12 autoderef, infer::TypeMismatch, static_lifetime, Canonical, DomainGoal, FnPointer, FnSig,
13 Interner, Solution, Substitution, Ty, TyBuilder, TyExt, TyKind,
14};
11 15
12use super::{InEnvironment, InferenceContext}; 16use super::{InEnvironment, InferOk, InferResult, InferenceContext, TypeError};
13 17
14impl<'a> InferenceContext<'a> { 18impl<'a> InferenceContext<'a> {
15 /// Unify two types, but may coerce the first one to the second one 19 /// Unify two types, but may coerce the first one to the second one
16 /// using "implicit coercion rules" if needed. 20 /// using "implicit coercion rules" if needed.
17 pub(super) fn coerce(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool { 21 pub(super) fn coerce(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
18 let from_ty = self.resolve_ty_shallow(from_ty).into_owned(); 22 let from_ty = self.resolve_ty_shallow(from_ty);
19 let to_ty = self.resolve_ty_shallow(to_ty); 23 let to_ty = self.resolve_ty_shallow(to_ty);
20 self.coerce_inner(from_ty, &to_ty) 24 match self.coerce_inner(from_ty, &to_ty) {
25 Ok(result) => {
26 self.table.register_infer_ok(result);
27 true
28 }
29 Err(_) => {
30 // FIXME deal with error
31 false
32 }
33 }
21 } 34 }
22 35
23 /// Merge two types from different branches, with possible coercion. 36 /// Merge two types from different branches, with possible coercion.
24 /// 37 ///
25 /// Mostly this means trying to coerce one to the other, but 38 /// Mostly this means trying to coerce one to the other, but
26 /// - if we have two function types for different functions, we need to 39 /// - if we have two function types for different functions or closures, we need to
27 /// coerce both to function pointers; 40 /// coerce both to function pointers;
28 /// - if we were concerned with lifetime subtyping, we'd need to look for a 41 /// - if we were concerned with lifetime subtyping, we'd need to look for a
29 /// least upper bound. 42 /// least upper bound.
30 pub(super) fn coerce_merge_branch(&mut self, ty1: &Ty, ty2: &Ty) -> Ty { 43 pub(super) fn coerce_merge_branch(&mut self, id: Option<ExprId>, ty1: &Ty, ty2: &Ty) -> Ty {
31 if self.coerce(ty1, ty2) { 44 let ty1 = self.resolve_ty_shallow(ty1);
32 ty2.clone() 45 let ty2 = self.resolve_ty_shallow(ty2);
33 } else if self.coerce(ty2, ty1) { 46 // Special case: two function types. Try to coerce both to
47 // pointers to have a chance at getting a match. See
48 // https://github.com/rust-lang/rust/blob/7b805396bf46dce972692a6846ce2ad8481c5f85/src/librustc_typeck/check/coercion.rs#L877-L916
49 let sig = match (ty1.kind(&Interner), ty2.kind(&Interner)) {
50 (TyKind::FnDef(..), TyKind::FnDef(..))
51 | (TyKind::Closure(..), TyKind::FnDef(..))
52 | (TyKind::FnDef(..), TyKind::Closure(..))
53 | (TyKind::Closure(..), TyKind::Closure(..)) => {
54 // FIXME: we're ignoring safety here. To be more correct, if we have one FnDef and one Closure,
55 // we should be coercing the closure to a fn pointer of the safety of the FnDef
56 cov_mark::hit!(coerce_fn_reification);
57 let sig = ty1.callable_sig(self.db).expect("FnDef without callable sig");
58 Some(sig)
59 }
60 _ => None,
61 };
62 if let Some(sig) = sig {
63 let target_ty = TyKind::Function(sig.to_fn_ptr()).intern(&Interner);
64 let result1 = self.coerce_inner(ty1.clone(), &target_ty);
65 let result2 = self.coerce_inner(ty2.clone(), &target_ty);
66 if let (Ok(result1), Ok(result2)) = (result1, result2) {
67 self.table.register_infer_ok(result1);
68 self.table.register_infer_ok(result2);
69 return target_ty;
70 }
71 }
72
73 // It might not seem like it, but order is important here: ty1 is our
74 // "previous" type, ty2 is the "new" one being added. If the previous
75 // type is a type variable and the new one is `!`, trying it the other
76 // way around first would mean we make the type variable `!`, instead of
77 // just marking it as possibly diverging.
78 if self.coerce(&ty2, &ty1) {
34 ty1.clone() 79 ty1.clone()
80 } else if self.coerce(&ty1, &ty2) {
81 ty2.clone()
35 } else { 82 } else {
36 if let (TyKind::FnDef(..), TyKind::FnDef(..)) = 83 if let Some(id) = id {
37 (ty1.kind(&Interner), ty2.kind(&Interner)) 84 self.result
38 { 85 .type_mismatches
39 cov_mark::hit!(coerce_fn_reification); 86 .insert(id.into(), TypeMismatch { expected: ty1.clone(), actual: ty2.clone() });
40 // Special case: two function types. Try to coerce both to
41 // pointers to have a chance at getting a match. See
42 // https://github.com/rust-lang/rust/blob/7b805396bf46dce972692a6846ce2ad8481c5f85/src/librustc_typeck/check/coercion.rs#L877-L916
43 let sig1 = ty1.callable_sig(self.db).expect("FnDef without callable sig");
44 let sig2 = ty2.callable_sig(self.db).expect("FnDef without callable sig");
45 let ptr_ty1 = TyBuilder::fn_ptr(sig1);
46 let ptr_ty2 = TyBuilder::fn_ptr(sig2);
47 self.coerce_merge_branch(&ptr_ty1, &ptr_ty2)
48 } else {
49 cov_mark::hit!(coerce_merge_fail_fallback);
50 ty1.clone()
51 } 87 }
88 cov_mark::hit!(coerce_merge_fail_fallback);
89 ty1.clone()
52 } 90 }
53 } 91 }
54 92
55 fn coerce_inner(&mut self, mut from_ty: Ty, to_ty: &Ty) -> bool { 93 fn coerce_inner(&mut self, from_ty: Ty, to_ty: &Ty) -> InferResult {
56 match (from_ty.kind(&Interner), to_ty.kind(&Interner)) { 94 if from_ty.is_never() {
57 // Never type will make type variable to fallback to Never Type instead of Unknown. 95 // Subtle: If we are coercing from `!` to `?T`, where `?T` is an unbound
58 (TyKind::Never, TyKind::InferenceVar(tv, TyVariableKind::General)) => { 96 // type variable, we want `?T` to fallback to `!` if not
59 self.table.type_variable_table.set_diverging(*tv, true); 97 // otherwise constrained. An example where this arises:
60 return true; 98 //
99 // let _: Option<?T> = Some({ return; });
100 //
101 // here, we would coerce from `!` to `?T`.
102 match to_ty.kind(&Interner) {
103 TyKind::InferenceVar(tv, TyVariableKind::General) => {
104 self.table.set_diverging(*tv, true);
105 }
106 _ => {}
61 } 107 }
62 (TyKind::Never, _) => return true, 108 return Ok(InferOk { goals: Vec::new() });
109 }
63 110
64 // Trivial cases, this should go after `never` check to 111 // Consider coercing the subtype to a DST
65 // avoid infer result type to be never 112 if let Ok(ret) = self.try_coerce_unsized(&from_ty, &to_ty) {
66 _ => { 113 return Ok(ret);
67 if self.table.unify_inner_trivial(&from_ty, &to_ty, 0) { 114 }
68 return true; 115
69 } 116 // Examine the supertype and consider auto-borrowing.
117 match to_ty.kind(&Interner) {
118 TyKind::Raw(mt, _) => {
119 return self.coerce_ptr(from_ty, to_ty, *mt);
70 } 120 }
121 TyKind::Ref(mt, _, _) => {
122 return self.coerce_ref(from_ty, to_ty, *mt);
123 }
124 _ => {}
71 } 125 }
72 126
73 // Pointer weakening and function to pointer 127 match from_ty.kind(&Interner) {
74 match (from_ty.kind(&Interner), to_ty.kind(&Interner)) { 128 TyKind::FnDef(..) => {
75 // `*mut T` -> `*const T` 129 // Function items are coercible to any closure
76 (TyKind::Raw(_, inner), TyKind::Raw(m2 @ Mutability::Not, ..)) => { 130 // type; function pointers are not (that would
77 from_ty = TyKind::Raw(*m2, inner.clone()).intern(&Interner); 131 // require double indirection).
132 // Additionally, we permit coercion of function
133 // items to drop the unsafe qualifier.
134 self.coerce_from_fn_item(from_ty, to_ty)
78 } 135 }
79 // `&mut T` -> `&T` 136 TyKind::Function(from_fn_ptr) => {
80 (TyKind::Ref(_, lt, inner), TyKind::Ref(m2 @ Mutability::Not, ..)) => { 137 // We permit coercion of fn pointers to drop the
81 from_ty = TyKind::Ref(*m2, lt.clone(), inner.clone()).intern(&Interner); 138 // unsafe qualifier.
139 self.coerce_from_fn_pointer(from_ty.clone(), from_fn_ptr, to_ty)
82 } 140 }
83 // `&T` -> `*const T` 141 TyKind::Closure(_, from_substs) => {
84 // `&mut T` -> `*mut T`/`*const T` 142 // Non-capturing closures are coercible to
85 (TyKind::Ref(.., substs), &TyKind::Raw(m2 @ Mutability::Not, ..)) 143 // function pointers or unsafe function pointers.
86 | (TyKind::Ref(Mutability::Mut, _, substs), &TyKind::Raw(m2, ..)) => { 144 // It cannot convert closures that require unsafe.
87 from_ty = TyKind::Raw(m2, substs.clone()).intern(&Interner); 145 self.coerce_closure_to_fn(from_ty.clone(), from_substs, to_ty)
88 } 146 }
147 _ => {
148 // Otherwise, just use unification rules.
149 self.table.try_unify(&from_ty, to_ty)
150 }
151 }
152 }
89 153
90 // Illegal mutability conversion 154 fn coerce_ptr(&mut self, from_ty: Ty, to_ty: &Ty, to_mt: Mutability) -> InferResult {
91 (TyKind::Raw(Mutability::Not, ..), TyKind::Raw(Mutability::Mut, ..)) 155 let (_is_ref, from_mt, from_inner) = match from_ty.kind(&Interner) {
92 | (TyKind::Ref(Mutability::Not, ..), TyKind::Ref(Mutability::Mut, ..)) => return false, 156 TyKind::Ref(mt, _, ty) => (true, mt, ty),
157 TyKind::Raw(mt, ty) => (false, mt, ty),
158 _ => return self.table.try_unify(&from_ty, to_ty),
159 };
93 160
94 // `{function_type}` -> `fn()` 161 coerce_mutabilities(*from_mt, to_mt)?;
95 (TyKind::FnDef(..), TyKind::Function { .. }) => match from_ty.callable_sig(self.db) { 162
96 None => return false, 163 // Check that the types which they point at are compatible.
97 Some(sig) => { 164 let from_raw = TyKind::Raw(to_mt, from_inner.clone()).intern(&Interner);
98 from_ty = TyBuilder::fn_ptr(sig); 165 // FIXME: behavior differs based on is_ref once we're computing adjustments
99 } 166 self.table.try_unify(&from_raw, to_ty)
167 }
168
169 /// Reborrows `&mut A` to `&mut B` and `&(mut) A` to `&B`.
170 /// To match `A` with `B`, autoderef will be performed,
171 /// calling `deref`/`deref_mut` where necessary.
172 fn coerce_ref(&mut self, from_ty: Ty, to_ty: &Ty, to_mt: Mutability) -> InferResult {
173 match from_ty.kind(&Interner) {
174 TyKind::Ref(mt, _, _) => {
175 coerce_mutabilities(*mt, to_mt)?;
176 }
177 _ => return self.table.try_unify(&from_ty, to_ty),
178 };
179
180 // NOTE: this code is mostly copied and adapted from rustc, and
181 // currently more complicated than necessary, carrying errors around
182 // etc.. This complication will become necessary when we actually track
183 // details of coercion errors though, so I think it's useful to leave
184 // the structure like it is.
185
186 let canonicalized = self.canonicalize(from_ty.clone());
187 let autoderef = autoderef::autoderef(
188 self.db,
189 self.resolver.krate(),
190 InEnvironment {
191 goal: canonicalized.value.clone(),
192 environment: self.trait_env.env.clone(),
100 }, 193 },
194 );
195 let mut first_error = None;
196 let mut found = None;
101 197
102 (TyKind::Closure(.., substs), TyKind::Function { .. }) => { 198 for (autoderefs, referent_ty) in autoderef.enumerate() {
103 from_ty = substs.at(&Interner, 0).assert_ty_ref(&Interner).clone(); 199 if autoderefs == 0 {
200 // Don't let this pass, otherwise it would cause
201 // &T to autoref to &&T.
202 continue;
104 } 203 }
105 204
106 _ => {} 205 let referent_ty = canonicalized.decanonicalize_ty(referent_ty.value);
206
207 // At this point, we have deref'd `a` to `referent_ty`. So
208 // imagine we are coercing from `&'a mut Vec<T>` to `&'b mut [T]`.
209 // In the autoderef loop for `&'a mut Vec<T>`, we would get
210 // three callbacks:
211 //
212 // - `&'a mut Vec<T>` -- 0 derefs, just ignore it
213 // - `Vec<T>` -- 1 deref
214 // - `[T]` -- 2 deref
215 //
216 // At each point after the first callback, we want to
217 // check to see whether this would match out target type
218 // (`&'b mut [T]`) if we autoref'd it. We can't just
219 // compare the referent types, though, because we still
220 // have to consider the mutability. E.g., in the case
221 // we've been considering, we have an `&mut` reference, so
222 // the `T` in `[T]` needs to be unified with equality.
223 //
224 // Therefore, we construct reference types reflecting what
225 // the types will be after we do the final auto-ref and
226 // compare those. Note that this means we use the target
227 // mutability [1], since it may be that we are coercing
228 // from `&mut T` to `&U`.
229 let lt = static_lifetime(); // FIXME: handle lifetimes correctly, see rustc
230 let derefd_from_ty = TyKind::Ref(to_mt, lt, referent_ty).intern(&Interner);
231 match self.table.try_unify(&derefd_from_ty, to_ty) {
232 Ok(result) => {
233 found = Some(result);
234 break;
235 }
236 Err(err) => {
237 if first_error.is_none() {
238 first_error = Some(err);
239 }
240 }
241 }
107 } 242 }
108 243
109 if let Some(ret) = self.try_coerce_unsized(&from_ty, &to_ty) { 244 // Extract type or return an error. We return the first error
110 return ret; 245 // we got, which should be from relating the "base" type
246 // (e.g., in example above, the failure from relating `Vec<T>`
247 // to the target type), since that should be the least
248 // confusing.
249 let result = match found {
250 Some(d) => d,
251 None => {
252 let err = first_error.expect("coerce_borrowed_pointer had no error");
253 return Err(err);
254 }
255 };
256
257 Ok(result)
258 }
259
260 /// Attempts to coerce from the type of a Rust function item into a function pointer.
261 fn coerce_from_fn_item(&mut self, from_ty: Ty, to_ty: &Ty) -> InferResult {
262 match to_ty.kind(&Interner) {
263 TyKind::Function(_) => {
264 let from_sig = from_ty.callable_sig(self.db).expect("FnDef had no sig");
265
266 // FIXME check ABI: Intrinsics are not coercible to function pointers
267 // FIXME Safe `#[target_feature]` functions are not assignable to safe fn pointers (RFC 2396)
268
269 // FIXME rustc normalizes assoc types in the sig here, not sure if necessary
270
271 let from_sig = from_sig.to_fn_ptr();
272 let from_fn_pointer = TyKind::Function(from_sig.clone()).intern(&Interner);
273 let ok = self.coerce_from_safe_fn(from_fn_pointer, &from_sig, to_ty)?;
274
275 Ok(ok)
276 }
277 _ => self.table.try_unify(&from_ty, to_ty),
111 } 278 }
279 }
280
281 fn coerce_from_fn_pointer(
282 &mut self,
283 from_ty: Ty,
284 from_f: &FnPointer,
285 to_ty: &Ty,
286 ) -> InferResult {
287 self.coerce_from_safe_fn(from_ty, from_f, to_ty)
288 }
112 289
113 // Auto Deref if cannot coerce 290 fn coerce_from_safe_fn(
114 match (from_ty.kind(&Interner), to_ty.kind(&Interner)) { 291 &mut self,
115 // FIXME: DerefMut 292 from_ty: Ty,
116 (TyKind::Ref(.., st1), TyKind::Ref(.., st2)) => { 293 from_fn_ptr: &FnPointer,
117 self.unify_autoderef_behind_ref(st1, st2) 294 to_ty: &Ty,
295 ) -> InferResult {
296 if let TyKind::Function(to_fn_ptr) = to_ty.kind(&Interner) {
297 if let (chalk_ir::Safety::Safe, chalk_ir::Safety::Unsafe) =
298 (from_fn_ptr.sig.safety, to_fn_ptr.sig.safety)
299 {
300 let from_unsafe =
301 TyKind::Function(safe_to_unsafe_fn_ty(from_fn_ptr.clone())).intern(&Interner);
302 return self.table.try_unify(&from_unsafe, to_ty);
118 } 303 }
304 }
305 self.table.try_unify(&from_ty, to_ty)
306 }
119 307
120 // Otherwise, normal unify 308 /// Attempts to coerce from the type of a non-capturing closure into a
121 _ => self.unify(&from_ty, to_ty), 309 /// function pointer.
310 fn coerce_closure_to_fn(
311 &mut self,
312 from_ty: Ty,
313 from_substs: &Substitution,
314 to_ty: &Ty,
315 ) -> InferResult {
316 match to_ty.kind(&Interner) {
317 TyKind::Function(fn_ty) /* if from_substs is non-capturing (FIXME) */ => {
318 // We coerce the closure, which has fn type
319 // `extern "rust-call" fn((arg0,arg1,...)) -> _`
320 // to
321 // `fn(arg0,arg1,...) -> _`
322 // or
323 // `unsafe fn(arg0,arg1,...) -> _`
324 let safety = fn_ty.sig.safety;
325 let pointer_ty = coerce_closure_fn_ty(from_substs, safety);
326 self.table.try_unify(&pointer_ty, to_ty)
327 }
328 _ => self.table.try_unify(&from_ty, to_ty),
122 } 329 }
123 } 330 }
124 331
125 /// Coerce a type using `from_ty: CoerceUnsized<ty_ty>` 332 /// Coerce a type using `from_ty: CoerceUnsized<ty_ty>`
126 /// 333 ///
127 /// See: https://doc.rust-lang.org/nightly/std/marker/trait.CoerceUnsized.html 334 /// See: https://doc.rust-lang.org/nightly/std/marker/trait.CoerceUnsized.html
128 fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty) -> Option<bool> { 335 fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty) -> InferResult {
336 // These 'if' statements require some explanation.
337 // The `CoerceUnsized` trait is special - it is only
338 // possible to write `impl CoerceUnsized<B> for A` where
339 // A and B have 'matching' fields. This rules out the following
340 // two types of blanket impls:
341 //
342 // `impl<T> CoerceUnsized<T> for SomeType`
343 // `impl<T> CoerceUnsized<SomeType> for T`
344 //
345 // Both of these trigger a special `CoerceUnsized`-related error (E0376)
346 //
347 // We can take advantage of this fact to avoid performing unecessary work.
348 // If either `source` or `target` is a type variable, then any applicable impl
349 // would need to be generic over the self-type (`impl<T> CoerceUnsized<SomeType> for T`)
350 // or generic over the `CoerceUnsized` type parameter (`impl<T> CoerceUnsized<T> for
351 // SomeType`).
352 //
353 // However, these are exactly the kinds of impls which are forbidden by
354 // the compiler! Therefore, we can be sure that coercion will always fail
355 // when either the source or target type is a type variable. This allows us
356 // to skip performing any trait selection, and immediately bail out.
357 if from_ty.is_ty_var() {
358 return Err(TypeError);
359 }
360 if to_ty.is_ty_var() {
361 return Err(TypeError);
362 }
363
364 // Handle reborrows before trying to solve `Source: CoerceUnsized<Target>`.
365 let coerce_from = match (from_ty.kind(&Interner), to_ty.kind(&Interner)) {
366 (TyKind::Ref(from_mt, _, from_inner), TyKind::Ref(to_mt, _, _)) => {
367 coerce_mutabilities(*from_mt, *to_mt)?;
368
369 let lt = static_lifetime();
370 TyKind::Ref(*to_mt, lt, from_inner.clone()).intern(&Interner)
371 }
372 (TyKind::Ref(from_mt, _, from_inner), TyKind::Raw(to_mt, _)) => {
373 coerce_mutabilities(*from_mt, *to_mt)?;
374
375 TyKind::Raw(*to_mt, from_inner.clone()).intern(&Interner)
376 }
377 _ => from_ty.clone(),
378 };
379
129 let krate = self.resolver.krate().unwrap(); 380 let krate = self.resolver.krate().unwrap();
130 let coerce_unsized_trait = match self.db.lang_item(krate, "coerce_unsized".into()) { 381 let coerce_unsized_trait = match self.db.lang_item(krate, "coerce_unsized".into()) {
131 Some(LangItemTarget::TraitId(trait_)) => trait_, 382 Some(LangItemTarget::TraitId(trait_)) => trait_,
132 _ => return None, 383 _ => return Err(TypeError),
133 }; 384 };
134 385
135 let trait_ref = { 386 let trait_ref = {
136 let b = TyBuilder::trait_ref(self.db, coerce_unsized_trait); 387 let b = TyBuilder::trait_ref(self.db, coerce_unsized_trait);
137 if b.remaining() != 2 { 388 if b.remaining() != 2 {
138 // The CoerceUnsized trait should have two generic params: Self and T. 389 // The CoerceUnsized trait should have two generic params: Self and T.
139 return None; 390 return Err(TypeError);
140 } 391 }
141 b.push(from_ty.clone()).push(to_ty.clone()).build() 392 b.push(coerce_from.clone()).push(to_ty.clone()).build()
142 }; 393 };
143 394
144 let goal = InEnvironment::new(&self.trait_env.env, trait_ref.cast(&Interner)); 395 let goal: InEnvironment<DomainGoal> =
396 InEnvironment::new(&self.trait_env.env, trait_ref.cast(&Interner));
145 397
146 let canonicalizer = self.canonicalizer(); 398 let canonicalized = self.canonicalize(goal);
147 let canonicalized = canonicalizer.canonicalize_obligation(goal);
148 399
149 let solution = self.db.trait_solve(krate, canonicalized.value.clone())?; 400 // FIXME: rustc's coerce_unsized is more specialized -- it only tries to
401 // solve `CoerceUnsized` and `Unsize` goals at this point and leaves the
402 // rest for later. Also, there's some logic about sized type variables.
403 // Need to find out in what cases this is necessary
404 let solution = self
405 .db
406 .trait_solve(krate, canonicalized.value.clone().cast(&Interner))
407 .ok_or(TypeError)?;
150 408
151 match solution { 409 match solution {
152 Solution::Unique(v) => { 410 Solution::Unique(v) => {
153 canonicalized.apply_solution( 411 canonicalized.apply_solution(
154 self, 412 &mut self.table,
155 Canonical { 413 Canonical {
156 binders: v.binders, 414 binders: v.binders,
157 // FIXME handle constraints 415 // FIXME handle constraints
@@ -159,38 +417,40 @@ impl<'a> InferenceContext<'a> {
159 }, 417 },
160 ); 418 );
161 } 419 }
162 _ => return None, 420 // FIXME: should we accept ambiguous results here?
421 _ => return Err(TypeError),
163 }; 422 };
164 423
165 Some(true) 424 Ok(InferOk { goals: Vec::new() })
166 } 425 }
426}
167 427
168 /// Unify `from_ty` to `to_ty` with optional auto Deref 428fn coerce_closure_fn_ty(closure_substs: &Substitution, safety: chalk_ir::Safety) -> Ty {
169 /// 429 let closure_sig = closure_substs.at(&Interner, 0).assert_ty_ref(&Interner).clone();
170 /// Note that the parameters are already stripped the outer reference. 430 match closure_sig.kind(&Interner) {
171 fn unify_autoderef_behind_ref(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool { 431 TyKind::Function(fn_ty) => TyKind::Function(FnPointer {
172 let canonicalized = self.canonicalizer().canonicalize_ty(from_ty.clone()); 432 num_binders: fn_ty.num_binders,
173 let to_ty = self.resolve_ty_shallow(&to_ty); 433 sig: FnSig { safety, ..fn_ty.sig },
174 // FIXME: Auto DerefMut 434 substitution: fn_ty.substitution.clone(),
175 for derefed_ty in autoderef::autoderef( 435 })
176 self.db, 436 .intern(&Interner),
177 self.resolver.krate(), 437 _ => TyKind::Error.intern(&Interner),
178 InEnvironment { 438 }
179 goal: canonicalized.value.clone(), 439}
180 environment: self.trait_env.env.clone(), 440
181 }, 441fn safe_to_unsafe_fn_ty(fn_ty: FnPointer) -> FnPointer {
182 ) { 442 FnPointer {
183 let derefed_ty = canonicalized.decanonicalize_ty(derefed_ty.value); 443 num_binders: fn_ty.num_binders,
184 let from_ty = self.resolve_ty_shallow(&derefed_ty); 444 sig: FnSig { safety: chalk_ir::Safety::Unsafe, ..fn_ty.sig },
185 // Stop when constructor matches. 445 substitution: fn_ty.substitution,
186 if from_ty.equals_ctor(&to_ty) { 446 }
187 // It will not recurse to `coerce`. 447}
188 return self.table.unify(&from_ty, &to_ty);
189 } else if self.table.unify_inner_trivial(&derefed_ty, &to_ty, 0) {
190 return true;
191 }
192 }
193 448
194 false 449fn coerce_mutabilities(from: Mutability, to: Mutability) -> Result<(), TypeError> {
450 match (from, to) {
451 (Mutability::Mut, Mutability::Mut)
452 | (Mutability::Mut, Mutability::Not)
453 | (Mutability::Not, Mutability::Not) => Ok(()),
454 (Mutability::Not, Mutability::Mut) => Err(TypeError),
195 } 455 }
196} 456}
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index 7278faeec..08c05c67c 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -35,39 +35,43 @@ use super::{
35impl<'a> InferenceContext<'a> { 35impl<'a> InferenceContext<'a> {
36 pub(super) fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty { 36 pub(super) fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
37 let ty = self.infer_expr_inner(tgt_expr, expected); 37 let ty = self.infer_expr_inner(tgt_expr, expected);
38 if ty.is_never() { 38 if self.resolve_ty_shallow(&ty).is_never() {
39 // Any expression that produces a value of type `!` must have diverged 39 // Any expression that produces a value of type `!` must have diverged
40 self.diverges = Diverges::Always; 40 self.diverges = Diverges::Always;
41 } 41 }
42 let could_unify = self.unify(&ty, &expected.ty); 42 if let Some(expected_ty) = expected.only_has_type(&mut self.table) {
43 if !could_unify { 43 let could_unify = self.unify(&ty, &expected_ty);
44 self.result.type_mismatches.insert( 44 if !could_unify {
45 tgt_expr.into(), 45 self.result.type_mismatches.insert(
46 TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() }, 46 tgt_expr.into(),
47 ); 47 TypeMismatch { expected: expected_ty.clone(), actual: ty.clone() },
48 );
49 }
48 } 50 }
49 self.resolve_ty_as_possible(ty) 51 ty
50 } 52 }
51 53
52 /// Infer type of expression with possibly implicit coerce to the expected type. 54 /// Infer type of expression with possibly implicit coerce to the expected type.
53 /// Return the type after possible coercion. 55 /// Return the type after possible coercion.
54 pub(super) fn infer_expr_coerce(&mut self, expr: ExprId, expected: &Expectation) -> Ty { 56 pub(super) fn infer_expr_coerce(&mut self, expr: ExprId, expected: &Expectation) -> Ty {
55 let ty = self.infer_expr_inner(expr, &expected); 57 let ty = self.infer_expr_inner(expr, &expected);
56 let ty = if !self.coerce(&ty, &expected.coercion_target()) { 58 let ty = if let Some(target) = expected.only_has_type(&mut self.table) {
57 self.result.type_mismatches.insert( 59 if !self.coerce(&ty, &target) {
58 expr.into(), 60 self.result.type_mismatches.insert(
59 TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() }, 61 expr.into(),
60 ); 62 TypeMismatch { expected: target.clone(), actual: ty.clone() },
61 // Return actual type when type mismatch. 63 );
62 // This is needed for diagnostic when return type mismatch. 64 // Return actual type when type mismatch.
63 ty 65 // This is needed for diagnostic when return type mismatch.
64 } else if expected.coercion_target().is_unknown() { 66 ty
65 ty 67 } else {
68 target.clone()
69 }
66 } else { 70 } else {
67 expected.ty.clone() 71 ty
68 }; 72 };
69 73
70 self.resolve_ty_as_possible(ty) 74 ty
71 } 75 }
72 76
73 fn callable_sig_from_fn_trait(&mut self, ty: &Ty, num_args: usize) -> Option<(Vec<Ty>, Ty)> { 77 fn callable_sig_from_fn_trait(&mut self, ty: &Ty, num_args: usize) -> Option<(Vec<Ty>, Ty)> {
@@ -98,10 +102,10 @@ impl<'a> InferenceContext<'a> {
98 goal: projection.trait_ref(self.db).cast(&Interner), 102 goal: projection.trait_ref(self.db).cast(&Interner),
99 environment: trait_env, 103 environment: trait_env,
100 }; 104 };
101 let canonical = self.canonicalizer().canonicalize_obligation(obligation.clone()); 105 let canonical = self.canonicalize(obligation.clone());
102 if self.db.trait_solve(krate, canonical.value).is_some() { 106 if self.db.trait_solve(krate, canonical.value.cast(&Interner)).is_some() {
103 self.push_obligation(obligation.goal); 107 self.push_obligation(obligation.goal);
104 let return_ty = self.normalize_projection_ty(projection); 108 let return_ty = self.table.normalize_projection_ty(projection);
105 Some((arg_tys, return_ty)) 109 Some((arg_tys, return_ty))
106 } else { 110 } else {
107 None 111 None
@@ -131,17 +135,21 @@ impl<'a> InferenceContext<'a> {
131 let condition_diverges = mem::replace(&mut self.diverges, Diverges::Maybe); 135 let condition_diverges = mem::replace(&mut self.diverges, Diverges::Maybe);
132 let mut both_arms_diverge = Diverges::Always; 136 let mut both_arms_diverge = Diverges::Always;
133 137
138 let mut result_ty = self.table.new_type_var();
134 let then_ty = self.infer_expr_inner(*then_branch, &expected); 139 let then_ty = self.infer_expr_inner(*then_branch, &expected);
135 both_arms_diverge &= mem::replace(&mut self.diverges, Diverges::Maybe); 140 both_arms_diverge &= mem::replace(&mut self.diverges, Diverges::Maybe);
141 result_ty = self.coerce_merge_branch(Some(*then_branch), &result_ty, &then_ty);
136 let else_ty = match else_branch { 142 let else_ty = match else_branch {
137 Some(else_branch) => self.infer_expr_inner(*else_branch, &expected), 143 Some(else_branch) => self.infer_expr_inner(*else_branch, &expected),
138 None => TyBuilder::unit(), 144 None => TyBuilder::unit(),
139 }; 145 };
140 both_arms_diverge &= self.diverges; 146 both_arms_diverge &= self.diverges;
147 // FIXME: create a synthetic `else {}` so we have something to refer to here instead of None?
148 result_ty = self.coerce_merge_branch(*else_branch, &result_ty, &else_ty);
141 149
142 self.diverges = condition_diverges | both_arms_diverge; 150 self.diverges = condition_diverges | both_arms_diverge;
143 151
144 self.coerce_merge_branch(&then_ty, &else_ty) 152 result_ty
145 } 153 }
146 Expr::Block { statements, tail, label, id: _ } => { 154 Expr::Block { statements, tail, label, id: _ } => {
147 let old_resolver = mem::replace( 155 let old_resolver = mem::replace(
@@ -277,12 +285,13 @@ impl<'a> InferenceContext<'a> {
277 // Eagerly try to relate the closure type with the expected 285 // Eagerly try to relate the closure type with the expected
278 // type, otherwise we often won't have enough information to 286 // type, otherwise we often won't have enough information to
279 // infer the body. 287 // infer the body.
280 self.coerce(&closure_ty, &expected.ty); 288 if let Some(t) = expected.only_has_type(&mut self.table) {
289 self.coerce(&closure_ty, &t);
290 }
281 291
282 // Now go through the argument patterns 292 // Now go through the argument patterns
283 for (arg_pat, arg_ty) in args.iter().zip(sig_tys) { 293 for (arg_pat, arg_ty) in args.iter().zip(sig_tys) {
284 let resolved = self.resolve_ty_as_possible(arg_ty); 294 self.infer_pat(*arg_pat, &arg_ty, BindingMode::default());
285 self.infer_pat(*arg_pat, &resolved, BindingMode::default());
286 } 295 }
287 296
288 let prev_diverges = mem::replace(&mut self.diverges, Diverges::Maybe); 297 let prev_diverges = mem::replace(&mut self.diverges, Diverges::Maybe);
@@ -297,13 +306,13 @@ impl<'a> InferenceContext<'a> {
297 } 306 }
298 Expr::Call { callee, args } => { 307 Expr::Call { callee, args } => {
299 let callee_ty = self.infer_expr(*callee, &Expectation::none()); 308 let callee_ty = self.infer_expr(*callee, &Expectation::none());
300 let canonicalized = self.canonicalizer().canonicalize_ty(callee_ty.clone()); 309 let canonicalized = self.canonicalize(callee_ty.clone());
301 let mut derefs = autoderef( 310 let mut derefs = autoderef(
302 self.db, 311 self.db,
303 self.resolver.krate(), 312 self.resolver.krate(),
304 InEnvironment { 313 InEnvironment {
305 goal: canonicalized.value.clone(), 314 goal: canonicalized.value.clone(),
306 environment: self.trait_env.env.clone(), 315 environment: self.table.trait_env.env.clone(),
307 }, 316 },
308 ); 317 );
309 let (param_tys, ret_ty): (Vec<Ty>, Ty) = derefs 318 let (param_tys, ret_ty): (Vec<Ty>, Ty) = derefs
@@ -350,7 +359,7 @@ impl<'a> InferenceContext<'a> {
350 359
351 let arm_ty = self.infer_expr_inner(arm.expr, &expected); 360 let arm_ty = self.infer_expr_inner(arm.expr, &expected);
352 all_arms_diverge &= self.diverges; 361 all_arms_diverge &= self.diverges;
353 result_ty = self.coerce_merge_branch(&result_ty, &arm_ty); 362 result_ty = self.coerce_merge_branch(Some(arm.expr), &result_ty, &arm_ty);
354 } 363 }
355 364
356 self.diverges = matchee_diverges | all_arms_diverge; 365 self.diverges = matchee_diverges | all_arms_diverge;
@@ -364,12 +373,6 @@ impl<'a> InferenceContext<'a> {
364 } 373 }
365 Expr::Continue { .. } => TyKind::Never.intern(&Interner), 374 Expr::Continue { .. } => TyKind::Never.intern(&Interner),
366 Expr::Break { expr, label } => { 375 Expr::Break { expr, label } => {
367 let val_ty = if let Some(expr) = expr {
368 self.infer_expr(*expr, &Expectation::none())
369 } else {
370 TyBuilder::unit()
371 };
372
373 let last_ty = 376 let last_ty =
374 if let Some(ctxt) = find_breakable(&mut self.breakables, label.as_ref()) { 377 if let Some(ctxt) = find_breakable(&mut self.breakables, label.as_ref()) {
375 ctxt.break_ty.clone() 378 ctxt.break_ty.clone()
@@ -377,7 +380,14 @@ impl<'a> InferenceContext<'a> {
377 self.err_ty() 380 self.err_ty()
378 }; 381 };
379 382
380 let merged_type = self.coerce_merge_branch(&last_ty, &val_ty); 383 let val_ty = if let Some(expr) = expr {
384 self.infer_expr(*expr, &Expectation::none())
385 } else {
386 TyBuilder::unit()
387 };
388
389 // FIXME: create a synthetic `()` during lowering so we have something to refer to here?
390 let merged_type = self.coerce_merge_branch(*expr, &last_ty, &val_ty);
381 391
382 if let Some(ctxt) = find_breakable(&mut self.breakables, label.as_ref()) { 392 if let Some(ctxt) = find_breakable(&mut self.breakables, label.as_ref()) {
383 ctxt.break_ty = merged_type; 393 ctxt.break_ty = merged_type;
@@ -411,7 +421,9 @@ impl<'a> InferenceContext<'a> {
411 self.write_variant_resolution(tgt_expr.into(), variant); 421 self.write_variant_resolution(tgt_expr.into(), variant);
412 } 422 }
413 423
414 self.unify(&ty, &expected.ty); 424 if let Some(t) = expected.only_has_type(&mut self.table) {
425 self.unify(&ty, &t);
426 }
415 427
416 let substs = ty 428 let substs = ty
417 .as_adt() 429 .as_adt()
@@ -442,7 +454,7 @@ impl<'a> InferenceContext<'a> {
442 } 454 }
443 Expr::Field { expr, name } => { 455 Expr::Field { expr, name } => {
444 let receiver_ty = self.infer_expr_inner(*expr, &Expectation::none()); 456 let receiver_ty = self.infer_expr_inner(*expr, &Expectation::none());
445 let canonicalized = self.canonicalizer().canonicalize_ty(receiver_ty); 457 let canonicalized = self.canonicalize(receiver_ty);
446 let ty = autoderef::autoderef( 458 let ty = autoderef::autoderef(
447 self.db, 459 self.db,
448 self.resolver.krate(), 460 self.resolver.krate(),
@@ -514,6 +526,7 @@ impl<'a> InferenceContext<'a> {
514 self.resolve_associated_type(inner_ty, self.resolve_ops_try_ok()) 526 self.resolve_associated_type(inner_ty, self.resolve_ops_try_ok())
515 } 527 }
516 Expr::Cast { expr, type_ref } => { 528 Expr::Cast { expr, type_ref } => {
529 // FIXME: propagate the "castable to" expectation (and find a test case that shows this is necessary)
517 let _inner_ty = self.infer_expr_inner(*expr, &Expectation::none()); 530 let _inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
518 let cast_ty = self.make_ty(type_ref); 531 let cast_ty = self.make_ty(type_ref);
519 // FIXME check the cast... 532 // FIXME check the cast...
@@ -521,15 +534,17 @@ impl<'a> InferenceContext<'a> {
521 } 534 }
522 Expr::Ref { expr, rawness, mutability } => { 535 Expr::Ref { expr, rawness, mutability } => {
523 let mutability = lower_to_chalk_mutability(*mutability); 536 let mutability = lower_to_chalk_mutability(*mutability);
524 let expectation = if let Some((exp_inner, exp_rawness, exp_mutability)) = 537 let expectation = if let Some((exp_inner, exp_rawness, exp_mutability)) = expected
525 &expected.ty.as_reference_or_ptr() 538 .only_has_type(&mut self.table)
539 .as_ref()
540 .and_then(|t| t.as_reference_or_ptr())
526 { 541 {
527 if *exp_mutability == Mutability::Mut && mutability == Mutability::Not { 542 if exp_mutability == Mutability::Mut && mutability == Mutability::Not {
528 // FIXME: throw type error - expected mut reference but found shared ref, 543 // FIXME: record type error - expected mut reference but found shared ref,
529 // which cannot be coerced 544 // which cannot be coerced
530 } 545 }
531 if *exp_rawness == Rawness::Ref && *rawness == Rawness::RawPtr { 546 if exp_rawness == Rawness::Ref && *rawness == Rawness::RawPtr {
532 // FIXME: throw type error - expected reference but found ptr, 547 // FIXME: record type error - expected reference but found ptr,
533 // which cannot be coerced 548 // which cannot be coerced
534 } 549 }
535 Expectation::rvalue_hint(Ty::clone(exp_inner)) 550 Expectation::rvalue_hint(Ty::clone(exp_inner))
@@ -556,10 +571,11 @@ impl<'a> InferenceContext<'a> {
556 } 571 }
557 Expr::UnaryOp { expr, op } => { 572 Expr::UnaryOp { expr, op } => {
558 let inner_ty = self.infer_expr_inner(*expr, &Expectation::none()); 573 let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
574 let inner_ty = self.resolve_ty_shallow(&inner_ty);
559 match op { 575 match op {
560 UnaryOp::Deref => match self.resolver.krate() { 576 UnaryOp::Deref => match self.resolver.krate() {
561 Some(krate) => { 577 Some(krate) => {
562 let canonicalized = self.canonicalizer().canonicalize_ty(inner_ty); 578 let canonicalized = self.canonicalize(inner_ty);
563 match autoderef::deref( 579 match autoderef::deref(
564 self.db, 580 self.db,
565 krate, 581 krate,
@@ -612,8 +628,10 @@ impl<'a> InferenceContext<'a> {
612 _ => Expectation::none(), 628 _ => Expectation::none(),
613 }; 629 };
614 let lhs_ty = self.infer_expr(*lhs, &lhs_expectation); 630 let lhs_ty = self.infer_expr(*lhs, &lhs_expectation);
631 let lhs_ty = self.resolve_ty_shallow(&lhs_ty);
615 let rhs_expectation = op::binary_op_rhs_expectation(*op, lhs_ty.clone()); 632 let rhs_expectation = op::binary_op_rhs_expectation(*op, lhs_ty.clone());
616 let rhs_ty = self.infer_expr(*rhs, &Expectation::has_type(rhs_expectation)); 633 let rhs_ty = self.infer_expr(*rhs, &Expectation::has_type(rhs_expectation));
634 let rhs_ty = self.resolve_ty_shallow(&rhs_ty);
617 635
618 let ret = op::binary_op_return_ty(*op, lhs_ty.clone(), rhs_ty.clone()); 636 let ret = op::binary_op_return_ty(*op, lhs_ty.clone(), rhs_ty.clone());
619 637
@@ -676,7 +694,7 @@ impl<'a> InferenceContext<'a> {
676 if let (Some(index_trait), Some(krate)) = 694 if let (Some(index_trait), Some(krate)) =
677 (self.resolve_ops_index(), self.resolver.krate()) 695 (self.resolve_ops_index(), self.resolver.krate())
678 { 696 {
679 let canonicalized = self.canonicalizer().canonicalize_ty(base_ty); 697 let canonicalized = self.canonicalize(base_ty);
680 let self_ty = method_resolution::resolve_indexing_op( 698 let self_ty = method_resolution::resolve_indexing_op(
681 self.db, 699 self.db,
682 &canonicalized.value, 700 &canonicalized.value,
@@ -696,8 +714,12 @@ impl<'a> InferenceContext<'a> {
696 } 714 }
697 } 715 }
698 Expr::Tuple { exprs } => { 716 Expr::Tuple { exprs } => {
699 let mut tys = match expected.ty.kind(&Interner) { 717 let mut tys = match expected
700 TyKind::Tuple(_, substs) => substs 718 .only_has_type(&mut self.table)
719 .as_ref()
720 .map(|t| t.kind(&Interner))
721 {
722 Some(TyKind::Tuple(_, substs)) => substs
701 .iter(&Interner) 723 .iter(&Interner)
702 .map(|a| a.assert_ty_ref(&Interner).clone()) 724 .map(|a| a.assert_ty_ref(&Interner).clone())
703 .chain(repeat_with(|| self.table.new_type_var())) 725 .chain(repeat_with(|| self.table.new_type_var()))
@@ -713,14 +735,16 @@ impl<'a> InferenceContext<'a> {
713 TyKind::Tuple(tys.len(), Substitution::from_iter(&Interner, tys)).intern(&Interner) 735 TyKind::Tuple(tys.len(), Substitution::from_iter(&Interner, tys)).intern(&Interner)
714 } 736 }
715 Expr::Array(array) => { 737 Expr::Array(array) => {
716 let elem_ty = match expected.ty.kind(&Interner) { 738 let elem_ty =
717 TyKind::Array(st, _) | TyKind::Slice(st) => st.clone(), 739 match expected.to_option(&mut self.table).as_ref().map(|t| t.kind(&Interner)) {
718 _ => self.table.new_type_var(), 740 Some(TyKind::Array(st, _)) | Some(TyKind::Slice(st)) => st.clone(),
719 }; 741 _ => self.table.new_type_var(),
742 };
720 743
721 let len = match array { 744 let len = match array {
722 Array::ElementList(items) => { 745 Array::ElementList(items) => {
723 for expr in items.iter() { 746 for expr in items.iter() {
747 // FIXME: use CoerceMany (coerce_merge_branch)
724 self.infer_expr_coerce(*expr, &Expectation::has_type(elem_ty.clone())); 748 self.infer_expr_coerce(*expr, &Expectation::has_type(elem_ty.clone()));
725 } 749 }
726 Some(items.len() as u64) 750 Some(items.len() as u64)
@@ -785,7 +809,6 @@ impl<'a> InferenceContext<'a> {
785 }; 809 };
786 // use a new type variable if we got unknown here 810 // use a new type variable if we got unknown here
787 let ty = self.insert_type_vars_shallow(ty); 811 let ty = self.insert_type_vars_shallow(ty);
788 let ty = self.resolve_ty_as_possible(ty);
789 self.write_expr_ty(tgt_expr, ty.clone()); 812 self.write_expr_ty(tgt_expr, ty.clone());
790 ty 813 ty
791 } 814 }
@@ -813,7 +836,6 @@ impl<'a> InferenceContext<'a> {
813 } 836 }
814 } 837 }
815 838
816 let ty = self.resolve_ty_as_possible(ty);
817 self.infer_pat(*pat, &ty, BindingMode::default()); 839 self.infer_pat(*pat, &ty, BindingMode::default());
818 } 840 }
819 Statement::Expr { expr, .. } => { 841 Statement::Expr { expr, .. } => {
@@ -836,7 +858,9 @@ impl<'a> InferenceContext<'a> {
836 // we don't even make an attempt at coercion 858 // we don't even make an attempt at coercion
837 self.table.new_maybe_never_var() 859 self.table.new_maybe_never_var()
838 } else { 860 } else {
839 self.coerce(&TyBuilder::unit(), &expected.coercion_target()); 861 if let Some(t) = expected.only_has_type(&mut self.table) {
862 self.coerce(&TyBuilder::unit(), &t);
863 }
840 TyBuilder::unit() 864 TyBuilder::unit()
841 } 865 }
842 }; 866 };
@@ -852,7 +876,7 @@ impl<'a> InferenceContext<'a> {
852 generic_args: Option<&GenericArgs>, 876 generic_args: Option<&GenericArgs>,
853 ) -> Ty { 877 ) -> Ty {
854 let receiver_ty = self.infer_expr(receiver, &Expectation::none()); 878 let receiver_ty = self.infer_expr(receiver, &Expectation::none());
855 let canonicalized_receiver = self.canonicalizer().canonicalize_ty(receiver_ty.clone()); 879 let canonicalized_receiver = self.canonicalize(receiver_ty.clone());
856 880
857 let traits_in_scope = self.resolver.traits_in_scope(self.db.upcast()); 881 let traits_in_scope = self.resolver.traits_in_scope(self.db.upcast());
858 882
@@ -891,7 +915,8 @@ impl<'a> InferenceContext<'a> {
891 }; 915 };
892 // Apply autoref so the below unification works correctly 916 // Apply autoref so the below unification works correctly
893 // FIXME: return correct autorefs from lookup_method 917 // FIXME: return correct autorefs from lookup_method
894 let actual_receiver_ty = match expected_receiver_ty.as_reference() { 918 let actual_receiver_ty = match self.resolve_ty_shallow(&expected_receiver_ty).as_reference()
919 {
895 Some((_, lifetime, mutability)) => { 920 Some((_, lifetime, mutability)) => {
896 TyKind::Ref(mutability, lifetime, derefed_receiver_ty).intern(&Interner) 921 TyKind::Ref(mutability, lifetime, derefed_receiver_ty).intern(&Interner)
897 } 922 }
@@ -971,6 +996,7 @@ impl<'a> InferenceContext<'a> {
971 } 996 }
972 997
973 fn register_obligations_for_call(&mut self, callable_ty: &Ty) { 998 fn register_obligations_for_call(&mut self, callable_ty: &Ty) {
999 let callable_ty = self.resolve_ty_shallow(&callable_ty);
974 if let TyKind::FnDef(fn_def, parameters) = callable_ty.kind(&Interner) { 1000 if let TyKind::FnDef(fn_def, parameters) = callable_ty.kind(&Interner) {
975 let def: CallableDefId = from_chalk(self.db, *fn_def); 1001 let def: CallableDefId = from_chalk(self.db, *fn_def);
976 let generic_predicates = self.db.generic_predicates(def.into()); 1002 let generic_predicates = self.db.generic_predicates(def.into());
diff --git a/crates/hir_ty/src/infer/pat.rs b/crates/hir_ty/src/infer/pat.rs
index b15f4977d..9c8e3b6ae 100644
--- a/crates/hir_ty/src/infer/pat.rs
+++ b/crates/hir_ty/src/infer/pat.rs
@@ -94,14 +94,15 @@ impl<'a> InferenceContext<'a> {
94 pub(super) fn infer_pat( 94 pub(super) fn infer_pat(
95 &mut self, 95 &mut self,
96 pat: PatId, 96 pat: PatId,
97 mut expected: &Ty, 97 expected: &Ty,
98 mut default_bm: BindingMode, 98 mut default_bm: BindingMode,
99 ) -> Ty { 99 ) -> Ty {
100 let body = Arc::clone(&self.body); // avoid borrow checker problem 100 let body = Arc::clone(&self.body); // avoid borrow checker problem
101 let mut expected = self.resolve_ty_shallow(expected);
101 102
102 if is_non_ref_pat(&body, pat) { 103 if is_non_ref_pat(&body, pat) {
103 while let Some((inner, _lifetime, mutability)) = expected.as_reference() { 104 while let Some((inner, _lifetime, mutability)) = expected.as_reference() {
104 expected = inner; 105 expected = self.resolve_ty_shallow(inner);
105 default_bm = match default_bm { 106 default_bm = match default_bm {
106 BindingMode::Move => BindingMode::Ref(mutability), 107 BindingMode::Move => BindingMode::Ref(mutability),
107 BindingMode::Ref(Mutability::Not) => BindingMode::Ref(Mutability::Not), 108 BindingMode::Ref(Mutability::Not) => BindingMode::Ref(Mutability::Not),
@@ -147,9 +148,9 @@ impl<'a> InferenceContext<'a> {
147 } 148 }
148 Pat::Or(ref pats) => { 149 Pat::Or(ref pats) => {
149 if let Some((first_pat, rest)) = pats.split_first() { 150 if let Some((first_pat, rest)) = pats.split_first() {
150 let ty = self.infer_pat(*first_pat, expected, default_bm); 151 let ty = self.infer_pat(*first_pat, &expected, default_bm);
151 for pat in rest { 152 for pat in rest {
152 self.infer_pat(*pat, expected, default_bm); 153 self.infer_pat(*pat, &expected, default_bm);
153 } 154 }
154 ty 155 ty
155 } else { 156 } else {
@@ -173,13 +174,13 @@ impl<'a> InferenceContext<'a> {
173 Pat::TupleStruct { path: p, args: subpats, ellipsis } => self.infer_tuple_struct_pat( 174 Pat::TupleStruct { path: p, args: subpats, ellipsis } => self.infer_tuple_struct_pat(
174 p.as_deref(), 175 p.as_deref(),
175 subpats, 176 subpats,
176 expected, 177 &expected,
177 default_bm, 178 default_bm,
178 pat, 179 pat,
179 *ellipsis, 180 *ellipsis,
180 ), 181 ),
181 Pat::Record { path: p, args: fields, ellipsis: _ } => { 182 Pat::Record { path: p, args: fields, ellipsis: _ } => {
182 self.infer_record_pat(p.as_deref(), fields, expected, default_bm, pat) 183 self.infer_record_pat(p.as_deref(), fields, &expected, default_bm, pat)
183 } 184 }
184 Pat::Path(path) => { 185 Pat::Path(path) => {
185 // FIXME use correct resolver for the surrounding expression 186 // FIXME use correct resolver for the surrounding expression
@@ -193,7 +194,7 @@ impl<'a> InferenceContext<'a> {
193 BindingMode::convert(*mode) 194 BindingMode::convert(*mode)
194 }; 195 };
195 let inner_ty = if let Some(subpat) = subpat { 196 let inner_ty = if let Some(subpat) = subpat {
196 self.infer_pat(*subpat, expected, default_bm) 197 self.infer_pat(*subpat, &expected, default_bm)
197 } else { 198 } else {
198 expected.clone() 199 expected.clone()
199 }; 200 };
@@ -206,7 +207,6 @@ impl<'a> InferenceContext<'a> {
206 } 207 }
207 BindingMode::Move => inner_ty.clone(), 208 BindingMode::Move => inner_ty.clone(),
208 }; 209 };
209 let bound_ty = self.resolve_ty_as_possible(bound_ty);
210 self.write_pat_ty(pat, bound_ty); 210 self.write_pat_ty(pat, bound_ty);
211 return inner_ty; 211 return inner_ty;
212 } 212 }
@@ -265,13 +265,12 @@ impl<'a> InferenceContext<'a> {
265 }; 265 };
266 // use a new type variable if we got error type here 266 // use a new type variable if we got error type here
267 let ty = self.insert_type_vars_shallow(ty); 267 let ty = self.insert_type_vars_shallow(ty);
268 if !self.unify(&ty, expected) { 268 if !self.unify(&ty, &expected) {
269 self.result.type_mismatches.insert( 269 self.result.type_mismatches.insert(
270 pat.into(), 270 pat.into(),
271 TypeMismatch { expected: expected.clone(), actual: ty.clone() }, 271 TypeMismatch { expected: expected.clone(), actual: ty.clone() },
272 ); 272 );
273 } 273 }
274 let ty = self.resolve_ty_as_possible(ty);
275 self.write_pat_ty(pat, ty.clone()); 274 self.write_pat_ty(pat, ty.clone());
276 ty 275 ty
277 } 276 }
diff --git a/crates/hir_ty/src/infer/path.rs b/crates/hir_ty/src/infer/path.rs
index 495282eba..14c99eafd 100644
--- a/crates/hir_ty/src/infer/path.rs
+++ b/crates/hir_ty/src/infer/path.rs
@@ -65,7 +65,6 @@ impl<'a> InferenceContext<'a> {
65 let typable: ValueTyDefId = match value { 65 let typable: ValueTyDefId = match value {
66 ValueNs::LocalBinding(pat) => { 66 ValueNs::LocalBinding(pat) => {
67 let ty = self.result.type_of_pat.get(pat)?.clone(); 67 let ty = self.result.type_of_pat.get(pat)?.clone();
68 let ty = self.resolve_ty_as_possible(ty);
69 return Some(ty); 68 return Some(ty);
70 } 69 }
71 ValueNs::FunctionId(it) => it.into(), 70 ValueNs::FunctionId(it) => it.into(),
@@ -218,14 +217,14 @@ impl<'a> InferenceContext<'a> {
218 return Some(result); 217 return Some(result);
219 } 218 }
220 219
221 let canonical_ty = self.canonicalizer().canonicalize_ty(ty.clone()); 220 let canonical_ty = self.canonicalize(ty.clone());
222 let krate = self.resolver.krate()?; 221 let krate = self.resolver.krate()?;
223 let traits_in_scope = self.resolver.traits_in_scope(self.db.upcast()); 222 let traits_in_scope = self.resolver.traits_in_scope(self.db.upcast());
224 223
225 method_resolution::iterate_method_candidates( 224 method_resolution::iterate_method_candidates(
226 &canonical_ty.value, 225 &canonical_ty.value,
227 self.db, 226 self.db,
228 self.trait_env.clone(), 227 self.table.trait_env.clone(),
229 krate, 228 krate,
230 &traits_in_scope, 229 &traits_in_scope,
231 None, 230 None,
@@ -275,6 +274,7 @@ impl<'a> InferenceContext<'a> {
275 name: &Name, 274 name: &Name,
276 id: ExprOrPatId, 275 id: ExprOrPatId,
277 ) -> Option<(ValueNs, Option<Substitution>)> { 276 ) -> Option<(ValueNs, Option<Substitution>)> {
277 let ty = self.resolve_ty_shallow(ty);
278 let (enum_id, subst) = match ty.as_adt() { 278 let (enum_id, subst) = match ty.as_adt() {
279 Some((AdtId::EnumId(e), subst)) => (e, subst), 279 Some((AdtId::EnumId(e), subst)) => (e, subst),
280 _ => return None, 280 _ => return None,
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index d8e0b4320..21d3fb54e 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -1,177 +1,95 @@
1//! Unification and canonicalization logic. 1//! Unification and canonicalization logic.
2 2
3use std::borrow::Cow; 3use std::{fmt, mem, sync::Arc};
4 4
5use chalk_ir::{ 5use chalk_ir::{
6 cast::Cast, fold::Fold, interner::HasInterner, FloatTy, IntTy, TyVariableKind, UniverseIndex, 6 cast::Cast, fold::Fold, interner::HasInterner, zip::Zip, FloatTy, IntTy, TyVariableKind,
7 VariableKind, 7 UniverseIndex,
8}; 8};
9use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; 9use chalk_solve::infer::ParameterEnaVariableExt;
10use ena::unify::UnifyKey;
10 11
11use super::{DomainGoal, InferenceContext}; 12use super::{InferOk, InferResult, InferenceContext, TypeError};
12use crate::{ 13use crate::{
13 fold_tys, static_lifetime, AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, 14 db::HirDatabase, fold_tys, static_lifetime, AliasEq, AliasTy, BoundVar, Canonical,
14 DebruijnIndex, FnPointer, FnSubst, InEnvironment, InferenceVar, Interner, Scalar, Substitution, 15 DebruijnIndex, GenericArg, Goal, Guidance, InEnvironment, InferenceVar, Interner, ProjectionTy,
15 Ty, TyExt, TyKind, WhereClause, 16 Scalar, Solution, Substitution, TraitEnvironment, Ty, TyKind, VariableKind,
16}; 17};
17 18
18impl<'a> InferenceContext<'a> { 19impl<'a> InferenceContext<'a> {
19 pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b> 20 pub(super) fn canonicalize<T: Fold<Interner> + HasInterner<Interner = Interner>>(
21 &mut self,
22 t: T,
23 ) -> Canonicalized<T::Result>
20 where 24 where
21 'a: 'b, 25 T::Result: HasInterner<Interner = Interner>,
22 { 26 {
23 Canonicalizer { ctx: self, free_vars: Vec::new(), var_stack: Vec::new() } 27 // try to resolve obligations before canonicalizing, since this might
28 // result in new knowledge about variables
29 self.resolve_obligations_as_possible();
30 self.table.canonicalize(t)
24 } 31 }
25} 32}
26 33
27pub(super) struct Canonicalizer<'a, 'b> 34#[derive(Debug, Clone)]
28where
29 'a: 'b,
30{
31 ctx: &'b mut InferenceContext<'a>,
32 free_vars: Vec<(InferenceVar, TyVariableKind)>,
33 /// A stack of type variables that is used to detect recursive types (which
34 /// are an error, but we need to protect against them to avoid stack
35 /// overflows).
36 var_stack: Vec<TypeVarId>,
37}
38
39#[derive(Debug)]
40pub(super) struct Canonicalized<T> 35pub(super) struct Canonicalized<T>
41where 36where
42 T: HasInterner<Interner = Interner>, 37 T: HasInterner<Interner = Interner>,
43{ 38{
44 pub(super) value: Canonical<T>, 39 pub(super) value: Canonical<T>,
45 free_vars: Vec<(InferenceVar, TyVariableKind)>, 40 free_vars: Vec<GenericArg>,
46}
47
48impl<'a, 'b> Canonicalizer<'a, 'b> {
49 fn add(&mut self, free_var: InferenceVar, kind: TyVariableKind) -> usize {
50 self.free_vars.iter().position(|&(v, _)| v == free_var).unwrap_or_else(|| {
51 let next_index = self.free_vars.len();
52 self.free_vars.push((free_var, kind));
53 next_index
54 })
55 }
56
57 fn do_canonicalize<T: Fold<Interner, Result = T> + HasInterner<Interner = Interner>>(
58 &mut self,
59 t: T,
60 binders: DebruijnIndex,
61 ) -> T {
62 fold_tys(
63 t,
64 |ty, binders| match ty.kind(&Interner) {
65 &TyKind::InferenceVar(var, kind) => {
66 let inner = from_inference_var(var);
67 if self.var_stack.contains(&inner) {
68 // recursive type
69 return self.ctx.table.type_variable_table.fallback_value(var, kind);
70 }
71 if let Some(known_ty) =
72 self.ctx.table.var_unification_table.inlined_probe_value(inner).known()
73 {
74 self.var_stack.push(inner);
75 let result = self.do_canonicalize(known_ty.clone(), binders);
76 self.var_stack.pop();
77 result
78 } else {
79 let root = self.ctx.table.var_unification_table.find(inner);
80 let position = self.add(to_inference_var(root), kind);
81 TyKind::BoundVar(BoundVar::new(binders, position)).intern(&Interner)
82 }
83 }
84 _ => ty,
85 },
86 binders,
87 )
88 }
89
90 fn into_canonicalized<T: HasInterner<Interner = Interner>>(
91 self,
92 result: T,
93 ) -> Canonicalized<T> {
94 let kinds = self
95 .free_vars
96 .iter()
97 .map(|&(_, k)| chalk_ir::WithKind::new(VariableKind::Ty(k), UniverseIndex::ROOT));
98 Canonicalized {
99 value: Canonical {
100 value: result,
101 binders: CanonicalVarKinds::from_iter(&Interner, kinds),
102 },
103 free_vars: self.free_vars,
104 }
105 }
106
107 pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> {
108 let result = self.do_canonicalize(ty, DebruijnIndex::INNERMOST);
109 self.into_canonicalized(result)
110 }
111
112 pub(crate) fn canonicalize_obligation(
113 mut self,
114 obligation: InEnvironment<DomainGoal>,
115 ) -> Canonicalized<InEnvironment<DomainGoal>> {
116 let result = match obligation.goal {
117 DomainGoal::Holds(wc) => {
118 DomainGoal::Holds(self.do_canonicalize(wc, DebruijnIndex::INNERMOST))
119 }
120 _ => unimplemented!(),
121 };
122 self.into_canonicalized(InEnvironment { goal: result, environment: obligation.environment })
123 }
124} 41}
125 42
126impl<T: HasInterner<Interner = Interner>> Canonicalized<T> { 43impl<T: HasInterner<Interner = Interner>> Canonicalized<T> {
127 pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty { 44 pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty {
128 crate::fold_free_vars(ty, |bound, _binders| { 45 chalk_ir::Substitute::apply(&self.free_vars, ty, &Interner)
129 let (v, k) = self.free_vars[bound.index];
130 TyKind::InferenceVar(v, k).intern(&Interner)
131 })
132 } 46 }
133 47
134 pub(super) fn apply_solution( 48 pub(super) fn apply_solution(
135 &self, 49 &self,
136 ctx: &mut InferenceContext<'_>, 50 ctx: &mut InferenceTable,
137 solution: Canonical<Substitution>, 51 solution: Canonical<Substitution>,
138 ) { 52 ) {
139 // the solution may contain new variables, which we need to convert to new inference vars 53 // the solution may contain new variables, which we need to convert to new inference vars
140 let new_vars = Substitution::from_iter( 54 let new_vars = Substitution::from_iter(
141 &Interner, 55 &Interner,
142 solution.binders.iter(&Interner).map(|k| match k.kind { 56 solution.binders.iter(&Interner).map(|k| match k.kind {
143 VariableKind::Ty(TyVariableKind::General) => { 57 VariableKind::Ty(TyVariableKind::General) => ctx.new_type_var().cast(&Interner),
144 ctx.table.new_type_var().cast(&Interner) 58 VariableKind::Ty(TyVariableKind::Integer) => ctx.new_integer_var().cast(&Interner),
145 } 59 VariableKind::Ty(TyVariableKind::Float) => ctx.new_float_var().cast(&Interner),
146 VariableKind::Ty(TyVariableKind::Integer) => {
147 ctx.table.new_integer_var().cast(&Interner)
148 }
149 VariableKind::Ty(TyVariableKind::Float) => {
150 ctx.table.new_float_var().cast(&Interner)
151 }
152 // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere 60 // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere
153 VariableKind::Lifetime => static_lifetime().cast(&Interner), 61 VariableKind::Lifetime => static_lifetime().cast(&Interner),
154 _ => panic!("const variable in solution"), 62 _ => panic!("const variable in solution"),
155 }), 63 }),
156 ); 64 );
157 for (i, ty) in solution.value.iter(&Interner).enumerate() { 65 for (i, v) in solution.value.iter(&Interner).enumerate() {
158 let (v, k) = self.free_vars[i]; 66 let var = self.free_vars[i].clone();
159 // eagerly replace projections in the type; we may be getting types 67 if let Some(ty) = v.ty(&Interner) {
160 // e.g. from where clauses where this hasn't happened yet 68 // eagerly replace projections in the type; we may be getting types
161 let ty = ctx.normalize_associated_types_in( 69 // e.g. from where clauses where this hasn't happened yet
162 new_vars.apply(ty.assert_ty_ref(&Interner).clone(), &Interner), 70 let ty = ctx.normalize_associated_types_in(new_vars.apply(ty.clone(), &Interner));
163 ); 71 ctx.unify(var.assert_ty_ref(&Interner), &ty);
164 ctx.table.unify(&TyKind::InferenceVar(v, k).intern(&Interner), &ty); 72 } else {
73 let _ = ctx.try_unify(&var, &new_vars.apply(v.clone(), &Interner));
74 }
165 } 75 }
166 } 76 }
167} 77}
168 78
169pub fn could_unify(t1: &Ty, t2: &Ty) -> bool { 79pub fn could_unify(
170 InferenceTable::new().unify(t1, t2) 80 db: &dyn HirDatabase,
81 env: Arc<TraitEnvironment>,
82 tys: &Canonical<(Ty, Ty)>,
83) -> bool {
84 unify(db, env, tys).is_some()
171} 85}
172 86
173pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> { 87pub(crate) fn unify(
174 let mut table = InferenceTable::new(); 88 db: &dyn HirDatabase,
89 env: Arc<TraitEnvironment>,
90 tys: &Canonical<(Ty, Ty)>,
91) -> Option<Substitution> {
92 let mut table = InferenceTable::new(db, env);
175 let vars = Substitution::from_iter( 93 let vars = Substitution::from_iter(
176 &Interner, 94 &Interner,
177 tys.binders 95 tys.binders
@@ -187,77 +105,151 @@ pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> {
187 } 105 }
188 // default any type vars that weren't unified back to their original bound vars 106 // default any type vars that weren't unified back to their original bound vars
189 // (kind of hacky) 107 // (kind of hacky)
190 for (i, var) in vars.iter(&Interner).enumerate() { 108 let find_var = |iv| {
191 let var = var.assert_ty_ref(&Interner); 109 vars.iter(&Interner).position(|v| match v.interned() {
192 if &*table.resolve_ty_shallow(var) == var { 110 chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(&Interner),
193 table.unify( 111 chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(&Interner),
194 var, 112 chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner),
195 &TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, i)).intern(&Interner), 113 } == Some(iv))
196 ); 114 };
197 } 115 let fallback = |iv, kind, default, binder| match kind {
198 } 116 chalk_ir::VariableKind::Ty(_ty_kind) => find_var(iv)
117 .map_or(default, |i| BoundVar::new(binder, i).to_ty(&Interner).cast(&Interner)),
118 chalk_ir::VariableKind::Lifetime => find_var(iv)
119 .map_or(default, |i| BoundVar::new(binder, i).to_lifetime(&Interner).cast(&Interner)),
120 chalk_ir::VariableKind::Const(ty) => find_var(iv)
121 .map_or(default, |i| BoundVar::new(binder, i).to_const(&Interner, ty).cast(&Interner)),
122 };
199 Some(Substitution::from_iter( 123 Some(Substitution::from_iter(
200 &Interner, 124 &Interner,
201 vars.iter(&Interner) 125 vars.iter(&Interner)
202 .map(|v| table.resolve_ty_completely(v.assert_ty_ref(&Interner).clone())), 126 .map(|v| table.resolve_with_fallback(v.assert_ty_ref(&Interner).clone(), fallback)),
203 )) 127 ))
204} 128}
205 129
206#[derive(Clone, Debug)] 130#[derive(Copy, Clone, Debug)]
207pub(super) struct TypeVariableTable { 131pub(crate) struct TypeVariableData {
208 inner: Vec<TypeVariableData>, 132 diverging: bool,
209} 133}
210 134
211impl TypeVariableTable { 135type ChalkInferenceTable = chalk_solve::infer::InferenceTable<Interner>;
212 fn push(&mut self, data: TypeVariableData) { 136
213 self.inner.push(data); 137#[derive(Clone)]
138pub(crate) struct InferenceTable<'a> {
139 pub(crate) db: &'a dyn HirDatabase,
140 pub(crate) trait_env: Arc<TraitEnvironment>,
141 var_unification_table: ChalkInferenceTable,
142 type_variable_table: Vec<TypeVariableData>,
143 pending_obligations: Vec<Canonicalized<InEnvironment<Goal>>>,
144}
145
146impl<'a> InferenceTable<'a> {
147 pub(crate) fn new(db: &'a dyn HirDatabase, trait_env: Arc<TraitEnvironment>) -> Self {
148 InferenceTable {
149 db,
150 trait_env,
151 var_unification_table: ChalkInferenceTable::new(),
152 type_variable_table: Vec::new(),
153 pending_obligations: Vec::new(),
154 }
214 } 155 }
215 156
216 pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) { 157 /// Chalk doesn't know about the `diverging` flag, so when it unifies two
217 self.inner[from_inference_var(iv).0 as usize].diverging = diverging; 158 /// type variables of which one is diverging, the chosen root might not be
159 /// diverging and we have no way of marking it as such at that time. This
160 /// function goes through all type variables and make sure their root is
161 /// marked as diverging if necessary, so that resolving them gives the right
162 /// result.
163 pub(super) fn propagate_diverging_flag(&mut self) {
164 for i in 0..self.type_variable_table.len() {
165 if !self.type_variable_table[i].diverging {
166 continue;
167 }
168 let v = InferenceVar::from(i as u32);
169 let root = self.var_unification_table.inference_var_root(v);
170 if let Some(data) = self.type_variable_table.get_mut(root.index() as usize) {
171 data.diverging = true;
172 }
173 }
218 } 174 }
219 175
220 fn is_diverging(&mut self, iv: InferenceVar) -> bool { 176 pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) {
221 self.inner[from_inference_var(iv).0 as usize].diverging 177 self.type_variable_table[iv.index() as usize].diverging = diverging;
222 } 178 }
223 179
224 fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty { 180 fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty {
225 match kind { 181 match kind {
226 _ if self.inner[from_inference_var(iv).0 as usize].diverging => TyKind::Never, 182 _ if self
183 .type_variable_table
184 .get(iv.index() as usize)
185 .map_or(false, |data| data.diverging) =>
186 {
187 TyKind::Never
188 }
227 TyVariableKind::General => TyKind::Error, 189 TyVariableKind::General => TyKind::Error,
228 TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)), 190 TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)),
229 TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)), 191 TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)),
230 } 192 }
231 .intern(&Interner) 193 .intern(&Interner)
232 } 194 }
233}
234 195
235#[derive(Copy, Clone, Debug)] 196 pub(super) fn canonicalize<T: Fold<Interner> + HasInterner<Interner = Interner>>(
236pub(crate) struct TypeVariableData { 197 &mut self,
237 diverging: bool, 198 t: T,
238} 199 ) -> Canonicalized<T::Result>
200 where
201 T::Result: HasInterner<Interner = Interner>,
202 {
203 let result = self.var_unification_table.canonicalize(&Interner, t);
204 let free_vars = result
205 .free_vars
206 .into_iter()
207 .map(|free_var| free_var.to_generic_arg(&Interner))
208 .collect();
209 Canonicalized { value: result.quantified, free_vars }
210 }
211
212 /// Recurses through the given type, normalizing associated types mentioned
213 /// in it by replacing them by type variables and registering obligations to
214 /// resolve later. This should be done once for every type we get from some
215 /// type annotation (e.g. from a let type annotation, field type or function
216 /// call). `make_ty` handles this already, but e.g. for field types we need
217 /// to do it as well.
218 pub(super) fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
219 fold_tys(
220 ty,
221 |ty, _| match ty.kind(&Interner) {
222 TyKind::Alias(AliasTy::Projection(proj_ty)) => {
223 self.normalize_projection_ty(proj_ty.clone())
224 }
225 _ => ty,
226 },
227 DebruijnIndex::INNERMOST,
228 )
229 }
239 230
240#[derive(Clone, Debug)] 231 pub(super) fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
241pub(crate) struct InferenceTable { 232 let var = self.new_type_var();
242 pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>, 233 let alias_eq = AliasEq { alias: AliasTy::Projection(proj_ty), ty: var.clone() };
243 pub(super) type_variable_table: TypeVariableTable, 234 let obligation = alias_eq.cast(&Interner);
244 pub(super) revision: u32, 235 self.register_obligation(obligation);
245} 236 var
237 }
246 238
247impl InferenceTable { 239 fn extend_type_variable_table(&mut self, to_index: usize) {
248 pub(crate) fn new() -> Self { 240 self.type_variable_table.extend(
249 InferenceTable { 241 (0..1 + to_index - self.type_variable_table.len())
250 var_unification_table: InPlaceUnificationTable::new(), 242 .map(|_| TypeVariableData { diverging: false }),
251 type_variable_table: TypeVariableTable { inner: Vec::new() }, 243 );
252 revision: 0,
253 }
254 } 244 }
255 245
256 fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty { 246 fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty {
257 self.type_variable_table.push(TypeVariableData { diverging }); 247 let var = self.var_unification_table.new_variable(UniverseIndex::ROOT);
258 let key = self.var_unification_table.new_key(TypeVarValue::Unknown); 248 // Chalk might have created some type variables for its own purposes that we don't know about...
259 assert_eq!(key.0 as usize, self.type_variable_table.inner.len() - 1); 249 self.extend_type_variable_table(var.index() as usize);
260 TyKind::InferenceVar(to_inference_var(key), kind).intern(&Interner) 250 assert_eq!(var.index() as usize, self.type_variable_table.len() - 1);
251 self.type_variable_table[var.index() as usize].diverging = diverging;
252 var.to_ty_with_kind(&Interner, kind)
261 } 253 }
262 254
263 pub(crate) fn new_type_var(&mut self) -> Ty { 255 pub(crate) fn new_type_var(&mut self) -> Ty {
@@ -276,350 +268,261 @@ impl InferenceTable {
276 self.new_var(TyVariableKind::General, true) 268 self.new_var(TyVariableKind::General, true)
277 } 269 }
278 270
279 pub(crate) fn resolve_ty_completely(&mut self, ty: Ty) -> Ty { 271 pub(crate) fn resolve_with_fallback<T>(
280 self.resolve_ty_completely_inner(&mut Vec::new(), ty) 272 &mut self,
273 t: T,
274 fallback: impl Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg,
275 ) -> T::Result
276 where
277 T: HasInterner<Interner = Interner> + Fold<Interner>,
278 {
279 self.resolve_with_fallback_inner(&mut Vec::new(), t, &fallback)
281 } 280 }
282 281
283 pub(crate) fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty { 282 fn resolve_with_fallback_inner<T>(
284 self.resolve_ty_as_possible_inner(&mut Vec::new(), ty) 283 &mut self,
284 var_stack: &mut Vec<InferenceVar>,
285 t: T,
286 fallback: &impl Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg,
287 ) -> T::Result
288 where
289 T: HasInterner<Interner = Interner> + Fold<Interner>,
290 {
291 t.fold_with(
292 &mut resolve::Resolver { table: self, var_stack, fallback },
293 DebruijnIndex::INNERMOST,
294 )
295 .expect("fold failed unexpectedly")
285 } 296 }
286 297
287 pub(crate) fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { 298 pub(crate) fn resolve_ty_completely(&mut self, ty: Ty) -> Ty {
288 self.unify_inner(ty1, ty2, 0) 299 self.resolve_with_fallback(ty, |_, _, d, _| d)
289 } 300 }
290 301
291 pub(crate) fn unify_substs( 302 /// Unify two types and register new trait goals that arise from that.
292 &mut self, 303 pub(crate) fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
293 substs1: &Substitution, 304 let result = if let Ok(r) = self.try_unify(ty1, ty2) {
294 substs2: &Substitution, 305 r
295 depth: usize, 306 } else {
296 ) -> bool { 307 return false;
297 substs1.iter(&Interner).zip(substs2.iter(&Interner)).all(|(t1, t2)| { 308 };
298 self.unify_inner(t1.assert_ty_ref(&Interner), t2.assert_ty_ref(&Interner), depth) 309 self.register_infer_ok(result);
299 }) 310 true
300 } 311 }
301 312
302 fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { 313 /// Unify two types and return new trait goals arising from it, so the
303 if depth > 1000 { 314 /// caller needs to deal with them.
304 // prevent stackoverflows 315 pub(crate) fn try_unify<T: Zip<Interner>>(&mut self, t1: &T, t2: &T) -> InferResult {
305 panic!("infinite recursion in unification"); 316 match self.var_unification_table.relate(
306 } 317 &Interner,
307 if ty1 == ty2 { 318 &self.db,
308 return true; 319 &self.trait_env.env,
309 } 320 chalk_ir::Variance::Invariant,
310 // try to resolve type vars first 321 t1,
311 let ty1 = self.resolve_ty_shallow(ty1); 322 t2,
312 let ty2 = self.resolve_ty_shallow(ty2); 323 ) {
313 if ty1.equals_ctor(&ty2) { 324 Ok(result) => Ok(InferOk { goals: result.goals }),
314 match (ty1.kind(&Interner), ty2.kind(&Interner)) { 325 Err(chalk_ir::NoSolution) => Err(TypeError),
315 (TyKind::Adt(_, substs1), TyKind::Adt(_, substs2))
316 | (TyKind::FnDef(_, substs1), TyKind::FnDef(_, substs2))
317 | (
318 TyKind::Function(FnPointer { substitution: FnSubst(substs1), .. }),
319 TyKind::Function(FnPointer { substitution: FnSubst(substs2), .. }),
320 )
321 | (TyKind::Tuple(_, substs1), TyKind::Tuple(_, substs2))
322 | (TyKind::OpaqueType(_, substs1), TyKind::OpaqueType(_, substs2))
323 | (TyKind::AssociatedType(_, substs1), TyKind::AssociatedType(_, substs2))
324 | (TyKind::Closure(.., substs1), TyKind::Closure(.., substs2)) => {
325 self.unify_substs(substs1, substs2, depth + 1)
326 }
327 (TyKind::Array(ty1, c1), TyKind::Array(ty2, c2)) if c1 == c2 => {
328 self.unify_inner(ty1, ty2, depth + 1)
329 }
330 (TyKind::Ref(_, _, ty1), TyKind::Ref(_, _, ty2))
331 | (TyKind::Raw(_, ty1), TyKind::Raw(_, ty2))
332 | (TyKind::Slice(ty1), TyKind::Slice(ty2)) => self.unify_inner(ty1, ty2, depth + 1),
333 _ => true, /* we checked equals_ctor already */
334 }
335 } else if let (TyKind::Closure(.., substs1), TyKind::Closure(.., substs2)) =
336 (ty1.kind(&Interner), ty2.kind(&Interner))
337 {
338 self.unify_substs(substs1, substs2, depth + 1)
339 } else {
340 self.unify_inner_trivial(&ty1, &ty2, depth)
341 } 326 }
342 } 327 }
343 328
344 pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { 329 /// If `ty` is a type variable with known type, returns that type;
345 match (ty1.kind(&Interner), ty2.kind(&Interner)) { 330 /// otherwise, return ty.
346 (TyKind::Error, _) | (_, TyKind::Error) => true, 331 pub(crate) fn resolve_ty_shallow(&mut self, ty: &Ty) -> Ty {
332 self.var_unification_table.normalize_ty_shallow(&Interner, ty).unwrap_or_else(|| ty.clone())
333 }
347 334
348 (TyKind::Placeholder(p1), TyKind::Placeholder(p2)) if *p1 == *p2 => true, 335 pub(crate) fn register_obligation(&mut self, goal: Goal) {
336 let in_env = InEnvironment::new(&self.trait_env.env, goal);
337 self.register_obligation_in_env(in_env)
338 }
349 339
350 (TyKind::Dyn(dyn1), TyKind::Dyn(dyn2)) 340 fn register_obligation_in_env(&mut self, goal: InEnvironment<Goal>) {
351 if dyn1.bounds.skip_binders().interned().len() 341 let canonicalized = self.canonicalize(goal);
352 == dyn2.bounds.skip_binders().interned().len() => 342 if !self.try_resolve_obligation(&canonicalized) {
353 { 343 self.pending_obligations.push(canonicalized);
354 for (pred1, pred2) in dyn1 344 }
355 .bounds 345 }
356 .skip_binders()
357 .interned()
358 .iter()
359 .zip(dyn2.bounds.skip_binders().interned().iter())
360 {
361 if !self.unify_preds(pred1.skip_binders(), pred2.skip_binders(), depth + 1) {
362 return false;
363 }
364 }
365 true
366 }
367 346
368 ( 347 pub(crate) fn register_infer_ok(&mut self, infer_ok: InferOk) {
369 TyKind::InferenceVar(tv1, TyVariableKind::General), 348 infer_ok.goals.into_iter().for_each(|goal| self.register_obligation_in_env(goal));
370 TyKind::InferenceVar(tv2, TyVariableKind::General), 349 }
371 )
372 | (
373 TyKind::InferenceVar(tv1, TyVariableKind::Integer),
374 TyKind::InferenceVar(tv2, TyVariableKind::Integer),
375 )
376 | (
377 TyKind::InferenceVar(tv1, TyVariableKind::Float),
378 TyKind::InferenceVar(tv2, TyVariableKind::Float),
379 ) if self.type_variable_table.is_diverging(*tv1)
380 == self.type_variable_table.is_diverging(*tv2) =>
381 {
382 // both type vars are unknown since we tried to resolve them
383 if !self
384 .var_unification_table
385 .unioned(from_inference_var(*tv1), from_inference_var(*tv2))
386 {
387 self.var_unification_table
388 .union(from_inference_var(*tv1), from_inference_var(*tv2));
389 self.revision += 1;
390 }
391 true
392 }
393 350
394 // The order of MaybeNeverTypeVar matters here. 351 pub(crate) fn resolve_obligations_as_possible(&mut self) {
395 // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar. 352 let _span = profile::span("resolve_obligations_as_possible");
396 // Unifying MaybeNeverTypeVar and other concrete type will let the former become it. 353 let mut changed = true;
397 (TyKind::InferenceVar(tv, TyVariableKind::General), other) 354 let mut obligations = Vec::new();
398 | (other, TyKind::InferenceVar(tv, TyVariableKind::General)) 355 while changed {
399 | ( 356 changed = false;
400 TyKind::InferenceVar(tv, TyVariableKind::Integer), 357 mem::swap(&mut self.pending_obligations, &mut obligations);
401 other @ TyKind::Scalar(Scalar::Int(_)), 358 for canonicalized in obligations.drain(..) {
402 ) 359 if !self.check_changed(&canonicalized) {
403 | ( 360 self.pending_obligations.push(canonicalized);
404 other @ TyKind::Scalar(Scalar::Int(_)), 361 continue;
405 TyKind::InferenceVar(tv, TyVariableKind::Integer), 362 }
406 ) 363 changed = true;
407 | ( 364 let uncanonical = chalk_ir::Substitute::apply(
408 TyKind::InferenceVar(tv, TyVariableKind::Integer), 365 &canonicalized.free_vars,
409 other @ TyKind::Scalar(Scalar::Uint(_)), 366 canonicalized.value.value,
410 ) 367 &Interner,
411 | (
412 other @ TyKind::Scalar(Scalar::Uint(_)),
413 TyKind::InferenceVar(tv, TyVariableKind::Integer),
414 )
415 | (
416 TyKind::InferenceVar(tv, TyVariableKind::Float),
417 other @ TyKind::Scalar(Scalar::Float(_)),
418 )
419 | (
420 other @ TyKind::Scalar(Scalar::Float(_)),
421 TyKind::InferenceVar(tv, TyVariableKind::Float),
422 ) => {
423 // the type var is unknown since we tried to resolve it
424 self.var_unification_table.union_value(
425 from_inference_var(*tv),
426 TypeVarValue::Known(other.clone().intern(&Interner)),
427 ); 368 );
428 self.revision += 1; 369 self.register_obligation_in_env(uncanonical);
429 true
430 } 370 }
431
432 _ => false,
433 } 371 }
434 } 372 }
435 373
436 fn unify_preds(&mut self, pred1: &WhereClause, pred2: &WhereClause, depth: usize) -> bool { 374 /// This checks whether any of the free variables in the `canonicalized`
437 match (pred1, pred2) { 375 /// have changed (either been unified with another variable, or with a
438 (WhereClause::Implemented(tr1), WhereClause::Implemented(tr2)) 376 /// value). If this is not the case, we don't need to try to solve the goal
439 if tr1.trait_id == tr2.trait_id => 377 /// again -- it'll give the same result as last time.
440 { 378 fn check_changed(&mut self, canonicalized: &Canonicalized<InEnvironment<Goal>>) -> bool {
441 self.unify_substs(&tr1.substitution, &tr2.substitution, depth + 1) 379 canonicalized.free_vars.iter().any(|var| {
380 let iv = match var.data(&Interner) {
381 chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(&Interner),
382 chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(&Interner),
383 chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner),
442 } 384 }
443 ( 385 .expect("free var is not inference var");
444 WhereClause::AliasEq(AliasEq { alias: alias1, ty: ty1 }), 386 if self.var_unification_table.probe_var(iv).is_some() {
445 WhereClause::AliasEq(AliasEq { alias: alias2, ty: ty2 }), 387 return true;
446 ) => {
447 let (substitution1, substitution2) = match (alias1, alias2) {
448 (AliasTy::Projection(projection_ty1), AliasTy::Projection(projection_ty2))
449 if projection_ty1.associated_ty_id == projection_ty2.associated_ty_id =>
450 {
451 (&projection_ty1.substitution, &projection_ty2.substitution)
452 }
453 (AliasTy::Opaque(opaque1), AliasTy::Opaque(opaque2))
454 if opaque1.opaque_ty_id == opaque2.opaque_ty_id =>
455 {
456 (&opaque1.substitution, &opaque2.substitution)
457 }
458 _ => return false,
459 };
460 self.unify_substs(&substitution1, &substitution2, depth + 1)
461 && self.unify_inner(&ty1, &ty2, depth + 1)
462 } 388 }
463 _ => false, 389 let root = self.var_unification_table.inference_var_root(iv);
464 } 390 iv != root
391 })
465 } 392 }
466 393
467 /// If `ty` is a type variable with known type, returns that type; 394 fn try_resolve_obligation(
468 /// otherwise, return ty. 395 &mut self,
469 pub(crate) fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> { 396 canonicalized: &Canonicalized<InEnvironment<Goal>>,
470 let mut ty = Cow::Borrowed(ty); 397 ) -> bool {
471 // The type variable could resolve to a int/float variable. Hence try 398 let solution = self.db.trait_solve(self.trait_env.krate, canonicalized.value.clone());
472 // resolving up to three times; each type of variable shouldn't occur 399
473 // more than once 400 match solution {
474 for i in 0..3 { 401 Some(Solution::Unique(canonical_subst)) => {
475 if i > 0 { 402 canonicalized.apply_solution(
476 cov_mark::hit!(type_var_resolves_to_int_var); 403 self,
404 Canonical {
405 binders: canonical_subst.binders,
406 // FIXME: handle constraints
407 value: canonical_subst.value.subst,
408 },
409 );
410 true
477 } 411 }
478 match ty.kind(&Interner) { 412 Some(Solution::Ambig(Guidance::Definite(substs))) => {
479 TyKind::InferenceVar(tv, _) => { 413 canonicalized.apply_solution(self, substs);
480 let inner = from_inference_var(*tv); 414 false
481 match self.var_unification_table.inlined_probe_value(inner).known() { 415 }
482 Some(known_ty) => { 416 Some(_) => {
483 // The known_ty can't be a type var itself 417 // FIXME use this when trying to resolve everything at the end
484 ty = Cow::Owned(known_ty.clone()); 418 false
485 } 419 }
486 _ => return ty, 420 None => {
487 } 421 // FIXME obligation cannot be fulfilled => diagnostic
488 } 422 true
489 _ => return ty,
490 } 423 }
491 } 424 }
492 log::error!("Inference variable still not resolved: {:?}", ty);
493 ty
494 }
495
496 /// Resolves the type as far as currently possible, replacing type variables
497 /// by their known types. All types returned by the infer_* functions should
498 /// be resolved as far as possible, i.e. contain no type variables with
499 /// known type.
500 fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
501 fold_tys(
502 ty,
503 |ty, _| match ty.kind(&Interner) {
504 &TyKind::InferenceVar(tv, kind) => {
505 let inner = from_inference_var(tv);
506 if tv_stack.contains(&inner) {
507 cov_mark::hit!(type_var_cycles_resolve_as_possible);
508 // recursive type
509 return self.type_variable_table.fallback_value(tv, kind);
510 }
511 if let Some(known_ty) =
512 self.var_unification_table.inlined_probe_value(inner).known()
513 {
514 // known_ty may contain other variables that are known by now
515 tv_stack.push(inner);
516 let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone());
517 tv_stack.pop();
518 result
519 } else {
520 ty
521 }
522 }
523 _ => ty,
524 },
525 DebruijnIndex::INNERMOST,
526 )
527 }
528
529 /// Resolves the type completely; type variables without known type are
530 /// replaced by TyKind::Unknown.
531 fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
532 fold_tys(
533 ty,
534 |ty, _| match ty.kind(&Interner) {
535 &TyKind::InferenceVar(tv, kind) => {
536 let inner = from_inference_var(tv);
537 if tv_stack.contains(&inner) {
538 cov_mark::hit!(type_var_cycles_resolve_completely);
539 // recursive type
540 return self.type_variable_table.fallback_value(tv, kind);
541 }
542 if let Some(known_ty) =
543 self.var_unification_table.inlined_probe_value(inner).known()
544 {
545 // known_ty may contain other variables that are known by now
546 tv_stack.push(inner);
547 let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone());
548 tv_stack.pop();
549 result
550 } else {
551 self.type_variable_table.fallback_value(tv, kind)
552 }
553 }
554 _ => ty,
555 },
556 DebruijnIndex::INNERMOST,
557 )
558 } 425 }
559} 426}
560 427
561/// The ID of a type variable. 428impl<'a> fmt::Debug for InferenceTable<'a> {
562#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] 429 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
563pub(super) struct TypeVarId(pub(super) u32); 430 f.debug_struct("InferenceTable").field("num_vars", &self.type_variable_table.len()).finish()
564
565impl UnifyKey for TypeVarId {
566 type Value = TypeVarValue;
567
568 fn index(&self) -> u32 {
569 self.0
570 }
571
572 fn from_index(i: u32) -> Self {
573 TypeVarId(i)
574 } 431 }
575
576 fn tag() -> &'static str {
577 "TypeVarId"
578 }
579}
580
581fn from_inference_var(var: InferenceVar) -> TypeVarId {
582 TypeVarId(var.index())
583}
584
585fn to_inference_var(TypeVarId(index): TypeVarId) -> InferenceVar {
586 index.into()
587}
588
589/// The value of a type variable: either we already know the type, or we don't
590/// know it yet.
591#[derive(Clone, PartialEq, Eq, Debug)]
592pub(super) enum TypeVarValue {
593 Known(Ty),
594 Unknown,
595} 432}
596 433
597impl TypeVarValue { 434mod resolve {
598 fn known(&self) -> Option<&Ty> { 435 use super::InferenceTable;
599 match self { 436 use crate::{
600 TypeVarValue::Known(ty) => Some(ty), 437 ConcreteConst, Const, ConstData, ConstValue, DebruijnIndex, GenericArg, InferenceVar,
601 TypeVarValue::Unknown => None, 438 Interner, Ty, TyVariableKind, VariableKind,
439 };
440 use chalk_ir::{
441 cast::Cast,
442 fold::{Fold, Folder},
443 Fallible,
444 };
445 use hir_def::type_ref::ConstScalar;
446
447 pub(super) struct Resolver<'a, 'b, F> {
448 pub(super) table: &'a mut InferenceTable<'b>,
449 pub(super) var_stack: &'a mut Vec<InferenceVar>,
450 pub(super) fallback: F,
451 }
452 impl<'a, 'b, 'i, F> Folder<'i, Interner> for Resolver<'a, 'b, F>
453 where
454 F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg + 'i,
455 {
456 fn as_dyn(&mut self) -> &mut dyn Folder<'i, Interner> {
457 self
602 } 458 }
603 }
604}
605
606impl UnifyValue for TypeVarValue {
607 type Error = NoError;
608 459
609 fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> { 460 fn interner(&self) -> &'i Interner {
610 match (value1, value2) { 461 &Interner
611 // We should never equate two type variables, both of which have 462 }
612 // known types. Instead, we recursively equate those types.
613 (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!(
614 "equating two type variables, both of which have known types: {:?} and {:?}",
615 t1, t2
616 ),
617 463
618 // If one side is known, prefer that one. 464 fn fold_inference_ty(
619 (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()), 465 &mut self,
620 (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()), 466 var: InferenceVar,
467 kind: TyVariableKind,
468 outer_binder: DebruijnIndex,
469 ) -> Fallible<Ty> {
470 let var = self.table.var_unification_table.inference_var_root(var);
471 if self.var_stack.contains(&var) {
472 // recursive type
473 let default = self.table.fallback_value(var, kind).cast(&Interner);
474 return Ok((self.fallback)(var, VariableKind::Ty(kind), default, outer_binder)
475 .assert_ty_ref(&Interner)
476 .clone());
477 }
478 let result = if let Some(known_ty) = self.table.var_unification_table.probe_var(var) {
479 // known_ty may contain other variables that are known by now
480 self.var_stack.push(var);
481 let result =
482 known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly");
483 self.var_stack.pop();
484 result.assert_ty_ref(&Interner).clone()
485 } else {
486 let default = self.table.fallback_value(var, kind).cast(&Interner);
487 (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder)
488 .assert_ty_ref(&Interner)
489 .clone()
490 };
491 Ok(result)
492 }
621 493
622 (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown), 494 fn fold_inference_const(
495 &mut self,
496 ty: Ty,
497 var: InferenceVar,
498 outer_binder: DebruijnIndex,
499 ) -> Fallible<Const> {
500 let var = self.table.var_unification_table.inference_var_root(var);
501 let default = ConstData {
502 ty: ty.clone(),
503 value: ConstValue::Concrete(ConcreteConst { interned: ConstScalar::Unknown }),
504 }
505 .intern(&Interner)
506 .cast(&Interner);
507 if self.var_stack.contains(&var) {
508 // recursive
509 return Ok((self.fallback)(var, VariableKind::Const(ty), default, outer_binder)
510 .assert_const_ref(&Interner)
511 .clone());
512 }
513 let result = if let Some(known_ty) = self.table.var_unification_table.probe_var(var) {
514 // known_ty may contain other variables that are known by now
515 self.var_stack.push(var);
516 let result =
517 known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly");
518 self.var_stack.pop();
519 result.assert_const_ref(&Interner).clone()
520 } else {
521 (self.fallback)(var, VariableKind::Const(ty), default, outer_binder)
522 .assert_const_ref(&Interner)
523 .clone()
524 };
525 Ok(result)
623 } 526 }
624 } 527 }
625} 528}
diff --git a/crates/hir_ty/src/interner.rs b/crates/hir_ty/src/interner.rs
index 7b4119747..29ffdd9b7 100644
--- a/crates/hir_ty/src/interner.rs
+++ b/crates/hir_ty/src/interner.rs
@@ -15,9 +15,15 @@ use std::{fmt, sync::Arc};
15#[derive(Debug, Copy, Clone, Hash, PartialOrd, Ord, PartialEq, Eq)] 15#[derive(Debug, Copy, Clone, Hash, PartialOrd, Ord, PartialEq, Eq)]
16pub struct Interner; 16pub struct Interner;
17 17
18#[derive(PartialEq, Eq, Hash, Debug)] 18#[derive(PartialEq, Eq, Hash)]
19pub struct InternedWrapper<T>(T); 19pub struct InternedWrapper<T>(T);
20 20
21impl<T: fmt::Debug> fmt::Debug for InternedWrapper<T> {
22 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
23 fmt::Debug::fmt(&self.0, f)
24 }
25}
26
21impl<T> std::ops::Deref for InternedWrapper<T> { 27impl<T> std::ops::Deref for InternedWrapper<T> {
22 type Target = T; 28 type Target = T;
23 29
@@ -101,66 +107,65 @@ impl chalk_ir::interner::Interner for Interner {
101 opaque_ty: &chalk_ir::OpaqueTy<Interner>, 107 opaque_ty: &chalk_ir::OpaqueTy<Interner>,
102 fmt: &mut fmt::Formatter<'_>, 108 fmt: &mut fmt::Formatter<'_>,
103 ) -> Option<fmt::Result> { 109 ) -> Option<fmt::Result> {
104 tls::with_current_program(|prog| Some(prog?.debug_opaque_ty(opaque_ty, fmt))) 110 Some(write!(fmt, "{:?}", opaque_ty.opaque_ty_id))
105 } 111 }
106 112
107 fn debug_opaque_ty_id( 113 fn debug_opaque_ty_id(
108 opaque_ty_id: chalk_ir::OpaqueTyId<Self>, 114 opaque_ty_id: chalk_ir::OpaqueTyId<Self>,
109 fmt: &mut fmt::Formatter<'_>, 115 fmt: &mut fmt::Formatter<'_>,
110 ) -> Option<fmt::Result> { 116 ) -> Option<fmt::Result> {
111 tls::with_current_program(|prog| Some(prog?.debug_opaque_ty_id(opaque_ty_id, fmt))) 117 Some(fmt.debug_struct("OpaqueTyId").field("index", &opaque_ty_id.0).finish())
112 } 118 }
113 119
114 fn debug_ty(ty: &chalk_ir::Ty<Interner>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> { 120 fn debug_ty(ty: &chalk_ir::Ty<Interner>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
115 tls::with_current_program(|prog| Some(prog?.debug_ty(ty, fmt))) 121 Some(write!(fmt, "{:?}", ty.data(&Interner)))
116 } 122 }
117 123
118 fn debug_lifetime( 124 fn debug_lifetime(
119 lifetime: &chalk_ir::Lifetime<Interner>, 125 lifetime: &chalk_ir::Lifetime<Interner>,
120 fmt: &mut fmt::Formatter<'_>, 126 fmt: &mut fmt::Formatter<'_>,
121 ) -> Option<fmt::Result> { 127 ) -> Option<fmt::Result> {
122 tls::with_current_program(|prog| Some(prog?.debug_lifetime(lifetime, fmt))) 128 Some(write!(fmt, "{:?}", lifetime.data(&Interner)))
123 } 129 }
124 130
125 fn debug_generic_arg( 131 fn debug_generic_arg(
126 parameter: &GenericArg, 132 parameter: &GenericArg,
127 fmt: &mut fmt::Formatter<'_>, 133 fmt: &mut fmt::Formatter<'_>,
128 ) -> Option<fmt::Result> { 134 ) -> Option<fmt::Result> {
129 tls::with_current_program(|prog| Some(prog?.debug_generic_arg(parameter, fmt))) 135 Some(write!(fmt, "{:?}", parameter.data(&Interner).inner_debug()))
130 } 136 }
131 137
132 fn debug_goal(goal: &Goal<Interner>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> { 138 fn debug_goal(goal: &Goal<Interner>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
133 tls::with_current_program(|prog| Some(prog?.debug_goal(goal, fmt))) 139 let goal_data = goal.data(&Interner);
140 Some(write!(fmt, "{:?}", goal_data))
134 } 141 }
135 142
136 fn debug_goals( 143 fn debug_goals(
137 goals: &chalk_ir::Goals<Interner>, 144 goals: &chalk_ir::Goals<Interner>,
138 fmt: &mut fmt::Formatter<'_>, 145 fmt: &mut fmt::Formatter<'_>,
139 ) -> Option<fmt::Result> { 146 ) -> Option<fmt::Result> {
140 tls::with_current_program(|prog| Some(prog?.debug_goals(goals, fmt))) 147 Some(write!(fmt, "{:?}", goals.debug(&Interner)))
141 } 148 }
142 149
143 fn debug_program_clause_implication( 150 fn debug_program_clause_implication(
144 pci: &chalk_ir::ProgramClauseImplication<Interner>, 151 pci: &chalk_ir::ProgramClauseImplication<Interner>,
145 fmt: &mut fmt::Formatter<'_>, 152 fmt: &mut fmt::Formatter<'_>,
146 ) -> Option<fmt::Result> { 153 ) -> Option<fmt::Result> {
147 tls::with_current_program(|prog| Some(prog?.debug_program_clause_implication(pci, fmt))) 154 Some(write!(fmt, "{:?}", pci.debug(&Interner)))
148 } 155 }
149 156
150 fn debug_substitution( 157 fn debug_substitution(
151 substitution: &chalk_ir::Substitution<Interner>, 158 substitution: &chalk_ir::Substitution<Interner>,
152 fmt: &mut fmt::Formatter<'_>, 159 fmt: &mut fmt::Formatter<'_>,
153 ) -> Option<fmt::Result> { 160 ) -> Option<fmt::Result> {
154 tls::with_current_program(|prog| Some(prog?.debug_substitution(substitution, fmt))) 161 Some(write!(fmt, "{:?}", substitution.debug(&Interner)))
155 } 162 }
156 163
157 fn debug_separator_trait_ref( 164 fn debug_separator_trait_ref(
158 separator_trait_ref: &chalk_ir::SeparatorTraitRef<Interner>, 165 separator_trait_ref: &chalk_ir::SeparatorTraitRef<Interner>,
159 fmt: &mut fmt::Formatter<'_>, 166 fmt: &mut fmt::Formatter<'_>,
160 ) -> Option<fmt::Result> { 167 ) -> Option<fmt::Result> {
161 tls::with_current_program(|prog| { 168 Some(write!(fmt, "{:?}", separator_trait_ref.debug(&Interner)))
162 Some(prog?.debug_separator_trait_ref(separator_trait_ref, fmt))
163 })
164 } 169 }
165 170
166 fn debug_fn_def_id( 171 fn debug_fn_def_id(
@@ -173,47 +178,43 @@ impl chalk_ir::interner::Interner for Interner {
173 constant: &chalk_ir::Const<Self>, 178 constant: &chalk_ir::Const<Self>,
174 fmt: &mut fmt::Formatter<'_>, 179 fmt: &mut fmt::Formatter<'_>,
175 ) -> Option<fmt::Result> { 180 ) -> Option<fmt::Result> {
176 tls::with_current_program(|prog| Some(prog?.debug_const(constant, fmt))) 181 Some(write!(fmt, "{:?}", constant.data(&Interner)))
177 } 182 }
178 fn debug_variable_kinds( 183 fn debug_variable_kinds(
179 variable_kinds: &chalk_ir::VariableKinds<Self>, 184 variable_kinds: &chalk_ir::VariableKinds<Self>,
180 fmt: &mut fmt::Formatter<'_>, 185 fmt: &mut fmt::Formatter<'_>,
181 ) -> Option<fmt::Result> { 186 ) -> Option<fmt::Result> {
182 tls::with_current_program(|prog| Some(prog?.debug_variable_kinds(variable_kinds, fmt))) 187 Some(write!(fmt, "{:?}", variable_kinds.as_slice(&Interner)))
183 } 188 }
184 fn debug_variable_kinds_with_angles( 189 fn debug_variable_kinds_with_angles(
185 variable_kinds: &chalk_ir::VariableKinds<Self>, 190 variable_kinds: &chalk_ir::VariableKinds<Self>,
186 fmt: &mut fmt::Formatter<'_>, 191 fmt: &mut fmt::Formatter<'_>,
187 ) -> Option<fmt::Result> { 192 ) -> Option<fmt::Result> {
188 tls::with_current_program(|prog| { 193 Some(write!(fmt, "{:?}", variable_kinds.inner_debug(&Interner)))
189 Some(prog?.debug_variable_kinds_with_angles(variable_kinds, fmt))
190 })
191 } 194 }
192 fn debug_canonical_var_kinds( 195 fn debug_canonical_var_kinds(
193 canonical_var_kinds: &chalk_ir::CanonicalVarKinds<Self>, 196 canonical_var_kinds: &chalk_ir::CanonicalVarKinds<Self>,
194 fmt: &mut fmt::Formatter<'_>, 197 fmt: &mut fmt::Formatter<'_>,
195 ) -> Option<fmt::Result> { 198 ) -> Option<fmt::Result> {
196 tls::with_current_program(|prog| { 199 Some(write!(fmt, "{:?}", canonical_var_kinds.as_slice(&Interner)))
197 Some(prog?.debug_canonical_var_kinds(canonical_var_kinds, fmt))
198 })
199 } 200 }
200 fn debug_program_clause( 201 fn debug_program_clause(
201 clause: &chalk_ir::ProgramClause<Self>, 202 clause: &chalk_ir::ProgramClause<Self>,
202 fmt: &mut fmt::Formatter<'_>, 203 fmt: &mut fmt::Formatter<'_>,
203 ) -> Option<fmt::Result> { 204 ) -> Option<fmt::Result> {
204 tls::with_current_program(|prog| Some(prog?.debug_program_clause(clause, fmt))) 205 Some(write!(fmt, "{:?}", clause.data(&Interner)))
205 } 206 }
206 fn debug_program_clauses( 207 fn debug_program_clauses(
207 clauses: &chalk_ir::ProgramClauses<Self>, 208 clauses: &chalk_ir::ProgramClauses<Self>,
208 fmt: &mut fmt::Formatter<'_>, 209 fmt: &mut fmt::Formatter<'_>,
209 ) -> Option<fmt::Result> { 210 ) -> Option<fmt::Result> {
210 tls::with_current_program(|prog| Some(prog?.debug_program_clauses(clauses, fmt))) 211 Some(write!(fmt, "{:?}", clauses.as_slice(&Interner)))
211 } 212 }
212 fn debug_quantified_where_clauses( 213 fn debug_quantified_where_clauses(
213 clauses: &chalk_ir::QuantifiedWhereClauses<Self>, 214 clauses: &chalk_ir::QuantifiedWhereClauses<Self>,
214 fmt: &mut fmt::Formatter<'_>, 215 fmt: &mut fmt::Formatter<'_>,
215 ) -> Option<fmt::Result> { 216 ) -> Option<fmt::Result> {
216 tls::with_current_program(|prog| Some(prog?.debug_quantified_where_clauses(clauses, fmt))) 217 Some(write!(fmt, "{:?}", clauses.as_slice(&Interner)))
217 } 218 }
218 219
219 fn intern_ty(&self, kind: chalk_ir::TyKind<Self>) -> Self::InternedType { 220 fn intern_ty(&self, kind: chalk_ir::TyKind<Self>) -> Self::InternedType {
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index 15b61bedc..72093d75a 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -43,8 +43,9 @@ use hir_def::{
43 type_ref::{ConstScalar, Rawness}, 43 type_ref::{ConstScalar, Rawness},
44 TypeParamId, 44 TypeParamId,
45}; 45};
46use stdx::always;
46 47
47use crate::{db::HirDatabase, display::HirDisplay, utils::generics}; 48use crate::{db::HirDatabase, utils::generics};
48 49
49pub use autoderef::autoderef; 50pub use autoderef::autoderef;
50pub use builder::TyBuilder; 51pub use builder::TyBuilder;
@@ -113,6 +114,7 @@ pub type FnSig = chalk_ir::FnSig<Interner>;
113 114
114pub type InEnvironment<T> = chalk_ir::InEnvironment<T>; 115pub type InEnvironment<T> = chalk_ir::InEnvironment<T>;
115pub type DomainGoal = chalk_ir::DomainGoal<Interner>; 116pub type DomainGoal = chalk_ir::DomainGoal<Interner>;
117pub type Goal = chalk_ir::Goal<Interner>;
116pub type AliasEq = chalk_ir::AliasEq<Interner>; 118pub type AliasEq = chalk_ir::AliasEq<Interner>;
117pub type Solution = chalk_solve::Solution<Interner>; 119pub type Solution = chalk_solve::Solution<Interner>;
118pub type ConstrainedSubst = chalk_ir::ConstrainedSubst<Interner>; 120pub type ConstrainedSubst = chalk_ir::ConstrainedSubst<Interner>;
@@ -167,6 +169,7 @@ pub fn make_canonical<T: HasInterner<Interner = Interner>>(
167 Canonical { value, binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds) } 169 Canonical { value, binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds) }
168} 170}
169 171
172// FIXME: get rid of this, just replace it by FnPointer
170/// A function signature as seen by type inference: Several parameter types and 173/// A function signature as seen by type inference: Several parameter types and
171/// one return type. 174/// one return type.
172#[derive(Clone, PartialEq, Eq, Debug)] 175#[derive(Clone, PartialEq, Eq, Debug)]
@@ -203,6 +206,17 @@ impl CallableSig {
203 } 206 }
204 } 207 }
205 208
209 pub fn to_fn_ptr(&self) -> FnPointer {
210 FnPointer {
211 num_binders: 0,
212 sig: FnSig { abi: (), safety: Safety::Safe, variadic: self.is_varargs },
213 substitution: FnSubst(Substitution::from_iter(
214 &Interner,
215 self.params_and_return.iter().cloned(),
216 )),
217 }
218 }
219
206 pub fn params(&self) -> &[Ty] { 220 pub fn params(&self) -> &[Ty] {
207 &self.params_and_return[0..self.params_and_return.len() - 1] 221 &self.params_and_return[0..self.params_and_return.len() - 1]
208 } 222 }
@@ -314,3 +328,58 @@ pub(crate) fn fold_tys<T: HasInterner<Interner = Interner> + Fold<Interner>>(
314 } 328 }
315 t.fold_with(&mut TyFolder(f), binders).expect("fold failed unexpectedly") 329 t.fold_with(&mut TyFolder(f), binders).expect("fold failed unexpectedly")
316} 330}
331
332pub fn replace_errors_with_variables<T>(t: T) -> Canonical<T::Result>
333where
334 T: HasInterner<Interner = Interner> + Fold<Interner>,
335 T::Result: HasInterner<Interner = Interner>,
336{
337 use chalk_ir::{
338 fold::{Folder, SuperFold},
339 Fallible,
340 };
341 struct ErrorReplacer {
342 vars: usize,
343 }
344 impl<'i> Folder<'i, Interner> for ErrorReplacer {
345 fn as_dyn(&mut self) -> &mut dyn Folder<'i, Interner> {
346 self
347 }
348
349 fn interner(&self) -> &'i Interner {
350 &Interner
351 }
352
353 fn fold_ty(&mut self, ty: Ty, outer_binder: DebruijnIndex) -> Fallible<Ty> {
354 if let TyKind::Error = ty.kind(&Interner) {
355 let index = self.vars;
356 self.vars += 1;
357 Ok(TyKind::BoundVar(BoundVar::new(outer_binder, index)).intern(&Interner))
358 } else {
359 let ty = ty.super_fold_with(self.as_dyn(), outer_binder)?;
360 Ok(ty)
361 }
362 }
363
364 fn fold_inference_ty(
365 &mut self,
366 var: InferenceVar,
367 kind: TyVariableKind,
368 _outer_binder: DebruijnIndex,
369 ) -> Fallible<Ty> {
370 always!(false);
371 Ok(TyKind::InferenceVar(var, kind).intern(&Interner))
372 }
373 }
374 let mut error_replacer = ErrorReplacer { vars: 0 };
375 let value = t
376 .fold_with(&mut error_replacer, DebruijnIndex::INNERMOST)
377 .expect("fold failed unexpectedly");
378 let kinds = (0..error_replacer.vars).map(|_| {
379 chalk_ir::CanonicalVarKind::new(
380 chalk_ir::VariableKind::Ty(TyVariableKind::General),
381 chalk_ir::UniverseIndex::ROOT,
382 )
383 });
384 Canonical { value, binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds) }
385}
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index bd8bb6028..8a375b973 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -1035,9 +1035,11 @@ pub(crate) fn trait_environment_query(
1035 clauses.push(program_clause.into_from_env_clause(&Interner)); 1035 clauses.push(program_clause.into_from_env_clause(&Interner));
1036 } 1036 }
1037 1037
1038 let krate = def.module(db.upcast()).krate();
1039
1038 let env = chalk_ir::Environment::new(&Interner).add_clauses(&Interner, clauses); 1040 let env = chalk_ir::Environment::new(&Interner).add_clauses(&Interner, clauses);
1039 1041
1040 Arc::new(TraitEnvironment { traits_from_clauses: traits_in_scope, env }) 1042 Arc::new(TraitEnvironment { krate, traits_from_clauses: traits_in_scope, env })
1041} 1043}
1042 1044
1043/// Resolve the where clause(s) of an item with generics. 1045/// Resolve the where clause(s) of an item with generics.
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index 48bbcfd9f..08e385a42 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -577,6 +577,7 @@ fn iterate_method_candidates_by_receiver(
577 if iterate_inherent_methods( 577 if iterate_inherent_methods(
578 self_ty, 578 self_ty,
579 db, 579 db,
580 env.clone(),
580 name, 581 name,
581 Some(receiver_ty), 582 Some(receiver_ty),
582 krate, 583 krate,
@@ -613,8 +614,16 @@ fn iterate_method_candidates_for_self_ty(
613 name: Option<&Name>, 614 name: Option<&Name>,
614 mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool, 615 mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
615) -> bool { 616) -> bool {
616 if iterate_inherent_methods(self_ty, db, name, None, krate, visible_from_module, &mut callback) 617 if iterate_inherent_methods(
617 { 618 self_ty,
619 db,
620 env.clone(),
621 name,
622 None,
623 krate,
624 visible_from_module,
625 &mut callback,
626 ) {
618 return true; 627 return true;
619 } 628 }
620 iterate_trait_method_candidates(self_ty, db, env, krate, traits_in_scope, name, None, callback) 629 iterate_trait_method_candidates(self_ty, db, env, krate, traits_in_scope, name, None, callback)
@@ -653,12 +662,12 @@ fn iterate_trait_method_candidates(
653 for (_name, item) in data.items.iter() { 662 for (_name, item) in data.items.iter() {
654 // Don't pass a `visible_from_module` down to `is_valid_candidate`, 663 // Don't pass a `visible_from_module` down to `is_valid_candidate`,
655 // since only inherent methods should be included into visibility checking. 664 // since only inherent methods should be included into visibility checking.
656 if !is_valid_candidate(db, name, receiver_ty, *item, self_ty, None) { 665 if !is_valid_candidate(db, env.clone(), name, receiver_ty, *item, self_ty, None) {
657 continue; 666 continue;
658 } 667 }
659 if !known_implemented { 668 if !known_implemented {
660 let goal = generic_implements_goal(db, env.clone(), t, self_ty.clone()); 669 let goal = generic_implements_goal(db, env.clone(), t, self_ty.clone());
661 if db.trait_solve(krate, goal).is_none() { 670 if db.trait_solve(krate, goal.cast(&Interner)).is_none() {
662 continue 'traits; 671 continue 'traits;
663 } 672 }
664 } 673 }
@@ -675,6 +684,7 @@ fn iterate_trait_method_candidates(
675fn iterate_inherent_methods( 684fn iterate_inherent_methods(
676 self_ty: &Canonical<Ty>, 685 self_ty: &Canonical<Ty>,
677 db: &dyn HirDatabase, 686 db: &dyn HirDatabase,
687 env: Arc<TraitEnvironment>,
678 name: Option<&Name>, 688 name: Option<&Name>,
679 receiver_ty: Option<&Canonical<Ty>>, 689 receiver_ty: Option<&Canonical<Ty>>,
680 krate: CrateId, 690 krate: CrateId,
@@ -690,14 +700,24 @@ fn iterate_inherent_methods(
690 700
691 for &impl_def in impls.for_self_ty(&self_ty.value) { 701 for &impl_def in impls.for_self_ty(&self_ty.value) {
692 for &item in db.impl_data(impl_def).items.iter() { 702 for &item in db.impl_data(impl_def).items.iter() {
693 if !is_valid_candidate(db, name, receiver_ty, item, self_ty, visible_from_module) { 703 if !is_valid_candidate(
704 db,
705 env.clone(),
706 name,
707 receiver_ty,
708 item,
709 self_ty,
710 visible_from_module,
711 ) {
694 continue; 712 continue;
695 } 713 }
696 // we have to check whether the self type unifies with the type 714 // we have to check whether the self type unifies with the type
697 // that the impl is for. If we have a receiver type, this 715 // that the impl is for. If we have a receiver type, this
698 // already happens in `is_valid_candidate` above; if not, we 716 // already happens in `is_valid_candidate` above; if not, we
699 // check it here 717 // check it here
700 if receiver_ty.is_none() && inherent_impl_substs(db, impl_def, self_ty).is_none() { 718 if receiver_ty.is_none()
719 && inherent_impl_substs(db, env.clone(), impl_def, self_ty).is_none()
720 {
701 cov_mark::hit!(impl_self_type_match_without_receiver); 721 cov_mark::hit!(impl_self_type_match_without_receiver);
702 continue; 722 continue;
703 } 723 }
@@ -722,7 +742,7 @@ pub fn resolve_indexing_op(
722 let deref_chain = autoderef_method_receiver(db, krate, ty); 742 let deref_chain = autoderef_method_receiver(db, krate, ty);
723 for ty in deref_chain { 743 for ty in deref_chain {
724 let goal = generic_implements_goal(db, env.clone(), index_trait, ty.clone()); 744 let goal = generic_implements_goal(db, env.clone(), index_trait, ty.clone());
725 if db.trait_solve(krate, goal).is_some() { 745 if db.trait_solve(krate, goal.cast(&Interner)).is_some() {
726 return Some(ty); 746 return Some(ty);
727 } 747 }
728 } 748 }
@@ -731,6 +751,7 @@ pub fn resolve_indexing_op(
731 751
732fn is_valid_candidate( 752fn is_valid_candidate(
733 db: &dyn HirDatabase, 753 db: &dyn HirDatabase,
754 env: Arc<TraitEnvironment>,
734 name: Option<&Name>, 755 name: Option<&Name>,
735 receiver_ty: Option<&Canonical<Ty>>, 756 receiver_ty: Option<&Canonical<Ty>>,
736 item: AssocItemId, 757 item: AssocItemId,
@@ -749,7 +770,7 @@ fn is_valid_candidate(
749 if !data.has_self_param() { 770 if !data.has_self_param() {
750 return false; 771 return false;
751 } 772 }
752 let transformed_receiver_ty = match transform_receiver_ty(db, m, self_ty) { 773 let transformed_receiver_ty = match transform_receiver_ty(db, env, m, self_ty) {
753 Some(ty) => ty, 774 Some(ty) => ty,
754 None => return false, 775 None => return false,
755 }; 776 };
@@ -776,6 +797,7 @@ fn is_valid_candidate(
776 797
777pub(crate) fn inherent_impl_substs( 798pub(crate) fn inherent_impl_substs(
778 db: &dyn HirDatabase, 799 db: &dyn HirDatabase,
800 env: Arc<TraitEnvironment>,
779 impl_id: ImplId, 801 impl_id: ImplId,
780 self_ty: &Canonical<Ty>, 802 self_ty: &Canonical<Ty>,
781) -> Option<Substitution> { 803) -> Option<Substitution> {
@@ -798,7 +820,7 @@ pub(crate) fn inherent_impl_substs(
798 binders: CanonicalVarKinds::from_iter(&Interner, kinds), 820 binders: CanonicalVarKinds::from_iter(&Interner, kinds),
799 value: (self_ty_with_vars, self_ty.value.clone()), 821 value: (self_ty_with_vars, self_ty.value.clone()),
800 }; 822 };
801 let substs = super::infer::unify(&tys)?; 823 let substs = super::infer::unify(db, env, &tys)?;
802 // We only want the substs for the vars we added, not the ones from self_ty. 824 // We only want the substs for the vars we added, not the ones from self_ty.
803 // Also, if any of the vars we added are still in there, we replace them by 825 // Also, if any of the vars we added are still in there, we replace them by
804 // Unknown. I think this can only really happen if self_ty contained 826 // Unknown. I think this can only really happen if self_ty contained
@@ -823,6 +845,7 @@ fn fallback_bound_vars(s: Substitution, num_vars_to_keep: usize) -> Substitution
823 845
824fn transform_receiver_ty( 846fn transform_receiver_ty(
825 db: &dyn HirDatabase, 847 db: &dyn HirDatabase,
848 env: Arc<TraitEnvironment>,
826 function_id: FunctionId, 849 function_id: FunctionId,
827 self_ty: &Canonical<Ty>, 850 self_ty: &Canonical<Ty>,
828) -> Option<Ty> { 851) -> Option<Ty> {
@@ -832,7 +855,7 @@ fn transform_receiver_ty(
832 .fill_with_unknown() 855 .fill_with_unknown()
833 .build(), 856 .build(),
834 AssocContainerId::ImplId(impl_id) => { 857 AssocContainerId::ImplId(impl_id) => {
835 let impl_substs = inherent_impl_substs(db, impl_id, &self_ty)?; 858 let impl_substs = inherent_impl_substs(db, env, impl_id, &self_ty)?;
836 TyBuilder::subst_for_def(db, function_id) 859 TyBuilder::subst_for_def(db, function_id)
837 .use_parent_substs(&impl_substs) 860 .use_parent_substs(&impl_substs)
838 .fill_with_unknown() 861 .fill_with_unknown()
@@ -852,7 +875,7 @@ pub fn implements_trait(
852 trait_: TraitId, 875 trait_: TraitId,
853) -> bool { 876) -> bool {
854 let goal = generic_implements_goal(db, env, trait_, ty.clone()); 877 let goal = generic_implements_goal(db, env, trait_, ty.clone());
855 let solution = db.trait_solve(krate, goal); 878 let solution = db.trait_solve(krate, goal.cast(&Interner));
856 879
857 solution.is_some() 880 solution.is_some()
858} 881}
@@ -865,7 +888,7 @@ pub fn implements_trait_unique(
865 trait_: TraitId, 888 trait_: TraitId,
866) -> bool { 889) -> bool {
867 let goal = generic_implements_goal(db, env, trait_, ty.clone()); 890 let goal = generic_implements_goal(db, env, trait_, ty.clone());
868 let solution = db.trait_solve(krate, goal); 891 let solution = db.trait_solve(krate, goal.cast(&Interner));
869 892
870 matches!(solution, Some(crate::Solution::Unique(_))) 893 matches!(solution, Some(crate::Solution::Unique(_)))
871} 894}
diff --git a/crates/hir_ty/src/tests/coercion.rs b/crates/hir_ty/src/tests/coercion.rs
index 190471069..bb568ea37 100644
--- a/crates/hir_ty/src/tests/coercion.rs
+++ b/crates/hir_ty/src/tests/coercion.rs
@@ -1,6 +1,6 @@
1use expect_test::expect; 1use expect_test::expect;
2 2
3use super::{check_infer, check_infer_with_mismatches}; 3use super::{check_infer, check_infer_with_mismatches, check_types};
4 4
5#[test] 5#[test]
6fn infer_block_expr_type_mismatch() { 6fn infer_block_expr_type_mismatch() {
@@ -858,3 +858,57 @@ fn coerce_unsize_generic() {
858 "]], 858 "]],
859 ); 859 );
860} 860}
861
862#[test]
863fn infer_two_closures_lub() {
864 check_types(
865 r#"
866fn foo(c: i32) {
867 let add = |a: i32, b: i32| a + b;
868 let sub = |a, b| a - b;
869 //^ |i32, i32| -> i32
870 if c > 42 { add } else { sub };
871 //^ fn(i32, i32) -> i32
872}
873 "#,
874 )
875}
876
877#[test]
878fn infer_match_diverging_branch_1() {
879 check_types(
880 r#"
881enum Result<T> { Ok(T), Err }
882fn parse<T>() -> T { loop {} }
883
884fn test() -> i32 {
885 let a = match parse() {
886 Ok(val) => val,
887 Err => return 0,
888 };
889 a
890 //^ i32
891}
892 "#,
893 )
894}
895
896#[test]
897fn infer_match_diverging_branch_2() {
898 // same as 1 except for order of branches
899 check_types(
900 r#"
901enum Result<T> { Ok(T), Err }
902fn parse<T>() -> T { loop {} }
903
904fn test() -> i32 {
905 let a = match parse() {
906 Err => return 0,
907 Ok(val) => val,
908 };
909 a
910 //^ i32
911}
912 "#,
913 )
914}
diff --git a/crates/hir_ty/src/tests/patterns.rs b/crates/hir_ty/src/tests/patterns.rs
index ddbadbe40..cd08b5c7a 100644
--- a/crates/hir_ty/src/tests/patterns.rs
+++ b/crates/hir_ty/src/tests/patterns.rs
@@ -747,7 +747,7 @@ fn foo(tuple: (u8, i16, f32)) {
747 209..210 '_': (u8, i16, f32) 747 209..210 '_': (u8, i16, f32)
748 214..216 '{}': () 748 214..216 '{}': ()
749 136..142: expected (u8, i16, f32), got (u8, i16) 749 136..142: expected (u8, i16, f32), got (u8, i16)
750 170..182: expected (u8, i16, f32), got (u8, i16, f32, _) 750 170..182: expected (u8, i16, f32), got (u8, i16, f32, {unknown})
751 "#]], 751 "#]],
752 ); 752 );
753} 753}
diff --git a/crates/hir_ty/src/tests/regression.rs b/crates/hir_ty/src/tests/regression.rs
index 431861712..ad9edf11c 100644
--- a/crates/hir_ty/src/tests/regression.rs
+++ b/crates/hir_ty/src/tests/regression.rs
@@ -86,8 +86,6 @@ fn bug_651() {
86 86
87#[test] 87#[test]
88fn recursive_vars() { 88fn recursive_vars() {
89 cov_mark::check!(type_var_cycles_resolve_completely);
90 cov_mark::check!(type_var_cycles_resolve_as_possible);
91 check_infer( 89 check_infer(
92 r#" 90 r#"
93 fn test() { 91 fn test() {
@@ -97,12 +95,12 @@ fn recursive_vars() {
97 "#, 95 "#,
98 expect![[r#" 96 expect![[r#"
99 10..47 '{ ...&y]; }': () 97 10..47 '{ ...&y]; }': ()
100 20..21 'y': &{unknown} 98 20..21 'y': {unknown}
101 24..31 'unknown': &{unknown} 99 24..31 'unknown': {unknown}
102 37..44 '[y, &y]': [&&{unknown}; 2] 100 37..44 '[y, &y]': [{unknown}; 2]
103 38..39 'y': &{unknown} 101 38..39 'y': {unknown}
104 41..43 '&y': &&{unknown} 102 41..43 '&y': &{unknown}
105 42..43 'y': &{unknown} 103 42..43 'y': {unknown}
106 "#]], 104 "#]],
107 ); 105 );
108} 106}
@@ -119,19 +117,19 @@ fn recursive_vars_2() {
119 "#, 117 "#,
120 expect![[r#" 118 expect![[r#"
121 10..79 '{ ...x)]; }': () 119 10..79 '{ ...x)]; }': ()
122 20..21 'x': &&{unknown} 120 20..21 'x': &{unknown}
123 24..31 'unknown': &&{unknown} 121 24..31 'unknown': &{unknown}
124 41..42 'y': &&{unknown} 122 41..42 'y': {unknown}
125 45..52 'unknown': &&{unknown} 123 45..52 'unknown': {unknown}
126 58..76 '[(x, y..., &x)]': [(&&&{unknown}, &&&{unknown}); 2] 124 58..76 '[(x, y..., &x)]': [(&{unknown}, {unknown}); 2]
127 59..65 '(x, y)': (&&&{unknown}, &&&{unknown}) 125 59..65 '(x, y)': (&{unknown}, {unknown})
128 60..61 'x': &&{unknown} 126 60..61 'x': &{unknown}
129 63..64 'y': &&{unknown} 127 63..64 'y': {unknown}
130 67..75 '(&y, &x)': (&&&{unknown}, &&&{unknown}) 128 67..75 '(&y, &x)': (&{unknown}, {unknown})
131 68..70 '&y': &&&{unknown} 129 68..70 '&y': &{unknown}
132 69..70 'y': &&{unknown} 130 69..70 'y': {unknown}
133 72..74 '&x': &&&{unknown} 131 72..74 '&x': &&{unknown}
134 73..74 'x': &&{unknown} 132 73..74 'x': &{unknown}
135 "#]], 133 "#]],
136 ); 134 );
137} 135}
@@ -165,7 +163,6 @@ fn infer_std_crash_1() {
165 163
166#[test] 164#[test]
167fn infer_std_crash_2() { 165fn infer_std_crash_2() {
168 cov_mark::check!(type_var_resolves_to_int_var);
169 // caused "equating two type variables, ...", taken from std 166 // caused "equating two type variables, ...", taken from std
170 check_infer( 167 check_infer(
171 r#" 168 r#"
@@ -257,27 +254,27 @@ fn infer_std_crash_5() {
257 expect![[r#" 254 expect![[r#"
258 26..322 '{ ... } }': () 255 26..322 '{ ... } }': ()
259 32..320 'for co... }': () 256 32..320 'for co... }': ()
260 36..43 'content': &{unknown} 257 36..43 'content': {unknown}
261 47..60 'doesnt_matter': {unknown} 258 47..60 'doesnt_matter': {unknown}
262 61..320 '{ ... }': () 259 61..320 '{ ... }': ()
263 75..79 'name': &&{unknown} 260 75..79 'name': &{unknown}
264 82..166 'if doe... }': &&{unknown} 261 82..166 'if doe... }': &{unknown}
265 85..98 'doesnt_matter': bool 262 85..98 'doesnt_matter': bool
266 99..128 '{ ... }': &&{unknown} 263 99..128 '{ ... }': &{unknown}
267 113..118 'first': &&{unknown} 264 113..118 'first': &{unknown}
268 134..166 '{ ... }': &&{unknown} 265 134..166 '{ ... }': &{unknown}
269 148..156 '&content': &&{unknown} 266 148..156 '&content': &{unknown}
270 149..156 'content': &{unknown} 267 149..156 'content': {unknown}
271 181..188 'content': &{unknown} 268 181..188 'content': &{unknown}
272 191..313 'if ICE... }': &{unknown} 269 191..313 'if ICE... }': &{unknown}
273 194..231 'ICE_RE..._VALUE': {unknown} 270 194..231 'ICE_RE..._VALUE': {unknown}
274 194..247 'ICE_RE...&name)': bool 271 194..247 'ICE_RE...&name)': bool
275 241..246 '&name': &&&{unknown} 272 241..246 '&name': &&{unknown}
276 242..246 'name': &&{unknown} 273 242..246 'name': &{unknown}
277 248..276 '{ ... }': &&{unknown} 274 248..276 '{ ... }': &{unknown}
278 262..266 'name': &&{unknown} 275 262..266 'name': &{unknown}
279 282..313 '{ ... }': &{unknown} 276 282..313 '{ ... }': {unknown}
280 296..303 'content': &{unknown} 277 296..303 'content': {unknown}
281 "#]], 278 "#]],
282 ); 279 );
283} 280}
diff --git a/crates/hir_ty/src/tests/simple.rs b/crates/hir_ty/src/tests/simple.rs
index a9cd42186..5c70a1fc0 100644
--- a/crates/hir_ty/src/tests/simple.rs
+++ b/crates/hir_ty/src/tests/simple.rs
@@ -1040,42 +1040,6 @@ fn infer_in_elseif() {
1040} 1040}
1041 1041
1042#[test] 1042#[test]
1043fn infer_closure_unify() {
1044 check_infer(
1045 r#"
1046 fn foo(f: bool) {
1047 let a = |x| x;
1048 let b = |x| x;
1049 let id = if f { a } else { b };
1050 id(123);
1051 }
1052 "#,
1053 expect![[r#"
1054 7..8 'f': bool
1055 16..106 '{ ...23); }': ()
1056 26..27 'a': |i32| -> i32
1057 30..35 '|x| x': |i32| -> i32
1058 31..32 'x': i32
1059 34..35 'x': i32
1060 45..46 'b': |i32| -> i32
1061 49..54 '|x| x': |i32| -> i32
1062 50..51 'x': i32
1063 53..54 'x': i32
1064 64..66 'id': |i32| -> i32
1065 69..90 'if f {... { b }': |i32| -> i32
1066 72..73 'f': bool
1067 74..79 '{ a }': |i32| -> i32
1068 76..77 'a': |i32| -> i32
1069 85..90 '{ b }': |i32| -> i32
1070 87..88 'b': |i32| -> i32
1071 96..98 'id': |i32| -> i32
1072 96..103 'id(123)': i32
1073 99..102 '123': i32
1074 "#]],
1075 )
1076}
1077
1078#[test]
1079fn infer_if_match_with_return() { 1043fn infer_if_match_with_return() {
1080 check_infer( 1044 check_infer(
1081 r#" 1045 r#"
diff --git a/crates/hir_ty/src/tests/traits.rs b/crates/hir_ty/src/tests/traits.rs
index f80cf9879..a5a2df54c 100644
--- a/crates/hir_ty/src/tests/traits.rs
+++ b/crates/hir_ty/src/tests/traits.rs
@@ -3104,7 +3104,7 @@ fn foo() {
3104 568..573 'f(&s)': FnOnce::Output<dyn FnOnce(&Option<i32>), (&Option<i32>,)> 3104 568..573 'f(&s)': FnOnce::Output<dyn FnOnce(&Option<i32>), (&Option<i32>,)>
3105 570..572 '&s': &Option<i32> 3105 570..572 '&s': &Option<i32>
3106 571..572 's': Option<i32> 3106 571..572 's': Option<i32>
3107 549..562: expected Box<dyn FnOnce(&Option<i32>)>, got Box<|_| -> ()> 3107 549..562: expected Box<dyn FnOnce(&Option<i32>)>, got Box<|{unknown}| -> ()>
3108 "#]], 3108 "#]],
3109 ); 3109 );
3110} 3110}
diff --git a/crates/hir_ty/src/tls.rs b/crates/hir_ty/src/tls.rs
index 87c671a42..708797c47 100644
--- a/crates/hir_ty/src/tls.rs
+++ b/crates/hir_ty/src/tls.rs
@@ -1,7 +1,7 @@
1//! Implementation of Chalk debug helper functions using TLS. 1//! Implementation of Chalk debug helper functions using TLS.
2use std::fmt; 2use std::fmt::{self, Debug};
3 3
4use chalk_ir::{AliasTy, GenericArg, Goal, Goals, Lifetime, ProgramClauseImplication}; 4use chalk_ir::AliasTy;
5use itertools::Itertools; 5use itertools::Itertools;
6 6
7use crate::{ 7use crate::{
@@ -53,14 +53,6 @@ impl DebugContext<'_> {
53 write!(fmt, "{}::{}", trait_data.name, type_alias_data.name) 53 write!(fmt, "{}::{}", trait_data.name, type_alias_data.name)
54 } 54 }
55 55
56 pub(crate) fn debug_opaque_ty_id(
57 &self,
58 opaque_ty_id: chalk_ir::OpaqueTyId<Interner>,
59 fmt: &mut fmt::Formatter<'_>,
60 ) -> Result<(), fmt::Error> {
61 fmt.debug_struct("OpaqueTyId").field("index", &opaque_ty_id.0).finish()
62 }
63
64 pub(crate) fn debug_alias( 56 pub(crate) fn debug_alias(
65 &self, 57 &self,
66 alias_ty: &AliasTy<Interner>, 58 alias_ty: &AliasTy<Interner>,
@@ -68,7 +60,7 @@ impl DebugContext<'_> {
68 ) -> Result<(), fmt::Error> { 60 ) -> Result<(), fmt::Error> {
69 match alias_ty { 61 match alias_ty {
70 AliasTy::Projection(projection_ty) => self.debug_projection_ty(projection_ty, fmt), 62 AliasTy::Projection(projection_ty) => self.debug_projection_ty(projection_ty, fmt),
71 AliasTy::Opaque(opaque_ty) => self.debug_opaque_ty(opaque_ty, fmt), 63 AliasTy::Opaque(opaque_ty) => opaque_ty.fmt(fmt),
72 } 64 }
73 } 65 }
74 66
@@ -96,79 +88,6 @@ impl DebugContext<'_> {
96 write!(fmt, ">::{}", type_alias_data.name) 88 write!(fmt, ">::{}", type_alias_data.name)
97 } 89 }
98 90
99 pub(crate) fn debug_opaque_ty(
100 &self,
101 opaque_ty: &chalk_ir::OpaqueTy<Interner>,
102 fmt: &mut fmt::Formatter<'_>,
103 ) -> Result<(), fmt::Error> {
104 write!(fmt, "{:?}", opaque_ty.opaque_ty_id)
105 }
106
107 pub(crate) fn debug_ty(
108 &self,
109 ty: &chalk_ir::Ty<Interner>,
110 fmt: &mut fmt::Formatter<'_>,
111 ) -> Result<(), fmt::Error> {
112 write!(fmt, "{:?}", ty.data(&Interner))
113 }
114
115 pub(crate) fn debug_lifetime(
116 &self,
117 lifetime: &Lifetime<Interner>,
118 fmt: &mut fmt::Formatter<'_>,
119 ) -> Result<(), fmt::Error> {
120 write!(fmt, "{:?}", lifetime.data(&Interner))
121 }
122
123 pub(crate) fn debug_generic_arg(
124 &self,
125 parameter: &GenericArg<Interner>,
126 fmt: &mut fmt::Formatter<'_>,
127 ) -> Result<(), fmt::Error> {
128 write!(fmt, "{:?}", parameter.data(&Interner).inner_debug())
129 }
130
131 pub(crate) fn debug_goal(
132 &self,
133 goal: &Goal<Interner>,
134 fmt: &mut fmt::Formatter<'_>,
135 ) -> Result<(), fmt::Error> {
136 let goal_data = goal.data(&Interner);
137 write!(fmt, "{:?}", goal_data)
138 }
139
140 pub(crate) fn debug_goals(
141 &self,
142 goals: &Goals<Interner>,
143 fmt: &mut fmt::Formatter<'_>,
144 ) -> Result<(), fmt::Error> {
145 write!(fmt, "{:?}", goals.debug(&Interner))
146 }
147
148 pub(crate) fn debug_program_clause_implication(
149 &self,
150 pci: &ProgramClauseImplication<Interner>,
151 fmt: &mut fmt::Formatter<'_>,
152 ) -> Result<(), fmt::Error> {
153 write!(fmt, "{:?}", pci.debug(&Interner))
154 }
155
156 pub(crate) fn debug_substitution(
157 &self,
158 substitution: &chalk_ir::Substitution<Interner>,
159 fmt: &mut fmt::Formatter<'_>,
160 ) -> Result<(), fmt::Error> {
161 write!(fmt, "{:?}", substitution.debug(&Interner))
162 }
163
164 pub(crate) fn debug_separator_trait_ref(
165 &self,
166 separator_trait_ref: &chalk_ir::SeparatorTraitRef<Interner>,
167 fmt: &mut fmt::Formatter<'_>,
168 ) -> Result<(), fmt::Error> {
169 write!(fmt, "{:?}", separator_trait_ref.debug(&Interner))
170 }
171
172 pub(crate) fn debug_fn_def_id( 91 pub(crate) fn debug_fn_def_id(
173 &self, 92 &self,
174 fn_def_id: chalk_ir::FnDefId<Interner>, 93 fn_def_id: chalk_ir::FnDefId<Interner>,
@@ -190,57 +109,6 @@ impl DebugContext<'_> {
190 } 109 }
191 } 110 }
192 } 111 }
193
194 pub(crate) fn debug_const(
195 &self,
196 _constant: &chalk_ir::Const<Interner>,
197 fmt: &mut fmt::Formatter<'_>,
198 ) -> fmt::Result {
199 write!(fmt, "const")
200 }
201
202 pub(crate) fn debug_variable_kinds(
203 &self,
204 variable_kinds: &chalk_ir::VariableKinds<Interner>,
205 fmt: &mut fmt::Formatter<'_>,
206 ) -> fmt::Result {
207 write!(fmt, "{:?}", variable_kinds.as_slice(&Interner))
208 }
209 pub(crate) fn debug_variable_kinds_with_angles(
210 &self,
211 variable_kinds: &chalk_ir::VariableKinds<Interner>,
212 fmt: &mut fmt::Formatter<'_>,
213 ) -> fmt::Result {
214 write!(fmt, "{:?}", variable_kinds.inner_debug(&Interner))
215 }
216 pub(crate) fn debug_canonical_var_kinds(
217 &self,
218 canonical_var_kinds: &chalk_ir::CanonicalVarKinds<Interner>,
219 fmt: &mut fmt::Formatter<'_>,
220 ) -> fmt::Result {
221 write!(fmt, "{:?}", canonical_var_kinds.as_slice(&Interner))
222 }
223 pub(crate) fn debug_program_clause(
224 &self,
225 clause: &chalk_ir::ProgramClause<Interner>,
226 fmt: &mut fmt::Formatter<'_>,
227 ) -> fmt::Result {
228 write!(fmt, "{:?}", clause.data(&Interner))
229 }
230 pub(crate) fn debug_program_clauses(
231 &self,
232 clauses: &chalk_ir::ProgramClauses<Interner>,
233 fmt: &mut fmt::Formatter<'_>,
234 ) -> fmt::Result {
235 write!(fmt, "{:?}", clauses.as_slice(&Interner))
236 }
237 pub(crate) fn debug_quantified_where_clauses(
238 &self,
239 clauses: &chalk_ir::QuantifiedWhereClauses<Interner>,
240 fmt: &mut fmt::Formatter<'_>,
241 ) -> fmt::Result {
242 write!(fmt, "{:?}", clauses.as_slice(&Interner))
243 }
244} 112}
245 113
246mod unsafe_tls { 114mod unsafe_tls {
diff --git a/crates/hir_ty/src/traits.rs b/crates/hir_ty/src/traits.rs
index 9936d0803..294cb531c 100644
--- a/crates/hir_ty/src/traits.rs
+++ b/crates/hir_ty/src/traits.rs
@@ -2,7 +2,7 @@
2 2
3use std::env::var; 3use std::env::var;
4 4
5use chalk_ir::cast::Cast; 5use chalk_ir::GoalData;
6use chalk_solve::{logging_db::LoggingRustIrDatabase, Solver}; 6use chalk_solve::{logging_db::LoggingRustIrDatabase, Solver};
7 7
8use base_db::CrateId; 8use base_db::CrateId;
@@ -10,7 +10,7 @@ use hir_def::{lang_item::LangItemTarget, TraitId};
10use stdx::panic_context; 10use stdx::panic_context;
11 11
12use crate::{ 12use crate::{
13 db::HirDatabase, AliasEq, AliasTy, Canonical, DomainGoal, Guidance, HirDisplay, InEnvironment, 13 db::HirDatabase, AliasEq, AliasTy, Canonical, DomainGoal, Goal, Guidance, InEnvironment,
14 Interner, Solution, TraitRefExt, Ty, TyKind, WhereClause, 14 Interner, Solution, TraitRefExt, Ty, TyKind, WhereClause,
15}; 15};
16 16
@@ -38,6 +38,7 @@ fn create_chalk_solver() -> chalk_recursive::RecursiveSolver<Interner> {
38/// we assume that `T: Default`. 38/// we assume that `T: Default`.
39#[derive(Debug, Clone, PartialEq, Eq, Hash)] 39#[derive(Debug, Clone, PartialEq, Eq, Hash)]
40pub struct TraitEnvironment { 40pub struct TraitEnvironment {
41 pub krate: CrateId,
41 // When we're using Chalk's Ty we can make this a BTreeMap since it's Ord, 42 // When we're using Chalk's Ty we can make this a BTreeMap since it's Ord,
42 // but for now it's too annoying... 43 // but for now it's too annoying...
43 pub(crate) traits_from_clauses: Vec<(Ty, TraitId)>, 44 pub(crate) traits_from_clauses: Vec<(Ty, TraitId)>,
@@ -45,6 +46,14 @@ pub struct TraitEnvironment {
45} 46}
46 47
47impl TraitEnvironment { 48impl TraitEnvironment {
49 pub fn empty(krate: CrateId) -> Self {
50 TraitEnvironment {
51 krate,
52 traits_from_clauses: Vec::new(),
53 env: chalk_ir::Environment::new(&Interner),
54 }
55 }
56
48 pub(crate) fn traits_in_scope_from_clauses<'a>( 57 pub(crate) fn traits_in_scope_from_clauses<'a>(
49 &'a self, 58 &'a self,
50 ty: &'a Ty, 59 ty: &'a Ty,
@@ -59,34 +68,25 @@ impl TraitEnvironment {
59 } 68 }
60} 69}
61 70
62impl Default for TraitEnvironment {
63 fn default() -> Self {
64 TraitEnvironment {
65 traits_from_clauses: Vec::new(),
66 env: chalk_ir::Environment::new(&Interner),
67 }
68 }
69}
70
71/// Solve a trait goal using Chalk. 71/// Solve a trait goal using Chalk.
72pub(crate) fn trait_solve_query( 72pub(crate) fn trait_solve_query(
73 db: &dyn HirDatabase, 73 db: &dyn HirDatabase,
74 krate: CrateId, 74 krate: CrateId,
75 goal: Canonical<InEnvironment<DomainGoal>>, 75 goal: Canonical<InEnvironment<Goal>>,
76) -> Option<Solution> { 76) -> Option<Solution> {
77 let _p = profile::span("trait_solve_query").detail(|| match &goal.value.goal { 77 let _p = profile::span("trait_solve_query").detail(|| match &goal.value.goal.data(&Interner) {
78 DomainGoal::Holds(WhereClause::Implemented(it)) => { 78 GoalData::DomainGoal(DomainGoal::Holds(WhereClause::Implemented(it))) => {
79 db.trait_data(it.hir_trait_id()).name.to_string() 79 db.trait_data(it.hir_trait_id()).name.to_string()
80 } 80 }
81 DomainGoal::Holds(WhereClause::AliasEq(_)) => "alias_eq".to_string(), 81 GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(_))) => "alias_eq".to_string(),
82 _ => "??".to_string(), 82 _ => "??".to_string(),
83 }); 83 });
84 log::info!("trait_solve_query({})", goal.value.goal.display(db)); 84 log::info!("trait_solve_query({:?})", goal.value.goal);
85 85
86 if let DomainGoal::Holds(WhereClause::AliasEq(AliasEq { 86 if let GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(AliasEq {
87 alias: AliasTy::Projection(projection_ty), 87 alias: AliasTy::Projection(projection_ty),
88 .. 88 ..
89 })) = &goal.value.goal 89 }))) = &goal.value.goal.data(&Interner)
90 { 90 {
91 if let TyKind::BoundVar(_) = projection_ty.self_type_parameter(&Interner).kind(&Interner) { 91 if let TyKind::BoundVar(_) = projection_ty.self_type_parameter(&Interner).kind(&Interner) {
92 // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible 92 // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible
@@ -94,11 +94,9 @@ pub(crate) fn trait_solve_query(
94 } 94 }
95 } 95 }
96 96
97 let canonical = goal.cast(&Interner);
98
99 // We currently don't deal with universes (I think / hope they're not yet 97 // We currently don't deal with universes (I think / hope they're not yet
100 // relevant for our use cases?) 98 // relevant for our use cases?)
101 let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 }; 99 let u_canonical = chalk_ir::UCanonical { canonical: goal, universes: 1 };
102 solve(db, krate, &u_canonical) 100 solve(db, krate, &u_canonical)
103} 101}
104 102
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-16 18:25:34 +0000