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