]> git.lizzy.rs Git - rust.git/blob - src/librustc_typeck/check/upvar.rs
Remove unused parts of ExprUseVisitor
[rust.git] / src / librustc_typeck / 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::middle::expr_use_visitor as euv;
36 use crate::middle::mem_categorization as mc;
37 use crate::middle::mem_categorization::Categorization;
38 use rustc::hir;
39 use rustc::hir::def_id::DefId;
40 use rustc::hir::def_id::LocalDefId;
41 use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor};
42 use rustc::infer::UpvarRegion;
43 use rustc::ty::{self, Ty, TyCtxt, UpvarSubsts};
44 use rustc_data_structures::fx::FxIndexMap;
45 use syntax::ast;
46 use syntax_pos::Span;
47
48 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
49     pub fn closure_analyze(&self, body: &'tcx hir::Body) {
50         InferBorrowKindVisitor { fcx: self }.visit_body(body);
51
52         // it's our job to process these.
53         assert!(self.deferred_call_resolutions.borrow().is_empty());
54     }
55 }
56
57 struct InferBorrowKindVisitor<'a, 'tcx> {
58     fcx: &'a FnCtxt<'a, 'tcx>,
59 }
60
61 impl<'a, 'tcx> Visitor<'tcx> for InferBorrowKindVisitor<'a, 'tcx> {
62     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
63         NestedVisitorMap::None
64     }
65
66     fn visit_expr(&mut self, expr: &'tcx hir::Expr) {
67         if let hir::ExprKind::Closure(cc, _, body_id, _, _) = expr.kind {
68             let body = self.fcx.tcx.hir().body(body_id);
69             self.visit_body(body);
70             self.fcx
71                 .analyze_closure(expr.hir_id, expr.span, body, cc);
72         }
73
74         intravisit::walk_expr(self, expr);
75     }
76 }
77
78 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
79     fn analyze_closure(
80         &self,
81         closure_hir_id: hir::HirId,
82         span: Span,
83         body: &hir::Body,
84         capture_clause: hir::CaptureClause,
85     ) {
86         /*!
87          * Analysis starting point.
88          */
89
90         debug!(
91             "analyze_closure(id={:?}, body.id={:?})",
92             closure_hir_id,
93             body.id()
94         );
95
96         // Extract the type of the closure.
97         let ty = self.node_ty(closure_hir_id);
98         let (closure_def_id, substs) = match ty.kind {
99             ty::Closure(def_id, substs) => (def_id, UpvarSubsts::Closure(substs)),
100             ty::Generator(def_id, substs, _) => (def_id, UpvarSubsts::Generator(substs)),
101             ty::Error => {
102                 // #51714: skip analysis when we have already encountered type errors
103                 return;
104             }
105             _ => {
106                 span_bug!(
107                     span,
108                     "type of closure expr {:?} is not a closure {:?}",
109                     closure_hir_id,
110                     ty
111                 );
112             }
113         };
114
115         let infer_kind = if let UpvarSubsts::Closure(closure_substs) = substs {
116             if self.closure_kind(closure_def_id, closure_substs).is_none() {
117                 Some(closure_substs)
118             } else {
119                 None
120             }
121         } else {
122             None
123         };
124
125         if let Some(upvars) = self.tcx.upvars(closure_def_id) {
126             let mut upvar_list: FxIndexMap<hir::HirId, ty::UpvarId> =
127                 FxIndexMap::with_capacity_and_hasher(upvars.len(), Default::default());
128             for (&var_hir_id, _) in upvars.iter() {
129                 let upvar_id = ty::UpvarId {
130                     var_path: ty::UpvarPath {
131                         hir_id: var_hir_id,
132                     },
133                     closure_expr_id: LocalDefId::from_def_id(closure_def_id),
134                 };
135                 debug!("seed upvar_id {:?}", upvar_id);
136                 // Adding the upvar Id to the list of Upvars, which will be added
137                 // to the map for the closure at the end of the for loop.
138                 upvar_list.insert(var_hir_id, upvar_id);
139
140                 let capture_kind = match capture_clause {
141                     hir::CaptureByValue => ty::UpvarCapture::ByValue,
142                     hir::CaptureByRef => {
143                         let origin = UpvarRegion(upvar_id, span);
144                         let upvar_region = self.next_region_var(origin);
145                         let upvar_borrow = ty::UpvarBorrow {
146                             kind: ty::ImmBorrow,
147                             region: upvar_region,
148                         };
149                         ty::UpvarCapture::ByRef(upvar_borrow)
150                     }
151                 };
152
153                 self.tables
154                     .borrow_mut()
155                     .upvar_capture_map
156                     .insert(upvar_id, capture_kind);
157             }
158             // Add the vector of upvars to the map keyed with the closure id.
159             // This gives us an easier access to them without having to call
160             // tcx.upvars again..
161             if !upvar_list.is_empty() {
162                 self.tables
163                     .borrow_mut()
164                     .upvar_list
165                     .insert(closure_def_id, upvar_list);
166             }
167         }
168
169         let body_owner_def_id = self.tcx.hir().body_owner_def_id(body.id());
170         assert_eq!(body_owner_def_id, closure_def_id);
171         let region_scope_tree = &self.tcx.region_scope_tree(body_owner_def_id);
172         let mut delegate = InferBorrowKind {
173             fcx: self,
174             closure_def_id: closure_def_id,
175             current_closure_kind: ty::ClosureKind::LATTICE_BOTTOM,
176             current_origin: None,
177             adjust_upvar_captures: ty::UpvarCaptureMap::default(),
178         };
179         euv::ExprUseVisitor::with_infer(
180             &mut delegate,
181             &self.infcx,
182             body_owner_def_id,
183             self.param_env,
184             region_scope_tree,
185             &self.tables.borrow(),
186         )
187         .consume_body(body);
188
189         if let Some(closure_substs) = infer_kind {
190             // Unify the (as yet unbound) type variable in the closure
191             // substs with the kind we inferred.
192             let inferred_kind = delegate.current_closure_kind;
193             let closure_kind_ty = closure_substs.closure_kind_ty(closure_def_id, self.tcx);
194             self.demand_eqtype(span, inferred_kind.to_ty(self.tcx), closure_kind_ty);
195
196             // If we have an origin, store it.
197             if let Some(origin) = delegate.current_origin {
198                 self.tables
199                     .borrow_mut()
200                     .closure_kind_origins_mut()
201                     .insert(closure_hir_id, origin);
202             }
203         }
204
205         self.tables
206             .borrow_mut()
207             .upvar_capture_map
208             .extend(delegate.adjust_upvar_captures);
209
210         // Now that we've analyzed the closure, we know how each
211         // variable is borrowed, and we know what traits the closure
212         // implements (Fn vs FnMut etc). We now have some updates to do
213         // with that information.
214         //
215         // Note that no closure type C may have an upvar of type C
216         // (though it may reference itself via a trait object). This
217         // results from the desugaring of closures to a struct like
218         // `Foo<..., UV0...UVn>`. If one of those upvars referenced
219         // C, then the type would have infinite size (and the
220         // inference algorithm will reject it).
221
222         // Equate the type variables for the upvars with the actual types.
223         let final_upvar_tys = self.final_upvar_tys(closure_hir_id);
224         debug!(
225             "analyze_closure: id={:?} substs={:?} final_upvar_tys={:?}",
226             closure_hir_id, substs, final_upvar_tys
227         );
228         for (upvar_ty, final_upvar_ty) in substs
229             .upvar_tys(closure_def_id, self.tcx)
230             .zip(final_upvar_tys)
231         {
232             self.demand_suptype(span, upvar_ty, final_upvar_ty);
233         }
234
235         // If we are also inferred the closure kind here,
236         // process any deferred resolutions.
237         let deferred_call_resolutions = self.remove_deferred_call_resolutions(closure_def_id);
238         for deferred_call_resolution in deferred_call_resolutions {
239             deferred_call_resolution.resolve(self);
240         }
241     }
242
243     // Returns a list of `ClosureUpvar`s for each upvar.
244     fn final_upvar_tys(&self, closure_id: hir::HirId) -> Vec<Ty<'tcx>> {
245         // Presently an unboxed closure type cannot "escape" out of a
246         // function, so we will only encounter ones that originated in the
247         // local crate or were inlined into it along with some function.
248         // This may change if abstract return types of some sort are
249         // implemented.
250         let tcx = self.tcx;
251         let closure_def_id = tcx.hir().local_def_id(closure_id);
252
253         tcx.upvars(closure_def_id).iter().flat_map(|upvars| {
254             upvars
255                 .iter()
256                 .map(|(&var_hir_id, _)| {
257                     let upvar_ty = self.node_ty(var_hir_id);
258                     let upvar_id = ty::UpvarId {
259                         var_path: ty::UpvarPath { hir_id: var_hir_id },
260                         closure_expr_id: LocalDefId::from_def_id(closure_def_id),
261                     };
262                     let capture = self.tables.borrow().upvar_capture(upvar_id);
263
264                     debug!(
265                         "var_id={:?} upvar_ty={:?} capture={:?}",
266                         var_hir_id, upvar_ty, capture
267                     );
268
269                     match capture {
270                         ty::UpvarCapture::ByValue => upvar_ty,
271                         ty::UpvarCapture::ByRef(borrow) => tcx.mk_ref(
272                             borrow.region,
273                             ty::TypeAndMut {
274                                 ty: upvar_ty,
275                                 mutbl: borrow.kind.to_mutbl_lossy(),
276                             },
277                         ),
278                     }
279                 })
280         })
281             .collect()
282     }
283 }
284
285 struct InferBorrowKind<'a, 'tcx> {
286     fcx: &'a FnCtxt<'a, 'tcx>,
287
288     // The def-id of the closure whose kind and upvar accesses are being inferred.
289     closure_def_id: DefId,
290
291     // The kind that we have inferred that the current closure
292     // requires. Note that we *always* infer a minimal kind, even if
293     // we don't always *use* that in the final result (i.e., sometimes
294     // we've taken the closure kind from the expectations instead, and
295     // for generators we don't even implement the closure traits
296     // really).
297     current_closure_kind: ty::ClosureKind,
298
299     // If we modified `current_closure_kind`, this field contains a `Some()` with the
300     // variable access that caused us to do so.
301     current_origin: Option<(Span, ast::Name)>,
302
303     // For each upvar that we access, we track the minimal kind of
304     // access we need (ref, ref mut, move, etc).
305     adjust_upvar_captures: ty::UpvarCaptureMap<'tcx>,
306 }
307
308 impl<'a, 'tcx> InferBorrowKind<'a, 'tcx> {
309     fn adjust_upvar_borrow_kind_for_consume(
310         &mut self,
311         cmt: &mc::cmt_<'tcx>,
312         mode: euv::ConsumeMode,
313     ) {
314         debug!(
315             "adjust_upvar_borrow_kind_for_consume(cmt={:?}, mode={:?})",
316             cmt, mode
317         );
318
319         // we only care about moves
320         match mode {
321             euv::Copy => {
322                 return;
323             }
324             euv::Move => {}
325         }
326
327         let tcx = self.fcx.tcx;
328
329         // watch out for a move of the deref of a borrowed pointer;
330         // for that to be legal, the upvar would have to be borrowed
331         // by value instead
332         let guarantor = cmt.guarantor();
333         debug!(
334             "adjust_upvar_borrow_kind_for_consume: guarantor={:?}",
335             guarantor
336         );
337         debug!(
338             "adjust_upvar_borrow_kind_for_consume: guarantor.cat={:?}",
339             guarantor.cat
340         );
341         if let Categorization::Deref(_, mc::BorrowedPtr(..)) = guarantor.cat {
342             debug!(
343                 "adjust_upvar_borrow_kind_for_consume: found deref with note {:?}",
344                 cmt.note
345             );
346             match guarantor.note {
347                 mc::NoteUpvarRef(upvar_id) => {
348                     debug!(
349                         "adjust_upvar_borrow_kind_for_consume: \
350                          setting upvar_id={:?} to by value",
351                         upvar_id
352                     );
353
354                     // to move out of an upvar, this must be a FnOnce closure
355                     self.adjust_closure_kind(
356                         upvar_id.closure_expr_id,
357                         ty::ClosureKind::FnOnce,
358                         guarantor.span,
359                         var_name(tcx, upvar_id.var_path.hir_id),
360                     );
361
362                     self.adjust_upvar_captures
363                         .insert(upvar_id, ty::UpvarCapture::ByValue);
364                 }
365                 mc::NoteClosureEnv(upvar_id) => {
366                     // we get just a closureenv ref if this is a
367                     // `move` closure, or if the upvar has already
368                     // been inferred to by-value. In any case, we
369                     // must still adjust the kind of the closure
370                     // to be a FnOnce closure to permit moves out
371                     // of the environment.
372                     self.adjust_closure_kind(
373                         upvar_id.closure_expr_id,
374                         ty::ClosureKind::FnOnce,
375                         guarantor.span,
376                         var_name(tcx, upvar_id.var_path.hir_id),
377                     );
378                 }
379                 mc::NoteIndex | mc::NoteNone => {}
380             }
381         }
382     }
383
384     /// Indicates that `cmt` is being directly mutated (e.g., assigned
385     /// to). If cmt contains any by-ref upvars, this implies that
386     /// those upvars must be borrowed using an `&mut` borrow.
387     fn adjust_upvar_borrow_kind_for_mut(&mut self, cmt: &mc::cmt_<'tcx>) {
388         debug!("adjust_upvar_borrow_kind_for_mut(cmt={:?})", cmt);
389
390         match cmt.cat.clone() {
391             Categorization::Deref(base, mc::Unique)
392             | Categorization::Interior(base, _)
393             | Categorization::Downcast(base, _) => {
394                 // Interior or owned data is mutable if base is
395                 // mutable, so iterate to the base.
396                 self.adjust_upvar_borrow_kind_for_mut(&base);
397             }
398
399             Categorization::Deref(base, mc::BorrowedPtr(..)) => {
400                 if !self.try_adjust_upvar_deref(cmt, ty::MutBorrow) {
401                     // assignment to deref of an `&mut`
402                     // borrowed pointer implies that the
403                     // pointer itself must be unique, but not
404                     // necessarily *mutable*
405                     self.adjust_upvar_borrow_kind_for_unique(&base);
406                 }
407             }
408
409             Categorization::Deref(_, mc::UnsafePtr(..))
410             | Categorization::StaticItem
411             | Categorization::ThreadLocal
412             | Categorization::Rvalue
413             | Categorization::Local(_)
414             | Categorization::Upvar(..) => {
415                 return;
416             }
417         }
418     }
419
420     fn adjust_upvar_borrow_kind_for_unique(&mut self, cmt: &mc::cmt_<'tcx>) {
421         debug!("adjust_upvar_borrow_kind_for_unique(cmt={:?})", cmt);
422
423         match cmt.cat.clone() {
424             Categorization::Deref(base, mc::Unique)
425             | Categorization::Interior(base, _)
426             | Categorization::Downcast(base, _) => {
427                 // Interior or owned data is unique if base is
428                 // unique.
429                 self.adjust_upvar_borrow_kind_for_unique(&base);
430             }
431
432             Categorization::Deref(base, mc::BorrowedPtr(..)) => {
433                 if !self.try_adjust_upvar_deref(cmt, ty::UniqueImmBorrow) {
434                     // for a borrowed pointer to be unique, its
435                     // base must be unique
436                     self.adjust_upvar_borrow_kind_for_unique(&base);
437                 }
438             }
439
440             Categorization::Deref(_, mc::UnsafePtr(..))
441             | Categorization::StaticItem
442             | Categorization::ThreadLocal
443             | Categorization::Rvalue
444             | Categorization::Local(_)
445             | Categorization::Upvar(..) => {}
446         }
447     }
448
449     fn try_adjust_upvar_deref(
450         &mut self,
451         cmt: &mc::cmt_<'tcx>,
452         borrow_kind: ty::BorrowKind,
453     ) -> bool {
454         assert!(match borrow_kind {
455             ty::MutBorrow => true,
456             ty::UniqueImmBorrow => true,
457
458             // imm borrows never require adjusting any kinds, so we don't wind up here
459             ty::ImmBorrow => false,
460         });
461
462         let tcx = self.fcx.tcx;
463
464         match cmt.note {
465             mc::NoteUpvarRef(upvar_id) => {
466                 // if this is an implicit deref of an
467                 // upvar, then we need to modify the
468                 // borrow_kind of the upvar to make sure it
469                 // is inferred to mutable if necessary
470                 self.adjust_upvar_borrow_kind(upvar_id, borrow_kind);
471
472                 // also need to be in an FnMut closure since this is not an ImmBorrow
473                 self.adjust_closure_kind(
474                     upvar_id.closure_expr_id,
475                     ty::ClosureKind::FnMut,
476                     cmt.span,
477                     var_name(tcx, upvar_id.var_path.hir_id),
478                 );
479
480                 true
481             }
482             mc::NoteClosureEnv(upvar_id) => {
483                 // this kind of deref occurs in a `move` closure, or
484                 // for a by-value upvar; in either case, to mutate an
485                 // upvar, we need to be an FnMut closure
486                 self.adjust_closure_kind(
487                     upvar_id.closure_expr_id,
488                     ty::ClosureKind::FnMut,
489                     cmt.span,
490                     var_name(tcx, upvar_id.var_path.hir_id),
491                 );
492
493                 true
494             }
495             mc::NoteIndex | mc::NoteNone => false,
496         }
497     }
498
499     /// We infer the borrow_kind with which to borrow upvars in a stack closure.
500     /// The borrow_kind basically follows a lattice of `imm < unique-imm < mut`,
501     /// moving from left to right as needed (but never right to left).
502     /// Here the argument `mutbl` is the borrow_kind that is required by
503     /// some particular use.
504     fn adjust_upvar_borrow_kind(&mut self, upvar_id: ty::UpvarId, kind: ty::BorrowKind) {
505         let upvar_capture = self
506             .adjust_upvar_captures
507             .get(&upvar_id)
508             .cloned()
509             .unwrap_or_else(|| self.fcx.tables.borrow().upvar_capture(upvar_id));
510         debug!(
511             "adjust_upvar_borrow_kind(upvar_id={:?}, upvar_capture={:?}, kind={:?})",
512             upvar_id, upvar_capture, kind
513         );
514
515         match upvar_capture {
516             ty::UpvarCapture::ByValue => {
517                 // Upvar is already by-value, the strongest criteria.
518             }
519             ty::UpvarCapture::ByRef(mut upvar_borrow) => {
520                 match (upvar_borrow.kind, kind) {
521                     // Take RHS:
522                     (ty::ImmBorrow, ty::UniqueImmBorrow)
523                     | (ty::ImmBorrow, ty::MutBorrow)
524                     | (ty::UniqueImmBorrow, ty::MutBorrow) => {
525                         upvar_borrow.kind = kind;
526                         self.adjust_upvar_captures
527                             .insert(upvar_id, ty::UpvarCapture::ByRef(upvar_borrow));
528                     }
529                     // Take LHS:
530                     (ty::ImmBorrow, ty::ImmBorrow)
531                     | (ty::UniqueImmBorrow, ty::ImmBorrow)
532                     | (ty::UniqueImmBorrow, ty::UniqueImmBorrow)
533                     | (ty::MutBorrow, _) => {}
534                 }
535             }
536         }
537     }
538
539     fn adjust_closure_kind(
540         &mut self,
541         closure_id: LocalDefId,
542         new_kind: ty::ClosureKind,
543         upvar_span: Span,
544         var_name: ast::Name,
545     ) {
546         debug!(
547             "adjust_closure_kind(closure_id={:?}, new_kind={:?}, upvar_span={:?}, var_name={})",
548             closure_id, new_kind, upvar_span, var_name
549         );
550
551         // Is this the closure whose kind is currently being inferred?
552         if closure_id.to_def_id() != self.closure_def_id {
553             debug!("adjust_closure_kind: not current closure");
554             return;
555         }
556
557         // closures start out as `Fn`.
558         let existing_kind = self.current_closure_kind;
559
560         debug!(
561             "adjust_closure_kind: closure_id={:?}, existing_kind={:?}, new_kind={:?}",
562             closure_id, existing_kind, new_kind
563         );
564
565         match (existing_kind, new_kind) {
566             (ty::ClosureKind::Fn, ty::ClosureKind::Fn)
567             | (ty::ClosureKind::FnMut, ty::ClosureKind::Fn)
568             | (ty::ClosureKind::FnMut, ty::ClosureKind::FnMut)
569             | (ty::ClosureKind::FnOnce, _) => {
570                 // no change needed
571             }
572
573             (ty::ClosureKind::Fn, ty::ClosureKind::FnMut)
574             | (ty::ClosureKind::Fn, ty::ClosureKind::FnOnce)
575             | (ty::ClosureKind::FnMut, ty::ClosureKind::FnOnce) => {
576                 // new kind is stronger than the old kind
577                 self.current_closure_kind = new_kind;
578                 self.current_origin = Some((upvar_span, var_name));
579             }
580         }
581     }
582 }
583
584 impl<'a, 'tcx> euv::Delegate<'tcx> for InferBorrowKind<'a, 'tcx> {
585     fn consume(&mut self, cmt: &mc::cmt_<'tcx>,mode: euv::ConsumeMode) {
586         debug!("consume(cmt={:?},mode={:?})", cmt, mode);
587         self.adjust_upvar_borrow_kind_for_consume(cmt, mode);
588     }
589
590     fn borrow(&mut self, cmt: &mc::cmt_<'tcx>, bk: ty::BorrowKind) {
591         debug!("borrow(cmt={:?}, bk={:?})", cmt, bk);
592
593         match bk {
594             ty::ImmBorrow => {}
595             ty::UniqueImmBorrow => {
596                 self.adjust_upvar_borrow_kind_for_unique(cmt);
597             }
598             ty::MutBorrow => {
599                 self.adjust_upvar_borrow_kind_for_mut(cmt);
600             }
601         }
602     }
603
604     fn mutate(&mut self, assignee_cmt: &mc::cmt_<'tcx>) {
605         debug!("mutate(assignee_cmt={:?})", assignee_cmt);
606
607         self.adjust_upvar_borrow_kind_for_mut(assignee_cmt);
608     }
609 }
610
611 fn var_name(tcx: TyCtxt<'_>, var_hir_id: hir::HirId) -> ast::Name {
612     tcx.hir().name(var_hir_id)
613 }