[Rust] ゲームでありがちなミュータブル参照の問題

# やりたいこと

ゲームエンジンを開発していると、よくあるパターンとして、 Entity の一つ一つにメソッドを呼ぶことがあると思いますが、そのときにゲーム全体の状態を渡したいことがあると思います。さらに、 Entity の応答に応じて GameState にも変更を加えたいということがあるでしょうから、ミュータブル参照を渡したいところです。

```rust
struct Entity { /* ... */ }

impl Entity {
    fn simulate(&mut self, state: &mut GameState) { /* ... */ }
}

struct GameState {
    entities: Vec<Entity>,
    /* ... */
}

impl GameState {
    fn simulate(&mut self) {
        for entity in &mut self.entities {
            entity.simulate(self);
        }
    }
}
```

C++ では簡単にできることですが、 Rust では当然ながらコンパイルエラーになります。 Entity 自体が GameState の一部なので、そのミュータブル参照を渡すということは、同じ`self`オブジェクトに2つのミュータブル参照からアクセスできてしまうからです。

```
error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> src/lib.rs:14:29
   |
13 |         for entity in &mut self.entities {
   |                       ------------------
   |                       |
   |                       first mutable borrow occurs here
   |                       first borrow later used here
14 |             entity.simulate(self);
   |                             ^^^^ second mutable borrow occurs here
```

# GameState を分ける方法

簡単な方法としては GameState を Entity のリストとそれ以外(`RestState`)に分けてしまうという方法があります。

```rust
struct Entity { /* ... */ }

impl Entity {
    fn simulate(&mut self, state: &mut RestState) { /* ... */ }
}

struct RestState;

struct GameState {
    entities: Vec<Entity>,
    rest: RestState,
}

impl GameState {
    fn simulate(&mut self) {
        for entity in &mut self.entities {
            entity.simulate(&mut self.rest);
        }
    }
}
```

しかしこれはあまりうまくいきません。 Entity のタイプが増えてくると、それぞれの Entity のリストとそれ以外を分けることが簡単にはできなくなってくるからです。例えば、下記のような GameState をどう分割できるか考えてみてください。

```rust
struct GameState {
    entities_a: Vec<EntityA>,
    entities_b: Vec<EntityB>,
    entities_c: Vec<EntityC>,
}
```

# 一時変数に move する方法

で、かなりトリッキーですが、 Entity のリストを一時オブジェクトに `std::mem::take` してしまい、あとで move し戻すという方法があります。これは `Vec` が `Default` だからできることですが、そうでないコンテナでも `Option` にくるんでやれば同じことができると思います。

```rust
impl GameState {
    fn simulate(&mut self) {
        let mut entities = std::mem::take(&mut self.entities);
        for entity in &mut entities {
            entity.simulate(self);
        }
        self.entities = entities;
    }
}
```

Entity のリスト全体を動かすので、パフォーマンス的に不利のようにも見えますが、実は Vec の指しているメモリ上のバッファは動かず、ポインタを移動しているだけなので、それほど悪い方法ではありません。ほかにも `RefCell` を使う方法もあると思いますが、 `RefCell` も貸し出し状態を管理する変数を必要とするので、オーバーヘッドという点では大差ないと思います。

# 同じ Entity のリストを参照するには？

ところでここで問題が生じます。上記の方法では、 Entity のリストをすべて GameState から退避してしまうので、同じ Entity のリストに存在する他の Entity を `Entity::simulate` から参照したいと思ってもできないということです。

```rust
impl Entity {
    fn simulate(&mut self, state: &mut GameState) {
        for entity in &mut state.entities {
            // 常に empty!
        }
    }
}
```

これを実現するには、 Entity のリストの中で自分自身を除いたすべてのものをイテレートすることができればいいわけです。素直に考えれば、 Entity のリスト全体を GameState から退避するのではなく、自分自身だけを除いたリストを残せばいいわけですが、これを `Vec` に対してやるのはかなりの非効率です。

10000個の Entity があるときを考えてみてください。一つ目の Entity を扱う時には、 後ろの9999個の Entity を一つ前にずらし、 二つ目のときには9998個を動かし、…ということをしなければなりません。 `HashMap` なら定数時間で削除/挿入ができますが、このためだけに `HashMap` を使うのは、キャッシュの局所性を考えても避けたいところです。 [swap_remove](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.swap_remove) で要素のシフトを避けることもできますが、もっと良い方法があります。

ここで Rust のスライス型には [split_at_mut](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.split_at_mut) という素晴らしいメソッドがあるという事実が役に立ちます。

```rust
impl Entity {
    fn simulate(
        &mut self,
        state: &mut GameState,
        first: &mut [Entity],
        last: &mut [Entity])
    {
        for entity in first.iter_mut() {
            /* ... */
        }
        for entity in last.iter_mut() {
            /* ... */
        }
    }
}

impl GameState {
    fn simulate(&mut self) {
        let mut entities = std::mem::take(&mut self.entities);
        for i in 0..entities.len() {
            let (first, mid) = entities.split_at_mut(i);
            let (center, last) = mid.split_first_mut().unwrap();
            center.simulate(self, first, last);
        }
        self.entities = entities;
    }
}
```

