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::mir::{Place, PlaceRef, ProjectionElem, ReadOnlyBodyAndCache};
  13 use rustc::ty::{self, TyCtxt};
  14 use rustc_hir as hir;
  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.local == other.local
  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 { local: _, projection: [] } => {
  73                     self.next = None;
  74                     return Some(cursor);
  75                 }
  76                 PlaceRef { local: _, projection: [proj_base @ .., elem] } => {
  77                     match elem {
  78                         ProjectionElem::Field(_ /*field*/, _ /*ty*/) => {
  79                             // FIXME: add union handling
  80                             self.next =
  81                                 Some(PlaceRef { local: cursor.local, projection: proj_base });
  82                             return Some(cursor);
  83                         }
  84                         ProjectionElem::Downcast(..)
  85                         | ProjectionElem::Subslice { .. }
  86                         | ProjectionElem::ConstantIndex { .. }
  87                         | ProjectionElem::Index(_) => {
  88                             cursor = PlaceRef { local: cursor.local, projection: proj_base };
  89                             continue 'cursor;
  90                         }
  91                         ProjectionElem::Deref => {
  92                             // (handled below)
  93                         }
  94                     }
  95
  96                     assert_eq!(*elem, ProjectionElem::Deref);
  97
  98                     match self.kind {
  99                         PrefixSet::Shallow => {
 100                             // Shallow prefixes are found by stripping away
 101                             // fields, but stop at *any* dereference.
 102                             // So we can just stop the traversal now.
 103                             self.next = None;
 104                             return Some(cursor);
 105                         }
 106                         PrefixSet::All => {
 107                             // All prefixes: just blindly enqueue the base
 108                             // of the projection.
 109                             self.next =
 110                                 Some(PlaceRef { local: cursor.local, projection: proj_base });
 111                             return Some(cursor);
 112                         }
 113                         PrefixSet::Supporting => {
 114                             // Fall through!
 115                         }
 116                     }
 117
 118                     assert_eq!(self.kind, PrefixSet::Supporting);
 119                     // Supporting prefixes: strip away fields and
 120                     // derefs, except we stop at the deref of a shared
 121                     // reference.
 122
 123                     let ty = Place::ty_from(cursor.local, proj_base, *self.body, self.tcx).ty;
 124                     match ty.kind {
 125                         ty::RawPtr(_) | ty::Ref(_ /*rgn*/, _ /*ty*/, hir::Mutability::Not) => {
 126                             // don't continue traversing over derefs of raw pointers or shared
 127                             // borrows.
 128                             self.next = None;
 129                             return Some(cursor);
 130                         }
 131
 132                         ty::Ref(_ /*rgn*/, _ /*ty*/, hir::Mutability::Mut) => {
 133                             self.next =
 134                                 Some(PlaceRef { local: cursor.local, projection: proj_base });
 135                             return Some(cursor);
 136                         }
 137
 138                         ty::Adt(..) if ty.is_box() => {
 139                             self.next =
 140                                 Some(PlaceRef { local: cursor.local, projection: proj_base });
 141                             return Some(cursor);
 142                         }
 143
 144                         _ => panic!("unknown type fed to Projection Deref."),
 145                     }
 146                 }
 147             }
 148         }
 149     }
 150 }