From 26199f0cbc947a09d21044aacaa1ae12af465e65 Mon Sep 17 00:00:00 2001 From: Eduard-Mihai Burtescu Date: Fri, 20 Mar 2020 07:42:14 +0200 Subject: [PATCH] ty/walk: switch `walk_shallow` from `Ty` to `GenericArg`. --- src/librustc_infer/infer/outlives/verify.rs | 42 +++++++++++--------- src/librustc_middle/ty/mod.rs | 7 ---- src/librustc_middle/ty/outlives.rs | 44 ++++++++++++--------- src/librustc_middle/ty/sty.rs | 26 ------------ src/librustc_middle/ty/walk.rs | 19 +++++---- 5 files changed, 58 insertions(+), 80 deletions(-) diff --git a/src/librustc_infer/infer/outlives/verify.rs b/src/librustc_infer/infer/outlives/verify.rs index 1cd6830b6a2..ed967f7ab3a 100644 --- a/src/librustc_infer/infer/outlives/verify.rs +++ b/src/librustc_infer/infer/outlives/verify.rs @@ -3,11 +3,9 @@ use crate::traits; use rustc_data_structures::captures::Captures; use rustc_hir::def_id::DefId; -use rustc_middle::ty::subst::{InternalSubsts, Subst}; +use rustc_middle::ty::subst::{GenericArg, GenericArgKind, InternalSubsts, Subst}; use rustc_middle::ty::{self, Ty, TyCtxt}; -use smallvec::smallvec; - /// The `TypeOutlives` struct has the job of "lowering" a `T: 'a` /// obligation into a series of `'a: 'b` constraints and "verifys", as /// described on the module comment. The final constraints are emitted @@ -44,7 +42,7 @@ fn type_bound(&self, ty: Ty<'tcx>) -> VerifyBound<'tcx> { match ty.kind { ty::Param(p) => self.param_bound(p), ty::Projection(data) => self.projection_bound(data), - _ => self.recursive_type_bound(ty), + _ => self.recursive_bound(ty.into()), } } @@ -144,25 +142,33 @@ pub fn projection_bound(&self, projection_ty: ty::ProjectionTy<'tcx>) -> VerifyB // see the extensive comment in projection_must_outlive let ty = self.tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs); - let recursive_bound = self.recursive_type_bound(ty); + let recursive_bound = self.recursive_bound(ty.into()); VerifyBound::AnyBound(env_bounds.chain(trait_bounds).collect()).or(recursive_bound) } - fn recursive_type_bound(&self, ty: Ty<'tcx>) -> VerifyBound<'tcx> { - let mut bounds = ty.walk_shallow().map(|subty| self.type_bound(subty)).collect::>(); - - let mut regions = smallvec![]; - ty.push_regions(&mut regions); - regions.retain(|r| !r.is_late_bound()); // ignore late-bound regions - bounds.push(VerifyBound::AllBounds( - regions.into_iter().map(|r| VerifyBound::OutlivedBy(r)).collect(), - )); - - // remove bounds that must hold, since they are not interesting - bounds.retain(|b| !b.must_hold()); + fn recursive_bound(&self, parent: GenericArg<'tcx>) -> VerifyBound<'tcx> { + let mut bounds = parent + .walk_shallow() + .filter_map(|child| match child.unpack() { + GenericArgKind::Type(ty) => Some(self.type_bound(ty)), + GenericArgKind::Lifetime(lt) => { + // Ignore late-bound regions. + if !lt.is_late_bound() { Some(VerifyBound::OutlivedBy(lt)) } else { None } + } + GenericArgKind::Const(_) => Some(self.recursive_bound(child)), + }) + .filter(|bound| { + // Remove bounds that must hold, since they are not interesting. + !bound.must_hold() + }); - if bounds.len() == 1 { bounds.pop().unwrap() } else { VerifyBound::AllBounds(bounds) } + match (bounds.next(), bounds.next()) { + (Some(first), None) => first, + (first, second) => { + VerifyBound::AllBounds(first.into_iter().chain(second).chain(bounds).collect()) + } + } } /// Searches the environment for where-clauses like `G: 'a` where diff --git a/src/librustc_middle/ty/mod.rs b/src/librustc_middle/ty/mod.rs index ca3055c4c62..bc12b96164b 100644 --- a/src/librustc_middle/ty/mod.rs +++ b/src/librustc_middle/ty/mod.rs @@ -2701,13 +2701,6 @@ pub fn walk(&'tcx self) -> TypeWalker<'tcx> { TypeWalker::new(self.into()) } - /// Iterator that walks the immediate children of `self`. Hence - /// `Foo, u32>` yields the sequence `[Bar, u32]` - /// (but not `i32`, like `walk`). - pub fn walk_shallow(&'tcx self) -> impl Iterator> { - walk::walk_shallow(self.into()) - } - /// Walks `ty` and any types appearing within `ty`, invoking the /// callback `f` on each type. If the callback returns `false`, then the /// children of the current type are ignored. diff --git a/src/librustc_middle/ty/outlives.rs b/src/librustc_middle/ty/outlives.rs index 9dd96f2f2b5..950539fbb0a 100644 --- a/src/librustc_middle/ty/outlives.rs +++ b/src/librustc_middle/ty/outlives.rs @@ -2,6 +2,7 @@ // refers to rules defined in RFC 1214 (`OutlivesFooBar`), so see that // RFC for reference. +use crate::ty::subst::{GenericArg, GenericArgKind}; use crate::ty::{self, Ty, TyCtxt, TypeFoldable}; use smallvec::SmallVec; @@ -107,8 +108,9 @@ impl<'tcx> TyCtxt<'tcx> { // fallback case: hard code // OutlivesProjectionComponents. Continue walking // through and constrain Pi. - let subcomponents = capture_components(tcx, ty); - out.push(Component::EscapingProjection(subcomponents)); + let mut subcomponents = smallvec![]; + compute_components_recursive(tcx, ty.into(), &mut subcomponents); + out.push(Component::EscapingProjection(subcomponents.into_iter().collect())); } } @@ -153,26 +155,30 @@ impl<'tcx> TyCtxt<'tcx> { // "bound regions list". In our representation, no such // list is maintained explicitly, because bound regions // themselves can be readily identified. - - push_region_constraints(ty, out); - for subty in ty.walk_shallow() { - compute_components(tcx, subty, out); - } + compute_components_recursive(tcx, ty.into(), out); } } } -fn capture_components(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Vec> { - let mut temp = smallvec![]; - push_region_constraints(ty, &mut temp); - for subty in ty.walk_shallow() { - compute_components(tcx, subty, &mut temp); +fn compute_components_recursive( + tcx: TyCtxt<'tcx>, + parent: GenericArg<'tcx>, + out: &mut SmallVec<[Component<'tcx>; 4]>, +) { + for child in parent.walk_shallow() { + match child.unpack() { + GenericArgKind::Type(ty) => { + compute_components(tcx, ty, out); + } + GenericArgKind::Lifetime(lt) => { + // Ignore late-bound regions. + if !lt.is_late_bound() { + out.push(Component::Region(lt)); + } + } + GenericArgKind::Const(_) => { + compute_components_recursive(tcx, child, out); + } + } } - temp.into_iter().collect() -} - -fn push_region_constraints<'tcx>(ty: Ty<'tcx>, out: &mut SmallVec<[Component<'tcx>; 4]>) { - let mut regions = smallvec![]; - ty.push_regions(&mut regions); - out.extend(regions.iter().filter(|&r| !r.is_late_bound()).map(|r| Component::Region(r))); } diff --git a/src/librustc_middle/ty/sty.rs b/src/librustc_middle/ty/sty.rs index ef815aaab75..acbfdbafa17 100644 --- a/src/librustc_middle/ty/sty.rs +++ b/src/librustc_middle/ty/sty.rs @@ -25,7 +25,6 @@ use rustc_span::symbol::{kw, Symbol}; use rustc_target::abi::{Size, VariantIdx}; use rustc_target::spec::abi; -use smallvec::SmallVec; use std::borrow::Cow; use std::cmp::Ordering; use std::marker::PhantomData; @@ -2152,31 +2151,6 @@ pub fn discriminant_for_variant( } } - /// Pushes onto `out` the regions directly referenced from this type (but not - /// types reachable from this type via `walk_tys`). This ignores late-bound - /// regions binders. - pub fn push_regions(&self, out: &mut SmallVec<[ty::Region<'tcx>; 4]>) { - match self.kind { - Ref(region, _, _) => { - out.push(region); - } - Dynamic(ref obj, region) => { - out.push(region); - if let Some(principal) = obj.principal() { - out.extend(principal.skip_binder().substs.regions()); - } - } - Adt(_, substs) | Opaque(_, substs) => out.extend(substs.regions()), - Closure(_, ref substs) | Generator(_, ref substs, _) => out.extend(substs.regions()), - Projection(ref data) | UnnormalizedProjection(ref data) => { - out.extend(data.substs.regions()) - } - FnDef(..) | FnPtr(_) | GeneratorWitness(..) | Bool | Char | Int(_) | Uint(_) - | Float(_) | Str | Array(..) | Slice(_) | RawPtr(_) | Never | Tuple(..) - | Foreign(..) | Param(_) | Bound(..) | Placeholder(..) | Infer(_) | Error => {} - } - } - /// When we create a closure, we record its kind (i.e., what trait /// it implements) into its `ClosureSubsts` using a type /// parameter. This is kind of a phantom type, except that the diff --git a/src/librustc_middle/ty/walk.rs b/src/librustc_middle/ty/walk.rs index 8000f23bc78..5dfede37b58 100644 --- a/src/librustc_middle/ty/walk.rs +++ b/src/librustc_middle/ty/walk.rs @@ -57,16 +57,15 @@ fn next(&mut self) -> Option> { } } -pub fn walk_shallow(parent: GenericArg<'tcx>) -> impl Iterator> { - let mut stack = SmallVec::new(); - push_inner(&mut stack, parent); - stack.into_iter().filter_map(|child| { - // FIXME(eddyb) remove this filter and expose all `GenericArg`s. - match child.unpack() { - GenericArgKind::Type(ty) => Some(ty), - GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => None, - } - }) +impl GenericArg<'tcx> { + /// Iterator that walks the immediate children of `self`. Hence + /// `Foo, u32>` yields the sequence `[Bar, u32]` + /// (but not `i32`, like `walk`). + pub fn walk_shallow(self) -> impl Iterator> { + let mut stack = SmallVec::new(); + push_inner(&mut stack, self); + stack.into_iter() + } } // We push `GenericArg`s on the stack in reverse order so as to -- 2.44.0