Auto merge of #52731 - nikomatsakis:issue-52057-inference-variable, r=pnkfelix

Issue 52057 — inference variable

Break out the computation of universal region relations and do it during the typeck, where we can handle the resulting constraints that arise.

r? @pnkfelix

10 files changed, 565 insertions, 331 deletions

diff --git a/src/librustc/traits/query/type_op/custom.rs b/src/librustc/traits/query/type_op/custom.rs
index 3d10ce80585..cc752d21ab2 100644
--- a/src/librustc/traits/query/type_op/custom.rs
+++ b/src/librustc/traits/query/type_op/custom.rs
@@ -75,6 +75,19 @@ fn scrape_region_constraints<'gcx, 'tcx, R>(
 ) -> Fallible<(R, Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>)> {
     let mut fulfill_cx = TraitEngine::new(infcx.tcx);
     let dummy_body_id = ObligationCause::dummy().body_id;
+
+    // During NLL, we expect that nobody will register region
+    // obligations **except** as part of a custom type op (and, at the
+    // end of each custom type op, we scrape out the region
+    // obligations that resulted). So this vector should be empty on
+    // entry.
+    let pre_obligations = infcx.take_registered_region_obligations();
+    assert!(
+        pre_obligations.is_empty(),
+        "scrape_region_constraints: incoming region obligations = {:#?}",
+        pre_obligations,
+    );
+
     let InferOk { value, obligations } = infcx.commit_if_ok(|_| op())?;
     debug_assert!(obligations.iter().all(|o| o.cause.body_id == dummy_body_id));
     fulfill_cx.register_predicate_obligations(infcx, obligations);
diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs
index 63d5de4f2e5..973568a67f0 100644
--- a/src/librustc_mir/borrow_check/nll/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/mod.rs
@@ -104,12 +104,14 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
         None
     };
 
+    let universal_regions = Rc::new(universal_regions);
+
     let elements = &Rc::new(RegionValueElements::new(mir));
 
     // Run the MIR type-checker.
     let liveness_map = NllLivenessMap::compute(&mir);
     let liveness = LivenessResults::compute(mir, &liveness_map);
-    let constraint_sets = type_check::type_check(
+    let (constraint_sets, universal_region_relations) = type_check::type_check(
         infcx,
         param_env,
         mir,
@@ -153,6 +155,7 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>(
     let mut regioncx = RegionInferenceContext::new(
         var_origins,
         universal_regions,
+        universal_region_relations,
         mir,
         outlives_constraints,
         type_tests,
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/dump_mir.rs b/src/librustc_mir/borrow_check/nll/region_infer/dump_mir.rs
index 88b34c76732..d3b4f0a0447 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/dump_mir.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/dump_mir.rs
@@ -33,7 +33,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
                     .universal_regions
                     .region_classification(region)
                     .unwrap();
-                let outlived_by = self.universal_regions.regions_outlived_by(region);
+                let outlived_by = self.universal_region_relations.regions_outlived_by(region);
                 writeln!(
                     out,
                     "| {r:rw$} | {c:cw$} | {ob}",
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 19ff6d9a7e3..afd4e2859ac 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
@@ -14,6 +14,7 @@ use borrow_check::nll::constraints::{
     ConstraintIndex, ConstraintSccIndex, ConstraintSet, OutlivesConstraint,
 };
 use borrow_check::nll::region_infer::values::{RegionElement, ToElementIndex};
+use borrow_check::nll::type_check::free_region_relations::UniversalRegionRelations;
 use borrow_check::nll::type_check::Locations;
 use rustc::hir::def_id::DefId;
 use rustc::infer::canonical::QueryRegionConstraint;
@@ -80,8 +81,12 @@ pub struct RegionInferenceContext<'tcx> {
     type_tests: Vec<TypeTest<'tcx>>,
 
     /// Information about the universally quantified regions in scope
-    /// on this function and their (known) relations to one another.
+    /// on this function.
     universal_regions: Rc<UniversalRegions<'tcx>>,
+
+    /// Information about how the universally quantified regions in
+    /// scope on this function relate to one another.
+    universal_region_relations: Rc<UniversalRegionRelations<'tcx>>,
 }
 
 struct RegionDefinition<'tcx> {
@@ -206,15 +211,14 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     /// of constraints produced by the MIR type check.
     pub(crate) fn new(
         var_infos: VarInfos,
-        universal_regions: UniversalRegions<'tcx>,
+        universal_regions: Rc<UniversalRegions<'tcx>>,
+        universal_region_relations: Rc<UniversalRegionRelations<'tcx>>,
         _mir: &Mir<'tcx>,
         outlives_constraints: ConstraintSet,
         type_tests: Vec<TypeTest<'tcx>>,
         liveness_constraints: LivenessValues<RegionVid>,
         elements: &Rc<RegionValueElements>,
     ) -> Self {
-        let universal_regions = Rc::new(universal_regions);
-
         // Create a RegionDefinition for each inference variable.
         let definitions: IndexVec<_, _> = var_infos
             .into_iter()
@@ -251,6 +255,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             scc_values,
             type_tests,
             universal_regions,
+            universal_region_relations,
         };
 
         result.init_free_and_bound_regions();
@@ -308,8 +313,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         for (external_name, variable) in self.universal_regions.named_universal_regions() {
             debug!(
                 "init_universal_regions: region {:?} has external name {:?}",
-                variable,
-                external_name
+                variable, external_name
             );
             self.definitions[variable].external_name = Some(external_name);
         }
@@ -419,10 +423,20 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         };
 
         self.check_type_tests(
-            infcx, mir, mir_def_id, outlives_requirements.as_mut(), errors_buffer);
+            infcx,
+            mir,
+            mir_def_id,
+            outlives_requirements.as_mut(),
+            errors_buffer,
+        );
 
         self.check_universal_regions(
-            infcx, mir, mir_def_id, outlives_requirements.as_mut(), errors_buffer);
+            infcx,
+            mir,
+            mir_def_id,
+            outlives_requirements.as_mut(),
+            errors_buffer,
+        );
 
         let outlives_requirements = outlives_requirements.unwrap_or(vec![]);
 
@@ -581,13 +595,15 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             if let Some(lower_bound_region) = lower_bound_region {
                 let region_scope_tree = &tcx.region_scope_tree(mir_def_id);
                 let type_test_span = type_test.locations.span(mir);
-                infcx.construct_generic_bound_failure(
-                    region_scope_tree,
-                    type_test_span,
-                    None,
-                    type_test.generic_kind,
-                    lower_bound_region,
-                ).buffer(errors_buffer);
+                infcx
+                    .construct_generic_bound_failure(
+                        region_scope_tree,
+                        type_test_span,
+                        None,
+                        type_test.generic_kind,
+                        lower_bound_region,
+                    )
+                    .buffer(errors_buffer);
             } else {
                 // FIXME. We should handle this case better. It
                 // indicates that we have e.g. some region variable
@@ -599,10 +615,12 @@ impl<'tcx> RegionInferenceContext<'tcx> {
                 // iterating over the universal regions and reporting
                 // an error that multiple bounds are required.
                 let type_test_span = type_test.locations.span(mir);
-                tcx.sess.struct_span_err(
-                    type_test_span,
-                    &format!("`{}` does not live long enough", type_test.generic_kind,),
-                ).buffer(errors_buffer);
+                tcx.sess
+                    .struct_span_err(
+                        type_test_span,
+                        &format!("`{}` does not live long enough", type_test.generic_kind,),
+                    )
+                    .buffer(errors_buffer);
             }
         }
     }
