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.
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.
13 The region check is a final pass that runs over the AST after we have
14 inferred the type constraints but before we have actually finalized
15 the types. Its purpose is to embed a variety of region constraints.
16 Inserting these constraints as a separate pass is good because (1) it
17 localizes the code that has to do with region inference and (2) often
18 we cannot know what constraints are needed until the basic types have
21 ### Interaction with the borrow checker
23 In general, the job of the borrowck module (which runs later) is to
24 check that all soundness criteria are met, given a particular set of
25 regions. The job of *this* module is to anticipate the needs of the
26 borrow checker and infer regions that will satisfy its requirements.
27 It is generally true that the inference doesn't need to be sound,
28 meaning that if there is a bug and we inferred bad regions, the borrow
29 checker should catch it. This is not entirely true though; for
30 example, the borrow checker doesn't check subtyping, and it doesn't
31 check that region pointers are always live when they are used. It
32 might be worthwhile to fix this so that borrowck serves as a kind of
33 verification step -- that would add confidence in the overall
34 correctness of the compiler, at the cost of duplicating some type
37 ### Inferring the duration of borrows, automatic and otherwise
39 Whenever we introduce a borrowed pointer, for example as the result of
40 a borrow expression `let x = &data`, the lifetime of the pointer `x`
41 is always specified as a region inference variable. `regionck` has the
42 job of adding constraints such that this inference variable is as
43 narrow as possible while still accommodating all uses (that is, every
44 dereference of the resulting pointer must be within the lifetime).
48 Generally speaking, `regionck` does NOT try to ensure that the data
49 `data` will outlive the pointer `x`. That is the job of borrowck. The
50 one exception is when "re-borrowing" the contents of another borrowed
51 pointer. For example, imagine you have a borrowed pointer `b` with
52 lifetime L1 and you have an expression `&*b`. The result of this
53 expression will be another borrowed pointer with lifetime L2 (which is
54 an inference variable). The borrow checker is going to enforce the
55 constraint that L2 < L1, because otherwise you are re-borrowing data
56 for a lifetime larger than the original loan. However, without the
57 routines in this module, the region inferencer would not know of this
58 dependency and thus it might infer the lifetime of L2 to be greater
59 than L1 (issue #3148).
61 There are a number of troublesome scenarios in the tests
62 `region-dependent-*.rs`, but here is one example:
65 struct Bar { foo: Foo }
66 fn get_i(x: &'a Bar) -> &'a int {
67 let foo = &x.foo; // Lifetime L1
71 Note that this comes up either with `&` expressions, `ref`
72 bindings, and `autorefs`, which are the three ways to introduce
75 The key point here is that when you are borrowing a value that
76 is "guaranteed" by a borrowed pointer, you must link the
77 lifetime of that borrowed pointer (L1, here) to the lifetime of
78 the borrow itself (L2). What do I mean by "guaranteed" by a
79 borrowed pointer? I mean any data that is reached by first
80 dereferencing a borrowed pointer and then either traversing
81 interior offsets or owned pointers. We say that the guarantor
82 of such data it the region of the borrowed pointer that was
83 traversed. This is essentially the same as the ownership
84 relation, except that a borrowed pointer never owns its
87 ### Inferring borrow kinds for upvars
89 Whenever there is a closure expression, we need to determine how each
90 upvar is used. We do this by initially assigning each upvar an
91 immutable "borrow kind" (see `ty::BorrowKind` for details) and then
92 "escalating" the kind as needed. The borrow kind proceeds according to
93 the following lattice:
95 ty::ImmBorrow -> ty::UniqueImmBorrow -> ty::MutBorrow
97 So, for example, if we see an assignment `x = 5` to an upvar `x`, we
98 will promote its borrow kind to mutable borrow. If we see an `&mut x`
99 we'll do the same. Naturally, this applies not just to the upvar, but
100 to everything owned by `x`, so the result is the same for something
101 like `x.f = 5` and so on (presuming `x` is not a borrowed pointer to a
102 struct). These adjustments are performed in
103 `adjust_upvar_borrow_kind()` (you can trace backwards through the code
106 The fact that we are inferring borrow kinds as we go results in a
107 semi-hacky interaction with mem-categorization. In particular,
108 mem-categorization will query the current borrow kind as it
109 categorizes, and we'll return the *current* value, but this may get
110 adjusted later. Therefore, in this module, we generally ignore the
111 borrow kind (and derived mutabilities) that are returned from
112 mem-categorization, since they may be inaccurate. (Another option
113 would be to use a unification scheme, where instead of returning a
114 concrete borrow kind like `ty::ImmBorrow`, we return a
115 `ty::InferBorrow(upvar_id)` or something like that, but this would
116 then mean that all later passes would have to check for these figments
117 and report an error, and it just seems like more mess in the end.)
122 use middle::mem_categorization as mc;
123 use middle::region::CodeExtent;
125 use middle::ty::{ReScope};
126 use middle::ty::{mod, Ty};
127 use middle::typeck::astconv::AstConv;
128 use middle::typeck::check::FnCtxt;
129 use middle::typeck::check::regionmanip;
130 use middle::typeck::check::vtable;
131 use middle::typeck::infer::resolve_and_force_all_but_regions;
132 use middle::typeck::infer::resolve_type;
133 use middle::typeck::infer;
134 use middle::typeck::MethodCall;
135 use middle::pat_util;
136 use util::nodemap::{DefIdMap, NodeMap, FnvHashMap};
137 use util::ppaux::{ty_to_string, Repr};
140 use syntax::codemap::Span;
142 use syntax::visit::Visitor;
144 use std::cell::{RefCell};
145 use std::collections::hash_map::{Vacant, Occupied};
147 ///////////////////////////////////////////////////////////////////////////
148 // PUBLIC ENTRY POINTS
150 pub fn regionck_expr(fcx: &FnCtxt, e: &ast::Expr) {
151 let mut rcx = Rcx::new(fcx, e.id);
152 if fcx.err_count_since_creation() == 0 {
153 // regionck assumes typeck succeeded
155 rcx.visit_region_obligations(e.id);
157 fcx.infcx().resolve_regions_and_report_errors();
160 pub fn regionck_item(fcx: &FnCtxt, item: &ast::Item) {
161 let mut rcx = Rcx::new(fcx, item.id);
162 rcx.visit_region_obligations(item.id);
163 fcx.infcx().resolve_regions_and_report_errors();
166 pub fn regionck_fn(fcx: &FnCtxt, id: ast::NodeId, blk: &ast::Block) {
167 let mut rcx = Rcx::new(fcx, blk.id);
168 if fcx.err_count_since_creation() == 0 {
169 // regionck assumes typeck succeeded
170 rcx.visit_fn_body(id, blk);
173 // Region checking a fn can introduce new trait obligations,
174 // particularly around closure bounds.
175 vtable::select_all_fcx_obligations_or_error(fcx);
177 fcx.infcx().resolve_regions_and_report_errors();
180 pub fn regionck_ensure_component_tys_wf<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
182 component_tys: &[Ty<'tcx>]) {
184 * Checks that the types in `component_tys` are well-formed.
185 * This will add constraints into the region graph.
186 * Does *not* run `resolve_regions_and_report_errors` and so forth.
189 let mut rcx = Rcx::new(fcx, 0);
190 for &component_ty in component_tys.iter() {
191 // Check that each type outlives the empty region. Since the
192 // empty region is a subregion of all others, this can't fail
193 // unless the type does not meet the well-formedness
195 type_must_outlive(&mut rcx, infer::RelateRegionParamBound(span),
196 component_ty, ty::ReEmpty);
200 ///////////////////////////////////////////////////////////////////////////
203 // If mem categorization results in an error, it's because the type
204 // check failed (or will fail, when the error is uncovered and
205 // reported during writeback). In this case, we just ignore this part
206 // of the code and don't try to add any more region constraints.
207 macro_rules! ignore_err(
216 // Stores parameters for a potential call to link_region()
217 // to perform if an upvar reference is marked unique/mutable after
218 // it has already been processed before.
219 struct MaybeLink<'tcx> {
221 borrow_region: ty::Region,
222 borrow_kind: ty::BorrowKind,
223 borrow_cmt: mc::cmt<'tcx>
226 // A map associating an upvar ID to a vector of the above
227 type MaybeLinkMap<'tcx> = RefCell<FnvHashMap<ty::UpvarId, Vec<MaybeLink<'tcx>>>>;
229 pub struct Rcx<'a, 'tcx: 'a> {
230 fcx: &'a FnCtxt<'a, 'tcx>,
232 region_param_pairs: Vec<(ty::Region, ty::ParamTy)>,
234 // id of innermost fn or loop
235 repeating_scope: ast::NodeId,
237 // Possible region links we will establish if an upvar
238 // turns out to be unique/mutable
239 maybe_links: MaybeLinkMap<'tcx>
242 fn region_of_def(fcx: &FnCtxt, def: def::Def) -> ty::Region {
244 * Returns the validity region of `def` -- that is, how long
250 def::DefLocal(node_id) => {
251 tcx.region_maps.var_region(node_id)
253 def::DefUpvar(node_id, _, body_id) => {
254 if body_id == ast::DUMMY_NODE_ID {
255 tcx.region_maps.var_region(node_id)
257 ReScope(CodeExtent::from_node_id(body_id))
261 tcx.sess.bug(format!("unexpected def in region_of_def: {}",
267 impl<'a, 'tcx> Rcx<'a, 'tcx> {
268 pub fn new(fcx: &'a FnCtxt<'a, 'tcx>,
269 initial_repeating_scope: ast::NodeId) -> Rcx<'a, 'tcx> {
271 repeating_scope: initial_repeating_scope,
272 region_param_pairs: Vec::new(),
273 maybe_links: RefCell::new(FnvHashMap::new()) }
276 pub fn tcx(&self) -> &'a ty::ctxt<'tcx> {
280 pub fn set_repeating_scope(&mut self, scope: ast::NodeId) -> ast::NodeId {
281 let old_scope = self.repeating_scope;
282 self.repeating_scope = scope;
286 pub fn resolve_type(&self, unresolved_ty: Ty<'tcx>) -> Ty<'tcx> {
288 * Try to resolve the type for the given node, returning
289 * t_err if an error results. Note that we never care
290 * about the details of the error, the same error will be
291 * detected and reported in the writeback phase.
293 * Note one important point: we do not attempt to resolve
294 * *region variables* here. This is because regionck is
295 * essentially adding constraints to those region variables
296 * and so may yet influence how they are resolved.
298 * Consider this silly example:
300 * fn borrow(x: &int) -> &int {x}
301 * fn foo(x: @int) -> int { // block: B
302 * let b = borrow(x); // region: <R0>
306 * Here, the region of `b` will be `<R0>`. `<R0>` is
307 * constrainted to be some subregion of the block B and some
308 * superregion of the call. If we forced it now, we'd choose
309 * the smaller region (the call). But that would make the *b
310 * illegal. Since we don't resolve, the type of b will be
311 * `&<R0>.int` and then `*b` will require that `<R0>` be
312 * bigger than the let and the `*b` expression, so we will
313 * effectively resolve `<R0>` to be the block B.
315 match resolve_type(self.fcx.infcx(), None, unresolved_ty,
316 resolve_and_force_all_but_regions) {
318 Err(_) => ty::mk_err()
322 /// Try to resolve the type for the given node.
323 fn resolve_node_type(&self, id: ast::NodeId) -> Ty<'tcx> {
324 let t = self.fcx.node_ty(id);
328 fn resolve_method_type(&self, method_call: MethodCall) -> Option<Ty<'tcx>> {
329 let method_ty = self.fcx.inh.method_map.borrow()
330 .get(&method_call).map(|method| method.ty);
331 method_ty.map(|method_ty| self.resolve_type(method_ty))
334 /// Try to resolve the type for the given node.
335 pub fn resolve_expr_type_adjusted(&mut self, expr: &ast::Expr) -> Ty<'tcx> {
336 let ty_unadjusted = self.resolve_node_type(expr.id);
337 if ty::type_is_error(ty_unadjusted) {
340 let tcx = self.fcx.tcx();
341 ty::adjust_ty(tcx, expr.span, expr.id, ty_unadjusted,
342 self.fcx.inh.adjustments.borrow().get(&expr.id),
343 |method_call| self.resolve_method_type(method_call))
347 fn visit_fn_body(&mut self,
351 // When we enter a function, we can derive
353 let fn_sig_map = self.fcx.inh.fn_sig_map.borrow();
354 let fn_sig = match fn_sig_map.get(&id) {
358 format!("No fn-sig entry for id={}", id).as_slice());
362 let len = self.region_param_pairs.len();
363 self.relate_free_regions(fn_sig.as_slice(), body.id);
364 self.visit_block(body);
365 self.visit_region_obligations(body.id);
366 self.region_param_pairs.truncate(len);
369 fn visit_region_obligations(&mut self, node_id: ast::NodeId)
371 debug!("visit_region_obligations: node_id={}", node_id);
372 let region_obligations = self.fcx.inh.region_obligations.borrow();
373 match region_obligations.get(&node_id) {
376 for r_o in vec.iter() {
377 debug!("visit_region_obligations: r_o={}",
378 r_o.repr(self.tcx()));
379 let sup_type = self.resolve_type(r_o.sup_type);
380 type_must_outlive(self, r_o.origin.clone(),
381 sup_type, r_o.sub_region);
387 fn relate_free_regions(&mut self,
388 fn_sig_tys: &[Ty<'tcx>],
389 body_id: ast::NodeId) {
391 * This method populates the region map's `free_region_map`.
392 * It walks over the transformed argument and return types for
393 * each function just before we check the body of that
394 * function, looking for types where you have a borrowed
395 * pointer to other borrowed data (e.g., `&'a &'b [uint]`. We
396 * do not allow references to outlive the things they point
397 * at, so we can assume that `'a <= 'b`. This holds for both
398 * the argument and return types, basically because, on the caller
399 * side, the caller is responsible for checking that the type of
400 * every expression (including the actual values for the arguments,
401 * as well as the return type of the fn call) is well-formed.
403 * Tests: `src/test/compile-fail/regions-free-region-ordering-*.rs`
406 debug!("relate_free_regions >>");
407 let tcx = self.tcx();
409 for &ty in fn_sig_tys.iter() {
410 let ty = self.resolve_type(ty);
411 debug!("relate_free_regions(t={})", ty.repr(tcx));
412 let body_scope = CodeExtent::from_node_id(body_id);
413 let body_scope = ty::ReScope(body_scope);
415 regionmanip::region_wf_constraints(
419 for constraint in constraints.iter() {
420 debug!("constraint: {}", constraint.repr(tcx));
422 regionmanip::RegionSubRegionConstraint(_,
424 ty::ReFree(free_b)) => {
425 tcx.region_maps.relate_free_regions(free_a, free_b);
427 regionmanip::RegionSubRegionConstraint(_,
429 ty::ReInfer(ty::ReVar(vid_b))) => {
430 self.fcx.inh.infcx.add_given(free_a, vid_b);
432 regionmanip::RegionSubRegionConstraint(..) => {
433 // In principle, we could record (and take
434 // advantage of) every relationship here, but
435 // we are also free not to -- it simply means
436 // strictly less that we can successfully type
437 // check. (It may also be that we should
438 // revise our inference system to be more
439 // general and to make use of *every*
440 // relationship that arises here, but
441 // presently we do not.)
443 regionmanip::RegionSubParamConstraint(_, r_a, p_b) => {
444 debug!("RegionSubParamConstraint: {} <= {}",
445 r_a.repr(tcx), p_b.repr(tcx));
447 self.region_param_pairs.push((r_a, p_b));
453 debug!("<< relate_free_regions");
457 impl<'fcx, 'tcx> mc::Typer<'tcx> for Rcx<'fcx, 'tcx> {
458 fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
462 fn node_ty(&self, id: ast::NodeId) -> mc::McResult<Ty<'tcx>> {
463 let t = self.resolve_node_type(id);
464 if ty::type_is_error(t) {Err(())} else {Ok(t)}
467 fn node_method_ty(&self, method_call: MethodCall) -> Option<Ty<'tcx>> {
468 self.resolve_method_type(method_call)
471 fn adjustments<'a>(&'a self) -> &'a RefCell<NodeMap<ty::AutoAdjustment<'tcx>>> {
472 &self.fcx.inh.adjustments
475 fn is_method_call(&self, id: ast::NodeId) -> bool {
476 self.fcx.inh.method_map.borrow().contains_key(&MethodCall::expr(id))
479 fn temporary_scope(&self, id: ast::NodeId) -> Option<CodeExtent> {
480 self.tcx().region_maps.temporary_scope(id)
483 fn upvar_borrow(&self, id: ty::UpvarId) -> ty::UpvarBorrow {
484 self.fcx.inh.upvar_borrow_map.borrow()[id].clone()
487 fn capture_mode(&self, closure_expr_id: ast::NodeId)
488 -> ast::CaptureClause {
489 self.tcx().capture_modes.borrow()[closure_expr_id].clone()
492 fn unboxed_closures<'a>(&'a self)
493 -> &'a RefCell<DefIdMap<ty::UnboxedClosure<'tcx>>> {
494 &self.fcx.inh.unboxed_closures
498 impl<'a, 'tcx, 'v> Visitor<'v> for Rcx<'a, 'tcx> {
499 // (..) FIXME(#3238) should use visit_pat, not visit_arm/visit_local,
500 // However, right now we run into an issue whereby some free
501 // regions are not properly related if they appear within the
502 // types of arguments that must be inferred. This could be
503 // addressed by deferring the construction of the region
504 // hierarchy, and in particular the relationships between free
505 // regions, until regionck, as described in #3238.
507 fn visit_fn(&mut self, _fk: visit::FnKind<'v>, _fd: &'v ast::FnDecl,
508 b: &'v ast::Block, _s: Span, id: ast::NodeId) {
509 self.visit_fn_body(id, b)
512 fn visit_item(&mut self, i: &ast::Item) { visit_item(self, i); }
514 fn visit_expr(&mut self, ex: &ast::Expr) { visit_expr(self, ex); }
516 //visit_pat: visit_pat, // (..) see above
518 fn visit_arm(&mut self, a: &ast::Arm) { visit_arm(self, a); }
520 fn visit_local(&mut self, l: &ast::Local) { visit_local(self, l); }
522 fn visit_block(&mut self, b: &ast::Block) { visit_block(self, b); }
525 fn visit_item(_rcx: &mut Rcx, _item: &ast::Item) {
529 fn visit_block(rcx: &mut Rcx, b: &ast::Block) {
530 visit::walk_block(rcx, b);
533 fn visit_arm(rcx: &mut Rcx, arm: &ast::Arm) {
535 for p in arm.pats.iter() {
536 constrain_bindings_in_pat(&**p, rcx);
539 visit::walk_arm(rcx, arm);
542 fn visit_local(rcx: &mut Rcx, l: &ast::Local) {
544 constrain_bindings_in_pat(&*l.pat, rcx);
546 visit::walk_local(rcx, l);
549 fn constrain_bindings_in_pat(pat: &ast::Pat, rcx: &mut Rcx) {
550 let tcx = rcx.fcx.tcx();
551 debug!("regionck::visit_pat(pat={})", pat.repr(tcx));
552 pat_util::pat_bindings(&tcx.def_map, pat, |_, id, span, _| {
553 // If we have a variable that contains region'd data, that
554 // data will be accessible from anywhere that the variable is
555 // accessed. We must be wary of loops like this:
557 // // from src/test/compile-fail/borrowck-lend-flow.rs
558 // let mut v = box 3, w = box 4;
559 // let mut x = &mut w;
562 // borrow(v); //~ ERROR cannot borrow
563 // x = &mut v; // (1)
566 // Typically, we try to determine the region of a borrow from
567 // those points where it is dereferenced. In this case, one
568 // might imagine that the lifetime of `x` need only be the
569 // body of the loop. But of course this is incorrect because
570 // the pointer that is created at point (1) is consumed at
571 // point (2), meaning that it must be live across the loop
572 // iteration. The easiest way to guarantee this is to require
573 // that the lifetime of any regions that appear in a
574 // variable's type enclose at least the variable's scope.
576 let var_region = tcx.region_maps.var_region(id);
577 type_of_node_must_outlive(
578 rcx, infer::BindingTypeIsNotValidAtDecl(span),
583 fn visit_expr(rcx: &mut Rcx, expr: &ast::Expr) {
584 debug!("regionck::visit_expr(e={}, repeating_scope={})",
585 expr.repr(rcx.fcx.tcx()), rcx.repeating_scope);
587 // No matter what, the type of each expression must outlive the
588 // scope of that expression. This also guarantees basic WF.
589 let expr_ty = rcx.resolve_node_type(expr.id);
591 type_must_outlive(rcx, infer::ExprTypeIsNotInScope(expr_ty, expr.span),
592 expr_ty, ty::ReScope(CodeExtent::from_node_id(expr.id)));
594 let method_call = MethodCall::expr(expr.id);
595 let has_method_map = rcx.fcx.inh.method_map.borrow().contains_key(&method_call);
597 // Check any autoderefs or autorefs that appear.
598 for &adjustment in rcx.fcx.inh.adjustments.borrow().get(&expr.id).iter() {
599 debug!("adjustment={}", adjustment);
601 ty::AdjustDerefRef(ty::AutoDerefRef {autoderefs, autoref: ref opt_autoref}) => {
602 let expr_ty = rcx.resolve_node_type(expr.id);
603 constrain_autoderefs(rcx, expr, autoderefs, expr_ty);
604 for autoref in opt_autoref.iter() {
605 link_autoref(rcx, expr, autoderefs, autoref);
607 // Require that the resulting region encompasses
610 // FIXME(#6268) remove to support nested method calls
611 type_of_node_must_outlive(
612 rcx, infer::AutoBorrow(expr.span),
613 expr.id, ty::ReScope(CodeExtent::from_node_id(expr.id)));
617 ty::AutoObject(_, ref bounds, _, _) => {
618 // Determine if we are casting `expr` to a trait
619 // instance. If so, we have to be sure that the type
620 // of the source obeys the new region bound.
621 let source_ty = rcx.resolve_node_type(expr.id);
622 type_must_outlive(rcx, infer::RelateObjectBound(expr.span),
623 source_ty, bounds.region_bound);
631 ast::ExprCall(ref callee, ref args) => {
633 constrain_call(rcx, expr, Some(&**callee),
634 args.iter().map(|e| &**e), false);
636 constrain_callee(rcx, callee.id, expr, &**callee);
637 constrain_call(rcx, expr, None,
638 args.iter().map(|e| &**e), false);
641 visit::walk_expr(rcx, expr);
644 ast::ExprMethodCall(_, _, ref args) => {
645 constrain_call(rcx, expr, Some(&*args[0]),
646 args.slice_from(1).iter().map(|e| &**e), false);
648 visit::walk_expr(rcx, expr);
651 ast::ExprAssign(ref lhs, _) => {
652 adjust_borrow_kind_for_assignment_lhs(rcx, &**lhs);
653 visit::walk_expr(rcx, expr);
656 ast::ExprAssignOp(_, ref lhs, ref rhs) => {
658 constrain_call(rcx, expr, Some(&**lhs),
659 Some(&**rhs).into_iter(), true);
662 adjust_borrow_kind_for_assignment_lhs(rcx, &**lhs);
664 visit::walk_expr(rcx, expr);
667 ast::ExprIndex(ref lhs, ref rhs) |
668 ast::ExprBinary(_, ref lhs, ref rhs) if has_method_map => {
669 // As `expr_method_call`, but the call is via an
670 // overloaded op. Note that we (sadly) currently use an
671 // implicit "by ref" sort of passing style here. This
672 // should be converted to an adjustment!
673 constrain_call(rcx, expr, Some(&**lhs),
674 Some(&**rhs).into_iter(), true);
676 visit::walk_expr(rcx, expr);
679 ast::ExprUnary(_, ref lhs) if has_method_map => {
681 constrain_call(rcx, expr, Some(&**lhs),
682 None::<ast::Expr>.iter(), true);
684 visit::walk_expr(rcx, expr);
687 ast::ExprUnary(ast::UnDeref, ref base) => {
688 // For *a, the lifetime of a must enclose the deref
689 let method_call = MethodCall::expr(expr.id);
690 let base_ty = match rcx.fcx.inh.method_map.borrow().get(&method_call) {
692 constrain_call(rcx, expr, Some(&**base),
693 None::<ast::Expr>.iter(), true);
694 ty::ty_fn_ret(method.ty).unwrap()
696 None => rcx.resolve_node_type(base.id)
699 ty::ty_rptr(r_ptr, _) => {
700 mk_subregion_due_to_dereference(
701 rcx, expr.span, ty::ReScope(CodeExtent::from_node_id(expr.id)), r_ptr);
706 visit::walk_expr(rcx, expr);
709 ast::ExprIndex(ref vec_expr, _) => {
710 // For a[b], the lifetime of a must enclose the deref
711 let vec_type = rcx.resolve_expr_type_adjusted(&**vec_expr);
712 constrain_index(rcx, expr, vec_type);
714 visit::walk_expr(rcx, expr);
717 ast::ExprCast(ref source, _) => {
718 // Determine if we are casting `source` to a trait
719 // instance. If so, we have to be sure that the type of
720 // the source obeys the trait's region bound.
721 constrain_cast(rcx, expr, &**source);
722 visit::walk_expr(rcx, expr);
725 ast::ExprAddrOf(m, ref base) => {
726 link_addr_of(rcx, expr, m, &**base);
728 // Require that when you write a `&expr` expression, the
729 // resulting pointer has a lifetime that encompasses the
730 // `&expr` expression itself. Note that we constraining
731 // the type of the node expr.id here *before applying
734 // FIXME(#6268) nested method calls requires that this rule change
735 let ty0 = rcx.resolve_node_type(expr.id);
736 type_must_outlive(rcx, infer::AddrOf(expr.span),
737 ty0, ty::ReScope(CodeExtent::from_node_id(expr.id)));
738 visit::walk_expr(rcx, expr);
741 ast::ExprMatch(ref discr, ref arms, _) => {
742 link_match(rcx, &**discr, arms.as_slice());
744 visit::walk_expr(rcx, expr);
747 ast::ExprProc(_, ref body) |
748 ast::ExprClosure(_, _, _, ref body) => {
749 check_expr_fn_block(rcx, expr, &**body);
752 ast::ExprLoop(ref body, _) => {
753 let repeating_scope = rcx.set_repeating_scope(body.id);
754 visit::walk_expr(rcx, expr);
755 rcx.set_repeating_scope(repeating_scope);
758 ast::ExprWhile(ref cond, ref body, _) => {
759 let repeating_scope = rcx.set_repeating_scope(cond.id);
760 rcx.visit_expr(&**cond);
762 rcx.set_repeating_scope(body.id);
763 rcx.visit_block(&**body);
765 rcx.set_repeating_scope(repeating_scope);
768 ast::ExprForLoop(ref pat, ref head, ref body, _) => {
769 constrain_bindings_in_pat(&**pat, rcx);
772 let mc = mc::MemCategorizationContext::new(rcx);
773 let pat_ty = rcx.resolve_node_type(pat.id);
774 let pat_cmt = mc.cat_rvalue(pat.id,
776 ty::ReScope(CodeExtent::from_node_id(body.id)),
778 link_pattern(rcx, mc, pat_cmt, &**pat);
781 rcx.visit_expr(&**head);
782 type_of_node_must_outlive(rcx,
783 infer::AddrOf(expr.span),
785 ty::ReScope(CodeExtent::from_node_id(expr.id)));
787 let repeating_scope = rcx.set_repeating_scope(body.id);
788 rcx.visit_block(&**body);
789 rcx.set_repeating_scope(repeating_scope);
793 visit::walk_expr(rcx, expr);
798 fn constrain_cast(rcx: &mut Rcx,
799 cast_expr: &ast::Expr,
800 source_expr: &ast::Expr)
802 debug!("constrain_cast(cast_expr={}, source_expr={})",
803 cast_expr.repr(rcx.tcx()),
804 source_expr.repr(rcx.tcx()));
806 let source_ty = rcx.resolve_node_type(source_expr.id);
807 let target_ty = rcx.resolve_node_type(cast_expr.id);
809 walk_cast(rcx, cast_expr, source_ty, target_ty);
811 fn walk_cast<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>,
812 cast_expr: &ast::Expr,
815 debug!("walk_cast(from_ty={}, to_ty={})",
816 from_ty.repr(rcx.tcx()),
817 to_ty.repr(rcx.tcx()));
818 match (&from_ty.sty, &to_ty.sty) {
819 /*From:*/ (&ty::ty_rptr(from_r, ref from_mt),
820 /*To: */ &ty::ty_rptr(to_r, ref to_mt)) => {
821 // Target cannot outlive source, naturally.
822 rcx.fcx.mk_subr(infer::Reborrow(cast_expr.span), to_r, from_r);
823 walk_cast(rcx, cast_expr, from_mt.ty, to_mt.ty);
827 /*To: */ &ty::ty_trait(box ty::TyTrait { bounds, .. })) => {
828 // When T is existentially quantified as a trait
829 // `Foo+'to`, it must outlive the region bound `'to`.
830 type_must_outlive(rcx, infer::RelateObjectBound(cast_expr.span),
831 from_ty, bounds.region_bound);
834 /*From:*/ (&ty::ty_uniq(from_referent_ty),
835 /*To: */ &ty::ty_uniq(to_referent_ty)) => {
836 walk_cast(rcx, cast_expr, from_referent_ty, to_referent_ty);
844 fn check_expr_fn_block(rcx: &mut Rcx,
847 let tcx = rcx.fcx.tcx();
848 let function_type = rcx.resolve_node_type(expr.id);
850 match function_type.sty {
851 ty::ty_closure(box ty::ClosureTy{store: ty::RegionTraitStore(..),
854 // For closure, ensure that the variables outlive region
855 // bound, since they are captured by reference.
856 ty::with_freevars(tcx, expr.id, |freevars| {
857 if freevars.is_empty() {
858 // No free variables means that the environment
859 // will be NULL at runtime and hence the closure
860 // has static lifetime.
862 // Variables being referenced must outlive closure.
863 constrain_free_variables_in_by_ref_closure(
864 rcx, bounds.region_bound, expr, freevars);
866 // Closure is stack allocated and hence cannot
867 // outlive the appropriate temporary scope.
868 let s = rcx.repeating_scope;
869 rcx.fcx.mk_subr(infer::InfStackClosure(expr.span),
870 bounds.region_bound, ty::ReScope(CodeExtent::from_node_id(s)));
874 ty::ty_unboxed_closure(_, region, _) => {
875 if tcx.capture_modes.borrow()[expr.id].clone() == ast::CaptureByRef {
876 ty::with_freevars(tcx, expr.id, |freevars| {
877 if !freevars.is_empty() {
878 // Variables being referenced must be constrained and registered
879 // in the upvar borrow map
880 constrain_free_variables_in_by_ref_closure(
881 rcx, region, expr, freevars);
889 let repeating_scope = rcx.set_repeating_scope(body.id);
890 visit::walk_expr(rcx, expr);
891 rcx.set_repeating_scope(repeating_scope);
893 match function_type.sty {
894 ty::ty_closure(box ty::ClosureTy { store: ty::RegionTraitStore(..), .. }) => {
895 ty::with_freevars(tcx, expr.id, |freevars| {
896 propagate_upupvar_borrow_kind(rcx, expr, freevars);
899 ty::ty_unboxed_closure(..) => {
900 if tcx.capture_modes.borrow()[expr.id].clone() == ast::CaptureByRef {
901 ty::with_freevars(tcx, expr.id, |freevars| {
902 propagate_upupvar_borrow_kind(rcx, expr, freevars);
909 match function_type.sty {
910 ty::ty_closure(box ty::ClosureTy {bounds, ..}) => {
911 ty::with_freevars(tcx, expr.id, |freevars| {
912 ensure_free_variable_types_outlive_closure_bound(rcx, bounds, expr, freevars);
915 ty::ty_unboxed_closure(_, region, _) => {
916 ty::with_freevars(tcx, expr.id, |freevars| {
917 let bounds = ty::region_existential_bound(region);
918 ensure_free_variable_types_outlive_closure_bound(rcx, bounds, expr, freevars);
924 fn ensure_free_variable_types_outlive_closure_bound(
926 bounds: ty::ExistentialBounds,
928 freevars: &[ty::Freevar])
931 * Make sure that the type of all free variables referenced
932 * inside a closure/proc outlive the closure/proc's lifetime
933 * bound. This is just a special case of the usual rules about
934 * closed over values outliving the object's lifetime bound.
937 let tcx = rcx.fcx.ccx.tcx;
939 debug!("ensure_free_variable_types_outlive_closure_bound({}, {})",
940 bounds.region_bound.repr(tcx), expr.repr(tcx));
942 for freevar in freevars.iter() {
944 let def_id = freevar.def.def_id();
945 assert!(def_id.krate == ast::LOCAL_CRATE);
949 // Compute the type of the field in the environment that
950 // represents `var_node_id`. For a by-value closure, this
951 // will be the same as the type of the variable. For a
952 // by-reference closure, this will be `&T` where `T` is
953 // the type of the variable.
954 let raw_var_ty = rcx.resolve_node_type(var_node_id);
955 let upvar_id = ty::UpvarId { var_id: var_node_id,
956 closure_expr_id: expr.id };
957 let var_ty = match rcx.fcx.inh.upvar_borrow_map.borrow().get(&upvar_id) {
958 Some(upvar_borrow) => {
959 ty::mk_rptr(rcx.tcx(),
961 ty::mt { mutbl: upvar_borrow.kind.to_mutbl_lossy(),
967 // Check that the type meets the criteria of the existential bounds:
968 for builtin_bound in bounds.builtin_bounds.iter() {
969 let code = traits::ClosureCapture(var_node_id, expr.span);
970 let cause = traits::ObligationCause::new(freevar.span, code);
971 let obligation = traits::obligation_for_builtin_bound(rcx.tcx(), cause,
972 var_ty, builtin_bound);
975 rcx.fcx.inh.fulfillment_cx.borrow_mut().register_obligation(rcx.tcx(),
982 rcx, infer::RelateProcBound(expr.span, var_node_id, var_ty),
983 var_ty, bounds.region_bound);
987 fn constrain_free_variables_in_by_ref_closure(
989 region_bound: ty::Region,
991 freevars: &[ty::Freevar])
994 * Make sure that all free variables referenced inside the
995 * closure outlive the closure's lifetime bound. Also, create
996 * an entry in the upvar_borrows map with a region.
999 let tcx = rcx.fcx.ccx.tcx;
1000 let infcx = rcx.fcx.infcx();
1001 debug!("constrain_free_variables({}, {})",
1002 region_bound.repr(tcx), expr.repr(tcx));
1003 for freevar in freevars.iter() {
1004 debug!("freevar def is {}", freevar.def);
1006 // Identify the variable being closed over and its node-id.
1007 let def = freevar.def;
1009 let def_id = def.def_id();
1010 assert!(def_id.krate == ast::LOCAL_CRATE);
1013 let upvar_id = ty::UpvarId { var_id: var_node_id,
1014 closure_expr_id: expr.id };
1016 // Create a region variable to represent this borrow. This borrow
1017 // must outlive the region on the closure.
1018 let origin = infer::UpvarRegion(upvar_id, expr.span);
1019 let freevar_region = infcx.next_region_var(origin);
1020 rcx.fcx.mk_subr(infer::FreeVariable(freevar.span, var_node_id),
1021 region_bound, freevar_region);
1023 // Create a UpvarBorrow entry. Note that we begin with a
1024 // const borrow_kind, but change it to either mut or
1025 // immutable as dictated by the uses.
1026 let upvar_borrow = ty::UpvarBorrow { kind: ty::ImmBorrow,
1027 region: freevar_region };
1028 rcx.fcx.inh.upvar_borrow_map.borrow_mut().insert(upvar_id,
1031 // Guarantee that the closure does not outlive the variable itself.
1032 let enclosing_region = region_of_def(rcx.fcx, def);
1033 debug!("enclosing_region = {}", enclosing_region.repr(tcx));
1034 rcx.fcx.mk_subr(infer::FreeVariable(freevar.span, var_node_id),
1035 region_bound, enclosing_region);
1039 fn propagate_upupvar_borrow_kind(rcx: &mut Rcx,
1041 freevars: &[ty::Freevar]) {
1042 let tcx = rcx.fcx.ccx.tcx;
1043 debug!("propagate_upupvar_borrow_kind({})", expr.repr(tcx));
1044 for freevar in freevars.iter() {
1045 // Because of the semi-hokey way that we are doing
1046 // borrow_kind inference, we need to check for
1047 // indirect dependencies, like so:
1056 // Here, the `inner_call` is basically "reborrowing" the
1057 // outer pointer. With no other changes, `inner_call`
1058 // would infer that it requires a mutable borrow, but
1059 // `outer_call` would infer that a const borrow is
1060 // sufficient. This is because we haven't linked the
1061 // borrow_kind of the borrow that occurs in the inner
1062 // closure to the borrow_kind of the borrow in the outer
1063 // closure. Note that regions *are* naturally linked
1064 // because we have a proper inference scheme there.
1066 // Anyway, for borrow_kind, we basically go back over now
1067 // after checking the inner closure (and hence
1068 // determining the final borrow_kind) and propagate that as
1069 // a constraint on the outer closure.
1071 def::DefUpvar(var_id, outer_closure_id, _) => {
1072 // thing being captured is itself an upvar:
1073 let outer_upvar_id = ty::UpvarId {
1075 closure_expr_id: outer_closure_id };
1076 let inner_upvar_id = ty::UpvarId {
1078 closure_expr_id: expr.id };
1079 link_upvar_borrow_kind_for_nested_closures(rcx,
1089 fn constrain_callee(rcx: &mut Rcx,
1090 callee_id: ast::NodeId,
1091 call_expr: &ast::Expr,
1092 callee_expr: &ast::Expr) {
1093 let call_region = ty::ReScope(CodeExtent::from_node_id(call_expr.id));
1095 let callee_ty = rcx.resolve_node_type(callee_id);
1096 match callee_ty.sty {
1097 ty::ty_bare_fn(..) => { }
1098 ty::ty_closure(ref closure_ty) => {
1099 let region = match closure_ty.store {
1100 ty::RegionTraitStore(r, _) => {
1101 // While we're here, link the closure's region with a unique
1102 // immutable borrow (gathered later in borrowck)
1103 let mc = mc::MemCategorizationContext::new(rcx);
1104 let expr_cmt = ignore_err!(mc.cat_expr(callee_expr));
1105 link_region(rcx, callee_expr.span, call_region,
1106 ty::UniqueImmBorrow, expr_cmt);
1109 ty::UniqTraitStore => ty::ReStatic
1111 rcx.fcx.mk_subr(infer::InvokeClosure(callee_expr.span),
1112 call_region, region);
1114 let region = closure_ty.bounds.region_bound;
1115 rcx.fcx.mk_subr(infer::InvokeClosure(callee_expr.span),
1116 call_region, region);
1119 // this should not happen, but it does if the program is
1122 // tcx.sess.span_bug(
1123 // callee_expr.span,
1124 // format!("Calling non-function: {}", callee_ty.repr(tcx)));
1129 fn constrain_call<'a, I: Iterator<&'a ast::Expr>>(rcx: &mut Rcx,
1130 call_expr: &ast::Expr,
1131 receiver: Option<&ast::Expr>,
1133 implicitly_ref_args: bool) {
1134 //! Invoked on every call site (i.e., normal calls, method calls,
1135 //! and overloaded operators). Constrains the regions which appear
1136 //! in the type of the function. Also constrains the regions that
1137 //! appear in the arguments appropriately.
1139 let tcx = rcx.fcx.tcx();
1140 debug!("constrain_call(call_expr={}, \
1142 implicitly_ref_args={})",
1143 call_expr.repr(tcx),
1145 implicitly_ref_args);
1147 // `callee_region` is the scope representing the time in which the
1150 // FIXME(#6268) to support nested method calls, should be callee_id
1151 let callee_scope = CodeExtent::from_node_id(call_expr.id);
1152 let callee_region = ty::ReScope(callee_scope);
1154 debug!("callee_region={}", callee_region.repr(tcx));
1156 for arg_expr in arg_exprs {
1157 debug!("Argument: {}", arg_expr.repr(tcx));
1159 // ensure that any regions appearing in the argument type are
1160 // valid for at least the lifetime of the function:
1161 type_of_node_must_outlive(
1162 rcx, infer::CallArg(arg_expr.span),
1163 arg_expr.id, callee_region);
1165 // unfortunately, there are two means of taking implicit
1166 // references, and we need to propagate constraints as a
1167 // result. modes are going away and the "DerefArgs" code
1168 // should be ported to use adjustments
1169 if implicitly_ref_args {
1170 link_by_ref(rcx, arg_expr, callee_scope);
1174 // as loop above, but for receiver
1175 for r in receiver.iter() {
1176 debug!("receiver: {}", r.repr(tcx));
1177 type_of_node_must_outlive(
1178 rcx, infer::CallRcvr(r.span),
1179 r.id, callee_region);
1180 if implicitly_ref_args {
1181 link_by_ref(rcx, &**r, callee_scope);
1186 fn constrain_autoderefs<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>,
1187 deref_expr: &ast::Expr,
1189 mut derefd_ty: Ty<'tcx>) {
1191 * Invoked on any auto-dereference that occurs. Checks that if
1192 * this is a region pointer being dereferenced, the lifetime of
1193 * the pointer includes the deref expr.
1195 let r_deref_expr = ty::ReScope(CodeExtent::from_node_id(deref_expr.id));
1196 for i in range(0u, derefs) {
1197 debug!("constrain_autoderefs(deref_expr=?, derefd_ty={}, derefs={}/{}",
1198 rcx.fcx.infcx().ty_to_string(derefd_ty),
1201 let method_call = MethodCall::autoderef(deref_expr.id, i);
1202 derefd_ty = match rcx.fcx.inh.method_map.borrow().get(&method_call) {
1204 // Treat overloaded autoderefs as if an AutoRef adjustment
1205 // was applied on the base type, as that is always the case.
1206 let fn_sig = ty::ty_fn_sig(method.ty);
1207 let self_ty = fn_sig.inputs[0];
1208 let (m, r) = match self_ty.sty {
1209 ty::ty_rptr(r, ref m) => (m.mutbl, r),
1210 _ => rcx.tcx().sess.span_bug(deref_expr.span,
1211 format!("bad overloaded deref type {}",
1212 method.ty.repr(rcx.tcx())).as_slice())
1215 let mc = mc::MemCategorizationContext::new(rcx);
1216 let self_cmt = ignore_err!(mc.cat_expr_autoderefd(deref_expr, i));
1217 link_region(rcx, deref_expr.span, r,
1218 ty::BorrowKind::from_mutbl(m), self_cmt);
1221 // Specialized version of constrain_call.
1222 type_must_outlive(rcx, infer::CallRcvr(deref_expr.span),
1223 self_ty, r_deref_expr);
1224 match fn_sig.output {
1225 ty::FnConverging(return_type) => {
1226 type_must_outlive(rcx, infer::CallReturn(deref_expr.span),
1227 return_type, r_deref_expr);
1230 ty::FnDiverging => unreachable!()
1236 match derefd_ty.sty {
1237 ty::ty_rptr(r_ptr, _) => {
1238 mk_subregion_due_to_dereference(rcx, deref_expr.span,
1239 r_deref_expr, r_ptr);
1244 match ty::deref(derefd_ty, true) {
1245 Some(mt) => derefd_ty = mt.ty,
1246 /* if this type can't be dereferenced, then there's already an error
1247 in the session saying so. Just bail out for now */
1253 pub fn mk_subregion_due_to_dereference(rcx: &mut Rcx,
1255 minimum_lifetime: ty::Region,
1256 maximum_lifetime: ty::Region) {
1257 rcx.fcx.mk_subr(infer::DerefPointer(deref_span),
1258 minimum_lifetime, maximum_lifetime)
1262 fn constrain_index<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>,
1263 index_expr: &ast::Expr,
1264 indexed_ty: Ty<'tcx>)
1267 * Invoked on any index expression that occurs. Checks that if
1268 * this is a slice being indexed, the lifetime of the pointer
1269 * includes the deref expr.
1272 debug!("constrain_index(index_expr=?, indexed_ty={}",
1273 rcx.fcx.infcx().ty_to_string(indexed_ty));
1275 let r_index_expr = ty::ReScope(CodeExtent::from_node_id(index_expr.id));
1276 match indexed_ty.sty {
1277 ty::ty_rptr(r_ptr, mt) => match mt.ty.sty {
1278 ty::ty_vec(_, None) | ty::ty_str => {
1279 rcx.fcx.mk_subr(infer::IndexSlice(index_expr.span),
1280 r_index_expr, r_ptr);
1289 fn type_of_node_must_outlive<'a, 'tcx>(
1290 rcx: &mut Rcx<'a, 'tcx>,
1291 origin: infer::SubregionOrigin<'tcx>,
1293 minimum_lifetime: ty::Region)
1296 * Guarantees that any lifetimes which appear in the type of
1297 * the node `id` (after applying adjustments) are valid for at
1298 * least `minimum_lifetime`
1301 let tcx = rcx.fcx.tcx();
1303 // Try to resolve the type. If we encounter an error, then typeck
1304 // is going to fail anyway, so just stop here and let typeck
1305 // report errors later on in the writeback phase.
1306 let ty0 = rcx.resolve_node_type(id);
1307 let ty = ty::adjust_ty(tcx, origin.span(), id, ty0,
1308 rcx.fcx.inh.adjustments.borrow().get(&id),
1309 |method_call| rcx.resolve_method_type(method_call));
1310 debug!("constrain_regions_in_type_of_node(\
1311 ty={}, ty0={}, id={}, minimum_lifetime={})",
1312 ty_to_string(tcx, ty), ty_to_string(tcx, ty0),
1313 id, minimum_lifetime);
1314 type_must_outlive(rcx, origin, ty, minimum_lifetime);
1317 fn link_addr_of(rcx: &mut Rcx, expr: &ast::Expr,
1318 mutability: ast::Mutability, base: &ast::Expr) {
1320 * Computes the guarantor for an expression `&base` and then
1321 * ensures that the lifetime of the resulting pointer is linked
1322 * to the lifetime of its guarantor (if any).
1325 debug!("link_addr_of(base=?)");
1328 let mc = mc::MemCategorizationContext::new(rcx);
1329 ignore_err!(mc.cat_expr(base))
1331 link_region_from_node_type(rcx, expr.span, expr.id, mutability, cmt);
1334 fn link_local(rcx: &Rcx, local: &ast::Local) {
1336 * Computes the guarantors for any ref bindings in a `let` and
1337 * then ensures that the lifetime of the resulting pointer is
1338 * linked to the lifetime of the initialization expression.
1341 debug!("regionck::for_local()");
1342 let init_expr = match local.init {
1344 Some(ref expr) => &**expr,
1346 let mc = mc::MemCategorizationContext::new(rcx);
1347 let discr_cmt = ignore_err!(mc.cat_expr(init_expr));
1348 link_pattern(rcx, mc, discr_cmt, &*local.pat);
1351 fn link_match(rcx: &Rcx, discr: &ast::Expr, arms: &[ast::Arm]) {
1353 * Computes the guarantors for any ref bindings in a match and
1354 * then ensures that the lifetime of the resulting pointer is
1355 * linked to the lifetime of its guarantor (if any).
1358 debug!("regionck::for_match()");
1359 let mc = mc::MemCategorizationContext::new(rcx);
1360 let discr_cmt = ignore_err!(mc.cat_expr(discr));
1361 debug!("discr_cmt={}", discr_cmt.repr(rcx.tcx()));
1362 for arm in arms.iter() {
1363 for root_pat in arm.pats.iter() {
1364 link_pattern(rcx, mc, discr_cmt.clone(), &**root_pat);
1369 fn link_pattern<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>,
1370 mc: mc::MemCategorizationContext<Rcx<'a, 'tcx>>,
1371 discr_cmt: mc::cmt<'tcx>,
1372 root_pat: &ast::Pat) {
1374 * Link lifetimes of any ref bindings in `root_pat` to
1375 * the pointers found in the discriminant, if needed.
1378 let _ = mc.cat_pattern(discr_cmt, root_pat, |mc, sub_cmt, sub_pat| {
1379 match sub_pat.node {
1381 ast::PatIdent(ast::BindByRef(mutbl), _, _) => {
1382 link_region_from_node_type(
1383 rcx, sub_pat.span, sub_pat.id,
1387 // `[_, ..slice, _]` pattern
1388 ast::PatVec(_, Some(ref slice_pat), _) => {
1389 match mc.cat_slice_pattern(sub_cmt, &**slice_pat) {
1390 Ok((slice_cmt, slice_mutbl, slice_r)) => {
1391 link_region(rcx, sub_pat.span, slice_r,
1392 ty::BorrowKind::from_mutbl(slice_mutbl),
1403 fn link_autoref(rcx: &Rcx,
1406 autoref: &ty::AutoRef) {
1408 * Link lifetime of borrowed pointer resulting from autoref
1409 * to lifetimes in the value being autoref'd.
1412 debug!("link_autoref(autoref={})", autoref);
1413 let mc = mc::MemCategorizationContext::new(rcx);
1414 let expr_cmt = ignore_err!(mc.cat_expr_autoderefd(expr, autoderefs));
1415 debug!("expr_cmt={}", expr_cmt.repr(rcx.tcx()));
1418 ty::AutoPtr(r, m, _) => {
1419 link_region(rcx, expr.span, r,
1420 ty::BorrowKind::from_mutbl(m), expr_cmt);
1423 ty::AutoUnsafe(..) | ty::AutoUnsizeUniq(_) | ty::AutoUnsize(_) => {}
1427 fn link_by_ref(rcx: &Rcx,
1429 callee_scope: CodeExtent) {
1431 * Computes the guarantor for cases where the `expr` is
1432 * being passed by implicit reference and must outlive
1436 let tcx = rcx.tcx();
1437 debug!("link_by_ref(expr={}, callee_scope={})",
1438 expr.repr(tcx), callee_scope);
1439 let mc = mc::MemCategorizationContext::new(rcx);
1440 let expr_cmt = ignore_err!(mc.cat_expr(expr));
1441 let borrow_region = ty::ReScope(callee_scope);
1442 link_region(rcx, expr.span, borrow_region, ty::ImmBorrow, expr_cmt);
1445 fn link_region_from_node_type<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>,
1448 mutbl: ast::Mutability,
1449 cmt_borrowed: mc::cmt<'tcx>) {
1451 * Like `link_region()`, except that the region is
1452 * extracted from the type of `id`, which must be some
1453 * reference (`&T`, `&str`, etc).
1456 let rptr_ty = rcx.resolve_node_type(id);
1457 if !ty::type_is_error(rptr_ty) {
1458 let tcx = rcx.fcx.ccx.tcx;
1459 debug!("rptr_ty={}", ty_to_string(tcx, rptr_ty));
1460 let r = ty::ty_region(tcx, span, rptr_ty);
1461 link_region(rcx, span, r, ty::BorrowKind::from_mutbl(mutbl),
1466 fn link_region<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>,
1468 borrow_region: ty::Region,
1469 borrow_kind: ty::BorrowKind,
1470 borrow_cmt: mc::cmt<'tcx>) {
1472 * Informs the inference engine that `borrow_cmt` is being
1473 * borrowed with kind `borrow_kind` and lifetime `borrow_region`.
1474 * In order to ensure borrowck is satisfied, this may create
1475 * constraints between regions, as explained in
1476 * `link_reborrowed_region()`.
1479 let mut borrow_cmt = borrow_cmt;
1480 let mut borrow_kind = borrow_kind;
1483 debug!("link_region(borrow_region={}, borrow_kind={}, borrow_cmt={})",
1484 borrow_region.repr(rcx.tcx()),
1485 borrow_kind.repr(rcx.tcx()),
1486 borrow_cmt.repr(rcx.tcx()));
1487 match borrow_cmt.cat.clone() {
1488 mc::cat_deref(ref_cmt, _,
1489 mc::Implicit(ref_kind, ref_region)) |
1490 mc::cat_deref(ref_cmt, _,
1491 mc::BorrowedPtr(ref_kind, ref_region)) => {
1492 match link_reborrowed_region(rcx, span,
1493 borrow_region, borrow_kind,
1494 ref_cmt, ref_region, ref_kind,
1506 mc::cat_downcast(cmt_base, _) |
1507 mc::cat_deref(cmt_base, _, mc::OwnedPtr) |
1508 mc::cat_interior(cmt_base, _) => {
1509 // Borrowing interior or owned data requires the base
1510 // to be valid and borrowable in the same fashion.
1511 borrow_cmt = cmt_base;
1512 borrow_kind = borrow_kind;
1515 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1516 mc::cat_static_item |
1519 mc::cat_rvalue(..) => {
1520 // These are all "base cases" with independent lifetimes
1521 // that are not subject to inference
1528 fn link_reborrowed_region<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>,
1530 borrow_region: ty::Region,
1531 borrow_kind: ty::BorrowKind,
1532 ref_cmt: mc::cmt<'tcx>,
1533 ref_region: ty::Region,
1534 mut ref_kind: ty::BorrowKind,
1536 -> Option<(mc::cmt<'tcx>, ty::BorrowKind)>
1539 * This is the most complicated case: the path being borrowed is
1540 * itself the referent of a borrowed pointer. Let me give an
1541 * example fragment of code to make clear(er) the situation:
1543 * let r: &'a mut T = ...; // the original reference "r" has lifetime 'a
1545 * &'z *r // the reborrow has lifetime 'z
1547 * Now, in this case, our primary job is to add the inference
1548 * constraint that `'z <= 'a`. Given this setup, let's clarify the
1549 * parameters in (roughly) terms of the example:
1551 * A borrow of: `& 'z bk * r` where `r` has type `& 'a bk T`
1552 * borrow_region ^~ ref_region ^~
1553 * borrow_kind ^~ ref_kind ^~
1556 * Here `bk` stands for some borrow-kind (e.g., `mut`, `uniq`, etc).
1558 * Unfortunately, there are some complications beyond the simple
1559 * scenario I just painted:
1561 * 1. The reference `r` might in fact be a "by-ref" upvar. In that
1562 * case, we have two jobs. First, we are inferring whether this reference
1563 * should be an `&T`, `&mut T`, or `&uniq T` reference, and we must
1564 * adjust that based on this borrow (e.g., if this is an `&mut` borrow,
1565 * then `r` must be an `&mut` reference). Second, whenever we link
1566 * two regions (here, `'z <= 'a`), we supply a *cause*, and in this
1567 * case we adjust the cause to indicate that the reference being
1568 * "reborrowed" is itself an upvar. This provides a nicer error message
1569 * should something go wrong.
1571 * 2. There may in fact be more levels of reborrowing. In the
1572 * example, I said the borrow was like `&'z *r`, but it might
1573 * in fact be a borrow like `&'z **q` where `q` has type `&'a
1574 * &'b mut T`. In that case, we want to ensure that `'z <= 'a`
1575 * and `'z <= 'b`. This is explained more below.
1577 * The return value of this function indicates whether we need to
1578 * recurse and process `ref_cmt` (see case 2 above).
1581 // Possible upvar ID we may need later to create an entry in the
1584 // Detect by-ref upvar `x`:
1585 let cause = match note {
1586 mc::NoteUpvarRef(ref upvar_id) => {
1587 let mut upvar_borrow_map =
1588 rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1589 match upvar_borrow_map.get_mut(upvar_id) {
1590 Some(upvar_borrow) => {
1591 // Adjust mutability that we infer for the upvar
1592 // so it can accommodate being borrowed with
1593 // mutability `kind`:
1594 adjust_upvar_borrow_kind_for_loan(rcx,
1599 // The mutability of the upvar may have been modified
1600 // by the above adjustment, so update our local variable.
1601 ref_kind = upvar_borrow.kind;
1603 infer::ReborrowUpvar(span, *upvar_id)
1606 rcx.tcx().sess.span_bug(
1608 format!("Illegal upvar id: {}",
1610 rcx.tcx())).as_slice());
1614 mc::NoteClosureEnv(ref upvar_id) => {
1615 // We don't have any mutability changes to propagate, but
1616 // we do want to note that an upvar reborrow caused this
1618 infer::ReborrowUpvar(span, *upvar_id)
1621 infer::Reborrow(span)
1625 debug!("link_reborrowed_region: {} <= {}",
1626 borrow_region.repr(rcx.tcx()),
1627 ref_region.repr(rcx.tcx()));
1628 rcx.fcx.mk_subr(cause, borrow_region, ref_region);
1630 // If we end up needing to recurse and establish a region link
1631 // with `ref_cmt`, calculate what borrow kind we will end up
1632 // needing. This will be used below.
1634 // One interesting twist is that we can weaken the borrow kind
1635 // when we recurse: to reborrow an `&mut` referent as mutable,
1636 // borrowck requires a unique path to the `&mut` reference but not
1637 // necessarily a *mutable* path.
1638 let new_borrow_kind = match borrow_kind {
1641 ty::MutBorrow | ty::UniqueImmBorrow =>
1645 // Decide whether we need to recurse and link any regions within
1646 // the `ref_cmt`. This is concerned for the case where the value
1647 // being reborrowed is in fact a borrowed pointer found within
1648 // another borrowed pointer. For example:
1650 // let p: &'b &'a mut T = ...;
1654 // What makes this case particularly tricky is that, if the data
1655 // being borrowed is a `&mut` or `&uniq` borrow, borrowck requires
1656 // not only that `'z <= 'a`, (as before) but also `'z <= 'b`
1657 // (otherwise the user might mutate through the `&mut T` reference
1658 // after `'b` expires and invalidate the borrow we are looking at
1661 // So let's re-examine our parameters in light of this more
1662 // complicated (possible) scenario:
1664 // A borrow of: `& 'z bk * * p` where `p` has type `&'b bk & 'a bk T`
1665 // borrow_region ^~ ref_region ^~
1666 // borrow_kind ^~ ref_kind ^~
1669 // (Note that since we have not examined `ref_cmt.cat`, we don't
1670 // know whether this scenario has occurred; but I wanted to show
1671 // how all the types get adjusted.)
1674 // The reference being reborrowed is a sharable ref of
1675 // type `&'a T`. In this case, it doesn't matter where we
1676 // *found* the `&T` pointer, the memory it references will
1677 // be valid and immutable for `'a`. So we can stop here.
1679 // (Note that the `borrow_kind` must also be ImmBorrow or
1680 // else the user is borrowed imm memory as mut memory,
1681 // which means they'll get an error downstream in borrowck
1684 // If mutability was inferred from an upvar, we may be
1685 // forced to revisit this decision later if processing
1686 // another borrow or nested closure ends up converting the
1687 // upvar borrow kind to mutable/unique. Record the
1688 // information needed to perform the recursive link in the
1691 mc::NoteUpvarRef(upvar_id) => {
1692 let link = MaybeLink {
1694 borrow_region: borrow_region,
1695 borrow_kind: new_borrow_kind,
1699 match rcx.maybe_links.borrow_mut().entry(upvar_id) {
1700 Vacant(entry) => { entry.set(vec![link]); }
1701 Occupied(entry) => { entry.into_mut().push(link); }
1710 ty::MutBorrow | ty::UniqueImmBorrow => {
1711 // The reference being reborrowed is either an `&mut T` or
1712 // `&uniq T`. This is the case where recursion is needed.
1713 return Some((ref_cmt, new_borrow_kind));
1718 fn adjust_borrow_kind_for_assignment_lhs(rcx: &Rcx,
1721 * Adjusts the inferred borrow_kind as needed to account
1722 * for upvars that are assigned to in an assignment
1726 let mc = mc::MemCategorizationContext::new(rcx);
1727 let cmt = ignore_err!(mc.cat_expr(lhs));
1728 adjust_upvar_borrow_kind_for_mut(rcx, cmt);
1731 fn adjust_upvar_borrow_kind_for_mut<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>,
1732 cmt: mc::cmt<'tcx>) {
1734 * Indicates that `cmt` is being directly mutated (e.g., assigned
1735 * to). If cmt contains any by-ref upvars, this implies that
1736 * those upvars must be borrowed using an `&mut` borow.
1741 debug!("adjust_upvar_borrow_kind_for_mut(cmt={})",
1742 cmt.repr(rcx.tcx()));
1744 match cmt.cat.clone() {
1745 mc::cat_deref(base, _, mc::OwnedPtr) |
1746 mc::cat_interior(base, _) |
1747 mc::cat_downcast(base, _) => {
1748 // Interior or owned data is mutable if base is
1749 // mutable, so iterate to the base.
1754 mc::cat_deref(base, _, mc::BorrowedPtr(..)) |
1755 mc::cat_deref(base, _, mc::Implicit(..)) => {
1757 mc::NoteUpvarRef(ref upvar_id) => {
1758 // if this is an implicit deref of an
1759 // upvar, then we need to modify the
1760 // borrow_kind of the upvar to make sure it
1761 // is inferred to mutable if necessary
1762 let mut upvar_borrow_map =
1763 rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1764 let ub = &mut (*upvar_borrow_map)[*upvar_id];
1765 return adjust_upvar_borrow_kind(rcx, *upvar_id, ub, ty::MutBorrow);
1771 // assignment to deref of an `&mut`
1772 // borrowed pointer implies that the
1773 // pointer itself must be unique, but not
1774 // necessarily *mutable*
1775 return adjust_upvar_borrow_kind_for_unique(rcx, base);
1778 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1779 mc::cat_static_item |
1782 mc::cat_upvar(..) => {
1789 fn adjust_upvar_borrow_kind_for_unique<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>, cmt: mc::cmt<'tcx>) {
1792 debug!("adjust_upvar_borrow_kind_for_unique(cmt={})",
1793 cmt.repr(rcx.tcx()));
1795 match cmt.cat.clone() {
1796 mc::cat_deref(base, _, mc::OwnedPtr) |
1797 mc::cat_interior(base, _) |
1798 mc::cat_downcast(base, _) => {
1799 // Interior or owned data is unique if base is
1805 mc::cat_deref(base, _, mc::BorrowedPtr(..)) |
1806 mc::cat_deref(base, _, mc::Implicit(..)) => {
1808 mc::NoteUpvarRef(ref upvar_id) => {
1809 // if this is an implicit deref of an
1810 // upvar, then we need to modify the
1811 // borrow_kind of the upvar to make sure it
1812 // is inferred to unique if necessary
1813 let mut ub = rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1814 let ub = &mut (*ub)[*upvar_id];
1815 return adjust_upvar_borrow_kind(rcx, *upvar_id, ub, ty::UniqueImmBorrow);
1821 // for a borrowed pointer to be unique, its
1822 // base must be unique
1823 return adjust_upvar_borrow_kind_for_unique(rcx, base);
1826 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1827 mc::cat_static_item |
1830 mc::cat_upvar(..) => {
1837 fn link_upvar_borrow_kind_for_nested_closures(rcx: &mut Rcx,
1838 inner_upvar_id: ty::UpvarId,
1839 outer_upvar_id: ty::UpvarId) {
1841 * Indicates that the borrow_kind of `outer_upvar_id` must
1842 * permit a reborrowing with the borrow_kind of `inner_upvar_id`.
1843 * This occurs in nested closures, see comment above at the call to
1847 debug!("link_upvar_borrow_kind: inner_upvar_id={} outer_upvar_id={}",
1848 inner_upvar_id, outer_upvar_id);
1850 let mut upvar_borrow_map = rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1851 let inner_borrow = upvar_borrow_map[inner_upvar_id].clone();
1852 match upvar_borrow_map.get_mut(&outer_upvar_id) {
1853 Some(outer_borrow) => {
1854 adjust_upvar_borrow_kind(rcx, outer_upvar_id, outer_borrow, inner_borrow.kind);
1856 None => { /* outer closure is not a stack closure */ }
1860 fn adjust_upvar_borrow_kind_for_loan(rcx: &Rcx,
1861 upvar_id: ty::UpvarId,
1862 upvar_borrow: &mut ty::UpvarBorrow,
1863 kind: ty::BorrowKind) {
1864 debug!("adjust_upvar_borrow_kind_for_loan: upvar_id={} kind={} -> {}",
1865 upvar_id, upvar_borrow.kind, kind);
1867 adjust_upvar_borrow_kind(rcx, upvar_id, upvar_borrow, kind)
1870 fn adjust_upvar_borrow_kind(rcx: &Rcx,
1871 upvar_id: ty::UpvarId,
1872 upvar_borrow: &mut ty::UpvarBorrow,
1873 kind: ty::BorrowKind) {
1875 * We infer the borrow_kind with which to borrow upvars in a stack
1876 * closure. The borrow_kind basically follows a lattice of
1877 * `imm < unique-imm < mut`, moving from left to right as needed (but never
1878 * right to left). Here the argument `mutbl` is the borrow_kind that
1879 * is required by some particular use.
1882 debug!("adjust_upvar_borrow_kind: id={} kind=({} -> {})",
1883 upvar_id, upvar_borrow.kind, kind);
1885 match (upvar_borrow.kind, kind) {
1887 (ty::ImmBorrow, ty::UniqueImmBorrow) |
1888 (ty::ImmBorrow, ty::MutBorrow) |
1889 (ty::UniqueImmBorrow, ty::MutBorrow) => {
1890 upvar_borrow.kind = kind;
1892 // Check if there are any region links we now need to
1893 // establish due to adjusting the borrow kind of the upvar
1894 match rcx.maybe_links.borrow_mut().entry(upvar_id) {
1895 Occupied(entry) => {
1896 for MaybeLink { span, borrow_region,
1897 borrow_kind, borrow_cmt } in entry.take().into_iter()
1899 link_region(rcx, span, borrow_region, borrow_kind, borrow_cmt);
1906 (ty::ImmBorrow, ty::ImmBorrow) |
1907 (ty::UniqueImmBorrow, ty::ImmBorrow) |
1908 (ty::UniqueImmBorrow, ty::UniqueImmBorrow) |
1909 (ty::MutBorrow, _) => {
1914 fn type_must_outlive<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>,
1915 origin: infer::SubregionOrigin<'tcx>,
1920 * Ensures that all borrowed data reachable via `ty` outlives `region`.
1923 debug!("type_must_outlive(ty={}, region={})",
1925 region.repr(rcx.tcx()));
1928 regionmanip::region_wf_constraints(
1932 for constraint in constraints.iter() {
1933 debug!("constraint: {}", constraint.repr(rcx.tcx()));
1935 regionmanip::RegionSubRegionConstraint(None, r_a, r_b) => {
1936 rcx.fcx.mk_subr(origin.clone(), r_a, r_b);
1938 regionmanip::RegionSubRegionConstraint(Some(ty), r_a, r_b) => {
1939 let o1 = infer::ReferenceOutlivesReferent(ty, origin.span());
1940 rcx.fcx.mk_subr(o1, r_a, r_b);
1942 regionmanip::RegionSubParamConstraint(None, r_a, param_b) => {
1943 param_must_outlive(rcx, origin.clone(), r_a, param_b);
1945 regionmanip::RegionSubParamConstraint(Some(ty), r_a, param_b) => {
1946 let o1 = infer::ReferenceOutlivesReferent(ty, origin.span());
1947 param_must_outlive(rcx, o1, r_a, param_b);
1953 fn param_must_outlive<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>,
1954 origin: infer::SubregionOrigin<'tcx>,
1956 param_ty: ty::ParamTy) {
1957 let param_env = &rcx.fcx.inh.param_env;
1959 debug!("param_must_outlive(region={}, param_ty={})",
1960 region.repr(rcx.tcx()),
1961 param_ty.repr(rcx.tcx()));
1963 // Collect all regions that `param_ty` is known to outlive into
1965 let mut param_bounds;
1967 // To start, collect bounds from user:
1968 let param_bound = param_env.bounds.get(param_ty.space, param_ty.idx);
1970 ty::required_region_bounds(rcx.tcx(),
1971 param_bound.region_bounds.as_slice(),
1972 param_bound.builtin_bounds,
1973 param_bound.trait_bounds.as_slice());
1975 // Collect default bound of fn body that applies to all in scope
1977 param_bounds.push(param_env.implicit_region_bound);
1979 // Finally, collect regions we scraped from the well-formedness
1980 // constraints in the fn signature. To do that, we walk the list
1981 // of known relations from the fn ctxt.
1983 // This is crucial because otherwise code like this fails:
1985 // fn foo<'a, A>(x: &'a A) { x.bar() }
1987 // The problem is that the type of `x` is `&'a A`. To be
1988 // well-formed, then, A must be lower-bounded by `'a`, but we
1989 // don't know that this holds from first principles.
1990 for &(ref r, ref p) in rcx.region_param_pairs.iter() {
1991 debug!("param_ty={}/{} p={}/{}",
1992 param_ty.repr(rcx.tcx()),
1997 param_bounds.push(*r);
2001 // Inform region inference that this parameter type must be
2002 // properly bounded.
2003 infer::verify_param_bound(rcx.fcx.infcx(),