introduce a region unification table and use it in dropck

Fixes #29844

6 files changed, 123 insertions, 11 deletions

diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs
index b39ddfe95c8..d677328e415 100644
--- a/src/librustc/middle/infer/mod.rs
+++ b/src/librustc/middle/infer/mod.rs
@@ -1225,6 +1225,13 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         value.fold_with(&mut r)
     }
 
+    pub fn resolve_type_and_region_vars_if_possible<T>(&self, value: &T) -> T
+        where T: TypeFoldable<'tcx>
+    {
+        let mut r = resolve::OpportunisticTypeAndRegionResolver::new(self);
+        value.fold_with(&mut r)
+    }
+
     /// Resolves all type variables in `t` and then, if any were left
     /// unresolved, substitutes an error type. This is used after the
     /// main checking when doing a second pass before writeback. The
diff --git a/src/librustc/middle/infer/region_inference/mod.rs b/src/librustc/middle/infer/region_inference/mod.rs
index f6068f1b644..30cf6344e23 100644
--- a/src/librustc/middle/infer/region_inference/mod.rs
+++ b/src/librustc/middle/infer/region_inference/mod.rs
@@ -20,6 +20,7 @@ pub use self::VarValue::*;
 use super::{RegionVariableOrigin, SubregionOrigin, TypeTrace, MiscVariable};
 
 use rustc_data_structures::graph::{self, Direction, NodeIndex};
+use rustc_data_structures::unify::{self, UnificationTable};
 use middle::free_region::FreeRegionMap;
 use middle::ty::{self, Ty};
 use middle::ty::{BoundRegion, FreeRegion, Region, RegionVid};
@@ -234,15 +235,16 @@ pub struct RegionVarBindings<'a, 'tcx: 'a> {
     // bound on a variable and so forth, which can never be rolled
     // back.
     undo_log: RefCell<Vec<UndoLogEntry>>,
+    unification_table: RefCell<UnificationTable<ty::RegionVid>>,
 
     // This contains the results of inference.  It begins as an empty
     // option and only acquires a value after inference is complete.
     values: RefCell<Option<Vec<VarValue>>>,
 }
 
-#[derive(Debug)]
 pub struct RegionSnapshot {
     length: usize,
+    region_snapshot: unify::Snapshot<ty::RegionVid>,
     skolemization_count: u32,
 }
 
@@ -260,6 +262,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
             skolemization_count: Cell::new(0),
             bound_count: Cell::new(0),
             undo_log: RefCell::new(Vec::new()),
+            unification_table: RefCell::new(UnificationTable::new()),
         }
     }
 
@@ -273,6 +276,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         self.undo_log.borrow_mut().push(OpenSnapshot);
         RegionSnapshot {
             length: length,
+            region_snapshot: self.unification_table.borrow_mut().snapshot(),
             skolemization_count: self.skolemization_count.get(),
         }
     }
@@ -289,6 +293,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
             (*undo_log)[snapshot.length] = CommitedSnapshot;
         }
         self.skolemization_count.set(snapshot.skolemization_count);
+        self.unification_table.borrow_mut().commit(snapshot.region_snapshot);
     }
 
     pub fn rollback_to(&self, snapshot: RegionSnapshot) {
@@ -328,6 +333,8 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         let c = undo_log.pop().unwrap();
         assert!(c == OpenSnapshot);
         self.skolemization_count.set(snapshot.skolemization_count);
+        self.unification_table.borrow_mut()
+            .rollback_to(snapshot.region_snapshot);
     }
 
     pub fn num_vars(&self) -> u32 {
@@ -340,7 +347,8 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     pub fn new_region_var(&self, origin: RegionVariableOrigin) -> RegionVid {
         let id = self.num_vars();
         self.var_origins.borrow_mut().push(origin.clone());
-        let vid = RegionVid { index: id };
+        let vid = self.unification_table.borrow_mut().new_key(());
+        assert_eq!(vid.index, id);
         if self.in_snapshot() {
             self.undo_log.borrow_mut().push(AddVar(vid));
         }
@@ -460,6 +468,10 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
             // equating regions.
             self.make_subregion(origin.clone(), sub, sup);
             self.make_subregion(origin, sup, sub);
+
+            if let (ty::ReVar(sub), ty::ReVar(sup)) = (sub, sup) {
+                self.unification_table.borrow_mut().union(sub, sup);
+            }
         }
     }
 
@@ -568,6 +580,10 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         }
     }
 
+    pub fn opportunistic_resolve_var(&self, rid: RegionVid) -> ty::Region {
+        ty::ReVar(self.unification_table.borrow_mut().find(rid))
+    }
+
     fn combine_map(&self, t: CombineMapType) -> &RefCell<CombineMap> {
         match t {
             Glb => &self.glbs,
@@ -1312,6 +1328,13 @@ impl<'tcx> fmt::Debug for RegionAndOrigin<'tcx> {
     }
 }
 
+impl fmt::Debug for RegionSnapshot {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "RegionSnapshot(length={},skolemization={})",
+               self.length, self.skolemization_count)
+    }
+}
+
 impl<'tcx> fmt::Debug for GenericKind<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         match *self {
diff --git a/src/librustc/middle/infer/resolve.rs b/src/librustc/middle/infer/resolve.rs
index 4bcceade775..5190c658194 100644
--- a/src/librustc/middle/infer/resolve.rs
+++ b/src/librustc/middle/infer/resolve.rs
@@ -45,6 +45,41 @@ impl<'a, 'tcx> ty::fold::TypeFolder<'tcx> for OpportunisticTypeResolver<'a, 'tcx
     }
 }
 