@@ -654,8 +672,11 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         // region, which ensures it can be encoded in a `ClosureOutlivesRequirement`.
         let lower_bound_plus = self.non_local_universal_upper_bound(*lower_bound);
         assert!(self.universal_regions.is_universal_region(lower_bound_plus));
-        assert!(!self.universal_regions
-            .is_local_free_region(lower_bound_plus));
+        assert!(
+            !self
+                .universal_regions
+                .is_local_free_region(lower_bound_plus)
+        );
 
         propagated_outlives_requirements.push(ClosureOutlivesRequirement {
             subject,
@@ -768,7 +789,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
 
         // Grow further to get smallest universal region known to
         // creator.
-        let non_local_lub = self.universal_regions.non_local_upper_bound(lub);
+        let non_local_lub = self.universal_region_relations.non_local_upper_bound(lub);
 
         debug!(
             "non_local_universal_upper_bound: non_local_lub={:?}",
@@ -804,7 +825,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         let mut lub = self.universal_regions.fr_fn_body;
         let r_scc = self.constraint_sccs.scc(r);
         for ur in self.scc_values.universal_regions_outlived_by(r_scc) {
-            lub = self.universal_regions.postdom_upper_bound(lub, ur);
+            lub = self.universal_region_relations.postdom_upper_bound(lub, ur);
         }
 
         debug!("universal_upper_bound: r={:?} lub={:?}", r, lub);
@@ -872,7 +893,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             .all(|r1| {
                 self.scc_values
                     .universal_regions_outlived_by(sup_region_scc)
-                    .any(|r2| self.universal_regions.outlives(r2, r1))
+                    .any(|r2| self.universal_region_relations.outlives(r2, r1))
             });
 
         if !universal_outlives {
@@ -887,7 +908,8 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             return true;
         }
 
-        self.scc_values.contains_points(sup_region_scc, sub_region_scc)
+        self.scc_values
+            .contains_points(sup_region_scc, sub_region_scc)
     }
 
     /// Once regions have been propagated, this method is used to see
@@ -977,7 +999,10 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         // (because `fr` includes `end(o)`).
         for shorter_fr in self.scc_values.universal_regions_outlived_by(longer_fr_scc) {
             // If it is known that `fr: o`, carry on.
-            if self.universal_regions.outlives(longer_fr, shorter_fr) {
+            if self
+                .universal_region_relations
+                .outlives(longer_fr, shorter_fr)
+            {
                 continue;
             }
 
@@ -991,14 +1016,19 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             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_regions.non_local_lower_bound(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);
 
                     // 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`.
-                    let shorter_fr_plus = self.universal_regions.non_local_upper_bound(shorter_fr);
+                    let shorter_fr_plus = self
+                        .universal_region_relations
+                        .non_local_upper_bound(shorter_fr);
                     debug!(
                         "check_universal_region: shorter_fr_plus={:?}",
                         shorter_fr_plus
@@ -1021,8 +1051,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             // Note: in this case, we use the unapproximated regions
             // to report the error. This gives better error messages
             // in some cases.
-            self.report_error(
-                mir, infcx, mir_def_id, longer_fr, shorter_fr, errors_buffer);
+            self.report_error(mir, infcx, mir_def_id, longer_fr, shorter_fr, errors_buffer);
         }
     }
 
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
new file mode 100644
index 00000000000..e4b1aacd34f
--- /dev/null
+++ b/src/librustc_mir/borrow_check/nll/type_check/free_region_relations.rs
@@ -0,0 +1,361 @@
+// 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.
+
+use borrow_check::location::LocationTable;
+use borrow_check::nll::facts::AllFacts;
+use borrow_check::nll::type_check::constraint_conversion;
+use borrow_check::nll::type_check::{Locations, MirTypeckRegionConstraints};
+use borrow_check::nll::universal_regions::UniversalRegions;
+use borrow_check::nll::ToRegionVid;
+use rustc::hir::def_id::DefId;
+use rustc::infer::outlives::free_region_map::FreeRegionRelations;
+use rustc::infer::region_constraints::GenericKind;
+use rustc::infer::InferCtxt;
+use rustc::traits::query::outlives_bounds::{self, OutlivesBound};
+use rustc::traits::query::type_op::{self, TypeOp};
+use rustc::ty::{self, RegionVid, Ty};
+use rustc_data_structures::transitive_relation::TransitiveRelation;
+use std::rc::Rc;
+use syntax::ast;
+
+#[derive(Debug)]
+crate struct UniversalRegionRelations<'tcx> {
+    universal_regions: Rc<UniversalRegions<'tcx>>,
+
+    /// Stores the outlives relations that are known to hold from the
+    /// implied bounds, in-scope where clauses, and that sort of
+    /// thing.
+    outlives: TransitiveRelation<RegionVid>,
+
+    /// This is the `<=` relation; that is, if `a: b`, then `b <= a`,
+    /// and we store that here. This is useful when figuring out how
+    /// to express some local region in terms of external regions our
+    /// caller will understand.
+    inverse_outlives: TransitiveRelation<RegionVid>,
+}
+
+/// Each RBP `('a, GK)` indicates that `GK: 'a` can be assumed to
+/// be true. These encode relationships like `T: 'a` that are
+/// added via implicit bounds.
+///
+/// Each region here is guaranteed to be a key in the `indices`
+/// map.  We use the "original" regions (i.e., the keys from the
+/// map, and not the values) because the code in
+/// `process_registered_region_obligations` has some special-cased
+/// logic expecting to see (e.g.) `ReStatic`, and if we supplied
+/// our special inference variable there, we would mess that up.
+type RegionBoundPairs<'tcx> = Vec<(ty::Region<'tcx>, GenericKind<'tcx>)>;
+
+/// As part of computing the free region relations, we also have to
+/// normalize the input-output types, which we then need later. So we
+/// return those.  This vector consists of first the input types and
+/// then the output type as the last element.
+type NormalizedInputsAndOutput<'tcx> = Vec<Ty<'tcx>>;
+
+crate struct CreateResult<'tcx> {
+    crate universal_region_relations: Rc<UniversalRegionRelations<'tcx>>,
+    crate region_bound_pairs: RegionBoundPairs<'tcx>,
+    crate normalized_inputs_and_output: NormalizedInputsAndOutput<'tcx>,
+}
+
+crate fn create(
+    infcx: &InferCtxt<'_, '_, 'tcx>,
+    mir_def_id: DefId,
+    param_env: ty::ParamEnv<'tcx>,
+    location_table: &LocationTable,
+    implicit_region_bound: Option<ty::Region<'tcx>>,
+    universal_regions: &Rc<UniversalRegions<'tcx>>,
+    constraints: &mut MirTypeckRegionConstraints<'tcx>,
+    all_facts: &mut Option<AllFacts>,
+) -> CreateResult<'tcx> {
+    let mir_node_id = infcx.tcx.hir.as_local_node_id(mir_def_id).unwrap();
+    UniversalRegionRelationsBuilder {
+        infcx,
+        mir_def_id,
+        mir_node_id,
+        param_env,
+        implicit_region_bound,
+        constraints,
+        location_table,
+        all_facts,
+        universal_regions: universal_regions.clone(),
+        region_bound_pairs: Vec::new(),
+        relations: UniversalRegionRelations {
+            universal_regions: universal_regions.clone(),
+            outlives: TransitiveRelation::new(),
+            inverse_outlives: TransitiveRelation::new(),
+        },
+    }.create()
+}
+
+impl UniversalRegionRelations<'tcx> {
+    /// Records in the `outlives_relation` (and
+    /// `inverse_outlives_relation`) that `fr_a: fr_b`. Invoked by the
+    /// builder below.
+    fn relate_universal_regions(&mut self, fr_a: RegionVid, fr_b: RegionVid) {
+        debug!(
+            "relate_universal_regions: fr_a={:?} outlives fr_b={:?}",
+            fr_a, fr_b
+        );
+        self.outlives.add(fr_a, fr_b);
+        self.inverse_outlives.add(fr_b, fr_a);
+    }
+
+    /// Given two universal regions, returns the postdominating
+    /// upper-bound (effectively the least upper bound).
+    ///
+    /// (See `TransitiveRelation::postdom_upper_bound` for details on
+    /// the postdominating upper bound in general.)
+    crate fn postdom_upper_bound(&self, fr1: RegionVid, fr2: RegionVid) -> RegionVid {
+        assert!(self.universal_regions.is_universal_region(fr1));
+        assert!(self.universal_regions.is_universal_region(fr2));
+        *self
+            .inverse_outlives
+            .postdom_upper_bound(&fr1, &fr2)
+            .unwrap_or(&self.universal_regions.fr_static)
+    }
+
+    /// 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.
+    ///
+    /// (*) 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 {
+        debug!("non_local_upper_bound(fr={:?})", fr);
+        self.non_local_bound(&self.inverse_outlives, fr)
+            .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.
+    ///
+    /// (*) 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<RegionVid> {
+        debug!("non_local_lower_bound(fr={:?})", fr);
+        self.non_local_bound(&self.outlives, fr)
+    }
+
+    /// 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(
+        &self,
+        relation: &TransitiveRelation<RegionVid>,
+        fr0: RegionVid,
+    ) -> Option<RegionVid> {
+        // This method assumes that `fr0` is one of the universally
+        // quantified region variables.
+        assert!(self.universal_regions.is_universal_region(fr0));
+
+        let mut external_parents = vec![];
+        let mut queue = vec![&fr0];
+
+        // Keep expanding `fr` into its parents until we reach
+        // non-local regions.
+        while let Some(fr) = queue.pop() {
+            if !self.universal_regions.is_local_free_region(*fr) {
+                external_parents.push(fr);
+                continue;
+            }
+
+            queue.extend(relation.parents(fr));
+        }
+
+        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
+            }
+        })
+    }
+
+    /// True if fr1 is known to outlive fr2.
+    ///
+    /// This will only ever be true for universally quantified regions.
+    crate fn outlives(&self, fr1: RegionVid, fr2: RegionVid) -> bool {
+        self.outlives.contains(&fr1, &fr2)
+    }
+
+    /// Returns a vector of free regions `x` such that `fr1: x` is
+    /// known to hold.
+    crate fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<&RegionVid> {
+        self.outlives.reachable_from(&fr1)
+    }
+}
+
+struct UniversalRegionRelationsBuilder<'this, 'gcx: 'tcx, 'tcx: 'this> {
+    infcx: &'this InferCtxt<'this, 'gcx, 'tcx>,
+    mir_def_id: DefId,
+    mir_node_id: ast::NodeId,
+    param_env: ty::ParamEnv<'tcx>,
+    location_table: &'this LocationTable,
+    universal_regions: Rc<UniversalRegions<'tcx>>,
+    implicit_region_bound: Option<ty::Region<'tcx>>,
+    constraints: &'this mut MirTypeckRegionConstraints<'tcx>,
+    all_facts: &'this mut Option<AllFacts>,
+
+    // outputs:
+    relations: UniversalRegionRelations<'tcx>,
+    region_bound_pairs: RegionBoundPairs<'tcx>,
+}
+
+impl UniversalRegionRelationsBuilder<'cx, 'gcx, 'tcx> {
+    crate fn create(mut self) -> CreateResult<'tcx> {
+        let unnormalized_input_output_tys = self
+            .universal_regions
+            .unnormalized_input_tys
+            .iter()
+            .cloned()
+            .chain(Some(self.universal_regions.unnormalized_output_ty));
+
+        // For each of the input/output types:
+        // - Normalize the type. This will create some region
+        //   constraints, which we buffer up because we are
+        //   not ready to process them yet.
+        // - Then compute the implied bounds. This will adjust
+        //   the `region_bound_pairs` and so forth.
+        // - After this is done, we'll process the constraints, once
+        //   the `relations` is built.
+        let mut normalized_inputs_and_output =
+            Vec::with_capacity(self.universal_regions.unnormalized_input_tys.len() + 1);
+        let constraint_sets: Vec<_> = unnormalized_input_output_tys
+            .flat_map(|ty| {
+                debug!("build: input_or_output={:?}", ty);
+                let (ty, constraints) = self
+                    .param_env
+                    .and(type_op::normalize::Normalize::new(ty))
+                    .fully_perform(self.infcx)
+                    .unwrap_or_else(|_| bug!("failed to normalize {:?}", ty));
+                self.add_implied_bounds(ty);
+                normalized_inputs_and_output.push(ty);
+                constraints
+            })
+            .collect();
+
+        // Insert the facts we know from the predicates. Why? Why not.
+        let param_env = self.param_env;
+        self.add_outlives_bounds(outlives_bounds::explicit_outlives_bounds(param_env));
+
+        // Finally:
+        // - outlives is reflexive, so `'r: 'r` for every region `'r`
+        // - `'static: 'r` for every region `'r`
+        // - `'r: 'fn_body` for every (other) universally quantified
+        //   region `'r`, all of which are provided by our caller
+        let fr_static = self.universal_regions.fr_static;
+        let fr_fn_body = self.universal_regions.fr_fn_body;
+        for fr in self.universal_regions.universal_regions() {
+            debug!(
+                "build: relating free region {:?} to itself and to 'static",
+                fr
+            );
+            self.relations.relate_universal_regions(fr, fr);
+            self.relations.relate_universal_regions(fr_static, fr);
+            self.relations.relate_universal_regions(fr, fr_fn_body);
+        }
+
+        for data in constraint_sets {
+            constraint_conversion::ConstraintConversion::new(
+                self.infcx.tcx,
+                &self.universal_regions,
+                &self.location_table,
+                &self.region_bound_pairs,
+                self.implicit_region_bound,
+                self.param_env,
+                Locations::All,
+                &mut self.constraints.outlives_constraints,
+                &mut self.constraints.type_tests,
+                &mut self.all_facts,
+            ).convert_all(&data);
+        }
+
+        CreateResult {
+            universal_region_relations: Rc::new(self.relations),
+            region_bound_pairs: self.region_bound_pairs,
+            normalized_inputs_and_output,
+        }
+    }
+
+    /// Update the type of a single local, which should represent
+    /// either the return type of the MIR or one of its arguments. At
+    /// the same time, compute and add any implied bounds that come
+    /// from this local.
+    fn add_implied_bounds(&mut self, ty: Ty<'tcx>) {
+        debug!("add_implied_bounds(ty={:?})", ty);
+        let span = self.infcx.tcx.def_span(self.mir_def_id);
+        let bounds = self
+            .infcx
+            .implied_outlives_bounds(self.param_env, self.mir_node_id, ty, span);
+        self.add_outlives_bounds(bounds);
+    }
+
+    /// Registers the `OutlivesBound` items from `outlives_bounds` in
+    /// the outlives relation as well as the region-bound pairs
+    /// listing.
+    fn add_outlives_bounds<I>(&mut self, outlives_bounds: I)
+    where
+        I: IntoIterator<Item = OutlivesBound<'tcx>>,
+    {
+        for outlives_bound in outlives_bounds {
+            debug!("add_outlives_bounds(bound={:?})", outlives_bound);
+
+            match outlives_bound {
+                OutlivesBound::RegionSubRegion(r1, r2) => {
+                    // The bound says that `r1 <= r2`; we store `r2: r1`.
+                    let r1 = self.universal_regions.to_region_vid(r1);
+                    let r2 = self.universal_regions.to_region_vid(r2);
+                    self.relations.relate_universal_regions(r2, r1);
+                }
+
+                OutlivesBound::RegionSubParam(r_a, param_b) => {
+                    self.region_bound_pairs
+                        .push((r_a, GenericKind::Param(param_b)));
+                }
+
+                OutlivesBound::RegionSubProjection(r_a, projection_b) => {
+                    self.region_bound_pairs
+                        .push((r_a, GenericKind::Projection(projection_b)));
+                }
+            }
+        }
+    }
+}
+
+/// This trait is used by the `impl-trait` constraint code to abstract
+/// over the `FreeRegionMap` from lexical regions and
+/// `UniversalRegions` (from NLL)`.
+impl<'tcx> FreeRegionRelations<'tcx> for UniversalRegionRelations<'tcx> {
+    fn sub_free_regions(&self, shorter: ty::Region<'tcx>, longer: ty::Region<'tcx>) -> bool {
+        let shorter = shorter.to_region_vid();
+        assert!(self.universal_regions.is_universal_region(shorter));
+        let longer = longer.to_region_vid();
+        assert!(self.universal_regions.is_universal_region(longer));
+        self.outlives(longer, shorter)
+    }
+}
diff --git a/src/librustc_mir/borrow_check/nll/type_check/input_output.rs b/src/librustc_mir/borrow_check/nll/type_check/input_output.rs
index ea0dc200b7d..af426670167 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/input_output.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/input_output.rs
@@ -18,6 +18,7 @@
 //! contain revealed `impl Trait` values).
 
 use borrow_check::nll::renumber;
