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.
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.
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};
19 /// A map that cross references each local with the locations where it
20 /// is defined (assigned), used, or dropped. Used during liveness
22 crate struct LocalUseMap<'me> {
23 liveness_map: &'me NllLivenessMap,
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
30 first_def_at: IndexVec<LiveVar, Option<AppearanceIndex>>,
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>>,
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>>,
43 appearances: IndexVec<AppearanceIndex, Appearance>,
47 point_index: PointIndex,
48 next: Option<AppearanceIndex>,
51 newtype_index!(AppearanceIndex);
53 impl vll::LinkElem for Appearance {
54 type LinkIndex = AppearanceIndex;
56 fn next(elem: &Self) -> Option<AppearanceIndex> {
61 impl LocalUseMap<'me> {
63 liveness_map: &'me NllLivenessMap,
64 elements: &RegionValueElements,
67 let nones = IndexVec::from_elem_n(None, liveness_map.num_variables());
68 let mut local_use_map = LocalUseMap {
70 first_def_at: nones.clone(),
71 first_use_at: nones.clone(),
73 appearances: IndexVec::new(),
77 local_use_map: &mut local_use_map,
84 crate fn defs(&self, local: LiveVar) -> impl Iterator<Item = PointIndex> + '_ {
85 vll::iter(self.first_def_at[local], &self.appearances)
86 .map(move |aa| self.appearances[aa].point_index)
89 crate fn uses(&self, local: LiveVar) -> impl Iterator<Item = PointIndex> + '_ {
90 vll::iter(self.first_use_at[local], &self.appearances)
91 .map(move |aa| self.appearances[aa].point_index)
94 crate fn drops(&self, local: LiveVar) -> impl Iterator<Item = PointIndex> + '_ {
95 vll::iter(self.first_drop_at[local], &self.appearances)
96 .map(move |aa| self.appearances[aa].point_index)
100 struct LocalUseMapBuild<'me, 'map: 'me> {
101 local_use_map: &'me mut LocalUseMap<'map>,
102 elements: &'me RegionValueElements,
105 impl LocalUseMapBuild<'_, '_> {
106 fn insert_def(&mut self, local: LiveVar, location: Location) {
109 &mut self.local_use_map.first_def_at[local],
110 &mut self.local_use_map.appearances,
115 fn insert_use(&mut self, local: LiveVar, location: Location) {
118 &mut self.local_use_map.first_use_at[local],
119 &mut self.local_use_map.appearances,
124 fn insert_drop(&mut self, local: LiveVar, location: Location) {
127 &mut self.local_use_map.first_drop_at[local],
128 &mut self.local_use_map.appearances,
134 elements: &RegionValueElements,
135 first_appearance: &mut Option<AppearanceIndex>,
136 appearances: &mut IndexVec<AppearanceIndex, Appearance>,
139 let point_index = elements.point_from_location(location);
140 let appearance_index = appearances.push(Appearance {
142 next: *first_appearance,
144 *first_appearance = Some(appearance_index);
148 impl Visitor<'tcx> for LocalUseMapBuild<'_, '_> {
149 fn visit_local(&mut self, &local: &Local, context: PlaceContext<'tcx>, location: Location) {
150 if let Some(local_with_region) = self.local_use_map.liveness_map.from_local(local) {
151 match categorize(context) {
152 Some(DefUse::Def) => self.insert_def(local_with_region, location),
153 Some(DefUse::Use) => self.insert_use(local_with_region, location),
154 Some(DefUse::Drop) => self.insert_drop(local_with_region, location),