src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs

   1 // Copyright 2018 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 use borrow_check::nll::region_infer::values::{PointIndex, RegionValueElements};
  12 use borrow_check::nll::type_check::liveness::liveness_map::{LiveVar, NllLivenessMap};
  13 use rustc::mir::visit::{PlaceContext, Visitor};
  14 use rustc::mir::{Local, Location, Mir};
  15 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  16 use rustc_data_structures::vec_linked_list as vll;
  17 use util::liveness::{categorize, DefUse, LiveVariableMap};
  18
  19 /// A map that cross references each local with the locations where it
  20 /// is defined (assigned), used, or dropped. Used during liveness
  21 /// computation.
  22 crate struct LocalUseMap<'me> {
  23     liveness_map: &'me NllLivenessMap,
  24
  25     /// Head of a linked list of **definitions** of each variable --
  26     /// definition in this context means assignment, e.g. `x` is
  27     /// defined in `x = y` but not `y`; that first def is the head of
  28     /// a linked list that lets you enumerate all places the variable
  29     /// is assigned.
  30     first_def_at: IndexVec<LiveVar, Option<AppearanceIndex>>,
  31
  32     /// Head of a linked list of **uses** of each variable -- use in
  33     /// this context means that the existing value of the variable is
  34     /// read or modified. e.g., `y` is used in `x = y` but not `x`.
  35     /// Note that `DROP(x)` terminators are excluded from this list.
  36     first_use_at: IndexVec<LiveVar, Option<AppearanceIndex>>,
  37
  38     /// Head of a linked list of **drops** of each variable -- these
  39     /// are a special category of uses corresponding to the drop that
  40     /// we add for each local variable.
  41     first_drop_at: IndexVec<LiveVar, Option<AppearanceIndex>>,
  42
  43     appearances: IndexVec<AppearanceIndex, Appearance>,
  44 }
  45
  46 struct Appearance {
  47     point_index: PointIndex,
  48     next: Option<AppearanceIndex>,
  49 }
  50
  51 newtype_index! {
  52     pub struct AppearanceIndex { .. }
  53 }
  54
  55 impl vll::LinkElem for Appearance {
  56     type LinkIndex = AppearanceIndex;
  57
  58     fn next(elem: &Self) -> Option<AppearanceIndex> {
  59         elem.next
  60     }
  61 }
  62
  63 impl LocalUseMap<'me> {
  64     crate fn build(
  65         liveness_map: &'me NllLivenessMap,
  66         elements: &RegionValueElements,
  67         mir: &Mir<'_>,
  68     ) -> Self {
  69         let nones = IndexVec::from_elem_n(None, liveness_map.num_variables());
  70         let mut local_use_map = LocalUseMap {
  71             liveness_map,
  72             first_def_at: nones.clone(),
  73             first_use_at: nones.clone(),
  74             first_drop_at: nones,
  75             appearances: IndexVec::new(),
  76         };
  77
  78         LocalUseMapBuild {
  79             local_use_map: &mut local_use_map,
  80             elements,
  81         }.visit_mir(mir);
  82
  83         local_use_map
  84     }
  85
  86     crate fn defs(&self, local: LiveVar) -> impl Iterator<Item = PointIndex> + '_ {
  87         vll::iter(self.first_def_at[local], &self.appearances)
  88             .map(move |aa| self.appearances[aa].point_index)
  89     }
  90
  91     crate fn uses(&self, local: LiveVar) -> impl Iterator<Item = PointIndex> + '_ {
  92         vll::iter(self.first_use_at[local], &self.appearances)
  93             .map(move |aa| self.appearances[aa].point_index)
  94     }
  95
  96     crate fn drops(&self, local: LiveVar) -> impl Iterator<Item = PointIndex> + '_ {
  97         vll::iter(self.first_drop_at[local], &self.appearances)
  98             .map(move |aa| self.appearances[aa].point_index)
  99     }
 100 }
 101
 102 struct LocalUseMapBuild<'me, 'map: 'me> {
 103     local_use_map: &'me mut LocalUseMap<'map>,
 104     elements: &'me RegionValueElements,
 105 }
 106
 107 impl LocalUseMapBuild<'_, '_> {
 108     fn insert_def(&mut self, local: LiveVar, location: Location) {
 109         Self::insert(
 110             self.elements,
 111             &mut self.local_use_map.first_def_at[local],
 112             &mut self.local_use_map.appearances,
 113             location,
 114         );
 115     }
 116
 117     fn insert_use(&mut self, local: LiveVar, location: Location) {
 118         Self::insert(
 119             self.elements,
 120             &mut self.local_use_map.first_use_at[local],
 121             &mut self.local_use_map.appearances,
 122             location,
 123         );
 124     }
 125
 126     fn insert_drop(&mut self, local: LiveVar, location: Location) {
 127         Self::insert(
 128             self.elements,
 129             &mut self.local_use_map.first_drop_at[local],
 130             &mut self.local_use_map.appearances,
 131             location,
 132         );
 133     }
 134
 135     fn insert(
 136         elements: &RegionValueElements,
 137         first_appearance: &mut Option<AppearanceIndex>,
 138         appearances: &mut IndexVec<AppearanceIndex, Appearance>,
 139         location: Location,
 140     ) {
 141         let point_index = elements.point_from_location(location);
 142         let appearance_index = appearances.push(Appearance {
 143             point_index,
 144             next: *first_appearance,
 145         });
 146         *first_appearance = Some(appearance_index);
 147     }
 148 }
 149
 150 impl Visitor<'tcx> for LocalUseMapBuild<'_, '_> {
 151     fn visit_local(&mut self, &local: &Local, context: PlaceContext<'tcx>, location: Location) {
 152         if let Some(local_with_region) = self.local_use_map.liveness_map.from_local(local) {
 153             match categorize(context) {
 154                 Some(DefUse::Def) => self.insert_def(local_with_region, location),
 155                 Some(DefUse::Use) => self.insert_use(local_with_region, location),
 156                 Some(DefUse::Drop) => self.insert_drop(local_with_region, location),
 157                 _ => (),
 158             }
 159         }
 160     }
 161 }