rustc_borrowck/
borrow_set.rs

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

rustc_borrowck/
borrow_set.rs
