compiler/rustc_typeck/src/check/upvar.rs

   1 //! ### Inferring borrow kinds for upvars
   2 //!
   3 //! Whenever there is a closure expression, we need to determine how each
   4 //! upvar is used. We do this by initially assigning each upvar an
   5 //! immutable "borrow kind" (see `ty::BorrowKind` for details) and then
   6 //! "escalating" the kind as needed. The borrow kind proceeds according to
   7 //! the following lattice:
   8 //!
   9 //!     ty::ImmBorrow -> ty::UniqueImmBorrow -> ty::MutBorrow
  10 //!
  11 //! So, for example, if we see an assignment `x = 5` to an upvar `x`, we
  12 //! will promote its borrow kind to mutable borrow. If we see an `&mut x`
  13 //! we'll do the same. Naturally, this applies not just to the upvar, but
  14 //! to everything owned by `x`, so the result is the same for something
  15 //! like `x.f = 5` and so on (presuming `x` is not a borrowed pointer to a
  16 //! struct). These adjustments are performed in
  17 //! `adjust_upvar_borrow_kind()` (you can trace backwards through the code
  18 //! from there).
  19 //!
  20 //! The fact that we are inferring borrow kinds as we go results in a
  21 //! semi-hacky interaction with mem-categorization. In particular,
  22 //! mem-categorization will query the current borrow kind as it
  23 //! categorizes, and we'll return the *current* value, but this may get
  24 //! adjusted later. Therefore, in this module, we generally ignore the
  25 //! borrow kind (and derived mutabilities) that are returned from
  26 //! mem-categorization, since they may be inaccurate. (Another option
  27 //! would be to use a unification scheme, where instead of returning a
  28 //! concrete borrow kind like `ty::ImmBorrow`, we return a
  29 //! `ty::InferBorrow(upvar_id)` or something like that, but this would
  30 //! then mean that all later passes would have to check for these figments
  31 //! and report an error, and it just seems like more mess in the end.)
  32
  33 use super::FnCtxt;
  34
  35 use crate::expr_use_visitor as euv;
  36 use rustc_data_structures::fx::FxIndexMap;
  37 use rustc_hir as hir;
  38 use rustc_hir::def_id::DefId;
  39 use rustc_hir::def_id::LocalDefId;
  40 use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor};
  41 use rustc_infer::infer::UpvarRegion;
  42 use rustc_middle::hir::place::{Place, PlaceBase, PlaceWithHirId, ProjectionKind};
  43 use rustc_middle::ty::{self, Ty, TyCtxt, UpvarSubsts};
  44 use rustc_span::sym;
  45 use rustc_span::{MultiSpan, Span, Symbol};
  46
  47 /// Describe the relationship between the paths of two places
  48 /// eg:
  49 /// - `foo` is ancestor of `foo.bar.baz`
  50 /// - `foo.bar.baz` is an descendant of `foo.bar`
  51 /// - `foo.bar` and `foo.baz` are divergent
  52 enum PlaceAncestryRelation {
  53     Ancestor,
  54     Descendant,
  55     Divergent,
  56 }
  57
  58 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
  59     pub fn closure_analyze(&self, body: &'tcx hir::Body<'tcx>) {
  60         InferBorrowKindVisitor { fcx: self }.visit_body(body);
  61
  62         // it's our job to process these.
  63         assert!(self.deferred_call_resolutions.borrow().is_empty());
  64     }
  65 }
  66
  67 struct InferBorrowKindVisitor<'a, 'tcx> {
  68     fcx: &'a FnCtxt<'a, 'tcx>,
  69 }
  70
  71 impl<'a, 'tcx> Visitor<'tcx> for InferBorrowKindVisitor<'a, 'tcx> {
  72     type Map = intravisit::ErasedMap<'tcx>;
  73
  74     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
  75         NestedVisitorMap::None
  76     }
  77
  78     fn visit_expr(&mut self, expr: &'tcx hir::Expr<'tcx>) {
  79         if let hir::ExprKind::Closure(cc, _, body_id, _, _) = expr.kind {
  80             let body = self.fcx.tcx.hir().body(body_id);
  81             self.visit_body(body);
  82             self.fcx.analyze_closure(expr.hir_id, expr.span, body, cc);
  83         }
  84
  85         intravisit::walk_expr(self, expr);
  86     }
  87 }
  88
  89 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
  90     /// Analysis starting point.
  91     fn analyze_closure(
  92         &self,
  93         closure_hir_id: hir::HirId,
  94         span: Span,
  95         body: &hir::Body<'_>,
  96         capture_clause: hir::CaptureBy,
  97     ) {
  98         debug!("analyze_closure(id={:?}, body.id={:?})", closure_hir_id, body.id());
  99
 100         // Extract the type of the closure.
 101         let ty = self.node_ty(closure_hir_id);
 102         let (closure_def_id, substs) = match *ty.kind() {
 103             ty::Closure(def_id, substs) => (def_id, UpvarSubsts::Closure(substs)),
 104             ty::Generator(def_id, substs, _) => (def_id, UpvarSubsts::Generator(substs)),
 105             ty::Error(_) => {
 106                 // #51714: skip analysis when we have already encountered type errors
 107                 return;
 108             }
 109             _ => {
 110                 span_bug!(
 111                     span,
 112                     "type of closure expr {:?} is not a closure {:?}",
 113                     closure_hir_id,
 114                     ty
 115                 );
 116             }
 117         };
 118
 119         let infer_kind = if let UpvarSubsts::Closure(closure_substs) = substs {
 120             self.closure_kind(closure_substs).is_none().then_some(closure_substs)
 121         } else {
 122             None
 123         };
 124
 125         let local_def_id = closure_def_id.expect_local();
 126
 127         let mut capture_information: FxIndexMap<Place<'tcx>, ty::CaptureInfo<'tcx>> =
 128             Default::default();
 129         if !self.tcx.features().capture_disjoint_fields {
 130             if let Some(upvars) = self.tcx.upvars_mentioned(closure_def_id) {
 131                 for (&var_hir_id, _) in upvars.iter() {
 132                     let place = self.place_for_root_variable(local_def_id, var_hir_id);
 133
 134                     debug!("seed place {:?}", place);
 135
 136                     let upvar_id = ty::UpvarId::new(var_hir_id, local_def_id);
 137                     let capture_kind = self.init_capture_kind(capture_clause, upvar_id, span);
 138                     let info = ty::CaptureInfo {
 139                         capture_kind_expr_id: None,
 140                         path_expr_id: None,
 141                         capture_kind,
 142                     };
 143
 144                     capture_information.insert(place, info);
 145                 }
 146             }
 147         }
 148
 149         let body_owner_def_id = self.tcx.hir().body_owner_def_id(body.id());
 150         assert_eq!(body_owner_def_id.to_def_id(), closure_def_id);
 151         let mut delegate = InferBorrowKind {
 152             fcx: self,
 153             closure_def_id,
 154             closure_span: span,
 155             capture_clause,
 156             current_closure_kind: ty::ClosureKind::LATTICE_BOTTOM,
 157             current_origin: None,
 158             capture_information,
 159         };
 160         euv::ExprUseVisitor::new(
 161             &mut delegate,
 162             &self.infcx,
 163             body_owner_def_id,
 164             self.param_env,
 165             &self.typeck_results.borrow(),
 166         )
 167         .consume_body(body);
 168
 169         debug!(
 170             "For closure={:?}, capture_information={:#?}",
 171             closure_def_id, delegate.capture_information
 172         );
 173         self.log_capture_analysis_first_pass(closure_def_id, &delegate.capture_information, span);
 174
 175         if let Some(closure_substs) = infer_kind {
 176             // Unify the (as yet unbound) type variable in the closure
 177             // substs with the kind we inferred.
 178             let inferred_kind = delegate.current_closure_kind;
 179             let closure_kind_ty = closure_substs.as_closure().kind_ty();
 180             self.demand_eqtype(span, inferred_kind.to_ty(self.tcx), closure_kind_ty);
 181
 182             // If we have an origin, store it.
 183             if let Some(origin) = delegate.current_origin.clone() {
 184                 let origin = if self.tcx.features().capture_disjoint_fields {
 185                     origin
 186                 } else {
 187                     // FIXME(project-rfc-2229#31): Once the changes to support reborrowing are
 188                     //                             made, make sure we are selecting and restricting
 189                     //                             the origin correctly.
 190                     (origin.0, Place { projections: vec![], ..origin.1 })
 191                 };
 192
 193                 self.typeck_results
 194                     .borrow_mut()
 195                     .closure_kind_origins_mut()
 196                     .insert(closure_hir_id, origin);
 197             }
 198         }
 199
 200         self.compute_min_captures(closure_def_id, delegate);
 201         self.log_closure_min_capture_info(closure_def_id, span);
 202
 203         self.min_captures_to_closure_captures_bridge(closure_def_id);
 204
 205         // Now that we've analyzed the closure, we know how each
 206         // variable is borrowed, and we know what traits the closure
 207         // implements (Fn vs FnMut etc). We now have some updates to do
 208         // with that information.
 209         //
 210         // Note that no closure type C may have an upvar of type C
 211         // (though it may reference itself via a trait object). This
 212         // results from the desugaring of closures to a struct like
 213         // `Foo<..., UV0...UVn>`. If one of those upvars referenced
 214         // C, then the type would have infinite size (and the
 215         // inference algorithm will reject it).
 216
 217         // Equate the type variables for the upvars with the actual types.
 218         let final_upvar_tys = self.final_upvar_tys(closure_def_id);
 219         debug!(
 220             "analyze_closure: id={:?} substs={:?} final_upvar_tys={:?}",
 221             closure_hir_id, substs, final_upvar_tys
 222         );
 223
 224         // Build a tuple (U0..Un) of the final upvar types U0..Un
 225         // and unify the upvar tupe type in the closure with it:
 226         let final_tupled_upvars_type = self.tcx.mk_tup(final_upvar_tys.iter());
 227         self.demand_suptype(span, substs.tupled_upvars_ty(), final_tupled_upvars_type);
 228
 229         // If we are also inferred the closure kind here,
 230         // process any deferred resolutions.
 231         let deferred_call_resolutions = self.remove_deferred_call_resolutions(closure_def_id);
 232         for deferred_call_resolution in deferred_call_resolutions {
 233             deferred_call_resolution.resolve(self);
 234         }
 235     }
 236
 237     // Returns a list of `Ty`s for each upvar.
 238     fn final_upvar_tys(&self, closure_id: DefId) -> Vec<Ty<'tcx>> {
 239         // Presently an unboxed closure type cannot "escape" out of a
 240         // function, so we will only encounter ones that originated in the
 241         // local crate or were inlined into it along with some function.
 242         // This may change if abstract return types of some sort are
 243         // implemented.
 244         let tcx = self.tcx;
 245
 246         self.typeck_results
 247             .borrow()
 248             .closure_min_captures_flattened(closure_id)
 249             .map(|captured_place| {
 250                 let upvar_ty = captured_place.place.ty();
 251                 let capture = captured_place.info.capture_kind;
 252
 253                 debug!(
 254                     "final_upvar_tys: place={:?} upvar_ty={:?} capture={:?}, mutability={:?}",
 255                     captured_place.place, upvar_ty, capture, captured_place.mutability,
 256                 );
 257
 258                 match capture {
 259                     ty::UpvarCapture::ByValue(_) => upvar_ty,
 260                     ty::UpvarCapture::ByRef(borrow) => tcx.mk_ref(
 261                         borrow.region,
 262                         ty::TypeAndMut { ty: upvar_ty, mutbl: borrow.kind.to_mutbl_lossy() },
 263                     ),
 264                 }
 265             })
 266             .collect()
 267     }
 268
 269     /// Bridge for closure analysis
 270     /// ----------------------------
 271     ///
 272     /// For closure with DefId `c`, the bridge converts structures required for supporting RFC 2229,
 273     /// to structures currently used in the compiler for handling closure captures.
 274     ///
 275     /// For example the following structure will be converted:
 276     ///
 277     /// closure_min_captures
 278     /// foo -> [ {foo.x, ImmBorrow}, {foo.y, MutBorrow} ]
 279     /// bar -> [ {bar.z, ByValue}, {bar.q, MutBorrow} ]
 280     ///
 281     /// to
 282     ///
 283     /// 1. closure_captures
 284     /// foo -> UpvarId(foo, c), bar -> UpvarId(bar, c)
 285     ///
 286     /// 2. upvar_capture_map
 287     /// UpvarId(foo,c) -> MutBorrow, UpvarId(bar, c) -> ByValue
 288     fn min_captures_to_closure_captures_bridge(&self, closure_def_id: DefId) {
 289         let mut closure_captures: FxIndexMap<hir::HirId, ty::UpvarId> = Default::default();
 290         let mut upvar_capture_map = ty::UpvarCaptureMap::default();
 291
 292         if let Some(min_captures) =
 293             self.typeck_results.borrow().closure_min_captures.get(&closure_def_id)
 294         {
 295             for (var_hir_id, min_list) in min_captures.iter() {
 296                 for captured_place in min_list {
 297                     let place = &captured_place.place;
 298                     let capture_info = captured_place.info;
 299
 300                     let upvar_id = match place.base {
 301                         PlaceBase::Upvar(upvar_id) => upvar_id,
 302                         base => bug!("Expected upvar, found={:?}", base),
 303                     };
 304
 305                     assert_eq!(upvar_id.var_path.hir_id, *var_hir_id);
 306                     assert_eq!(upvar_id.closure_expr_id, closure_def_id.expect_local());
 307
 308                     closure_captures.insert(*var_hir_id, upvar_id);
 309
 310                     let new_capture_kind =
 311                         if let Some(capture_kind) = upvar_capture_map.get(&upvar_id) {
 312                             // upvar_capture_map only stores the UpvarCapture (CaptureKind),
 313                             // so we create a fake capture info with no expression.
 314                             let fake_capture_info = ty::CaptureInfo {
 315                                 capture_kind_expr_id: None,
 316                                 path_expr_id: None,
 317                                 capture_kind: *capture_kind,
 318                             };
 319                             determine_capture_info(fake_capture_info, capture_info).capture_kind
 320                         } else {
 321                             capture_info.capture_kind
 322                         };
 323                     upvar_capture_map.insert(upvar_id, new_capture_kind);
 324                 }
 325             }
 326         }
 327         debug!("For closure_def_id={:?}, closure_captures={:#?}", closure_def_id, closure_captures);
 328         debug!(
 329             "For closure_def_id={:?}, upvar_capture_map={:#?}",
 330             closure_def_id, upvar_capture_map
 331         );
 332
 333         if !closure_captures.is_empty() {
 334             self.typeck_results
 335                 .borrow_mut()
 336                 .closure_captures
 337                 .insert(closure_def_id, closure_captures);
 338
 339             self.typeck_results.borrow_mut().upvar_capture_map.extend(upvar_capture_map);
 340         }
 341     }
 342
 343     /// Analyzes the information collected by `InferBorrowKind` to compute the min number of
 344     /// Places (and corresponding capture kind) that we need to keep track of to support all
 345     /// the required captured paths.
 346     ///
 347     /// Eg:
 348     /// ```rust,no_run
 349     /// struct Point { x: i32, y: i32 }
 350     ///
 351     /// let s: String;  // hir_id_s
 352     /// let mut p: Point; // his_id_p
 353     /// let c = || {
 354     ///        println!("{}", s);  // L1
 355     ///        p.x += 10;  // L2
 356     ///        println!("{}" , p.y) // L3
 357     ///        println!("{}", p) // L4
 358     ///        drop(s);   // L5
 359     /// };
 360     /// ```
 361     /// and let hir_id_L1..5 be the expressions pointing to use of a captured variable on
 362     /// the lines L1..5 respectively.
 363     ///
 364     /// InferBorrowKind results in a structure like this:
 365     ///
 366     /// ```
 367     /// {
 368     ///       Place(base: hir_id_s, projections: [], ....) -> {
 369     ///                                                            capture_kind_expr: hir_id_L5,
 370     ///                                                            path_expr_id: hir_id_L5,
 371     ///                                                            capture_kind: ByValue
 372     ///                                                       },
 373     ///       Place(base: hir_id_p, projections: [Field(0, 0)], ...) -> {
 374     ///                                                                     capture_kind_expr: hir_id_L2,
 375     ///                                                                     path_expr_id: hir_id_L2,
 376     ///                                                                     capture_kind: ByValue
 377     ///                                                                 },
 378     ///       Place(base: hir_id_p, projections: [Field(1, 0)], ...) -> {
 379     ///                                                                     capture_kind_expr: hir_id_L3,
 380     ///                                                                     path_expr_id: hir_id_L3,
 381     ///                                                                     capture_kind: ByValue
 382     ///                                                                 },
 383     ///       Place(base: hir_id_p, projections: [], ...) -> {
 384     ///                                                          capture_kind_expr: hir_id_L4,
 385     ///                                                          path_expr_id: hir_id_L4,
 386     ///                                                          capture_kind: ByValue
 387     ///                                                      },
 388     /// ```
 389     ///
 390     /// After the min capture analysis, we get:
 391     /// ```
 392     /// {
 393     ///       hir_id_s -> [
 394     ///            Place(base: hir_id_s, projections: [], ....) -> {
 395     ///                                                                capture_kind_expr: hir_id_L5,
 396     ///                                                                path_expr_id: hir_id_L5,
 397     ///                                                                capture_kind: ByValue
 398     ///                                                            },
 399     ///       ],
 400     ///       hir_id_p -> [
 401     ///            Place(base: hir_id_p, projections: [], ...) -> {
 402     ///                                                               capture_kind_expr: hir_id_L2,
 403     ///                                                               path_expr_id: hir_id_L4,
 404     ///                                                               capture_kind: ByValue
 405     ///                                                           },
 406     ///       ],
 407     /// ```
 408     fn compute_min_captures(
 409         &self,
 410         closure_def_id: DefId,
 411         inferred_info: InferBorrowKind<'_, 'tcx>,
 412     ) {
 413         let mut root_var_min_capture_list: ty::RootVariableMinCaptureList<'_> = Default::default();
 414
 415         for (place, capture_info) in inferred_info.capture_information.into_iter() {
 416             let var_hir_id = match place.base {
 417                 PlaceBase::Upvar(upvar_id) => upvar_id.var_path.hir_id,
 418                 base => bug!("Expected upvar, found={:?}", base),
 419             };
 420
 421             let place = restrict_capture_precision(place, capture_info.capture_kind);
 422
 423             let min_cap_list = match root_var_min_capture_list.get_mut(&var_hir_id) {
 424                 None => {
 425                     let mutability = self.determine_capture_mutability(&place);
 426                     let min_cap_list =
 427                         vec![ty::CapturedPlace { place, info: capture_info, mutability }];
 428                     root_var_min_capture_list.insert(var_hir_id, min_cap_list);
 429                     continue;
 430                 }
 431                 Some(min_cap_list) => min_cap_list,
 432             };
 433
 434             // Go through each entry in the current list of min_captures
 435             // - if ancestor is found, update it's capture kind to account for current place's
 436             // capture information.
 437             //
 438             // - if descendant is found, remove it from the list, and update the current place's
 439             // capture information to account for the descendants's capture kind.
 440             //
 441             // We can never be in a case where the list contains both an ancestor and a descendant
 442             // Also there can only be ancestor but in case of descendants there might be
 443             // multiple.
 444
 445             let mut descendant_found = false;
 446             let mut updated_capture_info = capture_info;
 447             min_cap_list.retain(|possible_descendant| {
 448                 match determine_place_ancestry_relation(&place, &possible_descendant.place) {
 449                     // current place is ancestor of possible_descendant
 450                     PlaceAncestryRelation::Ancestor => {
 451                         descendant_found = true;
 452                         let backup_path_expr_id = updated_capture_info.path_expr_id;
 453
 454                         updated_capture_info =
 455                             determine_capture_info(updated_capture_info, possible_descendant.info);
 456
 457                         // we need to keep the ancestor's `path_expr_id`
 458                         updated_capture_info.path_expr_id = backup_path_expr_id;
 459                         false
 460                     }
 461
 462                     _ => true,
 463                 }
 464             });
 465
 466             let mut ancestor_found = false;
 467             if !descendant_found {
 468                 for possible_ancestor in min_cap_list.iter_mut() {
 469                     match determine_place_ancestry_relation(&place, &possible_ancestor.place) {
 470                         // current place is descendant of possible_ancestor
 471                         PlaceAncestryRelation::Descendant => {
 472                             ancestor_found = true;
 473                             let backup_path_expr_id = possible_ancestor.info.path_expr_id;
 474                             possible_ancestor.info =
 475                                 determine_capture_info(possible_ancestor.info, capture_info);
 476
 477                             // we need to keep the ancestor's `path_expr_id`
 478                             possible_ancestor.info.path_expr_id = backup_path_expr_id;
 479
 480                             // Only one ancestor of the current place will be in the list.
 481                             break;
 482                         }
 483                         _ => {}
 484                     }
 485                 }
 486             }
 487
 488             // Only need to insert when we don't have an ancestor in the existing min capture list
 489             if !ancestor_found {
 490                 let mutability = self.determine_capture_mutability(&place);
 491                 let captured_place =
 492                     ty::CapturedPlace { place, info: updated_capture_info, mutability };
 493                 min_cap_list.push(captured_place);
 494             }
 495         }
 496
 497         debug!("For closure={:?}, min_captures={:#?}", closure_def_id, root_var_min_capture_list);
 498
 499         if !root_var_min_capture_list.is_empty() {
 500             self.typeck_results
 501                 .borrow_mut()
 502                 .closure_min_captures
 503                 .insert(closure_def_id, root_var_min_capture_list);
 504         }
 505     }
 506
 507     fn init_capture_kind(
 508         &self,
 509         capture_clause: hir::CaptureBy,
 510         upvar_id: ty::UpvarId,
 511         closure_span: Span,
 512     ) -> ty::UpvarCapture<'tcx> {
 513         match capture_clause {
 514             hir::CaptureBy::Value => ty::UpvarCapture::ByValue(None),
 515             hir::CaptureBy::Ref => {
 516                 let origin = UpvarRegion(upvar_id, closure_span);
 517                 let upvar_region = self.next_region_var(origin);
 518                 let upvar_borrow = ty::UpvarBorrow { kind: ty::ImmBorrow, region: upvar_region };
 519                 ty::UpvarCapture::ByRef(upvar_borrow)
 520             }
 521         }
 522     }
 523
 524     fn place_for_root_variable(
 525         &self,
 526         closure_def_id: LocalDefId,
 527         var_hir_id: hir::HirId,
 528     ) -> Place<'tcx> {
 529         let upvar_id = ty::UpvarId::new(var_hir_id, closure_def_id);
 530
 531         Place {
 532             base_ty: self.node_ty(var_hir_id),
 533             base: PlaceBase::Upvar(upvar_id),
 534             projections: Default::default(),
 535         }
 536     }
 537
 538     fn should_log_capture_analysis(&self, closure_def_id: DefId) -> bool {
 539         self.tcx.has_attr(closure_def_id, sym::rustc_capture_analysis)
 540     }
 541
 542     fn log_capture_analysis_first_pass(
 543         &self,
 544         closure_def_id: rustc_hir::def_id::DefId,
 545         capture_information: &FxIndexMap<Place<'tcx>, ty::CaptureInfo<'tcx>>,
 546         closure_span: Span,
 547     ) {
 548         if self.should_log_capture_analysis(closure_def_id) {
 549             let mut diag =
 550                 self.tcx.sess.struct_span_err(closure_span, "First Pass analysis includes:");
 551             for (place, capture_info) in capture_information {
 552                 let capture_str = construct_capture_info_string(self.tcx, place, capture_info);
 553                 let output_str = format!("Capturing {}", capture_str);
 554
 555                 let span =
 556                     capture_info.path_expr_id.map_or(closure_span, |e| self.tcx.hir().span(e));
 557                 diag.span_note(span, &output_str);
 558             }
 559             diag.emit();
 560         }
 561     }
 562
 563     fn log_closure_min_capture_info(&self, closure_def_id: DefId, closure_span: Span) {
 564         if self.should_log_capture_analysis(closure_def_id) {
 565             if let Some(min_captures) =
 566                 self.typeck_results.borrow().closure_min_captures.get(&closure_def_id)
 567             {
 568                 let mut diag =
 569                     self.tcx.sess.struct_span_err(closure_span, "Min Capture analysis includes:");
 570
 571                 for (_, min_captures_for_var) in min_captures {
 572                     for capture in min_captures_for_var {
 573                         let place = &capture.place;
 574                         let capture_info = &capture.info;
 575
 576                         let capture_str =
 577                             construct_capture_info_string(self.tcx, place, capture_info);
 578                         let output_str = format!("Min Capture {}", capture_str);
 579
 580                         if capture.info.path_expr_id != capture.info.capture_kind_expr_id {
 581                             let path_span = capture_info
 582                                 .path_expr_id
 583                                 .map_or(closure_span, |e| self.tcx.hir().span(e));
 584                             let capture_kind_span = capture_info
 585                                 .capture_kind_expr_id
 586                                 .map_or(closure_span, |e| self.tcx.hir().span(e));
 587
 588                             let mut multi_span: MultiSpan =
 589                                 MultiSpan::from_spans(vec![path_span, capture_kind_span]);
 590
 591                             let capture_kind_label =
 592                                 construct_capture_kind_reason_string(self.tcx, place, capture_info);
 593                             let path_label = construct_path_string(self.tcx, place);
 594
 595                             multi_span.push_span_label(path_span, path_label);
 596                             multi_span.push_span_label(capture_kind_span, capture_kind_label);
 597
 598                             diag.span_note(multi_span, &output_str);
 599                         } else {
 600                             let span = capture_info
 601                                 .path_expr_id
 602                                 .map_or(closure_span, |e| self.tcx.hir().span(e));
 603
 604                             diag.span_note(span, &output_str);
 605                         };
 606                     }
 607                 }
 608                 diag.emit();
 609             }
 610         }
 611     }
 612
 613     /// A captured place is mutable if
 614     /// 1. Projections don't include a Deref of an immut-borrow, **and**
 615     /// 2. PlaceBase is mut or projections include a Deref of a mut-borrow.
 616     fn determine_capture_mutability(&self, place: &Place<'tcx>) -> hir::Mutability {
 617         let var_hir_id = match place.base {
 618             PlaceBase::Upvar(upvar_id) => upvar_id.var_path.hir_id,
 619             _ => unreachable!(),
 620         };
 621
 622         let bm = *self
 623             .typeck_results
 624             .borrow()
 625             .pat_binding_modes()
 626             .get(var_hir_id)
 627             .expect("missing binding mode");
 628
 629         let mut is_mutbl = match bm {
 630             ty::BindByValue(mutability) => mutability,
 631             ty::BindByReference(_) => hir::Mutability::Not,
 632         };
 633
 634         for pointer_ty in place.deref_tys() {
 635             match pointer_ty.kind() {
 636                 // We don't capture derefs of raw ptrs
 637                 ty::RawPtr(_) => unreachable!(),
 638
 639                 // Derefencing a mut-ref allows us to mut the Place if we don't deref
 640                 // an immut-ref after on top of this.
 641                 ty::Ref(.., hir::Mutability::Mut) => is_mutbl = hir::Mutability::Mut,
 642
 643                 // The place isn't mutable once we dereference a immutable reference.
 644                 ty::Ref(.., hir::Mutability::Not) => return hir::Mutability::Not,
 645
 646                 // Dereferencing a box doesn't change mutability
 647                 ty::Adt(def, ..) if def.is_box() => {}
 648
 649                 unexpected_ty => bug!("deref of unexpected pointer type {:?}", unexpected_ty),
 650             }
 651         }
 652
 653         is_mutbl
 654     }
 655 }
 656
 657 struct InferBorrowKind<'a, 'tcx> {
 658     fcx: &'a FnCtxt<'a, 'tcx>,
 659
 660     // The def-id of the closure whose kind and upvar accesses are being inferred.
 661     closure_def_id: DefId,
 662
 663     closure_span: Span,
 664
 665     capture_clause: hir::CaptureBy,
 666
 667     // The kind that we have inferred that the current closure
 668     // requires. Note that we *always* infer a minimal kind, even if
 669     // we don't always *use* that in the final result (i.e., sometimes
 670     // we've taken the closure kind from the expectations instead, and
 671     // for generators we don't even implement the closure traits
 672     // really).
 673     current_closure_kind: ty::ClosureKind,
 674
 675     // If we modified `current_closure_kind`, this field contains a `Some()` with the
 676     // variable access that caused us to do so.
 677     current_origin: Option<(Span, Place<'tcx>)>,
 678
 679     /// For each Place that is captured by the closure, we track the minimal kind of
 680     /// access we need (ref, ref mut, move, etc) and the expression that resulted in such access.
 681     ///
 682     /// Consider closure where s.str1 is captured via an ImmutableBorrow and
 683     /// s.str2 via a MutableBorrow
 684     ///
 685     /// ```rust,no_run
 686     /// struct SomeStruct { str1: String, str2: String }
 687     ///
 688     /// // Assume that the HirId for the variable definition is `V1`
 689     /// let mut s = SomeStruct { str1: format!("s1"), str2: format!("s2") }
 690     ///
 691     /// let fix_s = |new_s2| {
 692     ///     // Assume that the HirId for the expression `s.str1` is `E1`
 693     ///     println!("Updating SomeStruct with str1=", s.str1);
 694     ///     // Assume that the HirId for the expression `*s.str2` is `E2`
 695     ///     s.str2 = new_s2;
 696     /// };
 697     /// ```
 698     ///
 699     /// For closure `fix_s`, (at a high level) the map contains
 700     ///
 701     /// Place { V1, [ProjectionKind::Field(Index=0, Variant=0)] } : CaptureKind { E1, ImmutableBorrow }
 702     /// Place { V1, [ProjectionKind::Field(Index=1, Variant=0)] } : CaptureKind { E2, MutableBorrow }
 703     capture_information: FxIndexMap<Place<'tcx>, ty::CaptureInfo<'tcx>>,
 704 }
 705
 706 impl<'a, 'tcx> InferBorrowKind<'a, 'tcx> {
 707     fn adjust_upvar_borrow_kind_for_consume(
 708         &mut self,
 709         place_with_id: &PlaceWithHirId<'tcx>,
 710         diag_expr_id: hir::HirId,
 711         mode: euv::ConsumeMode,
 712     ) {
 713         debug!(
 714             "adjust_upvar_borrow_kind_for_consume(place_with_id={:?}, diag_expr_id={:?}, mode={:?})",
 715             place_with_id, diag_expr_id, mode
 716         );
 717
 718         // we only care about moves
 719         match mode {
 720             euv::Copy => {
 721                 return;
 722             }
 723             euv::Move => {}
 724         }
 725
 726         let tcx = self.fcx.tcx;
 727         let upvar_id = if let PlaceBase::Upvar(upvar_id) = place_with_id.place.base {
 728             upvar_id
 729         } else {
 730             return;
 731         };
 732
 733         debug!("adjust_upvar_borrow_kind_for_consume: upvar={:?}", upvar_id);
 734
 735         let usage_span = tcx.hir().span(diag_expr_id);
 736
 737         // To move out of an upvar, this must be a FnOnce closure
 738         self.adjust_closure_kind(
 739             upvar_id.closure_expr_id,
 740             ty::ClosureKind::FnOnce,
 741             usage_span,
 742             place_with_id.place.clone(),
 743         );
 744
 745         let capture_info = ty::CaptureInfo {
 746             capture_kind_expr_id: Some(diag_expr_id),
 747             path_expr_id: Some(diag_expr_id),
 748             capture_kind: ty::UpvarCapture::ByValue(Some(usage_span)),
 749         };
 750
 751         let curr_info = self.capture_information[&place_with_id.place];
 752         let updated_info = determine_capture_info(curr_info, capture_info);
 753
 754         self.capture_information[&place_with_id.place] = updated_info;
 755     }
 756
 757     /// Indicates that `place_with_id` is being directly mutated (e.g., assigned
 758     /// to). If the place is based on a by-ref upvar, this implies that
 759     /// the upvar must be borrowed using an `&mut` borrow.
 760     fn adjust_upvar_borrow_kind_for_mut(
 761         &mut self,
 762         place_with_id: &PlaceWithHirId<'tcx>,
 763         diag_expr_id: hir::HirId,
 764     ) {
 765         debug!(
 766             "adjust_upvar_borrow_kind_for_mut(place_with_id={:?}, diag_expr_id={:?})",
 767             place_with_id, diag_expr_id
 768         );
 769
 770         if let PlaceBase::Upvar(_) = place_with_id.place.base {
 771             let mut borrow_kind = ty::MutBorrow;
 772             for pointer_ty in place_with_id.place.deref_tys() {
 773                 match pointer_ty.kind() {
 774                     // Raw pointers don't inherit mutability.
 775                     ty::RawPtr(_) => return,
 776                     // assignment to deref of an `&mut`
 777                     // borrowed pointer implies that the
 778                     // pointer itself must be unique, but not
 779                     // necessarily *mutable*
 780                     ty::Ref(.., hir::Mutability::Mut) => borrow_kind = ty::UniqueImmBorrow,
 781                     _ => (),
 782                 }
 783             }
 784             self.adjust_upvar_deref(place_with_id, diag_expr_id, borrow_kind);
 785         }
 786     }
 787
 788     fn adjust_upvar_borrow_kind_for_unique(
 789         &mut self,
 790         place_with_id: &PlaceWithHirId<'tcx>,
 791         diag_expr_id: hir::HirId,
 792     ) {
 793         debug!(
 794             "adjust_upvar_borrow_kind_for_unique(place_with_id={:?}, diag_expr_id={:?})",
 795             place_with_id, diag_expr_id
 796         );
 797
 798         if let PlaceBase::Upvar(_) = place_with_id.place.base {
 799             if place_with_id.place.deref_tys().any(ty::TyS::is_unsafe_ptr) {
 800                 // Raw pointers don't inherit mutability.
 801                 return;
 802             }
 803             // for a borrowed pointer to be unique, its base must be unique
 804             self.adjust_upvar_deref(place_with_id, diag_expr_id, ty::UniqueImmBorrow);
 805         }
 806     }
 807
 808     fn adjust_upvar_deref(
 809         &mut self,
 810         place_with_id: &PlaceWithHirId<'tcx>,
 811         diag_expr_id: hir::HirId,
 812         borrow_kind: ty::BorrowKind,
 813     ) {
 814         assert!(match borrow_kind {
 815             ty::MutBorrow => true,
 816             ty::UniqueImmBorrow => true,
 817
 818             // imm borrows never require adjusting any kinds, so we don't wind up here
 819             ty::ImmBorrow => false,
 820         });
 821
 822         let tcx = self.fcx.tcx;
 823
 824         // if this is an implicit deref of an
 825         // upvar, then we need to modify the
 826         // borrow_kind of the upvar to make sure it
 827         // is inferred to mutable if necessary
 828         self.adjust_upvar_borrow_kind(place_with_id, diag_expr_id, borrow_kind);
 829
 830         if let PlaceBase::Upvar(upvar_id) = place_with_id.place.base {
 831             self.adjust_closure_kind(
 832                 upvar_id.closure_expr_id,
 833                 ty::ClosureKind::FnMut,
 834                 tcx.hir().span(diag_expr_id),
 835                 place_with_id.place.clone(),
 836             );
 837         }
 838     }
 839
 840     /// We infer the borrow_kind with which to borrow upvars in a stack closure.
 841     /// The borrow_kind basically follows a lattice of `imm < unique-imm < mut`,
 842     /// moving from left to right as needed (but never right to left).
 843     /// Here the argument `mutbl` is the borrow_kind that is required by
 844     /// some particular use.
 845     fn adjust_upvar_borrow_kind(
 846         &mut self,
 847         place_with_id: &PlaceWithHirId<'tcx>,
 848         diag_expr_id: hir::HirId,
 849         kind: ty::BorrowKind,
 850     ) {
 851         let curr_capture_info = self.capture_information[&place_with_id.place];
 852
 853         debug!(
 854             "adjust_upvar_borrow_kind(place={:?}, diag_expr_id={:?}, capture_info={:?}, kind={:?})",
 855             place_with_id, diag_expr_id, curr_capture_info, kind
 856         );
 857
 858         if let ty::UpvarCapture::ByValue(_) = curr_capture_info.capture_kind {
 859             // It's already captured by value, we don't need to do anything here
 860             return;
 861         } else if let ty::UpvarCapture::ByRef(curr_upvar_borrow) = curr_capture_info.capture_kind {
 862             // Use the same region as the current capture information
 863             // Doesn't matter since only one of the UpvarBorrow will be used.
 864             let new_upvar_borrow = ty::UpvarBorrow { kind, region: curr_upvar_borrow.region };
 865
 866             let capture_info = ty::CaptureInfo {
 867                 capture_kind_expr_id: Some(diag_expr_id),
 868                 path_expr_id: Some(diag_expr_id),
 869                 capture_kind: ty::UpvarCapture::ByRef(new_upvar_borrow),
 870             };
 871             let updated_info = determine_capture_info(curr_capture_info, capture_info);
 872             self.capture_information[&place_with_id.place] = updated_info;
 873         };
 874     }
 875
 876     fn adjust_closure_kind(
 877         &mut self,
 878         closure_id: LocalDefId,
 879         new_kind: ty::ClosureKind,
 880         upvar_span: Span,
 881         place: Place<'tcx>,
 882     ) {
 883         debug!(
 884             "adjust_closure_kind(closure_id={:?}, new_kind={:?}, upvar_span={:?}, place={:?})",
 885             closure_id, new_kind, upvar_span, place
 886         );
 887
 888         // Is this the closure whose kind is currently being inferred?
 889         if closure_id.to_def_id() != self.closure_def_id {
 890             debug!("adjust_closure_kind: not current closure");
 891             return;
 892         }
 893
 894         // closures start out as `Fn`.
 895         let existing_kind = self.current_closure_kind;
 896
 897         debug!(
 898             "adjust_closure_kind: closure_id={:?}, existing_kind={:?}, new_kind={:?}",
 899             closure_id, existing_kind, new_kind
 900         );
 901
 902         match (existing_kind, new_kind) {
 903             (ty::ClosureKind::Fn, ty::ClosureKind::Fn)
 904             | (ty::ClosureKind::FnMut, ty::ClosureKind::Fn | ty::ClosureKind::FnMut)
 905             | (ty::ClosureKind::FnOnce, _) => {
 906                 // no change needed
 907             }
 908
 909             (ty::ClosureKind::Fn, ty::ClosureKind::FnMut | ty::ClosureKind::FnOnce)
 910             | (ty::ClosureKind::FnMut, ty::ClosureKind::FnOnce) => {
 911                 // new kind is stronger than the old kind
 912                 self.current_closure_kind = new_kind;
 913                 self.current_origin = Some((upvar_span, place));
 914             }
 915         }
 916     }
 917
 918     fn init_capture_info_for_place(
 919         &mut self,
 920         place_with_id: &PlaceWithHirId<'tcx>,
 921         diag_expr_id: hir::HirId,
 922     ) {
 923         if let PlaceBase::Upvar(upvar_id) = place_with_id.place.base {
 924             assert_eq!(self.closure_def_id.expect_local(), upvar_id.closure_expr_id);
 925
 926             let capture_kind =
 927                 self.fcx.init_capture_kind(self.capture_clause, upvar_id, self.closure_span);
 928
 929             let expr_id = Some(diag_expr_id);
 930             let capture_info = ty::CaptureInfo {
 931                 capture_kind_expr_id: expr_id,
 932                 path_expr_id: expr_id,
 933                 capture_kind,
 934             };
 935
 936             debug!("Capturing new place {:?}, capture_info={:?}", place_with_id, capture_info);
 937
 938             self.capture_information.insert(place_with_id.place.clone(), capture_info);
 939         } else {
 940             debug!("Not upvar: {:?}", place_with_id);
 941         }
 942     }
 943 }
 944
 945 impl<'a, 'tcx> euv::Delegate<'tcx> for InferBorrowKind<'a, 'tcx> {
 946     fn consume(
 947         &mut self,
 948         place_with_id: &PlaceWithHirId<'tcx>,
 949         diag_expr_id: hir::HirId,
 950         mode: euv::ConsumeMode,
 951     ) {
 952         debug!(
 953             "consume(place_with_id={:?}, diag_expr_id={:?}, mode={:?})",
 954             place_with_id, diag_expr_id, mode
 955         );
 956         if !self.capture_information.contains_key(&place_with_id.place) {
 957             self.init_capture_info_for_place(place_with_id, diag_expr_id);
 958         }
 959
 960         self.adjust_upvar_borrow_kind_for_consume(place_with_id, diag_expr_id, mode);
 961     }
 962
 963     fn borrow(
 964         &mut self,
 965         place_with_id: &PlaceWithHirId<'tcx>,
 966         diag_expr_id: hir::HirId,
 967         bk: ty::BorrowKind,
 968     ) {
 969         debug!(
 970             "borrow(place_with_id={:?}, diag_expr_id={:?}, bk={:?})",
 971             place_with_id, diag_expr_id, bk
 972         );
 973
 974         if !self.capture_information.contains_key(&place_with_id.place) {
 975             self.init_capture_info_for_place(place_with_id, diag_expr_id);
 976         }
 977
 978         match bk {
 979             ty::ImmBorrow => {}
 980             ty::UniqueImmBorrow => {
 981                 self.adjust_upvar_borrow_kind_for_unique(&place_with_id, diag_expr_id);
 982             }
 983             ty::MutBorrow => {
 984                 self.adjust_upvar_borrow_kind_for_mut(&place_with_id, diag_expr_id);
 985             }
 986         }
 987     }
 988
 989     fn mutate(&mut self, assignee_place: &PlaceWithHirId<'tcx>, diag_expr_id: hir::HirId) {
 990         debug!("mutate(assignee_place={:?}, diag_expr_id={:?})", assignee_place, diag_expr_id);
 991
 992         if !self.capture_information.contains_key(&assignee_place.place) {
 993             self.init_capture_info_for_place(assignee_place, diag_expr_id);
 994         }
 995
 996         self.adjust_upvar_borrow_kind_for_mut(assignee_place, diag_expr_id);
 997     }
 998 }
 999
