2 for_each_consumable, record_consumed_borrow::ConsumedAndBorrowedPlaces, DropRangesBuilder,
3 NodeInfo, PostOrderId, TrackedValue, TrackedValueIndex,
6 intravisit::{self, Visitor},
7 Body, Expr, ExprKind, Guard, HirId, LoopIdError,
9 use rustc_data_structures::{fx::FxHashMap, stable_set::FxHashSet};
11 use rustc_index::vec::IndexVec;
14 ty::{TyCtxt, TypeckResults},
18 /// Traverses the body to find the control flow graph and locations for the
19 /// relevant places are dropped or reinitialized.
21 /// The resulting structure still needs to be iterated to a fixed point, which
22 /// can be done with propagate_to_fixpoint in cfg_propagate.
23 pub(super) fn build_control_flow_graph<'tcx>(
26 typeck_results: &TypeckResults<'tcx>,
27 consumed_borrowed_places: ConsumedAndBorrowedPlaces,
28 body: &'tcx Body<'tcx>,
30 ) -> (DropRangesBuilder, FxHashSet<HirId>) {
31 let mut drop_range_visitor =
32 DropRangeVisitor::new(hir, tcx, typeck_results, consumed_borrowed_places, num_exprs);
33 intravisit::walk_body(&mut drop_range_visitor, body);
35 drop_range_visitor.drop_ranges.process_deferred_edges();
36 if let Some(filename) = &tcx.sess.opts.debugging_opts.dump_drop_tracking_cfg {
37 super::cfg_visualize::write_graph_to_file(&drop_range_visitor.drop_ranges, filename, tcx);
40 (drop_range_visitor.drop_ranges, drop_range_visitor.places.borrowed_temporaries)
43 /// This struct is used to gather the information for `DropRanges` to determine the regions of the
44 /// HIR tree for which a value is dropped.
46 /// We are interested in points where a variables is dropped or initialized, and the control flow
47 /// of the code. We identify locations in code by their post-order traversal index, so it is
48 /// important for this traversal to match that in `RegionResolutionVisitor` and `InteriorVisitor`.
50 /// We make several simplifying assumptions, with the goal of being more conservative than
51 /// necessary rather than less conservative (since being less conservative is unsound, but more
52 /// conservative is still safe). These assumptions are:
54 /// 1. Moving a variable `a` counts as a move of the whole variable.
55 /// 2. Moving a partial path like `a.b.c` is ignored.
56 /// 3. Reinitializing through a field (e.g. `a.b.c = 5`) counts as a reinitialization of all of
63 /// let mut a = (vec![0], vec![0]);
65 /// // `a` is not considered initialized.
70 /// let mut a = (vec![0], vec![0]);
73 /// // `a` is still considered initialized.
77 /// ```compile_fail,E0382
78 /// let mut a = (vec![0], vec![0]);
81 /// // all of `a` is considered initialized
84 struct DropRangeVisitor<'a, 'tcx> {
86 places: ConsumedAndBorrowedPlaces,
87 drop_ranges: DropRangesBuilder,
88 expr_index: PostOrderId,
90 typeck_results: &'a TypeckResults<'tcx>,
91 label_stack: Vec<(Option<rustc_ast::Label>, PostOrderId)>,
94 impl<'a, 'tcx> DropRangeVisitor<'a, 'tcx> {
98 typeck_results: &'a TypeckResults<'tcx>,
99 places: ConsumedAndBorrowedPlaces,
102 debug!("consumed_places: {:?}", places.consumed);
103 let drop_ranges = DropRangesBuilder::new(
104 places.consumed.iter().flat_map(|(_, places)| places.iter().cloned()),
112 expr_index: PostOrderId::from_u32(0),
119 fn record_drop(&mut self, value: TrackedValue) {
120 if self.places.borrowed.contains(&value) {
121 debug!("not marking {:?} as dropped because it is borrowed at some point", value);
123 debug!("marking {:?} as dropped at {:?}", value, self.expr_index);
124 let count = self.expr_index;
125 self.drop_ranges.drop_at(value, count);
129 /// ExprUseVisitor's consume callback doesn't go deep enough for our purposes in all
130 /// expressions. This method consumes a little deeper into the expression when needed.
131 fn consume_expr(&mut self, expr: &hir::Expr<'_>) {
132 debug!("consuming expr {:?}, count={:?}", expr.kind, self.expr_index);
137 .map_or(vec![], |places| places.iter().cloned().collect());
138 for place in places {
139 trace!(?place, "consuming place");
140 for_each_consumable(self.hir, place, |value| self.record_drop(value));
144 /// Marks an expression as being reinitialized.
146 /// Note that we always approximated on the side of things being more
147 /// initialized than they actually are, as opposed to less. In cases such
148 /// as `x.y = ...`, we would consider all of `x` as being initialized
149 /// instead of just the `y` field.
151 /// This is because it is always safe to consider something initialized
152 /// even when it is not, but the other way around will cause problems.
154 /// In the future, we will hopefully tighten up these rules to be more
156 fn reinit_expr(&mut self, expr: &hir::Expr<'_>) {
157 // Walk the expression to find the base. For example, in an expression
158 // like `*a[i].x`, we want to find the `a` and mark that as
161 ExprKind::Path(hir::QPath::Resolved(
163 hir::Path { res: hir::def::Res::Local(hir_id), .. },
165 // This is the base case, where we have found an actual named variable.
167 let location = self.expr_index;
168 debug!("reinitializing {:?} at {:?}", hir_id, location);
169 self.drop_ranges.reinit_at(TrackedValue::Variable(*hir_id), location);
172 ExprKind::Field(base, _) => self.reinit_expr(base),
174 // Most expressions do not refer to something where we need to track
175 // reinitializations.
177 // Some of these may be interesting in the future
180 | ExprKind::ConstBlock(..)
181 | ExprKind::Array(..)
183 | ExprKind::MethodCall(..)
185 | ExprKind::Binary(..)
186 | ExprKind::Unary(..)
190 | ExprKind::DropTemps(..)
194 | ExprKind::Match(..)
195 | ExprKind::Closure { .. }
196 | ExprKind::Block(..)
197 | ExprKind::Assign(..)
198 | ExprKind::AssignOp(..)
199 | ExprKind::Index(..)
200 | ExprKind::AddrOf(..)
201 | ExprKind::Break(..)
202 | ExprKind::Continue(..)
204 | ExprKind::InlineAsm(..)
205 | ExprKind::Struct(..)
206 | ExprKind::Repeat(..)
207 | ExprKind::Yield(..)
208 | ExprKind::Err => (),
212 /// For an expression with an uninhabited return type (e.g. a function that returns !),
213 /// this adds a self edge to to the CFG to model the fact that the function does not
215 fn handle_uninhabited_return(&mut self, expr: &Expr<'tcx>) {
216 let ty = self.typeck_results.expr_ty(expr);
217 let ty = self.tcx.erase_regions(ty);
218 let m = self.tcx.parent_module(expr.hir_id).to_def_id();
219 let param_env = self.tcx.param_env(m.expect_local());
220 if self.tcx.is_ty_uninhabited_from(m, ty, param_env) {
221 // This function will not return. We model this fact as an infinite loop.
222 self.drop_ranges.add_control_edge(self.expr_index + 1, self.expr_index + 1);
226 /// Map a Destination to an equivalent expression node
228 /// The destination field of a Break or Continue expression can target either an
229 /// expression or a block. The drop range analysis, however, only deals in
230 /// expression nodes, so blocks that might be the destination of a Break or Continue
231 /// will not have a PostOrderId.
233 /// If the destination is an expression, this function will simply return that expression's
234 /// hir_id. If the destination is a block, this function will return the hir_id of last
235 /// expression in the block.
236 fn find_target_expression_from_destination(
238 destination: hir::Destination,
239 ) -> Result<HirId, LoopIdError> {
240 destination.target_id.map(|target| {
241 let node = self.hir.get(target);
243 hir::Node::Expr(_) => target,
244 hir::Node::Block(b) => find_last_block_expression(b),
246 | hir::Node::Item(..)
247 | hir::Node::ForeignItem(..)
248 | hir::Node::TraitItem(..)
249 | hir::Node::ImplItem(..)
250 | hir::Node::Variant(..)
251 | hir::Node::Field(..)
252 | hir::Node::AnonConst(..)
253 | hir::Node::Stmt(..)
254 | hir::Node::PathSegment(..)
256 | hir::Node::TypeBinding(..)
257 | hir::Node::TraitRef(..)
258 | hir::Node::Binding(..)
261 | hir::Node::Local(..)
262 | hir::Node::Ctor(..)
263 | hir::Node::Lifetime(..)
264 | hir::Node::GenericParam(..)
265 | hir::Node::Crate(..)
266 | hir::Node::Infer(..) => bug!("Unsupported branch target: {:?}", node),
272 fn find_last_block_expression(block: &hir::Block<'_>) -> HirId {
273 block.expr.map_or_else(
274 // If there is no tail expression, there will be at least one statement in the
275 // block because the block contains a break or continue statement.
276 || block.stmts.last().unwrap().hir_id,
281 impl<'a, 'tcx> Visitor<'tcx> for DropRangeVisitor<'a, 'tcx> {
282 fn visit_expr(&mut self, expr: &'tcx Expr<'tcx>) {
283 let mut reinit = None;
285 ExprKind::Assign(lhs, rhs, _) => {
286 self.visit_expr(lhs);
287 self.visit_expr(rhs);
292 ExprKind::If(test, if_true, if_false) => {
293 self.visit_expr(test);
295 let fork = self.expr_index;
297 self.drop_ranges.add_control_edge(fork, self.expr_index + 1);
298 self.visit_expr(if_true);
299 let true_end = self.expr_index;
301 self.drop_ranges.add_control_edge(fork, self.expr_index + 1);
302 if let Some(if_false) = if_false {
303 self.visit_expr(if_false);
306 self.drop_ranges.add_control_edge(true_end, self.expr_index + 1);
308 ExprKind::Match(scrutinee, arms, ..) => {
309 // We walk through the match expression almost like a chain of if expressions.
310 // Here's a diagram to follow along with:
318 // └─┘ ├─┴──►└─┴──────┐
323 // │E│ if │F│ =>│G│, │
327 // ┌─┐◄───────────────────┘
331 // The order we want is that the scrutinee (A) flows into the first pattern (B),
332 // which flows into the guard (C). Then the guard either flows into the arm body
333 // (D) or into the start of the next arm (E). Finally, the body flows to the end
334 // of the match block (H).
336 // The subsequent arms follow the same ordering. First we go to the pattern, then
337 // the guard (if present, otherwise it flows straight into the body), then into
338 // the body and then to the end of the match expression.
340 // The comments below show which edge is being added.
341 self.visit_expr(scrutinee);
343 let (guard_exit, arm_end_ids) = arms.iter().fold(
344 (self.expr_index, vec![]),
345 |(incoming_edge, mut arm_end_ids), hir::Arm { pat, body, guard, .. }| {
347 self.drop_ranges.add_control_edge(incoming_edge, self.expr_index + 1);
349 // B -> C and E -> F are added implicitly due to the traversal order.
351 Some(Guard::If(expr)) => self.visit_expr(expr),
352 Some(Guard::IfLet(let_expr)) => {
353 self.visit_let_expr(let_expr);
357 // Likewise, C -> D and F -> G are added implicitly.
359 // Save C, F, so we can add the other outgoing edge.
360 let to_next_arm = self.expr_index;
362 // The default edge does not get added since we also have an explicit edge,
363 // so we also need to add an edge to the next node as well.
365 // This adds C -> D, F -> G
366 self.drop_ranges.add_control_edge(self.expr_index, self.expr_index + 1);
367 self.visit_expr(body);
369 // Save the end of the body so we can add the exit edge once we know where
371 arm_end_ids.push(self.expr_index);
373 // Pass C to the next iteration, as well as vec![D]
375 // On the last round through, we pass F and vec![D, G] so that we can
376 // add all the exit edges.
377 (to_next_arm, arm_end_ids)
381 self.drop_ranges.add_control_edge(guard_exit, self.expr_index + 1);
383 arm_end_ids.into_iter().for_each(|arm_end| {
385 self.drop_ranges.add_control_edge(arm_end, self.expr_index + 1)
389 ExprKind::Loop(body, label, ..) => {
390 let loop_begin = self.expr_index + 1;
391 self.label_stack.push((label, loop_begin));
392 if body.stmts.is_empty() && body.expr.is_none() {
393 // For empty loops we won't have updated self.expr_index after visiting the
394 // body, meaning we'd get an edge from expr_index to expr_index + 1, but
395 // instead we want an edge from expr_index + 1 to expr_index + 1.
396 self.drop_ranges.add_control_edge(loop_begin, loop_begin);
398 self.visit_block(body);
399 self.drop_ranges.add_control_edge(self.expr_index, loop_begin);
401 self.label_stack.pop();
403 // Find the loop entry by searching through the label stack for either the last entry
404 // (if label is none), or the first entry where the label matches this one. The Loop
405 // case maintains this stack mapping labels to the PostOrderId for the loop entry.
406 ExprKind::Continue(hir::Destination { label, .. }, ..) => self
410 .find(|(loop_label, _)| label.is_none() || *loop_label == label)
411 .map_or((), |(_, target)| {
412 self.drop_ranges.add_control_edge(self.expr_index, *target)
415 ExprKind::Break(destination, ..) => {
416 // destination either points to an expression or to a block. We use
417 // find_target_expression_from_destination to use the last expression of the block
418 // if destination points to a block.
420 // We add an edge to the hir_id of the expression/block we are breaking out of, and
421 // then in process_deferred_edges we will map this hir_id to its PostOrderId, which
422 // will refer to the end of the block due to the post order traversal.
423 self.find_target_expression_from_destination(destination).map_or((), |target| {
424 self.drop_ranges.add_control_edge_hir_id(self.expr_index, target)
428 ExprKind::Call(f, args) => {
431 self.visit_expr(arg);
434 self.handle_uninhabited_return(expr);
436 ExprKind::MethodCall(_, exprs, _) => {
438 self.visit_expr(expr);
441 self.handle_uninhabited_return(expr);
445 | ExprKind::Array(..)
446 | ExprKind::AssignOp(..)
447 | ExprKind::Binary(..)
448 | ExprKind::Block(..)
451 | ExprKind::Closure { .. }
452 | ExprKind::ConstBlock(..)
453 | ExprKind::DropTemps(..)
455 | ExprKind::Field(..)
456 | ExprKind::Index(..)
457 | ExprKind::InlineAsm(..)
461 | ExprKind::Repeat(..)
463 | ExprKind::Struct(..)
466 | ExprKind::Unary(..)
467 | ExprKind::Yield(..) => intravisit::walk_expr(self, expr),
470 self.expr_index = self.expr_index + 1;
471 self.drop_ranges.add_node_mapping(expr.hir_id, self.expr_index);
472 self.consume_expr(expr);
473 if let Some(expr) = reinit {
474 self.reinit_expr(expr);
478 fn visit_pat(&mut self, pat: &'tcx hir::Pat<'tcx>) {
479 intravisit::walk_pat(self, pat);
481 // Increment expr_count here to match what InteriorVisitor expects.
482 self.expr_index = self.expr_index + 1;
486 impl DropRangesBuilder {
488 tracked_values: impl Iterator<Item = TrackedValue>,
492 let mut tracked_value_map = FxHashMap::<_, TrackedValueIndex>::default();
493 let mut next = <_>::from(0u32);
494 for value in tracked_values {
495 for_each_consumable(hir, value, |value| {
496 if !tracked_value_map.contains_key(&value) {
497 tracked_value_map.insert(value, next);
502 debug!("hir_id_map: {:?}", tracked_value_map);
503 let num_values = tracked_value_map.len();
506 nodes: IndexVec::from_fn_n(|_| NodeInfo::new(num_values), num_exprs + 1),
507 deferred_edges: <_>::default(),
508 post_order_map: <_>::default(),
512 fn tracked_value_index(&self, tracked_value: TrackedValue) -> TrackedValueIndex {
513 *self.tracked_value_map.get(&tracked_value).unwrap()
516 /// Adds an entry in the mapping from HirIds to PostOrderIds
518 /// Needed so that `add_control_edge_hir_id` can work.
519 fn add_node_mapping(&mut self, node_hir_id: HirId, post_order_id: PostOrderId) {
520 self.post_order_map.insert(node_hir_id, post_order_id);
523 /// Like add_control_edge, but uses a hir_id as the target.
525 /// This can be used for branches where we do not know the PostOrderId of the target yet,
526 /// such as when handling `break` or `continue`.
527 fn add_control_edge_hir_id(&mut self, from: PostOrderId, to: HirId) {
528 self.deferred_edges.push((from, to));
531 fn drop_at(&mut self, value: TrackedValue, location: PostOrderId) {
532 let value = self.tracked_value_index(value);
533 self.node_mut(location).drops.push(value);
536 fn reinit_at(&mut self, value: TrackedValue, location: PostOrderId) {
537 let value = match self.tracked_value_map.get(&value) {
538 Some(value) => *value,
539 // If there's no value, this is never consumed and therefore is never dropped. We can
543 self.node_mut(location).reinits.push(value);
546 /// Looks up PostOrderId for any control edges added by HirId and adds a proper edge for them.
548 /// Should be called after visiting the HIR but before solving the control flow, otherwise some
549 /// edges will be missed.
550 fn process_deferred_edges(&mut self) {
551 trace!("processing deferred edges. post_order_map={:#?}", self.post_order_map);
552 let mut edges = vec![];
553 swap(&mut edges, &mut self.deferred_edges);
554 edges.into_iter().for_each(|(from, to)| {
555 trace!("Adding deferred edge from {:?} to {:?}", from, to);
556 let to = *self.post_order_map.get(&to).expect("Expression ID not found");
557 trace!("target edge PostOrderId={:?}", to);
558 self.add_control_edge(from, to)