我是否错误地实现了IntoIterator以引用LazyList实现，或者这是一个Rust错误？

Question

在实现一个LazyList的版本（一个不可变的懒惰计算memoized单链表，与Haskell列表一样），我遇到了一个执行IntoIterator的问题，因为代码在我认为它应该。以下代码已被简化以便显示问题;因此，不是通用的，不包括所有的不相关的实施IntoIterator方法：

use std::cell::UnsafeCell; 
use std::mem::replace; 
use std::rc::Rc; 

// only necessary because Box<FnOnce() -> R> doesn't yet work... 
trait Invoke<R =()> { 
    fn invoke(self: Box<Self>) -> R; 
} 

impl<'a, R, F: 'a + FnOnce() -> R> Invoke<R> for F { 
    #[inline(always)] 
    fn invoke(self: Box<F>) -> R { 
     (*self)() 
    } 
} 

// not thread safe 
struct Lazy<'a, T: 'a>(UnsafeCell<LazyState<'a, T>>); 

enum LazyState<'a, T: 'a> { 
    Unevaluated(Box<Invoke<T> + 'a>), 
    EvaluationInProgress, 
    Evaluated(T), 
} 

use self::LazyState::*; 

impl<'a, T: 'a> Lazy<'a, T> { 
    #[inline] 
    fn new<F: 'a + FnOnce() -> T>(func: F) -> Lazy<'a, T> { 
     Lazy(UnsafeCell::new(Unevaluated(Box::new(func)))) 
    } 
    #[inline] 
    pub fn evaluated(val: T) -> Lazy<'a, T> { 
     Lazy(UnsafeCell::new(Evaluated(val))) 
    } 
    #[inline] 
    fn value(&'a self) -> &'a T { 
     unsafe { 
      match *self.0.get() { 
       Evaluated(_) =>(), // nothing required; already Evaluated 
       EvaluationInProgress => panic!("Lazy::force called recursively!!!"), 
       _ => { 
        let ue = replace(&mut *self.0.get(), EvaluationInProgress); 
        if let Unevaluated(thnk) = ue { 
         *self.0.get() = Evaluated(thnk.invoke()); 
        } // no other possiblity! 
       } 
      } // following just gets evaluated, no other state possible 
      if let Evaluated(ref v) = *self.0.get() { 
       return v; 
      } else { 
       unreachable!(); 
      } 
     } 
    } 
} 

enum LazyList<'a> { 
    Empty, 
    Cons(i32, RcLazyListNode<'a>), 
} 

type RcLazyListNode<'a> = Rc<Lazy<'a, LazyList<'a>>>; 

impl<'a> LazyList<'a> { 
    fn iter(&self) -> Iter<'a> { 
     Iter(self) 
    } 
} 

struct Iter<'a>(*const LazyList<'a>); 

impl<'a> Iterator for Iter<'a> { 
    type Item = &'a i32; 

    fn next(&mut self) -> Option<Self::Item> { 
     unsafe { 
      if let LazyList::Cons(ref v, ref r) = *self.0 { 
       self.0 = r.value(); 
       Some(v) 
      } else { 
       None 
      } 
     } 
    } 
} 

impl<'a> IntoIterator for &'a LazyList<'a> { 
    type Item = &'a i32; 
    type IntoIter = Iter<'a>; 

    fn into_iter(self) -> Self::IntoIter { 
     self.iter() 
    } 
} 

fn main() { 
    let test2 = LazyList::Cons(2, Rc::new(Lazy::evaluated(LazyList::Empty))); 
    let test = LazyList::Cons(1, Rc::new(Lazy::new(move || test2))); 
    // let itr = Iter(&test); // works 
    // let itr = (&test).iter(); // works 
    let itr = IntoIterator::into_iter(&test); // not working 
    for v in itr { 
     println!("{}", v); 
    } 
} 

上面的代码失败：

rustc 1.13.0 (2c6933acc 2016-11-07) 
error: `test` does not live long enough 
    --> <anon>:103:40 
    | 
103 |  let itr = IntoIterator::into_iter(&test); // not working 
    |          ^^^^ does not live long enough 
... 
107 | } 
    | - borrowed value dropped before borrower 
    | 
    = note: values in a scope are dropped in the opposite order they are created 

如在main()的评论指出，代码除了通过IntoIterator trait作为参考被调用时，除非可以使用。这可能是实现引用的特征时的一个错误，其中包含指针的返回迭代器的所有权不会传递到与调用IntoIterator::into_iter相同的作用域，而是传递到'static生命周期，因此它在预期时不会丢失。

