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);
440 constrain_call(rcx, Some(callee.id), expr, None, *args, false);
442 visit::walk_expr(rcx, expr, ());
445 ast::ExprMethodCall(_, _, ref args) => {
446 constrain_call(rcx, None, expr, Some(args[0]),
447 args.slice_from(1), false);
449 visit::walk_expr(rcx, expr, ());
452 ast::ExprAssign(lhs, _) => {
453 adjust_borrow_kind_for_assignment_lhs(rcx, lhs);
454 visit::walk_expr(rcx, expr, ());
457 ast::ExprAssignOp(_, lhs, rhs) => {
459 constrain_call(rcx, None, expr, Some(lhs), [rhs], true);
462 adjust_borrow_kind_for_assignment_lhs(rcx, lhs);
464 visit::walk_expr(rcx, expr, ());
467 ast::ExprIndex(lhs, rhs) |
468 ast::ExprBinary(_, lhs, rhs) if has_method_map => {
469 // As `expr_method_call`, but the call is via an
470 // overloaded op. Note that we (sadly) currently use an
471 // implicit "by ref" sort of passing style here. This
472 // should be converted to an adjustment!
473 constrain_call(rcx, None, expr, Some(lhs), [rhs], true);
475 visit::walk_expr(rcx, expr, ());
478 ast::ExprUnary(_, lhs) if has_method_map => {
480 constrain_call(rcx, None, expr, Some(lhs), [], true);
482 visit::walk_expr(rcx, expr, ());
485 ast::ExprUnary(ast::UnDeref, base) => {
486 // For *a, the lifetime of a must enclose the deref
487 let base_ty = rcx.resolve_node_type(base.id);
488 constrain_derefs(rcx, expr, 1, base_ty);
490 visit::walk_expr(rcx, expr, ());
493 ast::ExprIndex(vec_expr, _) => {
494 // For a[b], the lifetime of a must enclose the deref
495 let vec_type = rcx.resolve_expr_type_adjusted(vec_expr);
496 constrain_index(rcx, expr, vec_type);
498 visit::walk_expr(rcx, expr, ());
501 ast::ExprCast(source, _) => {
502 // Determine if we are casting `source` to an trait
503 // instance. If so, we have to be sure that the type of
504 // the source obeys the trait's region bound.
506 // Note: there is a subtle point here concerning type
507 // parameters. It is possible that the type of `source`
508 // contains type parameters, which in turn may contain
509 // regions that are not visible to us (only the caller
510 // knows about them). The kind checker is ultimately
511 // responsible for guaranteeing region safety in that
512 // particular case. There is an extensive comment on the
513 // function check_cast_for_escaping_regions() in kind.rs
514 // explaining how it goes about doing that.
515 let target_ty = rcx.resolve_node_type(expr.id);
516 match ty::get(target_ty).sty {
517 ty::ty_trait(_, _, ty::RegionTraitStore(trait_region), _, _) => {
518 let source_ty = rcx.resolve_expr_type_adjusted(source);
519 constrain_regions_in_type(
522 infer::RelateObjectBound(expr.span),
528 visit::walk_expr(rcx, expr, ());
531 ast::ExprAddrOf(m, base) => {
532 link_addr_of(rcx, expr, m, base);
534 // Require that when you write a `&expr` expression, the
535 // resulting pointer has a lifetime that encompasses the
536 // `&expr` expression itself. Note that we constraining
537 // the type of the node expr.id here *before applying
540 // FIXME(#6268) nested method calls requires that this rule change
541 let ty0 = rcx.resolve_node_type(expr.id);
542 constrain_regions_in_type(rcx, ty::ReScope(expr.id),
543 infer::AddrOf(expr.span), ty0);
544 visit::walk_expr(rcx, expr, ());
547 ast::ExprMatch(discr, ref arms) => {
548 link_match(rcx, discr, *arms);
550 visit::walk_expr(rcx, expr, ());
553 ast::ExprFnBlock(_, ref body) | ast::ExprProc(_, ref body) => {
554 check_expr_fn_block(rcx, expr, &**body);
557 ast::ExprLoop(body, _) => {
558 let repeating_scope = rcx.set_repeating_scope(body.id);
559 visit::walk_expr(rcx, expr, ());
560 rcx.set_repeating_scope(repeating_scope);
563 ast::ExprWhile(cond, body) => {
564 let repeating_scope = rcx.set_repeating_scope(cond.id);
565 rcx.visit_expr(cond, ());
567 rcx.set_repeating_scope(body.id);
568 rcx.visit_block(body, ());
570 rcx.set_repeating_scope(repeating_scope);
574 visit::walk_expr(rcx, expr, ());
579 fn check_expr_fn_block(rcx: &mut Rcx,
582 let tcx = rcx.fcx.tcx();
583 let function_type = rcx.resolve_node_type(expr.id);
584 match ty::get(function_type).sty {
585 ty::ty_closure(ty::ClosureTy {
586 sigil: ast::BorrowedSigil, region: region, ..}) => {
587 let freevars = freevars::get_freevars(tcx, expr.id);
588 if freevars.is_empty() {
589 // No free variables means that the environment
590 // will be NULL at runtime and hence the closure
591 // has static lifetime.
593 // Closure must not outlive the variables it closes over.
594 constrain_free_variables(rcx, region, expr, freevars);
596 // Closure cannot outlive the appropriate temporary scope.
597 let s = rcx.repeating_scope;
598 rcx.fcx.mk_subr(true, infer::InfStackClosure(expr.span),
599 region, ty::ReScope(s));
605 let repeating_scope = rcx.set_repeating_scope(body.id);
606 visit::walk_expr(rcx, expr, ());
607 rcx.set_repeating_scope(repeating_scope);
609 match ty::get(function_type).sty {
610 ty::ty_closure(ty::ClosureTy {sigil: ast::BorrowedSigil, ..}) => {
611 let freevars = freevars::get_freevars(tcx, expr.id);
612 propagate_upupvar_borrow_kind(rcx, expr, freevars);
617 fn constrain_free_variables(rcx: &mut Rcx,
620 freevars: freevars::freevar_info) {
622 * Make sure that all free variables referenced inside the closure
623 * outlive the closure itself. Also, create an entry in the
624 * upvar_borrows map with a region.
627 let tcx = rcx.fcx.ccx.tcx;
628 let infcx = rcx.fcx.infcx();
629 debug!("constrain_free_variables({}, {})",
630 region.repr(tcx), expr.repr(tcx));
631 for freevar in freevars.iter() {
632 debug!("freevar def is {:?}", freevar.def);
634 // Identify the variable being closed over and its node-id.
635 let def = freevar.def;
636 let def_id = ast_util::def_id_of_def(def);
637 assert!(def_id.krate == ast::LOCAL_CRATE);
638 let upvar_id = ty::UpvarId { var_id: def_id.node,
639 closure_expr_id: expr.id };
641 // Create a region variable to represent this borrow. This borrow
642 // must outlive the region on the closure.
643 let origin = infer::UpvarRegion(upvar_id, expr.span);
644 let freevar_region = infcx.next_region_var(origin);
645 rcx.fcx.mk_subr(true, infer::FreeVariable(freevar.span, def_id.node),
646 region, freevar_region);
648 // Create a UpvarBorrow entry. Note that we begin with a
649 // const borrow_kind, but change it to either mut or
650 // immutable as dictated by the uses.
651 let upvar_borrow = ty::UpvarBorrow { kind: ty::ImmBorrow,
652 region: freevar_region };
653 let mut upvar_borrow_map = rcx.fcx.inh.upvar_borrow_map.borrow_mut();
654 upvar_borrow_map.get().insert(upvar_id, upvar_borrow);
656 // Guarantee that the closure does not outlive the variable itself.
657 let en_region = region_of_def(rcx.fcx, def);
658 debug!("en_region = {}", en_region.repr(tcx));
659 rcx.fcx.mk_subr(true, infer::FreeVariable(freevar.span, def_id.node),
664 fn propagate_upupvar_borrow_kind(rcx: &mut Rcx,
666 freevars: freevars::freevar_info) {
667 let tcx = rcx.fcx.ccx.tcx;
668 debug!("propagate_upupvar_borrow_kind({})", expr.repr(tcx));
669 for freevar in freevars.iter() {
670 // Because of the semi-hokey way that we are doing
671 // borrow_kind inference, we need to check for
672 // indirect dependencies, like so:
681 // Here, the `inner_call` is basically "reborrowing" the
682 // outer pointer. With no other changes, `inner_call`
683 // would infer that it requires a mutable borrow, but
684 // `outer_call` would infer that a const borrow is
685 // sufficient. This is because we haven't linked the
686 // borrow_kind of the borrow that occurs in the inner
687 // closure to the borrow_kind of the borrow in the outer
688 // closure. Note that regions *are* naturally linked
689 // because we have a proper inference scheme there.
691 // Anyway, for borrow_kind, we basically go back over now
692 // after checking the inner closure (and hence
693 // determining the final borrow_kind) and propagate that as
694 // a constraint on the outer closure.
696 ast::DefUpvar(var_id, _, outer_closure_id, _) => {
697 // thing being captured is itself an upvar:
698 let outer_upvar_id = ty::UpvarId {
700 closure_expr_id: outer_closure_id };
701 let inner_upvar_id = ty::UpvarId {
703 closure_expr_id: expr.id };
704 link_upvar_borrow_kind_for_nested_closures(rcx,
714 fn constrain_callee(rcx: &mut Rcx,
715 callee_id: ast::NodeId,
716 call_expr: &ast::Expr,
717 callee_expr: &ast::Expr) {
718 let call_region = ty::ReScope(call_expr.id);
720 let callee_ty = rcx.resolve_node_type(callee_id);
721 match ty::get(callee_ty).sty {
722 ty::ty_bare_fn(..) => { }
723 ty::ty_closure(ref closure_ty) => {
724 rcx.fcx.mk_subr(true, infer::InvokeClosure(callee_expr.span),
725 call_region, closure_ty.region);
728 // this should not happen, but it does if the program is
731 // tcx.sess.span_bug(
733 // format!("Calling non-function: {}", callee_ty.repr(tcx)));
738 fn constrain_call(rcx: &mut Rcx,
739 // might be expr_call, expr_method_call, or an overloaded
741 fn_expr_id: Option<ast::NodeId>,
742 call_expr: &ast::Expr,
743 receiver: Option<@ast::Expr>,
744 arg_exprs: &[@ast::Expr],
745 implicitly_ref_args: bool) {
746 //! Invoked on every call site (i.e., normal calls, method calls,
747 //! and overloaded operators). Constrains the regions which appear
748 //! in the type of the function. Also constrains the regions that
749 //! appear in the arguments appropriately.
751 let tcx = rcx.fcx.tcx();
752 debug!("constrain_call(call_expr={}, \
755 implicitly_ref_args={:?})",
759 implicitly_ref_args);
760 let callee_ty = match fn_expr_id {
761 Some(id) => rcx.resolve_node_type(id),
762 None => rcx.resolve_method_type(call_expr.id)
764 if ty::type_is_error(callee_ty) {
765 // Bail, as function type is unknown
768 let fn_sig = ty::ty_fn_sig(callee_ty);
770 // `callee_region` is the scope representing the time in which the
773 // FIXME(#6268) to support nested method calls, should be callee_id
774 let callee_scope = call_expr.id;
775 let callee_region = ty::ReScope(callee_scope);
777 for &arg_expr in arg_exprs.iter() {
780 // ensure that any regions appearing in the argument type are
781 // valid for at least the lifetime of the function:
782 constrain_regions_in_type_of_node(
783 rcx, arg_expr.id, callee_region,
784 infer::CallArg(arg_expr.span));
786 // unfortunately, there are two means of taking implicit
787 // references, and we need to propagate constraints as a
788 // result. modes are going away and the "DerefArgs" code
789 // should be ported to use adjustments
790 if implicitly_ref_args {
791 link_by_ref(rcx, arg_expr, callee_scope);
795 // as loop above, but for receiver
796 for &r in receiver.iter() {
798 constrain_regions_in_type_of_node(
799 rcx, r.id, callee_region, infer::CallRcvr(r.span));
800 if implicitly_ref_args {
801 link_by_ref(rcx, r, callee_scope);
805 // constrain regions that may appear in the return type to be
806 // valid for the function call:
807 constrain_regions_in_type(
808 rcx, callee_region, infer::CallReturn(call_expr.span),
812 fn constrain_derefs(rcx: &mut Rcx,
813 deref_expr: &ast::Expr,
815 mut derefd_ty: ty::t)
818 * Invoked on any dereference that occurs, whether explicitly
819 * or through an auto-deref. Checks that if this is a region
820 * pointer being derefenced, the lifetime of the pointer includes
823 let r_deref_expr = ty::ReScope(deref_expr.id);
824 for i in range(0u, derefs) {
825 debug!("constrain_derefs(deref_expr=?, derefd_ty={}, derefs={:?}/{:?}",
826 rcx.fcx.infcx().ty_to_str(derefd_ty),
829 match ty::get(derefd_ty).sty {
830 ty::ty_rptr(r_ptr, _) => {
831 mk_subregion_due_to_derefence(rcx, deref_expr.span,
832 r_deref_expr, r_ptr);
838 match ty::deref(derefd_ty, true) {
839 Some(mt) => derefd_ty = mt.ty,
840 /* if this type can't be dereferenced, then there's already an error
841 in the session saying so. Just bail out for now */
847 pub fn mk_subregion_due_to_derefence(rcx: &mut Rcx,
849 minimum_lifetime: ty::Region,
850 maximum_lifetime: ty::Region) {
851 rcx.fcx.mk_subr(true, infer::DerefPointer(deref_span),
852 minimum_lifetime, maximum_lifetime)
856 fn constrain_index(rcx: &mut Rcx,
857 index_expr: &ast::Expr,
861 * Invoked on any index expression that occurs. Checks that if
862 * this is a slice being indexed, the lifetime of the pointer
863 * includes the deref expr.
866 debug!("constrain_index(index_expr=?, indexed_ty={}",
867 rcx.fcx.infcx().ty_to_str(indexed_ty));
869 let r_index_expr = ty::ReScope(index_expr.id);
870 match ty::get(indexed_ty).sty {
871 ty::ty_str(ty::vstore_slice(r_ptr)) |
872 ty::ty_vec(_, ty::vstore_slice(r_ptr)) => {
873 rcx.fcx.mk_subr(true, infer::IndexSlice(index_expr.span),
874 r_index_expr, r_ptr);
881 fn constrain_regions_in_type_of_node(
884 minimum_lifetime: ty::Region,
885 origin: infer::SubregionOrigin) -> bool
887 //! Guarantees that any lifetimes which appear in the type of
888 //! the node `id` (after applying adjustments) are valid for at
889 //! least `minimum_lifetime`
891 let tcx = rcx.fcx.tcx();
893 // Try to resolve the type. If we encounter an error, then typeck
894 // is going to fail anyway, so just stop here and let typeck
895 // report errors later on in the writeback phase.
896 let ty0 = rcx.resolve_node_type(id);
898 let adjustments = rcx.fcx.inh.adjustments.borrow();
899 adjustments.get().find_copy(&id)
901 let ty = ty::adjust_ty(tcx, origin.span(), ty0, adjustment);
902 debug!("constrain_regions_in_type_of_node(\
903 ty={}, ty0={}, id={}, minimum_lifetime={:?}, adjustment={:?})",
904 ty_to_str(tcx, ty), ty_to_str(tcx, ty0),
905 id, minimum_lifetime, adjustment);
906 constrain_regions_in_type(rcx, minimum_lifetime, origin, ty)
909 fn constrain_regions_in_type(
911 minimum_lifetime: ty::Region,
912 origin: infer::SubregionOrigin,
916 * Requires that any regions which appear in `ty` must be
917 * superregions of `minimum_lifetime`. Also enforces the constraint
918 * that given a pointer type `&'r T`, T must not contain regions
919 * that outlive 'r, as well as analogous constraints for other
922 * This check prevents regions from being used outside of the block in
923 * which they are valid. Recall that regions represent blocks of
924 * code or expressions: this requirement basically says "any place
925 * that uses or may use a region R must be within the block of
926 * code that R corresponds to."
929 let e = rcx.errors_reported;
930 let tcx = rcx.fcx.ccx.tcx;
932 debug!("constrain_regions_in_type(minimum_lifetime={}, ty={})",
933 region_to_str(tcx, "", false, minimum_lifetime),
936 relate_nested_regions(tcx, Some(minimum_lifetime), ty, |r_sub, r_sup| {
937 debug!("relate_nested_regions(r_sub={}, r_sup={})",
941 if r_sup.is_bound() || r_sub.is_bound() {
942 // a bound region is one which appears inside an fn type.
943 // (e.g., the `&` in `fn(&T)`). Such regions need not be
944 // constrained by `minimum_lifetime` as they are placeholders
945 // for regions that are as-yet-unknown.
946 } else if r_sub == minimum_lifetime {
952 true, infer::ReferenceOutlivesReferent(ty, origin.span()),
957 return e == rcx.errors_reported;
960 // If mem categorization results in an error, it's because the type
961 // check failed (or will fail, when the error is uncovered and
962 // reported during writeback). In this case, we just ignore this part
963 // of the code and don't try to add any more region constraints.
964 macro_rules! ignore_err(
968 Err(()) => { return; }
973 fn link_addr_of(rcx: &mut Rcx, expr: &ast::Expr,
974 mutability: ast::Mutability, base: &ast::Expr) {
976 * Computes the guarantor for an expression `&base` and then
977 * ensures that the lifetime of the resulting pointer is linked
978 * to the lifetime of its guarantor (if any).
981 debug!("link_addr_of(base=?)");
984 let mut mc = mc::MemCategorizationContext { typer: &mut *rcx };
985 ignore_err!(mc.cat_expr(base))
987 link_region_from_node_type(rcx, expr.span, expr.id, mutability, cmt);
990 fn link_local(rcx: &mut Rcx, local: &ast::Local) {
992 * Computes the guarantors for any ref bindings in a `let` and
993 * then ensures that the lifetime of the resulting pointer is
994 * linked to the lifetime of the initialization expression.
997 debug!("regionck::for_local()");
998 let init_expr = match local.init {
1002 let mut mc = mc::MemCategorizationContext { typer: rcx };
1003 let discr_cmt = ignore_err!(mc.cat_expr(init_expr));
1004 link_pattern(&mut mc, discr_cmt, local.pat);
1007 fn link_match(rcx: &mut Rcx, discr: &ast::Expr, arms: &[ast::Arm]) {
1009 * Computes the guarantors for any ref bindings in a match and
1010 * then ensures that the lifetime of the resulting pointer is
1011 * linked to the lifetime of its guarantor (if any).
1014 debug!("regionck::for_match()");
1015 let mut mc = mc::MemCategorizationContext { typer: rcx };
1016 let discr_cmt = ignore_err!(mc.cat_expr(discr));
1017 debug!("discr_cmt={}", discr_cmt.repr(mc.typer.tcx()));
1018 for arm in arms.iter() {
1019 for &root_pat in arm.pats.iter() {
1020 link_pattern(&mut mc, discr_cmt, root_pat);
1025 fn link_pattern(mc: &mut mc::MemCategorizationContext<&mut Rcx>,
1027 root_pat: @ast::Pat) {
1029 * Link lifetimes of any ref bindings in `root_pat` to
1030 * the pointers found in the discriminant, if needed.
1033 let _ = mc.cat_pattern(discr_cmt, root_pat, |mc, sub_cmt, sub_pat| {
1034 match sub_pat.node {
1036 ast::PatIdent(ast::BindByRef(mutbl), _, _) => {
1037 link_region_from_node_type(
1038 mc.typer, sub_pat.span, sub_pat.id,
1042 // `[_, ..slice, _]` pattern
1043 ast::PatVec(_, Some(slice_pat), _) => {
1044 match mc.cat_slice_pattern(sub_cmt, slice_pat) {
1045 Ok((slice_cmt, slice_mutbl, slice_r)) => {
1046 link_region(mc.typer, sub_pat.span, slice_r,
1047 slice_mutbl, slice_cmt);
1057 fn link_autoref(rcx: &mut Rcx,
1060 autoref: &ty::AutoRef) {
1062 * Link lifetime of borrowed pointer resulting from autoref
1063 * to lifetimes in the value being autoref'd.
1066 debug!("link_autoref(autoref={:?})", autoref);
1067 let mut mc = mc::MemCategorizationContext { typer: rcx };
1068 let expr_cmt = ignore_err!(mc.cat_expr_autoderefd(expr, autoderefs));
1069 debug!("expr_cmt={}", expr_cmt.repr(mc.typer.tcx()));
1072 ty::AutoPtr(r, m) => {
1073 link_region(mc.typer, expr.span, r, m, expr_cmt);
1076 ty::AutoBorrowVec(r, m) | ty::AutoBorrowVecRef(r, m) => {
1077 let cmt_index = mc.cat_index(expr, expr_cmt, autoderefs+1);
1078 link_region(mc.typer, expr.span, r, m, cmt_index);
1081 ty::AutoBorrowFn(r) => {
1082 let cmt_deref = mc.cat_deref_fn_or_obj(expr, expr_cmt, 0);
1083 link_region(mc.typer, expr.span, r, ast::MutImmutable, cmt_deref);
1086 ty::AutoBorrowObj(r, m) => {
1087 let cmt_deref = mc.cat_deref_fn_or_obj(expr, expr_cmt, 0);
1088 link_region(mc.typer, expr.span, r, m, cmt_deref);
1091 ty::AutoUnsafe(_) => {}
1095 fn link_by_ref(rcx: &mut Rcx,
1097 callee_scope: ast::NodeId) {
1099 * Computes the guarantor for cases where the `expr` is
1100 * being passed by implicit reference and must outlive
1104 let tcx = rcx.tcx();
1105 debug!("link_by_ref(expr={}, callee_scope={})",
1106 expr.repr(tcx), callee_scope);
1107 let mut mc = mc::MemCategorizationContext { typer: rcx };
1108 let expr_cmt = ignore_err!(mc.cat_expr(expr));
1109 let region_min = ty::ReScope(callee_scope);
1110 link_region(mc.typer, expr.span, region_min, ast::MutImmutable, expr_cmt);
1113 fn link_region_from_node_type(rcx: &mut Rcx,
1116 mutbl: ast::Mutability,
1117 cmt_borrowed: mc::cmt) {
1119 * Like `link_region()`, except that the region is
1120 * extracted from the type of `id`, which must be some
1121 * reference (`&T`, `&str`, etc).
1124 let rptr_ty = rcx.resolve_node_type(id);
1125 if !ty::type_is_bot(rptr_ty) && !ty::type_is_error(rptr_ty) {
1126 let tcx = rcx.fcx.ccx.tcx;
1127 debug!("rptr_ty={}", ty_to_str(tcx, rptr_ty));
1128 let r = ty::ty_region(tcx, span, rptr_ty);
1129 link_region(rcx, span, r, mutbl, cmt_borrowed);
1133 fn link_region(rcx: &mut Rcx,
1135 region_min: ty::Region,
1136 mutbl: ast::Mutability,
1137 cmt_borrowed: mc::cmt) {
1139 * Informs the inference engine that a borrow of `cmt`
1140 * must have mutability `mutbl` and lifetime `region_min`.
1141 * If `cmt` is a deref of a region pointer with
1142 * lifetime `r_borrowed`, this will add the constraint that
1143 * `region_min <= r_borrowed`.
1146 // Iterate through all the things that must be live at least
1147 // for the lifetime `region_min` for the borrow to be valid:
1148 let mut cmt_borrowed = cmt_borrowed;
1150 debug!("link_region(region_min={}, mutbl={}, cmt_borrowed={})",
1151 region_min.repr(rcx.tcx()),
1152 mutbl.repr(rcx.tcx()),
1153 cmt_borrowed.repr(rcx.tcx()));
1154 match cmt_borrowed.cat {
1155 mc::cat_deref(base, _, mc::BorrowedPtr(_, r_borrowed)) => {
1156 // References to an upvar `x` are translated to
1157 // `*x`, since that is what happens in the
1158 // underlying machine. We detect such references
1159 // and treat them slightly differently, both to
1160 // offer better error messages and because we need
1161 // to infer the kind of borrow (mut, const, etc)
1162 // to use for each upvar.
1163 let cause = match base.cat {
1164 mc::cat_upvar(ref upvar_id, _) => {
1165 let mut upvar_borrow_map =
1166 rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1167 match upvar_borrow_map.get().find_mut(upvar_id) {
1168 Some(upvar_borrow) => {
1169 debug!("link_region: {} <= {}",
1170 region_min.repr(rcx.tcx()),
1171 upvar_borrow.region.repr(rcx.tcx()));
1172 adjust_upvar_borrow_kind_for_loan(
1176 infer::ReborrowUpvar(span, *upvar_id)
1179 rcx.tcx().sess.span_bug(
1181 format!("Illegal upvar id: {}",
1182 upvar_id.repr(rcx.tcx())));
1188 infer::Reborrow(span)
1192 debug!("link_region: {} <= {}",
1193 region_min.repr(rcx.tcx()),
1194 r_borrowed.repr(rcx.tcx()));
1195 rcx.fcx.mk_subr(true, cause, region_min, r_borrowed);
1197 if mutbl == ast::MutMutable {
1198 // If this is a mutable borrow, then the thing
1199 // being borrowed will have to be unique.
1200 // In user code, this means it must be an `&mut`
1201 // borrow, but for an upvar, we might opt
1202 // for an immutable-unique borrow.
1203 adjust_upvar_borrow_kind_for_unique(rcx, base);
1206 // Borrowing an `&mut` pointee for `region_min` is
1207 // only valid if the pointer resides in a unique
1208 // location which is itself valid for
1209 // `region_min`. We don't care about the unique
1210 // part, but we may need to influence the
1211 // inference to ensure that the location remains
1214 // FIXME(#8624) fixing borrowck will require this
1215 // if m == ast::m_mutbl {
1216 // cmt_borrowed = cmt_base;
1222 mc::cat_discr(cmt_base, _) |
1223 mc::cat_downcast(cmt_base) |
1224 mc::cat_deref(cmt_base, _, mc::OwnedPtr) |
1225 mc::cat_interior(cmt_base, _) => {
1226 // Interior or owned data requires its base to be valid
1227 cmt_borrowed = cmt_base;
1229 mc::cat_deref(_, _, mc::GcPtr(..)) |
1230 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1231 mc::cat_static_item |
1232 mc::cat_copied_upvar(..) |
1236 mc::cat_rvalue(..) => {
1237 // These are all "base cases" with independent lifetimes
1238 // that are not subject to inference
1245 fn adjust_borrow_kind_for_assignment_lhs(rcx: &mut Rcx,
1248 * Adjusts the inferred borrow_kind as needed to account
1249 * for upvars that are assigned to in an assignment
1253 let mut mc = mc::MemCategorizationContext { typer: rcx };
1254 let cmt = ignore_err!(mc.cat_expr(lhs));
1255 adjust_upvar_borrow_kind_for_mut(mc.typer, cmt);
1258 fn adjust_upvar_borrow_kind_for_mut(rcx: &mut Rcx,
1262 debug!("adjust_upvar_borrow_kind_for_mut(cmt={})",
1263 cmt.repr(rcx.tcx()));
1266 mc::cat_deref(base, _, mc::OwnedPtr) |
1267 mc::cat_interior(base, _) |
1268 mc::cat_downcast(base) |
1269 mc::cat_discr(base, _) => {
1270 // Interior or owned data is mutable if base is
1271 // mutable, so iterate to the base.
1276 mc::cat_deref(base, _, mc::BorrowedPtr(..)) => {
1278 mc::cat_upvar(ref upvar_id, _) => {
1279 // if this is an implicit deref of an
1280 // upvar, then we need to modify the
1281 // borrow_kind of the upvar to make sure it
1282 // is inferred to mutable if necessary
1283 let mut upvar_borrow_map =
1284 rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1285 let ub = upvar_borrow_map.get().get_mut(upvar_id);
1286 return adjust_upvar_borrow_kind(*upvar_id, ub, ty::MutBorrow);
1290 // assignment to deref of an `&mut`
1291 // borrowed pointer implies that the
1292 // pointer itself must be unique, but not
1293 // necessarily *mutable*
1294 return adjust_upvar_borrow_kind_for_unique(rcx, base);
1299 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1300 mc::cat_deref(_, _, mc::GcPtr) |
1301 mc::cat_static_item |
1303 mc::cat_copied_upvar(_) |
1306 mc::cat_upvar(..) => {
1313 fn adjust_upvar_borrow_kind_for_unique(rcx: &mut Rcx,
1317 debug!("adjust_upvar_borrow_kind_for_unique(cmt={})",
1318 cmt.repr(rcx.tcx()));
1321 mc::cat_deref(base, _, mc::OwnedPtr) |
1322 mc::cat_interior(base, _) |
1323 mc::cat_downcast(base) |
1324 mc::cat_discr(base, _) => {
1325 // Interior or owned data is unique if base is
1331 mc::cat_deref(base, _, mc::BorrowedPtr(..)) => {
1333 mc::cat_upvar(ref upvar_id, _) => {
1334 // if this is an implicit deref of an
1335 // upvar, then we need to modify the
1336 // borrow_kind of the upvar to make sure it
1337 // is inferred to unique if necessary
1338 let mut upvar_borrow_map =
1339 rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1340 let ub = upvar_borrow_map.get().get_mut(upvar_id);
1341 return adjust_upvar_borrow_kind(*upvar_id, ub, ty::UniqueImmBorrow);
1345 // for a borrowed pointer to be unique, its
1346 // base must be unique
1347 return adjust_upvar_borrow_kind_for_unique(rcx, base);
1352 mc::cat_deref(_, _, mc::UnsafePtr(..)) |
1353 mc::cat_deref(_, _, mc::GcPtr) |
1354 mc::cat_static_item |
1356 mc::cat_copied_upvar(_) |
1359 mc::cat_upvar(..) => {
1366 fn link_upvar_borrow_kind_for_nested_closures(rcx: &mut Rcx,
1367 inner_upvar_id: ty::UpvarId,
1368 outer_upvar_id: ty::UpvarId) {
1370 * Indicates that the borrow_kind of `outer_upvar_id` must
1371 * permit a reborrowing with the borrow_kind of `inner_upvar_id`.
1372 * This occurs in nested closures, see comment above at the call to
1376 debug!("link_upvar_borrow_kind: inner_upvar_id={:?} outer_upvar_id={:?}",
1377 inner_upvar_id, outer_upvar_id);
1379 let mut upvar_borrow_map = rcx.fcx.inh.upvar_borrow_map.borrow_mut();
1380 let inner_borrow = upvar_borrow_map.get().get_copy(&inner_upvar_id);
1381 match upvar_borrow_map.get().find_mut(&outer_upvar_id) {
1382 Some(outer_borrow) => {
1383 adjust_upvar_borrow_kind(outer_upvar_id, outer_borrow, inner_borrow.kind);
1385 None => { /* outer closure is not a stack closure */ }
1389 fn adjust_upvar_borrow_kind_for_loan(upvar_id: ty::UpvarId,
1390 upvar_borrow: &mut ty::UpvarBorrow,
1391 mutbl: ast::Mutability) {
1392 debug!("adjust_upvar_borrow_kind_for_loan: upvar_id={:?} kind={:?} -> {:?}",
1393 upvar_id, upvar_borrow.kind, mutbl);
1395 adjust_upvar_borrow_kind(upvar_id, upvar_borrow,
1396 ty::BorrowKind::from_mutbl(mutbl))
1399 fn adjust_upvar_borrow_kind(upvar_id: ty::UpvarId,
1400 upvar_borrow: &mut ty::UpvarBorrow,
1401 kind: ty::BorrowKind) {
1403 * We infer the borrow_kind with which to borrow upvars in a stack
1404 * closure. The borrow_kind basically follows a lattice of
1405 * `imm < unique-imm < mut`, moving from left to right as needed (but never
1406 * right to left). Here the argument `mutbl` is the borrow_kind that
1407 * is required by some particular use.
1410 debug!("adjust_upvar_borrow_kind: id={:?} kind=({:?} -> {:?})",
1411 upvar_id, upvar_borrow.kind, kind);
1413 match (upvar_borrow.kind, kind) {
1415 (ty::ImmBorrow, ty::UniqueImmBorrow) |
1416 (ty::ImmBorrow, ty::MutBorrow) |
1417 (ty::UniqueImmBorrow, ty::MutBorrow) => {
1418 upvar_borrow.kind = kind;
1421 (ty::ImmBorrow, ty::ImmBorrow) |
1422 (ty::UniqueImmBorrow, ty::ImmBorrow) |
1423 (ty::UniqueImmBorrow, ty::UniqueImmBorrow) |
1424 (ty::MutBorrow, _) => {