+use borrow_check::nll::type_check::free_region_relations::UniversalRegionRelations;
 use borrow_check::nll::universal_regions::UniversalRegions;
 use rustc::hir::def_id::DefId;
 use rustc::infer::InferOk;
@@ -37,22 +38,25 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
         mir: &Mir<'tcx>,
         mir_def_id: DefId,
         universal_regions: &UniversalRegions<'tcx>,
+        universal_region_relations: &UniversalRegionRelations<'tcx>,
+        normalized_inputs_and_output: &[Ty<'tcx>],
     ) {
         let tcx = self.infcx.tcx;
 
-        let &UniversalRegions {
-            unnormalized_output_ty,
-            unnormalized_input_tys,
-            ..
-        } = universal_regions;
+        let (&normalized_output_ty, normalized_input_tys) =
+            normalized_inputs_and_output.split_last().unwrap();
         let infcx = self.infcx;
 
         // Equate expected input tys with those in the MIR.
         let argument_locals = (1..).map(Local::new);
-        for (&unnormalized_input_ty, local) in unnormalized_input_tys.iter().zip(argument_locals) {
-            let input_ty = self.normalize(unnormalized_input_ty, Locations::All);
+        for (&normalized_input_ty, local) in normalized_input_tys.iter().zip(argument_locals) {
+            debug!(
+                "equate_inputs_and_outputs: normalized_input_ty = {:?}",
+                normalized_input_ty
+            );
+
             let mir_input_ty = mir.local_decls[local].ty;
-            self.equate_normalized_input_or_output(input_ty, mir_input_ty);
+            self.equate_normalized_input_or_output(normalized_input_ty, mir_input_ty);
         }
 
         assert!(
@@ -66,15 +70,6 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
 
         // Return types are a bit more complex. They may contain existential `impl Trait`
         // types.
-        debug!(
-            "equate_inputs_and_outputs: unnormalized_output_ty={:?}",
-            unnormalized_output_ty
-        );
-        let output_ty = self.normalize(unnormalized_output_ty, Locations::All);
-        debug!(
-            "equate_inputs_and_outputs: normalized output_ty={:?}",
-            output_ty
-        );
         let param_env = self.param_env;
         let mir_output_ty = mir.local_decls[RETURN_PLACE].ty;
         let anon_type_map =
@@ -90,7 +85,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
                                 mir_def_id,
                                 dummy_body_id,
                                 param_env,
-                                &output_ty,
+                                &normalized_output_ty,
                             ));
                         debug!(
                             "equate_inputs_and_outputs: instantiated output_ty={:?}",
@@ -144,7 +139,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
                     self,
                     Location::START,
                     "equate_inputs_and_outputs: `{:?}=={:?}` failed with `{:?}`",
-                    output_ty,
+                    normalized_output_ty,
                     mir_output_ty,
                     terr
                 );
@@ -160,7 +155,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
                 Locations::All,
                 CustomTypeOp::new(
                     |_cx| {
-                        infcx.constrain_anon_types(&anon_type_map, universal_regions);
+                        infcx.constrain_anon_types(&anon_type_map, universal_region_relations);
                         Ok(InferOk {
                             value: (),
                             obligations: vec![],
diff --git a/src/librustc_mir/borrow_check/nll/type_check/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
index b67de34593f..a18e2368bf7 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
@@ -17,9 +17,10 @@ use borrow_check::nll::constraints::{ConstraintSet, OutlivesConstraint};
 use borrow_check::nll::facts::AllFacts;
 use borrow_check::nll::region_infer::values::{RegionValueElements, LivenessValues};
 use borrow_check::nll::region_infer::{ClosureRegionRequirementsExt, TypeTest};
+use borrow_check::nll::type_check::free_region_relations::{CreateResult, UniversalRegionRelations};
 use borrow_check::nll::universal_regions::UniversalRegions;
-use borrow_check::nll::ToRegionVid;
 use borrow_check::nll::LocalWithRegion;
+use borrow_check::nll::ToRegionVid;
 use dataflow::move_paths::MoveData;
 use dataflow::FlowAtLocation;
 use dataflow::MaybeInitializedPlaces;
@@ -36,12 +37,12 @@ use rustc::traits::query::type_op;
 use rustc::traits::query::{Fallible, NoSolution};
 use rustc::ty::fold::TypeFoldable;
 use rustc::ty::{self, CanonicalTy, RegionVid, ToPolyTraitRef, Ty, TyCtxt, TypeVariants};
+use rustc_errors::Diagnostic;
 use std::fmt;
 use std::rc::Rc;
 use syntax_pos::{Span, DUMMY_SP};
 use transform::{MirPass, MirSource};
 use util::liveness::LivenessResults;
-use rustc_errors::Diagnostic;
 
 use rustc_data_structures::fx::FxHashSet;
 use rustc_data_structures::indexed_vec::Idx;
@@ -71,6 +72,7 @@ macro_rules! span_mirbug_and_err {
 }
 
 mod constraint_conversion;
+pub mod free_region_relations;
 mod input_output;
 mod liveness;
 mod relate_tys;
@@ -110,7 +112,7 @@ pub(crate) fn type_check<'gcx, 'tcx>(
     param_env: ty::ParamEnv<'gcx>,
     mir: &Mir<'tcx>,
     mir_def_id: DefId,
-    universal_regions: &UniversalRegions<'tcx>,
+    universal_regions: &Rc<UniversalRegions<'tcx>>,
     location_table: &LocationTable,
     borrow_set: &BorrowSet<'tcx>,
     liveness: &LivenessResults<LocalWithRegion>,
@@ -119,7 +121,10 @@ pub(crate) fn type_check<'gcx, 'tcx>(
     move_data: &MoveData<'tcx>,
     elements: &Rc<RegionValueElements>,
     errors_buffer: &mut Vec<Diagnostic>,
-) -> MirTypeckRegionConstraints<'tcx> {
+) -> (
+    MirTypeckRegionConstraints<'tcx>,
+    Rc<UniversalRegionRelations<'tcx>>,
+) {
     let implicit_region_bound = infcx.tcx.mk_region(ty::ReVar(universal_regions.fr_fn_body));
     let mut constraints = MirTypeckRegionConstraints {
         liveness_constraints: LivenessValues::new(elements),
@@ -127,6 +132,21 @@ pub(crate) fn type_check<'gcx, 'tcx>(
         type_tests: Vec::default(),
     };
 
+    let CreateResult {
+        universal_region_relations,
+        region_bound_pairs,
+        normalized_inputs_and_output,
+    } = free_region_relations::create(
+        infcx,
+        mir_def_id,
+        param_env,
+        location_table,
+        Some(implicit_region_bound),
+        universal_regions,
+        &mut constraints,
+        all_facts,
+    );
+
     {
         let mut borrowck_context = BorrowCheckContext {
             universal_regions,
@@ -141,17 +161,24 @@ pub(crate) fn type_check<'gcx, 'tcx>(
             mir_def_id,
             param_env,
             mir,
-            &universal_regions.region_bound_pairs,
+            &region_bound_pairs,
             Some(implicit_region_bound),
             Some(&mut borrowck_context),
             Some(errors_buffer),
             |cx| {
                 liveness::generate(cx, mir, liveness, flow_inits, move_data);
-                cx.equate_inputs_and_outputs(mir, mir_def_id, universal_regions);
+                cx.equate_inputs_and_outputs(
+                    mir,
+                    mir_def_id,
+                    universal_regions,
+                    &universal_region_relations,
+                    &normalized_inputs_and_output,
+                );
             },
         );
     }
-    constraints
+
+    (constraints, universal_region_relations)
 }
 
 fn type_check_internal<'a, 'gcx, 'tcx, F>(
@@ -164,8 +191,8 @@ fn type_check_internal<'a, 'gcx, 'tcx, F>(
     borrowck_context: Option<&'a mut BorrowCheckContext<'a, 'tcx>>,
     errors_buffer: Option<&mut Vec<Diagnostic>>,
     mut extra: F,
-)
-    where F: FnMut(&mut TypeChecker<'a, 'gcx, 'tcx>)
+) where
+    F: FnMut(&mut TypeChecker<'a, 'gcx, 'tcx>),
 {
     let mut checker = TypeChecker::new(
         infcx,
@@ -307,8 +334,7 @@ impl<'a, 'b, 'gcx, 'tcx> TypeVerifier<'a, 'b, 'gcx, 'tcx> {
             // don't have a handy function for that, so for
             // now we just ignore `value.val` regions.
 
-            let instantiated_predicates =
-                tcx.predicates_of(def_id).instantiate(tcx, substs);
+            let instantiated_predicates = tcx.predicates_of(def_id).instantiate(tcx, substs);
             type_checker.normalize_and_prove_instantiated_predicates(
                 instantiated_predicates,
                 location.boring(),
@@ -1023,9 +1049,11 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
                 // all the inputs that fed into it were live.
                 for &late_bound_region in map.values() {
                     if let Some(ref mut borrowck_context) = self.borrowck_context {
-                        let region_vid = borrowck_context.universal_regions.to_region_vid(
-                            late_bound_region);
-                        borrowck_context.constraints
+                        let region_vid = borrowck_context
+                            .universal_regions
+                            .to_region_vid(late_bound_region);
+                        borrowck_context
+                            .constraints
                             .liveness_constraints
                             .add_element(region_vid, term_location);
                     }
@@ -1241,12 +1269,13 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
         }
     }
 
-    fn check_local(&mut self,
-                   mir: &Mir<'tcx>,
-                   local: Local,
-                   local_decl: &LocalDecl<'tcx>,
-                   errors_buffer: &mut Option<&mut Vec<Diagnostic>>)
-    {
+    fn check_local(
+        &mut self,
+        mir: &Mir<'tcx>,
+        local: Local,
+        local_decl: &LocalDecl<'tcx>,
+        errors_buffer: &mut Option<&mut Vec<Diagnostic>>,
+    ) {
         match mir.local_kind(local) {
             LocalKind::ReturnPointer | LocalKind::Arg => {
                 // return values of normal functions are required to be
@@ -1274,12 +1303,14 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
             // slot or local, so to find all unsized rvalues it is enough
             // to check all temps, return slots and locals.
             if let None = self.reported_errors.replace((ty, span)) {
-                let mut diag = struct_span_err!(self.tcx().sess,
-                                                span,
-                                                E0161,
-                                                "cannot move a value of type {0}: the size of {0} \
-                                                 cannot be statically determined",
-                                                ty);
+                let mut diag = struct_span_err!(
+                    self.tcx().sess,
+                    span,
+                    E0161,
+                    "cannot move a value of type {0}: the size of {0} \
+                     cannot be statically determined",
+                    ty
+                );
                 if let Some(ref mut errors_buffer) = *errors_buffer {
                     diag.buffer(errors_buffer);
                 } else {
@@ -1577,13 +1608,11 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
                     debug!("add_reborrow_constraint - base_ty = {:?}", base_ty);
                     match base_ty.sty {
                         ty::TyRef(ref_region, _, mutbl) => {
-                            constraints
-                                .outlives_constraints
-                                .push(OutlivesConstraint {
-                                    sup: ref_region.to_region_vid(),
-                                    sub: borrow_region.to_region_vid(),
-                                    locations: location.boring(),
-                                });
+                            constraints.outlives_constraints.push(OutlivesConstraint {
+                                sup: ref_region.to_region_vid(),
+                                sub: borrow_region.to_region_vid(),
+                                locations: location.boring(),
+                            });
 
                             if let Some(all_facts) = all_facts {
                                 all_facts.outlives.push((
@@ -1768,10 +1797,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
         })
     }
 
-    fn typeck_mir(&mut self,
-                  mir: &Mir<'tcx>,
-                  mut errors_buffer: Option<&mut Vec<Diagnostic>>)
-    {
+    fn typeck_mir(&mut self, mir: &Mir<'tcx>, mut errors_buffer: Option<&mut Vec<Diagnostic>>) {
         self.last_span = mir.span;
         debug!("run_on_mir: {:?}", mir.span);
 
@@ -1841,7 +1867,17 @@ impl MirPass for TypeckMir {
 
         let param_env = tcx.param_env(def_id);
         tcx.infer_ctxt().enter(|infcx| {
-            type_check_internal(&infcx, def_id, param_env, mir, &[], None, None, None, |_| ());
+            type_check_internal(
+                &infcx,
+                def_id,
+                param_env,
+                mir,
+                &[],
+                None,
+                None,
+                None,
+                |_| (),
+            );
 
             // For verification purposes, we just ignore the resulting
             // region constraint sets. Not our problem. =)
diff --git a/src/librustc_mir/borrow_check/nll/universal_regions.rs b/src/librustc_mir/borrow_check/nll/universal_regions.rs
index 9bb7d123133..765c4cf906e 100644
--- a/src/librustc_mir/borrow_check/nll/universal_regions.rs
+++ b/src/librustc_mir/borrow_check/nll/universal_regions.rs
@@ -25,16 +25,12 @@
 use either::Either;
 use rustc::hir::def_id::DefId;
 use rustc::hir::{self, BodyOwnerKind, HirId};
-use rustc::infer::outlives::free_region_map::FreeRegionRelations;
-use rustc::infer::region_constraints::GenericKind;
 use rustc::infer::{InferCtxt, NLLRegionVariableOrigin};
-use rustc::traits::query::outlives_bounds::{self, OutlivesBound};
 use rustc::ty::fold::TypeFoldable;
 use rustc::ty::subst::Substs;
 use rustc::ty::{self, ClosureSubsts, GeneratorSubsts, RegionVid, Ty, TyCtxt};
 use rustc::util::nodemap::FxHashMap;
 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
-use rustc_data_structures::transitive_relation::TransitiveRelation;
 use std::iter;
 use syntax::ast;
 
@@ -85,21 +81,7 @@ pub struct UniversalRegions<'tcx> {
     /// as the name suggests. =)
     pub unnormalized_input_tys: &'tcx [Ty<'tcx>],
 
-    /// Each RBP `('a, GK)` indicates that `GK: 'a` can be assumed to
-    /// be true. These encode relationships like `T: 'a` that are
-    /// added via implicit bounds.
-    ///
-    /// Each region here is guaranteed to be a key in the `indices`
-    /// map.  We use the "original" regions (i.e., the keys from the
-    /// map, and not the values) because the code in
-    /// `process_registered_region_obligations` has some special-cased
-    /// logic expecting to see (e.g.) `ReStatic`, and if we supplied
-    /// our special inference variable there, we would mess that up.
-    pub region_bound_pairs: Vec<(ty::Region<'tcx>, GenericKind<'tcx>)>,
-
     pub yield_ty: Option<Ty<'tcx>>,
-
-    relations: UniversalRegionRelations,
 }
 
 /// The "defining type" for this MIR. The key feature of the "defining
@@ -171,20 +153,6 @@ struct UniversalRegionIndices<'tcx> {
     indices: FxHashMap<ty::Region<'tcx>, RegionVid>,
 }
 
-#[derive(Debug)]
-struct UniversalRegionRelations {
-    /// Stores the outlives relations that are known to hold from the
-    /// implied bounds, in-scope where clauses, and that sort of
-    /// thing.
-    outlives: TransitiveRelation<RegionVid>,
-
-    /// This is the `<=` relation; that is, if `a: b`, then `b <= a`,
-    /// and we store that here. This is useful when figuring out how
-    /// to express some local region in terms of external regions our
-    /// caller will understand.
-    inverse_outlives: TransitiveRelation<RegionVid>,
-}
-
 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
 pub enum RegionClassification {
     /// A **global** region is one that can be named from
@@ -249,11 +217,6 @@ impl<'tcx> UniversalRegions<'tcx> {
             mir_node_id,
             mir_hir_id,
             param_env,
-            region_bound_pairs: vec![],
-            relations: UniversalRegionRelations {
-                outlives: TransitiveRelation::new(),
-                inverse_outlives: TransitiveRelation::new(),
-            },
         }.build()
     }
 
@@ -326,45 +289,6 @@ impl<'tcx> UniversalRegions<'tcx> {
         self.num_universals
     }
 
-    /// Given two universal regions, returns the postdominating
-    /// upper-bound (effectively the least upper bound).
-    ///
-    /// (See `TransitiveRelation::postdom_upper_bound` for details on
-    /// the postdominating upper bound in general.)
-    pub fn postdom_upper_bound(&self, fr1: RegionVid, fr2: RegionVid) -> RegionVid {
-        assert!(self.is_universal_region(fr1));
-        assert!(self.is_universal_region(fr2));
-        *self.relations
-            .inverse_outlives
-            .postdom_upper_bound(&fr1, &fr2)
-            .unwrap_or(&self.fr_static)
-    }
-
-    /// 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.
-    ///
-    /// (*) If there are multiple competing choices, we pick the "postdominating"
-    /// one. See `TransitiveRelation::postdom_upper_bound` for details.
-    pub fn non_local_upper_bound(&self, fr: RegionVid) -> RegionVid {
-        debug!("non_local_upper_bound(fr={:?})", fr);
-        self.non_local_bound(&self.relations.inverse_outlives, fr)
-            .unwrap_or(self.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.
-    ///
-    /// (*) If there are multiple competing choices, we pick the "postdominating"
-    /// one. See `TransitiveRelation::postdom_upper_bound` for details.
-    pub fn non_local_lower_bound(&self, fr: RegionVid) -> Option<RegionVid> {
-        debug!("non_local_lower_bound(fr={:?})", fr);
-        self.non_local_bound(&self.relations.outlives, fr)
-    }
-
     /// Returns the number of global plus external universal regions.
     /// For closures, these are the regions that appear free in the
     /// closure type (versus those bound in the closure
@@ -374,68 +298,6 @@ impl<'tcx> UniversalRegions<'tcx> {
         self.first_local_index
     }
 
-    /// 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(
-        &self,
-        relation: &TransitiveRelation<RegionVid>,
-        fr0: RegionVid,
-    ) -> Option<RegionVid> {
-        // This method assumes that `fr0` is one of the universally
-        // quantified region variables.
-        assert!(self.is_universal_region(fr0));
-
-        let mut external_parents = vec![];
-        let mut queue = vec![&fr0];
-
-        // Keep expanding `fr` into its parents until we reach
-        // non-local regions.
-        while let Some(fr) = queue.pop() {
-            if !self.is_local_free_region(*fr) {
-                external_parents.push(fr);
-                continue;
-            }
-
-            queue.extend(relation.parents(fr));
-        }
-
-        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.is_local_free_region(post_dom) {
-                Some(post_dom)
-            } else {
-                None
-            }
-        })
-    }
-
-    /// True if fr1 is known to outlive fr2.
-    ///
-    /// This will only ever be true for universally quantified regions.
-    pub fn outlives(&self, fr1: RegionVid, fr2: RegionVid) -> bool {
-        self.relations.outlives.contains(&fr1, &fr2)
-    }
-
-    /// Returns a vector of free regions `x` such that `fr1: x` is
-    /// known to hold.
-    pub fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<&RegionVid> {
-        self.relations.outlives.reachable_from(&fr1)
-    }
-
     /// Get an iterator over all the early-bound regions that have names.
     pub fn named_universal_regions<'s>(
         &'s self,
@@ -455,14 +317,12 @@ struct UniversalRegionsBuilder<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
     mir_hir_id: HirId,
     mir_node_id: ast::NodeId,
     param_env: ty::ParamEnv<'tcx>,
-    region_bound_pairs: Vec<(ty::Region<'tcx>, GenericKind<'tcx>)>,
-    relations: UniversalRegionRelations,
 }
 
 const FR: NLLRegionVariableOrigin = NLLRegionVariableOrigin::FreeRegion;
 
 impl<'cx, 'gcx, 'tcx> UniversalRegionsBuilder<'cx, 'gcx, 'tcx> {
-    fn build(mut self) -> UniversalRegions<'tcx> {
+    fn build(self) -> UniversalRegions<'tcx> {
         debug!("build(mir_def_id={:?})", self.mir_def_id);
 
         let param_env = self.param_env;
@@ -519,33 +379,6 @@ impl<'cx, 'gcx, 'tcx> UniversalRegionsBuilder<'cx, 'gcx, 'tcx> {
         let fr_fn_body = self.infcx.next_nll_region_var(FR).to_region_vid();
         let num_universals = self.infcx.num_region_vars();
 
-        // Insert the facts we know from the predicates. Why? Why not.
-        self.add_outlives_bounds(
-            &indices,
-            outlives_bounds::explicit_outlives_bounds(param_env),
-        );
-
-        // Add the implied bounds from inputs and outputs.
-        for ty in inputs_and_output {
-            debug!("build: input_or_output={:?}", ty);
-            self.add_implied_bounds(&indices, ty);
-        }
-
-        // Finally:
-        // - outlives is reflexive, so `'r: 'r` for every region `'r`
-        // - `'static: 'r` for every region `'r`
-        // - `'r: 'fn_body` for every (other) universally quantified
-        //   region `'r`, all of which are provided by our caller
-        for fr in (FIRST_GLOBAL_INDEX..num_universals).map(RegionVid::new) {
-            debug!(
-                "build: relating free region {:?} to itself and to 'static",
-                fr
-            );
-            self.relations.relate_universal_regions(fr, fr);
-            self.relations.relate_universal_regions(fr_static, fr);
-            self.relations.relate_universal_regions(fr, fr_fn_body);
-        }
-
         let (unnormalized_output_ty, unnormalized_input_tys) =
             inputs_and_output.split_last().unwrap();
 
@@ -579,9 +412,7 @@ impl<'cx, 'gcx, 'tcx> UniversalRegionsBuilder<'cx, 'gcx, 'tcx> {
             defining_ty,
             unnormalized_output_ty,
             unnormalized_input_tys,
-            region_bound_pairs: self.region_bound_pairs,
             yield_ty: yield_ty,
-            relations: self.relations,
         }
     }
 
@@ -730,64 +561,6 @@ impl<'cx, 'gcx, 'tcx> UniversalRegionsBuilder<'cx, 'gcx, 'tcx> {
             }
         }
     }
-
-    /// Update the type of a single local, which should represent
-    /// either the return type of the MIR or one of its arguments. At
-    /// the same time, compute and add any implied bounds that come
-    /// from this local.
-    ///
-    /// Assumes that `universal_regions` indices map is fully constructed.
-    fn add_implied_bounds(&mut self, indices: &UniversalRegionIndices<'tcx>, ty: Ty<'tcx>) {
-        debug!("add_implied_bounds(ty={:?})", ty);
-        let span = self.infcx.tcx.def_span(self.mir_def_id);
-        let bounds = self.infcx
-            .implied_outlives_bounds(self.param_env, self.mir_node_id, ty, span);
-        self.add_outlives_bounds(indices, bounds);
-    }
-
-    /// Registers the `OutlivesBound` items from `outlives_bounds` in
-    /// the outlives relation as well as the region-bound pairs
-    /// listing.
-    fn add_outlives_bounds<I>(&mut self, indices: &UniversalRegionIndices<'tcx>, outlives_bounds: I)
-    where
-        I: IntoIterator<Item = OutlivesBound<'tcx>>,
-    {
-        for outlives_bound in outlives_bounds {
-            debug!("add_outlives_bounds(bound={:?})", outlives_bound);
-
-            match outlives_bound {
-                OutlivesBound::RegionSubRegion(r1, r2) => {
-                    // The bound says that `r1 <= r2`; we store `r2: r1`.
-                    let r1 = indices.to_region_vid(r1);
-                    let r2 = indices.to_region_vid(r2);
-                    self.relations.relate_universal_regions(r2, r1);
-                }
-
-                OutlivesBound::RegionSubParam(r_a, param_b) => {
-                    self.region_bound_pairs
-                        .push((r_a, GenericKind::Param(param_b)));
-                }
-
-                OutlivesBound::RegionSubProjection(r_a, projection_b) => {
-                    self.region_bound_pairs
-                        .push((r_a, GenericKind::Projection(projection_b)));
-                }
-            }
-        }
-    }
-}
-
-impl UniversalRegionRelations {
-    /// Records in the `outlives_relation` (and
-    /// `inverse_outlives_relation`) that `fr_a: fr_b`.
-    fn relate_universal_regions(&mut self, fr_a: RegionVid, fr_b: RegionVid) {
-        debug!(
-            "relate_universal_regions: fr_a={:?} outlives fr_b={:?}",
-            fr_a, fr_b
-        );
-        self.outlives.add(fr_a, fr_b);
-        self.inverse_outlives.add(fr_b, fr_a);
-    }
 }
 
 trait InferCtxtExt<'tcx> {
@@ -925,19 +698,6 @@ impl<'tcx> UniversalRegionIndices<'tcx> {
     }
 }
 
-/// This trait is used by the `impl-trait` constraint code to abstract
-/// over the `FreeRegionMap` from lexical regions and
-/// `UniversalRegions` (from NLL)`.
-impl<'tcx> FreeRegionRelations<'tcx> for UniversalRegions<'tcx> {
-    fn sub_free_regions(&self, shorter: ty::Region<'tcx>, longer: ty::Region<'tcx>) -> bool {
-        let shorter = shorter.to_region_vid();
-        assert!(self.is_universal_region(shorter));
-        let longer = longer.to_region_vid();
-        assert!(self.is_universal_region(longer));
-        self.outlives(longer, shorter)
-    }
-}
-
 /// Iterates over the late-bound regions defined on fn_def_id and
 /// invokes `f` with the liberated form of each one.
 fn for_each_late_bound_region_defined_on<'tcx>(
diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs
index 54730ecd75f..3f32d307409 100644
--- a/src/librustc_mir/lib.rs
+++ b/src/librustc_mir/lib.rs
@@ -14,6 +14,8 @@ Rust MIR: a lowered representation of Rust. Also: an experiment!
 
 */
 
+#![feature(infer_outlives_requirements)]
+#![feature(in_band_lifetimes)]
 #![feature(slice_patterns)]
 #![feature(slice_sort_by_cached_key)]
 #![feature(from_ref)]
diff --git a/src/test/ui/issue-52057.rs b/src/test/ui/issue-52057.rs
new file mode 100644
index 00000000000..533623fd389
--- /dev/null
+++ b/src/test/ui/issue-52057.rs
@@ -0,0 +1,35 @@
+// 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.
+
+// Regression test for #52057. There is an implied bound
+// that `I: 'a` where `'a` is the lifetime of `self` in `parse_first`;
+// but to observe that, one must normalize first.
+//
+// run-pass
+
+#![feature(nll)]
+
+pub trait Parser {
+    type Input;
+
+    #[inline(always)]
+    fn parse_first(input: &mut Self::Input);
+}
+
+impl<'a, I, P: ?Sized> Parser for &'a mut P
+where
+    P: Parser<Input = I>,
+{
+    type Input = I;
+
+    fn parse_first(_: &mut Self::Input) {}
+}
+
+fn main() {}