From ba2ef58ae6c126ec0b87b307d45fef2da127be22 Mon Sep 17 00:00:00 2001 From: matthewjasper Date: Tue, 16 Jun 2020 18:27:40 +0100 Subject: [PATCH] Unify region variables when projecting associated types This is required to avoid cycles when evaluating auto trait predicates. --- .../infer/canonical/canonicalizer.rs | 11 ++++- .../infer/region_constraints/mod.rs | 17 +++----- src/librustc_infer/infer/resolve.rs | 43 +++++++++++-------- src/librustc_middle/ty/fold.rs | 3 ++ .../traits/project.rs | 12 +++++- .../project-fn-ret-invariant.transmute.stderr | 4 +- .../{ => auto-traits}/auto-is-contextual.rs | 0 .../auto-trait-projection-recursion.rs | 34 +++++++++++++++ .../auto-trait-validation.rs | 0 .../auto-trait-validation.stderr | 0 .../ui/{traits => auto-traits}/auto-traits.rs | 0 .../{issues => auto-traits}/issue-23080-2.rs | 0 .../issue-23080-2.stderr | 0 .../ui/{issues => auto-traits}/issue-23080.rs | 0 .../issue-23080.stderr | 0 .../typeck-auto-trait-no-supertraits-2.rs | 0 .../typeck-auto-trait-no-supertraits-2.stderr | 0 .../typeck-auto-trait-no-supertraits.rs | 0 .../typeck-auto-trait-no-supertraits.stderr | 0 ...-default-trait-impl-constituent-types-2.rs | 0 ...ault-trait-impl-constituent-types-2.stderr | 0 ...ck-default-trait-impl-constituent-types.rs | 0 ...efault-trait-impl-constituent-types.stderr | 0 .../typeck-default-trait-impl-negation.rs | 0 .../typeck-default-trait-impl-negation.stderr | 0 .../typeck-default-trait-impl-precedence.rs | 0 ...ypeck-default-trait-impl-precedence.stderr | 0 .../traits-inductive-overflow-lifetime.rs | 30 +++++++++++++ .../traits-inductive-overflow-lifetime.stderr | 14 ++++++ 29 files changed, 133 insertions(+), 35 deletions(-) rename src/test/ui/{ => auto-traits}/auto-is-contextual.rs (100%) create mode 100644 src/test/ui/auto-traits/auto-trait-projection-recursion.rs rename src/test/ui/{ => auto-traits}/auto-trait-validation.rs (100%) rename src/test/ui/{ => auto-traits}/auto-trait-validation.stderr (100%) rename src/test/ui/{traits => auto-traits}/auto-traits.rs (100%) rename src/test/ui/{issues => auto-traits}/issue-23080-2.rs (100%) rename src/test/ui/{issues => auto-traits}/issue-23080-2.stderr (100%) rename src/test/ui/{issues => auto-traits}/issue-23080.rs (100%) rename src/test/ui/{issues => auto-traits}/issue-23080.stderr (100%) rename src/test/ui/{typeck => auto-traits}/typeck-auto-trait-no-supertraits-2.rs (100%) rename src/test/ui/{typeck => auto-traits}/typeck-auto-trait-no-supertraits-2.stderr (100%) rename src/test/ui/{typeck => auto-traits}/typeck-auto-trait-no-supertraits.rs (100%) rename src/test/ui/{typeck => auto-traits}/typeck-auto-trait-no-supertraits.stderr (100%) rename src/test/ui/{typeck => auto-traits}/typeck-default-trait-impl-constituent-types-2.rs (100%) rename src/test/ui/{typeck => auto-traits}/typeck-default-trait-impl-constituent-types-2.stderr (100%) rename src/test/ui/{typeck => auto-traits}/typeck-default-trait-impl-constituent-types.rs (100%) rename src/test/ui/{typeck => auto-traits}/typeck-default-trait-impl-constituent-types.stderr (100%) rename src/test/ui/{typeck => auto-traits}/typeck-default-trait-impl-negation.rs (100%) rename src/test/ui/{typeck => auto-traits}/typeck-default-trait-impl-negation.stderr (100%) rename src/test/ui/{typeck => auto-traits}/typeck-default-trait-impl-precedence.rs (100%) rename src/test/ui/{typeck => auto-traits}/typeck-default-trait-impl-precedence.stderr (100%) create mode 100644 src/test/ui/traits/traits-inductive-overflow-lifetime.rs create mode 100644 src/test/ui/traits/traits-inductive-overflow-lifetime.stderr diff --git a/src/librustc_infer/infer/canonical/canonicalizer.rs b/src/librustc_infer/infer/canonical/canonicalizer.rs index c2dae6ba4f8..8695b9616ee 100644 --- a/src/librustc_infer/infer/canonical/canonicalizer.rs +++ b/src/librustc_infer/infer/canonical/canonicalizer.rs @@ -314,18 +314,25 @@ fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { } ty::ReVar(vid) => { - let r = self + let resolved_vid = self .infcx .unwrap() .inner .borrow_mut() .unwrap_region_constraints() - .opportunistic_resolve_var(self.tcx, vid); + .opportunistic_resolve_var(vid); debug!( "canonical: region var found with vid {:?}, \ opportunistically resolved to {:?}", vid, r ); + // micro-optimize -- avoid an interner look-up if the vid + // hasn't changed. + let r = if vid == resolved_vid { + r + } else { + self.tcx.mk_region(ty::ReVar(resolved_vid)) + }; self.canonicalize_region_mode.canonicalize_free_region(self, r) } diff --git a/src/librustc_infer/infer/region_constraints/mod.rs b/src/librustc_infer/infer/region_constraints/mod.rs index 626774617a6..90d61a78f9b 100644 --- a/src/librustc_infer/infer/region_constraints/mod.rs +++ b/src/librustc_infer/infer/region_constraints/mod.rs @@ -50,10 +50,10 @@ pub struct RegionConstraintStorage<'tcx> { /// R1 <= R2 and R2 <= R1 and (b) we unify the two regions in this /// table. You can then call `opportunistic_resolve_var` early /// which will map R1 and R2 to some common region (i.e., either - /// R1 or R2). This is important when dropck and other such code - /// is iterating to a fixed point, because otherwise we sometimes - /// would wind up with a fresh stream of region variables that - /// have been equated but appear distinct. + /// R1 or R2). This is important when fulfillment, dropck and other such + /// code is iterating to a fixed point, because otherwise we sometimes + /// would wind up with a fresh stream of region variables that have been + /// equated but appear distinct. pub(super) unification_table: ut::UnificationTableStorage, /// a flag set to true when we perform any unifications; this is used @@ -714,13 +714,8 @@ pub fn glb_regions( } } - pub fn opportunistic_resolve_var( - &mut self, - tcx: TyCtxt<'tcx>, - rid: RegionVid, - ) -> ty::Region<'tcx> { - let vid = self.unification_table().probe_value(rid).min_vid; - tcx.mk_region(ty::ReVar(vid)) + pub fn opportunistic_resolve_var(&mut self, rid: RegionVid) -> ty::RegionVid { + self.unification_table().probe_value(rid).min_vid } fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> { diff --git a/src/librustc_infer/infer/resolve.rs b/src/librustc_infer/infer/resolve.rs index e28cf49c7f2..bda38301f1c 100644 --- a/src/librustc_infer/infer/resolve.rs +++ b/src/librustc_infer/infer/resolve.rs @@ -46,51 +46,56 @@ fn fold_const(&mut self, ct: &'tcx Const<'tcx>) -> &'tcx Const<'tcx> { } } -/// The opportunistic type and region resolver is similar to the -/// opportunistic type resolver, but also opportunistically resolves -/// regions. It is useful for canonicalization. -pub struct OpportunisticTypeAndRegionResolver<'a, 'tcx> { +/// The opportunistic region resolver opportunistically resolves regions +/// variables to the variable with the least variable id. It is used when +/// normlizing projections to avoid hitting the recursion limit by creating +/// many versions of a predicate for types that in the end have to unify. +/// +/// If you want to resolve type and const variables as well, call +/// [InferCtxt::resolve_vars_if_possible] first. +pub struct OpportunisticRegionResolver<'a, 'tcx> { infcx: &'a InferCtxt<'a, 'tcx>, } -impl<'a, 'tcx> OpportunisticTypeAndRegionResolver<'a, 'tcx> { +impl<'a, 'tcx> OpportunisticRegionResolver<'a, 'tcx> { pub fn new(infcx: &'a InferCtxt<'a, 'tcx>) -> Self { - OpportunisticTypeAndRegionResolver { infcx } + OpportunisticRegionResolver { infcx } } } -impl<'a, 'tcx> TypeFolder<'tcx> for OpportunisticTypeAndRegionResolver<'a, 'tcx> { +impl<'a, 'tcx> TypeFolder<'tcx> for OpportunisticRegionResolver<'a, 'tcx> { fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { self.infcx.tcx } fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { - if !t.needs_infer() { + if !t.has_infer_regions() { t // micro-optimize -- if there is nothing in this type that this fold affects... } else { - let t0 = self.infcx.shallow_resolve(t); - t0.super_fold_with(self) + t.super_fold_with(self) } } fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { match *r { - ty::ReVar(rid) => self - .infcx - .inner - .borrow_mut() - .unwrap_region_constraints() - .opportunistic_resolve_var(self.tcx(), rid), + ty::ReVar(rid) => { + let resolved = self + .infcx + .inner + .borrow_mut() + .unwrap_region_constraints() + .opportunistic_resolve_var(rid); + if resolved == rid { r } else { self.tcx().mk_region(ty::ReVar(resolved)) } + } _ => r, } } fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> { - if !ct.needs_infer() { + if !ct.has_infer_regions() { ct // micro-optimize -- if there is nothing in this const that this fold affects... } else { - let c0 = self.infcx.shallow_resolve(ct); - c0.super_fold_with(self) + ct.super_fold_with(self) } } } diff --git a/src/librustc_middle/ty/fold.rs b/src/librustc_middle/ty/fold.rs index 248dd00ef47..24dbf7b8c46 100644 --- a/src/librustc_middle/ty/fold.rs +++ b/src/librustc_middle/ty/fold.rs @@ -87,6 +87,9 @@ fn references_error(&self) -> bool { fn has_param_types_or_consts(&self) -> bool { self.has_type_flags(TypeFlags::HAS_TY_PARAM | TypeFlags::HAS_CT_PARAM) } + fn has_infer_regions(&self) -> bool { + self.has_type_flags(TypeFlags::HAS_RE_INFER) + } fn has_infer_types(&self) -> bool { self.has_type_flags(TypeFlags::HAS_TY_INFER) } diff --git a/src/librustc_trait_selection/traits/project.rs b/src/librustc_trait_selection/traits/project.rs index 9492c3c3409..bccd903f57e 100644 --- a/src/librustc_trait_selection/traits/project.rs +++ b/src/librustc_trait_selection/traits/project.rs @@ -24,6 +24,7 @@ use rustc_errors::ErrorReported; use rustc_hir::def_id::DefId; use rustc_hir::lang_items::{FnOnceTraitLangItem, GeneratorTraitLangItem}; +use rustc_infer::infer::resolve::OpportunisticRegionResolver; use rustc_middle::ty::fold::{TypeFoldable, TypeFolder}; use rustc_middle::ty::subst::Subst; use rustc_middle::ty::util::IntTypeExt; @@ -1146,7 +1147,7 @@ fn confirm_candidate<'cx, 'tcx>( ) -> Progress<'tcx> { debug!("confirm_candidate(candidate={:?}, obligation={:?})", candidate, obligation); - match candidate { + let mut progress = match candidate { ProjectionTyCandidate::ParamEnv(poly_projection) | ProjectionTyCandidate::TraitDef(poly_projection) => { confirm_param_env_candidate(selcx, obligation, poly_projection) @@ -1155,7 +1156,16 @@ fn confirm_candidate<'cx, 'tcx>( ProjectionTyCandidate::Select(impl_source) => { confirm_select_candidate(selcx, obligation, obligation_trait_ref, impl_source) } + }; + // When checking for cycle during evaluation, we compare predicates with + // "syntactic" equality. Since normalization generally introduces a type + // with new region variables, we need to resolve them to existing variables + // when possible for this to work. See `auto-trait-projection-recursion.rs` + // for a case where this matters. + if progress.ty.has_infer_regions() { + progress.ty = OpportunisticRegionResolver::new(selcx.infcx()).fold_ty(progress.ty); } + progress } fn confirm_select_candidate<'cx, 'tcx>( diff --git a/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr b/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr index 137cb83ccd3..0a05fc6bb82 100644 --- a/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr +++ b/src/test/ui/associated-types/cache/project-fn-ret-invariant.transmute.stderr @@ -1,8 +1,8 @@ error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements - --> $DIR/project-fn-ret-invariant.rs:48:8 + --> $DIR/project-fn-ret-invariant.rs:48:4 | LL | bar(foo, x) - | ^^^ + | ^^^^^^^^^^^ | note: first, the lifetime cannot outlive the lifetime `'a` as defined on the function body at 44:8... --> $DIR/project-fn-ret-invariant.rs:44:8 diff --git a/src/test/ui/auto-is-contextual.rs b/src/test/ui/auto-traits/auto-is-contextual.rs similarity index 100% rename from src/test/ui/auto-is-contextual.rs rename to src/test/ui/auto-traits/auto-is-contextual.rs diff --git a/src/test/ui/auto-traits/auto-trait-projection-recursion.rs b/src/test/ui/auto-traits/auto-trait-projection-recursion.rs new file mode 100644 index 00000000000..a36f26f02e9 --- /dev/null +++ b/src/test/ui/auto-traits/auto-trait-projection-recursion.rs @@ -0,0 +1,34 @@ +// Checking the `Send` bound in `main` requires: +// +// checking as Y>::P: Send +// which normalizes to Box>>: Send +// which needs X>: Send +// which needs as Y>::P: Send +// +// At this point we used to normalize the predicate to `Box>>: Send` +// and continue in a loop where we created new region variables to the +// recursion limit. To avoid this we now "canonicalize" region variables to +// lowest unified region vid. This means we instead have to prove +// `Box>>: Send`, which we can because auto traits are coinductive. + +// check-pass + +// Avoid a really long error message if this regresses. +#![recursion_limit="20"] + +trait Y { + type P; +} + +impl<'a> Y for C<'a> { + type P = Box>>; +} + +struct C<'a>(&'a ()); +struct X(T::P); + +fn is_send() {} + +fn main() { + is_send::>>(); +} diff --git a/src/test/ui/auto-trait-validation.rs b/src/test/ui/auto-traits/auto-trait-validation.rs similarity index 100% rename from src/test/ui/auto-trait-validation.rs rename to src/test/ui/auto-traits/auto-trait-validation.rs diff --git a/src/test/ui/auto-trait-validation.stderr b/src/test/ui/auto-traits/auto-trait-validation.stderr similarity index 100% rename from src/test/ui/auto-trait-validation.stderr rename to src/test/ui/auto-traits/auto-trait-validation.stderr diff --git a/src/test/ui/traits/auto-traits.rs b/src/test/ui/auto-traits/auto-traits.rs similarity index 100% rename from src/test/ui/traits/auto-traits.rs rename to src/test/ui/auto-traits/auto-traits.rs diff --git a/src/test/ui/issues/issue-23080-2.rs b/src/test/ui/auto-traits/issue-23080-2.rs similarity index 100% rename from src/test/ui/issues/issue-23080-2.rs rename to src/test/ui/auto-traits/issue-23080-2.rs diff --git a/src/test/ui/issues/issue-23080-2.stderr b/src/test/ui/auto-traits/issue-23080-2.stderr similarity index 100% rename from src/test/ui/issues/issue-23080-2.stderr rename to src/test/ui/auto-traits/issue-23080-2.stderr diff --git a/src/test/ui/issues/issue-23080.rs b/src/test/ui/auto-traits/issue-23080.rs similarity index 100% rename from src/test/ui/issues/issue-23080.rs rename to src/test/ui/auto-traits/issue-23080.rs diff --git a/src/test/ui/issues/issue-23080.stderr b/src/test/ui/auto-traits/issue-23080.stderr similarity index 100% rename from src/test/ui/issues/issue-23080.stderr rename to src/test/ui/auto-traits/issue-23080.stderr diff --git a/src/test/ui/typeck/typeck-auto-trait-no-supertraits-2.rs b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits-2.rs similarity index 100% rename from src/test/ui/typeck/typeck-auto-trait-no-supertraits-2.rs rename to src/test/ui/auto-traits/typeck-auto-trait-no-supertraits-2.rs diff --git a/src/test/ui/typeck/typeck-auto-trait-no-supertraits-2.stderr b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits-2.stderr similarity index 100% rename from src/test/ui/typeck/typeck-auto-trait-no-supertraits-2.stderr rename to src/test/ui/auto-traits/typeck-auto-trait-no-supertraits-2.stderr diff --git a/src/test/ui/typeck/typeck-auto-trait-no-supertraits.rs b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits.rs similarity index 100% rename from src/test/ui/typeck/typeck-auto-trait-no-supertraits.rs rename to src/test/ui/auto-traits/typeck-auto-trait-no-supertraits.rs diff --git a/src/test/ui/typeck/typeck-auto-trait-no-supertraits.stderr b/src/test/ui/auto-traits/typeck-auto-trait-no-supertraits.stderr similarity index 100% rename from src/test/ui/typeck/typeck-auto-trait-no-supertraits.stderr rename to src/test/ui/auto-traits/typeck-auto-trait-no-supertraits.stderr diff --git a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types-2.rs b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types-2.rs similarity index 100% rename from src/test/ui/typeck/typeck-default-trait-impl-constituent-types-2.rs rename to src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types-2.rs diff --git a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types-2.stderr b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types-2.stderr similarity index 100% rename from src/test/ui/typeck/typeck-default-trait-impl-constituent-types-2.stderr rename to src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types-2.stderr diff --git a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types.rs b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types.rs similarity index 100% rename from src/test/ui/typeck/typeck-default-trait-impl-constituent-types.rs rename to src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types.rs diff --git a/src/test/ui/typeck/typeck-default-trait-impl-constituent-types.stderr b/src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types.stderr similarity index 100% rename from src/test/ui/typeck/typeck-default-trait-impl-constituent-types.stderr rename to src/test/ui/auto-traits/typeck-default-trait-impl-constituent-types.stderr diff --git a/src/test/ui/typeck/typeck-default-trait-impl-negation.rs b/src/test/ui/auto-traits/typeck-default-trait-impl-negation.rs similarity index 100% rename from src/test/ui/typeck/typeck-default-trait-impl-negation.rs rename to src/test/ui/auto-traits/typeck-default-trait-impl-negation.rs diff --git a/src/test/ui/typeck/typeck-default-trait-impl-negation.stderr b/src/test/ui/auto-traits/typeck-default-trait-impl-negation.stderr similarity index 100% rename from src/test/ui/typeck/typeck-default-trait-impl-negation.stderr rename to src/test/ui/auto-traits/typeck-default-trait-impl-negation.stderr diff --git a/src/test/ui/typeck/typeck-default-trait-impl-precedence.rs b/src/test/ui/auto-traits/typeck-default-trait-impl-precedence.rs similarity index 100% rename from src/test/ui/typeck/typeck-default-trait-impl-precedence.rs rename to src/test/ui/auto-traits/typeck-default-trait-impl-precedence.rs diff --git a/src/test/ui/typeck/typeck-default-trait-impl-precedence.stderr b/src/test/ui/auto-traits/typeck-default-trait-impl-precedence.stderr similarity index 100% rename from src/test/ui/typeck/typeck-default-trait-impl-precedence.stderr rename to src/test/ui/auto-traits/typeck-default-trait-impl-precedence.stderr diff --git a/src/test/ui/traits/traits-inductive-overflow-lifetime.rs b/src/test/ui/traits/traits-inductive-overflow-lifetime.rs new file mode 100644 index 00000000000..205d50a2ed9 --- /dev/null +++ b/src/test/ui/traits/traits-inductive-overflow-lifetime.rs @@ -0,0 +1,30 @@ +// Test that we don't hit the recursion limit for short cycles involving lifetimes. + +// Shouldn't hit this, we should realize that we're in a cycle sooner. +#![recursion_limit="20"] + +trait NotAuto {} +trait Y { + type P; +} + +impl<'a> Y for C<'a> { + type P = Box>>; +} + +struct C<'a>(&'a ()); +struct X(T::P); + +impl NotAuto for Box {} +impl NotAuto for X where T::P: NotAuto {} +impl<'a> NotAuto for C<'a> {} + +fn is_send() {} +//~^ NOTE: required + +fn main() { + // Should only be a few notes. + is_send::>>(); + //~^ ERROR overflow evaluating + //~| NOTE: required +} diff --git a/src/test/ui/traits/traits-inductive-overflow-lifetime.stderr b/src/test/ui/traits/traits-inductive-overflow-lifetime.stderr new file mode 100644 index 00000000000..9a227229ea4 --- /dev/null +++ b/src/test/ui/traits/traits-inductive-overflow-lifetime.stderr @@ -0,0 +1,14 @@ +error[E0275]: overflow evaluating the requirement `std::boxed::Box>>: NotAuto` + --> $DIR/traits-inductive-overflow-lifetime.rs:27:5 + | +LL | fn is_send() {} + | ------- required by this bound in `is_send` +... +LL | is_send::>>(); + | ^^^^^^^^^^^^^^^^^^^^^^^^ + | + = note: required because of the requirements on the impl of `NotAuto` for `X>` + +error: aborting due to previous error + +For more information about this error, try `rustc --explain E0275`. -- 2.44.0