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
;
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
>>,
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
>>,
29 /// Map from local to all the borrows on that local.
30 pub local_map
: FxHashMap
<mir
::Local
, FxHashSet
<BorrowIndex
>>,
32 pub(crate) locals_state_at_exit
: LocalsStateAtExit
,
35 impl<'tcx
> Index
<BorrowIndex
> for BorrowSet
<'tcx
> {
36 type Output
= BorrowData
<'tcx
>;
38 fn index(&self, index
: BorrowIndex
) -> &BorrowData
<'tcx
> {
39 &self.location_map
[index
.as_usize()]
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
{
49 ActivatedAt(Location
),
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
>,
69 impl<'tcx
> fmt
::Display
for BorrowData
<'tcx
> {
70 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 ",
77 write
!(w
, "&{:?} {}{:?}", self.region
, kind
, self.borrowed_place
)
81 pub enum LocalsStateAtExit
{
83 SomeAreInvalidated { has_storage_dead_or_moved: BitSet<Local> }
,
86 impl LocalsStateAtExit
{
88 locals_are_invalidated_at_exit
: bool
,
90 move_data
: &MoveData
<'tcx
>,
92 struct HasStorageDead(BitSet
<Local
>);
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
) {
102 if locals_are_invalidated_at_exit
{
103 LocalsStateAtExit
::AllAreInvalidated
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
);
113 LocalsStateAtExit
::SomeAreInvalidated { has_storage_dead_or_moved }
118 impl<'tcx
> BorrowSet
<'tcx
> {
122 locals_are_invalidated_at_exit
: bool
,
123 move_data
: &MoveData
<'tcx
>,
125 let mut visitor
= GatherBorrows
{
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
,
139 for (block
, block_data
) in traversal
::preorder(&body
) {
140 visitor
.visit_basic_block_data(block
, block_data
);
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
,
151 pub(crate) fn activations_at_location(&self, location
: Location
) -> &[BorrowIndex
] {
152 self.activation_map
.get(&location
).map_or(&[], |activations
| &activations
[..])
155 pub(crate) fn len(&self) -> usize {
156 self.location_map
.len()
159 pub(crate) fn indices(&self) -> impl Iterator
<Item
= BorrowIndex
> {
160 BorrowIndex
::from_usize(0)..BorrowIndex
::from_usize(self.len())
163 pub(crate) fn iter_enumerated(&self) -> impl Iterator
<Item
= (BorrowIndex
, &BorrowData
<'tcx
>)> {
164 self.indices().zip(self.location_map
.values())
167 pub(crate) fn get_index_of(&self, location
: &Location
) -> Option
<BorrowIndex
> {
168 self.location_map
.get_index_of(location
).map(BorrowIndex
::from
)
172 struct GatherBorrows
<'a
, 'tcx
> {
174 body
: &'a Body
<'tcx
>,
175 location_map
: FxIndexMap
<Location
, BorrowData
<'tcx
>>,
176 activation_map
: FxHashMap
<Location
, Vec
<BorrowIndex
>>,
177 local_map
: FxHashMap
<mir
::Local
, FxHashSet
<BorrowIndex
>>,
179 /// When we encounter a 2-phase borrow statement, it will always
180 /// be assigning into a temporary TEMP:
184 /// We add TEMP into this map with `b`, where `b` is the index of
185 /// the borrow. When we find a later use of this activation, we
186 /// remove from the map (and add to the "tombstone" set below).
187 pending_activations
: FxHashMap
<mir
::Local
, BorrowIndex
>,
189 locals_state_at_exit
: LocalsStateAtExit
,
192 impl<'a
, 'tcx
> Visitor
<'tcx
> for GatherBorrows
<'a
, 'tcx
> {
195 assigned_place
: &mir
::Place
<'tcx
>,
196 rvalue
: &mir
::Rvalue
<'tcx
>,
197 location
: mir
::Location
,
199 if let mir
::Rvalue
::Ref(region
, kind
, ref borrowed_place
) = *rvalue
{
200 if borrowed_place
.ignore_borrow(self.tcx
, self.body
, &self.locals_state_at_exit
) {
201 debug
!("ignoring_borrow of {:?}", borrowed_place
);
205 let region
= region
.to_region_vid();
207 let borrow
= BorrowData
{
210 reserve_location
: location
,
211 activation_location
: TwoPhaseActivation
::NotTwoPhase
,
212 borrowed_place
: *borrowed_place
,
213 assigned_place
: *assigned_place
,
215 let (idx
, _
) = self.location_map
.insert_full(location
, borrow
);
216 let idx
= BorrowIndex
::from(idx
);
218 self.insert_as_pending_if_two_phase(location
, assigned_place
, kind
, idx
);
220 self.local_map
.entry(borrowed_place
.local
).or_default().insert(idx
);
223 self.super_assign(assigned_place
, rvalue
, location
)
226 fn visit_local(&mut self, temp
: Local
, context
: PlaceContext
, location
: Location
) {
227 if !context
.is_use() {
231 // We found a use of some temporary TMP
232 // check whether we (earlier) saw a 2-phase borrow like
235 if let Some(&borrow_index
) = self.pending_activations
.get(&temp
) {
236 let borrow_data
= &mut self.location_map
[borrow_index
.as_usize()];
238 // Watch out: the use of TMP in the borrow itself
239 // doesn't count as an activation. =)
240 if borrow_data
.reserve_location
== location
241 && context
== PlaceContext
::MutatingUse(MutatingUseContext
::Store
)
246 if let TwoPhaseActivation
::ActivatedAt(other_location
) = borrow_data
.activation_location
249 self.body
.source_info(location
).span
,
250 "found two uses for 2-phase borrow temporary {:?}: \
258 // Otherwise, this is the unique later use that we expect.
259 // Double check: This borrow is indeed a two-phase borrow (that is,
260 // we are 'transitioning' from `NotActivated` to `ActivatedAt`) and
261 // we've not found any other activations (checked above).
263 borrow_data
.activation_location
,
264 TwoPhaseActivation
::NotActivated
,
265 "never found an activation for this borrow!",
267 self.activation_map
.entry(location
).or_default().push(borrow_index
);
269 borrow_data
.activation_location
= TwoPhaseActivation
::ActivatedAt(location
);
273 fn visit_rvalue(&mut self, rvalue
: &mir
::Rvalue
<'tcx
>, location
: mir
::Location
) {
274 if let mir
::Rvalue
::Ref(region
, kind
, ref place
) = *rvalue
{
275 // double-check that we already registered a BorrowData for this
277 let borrow_data
= &self.location_map
[&location
];
278 assert_eq
!(borrow_data
.reserve_location
, location
);
279 assert_eq
!(borrow_data
.kind
, kind
);
280 assert_eq
!(borrow_data
.region
, region
.to_region_vid());
281 assert_eq
!(borrow_data
.borrowed_place
, *place
);
284 self.super_rvalue(rvalue
, location
)
288 impl<'a
, 'tcx
> GatherBorrows
<'a
, 'tcx
> {
289 /// If this is a two-phase borrow, then we will record it
290 /// as "pending" until we find the activating use.
291 fn insert_as_pending_if_two_phase(
293 start_location
: Location
,
294 assigned_place
: &mir
::Place
<'tcx
>,
295 kind
: mir
::BorrowKind
,
296 borrow_index
: BorrowIndex
,
299 "Borrows::insert_as_pending_if_two_phase({:?}, {:?}, {:?})",
300 start_location
, assigned_place
, borrow_index
,
303 if !allow_two_phase_borrow(kind
) {
304 debug
!(" -> {:?}", start_location
);
308 // When we encounter a 2-phase borrow statement, it will always
309 // be assigning into a temporary TEMP:
313 // so extract `temp`.
314 let Some(temp
) = assigned_place
.as_local() else {
316 self.body
.source_info(start_location
).span
,
317 "expected 2-phase borrow to assign to a local, not `{:?}`",
322 // Consider the borrow not activated to start. When we find an activation, we'll update
325 let borrow_data
= &mut self.location_map
[borrow_index
.as_usize()];
326 borrow_data
.activation_location
= TwoPhaseActivation
::NotActivated
;
329 // Insert `temp` into the list of pending activations. From
330 // now on, we'll be on the lookout for a use of it. Note that
331 // we are guaranteed that this use will come after the
333 let old_value
= self.pending_activations
.insert(temp
, borrow_index
);
334 if let Some(old_index
) = old_value
{
336 self.body
.source_info(start_location
).span
,
337 "found already pending activation for temp: {:?} \
338 at borrow_index: {:?} with associated data {:?}",
341 self.location_map
[old_index
.as_usize()]