rustc_borrowck/polonius/legacy/
location.rs

Help
1use rustc_index::IndexVec;
2use rustc_middle::mir::{BasicBlock, Body, Location};
3use tracing::debug;
4
5/// Maps between a MIR Location, which identifies a particular
6/// statement within a basic block, to a "rich location", which
7/// identifies at a finer granularity. In particular, we distinguish
8/// the *start* of a statement and the *mid-point*. The mid-point is
9/// the point *just* before the statement takes effect; in particular,
10/// for an assignment `A = B`, it is the point where B is about to be
11/// written into A. This mid-point is a kind of hack to work around
12/// our inability to track the position information at sufficient
13/// granularity through outlives relations; however, the rich location
14/// table serves another purpose: it compresses locations from
15/// multiple words into a single u32.
16pub struct PoloniusLocationTable {
17    num_points: usize,
18    statements_before_block: IndexVec<BasicBlock, usize>,
19}
20
21rustc_index::newtype_index! {
22    #[orderable]
23    #[debug_format = "LocationIndex({})"]
24    pub struct LocationIndex {}
25}
26
27#[derive(Copy, Clone, Debug)]
28pub enum RichLocation {
29    Start(Location),
30    Mid(Location),
31}
32
33impl PoloniusLocationTable {
34    pub(crate) fn new(body: &Body<'_>) -> Self {
35        let mut num_points = 0;
36        let statements_before_block = body
37            .basic_blocks
38            .iter()
39            .map(|block_data| {
40                let v = num_points;
41                num_points += (block_data.statements.len() + 1) * 2;
42                v
43            })
44            .collect();
45
46        debug!("PoloniusLocationTable(statements_before_block={:#?})", statements_before_block);
47        debug!("PoloniusLocationTable: num_points={:#?}", num_points);
48
49        Self { num_points, statements_before_block }
50    }
51
52    pub fn all_points(&self) -> impl Iterator<Item = LocationIndex> {
53        (0..self.num_points).map(LocationIndex::from_usize)
54    }
55
56    pub fn start_index(&self, location: Location) -> LocationIndex {
57        let Location { block, statement_index } = location;
58        let start_index = self.statements_before_block[block];
59        LocationIndex::from_usize(start_index + statement_index * 2)
60    }
61
62    pub fn mid_index(&self, location: Location) -> LocationIndex {
63        let Location { block, statement_index } = location;
64        let start_index = self.statements_before_block[block];
65        LocationIndex::from_usize(start_index + statement_index * 2 + 1)
66    }
67
68    pub fn to_rich_location(&self, index: LocationIndex) -> RichLocation {
69        let point_index = index.index();
70
71        // Find the basic block. We have a vector with the
72        // starting index of the statement in each block. Imagine
73        // we have statement #22, and we have a vector like:
74        //
75        // [0, 10, 20]
76        //
77        // In that case, this represents point_index 2 of
78        // basic block BB2. We know this because BB0 accounts for
79        // 0..10, BB1 accounts for 11..20, and BB2 accounts for
80        // 20...
81        //
82        // To compute this, we could do a binary search, but
83        // because I am lazy we instead iterate through to find
84        // the last point where the "first index" (0, 10, or 20)
85        // was less than the statement index (22). In our case, this will
86        // be (BB2, 20).
87        let (block, &first_index) = self
88            .statements_before_block
89            .iter_enumerated()
90            .rfind(|&(_, &first_index)| first_index <= point_index)
91            .unwrap();
92
93        let statement_index = (point_index - first_index) / 2;
94        if index.is_start() {
95            RichLocation::Start(Location { block, statement_index })
96        } else {
97            RichLocation::Mid(Location { block, statement_index })
98        }
99    }
100
101    pub fn to_location(&self, index: LocationIndex) -> Location {
102        match self.to_rich_location(index) {
103            RichLocation::Start(location) => location,
104            RichLocation::Mid(location) => location,
105        }
106    }
107}
108
109impl LocationIndex {
110    fn is_start(self) -> bool {
111        // even indices are start points; odd indices are mid points
112        (self.index() % 2) == 0
113    }
114}
rustc_borrowck/polonius/legacy/location.rs

rustc_borrowck/polonius/legacy/
location.rs