+/// The opportunistic type and region resolver is similar to the
+/// opportunistic type resolver, but also opportunistly resolves
+/// regions. It is useful for canonicalization.
+pub struct OpportunisticTypeAndRegionResolver<'a, 'tcx:'a> {
+    infcx: &'a InferCtxt<'a, 'tcx>,
+}
+
+impl<'a, 'tcx> OpportunisticTypeAndRegionResolver<'a, 'tcx> {
+    pub fn new(infcx: &'a InferCtxt<'a, 'tcx>) -> Self {
+        OpportunisticTypeAndRegionResolver { infcx: infcx }
+    }
+}
+
+impl<'a, 'tcx> ty::fold::TypeFolder<'tcx> for OpportunisticTypeAndRegionResolver<'a, 'tcx> {
+    fn tcx(&self) -> &ty::ctxt<'tcx> {
+        self.infcx.tcx
+    }
+
+    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
+        if !t.needs_infer() {
+            t // micro-optimize -- if there is nothing in this type that this fold affects...
+        } else {
+            let t0 = self.infcx.shallow_resolve(t);
+            ty::fold::super_fold_ty(self, t0)
+        }
+    }
+
+    fn fold_region(&mut self, r: ty::Region) -> ty::Region {
+        match r {
+          ty::ReVar(rid) => self.infcx.region_vars.opportunistic_resolve_var(rid),
+          _ => r,
+        }
+    }
+}
+
 ///////////////////////////////////////////////////////////////////////////
 // FULL TYPE RESOLUTION
 
diff --git a/src/librustc/middle/infer/unify_key.rs b/src/librustc/middle/infer/unify_key.rs
index 41aa191ac24..85d7d67a0e3 100644
--- a/src/librustc/middle/infer/unify_key.rs
+++ b/src/librustc/middle/infer/unify_key.rs
@@ -23,6 +23,13 @@ impl UnifyKey for ty::IntVid {
     fn tag(_: Option<ty::IntVid>) -> &'static str { "IntVid" }
 }
 
+impl UnifyKey for ty::RegionVid {
+    type Value = ();
+    fn index(&self) -> u32 { self.index }
+    fn from_index(i: u32) -> ty::RegionVid { ty::RegionVid { index: i } }
+    fn tag(_: Option<ty::RegionVid>) -> &'static str { "RegionVid" }
+}
+
 impl<'tcx> ToType<'tcx> for IntVarValue {
     fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
         match *self {
diff --git a/src/librustc_typeck/check/dropck.rs b/src/librustc_typeck/check/dropck.rs
index d68959b99be..0fbe8367493 100644
--- a/src/librustc_typeck/check/dropck.rs
+++ b/src/librustc_typeck/check/dropck.rs
@@ -17,7 +17,6 @@ use middle::region;
 use middle::subst::{self, Subst};
 use middle::traits;
 use middle::ty::{self, Ty};
-use util::nodemap::FnvHashSet;
 
 use syntax::ast;
 use syntax::codemap::{self, Span};
@@ -280,7 +279,7 @@ pub fn check_safety_of_destructor_if_necessary<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>
             rcx: rcx,
             span: span,
             parent_scope: parent_scope,
-            breadcrumbs: FnvHashSet()
+            breadcrumbs: Vec::new(),
         },
         TypeContext::Root,
         typ,
@@ -341,7 +340,7 @@ enum TypeContext {
 struct DropckContext<'a, 'b: 'a, 'tcx: 'b> {
     rcx: &'a mut Rcx<'b, 'tcx>,
     /// types that have already been traversed
-    breadcrumbs: FnvHashSet<Ty<'tcx>>,
+    breadcrumbs: Vec<Ty<'tcx>>,
     /// span for error reporting
     span: Span,
     /// the scope reachable dtorck types must outlive
@@ -356,6 +355,8 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'b, 'tcx>(
     depth: usize) -> Result<(), Error<'tcx>>
 {
     let tcx = cx.rcx.tcx();
+    let ty = cx.rcx.infcx().resolve_type_and_region_vars_if_possible(&ty);
+
     // Issue #22443: Watch out for overflow. While we are careful to
     // handle regular types properly, non-regular ones cause problems.
     let recursion_limit = tcx.sess.recursion_limit.get();
@@ -366,13 +367,19 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'b, 'tcx>(
         return Err(Error::Overflow(context, ty))
     }
 
-    if !cx.breadcrumbs.insert(ty) {
-        debug!("iterate_over_potentially_unsafe_regions_in_type \
-               {}ty: {} scope: {:?} - cached",
-               (0..depth).map(|_| ' ').collect::<String>(),
-               ty, cx.parent_scope);
-        return Ok(()); // we already visited this type
+    for breadcrumb in &mut cx.breadcrumbs {
+        *breadcrumb =
+            cx.rcx.infcx().resolve_type_and_region_vars_if_possible(breadcrumb);
+        if *breadcrumb == ty {
+            debug!("iterate_over_potentially_unsafe_regions_in_type \
+                   {}ty: {} scope: {:?} - cached",
+                   (0..depth).map(|_| ' ').collect::<String>(),
+                   ty, cx.parent_scope);
+            return Ok(()); // we already visited this type
+        }
     }
+    cx.breadcrumbs.push(ty);
+
     debug!("iterate_over_potentially_unsafe_regions_in_type \
            {}ty: {} scope: {:?}",
            (0..depth).map(|_| ' ').collect::<String>(),
diff --git a/src/test/run-pass/issue-29844.rs b/src/test/run-pass/issue-29844.rs
new file mode 100644
index 00000000000..51df4d60f04
--- /dev/null
+++ b/src/test/run-pass/issue-29844.rs
@@ -0,0 +1,33 @@
+// Copyright 2015 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 std::sync::Arc;
+
+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(Arc<R::DescriptorSet>)
+}
+
+fn main() {
+    let _x = DescriptorSet {slots: Vec::new()};
+}