Rustの `Arc` を読む(3): Rcを読む発展編

概要: Rustの `Arc` 型の実装は宝の宝庫です。そこで、これを隅から隅まで解説してみます。

第3回「Rcを読む発展編」では、 `Arc` のシングルスレッド版である `Rc` のソースコードを読み、 `Rc` の細部から Rust のさまざまな機能を読み解きます。

- [第1回 Arc/Rcの基本](https://qiita.com/qnighy/items/4bbbb20e71cf4ae527b9)
- [第2回 Rcを読む基本編](https://qiita.com/qnighy/items/5b2fbf27e3ee36e57b8d)
- **第3回** Rcを読む発展編
- [第4回 アトミック変数とメモリ順序](https://qiita.com/qnighy/items/b3b728adf5e4a3f1a841)
- [第5回 Arcを読む](https://qiita.com/qnighy/items/35db580a139d21f38410)

# はじめに

第2回で `Rc` の基本的な部分は掴めたはずなので、第2回で扱わなかった部分を拾っていきます。前回は参照カウンタの一般論が多かったと思いますが、今回はRust特有の話が多めです。

# まとめ

- Rustの標準ライブラリは要求するプラットフォームサポートに応じて3段階に分けられているが、 `Rc` はアロケーションに依存し、OSに依存しないため2段階目にあたる `alloc` に定義されている。
- Rustは高速なリリースサイクルとコンパイラの安定性、前方互換性を両立するために「機能の安定性」という概念を導入し、リリース可能な機能以外はnightlyビルドでのみ利用可能な仕組みを構築している。
- スマートポインタである `Rc` は参照先のメソッドとの衝突を防ぐため、`Rc` 自身に対する操作の多くはドット記法によるメソッド呼び出しではなく `Rc::foo` という形での呼び出しをする必要がある。
- ダミーの弱参照を作る方法があるが、その以前の実装は安全性に関してきわどい実装になっていたため2度の修正を経ている。
- `Rc` は参照先にサイズ不定型を使うことができるが、そのための追加のAPIは非常に興味深い。
  - 固定サイズの `Rc` をサイズ不定の `Rc` に変換するために `CoerceUnsized`, `DispatchFromDyn` が実装されている。
  - 一般のサイズ不定型の `Rc` を直接作成するための仕組みが `From` 実装としていくつか用意されており、Rustの高度なテクニックがいくつか見られる。
  - `RcBox` のレイアウトを計算する部分は安全性に関してきわどい実装や間違った実装になっていた時期があり、レイアウト計算の難しさを伺わせる。
  - スライスの `Rc<[T]>` を作るための仕組みは特殊化を駆使して効率的に実装されている。
- `Rc` はスレッドセーフではないが、この「スレッドセーフ」は実際には2つの概念 (`Send`/`Sync`) に分解される。
- `Rc` はデストラクタ(drop)を実装しているが、dropと `&T` と循環参照の微妙な機微を解決するために `#[may_dangle]` と `PhantomData` という道具が用いられている。
- `Rc` はエラーメッセージの調整のためだけにコンパイラに特別扱いされている。このためのフラグはユニットテストをうまく動かすために条件つきで付与されている。
- `Rc` の比較実装は場合によってはポインタ自体の比較と組み合わせて実装されるが、ここからは `PartialEq` と `Eq` の微妙な違いや特殊化とライフタイムの難しい関係が読み取れる。
- `Rc` には `Any`, `MaybeUninit`, `Pin` と組み合わせるためのサポートも用意されている。

# ソースコード

引き続き、以下の1.39.0の実装を読んでいきます。

https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs

# 定義されている場所

`Rc` は `src/liballoc/rc.rs` に定義されています。Rustコンパイラコードベースの慣習として `foo` というクレートは `src/libfoo` に入れることになっているので、これは `alloc` というクレートの `rc` というモジュールです。

実は、Rustの標準ライブラリは **`core`, `alloc`, `std` の3層構造**になっています。これは以下のように、プラットフォームの高級さに応じたAPIを提供する目的があります。

- `core` はRustがサポートする**ほとんどのプラットフォームが持っている基本機能** (メモリの読み書き、整数演算、ポインタ演算、スタック、関数呼び出しなど) にのみ依存するライブラリです。C言語におけるフリースタンディング環境 (freestanding environment) に近い概念です。
- `alloc` は `core` に加え、**動的メモリ確保** (いわゆる `malloc`/`free`) に依存する機能を足したライブラリです。
- `std` は `alloc` に加え、**OSの提供する機能** (スレッドの起動、ミューテックス、プロセスの起動、ファイルの読み書き、ソケット、環境変数、コマンドライン引数など) に依存する機能を足したライブラリです。C言語におけるホスト環境 (hosted environment) に近い概念です。

`Rc` は動的メモリ確保には依存しますが、OSの機能は使いません。そのため、 `alloc` で定義されています。

# 安定性アノテーション

`Rc` に限らず、標準ライブラリの実装にはほぼ漏れなく以下のような属性が付与されています。

```rust
#[stable(feature = "rust1", since = "1.0.0")]
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
pub struct Rc<T: ?Sized> {
    ptr: NonNull<RcBox<T>>,
    phantom: PhantomData<T>,
}

#[unstable(feature = "coerce_unsized", issue = "27732")]
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Rc<U>> for Rc<T> {}
```

これはRustの**安定性 (stability)**のためのアノテーションです。

Rustは**6週間に1回のマイナーリリース**という高速なリリースサイクルを採用しています。ここでいう「マイナー」とはsemantic versioningにおけるマイナー、つまり互換性を保った機能追加のことで、実際には重要な変更がたくさん含まれています。

リリースサイクルが高速であること自体は様々な利点がありますが、問題もあります。6週間で完全な実装ができる機能というのはそう多くありません。実装された機能が不完全なまま次のリリースに含まれてしまうと、互換性を保ったまま修正を加えるのは困難になります。Rustではそれぞれの機能を**安定な機能 (stable feature)**と**不安定な機能 (unstable feature)**に分けることでこの問題を解決しています。

- 安定な機能は、何もしなくても使えます。
- 不安定な機能は、 `#![feature(...)]` という宣言をすることではじめて使えるようになります。さらに、**この `#![feature(...)]` 宣言はnightly版のRustでのみ利用可能**で、betaやstableビルドでは使えないようになっています。

これによって、stableのユーザーは、完成して前方互換性が保証された機能だけを使うことができるようになっています。

ではこの「機能」の分類をどのように定義しているかというと、実は2つの方法があります。ひとつは[コンパイラそのものの「機能」](https://doc.rust-lang.org/unstable-book/language-features.html)を定義する方法で、[`syntax::feature_gate` モジュール](https://github.com/rust-lang/rust/tree/1.39.0/src/libsyntax/feature_gate) 内に機能の一覧がずらりと並んでいます。

もうひとつが[標準ライブラリの「機能」](https://doc.rust-lang.org/unstable-book/library-features.html)を定義する方法で、これが先ほど見た `#[stable]` と `#[unstable]` という2つの属性の役割です。これをつけることで、その機能をユーザーが使えるかどうかを決めることができます。

ただし、この「使える」ということの定義には注意が必要です。これは基本的に、 `#[stable]`/`#[unstable]` のついた定義を**名指しできるか**だと考えればよいです。たとえば、 `CoerceUnsized` そのものは `#[unstable]` がついています。これは `CoerceUnsized` を名指しすること (たとえば、 `CoerceUnsized` を自分の定義した型に実装したり、 `CoerceUnsized` を要求する関数を書いたりすること) が禁止されているだけで、 `CoerceUnsized` の恩恵を受けること (つまり、 `Arc<i32>` を `Arc<dyn Any>` に変換したりすること) は禁止されていません。

# `this` 引数

`Rc` のメソッドで、レシーバが `self` のものと `this` のものがあることに気付いたでしょうか。たとえば[`downgrade`](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L620-L626)の実装と[`inc_weak`](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L2014-L2025)の実装は以下のようになっていました。

```rust
impl<T: ?Sized> Rc<T> {
    // 第一引数はthis
    pub fn downgrade(this: &Self) -> Weak<T> {
        this.inc_weak();
        // Make sure we do not create a dangling Weak
        debug_assert!(!is_dangling(this.ptr));
        Weak { ptr: this.ptr }
    }

    // 第一引数はself
    fn inc_weak(&self) {
        let weak = self.weak();
        if weak == 0 || weak == usize::max_value() {
            unsafe { abort(); }
        }
        self.inner().weak.set(weak + 1);
    }
}
```

ここで **`this` は通常の識別子**であるのに対して **`self` は予約語**で特別な役割があります。「`impl` 内の関数の第一引数で、 `Self`, `&Self` など特定の型をもつものにしか使えない」という制約のかわりに、 `self` にはいくつかの特典があります:

- `self: &Self` を `&self` と略記できる。
- 第一引数が `self` の場合はメソッド記法 (`receiver.method()`) で呼び出せる。
- `self` 引数のライフタイムはlifetime elision規則で特別扱いされる。
- `self` 引数をもつことはメソッドがオブジェクト安全であるために必要な条件のひとつである。

さて、こんなに多くの特典があるのになぜわざわざ `this` にするのか、それは2つ目に挙げた**メソッド記法**を意図的に回避するためです。実際、 `Arc::downgrade` を以下のように呼び出すことはできません:

```rust
use std::rc::Rc;

fn main() {
    let rc = Rc::new(42);
    let _weak = rc.downgrade();
    //~^ERROR no method named `downgrade` found for type `std::rc::Rc<{integer}>` in the current scope
    //~|NOTE found the following associated functions; to be used as methods, functions must have a `self` parameter
    //~|NOTE the candidate is defined in an impl for the type `std::rc::Rc<_>`
}
```

このことは [`Rc` のドキュメント](https://doc.rust-lang.org/std/rc/struct.Rc.html)にもはっきり書いてあります:

> The inherent methods of `Rc` are all associated functions, which means that you have to call them as e.g., [`Rc::get_mut(&mut value)`](https://doc.rust-lang.org/std/rc/struct.Rc.html#method.get_mut) instead of `value.get_mut()`. This avoids conflicts with methods of the inner type `T`.)

訳:

> `Rc` の固有「メソッド」はすべて関連関数です。つまり、 `value.get_mut()` とは書けずに [`Rc::get_mut(&mut value)`](https://doc.rust-lang.org/std/rc/struct.Rc.html#method.get_mut) という風に呼ぶ必要があります。これにより内部の型 `T` のメソッドとの衝突を回避しています。

## 非公開APIの `self`

ドキュメントには書かれていませんが、今まで読んできた非公開APIはみな `self` を使っていたと思います。 `Rc` 自身の実装に使うだけなら、メソッド名の衝突は心配しなくていいので、特に気にせず `self` を使っているという寸法です。実際のメソッド解決のときは可視性を考慮しながら探索されるので、非公開APIの存在によって外から見たメソッド解決がおかしくなる心配はありません。

## トレイト実装の `self`

先ほどのドキュメントには「固有 (inherent)」という限定がありました。これは、「トレイトではなく型に紐付いた実装」ということを意味しています。実際、たとえば `Clone` の実装では `self` 引数が使われています。

```rust
impl<T: ?Sized> Clone for Rc<T> {
    fn clone(&self) -> Rc<T> { ... }
    //        ^^^^
}
```

でもこれは仕方ありません。`x.clone()` という形で呼べるというのは `Clone` が要求する性質の一つだからです。「`Rc<T>` は `Clone` という性質を満たす」という表明である以上、ここで `this` 引数を持ち出すことはできません (コンパイルエラーになります)。

ですから、以下のようにして `Rc<T>` の浅いコピーを作ることができるわけです。

```rust
use std::rc::Rc;

fn main() {
    let rc = Rc::new(42);
    let _rc2 = rc.clone();
}
```

ただ、この書き方は混乱のもとであるという主張もあり、以下のように明示することを推奨する人もいます (本稿の著者はこの意見には反対で、普通に `.clone()` を呼ぶ派です)。

```rust
use std::rc::Rc;

fn main() {
    let rc = Rc::new(42);
    let _rc2 = Rc::clone(&rc);
}
```

なお、 `Rc`, `Arc` に対する `.clone()` 呼び出しをチェックする[`clone_on_ref_ptr`](https://rust-lang.github.io/rust-clippy/v0.0.212/index.html#clone_on_ref_ptr)というlintがclippyに存在します。 `Rc::clone(&rc)` を推奨したい場合はこのlintを使うといいでしょう。

## `T` が特定の型の場合

`T` が特定の型の場合は、意図しない衝突は防げるため必ずしも `self` を回避する必要はありません。あとで紹介する `Arc<dyn Any>` がその例です。

(`String` や `Vec<T>` が `Deref` を実装しているにもかかわらず `self` 引数を多用するのも同じ理由です)

# ぶら下がり弱参照

`Weak` は弱参照なので、参照先の**実体がもはや存在していない場合 (ぶら下がり弱参照; dangling weak reference)**があります。以下のように `Rc` を作ってdowngradeし、元の `Rc` を捨てることでそのような `Weak` を作ることはできます。

```rust
let weak = Rc::downgrade(&Rc::new(42));
assert!(weak.upgrade().is_none());
```

しかし、何らかの都合で (番兵などのために) ダミーの弱参照が欲しい場合に、わざわざ実体のある `Rc` を作ってから `Weak` にするのは無駄感があります。そこで `Weak` にはダミーの弱参照を生成するための [`Weak::new`](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L1604-L1609) が用意されています。

実はこの `Weak::new` の実装はここ最近2回も変化しています。もともと[`Weak::new` が導入されたタイミング](https://github.com/rust-lang/rust/commit/cae91d7c8c21aa860bda29c62207a6726837952b)は以下のような実装になっていました。 (今風に少し変更しています)

```rust
impl<T> Weak<T> {
    pub fn new() -> Weak<T> {
        unsafe {
            Weak {
                ptr: Box::into_raw_non_null(box RcBox {
                    strong: Cell::new(0),
                    weak: Cell::new(1),
                    value: uninitialized(),
                }),
            }
        }
    }
}
```

この時点ではきわめて自然な作り方になっていました。ただし、このように `uninitialized` を使う構成は意味論が整理された今では即時の未定義動作 (instant UB) であるとされており非推奨です。 `NonNull<RcBox<MaybeUninit<T>>>` を作ってからキャストするほうが安全です。

ともあれ、この方法は無駄だと考えられ、以下のように[実装が変更されました](https://github.com/rust-lang/rust/commit/41730b7e2e2c28a13fe6d08a7ad47d31d68eccea):

```rust
impl<T> Weak<T> {
    pub fn new() -> Weak<T> {
        Weak {
            ptr: NonNull::dangling(),
        }
    }
}
```

ここで出てくる [`NonNull::dangling` の実装は以下のようになっています](https://github.com/rust-lang/rust/blob/1.39.0/src/libcore/ptr/non_null.rs#L56-L74)。

```rust
impl<T: Sized> NonNull<T> {
    pub const fn dangling() -> Self {
        unsafe {
            let ptr = mem::align_of::<T>() as *mut T;
            NonNull::new_unchecked(ptr)
        }
    }
}
```

0ではないダミーのポインタを返すようになっています。ところでこのドキュメントには以下のような注釈があります。

> Note that the pointer value may potentially represent a valid pointer to
> a `T`, which means this must not be used as a "not yet initialized"
> sentinel value. Types that lazily allocate must track initialization by
> some other means.

訳:

> 返されるポインタは `T` を参照する有効なポインタかもしれないことに注意してください。
> つまり、この値を「まだ初期化されていない」ということを表す番兵として使ってはいけないということです。
> メモリ確保を遅延して行うような型を実装する場合は、別途初期化状態を追跡する必要があります。

上記の `Weak::new` の実装はこれを守っていないように見えますね。実際その問題があって[実装が以下のように変更されています](https://github.com/rust-lang/rust/commit/33b8f6253fe18af5bc882cf885d68538c90dab62)。

```rust
impl<T> Weak<T> {
    pub fn new() -> Weak<T> {
        Weak {
            ptr: NonNull::new(usize::MAX as *mut RcBox<T>).expect("MAX is not 0"),
        }
    }
}
```

`RcBox<T>` は `usize` を含むので、少なくとも2でアラインされているはず(※Rustのポインタは最低2バイト)です。したがって、奇数である `usize::MAX` が有効なポインタと衝突する可能性はありません。また `RcBox` は最低4バイトあるので、アドレス空間のギリギリ端っこである `usize::MAX` から先に入るわけはありません。

前回までに紹介したソースコードでは簡略化していましたが、この仕様により **`Weak` の操作ではまずダミー値である `usize::MAX` との比較を行う必要があります**。たとえば、 [`Weak::clone` の実際のコード](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L1921-L1941)は以下のようになっています。

```rust
impl<T: ?Sized> Clone for Weak<T> {
    fn clone(&self) -> Weak<T> {
        if let Some(inner) = self.inner() {
            inner.inc_weak()
        }
        Weak { ptr: self.ptr }
    }
}
```

`self.inner()` がダミー値との比較をして、 `None` か `Some` を返すようになっています。

# サイズ不定型

前回も少し言及しましたが、 `Rc` の定義では以下のように `T: ?Sized` が指定されています。

```rust
pub struct Rc<T: ?Sized> {
    //        ^^^^^^^^^
    ptr: NonNull<RcBox<T>>,
    phantom: PhantomData<T>,
}
```

これにより `Arc<dyn Fn() -> bool>` や `Rc<dyn Any>` などを扱えるようになっています。

前回は `Rc` がサイズ不定型をサポートするためのコードは読み飛ばしていたので、ここで順番に見ていきたいと思います。

## サイズ不定型の `Drop`

当然ながら、デストラクタである `Drop` はありえる全ての型を網羅するように実装する必要があります。サイズ不定型も例外ではありません。

特に問題となるのが、ヒープ領域の解放処理です。ヒープ領域の解放処理は以下のようになっています。

```rust
Global.dealloc(self.ptr.cast(), Layout::for_value(self.ptr.as_ref()));
```

Rustでメモリを解放するにはこの `Global.dealloc` か、その前身である `std::alloc::dealloc` を使います。この `dealloc` は以下の2つの引数を取ります。

- 解放する領域の先頭を指すポインタ
- 解放する領域のレイアウト (サイズとアラインメントの対)

**C言語の `free` とは異なり、解放時もサイズとアラインメントを指定する必要がある**というのは注目に値します。これにより、より効率的なアロケーターを実装する余地を残しています。とはいえ、デフォルトではシステムアロケーター (OSが提供する `malloc`/`free` 実装) を使うので、実際にはこのレイアウト情報は捨てられていると思われます。

さてそのレイアウト情報ですが、サイズ固定型の場合は簡単で、型自体にサイズとアラインメントが決められています。 (その場合は `Layout::new::<T>()` で取得できます。)

しかしサイズ不定型の場合は同じ型でも異なるサイズやアラインメントを取る可能性があります。その場合でもfat pointerのメタデータ領域からサイズとアラインメントを取得できます。

```rust
// サイズ不変型のサイズとアラインメントはfat pointerのメタデータから取得できる。
let x: &dyn Send = &42_i32;
let y: &dyn Send = &42_i64;

assert_eq!(std::mem::size_of_val(x), 4);
assert_eq!(std::mem::size_of_val(y), 8);
```

ここでは `self.ptr.as_ref()` で `&RcBox<T>` 参照を作って、そのレイアウトを `Layout::for_value` で取得しています。この時点で `T` は解放済みなので、 `&RcBox<T>` という値を生成していいかは際どいところですが、 `T` は「解放済み」であって「未初期化」ではない (所有権が失われているだけで、元々あった値は入っている) ため、問題ないと考えられます。

## サイズ不定型への変換 (型強制)

Rustにはいくつか暗黙の型変換 (型強制; coercion) が実装されています。そのうちのひとつが**サイズ不定型への型強制 (unsized coercion)**です。

```rust
use std::any::Any;

fn main() {
    // トレイトオブジェクトへの型強制
    let x: &(dyn Any + Send + Sync) = &42_i32; // &i32
    // スライスへの型強制
    let y: &[i32] = &[1, 2, 3]; // &[i32; 3]
    // サイズ不定型の自動トレイト境界を取り除く型強制
    let z: &dyn Any = x; // &(dyn Any + Send + Sync)
}
```

これは `Rc`/`Arc` や `Weak` でも動作するようになっています。

```rust
use std::any::Any;
use std::rc::Rc;

fn main() {
    // トレイトオブジェクトへの型強制
    let x: Rc<dyn Any + Send + Sync> = Rc::new(42_i32); // Rc<i32>
    // スライスへの型強制
    let y: Rc<[i32]> = Rc::new([1, 2, 3]); // Rc<[i32; 3]>
    // サイズ不定型の自動トレイト境界を取り除く型強制
    let z: Rc<dyn Any> = x; // Rc<dyn Any + Send + Sync>
}
```

型強制ができる条件はやや難しいですが、大雑把には以下のように2段階で考えることになります。

- ある型 `T` を**メモリ上の表現はそのまま**に `U` と見なせるとき、
- それを包んだポインタ `Ptr<T>` を**別の表現のポインタ** `Ptr<U>` に変換できる

この2段階の条件にあわせて2つのトレイト `Unsize` と `CoerceUnsized` が用意されています。たとえば、

- `i32` はメモリ上の表現はそのままに `dyn Any + Send + Sync` と見なせる (`i32: Unsize<dyn Any + Send + Sync>`)
- そのため、 `&i32` を別の表現のポインタである `&(dyn Any + Send + Sync)` に変換できる (`&i32: CoerceUnsized<&(dyn Any + Send + Sync)>`)

となります。

ユーザー定義のポインタ型である `Rc`/`Arc`/`Weak` でこれらの型強制を使えるようにするには、明示的にトレイトを実装する必要があります。それをしているのが以下の行です。

```rust
impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Rc<U>> for Rc<T> {}
impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Weak<U>> for Weak<T> {}
```

上のコードから推測がつくように、 `CoerceUnsized` はマーカートレイト (実体のないトレイト) ですが、実装してよい条件が決まっていてコンパイラに検査されます。 (その意味では `Copy` と似ています)

この場合は以下のようにチェックされます。

- `Rc<T>: CoerceUnsized<Rc<U>>`
- ↑ `NonNull<RcBox<T>>: CoerceUnsized<NonNull<RcBox<U>>>` (主要なフィールドに注目)
- ↑ `RcBox<T>: Unsize<RcBox<U>>` (参照先に注目)
- ↑ `T: Unsize<U>` (最後のフィールドに注目)
- ↑ これは元々の `impl` の前提 (トレイト境界) に含まれる。

残念ながら `CoerceUnsized` は1.39.0時点では不安定機能なので、サードパーティーのクレート内でユーザー定義型に実装することはできません。

## `self` レシーバと動的ディスパッチ

**`self` 引数に指定できる型は限られる**という話はすでに書いたと思いますが、その型のレパートリーは増えつつあります。元々は以下の4つの型のみが対象でした。

- `Self`
- `&Self`
- `&mut Self`
- `Box<Self>`

1.33.0で [`#![feature(arbitrary_self_types)]`](https://github.com/rust-lang/rust/issues/44874) の[一部が安定化](https://github.com/rust-lang/rust/commit/153f5a7892274764256862692fa7e2c51474e5d0)され、以下の型も `self` の型として使えるようになりました。

- `Arc<Self>`
- `Rc<Self>`
- `Pin<&Self>`, `Pin<&mut Self>`, `Pin<Box<Self>>`, `Pin<Arc<Self>>`, `Pin<Rc<Self>>`

ここまでで、「すでに `Rc` をレシーバに取るメソッドがあったではないか」と疑問に思う人もいるかもしれません。たとえばこういう(感じの)関数が定義されていました。

```rust
impl<T: ?Sized> Rc<T> {
    fn inner(&self) -> &RcBox<T> { ... }
}
```

これは今までは定義できなかったのでしょうか。そんなことはありません。なぜなら、**この場合は `Rc` そのものが `Self` だから**です。そうではなく、次のように `Rc` そのものが `Self` ではないときに有用になったのが最近の変更点です。

```rust
use std::rc::Rc;

struct A;

impl A {
    // `Self` はRcではないが、 `self` の型は Rc
    fn foo(self: Rc<Self>) { ... }
}
```

これができるようになって最も嬉しいのが、**これらのポインタ型を動的ディスパッチに使うことができる**という点です。

```rust
use std::sync::Arc;
use std::thread::spawn;

// マルチスレッドで挨拶をする
pub trait Greet {
    fn greet(self: Arc<Self>);
}

#[derive(Debug)]
pub struct Greeter(String);

impl Greet for Greeter {
    fn greet(self: Arc<Self>) {
        let this = self.clone();
        let thread1 = spawn(move || {
            println!("thread1: {}", this.0);
        });
        let thread2 = spawn(move || {
            println!("thread2: {}", self.0);
        });
        thread1.join().unwrap();
        thread2.join().unwrap();
    }
}

fn main() {
    let greeter: Arc<dyn Greet> = Arc::new(Greeter("hello!".to_owned()));
    greeter.greet();
}
```

さてこの「`self` に指定できる」と「動的ディスパッチできる」は現在、トレイトで管理されています。 `Rc` に関してこれらを可能にしているのが以下の実装です。

```rust
impl<T: ?Sized> Receiver for Rc<T> {}
impl<T: ?Sized + Unsize<U>, U: ?Sized> DispatchFromDyn<Rc<U>> for Rc<T> {}
impl<T: ?Sized + Unsize<U>, U: ?Sized> DispatchFromDyn<Weak<U>> for Weak<T> {}
```

`Receiver` は隠しトレイト、 `DispatchFromDyn` は不安定トレイトなので、ユーザー定義型に対して実装することはまだできません。

ところで、 `DispatchFromDyn` は `CoerceUnsized` とよく似ていることに気付いたでしょうか。実のところ**動的ディスパッチ (dynamic dispatch) はサイズ不定型への型強制 (unsize coercion)の逆操作**と考えることができます。たとえば上の `Arc<dyn Greet>` の場合……

- 型強制 (`let greeter` の行) によって、 `Arc<Greeter>` が `Arc<dyn Greet>` に変換される。このときメタデータとして仮想関数テーブル (vtable) へのポインタが付与される。
- 動的ディスパッチ (`greeter.greet()`) では、 `Arc<dyn Greet>` に付与された仮想関数テーブルを使って実際の実装 (`Greeter::greet`) を探す。呼び出す側は元の型を忘れてしまっているが、呼び出された側は元の型 (`Arc<Greeter>`) を知っている。

となります。この類似性を考慮して、 `CoerceUnsized` と `DispatchFromDyn` は同じ形の定義が採用されたのだと思われます。

なお、 `Weak` が `DispatchFromDyn` を実装している理由は謎です。おそらく現時点では意味がないですが、将来 `self` 型として使えるようになる可能性を考慮して実装したのかもしれません。

## サイズ不定版の `new`

ここまでで `Rc` の作り方は、型強制によるものしか紹介してきませんでした。しかしこれでは不十分なケースもそれなりにあります。たとえば、型強制を使えば `Rc<[i32]>` を作ることができました:

```rust
let x: Rc<[i32]> = Rc::new([1, 2, 3]);
```

しかしこれは `Rc<[i32; 3]>` を経由して作っているので、決まった長さのものしか作ることができません。実行時に好きな長さの `Rc<[T]>` を作るには別の方法が必要です。

そもそも、 `Rc<[T]>` を直接作ることができないのは `Rc::new` が `T: Sized` を要求するせいです:

```rust
// T: Sized が仮定されている
impl<T> Rc<T> {
    // valueを値渡ししているので、 T: Sized が必要
    pub fn new(value: T) -> Rc<T> { ... }
}
```

`T` 型の値をムーブで渡しているので、サイズ不定右辺値 (unsized rvalues) が実験的な機能にとどまっている現状では `Rc::new` 自体の制約を緩和することはできません。ではどうすればいいでしょうか。 **`T` ではなく `Box<T>` を渡せばいい**ですね。実は [`Rc::from` (の実装のうちのひとつ)](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L1414-L1420) がまさにそれをしています。

```rust
impl<T: ?Sized> From<Box<T>> for Rc<T> {
    fn from(v: Box<T>) -> Rc<T> {
        Rc::from_box(v)
    }
}

impl<T: ?Sized> Rc<T> {
    /// Allocates an `RcBox<T>` with sufficient space for
    /// a possibly-unsized value where the value has the layout provided.
    ///
    /// The function `mem_to_rcbox` is called with the data pointer
    /// and must return back a (potentially fat)-pointer for the `RcBox<T>`.
    unsafe fn allocate_for_layout(
        value_layout: Layout,
        mem_to_rcbox: impl FnOnce(*mut u8) -> *mut RcBox<T>
    ) -> *mut RcBox<T> {
        // Calculate layout using the given value layout.
        // Previously, layout was calculated on the expression
        // `&*(ptr as *const RcBox<T>)`, but this created a misaligned
        // reference (see #54908).
        let layout = Layout::new::<RcBox<()>>()
            .extend(value_layout).unwrap().0
            .pad_to_align().unwrap();

        // Allocate for the layout.
        let mem = Global.alloc(layout)
            .unwrap_or_else(|_| handle_alloc_error(layout));

        // Initialize the RcBox
        let inner = mem_to_rcbox(mem.as_ptr());
        debug_assert_eq!(Layout::for_value(&*inner), layout);

        ptr::write(&mut (*inner).strong, Cell::new(1));
        ptr::write(&mut (*inner).weak, Cell::new(1));

        inner
    }

    /// Allocates an `RcBox<T>` with sufficient space for an unsized value
    unsafe fn allocate_for_ptr(ptr: *const T) -> *mut RcBox<T> {
        // Allocate for the `RcBox<T>` using the given value.
        Self::allocate_for_layout(
            Layout::for_value(&*ptr),
            |mem| set_data_ptr(ptr as *mut T, mem) as *mut RcBox<T>,
        )
    }

    fn from_box(v: Box<T>) -> Rc<T> {
        unsafe {
            let box_unique = Box::into_unique(v);
            let bptr = box_unique.as_ptr();

            let value_size = size_of_val(&*bptr);
            let ptr = Self::allocate_for_ptr(bptr);

            // Copy value as bytes
            ptr::copy_nonoverlapping(
                bptr as *const T as *const u8,
                &mut (*ptr).value as *mut _ as *mut u8,
                value_size);

            // Free the allocation without dropping its contents
            box_free(box_unique);

            Self::from_ptr(ptr)
        }
    }
}
```

いきなり大量のコードになってしまいました。基本的にやりたいことは `Rc::new` と同じなのですが、サイズ不定型を直接扱おうとするとどうしても難しくなってしまうようです。

### レイアウト計算

まず `allocate_for_layout` から始めましょう。

```rust
// Calculate layout using the given value layout.
// Previously, layout was calculated on the expression
// `&*(ptr as *const RcBox<T>)`, but this created a misaligned
// reference (see #54908).
let layout = Layout::new::<RcBox<()>>()
    .extend(value_layout).unwrap().0
    .pad_to_align().unwrap();
```

まずこの部分からです。 `Rc::new` ではまず `RcBox` の中身を完全に作ってからメモリを確保していましたが、サイズ不定の場合は安易にスタック上に保管できないので、**まずメモリを確保してから中身を埋めていく**ことになります。上の行は確保すべきメモリのサイズを計算しています。

何やらコメントで、過去のバグに言及していますね。[修正前](https://github.com/rust-lang/rust/commit/d60290fc63bcc19714abb7fad2c01cf2efe91efa)は以下のコードでした。

```rust
// Create a fake RcBox to find allocation size and alignment
let fake_ptr = ptr as *mut RcBox<T>;

let layout = Layout::for_value(&*fake_ptr);
```

今よりずっとシンプルですが、何やらかなり際どいことをしていますね。本来 `T` に対する参照を `RcBox<T>` に対する参照とみなしています。この2つは全然違うものです。というかこのas変換、通るんですね。

案の定これはアウトでした。たしかに正しいレイアウトが計算されます (←現状の実装では参照先を `RcBox` のような構造体で包んでもfat pointerの形式は一緒。コンパイラと一緒に提供される標準ライブラリ内ではこの性質に依存してもかまわない) が、 `&RcBox<T>` という参照型を作った時点で不適切な参照になってしまいます。 `T` がたとえば `[u8]` だったとすると、 `ptr` は奇数かもしれませんが、 `RcBox<T>` はアラインメント2以上 (通常4～8) なのでアラインメント違反になります。

これは一旦次のように修正されます。

```rust
// Calculate layout using the given value.
// Previously, layout was calculated on the expression
// `&*(ptr as *const RcBox<T>)`, but this created a misaligned
// reference (see #54908).
let (layout, _) = Layout::new::<RcBox<()>>()
    .extend(Layout::for_value(&*ptr)).unwrap();
```

実はこれには不備があり、最終的に以下のように[修正されました](https://github.com/rust-lang/rust/commit/317f494c72aead3fecd73788569983fd2f8ea8a3)。

```rust
// Calculate layout using the given value.
// Previously, layout was calculated on the expression
// `&*(ptr as *const RcBox<T>)`, but this created a misaligned
// reference (see #54908).
let layout = Layout::new::<RcBox<()>>()
    .extend(Layout::for_value(&*ptr)).unwrap().0
    .pad_to_align().unwrap();
```

さて、この正しい実装は `RcBox<T>` のレイアウトを正攻法で計算しています。つまり、まず `RcBox` の冒頭部

```rust
struct RcBox<T: ?Sized> {
    strong: Cell<usize>,
    weak: Cell<usize>,
    // ...
}
```

のレイアウトを、 `RcBox<()>` を使って計算しています。そして、その後最後のフィールド

```rust
// ...
    value: T,
// ...
```

のレイアウトを `Layout::for_value(&*ptr)` として計算し、この2つをうまく「組み合わせ」ています。

ところで、この「組み合わせ」はなぜうまくいくと言えるのでしょうか。それを考えるには、まず「C-like struct」と「Rust-like struct」について説明する必要があります。**以下に述べるレイアウトの詳細にはコンパイラの内部仕様も含まれていますが、コンパイラと一緒に配布される標準ライブラリではこれらの詳細に依存することが許されています**。

C-like structはCで採用されている構造体レイアウトです。たとえば、以下の構造体はサイズ12, アラインメント4です。

```rust
#[repr(C)]
struct Foo {
    x: u8,
    y: u32,
    z: u8,
    w: u8,
}

fn main() {
    assert_eq!(std::mem::size_of::<Foo>(), 12);
    assert_eq!(std::mem::align_of::<Foo>(), 4);
}
```

**C-like structのレイアウト**は、各フィールドのアラインメントを維持しながら順番にフィールドを追加することで行われます。このとき、計算途中では**構造体サイズを構造体アラインメントの定数倍に調整しません** (追加するフィールドのアラインメントには揃えます)。

| |サイズ|アラインメント||
|---|---|---|---|
|初期|0|1| |
|`x` を追加|1|1| `x` の位置は0 |
|`y` を追加|8|4| `y` の位置は4 |
|`z` を追加|9|4| `z` の位置は8 |
|`w` を追加|10|4| `w` の位置は9 |
|アラインメント調整|12|4|

計算の途中でアラインメント調整してしまうと、 `z` と `w` の間に余計なパディングが挿入されてしまいます。

**Rust-like struct**は、これに加えて**フィールドの並び替え**が発生します。ただし、**最後のフィールドがサイズ不定型になりえる場合は、そのフィールドは常に最後に配置される**というルールがあります。たとえば上の `Foo` は `repr(Rust)` (デフォルト) ではより小さい8バイトになります。


```rust
struct Foo {
    x: u8,
    y: u32,
    z: u8,
    w: u8,
}

fn main() {
    assert_eq!(std::mem::size_of::<Foo>(), 8);
    assert_eq!(std::mem::align_of::<Foo>(), 4);
}
```

さて、これを踏まえると、先ほどのレイアウト計算は実際にはおおよそ以下のような構造体のレイアウトを計算していたことになります。

```rust
#[repr(C)]
struct RcBox_<T> {
    head: RcBox<()>,
    tail: T,
}
```

これと実際の `RcBox<T>` が等しくなるには以下の条件が満たされる必要があります。

- レイアウト計算では `RcBox<()>`→`T`の順番にフィールドを追加している。この順番が実態と一致している必要がある。
- レイアウト計算では `RcBox<()>` の最終的なレイアウトを計算してから `T` を追加しているので、 `RcBox<()>` の段階で一度構造体サイズの切り上げが発生している。これが実際にはパディングを生んでいないことを確かめる必要がある。

前者は、「最後のフィールドがサイズ不定型になりえる場合は、そのフィールドは常に最後に配置される」というルールによる保証されています。

後者は、 `RcBox<T>` の中身が2つの同じ型のフィールドのみからなることから確認できます。同じレイアウトの型をいくつ組み合わせても追加のパディングは発生しないからです。

これでようやく、レイアウト計算の正当性がわかりました。途中で起きたバグは構造体の最終パディングの追加忘れなので、たとえば64bit環境で長さ3の `Rc<[u8]>` を作るにあたって19byteの領域を確保してしまう (実際には全体のアラインメント8にあわせて24byteにする必要がある) という問題だとわかります。

### メモリ確保

レイアウト計算がいきなりハードで疲れたかもしれません。いったん休憩するといいかもしれません。

レイアウト計算ができたら、次はそのレイアウトにしたがってメモリを確保します。

```rust
// Allocate for the layout.
let mem = Global.alloc(layout)
    .unwrap_or_else(|_| handle_alloc_error(layout));
```

動的なレイアウトで動的メモリ確保をするために、 `Box::new` のかわりに、その内部で使われているグローバルアロケーター (`Global.alloc`, `std::alloc::alloc`) を使っています。注目するべきは `handle_alloc_error` でしょうか。

`handle_alloc_error` は動的メモリ確保に失敗した場合に呼ぶべきフックです。最近は[`try_reserve`](https://github.com/rust-lang/rust/issues/48043)などのAPIも存在しますが、基本的に**メモリ不足のエラーから正しく復帰するのは[困難](https://eli.thegreenplace.net/2009/10/30/handling-out-of-memory-conditions-in-c)**と考えられています。 `handle_alloc_error` はそのような前提に立ったAPIで、以下のどちらかの挙動をすることが期待されています。

- プロセスを強制終了する。
- [パニックによりスレッドを遡上して最低限の片付けをする](https://rust-lang.github.io/rfcs/2116-alloc-me-maybe.html)。

おそらくこの選択肢を選べるようにするためだと思うのですが、 `handle_alloc_error` は `panic` と同様に実装を選択できるような仕組みになっています。実際の実装は[以下のように与えることができます](https://docs.rust-embedded.org/book/collections/)。

```rust
#[alloc_error_handler]
fn on_oom(_layout: Layout) -> ! {
    // Do something and abort
}
```

パニックハンドラは公式に2種類 (`panic_unwind` と `panic_abort`) 提供されていますが、動的メモリ確保エラーハンドラは1種類だけのようです。これは `std::alloc` 内に[以下のように定義されています](https://github.com/rust-lang/rust/blob/1.39.0/src/libstd/alloc.rs#L165-L218)。

```rust
#[alloc_error_handler]
pub fn rust_oom(layout: Layout) -> ! {
    let hook = HOOK.load(Ordering::SeqCst);
    let hook: fn(Layout) = if hook.is_null() {
        default_alloc_error_hook
    } else {
        unsafe { mem::transmute(hook) }
    };
    hook(layout);
    unsafe { crate::sys::abort_internal(); }
}

fn default_alloc_error_hook(layout: Layout) {
    dumb_print(format_args!("memory allocation of {} bytes failed", layout.size()));
}
```

この `rust_oom` 自体が差し替え可能な構造になっていて、登録されているフック関数を実行後にプロセスを強制終了しています。このフックの登録の仕組みもパニックハンドラ (`take_panic_hook` / `set_panic_hook`) と似ています。

### メタデータ付与

確保したメモリは `NotNull<()>` 型です。これはメタデータを持たないthinポインタ(←→fatポインタ) なので、どこかからメタデータを持ってくる必要があります。 `Rc::allocate_for_layout` 自身はこの部分に関与せず、以下のようなブラックボックスがあるという前提で仕事をしています:

```rust
mem_to_rcbox: impl FnOnce(*mut u8) -> *mut RcBox<T>
```

したがって、この部分の処理は単に関数を呼んでいるだけです。

```rust
let inner = mem_to_rcbox(mem.as_ptr());
```

`allocate_for_layout` は何箇所かから呼ばれていますが、最も興味深いのは今読んでいる `allocate_for_ptr` の実装です:

```rust
// Allocate for the `RcBox<T>` using the given value.
Self::allocate_for_layout(
    Layout::for_value(&*ptr),
    |mem| set_data_ptr(ptr as *mut T, mem) as *mut RcBox<T>,
)
```

`set_data_ptr` は以下です:

```rust
/// Sets the data pointer of a `?Sized` raw pointer.
///
/// For a slice/trait object, this sets the `data` field and leaves the rest
/// unchanged. For a sized raw pointer, this simply sets the pointer.
unsafe fn set_data_ptr<T: ?Sized, U>(mut ptr: *mut T, data: *mut U) -> *mut T {
    ptr::write(&mut ptr as *mut _ as *mut *mut u8, data as *mut u8);
    ptr
}
```

気持ちとしては**「確保したポインタ (`data`) をベースに、メタデータを別の場所 (`ptr`) からコピーしてくる」**のですが、実際にやっているのは逆で、「fatポインタ (`ptr`) をベースに、データポインタを他の場所 (`data`) から持ってくる」という処理になっています。これは**fatポインタのデータポインタは最初の1ワードである**という内部レイアウトの知識に依存しているため、標準ライブラリ以外で使うのは危険ですが、実は[objekt](https://github.com/dtolnay/objekt)あたりはそれに依存しているようなのであまり深く考えなくてもいいのかもしれません。

さて、今回は `Box<T>` からコピーしているので手に入ったメタデータは `T` 用のものです。これを `RcBox<T>` 用のメタデータに変換する必要がありますが、実際は **`RcBox<T>` のようなunsized構造体のメタデータはその末尾 (`T`) のメタデータと一致する**という性質があるため、単なるポインタキャストで問題なく動きます。

### ヘッダ部分の初期化

手に入ったのは未初期化状態の `RcBox<T>` へのポインタなので、データを埋めていく必要があります。まずはヘッダ部分である `strong` と `weak` を初期化します。

```rust
ptr::write(&mut (*inner).strong, Cell::new(1));
ptr::write(&mut (*inner).weak, Cell::new(1));
```

未初期化領域に値をムーブして初期化状態にするには `ptr::write` が適切なので、ここではそれを使っています。 `&mut` を使っているせいで若干危なっかしい (`&mut T` は参照先が有効である必要がある) ですが、今回使っている `Cell<usize>` は全ての表現がvalidな型です。(逆に、invalidな表現を持つ型の例としては `bool` や `char` などがあります。) なのでおそらくギリギリ問題を回避していると思います。この部分をより堅牢に行うために[参照を経由せずにフィールドへのポインタを取得する構文](https://rust-lang.github.io/rfcs/2582-raw-reference-mir-operator.html)が入る予定です。これが入れば上記のコードは以下のようになるはずです。

```rust
ptr::write(&raw mut (*inner).strong, Cell::new(1));
ptr::write(&raw mut (*inner).weak, Cell::new(1));
```

ここまでで、「あとは中身を用意するだけ」な状態の `NonNull<RcBox<T>>` が手に入りました。

### 元データの移動

`from_box` に戻ります。前半はあんまり面白くないのでスキップします。 (興味深いのは `Unique` という内部向けの型が使われていることくらいです)

```rust
// Boxの分解
let box_unique = Box::into_unique(v);
let bptr = box_unique.as_ptr();

// 参照先のサイズをあらかじめ計算しておく
let value_size = size_of_val(&*bptr);
// ここまで読んだ実装を呼び出している
let ptr = Self::allocate_for_ptr(bptr);
```

さて、元々やりたかったことは `Box<T>` から `Rc<T>` への変換です。 `Box` 内にある `T` の内容を `Rc` 側に移す必要があります。

```rust
// Copy value as bytes
ptr::copy_nonoverlapping(
    bptr as *const T as *const u8,
    &mut (*ptr).value as *mut _ as *mut u8,
    value_size);
```

コピー元もコピー先もポインタなので、readでもwriteでもなくcopyを使うのがよさそうです。コピー元とコピー先に重複がないという知識を利用してより効率的な実装を使っています。 (これはC言語の `memcpy`/`memmove` と同じですね)

この時点で、コピー先である `NonNull<RcBox<T>>` は完全に初期化された状態になり、かわりに `Box<T>` は中身が取り出されて所有権を失った状態になりました。なので、 `Box<T>` の抜け殻 (ヒープ領域)だけ解放します。

```rust
// Free the allocation without dropping its contents
box_free(box_unique);
```

最後に、 `Rc<T>` 型になるように変換して以上です。

## イテレータからの生成

`Rc<[T]>` を生成する方法は他にも用意されています。まずは[イテレータから生成する以下の実装](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L1453-L1543)から。

```rust
impl<T> iter::FromIterator<T> for Rc<[T]> {
    fn from_iter<I: iter::IntoIterator<Item = T>>(iter: I) -> Self {
        RcFromIter::from_iter(iter.into_iter())
    }
}
```

`FromIterator` はイテレータの `collect` メソッドの戻り値が実装すべきトレイトなので、これはイテレータチェインの末尾で `.collect::<Rc<[_]>>()` とすることで `Rc<[T]>` を生成できることを意味しています。

そしてこれは別の `RcFromIter` というトレイトに処理を移譲しています。これは**特殊化トレイト (specialization trait)** といわれるパターンで、不安定機能である特殊化 ([RFC 1210](https://rust-lang.github.io/rfcs/1210-impl-specialization.html)) を使うために使われます。(標準ライブラリはコンパイラと一緒に配布されるため、不安定機能に依存することが許されています) 特殊化を使うと、**特定の条件を満たしているときだけ別の実装を使う**、ということができます。

今回は以下のように実装されています。

```rust
/// Specialization trait used for collecting into `Rc<[T]>`.
trait RcFromIter<T, I> {
    fn from_iter(iter: I) -> Self;
}

// 実装A
impl<T, I: Iterator<Item = T>> RcFromIter<T, I> for Rc<[T]> {
    default fn from_iter(iter: I) -> Self { ... }
}

// 実装B
impl<T, I: iter::TrustedLen<Item = T>> RcFromIter<T, I> for Rc<[T]>  {
    default fn from_iter(iter: I) -> Self { ... }
}

// 実装C
impl<'a, T: 'a + Clone> RcFromIter<&'a T, slice::Iter<'a, T>> for Rc<[T]> {
    fn from_iter(iter: slice::Iter<'a, T>) -> Self { ... }
}
```

通常、トレイトに対する実装は重複が禁止されていますが、包含関係にある場合は特殊化とみなされて例外的に重複が許されます。上の例では**実装CがBの特別な場合で、実装Bが実装Aの特別な場合**になっています。

この場合、**実装Aの条件に合致していても、実装Aの提供する `from_iter` が採用されない場合があります**。このことを明示的に許可するために、実装Aの `from_iter` には `default` 修飾子がついています。同様に実装Bにも `default` がついていますが、実装Cにはついていません。実装Cは今ある中で最も具体的な実装で、それ以上特殊化されることがないからです。

わざわざ特別な場合の実装が提供されていることから、おそらく**実装Cは実装Bより効率的で、実装Bは実装Aより効率的だ**と推測されます。

ところで、なぜ **`FromIterator` に直接 `default` をつけて特殊化しないのでしょうか**。この2つには実は大きな違いがあります。それは**特殊化がオープンかどうか**です。 `FromIterator` は公開トレイトなので、その実装に `default` をつけた場合下流クレートが特殊化を増やす余地が生まれます。上記のように `RcFromIter` という特殊化トレイトを別に用意することで、あくまで自分が把握している特殊化だけを行うことができるという寸法です。オープン特殊化とクローズド特殊化には双方メリット・デメリットが考えられますが、そもそも**特殊化は不安定機能**なので現状API表層に特殊化関連の状態を露出する選択肢はないと思われます。

### 一般的なイテレータからの生成

まずは最も一般的な場合の実装から見ていきます。この場合の実装は以下のようになっています。

```rust
impl<T, I: Iterator<Item = T>> RcFromIter<T, I> for Rc<[T]> {
    default fn from_iter(iter: I) -> Self {
        iter.collect::<Vec<T>>().into()
    }
}
```

一旦別の `Vec<T>` に書き出してから、 `Rc<[T]>` に変換しています。なぜ `Vec<T>` を経由するかというと、**開始時点ではイテレータのサイズが不明だから**です。 `Rc<[T]>` 用の領域を確保するにはスライスのサイズが確定している必要があるため、どうせ一回の動的メモリ確保で済ませることはできません。ですから `Vec<T>` を経由するのが確実というわけです。

ではこの `Vec<T>` から `Rc<[T]>` に変換する処理はどうなっているかというと、[以下のようになっています](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L1422-L1435)。

```rust
impl<T> From<Vec<T>> for Rc<[T]> {
    fn from(mut v: Vec<T>) -> Rc<[T]> {
        unsafe {
            let rc = Rc::copy_from_slice(&v);

            // Allow the Vec to free its memory, but not destroy its contents
            v.set_len(0);

            rc
        }
    }
}
```

`Rc::copy_from_slice` の実装はあとで紹介します。これを使って `Vec<T>` の中身を吸い出して、残ったヒープ領域だけ解放しています。

### 固定長イテレータからの生成

イテレータのサイズがわかっている場合は、より[効率的な実装](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L1509-L1529)が用いられます:

```rust
impl<T, I: iter::TrustedLen<Item = T>> RcFromIter<T, I> for Rc<[T]>  {
    default fn from_iter(iter: I) -> Self {
        // This is the case for a `TrustedLen` iterator.
        let (low, high) = iter.size_hint();
        if let Some(high) = high {
            debug_assert_eq!(
                low, high,
                "TrustedLen iterator's size hint is not exact: {:?}",
                (low, high)
            );

            unsafe {
                // SAFETY: We need to ensure that the iterator has an exact length and we have.
                Rc::from_iter_exact(iter, low)
            }
        } else {
            // Fall back to normal implementation.
            iter.collect::<Vec<T>>().into()
        }
    }
}
```

これをみて「あれ？」と思った人もいるかもしれません。Rustの固定長イテレータといえば [`ExactSizeIterator`](https://doc.rust-lang.org/std/iter/trait.ExactSizeIterator.html) が有名ですが、ここでは [`TrustedLen`](https://doc.rust-lang.org/std/iter/trait.TrustedLen.html) という別のトレイトが使われています。

この2つの違いは、**間違った実装を提供したときのペナルティーの違い**です。

- `ExactSizeIterator` の実装を間違えてしまった場合、**論理的な不変条件 (logical invariant) 違反**になるため、本来パニックしない関数がパニックしたり、期待されていない値を返す可能性がありますが、**影響範囲は限定的**です。
- `TrustedLen` の実装を間違えてしまった場合、**安全性不変条件 (safety invariant) 違反**になるため、**未定義動作**、つまり**当該イテレータを使っている場所に限らず、プログラム全体が全く期待しない動作をする可能性**があります。

ここでの `From<I> for Rc<[T]>` の実装では、イテレータの長さを信用して `Rc<[T]>` のサイズを決め打ちするので、長さが間違っていた場合の対処が困難です。バッファオーバーフローや未初期化領域が発生する可能性があるため、 `TrustedLen` を使っているといえます。慎重に実装すれば対応できなくもないはずですが、単なる機会的な最適化なので、あえて頑張って一般性を高めるよりも `TrustedLen` でできる範囲をカバーすればいいという選択でしょう。

`TrustedLen` は `usize::MAX` よりも多くの要素を出力する場合は `size_hint` の上界で `None` を返すという規約になっているので、この場合は念の為普通の実装にフォールバックしています。 (実際には `Vec<T>` を構築する途中でメモリ不足になると考えられます。)

それ以外の場合は下界と上界が等しく、必ず実際の出力数と等しくなる保証があるため、この保証に基づいて `Rc<[T]>` を構築します。[これを行っているのが `Rc::from_iter_exact` です](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L978-L1027)。

```rust
impl<T> Rc<[T]> {
    /// Constructs an `Rc<[T]>` from an iterator known to be of a certain size.
    ///
    /// Behavior is undefined should the size be wrong.
    unsafe fn from_iter_exact(iter: impl iter::Iterator<Item = T>, len: usize) -> Rc<[T]> {
        // Panic guard while cloning T elements.
        // In the event of a panic, elements that have been written
        // into the new RcBox will be dropped, then the memory freed.
        struct Guard<T> {
            mem: NonNull<u8>,
            elems: *mut T,
            layout: Layout,
            n_elems: usize,
        }

        impl<T> Drop for Guard<T> {
            fn drop(&mut self) {
                unsafe {
                    let slice = from_raw_parts_mut(self.elems, self.n_elems);
                    ptr::drop_in_place(slice);

                    Global.dealloc(self.mem, self.layout);
                }
            }
        }

        let ptr = Self::allocate_for_slice(len);

        let mem = ptr as *mut _ as *mut u8;
        let layout = Layout::for_value(&*ptr);

        // Pointer to first element
        let elems = &mut (*ptr).value as *mut [T] as *mut T;

        let mut guard = Guard {
            mem: NonNull::new_unchecked(mem),
            elems,
            layout,
            n_elems: 0,
        };

        for (i, item) in iter.enumerate() {
            ptr::write(elems.add(i), item);
            guard.n_elems += 1;
        }

        // All clear. Forget the guard so it doesn't free the new RcBox.
        forget(guard);

        Self::from_ptr(ptr)
    }
}
```

最初のほうはまず、スライスの大きさにあわせて `NonNull<RcBox<[T]>>` を確保しています。このあたりは `From<Box<T>> for Rc<T>` の実装とほぼ同じです。最後の `elems` が本体 (`[T]`) の先頭部分へのポインタです。ここでは未初期化領域を指す `&mut [T]` が一時的に生成されてしまっているので若干問題がありそうですが、 `&raw mut` が実装されたらそちらに置き換えられるでしょう。

```rust
let ptr = Self::allocate_for_slice(len);

let mem = ptr as *mut _ as *mut u8;
let layout = Layout::for_value(&*ptr);

// Pointer to first element
let elems = &mut (*ptr).value as *mut [T] as *mut T;
```

その後、イテレータから1個ずつ要素を取り出して格納していっています。ここまでは簡単です。

```rust
for (i, item) in iter.enumerate() {
    ptr::write(elems.add(i), item);
}
Self::from_ptr(ptr)
```

問題は `Guard` 型です。これは初めて見る人も結構いるかもしれませんが、unsafeなプログラムを書くときに出てくるパターンのひとつです。先ほど見たコードの中で次の部分に注目してください。

```rust
for (i, item) in iter.enumerate() {
    //           ^^^^^^^^^^^^^^^^ イテレータのnext()を呼んでいる
    ptr::write(elems.add(i), item);
}
Self::from_ptr(ptr)
```

このイテレータはユーザーから提供されたものなので、**パニックする可能性**を考慮する必要があります。そんなことないと思うかもしれませんがこういったことは意外と起こりえます。たとえば以下のようなコードを考えます。

```rust
use std::rc::Rc;

fn main() {
    let slice = [1, 2, 3];
    let rc = slice.iter().map(|&x| x - 1).collect::<Rc<[usize]>>();
    eprintln!("rc = {:?}", rc);
}
```

これは正しく動作しますが、4行目を `let slice = [0, 1, 2, 3];` に変えるとデバッグモードではcollectの内部でパニックを起こします。これはまさに今読んでいる箇所でのパニックです。

通常のRustコードを書いているときは、パニックのときの後片づけはコンパイラが生成するコードによって適切に行われますが、unsafe Rustでは必ずしもそうではありません。unsafe Rustでは「中途半端な状態」を経由しつつ処理を進めるので、中途半端な状態でパニックが起こった場合は自力で回復する必要があります。そのときによく使われるのが今回使われている**panic guardパターン**です。

panic guardパターンは、**パニック時の巻き戻し中でもデストラクタ(drop)は実行される**という性質に注目し、パニック時の片付けを専用の構造体のデストラクタで行う方法です。今回は以下のようなデストラクタが定義されています。

```rust
impl<T> Drop for Guard<T> {
    fn drop(&mut self) {
        unsafe {
            let slice = from_raw_parts_mut(self.elems, self.n_elems);
            ptr::drop_in_place(slice);

            Global.dealloc(self.mem, self.layout);
        }
    }
}
```

イテレータの `next` がパニックする瞬間は「`Rc<[T]>` のためのメモリが確保済みで、 `[T]` 部分が途中まで埋まっている状態」です。 `next` のパニック自体は呼び出し元に伝搬するので、処理そのものを完了させる必要はない (`Rc<[T]>` を返す必要はない) です。ということは、**作りかけの `Rc<[T]>` を破棄する**ことが今回のpanic guardの仕事ということになります。そのためには、まず途中までの `[T]` の内容物をdropして……

```rust
let slice = from_raw_parts_mut(self.elems, self.n_elems);
ptr::drop_in_place(slice);
```

その後、確保したメモリ領域を解放すればいいわけです。

```rust
Global.dealloc(self.mem, self.layout);
```

これらの後片づけを行うには、「確保した領域の先頭ポインタとレイアウト情報」「スライスの先頭ポインタ」「何要素まで埋まったか」という情報が必要です。最後のデータ以外は定数なので初期化するときに渡すだけです。

```rust
let mut guard = Guard {
    mem: NonNull::new_unchecked(mem),
    elems,
    layout,
    n_elems: 0,
};
```

「何要素まで埋まったか」は処理が進むにつれ変化する内容です。 `for` ループの中で書き換える必要があります。

```rust
for (i, item) in iter.enumerate() {
    ptr::write(elems.add(i), item);
    guard.n_elems += 1; // これ
}
```

パニックする可能性があるのは `next` (`for` 内で暗黙的に呼ばれている) のみで、たとえば `ptr::write` はパニックしないので、それとの前後関係は自由です。

`Rc<[T]>` が完成したらpanic guardは破棄します。せっかく完成した `Rc<[T]>` をpanic guardのdropで壊されてはたまらないからです。

```rust
// All clear. Forget the guard so it doesn't free the new RcBox.
forget(guard);
```

これで安心して `Rc<[T]>` を返すことができるというわけです。

### スライスイテレータからの生成

さらに、イテレータが特定の方法で作られたものだった場合にさらに最適化しています。具体的には**スライスに由来するイテレータ**だった場合は、後述するスライスからの生成と同じなのでそちらの処理に移譲しています。

```rust
impl<'a, T: 'a + Clone> RcFromIter<&'a T, slice::Iter<'a, T>> for Rc<[T]> {
    fn from_iter(iter: slice::Iter<'a, T>) -> Self {
        // Delegate to `impl<T: Clone> From<&[T]> for Rc<[T]>`.
        //
        // In the case that `T: Copy`, we get to use `ptr::copy_nonoverlapping`
        // which is even more performant.
        //
        // In the fall-back case we have `T: Clone`. This is still better
        // than the `TrustedLen` implementation as slices have a known length
        // and so we get to avoid calling `size_hint` and avoid the branching.
        iter.as_slice().into()
    }
}
```

これを読んでいて、そもそもこの実装はバグっていて使われることがないと思ったのでバグ報告しました→ https://github.com/rust-lang/rust/issues/67307

## スライスからの生成

スライス (`&[T]`) からも `Rc<[T]>` を生成できます。しかし、 `Vec<T>` とは異なり `&[T]` は要素への所有権を持たないため、 `T: Clone` を仮定する必要があります。

```rust
impl<T: Clone> From<&[T]> for Rc<[T]> {
    fn from(v: &[T]) -> Rc<[T]> {
        <Self as RcFromSlice<T>>::from_slice(v)
    }
}
```

こちらも[特殊化トレイトに実装が移譲されています](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L1030-L1049)。

```rust
/// Specialization trait used for `From<&[T]>`.
trait RcFromSlice<T> {
    fn from_slice(slice: &[T]) -> Self;
}

impl<T: Clone> RcFromSlice<T> for Rc<[T]> {
    #[inline]
    default fn from_slice(v: &[T]) -> Self {
        unsafe {
            Self::from_iter_exact(v.iter().cloned(), v.len())
        }
    }
}

impl<T: Copy> RcFromSlice<T> for Rc<[T]> {
    #[inline]
    fn from_slice(v: &[T]) -> Self {
        unsafe { Rc::copy_from_slice(v) }
    }
}
```

- 一般に `T: Clone` の場合は、元の `&[T]` と同じメモリ表現とは限らないので、1要素ずつcloneするしかありません。しかし、要素数はわかっています。これは `TrustedLen` なイテレータの場合と同じですね。そういうわけで、同じ処理に移譲しています。
- しかし、 `T: Copy` とわかっている場合は単にメモリをコピーすればよいので、 `Box<T>`→`Rc<T>` の場合と同様の処理を使っています。

## `Weak::new`

ここまで、 `Rc::new` の代替になるサイズ不定型用のコンストラクタを読んできました。では `Weak::new` についてはどうでしょうか。そもそも、 `Weak::new` 自身はどうだったかというと……

```rust
impl<T> Weak<T> {
    pub fn new() -> Weak<T> {
        Weak {
            ptr: NonNull::new(usize::MAX as *mut RcBox<T>).expect("MAX is not 0"),
        }
    }
}
```

実は、 `T: Sized` を要求していました。でも、 `Rc::new` と違って `value: T` を受け取るわけではないので、 `T: ?Sized` でもよさそうです。なぜだめなのでしょうか？

これはRustにおけるfatポインタのメタデータのルールが確定していないことと関係あります。実際、[UCG (Unsafe Code Guideline)のポインタメタデータに関するissue](https://github.com/rust-lang/unsafe-code-guidelines/issues/166)ではまさに `Weak::new` が言及されています。

これによると、(例え`Weak<T>` や生ポインタであっても)メタデータは適切な値が入っていなければならないことになっています。(正確には、このルールが採用されるかは不確定ですが、不確定な以上は保守的に実装するべきです)

スライスであれば0は適切なメタデータですが、トレイトオブジェクトの場合はvtableを探してくる必要があります。「ダミーのvtable pointer」を作る汎用的な仕組みはないので、 `Weak::new` を `T: ?Sized` に一般化するのは現時点では難しいわけです。

なお、スライスの `Weak` を作りたければ `Weak::<[T; 0]>::new()` を `Weak<[T]>` に型強制すればOKです。

# Send/Sync

`Send`, `Sync` はスレッドセーフかどうかを表すトレイトです。

```rust
impl<T: ?Sized> !marker::Send for Rc<T> {}
impl<T: ?Sized> !marker::Sync for Rc<T> {}
impl<T: ?Sized> !marker::Send for Weak<T> {}
impl<T: ?Sized> !marker::Sync for Weak<T> {}
```

`Send`, `Sync` は[自動トレイト (auto trait)](https://rust-lang.github.io/rfcs/0019-opt-in-builtin-traits.html) (昔はOIBITsと呼ばれていた) の一種で、公開されているものでは以下の5つがあります。

- スレッド安全性: `Send`/`Sync`
- 巻き戻し安全性: `UnwindSafe`/`RefUnwindSafe`
- ピン外し安全性: `Unpin`

自動トレイトは**構造体のフィールド型に基づいて自動的に実装される**という特徴があり、1.39.0時点ではサードパーティーのライブラリが定義することはできません。構造体のフィールド型という内部仕様を露出してまう性質上、簡単には安定化されない(あるいは、永遠に安定化されない)だろうなと筆者は考えています。

さて、 `Send` と `Sync` の違いは何でしょうか。これは専有する場合と共有する場合にそれぞれ対応しています。つまり、

- `T: Send` は、 **`T` の所有権を他のスレッドに移してもよい**ということを意味します。
- `T: Sync` は、 **`T` の共有権 (`&T`) を他のスレッドに与えてもよい**ということを意味します。

実際に片方しか成立しない例を考えるとわかりやすいかもしれません。 `RefCell<i32>` は、アトミックではないロックによって排他制御を可能にするコンテナです。ロックがアトミックではないので、複数のスレッドから交互にアクセスされるとデータ競合になってしまいます。

- `&RefCell<i32>` を他のスレッドに与えてしまうと、そのスレッドと元のスレッドがロックに交互にアクセスすることが可能になってしまいます。したがって、 `RefCell<i32>: !Sync` です。
- しかし、 `RefCell<i32>` そのものを他のスレッドに送っても、元スレッドからは同じロックへのアクセス権は失われるので、データ競合にはなりえません。したがって、 `RefCell<i32>: Send` で問題ありません。

逆の例としては `MutexGuard<i32>` があります。(1.39.0時点)

- `MutexGuard<i32>` はロックの解放義務があること以外は `&mut i32` とほぼ同じです。 `&MutexGuard<i32>` を他スレッドに送ってもロックの解放義務は元スレッドにあるため、実質的には `&&mut i32` を送っているのと同じです。したがって `MutexGuard<i32>: Sync` で問題ありません。
- しかし、 `MutexGuard<i32>` そのものを他スレッドに送ってしまうと、ロックの取得と解放が別スレッドで行われることになってしまいます。 `Mutex` はプラットフォームによってはシステムミューテックスに依存しており、システムミューテックスでは別スレッドでのロックの解放を必ずしも許していないと考えられます。したがって、 `MutexGuard<i32>: !Send` となっています。

さて、これを踏まえて `Rc<T>` はスレッドセーフかどうかを考えてみます。

- `Rc<T>` は複製可能です。複製して `Rc<T>` の所有権を別スレッドに送ると、参照カウンタが共有されてしまいます。 `Rc<T>` の参照カウンタは非アトミックであるためこれはデータ競合になってしまいます。したがって、 `Rc<T>: !Send` です。
- `&Rc<T>` を送った場合でも、受け取り側で `clone` を呼んで `Rc<T>` を取得可能です。したがって `Rc<T>: !Sync` にする必要があります。

`Weak<T>` についても同様です。

ところで、生ポインタである `NonNull<_>` は(それ自体はただの整数なので) 本来は `Send`/`Sync` でもよいのですが、これを使ったライブラリが誤った使い方をすることを考えて安全寄り (`!Send`/`!Sync`) に倒してあります。そのため、実際には上記のように明示的に否定実装を持ち込まなくても、`Rc<T>` も自動的に `!Send`/`!Sync` になるはずです。それをわかった上で、念の為否定実装を用意しているのかなと思います。

# PhantomDataと `#[may_dangle]`

今までは無視していましたが、 `Rc` には `phantom` というフィールドがあります:

```rust
pub struct Rc<T: ?Sized> {
    ptr: NonNull<RcBox<T>>,
    phantom: PhantomData<T>,
    //       ^^^^^^^^^^^^^^
}
```

また、 `Drop` 実装には `#[may_dangle]` という謎の属性がついています。

```rust
unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> {
    //      ^^^^^^^^^^^^^
    ...
}
```

この2つは、**drop checkerの挙動を調整するため**に存在しています。

## drop checkerとは

第1回の中で、Rustの**デストラクタと循環参照の相性が悪い**ということに言及しました。そこでは、**`Arc`/`Rc` が循環参照を含むとき、デストラクタが呼ばれない**という問題を紹介しました。

`Arc<T>`/`Rc<T>` が循環参照を構成しうるのはこれらが共有ポインタだからですが、同じく共有ポインタである `&T` でも循環参照にまつわる問題があります。それは、**`&T` が循環参照を含むとき、デストラクタを安全に呼ぶことができない場合がある**という問題です。

では、第一回と同様、グラフを例にしてみます。以下の例では、名前つきノードの有向グラフを `&T` を使って表現しています。

```rust
use std::cell::RefCell;

#[derive(Debug)]
struct Node<'a> {
    name: String,
    neighbors: RefCell<Vec<&'a Node<'a>>>,
}

impl Node<'_> {
    fn new(name: &str) -> Self {
        Self {
            name: name.to_owned(),
            neighbors: RefCell::new(Vec::new()),
        }
    }
}

fn main() {
    let node1 = Node::new("node1");
    let node2 = Node::new("node2");
    node1.neighbors.borrow_mut().push(&node2);
    node2.neighbors.borrow_mut().push(&node1);
}
```

2つのノードが相互参照するようなグラフを作っています。これ自体はうまく動作します。 (動作するといっても、何もしていないので何も出力せず終わります。)

では、ここに次のような `Drop` 実装を足したらどうなるでしょうか。

```rust
impl Drop for Node<'_> {
    fn drop(&mut self) {
        let neighbors = self.neighbors.borrow();
        eprintln!("{} had {} neighbors:", self.name, neighbors.len());
        for neighbor in neighbors.iter() {
            eprintln!("    {}", neighbor.name);
        }
    }
}
```

これは、そのノードが要らなくなるときに、隣接するノードに関する情報をダンプするというものです。 `Drop` の実装としては何らおかしなことはありません。

しかしここで問題があります。「同時にdrop」という概念はないので、 **`node1` と `node2` はどちらかが先にdropされるはず**です。仮に `node2`→`node1` の順番にdropされるとしましょう。すると、 `node1` のDropを呼ぶ段階ではすでに `node2` は無効になっているはずです。しかし上のコードでは隣接ノードの名前を取得しているので、 `node2` の既にdropされた `String` にアクセスすことになります。これは**典型的なuse-after-free**です。逆順 (`node1`→`node2`) だったとしても同じ問題が起こります。

このような危険なコードを許すわけにはいかないので、**上記の `Drop` 実装を追加した時点でコンパイルエラーになる**ように設計されています。この仕組みが**drop checker**です。

## drop checkerの仕組み

drop checkerは、定義する側ではなく使う側でエラーを吐くようになっています。注目するべきは、 **`drop` 処理が安全に挿入できる条件**です。

デストラクタは、コンパイラが自動的に挿入することを除けば普通の関数呼び出しとそれほど違いません。たとえば、

```rust
fn main() {
    let s = String::from("Hello!");
}
```

というコードがあれば、これはコンパイルの途中で以下のように変形されているわけです。 (drop glueの挿入)

```rust
// drop glue挿入後の状態を表した擬似コード。コンパイルして動くわけではない
fn main() {
    let s = String::from("Hello!");
    // s を破棄する
    drop_in_place(&mut s);
}
```

なので、この**変形後のコードで `drop_in_place` の呼び出しが問題なく行える条件**を考えればいいわけです。

### 普通の関数呼び出しの呼び出し条件

……その前に、**普通の関数の呼び出しが問題なく行える条件**を考えてみます。たとえば以下の関数を考えます。

```rust
fn f(x: &i32) -> i32 {
    *x + *x
}
```

ライフタイムを明示すると次のようになります。

```rust
fn f<'a>(x: &'a i32) -> i32 {
    *x + *x
}
```

この「ライフタイム」というのは、時限での借用権を制御するためのタイマーのようなものでした。別の言い方をすると、 `'a` というのは**未来のある時刻**を指しているわけです。

ここで、この関数 `f` には**重要な暗黙の仮定**があります: それは、**受け取ったライフタイムは全て、関数が呼び出されている間は有効**だということです。実際関数内では `*x` と参照の参照先を取得しています。 `'a` が期限切れだったら、この操作は危険な操作になってしまいます。

これは、ライフタイム引数だけではなく、**型引数に含まれるライフタイム**にも適用されます。たとえば、以下のコードを考えます。

```rust
use std::ops::Add;

fn f<T: Copy + Add>(x: T) -> T::Output {
    x + x
}
```

この `f` はライフタイム引数を取りませんが、 `T` として `&'a i32` を入れるとひとつ前の `f` と同様の実装になります。この場合も、 **`T` に含まれる `'a` が関数呼び出しの間有効であること**が仮定されています。

### `drop_in_place` の呼び出し条件

ところが、同じ条件を自動で挿入される `drop_in_place` にそのまま適用してしまうと困ったことになります。先ほどのグラフの例をもう一度出してみます。

```rust
fn main() {
    let node1 = Node::new("node1");
    let node2 = Node::new("node2");
    node1.neighbors.borrow_mut().push(&node2);
    node2.neighbors.borrow_mut().push(&node1);
}
```

これは、 **`Node` が `Drop` を実装していないときは正しく動作**していました。ところが `drop_in_place` の条件を考えてみると……

```rust
// 擬似コード
fn main() {
    // どちらも Node<'a> 型
    let node1 = Node::new("node1"); // この変数の有効範囲を 'node1 とおく
    let node2 = Node::new("node2"); // この変数の有効範囲を 'node2 とおく
    // &'node1 Node<'a> を &'a Node<'a> にキャストしている
    // → 'node1: 'a ('a のほうが狭い)
    node1.neighbors.borrow_mut().push(&node2);
    // &'node2 Node<'a> を &'a Node<'a> にキャストしている
    // → 'node2: 'a ('a のほうが狭い)
    node2.neighbors.borrow_mut().push(&node1);

    // drop処理が開始したら、もはやその領域は有効とはいえない
    // したがって、この行(←)が 'node2 の終わり
    // 'node2: 'a なので、 'a もこの行で終わり
    drop_in_place(&mut node2); // 引数は*mut Node<'a> だが、 'a はもはや有効ではない!
    // この行(←)が 'node1 の終わり
    drop_in_place(&mut node1); // 引数は*mut Node<'a> だが、 'a はもはや有効ではない!
}
```

かなり複雑ですが、コメントに記載されているような理屈により、 **`drop_in_place` が呼び出された時点で `'a` がもはや無効**になってしまっています。これでは本来問題ない場合でもコンパイルエラーにせざるを得ません。

### `drop_in_place` を詳細に解析する

本来問題ないのに、このルールのもとではコンパイルエラーになってしまうのはなぜか。それは、上の例では**`'a` が有効である必要はない**のに、そのような仮定を導入してしまったからです。もう少し正確に言うと、

- `Drop for Node` 実装がない場合、 `'a` が有効である必要はないので、コンパイルを通したい。
- `Drop for Node` 実装がある場合、 `'a` が有効でないといけないので、コンパイルエラーにしたい。

ということになります。そこで、コンパイラが自動で挿入する `drop_in_place` については以下のようにします。

- 通常の関数呼び出しのように、**「全てのライフタイム引数・型引数に含まれるライフタイムが関数呼び出しの最中有効である」ということを要求しない**。
- そのかわり、各型について**「`drop_in_place` のために必要なライフタイムの一覧」をあらかじめ決めておき、それらのライフタイムが関数呼び出しの最中有効であることを要求する**。 (drop check)

### `drop_in_place` のためのライフタイム規則

便宜上、以下の関数を導入します。

- `all_lifetimes(T)` ... その型に含まれる全てのライフタイムの集合
  - 通常の関数呼び出しでは、 `all_lifetimes(T)` のライフタイムが関数呼び出し中有効であることが求められる。
- `drop_lifetimes(T)` ... その型をdropするのに必要なライフタイム。
  - コンパイラが自動で挿入する `drop_in_place` の呼び出しでは、 `drop_lifetimes(T)` のライフタイムが関数呼び出し中有効であることが求められる。

`all_lifetimes(T)` の定義は簡単です。 `drop_lifetimes(T)` を定義するのがここでの目的です。

`drop_in_place` は、カスタムdropを呼んだあとにフィールドを再帰的にdropします。そのため、 `drop_lifetimes(T)` の定義は原則として以下のようになります。

- `T` にカスタムdropがある場合、 `drop_lifetimes(T)` = `all_lifetimes(T)`
  - カスタムdropは `T` を自由に呼び出せるので、任意のカスタムdropを安全に呼べるようにするには `T` のライフタイムが全部有効であることを要求する必要がある。
- `T` にカスタムdropがない場合、 `drop_lifetimes(T)` = `T` の全てのフィールド `F_n` について `drop_lifetimes(F_n)` の合併

### `#[may_dangle]`

ところが、これだと融通が効かなさすぎるので、カスタムDropがより少ないライフタイムを要求するようにオプトアウトする方法があります。それが `#[may_dangle]` です。 `#[may_dangle]` は**Drop実装の型引数またはライフタイム引数**に付与できる特殊な属性です。これを考慮すると、 `drop_lifetimes` のルールは以下のように変更されます。

- 以下の全てを足したものが `drop_lifetimes(T)` である。
  - `T` のDrop実装の型引数のうち、 `#[may_dangle]` のついていないもの (`T_n` とおく) について `all_lifetimes(T_n)`
  - `T` のDrop実装のライフタイム引数のうち、 `#[may_dangle]` のついていないもの
  - `T` のフィールド (`F_n` とおく) について、 `drop_lifetimes(F_n)`
- ただし、Drop実装がない場合は、全ての型引数・ライフタイム引数に `#[may_dangle]` のついた空のDrop実装がある場合と等価として扱う。

`#[may_dangle]` がない場合、 `drop_lifetimes(T)` は「全ての型引数・全てのライフタイム引数・全てのフィールドのライフタイムを集めてきたもの」なので、 `all_lifetime(T)` と等しくなります。つまりさっきの定義とはちゃんと互換になっています。

`#[may_dangle]` をつけるということは、それに関係する参照をうっかり触ってしまわないように気をつける必要があるということで、間違えると未定義動作につながります。そのため、 **`#[may_dangle]` のついた `Drop` 実装は `unsafe` でマークする必要がある**というルールになっています。

## `Rc` のドロップライフタイムを調整する

さて、上の規則にもとづいて `Rc<T>` のドロップライフタイムを計算するとどうなるでしょうか。

まず、 `Rc<T>` には普通のカスタムドロップがある状態からはじめてみます。

```rust
pub struct Rc<T: ?sized> {
    ptr: NonNull<RcBox<T>>,
}
impl<T: ?Sized> Drop for Rc<T> { ... }
```

この場合、 **`drop_lifetimes(Rc<T>)` = `all_lifetimes(Rc<T>)` = `all_lifetimes(T)`** になります。このようにすれば安全ですが、実態を正しくあらわしていません。たとえば、 **`Rc<&'a i32>` をdropする場合、 `'a` が有効である必要はありません**。 `Rc::drop` が実際に `T` を自由に呼び出すことはないからです。強参照が消えたときだけ `drop_in_place` を呼ぶ可能性があるので、 `drop_lifetimes(Rc<T>) = drop_lifetimes(T)` であるべきです。

では、 `Rc::drop` が `T` を自由に呼び出せなくてもよいということを表すために `#[may_dangle] T` としたらどうなるでしょうか。

```rust
pub struct Rc<T: ?sized> {
    ptr: NonNull<RcBox<T>>,
}
unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> { ... }
```

この場合はフィールド型に基づいて計算され、 **`drop_lifetimes(Rc<T>)` = `drop_lifetimes(NonNull<RcBox<T>>)` = `{}`** ということになります。今度は `drop_lifetimes` が小さすぎで危険です。

ここで登場するのが、 `PhantomData` です。PhantomData自身は実体をもちませんが、これを置いておくことで「`T` がdropされうる」という関係を表明することができます。

```rust
pub struct Rc<T: ?sized> {
    ptr: NonNull<RcBox<T>>,
    phantom: PhantomData<T>,
}
unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> { ... }
```

こうすると、 `drop_lifetimes` の計算においては `PhantomData<T>` は `T` と同様に振る舞うので、 `drop_lifetimes(Rc<T>)` = `drop_lifetimes(NonNull<RcBox<T>>) ∪ drop_lifetimes(PhantomData<T>)` = `drop_lifetimes(PhantomData<T>)` = `drop_lifetimes(T)` となり、所望の結果を得ることができました。

## `PhantomData` の効果

`PhantomData<T>` はメモリレイアウト上は `()` と同じですが、以下の3つの効果があります。

- 変性 (共変・反変・非変・双変) を計算する上では `T` と同等に扱われる。
  - 幽霊型を作った際に未使用の型引数エラーで怒られるのはこれと関係がある。 `PhantomData<T>` を使うことでその引数を共変(または反変または非変)にすることができ、これによって未仕様型引数エラーを回避できる)
- 自動トレイトの計算上は `T` と同等に扱われる。
- drop checkerの処理上は `T` と同等に扱われる。

今回は3つ目の効果が必要で `PhantomData<T>` を使いましたが、他の2つの効果は問題ないのか確かめておく必要があります。

### 変性

`PhantomData<T>` フィールドを置くと、全体が `T` に対して共変になってしまいます。全体を `T` に対して反変な状態にしたいのであれば、うまく回避する必要があります。

今回扱っている `Rc<T>` は `&T` と同様、 `T` に対して共変になるのが正解です。 `RcBox<T>` は `T` に対して共変で、 `NonNull<T>` もまた `T` に対して共変なので、 `NonNull<RcBox<T>>` は `T` に対して共変です。そのため元から共変でした。 `PhantomData<T>` も `T` に対して共変なので、これを追加することに問題はありません。

### 自動トレイト

`PhantomData<T>` フィールドを置くと、自動トレイトの充足性計算でも `T` が考慮されてしまいます。 `Rc<T>` が各自動トレイトをどう実装すべきかと実態が合っているかどうか確かめておく必要があります。

- `Send`, `Sync` に対しては、明示的に否定実装を提供しているので影響はありません。
- `UnwindSafe` については `&T` と同様、 `T: RefUnwindSafe` であるときに実装されるべきです。これは `UnwindSafe` 側の定義で明示的に実装されているので問題ありません。
- `RefUnwindSafe` については、 `T: RefUnwindSafe` であるときに実装されるべきはずですが、そうはなっていないようです。まあ、 `UnwindSafe` は実装されていなくてもオプトインできるので問題ないのかもしれません。
- `Unpin` については `&T` と同様常に実装されるべきです。これ `rc.rs` 内で明示的に実装されているので問題ありません。

## `Weak` の場合

`Weak` の場合、 `Weak::drop` が `T` に触れることはないので、 `drop_lifetimes(Weak<T>) = {}` でいはずですが、実際には `#[may_dangle]` はついていないようです。おそらくあまり深い意図はなく、単に `#[may_dangle]` を必要としている人がいないからこの状態で放置されているのではないかと思います。

# ダウンキャストとAny

Rustのトレイトオブジェクトはデフォルトでは実行時型情報 (RTTI) を持たないためダウンキャストができませんが、別途実行時型情報を持たせることは可能です。 `Any` は `type_id` という実行時型情報を持たせることでダウンキャストを可能にするトレイトです。(特定の固定サイズ型へのダウンキャストだけ可能です)

ただし、実際のダウンキャストはポインタ型ごとに別々に実装を与える必要があります。 `Rc<dyn Any>` に関しても以下のような[ダウンキャストの実装](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L847-L879)があります。

```rust
impl Rc<dyn Any> {
    pub fn downcast<T: Any>(self) -> Result<Rc<T>, Rc<dyn Any>> {
        if (*self).is::<T>() {
            let ptr = self.ptr.cast::<RcBox<T>>();
            forget(self);
            Ok(Rc::from_inner(ptr))
        } else {
            Err(self)
        }
    }
}
```

やっていることは簡単で、Type IDを比較して一致したらその型の `Rc` に変換し、そうでなかったら失敗とみなして元の `Rc` を返しているだけです。

`Rc<dyn Any>` は参照先が `Any` とわかっているため、あえて `this: Self` とする必要はなく普通に `self` 引数を受け取っています。

# ポインタ比較

Rustのスマートポインタ/参照全般に言えることですが、 `Rc` の比較演算はアドレス自体ではなく中に保管されている値を比較します。

```rust
// 中身が等しい
assert_eq!(Rc::new(42), Rc::new(42));
```

一方で「ポインタとして」等しいかどうかを調べる演算は別途用意されています。

```rust
// ポインタは等しくない
assert!(!Rc::ptr_eq(&Rc::new(42), &Rc::new(42)));
```

さて、`Rc` を比較するさい、ポインタの比較を先に行えばより効率的な比較が行えそうです。実際 `PartialEq` の実装は以下のように特殊化を用いて[最適化されています](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L1153-L1236):

```rust
impl<T: ?Sized + PartialEq> PartialEq for Rc<T> {
    fn eq(&self, other: &Rc<T>) -> bool {
        RcEqIdent::eq(self, other)
    }
    fn ne(&self, other: &Rc<T>) -> bool {
        RcEqIdent::ne(self, other)
    }
}

impl<T: ?Sized + Eq> Eq for Rc<T> {}
```

肝心の `RcEqIdent` は以下のような特殊化ツリーになっています:

```rust
trait RcEqIdent<T: ?Sized + PartialEq> { ... }

impl<T: ?Sized + PartialEq> RcEqIdent<T> for Rc<T> { ... }

/// We're doing this specialization here, and not as a more general optimization on `&T`, because it
/// would otherwise add a cost to all equality checks on refs. We assume that `Rc`s are used to
/// store large values, that are slow to clone, but also heavy to check for equality, causing this
/// cost to pay off more easily. It's also more likely to have two `Rc` clones, that point to
/// the same value, than two `&T`s.
impl<T: ?Sized + Eq> RcEqIdent<T> for Rc<T> { ... }
```

コメントには、同様の最適化を `&T` に対して行わない理由が書いてありますね。

## `T: Eq`

さて、ここでまず注目するべきは「そもそもなぜこの最適化を適用するのに特殊化する必要があるのか」つまり以下のように実装してはだめなのかということです。

```rust
impl<T: ?Sized + PartialEq> PartialEq for Rc<T> {
    #[inline]
    fn eq(&self, other: &Rc<T>) -> bool {
        Rc::ptr_eq(self, other) || **self == **other
    }

    fn ne(&self, other: &Rc<T>) -> bool {
        !Rc::ptr_eq(self, other) && **self != **other
    }
}
```

もちろん答えはNoです。わざわざ特殊化するには当然理由があるわけですね。それは `PartialEq` と `Eq` の違いに関係しています。 **`PartialEq` は反射律 (同じもの同士を比較したら `true` になる) を必ずしも満たさなくてもよく、反射律を要求するには `Eq` を要求する必要があります**。たとえば……

```rust
// NaNは自分自身と等しくない
let x = f64::NAN;
assert_ne!(x, x);
```

という現象が発生します。 **`Rc` の比較は中身の比較と同値であってほしい**ので、次のような結果を期待します (実際そうなります)。

```rust
// NaNは自分自身と等しくない
let x = Rc::new(f64::NAN);
assert_ne!(x, x);
```

もし「ポインタが同じなら同じ」を無制限に適用してしまうと、上の比較結果も「等しい」となってしまい、一貫しない動作になってしまいます。 `T: Eq` のときに限ってこの最適化を適用すれば、 `T` 自身の比較が反射律を満たしていることが期待されるので、このような一貫しない結果になることは基本的にありません。

## ヘテロな `PartialEq`

`PartialEq` は異なる2つの型の間に実装することもできます。

```rust
// str: PartialEq<String>
assert_eq!(*"foo", String::from("foo"));
```

ところが、上で紹介した `PartialEq` の実装は、両辺の型が同じ場合に限られています。なぜでしょうか？

単なるサボりの可能性もありますが、ひとつ考えられるのが特殊化との兼ね合いです。特殊化が安定化されていない理由のひとつに、**ライフタイムと特殊化の関係が難しい**ということがあります。

例えば以下のような例を考えます。

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

trait Foo {
    fn foo(self);
}

impl<T: std::fmt::Debug + ?Sized> Foo for &T {
    default fn foo(self) {
        eprintln!("{:?} is not a static str", self);
    }
}

impl Foo for &'static str {
    fn foo(self) {
        eprintln!("{:?} is a static str", self);
    }
}
```

これは `&'static str` の場合だけ特別扱いして特殊化しています。これを使って以下のような関数 `foo1`, `foo2` を作ったらどうなるでしょうか。

```rust
fn foo_proxy<T: std::fmt::Debug + ?Sized>(s: &T) {
    Foo::foo(s);
}

fn foo1(s: &str) {
    foo_proxy(s);
}

fn foo2(s: &'static str) {
    foo_proxy(s);
}
```

`foo2` は参照が `'static` とわかっていますが、 `foo1` はそうではありません。ライフタイム情報は実行時には消えてしまうので、「`'static` かどうか」で実行時に場合分けすることもできません。もし、 `foo1` に `&'static str` を渡したらどうなるのでしょうか。実は現在の実装は驚くべき挙動を示します。

```rust
fn main() {
    foo1("foo");
    foo2("foo");
    
    let s = String::from("foo");
    let mut s = s.as_str();
    foo1(s);
    s = "foo";
    foo1(s);
}
```

上の例を実行すると全て `"foo" is a static str` と出力してしまいます。今はライフタイムを無視して特殊化しているようです。

もちろん、このまま特殊化が安定化されてしまうと大変なことが起こってしまいます。特殊化とライフタイムの関係は、安全かつ一貫した形でうまく定義される必要があります。たとえば[nikomatsakis氏の2018年の記事](http://smallcultfollowing.com/babysteps/blog/2018/02/09/maximally-minimal-specialization-always-applicable-impls/)ではそのようなルールの例が提案されています。

そしてこれを見ると次のようなルールが存在します。

> ### Condition 3: Each type parameter can only be used once.
>
> Using a type parameter more than once imposes "hidden" equality constraints between parts of the input types which in turn can lead to equality constraints between lifetimes. Therefore, an *always applicable* impl must use each type parameter only once, like this:
>
> ```rust
> impl<T, U> SomeTrait for (T, U) {
> }
> ```
>
> Repeating, as here, means the impl cannot be used to specialize:
>
> ```rust
> impl<T> SomeTrait for (T, T) {
>   //                   ^^^^
>   // `T` used twice: not always applicable
> }
> ```

このように、**異なる型引数を用いて与えられた実装を、ひとつの型引数を用いた実装で特殊化するのは禁止**しなければいけません。詳しい理由は当該ブログ記事を参照してほしいですが、端的に言うと `T = U` という制約は `'a = 'b` という制約を含む可能性があり、これによって正確に特殊化できない状況が発生しうるという理屈です。

もし、 `Rc` が以下のような実装を提供したとします。

```rust
impl<T: ?Sized + PartialEq<U>, U: ?Sized> PartialEq<Rc<U>> for Rc<T> { ... }
```

我々がもともと提供している特殊化は、 **`T = U` かつ `T: Eq` のとき**にのみ実装可能でした。 (`Eq` は `PartialEq` と違って、同じ型同士の場合にのみ定義されていることに注意してください。) これは上の記事で禁止されている種類の特殊化に該当します。

`Rc` の `PartialEq` 実装をヘテロ化できないのにはこのような背景がある可能性があります。

# `#[lang]`

`Rc` の定義は正確には以下のようになっていました。

```rust
#[cfg_attr(not(test), lang = "rc")]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Rc<T: ?Sized> {
    ptr: NonNull<RcBox<T>>,
    phantom: PhantomData<T>,
}
```

この `#[cfg_attr(not(test), lang = "rc")]` は以下のようなものです。

- 通常のビルドでは `#[lang = "rc"]` に展開される。
- テストビルドでは消える。

そしてこのこの `#[lang = "rc"]` というのは**言語アイテム (language item)**と呼ばれ、**コンパイラが特別扱いする必要のある型や関数**などを識別するためのマーカーです。

ところで第1回の冒頭で次のように書いたのを覚えているでしょうか。

> `Arc<T>` はRustの基本的な型のひとつですが、 `Box<T>` のようにコンパイラに特別扱いされているわけでもなく、実装も比較的コンパクトです(コメントやテスト、安定性に関する指示などを除いて500LOC程度) その一方で `Arc` は並行性制御や `Deref`, ドロップチェッカー, Unpin, Layoutの扱いなどRustをよりよく理解するための題材を多く含んでいます。そこで本記事では `Arc<T>` の実装を読んでいきます。

「コンパイラに特別扱いされているわけでもない」と書いていますね。これは嘘だったのかというと、50%嘘でした。というのも、`Box` などの本質的に特別扱いする必要のある型とは異なり、 `Rc` の言語アイテムマーカーは**エラーメッセージのカスタマイズ**のためだけに存在するからです。

このようなエラーメッセージのためのマーカーは[本来の言語アイテムとは区別して、診断アイテムという名前で分離しよう](https://github.com/rust-lang/rust/issues/66075)と提案されています。

さて、それとは別の話として、 `cfg_attr` を用いて条件付き属性にしている点も気になります。これは**同じ言語アイテムは全体で1つしか存在してはいけない**ことと関係あります。

Rustにはユニットテストのための機能が組み込まれていますが、**ユニットテスト用のビルドはリリースビルドやデバッグビルドとは別に作成されます**。ユニットテスト用のビルドの依存関係はデバッグビルド用のものが使われますが、必要な場合は**再帰的に自分自身のデバッグビルドに依存する場合もあります**。特にテストに必須の `test` は標準ライブラリである `std` に依存するので、`alloc` のテストビルドは `alloc` 自身のデバッグビルドに依存します。このとき依存ツリーには2つの異なる `Rc` が存在することになるわけですが、両方に `#[lang]` 属性がついているとルール違反になってしまいます。これを回避するために、テストビルドでは `#[lang]` 属性を付与しないようになっているわけです。

# MaybeUninit

大きなデータを扱うときは、先にメモリ領域を確保してから初期化をしたほうがよい場合があります。これを実現するための仕組みは整備途上ですが、その一部として [`Rc<MaybeUninit<T>>` を扱うためのAPI](https://github.com/rust-lang/rust/blob/1.39.0/src/liballoc/rc.rs#L330-L359)が最近追加されています。

`Rc` の実装として興味深い点はもはやほぼ残っていないので、省略します。

# Pin

`Pin` は「ムーブすると壊れてしまうデータ」をうまく扱うために最近追加された枠組みです。

`Pin` を使ったポインタを作る方法はいくつかありますが、 `Rc`/`Arc` を使う方法も用意されています。

```rust
use std::marker::PhantomPinned;
use std::pin::Pin;
use std::rc::Rc;

fn main() {
    // Unpinではない型の例としてPhantomPinnedを使う
    // Rc::pinによってPin<Rc<T>>を得ることができる
    let rc = Rc::pin(PhantomPinned);
    // Pin::as_refによってPin<&T>を得ることができる
    let r: Pin<&_> = rc.as_ref();
}
```

`Box` と異なり、すでにある `Rc<T>` を `Pin<Rc<T>>` にする(`T: Unpin` を仮定しない)安全な方法はありません。これはある `Rc<T>` を `Pin<Rc<T>>` にできたとしても他に同じ領域を指す `Rc<T>` が残っている可能性があるからです。

実装はそんなに面白くないので省略します。

# まとめ

- Rustの標準ライブラリは要求するプラットフォームサポートに応じて3段階に分けられているが、 `Rc` はアロケーションに依存し、OSに依存しないため2段階目にあたる `alloc` に定義されている。
- Rustは高速なリリースサイクルとコンパイラの安定性、前方互換性を両立するために「機能の安定性」という概念を導入し、リリース可能な機能以外はnightlyビルドでのみ利用可能な仕組みを構築している。
- スマートポインタである `Rc` は参照先のメソッドとの衝突を防ぐため、`Rc` 自身に対する操作の多くはドット記法によるメソッド呼び出しではなく `Rc::foo` という形での呼び出しをする必要がある。
- ダミーの弱参照を作る方法があるが、その以前の実装は安全性に関してきわどい実装になっていたため2度の修正を経ている。
- `Rc` は参照先にサイズ不定型を使うことができるが、そのための追加のAPIは非常に興味深い。
  - 固定サイズの `Rc` をサイズ不定の `Rc` に変換するために `CoerceUnsized`, `DispatchFromDyn` が実装されている。
  - 一般のサイズ不定型の `Rc` を直接作成するための仕組みが `From` 実装としていくつか用意されており、Rustの高度なテクニックがいくつか見られる。
  - `RcBox` のレイアウトを計算する部分は安全性に関してきわどい実装や間違った実装になっていた時期があり、レイアウト計算の難しさを伺わせる。
  - スライスの `Rc<[T]>` を作るための仕組みは特殊化を駆使して効率的に実装されている。
- `Rc` はスレッドセーフではないが、この「スレッドセーフ」は実際には2つの概念 (`Send`/`Sync`) に分解される。
- `Rc` はデストラクタ(drop)を実装しているが、dropと `&T` と循環参照の微妙な機微を解決するために `#[may_dangle]` と `PhantomData` という道具が用いられている。
- `Rc` はエラーメッセージの調整のためだけにコンパイラに特別扱いされている。このためのフラグはユニットテストをうまく動かすために条件つきで付与されている。
- `Rc` の比較実装は場合によってはポインタ自体の比較と組み合わせて実装されるが、ここからは `PartialEq` と `Eq` の微妙な違いや特殊化とライフタイムの難しい関係が読み取れる。
- `Rc` には `Any`, `MaybeUninit`, `Pin` と組み合わせるためのサポートも用意されている。

これで `Rc` の実装に関して興味深い点はほぼ掘りつくせたと思います。

次回はシングルスレッドの世界を飛び出し、 `Arc` を読むための準備をしたいと思います。