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