diff options
| -rw-r--r-- | src/librustc_mir/borrow_check/nll/region_infer/dfs.rs | 48 | ||||
| -rw-r--r-- | src/librustc_mir/borrow_check/nll/region_infer/mod.rs | 220 | ||||
| -rw-r--r-- | src/librustc_mir/borrow_check/nll/subtype_constraint_generation.rs | 68 | ||||
| -rw-r--r-- | src/test/ui/nll/ty-outlives/ty-param-fn.rs | 51 | ||||
| -rw-r--r-- | src/test/ui/nll/ty-outlives/ty-param-fn.stderr | 26 |
5 files changed, 389 insertions, 24 deletions
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/dfs.rs b/src/librustc_mir/borrow_check/nll/region_infer/dfs.rs index c8ac0fa233f..dcf5d979a4c 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/dfs.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/dfs.rs @@ -11,11 +11,12 @@ //! Module defining the `dfs` method on `RegionInferenceContext`, along with //! its associated helper traits. +use borrow_check::nll::universal_regions::UniversalRegions; +use borrow_check::nll::region_infer::RegionInferenceContext; +use borrow_check::nll::region_infer::values::{RegionElementIndex, RegionValues, RegionValueElements}; use rustc::mir::{Location, Mir}; use rustc::ty::RegionVid; use rustc_data_structures::fx::FxHashSet; -use super::RegionInferenceContext; -use super::values::{RegionElementIndex, RegionValues, RegionValueElements}; impl<'tcx> RegionInferenceContext<'tcx> { /// Function used to satisfy or test a `R1: R2 @ P` @@ -165,17 +166,16 @@ impl<'v> DfsOp for CopyFromSourceToTarget<'v> { /// condition. Similarly, if we reach the end of the graph and find /// that R1 contains some universal region that R2 does not contain, /// we abort the walk early. -#[allow(dead_code)] // TODO -pub(super) struct TestTarget<'v> { - source_region: RegionVid, - target_region: RegionVid, - elements: &'v RegionValueElements, - inferred_values: &'v RegionValues, - constraint_point: Location, +pub(super) struct TestTargetOutlivesSource<'v, 'tcx: 'v> { + pub source_region: RegionVid, + pub target_region: RegionVid, + pub elements: &'v RegionValueElements, + pub universal_regions: &'v UniversalRegions<'tcx>, + pub inferred_values: &'v RegionValues, + pub constraint_point: Location, } -#[allow(dead_code)] // TODO -impl<'v> DfsOp for TestTarget<'v> { +impl<'v, 'tcx> DfsOp for TestTargetOutlivesSource<'v, 'tcx> { /// The element that was not found within R2. type Early = RegionElementIndex; @@ -204,12 +204,32 @@ impl<'v> DfsOp for TestTarget<'v> { fn add_universal_regions_outlived_by_source_to_target( &mut self, ) -> Result<bool, RegionElementIndex> { - for ur in self.inferred_values + // For all `ur_in_source` in `source_region`. + for ur_in_source in self.inferred_values .universal_regions_outlived_by(self.source_region) { - if !self.inferred_values.contains(self.target_region, ur) { - return Err(self.elements.index(ur)); + // Check that `target_region` outlives `ur_in_source`. + + // If `ur_in_source` is a member of `target_region`, OK. + // + // (This is implied by the loop below, actually, just an + // irresistible micro-opt. Mm. Premature optimization. So + // tasty.) + if self.inferred_values.contains(self.target_region, ur_in_source) { + continue; } + + // If there is some other element X such that `target_region: X` and + // `X: ur_in_source`, OK. + if self.inferred_values + .universal_regions_outlived_by(self.target_region) + .any(|ur_in_target| self.universal_regions.outlives(ur_in_target, ur_in_source)) + { + continue; + } + + // Otherwise, not known to be true. + return Err(self.elements.index(ur_in_source)); } Ok(false) 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 af88edc22ce..86ba7524bf0 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs @@ -14,7 +14,7 @@ use rustc::infer::InferCtxt; use rustc::infer::NLLRegionVariableOrigin; use rustc::infer::RegionVariableOrigin; use rustc::infer::SubregionOrigin; -use rustc::infer::region_constraints::VarOrigins; +use rustc::infer::region_constraints::{GenericKind, VarOrigins}; use rustc::mir::{ClosureOutlivesRequirement, ClosureRegionRequirements, Location, Mir}; use rustc::ty::{self, RegionVid}; use rustc_data_structures::indexed_vec::IndexVec; @@ -24,7 +24,7 @@ use syntax_pos::Span; mod annotation; mod dfs; -use self::dfs::CopyFromSourceToTarget; +use self::dfs::{CopyFromSourceToTarget, TestTargetOutlivesSource}; mod dump_mir; mod graphviz; mod values; @@ -53,6 +53,9 @@ pub struct RegionInferenceContext<'tcx> { /// The constraints we have accumulated and used during solving. constraints: Vec<Constraint>, + /// Type constraints that we check after solving. + type_tests: Vec<TypeTest<'tcx>>, + /// Information about the universally quantified regions in scope /// on this function and their (known) relations to one another. universal_regions: UniversalRegions<'tcx>, @@ -95,6 +98,90 @@ pub struct Constraint { span: Span, } +/// A "type test" corresponds to an outlives constraint between a type +/// and a lifetime, like `T: 'x` or `<T as Foo>::Bar: 'x`. They are +/// translated from the `Verify` region constraints in the ordinary +/// inference context. +/// +/// These sorts of constraints are handled differently than ordinary +/// constraints, at least at present. During type checking, the +/// `InferCtxt::process_registered_region_obligations` method will +/// attempt to convert a type test like `T: 'x` into an ordinary +/// outlives constraint when possible (for example, `&'a T: 'b` will +/// be converted into `'a: 'b` and registered as a `Constraint`). +/// +/// In some cases, however, there are outlives relationships that are +/// not converted into a region constraint, but rather into one of +/// these "type tests". The distinction is that a type test does not +/// influence the inference result, but instead just examines the +/// values that we ultimately inferred for each region variable and +/// checks that they meet certain extra criteria. If not, an error +/// can be issued. +/// +/// One reason for this is that these type tests always boil down to a +/// check like `'a: 'x` where `'a` is a universally quantified region +/// -- and therefore not one whose value is really meant to be +/// *inferred*, precisely. Another reason is that these type tests can +/// involve *disjunction* -- that is, they can be satisfied in more +/// than one way. +/// +/// For more information about this translation, see +/// `InferCtxt::process_registered_region_obligations` and +/// `InferCtxt::type_must_outlive` in `rustc::infer::outlives`. +#[derive(Clone, Debug)] +pub struct TypeTest<'tcx> { + /// The type `T` that must outlive the region. + pub generic_kind: GenericKind<'tcx>, + + /// The region `'x` that the type must outlive. + pub lower_bound: RegionVid, + + /// The point where the outlives relation must hold. + pub point: Location, + + /// Where did this constraint arise? + pub span: Span, + + /// A test which, if met by the region `'x`, proves that this type + /// constraint is satisfied. + pub test: RegionTest, +} + +/// A "test" that can be applied to some "subject region" `'x`. These are used to +/// describe type constraints. Tests do not presently affect the +/// region values that get inferred for each variable; they only +/// examine the results *after* inference. This means they can +/// conveniently include disjuction ("a or b must be true"). +#[derive(Clone, Debug)] +pub enum RegionTest { + /// The subject region `'x` must by outlived by *some* region in + /// the given set of regions. + /// + /// This test comes from e.g. a where clause like `T: 'a + 'b`, + /// which implies that we know that `T: 'a` and that `T: + /// 'b`. Therefore, if we are trying to prove that `T: 'x`, we can + /// do so by showing that `'a: 'x` *or* `'b: 'x`. + IsOutlivedByAnyRegionIn(Vec<RegionVid>), + + /// The subject region `'x` must by outlived by *all* regions in + /// the given set of regions. + /// + /// This test comes from e.g. a projection type like `T = <u32 as + /// Trait<'a, 'b>>::Foo`, which must outlive `'a` or `'b`, and + /// maybe both. Therefore we can prove that `T: 'x` if we know + /// that `'a: 'x` *and* `'b: 'x`. + IsOutlivedByAllRegionsIn(Vec<RegionVid>), + + /// Any of the given tests are true. + /// + /// This arises from projections, for which there are multiple + /// ways to prove an outlives relationship. + Any(Vec<RegionTest>), + + /// All of the given tests are true. + All(Vec<RegionTest>), +} + impl<'tcx> RegionInferenceContext<'tcx> { /// Creates a new region inference context with a total of /// `num_region_variables` valid inference variables; the first N @@ -122,6 +209,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { liveness_constraints: RegionValues::new(elements, num_region_variables), inferred_values: None, constraints: Vec::new(), + type_tests: Vec::new(), universal_regions, }; @@ -243,7 +331,14 @@ impl<'tcx> RegionInferenceContext<'tcx> { }); } - /// Perform region inference. + /// Add a "type test" that must be satisfied. + pub(super) fn add_type_test(&mut self, type_test: TypeTest<'tcx>) { + self.type_tests.push(type_test); + } + + /// 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. pub(super) fn solve( &mut self, infcx: &InferCtxt<'_, '_, 'tcx>, @@ -254,6 +349,8 @@ impl<'tcx> RegionInferenceContext<'tcx> { self.propagate_constraints(mir); + self.check_type_tests(infcx, mir); + let outlives_requirements = self.check_universal_regions(infcx, mir_def_id); if outlives_requirements.is_empty() { @@ -328,6 +425,123 @@ impl<'tcx> RegionInferenceContext<'tcx> { /// therefore add `end('a)` into the region for `'b` -- but we /// have no evidence that `'b` outlives `'a`, so we want to report /// an error. + fn check_type_tests( + &self, + infcx: &InferCtxt<'_, '_, 'tcx>, + mir: &Mir<'tcx>, + ) { + for type_test in &self.type_tests { + debug!("check_type_test: {:?}", type_test); + + if !self.eval_region_test( + mir, + type_test.point, + type_test.lower_bound, + &type_test.test, + ) { + // Oh the humanity. Obviously we will do better than this error eventually. + infcx.tcx.sess.span_err( + type_test.span, + &format!("failed type test: {:?}", type_test), + ); + } + } + } + + /// Test if `test` is true when applied to `lower_bound` at + /// `point`, and returns true or false. + fn eval_region_test( + &self, + mir: &Mir<'tcx>, + point: Location, + lower_bound: RegionVid, + test: &RegionTest, + ) -> bool { + debug!( + "eval_region_test(point={:?}, lower_bound={:?}, test={:?})", + point, + lower_bound, + test + ); + + match test { + RegionTest::IsOutlivedByAllRegionsIn(regions) => regions + .iter() + .all(|&r| self.eval_outlives(mir, r, lower_bound, point)), + + RegionTest::IsOutlivedByAnyRegionIn(regions) => regions + .iter() + .any(|&r| self.eval_outlives(mir, r, lower_bound, point)), + + RegionTest::Any(tests) => tests + .iter() + .any(|test| self.eval_region_test(mir, point, lower_bound, test)), + + RegionTest::All(tests) => tests + .iter() + .all(|test| self.eval_region_test(mir, point, lower_bound, test)), + } + } + + // Evaluate whether `sup_region: sub_region @ point`. + fn eval_outlives( + &self, + mir: &Mir<'tcx>, + sup_region: RegionVid, + sub_region: RegionVid, + point: Location, + ) -> bool { + debug!( + "eval_outlives({:?}: {:?} @ {:?})", + sup_region, + sub_region, + point + ); + + // Roughly speaking, do a DFS of all region elements reachable + // from `point` contained in `sub_region`. If any of those are + // *not* present in `sup_region`, the DFS will abort early and + // yield an `Err` result. + match self.dfs( + mir, + TestTargetOutlivesSource { + source_region: sub_region, + target_region: sup_region, + constraint_point: point, + elements: &self.elements, + universal_regions: &self.universal_regions, + inferred_values: self.inferred_values.as_ref().unwrap(), + }, + ) { + Ok(_) => { + debug!("eval_outlives: true"); + true + } + + Err(elem) => { + debug!( + "eval_outlives: false because `{:?}` is not present in `{:?}`", + self.elements.to_element(elem), + sup_region + ); + false + } + } + } + + /// Once regions have been propagated, this method is used to see + /// whether any of the constraints were too strong. In particular, + /// we want to check for a case where a universally quantified + /// region exceeded its bounds. Consider: + /// + /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x } + /// + /// In this case, returning `x` requires `&'a u32 <: &'b u32` + /// and hence we establish (transitively) a constraint that + /// `'a: 'b`. The `propagate_constraints` code above will + /// therefore add `end('a)` into the region for `'b` -- but we + /// have no evidence that `'b` outlives `'a`, so we want to report + /// an error. fn check_universal_regions( &self, infcx: &InferCtxt<'_, '_, 'tcx>, diff --git a/src/librustc_mir/borrow_check/nll/subtype_constraint_generation.rs b/src/librustc_mir/borrow_check/nll/subtype_constraint_generation.rs index c98a94fa8bc..73c40827c54 100644 --- a/src/librustc_mir/borrow_check/nll/subtype_constraint_generation.rs +++ b/src/librustc_mir/borrow_check/nll/subtype_constraint_generation.rs @@ -11,11 +11,14 @@ use rustc::mir::Mir; use rustc::infer::region_constraints::Constraint; use rustc::infer::region_constraints::RegionConstraintData; +use rustc::infer::region_constraints::{Verify, VerifyBound}; use rustc::ty; +use syntax::codemap::Span; +use transform::type_check::Locations; use transform::type_check::MirTypeckRegionConstraints; use transform::type_check::OutlivesSet; -use super::region_infer::RegionInferenceContext; +use super::region_infer::{TypeTest, RegionInferenceContext, RegionTest}; /// When the MIR type-checker executes, it validates all the types in /// the MIR, and in the process generates a set of constraints that @@ -27,10 +30,7 @@ pub(super) fn generate<'tcx>( mir: &Mir<'tcx>, constraints: &MirTypeckRegionConstraints<'tcx>, ) { - SubtypeConstraintGenerator { - regioncx, - mir, - }.generate(constraints); + SubtypeConstraintGenerator { regioncx, mir }.generate(constraints); } struct SubtypeConstraintGenerator<'cx, 'tcx: 'cx> { @@ -65,6 +65,8 @@ impl<'cx, 'tcx> SubtypeConstraintGenerator<'cx, 'tcx> { givens, } = data; + let span = self.mir.source_info(locations.from_location).span; + for constraint in constraints.keys() { debug!("generate: constraint: {:?}", constraint); let (a_vid, b_vid) = match constraint { @@ -81,12 +83,15 @@ impl<'cx, 'tcx> SubtypeConstraintGenerator<'cx, 'tcx> { // reverse direction, because `regioncx` talks about // "outlives" (`>=`) whereas the region constraints // talk about `<=`. - let span = self.mir.source_info(locations.from_location).span; self.regioncx .add_outlives(span, b_vid, a_vid, locations.at_location); } - assert!(verifys.is_empty(), "verifys not yet implemented"); + for verify in verifys { + let type_test = self.verify_to_type_test(verify, span, locations); + self.regioncx.add_type_test(type_test); + } + assert!( givens.is_empty(), "MIR type-checker does not use givens (thank goodness)" @@ -94,6 +99,55 @@ impl<'cx, 'tcx> SubtypeConstraintGenerator<'cx, 'tcx> { } } + fn verify_to_type_test( + &self, + verify: &Verify<'tcx>, + span: Span, + locations: &Locations, + ) -> TypeTest<'tcx> { + let generic_kind = verify.kind; + + let lower_bound = self.to_region_vid(verify.region); + + let point = locations.at_location; + + let test = self.verify_bound_to_region_test(&verify.bound); + + TypeTest { + generic_kind, + lower_bound, + point, + span, + test, + } + } + + fn verify_bound_to_region_test(&self, verify_bound: &VerifyBound<'tcx>) -> RegionTest { + match verify_bound { + VerifyBound::AnyRegion(regions) => RegionTest::IsOutlivedByAnyRegionIn( + regions.iter().map(|r| self.to_region_vid(r)).collect(), + ), + + VerifyBound::AllRegions(regions) => RegionTest::IsOutlivedByAllRegionsIn( + regions.iter().map(|r| self.to_region_vid(r)).collect(), + ), + + VerifyBound::AnyBound(bounds) => RegionTest::Any( + bounds + .iter() + .map(|b| self.verify_bound_to_region_test(b)) + .collect(), + ), + + VerifyBound::AllBounds(bounds) => RegionTest::All( + bounds + .iter() + .map(|b| self.verify_bound_to_region_test(b)) + .collect(), + ), + } + } + fn to_region_vid(&self, r: ty::Region<'tcx>) -> ty::RegionVid { // Every region that we see in the constraints came from the // MIR or from the parameter environment. If the former, it diff --git a/src/test/ui/nll/ty-outlives/ty-param-fn.rs b/src/test/ui/nll/ty-outlives/ty-param-fn.rs new file mode 100644 index 00000000000..c6547ae68fa --- /dev/null +++ b/src/test/ui/nll/ty-outlives/ty-param-fn.rs @@ -0,0 +1,51 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// compile-flags:-Znll -Zborrowck=mir + +#![allow(warnings)] +#![feature(dyn_trait)] + +use std::fmt::Debug; + +fn no_region<'a, T>(x: Box<T>) -> Box<Debug + 'a> +where + T: Debug, +{ + x + //~^ WARNING not reporting region error due to -Znll + //~| ERROR failed type test +} + +fn correct_region<'a, T>(x: Box<T>) -> Box<Debug + 'a> +where + T: 'a + Debug, +{ + x +} + +fn wrong_region<'a, 'b, T>(x: Box<T>) -> Box<Debug + 'a> +where + T: 'b + Debug, +{ + x + //~^ WARNING not reporting region error due to -Znll + //~| ERROR failed type test +} + +fn outlives_region<'a, 'b, T>(x: Box<T>) -> Box<Debug + 'a> +where + T: 'b + Debug, + 'b: 'a, +{ + x +} + +fn main() {} diff --git a/src/test/ui/nll/ty-outlives/ty-param-fn.stderr b/src/test/ui/nll/ty-outlives/ty-param-fn.stderr new file mode 100644 index 00000000000..5b29ff88621 --- /dev/null +++ b/src/test/ui/nll/ty-outlives/ty-param-fn.stderr @@ -0,0 +1,26 @@ +warning: not reporting region error due to -Znll + --> $DIR/ty-param-fn.rs:22:5 + | +22 | x + | ^ + +warning: not reporting region error due to -Znll + --> $DIR/ty-param-fn.rs:38:5 + | +38 | x + | ^ + +error: failed type test: TypeTest { generic_kind: T/#1, lower_bound: '_#2r, point: bb0[3], span: $DIR/ty-param-fn.rs:22:5: 22:6, test: IsOutlivedByAnyRegionIn([]) } + --> $DIR/ty-param-fn.rs:22:5 + | +22 | x + | ^ + +error: failed type test: TypeTest { generic_kind: T/#2, lower_bound: '_#3r, point: bb0[3], span: $DIR/ty-param-fn.rs:38:5: 38:6, test: IsOutlivedByAnyRegionIn(['_#2r]) } + --> $DIR/ty-param-fn.rs:38:5 + | +38 | x + | ^ + +error: aborting due to 2 previous errors + |