この方法は、 `Vec` 自体のサイズは変えずに、スライスの範囲を自分を除外するように設定するという方法で、動的メモリを使わすに自分自身を除いたオブジェクトをイテレートすることができるという魔法のような方法です。

![dyn_iter.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/242745/b2e6fd08-5ddd-75ff-0733-1b6ec2bba108.png)


しかし、ちょっとだけカッコ悪いところがあります。それは `Entity::simulate()` の中で自分より前のスライスと後ろのスライスを別々にループで回さなくてはならないということです。

```rust
for entity in first.iter_mut() {
    /* ... */
}
for entity in last.iter_mut() {
    /* ... */
}
```

理想的には、前の半分と後ろの半分を続けてイテレートするようなイテレータがあるといいわけです。実際、これはそれほど難しくないです。

```rust
for entity in first.iter_mut().chain(last.iter_mut()) {
    /* ... */
}
```

しかし、このメソッドのシグネチャは、内部実装をさらけ出しているようでちょっと気持ち悪いです。

```rust
fn simulate(
    &mut self,
    state: &mut GameState,
    first: &mut [Entity],
    last: &mut [Entity])
```

理想的には、 `Iterator` トレイトでそのようなリストを生成する型を定義し、 `simulate` のシグネチャは次のようにしたいところです。

```rust
fn simulate(
    &mut self,
    state: &mut GameState,
    entities: &dyn Iterator<Item = Entity>);
```

しかし、 `Iterator` は一度リストをイテレートし終わったら、再び巻き戻して最初からやり直すということができないので、スライスの代わりにはなりません。 `Iterator` トレイトの必要なメソッドは `next()` のみで、巻き戻すということはできないのです。 Entity のリストを何度か辿りたいということはゲームの中では珍しいことではありませんので、これは何とかサポートしたいところです。

つまり、「`Iterator` トレイトを何度も生成しなおせるトレイト」が必要になるわけで、それを先ほどの `first` `last` スライスから生成する型を実装すればよいわけです。この方針の素晴らしい点は、もし自分を除外する必要がなければ単純なスライスを実装すればより効率的な型が同じロジックでも使えるようになるということです。

