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