static mutの危険性

次のような記事がありました。`static mut` の味を覚えたという記事です。

https://qiita.com/Cassin01/items/a2b67e200e87b61f41fa

ところでこの `static mut`は ["UB-happy" (trigger-happy由来の造語?) であるとして削除が提案](https://github.com/rust-lang/rust/issues/53639)される程度には物騒な代物です。そこで、どれくらい危険か、また競プロという文脈で代替策はないか書いてみたいと思います。

## 危ないプログラムの例

少し競プロ風に以下のようなサンプルプログラムを書いてみました。か～なり人工的というか、わざとらしい書き方になっていますが、「現実的には様々な条件が噛み合ったときに起こってしまう不幸を、例示のためにわざと当てに行っている」のだと思って許してください。

```rust
#![feature(const_vec_new)]

#[derive(Debug, Clone)]
struct Node {
    children: Vec<usize>,
    last: usize,
}

impl Node {
    fn add(&mut self, next: usize) -> usize {
        self.children.push(next);
        self.last = next;
        next
    }
}

static mut NODES: Vec<Node> = Vec::new();

unsafe fn new_node() -> usize {
    let ret = NODES.len();
    NODES.push(Node { children: Vec::new(), last: 0 });
    ret
}

fn main() {
    unsafe {
        let mut last = new_node();
        for i in 0..30 {
            last = NODES[last].add(new_node());
        }
        for node in &NODES {
            println!("{}", node.last);
        }
    }
}
```

このコードは `NODES` というノードプールを用意しています。ノードにはchildrenとlastというのがあって、lastには最近追加したchildrenが入っています。main内では、直線上のグラフを構成しています。

さて、これをprintすると何が出るでしょうか？グラフは「0→1→2→3→……」という構造になっているので、1から順に整数が出てくる(最後だけ0になる)はずです。しかし実際には異なる出力が得られる可能性があります。[Rust Playground](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=c53da2c10d63abae80d6dec018733d86)で試すと以下のようになりました。(2019-09-10現在)

```
1
0
3
0
5
6
7
0
9
10
11
12
13
14
15
0
17
18
19
20
21
22
23
24
25
26
27
28
29
30
0
```

こういった奇怪な現象は通常のRustでは起こりえません。 `static mut` を使うと、こういったミスを見逃しやすくなると考えられます。

## UBの危うさ

上の例はVecの挙動に立ち戻ることで説明をすることができます。しかし、UB(未定義動作)は必ずしもこのように容易に説明できる挙動になるとは限りません(これはC/C++でも、unsafe Rustでも同じことです)。たとえば以下のような記事が参考になると思います。

- https://devblogs.microsoft.com/oldnewthing/20140627-00/?p=633

UBというのはSegmentation Faultでもなければ、単にライブラリの実装の詳細が見えてしまうということでもありません。それらも含めて、「何が起こるか分からない」のが特徴です。「UBが発生した箇所とは直接関係ない場所で遅延してエラーになる」など、デバッグ困難なケースも多々あります。

「ある環境Aではたまたま動いていたが、別の環境Bでは全くもって変な挙動をする」という事象も困りますね。これはUBではなくてもありえる話ですが、UBが絡むとより厄介な形になって出てきます。競プロなら環境A=手元、環境B=ジャッジサーバーのときにとても困りますね。

(ではなぜそんな危険な現象を放置しているかというと、コンパイラにとっては「プログラムはUndefined Behaviorがないように書かれている」と仮定できるからです。この仮定はコンパイラが最適化を行うにあたって非常に重要なものです。このような言語の規格は意図的に、UBが存在するように設計されているわけです。)

## こわいunsafeとやさしいunsafe

Rustの場合、unsafeと書いた瞬間にその安全性はプログラマの責任になります。しかし、その「unsafe度」にも段階があると考えていいでしょう。

比較的扱いが容易なのは「0ではない」「境界内にある」など値に関する制約です。たとえば、

- [`NonNull::new_unchecked`](https://doc.rust-lang.org/std/ptr/struct.NonNull.html#method.new_unchecked)
- [`[T]::get_unchecked`](https://doc.rust-lang.org/std/primitive.slice.html#method.get_unchecked)

などがそれに当たります。これはプログラマの直感にはそこまで反さないため、高度な知識がなくてもそれなりにハンドルできると思います。

逆に難しいのは**参照のエイリアシング規則**がからむ場合です。「`&T` と `&mut T` の違いって何だっけ？」という問いが発生するタイプのもので、これは難しいです。

たとえば [`std::mem::transmute`](https://doc.rust-lang.org/std/mem/fn.transmute.html)というunsafe関数は、サイズが等しい2つの型の間で強制的に型変換をすることができます。 (OCamlの `Obj.magic` などの要領) しかしこれには特別な追加のチェックがあり、以下のコードはエラーになります。

```rust
unsafe fn force_write<'a>(p: &'a i32) {
    let p = std::mem::transmute::<&'a i32, &'a mut i32>(p);
    *p = 42;
}
```

エラーの内容は以下の通りです。

```
error: mutating transmuted &mut T from &T may cause undefined behavior, consider instead using an UnsafeCell
 --> src/lib.rs:2:13
  |
2 |     let p = std::mem::transmute::<&'a i32, &'a mut i32>(p);
  |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: #[deny(mutable_transmutes)] on by default
```

わざわざ警告ではなくエラーを出すほどには確証を持って「危ない」と言っているわけです。これがなぜだかわかるでしょうか？

こういった「参照のエイリアシング規則」がからむunsafeを適切に扱うには、Rustのunsafe意味論に対する深い理解が必要です。ここには可能な限り手を出さないのが賢明かと思います。 `static mut` もその仲間にあたると思います。

## 代替策 (競プロ以外)

まず、グローバルな状態を置くかわりに参照を持ち回すことで解決しないか考えるべきでしょう。実際にグローバルな状態が必要な場合、状況に応じて以下のような代替策があります。

- `lazy_static` + `Mutex`
- `once_cell` + `Mutex`
- `static` + `Mutex` (from `parking_lot`)
- `thread_local` + `RefCell`

## 代替策 (競プロの場合)

さて、[参照先の記事](https://qiita.com/Cassin01/items/a2b67e200e87b61f41fa)には以下のように書いてあります。

> Rustで競技プログラミングをする際外部変数を関数内で使用するためにはクロージャを使うと良いのですが、dfsのように再帰を行う際クロージャを使うと書くのが面倒なことになるので関数を普通に使うことになるのですが、C++erみたくglobal変数を使ってみたら引数を長々と書かなくてよくなり、より早く書けそう

これはもっともだと思います。再帰クロージャが書けないのは競プロではかなり面倒のもとになっていると思います。

競プロは基本的には「指定された環境で、指定されたデータセットに対して動けば正義」だと思いますし、リスクをわかった上で危険なRustコードを書く分にはそれを止めるのは烏滸がましいと思います。とはいえ、いちRustプログラマーとしては「あまりRust的ではないコード」が露出する機会はできるだけ抑えたいですし、せっかくのRustの利点を無駄にしない方法があればそれに越したことはありません。

そこで代替策として以下のような方法を提案したいと思います。少なくともRustの思想的にはかなりイディオマティックと言えるのではないかと思います。

```rust
// グローバル代わりの構造体
struct G {
    n: usize,
    k: usize,
    graph1: Vec<Vec<usize>>,
    graph2: Vec<Vec<usize>>,
}

// Gに対するメソッドとして各処理を定義する
impl G {
    fn dfs1(&mut self) {
        // ...
    }
    fn dfs2(&mut self) {
        // ...
    }
    fn main(&mut self) {
        // ...
    }
}

fn main() {
    G { ... }.main();
}
```

ただこの方法も最適ではなく、 `impl G` 分のインデントが見た目上かなり目立つのと、 `self.` や `&mut self` など `self` まわりでかなり冗長になると思います。普段のRustプログラミングではこれくらいの冗長性を気にしてたらやってられませんが、競プロでは短期的なコーディング効率が重要ですから、これくらいでも人によっては長すぎと思われても仕方ないかなと思います。最終的には各自の判断で最適な方法を選ぶしかないとは思います。

## まとめ

- `static mut` はそのリスクによってRustの利点を大きく損ねている。とりわけ一般的なプログラミングでは忌避すべきである
- 一方、競プロでRustを使うときの悩みどころの1つを解決する手段であることは否めない
- 多少の冗長性の増加とトレードオフになるが、グローバル代わりの `struct` を用意するという代替手段はある