如何在结构体字段上创建可变迭代器

Question

我正在使用Rust开发一款小型NES模拟器，并尝试在状态寄存器上添加新的特性。该寄存器是一个结构体，其中包含几个字段（标志位），每个字段都包含一个布尔值，而该寄存器本身是CPU结构体的一部分。

现在，我想循环遍历这些字段，并根据执行的某些指令设置布尔值。然而，我无法实现可变迭代器，我已经实现了into_iter()函数，并能够遍历这些字段以获取/打印布尔值，但如何在结构体本身内部改变这些值呢？这是可能的吗？

pub struct StatusRegister {
    CarryFlag: bool,
    ZeroFlag: bool,
    OverflowFlag: bool,
}

impl StatusRegister {
    fn new() -> Self {
        StatusRegister {
            CarryFlag: true,
            ZeroFlag: false,
            OverflowFlag: true,
        }
    }
}

impl<'a> IntoIterator for &'a StatusRegister {
    type Item = bool;
    type IntoIter = StatusRegisterIterator<'a>;

    fn into_iter(self) -> Self::IntoIter {
        StatusRegisterIterator {
            status: self,
            index: 0,
        }
    }
}

pub struct StatusRegisterIterator<'a> {
    status: &'a StatusRegister,
    index: usize,
}

impl<'a> Iterator for StatusRegisterIterator<'a> {
    type Item = bool;

    fn next(&mut self) -> Option<bool> {
        let result = match self.index {
            0 => self.status.CarryFlag,
            1 => self.status.ZeroFlag,
            2 => self.status.OverflowFlag,
            _ => return None,
        };
        self.index += 1;
        Some(result)
    }
}

pub struct CPU {
    pub memory: [u8; 0xffff],
    pub status: StatusRegister,
}

impl CPU {
    pub fn new() -> CPU {
        let memory = [0; 0xFFFF];
        CPU {
            memory,
            status: StatusRegister::new(),
        }
    }

    fn execute(&mut self) {
        let mut shifter = 0b1000_0000;
        for status in self.status.into_iter() {
            //mute status here!
            println!("{}", status);
            shifter <<= 1;
        }
    }
}

fn main() {
    let mut cpu = CPU::new();
    cpu.execute();
}

- Vinnie

---

这回答解决了你的问题吗？如何编写一个返回对自身引用的迭代器？ - Stargateur

重复的内容没有提到的是，在您的情况下，您需要 &mut，这与 & 有很大的区别，因为引用实现了复制，但可变引用不会。因此，编译器需要借用迭代器以确保可变引用仅被借用一次，但您无法这样做，因为 Rust 没有 GATs。我认为 std 在其可变迭代器实现中使用了不安全的方法。 - Stargateur

我不认为复制是合适的。预期的行为不是实现流迭代器，而只是返回对原始数据结构的引用。通用关联类型(GATs)与此无关。本质上，这个问题与 slice::IterMut 没有什么不同（除了在安全代码中可以通过两种不同的方式解决它）。 - trent

@trentcl 但是Slice IterMut的问题不就是GATs吗？ - Stargateur

@Stargateur 不，IterMut 在安全代码中实现起来很困难，但在类型系统中表达起来很容易。 - trent

Answer 1

一般来说，实现一个可变引用迭代器是困难的。如果迭代器返回对同一元素的引用两次，则会变得不安全。这意味着，如果您想要在纯安全代码中编写这样的迭代器，您必须以某种方式使编译器相信每个元素只被访问一次。这排除了简单地使用索引：您可能会忘记增加索引或将其设置在某个位置，而编译器无法推理出它。

---

一种可能的解决方法是将多个std::iter::once链接在一起（每个链接代表一个你想要迭代的引用）。

例如，

impl StatusRegister {
    fn iter_mut(&mut self) -> impl Iterator<Item = &mut bool> {
        use std::iter::once;
        once(&mut self.CarryFlag)
            .chain(once(&mut self.ZeroFlag))
            .chain(once(&mut self.OverflowFlag))
    }
}

(游乐场)

优点：

• 实现相对简单。
• 没有分配。
• 没有外部依赖。

缺点：

• 迭代器类型非常复杂：std::iter::Chain<std::iter::Chain<std::iter::Once<&mut bool>, std::iter::Once<&mut bool>>, std::iter::Once<&mut bool>>。

所以，如果你不想使用impl Iterator<Item = &mut bool>，你就必须在你的代码中有它。这包括为&mut StatusRegister实现IntoIterator，因为你必须明确指示IntoIter类型是什么。

---

另一种方法是使用数组或Vec来保存所有可变引用（具有正确的生命周期），然后委托其迭代器实现来获取值。例如，

