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 mc = middle::mem_categorization;
  18 use middle::ty;
  19 use util::ppaux::Repr;
  20 use syntax::ast;
  21 use syntax::codemap::Span;
  22
  23 type R = Result<(),()>;
  24
  25 pub fn guarantee_lifetime(bccx: &BorrowckCtxt,
  26                           item_scope_id: ast::NodeId,
  27                           root_scope_id: ast::NodeId,
  28                           span: Span,
  29                           cause: 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,
  43                                          root_scope_id: root_scope_id};
  44     ctxt.check(cmt, None)
  45 }
  46
  47 ///////////////////////////////////////////////////////////////////////////
  48 // Private
  49
  50 struct GuaranteeLifetimeContext<'a> {
  51     bccx: &'a BorrowckCtxt<'a>,
  52
  53     // the node id of the function body for the enclosing item
  54     item_scope_id: ast::NodeId,
  55
  56     // the node id of the innermost loop / function body; this is the
  57     // longest scope for which we can root managed boxes
  58     root_scope_id: ast::NodeId,
  59
  60     span: Span,
  61     cause: LoanCause,
  62     loan_region: ty::Region,
  63     loan_kind: ty::BorrowKind,
  64     cmt_original: mc::cmt
  65 }
  66
  67 impl<'a> GuaranteeLifetimeContext<'a> {
  68     fn tcx(&self) -> &'a ty::ctxt {
  69         self.bccx.tcx
  70     }
  71
  72     fn check(&self, cmt: mc::cmt, discr_scope: Option<ast::NodeId>) -> R {
  73         //! Main routine. Walks down `cmt` until we find the "guarantor".
  74         debug!("guarantee_lifetime.check(cmt={}, loan_region={})",
  75                cmt.repr(self.bccx.tcx),
  76                self.loan_region.repr(self.bccx.tcx));
  77
  78         match cmt.cat {
  79             mc::cat_rvalue(..) |
  80             mc::cat_copied_upvar(..) |                  // L-Local
  81             mc::cat_local(..) |                         // L-Local
  82             mc::cat_arg(..) |                           // L-Local
  83             mc::cat_upvar(..) |
  84             mc::cat_deref(_, _, mc::BorrowedPtr(..)) |  // L-Deref-Borrowed
  85             mc::cat_deref(_, _, mc::UnsafePtr(..)) => {
  86                 let scope = self.scope(cmt);
  87                 self.check_scope(scope)
  88             }
  89
  90             mc::cat_static_item => {
  91                 Ok(())
  92             }
  93
  94             mc::cat_deref(base, derefs, mc::GcPtr) => {
  95                 let base_scope = self.scope(base);
  96
  97                 // L-Deref-Managed-Imm-User-Root
  98                 let omit_root =
  99                     self.bccx.is_subregion_of(self.loan_region, base_scope) &&
 100                     self.is_rvalue_or_immutable(base) &&
 101                     !self.is_moved(base);
 102
 103                 if !omit_root {
 104                     // L-Deref-Managed-Imm-Compiler-Root
 105                     // L-Deref-Managed-Mut-Compiler-Root
 106                     self.check_root(cmt, base, derefs, discr_scope)
 107                 } else {
 108                     debug!("omitting root, base={}, base_scope={:?}",
 109                            base.repr(self.tcx()), base_scope);
 110                     Ok(())
 111                 }
 112             }
 113
 114             mc::cat_downcast(base) |
 115             mc::cat_deref(base, _, mc::OwnedPtr) |     // L-Deref-Send
 116             mc::cat_interior(base, _) => {             // L-Field
 117                 self.check(base, discr_scope)
 118             }
 119
 120             mc::cat_discr(base, new_discr_scope) => {
 121                 // Subtle: in a match, we must ensure that each binding
 122                 // variable remains valid for the duration of the arm in
 123                 // which it appears, presuming that this arm is taken.
 124                 // But it is inconvenient in trans to root something just
 125                 // for one arm.  Therefore, we insert a cat_discr(),
 126                 // basically a special kind of category that says "if this
 127                 // value must be dynamically rooted, root it for the scope
 128                 // `match_id`".
 129                 //
 130                 // As an example, consider this scenario:
 131                 //
 132                 //    let mut x = @Some(3);
 133                 //    match *x { Some(y) {...} None {...} }
 134                 //
 135                 // Technically, the value `x` need only be rooted
 136                 // in the `some` arm.  However, we evaluate `x` in trans
 137                 // before we know what arm will be taken, so we just
 138                 // always root it for the duration of the match.
 139                 //
 140                 // As a second example, consider *this* scenario:
 141                 //
 142                 //    let x = @@Some(3);
 143                 //    match x { @@Some(y) {...} @@None {...} }
 144                 //
 145                 // Here again, `x` need only be rooted in the `some` arm.
 146                 // In this case, the value which needs to be rooted is
 147                 // found only when checking which pattern matches: but
 148                 // this check is done before entering the arm.  Therefore,
 149                 // even in this case we just choose to keep the value
 150                 // rooted for the entire match.  This means the value will be
 151                 // rooted even if the none arm is taken.  Oh well.
 152                 //
 153                 // At first, I tried to optimize the second case to only
 154                 // root in one arm, but the result was suboptimal: first,
 155                 // it interfered with the construction of phi nodes in the
 156                 // arm, as we were adding code to root values before the
 157                 // phi nodes were added.  This could have been addressed
 158                 // with a second basic block.  However, the naive approach
 159                 // also yielded suboptimal results for patterns like:
 160                 //
 161                 //    let x = @@...;
 162                 //    match x { @@some_variant(y) | @@some_other_variant(y) =>
 163                 //
 164                 // The reason is that we would root the value once for
 165                 // each pattern and not once per arm.  This is also easily
 166                 // fixed, but it's yet more code for what is really quite
 167                 // the corner case.
 168                 //
 169                 // Nonetheless, if you decide to optimize this case in the
 170                 // future, you need only adjust where the cat_discr()
 171                 // node appears to draw the line between what will be rooted
 172                 // in the *arm* vs the *match*.
 173                 self.check(base, Some(new_discr_scope))
 174             }
 175         }
 176     }
 177
 178     fn is_rvalue_or_immutable(&self,
 179                               cmt: mc::cmt) -> bool {
 180         //! We can omit the root on an `@T` value if the location
 181         //! that holds the box is either (1) an rvalue, in which case
 182         //! it is in a non-user-accessible temporary, or (2) an immutable
 183         //! lvalue.
 184
 185         cmt.mutbl.is_immutable() || match cmt.guarantor().cat {
 186             mc::cat_rvalue(..) => true,
 187             _ => false
 188         }
 189     }
 190
 191     fn check_root(&self,
 192                   cmt_deref: mc::cmt,
 193                   cmt_base: mc::cmt,
 194                   derefs: uint,
 195                   discr_scope: Option<ast::NodeId>) -> R {
 196         debug!("check_root(cmt_deref={}, cmt_base={}, derefs={:?}, \
 197                 discr_scope={:?})",
 198                cmt_deref.repr(self.tcx()),
 199                cmt_base.repr(self.tcx()),
 200                derefs,
 201                discr_scope);
 202
 203         // Make sure that the loan does not exceed the maximum time
 204         // that we can root the value, dynamically.
 205         let root_region = ty::ReScope(self.root_scope_id);
 206         if !self.bccx.is_subregion_of(self.loan_region, root_region) {
 207             return Err(self.report_error(
 208                 err_out_of_root_scope(root_region, self.loan_region)));
 209         }
 210
 211         // Extract the scope id that indicates how long the rooting is required
 212         let root_scope = match self.loan_region {
 213             ty::ReScope(id) => id,
 214             _ => {
 215                 // the check above should fail for anything is not ReScope
 216                 self.bccx.tcx.sess.span_bug(
 217                     cmt_base.span,
 218                     format!("cannot issue root for scope region: {:?}",
 219                          self.loan_region));
 220             }
 221         };
 222
 223         // If inside of a match arm, expand the rooting to the entire
 224         // match. See the detailed discussion in `check()` above.
 225         let root_scope = match discr_scope {
 226             None => root_scope,
 227             Some(id) => {
 228                 if self.bccx.is_subscope_of(root_scope, id) {
 229                     id
 230                 } else {
 231                     root_scope
 232                 }
 233             }
 234         };
 235
 236         // Add a record of what is required
 237         let rm_key = root_map_key {id: cmt_deref.id, derefs: derefs};
 238         let root_info = RootInfo {scope: root_scope};
 239
 240         self.bccx.root_map.borrow_mut().insert(rm_key, root_info);
 241
 242         debug!("root_key: {:?} root_info: {:?}", rm_key, root_info);
 243         Ok(())
 244     }
 245
 246     fn check_scope(&self, max_scope: ty::Region) -> R {
 247         //! Reports an error if `loan_region` is larger than `valid_scope`
 248
 249         if !self.bccx.is_subregion_of(self.loan_region, max_scope) {
 250             Err(self.report_error(err_out_of_scope(max_scope, self.loan_region)))
 251         } else {
 252             Ok(())
 253         }
 254     }
 255
 256     fn is_moved(&self, cmt: mc::cmt) -> bool {
 257         //! True if `cmt` is something that is potentially moved
 258         //! out of the current stack frame.
 259
 260         match cmt.guarantor().cat {
 261             mc::cat_local(id) |
 262             mc::cat_arg(id) => {
 263                 self.bccx.moved_variables_set.contains(&id)
 264             }
 265             mc::cat_rvalue(..) |
 266             mc::cat_static_item |
 267             mc::cat_copied_upvar(..) |
 268             mc::cat_deref(..) |
 269             mc::cat_upvar(..) => {
 270                 false
 271             }
 272             r @ mc::cat_downcast(..) |
 273             r @ mc::cat_interior(..) |
 274             r @ mc::cat_discr(..) => {
 275                 self.tcx().sess.span_bug(
 276                     cmt.span,
 277                     format!("illegal guarantor category: {:?}", r));
 278             }
 279         }
 280     }
 281
 282     fn scope(&self, cmt: mc::cmt) -> ty::Region {
 283         //! Returns the maximal region scope for the which the
 284         //! lvalue `cmt` is guaranteed to be valid without any
 285         //! rooting etc, and presuming `cmt` is not mutated.
 286
 287         // See the SCOPE(LV) function in doc.rs
 288
 289         match cmt.cat {
 290             mc::cat_rvalue(temp_scope) => {
 291                 temp_scope
 292             }
 293             mc::cat_upvar(..) |
 294             mc::cat_copied_upvar(_) => {
 295                 ty::ReScope(self.item_scope_id)
 296             }
 297             mc::cat_static_item => {
 298                 ty::ReStatic
 299             }
 300             mc::cat_local(local_id) |
 301             mc::cat_arg(local_id) => {
 302                 ty::ReScope(self.bccx.tcx.region_maps.var_scope(local_id))
 303             }
 304             mc::cat_deref(_, _, mc::UnsafePtr(..)) => {
 305                 ty::ReStatic
 306             }
 307             mc::cat_deref(_, _, mc::BorrowedPtr(_, r)) => {
 308                 r
 309             }
 310             mc::cat_downcast(cmt) |
 311             mc::cat_deref(cmt, _, mc::OwnedPtr) |
 312             mc::cat_deref(cmt, _, mc::GcPtr) |
 313             mc::cat_interior(cmt, _) |
 314             mc::cat_discr(cmt, _) => {
 315                 self.scope(cmt)
 316             }
 317         }
 318     }
 319
 320     fn report_error(&self, code: bckerr_code) {
 321         self.bccx.report(BckError { cmt: self.cmt_original,
 322                                     span: self.span,
 323                                     cause: self.cause,
 324                                     code: code });
 325     }
 326 }