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

   1 //! This pass type-checks the MIR to ensure it is not broken.
   2
   3 use crate::borrow_check::borrow_set::BorrowSet;
   4 use crate::borrow_check::location::LocationTable;
   5 use crate::borrow_check::nll::constraints::{OutlivesConstraintSet, OutlivesConstraint};
   6 use crate::borrow_check::nll::member_constraints::MemberConstraintSet;
   7 use crate::borrow_check::nll::facts::AllFacts;
   8 use crate::borrow_check::nll::region_infer::values::LivenessValues;
   9 use crate::borrow_check::nll::region_infer::values::PlaceholderIndex;
  10 use crate::borrow_check::nll::region_infer::values::PlaceholderIndices;
  11 use crate::borrow_check::nll::region_infer::values::RegionValueElements;
  12 use crate::borrow_check::nll::region_infer::{ClosureRegionRequirementsExt, TypeTest};
  13 use crate::borrow_check::nll::renumber;
  14 use crate::borrow_check::nll::type_check::free_region_relations::{
  15     CreateResult, UniversalRegionRelations,
  16 };
  17 use crate::borrow_check::nll::universal_regions::{DefiningTy, UniversalRegions};
  18 use crate::borrow_check::nll::ToRegionVid;
  19 use crate::dataflow::move_paths::MoveData;
  20 use crate::dataflow::FlowAtLocation;
  21 use crate::dataflow::MaybeInitializedPlaces;
  22 use either::Either;
  23 use rustc::hir;
  24 use rustc::hir::def_id::DefId;
  25 use rustc::infer::canonical::QueryRegionConstraints;
  26 use rustc::infer::outlives::env::RegionBoundPairs;
  27 use rustc::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime, NLLRegionVariableOrigin};
  28 use rustc::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
  29 use rustc::mir::interpret::{ConstValue, PanicInfo};
  30 use rustc::mir::tcx::PlaceTy;
  31 use rustc::mir::visit::{PlaceContext, Visitor, NonMutatingUseContext};
  32 use rustc::mir::*;
  33 use rustc::traits::query::type_op;
  34 use rustc::traits::query::type_op::custom::CustomTypeOp;
  35 use rustc::traits::query::{Fallible, NoSolution};
  36 use rustc::traits::{self, ObligationCause, PredicateObligations};
  37 use rustc::ty::adjustment::{PointerCast};
  38 use rustc::ty::fold::TypeFoldable;
  39 use rustc::ty::subst::{Subst, SubstsRef, UnpackedKind, UserSubsts};
  40 use rustc::ty::{
  41     self, RegionVid, ToPolyTraitRef, Ty, TyCtxt, UserType,
  42     CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations,
  43     UserTypeAnnotationIndex,
  44 };
  45 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  46 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
  47 use rustc::ty::layout::VariantIdx;
  48 use std::rc::Rc;
  49 use std::{fmt, iter, mem};
  50 use syntax_pos::{Span, DUMMY_SP};
  51
  52 macro_rules! span_mirbug {
  53     ($context:expr, $elem:expr, $($message:tt)*) => ({
  54         $crate::borrow_check::nll::type_check::mirbug(
  55             $context.tcx(),
  56             $context.last_span,
  57             &format!(
  58                 "broken MIR in {:?} ({:?}): {}",
  59                 $context.mir_def_id,
  60                 $elem,
  61                 format_args!($($message)*),
  62             ),
  63         )
  64     })
  65 }
  66
  67 macro_rules! span_mirbug_and_err {
  68     ($context:expr, $elem:expr, $($message:tt)*) => ({
  69         {
  70             span_mirbug!($context, $elem, $($message)*);
  71             $context.error()
  72         }
  73     })
  74 }
  75
  76 mod constraint_conversion;
  77 pub mod free_region_relations;
  78 mod input_output;
  79 crate mod liveness;
  80 mod relate_tys;
  81
  82 /// Type checks the given `mir` in the context of the inference
  83 /// context `infcx`. Returns any region constraints that have yet to
  84 /// be proven. This result is includes liveness constraints that
  85 /// ensure that regions appearing in the types of all local variables
  86 /// are live at all points where that local variable may later be
  87 /// used.
  88 ///
  89 /// This phase of type-check ought to be infallible -- this is because
  90 /// the original, HIR-based type-check succeeded. So if any errors
  91 /// occur here, we will get a `bug!` reported.
  92 ///
  93 /// # Parameters
  94 ///
  95 /// - `infcx` -- inference context to use
  96 /// - `param_env` -- parameter environment to use for trait solving
  97 /// - `mir` -- MIR to type-check
  98 /// - `mir_def_id` -- DefId from which the MIR is derived (must be local)
  99 /// - `region_bound_pairs` -- the implied outlives obligations between type parameters
 100 ///   and lifetimes (e.g., `&'a T` implies `T: 'a`)
 101 /// - `implicit_region_bound` -- a region which all generic parameters are assumed
 102 ///   to outlive; should represent the fn body
 103 /// - `input_tys` -- fully liberated, but **not** normalized, expected types of the arguments;
 104 ///   the types of the input parameters found in the MIR itself will be equated with these
 105 /// - `output_ty` -- fully liberated, but **not** normalized, expected return type;
 106 ///   the type for the RETURN_PLACE will be equated with this
 107 /// - `liveness` -- results of a liveness computation on the MIR; used to create liveness
 108 ///   constraints for the regions in the types of variables
 109 /// - `flow_inits` -- results of a maybe-init dataflow analysis
 110 /// - `move_data` -- move-data constructed when performing the maybe-init dataflow analysis
 111 pub(crate) fn type_check<'tcx>(
 112     infcx: &InferCtxt<'_, 'tcx>,
 113     param_env: ty::ParamEnv<'tcx>,
 114     body: &Body<'tcx>,
 115     promoted: &IndexVec<Promoted, Body<'tcx>>,
 116     mir_def_id: DefId,
 117     universal_regions: &Rc<UniversalRegions<'tcx>>,
 118     location_table: &LocationTable,
 119     borrow_set: &BorrowSet<'tcx>,
 120     all_facts: &mut Option<AllFacts>,
 121     flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'tcx>>,
 122     move_data: &MoveData<'tcx>,
 123     elements: &Rc<RegionValueElements>,
 124 ) -> MirTypeckResults<'tcx> {
 125     let implicit_region_bound = infcx.tcx.mk_region(ty::ReVar(universal_regions.fr_fn_body));
 126     let mut constraints = MirTypeckRegionConstraints {
 127         placeholder_indices: PlaceholderIndices::default(),
 128         placeholder_index_to_region: IndexVec::default(),
 129         liveness_constraints: LivenessValues::new(elements.clone()),
 130         outlives_constraints: OutlivesConstraintSet::default(),
 131         member_constraints: MemberConstraintSet::default(),
 132         closure_bounds_mapping: Default::default(),
 133         type_tests: Vec::default(),
 134     };
 135
 136     let CreateResult {
 137         universal_region_relations,
 138         region_bound_pairs,
 139         normalized_inputs_and_output,
 140     } = free_region_relations::create(
 141         infcx,
 142         param_env,
 143         Some(implicit_region_bound),
 144         universal_regions,
 145         &mut constraints,
 146     );
 147
 148     let mut borrowck_context = BorrowCheckContext {
 149         universal_regions,
 150         location_table,
 151         borrow_set,
 152         all_facts,
 153         constraints: &mut constraints,
 154     };
 155
 156     type_check_internal(
 157         infcx,
 158         mir_def_id,
 159         param_env,
 160         body,
 161         promoted,
 162         &region_bound_pairs,
 163         implicit_region_bound,
 164         &mut borrowck_context,
 165         &universal_region_relations,
 166         |mut cx| {
 167             cx.equate_inputs_and_outputs(body, universal_regions, &normalized_inputs_and_output);
 168             liveness::generate(&mut cx, body, elements, flow_inits, move_data, location_table);
 169
 170             translate_outlives_facts(cx.borrowck_context);
 171         },
 172     );
 173
 174     MirTypeckResults {
 175         constraints,
 176         universal_region_relations,
 177     }
 178 }
 179
 180 fn type_check_internal<'a, 'tcx, R>(
 181     infcx: &'a InferCtxt<'a, 'tcx>,
 182     mir_def_id: DefId,
 183     param_env: ty::ParamEnv<'tcx>,
 184     body: &'a Body<'tcx>,
 185     promoted: &'a IndexVec<Promoted, Body<'tcx>>,
 186     region_bound_pairs: &'a RegionBoundPairs<'tcx>,
 187     implicit_region_bound: ty::Region<'tcx>,
 188     borrowck_context: &'a mut BorrowCheckContext<'a, 'tcx>,
 189     universal_region_relations: &'a UniversalRegionRelations<'tcx>,
 190     mut extra: impl FnMut(&mut TypeChecker<'a, 'tcx>) -> R,
 191 ) -> R where {
 192     let mut checker = TypeChecker::new(
 193         infcx,
 194         body,
 195         mir_def_id,
 196         param_env,
 197         region_bound_pairs,
 198         implicit_region_bound,
 199         borrowck_context,
 200         universal_region_relations,
 201     );
 202     let errors_reported = {
 203         let mut verifier = TypeVerifier::new(&mut checker, body, promoted);
 204         verifier.visit_body(body);
 205         verifier.errors_reported
 206     };
 207
 208     if !errors_reported {
 209         // if verifier failed, don't do further checks to avoid ICEs
 210         checker.typeck_mir(body);
 211     }
 212
 213     extra(&mut checker)
 214 }
 215
 216 fn translate_outlives_facts(cx: &mut BorrowCheckContext<'_, '_>) {
 217     if let Some(facts) = cx.all_facts {
 218         let location_table = cx.location_table;
 219         facts
 220             .outlives
 221             .extend(cx.constraints.outlives_constraints.outlives().iter().flat_map(
 222                 |constraint: &OutlivesConstraint| {
 223                     if let Some(from_location) = constraint.locations.from_location() {
 224                         Either::Left(iter::once((
 225                             constraint.sup,
 226                             constraint.sub,
 227                             location_table.mid_index(from_location),
 228                         )))
 229                     } else {
 230                         Either::Right(
 231                             location_table
 232                                 .all_points()
 233                                 .map(move |location| (constraint.sup, constraint.sub, location)),
 234                         )
 235                     }
 236                 },
 237             ));
 238     }
 239 }
 240
 241 fn mirbug(tcx: TyCtxt<'_>, span: Span, msg: &str) {
 242     // We sometimes see MIR failures (notably predicate failures) due to
 243     // the fact that we check rvalue sized predicates here. So use `delay_span_bug`
 244     // to avoid reporting bugs in those cases.
 245     tcx.sess.diagnostic().delay_span_bug(span, msg);
 246 }
 247
 248 enum FieldAccessError {
 249     OutOfRange { field_count: usize },
 250 }
 251
 252 /// Verifies that MIR types are sane to not crash further checks.
 253 ///
 254 /// The sanitize_XYZ methods here take an MIR object and compute its
 255 /// type, calling `span_mirbug` and returning an error type if there
 256 /// is a problem.
 257 struct TypeVerifier<'a, 'b, 'tcx> {
 258     cx: &'a mut TypeChecker<'b, 'tcx>,
 259     body: &'b Body<'tcx>,
 260     promoted: &'b IndexVec<Promoted, Body<'tcx>>,
 261     last_span: Span,
 262     mir_def_id: DefId,
 263     errors_reported: bool,
 264 }
 265
 266 impl<'a, 'b, 'tcx> Visitor<'tcx> for TypeVerifier<'a, 'b, 'tcx> {
 267     fn visit_span(&mut self, span: &Span) {
 268         if !span.is_dummy() {
 269             self.last_span = *span;
 270         }
 271     }
 272
 273     fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, location: Location) {
 274         self.sanitize_place(place, location, context);
 275     }
 276
 277     fn visit_constant(&mut self, constant: &Constant<'tcx>, location: Location) {
 278         self.super_constant(constant, location);
 279         self.sanitize_type(constant, constant.literal.ty);
 280
 281         if let Some(annotation_index) = constant.user_ty {
 282             if let Err(terr) = self.cx.relate_type_and_user_type(
 283                 constant.literal.ty,
 284                 ty::Variance::Invariant,
 285                 &UserTypeProjection { base: annotation_index, projs: vec![], },
 286                 location.to_locations(),
 287                 ConstraintCategory::Boring,
 288             ) {
 289                 let annotation = &self.cx.user_type_annotations[annotation_index];
 290                 span_mirbug!(
 291                     self,
 292                     constant,
 293                     "bad constant user type {:?} vs {:?}: {:?}",
 294                     annotation,
 295                     constant.literal.ty,
 296                     terr,
 297                 );
 298             }
 299         } else {
 300             if let ConstValue::Unevaluated(def_id, substs) = constant.literal.val {
 301                 if let Err(terr) = self.cx.fully_perform_op(
 302                     location.to_locations(),
 303                     ConstraintCategory::Boring,
 304                     self.cx.param_env.and(type_op::ascribe_user_type::AscribeUserType::new(
 305                         constant.literal.ty, def_id, UserSubsts { substs, user_self_ty: None },
 306                     )),
 307                 ) {
 308                     span_mirbug!(
 309                         self,
 310                         constant,
 311                         "bad constant type {:?} ({:?})",
 312                         constant,
 313                         terr
 314                     );
 315                 }
 316             }
 317             if let ty::FnDef(def_id, substs) = constant.literal.ty.sty {
 318                 let tcx = self.tcx();
 319
 320                 let instantiated_predicates = tcx
 321                     .predicates_of(def_id)
 322                     .instantiate(tcx, substs);
 323                 self.cx.normalize_and_prove_instantiated_predicates(
 324                     instantiated_predicates,
 325                     location.to_locations(),
 326                 );
 327             }
 328         }
 329     }
 330
 331     fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) {
 332         self.super_rvalue(rvalue, location);
 333         let rval_ty = rvalue.ty(self.body, self.tcx());
 334         self.sanitize_type(rvalue, rval_ty);
 335     }
 336
 337     fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
 338         self.super_local_decl(local, local_decl);
 339         self.sanitize_type(local_decl, local_decl.ty);
 340
 341         for (user_ty, span) in local_decl.user_ty.projections_and_spans() {
 342             let ty = if !local_decl.is_nonref_binding() {
 343                 // If we have a binding of the form `let ref x: T = ..` then remove the outermost
 344                 // reference so we can check the type annotation for the remaining type.
 345                 if let ty::Ref(_, rty, _) = local_decl.ty.sty {
 346                     rty
 347                 } else {
 348                     bug!("{:?} with ref binding has wrong type {}", local, local_decl.ty);
 349                 }
 350             } else {
 351                 local_decl.ty
 352             };
 353
 354             if let Err(terr) = self.cx.relate_type_and_user_type(
 355                 ty,
 356                 ty::Variance::Invariant,
 357                 user_ty,
 358                 Locations::All(*span),
 359                 ConstraintCategory::TypeAnnotation,
 360             ) {
 361                 span_mirbug!(
 362                     self,
 363                     local,
 364                     "bad user type on variable {:?}: {:?} != {:?} ({:?})",
 365                     local,
 366                     local_decl.ty,
 367                     local_decl.user_ty,
 368                     terr,
 369                 );
 370             }
 371         }
 372     }
 373
 374     fn visit_body(&mut self, body: &Body<'tcx>) {
 375         self.sanitize_type(&"return type", body.return_ty());
 376         for local_decl in &body.local_decls {
 377             self.sanitize_type(local_decl, local_decl.ty);
 378         }
 379         if self.errors_reported {
 380             return;
 381         }
 382         self.super_body(body);
 383     }
 384 }
 385
 386 impl<'a, 'b, 'tcx> TypeVerifier<'a, 'b, 'tcx> {
 387     fn new(cx: &'a mut TypeChecker<'b, 'tcx>, body: &'b Body<'tcx>, promoted: &'b IndexVec<Promoted, Body<'tcx>>) -> Self {
 388         TypeVerifier {
 389             body,
 390             promoted,
 391             mir_def_id: cx.mir_def_id,
 392             cx,
 393             last_span: body.span,
 394             errors_reported: false,
 395         }
 396     }
 397
 398     fn tcx(&self) -> TyCtxt<'tcx> {
 399         self.cx.infcx.tcx
 400     }
 401
 402     fn sanitize_type(&mut self, parent: &dyn fmt::Debug, ty: Ty<'tcx>) -> Ty<'tcx> {
 403         if ty.has_escaping_bound_vars() || ty.references_error() {
 404             span_mirbug_and_err!(self, parent, "bad type {:?}", ty)
 405         } else {
 406             ty
 407         }
 408     }
 409
 410     /// Checks that the types internal to the `place` match up with
 411     /// what would be expected.
 412     fn sanitize_place(
 413         &mut self,
 414         place: &Place<'tcx>,
 415         location: Location,
 416         context: PlaceContext,
 417     ) -> PlaceTy<'tcx> {
 418         debug!("sanitize_place: {:?}", place);
 419
 420         place.iterate(|place_base, place_projection| {
 421             let mut place_ty = match place_base {
 422                 PlaceBase::Local(index) =>
 423                     PlaceTy::from_ty(self.body.local_decls[*index].ty),
 424                 PlaceBase::Static(box Static { kind, ty: sty }) => {
 425                     let sty = self.sanitize_type(place, sty);
 426                     let check_err =
 427                         |verifier: &mut TypeVerifier<'a, 'b, 'tcx>,
 428                          place: &Place<'tcx>,
 429                          ty,
 430                          sty| {
 431                             if let Err(terr) = verifier.cx.eq_types(
 432                                 sty,
 433                                 ty,
 434                                 location.to_locations(),
 435                                 ConstraintCategory::Boring,
 436                             ) {
 437                                 span_mirbug!(
 438                                 verifier,
 439                                 place,
 440                                 "bad promoted type ({:?}: {:?}): {:?}",
 441                                 ty,
 442                                 sty,
 443                                 terr
 444                             );
 445                             };
 446                         };
 447                     match kind {
 448                         StaticKind::Promoted(promoted) => {
 449                             if !self.errors_reported {
 450                                 let promoted_body = &self.promoted[*promoted];
 451                                 self.sanitize_promoted(promoted_body, location);
 452
 453                                 let promoted_ty = promoted_body.return_ty();
 454                                 check_err(self, place, promoted_ty, sty);
 455                             }
 456                         }
 457                         StaticKind::Static(def_id) => {
 458                             let ty = self.tcx().type_of(*def_id);
 459                             let ty = self.cx.normalize(ty, location);
 460
 461                             check_err(self, place, ty, sty);
 462                         }
 463                     }
 464                     PlaceTy::from_ty(sty)
 465                 }
 466             };
 467
 468             // FIXME use place_projection.is_empty() when is available
 469             if place.projection.is_none() {
 470                 if let PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) = context {
 471                     let is_promoted = match place {
 472                         Place {
 473                             base: PlaceBase::Static(box Static {
 474                                 kind: StaticKind::Promoted(_),
 475                                 ..
 476                             }),
 477                             projection: None,
 478                         } => true,
 479                         _ => false,
 480                     };
 481
 482                     if !is_promoted {
 483                         let tcx = self.tcx();
 484                         let trait_ref = ty::TraitRef {
 485                             def_id: tcx.lang_items().copy_trait().unwrap(),
 486                             substs: tcx.mk_substs_trait(place_ty.ty, &[]),
 487                         };
 488
 489                         // In order to have a Copy operand, the type T of the
 490                         // value must be Copy. Note that we prove that T: Copy,
 491                         // rather than using the `is_copy_modulo_regions`
 492                         // test. This is important because
 493                         // `is_copy_modulo_regions` ignores the resulting region
 494                         // obligations and assumes they pass. This can result in
 495                         // bounds from Copy impls being unsoundly ignored (e.g.,
 496                         // #29149). Note that we decide to use Copy before knowing
 497                         // whether the bounds fully apply: in effect, the rule is
 498                         // that if a value of some type could implement Copy, then
 499                         // it must.
 500                         self.cx.prove_trait_ref(
 501                             trait_ref,
 502                             location.to_locations(),
 503                             ConstraintCategory::CopyBound,
 504                         );
 505                     }
 506                 }
 507             }
 508
 509             for proj in place_projection {
 510                 if place_ty.variant_index.is_none() {
 511                     if place_ty.ty.references_error() {
 512                         assert!(self.errors_reported);
 513                         return PlaceTy::from_ty(self.tcx().types.err);
 514                     }
 515                 }
 516                 place_ty = self.sanitize_projection(place_ty, &proj.elem, place, location)
 517             }
 518
 519             place_ty
 520         })
 521     }
 522
 523     fn sanitize_promoted(&mut self, promoted_body: &'b Body<'tcx>, location: Location) {
 524         // Determine the constraints from the promoted MIR by running the type
 525         // checker on the promoted MIR, then transfer the constraints back to
 526         // the main MIR, changing the locations to the provided location.
 527
 528         let parent_body = mem::replace(&mut self.body, promoted_body);
 529
 530         let all_facts = &mut None;
 531         let mut constraints = Default::default();
 532         let mut closure_bounds = Default::default();
 533         // Don't try to add borrow_region facts for the promoted MIR
 534         mem::swap(self.cx.borrowck_context.all_facts, all_facts);
 535
 536         // Use a new sets of constraints and closure bounds so that we can
 537         // modify their locations.
 538         mem::swap(
 539             &mut self.cx.borrowck_context.constraints.outlives_constraints,
 540             &mut constraints
 541         );
 542         mem::swap(
 543             &mut self.cx.borrowck_context.constraints.closure_bounds_mapping,
 544             &mut closure_bounds
 545         );
 546
 547         self.visit_body(promoted_body);
 548
 549         if !self.errors_reported {
 550             // if verifier failed, don't do further checks to avoid ICEs
 551             self.cx.typeck_mir(promoted_body);
 552         }
 553
 554         self.body = parent_body;
 555         // Merge the outlives constraints back in, at the given location.
 556         mem::swap(self.cx.borrowck_context.all_facts, all_facts);
 557         mem::swap(
 558             &mut self.cx.borrowck_context.constraints.outlives_constraints,
 559             &mut constraints
 560         );
 561         mem::swap(
 562             &mut self.cx.borrowck_context.constraints.closure_bounds_mapping,
 563             &mut closure_bounds
 564         );
 565
 566         let locations = location.to_locations();
 567         for constraint in constraints.outlives().iter() {
 568             let mut constraint = *constraint;
 569             constraint.locations = locations;
 570             if let ConstraintCategory::Return
 571                 | ConstraintCategory::UseAsConst
 572                 | ConstraintCategory::UseAsStatic = constraint.category
 573             {
 574                 // "Returning" from a promoted is an assigment to a
 575                 // temporary from the user's point of view.
 576                 constraint.category = ConstraintCategory::Boring;
 577             }
 578             self.cx.borrowck_context.constraints.outlives_constraints.push(constraint)
 579         }
 580
 581         if !closure_bounds.is_empty() {
 582             let combined_bounds_mapping = closure_bounds
 583                 .into_iter()
 584                 .flat_map(|(_, value)| value)
 585                 .collect();
 586             let existing = self.cx.borrowck_context
 587                 .constraints
 588                 .closure_bounds_mapping
 589                 .insert(location, combined_bounds_mapping);
 590             assert!(
 591                 existing.is_none(),
 592                 "Multiple promoteds/closures at the same location."
 593             );
 594         }
 595     }
 596
 597     fn sanitize_projection(
 598         &mut self,
 599         base: PlaceTy<'tcx>,
 600         pi: &PlaceElem<'tcx>,
 601         place: &Place<'tcx>,
 602         location: Location,
 603     ) -> PlaceTy<'tcx> {
 604         debug!("sanitize_projection: {:?} {:?} {:?}", base, pi, place);
 605         let tcx = self.tcx();
 606         let base_ty = base.ty;
 607         match *pi {
 608             ProjectionElem::Deref => {
 609                 let deref_ty = base_ty.builtin_deref(true);
 610                 PlaceTy::from_ty(
 611                     deref_ty.map(|t| t.ty).unwrap_or_else(|| {
 612                         span_mirbug_and_err!(self, place, "deref of non-pointer {:?}", base_ty)
 613                     })
 614                 )
 615             }
 616             ProjectionElem::Index(i) => {
 617                 let index_ty = Place::from(i).ty(self.body, tcx).ty;
 618                 if index_ty != tcx.types.usize {
 619                     PlaceTy::from_ty(
 620                         span_mirbug_and_err!(self, i, "index by non-usize {:?}", i),
 621                     )
 622                 } else {
 623                     PlaceTy::from_ty(
 624                         base_ty.builtin_index().unwrap_or_else(|| {
 625                             span_mirbug_and_err!(self, place, "index of non-array {:?}", base_ty)
 626                         }),
 627                     )
 628                 }
 629             }
 630             ProjectionElem::ConstantIndex { .. } => {
 631                 // consider verifying in-bounds
 632                 PlaceTy::from_ty(
 633                     base_ty.builtin_index().unwrap_or_else(|| {
 634                         span_mirbug_and_err!(self, place, "index of non-array {:?}", base_ty)
 635                     }),
 636                 )
 637             }
 638             ProjectionElem::Subslice { from, to } => PlaceTy::from_ty(
 639                 match base_ty.sty {
 640                     ty::Array(inner, size) => {
 641                         let size = size.eval_usize(tcx, self.cx.param_env);
 642                         let min_size = (from as u64) + (to as u64);
 643                         if let Some(rest_size) = size.checked_sub(min_size) {
 644                             tcx.mk_array(inner, rest_size)
 645                         } else {
 646                             span_mirbug_and_err!(
 647                                 self,
 648                                 place,
 649                                 "taking too-small slice of {:?}",
 650                                 base_ty
 651                             )
 652                         }
 653                     }
 654                     ty::Slice(..) => base_ty,
 655                     _ => span_mirbug_and_err!(self, place, "slice of non-array {:?}", base_ty),
 656                 },
 657             ),
 658             ProjectionElem::Downcast(maybe_name, index) => match base_ty.sty {
 659                 ty::Adt(adt_def, _substs) if adt_def.is_enum() => {
 660                     if index.as_usize() >= adt_def.variants.len() {
 661                         PlaceTy::from_ty(
 662                             span_mirbug_and_err!(
 663                                 self,
 664                                 place,
 665                                 "cast to variant #{:?} but enum only has {:?}",
 666                                 index,
 667                                 adt_def.variants.len()
 668                             ),
 669                         )
 670                     } else {
 671                         PlaceTy {
 672                             ty: base_ty,
 673                             variant_index: Some(index),
 674                         }
 675                     }
 676                 }
 677                 // We do not need to handle generators here, because this runs
 678                 // before the generator transform stage.
 679                 _ => {
 680                     let ty = if let Some(name) = maybe_name {
 681                         span_mirbug_and_err!(
 682                             self,
 683                             place,
 684                             "can't downcast {:?} as {:?}",
 685                             base_ty,
 686                             name
 687                         )
 688                     } else {
 689                         span_mirbug_and_err!(self, place, "can't downcast {:?}", base_ty)
 690                     };
 691                     PlaceTy::from_ty(ty)
 692                 },
 693             },
 694             ProjectionElem::Field(field, fty) => {
 695                 let fty = self.sanitize_type(place, fty);
 696                 match self.field_ty(place, base, field, location) {
 697                     Ok(ty) => if let Err(terr) = self.cx.eq_types(
 698                         ty,
 699                         fty,
 700                         location.to_locations(),
 701                         ConstraintCategory::Boring,
 702                     ) {
 703                         span_mirbug!(
 704                             self,
 705                             place,
 706                             "bad field access ({:?}: {:?}): {:?}",
 707                             ty,
 708                             fty,
 709                             terr
 710                         );
 711                     },
 712                     Err(FieldAccessError::OutOfRange { field_count }) => span_mirbug!(
 713                         self,
 714                         place,
 715                         "accessed field #{} but variant only has {}",
 716                         field.index(),
 717                         field_count
 718                     ),
 719                 }
 720                 PlaceTy::from_ty(fty)
 721             }
 722         }
 723     }
 724
 725     fn error(&mut self) -> Ty<'tcx> {
 726         self.errors_reported = true;
 727         self.tcx().types.err
 728     }
 729
 730     fn field_ty(
 731         &mut self,
 732         parent: &dyn fmt::Debug,
 733         base_ty: PlaceTy<'tcx>,
 734         field: Field,
 735         location: Location,
 736     ) -> Result<Ty<'tcx>, FieldAccessError> {
 737         let tcx = self.tcx();
 738
 739         let (variant, substs) = match base_ty {
 740             PlaceTy { ty, variant_index: Some(variant_index) } => match ty.sty {
 741                 ty::Adt(adt_def, substs) => (&adt_def.variants[variant_index], substs),
 742                 ty::Generator(def_id, substs, _) => {
 743                     let mut variants = substs.state_tys(def_id, tcx);
 744                     let mut variant = match variants.nth(variant_index.into()) {
 745                         Some(v) => v,
 746                         None => {
 747                             bug!("variant_index of generator out of range: {:?}/{:?}",
 748                                  variant_index,
 749                                  substs.state_tys(def_id, tcx).count())
 750                         }
 751                     };
 752                     return match variant.nth(field.index()) {
 753                         Some(ty) => Ok(ty),
 754                         None => Err(FieldAccessError::OutOfRange {
 755                             field_count: variant.count(),
 756                         }),
 757                     }
 758                 }
 759                 _ => bug!("can't have downcast of non-adt non-generator type"),
 760             }
 761             PlaceTy { ty, variant_index: None } => match ty.sty {
 762                 ty::Adt(adt_def, substs) if !adt_def.is_enum() =>
 763                     (&adt_def.variants[VariantIdx::new(0)], substs),
 764                 ty::Closure(def_id, substs) => {
 765                     return match substs.upvar_tys(def_id, tcx).nth(field.index()) {
 766                         Some(ty) => Ok(ty),
 767                         None => Err(FieldAccessError::OutOfRange {
 768                             field_count: substs.upvar_tys(def_id, tcx).count(),
 769                         }),
 770                     }
 771                 }
 772                 ty::Generator(def_id, substs, _) => {
 773                     // Only prefix fields (upvars and current state) are
 774                     // accessible without a variant index.
 775                     return match substs.prefix_tys(def_id, tcx).nth(field.index()) {
 776                         Some(ty) => Ok(ty),
 777                         None => Err(FieldAccessError::OutOfRange {
 778                             field_count: substs.prefix_tys(def_id, tcx).count(),
 779                         }),
 780                     }
 781                 }
 782                 ty::Tuple(tys) => {
 783                     return match tys.get(field.index()) {
 784                         Some(&ty) => Ok(ty.expect_ty()),
 785                         None => Err(FieldAccessError::OutOfRange {
 786                             field_count: tys.len(),
 787                         }),
 788                     }
 789                 }
 790                 _ => {
 791                     return Ok(span_mirbug_and_err!(
 792                         self,
 793                         parent,
 794                         "can't project out of {:?}",
 795                         base_ty
 796                     ))
 797                 }
 798             },
 799         };
 800
 801         if let Some(field) = variant.fields.get(field.index()) {
 802             Ok(self.cx.normalize(&field.ty(tcx, substs), location))
 803         } else {
 804             Err(FieldAccessError::OutOfRange {
 805                 field_count: variant.fields.len(),
 806             })
 807         }
 808     }
 809 }
 810
 811 /// The MIR type checker. Visits the MIR and enforces all the
 812 /// constraints needed for it to be valid and well-typed. Along the
 813 /// way, it accrues region constraints -- these can later be used by
 814 /// NLL region checking.
 815 struct TypeChecker<'a, 'tcx> {
 816     infcx: &'a InferCtxt<'a, 'tcx>,
 817     param_env: ty::ParamEnv<'tcx>,
 818     last_span: Span,
 819     body: &'a Body<'tcx>,
 820     /// User type annotations are shared between the main MIR and the MIR of
 821     /// all of the promoted items.
 822     user_type_annotations: &'a CanonicalUserTypeAnnotations<'tcx>,
 823     mir_def_id: DefId,
 824     region_bound_pairs: &'a RegionBoundPairs<'tcx>,
 825     implicit_region_bound: ty::Region<'tcx>,
 826     reported_errors: FxHashSet<(Ty<'tcx>, Span)>,
 827     borrowck_context: &'a mut BorrowCheckContext<'a, 'tcx>,
 828     universal_region_relations: &'a UniversalRegionRelations<'tcx>,
 829 }
 830
 831 struct BorrowCheckContext<'a, 'tcx> {
 832     universal_regions: &'a UniversalRegions<'tcx>,
 833     location_table: &'a LocationTable,
 834     all_facts: &'a mut Option<AllFacts>,
 835     borrow_set: &'a BorrowSet<'tcx>,
 836     constraints: &'a mut MirTypeckRegionConstraints<'tcx>,
 837 }
 838
 839 crate struct MirTypeckResults<'tcx> {
 840     crate constraints: MirTypeckRegionConstraints<'tcx>,
 841     crate universal_region_relations: Rc<UniversalRegionRelations<'tcx>>,
 842 }
 843
 844 /// A collection of region constraints that must be satisfied for the
 845 /// program to be considered well-typed.
 846 crate struct MirTypeckRegionConstraints<'tcx> {
 847     /// Maps from a `ty::Placeholder` to the corresponding
 848     /// `PlaceholderIndex` bit that we will use for it.
 849     ///
 850     /// To keep everything in sync, do not insert this set
 851     /// directly. Instead, use the `placeholder_region` helper.
 852     crate placeholder_indices: PlaceholderIndices,
 853
 854     /// Each time we add a placeholder to `placeholder_indices`, we
 855     /// also create a corresponding "representative" region vid for
 856     /// that wraps it. This vector tracks those. This way, when we
 857     /// convert the same `ty::RePlaceholder(p)` twice, we can map to
 858     /// the same underlying `RegionVid`.
 859     crate placeholder_index_to_region: IndexVec<PlaceholderIndex, ty::Region<'tcx>>,
 860
 861     /// In general, the type-checker is not responsible for enforcing
 862     /// liveness constraints; this job falls to the region inferencer,
 863     /// which performs a liveness analysis. However, in some limited
 864     /// cases, the MIR type-checker creates temporary regions that do
 865     /// not otherwise appear in the MIR -- in particular, the
 866     /// late-bound regions that it instantiates at call-sites -- and
 867     /// hence it must report on their liveness constraints.
 868     crate liveness_constraints: LivenessValues<RegionVid>,
 869
 870     crate outlives_constraints: OutlivesConstraintSet,
 871
 872     crate member_constraints: MemberConstraintSet<'tcx, RegionVid>,
 873
 874     crate closure_bounds_mapping:
 875         FxHashMap<Location, FxHashMap<(RegionVid, RegionVid), (ConstraintCategory, Span)>>,
 876
 877     crate type_tests: Vec<TypeTest<'tcx>>,
 878 }
 879
 880 impl MirTypeckRegionConstraints<'tcx> {
 881     fn placeholder_region(
 882         &mut self,
 883         infcx: &InferCtxt<'_, 'tcx>,
 884         placeholder: ty::PlaceholderRegion,
 885     ) -> ty::Region<'tcx> {
 886         let placeholder_index = self.placeholder_indices.insert(placeholder);
 887         match self.placeholder_index_to_region.get(placeholder_index) {
 888             Some(&v) => v,
 889             None => {
 890                 let origin = NLLRegionVariableOrigin::Placeholder(placeholder);
 891                 let region = infcx.next_nll_region_var_in_universe(origin, placeholder.universe);
 892                 self.placeholder_index_to_region.push(region);
 893                 region
 894             }
 895         }
 896     }
 897 }
 898
 899 /// The `Locations` type summarizes *where* region constraints are
 900 /// required to hold. Normally, this is at a particular point which
 901 /// created the obligation, but for constraints that the user gave, we
 902 /// want the constraint to hold at all points.
 903 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 904 pub enum Locations {
 905     /// Indicates that a type constraint should always be true. This
 906     /// is particularly important in the new borrowck analysis for
 907     /// things like the type of the return slot. Consider this
 908     /// example:
 909     ///
 910     /// ```
 911     /// fn foo<'a>(x: &'a u32) -> &'a u32 {
 912     ///     let y = 22;
 913     ///     return &y; // error
 914     /// }
 915     /// ```
 916     ///
 917     /// Here, we wind up with the signature from the return type being
 918     /// something like `&'1 u32` where `'1` is a universal region. But
 919     /// the type of the return slot `_0` is something like `&'2 u32`
 920     /// where `'2` is an existential region variable. The type checker
 921     /// requires that `&'2 u32 = &'1 u32` -- but at what point? In the
 922     /// older NLL analysis, we required this only at the entry point
 923     /// to the function. By the nature of the constraints, this wound
 924     /// up propagating to all points reachable from start (because
 925     /// `'1` -- as a universal region -- is live everywhere). In the
 926     /// newer analysis, though, this doesn't work: `_0` is considered
 927     /// dead at the start (it has no usable value) and hence this type
 928     /// equality is basically a no-op. Then, later on, when we do `_0
 929     /// = &'3 y`, that region `'3` never winds up related to the
 930     /// universal region `'1` and hence no error occurs. Therefore, we
 931     /// use Locations::All instead, which ensures that the `'1` and
 932     /// `'2` are equal everything. We also use this for other
 933     /// user-given type annotations; e.g., if the user wrote `let mut
 934     /// x: &'static u32 = ...`, we would ensure that all values
 935     /// assigned to `x` are of `'static` lifetime.
 936     ///
 937     /// The span points to the place the constraint arose. For example,
 938     /// it points to the type in a user-given type annotation. If
 939     /// there's no sensible span then it's DUMMY_SP.
 940     All(Span),
 941
 942     /// An outlives constraint that only has to hold at a single location,
 943     /// usually it represents a point where references flow from one spot to
 944     /// another (e.g., `x = y`)
 945     Single(Location),
 946 }
 947
 948 impl Locations {
 949     pub fn from_location(&self) -> Option<Location> {
 950         match self {
 951             Locations::All(_) => None,
 952             Locations::Single(from_location) => Some(*from_location),
 953         }
 954     }
 955
 956     /// Gets a span representing the location.
 957     pub fn span(&self, body: &Body<'_>) -> Span {
 958         match self {
 959             Locations::All(span) => *span,
 960             Locations::Single(l) => body.source_info(*l).span,
 961         }
 962     }
 963 }
 964
 965 impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
 966     fn new(
 967         infcx: &'a InferCtxt<'a, 'tcx>,
 968         body: &'a Body<'tcx>,
 969         mir_def_id: DefId,
 970         param_env: ty::ParamEnv<'tcx>,
 971         region_bound_pairs: &'a RegionBoundPairs<'tcx>,
 972         implicit_region_bound: ty::Region<'tcx>,
 973         borrowck_context: &'a mut BorrowCheckContext<'a, 'tcx>,
 974         universal_region_relations: &'a UniversalRegionRelations<'tcx>,
 975     ) -> Self {
 976         let mut checker = Self {
 977             infcx,
 978             last_span: DUMMY_SP,
 979             mir_def_id,
 980             body,
 981             user_type_annotations: &body.user_type_annotations,
 982             param_env,
 983             region_bound_pairs,
 984             implicit_region_bound,
 985             borrowck_context,
 986             reported_errors: Default::default(),
 987             universal_region_relations,
 988         };
 989         checker.check_user_type_annotations();
 990         checker
 991     }
 992
 993     /// Equate the inferred type and the annotated type for user type annotations
 994     fn check_user_type_annotations(&mut self) {
 995         debug!(
 996             "check_user_type_annotations: user_type_annotations={:?}",
 997              self.user_type_annotations
 998         );
 999         for user_annotation in self.user_type_annotations {
1000             let CanonicalUserTypeAnnotation { span, ref user_ty, inferred_ty } = *user_annotation;
1001             let (annotation, _) = self.infcx.instantiate_canonical_with_fresh_inference_vars(
1002                 span, user_ty
1003             );
1004             match annotation {
1005                 UserType::Ty(mut ty) => {
1006                     ty = self.normalize(ty, Locations::All(span));
1007
1008                     if let Err(terr) = self.eq_types(
1009                         ty,
1010                         inferred_ty,
1011                         Locations::All(span),
1012                         ConstraintCategory::BoringNoLocation,
1013                     ) {
1014                         span_mirbug!(
1015                             self,
1016                             user_annotation,
1017                             "bad user type ({:?} = {:?}): {:?}",
1018                             ty,
1019                             inferred_ty,
1020                             terr
1021                         );
1022                     }
1023
1024                     self.prove_predicate(
1025                         ty::Predicate::WellFormed(inferred_ty),
1026                         Locations::All(span),
1027                         ConstraintCategory::TypeAnnotation,
1028                     );
1029                 },
1030                 UserType::TypeOf(def_id, user_substs) => {
1031                     if let Err(terr) = self.fully_perform_op(
1032                         Locations::All(span),
1033                         ConstraintCategory::BoringNoLocation,
1034                         self.param_env.and(type_op::ascribe_user_type::AscribeUserType::new(
1035                             inferred_ty, def_id, user_substs,
1036                         )),
1037                     ) {
1038                         span_mirbug!(
1039                             self,
1040                             user_annotation,
1041                             "bad user type AscribeUserType({:?}, {:?} {:?}): {:?}",
1042                             inferred_ty,
1043                             def_id,
1044                             user_substs,
1045                             terr
1046                         );
1047                     }
1048                 },
1049             }
1050         }
1051     }
1052
1053     /// Given some operation `op` that manipulates types, proves
1054     /// predicates, or otherwise uses the inference context, executes
1055     /// `op` and then executes all the further obligations that `op`
1056     /// returns. This will yield a set of outlives constraints amongst
1057     /// regions which are extracted and stored as having occurred at
1058     /// `locations`.
1059     ///
1060     /// **Any `rustc::infer` operations that might generate region
1061     /// constraints should occur within this method so that those
1062     /// constraints can be properly localized!**
1063     fn fully_perform_op<R>(
1064         &mut self,
1065         locations: Locations,
1066         category: ConstraintCategory,
1067         op: impl type_op::TypeOp<'tcx, Output = R>,
1068     ) -> Fallible<R> {
1069         let (r, opt_data) = op.fully_perform(self.infcx)?;
1070
1071         if let Some(data) = &opt_data {
1072             self.push_region_constraints(locations, category, data);
1073         }
1074
1075         Ok(r)
1076     }
1077
1078     fn push_region_constraints(
1079         &mut self,
1080         locations: Locations,
1081         category: ConstraintCategory,
1082         data: &QueryRegionConstraints<'tcx>,
1083     ) {
1084         debug!(
1085             "push_region_constraints: constraints generated at {:?} are {:#?}",
1086             locations, data
1087         );
1088
1089         constraint_conversion::ConstraintConversion::new(
1090             self.infcx,
1091             self.borrowck_context.universal_regions,
1092             self.region_bound_pairs,
1093             Some(self.implicit_region_bound),
1094             self.param_env,
1095             locations,
1096             category,
1097             &mut self.borrowck_context.constraints,
1098         ).convert_all(data);
1099     }
1100
1101     /// Convenient wrapper around `relate_tys::relate_types` -- see
1102     /// that fn for docs.
1103     fn relate_types(
1104         &mut self,
1105         a: Ty<'tcx>,
1106         v: ty::Variance,
1107         b: Ty<'tcx>,
1108         locations: Locations,
1109         category: ConstraintCategory,
1110     ) -> Fallible<()> {
1111         relate_tys::relate_types(
1112             self.infcx,
1113             a,
1114             v,
1115             b,
1116             locations,
1117             category,
1118             Some(self.borrowck_context),
1119         )
1120     }
1121
1122     fn sub_types(
1123         &mut self,
1124         sub: Ty<'tcx>,
1125         sup: Ty<'tcx>,
1126         locations: Locations,
1127         category: ConstraintCategory,
1128     ) -> Fallible<()> {
1129         self.relate_types(sub, ty::Variance::Covariant, sup, locations, category)
1130     }
1131
1132     /// Try to relate `sub <: sup`; if this fails, instantiate opaque
1133     /// variables in `sub` with their inferred definitions and try
1134     /// again. This is used for opaque types in places (e.g., `let x:
1135     /// impl Foo = ..`).
1136     fn sub_types_or_anon(
1137         &mut self,
1138         sub: Ty<'tcx>,
1139         sup: Ty<'tcx>,
1140         locations: Locations,
1141         category: ConstraintCategory,
1142     ) -> Fallible<()> {
1143         if let Err(terr) = self.sub_types(sub, sup, locations, category) {
1144             if let ty::Opaque(..) = sup.sty {
1145                 // When you have `let x: impl Foo = ...` in a closure,
1146                 // the resulting inferend values are stored with the
1147                 // def-id of the base function.
1148                 let parent_def_id = self.tcx().closure_base_def_id(self.mir_def_id);
1149                 return self.eq_opaque_type_and_type(sub, sup, parent_def_id, locations, category);
1150             } else {
1151                 return Err(terr);
1152             }
1153         }
1154         Ok(())
1155     }
1156
1157     fn eq_types(
1158         &mut self,
1159         a: Ty<'tcx>,
1160         b: Ty<'tcx>,
1161         locations: Locations,
1162         category: ConstraintCategory,
1163     ) -> Fallible<()> {
1164         self.relate_types(a, ty::Variance::Invariant, b, locations, category)
1165     }
1166
1167     fn relate_type_and_user_type(
1168         &mut self,
1169         a: Ty<'tcx>,
1170         v: ty::Variance,
1171         user_ty: &UserTypeProjection,
1172         locations: Locations,
1173         category: ConstraintCategory,
1174     ) -> Fallible<()> {
1175         debug!(
1176             "relate_type_and_user_type(a={:?}, v={:?}, user_ty={:?}, locations={:?})",
1177             a, v, user_ty, locations,
1178         );
1179
1180         let annotated_type = self.user_type_annotations[user_ty.base].inferred_ty;
1181         let mut curr_projected_ty = PlaceTy::from_ty(annotated_type);
1182
1183         let tcx = self.infcx.tcx;
1184
1185         for proj in &user_ty.projs {
1186             let projected_ty = curr_projected_ty.projection_ty_core(
1187                 tcx,
1188                 self.param_env,
1189                 proj,
1190                 |this, field, &()| {
1191                     let ty = this.field_ty(tcx, field);
1192                     self.normalize(ty, locations)
1193                 },
1194             );
1195             curr_projected_ty = projected_ty;
1196         }
1197         debug!("user_ty base: {:?} freshened: {:?} projs: {:?} yields: {:?}",
1198                 user_ty.base, annotated_type, user_ty.projs, curr_projected_ty);
1199
1200         let ty = curr_projected_ty.ty;
1201         self.relate_types(a, v, ty, locations, category)?;
1202
1203         Ok(())
1204     }
1205
1206     fn eq_opaque_type_and_type(
1207         &mut self,
1208         revealed_ty: Ty<'tcx>,
1209         anon_ty: Ty<'tcx>,
1210         anon_owner_def_id: DefId,
1211         locations: Locations,
1212         category: ConstraintCategory,
1213     ) -> Fallible<()> {
1214         debug!(
1215             "eq_opaque_type_and_type( \
1216              revealed_ty={:?}, \
1217              anon_ty={:?})",
1218             revealed_ty, anon_ty
1219         );
1220         let infcx = self.infcx;
1221         let tcx = infcx.tcx;
1222         let param_env = self.param_env;
1223         let body = self.body;
1224         debug!("eq_opaque_type_and_type: mir_def_id={:?}", self.mir_def_id);
1225         let opaque_type_map = self.fully_perform_op(
1226             locations,
1227             category,
1228             CustomTypeOp::new(
1229                 |infcx| {
1230                     let mut obligations = ObligationAccumulator::default();
1231
1232                     let dummy_body_id = ObligationCause::dummy().body_id;
1233                     let (output_ty, opaque_type_map) =
1234                         obligations.add(infcx.instantiate_opaque_types(
1235                             anon_owner_def_id,
1236                             dummy_body_id,
1237                             param_env,
1238                             &anon_ty,
1239                             locations.span(body),
1240                         ));
1241                     debug!(
1242                         "eq_opaque_type_and_type: \
1243                          instantiated output_ty={:?} \
1244                          opaque_type_map={:#?} \
1245                          revealed_ty={:?}",
1246                         output_ty, opaque_type_map, revealed_ty
1247                     );
1248                     obligations.add(infcx
1249                         .at(&ObligationCause::dummy(), param_env)
1250                         .eq(output_ty, revealed_ty)?);
1251
1252                     for (&opaque_def_id, opaque_decl) in &opaque_type_map {
1253                         let opaque_defn_ty = tcx.type_of(opaque_def_id);
1254                         let opaque_defn_ty = opaque_defn_ty.subst(tcx, opaque_decl.substs);
1255                         let opaque_defn_ty = renumber::renumber_regions(infcx, &opaque_defn_ty);
1256                         let concrete_is_opaque = infcx
1257                             .resolve_vars_if_possible(&opaque_decl.concrete_ty).is_impl_trait();
1258
1259                         debug!(
1260                             "eq_opaque_type_and_type: concrete_ty={:?}={:?} opaque_defn_ty={:?} \
1261                             concrete_is_opaque={}",
1262                             opaque_decl.concrete_ty,
1263                             infcx.resolve_vars_if_possible(&opaque_decl.concrete_ty),
1264                             opaque_defn_ty,
1265                             concrete_is_opaque
1266                         );
1267
1268                         // concrete_is_opaque is `true` when we're using an opaque `impl Trait`
1269                         // type without 'revealing' it. For example, code like this:
1270                         //
1271                         // type Foo = impl Debug;
1272                         // fn foo1() -> Foo { ... }
1273                         // fn foo2() -> Foo { foo1() }
1274                         //
1275                         // In `foo2`, we're not revealing the type of `Foo` - we're
1276                         // just treating it as the opaque type.
1277                         //
1278                         // When this occurs, we do *not* want to try to equate
1279                         // the concrete type with the underlying defining type
1280                         // of the opaque type - this will always fail, since
1281                         // the defining type of an opaque type is always
1282                         // some other type (e.g. not itself)
1283                         // Essentially, none of the normal obligations apply here -
1284                         // we're just passing around some unknown opaque type,
1285                         // without actually looking at the underlying type it
1286                         // gets 'revealed' into
1287
1288                         if !concrete_is_opaque {
1289                             obligations.add(infcx
1290                                 .at(&ObligationCause::dummy(), param_env)
1291                                 .eq(opaque_decl.concrete_ty, opaque_defn_ty)?);
1292                         }
1293                     }
1294
1295                     debug!("eq_opaque_type_and_type: equated");
1296
1297                     Ok(InferOk {
1298                         value: Some(opaque_type_map),
1299                         obligations: obligations.into_vec(),
1300                     })
1301                 },
1302                 || "input_output".to_string(),
1303             ),
1304         )?;
1305
1306         let universal_region_relations = self.universal_region_relations;
1307
1308         // Finally, if we instantiated the anon types successfully, we
1309         // have to solve any bounds (e.g., `-> impl Iterator` needs to
1310         // prove that `T: Iterator` where `T` is the type we
1311         // instantiated it with).
1312         if let Some(opaque_type_map) = opaque_type_map {
1313             for (opaque_def_id, opaque_decl) in opaque_type_map {
1314                 self.fully_perform_op(
1315                     locations,
1316                     ConstraintCategory::OpaqueType,
1317                     CustomTypeOp::new(
1318                         |_cx| {
1319                             infcx.constrain_opaque_type(
1320                                 opaque_def_id,
1321                                 &opaque_decl,
1322                                 universal_region_relations,
1323                             );
1324                             Ok(InferOk {
1325                                 value: (),
1326                                 obligations: vec![],
1327                             })
1328                         },
1329                         || "opaque_type_map".to_string(),
1330                     ),
1331                 )?;
1332             }
1333         }
1334         Ok(())
1335     }
1336
1337     fn tcx(&self) -> TyCtxt<'tcx> {
1338         self.infcx.tcx
1339     }
1340
1341     fn check_stmt(&mut self, body: &Body<'tcx>, stmt: &Statement<'tcx>, location: Location) {
1342         debug!("check_stmt: {:?}", stmt);
1343         let tcx = self.tcx();
1344         match stmt.kind {
1345             StatementKind::Assign(ref place, ref rv) => {
1346                 // Assignments to temporaries are not "interesting";
1347                 // they are not caused by the user, but rather artifacts
1348                 // of lowering. Assignments to other sorts of places *are* interesting
1349                 // though.
1350                 let category = match *place {
1351                     Place {
1352                         base: PlaceBase::Local(RETURN_PLACE),
1353                         projection: None,
1354                     } => if let BorrowCheckContext {
1355                         universal_regions:
1356                             UniversalRegions {
1357                                 defining_ty: DefiningTy::Const(def_id, _),
1358                                 ..
1359                             },
1360                         ..
1361                     } = self.borrowck_context {
1362                         if tcx.is_static(*def_id) {
1363                             ConstraintCategory::UseAsStatic
1364                         } else {
1365                             ConstraintCategory::UseAsConst
1366                         }
1367                     } else {
1368                         ConstraintCategory::Return
1369                     },
1370                     Place {
1371                         base: PlaceBase::Local(l),
1372                         projection: None,
1373                     } if !body.local_decls[l].is_user_variable.is_some() => {
1374                         ConstraintCategory::Boring
1375                     }
1376                     _ => ConstraintCategory::Assignment,
1377                 };
1378
1379                 let place_ty = place.ty(body, tcx).ty;
1380                 let rv_ty = rv.ty(body, tcx);
1381                 if let Err(terr) =
1382                     self.sub_types_or_anon(rv_ty, place_ty, location.to_locations(), category)
1383                 {
1384                     span_mirbug!(
1385                         self,
1386                         stmt,
1387                         "bad assignment ({:?} = {:?}): {:?}",
1388                         place_ty,
1389                         rv_ty,
1390                         terr
1391                     );
1392                 }
1393
1394                 if let Some(annotation_index) = self.rvalue_user_ty(rv) {
1395                     if let Err(terr) = self.relate_type_and_user_type(
1396                         rv_ty,
1397                         ty::Variance::Invariant,
1398                         &UserTypeProjection { base: annotation_index, projs: vec![], },
1399                         location.to_locations(),
1400                         ConstraintCategory::Boring,
1401                     ) {
1402                         let annotation = &self.user_type_annotations[annotation_index];
1403                         span_mirbug!(
1404                             self,
1405                             stmt,
1406                             "bad user type on rvalue ({:?} = {:?}): {:?}",
1407                             annotation,
1408                             rv_ty,
1409                             terr
1410                         );
1411                     }
1412                 }
1413
1414                 self.check_rvalue(body, rv, location);
1415                 if !self.tcx().features().unsized_locals {
1416                     let trait_ref = ty::TraitRef {
1417                         def_id: tcx.lang_items().sized_trait().unwrap(),
1418                         substs: tcx.mk_substs_trait(place_ty, &[]),
1419                     };
1420                     self.prove_trait_ref(
1421                         trait_ref,
1422                         location.to_locations(),
1423                         ConstraintCategory::SizedBound,
1424                     );
1425                 }
1426             }
1427             StatementKind::SetDiscriminant {
1428                 ref place,
1429                 variant_index,
1430             } => {
1431                 let place_type = place.ty(body, tcx).ty;
1432                 let adt = match place_type.sty {
1433                     ty::Adt(adt, _) if adt.is_enum() => adt,
1434                     _ => {
1435                         span_bug!(
1436                             stmt.source_info.span,
1437                             "bad set discriminant ({:?} = {:?}): lhs is not an enum",
1438                             place,
1439                             variant_index
1440                         );
1441                     }
1442                 };
1443                 if variant_index.as_usize() >= adt.variants.len() {
1444                     span_bug!(
1445                         stmt.source_info.span,
1446                         "bad set discriminant ({:?} = {:?}): value of of range",
1447                         place,
1448                         variant_index
1449                     );
1450                 };
1451             }
1452             StatementKind::AscribeUserType(ref place, variance, box ref projection) => {
1453                 let place_ty = place.ty(body, tcx).ty;
1454                 if let Err(terr) = self.relate_type_and_user_type(
1455                     place_ty,
1456                     variance,
1457                     projection,
1458                     Locations::All(stmt.source_info.span),
1459                     ConstraintCategory::TypeAnnotation,
1460                 ) {
1461                     let annotation = &self.user_type_annotations[projection.base];
1462                     span_mirbug!(
1463                         self,
1464                         stmt,
1465                         "bad type assert ({:?} <: {:?} with projections {:?}): {:?}",
1466                         place_ty,
1467                         annotation,
1468                         projection.projs,
1469                         terr
1470                     );
1471                 }
1472             }
1473             StatementKind::FakeRead(..)
1474             | StatementKind::StorageLive(..)
1475             | StatementKind::StorageDead(..)
1476             | StatementKind::InlineAsm { .. }
1477             | StatementKind::Retag { .. }
1478             | StatementKind::Nop => {}
1479         }
1480     }
1481
1482     fn check_terminator(
1483         &mut self,
1484         body: &Body<'tcx>,
1485         term: &Terminator<'tcx>,
1486         term_location: Location,
1487     ) {
1488         debug!("check_terminator: {:?}", term);
1489         let tcx = self.tcx();
1490         match term.kind {
1491             TerminatorKind::Goto { .. }
1492             | TerminatorKind::Resume
1493             | TerminatorKind::Abort
1494             | TerminatorKind::Return
1495             | TerminatorKind::GeneratorDrop
1496             | TerminatorKind::Unreachable
1497             | TerminatorKind::Drop { .. }
1498             | TerminatorKind::FalseEdges { .. }
1499             | TerminatorKind::FalseUnwind { .. } => {
1500                 // no checks needed for these
1501             }
1502
1503             TerminatorKind::DropAndReplace {
1504                 ref location,
1505                 ref value,
1506                 target: _,
1507                 unwind: _,
1508             } => {
1509                 let place_ty = location.ty(body, tcx).ty;
1510                 let rv_ty = value.ty(body, tcx);
1511
1512                 let locations = term_location.to_locations();
1513                 if let Err(terr) =
1514                     self.sub_types(rv_ty, place_ty, locations, ConstraintCategory::Assignment)
1515                 {
1516                     span_mirbug!(
1517                         self,
1518                         term,
1519                         "bad DropAndReplace ({:?} = {:?}): {:?}",
1520                         place_ty,
1521                         rv_ty,
1522                         terr
1523                     );
1524                 }
1525             }
1526             TerminatorKind::SwitchInt {
1527                 ref discr,
1528                 switch_ty,
1529                 ..
1530             } => {
1531                 let discr_ty = discr.ty(body, tcx);
1532                 if let Err(terr) = self.sub_types(
1533                     discr_ty,
1534                     switch_ty,
1535                     term_location.to_locations(),
1536                     ConstraintCategory::Assignment,
1537                 ) {
1538                     span_mirbug!(
1539                         self,
1540                         term,
1541                         "bad SwitchInt ({:?} on {:?}): {:?}",
1542                         switch_ty,
1543                         discr_ty,
1544                         terr
1545                     );
1546                 }
1547                 if !switch_ty.is_integral() && !switch_ty.is_char() && !switch_ty.is_bool() {
1548                     span_mirbug!(self, term, "bad SwitchInt discr ty {:?}", switch_ty);
1549                 }
1550                 // FIXME: check the values
1551             }
1552             TerminatorKind::Call {
1553                 ref func,
1554                 ref args,
1555                 ref destination,
1556                 from_hir_call,
1557                 ..
1558             } => {
1559                 let func_ty = func.ty(body, tcx);
1560                 debug!("check_terminator: call, func_ty={:?}", func_ty);
1561                 let sig = match func_ty.sty {
1562                     ty::FnDef(..) | ty::FnPtr(_) => func_ty.fn_sig(tcx),
1563                     _ => {
1564                         span_mirbug!(self, term, "call to non-function {:?}", func_ty);
1565                         return;
1566                     }
1567                 };
1568                 let (sig, map) = self.infcx.replace_bound_vars_with_fresh_vars(
1569                     term.source_info.span,
1570                     LateBoundRegionConversionTime::FnCall,
1571                     &sig,
1572                 );
1573                 let sig = self.normalize(sig, term_location);
1574                 self.check_call_dest(body, term, &sig, destination, term_location);
1575
1576                 self.prove_predicates(
1577                     sig.inputs_and_output.iter().map(|ty| ty::Predicate::WellFormed(ty)),
1578                     term_location.to_locations(),
1579                     ConstraintCategory::Boring,
1580                 );
1581
1582                 // The ordinary liveness rules will ensure that all
1583                 // regions in the type of the callee are live here. We
1584                 // then further constrain the late-bound regions that
1585                 // were instantiated at the call site to be live as
1586                 // well. The resulting is that all the input (and
1587                 // output) types in the signature must be live, since
1588                 // all the inputs that fed into it were live.
1589                 for &late_bound_region in map.values() {
1590                     let region_vid = self.borrowck_context
1591                         .universal_regions
1592                         .to_region_vid(late_bound_region);
1593                     self.borrowck_context
1594                         .constraints
1595                         .liveness_constraints
1596                         .add_element(region_vid, term_location);
1597                 }
1598
1599                 self.check_call_inputs(body, term, &sig, args, term_location, from_hir_call);
1600             }
1601             TerminatorKind::Assert {
1602                 ref cond, ref msg, ..
1603             } => {
1604                 let cond_ty = cond.ty(body, tcx);
1605                 if cond_ty != tcx.types.bool {
1606                     span_mirbug!(self, term, "bad Assert ({:?}, not bool", cond_ty);
1607                 }
1608
1609                 if let PanicInfo::BoundsCheck { ref len, ref index } = *msg {
1610                     if len.ty(body, tcx) != tcx.types.usize {
1611                         span_mirbug!(self, len, "bounds-check length non-usize {:?}", len)
1612                     }
1613                     if index.ty(body, tcx) != tcx.types.usize {
1614                         span_mirbug!(self, index, "bounds-check index non-usize {:?}", index)
1615                     }
1616                 }
1617             }
1618             TerminatorKind::Yield { ref value, .. } => {
1619                 let value_ty = value.ty(body, tcx);
1620                 match body.yield_ty {
1621                     None => span_mirbug!(self, term, "yield in non-generator"),
1622                     Some(ty) => {
1623                         if let Err(terr) = self.sub_types(
1624                             value_ty,
1625                             ty,
1626                             term_location.to_locations(),
1627                             ConstraintCategory::Yield,
1628                         ) {
1629                             span_mirbug!(
1630                                 self,
1631                                 term,
1632                                 "type of yield value is {:?}, but the yield type is {:?}: {:?}",
1633                                 value_ty,
1634                                 ty,
1635                                 terr
1636                             );
1637                         }
1638                     }
1639                 }
1640             }
1641         }
1642     }
1643
1644     fn check_call_dest(
1645         &mut self,
1646         body: &Body<'tcx>,
1647         term: &Terminator<'tcx>,
1648         sig: &ty::FnSig<'tcx>,
1649         destination: &Option<(Place<'tcx>, BasicBlock)>,
1650         term_location: Location,
1651     ) {
1652         let tcx = self.tcx();
1653         match *destination {
1654             Some((ref dest, _target_block)) => {
1655                 let dest_ty = dest.ty(body, tcx).ty;
1656                 let category = match *dest {
1657                     Place {
1658                         base: PlaceBase::Local(RETURN_PLACE),
1659                         projection: None,
1660                     } => {
1661                         if let BorrowCheckContext {
1662                             universal_regions:
1663                                 UniversalRegions {
1664                                     defining_ty: DefiningTy::Const(def_id, _),
1665                                     ..
1666                                 },
1667                             ..
1668                         } = self.borrowck_context
1669                         {
1670                             if tcx.is_static(*def_id) {
1671                                 ConstraintCategory::UseAsStatic
1672                             } else {
1673                                 ConstraintCategory::UseAsConst
1674                             }
1675                         } else {
1676                             ConstraintCategory::Return
1677                         }
1678                     }
1679                     Place {
1680                         base: PlaceBase::Local(l),
1681                         projection: None,
1682                     } if !body.local_decls[l].is_user_variable.is_some() => {
1683                         ConstraintCategory::Boring
1684                     }
1685                     _ => ConstraintCategory::Assignment,
1686                 };
1687
1688                 let locations = term_location.to_locations();
1689
1690                 if let Err(terr) =
1691                     self.sub_types_or_anon(sig.output(), dest_ty, locations, category)
1692                 {
1693                     span_mirbug!(
1694                         self,
1695                         term,
1696                         "call dest mismatch ({:?} <- {:?}): {:?}",
1697                         dest_ty,
1698                         sig.output(),
1699                         terr
1700                     );
1701                 }
1702
1703                 // When `#![feature(unsized_locals)]` is not enabled,
1704                 // this check is done at `check_local`.
1705                 if self.tcx().features().unsized_locals {
1706                     let span = term.source_info.span;
1707                     self.ensure_place_sized(dest_ty, span);
1708                 }
1709             }
1710             None => {
1711                 if !sig.output().conservative_is_privately_uninhabited(self.tcx()) {
1712                     span_mirbug!(self, term, "call to converging function {:?} w/o dest", sig);
1713                 }
1714             }
1715         }
1716     }
1717
1718     fn check_call_inputs(
1719         &mut self,
1720         body: &Body<'tcx>,
1721         term: &Terminator<'tcx>,
1722         sig: &ty::FnSig<'tcx>,
1723         args: &[Operand<'tcx>],
1724         term_location: Location,
1725         from_hir_call: bool,
1726     ) {
1727         debug!("check_call_inputs({:?}, {:?})", sig, args);
1728         // Do not count the `VaListImpl` argument as a "true" argument to
1729         // a C-variadic function.
1730         let inputs = if sig.c_variadic {
1731             &sig.inputs()[..sig.inputs().len() - 1]
1732         } else {
1733             &sig.inputs()[..]
1734         };
1735         if args.len() < inputs.len() || (args.len() > inputs.len() && !sig.c_variadic) {
1736             span_mirbug!(self, term, "call to {:?} with wrong # of args", sig);
1737         }
1738         for (n, (fn_arg, op_arg)) in inputs.iter().zip(args).enumerate() {
1739             let op_arg_ty = op_arg.ty(body, self.tcx());
1740             let category = if from_hir_call {
1741                 ConstraintCategory::CallArgument
1742             } else {
1743                 ConstraintCategory::Boring
1744             };
1745             if let Err(terr) =
1746                 self.sub_types(op_arg_ty, fn_arg, term_location.to_locations(), category)
1747             {
1748                 span_mirbug!(
1749                     self,
1750                     term,
1751                     "bad arg #{:?} ({:?} <- {:?}): {:?}",
1752                     n,
1753                     fn_arg,
1754                     op_arg_ty,
1755                     terr
1756                 );
1757             }
1758         }
1759     }
1760
1761     fn check_iscleanup(&mut self, body: &Body<'tcx>, block_data: &BasicBlockData<'tcx>) {
1762         let is_cleanup = block_data.is_cleanup;
1763         self.last_span = block_data.terminator().source_info.span;
1764         match block_data.terminator().kind {
1765             TerminatorKind::Goto { target } => {
1766                 self.assert_iscleanup(body, block_data, target, is_cleanup)
1767             }
1768             TerminatorKind::SwitchInt { ref targets, .. } => for target in targets {
1769                 self.assert_iscleanup(body, block_data, *target, is_cleanup);
1770             },
1771             TerminatorKind::Resume => if !is_cleanup {
1772                 span_mirbug!(self, block_data, "resume on non-cleanup block!")
1773             },
1774             TerminatorKind::Abort => if !is_cleanup {
1775                 span_mirbug!(self, block_data, "abort on non-cleanup block!")
1776             },
1777             TerminatorKind::Return => if is_cleanup {
1778                 span_mirbug!(self, block_data, "return on cleanup block")
1779             },
1780             TerminatorKind::GeneratorDrop { .. } => if is_cleanup {
1781                 span_mirbug!(self, block_data, "generator_drop in cleanup block")
1782             },
1783             TerminatorKind::Yield { resume, drop, .. } => {
1784                 if is_cleanup {
1785                     span_mirbug!(self, block_data, "yield in cleanup block")
1786                 }
1787                 self.assert_iscleanup(body, block_data, resume, is_cleanup);
1788                 if let Some(drop) = drop {
1789                     self.assert_iscleanup(body, block_data, drop, is_cleanup);
1790                 }
1791             }
1792             TerminatorKind::Unreachable => {}
1793             TerminatorKind::Drop { target, unwind, .. }
1794             | TerminatorKind::DropAndReplace { target, unwind, .. }
1795             | TerminatorKind::Assert {
1796                 target,
1797                 cleanup: unwind,
1798                 ..
1799             } => {
1800                 self.assert_iscleanup(body, block_data, target, is_cleanup);
1801                 if let Some(unwind) = unwind {
1802                     if is_cleanup {
1803                         span_mirbug!(self, block_data, "unwind on cleanup block")
1804                     }
1805                     self.assert_iscleanup(body, block_data, unwind, true);
1806                 }
1807             }
1808             TerminatorKind::Call {
1809                 ref destination,
1810                 cleanup,
1811                 ..
1812             } => {
1813                 if let &Some((_, target)) = destination {
1814                     self.assert_iscleanup(body, block_data, target, is_cleanup);
1815                 }
1816                 if let Some(cleanup) = cleanup {
1817                     if is_cleanup {
1818                         span_mirbug!(self, block_data, "cleanup on cleanup block")
1819                     }
1820                     self.assert_iscleanup(body, block_data, cleanup, true);
1821                 }
1822             }
1823             TerminatorKind::FalseEdges {
1824                 real_target,
1825                 imaginary_target,
1826             } => {
1827                 self.assert_iscleanup(body, block_data, real_target, is_cleanup);
1828                 self.assert_iscleanup(body, block_data, imaginary_target, is_cleanup);
1829             }
1830             TerminatorKind::FalseUnwind {
1831                 real_target,
1832                 unwind,
1833             } => {
1834                 self.assert_iscleanup(body, block_data, real_target, is_cleanup);
1835                 if let Some(unwind) = unwind {
1836                     if is_cleanup {
1837                         span_mirbug!(
1838                             self,
1839                             block_data,
1840                             "cleanup in cleanup block via false unwind"
1841                         );
1842                     }
1843                     self.assert_iscleanup(body, block_data, unwind, true);
1844                 }
1845             }
1846         }
1847     }
1848
1849     fn assert_iscleanup(
1850         &mut self,
1851         body: &Body<'tcx>,
1852         ctxt: &dyn fmt::Debug,
1853         bb: BasicBlock,
1854         iscleanuppad: bool,
1855     ) {
1856         if body[bb].is_cleanup != iscleanuppad {
1857             span_mirbug!(
1858                 self,
1859                 ctxt,
1860                 "cleanuppad mismatch: {:?} should be {:?}",
1861                 bb,
1862                 iscleanuppad
1863             );
1864         }
1865     }
1866
1867     fn check_local(&mut self, body: &Body<'tcx>, local: Local, local_decl: &LocalDecl<'tcx>) {
1868         match body.local_kind(local) {
1869             LocalKind::ReturnPointer | LocalKind::Arg => {
1870                 // return values of normal functions are required to be
1871                 // sized by typeck, but return values of ADT constructors are
1872                 // not because we don't include a `Self: Sized` bounds on them.
1873                 //
1874                 // Unbound parts of arguments were never required to be Sized
1875                 // - maybe we should make that a warning.
1876                 return;
1877             }
1878             LocalKind::Var | LocalKind::Temp => {}
1879         }
1880
1881         // When `#![feature(unsized_locals)]` is enabled, only function calls
1882         // and nullary ops are checked in `check_call_dest`.
1883         if !self.tcx().features().unsized_locals {
1884             let span = local_decl.source_info.span;
1885             let ty = local_decl.ty;
1886             self.ensure_place_sized(ty, span);
1887         }
1888     }
1889
1890     fn ensure_place_sized(&mut self, ty: Ty<'tcx>, span: Span) {
1891         let tcx = self.tcx();
1892
1893         // Erase the regions from `ty` to get a global type.  The
1894         // `Sized` bound in no way depends on precise regions, so this
1895         // shouldn't affect `is_sized`.
1896         let gcx = tcx.global_tcx();
1897         let erased_ty = tcx.erase_regions(&ty);
1898         if !erased_ty.is_sized(gcx.at(span), self.param_env) {
1899             // in current MIR construction, all non-control-flow rvalue
1900             // expressions evaluate through `as_temp` or `into` a return
1901             // slot or local, so to find all unsized rvalues it is enough
1902             // to check all temps, return slots and locals.
1903             if let None = self.reported_errors.replace((ty, span)) {
1904                 let mut diag = struct_span_err!(
1905                     self.tcx().sess,
1906                     span,
1907                     E0161,
1908                     "cannot move a value of type {0}: the size of {0} \
1909                      cannot be statically determined",
1910                     ty
1911                 );
1912
1913                 // While this is located in `nll::typeck` this error is not
1914                 // an NLL error, it's a required check to prevent creation
1915                 // of unsized rvalues in certain cases:
1916                 // * operand of a box expression
1917                 // * callee in a call expression
1918                 diag.emit();
1919             }
1920         }
1921     }
1922
1923     fn aggregate_field_ty(
1924         &mut self,
1925         ak: &AggregateKind<'tcx>,
1926         field_index: usize,
1927         location: Location,
1928     ) -> Result<Ty<'tcx>, FieldAccessError> {
1929         let tcx = self.tcx();
1930
1931         match *ak {
1932             AggregateKind::Adt(def, variant_index, substs, _, active_field_index) => {
1933                 let variant = &def.variants[variant_index];
1934                 let adj_field_index = active_field_index.unwrap_or(field_index);
1935                 if let Some(field) = variant.fields.get(adj_field_index) {
1936                     Ok(self.normalize(field.ty(tcx, substs), location))
1937                 } else {
1938                     Err(FieldAccessError::OutOfRange {
1939                         field_count: variant.fields.len(),
1940                     })
1941                 }
1942             }
1943             AggregateKind::Closure(def_id, substs) => {
1944                 match substs.upvar_tys(def_id, tcx).nth(field_index) {
1945                     Some(ty) => Ok(ty),
1946                     None => Err(FieldAccessError::OutOfRange {
1947                         field_count: substs.upvar_tys(def_id, tcx).count(),
1948                     }),
1949                 }
1950             }
1951             AggregateKind::Generator(def_id, substs, _) => {
1952                 // It doesn't make sense to look at a field beyond the prefix;
1953                 // these require a variant index, and are not initialized in
1954                 // aggregate rvalues.
1955                 match substs.prefix_tys(def_id, tcx).nth(field_index) {
1956                     Some(ty) => Ok(ty),
1957                     None => Err(FieldAccessError::OutOfRange {
1958                         field_count: substs.prefix_tys(def_id, tcx).count(),
1959                     }),
1960                 }
1961             }
1962             AggregateKind::Array(ty) => Ok(ty),
1963             AggregateKind::Tuple => {
1964                 unreachable!("This should have been covered in check_rvalues");
1965             }
1966         }
1967     }
1968
1969     fn check_rvalue(&mut self, body: &Body<'tcx>, rvalue: &Rvalue<'tcx>, location: Location) {
1970         let tcx = self.tcx();
1971
1972         match rvalue {
1973             Rvalue::Aggregate(ak, ops) => {
1974                 self.check_aggregate_rvalue(body, rvalue, ak, ops, location)
1975             }
1976
1977             Rvalue::Repeat(operand, len) => if *len > 1 {
1978                 if let Operand::Move(_) = operand {
1979                     // While this is located in `nll::typeck` this error is not an NLL error, it's
1980                     // a required check to make sure that repeated elements implement `Copy`.
1981                     let span = body.source_info(location).span;
1982                     let ty = operand.ty(body, tcx);
1983                     if !self.infcx.type_is_copy_modulo_regions(self.param_env, ty, span) {
1984                         self.infcx.report_selection_error(
1985                             &traits::Obligation::new(
1986                                 ObligationCause::new(
1987                                     span,
1988                                     self.tcx().hir().def_index_to_hir_id(self.mir_def_id.index),
1989                                     traits::ObligationCauseCode::RepeatVec,
1990                                 ),
1991                                 self.param_env,
1992                                 ty::Predicate::Trait(ty::Binder::bind(ty::TraitPredicate {
1993                                     trait_ref: ty::TraitRef::new(
1994                                         self.tcx().lang_items().copy_trait().unwrap(),
1995                                         tcx.mk_substs_trait(ty, &[]),
1996                                     ),
1997                                 })),
1998                             ),
1999                             &traits::SelectionError::Unimplemented,
2000                             false,
2001                         );
2002                     }
2003                 }
2004             },
2005
2006             Rvalue::NullaryOp(_, ty) => {
2007                 // Even with unsized locals cannot box an unsized value.
2008                 if self.tcx().features().unsized_locals {
2009                     let span = body.source_info(location).span;
2010                     self.ensure_place_sized(ty, span);
2011                 }
2012
2013                 let trait_ref = ty::TraitRef {
2014                     def_id: tcx.lang_items().sized_trait().unwrap(),
2015                     substs: tcx.mk_substs_trait(ty, &[]),
2016                 };
2017
2018                 self.prove_trait_ref(
2019                     trait_ref,
2020                     location.to_locations(),
2021                     ConstraintCategory::SizedBound,
2022                 );
2023             }
2024
2025             Rvalue::Cast(cast_kind, op, ty) => {
2026                 match cast_kind {
2027                     CastKind::Pointer(PointerCast::ReifyFnPointer) => {
2028                         let fn_sig = op.ty(body, tcx).fn_sig(tcx);
2029
2030                         // The type that we see in the fcx is like
2031                         // `foo::<'a, 'b>`, where `foo` is the path to a
2032                         // function definition. When we extract the
2033                         // signature, it comes from the `fn_sig` query,
2034                         // and hence may contain unnormalized results.
2035                         let fn_sig = self.normalize(fn_sig, location);
2036
2037                         let ty_fn_ptr_from = tcx.mk_fn_ptr(fn_sig);
2038
2039                         if let Err(terr) = self.eq_types(
2040                             ty_fn_ptr_from,
2041                             ty,
2042                             location.to_locations(),
2043                             ConstraintCategory::Cast,
2044                         ) {
2045                             span_mirbug!(
2046                                 self,
2047                                 rvalue,
2048                                 "equating {:?} with {:?} yields {:?}",
2049                                 ty_fn_ptr_from,
2050                                 ty,
2051                                 terr
2052                             );
2053                         }
2054                     }
2055
2056                     CastKind::Pointer(PointerCast::ClosureFnPointer(unsafety)) => {
2057                         let sig = match op.ty(body, tcx).sty {
2058                             ty::Closure(def_id, substs) => {
2059                                 substs.closure_sig_ty(def_id, tcx).fn_sig(tcx)
2060                             }
2061                             _ => bug!(),
2062                         };
2063                         let ty_fn_ptr_from = tcx.coerce_closure_fn_ty(sig, *unsafety);
2064
2065                         if let Err(terr) = self.eq_types(
2066                             ty_fn_ptr_from,
2067                             ty,
2068                             location.to_locations(),
2069                             ConstraintCategory::Cast,
2070                         ) {
2071                             span_mirbug!(
2072                                 self,
2073                                 rvalue,
2074                                 "equating {:?} with {:?} yields {:?}",
2075                                 ty_fn_ptr_from,
2076                                 ty,
2077                                 terr
2078                             );
2079                         }
2080                     }
2081
2082                     CastKind::Pointer(PointerCast::UnsafeFnPointer) => {
2083                         let fn_sig = op.ty(body, tcx).fn_sig(tcx);
2084
2085                         // The type that we see in the fcx is like
2086                         // `foo::<'a, 'b>`, where `foo` is the path to a
2087                         // function definition. When we extract the
2088                         // signature, it comes from the `fn_sig` query,
2089                         // and hence may contain unnormalized results.
2090                         let fn_sig = self.normalize(fn_sig, location);
2091
2092                         let ty_fn_ptr_from = tcx.safe_to_unsafe_fn_ty(fn_sig);
2093
2094                         if let Err(terr) = self.eq_types(
2095                             ty_fn_ptr_from,
2096                             ty,
2097                             location.to_locations(),
2098                             ConstraintCategory::Cast,
2099                         ) {
2100                             span_mirbug!(
2101                                 self,
2102                                 rvalue,
2103                                 "equating {:?} with {:?} yields {:?}",
2104                                 ty_fn_ptr_from,
2105                                 ty,
2106                                 terr
2107                             );
2108                         }
2109                     }
2110
2111                     CastKind::Pointer(PointerCast::Unsize) => {
2112                         let &ty = ty;
2113                         let trait_ref = ty::TraitRef {
2114                             def_id: tcx.lang_items().coerce_unsized_trait().unwrap(),
2115                             substs: tcx.mk_substs_trait(op.ty(body, tcx), &[ty.into()]),
2116                         };
2117
2118                         self.prove_trait_ref(
2119                             trait_ref,
2120                             location.to_locations(),
2121                             ConstraintCategory::Cast,
2122                         );
2123                     }
2124
2125                     CastKind::Pointer(PointerCast::MutToConstPointer) => {
2126                         let ty_from = match op.ty(body, tcx).sty {
2127                             ty::RawPtr(ty::TypeAndMut {
2128                                 ty: ty_from,
2129                                 mutbl: hir::MutMutable,
2130                             }) => ty_from,
2131                             _ => {
2132                                 span_mirbug!(
2133                                     self,
2134                                     rvalue,
2135                                     "unexpected base type for cast {:?}",
2136                                     ty,
2137                                 );
2138                                 return;
2139                             }
2140                         };
2141                         let ty_to = match ty.sty {
2142                             ty::RawPtr(ty::TypeAndMut {
2143                                 ty: ty_to,
2144                                 mutbl: hir::MutImmutable,
2145                             }) => ty_to,
2146                             _ => {
2147                                 span_mirbug!(
2148                                     self,
2149                                     rvalue,
2150                                     "unexpected target type for cast {:?}",
2151                                     ty,
2152                                 );
2153                                 return;
2154                             }
2155                         };
2156                         if let Err(terr) = self.sub_types(
2157                             ty_from,
2158                             ty_to,
2159                             location.to_locations(),
2160                             ConstraintCategory::Cast,
2161                         ) {
2162                             span_mirbug!(
2163                                 self,
2164                                 rvalue,
2165                                 "relating {:?} with {:?} yields {:?}",
2166                                 ty_from,
2167                                 ty_to,
2168                                 terr
2169                             )
2170                         }
2171                     }
2172
2173                     CastKind::Misc => {
2174                         if let ty::Ref(_, mut ty_from, _) = op.ty(body, tcx).sty {
2175                             let (mut ty_to, mutability) = if let ty::RawPtr(ty::TypeAndMut {
2176                                 ty: ty_to,
2177                                 mutbl,
2178                             }) = ty.sty {
2179                                 (ty_to, mutbl)
2180                             } else {
2181                                 span_mirbug!(
2182                                     self,
2183                                     rvalue,
2184                                     "invalid cast types {:?} -> {:?}",
2185                                     op.ty(body, tcx),
2186                                     ty,
2187                                 );
2188                                 return;
2189                             };
2190
2191                             // Handle the direct cast from `&[T; N]` to `*const T` by unwrapping
2192                             // any array we find.
2193                             while let ty::Array(ty_elem_from, _) = ty_from.sty {
2194                                 ty_from = ty_elem_from;
2195                                 if let ty::Array(ty_elem_to, _) = ty_to.sty {
2196                                     ty_to = ty_elem_to;
2197                                 } else {
2198                                     break;
2199                                 }
2200                             }
2201
2202                             if let hir::MutMutable = mutability {
2203                                 if let Err(terr) = self.eq_types(
2204                                     ty_from,
2205                                     ty_to,
2206                                     location.to_locations(),
2207                                     ConstraintCategory::Cast,
2208                                 ) {
2209                                     span_mirbug!(
2210                                         self,
2211                                         rvalue,
2212                                         "equating {:?} with {:?} yields {:?}",
2213                                         ty_from,
2214                                         ty_to,
2215                                         terr
2216                                     )
2217                                 }
2218                             } else {
2219                                 if let Err(terr) = self.sub_types(
2220                                     ty_from,
2221                                     ty_to,
2222                                     location.to_locations(),
2223                                     ConstraintCategory::Cast,
2224                                 ) {
2225                                     span_mirbug!(
2226                                         self,
2227                                         rvalue,
2228                                         "relating {:?} with {:?} yields {:?}",
2229                                         ty_from,
2230                                         ty_to,
2231                                         terr
2232                                     )
2233                                 }
2234                             }
2235                         }
2236                     }
2237                 }
2238             }
2239
2240             Rvalue::Ref(region, _borrow_kind, borrowed_place) => {
2241                 self.add_reborrow_constraint(body, location, region, borrowed_place);
2242             }
2243
2244             Rvalue::BinaryOp(BinOp::Eq, left, right)
2245             | Rvalue::BinaryOp(BinOp::Ne, left, right)
2246             | Rvalue::BinaryOp(BinOp::Lt, left, right)
2247             | Rvalue::BinaryOp(BinOp::Le, left, right)
2248             | Rvalue::BinaryOp(BinOp::Gt, left, right)
2249             | Rvalue::BinaryOp(BinOp::Ge, left, right) => {
2250                 let ty_left = left.ty(body, tcx);
2251                 if let ty::RawPtr(_) | ty::FnPtr(_) = ty_left.sty {
2252                     let ty_right = right.ty(body, tcx);
2253                     let common_ty = self.infcx.next_ty_var(
2254                         TypeVariableOrigin {
2255                             kind: TypeVariableOriginKind::MiscVariable,
2256                             span: body.source_info(location).span,
2257                         }
2258                     );
2259                     self.sub_types(
2260                         common_ty,
2261                         ty_left,
2262                         location.to_locations(),
2263                         ConstraintCategory::Boring
2264                     ).unwrap_or_else(|err| {
2265                         bug!("Could not equate type variable with {:?}: {:?}", ty_left, err)
2266                     });
2267                     if let Err(terr) = self.sub_types(
2268                         common_ty,
2269                         ty_right,
2270                         location.to_locations(),
2271                         ConstraintCategory::Boring
2272                     ) {
2273                         span_mirbug!(
2274                             self,
2275                             rvalue,
2276                             "unexpected comparison types {:?} and {:?} yields {:?}",
2277                             ty_left,
2278                             ty_right,
2279                             terr
2280                         )
2281                     }
2282                 }
2283             }
2284
2285             Rvalue::Use(..)
2286             | Rvalue::Len(..)
2287             | Rvalue::BinaryOp(..)
2288             | Rvalue::CheckedBinaryOp(..)
2289             | Rvalue::UnaryOp(..)
2290             | Rvalue::Discriminant(..) => {}
2291         }
2292     }
2293
2294     /// If this rvalue supports a user-given type annotation, then
2295     /// extract and return it. This represents the final type of the
2296     /// rvalue and will be unified with the inferred type.
2297     fn rvalue_user_ty(&self, rvalue: &Rvalue<'tcx>) -> Option<UserTypeAnnotationIndex> {
2298         match rvalue {
2299             Rvalue::Use(_)
2300             | Rvalue::Repeat(..)
2301             | Rvalue::Ref(..)
2302             | Rvalue::Len(..)
2303             | Rvalue::Cast(..)
2304             | Rvalue::BinaryOp(..)
2305             | Rvalue::CheckedBinaryOp(..)
2306             | Rvalue::NullaryOp(..)
2307             | Rvalue::UnaryOp(..)
2308             | Rvalue::Discriminant(..) => None,
2309
2310             Rvalue::Aggregate(aggregate, _) => match **aggregate {
2311                 AggregateKind::Adt(_, _, _, user_ty, _) => user_ty,
2312                 AggregateKind::Array(_) => None,
2313                 AggregateKind::Tuple => None,
2314                 AggregateKind::Closure(_, _) => None,
2315                 AggregateKind::Generator(_, _, _) => None,
2316             },
2317         }
2318     }
2319
2320     fn check_aggregate_rvalue(
2321         &mut self,
2322         body: &Body<'tcx>,
2323         rvalue: &Rvalue<'tcx>,
2324         aggregate_kind: &AggregateKind<'tcx>,
2325         operands: &[Operand<'tcx>],
2326         location: Location,
2327     ) {
2328         let tcx = self.tcx();
2329
2330         self.prove_aggregate_predicates(aggregate_kind, location);
2331
2332         if *aggregate_kind == AggregateKind::Tuple {
2333             // tuple rvalue field type is always the type of the op. Nothing to check here.
2334             return;
2335         }
2336
2337         for (i, operand) in operands.iter().enumerate() {
2338             let field_ty = match self.aggregate_field_ty(aggregate_kind, i, location) {
2339                 Ok(field_ty) => field_ty,
2340                 Err(FieldAccessError::OutOfRange { field_count }) => {
2341                     span_mirbug!(
2342                         self,
2343                         rvalue,
2344                         "accessed field #{} but variant only has {}",
2345                         i,
2346                         field_count
2347                     );
2348                     continue;
2349                 }
2350             };
2351             let operand_ty = operand.ty(body, tcx);
2352
2353             if let Err(terr) = self.sub_types(
2354                 operand_ty,
2355                 field_ty,
2356                 location.to_locations(),
2357                 ConstraintCategory::Boring,
2358             ) {
2359                 span_mirbug!(
2360                     self,
2361                     rvalue,
2362                     "{:?} is not a subtype of {:?}: {:?}",
2363                     operand_ty,
2364                     field_ty,
2365                     terr
2366                 );
2367             }
2368         }
2369     }
2370
2371     /// Adds the constraints that arise from a borrow expression `&'a P` at the location `L`.
2372     ///
2373     /// # Parameters
2374     ///
2375     /// - `location`: the location `L` where the borrow expression occurs
2376     /// - `borrow_region`: the region `'a` associated with the borrow
2377     /// - `borrowed_place`: the place `P` being borrowed
2378     fn add_reborrow_constraint(
2379         &mut self,
2380         body: &Body<'tcx>,
2381         location: Location,
2382         borrow_region: ty::Region<'tcx>,
2383         borrowed_place: &Place<'tcx>,
2384     ) {
2385         // These constraints are only meaningful during borrowck:
2386         let BorrowCheckContext {
2387             borrow_set,
2388             location_table,
2389             all_facts,
2390             constraints,
2391             ..
2392         } = self.borrowck_context;
2393
2394         // In Polonius mode, we also push a `borrow_region` fact
2395         // linking the loan to the region (in some cases, though,
2396         // there is no loan associated with this borrow expression --
2397         // that occurs when we are borrowing an unsafe place, for
2398         // example).
2399         if let Some(all_facts) = all_facts {
2400             if let Some(borrow_index) = borrow_set.location_map.get(&location) {
2401                 let region_vid = borrow_region.to_region_vid();
2402                 all_facts.borrow_region.push((
2403                     region_vid,
2404                     *borrow_index,
2405                     location_table.mid_index(location),
2406                 ));
2407             }
2408         }
2409
2410         // If we are reborrowing the referent of another reference, we
2411         // need to add outlives relationships. In a case like `&mut
2412         // *p`, where the `p` has type `&'b mut Foo`, for example, we
2413         // need to ensure that `'b: 'a`.
2414
2415         let mut borrowed_projection = &borrowed_place.projection;
2416
2417         debug!(
2418             "add_reborrow_constraint({:?}, {:?}, {:?})",
2419             location, borrow_region, borrowed_place
2420         );
2421         while let Some(box proj) = borrowed_projection {
2422             debug!("add_reborrow_constraint - iteration {:?}", borrowed_projection);
2423
2424             match proj.elem {
2425                 ProjectionElem::Deref => {
2426                     let tcx = self.infcx.tcx;
2427                     let base_ty = Place::ty_from(&borrowed_place.base, &proj.base, body, tcx).ty;
2428
2429                     debug!("add_reborrow_constraint - base_ty = {:?}", base_ty);
2430                     match base_ty.sty {
2431                         ty::Ref(ref_region, _, mutbl) => {
2432                             constraints.outlives_constraints.push(OutlivesConstraint {
2433                                 sup: ref_region.to_region_vid(),
2434                                 sub: borrow_region.to_region_vid(),
2435                                 locations: location.to_locations(),
2436                                 category: ConstraintCategory::Boring,
2437                             });
2438
2439                             match mutbl {
2440                                 hir::Mutability::MutImmutable => {
2441                                     // Immutable reference. We don't need the base
2442                                     // to be valid for the entire lifetime of
2443                                     // the borrow.
2444                                     break;
2445                                 }
2446                                 hir::Mutability::MutMutable => {
2447                                     // Mutable reference. We *do* need the base
2448                                     // to be valid, because after the base becomes
2449                                     // invalid, someone else can use our mutable deref.
2450
2451                                     // This is in order to make the following function
2452                                     // illegal:
2453                                     // ```
2454                                     // fn unsafe_deref<'a, 'b>(x: &'a &'b mut T) -> &'b mut T {
2455                                     //     &mut *x
2456                                     // }
2457                                     // ```
2458                                     //
2459                                     // As otherwise you could clone `&mut T` using the
2460                                     // following function:
2461                                     // ```
2462                                     // fn bad(x: &mut T) -> (&mut T, &mut T) {
2463                                     //     let my_clone = unsafe_deref(&'a x);
2464                                     //     ENDREGION 'a;
2465                                     //     (my_clone, x)
2466                                     // }
2467                                     // ```
2468                                 }
2469                             }
2470                         }
2471                         ty::RawPtr(..) => {
2472                             // deref of raw pointer, guaranteed to be valid
2473                             break;
2474                         }
2475                         ty::Adt(def, _) if def.is_box() => {
2476                             // deref of `Box`, need the base to be valid - propagate
2477                         }
2478                         _ => bug!("unexpected deref ty {:?} in {:?}", base_ty, borrowed_place),
2479                     }
2480                 }
2481                 ProjectionElem::Field(..)
2482                 | ProjectionElem::Downcast(..)
2483                 | ProjectionElem::Index(..)
2484                 | ProjectionElem::ConstantIndex { .. }
2485                 | ProjectionElem::Subslice { .. } => {
2486                     // other field access
2487                 }
2488             }
2489
2490             // The "propagate" case. We need to check that our base is valid
2491             // for the borrow's lifetime.
2492             borrowed_projection = &proj.base;
2493         }
2494     }
2495
2496     fn prove_aggregate_predicates(
2497         &mut self,
2498         aggregate_kind: &AggregateKind<'tcx>,
2499         location: Location,
2500     ) {
2501         let tcx = self.tcx();
2502
2503         debug!(
2504             "prove_aggregate_predicates(aggregate_kind={:?}, location={:?})",
2505             aggregate_kind, location
2506         );
2507
2508         let instantiated_predicates = match aggregate_kind {
2509             AggregateKind::Adt(def, _, substs, _, _) => {
2510                 tcx.predicates_of(def.did).instantiate(tcx, substs)
2511             }
2512
2513             // For closures, we have some **extra requirements** we
2514             //
2515             // have to check. In particular, in their upvars and
2516             // signatures, closures often reference various regions
2517             // from the surrounding function -- we call those the
2518             // closure's free regions. When we borrow-check (and hence
2519             // region-check) closures, we may find that the closure
2520             // requires certain relationships between those free
2521             // regions. However, because those free regions refer to
2522             // portions of the CFG of their caller, the closure is not
2523             // in a position to verify those relationships. In that
2524             // case, the requirements get "propagated" to us, and so
2525             // we have to solve them here where we instantiate the
2526             // closure.
2527             //
2528             // Despite the opacity of the previous parapgrah, this is
2529             // actually relatively easy to understand in terms of the
2530             // desugaring. A closure gets desugared to a struct, and
2531             // these extra requirements are basically like where
2532             // clauses on the struct.
2533             AggregateKind::Closure(def_id, ty::ClosureSubsts { substs })
2534             | AggregateKind::Generator(def_id, ty::GeneratorSubsts { substs }, _) => {
2535                 self.prove_closure_bounds(tcx, *def_id, substs, location)
2536             }
2537
2538             AggregateKind::Array(_) | AggregateKind::Tuple => ty::InstantiatedPredicates::empty(),
2539         };
2540
2541         self.normalize_and_prove_instantiated_predicates(
2542             instantiated_predicates,
2543             location.to_locations(),
2544         );
2545     }
2546
2547     fn prove_closure_bounds(
2548         &mut self,
2549         tcx: TyCtxt<'tcx>,
2550         def_id: DefId,
2551         substs: SubstsRef<'tcx>,
2552         location: Location,
2553     ) -> ty::InstantiatedPredicates<'tcx> {
2554         if let Some(closure_region_requirements) = tcx.mir_borrowck(def_id).closure_requirements {
2555             let closure_constraints = QueryRegionConstraints {
2556                 outlives: closure_region_requirements.apply_requirements(tcx, def_id, substs),
2557
2558                 // Presently, closures never propagate member
2559                 // constraints to their parents -- they are enforced
2560                 // locally.  This is largely a non-issue as member
2561                 // constraints only come from `-> impl Trait` and
2562                 // friends which don't appear (thus far...) in
2563                 // closures.
2564                 member_constraints: vec![],
2565             };
2566
2567             let bounds_mapping = closure_constraints
2568                 .outlives
2569                 .iter()
2570                 .enumerate()
2571                 .filter_map(|(idx, constraint)| {
2572                     let ty::OutlivesPredicate(k1, r2) =
2573                         constraint.no_bound_vars().unwrap_or_else(|| {
2574                             bug!("query_constraint {:?} contained bound vars", constraint,);
2575                         });
2576
2577                     match k1.unpack() {
2578                         UnpackedKind::Lifetime(r1) => {
2579                             // constraint is r1: r2
2580                             let r1_vid = self.borrowck_context.universal_regions.to_region_vid(r1);
2581                             let r2_vid = self.borrowck_context.universal_regions.to_region_vid(r2);
2582                             let outlives_requirements =
2583                                 &closure_region_requirements.outlives_requirements[idx];
2584                             Some((
2585                                 (r1_vid, r2_vid),
2586                                 (
2587                                     outlives_requirements.category,
2588                                     outlives_requirements.blame_span,
2589                                 ),
2590                             ))
2591                         }
2592                         UnpackedKind::Type(_) | UnpackedKind::Const(_) => None,
2593                     }
2594                 })
2595                 .collect();
2596
2597             let existing = self.borrowck_context
2598                 .constraints
2599                 .closure_bounds_mapping
2600                 .insert(location, bounds_mapping);
2601             assert!(
2602                 existing.is_none(),
2603                 "Multiple closures at the same location."
2604             );
2605
2606             self.push_region_constraints(
2607                 location.to_locations(),
2608                 ConstraintCategory::ClosureBounds,
2609                 &closure_constraints,
2610             );
2611         }
2612
2613         tcx.predicates_of(def_id).instantiate(tcx, substs)
2614     }
2615
2616     fn prove_trait_ref(
2617         &mut self,
2618         trait_ref: ty::TraitRef<'tcx>,
2619         locations: Locations,
2620         category: ConstraintCategory,
2621     ) {
2622         self.prove_predicates(
2623             Some(ty::Predicate::Trait(
2624                 trait_ref.to_poly_trait_ref().to_poly_trait_predicate(),
2625             )),
2626             locations,
2627             category,
2628         );
2629     }
2630
2631     fn normalize_and_prove_instantiated_predicates(
2632         &mut self,
2633         instantiated_predicates: ty::InstantiatedPredicates<'tcx>,
2634         locations: Locations,
2635     ) {
2636         for predicate in instantiated_predicates.predicates {
2637             let predicate = self.normalize(predicate, locations);
2638             self.prove_predicate(predicate, locations, ConstraintCategory::Boring);
2639         }
2640     }
2641
2642     fn prove_predicates(
2643         &mut self,
2644         predicates: impl IntoIterator<Item = ty::Predicate<'tcx>>,
2645         locations: Locations,
2646         category: ConstraintCategory,
2647     ) {
2648         for predicate in predicates {
2649             debug!(
2650                 "prove_predicates(predicate={:?}, locations={:?})",
2651                 predicate, locations,
2652             );
2653
2654             self.prove_predicate(predicate, locations, category);
2655         }
2656     }
2657
2658     fn prove_predicate(
2659         &mut self,
2660         predicate: ty::Predicate<'tcx>,
2661         locations: Locations,
2662         category: ConstraintCategory,
2663     ) {
2664         debug!(
2665             "prove_predicate(predicate={:?}, location={:?})",
2666             predicate, locations,
2667         );
2668
2669         let param_env = self.param_env;
2670         self.fully_perform_op(
2671             locations,
2672             category,
2673             param_env.and(type_op::prove_predicate::ProvePredicate::new(predicate)),
2674         ).unwrap_or_else(|NoSolution| {
2675             span_mirbug!(self, NoSolution, "could not prove {:?}", predicate);
2676         })
2677     }
2678
2679     fn typeck_mir(&mut self, body: &Body<'tcx>) {
2680         self.last_span = body.span;
2681         debug!("run_on_mir: {:?}", body.span);
2682
2683         for (local, local_decl) in body.local_decls.iter_enumerated() {
2684             self.check_local(body, local, local_decl);
2685         }
2686
2687         for (block, block_data) in body.basic_blocks().iter_enumerated() {
2688             let mut location = Location {
2689                 block,
2690                 statement_index: 0,
2691             };
2692             for stmt in &block_data.statements {
2693                 if !stmt.source_info.span.is_dummy() {
2694                     self.last_span = stmt.source_info.span;
2695                 }
2696                 self.check_stmt(body, stmt, location);
2697                 location.statement_index += 1;
2698             }
2699
2700             self.check_terminator(body, block_data.terminator(), location);
2701             self.check_iscleanup(body, block_data);
2702         }
2703     }
2704
2705     fn normalize<T>(&mut self, value: T, location: impl NormalizeLocation) -> T
2706     where
2707         T: type_op::normalize::Normalizable<'tcx> + Copy + 'tcx,
2708     {
2709         debug!("normalize(value={:?}, location={:?})", value, location);
2710         let param_env = self.param_env;
2711         self.fully_perform_op(
2712             location.to_locations(),
2713             ConstraintCategory::Boring,
2714             param_env.and(type_op::normalize::Normalize::new(value)),
2715         ).unwrap_or_else(|NoSolution| {
2716             span_mirbug!(self, NoSolution, "failed to normalize `{:?}`", value);
2717             value
2718         })
2719     }
2720 }
2721
2722 trait NormalizeLocation: fmt::Debug + Copy {
2723     fn to_locations(self) -> Locations;
2724 }
2725
2726 impl NormalizeLocation for Locations {
2727     fn to_locations(self) -> Locations {
2728         self
2729     }
2730 }
2731
2732 impl NormalizeLocation for Location {
2733     fn to_locations(self) -> Locations {
2734         Locations::Single(self)
2735     }
2736 }
2737
2738 #[derive(Debug, Default)]
2739 struct ObligationAccumulator<'tcx> {
2740     obligations: PredicateObligations<'tcx>,
2741 }
2742
2743 impl<'tcx> ObligationAccumulator<'tcx> {
2744     fn add<T>(&mut self, value: InferOk<'tcx, T>) -> T {
2745         let InferOk { value, obligations } = value;
2746         self.obligations.extend(obligations);
2747         value
2748     }
2749
2750     fn into_vec(self) -> PredicateObligations<'tcx> {
2751         self.obligations
2752     }
2753 }