Я неправильно внедряю 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. Это может быть ошибкой в ​​реализации признаков для ссылок, где право собственности на возвращенный итератор, содержащий указатель, не переносится в ту же область, что и вызов IntoIterator::into_iter, а скорее на время жизни 'static, таким образом, он не отбрасывается при ожидании.

Как это реализовать, если это возможно? Я попытался добавить поле маркера std::marker::PhantomData<> в структуру Iter, но, похоже, тоже присваивается '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.

Код содержит некоторые методы, фактически не используемые включенным тестовым кодом, и особенно методы unwrap() бесполезны здесь, поскольку мы не можем использовать тип, встроенный в другой тип (если мы не заменим внутреннее изменяемое значение); потребуется еще несколько тестов для метода 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, тогда для каждой итерации потребовалось бы очень немного тактовых циклов ЦП (кроме того, если бы использовалась бесконечная точность BigUint), а не требуется сотни циклов для каждой итерации для LazyList (и многое другое для версии «sync»).

В целом, более императивные реализации, возможно, с использованием Vec<T>, если требуется мемонирование, гораздо более результативны, чем это из-за высоких служебных затрат на подсчет ссылок, много небольших распределений/деаллокаций и клона/копирования, необходимых для программирования функционального стиля ,