ですが、ここまで来て自分の力では実装できそうにない気がしたので、私は公式フォーラムに[助けを求めました](https://users.rust-lang.org/t/how-to-rewind-or-recreate-an-iterator-trait-object/51499)。 Rust はコミュニティのクオリティが高いことに定評がありますが、その評判に違わず、私の求めていた実装を示してくれた人がいました。

以下が「巻き戻し可能なイテレータ」に相当するトレイトです。

```rust
pub(crate) trait DynIter {
    type Item;
    fn dyn_iter(&self) -> Box<dyn Iterator<Item = &Self::Item> + '_>;
    fn as_dyn_iter(&self) -> &dyn DynIter<Item = Self::Item>;
}
impl<T, Item> DynIter for T
where
    for<'a> &'a T: IntoIterator<Item = &'a Item>,
{
    type Item = Item;
    fn dyn_iter(&self) -> Box<dyn Iterator<Item = &Self::Item> + '_> {
        Box::new(self.into_iter())
    }
    fn as_dyn_iter(&self) -> &dyn DynIter<Item = Self::Item> {
        self
    }
}

pub(crate) trait DynIterMut: DynIter {
    fn dyn_iter_mut(&mut self) -> Box<dyn Iterator<Item = &mut Self::Item> + '_>;
}
impl<T, Item> DynIterMut for T
where
    for<'a> &'a T: IntoIterator<Item = &'a Item>,
    for<'a> &'a mut T: IntoIterator<Item = &'a mut Item>,
{
    fn dyn_iter_mut(&mut self) -> Box<dyn Iterator<Item = &mut Self::Item> + '_> {
        Box::new(self.into_iter())
    }
}

```

そして、次にスライスの組から前述のトレイトを実装する型です。

```rust
        struct MutRef<'r, T: ?Sized>(&'r mut T);
        impl<'a, 'r, T: ?Sized> IntoIterator for &'a MutRef<'r, T>
        where
            &'a T: IntoIterator,
        {
            type IntoIter = <&'a T as IntoIterator>::IntoIter;
            type Item = <&'a T as IntoIterator>::Item;
            fn into_iter(self) -> Self::IntoIter {
                self.0.into_iter()
            }
        }
        impl<'a, 'r, T: ?Sized> IntoIterator for &'a mut MutRef<'r, T>
        where
            &'a mut T: IntoIterator,
        {
            type IntoIter = <&'a mut T as IntoIterator>::IntoIter;
            type Item = <&'a mut T as IntoIterator>::Item;
            fn into_iter(self) -> Self::IntoIter {
                self.0.into_iter()
            }
        }

        struct Chained<S, T>(S, T);
        impl<'a, S, T, Item: 'a> IntoIterator for &'a Chained<S, T>
        where
            &'a S: IntoIterator<Item = &'a Item>,
            &'a T: IntoIterator<Item = &'a Item>,
        {
            type IntoIter =
                iter::Chain<<&'a S as IntoIterator>::IntoIter, <&'a T as IntoIterator>::IntoIter>;
            type Item = &'a Item;
            fn into_iter(self) -> Self::IntoIter {
                self.0.into_iter().chain(self.1.into_iter())
            }
        }
        impl<'a, S, T, Item: 'a> IntoIterator for &'a mut Chained<S, T>
        where
            &'a mut S: IntoIterator<Item = &'a mut Item>,
            &'a mut T: IntoIterator<Item = &'a mut Item>,
        {
            type IntoIter = iter::Chain<
                <&'a mut S as IntoIterator>::IntoIter,
                <&'a mut T as IntoIterator>::IntoIter,
            >;
            type Item = &'a mut Item;
            fn into_iter(self) -> Self::IntoIter {
                self.0.into_iter().chain(self.1.into_iter())
            }
        }
```

使うときは次のようにします。

```rust
center.simulate(self, &mut Chained(MutRef(first), MutRef(last)));
```

正直、いまだにこの実装を完璧には理解できていません ^^;
ですが、動的メモリを使っていることはわかります。 DynIter の実装によって、生成される Iterator オブジェクトのサイズが変わるので、これは仕方のないことのように思います。もしかしたら impl Trait で静的ディスパッチすればコンパイル時にサイズがわかるので動的メモリを使わなくても済むかもしれませんが、これは次の改善案ですね。

```rust
fn simulate(&mut self, state: &mut GameState, others: impl DynIterMut<Item = Entity>);
```

# オブジェクト指向への応用

ここまでの話は、 Entity が何らかの具体的な型である前提でしたが、実際、このテクニックが真価を発揮するのは、トレイトオブジェクトを使ったオブジェクト指向で Entity を実装した時です。

```rust
trait Entity {
    fn simulate(&mut self, state: &mut GameState, others: &dyn DynIterMut<Item = Box<dyn Entity>>);
}
```

Entity のリストはトレイトオブジェクトのリストになります。

```rust
struct GameState {
    entities: Vec<Box<dyn Entity>>,
}
```

それぞれのオブジェクトが実装しているのは動的ポリモーフィズムにより異なる関数となりますが、 `GameState::simulate` のロジックは全く変わることなく、そしてそれぞれの型のメソッドでは `DynIterMut` を使って巻き戻し可能なイテレータを何度でも使えるのです。

このような方法で実際に実装したブラウザゲームが[こちら](https://github.com/msakuta/FactorishWasm)です。


# ECS への応用

ECS (Entity Component System) は最近流行りのゲームアーキテクチャで、有名どころでは Unity が使っていますが、 Rust では specs というライブラリがサポートしています。

specs は、ゲームエンジンでありがちなミュータブル参照の問題の多くを回避するのに役立ちますが、やはりどうしても同じ型(コンポーネント)のリストの複数の要素を同時にミュータブル参照したい場合にはボローチェッカーと戦う羽目になります。

```rust
let entities = world.entities();
let mut components = world.write_component::<SomeComponent>();
for (entity, component) in (&entities, &mut component).join() {
    component.simulate(entity, &components);
}
```

このような場合も、前述のスライストリックが役に立ちます。

```rust
let mut component_bundle = (
    &entities,
    &mut component,
)
.join()
.collect::<Vec<_>>();
for i in 0..component_bundle.len() {
    let (first, second) = component_bundle.split_at_mut(i);
    let (center, last) = second.split_at_first();
    center.simulate(self, first, last);
}
```

難点としては、一度スライスに直さなくてはいけないので、 `Vec` に `Collect` する必要があるということです。実際のコンポーネントではなく、そのコンポーネントへの参照のスライスなので、サイズはそれほど大きくありませんが、動的メモリの生成が必要になります。

複数の Entity の同じコンポーネントへのミュータブル参照を同時に取りたいことなんて、そんなにあるか？と思う方もいるかもしれませんが、私の場合は流体のコンテナコンポーネントで隣の接続した Entity との間で流入/流出のシミュレーションをするために必要でした。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/242745/e3cbad80-d283-ba62-a5a4-d80642440417.png)



# おわりに

パフォーマンスに関わること一般に言えることですが、 n 個のオブジェクトがあったときに総当たりで n^2 のチェックを行うのは筋が良いとはいえません。 n に対してスケールするには、何らかのインデックスを使ってチェック対象を絞り込むべきでしょう。しかしながら、小さなゲームについてはこのような単純な方法でもそこそこうまくいきます。

このスライストリックは、私の知る限り HashMap や BTreeMap には使えません。元のデータ構造に変更を加えずにサブセットへのミュータブル参照を複数同時に返すメソッドがないからです。もし、できるよ！という人がいたら教えてください。 :bow: