Fix overflow when performing drop check calculations in NLL

Clearing out the infcx's region constraints after processing each type
ends up interacting badly with normalizing associated types. This commit
keeps all region constraints intact until the end of
TypeLivenessGenerator.add_drop_live_constraint, ensuring that normalized
types are able to re-use existing inference variables.

Fixes #47589

2 files changed, 113 insertions, 37 deletions

diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness.rs
index 6c2037810d3..93bb3cb6647 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness.rs
@@ -15,7 +15,11 @@ use dataflow::move_paths::{HasMoveData, MoveData};
 use rustc::mir::{BasicBlock, Location, Mir};
 use rustc::mir::Local;
 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
+//use rustc::ty::subst::Kind;
+use rustc::traits;
+use rustc::infer::InferOk;
 use rustc::util::common::ErrorReported;
+use borrow_check::nll::type_check::AtLocation;
 use rustc_data_structures::fx::FxHashSet;
 use syntax::codemap::DUMMY_SP;
 use util::liveness::LivenessResults;
@@ -184,48 +188,87 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
             location
         );
 
-        let tcx = self.cx.infcx.tcx;
-        let mut types = vec![(dropped_ty, 0)];
-        let mut known = FxHashSet();
-        while let Some((ty, depth)) = types.pop() {
-            let span = DUMMY_SP; // FIXME
-            let result = match tcx.dtorck_constraint_for_ty(span, dropped_ty, depth, ty) {
-                Ok(result) => result,
-                Err(ErrorReported) => {
-                    continue;
-                }
-            };
-
-            let ty::DtorckConstraint {
-                outlives,
-                dtorck_types,
-            } = result;
-
-            // All things in the `outlives` array may be touched by
-            // the destructor and must be live at this point.
-            for outlive in outlives {
-                let cause = Cause::DropVar(dropped_local, location);
-                self.push_type_live_constraint(outlive, location, cause);
-            }
+        // If we end visiting the same type twice (usually due to a cycle involving
+        // associated types), we need to ensure that its region types match up with the type
+        // we added to the 'known' map the first time around. For this reason, we need
+        // our infcx to hold onto its calculated region constraints after each call
+        // to dtorck_constraint_for_ty. Otherwise, normalizing the corresponding associated
+        // type will end up instantiating the type with a new set of inference variables
+        // Since this new type will never be in 'known', we end up looping forever.
+        //
+        // For this reason, we avoid calling TypeChecker.normalize, instead doing all normalization
+        // ourselves in one large 'fully_perform_op' callback.
+        let (type_constraints, kind_constraints) = self.cx.fully_perform_op(location.at_self(),
+            |cx| {
+
+            let tcx = cx.infcx.tcx;
+            let mut selcx = traits::SelectionContext::new(cx.infcx);
+            let cause = cx.misc(cx.last_span);
+
+            let mut types = vec![(dropped_ty, 0)];
+            let mut final_obligations = Vec::new();
+            let mut type_constraints = Vec::new();
+            let mut kind_constraints = Vec::new();
 
-            // However, there may also be some types that
-            // `dtorck_constraint_for_ty` could not resolve (e.g.,
-            // associated types and parameters). We need to normalize
-            // associated types here and possibly recursively process.
-            for ty in dtorck_types {
-                let ty = self.cx.normalize(&ty, location);
-                let ty = self.cx.infcx.resolve_type_and_region_vars_if_possible(&ty);
-                match ty.sty {
-                    ty::TyParam(..) | ty::TyProjection(..) | ty::TyAnon(..) => {
-                        let cause = Cause::DropVar(dropped_local, location);
-                        self.push_type_live_constraint(ty, location, cause);
+            let mut known = FxHashSet();
+
+            while let Some((ty, depth)) = types.pop() {
+                let span = DUMMY_SP; // FIXME
+                let result = match tcx.dtorck_constraint_for_ty(span, dropped_ty, depth, ty) {
+                    Ok(result) => result,
+                    Err(ErrorReported) => {
+                        continue;
                     }
+                };
+
+                let ty::DtorckConstraint {
+                    outlives,
+                    dtorck_types,
+                } = result;
+
+                // All things in the `outlives` array may be touched by
+                // the destructor and must be live at this point.
+                for outlive in outlives {
+                    let cause = Cause::DropVar(dropped_local, location);
+                    kind_constraints.push((outlive, location, cause));
+                }
 
-                    _ => if known.insert(ty) {
-                        types.push((ty, depth + 1));
-                    },
+                // However, there may also be some types that
+                // `dtorck_constraint_for_ty` could not resolve (e.g.,
+                // associated types and parameters). We need to normalize
+                // associated types here and possibly recursively process.
+                for ty in dtorck_types {
+                    let traits::Normalized { value: ty, obligations } =
+                        traits::normalize(&mut selcx, cx.param_env, cause.clone(), &ty);
+
+                    final_obligations.extend(obligations);
+
+                    //let ty = self.cx.normalize(&ty, location);
+                    let ty = cx.infcx.resolve_type_and_region_vars_if_possible(&ty);
+                    match ty.sty {
+                        ty::TyParam(..) | ty::TyProjection(..) | ty::TyAnon(..) => {
+                            let cause = Cause::DropVar(dropped_local, location);
+                            type_constraints.push((ty, location, cause));
+                        }
+
+                        _ => if known.insert(ty) {
+                            types.push((ty, depth + 1));
+                        },
+                    }
                 }
             }
+
+            Ok(InferOk {
+                value: (type_constraints, kind_constraints), obligations: final_obligations
+            })
+        }).unwrap();
+
+        for (ty, location, cause) in type_constraints {
+            self.push_type_live_constraint(ty, location, cause);
+        }
+
+        for (kind, location, cause) in kind_constraints {
+            self.push_type_live_constraint(kind, location, cause);
         }
     }
 }
diff --git a/src/test/run-pass/nll/issue-47589.rs b/src/test/run-pass/nll/issue-47589.rs
new file mode 100644
index 00000000000..393c18efad0
--- /dev/null
+++ b/src/test/run-pass/nll/issue-47589.rs
@@ -0,0 +1,33 @@
+// Copyright 2018 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.
+
+#![feature(nll)]
+
+pub struct DescriptorSet<'a> {
+    pub slots: Vec<AttachInfo<'a, Resources>>
+}
+
+pub trait ResourcesTrait<'r>: Sized {
+    type DescriptorSet: 'r;
+}
+
+pub struct Resources;
+
+impl<'a> ResourcesTrait<'a> for Resources {
+    type DescriptorSet = DescriptorSet<'a>;
+}
+
+pub enum AttachInfo<'a, R: ResourcesTrait<'a>> {
+    NextDescriptorSet(Box<R::DescriptorSet>)
+}
+
+fn main() {
+    let _x = DescriptorSet {slots: Vec::new()};
+}