Rust递归迭代器函数报overflow evaluating the requirement错误如何解决

触发error[E0275]类型求值溢出的核心原因是泛型单态化触发了无限类型递归：

• 原实现中compile是泛型函数，Rust编译器会为每个传入的迭代器类型生成独立的单态化实现
• 处理[语法递归调用compile时，传入的是iter.by_ref().take_while(...)，这是一个和外层迭代器类型完全不同的全新TakeWhile<...>类型
• 编译器为这个新的TakeWhile类型生成compile实现时，会发现函数内部又会生成嵌套一层的TakeWhile类型，要求继续单态化编译，这个过程没有终止条件，最终迭代器类型无限嵌套撞破编译器递归上限
• 编译器提示加recursion_limit是无效方案：因为类型嵌套是无限的，调再高的限制值都会被撞破。

使用动态分发的迭代器trait object擦除具体迭代器类型，打破无限类型递归链。不管嵌套多少层TakeWhile适配器，只要迭代器产出的元素是&u8，都可以统一转为&mut dyn Iterator<Item = &'a u8>类型，递归调用时参数类型永远固定，不会生成无限嵌套的类型。

修复后的可运行代码：

#[derive(Debug)]
enum Instruction {
    Add,
    Sub,
    Left,
    Right,
    Out,
    In,
    Loop(Vec<Instruction>),
}

fn compile<'a>(iter: &mut dyn Iterator<Item = &'a u8>) -> Vec<Instruction> {
    let mut instructions = Vec::new();

    while let Some(c) = iter.next() {
        instructions.push(match c {
            b'+' => Instruction::Add,
            b'-' => Instruction::Sub,
            b'<' => Instruction::Left,
            b'>' => Instruction::Right,
            b'.' => Instruction::Out,
            b',' => Instruction::In,
            b'[' => Instruction::Loop({
                let mut depth = 1;
                let mut sub_iter = iter.take_while(|c| {
                    match c {
                        b'[' => depth += 1,
                        b']' => depth -= 1,
                        _ => {}
                    }
                    depth != 0
                });
                compile(&mut sub_iter)
            }),
            _ => continue,
        });
    }
    instructions
}

// 调用示例
fn main() {
    let code = b"+++[->+<].";
    let mut iter = code.iter();
    let instructions = compile(&mut iter);
    println!("{:?}", instructions);
}

可选替代方案 #

也可以在递归前先把循环内的字符收集到临时Vec中，再传入Vec的迭代器递归，这样递归时传入的永远是固定的std::slice::Iter<u8>类型，也能解决问题，但会产生额外的堆内存分配，性能略低于trait object方案。

内容的提问来源于stack exchange，提问作者w1ke