Auto merge of #32794 - Manishearth:rollup, r=Manishearth

Rollup of 7 pull requests

- Successful merges: #32674, #32699, #32711, #32745, #32748, #32757, #32789
- Failed merges:

53 files changed, 815 insertions, 521 deletions

diff --git a/src/liballoc/arc.rs b/src/liballoc/arc.rs
index 055029dddcd..e1f698cb484 100644
--- a/src/liballoc/arc.rs
+++ b/src/liballoc/arc.rs
@@ -263,6 +263,7 @@ impl<T: ?Sized> Arc<T> {
         loop {
             // check if the weak counter is currently "locked"; if so, spin.
             if cur == usize::MAX {
+                cur = this.inner().weak.load(Relaxed);
                 continue;
             }
 
diff --git a/src/libcollectionstest/slice.rs b/src/libcollectionstest/slice.rs
index ca2ee0c512b..236c151891d 100644
--- a/src/libcollectionstest/slice.rs
+++ b/src/libcollectionstest/slice.rs
@@ -574,18 +574,48 @@ fn test_slice_2() {
     assert_eq!(v[1], 3);
 }
 
+macro_rules! assert_order {
+    (Greater, $a:expr, $b:expr) => {
+        assert_eq!($a.cmp($b), Greater);
+        assert!($a > $b);
+    };
+    (Less, $a:expr, $b:expr) => {
+        assert_eq!($a.cmp($b), Less);
+        assert!($a < $b);
+    };
+    (Equal, $a:expr, $b:expr) => {
+        assert_eq!($a.cmp($b), Equal);
+        assert_eq!($a, $b);
+    }
+}
+
+#[test]
+fn test_total_ord_u8() {
+    let c = &[1u8, 2, 3];
+    assert_order!(Greater, &[1u8, 2, 3, 4][..], &c[..]);
+    let c = &[1u8, 2, 3, 4];
+    assert_order!(Less, &[1u8, 2, 3][..], &c[..]);
+    let c = &[1u8, 2, 3, 6];
+    assert_order!(Equal, &[1u8, 2, 3, 6][..], &c[..]);
+    let c = &[1u8, 2, 3, 4, 5, 6];
+    assert_order!(Less, &[1u8, 2, 3, 4, 5, 5, 5, 5][..], &c[..]);
+    let c = &[1u8, 2, 3, 4];
+    assert_order!(Greater, &[2u8, 2][..], &c[..]);
+}
+
+
 #[test]
-fn test_total_ord() {
+fn test_total_ord_i32() {
     let c = &[1, 2, 3];
-    [1, 2, 3, 4][..].cmp(c) == Greater;
+    assert_order!(Greater, &[1, 2, 3, 4][..], &c[..]);
     let c = &[1, 2, 3, 4];
-    [1, 2, 3][..].cmp(c) == Less;
+    assert_order!(Less, &[1, 2, 3][..], &c[..]);
     let c = &[1, 2, 3, 6];
-    [1, 2, 3, 4][..].cmp(c) == Equal;
+    assert_order!(Equal, &[1, 2, 3, 6][..], &c[..]);
     let c = &[1, 2, 3, 4, 5, 6];
-    [1, 2, 3, 4, 5, 5, 5, 5][..].cmp(c) == Less;
+    assert_order!(Less, &[1, 2, 3, 4, 5, 5, 5, 5][..], &c[..]);
     let c = &[1, 2, 3, 4];
-    [2, 2][..].cmp(c) == Greater;
+    assert_order!(Greater, &[2, 2][..], &c[..]);
 }
 
 #[test]
diff --git a/src/libcore/lib.rs b/src/libcore/lib.rs
index 648b652772a..fa5e90562d8 100644
--- a/src/libcore/lib.rs
+++ b/src/libcore/lib.rs
@@ -75,6 +75,7 @@
 #![feature(unwind_attributes)]
 #![feature(repr_simd, platform_intrinsics)]
 #![feature(rustc_attrs)]
+#![feature(specialization)]
 #![feature(staged_api)]
 #![feature(unboxed_closures)]
 #![feature(question_mark)]
diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs
index aa555b44e89..25082eed2fe 100644
--- a/src/libcore/slice.rs
+++ b/src/libcore/slice.rs
@@ -1630,12 +1630,60 @@ pub unsafe fn from_raw_parts_mut<'a, T>(p: *mut T, len: usize) -> &'a mut [T] {
 }
 
 //
-// Boilerplate traits
+// Comparison traits
 //
 
+extern {
+    /// Call implementation provided memcmp
+    ///
+    /// Interprets the data as u8.
+    ///
+    /// Return 0 for equal, < 0 for less than and > 0 for greater
+    /// than.
+    // FIXME(#32610): Return type should be c_int
+    fn memcmp(s1: *const u8, s2: *const u8, n: usize) -> i32;
+}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
     fn eq(&self, other: &[B]) -> bool {
+        SlicePartialEq::equal(self, other)
+    }
+
+    fn ne(&self, other: &[B]) -> bool {
+        SlicePartialEq::not_equal(self, other)
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: Eq> Eq for [T] {}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: Ord> Ord for [T] {
+    fn cmp(&self, other: &[T]) -> Ordering {
+        SliceOrd::compare(self, other)
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T: PartialOrd> PartialOrd for [T] {
+    fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
+        SlicePartialOrd::partial_compare(self, other)
+    }
+}
+
+#[doc(hidden)]
+// intermediate trait for specialization of slice's PartialEq
+trait SlicePartialEq<B> {
+    fn equal(&self, other: &[B]) -> bool;
+    fn not_equal(&self, other: &[B]) -> bool;
+}
+
+// Generic slice equality
+impl<A, B> SlicePartialEq<B> for [A]
+    where A: PartialEq<B>
+{
+    default fn equal(&self, other: &[B]) -> bool {
         if self.len() != other.len() {
             return false;
         }
@@ -1648,7 +1696,8 @@ impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
 
         true
     }
-    fn ne(&self, other: &[B]) -> bool {
+
+    default fn not_equal(&self, other: &[B]) -> bool {
         if self.len() != other.len() {
             return true;
         }
@@ -1663,12 +1712,36 @@ impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<T: Eq> Eq for [T] {}
+// Use memcmp for bytewise equality when the types allow
+impl<A> SlicePartialEq<A> for [A]
+    where A: PartialEq<A> + BytewiseEquality
+{
+    fn equal(&self, other: &[A]) -> bool {
+        if self.len() != other.len() {
+            return false;
+        }
+        unsafe {
+            let size = mem::size_of_val(self);
+            memcmp(self.as_ptr() as *const u8,
+                   other.as_ptr() as *const u8, size) == 0
+        }
+    }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<T: Ord> Ord for [T] {
-    fn cmp(&self, other: &[T]) -> Ordering {
+    fn not_equal(&self, other: &[A]) -> bool {
+        !self.equal(other)
+    }
+}
+
+#[doc(hidden)]
+// intermediate trait for specialization of slice's PartialOrd
+trait SlicePartialOrd<B> {
+    fn partial_compare(&self, other: &[B]) -> Option<Ordering>;
+}
+
+impl<A> SlicePartialOrd<A> for [A]
+    where A: PartialOrd
+{
+    default fn partial_compare(&self, other: &[A]) -> Option<Ordering> {
         let l = cmp::min(self.len(), other.len());
 
         // Slice to the loop iteration range to enable bound check
@@ -1677,19 +1750,33 @@ impl<T: Ord> Ord for [T] {
         let rhs = &other[..l];
 
         for i in 0..l {
-            match lhs[i].cmp(&rhs[i]) {
-                Ordering::Equal => (),
+            match lhs[i].partial_cmp(&rhs[i]) {
+                Some(Ordering::Equal) => (),
                 non_eq => return non_eq,
             }
         }
 
-        self.len().cmp(&other.len())
+        self.len().partial_cmp(&other.len())
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<T: PartialOrd> PartialOrd for [T] {
-    fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
+impl SlicePartialOrd<u8> for [u8] {
+    #[inline]
+    fn partial_compare(&self, other: &[u8]) -> Option<Ordering> {
+        Some(SliceOrd::compare(self, other))
+    }
+}
+
+#[doc(hidden)]
+// intermediate trait for specialization of slice's Ord
+trait SliceOrd<B> {
+    fn compare(&self, other: &[B]) -> Ordering;
+}
+
+impl<A> SliceOrd<A> for [A]
+    where A: Ord
+{
+    default fn compare(&self, other: &[A]) -> Ordering {
         let l = cmp::min(self.len(), other.len());
 
         // Slice to the loop iteration range to enable bound check
@@ -1698,12 +1785,48 @@ impl<T: PartialOrd> PartialOrd for [T] {
         let rhs = &other[..l];
 
         for i in 0..l {
-            match lhs[i].partial_cmp(&rhs[i]) {
-                Some(Ordering::Equal) => (),
+            match lhs[i].cmp(&rhs[i]) {
+                Ordering::Equal => (),
                 non_eq => return non_eq,
             }
         }
 
-        self.len().partial_cmp(&other.len())
+        self.len().cmp(&other.len())
     }
 }
+
+// memcmp compares a sequence of unsigned bytes lexicographically.
+// this matches the order we want for [u8], but no others (not even [i8]).
+impl SliceOrd<u8> for [u8] {
+    #[inline]
+    fn compare(&self, other: &[u8]) -> Ordering {
+        let order = unsafe {
+            memcmp(self.as_ptr(), other.as_ptr(),
+                   cmp::min(self.len(), other.len()))
+        };
+        if order == 0 {
+            self.len().cmp(&other.len())
+        } else if order < 0 {
+            Less
+        } else {
+            Greater
+        }
+    }
+}
+
+#[doc(hidden)]
+/// Trait implemented for types that can be compared for equality using
+/// their bytewise representation
+trait BytewiseEquality { }
+
+macro_rules! impl_marker_for {
+    ($traitname:ident, $($ty:ty)*) => {
+        $(
+            impl $traitname for $ty { }
+        )*
+    }
+}
+
+impl_marker_for!(BytewiseEquality,
+                 u8 i8 u16 i16 u32 i32 u64 i64 usize isize char bool);
+
diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index d5a5e2b4741..305546df5be 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -1150,16 +1150,7 @@ Section: Comparing strings
 #[lang = "str_eq"]
 #[inline]
 fn eq_slice(a: &str, b: &str) -> bool {
-    a.len() == b.len() && unsafe { cmp_slice(a, b, a.len()) == 0 }
-}
-
-/// Bytewise slice comparison.
-/// NOTE: This uses the system's memcmp, which is currently dramatically
-/// faster than comparing each byte in a loop.
-#[inline]
-unsafe fn cmp_slice(a: &str, b: &str, len: usize) -> i32 {
-    extern { fn memcmp(s1: *const i8, s2: *const i8, n: usize) -> i32; }
-    memcmp(a.as_ptr() as *const i8, b.as_ptr() as *const i8, len)
+    a.as_bytes() == b.as_bytes()
 }
 
 /*
@@ -1328,8 +1319,7 @@ Section: Trait implementations
 */
 
 mod traits {
-    use cmp::{self, Ordering, Ord, PartialEq, PartialOrd, Eq};
-    use cmp::Ordering::{Less, Greater};
+    use cmp::{Ord, Ordering, PartialEq, PartialOrd, Eq};
     use iter::Iterator;
     use option::Option;
     use option::Option::Some;
@@ -1340,16 +1330,7 @@ mod traits {
     impl Ord for str {
         #[inline]
         fn cmp(&self, other: &str) -> Ordering {
-            let cmp = unsafe {
-                super::cmp_slice(self, other, cmp::min(self.len(), other.len()))
-            };
-            if cmp == 0 {
-                self.len().cmp(&other.len())
-            } else if cmp < 0 {
-                Less
-            } else {
-                Greater
-            }
+            self.as_bytes().cmp(other.as_bytes())
         }
     }
 
diff --git a/src/libcore/sync/atomic.rs b/src/libcore/sync/atomic.rs
index d2e98a795d9..483c3822df6 100644
--- a/src/libcore/sync/atomic.rs
+++ b/src/libcore/sync/atomic.rs
@@ -327,7 +327,7 @@ impl AtomicBool {
     /// `compare_exchange` takes two `Ordering` arguments to describe the memory ordering of this
     /// operation. The first describes the required ordering if the operation succeeds while the
     /// second describes the required ordering when the operation fails. The failure ordering can't
-    /// be `Acquire` or `AcqRel` and must be equivalent or weaker than the success ordering.
+    /// be `Release` or `AcqRel` and must be equivalent or weaker than the success ordering.
     ///
     /// # Examples
     ///
@@ -376,7 +376,7 @@ impl AtomicBool {
     /// `compare_exchange_weak` takes two `Ordering` arguments to describe the memory
     /// ordering of this operation. The first describes the required ordering if the operation
     /// succeeds while the second describes the required ordering when the operation fails. The
-    /// failure ordering can't be `Acquire` or `AcqRel` and must be equivalent or weaker than the
+    /// failure ordering can't be `Release` or `AcqRel` and must be equivalent or weaker than the
     /// success ordering.
     ///
     /// # Examples
@@ -663,7 +663,7 @@ impl AtomicIsize {
     /// `compare_exchange` takes two `Ordering` arguments to describe the memory ordering of this
     /// operation. The first describes the required ordering if the operation succeeds while the
     /// second describes the required ordering when the operation fails. The failure ordering can't
-    /// be `Acquire` or `AcqRel` and must be equivalent or weaker than the success ordering.
+    /// be `Release` or `AcqRel` and must be equivalent or weaker than the success ordering.
     ///
     /// # Examples
     ///
@@ -705,7 +705,7 @@ impl AtomicIsize {
     /// `compare_exchange_weak` takes two `Ordering` arguments to describe the memory
     /// ordering of this operation. The first describes the required ordering if the operation
     /// succeeds while the second describes the required ordering when the operation fails. The
-    /// failure ordering can't be `Acquire` or `AcqRel` and must be equivalent or weaker than the
+    /// failure ordering can't be `Release` or `AcqRel` and must be equivalent or weaker than the
     /// success ordering.
     ///
     /// # Examples
@@ -939,7 +939,7 @@ impl AtomicUsize {
     /// `compare_exchange` takes two `Ordering` arguments to describe the memory ordering of this
     /// operation. The first describes the required ordering if the operation succeeds while the
     /// second describes the required ordering when the operation fails. The failure ordering can't
-    /// be `Acquire` or `AcqRel` and must be equivalent or weaker than the success ordering.
+    /// be `Release` or `AcqRel` and must be equivalent or weaker than the success ordering.
     ///
     /// # Examples
     ///
@@ -981,7 +981,7 @@ impl AtomicUsize {
     /// `compare_exchange_weak` takes two `Ordering` arguments to describe the memory
     /// ordering of this operation. The first describes the required ordering if the operation
     /// succeeds while the second describes the required ordering when the operation fails. The
-    /// failure ordering can't be `Acquire` or `AcqRel` and must be equivalent or weaker than the
+    /// failure ordering can't be `Release` or `AcqRel` and must be equivalent or weaker than the
     /// success ordering.
     ///
     /// # Examples
@@ -1223,7 +1223,7 @@ impl<T> AtomicPtr<T> {
     /// `compare_exchange` takes two `Ordering` arguments to describe the memory ordering of this
     /// operation. The first describes the required ordering if the operation succeeds while the
     /// second describes the required ordering when the operation fails. The failure ordering can't
-    /// be `Acquire` or `AcqRel` and must be equivalent or weaker than the success ordering.
+    /// be `Release` or `AcqRel` and must be equivalent or weaker than the success ordering.
     ///
     /// # Examples
     ///
@@ -1270,7 +1270,7 @@ impl<T> AtomicPtr<T> {
     /// `compare_exchange_weak` takes two `Ordering` arguments to describe the memory
     /// ordering of this operation. The first describes the required ordering if the operation
     /// succeeds while the second describes the required ordering when the operation fails. The
-    /// failure ordering can't be `Acquire` or `AcqRel` and must be equivalent or weaker than the
+    /// failure ordering can't be `Release` or `AcqRel` and must be equivalent or weaker than the
     /// success ordering.
     ///
     /// # Examples
@@ -1396,8 +1396,8 @@ unsafe fn atomic_compare_exchange<T>(dst: *mut T,
         (AcqRel, Relaxed)  => intrinsics::atomic_cxchg_acqrel_failrelaxed(dst, old, new),
         (SeqCst, Relaxed)  => intrinsics::atomic_cxchg_failrelaxed(dst, old, new),
         (SeqCst, Acquire)  => intrinsics::atomic_cxchg_failacq(dst, old, new),
-        (_, Release) => panic!("there is no such thing as an acquire/release failure ordering"),
-        (_, AcqRel) => panic!("there is no such thing as a release failure ordering"),
+        (_, AcqRel) => panic!("there is no such thing as an acquire/release failure ordering"),
+        (_, Release) => panic!("there is no such thing as a release failure ordering"),
         _ => panic!("a failure ordering can't be stronger than a success ordering"),
     };
     if ok {
@@ -1446,8 +1446,8 @@ unsafe fn atomic_compare_exchange_weak<T>(dst: *mut T,
         (AcqRel, Relaxed)  => intrinsics::atomic_cxchgweak_acqrel_failrelaxed(dst, old, new),
         (SeqCst, Relaxed)  => intrinsics::atomic_cxchgweak_failrelaxed(dst, old, new),
         (SeqCst, Acquire)  => intrinsics::atomic_cxchgweak_failacq(dst, old, new),
-        (_, Release) => panic!("there is no such thing as an acquire/release failure ordering"),
-        (_, AcqRel) => panic!("there is no such thing as a release failure ordering"),
+        (_, AcqRel) => panic!("there is no such thing as an acquire/release failure ordering"),
+        (_, Release) => panic!("there is no such thing as a release failure ordering"),
         _ => panic!("a failure ordering can't be stronger than a success ordering"),
     };
     if ok {
diff --git a/src/librustc/hir/intravisit.rs b/src/librustc/hir/intravisit.rs
index d34d66918ca..55fd58da866 100644
--- a/src/librustc/hir/intravisit.rs
+++ b/src/librustc/hir/intravisit.rs
@@ -37,10 +37,10 @@ use std::u32;
 #[derive(Copy, Clone, PartialEq, Eq)]
 pub enum FnKind<'a> {
     /// fn foo() or extern "Abi" fn foo()
-    ItemFn(Name, &'a Generics, Unsafety, Constness, Abi, Visibility, &'a [Attribute]),
+    ItemFn(Name, &'a Generics, Unsafety, Constness, Abi, &'a Visibility, &'a [Attribute]),
 
     /// fn foo(&self)
-    Method(Name, &'a MethodSig, Option<Visibility>, &'a [Attribute]),
+    Method(Name, &'a MethodSig, Option<&'a Visibility>, &'a [Attribute]),
 
     /// |x, y| {}
     Closure(&'a [Attribute]),
@@ -324,7 +324,7 @@ pub fn walk_item<'v, V: Visitor<'v>>(visitor: &mut V, item: &'v Item) {
                                             unsafety,
                                             constness,
                                             abi,
-                                            item.vis,
+                                            &item.vis,
                                             &item.attrs),
                              declaration,
                              body,
@@ -672,7 +672,7 @@ pub fn walk_impl_item<'v, V: Visitor<'v>>(visitor: &mut V, impl_item: &'v ImplIt
         ImplItemKind::Method(ref sig, ref body) => {
             visitor.visit_fn(FnKind::Method(impl_item.name,
                                             sig,
-                                            Some(impl_item.vis),
+                                            Some(&impl_item.vis),
                                             &impl_item.attrs),
                              &sig.decl,
                              body,
diff --git a/src/librustc/hir/map/blocks.rs b/src/librustc/hir/map/blocks.rs
index 7b1c692d54b..8c626226bd3 100644
--- a/src/librustc/hir/map/blocks.rs
+++ b/src/librustc/hir/map/blocks.rs
@@ -113,7 +113,7 @@ struct ItemFnParts<'a> {
     unsafety: ast::Unsafety,
     constness: ast::Constness,
     abi:      abi::Abi,
-    vis:      ast::Visibility,
+    vis:      &'a ast::Visibility,
     generics: &'a ast::Generics,
     body:     &'a Block,
     id:       NodeId,
@@ -208,7 +208,7 @@ impl<'a> FnLikeNode<'a> {
         M: FnOnce(NodeId,
                   Name,
                   &'a ast::MethodSig,
-                  Option<ast::Visibility>,
+                  Option<&'a ast::Visibility>,
                   &'a ast::Block,
                   Span,
                   &'a [Attribute])
@@ -226,7 +226,7 @@ impl<'a> FnLikeNode<'a> {
                         body: &block,
                         generics: generics,
                         abi: abi,
-                        vis: i.vis,
+                        vis: &i.vis,
                         constness: constness,
                         span: i.span,
                         attrs: &i.attrs,
@@ -242,7 +242,7 @@ impl<'a> FnLikeNode<'a> {
             map::NodeImplItem(ii) => {
                 match ii.node {
                     ast::ImplItemKind::Method(ref sig, ref body) => {
-                        method(ii.id, ii.name, sig, Some(ii.vis), body, ii.span, &ii.attrs)
+                        method(ii.id, ii.name, sig, Some(&ii.vis), body, ii.span, &ii.attrs)
                     }
                     _ => {
                         bug!("impl method FnLikeNode that is not fn-like")
diff --git a/src/librustc/hir/map/mod.rs b/src/librustc/hir/map/mod.rs
index e1b7afda58b..fc1c4aeb226 100644
--- a/src/librustc/hir/map/mod.rs
+++ b/src/librustc/hir/map/mod.rs
@@ -430,7 +430,7 @@ impl<'ast> Map<'ast> {
 
     /// Returns the NodeId of `id`'s nearest module parent, or `id` itself if no
     /// module parent is in this map.
-    fn get_module_parent(&self, id: NodeId) -> NodeId {
+    pub fn get_module_parent(&self, id: NodeId) -> NodeId {
         match self.walk_parent_nodes(id, |node| match *node {
             NodeItem(&Item { node: Item_::ItemMod(_), .. }) => true,
             _ => false,
@@ -440,18 +440,6 @@ impl<'ast> Map<'ast> {
         }
     }
 
-    pub fn private_item_is_visible_from(&self, item: NodeId, block: NodeId) -> bool {
-        // A private item is visible from everything in its nearest module parent.
-        let visibility = self.get_module_parent(item);
-        let mut block_ancestor = self.get_module_parent(block);
-        loop {
-            if block_ancestor == visibility { return true }
-            let block_ancestor_parent = self.get_module_parent(block_ancestor);
-            if block_ancestor_parent == block_ancestor { return false }
-            block_ancestor = block_ancestor_parent;
-        }
-    }
-
     /// Returns the nearest enclosing scope. A scope is an item or block.
     /// FIXME it is not clear to me that all items qualify as scopes - statics
     /// and associated types probably shouldn't, for example. Behaviour in this
diff --git a/src/librustc/hir/mod.rs b/src/librustc/hir/mod.rs
index edb9b783527..8e748875b93 100644
--- a/src/librustc/hir/mod.rs
+++ b/src/librustc/hir/mod.rs
@@ -1431,21 +1431,12 @@ pub struct PolyTraitRef {
     pub span: Span,
 }
 
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 pub enum Visibility {
     Public,
     Inherited,
 }
 
-impl Visibility {
-    pub fn inherit_from(&self, parent_visibility: Visibility) -> Visibility {
-        match self {
-            &Inherited => parent_visibility,
-            &Public => *self,
-        }
-    }
-}
-
 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 pub struct StructField {
     pub span: Span,
diff --git a/src/librustc/hir/print.rs b/src/librustc/hir/print.rs
index cd2dfd44639..7affb129313 100644
--- a/src/librustc/hir/print.rs
+++ b/src/librustc/hir/print.rs
@@ -294,7 +294,7 @@ pub fn fun_to_string(decl: &hir::FnDecl,
                    Some(name),
                    generics,
                    opt_explicit_self,
-                   hir::Inherited)?;
+                   &hir::Inherited)?;
         s.end()?; // Close the head box
         s.end() // Close the outer box
     })
@@ -322,8 +322,8 @@ pub fn arg_to_string(arg: &hir::Arg) -> String {
     to_string(|s| s.print_arg(arg, false))
 }
 
-pub fn visibility_qualified(vis: hir::Visibility, s: &str) -> String {
-    match vis {
+pub fn visibility_qualified(vis: &hir::Visibility, s: &str) -> String {
+    match *vis {
         hir::Public => format!("pub {}", s),
         hir::Inherited => s.to_string(),
     }
@@ -573,13 +573,13 @@ impl<'a> State<'a> {
                               Some(item.name),
                               generics,
                               None,
-                              item.vis)?;
+                              &item.vis)?;
                 self.end()?; // end head-ibox
                 word(&mut self.s, ";")?;
                 self.end() // end the outer fn box
             }
             hir::ForeignItemStatic(ref t, m) => {
-                self.head(&visibility_qualified(item.vis, "static"))?;
+                self.head(&visibility_qualified(&item.vis, "static"))?;
                 if m {
                     self.word_space("mut")?;
                 }
@@ -597,7 +597,7 @@ impl<'a> State<'a> {
                               name: ast::Name,
                               ty: &hir::Ty,
                               default: Option<&hir::Expr>,
-                              vis: hir::Visibility)
+                              vis: &hir::Visibility)
                               -> io::Result<()> {
         word(&mut self.s, &visibility_qualified(vis, ""))?;
         self.word_space("const")?;
@@ -648,7 +648,7 @@ impl<'a> State<'a> {
         self.ann.pre(self, NodeItem(item))?;
         match item.node {
             hir::ItemExternCrate(ref optional_path) => {
-                self.head(&visibility_qualified(item.vis, "extern crate"))?;
+                self.head(&visibility_qualified(&item.vis, "extern crate"))?;
                 if let Some(p) = *optional_path {
                     let val = p.as_str();
                     if val.contains("-") {
@@ -666,14 +666,14 @@ impl<'a> State<'a> {
                 self.end()?; // end outer head-block
             }
             hir::ItemUse(ref vp) => {
-                self.head(&visibility_qualified(item.vis, "use"))?;
+                self.head(&visibility_qualified(&item.vis, "use"))?;
                 self.print_view_path(&vp)?;
                 word(&mut self.s, ";")?;
                 self.end()?; // end inner head-block
                 self.end()?; // end outer head-block
             }
             hir::ItemStatic(ref ty, m, ref expr) => {
-                self.head(&visibility_qualified(item.vis, "static"))?;
+                self.head(&visibility_qualified(&item.vis, "static"))?;
                 if m == hir::MutMutable {
                     self.word_space("mut")?;
                 }
@@ -689,7 +689,7 @@ impl<'a> State<'a> {
                 self.end()?; // end the outer cbox
             }
             hir::ItemConst(ref ty, ref expr) => {
-                self.head(&visibility_qualified(item.vis, "const"))?;
+                self.head(&visibility_qualified(&item.vis, "const"))?;
                 self.print_name(item.name)?;
                 self.word_space(":")?;
                 self.print_type(&ty)?;
@@ -710,12 +710,12 @@ impl<'a> State<'a> {
                               Some(item.name),
                               typarams,
                               None,
-                              item.vis)?;
+                              &item.vis)?;
                 word(&mut self.s, " ")?;
                 self.print_block_with_attrs(&body, &item.attrs)?;
             }
             hir::ItemMod(ref _mod) => {
-                self.head(&visibility_qualified(item.vis, "mod"))?;
+                self.head(&visibility_qualified(&item.vis, "mod"))?;
                 self.print_name(item.name)?;
                 self.nbsp()?;
                 self.bopen()?;
@@ -732,7 +732,7 @@ impl<'a> State<'a> {
             hir::ItemTy(ref ty, ref params) => {
                 self.ibox(indent_unit)?;
                 self.ibox(0)?;
-                self.word_nbsp(&visibility_qualified(item.vis, "type"))?;
+                self.word_nbsp(&visibility_qualified(&item.vis, "type"))?;
                 self.print_name(item.name)?;
                 self.print_generics(params)?;
                 self.end()?; // end the inner ibox
@@ -745,16 +745,16 @@ impl<'a> State<'a> {
                 self.end()?; // end the outer ibox
             }
             hir::ItemEnum(ref enum_definition, ref params) => {
-                self.print_enum_def(enum_definition, params, item.name, item.span, item.vis)?;
+                self.print_enum_def(enum_definition, params, item.name, item.span, &item.vis)?;
             }
             hir::ItemStruct(ref struct_def, ref generics) => {
-                self.head(&visibility_qualified(item.vis, "struct"))?;
+                self.head(&visibility_qualified(&item.vis, "struct"))?;
                 self.print_struct(struct_def, generics, item.name, item.span, true)?;
             }
 
             hir::ItemDefaultImpl(unsafety, ref trait_ref) => {
                 self.head("")?;
-                self.print_visibility(item.vis)?;
+                self.print_visibility(&item.vis)?;
                 self.print_unsafety(unsafety)?;
                 self.word_nbsp("impl")?;
                 self.print_trait_ref(trait_ref)?;
@@ -771,7 +771,7 @@ impl<'a> State<'a> {
                           ref ty,
                           ref impl_items) => {
                 self.head("")?;
-                self.print_visibility(item.vis)?;
+                self.print_visibility(&item.vis)?;
                 self.print_unsafety(unsafety)?;
                 self.word_nbsp("impl")?;
 
@@ -809,7 +809,7 @@ impl<'a> State<'a> {
             }
             hir::ItemTrait(unsafety, ref generics, ref bounds, ref trait_items) => {
                 self.head("")?;
-                self.print_visibility(item.vis)?;
+                self.print_visibility(&item.vis)?;
                 self.print_unsafety(unsafety)?;
                 self.word_nbsp("trait")?;
                 self.print_name(item.name)?;
@@ -867,7 +867,7 @@ impl<'a> State<'a> {
                           generics: &hir::Generics,
                           name: ast::Name,
                           span: codemap::Span,
-                          visibility: hir::Visibility)
+                          visibility: &hir::Visibility)
                           -> io::Result<()> {
         self.head(&visibility_qualified(visibility, "enum"))?;
         self.print_name(name)?;
@@ -895,8 +895,8 @@ impl<'a> State<'a> {
         self.bclose(span)
     }
 
-    pub fn print_visibility(&mut self, vis: hir::Visibility) -> io::Result<()> {
-        match vis {
+    pub fn print_visibility(&mut self, vis: &hir::Visibility) -> io::Result<()> {
+        match *vis {
             hir::Public => self.word_nbsp("pub"),
             hir::Inherited => Ok(()),
         }
@@ -915,7 +915,7 @@ impl<'a> State<'a> {
             if struct_def.is_tuple() {
                 self.popen()?;
                 self.commasep(Inconsistent, struct_def.fields(), |s, field| {
-                    s.print_visibility(field.vis)?;
+                    s.print_visibility(&field.vis)?;
                     s.maybe_print_comment(field.span.lo)?;
                     s.print_type(&field.ty)
                 })?;
@@ -937,7 +937,7 @@ impl<'a> State<'a> {
                 self.hardbreak_if_not_bol()?;
                 self.maybe_print_comment(field.span.lo)?;
                 self.print_outer_attributes(&field.attrs)?;
-                self.print_visibility(field.vis)?;
+                self.print_visibility(&field.vis)?;
                 self.print_name(field.name)?;
                 self.word_nbsp(":")?;
                 self.print_type(&field.ty)?;
@@ -964,7 +964,7 @@ impl<'a> State<'a> {
     pub fn print_method_sig(&mut self,
                             name: ast::Name,
                             m: &hir::MethodSig,
-                            vis: hir::Visibility)
+                            vis: &hir::Visibility)
                             -> io::Result<()> {
         self.print_fn(&m.decl,
                       m.unsafety,
@@ -986,13 +986,13 @@ impl<'a> State<'a> {
                 self.print_associated_const(ti.name,
                                             &ty,
                                             default.as_ref().map(|expr| &**expr),
-                                            hir::Inherited)?;
+                                            &hir::Inherited)?;
             }
             hir::MethodTraitItem(ref sig, ref body) => {
                 if body.is_some() {
                     self.head("")?;
                 }
-                self.print_method_sig(ti.name, sig, hir::Inherited)?;
+                self.print_method_sig(ti.name, sig, &hir::Inherited)?;
                 if let Some(ref body) = *body {
                     self.nbsp()?;
                     self.print_block_with_attrs(body, &ti.attrs)?;
@@ -1021,11 +1021,11 @@ impl<'a> State<'a> {
 
         match ii.node {
             hir::ImplItemKind::Const(ref ty, ref expr) => {
-                self.print_associated_const(ii.name, &ty, Some(&expr), ii.vis)?;
+                self.print_associated_const(ii.name, &ty, Some(&expr), &ii.vis)?;
             }
             hir::ImplItemKind::Method(ref sig, ref body) => {
                 self.head("")?;
-                self.print_method_sig(ii.name, sig, ii.vis)?;
+                self.print_method_sig(ii.name, sig, &ii.vis)?;
                 self.nbsp()?;
                 self.print_block_with_attrs(body, &ii.attrs)?;
             }
@@ -1910,7 +1910,7 @@ impl<'a> State<'a> {
                     name: Option<ast::Name>,
                     generics: &hir::Generics,
                     opt_explicit_self: Option<&hir::ExplicitSelf_>,
-                    vis: hir::Visibility)
+                    vis: &hir::Visibility)
                     -> io::Result<()> {
         self.print_fn_header_info(unsafety, constness, abi, vis)?;
 
@@ -2267,7 +2267,7 @@ impl<'a> State<'a> {
                       name,
                       &generics,
                       opt_explicit_self,
-                      hir::Inherited)?;
+                      &hir::Inherited)?;
         self.end()
     }
 
@@ -2347,7 +2347,7 @@ impl<'a> State<'a> {
                                 unsafety: hir::Unsafety,
                                 constness: hir::Constness,
                                 abi: Abi,
-                                vis: hir::Visibility)
+                                vis: &hir::Visibility)
                                 -> io::Result<()> {
         word(&mut self.s, &visibility_qualified(vis, ""))?;
         self.print_unsafety(unsafety)?;
diff --git a/src/librustc/middle/cstore.rs b/src/librustc/middle/cstore.rs
index 1f6328187a5..d3db0804c24 100644
--- a/src/librustc/middle/cstore.rs
+++ b/src/librustc/middle/cstore.rs
@@ -116,7 +116,7 @@ pub const LOCAL_CRATE: ast::CrateNum = 0;
 pub struct ChildItem {
     pub def: DefLike,
     pub name: ast::Name,
-    pub vis: hir::Visibility
+    pub vis: ty::Visibility,
 }
 
 pub enum FoundAst<'ast> {
@@ -157,7 +157,7 @@ pub trait CrateStore<'tcx> : Any {
     // item info
     fn stability(&self, def: DefId) -> Option<attr::Stability>;
     fn deprecation(&self, def: DefId) -> Option<attr::Deprecation>;
-    fn visibility(&self, def: DefId) -> hir::Visibility;
+    fn visibility(&self, def: DefId) -> ty::Visibility;
     fn closure_kind(&self, tcx: &TyCtxt<'tcx>, def_id: DefId)
                     -> ty::ClosureKind;
     fn closure_ty(&self, tcx: &TyCtxt<'tcx>, def_id: DefId)
@@ -334,7 +334,7 @@ impl<'tcx> CrateStore<'tcx> for DummyCrateStore {
     // item info
     fn stability(&self, def: DefId) -> Option<attr::Stability> { bug!("stability") }
     fn deprecation(&self, def: DefId) -> Option<attr::Deprecation> { bug!("deprecation") }
-    fn visibility(&self, def: DefId) -> hir::Visibility { bug!("visibility") }
+    fn visibility(&self, def: DefId) -> ty::Visibility { bug!("visibility") }
     fn closure_kind(&self, tcx: &TyCtxt<'tcx>, def_id: DefId)
                     -> ty::ClosureKind  { bug!("closure_kind") }
     fn closure_ty(&self, tcx: &TyCtxt<'tcx>, def_id: DefId)
diff --git a/src/librustc/traits/specialize/specialization_graph.rs b/src/librustc/traits/specialize/specialization_graph.rs
index 51b0b6b8b38..3c65e368db5 100644
--- a/src/librustc/traits/specialize/specialization_graph.rs
+++ b/src/librustc/traits/specialize/specialization_graph.rs
@@ -18,8 +18,9 @@ use hir::def_id::DefId;
 use infer;
 use traits::{self, ProjectionMode};
 use ty::{self, TyCtxt, ImplOrTraitItem, TraitDef, TypeFoldable};
+use ty::fast_reject::{self, SimplifiedType};
 use syntax::ast::Name;
-use util::nodemap::DefIdMap;
+use util::nodemap::{DefIdMap, FnvHashMap};
 
 /// A per-trait graph of impls in specialization order. At the moment, this
 /// graph forms a tree rooted with the trait itself, with all other nodes
@@ -42,7 +43,124 @@ pub struct Graph {
     parent: DefIdMap<DefId>,
 
     // the "root" impls are found by looking up the trait's def_id.
-    children: DefIdMap<Vec<DefId>>,
+    children: DefIdMap<Children>,
+}
+
+/// Children of a given impl, grouped into blanket/non-blanket varieties as is
+/// done in `TraitDef`.
+struct Children {
+    // Impls of a trait (or specializations of a given impl). To allow for
+    // quicker lookup, the impls are indexed by a simplified version of their
+    // `Self` type: impls with a simplifiable `Self` are stored in
+    // `nonblanket_impls` keyed by it, while all other impls are stored in
+    // `blanket_impls`.
+    //
+    // A similar division is used within `TraitDef`, but the lists there collect
+    // together *all* the impls for a trait, and are populated prior to building
+    // the specialization graph.
+
+    /// Impls of the trait.
+    nonblanket_impls: FnvHashMap<fast_reject::SimplifiedType, Vec<DefId>>,
+
+    /// Blanket impls associated with the trait.
+    blanket_impls: Vec<DefId>,
+}
+
+/// The result of attempting to insert an impl into a group of children.
+enum InsertResult<'a, 'tcx: 'a> {
+    /// The impl was inserted as a new child in this group of children.
+    BecameNewSibling,
+
+    /// The impl replaced an existing impl that specializes it.
+    Replaced(DefId),
+
+    /// The impl is a specialization of an existing child.
+    ShouldRecurseOn(DefId),
+
+    /// The impl has an unresolvable overlap with an existing child (neither
+    /// specializes the other).
+    Overlapped(Overlap<'a, 'tcx>),
+}
+
+impl Children {
+    fn new() -> Children {
+        Children {
+            nonblanket_impls: FnvHashMap(),
+            blanket_impls: vec![],
+        }
+    }
+
+    /// Insert an impl into this set of children without comparing to any existing impls
+    fn insert_blindly(&mut self, tcx: &TyCtxt, impl_def_id: DefId) {
+        let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
+        if let Some(sty) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false) {
+            self.nonblanket_impls.entry(sty).or_insert(vec![]).push(impl_def_id)
+        } else {
+            self.blanket_impls.push(impl_def_id)
+        }
+    }
+
+    /// Attempt to insert an impl into this set of children, while comparing for
+    /// specialiation relationships.
+    fn insert<'a, 'tcx>(&mut self,
+                        tcx: &'a TyCtxt<'tcx>,
+                        impl_def_id: DefId,
+                        simplified_self: Option<SimplifiedType>)
+                        -> InsertResult<'a, 'tcx>
+    {
+        for slot in match simplified_self {
+            Some(sty) => self.filtered_mut(sty),
+            None => self.iter_mut(),
+        } {
+            let possible_sibling = *slot;
+
+            let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, ProjectionMode::Topmost);
+            let overlap = traits::overlapping_impls(&infcx, possible_sibling, impl_def_id);
+
+            if let Some(impl_header) = overlap {
+                let le = specializes(tcx, impl_def_id, possible_sibling);
+                let ge = specializes(tcx, possible_sibling, impl_def_id);
+
+                if le && !ge {
+                    debug!("descending as child of TraitRef {:?}",
+                           tcx.impl_trait_ref(possible_sibling).unwrap());
+
+                    // the impl specializes possible_sibling
+                    return InsertResult::ShouldRecurseOn(possible_sibling);
+                } else if ge && !le {
+                    debug!("placing as parent of TraitRef {:?}",
+                           tcx.impl_trait_ref(possible_sibling).unwrap());
+
+                    // possible_sibling specializes the impl
+                    *slot = impl_def_id;
+                    return InsertResult::Replaced(possible_sibling);
+                } else {
+                    // overlap, but no specialization; error out
+                    return InsertResult::Overlapped(Overlap {
+                        with_impl: possible_sibling,
+                        on_trait_ref: impl_header.trait_ref.unwrap(),
+                        in_context: infcx,
+                    });
+                }
+            }
+        }
+
+        // no overlap with any potential siblings, so add as a new sibling
+        debug!("placing as new sibling");
+        self.insert_blindly(tcx, impl_def_id);
+        InsertResult::BecameNewSibling
+    }
+
+    fn iter_mut<'a>(&'a mut self) -> Box<Iterator<Item = &'a mut DefId> + 'a> {
+        let nonblanket = self.nonblanket_impls.iter_mut().flat_map(|(_, v)| v.iter_mut());
+        Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
+    }
+
+    fn filtered_mut<'a>(&'a mut self, sty: SimplifiedType)
+                        -> Box<Iterator<Item = &'a mut DefId> + 'a> {
+        let nonblanket = self.nonblanket_impls.entry(sty).or_insert(vec![]).iter_mut();
+        Box::new(self.blanket_impls.iter_mut().chain(nonblanket))
+    }
 }
 
 impl Graph {
@@ -78,78 +196,53 @@ impl Graph {
                    trait_ref, impl_def_id, trait_def_id);
 
             self.parent.insert(impl_def_id, trait_def_id);
-            self.children.entry(trait_def_id).or_insert(vec![]).push(impl_def_id);
+            self.children.entry(trait_def_id).or_insert(Children::new())
+                .insert_blindly(tcx, impl_def_id);
             return Ok(());
         }
 
         let mut parent = trait_def_id;
+        let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false);
 
-        // Ugly hack around borrowck limitations. Assigned only in the case
-        // where we bump downward an existing node in the graph.
-        let child_to_insert;
-
-        'descend: loop {
-            let mut possible_siblings = self.children.entry(parent).or_insert(vec![]);
-
-            for slot in possible_siblings.iter_mut() {
-                let possible_sibling = *slot;
-
-                let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, ProjectionMode::Topmost);
-                let overlap = traits::overlapping_impls(&infcx, possible_sibling, impl_def_id);
-
-                if let Some(impl_header) = overlap {
-                    let le = specializes(tcx, impl_def_id, possible_sibling);
-                    let ge = specializes(tcx, possible_sibling, impl_def_id);
-
-                    if le && !ge {
-                        debug!("descending as child of TraitRef {:?}",
-                               tcx.impl_trait_ref(possible_sibling).unwrap());
-
-                        // the impl specializes possible_sibling
-                        parent = possible_sibling;
-                        continue 'descend;
-                    } else if ge && !le {
-                        debug!("placing as parent of TraitRef {:?}",
-                               tcx.impl_trait_ref(possible_sibling).unwrap());
-
-                        // possible_sibling specializes the impl
-                        *slot = impl_def_id;
-                        self.parent.insert(impl_def_id, parent);
-                        self.parent.insert(possible_sibling, impl_def_id);
-                        // we have to defer the insertion, because we can't
-                        // relinquish the borrow of `self.children`
-                        child_to_insert = possible_sibling;
-                        break 'descend;
-                    } else {
-                        // overlap, but no specialization; error out
-                        return Err(Overlap {
-                            with_impl: possible_sibling,
-                            on_trait_ref: impl_header.trait_ref.unwrap(),
-                            in_context: infcx,
-                        });
-                    }
+        // Descend the specialization tree, where `parent` is the current parent node
+        loop {
+            use self::InsertResult::*;
+
+            let insert_result = self.children.entry(parent).or_insert(Children::new())
+                .insert(tcx, impl_def_id, simplified);
+
+            match insert_result {
+                BecameNewSibling => {
+                    break;
+                }
+                Replaced(new_child) => {
+                    self.parent.insert(new_child, impl_def_id);
+                    let mut new_children = Children::new();
+                    new_children.insert_blindly(tcx, new_child);
+                    self.children.insert(impl_def_id, new_children);
+                    break;
+                }
+                ShouldRecurseOn(new_parent) => {
+                    parent = new_parent;
+                }
+                Overlapped(error) => {
+                    return Err(error);
                 }
             }
-
-            // no overlap with any potential siblings, so add as a new sibling
-            debug!("placing as new sibling");
-            self.parent.insert(impl_def_id, parent);
-            possible_siblings.push(impl_def_id);
-            return Ok(());
         }
 
-        self.children.insert(impl_def_id, vec![child_to_insert]);
+        self.parent.insert(impl_def_id, parent);
         Ok(())
     }
 
     /// Insert cached metadata mapping from a child impl back to its parent.
-    pub fn record_impl_from_cstore(&mut self, parent: DefId, child: DefId) {
+    pub fn record_impl_from_cstore(&mut self, tcx: &TyCtxt, parent: DefId, child: DefId) {
         if self.parent.insert(child, parent).is_some() {
             bug!("When recording an impl from the crate store, information about its parent \
                   was already present.");
         }
 
-        self.children.entry(parent).or_insert(vec![]).push(child);
+        self.children.entry(parent).or_insert(Children::new()).insert_blindly(tcx, child);
     }
 
     /// The parent of a given impl, which is the def id of the trait when the
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 444fea0918f..47e8f91b48c 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -232,7 +232,7 @@ impl<'tcx> ImplOrTraitItem<'tcx> {
         }
     }
 
-    pub fn vis(&self) -> hir::Visibility {
+    pub fn vis(&self) -> Visibility {
         match *self {
             ConstTraitItem(ref associated_const) => associated_const.vis,
             MethodTraitItem(ref method) => method.vis,
@@ -273,6 +273,56 @@ impl ImplOrTraitItemId {
     }
 }
 
+#[derive(Clone, Debug, PartialEq, Eq, Copy)]
+pub enum Visibility {
+    /// Visible everywhere (including in other crates).
+    Public,
+    /// Visible only in the given crate-local module.
+    Restricted(NodeId),
+    /// Not visible anywhere in the local crate. This is the visibility of private external items.
+    PrivateExternal,
+}
+
+impl Visibility {
+    pub fn from_hir(visibility: &hir::Visibility, id: NodeId, tcx: &TyCtxt) -> Self {
+        match *visibility {
+            hir::Public => Visibility::Public,
+            hir::Inherited => Visibility::Restricted(tcx.map.get_module_parent(id)),
+        }
+    }
+
+    /// Returns true if an item with this visibility is accessible from the given block.
+    pub fn is_accessible_from(self, block: NodeId, map: &ast_map::Map) -> bool {
+        let restriction = match self {
+            // Public items are visible everywhere.
+            Visibility::Public => return true,
+            // Private items from other crates are visible nowhere.
+            Visibility::PrivateExternal => return false,
+            // Restricted items are visible in an arbitrary local module.
+            Visibility::Restricted(module) => module,
+        };
+
+        let mut block_ancestor = block;
+        loop {
+            if block_ancestor == restriction { return true }
+            let block_ancestor_parent = map.get_module_parent(block_ancestor);
+            if block_ancestor_parent == block_ancestor { return false }
+            block_ancestor = block_ancestor_parent;
+        }
+    }
+
+    /// Returns true if this visibility is at least as accessible as the given visibility
+    pub fn is_at_least(self, vis: Visibility, map: &ast_map::Map) -> bool {
+        let vis_restriction = match vis {
+            Visibility::Public => return self == Visibility::Public,
+            Visibility::PrivateExternal => return true,
+            Visibility::Restricted(module) => module,
+        };
+
+        self.is_accessible_from(vis_restriction, map)
+    }
+}
+
 #[derive(Clone, Debug)]
 pub struct Method<'tcx> {
     pub name: Name,
@@ -280,7 +330,7 @@ pub struct Method<'tcx> {
     pub predicates: GenericPredicates<'tcx>,
     pub fty: BareFnTy<'tcx>,
     pub explicit_self: ExplicitSelfCategory,
-    pub vis: hir::Visibility,
+    pub vis: Visibility,
     pub defaultness: hir::Defaultness,
     pub def_id: DefId,
     pub container: ImplOrTraitItemContainer,
@@ -292,7 +342,7 @@ impl<'tcx> Method<'tcx> {
                predicates: GenericPredicates<'tcx>,
                fty: BareFnTy<'tcx>,
                explicit_self: ExplicitSelfCategory,
-               vis: hir::Visibility,
+               vis: Visibility,
                defaultness: hir::Defaultness,
                def_id: DefId,
                container: ImplOrTraitItemContainer)
@@ -336,7 +386,7 @@ impl<'tcx> Hash for Method<'tcx> {
 pub struct AssociatedConst<'tcx> {
     pub name: Name,
     pub ty: Ty<'tcx>,
-    pub vis: hir::Visibility,
+    pub vis: Visibility,
     pub defaultness: hir::Defaultness,
     pub def_id: DefId,
     pub container: ImplOrTraitItemContainer,
@@ -347,7 +397,7 @@ pub struct AssociatedConst<'tcx> {
 pub struct AssociatedType<'tcx> {
     pub name: Name,
     pub ty: Option<Ty<'tcx>>,
-    pub vis: hir::Visibility,
+    pub vis: Visibility,
     pub defaultness: hir::Defaultness,
     pub def_id: DefId,
     pub container: ImplOrTraitItemContainer,
@@ -1419,7 +1469,7 @@ pub struct FieldDefData<'tcx, 'container: 'tcx> {
     /// are not real items, and don't have entries in tcache etc.
     pub did: DefId,
     pub name: Name,
-    pub vis: hir::Visibility,
+    pub vis: Visibility,
     /// TyIVar is used here to allow for variance (see the doc at
     /// AdtDefData).
     ///
@@ -1704,7 +1754,7 @@ impl<'tcx, 'container> VariantDefData<'tcx, 'container> {
 impl<'tcx, 'container> FieldDefData<'tcx, 'container> {
     pub fn new(did: DefId,
                name: Name,
-               vis: hir::Visibility) -> Self {
+               vis: Visibility) -> Self {
         FieldDefData {
             did: did,
             name: name,
diff --git a/src/librustc/ty/trait_def.rs b/src/librustc/ty/trait_def.rs
index 94f4e31efc6..39a3837ae7f 100644
--- a/src/librustc/ty/trait_def.rs
+++ b/src/librustc/ty/trait_def.rs
@@ -15,7 +15,7 @@ use ty;
 use ty::fast_reject;
 use ty::{Ty, TyCtxt, TraitRef};
 use std::borrow::{Borrow};
-use std::cell::{Cell, Ref, RefCell};
+use std::cell::{Cell, RefCell};
 use syntax::ast::Name;
 use hir;
 use util::nodemap::FnvHashMap;
@@ -43,10 +43,17 @@ pub struct TraitDef<'tcx> {
     /// for resolving `X::Foo` type markers.
     pub associated_type_names: Vec<Name>,
 
-    // Impls of this trait. To allow for quicker lookup, the impls are indexed
-    // by a simplified version of their Self type: impls with a simplifiable
-    // Self are stored in nonblanket_impls keyed by it, while all other impls
-    // are stored in blanket_impls.
+    // Impls of a trait. To allow for quicker lookup, the impls are indexed by a
+    // simplified version of their `Self` type: impls with a simplifiable `Self`
+    // are stored in `nonblanket_impls` keyed by it, while all other impls are
+    // stored in `blanket_impls`.
+    //
+    // A similar division is used within `specialization_graph`, but the ones
+    // here are (1) stored as a flat list for the trait and (2) populated prior
+    // to -- and used while -- determining specialization order.
+    //
+    // FIXME: solve the reentrancy issues and remove these lists in favor of the
+    // ones in `specialization_graph`.
     //
     // These lists are tracked by `DepNode::TraitImpls`; we don't use
     // a DepTrackingMap but instead have the `TraitDef` insert the
@@ -184,7 +191,7 @@ impl<'tcx> TraitDef<'tcx> {
             // if the impl is non-local, it's placed directly into the
             // specialization graph using parent information drawn from metadata.
             self.specialization_graph.borrow_mut()
-                .record_impl_from_cstore(parent_impl, impl_def_id)
+                .record_impl_from_cstore(tcx, parent_impl, impl_def_id)
         }
     }
 
@@ -261,14 +268,6 @@ impl<'tcx> TraitDef<'tcx> {
             }
         }
     }
-
-    pub fn borrow_impl_lists<'s>(&'s self, tcx: &TyCtxt<'tcx>)
-                                 -> (Ref<'s, Vec<DefId>>,
-                                     Ref<'s, FnvHashMap<fast_reject::SimplifiedType, Vec<DefId>>>) {
-        self.read_trait_impls(tcx);
-        (self.blanket_impls.borrow(), self.nonblanket_impls.borrow())
-    }
-
 }
 
 bitflags! {
diff --git a/src/librustc_metadata/csearch.rs b/src/librustc_metadata/csearch.rs
index 0b90ad5b4e2..8e7be0e3a0f 100644
--- a/src/librustc_metadata/csearch.rs
+++ b/src/librustc_metadata/csearch.rs
@@ -48,7 +48,7 @@ impl<'tcx> CrateStore<'tcx> for cstore::CStore {
         decoder::get_deprecation(&cdata, def.index)
     }
 
-    fn visibility(&self, def: DefId) -> hir::Visibility {
+    fn visibility(&self, def: DefId) -> ty::Visibility {
         let cdata = self.get_crate_data(def.krate);
         decoder::get_visibility(&cdata, def.index)
     }
@@ -536,7 +536,6 @@ impl<'tcx> CrateStore<'tcx> for cstore::CStore {
         let mut visible_parent_map = self.visible_parent_map.borrow_mut();
         if !visible_parent_map.is_empty() { return visible_parent_map; }
 
-        use rustc::hir;
         use rustc::middle::cstore::{CrateStore, ChildItem};
         use std::collections::vec_deque::VecDeque;
         use std::collections::hash_map::Entry;
@@ -552,7 +551,7 @@ impl<'tcx> CrateStore<'tcx> for cstore::CStore {
             let mut bfs_queue = &mut VecDeque::new();
             let mut add_child = |bfs_queue: &mut VecDeque<_>, child: ChildItem, parent: DefId| {
                 let child = match child.def {
-                    DefLike::DlDef(def) if child.vis == hir::Public => def.def_id(),
+                    DefLike::DlDef(def) if child.vis == ty::Visibility::Public => def.def_id(),
                     _ => return,
                 };
 
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index 6b53edbbff1..a0881f1153e 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -140,13 +140,13 @@ fn item_family(item: rbml::Doc) -> Family {
     }
 }
 
-fn item_visibility(item: rbml::Doc) -> hir::Visibility {
+fn item_visibility(item: rbml::Doc) -> ty::Visibility {
     match reader::maybe_get_doc(item, tag_items_data_item_visibility) {
-        None => hir::Public,
+        None => ty::Visibility::Public,
         Some(visibility_doc) => {
             match reader::doc_as_u8(visibility_doc) as char {
-                'y' => hir::Public,
-                'i' => hir::Inherited,
+                'y' => ty::Visibility::Public,
+                'i' => ty::Visibility::PrivateExternal,
                 _ => bug!("unknown visibility character")
             }
         }
@@ -541,7 +541,7 @@ pub fn get_deprecation(cdata: Cmd, id: DefIndex) -> Option<attr::Deprecation> {
     })
 }
 
-pub fn get_visibility(cdata: Cmd, id: DefIndex) -> hir::Visibility {
+pub fn get_visibility(cdata: Cmd, id: DefIndex) -> ty::Visibility {
     item_visibility(cdata.lookup_item(id))
 }
 
@@ -639,7 +639,7 @@ fn each_child_of_item_or_crate<F, G>(intr: Rc<IdentInterner>,
                                      item_doc: rbml::Doc,
                                      mut get_crate_data: G,
                                      mut callback: F) where
-    F: FnMut(DefLike, ast::Name, hir::Visibility),
+    F: FnMut(DefLike, ast::Name, ty::Visibility),
     G: FnMut(ast::CrateNum) -> Rc<crate_metadata>,
 {
     // Iterate over all children.
@@ -723,7 +723,7 @@ fn each_child_of_item_or_crate<F, G>(intr: Rc<IdentInterner>,
             let def_like = item_to_def_like(crate_data, child_item_doc, child_def_id);
             // These items have a public visibility because they're part of
             // a public re-export.
-            callback(def_like, token::intern(name), hir::Public);
+            callback(def_like, token::intern(name), ty::Visibility::Public);
         }
     }
 }
@@ -734,7 +734,7 @@ pub fn each_child_of_item<F, G>(intr: Rc<IdentInterner>,
                                id: DefIndex,
                                get_crate_data: G,
                                callback: F) where
-    F: FnMut(DefLike, ast::Name, hir::Visibility),
+    F: FnMut(DefLike, ast::Name, ty::Visibility),
     G: FnMut(ast::CrateNum) -> Rc<crate_metadata>,
 {
     // Find the item.
@@ -755,7 +755,7 @@ pub fn each_top_level_item_of_crate<F, G>(intr: Rc<IdentInterner>,
                                           cdata: Cmd,
                                           get_crate_data: G,
                                           callback: F) where
-    F: FnMut(DefLike, ast::Name, hir::Visibility),
+    F: FnMut(DefLike, ast::Name, ty::Visibility),
     G: FnMut(ast::CrateNum) -> Rc<crate_metadata>,
 {
     let root_doc = rbml::Doc::new(cdata.data());
@@ -1138,11 +1138,11 @@ pub fn get_struct_field_attrs(cdata: Cmd) -> FnvHashMap<DefId, Vec<ast::Attribut
     }).collect()
 }
 
-fn struct_field_family_to_visibility(family: Family) -> hir::Visibility {
+fn struct_field_family_to_visibility(family: Family) -> ty::Visibility {
     match family {
-      PublicField => hir::Public,
-      InheritedField => hir::Inherited,
-      _ => bug!()
+        PublicField => ty::Visibility::Public,
+        InheritedField => ty::Visibility::PrivateExternal,
+        _ => bug!()
     }
 }
 
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index d45650159e3..69f61cf97c0 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -249,7 +249,7 @@ fn encode_struct_fields(rbml_w: &mut Encoder,
 fn encode_enum_variant_info<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
                                       rbml_w: &mut Encoder,
                                       did: DefId,
-                                      vis: hir::Visibility,
+                                      vis: &hir::Visibility,
                                       index: &mut CrateIndex<'tcx>) {
     debug!("encode_enum_variant_info(did={:?})", did);
     let repr_hints = ecx.tcx.lookup_repr_hints(did);
@@ -355,7 +355,7 @@ fn encode_info_for_mod(ecx: &EncodeContext,
                        attrs: &[ast::Attribute],
                        id: NodeId,
                        name: Name,
-                       vis: hir::Visibility) {
+                       vis: &hir::Visibility) {
     rbml_w.start_tag(tag_items_data_item);
     encode_def_id_and_key(ecx, rbml_w, ecx.tcx.map.local_def_id(id));
     encode_family(rbml_w, 'm');
@@ -383,7 +383,7 @@ fn encode_info_for_mod(ecx: &EncodeContext,
     encode_deprecation(rbml_w, depr);
 
     // Encode the reexports of this module, if this module is public.
-    if vis == hir::Public {
+    if *vis == hir::Public {
         debug!("(encoding info for module) encoding reexports for {}", id);
         encode_reexports(ecx, rbml_w, id);
     }
@@ -393,21 +393,31 @@ fn encode_info_for_mod(ecx: &EncodeContext,
 }
 
 fn encode_struct_field_family(rbml_w: &mut Encoder,
-                              visibility: hir::Visibility) {
-    encode_family(rbml_w, match visibility {
-        hir::Public => 'g',
-        hir::Inherited => 'N'
-    });
+                              visibility: ty::Visibility) {
+    encode_family(rbml_w, if visibility.is_public() { 'g' } else { 'N' });
 }
 
-fn encode_visibility(rbml_w: &mut Encoder, visibility: hir::Visibility) {
-    let ch = match visibility {
-        hir::Public => 'y',
-        hir::Inherited => 'i',
-    };
+fn encode_visibility<T: HasVisibility>(rbml_w: &mut Encoder, visibility: T) {
+    let ch = if visibility.is_public() { 'y' } else { 'i' };
     rbml_w.wr_tagged_u8(tag_items_data_item_visibility, ch as u8);
 }
 
+trait HasVisibility: Sized {
+    fn is_public(self) -> bool;
+}
+
+impl<'a> HasVisibility for &'a hir::Visibility {
+    fn is_public(self) -> bool {
+        *self == hir::Public
+    }
+}
+
+impl HasVisibility for ty::Visibility {
+    fn is_public(self) -> bool {
+        self == ty::Visibility::Public
+    }
+}
+
 fn encode_constness(rbml_w: &mut Encoder, constness: hir::Constness) {
     rbml_w.start_tag(tag_items_data_item_constness);
     let ch = match constness {
@@ -861,7 +871,7 @@ fn encode_info_for_item<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
     debug!("encoding info for item at {}",
            tcx.sess.codemap().span_to_string(item.span));
 
-    let vis = item.vis;
+    let vis = &item.vis;
     let def_id = ecx.tcx.map.local_def_id(item.id);
     let stab = stability::lookup_stability(tcx, ecx.tcx.map.local_def_id(item.id));
     let depr = stability::lookup_deprecation(tcx, ecx.tcx.map.local_def_id(item.id));
@@ -932,7 +942,7 @@ fn encode_info_for_item<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
                             &item.attrs,
                             item.id,
                             item.name,
-                            item.vis);
+                            &item.vis);
       }
       hir::ItemForeignMod(ref fm) => {
         index.record(def_id, rbml_w);
@@ -1336,7 +1346,7 @@ fn encode_info_for_foreign_item<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
     index.record(def_id, rbml_w);
     rbml_w.start_tag(tag_items_data_item);
     encode_def_id_and_key(ecx, rbml_w, def_id);
-    encode_visibility(rbml_w, nitem.vis);
+    encode_visibility(rbml_w, &nitem.vis);
     match nitem.node {
       hir::ForeignItemFn(ref fndecl, _) => {
         encode_family(rbml_w, FN_FAMILY);
@@ -1443,7 +1453,7 @@ fn encode_info_for_items<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
                         &[],
                         CRATE_NODE_ID,
                         syntax::parse::token::intern(&ecx.link_meta.crate_name),
-                        hir::Public);
+                        &hir::Public);
 
     krate.visit_all_items(&mut EncodeVisitor {
         index: &mut index,
diff --git a/src/librustc_privacy/lib.rs b/src/librustc_privacy/lib.rs
index 8840bd42717..a6ce4cc3ee4 100644
--- a/src/librustc_privacy/lib.rs
+++ b/src/librustc_privacy/lib.rs
@@ -382,26 +382,18 @@ struct PrivacyVisitor<'a, 'tcx: 'a> {
 }
 
 impl<'a, 'tcx> PrivacyVisitor<'a, 'tcx> {
-    fn item_is_visible(&self, did: DefId) -> bool {
-        let visibility = match self.tcx.map.as_local_node_id(did) {
-            Some(node_id) => self.tcx.map.expect_item(node_id).vis,
-            None => self.tcx.sess.cstore.visibility(did),
-        };
-        visibility == hir::Public || self.private_accessible(did)
-    }
-
-    /// True if `did` is private-accessible
-    fn private_accessible(&self, did: DefId) -> bool {
+    fn item_is_accessible(&self, did: DefId) -> bool {
         match self.tcx.map.as_local_node_id(did) {
-            Some(node_id) => self.tcx.map.private_item_is_visible_from(node_id, self.curitem),
-            None => false,
-        }
+            Some(node_id) =>
+                ty::Visibility::from_hir(&self.tcx.map.expect_item(node_id).vis, node_id, self.tcx),
+            None => self.tcx.sess.cstore.visibility(did),
+        }.is_accessible_from(self.curitem, &self.tcx.map)
     }
 
     // Checks that a field is in scope.
     fn check_field(&mut self, span: Span, def: ty::AdtDef<'tcx>, field: ty::FieldDef<'tcx>) {
         if def.adt_kind() == ty::AdtKind::Struct &&
-                field.vis != hir::Public && !self.private_accessible(def.did) {
+           !field.vis.is_accessible_from(self.curitem, &self.tcx.map) {
             span_err!(self.tcx.sess, span, E0451, "field `{}` of struct `{}` is private",
                       field.name, self.tcx.item_path_str(def.did));
         }
@@ -412,7 +404,7 @@ impl<'a, 'tcx> PrivacyVisitor<'a, 'tcx> {
         match self.tcx.impl_or_trait_item(method_def_id).container() {
             // Trait methods are always all public. The only controlling factor
             // is whether the trait itself is accessible or not.
-            ty::TraitContainer(trait_def_id) if !self.item_is_visible(trait_def_id) => {
+            ty::TraitContainer(trait_def_id) if !self.item_is_accessible(trait_def_id) => {
                 let msg = format!("source trait `{}` is private",
                                   self.tcx.item_path_str(trait_def_id));
                 self.tcx.sess.span_err(span, &msg);
@@ -464,7 +456,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for PrivacyVisitor<'a, 'tcx> {
                         _ => expr_ty
                     }.ty_adt_def().unwrap();
                     let any_priv = def.struct_variant().fields.iter().any(|f| {
-                        f.vis != hir::Public && !self.private_accessible(def.did)
+                        !f.vis.is_accessible_from(self.curitem, &self.tcx.map)
                     });
                     if any_priv {
                         span_err!(self.tcx.sess, expr.span, E0450,
@@ -548,8 +540,8 @@ impl<'a, 'tcx> SanePrivacyVisitor<'a, 'tcx> {
     /// Such qualifiers can be set by syntax extensions even if the parser doesn't allow them,
     /// so we check things like variant fields too.
     fn check_sane_privacy(&self, item: &hir::Item) {
-        let check_inherited = |sp, vis, note: &str| {
-            if vis != hir::Inherited {
+        let check_inherited = |sp, vis: &hir::Visibility, note: &str| {
+            if *vis != hir::Inherited {
                 let mut err = struct_span_err!(self.tcx.sess, sp, E0449,
                                                "unnecessary visibility qualifier");
                 if !note.is_empty() {
@@ -561,29 +553,29 @@ impl<'a, 'tcx> SanePrivacyVisitor<'a, 'tcx> {
 
         match item.node {
             hir::ItemImpl(_, _, _, Some(..), _, ref impl_items) => {
-                check_inherited(item.span, item.vis,
+                check_inherited(item.span, &item.vis,
                                 "visibility qualifiers have no effect on trait impls");
                 for impl_item in impl_items {
-                    check_inherited(impl_item.span, impl_item.vis,
+                    check_inherited(impl_item.span, &impl_item.vis,
                                     "visibility qualifiers have no effect on trait impl items");
                 }
             }
             hir::ItemImpl(_, _, _, None, _, _) => {
-                check_inherited(item.span, item.vis,
+                check_inherited(item.span, &item.vis,
                                 "place qualifiers on individual methods instead");
             }
             hir::ItemDefaultImpl(..) => {
-                check_inherited(item.span, item.vis,
+                check_inherited(item.span, &item.vis,
                                 "visibility qualifiers have no effect on trait impls");
             }
             hir::ItemForeignMod(..) => {
-                check_inherited(item.span, item.vis,
+                check_inherited(item.span, &item.vis,
                                 "place qualifiers on individual functions instead");
             }
             hir::ItemEnum(ref def, _) => {
                 for variant in &def.variants {
                     for field in variant.node.data.fields() {
-                        check_inherited(field.span, field.vis,
+                        check_inherited(field.span, &field.vis,
                                         "visibility qualifiers have no effect on variant fields");
                     }
                 }
@@ -659,8 +651,8 @@ impl<'a, 'tcx> ObsoleteVisiblePrivateTypesVisitor<'a, 'tcx> {
         }
     }
 
-    fn item_is_public(&self, id: &ast::NodeId, vis: hir::Visibility) -> bool {
-        self.access_levels.is_reachable(*id) || vis == hir::Public
+    fn item_is_public(&self, id: &ast::NodeId, vis: &hir::Visibility) -> bool {
+        self.access_levels.is_reachable(*id) || *vis == hir::Public
     }
 }
 
@@ -789,7 +781,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for ObsoleteVisiblePrivateTypesVisitor<'a, 'tcx>
                                 match impl_item.node {
                                     hir::ImplItemKind::Const(..) |
                                     hir::ImplItemKind::Method(..)
-                                        if self.item_is_public(&impl_item.id, impl_item.vis) =>
+                                        if self.item_is_public(&impl_item.id, &impl_item.vis) =>
                                     {
                                         intravisit::walk_impl_item(self, impl_item)
                                     }
@@ -831,14 +823,14 @@ impl<'a, 'tcx, 'v> Visitor<'v> for ObsoleteVisiblePrivateTypesVisitor<'a, 'tcx>
                     for impl_item in impl_items {
                         match impl_item.node {
                             hir::ImplItemKind::Const(..) => {
-                                if self.item_is_public(&impl_item.id, impl_item.vis) {
+                                if self.item_is_public(&impl_item.id, &impl_item.vis) {
                                     found_pub_static = true;
                                     intravisit::walk_impl_item(self, impl_item);
                                 }
                             }
                             hir::ImplItemKind::Method(ref sig, _) => {
                                 if sig.explicit_self.node == hir::SelfStatic &&
-                                      self.item_is_public(&impl_item.id, impl_item.vis) {
+                                      self.item_is_public(&impl_item.id, &impl_item.vis) {
                                     found_pub_static = true;
                                     intravisit::walk_impl_item(self, impl_item);
                                 }
@@ -858,7 +850,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for ObsoleteVisiblePrivateTypesVisitor<'a, 'tcx>
             hir::ItemTy(..) => return,
 
             // not at all public, so we don't care
-            _ if !self.item_is_public(&item.id, item.vis) => {
+            _ if !self.item_is_public(&item.id, &item.vis) => {
                 return;
             }
 
@@ -944,27 +936,41 @@ impl<'a, 'tcx, 'v> Visitor<'v> for ObsoleteVisiblePrivateTypesVisitor<'a, 'tcx>
 
 struct SearchInterfaceForPrivateItemsVisitor<'a, 'tcx: 'a> {
     tcx: &'a TyCtxt<'tcx>,
-    // Do not report an error when a private type is found
-    is_quiet: bool,
-    // Is private component found?
-    is_public: bool,
+    /// The visitor checks that each component type is at least this visible
+    required_visibility: ty::Visibility,
+    /// The visibility of the least visible component that has been visited
+    min_visibility: ty::Visibility,
     old_error_set: &'a NodeSet,
 }
 
 impl<'a, 'tcx: 'a> SearchInterfaceForPrivateItemsVisitor<'a, 'tcx> {
-    // Check if the type alias contain private types when substituted
-    fn is_public_type_alias(&self, item: &hir::Item, path: &hir::Path) -> bool {
+    fn new(tcx: &'a TyCtxt<'tcx>, old_error_set: &'a NodeSet) -> Self {
+        SearchInterfaceForPrivateItemsVisitor {
+            tcx: tcx,
+            min_visibility: ty::Visibility::Public,
+            required_visibility: ty::Visibility::PrivateExternal,
+            old_error_set: old_error_set,
+        }
+    }
+}
+
+impl<'a, 'tcx: 'a> SearchInterfaceForPrivateItemsVisitor<'a, 'tcx> {
+    // Return the visibility of the type alias's least visible component type when substituted
+    fn substituted_alias_visibility(&self, item: &hir::Item, path: &hir::Path)
+                                    -> Option<ty::Visibility> {
         // We substitute type aliases only when determining impl publicity
         // FIXME: This will probably change and all type aliases will be substituted,
         // requires an amendment to RFC 136.
-        if !self.is_quiet {
-            return false
+        if self.required_visibility != ty::Visibility::PrivateExternal {
+            return None;
         }
         // Type alias is considered public if the aliased type is
         // public, even if the type alias itself is private. So, something
         // like `type A = u8; pub fn f() -> A {...}` doesn't cause an error.
         if let hir::ItemTy(ref ty, ref generics) = item.node {
-            let mut check = SearchInterfaceForPrivateItemsVisitor { is_public: true, ..*self };
+            let mut check = SearchInterfaceForPrivateItemsVisitor {
+                min_visibility: ty::Visibility::Public, ..*self
+            };
             check.visit_ty(ty);
             // If a private type alias with default type parameters is used in public
             // interface we must ensure, that the defaults are public if they are actually used.
@@ -978,26 +984,23 @@ impl<'a, 'tcx: 'a> SearchInterfaceForPrivateItemsVisitor<'a, 'tcx> {
                     check.visit_ty(default_ty);
                 }
             }
-            check.is_public
+            Some(check.min_visibility)
         } else {
-            false
+            None
         }
     }
 }
 
 impl<'a, 'tcx: 'a, 'v> Visitor<'v> for SearchInterfaceForPrivateItemsVisitor<'a, 'tcx> {
     fn visit_ty(&mut self, ty: &hir::Ty) {
-        if self.is_quiet && !self.is_public {
-            // We are in quiet mode and a private type is already found, no need to proceed
-            return
-        }
         if let hir::TyPath(_, ref path) = ty.node {
             let def = self.tcx.def_map.borrow().get(&ty.id).unwrap().full_def();
             match def {
                 Def::PrimTy(..) | Def::SelfTy(..) | Def::TyParam(..) => {
                     // Public
                 }
-                Def::AssociatedTy(..) if self.is_quiet => {
+                Def::AssociatedTy(..)
+                    if self.required_visibility == ty::Visibility::PrivateExternal => {
                     // Conservatively approximate the whole type alias as public without
                     // recursing into its components when determining impl publicity.
                     // For example, `impl <Type as Trait>::Alias {...}` may be a public impl
@@ -1011,21 +1014,24 @@ impl<'a, 'tcx: 'a, 'v> Visitor<'v> for SearchInterfaceForPrivateItemsVisitor<'a,
                     // Non-local means public (private items can't leave their crate, modulo bugs)
                     if let Some(node_id) = self.tcx.map.as_local_node_id(def_id) {
                         let item = self.tcx.map.expect_item(node_id);
-                        if item.vis != hir::Public && !self.is_public_type_alias(item, path) {
-                            if !self.is_quiet {
-                                if self.old_error_set.contains(&ty.id) {
-                                    span_err!(self.tcx.sess, ty.span, E0446,
-                                              "private type in public interface");
-                                } else {
-                                    self.tcx.sess.add_lint (
-                                        lint::builtin::PRIVATE_IN_PUBLIC,
-                                        node_id,
-                                        ty.span,
-                                        format!("private type in public interface"),
-                                    );
-                                }
+                        let vis = match self.substituted_alias_visibility(item, path) {
+                            Some(vis) => vis,
+                            None => ty::Visibility::from_hir(&item.vis, node_id, &self.tcx),
+                        };
+
+                        if !vis.is_at_least(self.min_visibility, &self.tcx.map) {
+                            self.min_visibility = vis;
+                        }
+                        if !vis.is_at_least(self.required_visibility, &self.tcx.map) {
+                            if self.old_error_set.contains(&ty.id) {
+                                span_err!(self.tcx.sess, ty.span, E0446,
+                                          "private type in public interface");
+                            } else {
+                                self.tcx.sess.add_lint(lint::builtin::PRIVATE_IN_PUBLIC,
+                                                       node_id,
+                                                       ty.span,
+                                                       format!("private type in public interface"));
                             }
-                            self.is_public = false;
                         }
                     }
                 }
@@ -1037,28 +1043,26 @@ impl<'a, 'tcx: 'a, 'v> Visitor<'v> for SearchInterfaceForPrivateItemsVisitor<'a,
     }
 
     fn visit_trait_ref(&mut self, trait_ref: &hir::TraitRef) {
-        if self.is_quiet && !self.is_public {
-            // We are in quiet mode and a private type is already found, no need to proceed
-            return
-        }
         // Non-local means public (private items can't leave their crate, modulo bugs)
         let def_id = self.tcx.trait_ref_to_def_id(trait_ref);
         if let Some(node_id) = self.tcx.map.as_local_node_id(def_id) {
             let item = self.tcx.map.expect_item(node_id);
-            if item.vis != hir::Public {
-                if !self.is_quiet {
-                    if self.old_error_set.contains(&trait_ref.ref_id) {
-                        span_err!(self.tcx.sess, trait_ref.path.span, E0445,
-                                  "private trait in public interface");
-                    } else {
-                        self.tcx.sess.add_lint(lint::builtin::PRIVATE_IN_PUBLIC,
-                                               node_id,
-                                               trait_ref.path.span,
-                                               "private trait in public interface (error E0445)"
-                                                    .to_string());
-                    }
+            let vis = ty::Visibility::from_hir(&item.vis, node_id, &self.tcx);
+
+            if !vis.is_at_least(self.min_visibility, &self.tcx.map) {
+                self.min_visibility = vis;
+            }
+            if !vis.is_at_least(self.required_visibility, &self.tcx.map) {
+                if self.old_error_set.contains(&trait_ref.ref_id) {
+                    span_err!(self.tcx.sess, trait_ref.path.span, E0445,
+                              "private trait in public interface");
+                } else {
+                    self.tcx.sess.add_lint(lint::builtin::PRIVATE_IN_PUBLIC,
+                                           node_id,
+                                           trait_ref.path.span,
+                                           "private trait in public interface (error E0445)"
+                                                .to_string());
                 }
-                self.is_public = false;
             }
         }
 
@@ -1080,29 +1084,29 @@ struct PrivateItemsInPublicInterfacesVisitor<'a, 'tcx: 'a> {
 
 impl<'a, 'tcx> PrivateItemsInPublicInterfacesVisitor<'a, 'tcx> {
     // A type is considered public if it doesn't contain any private components
-    fn is_public_ty(&self, ty: &hir::Ty) -> bool {
-        let mut check = SearchInterfaceForPrivateItemsVisitor {
-            tcx: self.tcx, is_quiet: true, is_public: true, old_error_set: self.old_error_set
-        };
+    fn ty_visibility(&self, ty: &hir::Ty) -> ty::Visibility {
+        let mut check = SearchInterfaceForPrivateItemsVisitor::new(self.tcx, self.old_error_set);
         check.visit_ty(ty);
-        check.is_public
+        check.min_visibility
     }
 
     // A trait reference is considered public if it doesn't contain any private components
-    fn is_public_trait_ref(&self, trait_ref: &hir::TraitRef) -> bool {
-        let mut check = SearchInterfaceForPrivateItemsVisitor {
-            tcx: self.tcx, is_quiet: true, is_public: true, old_error_set: self.old_error_set
-        };
+    fn trait_ref_visibility(&self, trait_ref: &hir::TraitRef) -> ty::Visibility {
+        let mut check = SearchInterfaceForPrivateItemsVisitor::new(self.tcx, self.old_error_set);
         check.visit_trait_ref(trait_ref);
-        check.is_public
+        check.min_visibility
     }
 }
 
 impl<'a, 'tcx, 'v> Visitor<'v> for PrivateItemsInPublicInterfacesVisitor<'a, 'tcx> {
     fn visit_item(&mut self, item: &hir::Item) {
-        let mut check = SearchInterfaceForPrivateItemsVisitor {
-            tcx: self.tcx, is_quiet: false, is_public: true, old_error_set: self.old_error_set
+        let min = |vis1: ty::Visibility, vis2| {
+            if vis1.is_at_least(vis2, &self.tcx.map) { vis2 } else { vis1 }
         };
+
+        let mut check = SearchInterfaceForPrivateItemsVisitor::new(self.tcx, self.old_error_set);
+        let item_visibility = ty::Visibility::from_hir(&item.vis, item.id, &self.tcx);
+
         match item.node {
             // Crates are always public
             hir::ItemExternCrate(..) => {}
@@ -1113,27 +1117,26 @@ impl<'a, 'tcx, 'v> Visitor<'v> for PrivateItemsInPublicInterfacesVisitor<'a, 'tc
             // Subitems of these items have inherited publicity
             hir::ItemConst(..) | hir::ItemStatic(..) | hir::ItemFn(..) |
             hir::ItemEnum(..) | hir::ItemTrait(..) | hir::ItemTy(..) => {
-                if item.vis == hir::Public {
-                    check.visit_item(item);
-                }
+                check.required_visibility = item_visibility;
+                check.visit_item(item);
             }
             // Subitems of foreign modules have their own publicity
             hir::ItemForeignMod(ref foreign_mod) => {
                 for foreign_item in &foreign_mod.items {
-                    if foreign_item.vis == hir::Public {
-                        check.visit_foreign_item(foreign_item);
-                    }
+                    check.required_visibility =
+                        ty::Visibility::from_hir(&foreign_item.vis, item.id, &self.tcx);
+                    check.visit_foreign_item(foreign_item);
                 }
             }
             // Subitems of structs have their own publicity
             hir::ItemStruct(ref struct_def, ref generics) => {
-                if item.vis == hir::Public {
-                    check.visit_generics(generics);
-                    for field in struct_def.fields() {
-                        if field.vis == hir::Public {
-                            check.visit_struct_field(field);
-                        }
-                    }
+                check.required_visibility = item_visibility;
+                check.visit_generics(generics);
+
+                for field in struct_def.fields() {
+                    let field_visibility = ty::Visibility::from_hir(&field.vis, item.id, &self.tcx);
+                    check.required_visibility = min(item_visibility, field_visibility);
+                    check.visit_struct_field(field);
                 }
             }
             // The interface is empty
@@ -1141,23 +1144,25 @@ impl<'a, 'tcx, 'v> Visitor<'v> for PrivateItemsInPublicInterfacesVisitor<'a, 'tc
             // An inherent impl is public when its type is public
             // Subitems of inherent impls have their own publicity
             hir::ItemImpl(_, _, ref generics, None, ref ty, ref impl_items) => {
-                if self.is_public_ty(ty) {
-                    check.visit_generics(generics);
-                    for impl_item in impl_items {
-                        if impl_item.vis == hir::Public {
-                            check.visit_impl_item(impl_item);
-                        }
-                    }
+                let ty_vis = self.ty_visibility(ty);
+                check.required_visibility = ty_vis;
+                check.visit_generics(generics);
+
+                for impl_item in impl_items {
+                    let impl_item_vis =
+                        ty::Visibility::from_hir(&impl_item.vis, item.id, &self.tcx);
+                    check.required_visibility = min(impl_item_vis, ty_vis);
+                    check.visit_impl_item(impl_item);
                 }
             }
             // A trait impl is public when both its type and its trait are public
             // Subitems of trait impls have inherited publicity
             hir::ItemImpl(_, _, ref generics, Some(ref trait_ref), ref ty, ref impl_items) => {
-                if self.is_public_ty(ty) && self.is_public_trait_ref(trait_ref) {
-                    check.visit_generics(generics);
-                    for impl_item in impl_items {
-                        check.visit_impl_item(impl_item);
-                    }
+                let vis = min(self.ty_visibility(ty), self.trait_ref_visibility(trait_ref));
+                check.required_visibility = vis;
+                check.visit_generics(generics);
+                for impl_item in impl_items {
+                    check.visit_impl_item(impl_item);
                 }
             }
         }
diff --git a/src/librustc_resolve/build_reduced_graph.rs b/src/librustc_resolve/build_reduced_graph.rs
index a422b09f96b..003450cd6fd 100644
--- a/src/librustc_resolve/build_reduced_graph.rs
+++ b/src/librustc_resolve/build_reduced_graph.rs
@@ -26,7 +26,7 @@ use rustc::middle::cstore::{CrateStore, ChildItem, DlDef};
 use rustc::lint;
 use rustc::hir::def::*;
 use rustc::hir::def_id::{CRATE_DEF_INDEX, DefId};
-use rustc::ty::VariantKind;
+use rustc::ty::{self, VariantKind};
 
 use syntax::ast::Name;
 use syntax::attr::AttrMetaMethods;
@@ -434,7 +434,7 @@ impl<'b, 'tcx:'b> Resolver<'b, 'tcx> {
         }
 
         let name = xcdef.name;
-        let is_public = xcdef.vis == hir::Public || parent.is_trait();
+        let is_public = xcdef.vis == ty::Visibility::Public || parent.is_trait();
 
         let mut modifiers = DefModifiers::empty();
         if is_public {
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index 299a8c0299d..5f4244caa62 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -1714,9 +1714,10 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                             match self.resolve_crate_relative_path(prefix.span,
                                                                    &prefix.segments,
                                                                    TypeNS) {
-                                Some(def) =>
+                                Ok(def) =>
                                     self.record_def(item.id, PathResolution::new(def, 0)),
-                                None => {
+                                Err(true) => self.record_def(item.id, err_path_resolution()),
+                                Err(false) => {
                                     resolve_error(self,
                                                   prefix.span,
                                                   ResolutionError::FailedToResolve(
@@ -1835,7 +1836,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                                trait_path: &Path,
                                path_depth: usize)
                                -> Result<PathResolution, ()> {
-        if let Some(path_res) = self.resolve_path(id, trait_path, path_depth, TypeNS) {
+        self.resolve_path(id, trait_path, path_depth, TypeNS).and_then(|path_res| {
             if let Def::Trait(_) = path_res.base_def {
                 debug!("(resolving trait) found trait def: {:?}", path_res);
                 Ok(path_res)
@@ -1855,9 +1856,10 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                     }
                 }
                 err.emit();
-                Err(())
+                Err(true)
             }
-        } else {
+        }).map_err(|error_reported| {
+            if error_reported { return }
 
             // find possible candidates
             let trait_name = trait_path.segments.last().unwrap().identifier.name;
@@ -1880,8 +1882,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                 );
 
             resolve_error(self, trait_path.span, error);
-            Err(())
-        }
+        })
     }
 
     fn resolve_generics(&mut self, generics: &Generics) {
@@ -1890,15 +1891,18 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                 &hir::WherePredicate::BoundPredicate(_) |
                 &hir::WherePredicate::RegionPredicate(_) => {}
                 &hir::WherePredicate::EqPredicate(ref eq_pred) => {
-                    let path_res = self.resolve_path(eq_pred.id, &eq_pred.path, 0, TypeNS);
-                    if let Some(PathResolution { base_def: Def::TyParam(..), .. }) = path_res {
-                        self.record_def(eq_pred.id, path_res.unwrap());
-                    } else {
-                        resolve_error(self,
-                                      eq_pred.span,
-                                      ResolutionError::UndeclaredAssociatedType);
+                    self.resolve_path(eq_pred.id, &eq_pred.path, 0, TypeNS).and_then(|path_res| {
+                        if let PathResolution { base_def: Def::TyParam(..), .. } = path_res {
+                            Ok(self.record_def(eq_pred.id, path_res))
+                        } else {
+                            Err(false)
+                        }
+                    }).map_err(|error_reported| {
                         self.record_def(eq_pred.id, err_path_resolution());
-                    }
+                        if error_reported { return }
+                        let error_variant = ResolutionError::UndeclaredAssociatedType;
+                        resolve_error(self, eq_pred.span, error_variant);
+                    }).unwrap_or(());
                 }
             }
         }
@@ -2168,21 +2172,18 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
                 // This is a path in the type namespace. Walk through scopes
                 // looking for it.
-                match resolution {
-                    Some(def) => {
-                        // Write the result into the def map.
-                        debug!("(resolving type) writing resolution for `{}` (id {}) = {:?}",
-                               path_names_to_string(path, 0),
-                               ty.id,
-                               def);
-                        self.record_def(ty.id, def);
-                    }
-                    None => {
-                        self.record_def(ty.id, err_path_resolution());
-
-                        // Keep reporting some errors even if they're ignored above.
-                        self.resolve_path(ty.id, path, 0, TypeNS);
+                if let Some(def) = resolution {
+                    // Write the result into the def map.
+                    debug!("(resolving type) writing resolution for `{}` (id {}) = {:?}",
+                           path_names_to_string(path, 0), ty.id, def);
+                    self.record_def(ty.id, def);
+                } else {
+                    self.record_def(ty.id, err_path_resolution());
 
+                    // Keep reporting some errors even if they're ignored above.
+                    if let Err(true) = self.resolve_path(ty.id, path, 0, TypeNS) {
+                        // `resolve_path` already reported the error
+                    } else {
                         let kind = if maybe_qself.is_some() {
                             "associated type"
                         } else {
@@ -2481,11 +2482,11 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
 
                 PatKind::Struct(ref path, _, _) => {
                     match self.resolve_path(pat_id, path, 0, TypeNS) {
-                        Some(definition) => {
+                        Ok(definition) => {
                             self.record_def(pattern.id, definition);
                         }
-                        result => {
-                            debug!("(resolving pattern) didn't find struct def: {:?}", result);
+                        Err(true) => self.record_def(pattern.id, err_path_resolution()),
+                        Err(false) => {
                             resolve_error(
                                 self,
                                 path.span,
@@ -2552,14 +2553,14 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         }
 
         let mut resolution = self.with_no_errors(|this| {
-            this.resolve_path(id, path, 0, namespace)
+            this.resolve_path(id, path, 0, namespace).ok()
         });
         for depth in 1..max_assoc_types {
             if resolution.is_some() {
                 break;
             }
             self.with_no_errors(|this| {
-                resolution = this.resolve_path(id, path, depth, TypeNS);
+                resolution = this.resolve_path(id, path, depth, TypeNS).ok();
             });
         }
         if let Some(Def::Mod(_)) = resolution.map(|r| r.base_def) {
@@ -2572,7 +2573,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
     /// Skips `path_depth` trailing segments, which is also reflected in the
     /// returned value. See `hir::def::PathResolution` for more info.
     fn resolve_path(&mut self, id: NodeId, path: &Path, path_depth: usize, namespace: Namespace)
-                    -> Option<PathResolution> {
+                    -> Result<PathResolution, bool /* true if an error was reported */ > {
         let span = path.span;
         let segments = &path.segments[..path.segments.len() - path_depth];
 
@@ -2611,14 +2612,14 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
             //
             // Such behavior is required for backward compatibility.
             // The same fallback is used when `a` resolves to nothing.
-            let unqualified_def = resolve_identifier_with_fallback(self, true);
-            return unqualified_def.and_then(|def| self.adjust_local_def(def, span)).map(mk_res);
+            let def = resolve_identifier_with_fallback(self, true).ok_or(false);
+            return def.and_then(|def| self.adjust_local_def(def, span).ok_or(true)).map(mk_res);
         }
 
         let unqualified_def = resolve_identifier_with_fallback(self, false);
         let def = self.resolve_module_relative_path(span, segments, namespace);
         match (def, unqualified_def) {
-            (Some(d), Some(ref ud)) if d == ud.def => {
+            (Ok(d), Some(ref ud)) if d == ud.def => {
                 self.session
                     .add_lint(lint::builtin::UNUSED_QUALIFICATIONS,
                               id,
@@ -2739,7 +2740,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                                     span: Span,
                                     segments: &[hir::PathSegment],
                                     namespace: Namespace)
-                                    -> Option<Def> {
+                                    -> Result<Def, bool /* true if an error was reported */> {
         let module_path = segments.split_last()
                                   .unwrap()
                                   .1
@@ -2760,9 +2761,9 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                 };
 
                 resolve_error(self, span, ResolutionError::FailedToResolve(&msg));
-                return None;
+                return Err(true);
             }
-            Indeterminate => return None,
+            Indeterminate => return Err(false),
             Success(resulting_module) => {
                 containing_module = resulting_module;
             }
@@ -2773,7 +2774,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         result.success().map(|binding| {
             self.check_privacy(containing_module, name, binding, span);
             binding.def().unwrap()
-        })
+        }).ok_or(false)
     }
 
     /// Invariant: This must be called only during main resolution, not during
@@ -2782,7 +2783,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                                    span: Span,
                                    segments: &[hir::PathSegment],
                                    namespace: Namespace)
-                                   -> Option<Def> {
+                                   -> Result<Def, bool /* true if an error was reported */> {
         let module_path = segments.split_last()
                                   .unwrap()
                                   .1
@@ -2808,10 +2809,10 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                 };
 
                 resolve_error(self, span, ResolutionError::FailedToResolve(&msg));
-                return None;
+                return Err(true);
             }
 
-            Indeterminate => return None,
+            Indeterminate => return Err(false),
 
             Success(resulting_module) => {
                 containing_module = resulting_module;
@@ -2823,7 +2824,7 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
         result.success().map(|binding| {
             self.check_privacy(containing_module, name, binding, span);
             binding.def().unwrap()
-        })
+        }).ok_or(false)
     }
 
     fn with_no_errors<T, F>(&mut self, f: F) -> T
@@ -3038,25 +3039,26 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                     });
 
                     self.record_def(expr.id, err_path_resolution());
-                    match type_res.map(|r| r.base_def) {
-                        Some(Def::Struct(..)) => {
-                            let mut err = resolve_struct_error(self,
-                                expr.span,
-                                ResolutionError::StructVariantUsedAsFunction(&path_name));
-
-                            let msg = format!("did you mean to write: `{} {{ /* fields */ }}`?",
-                                              path_name);
-                            if self.emit_errors {
-                                err.fileline_help(expr.span, &msg);
-                            } else {
-                                err.span_help(expr.span, &msg);
-                            }
-                            err.emit();
-                        }
-                        _ => {
-                            // Keep reporting some errors even if they're ignored above.
-                            self.resolve_path(expr.id, path, 0, ValueNS);
 
+                    if let Ok(Def::Struct(..)) = type_res.map(|r| r.base_def) {
+                        let error_variant =
+                            ResolutionError::StructVariantUsedAsFunction(&path_name);
+                        let mut err = resolve_struct_error(self, expr.span, error_variant);
+
+                        let msg = format!("did you mean to write: `{} {{ /* fields */ }}`?",
+                                          path_name);
+
+                        if self.emit_errors {
+                            err.fileline_help(expr.span, &msg);
+                        } else {
+                            err.span_help(expr.span, &msg);
+                        }
+                        err.emit();
+                    } else {
+                        // Keep reporting some errors even if they're ignored above.
+                        if let Err(true) = self.resolve_path(expr.id, path, 0, ValueNS) {
+                            // `resolve_path` already reported the error
+                        } else {
                             let mut method_scope = false;
                             self.value_ribs.iter().rev().all(|rib| {
                                 method_scope = match rib.kind {
@@ -3130,8 +3132,9 @@ impl<'a, 'tcx> Resolver<'a, 'tcx> {
                 // check to ensure that the path is actually a structure; that
                 // is checked later during typeck.
                 match self.resolve_path(expr.id, path, 0, TypeNS) {
-                    Some(definition) => self.record_def(expr.id, definition),
-                    None => {
+                    Ok(definition) => self.record_def(expr.id, definition),
+                    Err(true) => self.record_def(expr.id, err_path_resolution()),
+                    Err(false) => {
                         debug!("(resolving expression) didn't find struct def",);
 
                         resolve_error(self,
diff --git a/src/librustc_typeck/check/method/mod.rs b/src/librustc_typeck/check/method/mod.rs
index 3f069a68316..31d95af4fbb 100644
--- a/src/librustc_typeck/check/method/mod.rs
+++ b/src/librustc_typeck/check/method/mod.rs
@@ -343,7 +343,7 @@ pub fn resolve_ufcs<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
     let def = pick.item.def();
 
     if let probe::InherentImplPick = pick.kind {
-        if pick.item.vis() != hir::Public && !fcx.private_item_is_visible(def.def_id()) {
+        if !pick.item.vis().is_accessible_from(fcx.body_id, &fcx.tcx().map) {
             let msg = format!("{} `{}` is private", def.kind_name(), &method_name.as_str());
             fcx.tcx().sess.span_err(span, &msg);
         }
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index 7d98eac30c5..0ffbbfea84e 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -412,7 +412,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
             return self.record_static_candidate(ImplSource(impl_def_id));
         }
 
-        if item.vis() != hir::Public && !self.fcx.private_item_is_visible(item.def_id()) {
+        if !item.vis().is_accessible_from(self.fcx.body_id, &self.tcx().map) {
             self.private_candidate = Some(item.def());
             return
         }
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index e7159e65eeb..45877d7099b 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -95,7 +95,7 @@ use rustc::traits::{self, report_fulfillment_errors, ProjectionMode};
 use rustc::ty::{GenericPredicates, TypeScheme};
 use rustc::ty::{ParamTy, ParameterEnvironment};
 use rustc::ty::{LvaluePreference, NoPreference, PreferMutLvalue};
-use rustc::ty::{self, ToPolyTraitRef, Ty, TyCtxt};
+use rustc::ty::{self, ToPolyTraitRef, Ty, TyCtxt, Visibility};
 use rustc::ty::{MethodCall, MethodCallee};
 use rustc::ty::adjustment;
 use rustc::ty::error::TypeError;
@@ -125,8 +125,7 @@ use syntax::ptr::P;
 use syntax::util::lev_distance::find_best_match_for_name;
 
 use rustc::hir::intravisit::{self, Visitor};
-use rustc::hir;
-use rustc::hir::{Visibility, PatKind};
+use rustc::hir::{self, PatKind};
 use rustc::hir::print as pprust;
 use rustc_back::slice;
 use rustc_const_eval::eval_repeat_count;
@@ -2055,13 +2054,6 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
             Err(errors) => { report_fulfillment_errors(self.infcx(), &errors); }
         }
     }
-
-    fn private_item_is_visible(&self, def_id: DefId) -> bool {
-        match self.tcx().map.as_local_node_id(def_id) {
-            Some(node_id) => self.tcx().map.private_item_is_visible_from(node_id, self.body_id),
-            None => false, // Private items from other crates are never visible
-        }
-    }
 }
 
 impl<'a, 'tcx> RegionScope for FnCtxt<'a, 'tcx> {
@@ -2967,7 +2959,7 @@ fn check_expr_with_expectation_and_lvalue_pref<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
                     debug!("struct named {:?}",  base_t);
                     if let Some(field) = base_def.struct_variant().find_field_named(field.node) {
                         let field_ty = fcx.field_ty(expr.span, field, substs);
-                        if field.vis == hir::Public || fcx.private_item_is_visible(base_def.did) {
+                        if field.vis.is_accessible_from(fcx.body_id, &fcx.tcx().map) {
                             return Some(field_ty);
                         }
                         private_candidate = Some((base_def.did, field_ty));
@@ -3079,7 +3071,7 @@ fn check_expr_with_expectation_and_lvalue_pref<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
                 debug!("tuple struct named {:?}",  base_t);
                 if let Some(field) = base_def.struct_variant().fields.get(idx.node) {
                     let field_ty = fcx.field_ty(expr.span, field, substs);
-                    if field.vis == hir::Public || fcx.private_item_is_visible(base_def.did) {
+                    if field.vis.is_accessible_from(fcx.body_id, &fcx.tcx().map) {
                         return Some(field_ty);
                     }
                     private_candidate = Some((base_def.did, field_ty));
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 9d76b4c5284..2e1a6846843 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -532,7 +532,7 @@ fn convert_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                             container: ImplOrTraitItemContainer,
                             name: ast::Name,
                             id: ast::NodeId,
-                            vis: hir::Visibility,
+                            vis: &hir::Visibility,
                             sig: &hir::MethodSig,
                             defaultness: hir::Defaultness,
                             untransformed_rcvr_ty: Ty<'tcx>,
@@ -555,7 +555,7 @@ fn convert_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                     ty_generic_predicates,
                                     fty,
                                     explicit_self_category,
-                                    vis,
+                                    ty::Visibility::from_hir(vis, id, ccx.tcx),
                                     defaultness,
                                     def_id,
                                     container);
@@ -602,7 +602,7 @@ fn convert_associated_const<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                       container: ImplOrTraitItemContainer,
                                       name: ast::Name,
                                       id: ast::NodeId,
-                                      vis: hir::Visibility,
+                                      vis: &hir::Visibility,
                                       defaultness: hir::Defaultness,
                                       ty: ty::Ty<'tcx>,
                                       has_value: bool)
@@ -614,7 +614,7 @@ fn convert_associated_const<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 
     let associated_const = Rc::new(ty::AssociatedConst {
         name: name,
-        vis: vis,
+        vis: ty::Visibility::from_hir(vis, id, ccx.tcx),
         defaultness: defaultness,
         def_id: ccx.tcx.map.local_def_id(id),
         container: container,
@@ -629,13 +629,13 @@ fn convert_associated_type<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                      container: ImplOrTraitItemContainer,
                                      name: ast::Name,
                                      id: ast::NodeId,
-                                     vis: hir::Visibility,
+                                     vis: &hir::Visibility,
                                      defaultness: hir::Defaultness,
                                      ty: Option<Ty<'tcx>>)
 {
     let associated_type = Rc::new(ty::AssociatedType {
         name: name,
-        vis: vis,
+        vis: ty::Visibility::from_hir(vis, id, ccx.tcx),
         defaultness: defaultness,
         ty: ty,
         def_id: ccx.tcx.map.local_def_id(id),
@@ -738,17 +738,6 @@ fn convert_item(ccx: &CrateCtxt, it: &hir::Item) {
             tcx.predicates.borrow_mut().insert(def_id, ty_predicates.clone());
 
 
-            // If there is a trait reference, treat the methods as always public.
-            // This is to work around some incorrect behavior in privacy checking:
-            // when the method belongs to a trait, it should acquire the privacy
-            // from the trait, not the impl. Forcing the visibility to be public
-            // makes things sorta work.
-            let parent_visibility = if opt_trait_ref.is_some() {
-                hir::Public
-            } else {
-                it.vis
-            };
-
             // Convert all the associated consts.
             // Also, check if there are any duplicate associated items
             let mut seen_type_items = FnvHashSet();
@@ -771,9 +760,12 @@ fn convert_item(ccx: &CrateCtxt, it: &hir::Item) {
                                                generics: ty_generics.clone(),
                                                ty: ty,
                                            });
+                    // Trait-associated constants are always public.
+                    let public = &hir::Public;
+                    let visibility = if opt_trait_ref.is_some() { public } else { &impl_item.vis };
                     convert_associated_const(ccx, ImplContainer(def_id),
                                              impl_item.name, impl_item.id,
-                                             impl_item.vis.inherit_from(parent_visibility),
+                                             visibility,
                                              impl_item.defaultness,
                                              ty, true /* has_value */);
                 }
@@ -790,18 +782,16 @@ fn convert_item(ccx: &CrateCtxt, it: &hir::Item) {
                     let typ = ccx.icx(&ty_predicates).to_ty(&ExplicitRscope, ty);
 
                     convert_associated_type(ccx, ImplContainer(def_id),
-                                            impl_item.name, impl_item.id, impl_item.vis,
+                                            impl_item.name, impl_item.id, &impl_item.vis,
                                             impl_item.defaultness, Some(typ));
                 }
             }
 
             for impl_item in impl_items {
                 if let hir::ImplItemKind::Method(ref sig, _) = impl_item.node {
-                    // if the method specifies a visibility, use that, otherwise
-                    // inherit the visibility from the impl (so `foo` in `pub impl
-                    // { fn foo(); }` is public, but private in `impl { fn
-                    // foo(); }`).
-                    let method_vis = impl_item.vis.inherit_from(parent_visibility);
+                    // Trait methods are always public.
+                    let public = &hir::Public;
+                    let method_vis = if opt_trait_ref.is_some() { public } else { &impl_item.vis };
 
                     convert_method(ccx, ImplContainer(def_id),
                                    impl_item.name, impl_item.id, method_vis,
@@ -839,7 +829,7 @@ fn convert_item(ccx: &CrateCtxt, it: &hir::Item) {
                                              container,
                                              trait_item.name,
                                              trait_item.id,
-                                             hir::Public,
+                                             &hir::Public,
                                              hir::Defaultness::Default,
                                              ty,
                                              default.is_some())
@@ -857,7 +847,7 @@ fn convert_item(ccx: &CrateCtxt, it: &hir::Item) {
                                             container,
                                             trait_item.name,
                                             trait_item.id,
-                                            hir::Public,
+                                            &hir::Public,
                                             hir::Defaultness::Default,
                                             typ);
                 }
@@ -870,7 +860,7 @@ fn convert_item(ccx: &CrateCtxt, it: &hir::Item) {
                                    container,
                                    trait_item.name,
                                    trait_item.id,
-                                   hir::Inherited,
+                                   &hir::Inherited,
                                    sig,
                                    hir::Defaultness::Default,
                                    tcx.mk_self_type(),
@@ -987,6 +977,7 @@ fn convert_struct_variant<'tcx>(tcx: &TyCtxt<'tcx>,
                                 disr_val: ty::Disr,
                                 def: &hir::VariantData) -> ty::VariantDefData<'tcx, 'tcx> {
     let mut seen_fields: FnvHashMap<ast::Name, Span> = FnvHashMap();
+    let node_id = tcx.map.as_local_node_id(did).unwrap();
     let fields = def.fields().iter().map(|f| {
         let fid = tcx.map.local_def_id(f.id);
         let dup_span = seen_fields.get(&f.name).cloned();
@@ -1000,7 +991,7 @@ fn convert_struct_variant<'tcx>(tcx: &TyCtxt<'tcx>,
             seen_fields.insert(f.name, f.span);
         }
 
-        ty::FieldDefData::new(fid, f.name, f.vis)
+        ty::FieldDefData::new(fid, f.name, ty::Visibility::from_hir(&f.vis, node_id, tcx))
     }).collect();
     ty::VariantDefData {
         did: did,
diff --git a/src/librustdoc/clean/inline.rs b/src/librustdoc/clean/inline.rs
index 8c65eb8dbd3..85097549826 100644
--- a/src/librustdoc/clean/inline.rs
+++ b/src/librustdoc/clean/inline.rs
@@ -361,7 +361,7 @@ pub fn build_impl(cx: &DocContext,
                 })
             }
             ty::MethodTraitItem(method) => {
-                if method.vis != hir::Public && associated_trait.is_none() {
+                if method.vis != ty::Visibility::Public && associated_trait.is_none() {
                     return None
                 }
                 let mut item = method.clean(cx);
@@ -471,7 +471,7 @@ fn build_module(cx: &DocContext, tcx: &TyCtxt,
                 cstore::DlDef(Def::ForeignMod(did)) => {
                     fill_in(cx, tcx, did, items);
                 }
-                cstore::DlDef(def) if item.vis == hir::Public => {
+                cstore::DlDef(def) if item.vis == ty::Visibility::Public => {
                     if !visited.insert(def) { continue }
                     if let Some(i) = try_inline_def(cx, tcx, def) {
                         items.extend(i)
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index 4895022cfac..673aa17ecd1 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -1754,7 +1754,7 @@ impl Clean<Item> for hir::StructField {
             name: Some(self.name).clean(cx),
             attrs: self.attrs.clean(cx),
             source: self.span.clean(cx),
-            visibility: Some(self.vis),
+            visibility: self.vis.clean(cx),
             stability: get_stability(cx, cx.map.local_def_id(self.id)),
             deprecation: get_deprecation(cx, cx.map.local_def_id(self.id)),
             def_id: cx.map.local_def_id(self.id),
@@ -1771,7 +1771,7 @@ impl<'tcx> Clean<Item> for ty::FieldDefData<'tcx, 'static> {
             name: Some(self.name).clean(cx),
             attrs: attr_map.get(&self.did).unwrap_or(&Vec::new()).clean(cx),
             source: Span::empty(),
-            visibility: Some(self.vis),
+            visibility: self.vis.clean(cx),
             stability: get_stability(cx, self.did),
             deprecation: get_deprecation(cx, self.did),
             def_id: self.did,
@@ -1784,7 +1784,13 @@ pub type Visibility = hir::Visibility;
 
 impl Clean<Option<Visibility>> for hir::Visibility {
     fn clean(&self, _: &DocContext) -> Option<Visibility> {
-        Some(*self)
+        Some(self.clone())
+    }
+}
+
+impl Clean<Option<Visibility>> for ty::Visibility {
+    fn clean(&self, _: &DocContext) -> Option<Visibility> {
+        Some(if *self == ty::Visibility::Public { hir::Public } else { hir::Inherited })
     }
 }
 
@@ -1902,7 +1908,7 @@ impl<'tcx> Clean<Item> for ty::VariantDefData<'tcx, 'static> {
                             source: Span::empty(),
                             name: Some(field.name.clean(cx)),
                             attrs: cx.tcx().get_attrs(field.did).clean(cx),
-                            visibility: Some(field.vis),
+                            visibility: field.vis.clean(cx),
                             def_id: field.did,
                             stability: get_stability(cx, field.did),
                             deprecation: get_deprecation(cx, field.did),
diff --git a/src/librustdoc/html/format.rs b/src/librustdoc/html/format.rs
index a43711a3273..ce20ad05acb 100644
--- a/src/librustdoc/html/format.rs
+++ b/src/librustdoc/html/format.rs
@@ -31,7 +31,7 @@ use html::render::{cache, CURRENT_LOCATION_KEY};
 /// Helper to render an optional visibility with a space after it (if the
 /// visibility is preset)
 #[derive(Copy, Clone)]
-pub struct VisSpace(pub Option<hir::Visibility>);
+pub struct VisSpace<'a>(pub &'a Option<hir::Visibility>);
 /// Similarly to VisSpace, this structure is used to render a function style with a
 /// space after it.
 #[derive(Copy, Clone)]
@@ -56,9 +56,9 @@ pub struct TyParamBounds<'a>(pub &'a [clean::TyParamBound]);
 pub struct CommaSep<'a, T: 'a>(pub &'a [T]);
 pub struct AbiSpace(pub Abi);
 
-impl VisSpace {
-    pub fn get(&self) -> Option<hir::Visibility> {
-        let VisSpace(v) = *self; v
+impl<'a> VisSpace<'a> {
+    pub fn get(self) -> &'a Option<hir::Visibility> {
+        let VisSpace(v) = self; v
     }
 }
 
@@ -636,9 +636,9 @@ impl<'a> fmt::Display for Method<'a> {
     }
 }
 
-impl fmt::Display for VisSpace {
+impl<'a> fmt::Display for VisSpace<'a> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        match self.get() {
+        match *self.get() {
             Some(hir::Public) => write!(f, "pub "),
             Some(hir::Inherited) | None => Ok(())
         }
diff --git a/src/librustdoc/html/render.rs b/src/librustdoc/html/render.rs
index 3352e74c4c3..c5850089578 100644
--- a/src/librustdoc/html/render.rs
+++ b/src/librustdoc/html/render.rs
@@ -1714,13 +1714,13 @@ fn item_module(w: &mut fmt::Formatter, cx: &Context,
                 match *src {
                     Some(ref src) => {
                         write!(w, "<tr><td><code>{}extern crate {} as {};",
-                               VisSpace(myitem.visibility),
+                               VisSpace(&myitem.visibility),
                                src,
                                name)?
                     }
                     None => {
                         write!(w, "<tr><td><code>{}extern crate {};",
-                               VisSpace(myitem.visibility), name)?
+                               VisSpace(&myitem.visibility), name)?
                     }
                 }
                 write!(w, "</code></td></tr>")?;
@@ -1728,7 +1728,7 @@ fn item_module(w: &mut fmt::Formatter, cx: &Context,
 
             clean::ImportItem(ref import) => {
                 write!(w, "<tr><td><code>{}{}</code></td></tr>",
-                       VisSpace(myitem.visibility), *import)?;
+                       VisSpace(&myitem.visibility), *import)?;
             }
 
             _ => {
@@ -1831,7 +1831,7 @@ fn item_constant(w: &mut fmt::Formatter, cx: &Context, it: &clean::Item,
                  c: &clean::Constant) -> fmt::Result {
     write!(w, "<pre class='rust const'>{vis}const \
                {name}: {typ}{init}</pre>",
-           vis = VisSpace(it.visibility),
+           vis = VisSpace(&it.visibility),
            name = it.name.as_ref().unwrap(),
            typ = c.type_,
            init = Initializer(&c.expr))?;
@@ -1842,7 +1842,7 @@ fn item_static(w: &mut fmt::Formatter, cx: &Context, it: &clean::Item,
                s: &clean::Static) -> fmt::Result {
     write!(w, "<pre class='rust static'>{vis}static {mutability}\
                {name}: {typ}{init}</pre>",
-           vis = VisSpace(it.visibility),
+           vis = VisSpace(&it.visibility),
            mutability = MutableSpace(s.mutability),
            name = it.name.as_ref().unwrap(),
            typ = s.type_,
@@ -1859,7 +1859,7 @@ fn item_function(w: &mut fmt::Formatter, cx: &Context, it: &clean::Item,
     };
     write!(w, "<pre class='rust fn'>{vis}{constness}{unsafety}{abi}fn \
                {name}{generics}{decl}{where_clause}</pre>",
-           vis = VisSpace(it.visibility),
+           vis = VisSpace(&it.visibility),
            constness = ConstnessSpace(vis_constness),
            unsafety = UnsafetySpace(f.unsafety),
            abi = AbiSpace(f.abi),
@@ -1887,7 +1887,7 @@ fn item_trait(w: &mut fmt::Formatter, cx: &Context, it: &clean::Item,
 
     // Output the trait definition
     write!(w, "<pre class='rust trait'>{}{}trait {}{}{}{} ",
-           VisSpace(it.visibility),
+           VisSpace(&it.visibility),
            UnsafetySpace(t.unsafety),
            it.name.as_ref().unwrap(),
            t.generics,
@@ -2214,7 +2214,7 @@ fn item_enum(w: &mut fmt::Formatter, cx: &Context, it: &clean::Item,
     write!(w, "<pre class='rust enum'>")?;
     render_attributes(w, it)?;
     write!(w, "{}enum {}{}{}",
-           VisSpace(it.visibility),
+           VisSpace(&it.visibility),
            it.name.as_ref().unwrap(),
            e.generics,
            WhereClause(&e.generics))?;
@@ -2326,7 +2326,7 @@ fn render_struct(w: &mut fmt::Formatter, it: &clean::Item,
                  tab: &str,
                  structhead: bool) -> fmt::Result {
     write!(w, "{}{}{}",
-           VisSpace(it.visibility),
+           VisSpace(&it.visibility),
            if structhead {"struct "} else {""},
            it.name.as_ref().unwrap())?;
     if let Some(g) = g {
@@ -2338,7 +2338,7 @@ fn render_struct(w: &mut fmt::Formatter, it: &clean::Item,
             for field in fields {
                 if let clean::StructFieldItem(ref ty) = field.inner {
                     write!(w, "    {}{}: {},\n{}",
-                           VisSpace(field.visibility),
+                           VisSpace(&field.visibility),
                            field.name.as_ref().unwrap(),
                            *ty,
                            tab)?;
@@ -2361,7 +2361,7 @@ fn render_struct(w: &mut fmt::Formatter, it: &clean::Item,
                         write!(w, "_")?
                     }
                     clean::StructFieldItem(ref ty) => {
-                        write!(w, "{}{}", VisSpace(field.visibility), *ty)?
+                        write!(w, "{}{}", VisSpace(&field.visibility), *ty)?
                     }
                     _ => unreachable!()
                 }
diff --git a/src/librustdoc/visit_ast.rs b/src/librustdoc/visit_ast.rs
index 45c7969ef7c..5c36c38abc5 100644
--- a/src/librustdoc/visit_ast.rs
+++ b/src/librustdoc/visit_ast.rs
@@ -101,7 +101,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
             id: item.id,
             struct_type: struct_type,
             name: name,
-            vis: item.vis,
+            vis: item.vis.clone(),
             stab: self.stability(item.id),
             depr: self.deprecation(item.id),
             attrs: item.attrs.clone(),
@@ -125,7 +125,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
                 def: v.node.data.clone(),
                 whence: v.span,
             }).collect(),
-            vis: it.vis,
+            vis: it.vis.clone(),
             stab: self.stability(it.id),
             depr: self.deprecation(it.id),
             generics: params.clone(),
@@ -144,7 +144,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
         debug!("Visiting fn");
         Function {
             id: item.id,
-            vis: item.vis,
+            vis: item.vis.clone(),
             stab: self.stability(item.id),
             depr: self.deprecation(item.id),
             attrs: item.attrs.clone(),
@@ -166,7 +166,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
         om.where_outer = span;
         om.where_inner = m.inner;
         om.attrs = attrs;
-        om.vis = vis;
+        om.vis = vis.clone();
         om.stab = self.stability(id);
         om.depr = self.deprecation(id);
         om.id = id;
@@ -299,7 +299,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
                 om.extern_crates.push(ExternCrate {
                     name: name,
                     path: p.map(|x|x.to_string()),
-                    vis: item.vis,
+                    vis: item.vis.clone(),
                     attrs: item.attrs.clone(),
                     whence: item.span,
                 })
@@ -324,7 +324,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
                 };
                 om.imports.push(Import {
                     id: item.id,
-                    vis: item.vis,
+                    vis: item.vis.clone(),
                     attrs: item.attrs.clone(),
                     node: node,
                     whence: item.span,
@@ -333,7 +333,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
             hir::ItemMod(ref m) => {
                 om.mods.push(self.visit_mod_contents(item.span,
                                                      item.attrs.clone(),
-                                                     item.vis,
+                                                     item.vis.clone(),
                                                      item.id,
                                                      m,
                                                      Some(name)));
@@ -353,7 +353,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
                     id: item.id,
                     attrs: item.attrs.clone(),
                     whence: item.span,
-                    vis: item.vis,
+                    vis: item.vis.clone(),
                     stab: self.stability(item.id),
                     depr: self.deprecation(item.id),
                 };
@@ -368,7 +368,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
                     name: name,
                     attrs: item.attrs.clone(),
                     whence: item.span,
-                    vis: item.vis,
+                    vis: item.vis.clone(),
                     stab: self.stability(item.id),
                     depr: self.deprecation(item.id),
                 };
@@ -382,7 +382,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
                     name: name,
                     attrs: item.attrs.clone(),
                     whence: item.span,
-                    vis: item.vis,
+                    vis: item.vis.clone(),
                     stab: self.stability(item.id),
                     depr: self.deprecation(item.id),
                 };
@@ -398,7 +398,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
                     id: item.id,
                     attrs: item.attrs.clone(),
                     whence: item.span,
-                    vis: item.vis,
+                    vis: item.vis.clone(),
                     stab: self.stability(item.id),
                     depr: self.deprecation(item.id),
                 };
@@ -415,7 +415,7 @@ impl<'a, 'tcx> RustdocVisitor<'a, 'tcx> {
                     attrs: item.attrs.clone(),
                     id: item.id,
                     whence: item.span,
-                    vis: item.vis,
+                    vis: item.vis.clone(),
                     stab: self.stability(item.id),
                     depr: self.deprecation(item.id),
                 };
diff --git a/src/test/compile-fail-fulldeps/macro-crate-doesnt-resolve.rs b/src/test/compile-fail-fulldeps/macro-crate-doesnt-resolve.rs
index 8ac03606720..1fbde00a3df 100644
--- a/src/test/compile-fail-fulldeps/macro-crate-doesnt-resolve.rs
+++ b/src/test/compile-fail-fulldeps/macro-crate-doesnt-resolve.rs
@@ -16,5 +16,4 @@ extern crate macro_crate_test;
 fn main() {
     macro_crate_test::foo();
     //~^ ERROR failed to resolve. Use of undeclared type or module `macro_crate_test`
-    //~^^ ERROR unresolved name `macro_crate_test::foo`
 }
diff --git a/src/test/compile-fail/bad-module.rs b/src/test/compile-fail/bad-module.rs
index edc118cb039..0cd3a885318 100644
--- a/src/test/compile-fail/bad-module.rs
+++ b/src/test/compile-fail/bad-module.rs
@@ -8,6 +8,6 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern: unresolved name
+// error-pattern: failed to resolve. Use of undeclared type or module `thing`
 
 fn main() { let foo = thing::len(Vec::new()); }
diff --git a/src/test/compile-fail/bad-type-env-capture.rs b/src/test/compile-fail/bad-type-env-capture.rs
index a3139905244..c1547dd82b3 100644
--- a/src/test/compile-fail/bad-type-env-capture.rs
+++ b/src/test/compile-fail/bad-type-env-capture.rs
@@ -10,6 +10,5 @@
 
 fn foo<T>() {
     fn bar(b: T) { } //~ ERROR can't use type parameters from outer
-    //~^ ERROR type name `T` is undefined or not in scope
 }
 fn main() { }
diff --git a/src/test/compile-fail/export-fully-qualified.rs b/src/test/compile-fail/export-fully-qualified.rs
index 2ba2ef1c05a..166ef7ab87f 100644
--- a/src/test/compile-fail/export-fully-qualified.rs
+++ b/src/test/compile-fail/export-fully-qualified.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern: unresolved name
+// error-pattern: failed to resolve. Use of undeclared type or module `foo`
 
 // In this test baz isn't resolved when called as foo.baz even though
 // it's called from inside foo. This is somewhat surprising and may
diff --git a/src/test/compile-fail/export2.rs b/src/test/compile-fail/export2.rs
index 6104c02c90a..f7b1400aa45 100644
--- a/src/test/compile-fail/export2.rs
+++ b/src/test/compile-fail/export2.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern: unresolved name
+// error-pattern: failed to resolve. Use of undeclared type or module `bar`
 
 mod foo {
     pub fn x() { bar::x(); }
diff --git a/src/test/compile-fail/inner-static-type-parameter.rs b/src/test/compile-fail/inner-static-type-parameter.rs
index 6fcda66486b..a6a33198458 100644
--- a/src/test/compile-fail/inner-static-type-parameter.rs
+++ b/src/test/compile-fail/inner-static-type-parameter.rs
@@ -15,7 +15,6 @@ enum Bar<T> { What } //~ ERROR parameter `T` is never used
 fn foo<T>() {
     static a: Bar<T> = Bar::What;
     //~^ ERROR cannot use an outer type parameter in this context
-    //~| ERROR type name `T` is undefined or not in scope
 }
 
 fn main() {
diff --git a/src/test/compile-fail/issue-12796.rs b/src/test/compile-fail/issue-12796.rs
index 33fbdce4ee2..0c3c82a99f2 100644
--- a/src/test/compile-fail/issue-12796.rs
+++ b/src/test/compile-fail/issue-12796.rs
@@ -12,7 +12,6 @@ trait Trait {
     fn outer(&self) {
         fn inner(_: &Self) {
             //~^ ERROR can't use type parameters from outer function
-            //~^^ ERROR use of `Self` outside of an impl or trait
         }
     }
 }
diff --git a/src/test/compile-fail/issue-30079.rs b/src/test/compile-fail/issue-30079.rs
new file mode 100644
index 00000000000..a8db01b82da
--- /dev/null
+++ b/src/test/compile-fail/issue-30079.rs
@@ -0,0 +1,55 @@
+// 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.
+
+#![feature(rustc_attrs)]
+#![allow(unused)]
+
+struct SemiPriv;
+
+mod m1 {
+    struct Priv;
+    impl ::SemiPriv {
+        pub fn f(_: Priv) {} //~ WARN private type in public interface
+        //~^ WARNING hard error
+    }
+
+    impl Priv {
+        pub fn f(_: Priv) {} // ok
+    }
+}
+
+mod m2 {
+    struct Priv;
+    impl ::std::ops::Deref for ::SemiPriv {
+        type Target = Priv; //~ WARN private type in public interface
+        //~^ WARNING hard error
+        fn deref(&self) -> &Self::Target { unimplemented!() }
+    }
+
+    impl ::std::ops::Deref for Priv {
+        type Target = Priv; // ok
+        fn deref(&self) -> &Self::Target { unimplemented!() }
+    }
+}
+
+trait SemiPrivTrait {
+    type Assoc;
+}
+
+mod m3 {
+    struct Priv;
+    impl ::SemiPrivTrait for () {
+        type Assoc = Priv; //~ WARN private type in public interface
+        //~^ WARNING hard error
+    }
+}
+
+#[rustc_error]
+fn main() {} //~ ERROR compilation successful
diff --git a/src/test/compile-fail/issue-3021-b.rs b/src/test/compile-fail/issue-3021-b.rs
index 5c539cd739c..2b0a24cfdb3 100644
--- a/src/test/compile-fail/issue-3021-b.rs
+++ b/src/test/compile-fail/issue-3021-b.rs
@@ -17,7 +17,6 @@ fn siphash(k0 : u64) {
     impl siphash {
         pub fn reset(&mut self) {
            self.v0 = k0 ^ 0x736f6d6570736575; //~ ERROR can't capture dynamic environment
-           //~^ ERROR unresolved name `k0`
         }
     }
 }
diff --git a/src/test/compile-fail/issue-3021-c.rs b/src/test/compile-fail/issue-3021-c.rs
index 03473bd44cc..635006a3b4d 100644
--- a/src/test/compile-fail/issue-3021-c.rs
+++ b/src/test/compile-fail/issue-3021-c.rs
@@ -13,8 +13,6 @@ fn siphash<T>() {
     trait t {
         fn g(&self, x: T) -> T;  //~ ERROR can't use type parameters from outer function; try using
         //~^ ERROR can't use type parameters from outer function; try using
-        //~^^ ERROR type name `T` is undefined or not in scope
-        //~^^^ ERROR type name `T` is undefined or not in scope
     }
 }
 
diff --git a/src/test/compile-fail/issue-3021-d.rs b/src/test/compile-fail/issue-3021-d.rs
index ecc8ac34ecf..c23e12e713a 100644
--- a/src/test/compile-fail/issue-3021-d.rs
+++ b/src/test/compile-fail/issue-3021-d.rs
@@ -29,9 +29,7 @@ fn siphash(k0 : u64, k1 : u64) {
    impl siphash for SipState {
         fn reset(&self) {
             self.v0 = k0 ^ 0x736f6d6570736575; //~ ERROR can't capture dynamic environment
-            //~^ ERROR unresolved name `k0`
             self.v1 = k1 ^ 0x646f72616e646f6d; //~ ERROR can't capture dynamic environment
-            //~^ ERROR unresolved name `k1`
         }
         fn result(&self) -> u64 { return mk_result(self); }
     }
diff --git a/src/test/compile-fail/issue-3021.rs b/src/test/compile-fail/issue-3021.rs
index 7cf772b0728..f93a333d2ae 100644
--- a/src/test/compile-fail/issue-3021.rs
+++ b/src/test/compile-fail/issue-3021.rs
@@ -20,7 +20,6 @@ fn siphash(k0 : u64) {
     impl SipHash for SipState {
         fn reset(&self) {
            self.v0 = k0 ^ 0x736f6d6570736575; //~ ERROR can't capture dynamic environment
-           //~^ ERROR unresolved name `k0`
         }
     }
     panic!();
diff --git a/src/test/compile-fail/issue-3214.rs b/src/test/compile-fail/issue-3214.rs
index 4f955df8205..d3b932fbc53 100644
--- a/src/test/compile-fail/issue-3214.rs
+++ b/src/test/compile-fail/issue-3214.rs
@@ -11,7 +11,6 @@
 fn foo<T>() {
     struct foo {
         x: T, //~ ERROR can't use type parameters from outer function;
-        //~^ ERROR type name `T` is undefined or not in scope
     }
 
     impl<T> Drop for foo<T> {
diff --git a/src/test/compile-fail/issue-3521-2.rs b/src/test/compile-fail/issue-3521-2.rs
index ad5bc4e445c..6cd2c02c417 100644
--- a/src/test/compile-fail/issue-3521-2.rs
+++ b/src/test/compile-fail/issue-3521-2.rs
@@ -13,7 +13,6 @@ fn main() {
 
     static y: isize = foo + 1;
     //~^ ERROR attempt to use a non-constant value in a constant
-    //~| ERROR unresolved name `foo`
 
     println!("{}", y);
 }
diff --git a/src/test/compile-fail/issue-3521.rs b/src/test/compile-fail/issue-3521.rs
index 34cd8cae2de..52375ef281a 100644
--- a/src/test/compile-fail/issue-3521.rs
+++ b/src/test/compile-fail/issue-3521.rs
@@ -15,8 +15,7 @@ fn main() {
     enum Stuff {
         Bar = foo
         //~^ ERROR attempt to use a non-constant value in a constant
-        //~| ERROR unresolved name `foo`
-        //~^^^ ERROR constant evaluation error: non-constant path in constant expression
+        //~^^ ERROR constant evaluation error: non-constant path in constant expression
     }
 
     println!("{}", Stuff::Bar);
diff --git a/src/test/compile-fail/issue-3668-2.rs b/src/test/compile-fail/issue-3668-2.rs
index a09c8090de0..16fb2f68133 100644
--- a/src/test/compile-fail/issue-3668-2.rs
+++ b/src/test/compile-fail/issue-3668-2.rs
@@ -11,7 +11,6 @@
 fn f(x:isize) {
     static child: isize = x + 1;
     //~^ ERROR attempt to use a non-constant value in a constant
-    //~| ERROR unresolved name `x`
 }
 
 fn main() {}
diff --git a/src/test/compile-fail/issue-3668.rs b/src/test/compile-fail/issue-3668.rs
index 9b7476244f0..9c31dc1e38e 100644
--- a/src/test/compile-fail/issue-3668.rs
+++ b/src/test/compile-fail/issue-3668.rs
@@ -17,7 +17,6 @@ impl PTrait for P {
    fn getChildOption(&self) -> Option<Box<P>> {
        static childVal: Box<P> = self.child.get();
        //~^ ERROR attempt to use a non-constant value in a constant
-       //~| ERROR unresolved name `self`
        panic!();
    }
 }
diff --git a/src/test/compile-fail/issue-5997-enum.rs b/src/test/compile-fail/issue-5997-enum.rs
index 20d239c6ae0..463fdaa1069 100644
--- a/src/test/compile-fail/issue-5997-enum.rs
+++ b/src/test/compile-fail/issue-5997-enum.rs
@@ -11,7 +11,6 @@
 fn f<Z>() -> bool {
     enum E { V(Z) }
     //~^ ERROR can't use type parameters from outer function
-    //~^^ ERROR type name `Z` is undefined or not in scope
     true
 }
 
diff --git a/src/test/compile-fail/issue-5997-struct.rs b/src/test/compile-fail/issue-5997-struct.rs
index 40be2f04cb4..e9cfafc98df 100644
--- a/src/test/compile-fail/issue-5997-struct.rs
+++ b/src/test/compile-fail/issue-5997-struct.rs
@@ -9,8 +9,7 @@
 // except according to those terms.
 
 fn f<T>() -> bool {
-    struct S(T); //~ ERROR type name `T` is undefined or not in scope
-    //~^ ERROR can't use type parameters from outer function; try using
+    struct S(T); //~ ERROR can't use type parameters from outer function; try using
 
     true
 }
diff --git a/src/test/compile-fail/issue-6642.rs b/src/test/compile-fail/issue-6642.rs
index 2c1809d4d48..1fe10ba7a27 100644
--- a/src/test/compile-fail/issue-6642.rs
+++ b/src/test/compile-fail/issue-6642.rs
@@ -13,7 +13,6 @@ impl A {
     fn m(&self) {
         fn x() {
             self.m() //~ ERROR can't capture dynamic environment in a fn item
-            //~^ ERROR unresolved name `self`
         }
     }
 }
diff --git a/src/test/compile-fail/macro-inner-attributes.rs b/src/test/compile-fail/macro-inner-attributes.rs
index abf0ed420e7..1111b21d455 100644
--- a/src/test/compile-fail/macro-inner-attributes.rs
+++ b/src/test/compile-fail/macro-inner-attributes.rs
@@ -26,6 +26,5 @@ test!(b,
 fn main() {
     a::bar();
     //~^ ERROR failed to resolve. Use of undeclared type or module `a`
-    //~^^ ERROR unresolved name `a::bar`
     b::bar();
 }
diff --git a/src/test/compile-fail/no-link.rs b/src/test/compile-fail/no-link.rs
index a9c2b6a942c..957b6cda553 100644
--- a/src/test/compile-fail/no-link.rs
+++ b/src/test/compile-fail/no-link.rs
@@ -14,6 +14,5 @@ extern crate libc;
 fn main() {
     unsafe {
         libc::abs(0);  //~ ERROR Use of undeclared type or module `libc`
-                      //~^ ERROR unresolved name `libc::abs`
     }
 }
diff --git a/src/test/compile-fail/resolve-type-param-in-item-in-trait.rs b/src/test/compile-fail/resolve-type-param-in-item-in-trait.rs
index 92134ecde91..30ff1ed0e26 100644
--- a/src/test/compile-fail/resolve-type-param-in-item-in-trait.rs
+++ b/src/test/compile-fail/resolve-type-param-in-item-in-trait.rs
@@ -18,7 +18,6 @@ trait TraitA<A> {
             //~^ ERROR parameter `B` is never used
             Variance(A)
                 //~^ ERROR can't use type parameters from outer function
-                //~^^ ERROR type name `A` is undefined or not in scope
         }
     }
 }
@@ -27,8 +26,7 @@ trait TraitB<A> {
     fn outer(self) {
         struct Foo<B>(A);
                 //~^ ERROR can't use type parameters from outer function
-                //~^^ ERROR type name `A` is undefined or not in scope
-                //~^^^ ERROR parameter `B` is never used
+                //~^^ ERROR parameter `B` is never used
     }
 }
 
@@ -36,8 +34,7 @@ trait TraitC<A> {
     fn outer(self) {
         struct Foo<B> { a: A }
                 //~^ ERROR can't use type parameters from outer function
-                //~^^ ERROR type name `A` is undefined or not in scope
-                //~^^^ ERROR parameter `B` is never used
+                //~^^ ERROR parameter `B` is never used
     }
 }
 
@@ -45,7 +42,6 @@ trait TraitD<A> {
     fn outer(self) {
         fn foo<B>(a: A) { }
                 //~^ ERROR can't use type parameters from outer function
-                //~^^ ERROR type name `A` is undefined or not in scope
     }
 }