Auto merge of #37294 - nikomatsakis:issue-37154, r=nikomatsakis

remove keys w/ skolemized regions from proj cache when popping skolemized regions

This addresses #37154 (a regression). The projection cache was incorrectly caching the results for skolemized regions -- when we pop skolemized regions, we are supposed to drop cache keys for them (just as we remove those skolemized regions from the region inference graph). This is because those skolemized region numbers will be reused later with different meaning (and we have determined that the old ones don't leak out in any meaningful way).

I did a *somewhat* aggressive fix here of only removing keys that mention the skolemized regions. One could imagine just removing all keys added since we started the skolemization (as indeed I did in my initial commit). This more aggressive fix required fixing a latent bug in `TypeFlags`, as an aside.

I believe the more aggressive fix is correct; clearly there can be entries that are unrelated to the skoelemized region, and it's a shame to remove them. My one concern was that it *is* possible I believe to have some region variables that are created and related to skolemized regions, and maybe some of them could end up in the cache. However, that seems harmless enough to me-- those relations will be removed, and couldn't have impacted how trait resolution proceeded anyway (iow, the cache entry is not wrong, though it is kind of useless).

r? @pnkfelix
cc @arielb1

8 files changed, 130 insertions, 53 deletions

diff --git a/src/librustc/infer/higher_ranked/mod.rs b/src/librustc/infer/higher_ranked/mod.rs
index c1d9240ba06..25b899b3c56 100644
--- a/src/librustc/infer/higher_ranked/mod.rs
+++ b/src/librustc/infer/higher_ranked/mod.rs
@@ -839,5 +839,9 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         debug!("pop_skolemized({:?})", skol_map);
         let skol_regions: FnvHashSet<_> = skol_map.values().cloned().collect();
         self.region_vars.pop_skolemized(&skol_regions, &snapshot.region_vars_snapshot);
+        if !skol_map.is_empty() {
+            self.projection_cache.borrow_mut().rollback_skolemized(
+                &snapshot.projection_cache_snapshot);
+        }
     }
 }
diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index 27554c0d2a4..f1f1658cc82 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -167,7 +167,7 @@ pub fn poly_project_and_unify_type<'cx, 'gcx, 'tcx>(
             infcx.skolemize_late_bound_regions(&obligation.predicate, snapshot);
 
         let skol_obligation = obligation.with(skol_predicate);
-        match project_and_unify_type(selcx, &skol_obligation) {
+        let r = match project_and_unify_type(selcx, &skol_obligation) {
             Ok(result) => {
                 let span = obligation.cause.span;
                 match infcx.leak_check(false, span, &skol_map, snapshot) {
@@ -178,7 +178,9 @@ pub fn poly_project_and_unify_type<'cx, 'gcx, 'tcx>(
             Err(e) => {
                 Err(e)
             }
-        }
+        };
+
+        r
     })
 }
 
@@ -1396,6 +1398,10 @@ impl<'tcx> ProjectionCache<'tcx> {
         self.map.rollback_to(snapshot.snapshot);
     }
 
+    pub fn rollback_skolemized(&mut self, snapshot: &ProjectionCacheSnapshot) {
+        self.map.partial_rollback(&snapshot.snapshot, &|k| k.has_re_skol());
+    }
+
     pub fn commit(&mut self, snapshot: ProjectionCacheSnapshot) {
         self.map.commit(snapshot.snapshot);
     }
diff --git a/src/librustc/ty/flags.rs b/src/librustc/ty/flags.rs
index 1434b0e60e2..649d78f9d9e 100644
--- a/src/librustc/ty/flags.rs
+++ b/src/librustc/ty/flags.rs
@@ -11,6 +11,7 @@
 use ty::subst::Substs;
 use ty::{self, Ty, TypeFlags, TypeFoldable};
 
