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::{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 { expr_id: None, capture_kind };
 139
 140                     capture_information.insert(place, info);
 141                 }
 142             }
 143         }
 144
 145         let body_owner_def_id = self.tcx.hir().body_owner_def_id(body.id());
 146         assert_eq!(body_owner_def_id.to_def_id(), closure_def_id);
 147         let mut delegate = InferBorrowKind {
 148             fcx: self,
 149             closure_def_id,
 150             closure_span: span,
 151             capture_clause,
 152             current_closure_kind: ty::ClosureKind::LATTICE_BOTTOM,
 153             current_origin: None,
 154             capture_information,
 155         };
 156         euv::ExprUseVisitor::new(
 157             &mut delegate,
 158             &self.infcx,
 159             body_owner_def_id,
 160             self.param_env,
 161             &self.typeck_results.borrow(),
 162         )
 163         .consume_body(body);
 164
 165         debug!(
 166             "For closure={:?}, capture_information={:#?}",
 167             closure_def_id, delegate.capture_information
 168         );
 169         self.log_capture_analysis_first_pass(closure_def_id, &delegate.capture_information, span);
 170
 171         if let Some(closure_substs) = infer_kind {
 172             // Unify the (as yet unbound) type variable in the closure
 173             // substs with the kind we inferred.
 174             let inferred_kind = delegate.current_closure_kind;
 175             let closure_kind_ty = closure_substs.as_closure().kind_ty();
 176             self.demand_eqtype(span, inferred_kind.to_ty(self.tcx), closure_kind_ty);
 177
 178             // If we have an origin, store it.
 179             if let Some(origin) = delegate.current_origin {
 180                 self.typeck_results
 181                     .borrow_mut()
 182                     .closure_kind_origins_mut()
 183                     .insert(closure_hir_id, origin);
 184             }
 185         }
 186
 187         self.compute_min_captures(closure_def_id, delegate);
 188         self.log_closure_min_capture_info(closure_def_id, span);
 189
 190         self.min_captures_to_closure_captures_bridge(closure_def_id);
 191
 192         // Now that we've analyzed the closure, we know how each
 193         // variable is borrowed, and we know what traits the closure
 194         // implements (Fn vs FnMut etc). We now have some updates to do
 195         // with that information.
 196         //
 197         // Note that no closure type C may have an upvar of type C
 198         // (though it may reference itself via a trait object). This
 199         // results from the desugaring of closures to a struct like
 200         // `Foo<..., UV0...UVn>`. If one of those upvars referenced
 201         // C, then the type would have infinite size (and the
 202         // inference algorithm will reject it).
 203
 204         // Equate the type variables for the upvars with the actual types.
 205         let final_upvar_tys = self.final_upvar_tys(closure_hir_id);
 206         debug!(
 207             "analyze_closure: id={:?} substs={:?} final_upvar_tys={:?}",
 208             closure_hir_id, substs, final_upvar_tys
 209         );
 210
 211         // Build a tuple (U0..Un) of the final upvar types U0..Un
 212         // and unify the upvar tupe type in the closure with it:
 213         let final_tupled_upvars_type = self.tcx.mk_tup(final_upvar_tys.iter());
 214         self.demand_suptype(span, substs.tupled_upvars_ty(), final_tupled_upvars_type);
 215
 216         // If we are also inferred the closure kind here,
 217         // process any deferred resolutions.
 218         let deferred_call_resolutions = self.remove_deferred_call_resolutions(closure_def_id);
 219         for deferred_call_resolution in deferred_call_resolutions {
 220             deferred_call_resolution.resolve(self);
 221         }
 222     }
 223
 224     // Returns a list of `Ty`s for each upvar.
 225     fn final_upvar_tys(&self, closure_id: hir::HirId) -> Vec<Ty<'tcx>> {
 226         // Presently an unboxed closure type cannot "escape" out of a
 227         // function, so we will only encounter ones that originated in the
 228         // local crate or were inlined into it along with some function.
 229         // This may change if abstract return types of some sort are
 230         // implemented.
 231         let tcx = self.tcx;
 232         let closure_def_id = tcx.hir().local_def_id(closure_id);
 233
 234         self.typeck_results
 235             .borrow()
 236             .closure_captures
 237             .get(&closure_def_id.to_def_id())
 238             .iter()
 239             .flat_map(|upvars| {
 240                 upvars.iter().map(|(&var_hir_id, _)| {
 241                     let upvar_ty = self.node_ty(var_hir_id);
 242                     let upvar_id = ty::UpvarId::new(var_hir_id, closure_def_id);
 243                     let capture = self.typeck_results.borrow().upvar_capture(upvar_id);
 244
 245                     debug!("var_id={:?} upvar_ty={:?} capture={:?}", var_hir_id, upvar_ty, capture);
 246
 247                     match capture {
 248                         ty::UpvarCapture::ByValue(_) => upvar_ty,
 249                         ty::UpvarCapture::ByRef(borrow) => tcx.mk_ref(
 250                             borrow.region,
 251                             ty::TypeAndMut { ty: upvar_ty, mutbl: borrow.kind.to_mutbl_lossy() },
 252                         ),
 253                     }
 254                 })
 255             })
 256             .collect()
 257     }
 258
 259     /// Bridge for closure analysis
 260     /// ----------------------------
 261     ///
 262     /// For closure with DefId `c`, the bridge converts structures required for supporting RFC 2229,
 263     /// to structures currently used in the compiler for handling closure captures.
 264     ///
 265     /// For example the following structure will be converted:
 266     ///
 267     /// closure_min_captures
 268     /// foo -> [ {foo.x, ImmBorrow}, {foo.y, MutBorrow} ]
 269     /// bar -> [ {bar.z, ByValue}, {bar.q, MutBorrow} ]
 270     ///
 271     /// to
 272     ///
 273     /// 1. closure_captures
 274     /// foo -> UpvarId(foo, c), bar -> UpvarId(bar, c)
 275     ///
 276     /// 2. upvar_capture_map
 277     /// UpvarId(foo,c) -> MutBorrow, UpvarId(bar, c) -> ByValue
 278     fn min_captures_to_closure_captures_bridge(&self, closure_def_id: DefId) {
 279         let mut closure_captures: FxIndexMap<hir::HirId, ty::UpvarId> = Default::default();
 280         let mut upvar_capture_map = ty::UpvarCaptureMap::default();
 281
 282         if let Some(min_captures) =
 283             self.typeck_results.borrow().closure_min_captures.get(&closure_def_id)
 284         {
 285             for (var_hir_id, min_list) in min_captures.iter() {
 286                 for captured_place in min_list {
 287                     let place = &captured_place.place;
 288                     let capture_info = captured_place.info;
 289
 290                     let upvar_id = match place.base {
 291                         PlaceBase::Upvar(upvar_id) => upvar_id,
 292                         base => bug!("Expected upvar, found={:?}", base),
 293                     };
 294
 295                     assert_eq!(upvar_id.var_path.hir_id, *var_hir_id);
 296                     assert_eq!(upvar_id.closure_expr_id, closure_def_id.expect_local());
 297
 298                     closure_captures.insert(*var_hir_id, upvar_id);
 299
 300                     let new_capture_kind = if let Some(capture_kind) =
 301                         upvar_capture_map.get(&upvar_id)
 302                     {
 303                         // upvar_capture_map only stores the UpvarCapture (CaptureKind),
 304                         // so we create a fake capture info with no expression.
 305                         let fake_capture_info =
 306                             ty::CaptureInfo { expr_id: None, capture_kind: capture_kind.clone() };
 307                         determine_capture_info(fake_capture_info, capture_info).capture_kind
 308                     } else {
 309                         capture_info.capture_kind
 310                     };
 311                     upvar_capture_map.insert(upvar_id, new_capture_kind);
 312                 }
 313             }
 314         }
 315         debug!("For closure_def_id={:?}, closure_captures={:#?}", closure_def_id, closure_captures);
 316         debug!(
 317             "For closure_def_id={:?}, upvar_capture_map={:#?}",
 318             closure_def_id, upvar_capture_map
 319         );
 320
 321         if !closure_captures.is_empty() {
 322             self.typeck_results
 323                 .borrow_mut()
 324                 .closure_captures
 325                 .insert(closure_def_id, closure_captures);
 326
 327             self.typeck_results.borrow_mut().upvar_capture_map.extend(upvar_capture_map);
 328         }
 329     }
 330
 331     /// Analyzes the information collected by `InferBorrowKind` to compute the min number of
 332     /// Places (and corresponding capture kind) that we need to keep track of to support all
 333     /// the required captured paths.
 334     ///
 335     /// Eg:
 336     /// ```rust,no_run
 337     /// struct Point { x: i32, y: i32 }
 338     ///
 339     /// let s: String;  // hir_id_s
 340     /// let mut p: Point; // his_id_p
 341     /// let c = || {
 342     ///        println!("{}", s);  // L1
 343     ///        p.x += 10;  // L2
 344     ///        println!("{}" , p.y) // L3
 345     ///        println!("{}", p) // L4
 346     ///        drop(s);   // L5
 347     /// };
 348     /// ```
 349     /// and let hir_id_L1..5 be the expressions pointing to use of a captured variable on
 350     /// the lines L1..5 respectively.
 351     ///
 352     /// InferBorrowKind results in a structure like this:
 353     ///
 354     /// ```
 355     /// {
 356     ///       Place(base: hir_id_s, projections: [], ....) -> (hir_id_L5, ByValue),
 357     ///       Place(base: hir_id_p, projections: [Field(0, 0)], ...) -> (hir_id_L2, ByRef(MutBorrow))
 358     ///       Place(base: hir_id_p, projections: [Field(1, 0)], ...) -> (hir_id_L3, ByRef(ImmutBorrow))
 359     ///       Place(base: hir_id_p, projections: [], ...) -> (hir_id_L4, ByRef(ImmutBorrow))
 360     /// ```
 361     ///
 362     /// After the min capture analysis, we get:
 363     /// ```
 364     /// {
 365     ///       hir_id_s -> [
 366     ///            Place(base: hir_id_s, projections: [], ....) -> (hir_id_L4, ByValue)
 367     ///       ],
 368     ///       hir_id_p -> [
 369     ///            Place(base: hir_id_p, projections: [], ...) -> (hir_id_L2, ByRef(MutBorrow)),
 370     ///       ],
 371     /// ```
 372     fn compute_min_captures(
 373         &self,
 374         closure_def_id: DefId,
 375         inferred_info: InferBorrowKind<'_, 'tcx>,
 376     ) {
 377         let mut root_var_min_capture_list: ty::RootVariableMinCaptureList<'_> = Default::default();
 378
 379         for (place, capture_info) in inferred_info.capture_information.into_iter() {
 380             let var_hir_id = match place.base {
 381                 PlaceBase::Upvar(upvar_id) => upvar_id.var_path.hir_id,
 382                 base => bug!("Expected upvar, found={:?}", base),
 383             };
 384
 385             // Arrays are captured in entirety, drop Index projections and projections
 386             // after Index projections.
 387             let first_index_projection =
 388                 place.projections.split(|proj| ProjectionKind::Index == proj.kind).next();
 389             let place = Place {
 390                 base_ty: place.base_ty,
 391                 base: place.base,
 392                 projections: first_index_projection.map_or(Vec::new(), |p| p.to_vec()),
 393             };
 394
 395             let min_cap_list = match root_var_min_capture_list.get_mut(&var_hir_id) {
 396                 None => {
 397                     let min_cap_list = vec![ty::CapturedPlace { place: place, info: capture_info }];
 398                     root_var_min_capture_list.insert(var_hir_id, min_cap_list);
 399                     continue;
 400                 }
 401                 Some(min_cap_list) => min_cap_list,
 402             };
 403
 404             // Go through each entry in the current list of min_captures
 405             // - if ancestor is found, update it's capture kind to account for current place's
 406             // capture information.
 407             //
 408             // - if descendant is found, remove it from the list, and update the current place's
 409             // capture information to account for the descendants's capture kind.
 410             //
 411             // We can never be in a case where the list contains both an ancestor and a descendant
 412             // Also there can only be ancestor but in case of descendants there might be
 413             // multiple.
 414
 415             let mut descendant_found = false;
 416             let mut updated_capture_info = capture_info;
 417             min_cap_list.retain(|possible_descendant| {
 418                 match determine_place_ancestry_relation(&place, &possible_descendant.place) {
 419                     // current place is ancestor of possible_descendant
 420                     PlaceAncestryRelation::Ancestor => {
 421                         descendant_found = true;
 422                         updated_capture_info =
 423                             determine_capture_info(updated_capture_info, possible_descendant.info);
 424                         false
 425                     }
 426
 427                     _ => true,
 428                 }
 429             });
 430
 431             let mut ancestor_found = false;
 432             if !descendant_found {
 433                 for possible_ancestor in min_cap_list.iter_mut() {
 434                     match determine_place_ancestry_relation(&place, &possible_ancestor.place) {
 435                         // current place is descendant of possible_ancestor
 436                         PlaceAncestryRelation::Descendant => {
 437                             ancestor_found = true;
 438                             possible_ancestor.info =
 439                                 determine_capture_info(possible_ancestor.info, capture_info);
 440
 441                             // Only one ancestor of the current place will be in the list.
 442                             break;
 443                         }
 444                         _ => {}
 445                     }
 446                 }
 447             }
 448
 449             // Only need to insert when we don't have an ancestor in the existing min capture list
 450             if !ancestor_found {
 451                 let captured_place =
 452                     ty::CapturedPlace { place: place.clone(), info: updated_capture_info };
 453                 min_cap_list.push(captured_place);
 454             }
 455         }
 456
 457         debug!("For closure={:?}, min_captures={:#?}", closure_def_id, root_var_min_capture_list);
 458
 459         if !root_var_min_capture_list.is_empty() {
 460             self.typeck_results
 461                 .borrow_mut()
 462                 .closure_min_captures
 463                 .insert(closure_def_id, root_var_min_capture_list);
 464         }
 465     }
 466
 467     fn init_capture_kind(
 468         &self,
 469         capture_clause: hir::CaptureBy,
 470         upvar_id: ty::UpvarId,
 471         closure_span: Span,
 472     ) -> ty::UpvarCapture<'tcx> {
 473         match capture_clause {
 474             hir::CaptureBy::Value => ty::UpvarCapture::ByValue(None),
 475             hir::CaptureBy::Ref => {
 476                 let origin = UpvarRegion(upvar_id, closure_span);
 477                 let upvar_region = self.next_region_var(origin);
 478                 let upvar_borrow = ty::UpvarBorrow { kind: ty::ImmBorrow, region: upvar_region };
 479                 ty::UpvarCapture::ByRef(upvar_borrow)
 480             }
 481         }
 482     }
 483
 484     fn place_for_root_variable(
 485         &self,
 486         closure_def_id: LocalDefId,
 487         var_hir_id: hir::HirId,
 488     ) -> Place<'tcx> {
 489         let upvar_id = ty::UpvarId::new(var_hir_id, closure_def_id);
 490
 491         Place {
 492             base_ty: self.node_ty(var_hir_id),
 493             base: PlaceBase::Upvar(upvar_id),
 494             projections: Default::default(),
 495         }
 496     }
 497
 498     fn should_log_capture_analysis(&self, closure_def_id: DefId) -> bool {
 499         self.tcx.has_attr(closure_def_id, sym::rustc_capture_analysis)
 500     }
 501
 502     fn log_capture_analysis_first_pass(
 503         &self,
 504         closure_def_id: rustc_hir::def_id::DefId,
 505         capture_information: &FxIndexMap<Place<'tcx>, ty::CaptureInfo<'tcx>>,
 506         closure_span: Span,
 507     ) {
 508         if self.should_log_capture_analysis(closure_def_id) {
 509             let mut diag =
 510                 self.tcx.sess.struct_span_err(closure_span, "First Pass analysis includes:");
 511             for (place, capture_info) in capture_information {
 512                 let capture_str = construct_capture_info_string(self.tcx, place, capture_info);
 513                 let output_str = format!("Capturing {}", capture_str);
 514
 515                 let span = capture_info.expr_id.map_or(closure_span, |e| self.tcx.hir().span(e));
 516                 diag.span_note(span, &output_str);
 517             }
 518             diag.emit();
 519         }
 520     }
 521
 522     fn log_closure_min_capture_info(&self, closure_def_id: DefId, closure_span: Span) {
 523         if self.should_log_capture_analysis(closure_def_id) {
 524             if let Some(min_captures) =
 525                 self.typeck_results.borrow().closure_min_captures.get(&closure_def_id)
 526             {
 527                 let mut diag =
 528                     self.tcx.sess.struct_span_err(closure_span, "Min Capture analysis includes:");
 529
 530                 for (_, min_captures_for_var) in min_captures {
 531                     for capture in min_captures_for_var {
 532                         let place = &capture.place;
 533                         let capture_info = &capture.info;
 534
 535                         let capture_str =
 536                             construct_capture_info_string(self.tcx, place, capture_info);
 537                         let output_str = format!("Min Capture {}", capture_str);
 538
 539                         let span =
 540                             capture_info.expr_id.map_or(closure_span, |e| self.tcx.hir().span(e));
 541                         diag.span_note(span, &output_str);
 542                     }
 543                 }
 544                 diag.emit();
 545             }
 546         }
 547     }
 548 }
 549
 550 struct InferBorrowKind<'a, 'tcx> {
 551     fcx: &'a FnCtxt<'a, 'tcx>,
 552
 553     // The def-id of the closure whose kind and upvar accesses are being inferred.
 554     closure_def_id: DefId,
 555
 556     closure_span: Span,
 557
 558     capture_clause: hir::CaptureBy,
 559
 560     // The kind that we have inferred that the current closure
 561     // requires. Note that we *always* infer a minimal kind, even if
 562     // we don't always *use* that in the final result (i.e., sometimes
 563     // we've taken the closure kind from the expectations instead, and
 564     // for generators we don't even implement the closure traits
 565     // really).
 566     current_closure_kind: ty::ClosureKind,
 567
 568     // If we modified `current_closure_kind`, this field contains a `Some()` with the
 569     // variable access that caused us to do so.
 570     current_origin: Option<(Span, Symbol)>,
 571
 572     /// For each Place that is captured by the closure, we track the minimal kind of
 573     /// access we need (ref, ref mut, move, etc) and the expression that resulted in such access.
 574     ///
 575     /// Consider closure where s.str1 is captured via an ImmutableBorrow and
 576     /// s.str2 via a MutableBorrow
 577     ///
 578     /// ```rust,no_run
 579     /// struct SomeStruct { str1: String, str2: String }
 580     ///
 581     /// // Assume that the HirId for the variable definition is `V1`
 582     /// let mut s = SomeStruct { str1: format!("s1"), str2: format!("s2") }
 583     ///
 584     /// let fix_s = |new_s2| {
 585     ///     // Assume that the HirId for the expression `s.str1` is `E1`
 586     ///     println!("Updating SomeStruct with str1=", s.str1);
 587     ///     // Assume that the HirId for the expression `*s.str2` is `E2`
 588     ///     s.str2 = new_s2;
 589     /// };
 590     /// ```
 591     ///
 592     /// For closure `fix_s`, (at a high level) the map contains
 593     ///
 594     /// Place { V1, [ProjectionKind::Field(Index=0, Variant=0)] } : CaptureKind { E1, ImmutableBorrow }
 595     /// Place { V1, [ProjectionKind::Field(Index=1, Variant=0)] } : CaptureKind { E2, MutableBorrow }
 596     capture_information: FxIndexMap<Place<'tcx>, ty::CaptureInfo<'tcx>>,
 597 }
 598
 599 impl<'a, 'tcx> InferBorrowKind<'a, 'tcx> {
 600     fn adjust_upvar_borrow_kind_for_consume(
 601         &mut self,
 602         place_with_id: &PlaceWithHirId<'tcx>,
 603         diag_expr_id: hir::HirId,
 604         mode: euv::ConsumeMode,
 605     ) {
 606         debug!(
 607             "adjust_upvar_borrow_kind_for_consume(place_with_id={:?}, diag_expr_id={:?}, mode={:?})",
 608             place_with_id, diag_expr_id, mode
 609         );
 610
 611         // we only care about moves
 612         match mode {
 613             euv::Copy => {
 614                 return;
 615             }
 616             euv::Move => {}
 617         }
 618
 619         let tcx = self.fcx.tcx;
 620         let upvar_id = if let PlaceBase::Upvar(upvar_id) = place_with_id.place.base {
 621             upvar_id
 622         } else {
 623             return;
 624         };
 625
 626         debug!("adjust_upvar_borrow_kind_for_consume: upvar={:?}", upvar_id);
 627
 628         let usage_span = tcx.hir().span(diag_expr_id);
 629
 630         // To move out of an upvar, this must be a FnOnce closure
 631         self.adjust_closure_kind(
 632             upvar_id.closure_expr_id,
 633             ty::ClosureKind::FnOnce,
 634             usage_span,
 635             var_name(tcx, upvar_id.var_path.hir_id),
 636         );
 637
 638         let capture_info = ty::CaptureInfo {
 639             expr_id: Some(diag_expr_id),
 640             capture_kind: ty::UpvarCapture::ByValue(Some(usage_span)),
 641         };
 642
 643         let curr_info = self.capture_information[&place_with_id.place];
 644         let updated_info = determine_capture_info(curr_info, capture_info);
 645
 646         self.capture_information[&place_with_id.place] = updated_info;
 647     }
 648
 649     /// Indicates that `place_with_id` is being directly mutated (e.g., assigned
 650     /// to). If the place is based on a by-ref upvar, this implies that
 651     /// the upvar must be borrowed using an `&mut` borrow.
 652     fn adjust_upvar_borrow_kind_for_mut(
 653         &mut self,
 654         place_with_id: &PlaceWithHirId<'tcx>,
 655         diag_expr_id: hir::HirId,
 656     ) {
 657         debug!(
 658             "adjust_upvar_borrow_kind_for_mut(place_with_id={:?}, diag_expr_id={:?})",
 659             place_with_id, diag_expr_id
 660         );
 661
 662         if let PlaceBase::Upvar(_) = place_with_id.place.base {
 663             let mut borrow_kind = ty::MutBorrow;
 664             for pointer_ty in place_with_id.place.deref_tys() {
 665                 match pointer_ty.kind() {
 666                     // Raw pointers don't inherit mutability.
 667                     ty::RawPtr(_) => return,
 668                     // assignment to deref of an `&mut`
 669                     // borrowed pointer implies that the
 670                     // pointer itself must be unique, but not
 671                     // necessarily *mutable*
 672                     ty::Ref(.., hir::Mutability::Mut) => borrow_kind = ty::UniqueImmBorrow,
 673                     _ => (),
 674                 }
 675             }
 676             self.adjust_upvar_deref(place_with_id, diag_expr_id, borrow_kind);
 677         }
 678     }
 679
 680     fn adjust_upvar_borrow_kind_for_unique(
 681         &mut self,
 682         place_with_id: &PlaceWithHirId<'tcx>,
 683         diag_expr_id: hir::HirId,
 684     ) {
 685         debug!(
 686             "adjust_upvar_borrow_kind_for_unique(place_with_id={:?}, diag_expr_id={:?})",
 687             place_with_id, diag_expr_id
 688         );
 689
 690         if let PlaceBase::Upvar(_) = place_with_id.place.base {
 691             if place_with_id.place.deref_tys().any(ty::TyS::is_unsafe_ptr) {
 692                 // Raw pointers don't inherit mutability.
 693                 return;
 694             }
 695             // for a borrowed pointer to be unique, its base must be unique
 696             self.adjust_upvar_deref(place_with_id, diag_expr_id, ty::UniqueImmBorrow);
 697         }
 698     }
 699
 700     fn adjust_upvar_deref(
 701         &mut self,
 702         place_with_id: &PlaceWithHirId<'tcx>,
 703         diag_expr_id: hir::HirId,
 704         borrow_kind: ty::BorrowKind,
 705     ) {
 706         assert!(match borrow_kind {
 707             ty::MutBorrow => true,
 708             ty::UniqueImmBorrow => true,
 709
 710             // imm borrows never require adjusting any kinds, so we don't wind up here
 711             ty::ImmBorrow => false,
 712         });
 713
 714         let tcx = self.fcx.tcx;
 715
 716         // if this is an implicit deref of an
 717         // upvar, then we need to modify the
 718         // borrow_kind of the upvar to make sure it
 719         // is inferred to mutable if necessary
 720         self.adjust_upvar_borrow_kind(place_with_id, diag_expr_id, borrow_kind);
 721
 722         if let PlaceBase::Upvar(upvar_id) = place_with_id.place.base {
 723             self.adjust_closure_kind(
 724                 upvar_id.closure_expr_id,
 725                 ty::ClosureKind::FnMut,
 726                 tcx.hir().span(diag_expr_id),
 727                 var_name(tcx, upvar_id.var_path.hir_id),
 728             );
 729         }
 730     }
 731
 732     /// We infer the borrow_kind with which to borrow upvars in a stack closure.
 733     /// The borrow_kind basically follows a lattice of `imm < unique-imm < mut`,
 734     /// moving from left to right as needed (but never right to left).
 735     /// Here the argument `mutbl` is the borrow_kind that is required by
 736     /// some particular use.
 737     fn adjust_upvar_borrow_kind(
 738         &mut self,
 739         place_with_id: &PlaceWithHirId<'tcx>,
 740         diag_expr_id: hir::HirId,
 741         kind: ty::BorrowKind,
 742     ) {
 743         let curr_capture_info = self.capture_information[&place_with_id.place];
 744
 745         debug!(
 746             "adjust_upvar_borrow_kind(place={:?}, diag_expr_id={:?}, capture_info={:?}, kind={:?})",
 747             place_with_id, diag_expr_id, curr_capture_info, kind
 748         );
 749
 750         if let ty::UpvarCapture::ByValue(_) = curr_capture_info.capture_kind {
 751             // It's already captured by value, we don't need to do anything here
 752             return;
 753         } else if let ty::UpvarCapture::ByRef(curr_upvar_borrow) = curr_capture_info.capture_kind {
 754             // Use the same region as the current capture information
 755             // Doesn't matter since only one of the UpvarBorrow will be used.
 756             let new_upvar_borrow = ty::UpvarBorrow { kind, region: curr_upvar_borrow.region };
 757
 758             let capture_info = ty::CaptureInfo {
 759                 expr_id: Some(diag_expr_id),
 760                 capture_kind: ty::UpvarCapture::ByRef(new_upvar_borrow),
 761             };
 762             let updated_info = determine_capture_info(curr_capture_info, capture_info);
 763             self.capture_information[&place_with_id.place] = updated_info;
 764         };
 765     }
 766
 767     fn adjust_closure_kind(
 768         &mut self,
 769         closure_id: LocalDefId,
 770         new_kind: ty::ClosureKind,
 771         upvar_span: Span,
 772         var_name: Symbol,
 773     ) {
 774         debug!(
 775             "adjust_closure_kind(closure_id={:?}, new_kind={:?}, upvar_span={:?}, var_name={})",
 776             closure_id, new_kind, upvar_span, var_name
 777         );
 778
 779         // Is this the closure whose kind is currently being inferred?
 780         if closure_id.to_def_id() != self.closure_def_id {
 781             debug!("adjust_closure_kind: not current closure");
 782             return;
 783         }
 784
 785         // closures start out as `Fn`.
 786         let existing_kind = self.current_closure_kind;
 787
 788         debug!(
 789             "adjust_closure_kind: closure_id={:?}, existing_kind={:?}, new_kind={:?}",
 790             closure_id, existing_kind, new_kind
 791         );
 792
 793         match (existing_kind, new_kind) {
 794             (ty::ClosureKind::Fn, ty::ClosureKind::Fn)
 795             | (ty::ClosureKind::FnMut, ty::ClosureKind::Fn | ty::ClosureKind::FnMut)
 796             | (ty::ClosureKind::FnOnce, _) => {
 797                 // no change needed
 798             }
 799
 800             (ty::ClosureKind::Fn, ty::ClosureKind::FnMut | ty::ClosureKind::FnOnce)
 801             | (ty::ClosureKind::FnMut, ty::ClosureKind::FnOnce) => {
 802                 // new kind is stronger than the old kind
 803                 self.current_closure_kind = new_kind;
 804                 self.current_origin = Some((upvar_span, var_name));
 805             }
 806         }
 807     }
 808
 809     fn init_capture_info_for_place(
 810         &mut self,
 811         place_with_id: &PlaceWithHirId<'tcx>,
 812         diag_expr_id: hir::HirId,
 813     ) {
 814         if let PlaceBase::Upvar(upvar_id) = place_with_id.place.base {
 815             assert_eq!(self.closure_def_id.expect_local(), upvar_id.closure_expr_id);
 816
 817             let capture_kind =
 818                 self.fcx.init_capture_kind(self.capture_clause, upvar_id, self.closure_span);
 819
 820             let expr_id = Some(diag_expr_id);
 821             let capture_info = ty::CaptureInfo { expr_id, capture_kind };
 822
 823             debug!("Capturing new place {:?}, capture_info={:?}", place_with_id, capture_info);
 824
 825             self.capture_information.insert(place_with_id.place.clone(), capture_info);
 826         } else {
 827             debug!("Not upvar: {:?}", place_with_id);
 828         }
 829     }
 830 }
 831
 832 impl<'a, 'tcx> euv::Delegate<'tcx> for InferBorrowKind<'a, 'tcx> {
 833     fn consume(
 834         &mut self,
 835         place_with_id: &PlaceWithHirId<'tcx>,
 836         diag_expr_id: hir::HirId,
 837         mode: euv::ConsumeMode,
 838     ) {
 839         debug!(
 840             "consume(place_with_id={:?}, diag_expr_id={:?}, mode={:?})",
 841             place_with_id, diag_expr_id, mode
 842         );
 843         if !self.capture_information.contains_key(&place_with_id.place) {
 844             self.init_capture_info_for_place(place_with_id, diag_expr_id);
 845         }
 846
 847         self.adjust_upvar_borrow_kind_for_consume(place_with_id, diag_expr_id, mode);
 848     }
 849
 850     fn borrow(
 851         &mut self,
 852         place_with_id: &PlaceWithHirId<'tcx>,
 853         diag_expr_id: hir::HirId,
 854         bk: ty::BorrowKind,
 855     ) {
 856         debug!(
 857             "borrow(place_with_id={:?}, diag_expr_id={:?}, bk={:?})",
 858             place_with_id, diag_expr_id, bk
 859         );
 860
 861         if !self.capture_information.contains_key(&place_with_id.place) {
 862             self.init_capture_info_for_place(place_with_id, diag_expr_id);
 863         }
 864
 865         match bk {
 866             ty::ImmBorrow => {}
 867             ty::UniqueImmBorrow => {
 868                 self.adjust_upvar_borrow_kind_for_unique(&place_with_id, diag_expr_id);
 869             }
 870             ty::MutBorrow => {
 871                 self.adjust_upvar_borrow_kind_for_mut(&place_with_id, diag_expr_id);
 872             }
 873         }
 874     }
 875
 876     fn mutate(&mut self, assignee_place: &PlaceWithHirId<'tcx>, diag_expr_id: hir::HirId) {
 877         debug!("mutate(assignee_place={:?}, diag_expr_id={:?})", assignee_place, diag_expr_id);
 878
 879         if !self.capture_information.contains_key(&assignee_place.place) {
 880             self.init_capture_info_for_place(assignee_place, diag_expr_id);
 881         }
 882
 883         self.adjust_upvar_borrow_kind_for_mut(assignee_place, diag_expr_id);
 884     }
 885 }
 886
 887 fn construct_capture_info_string(
 888     tcx: TyCtxt<'_>,
 889     place: &Place<'tcx>,
 890     capture_info: &ty::CaptureInfo<'tcx>,
 891 ) -> String {
 892     let variable_name = match place.base {
 893         PlaceBase::Upvar(upvar_id) => var_name(tcx, upvar_id.var_path.hir_id).to_string(),
 894         _ => bug!("Capture_information should only contain upvars"),
 895     };
 896
 897     let mut projections_str = String::new();
 898     for (i, item) in place.projections.iter().enumerate() {
 899         let proj = match item.kind {
 900             ProjectionKind::Field(a, b) => format!("({:?}, {:?})", a, b),
 901             ProjectionKind::Deref => String::from("Deref"),
 902             ProjectionKind::Index => String::from("Index"),
 903             ProjectionKind::Subslice => String::from("Subslice"),
 904         };
 905         if i != 0 {
 906             projections_str.push_str(",");
 907         }
 908         projections_str.push_str(proj.as_str());
 909     }
 910
 911     let capture_kind_str = match capture_info.capture_kind {
 912         ty::UpvarCapture::ByValue(_) => "ByValue".into(),
 913         ty::UpvarCapture::ByRef(borrow) => format!("{:?}", borrow.kind),
 914     };
 915     format!("{}[{}] -> {}", variable_name, projections_str, capture_kind_str)
 916 }
 917
 918 fn var_name(tcx: TyCtxt<'_>, var_hir_id: hir::HirId) -> Symbol {
 919     tcx.hir().name(var_hir_id)
 920 }
 921
 922 /// Helper function to determine if we need to escalate CaptureKind from
 923 /// CaptureInfo A to B and returns the escalated CaptureInfo.
 924 /// (Note: CaptureInfo contains CaptureKind and an expression that led to capture it in that way)
 925 ///
 926 /// If both `CaptureKind`s are considered equivalent, then the CaptureInfo is selected based
 927 /// on the `CaptureInfo` containing an associated expression id.
 928 ///
 929 /// If both the CaptureKind and Expression are considered to be equivalent,
 930 /// then `CaptureInfo` A is preferred. This can be useful in cases where we want to priortize
 931 /// expressions reported back to the user as part of diagnostics based on which appears earlier
 932 /// in the closure. This can be acheived simply by calling
 933 /// `determine_capture_info(existing_info, current_info)`. This works out because the
 934 /// expressions that occur earlier in the closure body than the current expression are processed before.
 935 /// Consider the following example
 936 /// ```rust,no_run
 937 /// struct Point { x: i32, y: i32 }
 938 /// let mut p: Point { x: 10, y: 10 };
 939 ///
 940 /// let c = || {
 941 ///     p.x     += 10;
 942 /// // ^ E1 ^
 943 ///     // ...
 944 ///     // More code
 945 ///     // ...
 946 ///     p.x += 10; // E2
 947 /// // ^ E2 ^
 948 /// };
 949 /// ```
 950 /// `CaptureKind` associated with both `E1` and `E2` will be ByRef(MutBorrow),
 951 /// and both have an expression associated, however for diagnostics we prefer reporting
 952 /// `E1` since it appears earlier in the closure body. When `E2` is being processed we
 953 /// would've already handled `E1`, and have an existing capture_information for it.
 954 /// Calling `determine_capture_info(existing_info_e1, current_info_e2)` will return
 955 /// `existing_info_e1` in this case, allowing us to point to `E1` in case of diagnostics.
 956 fn determine_capture_info(
 957     capture_info_a: ty::CaptureInfo<'tcx>,
 958     capture_info_b: ty::CaptureInfo<'tcx>,
 959 ) -> ty::CaptureInfo<'tcx> {
 960     // If the capture kind is equivalent then, we don't need to escalate and can compare the
 961     // expressions.
 962     let eq_capture_kind = match (capture_info_a.capture_kind, capture_info_b.capture_kind) {
 963         (ty::UpvarCapture::ByValue(_), ty::UpvarCapture::ByValue(_)) => {
 964             // We don't need to worry about the spans being ignored here.
 965             //
 966             // The expr_id in capture_info corresponds to the span that is stored within
 967             // ByValue(span) and therefore it gets handled with priortizing based on
 968             // expressions below.
 969             true
 970         }
 971         (ty::UpvarCapture::ByRef(ref_a), ty::UpvarCapture::ByRef(ref_b)) => {
 972             ref_a.kind == ref_b.kind
 973         }
 974         (ty::UpvarCapture::ByValue(_), _) | (ty::UpvarCapture::ByRef(_), _) => false,
 975     };
 976
 977     if eq_capture_kind {
 978         match (capture_info_a.expr_id, capture_info_b.expr_id) {
 979             (Some(_), _) | (None, None) => capture_info_a,
 980             (None, Some(_)) => capture_info_b,
 981         }
 982     } else {
 983         // We select the CaptureKind which ranks higher based the following priority order:
 984         // ByValue > MutBorrow > UniqueImmBorrow > ImmBorrow
 985         match (capture_info_a.capture_kind, capture_info_b.capture_kind) {
 986             (ty::UpvarCapture::ByValue(_), _) => capture_info_a,
 987             (_, ty::UpvarCapture::ByValue(_)) => capture_info_b,
 988             (ty::UpvarCapture::ByRef(ref_a), ty::UpvarCapture::ByRef(ref_b)) => {
 989                 match (ref_a.kind, ref_b.kind) {
 990                     // Take LHS:
 991                     (ty::UniqueImmBorrow | ty::MutBorrow, ty::ImmBorrow)
 992                     | (ty::MutBorrow, ty::UniqueImmBorrow) => capture_info_a,
 993
 994                     // Take RHS:
 995                     (ty::ImmBorrow, ty::UniqueImmBorrow | ty::MutBorrow)
 996                     | (ty::UniqueImmBorrow, ty::MutBorrow) => capture_info_b,
 997
 998                     (ty::ImmBorrow, ty::ImmBorrow)
 999                     | (ty::UniqueImmBorrow, ty::UniqueImmBorrow)
1000                     | (ty::MutBorrow, ty::MutBorrow) => {
1001                         bug!("Expected unequal capture kinds");
1002                     }
1003                 }
1004             }
1005         }
1006     }
1007 }
1008
1009 /// Determines the Ancestry relationship of Place A relative to Place B
1010 ///
1011 /// `PlaceAncestryRelation::Ancestor` implies Place A is ancestor of Place B
1012 /// `PlaceAncestryRelation::Descendant` implies Place A is descendant of Place B
1013 /// `PlaceAncestryRelation::Divergent` implies neither of them is the ancestor of the other.
1014 fn determine_place_ancestry_relation(
1015     place_a: &Place<'tcx>,
1016     place_b: &Place<'tcx>,
1017 ) -> PlaceAncestryRelation {
1018     // If Place A and Place B, don't start off from the same root variable, they are divergent.
1019     if place_a.base != place_b.base {
1020         return PlaceAncestryRelation::Divergent;
1021     }
1022
1023     // Assume of length of projections_a = n
1024     let projections_a = &place_a.projections;
1025
1026     // Assume of length of projections_b = m
1027     let projections_b = &place_b.projections;
1028
1029     let mut same_initial_projections = true;
1030
1031     for (proj_a, proj_b) in projections_a.iter().zip(projections_b.iter()) {
1032         if proj_a != proj_b {
1033             same_initial_projections = false;
1034             break;
1035         }
1036     }
1037
1038     if same_initial_projections {
1039         // First min(n, m) projections are the same
1040         // Select Ancestor/Descendant
1041         if projections_b.len() >= projections_a.len() {
1042             PlaceAncestryRelation::Ancestor
1043         } else {
1044             PlaceAncestryRelation::Descendant
1045         }
1046     } else {
1047         PlaceAncestryRelation::Divergent
1048     }
1049 }