Rust中的递归生成器会导致“递归类型"错误;解决方法? [英] Recursive generator in Rust causing "recursive type" error; workaround?
问题描述
我有一个形式的构造:
pub enum Value {
Nil,
Str(String),
Seq(Vec<Value>),
}
Value为null，字符串或其他Value的向量，然后可以是三个选项中的任何一个.
A Value is either null, a string, or a vector of other Values, which can then in turn be any of the three options.
我想创建一种方法，该方法懒惰地遍历Value中的每个String，并尊重嵌套.我的第一次尝试看起来像这样:
I'd like to make a method that lazily iterates over each String in a Value, respecting nesting. My first attempt looks something like this:
#![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:
When running the above code, I get a compiler error about a recursive type, since I'm calling iter_over inside another call to 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, ()}]>`
除了放弃一种懒惰的方法，而只是使用向量，我似乎无法找出解决方法.我可以在这里采取哪些潜在途径?
Aside from abandoning a lazy approach and just using vectors, I can't seem to figure out a workaround. What are some potential avenues I can take here?
推荐答案
生成器屈服时，它们需要存储范围内的局部变量和其他超出yield表达式的值.生成器是具有初始状态的一个变体，每个yield表达式的一个变体和完成"状态的一个无状态变体的枚举.在iter_over中定义的生成器具有一个变体(用于yield i)，该变体必须存储具有相同生成器类型的另一个实例(间接地，因为它包装在It中).简化后，您最终得到的是这样的类型:
When generators yield, they need to store the local variables that are in scope and other values that live beyond the yield expression. Generators are enums with one variant for the initial state, one variant for each yield expression and one stateless variant for the "done" state. The generator defined in iter_over has a variant (for the yield i) that must store another instance of the same generator type (indirectly, because it's wrapped in an It). Simplified, you end up with a type like this:
enum State<'a> {
Seq(std::slice::Iter<'a, Value>, State<'a>),
Done,
}
此类型无效，编译器会告诉我们原因以及解决方法:
This type isn't valid, and the compiler tells us why and how to fix it:
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中，以避免无限大小的问题.
We can apply the advice given by the compiler to your situation: we can wrap the inner iterator in a Box to avoid the infinite size problem.
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)
}
}
更新: 破坏性变化导致上述解决方案不再起作用.将迭代器装箱已不再足够.即使struct T(Box<T>);是有效的，这也是错误的，原因与type T = Box<T>;无效相同.只有命名类型可以递归.为了解决这个问题，我们必须将类型隐藏在特征对象的后面.仍然需要装箱；生成器必须拥有内部迭代器，因此我们不能在此处使用引用.
UPDATE: A breaking change causes the above solution to no longer work. It's no longer sufficient to box the iterator. It's an error for pretty much the same reason type T = Box<T>; is invalid, even though struct T(Box<T>); is valid; only named types can be recursive. To solve this, we must hide the type behind a trait object. Boxing is still necessary; the generator must own the inner iterator, so we can't use a reference here.
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)
}
}
这篇关于Rust中的递归生成器会导致“递归类型"错误;解决方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
