auto merge of #11768 : nikomatsakis/rust/issue-11385-cell-and-variance, r=pnkfelix

Introduce marker types for indicating variance and for opting out
of builtin bounds.

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

r? @pnkfelix (since you reviewed the variance inference in the first place)

9 files changed, 264 insertions, 43 deletions

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> {