1 use crate::move_paths
::builder
::MoveDat
;
2 use rustc_data_structures
::fx
::FxHashMap
;
3 use rustc_index
::vec
::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
! {
17 #[debug_format = "mp{}"]
18 pub struct MovePathIndex {}
21 impl polonius_engine
::Atom
for MovePathIndex
{
22 fn index(self) -> usize {
23 rustc_index
::vec
::Idx
::index(self)
27 rustc_index
::newtype_index
! {
28 #[debug_format = "mo{}"]
29 pub struct MoveOutIndex {}
32 rustc_index
::newtype_index
! {
33 #[debug_format = "in{}"]
34 pub struct InitIndex {}
38 pub fn move_path_index(self, move_data
: &MoveData
<'_
>) -> MovePathIndex
{
39 move_data
.moves
[self].path
43 /// `MovePath` is a canonicalized representation of a path that is
44 /// moved or assigned to.
46 /// It follows a tree structure.
48 /// Given `struct X { m: M, n: N }` and `x: X`, moves like `drop x.m;`
49 /// move *out* of the place `x.m`.
51 /// The MovePaths representing `x.m` and `x.n` are siblings (that is,
52 /// one of them will link to the other via the `next_sibling` field,
53 /// and the other will have no entry in its `next_sibling` field), and
54 /// they both have the MovePath representing `x` as their parent.
56 pub struct MovePath
<'tcx
> {
57 pub next_sibling
: Option
<MovePathIndex
>,
58 pub first_child
: Option
<MovePathIndex
>,
59 pub parent
: Option
<MovePathIndex
>,
60 pub place
: Place
<'tcx
>,
63 impl<'tcx
> MovePath
<'tcx
> {
64 /// Returns an iterator over the parents of `self`.
67 move_paths
: &'a IndexVec
<MovePathIndex
, MovePath
<'tcx
>>,
68 ) -> impl 'a
+ Iterator
<Item
= (MovePathIndex
, &'a MovePath
<'tcx
>)> {
69 let first
= self.parent
.map(|mpi
| (mpi
, &move_paths
[mpi
]));
72 fetch_next
: move |_
, parent
: &MovePath
<'_
>| {
73 parent
.parent
.map(|mpi
| (mpi
, &move_paths
[mpi
]))
78 /// Returns an iterator over the immediate children of `self`.
81 move_paths
: &'a IndexVec
<MovePathIndex
, MovePath
<'tcx
>>,
82 ) -> impl 'a
+ Iterator
<Item
= (MovePathIndex
, &'a MovePath
<'tcx
>)> {
83 let first
= self.first_child
.map(|mpi
| (mpi
, &move_paths
[mpi
]));
86 fetch_next
: move |_
, child
: &MovePath
<'_
>| {
87 child
.next_sibling
.map(|mpi
| (mpi
, &move_paths
[mpi
]))
92 /// Finds the closest descendant of `self` for which `f` returns `true` using a breadth-first
95 /// `f` will **not** be called on `self`.
96 pub fn find_descendant(
98 move_paths
: &IndexVec
<MovePathIndex
, MovePath
<'_
>>,
99 f
: impl Fn(MovePathIndex
) -> bool
,
100 ) -> Option
<MovePathIndex
> {
101 let mut todo
= if let Some(child
) = self.first_child
{
107 while let Some(mpi
) = todo
.pop() {
112 let move_path
= &move_paths
[mpi
];
113 if let Some(child
) = move_path
.first_child
{
117 // After we've processed the original `mpi`, we should always
118 // traverse the siblings of any of its children.
119 if let Some(sibling
) = move_path
.next_sibling
{
128 impl<'tcx
> fmt
::Debug
for MovePath
<'tcx
> {
129 fn fmt(&self, w
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
130 write
!(w
, "MovePath {{")?
;
131 if let Some(parent
) = self.parent
{
132 write
!(w
, " parent: {parent:?},")?
;
134 if let Some(first_child
) = self.first_child
{
135 write
!(w
, " first_child: {first_child:?},")?
;
137 if let Some(next_sibling
) = self.next_sibling
{
138 write
!(w
, " next_sibling: {next_sibling:?}")?
;
140 write
!(w
, " place: {:?} }}", self.place
)
144 impl<'tcx
> fmt
::Display
for MovePath
<'tcx
> {
145 fn fmt(&self, w
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
146 write
!(w
, "{:?}", self.place
)
150 struct MovePathLinearIter
<'a
, 'tcx
, F
> {
151 next
: Option
<(MovePathIndex
, &'a MovePath
<'tcx
>)>,
155 impl<'a
, 'tcx
, F
> Iterator
for MovePathLinearIter
<'a
, 'tcx
, F
>
157 F
: FnMut(MovePathIndex
, &'a MovePath
<'tcx
>) -> Option
<(MovePathIndex
, &'a MovePath
<'tcx
>)>,
159 type Item
= (MovePathIndex
, &'a MovePath
<'tcx
>);
161 fn next(&mut self) -> Option
<Self::Item
> {
162 let ret
= self.next
.take()?
;
163 self.next
= (self.fetch_next
)(ret
.0, ret
.1);
169 pub struct MoveData
<'tcx
> {
170 pub move_paths
: IndexVec
<MovePathIndex
, MovePath
<'tcx
>>,
171 pub moves
: IndexVec
<MoveOutIndex
, MoveOut
>,
172 /// Each Location `l` is mapped to the MoveOut's that are effects
173 /// of executing the code at `l`. (There can be multiple MoveOut's
174 /// for a given `l` because each MoveOut is associated with one
175 /// particular path being moved.)
176 pub loc_map
: LocationMap
<SmallVec
<[MoveOutIndex
; 4]>>,
177 pub path_map
: IndexVec
<MovePathIndex
, SmallVec
<[MoveOutIndex
; 4]>>,
178 pub rev_lookup
: MovePathLookup
,
179 pub inits
: IndexVec
<InitIndex
, Init
>,
180 /// Each Location `l` is mapped to the Inits that are effects
181 /// of executing the code at `l`.
182 pub init_loc_map
: LocationMap
<SmallVec
<[InitIndex
; 4]>>,
183 pub init_path_map
: IndexVec
<MovePathIndex
, SmallVec
<[InitIndex
; 4]>>,
186 pub trait HasMoveData
<'tcx
> {
187 fn move_data(&self) -> &MoveData
<'tcx
>;
191 pub struct LocationMap
<T
> {
192 /// Location-indexed (BasicBlock for outer index, index within BB
193 /// for inner index) map.
194 pub(crate) map
: IndexVec
<BasicBlock
, Vec
<T
>>,
197 impl<T
> Index
<Location
> for LocationMap
<T
> {
199 fn index(&self, index
: Location
) -> &Self::Output
{
200 &self.map
[index
.block
][index
.statement_index
]
204 impl<T
> IndexMut
<Location
> for LocationMap
<T
> {
205 fn index_mut(&mut self, index
: Location
) -> &mut Self::Output
{
206 &mut self.map
[index
.block
][index
.statement_index
]
210 impl<T
> LocationMap
<T
>
214 fn new(body
: &Body
<'_
>) -> Self {
219 .map(|block
| vec
![T
::default(); block
.statements
.len() + 1])
225 /// `MoveOut` represents a point in a program that moves out of some
226 /// L-value; i.e., "creates" uninitialized memory.
228 /// With respect to dataflow analysis:
229 /// - Generated by moves and declaration of uninitialized variables.
230 /// - Killed by assignments to the memory.
231 #[derive(Copy, Clone)]
234 pub path
: MovePathIndex
,
236 pub source
: Location
,
239 impl fmt
::Debug
for MoveOut
{
240 fn fmt(&self, fmt
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
241 write
!(fmt
, "{:?}@{:?}", self.path
, self.source
)
245 /// `Init` represents a point in a program that initializes some L-value;
246 #[derive(Copy, Clone)]
248 /// path being initialized
249 pub path
: MovePathIndex
,
250 /// location of initialization
251 pub location
: InitLocation
,
252 /// Extra information about this initialization
256 /// Initializations can be from an argument or from a statement. Arguments
257 /// do not have locations, in those cases the `Local` is kept..
258 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
259 pub enum InitLocation
{
264 /// Additional information about the initialization.
265 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
267 /// Deep init, even on panic
269 /// Only does a shallow init
271 /// This doesn't initialize the variable on panic (and a panic is possible).
275 impl fmt
::Debug
for Init
{
276 fn fmt(&self, fmt
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
277 write
!(fmt
, "{:?}@{:?} ({:?})", self.path
, self.location
, self.kind
)
282 pub fn span
<'tcx
>(&self, body
: &Body
<'tcx
>) -> Span
{
283 match self.location
{
284 InitLocation
::Argument(local
) => body
.local_decls
[local
].source_info
.span
,
285 InitLocation
::Statement(location
) => body
.source_info(location
).span
,
290 /// Tables mapping from a place to its MovePathIndex.
292 pub struct MovePathLookup
{
293 locals
: IndexVec
<Local
, MovePathIndex
>,
295 /// projections are made from a base-place and a projection
296 /// elem. The base-place will have a unique MovePathIndex; we use
297 /// the latter as the index into the outer vector (narrowing
298 /// subsequent search so that it is solely relative to that
299 /// base-place). For the remaining lookup, we map the projection
300 /// elem to the associated MovePathIndex.
301 projections
: FxHashMap
<(MovePathIndex
, AbstractElem
), MovePathIndex
>,
306 #[derive(Copy, Clone, Debug)]
307 pub enum LookupResult
{
308 Exact(MovePathIndex
),
309 Parent(Option
<MovePathIndex
>),
312 impl MovePathLookup
{
313 // Unlike the builder `fn move_path_for` below, this lookup
314 // alternative will *not* create a MovePath on the fly for an
315 // unknown place, but will rather return the nearest available
317 pub fn find(&self, place
: PlaceRef
<'_
>) -> LookupResult
{
318 let mut result
= self.locals
[place
.local
];
320 for elem
in place
.projection
.iter() {
321 if let Some(&subpath
) = self.projections
.get(&(result
, elem
.lift())) {
324 return LookupResult
::Parent(Some(result
));
328 LookupResult
::Exact(result
)
331 pub fn find_local(&self, local
: Local
) -> MovePathIndex
{
335 /// An enumerated iterator of `local`s and their associated
336 /// `MovePathIndex`es.
337 pub fn iter_locals_enumerated(
339 ) -> impl DoubleEndedIterator
<Item
= (Local
, MovePathIndex
)> + ExactSizeIterator
+ '_
{
340 self.locals
.iter_enumerated().map(|(l
, &idx
)| (l
, idx
))
345 pub struct IllegalMoveOrigin
<'tcx
> {
346 pub location
: Location
,
347 pub kind
: IllegalMoveOriginKind
<'tcx
>,
351 pub enum IllegalMoveOriginKind
<'tcx
> {
352 /// Illegal move due to attempt to move from behind a reference.
354 /// The place the reference refers to: if erroneous code was trying to
355 /// move from `(*x).f` this will be `*x`.
356 target_place
: Place
<'tcx
>,
359 /// Illegal move due to attempt to move from field of an ADT that
360 /// implements `Drop`. Rust maintains invariant that all `Drop`
361 /// ADT's remain fully-initialized so that user-defined destructor
362 /// can safely read from all of the ADT's fields.
363 InteriorOfTypeWithDestructor { container_ty: Ty<'tcx> }
,
365 /// Illegal move due to attempt to move out of a slice or array.
366 InteriorOfSliceOrArray { ty: Ty<'tcx>, is_index: bool }
,
370 pub enum MoveError
<'tcx
> {
371 IllegalMove { cannot_move_out_of: IllegalMoveOrigin<'tcx> }
,
372 UnionMove { path: MovePathIndex }
,
375 impl<'tcx
> MoveError
<'tcx
> {
376 fn cannot_move_out_of(location
: Location
, kind
: IllegalMoveOriginKind
<'tcx
>) -> Self {
377 let origin
= IllegalMoveOrigin { location, kind }
;
378 MoveError
::IllegalMove { cannot_move_out_of: origin }
382 impl<'tcx
> MoveData
<'tcx
> {
386 param_env
: ParamEnv
<'tcx
>,
388 builder
::gather_moves(body
, tcx
, param_env
)
391 /// For the move path `mpi`, returns the root local variable (if any) that starts the path.
392 /// (e.g., for a path like `a.b.c` returns `Some(a)`)
393 pub fn base_local(&self, mut mpi
: MovePathIndex
) -> Option
<Local
> {
395 let path
= &self.move_paths
[mpi
];
396 if let Some(l
) = path
.place
.as_local() {
399 if let Some(parent
) = path
.parent
{
408 pub fn find_in_move_path_or_its_descendants(
411 pred
: impl Fn(MovePathIndex
) -> bool
,
412 ) -> Option
<MovePathIndex
> {
417 self.move_paths
[root
].find_descendant(&self.move_paths
, pred
)