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 rustc_data_structures
::fx
::FxIndexMap
;
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
::{PlaceBase, PlaceWithHirId}
;
43 use rustc_middle
::ty
::{self, Ty, TyCtxt, UpvarSubsts}
;
44 use rustc_span
::{Span, Symbol}
;
45 use std
::collections
::hash_map
::Entry
;
47 impl<'a
, 'tcx
> FnCtxt
<'a
, 'tcx
> {
48 pub fn closure_analyze(&self, body
: &'tcx hir
::Body
<'tcx
>) {
49 InferBorrowKindVisitor { fcx: self }
.visit_body(body
);
51 // it's our job to process these.
52 assert
!(self.deferred_call_resolutions
.borrow().is_empty());
56 struct InferBorrowKindVisitor
<'a
, 'tcx
> {
57 fcx
: &'a FnCtxt
<'a
, 'tcx
>,
60 impl<'a
, 'tcx
> Visitor
<'tcx
> for InferBorrowKindVisitor
<'a
, 'tcx
> {
61 type Map
= intravisit
::ErasedMap
<'tcx
>;
63 fn nested_visit_map(&mut self) -> NestedVisitorMap
<Self::Map
> {
64 NestedVisitorMap
::None
67 fn visit_expr(&mut self, expr
: &'tcx hir
::Expr
<'tcx
>) {
68 if let hir
::ExprKind
::Closure(cc
, _
, body_id
, _
, _
) = expr
.kind
{
69 let body
= self.fcx
.tcx
.hir().body(body_id
);
70 self.visit_body(body
);
71 self.fcx
.analyze_closure(expr
.hir_id
, expr
.span
, body
, cc
);
74 intravisit
::walk_expr(self, expr
);
78 impl<'a
, 'tcx
> FnCtxt
<'a
, 'tcx
> {
79 /// Analysis starting point.
82 closure_hir_id
: hir
::HirId
,
85 capture_clause
: hir
::CaptureBy
,
87 debug
!("analyze_closure(id={:?}, body.id={:?})", closure_hir_id
, body
.id());
89 // Extract the type of the closure.
90 let ty
= self.node_ty(closure_hir_id
);
91 let (closure_def_id
, substs
) = match *ty
.kind() {
92 ty
::Closure(def_id
, substs
) => (def_id
, UpvarSubsts
::Closure(substs
)),
93 ty
::Generator(def_id
, substs
, _
) => (def_id
, UpvarSubsts
::Generator(substs
)),
95 // #51714: skip analysis when we have already encountered type errors
101 "type of closure expr {:?} is not a closure {:?}",
108 let infer_kind
= if let UpvarSubsts
::Closure(closure_substs
) = substs
{
109 self.closure_kind(closure_substs
).is_none().then_some(closure_substs
)
114 if let Some(upvars
) = self.tcx
.upvars_mentioned(closure_def_id
) {
115 let mut closure_captures
: FxIndexMap
<hir
::HirId
, ty
::UpvarId
> =
116 FxIndexMap
::with_capacity_and_hasher(upvars
.len(), Default
::default());
117 for (&var_hir_id
, _
) in upvars
.iter() {
118 let upvar_id
= ty
::UpvarId
{
119 var_path
: ty
::UpvarPath { hir_id: var_hir_id }
,
120 closure_expr_id
: closure_def_id
.expect_local(),
122 debug
!("seed upvar_id {:?}", upvar_id
);
123 // Adding the upvar Id to the list of Upvars, which will be added
124 // to the map for the closure at the end of the for loop.
125 closure_captures
.insert(var_hir_id
, upvar_id
);
127 let capture_kind
= match capture_clause
{
128 hir
::CaptureBy
::Value
=> ty
::UpvarCapture
::ByValue(None
),
129 hir
::CaptureBy
::Ref
=> {
130 let origin
= UpvarRegion(upvar_id
, span
);
131 let upvar_region
= self.next_region_var(origin
);
133 ty
::UpvarBorrow { kind: ty::ImmBorrow, region: upvar_region }
;
134 ty
::UpvarCapture
::ByRef(upvar_borrow
)
138 self.typeck_results
.borrow_mut().upvar_capture_map
.insert(upvar_id
, capture_kind
);
140 // Add the vector of upvars to the map keyed with the closure id.
141 // This gives us an easier access to them without having to call
142 // tcx.upvars again..
143 if !closure_captures
.is_empty() {
147 .insert(closure_def_id
, closure_captures
);
151 let body_owner_def_id
= self.tcx
.hir().body_owner_def_id(body
.id());
152 assert_eq
!(body_owner_def_id
.to_def_id(), closure_def_id
);
153 let mut delegate
= InferBorrowKind
{
156 current_closure_kind
: ty
::ClosureKind
::LATTICE_BOTTOM
,
157 current_origin
: None
,
158 adjust_upvar_captures
: ty
::UpvarCaptureMap
::default(),
160 euv
::ExprUseVisitor
::new(
165 &self.typeck_results
.borrow(),
169 if let Some(closure_substs
) = infer_kind
{
170 // Unify the (as yet unbound) type variable in the closure
171 // substs with the kind we inferred.
172 let inferred_kind
= delegate
.current_closure_kind
;
173 let closure_kind_ty
= closure_substs
.as_closure().kind_ty();
174 self.demand_eqtype(span
, inferred_kind
.to_ty(self.tcx
), closure_kind_ty
);
176 // If we have an origin, store it.
177 if let Some(origin
) = delegate
.current_origin
{
180 .closure_kind_origins_mut()
181 .insert(closure_hir_id
, origin
);
185 self.typeck_results
.borrow_mut().upvar_capture_map
.extend(delegate
.adjust_upvar_captures
);
187 // Now that we've analyzed the closure, we know how each
188 // variable is borrowed, and we know what traits the closure
189 // implements (Fn vs FnMut etc). We now have some updates to do
190 // with that information.
192 // Note that no closure type C may have an upvar of type C
193 // (though it may reference itself via a trait object). This
194 // results from the desugaring of closures to a struct like
195 // `Foo<..., UV0...UVn>`. If one of those upvars referenced
196 // C, then the type would have infinite size (and the
197 // inference algorithm will reject it).
199 // Equate the type variables for the upvars with the actual types.
200 let final_upvar_tys
= self.final_upvar_tys(closure_hir_id
);
202 "analyze_closure: id={:?} substs={:?} final_upvar_tys={:?}",
203 closure_hir_id
, substs
, final_upvar_tys
206 // Build a tuple (U0..Un) of the final upvar types U0..Un
207 // and unify the upvar tupe type in the closure with it:
208 let final_tupled_upvars_type
= self.tcx
.mk_tup(final_upvar_tys
.iter());
209 self.demand_suptype(span
, substs
.tupled_upvars_ty(), final_tupled_upvars_type
);
211 // If we are also inferred the closure kind here,
212 // process any deferred resolutions.
213 let deferred_call_resolutions
= self.remove_deferred_call_resolutions(closure_def_id
);
214 for deferred_call_resolution
in deferred_call_resolutions
{
215 deferred_call_resolution
.resolve(self);
219 // Returns a list of `Ty`s for each upvar.
220 fn final_upvar_tys(&self, closure_id
: hir
::HirId
) -> Vec
<Ty
<'tcx
>> {
221 // Presently an unboxed closure type cannot "escape" out of a
222 // function, so we will only encounter ones that originated in the
223 // local crate or were inlined into it along with some function.
224 // This may change if abstract return types of some sort are
227 let closure_def_id
= tcx
.hir().local_def_id(closure_id
);
229 tcx
.upvars_mentioned(closure_def_id
)
232 upvars
.iter().map(|(&var_hir_id
, _
)| {
233 let upvar_ty
= self.node_ty(var_hir_id
);
234 let upvar_id
= ty
::UpvarId
{
235 var_path
: ty
::UpvarPath { hir_id: var_hir_id }
,
236 closure_expr_id
: closure_def_id
,
238 let capture
= self.typeck_results
.borrow().upvar_capture(upvar_id
);
240 debug
!("var_id={:?} upvar_ty={:?} capture={:?}", var_hir_id
, upvar_ty
, capture
);
243 ty
::UpvarCapture
::ByValue(_
) => upvar_ty
,
244 ty
::UpvarCapture
::ByRef(borrow
) => tcx
.mk_ref(
246 ty
::TypeAndMut { ty: upvar_ty, mutbl: borrow.kind.to_mutbl_lossy() }
,
255 struct InferBorrowKind
<'a
, 'tcx
> {
256 fcx
: &'a FnCtxt
<'a
, 'tcx
>,
258 // The def-id of the closure whose kind and upvar accesses are being inferred.
259 closure_def_id
: DefId
,
261 // The kind that we have inferred that the current closure
262 // requires. Note that we *always* infer a minimal kind, even if
263 // we don't always *use* that in the final result (i.e., sometimes
264 // we've taken the closure kind from the expectations instead, and
265 // for generators we don't even implement the closure traits
267 current_closure_kind
: ty
::ClosureKind
,
269 // If we modified `current_closure_kind`, this field contains a `Some()` with the
270 // variable access that caused us to do so.
271 current_origin
: Option
<(Span
, Symbol
)>,
273 // For each upvar that we access, we track the minimal kind of
274 // access we need (ref, ref mut, move, etc).
275 adjust_upvar_captures
: ty
::UpvarCaptureMap
<'tcx
>,
278 impl<'a
, 'tcx
> InferBorrowKind
<'a
, 'tcx
> {
279 fn adjust_upvar_borrow_kind_for_consume(
281 place_with_id
: &PlaceWithHirId
<'tcx
>,
282 diag_expr_id
: hir
::HirId
,
283 mode
: euv
::ConsumeMode
,
286 "adjust_upvar_borrow_kind_for_consume(place_with_id={:?}, diag_expr_id={:?}, mode={:?})",
287 place_with_id
, diag_expr_id
, mode
290 // we only care about moves
298 let tcx
= self.fcx
.tcx
;
299 let upvar_id
= if let PlaceBase
::Upvar(upvar_id
) = place_with_id
.place
.base
{
305 debug
!("adjust_upvar_borrow_kind_for_consume: upvar={:?}", upvar_id
);
307 let usage_span
= tcx
.hir().span(diag_expr_id
);
309 // To move out of an upvar, this must be a FnOnce closure
310 self.adjust_closure_kind(
311 upvar_id
.closure_expr_id
,
312 ty
::ClosureKind
::FnOnce
,
314 var_name(tcx
, upvar_id
.var_path
.hir_id
),
317 let new_capture
= ty
::UpvarCapture
::ByValue(Some(usage_span
));
318 match self.adjust_upvar_captures
.entry(upvar_id
) {
319 Entry
::Occupied(mut e
) => {
321 // We always overwrite `ByRef`, since we require
322 // that the upvar be available by value.
324 // If we had a previous by-value usage without a specific
325 // span, use ours instead. Otherwise, keep the first span
326 // we encountered, since there isn't an obviously better one.
327 ty
::UpvarCapture
::ByRef(_
) | ty
::UpvarCapture
::ByValue(None
) => {
328 e
.insert(new_capture
);
333 Entry
::Vacant(e
) => {
334 e
.insert(new_capture
);
339 /// Indicates that `place_with_id` is being directly mutated (e.g., assigned
340 /// to). If the place is based on a by-ref upvar, this implies that
341 /// the upvar must be borrowed using an `&mut` borrow.
342 fn adjust_upvar_borrow_kind_for_mut(
344 place_with_id
: &PlaceWithHirId
<'tcx
>,
345 diag_expr_id
: hir
::HirId
,
348 "adjust_upvar_borrow_kind_for_mut(place_with_id={:?}, diag_expr_id={:?})",
349 place_with_id
, diag_expr_id
352 if let PlaceBase
::Upvar(upvar_id
) = place_with_id
.place
.base
{
353 let mut borrow_kind
= ty
::MutBorrow
;
354 for pointer_ty
in place_with_id
.place
.deref_tys() {
355 match pointer_ty
.kind() {
356 // Raw pointers don't inherit mutability.
357 ty
::RawPtr(_
) => return,
358 // assignment to deref of an `&mut`
359 // borrowed pointer implies that the
360 // pointer itself must be unique, but not
361 // necessarily *mutable*
362 ty
::Ref(.., hir
::Mutability
::Mut
) => borrow_kind
= ty
::UniqueImmBorrow
,
366 self.adjust_upvar_deref(upvar_id
, self.fcx
.tcx
.hir().span(diag_expr_id
), borrow_kind
);
370 fn adjust_upvar_borrow_kind_for_unique(
372 place_with_id
: &PlaceWithHirId
<'tcx
>,
373 diag_expr_id
: hir
::HirId
,
376 "adjust_upvar_borrow_kind_for_unique(place_with_id={:?}, diag_expr_id={:?})",
377 place_with_id
, diag_expr_id
380 if let PlaceBase
::Upvar(upvar_id
) = place_with_id
.place
.base
{
381 if place_with_id
.place
.deref_tys().any(ty
::TyS
::is_unsafe_ptr
) {
382 // Raw pointers don't inherit mutability.
385 // for a borrowed pointer to be unique, its base must be unique
386 self.adjust_upvar_deref(
388 self.fcx
.tcx
.hir().span(diag_expr_id
),
394 fn adjust_upvar_deref(
396 upvar_id
: ty
::UpvarId
,
398 borrow_kind
: ty
::BorrowKind
,
400 assert
!(match borrow_kind
{
401 ty
::MutBorrow
=> true,
402 ty
::UniqueImmBorrow
=> true,
404 // imm borrows never require adjusting any kinds, so we don't wind up here
405 ty
::ImmBorrow
=> false,
408 let tcx
= self.fcx
.tcx
;
410 // if this is an implicit deref of an
411 // upvar, then we need to modify the
412 // borrow_kind of the upvar to make sure it
413 // is inferred to mutable if necessary
414 self.adjust_upvar_borrow_kind(upvar_id
, borrow_kind
);
416 // also need to be in an FnMut closure since this is not an ImmBorrow
417 self.adjust_closure_kind(
418 upvar_id
.closure_expr_id
,
419 ty
::ClosureKind
::FnMut
,
421 var_name(tcx
, upvar_id
.var_path
.hir_id
),
425 /// We infer the borrow_kind with which to borrow upvars in a stack closure.
426 /// The borrow_kind basically follows a lattice of `imm < unique-imm < mut`,
427 /// moving from left to right as needed (but never right to left).
428 /// Here the argument `mutbl` is the borrow_kind that is required by
429 /// some particular use.
430 fn adjust_upvar_borrow_kind(&mut self, upvar_id
: ty
::UpvarId
, kind
: ty
::BorrowKind
) {
431 let upvar_capture
= self
432 .adjust_upvar_captures
435 .unwrap_or_else(|| self.fcx
.typeck_results
.borrow().upvar_capture(upvar_id
));
437 "adjust_upvar_borrow_kind(upvar_id={:?}, upvar_capture={:?}, kind={:?})",
438 upvar_id
, upvar_capture
, kind
441 match upvar_capture
{
442 ty
::UpvarCapture
::ByValue(_
) => {
443 // Upvar is already by-value, the strongest criteria.
445 ty
::UpvarCapture
::ByRef(mut upvar_borrow
) => {
446 match (upvar_borrow
.kind
, kind
) {
448 (ty
::ImmBorrow
, ty
::UniqueImmBorrow
| ty
::MutBorrow
)
449 | (ty
::UniqueImmBorrow
, ty
::MutBorrow
) => {
450 upvar_borrow
.kind
= kind
;
451 self.adjust_upvar_captures
452 .insert(upvar_id
, ty
::UpvarCapture
::ByRef(upvar_borrow
));
455 (ty
::ImmBorrow
, ty
::ImmBorrow
)
456 | (ty
::UniqueImmBorrow
, ty
::ImmBorrow
| ty
::UniqueImmBorrow
)
457 | (ty
::MutBorrow
, _
) => {}
463 fn adjust_closure_kind(
465 closure_id
: LocalDefId
,
466 new_kind
: ty
::ClosureKind
,
471 "adjust_closure_kind(closure_id={:?}, new_kind={:?}, upvar_span={:?}, var_name={})",
472 closure_id
, new_kind
, upvar_span
, var_name
475 // Is this the closure whose kind is currently being inferred?
476 if closure_id
.to_def_id() != self.closure_def_id
{
477 debug
!("adjust_closure_kind: not current closure");
481 // closures start out as `Fn`.
482 let existing_kind
= self.current_closure_kind
;
485 "adjust_closure_kind: closure_id={:?}, existing_kind={:?}, new_kind={:?}",
486 closure_id
, existing_kind
, new_kind
489 match (existing_kind
, new_kind
) {
490 (ty
::ClosureKind
::Fn
, ty
::ClosureKind
::Fn
)
491 | (ty
::ClosureKind
::FnMut
, ty
::ClosureKind
::Fn
| ty
::ClosureKind
::FnMut
)
492 | (ty
::ClosureKind
::FnOnce
, _
) => {
496 (ty
::ClosureKind
::Fn
, ty
::ClosureKind
::FnMut
| ty
::ClosureKind
::FnOnce
)
497 | (ty
::ClosureKind
::FnMut
, ty
::ClosureKind
::FnOnce
) => {
498 // new kind is stronger than the old kind
499 self.current_closure_kind
= new_kind
;
500 self.current_origin
= Some((upvar_span
, var_name
));
506 impl<'a
, 'tcx
> euv
::Delegate
<'tcx
> for InferBorrowKind
<'a
, 'tcx
> {
509 place_with_id
: &PlaceWithHirId
<'tcx
>,
510 diag_expr_id
: hir
::HirId
,
511 mode
: euv
::ConsumeMode
,
514 "consume(place_with_id={:?}, diag_expr_id={:?}, mode={:?})",
515 place_with_id
, diag_expr_id
, mode
517 self.adjust_upvar_borrow_kind_for_consume(&place_with_id
, diag_expr_id
, mode
);
522 place_with_id
: &PlaceWithHirId
<'tcx
>,
523 diag_expr_id
: hir
::HirId
,
527 "borrow(place_with_id={:?}, diag_expr_id={:?}, bk={:?})",
528 place_with_id
, diag_expr_id
, bk
533 ty
::UniqueImmBorrow
=> {
534 self.adjust_upvar_borrow_kind_for_unique(&place_with_id
, diag_expr_id
);
537 self.adjust_upvar_borrow_kind_for_mut(&place_with_id
, diag_expr_id
);
542 fn mutate(&mut self, assignee_place
: &PlaceWithHirId
<'tcx
>, diag_expr_id
: hir
::HirId
) {
543 debug
!("mutate(assignee_place={:?}, diag_expr_id={:?})", assignee_place
, diag_expr_id
);
544 self.adjust_upvar_borrow_kind_for_mut(assignee_place
, diag_expr_id
);
548 fn var_name(tcx
: TyCtxt
<'_
>, var_hir_id
: hir
::HirId
) -> Symbol
{
549 tcx
.hir().name(var_hir_id
)