我是否错误地实现了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不相关的所有方法:

In implementing a version of a LazyList (an immutable lazily-computed memoized singly-linked list, much as Haskell lists), I have run into a problem of implementing IntoIterator in that the code does not drop the reference when I think it should. The following code has been simplified so as just to show the problem; thus, is not generic and does not include all of the methods not related to implementing 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);
    }
}

上面的代码失败，并显示以下信息:

The above code fails with:

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的生存期，因此在以下情况下不会被丢弃预期的.

As noted in the comments in main(), the code is usable except when called as a reference through the IntoIterator trait. This may be a bug in implementing traits for references where the ownership of the returned iterator containing a pointer is not transferred to the same scope as the call to IntoIterator::into_iterbut rather to the 'static lifetime, thus, it is not dropped when expected.

如果可能的话，该如何实施?我尝试将std::marker::PhantomData<>标记字段添加到Iter结构中，但似乎也为它分配了'static生存期.

How do I implement this, if possible? I've tried adding a std::marker::PhantomData<> marker field to the Iter struct but it seems that, too, is assigned a 'static lifetime.

推荐答案

实现IntoIterator时，您统一了对列表的引用和列表包含的项之间的生存期:

When you implemented IntoIterator, you unified the lifetimes between the reference to the list and the items that the list contains:

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

这要求'a必须是较短的寿命.在这种情况下，这没有用.相反，您需要有两个不同的生存期:

That requires that 'a must be the shorter of the lifetimes. That's not useful in this case. Instead, you need to have two distinct lifetimes:

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

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

这篇关于我是否错误地实现了IntoIterator以引用LazyList实现，或者这是Rust错误?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！