From 8fa24bbc5729f356ea372b196f019b7568e17158 Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Sun, 1 Jul 2018 10:22:36 -0400 Subject: [PATCH] generate reborrow constraints at type check time --- .../borrow_check/nll/constraint_generation.rs | 138 +--------------- src/librustc_mir/borrow_check/nll/mod.rs | 1 + .../borrow_check/nll/region_infer/mod.rs | 11 -- .../borrow_check/nll/type_check/mod.rs | 156 +++++++++++++++++- 4 files changed, 154 insertions(+), 152 deletions(-) diff --git a/src/librustc_mir/borrow_check/nll/constraint_generation.rs b/src/librustc_mir/borrow_check/nll/constraint_generation.rs index 25a0123755f..9dcdf7de314 100644 --- a/src/librustc_mir/borrow_check/nll/constraint_generation.rs +++ b/src/librustc_mir/borrow_check/nll/constraint_generation.rs @@ -13,14 +13,11 @@ use borrow_check::nll::ToRegionVid; use borrow_check::nll::facts::AllFacts; use borrow_check::nll::region_infer::RegionInferenceContext; -use borrow_check::nll::type_check::AtLocation; -use rustc::hir; use rustc::infer::InferCtxt; use rustc::mir::visit::TyContext; use rustc::mir::visit::Visitor; -use rustc::mir::Place::Projection; use rustc::mir::{BasicBlock, BasicBlockData, Location, Mir, Place, Rvalue}; -use rustc::mir::{Local, PlaceProjection, ProjectionElem, Statement, Terminator}; +use rustc::mir::{Local, Statement, Terminator}; use rustc::ty::fold::TypeFoldable; use rustc::ty::subst::Substs; use rustc::ty::{self, CanonicalTy, ClosureSubsts, GeneratorSubsts}; @@ -41,7 +38,6 @@ pub(super) fn generate_constraints<'cx, 'gcx, 'tcx>( regioncx, location_table, all_facts, - mir, }; cg.add_region_liveness_constraints_from_type_check(liveness_set_from_typeck); @@ -57,7 +53,6 @@ struct ConstraintGeneration<'cg, 'cx: 'cg, 'gcx: 'tcx, 'tcx: 'cx> { all_facts: &'cg mut Option, location_table: &'cg LocationTable, regioncx: &'cg mut RegionInferenceContext<'tcx>, - mir: &'cg Mir<'tcx>, borrow_set: &'cg BorrowSet<'tcx>, } @@ -184,41 +179,6 @@ fn visit_terminator( self.super_terminator(block, terminator, location); } - fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) { - debug!("visit_rvalue(rvalue={:?}, location={:?})", rvalue, location); - - match rvalue { - Rvalue::Ref(region, _borrow_kind, borrowed_place) => { - // In some cases, e.g. when borrowing from an unsafe - // place, we don't bother to create a loan, since - // there are no conditions to validate. - if let Some(all_facts) = self.all_facts { - if let Some(borrow_index) = self.borrow_set.location_map.get(&location) { - let region_vid = region.to_region_vid(); - all_facts.borrow_region.push(( - region_vid, - *borrow_index, - self.location_table.mid_index(location), - )); - } - } - - // Look for an rvalue like: - // - // & L - // - // where L is the path that is borrowed. In that case, we have - // to add the reborrow constraints (which don't fall out - // naturally from the type-checker). - self.add_reborrow_constraint(location, region, borrowed_place); - } - - _ => {} - } - - self.super_rvalue(rvalue, location); - } - fn visit_user_assert_ty( &mut self, _c_ty: &CanonicalTy<'tcx>, @@ -285,100 +245,4 @@ fn add_regular_live_constraint(&mut self, live_ty: T, location: Location) self.regioncx.add_live_point(vid, location); }); } - - // Add the reborrow constraint at `location` so that `borrowed_place` - // is valid for `borrow_region`. - fn add_reborrow_constraint( - &mut self, - location: Location, - borrow_region: ty::Region<'tcx>, - borrowed_place: &Place<'tcx>, - ) { - let mut borrowed_place = borrowed_place; - - debug!( - "add_reborrow_constraint({:?}, {:?}, {:?})", - location, borrow_region, borrowed_place - ); - while let Projection(box PlaceProjection { base, elem }) = borrowed_place { - debug!("add_reborrow_constraint - iteration {:?}", borrowed_place); - - match *elem { - ProjectionElem::Deref => { - let tcx = self.infcx.tcx; - let base_ty = base.ty(self.mir, tcx).to_ty(tcx); - - debug!("add_reborrow_constraint - base_ty = {:?}", base_ty); - match base_ty.sty { - ty::TyRef(ref_region, _, mutbl) => { - self.regioncx.add_outlives( - location.boring(), - ref_region.to_region_vid(), - borrow_region.to_region_vid(), - ); - - if let Some(all_facts) = self.all_facts { - all_facts.outlives.push(( - ref_region.to_region_vid(), - borrow_region.to_region_vid(), - self.location_table.mid_index(location), - )); - } - - match mutbl { - hir::Mutability::MutImmutable => { - // Immutable reference. We don't need the base - // to be valid for the entire lifetime of - // the borrow. - break; - } - hir::Mutability::MutMutable => { - // Mutable reference. We *do* need the base - // to be valid, because after the base becomes - // invalid, someone else can use our mutable deref. - - // This is in order to make the following function - // illegal: - // ``` - // fn unsafe_deref<'a, 'b>(x: &'a &'b mut T) -> &'b mut T { - // &mut *x - // } - // ``` - // - // As otherwise you could clone `&mut T` using the - // following function: - // ``` - // fn bad(x: &mut T) -> (&mut T, &mut T) { - // let my_clone = unsafe_deref(&'a x); - // ENDREGION 'a; - // (my_clone, x) - // } - // ``` - } - } - } - ty::TyRawPtr(..) => { - // deref of raw pointer, guaranteed to be valid - break; - } - ty::TyAdt(def, _) if def.is_box() => { - // deref of `Box`, need the base to be valid - propagate - } - _ => bug!("unexpected deref ty {:?} in {:?}", base_ty, borrowed_place), - } - } - ProjectionElem::Field(..) - | ProjectionElem::Downcast(..) - | ProjectionElem::Index(..) - | ProjectionElem::ConstantIndex { .. } - | ProjectionElem::Subslice { .. } => { - // other field access - } - } - - // The "propagate" case. We need to check that our base is valid - // for the borrow's lifetime. - borrowed_place = base; - } - } } diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs index 16506800c9e..1891cac268c 100644 --- a/src/librustc_mir/borrow_check/nll/mod.rs +++ b/src/librustc_mir/borrow_check/nll/mod.rs @@ -108,6 +108,7 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>( def_id, &universal_regions, location_table, + borrow_set, &liveness, &mut all_facts, flow_inits, diff --git a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs index 164941203e0..8cae1fd2a4f 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs @@ -333,17 +333,6 @@ pub(super) fn add_live_point(&mut self, v: RegionVid, point: Location) -> bool { self.liveness_constraints.add_element(v, element) } - /// Indicates that the region variable `sup` must outlive `sub` is live at the point `point`. - pub(super) fn add_outlives(&mut self, locations: Locations, sup: RegionVid, sub: RegionVid) { - assert!(self.inferred_values.is_none(), "values already inferred"); - self.constraints.push(OutlivesConstraint { - locations, - sup, - sub, - next: None, - }) - } - /// Perform region inference and report errors if we see any /// unsatisfiable constraints. If this is a closure, returns the /// region requirements to propagate to our creator, if any. diff --git a/src/librustc_mir/borrow_check/nll/type_check/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/mod.rs index 2b47d50b4c2..0203349ffab 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs @@ -11,14 +11,17 @@ //! This pass type-checks the MIR to ensure it is not broken. #![allow(unreachable_code)] +use borrow_check::borrow_set::BorrowSet; use borrow_check::location::LocationTable; -use borrow_check::nll::constraint_set::ConstraintSet; +use borrow_check::nll::constraint_set::{ConstraintSet, OutlivesConstraint}; use borrow_check::nll::facts::AllFacts; use borrow_check::nll::region_infer::{ClosureRegionRequirementsExt, TypeTest}; use borrow_check::nll::universal_regions::UniversalRegions; +use borrow_check::nll::ToRegionVid; use dataflow::move_paths::MoveData; use dataflow::FlowAtLocation; use dataflow::MaybeInitializedPlaces; +use rustc::hir; use rustc::hir::def_id::DefId; use rustc::infer::canonical::QueryRegionConstraint; use rustc::infer::region_constraints::GenericKind; @@ -103,6 +106,7 @@ pub(crate) fn type_check<'gcx, 'tcx>( mir_def_id: DefId, universal_regions: &UniversalRegions<'tcx>, location_table: &LocationTable, + borrow_set: &BorrowSet<'tcx>, liveness: &LivenessResults, all_facts: &mut Option, flow_inits: &mut FlowAtLocation>, @@ -119,6 +123,7 @@ pub(crate) fn type_check<'gcx, 'tcx>( Some(BorrowCheckContext { universal_regions, location_table, + borrow_set, all_facts, }), &mut |cx| { @@ -141,6 +146,7 @@ fn type_check_internal<'gcx, 'tcx>( ) -> MirTypeckRegionConstraints<'tcx> { let mut checker = TypeChecker::new( infcx, + mir, mir_def_id, param_env, region_bound_pairs, @@ -592,6 +598,7 @@ struct TypeChecker<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> { infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, param_env: ty::ParamEnv<'gcx>, last_span: Span, + mir: &'a Mir<'tcx>, mir_def_id: DefId, region_bound_pairs: &'a [(ty::Region<'tcx>, GenericKind<'tcx>)], implicit_region_bound: Option>, @@ -604,6 +611,7 @@ struct BorrowCheckContext<'a, 'tcx: 'a> { universal_regions: &'a UniversalRegions<'tcx>, location_table: &'a LocationTable, all_facts: &'a mut Option, + borrow_set: &'a BorrowSet<'tcx>, } /// A collection of region constraints that must be satisfied for the @@ -704,6 +712,7 @@ pub fn span(&self, mir: &Mir<'_>) -> Span { impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { fn new( infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, + mir: &'a Mir<'tcx>, mir_def_id: DefId, param_env: ty::ParamEnv<'gcx>, region_bound_pairs: &'a [(ty::Region<'tcx>, GenericKind<'tcx>)], @@ -713,6 +722,7 @@ fn new( TypeChecker { infcx, last_span: DUMMY_SP, + mir, mir_def_id, param_env, region_bound_pairs, @@ -857,8 +867,7 @@ fn check_stmt(&mut self, mir: &Mir<'tcx>, stmt: &Statement<'tcx>, location: Loca } StatementKind::UserAssertTy(ref c_ty, ref local) => { let local_ty = mir.local_decls()[*local].ty; - let (ty, _) = self - .infcx + let (ty, _) = self.infcx .instantiate_canonical_with_fresh_inference_vars(stmt.source_info.span, c_ty); debug!( "check_stmt: user_assert_ty ty={:?} local_ty={:?}", @@ -1400,9 +1409,12 @@ fn check_rvalue(&mut self, mir: &Mir<'tcx>, rvalue: &Rvalue<'tcx>, location: Loc CastKind::Misc => {} }, + Rvalue::Ref(region, _borrow_kind, borrowed_place) => { + self.add_reborrow_constraint(location, region, borrowed_place); + } + // FIXME: These other cases have to be implemented in future PRs Rvalue::Use(..) - | Rvalue::Ref(..) | Rvalue::Len(..) | Rvalue::BinaryOp(..) | Rvalue::CheckedBinaryOp(..) @@ -1457,6 +1469,142 @@ fn check_aggregate_rvalue( } } + /// Add the constraints that arise from a borrow expression `&'a P` at the location `L`. + /// + /// # Parameters + /// + /// - `location`: the location `L` where the borrow expression occurs + /// - `borrow_region`: the region `'a` associated with the borrow + /// - `borrowed_place`: the place `P` being borrowed + fn add_reborrow_constraint( + &mut self, + location: Location, + borrow_region: ty::Region<'tcx>, + borrowed_place: &Place<'tcx>, + ) { + // These constraints are only meaningful during borrowck: + let BorrowCheckContext { + borrow_set, + location_table, + all_facts, + .. + } = match &mut self.borrowck_context { + Some(borrowck_context) => borrowck_context, + None => return, + }; + + // In Polonius mode, we also push a `borrow_region` fact + // linking the loan to the region (in some cases, though, + // there is no loan associated with this borrow expression -- + // that occurs when we are borrowing an unsafe place, for + // example). + if let Some(all_facts) = all_facts { + if let Some(borrow_index) = borrow_set.location_map.get(&location) { + let region_vid = borrow_region.to_region_vid(); + all_facts.borrow_region.push(( + region_vid, + *borrow_index, + location_table.mid_index(location), + )); + } + } + + // If we are reborrowing the referent of another reference, we + // need to add outlives relationships. In a case like `&mut + // *p`, where the `p` has type `&'b mut Foo`, for example, we + // need to ensure that `'b: 'a`. + + let mut borrowed_place = borrowed_place; + + debug!( + "add_reborrow_constraint({:?}, {:?}, {:?})", + location, borrow_region, borrowed_place + ); + while let Place::Projection(box PlaceProjection { base, elem }) = borrowed_place { + debug!("add_reborrow_constraint - iteration {:?}", borrowed_place); + + match *elem { + ProjectionElem::Deref => { + let tcx = self.infcx.tcx; + let base_ty = base.ty(self.mir, tcx).to_ty(tcx); + + debug!("add_reborrow_constraint - base_ty = {:?}", base_ty); + match base_ty.sty { + ty::TyRef(ref_region, _, mutbl) => { + self.constraints + .outlives_constraints + .push(OutlivesConstraint { + sup: ref_region.to_region_vid(), + sub: borrow_region.to_region_vid(), + locations: location.boring(), + next: None, + }); + + if let Some(all_facts) = all_facts { + all_facts.outlives.push(( + ref_region.to_region_vid(), + borrow_region.to_region_vid(), + location_table.mid_index(location), + )); + } + + match mutbl { + hir::Mutability::MutImmutable => { + // Immutable reference. We don't need the base + // to be valid for the entire lifetime of + // the borrow. + break; + } + hir::Mutability::MutMutable => { + // Mutable reference. We *do* need the base + // to be valid, because after the base becomes + // invalid, someone else can use our mutable deref. + + // This is in order to make the following function + // illegal: + // ``` + // fn unsafe_deref<'a, 'b>(x: &'a &'b mut T) -> &'b mut T { + // &mut *x + // } + // ``` + // + // As otherwise you could clone `&mut T` using the + // following function: + // ``` + // fn bad(x: &mut T) -> (&mut T, &mut T) { + // let my_clone = unsafe_deref(&'a x); + // ENDREGION 'a; + // (my_clone, x) + // } + // ``` + } + } + } + ty::TyRawPtr(..) => { + // deref of raw pointer, guaranteed to be valid + break; + } + ty::TyAdt(def, _) if def.is_box() => { + // deref of `Box`, need the base to be valid - propagate + } + _ => bug!("unexpected deref ty {:?} in {:?}", base_ty, borrowed_place), + } + } + ProjectionElem::Field(..) + | ProjectionElem::Downcast(..) + | ProjectionElem::Index(..) + | ProjectionElem::ConstantIndex { .. } + | ProjectionElem::Subslice { .. } => { + // other field access + } + } + + // The "propagate" case. We need to check that our base is valid + // for the borrow's lifetime. + borrowed_place = base; + } + } + fn prove_aggregate_predicates( &mut self, aggregate_kind: &AggregateKind<'tcx>, -- 2.44.0