compiler/rustc_hir_analysis/src/check/generator_interior/drop_ranges/cfg_build.rs

   1 use super::{
   2     for_each_consumable, record_consumed_borrow::ConsumedAndBorrowedPlaces, DropRangesBuilder,
   3     NodeInfo, PostOrderId, TrackedValue, TrackedValueIndex,
   4 };
   5 use hir::{
   6     intravisit::{self, Visitor},
   7     Body, Expr, ExprKind, Guard, HirId, LoopIdError,
   8 };
   9 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  10 use rustc_hir as hir;
  11 use rustc_index::vec::IndexVec;
  12 use rustc_middle::{
  13     hir::map::Map,
  14     ty::{TyCtxt, TypeckResults},
  15 };
  16 use std::mem::swap;
  17
  18 /// Traverses the body to find the control flow graph and locations for the
  19 /// relevant places are dropped or reinitialized.
  20 ///
  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>(
  24     hir: Map<'tcx>,
  25     tcx: TyCtxt<'tcx>,
  26     typeck_results: &TypeckResults<'tcx>,
  27     consumed_borrowed_places: ConsumedAndBorrowedPlaces,
  28     body: &'tcx Body<'tcx>,
  29     num_exprs: usize,
  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);
  34
  35     drop_range_visitor.drop_ranges.process_deferred_edges();
  36     if let Some(filename) = &tcx.sess.opts.unstable_opts.dump_drop_tracking_cfg {
  37         super::cfg_visualize::write_graph_to_file(&drop_range_visitor.drop_ranges, filename, tcx);
  38     }
  39
  40     (drop_range_visitor.drop_ranges, drop_range_visitor.places.borrowed_temporaries)
  41 }
  42
  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.
  45 ///
  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`.
  49 ///
  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:
  53 ///
  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
  57 ///    `a`.
  58 ///
  59 /// Some examples:
  60 ///
  61 /// Rule 1:
  62 /// ```rust
  63 /// let mut a = (vec![0], vec![0]);
  64 /// drop(a);
  65 /// // `a` is not considered initialized.
  66 /// ```
  67 ///
  68 /// Rule 2:
  69 /// ```rust
  70 /// let mut a = (vec![0], vec![0]);
  71 /// drop(a.0);
  72 /// drop(a.1);
  73 /// // `a` is still considered initialized.
  74 /// ```
  75 ///
  76 /// Rule 3:
  77 /// ```compile_fail,E0382
  78 /// let mut a = (vec![0], vec![0]);
  79 /// drop(a);
  80 /// a.1 = vec![1];
  81 /// // all of `a` is considered initialized
  82 /// ```
  83
  84 struct DropRangeVisitor<'a, 'tcx> {
  85     hir: Map<'tcx>,
  86     places: ConsumedAndBorrowedPlaces,
  87     drop_ranges: DropRangesBuilder,
  88     expr_index: PostOrderId,
  89     tcx: TyCtxt<'tcx>,
  90     typeck_results: &'a TypeckResults<'tcx>,
  91     label_stack: Vec<(Option<rustc_ast::Label>, PostOrderId)>,
  92 }
  93
  94 impl<'a, 'tcx> DropRangeVisitor<'a, 'tcx> {
  95     fn new(
  96         hir: Map<'tcx>,
  97         tcx: TyCtxt<'tcx>,
  98         typeck_results: &'a TypeckResults<'tcx>,
  99         places: ConsumedAndBorrowedPlaces,
 100         num_exprs: usize,
 101     ) -> Self {
 102         debug!("consumed_places: {:?}", places.consumed);
 103         let drop_ranges = DropRangesBuilder::new(
 104             places.consumed.iter().flat_map(|(_, places)| places.iter().cloned()),
 105             hir,
 106             num_exprs,
 107         );
 108         Self {
 109             hir,
 110             places,
 111             drop_ranges,
 112             expr_index: PostOrderId::from_u32(0),
 113             typeck_results,
 114             tcx,
 115             label_stack: vec![],
 116         }
 117     }
 118
 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);
 122         } else {
 123             debug!("marking {:?} as dropped at {:?}", value, self.expr_index);
 124             let count = self.expr_index;
 125             self.drop_ranges.drop_at(value, count);
 126         }
 127     }
 128
 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);
 133         let places = self
 134             .places
 135             .consumed
 136             .get(&expr.hir_id)
 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));
 141         }
 142     }
 143
 144     /// Marks an expression as being reinitialized.
 145     ///
 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.
 150     ///
 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.
 153     ///
 154     /// In the future, we will hopefully tighten up these rules to be more
 155     /// precise.
 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
 159         // reinitialized.
 160         match expr.kind {
 161             ExprKind::Path(hir::QPath::Resolved(
 162                 _,
 163                 hir::Path { res: hir::def::Res::Local(hir_id), .. },
 164             )) => {
 165                 // This is the base case, where we have found an actual named variable.
 166
 167                 let location = self.expr_index;
 168                 debug!("reinitializing {:?} at {:?}", hir_id, location);
 169                 self.drop_ranges.reinit_at(TrackedValue::Variable(*hir_id), location);
 170             }
 171
 172             ExprKind::Field(base, _) => self.reinit_expr(base),
 173
 174             // Most expressions do not refer to something where we need to track
 175             // reinitializations.
 176             //
 177             // Some of these may be interesting in the future
 178             ExprKind::Path(..)
 179             | ExprKind::Box(..)
 180             | ExprKind::ConstBlock(..)
 181             | ExprKind::Array(..)
 182             | ExprKind::Call(..)
 183             | ExprKind::MethodCall(..)
 184             | ExprKind::Tup(..)
 185             | ExprKind::Binary(..)
 186             | ExprKind::Unary(..)
 187             | ExprKind::Lit(..)
 188             | ExprKind::Cast(..)
 189             | ExprKind::Type(..)
 190             | ExprKind::DropTemps(..)
 191             | ExprKind::Let(..)
 192             | ExprKind::If(..)
 193             | ExprKind::Loop(..)
 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(..)
 203             | ExprKind::Ret(..)
 204             | ExprKind::InlineAsm(..)
 205             | ExprKind::Struct(..)
 206             | ExprKind::Repeat(..)
 207             | ExprKind::Yield(..)
 208             | ExprKind::Err => (),
 209         }
 210     }
 211
 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
 214     /// return.
 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);
 223         }
 224     }
 225
 226     /// Map a Destination to an equivalent expression node
 227     ///
 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.
 232     ///
 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(
 237         &self,
 238         destination: hir::Destination,
 239     ) -> Result<HirId, LoopIdError> {
 240         destination.target_id.map(|target| {
 241             let node = self.hir.get(target);
 242             match node {
 243                 hir::Node::Expr(_) => target,
 244                 hir::Node::Block(b) => find_last_block_expression(b),
 245                 hir::Node::Param(..)
 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(..)
 255                 | hir::Node::Ty(..)
 256                 | hir::Node::TypeBinding(..)
 257                 | hir::Node::TraitRef(..)
 258                 | hir::Node::Pat(..)
 259                 | hir::Node::PatField(..)
 260                 | hir::Node::ExprField(..)
 261                 | hir::Node::Arm(..)
 262                 | hir::Node::Local(..)
 263                 | hir::Node::Ctor(..)
 264                 | hir::Node::Lifetime(..)
 265                 | hir::Node::GenericParam(..)
 266                 | hir::Node::Crate(..)
 267                 | hir::Node::Infer(..) => bug!("Unsupported branch target: {:?}", node),
 268             }
 269         })
 270     }
 271 }
 272
 273 fn find_last_block_expression(block: &hir::Block<'_>) -> HirId {
 274     block.expr.map_or_else(
 275         // If there is no tail expression, there will be at least one statement in the
 276         // block because the block contains a break or continue statement.
 277         || block.stmts.last().unwrap().hir_id,
 278         |expr| expr.hir_id,
 279     )
 280 }
 281
 282 impl<'a, 'tcx> Visitor<'tcx> for DropRangeVisitor<'a, 'tcx> {
 283     fn visit_expr(&mut self, expr: &'tcx Expr<'tcx>) {
 284         let mut reinit = None;
 285         match expr.kind {
 286             ExprKind::Assign(lhs, rhs, _) => {
 287                 self.visit_expr(lhs);
 288                 self.visit_expr(rhs);
 289
 290                 reinit = Some(lhs);
 291             }
 292
 293             ExprKind::If(test, if_true, if_false) => {
 294                 self.visit_expr(test);
 295
 296                 let fork = self.expr_index;
 297
 298                 self.drop_ranges.add_control_edge(fork, self.expr_index + 1);
 299                 self.visit_expr(if_true);
 300                 let true_end = self.expr_index;
 301
 302                 self.drop_ranges.add_control_edge(fork, self.expr_index + 1);
 303                 if let Some(if_false) = if_false {
 304                     self.visit_expr(if_false);
 305                 }
 306
 307                 self.drop_ranges.add_control_edge(true_end, self.expr_index + 1);
 308             }
 309             ExprKind::Match(scrutinee, arms, ..) => {
 310                 // We walk through the match expression almost like a chain of if expressions.
 311                 // Here's a diagram to follow along with:
 312                 //
 313                 //           ┌─┐
 314                 //     match │A│ {
 315                 //       ┌───┴─┘
 316                 //       │
 317                 //      ┌▼┌───►┌─┐   ┌─┐
 318                 //      │B│ if │C│ =>│D│,
 319                 //      └─┘    ├─┴──►└─┴──────┐
 320                 //          ┌──┘              │
 321                 //       ┌──┘                 │
 322                 //       │                    │
 323                 //      ┌▼┌───►┌─┐   ┌─┐      │
 324                 //      │E│ if │F│ =>│G│,     │
 325                 //      └─┘    ├─┴──►└─┴┐     │
 326                 //             │        │     │
 327                 //     }       ▼        ▼     │
 328                 //     ┌─┐◄───────────────────┘
 329                 //     │H│
 330                 //     └─┘
 331                 //
 332                 // The order we want is that the scrutinee (A) flows into the first pattern (B),
 333                 // which flows into the guard (C). Then the guard either flows into the arm body
 334                 // (D) or into the start of the next arm (E). Finally, the body flows to the end
 335                 // of the match block (H).
 336                 //
 337                 // The subsequent arms follow the same ordering. First we go to the pattern, then
 338                 // the guard (if present, otherwise it flows straight into the body), then into
 339                 // the body and then to the end of the match expression.
 340                 //
 341                 // The comments below show which edge is being added.
 342                 self.visit_expr(scrutinee);
 343
 344                 let (guard_exit, arm_end_ids) = arms.iter().fold(
 345                     (self.expr_index, vec![]),
 346                     |(incoming_edge, mut arm_end_ids), hir::Arm { pat, body, guard, .. }| {
 347                         // A -> B, or C -> E
 348                         self.drop_ranges.add_control_edge(incoming_edge, self.expr_index + 1);
 349                         self.visit_pat(pat);
 350                         // B -> C and E -> F are added implicitly due to the traversal order.
 351                         match guard {
 352                             Some(Guard::If(expr)) => self.visit_expr(expr),
 353                             Some(Guard::IfLet(let_expr)) => {
 354                                 self.visit_let_expr(let_expr);
 355                             }
 356                             None => (),
 357                         }
 358                         // Likewise, C -> D and F -> G are added implicitly.
 359
 360                         // Save C, F, so we can add the other outgoing edge.
 361                         let to_next_arm = self.expr_index;
 362
 363                         // The default edge does not get added since we also have an explicit edge,
 364                         // so we also need to add an edge to the next node as well.
 365                         //
 366                         // This adds C -> D, F -> G
 367                         self.drop_ranges.add_control_edge(self.expr_index, self.expr_index + 1);
 368                         self.visit_expr(body);
 369
 370                         // Save the end of the body so we can add the exit edge once we know where
 371                         // the exit is.
 372                         arm_end_ids.push(self.expr_index);
 373
 374                         // Pass C to the next iteration, as well as vec![D]
 375                         //
 376                         // On the last round through, we pass F and vec![D, G] so that we can
 377                         // add all the exit edges.
 378                         (to_next_arm, arm_end_ids)
 379                     },
 380                 );
 381                 // F -> H
 382                 self.drop_ranges.add_control_edge(guard_exit, self.expr_index + 1);
 383
 384                 arm_end_ids.into_iter().for_each(|arm_end| {
 385                     // D -> H, G -> H
 386                     self.drop_ranges.add_control_edge(arm_end, self.expr_index + 1)
 387                 });
 388             }
 389
 390             ExprKind::Loop(body, label, ..) => {
 391                 let loop_begin = self.expr_index + 1;
 392                 self.label_stack.push((label, loop_begin));
 393                 if body.stmts.is_empty() && body.expr.is_none() {
 394                     // For empty loops we won't have updated self.expr_index after visiting the
 395                     // body, meaning we'd get an edge from expr_index to expr_index + 1, but
 396                     // instead we want an edge from expr_index + 1 to expr_index + 1.
 397                     self.drop_ranges.add_control_edge(loop_begin, loop_begin);
 398                 } else {
 399                     self.visit_block(body);
 400                     self.drop_ranges.add_control_edge(self.expr_index, loop_begin);
 401                 }
 402                 self.label_stack.pop();
 403             }
 404             // Find the loop entry by searching through the label stack for either the last entry
 405             // (if label is none), or the first entry where the label matches this one. The Loop
 406             // case maintains this stack mapping labels to the PostOrderId for the loop entry.
 407             ExprKind::Continue(hir::Destination { label, .. }, ..) => self
 408                 .label_stack
 409                 .iter()
 410                 .rev()
 411                 .find(|(loop_label, _)| label.is_none() || *loop_label == label)
 412                 .map_or((), |(_, target)| {
 413                     self.drop_ranges.add_control_edge(self.expr_index, *target)
 414                 }),
 415
 416             ExprKind::Break(destination, ..) => {
 417                 // destination either points to an expression or to a block. We use
 418                 // find_target_expression_from_destination to use the last expression of the block
 419                 // if destination points to a block.
 420                 //
 421                 // We add an edge to the hir_id of the expression/block we are breaking out of, and
 422                 // then in process_deferred_edges we will map this hir_id to its PostOrderId, which
 423                 // will refer to the end of the block due to the post order traversal.
 424                 self.find_target_expression_from_destination(destination).map_or((), |target| {
 425                     self.drop_ranges.add_control_edge_hir_id(self.expr_index, target)
 426                 })
 427             }
 428
 429             ExprKind::Call(f, args) => {
 430                 self.visit_expr(f);
 431                 for arg in args {
 432                     self.visit_expr(arg);
 433                 }
 434
 435                 self.handle_uninhabited_return(expr);
 436             }
 437             ExprKind::MethodCall(_, receiver, exprs, _) => {
 438                 self.visit_expr(receiver);
 439                 for expr in exprs {
 440                     self.visit_expr(expr);
 441                 }
 442
 443                 self.handle_uninhabited_return(expr);
 444             }
 445
 446             ExprKind::AddrOf(..)
 447             | ExprKind::Array(..)
 448             | ExprKind::AssignOp(..)
 449             | ExprKind::Binary(..)
 450             | ExprKind::Block(..)
 451             | ExprKind::Box(..)
 452             | ExprKind::Cast(..)
 453             | ExprKind::Closure { .. }
 454             | ExprKind::ConstBlock(..)
 455             | ExprKind::DropTemps(..)
 456             | ExprKind::Err
 457             | ExprKind::Field(..)
 458             | ExprKind::Index(..)
 459             | ExprKind::InlineAsm(..)
 460             | ExprKind::Let(..)
 461             | ExprKind::Lit(..)
 462             | ExprKind::Path(..)
 463             | ExprKind::Repeat(..)
 464             | ExprKind::Ret(..)
 465             | ExprKind::Struct(..)
 466             | ExprKind::Tup(..)
 467             | ExprKind::Type(..)
 468             | ExprKind::Unary(..)
 469             | ExprKind::Yield(..) => intravisit::walk_expr(self, expr),
 470         }
 471
 472         self.expr_index = self.expr_index + 1;
 473         self.drop_ranges.add_node_mapping(expr.hir_id, self.expr_index);
 474         self.consume_expr(expr);
 475         if let Some(expr) = reinit {
 476             self.reinit_expr(expr);
 477         }
 478     }
 479
 480     fn visit_pat(&mut self, pat: &'tcx hir::Pat<'tcx>) {
 481         intravisit::walk_pat(self, pat);
 482
 483         // Increment expr_count here to match what InteriorVisitor expects.
 484         self.expr_index = self.expr_index + 1;
 485     }
 486 }
 487
 488 impl DropRangesBuilder {
 489     fn new(
 490         tracked_values: impl Iterator<Item = TrackedValue>,
 491         hir: Map<'_>,
 492         num_exprs: usize,
 493     ) -> Self {
 494         let mut tracked_value_map = FxHashMap::<_, TrackedValueIndex>::default();
 495         let mut next = <_>::from(0u32);
 496         for value in tracked_values {
 497             for_each_consumable(hir, value, |value| {
 498                 if !tracked_value_map.contains_key(&value) {
 499                     tracked_value_map.insert(value, next);
 500                     next = next + 1;
 501                 }
 502             });
 503         }
 504         debug!("hir_id_map: {:?}", tracked_value_map);
 505         let num_values = tracked_value_map.len();
 506         Self {
 507             tracked_value_map,
 508             nodes: IndexVec::from_fn_n(|_| NodeInfo::new(num_values), num_exprs + 1),
 509             deferred_edges: <_>::default(),
 510             post_order_map: <_>::default(),
 511         }
 512     }
 513
 514     fn tracked_value_index(&self, tracked_value: TrackedValue) -> TrackedValueIndex {
 515         *self.tracked_value_map.get(&tracked_value).unwrap()
 516     }
 517
 518     /// Adds an entry in the mapping from HirIds to PostOrderIds
 519     ///
 520     /// Needed so that `add_control_edge_hir_id` can work.
 521     fn add_node_mapping(&mut self, node_hir_id: HirId, post_order_id: PostOrderId) {
 522         self.post_order_map.insert(node_hir_id, post_order_id);
 523     }
 524
 525     /// Like add_control_edge, but uses a hir_id as the target.
 526     ///
 527     /// This can be used for branches where we do not know the PostOrderId of the target yet,
 528     /// such as when handling `break` or `continue`.
 529     fn add_control_edge_hir_id(&mut self, from: PostOrderId, to: HirId) {
 530         self.deferred_edges.push((from, to));
 531     }
 532
 533     fn drop_at(&mut self, value: TrackedValue, location: PostOrderId) {
 534         let value = self.tracked_value_index(value);
 535         self.node_mut(location).drops.push(value);
 536     }
 537
 538     fn reinit_at(&mut self, value: TrackedValue, location: PostOrderId) {
 539         let value = match self.tracked_value_map.get(&value) {
 540             Some(value) => *value,
 541             // If there's no value, this is never consumed and therefore is never dropped. We can
 542             // ignore this.
 543             None => return,
 544         };
 545         self.node_mut(location).reinits.push(value);
 546     }
 547
 548     /// Looks up PostOrderId for any control edges added by HirId and adds a proper edge for them.
 549     ///
 550     /// Should be called after visiting the HIR but before solving the control flow, otherwise some
 551     /// edges will be missed.
 552     fn process_deferred_edges(&mut self) {
 553         trace!("processing deferred edges. post_order_map={:#?}", self.post_order_map);
 554         let mut edges = vec![];
 555         swap(&mut edges, &mut self.deferred_edges);
 556         edges.into_iter().for_each(|(from, to)| {
 557             trace!("Adding deferred edge from {:?} to {:?}", from, to);
 558             let to = *self.post_order_map.get(&to).expect("Expression ID not found");
 559             trace!("target edge PostOrderId={:?}", to);
 560             self.add_control_edge(from, to)
 561         });
 562     }
 563 }