1000 /// Truncate projections so that following rules are obeyed by the captured `place`:
1001 ///
1002 /// - No Derefs in move closure, this will result in value behind a reference getting moved.
1003 /// - No projections are applied to raw pointers, since these require unsafe blocks. We capture
1004 ///   them completely.
1005 /// - No Index projections are captured, since arrays are captured completely.
1006 fn restrict_capture_precision<'tcx>(
1007     mut place: Place<'tcx>,
1008     capture_kind: ty::UpvarCapture<'tcx>,
1009 ) -> Place<'tcx> {
1010     if place.projections.is_empty() {
1011         // Nothing to do here
1012         return place;
1013     }
1014
1015     if place.base_ty.is_unsafe_ptr() {
1016         place.projections.truncate(0);
1017         return place;
1018     }
1019
1020     let mut truncated_length = usize::MAX;
1021     let mut first_deref_projection = usize::MAX;
1022
1023     for (i, proj) in place.projections.iter().enumerate() {
1024         if proj.ty.is_unsafe_ptr() {
1025             // Don't apply any projections on top of an unsafe ptr
1026             truncated_length = truncated_length.min(i + 1);
1027             break;
1028         }
1029         match proj.kind {
1030             ProjectionKind::Index => {
1031                 // Arrays are completely captured, so we drop Index projections
1032                 truncated_length = truncated_length.min(i);
1033                 break;
1034             }
1035             ProjectionKind::Deref => {
1036                 // We only drop Derefs in case of move closures
1037                 // There might be an index projection or raw ptr ahead, so we don't stop here.
1038                 first_deref_projection = first_deref_projection.min(i);
1039             }
1040             ProjectionKind::Field(..) => {} // ignore
1041             ProjectionKind::Subslice => {}  // We never capture this
1042         }
1043     }
1044
1045     let length = place
1046         .projections
1047         .len()
1048         .min(truncated_length)
1049         // In case of capture `ByValue` we want to not capture derefs
1050         .min(match capture_kind {
1051             ty::UpvarCapture::ByValue(..) => first_deref_projection,
1052             ty::UpvarCapture::ByRef(..) => usize::MAX,
1053         });
1054
1055     place.projections.truncate(length);
1056
1057     place
1058 }
1059
1060 fn construct_place_string(tcx: TyCtxt<'_>, place: &Place<'tcx>) -> String {
1061     let variable_name = match place.base {
1062         PlaceBase::Upvar(upvar_id) => var_name(tcx, upvar_id.var_path.hir_id).to_string(),
1063         _ => bug!("Capture_information should only contain upvars"),
1064     };
1065
1066     let mut projections_str = String::new();
1067     for (i, item) in place.projections.iter().enumerate() {
1068         let proj = match item.kind {
1069             ProjectionKind::Field(a, b) => format!("({:?}, {:?})", a, b),
1070             ProjectionKind::Deref => String::from("Deref"),
1071             ProjectionKind::Index => String::from("Index"),
1072             ProjectionKind::Subslice => String::from("Subslice"),
1073         };
1074         if i != 0 {
1075             projections_str.push_str(",");
1076         }
1077         projections_str.push_str(proj.as_str());
1078     }
1079
1080     format!("{}[{}]", variable_name, projections_str)
1081 }
1082
1083 fn construct_capture_kind_reason_string(
1084     tcx: TyCtxt<'_>,
1085     place: &Place<'tcx>,
1086     capture_info: &ty::CaptureInfo<'tcx>,
1087 ) -> String {
1088     let place_str = construct_place_string(tcx, &place);
1089
1090     let capture_kind_str = match capture_info.capture_kind {
1091         ty::UpvarCapture::ByValue(_) => "ByValue".into(),
1092         ty::UpvarCapture::ByRef(borrow) => format!("{:?}", borrow.kind),
1093     };
1094
1095     format!("{} captured as {} here", place_str, capture_kind_str)
1096 }
1097
1098 fn construct_path_string(tcx: TyCtxt<'_>, place: &Place<'tcx>) -> String {
1099     let place_str = construct_place_string(tcx, &place);
1100
1101     format!("{} used here", place_str)
1102 }
1103
1104 fn construct_capture_info_string(
1105     tcx: TyCtxt<'_>,
1106     place: &Place<'tcx>,
1107     capture_info: &ty::CaptureInfo<'tcx>,
1108 ) -> String {
1109     let place_str = construct_place_string(tcx, &place);
1110
1111     let capture_kind_str = match capture_info.capture_kind {
1112         ty::UpvarCapture::ByValue(_) => "ByValue".into(),
1113         ty::UpvarCapture::ByRef(borrow) => format!("{:?}", borrow.kind),
1114     };
1115     format!("{} -> {}", place_str, capture_kind_str)
1116 }
1117
1118 fn var_name(tcx: TyCtxt<'_>, var_hir_id: hir::HirId) -> Symbol {
1119     tcx.hir().name(var_hir_id)
1120 }
1121
1122 /// Helper function to determine if we need to escalate CaptureKind from
1123 /// CaptureInfo A to B and returns the escalated CaptureInfo.
1124 /// (Note: CaptureInfo contains CaptureKind and an expression that led to capture it in that way)
1125 ///
1126 /// If both `CaptureKind`s are considered equivalent, then the CaptureInfo is selected based
1127 /// on the `CaptureInfo` containing an associated `capture_kind_expr_id`.
1128 ///
1129 /// It is the caller's duty to figure out which path_expr_id to use.
1130 ///
1131 /// If both the CaptureKind and Expression are considered to be equivalent,
1132 /// then `CaptureInfo` A is preferred. This can be useful in cases where we want to priortize
1133 /// expressions reported back to the user as part of diagnostics based on which appears earlier
1134 /// in the closure. This can be acheived simply by calling
1135 /// `determine_capture_info(existing_info, current_info)`. This works out because the
1136 /// expressions that occur earlier in the closure body than the current expression are processed before.
1137 /// Consider the following example
1138 /// ```rust,no_run
1139 /// struct Point { x: i32, y: i32 }
1140 /// let mut p: Point { x: 10, y: 10 };
1141 ///
1142 /// let c = || {
1143 ///     p.x     += 10;
1144 /// // ^ E1 ^
1145 ///     // ...
1146 ///     // More code
1147 ///     // ...
1148 ///     p.x += 10; // E2
1149 /// // ^ E2 ^
1150 /// };
1151 /// ```
1152 /// `CaptureKind` associated with both `E1` and `E2` will be ByRef(MutBorrow),
1153 /// and both have an expression associated, however for diagnostics we prefer reporting
1154 /// `E1` since it appears earlier in the closure body. When `E2` is being processed we
1155 /// would've already handled `E1`, and have an existing capture_information for it.
1156 /// Calling `determine_capture_info(existing_info_e1, current_info_e2)` will return
1157 /// `existing_info_e1` in this case, allowing us to point to `E1` in case of diagnostics.
1158 fn determine_capture_info(
1159     capture_info_a: ty::CaptureInfo<'tcx>,
1160     capture_info_b: ty::CaptureInfo<'tcx>,
1161 ) -> ty::CaptureInfo<'tcx> {
1162     // If the capture kind is equivalent then, we don't need to escalate and can compare the
1163     // expressions.
1164     let eq_capture_kind = match (capture_info_a.capture_kind, capture_info_b.capture_kind) {
1165         (ty::UpvarCapture::ByValue(_), ty::UpvarCapture::ByValue(_)) => {
1166             // We don't need to worry about the spans being ignored here.
1167             //
1168             // The expr_id in capture_info corresponds to the span that is stored within
1169             // ByValue(span) and therefore it gets handled with priortizing based on
1170             // expressions below.
1171             true
1172         }
1173         (ty::UpvarCapture::ByRef(ref_a), ty::UpvarCapture::ByRef(ref_b)) => {
1174             ref_a.kind == ref_b.kind
1175         }
1176         (ty::UpvarCapture::ByValue(_), _) | (ty::UpvarCapture::ByRef(_), _) => false,
1177     };
1178
1179     if eq_capture_kind {
1180         match (capture_info_a.capture_kind_expr_id, capture_info_b.capture_kind_expr_id) {
1181             (Some(_), _) | (None, None) => capture_info_a,
1182             (None, Some(_)) => capture_info_b,
1183         }
1184     } else {
1185         // We select the CaptureKind which ranks higher based the following priority order:
1186         // ByValue > MutBorrow > UniqueImmBorrow > ImmBorrow
1187         match (capture_info_a.capture_kind, capture_info_b.capture_kind) {
1188             (ty::UpvarCapture::ByValue(_), _) => capture_info_a,
1189             (_, ty::UpvarCapture::ByValue(_)) => capture_info_b,
1190             (ty::UpvarCapture::ByRef(ref_a), ty::UpvarCapture::ByRef(ref_b)) => {
1191                 match (ref_a.kind, ref_b.kind) {
1192                     // Take LHS:
1193                     (ty::UniqueImmBorrow | ty::MutBorrow, ty::ImmBorrow)
1194                     | (ty::MutBorrow, ty::UniqueImmBorrow) => capture_info_a,
1195
1196                     // Take RHS:
1197                     (ty::ImmBorrow, ty::UniqueImmBorrow | ty::MutBorrow)
1198                     | (ty::UniqueImmBorrow, ty::MutBorrow) => capture_info_b,
1199
1200                     (ty::ImmBorrow, ty::ImmBorrow)
1201                     | (ty::UniqueImmBorrow, ty::UniqueImmBorrow)
1202                     | (ty::MutBorrow, ty::MutBorrow) => {
1203                         bug!("Expected unequal capture kinds");
1204                     }
1205                 }
1206             }
1207         }
1208     }
1209 }
1210
1211 /// Determines the Ancestry relationship of Place A relative to Place B
1212 ///
1213 /// `PlaceAncestryRelation::Ancestor` implies Place A is ancestor of Place B
1214 /// `PlaceAncestryRelation::Descendant` implies Place A is descendant of Place B
1215 /// `PlaceAncestryRelation::Divergent` implies neither of them is the ancestor of the other.
1216 fn determine_place_ancestry_relation(
1217     place_a: &Place<'tcx>,
1218     place_b: &Place<'tcx>,
1219 ) -> PlaceAncestryRelation {
1220     // If Place A and Place B, don't start off from the same root variable, they are divergent.
1221     if place_a.base != place_b.base {
1222         return PlaceAncestryRelation::Divergent;
1223     }
1224
1225     // Assume of length of projections_a = n
1226     let projections_a = &place_a.projections;
1227
1228     // Assume of length of projections_b = m
1229     let projections_b = &place_b.projections;
1230
1231     let mut same_initial_projections = true;
1232
1233     for (proj_a, proj_b) in projections_a.iter().zip(projections_b.iter()) {
1234         if proj_a != proj_b {
1235             same_initial_projections = false;
1236             break;
1237         }
1238     }
1239
1240     if same_initial_projections {
1241         // First min(n, m) projections are the same
1242         // Select Ancestor/Descendant
1243         if projections_b.len() >= projections_a.len() {
1244             PlaceAncestryRelation::Ancestor
1245         } else {
1246             PlaceAncestryRelation::Descendant
1247         }
1248     } else {
1249         PlaceAncestryRelation::Divergent
1250     }
1251 }