rustc_mir_dataflow/move_paths/
builder.rs

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

rustc_mir_dataflow/move_paths/
builder.rs
