1 // Copyright 2012 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::freevars;
123 use mc = middle::mem_categorization;
124 use middle::ty::{ReScope};
126 use middle::typeck::astconv::AstConv;
127 use middle::typeck::check::FnCtxt;
128 use middle::typeck::check::regionmanip::relate_nested_regions;
129 use middle::typeck::infer::resolve_and_force_all_but_regions;
130 use middle::typeck::infer::resolve_type;
131 use middle::typeck::infer;
132 use middle::pat_util;
133 use util::ppaux::{ty_to_str, region_to_str, Repr};
135 use syntax::ast::{ManagedSigil, OwnedSigil, BorrowedSigil};
136 use syntax::ast::{DefArg, DefBinding, DefLocal, DefUpvar};
138 use syntax::ast_util;
139 use syntax::codemap::Span;
141 use syntax::visit::Visitor;
145 errors_reported: uint,
147 // id of innermost fn or loop
148 repeating_scope: ast::NodeId,
151 fn region_of_def(fcx: @FnCtxt, def: ast::Def) -> ty::Region {
153 * Returns the validity region of `def` -- that is, how long
159 DefLocal(node_id, _) | DefArg(node_id, _) |
160 DefBinding(node_id, _) => {
161 tcx.region_maps.var_region(node_id)
163 DefUpvar(_, subdef, closure_id, body_id) => {
164 match ty::ty_closure_sigil(fcx.node_ty(closure_id)) {
165 BorrowedSigil => region_of_def(fcx, *subdef),
166 ManagedSigil | OwnedSigil => ReScope(body_id)
170 tcx.sess.bug(format!("unexpected def in region_of_def: {:?}",
177 pub fn tcx(&self) -> ty::ctxt {
181 pub fn set_repeating_scope(&mut self, scope: ast::NodeId) -> ast::NodeId {
182 let old_scope = self.repeating_scope;
183 self.repeating_scope = scope;
187 pub fn resolve_type(&mut self, unresolved_ty: ty::t) -> ty::t {
189 * Try to resolve the type for the given node, returning
190 * t_err if an error results. Note that we never care
191 * about the details of the error, the same error will be
192 * detected and reported in the writeback phase.
194 * Note one important point: we do not attempt to resolve
195 * *region variables* here. This is because regionck is
196 * essentially adding constraints to those region variables
197 * and so may yet influence how they are resolved.
199 * Consider this silly example:
201 * fn borrow(x: &int) -> &int {x}
202 * fn foo(x: @int) -> int { // block: B
203 * let b = borrow(x); // region: <R0>
207 * Here, the region of `b` will be `<R0>`. `<R0>` is
208 * constrainted to be some subregion of the block B and some
209 * superregion of the call. If we forced it now, we'd choose
210 * the smaller region (the call). But that would make the *b
211 * illegal. Since we don't resolve, the type of b will be
212 * `&<R0>.int` and then `*b` will require that `<R0>` be
213 * bigger than the let and the `*b` expression, so we will
214 * effectively resolve `<R0>` to be the block B.
216 match resolve_type(self.fcx.infcx(), unresolved_ty,
217 resolve_and_force_all_but_regions) {
219 Err(_) => ty::mk_err()
223 /// Try to resolve the type for the given node.
224 pub fn resolve_node_type(&mut self, id: ast::NodeId) -> ty::t {
225 let t = self.fcx.node_ty(id);
229 /// Try to resolve the callee type for the given method call.
230 pub fn resolve_method_type(&mut self, id: ast::NodeId) -> ty::t {
231 let t = self.fcx.method_ty(id);
235 /// Try to resolve the type for the given node.
236 pub fn resolve_expr_type_adjusted(&mut self, expr: &ast::Expr) -> ty::t {
237 let ty_unadjusted = self.resolve_node_type(expr.id);
238 if ty::type_is_error(ty_unadjusted) || ty::type_is_bot(ty_unadjusted) {
241 let tcx = self.fcx.tcx();
243 let adjustments = self.fcx.inh.adjustments.borrow();
244 adjustments.get().find_copy(&expr.id)
246 ty::adjust_ty(tcx, expr.span, ty_unadjusted, adjustment)
251 impl<'a> mc::Typer for &'a mut Rcx {
252 fn tcx(&self) -> ty::ctxt {
256 fn node_ty(&mut self, id: ast::NodeId) -> mc::McResult<ty::t> {
257 let t = self.resolve_node_type(id);
258 if ty::type_is_error(t) {Err(())} else {Ok(t)}
261 fn adjustment(&mut self, id: ast::NodeId) -> Option<@ty::AutoAdjustment> {
262 let adjustments = self.fcx.inh.adjustments.borrow();
263 adjustments.get().find_copy(&id)
266 fn is_method_call(&mut self, id: ast::NodeId) -> bool {
267 let method_map = self.fcx.inh.method_map.borrow();
268 method_map.get().contains_key(&id)
271 fn temporary_scope(&mut self, id: ast::NodeId) -> Option<ast::NodeId> {
272 self.tcx().region_maps.temporary_scope(id)
275 fn upvar_borrow(&mut self, id: ty::UpvarId) -> ty::UpvarBorrow {
276 let upvar_borrow_map = self.fcx.inh.upvar_borrow_map.borrow();
277 upvar_borrow_map.get().get_copy(&id)
281 pub fn regionck_expr(fcx: @FnCtxt, e: &ast::Expr) {
282 let mut rcx = Rcx { fcx: fcx, errors_reported: 0,
283 repeating_scope: e.id };
285 if fcx.err_count_since_creation() == 0 {
286 // regionck assumes typeck succeeded
287 rcx.visit_expr(e, ());
289 fcx.infcx().resolve_regions();
292 pub fn regionck_fn(fcx: @FnCtxt, blk: &ast::Block) {
293 let mut rcx = Rcx { fcx: fcx, errors_reported: 0,
294 repeating_scope: blk.id };
296 if fcx.err_count_since_creation() == 0 {
297 // regionck assumes typeck succeeded
298 rcx.visit_block(blk, ());
300 fcx.infcx().resolve_regions();
303 impl Visitor<()> for Rcx {
304 // (..) FIXME(#3238) should use visit_pat, not visit_arm/visit_local,
305 // However, right now we run into an issue whereby some free
306 // regions are not properly related if they appear within the
307 // types of arguments that must be inferred. This could be
308 // addressed by deferring the construction of the region
309 // hierarchy, and in particular the relationships between free
310 // regions, until regionck, as described in #3238.
312 fn visit_item(&mut self, i: &ast::Item, _: ()) { visit_item(self, i); }
314 fn visit_expr(&mut self, ex: &ast::Expr, _: ()) { visit_expr(self, ex); }
316 //visit_pat: visit_pat, // (..) see above
318 fn visit_arm(&mut self, a: &ast::Arm, _: ()) { visit_arm(self, a); }
320 fn visit_local(&mut self, l: &ast::Local, _: ()) { visit_local(self, l); }
322 fn visit_block(&mut self, b: &ast::Block, _: ()) { visit_block(self, b); }
325 fn visit_item(_rcx: &mut Rcx, _item: &ast::Item) {
329 fn visit_block(rcx: &mut Rcx, b: &ast::Block) {
330 visit::walk_block(rcx, b, ());
333 fn visit_arm(rcx: &mut Rcx, arm: &ast::Arm) {
335 for &p in arm.pats.iter() {
336 constrain_bindings_in_pat(p, rcx);
339 visit::walk_arm(rcx, arm, ());
342 fn visit_local(rcx: &mut Rcx, l: &ast::Local) {
344 constrain_bindings_in_pat(l.pat, rcx);
346 visit::walk_local(rcx, l, ());
349 fn constrain_bindings_in_pat(pat: &ast::Pat, rcx: &mut Rcx) {
350 let tcx = rcx.fcx.tcx();
351 debug!("regionck::visit_pat(pat={})", pat.repr(tcx));
352 pat_util::pat_bindings(tcx.def_map, pat, |_, id, span, _| {
353 // If we have a variable that contains region'd data, that
354 // data will be accessible from anywhere that the variable is
355 // accessed. We must be wary of loops like this:
357 // // from src/test/compile-fail/borrowck-lend-flow.rs
358 // let mut v = ~3, w = ~4;
359 // let mut x = &mut w;
362 // borrow(v); //~ ERROR cannot borrow
363 // x = &mut v; // (1)
366 // Typically, we try to determine the region of a borrow from
367 // those points where it is dereferenced. In this case, one
368 // might imagine that the lifetime of `x` need only be the
369 // body of the loop. But of course this is incorrect because
370 // the pointer that is created at point (1) is consumed at
371 // point (2), meaning that it must be live across the loop
372 // iteration. The easiest way to guarantee this is to require
373 // that the lifetime of any regions that appear in a
374 // variable's type enclose at least the variable's scope.
376 let var_region = tcx.region_maps.var_region(id);
377 constrain_regions_in_type_of_node(
379 infer::BindingTypeIsNotValidAtDecl(span));
383 fn visit_expr(rcx: &mut Rcx, expr: &ast::Expr) {
384 debug!("regionck::visit_expr(e={}, repeating_scope={:?})",
385 expr.repr(rcx.fcx.tcx()), rcx.repeating_scope);
387 let has_method_map = rcx.fcx.inh.method_map.get().contains_key(&expr.id);
389 // Check any autoderefs or autorefs that appear.
391 let adjustments = rcx.fcx.inh.adjustments.borrow();
392 let r = adjustments.get().find(&expr.id);
393 for &adjustment in r.iter() {
394 debug!("adjustment={:?}", adjustment);
397 ty::AutoDerefRef {autoderefs: autoderefs, autoref: opt_autoref}) =>
399 let expr_ty = rcx.resolve_node_type(expr.id);
400 constrain_derefs(rcx, expr, autoderefs, expr_ty);
401 for autoref in opt_autoref.iter() {
402 link_autoref(rcx, expr, autoderefs, autoref);
404 // Require that the resulting region encompasses
407 // FIXME(#6268) remove to support nested method calls
408 constrain_regions_in_type_of_node(
409 rcx, expr.id, ty::ReScope(expr.id),
410 infer::AutoBorrow(expr.span));
413 ty::AutoObject(ast::BorrowedSigil, Some(trait_region), _, _, _, _) => {
414 // Determine if we are casting `expr` to an trait
415 // instance. If so, we have to be sure that the type of
416 // the source obeys the trait's region bound.
418 // Note: there is a subtle point here concerning type
419 // parameters. It is possible that the type of `source`
420 // contains type parameters, which in turn may contain
421 // regions that are not visible to us (only the caller
422 // knows about them). The kind checker is ultimately
423 // responsible for guaranteeing region safety in that
424 // particular case. There is an extensive comment on the
425 // function check_cast_for_escaping_regions() in kind.rs
426 // explaining how it goes about doing that.
428 let source_ty = rcx.fcx.expr_ty(expr);
429 constrain_regions_in_type(rcx, trait_region,
430 infer::RelateObjectBound(expr.span), source_ty);
438 ast::ExprCall(callee, ref args) => {
439 constrain_callee(rcx, callee.id, expr, callee);
447 visit::walk_expr(rcx, expr, ());
450 ast::ExprMethodCall(_, _, ref args) => {
451 constrain_call(rcx, None, expr, Some(*args.get(0)),
452 args.slice_from(1), false);
454 visit::walk_expr(rcx, expr, ());
457 ast::ExprAssign(lhs, _) => {
458 adjust_borrow_kind_for_assignment_lhs(rcx, lhs);
459 visit::walk_expr(rcx, expr, ());
462 ast::ExprAssignOp(_, lhs, rhs) => {
464 constrain_call(rcx, None, expr, Some(lhs), [rhs], true);
467 adjust_borrow_kind_for_assignment_lhs(rcx, lhs);
469 visit::walk_expr(rcx, expr, ());
472 ast::ExprIndex(lhs, rhs) |
473 ast::ExprBinary(_, lhs, rhs) if has_method_map => {
474 // As `expr_method_call`, but the call is via an
475 // overloaded op. Note that we (sadly) currently use an
476 // implicit "by ref" sort of passing style here. This
477 // should be converted to an adjustment!
478 constrain_call(rcx, None, expr, Some(lhs), [rhs], true);
480 visit::walk_expr(rcx, expr, ());
483 ast::ExprUnary(_, lhs) if has_method_map => {
485 constrain_call(rcx, None, expr, Some(lhs), [], true);
487 visit::walk_expr(rcx, expr, ());
490 ast::ExprUnary(ast::UnDeref, base) => {
491 // For *a, the lifetime of a must enclose the deref
492 let base_ty = rcx.resolve_node_type(base.id);
493 constrain_derefs(rcx, expr, 1, base_ty);
495 visit::walk_expr(rcx, expr, ());
498 ast::ExprIndex(vec_expr, _) => {
499 // For a[b], the lifetime of a must enclose the deref
500 let vec_type = rcx.resolve_expr_type_adjusted(vec_expr);
501 constrain_index(rcx, expr, vec_type);
503 visit::walk_expr(rcx, expr, ());
506 ast::ExprCast(source, _) => {
507 // Determine if we are casting `source` to an trait
508 // instance. If so, we have to be sure that the type of
509 // the source obeys the trait's region bound.
511 // Note: there is a subtle point here concerning type
512 // parameters. It is possible that the type of `source`
513 // contains type parameters, which in turn may contain
514 // regions that are not visible to us (only the caller
515 // knows about them). The kind checker is ultimately
516 // responsible for guaranteeing region safety in that
517 // particular case. There is an extensive comment on the
518 // function check_cast_for_escaping_regions() in kind.rs
519 // explaining how it goes about doing that.
520 let target_ty = rcx.resolve_node_type(expr.id);
521 match ty::get(target_ty).sty {
522 ty::ty_trait(_, _, ty::RegionTraitStore(trait_region), _, _) => {
523 let source_ty = rcx.resolve_expr_type_adjusted(source);
524 constrain_regions_in_type(
527 infer::RelateObjectBound(expr.span),
533 visit::walk_expr(rcx, expr, ());
536 ast::ExprAddrOf(m, base) => {
537 link_addr_of(rcx, expr, m, base);
539 // Require that when you write a `&expr` expression, the
540 // resulting pointer has a lifetime that encompasses the
541 // `&expr` expression itself. Note that we constraining
542 // the type of the node expr.id here *before applying
545 // FIXME(#6268) nested method calls requires that this rule change
546 let ty0 = rcx.resolve_node_type(expr.id);
547 constrain_regions_in_type(rcx, ty::ReScope(expr.id),
548 infer::AddrOf(expr.span), ty0);
549 visit::walk_expr(rcx, expr, ());
552 ast::ExprMatch(discr, ref arms) => {
553 link_match(rcx, discr, arms.as_slice());
555 visit::walk_expr(rcx, expr, ());
558 ast::ExprFnBlock(_, ref body) | ast::ExprProc(_, ref body) => {
559 check_expr_fn_block(rcx, expr, &**body);
562 ast::ExprLoop(body, _) => {
563 let repeating_scope = rcx.set_repeating_scope(body.id);
564 visit::walk_expr(rcx, expr, ());
565 rcx.set_repeating_scope(repeating_scope);
568 ast::ExprWhile(cond, body) => {
569 let repeating_scope = rcx.set_repeating_scope(cond.id);
570 rcx.visit_expr(cond, ());
572 rcx.set_repeating_scope(body.id);
573 rcx.visit_block(body, ());
575 rcx.set_repeating_scope(repeating_scope);
579 visit::walk_expr(rcx, expr, ());
584 fn check_expr_fn_block(rcx: &mut Rcx,
587 let tcx = rcx.fcx.tcx();
588 let function_type = rcx.resolve_node_type(expr.id);
589 match ty::get(function_type).sty {
590 ty::ty_closure(ty::ClosureTy {
591 sigil: ast::BorrowedSigil, region: region, ..}) => {
592 let freevars = freevars::get_freevars(tcx, expr.id);
593 if freevars.is_empty() {
594 // No free variables means that the environment
595 // will be NULL at runtime and hence the closure
596 // has static lifetime.
598 // Closure must not outlive the variables it closes over.
599 constrain_free_variables(rcx, region, expr, freevars);
601 // Closure cannot outlive the appropriate temporary scope.
602 let s = rcx.repeating_scope;
603 rcx.fcx.mk_subr(true, infer::InfStackClosure(expr.span),
604 region, ty::ReScope(s));
610 let repeating_scope = rcx.set_repeating_scope(body.id);
611 visit::walk_expr(rcx, expr, ());
612 rcx.set_repeating_scope(repeating_scope);
614 match ty::get(function_type).sty {
615 ty::ty_closure(ty::ClosureTy {sigil: ast::BorrowedSigil, ..}) => {
616 let freevars = freevars::get_freevars(tcx, expr.id);
617 propagate_upupvar_borrow_kind(rcx, expr, freevars);
622 fn constrain_free_variables(rcx: &mut Rcx,
625 freevars: freevars::freevar_info) {
627 * Make sure that all free variables referenced inside the closure
628 * outlive the closure itself. Also, create an entry in the
629 * upvar_borrows map with a region.
632 let tcx = rcx.fcx.ccx.tcx;
633 let infcx = rcx.fcx.infcx();
634 debug!("constrain_free_variables({}, {})",
635 region.repr(tcx), expr.repr(tcx));
636 for freevar in freevars.iter() {
637 debug!("freevar def is {:?}", freevar.def);
639 // Identify the variable being closed over and its node-id.
640 let def = freevar.def;
641 let def_id = ast_util::def_id_of_def(def);
642 assert!(def_id.krate == ast::LOCAL_CRATE);
643 let upvar_id = ty::UpvarId { var_id: def_id.node,
644 closure_expr_id: expr.id };
646 // Create a region variable to represent this borrow. This borrow
647 // must outlive the region on the closure.
648 let origin = infer::UpvarRegion(upvar_id, expr.span);
649 let freevar_region = infcx.next_region_var(origin);
650 rcx.fcx.mk_subr(true, infer::FreeVariable(freevar.span, def_id.node),
651 region, freevar_region);
653 // Create a UpvarBorrow entry. Note that we begin with a
654 // const borrow_kind, but change it to either mut or
655 // immutable as dictated by the uses.
656 let upvar_borrow = ty::UpvarBorrow { kind: ty::ImmBorrow,
657 region: freevar_region };
658 let mut upvar_borrow_map = rcx.fcx.inh.upvar_borrow_map.borrow_mut();
659 upvar_borrow_map.get().insert(upvar_id, upvar_borrow);
661 // Guarantee that the closure does not outlive the variable itself.
662 let en_region = region_of_def(rcx.fcx, def);
663 debug!("en_region = {}", en_region.repr(tcx));
664 rcx.fcx.mk_subr(true, infer::FreeVariable(freevar.span, def_id.node),
669 fn propagate_upupvar_borrow_kind(rcx: &mut Rcx,
671 freevars: freevars::freevar_info) {
672 let tcx = rcx.fcx.ccx.tcx;
673 debug!("propagate_upupvar_borrow_kind({})", expr.repr(tcx));
674 for freevar in freevars.iter() {
675 // Because of the semi-hokey way that we are doing
676 // borrow_kind inference, we need to check for
677 // indirect dependencies, like so:
686 // Here, the `inner_call` is basically "reborrowing" the
687 // outer pointer. With no other changes, `inner_call`
688 // would infer that it requires a mutable borrow, but
689 // `outer_call` would infer that a const borrow is
690 // sufficient. This is because we haven't linked the
691 // borrow_kind of the borrow that occurs in the inner
692 // closure to the borrow_kind of the borrow in the outer
693 // closure. Note that regions *are* naturally linked
694 // because we have a proper inference scheme there.
696 // Anyway, for borrow_kind, we basically go back over now
697 // after checking the inner closure (and hence
698 // determining the final borrow_kind) and propagate that as
699 // a constraint on the outer closure.
701 ast::DefUpvar(var_id, _, outer_closure_id, _) => {
702 // thing being captured is itself an upvar:
703 let outer_upvar_id = ty::UpvarId {
705 closure_expr_id: outer_closure_id };
706 let inner_upvar_id = ty::UpvarId {
708 closure_expr_id: expr.id };
709 link_upvar_borrow_kind_for_nested_closures(rcx,
719 fn constrain_callee(rcx: &mut Rcx,
720 callee_id: ast::NodeId,
721 call_expr: &ast::Expr,
722 callee_expr: &ast::Expr) {
723 let call_region = ty::ReScope(call_expr.id);
725 let callee_ty = rcx.resolve_node_type(callee_id);
726 match ty::get(callee_ty).sty {
727 ty::ty_bare_fn(..) => { }
728 ty::ty_closure(ref closure_ty) => {
729 rcx.fcx.mk_subr(true, infer::InvokeClosure(callee_expr.span),
730 call_region, closure_ty.region);
733 // this should not happen, but it does if the program is
736 // tcx.sess.span_bug(
738 // format!("Calling non-function: {}", callee_ty.repr(tcx)));
743 fn constrain_call(rcx: &mut Rcx,
744 // might be expr_call, expr_method_call, or an overloaded
746 fn_expr_id: Option<ast::NodeId>,
747 call_expr: &ast::Expr,
748 receiver: Option<@ast::Expr>,
749 arg_exprs: &[@ast::Expr],
750 implicitly_ref_args: bool) {
751 //! Invoked on every call site (i.e., normal calls, method calls,
752 //! and overloaded operators). Constrains the regions which appear
753 //! in the type of the function. Also constrains the regions that
754 //! appear in the arguments appropriately.
756 let tcx = rcx.fcx.tcx();
757 debug!("constrain_call(call_expr={}, \
760 implicitly_ref_args={:?})",
764 implicitly_ref_args);
765 let callee_ty = match fn_expr_id {
766 Some(id) => rcx.resolve_node_type(id),
767 None => rcx.resolve_method_type(call_expr.id)
769 if ty::type_is_error(callee_ty) {
770 // Bail, as function type is unknown
773 let fn_sig = ty::ty_fn_sig(callee_ty);
775 // `callee_region` is the scope representing the time in which the
778 // FIXME(#6268) to support nested method calls, should be callee_id
779 let callee_scope = call_expr.id;
780 let callee_region = ty::ReScope(callee_scope);
782 for &arg_expr in arg_exprs.iter() {
785 // ensure that any regions appearing in the argument type are
786 // valid for at least the lifetime of the function:
787 constrain_regions_in_type_of_node(
788 rcx, arg_expr.id, callee_region,
789 infer::CallArg(arg_expr.span));
791 // unfortunately, there are two means of taking implicit
792 // references, and we need to propagate constraints as a
793 // result. modes are going away and the "DerefArgs" code
794 // should be ported to use adjustments
795 if implicitly_ref_args {
796 link_by_ref(rcx, arg_expr, callee_scope);
800 // as loop above, but for receiver
801 for &r in receiver.iter() {
803 constrain_regions_in_type_of_node(
804 rcx, r.id, callee_region, infer::CallRcvr(r.span));
805 if implicitly_ref_args {
806 link_by_ref(rcx, r, callee_scope);
810 // constrain regions that may appear in the return type to be
811 // valid for the function call:
812 constrain_regions_in_type(
813 rcx, callee_region, infer::CallReturn(call_expr.span),
817 fn constrain_derefs(rcx: &mut Rcx,
818 deref_expr: &ast::Expr,
820 mut derefd_ty: ty::t)
823 * Invoked on any dereference that occurs, whether explicitly
824 * or through an auto-deref. Checks that if this is a region
825 * pointer being derefenced, the lifetime of the pointer includes
828 let r_deref_expr = ty::ReScope(deref_expr.id);
829 for i in range(0u, derefs) {
830 debug!("constrain_derefs(deref_expr=?, derefd_ty={}, derefs={:?}/{:?}",
831 rcx.fcx.infcx().ty_to_str(derefd_ty),
834 match ty::get(derefd_ty).sty {
835 ty::ty_rptr(r_ptr, _) => {
836 mk_subregion_due_to_derefence(rcx, deref_expr.span,
837 r_deref_expr, r_ptr);
843 match ty::deref(derefd_ty, true) {
844 Some(mt) => derefd_ty = mt.ty,
845 /* if this type can't be dereferenced, then there's already an error
846 in the session saying so. Just bail out for now */
852 pub fn mk_subregion_due_to_derefence(rcx: &mut Rcx,
854 minimum_lifetime: ty::Region,
855 maximum_lifetime: ty::Region) {
856 rcx.fcx.mk_subr(true, infer::DerefPointer(deref_span),
857 minimum_lifetime, maximum_lifetime)
861 fn constrain_index(rcx: &mut Rcx,
862 index_expr: &ast::Expr,
866 * Invoked on any index expression that occurs. Checks that if
867 * this is a slice being indexed, the lifetime of the pointer
868 * includes the deref expr.
871 debug!("constrain_index(index_expr=?, indexed_ty={}",
872 rcx.fcx.infcx().ty_to_str(indexed_ty));
874 let r_index_expr = ty::ReScope(index_expr.id);
875 match ty::get(indexed_ty).sty {
876 ty::ty_str(ty::vstore_slice(r_ptr)) |
877 ty::ty_vec(_, ty::vstore_slice(r_ptr)) => {
878 rcx.fcx.mk_subr(true, infer::IndexSlice(index_expr.span),
879 r_index_expr, r_ptr);
886 fn constrain_regions_in_type_of_node(
889 minimum_lifetime: ty::Region,
890 origin: infer::SubregionOrigin) -> bool
892 //! Guarantees that any lifetimes which appear in the type of
893 //! the node `id` (after applying adjustments) are valid for at
894 //! least `minimum_lifetime`
896 let tcx = rcx.fcx.tcx();
898 // Try to resolve the type. If we encounter an error, then typeck
899 // is going to fail anyway, so just stop here and let typeck
900 // report errors later on in the writeback phase.
901 let ty0 = rcx.resolve_node_type(id);
903 let adjustments = rcx.fcx.inh.adjustments.borrow();
904 adjustments.get().find_copy(&id)
906 let ty = ty::adjust_ty(tcx, origin.span(), ty0, adjustment);
907 debug!("constrain_regions_in_type_of_node(\
908 ty={}, ty0={}, id={}, minimum_lifetime={:?}, adjustment={:?})",
909 ty_to_str(tcx, ty), ty_to_str(tcx, ty0),
910 id, minimum_lifetime, adjustment);
911 constrain_regions_in_type(rcx, minimum_lifetime, origin, ty)
914 fn constrain_regions_in_type(
916 minimum_lifetime: ty::Region,
917 origin: infer::SubregionOrigin,
921 * Requires that any regions which appear in `ty` must be
922 * superregions of `minimum_lifetime`. Also enforces the constraint
923 * that given a pointer type `&'r T`, T must not contain regions
924 * that outlive 'r, as well as analogous constraints for other
927 * This check prevents regions from being used outside of the block in
928 * which they are valid. Recall that regions represent blocks of
929 * code or expressions: this requirement basically says "any place
930 * that uses or may use a region R must be within the block of
931 * code that R corresponds to."
934 let e = rcx.errors_reported;
935 let tcx = rcx.fcx.ccx.tcx;
937 debug!("constrain_regions_in_type(minimum_lifetime={}, ty={})",
938 region_to_str(tcx, "", false, minimum_lifetime),
941 relate_nested_regions(tcx, Some(minimum_lifetime), ty, |r_sub, r_sup| {
942 debug!("relate_nested_regions(r_sub={}, r_sup={})",
946 if r_sup.is_bound() || r_sub.is_bound() {
947 // a bound region is one which appears inside an fn type.
948 // (e.g., the `&` in `fn(&T)`). Such regions need not be
949 // constrained by `minimum_lifetime` as they are placeholders
950 // for regions that are as-yet-unknown.
951 } else if r_sub == minimum_lifetime {
957 true, infer::ReferenceOutlivesReferent(ty, origin.span()),
962 return e == rcx.errors_reported;
965 // If mem categorization results in an error, it's because the type
966 // check failed (or will fail, when the error is uncovered and
967 // reported during writeback). In this case, we just ignore this part
968 // of the code and don't try to add any more region constraints.
969 macro_rules! ignore_err(
973 Err(()) => { return; }
978 fn link_addr_of(rcx: &mut Rcx, expr: &ast::Expr,
979 mutability: ast::Mutability, base: &ast::Expr) {
981 * Computes the guarantor for an expression `&base` and then
982 * ensures that the lifetime of the resulting pointer is linked
983 * to the lifetime of its guarantor (if any).
986 debug!("link_addr_of(base=?)");
989 let mut mc = mc::MemCategorizationContext { typer: &mut *rcx };
990 ignore_err!(mc.cat_expr(base))
992 link_region_from_node_type(rcx, expr.span, expr.id, mutability, cmt);
995 fn link_local(rcx: &mut Rcx, local: &ast::Local) {
997 * Computes the guarantors for any ref bindings in a `let` and
998 * then ensures that the lifetime of the resulting pointer is
999 * linked to the lifetime of the initialization expression.
1002 debug!("regionck::for_local()");
1003 let init_expr = match local.init {
1007 let mut mc = mc::MemCategorizationContext { typer: rcx };
1008 let discr_cmt = ignore_err!(mc.cat_expr(init_expr));
1009 link_pattern(&mut mc, discr_cmt, local.pat);
1012 fn link_match(rcx: &mut Rcx, discr: &ast::Expr, arms: &[ast::Arm]) {
1014 * Computes the guarantors for any ref bindings in a match and
1015 * then ensures that the lifetime of the resulting pointer is
1016 * linked to the lifetime of its guarantor (if any).
1019 debug!("regionck::for_match()");
1020 let mut mc = mc::MemCategorizationContext { typer: rcx };
1021 let discr_cmt = ignore_err!(mc.cat_expr(discr));
1022 debug!("discr_cmt={}", discr_cmt.repr(mc.typer.tcx()));
1023 for arm in arms.iter() {
1024 for &root_pat in arm.pats.iter() {
1025 link_pattern(&mut mc, discr_cmt, root_pat);
1030 fn link_pattern(mc: &mut mc::MemCategorizationContext<&mut Rcx>,
1032 root_pat: @ast::Pat) {
1034 * Link lifetimes of any ref bindings in `root_pat` to
1035 * the pointers found in the discriminant, if needed.
1038 let _ = mc.cat_pattern(discr_cmt, root_pat, |mc, sub_cmt, sub_pat| {
1039 match sub_pat.node {
1041 ast::PatIdent(ast::BindByRef(mutbl), _, _) => {
1042 link_region_from_node_type(
1043 mc.typer, sub_pat.span, sub_pat.id,
1047 // `[_, ..slice, _]` pattern
1048 ast::PatVec(_, Some(slice_pat), _) => {
1049 match mc.cat_slice_pattern(sub_cmt, slice_pat) {
1050 Ok((slice_cmt, slice_mutbl, slice_r)) => {
1051 link_region(mc.typer, sub_pat.span, slice_r,
1052 slice_mutbl, slice_cmt);
1062 fn link_autoref(rcx: &mut Rcx,
1065 autoref: &ty::AutoRef) {
1067 * Link lifetime of borrowed pointer resulting from autoref
1068 * to lifetimes in the value being autoref'd.
1071 debug!("link_autoref(autoref={:?})", autoref);
1072 let mut mc = mc::MemCategorizationContext { typer: rcx };
1073 let expr_cmt = ignore_err!(mc.cat_expr_autoderefd(expr, autoderefs));
1074 debug!("expr_cmt={}", expr_cmt.repr(mc.typer.tcx()));
1077 ty::AutoPtr(r, m) => {
1078 link_region(mc.typer, expr.span, r, m, expr_cmt);
1081 ty::AutoBorrowVec(r, m) | ty::AutoBorrowVecRef(r, m) => {
1082 let cmt_index = mc.cat_index(expr, expr_cmt, autoderefs+1);
1083 link_region(mc.typer, expr.span, r, m, cmt_index);
1086 ty::AutoBorrowFn(r) => {
1087 let cmt_deref = mc.cat_deref_fn_or_obj(expr, expr_cmt, 0);
1088 link_region(mc.typer, expr.span, r, ast::MutImmutable, cmt_deref);
1091 ty::AutoBorrowObj(r, m) => {
1092 let cmt_deref = mc.cat_deref_fn_or_obj(expr, expr_cmt, 0);
1093 link_region(mc.typer, expr.span, r, m, cmt_deref);
1096 ty::AutoUnsafe(_) => {}
1100 fn link_by_ref(rcx: &mut Rcx,
1102 callee_scope: ast::NodeId) {
1104 * Computes the guarantor for cases where the `expr` is
1105 * being passed by implicit reference and must outlive
1109 let tcx = rcx.tcx();
1110 debug!("link_by_ref(expr={}, callee_scope={})",
1111 expr.repr(tcx), callee_scope);
1112 let mut mc = mc::MemCategorizationContext { typer: rcx };
1113 let expr_cmt = ignore_err!(mc.cat_expr(expr));
1114 let region_min = ty::ReScope(callee_scope);
1115 link_region(mc.typer, expr.span, region_min, ast::MutImmutable, expr_cmt);
1118 fn link_region_from_node_type(rcx: &mut Rcx,
1121 mutbl: ast::Mutability,
1122 cmt_borrowed: mc::cmt) {
1124 * Like `link_region()`, except that the region is
1125 * extracted from the type of `id`, which must be some
1126 * reference (`&T`, `&str`, etc).
1129 let rptr_ty = rcx.resolve_node_type(id);
1130 if !ty::type_is_bot(rptr_ty) && !ty::type_is_error(rptr_ty) {
1131 let tcx = rcx.fcx.ccx.tcx;
1132 debug!("rptr_ty={}", ty_to_str(tcx, rptr_ty));
1133 let r = ty::ty_region(tcx, span, rptr_ty);
1134 link_region(rcx, span, r, mutbl, cmt_borrowed);
1138 fn link_region(rcx: &mut Rcx,
1140 region_min: ty::Region,
1141 mutbl: ast::Mutability,
1142 cmt_borrowed: mc::cmt) {
1144 * Informs the inference engine that a borrow of `cmt`
1145 * must have mutability `mutbl` and lifetime `region_min`.
1146 * If `cmt` is a deref of a region pointer with
1147 * lifetime `r_borrowed`, this will add the constraint that
1148 * `region_min <= r_borrowed`.
1151 // Iterate through all the things that must be live at least
1152 // for the lifetime `region_min` for the borrow to be valid:
1153 let mut cmt_borrowed = cmt_borrowed;
1155 debug!("link_region(region_min={}, mutbl={}, cmt_borrowed={})",
1156 region_min.repr(rcx.tcx()),
1157 mutbl.repr(rcx.tcx()),
1158 cmt_borrowed.repr(rcx.tcx()));
1159 match cmt_borrowed.cat {
1160 mc::cat_deref(base, _, mc::BorrowedPtr(_, r_borrowed)) => {
1161 // References to an upvar `x` are translated to
1162 // `*x`, since that is what happens in the
1163 // underlying machine. We detect such references
1164 // and treat them slightly differently, both to
1165 // offer better error messages and because we need
1166 // to infer the kind of borrow (mut, const, etc)
1167 // to use for each upvar.
1168 let cause = match base.cat {
1169 mc::cat_upvar(ref upvar_id, _) => {
1170 let mut upvar_borrow_map =
1171 rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1172 match upvar_borrow_map.get().find_mut(upvar_id) {
1173 Some(upvar_borrow) => {
1174 debug!("link_region: {} <= {}",
1175 region_min.repr(rcx.tcx()),
1176 upvar_borrow.region.repr(rcx.tcx()));
1177 adjust_upvar_borrow_kind_for_loan(
1181 infer::ReborrowUpvar(span, *upvar_id)
1184 rcx.tcx().sess.span_bug(
1186 format!("Illegal upvar id: {}",
1187 upvar_id.repr(rcx.tcx())));
1193 infer::Reborrow(span)
1197 debug!("link_region: {} <= {}",
1198 region_min.repr(rcx.tcx()),
1199 r_borrowed.repr(rcx.tcx()));
1200 rcx.fcx.mk_subr(true, cause, region_min, r_borrowed);
1202 if mutbl == ast::MutMutable {
1203 // If this is a mutable borrow, then the thing
1204 // being borrowed will have to be unique.
1205 // In user code, this means it must be an `&mut`
1206 // borrow, but for an upvar, we might opt
1207 // for an immutable-unique borrow.
1208 adjust_upvar_borrow_kind_for_unique(rcx, base);
1211 // Borrowing an `&mut` pointee for `region_min` is
1212 // only valid if the pointer resides in a unique
1213 // location which is itself valid for
1214 // `region_min`. We don't care about the unique
1215 // part, but we may need to influence the
1216 // inference to ensure that the location remains
1219 // FIXME(#8624) fixing borrowck will require this
1220 // if m == ast::m_mutbl {
1221 // cmt_borrowed = cmt_base;
1227 mc::cat_discr(cmt_base, _) |
1228 mc::cat_downcast(cmt_base) |
1229 mc::cat_deref(cmt_base, _, mc::OwnedPtr) |
1230 mc::cat_interior(cmt_base, _) => {
1231 // Interior or owned data requires its base to be valid
1232 cmt_borrowed = cmt_base;
1234 mc::cat_deref(_, _, mc::GcPtr(..)) |
1235 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1236 mc::cat_static_item |
1237 mc::cat_copied_upvar(..) |
1241 mc::cat_rvalue(..) => {
1242 // These are all "base cases" with independent lifetimes
1243 // that are not subject to inference
1250 fn adjust_borrow_kind_for_assignment_lhs(rcx: &mut Rcx,
1253 * Adjusts the inferred borrow_kind as needed to account
1254 * for upvars that are assigned to in an assignment
1258 let mut mc = mc::MemCategorizationContext { typer: rcx };
1259 let cmt = ignore_err!(mc.cat_expr(lhs));
1260 adjust_upvar_borrow_kind_for_mut(mc.typer, cmt);
1263 fn adjust_upvar_borrow_kind_for_mut(rcx: &mut Rcx,
1267 debug!("adjust_upvar_borrow_kind_for_mut(cmt={})",
1268 cmt.repr(rcx.tcx()));
1271 mc::cat_deref(base, _, mc::OwnedPtr) |
1272 mc::cat_interior(base, _) |
1273 mc::cat_downcast(base) |
1274 mc::cat_discr(base, _) => {
1275 // Interior or owned data is mutable if base is
1276 // mutable, so iterate to the base.
1281 mc::cat_deref(base, _, mc::BorrowedPtr(..)) => {
1283 mc::cat_upvar(ref upvar_id, _) => {
1284 // if this is an implicit deref of an
1285 // upvar, then we need to modify the
1286 // borrow_kind of the upvar to make sure it
1287 // is inferred to mutable if necessary
1288 let mut upvar_borrow_map =
1289 rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1290 let ub = upvar_borrow_map.get().get_mut(upvar_id);
1291 return adjust_upvar_borrow_kind(*upvar_id, ub, ty::MutBorrow);
1295 // assignment to deref of an `&mut`
1296 // borrowed pointer implies that the
1297 // pointer itself must be unique, but not
1298 // necessarily *mutable*
1299 return adjust_upvar_borrow_kind_for_unique(rcx, base);
1304 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1305 mc::cat_deref(_, _, mc::GcPtr) |
1306 mc::cat_static_item |
1308 mc::cat_copied_upvar(_) |
1311 mc::cat_upvar(..) => {
1318 fn adjust_upvar_borrow_kind_for_unique(rcx: &mut Rcx,
1322 debug!("adjust_upvar_borrow_kind_for_unique(cmt={})",
1323 cmt.repr(rcx.tcx()));
1326 mc::cat_deref(base, _, mc::OwnedPtr) |
1327 mc::cat_interior(base, _) |
1328 mc::cat_downcast(base) |
1329 mc::cat_discr(base, _) => {
1330 // Interior or owned data is unique if base is
1336 mc::cat_deref(base, _, mc::BorrowedPtr(..)) => {
1338 mc::cat_upvar(ref upvar_id, _) => {
1339 // if this is an implicit deref of an
1340 // upvar, then we need to modify the
1341 // borrow_kind of the upvar to make sure it
1342 // is inferred to unique if necessary
1343 let mut upvar_borrow_map =
1344 rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1345 let ub = upvar_borrow_map.get().get_mut(upvar_id);
1346 return adjust_upvar_borrow_kind(*upvar_id, ub, ty::UniqueImmBorrow);
1350 // for a borrowed pointer to be unique, its
1351 // base must be unique
1352 return adjust_upvar_borrow_kind_for_unique(rcx, base);
1357 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1358 mc::cat_deref(_, _, mc::GcPtr) |
1359 mc::cat_static_item |
1361 mc::cat_copied_upvar(_) |
1364 mc::cat_upvar(..) => {
1371 fn link_upvar_borrow_kind_for_nested_closures(rcx: &mut Rcx,
1372 inner_upvar_id: ty::UpvarId,
1373 outer_upvar_id: ty::UpvarId) {
1375 * Indicates that the borrow_kind of `outer_upvar_id` must
1376 * permit a reborrowing with the borrow_kind of `inner_upvar_id`.
1377 * This occurs in nested closures, see comment above at the call to
1381 debug!("link_upvar_borrow_kind: inner_upvar_id={:?} outer_upvar_id={:?}",
1382 inner_upvar_id, outer_upvar_id);
1384 let mut upvar_borrow_map = rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1385 let inner_borrow = upvar_borrow_map.get().get_copy(&inner_upvar_id);
1386 match upvar_borrow_map.get().find_mut(&outer_upvar_id) {
1387 Some(outer_borrow) => {
1388 adjust_upvar_borrow_kind(outer_upvar_id, outer_borrow, inner_borrow.kind);
1390 None => { /* outer closure is not a stack closure */ }
1394 fn adjust_upvar_borrow_kind_for_loan(upvar_id: ty::UpvarId,
1395 upvar_borrow: &mut ty::UpvarBorrow,
1396 mutbl: ast::Mutability) {
1397 debug!("adjust_upvar_borrow_kind_for_loan: upvar_id={:?} kind={:?} -> {:?}",
1398 upvar_id, upvar_borrow.kind, mutbl);
1400 adjust_upvar_borrow_kind(upvar_id, upvar_borrow,
1401 ty::BorrowKind::from_mutbl(mutbl))
1404 fn adjust_upvar_borrow_kind(upvar_id: ty::UpvarId,
1405 upvar_borrow: &mut ty::UpvarBorrow,
1406 kind: ty::BorrowKind) {
1408 * We infer the borrow_kind with which to borrow upvars in a stack
1409 * closure. The borrow_kind basically follows a lattice of
1410 * `imm < unique-imm < mut`, moving from left to right as needed (but never
1411 * right to left). Here the argument `mutbl` is the borrow_kind that
1412 * is required by some particular use.
1415 debug!("adjust_upvar_borrow_kind: id={:?} kind=({:?} -> {:?})",
1416 upvar_id, upvar_borrow.kind, kind);
1418 match (upvar_borrow.kind, kind) {
1420 (ty::ImmBorrow, ty::UniqueImmBorrow) |
1421 (ty::ImmBorrow, ty::MutBorrow) |
1422 (ty::UniqueImmBorrow, ty::MutBorrow) => {
1423 upvar_borrow.kind = kind;
1426 (ty::ImmBorrow, ty::ImmBorrow) |
1427 (ty::UniqueImmBorrow, ty::ImmBorrow) |
1428 (ty::UniqueImmBorrow, ty::UniqueImmBorrow) |
1429 (ty::MutBorrow, _) => {