変性と PhantomData

これを今先送りにして後で直すのは面倒なことになるので、ハードコアなレイアウト関連のことを今やってしまいます。

unsafe な Rust コレクションを作るうえでの、ひどい5騎士がいます。

ありがたいことに、最後の2つは私たちにとって問題にはなりません。

3つ目は、問題にしようと思えばできなくはないですが、割に合いません – LinkedList を選んだ時点で、メモリ効率の戦いはすでに100倍くらい放棄しているのです。

2つ目は、以前の私は本当に重要で std もいろいろ手を入れているものだと強く主張していたものですが、デフォルトは安全で、それをいじる方法は不安定で、デフォルトの制限に気づくには本当にとんでもなく頑張る必要があるので、心配しなくてかまいません。

となると残るのは変性だけです。正直なところ、これもたぶん先送りにできますが、私は今でもコレクションの人間としての誇りを持っているので、変性のやつをやります。

さて、驚きですが、Rust にはサブタイピングがあります。特に、&'big T は &'small T のサブタイプです。なぜでしょうか？それは、あるコードがプログラム内の特定の領域だけ生きる参照を必要としている場合、通常はそれより長く生きる参照を渡してもまったく問題ないからです。直感的にも、それはそのとおりですよね？

なぜこれが重要なのでしょうか？同じ型の2つの値を受け取るコードを考えてみましょう。

fn take_two<T>(_val1: T, _val2: T) { }

これはひどく退屈なコードなので、T=&u32 でも問題なく動くと期待してよいはずですよね？

#![allow(unused)]
fn main() {
fn two_refs<'big: 'small, 'small>(
    big: &'big u32, 
    small: &'small u32,
) {
    take_two(big, small);
}

fn take_two<T>(_val1: T, _val2: T) { }
}

はい、これは問題なくコンパイルできます！

では少し遊んで、そうですね、std::cell::Cell で包んでみましょう。

#![allow(unused)]
fn main() {
use std::cell::Cell;

fn two_refs<'big: 'small, 'small>(
    // 注: この2行が変わりました
    big: Cell<&'big u32>, 
    small: Cell<&'small u32>,
) {
    take_two(big, small);
}

fn take_two<T>(_val1: T, _val2: T) { }
}

error[E0623]: lifetime mismatch
 --> src/main.rs:7:19
  |
4 |     big: Cell<&'big u32>, 
  |               ---------
5 |     small: Cell<&'small u32>,
  |                 ----------- these two types are declared with different lifetimes...
6 | ) {
7 |     take_two(big, small);
  |                   ^^^^^ ...but data from `small` flows into `big` here

えっ？？？ライフタイムには触っていないのに、なぜコンパイラは怒っているのでしょうか！？

ああまあ、ライフタイムの「サブタイピング」関連は本当に単純なので、参照を何かで包むと壊れるに違いありません。ほら、Vec でも壊れます。

#![allow(unused)]
fn main() {
fn two_refs<'big: 'small, 'small>(
    big: Vec<&'big u32>, 
    small: Vec<&'small u32>,
) {
    take_two(big, small);
}

fn take_two<T>(_val1: T, _val2: T) { }
}

    Finished dev [unoptimized + debuginfo] target(s) in 1.07s
     Running `target/debug/playground`

ほら、これもコンパイルできな――待って、何？？？ Vec は魔法なの？？？？？？

ええ、そうです。でも、違います。魔法はずっと私たちの中にあり、その魔法こそが ✨変性✨ です。

血みどろの詳細を全部知りたいなら、Nomicon のサブタイピングの章を読んでください。基本的に、サブタイピングは常に安全とは限りません。特に、可変参照が関わる場合は安全ではありません。mem::swap のようなものを使えるせいで、突然、あっ、ダングリングポインターだ！となるからです。

「可変参照のような」ものは不変です。つまり、それらのジェネリックパラメーターではサブタイピングが起こるのをブロックします。したがって安全性のために、&mut T は T に関して不変であり、Cell<T> も T に関して不変です。なぜなら &Cell<T> は基本的にただの &mut T だからです（内部可変性のため）。

不変でないもののほとんどは共変であり、それは単にサブタイピングがそれを「通り抜けて」通常どおり機能し続けるという意味です（サブタイピングを逆向きにする反変な型もありますが、本当にまれで誰も好きではないので、もう触れません）。

コレクションは一般にデータへの可変ポインターを含むので、それらも不変だと思うかもしれませんが、実際にはそうである必要はありません！ Rust の所有権システムのおかげで、Vec<T> は意味論的には T と等価であり、つまり共変であっても安全なのです！

残念ながら、この定義は不変です。

#![allow(unused)]
fn main() {
pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
}

type Link<T> = *mut Node<T>;

struct Node<T> {
    front: Link<T>,
    back: Link<T>,
    elem: T, 
}
}

