[WIP] Rust初心者が困惑しそうな点について

私（Rust初心者）が困惑した事柄を随時追加していきます．

# ライフタイムとスコープ

以下のような[コード](https://play.rust-lang.org/?version=nightly&mode=release&edition=2015&gist=6bffc66e799538337dca79d1b01cb87b)をコンパイルすると[エラー](https://doc.rust-lang.org/stable/error-index.html#E0506)になります．

```rust
struct A { a: i32 }

fn main() {
    let mut a1 = A { a: 1 };
    let mut a2 = A { a: 2 };
    let mut r = &mut a1;
    let x = &r.a;  // &i32, immutable
    r = &mut a2;   // this line seems to be safe, but makes E0506
}
```

このコードだけだと大した問題ではないと感じると思いますが，再帰構造をループでたどる「素直な」コードを書くと同じ問題が発生します．

* [末尾再帰をループにできないRustプログラムの例 - 簡潔なQ](https://qnighy.hatenablog.com/entry/2017/05/06/070000)
* [rustで単方向リスト＋単体テスト - Qiita](https://qiita.com/tkyk0317/items/8edf3374ead689875d4b)
* [Learning Rust With Entirely Too Many Linked Lists](http://cglab.ca/~abeinges/blah/too-many-lists/book/first-ownership.html)

Stack Overflowで解決法をいくつか見つけられます．

* [Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time - Stack Overflow](https://stackoverflow.com/questions/37986640/cannot-obtain-a-mutable-reference-when-iterating-a-recursive-structure-cannot-b/37987197#37987197)

Non-Lexical LifetimeのRFCは[こちら](https://rust-lang.github.io/rfcs/2094-nll.html)．2018-10-30時点では，`#![feature(nll)]`はNightlyでのみ動作します．

# モジュールの宣言

Rustのモジュールシステムは，ファイルおよびフォルダ構成と密接に関係しています．そのため，モジュールの宣言（モジュールの定義ではない）は通常以下のファイルでのみ行えます．

* main.rs
* lib.rs
* mod.rs

Rustでは，あるファイル内に書かれたコードは，ファイル名を名前とするモジュールのスコープ内に配置されます．そのため，以下のようなコードを書いた場合，

```rust:animal.rs
mod cat;
```

`rustc`は，`animal/cat.rs`もしくは`animal/cat/mod.rs`を探します．また，`mod.rs`以外でモジュール宣言を行った場合，以下のようなコンパイルエラーになります．

```console
error[E0658]: mod statements in non-mod.rs files are unstable (see issue #44660)
 --> src/animal.rs:1:5
  |
1 | mod cat;
  |     ^^^
  |
  = help: on stable builds, rename this file to animal/mod.rs
```

制約はあるようですが，上記の３つのファイル以外でもモジュール宣言を記述可能にしようということが[RFC2126](https://rust-lang.github.io/rfcs/2126-path-clarity.html)で提案されているようです．

# 固定長バッファーをヒープから確保するときは，`Box::new([T: N])`は避けましょう

理由については[[WIP] rustcが生成するコードの調査](https://qiita.com/masnagam/items/068f39116950f1f85651#boxnew%E3%81%A8%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%81%AE%E5%88%9D%E6%9C%9F%E5%8C%96)を見てください．

特に事情がなければ`Vec`を使うので良いと思います．

* [rustで動的にバッファを確保する方法 - 睡分不足](http://mmi.hatenablog.com/entry/2017/08/06/230823)

## 大きな構造体を`Box::new()`すると，スタックを消費してしまう問題

関連問題として，大きな構造体のメモリを確保するときに，スタックの消費を避けるためヒープから確保しようとして`Box::new()`に置き換えたとしても，スタックを消費されてしまうという問題が発生します．`box`を使えば`Box::new()`の問題は解決できますが，`Rc::new()`など他のものについては現時点では解決方法は存在しないようです．

一連のコピーコストを改善するため[配置構文](https://rust-lang.github.io/rfcs/1228-placement-left-arrow.html)というものが提案されていましたが，すでにunstableからも削除されています．詳細については[[WIP] rustcが生成するコードの調査](https://qiita.com/masnagam/items/068f39116950f1f85651#%E9%85%8D%E7%BD%AE%E6%A7%8B%E6%96%87)を見てください．

# 比較演算子

型強制やトレイトの実装状況などに応じで，コンパイルエラーになったり，C/C++プログラマーが困惑するような動作が発生します．

以下はどちらも`true`と評価されますが，実行される処理が異なります．

```rust:rust
1 == 1;
&1 == &1;
```

```:MIR
// 1 == 1
_1 = Eq(const 1i32, const 1i32);

// &1 == &1
_2 = const std::cmp::PartialEq::eq(move _3, move _4) -> bb1;
```

参照同士の比較はポインターの比較ではなく，[`std::cmp::PartialEq::eq()`](https://doc.rust-lang.org/src/core/cmp.rs.html#870)の呼び出しです．上記の例は`i32`の例ですが，`std::cmp::PartialEq`は個別に実装可能なので，比較対象のオブジェクトごとに動作が異なります．殆どの場合，アドレス比較ではなく，内容の比較が行われるようです．

`std::cmp::PartialEq::eq()`の定義上，以下のような比較はコンパイルエラーになります．

```rust:rust
1 == &1;
&1 == 1;
```

以下はコンパイルできますが，

```rust:rust
(&1 as *const i32) == &1;  // 型強制で&i32が*const i32に
```

逆はコンパイルエラーです．

```rust:rust
&1 == (&1 as *const i32);  // &i32はstd::cmp::PartialEq<*const i32>::eq()を持たない
```

アドレス比較したいときは素直に[`std::ptr::eq()`](https://doc.rust-lang.org/std/ptr/fn.eq.html)を使いましょう．これなら引数の順番に関係なくアドレス比較できます．

```rust:rust
std::ptr::eq(&1, (&1 as *const i32));
std::ptr::eq((&1 as *const i32), &1);
```

# 借用ルールとオブジェクト間のリンク

Rustは，ミュータブルな参照に関して安全性のため不寛容な[ルール](https://doc.rust-jp.rs/the-rust-programming-language-ja/1.6/book/references-and-borrowing.html#%E3%83%AB%E3%83%BC%E3%83%AB)を持っています．そのため，ミュータブルなグラフ（またはそれに類するリンク構造）上で１つ以上の被参照を持つノードのエッジを表現する場合には工夫が必要です．

* [SimonSapin/rust-forest: A tree of reference-counted nodes, with `RefCell` for mutability](https://github.com/SimonSapin/rust-forest)
* [saschagrunert/indextree: Arena based tree 🌲 structure by using indices instead of reference counted pointers](https://github.com/saschagrunert/indextree)

以下では４つのエッジを持つ木構造を例に説明します．子ノードを`Vec<Node<T>>`として関数を再帰呼び出しすることでも木構造とその操作を表現することができますが，本件の趣旨とは合わないため除外します．

## `Cell<Option<&'a Node<'a, T>>>`を使う

一般的には，この方法を使う場合はborrow chekerを通すために各エッジのライフタイムを指定する必要があります．

```rust:rust
struct Node<'a, 'b, 'c, 'd, T> {
    parent: Cell<Edge<'a, T>>,
    prev_sibling: Cell<Edge<'b, T>>,
    next_sibling: Cell<Edge<'c, T>>,
    first_child: Cell<Edge<'d, T>>,
    value: T,
}
```

しかし，`Edge`は`Node`への参照を含むため，その定義に`Node`のジェネリックパラメーターを含む必要があります．

```rust:rust
type Edge<'a, 'b, 'c, 'd, 'e, T> = Option<&'a Node<'b, 'c, 'd, 'e, T>>;
```

`Node`はこの定義の`Edge`を含むはずなので．．．つまり，個別の参照のライフタイムを指定する形では定義することはできません．再帰構造なので当然といえば当然です．

結局，再帰構造上以下のような形でしか定義できません．

```rust:rust
type Edge<'a, T> = Option<&'a Node<'a, T>>;

struct Node<'a, T> {
    parent: Cell<Edge<'a, T>>,
    prev_sibling: Cell<Edge<'a, T>>,
    next_sibling: Cell<Edge<'a, T>>,
    first_child: Cell<Edge<'a, T>>,
    value: T,
}
```

これは，すべてのノードが同じライフタイムを持つことを意味します．

Rustでは異なるライフタイムを持つミュータブルなグラフをノードへの参照を使って表現することはできません．

## `Option<Rc<RefCell<Node<T>>>>`を使う

ライフタイムが異なる場合，ノードへの参照を使って表現することができないことが分かりました．これはライフタイムが異なる場合，ダングリングポインターの排除をコンパイル時に行えないことを意味しています．仕方がないので実行時にチェックすることにします．

```rust:rust
type Ref<T> = Rc<RefCell<Node<T>>>;
type WeakRef<T> = Weak<RefCell<Node<T>>>;

type Edge<T> = Option<Ref<T>>;
type WeakEdge<T> = Option<WeakRef<T>>;

struct Node<T> {
    parent: WeakEdge<T>,
    prev_sibling: WeakEdge<T>,
    next_sibling: Edge<T>,
    first_child: Edge<T>,
    value: T,
}
```

循環参照を避けるため`Weak`を使います．今回は木構造なので上記のような形でノードを定義できましたが，一般的には弱参照を使った循環回避は簡単ではありません．それが可能な形になるようにデータ構造を設計する必要があります．

ジェネリックパラメーターでのライフタイムの指定がなくなったため，一時的に保持したノードへの参照がダングリングポインターにならないことをコンパイル時に確認することはできません．その代りに，`RefCell`を使って実行時にチェックするようになっています．

実行時のコストについて，以下にまとめておきます．

* `Rc`および`Weak`生成・破棄時のカウンター操作
    * イテレーションでノードをたどるたびに発生します
* `RefCell`での`Ref`および`RefMut`の生成・破棄時のコスト
    * ノード参照時に発生します

多数のノードにわたり何度もイテレーションを行う場合，高コストとなる可能性があります．

## `Option<NonNull<Node<T>>>`

一時変数がダングリングポインターにならないことをプログラマーが保証することを許容できるのであれば，`NonNull<Node<T>`もしくは`*const Node<T>`を使えます．

```rust:rust
type Ref<T> = NonNull<Node<T>>;
type Edge<T> = Option<Ref<T>>;

struct Node<T> {
    parent: Cell<Edge<T>>,
    prev_sibling: Cell<Edge<T>>,
    next_sibling: Cell<Edge<T>>,
    first_child: Cell<Edge<T>>,
    value: T,
}
```

エッジのライフタイム指定もありませんし，参照の借用についての制限もありません．ただし，ダングリングポインターの問題や値の一貫性の問題が残ります．

```rust:rust
let parent = Node::new(0);
let node = Node::new(1);
parent.append(&node);
let first_child = parent.first_child();  // Edge<i32>を返すとする
node.remove();
// nodeは生きてはいるが，first_childは昔の状態での値を保持
```

`Node<T>::parant`などは`Drop`を実装することでリンクの一貫性を保つことが可能ですが，`Edge<T>`や`Ref<T>`を一時変数にバインドしている場合，どうにもなりません．

`LinkedList`のように，リンク構造を隠蔽可能な場合は，`Node<T>::value`を生ポインターなどで取得しないことを前提にすれば，使用者側でダングリングポインターが発生することはありません．

`Box<Node<T>>`や`Rc<Node<T>>`を使うことで，使用者側でダングリングポインターが発生しないように管理することは可能ですが，使用者が`Box`を使うのか`Rc`を使うのか`Node<T>`側では決めることができないので，使用者側で`Edge<T>`から適切な型に変換する処理を実装する必要があります．

## 一意なノード識別子のリスト

ノードに一意な識別子をつけて，エッジを識別子のリストとして表現することも可能です．ただし，これは`NonNull<Node<T>>`の場合同様，ダングリングポインターに類する問題や値の一貫性の問題が発生します．基本的には`NonNull<Node<T>>`の変種の１つなので説明を割愛します．

# `T: U`トレイトオブジェクトから`U`トレイトオブジェクトへの変換

現時点では，`T: U`トレイトオブジェクトから`U`トレイトオブジェクトへの変換は自動では行われません．

```rust:rust
trait Node {}
trait Element : Node {}

struct ElementImpl {}

impl Node for ElementImpl {}
impl Element for ElementImpl {}

fn main() {
    let element_impl = ElementImpl {};
    let element: &Element = &element_impl;
    let node: &Node = element;  // &dyn Nodeに変換したいが，ビルドエラーとなる
}
```

Issueとして登録済みです．まだクローズされていないので，将来サポートされる可能性はあるようです．

* [Objects should be upcastable to supertraits · Issue #5665 · rust-lang/rust](https://github.com/rust-lang/rust/issues/5665)

以下のように，`AsRef<T>`を使って明示的に変換することなら可能です．

```rust:rust
trait Node {}
trait Element : Node + AsRef<Node> {}

struct ElementImpl {}

impl Node for ElementImpl {}
impl Element for ElementImpl {}

impl<'a> AsRef<Node + 'a> for ElementImpl {
    fn as_ref<'b>(&'b self) -> &'b (Node + 'a) {
        self
    }
}

fn main() {
    let element_impl = ElementImpl {};
    let element: &Element = &element_impl;
    let node: &Node = element.as_ref();  // &dyn Node
}
```

# トレイトオブジェクト経由だと`use`してなくてもメソッドを呼び出せる

[ドキュメント](https://doc.rust-jp.rs/the-rust-programming-language-ja/1.6/book/traits.html#%E3%83%88%E3%83%AC%E3%82%A4%E3%83%88%E5%AE%9F%E8%A3%85%E3%81%AE%E3%83%AB%E3%83%BC%E3%83%AB)にもちゃんと書いてありますが，スコープ内のトレイトのみが適用されます．

```rust:rust
mod dom {
    pub trait Element {
        fn tag_name(&self) -> &str;
    }
}

struct ElementImpl {}

impl dom::Element for ElementImpl {
    fn tag_name(&self) -> &str {
        "element"
    }
}

fn main() {
    let element_impl = ElementImpl {};
    // 以下の行でビルドエラー．
    // domで定義されたElementがスコープに含まれていないため，tag_name()が見つからない
    println!("{}", element_impl.tag_name());
}
```

しかし，トレイトオブジェクト経由なら呼び出せます．

```rust:rust
mod dom {
    pub trait Element {
        fn tag_name(&self) -> &str;
    }
}

struct ElementImpl {}

impl dom::Element for ElementImpl {
    fn tag_name(&self) -> &str {
        "element"
    }
}

fn main() {
    let element_impl = ElementImpl {};
    let element: &dom::Element = &element_impl;
    println!("{}", element.tag_name());
}
```

最初の例との一貫性を考えるなら，本来呼び出せてはいけないはずだと思われます．そのため，バグではないかと疑っていますが，まだ[調査中](https://users.rust-lang.org/t/calling-a-method-on-a-trait-object-without-importing-its-trait-definition/22179)です．多分，`dom::Element`が使えてしまうことが問題の根本原因だと思われます．

これが仕様なのかどうなのか，ご存知の方がいたらコメントください．

# 変数に束縛したミュータブルな参照を，同じ型の別の変数に代入した場合の動作

例えば，以下のようなコードをコンパイルすると

```rust:example-1
let mut i = 0;
let r = &mut i;
let s = r;
let t = r;
```

```
error[E0382]: use of moved value: `r`
 --> src/lib.rs:5:5
  |
4 | let s = r;
  |     - value moved here
5 | let t = r;
  |     ^ value used here after move
  |
  = note: move occurs because `r` has type `&mut i32`, which does not implement the `Copy` trait
```

`&mut i32`は`Copy`を実装していないので，`r`の値が`s`に移動され，その結果コンパイルエラーになります．

ところが，以下のように関数呼び出しに変えるとコンパイルエラーにはなりません．

```rust:
let mut i = 0;
let r = &mut i;
func(r);
let s = r;

fn func(x: &mut i32) {}
```

関数呼び出しで値が移動してしまうと，`&mut self`なメソッドを１回しか呼び出せなくなってしまうので妥当な動作だとは思います．しかし，一体何が起きているのかよくわかりません．

## 再借用

同様の疑問を持った人がRedditに投稿しています．

* [Why can I use an &mut reference twice? : rust](https://www.reddit.com/r/rust/comments/46qwjv/why_can_i_use_an_mut_reference_twice/)

どうやら，ミュータブルな参照を束縛した変数を，同じ型（ミュータブルな参照）の変数に代入した場合，再借用が行われるという動作になっているとのことです．

以下のコードで再借用を確認できます．

```rust:example-2
let mut i = 0;
let r = &mut i;
let s: &mut i32 = r;
let t: &mut i32 = r;
```

```
error[E0499]: cannot borrow `*r` as mutable more than once at a time
 --> src/lib.rs:5:19
  |
4 | let s: &mut i32 = r;
  |                   - first mutable borrow occurs here
5 | let t: &mut i32 = r;
  |                   ^ second mutable borrow occurs here
6 | }
  | - first borrow ends here
```

`example-1`とエラー内容が異なります．

どちらの例でも`s`は`&mut i32`になると考える人が多いと思いますが，MIRを見ると型が違うことが分かります．

```rust:example-1
let s = r;  // let _3: &mut i32;
```

```rust:example-2
let s: &mut i32 = r;  // let _3: &mut i32 as Canonical { variables: [CanonicalVarInfo { kind: Region }], value: &mut i32 };
```

`example-1`の`s`は，型推論により`&mut i32`となり，`&mut i32`は`Copy`を実装していないので値が移動します．

一方，`example-2`の`s`は，`&mut i32`と型を明示的に指定しましたが，コンパイラにより`Canonical { variables: [CanonicalVarInfo { kind: Region }], value: &mut i32 }`という型に書き換えられています．

TRPLのどこにも書かれていませんが，`let i: i32`などと型を明示した場合，`Canonical`へと変換されるようです．

2019-07-28追記：[こちらの記事](https://qiita.com/reismannnr2/items/a7e4ed098bcf0c7ed8d2)に再借用となる条件について記述されているページへのリンクがあります．