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 = self.next?;
  91
  92         // Post-processing `place`: Enqueue any remaining
  93         // work. Also, `place` may not be a prefix itself, but
  94         // may hold one further down (e.g. we never return
  95         // downcasts here, but may return a base of a downcast).
  96
  97         'cursor: loop {
  98             let proj = match *cursor {
  99                 Place::Promoted(_) |
 100                 Place::Local(_) | // search yielded this leaf
 101                 Place::Static(_) => {
 102                     self.next = None;
 103                     return Some(cursor);
 104                 }
 105
 106                 Place::Projection(ref proj) => proj,
 107             };
 108
 109             match proj.elem {
 110                 ProjectionElem::Field(_ /*field*/, _ /*ty*/) => {
 111                         // FIXME: add union handling
 112                     self.next = Some(&proj.base);
 113                     return Some(cursor);
 114                 }
 115                 ProjectionElem::Downcast(..) |
 116                 ProjectionElem::Subslice { .. } |
 117                 ProjectionElem::ConstantIndex { .. } |
 118                 ProjectionElem::Index(_) => {
 119                     cursor = &proj.base;
 120                     continue 'cursor;
 121                 }
 122                 ProjectionElem::Deref => {
 123                     // (handled below)
 124                 }
 125             }
 126
 127             assert_eq!(proj.elem, ProjectionElem::Deref);
 128
 129             match self.kind {
 130                 PrefixSet::Shallow => {
 131                     // shallow prefixes are found by stripping away
 132                     // fields, but stop at *any* dereference.
 133                     // So we can just stop the traversal now.
 134                     self.next = None;
 135                     return Some(cursor);
 136                 }
 137                 PrefixSet::All => {
 138                     // all prefixes: just blindly enqueue the base
 139                     // of the projection
 140                     self.next = Some(&proj.base);
 141                     return Some(cursor);
 142                 }
 143                 PrefixSet::Supporting => {
 144                     // fall through!
 145                 }
 146             }
 147
 148             assert_eq!(self.kind, PrefixSet::Supporting);
 149             // supporting prefixes: strip away fields and
 150             // derefs, except we stop at the deref of a shared
 151             // reference.
 152
 153             let ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
 154             match ty.sty {
 155                 ty::RawPtr(_) |
 156                 ty::Ref(
 157                     _, /*rgn*/
 158                     _, /*ty*/
 159                     hir::MutImmutable
 160                     ) => {
 161                     // don't continue traversing over derefs of raw pointers or shared borrows.
 162                     self.next = None;
 163                     return Some(cursor);
 164                 }
 165
 166                 ty::Ref(
 167                     _, /*rgn*/
 168                     _, /*ty*/
 169                     hir::MutMutable,
 170                     ) => {
 171                     self.next = Some(&proj.base);
 172                     return Some(cursor);
 173                 }
 174
 175                 ty::Adt(..) if ty.is_box() => {
 176                     self.next = Some(&proj.base);
 177                     return Some(cursor);
 178                 }
 179
 180                 _ => panic!("unknown type fed to Projection Deref."),
 181             }
 182         }
 183     }
 184 }