では Rust は実際にどのようにしてものごとの変性を決めているのでしょうか？ 1.0 より前の古き良き時代には、望む変性を人々に指定させてみたりもしましたが……それは完全な大惨事でした！サブタイピングと変性を理解するのは本当に難しく、コア開発者たちでさえ基本的な用語について本気で意見が割れていました！そこで私たちは「例による変性」というアプローチに移りました。コンパイラは単にフィールドを見て、その変性をコピーします。何らかの食い違いがあれば、不変が常に勝ちます。なぜならそれが安全だからです。

では、私たちの型定義の何に Rust は怒っているのでしょうか？ *mut です！

Rust の生ポインターは、基本的には何でもできるようにしようとしていますが、安全性機能がちょうど1つだけあります。ほとんどの人は、変性とサブタイピングが Rust に存在することをまったく知らず、誤って共変になっているとひどく危険なので、*mut T は不変です。なぜなら、それが &mut T 「として」使われている可能性が高いからです。

これは、Rust でコレクションを書くことに長い時間を費やしてきたまさに私という人間にとって、非常に腹立たしいことです。だから私が std::ptr::NonNull を作ったとき、この小さな魔法を入れました。

*mut T とは異なり、NonNull<T> は T に関して共変になるように選ばれました。これにより、共変な型を構築するときに NonNull<T> を使えるようになりますが、実際には共変であるべきでない型で使うと、健全性を損なうリスクが生じます。

でも、ちょっと待ってください。そのインターフェイスは *mut T を中心に作られています。どういうことでしょう！ただの魔法なのでしょうか？！見てみましょう。

#![allow(unused)]
fn main() {
pub struct NonNull<T> {
    pointer: *const T,
}


impl<T> NonNull<T> {
    pub unsafe fn new_unchecked(ptr: *mut T) -> Self {
        // 安全性: 呼び出し元は `ptr` が非 null であることを保証しなければなりません。
        unsafe { NonNull { pointer: ptr as *const T } }
    }
}
}

いいえ。ここに魔法はありません！ NonNull は単に *const T が共変であるという事実を悪用し、それを代わりに格納しているだけです。API 境界で *mut T との間でキャストを行い、*mut T を格納している「ように見せて」いるのです。トリックはそれだけです！これが Rust のコレクションが共変である仕組みです！そして、これはみじめです！だから私は、良いポインター型があなたの代わりにそれをやってくれるようにしました！どういたしまして！サブタイピングのフットガンをお楽しみください！あなたのあらゆる問題への解決策は NonNull を使うことです。そして再び null 許容ポインタを持ちたくなったら、Option<NonNull<T>> を使います。本当にわざわざそんなことをするんですか..?

はい！最悪ですが、私たちはプロダクショングレードのリンクリストを作っているので、嫌なこともきちんと受け入れて、難しいやり方で物事を進めます（単に裸の *const T を使ってあちこちでキャストしてもよいのですが、エルゴノミクス科学のために、これがどれほど苦痛なのかを本気で見てみたいのです…）。

というわけで、最終的な型定義は次のようになります。

#![allow(unused)]
fn main() {
use std::ptr::NonNull;

// !!!ここが変更されました!!!
pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
}

type Link<T> = Option<NonNull<Node<T>>>;

struct Node<T> {
    front: Link<T>,
    back: Link<T>,
    elem: T, 
}
}

…いや待ってください、最後にもう 1 つだけ。生ポインタ関連のことをするときはいつでも、ポインタを保護するために Ghost を追加するべきです。

use std::marker::PhantomData;

pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
    /// 意味論上、T の値を値として格納します。
    _boo: PhantomData<T>,
}

このケースでは、PhantomData が実際に必要だとは思いませんが、NonNull（または一般に生ポインタ）を使うときはいつでも、安全のため、そして自分が何をしているつもりなのかをコンパイラや他の人に明確に示すために、常に追加するべきです。

PhantomData は、あなたの型の中に概念上は存在するけれど、さまざまな理由（間接参照、型消去、…）で実際には存在しない追加の「例」フィールドをコンパイラに与える方法です。このケースでは、自分たちの型が T の値を格納している「かのように」振る舞うと主張しているため NonNull を使っているので、それを明示するために PhantomData を追加します。

stdlib がこれを行う理由は実際には他にもあります。というのも、呪われた Drop Check overrides にアクセスできるからです。しかしその機能は何度も作り直されてきたので、PhantomData の件が今でもそれにとって意味のあるものなのか、実際のところ私はわかっていません。それでも私は永遠にそれをカーゴカルトし続けるつもりです。Drop Check Magic が脳に焼き付いているので！

（Node は文字どおり T を格納しているので、これをする必要はありません。やったね！）

…さて、本当にこれでレイアウトは完了です！実際の基本機能に進みましょう！

Keyboard shortcuts

Learning Rust With Entirely Too Many Linked Lists 日本語版

変性と PhantomData