]>
git.proxmox.com Git - rustc.git/blob - compiler/rustc_mir_dataflow/src/move_paths/mod.rs
1 use crate::un_derefer
::UnDerefer
;
2 use rustc_data_structures
::fx
::FxHashMap
;
3 use rustc_index
::{IndexSlice, IndexVec}
;
4 use rustc_middle
::mir
::*;
5 use rustc_middle
::ty
::{ParamEnv, Ty, TyCtxt}
;
7 use smallvec
::SmallVec
;
10 use std
::ops
::{Index, IndexMut}
;
12 use self::abs_domain
::{AbstractElem, Lift}
;
16 rustc_index
::newtype_index
! {
18 #[debug_format = "mp{}"]
19 pub struct MovePathIndex {}
22 impl polonius_engine
::Atom
for MovePathIndex
{
23 fn index(self) -> usize {
24 rustc_index
::Idx
::index(self)
28 rustc_index
::newtype_index
! {
30 #[debug_format = "mo{}"]
31 pub struct MoveOutIndex {}
34 rustc_index
::newtype_index
! {
35 #[debug_format = "in{}"]
36 pub struct InitIndex {}
40 pub fn move_path_index(self, move_data
: &MoveData
<'_
>) -> MovePathIndex
{
41 move_data
.moves
[self].path
45 /// `MovePath` is a canonicalized representation of a path that is
46 /// moved or assigned to.
48 /// It follows a tree structure.
50 /// Given `struct X { m: M, n: N }` and `x: X`, moves like `drop x.m;`
51 /// move *out* of the place `x.m`.
53 /// The MovePaths representing `x.m` and `x.n` are siblings (that is,
54 /// one of them will link to the other via the `next_sibling` field,
55 /// and the other will have no entry in its `next_sibling` field), and
56 /// they both have the MovePath representing `x` as their parent.
58 pub struct MovePath
<'tcx
> {
59 pub next_sibling
: Option
<MovePathIndex
>,
60 pub first_child
: Option
<MovePathIndex
>,
61 pub parent
: Option
<MovePathIndex
>,
62 pub place
: Place
<'tcx
>,
65 impl<'tcx
> MovePath
<'tcx
> {
66 /// Returns an iterator over the parents of `self`.
69 move_paths
: &'a IndexSlice
<MovePathIndex
, MovePath
<'tcx
>>,
70 ) -> impl 'a
+ Iterator
<Item
= (MovePathIndex
, &'a MovePath
<'tcx
>)> {
71 let first
= self.parent
.map(|mpi
| (mpi
, &move_paths
[mpi
]));
74 fetch_next
: move |_
, parent
: &MovePath
<'_
>| {
75 parent
.parent
.map(|mpi
| (mpi
, &move_paths
[mpi
]))
80 /// Returns an iterator over the immediate children of `self`.
83 move_paths
: &'a IndexSlice
<MovePathIndex
, MovePath
<'tcx
>>,
84 ) -> impl 'a
+ Iterator
<Item
= (MovePathIndex
, &'a MovePath
<'tcx
>)> {
85 let first
= self.first_child
.map(|mpi
| (mpi
, &move_paths
[mpi
]));
88 fetch_next
: move |_
, child
: &MovePath
<'_
>| {
89 child
.next_sibling
.map(|mpi
| (mpi
, &move_paths
[mpi
]))
94 /// Finds the closest descendant of `self` for which `f` returns `true` using a breadth-first
97 /// `f` will **not** be called on `self`.
98 pub fn find_descendant(
100 move_paths
: &IndexSlice
<MovePathIndex
, MovePath
<'_
>>,
101 f
: impl Fn(MovePathIndex
) -> bool
,
102 ) -> Option
<MovePathIndex
> {
103 let mut todo
= if let Some(child
) = self.first_child
{
109 while let Some(mpi
) = todo
.pop() {
114 let move_path
= &move_paths
[mpi
];
115 if let Some(child
) = move_path
.first_child
{
119 // After we've processed the original `mpi`, we should always
120 // traverse the siblings of any of its children.
121 if let Some(sibling
) = move_path
.next_sibling
{
130 impl<'tcx
> fmt
::Debug
for MovePath
<'tcx
> {
131 fn fmt(&self, w
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
132 write
!(w
, "MovePath {{")?
;
133 if let Some(parent
) = self.parent
{
134 write
!(w
, " parent: {parent:?},")?
;
136 if let Some(first_child
) = self.first_child
{
137 write
!(w
, " first_child: {first_child:?},")?
;
139 if let Some(next_sibling
) = self.next_sibling
{
140 write
!(w
, " next_sibling: {next_sibling:?}")?
;
142 write
!(w
, " place: {:?} }}", self.place
)
146 impl<'tcx
> fmt
::Display
for MovePath
<'tcx
> {
147 fn fmt(&self, w
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
148 write
!(w
, "{:?}", self.place
)
152 struct MovePathLinearIter
<'a
, 'tcx
, F
> {
153 next
: Option
<(MovePathIndex
, &'a MovePath
<'tcx
>)>,
157 impl<'a
, 'tcx
, F
> Iterator
for MovePathLinearIter
<'a
, 'tcx
, F
>
159 F
: FnMut(MovePathIndex
, &'a MovePath
<'tcx
>) -> Option
<(MovePathIndex
, &'a MovePath
<'tcx
>)>,
161 type Item
= (MovePathIndex
, &'a MovePath
<'tcx
>);
163 fn next(&mut self) -> Option
<Self::Item
> {
164 let ret
= self.next
.take()?
;
165 self.next
= (self.fetch_next
)(ret
.0, ret
.1);
171 pub struct MoveData
<'tcx
> {
172 pub move_paths
: IndexVec
<MovePathIndex
, MovePath
<'tcx
>>,
173 pub moves
: IndexVec
<MoveOutIndex
, MoveOut
>,
174 /// Each Location `l` is mapped to the MoveOut's that are effects
175 /// of executing the code at `l`. (There can be multiple MoveOut's
176 /// for a given `l` because each MoveOut is associated with one
177 /// particular path being moved.)
178 pub loc_map
: LocationMap
<SmallVec
<[MoveOutIndex
; 4]>>,
179 pub path_map
: IndexVec
<MovePathIndex
, SmallVec
<[MoveOutIndex
; 4]>>,
180 pub rev_lookup
: MovePathLookup
<'tcx
>,
181 pub inits
: IndexVec
<InitIndex
, Init
>,
182 /// Each Location `l` is mapped to the Inits that are effects
183 /// of executing the code at `l`.
184 pub init_loc_map
: LocationMap
<SmallVec
<[InitIndex
; 4]>>,
185 pub init_path_map
: IndexVec
<MovePathIndex
, SmallVec
<[InitIndex
; 4]>>,
188 pub trait HasMoveData
<'tcx
> {
189 fn move_data(&self) -> &MoveData
<'tcx
>;
193 pub struct LocationMap
<T
> {
194 /// Location-indexed (BasicBlock for outer index, index within BB
195 /// for inner index) map.
196 pub(crate) map
: IndexVec
<BasicBlock
, Vec
<T
>>,
199 impl<T
> Index
<Location
> for LocationMap
<T
> {
201 fn index(&self, index
: Location
) -> &Self::Output
{
202 &self.map
[index
.block
][index
.statement_index
]
206 impl<T
> IndexMut
<Location
> for LocationMap
<T
> {
207 fn index_mut(&mut self, index
: Location
) -> &mut Self::Output
{
208 &mut self.map
[index
.block
][index
.statement_index
]
212 impl<T
> LocationMap
<T
>
216 fn new(body
: &Body
<'_
>) -> Self {
221 .map(|block
| vec
![T
::default(); block
.statements
.len() + 1])
227 /// `MoveOut` represents a point in a program that moves out of some
228 /// L-value; i.e., "creates" uninitialized memory.
230 /// With respect to dataflow analysis:
231 /// - Generated by moves and declaration of uninitialized variables.
232 /// - Killed by assignments to the memory.
233 #[derive(Copy, Clone)]
236 pub path
: MovePathIndex
,
238 pub source
: Location
,
241 impl fmt
::Debug
for MoveOut
{
242 fn fmt(&self, fmt
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
243 write
!(fmt
, "{:?}@{:?}", self.path
, self.source
)
247 /// `Init` represents a point in a program that initializes some L-value;
248 #[derive(Copy, Clone)]
250 /// path being initialized
251 pub path
: MovePathIndex
,
252 /// location of initialization
253 pub location
: InitLocation
,
254 /// Extra information about this initialization
258 /// Initializations can be from an argument or from a statement. Arguments
259 /// do not have locations, in those cases the `Local` is kept..
260 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
261 pub enum InitLocation
{
266 /// Additional information about the initialization.
267 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
269 /// Deep init, even on panic
271 /// Only does a shallow init
273 /// This doesn't initialize the variable on panic (and a panic is possible).
277 impl fmt
::Debug
for Init
{
278 fn fmt(&self, fmt
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
279 write
!(fmt
, "{:?}@{:?} ({:?})", self.path
, self.location
, self.kind
)
284 pub fn span
<'tcx
>(&self, body
: &Body
<'tcx
>) -> Span
{
285 match self.location
{
286 InitLocation
::Argument(local
) => body
.local_decls
[local
].source_info
.span
,
287 InitLocation
::Statement(location
) => body
.source_info(location
).span
,
292 /// Tables mapping from a place to its MovePathIndex.
294 pub struct MovePathLookup
<'tcx
> {
295 locals
: IndexVec
<Local
, Option
<MovePathIndex
>>,
297 /// projections are made from a base-place and a projection
298 /// elem. The base-place will have a unique MovePathIndex; we use
299 /// the latter as the index into the outer vector (narrowing
300 /// subsequent search so that it is solely relative to that
301 /// base-place). For the remaining lookup, we map the projection
302 /// elem to the associated MovePathIndex.
303 projections
: FxHashMap
<(MovePathIndex
, AbstractElem
), MovePathIndex
>,
305 un_derefer
: UnDerefer
<'tcx
>,
310 #[derive(Copy, Clone, Debug)]
311 pub enum LookupResult
{
312 Exact(MovePathIndex
),
313 Parent(Option
<MovePathIndex
>),
316 impl<'tcx
> MovePathLookup
<'tcx
> {
317 // Unlike the builder `fn move_path_for` below, this lookup
318 // alternative will *not* create a MovePath on the fly for an
319 // unknown place, but will rather return the nearest available
321 pub fn find(&self, place
: PlaceRef
<'tcx
>) -> LookupResult
{
322 let Some(mut result
) = self.find_local(place
.local
) else {
323 return LookupResult
::Parent(None
);
326 for (_
, elem
) in self.un_derefer
.iter_projections(place
) {
327 if let Some(&subpath
) = self.projections
.get(&(result
, elem
.lift())) {
330 return LookupResult
::Parent(Some(result
));
334 LookupResult
::Exact(result
)
338 pub fn find_local(&self, local
: Local
) -> Option
<MovePathIndex
> {
342 /// An enumerated iterator of `local`s and their associated
343 /// `MovePathIndex`es.
344 pub fn iter_locals_enumerated(
346 ) -> impl DoubleEndedIterator
<Item
= (Local
, MovePathIndex
)> + '_
{
347 self.locals
.iter_enumerated().filter_map(|(l
, &idx
)| Some((l
, idx?
)))
351 impl<'tcx
> MoveData
<'tcx
> {
355 param_env
: ParamEnv
<'tcx
>,
356 filter
: impl Fn(Ty
<'tcx
>) -> bool
,
357 ) -> MoveData
<'tcx
> {
358 builder
::gather_moves(body
, tcx
, param_env
, filter
)
361 /// For the move path `mpi`, returns the root local variable (if any) that starts the path.
362 /// (e.g., for a path like `a.b.c` returns `Some(a)`)
363 pub fn base_local(&self, mut mpi
: MovePathIndex
) -> Option
<Local
> {
365 let path
= &self.move_paths
[mpi
];
366 if let Some(l
) = path
.place
.as_local() {
369 if let Some(parent
) = path
.parent
{
378 pub fn find_in_move_path_or_its_descendants(
381 pred
: impl Fn(MovePathIndex
) -> bool
,
382 ) -> Option
<MovePathIndex
> {
387 self.move_paths
[root
].find_descendant(&self.move_paths
, pred
)