如果可能，我该如何执行此操作？我尝试在Iter结构中添加一个std::marker::PhantomData<>标记字段，但它似乎也被分配了一个'static生命周期。

Answer 1

当你实现IntoIterator，你统一参考列表，该列表包含了项目之间的寿命：

impl<'a> IntoIterator for &'a LazyList<'a> 

这需要'a必须寿命的缩短。这在这种情况下没有用。相反，你需要有两个不同的寿命：

impl<'l, 'i> IntoIterator for &'l LazyList<'i> { 
    type Item = &'i i32; 
    type IntoIter = Iter<'i>; 

    fn into_iter(self) -> Self::IntoIter { 
     self.iter() 
    } 
} 

Answer 2

对于那些谁通过搜索除锈，懒惰，和LazyList发现这个问题，我在这里发表的懒惰和LazyList最终通用工作代码与两个非和线程与当前稳定的Rust版本1.13一起工作的安全版本。因为我们不能使用嵌入在另一种类型中的类型（除非我们替换内部可变值）;因为我们不能使用嵌入另一种类型的类型（除非我们替换内部可变值），因此，这些方法在这里没有用处。需要为singleton()方法，unwrap()方法和tail()方法设计更多的测试。

因为我们通常不能解包，所以嵌入类型必须是Clone;这会在涉及的复制操作中花费一些性能，所以当类型很大时（复制），可能需要将它们包装在Rc中以便快速参考 - 计数克隆。

的代码如下：

// only necessary because Box<FnOnce() -> R> doesn't work... 
mod thunk { 
    pub trait Invoke<R =()> { 
     fn invoke(self: Box<Self>) -> R; 
    } 

    impl<R, F: FnOnce() -> R> Invoke<R> for F { 
     #[inline(always)] 
     fn invoke(self: Box<F>) -> R { (*self)() } 
    } 
} 

// Lazy is lazily evaluated contained value using the above Invoke trait 
// instead of the desire Box<FnOnce() -> T> or a stable FnBox (currently not)... 
mod lazy { 
    use thunk::Invoke; 
    use std::cell::UnsafeCell; 
    use std::mem::replace; 
    use std::ops::Deref; 

    // Lazy is lazily evaluated contained value using the above Invoke trait 
    // instead of the desire Box<FnOnce() -> T> or a stable FnBox (currently not)... 
    pub struct Lazy<'a, T: 'a>(UnsafeCell<LazyState<'a, T>>); 

    enum LazyState<'a, T: 'a> { 
     Unevaluated(Box<Invoke<T> + 'a>), 
     EvaluationInProgress, 
     Evaluated(T), 
    } 

    use self::LazyState::*; 

// impl<'a, T:'a> !Sync for Lazy<'a, T> {} 

    impl<'a, T: 'a> Lazy<'a, T> { 
     #[inline] 
     pub fn new<F: 'a + FnOnce() -> T>(func: F) -> Lazy<'a, T> { 
      Lazy(UnsafeCell::new(Unevaluated(Box::new(func)))) 
     } 
     #[inline] 
     pub fn evaluated(val: T) -> Lazy<'a, T> { 
      Lazy(UnsafeCell::new(Evaluated(val))) 
     } 
     #[inline(always)] 
     fn force<'b>(&'b self) { 
      unsafe { 
       match *self.0.get() { 
        Evaluated(_) => return, // nothing required; already Evaluated 
        EvaluationInProgress => panic!("Lazy::force called recursively!!!"), 
        _ => { 
         let ue = replace(&mut *self.0.get(), EvaluationInProgress); 
         if let Unevaluated(thnk) = ue { 
          *self.0.get() = Evaluated(thnk.invoke()); 
         } // no other possiblity! 
        } 
       } 
      } 
     } 
     #[inline] 
     pub fn unwrap<'b>(self) -> T where T: 'b { // consumes the object to produce the value 
      self.force(); // evaluatate if not evealutated 
      match unsafe { self.0.into_inner() } { 
       Evaluated(v) => v, 
       _ => unreachable!() // previous code guarantees never not Evaluated 
      } 
     } 
    } 

    impl<'a, T: 'a> Deref for Lazy<'a, T> { 
     type Target = T; 
     #[inline] 
     fn deref<'b>(&'b self) -> &'b T { 
      self.force(); // evaluatate if not evalutated 
      match unsafe { &*self.0.get() } { 
       &Evaluated(ref v) => return v, 
       _ => unreachable!(), 
      } 
     } 
    } 
} 

