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