Start implementation of RFC 1216 (make ! a type)

Add `TyKind::Empty` and fix resulting build errors.

39 files changed, 69 insertions, 17 deletions

diff --git a/src/librustc/hir/fold.rs b/src/librustc/hir/fold.rs
index dd79e14f077..822a603fbb8 100644
--- a/src/librustc/hir/fold.rs
+++ b/src/librustc/hir/fold.rs
@@ -353,6 +353,7 @@ pub fn noop_fold_ty<T: Folder>(t: P<Ty>, fld: &mut T) -> P<Ty> {
                         }
                     }))
                 }
+                TyEmpty => node,
                 TyTup(tys) => TyTup(tys.move_map(|ty| fld.fold_ty(ty))),
                 TyPath(qself, path) => {
                     let qself = qself.map(|QSelf { ty, position }| {
diff --git a/src/librustc/hir/intravisit.rs b/src/librustc/hir/intravisit.rs
index 1162c290f9c..0c24d1315f1 100644
--- a/src/librustc/hir/intravisit.rs
+++ b/src/librustc/hir/intravisit.rs
@@ -403,6 +403,7 @@ pub fn walk_ty<'v, V: Visitor<'v>>(visitor: &mut V, typ: &'v Ty) {
             walk_list!(visitor, visit_lifetime, opt_lifetime);
             visitor.visit_ty(&mutable_type.ty)
         }
+        TyEmpty => {},
         TyTup(ref tuple_element_types) => {
             walk_list!(visitor, visit_ty, tuple_element_types);
         }
diff --git a/src/librustc/hir/lowering.rs b/src/librustc/hir/lowering.rs
index eb98ed77da7..3170dd1884a 100644
--- a/src/librustc/hir/lowering.rs
+++ b/src/librustc/hir/lowering.rs
@@ -270,6 +270,7 @@ impl<'a> LoweringContext<'a> {
                         decl: self.lower_fn_decl(&f.decl),
                     }))
                 }
