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