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::build_control_flow_graph;
  16 use self::record_consumed_borrow::find_consumed_and_borrowed;
  17 use crate::check::FnCtxt;
  18 use hir::def_id::DefId;
  19 use hir::{Body, HirId, HirIdMap, Node};
  20 use rustc_data_structures::fx::FxHashMap;
  21 use rustc_data_structures::stable_set::FxHashSet;
  22 use rustc_hir as hir;
  23 use rustc_index::bit_set::BitSet;
  24 use rustc_index::vec::IndexVec;
  25 use rustc_middle::hir::map::Map;
  26 use rustc_middle::hir::place::{PlaceBase, PlaceWithHirId};
  27 use rustc_middle::ty;
  28 use std::collections::BTreeMap;
  29 use std::fmt::Debug;
  30
  31 mod cfg_build;
  32 mod cfg_propagate;
  33 mod cfg_visualize;
  34 mod record_consumed_borrow;
  35
  36 pub fn compute_drop_ranges<'a, 'tcx>(
  37     fcx: &'a FnCtxt<'a, 'tcx>,
  38     def_id: DefId,
  39     body: &'tcx Body<'tcx>,
  40 ) -> DropRanges {
  41     if fcx.sess().opts.unstable_opts.drop_tracking {
  42         let consumed_borrowed_places = find_consumed_and_borrowed(fcx, def_id, body);
  43
  44         let typeck_results = &fcx.typeck_results.borrow();
  45         let num_exprs = fcx.tcx.region_scope_tree(def_id).body_expr_count(body.id()).unwrap_or(0);
  46         let (mut drop_ranges, borrowed_temporaries) = build_control_flow_graph(
  47             fcx.tcx.hir(),
  48             fcx.tcx,
  49             typeck_results,
  50             consumed_borrowed_places,
  51             body,
  52             num_exprs,
  53         );
  54
  55         drop_ranges.propagate_to_fixpoint();
  56
  57         debug!("borrowed_temporaries = {borrowed_temporaries:?}");
  58         DropRanges {
  59             tracked_value_map: drop_ranges.tracked_value_map,
  60             nodes: drop_ranges.nodes,
  61             borrowed_temporaries: Some(borrowed_temporaries),
  62         }
  63     } else {
  64         // If drop range tracking is not enabled, skip all the analysis and produce an
  65         // empty set of DropRanges.
  66         DropRanges {
  67             tracked_value_map: FxHashMap::default(),
  68             nodes: IndexVec::new(),
  69             borrowed_temporaries: None,
  70         }
  71     }
  72 }
  73
  74 /// Applies `f` to consumable node in the HIR subtree pointed to by `place`.
  75 ///
  76 /// This includes the place itself, and if the place is a reference to a local
  77 /// variable then `f` is also called on the HIR node for that variable as well.
  78 ///
  79 /// For example, if `place` points to `foo()`, then `f` is called once for the
  80 /// result of `foo`. On the other hand, if `place` points to `x` then `f` will
  81 /// be called both on the `ExprKind::Path` node that represents the expression
  82 /// as well as the HirId of the local `x` itself.
  83 fn for_each_consumable<'tcx>(hir: Map<'tcx>, place: TrackedValue, mut f: impl FnMut(TrackedValue)) {
  84     f(place);
  85     let node = hir.find(place.hir_id());
  86     if let Some(Node::Expr(expr)) = node {
  87         match expr.kind {
  88             hir::ExprKind::Path(hir::QPath::Resolved(
  89                 _,
  90                 hir::Path { res: hir::def::Res::Local(hir_id), .. },
  91             )) => {
  92                 f(TrackedValue::Variable(*hir_id));
  93             }
  94             _ => (),
  95         }
  96     }
  97 }
  98
  99 rustc_index::newtype_index! {
 100     pub struct PostOrderId {
 101         DEBUG_FORMAT = "id({})",
 102     }
 103 }
 104
 105 rustc_index::newtype_index! {
 106     pub struct TrackedValueIndex {
 107         DEBUG_FORMAT = "hidx({})",
 108     }
 109 }
 110
 111 /// Identifies a value whose drop state we need to track.
 112 #[derive(PartialEq, Eq, Hash, Clone, Copy)]
 113 enum TrackedValue {
 114     /// Represents a named variable, such as a let binding, parameter, or upvar.
 115     ///
 116     /// The HirId points to the variable's definition site.
 117     Variable(HirId),
 118     /// A value produced as a result of an expression.
 119     ///
 120     /// The HirId points to the expression that returns this value.
 121     Temporary(HirId),
 122 }
 123
 124 impl Debug for TrackedValue {
 125     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 126         ty::tls::with_opt(|opt_tcx| {
 127             if let Some(tcx) = opt_tcx {
 128                 write!(f, "{}", tcx.hir().node_to_string(self.hir_id()))
 129             } else {
 130                 match self {
 131                     Self::Variable(hir_id) => write!(f, "Variable({:?})", hir_id),
 132                     Self::Temporary(hir_id) => write!(f, "Temporary({:?})", hir_id),
 133                 }
 134             }
 135         })
 136     }
 137 }
 138
 139 impl TrackedValue {
 140     fn hir_id(&self) -> HirId {
 141         match self {
 142             TrackedValue::Variable(hir_id) | TrackedValue::Temporary(hir_id) => *hir_id,
 143         }
 144     }
 145
 146     fn from_place_with_projections_allowed(place_with_id: &PlaceWithHirId<'_>) -> Self {
 147         match place_with_id.place.base {
 148             PlaceBase::Rvalue | PlaceBase::StaticItem => {
 149                 TrackedValue::Temporary(place_with_id.hir_id)
 150             }
 151             PlaceBase::Local(hir_id)
 152             | PlaceBase::Upvar(ty::UpvarId { var_path: ty::UpvarPath { hir_id }, .. }) => {
 153                 TrackedValue::Variable(hir_id)
 154             }
 155         }
 156     }
 157 }
 158
 159 /// Represents a reason why we might not be able to convert a HirId or Place
 160 /// into a tracked value.
 161 #[derive(Debug)]
 162 enum TrackedValueConversionError {
 163     /// Place projects are not currently supported.
 164     ///
 165     /// The reasoning around these is kind of subtle, so we choose to be more
 166     /// conservative around these for now. There is no reason in theory we
 167     /// cannot support these, we just have not implemented it yet.
 168     PlaceProjectionsNotSupported,
 169 }
 170
 171 impl TryFrom<&PlaceWithHirId<'_>> for TrackedValue {
 172     type Error = TrackedValueConversionError;
 173
 174     fn try_from(place_with_id: &PlaceWithHirId<'_>) -> Result<Self, Self::Error> {
 175         if !place_with_id.place.projections.is_empty() {
 176             debug!(
 177                 "TrackedValue from PlaceWithHirId: {:?} has projections, which are not supported.",
 178                 place_with_id
 179             );
 180             return Err(TrackedValueConversionError::PlaceProjectionsNotSupported);
 181         }
 182
 183         Ok(TrackedValue::from_place_with_projections_allowed(place_with_id))
 184     }
 185 }
 186
 187 pub struct DropRanges {
 188     tracked_value_map: FxHashMap<TrackedValue, TrackedValueIndex>,
 189     nodes: IndexVec<PostOrderId, NodeInfo>,
 190     borrowed_temporaries: Option<FxHashSet<HirId>>,
 191 }
 192
 193 impl DropRanges {
 194     pub fn is_dropped_at(&self, hir_id: HirId, location: usize) -> bool {
 195         self.tracked_value_map
 196             .get(&TrackedValue::Temporary(hir_id))
 197             .or(self.tracked_value_map.get(&TrackedValue::Variable(hir_id)))
 198             .cloned()
 199             .map_or(false, |tracked_value_id| {
 200                 self.expect_node(location.into()).drop_state.contains(tracked_value_id)
 201             })
 202     }
 203
 204     pub fn is_borrowed_temporary(&self, expr: &hir::Expr<'_>) -> bool {
 205         if let Some(b) = &self.borrowed_temporaries { b.contains(&expr.hir_id) } else { true }
 206     }
 207
 208     /// Returns a reference to the NodeInfo for a node, panicking if it does not exist
 209     fn expect_node(&self, id: PostOrderId) -> &NodeInfo {
 210         &self.nodes[id]
 211     }
 212 }
 213
 214 /// Tracks information needed to compute drop ranges.
 215 struct DropRangesBuilder {
 216     /// The core of DropRangesBuilder is a set of nodes, which each represent
 217     /// one expression. We primarily refer to them by their index in a
 218     /// post-order traversal of the HIR tree,  since this is what
 219     /// generator_interior uses to talk about yield positions.
 220     ///
 221     /// This IndexVec keeps the relevant details for each node. See the
 222     /// NodeInfo struct for more details, but this information includes things
 223     /// such as the set of control-flow successors, which variables are dropped
 224     /// or reinitialized, and whether each variable has been inferred to be
 225     /// known-dropped or potentially reinitialized at each point.
 226     nodes: IndexVec<PostOrderId, NodeInfo>,
 227     /// We refer to values whose drop state we are tracking by the HirId of
 228     /// where they are defined. Within a NodeInfo, however, we store the
 229     /// drop-state in a bit vector indexed by a HirIdIndex
 230     /// (see NodeInfo::drop_state). The hir_id_map field stores the mapping
 231     /// from HirIds to the HirIdIndex that is used to represent that value in
 232     /// bitvector.
 233     tracked_value_map: FxHashMap<TrackedValue, TrackedValueIndex>,
 234
 235     /// When building the control flow graph, we don't always know the
 236     /// post-order index of the target node at the point we encounter it.
 237     /// For example, this happens with break and continue. In those cases,
 238     /// we store a pair of the PostOrderId of the source and the HirId
 239     /// of the target. Once we have gathered all of these edges, we make a
 240     /// pass over the set of deferred edges (see process_deferred_edges in
 241     /// cfg_build.rs), look up the PostOrderId for the target (since now the
 242     /// post-order index for all nodes is known), and add missing control flow
 243     /// edges.
 244     deferred_edges: Vec<(PostOrderId, HirId)>,
 245     /// This maps HirIds of expressions to their post-order index. It is
 246     /// used in process_deferred_edges to correctly add back-edges.
 247     post_order_map: HirIdMap<PostOrderId>,
 248 }
 249
 250 impl Debug for DropRangesBuilder {
 251     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 252         f.debug_struct("DropRanges")
 253             .field("hir_id_map", &self.tracked_value_map)
 254             .field("post_order_maps", &self.post_order_map)
 255             .field("nodes", &self.nodes.iter_enumerated().collect::<BTreeMap<_, _>>())
 256             .finish()
 257     }
 258 }
 259
 260 /// DropRanges keeps track of what values are definitely dropped at each point in the code.
 261 ///
 262 /// Values of interest are defined by the hir_id of their place. Locations in code are identified
 263 /// by their index in the post-order traversal. At its core, DropRanges maps
 264 /// (hir_id, post_order_id) -> bool, where a true value indicates that the value is definitely
 265 /// dropped at the point of the node identified by post_order_id.
 266 impl DropRangesBuilder {
 267     /// Returns the number of values (hir_ids) that are tracked
 268     fn num_values(&self) -> usize {
 269         self.tracked_value_map.len()
 270     }
 271
 272     fn node_mut(&mut self, id: PostOrderId) -> &mut NodeInfo {
 273         let size = self.num_values();
 274         self.nodes.ensure_contains_elem(id, || NodeInfo::new(size));
 275         &mut self.nodes[id]
 276     }
 277
 278     fn add_control_edge(&mut self, from: PostOrderId, to: PostOrderId) {
 279         trace!("adding control edge from {:?} to {:?}", from, to);
 280         self.node_mut(from).successors.push(to);
 281     }
 282 }
 283
 284 #[derive(Debug)]
 285 struct NodeInfo {
 286     /// IDs of nodes that can follow this one in the control flow
 287     ///
 288     /// If the vec is empty, then control proceeds to the next node.
 289     successors: Vec<PostOrderId>,
 290
 291     /// List of hir_ids that are dropped by this node.
 292     drops: Vec<TrackedValueIndex>,
 293
 294     /// List of hir_ids that are reinitialized by this node.
 295     reinits: Vec<TrackedValueIndex>,
 296
 297     /// Set of values that are definitely dropped at this point.
 298     drop_state: BitSet<TrackedValueIndex>,
 299 }
 300
 301 impl NodeInfo {
 302     fn new(num_values: usize) -> Self {
 303         Self {
 304             successors: vec![],
 305             drops: vec![],
 306             reinits: vec![],
 307             drop_state: BitSet::new_filled(num_values),
 308         }
 309     }
 310 }