rust - 链接迭代器以引用不同的生活时间

Question

我想建立一个用于在Rust中遍历一棵树的递归函数。该函数应始终获取下一个元素，并在对祖先元素的引用上进行迭代。

对于祖先元素的迭代器，原则上可以使用chain和once方法。考虑下面的简单示例，其中树是Vec(出于本演示的目的):

fn proceed<'a, I>(mut remaining: Vec<String>, ancestors: I)
where
    I: Iterator<Item = &'a String> + Clone,
{
    if let Some(next) = remaining.pop() {
        let next_ancestors = ancestors.chain(std::iter::once(&next));
        proceed(remaining, next_ancestors);
    }
}

Playground

由于&next的生存期比'a的生存期短，因此无法编译:

error[E0597]: `next` does not live long enough
 --> src/lib.rs:6:62
  |
1 | fn proceed<'a, I>(mut remaining: Vec<String>, ancestors: I)
  |            -- lifetime `'a` defined here
...
6 |         let next_ancestors = ancestors.chain(std::iter::once(&next));
  |                              --------------------------------^^^^^--
  |                              |                               |
  |                              |                               borrowed value does not live long enough
  |                              argument requires that `next` is borrowed for `'a`
7 |         proceed(remaining, next_ancestors);
8 |     }
  |     - `next` dropped here while still borrowed

我试图通过添加一个显式的第二生命周期'b: 'a并通过let next_ref: &'b String = &next之类的方式强制显式引用来克服此问题，但这也会产生(不同的)错误消息。

我想到的一种解决方案是按以下方式调用map:

let next_ancestors = ancestors.map(|r| r).chain(std::iter::once(&next));

正如@trentcl指出的那样，此doesn't actually solve the problem会导致编译器在实际上尝试调用该函数时为所有嵌套的proceed编译Chain时陷入无限循环。

Answer 1

解决方案已经存在，仅作总结:

如您所知，使用map(|r| r)可“解耦” ancestors的生命周期需求
从&next的生命周期开始。

如评论中所述，修复
无限递归是将ancestors更改为特征对象的问题。

fn proceed<'a>(mut remaining: Vec<String>, ancestors: &mut dyn Iterator<Item = &'a String>) {
    if let Some(next) = remaining.pop() {
        let mut next_ancestors = ancestors.map(|r| r).chain(std::iter::once(&next));
        proceed(remaining, &mut next_ancestors);
    }
}

fn main() {
    let v = vec!["a".to_string(), "b".to_string()];
    proceed(v, &mut std::iter::empty());
}