为 LazyList 实现 FromIterator 时遇到更严格的生命周期要求的问题
Trouble with stricter lifetime requirements when implementing FromIterator for LazyList
我正在玩 中的代码，但 FromIterator impl 不再编译：
error[E0276]: impl has stricter requirements than trait --> src/lib.rs:184:9
| 184 | fn from_iter<I: IntoIterator<Item = T> + 'a>(itrbl: I) -> LazyList<'a, T> {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ impl has extra requirement `I: 'a`
For more information about this error, try `rustc --explain E0276`.
// 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)...
pub mod lazy {
use crate::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<dyn Invoke<T> + 'a>),
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(Box::new(func))))
}
#[inline]
pub fn evaluated(val: T) -> Lazy<'a, T> {
Lazy(UnsafeCell::new(Evaluated(val)))
}
#[inline(always)]
fn force(&self) {
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!
}
}
}
}
#[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(&self) -> &T {
self.force(); // evaluatate if not evalutated
match *unsafe { &*self.0.get() } {
Evaluated(ref v) => 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.
pub mod lazylist {
use crate::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> = 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(&self) -> &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)
}
}
}
不幸的是，我已经用尽了关于如何尝试和解决这个问题的所有想法。
问题中的代码（虽然不在引用的答案中，但已更新）依赖于旧版本编译器中的健全性错误（#18937) which has since been fixed。
无法通过将迭代器存储在结构中来为 LazyList 或任何数据结构实现 FromIterator。这是因为 FromIterator 特征允许实现者 (Self) 比迭代器类型 (I::IntoIter) 长寿。编译器接受它是一种疏忽。
从互联网上复制代码时，请注意源代码的年龄。此代码在其他几个方面也已过时，特别是：
- 它使用 Rust 2015 风格的路径
- 它在特征对象类型上省略了
dyn
- 不再需要
Invoke 解决方法，因为 。
我正在玩
error[E0276]: impl has stricter requirements than trait --> src/lib.rs:184:9
| 184 | fn from_iter<I: IntoIterator<Item = T> + 'a>(itrbl: I) -> LazyList<'a, T> {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ impl has extra requirement `I: 'a`
For more information about this error, try `rustc --explain E0276`.
// 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)...
pub mod lazy {
use crate::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<dyn Invoke<T> + 'a>),
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(Box::new(func))))
}
#[inline]
pub fn evaluated(val: T) -> Lazy<'a, T> {
Lazy(UnsafeCell::new(Evaluated(val)))
}
#[inline(always)]
fn force(&self) {
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!
}
}
}
}
#[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(&self) -> &T {
self.force(); // evaluatate if not evalutated
match *unsafe { &*self.0.get() } {
Evaluated(ref v) => 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.
pub mod lazylist {
use crate::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> = 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(&self) -> &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)
}
}
}
不幸的是，我已经用尽了关于如何尝试和解决这个问题的所有想法。
问题中的代码（虽然不在引用的答案中，但已更新）依赖于旧版本编译器中的健全性错误（#18937) which has since been fixed。
无法通过将迭代器存储在结构中来为 LazyList 或任何数据结构实现 FromIterator。这是因为 FromIterator 特征允许实现者 (Self) 比迭代器类型 (I::IntoIter) 长寿。编译器接受它是一种疏忽。
从互联网上复制代码时，请注意源代码的年龄。此代码在其他几个方面也已过时，特别是：
- 它使用 Rust 2015 风格的路径
- 它在特征对象类型上省略了
dyn - 不再需要
Invoke解决方法，因为