mod lazy_sync { 
    use thunk::Invoke; 
    use std::cell::UnsafeCell; 
    use std::mem::replace; 
    use std::sync::Mutex; 
    use std::sync::atomic::AtomicBool; 
    use std::sync::atomic::Ordering::Relaxed; 
    use std::ops::Deref; 

    pub struct Lazy<'a, T: 'a + Send + Sync>(
     UnsafeCell<LazyState<'a, T>>, AtomicBool, Mutex<()>); 

    enum LazyState<'a, T: 'a + Send + Sync> { 
     Unevaluated(Box<Invoke<T> + 'a>), 
     EvaluationInProgress, 
     Evaluated(T), 
    } 

    use self::LazyState::*; 

    unsafe impl<'a, T: 'a + Send + Sync> Send for Lazy<'a, T> {} 
    unsafe impl<'a, T: 'a + Send + Sync> Sync for Lazy<'a, T> {} 

    impl<'a, T: 'a + Send + Sync> Lazy<'a, T> { 
     #[inline] 
     pub fn new<F: 'a + FnOnce() -> T>(func: F) -> Lazy<'a, T> { 
      Lazy(UnsafeCell::new(Unevaluated(Box::new(func))), 
       AtomicBool::new(false), Mutex::new(())) 
     } 
     #[inline] 
     pub fn evaluated(val: T) -> Lazy<'a, T> { 
      Lazy(UnsafeCell::new(Evaluated(val)), 
       AtomicBool::new(true), Mutex::new(())) 
     } 
     #[inline(always)] 
     fn force<'b>(&'b self) { 
      unsafe { 
      if !self.1.load(Relaxed) { 
       let _ = self.2.lock(); 
       // if we don't get the false below, means 
       // another thread already handled the thunk, 
       // including setting to true, still processing when checked 
       if !self.1.load(Relaxed) { 
        match *self.0.get() { 
         Evaluated(_) => return, // nothing required; already Evaluated 
         EvaluationInProgress => unreachable!(), // because lock race recursive evals... 
         _ => { 
          if let Unevaluated(thnk) = replace(&mut *self.0.get(), EvaluationInProgress) { 
           *self.0.get() = Evaluated(thnk.invoke()); 
          } // no other possiblity! 
         } 
        } 
        self.1.store(true, Relaxed); 
       } 
      } 
      } 
     } 

     #[inline] 
     pub fn unwrap<'b>(self) -> T where T: 'b { // consumes the object to produce the value 
      self.force(); // evaluatate if not evealutated 
      match unsafe { self.0.into_inner() } { 
       Evaluated(v) => v, 
       _ => unreachable!() // previous code guarantees never not Evaluated 
      } 
     } 
    } 

    impl<'a, T: 'a + Send + Sync> Deref for Lazy<'a, T> { 
     type Target = T; 
     #[inline] 
     fn deref<'b>(&'b self) -> &'b T { 
      self.force(); // evaluatate if not evalutated 
       match unsafe { &*self.0.get() } { 
        &Evaluated(ref v) => return v, 
        _ => unreachable!(), 
       } 
     } 
    } 
} 

// LazyList is an immutable lazily-evaluated persistent (memoized) singly-linked list 
// similar to lists in Haskell, although here only tails are lazy... 
// depends on the contained type being Clone so that the LazyList can be 
// extracted from the reference-counted Rc heap objects in which embedded. 
mod lazylist { 
    use lazy::Lazy; 
    use std::rc::Rc; 
    use std::iter::FromIterator; 
    use std::mem::{replace, swap}; 

    #[derive(Clone)] 
    pub enum LazyList<'a, T: 'a + Clone> { 
     Empty, 
     Cons(T, RcLazyListNode<'a, T>), 
    } 

    pub use self::LazyList::Empty; 
    use self::LazyList::Cons; 

    type RcLazyListNode<'a, T: 'a> = Rc<Lazy<'a, LazyList<'a, T>>>; 

// impl<'a, T:'a> !Sync for LazyList<'a, T> {} 

