1 use crate::nll::ToRegionVid; 2 use crate::path_utils::allow_two_phase_borrow; 3 use crate::place_ext::PlaceExt; 4 use crate::BorrowIndex; 5 use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexMap}; 6 use rustc_index::bit_set::BitSet; 7 use rustc_middle::mir::traversal; 8 use rustc_middle::mir::visit::{MutatingUseContext, NonUseContext, PlaceContext, Visitor}; 9 use rustc_middle::mir::{self, Body, Local, Location}; 10 use rustc_middle::ty::{RegionVid, TyCtxt}; 11 use rustc_mir_dataflow::move_paths::MoveData; 12 use std::fmt; 13 use std::ops::Index; 14 15 pub struct BorrowSet<'tcx> { 16 /// The fundamental map relating bitvector indexes to the borrows 17 /// in the MIR. Each borrow is also uniquely identified in the MIR 18 /// by the `Location` of the assignment statement in which it 19 /// appears on the right hand side. Thus the location is the map 20 /// key, and its position in the map corresponds to `BorrowIndex`. 21 pub location_map: FxIndexMap<Location, BorrowData<'tcx>>, 22 23 /// Locations which activate borrows. 24 /// NOTE: a given location may activate more than one borrow in the future 25 /// when more general two-phase borrow support is introduced, but for now we 26 /// only need to store one borrow index. 27 pub activation_map: FxHashMap<Location, Vec<BorrowIndex>>, 28 29 /// Map from local to all the borrows on that local. 30 pub local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>, 31 32 crate locals_state_at_exit: LocalsStateAtExit, 33 } 34 35 impl<'tcx> Index<BorrowIndex> for BorrowSet<'tcx> { 36 type Output = BorrowData<'tcx>; 37 index(&self, index: BorrowIndex) -> &BorrowData<'tcx>38 fn index(&self, index: BorrowIndex) -> &BorrowData<'tcx> { 39 &self.location_map[index.as_usize()] 40 } 41 } 42 43 /// Location where a two-phase borrow is activated, if a borrow 44 /// is in fact a two-phase borrow. 45 #[derive(Copy, Clone, PartialEq, Eq, Debug)] 46 pub enum TwoPhaseActivation { 47 NotTwoPhase, 48 NotActivated, 49 ActivatedAt(Location), 50 } 51 52 #[derive(Debug, Clone)] 53 pub struct BorrowData<'tcx> { 54 /// Location where the borrow reservation starts. 55 /// In many cases, this will be equal to the activation location but not always. 56 pub reserve_location: Location, 57 /// Location where the borrow is activated. 58 pub activation_location: TwoPhaseActivation, 59 /// What kind of borrow this is 60 pub kind: mir::BorrowKind, 61 /// The region for which this borrow is live 62 pub region: RegionVid, 63 /// Place from which we are borrowing 64 pub borrowed_place: mir::Place<'tcx>, 65 /// Place to which the borrow was stored 66 pub assigned_place: mir::Place<'tcx>, 67 } 68 69 impl<'tcx> fmt::Display for BorrowData<'tcx> { fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result70 fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result { 71 let kind = match self.kind { 72 mir::BorrowKind::Shared => "", 73 mir::BorrowKind::Shallow => "shallow ", 74 mir::BorrowKind::Unique => "uniq ", 75 mir::BorrowKind::Mut { .. } => "mut ", 76 }; 77 write!(w, "&{:?} {}{:?}", self.region, kind, self.borrowed_place) 78 } 79 } 80 81 pub enum LocalsStateAtExit { 82 AllAreInvalidated, 83 SomeAreInvalidated { has_storage_dead_or_moved: BitSet<Local> }, 84 } 85 86 impl LocalsStateAtExit { build( locals_are_invalidated_at_exit: bool, body: &Body<'tcx>, move_data: &MoveData<'tcx>, ) -> Self87 fn build( 88 locals_are_invalidated_at_exit: bool, 89 body: &Body<'tcx>, 90 move_data: &MoveData<'tcx>, 91 ) -> Self { 92 struct HasStorageDead(BitSet<Local>); 93 94 impl<'tcx> Visitor<'tcx> for HasStorageDead { 95 fn visit_local(&mut self, local: &Local, ctx: PlaceContext, _: Location) { 96 if ctx == PlaceContext::NonUse(NonUseContext::StorageDead) { 97 self.0.insert(*local); 98 } 99 } 100 } 101 102 if locals_are_invalidated_at_exit { 103 LocalsStateAtExit::AllAreInvalidated 104 } else { 105 let mut has_storage_dead = HasStorageDead(BitSet::new_empty(body.local_decls.len())); 106 has_storage_dead.visit_body(&body); 107 let mut has_storage_dead_or_moved = has_storage_dead.0; 108 for move_out in &move_data.moves { 109 if let Some(index) = move_data.base_local(move_out.path) { 110 has_storage_dead_or_moved.insert(index); 111 } 112 } 113 LocalsStateAtExit::SomeAreInvalidated { has_storage_dead_or_moved } 114 } 115 } 116 } 117 118 impl<'tcx> BorrowSet<'tcx> { build( tcx: TyCtxt<'tcx>, body: &Body<'tcx>, locals_are_invalidated_at_exit: bool, move_data: &MoveData<'tcx>, ) -> Self119 pub fn build( 120 tcx: TyCtxt<'tcx>, 121 body: &Body<'tcx>, 122 locals_are_invalidated_at_exit: bool, 123 move_data: &MoveData<'tcx>, 124 ) -> Self { 125 let mut visitor = GatherBorrows { 126 tcx, 127 body: &body, 128 location_map: Default::default(), 129 activation_map: Default::default(), 130 local_map: Default::default(), 131 pending_activations: Default::default(), 132 locals_state_at_exit: LocalsStateAtExit::build( 133 locals_are_invalidated_at_exit, 134 body, 135 move_data, 136 ), 137 }; 138 139 for (block, block_data) in traversal::preorder(&body) { 140 visitor.visit_basic_block_data(block, block_data); 141 } 142 143 BorrowSet { 144 location_map: visitor.location_map, 145 activation_map: visitor.activation_map, 146 local_map: visitor.local_map, 147 locals_state_at_exit: visitor.locals_state_at_exit, 148 } 149 } 150 activations_at_location(&self, location: Location) -> &[BorrowIndex]151 crate fn activations_at_location(&self, location: Location) -> &[BorrowIndex] { 152 self.activation_map.get(&location).map_or(&[], |activations| &activations[..]) 153 } 154 len(&self) -> usize155 crate fn len(&self) -> usize { 156 self.location_map.len() 157 } 158 indices(&self) -> impl Iterator<Item = BorrowIndex>159 crate fn indices(&self) -> impl Iterator<Item = BorrowIndex> { 160 BorrowIndex::from_usize(0)..BorrowIndex::from_usize(self.len()) 161 } 162 iter_enumerated(&self) -> impl Iterator<Item = (BorrowIndex, &BorrowData<'tcx>)>163 crate fn iter_enumerated(&self) -> impl Iterator<Item = (BorrowIndex, &BorrowData<'tcx>)> { 164 self.indices().zip(self.location_map.values()) 165 } 166 get_index_of(&self, location: &Location) -> Option<BorrowIndex>167 crate fn get_index_of(&self, location: &Location) -> Option<BorrowIndex> { 168 self.location_map.get_index_of(location).map(BorrowIndex::from) 169 } 170 contains(&self, location: &Location) -> bool171 crate fn contains(&self, location: &Location) -> bool { 172 self.location_map.contains_key(location) 173 } 174 } 175 176 struct GatherBorrows<'a, 'tcx> { 177 tcx: TyCtxt<'tcx>, 178 body: &'a Body<'tcx>, 179 location_map: FxIndexMap<Location, BorrowData<'tcx>>, 180 activation_map: FxHashMap<Location, Vec<BorrowIndex>>, 181 local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>, 182 183 /// When we encounter a 2-phase borrow statement, it will always 184 /// be assigning into a temporary TEMP: 185 /// 186 /// TEMP = &foo 187 /// 188 /// We add TEMP into this map with `b`, where `b` is the index of 189 /// the borrow. When we find a later use of this activation, we 190 /// remove from the map (and add to the "tombstone" set below). 191 pending_activations: FxHashMap<mir::Local, BorrowIndex>, 192 193 locals_state_at_exit: LocalsStateAtExit, 194 } 195 196 impl<'a, 'tcx> Visitor<'tcx> for GatherBorrows<'a, 'tcx> { visit_assign( &mut self, assigned_place: &mir::Place<'tcx>, rvalue: &mir::Rvalue<'tcx>, location: mir::Location, )197 fn visit_assign( 198 &mut self, 199 assigned_place: &mir::Place<'tcx>, 200 rvalue: &mir::Rvalue<'tcx>, 201 location: mir::Location, 202 ) { 203 if let mir::Rvalue::Ref(region, kind, ref borrowed_place) = *rvalue { 204 if borrowed_place.ignore_borrow(self.tcx, self.body, &self.locals_state_at_exit) { 205 debug!("ignoring_borrow of {:?}", borrowed_place); 206 return; 207 } 208 209 let region = region.to_region_vid(); 210 211 let borrow = BorrowData { 212 kind, 213 region, 214 reserve_location: location, 215 activation_location: TwoPhaseActivation::NotTwoPhase, 216 borrowed_place: *borrowed_place, 217 assigned_place: *assigned_place, 218 }; 219 let (idx, _) = self.location_map.insert_full(location, borrow); 220 let idx = BorrowIndex::from(idx); 221 222 self.insert_as_pending_if_two_phase(location, assigned_place, kind, idx); 223 224 self.local_map.entry(borrowed_place.local).or_default().insert(idx); 225 } 226 227 self.super_assign(assigned_place, rvalue, location) 228 } 229 visit_local(&mut self, temp: &Local, context: PlaceContext, location: Location)230 fn visit_local(&mut self, temp: &Local, context: PlaceContext, location: Location) { 231 if !context.is_use() { 232 return; 233 } 234 235 // We found a use of some temporary TMP 236 // check whether we (earlier) saw a 2-phase borrow like 237 // 238 // TMP = &mut place 239 if let Some(&borrow_index) = self.pending_activations.get(temp) { 240 let borrow_data = &mut self.location_map[borrow_index.as_usize()]; 241 242 // Watch out: the use of TMP in the borrow itself 243 // doesn't count as an activation. =) 244 if borrow_data.reserve_location == location 245 && context == PlaceContext::MutatingUse(MutatingUseContext::Store) 246 { 247 return; 248 } 249 250 if let TwoPhaseActivation::ActivatedAt(other_location) = borrow_data.activation_location 251 { 252 span_bug!( 253 self.body.source_info(location).span, 254 "found two uses for 2-phase borrow temporary {:?}: \ 255 {:?} and {:?}", 256 temp, 257 location, 258 other_location, 259 ); 260 } 261 262 // Otherwise, this is the unique later use that we expect. 263 // Double check: This borrow is indeed a two-phase borrow (that is, 264 // we are 'transitioning' from `NotActivated` to `ActivatedAt`) and 265 // we've not found any other activations (checked above). 266 assert_eq!( 267 borrow_data.activation_location, 268 TwoPhaseActivation::NotActivated, 269 "never found an activation for this borrow!", 270 ); 271 self.activation_map.entry(location).or_default().push(borrow_index); 272 273 borrow_data.activation_location = TwoPhaseActivation::ActivatedAt(location); 274 } 275 } 276 visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: mir::Location)277 fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: mir::Location) { 278 if let mir::Rvalue::Ref(region, kind, ref place) = *rvalue { 279 // double-check that we already registered a BorrowData for this 280 281 let borrow_data = &self.location_map[&location]; 282 assert_eq!(borrow_data.reserve_location, location); 283 assert_eq!(borrow_data.kind, kind); 284 assert_eq!(borrow_data.region, region.to_region_vid()); 285 assert_eq!(borrow_data.borrowed_place, *place); 286 } 287 288 self.super_rvalue(rvalue, location) 289 } 290 } 291 292 impl<'a, 'tcx> GatherBorrows<'a, 'tcx> { 293 /// If this is a two-phase borrow, then we will record it 294 /// as "pending" until we find the activating use. insert_as_pending_if_two_phase( &mut self, start_location: Location, assigned_place: &mir::Place<'tcx>, kind: mir::BorrowKind, borrow_index: BorrowIndex, )295 fn insert_as_pending_if_two_phase( 296 &mut self, 297 start_location: Location, 298 assigned_place: &mir::Place<'tcx>, 299 kind: mir::BorrowKind, 300 borrow_index: BorrowIndex, 301 ) { 302 debug!( 303 "Borrows::insert_as_pending_if_two_phase({:?}, {:?}, {:?})", 304 start_location, assigned_place, borrow_index, 305 ); 306 307 if !allow_two_phase_borrow(kind) { 308 debug!(" -> {:?}", start_location); 309 return; 310 } 311 312 // When we encounter a 2-phase borrow statement, it will always 313 // be assigning into a temporary TEMP: 314 // 315 // TEMP = &foo 316 // 317 // so extract `temp`. 318 let Some(temp) = assigned_place.as_local() else { 319 span_bug!( 320 self.body.source_info(start_location).span, 321 "expected 2-phase borrow to assign to a local, not `{:?}`", 322 assigned_place, 323 ); 324 }; 325 326 // Consider the borrow not activated to start. When we find an activation, we'll update 327 // this field. 328 { 329 let borrow_data = &mut self.location_map[borrow_index.as_usize()]; 330 borrow_data.activation_location = TwoPhaseActivation::NotActivated; 331 } 332 333 // Insert `temp` into the list of pending activations. From 334 // now on, we'll be on the lookout for a use of it. Note that 335 // we are guaranteed that this use will come after the 336 // assignment. 337 let old_value = self.pending_activations.insert(temp, borrow_index); 338 if let Some(old_index) = old_value { 339 span_bug!( 340 self.body.source_info(start_location).span, 341 "found already pending activation for temp: {:?} \ 342 at borrow_index: {:?} with associated data {:?}", 343 temp, 344 old_index, 345 self.location_map[old_index.as_usize()] 346 ); 347 } 348 } 349 } 350