我有以下形式的构造:
pub enum Value {
Nil,
Str(String),
Seq(Vec<Value>),
}
Value
为null,字符串或其他Value
的向量,然后可以是三个选项中的任何一个。
我想制作一种方法,该方法在嵌套上优先考虑String
中每个Value
的迭代。我的第一次尝试看起来像这样:
#![feature(generators)]
#![feature(generator_trait)]
use std::ops::{Generator, GeneratorState};
use std::pin::Pin;
fn gen_to_iter<G>(g: G) -> impl Iterator<Item = G::Yield>
where
G: Generator<Return = ()> + Unpin,
{
struct It<G>(G);
impl<G: Generator<Return = ()> + Unpin> Iterator for It<G> {
type Item = G::Yield;
fn next(&mut self) -> Option<Self::Item> {
match Pin::new(&mut self.0).resume() {
GeneratorState::Yielded(y) => Some(y),
GeneratorState::Complete(()) => None,
}
}
}
It(g)
}
pub enum Value {
Nil,
Str(String),
Seq(Vec<Value>),
}
impl Value {
pub fn iter_over<'a>(&'a self) -> impl Iterator<Item = &'a String> {
let closure = move || match *self {
Value::Nil => {}
Value::Str(ref s) => {
yield s;
}
Value::Seq(ref vs) => {
for v in vs {
for i in v.iter_over() {
yield i;
}
}
}
};
gen_to_iter(closure)
}
}
fn main() {
let val = Value::Seq(vec![Value::Str("test".to_string())]);
for s in val.iter_over() {
println!("{}", s);
}
}
[运行上面的代码时,由于在另一个对iter_over
的调用中调用iter_over
,所以我得到了关于递归类型的编译器错误:
error[E0720]: opaque type expands to a recursive type
--> src/main.rs:34:39
|
34 | pub fn iter_over<'a>(&'a self) -> impl Iterator<Item = &'a String> {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expands to a recursive type
|
= note: expanded type is `gen_to_iter::It<[generator@src/main.rs:35:23: 47:10 self:&'a Value for<'r, 's, 't0, 't1, 't2, 't3, 't4, 't5, 't6, 't7, 't8, 't9, 't10, 't11, 't12, 't13, 't14, 't15, 't16, 't17> {&'r Value, Value, &'s std::string::String, &'t0 std::string::String, (), &'t1 std::vec::Vec<Value>, fn(&'t2 std::vec::Vec<Value>) -> <&'t2 std::vec::Vec<Value> as std::iter::IntoIterator>::IntoIter {<&'t2 std::vec::Vec<Value> as std::iter::IntoIterator>::into_iter}, &'t3 std::vec::Vec<Value>, std::slice::Iter<'t4, Value>, std::slice::Iter<'t5, Value>, &'t6 Value, &'t7 Value, fn(impl std::iter::Iterator) -> <impl std::iter::Iterator as std::iter::IntoIterator>::IntoIter {<impl std::iter::Iterator as std::iter::IntoIterator>::into_iter}, &'t9 Value, &'t10 Value, impl std::iter::Iterator, impl std::iter::Iterator, impl std::iter::Iterator, &'t14 std::string::String, &'t15 std::string::String, &'t16 std::string::String, &'t17 std::string::String, ()}]>`
除了放弃一种懒惰的方法,而只是使用向量,我似乎无法找出解决方法。我可以在这里采取哪些潜在途径?
[生成器屈服时,它们需要存储范围内的局部变量和其他超出yield
表达式的值。生成器是枚举,其初始状态有一个变量,每个yield
表达式有一个变量,“完成”状态有一个无状态变量。在iter_over
中定义的生成器具有一个变体(对于yield i
),该变体必须存储同一生成器类型的另一个实例(间接地,因为它包装在It
中)。简化后,您最终得到的是这样的类型:
enum State<'a> {
Seq(std::slice::Iter<'a, Value>, State<'a>),
Done,
}
此类型无效,编译器会告诉我们为什么以及如何修复它:
error[E0072]: recursive type `State` has infinite size
--> src/main.rs:60:1
|
60 | enum State<'a> {
| ^^^^^^^^^^^^^^ recursive type has infinite size
61 | Seq(std::slice::Iter<'a, Value>, State<'a>),
| --------- recursive without indirection
|
= help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `State` representable
我们可以将编译器给出的建议应用于您的情况:我们可以将内部迭代器包装在Box
中,以避免无限大小的问题。
impl Value {
pub fn iter_over<'a>(&'a self) -> impl Iterator<Item = &'a String> {
let closure = move || {
match *self {
Value::Nil => {},
Value::Str(ref s) => { yield s; },
Value::Seq(ref vs) => {
for v in vs {
// This Box is necessary to give the generator a finite size.
for i in Box::new(v.iter_over()) {
yield i;
}
}
},
}
};
gen_to_iter(closure)
}
}
UPDATE: breaking change使上述解决方案不再起作用。将迭代器装箱已不再足够。尽管type T = Box<T>;
有效,但由于struct T(Box<T>);
无效的原因大致相同,这是一个错误;只有命名类型可以递归。为了解决这个问题,我们必须将类型隐藏在特征对象的后面。仍然需要装箱;生成器必须拥有内部迭代器,因此我们在这里不能使用引用。
impl Value {
pub fn iter_over<'a>(&'a self) -> impl Iterator<Item = &'a String> {
let closure = move || {
match *self {
Value::Nil => {},
Value::Str(ref s) => { yield s; },
Value::Seq(ref vs) => {
for v in vs {
// An `impl trait` type cannot refer to itself, even with indirection.
// https://github.com/rust-lang/rust/pull/56074#issuecomment-442982242
let iter = Box::new(v.iter_over()) as Box<dyn Iterator<Item = &'a String>>;
for i in iter {
yield i;
}
}
},
}
};
gen_to_iter(closure)
}
}