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

Am I incorrectly implementing IntoIterator for a reference to a LazyList implementation or is this a Rust bug?

在实现 LazyList 的一个版本(一个不可变的延迟计算的记忆化单链表,就像 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 特性作为引用调用 。这可能是实现引用特征的一个错误,其中包含指针的返回迭代器的所有权没有转移到与调用 IntoIterator::into_iter 相同的范围,而是转移到 'static 生命周期,因此,它没有在预期的时候被丢弃。

如果可能,我该如何实施?我已经尝试将 std::marker::PhantomData<> 标记字段添加到 Iter 结构,但似乎也被分配了 'static 生命周期。

当您实现 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()
    }
}

对于那些通过搜索 Rust、Lazy 和 LazyList 找到这个问题的人,我在这里 post Lazy 和 LazyList 的最终通用工作代码,具有非和线程安全版本,可与当前稳定的 Rust 一起使用版本 1.56.1.

该代码包含一些测试代码实际上没有使用的方法,尤其是 unwrap() 方法在这里没用,因为我们不能使用嵌入在另一个类型中的类型(除非我们替换内部可变价值);需要为 singleton() 方法、unwrap() 方法和 tail() 方法设计更多测试。

因为一般不能解包,嵌入类型必须是Clone;这会在所涉及的复制操作中消耗一些性能,因此当类型很大时(按复制方式),人们可能希望将它们包装在 Rc 中以实现更快的引用计数克隆。

代码如下:

pub struct Thunk<'a, R>(Box<dyn FnOnce() -> R + 'a>);
 
impl<'a, R: 'a> Thunk<'a, R> {
    #[inline(always)]
    fn new<F: 'a + FnOnce() -> R>(func: F) -> Thunk<'a, R> {
        Thunk(Box::new(func))
    }
    #[inline(always)]
    fn invoke(self) -> R { self.0() }
}
 
// Lazy is lazily evaluated contained value using the above Thunk implementation...
mod lazy {
    use crate::Thunk;
    use std::cell::UnsafeCell;
    use std::mem::replace;
    use std::ops::Deref;

    // Lazy is lazily evaluated contained value using the above Thunk implementation...
    pub struct Lazy<'a, T: 'a>(UnsafeCell<LazyState<'a, T>>);

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

    use self::LazyState::*;

    impl<'a, T: 'a> Lazy<'a, T> {
        #[inline]
        pub fn new<F: 'a + FnOnce() -> T>(func: F) -> Lazy<'a, T> {
            Lazy(UnsafeCell::new(Unevaluated(Thunk::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 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 crate::Thunk;
    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(Thunk<'a, T>),
        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(Thunk::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 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 crate::lazy::Lazy;
    use std::rc::Rc;
    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> = 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)
        }
        pub 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)
        }

    }

    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 crate::lazy_sync::Lazy;
    use std::sync::Arc as Rc;
    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> = 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)
        }
        pub 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)
        }
    }

    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 = LazyList::from_iter(0..);
    for i in (&test2).into_iter().take(15) {
        print!("{} ", i)
    } // and from_iter() works
    println!("");
}

输出如下:

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

请注意,尽管这表明在 Rust 中可以使用 LazyList 的函数式编程风格,但这并不意味着它应该是所有用例的首选风格,尤其是在需要高性能的情况下。例如,如果上面的 fib() 函数被编写为直接输出一个迭代器而不是 LazyList,那么每次迭代只需要很少的 CPU 个时钟周期(除非无限使用精度 BigUint,速度较慢),而不是 LazyList 每次迭代所需的数百个周期(“同步”版本需要更多周期)。

一般来说,由于引用计数的高开销、许多小的 allocations/deallocations 和 clone/copying 需要函数式风格编程。