1 //! ### Inferring borrow kinds for upvars
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:
9 //! ty::ImmBorrow -> ty::UniqueImmBorrow -> ty::MutBorrow
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
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.)
35 use crate::expr_use_visitor as euv;
36 use crate::mem_categorization as mc;
37 use crate::mem_categorization::PlaceBase;
38 use rustc::ty::{self, Ty, TyCtxt, UpvarSubsts};
40 use rustc_data_structures::fx::FxIndexMap;
42 use rustc_hir::def_id::DefId;
43 use rustc_hir::def_id::LocalDefId;
44 use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor};
45 use rustc_infer::infer::UpvarRegion;
48 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
49 pub fn closure_analyze(&self, body: &'tcx hir::Body<'tcx>) {
50 InferBorrowKindVisitor { fcx: self }.visit_body(body);
52 // it's our job to process these.
53 assert!(self.deferred_call_resolutions.borrow().is_empty());
57 struct InferBorrowKindVisitor<'a, 'tcx> {
58 fcx: &'a FnCtxt<'a, 'tcx>,
61 impl<'a, 'tcx> Visitor<'tcx> for InferBorrowKindVisitor<'a, 'tcx> {
62 type Map = intravisit::ErasedMap<'tcx>;
64 fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
65 NestedVisitorMap::None
68 fn visit_expr(&mut self, expr: &'tcx hir::Expr<'tcx>) {
69 if let hir::ExprKind::Closure(cc, _, body_id, _, _) = expr.kind {
70 let body = self.fcx.tcx.hir().body(body_id);
71 self.visit_body(body);
72 self.fcx.analyze_closure(expr.hir_id, expr.span, body, cc);
75 intravisit::walk_expr(self, expr);
79 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
80 /// Analysis starting point.
83 closure_hir_id: hir::HirId,
86 capture_clause: hir::CaptureBy,
88 debug!("analyze_closure(id={:?}, body.id={:?})", closure_hir_id, body.id());
90 // Extract the type of the closure.
91 let ty = self.node_ty(closure_hir_id);
92 let (closure_def_id, substs) = match ty.kind {
93 ty::Closure(def_id, substs) => (def_id, UpvarSubsts::Closure(substs)),
94 ty::Generator(def_id, substs, _) => (def_id, UpvarSubsts::Generator(substs)),
96 // #51714: skip analysis when we have already encountered type errors
102 "type of closure expr {:?} is not a closure {:?}",
109 let infer_kind = if let UpvarSubsts::Closure(closure_substs) = substs {
110 self.closure_kind(closure_def_id, closure_substs).is_none().then_some(closure_substs)
115 if let Some(upvars) = self.tcx.upvars(closure_def_id) {
116 let mut upvar_list: FxIndexMap<hir::HirId, ty::UpvarId> =
117 FxIndexMap::with_capacity_and_hasher(upvars.len(), Default::default());
118 for (&var_hir_id, _) in upvars.iter() {
119 let upvar_id = ty::UpvarId {
120 var_path: ty::UpvarPath { hir_id: var_hir_id },
121 closure_expr_id: LocalDefId::from_def_id(closure_def_id),
123 debug!("seed upvar_id {:?}", upvar_id);
124 // Adding the upvar Id to the list of Upvars, which will be added
125 // to the map for the closure at the end of the for loop.
126 upvar_list.insert(var_hir_id, upvar_id);
128 let capture_kind = match capture_clause {
129 hir::CaptureBy::Value => ty::UpvarCapture::ByValue,
130 hir::CaptureBy::Ref => {
131 let origin = UpvarRegion(upvar_id, span);
132 let upvar_region = self.next_region_var(origin);
134 ty::UpvarBorrow { kind: ty::ImmBorrow, region: upvar_region };
135 ty::UpvarCapture::ByRef(upvar_borrow)
139 self.tables.borrow_mut().upvar_capture_map.insert(upvar_id, capture_kind);
141 // Add the vector of upvars to the map keyed with the closure id.
142 // This gives us an easier access to them without having to call
143 // tcx.upvars again..
144 if !upvar_list.is_empty() {
145 self.tables.borrow_mut().upvar_list.insert(closure_def_id, upvar_list);
149 let body_owner_def_id = self.tcx.hir().body_owner_def_id(body.id());
150 assert_eq!(body_owner_def_id, closure_def_id);
151 let mut delegate = InferBorrowKind {
154 current_closure_kind: ty::ClosureKind::LATTICE_BOTTOM,
155 current_origin: None,
156 adjust_upvar_captures: ty::UpvarCaptureMap::default(),
158 euv::ExprUseVisitor::new(
163 &self.tables.borrow(),
167 if let Some(closure_substs) = infer_kind {
168 // Unify the (as yet unbound) type variable in the closure
169 // substs with the kind we inferred.
170 let inferred_kind = delegate.current_closure_kind;
171 let closure_kind_ty = closure_substs.as_closure().kind_ty(closure_def_id, self.tcx);
172 self.demand_eqtype(span, inferred_kind.to_ty(self.tcx), closure_kind_ty);
174 // If we have an origin, store it.
175 if let Some(origin) = delegate.current_origin {
176 self.tables.borrow_mut().closure_kind_origins_mut().insert(closure_hir_id, origin);
180 self.tables.borrow_mut().upvar_capture_map.extend(delegate.adjust_upvar_captures);
182 // Now that we've analyzed the closure, we know how each
183 // variable is borrowed, and we know what traits the closure
184 // implements (Fn vs FnMut etc). We now have some updates to do
185 // with that information.
187 // Note that no closure type C may have an upvar of type C
188 // (though it may reference itself via a trait object). This
189 // results from the desugaring of closures to a struct like
190 // `Foo<..., UV0...UVn>`. If one of those upvars referenced
191 // C, then the type would have infinite size (and the
192 // inference algorithm will reject it).
194 // Equate the type variables for the upvars with the actual types.
195 let final_upvar_tys = self.final_upvar_tys(closure_hir_id);
197 "analyze_closure: id={:?} substs={:?} final_upvar_tys={:?}",
198 closure_hir_id, substs, final_upvar_tys
200 for (upvar_ty, final_upvar_ty) in
201 substs.upvar_tys(closure_def_id, self.tcx).zip(final_upvar_tys)
203 self.demand_suptype(span, upvar_ty, final_upvar_ty);
206 // If we are also inferred the closure kind here,
207 // process any deferred resolutions.
208 let deferred_call_resolutions = self.remove_deferred_call_resolutions(closure_def_id);
209 for deferred_call_resolution in deferred_call_resolutions {
210 deferred_call_resolution.resolve(self);
214 // Returns a list of `Ty`s for each upvar.
215 fn final_upvar_tys(&self, closure_id: hir::HirId) -> Vec<Ty<'tcx>> {
216 // Presently an unboxed closure type cannot "escape" out of a
217 // function, so we will only encounter ones that originated in the
218 // local crate or were inlined into it along with some function.
219 // This may change if abstract return types of some sort are
222 let closure_def_id = tcx.hir().local_def_id(closure_id);
224 tcx.upvars(closure_def_id)
227 upvars.iter().map(|(&var_hir_id, _)| {
228 let upvar_ty = self.node_ty(var_hir_id);
229 let upvar_id = ty::UpvarId {
230 var_path: ty::UpvarPath { hir_id: var_hir_id },
231 closure_expr_id: LocalDefId::from_def_id(closure_def_id),
233 let capture = self.tables.borrow().upvar_capture(upvar_id);
235 debug!("var_id={:?} upvar_ty={:?} capture={:?}", var_hir_id, upvar_ty, capture);
238 ty::UpvarCapture::ByValue => upvar_ty,
239 ty::UpvarCapture::ByRef(borrow) => tcx.mk_ref(
241 ty::TypeAndMut { ty: upvar_ty, mutbl: borrow.kind.to_mutbl_lossy() },
250 struct InferBorrowKind<'a, 'tcx> {
251 fcx: &'a FnCtxt<'a, 'tcx>,
253 // The def-id of the closure whose kind and upvar accesses are being inferred.
254 closure_def_id: DefId,
256 // The kind that we have inferred that the current closure
257 // requires. Note that we *always* infer a minimal kind, even if
258 // we don't always *use* that in the final result (i.e., sometimes
259 // we've taken the closure kind from the expectations instead, and
260 // for generators we don't even implement the closure traits
262 current_closure_kind: ty::ClosureKind,
264 // If we modified `current_closure_kind`, this field contains a `Some()` with the
265 // variable access that caused us to do so.
266 current_origin: Option<(Span, ast::Name)>,
268 // For each upvar that we access, we track the minimal kind of
269 // access we need (ref, ref mut, move, etc).
270 adjust_upvar_captures: ty::UpvarCaptureMap<'tcx>,
273 impl<'a, 'tcx> InferBorrowKind<'a, 'tcx> {
274 fn adjust_upvar_borrow_kind_for_consume(
276 place: &mc::Place<'tcx>,
277 mode: euv::ConsumeMode,
279 debug!("adjust_upvar_borrow_kind_for_consume(place={:?}, mode={:?})", place, mode);
281 // we only care about moves
289 let tcx = self.fcx.tcx;
290 let upvar_id = if let PlaceBase::Upvar(upvar_id) = place.base {
296 debug!("adjust_upvar_borrow_kind_for_consume: upvar={:?}", upvar_id);
298 // To move out of an upvar, this must be a FnOnce closure
299 self.adjust_closure_kind(
300 upvar_id.closure_expr_id,
301 ty::ClosureKind::FnOnce,
303 var_name(tcx, upvar_id.var_path.hir_id),
306 self.adjust_upvar_captures.insert(upvar_id, ty::UpvarCapture::ByValue);
309 /// Indicates that `place` is being directly mutated (e.g., assigned
310 /// to). If the place is based on a by-ref upvar, this implies that
311 /// the upvar must be borrowed using an `&mut` borrow.
312 fn adjust_upvar_borrow_kind_for_mut(&mut self, place: &mc::Place<'tcx>) {
313 debug!("adjust_upvar_borrow_kind_for_mut(place={:?})", place);
315 if let PlaceBase::Upvar(upvar_id) = place.base {
316 let mut borrow_kind = ty::MutBorrow;
317 for pointer_ty in place.deref_tys() {
318 match pointer_ty.kind {
319 // Raw pointers don't inherit mutability.
320 ty::RawPtr(_) => return,
321 // assignment to deref of an `&mut`
322 // borrowed pointer implies that the
323 // pointer itself must be unique, but not
324 // necessarily *mutable*
325 ty::Ref(.., hir::Mutability::Mut) => borrow_kind = ty::UniqueImmBorrow,
329 self.adjust_upvar_deref(upvar_id, place.span, borrow_kind);
333 fn adjust_upvar_borrow_kind_for_unique(&mut self, place: &mc::Place<'tcx>) {
334 debug!("adjust_upvar_borrow_kind_for_unique(place={:?})", place);
336 if let PlaceBase::Upvar(upvar_id) = place.base {
337 if place.deref_tys().any(ty::TyS::is_unsafe_ptr) {
338 // Raw pointers don't inherit mutability.
341 // for a borrowed pointer to be unique, its base must be unique
342 self.adjust_upvar_deref(upvar_id, place.span, ty::UniqueImmBorrow);
346 fn adjust_upvar_deref(
348 upvar_id: ty::UpvarId,
350 borrow_kind: ty::BorrowKind,
352 assert!(match borrow_kind {
353 ty::MutBorrow => true,
354 ty::UniqueImmBorrow => true,
356 // imm borrows never require adjusting any kinds, so we don't wind up here
357 ty::ImmBorrow => false,
360 let tcx = self.fcx.tcx;
362 // if this is an implicit deref of an
363 // upvar, then we need to modify the
364 // borrow_kind of the upvar to make sure it
365 // is inferred to mutable if necessary
366 self.adjust_upvar_borrow_kind(upvar_id, borrow_kind);
368 // also need to be in an FnMut closure since this is not an ImmBorrow
369 self.adjust_closure_kind(
370 upvar_id.closure_expr_id,
371 ty::ClosureKind::FnMut,
373 var_name(tcx, upvar_id.var_path.hir_id),
377 /// We infer the borrow_kind with which to borrow upvars in a stack closure.
378 /// The borrow_kind basically follows a lattice of `imm < unique-imm < mut`,
379 /// moving from left to right as needed (but never right to left).
380 /// Here the argument `mutbl` is the borrow_kind that is required by
381 /// some particular use.
382 fn adjust_upvar_borrow_kind(&mut self, upvar_id: ty::UpvarId, kind: ty::BorrowKind) {
383 let upvar_capture = self
384 .adjust_upvar_captures
387 .unwrap_or_else(|| self.fcx.tables.borrow().upvar_capture(upvar_id));
389 "adjust_upvar_borrow_kind(upvar_id={:?}, upvar_capture={:?}, kind={:?})",
390 upvar_id, upvar_capture, kind
393 match upvar_capture {
394 ty::UpvarCapture::ByValue => {
395 // Upvar is already by-value, the strongest criteria.
397 ty::UpvarCapture::ByRef(mut upvar_borrow) => {
398 match (upvar_borrow.kind, kind) {
400 (ty::ImmBorrow, ty::UniqueImmBorrow)
401 | (ty::ImmBorrow, ty::MutBorrow)
402 | (ty::UniqueImmBorrow, ty::MutBorrow) => {
403 upvar_borrow.kind = kind;
404 self.adjust_upvar_captures
405 .insert(upvar_id, ty::UpvarCapture::ByRef(upvar_borrow));
408 (ty::ImmBorrow, ty::ImmBorrow)
409 | (ty::UniqueImmBorrow, ty::ImmBorrow)
410 | (ty::UniqueImmBorrow, ty::UniqueImmBorrow)
411 | (ty::MutBorrow, _) => {}
417 fn adjust_closure_kind(
419 closure_id: LocalDefId,
420 new_kind: ty::ClosureKind,
425 "adjust_closure_kind(closure_id={:?}, new_kind={:?}, upvar_span={:?}, var_name={})",
426 closure_id, new_kind, upvar_span, var_name
429 // Is this the closure whose kind is currently being inferred?
430 if closure_id.to_def_id() != self.closure_def_id {
431 debug!("adjust_closure_kind: not current closure");
435 // closures start out as `Fn`.
436 let existing_kind = self.current_closure_kind;
439 "adjust_closure_kind: closure_id={:?}, existing_kind={:?}, new_kind={:?}",
440 closure_id, existing_kind, new_kind
443 match (existing_kind, new_kind) {
444 (ty::ClosureKind::Fn, ty::ClosureKind::Fn)
445 | (ty::ClosureKind::FnMut, ty::ClosureKind::Fn)
446 | (ty::ClosureKind::FnMut, ty::ClosureKind::FnMut)
447 | (ty::ClosureKind::FnOnce, _) => {
451 (ty::ClosureKind::Fn, ty::ClosureKind::FnMut)
452 | (ty::ClosureKind::Fn, ty::ClosureKind::FnOnce)
453 | (ty::ClosureKind::FnMut, ty::ClosureKind::FnOnce) => {
454 // new kind is stronger than the old kind
455 self.current_closure_kind = new_kind;
456 self.current_origin = Some((upvar_span, var_name));
462 impl<'a, 'tcx> euv::Delegate<'tcx> for InferBorrowKind<'a, 'tcx> {
463 fn consume(&mut self, place: &mc::Place<'tcx>, mode: euv::ConsumeMode) {
464 debug!("consume(place={:?},mode={:?})", place, mode);
465 self.adjust_upvar_borrow_kind_for_consume(place, mode);
468 fn borrow(&mut self, place: &mc::Place<'tcx>, bk: ty::BorrowKind) {
469 debug!("borrow(place={:?}, bk={:?})", place, bk);
473 ty::UniqueImmBorrow => {
474 self.adjust_upvar_borrow_kind_for_unique(place);
477 self.adjust_upvar_borrow_kind_for_mut(place);
482 fn mutate(&mut self, assignee_place: &mc::Place<'tcx>) {
483 debug!("mutate(assignee_place={:?})", assignee_place);
485 self.adjust_upvar_borrow_kind_for_mut(assignee_place);
489 fn var_name(tcx: TyCtxt<'_>, var_hir_id: hir::HirId) -> ast::Name {
490 tcx.hir().name(var_hir_id)