From 79e8c311765df4c35558aa9683f1e2004719175a Mon Sep 17 00:00:00 2001 From: Matthew Jasper Date: Wed, 6 Feb 2019 14:13:01 +0100 Subject: [PATCH] Propagate region constraints more precisely from closures --- .../borrow_check/nll/region_infer/mod.rs | 66 +++++++----- .../nll/type_check/free_region_relations.rs | 102 +++++++++++------- .../issue-58127-mutliple-requirements.rs | 40 +++++++ 3 files changed, 142 insertions(+), 66 deletions(-) create mode 100644 src/test/ui/nll/closure-requirements/issue-58127-mutliple-requirements.rs 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 7a0cd2ac26c..cbeb5dc206e 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs @@ -763,20 +763,26 @@ fn try_promote_type_test<'gcx>( debug!("try_promote_type_test: ur={:?}", ur); - let non_local_ub = self.universal_region_relations.non_local_upper_bound(ur); + let non_local_ub = self.universal_region_relations.non_local_upper_bounds(&ur); debug!("try_promote_type_test: non_local_ub={:?}", non_local_ub); - assert!(self.universal_regions.is_universal_region(non_local_ub)); - assert!(!self.universal_regions.is_local_free_region(non_local_ub)); - - let requirement = ClosureOutlivesRequirement { - subject, - outlived_free_region: non_local_ub, - blame_span: locations.span(mir), - category: ConstraintCategory::Boring, - }; - debug!("try_promote_type_test: pushing {:#?}", requirement); - propagated_outlives_requirements.push(requirement); + // This is slightly too conservative. To show T: '1, given `'2: '1` + // and `'3: '1` we only need to prove that T: '2 *or* T: '3, but to + // avoid potential non-determinism we approximate this by requiring + // T: '1 and T: '2. + for &upper_bound in non_local_ub { + debug_assert!(self.universal_regions.is_universal_region(upper_bound)); + debug_assert!(!self.universal_regions.is_local_free_region(upper_bound)); + + let requirement = ClosureOutlivesRequirement { + subject, + outlived_free_region: upper_bound, + blame_span: locations.span(mir), + category: ConstraintCategory::Boring, + }; + debug!("try_promote_type_test: pushing {:#?}", requirement); + propagated_outlives_requirements.push(requirement); + } } true } @@ -1217,35 +1223,37 @@ fn check_universal_region_relation( longer_fr, shorter_fr, ); - if let Some(propagated_outlives_requirements) = propagated_outlives_requirements { - // Shrink `fr` until we find a non-local region (if we do). - // We'll call that `fr-` -- it's ever so slightly smaller than `fr`. - if let Some(fr_minus) = self.universal_region_relations + // Shrink `longer_fr` until we find a non-local region (if we do). + // We'll call it `fr-` -- it's ever so slightly smaller than + // `longer_fr`. + + if let Some(fr_minus) = self + .universal_region_relations .non_local_lower_bound(longer_fr) { debug!("check_universal_region: fr_minus={:?}", fr_minus); let blame_span_category = self.find_outlives_blame_span(mir, longer_fr, shorter_fr); - // Grow `shorter_fr` until we find a non-local - // region. (We always will.) We'll call that - // `shorter_fr+` -- it's ever so slightly larger than - // `fr`. + // Grow `shorter_fr` until we find some non-local regions. (We + // always will.) We'll call them `shorter_fr+` -- they're ever + // so slightly larger than `shorter_fr`. let shorter_fr_plus = self.universal_region_relations - .non_local_upper_bound(shorter_fr); + .non_local_upper_bounds(&shorter_fr); debug!( "check_universal_region: shorter_fr_plus={:?}", shorter_fr_plus ); - - // Push the constraint `fr-: shorter_fr+` - propagated_outlives_requirements.push(ClosureOutlivesRequirement { - subject: ClosureOutlivesSubject::Region(fr_minus), - outlived_free_region: shorter_fr_plus, - blame_span: blame_span_category.1, - category: blame_span_category.0, - }); + for &&fr in &shorter_fr_plus { + // Push the constraint `fr-: shorter_fr+` + propagated_outlives_requirements.push(ClosureOutlivesRequirement { + subject: ClosureOutlivesSubject::Region(fr_minus), + outlived_free_region: fr, + blame_span: blame_span_category.1, + category: blame_span_category.0, + }); + } return None; } } diff --git a/src/librustc_mir/borrow_check/nll/type_check/free_region_relations.rs b/src/librustc_mir/borrow_check/nll/type_check/free_region_relations.rs index 7ddfd55dbbb..3b663ef6dad 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/free_region_relations.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/free_region_relations.rs @@ -105,44 +105,89 @@ fn relate_universal_regions(&mut self, fr_a: RegionVid, fr_b: RegionVid) { /// Finds an "upper bound" for `fr` that is not local. In other /// words, returns the smallest (*) known region `fr1` that (a) - /// outlives `fr` and (b) is not local. This cannot fail, because - /// we will always find `'static` at worst. + /// outlives `fr` and (b) is not local. /// - /// (*) If there are multiple competing choices, we pick the "postdominating" - /// one. See `TransitiveRelation::postdom_upper_bound` for details. - crate fn non_local_upper_bound(&self, fr: RegionVid) -> RegionVid { + /// (*) If there are multiple competing choices, we return all of them. + crate fn non_local_upper_bounds(&'a self, fr: &'a RegionVid) -> Vec<&'a RegionVid> { debug!("non_local_upper_bound(fr={:?})", fr); - self.non_local_bound(&self.inverse_outlives, fr) + let res = self.non_local_bounds(&self.inverse_outlives, fr); + assert!(!res.is_empty(), "can't find an upper bound!?"); + res + } + + /// Returns the "postdominating" bound of the set of + /// `non_local_upper_bounds` for the given region. + crate fn non_local_upper_bound(&self, fr: RegionVid) -> RegionVid { + let upper_bounds = self.non_local_upper_bounds(&fr); + + // In case we find more than one, reduce to one for + // convenience. This is to prevent us from generating more + // complex constraints, but it will cause spurious errors. + let post_dom = self + .inverse_outlives + .mutual_immediate_postdominator(upper_bounds); + + debug!("non_local_bound: post_dom={:?}", post_dom); + + post_dom + .and_then(|&post_dom| { + // If the mutual immediate postdom is not local, then + // there is no non-local result we can return. + if !self.universal_regions.is_local_free_region(post_dom) { + Some(post_dom) + } else { + None + } + }) .unwrap_or(self.universal_regions.fr_static) } + /// Finds a "lower bound" for `fr` that is not local. In other /// words, returns the largest (*) known region `fr1` that (a) is - /// outlived by `fr` and (b) is not local. This cannot fail, - /// because we will always find `'static` at worst. + /// outlived by `fr` and (b) is not local. /// /// (*) If there are multiple competing choices, we pick the "postdominating" /// one. See `TransitiveRelation::postdom_upper_bound` for details. crate fn non_local_lower_bound(&self, fr: RegionVid) -> Option { debug!("non_local_lower_bound(fr={:?})", fr); - self.non_local_bound(&self.outlives, fr) + let lower_bounds = self.non_local_bounds(&self.outlives, &fr); + + // In case we find more than one, reduce to one for + // convenience. This is to prevent us from generating more + // complex constraints, but it will cause spurious errors. + let post_dom = self + .outlives + .mutual_immediate_postdominator(lower_bounds); + + debug!("non_local_bound: post_dom={:?}", post_dom); + + post_dom + .and_then(|&post_dom| { + // If the mutual immediate postdom is not local, then + // there is no non-local result we can return. + if !self.universal_regions.is_local_free_region(post_dom) { + Some(post_dom) + } else { + None + } + }) } - /// Helper for `non_local_upper_bound` and - /// `non_local_lower_bound`. Repeatedly invokes `postdom_parent` - /// until we find something that is not local. Returns `None` if we - /// never do so. - fn non_local_bound( + /// Helper for `non_local_upper_bounds` and `non_local_lower_bounds`. + /// Repeatedly invokes `postdom_parent` until we find something that is not + /// local. Returns `None` if we never do so. + fn non_local_bounds<'a>( &self, - relation: &TransitiveRelation, - fr0: RegionVid, - ) -> Option { + relation: &'a TransitiveRelation, + fr0: &'a RegionVid, + ) -> Vec<&'a RegionVid> { // This method assumes that `fr0` is one of the universally // quantified region variables. - assert!(self.universal_regions.is_universal_region(fr0)); + assert!(self.universal_regions.is_universal_region(*fr0)); let mut external_parents = vec![]; - let mut queue = vec![&fr0]; + let mut queue = vec![fr0]; // Keep expanding `fr` into its parents until we reach // non-local regions. @@ -157,24 +202,7 @@ fn non_local_bound( debug!("non_local_bound: external_parents={:?}", external_parents); - // In case we find more than one, reduce to one for - // convenience. This is to prevent us from generating more - // complex constraints, but it will cause spurious errors. - let post_dom = relation - .mutual_immediate_postdominator(external_parents) - .cloned(); - - debug!("non_local_bound: post_dom={:?}", post_dom); - - post_dom.and_then(|post_dom| { - // If the mutual immediate postdom is not local, then - // there is no non-local result we can return. - if !self.universal_regions.is_local_free_region(post_dom) { - Some(post_dom) - } else { - None - } - }) + external_parents } /// Returns `true` if fr1 is known to outlive fr2. diff --git a/src/test/ui/nll/closure-requirements/issue-58127-mutliple-requirements.rs b/src/test/ui/nll/closure-requirements/issue-58127-mutliple-requirements.rs new file mode 100644 index 00000000000..71d5d4053ee --- /dev/null +++ b/src/test/ui/nll/closure-requirements/issue-58127-mutliple-requirements.rs @@ -0,0 +1,40 @@ +// revisions: migrate nll +//[migrate]compile-flags: -Z borrowck=migrate +#![cfg_attr(nll, feature(nll))] + +// compile-pass + +// Test that we propagate region relations from closures precisely when there is +// more than one non-local lower bound. + +// In this case the closure has signature +// |x: &'4 mut (&'5 (&'1 str, &'2 str), &'3 str)| -> .. +// We end up with a `'3: '5` constraint that we can propagate as +// `'3: '1`, `'3: '2`, but previously we approximated it as `'3: 'static`. + +// As an optimization, we primarily propagate bounds for the "representative" +// of each SCC. As such we have these two similar cases where hopefully one +// of them will test the case we want (case2, when this test was added). +mod case1 { + fn f(s: &str) { + g(s, |x| h(x)); + } + + fn g(_: T, _: F) + where F: Fn(&mut (&(T, T), T)) {} + + fn h(_: &mut (&(T, T), T)) {} +} + +mod case2 { + fn f(s: &str) { + g(s, |x| h(x)); + } + + fn g(_: T, _: F) + where F: Fn(&mut (T, &(T, T))) {} + + fn h(_: &mut (T, &(T, T))) {} +} + +fn main() {} -- 2.44.0