    impl<'a, T: 'a + Clone> LazyList<'a, T> { 
     #[inline] 
     pub fn singleton(v: T) -> LazyList<'a, T> { 
      Cons(v, Rc::new(Lazy::evaluated(Empty))) 
     } 
     #[inline] 
     pub fn cons<F>(v: T, cntf: F) -> LazyList<'a, T> 
      where F: 'a + FnOnce() -> LazyList<'a, T> 
     { 
      Cons(v, Rc::new(Lazy::new(cntf))) 
     } 
     #[inline] 
     pub fn head<'b>(&'b self) -> &'b T { 
      if let Cons(ref hd, _) = *self { 
       return hd; 
      } 
      panic!("LazyList::head called on an Empty LazyList!!!") 
     } 
     #[inline] 
     pub fn tail<'b>(&'b self) -> &'b Lazy<'a, LazyList<'a, T>> { 
      if let Cons(_, ref rlln) = *self { 
       return &*rlln; 
      } 
      panic!("LazyList::tail called on an Empty LazyList!!!") 
     } 
     #[inline] 
     pub fn unwrap(self) -> (T, RcLazyListNode<'a, T>) { 
      // consumes the object 
      if let Cons(hd, rlln) = self { 
       return (hd, rlln); 
      } 
      panic!("LazyList::unwrap called on an Empty LazyList!!!") 
     } 
     #[inline] 
     fn iter(&self) -> Iter<'a, T> { 
      Iter(self) 
     } 
    } 

    impl<'a, T: 'a + Clone> Iterator for LazyList<'a, T> { 
     type Item = T; 

     fn next(&mut self) -> Option<Self::Item> { 
      match replace(self, Empty) { 
       Cons(hd, rlln) => { 
        let mut newll = (*rlln).clone(); 
        swap(self, &mut newll); // self now contains tail, newll contains the Empty 
        Some(hd) 
       } 
       _ => None, 
      } 
     } 
    } 

    pub struct Iter<'a, T: 'a + Clone>(*const LazyList<'a, T>); 

    impl<'a, T: 'a + Clone> Iterator for Iter<'a, T> { 
     type Item = &'a T; 

     fn next(&mut self) -> Option<Self::Item> { 
      unsafe { 
       if let LazyList::Cons(ref v, ref r) = *self.0 { 
        self.0 = &***r; 
        Some(v) 
       } else { 
        None 
       } 
      } 
     } 
    } 

    impl<'i, 'l, T: 'i + Clone> IntoIterator for &'l LazyList<'i, T> { 
     type Item = &'i T; 
     type IntoIter = Iter<'i, T>; 

     fn into_iter(self) -> Self::IntoIter { 
      self.iter() 
     } 
    } 

    impl<'a, T: 'a + Clone> FromIterator<T> for LazyList<'a, T> { 
     fn from_iter<I: IntoIterator<Item = T> + 'a>(itrbl: I) -> LazyList<'a, T> { 
      let itr = itrbl.into_iter(); 
      #[inline(always)] 
      fn next_iter<'b, R, Itr>(mut iter: Itr) -> LazyList<'b, R> 
       where R: 'b + Clone, 
         Itr: 'b + Iterator<Item = R> 
      { 
       match iter.next() { 
        Some(val) => LazyList::cons(val, move || next_iter(iter)), 
        None => Empty, 
       } 
      } 
      next_iter(itr) 
     } 
    } 

} 

mod lazylist_sync { 
    use lazy_sync::Lazy; 
    use std::sync::Arc as Rc; 
    use std::iter::FromIterator; 
    use std::mem::{replace, swap}; 

    #[derive(Clone)] 
    pub enum LazyList<'a, T: 'a + Send + Sync + Clone> { 
     Empty, 
     Cons(T, RcLazyListNode<'a, T>), 
    } 

    pub use self::LazyList::Empty; 
    use self::LazyList::Cons; 

    type RcLazyListNode<'a, T: 'a> = Rc<Lazy<'a, LazyList<'a, T>>>; 

    unsafe impl<'a, T: 'a + Send + Sync + Clone> Send for LazyList<'a, T> {} 
    unsafe impl<'a, T: 'a + Send + Sync + Clone> Sync for LazyList<'a, T> {} 