+#[derive(Debug)]
 pub struct FlagComputation {
     pub flags: TypeFlags,
 
@@ -182,24 +183,9 @@ impl FlagComputation {
     }
 
     fn add_region(&mut self, r: &ty::Region) {
-        match *r {
-            ty::ReVar(..) => {
-                self.add_flags(TypeFlags::HAS_RE_INFER);
-                self.add_flags(TypeFlags::KEEP_IN_LOCAL_TCX);
-            }
-            ty::ReSkolemized(..) => {
-                self.add_flags(TypeFlags::HAS_RE_INFER);
-                self.add_flags(TypeFlags::HAS_RE_SKOL);
-                self.add_flags(TypeFlags::KEEP_IN_LOCAL_TCX);
-            }
-            ty::ReLateBound(debruijn, _) => { self.add_depth(debruijn.depth); }
-            ty::ReEarlyBound(..) => { self.add_flags(TypeFlags::HAS_RE_EARLY_BOUND); }
-            ty::ReStatic | ty::ReErased => {}
-            _ => { self.add_flags(TypeFlags::HAS_FREE_REGIONS); }
-        }
-
-        if !r.is_global() {
-            self.add_flags(TypeFlags::HAS_LOCAL_NAMES);
+        self.add_flags(r.type_flags());
+        if let ty::ReLateBound(debruijn, _) = *r {
+            self.add_depth(debruijn.depth);
         }
     }
 
diff --git a/src/librustc/ty/fold.rs b/src/librustc/ty/fold.rs
index 886ad8cd861..ae0a4a0e6bd 100644
--- a/src/librustc/ty/fold.rs
+++ b/src/librustc/ty/fold.rs
@@ -91,6 +91,9 @@ pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
     fn needs_subst(&self) -> bool {
         self.has_type_flags(TypeFlags::NEEDS_SUBST)
     }
+    fn has_re_skol(&self) -> bool {
+        self.has_type_flags(TypeFlags::HAS_RE_SKOL)
+    }
     fn has_closure_types(&self) -> bool {
         self.has_type_flags(TypeFlags::HAS_TY_CLOSURE)
     }
@@ -632,26 +635,15 @@ struct HasTypeFlagsVisitor {
 
 impl<'tcx> TypeVisitor<'tcx> for HasTypeFlagsVisitor {
     fn visit_ty(&mut self, t: Ty) -> bool {
-        t.flags.get().intersects(self.flags)
+        let flags = t.flags.get();
+        debug!("HasTypeFlagsVisitor: t={:?} t.flags={:?} self.flags={:?}", t, flags, self.flags);
+        flags.intersects(self.flags)
     }
 
     fn visit_region(&mut self, r: &'tcx ty::Region) -> bool {
-        if self.flags.intersects(ty::TypeFlags::HAS_LOCAL_NAMES) {
-            // does this represent a region that cannot be named
-            // in a global way? used in fulfillment caching.
-            match *r {
-                ty::ReStatic | ty::ReEmpty | ty::ReErased => {}
-                _ => return true,
-            }
-        }
-        if self.flags.intersects(ty::TypeFlags::HAS_RE_INFER |
-                                 ty::TypeFlags::KEEP_IN_LOCAL_TCX) {
-            match *r {
-                ty::ReVar(_) | ty::ReSkolemized(..) => { return true }
-                _ => {}
-            }
-        }
-        false
+        let flags = r.type_flags();
+        debug!("HasTypeFlagsVisitor: r={:?} r.flags={:?} self.flags={:?}", r, flags, self.flags);
+        flags.intersects(self.flags)
     }
 }
 
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 018f01e5913..eca699a393d 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -477,6 +477,7 @@ bitflags! {
                                   TypeFlags::HAS_SELF.bits |
                                   TypeFlags::HAS_TY_INFER.bits |
                                   TypeFlags::HAS_RE_INFER.bits |
+                                  TypeFlags::HAS_RE_SKOL.bits |
                                   TypeFlags::HAS_RE_EARLY_BOUND.bits |
                                   TypeFlags::HAS_FREE_REGIONS.bits |
                                   TypeFlags::HAS_TY_ERR.bits |
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 302cab0446c..92dfb883ef3 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -406,7 +406,7 @@ impl<T> Binder<T> {
 
 impl fmt::Debug for TypeFlags {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "{}", self.bits)
+        write!(f, "{:x}", self.bits)
     }
 }
 
@@ -866,6 +866,35 @@ impl Region {
             r => r
         }
     }
+
+    pub fn type_flags(&self) -> TypeFlags {
+        let mut flags = TypeFlags::empty();
+
+        match *self {
+            ty::ReVar(..) => {
+                flags = flags | TypeFlags::HAS_RE_INFER;
+                flags = flags | TypeFlags::KEEP_IN_LOCAL_TCX;
+            }
+            ty::ReSkolemized(..) => {
+                flags = flags | TypeFlags::HAS_RE_INFER;
+                flags = flags | TypeFlags::HAS_RE_SKOL;
+                flags = flags | TypeFlags::KEEP_IN_LOCAL_TCX;
+            }
+            ty::ReLateBound(..) => { }
+            ty::ReEarlyBound(..) => { flags = flags | TypeFlags::HAS_RE_EARLY_BOUND; }
+            ty::ReStatic | ty::ReErased => { }
+            _ => { flags = flags | TypeFlags::HAS_FREE_REGIONS; }
+        }
+
+        match *self {
+            ty::ReStatic | ty::ReEmpty | ty::ReErased => (),
+            _ => flags = flags | TypeFlags::HAS_LOCAL_NAMES,
+        }
+
+        debug!("type_flags({:?}) = {:?}", self, flags);
+
+        flags
+    }
 }
 
 // Type utilities
diff --git a/src/librustc_data_structures/snapshot_map/mod.rs b/src/librustc_data_structures/snapshot_map/mod.rs
index 0306066d6e7..a4e6166032d 100644
--- a/src/librustc_data_structures/snapshot_map/mod.rs
+++ b/src/librustc_data_structures/snapshot_map/mod.rs
@@ -11,6 +11,7 @@
 use fnv::FnvHashMap;
 use std::hash::Hash;
 use std::ops;
+use std::mem;
 
 #[cfg(test)]
 mod test;
@@ -31,6 +32,7 @@ enum UndoLog<K, V> {
     CommittedSnapshot,
     Inserted(K),
     Overwrite(K, V),
+    Noop,
 }
 
 impl<K, V> SnapshotMap<K, V>
@@ -100,24 +102,33 @@ impl<K, V> SnapshotMap<K, V>
         }
     }
 
