src/librustc_mir/borrow_check/prefixes.rs

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