ty: switch `Ty::walk` from `Ty` to `GenericArg`.

14 files changed, 301 insertions, 232 deletions

diff --git a/src/librustc_infer/infer/error_reporting/need_type_info.rs b/src/librustc_infer/infer/error_reporting/need_type_info.rs
index 7824855fe05..bb6e5700cca 100644
--- a/src/librustc_infer/infer/error_reporting/need_type_info.rs
+++ b/src/librustc_infer/infer/error_reporting/need_type_info.rs
@@ -7,52 +7,59 @@ use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor};
 use rustc_hir::{Body, Expr, ExprKind, FnRetTy, HirId, Local, Pat};
 use rustc_middle::hir::map::Map;
 use rustc_middle::ty::print::Print;
-use rustc_middle::ty::{self, DefIdTree, Infer, Ty, TyVar};
+use rustc_middle::ty::subst::{GenericArg, GenericArgKind};
+use rustc_middle::ty::{self, DefIdTree, Ty};
 use rustc_span::source_map::DesugaringKind;
 use rustc_span::symbol::kw;
 use rustc_span::Span;
 use std::borrow::Cow;
 
-struct FindLocalByTypeVisitor<'a, 'tcx> {
+struct FindHirNodeVisitor<'a, 'tcx> {
     infcx: &'a InferCtxt<'a, 'tcx>,
-    target_ty: Ty<'tcx>,
-    hir_map: Map<'tcx>,
+    target: GenericArg<'tcx>,
+    found_node_ty: Option<Ty<'tcx>>,
     found_local_pattern: Option<&'tcx Pat<'tcx>>,
     found_arg_pattern: Option<&'tcx Pat<'tcx>>,
-    found_ty: Option<Ty<'tcx>>,
-    found_closure: Option<&'tcx ExprKind<'tcx>>,
+    found_closure: Option<&'tcx Expr<'tcx>>,
     found_method_call: Option<&'tcx Expr<'tcx>>,
 }
 
-impl<'a, 'tcx> FindLocalByTypeVisitor<'a, 'tcx> {
-    fn new(infcx: &'a InferCtxt<'a, 'tcx>, target_ty: Ty<'tcx>, hir_map: Map<'tcx>) -> Self {
+impl<'a, 'tcx> FindHirNodeVisitor<'a, 'tcx> {
+    fn new(infcx: &'a InferCtxt<'a, 'tcx>, target: GenericArg<'tcx>) -> Self {
         Self {
             infcx,
-            target_ty,
-            hir_map,
+            target,
+            found_node_ty: None,
             found_local_pattern: None,
             found_arg_pattern: None,
-            found_ty: None,
             found_closure: None,
             found_method_call: None,
         }
     }
 
-    fn node_matches_type(&mut self, hir_id: HirId) -> Option<Ty<'tcx>> {
+    fn node_ty_contains_target(&mut self, hir_id: HirId) -> Option<Ty<'tcx>> {
         let ty_opt =
             self.infcx.in_progress_tables.and_then(|tables| tables.borrow().node_type_opt(hir_id));
         match ty_opt {
             Some(ty) => {
                 let ty = self.infcx.resolve_vars_if_possible(&ty);
-                if ty.walk().any(|inner_ty| {
-                    inner_ty == self.target_ty
-                        || match (&inner_ty.kind, &self.target_ty.kind) {
-                            (&Infer(TyVar(a_vid)), &Infer(TyVar(b_vid))) => self
-                                .infcx
-                                .inner
-                                .borrow_mut()
-                                .type_variables
-                                .sub_unified(a_vid, b_vid),
+                if ty.walk().any(|inner| {
+                    inner == self.target
+                        || match (inner.unpack(), self.target.unpack()) {
+                            (GenericArgKind::Type(inner_ty), GenericArgKind::Type(target_ty)) => {
+                                match (&inner_ty.kind, &target_ty.kind) {
+                                    (
+                                        &ty::Infer(ty::TyVar(a_vid)),
+                                        &ty::Infer(ty::TyVar(b_vid)),
+                                    ) => self
+                                        .infcx
+                                        .inner
+                                        .borrow_mut()
+                                        .type_variables
+                                        .sub_unified(a_vid, b_vid),
+                                    _ => false,
+                                }
+                            }
                             _ => false,
                         }
                 }) {
@@ -66,36 +73,39 @@ impl<'a, 'tcx> FindLocalByTypeVisitor<'a, 'tcx> {
     }
 }
 
-impl<'a, 'tcx> Visitor<'tcx> for FindLocalByTypeVisitor<'a, 'tcx> {
+impl<'a, 'tcx> Visitor<'tcx> for FindHirNodeVisitor<'a, 'tcx> {
     type Map = Map<'tcx>;
 
     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
-        NestedVisitorMap::OnlyBodies(self.hir_map)
+        NestedVisitorMap::OnlyBodies(self.infcx.tcx.hir())
     }
 
     fn visit_local(&mut self, local: &'tcx Local<'tcx>) {
-        if let (None, Some(ty)) = (self.found_local_pattern, self.node_matches_type(local.hir_id)) {
+        if let (None, Some(ty)) =
+            (self.found_local_pattern, self.node_ty_contains_target(local.hir_id))
+        {
             self.found_local_pattern = Some(&*local.pat);
-            self.found_ty = Some(ty);
+            self.found_node_ty = Some(ty);
         }
         intravisit::walk_local(self, local);
     }
 
     fn visit_body(&mut self, body: &'tcx Body<'tcx>) {
         for param in body.params {
-            if let (None, Some(ty)) = (self.found_arg_pattern, self.node_matches_type(param.hir_id))
+            if let (None, Some(ty)) =
+                (self.found_arg_pattern, self.node_ty_contains_target(param.hir_id))
             {
                 self.found_arg_pattern = Some(&*param.pat);
-                self.found_ty = Some(ty);
+                self.found_node_ty = Some(ty);
             }
         }
         intravisit::walk_body(self, body);
     }
 
     fn visit_expr(&mut self, expr: &'tcx Expr<'tcx>) {
-        if self.node_matches_type(expr.hir_id).is_some() {
+        if self.node_ty_contains_target(expr.hir_id).is_some() {
             match expr.kind {
-                ExprKind::Closure(..) => self.found_closure = Some(&expr.kind),
+                ExprKind::Closure(..) => self.found_closure = Some(&expr),
                 ExprKind::MethodCall(..) => self.found_method_call = Some(&expr),
                 _ => {}
             }
@@ -213,6 +223,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         (s, None, ty.prefix_string(), None, None)
     }
 
+    // FIXME(eddyb) generalize all of this to handle `ty::Const` inference variables as well.
     pub fn need_type_info_err(
         &self,
         body_id: Option<hir::BodyId>,
@@ -223,7 +234,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         let ty = self.resolve_vars_if_possible(&ty);
         let (name, name_sp, descr, parent_name, parent_descr) = self.extract_type_name(&ty, None);
 
-        let mut local_visitor = FindLocalByTypeVisitor::new(&self, ty, self.tcx.hir());
+        let mut local_visitor = FindHirNodeVisitor::new(&self, ty.into());
         let ty_to_string = |ty: Ty<'tcx>| -> String {
             let mut s = String::new();
             let mut printer = ty::print::FmtPrinter::new(self.tcx, &mut s, Namespace::TypeNS);
@@ -276,7 +287,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                 (!ty.is_impl_trait() || self.tcx.features().impl_trait_in_bindings)
         };
 
-        let ty_msg = match local_visitor.found_ty {
+        let ty_msg = match local_visitor.found_node_ty {
             Some(ty::TyS { kind: ty::Closure(_, substs), .. }) => {
                 let fn_sig = substs.as_closure().sig();
                 let args = closure_args(&fn_sig);
@@ -310,28 +321,32 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
             error_code,
         );
 
-        let suffix = match local_visitor.found_ty {
+        let suffix = match local_visitor.found_node_ty {
             Some(ty::TyS { kind: ty::Closure(_, substs), .. }) => {
                 let fn_sig = substs.as_closure().sig();
                 let ret = fn_sig.output().skip_binder().to_string();
 
-                if let Some(ExprKind::Closure(_, decl, body_id, ..)) = local_visitor.found_closure {
-                    if let Some(body) = self.tcx.hir().krate().bodies.get(body_id) {
-                        closure_return_type_suggestion(
-                            span,
-                            &mut err,
-                            &decl.output,
-                            &body,
-                            &descr,
-                            &name,
-                            &ret,
-                            parent_name,
-                            parent_descr,
-                        );
-                        // We don't want to give the other suggestions when the problem is the
-                        // closure return type.
-                        return err;
-                    }
+                let closure_decl_and_body_id =
+                    local_visitor.found_closure.and_then(|closure| match &closure.kind {
+                        ExprKind::Closure(_, decl, body_id, ..) => Some((decl, *body_id)),
+                        _ => None,
+                    });
+
+                if let Some((decl, body_id)) = closure_decl_and_body_id {
+                    closure_return_type_suggestion(
+                        span,
+                        &mut err,
+                        &decl.output,
+                        self.tcx.hir().body(body_id),
+                        &descr,
+                        &name,
+                        &ret,
+                        parent_name,
+                        parent_descr,
+                    );
+                    // We don't want to give the other suggestions when the problem is the
+                    // closure return type.
+                    return err;
                 }
 
                 // This shouldn't be reachable, but just in case we leave a reasonable fallback.
diff --git a/src/librustc_lint/builtin.rs b/src/librustc_lint/builtin.rs
index cff86e8f218..84cf2258ac2 100644
--- a/src/librustc_lint/builtin.rs
+++ b/src/librustc_lint/builtin.rs
@@ -36,6 +36,7 @@ use rustc_hir::def_id::DefId;
 use rustc_hir::{GenericParamKind, PatKind};
 use rustc_hir::{HirIdSet, Node};
 use rustc_middle::lint::LintDiagnosticBuilder;
+use rustc_middle::ty::subst::GenericArgKind;
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_session::lint::FutureIncompatibleInfo;
 use rustc_span::edition::Edition;
@@ -104,11 +105,13 @@ declare_lint_pass!(BoxPointers => [BOX_POINTERS]);
 
 impl BoxPointers {
     fn check_heap_type(&self, cx: &LateContext<'_, '_>, span: Span, ty: Ty<'_>) {
-        for leaf_ty in ty.walk() {
-            if leaf_ty.is_box() {
-                cx.struct_span_lint(BOX_POINTERS, span, |lint| {
-                    lint.build(&format!("type uses owned (Box type) pointers: {}", ty)).emit()
-                });
+        for leaf in ty.walk() {
+            if let GenericArgKind::Type(leaf_ty) = leaf.unpack() {
+                if leaf_ty.is_box() {
+                    cx.struct_span_lint(BOX_POINTERS, span, |lint| {
+                        lint.build(&format!("type uses owned (Box type) pointers: {}", ty)).emit()
+                    });
+                }
             }
         }
     }
diff --git a/src/librustc_middle/ty/mod.rs b/src/librustc_middle/ty/mod.rs
index bc12b96164b..79fa13b0b4a 100644
--- a/src/librustc_middle/ty/mod.rs
+++ b/src/librustc_middle/ty/mod.rs
@@ -19,7 +19,6 @@ use crate::traits::{self, Reveal};
 use crate::ty;
 use crate::ty::subst::{InternalSubsts, Subst, SubstsRef};
 use crate::ty::util::{Discr, IntTypeExt};
-use crate::ty::walk::TypeWalker;
 use rustc_ast::ast::{self, Ident, Name};
 use rustc_ast::node_id::{NodeId, NodeMap, NodeSet};
 use rustc_attr as attr;
@@ -2686,39 +2685,6 @@ impl<'tcx> ClosureKind {
     }
 }
 
-impl<'tcx> TyS<'tcx> {
-    /// Iterator that walks `self` and any types reachable from
-    /// `self`, in depth-first order. Note that just walks the types
-    /// that appear in `self`, it does not descend into the fields of
-    /// structs or variants. For example:
-    ///
-    /// ```notrust
-    /// isize => { isize }
-    /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
-    /// [isize] => { [isize], isize }
-    /// ```
-    pub fn walk(&'tcx self) -> TypeWalker<'tcx> {
-        TypeWalker::new(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.
-    ///
-    /// Note: prefer `ty.walk()` where possible.
-    pub fn maybe_walk<F>(&'tcx self, mut f: F)
-    where
-        F: FnMut(Ty<'tcx>) -> bool,
-    {
-        let mut walker = self.walk();
-        while let Some(ty) = walker.next() {
-            if !f(ty) {
-                walker.skip_current_subtree();
-            }
-        }
-    }
-}
-
 impl BorrowKind {
     pub fn from_mutbl(m: hir::Mutability) -> BorrowKind {
         match m {
diff --git a/src/librustc_middle/ty/walk.rs b/src/librustc_middle/ty/walk.rs
index 5dfede37b58..c7a317f39ad 100644
--- a/src/librustc_middle/ty/walk.rs
+++ b/src/librustc_middle/ty/walk.rs
@@ -1,8 +1,8 @@
 //! An iterator over the type substructure.
 //! WARNING: this does not keep track of the region depth.
 
+use crate::ty;
 use crate::ty::subst::{GenericArg, GenericArgKind};
-use crate::ty::{self, Ty};
 use smallvec::{self, SmallVec};
 
 // The TypeWalker's stack is hot enough that it's worth going to some effort to
@@ -37,27 +37,33 @@ impl<'tcx> TypeWalker<'tcx> {
 }
 
 impl<'tcx> Iterator for TypeWalker<'tcx> {
-    type Item = Ty<'tcx>;
+    type Item = GenericArg<'tcx>;
 
-    fn next(&mut self) -> Option<Ty<'tcx>> {
+    fn next(&mut self) -> Option<GenericArg<'tcx>> {
         debug!("next(): stack={:?}", self.stack);
-        while let Some(next) = self.stack.pop() {
-            self.last_subtree = self.stack.len();
-            push_inner(&mut self.stack, next);
-            debug!("next: stack={:?}", self.stack);
-
-            // FIXME(eddyb) remove this filter and expose all `GenericArg`s.
-            match next.unpack() {
-                GenericArgKind::Type(ty) => return Some(ty),
-                GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => {}
-            }
-        }
-
-        None
+        let next = self.stack.pop()?;
+        self.last_subtree = self.stack.len();
+        push_inner(&mut self.stack, next);
+        debug!("next: stack={:?}", self.stack);
+        Some(next)
     }
 }
 
 impl GenericArg<'tcx> {
+    /// Iterator that walks `self` and any types reachable from
+    /// `self`, in depth-first order. Note that just walks the types
+    /// that appear in `self`, it does not descend into the fields of
+    /// structs or variants. For example:
+    ///
+    /// ```notrust
+    /// isize => { isize }
+    /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
+    /// [isize] => { [isize], isize }
+    /// ```
+    pub fn walk(self) -> TypeWalker<'tcx> {
+        TypeWalker::new(self)
+    }
+
     /// Iterator that walks the immediate children of `self`. Hence
     /// `Foo<Bar<i32>, u32>` yields the sequence `[Bar<i32>, u32]`
     /// (but not `i32`, like `walk`).
@@ -68,6 +74,22 @@ impl GenericArg<'tcx> {
     }
 }
 
+impl<'tcx> super::TyS<'tcx> {
+    /// Iterator that walks `self` and any types reachable from
+    /// `self`, in depth-first order. Note that just walks the types
+    /// that appear in `self`, it does not descend into the fields of
+    /// structs or variants. For example:
+    ///
+    /// ```notrust
+    /// isize => { isize }
+    /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
+    /// [isize] => { [isize], isize }
+    /// ```
+    pub fn walk(&'tcx self) -> TypeWalker<'tcx> {
+        TypeWalker::new(self.into())
+    }
+}
+
 // We push `GenericArg`s on the stack in reverse order so as to
 // maintain a pre-order traversal. As of the time of this
 // writing, the fact that the traversal is pre-order is not
diff --git a/src/librustc_mir/monomorphize/collector.rs b/src/librustc_mir/monomorphize/collector.rs
index 1032ff413af..d8ceda96a25 100644
--- a/src/librustc_mir/monomorphize/collector.rs
+++ b/src/librustc_mir/monomorphize/collector.rs
@@ -191,7 +191,7 @@ use rustc_middle::mir::visit::Visitor as MirVisitor;
 use rustc_middle::mir::{self, Local, Location};
 use rustc_middle::ty::adjustment::{CustomCoerceUnsized, PointerCast};
 use rustc_middle::ty::print::obsolete::DefPathBasedNames;
-use rustc_middle::ty::subst::InternalSubsts;
+use rustc_middle::ty::subst::{GenericArgKind, InternalSubsts};
 use rustc_middle::ty::{self, GenericParamDefKind, Instance, Ty, TyCtxt, TypeFoldable};
 use rustc_session::config::EntryFnType;
 use smallvec::SmallVec;
@@ -442,9 +442,16 @@ fn check_recursion_limit<'tcx>(
 }
 
 fn check_type_length_limit<'tcx>(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>) {
-    let type_length = instance.substs.types().flat_map(|ty| ty.walk()).count();
-    let const_length = instance.substs.consts().flat_map(|ct| ct.ty.walk()).count();
-    debug!(" => type length={}, const length={}", type_length, const_length);
+    let type_length = instance
+        .substs
+        .iter()
+        .flat_map(|&arg| arg.walk())
+        .filter(|arg| match arg.unpack() {
+            GenericArgKind::Type(_) | GenericArgKind::Const(_) => true,
+            GenericArgKind::Lifetime(_) => false,
+        })
+        .count();
+    debug!(" => type length={}", type_length);
 
     // Rust code can easily create exponentially-long types using only a
     // polynomial recursion depth. Even with the default recursion
@@ -453,11 +460,7 @@ fn check_type_length_limit<'tcx>(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>) {
     //
     // Bail out in these cases to avoid that bad user experience.
     let type_length_limit = *tcx.sess.type_length_limit.get();
-    // We include the const length in the type length, as it's better
-    // to be overly conservative.
-    // FIXME(const_generics): we should instead uniformly walk through `substs`,
-    // ignoring lifetimes.
-    if type_length + const_length > type_length_limit {
+    if type_length > type_length_limit {
         // The instance name is already known to be too long for rustc.
         // Show only the first and last 32 characters to avoid blasting
         // the user's terminal with thousands of lines of type-name.
diff --git a/src/librustc_mir/transform/qualify_min_const_fn.rs b/src/librustc_mir/transform/qualify_min_const_fn.rs
index c5b366ef572..8f7a1b948e3 100644
--- a/src/librustc_mir/transform/qualify_min_const_fn.rs
+++ b/src/librustc_mir/transform/qualify_min_const_fn.rs
@@ -2,6 +2,7 @@ use rustc_attr as attr;
 use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
 use rustc_middle::mir::*;
+use rustc_middle::ty::subst::GenericArgKind;
 use rustc_middle::ty::{self, adjustment::PointerCast, Predicate, Ty, TyCtxt};
 use rustc_span::symbol::{sym, Symbol};
 use rustc_span::Span;
@@ -92,7 +93,15 @@ pub fn is_min_const_fn(tcx: TyCtxt<'tcx>, def_id: DefId, body: &'a Body<'tcx>) -
 }
 
 fn check_ty(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, span: Span, fn_def_id: DefId) -> McfResult {
-    for ty in ty.walk() {
+    for arg in ty.walk() {
+        let ty = match arg.unpack() {
+            GenericArgKind::Type(ty) => ty,
+
+            // No constraints on lifetimes or constants, except potentially
+            // constants' types, but `walk` will get to them as well.
+            GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => continue,
+        };
+
         match ty.kind {
             ty::Ref(_, _, hir::Mutability::Mut) => {
                 if !feature_allowed(tcx, fn_def_id, sym::const_mut_refs) {
diff --git a/src/librustc_trait_selection/traits/fulfill.rs b/src/librustc_trait_selection/traits/fulfill.rs
index 09a33120ba7..49a4b96f8b7 100644
--- a/src/librustc_trait_selection/traits/fulfill.rs
+++ b/src/librustc_trait_selection/traits/fulfill.rs
@@ -536,18 +536,17 @@ fn trait_ref_type_vars<'a, 'tcx>(
     selcx: &mut SelectionContext<'a, 'tcx>,
     trait_ref: ty::PolyTraitRef<'tcx>,
 ) -> Vec<TyOrConstInferVar<'tcx>> {
-    trait_ref
+    selcx
+        .infcx()
+        .resolve_vars_if_possible(&trait_ref)
         .skip_binder() // ok b/c this check doesn't care about regions
-        // FIXME(eddyb) walk over `GenericArg` to support const infer vars.
-        .input_types()
-        .map(|ty| selcx.infcx().resolve_vars_if_possible(&ty))
-        // FIXME(eddyb) try using `maybe_walk` to skip *all* subtrees that
-        // don't contain inference variables, not just the outermost level.
-        // FIXME(eddyb) use `has_infer_types_or_const`.
-        .filter(|ty| ty.has_infer_types())
-        .flat_map(|ty| ty.walk())
-        // FIXME(eddyb) use `TyOrConstInferVar::maybe_from_generic_arg`.
-        .filter_map(TyOrConstInferVar::maybe_from_ty)
+        .substs
+        .iter()
+        // FIXME(eddyb) try using `skip_current_subtree` to skip everything that
+        // doesn't contain inference variables, not just the outermost level.
+        .filter(|arg| arg.has_infer_types_or_consts())
+        .flat_map(|arg| arg.walk())
+        .filter_map(TyOrConstInferVar::maybe_from_generic_arg)
         .collect()
 }
 
diff --git a/src/librustc_trait_selection/traits/object_safety.rs b/src/librustc_trait_selection/traits/object_safety.rs
index 20b3fa908d2..fc2e984e34d 100644
--- a/src/librustc_trait_selection/traits/object_safety.rs
+++ b/src/librustc_trait_selection/traits/object_safety.rs
@@ -16,7 +16,7 @@ use crate::traits::{self, Obligation, ObligationCause};
 use rustc_errors::{Applicability, FatalError};
 use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
-use rustc_middle::ty::subst::{InternalSubsts, Subst};
+use rustc_middle::ty::subst::{GenericArgKind, InternalSubsts, Subst};
 use rustc_middle::ty::{self, Predicate, ToPredicate, Ty, TyCtxt, TypeFoldable, WithConstness};
 use rustc_session::lint::builtin::WHERE_CLAUSES_OBJECT_SAFETY;
 use rustc_span::symbol::Symbol;
@@ -234,7 +234,7 @@ fn predicates_reference_self(
         tcx.predicates_of(trait_def_id)
     };
     let self_ty = tcx.types.self_param;
-    let has_self_ty = |t: Ty<'_>| t.walk().any(|t| t == self_ty);
+    let has_self_ty = |t: Ty<'_>| t.walk().any(|arg| arg == self_ty.into());
     predicates
         .predicates
         .iter()
@@ -725,19 +725,17 @@ fn contains_illegal_self_type_reference<'tcx>(
     // without knowing what `Self` is.
 
     let mut supertraits: Option<Vec<ty::PolyTraitRef<'tcx>>> = None;
-    let mut error = false;
     let self_ty = tcx.types.self_param;
-    ty.maybe_walk(|ty| {
-        match ty.kind {
-            ty::Param(_) => {
-                if ty == self_ty {
-                    error = true;
-                }
 
-                false // no contained types to walk
-            }
+    let mut walker = ty.walk();
+    while let Some(arg) = walker.next() {
+        if arg == self_ty.into() {
+            return true;
+        }
 
-            ty::Projection(ref data) => {
+        // Special-case projections (everything else is walked normally).
+        if let GenericArgKind::Type(ty) = arg.unpack() {
+            if let ty::Projection(ref data) = ty.kind {
                 // This is a projected type `<Foo as SomeTrait>::X`.
 
                 // Compute supertraits of current trait lazily.
@@ -759,17 +757,18 @@ fn contains_illegal_self_type_reference<'tcx>(
                     supertraits.as_ref().unwrap().contains(&projection_trait_ref);
 
                 if is_supertrait_of_current_trait {
-                    false // do not walk contained types, do not report error, do collect $200
-                } else {
-                    true // DO walk contained types, POSSIBLY reporting an error
+                    // Do not walk contained types, do not report error, do collect $200.
+                    walker.skip_current_subtree();
                 }
-            }
 
-            _ => true, // walk contained types, if any
+                // DO walk contained types, POSSIBLY reporting an error.
+            }
         }
-    });
 
-    error
+        // Walk contained types, if any.
+    }
+
+    false
 }
 
 pub fn provide(providers: &mut ty::query::Providers<'_>) {
diff --git a/src/librustc_trait_selection/traits/select.rs b/src/librustc_trait_selection/traits/select.rs
index 3d95824cdf0..ed547cac582 100644
--- a/src/librustc_trait_selection/traits/select.rs
+++ b/src/librustc_trait_selection/traits/select.rs
@@ -44,7 +44,7 @@ use rustc_index::bit_set::GrowableBitSet;
 use rustc_middle::dep_graph::{DepKind, DepNodeIndex};
 use rustc_middle::ty::fast_reject;
 use rustc_middle::ty::relate::TypeRelation;
-use rustc_middle::ty::subst::{Subst, SubstsRef};
+use rustc_middle::ty::subst::{GenericArg, GenericArgKind, Subst, SubstsRef};
 use rustc_middle::ty::{
     self, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, TypeFoldable, WithConstness,
 };
@@ -1242,9 +1242,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         result: &SelectionResult<'tcx, SelectionCandidate<'tcx>>,
     ) -> bool {
         match result {
-            Ok(Some(SelectionCandidate::ParamCandidate(trait_ref))) => {
-                !trait_ref.skip_binder().input_types().any(|t| t.walk().any(|t_| t_.is_ty_infer()))
-            }
+            Ok(Some(SelectionCandidate::ParamCandidate(trait_ref))) => !trait_ref.has_local_value(),
             _ => true,
         }
     }
@@ -3048,20 +3046,31 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
             // `Struct<T>` -> `Struct<U>`
             (&ty::Adt(def, substs_a), &ty::Adt(_, substs_b)) => {
-                let fields =
-                    def.all_fields().map(|field| tcx.type_of(field.did)).collect::<Vec<_>>();
-
-                // The last field of the structure has to exist and contain type parameters.
-                let field = if let Some(&field) = fields.last() {
-                    field
-                } else {
-                    return Err(Unimplemented);
+                let maybe_unsizing_param_idx = |arg: GenericArg<'tcx>| match arg.unpack() {
+                    GenericArgKind::Type(ty) => match ty.kind {
+                        ty::Param(p) => Some(p.index),
+                        _ => None,
+                    },
+
+                    // Lifetimes aren't allowed to change during unsizing.
+                    GenericArgKind::Lifetime(_) => None,
+
+                    GenericArgKind::Const(ct) => match ct.val {
+                        ty::ConstKind::Param(p) => Some(p.index),
+                        _ => None,
+                    },
                 };
-                let mut ty_params = GrowableBitSet::new_empty();
+
+                // The last field of the structure has to exist and contain type/const parameters.
+                let (tail_field, prefix_fields) =
+                    def.non_enum_variant().fields.split_last().ok_or(Unimplemented)?;
+                let tail_field_ty = tcx.type_of(tail_field.did);
+
+                let mut unsizing_params = GrowableBitSet::new_empty();
                 let mut found = false;
-                for ty in field.walk() {
-                    if let ty::Param(p) = ty.kind {
-                        ty_params.insert(p.index as usize);
+                for arg in tail_field_ty.walk() {
+                    if let Some(i) = maybe_unsizing_param_idx(arg) {
+                        unsizing_params.insert(i);
                         found = true;
                     }
                 }
@@ -3069,31 +3078,31 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     return Err(Unimplemented);
                 }
 
-                // Replace type parameters used in unsizing with
-                // Error and ensure they do not affect any other fields.
-                // This could be checked after type collection for any struct
-                // with a potentially unsized trailing field.
-                let params = substs_a
-                    .iter()
-                    .enumerate()
-                    .map(|(i, &k)| if ty_params.contains(i) { tcx.types.err.into() } else { k });
-                let substs = tcx.mk_substs(params);
-                for &ty in fields.split_last().unwrap().1 {
-                    if ty.subst(tcx, substs).references_error() {
-                        return Err(Unimplemented);
+                // Ensure none of the other fields mention the parameters used
+                // in unsizing.
+                // FIXME(eddyb) cache this (including computing `unsizing_params`)
+                // by putting it in a query; it would only need the `DefId` as it
+                // looks at declared field types, not anything substituted.
+                for field in prefix_fields {
+                    for arg in tcx.type_of(field.did).walk() {
+                        if let Some(i) = maybe_unsizing_param_idx(arg) {
+                            if unsizing_params.contains(i) {
+                                return Err(Unimplemented);
+                            }
+                        }
                     }
                 }
 
-                // Extract `Field<T>` and `Field<U>` from `Struct<T>` and `Struct<U>`.
-                let inner_source = field.subst(tcx, substs_a);
-                let inner_target = field.subst(tcx, substs_b);
+                // Extract `TailField<T>` and `TailField<U>` from `Struct<T>` and `Struct<U>`.
+                let source_tail = tail_field_ty.subst(tcx, substs_a);
+                let target_tail = tail_field_ty.subst(tcx, substs_b);
 
                 // Check that the source struct with the target's
-                // unsized parameters is equal to the target.
-                let params = substs_a.iter().enumerate().map(|(i, &k)| {
-                    if ty_params.contains(i) { substs_b.type_at(i).into() } else { k }
-                });
-                let new_struct = tcx.mk_adt(def, tcx.mk_substs(params));
+                // unsizing parameters is equal to the target.
+                let substs = tcx.mk_substs(substs_a.iter().enumerate().map(|(i, &k)| {
+                    if unsizing_params.contains(i as u32) { substs_b[i] } else { k }
+                }));
+                let new_struct = tcx.mk_adt(def, substs);
                 let InferOk { obligations, .. } = self
                     .infcx
                     .at(&obligation.cause, obligation.param_env)
@@ -3101,15 +3110,15 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     .map_err(|_| Unimplemented)?;
                 nested.extend(obligations);
 
-                // Construct the nested `Field<T>: Unsize<Field<U>>` predicate.
+                // Construct the nested `TailField<T>: Unsize<TailField<U>>` predicate.
                 nested.push(predicate_for_trait_def(
                     tcx,
                     obligation.param_env,
                     obligation.cause.clone(),
                     obligation.predicate.def_id(),
                     obligation.recursion_depth + 1,
-                    inner_source,
-                    &[inner_target.into()],
+                    source_tail,
+                    &[target_tail.into()],
                 ));
             }
 
diff --git a/src/librustc_trait_selection/traits/wf.rs b/src/librustc_trait_selection/traits/wf.rs
index 1eb41e0b4d1..6b38749e1e7 100644
--- a/src/librustc_trait_selection/traits/wf.rs
+++ b/src/librustc_trait_selection/traits/wf.rs
@@ -4,7 +4,7 @@ use crate::traits::{self, AssocTypeBoundData};
 use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
 use rustc_hir::lang_items;
-use rustc_middle::ty::subst::SubstsRef;
+use rustc_middle::ty::subst::{GenericArgKind, SubstsRef};
 use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt, TypeFoldable, WithConstness};
 use rustc_span::symbol::{kw, Ident};
 use rustc_span::Span;
@@ -391,9 +391,21 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
     /// is WF. Returns false if `ty0` is an unresolved type variable,
     /// in which case we are not able to simplify at all.
     fn compute(&mut self, ty0: Ty<'tcx>) -> bool {
-        let mut subtys = ty0.walk();
+        let mut walker = ty0.walk();
         let param_env = self.param_env;
-        while let Some(ty) = subtys.next() {
+        while let Some(arg) = walker.next() {
+            let ty = match arg.unpack() {
+                GenericArgKind::Type(ty) => ty,
+
+                // No WF constraints for lifetimes being present, any outlives
+                // obligations are handled by the parent (e.g. `ty::Ref`).
+                GenericArgKind::Lifetime(_) => continue,
+
+                // FIXME(eddyb) this is wrong and needs to be replaced
+                // (see https://github.com/rust-lang/rust/pull/70107).
+                GenericArgKind::Const(_) => continue,
+            };
+
             match ty.kind {
                 ty::Bool
                 | ty::Char
@@ -417,6 +429,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
 
                 ty::Array(subty, len) => {
                     self.require_sized(subty, traits::SliceOrArrayElem);
+                    // FIXME(eddyb) handle `GenericArgKind::Const` above instead.
                     self.compute_array_len(*len);
                 }
 
@@ -433,7 +446,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                 }
 
                 ty::Projection(data) => {
-                    subtys.skip_current_subtree(); // subtree handled by compute_projection
+                    walker.skip_current_subtree(); // subtree handled by compute_projection
                     self.compute_projection(data);
                 }
 
@@ -504,7 +517,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
                     // are not directly inspecting closure types
                     // anyway, except via auto trait matching (which
                     // only inspects the upvar types).
-                    subtys.skip_current_subtree(); // subtree handled by compute_projection
+                    walker.skip_current_subtree(); // subtree handled by compute_projection
                     for upvar_ty in substs.as_closure().upvar_tys() {
                         self.compute(upvar_ty);
                     }
diff --git a/src/librustc_traits/lowering/environment.rs b/src/librustc_traits/lowering/environment.rs
index 28d5d25dd1b..612ab9b70eb 100644
--- a/src/librustc_traits/lowering/environment.rs
+++ b/src/librustc_traits/lowering/environment.rs
@@ -3,6 +3,7 @@ use rustc_hir::def_id::DefId;
 use rustc_middle::traits::{
     Clause, Clauses, DomainGoal, Environment, FromEnv, ProgramClause, ProgramClauseCategory,
 };
+use rustc_middle::ty::subst::GenericArgKind;
 use rustc_middle::ty::{self, Ty, TyCtxt};
 
 struct ClauseVisitor<'a, 'tcx> {
@@ -210,7 +211,8 @@ crate fn environment(tcx: TyCtxt<'_>, def_id: DefId) -> Environment<'_> {
         _ => NodeKind::Other,
     };
 
-    let mut input_tys = FxHashSet::default();
+    // FIXME(eddyb) isn't the unordered nature of this a hazard?
+    let mut inputs = FxHashSet::default();
 
     match node_kind {
         // In a trait impl, we assume that the header trait ref and all its
@@ -218,14 +220,14 @@ crate fn environment(tcx: TyCtxt<'_>, def_id: DefId) -> Environment<'_> {
         NodeKind::TraitImpl => {
             let trait_ref = tcx.impl_trait_ref(def_id).expect("not an impl");
 
-            input_tys.extend(trait_ref.input_types().flat_map(|ty| ty.walk()));
+            inputs.extend(trait_ref.substs.iter().flat_map(|&arg| arg.walk()));
         }
 
         // In an inherent impl, we assume that the receiver type and all its
         // constituents are well-formed.
         NodeKind::InherentImpl => {
             let self_ty = tcx.type_of(def_id);
-            input_tys.extend(self_ty.walk());
+            inputs.extend(self_ty.walk());
         }
 
         // In an fn, we assume that the arguments and all their constituents are
@@ -234,16 +236,27 @@ crate fn environment(tcx: TyCtxt<'_>, def_id: DefId) -> Environment<'_> {
             let fn_sig = tcx.fn_sig(def_id);
             let fn_sig = tcx.liberate_late_bound_regions(def_id, &fn_sig);
 
-            input_tys.extend(fn_sig.inputs().iter().flat_map(|ty| ty.walk()));
+            inputs.extend(fn_sig.inputs().iter().flat_map(|ty| ty.walk()));
         }
 
         NodeKind::Other => (),
     }
 
     let clauses = clauses.chain(
-        input_tys
+        inputs
             .into_iter()
-            .map(|ty| DomainGoal::FromEnv(FromEnv::Ty(ty)))
+            .filter_map(|arg| {
+                match arg.unpack() {
+                    GenericArgKind::Type(ty) => Some(FromEnv::Ty(ty)),
+
+                    // FIXME(eddyb) no WF conditions from lifetimes?
+                    GenericArgKind::Lifetime(_) => None,
+
+                    // FIXME(eddyb) support const generics in Chalk
+                    GenericArgKind::Const(_) => None,
+                }
+            })
+            .map(DomainGoal::FromEnv)
             .map(|domain_goal| domain_goal.into_program_clause())
             .map(Clause::Implies),
     );
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index c3ebcbfc832..ed7ec1c3b10 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -737,8 +737,9 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         let default_needs_object_self = |param: &ty::GenericParamDef| {
             if let GenericParamDefKind::Type { has_default, .. } = param.kind {
                 if is_object && has_default {
+                    let default_ty = tcx.at(span).type_of(param.def_id);
                     let self_param = tcx.types.self_param;
-                    if tcx.at(span).type_of(param.def_id).walk().any(|ty| ty == self_param) {
+                    if default_ty.walk().any(|arg| arg == self_param.into()) {
                         // There is no suitable inference default for a type parameter
                         // that references self, in an object type.
                         return true;
@@ -1617,7 +1618,8 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                     ty::Predicate::Projection(pred) => {
                         // A `Self` within the original bound will be substituted with a
                         // `trait_object_dummy_self`, so check for that.
-                        let references_self = pred.skip_binder().ty.walk().any(|t| t == dummy_self);
+                        let references_self =
+                            pred.skip_binder().ty.walk().any(|arg| arg == dummy_self.into());
 
                         // If the projection output contains `Self`, force the user to
                         // elaborate it explicitly to avoid a lot of complexity.
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 293c4feac62..eebc34d3db8 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -102,6 +102,7 @@ use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor};
 use rustc_hir::itemlikevisit::ItemLikeVisitor;
 use rustc_hir::lang_items;
 use rustc_hir::{ExprKind, GenericArg, HirIdMap, Item, ItemKind, Node, PatKind, QPath};
+use rustc_index::bit_set::BitSet;
 use rustc_index::vec::Idx;
 use rustc_infer::infer::canonical::{Canonical, OriginalQueryValues, QueryResponse};
 use rustc_infer::infer::error_reporting::TypeAnnotationNeeded::E0282;
@@ -1767,7 +1768,7 @@ pub fn check_item_type<'tcx>(tcx: TyCtxt<'tcx>, it: &'tcx hir::Item<'tcx>) {
             let def_id = tcx.hir().local_def_id(it.hir_id);
             let pty_ty = tcx.type_of(def_id);
             let generics = tcx.generics_of(def_id);
-            check_bounds_are_used(tcx, &generics, pty_ty);
+            check_type_params_are_used(tcx, &generics, pty_ty);
         }
         hir::ItemKind::ForeignMod(ref m) => {
             check_abi(tcx, it.span, m.abi);
@@ -4139,20 +4140,23 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                 // `FulfillmentError`.
                 let mut referenced_in = final_arg_types
                     .iter()
-                    .map(|(i, checked_ty, _)| (i, checked_ty))
-                    .chain(final_arg_types.iter().map(|(i, _, coerced_ty)| (i, coerced_ty)))
+                    .map(|&(i, checked_ty, _)| (i, checked_ty))
+                    .chain(final_arg_types.iter().map(|&(i, _, coerced_ty)| (i, coerced_ty)))
                     .flat_map(|(i, ty)| {
-                        let ty = self.resolve_vars_if_possible(ty);
+                        let ty = self.resolve_vars_if_possible(&ty);
                         // We walk the argument type because the argument's type could have
                         // been `Option<T>`, but the `FulfillmentError` references `T`.
-                        ty.walk()
-                            .filter(|&ty| ty == predicate.skip_binder().self_ty())
-                            .map(move |_| *i)
+                        if ty.walk().any(|arg| arg == predicate.skip_binder().self_ty().into()) {
+                            Some(i)
+                        } else {
+                            None
+                        }
                     })
                     .collect::<Vec<_>>();
 
                 // Both checked and coerced types could have matched, thus we need to remove
                 // duplicates.
+                referenced_in.sort();
                 referenced_in.dedup();
 
                 if let (Some(ref_in), None) = (referenced_in.pop(), referenced_in.pop()) {
@@ -5744,43 +5748,47 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     }
 }
 
-pub fn check_bounds_are_used<'tcx>(tcx: TyCtxt<'tcx>, generics: &ty::Generics, ty: Ty<'tcx>) {
-    let own_counts = generics.own_counts();
-    debug!(
-        "check_bounds_are_used(n_tys={}, n_cts={}, ty={:?})",
-        own_counts.types, own_counts.consts, ty
-    );
+fn check_type_params_are_used<'tcx>(tcx: TyCtxt<'tcx>, generics: &ty::Generics, ty: Ty<'tcx>) {
+    debug!("check_type_params_are_used(generics={:?}, ty={:?})", generics, ty);
+
+    assert_eq!(generics.parent, None);
 
-    if own_counts.types == 0 {
+    if generics.own_counts().types == 0 {
         return;
     }
 
-    // Make a vector of booleans initially `false`; set to `true` when used.
-    let mut types_used = vec![false; own_counts.types];
+    let mut params_used = BitSet::new_empty(generics.params.len());
 
-    for leaf_ty in ty.walk() {
-        if let ty::Param(ty::ParamTy { index, .. }) = leaf_ty.kind {
-            debug!("found use of ty param num {}", index);
-            types_used[index as usize - own_counts.lifetimes] = true;
-        } else if let ty::Error = leaf_ty.kind {
-            // If there is already another error, do not emit
-            // an error for not using a type parameter.
-            assert!(tcx.sess.has_errors());
-            return;
+    if ty.references_error() {
+        // If there is already another error, do not emit
+        // an error for not using a type parameter.
+        assert!(tcx.sess.has_errors());
+        return;
+    }
+
+    for leaf in ty.walk() {
+        if let GenericArgKind::Type(leaf_ty) = leaf.unpack() {
+            if let ty::Param(param) = leaf_ty.kind {
+                debug!("found use of ty param {:?}", param);
+                params_used.insert(param.index);
+            }
         }
     }
 
-    let types = generics.params.iter().filter(|param| match param.kind {
-        ty::GenericParamDefKind::Type { .. } => true,
-        _ => false,
-    });
-    for (&used, param) in types_used.iter().zip(types) {
-        if !used {
-            let id = tcx.hir().as_local_hir_id(param.def_id).unwrap();
-            let span = tcx.hir().span(id);
-            struct_span_err!(tcx.sess, span, E0091, "type parameter `{}` is unused", param.name)
+    for param in &generics.params {
+        if !params_used.contains(param.index) {
+            if let ty::GenericParamDefKind::Type { .. } = param.kind {
+                let span = tcx.def_span(param.def_id);
+                struct_span_err!(
+                    tcx.sess,
+                    span,
+                    E0091,
+                    "type parameter `{}` is unused",
+                    param.name,
+                )
                 .span_label(span, "unused type parameter")
                 .emit();
+            }
         }
     }
 }
diff --git a/src/librustc_typeck/outlives/implicit_infer.rs b/src/librustc_typeck/outlives/implicit_infer.rs
index df7c535ff3b..2abca302469 100644
--- a/src/librustc_typeck/outlives/implicit_infer.rs
+++ b/src/librustc_typeck/outlives/implicit_infer.rs
@@ -119,7 +119,15 @@ fn insert_required_predicates_to_be_wf<'tcx>(
     required_predicates: &mut RequiredPredicates<'tcx>,
     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
 ) {
-    for ty in field_ty.walk() {
+    for arg in field_ty.walk() {
+        let ty = match arg.unpack() {
+            GenericArgKind::Type(ty) => ty,
+
+            // No predicates from lifetimes or constants, except potentially
+            // constants' types, but `walk` will get to them as well.
+            GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => continue,
+        };
+
         match ty.kind {
             // The field is of type &'a T which means that we will have
             // a predicate requirement of T: 'a (T outlives 'a).
@@ -303,7 +311,7 @@ pub fn check_explicit_predicates<'tcx>(
         // 'b`.
         if let Some(self_ty) = ignored_self_ty {
             if let GenericArgKind::Type(ty) = outlives_predicate.0.unpack() {
-                if ty.walk().any(|ty| ty == self_ty) {
+                if ty.walk().any(|arg| arg == self_ty.into()) {
                     debug!("skipping self ty = {:?}", &ty);
                     continue;
                 }