compiler/rustc_borrowck/src/type_check/mod.rs

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