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

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

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

• 第1回 Arc/Rcの基本
• 第2回 Rcを読む基本編
• 第3回 Rcを読む発展編
• 第4回 アトミック変数とメモリ順序
• 第5回 Arcを読む

はじめに

第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の実装を読んでいきます。

定義されている場所

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 に限らず、標準ライブラリの実装にはほぼ漏れなく以下のような属性が付与されています。

#[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つの方法があります。ひとつはコンパイラそのものの「機能」を定義する方法で、syntax::feature_gate モジュール 内に機能の一覧がずらりと並んでいます。

もうひとつが標準ライブラリの「機能」を定義する方法で、これが先ほど見た #[stable] と #[unstable] という2つの属性の役割です。これをつけることで、その機能をユーザーが使えるかどうかを決めることができます。

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

this 引数

Rc のメソッドで、レシーバが self のものと this のものがあることに気付いたでしょうか。たとえばdowngradeの実装とinc_weakの実装は以下のようになっていました。

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 を以下のように呼び出すことはできません:

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 のドキュメントにもはっきり書いてあります:

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) instead of value.get_mut(). This avoids conflicts with methods of the inner type T.)

訳:

Rc の固有「メソッド」はすべて関連関数です。つまり、 value.get_mut() とは書けずに Rc::get_mut(&mut value) という風に呼ぶ必要があります。これにより内部の型 T のメソッドとの衝突を回避しています。

非公開APIの self

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

トレイト実装の self

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

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

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

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

use std::rc::Rc;

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

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

use std::rc::Rc;

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

なお、 Rc, Arc に対する .clone() 呼び出しをチェックする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 を作ることはできます。

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

しかし、何らかの都合で (番兵などのために) ダミーの弱参照が欲しい場合に、わざわざ実体のある Rc を作ってから Weak にするのは無駄感があります。そこで Weak にはダミーの弱参照を生成するための Weak::new が用意されています。

実はこの Weak::new の実装はここ最近2回も変化しています。もともとWeak::new が導入されたタイミングは以下のような実装になっていました。 (今風に少し変更しています)

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>>> を作ってからキャストするほうが安全です。

ともあれ、この方法は無駄だと考えられ、以下のように実装が変更されました:

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

ここで出てくる NonNull::dangling の実装は以下のようになっています。

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 の実装はこれを守っていないように見えますね。実際その問題があって実装が以下のように変更されています。

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 の実際のコードは以下のようになっています。

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 が指定されています。

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

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

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

サイズ不定型の Drop

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

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

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のメタデータ領域からサイズとアラインメントを取得できます。

// サイズ不変型のサイズとアラインメントは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)**です。

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 でも動作するようになっています。

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 でこれらの型強制を使えるようにするには、明示的にトレイトを実装する必要があります。それをしているのが以下の行です。

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)] の一部が安定化され、以下の型も self の型として使えるようになりました。

• Arc<Self>
• Rc<Self>
• Pin<&Self>, Pin<&mut Self>, Pin<Box<Self>>, Pin<Arc<Self>>, Pin<Rc<Self>>

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

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

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

use std::rc::Rc;

struct A;

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

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

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 に関してこれらを可能にしているのが以下の実装です。

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]> を作ることができました:

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

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

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

// 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 (の実装のうちのひとつ) がまさにそれをしています。

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 から始めましょう。

// 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 の中身を完全に作ってからメモリを確保していましたが、サイズ不定の場合は安易にスタック上に保管できないので、まずメモリを確保してから中身を埋めていくことになります。上の行は確保すべきメモリのサイズを計算しています。

何やらコメントで、過去のバグに言及していますね。修正前は以下のコードでした。

// 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) なのでアラインメント違反になります。

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

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

実はこれには不備があり、最終的に以下のように修正されました。

// 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 の冒頭部

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

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

// ...
    value: T,
// ...

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

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

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

#[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バイトになります。

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

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

#[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にする必要がある) という問題だとわかります。

メモリ確保

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

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

// 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などのAPIも存在しますが、基本的に**メモリ不足のエラーから正しく復帰するのは困難**と考えられています。 handle_alloc_error はそのような前提に立ったAPIで、以下のどちらかの挙動をすることが期待されています。

• プロセスを強制終了する。
• パニックによりスレッドを遡上して最低限の片付けをする。

おそらくこの選択肢を選べるようにするためだと思うのですが、 handle_alloc_error は panic と同様に実装を選択できるような仕組みになっています。実際の実装は以下のように与えることができます。

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

