Introduce marker types for indicating variance and for opting out

of builtin bounds.

Fixes #10834.
Fixes #11385.
cc #5922.

36 files changed, 729 insertions, 154 deletions

diff --git a/src/libarena/lib.rs b/src/libarena/lib.rs
index 27dad55c429..44ec3f4a5a1 100644
--- a/src/libarena/lib.rs
+++ b/src/libarena/lib.rs
@@ -33,6 +33,7 @@ use std::cast;
 use std::cell::{Cell, RefCell};
 use std::num;
 use std::ptr;
+use std::kinds::marker;
 use std::mem;
 use std::rt::global_heap;
 use std::uint;
@@ -71,7 +72,6 @@ struct Chunk {
 // different chunks than objects without destructors. This reduces
 // overhead when initializing plain-old-data and means we don't need
 // to waste time running the destructors of POD.
-#[no_freeze]
 pub struct Arena {
     // The head is separated out from the list as a unbenchmarked
     // microoptimization, to avoid needing to case on the list to
@@ -79,6 +79,7 @@ pub struct Arena {
     priv head: Chunk,
     priv pod_head: Chunk,
     priv chunks: RefCell<@List<Chunk>>,
+    priv no_freeze: marker::NoFreeze,
 }
 
 impl Arena {
@@ -91,6 +92,7 @@ impl Arena {
             head: chunk(initial_size, false),
             pod_head: chunk(initial_size, true),
             chunks: RefCell::new(@Nil),
+            no_freeze: marker::NoFreeze,
         }
     }
 }
diff --git a/src/libextra/arc.rs b/src/libextra/arc.rs
index 1c6c3adf972..43366d2aa6d 100644
--- a/src/libextra/arc.rs
+++ b/src/libextra/arc.rs
@@ -45,6 +45,7 @@ use sync;
 use sync::{Mutex, RWLock};
 
 use std::cast;
+use std::kinds::marker;
 use std::sync::arc::UnsafeArc;
 use std::task;
 
@@ -150,9 +151,10 @@ impl<T:Freeze + Send> Clone for Arc<T> {
 struct MutexArcInner<T> { lock: Mutex, failed: bool, data: T }
 
 /// An Arc with mutable data protected by a blocking mutex.
-#[no_freeze]
-pub struct MutexArc<T> { priv x: UnsafeArc<MutexArcInner<T>> }
-
+pub struct MutexArc<T> {
+    priv x: UnsafeArc<MutexArcInner<T>>,
+    priv marker: marker::NoFreeze,
+}
 
 impl<T:Send> Clone for MutexArc<T> {
     /// Duplicate a mutex-protected Arc. See arc::clone for more details.
@@ -160,7 +162,8 @@ impl<T:Send> Clone for MutexArc<T> {
     fn clone(&self) -> MutexArc<T> {
         // NB: Cloning the underlying mutex is not necessary. Its reference
         // count would be exactly the same as the shared state's.
-        MutexArc { x: self.x.clone() }
+        MutexArc { x: self.x.clone(),
+                   marker: marker::NoFreeze, }
     }
 }
 
@@ -179,7 +182,8 @@ impl<T:Send> MutexArc<T> {
             lock: Mutex::new_with_condvars(num_condvars),
             failed: false, data: user_data
         };
-        MutexArc { x: UnsafeArc::new(data) }
+        MutexArc { x: UnsafeArc::new(data),
+                   marker: marker::NoFreeze, }
     }
 
     /**
@@ -318,16 +322,17 @@ struct RWArcInner<T> { lock: RWLock, failed: bool, data: T }
  *
  * Unlike mutex_arcs, rw_arcs are safe, because they cannot be nested.
  */
-#[no_freeze]
 pub struct RWArc<T> {
     priv x: UnsafeArc<RWArcInner<T>>,
+    priv marker: marker::NoFreeze,
 }
 
 impl<T:Freeze + Send> Clone for RWArc<T> {
     /// Duplicate a rwlock-protected Arc. See arc::clone for more details.
     #[inline]
     fn clone(&self) -> RWArc<T> {
-        RWArc { x: self.x.clone() }
+        RWArc { x: self.x.clone(),
+                marker: marker::NoFreeze, }
     }
 
 }
@@ -347,7 +352,8 @@ impl<T:Freeze + Send> RWArc<T> {
             lock: RWLock::new_with_condvars(num_condvars),
             failed: false, data: user_data
         };
-        RWArc { x: UnsafeArc::new(data), }
+        RWArc { x: UnsafeArc::new(data),
+                marker: marker::NoFreeze, }
     }
 
     /**
diff --git a/src/librustc/middle/lang_items.rs b/src/librustc/middle/lang_items.rs
index d11cd4b3f38..aed35c6075e 100644
--- a/src/librustc/middle/lang_items.rs
+++ b/src/librustc/middle/lang_items.rs
@@ -273,4 +273,17 @@ lets_do_this! {
     37, ManagedHeapLangItem,             "managed_heap",            managed_heap;
     38, ExchangeHeapLangItem,            "exchange_heap",           exchange_heap;
     39, GcLangItem,                      "gc",                      gc;
+
+    40, CovariantTypeItem,               "covariant_type",          covariant_type;
+    41, ContravariantTypeItem,           "contravariant_type",      contravariant_type;
+    42, InvariantTypeItem,               "invariant_type",          invariant_type;
+
+    43, CovariantLifetimeItem,           "covariant_lifetime",      covariant_lifetime;
+    44, ContravariantLifetimeItem,       "contravariant_lifetime",  contravariant_lifetime;
+    45, InvariantLifetimeItem,           "invariant_lifetime",      invariant_lifetime;
+
+    46, NoFreezeItem,                    "no_freeze_bound",         no_freeze_bound;
+    47, NoSendItem,                      "no_send_bound",           no_send_bound;
+    48, NoPodItem,                       "no_pod_bound",            no_pod_bound;
+    49, ManagedItem,                     "managed_bound",           managed_bound;
 }
diff --git a/src/librustc/middle/lint.rs b/src/librustc/middle/lint.rs
index 89d5ca74012..825509d539e 100644
--- a/src/librustc/middle/lint.rs
+++ b/src/librustc/middle/lint.rs
@@ -957,8 +957,8 @@ static other_attrs: &'static [&'static str] = &[
     "thread_local", // for statics
     "allow", "deny", "forbid", "warn", // lint options
     "deprecated", "experimental", "unstable", "stable", "locked", "frozen", //item stability
-    "crate_map", "cfg", "doc", "export_name", "link_section", "no_freeze",
-    "no_mangle", "no_send", "static_assert", "unsafe_no_drop_flag", "packed",
+    "crate_map", "cfg", "doc", "export_name", "link_section",
+    "no_mangle", "static_assert", "unsafe_no_drop_flag", "packed",
     "simd", "repr", "deriving", "unsafe_destructor", "link", "phase",
     "macro_export", "must_use",
 
diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs
index d39369c7a5f..38b34cd13bc 100644
--- a/src/librustc/middle/trans/base.rs
+++ b/src/librustc/middle/trans/base.rs
@@ -328,7 +328,7 @@ pub fn at_box_body(bcx: &Block, body_t: ty::t, boxptr: ValueRef) -> ValueRef {
 // malloc_raw_dyn: allocates a box to contain a given type, but with a
 // potentially dynamic size.
 pub fn malloc_raw_dyn<'a>(
-                      bcx: &'a Block,
+                      bcx: &'a Block<'a>,
                       t: ty::t,
                       heap: heap,
                       size: ValueRef)
@@ -425,7 +425,7 @@ pub fn malloc_general_dyn<'a>(
     }
 }
 
-pub fn malloc_general<'a>(bcx: &'a Block, t: ty::t, heap: heap)
+pub fn malloc_general<'a>(bcx: &'a Block<'a>, t: ty::t, heap: heap)
                       -> MallocResult<'a> {
     let ty = type_of(bcx.ccx(), t);
     assert!(heap != heap_exchange);
@@ -1230,18 +1230,19 @@ pub fn make_return_pointer(fcx: &FunctionContext, output_type: ty::t)
 //
 // Be warned! You must call `init_function` before doing anything with the
 // returned function context.
-pub fn new_fn_ctxt_detailed(ccx: @CrateContext,
-                            path: ast_map::Path,
-                            llfndecl: ValueRef,
-                            id: ast::NodeId,
-                            has_env: bool,
-                            output_type: ty::t,
-                            param_substs: Option<@param_substs>,
-                            sp: Option<Span>)
-                            -> FunctionContext {
+pub fn new_fn_ctxt<'a>(ccx: @CrateContext,
+                       path: ast_map::Path,
+                       llfndecl: ValueRef,
+                       id: ast::NodeId,
+                       has_env: bool,
+                       output_type: ty::t,
+                       param_substs: Option<@param_substs>,
+                       sp: Option<Span>,
+                       block_arena: &'a TypedArena<Block<'a>>)
+                       -> FunctionContext<'a> {
     for p in param_substs.iter() { p.validate(); }
 
-    debug!("new_fn_ctxt_detailed(path={},
+    debug!("new_fn_ctxt(path={},
            id={:?}, \
            param_substs={})",
            path_str(ccx.sess, path),
@@ -1258,25 +1259,25 @@ pub fn new_fn_ctxt_detailed(ccx: @CrateContext,
     let debug_context = debuginfo::create_function_debug_context(ccx, id, param_substs, llfndecl);
 
     let mut fcx = FunctionContext {
-        llfn: llfndecl,
-        llenv: None,
-        llretptr: Cell::new(None),
-        entry_bcx: RefCell::new(None),
-        alloca_insert_pt: Cell::new(None),
-        llreturn: Cell::new(None),
-        personality: Cell::new(None),
-        caller_expects_out_pointer: uses_outptr,
-        llargs: RefCell::new(HashMap::new()),
-        lllocals: RefCell::new(HashMap::new()),
-        llupvars: RefCell::new(HashMap::new()),
-        id: id,
-        param_substs: param_substs,
-        span: sp,
-        path: path,
-        block_arena: TypedArena::new(),
-        ccx: ccx,
-        debug_context: debug_context,
-        scopes: RefCell::new(~[])
+          llfn: llfndecl,
+          llenv: None,
+          llretptr: Cell::new(None),
+          entry_bcx: RefCell::new(None),
+          alloca_insert_pt: Cell::new(None),
+          llreturn: Cell::new(None),
+          personality: Cell::new(None),
+          caller_expects_out_pointer: uses_outptr,
+          llargs: RefCell::new(HashMap::new()),
+          lllocals: RefCell::new(HashMap::new()),
+          llupvars: RefCell::new(HashMap::new()),
+          id: id,
+          param_substs: param_substs,
+          span: sp,
+          path: path,
+          block_arena: block_arena,
+          ccx: ccx,
+          debug_context: debug_context,
+          scopes: RefCell::new(~[])
     };
 
     if has_env {
@@ -1328,18 +1329,6 @@ pub fn init_function<'a>(
     }
 }
 
-pub fn new_fn_ctxt(ccx: @CrateContext,
-                   path: ast_map::Path,
-                   llfndecl: ValueRef,
-                   has_env: bool,
-                   output_type: ty::t,
-                   sp: Option<Span>)
-                   -> FunctionContext {
-    // FIXME(#11385): Do not call `init_function` here; it will typecheck
-    // but segfault.
-    new_fn_ctxt_detailed(ccx, path, llfndecl, -1, has_env, output_type, None, sp)
-}
-
 // NB: must keep 4 fns in sync:
 //
 //  - type_of_fn
@@ -1411,7 +1400,8 @@ fn copy_args_to_allocas<'a>(fcx: &FunctionContext<'a>,
 
 // Ties up the llstaticallocas -> llloadenv -> lltop edges,
 // and builds the return block.
-pub fn finish_fn(fcx: &FunctionContext, last_bcx: &Block) {
+pub fn finish_fn<'a>(fcx: &'a FunctionContext<'a>,
+                     last_bcx: &'a Block<'a>) {
     let _icx = push_ctxt("finish_fn");
 
     let ret_cx = match fcx.llreturn.get() {
@@ -1469,7 +1459,7 @@ pub fn trans_closure<'a>(ccx: @CrateContext,
                          id: ast::NodeId,
                          _attributes: &[ast::Attribute],
                          output_type: ty::t,
-                         maybe_load_env: |&'a Block<'a>| -> &'a Block<'a>) {
+                         maybe_load_env: <'b> |&'b Block<'b>| -> &'b Block<'b>) {
     ccx.stats.n_closures.set(ccx.stats.n_closures.get() + 1);
 
     let _icx = push_ctxt("trans_closure");
@@ -1483,8 +1473,16 @@ pub fn trans_closure<'a>(ccx: @CrateContext,
         _ => false
     };
 
-    let fcx = new_fn_ctxt_detailed(ccx, path, llfndecl, id, has_env, output_type,
-                                   param_substs, Some(body.span));
+    let arena = TypedArena::new();
+    let fcx = new_fn_ctxt(ccx,
+                          path,
+                          llfndecl,
+                          id,
+                          has_env,
+                          output_type,
+                          param_substs,
+                          Some(body.span),
+                          &arena);
     init_function(&fcx, false, output_type, param_substs);
 
     // cleanup scope for the incoming arguments
@@ -1626,8 +1624,16 @@ fn trans_enum_variant_or_tuple_like_struct(ccx: @CrateContext,
                  ty_to_str(ccx.tcx, ctor_ty)))
     };
 
-    let fcx = new_fn_ctxt_detailed(ccx, ~[], llfndecl, ctor_id, false,
-                                   result_ty, param_substs, None);
+    let arena = TypedArena::new();
+    let fcx = new_fn_ctxt(ccx,
+                          ~[],
+                          llfndecl,
+                          ctor_id,
+                          false,
+                          result_ty,
+                          param_substs,
+                          None,
+                          &arena);
     init_function(&fcx, false, result_ty, param_substs);
 
     let arg_tys = ty::ty_fn_args(ctor_ty);
diff --git a/src/librustc/middle/trans/cleanup.rs b/src/librustc/middle/trans/cleanup.rs
index 6e92ea9f11e..c6d56db6877 100644
--- a/src/librustc/middle/trans/cleanup.rs
+++ b/src/librustc/middle/trans/cleanup.rs
@@ -214,7 +214,7 @@ impl<'a> CleanupMethods<'a> for FunctionContext<'a> {
         self.ccx.tcx.sess.bug("No loop scope found");
     }
 
-    fn normal_exit_block(&self,
+    fn normal_exit_block(&'a self,
                          cleanup_scope: ast::NodeId,
                          exit: uint) -> BasicBlockRef {
         /*!
@@ -226,7 +226,7 @@ impl<'a> CleanupMethods<'a> for FunctionContext<'a> {
         self.trans_cleanups_to_exit_scope(LoopExit(cleanup_scope, exit))
     }
 
-    fn return_exit_block(&self) -> BasicBlockRef {
+    fn return_exit_block(&'a self) -> BasicBlockRef {
         /*!
          * Returns a block to branch to which will perform all pending
          * cleanups and then return from this function
@@ -371,7 +371,7 @@ impl<'a> CleanupMethods<'a> for FunctionContext<'a> {
         scopes.get().iter().rev().any(|s| s.needs_invoke())
     }
 
-    fn get_landing_pad(&self) -> BasicBlockRef {
+    fn get_landing_pad(&'a self) -> BasicBlockRef {
         /*!
          * Returns a basic block to branch to in the event of a failure.
          * This block will run the failure cleanups and eventually
@@ -481,7 +481,7 @@ impl<'a> CleanupHelperMethods<'a> for FunctionContext<'a> {
         f(scopes.get().last().unwrap())
     }
 
-    fn trans_cleanups_to_exit_scope(&self,
+    fn trans_cleanups_to_exit_scope(&'a self,
                                     label: EarlyExitLabel)
                                     -> BasicBlockRef {
         /*!
@@ -641,7 +641,7 @@ impl<'a> CleanupHelperMethods<'a> for FunctionContext<'a> {
         prev_llbb
     }
 
-    fn get_or_create_landing_pad(&self) -> BasicBlockRef {
+    fn get_or_create_landing_pad(&'a self) -> BasicBlockRef {
         /*!
          * Creates a landing pad for the top scope, if one does not
          * exist.  The landing pad will perform all cleanups necessary
@@ -903,10 +903,10 @@ pub trait CleanupMethods<'a> {
                                           custom_scope: CustomScopeIndex)
                                           -> &'a Block<'a>;
     fn top_loop_scope(&self) -> ast::NodeId;
-    fn normal_exit_block(&self,
+    fn normal_exit_block(&'a self,
                          cleanup_scope: ast::NodeId,
                          exit: uint) -> BasicBlockRef;
-    fn return_exit_block(&self) -> BasicBlockRef;
+    fn return_exit_block(&'a self) -> BasicBlockRef;
     fn schedule_drop_mem(&self,
                          cleanup_scope: ScopeId,
                          val: ValueRef,
@@ -929,7 +929,7 @@ pub trait CleanupMethods<'a> {
                                     custom_scope: CustomScopeIndex,
                                     cleanup: ~Cleanup);
     fn needs_invoke(&self) -> bool;
-    fn get_landing_pad(&self) -> BasicBlockRef;
+    fn get_landing_pad(&'a self) -> BasicBlockRef;
 }
 
 trait CleanupHelperMethods<'a> {
@@ -940,10 +940,10 @@ trait CleanupHelperMethods<'a> {
     fn trans_scope_cleanups(&self,
                             bcx: &'a Block<'a>,
                             scope: &CleanupScope<'a>) -> &'a Block<'a>;
-    fn trans_cleanups_to_exit_scope(&self,
+    fn trans_cleanups_to_exit_scope(&'a self,
                                     label: EarlyExitLabel)
                                     -> BasicBlockRef;
-    fn get_or_create_landing_pad(&self) -> BasicBlockRef;
+    fn get_or_create_landing_pad(&'a self) -> BasicBlockRef;
     fn scopes_len(&self) -> uint;
     fn push_scope(&self, scope: CleanupScope<'a>);
     fn pop_scope(&self) -> CleanupScope<'a>;
diff --git a/src/librustc/middle/trans/closure.rs b/src/librustc/middle/trans/closure.rs
index 5a8039f9c4d..d1979c3fee7 100644
--- a/src/librustc/middle/trans/closure.rs
+++ b/src/librustc/middle/trans/closure.rs
@@ -25,6 +25,7 @@ use middle::ty;
 use util::ppaux::Repr;
 use util::ppaux::ty_to_str;
 
+use arena::TypedArena;
 use std::vec;
 use syntax::ast;
 use syntax::ast_map::PathName;
@@ -404,9 +405,9 @@ pub fn trans_expr_fn<'a>(
     };
     let ClosureResult {llbox, cdata_ty, bcx} = build_closure(bcx, cap_vars, sigil);
     trans_closure(ccx, sub_path, decl, body, llfn,
-                    bcx.fcx.param_substs, user_id,
-                    [], ty::ty_fn_ret(fty),
-                    |bcx| load_environment(bcx, cdata_ty, cap_vars, sigil));
+                  bcx.fcx.param_substs, user_id,
+                  [], ty::ty_fn_ret(fty),
+                  |bcx| load_environment(bcx, cdata_ty, cap_vars, sigil));
     fill_fn_pair(bcx, dest_addr, llfn, llbox);
 
     bcx
@@ -470,7 +471,9 @@ pub fn get_wrapper_for_bare_fn(ccx: @CrateContext,
 
     let _icx = push_ctxt("closure::get_wrapper_for_bare_fn");
 
-    let fcx = new_fn_ctxt(ccx, ~[], llfn, true, f.sig.output, None);
+    let arena = TypedArena::new();
+    let fcx = new_fn_ctxt(ccx, ~[], llfn, -1, true, f.sig.output, None, None,
+                          &arena);
     init_function(&fcx, true, f.sig.output, None);
     let bcx = fcx.entry_bcx.get().unwrap();
 
diff --git a/src/librustc/middle/trans/common.rs b/src/librustc/middle/trans/common.rs
index 18a6727dee0..d35f9a28a83 100644
--- a/src/librustc/middle/trans/common.rs
+++ b/src/librustc/middle/trans/common.rs
@@ -281,7 +281,7 @@ pub struct FunctionContext<'a> {
     path: Path,
 
     // The arena that blocks are allocated from.
-    block_arena: TypedArena<Block<'a>>,
+    block_arena: &'a TypedArena<Block<'a>>,
 
     // This function's enclosing crate context.
     ccx: @CrateContext,
diff --git a/src/librustc/middle/trans/glue.rs b/src/librustc/middle/trans/glue.rs
index ab77d105e5f..705501c8223 100644
--- a/src/librustc/middle/trans/glue.rs
+++ b/src/librustc/middle/trans/glue.rs
@@ -36,6 +36,7 @@ use util::ppaux::ty_to_short_str;
 
 use middle::trans::type_::Type;
 
+use arena::TypedArena;
 use std::c_str::ToCStr;
 use std::cell::Cell;
 use std::libc::c_uint;
@@ -504,16 +505,21 @@ fn declare_generic_glue(ccx: &CrateContext, t: ty::t, llfnty: Type,
     return llfn;
 }
 
-pub type glue_helper<'a> =
-    'a |&'a Block<'a>, ValueRef, ty::t| -> &'a Block<'a>;
-
-fn make_generic_glue(ccx: @CrateContext, t: ty::t, llfn: ValueRef,
-                     helper: glue_helper, name: &str) -> ValueRef {
+fn make_generic_glue(ccx: @CrateContext,
+                     t: ty::t,
+                     llfn: ValueRef,
+                     helper: <'a> |&'a Block<'a>, ValueRef, ty::t|
+                                  -> &'a Block<'a>,
+                     name: &str)
+                     -> ValueRef {
     let _icx = push_ctxt("make_generic_glue");
     let glue_name = format!("glue {} {}", name, ty_to_short_str(ccx.tcx, t));
     let _s = StatRecorder::new(ccx, glue_name);
 
-    let fcx = new_fn_ctxt(ccx, ~[], llfn, false, ty::mk_nil(), None);
+    let arena = TypedArena::new();
+    let fcx = new_fn_ctxt(ccx, ~[], llfn, -1, false, ty::mk_nil(), None, None,
+                          &arena);
+
     init_function(&fcx, false, ty::mk_nil(), None);
 
     lib::llvm::SetLinkage(llfn, lib::llvm::InternalLinkage);
@@ -529,7 +535,6 @@ fn make_generic_glue(ccx: @CrateContext, t: ty::t, llfn: ValueRef,
     let bcx = fcx.entry_bcx.get().unwrap();
     let llrawptr0 = unsafe { llvm::LLVMGetParam(llfn, fcx.arg_pos(0) as c_uint) };
     let bcx = helper(bcx, llrawptr0, t);
-
     finish_fn(&fcx, bcx);
 
     llfn
diff --git a/src/librustc/middle/trans/intrinsic.rs b/src/librustc/middle/trans/intrinsic.rs
index b662d08062f..da3b9202d92 100644
--- a/src/librustc/middle/trans/intrinsic.rs
+++ b/src/librustc/middle/trans/intrinsic.rs
@@ -10,6 +10,7 @@
 
 #[allow(non_uppercase_pattern_statics)];
 
+use arena::TypedArena;
 use back::abi;
 use lib::llvm::{SequentiallyConsistent, Acquire, Release, Xchg};
 use lib::llvm::{ValueRef, Pointer, Array, Struct};
@@ -194,8 +195,16 @@ pub fn trans_intrinsic(ccx: @CrateContext,
 
     let output_type = ty::ty_fn_ret(ty::node_id_to_type(ccx.tcx, item.id));
 
-    let fcx = new_fn_ctxt_detailed(ccx, path, decl, item.id, false, output_type,
-                                   Some(substs), Some(item.span));
+    let arena = TypedArena::new();
+    let fcx = new_fn_ctxt(ccx,
+                          path,
+                          decl,
+                          item.id,
+                          false,
+                          output_type,
+                          Some(substs),
+                          Some(item.span),
+                          &arena);
     init_function(&fcx, true, output_type, Some(substs));
 
     set_always_inline(fcx.llfn);
diff --git a/src/librustc/middle/trans/reflect.rs b/src/librustc/middle/trans/reflect.rs
index cbfd83309a4..0e245de6019 100644
--- a/src/librustc/middle/trans/reflect.rs
+++ b/src/librustc/middle/trans/reflect.rs
@@ -24,6 +24,7 @@ use middle::trans::type_of::*;
 use middle::ty;
 use util::ppaux::ty_to_str;
 
+use arena::TypedArena;
 use std::libc::c_uint;
 use std::option::{Some,None};
 use std::vec;
@@ -292,10 +293,17 @@ impl<'a> Reflector<'a> {
                                                                sub_path,
                                                                "get_disr");
 
-                let llfdecl = decl_internal_rust_fn(ccx, false,
-                                                    [opaqueptrty],
-                                                    ty::mk_u64(), sym);
-                let fcx = new_fn_ctxt(ccx, ~[], llfdecl, false, ty::mk_u64(), None);
+                let llfdecl = decl_internal_rust_fn(ccx, false, [opaqueptrty], ty::mk_u64(), sym);
+                let arena = TypedArena::new();
+                let fcx = new_fn_ctxt(ccx,
+                                      ~[],
+                                      llfdecl,
+                                      -1, // id
+                                      false,
+                                      ty::mk_u64(),
+                                      None,
+                                      None,
+                                      &arena);
                 init_function(&fcx, false, ty::mk_u64(), None);
 
                 let arg = unsafe {
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index f216a1cc0a2..f26d9432794 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -1772,7 +1772,9 @@ def_type_content_sets!(
         // Things that prevent values from being considered sized
         Nonsized                            = 0b0000__00000000__0001,
 
-        // Things that make values considered not POD (same as `Moves`)
+        // Things that make values considered not POD (would be same
+        // as `Moves`, but for the fact that managed data `@` is
+        // not considered POD)
         Nonpod                              = 0b0000__00001111__0000,
 
         // Bits to set when a managed value is encountered
@@ -2051,7 +2053,7 @@ pub fn type_contents(cx: ctxt, ty: t) -> TypeContents {
                 if ty::has_dtor(cx, did) {
                     res = res | TC::OwnsDtor;
                 }
-                apply_attributes(cx, did, res)
+                apply_lang_items(cx, did, res)
             }
 
             ty_tup(ref tys) => {
@@ -2066,7 +2068,7 @@ pub fn type_contents(cx: ctxt, ty: t) -> TypeContents {
                             tc_ty(cx, *arg_ty, cache)
                         })
                     });
-                apply_attributes(cx, did, res)
+                apply_lang_items(cx, did, res)
             }
 
             ty_param(p) => {
@@ -2121,13 +2123,21 @@ pub fn type_contents(cx: ctxt, ty: t) -> TypeContents {
         mc | tc_ty(cx, mt.ty, cache)
     }
 
-    fn apply_attributes(cx: ctxt,
+    fn apply_lang_items(cx: ctxt,
                         did: ast::DefId,
                         tc: TypeContents)
                         -> TypeContents {
-        tc |
-            TC::ReachesMutable.when(has_attr(cx, did, "no_freeze")) |
-            TC::ReachesNonsendAnnot.when(has_attr(cx, did, "no_send"))
+        if Some(did) == cx.lang_items.no_freeze_bound() {
+            tc | TC::ReachesMutable
+        } else if Some(did) == cx.lang_items.no_send_bound() {
+            tc | TC::ReachesNonsendAnnot
+        } else if Some(did) == cx.lang_items.managed_bound() {
+            tc | TC::Managed
+        } else if Some(did) == cx.lang_items.no_pod_bound() {
+            tc | TC::OwnsAffine
+        } else {
+            tc
+        }
     }
 
     fn borrowed_contents(region: ty::Region,
diff --git a/src/librustc/middle/typeck/variance.rs b/src/librustc/middle/typeck/variance.rs
index dc57ad747eb..83be5fd2a30 100644
--- a/src/librustc/middle/typeck/variance.rs
+++ b/src/librustc/middle/typeck/variance.rs
@@ -397,6 +397,15 @@ impl<'a> Visitor<()> for TermsContext<'a> {
 struct ConstraintContext<'a> {
     terms_cx: TermsContext<'a>,
 
+    // These are the def-id of the std::kinds::marker::InvariantType,
+    // std::kinds::marker::InvariantLifetime, and so on. The arrays
+    // are indexed by the `ParamKind` (type, lifetime, self). Note
+    // that there are no marker types for self, so the entries for
+    // self are always None.
+    invariant_lang_items: [Option<ast::DefId>, ..3],
+    covariant_lang_items: [Option<ast::DefId>, ..3],
+    contravariant_lang_items: [Option<ast::DefId>, ..3],
+
     // These are pointers to common `ConstantTerm` instances
     covariant: VarianceTermPtr<'a>,
     contravariant: VarianceTermPtr<'a>,
@@ -416,12 +425,36 @@ struct Constraint<'a> {
 fn add_constraints_from_crate<'a>(terms_cx: TermsContext<'a>,
                                   crate: &ast::Crate)
                                   -> ConstraintContext<'a> {
+    let mut invariant_lang_items = [None, ..3];
+    let mut covariant_lang_items = [None, ..3];
+    let mut contravariant_lang_items = [None, ..3];
+
+    covariant_lang_items[TypeParam as uint] =
+        terms_cx.tcx.lang_items.covariant_type();
+    covariant_lang_items[RegionParam as uint] =
+        terms_cx.tcx.lang_items.covariant_lifetime();
+
+    contravariant_lang_items[TypeParam as uint] =
+        terms_cx.tcx.lang_items.contravariant_type();
+    contravariant_lang_items[RegionParam as uint] =
+        terms_cx.tcx.lang_items.contravariant_lifetime();
+
+    invariant_lang_items[TypeParam as uint] =
+        terms_cx.tcx.lang_items.invariant_type();
+    invariant_lang_items[RegionParam as uint] =
+        terms_cx.tcx.lang_items.invariant_lifetime();
+
     let covariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Covariant));
     let contravariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Contravariant));
     let invariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Invariant));
     let bivariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Bivariant));
     let mut constraint_cx = ConstraintContext {
         terms_cx: terms_cx,
+
+        invariant_lang_items: invariant_lang_items,
+        covariant_lang_items: covariant_lang_items,
+        contravariant_lang_items: contravariant_lang_items,
+
         covariant: covariant,
         contravariant: contravariant,
         invariant: invariant,
@@ -520,7 +553,14 @@ impl<'a> ConstraintContext<'a> {
          */
 
         assert_eq!(param_def_id.crate, item_def_id.crate);
-        if param_def_id.crate == ast::LOCAL_CRATE {
+
+        if self.invariant_lang_items[kind as uint] == Some(item_def_id) {
+            self.invariant
+        } else if self.covariant_lang_items[kind as uint] == Some(item_def_id) {
+            self.covariant
+        } else if self.contravariant_lang_items[kind as uint] == Some(item_def_id) {
+            self.contravariant
+        } else if param_def_id.crate == ast::LOCAL_CRATE {
             // Parameter on an item defined within current crate:
             // variance not yet inferred, so return a symbolic
             // variance.
diff --git a/src/libstd/c_str.rs b/src/libstd/c_str.rs
index 6e6aa9ad3fa..ded80d07003 100644
--- a/src/libstd/c_str.rs
+++ b/src/libstd/c_str.rs
@@ -66,6 +66,7 @@ use cast;
 use container::Container;
 use iter::{Iterator, range};
 use libc;
+use kinds::marker;
 use ops::Drop;
 use option::{Option, Some, None};
 use ptr::RawPtr;
@@ -174,7 +175,7 @@ impl CString {
     pub fn iter<'a>(&'a self) -> CChars<'a> {
         CChars {
             ptr: self.buf,
-            lifetime: unsafe { cast::transmute(self.buf) },
+            marker: marker::ContravariantLifetime,
         }
     }
 }
@@ -332,7 +333,7 @@ fn check_for_null(v: &[u8], buf: *mut libc::c_char) {
 /// Use with the `std::iter` module.
 pub struct CChars<'a> {
     priv ptr: *libc::c_char,
-    priv lifetime: &'a libc::c_char, // FIXME: #5922
+    priv marker: marker::ContravariantLifetime<'a>,
 }
 
 impl<'a> Iterator<libc::c_char> for CChars<'a> {
diff --git a/src/libstd/cell.rs b/src/libstd/cell.rs
index 62fc08fd9d3..eb7d62b7bd3 100644
--- a/src/libstd/cell.rs
+++ b/src/libstd/cell.rs
@@ -13,19 +13,22 @@
 use prelude::*;
 use cast;
 use util::NonCopyable;
+use kinds::{marker,Pod};
 
 /// A mutable memory location that admits only `Pod` data.
-#[no_freeze]
-#[deriving(Clone)]
 pub struct Cell<T> {
     priv value: T,
+    priv marker1: marker::InvariantType<T>,
+    priv marker2: marker::NoFreeze,
 }
 
-impl<T: ::kinds::Pod> Cell<T> {
+impl<T:Pod> Cell<T> {
     /// Creates a new `Cell` containing the given value.
     pub fn new(value: T) -> Cell<T> {
         Cell {
             value: value,
+            marker1: marker::InvariantType::<T>,
+            marker2: marker::NoFreeze,
         }
     }
 
@@ -44,12 +47,19 @@ impl<T: ::kinds::Pod> Cell<T> {
     }
 }
 
+impl<T:Pod> Clone for Cell<T> {
+    fn clone(&self) -> Cell<T> {
+        Cell::new(self.get())
+    }
+}
+
 /// A mutable memory location with dynamically checked borrow rules
-#[no_freeze]
 pub struct RefCell<T> {
     priv value: T,
     priv borrow: BorrowFlag,
-    priv nc: NonCopyable
+    priv nc: NonCopyable,
+    priv marker1: marker::InvariantType<T>,
+    priv marker2: marker::NoFreeze,
 }
 
 // Values [1, MAX-1] represent the number of `Ref` active
@@ -62,6 +72,8 @@ impl<T> RefCell<T> {
     /// Create a new `RefCell` containing `value`
     pub fn new(value: T) -> RefCell<T> {
         RefCell {
+            marker1: marker::InvariantType::<T>,
+            marker2: marker::NoFreeze,
             value: value,
             borrow: UNUSED,
             nc: NonCopyable
diff --git a/src/libstd/comm/mod.rs b/src/libstd/comm/mod.rs
index 7f8f74f1b64..7b1a6055542 100644
--- a/src/libstd/comm/mod.rs
+++ b/src/libstd/comm/mod.rs
@@ -230,6 +230,7 @@ use clone::Clone;
 use container::Container;
 use int;
 use iter::Iterator;
+use kinds::marker;
 use kinds::Send;
 use ops::Drop;
 use option::{Option, Some, None};
@@ -297,9 +298,11 @@ impl<T: Send> Consumer<T>{
 
 /// The receiving-half of Rust's channel type. This half can only be owned by
 /// one task
-#[no_freeze] // can't share ports in an arc
 pub struct Port<T> {
     priv queue: Consumer<T>,
+
+    // can't share in an arc
+    priv marker: marker::NoFreeze,
 }
 
 /// An iterator over messages received on a port, this iterator will block
@@ -311,17 +314,22 @@ pub struct Messages<'a, T> {
 
 /// The sending-half of Rust's channel type. This half can only be owned by one
 /// task
-#[no_freeze] // can't share chans in an arc
 pub struct Chan<T> {
     priv queue: spsc::Producer<T, Packet>,
+
+    // can't share in an arc
+    priv marker: marker::NoFreeze,
 }
 
 /// The sending-half of Rust's channel type. This half can be shared among many
 /// tasks by creating copies of itself through the `clone` method.
-#[no_freeze] // technically this implementation is shareable, but it shouldn't
-             // be required to be shareable in an arc
 pub struct SharedChan<T> {
     priv queue: mpsc::Producer<T, Packet>,
+
+    // can't share in an arc -- technically this implementation is
+    // shareable, but it shouldn't be required to be shareable in an
+    // arc
+    priv marker: marker::NoFreeze,
 }
 
 /// This enumeration is the list of the possible reasons that try_recv could not
@@ -545,7 +553,8 @@ impl<T: Send> Chan<T> {
         // maximum buffer size
         let (c, p) = spsc::queue(128, Packet::new());
         let c = SPSC(c);
-        (Port { queue: c }, Chan { queue: p })
+        (Port { queue: c, marker: marker::NoFreeze },
+         Chan { queue: p, marker: marker::NoFreeze })
     }
 
     /// Sends a value along this channel to be received by the corresponding
@@ -640,7 +649,8 @@ impl<T: Send> SharedChan<T> {
     pub fn new() -> (Port<T>, SharedChan<T>) {
         let (c, p) = mpsc::queue(Packet::new());
         let c = MPSC(c);
-        (Port { queue: c }, SharedChan { queue: p })
+        (Port { queue: c, marker: marker::NoFreeze },
+         SharedChan { queue: p, marker: marker::NoFreeze })
     }
 
     /// Equivalent method to `send` on the `Chan` type (using the same
@@ -706,7 +716,7 @@ impl<T: Send> SharedChan<T> {
 impl<T: Send> Clone for SharedChan<T> {
     fn clone(&self) -> SharedChan<T> {
         unsafe { (*self.queue.packet()).channels.fetch_add(1, SeqCst); }
-        SharedChan { queue: self.queue.clone() }
+        SharedChan { queue: self.queue.clone(), marker: marker::NoFreeze }
     }
 }
 
diff --git a/src/libstd/comm/select.rs b/src/libstd/comm/select.rs
index a0db70117aa..a369ecba86b 100644
--- a/src/libstd/comm/select.rs
+++ b/src/libstd/comm/select.rs
@@ -47,6 +47,7 @@
 use cast;
 use comm;
 use iter::Iterator;
+use kinds::marker;
 use kinds::Send;
 use ops::Drop;
 use option::{Some, None, Option};
@@ -77,12 +78,12 @@ macro_rules! select {
 
 /// The "port set" of the select interface. This structure is used to manage a
 /// set of ports which are being selected over.
-#[no_freeze]
-#[no_send]
 pub struct Select {
     priv head: *mut Packet,
     priv tail: *mut Packet,
     priv next_id: uint,
+    priv marker1: marker::NoSend,
+    priv marker2: marker::NoFreeze,
 }
 
 /// A handle to a port which is currently a member of a `Select` set of ports.
@@ -108,6 +109,8 @@ impl Select {
             head: 0 as *mut Packet,
             tail: 0 as *mut Packet,
             next_id: 1,
+            marker1: marker::NoSend,
+            marker2: marker::NoFreeze,
         }
     }
 
diff --git a/src/libstd/gc.rs b/src/libstd/gc.rs
index 9985a280fa5..8ec07290a31 100644
--- a/src/libstd/gc.rs
+++ b/src/libstd/gc.rs
@@ -18,6 +18,7 @@ collector is task-local so `Gc<T>` is not sendable.
 
 #[allow(experimental)];
 
+use kinds::marker;
 use kinds::Send;
 use clone::{Clone, DeepClone};
 use managed;
@@ -25,25 +26,26 @@ use managed;
 /// Immutable garbage-collected pointer type
 #[lang="gc"]
 #[cfg(not(test))]
-#[no_send]
 #[experimental = "Gc is currently based on reference-counting and will not collect cycles until \
                   task annihilation. For now, cycles need to be broken manually by using `Rc<T>` \
                   with a non-owning `Weak<T>` pointer. A tracing garbage collector is planned."]
 pub struct Gc<T> {
-    priv ptr: @T
+    priv ptr: @T,
+    priv marker: marker::NoSend,
 }
 
 #[cfg(test)]
 #[no_send]
 pub struct Gc<T> {
-    priv ptr: @T
+    priv ptr: @T,
+    priv marker: marker::NoSend,
 }
 
 impl<T: 'static> Gc<T> {
     /// Construct a new garbage-collected box
     #[inline]
     pub fn new(value: T) -> Gc<T> {
-        Gc { ptr: @value }
+        Gc { ptr: @value, marker: marker::NoSend }
     }
 
     /// Borrow the value contained in the garbage-collected box
@@ -63,7 +65,7 @@ impl<T> Clone for Gc<T> {
     /// Clone the pointer only
     #[inline]
     fn clone(&self) -> Gc<T> {
-        Gc{ ptr: self.ptr }
+        Gc{ ptr: self.ptr, marker: marker::NoSend }
     }
 }
 
diff --git a/src/libstd/kinds.rs b/src/libstd/kinds.rs
index 462a0f1b0c8..51e9e9b3864 100644
--- a/src/libstd/kinds.rs
+++ b/src/libstd/kinds.rs
@@ -46,3 +46,190 @@ pub trait Pod {
     // Empty.
 }
 
+/// Marker types are special types that are used with unsafe code to
+/// inform the compiler of special constraints. Marker types should
+/// only be needed when you are creating an abstraction that is
+/// implemented using unsafe code. In that case, you may want to embed
+/// some of the marker types below into your type.
+pub mod marker {
+
+    /// A marker type whose type parameter `T` is considered to be
+    /// covariant with respect to the type itself. This is (typically)
+    /// used to indicate that an instance of the type `T` is being stored
+    /// into memory and read from, even though that may not be apparent.
+    ///
+    /// For more information about variance, refer to this Wikipedia
+    /// article <http://en.wikipedia.org/wiki/Variance_%28computer_science%29>.
+    ///
+    /// *Note:* It is very unusual to have to add a covariant constraint.
+    /// If you are not sure, you probably want to use `InvariantType`.
+    ///
+    /// # Example
+    ///
+    /// Given a struct `S` that includes a type parameter `T`
+    /// but does not actually *reference* that type parameter:
+    ///
+    /// ```
+    /// struct S<T> { x: *() }
+    /// fn get<T>(s: &S<T>) -> T {
+    ///    unsafe {
+    ///        let x: *T = cast::transmute(s.x);
+    ///        *x
+    ///    }
+    /// }
+    /// ```
+    ///
+    /// The type system would currently infer that the value of
+    /// the type parameter `T` is irrelevant, and hence a `S<int>` is
+    /// a subtype of `S<~[int]>` (or, for that matter, `S<U>` for
+    /// for any `U`). But this is incorrect because `get()` converts the
+    /// `*()` into a `*T` and reads from it. Therefore, we should include the
+    /// a marker field `CovariantType<T>` to inform the type checker that
+    /// `S<T>` is a subtype of `S<U>` if `T` is a a subtype of `U`
+    /// (for example, `S<&'static int>` is a subtype of `S<&'a int>`
+    /// for some lifetime `'a`, but not the other way around).
+    #[lang="covariant_type"]
+    #[deriving(Eq,Clone)]
+    pub struct CovariantType<T>;
+
+    /// A marker type whose type parameter `T` is considered to be
+    /// contravariant with respect to the type itself. This is (typically)
+    /// used to indicate that an instance of the type `T` will be consumed
+    /// (but not read from), even though that may not be apparent.
+    ///
+    /// For more information about variance, refer to this Wikipedia
+    /// article <http://en.wikipedia.org/wiki/Variance_%28computer_science%29>.
+    ///
+    /// *Note:* It is very unusual to have to add a contravariant constraint.
+    /// If you are not sure, you probably want to use `InvariantType`.
+    ///
+    /// # Example
+    ///
+    /// Given a struct `S` that includes a type parameter `T`
+    /// but does not actually *reference* that type parameter:
+    ///
+    /// ```
+    /// struct S<T> { x: *() }
+    /// fn get<T>(s: &S<T>, v: T) {
+    ///    unsafe {
+    ///        let x: fn(T) = cast::transmute(s.x);
+    ///        x(v)
+    ///    }
+    /// }
+    /// ```
+    ///
+    /// The type system would currently infer that the value of
+    /// the type parameter `T` is irrelevant, and hence a `S<int>` is
+    /// a subtype of `S<~[int]>` (or, for that matter, `S<U>` for
+    /// for any `U`). But this is incorrect because `get()` converts the
+    /// `*()` into a `fn(T)` and then passes a value of type `T` to it.
+    ///
+    /// Supplying a `ContravariantType` marker would correct the
+    /// problem, because it would mark `S` so that `S<T>` is only a
+    /// subtype of `S<U>` if `U` is a subtype of `T`; given that the
+    /// function requires arguments of type `T`, it must also accept
+    /// arguments of type `U`, hence such a conversion is safe.
+    #[lang="contravariant_type"]
+    #[deriving(Eq,Clone)]
+    pub struct ContravariantType<T>;
+
+    /// A marker type whose type parameter `T` is considered to be
+    /// invariant with respect to the type itself. This is (typically)
+    /// used to indicate that instances of the type `T` may be read or
+    /// written, even though that may not be apparent.
+    ///
+    /// For more information about variance, refer to this Wikipedia
+    /// article <http://en.wikipedia.org/wiki/Variance_%28computer_science%29>.
+    ///
+    /// # Example
+    ///
+    /// The Cell type is an example which uses unsafe code to achieve
+    /// "interior" mutability:
+    ///
+    /// ```
+    /// struct Cell<T> { priv value: T }
+    /// ```
+    ///
+    /// The type system would infer that `value` is only read here and
+    /// never written, but in fact `Cell` uses unsafe code to achieve
+    /// interior mutability.
+    #[lang="invariant_type"]
+    #[deriving(Eq,Clone)]
+    pub struct InvariantType<T>;
+
+    /// As `CovariantType`, but for lifetime parameters. Using
+    /// `CovariantLifetime<'a>` indicates that it is ok to substitute
+    /// a *longer* lifetime for `'a` than the one you originally
+    /// started with (e.g., you could convert any lifetime `'foo` to
+    /// `'static`). You almost certainly want `ContravariantLifetime`
+    /// instead, or possibly `InvariantLifetime`. The only case where
+    /// it would be appropriate is that you have a (type-casted, and
+    /// hence hidden from the type system) function pointer with a
+    /// signature like `fn(&'a T)` (and no other uses of `'a`). In
+    /// this case, it is ok to substitute a larger lifetime for `'a`
+    /// (e.g., `fn(&'static T)`), because the function is only
+    /// becoming more selective in terms of what it accepts as
+    /// argument.
+    ///
+    /// For more information about variance, refer to this Wikipedia
+    /// article <http://en.wikipedia.org/wiki/Variance_%28computer_science%29>.
+    #[lang="covariant_lifetime"]
+    #[deriving(Eq,Clone)]
+    pub struct CovariantLifetime<'a>;
+
+    /// As `ContravariantType`, but for lifetime parameters. Using
+    /// `ContravariantLifetime<'a>` indicates that it is ok to
+    /// substitute a *shorter* lifetime for `'a` than the one you
+    /// originally started with (e.g., you could convert `'static` to
+    /// any lifetime `'foo`). This is appropriate for cases where you
+    /// have an unsafe pointer that is actually a pointer into some
+    /// memory with lifetime `'a`, and thus you want to limit the
+    /// lifetime of your data structure to `'a`. An example of where
+    /// this is used is the iterator for vectors.
+    ///
+    /// For more information about variance, refer to this Wikipedia
+    /// article <http://en.wikipedia.org/wiki/Variance_%28computer_science%29>.
+    #[lang="contravariant_lifetime"]
+    #[deriving(Eq,Clone)]
+    pub struct ContravariantLifetime<'a>;
+
+    /// As `InvariantType`, but for lifetime parameters. Using
+    /// `InvariantLifetime<'a>` indicates that it is not ok to
+    /// substitute any other lifetime for `'a` besides its original
+    /// value. This is appropriate for cases where you have an unsafe
+    /// pointer that is actually a pointer into memory with lifetime `'a`,
+    /// and this pointer is itself stored in an inherently mutable
+    /// location (such as a `Cell`).
+    #[lang="invariant_lifetime"]
+    #[deriving(Eq,Clone)]
+    pub struct InvariantLifetime<'a>;
+
+    /// A type which is considered "not freezable", meaning that
+    /// its contents could change even if stored in an immutable
+    /// context or it is the referent of an `&T` pointer. This is
+    /// typically embedded in other types, such as `Cell`.
+    #[lang="no_freeze_bound"]
+    #[deriving(Eq,Clone)]
+    pub struct NoFreeze;
+
+    /// A type which is considered "not sendable", meaning that it cannot
+    /// be safely sent between tasks, even if it is owned. This is
+    /// typically embedded in other types, such as `Gc`, to ensure that
+    /// their instances remain thread-local.
+    #[lang="no_send_bound"]
+    #[deriving(Eq,Clone)]
+    pub struct NoSend;
+
+    /// A type which is considered "not POD", meaning that it is not
+    /// implicitly copyable. This is typically embedded in other types to
+    /// ensure that they are never copied, even if they lack a destructor.
+    #[lang="no_pod_bound"]
+    #[deriving(Eq,Clone)]
+    pub struct NoPod;
+
+    /// A type which is considered managed by the GC. This is typically
+    /// embedded in other types.
+    #[lang="managed_bound"]
+    #[deriving(Eq,Clone)]
+    pub struct Managed;
+}
diff --git a/src/libstd/rand/mod.rs b/src/libstd/rand/mod.rs
index f9bd291fbf4..44962684300 100644
--- a/src/libstd/rand/mod.rs
+++ b/src/libstd/rand/mod.rs
@@ -69,6 +69,7 @@ use cast;
 use cmp::Ord;
 use container::Container;
 use iter::{Iterator, range};
+use kinds::marker;
 use local_data;
 use prelude::*;
 use str;
@@ -543,7 +544,6 @@ impl reseeding::Reseeder<StdRng> for TaskRngReseeder {
 static TASK_RNG_RESEED_THRESHOLD: uint = 32_768;
 type TaskRngInner = reseeding::ReseedingRng<StdRng, TaskRngReseeder>;
 /// The task-local RNG.
-#[no_send]
 pub struct TaskRng {
     // This points into TLS (specifically, it points to the endpoint
     // of a ~ stored in TLS, to make it robust against TLS moving
@@ -554,7 +554,8 @@ pub struct TaskRng {
     // The use of unsafe code here is OK if the invariants above are
     // satisfied; and it allows us to avoid (unnecessarily) using a
     // GC'd or RC'd pointer.
-    priv rng: *mut TaskRngInner
+    priv rng: *mut TaskRngInner,
+    priv marker: marker::NoSend,
 }
 
 // used to make space in TLS for a random number generator
@@ -581,9 +582,9 @@ pub fn task_rng() -> TaskRng {
 
             local_data::set(TASK_RNG_KEY, rng);
 
-            TaskRng { rng: ptr }
+            TaskRng { rng: ptr, marker: marker::NoSend }
         }
-        Some(rng) => TaskRng { rng: &mut **rng }
+        Some(rng) => TaskRng { rng: &mut **rng, marker: marker::NoSend }
     })
 }
 
diff --git a/src/libstd/rc.rs b/src/libstd/rc.rs
index fe82ac74069..7d0ddb2e4fb 100644
--- a/src/libstd/rc.rs
+++ b/src/libstd/rc.rs
@@ -27,6 +27,7 @@ use cast::transmute;
 use ops::Drop;
 use cmp::{Eq, Ord};
 use clone::{Clone, DeepClone};
+use kinds::marker;
 use rt::global_heap::exchange_free;
 use ptr::read_ptr;
 use option::{Option, Some, None};
@@ -39,16 +40,19 @@ struct RcBox<T> {
 
 /// Immutable reference counted pointer type
 #[unsafe_no_drop_flag]
-#[no_send]
 pub struct Rc<T> {
-    priv ptr: *mut RcBox<T>
+    priv ptr: *mut RcBox<T>,
+    priv marker: marker::NoSend
 }
 
 impl<T> Rc<T> {
     /// Construct a new reference-counted box
     pub fn new(value: T) -> Rc<T> {
         unsafe {
-            Rc { ptr: transmute(~RcBox { value: value, strong: 1, weak: 0 }) }
+            Rc {
+                ptr: transmute(~RcBox { value: value, strong: 1, weak: 0 }),
+                marker: marker::NoSend,
+            }
         }
     }
 }
@@ -64,7 +68,7 @@ impl<T> Rc<T> {
     pub fn downgrade(&self) -> Weak<T> {
         unsafe {
             (*self.ptr).weak += 1;
-            Weak { ptr: self.ptr }
+            Weak { ptr: self.ptr, marker: marker::NoSend }
         }
     }
 }
@@ -91,7 +95,7 @@ impl<T> Clone for Rc<T> {
     fn clone(&self) -> Rc<T> {
         unsafe {
             (*self.ptr).strong += 1;
-            Rc { ptr: self.ptr }
+            Rc { ptr: self.ptr, marker: marker::NoSend }
         }
     }
 }
@@ -127,9 +131,9 @@ impl<T: Ord> Ord for Rc<T> {
 
 /// Weak reference to a reference-counted box
 #[unsafe_no_drop_flag]
-#[no_send]
 pub struct Weak<T> {
-    priv ptr: *mut RcBox<T>
+    priv ptr: *mut RcBox<T>,
+    priv marker: marker::NoSend
 }
 
 impl<T> Weak<T> {
@@ -140,7 +144,7 @@ impl<T> Weak<T> {
                 None
             } else {
                 (*self.ptr).strong += 1;
-                Some(Rc { ptr: self.ptr })
+                Some(Rc { ptr: self.ptr, marker: marker::NoSend })
             }
         }
     }
@@ -165,7 +169,7 @@ impl<T> Clone for Weak<T> {
     fn clone(&self) -> Weak<T> {
         unsafe {
             (*self.ptr).weak += 1;
-            Weak { ptr: self.ptr }
+            Weak { ptr: self.ptr, marker: marker::NoSend }
         }
     }
 }
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 467bcf075f6..bdb6077f984 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -117,6 +117,7 @@ use ptr::RawPtr;
 use rt::global_heap::{malloc_raw, realloc_raw, exchange_free};
 use mem;
 use mem::size_of;
+use kinds::marker;
 use uint;
 use unstable::finally::Finally;
 use unstable::intrinsics;
@@ -1055,12 +1056,12 @@ impl<'a,T> ImmutableVector<'a, T> for &'a [T] {
             let p = self.as_ptr();
             if mem::size_of::<T>() == 0 {
                 Items{ptr: p,
-                            end: (p as uint + self.len()) as *T,
-                            lifetime: None}
+                      end: (p as uint + self.len()) as *T,
+                      marker: marker::ContravariantLifetime::<'a>}
             } else {
                 Items{ptr: p,
-                            end: p.offset(self.len() as int),
-                            lifetime: None}
+                      end: p.offset(self.len() as int),
+                      marker: marker::ContravariantLifetime::<'a>}
             }
         }
     }
@@ -2281,12 +2282,12 @@ impl<'a,T> MutableVector<'a, T> for &'a mut [T] {
             let p = self.as_mut_ptr();
             if mem::size_of::<T>() == 0 {
                 MutItems{ptr: p,
-                               end: (p as uint + self.len()) as *mut T,
-                               lifetime: None}
+                         end: (p as uint + self.len()) as *mut T,
+                         marker: marker::ContravariantLifetime::<'a>}
             } else {
                 MutItems{ptr: p,
-                               end: p.offset(self.len() as int),
-                               lifetime: None}
+                         end: p.offset(self.len() as int),
+                         marker: marker::ContravariantLifetime::<'a>}
             }
         }
     }
@@ -2638,7 +2639,7 @@ macro_rules! iterator {
         pub struct $name<'a, T> {
             priv ptr: $ptr,
             priv end: $ptr,
-            priv lifetime: Option<$elem> // FIXME: #5922
+            priv marker: marker::ContravariantLifetime<'a>,
         }
 
         impl<'a, T> Iterator<$elem> for $name<'a, T> {
diff --git a/src/test/compile-fail/marker-no-freeze.rs b/src/test/compile-fail/marker-no-freeze.rs
new file mode 100644
index 00000000000..85f4f4fefd4
--- /dev/null
+++ b/src/test/compile-fail/marker-no-freeze.rs
@@ -0,0 +1,18 @@
+// Copyright 2013 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::kinds::marker;
+
+fn foo<P:Freeze>(p: P) { }
+
+fn main()
+{
+    foo(marker::NoFreeze); //~ ERROR does not fulfill `Freeze`
+}
diff --git a/src/test/compile-fail/marker-no-pod.rs b/src/test/compile-fail/marker-no-pod.rs
new file mode 100644
index 00000000000..90b277a7432
--- /dev/null
+++ b/src/test/compile-fail/marker-no-pod.rs
@@ -0,0 +1,18 @@
+// Copyright 2013 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::kinds::marker;
+
+fn foo<P:Pod>(p: P) { }
+
+fn main()
+{
+    foo(marker::NoPod); //~ ERROR does not fulfill `Pod`
+}
diff --git a/src/test/compile-fail/marker-no-send.rs b/src/test/compile-fail/marker-no-send.rs
new file mode 100644
index 00000000000..101959035eb
--- /dev/null
+++ b/src/test/compile-fail/marker-no-send.rs
@@ -0,0 +1,18 @@
+// Copyright 2013 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::kinds::marker;
+
+fn foo<P:Send>(p: P) { }
+
+fn main()
+{
+    foo(marker::NoSend); //~ ERROR does not fulfill `Send`
+}
diff --git a/src/test/compile-fail/mutable-enum-indirect.rs b/src/test/compile-fail/mutable-enum-indirect.rs
index 9fad05387c6..0e14de61ff7 100644
--- a/src/test/compile-fail/mutable-enum-indirect.rs
+++ b/src/test/compile-fail/mutable-enum-indirect.rs
@@ -1,12 +1,13 @@
 // Tests that an `&` pointer to something inherently mutable is itself
 // to be considered mutable.
 
-#[no_freeze]
-enum Foo { A }
+use std::kinds::marker;
+
+enum Foo { A(marker::NoFreeze) }
 
 fn bar<T: Freeze>(_: T) {}
 
 fn main() {
-    let x = A;
+    let x = A(marker::NoFreeze);
     bar(&x); //~ ERROR type parameter with an incompatible type
 }
diff --git a/src/test/compile-fail/no_freeze-enum.rs b/src/test/compile-fail/no_freeze-enum.rs
index 35842a53a31..9b7189d02bb 100644
--- a/src/test/compile-fail/no_freeze-enum.rs
+++ b/src/test/compile-fail/no_freeze-enum.rs
@@ -8,12 +8,13 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-#[no_freeze]
-enum Foo { A }
+use std::kinds::marker;
+
+enum Foo { A(marker::NoFreeze) }
 
 fn bar<T: Freeze>(_: T) {}
 
 fn main() {
-    let x = A;
+    let x = A(marker::NoFreeze);
     bar(x); //~ ERROR instantiating a type parameter with an incompatible type `Foo`, which does not fulfill `Freeze`
 }
diff --git a/src/test/compile-fail/no_freeze-struct.rs b/src/test/compile-fail/no_freeze-struct.rs
index 6f29fcfd96d..9ac7966e704 100644
--- a/src/test/compile-fail/no_freeze-struct.rs
+++ b/src/test/compile-fail/no_freeze-struct.rs
@@ -8,12 +8,13 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-#[no_freeze]
-struct Foo { a: int }
+use std::kinds::marker;
+
+struct Foo { a: int, m: marker::NoFreeze }
 
 fn bar<T: Freeze>(_: T) {}
 
 fn main() {
-    let x = Foo { a: 5 };
+    let x = Foo { a: 5, m: marker::NoFreeze };
     bar(x); //~ ERROR instantiating a type parameter with an incompatible type `Foo`, which does not fulfill `Freeze`
 }
diff --git a/src/test/compile-fail/no_send-enum.rs b/src/test/compile-fail/no_send-enum.rs
index b436bfb8b0f..7a5ad743d21 100644
--- a/src/test/compile-fail/no_send-enum.rs
+++ b/src/test/compile-fail/no_send-enum.rs
@@ -8,12 +8,15 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-#[no_send]
-enum Foo { A }
+use std::kinds::marker;
+
+enum Foo {
+    A(marker::NoSend)
+}
 
 fn bar<T: Send>(_: T) {}
 
 fn main() {
-    let x = A;
+    let x = A(marker::NoSend);
     bar(x); //~ ERROR instantiating a type parameter with an incompatible type `Foo`, which does not fulfill `Send`
 }
diff --git a/src/test/compile-fail/no_send-struct.rs b/src/test/compile-fail/no_send-struct.rs
index 542c3aa212b..7617602cbfb 100644
--- a/src/test/compile-fail/no_send-struct.rs
+++ b/src/test/compile-fail/no_send-struct.rs
@@ -8,12 +8,16 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-#[no_send]
-struct Foo { a: int }
+use std::kinds::marker;
+
+struct Foo {
+    a: int,
+    ns: marker::NoSend
+}
 
 fn bar<T: Send>(_: T) {}
 
 fn main() {
-    let x = Foo { a: 5 };
+    let x = Foo { a: 5, ns: marker::NoSend };
     bar(x); //~ ERROR instantiating a type parameter with an incompatible type `Foo`, which does not fulfill `Send`
 }
diff --git a/src/test/compile-fail/regions-infer-contravariance-due-to-decl.rs b/src/test/compile-fail/regions-infer-contravariance-due-to-decl.rs
new file mode 100644
index 00000000000..d3e9c1f6ea8
--- /dev/null
+++ b/src/test/compile-fail/regions-infer-contravariance-due-to-decl.rs
@@ -0,0 +1,39 @@
+// Copyright 2012 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.
+
+// Test that a type which is contravariant with respect to its region
+// parameter yields an error when used in a covariant way.
+//
+// Note: see variance-regions-*.rs for the tests that check that the
+// variance inference works in the first place.
+
+use std::kinds::marker;
+
+// This is contravariant with respect to 'a, meaning that
+// Contravariant<'foo> <: Contravariant<'static> because
+// 'foo <= 'static
+struct Contravariant<'a> {
+    marker: marker::ContravariantLifetime<'a>
+}
+
+fn use_<'short,'long>(c: Contravariant<'short>,
+                      s: &'short int,
+                      l: &'long int,
+                      _where:Option<&'short &'long ()>) {
+
+    // Test whether Contravariant<'short> <: Contravariant<'long>.  Since
+    // 'short <= 'long, this would be true if the Contravariant type were
+    // covariant with respect to its parameter 'a.
+
+    let _: Contravariant<'long> = c; //~ ERROR mismatched types
+    //~^ ERROR  cannot infer an appropriate lifetime
+}
+
+fn main() {}
diff --git a/src/test/compile-fail/regions-infer-covariance-due-to-decl.rs b/src/test/compile-fail/regions-infer-covariance-due-to-decl.rs
new file mode 100644
index 00000000000..2d3ca173012
--- /dev/null
+++ b/src/test/compile-fail/regions-infer-covariance-due-to-decl.rs
@@ -0,0 +1,36 @@
+// Copyright 2012 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.
+
+// Test that a type which is covariant with respect to its region
+// parameter yields an error when used in a contravariant way.
+//
+// Note: see variance-regions-*.rs for the tests that check that the
+// variance inference works in the first place.
+
+use std::kinds::marker;
+
+struct Covariant<'a> {
+    marker: marker::CovariantLifetime<'a>
+}
+
+fn use_<'short,'long>(c: Covariant<'long>,
+                      s: &'short int,
+                      l: &'long int,
+                      _where:Option<&'short &'long ()>) {
+
+    // Test whether Covariant<'long> <: Covariant<'short>.  Since
+    // 'short <= 'long, this would be true if the Covariant type were
+    // contravariant with respect to its parameter 'a.
+
+    let _: Covariant<'short> = c; //~ ERROR mismatched types
+    //~^ ERROR  cannot infer an appropriate lifetime
+}
+
+fn main() {}
diff --git a/src/test/compile-fail/regions-infer-invariance-due-to-decl.rs b/src/test/compile-fail/regions-infer-invariance-due-to-decl.rs
new file mode 100644
index 00000000000..ad5ad143b15
--- /dev/null
+++ b/src/test/compile-fail/regions-infer-invariance-due-to-decl.rs
@@ -0,0 +1,26 @@
+// Copyright 2012 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::kinds::marker;
+
+struct invariant<'a> {
+    marker: marker::InvariantLifetime<'a>
+}
+
+fn to_same_lifetime<'r>(bi: invariant<'r>) {
+    let bj: invariant<'r> = bi;
+}
+
+fn to_longer_lifetime<'r>(bi: invariant<'r>) -> invariant<'static> {
+    bi //~ ERROR mismatched types
+}
+
+fn main() {
+}
diff --git a/src/test/compile-fail/variance-cell-is-invariant.rs b/src/test/compile-fail/variance-cell-is-invariant.rs
new file mode 100644
index 00000000000..0efca74f3ce
--- /dev/null
+++ b/src/test/compile-fail/variance-cell-is-invariant.rs
@@ -0,0 +1,28 @@
+// Copyright 2012 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.
+
+// Test that Cell is considered invariant with respect to its
+// type.
+
+use std::cell::Cell;
+
+struct Foo<'a> {
+    x: Cell<Option<&'a int>>,
+}
+
+fn use_<'short,'long>(c: Foo<'short>,
+                      s: &'short int,
+                      l: &'long int,
+                      _where:Option<&'short &'long ()>) {
+    let _: Foo<'long> = c; //~ ERROR mismatched types
+}
+
+fn main() {
+}
diff --git a/src/test/run-pass/cell-does-not-clone.rs b/src/test/run-pass/cell-does-not-clone.rs
new file mode 100644
index 00000000000..97310fd9ad2
--- /dev/null
+++ b/src/test/run-pass/cell-does-not-clone.rs
@@ -0,0 +1,31 @@
+// 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::cell::Cell;
+
+struct Foo {
+    x: int
+}
+
+impl Clone for Foo {
+    fn clone(&self) -> Foo {
+        // Using Cell in any way should never cause clone() to be
+        // invoked -- after all, that would permit evil user code to
+        // abuse `Cell` and trigger crashes.
+
+        fail!();
+    }
+}
+
+pub fn main() {
+    let x = Cell::new(Foo { x: 22 });
+    let _y = x.get();
+    let _z = x.clone();
+}
diff --git a/src/test/run-pass/regions-infer-bivariance.rs b/src/test/run-pass/regions-infer-bivariance.rs
new file mode 100644
index 00000000000..8b9d6af1017
--- /dev/null
+++ b/src/test/run-pass/regions-infer-bivariance.rs
@@ -0,0 +1,28 @@
+// Copyright 2012 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.
+
+// Test that a type whose lifetime parameters is never used is
+// inferred to be bivariant.
+
+use std::kinds::marker;
+
+struct Bivariant<'a>;
+
+fn use1<'short,'long>(c: Bivariant<'short>,
+                      _where:Option<&'short &'long ()>) {
+    let _: Bivariant<'long> = c;
+}
+
+fn use2<'short,'long>(c: Bivariant<'long>,
+                      _where:Option<&'short &'long ()>) {
+    let _: Bivariant<'short> = c;
+}
+
+pub fn main() {}