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::{Body, Place, PlaceBase, PlaceRef, ProjectionElem};
  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: &'cx Body<'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 {
  57             next: Some(place_ref),
  58             kind,
  59             body: self.body,
  60             tcx: self.infcx.tcx,
  61         }
  62     }
  63 }
  64
  65 impl<'cx, 'tcx> Iterator for Prefixes<'cx, 'tcx> {
  66     type Item = PlaceRef<'cx, 'tcx>;
  67     fn next(&mut self) -> Option<Self::Item> {
  68         let mut cursor = self.next?;
  69
  70         // Post-processing `place`: Enqueue any remaining
  71         // work. Also, `place` may not be a prefix itself, but
  72         // may hold one further down (e.g., we never return
  73         // downcasts here, but may return a base of a downcast).
  74
  75         'cursor: loop {
  76             match &cursor {
  77                 PlaceRef {
  78                     base: PlaceBase::Local(_),
  79                     projection: [],
  80                 }
  81                 | // search yielded this leaf
  82                 PlaceRef {
  83                     base: PlaceBase::Static(_),
  84                     projection: [],
  85                 } => {
  86                     self.next = None;
  87                     return Some(cursor);
  88                 }
  89                 PlaceRef {
  90                     base: _,
  91                     projection: [proj_base @ .., elem],
  92                 } => {
  93                     match elem {
  94                         ProjectionElem::Field(_ /*field*/, _ /*ty*/) => {
  95                             // FIXME: add union handling
  96                             self.next = Some(PlaceRef {
  97                                 base: cursor.base,
  98                                 projection: proj_base,
  99                             });
 100                             return Some(cursor);
 101                         }
 102                         ProjectionElem::Downcast(..) |
 103                         ProjectionElem::Subslice { .. } |
 104                         ProjectionElem::ConstantIndex { .. } |
 105                         ProjectionElem::Index(_) => {
 106                             cursor = PlaceRef {
 107                                 base: cursor.base,
 108                                 projection: proj_base,
 109                             };
 110                             continue 'cursor;
 111                         }
 112                         ProjectionElem::Deref => {
 113                             // (handled below)
 114                         }
 115                     }
 116
 117                     assert_eq!(*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(PlaceRef {
 131                                 base: cursor.base,
 132                                 projection: proj_base,
 133                             });
 134                             return Some(cursor);
 135                         }
 136                         PrefixSet::Supporting => {
 137                             // Fall through!
 138                         }
 139                     }
 140
 141                     assert_eq!(self.kind, PrefixSet::Supporting);
 142                     // Supporting prefixes: strip away fields and
 143                     // derefs, except we stop at the deref of a shared
 144                     // reference.
 145
 146                     let ty = Place::ty_from(cursor.base, proj_base, self.body, self.tcx).ty;
 147                     match ty.kind {
 148                         ty::RawPtr(_) |
 149                         ty::Ref(
 150                             _, /*rgn*/
 151                             _, /*ty*/
 152                             hir::MutImmutable
 153                             ) => {
 154                             // don't continue traversing over derefs of raw pointers or shared
 155                             // borrows.
 156                             self.next = None;
 157                             return Some(cursor);
 158                         }
 159
 160                         ty::Ref(
 161                             _, /*rgn*/
 162                             _, /*ty*/
 163                             hir::MutMutable,
 164                             ) => {
 165                             self.next = Some(PlaceRef {
 166                                 base: cursor.base,
 167                                 projection: proj_base,
 168                             });
 169                             return Some(cursor);
 170                         }
 171
 172                         ty::Adt(..) if ty.is_box() => {
 173                             self.next = Some(PlaceRef {
 174                                 base: cursor.base,
 175                                 projection: proj_base,
 176                             });
 177                             return Some(cursor);
 178                         }
 179
 180                         _ => panic!("unknown type fed to Projection Deref."),
 181                     }
 182                 }
 183             }
 184         }
 185     }
 186 }