src/librustc/middle/borrowck/gather_loans/lifetime.rs

   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.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 /*!
  12  * This module implements the check that the lifetime of a borrow
  13  * does not exceed the lifetime of the value being borrowed.
  14  */
  15
  16 use middle::borrowck::*;
  17 use euv = middle::expr_use_visitor;
  18 use mc = middle::mem_categorization;
  19 use middle::ty;
  20 use util::ppaux::Repr;
  21 use syntax::ast;
  22 use syntax::codemap::Span;
  23
  24 type R = Result<(),()>;
  25
  26 pub fn guarantee_lifetime(bccx: &BorrowckCtxt,
  27                           item_scope_id: ast::NodeId,
  28                           span: Span,
  29                           cause: euv::LoanCause,
  30                           cmt: mc::cmt,
  31                           loan_region: ty::Region,
  32                           loan_kind: ty::BorrowKind)
  33                           -> Result<(),()> {
  34     debug!("guarantee_lifetime(cmt={}, loan_region={})",
  35            cmt.repr(bccx.tcx), loan_region.repr(bccx.tcx));
  36     let ctxt = GuaranteeLifetimeContext {bccx: bccx,
  37                                          item_scope_id: item_scope_id,
  38                                          span: span,
  39                                          cause: cause,
  40                                          loan_region: loan_region,
  41                                          loan_kind: loan_kind,
  42                                          cmt_original: cmt.clone()};
  43     ctxt.check(&cmt, None)
  44 }
  45
  46 ///////////////////////////////////////////////////////////////////////////
  47 // Private
  48
  49 struct GuaranteeLifetimeContext<'a> {
  50     bccx: &'a BorrowckCtxt<'a>,
  51
  52     // the node id of the function body for the enclosing item
  53     item_scope_id: ast::NodeId,
  54
  55     span: Span,
  56     cause: euv::LoanCause,
  57     loan_region: ty::Region,
  58     loan_kind: ty::BorrowKind,
  59     cmt_original: mc::cmt
  60 }
  61
  62 impl<'a> GuaranteeLifetimeContext<'a> {
  63
  64     fn check(&self, cmt: &mc::cmt, discr_scope: Option<ast::NodeId>) -> R {
  65         //! Main routine. Walks down `cmt` until we find the "guarantor".
  66         debug!("guarantee_lifetime.check(cmt={}, loan_region={})",
  67                cmt.repr(self.bccx.tcx),
  68                self.loan_region.repr(self.bccx.tcx));
  69
  70         match cmt.cat {
  71             mc::cat_rvalue(..) |
  72             mc::cat_copied_upvar(..) |                  // L-Local
  73             mc::cat_local(..) |                         // L-Local
  74             mc::cat_arg(..) |                           // L-Local
  75             mc::cat_upvar(..) |
  76             mc::cat_deref(_, _, mc::BorrowedPtr(..)) |  // L-Deref-Borrowed
  77             mc::cat_deref(_, _, mc::UnsafePtr(..)) => {
  78                 self.check_scope(self.scope(cmt))
  79             }
  80
  81             mc::cat_static_item => {
  82                 Ok(())
  83             }
  84
  85             mc::cat_downcast(ref base) |
  86             mc::cat_deref(ref base, _, mc::OwnedPtr) |     // L-Deref-Send
  87             mc::cat_interior(ref base, _) |                // L-Field
  88             mc::cat_deref(ref base, _, mc::GcPtr) => {
  89                 self.check(base, discr_scope)
  90             }
  91
  92             mc::cat_discr(ref base, new_discr_scope) => {
  93                 // Subtle: in a match, we must ensure that each binding
  94                 // variable remains valid for the duration of the arm in
  95                 // which it appears, presuming that this arm is taken.
  96                 // But it is inconvenient in trans to root something just
  97                 // for one arm.  Therefore, we insert a cat_discr(),
  98                 // basically a special kind of category that says "if this
  99                 // value must be dynamically rooted, root it for the scope
 100                 // `match_id`".
 101                 //
 102                 // As an example, consider this scenario:
 103                 //
 104                 //    let mut x = @Some(3);
 105                 //    match *x { Some(y) {...} None {...} }
 106                 //
 107                 // Technically, the value `x` need only be rooted
 108                 // in the `some` arm.  However, we evaluate `x` in trans
 109                 // before we know what arm will be taken, so we just
 110                 // always root it for the duration of the match.
 111                 //
 112                 // As a second example, consider *this* scenario:
 113                 //
 114                 //    let x = @@Some(3);
 115                 //    match x { @@Some(y) {...} @@None {...} }
 116                 //
 117                 // Here again, `x` need only be rooted in the `some` arm.
 118                 // In this case, the value which needs to be rooted is
 119                 // found only when checking which pattern matches: but
 120                 // this check is done before entering the arm.  Therefore,
 121                 // even in this case we just choose to keep the value
 122                 // rooted for the entire match.  This means the value will be
 123                 // rooted even if the none arm is taken.  Oh well.
 124                 //
 125                 // At first, I tried to optimize the second case to only
 126                 // root in one arm, but the result was suboptimal: first,
 127                 // it interfered with the construction of phi nodes in the
 128                 // arm, as we were adding code to root values before the
 129                 // phi nodes were added.  This could have been addressed
 130                 // with a second basic block.  However, the naive approach
 131                 // also yielded suboptimal results for patterns like:
 132                 //
 133                 //    let x = @@...;
 134                 //    match x { @@some_variant(y) | @@some_other_variant(y) =>
 135                 //
 136                 // The reason is that we would root the value once for
 137                 // each pattern and not once per arm.  This is also easily
 138                 // fixed, but it's yet more code for what is really quite
 139                 // the corner case.
 140                 //
 141                 // Nonetheless, if you decide to optimize this case in the
 142                 // future, you need only adjust where the cat_discr()
 143                 // node appears to draw the line between what will be rooted
 144                 // in the *arm* vs the *match*.
 145                 self.check(base, Some(new_discr_scope))
 146             }
 147         }
 148     }
 149
 150     fn check_scope(&self, max_scope: ty::Region) -> R {
 151         //! Reports an error if `loan_region` is larger than `valid_scope`
 152
 153         if !self.bccx.is_subregion_of(self.loan_region, max_scope) {
 154             Err(self.report_error(err_out_of_scope(max_scope, self.loan_region)))
 155         } else {
 156             Ok(())
 157         }
 158     }
 159
 160     fn scope(&self, cmt: &mc::cmt) -> ty::Region {
 161         //! Returns the maximal region scope for the which the
 162         //! lvalue `cmt` is guaranteed to be valid without any
 163         //! rooting etc, and presuming `cmt` is not mutated.
 164
 165         // See the SCOPE(LV) function in doc.rs
 166
 167         match cmt.cat {
 168             mc::cat_rvalue(temp_scope) => {
 169                 temp_scope
 170             }
 171             mc::cat_upvar(..) |
 172             mc::cat_copied_upvar(_) => {
 173                 ty::ReScope(self.item_scope_id)
 174             }
 175             mc::cat_static_item => {
 176                 ty::ReStatic
 177             }
 178             mc::cat_local(local_id) |
 179             mc::cat_arg(local_id) => {
 180                 ty::ReScope(self.bccx.tcx.region_maps.var_scope(local_id))
 181             }
 182             mc::cat_deref(_, _, mc::UnsafePtr(..)) => {
 183                 ty::ReStatic
 184             }
 185             mc::cat_deref(_, _, mc::BorrowedPtr(_, r)) => {
 186                 r
 187             }
 188             mc::cat_downcast(ref cmt) |
 189             mc::cat_deref(ref cmt, _, mc::OwnedPtr) |
 190             mc::cat_deref(ref cmt, _, mc::GcPtr) |
 191             mc::cat_interior(ref cmt, _) |
 192             mc::cat_discr(ref cmt, _) => {
 193                 self.scope(cmt)
 194             }
 195         }
 196     }
 197
 198     fn report_error(&self, code: bckerr_code) {
 199         self.bccx.report(BckError { cmt: self.cmt_original.clone(),
 200                                     span: self.span,
 201                                     cause: self.cause,
 202                                     code: code });
 203     }
 204 }