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.
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.
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.
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;
22 use rustc_index::bit_set::BitSet;
23 use rustc_index::vec::IndexVec;
24 use rustc_middle::hir::map::Map;
25 use rustc_middle::hir::place::{PlaceBase, PlaceWithHirId};
27 use std::collections::BTreeMap;
33 mod record_consumed_borrow;
35 pub fn compute_drop_ranges<'a, 'tcx>(
36 fcx: &'a FnCtxt<'a, 'tcx>,
38 body: &'tcx Body<'tcx>,
40 if super::ENABLE_DROP_TRACKING {
41 let consumed_borrowed_places = find_consumed_and_borrowed(fcx, def_id, body);
43 let num_exprs = fcx.tcx.region_scope_tree(def_id).body_expr_count(body.id()).unwrap_or(0);
44 let mut drop_ranges = build_control_flow_graph(
47 &fcx.typeck_results.borrow(),
48 consumed_borrowed_places,
53 drop_ranges.propagate_to_fixpoint();
55 DropRanges { tracked_value_map: drop_ranges.tracked_value_map, nodes: drop_ranges.nodes }
57 // If drop range tracking is not enabled, skip all the analysis and produce an
58 // empty set of DropRanges.
59 DropRanges { tracked_value_map: FxHashMap::default(), nodes: IndexVec::new() }
63 /// Applies `f` to consumable node in the HIR subtree pointed to by `place`.
65 /// This includes the place itself, and if the place is a reference to a local
66 /// variable then `f` is also called on the HIR node for that variable as well.
68 /// For example, if `place` points to `foo()`, then `f` is called once for the
69 /// result of `foo`. On the other hand, if `place` points to `x` then `f` will
70 /// be called both on the `ExprKind::Path` node that represents the expression
71 /// as well as the HirId of the local `x` itself.
72 fn for_each_consumable<'tcx>(hir: Map<'tcx>, place: TrackedValue, mut f: impl FnMut(TrackedValue)) {
74 let node = hir.find(place.hir_id());
75 if let Some(Node::Expr(expr)) = node {
77 hir::ExprKind::Path(hir::QPath::Resolved(
79 hir::Path { res: hir::def::Res::Local(hir_id), .. },
81 f(TrackedValue::Variable(*hir_id));
88 rustc_index::newtype_index! {
89 pub struct PostOrderId {
90 DEBUG_FORMAT = "id({})",
94 rustc_index::newtype_index! {
95 pub struct TrackedValueIndex {
96 DEBUG_FORMAT = "hidx({})",
100 /// Identifies a value whose drop state we need to track.
101 #[derive(PartialEq, Eq, Hash, Debug, Clone, Copy)]
103 /// Represents a named variable, such as a let binding, parameter, or upvar.
105 /// The HirId points to the variable's definition site.
107 /// A value produced as a result of an expression.
109 /// The HirId points to the expression that returns this value.
114 fn hir_id(&self) -> HirId {
116 TrackedValue::Variable(hir_id) | TrackedValue::Temporary(hir_id) => *hir_id,
121 /// Represents a reason why we might not be able to convert a HirId or Place
122 /// into a tracked value.
124 enum TrackedValueConversionError {
125 /// Place projects are not currently supported.
127 /// The reasoning around these is kind of subtle, so we choose to be more
128 /// conservative around these for now. There is not reason in theory we
129 /// cannot support these, we just have not implemented it yet.
130 PlaceProjectionsNotSupported,
133 impl TryFrom<&PlaceWithHirId<'_>> for TrackedValue {
134 type Error = TrackedValueConversionError;
136 fn try_from(place_with_id: &PlaceWithHirId<'_>) -> Result<Self, Self::Error> {
137 if !place_with_id.place.projections.is_empty() {
139 "TrackedValue from PlaceWithHirId: {:?} has projections, which are not supported.",
142 return Err(TrackedValueConversionError::PlaceProjectionsNotSupported);
145 match place_with_id.place.base {
146 PlaceBase::Rvalue | PlaceBase::StaticItem => {
147 Ok(TrackedValue::Temporary(place_with_id.hir_id))
149 PlaceBase::Local(hir_id)
150 | PlaceBase::Upvar(ty::UpvarId { var_path: ty::UpvarPath { hir_id }, .. }) => {
151 Ok(TrackedValue::Variable(hir_id))
157 pub struct DropRanges {
158 tracked_value_map: FxHashMap<TrackedValue, TrackedValueIndex>,
159 nodes: IndexVec<PostOrderId, NodeInfo>,
163 pub fn is_dropped_at(&self, hir_id: HirId, location: usize) -> bool {
164 self.tracked_value_map
165 .get(&TrackedValue::Temporary(hir_id))
166 .or(self.tracked_value_map.get(&TrackedValue::Variable(hir_id)))
168 .map_or(false, |tracked_value_id| {
169 self.expect_node(location.into()).drop_state.contains(tracked_value_id)
173 /// Returns a reference to the NodeInfo for a node, panicking if it does not exist
174 fn expect_node(&self, id: PostOrderId) -> &NodeInfo {
179 /// Tracks information needed to compute drop ranges.
180 struct DropRangesBuilder {
181 /// The core of DropRangesBuilder is a set of nodes, which each represent
182 /// one expression. We primarily refer to them by their index in a
183 /// post-order traversal of the HIR tree, since this is what
184 /// generator_interior uses to talk about yield positions.
186 /// This IndexVec keeps the relevant details for each node. See the
187 /// NodeInfo struct for more details, but this information includes things
188 /// such as the set of control-flow successors, which variables are dropped
189 /// or reinitialized, and whether each variable has been inferred to be
190 /// known-dropped or potentially reintiialized at each point.
191 nodes: IndexVec<PostOrderId, NodeInfo>,
192 /// We refer to values whose drop state we are tracking by the HirId of
193 /// where they are defined. Within a NodeInfo, however, we store the
194 /// drop-state in a bit vector indexed by a HirIdIndex
195 /// (see NodeInfo::drop_state). The hir_id_map field stores the mapping
196 /// from HirIds to the HirIdIndex that is used to represent that value in
198 tracked_value_map: FxHashMap<TrackedValue, TrackedValueIndex>,
200 /// When building the control flow graph, we don't always know the
201 /// post-order index of the target node at the point we encounter it.
202 /// For example, this happens with break and continue. In those cases,
203 /// we store a pair of the PostOrderId of the source and the HirId
204 /// of the target. Once we have gathered all of these edges, we make a
205 /// pass over the set of deferred edges (see process_deferred_edges in
206 /// cfg_build.rs), look up the PostOrderId for the target (since now the
207 /// post-order index for all nodes is known), and add missing control flow
209 deferred_edges: Vec<(PostOrderId, HirId)>,
210 /// This maps HirIds of expressions to their post-order index. It is
211 /// used in process_deferred_edges to correctly add back-edges.
212 post_order_map: HirIdMap<PostOrderId>,
215 impl Debug for DropRangesBuilder {
216 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
217 f.debug_struct("DropRanges")
218 .field("hir_id_map", &self.tracked_value_map)
219 .field("post_order_maps", &self.post_order_map)
220 .field("nodes", &self.nodes.iter_enumerated().collect::<BTreeMap<_, _>>())
225 /// DropRanges keeps track of what values are definitely dropped at each point in the code.
227 /// Values of interest are defined by the hir_id of their place. Locations in code are identified
228 /// by their index in the post-order traversal. At its core, DropRanges maps
229 /// (hir_id, post_order_id) -> bool, where a true value indicates that the value is definitely
230 /// dropped at the point of the node identified by post_order_id.
231 impl DropRangesBuilder {
232 /// Returns the number of values (hir_ids) that are tracked
233 fn num_values(&self) -> usize {
234 self.tracked_value_map.len()
237 fn node_mut(&mut self, id: PostOrderId) -> &mut NodeInfo {
238 let size = self.num_values();
239 self.nodes.ensure_contains_elem(id, || NodeInfo::new(size));
243 fn add_control_edge(&mut self, from: PostOrderId, to: PostOrderId) {
244 trace!("adding control edge from {:?} to {:?}", from, to);
245 self.node_mut(from.into()).successors.push(to.into());
251 /// IDs of nodes that can follow this one in the control flow
253 /// If the vec is empty, then control proceeds to the next node.
254 successors: Vec<PostOrderId>,
256 /// List of hir_ids that are dropped by this node.
257 drops: Vec<TrackedValueIndex>,
259 /// List of hir_ids that are reinitialized by this node.
260 reinits: Vec<TrackedValueIndex>,
262 /// Set of values that are definitely dropped at this point.
263 drop_state: BitSet<TrackedValueIndex>,
267 fn new(num_values: usize) -> Self {
272 drop_state: BitSet::new_filled(num_values),