+                Empty => hir::TyEmpty,
                 Tup(ref tys) => hir::TyTup(tys.iter().map(|ty| self.lower_ty(ty)).collect()),
                 Paren(ref ty) => {
                     return self.lower_ty(ty);
diff --git a/src/librustc/hir/mod.rs b/src/librustc/hir/mod.rs
index 707ef987c2c..366b0100bda 100644
--- a/src/librustc/hir/mod.rs
+++ b/src/librustc/hir/mod.rs
@@ -1112,6 +1112,7 @@ pub struct BareFnTy {
 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 /// The different kinds of types recognized by the compiler
 pub enum Ty_ {
+    /// A variable length array (`[T]`)
     TyVec(P<Ty>),
     /// A fixed length array (`[T; n]`)
     TyFixedLengthVec(P<Ty>, P<Expr>),
@@ -1121,6 +1122,8 @@ pub enum Ty_ {
     TyRptr(Option<Lifetime>, MutTy),
     /// A bare function (e.g. `fn(usize) -> bool`)
     TyBareFn(P<BareFnTy>),
+    /// The empty type (`!`)
+    TyEmpty,
     /// A tuple (`(A, B, C, D,...)`)
     TyTup(HirVec<P<Ty>>),
     /// A path (`module::module::...::Type`), optionally
diff --git a/src/librustc/hir/print.rs b/src/librustc/hir/print.rs
index 6dedae5ccd7..71694bc4e7d 100644
--- a/src/librustc/hir/print.rs
+++ b/src/librustc/hir/print.rs
@@ -504,6 +504,9 @@ impl<'a> State<'a> {
                 self.print_opt_lifetime(lifetime)?;
                 self.print_mt(mt)?;
             }
+            hir::TyEmpty => {
+                word(&mut self.s, "!")?;
+            },
             hir::TyTup(ref elts) => {
                 self.popen()?;
                 self.commasep(Inconsistent, &elts[..], |s, ty| s.print_type(&ty))?;
diff --git a/src/librustc/infer/freshen.rs b/src/librustc/infer/freshen.rs
index 1fb4e59e131..7e7953aa258 100644
--- a/src/librustc/infer/freshen.rs
+++ b/src/librustc/infer/freshen.rs
@@ -168,6 +168,7 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
             ty::TyTrait(..) |
             ty::TyStruct(..) |
             ty::TyClosure(..) |
+            ty::TyEmpty |
             ty::TyTuple(..) |
             ty::TyProjection(..) |
             ty::TyParam(..) |
diff --git a/src/librustc/traits/coherence.rs b/src/librustc/traits/coherence.rs
index 37193d45e68..291c7c6426a 100644
--- a/src/librustc/traits/coherence.rs
+++ b/src/librustc/traits/coherence.rs
@@ -253,6 +253,7 @@ fn ty_is_local_constructor(tcx: TyCtxt, ty: Ty, infer_is_local: InferIsLocal)->
         ty::TySlice(..) |
         ty::TyRawPtr(..) |
         ty::TyRef(..) |
+        ty::TyEmpty |
         ty::TyTuple(..) |
         ty::TyParam(..) |
         ty::TyProjection(..) => {
diff --git a/src/librustc/traits/error_reporting.rs b/src/librustc/traits/error_reporting.rs
index 09b5a34fdf3..4ee173fbb1c 100644
--- a/src/librustc/traits/error_reporting.rs
+++ b/src/librustc/traits/error_reporting.rs
@@ -212,6 +212,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                 ty::TyProjection(..) => Some(13),
                 ty::TyParam(..) => Some(14),
                 ty::TyAnon(..) => Some(15),
+                ty::TyEmpty => Some(16),
                 ty::TyInfer(..) | ty::TyError => None
             }
         }
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 2df492e507b..131074443b4 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -1772,7 +1772,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             ty::TyUint(_) | ty::TyInt(_) | ty::TyBool | ty::TyFloat(_) |
             ty::TyFnDef(..) | ty::TyFnPtr(_) | ty::TyRawPtr(..) |
             ty::TyChar | ty::TyBox(_) | ty::TyRef(..) |
-            ty::TyArray(..) | ty::TyClosure(..) |
+            ty::TyArray(..) | ty::TyClosure(..) | ty::TyEmpty |
             ty::TyError => {
                 // safe for everything
                 Where(ty::Binder(Vec::new()))
@@ -1820,7 +1820,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             ty::TyInfer(ty::IntVar(_)) | ty::TyInfer(ty::FloatVar(_)) |
             ty::TyUint(_) | ty::TyInt(_) | ty::TyBool | ty::TyFloat(_) |
             ty::TyFnDef(..) | ty::TyFnPtr(_) | ty::TyChar |
-            ty::TyRawPtr(..) | ty::TyError |
+            ty::TyRawPtr(..) | ty::TyError | ty::TyEmpty |
             ty::TyRef(_, ty::TypeAndMut { ty: _, mutbl: hir::MutImmutable }) => {
                 Where(ty::Binder(Vec::new()))
             }
@@ -1886,6 +1886,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             ty::TyError |
             ty::TyInfer(ty::IntVar(_)) |
             ty::TyInfer(ty::FloatVar(_)) |
+            ty::TyEmpty |
             ty::TyChar => {
                 Vec::new()
             }
diff --git a/src/librustc/ty/contents.rs b/src/librustc/ty/contents.rs
index 8da7568c558..67a2624eaad 100644
--- a/src/librustc/ty/contents.rs
+++ b/src/librustc/ty/contents.rs
@@ -185,7 +185,7 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
 
                 // Scalar and unique types are sendable, and durable
                 ty::TyInfer(ty::FreshIntTy(_)) | ty::TyInfer(ty::FreshFloatTy(_)) |
-                ty::TyBool | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
+                ty::TyBool | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) | ty::TyEmpty |
                 ty::TyFnDef(..) | ty::TyFnPtr(_) | ty::TyChar => {
                     TC::None
                 }
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 13401e91265..6babd124665 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -190,6 +190,7 @@ pub struct CommonTypes<'tcx> {
     pub u64: Ty<'tcx>,
     pub f32: Ty<'tcx>,
     pub f64: Ty<'tcx>,
+    pub empty: Ty<'tcx>,
     pub err: Ty<'tcx>,
 }
 
@@ -256,6 +257,7 @@ impl<'tcx> CommonTypes<'tcx> {
         CommonTypes {
             bool: mk(TyBool),
             char: mk(TyChar),
+            empty: mk(TyEmpty),
             err: mk(TyError),
             isize: mk(TyInt(ast::IntTy::Is)),
             i8: mk(TyInt(ast::IntTy::I8)),
@@ -975,7 +977,7 @@ macro_rules! sty_debug_print {
                 for &Interned(t) in tcx.interners.type_.borrow().iter() {
                     let variant = match t.sty {
                         ty::TyBool | ty::TyChar | ty::TyInt(..) | ty::TyUint(..) |
-                            ty::TyFloat(..) | ty::TyStr => continue,
+                            ty::TyFloat(..) | ty::TyStr | ty::TyEmpty => continue,
                         ty::TyError => /* unimportant */ continue,
                         $(ty::$variant(..) => &mut $variant,)*
                     };
@@ -1256,6 +1258,10 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         self.mk_ty(TySlice(ty))
     }
 
+    pub fn mk_empty(&self) -> Ty<'tcx> {
+        self.mk_ty(TyEmpty)
+    }
+
     pub fn mk_tup(self, ts: Vec<Ty<'tcx>>) -> Ty<'tcx> {
         self.mk_ty(TyTuple(self.mk_type_list(ts)))
     }
diff --git a/src/librustc/ty/error.rs b/src/librustc/ty/error.rs
index 66165ec6ff7..e43b23ef3c4 100644
--- a/src/librustc/ty/error.rs
+++ b/src/librustc/ty/error.rs
@@ -214,7 +214,7 @@ impl<'a, 'gcx, 'lcx, 'tcx> ty::TyS<'tcx> {
     fn sort_string(&self, tcx: TyCtxt<'a, 'gcx, 'lcx>) -> String {
         match self.sty {
             ty::TyBool | ty::TyChar | ty::TyInt(_) |
-            ty::TyUint(_) | ty::TyFloat(_) | ty::TyStr => self.to_string(),
+            ty::TyUint(_) | ty::TyFloat(_) | ty::TyStr | ty::TyEmpty => self.to_string(),
             ty::TyTuple(ref tys) if tys.is_empty() => self.to_string(),
 
             ty::TyEnum(def, _) => format!("enum `{}`", tcx.item_path_str(def.did)),
diff --git a/src/librustc/ty/fast_reject.rs b/src/librustc/ty/fast_reject.rs
index e6f2ba8b650..a90c90e99ed 100644
--- a/src/librustc/ty/fast_reject.rs
+++ b/src/librustc/ty/fast_reject.rs
@@ -26,6 +26,7 @@ pub enum SimplifiedType {
     StrSimplifiedType,
     VecSimplifiedType,
     PtrSimplifiedType,
+    EmptySimplifiedType,
     TupleSimplifiedType(usize),
     TraitSimplifiedType(DefId),
     StructSimplifiedType(DefId),
@@ -81,6 +82,7 @@ pub fn simplify_type<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
         ty::TyClosure(def_id, _) => {
             Some(ClosureSimplifiedType(def_id))
         }
+        ty::TyEmpty => Some(EmptySimplifiedType),
         ty::TyTuple(ref tys) => {
             Some(TupleSimplifiedType(tys.len()))
         }
diff --git a/src/librustc/ty/flags.rs b/src/librustc/ty/flags.rs
index 85b7d66a2eb..981b029da9b 100644
--- a/src/librustc/ty/flags.rs
+++ b/src/librustc/ty/flags.rs
@@ -60,6 +60,7 @@ impl FlagComputation {
             &ty::TyInt(_) |
             &ty::TyFloat(_) |
             &ty::TyUint(_) |
+            &ty::TyEmpty |
             &ty::TyStr => {
             }
 
diff --git a/src/librustc/ty/item_path.rs b/src/librustc/ty/item_path.rs
index bfe6303d8a3..a3189370707 100644
--- a/src/librustc/ty/item_path.rs
+++ b/src/librustc/ty/item_path.rs
@@ -349,6 +349,7 @@ pub fn characteristic_def_id_of_type(ty: Ty) -> Option<DefId> {
         ty::TyAnon(..) |
         ty::TyInfer(_) |
         ty::TyError |
+        ty::TyEmpty |
         ty::TyFloat(_) => None,
     }
 }
diff --git a/src/librustc/ty/layout.rs b/src/librustc/ty/layout.rs
index d73e412f55f..79631bff964 100644
--- a/src/librustc/ty/layout.rs
+++ b/src/librustc/ty/layout.rs
@@ -795,6 +795,9 @@ impl<'a, 'gcx, 'tcx> Layout {
             ty::TyFloat(FloatTy::F64) => Scalar { value: F64, non_zero: false },
             ty::TyFnPtr(_) => Scalar { value: Pointer, non_zero: true },
 
+            // The empty type.
+            ty::TyEmpty => Univariant { variant: Struct::new(dl, false), non_zero: false },
+
             // Potentially-fat pointers.
             ty::TyBox(pointee) |
             ty::TyRef(_, ty::TypeAndMut { ty: pointee, .. }) |
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 8e89b3c6087..29bbb8680e2 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -1854,7 +1854,7 @@ impl<'a, 'tcx> AdtDefData<'tcx, 'tcx> {
         let result = match ty.sty {
             TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
             TyBox(..) | TyRawPtr(..) | TyRef(..) | TyFnDef(..) | TyFnPtr(_) |
-            TyArray(..) | TyClosure(..) => {
+            TyArray(..) | TyClosure(..) | TyEmpty => {
                 vec![]
             }
 
diff --git a/src/librustc/ty/outlives.rs b/src/librustc/ty/outlives.rs
index df907c26f71..bc90c18856f 100644
--- a/src/librustc/ty/outlives.rs
+++ b/src/librustc/ty/outlives.rs
@@ -171,6 +171,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
             ty::TyInt(..) |         // OutlivesScalar
             ty::TyUint(..) |        // OutlivesScalar
             ty::TyFloat(..) |       // OutlivesScalar
+            ty::TyEmpty |           // ...
             ty::TyEnum(..) |        // OutlivesNominalType
             ty::TyStruct(..) |      // OutlivesNominalType
             ty::TyBox(..) |         // OutlivesNominalType (ish)
diff --git a/src/librustc/ty/structural_impls.rs b/src/librustc/ty/structural_impls.rs
index 8c10806fda7..a7713bdfcb3 100644
--- a/src/librustc/ty/structural_impls.rs
+++ b/src/librustc/ty/structural_impls.rs
@@ -498,7 +498,7 @@ impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
             ty::TyAnon(did, substs) => ty::TyAnon(did, substs.fold_with(folder)),
             ty::TyBool | ty::TyChar | ty::TyStr | ty::TyInt(_) |
             ty::TyUint(_) | ty::TyFloat(_) | ty::TyError | ty::TyInfer(_) |
-            ty::TyParam(..) => self.sty.clone(),
+            ty::TyParam(..) | ty::TyEmpty => self.sty.clone(),
         };
         folder.tcx().mk_ty(sty)
     }
@@ -527,7 +527,7 @@ impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
             ty::TyAnon(_, ref substs) => substs.visit_with(visitor),
             ty::TyBool | ty::TyChar | ty::TyStr | ty::TyInt(_) |
             ty::TyUint(_) | ty::TyFloat(_) | ty::TyError | ty::TyInfer(_) |
-            ty::TyParam(..) => false,
+            ty::TyParam(..) | ty::TyEmpty => false,
         }
     }
 
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 912cb39face..d693f7f0b83 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -159,6 +159,9 @@ pub enum TypeVariants<'tcx> {
     /// `|a| a`.
     TyClosure(DefId, ClosureSubsts<'tcx>),
 
+    /// The empty type `!`
+    TyEmpty,
+
     /// A tuple type.  For example, `(i32, bool)`.
     TyTuple(&'tcx [Ty<'tcx>]),
 
@@ -1260,6 +1263,7 @@ impl<'a, 'gcx, 'tcx> TyS<'tcx> {
             TyArray(_, _) |
             TySlice(_) |
             TyRawPtr(_) |
+            TyEmpty |
             TyTuple(_) |
             TyParam(_) |
             TyInfer(_) |
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index e7bcfbfd823..eae97a9c49e 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -485,6 +485,7 @@ impl<'a, 'gcx, 'tcx> TypeVisitor<'tcx> for TypeIdHasher<'a, 'gcx, 'tcx> {
                 self.def_id(data.trait_ref.def_id);
                 self.hash(data.item_name.as_str());
             }
+            TyEmpty |
             TyBool |
             TyChar |
             TyStr |
@@ -550,7 +551,7 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
 
         // Fast-path for primitive types
         let result = match self.sty {
-            TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
+            TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) | TyEmpty |
             TyRawPtr(..) | TyFnDef(..) | TyFnPtr(_) | TyRef(_, TypeAndMut {
                 mutbl: hir::MutImmutable, ..
             }) => Some(false),
@@ -596,7 +597,7 @@ impl<'a, 'tcx> ty::TyS<'tcx> {
         let result = match self.sty {
             TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
             TyBox(..) | TyRawPtr(..) | TyRef(..) | TyFnDef(..) | TyFnPtr(_) |
-            TyArray(..) | TyTuple(..) | TyClosure(..) => Some(true),
+            TyArray(..) | TyTuple(..) | TyClosure(..) | TyEmpty => Some(true),
 
             TyStr | TyTrait(..) | TySlice(_) => Some(false),
 
diff --git a/src/librustc/ty/walk.rs b/src/librustc/ty/walk.rs
index ebc2642678b..d46de6f7993 100644
--- a/src/librustc/ty/walk.rs
+++ b/src/librustc/ty/walk.rs
@@ -70,7 +70,7 @@ pub fn walk_shallow<'tcx>(ty: Ty<'tcx>) -> IntoIter<Ty<'tcx>> {
 fn push_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, parent_ty: Ty<'tcx>) {
     match parent_ty.sty {
         ty::TyBool | ty::TyChar | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
-        ty::TyStr | ty::TyInfer(_) | ty::TyParam(_) | ty::TyError => {
+        ty::TyStr | ty::TyInfer(_) | ty::TyParam(_) | ty::TyEmpty | ty::TyError => {
         }
         ty::TyBox(ty) | ty::TyArray(ty, _) | ty::TySlice(ty) => {
             stack.push(ty);
diff --git a/src/librustc/ty/wf.rs b/src/librustc/ty/wf.rs
index f6ddfe60d40..6e138db74c9 100644
--- a/src/librustc/ty/wf.rs
+++ b/src/librustc/ty/wf.rs
@@ -321,6 +321,7 @@ impl<'a, 'gcx, 'tcx> WfPredicates<'a, 'gcx, 'tcx> {
                 ty::TyFloat(..) |
                 ty::TyError |
                 ty::TyStr |
+                ty::TyEmpty |
                 ty::TyParam(_) => {
                     // WfScalar, WfParameter, etc
                 }
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index a17c0106813..fa1d1e0a901 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -14,7 +14,7 @@ use ty::subst::{self, Subst};
 use ty::{BrAnon, BrEnv, BrFresh, BrNamed};
 use ty::{TyBool, TyChar, TyStruct, TyEnum};
 use ty::{TyError, TyStr, TyArray, TySlice, TyFloat, TyFnDef, TyFnPtr};
-use ty::{TyParam, TyRawPtr, TyRef, TyTuple};
+use ty::{TyParam, TyRawPtr, TyRef, TyEmpty, TyTuple};
 use ty::TyClosure;
 use ty::{TyBox, TyTrait, TyInt, TyUint, TyInfer};
 use ty::{self, Ty, TyCtxt, TypeFoldable};
@@ -847,6 +847,7 @@ impl<'tcx> fmt::Display for ty::TypeVariants<'tcx> {
                 }
                 write!(f, "{}", tm)
             }
+            TyEmpty => write!(f, "!"),
             TyTuple(ref tys) => {
                 write!(f, "(")?;
                 let mut tys = tys.iter();
diff --git a/src/librustc_lint/types.rs b/src/librustc_lint/types.rs
index b9861c309db..27da78eceb4 100644
--- a/src/librustc_lint/types.rs
+++ b/src/librustc_lint/types.rs
@@ -523,7 +523,7 @@ impl<'a, 'tcx> ImproperCTypesVisitor<'a, 'tcx> {
 
             // Primitive types with a stable representation.
             ty::TyBool | ty::TyInt(..) | ty::TyUint(..) |
-            ty::TyFloat(..) => FfiSafe,
+            ty::TyFloat(..) | ty::TyEmpty => FfiSafe,
 
             ty::TyBox(..) => {
                 FfiUnsafe("found Rust type Box<_> in foreign module, \
diff --git a/src/librustc_metadata/tydecode.rs b/src/librustc_metadata/tydecode.rs
index 1dcec35adb2..96cf3b7e91c 100644
--- a/src/librustc_metadata/tydecode.rs
+++ b/src/librustc_metadata/tydecode.rs
@@ -311,6 +311,7 @@ impl<'a,'tcx> TyDecoder<'a,'tcx> {
         let tcx = self.tcx;
         match self.next() {
             'b' => return tcx.types.bool,
+            '!' => return tcx.types.empty,
             'i' => { /* eat the s of is */ self.next(); return tcx.types.isize },
             'u' => { /* eat the s of us */ self.next(); return tcx.types.usize },
             'M' => {
diff --git a/src/librustc_metadata/tyencode.rs b/src/librustc_metadata/tyencode.rs
index c2e91eba0d2..26fcb9b1f9f 100644
--- a/src/librustc_metadata/tyencode.rs
+++ b/src/librustc_metadata/tyencode.rs
@@ -74,6 +74,7 @@ pub fn enc_ty<'a, 'tcx>(w: &mut Cursor<Vec<u8>>, cx: &ctxt<'a, 'tcx>, t: Ty<'tcx
     match t.sty {
         ty::TyBool => { write!(w, "b"); }
         ty::TyChar => { write!(w, "c"); }
+        ty::TyEmpty => { write!(w, "!"); }
         ty::TyInt(t) => {
             match t {
                 ast::IntTy::Is => write!(w, "is"),
diff --git a/src/librustc_trans/collector.rs b/src/librustc_trans/collector.rs
index 4a6dbb2bdae..4df96a3b685 100644
--- a/src/librustc_trans/collector.rs
+++ b/src/librustc_trans/collector.rs
@@ -753,6 +753,7 @@ fn find_drop_glue_neighbors<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
         ty::TyRef(..)   |
         ty::TyFnDef(..) |
         ty::TyFnPtr(_)  |
+        ty::TyEmpty     |
         ty::TyTrait(_)  => {
             /* nothing to do */
         }
diff --git a/src/librustc_trans/debuginfo/type_names.rs b/src/librustc_trans/debuginfo/type_names.rs
index bee2667c71f..efd4acfeaa2 100644
--- a/src/librustc_trans/debuginfo/type_names.rs
+++ b/src/librustc_trans/debuginfo/type_names.rs
@@ -40,6 +40,7 @@ pub fn push_debuginfo_type_name<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
         ty::TyBool => output.push_str("bool"),
         ty::TyChar => output.push_str("char"),
         ty::TyStr => output.push_str("str"),
+        ty::TyEmpty => output.push_str("!"),
         ty::TyInt(int_ty) => output.push_str(int_ty.ty_to_string()),
         ty::TyUint(uint_ty) => output.push_str(uint_ty.ty_to_string()),
         ty::TyFloat(float_ty) => output.push_str(float_ty.ty_to_string()),
diff --git a/src/librustc_trans/trans_item.rs b/src/librustc_trans/trans_item.rs
index 187ffe353fd..ef756a7addd 100644
--- a/src/librustc_trans/trans_item.rs
+++ b/src/librustc_trans/trans_item.rs
@@ -412,6 +412,7 @@ pub fn push_unique_type_name<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         ty::TyBool              => output.push_str("bool"),
         ty::TyChar              => output.push_str("char"),
         ty::TyStr               => output.push_str("str"),
+        ty::TyEmpty             => output.push_str("!"),
         ty::TyInt(ast::IntTy::Is)    => output.push_str("isize"),
         ty::TyInt(ast::IntTy::I8)    => output.push_str("i8"),
         ty::TyInt(ast::IntTy::I16)   => output.push_str("i16"),
diff --git a/src/librustc_trans/type_of.rs b/src/librustc_trans/type_of.rs
index cde53f6fa89..6224bb76166 100644
--- a/src/librustc_trans/type_of.rs
+++ b/src/librustc_trans/type_of.rs
@@ -64,6 +64,7 @@ pub fn sizing_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>) -> Typ
         ty::TyInt(t) => Type::int_from_ty(cx, t),
         ty::TyUint(t) => Type::uint_from_ty(cx, t),
         ty::TyFloat(t) => Type::float_from_ty(cx, t),
+        ty::TyEmpty => Type::nil(cx),
 
         ty::TyBox(ty) |
         ty::TyRef(_, ty::TypeAndMut{ty, ..}) |
@@ -249,6 +250,7 @@ pub fn in_memory_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>) ->
       ty::TyInt(t) => Type::int_from_ty(cx, t),
       ty::TyUint(t) => Type::uint_from_ty(cx, t),
       ty::TyFloat(t) => Type::float_from_ty(cx, t),
+      ty::TyEmpty => Type::nil(cx),
       ty::TyEnum(def, ref substs) => {
           // Only create the named struct, but don't fill it in. We
           // fill it in *after* placing it into the type cache. This
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index ad61b5b0b51..1af171eb468 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -1700,6 +1700,9 @@ impl<'o, 'gcx: 'tcx, 'tcx> AstConv<'gcx, 'tcx>+'o {
                 let t = self.ast_ty_to_ty(rscope1, &mt.ty);
                 tcx.mk_ref(tcx.mk_region(r), ty::TypeAndMut {ty: t, mutbl: mt.mutbl})
             }
+            hir::TyEmpty => {
+                tcx.mk_empty()
+            },
             hir::TyTup(ref fields) => {
                 let flds = fields.iter()
                                  .map(|t| self.ast_ty_to_ty(rscope, &t))
diff --git a/src/librustc_typeck/check/dropck.rs b/src/librustc_typeck/check/dropck.rs
index f65e15430da..b526d2dcbed 100644
--- a/src/librustc_typeck/check/dropck.rs
+++ b/src/librustc_typeck/check/dropck.rs
@@ -433,7 +433,7 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'b, 'gcx, 'tcx>(
     // We still need to ensure all referenced data is safe.
     match ty.sty {
         ty::TyBool | ty::TyChar | ty::TyInt(_) | ty::TyUint(_) |
-        ty::TyFloat(_) | ty::TyStr => {
+        ty::TyFloat(_) | ty::TyStr | ty::TyEmpty => {
             // primitive - definitely safe
             Ok(())
         }
diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs
index 13deac57330..2ac74e2e7f8 100644
--- a/src/librustc_typeck/coherence/mod.rs
+++ b/src/librustc_typeck/coherence/mod.rs
@@ -24,7 +24,7 @@ use rustc::ty::{ImplOrTraitItemId, ConstTraitItemId};
 use rustc::ty::{MethodTraitItemId, TypeTraitItemId, ParameterEnvironment};
 use rustc::ty::{Ty, TyBool, TyChar, TyEnum, TyError};
 use rustc::ty::{TyParam, TyRawPtr};
-use rustc::ty::{TyRef, TyStruct, TyTrait, TyTuple};
+use rustc::ty::{TyRef, TyStruct, TyTrait, TyEmpty, TyTuple};
 use rustc::ty::{TyStr, TyArray, TySlice, TyFloat, TyInfer, TyInt};
 use rustc::ty::{TyUint, TyClosure, TyBox, TyFnDef, TyFnPtr};
 use rustc::ty::{TyProjection, TyAnon};
@@ -84,7 +84,7 @@ impl<'a, 'gcx, 'tcx> CoherenceChecker<'a, 'gcx, 'tcx> {
 
             TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
             TyStr | TyArray(..) | TySlice(..) | TyFnDef(..) | TyFnPtr(_) |
-            TyTuple(..) | TyParam(..) | TyError |
+            TyTuple(..) | TyParam(..) | TyError | TyEmpty |
             TyRawPtr(_) | TyRef(_, _) | TyProjection(..) => {
                 None
             }
diff --git a/src/librustc_typeck/variance/constraints.rs b/src/librustc_typeck/variance/constraints.rs
index b9e0b4a10ea..918e0386a68 100644
--- a/src/librustc_typeck/variance/constraints.rs
+++ b/src/librustc_typeck/variance/constraints.rs
@@ -322,7 +322,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
         match ty.sty {
             ty::TyBool |
             ty::TyChar | ty::TyInt(_) | ty::TyUint(_) |
-            ty::TyFloat(_) | ty::TyStr => {
+            ty::TyFloat(_) | ty::TyStr | ty::TyEmpty => {
                 /* leaf type -- noop */
             }
 
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 3f929e6d23a..6ba5eccc5cf 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -1348,6 +1348,7 @@ pub struct BareFnTy {
 /// The different kinds of types recognized by the compiler
 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 pub enum TyKind {
+    /// A variable-length array (`[T]`)
     Vec(P<Ty>),
     /// A fixed length array (`[T; n]`)
     FixedLengthVec(P<Ty>, P<Expr>),
@@ -1357,6 +1358,8 @@ pub enum TyKind {
     Rptr(Option<Lifetime>, MutTy),
     /// A bare function (e.g. `fn(usize) -> bool`)
     BareFn(P<BareFnTy>),
+    /// The empty type (`!`)
+    Empty,
     /// A tuple (`(A, B, C, D,...)`)
     Tup(Vec<P<Ty>> ),
     /// A path (`module::module::...::Type`), optionally
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index afc990f498e..47addd8aba5 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -373,6 +373,7 @@ pub fn noop_fold_ty<T: Folder>(t: P<Ty>, fld: &mut T) -> P<Ty> {
                     decl: fld.fold_fn_decl(decl)
                 }))
             }
+            TyKind::Empty => node,
             TyKind::Tup(tys) => TyKind::Tup(tys.move_map(|ty| fld.fold_ty(ty))),
             TyKind::Paren(ty) => TyKind::Paren(fld.fold_ty(ty)),
             TyKind::Path(qself, path) => {
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index 62e55eb78b7..6214dc5301b 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -976,6 +976,9 @@ impl<'a> State<'a> {
                 try!(self.print_opt_lifetime(lifetime));
                 try!(self.print_mt(mt));
             }
+            ast::TyKind::Empty => {
+                word(&mut self.s, "!")?;
+            },
             ast::TyKind::Tup(ref elts) => {
                 try!(self.popen());
                 try!(self.commasep(Inconsistent, &elts[..],
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index 6d3cdbdc6da..1d40e3e395e 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -319,6 +319,7 @@ pub fn walk_ty<V: Visitor>(visitor: &mut V, typ: &Ty) {
             walk_list!(visitor, visit_lifetime, opt_lifetime);
             visitor.visit_ty(&mutable_type.ty)
         }
+        TyKind::Empty => {},
         TyKind::Tup(ref tuple_element_types) => {
             walk_list!(visitor, visit_ty, tuple_element_types);
         }