compiler/rustc_typeck/src/check/generator_interior/drop_ranges.rs

   1 //! Drop range analysis finds the portions of the tree where a value is guaranteed to be dropped
   2 //! (i.e. moved, uninitialized, etc.). This is used to exclude the types of those values from the
   3 //! generator type. See `InteriorVisitor::record` for where the results of this analysis are used.
   4 //!
   5 //! There are three phases to this analysis:
   6 //! 1. Use `ExprUseVisitor` to identify the interesting values that are consumed and borrowed.
   7 //! 2. Use `DropRangeVisitor` to find where the interesting values are dropped or reinitialized,
   8 //!    and also build a control flow graph.
   9 //! 3. Use `DropRanges::propagate_to_fixpoint` to flow the dropped/reinitialized information through
  10 //!    the CFG and find the exact points where we know a value is definitely dropped.
  11 //!
  12 //! The end result is a data structure that maps the post-order index of each node in the HIR tree
  13 //! to a set of values that are known to be dropped at that location.
  14
  15 use self::cfg_build::DropRangeVisitor;
  16 use self::record_consumed_borrow::ExprUseDelegate;
  17 use crate::check::FnCtxt;
  18 use hir::def_id::DefId;
  19 use hir::{Body, HirId, HirIdMap, Node, intravisit};
  20 use rustc_hir as hir;
  21 use rustc_index::bit_set::BitSet;
  22 use rustc_index::vec::IndexVec;
  23 use rustc_middle::hir::map::Map;
  24 use std::collections::BTreeMap;
  25 use std::fmt::Debug;
  26 use std::mem::swap;
  27
  28 mod cfg_build;
  29 mod record_consumed_borrow;
  30 mod cfg_propagate;
  31 mod cfg_visualize;
  32
  33 pub fn compute_drop_ranges<'a, 'tcx>(
  34     fcx: &'a FnCtxt<'a, 'tcx>,
  35     def_id: DefId,
  36     body: &'tcx Body<'tcx>,
  37 ) -> DropRanges {
  38     let mut expr_use_visitor = ExprUseDelegate::new(fcx.tcx.hir());
  39     expr_use_visitor.consume_body(fcx, def_id, body);
  40
  41     let mut drop_range_visitor = DropRangeVisitor::from_uses(
  42         expr_use_visitor,
  43         fcx.tcx.region_scope_tree(def_id).body_expr_count(body.id()).unwrap_or(0),
  44     );
  45     intravisit::walk_body(&mut drop_range_visitor, body);
  46
  47     let mut drop_ranges = drop_range_visitor.into_drop_ranges();
  48     drop_ranges.propagate_to_fixpoint();
  49
  50     drop_ranges
  51 }
  52
  53 /// Applies `f` to consumable portion of a HIR node.
  54 ///
  55 /// The `node` parameter should be the result of calling `Map::find(place)`.
  56 fn for_each_consumable(place: HirId, node: Option<Node<'_>>, mut f: impl FnMut(HirId)) {
  57     f(place);
  58     if let Some(Node::Expr(expr)) = node {
  59         match expr.kind {
  60             hir::ExprKind::Path(hir::QPath::Resolved(
  61                 _,
  62                 hir::Path { res: hir::def::Res::Local(hir_id), .. },
  63             )) => {
  64                 f(*hir_id);
  65             }
  66             _ => (),
  67         }
  68     }
  69 }
  70
  71 rustc_index::newtype_index! {
  72     pub struct PostOrderId {
  73         DEBUG_FORMAT = "id({})",
  74     }
  75 }
  76
  77 rustc_index::newtype_index! {
  78     pub struct HirIdIndex {
  79         DEBUG_FORMAT = "hidx({})",
  80     }
  81 }
  82
  83 pub struct DropRanges {
  84     hir_id_map: HirIdMap<HirIdIndex>,
  85     nodes: IndexVec<PostOrderId, NodeInfo>,
  86     deferred_edges: Vec<(usize, HirId)>,
  87     // FIXME: This should only be used for loops and break/continue.
  88     post_order_map: HirIdMap<usize>,
  89 }
  90
  91 impl Debug for DropRanges {
  92     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
  93         f.debug_struct("DropRanges")
  94             .field("hir_id_map", &self.hir_id_map)
  95             .field("post_order_maps", &self.post_order_map)
  96             .field("nodes", &self.nodes.iter_enumerated().collect::<BTreeMap<_, _>>())
  97             .finish()
  98     }
  99 }
 100
 101 /// DropRanges keeps track of what values are definitely dropped at each point in the code.
 102 ///
 103 /// Values of interest are defined by the hir_id of their place. Locations in code are identified
 104 /// by their index in the post-order traversal. At its core, DropRanges maps
 105 /// (hir_id, post_order_id) -> bool, where a true value indicates that the value is definitely
 106 /// dropped at the point of the node identified by post_order_id.
 107 impl DropRanges {
 108     pub fn new(hir_ids: impl Iterator<Item = HirId>, hir: &Map<'_>, num_exprs: usize) -> Self {
 109         let mut hir_id_map = HirIdMap::<HirIdIndex>::default();
 110         let mut next = <_>::from(0u32);
 111         for hir_id in hir_ids {
 112             for_each_consumable(hir_id, hir.find(hir_id), |hir_id| {
 113                 if !hir_id_map.contains_key(&hir_id) {
 114                     hir_id_map.insert(hir_id, next);
 115                     next = <_>::from(next.index() + 1);
 116                 }
 117             });
 118         }
 119         debug!("hir_id_map: {:?}", hir_id_map);
 120         let num_values = hir_id_map.len();
 121         Self {
 122             hir_id_map,
 123             nodes: IndexVec::from_fn_n(|_| NodeInfo::new(num_values), num_exprs + 1),
 124             deferred_edges: <_>::default(),
 125             post_order_map: <_>::default(),
 126         }
 127     }
 128
 129     fn hidx(&self, hir_id: HirId) -> HirIdIndex {
 130         *self.hir_id_map.get(&hir_id).unwrap()
 131     }
 132
 133     pub fn is_dropped_at(&mut self, hir_id: HirId, location: usize) -> bool {
 134         self.hir_id_map
 135             .get(&hir_id)
 136             .copied()
 137             .map_or(false, |hir_id| self.expect_node(location.into()).drop_state.contains(hir_id))
 138     }
 139
 140     /// Returns the number of values (hir_ids) that are tracked
 141     fn num_values(&self) -> usize {
 142         self.hir_id_map.len()
 143     }
 144
 145     /// Adds an entry in the mapping from HirIds to PostOrderIds
 146     ///
 147     /// Needed so that `add_control_edge_hir_id` can work.
 148     pub fn add_node_mapping(&mut self, hir_id: HirId, post_order_id: usize) {
 149         self.post_order_map.insert(hir_id, post_order_id);
 150     }
 151
 152     /// Returns a reference to the NodeInfo for a node, panicking if it does not exist
 153     fn expect_node(&self, id: PostOrderId) -> &NodeInfo {
 154         &self.nodes[id]
 155     }
 156
 157     fn node_mut(&mut self, id: PostOrderId) -> &mut NodeInfo {
 158         let size = self.num_values();
 159         self.nodes.ensure_contains_elem(id, || NodeInfo::new(size));
 160         &mut self.nodes[id]
 161     }
 162
 163     pub fn add_control_edge(&mut self, from: usize, to: usize) {
 164         trace!("adding control edge from {} to {}", from, to);
 165         self.node_mut(from.into()).successors.push(to.into());
 166     }
 167
 168     /// Like add_control_edge, but uses a hir_id as the target.
 169     ///
 170     /// This can be used for branches where we do not know the PostOrderId of the target yet,
 171     /// such as when handling `break` or `continue`.
 172     pub fn add_control_edge_hir_id(&mut self, from: usize, to: HirId) {
 173         self.deferred_edges.push((from, to));
 174     }
 175
 176     /// Looks up PostOrderId for any control edges added by HirId and adds a proper edge for them.
 177     ///
 178     /// Should be called after visiting the HIR but before solving the control flow, otherwise some
 179     /// edges will be missed.
 180     fn process_deferred_edges(&mut self) {
 181         let mut edges = vec![];
 182         swap(&mut edges, &mut self.deferred_edges);
 183         edges.into_iter().for_each(|(from, to)| {
 184             let to = *self.post_order_map.get(&to).expect("Expression ID not found");
 185             trace!("Adding deferred edge from {} to {}", from, to);
 186             self.add_control_edge(from, to)
 187         });
 188     }
 189
 190     pub fn drop_at(&mut self, value: HirId, location: usize) {
 191         let value = self.hidx(value);
 192         self.node_mut(location.into()).drops.push(value);
 193     }
 194
 195     pub fn reinit_at(&mut self, value: HirId, location: usize) {
 196         let value = match self.hir_id_map.get(&value) {
 197             Some(value) => *value,
 198             // If there's no value, this is never consumed and therefore is never dropped. We can
 199             // ignore this.
 200             None => return,
 201         };
 202         self.node_mut(location.into()).reinits.push(value);
 203     }
 204
 205 }
 206
 207 #[derive(Debug)]
 208 struct NodeInfo {
 209     /// IDs of nodes that can follow this one in the control flow
 210     ///
 211     /// If the vec is empty, then control proceeds to the next node.
 212     successors: Vec<PostOrderId>,
 213
 214     /// List of hir_ids that are dropped by this node.
 215     drops: Vec<HirIdIndex>,
 216
 217     /// List of hir_ids that are reinitialized by this node.
 218     reinits: Vec<HirIdIndex>,
 219
 220     /// Set of values that are definitely dropped at this point.
 221     drop_state: BitSet<HirIdIndex>,
 222 }
 223
 224 impl NodeInfo {
 225     fn new(num_values: usize) -> Self {
 226         Self {
 227             successors: vec![],
 228             drops: vec![],
 229             reinits: vec![],
 230             drop_state: BitSet::new_filled(num_values),
 231         }
 232     }
 233 }