src/librustc_mir/borrow_check/prefixes.rs

   1 //! From the NLL RFC: "The deep [aka 'supporting'] prefixes for an
   2 //! place are formed by stripping away fields and derefs, except that
   3 //! we stop when we reach the deref of a shared reference. [...] "
   4 //!
   5 //! "Shallow prefixes are found by stripping away fields, but stop at
   6 //! any dereference. So: writing a path like `a` is illegal if `a.b`
   7 //! is borrowed. But: writing `a` is legal if `*a` is borrowed,
   8 //! whether or not `a` is a shared or mutable reference. [...] "
   9
  10 use super::MirBorrowckCtxt;
  11
  12 use rustc::hir;
  13 use rustc::ty::{self, TyCtxt};
  14 use rustc::mir::{Mir, Place, ProjectionElem};
  15
  16 pub trait IsPrefixOf<'tcx> {
  17     fn is_prefix_of(&self, other: &Place<'tcx>) -> bool;
  18 }
  19
  20 impl<'tcx> IsPrefixOf<'tcx> for Place<'tcx> {
  21     fn is_prefix_of(&self, other: &Place<'tcx>) -> bool {
  22         let mut cursor = other;
  23         loop {
  24             if self == cursor {
  25                 return true;
  26             }
  27
  28             match *cursor {
  29                 Place::Promoted(_) |
  30                 Place::Local(_) | Place::Static(_) => return false,
  31                 Place::Projection(ref proj) => {
  32                     cursor = &proj.base;
  33                 }
  34             }
  35         }
  36     }
  37 }
  38
  39
  40 pub(super) struct Prefixes<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
  41     mir: &'cx Mir<'tcx>,
  42     tcx: TyCtxt<'cx, 'gcx, 'tcx>,
  43     kind: PrefixSet,
  44     next: Option<&'cx Place<'tcx>>,
  45 }
  46
  47 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  48 #[allow(dead_code)]
  49 pub(super) enum PrefixSet {
  50     /// Doesn't stop until it returns the base case (a Local or
  51     /// Static prefix).
  52     All,
  53     /// Stops at any dereference.
  54     Shallow,
  55     /// Stops at the deref of a shared reference.
  56     Supporting,
  57 }
  58
  59 impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
  60     /// Returns an iterator over the prefixes of `place`
  61     /// (inclusive) from longest to smallest, potentially
  62     /// terminating the iteration early based on `kind`.
  63     pub(super) fn prefixes(
  64         &self,
  65         place: &'cx Place<'tcx>,
  66         kind: PrefixSet,
  67     ) -> Prefixes<'cx, 'gcx, 'tcx> {
  68         Prefixes {
  69             next: Some(place),
  70             kind,
  71             mir: self.mir,
  72             tcx: self.infcx.tcx,
  73         }
  74     }
  75 }
  76
  77 impl<'cx, 'gcx, 'tcx> Iterator for Prefixes<'cx, 'gcx, 'tcx> {
  78     type Item = &'cx Place<'tcx>;
  79     fn next(&mut self) -> Option<Self::Item> {
  80         let mut cursor = self.next?;
  81
  82         // Post-processing `place`: Enqueue any remaining
  83         // work. Also, `place` may not be a prefix itself, but
  84         // may hold one further down (e.g., we never return
  85         // downcasts here, but may return a base of a downcast).
  86
  87         'cursor: loop {
  88             let proj = match *cursor {
  89                 Place::Promoted(_) |
  90                 Place::Local(_) | // search yielded this leaf
  91                 Place::Static(_) => {
  92                     self.next = None;
  93                     return Some(cursor);
  94                 }
  95
  96                 Place::Projection(ref proj) => proj,
  97             };
  98
  99             match proj.elem {
 100                 ProjectionElem::Field(_ /*field*/, _ /*ty*/) => {
 101                         // FIXME: add union handling
 102                     self.next = Some(&proj.base);
 103                     return Some(cursor);
 104                 }
 105                 ProjectionElem::Downcast(..) |
 106                 ProjectionElem::Subslice { .. } |
 107                 ProjectionElem::ConstantIndex { .. } |
 108                 ProjectionElem::Index(_) => {
 109                     cursor = &proj.base;
 110                     continue 'cursor;
 111                 }
 112                 ProjectionElem::Deref => {
 113                     // (handled below)
 114                 }
 115             }
 116
 117             assert_eq!(proj.elem, ProjectionElem::Deref);
 118
 119             match self.kind {
 120                 PrefixSet::Shallow => {
 121                     // shallow prefixes are found by stripping away
 122                     // fields, but stop at *any* dereference.
 123                     // So we can just stop the traversal now.
 124                     self.next = None;
 125                     return Some(cursor);
 126                 }
 127                 PrefixSet::All => {
 128                     // all prefixes: just blindly enqueue the base
 129                     // of the projection
 130                     self.next = Some(&proj.base);
 131                     return Some(cursor);
 132                 }
 133                 PrefixSet::Supporting => {
 134                     // fall through!
 135                 }
 136             }
 137
 138             assert_eq!(self.kind, PrefixSet::Supporting);
 139             // supporting prefixes: strip away fields and
 140             // derefs, except we stop at the deref of a shared
 141             // reference.
 142
 143             let ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
 144             match ty.sty {
 145                 ty::RawPtr(_) |
 146                 ty::Ref(
 147                     _, /*rgn*/
 148                     _, /*ty*/
 149                     hir::MutImmutable
 150                     ) => {
 151                     // don't continue traversing over derefs of raw pointers or shared borrows.
 152                     self.next = None;
 153                     return Some(cursor);
 154                 }
 155
 156                 ty::Ref(
 157                     _, /*rgn*/
 158                     _, /*ty*/
 159                     hir::MutMutable,
 160                     ) => {
 161                     self.next = Some(&proj.base);
 162                     return Some(cursor);
 163                 }
 164
 165                 ty::Adt(..) if ty.is_box() => {
 166                     self.next = Some(&proj.base);
 167                     return Some(cursor);
 168                 }
 169
 170                 _ => panic!("unknown type fed to Projection Deref."),
 171             }
 172         }
 173     }
 174 }