auto merge of #15406 : luqmana/rust/nop, r=pcwalton

Extend the null ptr optimization to work with slices, closures, procs, & trait objects by using the internal pointers as the discriminant.

This decreases the size of `Option<&[int]>` (and similar) by one word.

7 files changed, 185 insertions, 77 deletions

diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index d53ecabd5a9..6e2dc95cfd6 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -27,6 +27,10 @@ use {Collection, Mutable};
 use slice::{MutableOrdVector, MutableVectorAllocating, CloneableVector};
 use slice::{Items, MutItems};
 
+
+#[doc(hidden)]
+pub static PTR_MARKER: u8 = 0;
+
 /// An owned, growable vector.
 ///
 /// # Examples
@@ -71,7 +75,11 @@ impl<T> Vec<T> {
     /// ```
     #[inline]
     pub fn new() -> Vec<T> {
-        Vec { len: 0, cap: 0, ptr: 0 as *mut T }
+        // We want ptr to never be NULL so instead we set it to some arbitrary
+        // non-null value which is fine since we never call deallocate on the ptr
+        // if cap is 0. The reason for this is because the pointer of a slice
+        // being NULL would break the null pointer optimization for enums.
+        Vec { len: 0, cap: 0, ptr: &PTR_MARKER as *const _ as *mut T }
     }
 
     /// Constructs a new, empty `Vec` with the specified capacity.
@@ -88,7 +96,7 @@ impl<T> Vec<T> {
     #[inline]
     pub fn with_capacity(capacity: uint) -> Vec<T> {
         if mem::size_of::<T>() == 0 {
-            Vec { len: 0, cap: uint::MAX, ptr: 0 as *mut T }
+            Vec { len: 0, cap: uint::MAX, ptr: &PTR_MARKER as *const _ as *mut T }
         } else if capacity == 0 {
             Vec::new()
         } else {
@@ -1206,15 +1214,7 @@ impl<T> Vec<T> {
     /// would also make any pointers to it invalid.
     #[inline]
     pub fn as_ptr(&self) -> *const T {
-        // If we have a 0-sized vector, then the base pointer should not be NULL
-        // because an iterator over the slice will attempt to yield the base
-        // pointer as the first element in the vector, but this will end up
-        // being Some(NULL) which is optimized to None.
-        if mem::size_of::<T>() == 0 {
-            1 as *const T
-        } else {
-            self.ptr as *const T
-        }
+        self.ptr as *const T
     }
 
     /// Returns a mutable unsafe pointer to the vector's buffer.
@@ -1226,12 +1226,7 @@ impl<T> Vec<T> {
     /// would also make any pointers to it invalid.
     #[inline]
     pub fn as_mut_ptr(&mut self) -> *mut T {
-        // see above for the 0-size check
-        if mem::size_of::<T>() == 0 {
-            1 as *mut T
-        } else {
-            self.ptr
-        }
+        self.ptr
     }
 
     /// Retains only the elements specified by the predicate.
diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs
index 0178c0318b8..8197a7c2dcb 100644
--- a/src/libcore/slice.rs
+++ b/src/libcore/slice.rs
@@ -884,17 +884,20 @@ macro_rules! iterator {
                     if self.ptr == self.end {
                         None
                     } else {
-                        let old = self.ptr;
-                        self.ptr = if mem::size_of::<T>() == 0 {
+                        if mem::size_of::<T>() == 0 {
                             // purposefully don't use 'ptr.offset' because for
                             // vectors with 0-size elements this would return the
                             // same pointer.
-                            transmute(self.ptr as uint + 1)
+                            self.ptr = transmute(self.ptr as uint + 1);
+
+                            // Use a non-null pointer value
+                            Some(transmute(1u))
                         } else {
-                            self.ptr.offset(1)
-                        };
+                            let old = self.ptr;
+                            self.ptr = self.ptr.offset(1);
 
-                        Some(transmute(old))
+                            Some(transmute(old))
+                        }
                     }
                 }
             }
@@ -916,13 +919,17 @@ macro_rules! iterator {
                     if self.end == self.ptr {
                         None
                     } else {
-                        self.end = if mem::size_of::<T>() == 0 {
+                        if mem::size_of::<T>() == 0 {
                             // See above for why 'ptr.offset' isn't used
-                            transmute(self.end as uint - 1)
+                            self.end = transmute(self.end as uint - 1);
+
+                            // Use a non-null pointer value
+                            Some(transmute(1u))
                         } else {
-                            self.end.offset(-1)
-                        };
-                        Some(transmute(self.end))
+                            self.end = self.end.offset(-1);
+
+                            Some(transmute(self.end))
+                        }
                     }
                 }
             }
@@ -956,7 +963,12 @@ impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
     fn idx(&mut self, index: uint) -> Option<&'a T> {
         unsafe {
             if index < self.indexable() {
-                transmute(self.ptr.offset(index as int))
+                if mem::size_of::<T>() == 0 {
+                    // Use a non-null pointer value
+                    Some(transmute(1u))
+                } else {
+                    Some(transmute(self.ptr.offset(index as int)))
+                }
             } else {
                 None
             }
diff --git a/src/librustc/middle/trans/adt.rs b/src/librustc/middle/trans/adt.rs
index f7fb6646938..4c7db01657b 100644
--- a/src/librustc/middle/trans/adt.rs
+++ b/src/librustc/middle/trans/adt.rs
@@ -111,7 +111,7 @@ pub enum Repr {
     StructWrappedNullablePointer {
         pub nonnull: Struct,
         pub nndiscr: Disr,
-        pub ptrfield: uint,
+        pub ptrfield: PointerField,
         pub nullfields: Vec<ty::t>,
     }
 }
@@ -211,24 +211,21 @@ fn represent_type_uncached(cx: &CrateContext, t: ty::t) -> Repr {
                 let mut discr = 0;
                 while discr < 2 {
                     if cases.get(1 - discr).is_zerolen(cx) {
+                        let st = mk_struct(cx, cases.get(discr).tys.as_slice(), false);
                         match cases.get(discr).find_ptr() {
+                            Some(ThinPointer(_)) if st.fields.len() == 1 => {
+                                return RawNullablePointer {
+                                    nndiscr: discr as Disr,
+                                    nnty: *st.fields.get(0),
+                                    nullfields: cases.get(1 - discr).tys.clone()
+                                };
+                            }
                             Some(ptrfield) => {
-                                let st = mk_struct(cx, cases.get(discr).tys.as_slice(),
-                                                   false);
-
-                                return if st.fields.len() == 1 {
-                                    RawNullablePointer {
-                                        nndiscr: discr as Disr,
-                                        nnty: *st.fields.get(0),
-                                        nullfields: cases.get(1 - discr).tys.clone()
-                                    }
-                                } else {
-                                    StructWrappedNullablePointer {
-                                        nndiscr: discr as Disr,
-                                        nonnull: st,
-                                        ptrfield: ptrfield,
-                                        nullfields: cases.get(1 - discr).tys.clone()
-                                    }
+                                return StructWrappedNullablePointer {
+                                    nndiscr: discr as Disr,
+                                    nonnull: st,
+                                    ptrfield: ptrfield,
+                                    nullfields: cases.get(1 - discr).tys.clone()
                                 };
                             }
                             None => { }
@@ -283,23 +280,67 @@ pub fn is_ffi_safe(tcx: &ty::ctxt, def_id: ast::DefId) -> bool {
 }
 
 // this should probably all be in ty
-struct Case { discr: Disr, tys: Vec<ty::t> }
+struct Case {
+    discr: Disr,
+    tys: Vec<ty::t>
+}
+
+
+#[deriving(Show)]
+pub enum PointerField {
+    ThinPointer(uint),
+    FatPointer(uint, uint)
+}
+
 impl Case {
     fn is_zerolen(&self, cx: &CrateContext) -> bool {
         mk_struct(cx, self.tys.as_slice(), false).size == 0
     }
-    fn find_ptr(&self) -> Option<uint> {
-        self.tys.iter().position(|&ty| {
+    fn find_ptr(&self) -> Option<PointerField> {
+        use back::abi::{fn_field_code, slice_elt_base, trt_field_box};
+
+        for (i, &ty) in self.tys.iter().enumerate() {
             match ty::get(ty).sty {
-                ty::ty_uniq(ty) | ty::ty_rptr(_, ty::mt{ty, ..}) => match ty::get(ty).sty {
-                    ty::ty_vec(_, None) | ty::ty_str| ty::ty_trait(..) => false,
-                    _ => true,
+                // &T/&mut T could either be a thin or fat pointer depending on T
+                ty::ty_rptr(_, ty::mt { ty, .. }) => match ty::get(ty).sty {
+                    // &[T] and &str are a pointer and length pair
+                    ty::ty_vec(_, None) | ty::ty_str => return Some(FatPointer(i, slice_elt_base)),
+
+                    // &Trait/&mut Trait are a pair of pointers: the actual object and a vtable
+                    ty::ty_trait(..) => return Some(FatPointer(i, trt_field_box)),
+
+                    // Any other &T/&mut T is just a pointer
+                    _ => return Some(ThinPointer(i))
+                },
+
+                // Box<T> could either be a thin or fat pointer depending on T
+                ty::ty_uniq(t) => match ty::get(t).sty {
+                    // Box<[T]>/Box<str> might be FatPointer in a post DST world
+                    ty::ty_vec(_, None) | ty::ty_str => continue,
+
+                    // Box<Trait> is a pair of pointers: the actual object and a vtable
+                    ty::ty_trait(..) => return Some(FatPointer(i, trt_field_box)),
+
+                    // Any other Box<T> is just a pointer
+                    _ => return Some(ThinPointer(i))
                 },
-                ty::ty_box(..) | ty::ty_bare_fn(..) => true,
-                // Is that everything?  Would closures or slices qualify?
-                _ => false
+
+                // Gc<T> is just a pointer
+                ty::ty_box(..) => return Some(ThinPointer(i)),
+
+                // Functions are just pointers
+                ty::ty_bare_fn(..) => return Some(ThinPointer(i)),
+
+                // Closures are a pair of pointers: the code and environment
+                ty::ty_closure(..) => return Some(FatPointer(i, fn_field_code)),
+
+                // Anything else is not a pointer
+                _ => continue
+
             }
-        })
+        }
+
+        None
     }
 }
 
@@ -552,8 +593,8 @@ pub fn trans_get_discr(bcx: &Block, r: &Repr, scrutinee: ValueRef, cast_to: Opti
             val = ICmp(bcx, cmp, Load(bcx, scrutinee), C_null(llptrty));
             signed = false;
         }
-        StructWrappedNullablePointer { nonnull: ref nonnull, nndiscr, ptrfield, .. } => {
-            val = struct_wrapped_nullable_bitdiscr(bcx, nonnull, nndiscr, ptrfield, scrutinee);
+        StructWrappedNullablePointer { nndiscr, ptrfield, .. } => {
+            val = struct_wrapped_nullable_bitdiscr(bcx, nndiscr, ptrfield, scrutinee);
             signed = false;
         }
     }
@@ -563,12 +604,15 @@ pub fn trans_get_discr(bcx: &Block, r: &Repr, scrutinee: ValueRef, cast_to: Opti
     }
 }
 
-fn struct_wrapped_nullable_bitdiscr(bcx: &Block, nonnull: &Struct, nndiscr: Disr, ptrfield: uint,
+fn struct_wrapped_nullable_bitdiscr(bcx: &Block, nndiscr: Disr, ptrfield: PointerField,
                                     scrutinee: ValueRef) -> ValueRef {
-    let llptr = Load(bcx, GEPi(bcx, scrutinee, [0, ptrfield]));
+    let llptrptr = match ptrfield {
+        ThinPointer(field) => GEPi(bcx, scrutinee, [0, field]),
+        FatPointer(field, pair) => GEPi(bcx, scrutinee, [0, field, pair])
+    };
+    let llptr = Load(bcx, llptrptr);
     let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
-    let llptrty = type_of::type_of(bcx.ccx(), *nonnull.fields.get(ptrfield));
-    ICmp(bcx, cmp, llptr, C_null(llptrty))
+    ICmp(bcx, cmp, llptr, C_null(val_ty(llptr)))
 }
 
 /// Helper for cases where the discriminant is simply loaded.
@@ -655,9 +699,15 @@ pub fn trans_start_init(bcx: &Block, r: &Repr, val: ValueRef, discr: Disr) {
         }
         StructWrappedNullablePointer { nonnull: ref nonnull, nndiscr, ptrfield, .. } => {
             if discr != nndiscr {
-                let llptrptr = GEPi(bcx, val, [0, ptrfield]);
-                let llptrty = type_of::type_of(bcx.ccx(),
-                                               *nonnull.fields.get(ptrfield));
+                let (llptrptr, llptrty) = match ptrfield {
+                    ThinPointer(field) =>
+                        (GEPi(bcx, val, [0, field]),
+                         type_of::type_of(bcx.ccx(), *nonnull.fields.get(field))),
+                    FatPointer(field, pair) => {
+                        let v = GEPi(bcx, val, [0, field, pair]);
+                        (v, val_ty(v).element_type())
+                    }
+                };
                 Store(bcx, C_null(llptrty), llptrptr)
             }
         }
@@ -925,7 +975,11 @@ pub fn const_get_discrim(ccx: &CrateContext, r: &Repr, val: ValueRef)
             }
         }
         StructWrappedNullablePointer { nndiscr, ptrfield, .. } => {
-            if is_null(const_struct_field(ccx, val, ptrfield)) {
+            let (idx, sub_idx) = match ptrfield {
+                ThinPointer(field) => (field, None),
+                FatPointer(field, pair) => (field, Some(pair))
+            };
+            if is_null(const_struct_field(ccx, val, idx, sub_idx)) {
                 /* subtraction as uint is ok because nndiscr is either 0 or 1 */
                 (1 - nndiscr) as Disr
             } else {
@@ -946,18 +1000,18 @@ pub fn const_get_field(ccx: &CrateContext, r: &Repr, val: ValueRef,
                        _discr: Disr, ix: uint) -> ValueRef {
     match *r {
         CEnum(..) => ccx.sess().bug("element access in C-like enum const"),
-        Univariant(..) => const_struct_field(ccx, val, ix),
-        General(..) => const_struct_field(ccx, val, ix + 1),
+        Univariant(..) => const_struct_field(ccx, val, ix, None),
+        General(..) => const_struct_field(ccx, val, ix + 1, None),
         RawNullablePointer { .. } => {
             assert_eq!(ix, 0);
             val
         }
-        StructWrappedNullablePointer{ .. } => const_struct_field(ccx, val, ix)
+        StructWrappedNullablePointer{ .. } => const_struct_field(ccx, val, ix, None)
     }
 }
 
 /// Extract field of struct-like const, skipping our alignment padding.
-fn const_struct_field(ccx: &CrateContext, val: ValueRef, ix: uint)
+fn const_struct_field(ccx: &CrateContext, val: ValueRef, ix: uint, sub_idx: Option<uint>)
     -> ValueRef {
     // Get the ix-th non-undef element of the struct.
     let mut real_ix = 0; // actual position in the struct
@@ -965,7 +1019,10 @@ fn const_struct_field(ccx: &CrateContext, val: ValueRef, ix: uint)
     let mut field;
     loop {
         loop {
-            field = const_get_elt(ccx, val, [real_ix]);
+            field = match sub_idx {
+                Some(si) => const_get_elt(ccx, val, [real_ix, si as u32]),
+                None => const_get_elt(ccx, val, [real_ix])
+            };
             if !is_undef(field) {
                 break;
             }
diff --git a/src/librustc/middle/trans/consts.rs b/src/librustc/middle/trans/consts.rs
index 527ce5dfaae..52a097ca6f0 100644
--- a/src/librustc/middle/trans/consts.rs
+++ b/src/librustc/middle/trans/consts.rs
@@ -484,8 +484,7 @@ fn const_expr_unadjusted(cx: &CrateContext, e: &ast::Expr,
                 if ty::type_is_signed(ety) { llvm::LLVMConstFPToSI(v, llty.to_ref()) }
                 else { llvm::LLVMConstFPToUI(v, llty.to_ref()) }
               }
-              (expr::cast_enum, expr::cast_integral) |
-              (expr::cast_enum, expr::cast_float)  => {
+              (expr::cast_enum, expr::cast_integral) => {
                 let repr = adt::represent_type(cx, basety);
                 let discr = adt::const_get_discrim(cx, &*repr, v);
                 let iv = C_integral(cx.int_type, discr, false);
diff --git a/src/librustc/middle/trans/debuginfo.rs b/src/librustc/middle/trans/debuginfo.rs
index 7eb3fcce780..f281d8e2448 100644
--- a/src/librustc/middle/trans/debuginfo.rs
+++ b/src/librustc/middle/trans/debuginfo.rs
@@ -2152,8 +2152,12 @@ impl EnumMemberDescriptionFactory {
                 let null_variant_index = (1 - nndiscr) as uint;
                 let null_variant_ident = self.variants.get(null_variant_index).name;
                 let null_variant_name = token::get_ident(null_variant_ident);
+                let discrfield = match ptrfield {
+                    adt::ThinPointer(field) => format!("{}", field),
+                    adt::FatPointer(field, pair) => format!("{}${}", field, pair)
+                };
                 let union_member_name = format!("RUST$ENCODED$ENUM${}${}",
-                                                ptrfield,
+                                                discrfield,
                                                 null_variant_name);
 
                 // Create the (singleton) list of descriptions of union members.
@@ -2196,7 +2200,7 @@ impl VariantMemberDescriptionFactory {
 
 enum EnumDiscriminantInfo {
     RegularDiscriminant(DIType),
-    OptimizedDiscriminant(uint),
+    OptimizedDiscriminant(adt::PointerField),
     NoDiscriminant
 }
 
diff --git a/src/librustc/middle/trans/tvec.rs b/src/librustc/middle/trans/tvec.rs
index 65bf0b85008..19d7d6c6a00 100644
--- a/src/librustc/middle/trans/tvec.rs
+++ b/src/librustc/middle/trans/tvec.rs
@@ -155,8 +155,9 @@ pub fn trans_slice_vstore<'a>(
     let llcount = C_uint(ccx, count);
     let llfixed;
     if count == 0 {
-        // Zero-length array: just use NULL as the data pointer
-        llfixed = C_null(vt.llunit_ty.ptr_to());
+        // Just create a zero-sized alloca to preserve
+        // the non-null invariant of the inner slice ptr
+        llfixed = base::arrayalloca(bcx, vt.llunit_ty, llcount);
     } else {
         // Make a fixed-length backing array and allocate it on the stack.
         llfixed = base::arrayalloca(bcx, vt.llunit_ty, llcount);
diff --git a/src/test/run-pass/enum-null-pointer-opt.rs b/src/test/run-pass/enum-null-pointer-opt.rs
new file mode 100644
index 00000000000..bd9dfc1e449
--- /dev/null
+++ b/src/test/run-pass/enum-null-pointer-opt.rs
@@ -0,0 +1,40 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+
+use std::gc::Gc;
+use std::mem::size_of;
+
+trait Trait {}
+
+fn main() {
+    // Closures - || / proc()
+    assert_eq!(size_of::<proc()>(), size_of::<Option<proc()>>());
+    assert_eq!(size_of::<||>(), size_of::<Option<||>>());
+
+    // Functions
+    assert_eq!(size_of::<fn(int)>(), size_of::<Option<fn(int)>>());
+    assert_eq!(size_of::<extern "C" fn(int)>(), size_of::<Option<extern "C" fn(int)>>());
+
+    // Slices - &str / &[T] / &mut [T]
+    assert_eq!(size_of::<&str>(), size_of::<Option<&str>>());
+    assert_eq!(size_of::<&[int]>(), size_of::<Option<&[int]>>());
+    assert_eq!(size_of::<&mut [int]>(), size_of::<Option<&mut [int]>>());
+
+    // Traits - Box<Trait> / &Trait / &mut Trait
+    assert_eq!(size_of::<Box<Trait>>(), size_of::<Option<Box<Trait>>>());
+    assert_eq!(size_of::<&Trait>(), size_of::<Option<&Trait>>());
+    assert_eq!(size_of::<&mut Trait>(), size_of::<Option<&mut Trait>>());
+
+    // Pointers - Box<T> / Gc<T>
+    assert_eq!(size_of::<Box<int>>(), size_of::<Option<Box<int>>>());
+    assert_eq!(size_of::<Gc<int>>(), size_of::<Option<Gc<int>>>());
+
+}