]> git.lizzy.rs Git - rust.git/blob - src/librustc_typeck/check/upvar.rs
Auto merge of #28585 - ranma42:simpler-panic, r=alexcrichton
[rust.git] / src / librustc_typeck / check / upvar.rs
1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 //! ### Inferring borrow kinds for upvars
12 //!
13 //! Whenever there is a closure expression, we need to determine how each
14 //! upvar is used. We do this by initially assigning each upvar an
15 //! immutable "borrow kind" (see `ty::BorrowKind` for details) and then
16 //! "escalating" the kind as needed. The borrow kind proceeds according to
17 //! the following lattice:
18 //!
19 //!     ty::ImmBorrow -> ty::UniqueImmBorrow -> ty::MutBorrow
20 //!
21 //! So, for example, if we see an assignment `x = 5` to an upvar `x`, we
22 //! will promote its borrow kind to mutable borrow. If we see an `&mut x`
23 //! we'll do the same. Naturally, this applies not just to the upvar, but
24 //! to everything owned by `x`, so the result is the same for something
25 //! like `x.f = 5` and so on (presuming `x` is not a borrowed pointer to a
26 //! struct). These adjustments are performed in
27 //! `adjust_upvar_borrow_kind()` (you can trace backwards through the code
28 //! from there).
29 //!
30 //! The fact that we are inferring borrow kinds as we go results in a
31 //! semi-hacky interaction with mem-categorization. In particular,
32 //! mem-categorization will query the current borrow kind as it
33 //! categorizes, and we'll return the *current* value, but this may get
34 //! adjusted later. Therefore, in this module, we generally ignore the
35 //! borrow kind (and derived mutabilities) that are returned from
36 //! mem-categorization, since they may be inaccurate. (Another option
37 //! would be to use a unification scheme, where instead of returning a
38 //! concrete borrow kind like `ty::ImmBorrow`, we return a
39 //! `ty::InferBorrow(upvar_id)` or something like that, but this would
40 //! then mean that all later passes would have to check for these figments
41 //! and report an error, and it just seems like more mess in the end.)
42
43 use super::FnCtxt;
44
45 use check::demand;
46 use middle::def_id::DefId;
47 use middle::expr_use_visitor as euv;
48 use middle::mem_categorization as mc;
49 use middle::ty::{self, Ty};
50 use middle::infer::{InferCtxt, UpvarRegion};
51 use std::collections::HashSet;
52 use syntax::ast;
53 use syntax::codemap::Span;
54 use rustc_front::hir;
55 use rustc_front::visit::{self, Visitor};
56
57 ///////////////////////////////////////////////////////////////////////////
58 // PUBLIC ENTRY POINTS
59
60 pub fn closure_analyze_fn(fcx: &FnCtxt,
61                           _id: ast::NodeId,
62                           _decl: &hir::FnDecl,
63                           body: &hir::Block)
64 {
65     let mut seed = SeedBorrowKind::new(fcx);
66     seed.visit_block(body);
67     let closures_with_inferred_kinds = seed.closures_with_inferred_kinds;
68
69     let mut adjust = AdjustBorrowKind::new(fcx, &closures_with_inferred_kinds);
70     adjust.visit_block(body);
71
72     // it's our job to process these.
73     assert!(fcx.inh.deferred_call_resolutions.borrow().is_empty());
74 }
75
76 ///////////////////////////////////////////////////////////////////////////
77 // SEED BORROW KIND
78
79 struct SeedBorrowKind<'a,'tcx:'a> {
80     fcx: &'a FnCtxt<'a,'tcx>,
81     closures_with_inferred_kinds: HashSet<ast::NodeId>,
82 }
83
84 impl<'a, 'tcx, 'v> Visitor<'v> for SeedBorrowKind<'a, 'tcx> {
85     fn visit_expr(&mut self, expr: &hir::Expr) {
86         match expr.node {
87             hir::ExprClosure(cc, _, ref body) => {
88                 self.check_closure(expr, cc, &**body);
89             }
90
91             _ => { }
92         }
93
94         visit::walk_expr(self, expr);
95     }
96
97     // Skip all items; they aren't in the same context.
98     fn visit_item(&mut self, _: &'v hir::Item) { }
99 }
100
101 impl<'a,'tcx> SeedBorrowKind<'a,'tcx> {
102     fn new(fcx: &'a FnCtxt<'a,'tcx>) -> SeedBorrowKind<'a,'tcx> {
103         SeedBorrowKind { fcx: fcx, closures_with_inferred_kinds: HashSet::new() }
104     }
105
106     fn tcx(&self) -> &'a ty::ctxt<'tcx> {
107         self.fcx.tcx()
108     }
109
110     fn infcx(&self) -> &'a InferCtxt<'a,'tcx> {
111         self.fcx.infcx()
112     }
113
114     fn check_closure(&mut self,
115                      expr: &hir::Expr,
116                      capture_clause: hir::CaptureClause,
117                      _body: &hir::Block)
118     {
119         let closure_def_id = DefId::local(expr.id);
120         if !self.fcx.inh.tables.borrow().closure_kinds.contains_key(&closure_def_id) {
121             self.closures_with_inferred_kinds.insert(expr.id);
122             self.fcx.inh.tables.borrow_mut().closure_kinds
123                                             .insert(closure_def_id, ty::FnClosureKind);
124             debug!("check_closure: adding closure_id={:?} to closures_with_inferred_kinds",
125                    closure_def_id);
126         }
127
128         self.tcx().with_freevars(expr.id, |freevars| {
129             for freevar in freevars {
130                 let var_node_id = freevar.def.local_node_id();
131                 let upvar_id = ty::UpvarId { var_id: var_node_id,
132                                              closure_expr_id: expr.id };
133                 debug!("seed upvar_id {:?}", upvar_id);
134
135                 let capture_kind = match capture_clause {
136                     hir::CaptureByValue => {
137                         ty::UpvarCapture::ByValue
138                     }
139                     hir::CaptureByRef => {
140                         let origin = UpvarRegion(upvar_id, expr.span);
141                         let freevar_region = self.infcx().next_region_var(origin);
142                         let upvar_borrow = ty::UpvarBorrow { kind: ty::ImmBorrow,
143                                                              region: freevar_region };
144                         ty::UpvarCapture::ByRef(upvar_borrow)
145                     }
146                 };
147
148                 self.fcx.inh.tables.borrow_mut().upvar_capture_map.insert(upvar_id, capture_kind);
149             }
150         });
151     }
152 }
153
154 ///////////////////////////////////////////////////////////////////////////
155 // ADJUST BORROW KIND
156
157 struct AdjustBorrowKind<'a,'tcx:'a> {
158     fcx: &'a FnCtxt<'a,'tcx>,
159     closures_with_inferred_kinds: &'a HashSet<ast::NodeId>,
160 }
161
162 impl<'a,'tcx> AdjustBorrowKind<'a,'tcx> {
163     fn new(fcx: &'a FnCtxt<'a,'tcx>,
164            closures_with_inferred_kinds: &'a HashSet<ast::NodeId>)
165            -> AdjustBorrowKind<'a,'tcx> {
166         AdjustBorrowKind { fcx: fcx, closures_with_inferred_kinds: closures_with_inferred_kinds }
167     }
168
169     fn analyze_closure(&mut self,
170                        id: ast::NodeId,
171                        span: Span,
172                        decl: &hir::FnDecl,
173                        body: &hir::Block) {
174         /*!
175          * Analysis starting point.
176          */
177
178         debug!("analyze_closure(id={:?}, body.id={:?})", id, body.id);
179
180         {
181             let mut euv = euv::ExprUseVisitor::new(self, self.fcx.infcx());
182             euv.walk_fn(decl, body);
183         }
184
185         // Now that we've analyzed the closure, we know how each
186         // variable is borrowed, and we know what traits the closure
187         // implements (Fn vs FnMut etc). We now have some updates to do
188         // with that information.
189         //
190         // Note that no closure type C may have an upvar of type C
191         // (though it may reference itself via a trait object). This
192         // results from the desugaring of closures to a struct like
193         // `Foo<..., UV0...UVn>`. If one of those upvars referenced
194         // C, then the type would have infinite size (and the
195         // inference algorithm will reject it).
196
197         // Extract the type variables UV0...UVn.
198         let closure_substs = match self.fcx.node_ty(id).sty {
199             ty::TyClosure(_, ref substs) => substs,
200             ref t => {
201                 self.fcx.tcx().sess.span_bug(
202                     span,
203                     &format!("type of closure expr {:?} is not a closure {:?}",
204                              id, t));
205             }
206         };
207
208         // Equate the type variables with the actual types.
209         let final_upvar_tys = self.final_upvar_tys(id);
210         debug!("analyze_closure: id={:?} closure_substs={:?} final_upvar_tys={:?}",
211                id, closure_substs, final_upvar_tys);
212         for (&upvar_ty, final_upvar_ty) in closure_substs.upvar_tys.iter().zip(final_upvar_tys) {
213             demand::eqtype(self.fcx, span, final_upvar_ty, upvar_ty);
214         }
215
216         // Now we must process and remove any deferred resolutions,
217         // since we have a concrete closure kind.
218         let closure_def_id = DefId::local(id);
219         if self.closures_with_inferred_kinds.contains(&id) {
220             let mut deferred_call_resolutions =
221                 self.fcx.remove_deferred_call_resolutions(closure_def_id);
222             for deferred_call_resolution in &mut deferred_call_resolutions {
223                 deferred_call_resolution.resolve(self.fcx);
224             }
225         }
226     }
227
228     // Returns a list of `ClosureUpvar`s for each upvar.
229     fn final_upvar_tys(&mut self, closure_id: ast::NodeId) -> Vec<Ty<'tcx>> {
230         // Presently an unboxed closure type cannot "escape" out of a
231         // function, so we will only encounter ones that originated in the
232         // local crate or were inlined into it along with some function.
233         // This may change if abstract return types of some sort are
234         // implemented.
235         let tcx = self.fcx.tcx();
236         tcx.with_freevars(closure_id, |freevars| {
237             freevars.iter()
238                     .map(|freevar| {
239                         let freevar_def_id = freevar.def.def_id();
240                         let freevar_ty = self.fcx.node_ty(freevar_def_id.node);
241                         let upvar_id = ty::UpvarId {
242                             var_id: freevar_def_id.node,
243                             closure_expr_id: closure_id
244                         };
245                         let capture = self.fcx.infcx().upvar_capture(upvar_id).unwrap();
246
247                         debug!("freevar_def_id={:?} freevar_ty={:?} capture={:?}",
248                                freevar_def_id, freevar_ty, capture);
249
250                         match capture {
251                             ty::UpvarCapture::ByValue => freevar_ty,
252                             ty::UpvarCapture::ByRef(borrow) =>
253                                 tcx.mk_ref(tcx.mk_region(borrow.region),
254                                            ty::TypeAndMut {
255                                                ty: freevar_ty,
256                                                mutbl: borrow.kind.to_mutbl_lossy(),
257                                            }),
258                         }
259                     })
260                     .collect()
261             })
262     }
263
264     fn adjust_upvar_borrow_kind_for_consume(&self,
265                                             cmt: mc::cmt<'tcx>,
266                                             mode: euv::ConsumeMode)
267     {
268         debug!("adjust_upvar_borrow_kind_for_consume(cmt={:?}, mode={:?})",
269                cmt, mode);
270
271         // we only care about moves
272         match mode {
273             euv::Copy => { return; }
274             euv::Move(_) => { }
275         }
276
277         // watch out for a move of the deref of a borrowed pointer;
278         // for that to be legal, the upvar would have to be borrowed
279         // by value instead
280         let guarantor = cmt.guarantor();
281         debug!("adjust_upvar_borrow_kind_for_consume: guarantor={:?}",
282                guarantor);
283         match guarantor.cat {
284             mc::cat_deref(_, _, mc::BorrowedPtr(..)) |
285             mc::cat_deref(_, _, mc::Implicit(..)) => {
286                 match cmt.note {
287                     mc::NoteUpvarRef(upvar_id) => {
288                         debug!("adjust_upvar_borrow_kind_for_consume: \
289                                 setting upvar_id={:?} to by value",
290                                upvar_id);
291
292                         // to move out of an upvar, this must be a FnOnce closure
293                         self.adjust_closure_kind(upvar_id.closure_expr_id, ty::FnOnceClosureKind);
294
295                         let upvar_capture_map =
296                             &mut self.fcx.inh.tables.borrow_mut().upvar_capture_map;
297                         upvar_capture_map.insert(upvar_id, ty::UpvarCapture::ByValue);
298                     }
299                     mc::NoteClosureEnv(upvar_id) => {
300                         // we get just a closureenv ref if this is a
301                         // `move` closure, or if the upvar has already
302                         // been inferred to by-value. In any case, we
303                         // must still adjust the kind of the closure
304                         // to be a FnOnce closure to permit moves out
305                         // of the environment.
306                         self.adjust_closure_kind(upvar_id.closure_expr_id, ty::FnOnceClosureKind);
307                     }
308                     mc::NoteNone => {
309                     }
310                 }
311             }
312             _ => { }
313         }
314     }
315
316     /// Indicates that `cmt` is being directly mutated (e.g., assigned
317     /// to). If cmt contains any by-ref upvars, this implies that
318     /// those upvars must be borrowed using an `&mut` borrow.
319     fn adjust_upvar_borrow_kind_for_mut(&mut self, cmt: mc::cmt<'tcx>) {
320         debug!("adjust_upvar_borrow_kind_for_mut(cmt={:?})",
321                cmt);
322
323         match cmt.cat.clone() {
324             mc::cat_deref(base, _, mc::Unique) |
325             mc::cat_interior(base, _) |
326             mc::cat_downcast(base, _) => {
327                 // Interior or owned data is mutable if base is
328                 // mutable, so iterate to the base.
329                 self.adjust_upvar_borrow_kind_for_mut(base);
330             }
331
332             mc::cat_deref(base, _, mc::BorrowedPtr(..)) |
333             mc::cat_deref(base, _, mc::Implicit(..)) => {
334                 if !self.try_adjust_upvar_deref(&cmt.note, ty::MutBorrow) {
335                     // assignment to deref of an `&mut`
336                     // borrowed pointer implies that the
337                     // pointer itself must be unique, but not
338                     // necessarily *mutable*
339                     self.adjust_upvar_borrow_kind_for_unique(base);
340                 }
341             }
342
343             mc::cat_deref(_, _, mc::UnsafePtr(..)) |
344             mc::cat_static_item |
345             mc::cat_rvalue(_) |
346             mc::cat_local(_) |
347             mc::cat_upvar(..) => {
348                 return;
349             }
350         }
351     }
352
353     fn adjust_upvar_borrow_kind_for_unique(&self, cmt: mc::cmt<'tcx>) {
354         debug!("adjust_upvar_borrow_kind_for_unique(cmt={:?})",
355                cmt);
356
357         match cmt.cat.clone() {
358             mc::cat_deref(base, _, mc::Unique) |
359             mc::cat_interior(base, _) |
360             mc::cat_downcast(base, _) => {
361                 // Interior or owned data is unique if base is
362                 // unique.
363                 self.adjust_upvar_borrow_kind_for_unique(base);
364             }
365
366             mc::cat_deref(base, _, mc::BorrowedPtr(..)) |
367             mc::cat_deref(base, _, mc::Implicit(..)) => {
368                 if !self.try_adjust_upvar_deref(&cmt.note, ty::UniqueImmBorrow) {
369                     // for a borrowed pointer to be unique, its
370                     // base must be unique
371                     self.adjust_upvar_borrow_kind_for_unique(base);
372                 }
373             }
374
375             mc::cat_deref(_, _, mc::UnsafePtr(..)) |
376             mc::cat_static_item |
377             mc::cat_rvalue(_) |
378             mc::cat_local(_) |
379             mc::cat_upvar(..) => {
380             }
381         }
382     }
383
384     fn try_adjust_upvar_deref(&self,
385                               note: &mc::Note,
386                               borrow_kind: ty::BorrowKind)
387                               -> bool
388     {
389         assert!(match borrow_kind {
390             ty::MutBorrow => true,
391             ty::UniqueImmBorrow => true,
392
393             // imm borrows never require adjusting any kinds, so we don't wind up here
394             ty::ImmBorrow => false,
395         });
396
397         match *note {
398             mc::NoteUpvarRef(upvar_id) => {
399                 // if this is an implicit deref of an
400                 // upvar, then we need to modify the
401                 // borrow_kind of the upvar to make sure it
402                 // is inferred to mutable if necessary
403                 {
404                     let upvar_capture_map = &mut self.fcx.inh.tables.borrow_mut().upvar_capture_map;
405                     let ub = upvar_capture_map.get_mut(&upvar_id).unwrap();
406                     self.adjust_upvar_borrow_kind(upvar_id, ub, borrow_kind);
407                 }
408
409                 // also need to be in an FnMut closure since this is not an ImmBorrow
410                 self.adjust_closure_kind(upvar_id.closure_expr_id, ty::FnMutClosureKind);
411
412                 true
413             }
414             mc::NoteClosureEnv(upvar_id) => {
415                 // this kind of deref occurs in a `move` closure, or
416                 // for a by-value upvar; in either case, to mutate an
417                 // upvar, we need to be an FnMut closure
418                 self.adjust_closure_kind(upvar_id.closure_expr_id, ty::FnMutClosureKind);
419
420                 true
421             }
422             mc::NoteNone => {
423                 false
424             }
425         }
426     }
427
428     /// We infer the borrow_kind with which to borrow upvars in a stack closure. The borrow_kind
429     /// basically follows a lattice of `imm < unique-imm < mut`, moving from left to right as needed
430     /// (but never right to left). Here the argument `mutbl` is the borrow_kind that is required by
431     /// some particular use.
432     fn adjust_upvar_borrow_kind(&self,
433                                 upvar_id: ty::UpvarId,
434                                 upvar_capture: &mut ty::UpvarCapture,
435                                 kind: ty::BorrowKind) {
436         debug!("adjust_upvar_borrow_kind(upvar_id={:?}, upvar_capture={:?}, kind={:?})",
437                upvar_id, upvar_capture, kind);
438
439         match *upvar_capture {
440             ty::UpvarCapture::ByValue => {
441                 // Upvar is already by-value, the strongest criteria.
442             }
443             ty::UpvarCapture::ByRef(ref mut upvar_borrow) => {
444                 match (upvar_borrow.kind, kind) {
445                     // Take RHS:
446                     (ty::ImmBorrow, ty::UniqueImmBorrow) |
447                     (ty::ImmBorrow, ty::MutBorrow) |
448                     (ty::UniqueImmBorrow, ty::MutBorrow) => {
449                         upvar_borrow.kind = kind;
450                     }
451                     // Take LHS:
452                     (ty::ImmBorrow, ty::ImmBorrow) |
453                     (ty::UniqueImmBorrow, ty::ImmBorrow) |
454                     (ty::UniqueImmBorrow, ty::UniqueImmBorrow) |
455                     (ty::MutBorrow, _) => {
456                     }
457                 }
458             }
459         }
460     }
461
462     fn adjust_closure_kind(&self,
463                            closure_id: ast::NodeId,
464                            new_kind: ty::ClosureKind) {
465         debug!("adjust_closure_kind(closure_id={}, new_kind={:?})",
466                closure_id, new_kind);
467
468         if !self.closures_with_inferred_kinds.contains(&closure_id) {
469             return;
470         }
471
472         let closure_def_id = DefId::local(closure_id);
473         let closure_kinds = &mut self.fcx.inh.tables.borrow_mut().closure_kinds;
474         let existing_kind = *closure_kinds.get(&closure_def_id).unwrap();
475
476         debug!("adjust_closure_kind: closure_id={}, existing_kind={:?}, new_kind={:?}",
477                closure_id, existing_kind, new_kind);
478
479         match (existing_kind, new_kind) {
480             (ty::FnClosureKind, ty::FnClosureKind) |
481             (ty::FnMutClosureKind, ty::FnClosureKind) |
482             (ty::FnMutClosureKind, ty::FnMutClosureKind) |
483             (ty::FnOnceClosureKind, _) => {
484                 // no change needed
485             }
486
487             (ty::FnClosureKind, ty::FnMutClosureKind) |
488             (ty::FnClosureKind, ty::FnOnceClosureKind) |
489             (ty::FnMutClosureKind, ty::FnOnceClosureKind) => {
490                 // new kind is stronger than the old kind
491                 closure_kinds.insert(closure_def_id, new_kind);
492             }
493         }
494     }
495 }
496
497 impl<'a, 'tcx, 'v> Visitor<'v> for AdjustBorrowKind<'a, 'tcx> {
498     fn visit_fn(&mut self,
499                 fn_kind: visit::FnKind<'v>,
500                 decl: &'v hir::FnDecl,
501                 body: &'v hir::Block,
502                 span: Span,
503                 id: ast::NodeId)
504     {
505         visit::walk_fn(self, fn_kind, decl, body, span);
506         self.analyze_closure(id, span, decl, body);
507     }
508
509     // Skip all items; they aren't in the same context.
510     fn visit_item(&mut self, _: &'v hir::Item) { }
511 }
512
513 impl<'a,'tcx> euv::Delegate<'tcx> for AdjustBorrowKind<'a,'tcx> {
514     fn consume(&mut self,
515                _consume_id: ast::NodeId,
516                _consume_span: Span,
517                cmt: mc::cmt<'tcx>,
518                mode: euv::ConsumeMode)
519     {
520         debug!("consume(cmt={:?},mode={:?})", cmt, mode);
521         self.adjust_upvar_borrow_kind_for_consume(cmt, mode);
522     }
523
524     fn matched_pat(&mut self,
525                    _matched_pat: &hir::Pat,
526                    _cmt: mc::cmt<'tcx>,
527                    _mode: euv::MatchMode)
528     {}
529
530     fn consume_pat(&mut self,
531                    _consume_pat: &hir::Pat,
532                    cmt: mc::cmt<'tcx>,
533                    mode: euv::ConsumeMode)
534     {
535         debug!("consume_pat(cmt={:?},mode={:?})", cmt, mode);
536         self.adjust_upvar_borrow_kind_for_consume(cmt, mode);
537     }
538
539     fn borrow(&mut self,
540               borrow_id: ast::NodeId,
541               _borrow_span: Span,
542               cmt: mc::cmt<'tcx>,
543               _loan_region: ty::Region,
544               bk: ty::BorrowKind,
545               _loan_cause: euv::LoanCause)
546     {
547         debug!("borrow(borrow_id={}, cmt={:?}, bk={:?})",
548                borrow_id, cmt, bk);
549
550         match bk {
551             ty::ImmBorrow => { }
552             ty::UniqueImmBorrow => {
553                 self.adjust_upvar_borrow_kind_for_unique(cmt);
554             }
555             ty::MutBorrow => {
556                 self.adjust_upvar_borrow_kind_for_mut(cmt);
557             }
558         }
559     }
560
561     fn decl_without_init(&mut self,
562                          _id: ast::NodeId,
563                          _span: Span)
564     {}
565
566     fn mutate(&mut self,
567               _assignment_id: ast::NodeId,
568               _assignment_span: Span,
569               assignee_cmt: mc::cmt<'tcx>,
570               _mode: euv::MutateMode)
571     {
572         debug!("mutate(assignee_cmt={:?})",
573                assignee_cmt);
574
575         self.adjust_upvar_borrow_kind_for_mut(assignee_cmt);
576     }
577 }