私（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

 

• rustで単方向リスト＋単体テスト – Qiita

 

Learning Rust With Entirely Too Many Linked Lists

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

Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time – Stack Overflow

Non-Lexical LifetimeのRFCはこちら．2018-10-30時点では，#![feature(nll)]はNightlyでのみ動作します．

モジュールの宣言

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

• main.rs

 

• lib.rs

 

mod.rs

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

mod cat;

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

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で提案されているようです．

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

理由については[WIP] rustcが生成するコードの調査を見てください．

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

rustで動的にバッファを確保する方法 – 睡分不足

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

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

一連のコピーコストを改善するため配置構文というものが提案されていましたが，すでにunstableからも削除されています．詳細については[WIP] rustcが生成するコードの調査を見てください．

比較演算子

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

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

1 == 1;
&1 == &1;

// 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()の呼び出しです．上記の例はi32の例ですが，std::cmp::PartialEqは個別に実装可能なので，比較対象のオブジェクトごとに動作が異なります．殆どの場合，アドレス比較ではなく，内容の比較が行われるようです．

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

1 == &1;
&1 == 1;

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

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

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

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

アドレス比較したいときは素直にstd::ptr::eq()を使いましょう．これなら引数の順番に関係なくアドレス比較できます．

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

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

Rustは，ミュータブルな参照に関して安全性のため不寛容なルールを持っています．そのため，ミュータブルなグラフ（またはそれに類するリンク構造）上で１つ以上の被参照を持つノードのエッジを表現する場合には工夫が必要です．

• SimonSapin/rust-forest: A tree of reference-counted nodes, with RefCell for mutability

 

saschagrunert/indextree: Arena based tree ? structure by using indices instead of reference counted pointers

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

Cell<option<&’a Node<‘a, T>>>を使う

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

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のジェネリックパラメーターを含む必要があります．

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

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

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

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>>>を使う

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

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>>

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

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,
}

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

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

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

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

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

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

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

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

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

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

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してなくてもメソッドを呼び出せる

ドキュメントにもちゃんと書いてありますが，スコープ内のトレイトのみが適用されます．

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());
}

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

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());
}

最初の例との一貫性を考えるなら，本来呼び出せてはいけないはずだと思われます．そのため，バグではないかと疑っていますが，まだ調査中です．多分，dom::Elementが使えてしまうことが問題の根本原因だと思われます．

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

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

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

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に移動され，その結果コンパイルエラーになります．

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

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

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

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

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を見ると型が違うことが分かります．

let s = r;  // let _3: &mut i32;

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追記：こちらの記事に再借用となる条件について記述されているページへのリンクがあります．