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::def::{DefArg, DefBinding, DefLocal, DefUpvar};
123 use middle::freevars;
124 use middle::mem_categorization as mc;
125 use middle::ty::{ReScope};
127 use middle::typeck::astconv::AstConv;
128 use middle::typeck::check::FnCtxt;
129 use middle::typeck::check::regionmanip;
130 use middle::typeck::infer::resolve_and_force_all_but_regions;
131 use middle::typeck::infer::resolve_type;
132 use middle::typeck::infer;
133 use middle::typeck::MethodCall;
134 use middle::pat_util;
135 use util::nodemap::{DefIdMap, NodeMap};
136 use util::ppaux::{ty_to_string, Repr};
139 use syntax::codemap::Span;
141 use syntax::visit::Visitor;
143 use std::cell::RefCell;
146 ///////////////////////////////////////////////////////////////////////////
147 // PUBLIC ENTRY POINTS
149 pub fn regionck_expr(fcx: &FnCtxt, e: &ast::Expr) {
150 let mut rcx = Rcx::new(fcx, e.id);
151 if fcx.err_count_since_creation() == 0 {
152 // regionck assumes typeck succeeded
153 rcx.visit_expr(e, ());
154 rcx.visit_region_obligations(e.id);
156 fcx.infcx().resolve_regions_and_report_errors();
159 pub fn regionck_type_defn(fcx: &FnCtxt,
161 component_tys: &[ty::t]) {
162 let mut rcx = Rcx::new(fcx, 0);
163 for &component_ty in component_tys.iter() {
164 // Check that each type outlives the empty region. Since the
165 // empty region is a subregion of all others, this can't fail
166 // unless the type does not meet the well-formedness
168 type_must_outlive(&mut rcx, infer::RelateRegionParamBound(span),
169 component_ty, ty::ReEmpty);
171 fcx.infcx().resolve_regions_and_report_errors();
174 pub fn regionck_fn(fcx: &FnCtxt, id: ast::NodeId, blk: &ast::Block) {
175 let mut rcx = Rcx::new(fcx, blk.id);
176 if fcx.err_count_since_creation() == 0 {
177 // regionck assumes typeck succeeded
178 rcx.visit_fn_body(id, blk);
180 fcx.infcx().resolve_regions_and_report_errors();
183 ///////////////////////////////////////////////////////////////////////////
186 // If mem categorization results in an error, it's because the type
187 // check failed (or will fail, when the error is uncovered and
188 // reported during writeback). In this case, we just ignore this part
189 // of the code and don't try to add any more region constraints.
190 macro_rules! ignore_err(
199 pub struct Rcx<'a, 'tcx: 'a> {
200 fcx: &'a FnCtxt<'a, 'tcx>,
202 region_param_pairs: Vec<(ty::Region, ty::ParamTy)>,
204 // id of innermost fn or loop
205 repeating_scope: ast::NodeId,
208 /// When entering a function, we can derive relationships from the
209 /// signature between various regions and type parameters. Consider
212 /// fn foo<'a, A>(x: &'a A) { ... }
214 /// Here, we can derive that `A` must outlive `'a`, because otherwise
215 /// the caller would be illegal. We record this by storing a series of
216 /// pairs (in this case, `('a, A)`). These pairs will be consulted
217 /// later during regionck.
219 /// In the case of nested fns, additional relationships may be
220 /// derived. The result is a link list walking up the stack (hence
221 /// the `previous` field).
223 pub struct RegionSubParamConstraints<'a> {
224 pairs: Vec<(ty::Region, ty::ParamTy)>,
225 previous: Option<&'a RegionSubParamConstraints<'a>>,
228 fn region_of_def(fcx: &FnCtxt, def: def::Def) -> ty::Region {
230 * Returns the validity region of `def` -- that is, how long
236 DefLocal(node_id, _) | DefArg(node_id, _) |
237 DefBinding(node_id, _) => {
238 tcx.region_maps.var_region(node_id)
240 DefUpvar(_, subdef, closure_id, body_id) => {
241 match ty::ty_closure_store(fcx.node_ty(closure_id)) {
242 ty::RegionTraitStore(..) => region_of_def(fcx, *subdef),
243 ty::UniqTraitStore => ReScope(body_id)
247 tcx.sess.bug(format!("unexpected def in region_of_def: {:?}",
253 impl<'a, 'tcx> Rcx<'a, 'tcx> {
254 pub fn new(fcx: &'a FnCtxt<'a, 'tcx>,
255 initial_repeating_scope: ast::NodeId) -> Rcx<'a, 'tcx> {
257 repeating_scope: initial_repeating_scope,
258 region_param_pairs: Vec::new() }
261 pub fn tcx(&self) -> &'a ty::ctxt<'tcx> {
265 pub fn set_repeating_scope(&mut self, scope: ast::NodeId) -> ast::NodeId {
266 let old_scope = self.repeating_scope;
267 self.repeating_scope = scope;
271 pub fn resolve_type(&self, unresolved_ty: ty::t) -> ty::t {
273 * Try to resolve the type for the given node, returning
274 * t_err if an error results. Note that we never care
275 * about the details of the error, the same error will be
276 * detected and reported in the writeback phase.
278 * Note one important point: we do not attempt to resolve
279 * *region variables* here. This is because regionck is
280 * essentially adding constraints to those region variables
281 * and so may yet influence how they are resolved.
283 * Consider this silly example:
285 * fn borrow(x: &int) -> &int {x}
286 * fn foo(x: @int) -> int { // block: B
287 * let b = borrow(x); // region: <R0>
291 * Here, the region of `b` will be `<R0>`. `<R0>` is
292 * constrainted to be some subregion of the block B and some
293 * superregion of the call. If we forced it now, we'd choose
294 * the smaller region (the call). But that would make the *b
295 * illegal. Since we don't resolve, the type of b will be
296 * `&<R0>.int` and then `*b` will require that `<R0>` be
297 * bigger than the let and the `*b` expression, so we will
298 * effectively resolve `<R0>` to be the block B.
300 match resolve_type(self.fcx.infcx(), None, unresolved_ty,
301 resolve_and_force_all_but_regions) {
303 Err(_) => ty::mk_err()
307 /// Try to resolve the type for the given node.
308 fn resolve_node_type(&self, id: ast::NodeId) -> ty::t {
309 let t = self.fcx.node_ty(id);
313 fn resolve_method_type(&self, method_call: MethodCall) -> Option<ty::t> {
314 let method_ty = self.fcx.inh.method_map.borrow()
315 .find(&method_call).map(|method| method.ty);
316 method_ty.map(|method_ty| self.resolve_type(method_ty))
319 /// Try to resolve the type for the given node.
320 pub fn resolve_expr_type_adjusted(&mut self, expr: &ast::Expr) -> ty::t {
321 let ty_unadjusted = self.resolve_node_type(expr.id);
322 if ty::type_is_error(ty_unadjusted) || ty::type_is_bot(ty_unadjusted) {
325 let tcx = self.fcx.tcx();
326 ty::adjust_ty(tcx, expr.span, expr.id, ty_unadjusted,
327 self.fcx.inh.adjustments.borrow().find(&expr.id),
328 |method_call| self.resolve_method_type(method_call))
332 fn visit_fn_body(&mut self,
336 // When we enter a function, we can derive
338 let fn_sig_map = self.fcx.inh.fn_sig_map.borrow();
339 let fn_sig = match fn_sig_map.find(&id) {
343 format!("No fn-sig entry for id={}", id).as_slice());
347 let len = self.region_param_pairs.len();
348 self.relate_free_regions(fn_sig.as_slice(), body.id);
349 self.visit_block(body, ());
350 self.visit_region_obligations(body.id);
351 self.region_param_pairs.truncate(len);
354 fn visit_region_obligations(&mut self, node_id: ast::NodeId)
356 debug!("visit_region_obligations: node_id={}", node_id);
357 let region_obligations = self.fcx.inh.region_obligations.borrow();
358 match region_obligations.find(&node_id) {
361 for r_o in vec.iter() {
362 debug!("visit_region_obligations: r_o={}",
363 r_o.repr(self.tcx()));
364 let sup_type = self.resolve_type(r_o.sup_type);
365 type_must_outlive(self, r_o.origin.clone(),
366 sup_type, r_o.sub_region);
372 fn relate_free_regions(&mut self,
373 fn_sig_tys: &[ty::t],
374 body_id: ast::NodeId) {
376 * This method populates the region map's `free_region_map`.
377 * It walks over the transformed argument and return types for
378 * each function just before we check the body of that
379 * function, looking for types where you have a borrowed
380 * pointer to other borrowed data (e.g., `&'a &'b [uint]`. We
381 * do not allow references to outlive the things they point
382 * at, so we can assume that `'a <= 'b`. This holds for both
383 * the argument and return types, basically because, on the caller
384 * side, the caller is responsible for checking that the type of
385 * every expression (including the actual values for the arguments,
386 * as well as the return type of the fn call) is well-formed.
388 * Tests: `src/test/compile-fail/regions-free-region-ordering-*.rs`
391 debug!("relate_free_regions >>");
392 let tcx = self.tcx();
394 for &ty in fn_sig_tys.iter() {
395 let ty = self.resolve_type(ty);
396 debug!("relate_free_regions(t={})", ty.repr(tcx));
397 let body_scope = ty::ReScope(body_id);
399 regionmanip::region_wf_constraints(
403 for constraint in constraints.iter() {
404 debug!("constraint: {}", constraint.repr(tcx));
406 regionmanip::RegionSubRegionConstraint(_,
408 ty::ReFree(free_b)) => {
409 tcx.region_maps.relate_free_regions(free_a, free_b);
411 regionmanip::RegionSubRegionConstraint(_,
413 ty::ReInfer(ty::ReVar(vid_b))) => {
414 self.fcx.inh.infcx.add_given(free_a, vid_b);
416 regionmanip::RegionSubRegionConstraint(..) => {
417 // In principle, we could record (and take
418 // advantage of) every relationship here, but
419 // we are also free not to -- it simply means
420 // strictly less that we can successfully type
421 // check. (It may also be that we should
422 // revise our inference system to be more
423 // general and to make use of *every*
424 // relationship that arises here, but
425 // presently we do not.)
427 regionmanip::RegionSubParamConstraint(_, r_a, p_b) => {
428 debug!("RegionSubParamConstraint: {} <= {}",
429 r_a.repr(tcx), p_b.repr(tcx));
431 self.region_param_pairs.push((r_a, p_b));
437 debug!("<< relate_free_regions");
441 impl<'fcx, 'tcx> mc::Typer<'tcx> for Rcx<'fcx, 'tcx> {
442 fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
446 fn node_ty(&self, id: ast::NodeId) -> mc::McResult<ty::t> {
447 let t = self.resolve_node_type(id);
448 if ty::type_is_error(t) {Err(())} else {Ok(t)}
451 fn node_method_ty(&self, method_call: MethodCall) -> Option<ty::t> {
452 self.resolve_method_type(method_call)
455 fn adjustments<'a>(&'a self) -> &'a RefCell<NodeMap<ty::AutoAdjustment>> {
456 &self.fcx.inh.adjustments
459 fn is_method_call(&self, id: ast::NodeId) -> bool {
460 self.fcx.inh.method_map.borrow().contains_key(&MethodCall::expr(id))
463 fn temporary_scope(&self, id: ast::NodeId) -> Option<ast::NodeId> {
464 self.tcx().region_maps.temporary_scope(id)
467 fn upvar_borrow(&self, id: ty::UpvarId) -> ty::UpvarBorrow {
468 self.fcx.inh.upvar_borrow_map.borrow().get_copy(&id)
471 fn capture_mode(&self, closure_expr_id: ast::NodeId)
472 -> freevars::CaptureMode {
473 self.tcx().capture_modes.borrow().get_copy(&closure_expr_id)
476 fn unboxed_closures<'a>(&'a self)
477 -> &'a RefCell<DefIdMap<ty::UnboxedClosure>> {
478 &self.fcx.inh.unboxed_closures
482 impl<'a, 'tcx> Visitor<()> for Rcx<'a, 'tcx> {
483 // (..) FIXME(#3238) should use visit_pat, not visit_arm/visit_local,
484 // However, right now we run into an issue whereby some free
485 // regions are not properly related if they appear within the
486 // types of arguments that must be inferred. This could be
487 // addressed by deferring the construction of the region
488 // hierarchy, and in particular the relationships between free
489 // regions, until regionck, as described in #3238.
491 fn visit_fn(&mut self, _fk: &visit::FnKind, _fd: &ast::FnDecl,
492 b: &ast::Block, _s: Span, id: ast::NodeId, _e: ()) {
493 self.visit_fn_body(id, b)
496 fn visit_item(&mut self, i: &ast::Item, _: ()) { visit_item(self, i); }
498 fn visit_expr(&mut self, ex: &ast::Expr, _: ()) { visit_expr(self, ex); }
500 //visit_pat: visit_pat, // (..) see above
502 fn visit_arm(&mut self, a: &ast::Arm, _: ()) { visit_arm(self, a); }
504 fn visit_local(&mut self, l: &ast::Local, _: ()) { visit_local(self, l); }
506 fn visit_block(&mut self, b: &ast::Block, _: ()) { visit_block(self, b); }
509 fn visit_item(_rcx: &mut Rcx, _item: &ast::Item) {
513 fn visit_block(rcx: &mut Rcx, b: &ast::Block) {
514 visit::walk_block(rcx, b, ());
517 fn visit_arm(rcx: &mut Rcx, arm: &ast::Arm) {
519 for p in arm.pats.iter() {
520 constrain_bindings_in_pat(&**p, rcx);
523 visit::walk_arm(rcx, arm, ());
526 fn visit_local(rcx: &mut Rcx, l: &ast::Local) {
528 constrain_bindings_in_pat(&*l.pat, rcx);
530 visit::walk_local(rcx, l, ());
533 fn constrain_bindings_in_pat(pat: &ast::Pat, rcx: &mut Rcx) {
534 let tcx = rcx.fcx.tcx();
535 debug!("regionck::visit_pat(pat={})", pat.repr(tcx));
536 pat_util::pat_bindings(&tcx.def_map, pat, |_, id, span, _| {
537 // If we have a variable that contains region'd data, that
538 // data will be accessible from anywhere that the variable is
539 // accessed. We must be wary of loops like this:
541 // // from src/test/compile-fail/borrowck-lend-flow.rs
542 // let mut v = box 3, w = box 4;
543 // let mut x = &mut w;
546 // borrow(v); //~ ERROR cannot borrow
547 // x = &mut v; // (1)
550 // Typically, we try to determine the region of a borrow from
551 // those points where it is dereferenced. In this case, one
552 // might imagine that the lifetime of `x` need only be the
553 // body of the loop. But of course this is incorrect because
554 // the pointer that is created at point (1) is consumed at
555 // point (2), meaning that it must be live across the loop
556 // iteration. The easiest way to guarantee this is to require
557 // that the lifetime of any regions that appear in a
558 // variable's type enclose at least the variable's scope.
560 let var_region = tcx.region_maps.var_region(id);
561 type_of_node_must_outlive(
562 rcx, infer::BindingTypeIsNotValidAtDecl(span),
567 fn visit_expr(rcx: &mut Rcx, expr: &ast::Expr) {
568 debug!("regionck::visit_expr(e={}, repeating_scope={:?})",
569 expr.repr(rcx.fcx.tcx()), rcx.repeating_scope);
571 // No matter what, the type of each expression must outlive the
572 // scope of that expression. This also guarantees basic WF.
573 let expr_ty = rcx.resolve_node_type(expr.id);
575 type_must_outlive(rcx, infer::ExprTypeIsNotInScope(expr_ty, expr.span),
576 expr_ty, ty::ReScope(expr.id));
578 let method_call = MethodCall::expr(expr.id);
579 let has_method_map = rcx.fcx.inh.method_map.borrow().contains_key(&method_call);
581 // Check any autoderefs or autorefs that appear.
582 for &adjustment in rcx.fcx.inh.adjustments.borrow().find(&expr.id).iter() {
583 debug!("adjustment={:?}", adjustment);
585 ty::AutoDerefRef(ty::AutoDerefRef {autoderefs, autoref: ref opt_autoref}) => {
586 let expr_ty = rcx.resolve_node_type(expr.id);
587 constrain_autoderefs(rcx, expr, autoderefs, expr_ty);
588 for autoref in opt_autoref.iter() {
589 link_autoref(rcx, expr, autoderefs, autoref);
591 // Require that the resulting region encompasses
594 // FIXME(#6268) remove to support nested method calls
595 type_of_node_must_outlive(
596 rcx, infer::AutoBorrow(expr.span),
597 expr.id, ty::ReScope(expr.id));
601 ty::AutoObject(_, ref bounds, _, _) => {
602 // Determine if we are casting `expr` to a trait
603 // instance. If so, we have to be sure that the type
604 // of the source obeys the new region bound.
605 let source_ty = rcx.resolve_node_type(expr.id);
606 type_must_outlive(rcx, infer::RelateObjectBound(expr.span),
607 source_ty, bounds.region_bound);
615 ast::ExprCall(ref callee, ref args) => {
617 constrain_call(rcx, expr, Some(*callee),
618 args.as_slice(), false);
620 constrain_callee(rcx, callee.id, expr, &**callee);
628 visit::walk_expr(rcx, expr, ());
631 ast::ExprMethodCall(_, _, ref args) => {
632 constrain_call(rcx, expr, Some(*args.get(0)),
633 args.slice_from(1), false);
635 visit::walk_expr(rcx, expr, ());
638 ast::ExprAssign(ref lhs, _) => {
639 adjust_borrow_kind_for_assignment_lhs(rcx, &**lhs);
640 visit::walk_expr(rcx, expr, ());
643 ast::ExprAssignOp(_, ref lhs, ref rhs) => {
645 constrain_call(rcx, expr, Some(lhs.clone()),
646 [rhs.clone()], true);
649 adjust_borrow_kind_for_assignment_lhs(rcx, &**lhs);
651 visit::walk_expr(rcx, expr, ());
654 ast::ExprIndex(ref lhs, ref rhs) |
655 ast::ExprBinary(_, ref lhs, ref rhs) if has_method_map => {
656 // As `expr_method_call`, but the call is via an
657 // overloaded op. Note that we (sadly) currently use an
658 // implicit "by ref" sort of passing style here. This
659 // should be converted to an adjustment!
660 constrain_call(rcx, expr, Some(lhs.clone()),
661 [rhs.clone()], true);
663 visit::walk_expr(rcx, expr, ());
666 ast::ExprUnary(_, ref lhs) if has_method_map => {
668 constrain_call(rcx, expr, Some(lhs.clone()), [], true);
670 visit::walk_expr(rcx, expr, ());
673 ast::ExprUnary(ast::UnBox, ref base) => {
674 // Managed data must not have borrowed pointers within it:
675 let base_ty = rcx.resolve_node_type(base.id);
676 type_must_outlive(rcx, infer::Managed(expr.span),
677 base_ty, ty::ReStatic);
678 visit::walk_expr(rcx, expr, ());
681 ast::ExprUnary(ast::UnDeref, ref base) => {
682 // For *a, the lifetime of a must enclose the deref
683 let method_call = MethodCall::expr(expr.id);
684 let base_ty = match rcx.fcx.inh.method_map.borrow().find(&method_call) {
686 constrain_call(rcx, expr, Some(base.clone()), [], true);
687 ty::ty_fn_ret(method.ty)
689 None => rcx.resolve_node_type(base.id)
691 match ty::get(base_ty).sty {
692 ty::ty_rptr(r_ptr, _) => {
693 mk_subregion_due_to_dereference(rcx, expr.span,
694 ty::ReScope(expr.id), r_ptr);
699 visit::walk_expr(rcx, expr, ());
702 ast::ExprIndex(ref vec_expr, _) => {
703 // For a[b], the lifetime of a must enclose the deref
704 let vec_type = rcx.resolve_expr_type_adjusted(&**vec_expr);
705 constrain_index(rcx, expr, vec_type);
707 visit::walk_expr(rcx, expr, ());
710 ast::ExprCast(ref source, _) => {
711 // Determine if we are casting `source` to a trait
712 // instance. If so, we have to be sure that the type of
713 // the source obeys the trait's region bound.
714 constrain_cast(rcx, expr, &**source);
715 visit::walk_expr(rcx, expr, ());
718 ast::ExprAddrOf(m, ref base) => {
719 link_addr_of(rcx, expr, m, &**base);
721 // Require that when you write a `&expr` expression, the
722 // resulting pointer has a lifetime that encompasses the
723 // `&expr` expression itself. Note that we constraining
724 // the type of the node expr.id here *before applying
727 // FIXME(#6268) nested method calls requires that this rule change
728 let ty0 = rcx.resolve_node_type(expr.id);
729 type_must_outlive(rcx, infer::AddrOf(expr.span),
730 ty0, ty::ReScope(expr.id));
731 visit::walk_expr(rcx, expr, ());
734 ast::ExprMatch(ref discr, ref arms) => {
735 link_match(rcx, &**discr, arms.as_slice());
737 visit::walk_expr(rcx, expr, ());
740 ast::ExprFnBlock(_, _, ref body) |
741 ast::ExprProc(_, ref body) |
742 ast::ExprUnboxedFn(_, _, _, ref body) => {
743 check_expr_fn_block(rcx, expr, &**body);
746 ast::ExprLoop(ref body, _) => {
747 let repeating_scope = rcx.set_repeating_scope(body.id);
748 visit::walk_expr(rcx, expr, ());
749 rcx.set_repeating_scope(repeating_scope);
752 ast::ExprWhile(ref cond, ref body, _) => {
753 let repeating_scope = rcx.set_repeating_scope(cond.id);
754 rcx.visit_expr(&**cond, ());
756 rcx.set_repeating_scope(body.id);
757 rcx.visit_block(&**body, ());
759 rcx.set_repeating_scope(repeating_scope);
762 ast::ExprForLoop(ref pat, ref head, ref body, _) => {
763 constrain_bindings_in_pat(&**pat, rcx);
766 let mc = mc::MemCategorizationContext::new(rcx);
767 let head_cmt = ignore_err!(mc.cat_expr(&**head));
768 link_pattern(rcx, mc, head_cmt, &**pat);
771 rcx.visit_expr(&**head, ());
772 type_of_node_must_outlive(rcx,
773 infer::AddrOf(expr.span),
775 ty::ReScope(expr.id));
777 let repeating_scope = rcx.set_repeating_scope(body.id);
778 rcx.visit_block(&**body, ());
779 rcx.set_repeating_scope(repeating_scope);
783 visit::walk_expr(rcx, expr, ());
788 fn constrain_cast(rcx: &mut Rcx,
789 cast_expr: &ast::Expr,
790 source_expr: &ast::Expr)
792 debug!("constrain_cast(cast_expr={}, source_expr={})",
793 cast_expr.repr(rcx.tcx()),
794 source_expr.repr(rcx.tcx()));
796 let source_ty = rcx.resolve_node_type(source_expr.id);
797 let target_ty = rcx.resolve_node_type(cast_expr.id);
799 walk_cast(rcx, cast_expr, source_ty, target_ty);
801 fn walk_cast(rcx: &mut Rcx,
802 cast_expr: &ast::Expr,
805 debug!("walk_cast(from_ty={}, to_ty={})",
806 from_ty.repr(rcx.tcx()),
807 to_ty.repr(rcx.tcx()));
808 match (&ty::get(from_ty).sty, &ty::get(to_ty).sty) {
809 /*From:*/ (&ty::ty_rptr(from_r, ref from_mt),
810 /*To: */ &ty::ty_rptr(to_r, ref to_mt)) => {
811 // Target cannot outlive source, naturally.
812 rcx.fcx.mk_subr(infer::Reborrow(cast_expr.span), to_r, from_r);
813 walk_cast(rcx, cast_expr, from_mt.ty, to_mt.ty);
817 /*To: */ &ty::ty_trait(box ty::TyTrait { bounds, .. })) => {
818 // When T is existentially quantified as a trait
819 // `Foo+'to`, it must outlive the region bound `'to`.
820 type_must_outlive(rcx, infer::RelateObjectBound(cast_expr.span),
821 from_ty, bounds.region_bound);
824 /*From:*/ (&ty::ty_uniq(from_referent_ty),
825 /*To: */ &ty::ty_uniq(to_referent_ty)) => {
826 walk_cast(rcx, cast_expr, from_referent_ty, to_referent_ty);
834 fn check_expr_fn_block(rcx: &mut Rcx,
837 let tcx = rcx.fcx.tcx();
838 let function_type = rcx.resolve_node_type(expr.id);
840 match ty::get(function_type).sty {
841 ty::ty_closure(box ty::ClosureTy{store: ty::RegionTraitStore(..),
844 // For closure, ensure that the variables outlive region
845 // bound, since they are captured by reference.
846 freevars::with_freevars(tcx, expr.id, |freevars| {
847 if freevars.is_empty() {
848 // No free variables means that the environment
849 // will be NULL at runtime and hence the closure
850 // has static lifetime.
852 // Variables being referenced must outlive closure.
853 constrain_free_variables_in_stack_closure(
854 rcx, bounds.region_bound, expr, freevars);
856 // Closure is stack allocated and hence cannot
857 // outlive the appropriate temporary scope.
858 let s = rcx.repeating_scope;
859 rcx.fcx.mk_subr(infer::InfStackClosure(expr.span),
860 bounds.region_bound, ty::ReScope(s));
864 ty::ty_closure(box ty::ClosureTy{store: ty::UniqTraitStore,
867 // For proc, ensure that the *types* of the variables
868 // outlive region bound, since they are captured by value.
869 freevars::with_freevars(tcx, expr.id, |freevars| {
870 ensure_free_variable_types_outlive_closure_bound(
871 rcx, bounds.region_bound, expr, freevars);
874 ty::ty_unboxed_closure(_, region) => {
875 freevars::with_freevars(tcx, expr.id, |freevars| {
876 // No free variables means that there is no environment and
877 // hence the closure has static lifetime. Otherwise, the
878 // closure must not outlive the variables it closes over
881 // NDM -- this seems wrong, discuss with pcwalton, should
882 // be straightforward enough.
883 if !freevars.is_empty() {
884 ensure_free_variable_types_outlive_closure_bound(
885 rcx, region, expr, freevars);
892 let repeating_scope = rcx.set_repeating_scope(body.id);
893 visit::walk_expr(rcx, expr, ());
894 rcx.set_repeating_scope(repeating_scope);
896 match ty::get(function_type).sty {
897 ty::ty_closure(box ty::ClosureTy {
898 store: ty::RegionTraitStore(..),
901 freevars::with_freevars(tcx, expr.id, |freevars| {
902 propagate_upupvar_borrow_kind(rcx, expr, freevars);
908 fn ensure_free_variable_types_outlive_closure_bound(
910 region_bound: ty::Region,
912 freevars: &[freevars::freevar_entry])
915 * Make sure that the type of all free variables referenced
916 * inside a closure/proc outlive the closure/proc's lifetime
917 * bound. This is just a special case of the usual rules about
918 * closed over values outliving the object's lifetime bound.
921 let tcx = rcx.fcx.ccx.tcx;
923 debug!("ensure_free_variable_types_outlive_closure_bound({}, {})",
924 region_bound.repr(tcx), expr.repr(tcx));
926 for freevar in freevars.iter() {
928 let def_id = freevar.def.def_id();
929 assert!(def_id.krate == ast::LOCAL_CRATE);
933 let var_ty = rcx.resolve_node_type(var_node_id);
936 rcx, infer::RelateProcBound(expr.span, var_node_id, var_ty),
937 var_ty, region_bound);
941 fn constrain_free_variables_in_stack_closure(
943 region_bound: ty::Region,
945 freevars: &[freevars::freevar_entry])
948 * Make sure that all free variables referenced inside the
949 * closure outlive the closure's lifetime bound. Also, create
950 * an entry in the upvar_borrows map with a region.
953 let tcx = rcx.fcx.ccx.tcx;
954 let infcx = rcx.fcx.infcx();
955 debug!("constrain_free_variables({}, {})",
956 region_bound.repr(tcx), expr.repr(tcx));
957 for freevar in freevars.iter() {
958 debug!("freevar def is {:?}", freevar.def);
960 // Identify the variable being closed over and its node-id.
961 let def = freevar.def;
963 let def_id = def.def_id();
964 assert!(def_id.krate == ast::LOCAL_CRATE);
967 let upvar_id = ty::UpvarId { var_id: var_node_id,
968 closure_expr_id: expr.id };
970 // Create a region variable to represent this borrow. This borrow
971 // must outlive the region on the closure.
972 let origin = infer::UpvarRegion(upvar_id, expr.span);
973 let freevar_region = infcx.next_region_var(origin);
974 rcx.fcx.mk_subr(infer::FreeVariable(freevar.span, var_node_id),
975 region_bound, freevar_region);
977 // Create a UpvarBorrow entry. Note that we begin with a
978 // const borrow_kind, but change it to either mut or
979 // immutable as dictated by the uses.
980 let upvar_borrow = ty::UpvarBorrow { kind: ty::ImmBorrow,
981 region: freevar_region };
982 rcx.fcx.inh.upvar_borrow_map.borrow_mut().insert(upvar_id,
985 // Guarantee that the closure does not outlive the variable itself.
986 let enclosing_region = region_of_def(rcx.fcx, def);
987 debug!("enclosing_region = {}", enclosing_region.repr(tcx));
988 rcx.fcx.mk_subr(infer::FreeVariable(freevar.span, var_node_id),
989 region_bound, enclosing_region);
993 fn propagate_upupvar_borrow_kind(rcx: &mut Rcx,
995 freevars: &[freevars::freevar_entry]) {
996 let tcx = rcx.fcx.ccx.tcx;
997 debug!("propagate_upupvar_borrow_kind({})", expr.repr(tcx));
998 for freevar in freevars.iter() {
999 // Because of the semi-hokey way that we are doing
1000 // borrow_kind inference, we need to check for
1001 // indirect dependencies, like so:
1010 // Here, the `inner_call` is basically "reborrowing" the
1011 // outer pointer. With no other changes, `inner_call`
1012 // would infer that it requires a mutable borrow, but
1013 // `outer_call` would infer that a const borrow is
1014 // sufficient. This is because we haven't linked the
1015 // borrow_kind of the borrow that occurs in the inner
1016 // closure to the borrow_kind of the borrow in the outer
1017 // closure. Note that regions *are* naturally linked
1018 // because we have a proper inference scheme there.
1020 // Anyway, for borrow_kind, we basically go back over now
1021 // after checking the inner closure (and hence
1022 // determining the final borrow_kind) and propagate that as
1023 // a constraint on the outer closure.
1025 def::DefUpvar(var_id, _, outer_closure_id, _) => {
1026 // thing being captured is itself an upvar:
1027 let outer_upvar_id = ty::UpvarId {
1029 closure_expr_id: outer_closure_id };
1030 let inner_upvar_id = ty::UpvarId {
1032 closure_expr_id: expr.id };
1033 link_upvar_borrow_kind_for_nested_closures(rcx,
1043 fn constrain_callee(rcx: &mut Rcx,
1044 callee_id: ast::NodeId,
1045 call_expr: &ast::Expr,
1046 callee_expr: &ast::Expr) {
1047 let call_region = ty::ReScope(call_expr.id);
1049 let callee_ty = rcx.resolve_node_type(callee_id);
1050 match ty::get(callee_ty).sty {
1051 ty::ty_bare_fn(..) => { }
1052 ty::ty_closure(ref closure_ty) => {
1053 let region = match closure_ty.store {
1054 ty::RegionTraitStore(r, _) => {
1055 // While we're here, link the closure's region with a unique
1056 // immutable borrow (gathered later in borrowck)
1057 let mc = mc::MemCategorizationContext::new(rcx);
1058 let expr_cmt = ignore_err!(mc.cat_expr(callee_expr));
1059 link_region(rcx, callee_expr.span, call_region,
1060 ty::UniqueImmBorrow, expr_cmt);
1063 ty::UniqTraitStore => ty::ReStatic
1065 rcx.fcx.mk_subr(infer::InvokeClosure(callee_expr.span),
1066 call_region, region);
1069 // this should not happen, but it does if the program is
1072 // tcx.sess.span_bug(
1073 // callee_expr.span,
1074 // format!("Calling non-function: {}", callee_ty.repr(tcx)));
1079 fn constrain_call(rcx: &mut Rcx,
1080 call_expr: &ast::Expr,
1081 receiver: Option<Gc<ast::Expr>>,
1082 arg_exprs: &[Gc<ast::Expr>],
1083 implicitly_ref_args: bool) {
1084 //! Invoked on every call site (i.e., normal calls, method calls,
1085 //! and overloaded operators). Constrains the regions which appear
1086 //! in the type of the function. Also constrains the regions that
1087 //! appear in the arguments appropriately.
1089 let tcx = rcx.fcx.tcx();
1090 debug!("constrain_call(call_expr={}, \
1093 implicitly_ref_args={:?})",
1094 call_expr.repr(tcx),
1096 arg_exprs.repr(tcx),
1097 implicitly_ref_args);
1099 // `callee_region` is the scope representing the time in which the
1102 // FIXME(#6268) to support nested method calls, should be callee_id
1103 let callee_scope = call_expr.id;
1104 let callee_region = ty::ReScope(callee_scope);
1106 debug!("callee_region={}", callee_region.repr(tcx));
1108 for arg_expr in arg_exprs.iter() {
1109 debug!("Argument: {}", arg_expr.repr(tcx));
1111 // ensure that any regions appearing in the argument type are
1112 // valid for at least the lifetime of the function:
1113 type_of_node_must_outlive(
1114 rcx, infer::CallArg(arg_expr.span),
1115 arg_expr.id, callee_region);
1117 // unfortunately, there are two means of taking implicit
1118 // references, and we need to propagate constraints as a
1119 // result. modes are going away and the "DerefArgs" code
1120 // should be ported to use adjustments
1121 if implicitly_ref_args {
1122 link_by_ref(rcx, &**arg_expr, callee_scope);
1126 // as loop above, but for receiver
1127 for r in receiver.iter() {
1128 debug!("receiver: {}", r.repr(tcx));
1129 type_of_node_must_outlive(
1130 rcx, infer::CallRcvr(r.span),
1131 r.id, callee_region);
1132 if implicitly_ref_args {
1133 link_by_ref(rcx, &**r, callee_scope);
1138 fn constrain_autoderefs(rcx: &mut Rcx,
1139 deref_expr: &ast::Expr,
1141 mut derefd_ty: ty::t) {
1143 * Invoked on any auto-dereference that occurs. Checks that if
1144 * this is a region pointer being dereferenced, the lifetime of
1145 * the pointer includes the deref expr.
1147 let r_deref_expr = ty::ReScope(deref_expr.id);
1148 for i in range(0u, derefs) {
1149 debug!("constrain_autoderefs(deref_expr=?, derefd_ty={}, derefs={:?}/{:?}",
1150 rcx.fcx.infcx().ty_to_string(derefd_ty),
1153 let method_call = MethodCall::autoderef(deref_expr.id, i);
1154 derefd_ty = match rcx.fcx.inh.method_map.borrow().find(&method_call) {
1156 // Treat overloaded autoderefs as if an AutoRef adjustment
1157 // was applied on the base type, as that is always the case.
1158 let fn_sig = ty::ty_fn_sig(method.ty);
1159 let self_ty = *fn_sig.inputs.get(0);
1160 let (m, r) = match ty::get(self_ty).sty {
1161 ty::ty_rptr(r, ref m) => (m.mutbl, r),
1162 _ => rcx.tcx().sess.span_bug(deref_expr.span,
1163 format!("bad overloaded deref type {}",
1164 method.ty.repr(rcx.tcx())).as_slice())
1167 let mc = mc::MemCategorizationContext::new(rcx);
1168 let self_cmt = ignore_err!(mc.cat_expr_autoderefd(deref_expr, i));
1169 link_region(rcx, deref_expr.span, r,
1170 ty::BorrowKind::from_mutbl(m), self_cmt);
1173 // Specialized version of constrain_call.
1174 type_must_outlive(rcx, infer::CallRcvr(deref_expr.span),
1175 self_ty, r_deref_expr);
1176 type_must_outlive(rcx, infer::CallReturn(deref_expr.span),
1177 fn_sig.output, r_deref_expr);
1183 match ty::get(derefd_ty).sty {
1184 ty::ty_rptr(r_ptr, _) => {
1185 mk_subregion_due_to_dereference(rcx, deref_expr.span,
1186 r_deref_expr, r_ptr);
1191 match ty::deref(derefd_ty, true) {
1192 Some(mt) => derefd_ty = mt.ty,
1193 /* if this type can't be dereferenced, then there's already an error
1194 in the session saying so. Just bail out for now */
1200 pub fn mk_subregion_due_to_dereference(rcx: &mut Rcx,
1202 minimum_lifetime: ty::Region,
1203 maximum_lifetime: ty::Region) {
1204 rcx.fcx.mk_subr(infer::DerefPointer(deref_span),
1205 minimum_lifetime, maximum_lifetime)
1209 fn constrain_index(rcx: &mut Rcx,
1210 index_expr: &ast::Expr,
1214 * Invoked on any index expression that occurs. Checks that if
1215 * this is a slice being indexed, the lifetime of the pointer
1216 * includes the deref expr.
1219 debug!("constrain_index(index_expr=?, indexed_ty={}",
1220 rcx.fcx.infcx().ty_to_string(indexed_ty));
1222 let r_index_expr = ty::ReScope(index_expr.id);
1223 match ty::get(indexed_ty).sty {
1224 ty::ty_rptr(r_ptr, mt) => match ty::get(mt.ty).sty {
1225 ty::ty_vec(_, None) | ty::ty_str => {
1226 rcx.fcx.mk_subr(infer::IndexSlice(index_expr.span),
1227 r_index_expr, r_ptr);
1236 fn type_of_node_must_outlive(
1238 origin: infer::SubregionOrigin,
1240 minimum_lifetime: ty::Region)
1243 * Guarantees that any lifetimes which appear in the type of
1244 * the node `id` (after applying adjustments) are valid for at
1245 * least `minimum_lifetime`
1248 let tcx = rcx.fcx.tcx();
1250 // Try to resolve the type. If we encounter an error, then typeck
1251 // is going to fail anyway, so just stop here and let typeck
1252 // report errors later on in the writeback phase.
1253 let ty0 = rcx.resolve_node_type(id);
1254 let ty = ty::adjust_ty(tcx, origin.span(), id, ty0,
1255 rcx.fcx.inh.adjustments.borrow().find(&id),
1256 |method_call| rcx.resolve_method_type(method_call));
1257 debug!("constrain_regions_in_type_of_node(\
1258 ty={}, ty0={}, id={}, minimum_lifetime={:?})",
1259 ty_to_string(tcx, ty), ty_to_string(tcx, ty0),
1260 id, minimum_lifetime);
1261 type_must_outlive(rcx, origin, ty, minimum_lifetime);
1264 fn link_addr_of(rcx: &mut Rcx, expr: &ast::Expr,
1265 mutability: ast::Mutability, base: &ast::Expr) {
1267 * Computes the guarantor for an expression `&base` and then
1268 * ensures that the lifetime of the resulting pointer is linked
1269 * to the lifetime of its guarantor (if any).
1272 debug!("link_addr_of(base=?)");
1275 let mc = mc::MemCategorizationContext::new(rcx);
1276 ignore_err!(mc.cat_expr(base))
1278 link_region_from_node_type(rcx, expr.span, expr.id, mutability, cmt);
1281 fn link_local(rcx: &Rcx, local: &ast::Local) {
1283 * Computes the guarantors for any ref bindings in a `let` and
1284 * then ensures that the lifetime of the resulting pointer is
1285 * linked to the lifetime of the initialization expression.
1288 debug!("regionck::for_local()");
1289 let init_expr = match local.init {
1291 Some(ref expr) => expr,
1293 let mc = mc::MemCategorizationContext::new(rcx);
1294 let discr_cmt = ignore_err!(mc.cat_expr(&**init_expr));
1295 link_pattern(rcx, mc, discr_cmt, &*local.pat);
1298 fn link_match(rcx: &Rcx, discr: &ast::Expr, arms: &[ast::Arm]) {
1300 * Computes the guarantors for any ref bindings in a match and
1301 * then ensures that the lifetime of the resulting pointer is
1302 * linked to the lifetime of its guarantor (if any).
1305 debug!("regionck::for_match()");
1306 let mc = mc::MemCategorizationContext::new(rcx);
1307 let discr_cmt = ignore_err!(mc.cat_expr(discr));
1308 debug!("discr_cmt={}", discr_cmt.repr(rcx.tcx()));
1309 for arm in arms.iter() {
1310 for root_pat in arm.pats.iter() {
1311 link_pattern(rcx, mc, discr_cmt.clone(), &**root_pat);
1316 fn link_pattern(rcx: &Rcx,
1317 mc: mc::MemCategorizationContext<Rcx>,
1319 root_pat: &ast::Pat) {
1321 * Link lifetimes of any ref bindings in `root_pat` to
1322 * the pointers found in the discriminant, if needed.
1325 let _ = mc.cat_pattern(discr_cmt, root_pat, |mc, sub_cmt, sub_pat| {
1326 match sub_pat.node {
1328 ast::PatIdent(ast::BindByRef(mutbl), _, _) => {
1329 link_region_from_node_type(
1330 rcx, sub_pat.span, sub_pat.id,
1334 // `[_, ..slice, _]` pattern
1335 ast::PatVec(_, Some(ref slice_pat), _) => {
1336 match mc.cat_slice_pattern(sub_cmt, &**slice_pat) {
1337 Ok((slice_cmt, slice_mutbl, slice_r)) => {
1338 link_region(rcx, sub_pat.span, slice_r,
1339 ty::BorrowKind::from_mutbl(slice_mutbl),
1350 fn link_autoref(rcx: &Rcx,
1353 autoref: &ty::AutoRef) {
1355 * Link lifetime of borrowed pointer resulting from autoref
1356 * to lifetimes in the value being autoref'd.
1359 debug!("link_autoref(autoref={:?})", autoref);
1360 let mc = mc::MemCategorizationContext::new(rcx);
1361 let expr_cmt = ignore_err!(mc.cat_expr_autoderefd(expr, autoderefs));
1362 debug!("expr_cmt={}", expr_cmt.repr(rcx.tcx()));
1365 ty::AutoPtr(r, m, _) => {
1366 link_region(rcx, expr.span, r,
1367 ty::BorrowKind::from_mutbl(m), expr_cmt);
1370 ty::AutoUnsafe(..) | ty::AutoUnsizeUniq(_) | ty::AutoUnsize(_) => {}
1374 fn link_by_ref(rcx: &Rcx,
1376 callee_scope: ast::NodeId) {
1378 * Computes the guarantor for cases where the `expr` is
1379 * being passed by implicit reference and must outlive
1383 let tcx = rcx.tcx();
1384 debug!("link_by_ref(expr={}, callee_scope={})",
1385 expr.repr(tcx), callee_scope);
1386 let mc = mc::MemCategorizationContext::new(rcx);
1387 let expr_cmt = ignore_err!(mc.cat_expr(expr));
1388 let borrow_region = ty::ReScope(callee_scope);
1389 link_region(rcx, expr.span, borrow_region, ty::ImmBorrow, expr_cmt);
1392 fn link_region_from_node_type(rcx: &Rcx,
1395 mutbl: ast::Mutability,
1396 cmt_borrowed: mc::cmt) {
1398 * Like `link_region()`, except that the region is
1399 * extracted from the type of `id`, which must be some
1400 * reference (`&T`, `&str`, etc).
1403 let rptr_ty = rcx.resolve_node_type(id);
1404 if !ty::type_is_bot(rptr_ty) && !ty::type_is_error(rptr_ty) {
1405 let tcx = rcx.fcx.ccx.tcx;
1406 debug!("rptr_ty={}", ty_to_string(tcx, rptr_ty));
1407 let r = ty::ty_region(tcx, span, rptr_ty);
1408 link_region(rcx, span, r, ty::BorrowKind::from_mutbl(mutbl),
1413 fn link_region(rcx: &Rcx,
1415 borrow_region: ty::Region,
1416 borrow_kind: ty::BorrowKind,
1417 borrow_cmt: mc::cmt) {
1419 * Informs the inference engine that `borrow_cmt` is being
1420 * borrowed with kind `borrow_kind` and lifetime `borrow_region`.
1421 * In order to ensure borrowck is satisfied, this may create
1422 * constraints between regions, as explained in
1423 * `link_reborrowed_region()`.
1426 let mut borrow_cmt = borrow_cmt;
1427 let mut borrow_kind = borrow_kind;
1430 debug!("link_region(borrow_region={}, borrow_kind={}, borrow_cmt={})",
1431 borrow_region.repr(rcx.tcx()),
1432 borrow_kind.repr(rcx.tcx()),
1433 borrow_cmt.repr(rcx.tcx()));
1434 match borrow_cmt.cat.clone() {
1435 mc::cat_deref(ref_cmt, _,
1436 mc::Implicit(ref_kind, ref_region)) |
1437 mc::cat_deref(ref_cmt, _,
1438 mc::BorrowedPtr(ref_kind, ref_region)) => {
1439 match link_reborrowed_region(rcx, span,
1440 borrow_region, borrow_kind,
1441 ref_cmt, ref_region, ref_kind) {
1452 mc::cat_discr(cmt_base, _) |
1453 mc::cat_downcast(cmt_base) |
1454 mc::cat_deref(cmt_base, _, mc::GcPtr(..)) |
1455 mc::cat_deref(cmt_base, _, mc::OwnedPtr) |
1456 mc::cat_interior(cmt_base, _) => {
1457 // Borrowing interior or owned data requires the base
1458 // to be valid and borrowable in the same fashion.
1459 borrow_cmt = cmt_base;
1460 borrow_kind = borrow_kind;
1463 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1464 mc::cat_static_item |
1465 mc::cat_copied_upvar(..) |
1469 mc::cat_rvalue(..) => {
1470 // These are all "base cases" with independent lifetimes
1471 // that are not subject to inference
1478 fn link_reborrowed_region(rcx: &Rcx,
1480 borrow_region: ty::Region,
1481 borrow_kind: ty::BorrowKind,
1483 ref_region: ty::Region,
1484 ref_kind: ty::BorrowKind)
1485 -> Option<(mc::cmt, ty::BorrowKind)>
1488 * This is the most complicated case: the path being borrowed is
1489 * itself the referent of a borrowed pointer. Let me give an
1490 * example fragment of code to make clear(er) the situation:
1492 * let r: &'a mut T = ...; // the original reference "r" has lifetime 'a
1494 * &'z *r // the reborrow has lifetime 'z
1496 * Now, in this case, our primary job is to add the inference
1497 * constraint that `'z <= 'a`. Given this setup, let's clarify the
1498 * parameters in (roughly) terms of the example:
1500 * A borrow of: `& 'z bk * r` where `r` has type `& 'a bk T`
1501 * borrow_region ^~ ref_region ^~
1502 * borrow_kind ^~ ref_kind ^~
1505 * Here `bk` stands for some borrow-kind (e.g., `mut`, `uniq`, etc).
1507 * Unfortunately, there are some complications beyond the simple
1508 * scenario I just painted:
1510 * 1. The reference `r` might in fact be a "by-ref" upvar. In that
1511 * case, we have two jobs. First, we are inferring whether this reference
1512 * should be an `&T`, `&mut T`, or `&uniq T` reference, and we must
1513 * adjust that based on this borrow (e.g., if this is an `&mut` borrow,
1514 * then `r` must be an `&mut` reference). Second, whenever we link
1515 * two regions (here, `'z <= 'a`), we supply a *cause*, and in this
1516 * case we adjust the cause to indicate that the reference being
1517 * "reborrowed" is itself an upvar. This provides a nicer error message
1518 * should something go wrong.
1520 * 2. There may in fact be more levels of reborrowing. In the
1521 * example, I said the borrow was like `&'z *r`, but it might
1522 * in fact be a borrow like `&'z **q` where `q` has type `&'a
1523 * &'b mut T`. In that case, we want to ensure that `'z <= 'a`
1524 * and `'z <= 'b`. This is explained more below.
1526 * The return value of this function indicates whether we need to
1527 * recurse and process `ref_cmt` (see case 2 above).
1530 // Detect references to an upvar `x`:
1531 let cause = match ref_cmt.cat {
1532 mc::cat_upvar(ref upvar_id, _) => {
1533 let mut upvar_borrow_map =
1534 rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1535 match upvar_borrow_map.find_mut(upvar_id) {
1536 Some(upvar_borrow) => {
1537 // Adjust mutability that we infer for the upvar
1538 // so it can accommodate being borrowed with
1539 // mutability `kind`:
1540 adjust_upvar_borrow_kind_for_loan(*upvar_id,
1544 infer::ReborrowUpvar(span, *upvar_id)
1547 rcx.tcx().sess.span_bug(
1549 format!("Illegal upvar id: {}",
1551 rcx.tcx())).as_slice());
1557 infer::Reborrow(span)
1561 debug!("link_reborrowed_region: {} <= {}",
1562 borrow_region.repr(rcx.tcx()),
1563 ref_region.repr(rcx.tcx()));
1564 rcx.fcx.mk_subr(cause, borrow_region, ref_region);
1566 // Decide whether we need to recurse and link any regions within
1567 // the `ref_cmt`. This is concerned for the case where the value
1568 // being reborrowed is in fact a borrowed pointer found within
1569 // another borrowed pointer. For example:
1571 // let p: &'b &'a mut T = ...;
1575 // What makes this case particularly tricky is that, if the data
1576 // being borrowed is a `&mut` or `&uniq` borrow, borrowck requires
1577 // not only that `'z <= 'a`, (as before) but also `'z <= 'b`
1578 // (otherwise the user might mutate through the `&mut T` reference
1579 // after `'b` expires and invalidate the borrow we are looking at
1582 // So let's re-examine our parameters in light of this more
1583 // complicated (possible) scenario:
1585 // A borrow of: `& 'z bk * * p` where `p` has type `&'b bk & 'a bk T`
1586 // borrow_region ^~ ref_region ^~
1587 // borrow_kind ^~ ref_kind ^~
1590 // (Note that since we have not examined `ref_cmt.cat`, we don't
1591 // know whether this scenario has occurred; but I wanted to show
1592 // how all the types get adjusted.)
1595 // The reference being reborrowed is a sharable ref of
1596 // type `&'a T`. In this case, it doesn't matter where we
1597 // *found* the `&T` pointer, the memory it references will
1598 // be valid and immutable for `'a`. So we can stop here.
1600 // (Note that the `borrow_kind` must also be ImmBorrow or
1601 // else the user is borrowed imm memory as mut memory,
1602 // which means they'll get an error downstream in borrowck
1607 ty::MutBorrow | ty::UniqueImmBorrow => {
1608 // The reference being reborrowed is either an `&mut T` or
1609 // `&uniq T`. This is the case where recursion is needed.
1611 // One interesting twist is that we can weaken the borrow
1612 // kind when we recurse: to reborrow an `&mut` referent as
1613 // mutable, borrowck requires a unique path to the `&mut`
1614 // reference but not necessarily a *mutable* path.
1615 let new_borrow_kind = match borrow_kind {
1618 ty::MutBorrow | ty::UniqueImmBorrow =>
1621 return Some((ref_cmt, new_borrow_kind));
1626 fn adjust_borrow_kind_for_assignment_lhs(rcx: &Rcx,
1629 * Adjusts the inferred borrow_kind as needed to account
1630 * for upvars that are assigned to in an assignment
1634 let mc = mc::MemCategorizationContext::new(rcx);
1635 let cmt = ignore_err!(mc.cat_expr(lhs));
1636 adjust_upvar_borrow_kind_for_mut(rcx, cmt);
1639 fn adjust_upvar_borrow_kind_for_mut(rcx: &Rcx,
1642 * Indicates that `cmt` is being directly mutated (e.g., assigned
1643 * to). If cmt contains any by-ref upvars, this implies that
1644 * those upvars must be borrowed using an `&mut` borow.
1649 debug!("adjust_upvar_borrow_kind_for_mut(cmt={})",
1650 cmt.repr(rcx.tcx()));
1652 match cmt.cat.clone() {
1653 mc::cat_deref(base, _, mc::OwnedPtr) |
1654 mc::cat_interior(base, _) |
1655 mc::cat_downcast(base) |
1656 mc::cat_discr(base, _) => {
1657 // Interior or owned data is mutable if base is
1658 // mutable, so iterate to the base.
1663 mc::cat_deref(base, _, mc::BorrowedPtr(..)) |
1664 mc::cat_deref(base, _, mc::Implicit(..)) => {
1666 mc::cat_upvar(ref upvar_id, _) => {
1667 // if this is an implicit deref of an
1668 // upvar, then we need to modify the
1669 // borrow_kind of the upvar to make sure it
1670 // is inferred to mutable if necessary
1671 let mut upvar_borrow_map =
1672 rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1673 let ub = upvar_borrow_map.get_mut(upvar_id);
1674 return adjust_upvar_borrow_kind(*upvar_id, ub, ty::MutBorrow);
1680 // assignment to deref of an `&mut`
1681 // borrowed pointer implies that the
1682 // pointer itself must be unique, but not
1683 // necessarily *mutable*
1684 return adjust_upvar_borrow_kind_for_unique(rcx, base);
1687 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1688 mc::cat_deref(_, _, mc::GcPtr) |
1689 mc::cat_static_item |
1691 mc::cat_copied_upvar(_) |
1694 mc::cat_upvar(..) => {
1701 fn adjust_upvar_borrow_kind_for_unique(rcx: &Rcx, cmt: mc::cmt) {
1704 debug!("adjust_upvar_borrow_kind_for_unique(cmt={})",
1705 cmt.repr(rcx.tcx()));
1707 match cmt.cat.clone() {
1708 mc::cat_deref(base, _, mc::OwnedPtr) |
1709 mc::cat_interior(base, _) |
1710 mc::cat_downcast(base) |
1711 mc::cat_discr(base, _) => {
1712 // Interior or owned data is unique if base is
1718 mc::cat_deref(base, _, mc::BorrowedPtr(..)) |
1719 mc::cat_deref(base, _, mc::Implicit(..)) => {
1721 mc::cat_upvar(ref upvar_id, _) => {
1722 // if this is an implicit deref of an
1723 // upvar, then we need to modify the
1724 // borrow_kind of the upvar to make sure it
1725 // is inferred to unique if necessary
1726 let mut ub = rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1727 let ub = ub.get_mut(upvar_id);
1728 return adjust_upvar_borrow_kind(*upvar_id, ub, ty::UniqueImmBorrow);
1734 // for a borrowed pointer to be unique, its
1735 // base must be unique
1736 return adjust_upvar_borrow_kind_for_unique(rcx, base);
1739 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1740 mc::cat_deref(_, _, mc::GcPtr) |
1741 mc::cat_static_item |
1743 mc::cat_copied_upvar(_) |
1746 mc::cat_upvar(..) => {
1753 fn link_upvar_borrow_kind_for_nested_closures(rcx: &mut Rcx,
1754 inner_upvar_id: ty::UpvarId,
1755 outer_upvar_id: ty::UpvarId) {
1757 * Indicates that the borrow_kind of `outer_upvar_id` must
1758 * permit a reborrowing with the borrow_kind of `inner_upvar_id`.
1759 * This occurs in nested closures, see comment above at the call to
1763 debug!("link_upvar_borrow_kind: inner_upvar_id={:?} outer_upvar_id={:?}",
1764 inner_upvar_id, outer_upvar_id);
1766 let mut upvar_borrow_map = rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1767 let inner_borrow = upvar_borrow_map.get_copy(&inner_upvar_id);
1768 match upvar_borrow_map.find_mut(&outer_upvar_id) {
1769 Some(outer_borrow) => {
1770 adjust_upvar_borrow_kind(outer_upvar_id, outer_borrow, inner_borrow.kind);
1772 None => { /* outer closure is not a stack closure */ }
1776 fn adjust_upvar_borrow_kind_for_loan(upvar_id: ty::UpvarId,
1777 upvar_borrow: &mut ty::UpvarBorrow,
1778 kind: ty::BorrowKind) {
1779 debug!("adjust_upvar_borrow_kind_for_loan: upvar_id={:?} kind={:?} -> {:?}",
1780 upvar_id, upvar_borrow.kind, kind);
1782 adjust_upvar_borrow_kind(upvar_id, upvar_borrow, kind)
1785 fn adjust_upvar_borrow_kind(upvar_id: ty::UpvarId,
1786 upvar_borrow: &mut ty::UpvarBorrow,
1787 kind: ty::BorrowKind) {
1789 * We infer the borrow_kind with which to borrow upvars in a stack
1790 * closure. The borrow_kind basically follows a lattice of
1791 * `imm < unique-imm < mut`, moving from left to right as needed (but never
1792 * right to left). Here the argument `mutbl` is the borrow_kind that
1793 * is required by some particular use.
1796 debug!("adjust_upvar_borrow_kind: id={:?} kind=({:?} -> {:?})",
1797 upvar_id, upvar_borrow.kind, kind);
1799 match (upvar_borrow.kind, kind) {
1801 (ty::ImmBorrow, ty::UniqueImmBorrow) |
1802 (ty::ImmBorrow, ty::MutBorrow) |
1803 (ty::UniqueImmBorrow, ty::MutBorrow) => {
1804 upvar_borrow.kind = kind;
1807 (ty::ImmBorrow, ty::ImmBorrow) |
1808 (ty::UniqueImmBorrow, ty::ImmBorrow) |
1809 (ty::UniqueImmBorrow, ty::UniqueImmBorrow) |
1810 (ty::MutBorrow, _) => {
1815 fn type_must_outlive(rcx: &mut Rcx,
1816 origin: infer::SubregionOrigin,
1821 * Ensures that all borrowed data reachable via `ty` outlives `region`.
1824 debug!("type_must_outlive(ty={}, region={})",
1826 region.repr(rcx.tcx()));
1829 regionmanip::region_wf_constraints(
1833 for constraint in constraints.iter() {
1834 debug!("constraint: {}", constraint.repr(rcx.tcx()));
1836 regionmanip::RegionSubRegionConstraint(None, r_a, r_b) => {
1837 rcx.fcx.mk_subr(origin.clone(), r_a, r_b);
1839 regionmanip::RegionSubRegionConstraint(Some(ty), r_a, r_b) => {
1840 let o1 = infer::ReferenceOutlivesReferent(ty, origin.span());
1841 rcx.fcx.mk_subr(o1, r_a, r_b);
1843 regionmanip::RegionSubParamConstraint(None, r_a, param_b) => {
1844 param_must_outlive(rcx, origin.clone(), r_a, param_b);
1846 regionmanip::RegionSubParamConstraint(Some(ty), r_a, param_b) => {
1847 let o1 = infer::ReferenceOutlivesReferent(ty, origin.span());
1848 param_must_outlive(rcx, o1, r_a, param_b);
1854 fn param_must_outlive(rcx: &Rcx,
1855 origin: infer::SubregionOrigin,
1857 param_ty: ty::ParamTy) {
1858 let param_env = &rcx.fcx.inh.param_env;
1860 debug!("param_must_outlive(region={}, param_ty={})",
1861 region.repr(rcx.tcx()),
1862 param_ty.repr(rcx.tcx()));
1864 // Collect all regions that `param_ty` is known to outlive into
1866 let mut param_bounds;
1868 // To start, collect bounds from user:
1869 let param_bound = param_env.bounds.get(param_ty.space, param_ty.idx);
1871 ty::required_region_bounds(rcx.tcx(),
1872 param_bound.opt_region_bound.as_slice(),
1873 param_bound.builtin_bounds,
1874 param_bound.trait_bounds.as_slice());
1876 // Collect default bound of fn body that applies to all in scope
1878 param_bounds.push(param_env.implicit_region_bound);
1880 // Finally, collect regions we scraped from the well-formedness
1881 // constraints in the fn signature. To do that, we walk the list
1882 // of known relations from the fn ctxt.
1884 // This is crucial because otherwise code like this fails:
1886 // fn foo<'a, A>(x: &'a A) { x.bar() }
1888 // The problem is that the type of `x` is `&'a A`. To be
1889 // well-formed, then, A must be lower-bounded by `'a`, but we
1890 // don't know that this holds from first principles.
1891 for &(ref r, ref p) in rcx.region_param_pairs.iter() {
1892 debug!("param_ty={}/{} p={}/{}",
1893 param_ty.repr(rcx.tcx()),
1898 param_bounds.push(*r);
1902 // Inform region inference that this parameter type must be
1903 // properly bounded.
1904 infer::verify_param_bound(rcx.fcx.infcx(),