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