1 use rustc_infer::infer::InferCtxt;
2 use rustc_middle::mir::visit::TyContext;
3 use rustc_middle::mir::visit::Visitor;
4 use rustc_middle::mir::{
5 BasicBlock, BasicBlockData, Body, Local, Location, Place, PlaceRef, ProjectionElem, Rvalue,
6 SourceInfo, Statement, StatementKind, Terminator, TerminatorKind, UserTypeProjection,
8 use rustc_middle::ty::fold::TypeFoldable;
9 use rustc_middle::ty::subst::SubstsRef;
10 use rustc_middle::ty::{self, RegionVid, Ty};
13 borrow_set::BorrowSet, facts::AllFacts, location::LocationTable, nll::ToRegionVid,
14 places_conflict, region_infer::values::LivenessValues,
17 pub(super) fn generate_constraints<'cx, 'tcx>(
18 infcx: &InferCtxt<'cx, 'tcx>,
19 liveness_constraints: &mut LivenessValues<RegionVid>,
20 all_facts: &mut Option<AllFacts>,
21 location_table: &LocationTable,
23 borrow_set: &BorrowSet<'tcx>,
25 let mut cg = ConstraintGeneration {
34 for (bb, data) in body.basic_blocks().iter_enumerated() {
35 cg.visit_basic_block_data(bb, data);
39 /// 'cg = the duration of the constraint generation process itself.
40 struct ConstraintGeneration<'cg, 'cx, 'tcx> {
41 infcx: &'cg InferCtxt<'cx, 'tcx>,
42 all_facts: &'cg mut Option<AllFacts>,
43 location_table: &'cg LocationTable,
44 liveness_constraints: &'cg mut LivenessValues<RegionVid>,
45 borrow_set: &'cg BorrowSet<'tcx>,
46 body: &'cg Body<'tcx>,
49 impl<'cg, 'cx, 'tcx> Visitor<'tcx> for ConstraintGeneration<'cg, 'cx, 'tcx> {
50 fn visit_basic_block_data(&mut self, bb: BasicBlock, data: &BasicBlockData<'tcx>) {
51 self.super_basic_block_data(bb, data);
54 /// We sometimes have `substs` within an rvalue, or within a
55 /// call. Make them live at the location where they appear.
56 fn visit_substs(&mut self, substs: &SubstsRef<'tcx>, location: Location) {
57 self.add_regular_live_constraint(*substs, location);
58 self.super_substs(substs);
61 /// We sometimes have `region` within an rvalue, or within a
62 /// call. Make them live at the location where they appear.
63 fn visit_region(&mut self, region: ty::Region<'tcx>, location: Location) {
64 self.add_regular_live_constraint(region, location);
65 self.super_region(region);
68 /// We sometimes have `ty` within an rvalue, or within a
69 /// call. Make them live at the location where they appear.
70 fn visit_ty(&mut self, ty: Ty<'tcx>, ty_context: TyContext) {
72 TyContext::ReturnTy(SourceInfo { span, .. })
73 | TyContext::YieldTy(SourceInfo { span, .. })
74 | TyContext::UserTy(span)
75 | TyContext::LocalDecl { source_info: SourceInfo { span, .. }, .. } => {
76 span_bug!(span, "should not be visiting outside of the CFG: {:?}", ty_context);
78 TyContext::Location(location) => {
79 self.add_regular_live_constraint(ty, location);
86 fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
87 if let Some(all_facts) = self.all_facts {
88 let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation");
89 all_facts.cfg_edge.push((
90 self.location_table.start_index(location),
91 self.location_table.mid_index(location),
94 all_facts.cfg_edge.push((
95 self.location_table.mid_index(location),
96 self.location_table.start_index(location.successor_within_block()),
99 // If there are borrows on this now dead local, we need to record them as `killed`.
100 if let StatementKind::StorageDead(local) = statement.kind {
101 record_killed_borrows_for_local(
111 self.super_statement(statement, location);
114 fn visit_assign(&mut self, place: &Place<'tcx>, rvalue: &Rvalue<'tcx>, location: Location) {
115 // When we see `X = ...`, then kill borrows of
116 // `(*X).foo` and so forth.
117 self.record_killed_borrows_for_place(*place, location);
119 self.super_assign(place, rvalue, location);
122 fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
123 if let Some(all_facts) = self.all_facts {
124 let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation");
125 all_facts.cfg_edge.push((
126 self.location_table.start_index(location),
127 self.location_table.mid_index(location),
130 let successor_blocks = terminator.successors();
131 all_facts.cfg_edge.reserve(successor_blocks.size_hint().0);
132 for successor_block in successor_blocks {
133 all_facts.cfg_edge.push((
134 self.location_table.mid_index(location),
135 self.location_table.start_index(successor_block.start_location()),
140 // A `Call` terminator's return value can be a local which has borrows,
141 // so we need to record those as `killed` as well.
142 if let TerminatorKind::Call { destination, .. } = terminator.kind {
143 self.record_killed_borrows_for_place(destination, location);
146 self.super_terminator(terminator, location);
149 fn visit_ascribe_user_ty(
151 _place: &Place<'tcx>,
152 _variance: ty::Variance,
153 _user_ty: &UserTypeProjection,
159 impl<'cx, 'cg, 'tcx> ConstraintGeneration<'cx, 'cg, 'tcx> {
160 /// Some variable with type `live_ty` is "regular live" at
161 /// `location` -- i.e., it may be used later. This means that all
162 /// regions appearing in the type `live_ty` must be live at
164 fn add_regular_live_constraint<T>(&mut self, live_ty: T, location: Location)
166 T: TypeFoldable<'tcx>,
168 debug!("add_regular_live_constraint(live_ty={:?}, location={:?})", live_ty, location);
170 self.infcx.tcx.for_each_free_region(&live_ty, |live_region| {
171 let vid = live_region.to_region_vid();
172 self.liveness_constraints.add_element(vid, location);
176 /// When recording facts for Polonius, records the borrows on the specified place
177 /// as `killed`. For example, when assigning to a local, or on a call's return destination.
178 fn record_killed_borrows_for_place(&mut self, place: Place<'tcx>, location: Location) {
179 if let Some(all_facts) = self.all_facts {
180 let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation");
182 // Depending on the `Place` we're killing:
183 // - if it's a local, or a single deref of a local,
184 // we kill all the borrows on the local.
185 // - if it's a deeper projection, we have to filter which
186 // of the borrows are killed: the ones whose `borrowed_place`
187 // conflicts with the `place`.
188 match place.as_ref() {
189 PlaceRef { local, projection: &[] }
190 | PlaceRef { local, projection: &[ProjectionElem::Deref] } => {
192 "Recording `killed` facts for borrows of local={:?} at location={:?}",
196 record_killed_borrows_for_local(
205 PlaceRef { local, projection: &[.., _] } => {
206 // Kill conflicting borrows of the innermost local.
208 "Recording `killed` facts for borrows of \
209 innermost projected local={:?} at location={:?}",
213 if let Some(borrow_indices) = self.borrow_set.local_map.get(&local) {
214 for &borrow_index in borrow_indices {
215 let places_conflict = places_conflict::places_conflict(
218 self.borrow_set[borrow_index].borrowed_place,
220 places_conflict::PlaceConflictBias::NoOverlap,
224 let location_index = self.location_table.mid_index(location);
225 all_facts.loan_killed_at.push((borrow_index, location_index));
235 /// When recording facts for Polonius, records the borrows on the specified local as `killed`.
236 fn record_killed_borrows_for_local(
237 all_facts: &mut AllFacts,
238 borrow_set: &BorrowSet<'_>,
239 location_table: &LocationTable,
243 if let Some(borrow_indices) = borrow_set.local_map.get(&local) {
244 all_facts.loan_killed_at.reserve(borrow_indices.len());
245 for &borrow_index in borrow_indices {
246 let location_index = location_table.mid_index(location);
247 all_facts.loan_killed_at.push((borrow_index, location_index));