diff options
Diffstat (limited to 'compiler/rustc_mir/src/dataflow/move_paths')
| -rw-r--r-- | compiler/rustc_mir/src/dataflow/move_paths/abs_domain.rs | 61 | ||||
| -rw-r--r-- | compiler/rustc_mir/src/dataflow/move_paths/builder.rs | 552 | ||||
| -rw-r--r-- | compiler/rustc_mir/src/dataflow/move_paths/mod.rs | 415 |
3 files changed, 1028 insertions, 0 deletions
diff --git a/compiler/rustc_mir/src/dataflow/move_paths/abs_domain.rs b/compiler/rustc_mir/src/dataflow/move_paths/abs_domain.rs new file mode 100644 index 00000000000..28936274baa --- /dev/null +++ b/compiler/rustc_mir/src/dataflow/move_paths/abs_domain.rs @@ -0,0 +1,61 @@ +//! The move-analysis portion of borrowck needs to work in an abstract +//! domain of lifted `Place`s. Most of the `Place` variants fall into a +//! one-to-one mapping between the concrete and abstract (e.g., a +//! field-deref on a local variable, `x.field`, has the same meaning +//! in both domains). Indexed projections are the exception: `a[x]` +//! needs to be treated as mapping to the same move path as `a[y]` as +//! well as `a[13]`, etc. +//! +//! (In theory, the analysis could be extended to work with sets of +//! paths, so that `a[0]` and `a[13]` could be kept distinct, while +//! `a[x]` would still overlap them both. But that is not this +//! representation does today.) + +use rustc_middle::mir::{Local, Operand, PlaceElem, ProjectionElem}; +use rustc_middle::ty::Ty; + +#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] +pub struct AbstractOperand; +#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] +pub struct AbstractType; +pub type AbstractElem = ProjectionElem<AbstractOperand, AbstractType>; + +pub trait Lift { + type Abstract; + fn lift(&self) -> Self::Abstract; +} +impl<'tcx> Lift for Operand<'tcx> { + type Abstract = AbstractOperand; + fn lift(&self) -> Self::Abstract { + AbstractOperand + } +} +impl Lift for Local { + type Abstract = AbstractOperand; + fn lift(&self) -> Self::Abstract { + AbstractOperand + } +} +impl<'tcx> Lift for Ty<'tcx> { + type Abstract = AbstractType; + fn lift(&self) -> Self::Abstract { + AbstractType + } +} +impl<'tcx> Lift for PlaceElem<'tcx> { + type Abstract = AbstractElem; + fn lift(&self) -> Self::Abstract { + match *self { + ProjectionElem::Deref => ProjectionElem::Deref, + ProjectionElem::Field(f, ty) => ProjectionElem::Field(f, ty.lift()), + ProjectionElem::Index(ref i) => ProjectionElem::Index(i.lift()), + ProjectionElem::Subslice { from, to, from_end } => { + ProjectionElem::Subslice { from, to, from_end } + } + ProjectionElem::ConstantIndex { offset, min_length, from_end } => { + ProjectionElem::ConstantIndex { offset, min_length, from_end } + } + ProjectionElem::Downcast(a, u) => ProjectionElem::Downcast(a, u), + } + } +} diff --git a/compiler/rustc_mir/src/dataflow/move_paths/builder.rs b/compiler/rustc_mir/src/dataflow/move_paths/builder.rs new file mode 100644 index 00000000000..e088dc6a954 --- /dev/null +++ b/compiler/rustc_mir/src/dataflow/move_paths/builder.rs @@ -0,0 +1,552 @@ +use rustc_index::vec::IndexVec; +use rustc_middle::mir::tcx::RvalueInitializationState; +use rustc_middle::mir::*; +use rustc_middle::ty::{self, TyCtxt}; +use smallvec::{smallvec, SmallVec}; + +use std::convert::TryInto; +use std::mem; + +use super::abs_domain::Lift; +use super::IllegalMoveOriginKind::*; +use super::{Init, InitIndex, InitKind, InitLocation, LookupResult, MoveError}; +use super::{ + LocationMap, MoveData, MoveOut, MoveOutIndex, MovePath, MovePathIndex, MovePathLookup, +}; + +struct MoveDataBuilder<'a, 'tcx> { + body: &'a Body<'tcx>, + tcx: TyCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + data: MoveData<'tcx>, + errors: Vec<(Place<'tcx>, MoveError<'tcx>)>, +} + +impl<'a, 'tcx> MoveDataBuilder<'a, 'tcx> { + fn new(body: &'a Body<'tcx>, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> Self { + let mut move_paths = IndexVec::new(); + let mut path_map = IndexVec::new(); + let mut init_path_map = IndexVec::new(); + + MoveDataBuilder { + body, + tcx, + param_env, + errors: Vec::new(), + data: MoveData { + moves: IndexVec::new(), + loc_map: LocationMap::new(body), + rev_lookup: MovePathLookup { + locals: body + .local_decls + .indices() + .map(|i| { + Self::new_move_path( + &mut move_paths, + &mut path_map, + &mut init_path_map, + None, + Place::from(i), + ) + }) + .collect(), + projections: Default::default(), + }, + move_paths, + path_map, + inits: IndexVec::new(), + init_loc_map: LocationMap::new(body), + init_path_map, + }, + } + } + + fn new_move_path( + move_paths: &mut IndexVec<MovePathIndex, MovePath<'tcx>>, + path_map: &mut IndexVec<MovePathIndex, SmallVec<[MoveOutIndex; 4]>>, + init_path_map: &mut IndexVec<MovePathIndex, SmallVec<[InitIndex; 4]>>, + parent: Option<MovePathIndex>, + place: Place<'tcx>, + ) -> MovePathIndex { + let move_path = + move_paths.push(MovePath { next_sibling: None, first_child: None, parent, place }); + + if let Some(parent) = parent { + let next_sibling = mem::replace(&mut move_paths[parent].first_child, Some(move_path)); + move_paths[move_path].next_sibling = next_sibling; + } + + let path_map_ent = path_map.push(smallvec![]); + assert_eq!(path_map_ent, move_path); + + let init_path_map_ent = init_path_map.push(smallvec![]); + assert_eq!(init_path_map_ent, move_path); + + move_path + } +} + +impl<'b, 'a, 'tcx> Gatherer<'b, 'a, 'tcx> { + /// This creates a MovePath for a given place, returning an `MovePathError` + /// if that place can't be moved from. + /// + /// NOTE: places behind references *do not* get a move path, which is + /// problematic for borrowck. + /// + /// Maybe we should have separate "borrowck" and "moveck" modes. + fn move_path_for(&mut self, place: Place<'tcx>) -> Result<MovePathIndex, MoveError<'tcx>> { + debug!("lookup({:?})", place); + let mut base = self.builder.data.rev_lookup.locals[place.local]; + + // The move path index of the first union that we find. Once this is + // some we stop creating child move paths, since moves from unions + // move the whole thing. + // We continue looking for other move errors though so that moving + // from `*(u.f: &_)` isn't allowed. + let mut union_path = None; + + for (i, elem) in place.projection.iter().enumerate() { + let proj_base = &place.projection[..i]; + let body = self.builder.body; + let tcx = self.builder.tcx; + let place_ty = Place::ty_from(place.local, proj_base, body, tcx).ty; + match place_ty.kind { + ty::Ref(..) | ty::RawPtr(..) => { + let proj = &place.projection[..i + 1]; + return Err(MoveError::cannot_move_out_of( + self.loc, + BorrowedContent { + target_place: Place { + local: place.local, + projection: tcx.intern_place_elems(proj), + }, + }, + )); + } + ty::Adt(adt, _) if adt.has_dtor(tcx) && !adt.is_box() => { + return Err(MoveError::cannot_move_out_of( + self.loc, + InteriorOfTypeWithDestructor { container_ty: place_ty }, + )); + } + ty::Adt(adt, _) if adt.is_union() => { + union_path.get_or_insert(base); + } + ty::Slice(_) => { + return Err(MoveError::cannot_move_out_of( + self.loc, + InteriorOfSliceOrArray { + ty: place_ty, + is_index: match elem { + ProjectionElem::Index(..) => true, + _ => false, + }, + }, + )); + } + + ty::Array(..) => { + if let ProjectionElem::Index(..) = elem { + return Err(MoveError::cannot_move_out_of( + self.loc, + InteriorOfSliceOrArray { ty: place_ty, is_index: true }, + )); + } + } + + _ => {} + }; + + if union_path.is_none() { + base = self.add_move_path(base, elem, |tcx| Place { + local: place.local, + projection: tcx.intern_place_elems(&place.projection[..i + 1]), + }); + } + } + + if let Some(base) = union_path { + // Move out of union - always move the entire union. + Err(MoveError::UnionMove { path: base }) + } else { + Ok(base) + } + } + + fn add_move_path( + &mut self, + base: MovePathIndex, + elem: PlaceElem<'tcx>, + mk_place: impl FnOnce(TyCtxt<'tcx>) -> Place<'tcx>, + ) -> MovePathIndex { + let MoveDataBuilder { + data: MoveData { rev_lookup, move_paths, path_map, init_path_map, .. }, + tcx, + .. + } = self.builder; + *rev_lookup.projections.entry((base, elem.lift())).or_insert_with(move || { + MoveDataBuilder::new_move_path( + move_paths, + path_map, + init_path_map, + Some(base), + mk_place(*tcx), + ) + }) + } + + fn create_move_path(&mut self, place: Place<'tcx>) { + // This is an non-moving access (such as an overwrite or + // drop), so this not being a valid move path is OK. + let _ = self.move_path_for(place); + } +} + +impl<'a, 'tcx> MoveDataBuilder<'a, 'tcx> { + fn finalize( + self, + ) -> Result<MoveData<'tcx>, (MoveData<'tcx>, Vec<(Place<'tcx>, MoveError<'tcx>)>)> { + debug!("{}", { + debug!("moves for {:?}:", self.body.span); + for (j, mo) in self.data.moves.iter_enumerated() { + debug!(" {:?} = {:?}", j, mo); + } + debug!("move paths for {:?}:", self.body.span); + for (j, path) in self.data.move_paths.iter_enumerated() { + debug!(" {:?} = {:?}", j, path); + } + "done dumping moves" + }); + + if !self.errors.is_empty() { Err((self.data, self.errors)) } else { Ok(self.data) } + } +} + +pub(super) fn gather_moves<'tcx>( + body: &Body<'tcx>, + tcx: TyCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, +) -> Result<MoveData<'tcx>, (MoveData<'tcx>, Vec<(Place<'tcx>, MoveError<'tcx>)>)> { + let mut builder = MoveDataBuilder::new(body, tcx, param_env); + + builder.gather_args(); + + for (bb, block) in body.basic_blocks().iter_enumerated() { + for (i, stmt) in block.statements.iter().enumerate() { + let source = Location { block: bb, statement_index: i }; + builder.gather_statement(source, stmt); + } + + let terminator_loc = Location { block: bb, statement_index: block.statements.len() }; + builder.gather_terminator(terminator_loc, block.terminator()); + } + + builder.finalize() +} + +impl<'a, 'tcx> MoveDataBuilder<'a, 'tcx> { + fn gather_args(&mut self) { + for arg in self.body.args_iter() { + let path = self.data.rev_lookup.locals[arg]; + + let init = self.data.inits.push(Init { + path, + kind: InitKind::Deep, + location: InitLocation::Argument(arg), + }); + + debug!("gather_args: adding init {:?} of {:?} for argument {:?}", init, path, arg); + + self.data.init_path_map[path].push(init); + } + } + + fn gather_statement(&mut self, loc: Location, stmt: &Statement<'tcx>) { + debug!("gather_statement({:?}, {:?})", loc, stmt); + (Gatherer { builder: self, loc }).gather_statement(stmt); + } + + fn gather_terminator(&mut self, loc: Location, term: &Terminator<'tcx>) { + debug!("gather_terminator({:?}, {:?})", loc, term); + (Gatherer { builder: self, loc }).gather_terminator(term); + } +} + +struct Gatherer<'b, 'a, 'tcx> { + builder: &'b mut MoveDataBuilder<'a, 'tcx>, + loc: Location, +} + +impl<'b, 'a, 'tcx> Gatherer<'b, 'a, 'tcx> { + fn gather_statement(&mut self, stmt: &Statement<'tcx>) { + match &stmt.kind { + StatementKind::Assign(box (place, rval)) => { + self.create_move_path(*place); + if let RvalueInitializationState::Shallow = rval.initialization_state() { + // Box starts out uninitialized - need to create a separate + // move-path for the interior so it will be separate from + // the exterior. + self.create_move_path(self.builder.tcx.mk_place_deref(*place)); + self.gather_init(place.as_ref(), InitKind::Shallow); + } else { + self.gather_init(place.as_ref(), InitKind::Deep); + } + self.gather_rvalue(rval); + } + StatementKind::FakeRead(_, place) => { + self.create_move_path(**place); + } + StatementKind::LlvmInlineAsm(ref asm) => { + for (output, kind) in asm.outputs.iter().zip(&asm.asm.outputs) { + if !kind.is_indirect { + self.gather_init(output.as_ref(), InitKind::Deep); + } + } + for (_, input) in asm.inputs.iter() { + self.gather_operand(input); + } + } + StatementKind::StorageLive(_) => {} + StatementKind::StorageDead(local) => { + self.gather_move(Place::from(*local)); + } + StatementKind::SetDiscriminant { .. } => { + span_bug!( + stmt.source_info.span, + "SetDiscriminant should not exist during borrowck" + ); + } + StatementKind::Retag { .. } + | StatementKind::AscribeUserType(..) + | StatementKind::Coverage(..) + | StatementKind::Nop => {} + } + } + + fn gather_rvalue(&mut self, rvalue: &Rvalue<'tcx>) { + match *rvalue { + Rvalue::ThreadLocalRef(_) => {} // not-a-move + Rvalue::Use(ref operand) + | Rvalue::Repeat(ref operand, _) + | Rvalue::Cast(_, ref operand, _) + | Rvalue::UnaryOp(_, ref operand) => self.gather_operand(operand), + Rvalue::BinaryOp(ref _binop, ref lhs, ref rhs) + | Rvalue::CheckedBinaryOp(ref _binop, ref lhs, ref rhs) => { + self.gather_operand(lhs); + self.gather_operand(rhs); + } + Rvalue::Aggregate(ref _kind, ref operands) => { + for operand in operands { + self.gather_operand(operand); + } + } + Rvalue::Ref(..) + | Rvalue::AddressOf(..) + | Rvalue::Discriminant(..) + | Rvalue::Len(..) + | Rvalue::NullaryOp(NullOp::SizeOf, _) + | Rvalue::NullaryOp(NullOp::Box, _) => { + // This returns an rvalue with uninitialized contents. We can't + // move out of it here because it is an rvalue - assignments always + // completely initialize their place. + // + // However, this does not matter - MIR building is careful to + // only emit a shallow free for the partially-initialized + // temporary. + // + // In any case, if we want to fix this, we have to register a + // special move and change the `statement_effect` functions. + } + } + } + + fn gather_terminator(&mut self, term: &Terminator<'tcx>) { + match term.kind { + TerminatorKind::Goto { target: _ } + | TerminatorKind::Resume + | TerminatorKind::Abort + | TerminatorKind::GeneratorDrop + | TerminatorKind::FalseEdge { .. } + | TerminatorKind::FalseUnwind { .. } + | TerminatorKind::Unreachable => {} + + TerminatorKind::Return => { + self.gather_move(Place::return_place()); + } + + TerminatorKind::Assert { ref cond, .. } => { + self.gather_operand(cond); + } + + TerminatorKind::SwitchInt { ref discr, .. } => { + self.gather_operand(discr); + } + + TerminatorKind::Yield { ref value, resume_arg: place, .. } => { + self.gather_operand(value); + self.create_move_path(place); + self.gather_init(place.as_ref(), InitKind::Deep); + } + + TerminatorKind::Drop { place, target: _, unwind: _ } => { + self.gather_move(place); + } + TerminatorKind::DropAndReplace { place, ref value, .. } => { + self.create_move_path(place); + self.gather_operand(value); + self.gather_init(place.as_ref(), InitKind::Deep); + } + TerminatorKind::Call { + ref func, + ref args, + ref destination, + cleanup: _, + from_hir_call: _, + fn_span: _, + } => { + self.gather_operand(func); + for arg in args { + self.gather_operand(arg); + } + if let Some((destination, _bb)) = *destination { + self.create_move_path(destination); + self.gather_init(destination.as_ref(), InitKind::NonPanicPathOnly); + } + } + TerminatorKind::InlineAsm { + template: _, + ref operands, + options: _, + line_spans: _, + destination: _, + } => { + for op in operands { + match *op { + InlineAsmOperand::In { reg: _, ref value } + | InlineAsmOperand::Const { ref value } => { + self.gather_operand(value); + } + InlineAsmOperand::Out { reg: _, late: _, place, .. } => { + if let Some(place) = place { + self.create_move_path(place); + self.gather_init(place.as_ref(), InitKind::Deep); + } + } + InlineAsmOperand::InOut { reg: _, late: _, ref in_value, out_place } => { + self.gather_operand(in_value); + if let Some(out_place) = out_place { + self.create_move_path(out_place); + self.gather_init(out_place.as_ref(), InitKind::Deep); + } + } + InlineAsmOperand::SymFn { value: _ } + | InlineAsmOperand::SymStatic { def_id: _ } => {} + } + } + } + } + } + + fn gather_operand(&mut self, operand: &Operand<'tcx>) { + match *operand { + Operand::Constant(..) | Operand::Copy(..) => {} // not-a-move + Operand::Move(place) => { + // a move + self.gather_move(place); + } + } + } + + fn gather_move(&mut self, place: Place<'tcx>) { + debug!("gather_move({:?}, {:?})", self.loc, place); + + if let [ref base @ .., ProjectionElem::Subslice { from, to, from_end: false }] = + **place.projection + { + // Split `Subslice` patterns into the corresponding list of + // `ConstIndex` patterns. This is done to ensure that all move paths + // are disjoint, which is expected by drop elaboration. + let base_place = + Place { local: place.local, projection: self.builder.tcx.intern_place_elems(base) }; + let base_path = match self.move_path_for(base_place) { + Ok(path) => path, + Err(MoveError::UnionMove { path }) => { + self.record_move(place, path); + return; + } + Err(error @ MoveError::IllegalMove { .. }) => { + self.builder.errors.push((base_place, error)); + return; + } + }; + let base_ty = base_place.ty(self.builder.body, self.builder.tcx).ty; + let len: u64 = match base_ty.kind { + ty::Array(_, size) => { + let length = size.eval_usize(self.builder.tcx, self.builder.param_env); + length + .try_into() + .expect("slice pattern of array with more than u32::MAX elements") + } + _ => bug!("from_end: false slice pattern of non-array type"), + }; + for offset in from..to { + let elem = + ProjectionElem::ConstantIndex { offset, min_length: len, from_end: false }; + let path = + self.add_move_path(base_path, elem, |tcx| tcx.mk_place_elem(base_place, elem)); + self.record_move(place, path); + } + } else { + match self.move_path_for(place) { + Ok(path) | Err(MoveError::UnionMove { path }) => self.record_move(place, path), + Err(error @ MoveError::IllegalMove { .. }) => { + self.builder.errors.push((place, error)); + } + }; + } + } + + fn record_move(&mut self, place: Place<'tcx>, path: MovePathIndex) { + let move_out = self.builder.data.moves.push(MoveOut { path, source: self.loc }); + debug!( + "gather_move({:?}, {:?}): adding move {:?} of {:?}", + self.loc, place, move_out, path + ); + self.builder.data.path_map[path].push(move_out); + self.builder.data.loc_map[self.loc].push(move_out); + } + + fn gather_init(&mut self, place: PlaceRef<'tcx>, kind: InitKind) { + debug!("gather_init({:?}, {:?})", self.loc, place); + + let mut place = place; + + // Check if we are assigning into a field of a union, if so, lookup the place + // of the union so it is marked as initialized again. + if let [proj_base @ .., ProjectionElem::Field(_, _)] = place.projection { + if let ty::Adt(def, _) = + Place::ty_from(place.local, proj_base, self.builder.body, self.builder.tcx).ty.kind + { + if def.is_union() { + place = PlaceRef { local: place.local, projection: proj_base } + } + } + } + + if let LookupResult::Exact(path) = self.builder.data.rev_lookup.find(place) { + let init = self.builder.data.inits.push(Init { + location: InitLocation::Statement(self.loc), + path, + kind, + }); + + debug!( + "gather_init({:?}, {:?}): adding init {:?} of {:?}", + self.loc, place, init, path + ); + + self.builder.data.init_path_map[path].push(init); + self.builder.data.init_loc_map[self.loc].push(init); + } + } +} diff --git a/compiler/rustc_mir/src/dataflow/move_paths/mod.rs b/compiler/rustc_mir/src/dataflow/move_paths/mod.rs new file mode 100644 index 00000000000..d66d2625d78 --- /dev/null +++ b/compiler/rustc_mir/src/dataflow/move_paths/mod.rs @@ -0,0 +1,415 @@ +use core::slice::Iter; +use rustc_data_structures::fx::FxHashMap; +use rustc_index::vec::{Enumerated, IndexVec}; +use rustc_middle::mir::*; +use rustc_middle::ty::{ParamEnv, Ty, TyCtxt}; +use rustc_span::Span; +use smallvec::SmallVec; + +use std::fmt; +use std::ops::{Index, IndexMut}; + +use self::abs_domain::{AbstractElem, Lift}; + +mod abs_domain; + +rustc_index::newtype_index! { + pub struct MovePathIndex { + DEBUG_FORMAT = "mp{}" + } +} + +rustc_index::newtype_index! { + pub struct MoveOutIndex { + DEBUG_FORMAT = "mo{}" + } +} + +rustc_index::newtype_index! { + pub struct InitIndex { + DEBUG_FORMAT = "in{}" + } +} + +impl MoveOutIndex { + pub fn move_path_index(&self, move_data: &MoveData<'_>) -> MovePathIndex { + move_data.moves[*self].path + } +} + +/// `MovePath` is a canonicalized representation of a path that is +/// moved or assigned to. +/// +/// It follows a tree structure. +/// +/// Given `struct X { m: M, n: N }` and `x: X`, moves like `drop x.m;` +/// move *out* of the place `x.m`. +/// +/// The MovePaths representing `x.m` and `x.n` are siblings (that is, +/// one of them will link to the other via the `next_sibling` field, +/// and the other will have no entry in its `next_sibling` field), and +/// they both have the MovePath representing `x` as their parent. +#[derive(Clone)] +pub struct MovePath<'tcx> { + pub next_sibling: Option<MovePathIndex>, + pub first_child: Option<MovePathIndex>, + pub parent: Option<MovePathIndex>, + pub place: Place<'tcx>, +} + +impl<'tcx> MovePath<'tcx> { + /// Returns an iterator over the parents of `self`. + pub fn parents<'a>( + &self, + move_paths: &'a IndexVec<MovePathIndex, MovePath<'tcx>>, + ) -> impl 'a + Iterator<Item = (MovePathIndex, &'a MovePath<'tcx>)> { + let first = self.parent.map(|mpi| (mpi, &move_paths[mpi])); + MovePathLinearIter { + next: first, + fetch_next: move |_, parent: &MovePath<'_>| { + parent.parent.map(|mpi| (mpi, &move_paths[mpi])) + }, + } + } + + /// Returns an iterator over the immediate children of `self`. + pub fn children<'a>( + &self, + move_paths: &'a IndexVec<MovePathIndex, MovePath<'tcx>>, + ) -> impl 'a + Iterator<Item = (MovePathIndex, &'a MovePath<'tcx>)> { + let first = self.first_child.map(|mpi| (mpi, &move_paths[mpi])); + MovePathLinearIter { + next: first, + fetch_next: move |_, child: &MovePath<'_>| { + child.next_sibling.map(|mpi| (mpi, &move_paths[mpi])) + }, + } + } + + /// Finds the closest descendant of `self` for which `f` returns `true` using a breadth-first + /// search. + /// + /// `f` will **not** be called on `self`. + pub fn find_descendant( + &self, + move_paths: &IndexVec<MovePathIndex, MovePath<'_>>, + f: impl Fn(MovePathIndex) -> bool, + ) -> Option<MovePathIndex> { + let mut todo = if let Some(child) = self.first_child { + vec![child] + } else { + return None; + }; + + while let Some(mpi) = todo.pop() { + if f(mpi) { + return Some(mpi); + } + + let move_path = &move_paths[mpi]; + if let Some(child) = move_path.first_child { + todo.push(child); + } + + // After we've processed the original `mpi`, we should always + // traverse the siblings of any of its children. + if let Some(sibling) = move_path.next_sibling { + todo.push(sibling); + } + } + + None + } +} + +impl<'tcx> fmt::Debug for MovePath<'tcx> { + fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(w, "MovePath {{")?; + if let Some(parent) = self.parent { + write!(w, " parent: {:?},", parent)?; + } + if let Some(first_child) = self.first_child { + write!(w, " first_child: {:?},", first_child)?; + } + if let Some(next_sibling) = self.next_sibling { + write!(w, " next_sibling: {:?}", next_sibling)?; + } + write!(w, " place: {:?} }}", self.place) + } +} + +impl<'tcx> fmt::Display for MovePath<'tcx> { + fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(w, "{:?}", self.place) + } +} + +#[allow(unused)] +struct MovePathLinearIter<'a, 'tcx, F> { + next: Option<(MovePathIndex, &'a MovePath<'tcx>)>, + fetch_next: F, +} + +impl<'a, 'tcx, F> Iterator for MovePathLinearIter<'a, 'tcx, F> +where + F: FnMut(MovePathIndex, &'a MovePath<'tcx>) -> Option<(MovePathIndex, &'a MovePath<'tcx>)>, +{ + type Item = (MovePathIndex, &'a MovePath<'tcx>); + + fn next(&mut self) -> Option<Self::Item> { + let ret = self.next.take()?; + self.next = (self.fetch_next)(ret.0, ret.1); + Some(ret) + } +} + +#[derive(Debug)] +pub struct MoveData<'tcx> { + pub move_paths: IndexVec<MovePathIndex, MovePath<'tcx>>, + pub moves: IndexVec<MoveOutIndex, MoveOut>, + /// Each Location `l` is mapped to the MoveOut's that are effects + /// of executing the code at `l`. (There can be multiple MoveOut's + /// for a given `l` because each MoveOut is associated with one + /// particular path being moved.) + pub loc_map: LocationMap<SmallVec<[MoveOutIndex; 4]>>, + pub path_map: IndexVec<MovePathIndex, SmallVec<[MoveOutIndex; 4]>>, + pub rev_lookup: MovePathLookup, + pub inits: IndexVec<InitIndex, Init>, + /// Each Location `l` is mapped to the Inits that are effects + /// of executing the code at `l`. + pub init_loc_map: LocationMap<SmallVec<[InitIndex; 4]>>, + pub init_path_map: IndexVec<MovePathIndex, SmallVec<[InitIndex; 4]>>, +} + +pub trait HasMoveData<'tcx> { + fn move_data(&self) -> &MoveData<'tcx>; +} + +#[derive(Debug)] +pub struct LocationMap<T> { + /// Location-indexed (BasicBlock for outer index, index within BB + /// for inner index) map. + pub(crate) map: IndexVec<BasicBlock, Vec<T>>, +} + +impl<T> Index<Location> for LocationMap<T> { + type Output = T; + fn index(&self, index: Location) -> &Self::Output { + &self.map[index.block][index.statement_index] + } +} + +impl<T> IndexMut<Location> for LocationMap<T> { + fn index_mut(&mut self, index: Location) -> &mut Self::Output { + &mut self.map[index.block][index.statement_index] + } +} + +impl<T> LocationMap<T> +where + T: Default + Clone, +{ + fn new(body: &Body<'_>) -> Self { + LocationMap { + map: body + .basic_blocks() + .iter() + .map(|block| vec![T::default(); block.statements.len() + 1]) + .collect(), + } + } +} + +/// `MoveOut` represents a point in a program that moves out of some +/// L-value; i.e., "creates" uninitialized memory. +/// +/// With respect to dataflow analysis: +/// - Generated by moves and declaration of uninitialized variables. +/// - Killed by assignments to the memory. +#[derive(Copy, Clone)] +pub struct MoveOut { + /// path being moved + pub path: MovePathIndex, + /// location of move + pub source: Location, +} + +impl fmt::Debug for MoveOut { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(fmt, "{:?}@{:?}", self.path, self.source) + } +} + +/// `Init` represents a point in a program that initializes some L-value; +#[derive(Copy, Clone)] +pub struct Init { + /// path being initialized + pub path: MovePathIndex, + /// location of initialization + pub location: InitLocation, + /// Extra information about this initialization + pub kind: InitKind, +} + +/// Initializations can be from an argument or from a statement. Arguments +/// do not have locations, in those cases the `Local` is kept.. +#[derive(Copy, Clone, Debug, PartialEq, Eq)] +pub enum InitLocation { + Argument(Local), + Statement(Location), +} + +/// Additional information about the initialization. +#[derive(Copy, Clone, Debug, PartialEq, Eq)] +pub enum InitKind { + /// Deep init, even on panic + Deep, + /// Only does a shallow init + Shallow, + /// This doesn't initialize the variable on panic (and a panic is possible). + NonPanicPathOnly, +} + +impl fmt::Debug for Init { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(fmt, "{:?}@{:?} ({:?})", self.path, self.location, self.kind) + } +} + +impl Init { + crate fn span<'tcx>(&self, body: &Body<'tcx>) -> Span { + match self.location { + InitLocation::Argument(local) => body.local_decls[local].source_info.span, + InitLocation::Statement(location) => body.source_info(location).span, + } + } +} + +/// Tables mapping from a place to its MovePathIndex. +#[derive(Debug)] +pub struct MovePathLookup { + locals: IndexVec<Local, MovePathIndex>, + + /// projections are made from a base-place and a projection + /// elem. The base-place will have a unique MovePathIndex; we use + /// the latter as the index into the outer vector (narrowing + /// subsequent search so that it is solely relative to that + /// base-place). For the remaining lookup, we map the projection + /// elem to the associated MovePathIndex. + projections: FxHashMap<(MovePathIndex, AbstractElem), MovePathIndex>, +} + +mod builder; + +#[derive(Copy, Clone, Debug)] +pub enum LookupResult { + Exact(MovePathIndex), + Parent(Option<MovePathIndex>), +} + +impl MovePathLookup { + // Unlike the builder `fn move_path_for` below, this lookup + // alternative will *not* create a MovePath on the fly for an + // unknown place, but will rather return the nearest available + // parent. + pub fn find(&self, place: PlaceRef<'_>) -> LookupResult { + let mut result = self.locals[place.local]; + + for elem in place.projection.iter() { + if let Some(&subpath) = self.projections.get(&(result, elem.lift())) { + result = subpath; + } else { + return LookupResult::Parent(Some(result)); + } + } + + LookupResult::Exact(result) + } + + pub fn find_local(&self, local: Local) -> MovePathIndex { + self.locals[local] + } + + /// An enumerated iterator of `local`s and their associated + /// `MovePathIndex`es. + pub fn iter_locals_enumerated(&self) -> Enumerated<Local, Iter<'_, MovePathIndex>> { + self.locals.iter_enumerated() + } +} + +#[derive(Debug)] +pub struct IllegalMoveOrigin<'tcx> { + pub(crate) location: Location, + pub(crate) kind: IllegalMoveOriginKind<'tcx>, +} + +#[derive(Debug)] +pub(crate) enum IllegalMoveOriginKind<'tcx> { + /// Illegal move due to attempt to move from behind a reference. + BorrowedContent { + /// The place the reference refers to: if erroneous code was trying to + /// move from `(*x).f` this will be `*x`. + target_place: Place<'tcx>, + }, + + /// Illegal move due to attempt to move from field of an ADT that + /// implements `Drop`. Rust maintains invariant that all `Drop` + /// ADT's remain fully-initialized so that user-defined destructor + /// can safely read from all of the ADT's fields. + InteriorOfTypeWithDestructor { container_ty: Ty<'tcx> }, + + /// Illegal move due to attempt to move out of a slice or array. + InteriorOfSliceOrArray { ty: Ty<'tcx>, is_index: bool }, +} + +#[derive(Debug)] +pub enum MoveError<'tcx> { + IllegalMove { cannot_move_out_of: IllegalMoveOrigin<'tcx> }, + UnionMove { path: MovePathIndex }, +} + +impl<'tcx> MoveError<'tcx> { + fn cannot_move_out_of(location: Location, kind: IllegalMoveOriginKind<'tcx>) -> Self { + let origin = IllegalMoveOrigin { location, kind }; + MoveError::IllegalMove { cannot_move_out_of: origin } + } +} + +impl<'tcx> MoveData<'tcx> { + pub fn gather_moves( + body: &Body<'tcx>, + tcx: TyCtxt<'tcx>, + param_env: ParamEnv<'tcx>, + ) -> Result<Self, (Self, Vec<(Place<'tcx>, MoveError<'tcx>)>)> { + builder::gather_moves(body, tcx, param_env) + } + + /// For the move path `mpi`, returns the root local variable (if any) that starts the path. + /// (e.g., for a path like `a.b.c` returns `Some(a)`) + pub fn base_local(&self, mut mpi: MovePathIndex) -> Option<Local> { + loop { + let path = &self.move_paths[mpi]; + if let Some(l) = path.place.as_local() { + return Some(l); + } + if let Some(parent) = path.parent { + mpi = parent; + continue; + } else { + return None; + } + } + } + + pub fn find_in_move_path_or_its_descendants( + &self, + root: MovePathIndex, + pred: impl Fn(MovePathIndex) -> bool, + ) -> Option<MovePathIndex> { + if pred(root) { + return Some(root); + } + + self.move_paths[root].find_descendant(&self.move_paths, pred) + } +} |