3 use rustc
::ty
::{Ty, TyCtxt, ParamEnv}
;
4 use rustc
::util
::nodemap
::FxHashMap
;
5 use rustc_index
::vec
::{Enumerated, Idx, IndexVec}
;
6 use smallvec
::SmallVec
;
10 use std
::ops
::{Index, IndexMut}
;
12 use self::abs_domain
::{AbstractElem, Lift}
;
16 rustc_index
::newtype_index
! {
17 pub struct MovePathIndex
{
22 rustc_index
::newtype_index
! {
23 pub struct MoveOutIndex
{
28 rustc_index
::newtype_index
! {
29 pub struct InitIndex
{
35 pub fn move_path_index(&self, move_data
: &MoveData
<'_
>) -> MovePathIndex
{
36 move_data
.moves
[*self].path
40 /// `MovePath` is a canonicalized representation of a path that is
41 /// moved or assigned to.
43 /// It follows a tree structure.
45 /// Given `struct X { m: M, n: N }` and `x: X`, moves like `drop x.m;`
46 /// move *out* of the place `x.m`.
48 /// The MovePaths representing `x.m` and `x.n` are siblings (that is,
49 /// one of them will link to the other via the `next_sibling` field,
50 /// and the other will have no entry in its `next_sibling` field), and
51 /// they both have the MovePath representing `x` as their parent.
53 pub struct MovePath
<'tcx
> {
54 pub next_sibling
: Option
<MovePathIndex
>,
55 pub first_child
: Option
<MovePathIndex
>,
56 pub parent
: Option
<MovePathIndex
>,
57 pub place
: Place
<'tcx
>,
60 impl<'tcx
> MovePath
<'tcx
> {
63 move_paths
: &IndexVec
<MovePathIndex
, MovePath
<'_
>>,
64 ) -> Vec
<MovePathIndex
> {
65 let mut parents
= Vec
::new();
67 let mut curr_parent
= self.parent
;
68 while let Some(parent_mpi
) = curr_parent
{
69 parents
.push(parent_mpi
);
70 curr_parent
= move_paths
[parent_mpi
].parent
;
77 impl<'tcx
> fmt
::Debug
for MovePath
<'tcx
> {
78 fn fmt(&self, w
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
79 write
!(w
, "MovePath {{")?
;
80 if let Some(parent
) = self.parent
{
81 write
!(w
, " parent: {:?},", parent
)?
;
83 if let Some(first_child
) = self.first_child
{
84 write
!(w
, " first_child: {:?},", first_child
)?
;
86 if let Some(next_sibling
) = self.next_sibling
{
87 write
!(w
, " next_sibling: {:?}", next_sibling
)?
;
89 write
!(w
, " place: {:?} }}", self.place
)
93 impl<'tcx
> fmt
::Display
for MovePath
<'tcx
> {
94 fn fmt(&self, w
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
95 write
!(w
, "{:?}", self.place
)
100 pub struct MoveData
<'tcx
> {
101 pub move_paths
: IndexVec
<MovePathIndex
, MovePath
<'tcx
>>,
102 pub moves
: IndexVec
<MoveOutIndex
, MoveOut
>,
103 /// Each Location `l` is mapped to the MoveOut's that are effects
104 /// of executing the code at `l`. (There can be multiple MoveOut's
105 /// for a given `l` because each MoveOut is associated with one
106 /// particular path being moved.)
107 pub loc_map
: LocationMap
<SmallVec
<[MoveOutIndex
; 4]>>,
108 pub path_map
: IndexVec
<MovePathIndex
, SmallVec
<[MoveOutIndex
; 4]>>,
109 pub rev_lookup
: MovePathLookup
,
110 pub inits
: IndexVec
<InitIndex
, Init
>,
111 /// Each Location `l` is mapped to the Inits that are effects
112 /// of executing the code at `l`.
113 pub init_loc_map
: LocationMap
<SmallVec
<[InitIndex
; 4]>>,
114 pub init_path_map
: IndexVec
<MovePathIndex
, SmallVec
<[InitIndex
; 4]>>,
117 pub trait HasMoveData
<'tcx
> {
118 fn move_data(&self) -> &MoveData
<'tcx
>;
122 pub struct LocationMap
<T
> {
123 /// Location-indexed (BasicBlock for outer index, index within BB
124 /// for inner index) map.
125 pub(crate) map
: IndexVec
<BasicBlock
, Vec
<T
>>,
128 impl<T
> Index
<Location
> for LocationMap
<T
> {
130 fn index(&self, index
: Location
) -> &Self::Output
{
131 &self.map
[index
.block
][index
.statement_index
]
135 impl<T
> IndexMut
<Location
> for LocationMap
<T
> {
136 fn index_mut(&mut self, index
: Location
) -> &mut Self::Output
{
137 &mut self.map
[index
.block
][index
.statement_index
]
141 impl<T
> LocationMap
<T
>
145 fn new(body
: &Body
<'_
>) -> Self {
150 .map(|block
| vec
![T
::default(); block
.statements
.len() + 1])
156 /// `MoveOut` represents a point in a program that moves out of some
157 /// L-value; i.e., "creates" uninitialized memory.
159 /// With respect to dataflow analysis:
160 /// - Generated by moves and declaration of uninitialized variables.
161 /// - Killed by assignments to the memory.
162 #[derive(Copy, Clone)]
165 pub path
: MovePathIndex
,
167 pub source
: Location
,
170 impl fmt
::Debug
for MoveOut
{
171 fn fmt(&self, fmt
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
172 write
!(fmt
, "{:?}@{:?}", self.path
, self.source
)
176 /// `Init` represents a point in a program that initializes some L-value;
177 #[derive(Copy, Clone)]
179 /// path being initialized
180 pub path
: MovePathIndex
,
181 /// location of initialization
182 pub location
: InitLocation
,
183 /// Extra information about this initialization
187 /// Initializations can be from an argument or from a statement. Arguments
188 /// do not have locations, in those cases the `Local` is kept..
189 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
190 pub enum InitLocation
{
195 /// Additional information about the initialization.
196 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
198 /// Deep init, even on panic
200 /// Only does a shallow init
202 /// This doesn't initialize the variable on panic (and a panic is possible).
206 impl fmt
::Debug
for Init
{
207 fn fmt(&self, fmt
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
208 write
!(fmt
, "{:?}@{:?} ({:?})", self.path
, self.location
, self.kind
)
213 crate fn span
<'tcx
>(&self, body
: &Body
<'tcx
>) -> Span
{
214 match self.location
{
215 InitLocation
::Argument(local
) => body
.local_decls
[local
].source_info
.span
,
216 InitLocation
::Statement(location
) => body
.source_info(location
).span
,
221 /// Tables mapping from a place to its MovePathIndex.
223 pub struct MovePathLookup
{
224 locals
: IndexVec
<Local
, MovePathIndex
>,
226 /// projections are made from a base-place and a projection
227 /// elem. The base-place will have a unique MovePathIndex; we use
228 /// the latter as the index into the outer vector (narrowing
229 /// subsequent search so that it is solely relative to that
230 /// base-place). For the remaining lookup, we map the projection
231 /// elem to the associated MovePathIndex.
232 projections
: FxHashMap
<(MovePathIndex
, AbstractElem
), MovePathIndex
>,
237 #[derive(Copy, Clone, Debug)]
238 pub enum LookupResult
{
239 Exact(MovePathIndex
),
240 Parent(Option
<MovePathIndex
>),
243 impl MovePathLookup
{
244 // Unlike the builder `fn move_path_for` below, this lookup
245 // alternative will *not* create a MovePath on the fly for an
246 // unknown place, but will rather return the nearest available
248 pub fn find(&self, place
: PlaceRef
<'_
, '_
>) -> LookupResult
{
249 let mut result
= match place
.base
{
250 PlaceBase
::Local(local
) => self.locals
[*local
],
251 PlaceBase
::Static(..) => return LookupResult
::Parent(None
),
254 for elem
in place
.projection
.iter() {
255 if let Some(&subpath
) = self.projections
.get(&(result
, elem
.lift())) {
258 return LookupResult
::Parent(Some(result
));
262 LookupResult
::Exact(result
)
265 pub fn find_local(&self, local
: Local
) -> MovePathIndex
{
269 /// An enumerated iterator of `local`s and their associated
270 /// `MovePathIndex`es.
271 pub fn iter_locals_enumerated(&self) -> Enumerated
<Local
, Iter
<'_
, MovePathIndex
>> {
272 self.locals
.iter_enumerated()
277 pub struct IllegalMoveOrigin
<'tcx
> {
278 pub(crate) location
: Location
,
279 pub(crate) kind
: IllegalMoveOriginKind
<'tcx
>,
283 pub(crate) enum IllegalMoveOriginKind
<'tcx
> {
284 /// Illegal move due to attempt to move from `static` variable.
287 /// Illegal move due to attempt to move from behind a reference.
289 /// The place the reference refers to: if erroneous code was trying to
290 /// move from `(*x).f` this will be `*x`.
291 target_place
: Place
<'tcx
>,
294 /// Illegal move due to attempt to move from field of an ADT that
295 /// implements `Drop`. Rust maintains invariant that all `Drop`
296 /// ADT's remain fully-initialized so that user-defined destructor
297 /// can safely read from all of the ADT's fields.
298 InteriorOfTypeWithDestructor { container_ty: Ty<'tcx> }
,
300 /// Illegal move due to attempt to move out of a slice or array.
301 InteriorOfSliceOrArray { ty: Ty<'tcx>, is_index: bool }
,
305 pub enum MoveError
<'tcx
> {
306 IllegalMove { cannot_move_out_of: IllegalMoveOrigin<'tcx> }
,
307 UnionMove { path: MovePathIndex }
,
310 impl<'tcx
> MoveError
<'tcx
> {
311 fn cannot_move_out_of(location
: Location
, kind
: IllegalMoveOriginKind
<'tcx
>) -> Self {
312 let origin
= IllegalMoveOrigin { location, kind }
;
313 MoveError
::IllegalMove { cannot_move_out_of: origin }
317 impl<'tcx
> MoveData
<'tcx
> {
321 param_env
: ParamEnv
<'tcx
>,
322 ) -> Result
<Self, (Self, Vec
<(Place
<'tcx
>, MoveError
<'tcx
>)>)> {
323 builder
::gather_moves(body
, tcx
, param_env
)
326 /// For the move path `mpi`, returns the root local variable (if any) that starts the path.
327 /// (e.g., for a path like `a.b.c` returns `Some(a)`)
328 pub fn base_local(&self, mut mpi
: MovePathIndex
) -> Option
<Local
> {
330 let path
= &self.move_paths
[mpi
];
331 if let Some(l
) = path
.place
.as_local() {
334 if let Some(parent
) = path
.parent
{