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}
;
12 use crate::borrow_check
::{
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 if let Some((place
, _
)) = destination
{
144 self.record_killed_borrows_for_place(place
, location
);
148 self.super_terminator(terminator
, location
);
151 fn visit_ascribe_user_ty(
153 _place
: &Place
<'tcx
>,
154 _variance
: &ty
::Variance
,
155 _user_ty
: &UserTypeProjection
,
161 impl<'cx
, 'cg
, 'tcx
> ConstraintGeneration
<'cx
, 'cg
, 'tcx
> {
162 /// Some variable with type `live_ty` is "regular live" at
163 /// `location` -- i.e., it may be used later. This means that all
164 /// regions appearing in the type `live_ty` must be live at
166 fn add_regular_live_constraint
<T
>(&mut self, live_ty
: T
, location
: Location
)
168 T
: TypeFoldable
<'tcx
>,
170 debug
!("add_regular_live_constraint(live_ty={:?}, location={:?})", live_ty
, location
);
172 self.infcx
.tcx
.for_each_free_region(&live_ty
, |live_region
| {
173 let vid
= live_region
.to_region_vid();
174 self.liveness_constraints
.add_element(vid
, location
);
178 /// When recording facts for Polonius, records the borrows on the specified place
179 /// as `killed`. For example, when assigning to a local, or on a call's return destination.
180 fn record_killed_borrows_for_place(&mut self, place
: Place
<'tcx
>, location
: Location
) {
181 if let Some(all_facts
) = self.all_facts
{
182 let _prof_timer
= self.infcx
.tcx
.prof
.generic_activity("polonius_fact_generation");
184 // Depending on the `Place` we're killing:
185 // - if it's a local, or a single deref of a local,
186 // we kill all the borrows on the local.
187 // - if it's a deeper projection, we have to filter which
188 // of the borrows are killed: the ones whose `borrowed_place`
189 // conflicts with the `place`.
190 match place
.as_ref() {
191 PlaceRef { local, projection: &[] }
192 | PlaceRef { local, projection: &[ProjectionElem::Deref] }
=> {
194 "Recording `killed` facts for borrows of local={:?} at location={:?}",
198 record_killed_borrows_for_local(
207 PlaceRef { local, projection: &[.., _] }
=> {
208 // Kill conflicting borrows of the innermost local.
210 "Recording `killed` facts for borrows of \
211 innermost projected local={:?} at location={:?}",
215 if let Some(borrow_indices
) = self.borrow_set
.local_map
.get(&local
) {
216 for &borrow_index
in borrow_indices
{
217 let places_conflict
= places_conflict
::places_conflict(
220 self.borrow_set
.borrows
[borrow_index
].borrowed_place
,
222 places_conflict
::PlaceConflictBias
::NoOverlap
,
226 let location_index
= self.location_table
.mid_index(location
);
227 all_facts
.killed
.push((borrow_index
, location_index
));
237 /// When recording facts for Polonius, records the borrows on the specified local as `killed`.
238 fn record_killed_borrows_for_local(
239 all_facts
: &mut AllFacts
,
240 borrow_set
: &BorrowSet
<'_
>,
241 location_table
: &LocationTable
,
245 if let Some(borrow_indices
) = borrow_set
.local_map
.get(&local
) {
246 all_facts
.killed
.reserve(borrow_indices
.len());
247 for &borrow_index
in borrow_indices
{
248 let location_index
= location_table
.mid_index(location
);
249 all_facts
.killed
.push((borrow_index
, location_index
));