extract out the implied bounds code from `regionck`

4 files changed, 357 insertions, 270 deletions

diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index 6767fbae3d8..297feead617 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -139,9 +139,10 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
         });
     }
 
-    pub fn register_predicate_obligations(&mut self,
-                                          infcx: &InferCtxt<'a, 'gcx, 'tcx>,
-                                          obligations: Vec<PredicateObligation<'tcx>>)
+    pub fn register_predicate_obligations<I>(&mut self,
+                                             infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+                                             obligations: I)
+        where I: IntoIterator<Item = PredicateObligation<'tcx>>
     {
         for obligation in obligations {
             self.register_predicate_obligation(infcx, obligation);
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index c8b2032a498..7d98a1c9246 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -137,6 +137,7 @@ pub mod dropck;
 pub mod _match;
 pub mod writeback;
 mod regionck;
+mod regionck_implied_bounds;
 pub mod coercion;
 pub mod demand;
 pub mod method;
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index 06e0e6ccdb5..5954a0f2ecd 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -84,17 +84,14 @@
 
 use check::dropck;
 use check::FnCtxt;
-use middle::free_region::FreeRegionMap;
 use middle::mem_categorization as mc;
 use middle::mem_categorization::Categorization;
 use middle::region;
 use rustc::hir::def_id::DefId;
 use rustc::ty::subst::Substs;
-use rustc::ty::{self, Ty, TypeFoldable};
-use rustc::infer::{self, GenericKind};
+use rustc::ty::{self, Ty};
+use rustc::infer;
 use rustc::ty::adjustment;
-use rustc::ty::outlives::Component;
-use rustc::ty::wf;
 
 use std::mem;
 use std::ops::Deref;
@@ -104,6 +101,8 @@ use syntax_pos::Span;
 use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
 use rustc::hir::{self, PatKind};
 
+use super::regionck_implied_bounds::OutlivesEnvironment;
+
 // a variation on try that just returns unit
 macro_rules! ignore_err {
     ($e:expr) => (match $e { Ok(e) => e, Err(_) => return () })
@@ -116,7 +115,11 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
     pub fn regionck_expr(&self, body: &'gcx hir::Body) {
         let subject = self.tcx.hir.body_owner_def_id(body.id());
         let id = body.value.id;
-        let mut rcx = RegionCtxt::new(self, RepeatingScope(id), id, Subject(subject));
+        let mut rcx = RegionCtxt::new(self,
+                                      RepeatingScope(id),
+                                      id,
+                                      Subject(subject),
+                                      self.param_env);
         if self.err_count_since_creation() == 0 {
             // regionck assumes typeck succeeded
             rcx.visit_body(body);
@@ -125,7 +128,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         rcx.resolve_regions_and_report_errors();
 
         assert!(self.tables.borrow().free_region_map.is_empty());
-        self.tables.borrow_mut().free_region_map = rcx.free_region_map;
+        self.tables.borrow_mut().free_region_map = rcx.outlives_environment.into_free_region_map();
     }
 
     /// Region checking during the WF phase for items. `wf_tys` are the
@@ -136,10 +139,12 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                          wf_tys: &[Ty<'tcx>]) {
         debug!("regionck_item(item.id={:?}, wf_tys={:?}", item_id, wf_tys);
         let subject = self.tcx.hir.local_def_id(item_id);
-        let mut rcx = RegionCtxt::new(self, RepeatingScope(item_id), item_id, Subject(subject));
-        rcx.free_region_map.relate_free_regions_from_predicates(
-            &self.param_env.caller_bounds);
-        rcx.relate_free_regions(wf_tys, item_id, span);
+        let mut rcx = RegionCtxt::new(self,
+                                      RepeatingScope(item_id),
+                                      item_id,
+                                      Subject(subject),
+                                      self.param_env);
+        rcx.outlives_environment.add_implied_bounds(self, wf_tys, item_id, span);
         rcx.visit_region_obligations(item_id);
         rcx.resolve_regions_and_report_errors();
     }
@@ -158,23 +163,24 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         debug!("regionck_fn(id={})", fn_id);
         let subject = self.tcx.hir.body_owner_def_id(body.id());
         let node_id = body.value.id;
-        let mut rcx = RegionCtxt::new(self, RepeatingScope(node_id), node_id, Subject(subject));
+        let mut rcx = RegionCtxt::new(self,
+                                      RepeatingScope(node_id),
+                                      node_id,
+                                      Subject(subject),
+                                      self.param_env);
 
         if self.err_count_since_creation() == 0 {
             // regionck assumes typeck succeeded
             rcx.visit_fn_body(fn_id, body, self.tcx.hir.span(fn_id));
         }
 
-        rcx.free_region_map.relate_free_regions_from_predicates(
-            &self.param_env.caller_bounds);
-
         rcx.resolve_regions_and_report_errors();
 
         // In this mode, we also copy the free-region-map into the
         // tables of the enclosing fcx. In the other regionck modes
         // (e.g., `regionck_item`), we don't have an enclosing tables.
         assert!(self.tables.borrow().free_region_map.is_empty());
-        self.tables.borrow_mut().free_region_map = rcx.free_region_map;
+        self.tables.borrow_mut().free_region_map = rcx.outlives_environment.into_free_region_map();
     }
 }
 
@@ -184,11 +190,9 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 pub struct RegionCtxt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     pub fcx: &'a FnCtxt<'a, 'gcx, 'tcx>,
 
-    region_bound_pairs: Vec<(ty::Region<'tcx>, GenericKind<'tcx>)>,
-
     pub region_scope_tree: Rc<region::ScopeTree>,
 
-    free_region_map: FreeRegionMap<'tcx>,
+    outlives_environment: OutlivesEnvironment<'tcx>,
 
     // id of innermost fn body id
     body_id: ast::NodeId,
@@ -204,24 +208,6 @@ pub struct RegionCtxt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 
 }
 
-/// Implied bounds are region relationships that we deduce
-/// automatically.  The idea is that (e.g.) a caller must check that a
-/// function's argument types are well-formed immediately before
-/// calling that fn, and hence the *callee* can assume that its
-/// argument types are well-formed. This may imply certain relationships
-/// between generic parameters. For example:
-///
-///     fn foo<'a,T>(x: &'a T)
-///
-/// can only be called with a `'a` and `T` such that `&'a T` is WF.
-/// For `&'a T` to be WF, `T: 'a` must hold. So we can assume `T: 'a`.
-#[derive(Debug)]
-enum ImpliedBound<'tcx> {
-    RegionSubRegion(ty::Region<'tcx>, ty::Region<'tcx>),
-    RegionSubParam(ty::Region<'tcx>, ty::ParamTy),
-    RegionSubProjection(ty::Region<'tcx>, ty::ProjectionTy<'tcx>),
-}
-
 impl<'a, 'gcx, 'tcx> Deref for RegionCtxt<'a, 'gcx, 'tcx> {
     type Target = FnCtxt<'a, 'gcx, 'tcx>;
     fn deref(&self) -> &Self::Target {
@@ -236,8 +222,11 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
     pub fn new(fcx: &'a FnCtxt<'a, 'gcx, 'tcx>,
                RepeatingScope(initial_repeating_scope): RepeatingScope,
                initial_body_id: ast::NodeId,
-               Subject(subject): Subject) -> RegionCtxt<'a, 'gcx, 'tcx> {
+               Subject(subject): Subject,
+               param_env: ty::ParamEnv<'tcx>)
+               -> RegionCtxt<'a, 'gcx, 'tcx> {
         let region_scope_tree = fcx.tcx.region_scope_tree(subject);
+        let outlives_environment = OutlivesEnvironment::new(param_env);
         RegionCtxt {
             fcx,
             region_scope_tree,
@@ -245,20 +234,10 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
             body_id: initial_body_id,
             call_site_scope: None,
             subject_def_id: subject,
-            region_bound_pairs: Vec::new(),
-            free_region_map: FreeRegionMap::new(),
+            outlives_environment,
         }
     }
 
-    fn set_call_site_scope(&mut self, call_site_scope: Option<region::Scope>)
-                           -> Option<region::Scope> {
-        mem::replace(&mut self.call_site_scope, call_site_scope)
-    }
-
-    fn set_body_id(&mut self, body_id: ast::NodeId) -> ast::NodeId {
-        mem::replace(&mut self.body_id, body_id)
-    }
-
     fn set_repeating_scope(&mut self, scope: ast::NodeId) -> ast::NodeId {
         mem::replace(&mut self.repeating_scope, scope)
     }
@@ -302,6 +281,18 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
         self.resolve_type(ty)
     }
 
+    /// This is the "main" function when region-checking a function item or a closure
+    /// within a function item. It begins by updating various fields (e.g., `call_site_scope`
+    /// and `outlives_environment`) to be appropriate to the function and then adds constraints
+    /// derived from the function body.
+    ///
+    /// Note that it does **not** restore the state of the fields that
+    /// it updates! This is intentional, since -- for the main
+    /// function -- we wish to be able to read the final
+    /// `outlives_environment` and other fields from the caller. For
+    /// closures, however, we save and restore any "scoped state"
+    /// before we invoke this function. (See `visit_fn` in the
+    /// `intravisit::Visitor` impl below.)
     fn visit_fn_body(&mut self,
                      id: ast::NodeId, // the id of the fn itself
                      body: &'gcx hir::Body,
@@ -311,9 +302,10 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
         debug!("visit_fn_body(id={})", id);
 
         let body_id = body.id();
+        self.body_id = body_id.node_id;
 
         let call_site = region::Scope::CallSite(body.value.hir_id.local_id);
-        let old_call_site_scope = self.set_call_site_scope(Some(call_site));
+        self.call_site_scope = Some(call_site);
 
         let fn_sig = {
             let fn_hir_id = self.tcx.hir.node_to_hir_id(id);
@@ -325,8 +317,6 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
             }
         };
 
-        let old_region_bounds_pairs_len = self.region_bound_pairs.len();
-
         // Collect the types from which we create inferred bounds.
         // For the return type, if diverging, substitute `bool` just
         // because it will have no effect.
@@ -335,8 +325,11 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
         let fn_sig_tys: Vec<_> =
             fn_sig.inputs().iter().cloned().chain(Some(fn_sig.output())).collect();
 
-        let old_body_id = self.set_body_id(body_id.node_id);
-        self.relate_free_regions(&fn_sig_tys[..], body_id.node_id, span);
+        self.outlives_environment.add_implied_bounds(
+            self.fcx,
+            &fn_sig_tys[..],
+            body_id.node_id,
+            span);
         self.link_fn_args(region::Scope::Node(body.value.hir_id.local_id), &body.arguments);
         self.visit_body(body);
         self.visit_region_obligations(body_id.node_id);
@@ -349,11 +342,6 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
         self.type_of_node_must_outlive(infer::CallReturn(span),
                                        body_hir_id,
                                        call_site_region);
-
-        self.region_bound_pairs.truncate(old_region_bounds_pairs_len);
-
-        self.set_body_id(old_body_id);
-        self.set_call_site_scope(old_call_site_scope);
     }
 
     fn visit_region_obligations(&mut self, node_id: ast::NodeId)
@@ -366,217 +354,16 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
         self.select_all_obligations_or_error();
 
         self.infcx.process_registered_region_obligations(
-            &self.region_bound_pairs,
+            self.outlives_environment.region_bound_pairs(),
             self.implicit_region_bound,
             self.param_env,
             self.body_id);
     }
 
