rustc_mir_dataflow/move_paths/
builder.rs

Help
1use std::mem;
2
3use rustc_index::IndexVec;
4use rustc_middle::mir::tcx::{PlaceTy, RvalueInitializationState};
5use rustc_middle::mir::*;
6use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitableExt};
7use rustc_middle::{bug, span_bug};
8use smallvec::{SmallVec, smallvec};
9use tracing::debug;
10
11use super::abs_domain::Lift;
12use super::{
13    Init, InitIndex, InitKind, InitLocation, LocationMap, LookupResult, MoveData, MoveOut,
14    MoveOutIndex, MovePath, MovePathIndex, MovePathLookup,
15};
16
17struct MoveDataBuilder<'a, 'tcx, F> {
18    body: &'a Body<'tcx>,
19    loc: Location,
20    tcx: TyCtxt<'tcx>,
21    data: MoveData<'tcx>,
22    filter: F,
23}
24
25impl<'a, 'tcx, F: Fn(Ty<'tcx>) -> bool> MoveDataBuilder<'a, 'tcx, F> {
26    fn new(body: &'a Body<'tcx>, tcx: TyCtxt<'tcx>, filter: F) -> Self {
27        let mut move_paths = IndexVec::new();
28        let mut path_map = IndexVec::new();
29        let mut init_path_map = IndexVec::new();
30
31        let locals = body
32            .local_decls
33            .iter_enumerated()
34            .map(|(i, l)| {
35                if l.is_deref_temp() {
36                    return None;
37                }
38                if filter(l.ty) {
39                    Some(new_move_path(
40                        &mut move_paths,
41                        &mut path_map,
42                        &mut init_path_map,
43                        None,
44                        Place::from(i),
45                    ))
46                } else {
47                    None
48                }
49            })
50            .collect();
51
52        MoveDataBuilder {
53            body,
54            loc: Location::START,
55            tcx,
56            data: MoveData {
57                moves: IndexVec::new(),
58                loc_map: LocationMap::new(body),
59                rev_lookup: MovePathLookup {
60                    locals,
61                    projections: Default::default(),
62                    un_derefer: Default::default(),
63                },
64                move_paths,
65                path_map,
66                inits: IndexVec::new(),
67                init_loc_map: LocationMap::new(body),
68                init_path_map,
69            },
70            filter,
71        }
72    }
73}
74
75fn new_move_path<'tcx>(
76    move_paths: &mut IndexVec<MovePathIndex, MovePath<'tcx>>,
77    path_map: &mut IndexVec<MovePathIndex, SmallVec<[MoveOutIndex; 4]>>,
78    init_path_map: &mut IndexVec<MovePathIndex, SmallVec<[InitIndex; 4]>>,
79    parent: Option<MovePathIndex>,
80    place: Place<'tcx>,
81) -> MovePathIndex {
82    let move_path =
83        move_paths.push(MovePath { next_sibling: None, first_child: None, parent, place });
84
85    if let Some(parent) = parent {
86        let next_sibling = mem::replace(&mut move_paths[parent].first_child, Some(move_path));
87        move_paths[move_path].next_sibling = next_sibling;
88    }
89
90    let path_map_ent = path_map.push(smallvec![]);
91    assert_eq!(path_map_ent, move_path);
92
93    let init_path_map_ent = init_path_map.push(smallvec![]);
94    assert_eq!(init_path_map_ent, move_path);
95
96    move_path
97}
98
99enum MovePathResult {
100    Path(MovePathIndex),
101    Union(MovePathIndex),
102    Error,
103}
104
105impl<'a, 'tcx, F: Fn(Ty<'tcx>) -> bool> MoveDataBuilder<'a, 'tcx, F> {
106    /// This creates a MovePath for a given place, returning an `MovePathError`
107    /// if that place can't be moved from.
108    ///
109    /// NOTE: places behind references *do not* get a move path, which is
110    /// problematic for borrowck.
111    ///
112    /// Maybe we should have separate "borrowck" and "moveck" modes.
113    fn move_path_for(&mut self, place: Place<'tcx>) -> MovePathResult {
114        let data = &mut self.data;
115
116        debug!("lookup({:?})", place);
117        let Some(mut base) = data.rev_lookup.find_local(place.local) else {
118            return MovePathResult::Error;
119        };
120
121        // The move path index of the first union that we find. Once this is
122        // some we stop creating child move paths, since moves from unions
123        // move the whole thing.
124        // We continue looking for other move errors though so that moving
125        // from `*(u.f: &_)` isn't allowed.
126        let mut union_path = None;
127
128        for (place_ref, elem) in data.rev_lookup.un_derefer.iter_projections(place.as_ref()) {
129            let body = self.body;
130            let tcx = self.tcx;
131            let place_ty = place_ref.ty(body, tcx).ty;
132            if place_ty.references_error() {
133                return MovePathResult::Error;
134            }
135            match elem {
136                ProjectionElem::Deref => match place_ty.kind() {
137                    ty::Ref(..) | ty::RawPtr(..) => {
138                        return MovePathResult::Error;
139                    }
140                    ty::Adt(adt, _) => {
141                        if !adt.is_box() {
142                            bug!("Adt should be a box type when Place is deref");
143                        }
144                    }
145                    ty::Bool
146                    | ty::Char
147                    | ty::Int(_)
148                    | ty::Uint(_)
149                    | ty::Float(_)
150                    | ty::Foreign(_)
151                    | ty::Str
152                    | ty::Array(_, _)
153                    | ty::Pat(_, _)
154                    | ty::Slice(_)
155                    | ty::FnDef(_, _)
156                    | ty::FnPtr(..)
157                    | ty::Dynamic(_, _, _)
158                    | ty::Closure(..)
159                    | ty::CoroutineClosure(..)
160                    | ty::Coroutine(_, _)
161                    | ty::CoroutineWitness(..)
162                    | ty::Never
163                    | ty::Tuple(_)
164                    | ty::UnsafeBinder(_)
165                    | ty::Alias(_, _)
166                    | ty::Param(_)
167                    | ty::Bound(_, _)
168                    | ty::Infer(_)
169                    | ty::Error(_)
170                    | ty::Placeholder(_) => {
171                        bug!("When Place is Deref it's type shouldn't be {place_ty:#?}")
172                    }
173                },
174                ProjectionElem::Field(_, _) => match place_ty.kind() {
175                    ty::Adt(adt, _) => {
176                        if adt.has_dtor(tcx) {
177                            return MovePathResult::Error;
178                        }
179                        if adt.is_union() {
180                            union_path.get_or_insert(base);
181                        }
182                    }
183                    ty::Closure(..)
184                    | ty::CoroutineClosure(..)
185                    | ty::Coroutine(_, _)
186                    | ty::Tuple(_) => (),
187                    ty::Bool
188                    | ty::Char
189                    | ty::Int(_)
190                    | ty::Uint(_)
191                    | ty::Float(_)
192                    | ty::Foreign(_)
193                    | ty::Str
194                    | ty::Array(_, _)
195                    | ty::Pat(_, _)
196                    | ty::Slice(_)
197                    | ty::RawPtr(_, _)
198                    | ty::Ref(_, _, _)
199                    | ty::FnDef(_, _)
200                    | ty::FnPtr(..)
201                    | ty::Dynamic(_, _, _)
202                    | ty::CoroutineWitness(..)
203                    | ty::Never
204                    | ty::UnsafeBinder(_)
205                    | ty::Alias(_, _)
206                    | ty::Param(_)
207                    | ty::Bound(_, _)
208                    | ty::Infer(_)
209                    | ty::Error(_)
210                    | ty::Placeholder(_) => bug!(
211                        "When Place contains ProjectionElem::Field its type shouldn't be {place_ty:#?}"
212                    ),
213                },
214                ProjectionElem::ConstantIndex { .. } | ProjectionElem::Subslice { .. } => {
215                    match place_ty.kind() {
216                        ty::Slice(_) => {
217                            return MovePathResult::Error;
218                        }
219                        ty::Array(_, _) => (),
220                        _ => bug!("Unexpected type {:#?}", place_ty.is_array()),
221                    }
222                }
223                ProjectionElem::Index(_) => match place_ty.kind() {
224                    ty::Array(..) | ty::Slice(_) => {
225                        return MovePathResult::Error;
226                    }
227                    _ => bug!("Unexpected type {place_ty:#?}"),
228                },
229                ProjectionElem::UnwrapUnsafeBinder(_) => {}
230                // `OpaqueCast`:Only transmutes the type, so no moves there.
231                // `Downcast`  :Only changes information about a `Place` without moving.
232                // `Subtype`   :Only transmutes the type, so moves.
233                // So it's safe to skip these.
234                ProjectionElem::OpaqueCast(_)
235                | ProjectionElem::Subtype(_)
236                | ProjectionElem::Downcast(_, _) => (),
237            }
238            let elem_ty = PlaceTy::from_ty(place_ty).projection_ty(tcx, elem).ty;
239            if !(self.filter)(elem_ty) {
240                return MovePathResult::Error;
241            }
242            if union_path.is_none() {
243                // inlined from add_move_path because of a borrowck conflict with the iterator
244                base =
245                    *data.rev_lookup.projections.entry((base, elem.lift())).or_insert_with(|| {
246                        new_move_path(
247                            &mut data.move_paths,
248                            &mut data.path_map,
249                            &mut data.init_path_map,
250                            Some(base),
251                            place_ref.project_deeper(&[elem], tcx),
252                        )
253                    })
254            }
255        }
256
257        if let Some(base) = union_path {
258            // Move out of union - always move the entire union.
259            MovePathResult::Union(base)
260        } else {
261            MovePathResult::Path(base)
262        }
263    }
264
265    fn add_move_path(
266        &mut self,
267        base: MovePathIndex,
268        elem: PlaceElem<'tcx>,
269        mk_place: impl FnOnce(TyCtxt<'tcx>) -> Place<'tcx>,
270    ) -> MovePathIndex {
271        let MoveDataBuilder {
272            data: MoveData { rev_lookup, move_paths, path_map, init_path_map, .. },
273            tcx,
274            ..
275        } = self;
276        *rev_lookup.projections.entry((base, elem.lift())).or_insert_with(move || {
277            new_move_path(move_paths, path_map, init_path_map, Some(base), mk_place(*tcx))
278        })
279    }
280
281    fn create_move_path(&mut self, place: Place<'tcx>) {
282        // This is an non-moving access (such as an overwrite or
283        // drop), so this not being a valid move path is OK.
284        let _ = self.move_path_for(place);
285    }
286
287    fn finalize(self) -> MoveData<'tcx> {
288        debug!("{}", {
289            debug!("moves for {:?}:", self.body.span);
290            for (j, mo) in self.data.moves.iter_enumerated() {
291                debug!("    {:?} = {:?}", j, mo);
292            }
293            debug!("move paths for {:?}:", self.body.span);
294            for (j, path) in self.data.move_paths.iter_enumerated() {
295                debug!("    {:?} = {:?}", j, path);
296            }
297            "done dumping moves"
298        });
299
300        self.data
301    }
302}
303
304pub(super) fn gather_moves<'tcx>(
305    body: &Body<'tcx>,
306    tcx: TyCtxt<'tcx>,
307    filter: impl Fn(Ty<'tcx>) -> bool,
308) -> MoveData<'tcx> {
309    let mut builder = MoveDataBuilder::new(body, tcx, filter);
310
311    builder.gather_args();
312
313    for (bb, block) in body.basic_blocks.iter_enumerated() {
314        for (i, stmt) in block.statements.iter().enumerate() {
315            builder.loc = Location { block: bb, statement_index: i };
316            builder.gather_statement(stmt);
317        }
318
319        builder.loc = Location { block: bb, statement_index: block.statements.len() };
320        builder.gather_terminator(block.terminator());
321    }
322
323    builder.finalize()
324}
325
326impl<'a, 'tcx, F: Fn(Ty<'tcx>) -> bool> MoveDataBuilder<'a, 'tcx, F> {
327    fn gather_args(&mut self) {
328        for arg in self.body.args_iter() {
329            if let Some(path) = self.data.rev_lookup.find_local(arg) {
330                let init = self.data.inits.push(Init {
331                    path,
332                    kind: InitKind::Deep,
333                    location: InitLocation::Argument(arg),
334                });
335
336                debug!("gather_args: adding init {:?} of {:?} for argument {:?}", init, path, arg);
337
338                self.data.init_path_map[path].push(init);
339            }
340        }
341    }
342
343    fn gather_statement(&mut self, stmt: &Statement<'tcx>) {
344        debug!("gather_statement({:?}, {:?})", self.loc, stmt);
345        match &stmt.kind {
346            StatementKind::Assign(box (place, Rvalue::CopyForDeref(reffed))) => {
347                let local = place.as_local().unwrap();
348                assert!(self.body.local_decls[local].is_deref_temp());
349
350                let rev_lookup = &mut self.data.rev_lookup;
351
352                rev_lookup.un_derefer.insert(local, reffed.as_ref());
353                let base_local = rev_lookup.un_derefer.deref_chain(local).first().unwrap().local;
354                rev_lookup.locals[local] = rev_lookup.locals[base_local];
355            }
356            StatementKind::Assign(box (place, rval)) => {
357                self.create_move_path(*place);
358                if let RvalueInitializationState::Shallow = rval.initialization_state() {
359                    // Box starts out uninitialized - need to create a separate
360                    // move-path for the interior so it will be separate from
361                    // the exterior.
362                    self.create_move_path(self.tcx.mk_place_deref(*place));
363                    self.gather_init(place.as_ref(), InitKind::Shallow);
364                } else {
365                    self.gather_init(place.as_ref(), InitKind::Deep);
366                }
367                self.gather_rvalue(rval);
368            }
369            StatementKind::FakeRead(box (_, place)) => {
370                self.create_move_path(*place);
371            }
372            StatementKind::StorageLive(_) => {}
373            StatementKind::StorageDead(local) => {
374                // DerefTemp locals (results of CopyForDeref) don't actually move anything.
375                if !self.body.local_decls[*local].is_deref_temp() {
376                    self.gather_move(Place::from(*local));
377                }
378            }
379            StatementKind::SetDiscriminant { .. } | StatementKind::Deinit(..) => {
380                span_bug!(
381                    stmt.source_info.span,
382                    "SetDiscriminant/Deinit should not exist during borrowck"
383                );
384            }
385            StatementKind::Retag { .. }
386            | StatementKind::AscribeUserType(..)
387            | StatementKind::PlaceMention(..)
388            | StatementKind::Coverage(..)
389            | StatementKind::Intrinsic(..)
390            | StatementKind::ConstEvalCounter
391            | StatementKind::BackwardIncompatibleDropHint { .. }
392            | StatementKind::Nop => {}
393        }
394    }
395
396    fn gather_rvalue(&mut self, rvalue: &Rvalue<'tcx>) {
397        match *rvalue {
398            Rvalue::ThreadLocalRef(_) => {} // not-a-move
399            Rvalue::Use(ref operand)
400            | Rvalue::Repeat(ref operand, _)
401            | Rvalue::Cast(_, ref operand, _)
402            | Rvalue::ShallowInitBox(ref operand, _)
403            | Rvalue::UnaryOp(_, ref operand)
404            | Rvalue::WrapUnsafeBinder(ref operand, _) => self.gather_operand(operand),
405            Rvalue::BinaryOp(ref _binop, box (ref lhs, ref rhs)) => {
406                self.gather_operand(lhs);
407                self.gather_operand(rhs);
408            }
409            Rvalue::Aggregate(ref _kind, ref operands) => {
410                for operand in operands {
411                    self.gather_operand(operand);
412                }
413            }
414            Rvalue::CopyForDeref(..) => unreachable!(),
415            Rvalue::Ref(..)
416            | Rvalue::RawPtr(..)
417            | Rvalue::Discriminant(..)
418            | Rvalue::Len(..)
419            | Rvalue::NullaryOp(
420                NullOp::SizeOf
421                | NullOp::AlignOf
422                | NullOp::OffsetOf(..)
423                | NullOp::UbChecks
424                | NullOp::ContractChecks,
425                _,
426            ) => {}
427        }
428    }
429
430    fn gather_terminator(&mut self, term: &Terminator<'tcx>) {
431        debug!("gather_terminator({:?}, {:?})", self.loc, term);
432        match term.kind {
433            TerminatorKind::Goto { target: _ }
434            | TerminatorKind::FalseEdge { .. }
435            | TerminatorKind::FalseUnwind { .. }
436            // In some sense returning moves the return place into the current
437            // call's destination, however, since there are no statements after
438            // this that could possibly access the return place, this doesn't
439            // need recording.
440            | TerminatorKind::Return
441            | TerminatorKind::UnwindResume
442            | TerminatorKind::UnwindTerminate(_)
443            | TerminatorKind::CoroutineDrop
444            | TerminatorKind::Unreachable
445            | TerminatorKind::Drop { .. } => {}
446
447            TerminatorKind::Assert { ref cond, .. } => {
448                self.gather_operand(cond);
449            }
450
451            TerminatorKind::SwitchInt { ref discr, .. } => {
452                self.gather_operand(discr);
453            }
454
455            TerminatorKind::Yield { ref value, resume_arg: place, .. } => {
456                self.gather_operand(value);
457                self.create_move_path(place);
458                self.gather_init(place.as_ref(), InitKind::Deep);
459            }
460            TerminatorKind::Call {
461                ref func,
462                ref args,
463                destination,
464                target,
465                unwind: _,
466                call_source: _,
467                fn_span: _,
468            } => {
469                self.gather_operand(func);
470                for arg in args {
471                    self.gather_operand(&arg.node);
472                }
473                if let Some(_bb) = target {
474                    self.create_move_path(destination);
475                    self.gather_init(destination.as_ref(), InitKind::NonPanicPathOnly);
476                }
477            }
478            TerminatorKind::TailCall { ref func, ref args, .. } => {
479                self.gather_operand(func);
480                for arg in args {
481                    self.gather_operand(&arg.node);
482                }
483            }
484            TerminatorKind::InlineAsm {
485                asm_macro: _,
486                template: _,
487                ref operands,
488                options: _,
489                line_spans: _,
490                targets: _,
491                unwind: _,
492            } => {
493                for op in operands {
494                    match *op {
495                        InlineAsmOperand::In { reg: _, ref value }
496                         => {
497                            self.gather_operand(value);
498                        }
499                        InlineAsmOperand::Out { reg: _, late: _, place, .. } => {
500                            if let Some(place) = place {
501                                self.create_move_path(place);
502                                self.gather_init(place.as_ref(), InitKind::Deep);
503                            }
504                        }
505                        InlineAsmOperand::InOut { reg: _, late: _, ref in_value, out_place } => {
506                            self.gather_operand(in_value);
507                            if let Some(out_place) = out_place {
508                                self.create_move_path(out_place);
509                                self.gather_init(out_place.as_ref(), InitKind::Deep);
510                            }
511                        }
512                        InlineAsmOperand::Const { value: _ }
513                        | InlineAsmOperand::SymFn { value: _ }
514                        | InlineAsmOperand::SymStatic { def_id: _ }
515                        | InlineAsmOperand::Label { target_index: _ } => {}
516                    }
517                }
518            }
519        }
520    }
521
522    fn gather_operand(&mut self, operand: &Operand<'tcx>) {
523        match *operand {
524            Operand::Constant(..) | Operand::Copy(..) => {} // not-a-move
525            Operand::Move(place) => {
526                // a move
527                self.gather_move(place);
528            }
529        }
530    }
531
532    fn gather_move(&mut self, place: Place<'tcx>) {
533        debug!("gather_move({:?}, {:?})", self.loc, place);
534        if let [ref base @ .., ProjectionElem::Subslice { from, to, from_end: false }] =
535            **place.projection
536        {
537            // Split `Subslice` patterns into the corresponding list of
538            // `ConstIndex` patterns. This is done to ensure that all move paths
539            // are disjoint, which is expected by drop elaboration.
540            let base_place =
541                Place { local: place.local, projection: self.tcx.mk_place_elems(base) };
542            let base_path = match self.move_path_for(base_place) {
543                MovePathResult::Path(path) => path,
544                MovePathResult::Union(path) => {
545                    self.record_move(place, path);
546                    return;
547                }
548                MovePathResult::Error => {
549                    return;
550                }
551            };
552            let base_ty = base_place.ty(self.body, self.tcx).ty;
553            let len: u64 = match base_ty.kind() {
554                ty::Array(_, size) => size
555                    .try_to_target_usize(self.tcx)
556                    .expect("expected subslice projection on fixed-size array"),
557                _ => bug!("from_end: false slice pattern of non-array type"),
558            };
559            for offset in from..to {
560                let elem =
561                    ProjectionElem::ConstantIndex { offset, min_length: len, from_end: false };
562                let path =
563                    self.add_move_path(base_path, elem, |tcx| tcx.mk_place_elem(base_place, elem));
564                self.record_move(place, path);
565            }
566        } else {
567            match self.move_path_for(place) {
568                MovePathResult::Path(path) | MovePathResult::Union(path) => {
569                    self.record_move(place, path)
570                }
571                MovePathResult::Error => {}
572            };
573        }
574    }
575
576    fn record_move(&mut self, place: Place<'tcx>, path: MovePathIndex) {
577        let move_out = self.data.moves.push(MoveOut { path, source: self.loc });
578        debug!(
579            "gather_move({:?}, {:?}): adding move {:?} of {:?}",
580            self.loc, place, move_out, path
581        );
582        self.data.path_map[path].push(move_out);
583        self.data.loc_map[self.loc].push(move_out);
584    }
585
586    fn gather_init(&mut self, place: PlaceRef<'tcx>, kind: InitKind) {
587        debug!("gather_init({:?}, {:?})", self.loc, place);
588
589        let mut place = place;
590
591        // Check if we are assigning into a field of a union, if so, lookup the place
592        // of the union so it is marked as initialized again.
593        if let Some((place_base, ProjectionElem::Field(_, _))) = place.last_projection() {
594            if place_base.ty(self.body, self.tcx).ty.is_union() {
595                place = place_base;
596            }
597        }
598
599        if let LookupResult::Exact(path) = self.data.rev_lookup.find(place) {
600            let init = self.data.inits.push(Init {
601                location: InitLocation::Statement(self.loc),
602                path,
603                kind,
604            });
605
606            debug!(
607                "gather_init({:?}, {:?}): adding init {:?} of {:?}",
608                self.loc, place, init, path
609            );
610
611            self.data.init_path_map[path].push(init);
612            self.data.init_loc_map[self.loc].push(init);
613        }
614    }
615}
rustc_mir_dataflow/move_paths/builder.rs

rustc_mir_dataflow/move_paths/
builder.rs