+    pub fn partial_rollback<F>(&mut self,
+                               snapshot: &Snapshot,
+                               should_revert_key: &F)
+        where F: Fn(&K) -> bool
+    {
+        self.assert_open_snapshot(snapshot);
+        for i in (snapshot.len + 1..self.undo_log.len()).rev() {
+            let reverse = match self.undo_log[i] {
+                UndoLog::OpenSnapshot => false,
+                UndoLog::CommittedSnapshot => false,
+                UndoLog::Noop => false,
+                UndoLog::Inserted(ref k) => should_revert_key(k),
+                UndoLog::Overwrite(ref k, _) => should_revert_key(k),
+            };
+
+            if reverse {
+                let entry = mem::replace(&mut self.undo_log[i], UndoLog::Noop);
+                self.reverse(entry);
+            }
+        }
+    }
+
     pub fn rollback_to(&mut self, snapshot: Snapshot) {
         self.assert_open_snapshot(&snapshot);
         while self.undo_log.len() > snapshot.len + 1 {
-            match self.undo_log.pop().unwrap() {
-                UndoLog::OpenSnapshot => {
-                    panic!("cannot rollback an uncommitted snapshot");
-                }
-
-                UndoLog::CommittedSnapshot => {}
-
-                UndoLog::Inserted(key) => {
-                    self.map.remove(&key);
-                }
-
-                UndoLog::Overwrite(key, old_value) => {
-                    self.map.insert(key, old_value);
-                }
-            }
+            let entry = self.undo_log.pop().unwrap();
+            self.reverse(entry);
         }
 
         let v = self.undo_log.pop().unwrap();
@@ -127,6 +138,26 @@ impl<K, V> SnapshotMap<K, V>
         });
         assert!(self.undo_log.len() == snapshot.len);
     }
+
+    fn reverse(&mut self, entry: UndoLog<K, V>) {
+        match entry {
+            UndoLog::OpenSnapshot => {
+                panic!("cannot rollback an uncommitted snapshot");
+            }
+
+            UndoLog::CommittedSnapshot => {}
+
+            UndoLog::Inserted(key) => {
+                self.map.remove(&key);
+            }
+
+            UndoLog::Overwrite(key, old_value) => {
+                self.map.insert(key, old_value);
+            }
+
+            UndoLog::Noop => {}
+        }
+    }
 }
 
 impl<'k, K, V> ops::Index<&'k K> for SnapshotMap<K, V>
diff --git a/src/test/run-pass/project-cache-issue-37154.rs b/src/test/run-pass/project-cache-issue-37154.rs
new file mode 100644
index 00000000000..29dc6984e23
--- /dev/null
+++ b/src/test/run-pass/project-cache-issue-37154.rs
@@ -0,0 +1,28 @@
+// 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.
+
+// Regression test for #37154: the problem here was that the cache
+// results in a false error because it was caching skolemized results
+// even after those skolemized regions had been popped.
+
+trait Foo {
+    fn method(&self) {}
+}
+
+struct Wrapper<T>(T);
+
+impl<T> Foo for Wrapper<T> where for<'a> &'a T: IntoIterator<Item=&'a ()> {}
+
+fn f(x: Wrapper<Vec<()>>) {
+    x.method(); // This works.
+    x.method(); // error: no method named `method`
+}
+
+fn main() { }