-    /// This method populates the region map's `free_region_map`. It walks over the transformed
-    /// argument and return types for each function just before we check the body of that function,
-    /// looking for types where you have a borrowed pointer to other borrowed data (e.g., `&'a &'b
-    /// [usize]`.  We do not allow references to outlive the things they point at, so we can assume
-    /// that `'a <= 'b`. This holds for both the argument and return types, basically because, on
-    /// the caller side, the caller is responsible for checking that the type of every expression
-    /// (including the actual values for the arguments, as well as the return type of the fn call)
-    /// is well-formed.
-    ///
-    /// Tests: `src/test/compile-fail/regions-free-region-ordering-*.rs`
-    fn relate_free_regions(&mut self,
-                           fn_sig_tys: &[Ty<'tcx>],
-                           body_id: ast::NodeId,
-                           span: Span) {
-        debug!("relate_free_regions >>");
-
-        for &ty in fn_sig_tys {
-            let ty = self.resolve_type(ty);
-            debug!("relate_free_regions(t={:?})", ty);
-            let implied_bounds = self.implied_bounds(body_id, ty, span);
-
-            // But also record other relationships, such as `T:'x`,
-            // that don't go into the free-region-map but which we use
-            // here.
-            for implication in implied_bounds {
-                debug!("implication: {:?}", implication);
-                match implication {
-                    ImpliedBound::RegionSubRegion(r_a @ &ty::ReEarlyBound(_),
-                                                  &ty::ReVar(vid_b)) |
-                    ImpliedBound::RegionSubRegion(r_a @ &ty::ReFree(_),
-                                                  &ty::ReVar(vid_b)) => {
-                        self.add_given(r_a, vid_b);
-                    }
-                    ImpliedBound::RegionSubParam(r_a, param_b) => {
-                        self.region_bound_pairs.push((r_a, GenericKind::Param(param_b)));
-                    }
-                    ImpliedBound::RegionSubProjection(r_a, projection_b) => {
-                        self.region_bound_pairs.push((r_a, GenericKind::Projection(projection_b)));
-                    }
-                    ImpliedBound::RegionSubRegion(r_a, r_b) => {
-                        // In principle, we could record (and take
-                        // advantage of) every relationship here, but
-                        // we are also free not to -- it simply means
-                        // strictly less that we can successfully type
-                        // check. Right now we only look for things
-                        // relationships between free regions. (It may
-                        // also be that we should revise our inference
-                        // system to be more general and to make use
-                        // of *every* relationship that arises here,
-                        // but presently we do not.)
-                        if body_id == self.fcx.body_id {
-                            // Only modify `free_region_map` if these
-                            // are parameters from the root
-                            // function. That's because this data
-                            // struture is shared across all functions
-                            // and hence we don't want to take implied
-                            // bounds from one closure and use them
-                            // outside.
-                            self.free_region_map.relate_regions(r_a, r_b);
-                        }
-                    }
-                }
-            }
-        }
-
-        debug!("<< relate_free_regions");
-    }
-
-    /// Compute the implied bounds that a callee/impl can assume based on
-    /// the fact that caller/projector has ensured that `ty` is WF.  See
-    /// the `ImpliedBound` type for more details.
-    fn implied_bounds(&mut self, body_id: ast::NodeId, ty: Ty<'tcx>, span: Span)
-                      -> Vec<ImpliedBound<'tcx>> {
-        // Sometimes when we ask what it takes for T: WF, we get back that
-        // U: WF is required; in that case, we push U onto this stack and
-        // process it next. Currently (at least) these resulting
-        // predicates are always guaranteed to be a subset of the original
-        // type, so we need not fear non-termination.
-        let mut wf_types = vec![ty];
-
-        let mut implied_bounds = vec![];
-
-        while let Some(ty) = wf_types.pop() {
-            // Compute the obligations for `ty` to be well-formed. If `ty` is
-            // an unresolved inference variable, just substituted an empty set
-            // -- because the return type here is going to be things we *add*
-            // to the environment, it's always ok for this set to be smaller
-            // than the ultimate set. (Note: normally there won't be
-            // unresolved inference variables here anyway, but there might be
-            // during typeck under some circumstances.)
-            let obligations =
-                wf::obligations(self, self.fcx.param_env, body_id, ty, span)
-                .unwrap_or(vec![]);
-
-            // NB: All of these predicates *ought* to be easily proven
-            // true. In fact, their correctness is (mostly) implied by
-            // other parts of the program. However, in #42552, we had
-            // an annoying scenario where:
-            //
-            // - Some `T::Foo` gets normalized, resulting in a
-            //   variable `_1` and a `T: Trait<Foo=_1>` constraint
-            //   (not sure why it couldn't immediately get
-            //   solved). This result of `_1` got cached.
-            // - These obligations were dropped on the floor here,
-            //   rather than being registered.
-            // - Then later we would get a request to normalize
-            //   `T::Foo` which would result in `_1` being used from
-            //   the cache, but hence without the `T: Trait<Foo=_1>`
-            //   constraint. As a result, `_1` never gets resolved,
-            //   and we get an ICE (in dropck).
-            //
-            // Therefore, we register any predicates involving
-            // inference variables. We restrict ourselves to those
-            // involving inference variables both for efficiency and
-            // to avoids duplicate errors that otherwise show up.
-            self.fcx.register_predicates(
-                obligations.iter()
-                           .filter(|o| o.predicate.has_infer_types())
-                           .cloned());
-
-            // From the full set of obligations, just filter down to the
-            // region relationships.
-            implied_bounds.extend(
-                obligations
-                    .into_iter()
-                    .flat_map(|obligation| {
-                        assert!(!obligation.has_escaping_regions());
-                        match obligation.predicate {
-                            ty::Predicate::Trait(..) |
-                            ty::Predicate::Equate(..) |
-                            ty::Predicate::Subtype(..) |
-                            ty::Predicate::Projection(..) |
-                            ty::Predicate::ClosureKind(..) |
-                            ty::Predicate::ObjectSafe(..) |
-                            ty::Predicate::ConstEvaluatable(..) =>
-                                vec![],
-
-                            ty::Predicate::WellFormed(subty) => {
-                                wf_types.push(subty);
-                                vec![]
-                            }
-
-                            ty::Predicate::RegionOutlives(ref data) =>
-                                match self.tcx.no_late_bound_regions(data) {
-                                    None =>
-                                        vec![],
-                                    Some(ty::OutlivesPredicate(r_a, r_b)) =>
-                                        vec![ImpliedBound::RegionSubRegion(r_b, r_a)],
-                                },
-
-                            ty::Predicate::TypeOutlives(ref data) =>
-                                match self.tcx.no_late_bound_regions(data) {
-                                    None => vec![],
-                                    Some(ty::OutlivesPredicate(ty_a, r_b)) => {
-                                        let ty_a = self.resolve_type_vars_if_possible(&ty_a);
-                                        let components = self.tcx.outlives_components(ty_a);
-                                        self.implied_bounds_from_components(r_b, components)
-                                    }
-                                },
-                        }}));
-        }
-
-        implied_bounds
-    }
-
-    /// When we have an implied bound that `T: 'a`, we can further break
-    /// this down to determine what relationships would have to hold for
-    /// `T: 'a` to hold. We get to assume that the caller has validated
-    /// those relationships.
-    fn implied_bounds_from_components(&self,
-                                      sub_region: ty::Region<'tcx>,
-                                      sup_components: Vec<Component<'tcx>>)
-                                      -> Vec<ImpliedBound<'tcx>>
-    {
-        sup_components
-            .into_iter()
-            .flat_map(|component| {
-                match component {
-                    Component::Region(r) =>
-                        vec![ImpliedBound::RegionSubRegion(sub_region, r)],
-                    Component::Param(p) =>
-                        vec![ImpliedBound::RegionSubParam(sub_region, p)],
-                    Component::Projection(p) =>
-                        vec![ImpliedBound::RegionSubProjection(sub_region, p)],
-                    Component::EscapingProjection(_) =>
-                    // If the projection has escaping regions, don't
-                    // try to infer any implied bounds even for its
-                    // free components. This is conservative, because
-                    // the caller will still have to prove that those
-                    // free components outlive `sub_region`. But the
-                    // idea is that the WAY that the caller proves
-                    // that may change in the future and we want to
-                    // give ourselves room to get smarter here.
-                        vec![],
-                    Component::UnresolvedInferenceVariable(..) =>
-                        vec![],
-                }
-            })
-            .collect()
-    }
-
     fn resolve_regions_and_report_errors(&self) {
         self.fcx.resolve_regions_and_report_errors(self.subject_def_id,
                                                    &self.region_scope_tree,
-                                                   &self.free_region_map);
+                                                   self.outlives_environment.free_region_map());
     }
 
     fn constrain_bindings_in_pat(&mut self, pat: &hir::Pat) {
@@ -632,10 +419,28 @@ impl<'a, 'gcx, 'tcx> Visitor<'gcx> for RegionCtxt<'a, 'gcx, 'tcx> {
         NestedVisitorMap::None
     }
 
-    fn visit_fn(&mut self, _fk: intravisit::FnKind<'gcx>, _: &'gcx hir::FnDecl,
-                b: hir::BodyId, span: Span, id: ast::NodeId) {
-        let body = self.tcx.hir.body(b);
-        self.visit_fn_body(id, body, span)
+    fn visit_fn(&mut self,
+                fk: intravisit::FnKind<'gcx>,
+                _: &'gcx hir::FnDecl,
+                body_id: hir::BodyId,
+                span: Span,
+                id: ast::NodeId) {
+        assert!(match fk { intravisit::FnKind::Closure(..) => true, _ => false },
+                "visit_fn invoked for something other than a closure");
+
+        // Save state of current function before invoking
+        // `visit_fn_body`.  We will restore afterwards.
+        let outlives_environment = self.outlives_environment.clone();
+        let old_body_id = self.body_id;
+        let old_call_site_scope = self.call_site_scope;
+
+        let body = self.tcx.hir.body(body_id);
+        self.visit_fn_body(id, body, span);
+
+        // Restore state from previous function.
+        self.call_site_scope = old_call_site_scope;
+        self.body_id = old_body_id;
+        self.outlives_environment = outlives_environment;
     }
 
     //visit_pat: visit_pat, // (..) see above
@@ -1144,7 +949,7 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
                              ty: Ty<'tcx>,
                              region: ty::Region<'tcx>)
     {
-        self.infcx.type_must_outlive(&self.region_bound_pairs,
+        self.infcx.type_must_outlive(self.outlives_environment.region_bound_pairs(),
                                      self.implicit_region_bound,
                                      self.param_env,
                                      origin,
diff --git a/src/librustc_typeck/check/regionck_implied_bounds.rs b/src/librustc_typeck/check/regionck_implied_bounds.rs
new file mode 100644
index 00000000000..f84e0dd880f
--- /dev/null
+++ b/src/librustc_typeck/check/regionck_implied_bounds.rs
@@ -0,0 +1,280 @@
+use middle::free_region::FreeRegionMap;
+use rustc::ty::{self, Ty, TypeFoldable};
+use rustc::infer::{InferCtxt, GenericKind};
+use rustc::traits::FulfillmentContext;
+use rustc::ty::outlives::Component;
+use rustc::ty::wf;
+
+use syntax::ast;
+use syntax_pos::Span;
+
+#[derive(Clone)]
+pub struct OutlivesEnvironment<'tcx> {
+    param_env: ty::ParamEnv<'tcx>,
+    free_region_map: FreeRegionMap<'tcx>,
+    region_bound_pairs: Vec<(ty::Region<'tcx>, GenericKind<'tcx>)>,
+}
+
+/// Implied bounds are region relationships that we deduce
+/// automatically.  The idea is that (e.g.) a caller must check that a
+/// function's argument types are well-formed immediately before
+/// calling that fn, and hence the *callee* can assume that its
+/// argument types are well-formed. This may imply certain relationships
+/// between generic parameters. For example:
+///
+///     fn foo<'a,T>(x: &'a T)
+///
+/// can only be called with a `'a` and `T` such that `&'a T` is WF.
+/// For `&'a T` to be WF, `T: 'a` must hold. So we can assume `T: 'a`.
+#[derive(Debug)]
+enum ImpliedBound<'tcx> {
+    RegionSubRegion(ty::Region<'tcx>, ty::Region<'tcx>),
+    RegionSubParam(ty::Region<'tcx>, ty::ParamTy),
+    RegionSubProjection(ty::Region<'tcx>, ty::ProjectionTy<'tcx>),
+}
+
+impl<'a, 'gcx: 'tcx, 'tcx: 'a> OutlivesEnvironment<'tcx> {
+    pub fn new(param_env: ty::ParamEnv<'tcx>) -> Self {
+        let mut free_region_map = FreeRegionMap::new();
+        free_region_map.relate_free_regions_from_predicates(&param_env.caller_bounds);
+
+        OutlivesEnvironment {
+            param_env,
+            free_region_map,
+            region_bound_pairs: vec![],
+        }
+    }
+
+    /// Borrows current value of the `free_region_map`.
+    pub fn free_region_map(&self) -> &FreeRegionMap<'tcx> {
+        &self.free_region_map
+    }
+
+    /// Borrows current value of the `region_bound_pairs`.
+    pub fn region_bound_pairs(&self) -> &[(ty::Region<'tcx>, GenericKind<'tcx>)] {
+        &self.region_bound_pairs
+    }
+
+    /// Returns ownership of the `free_region_map`.
+    pub fn into_free_region_map(self) -> FreeRegionMap<'tcx> {
+        self.free_region_map
+    }
+
+    /// This method adds "implied bounds" into the outlives environment.
+    /// Implied bounds are outlives relationships that we can deduce
+    /// on the basis that certain types must be well-formed -- these are
+    /// either the types that appear in the function signature or else
+    /// the input types to an impl. For example, if you have a function
+    /// like
+    ///
+    /// ```
+    /// fn foo<'a, 'b, T>(x: &'a &'b [T]) { }
+    /// ```
+    ///
+    /// we can assume in the caller's body that `'b: 'a` and that `T:
+    /// 'b` (and hence, transitively, that `T: 'a`). This method would
+    /// add those assumptions into the outlives-environment.
+    ///
+    /// Tests: `src/test/compile-fail/regions-free-region-ordering-*.rs`
+    pub fn add_implied_bounds(
+        &mut self,
+        infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+        fn_sig_tys: &[Ty<'tcx>],
+        body_id: ast::NodeId,
+        span: Span,
+    ) {
+        debug!("add_implied_bounds()");
+
+        for &ty in fn_sig_tys {
+            let ty = infcx.resolve_type_vars_if_possible(&ty);
+            debug!("add_implied_bounds: ty = {}", ty);
+            let implied_bounds = self.implied_bounds(infcx, body_id, ty, span);
+
+            // But also record other relationships, such as `T:'x`,
+            // that don't go into the free-region-map but which we use
+            // here.
+            for implication in implied_bounds {
+                debug!("add_implied_bounds: implication={:?}", implication);
+                match implication {
+                    ImpliedBound::RegionSubRegion(
+                        r_a @ &ty::ReEarlyBound(_),
+                        &ty::ReVar(vid_b),
+                    ) |
+                    ImpliedBound::RegionSubRegion(r_a @ &ty::ReFree(_), &ty::ReVar(vid_b)) => {
+                        infcx.add_given(r_a, vid_b);
+                    }
+                    ImpliedBound::RegionSubParam(r_a, param_b) => {
+                        self.region_bound_pairs
+                            .push((r_a, GenericKind::Param(param_b)));
+                    }
+                    ImpliedBound::RegionSubProjection(r_a, projection_b) => {
+                        self.region_bound_pairs
+                            .push((r_a, GenericKind::Projection(projection_b)));
+                    }
+                    ImpliedBound::RegionSubRegion(r_a, r_b) => {
+                        // In principle, we could record (and take
+                        // advantage of) every relationship here, but
+                        // we are also free not to -- it simply means
+                        // strictly less that we can successfully type
+                        // check. Right now we only look for things
+                        // relationships between free regions. (It may
+                        // also be that we should revise our inference
+                        // system to be more general and to make use
+                        // of *every* relationship that arises here,
+                        // but presently we do not.)
+                        self.free_region_map.relate_regions(r_a, r_b);
+                    }
+                }
+            }
+        }
+    }
+
+    /// Compute the implied bounds that a callee/impl can assume based on
+    /// the fact that caller/projector has ensured that `ty` is WF.  See
+    /// the `ImpliedBound` type for more details.
+    fn implied_bounds(
+        &mut self,
+        infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+        body_id: ast::NodeId,
+        ty: Ty<'tcx>,
+        span: Span,
+    ) -> Vec<ImpliedBound<'tcx>> {
+        let tcx = infcx.tcx;
+
+        // Sometimes when we ask what it takes for T: WF, we get back that
+        // U: WF is required; in that case, we push U onto this stack and
+        // process it next. Currently (at least) these resulting
+        // predicates are always guaranteed to be a subset of the original
+        // type, so we need not fear non-termination.
+        let mut wf_types = vec![ty];
+
+        let mut implied_bounds = vec![];
+
+        let mut fulfill_cx = FulfillmentContext::new();
+
+        while let Some(ty) = wf_types.pop() {
+            // Compute the obligations for `ty` to be well-formed. If `ty` is
+            // an unresolved inference variable, just substituted an empty set
+            // -- because the return type here is going to be things we *add*
+            // to the environment, it's always ok for this set to be smaller
+            // than the ultimate set. (Note: normally there won't be
+            // unresolved inference variables here anyway, but there might be
+            // during typeck under some circumstances.)
+            let obligations =
+                wf::obligations(infcx, self.param_env, body_id, ty, span).unwrap_or(vec![]);
+
+            // NB: All of these predicates *ought* to be easily proven
+            // true. In fact, their correctness is (mostly) implied by
+            // other parts of the program. However, in #42552, we had
+            // an annoying scenario where:
+            //
+            // - Some `T::Foo` gets normalized, resulting in a
+            //   variable `_1` and a `T: Trait<Foo=_1>` constraint
+            //   (not sure why it couldn't immediately get
+            //   solved). This result of `_1` got cached.
+            // - These obligations were dropped on the floor here,
+            //   rather than being registered.
+            // - Then later we would get a request to normalize
+            //   `T::Foo` which would result in `_1` being used from
+            //   the cache, but hence without the `T: Trait<Foo=_1>`
+            //   constraint. As a result, `_1` never gets resolved,
+            //   and we get an ICE (in dropck).
+            //
+            // Therefore, we register any predicates involving
+            // inference variables. We restrict ourselves to those
+            // involving inference variables both for efficiency and
+            // to avoids duplicate errors that otherwise show up.
+            fulfill_cx.register_predicate_obligations(
+                infcx,
+                obligations
+                    .iter()
+                    .filter(|o| o.predicate.has_infer_types())
+                    .cloned());
+
+            // From the full set of obligations, just filter down to the
+            // region relationships.
+            implied_bounds.extend(obligations.into_iter().flat_map(|obligation| {
+                assert!(!obligation.has_escaping_regions());
+                match obligation.predicate {
+                    ty::Predicate::Trait(..) |
+                    ty::Predicate::Equate(..) |
+                    ty::Predicate::Subtype(..) |
+                    ty::Predicate::Projection(..) |
+                    ty::Predicate::ClosureKind(..) |
+                    ty::Predicate::ObjectSafe(..) |
+                    ty::Predicate::ConstEvaluatable(..) => vec![],
+
+                    ty::Predicate::WellFormed(subty) => {
+                        wf_types.push(subty);
+                        vec![]
+                    }
+
+                    ty::Predicate::RegionOutlives(ref data) => {
+                        match tcx.no_late_bound_regions(data) {
+                            None => vec![],
+                            Some(ty::OutlivesPredicate(r_a, r_b)) => {
+                                vec![ImpliedBound::RegionSubRegion(r_b, r_a)]
+                            }
+                        }
+                    }
+
+                    ty::Predicate::TypeOutlives(ref data) => {
+                        match tcx.no_late_bound_regions(data) {
+                            None => vec![],
+                            Some(ty::OutlivesPredicate(ty_a, r_b)) => {
+                                let ty_a = infcx.resolve_type_vars_if_possible(&ty_a);
+                                let components = tcx.outlives_components(ty_a);
+                                self.implied_bounds_from_components(r_b, components)
+                            }
+                        }
+                    }
+                }
+            }));
+        }
+
+        // Ensure that those obligations that we had to solve
+        // get solved *here*.
+        match fulfill_cx.select_all_or_error(infcx) {
+            Ok(()) => (),
+            Err(errors) => infcx.report_fulfillment_errors(&errors, None),
+        }
+
+        implied_bounds
+    }
+
+    /// When we have an implied bound that `T: 'a`, we can further break
+    /// this down to determine what relationships would have to hold for
+    /// `T: 'a` to hold. We get to assume that the caller has validated
+    /// those relationships.
+    fn implied_bounds_from_components(
+        &self,
+        sub_region: ty::Region<'tcx>,
+        sup_components: Vec<Component<'tcx>>,
+    ) -> Vec<ImpliedBound<'tcx>> {
+        sup_components
+            .into_iter()
+            .flat_map(|component| {
+                match component {
+                    Component::Region(r) =>
+                        vec![ImpliedBound::RegionSubRegion(sub_region, r)],
+                    Component::Param(p) =>
+                        vec![ImpliedBound::RegionSubParam(sub_region, p)],
+                    Component::Projection(p) =>
+                        vec![ImpliedBound::RegionSubProjection(sub_region, p)],
+                    Component::EscapingProjection(_) =>
+                    // If the projection has escaping regions, don't
+                    // try to infer any implied bounds even for its
+                    // free components. This is conservative, because
+                    // the caller will still have to prove that those
+                    // free components outlive `sub_region`. But the
+                    // idea is that the WAY that the caller proves
+                    // that may change in the future and we want to
+                    // give ourselves room to get smarter here.
+                        vec![],
+                    Component::UnresolvedInferenceVariable(..) =>
+                        vec![],
+                }
+            })
+            .collect()
+    }
+}