src/librustc_mir/borrow_check/nll/type_check/mod.rs

   1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! This pass type-checks the MIR to ensure it is not broken.
  12 #![allow(unreachable_code)]
  13
  14 use borrow_check::nll::region_infer::Cause;
  15 use borrow_check::nll::region_infer::ClosureRegionRequirementsExt;
  16 use borrow_check::nll::universal_regions::UniversalRegions;
  17 use dataflow::move_paths::MoveData;
  18 use dataflow::FlowAtLocation;
  19 use dataflow::MaybeInitializedPlaces;
  20 use rustc::hir::def_id::DefId;
  21 use rustc::infer::region_constraints::{GenericKind, RegionConstraintData};
  22 use rustc::infer::{InferCtxt, InferOk, InferResult, LateBoundRegionConversionTime, UnitResult};
  23 use rustc::mir::tcx::PlaceTy;
  24 use rustc::mir::visit::{PlaceContext, Visitor};
  25 use rustc::mir::interpret::EvalErrorKind::BoundsCheck;
  26 use rustc::mir::*;
  27 use rustc::traits::query::NoSolution;
  28 use rustc::traits::{self, Normalized, TraitEngine};
  29 use rustc::ty::error::TypeError;
  30 use rustc::ty::fold::TypeFoldable;
  31 use rustc::ty::{self, ToPolyTraitRef, Ty, TyCtxt, TypeVariants};
  32 use std::fmt;
  33 use syntax::ast;
  34 use syntax_pos::{Span, DUMMY_SP};
  35 use transform::{MirPass, MirSource};
  36 use util::liveness::LivenessResults;
  37
  38 use rustc_data_structures::fx::FxHashSet;
  39 use rustc_data_structures::indexed_vec::Idx;
  40
  41 macro_rules! span_mirbug {
  42     ($context:expr, $elem:expr, $($message:tt)*) => ({
  43         $crate::borrow_check::nll::type_check::mirbug(
  44             $context.tcx(),
  45             $context.last_span,
  46             &format!(
  47                 "broken MIR in {:?} ({:?}): {}",
  48                 $context.body_id,
  49                 $elem,
  50                 format_args!($($message)*),
  51             ),
  52         )
  53     })
  54 }
  55
  56 macro_rules! span_mirbug_and_err {
  57     ($context:expr, $elem:expr, $($message:tt)*) => ({
  58         {
  59             span_mirbug!($context, $elem, $($message)*);
  60             $context.error()
  61         }
  62     })
  63 }
  64
  65 mod input_output;
  66 mod liveness;
  67
  68 /// Type checks the given `mir` in the context of the inference
  69 /// context `infcx`. Returns any region constraints that have yet to
  70 /// be proven. This result is includes liveness constraints that
  71 /// ensure that regions appearing in the types of all local variables
  72 /// are live at all points where that local variable may later be
  73 /// used.
  74 ///
  75 /// This phase of type-check ought to be infallible -- this is because
  76 /// the original, HIR-based type-check succeeded. So if any errors
  77 /// occur here, we will get a `bug!` reported.
  78 ///
  79 /// # Parameters
  80 ///
  81 /// - `infcx` -- inference context to use
  82 /// - `param_env` -- parameter environment to use for trait solving
  83 /// - `mir` -- MIR to type-check
  84 /// - `mir_def_id` -- DefId from which the MIR is derived (must be local)
  85 /// - `region_bound_pairs` -- the implied outlives obligations between type parameters
  86 ///   and lifetimes (e.g., `&'a T` implies `T: 'a`)
  87 /// - `implicit_region_bound` -- a region which all generic parameters are assumed
  88 ///   to outlive; should represent the fn body
  89 /// - `input_tys` -- fully liberated, but **not** normalized, expected types of the arguments;
  90 ///   the types of the input parameters found in the MIR itself will be equated with these
  91 /// - `output_ty` -- fully liberaetd, but **not** normalized, expected return type;
  92 ///   the type for the RETURN_PLACE will be equated with this
  93 /// - `liveness` -- results of a liveness computation on the MIR; used to create liveness
  94 ///   constraints for the regions in the types of variables
  95 /// - `flow_inits` -- results of a maybe-init dataflow analysis
  96 /// - `move_data` -- move-data constructed when performing the maybe-init dataflow analysis
  97 pub(crate) fn type_check<'gcx, 'tcx>(
  98     infcx: &InferCtxt<'_, 'gcx, 'tcx>,
  99     param_env: ty::ParamEnv<'gcx>,
 100     mir: &Mir<'tcx>,
 101     mir_def_id: DefId,
 102     universal_regions: &UniversalRegions<'tcx>,
 103     liveness: &LivenessResults,
 104     flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>,
 105     move_data: &MoveData<'tcx>,
 106 ) -> MirTypeckRegionConstraints<'tcx> {
 107     let body_id = infcx.tcx.hir.as_local_node_id(mir_def_id).unwrap();
 108     let implicit_region_bound = infcx.tcx.mk_region(ty::ReVar(universal_regions.fr_fn_body));
 109     type_check_internal(
 110         infcx,
 111         body_id,
 112         param_env,
 113         mir,
 114         &universal_regions.region_bound_pairs,
 115         Some(implicit_region_bound),
 116         &mut |cx| {
 117             liveness::generate(cx, mir, liveness, flow_inits, move_data);
 118
 119             cx.equate_inputs_and_outputs(mir, mir_def_id, universal_regions);
 120         },
 121     )
 122 }
 123
 124 fn type_check_internal<'gcx, 'tcx>(
 125     infcx: &InferCtxt<'_, 'gcx, 'tcx>,
 126     body_id: ast::NodeId,
 127     param_env: ty::ParamEnv<'gcx>,
 128     mir: &Mir<'tcx>,
 129     region_bound_pairs: &[(ty::Region<'tcx>, GenericKind<'tcx>)],
 130     implicit_region_bound: Option<ty::Region<'tcx>>,
 131     extra: &mut dyn FnMut(&mut TypeChecker<'_, 'gcx, 'tcx>),
 132 ) -> MirTypeckRegionConstraints<'tcx> {
 133     let mut checker = TypeChecker::new(
 134         infcx,
 135         body_id,
 136         param_env,
 137         region_bound_pairs,
 138         implicit_region_bound,
 139     );
 140     let errors_reported = {
 141         let mut verifier = TypeVerifier::new(&mut checker, mir);
 142         verifier.visit_mir(mir);
 143         verifier.errors_reported
 144     };
 145
 146     if !errors_reported {
 147         // if verifier failed, don't do further checks to avoid ICEs
 148         checker.typeck_mir(mir);
 149     }
 150
 151     extra(&mut checker);
 152
 153     checker.constraints
 154 }
 155
 156 fn mirbug(tcx: TyCtxt, span: Span, msg: &str) {
 157     // We sometimes see MIR failures (notably predicate failures) due to
 158     // the fact that we check rvalue sized predicates here. So use `delay_span_bug`
 159     // to avoid reporting bugs in those cases.
 160     tcx.sess.diagnostic().delay_span_bug(span, msg);
 161 }
 162
 163 enum FieldAccessError {
 164     OutOfRange { field_count: usize },
 165 }
 166
 167 /// Verifies that MIR types are sane to not crash further checks.
 168 ///
 169 /// The sanitize_XYZ methods here take an MIR object and compute its
 170 /// type, calling `span_mirbug` and returning an error type if there
 171 /// is a problem.
 172 struct TypeVerifier<'a, 'b: 'a, 'gcx: 'b + 'tcx, 'tcx: 'b> {
 173     cx: &'a mut TypeChecker<'b, 'gcx, 'tcx>,
 174     mir: &'a Mir<'tcx>,
 175     last_span: Span,
 176     body_id: ast::NodeId,
 177     errors_reported: bool,
 178 }
 179
 180 impl<'a, 'b, 'gcx, 'tcx> Visitor<'tcx> for TypeVerifier<'a, 'b, 'gcx, 'tcx> {
 181     fn visit_span(&mut self, span: &Span) {
 182         if *span != DUMMY_SP {
 183             self.last_span = *span;
 184         }
 185     }
 186
 187     fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, location: Location) {
 188         self.sanitize_place(place, location, context);
 189     }
 190
 191     fn visit_constant(&mut self, constant: &Constant<'tcx>, location: Location) {
 192         self.super_constant(constant, location);
 193         self.sanitize_constant(constant, location);
 194         self.sanitize_type(constant, constant.ty);
 195     }
 196
 197     fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) {
 198         self.super_rvalue(rvalue, location);
 199         let rval_ty = rvalue.ty(self.mir, self.tcx());
 200         self.sanitize_type(rvalue, rval_ty);
 201     }
 202
 203     fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
 204         self.super_local_decl(local, local_decl);
 205         self.sanitize_type(local_decl, local_decl.ty);
 206     }
 207
 208     fn visit_mir(&mut self, mir: &Mir<'tcx>) {
 209         self.sanitize_type(&"return type", mir.return_ty());
 210         for local_decl in &mir.local_decls {
 211             self.sanitize_type(local_decl, local_decl.ty);
 212         }
 213         if self.errors_reported {
 214             return;
 215         }
 216         self.super_mir(mir);
 217     }
 218 }
 219
 220 impl<'a, 'b, 'gcx, 'tcx> TypeVerifier<'a, 'b, 'gcx, 'tcx> {
 221     fn new(cx: &'a mut TypeChecker<'b, 'gcx, 'tcx>, mir: &'a Mir<'tcx>) -> Self {
 222         TypeVerifier {
 223             mir,
 224             body_id: cx.body_id,
 225             cx,
 226             last_span: mir.span,
 227             errors_reported: false,
 228         }
 229     }
 230
 231     fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
 232         self.cx.infcx.tcx
 233     }
 234
 235     fn sanitize_type(&mut self, parent: &dyn fmt::Debug, ty: Ty<'tcx>) -> Ty<'tcx> {
 236         if ty.has_escaping_regions() || ty.references_error() {
 237             span_mirbug_and_err!(self, parent, "bad type {:?}", ty)
 238         } else {
 239             ty
 240         }
 241     }
 242
 243     /// Checks that the constant's `ty` field matches up with what
 244     /// would be expected from its literal.
 245     fn sanitize_constant(&mut self, constant: &Constant<'tcx>, location: Location) {
 246         debug!(
 247             "sanitize_constant(constant={:?}, location={:?})",
 248             constant, location
 249         );
 250
 251         let expected_ty = match constant.literal {
 252             Literal::Value { value } => {
 253                 // FIXME(#46702) -- We need some way to get the predicates
 254                 // associated with the "pre-evaluated" form of the
 255                 // constant. For example, consider that the constant
 256                 // may have associated constant projections (`<Foo as
 257                 // Trait<'a, 'b>>::SOME_CONST`) that impose
 258                 // constraints on `'a` and `'b`. These constraints
 259                 // would be lost if we just look at the normalized
 260                 // value.
 261                 if let ty::TyFnDef(def_id, substs) = value.ty.sty {
 262                     let tcx = self.tcx();
 263                     let type_checker = &mut self.cx;
 264
 265                     // FIXME -- For now, use the substitutions from
 266                     // `value.ty` rather than `value.val`. The
 267                     // renumberer will rewrite them to independent
 268                     // sets of regions; in principle, we ought to
 269                     // derive the type of the `value.val` from "first
 270                     // principles" and equate with value.ty, but as we
 271                     // are transitioning to the miri-based system, we
 272                     // don't have a handy function for that, so for
 273                     // now we just ignore `value.val` regions.
 274
 275                     let instantiated_predicates =
 276                         tcx.predicates_of(def_id).instantiate(tcx, substs);
 277                     let predicates =
 278                         type_checker.normalize(&instantiated_predicates.predicates, location);
 279                     type_checker.prove_predicates(predicates, location);
 280                 }
 281
 282                 value.ty
 283             }
 284
 285             Literal::Promoted { .. } => {
 286                 // FIXME -- promoted MIR return types reference
 287                 // various "free regions" (e.g., scopes and things)
 288                 // that they ought not to do. We have to figure out
 289                 // how best to handle that -- probably we want treat
 290                 // promoted MIR much like closures, renumbering all
 291                 // their free regions and propagating constraints
 292                 // upwards. We have the same acyclic guarantees, so
 293                 // that should be possible. But for now, ignore them.
 294                 //
 295                 // let promoted_mir = &self.mir.promoted[index];
 296                 // promoted_mir.return_ty()
 297                 return;
 298             }
 299         };
 300
 301         debug!("sanitize_constant: expected_ty={:?}", expected_ty);
 302
 303         if let Err(terr) = self.cx
 304             .eq_types(expected_ty, constant.ty, location.at_self())
 305         {
 306             span_mirbug!(
 307                 self,
 308                 constant,
 309                 "constant {:?} should have type {:?} but has {:?} ({:?})",
 310                 constant,
 311                 expected_ty,
 312                 constant.ty,
 313                 terr,
 314             );
 315         }
 316     }
 317
 318     /// Checks that the types internal to the `place` match up with
 319     /// what would be expected.
 320     fn sanitize_place(
 321         &mut self,
 322         place: &Place<'tcx>,
 323         location: Location,
 324         context: PlaceContext,
 325     ) -> PlaceTy<'tcx> {
 326         debug!("sanitize_place: {:?}", place);
 327         let place_ty = match *place {
 328             Place::Local(index) => PlaceTy::Ty {
 329                 ty: self.mir.local_decls[index].ty,
 330             },
 331             Place::Static(box Static { def_id, ty: sty }) => {
 332                 let sty = self.sanitize_type(place, sty);
 333                 let ty = self.tcx().type_of(def_id);
 334                 let ty = self.cx.normalize(&ty, location);
 335                 if let Err(terr) = self.cx.eq_types(ty, sty, location.at_self()) {
 336                     span_mirbug!(
 337                         self,
 338                         place,
 339                         "bad static type ({:?}: {:?}): {:?}",
 340                         ty,
 341                         sty,
 342                         terr
 343                     );
 344                 }
 345                 PlaceTy::Ty { ty: sty }
 346             }
 347             Place::Projection(ref proj) => {
 348                 let base_context = if context.is_mutating_use() {
 349                     PlaceContext::Projection(Mutability::Mut)
 350                 } else {
 351                     PlaceContext::Projection(Mutability::Not)
 352                 };
 353                 let base_ty = self.sanitize_place(&proj.base, location, base_context);
 354                 if let PlaceTy::Ty { ty } = base_ty {
 355                     if ty.references_error() {
 356                         assert!(self.errors_reported);
 357                         return PlaceTy::Ty {
 358                             ty: self.tcx().types.err,
 359                         };
 360                     }
 361                 }
 362                 self.sanitize_projection(base_ty, &proj.elem, place, location)
 363             }
 364         };
 365         if let PlaceContext::Copy = context {
 366             let tcx = self.tcx();
 367             let trait_ref = ty::TraitRef {
 368                 def_id: tcx.lang_items().copy_trait().unwrap(),
 369                 substs: tcx.mk_substs_trait(place_ty.to_ty(tcx), &[]),
 370             };
 371
 372             // In order to have a Copy operand, the type T of the value must be Copy. Note that we
 373             // prove that T: Copy, rather than using the type_moves_by_default test. This is
 374             // important because type_moves_by_default ignores the resulting region obligations and
 375             // assumes they pass. This can result in bounds from Copy impls being unsoundly ignored
 376             // (e.g., #29149). Note that we decide to use Copy before knowing whether the bounds
 377             // fully apply: in effect, the rule is that if a value of some type could implement
 378             // Copy, then it must.
 379             self.cx.prove_trait_ref(trait_ref, location);
 380         }
 381         place_ty
 382     }
 383
 384     fn sanitize_projection(
 385         &mut self,
 386         base: PlaceTy<'tcx>,
 387         pi: &PlaceElem<'tcx>,
 388         place: &Place<'tcx>,
 389         location: Location,
 390     ) -> PlaceTy<'tcx> {
 391         debug!("sanitize_projection: {:?} {:?} {:?}", base, pi, place);
 392         let tcx = self.tcx();
 393         let base_ty = base.to_ty(tcx);
 394         match *pi {
 395             ProjectionElem::Deref => {
 396                 let deref_ty = base_ty.builtin_deref(true);
 397                 PlaceTy::Ty {
 398                     ty: deref_ty.map(|t| t.ty).unwrap_or_else(|| {
 399                         span_mirbug_and_err!(self, place, "deref of non-pointer {:?}", base_ty)
 400                     }),
 401                 }
 402             }
 403             ProjectionElem::Index(i) => {
 404                 let index_ty = Place::Local(i).ty(self.mir, tcx).to_ty(tcx);
 405                 if index_ty != tcx.types.usize {
 406                     PlaceTy::Ty {
 407                         ty: span_mirbug_and_err!(self, i, "index by non-usize {:?}", i),
 408                     }
 409                 } else {
 410                     PlaceTy::Ty {
 411                         ty: base_ty.builtin_index().unwrap_or_else(|| {
 412                             span_mirbug_and_err!(self, place, "index of non-array {:?}", base_ty)
 413                         }),
 414                     }
 415                 }
 416             }
 417             ProjectionElem::ConstantIndex { .. } => {
 418                 // consider verifying in-bounds
 419                 PlaceTy::Ty {
 420                     ty: base_ty.builtin_index().unwrap_or_else(|| {
 421                         span_mirbug_and_err!(self, place, "index of non-array {:?}", base_ty)
 422                     }),
 423                 }
 424             }
 425             ProjectionElem::Subslice { from, to } => PlaceTy::Ty {
 426                 ty: match base_ty.sty {
 427                     ty::TyArray(inner, size) => {
 428                         let size = size.val.unwrap_u64();
 429                         let min_size = (from as u64) + (to as u64);
 430                         if let Some(rest_size) = size.checked_sub(min_size) {
 431                             tcx.mk_array(inner, rest_size)
 432                         } else {
 433                             span_mirbug_and_err!(
 434                                 self,
 435                                 place,
 436                                 "taking too-small slice of {:?}",
 437                                 base_ty
 438                             )
 439                         }
 440                     }
 441                     ty::TySlice(..) => base_ty,
 442                     _ => span_mirbug_and_err!(self, place, "slice of non-array {:?}", base_ty),
 443                 },
 444             },
 445             ProjectionElem::Downcast(adt_def1, index) => match base_ty.sty {
 446                 ty::TyAdt(adt_def, substs) if adt_def.is_enum() && adt_def == adt_def1 => {
 447                     if index >= adt_def.variants.len() {
 448                         PlaceTy::Ty {
 449                             ty: span_mirbug_and_err!(
 450                                 self,
 451                                 place,
 452                                 "cast to variant #{:?} but enum only has {:?}",
 453                                 index,
 454                                 adt_def.variants.len()
 455                             ),
 456                         }
 457                     } else {
 458                         PlaceTy::Downcast {
 459                             adt_def,
 460                             substs,
 461                             variant_index: index,
 462                         }
 463                     }
 464                 }
 465                 _ => PlaceTy::Ty {
 466                     ty: span_mirbug_and_err!(
 467                         self,
 468                         place,
 469                         "can't downcast {:?} as {:?}",
 470                         base_ty,
 471                         adt_def1
 472                     ),
 473                 },
 474             },
 475             ProjectionElem::Field(field, fty) => {
 476                 let fty = self.sanitize_type(place, fty);
 477                 match self.field_ty(place, base, field, location) {
 478                     Ok(ty) => if let Err(terr) = self.cx.eq_types(ty, fty, location.at_self()) {
 479                         span_mirbug!(
 480                             self,
 481                             place,
 482                             "bad field access ({:?}: {:?}): {:?}",
 483                             ty,
 484                             fty,
 485                             terr
 486                         );
 487                     },
 488                     Err(FieldAccessError::OutOfRange { field_count }) => span_mirbug!(
 489                         self,
 490                         place,
 491                         "accessed field #{} but variant only has {}",
 492                         field.index(),
 493                         field_count
 494                     ),
 495                 }
 496                 PlaceTy::Ty { ty: fty }
 497             }
 498         }
 499     }
 500
 501     fn error(&mut self) -> Ty<'tcx> {
 502         self.errors_reported = true;
 503         self.tcx().types.err
 504     }
 505
 506     fn field_ty(
 507         &mut self,
 508         parent: &dyn fmt::Debug,
 509         base_ty: PlaceTy<'tcx>,
 510         field: Field,
 511         location: Location,
 512     ) -> Result<Ty<'tcx>, FieldAccessError> {
 513         let tcx = self.tcx();
 514
 515         let (variant, substs) = match base_ty {
 516             PlaceTy::Downcast {
 517                 adt_def,
 518                 substs,
 519                 variant_index,
 520             } => (&adt_def.variants[variant_index], substs),
 521             PlaceTy::Ty { ty } => match ty.sty {
 522                 ty::TyAdt(adt_def, substs) if !adt_def.is_enum() => (&adt_def.variants[0], substs),
 523                 ty::TyClosure(def_id, substs) => {
 524                     return match substs.upvar_tys(def_id, tcx).nth(field.index()) {
 525                         Some(ty) => Ok(ty),
 526                         None => Err(FieldAccessError::OutOfRange {
 527                             field_count: substs.upvar_tys(def_id, tcx).count(),
 528                         }),
 529                     }
 530                 }
 531                 ty::TyGenerator(def_id, substs, _) => {
 532                     // Try pre-transform fields first (upvars and current state)
 533                     if let Some(ty) = substs.pre_transforms_tys(def_id, tcx).nth(field.index()) {
 534                         return Ok(ty);
 535                     }
 536
 537                     // Then try `field_tys` which contains all the fields, but it
 538                     // requires the final optimized MIR.
 539                     return match substs.field_tys(def_id, tcx).nth(field.index()) {
 540                         Some(ty) => Ok(ty),
 541                         None => Err(FieldAccessError::OutOfRange {
 542                             field_count: substs.field_tys(def_id, tcx).count(),
 543                         }),
 544                     };
 545                 }
 546                 ty::TyTuple(tys) => {
 547                     return match tys.get(field.index()) {
 548                         Some(&ty) => Ok(ty),
 549                         None => Err(FieldAccessError::OutOfRange {
 550                             field_count: tys.len(),
 551                         }),
 552                     }
 553                 }
 554                 _ => {
 555                     return Ok(span_mirbug_and_err!(
 556                         self,
 557                         parent,
 558                         "can't project out of {:?}",
 559                         base_ty
 560                     ))
 561                 }
 562             },
 563         };
 564
 565         if let Some(field) = variant.fields.get(field.index()) {
 566             Ok(self.cx.normalize(&field.ty(tcx, substs), location))
 567         } else {
 568             Err(FieldAccessError::OutOfRange {
 569                 field_count: variant.fields.len(),
 570             })
 571         }
 572     }
 573 }
 574
 575 /// The MIR type checker. Visits the MIR and enforces all the
 576 /// constraints needed for it to be valid and well-typed. Along the
 577 /// way, it accrues region constraints -- these can later be used by
 578 /// NLL region checking.
 579 struct TypeChecker<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
 580     infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
 581     param_env: ty::ParamEnv<'gcx>,
 582     last_span: Span,
 583     body_id: ast::NodeId,
 584     region_bound_pairs: &'a [(ty::Region<'tcx>, GenericKind<'tcx>)],
 585     implicit_region_bound: Option<ty::Region<'tcx>>,
 586     reported_errors: FxHashSet<(Ty<'tcx>, Span)>,
 587     constraints: MirTypeckRegionConstraints<'tcx>,
 588 }
 589
 590 /// A collection of region constraints that must be satisfied for the
 591 /// program to be considered well-typed.
 592 #[derive(Default)]
 593 pub(crate) struct MirTypeckRegionConstraints<'tcx> {
 594     /// In general, the type-checker is not responsible for enforcing
 595     /// liveness constraints; this job falls to the region inferencer,
 596     /// which performs a liveness analysis. However, in some limited
 597     /// cases, the MIR type-checker creates temporary regions that do
 598     /// not otherwise appear in the MIR -- in particular, the
 599     /// late-bound regions that it instantiates at call-sites -- and
 600     /// hence it must report on their liveness constraints.
 601     pub liveness_set: Vec<(ty::Region<'tcx>, Location, Cause)>,
 602
 603     /// During the course of type-checking, we will accumulate region
 604     /// constraints due to performing subtyping operations or solving
 605     /// traits. These are accumulated into this vector for later use.
 606     pub outlives_sets: Vec<OutlivesSet<'tcx>>,
 607 }
 608
 609 /// Outlives relationships between regions and types created at a
 610 /// particular point within the control-flow graph.
 611 pub struct OutlivesSet<'tcx> {
 612     /// The locations associated with these constraints.
 613     pub locations: Locations,
 614
 615     /// Constraints generated. In terms of the NLL RFC, when you have
 616     /// a constraint `R1: R2 @ P`, the data in there specifies things
 617     /// like `R1: R2`.
 618     pub data: RegionConstraintData<'tcx>,
 619 }
 620
 621 #[derive(Copy, Clone, Debug)]
 622 pub struct Locations {
 623     /// The location in the MIR that generated these constraints.
 624     /// This is intended for error reporting and diagnosis; the
 625     /// constraints may *take effect* at a distinct spot.
 626     pub from_location: Location,
 627
 628     /// The constraints must be met at this location. In terms of the
 629     /// NLL RFC, when you have a constraint `R1: R2 @ P`, this field
 630     /// is the `P` value.
 631     pub at_location: Location,
 632 }
 633
 634 impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
 635     fn new(
 636         infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
 637         body_id: ast::NodeId,
 638         param_env: ty::ParamEnv<'gcx>,
 639         region_bound_pairs: &'a [(ty::Region<'tcx>, GenericKind<'tcx>)],
 640         implicit_region_bound: Option<ty::Region<'tcx>>,
 641     ) -> Self {
 642         TypeChecker {
 643             infcx,
 644             last_span: DUMMY_SP,
 645             body_id,
 646             param_env,
 647             region_bound_pairs,
 648             implicit_region_bound,
 649             reported_errors: FxHashSet(),
 650             constraints: MirTypeckRegionConstraints::default(),
 651         }
 652     }
 653
 654     fn misc(&self, span: Span) -> traits::ObligationCause<'tcx> {
 655         traits::ObligationCause::misc(span, self.body_id)
 656     }
 657
 658     fn fully_perform_op<OP, R>(
 659         &mut self,
 660         locations: Locations,
 661         op: OP,
 662     ) -> Result<R, TypeError<'tcx>>
 663     where
 664         OP: FnOnce(&mut Self) -> InferResult<'tcx, R>,
 665     {
 666         let mut fulfill_cx = TraitEngine::new(self.infcx.tcx);
 667         let InferOk { value, obligations } = self.infcx.commit_if_ok(|_| op(self))?;
 668         fulfill_cx.register_predicate_obligations(self.infcx, obligations);
 669         if let Err(e) = fulfill_cx.select_all_or_error(self.infcx) {
 670             span_mirbug!(self, "", "errors selecting obligation: {:?}", e);
 671         }
 672
 673         self.infcx.process_registered_region_obligations(
 674             self.region_bound_pairs,
 675             self.implicit_region_bound,
 676             self.param_env,
 677             self.body_id,
 678         );
 679
 680         let data = self.infcx.take_and_reset_region_constraints();
 681         if !data.is_empty() {
 682             debug!(
 683                 "fully_perform_op: constraints generated at {:?} are {:#?}",
 684                 locations, data
 685             );
 686             self.constraints
 687                 .outlives_sets
 688                 .push(OutlivesSet { locations, data });
 689         }
 690
 691         Ok(value)
 692     }
 693
 694     fn sub_types(
 695         &mut self,
 696         sub: Ty<'tcx>,
 697         sup: Ty<'tcx>,
 698         locations: Locations,
 699     ) -> UnitResult<'tcx> {
 700         self.fully_perform_op(locations, |this| {
 701             this.infcx
 702                 .at(&this.misc(this.last_span), this.param_env)
 703                 .sup(sup, sub)
 704         })
 705     }
 706
 707     fn eq_types(&mut self, a: Ty<'tcx>, b: Ty<'tcx>, locations: Locations) -> UnitResult<'tcx> {
 708         self.fully_perform_op(locations, |this| {
 709             this.infcx
 710                 .at(&this.misc(this.last_span), this.param_env)
 711                 .eq(b, a)
 712         })
 713     }
 714
 715     fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
 716         self.infcx.tcx
 717     }
 718
 719     fn check_stmt(&mut self, mir: &Mir<'tcx>, stmt: &Statement<'tcx>, location: Location) {
 720         debug!("check_stmt: {:?}", stmt);
 721         let tcx = self.tcx();
 722         match stmt.kind {
 723             StatementKind::Assign(ref place, ref rv) => {
 724                 let place_ty = place.ty(mir, tcx).to_ty(tcx);
 725                 let rv_ty = rv.ty(mir, tcx);
 726                 if let Err(terr) =
 727                     self.sub_types(rv_ty, place_ty, location.at_successor_within_block())
 728                 {
 729                     span_mirbug!(
 730                         self,
 731                         stmt,
 732                         "bad assignment ({:?} = {:?}): {:?}",
 733                         place_ty,
 734                         rv_ty,
 735                         terr
 736                     );
 737                 }
 738                 self.check_rvalue(mir, rv, location);
 739             }
 740             StatementKind::SetDiscriminant {
 741                 ref place,
 742                 variant_index,
 743             } => {
 744                 let place_type = place.ty(mir, tcx).to_ty(tcx);
 745                 let adt = match place_type.sty {
 746                     TypeVariants::TyAdt(adt, _) if adt.is_enum() => adt,
 747                     _ => {
 748                         span_bug!(
 749                             stmt.source_info.span,
 750                             "bad set discriminant ({:?} = {:?}): lhs is not an enum",
 751                             place,
 752                             variant_index
 753                         );
 754                     }
 755                 };
 756                 if variant_index >= adt.variants.len() {
 757                     span_bug!(
 758                         stmt.source_info.span,
 759                         "bad set discriminant ({:?} = {:?}): value of of range",
 760                         place,
 761                         variant_index
 762                     );
 763                 };
 764             }
 765             StatementKind::UserAssertTy(ref c_ty, ref local) => {
 766                 let local_ty = mir.local_decls()[*local].ty;
 767                 let (ty, _) = self.infcx
 768                     .instantiate_canonical_with_fresh_inference_vars(stmt.source_info.span, c_ty);
 769                 debug!(
 770                     "check_stmt: user_assert_ty ty={:?} local_ty={:?}",
 771                     ty, local_ty
 772                 );
 773                 if let Err(terr) = self.eq_types(ty, local_ty, location.at_self()) {
 774                     span_mirbug!(
 775                         self,
 776                         stmt,
 777                         "bad type assert ({:?} = {:?}): {:?}",
 778                         ty,
 779                         local_ty,
 780                         terr
 781                     );
 782                 }
 783             }
 784             StatementKind::StorageLive(_)
 785             | StatementKind::StorageDead(_)
 786             | StatementKind::InlineAsm { .. }
 787             | StatementKind::EndRegion(_)
 788             | StatementKind::Validate(..)
 789             | StatementKind::Nop => {}
 790         }
 791     }
 792
 793     fn check_terminator(
 794         &mut self,
 795         mir: &Mir<'tcx>,
 796         term: &Terminator<'tcx>,
 797         term_location: Location,
 798     ) {
 799         debug!("check_terminator: {:?}", term);
 800         let tcx = self.tcx();
 801         match term.kind {
 802             TerminatorKind::Goto { .. }
 803             | TerminatorKind::Resume
 804             | TerminatorKind::Abort
 805             | TerminatorKind::Return
 806             | TerminatorKind::GeneratorDrop
 807             | TerminatorKind::Unreachable
 808             | TerminatorKind::Drop { .. }
 809             | TerminatorKind::FalseEdges { .. }
 810             | TerminatorKind::FalseUnwind { .. } => {
 811                 // no checks needed for these
 812             }
 813
 814             TerminatorKind::DropAndReplace {
 815                 ref location,
 816                 ref value,
 817                 target,
 818                 unwind,
 819             } => {
 820                 let place_ty = location.ty(mir, tcx).to_ty(tcx);
 821                 let rv_ty = value.ty(mir, tcx);
 822
 823                 let locations = Locations {
 824                     from_location: term_location,
 825                     at_location: target.start_location(),
 826                 };
 827                 if let Err(terr) = self.sub_types(rv_ty, place_ty, locations) {
 828                     span_mirbug!(
 829                         self,
 830                         term,
 831                         "bad DropAndReplace ({:?} = {:?}): {:?}",
 832                         place_ty,
 833                         rv_ty,
 834                         terr
 835                     );
 836                 }
 837
 838                 // Subtle: this assignment occurs at the start of
 839                 // *both* blocks, so we need to ensure that it holds
 840                 // at both locations.
 841                 if let Some(unwind) = unwind {
 842                     let locations = Locations {
 843                         from_location: term_location,
 844                         at_location: unwind.start_location(),
 845                     };
 846                     if let Err(terr) = self.sub_types(rv_ty, place_ty, locations) {
 847                         span_mirbug!(
 848                             self,
 849                             term,
 850                             "bad DropAndReplace ({:?} = {:?}): {:?}",
 851                             place_ty,
 852                             rv_ty,
 853                             terr
 854                         );
 855                     }
 856                 }
 857             }
 858             TerminatorKind::SwitchInt {
 859                 ref discr,
 860                 switch_ty,
 861                 ..
 862             } => {
 863                 let discr_ty = discr.ty(mir, tcx);
 864                 if let Err(terr) = self.sub_types(discr_ty, switch_ty, term_location.at_self()) {
 865                     span_mirbug!(
 866                         self,
 867                         term,
 868                         "bad SwitchInt ({:?} on {:?}): {:?}",
 869                         switch_ty,
 870                         discr_ty,
 871                         terr
 872                     );
 873                 }
 874                 if !switch_ty.is_integral() && !switch_ty.is_char() && !switch_ty.is_bool() {
 875                     span_mirbug!(self, term, "bad SwitchInt discr ty {:?}", switch_ty);
 876                 }
 877                 // FIXME: check the values
 878             }
 879             TerminatorKind::Call {
 880                 ref func,
 881                 ref args,
 882                 ref destination,
 883                 ..
 884             } => {
 885                 let func_ty = func.ty(mir, tcx);
 886                 debug!("check_terminator: call, func_ty={:?}", func_ty);
 887                 let sig = match func_ty.sty {
 888                     ty::TyFnDef(..) | ty::TyFnPtr(_) => func_ty.fn_sig(tcx),
 889                     _ => {
 890                         span_mirbug!(self, term, "call to non-function {:?}", func_ty);
 891                         return;
 892                     }
 893                 };
 894                 let (sig, map) = self.infcx.replace_late_bound_regions_with_fresh_var(
 895                     term.source_info.span,
 896                     LateBoundRegionConversionTime::FnCall,
 897                     &sig,
 898                 );
 899                 let sig = self.normalize(&sig, term_location);
 900                 self.check_call_dest(mir, term, &sig, destination, term_location);
 901
 902                 self.prove_predicates(
 903                     sig.inputs().iter().map(|ty| ty::Predicate::WellFormed(ty)),
 904                     term_location,
 905                 );
 906
 907                 // The ordinary liveness rules will ensure that all
 908                 // regions in the type of the callee are live here. We
 909                 // then further constrain the late-bound regions that
 910                 // were instantiated at the call site to be live as
 911                 // well. The resulting is that all the input (and
 912                 // output) types in the signature must be live, since
 913                 // all the inputs that fed into it were live.
 914                 for &late_bound_region in map.values() {
 915                     self.constraints.liveness_set.push((
 916                         late_bound_region,
 917                         term_location,
 918                         Cause::LiveOther(term_location),
 919                     ));
 920                 }
 921
 922                 self.check_call_inputs(mir, term, &sig, args, term_location);
 923             }
 924             TerminatorKind::Assert {
 925                 ref cond, ref msg, ..
 926             } => {
 927                 let cond_ty = cond.ty(mir, tcx);
 928                 if cond_ty != tcx.types.bool {
 929                     span_mirbug!(self, term, "bad Assert ({:?}, not bool", cond_ty);
 930                 }
 931
 932                 if let BoundsCheck { ref len, ref index } = *msg {
 933                     if len.ty(mir, tcx) != tcx.types.usize {
 934                         span_mirbug!(self, len, "bounds-check length non-usize {:?}", len)
 935                     }
 936                     if index.ty(mir, tcx) != tcx.types.usize {
 937                         span_mirbug!(self, index, "bounds-check index non-usize {:?}", index)
 938                     }
 939                 }
 940             }
 941             TerminatorKind::Yield { ref value, .. } => {
 942                 let value_ty = value.ty(mir, tcx);
 943                 match mir.yield_ty {
 944                     None => span_mirbug!(self, term, "yield in non-generator"),
 945                     Some(ty) => {
 946                         if let Err(terr) = self.sub_types(value_ty, ty, term_location.at_self()) {
 947                             span_mirbug!(
 948                                 self,
 949                                 term,
 950                                 "type of yield value is {:?}, but the yield type is {:?}: {:?}",
 951                                 value_ty,
 952                                 ty,
 953                                 terr
 954                             );
 955                         }
 956                     }
 957                 }
 958             }
 959         }
 960     }
 961
 962     fn check_call_dest(
 963         &mut self,
 964         mir: &Mir<'tcx>,
 965         term: &Terminator<'tcx>,
 966         sig: &ty::FnSig<'tcx>,
 967         destination: &Option<(Place<'tcx>, BasicBlock)>,
 968         term_location: Location,
 969     ) {
 970         let tcx = self.tcx();
 971         match *destination {
 972             Some((ref dest, target_block)) => {
 973                 let dest_ty = dest.ty(mir, tcx).to_ty(tcx);
 974                 let locations = Locations {
 975                     from_location: term_location,
 976                     at_location: target_block.start_location(),
 977                 };
 978                 if let Err(terr) = self.sub_types(sig.output(), dest_ty, locations) {
 979                     span_mirbug!(
 980                         self,
 981                         term,
 982                         "call dest mismatch ({:?} <- {:?}): {:?}",
 983                         dest_ty,
 984                         sig.output(),
 985                         terr
 986                     );
 987                 }
 988             }
 989             None => {
 990                 // FIXME(canndrew): This is_never should probably be an is_uninhabited
 991                 if !sig.output().is_never() {
 992                     span_mirbug!(self, term, "call to converging function {:?} w/o dest", sig);
 993                 }
 994             }
 995         }
 996     }
 997
 998     fn check_call_inputs(
 999         &mut self,
1000         mir: &Mir<'tcx>,
1001         term: &Terminator<'tcx>,
1002         sig: &ty::FnSig<'tcx>,
1003         args: &[Operand<'tcx>],
1004         term_location: Location,
1005     ) {
1006         debug!("check_call_inputs({:?}, {:?})", sig, args);
1007         if args.len() < sig.inputs().len() || (args.len() > sig.inputs().len() && !sig.variadic) {
1008             span_mirbug!(self, term, "call to {:?} with wrong # of args", sig);
1009         }
1010         for (n, (fn_arg, op_arg)) in sig.inputs().iter().zip(args).enumerate() {
1011             let op_arg_ty = op_arg.ty(mir, self.tcx());
1012             if let Err(terr) = self.sub_types(op_arg_ty, fn_arg, term_location.at_self()) {
1013                 span_mirbug!(
1014                     self,
1015                     term,
1016                     "bad arg #{:?} ({:?} <- {:?}): {:?}",
1017                     n,
1018                     fn_arg,
1019                     op_arg_ty,
1020                     terr
1021                 );
1022             }
1023         }
1024     }
1025
1026     fn check_iscleanup(&mut self, mir: &Mir<'tcx>, block_data: &BasicBlockData<'tcx>) {
1027         let is_cleanup = block_data.is_cleanup;
1028         self.last_span = block_data.terminator().source_info.span;
1029         match block_data.terminator().kind {
1030             TerminatorKind::Goto { target } => {
1031                 self.assert_iscleanup(mir, block_data, target, is_cleanup)
1032             }
1033             TerminatorKind::SwitchInt { ref targets, .. } => for target in targets {
1034                 self.assert_iscleanup(mir, block_data, *target, is_cleanup);
1035             },
1036             TerminatorKind::Resume => if !is_cleanup {
1037                 span_mirbug!(self, block_data, "resume on non-cleanup block!")
1038             },
1039             TerminatorKind::Abort => if !is_cleanup {
1040                 span_mirbug!(self, block_data, "abort on non-cleanup block!")
1041             },
1042             TerminatorKind::Return => if is_cleanup {
1043                 span_mirbug!(self, block_data, "return on cleanup block")
1044             },
1045             TerminatorKind::GeneratorDrop { .. } => if is_cleanup {
1046                 span_mirbug!(self, block_data, "generator_drop in cleanup block")
1047             },
1048             TerminatorKind::Yield { resume, drop, .. } => {
1049                 if is_cleanup {
1050                     span_mirbug!(self, block_data, "yield in cleanup block")
1051                 }
1052                 self.assert_iscleanup(mir, block_data, resume, is_cleanup);
1053                 if let Some(drop) = drop {
1054                     self.assert_iscleanup(mir, block_data, drop, is_cleanup);
1055                 }
1056             }
1057             TerminatorKind::Unreachable => {}
1058             TerminatorKind::Drop { target, unwind, .. }
1059             | TerminatorKind::DropAndReplace { target, unwind, .. }
1060             | TerminatorKind::Assert {
1061                 target,
1062                 cleanup: unwind,
1063                 ..
1064             } => {
1065                 self.assert_iscleanup(mir, block_data, target, is_cleanup);
1066                 if let Some(unwind) = unwind {
1067                     if is_cleanup {
1068                         span_mirbug!(self, block_data, "unwind on cleanup block")
1069                     }
1070                     self.assert_iscleanup(mir, block_data, unwind, true);
1071                 }
1072             }
1073             TerminatorKind::Call {
1074                 ref destination,
1075                 cleanup,
1076                 ..
1077             } => {
1078                 if let &Some((_, target)) = destination {
1079                     self.assert_iscleanup(mir, block_data, target, is_cleanup);
1080                 }
1081                 if let Some(cleanup) = cleanup {
1082                     if is_cleanup {
1083                         span_mirbug!(self, block_data, "cleanup on cleanup block")
1084                     }
1085                     self.assert_iscleanup(mir, block_data, cleanup, true);
1086                 }
1087             }
1088             TerminatorKind::FalseEdges {
1089                 real_target,
1090                 ref imaginary_targets,
1091             } => {
1092                 self.assert_iscleanup(mir, block_data, real_target, is_cleanup);
1093                 for target in imaginary_targets {
1094                     self.assert_iscleanup(mir, block_data, *target, is_cleanup);
1095                 }
1096             }
1097             TerminatorKind::FalseUnwind {
1098                 real_target,
1099                 unwind,
1100             } => {
1101                 self.assert_iscleanup(mir, block_data, real_target, is_cleanup);
1102                 if let Some(unwind) = unwind {
1103                     if is_cleanup {
1104                         span_mirbug!(
1105                             self,
1106                             block_data,
1107                             "cleanup in cleanup block via false unwind"
1108                         );
1109                     }
1110                     self.assert_iscleanup(mir, block_data, unwind, true);
1111                 }
1112             }
1113         }
1114     }
1115
1116     fn assert_iscleanup(
1117         &mut self,
1118         mir: &Mir<'tcx>,
1119         ctxt: &dyn fmt::Debug,
1120         bb: BasicBlock,
1121         iscleanuppad: bool,
1122     ) {
1123         if mir[bb].is_cleanup != iscleanuppad {
1124             span_mirbug!(
1125                 self,
1126                 ctxt,
1127                 "cleanuppad mismatch: {:?} should be {:?}",
1128                 bb,
1129                 iscleanuppad
1130             );
1131         }
1132     }
1133
1134     fn check_local(&mut self, mir: &Mir<'tcx>, local: Local, local_decl: &LocalDecl<'tcx>) {
1135         match mir.local_kind(local) {
1136             LocalKind::ReturnPointer | LocalKind::Arg => {
1137                 // return values of normal functions are required to be
1138                 // sized by typeck, but return values of ADT constructors are
1139                 // not because we don't include a `Self: Sized` bounds on them.
1140                 //
1141                 // Unbound parts of arguments were never required to be Sized
1142                 // - maybe we should make that a warning.
1143                 return;
1144             }
1145             LocalKind::Var | LocalKind::Temp => {}
1146         }
1147
1148         let span = local_decl.source_info.span;
1149         let ty = local_decl.ty;
1150
1151         // Erase the regions from `ty` to get a global type.  The
1152         // `Sized` bound in no way depends on precise regions, so this
1153         // shouldn't affect `is_sized`.
1154         let gcx = self.tcx().global_tcx();
1155         let erased_ty = gcx.lift(&self.tcx().erase_regions(&ty)).unwrap();
1156         if !erased_ty.is_sized(gcx.at(span), self.param_env) {
1157             // in current MIR construction, all non-control-flow rvalue
1158             // expressions evaluate through `as_temp` or `into` a return
1159             // slot or local, so to find all unsized rvalues it is enough
1160             // to check all temps, return slots and locals.
1161             if let None = self.reported_errors.replace((ty, span)) {
1162                 span_err!(
1163                     self.tcx().sess,
1164                     span,
1165                     E0161,
1166                     "cannot move a value of type {0}: the size of {0} \
1167                      cannot be statically determined",
1168                     ty
1169                 );
1170             }
1171         }
1172     }
1173
1174     fn aggregate_field_ty(
1175         &mut self,
1176         ak: &AggregateKind<'tcx>,
1177         field_index: usize,
1178         location: Location,
1179     ) -> Result<Ty<'tcx>, FieldAccessError> {
1180         let tcx = self.tcx();
1181
1182         match *ak {
1183             AggregateKind::Adt(def, variant_index, substs, active_field_index) => {
1184                 let variant = &def.variants[variant_index];
1185                 let adj_field_index = active_field_index.unwrap_or(field_index);
1186                 if let Some(field) = variant.fields.get(adj_field_index) {
1187                     Ok(self.normalize(&field.ty(tcx, substs), location))
1188                 } else {
1189                     Err(FieldAccessError::OutOfRange {
1190                         field_count: variant.fields.len(),
1191                     })
1192                 }
1193             }
1194             AggregateKind::Closure(def_id, substs) => {
1195                 match substs.upvar_tys(def_id, tcx).nth(field_index) {
1196                     Some(ty) => Ok(ty),
1197                     None => Err(FieldAccessError::OutOfRange {
1198                         field_count: substs.upvar_tys(def_id, tcx).count(),
1199                     }),
1200                 }
1201             }
1202             AggregateKind::Generator(def_id, substs, _) => {
1203                 // Try pre-transform fields first (upvars and current state)
1204                 if let Some(ty) = substs.pre_transforms_tys(def_id, tcx).nth(field_index) {
1205                     Ok(ty)
1206                 } else {
1207                     // Then try `field_tys` which contains all the fields, but it
1208                     // requires the final optimized MIR.
1209                     match substs.field_tys(def_id, tcx).nth(field_index) {
1210                         Some(ty) => Ok(ty),
1211                         None => Err(FieldAccessError::OutOfRange {
1212                             field_count: substs.field_tys(def_id, tcx).count(),
1213                         }),
1214                     }
1215                 }
1216             }
1217             AggregateKind::Array(ty) => Ok(ty),
1218             AggregateKind::Tuple => {
1219                 unreachable!("This should have been covered in check_rvalues");
1220             }
1221         }
1222     }
1223
1224     fn check_rvalue(&mut self, mir: &Mir<'tcx>, rvalue: &Rvalue<'tcx>, location: Location) {
1225         let tcx = self.tcx();
1226
1227         match rvalue {
1228             Rvalue::Aggregate(ak, ops) => {
1229                 self.check_aggregate_rvalue(mir, rvalue, ak, ops, location)
1230             }
1231
1232             Rvalue::Repeat(operand, len) => if *len > 1 {
1233                 let operand_ty = operand.ty(mir, tcx);
1234
1235                 let trait_ref = ty::TraitRef {
1236                     def_id: tcx.lang_items().copy_trait().unwrap(),
1237                     substs: tcx.mk_substs_trait(operand_ty, &[]),
1238                 };
1239
1240                 self.prove_trait_ref(trait_ref, location);
1241             },
1242
1243             Rvalue::NullaryOp(_, ty) => {
1244                 let trait_ref = ty::TraitRef {
1245                     def_id: tcx.lang_items().sized_trait().unwrap(),
1246                     substs: tcx.mk_substs_trait(ty, &[]),
1247                 };
1248
1249                 self.prove_trait_ref(trait_ref, location);
1250             }
1251
1252             Rvalue::Cast(cast_kind, op, ty) => match cast_kind {
1253                 CastKind::ReifyFnPointer => {
1254                     let fn_sig = op.ty(mir, tcx).fn_sig(tcx);
1255
1256                     // The type that we see in the fcx is like
1257                     // `foo::<'a, 'b>`, where `foo` is the path to a
1258                     // function definition. When we extract the
1259                     // signature, it comes from the `fn_sig` query,
1260                     // and hence may contain unnormalized results.
1261                     let fn_sig = self.normalize(&fn_sig, location);
1262
1263                     let ty_fn_ptr_from = tcx.mk_fn_ptr(fn_sig);
1264
1265                     if let Err(terr) = self.eq_types(ty_fn_ptr_from, ty, location.at_self()) {
1266                         span_mirbug!(
1267                             self,
1268                             rvalue,
1269                             "equating {:?} with {:?} yields {:?}",
1270                             ty_fn_ptr_from,
1271                             ty,
1272                             terr
1273                         );
1274                     }
1275                 }
1276
1277                 CastKind::ClosureFnPointer => {
1278                     let sig = match op.ty(mir, tcx).sty {
1279                         ty::TyClosure(def_id, substs) => {
1280                             substs.closure_sig_ty(def_id, tcx).fn_sig(tcx)
1281                         }
1282                         _ => bug!(),
1283                     };
1284                     let ty_fn_ptr_from = tcx.coerce_closure_fn_ty(sig);
1285
1286                     if let Err(terr) = self.eq_types(ty_fn_ptr_from, ty, location.at_self()) {
1287                         span_mirbug!(
1288                             self,
1289                             rvalue,
1290                             "equating {:?} with {:?} yields {:?}",
1291                             ty_fn_ptr_from,
1292                             ty,
1293                             terr
1294                         );
1295                     }
1296                 }
1297
1298                 CastKind::UnsafeFnPointer => {
1299                     let fn_sig = op.ty(mir, tcx).fn_sig(tcx);
1300
1301                     // The type that we see in the fcx is like
1302                     // `foo::<'a, 'b>`, where `foo` is the path to a
1303                     // function definition. When we extract the
1304                     // signature, it comes from the `fn_sig` query,
1305                     // and hence may contain unnormalized results.
1306                     let fn_sig = self.normalize(&fn_sig, location);
1307
1308                     let ty_fn_ptr_from = tcx.safe_to_unsafe_fn_ty(fn_sig);
1309
1310                     if let Err(terr) = self.eq_types(ty_fn_ptr_from, ty, location.at_self()) {
1311                         span_mirbug!(
1312                             self,
1313                             rvalue,
1314                             "equating {:?} with {:?} yields {:?}",
1315                             ty_fn_ptr_from,
1316                             ty,
1317                             terr
1318                         );
1319                     }
1320                 }
1321
1322                 CastKind::Unsize => {
1323                     let trait_ref = ty::TraitRef {
1324                         def_id: tcx.lang_items().coerce_unsized_trait().unwrap(),
1325                         substs: tcx.mk_substs_trait(op.ty(mir, tcx), &[ty]),
1326                     };
1327
1328                     self.prove_trait_ref(trait_ref, location);
1329                 }
1330
1331                 CastKind::Misc => {}
1332             },
1333
1334             // FIXME: These other cases have to be implemented in future PRs
1335             Rvalue::Use(..)
1336             | Rvalue::Ref(..)
1337             | Rvalue::Len(..)
1338             | Rvalue::BinaryOp(..)
1339             | Rvalue::CheckedBinaryOp(..)
1340             | Rvalue::UnaryOp(..)
1341             | Rvalue::Discriminant(..) => {}
1342         }
1343     }
1344
1345     fn check_aggregate_rvalue(
1346         &mut self,
1347         mir: &Mir<'tcx>,
1348         rvalue: &Rvalue<'tcx>,
1349         aggregate_kind: &AggregateKind<'tcx>,
1350         operands: &[Operand<'tcx>],
1351         location: Location,
1352     ) {
1353         let tcx = self.tcx();
1354
1355         self.prove_aggregate_predicates(aggregate_kind, location);
1356
1357         if *aggregate_kind == AggregateKind::Tuple {
1358             // tuple rvalue field type is always the type of the op. Nothing to check here.
1359             return;
1360         }
1361
1362         for (i, operand) in operands.iter().enumerate() {
1363             let field_ty = match self.aggregate_field_ty(aggregate_kind, i, location) {
1364                 Ok(field_ty) => field_ty,
1365                 Err(FieldAccessError::OutOfRange { field_count }) => {
1366                     span_mirbug!(
1367                         self,
1368                         rvalue,
1369                         "accessed field #{} but variant only has {}",
1370                         i,
1371                         field_count
1372                     );
1373                     continue;
1374                 }
1375             };
1376             let operand_ty = operand.ty(mir, tcx);
1377             if let Err(terr) =
1378                 self.sub_types(operand_ty, field_ty, location.at_successor_within_block())
1379             {
1380                 span_mirbug!(
1381                     self,
1382                     rvalue,
1383                     "{:?} is not a subtype of {:?}: {:?}",
1384                     operand_ty,
1385                     field_ty,
1386                     terr
1387                 );
1388             }
1389         }
1390     }
1391
1392     fn prove_aggregate_predicates(
1393         &mut self,
1394         aggregate_kind: &AggregateKind<'tcx>,
1395         location: Location,
1396     ) {
1397         let tcx = self.tcx();
1398
1399         debug!(
1400             "prove_aggregate_predicates(aggregate_kind={:?}, location={:?})",
1401             aggregate_kind, location
1402         );
1403
1404         let instantiated_predicates = match aggregate_kind {
1405             AggregateKind::Adt(def, _, substs, _) => {
1406                 tcx.predicates_of(def.did).instantiate(tcx, substs)
1407             }
1408
1409             // For closures, we have some **extra requirements** we
1410             //
1411             // have to check. In particular, in their upvars and
1412             // signatures, closures often reference various regions
1413             // from the surrounding function -- we call those the
1414             // closure's free regions. When we borrow-check (and hence
1415             // region-check) closures, we may find that the closure
1416             // requires certain relationships between those free
1417             // regions. However, because those free regions refer to
1418             // portions of the CFG of their caller, the closure is not
1419             // in a position to verify those relationships. In that
1420             // case, the requirements get "propagated" to us, and so
1421             // we have to solve them here where we instantiate the
1422             // closure.
1423             //
1424             // Despite the opacity of the previous parapgrah, this is
1425             // actually relatively easy to understand in terms of the
1426             // desugaring. A closure gets desugared to a struct, and
1427             // these extra requirements are basically like where
1428             // clauses on the struct.
1429             AggregateKind::Closure(def_id, substs) => {
1430                 if let Some(closure_region_requirements) =
1431                     tcx.mir_borrowck(*def_id).closure_requirements
1432                 {
1433                     closure_region_requirements.apply_requirements(
1434                         self.infcx,
1435                         self.body_id,
1436                         location,
1437                         *def_id,
1438                         *substs,
1439                     );
1440                 }
1441
1442                 tcx.predicates_of(*def_id).instantiate(tcx, substs.substs)
1443             }
1444
1445             AggregateKind::Generator(def_id, substs, _) => {
1446                 tcx.predicates_of(*def_id).instantiate(tcx, substs.substs)
1447             }
1448
1449             AggregateKind::Array(_) | AggregateKind::Tuple => ty::InstantiatedPredicates::empty(),
1450         };
1451
1452         let predicates = self.normalize(&instantiated_predicates.predicates, location);
1453         debug!("prove_aggregate_predicates: predicates={:?}", predicates);
1454         self.prove_predicates(predicates, location);
1455     }
1456
1457     fn prove_trait_ref(&mut self, trait_ref: ty::TraitRef<'tcx>, location: Location) {
1458         self.prove_predicates(
1459             Some(ty::Predicate::Trait(
1460                 trait_ref.to_poly_trait_ref().to_poly_trait_predicate(),
1461             )),
1462             location,
1463         );
1464     }
1465
1466     fn prove_predicates<T>(&mut self, predicates: T, location: Location)
1467     where
1468         T: IntoIterator<Item = ty::Predicate<'tcx>>,
1469         T::IntoIter: Clone,
1470     {
1471         let predicates = predicates.into_iter();
1472
1473         debug!(
1474             "prove_predicates(predicates={:?}, location={:?})",
1475             predicates.clone().collect::<Vec<_>>(),
1476             location,
1477         );
1478         self.fully_perform_op(location.at_self(), |this| {
1479             let cause = this.misc(this.last_span);
1480             let obligations = predicates
1481                 .into_iter()
1482                 .map(|p| traits::Obligation::new(cause.clone(), this.param_env, p))
1483                 .collect();
1484             Ok(InferOk {
1485                 value: (),
1486                 obligations,
1487             })
1488         }).unwrap()
1489     }
1490
1491     fn typeck_mir(&mut self, mir: &Mir<'tcx>) {
1492         self.last_span = mir.span;
1493         debug!("run_on_mir: {:?}", mir.span);
1494
1495         for (local, local_decl) in mir.local_decls.iter_enumerated() {
1496             self.check_local(mir, local, local_decl);
1497         }
1498
1499         for (block, block_data) in mir.basic_blocks().iter_enumerated() {
1500             let mut location = Location {
1501                 block,
1502                 statement_index: 0,
1503             };
1504             for stmt in &block_data.statements {
1505                 if stmt.source_info.span != DUMMY_SP {
1506                     self.last_span = stmt.source_info.span;
1507                 }
1508                 self.check_stmt(mir, stmt, location);
1509                 location.statement_index += 1;
1510             }
1511
1512             self.check_terminator(mir, block_data.terminator(), location);
1513             self.check_iscleanup(mir, block_data);
1514         }
1515     }
1516
1517     fn normalize<T>(&mut self, value: &T, location: Location) -> T
1518     where
1519         T: fmt::Debug + TypeFoldable<'tcx>,
1520     {
1521         debug!("normalize(value={:?}, location={:?})", value, location);
1522         self.fully_perform_op(location.at_self(), |this| {
1523             let Normalized { value, obligations } = this.infcx
1524                 .at(&this.misc(this.last_span), this.param_env)
1525                 .normalize(value)
1526                 .unwrap_or_else(|NoSolution| {
1527                     span_bug!(
1528                         this.last_span,
1529                         "normalization of `{:?}` failed at {:?}",
1530                         value,
1531                         location,
1532                     );
1533                 });
1534             Ok(InferOk { value, obligations })
1535         }).unwrap()
1536     }
1537 }
1538
1539 pub struct TypeckMir;
1540
1541 impl MirPass for TypeckMir {
1542     fn run_pass<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, src: MirSource, mir: &mut Mir<'tcx>) {
1543         let def_id = src.def_id;
1544         let id = tcx.hir.as_local_node_id(def_id).unwrap();
1545         debug!("run_pass: {:?}", def_id);
1546
1547         // When NLL is enabled, the borrow checker runs the typeck
1548         // itself, so we don't need this MIR pass anymore.
1549         if tcx.use_mir_borrowck() {
1550             return;
1551         }
1552
1553         if tcx.sess.err_count() > 0 {
1554             // compiling a broken program can obviously result in a
1555             // broken MIR, so try not to report duplicate errors.
1556             return;
1557         }
1558         let param_env = tcx.param_env(def_id);
1559         tcx.infer_ctxt().enter(|infcx| {
1560             let _ = type_check_internal(&infcx, id, param_env, mir, &[], None, &mut |_| ());
1561
1562             // For verification purposes, we just ignore the resulting
1563             // region constraint sets. Not our problem. =)
1564         });
1565     }
1566 }
1567
1568 trait AtLocation {
1569     /// Creates a `Locations` where `self` is both the from-location
1570     /// and the at-location. This means that any required region
1571     /// relationships must hold upon entering the statement/terminator
1572     /// indicated by `self`. This is typically used when processing
1573     /// "inputs" to the given location.
1574     fn at_self(self) -> Locations;
1575
1576     /// Creates a `Locations` where `self` is the from-location and
1577     /// its successor within the block is the at-location. This means
1578     /// that any required region relationships must hold only upon
1579     /// **exiting** the statement/terminator indicated by `self`. This
1580     /// is for example used when you have a `place = rv` statement: it
1581     /// indicates that the `typeof(rv) <: typeof(place)` as of the
1582     /// **next** statement.
1583     fn at_successor_within_block(self) -> Locations;
1584 }
1585
1586 impl AtLocation for Location {
1587     fn at_self(self) -> Locations {
1588         Locations {
1589             from_location: self,
1590             at_location: self,
1591         }
1592     }
1593
1594     fn at_successor_within_block(self) -> Locations {
1595         Locations {
1596             from_location: self,
1597             at_location: self.successor_within_block(),
1598         }
1599     }
1600 }