crates/ra_hir/src/ty/infer.rs

   1 //! Type inference, i.e. the process of walking through the code and determining
   2 //! the type of each expression and pattern.
   3 //!
   4 //! For type inference, compare the implementations in rustc (the various
   5 //! check_* methods in librustc_typeck/check/mod.rs are a good entry point) and
   6 //! IntelliJ-Rust (org.rust.lang.core.types.infer). Our entry point for
   7 //! inference here is the `infer` function, which infers the types of all
   8 //! expressions in a given function.
   9 //!
  10 //! During inference, types (i.e. the `Ty` struct) can contain type 'variables'
  11 //! which represent currently unknown types; as we walk through the expressions,
  12 //! we might determine that certain variables need to be equal to each other, or
  13 //! to certain types. To record this, we use the union-find implementation from
  14 //! the `ena` crate, which is extracted from rustc.
  15
  16 use std::borrow::Cow;
  17 use std::iter::repeat;
  18 use std::mem;
  19 use std::ops::Index;
  20 use std::sync::Arc;
  21
  22 use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
  23 use rustc_hash::FxHashMap;
  24
  25 use ra_arena::map::ArenaMap;
  26 use ra_prof::profile;
  27 use test_utils::tested_by;
  28
  29 use super::{
  30     autoderef, lower, method_resolution, op, primitive,
  31     traits::{Guidance, Obligation, ProjectionPredicate, Solution},
  32     ApplicationTy, CallableDef, InEnvironment, ProjectionTy, Substs, TraitEnvironment, TraitRef,
  33     Ty, TypableDef, TypeCtor,
  34 };
  35 use crate::{
  36     adt::VariantDef,
  37     code_model::{ModuleDef::Trait, TypeAlias},
  38     diagnostics::DiagnosticSink,
  39     expr::{
  40         self, Array, BinaryOp, BindingAnnotation, Body, Expr, ExprId, FieldPat, Literal, Pat,
  41         PatId, Statement, UnaryOp,
  42     },
  43     generics::{GenericParams, HasGenericParams},
  44     name,
  45     nameres::{Namespace, PerNs},
  46     path::{GenericArg, GenericArgs, PathKind, PathSegment},
  47     resolve::{
  48         Resolution::{self, Def},
  49         Resolver,
  50     },
  51     ty::infer::diagnostics::InferenceDiagnostic,
  52     type_ref::{Mutability, TypeRef},
  53     AdtDef, ConstData, DefWithBody, FnData, Function, HirDatabase, ImplItem, ModuleDef, Name, Path,
  54     StructField,
  55 };
  56
  57 mod unify;
  58
  59 /// The entry point of type inference.
  60 pub fn infer_query(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
  61     let _p = profile("infer_query");
  62     let body = def.body(db);
  63     let resolver = def.resolver(db);
  64     let mut ctx = InferenceContext::new(db, body, resolver);
  65
  66     match def {
  67         DefWithBody::Const(ref c) => ctx.collect_const(&c.data(db)),
  68         DefWithBody::Function(ref f) => ctx.collect_fn(&f.data(db)),
  69         DefWithBody::Static(ref s) => ctx.collect_const(&s.data(db)),
  70     }
  71
  72     ctx.infer_body();
  73
  74     Arc::new(ctx.resolve_all())
  75 }
  76
  77 #[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
  78 enum ExprOrPatId {
  79     ExprId(ExprId),
  80     PatId(PatId),
  81 }
  82
  83 impl_froms!(ExprOrPatId: ExprId, PatId);
  84
  85 /// Binding modes inferred for patterns.
  86 /// https://doc.rust-lang.org/reference/patterns.html#binding-modes
  87 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
  88 enum BindingMode {
  89     Move,
  90     Ref(Mutability),
  91 }
  92
  93 impl BindingMode {
  94     pub fn convert(annotation: BindingAnnotation) -> BindingMode {
  95         match annotation {
  96             BindingAnnotation::Unannotated | BindingAnnotation::Mutable => BindingMode::Move,
  97             BindingAnnotation::Ref => BindingMode::Ref(Mutability::Shared),
  98             BindingAnnotation::RefMut => BindingMode::Ref(Mutability::Mut),
  99         }
 100     }
 101 }
 102
 103 impl Default for BindingMode {
 104     fn default() -> Self {
 105         BindingMode::Move
 106     }
 107 }
 108
 109 /// The result of type inference: A mapping from expressions and patterns to types.
 110 #[derive(Clone, PartialEq, Eq, Debug, Default)]
 111 pub struct InferenceResult {
 112     /// For each method call expr, records the function it resolves to.
 113     method_resolutions: FxHashMap<ExprId, Function>,
 114     /// For each field access expr, records the field it resolves to.
 115     field_resolutions: FxHashMap<ExprId, StructField>,
 116     /// For each struct literal, records the variant it resolves to.
 117     variant_resolutions: FxHashMap<ExprOrPatId, VariantDef>,
 118     /// For each associated item record what it resolves to
 119     assoc_resolutions: FxHashMap<ExprOrPatId, ImplItem>,
 120     diagnostics: Vec<InferenceDiagnostic>,
 121     pub(super) type_of_expr: ArenaMap<ExprId, Ty>,
 122     pub(super) type_of_pat: ArenaMap<PatId, Ty>,
 123 }
 124
 125 impl InferenceResult {
 126     pub fn method_resolution(&self, expr: ExprId) -> Option<Function> {
 127         self.method_resolutions.get(&expr).copied()
 128     }
 129     pub fn field_resolution(&self, expr: ExprId) -> Option<StructField> {
 130         self.field_resolutions.get(&expr).copied()
 131     }
 132     pub fn variant_resolution_for_expr(&self, id: ExprId) -> Option<VariantDef> {
 133         self.variant_resolutions.get(&id.into()).copied()
 134     }
 135     pub fn variant_resolution_for_pat(&self, id: PatId) -> Option<VariantDef> {
 136         self.variant_resolutions.get(&id.into()).copied()
 137     }
 138     pub fn assoc_resolutions_for_expr(&self, id: ExprId) -> Option<ImplItem> {
 139         self.assoc_resolutions.get(&id.into()).copied()
 140     }
 141     pub fn assoc_resolutions_for_pat(&self, id: PatId) -> Option<ImplItem> {
 142         self.assoc_resolutions.get(&id.into()).copied()
 143     }
 144     pub(crate) fn add_diagnostics(
 145         &self,
 146         db: &impl HirDatabase,
 147         owner: Function,
 148         sink: &mut DiagnosticSink,
 149     ) {
 150         self.diagnostics.iter().for_each(|it| it.add_to(db, owner, sink))
 151     }
 152 }
 153
 154 impl Index<ExprId> for InferenceResult {
 155     type Output = Ty;
 156
 157     fn index(&self, expr: ExprId) -> &Ty {
 158         self.type_of_expr.get(expr).unwrap_or(&Ty::Unknown)
 159     }
 160 }
 161
 162 impl Index<PatId> for InferenceResult {
 163     type Output = Ty;
 164
 165     fn index(&self, pat: PatId) -> &Ty {
 166         self.type_of_pat.get(pat).unwrap_or(&Ty::Unknown)
 167     }
 168 }
 169
 170 /// The inference context contains all information needed during type inference.
 171 #[derive(Clone, Debug)]
 172 struct InferenceContext<'a, D: HirDatabase> {
 173     db: &'a D,
 174     body: Arc<Body>,
 175     resolver: Resolver,
 176     var_unification_table: InPlaceUnificationTable<TypeVarId>,
 177     trait_env: Arc<TraitEnvironment>,
 178     obligations: Vec<Obligation>,
 179     result: InferenceResult,
 180     /// The return type of the function being inferred.
 181     return_ty: Ty,
 182 }
 183
 184 impl<'a, D: HirDatabase> InferenceContext<'a, D> {
 185     fn new(db: &'a D, body: Arc<Body>, resolver: Resolver) -> Self {
 186         InferenceContext {
 187             result: InferenceResult::default(),
 188             var_unification_table: InPlaceUnificationTable::new(),
 189             obligations: Vec::default(),
 190             return_ty: Ty::Unknown, // set in collect_fn_signature
 191             trait_env: lower::trait_env(db, &resolver),
 192             db,
 193             body,
 194             resolver,
 195         }
 196     }
 197
 198     fn resolve_all(mut self) -> InferenceResult {
 199         // FIXME resolve obligations as well (use Guidance if necessary)
 200         let mut result = mem::replace(&mut self.result, InferenceResult::default());
 201         let mut tv_stack = Vec::new();
 202         for ty in result.type_of_expr.values_mut() {
 203             let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown));
 204             *ty = resolved;
 205         }
 206         for ty in result.type_of_pat.values_mut() {
 207             let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown));
 208             *ty = resolved;
 209         }
 210         result
 211     }
 212
 213     fn write_expr_ty(&mut self, expr: ExprId, ty: Ty) {
 214         self.result.type_of_expr.insert(expr, ty);
 215     }
 216
 217     fn write_method_resolution(&mut self, expr: ExprId, func: Function) {
 218         self.result.method_resolutions.insert(expr, func);
 219     }
 220
 221     fn write_field_resolution(&mut self, expr: ExprId, field: StructField) {
 222         self.result.field_resolutions.insert(expr, field);
 223     }
 224
 225     fn write_variant_resolution(&mut self, id: ExprOrPatId, variant: VariantDef) {
 226         self.result.variant_resolutions.insert(id, variant);
 227     }
 228
 229     fn write_assoc_resolution(&mut self, id: ExprOrPatId, item: ImplItem) {
 230         self.result.assoc_resolutions.insert(id, item);
 231     }
 232
 233     fn write_pat_ty(&mut self, pat: PatId, ty: Ty) {
 234         self.result.type_of_pat.insert(pat, ty);
 235     }
 236
 237     fn push_diagnostic(&mut self, diagnostic: InferenceDiagnostic) {
 238         self.result.diagnostics.push(diagnostic);
 239     }
 240
 241     fn make_ty(&mut self, type_ref: &TypeRef) -> Ty {
 242         let ty = Ty::from_hir(
 243             self.db,
 244             // FIXME use right resolver for block
 245             &self.resolver,
 246             type_ref,
 247         );
 248         let ty = self.insert_type_vars(ty);
 249         self.normalize_associated_types_in(ty)
 250     }
 251
 252     fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool {
 253         substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth))
 254     }
 255
 256     fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
 257         self.unify_inner(ty1, ty2, 0)
 258     }
 259
 260     fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
 261         if depth > 1000 {
 262             // prevent stackoverflows
 263             panic!("infinite recursion in unification");
 264         }
 265         if ty1 == ty2 {
 266             return true;
 267         }
 268         // try to resolve type vars first
 269         let ty1 = self.resolve_ty_shallow(ty1);
 270         let ty2 = self.resolve_ty_shallow(ty2);
 271         match (&*ty1, &*ty2) {
 272             (Ty::Unknown, ..) => true,
 273             (.., Ty::Unknown) => true,
 274             (Ty::Apply(a_ty1), Ty::Apply(a_ty2)) if a_ty1.ctor == a_ty2.ctor => {
 275                 self.unify_substs(&a_ty1.parameters, &a_ty2.parameters, depth + 1)
 276             }
 277             (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2)))
 278             | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2)))
 279             | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2))) => {
 280                 // both type vars are unknown since we tried to resolve them
 281                 self.var_unification_table.union(*tv1, *tv2);
 282                 true
 283             }
 284             (Ty::Infer(InferTy::TypeVar(tv)), other)
 285             | (other, Ty::Infer(InferTy::TypeVar(tv)))
 286             | (Ty::Infer(InferTy::IntVar(tv)), other)
 287             | (other, Ty::Infer(InferTy::IntVar(tv)))
 288             | (Ty::Infer(InferTy::FloatVar(tv)), other)
 289             | (other, Ty::Infer(InferTy::FloatVar(tv))) => {
 290                 // the type var is unknown since we tried to resolve it
 291                 self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone()));
 292                 true
 293             }
 294             _ => false,
 295         }
 296     }
 297
 298     fn new_type_var(&mut self) -> Ty {
 299         Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
 300     }
 301
 302     fn new_integer_var(&mut self) -> Ty {
 303         Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
 304     }
 305
 306     fn new_float_var(&mut self) -> Ty {
 307         Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
 308     }
 309
 310     /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it.
 311     fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty {
 312         match ty {
 313             Ty::Unknown => self.new_type_var(),
 314             Ty::Apply(ApplicationTy {
 315                 ctor: TypeCtor::Int(primitive::UncertainIntTy::Unknown),
 316                 ..
 317             }) => self.new_integer_var(),
 318             Ty::Apply(ApplicationTy {
 319                 ctor: TypeCtor::Float(primitive::UncertainFloatTy::Unknown),
 320                 ..
 321             }) => self.new_float_var(),
 322             _ => ty,
 323         }
 324     }
 325
 326     fn insert_type_vars(&mut self, ty: Ty) -> Ty {
 327         ty.fold(&mut |ty| self.insert_type_vars_shallow(ty))
 328     }
 329
 330     fn resolve_obligations_as_possible(&mut self) {
 331         let obligations = mem::replace(&mut self.obligations, Vec::new());
 332         for obligation in obligations {
 333             let in_env = InEnvironment::new(self.trait_env.clone(), obligation.clone());
 334             let canonicalized = self.canonicalizer().canonicalize_obligation(in_env);
 335             let solution =
 336                 self.db.trait_solve(self.resolver.krate().unwrap(), canonicalized.value.clone());
 337
 338             match solution {
 339                 Some(Solution::Unique(substs)) => {
 340                     canonicalized.apply_solution(self, substs.0);
 341                 }
 342                 Some(Solution::Ambig(Guidance::Definite(substs))) => {
 343                     canonicalized.apply_solution(self, substs.0);
 344                     self.obligations.push(obligation);
 345                 }
 346                 Some(_) => {
 347                     // FIXME use this when trying to resolve everything at the end
 348                     self.obligations.push(obligation);
 349                 }
 350                 None => {
 351                     // FIXME obligation cannot be fulfilled => diagnostic
 352                 }
 353             };
 354         }
 355     }
 356
 357     /// Resolves the type as far as currently possible, replacing type variables
 358     /// by their known types. All types returned by the infer_* functions should
 359     /// be resolved as far as possible, i.e. contain no type variables with
 360     /// known type.
 361     fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
 362         self.resolve_obligations_as_possible();
 363
 364         ty.fold(&mut |ty| match ty {
 365             Ty::Infer(tv) => {
 366                 let inner = tv.to_inner();
 367                 if tv_stack.contains(&inner) {
 368                     tested_by!(type_var_cycles_resolve_as_possible);
 369                     // recursive type
 370                     return tv.fallback_value();
 371                 }
 372                 if let Some(known_ty) = self.var_unification_table.probe_value(inner).known() {
 373                     // known_ty may contain other variables that are known by now
 374                     tv_stack.push(inner);
 375                     let result = self.resolve_ty_as_possible(tv_stack, known_ty.clone());
 376                     tv_stack.pop();
 377                     result
 378                 } else {
 379                     ty
 380                 }
 381             }
 382             _ => ty,
 383         })
 384     }
 385
 386     /// If `ty` is a type variable with known type, returns that type;
 387     /// otherwise, return ty.
 388     fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
 389         let mut ty = Cow::Borrowed(ty);
 390         // The type variable could resolve to a int/float variable. Hence try
 391         // resolving up to three times; each type of variable shouldn't occur
 392         // more than once
 393         for i in 0..3 {
 394             if i > 0 {
 395                 tested_by!(type_var_resolves_to_int_var);
 396             }
 397             match &*ty {
 398                 Ty::Infer(tv) => {
 399                     let inner = tv.to_inner();
 400                     match self.var_unification_table.probe_value(inner).known() {
 401                         Some(known_ty) => {
 402                             // The known_ty can't be a type var itself
 403                             ty = Cow::Owned(known_ty.clone());
 404                         }
 405                         _ => return ty,
 406                     }
 407                 }
 408                 _ => return ty,
 409             }
 410         }
 411         log::error!("Inference variable still not resolved: {:?}", ty);
 412         ty
 413     }
 414
 415     /// Recurses through the given type, normalizing associated types mentioned
 416     /// in it by replacing them by type variables and registering obligations to
 417     /// resolve later. This should be done once for every type we get from some
 418     /// type annotation (e.g. from a let type annotation, field type or function
 419     /// call). `make_ty` handles this already, but e.g. for field types we need
 420     /// to do it as well.
 421     fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
 422         let ty = self.resolve_ty_as_possible(&mut vec![], ty);
 423         ty.fold(&mut |ty| match ty {
 424             Ty::Projection(proj_ty) => self.normalize_projection_ty(proj_ty),
 425             Ty::UnselectedProjection(proj_ty) => {
 426                 // FIXME use Chalk's unselected projection support
 427                 Ty::UnselectedProjection(proj_ty)
 428             }
 429             _ => ty,
 430         })
 431     }
 432
 433     fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
 434         let var = self.new_type_var();
 435         let predicate = ProjectionPredicate { projection_ty: proj_ty.clone(), ty: var.clone() };
 436         let obligation = Obligation::Projection(predicate);
 437         self.obligations.push(obligation);
 438         var
 439     }
 440
 441     /// Resolves the type completely; type variables without known type are
 442     /// replaced by Ty::Unknown.
 443     fn resolve_ty_completely(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
 444         ty.fold(&mut |ty| match ty {
 445             Ty::Infer(tv) => {
 446                 let inner = tv.to_inner();
 447                 if tv_stack.contains(&inner) {
 448                     tested_by!(type_var_cycles_resolve_completely);
 449                     // recursive type
 450                     return tv.fallback_value();
 451                 }
 452                 if let Some(known_ty) = self.var_unification_table.probe_value(inner).known() {
 453                     // known_ty may contain other variables that are known by now
 454                     tv_stack.push(inner);
 455                     let result = self.resolve_ty_completely(tv_stack, known_ty.clone());
 456                     tv_stack.pop();
 457                     result
 458                 } else {
 459                     tv.fallback_value()
 460                 }
 461             }
 462             _ => ty,
 463         })
 464     }
 465
 466     fn infer_path_expr(&mut self, resolver: &Resolver, path: &Path, id: ExprOrPatId) -> Option<Ty> {
 467         let resolved = resolver.resolve_path_segments(self.db, &path);
 468
 469         let (def, remaining_index) = resolved.into_inner();
 470
 471         log::debug!(
 472             "path {:?} resolved to {:?} with remaining index {:?}",
 473             path,
 474             def,
 475             remaining_index
 476         );
 477
 478         // if the remaining_index is None, we expect the path
 479         // to be fully resolved, in this case we continue with
 480         // the default by attempting to `take_values´ from the resolution.
 481         // Otherwise the path was partially resolved, which means
 482         // we might have resolved into a type for which
 483         // we may find some associated item starting at the
 484         // path.segment pointed to by `remaining_index´
 485         let mut resolved =
 486             if remaining_index.is_none() { def.take_values()? } else { def.take_types()? };
 487
 488         let remaining_index = remaining_index.unwrap_or_else(|| path.segments.len());
 489         let mut actual_def_ty: Option<Ty> = None;
 490
 491         let krate = resolver.krate()?;
 492         // resolve intermediate segments
 493         for (i, segment) in path.segments[remaining_index..].iter().enumerate() {
 494             let ty = match resolved {
 495                 Resolution::Def(def) => {
 496                     // FIXME resolve associated items from traits as well
 497                     let typable: Option<TypableDef> = def.into();
 498                     let typable = typable?;
 499
 500                     let ty = self.db.type_for_def(typable, Namespace::Types);
 501
 502                     // For example, this substs will take `Gen::*<u32>*::make`
 503                     assert!(remaining_index > 0);
 504                     let substs = Ty::substs_from_path_segment(
 505                         self.db,
 506                         &self.resolver,
 507                         &path.segments[remaining_index + i - 1],
 508                         typable,
 509                     );
 510
 511                     ty.subst(&substs)
 512                 }
 513                 Resolution::LocalBinding(_) => {
 514                     // can't have a local binding in an associated item path
 515                     return None;
 516                 }
 517                 Resolution::GenericParam(..) => {
 518                     // FIXME associated item of generic param
 519                     return None;
 520                 }
 521                 Resolution::SelfType(_) => {
 522                     // FIXME associated item of self type
 523                     return None;
 524                 }
 525             };
 526
 527             // Attempt to find an impl_item for the type which has a name matching
 528             // the current segment
 529             log::debug!("looking for path segment: {:?}", segment);
 530
 531             actual_def_ty = Some(ty.clone());
 532
 533             let item: crate::ModuleDef = ty.iterate_impl_items(self.db, krate, |item| {
 534                 let matching_def: Option<crate::ModuleDef> = match item {
 535                     crate::ImplItem::Method(func) => {
 536                         if segment.name == func.name(self.db) {
 537                             Some(func.into())
 538                         } else {
 539                             None
 540                         }
 541                     }
 542
 543                     crate::ImplItem::Const(konst) => {
 544                         let data = konst.data(self.db);
 545                         if segment.name == *data.name() {
 546                             Some(konst.into())
 547                         } else {
 548                             None
 549                         }
 550                     }
 551
 552                     // FIXME: Resolve associated types
 553                     crate::ImplItem::TypeAlias(_) => None,
 554                 };
 555                 match matching_def {
 556                     Some(_) => {
 557                         self.write_assoc_resolution(id, item);
 558                         matching_def
 559                     }
 560                     None => None,
 561                 }
 562             })?;
 563
 564             resolved = Resolution::Def(item);
 565         }
 566
 567         match resolved {
 568             Resolution::Def(def) => {
 569                 let typable: Option<TypableDef> = def.into();
 570                 let typable = typable?;
 571                 let mut ty = self.db.type_for_def(typable, Namespace::Values);
 572                 if let Some(sts) = self.find_self_types(&def, actual_def_ty) {
 573                     ty = ty.subst(&sts);
 574                 }
 575
 576                 let substs = Ty::substs_from_path(self.db, &self.resolver, path, typable);
 577                 let ty = ty.subst(&substs);
 578                 let ty = self.insert_type_vars(ty);
 579                 let ty = self.normalize_associated_types_in(ty);
 580                 Some(ty)
 581             }
 582             Resolution::LocalBinding(pat) => {
 583                 let ty = self.result.type_of_pat.get(pat)?.clone();
 584                 let ty = self.resolve_ty_as_possible(&mut vec![], ty);
 585                 Some(ty)
 586             }
 587             Resolution::GenericParam(..) => {
 588                 // generic params can't refer to values... yet
 589                 None
 590             }
 591             Resolution::SelfType(_) => {
 592                 log::error!("path expr {:?} resolved to Self type in values ns", path);
 593                 None
 594             }
 595         }
 596     }
 597
 598     fn find_self_types(&self, def: &ModuleDef, actual_def_ty: Option<Ty>) -> Option<Substs> {
 599         let actual_def_ty = actual_def_ty?;
 600
 601         if let crate::ModuleDef::Function(func) = def {
 602             // We only do the infer if parent has generic params
 603             let gen = func.generic_params(self.db);
 604             if gen.count_parent_params() == 0 {
 605                 return None;
 606             }
 607
 608             let impl_block = func.impl_block(self.db)?.target_ty(self.db);
 609             let impl_block_substs = impl_block.substs()?;
 610             let actual_substs = actual_def_ty.substs()?;
 611
 612             let mut new_substs = vec![Ty::Unknown; gen.count_parent_params()];
 613
 614             // The following code *link up* the function actual parma type
 615             // and impl_block type param index
 616             impl_block_substs.iter().zip(actual_substs.iter()).for_each(|(param, pty)| {
 617                 if let Ty::Param { idx, .. } = param {
 618                     if let Some(s) = new_substs.get_mut(*idx as usize) {
 619                         *s = pty.clone();
 620                     }
 621                 }
 622             });
 623
 624             Some(Substs(new_substs.into()))
 625         } else {
 626             None
 627         }
 628     }
 629
 630     fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantDef>) {
 631         let path = match path {
 632             Some(path) => path,
 633             None => return (Ty::Unknown, None),
 634         };
 635         let resolver = &self.resolver;
 636         let typable: Option<TypableDef> =
 637             // FIXME: this should resolve assoc items as well, see this example:
 638             // https://play.rust-lang.org/?gist=087992e9e22495446c01c0d4e2d69521
 639             match resolver.resolve_path_without_assoc_items(self.db, &path).take_types() {
 640                 Some(Resolution::Def(def)) => def.into(),
 641                 Some(Resolution::LocalBinding(..)) => {
 642                     // this cannot happen
 643                     log::error!("path resolved to local binding in type ns");
 644                     return (Ty::Unknown, None);
 645                 }
 646                 Some(Resolution::GenericParam(..)) => {
 647                     // generic params can't be used in struct literals
 648                     return (Ty::Unknown, None);
 649                 }
 650                 Some(Resolution::SelfType(..)) => {
 651                     // FIXME this is allowed in an impl for a struct, handle this
 652                     return (Ty::Unknown, None);
 653                 }
 654                 None => return (Ty::Unknown, None),
 655             };
 656         let def = match typable {
 657             None => return (Ty::Unknown, None),
 658             Some(it) => it,
 659         };
 660         // FIXME remove the duplication between here and `Ty::from_path`?
 661         let substs = Ty::substs_from_path(self.db, resolver, path, def);
 662         match def {
 663             TypableDef::Struct(s) => {
 664                 let ty = s.ty(self.db);
 665                 let ty = self.insert_type_vars(ty.apply_substs(substs));
 666                 (ty, Some(s.into()))
 667             }
 668             TypableDef::EnumVariant(var) => {
 669                 let ty = var.parent_enum(self.db).ty(self.db);
 670                 let ty = self.insert_type_vars(ty.apply_substs(substs));
 671                 (ty, Some(var.into()))
 672             }
 673             TypableDef::Union(_)
 674             | TypableDef::TypeAlias(_)
 675             | TypableDef::Function(_)
 676             | TypableDef::Enum(_)
 677             | TypableDef::Const(_)
 678             | TypableDef::Static(_)
 679             | TypableDef::BuiltinType(_) => (Ty::Unknown, None),
 680         }
 681     }
 682
 683     fn infer_tuple_struct_pat(
 684         &mut self,
 685         path: Option<&Path>,
 686         subpats: &[PatId],
 687         expected: &Ty,
 688         default_bm: BindingMode,
 689     ) -> Ty {
 690         let (ty, def) = self.resolve_variant(path);
 691
 692         self.unify(&ty, expected);
 693
 694         let substs = ty.substs().unwrap_or_else(Substs::empty);
 695
 696         for (i, &subpat) in subpats.iter().enumerate() {
 697             let expected_ty = def
 698                 .and_then(|d| d.field(self.db, &Name::tuple_field_name(i)))
 699                 .map_or(Ty::Unknown, |field| field.ty(self.db))
 700                 .subst(&substs);
 701             let expected_ty = self.normalize_associated_types_in(expected_ty);
 702             self.infer_pat(subpat, &expected_ty, default_bm);
 703         }
 704
 705         ty
 706     }
 707
 708     fn infer_struct_pat(
 709         &mut self,
 710         path: Option<&Path>,
 711         subpats: &[FieldPat],
 712         expected: &Ty,
 713         default_bm: BindingMode,
 714         id: PatId,
 715     ) -> Ty {
 716         let (ty, def) = self.resolve_variant(path);
 717         if let Some(variant) = def {
 718             self.write_variant_resolution(id.into(), variant);
 719         }
 720
 721         self.unify(&ty, expected);
 722
 723         let substs = ty.substs().unwrap_or_else(Substs::empty);
 724
 725         for subpat in subpats {
 726             let matching_field = def.and_then(|it| it.field(self.db, &subpat.name));
 727             let expected_ty =
 728                 matching_field.map_or(Ty::Unknown, |field| field.ty(self.db)).subst(&substs);
 729             let expected_ty = self.normalize_associated_types_in(expected_ty);
 730             self.infer_pat(subpat.pat, &expected_ty, default_bm);
 731         }
 732
 733         ty
 734     }
 735
 736     fn infer_pat(&mut self, pat: PatId, mut expected: &Ty, mut default_bm: BindingMode) -> Ty {
 737         let body = Arc::clone(&self.body); // avoid borrow checker problem
 738
 739         let is_non_ref_pat = match &body[pat] {
 740             Pat::Tuple(..)
 741             | Pat::TupleStruct { .. }
 742             | Pat::Struct { .. }
 743             | Pat::Range { .. }
 744             | Pat::Slice { .. } => true,
 745             // FIXME: Path/Lit might actually evaluate to ref, but inference is unimplemented.
 746             Pat::Path(..) | Pat::Lit(..) => true,
 747             Pat::Wild | Pat::Bind { .. } | Pat::Ref { .. } | Pat::Missing => false,
 748         };
 749         if is_non_ref_pat {
 750             while let Some((inner, mutability)) = expected.as_reference() {
 751                 expected = inner;
 752                 default_bm = match default_bm {
 753                     BindingMode::Move => BindingMode::Ref(mutability),
 754                     BindingMode::Ref(Mutability::Shared) => BindingMode::Ref(Mutability::Shared),
 755                     BindingMode::Ref(Mutability::Mut) => BindingMode::Ref(mutability),
 756                 }
 757             }
 758         } else if let Pat::Ref { .. } = &body[pat] {
 759             tested_by!(match_ergonomics_ref);
 760             // When you encounter a `&pat` pattern, reset to Move.
 761             // This is so that `w` is by value: `let (_, &w) = &(1, &2);`
 762             default_bm = BindingMode::Move;
 763         }
 764
 765         // Lose mutability.
 766         let default_bm = default_bm;
 767         let expected = expected;
 768
 769         let ty = match &body[pat] {
 770             Pat::Tuple(ref args) => {
 771                 let expectations = match expected.as_tuple() {
 772                     Some(parameters) => &*parameters.0,
 773                     _ => &[],
 774                 };
 775                 let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown));
 776
 777                 let inner_tys: Substs = args
 778                     .iter()
 779                     .zip(expectations_iter)
 780                     .map(|(&pat, ty)| self.infer_pat(pat, ty, default_bm))
 781                     .collect::<Vec<_>>()
 782                     .into();
 783
 784                 Ty::apply(TypeCtor::Tuple { cardinality: inner_tys.len() as u16 }, inner_tys)
 785             }
 786             Pat::Ref { pat, mutability } => {
 787                 let expectation = match expected.as_reference() {
 788                     Some((inner_ty, exp_mut)) => {
 789                         if *mutability != exp_mut {
 790                             // FIXME: emit type error?
 791                         }
 792                         inner_ty
 793                     }
 794                     _ => &Ty::Unknown,
 795                 };
 796                 let subty = self.infer_pat(*pat, expectation, default_bm);
 797                 Ty::apply_one(TypeCtor::Ref(*mutability), subty)
 798             }
 799             Pat::TupleStruct { path: ref p, args: ref subpats } => {
 800                 self.infer_tuple_struct_pat(p.as_ref(), subpats, expected, default_bm)
 801             }
 802             Pat::Struct { path: ref p, args: ref fields } => {
 803                 self.infer_struct_pat(p.as_ref(), fields, expected, default_bm, pat)
 804             }
 805             Pat::Path(path) => {
 806                 // FIXME use correct resolver for the surrounding expression
 807                 let resolver = self.resolver.clone();
 808                 self.infer_path_expr(&resolver, &path, pat.into()).unwrap_or(Ty::Unknown)
 809             }
 810             Pat::Bind { mode, name: _name, subpat } => {
 811                 let mode = if mode == &BindingAnnotation::Unannotated {
 812                     default_bm
 813                 } else {
 814                     BindingMode::convert(*mode)
 815                 };
 816                 let inner_ty = if let Some(subpat) = subpat {
 817                     self.infer_pat(*subpat, expected, default_bm)
 818                 } else {
 819                     expected.clone()
 820                 };
 821                 let inner_ty = self.insert_type_vars_shallow(inner_ty);
 822
 823                 let bound_ty = match mode {
 824                     BindingMode::Ref(mutability) => {
 825                         Ty::apply_one(TypeCtor::Ref(mutability), inner_ty.clone())
 826                     }
 827                     BindingMode::Move => inner_ty.clone(),
 828                 };
 829                 let bound_ty = self.resolve_ty_as_possible(&mut vec![], bound_ty);
 830                 self.write_pat_ty(pat, bound_ty);
 831                 return inner_ty;
 832             }
 833             _ => Ty::Unknown,
 834         };
 835         // use a new type variable if we got Ty::Unknown here
 836         let ty = self.insert_type_vars_shallow(ty);
 837         self.unify(&ty, expected);
 838         let ty = self.resolve_ty_as_possible(&mut vec![], ty);
 839         self.write_pat_ty(pat, ty.clone());
 840         ty
 841     }
 842
 843     fn substs_for_method_call(
 844         &mut self,
 845         def_generics: Option<Arc<GenericParams>>,
 846         generic_args: Option<&GenericArgs>,
 847         receiver_ty: &Ty,
 848     ) -> Substs {
 849         let (parent_param_count, param_count) =
 850             def_generics.as_ref().map_or((0, 0), |g| (g.count_parent_params(), g.params.len()));
 851         let mut substs = Vec::with_capacity(parent_param_count + param_count);
 852         // Parent arguments are unknown, except for the receiver type
 853         if let Some(parent_generics) = def_generics.and_then(|p| p.parent_params.clone()) {
 854             for param in &parent_generics.params {
 855                 if param.name == name::SELF_TYPE {
 856                     substs.push(receiver_ty.clone());
 857                 } else {
 858                     substs.push(Ty::Unknown);
 859                 }
 860             }
 861         }
 862         // handle provided type arguments
 863         if let Some(generic_args) = generic_args {
 864             // if args are provided, it should be all of them, but we can't rely on that
 865             for arg in generic_args.args.iter().take(param_count) {
 866                 match arg {
 867                     GenericArg::Type(type_ref) => {
 868                         let ty = self.make_ty(type_ref);
 869                         substs.push(ty);
 870                     }
 871                 }
 872             }
 873         };
 874         let supplied_params = substs.len();
 875         for _ in supplied_params..parent_param_count + param_count {
 876             substs.push(Ty::Unknown);
 877         }
 878         assert_eq!(substs.len(), parent_param_count + param_count);
 879         Substs(substs.into())
 880     }
 881
 882     fn register_obligations_for_call(&mut self, callable_ty: &Ty) {
 883         if let Ty::Apply(a_ty) = callable_ty {
 884             if let TypeCtor::FnDef(def) = a_ty.ctor {
 885                 let generic_predicates = self.db.generic_predicates(def.into());
 886                 for predicate in generic_predicates.iter() {
 887                     let predicate = predicate.clone().subst(&a_ty.parameters);
 888                     if let Some(obligation) = Obligation::from_predicate(predicate) {
 889                         self.obligations.push(obligation);
 890                     }
 891                 }
 892                 // add obligation for trait implementation, if this is a trait method
 893                 match def {
 894                     CallableDef::Function(f) => {
 895                         if let Some(trait_) = f.parent_trait(self.db) {
 896                             // construct a TraitDef
 897                             let substs = a_ty.parameters.prefix(
 898                                 trait_.generic_params(self.db).count_params_including_parent(),
 899                             );
 900                             self.obligations.push(Obligation::Trait(TraitRef { trait_, substs }));
 901                         }
 902                     }
 903                     CallableDef::Struct(_) | CallableDef::EnumVariant(_) => {}
 904                 }
 905             }
 906         }
 907     }
 908
 909     fn infer_method_call(
 910         &mut self,
 911         tgt_expr: ExprId,
 912         receiver: ExprId,
 913         args: &[ExprId],
 914         method_name: &Name,
 915         generic_args: Option<&GenericArgs>,
 916     ) -> Ty {
 917         let receiver_ty = self.infer_expr(receiver, &Expectation::none());
 918         let canonicalized_receiver = self.canonicalizer().canonicalize_ty(receiver_ty.clone());
 919         let resolved = method_resolution::lookup_method(
 920             &canonicalized_receiver.value,
 921             self.db,
 922             method_name,
 923             &self.resolver,
 924         );
 925         let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
 926             Some((ty, func)) => {
 927                 let ty = canonicalized_receiver.decanonicalize_ty(ty);
 928                 self.write_method_resolution(tgt_expr, func);
 929                 (
 930                     ty,
 931                     self.db.type_for_def(func.into(), Namespace::Values),
 932                     Some(func.generic_params(self.db)),
 933                 )
 934             }
 935             None => (receiver_ty, Ty::Unknown, None),
 936         };
 937         let substs = self.substs_for_method_call(def_generics, generic_args, &derefed_receiver_ty);
 938         let method_ty = method_ty.apply_substs(substs);
 939         let method_ty = self.insert_type_vars(method_ty);
 940         self.register_obligations_for_call(&method_ty);
 941         let (expected_receiver_ty, param_tys, ret_ty) = match method_ty.callable_sig(self.db) {
 942             Some(sig) => {
 943                 if !sig.params().is_empty() {
 944                     (sig.params()[0].clone(), sig.params()[1..].to_vec(), sig.ret().clone())
 945                 } else {
 946                     (Ty::Unknown, Vec::new(), sig.ret().clone())
 947                 }
 948             }
 949             None => (Ty::Unknown, Vec::new(), Ty::Unknown),
 950         };
 951         // Apply autoref so the below unification works correctly
 952         // FIXME: return correct autorefs from lookup_method
 953         let actual_receiver_ty = match expected_receiver_ty.as_reference() {
 954             Some((_, mutability)) => Ty::apply_one(TypeCtor::Ref(mutability), derefed_receiver_ty),
 955             _ => derefed_receiver_ty,
 956         };
 957         self.unify(&expected_receiver_ty, &actual_receiver_ty);
 958
 959         let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
 960         for (arg, param_ty) in args.iter().zip(param_iter) {
 961             let param_ty = self.normalize_associated_types_in(param_ty);
 962             self.infer_expr(*arg, &Expectation::has_type(param_ty));
 963         }
 964         let ret_ty = self.normalize_associated_types_in(ret_ty);
 965         ret_ty
 966     }
 967
 968     fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
 969         let body = Arc::clone(&self.body); // avoid borrow checker problem
 970         let ty = match &body[tgt_expr] {
 971             Expr::Missing => Ty::Unknown,
 972             Expr::If { condition, then_branch, else_branch } => {
 973                 // if let is desugared to match, so this is always simple if
 974                 self.infer_expr(*condition, &Expectation::has_type(Ty::simple(TypeCtor::Bool)));
 975                 let then_ty = self.infer_expr(*then_branch, expected);
 976                 match else_branch {
 977                     Some(else_branch) => {
 978                         self.infer_expr(*else_branch, expected);
 979                     }
 980                     None => {
 981                         // no else branch -> unit
 982                         self.unify(&then_ty, &Ty::unit()); // actually coerce
 983                     }
 984                 };
 985                 then_ty
 986             }
 987             Expr::Block { statements, tail } => self.infer_block(statements, *tail, expected),
 988             Expr::TryBlock { body } => {
 989                 let _inner = self.infer_expr(*body, expected);
 990                 // FIXME should be std::result::Result<{inner}, _>
 991                 Ty::Unknown
 992             }
 993             Expr::Loop { body } => {
 994                 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
 995                 // FIXME handle break with value
 996                 Ty::simple(TypeCtor::Never)
 997             }
 998             Expr::While { condition, body } => {
 999                 // while let is desugared to a match loop, so this is always simple while
1000                 self.infer_expr(*condition, &Expectation::has_type(Ty::simple(TypeCtor::Bool)));
1001                 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
1002                 Ty::unit()
1003             }
1004             Expr::For { iterable, body, pat } => {
1005                 let iterable_ty = self.infer_expr(*iterable, &Expectation::none());
1006
1007                 let pat_ty = match self.resolve_into_iter_item() {
1008                     Some(into_iter_item_alias) => {
1009                         let pat_ty = self.new_type_var();
1010                         let projection = ProjectionPredicate {
1011                             ty: pat_ty.clone(),
1012                             projection_ty: ProjectionTy {
1013                                 associated_ty: into_iter_item_alias,
1014                                 parameters: vec![iterable_ty].into(),
1015                             },
1016                         };
1017                         self.obligations.push(Obligation::Projection(projection));
1018                         self.resolve_ty_as_possible(&mut vec![], pat_ty)
1019                     }
1020                     None => Ty::Unknown,
1021                 };
1022
1023                 self.infer_pat(*pat, &pat_ty, BindingMode::default());
1024                 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
1025                 Ty::unit()
1026             }
1027             Expr::Lambda { body, args, arg_types } => {
1028                 assert_eq!(args.len(), arg_types.len());
1029
1030                 for (arg_pat, arg_type) in args.iter().zip(arg_types.iter()) {
1031                     let expected = if let Some(type_ref) = arg_type {
1032                         self.make_ty(type_ref)
1033                     } else {
1034                         Ty::Unknown
1035                     };
1036                     self.infer_pat(*arg_pat, &expected, BindingMode::default());
1037                 }
1038
1039                 // FIXME: infer lambda type etc.
1040                 let _body_ty = self.infer_expr(*body, &Expectation::none());
1041                 Ty::Unknown
1042             }
1043             Expr::Call { callee, args } => {
1044                 let callee_ty = self.infer_expr(*callee, &Expectation::none());
1045                 let (param_tys, ret_ty) = match callee_ty.callable_sig(self.db) {
1046                     Some(sig) => (sig.params().to_vec(), sig.ret().clone()),
1047                     None => {
1048                         // Not callable
1049                         // FIXME: report an error
1050                         (Vec::new(), Ty::Unknown)
1051                     }
1052                 };
1053                 self.register_obligations_for_call(&callee_ty);
1054                 let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
1055                 for (arg, param_ty) in args.iter().zip(param_iter) {
1056                     let param_ty = self.normalize_associated_types_in(param_ty);
1057                     self.infer_expr(*arg, &Expectation::has_type(param_ty));
1058                 }
1059                 let ret_ty = self.normalize_associated_types_in(ret_ty);
1060                 ret_ty
1061             }
1062             Expr::MethodCall { receiver, args, method_name, generic_args } => self
1063                 .infer_method_call(tgt_expr, *receiver, &args, &method_name, generic_args.as_ref()),
1064             Expr::Match { expr, arms } => {
1065                 let expected = if expected.ty == Ty::Unknown {
1066                     Expectation::has_type(self.new_type_var())
1067                 } else {
1068                     expected.clone()
1069                 };
1070                 let input_ty = self.infer_expr(*expr, &Expectation::none());
1071
1072                 for arm in arms {
1073                     for &pat in &arm.pats {
1074                         let _pat_ty = self.infer_pat(pat, &input_ty, BindingMode::default());
1075                     }
1076                     if let Some(guard_expr) = arm.guard {
1077                         self.infer_expr(
1078                             guard_expr,
1079                             &Expectation::has_type(Ty::simple(TypeCtor::Bool)),
1080                         );
1081                     }
1082                     self.infer_expr(arm.expr, &expected);
1083                 }
1084
1085                 expected.ty
1086             }
1087             Expr::Path(p) => {
1088                 // FIXME this could be more efficient...
1089                 let resolver = expr::resolver_for_expr(self.body.clone(), self.db, tgt_expr);
1090                 self.infer_path_expr(&resolver, p, tgt_expr.into()).unwrap_or(Ty::Unknown)
1091             }
1092             Expr::Continue => Ty::simple(TypeCtor::Never),
1093             Expr::Break { expr } => {
1094                 if let Some(expr) = expr {
1095                     // FIXME handle break with value
1096                     self.infer_expr(*expr, &Expectation::none());
1097                 }
1098                 Ty::simple(TypeCtor::Never)
1099             }
1100             Expr::Return { expr } => {
1101                 if let Some(expr) = expr {
1102                     self.infer_expr(*expr, &Expectation::has_type(self.return_ty.clone()));
1103                 }
1104                 Ty::simple(TypeCtor::Never)
1105             }
1106             Expr::StructLit { path, fields, spread } => {
1107                 let (ty, def_id) = self.resolve_variant(path.as_ref());
1108                 if let Some(variant) = def_id {
1109                     self.write_variant_resolution(tgt_expr.into(), variant);
1110                 }
1111
1112                 let substs = ty.substs().unwrap_or_else(Substs::empty);
1113                 for (field_idx, field) in fields.iter().enumerate() {
1114                     let field_ty = def_id
1115                         .and_then(|it| match it.field(self.db, &field.name) {
1116                             Some(field) => Some(field),
1117                             None => {
1118                                 self.push_diagnostic(InferenceDiagnostic::NoSuchField {
1119                                     expr: tgt_expr,
1120                                     field: field_idx,
1121                                 });
1122                                 None
1123                             }
1124                         })
1125                         .map_or(Ty::Unknown, |field| field.ty(self.db))
1126                         .subst(&substs);
1127                     self.infer_expr(field.expr, &Expectation::has_type(field_ty));
1128                 }
1129                 if let Some(expr) = spread {
1130                     self.infer_expr(*expr, &Expectation::has_type(ty.clone()));
1131                 }
1132                 ty
1133             }
1134             Expr::Field { expr, name } => {
1135                 let receiver_ty = self.infer_expr(*expr, &Expectation::none());
1136                 let canonicalized = self.canonicalizer().canonicalize_ty(receiver_ty);
1137                 let ty = autoderef::autoderef(
1138                     self.db,
1139                     &self.resolver.clone(),
1140                     canonicalized.value.clone(),
1141                 )
1142                 .find_map(|derefed_ty| match canonicalized.decanonicalize_ty(derefed_ty.value) {
1143                     Ty::Apply(a_ty) => match a_ty.ctor {
1144                         TypeCtor::Tuple { .. } => {
1145                             let i = name.to_string().parse::<usize>().ok();
1146                             i.and_then(|i| a_ty.parameters.0.get(i).cloned())
1147                         }
1148                         TypeCtor::Adt(AdtDef::Struct(s)) => s.field(self.db, name).map(|field| {
1149                             self.write_field_resolution(tgt_expr, field);
1150                             field.ty(self.db).subst(&a_ty.parameters)
1151                         }),
1152                         _ => None,
1153                     },
1154                     _ => None,
1155                 })
1156                 .unwrap_or(Ty::Unknown);
1157                 let ty = self.insert_type_vars(ty);
1158                 self.normalize_associated_types_in(ty)
1159             }
1160             Expr::Await { expr } => {
1161                 let inner_ty = self.infer_expr(*expr, &Expectation::none());
1162                 let ty = match self.resolve_future_future_output() {
1163                     Some(future_future_output_alias) => {
1164                         let ty = self.new_type_var();
1165                         let projection = ProjectionPredicate {
1166                             ty: ty.clone(),
1167                             projection_ty: ProjectionTy {
1168                                 associated_ty: future_future_output_alias,
1169                                 parameters: vec![inner_ty].into(),
1170                             },
1171                         };
1172                         self.obligations.push(Obligation::Projection(projection));
1173                         self.resolve_ty_as_possible(&mut vec![], ty)
1174                     }
1175                     None => Ty::Unknown,
1176                 };
1177                 ty
1178             }
1179             Expr::Try { expr } => {
1180                 let inner_ty = self.infer_expr(*expr, &Expectation::none());
1181                 let ty = match self.resolve_ops_try_ok() {
1182                     Some(ops_try_ok_alias) => {
1183                         let ty = self.new_type_var();
1184                         let projection = ProjectionPredicate {
1185                             ty: ty.clone(),
1186                             projection_ty: ProjectionTy {
1187                                 associated_ty: ops_try_ok_alias,
1188                                 parameters: vec![inner_ty].into(),
1189                             },
1190                         };
1191                         self.obligations.push(Obligation::Projection(projection));
1192                         self.resolve_ty_as_possible(&mut vec![], ty)
1193                     }
1194                     None => Ty::Unknown,
1195                 };
1196                 ty
1197             }
1198             Expr::Cast { expr, type_ref } => {
1199                 let _inner_ty = self.infer_expr(*expr, &Expectation::none());
1200                 let cast_ty = self.make_ty(type_ref);
1201                 // FIXME check the cast...
1202                 cast_ty
1203             }
1204             Expr::Ref { expr, mutability } => {
1205                 let expectation =
1206                     if let Some((exp_inner, exp_mutability)) = &expected.ty.as_reference() {
1207                         if *exp_mutability == Mutability::Mut && *mutability == Mutability::Shared {
1208                             // FIXME: throw type error - expected mut reference but found shared ref,
1209                             // which cannot be coerced
1210                         }
1211                         Expectation::has_type(Ty::clone(exp_inner))
1212                     } else {
1213                         Expectation::none()
1214                     };
1215                 // FIXME reference coercions etc.
1216                 let inner_ty = self.infer_expr(*expr, &expectation);
1217                 Ty::apply_one(TypeCtor::Ref(*mutability), inner_ty)
1218             }
1219             Expr::UnaryOp { expr, op } => {
1220                 let inner_ty = self.infer_expr(*expr, &Expectation::none());
1221                 match op {
1222                     UnaryOp::Deref => {
1223                         let canonicalized = self.canonicalizer().canonicalize_ty(inner_ty);
1224                         if let Some(derefed_ty) =
1225                             autoderef::deref(self.db, &self.resolver, &canonicalized.value)
1226                         {
1227                             canonicalized.decanonicalize_ty(derefed_ty.value)
1228                         } else {
1229                             Ty::Unknown
1230                         }
1231                     }
1232                     UnaryOp::Neg => {
1233                         match &inner_ty {
1234                             Ty::Apply(a_ty) => match a_ty.ctor {
1235                                 TypeCtor::Int(primitive::UncertainIntTy::Unknown)
1236                                 | TypeCtor::Int(primitive::UncertainIntTy::Known(
1237                                     primitive::IntTy {
1238                                         signedness: primitive::Signedness::Signed,
1239                                         ..
1240                                     },
1241                                 ))
1242                                 | TypeCtor::Float(..) => inner_ty,
1243                                 _ => Ty::Unknown,
1244                             },
1245                             Ty::Infer(InferTy::IntVar(..)) | Ty::Infer(InferTy::FloatVar(..)) => {
1246                                 inner_ty
1247                             }
1248                             // FIXME: resolve ops::Neg trait
1249                             _ => Ty::Unknown,
1250                         }
1251                     }
1252                     UnaryOp::Not => {
1253                         match &inner_ty {
1254                             Ty::Apply(a_ty) => match a_ty.ctor {
1255                                 TypeCtor::Bool | TypeCtor::Int(_) => inner_ty,
1256                                 _ => Ty::Unknown,
1257                             },
1258                             Ty::Infer(InferTy::IntVar(..)) => inner_ty,
1259                             // FIXME: resolve ops::Not trait for inner_ty
1260                             _ => Ty::Unknown,
1261                         }
1262                     }
1263                 }
1264             }
1265             Expr::BinaryOp { lhs, rhs, op } => match op {
1266                 Some(op) => {
1267                     let lhs_expectation = match op {
1268                         BinaryOp::BooleanAnd | BinaryOp::BooleanOr => {
1269                             Expectation::has_type(Ty::simple(TypeCtor::Bool))
1270                         }
1271                         _ => Expectation::none(),
1272                     };
1273                     let lhs_ty = self.infer_expr(*lhs, &lhs_expectation);
1274                     // FIXME: find implementation of trait corresponding to operation
1275                     // symbol and resolve associated `Output` type
1276                     let rhs_expectation = op::binary_op_rhs_expectation(*op, lhs_ty);
1277                     let rhs_ty = self.infer_expr(*rhs, &Expectation::has_type(rhs_expectation));
1278
1279                     // FIXME: similar as above, return ty is often associated trait type
1280                     op::binary_op_return_ty(*op, rhs_ty)
1281                 }
1282                 _ => Ty::Unknown,
1283             },
1284             Expr::Tuple { exprs } => {
1285                 let mut ty_vec = Vec::with_capacity(exprs.len());
1286                 for arg in exprs.iter() {
1287                     ty_vec.push(self.infer_expr(*arg, &Expectation::none()));
1288                 }
1289
1290                 Ty::apply(
1291                     TypeCtor::Tuple { cardinality: ty_vec.len() as u16 },
1292                     Substs(ty_vec.into()),
1293                 )
1294             }
1295             Expr::Array(array) => {
1296                 let elem_ty = match &expected.ty {
1297                     Ty::Apply(a_ty) => match a_ty.ctor {
1298                         TypeCtor::Slice | TypeCtor::Array => {
1299                             Ty::clone(&a_ty.parameters.as_single())
1300                         }
1301                         _ => self.new_type_var(),
1302                     },
1303                     _ => self.new_type_var(),
1304                 };
1305
1306                 match array {
1307                     Array::ElementList(items) => {
1308                         for expr in items.iter() {
1309                             self.infer_expr(*expr, &Expectation::has_type(elem_ty.clone()));
1310                         }
1311                     }
1312                     Array::Repeat { initializer, repeat } => {
1313                         self.infer_expr(*initializer, &Expectation::has_type(elem_ty.clone()));
1314                         self.infer_expr(
1315                             *repeat,
1316                             &Expectation::has_type(Ty::simple(TypeCtor::Int(
1317                                 primitive::UncertainIntTy::Known(primitive::IntTy::usize()),
1318                             ))),
1319                         );
1320                     }
1321                 }
1322
1323                 Ty::apply_one(TypeCtor::Array, elem_ty)
1324             }
1325             Expr::Literal(lit) => match lit {
1326                 Literal::Bool(..) => Ty::simple(TypeCtor::Bool),
1327                 Literal::String(..) => {
1328                     Ty::apply_one(TypeCtor::Ref(Mutability::Shared), Ty::simple(TypeCtor::Str))
1329                 }
1330                 Literal::ByteString(..) => {
1331                     let byte_type = Ty::simple(TypeCtor::Int(primitive::UncertainIntTy::Known(
1332                         primitive::IntTy::u8(),
1333                     )));
1334                     let slice_type = Ty::apply_one(TypeCtor::Slice, byte_type);
1335                     Ty::apply_one(TypeCtor::Ref(Mutability::Shared), slice_type)
1336                 }
1337                 Literal::Char(..) => Ty::simple(TypeCtor::Char),
1338                 Literal::Int(_v, ty) => Ty::simple(TypeCtor::Int(*ty)),
1339                 Literal::Float(_v, ty) => Ty::simple(TypeCtor::Float(*ty)),
1340             },
1341         };
1342         // use a new type variable if we got Ty::Unknown here
1343         let ty = self.insert_type_vars_shallow(ty);
1344         self.unify(&ty, &expected.ty);
1345         let ty = self.resolve_ty_as_possible(&mut vec![], ty);
1346         self.write_expr_ty(tgt_expr, ty.clone());
1347         ty
1348     }
1349
1350     fn infer_block(
1351         &mut self,
1352         statements: &[Statement],
1353         tail: Option<ExprId>,
1354         expected: &Expectation,
1355     ) -> Ty {
1356         for stmt in statements {
1357             match stmt {
1358                 Statement::Let { pat, type_ref, initializer } => {
1359                     let decl_ty =
1360                         type_ref.as_ref().map(|tr| self.make_ty(tr)).unwrap_or(Ty::Unknown);
1361                     let decl_ty = self.insert_type_vars(decl_ty);
1362                     let ty = if let Some(expr) = initializer {
1363                         let expr_ty = self.infer_expr(*expr, &Expectation::has_type(decl_ty));
1364                         expr_ty
1365                     } else {
1366                         decl_ty
1367                     };
1368
1369                     self.infer_pat(*pat, &ty, BindingMode::default());
1370                 }
1371                 Statement::Expr(expr) => {
1372                     self.infer_expr(*expr, &Expectation::none());
1373                 }
1374             }
1375         }
1376         let ty = if let Some(expr) = tail { self.infer_expr(expr, expected) } else { Ty::unit() };
1377         ty
1378     }
1379
1380     fn collect_const(&mut self, data: &ConstData) {
1381         self.return_ty = self.make_ty(data.type_ref());
1382     }
1383
1384     fn collect_fn(&mut self, data: &FnData) {
1385         let body = Arc::clone(&self.body); // avoid borrow checker problem
1386         for (type_ref, pat) in data.params().iter().zip(body.params()) {
1387             let ty = self.make_ty(type_ref);
1388
1389             self.infer_pat(*pat, &ty, BindingMode::default());
1390         }
1391         self.return_ty = self.make_ty(data.ret_type());
1392     }
1393
1394     fn infer_body(&mut self) {
1395         self.infer_expr(self.body.body_expr(), &Expectation::has_type(self.return_ty.clone()));
1396     }
1397
1398     fn resolve_into_iter_item(&self) -> Option<TypeAlias> {
1399         let into_iter_path = Path {
1400             kind: PathKind::Abs,
1401             segments: vec![
1402                 PathSegment { name: name::STD, args_and_bindings: None },
1403                 PathSegment { name: name::ITER, args_and_bindings: None },
1404                 PathSegment { name: name::INTO_ITERATOR, args_and_bindings: None },
1405             ],
1406         };
1407
1408         match self.resolver.resolve_path_segments(self.db, &into_iter_path).into_fully_resolved() {
1409             PerNs { types: Some(Def(Trait(trait_))), .. } => {
1410                 Some(trait_.associated_type_by_name(self.db, name::ITEM)?)
1411             }
1412             _ => None,
1413         }
1414     }
1415
1416     fn resolve_ops_try_ok(&self) -> Option<TypeAlias> {
1417         let ops_try_path = Path {
1418             kind: PathKind::Abs,
1419             segments: vec![
1420                 PathSegment { name: name::STD, args_and_bindings: None },
1421                 PathSegment { name: name::OPS, args_and_bindings: None },
1422                 PathSegment { name: name::TRY, args_and_bindings: None },
1423             ],
1424         };
1425
1426         match self.resolver.resolve_path_segments(self.db, &ops_try_path).into_fully_resolved() {
1427             PerNs { types: Some(Def(Trait(trait_))), .. } => {
1428                 Some(trait_.associated_type_by_name(self.db, name::OK)?)
1429             }
1430             _ => None,
1431         }
1432     }
1433
1434     fn resolve_future_future_output(&self) -> Option<TypeAlias> {
1435         let future_future_path = Path {
1436             kind: PathKind::Abs,
1437             segments: vec![
1438                 PathSegment { name: name::STD, args_and_bindings: None },
1439                 PathSegment { name: name::FUTURE_MOD, args_and_bindings: None },
1440                 PathSegment { name: name::FUTURE_TYPE, args_and_bindings: None },
1441             ],
1442         };
1443
1444         match self
1445             .resolver
1446             .resolve_path_segments(self.db, &future_future_path)
1447             .into_fully_resolved()
1448         {
1449             PerNs { types: Some(Def(Trait(trait_))), .. } => {
1450                 Some(trait_.associated_type_by_name(self.db, name::OUTPUT)?)
1451             }
1452             _ => None,
1453         }
1454     }
1455 }
1456
1457 /// The ID of a type variable.
1458 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
1459 pub struct TypeVarId(pub(super) u32);
1460
1461 impl UnifyKey for TypeVarId {
1462     type Value = TypeVarValue;
1463
1464     fn index(&self) -> u32 {
1465         self.0
1466     }
1467
1468     fn from_index(i: u32) -> Self {
1469         TypeVarId(i)
1470     }
1471
1472     fn tag() -> &'static str {
1473         "TypeVarId"
1474     }
1475 }
1476
1477 /// The value of a type variable: either we already know the type, or we don't
1478 /// know it yet.
1479 #[derive(Clone, PartialEq, Eq, Debug)]
1480 pub enum TypeVarValue {
1481     Known(Ty),
1482     Unknown,
1483 }
1484
1485 impl TypeVarValue {
1486     fn known(&self) -> Option<&Ty> {
1487         match self {
1488             TypeVarValue::Known(ty) => Some(ty),
1489             TypeVarValue::Unknown => None,
1490         }
1491     }
1492 }
1493
1494 impl UnifyValue for TypeVarValue {
1495     type Error = NoError;
1496
1497     fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
1498         match (value1, value2) {
1499             // We should never equate two type variables, both of which have
1500             // known types. Instead, we recursively equate those types.
1501             (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!(
1502                 "equating two type variables, both of which have known types: {:?} and {:?}",
1503                 t1, t2
1504             ),
1505
1506             // If one side is known, prefer that one.
1507             (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()),
1508             (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()),
1509
1510             (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown),
1511         }
1512     }
1513 }
1514
1515 /// The kinds of placeholders we need during type inference. There's separate
1516 /// values for general types, and for integer and float variables. The latter
1517 /// two are used for inference of literal values (e.g. `100` could be one of
1518 /// several integer types).
1519 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
1520 pub enum InferTy {
1521     TypeVar(TypeVarId),
1522     IntVar(TypeVarId),
1523     FloatVar(TypeVarId),
1524 }
1525
1526 impl InferTy {
1527     fn to_inner(self) -> TypeVarId {
1528         match self {
1529             InferTy::TypeVar(ty) | InferTy::IntVar(ty) | InferTy::FloatVar(ty) => ty,
1530         }
1531     }
1532
1533     fn fallback_value(self) -> Ty {
1534         match self {
1535             InferTy::TypeVar(..) => Ty::Unknown,
1536             InferTy::IntVar(..) => {
1537                 Ty::simple(TypeCtor::Int(primitive::UncertainIntTy::Known(primitive::IntTy::i32())))
1538             }
1539             InferTy::FloatVar(..) => Ty::simple(TypeCtor::Float(
1540                 primitive::UncertainFloatTy::Known(primitive::FloatTy::f64()),
1541             )),
1542         }
1543     }
1544 }
1545
1546 /// When inferring an expression, we propagate downward whatever type hint we
1547 /// are able in the form of an `Expectation`.
1548 #[derive(Clone, PartialEq, Eq, Debug)]
1549 struct Expectation {
1550     ty: Ty,
1551     // FIXME: In some cases, we need to be aware whether the expectation is that
1552     // the type match exactly what we passed, or whether it just needs to be
1553     // coercible to the expected type. See Expectation::rvalue_hint in rustc.
1554 }
1555
1556 impl Expectation {
1557     /// The expectation that the type of the expression needs to equal the given
1558     /// type.
1559     fn has_type(ty: Ty) -> Self {
1560         Expectation { ty }
1561     }
1562
1563     /// This expresses no expectation on the type.
1564     fn none() -> Self {
1565         Expectation { ty: Ty::Unknown }
1566     }
1567 }
1568
1569 mod diagnostics {
1570     use crate::{
1571         diagnostics::{DiagnosticSink, NoSuchField},
1572         expr::ExprId,
1573         Function, HasSource, HirDatabase,
1574     };
1575
1576     #[derive(Debug, PartialEq, Eq, Clone)]
1577     pub(super) enum InferenceDiagnostic {
1578         NoSuchField { expr: ExprId, field: usize },
1579     }
1580
1581     impl InferenceDiagnostic {
1582         pub(super) fn add_to(
1583             &self,
1584             db: &impl HirDatabase,
1585             owner: Function,
1586             sink: &mut DiagnosticSink,
1587         ) {
1588             match self {
1589                 InferenceDiagnostic::NoSuchField { expr, field } => {
1590                     let file = owner.source(db).file_id;
1591                     let field = owner.body_source_map(db).field_syntax(*expr, *field);
1592                     sink.push(NoSuchField { file, field })
1593                 }
1594             }
1595         }
1596     }
1597 }