パニックハンドラは公式に2種類 (panic_unwind と panic_abort) 提供されていますが、動的メモリ確保エラーハンドラは1種類だけのようです。これは std::alloc 内に以下のように定義されています。

#[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 自身はこの部分に関与せず、以下のようなブラックボックスがあるという前提で仕事をしています:

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

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

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

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

// 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 は以下です:

/// 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あたりはそれに依存しているようなのであまり深く考えなくてもいいのかもしれません。

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

ヘッダ部分の初期化

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

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 などがあります。) なのでおそらくギリギリ問題を回避していると思います。この部分をより堅牢に行うために参照を経由せずにフィールドへのポインタを取得する構文が入る予定です。これが入れば上記のコードは以下のようになるはずです。

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

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

元データの移動

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

// 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 側に移す必要があります。

// 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> の抜け殻 (ヒープ領域)だけ解放します。

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

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

イテレータからの生成

Rc<[T]> を生成する方法は他にも用意されています。まずはイテレータから生成する以下の実装から。

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) を使うために使われます。(標準ライブラリはコンパイラと一緒に配布されるため、不安定機能に依存することが許されています) 特殊化を使うと、特定の条件を満たしているときだけ別の実装を使う、ということができます。

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

/// 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表層に特殊化関連の状態を露出する選択肢はないと思われます。

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

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

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]> に変換する処理はどうなっているかというと、以下のようになっています。

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> の中身を吸い出して、残ったヒープ領域だけ解放しています。

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

イテレータのサイズがわかっている場合は、より効率的な実装が用いられます:

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 が有名ですが、ここでは TrustedLen という別のトレイトが使われています。

この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 です。

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 が実装されたらそちらに置き換えられるでしょう。

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個ずつ要素を取り出して格納していっています。ここまでは簡単です。

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

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

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

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

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)は実行されるという性質に注目し、パニック時の片付けを専用の構造体のデストラクタで行う方法です。今回は以下のようなデストラクタが定義されています。

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して……

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

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

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

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

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

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

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で壊されてはたまらないからです。

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

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

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

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

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 を仮定する必要があります。

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

こちらも特殊化トレイトに実装が移譲されています。

/// 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 自身はどうだったかというと……

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ではまさに Weak::new が言及されています。

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

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

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

Send/Sync

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

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) (昔は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 というフィールドがあります:

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

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

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 を使って表現しています。

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 実装を足したらどうなるでしょうか。

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 処理が安全に挿入できる条件です。

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

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

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

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

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

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

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

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

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

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

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

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

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

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 にそのまま適用してしまうと困ったことになります。先ほどのグラフの例をもう一度出してみます。

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 の条件を考えてみると……

// 擬似コード
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> には普通のカスタムドロップがある状態からはじめてみます。

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 としたらどうなるでしょうか。

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されうる」という関係を表明することができます。

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> に関しても以下のようなダウンキャストの実装があります。

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 の比較演算はアドレス自体ではなく中に保管されている値を比較します。

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

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

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

さて、Rc を比較するさい、ポインタの比較を先に行えばより効率的な比較が行えそうです。実際 PartialEq の実装は以下のように特殊化を用いて最適化されています:

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 は以下のような特殊化ツリーになっています:

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

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

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 を要求する必要があります。たとえば……

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

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

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

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

ヘテロな PartialEq

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

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

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

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

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

#![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 を作ったらどうなるでしょうか。

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 を渡したらどうなるのでしょうか。実は現在の実装は驚くべき挙動を示します。

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年の記事ではそのようなルールの例が提案されています。

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

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:

impl<T, U> SomeTrait for (T, U) {
}

Repeating, as here, means the impl cannot be used to specialize:

impl<T> SomeTrait for (T, T) {
  //                   ^^^^
  // `T` used twice: not always applicable
}

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

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

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

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

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

#[lang]

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

#[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 の言語アイテムマーカーはエラーメッセージのカスタマイズのためだけに存在するからです。

このようなエラーメッセージのためのマーカーは本来の言語アイテムとは区別して、診断アイテムという名前で分離しようと提案されています。

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

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

MaybeUninit

大きなデータを扱うときは、先にメモリ領域を確保してから初期化をしたほうがよい場合があります。これを実現するための仕組みは整備途上ですが、その一部として Rc<MaybeUninit<T>> を扱うためのAPIが最近追加されています。

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

Pin

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

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

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 を読むための準備をしたいと思います。