impl StatusRegister {
    fn iter_mut(&mut self) -> std::vec::IntoIter<&mut bool> {
        vec![
            &mut self.CarryFlag,
            &mut self.ZeroFlag,
            &mut self.OverflowFlag,
        ]
        .into_iter()
    }
}

(游乐场)

优点：

• 类型为可管理性更高的std::vec::IntoIter<&mut bool>。
• 实现仍然相当简单。
• 没有外部依赖。

缺点：

• 每次调用iter_mut都需要分配内存。

我也提到了使用数组。这将避免分配内存，但事实证明，数组目前还没有实现对其值的迭代器，因此使用[&mut bool; 3]而不是Vec<&mut bool>的上述代码将无法工作。但是，存在一些创建固定长度、大小有限的数组的功能库，例如arrayvec（或array_vec）。

优点：

• 无需分配内存。
• 简单的迭代器类型。
• 实现简单。

缺点：

• 外部依赖。

---

我将介绍的最后一种方法是使用unsafe。由于这种方法与其他方法相比没有太多优点，所以通常不建议使用。主要是为了向您展示如何实现此方法。

与您的原始代码一样，我们将在自己的结构上实现Iterator。

impl<'a> IntoIterator for &'a mut StatusRegister {
    type IntoIter = StatusRegisterIterMut<'a>;
    type Item = &'a mut bool;

    fn into_iter(self) -> Self::IntoIter {
        StatusRegisterIterMut {
            status: self,
            index: 0,
        }
    }
}

pub struct StatusRegisterIterMut<'a> {
    status: &'a mut StatusRegister,
    index: usize,
}

不安全性来自于 next 方法，我们必须（基本上）将类型为 &mut &mut T 的东西转换为 &mut T，这通常是不安全的。但只要确保 next 不允许别名这些可变引用，就应该没问题。可能还有一些其他微妙的问题，所以我不能保证这是可靠的。值得一提的是，MIRI 在这方面没有发现任何问题。

impl<'a> Iterator for StatusRegisterIterMut<'a> {
    type Item = &'a mut bool;

    // Invariant to keep: index is 0, 1, 2 or 3
    // Every call, this increments by one, capped at 3
    // index should never be 0 on two different calls
    // and similarly for 1 and 2.
    fn next(&mut self) -> Option<Self::Item> {
        let result = unsafe {
            match self.index {
                // Safety: Since each of these three branches are
                // executed exactly once, we hand out no more than one mutable reference
                // to each part of self.status
                // Since self.status is valid for 'a
                // Each partial borrow is also valid for 'a
                0 => &mut *(&mut self.status.CarryFlag as *mut _),
                1 => &mut *(&mut self.status.ZeroFlag as *mut _),
                2 => &mut *(&mut self.status.OverflowFlag as *mut _),
                _ => return None
            }
        };
        // If self.index isn't 0, 1 or 2, we'll have already returned
        // So this bumps us up to 1, 2 or 3.
        self.index += 1;
        Some(result)
    }
}

(playground)

优点：

• 没有分配内存。
• 迭代器类型名称简单。
• 没有外部依赖。

缺点：

• 实现复杂。要成功使用unsafe，您需要非常熟悉什么是允许的和不允许的。这个答案的这一部分花费了我最长的时间，以确保我没有做错什么。
• 不安全会传染到模块中。在定义该迭代器的模块内，我可以通过干扰StatusRegisterIterMut的status或index字段来“安全”地引起不良后果。唯一允许封装的事情是，在该模块之外，这些字段不可见。

- SCappella

---

我仍然认为GATs会更好地解决这个问题，但是很好的回答总结了所有当前的技巧。我认为向量或数组可能是最简单和高效的选择，因为链式的成本可能有点高，因为它是O(n)，而切片长度是O(1)。请注意，不安全版本也是O(n)，但编译器可以轻松优化它。 - Stargateur

@Stargateur 在这种情况下，流迭代器版本比普通迭代器严格更差，因为它仍然可变地借用原始结构体，但无法进行“collect”。GAT解决了类型系统当前表达能力不足的问题，但在这种情况下，类型系统已经足够表达，并且困难在于实现。 - trent

@trentcl 我不同意你对问题的理解。通用关联类型（GATs）将允许迭代器被收集，我不明白为什么它实际上不应该这样做。 GATs将允许借用迭代器的可能性，并确保可变借用仅存在一次。因此，“在这种情况下，类型系统已经足够表达”我不同意或者我漏掉了什么。 - Stargateur

@Stargateur 你无法收集任何流式迭代器。API不允许这样做（或其他常见用法，例如 let first = iter.next(); let second = iter.next(); foo(first, second);）。流式迭代器是非流式迭代器的一般化（因为它们可以编写在非流式迭代器无法编写的情况下），但它们的功能较弱（因为它们不能执行所有非流式迭代器可以执行的操作）。 - trent