types - Rust 中这个奇怪的递归类型错误是怎么回事？

Question

我有一个名为 Join 的可迭代结构:

use std::iter::Peekable;

#[derive(Debug)]
pub struct Join<T, S> {
    container: T,
    separator: S,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum JoinItem<T, S> {
    Element(T),
    Separator(S),
}

pub struct JoinIter<Iter: Iterator, Sep> {
    iter: Peekable<Iter>,
    sep: Sep,
    next_sep: bool,
}

impl<Iter: Iterator, Sep> JoinIter<Iter, Sep> {
    fn new(iter: Iter, sep: Sep) -> Self {
        JoinIter {
            iter: iter.peekable(),
            sep,
            next_sep: false,
        }
    }
}

impl<I: Iterator, S: Clone> Iterator for JoinIter<I, S> {
    type Item = JoinItem<I::Item, S>;

    /// Advance to the next item in the Join. This will either be the next
    /// element in the underlying iterator, or a clone of the separator.
    fn next(&mut self) -> Option<Self::Item> {
        let sep = &self.sep;
        let next_sep = &mut self.next_sep;

        if *next_sep {
            self.iter.peek().map(|_| {
                *next_sep = false;
                JoinItem::Separator(sep.clone())
            })
        } else {
            self.iter.next().map(|element| {
                *next_sep = true;
                JoinItem::Element(element)
            })
        }
    }
}

对 Join 的引用工具 IntoIterator :

impl<'a, T, S> IntoIterator for &'a Join<T, S>
where
    &'a T: IntoIterator,
{
    type IntoIter = JoinIter<<&'a T as IntoIterator>::IntoIter, &'a S>;
    type Item = JoinItem<<&'a T as IntoIterator>::Item, &'a S>;

    fn into_iter(self) -> Self::IntoIter {
        JoinIter::new(self.container.into_iter(), &self.separator)
    }
}

这会编译并通过使用测试。

我还有一个 iter在我的 Join 上定义的方法结构:

impl<T, S> Join<T, S>
where
    for<'a> &'a T: IntoIterator,
{
    pub fn iter(&self) -> JoinIter<<&T as IntoIterator>::IntoIter, &S> {
        self.into_iter()
    }
}

这编译得很好，但是当我实际尝试使用它时:

fn main() {
    // Create a join struct
    let join = Join {
        container: vec![1, 2, 3],
        separator: ", ",
    };

    // This works fine
    let mut good_ref_iter = (&join).into_iter();
    assert_eq!(good_ref_iter.next(), Some(JoinItem::Element(&1)));
    assert_eq!(good_ref_iter.next(), Some(JoinItem::Separator(&", ")));
    assert_eq!(good_ref_iter.next(), Some(JoinItem::Element(&2)));
    assert_eq!(good_ref_iter.next(), Some(JoinItem::Separator(&", ")));
    assert_eq!(good_ref_iter.next(), Some(JoinItem::Element(&3)));
    assert_eq!(good_ref_iter.next(), None);

    // This line fails to compile; comment out this section and it all works
    let bad_ref_iter = join.iter();
    assert_eq!(bad_ref_iter.next(), Some(JoinItem::Element(&1)));
    assert_eq!(bad_ref_iter.next(), Some(JoinItem::Separator(&", ")));
    assert_eq!(bad_ref_iter.next(), Some(JoinItem::Element(&2)));
    assert_eq!(bad_ref_iter.next(), Some(JoinItem::Separator(&", ")));
    assert_eq!(bad_ref_iter.next(), Some(JoinItem::Element(&3)));
    assert_eq!(bad_ref_iter.next(), None);
}

我遇到了某种奇怪的类型递归错误:

error[E0275]: overflow evaluating the requirement `&_: std::marker::Sized`
   --> src/join.rs:288:29
    |
 96 |         let mut iter = join.iter();
    |                             ^^^^
    |
    = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&_`
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&join::Join<_, _>`
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&join::Join<join::Join<_, _>, _>`
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&join::Join<join::Join<join::Join<_, _>, _>, _>`
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&join::Join<join::Join<join::Join<join::Join<_, _>, _>, _>, _>`
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&join::Join<join::Join<join::Join<join::Join<join::Join<_, _>, _>, _>, _>, _>`
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&join::Join<join::Join<join::Join<join::Join<join::Join<join::Join<_, _>, _>, _>, _>, _>, _>`
...

(我在 ... 中编辑了大约 100 多行递归类型错误)

据我所知，它似乎在尝试主动评估 &Join<_, _> 是否存在。工具 IntoIterator ，这需要检查是否 &Join<Join<_, _>, _>实现 IntoIterator，等等。我不明白的是为什么它认为它必须这样做，因为我的实际类型完全符合 Join<Vec<{integer}, &'static str> 的要求。 .我尝试过的一些事情:

• 将特征边界从 impl header 移到 iter 中函数，像这样:

  fn iter(&'a self) -> JoinIter<<&'a T as IntoIterator>::IntoIter, &'a S>
  where &'a T: IntoIterator
  

  这有相同的结果。

• 替换 self.into_iter()与底层表达式，JoinIter::new(self.container.into_iter(), self.separator) ，希望它可能正在努力区分 self.into_iter()来自 (&self).into_iter() .我已经尝试了以下所有模式:

  • fn iter(&self) -> ... { self.into_iter() }
  • fn iter(&self) -> ... { (&self).into_iter() }
  • fn iter(&self) -> ... { JoinIter::new(self.container.into_iter(), &self.separator) }
  • fn iter(&self) -> ... { JoinIter::new((&self.container).into_iter(), &self.separator) }
• 说到这里，替换对 self.iter() 的调用与 (&self).into_iter()修复了问题，但将其替换为 (&self).iter()没有。

为什么 (&join).into_iter()工作，但是join.iter()没有，即使iter()只需调用 self.into_iter()在幕后？

这个具有相同代码的完整示例也可以在 Rust Playground 中找到。

---

有关 Join 的更多信息, 看我大Stack Overflow question和我的实际 source code .

Answer 1

编译器似乎无法解决 iter() 所需的特征要求返回类型 JoinIter<<&T as IntoIterator>::IntoIter, &S> .

我从 rustc --explain E0275 收到了这方面的提示错误解释:

This error occurs when there was a recursive trait requirement that overflowed before it could be evaluated. Often this means that there is unbounded recursion in resolving some type bounds.

我不知道 rust 的推理过程的细节，我猜想发生了以下情况。

接受这个签名:

fn iter(&self) -> JoinIter<<&T as IntoIterator>::IntoIter, &S>

编译器尝试推断返回类型:

JoinIter<<&T as IntoIterator>::IntoIter, &S>

但是<&T as IntoIterator>::IntoIter从 &'a Join 推断实现:

impl<'a, T, S> IntoIterator for &'a Join<T, S>
    where &'a T: IntoIterator
{
    type IntoIter = JoinIter<<&'a T as IntoIterator>::IntoIter, &'a S>;
    type Item = JoinItem<<&'a T as IntoIterator>::Item, &'a S>;

    fn into_iter(self) -> Self::IntoIter {
        JoinIter::new(self.container.into_iter(), &self.separator)
    }
}

和IntoIter又是一个 JoinIter<<&'a T as IntoIterator>::IntoIter, &'a S>有一个 IntoIter如此这般，无穷无尽。

使其编译的一种方法是用 turbofish 帮助编译器:

let mut bad_ref_iter = Join::<Vec<i32>, &str>::iter(&join);

代替:

let bad_ref_iter = join.iter();

更新

行:

type IntoIter = JoinIter<<&'a T as IntoIterator>::IntoIter, &'a S>;    

生成递归，因为 Rust 检查特征在定义时是否有效，而不是在使用时检查。

参见 this post有关更多详细信息和指向工作进度的指示 惰性规范化，这可能会解决这个问题。