    impl<'a, T: 'a + Send + Sync + Clone> LazyList<'a, T> { 
     #[inline] 
     pub fn singleton(v: T) -> LazyList<'a, T> { 
      Cons(v, Rc::new(Lazy::evaluated(Empty))) 
     } 
     #[inline] 
     pub fn cons<F>(v: T, cntf: F) -> LazyList<'a, T> 
      where F: 'a + FnOnce() -> LazyList<'a, T> 
     { 
      Cons(v, Rc::new(Lazy::new(cntf))) 
     } 
     #[inline] 
     pub fn head<'b>(&'b self) -> &'b T { 
      if let Cons(ref hd, _) = *self { 
       return hd; 
      } 
      panic!("LazyList::head called on an Empty LazyList!!!") 
     } 
     #[inline] 
     pub fn tail<'b>(&'b self) -> &'b Lazy<'a, LazyList<'a, T>> { 
      if let Cons(_, ref rlln) = *self { 
       return &*rlln; 
      } 
      panic!("LazyList::tail called on an Empty LazyList!!!") 
     } 
     #[inline] 
     pub fn unwrap(self) -> (T, RcLazyListNode<'a, T>) { 
      // consumes the object 
      if let Cons(hd, rlln) = self { 
       return (hd, rlln); 
      } 
      panic!("LazyList::unwrap called on an Empty LazyList!!!") 
     } 
     #[inline] 
     fn iter(&self) -> Iter<'a, T> { 
      Iter(self) 
     } 
    } 

    impl<'a, T: 'a + Send + Sync + Clone> Iterator for LazyList<'a, T> { 
     type Item = T; 

     fn next(&mut self) -> Option<Self::Item> { 
      match replace(self, Empty) { 
       Cons(hd, rlln) => { 
        let mut newll = (*rlln).clone(); 
        swap(self, &mut newll); // self now contains tail, newll contains the Empty 
        Some(hd) 
       } 
       _ => None, 
      } 
     } 
    } 

    pub struct Iter<'a, T: 'a + Send + Sync + Clone>(*const LazyList<'a, T>); 

    impl<'a, T: 'a + Send + Sync + Clone> Iterator for Iter<'a, T> { 
     type Item = &'a T; 

     fn next(&mut self) -> Option<Self::Item> { 
      unsafe { 
       if let LazyList::Cons(ref v, ref r) = *self.0 { 
        self.0 = &***r; 
        Some(v) 
       } else { 
        None 
       } 
      } 
     } 
    } 

    impl<'i, 'l, T: 'i + Send + Sync + Clone> IntoIterator for &'l LazyList<'i, T> { 
     type Item = &'i T; 
     type IntoIter = Iter<'i, T>; 

     fn into_iter(self) -> Self::IntoIter { 
      self.iter() 
     } 
    } 

    impl<'a, T: 'a + Send + Sync + Clone> FromIterator<T> for LazyList<'a, T> { 
     fn from_iter<I: IntoIterator<Item = T> + 'a>(itrbl: I) -> LazyList<'a, T> { 
      let itr = itrbl.into_iter(); 
      #[inline(always)] 
      fn next_iter<'b, R: 'b + Send + Sync, Itr>(mut iter: Itr) -> LazyList<'b, R> 
       where R: 'b + Clone, 
         Itr: 'b + Iterator<Item = R> 
      { 
       match iter.next() { 
        Some(val) => LazyList::cons(val, move || next_iter(iter)), 
        None => Empty, 
       } 
      } 
      next_iter(itr) 
     } 
    } 
} 

use self::lazylist::LazyList; 
//use self::lazylist_sync::LazyList; // for slower thread-safe version 

fn main() { 
    fn fib<'a>() -> LazyList<'a, u64> { 
     fn fibi<'b>(f: u64, s: u64) -> LazyList<'b, u64> { 
      LazyList::cons(f, move || { let n = &f + &s; fibi(s, n) }) 
     } 
     fibi(0, 1) 
    } 
    let test1 = fib(); 
    for v in test1.take(20) { 
     print!("{} ", v); 
    } 
    println!(""); 
    let test2 = (0..).collect::<LazyList<_>>(); 
    for i in (&test2).into_iter().take(15) { 
     print!("{} ", i) 
    } // and from_iter() works 
} 

与输出如下：

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 

注意的是，虽然这表明，随着LazyList函数式编程风格是可能的锈，它不意味着它应该是所有用例的首选样式，特别是如果需要高性能的话。例如，如果上面的fib()函数被写入来直接输出一个迭代器而不是一个LazyList，那么它每次迭代只需要很少的CPU时钟周期（除非使用无限精度BigUint，这是更慢的），而不是LazyList每次迭代需要数百个周期（以及更多的“同步”版本）。由于引用计数的开销很高，函数式编程所需的很多小的分配/释放以及克隆/复制，因此，如果需要记忆，可能使用Vec<T>，因此更强制执行。