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
205 for (upvar_ty
, final_upvar_ty
) in substs
.upvar_tys().zip(final_upvar_tys
) {
206 self.demand_suptype(span
, upvar_ty
, final_upvar_ty
);
209 // If we are also inferred the closure kind here,
210 // process any deferred resolutions.
211 let deferred_call_resolutions
= self.remove_deferred_call_resolutions(closure_def_id
);
212 for deferred_call_resolution
in deferred_call_resolutions
{
213 deferred_call_resolution
.resolve(self);
217 // Returns a list of `Ty`s for each upvar.
218 fn final_upvar_tys(&self, closure_id
: hir
::HirId
) -> Vec
<Ty
<'tcx
>> {
219 // Presently an unboxed closure type cannot "escape" out of a
220 // function, so we will only encounter ones that originated in the
221 // local crate or were inlined into it along with some function.
222 // This may change if abstract return types of some sort are
225 let closure_def_id
= tcx
.hir().local_def_id(closure_id
);
227 tcx
.upvars_mentioned(closure_def_id
)
230 upvars
.iter().map(|(&var_hir_id
, _
)| {
231 let upvar_ty
= self.node_ty(var_hir_id
);
232 let upvar_id
= ty
::UpvarId
{
233 var_path
: ty
::UpvarPath { hir_id: var_hir_id }
,
234 closure_expr_id
: closure_def_id
,
236 let capture
= self.typeck_results
.borrow().upvar_capture(upvar_id
);
238 debug
!("var_id={:?} upvar_ty={:?} capture={:?}", var_hir_id
, upvar_ty
, capture
);
241 ty
::UpvarCapture
::ByValue(_
) => upvar_ty
,
242 ty
::UpvarCapture
::ByRef(borrow
) => tcx
.mk_ref(
244 ty
::TypeAndMut { ty: upvar_ty, mutbl: borrow.kind.to_mutbl_lossy() }
,
253 struct InferBorrowKind
<'a
, 'tcx
> {
254 fcx
: &'a FnCtxt
<'a
, 'tcx
>,
256 // The def-id of the closure whose kind and upvar accesses are being inferred.
257 closure_def_id
: DefId
,
259 // The kind that we have inferred that the current closure
260 // requires. Note that we *always* infer a minimal kind, even if
261 // we don't always *use* that in the final result (i.e., sometimes
262 // we've taken the closure kind from the expectations instead, and
263 // for generators we don't even implement the closure traits
265 current_closure_kind
: ty
::ClosureKind
,
267 // If we modified `current_closure_kind`, this field contains a `Some()` with the
268 // variable access that caused us to do so.
269 current_origin
: Option
<(Span
, Symbol
)>,
271 // For each upvar that we access, we track the minimal kind of
272 // access we need (ref, ref mut, move, etc).
273 adjust_upvar_captures
: ty
::UpvarCaptureMap
<'tcx
>,
276 impl<'a
, 'tcx
> InferBorrowKind
<'a
, 'tcx
> {
277 fn adjust_upvar_borrow_kind_for_consume(
279 place_with_id
: &PlaceWithHirId
<'tcx
>,
280 mode
: euv
::ConsumeMode
,
283 "adjust_upvar_borrow_kind_for_consume(place_with_id={:?}, mode={:?})",
287 // we only care about moves
295 let tcx
= self.fcx
.tcx
;
296 let upvar_id
= if let PlaceBase
::Upvar(upvar_id
) = place_with_id
.place
.base
{
302 debug
!("adjust_upvar_borrow_kind_for_consume: upvar={:?}", upvar_id
);
304 let usage_span
= tcx
.hir().span(place_with_id
.hir_id
);
306 // To move out of an upvar, this must be a FnOnce closure
307 self.adjust_closure_kind(
308 upvar_id
.closure_expr_id
,
309 ty
::ClosureKind
::FnOnce
,
311 var_name(tcx
, upvar_id
.var_path
.hir_id
),
314 // In a case like `let pat = upvar`, don't use the span
315 // of the pattern, as this just looks confusing.
316 let by_value_span
= match tcx
.hir().get(place_with_id
.hir_id
) {
317 hir
::Node
::Pat(_
) => None
,
318 _
=> Some(usage_span
),
321 let new_capture
= ty
::UpvarCapture
::ByValue(by_value_span
);
322 match self.adjust_upvar_captures
.entry(upvar_id
) {
323 Entry
::Occupied(mut e
) => {
325 // We always overwrite `ByRef`, since we require
326 // that the upvar be available by value.
328 // If we had a previous by-value usage without a specific
329 // span, use ours instead. Otherwise, keep the first span
330 // we encountered, since there isn't an obviously better one.
331 ty
::UpvarCapture
::ByRef(_
) | ty
::UpvarCapture
::ByValue(None
) => {
332 e
.insert(new_capture
);
337 Entry
::Vacant(e
) => {
338 e
.insert(new_capture
);
343 /// Indicates that `place_with_id` is being directly mutated (e.g., assigned
344 /// to). If the place is based on a by-ref upvar, this implies that
345 /// the upvar must be borrowed using an `&mut` borrow.
346 fn adjust_upvar_borrow_kind_for_mut(&mut self, place_with_id
: &PlaceWithHirId
<'tcx
>) {
347 debug
!("adjust_upvar_borrow_kind_for_mut(place_with_id={:?})", place_with_id
);
349 if let PlaceBase
::Upvar(upvar_id
) = place_with_id
.place
.base
{
350 let mut borrow_kind
= ty
::MutBorrow
;
351 for pointer_ty
in place_with_id
.place
.deref_tys() {
352 match pointer_ty
.kind() {
353 // Raw pointers don't inherit mutability.
354 ty
::RawPtr(_
) => return,
355 // assignment to deref of an `&mut`
356 // borrowed pointer implies that the
357 // pointer itself must be unique, but not
358 // necessarily *mutable*
359 ty
::Ref(.., hir
::Mutability
::Mut
) => borrow_kind
= ty
::UniqueImmBorrow
,
363 self.adjust_upvar_deref(
365 self.fcx
.tcx
.hir().span(place_with_id
.hir_id
),
371 fn adjust_upvar_borrow_kind_for_unique(&mut self, place_with_id
: &PlaceWithHirId
<'tcx
>) {
372 debug
!("adjust_upvar_borrow_kind_for_unique(place_with_id={:?})", place_with_id
);
374 if let PlaceBase
::Upvar(upvar_id
) = place_with_id
.place
.base
{
375 if place_with_id
.place
.deref_tys().any(ty
::TyS
::is_unsafe_ptr
) {
376 // Raw pointers don't inherit mutability.
379 // for a borrowed pointer to be unique, its base must be unique
380 self.adjust_upvar_deref(
382 self.fcx
.tcx
.hir().span(place_with_id
.hir_id
),
388 fn adjust_upvar_deref(
390 upvar_id
: ty
::UpvarId
,
392 borrow_kind
: ty
::BorrowKind
,
394 assert
!(match borrow_kind
{
395 ty
::MutBorrow
=> true,
396 ty
::UniqueImmBorrow
=> true,
398 // imm borrows never require adjusting any kinds, so we don't wind up here
399 ty
::ImmBorrow
=> false,
402 let tcx
= self.fcx
.tcx
;
404 // if this is an implicit deref of an
405 // upvar, then we need to modify the
406 // borrow_kind of the upvar to make sure it
407 // is inferred to mutable if necessary
408 self.adjust_upvar_borrow_kind(upvar_id
, borrow_kind
);
410 // also need to be in an FnMut closure since this is not an ImmBorrow
411 self.adjust_closure_kind(
412 upvar_id
.closure_expr_id
,
413 ty
::ClosureKind
::FnMut
,
415 var_name(tcx
, upvar_id
.var_path
.hir_id
),
419 /// We infer the borrow_kind with which to borrow upvars in a stack closure.
420 /// The borrow_kind basically follows a lattice of `imm < unique-imm < mut`,
421 /// moving from left to right as needed (but never right to left).
422 /// Here the argument `mutbl` is the borrow_kind that is required by
423 /// some particular use.
424 fn adjust_upvar_borrow_kind(&mut self, upvar_id
: ty
::UpvarId
, kind
: ty
::BorrowKind
) {
425 let upvar_capture
= self
426 .adjust_upvar_captures
429 .unwrap_or_else(|| self.fcx
.typeck_results
.borrow().upvar_capture(upvar_id
));
431 "adjust_upvar_borrow_kind(upvar_id={:?}, upvar_capture={:?}, kind={:?})",
432 upvar_id
, upvar_capture
, kind
435 match upvar_capture
{
436 ty
::UpvarCapture
::ByValue(_
) => {
437 // Upvar is already by-value, the strongest criteria.
439 ty
::UpvarCapture
::ByRef(mut upvar_borrow
) => {
440 match (upvar_borrow
.kind
, kind
) {
442 (ty
::ImmBorrow
, ty
::UniqueImmBorrow
| ty
::MutBorrow
)
443 | (ty
::UniqueImmBorrow
, ty
::MutBorrow
) => {
444 upvar_borrow
.kind
= kind
;
445 self.adjust_upvar_captures
446 .insert(upvar_id
, ty
::UpvarCapture
::ByRef(upvar_borrow
));
449 (ty
::ImmBorrow
, ty
::ImmBorrow
)
450 | (ty
::UniqueImmBorrow
, ty
::ImmBorrow
| ty
::UniqueImmBorrow
)
451 | (ty
::MutBorrow
, _
) => {}
457 fn adjust_closure_kind(
459 closure_id
: LocalDefId
,
460 new_kind
: ty
::ClosureKind
,
465 "adjust_closure_kind(closure_id={:?}, new_kind={:?}, upvar_span={:?}, var_name={})",
466 closure_id
, new_kind
, upvar_span
, var_name
469 // Is this the closure whose kind is currently being inferred?
470 if closure_id
.to_def_id() != self.closure_def_id
{
471 debug
!("adjust_closure_kind: not current closure");
475 // closures start out as `Fn`.
476 let existing_kind
= self.current_closure_kind
;
479 "adjust_closure_kind: closure_id={:?}, existing_kind={:?}, new_kind={:?}",
480 closure_id
, existing_kind
, new_kind
483 match (existing_kind
, new_kind
) {
484 (ty
::ClosureKind
::Fn
, ty
::ClosureKind
::Fn
)
485 | (ty
::ClosureKind
::FnMut
, ty
::ClosureKind
::Fn
| ty
::ClosureKind
::FnMut
)
486 | (ty
::ClosureKind
::FnOnce
, _
) => {
490 (ty
::ClosureKind
::Fn
, ty
::ClosureKind
::FnMut
| ty
::ClosureKind
::FnOnce
)
491 | (ty
::ClosureKind
::FnMut
, ty
::ClosureKind
::FnOnce
) => {
492 // new kind is stronger than the old kind
493 self.current_closure_kind
= new_kind
;
494 self.current_origin
= Some((upvar_span
, var_name
));
500 impl<'a
, 'tcx
> euv
::Delegate
<'tcx
> for InferBorrowKind
<'a
, 'tcx
> {
501 fn consume(&mut self, place_with_id
: &PlaceWithHirId
<'tcx
>, mode
: euv
::ConsumeMode
) {
502 debug
!("consume(place_with_id={:?},mode={:?})", place_with_id
, mode
);
503 self.adjust_upvar_borrow_kind_for_consume(place_with_id
, mode
);
506 fn borrow(&mut self, place_with_id
: &PlaceWithHirId
<'tcx
>, bk
: ty
::BorrowKind
) {
507 debug
!("borrow(place_with_id={:?}, bk={:?})", place_with_id
, bk
);
511 ty
::UniqueImmBorrow
=> {
512 self.adjust_upvar_borrow_kind_for_unique(place_with_id
);
515 self.adjust_upvar_borrow_kind_for_mut(place_with_id
);
520 fn mutate(&mut self, assignee_place
: &PlaceWithHirId
<'tcx
>) {
521 debug
!("mutate(assignee_place={:?})", assignee_place
);
523 self.adjust_upvar_borrow_kind_for_mut(assignee_place
);
527 fn var_name(tcx
: TyCtxt
<'_
>, var_hir_id
: hir
::HirId
) -> Symbol
{
528 tcx
.hir().name(var_hir_id
)