Rust 裏本

高度で危険な Rust Programming のための闇の技法

NOTE: この文書はドラフトです。重大な間違いを含んでいるかもしれません。

私に与えられたのは、望んだようなプログラムではなく、身を震わせるような暗黒と言い表せないような孤独であった。そして私はついに、誰ひとり口にしようともしなかった恐ろしい真実、ささやくことすらできない神秘中の神秘を目にしたのだ。石のように硬く、耳障りな音をたてるこの言語は、ロンドンが古きロンドンではなく、パリが古きパリではないように、Rust の御代をとこしえにするものではなく、実はきわめて危険で、不完全に防腐処理された、だらしなく寝そべった死体だったのだ。そこにはコンパイル時に生まれた奇妙な生き物たちが所在なさげに蔓延っていた。

（訳注: H.P. ラヴクラフトの小説「あの男」のパロディのようです。）

この本は、危険な Rust プログラムを正しく書くために理解しなくてはいけない、不愉快な詳細について詳しく見ていきます。このような性質上、この文書は今まで語られることのなかった恐怖を解き放ち、あなたの精神を何十億もの絶望のかけらに砕いてしまうかもしれません。

もし貴方が Rust とともに長く幸せな人生を歩みたいと望むなら、今すぐに背を向けて、この本を見てしまったことを忘れるのです。貴方には必要ないのですから。しかし、危険なコードを書く意思がもしも貴方にあるのなら、もしくはこの言語の最重要部にただ踏み込んでみたいのなら、この本は代えがたい情報をもたらすでしょう。

The Book とは異なり、ここでは多くの事前知識を前提としています。特に基本的なシステムプログラミングと Rust に精通していなくてはなりません。もし貴方がそうでないなら、まず The Book を読む べきでしょう。とはいえ、The Book は前提ではありませんし、適切な場面で基本知識を復習する機会を与えます。The Book を飛ばしてこの本を読んでも構いませんが、すべてが基礎から説明されるわけではないことを覚えておいてください。

はっきり言いますが、この本は詳細について深く説明します。例外の安全性、ポインタエイリアシング、メモリモデル、そして型理論についても少し。また、様々な種類の安全性や保証についてもたくさん説明します。

訳注: 原文はこちら、日本語の翻訳文書はこちらです。

安全と危険のご紹介

安全な「高級」言語のプログラマは、本質的なジレンマに直面します。何が欲しいかをただ伝えるだけで、 それがどのように実現されるかを悩む必要がないのは 本当に 素晴らしいのですが、それが許容できないほどの ひどいパフォーマンスをもたらすこともあります。 期待するパフォーマンスを得るために、明瞭で慣用的なやり方を断念しなくてはいけないかもしれないし、 または、どうしようもないと諦めて、それほど心地よくない 危険な 言語で実装することを決心するかもしれません。

もっと悪いことに、オペレーティングシステムと直接話したい時には、C 言語 という危険な言語で 会話を しなくてはなりません。C 言語はつねに存在し、逃れることはできないのです。 C 言語はプログラミングの世界での橋渡し言語だからです。 他の安全な言語も、たいてい C 言語のインターフェースを世界中に野放しでさらしています。 理由の如何にかかわらず、あなたのプログラムが C 言語と会話した瞬間に、安全ではなくなるのです。

とはいえ、Rust は 完全に 安全なプログラミング言語です。

・・・いえ、Rust は安全なプログラミング言語をもっていると言えます。一歩下がって考えてみましょう。

Rust は 2 つのプログラミング言語から成り立っていると言えます。安全な Rust と 危険な Rust です。 安全な Rust は、本当に全く安全ですが、危険な Rust は、当然ですが、本当に全く安全ではありません。 実際、危険な Rust では本当に本当に危険な事ができるのです。

安全な Rust は真の Rust プログラミング言語です。もしあなたが安全な Rust だけでコードを書くなら、 型安全やメモリ安全性などを心配する必要はないでしょう。 ヌルポインタやダングリングポインタ、馬鹿げた「未定義な挙動」などに我慢する必要はないのです。

なんて素晴らしいんだ。

また、標準ライブラリにはすぐに使える十分なユーティリティが揃っています。 それを使えば、ハイパフォーマンスでかっこいいアプリケーションやライブラリを、 正当で慣用的な安全な Rust で書けるでしょう。

でも、もしかしたらあなたは他の言語と話したいかもしれません。もしかしたら標準ライブラリが提供していない 低レイヤを抽象化しようとしているのかもしれないし、もしかしたら標準ライブラリを書いている （標準ライブラリは Rust で書かれています）のかもしれないし、もしかしたらあなたがやりたい事は、 型システムが理解できない、ぎょっとするようなことかもしれません。 もしかしたらあなたには危険な Rust が必要かもしれません。

危険な Rust のルールとセマンティクスは、安全な Rust と同じです。 ただし、危険な Rust ではちょっと多くの事ができ、それは間違いなく安全ではありません。

危険な Rust であなたができる事は、たったこれだけです。

• 生ポインタが指す値を得る
• unsafe な関数を呼ぶ（C 言語で書かれた関数や、intrinsic、生のアロケータなど）
• unsafe なトレイトを実装する
• 静的な構造体を変更する

これだけです。これらの操作がなぜ「危険」と分類されているかというと、 間違って使うととても恐ろしい「未定義な挙動」を引き起こすからです。 「未定義な挙動」が起きると、コンパイラは、あなたのプログラムにとってどんな悪いことでもできるようになります。 何があっても「未定義な挙動」を起こすべきではないです。

C 言語と違って、Rust では「未定義な挙動」は限定されています。 言語コアは次のような事が起きるのを防ぎます。

• ヌルポインタやダングリングポインタの参照外し
• 未初期化のメモリ を読む
• ポインタエイリアスルール を破る
• 不正なプリミティブな値を生成する
  • ダングリング参照、ヌル参照
  • 0 でも 1 でもない bool 値
  • 未定義な enum 判別式
  • [0x0, 0xD7FF] と [0xE000, 0x10FFFF] 範囲外の char 値
  • utf8 ではない str 値
• 他の言語に巻き戻す
• データ競合 を引き起こす

これだけです。これが、Rust が防ぐ「未定義な挙動」の原因です。 もちろん、危険な関数やトレイトが「未定義な挙動」を起こさないための他の制約を作り出す事は可能ですが、 そういった制約が破られた場合、たいてい上の問題のどれかを引き起こします。 コンパイラ intrinsic がその他の制約を生み出し、コードの最適化に関する特別な仮定をすることもあります。

Rust はその他の疑わしい操作については、とても寛容です。 Rust は次の操作を「安全」だと判断します。

• デッドロック
• 競合状態
• メモリリーク
• デストラクタを呼ぶことに失敗する
• 整数のオーバーフロー
• プログラムの異常終了
• 本番環境のデータベースを削除してしまう事

とはいえ、こういうことをできてしまうプログラムは恐らく間違っていると言えるでしょう。 Rust はこういった事を起きにくくするためのツールをたくさん提供します。 しかし、これらの問題を完全に防ぐのは現実的ではないと考えられています。

安全と危険の相互作用

安全な Rust とアンセーフな Rust とはどう関係しているのでしょうか? どのように影響し合うのでしょうか?

unsafe キーワードがインターフェースとなり、安全な Rust とアンセーフな Rust とを分離します。 このため、安全な Rust は安全な言語で、アンセーフな部分は完全に境界外に管理されている、と言うことができるのです。

unsafe は 2 つの目的に使われます。コンパイラがチェックできない契約が存在する事を宣言することと、 コードが契約に準拠していることがプログラマによってチェックされた事を宣言する事です。

関数 と トレイトの宣言 に未チェックな契約が存在する事を、unsafe を使って示すことができます。 関数に unsafe を使うと、ドキュメントを読んで、 要求された契約を守るように関数を使うことを、その関数のユーザーに要請することになります。 トレイトの宣言に unsafe を使うと、そのトレイトを実装するユーザーに対し、ドキュメントをチェックして契約を守るよう要請します。

コードブロックに使われた unsafe は、そのブロックで呼ばれているアンセーフな関数が要求する契約は守られていて、コードが信頼出来る事を意味します。unsafe をトレイトの実装に使うと、その実装がトレイトのドキュメントに書かれている契約に準拠している事を示します。

標準ライブラリにはいくつものアンセーフな関数があります。例えば、

• slice::get_unchecked は未チェックのインデックス参照を実行します。自由自在にメモリ安全性に違反できます。
• mem::transmute は、型安全の仕組みを好きなようにすり抜けて、ある値が特定の型であると再解釈します（詳細は 変換 をみてください）。
• サイズが確定している型の生ポインタには、固有の offset メソッドがあります。渡されたオフセットが LLVM が定める "境界内" になければ、未定義の挙動を引き起こします。
• すべての FFI 関数は unsafe です。なぜなら Rust コンパイラは、他の言語が実行するどんな操作もチェックできないからです。

Rust 1.0 現在、アンセーフなトレイトは 2 つしかありません。

• Send は API を持たないマーカートレイトで、実装された型が他のスレッドに安全に送れる（ムーブできる）ことを約束します。
• Sync もマーカートレイトで、このトレイトを実装した型は、共有された参照を使って安全に複数のスレッドで共有できる事を約束します。

また、多くの Rust 標準ライブラリは内部でアンセーフな Rust を使っています。ただ、標準ライブラリの 実装はプログラマが徹底的にチェックしているので、アンセーフな Rust の上に実装された安全な Rust は安全であると仮定して良いでしょう。

このように分離する目的は、結局のところ、安全な Rust のたった一つの基本的な性質にあります。

どうやっても、安全な Rust では未定義な挙動を起こせない。

このように安全とアンセーフを分けると、安全な Rust は、自分が利用するアンセーフな Rust が正しく書かれている事、 つまりアンセーフな Rust がそれが守るべき契約を実際に守っている事、を本質的に信頼しなくてはいけません。 逆に、アンセーフな Rust は安全な Rust を注意して信頼しなくてはいけません。

例えば、Rust には PartialOrdトレイトと Ordトレイトがあり、単に比較可能な型と全順序が 定義されている型（任意の値が同じ型の他の値と比べて等しいか、大きいか、小さい）とを区別します。 順序つきマップの BTreeMap は半順序の型には使えないので、キーとして使われる型が Ordトレイトを 実装している事を要求します。 しかし BTreeMap の実装ではアンセーフな Rust が使われていて、アンセーフな Rust は渡された Ord の実装が 適切であるとは仮定できません。 BTreeMap 内部のアンセーフな部分は、キー型の Ord の実装が全順序ではない場合でも、必要な契約が すべて守られるよう注意深く書かれなくてはいけません。

アンセーフな Rust は安全な Rust を無意識には信頼できません。アンセーフな Rust コードを書くときには、 安全な Rust の特定のコードのみに依存する必要があり、 安全な Rust が将来にわたって同様の安全性を提供すると仮定してはいけません。

この問題を解決するために unsafe なトレイトが存在します。理論上は、BTreeMap 型は キーが Ord ではなく、新しいトレイトUnsafeOrd を実装する事を要求する事ができます。 このようなコードになるでしょう。

#![allow(unused)]
fn main() {
use std::cmp::Ordering;

unsafe trait UnsafeOrd {
    fn cmp(&self, other: &Self) -> Ordering;
}
}

この場合、UnsafeOrd を実装する型は、このトレイトが期待する契約に準拠している事を示すために unsafe キーワードを使うことになります。 この状況では、BTreeMap 内部のアンセーフな Rust は、キー型が UnsafeOrd を正しく実装していると 信用する事ができます。もしそうで無ければ、それはトレイトの実装の問題であり、 これは Rust の安全性の保証と一致しています。

トレイトに unsafe をつけるかどうかは API デザインにおける選択です。 Rust では従来 unsafe なトレイトを避けてきました。そうしないとアンセーフな Rust が 蔓延してしまい、好ましくないからです。 Send と Sync が unsafe となっているのは、スレッドの安全性が 基本的な性質 であり、 間違った Ord の実装に対して危険なコードが防衛できるのと同様の意味では防衛できないからです。 あなたが宣言したトレイトを unsafe とマークするかどうかも、同じようにじっくりと考えてください。 もし unsafe なコードがそのトレイトの間違った実装から防御することが合理的に不可能であるなら、 そのトレイトを unsafe とするのは合理的な選択です。

余談ですが、unsafe なトレイトである Send と Sync は、それらを実装する事が安全だと 実証可能な場合には自動的に実装されます。 Send は、Send を実装した型だけから構成される型に対して、自動的に実装されます。 Sync は、Sync を実装した型だけから構成される型に対して、自動的に実装されます。

これが安全な Rust とアンセーフな Rust のダンスです。 これは、安全な Rust をできるだけ快適に使えるように、しかしアンセーフな Rust を書くには それ以上の努力と注意深さが要求されるようなデザインになっています。 この本の残りでは、どういう点に注意しなくはいけないのか、 アンセーフな Rust を維持するための契約とは何なのかを議論します。

Unsafe と連携する

たいていの場合、アンセーフな Rust を扱うツールは、限定された状況やバイナリでしか使えないようになっています。 残念なことに、現実はそれよりも極めて複雑です。例えば、以下の簡単な関数を見てみましょう。

#![allow(unused)]
fn main() {
fn index(idx: usize, arr: &[u8]) -> Option<u8> {
    if idx < arr.len() {
        unsafe {
            Some(*arr.get_unchecked(idx))
        }
    } else {
        None
    }
}
}

この関数は明らかに安全です。インデックスが範囲内である事をチェックし、 範囲内であれば未チェックで配列をインデックス参照します。 しかしこのような自明な関数でさえも、unsafe ブロックのスコープには疑問が残ります。 < を <= に変えてみましょう。

#![allow(unused)]
fn main() {
fn index(idx: usize, arr: &[u8]) -> Option<u8> {
    if idx <= arr.len() {
        unsafe {
            Some(*arr.get_unchecked(idx))
        }
    } else {
        None
    }
}
}

安全なコードを変更しただけなのに、今やこのプログラムは安全ではなくなりました。 これが安全性の本質的な問題です。局所的ではないのです。 アンセーフな操作の健全性は、通常 "安全" な操作によって構築された状態に依存しているのです。

安全性は、アンセーフな操作をしたからといってあらゆる他の悪い事を考慮する必要はない、という意味ではモジュール化されています。 例えば、スライスに対して未チェックのインデックスアクセスをしても、スライスがヌルだったらどうしようとか、 スライスが未初期化のメモリを含んでいるかもといった心配をする必要はありません。基本的には何も変わりません。 しかし、プログラムは本質的にステートフルであり、アンセーフな操作はその他の任意の状態に依存しているかもしれない、 という意味で、安全性はモジュール化されてはいないのです。

実際にステートフルな状況を考えると、事態はもっと厄介になります。 Vec の簡単な実装を見てみましょう。

use std::ptr;

// この定義は不完全であることに注意してください。Vec の実装に関するセクションをみてください。
pub struct Vec<T> {
    ptr: *mut T,
    len: usize,
    cap: usize,
}

// この実装ではサイズが 0 の型を正しく扱えないことに注意してください。
// ここでは、すべてが 0 以上の固定サイズの型しか存在しない素敵な仮想的な世界を仮定します。
impl<T> Vec<T> {
    pub fn push(&mut self, elem: T) {
        if self.len == self.cap {
            // この例では重要ではありません。
            self.reallocate();
        }
        unsafe {
            ptr::write(self.ptr.offset(self.len as isize), elem);
            self.len += 1;
        }
    }

    fn reallocate(&mut self) { }
}

fn main() {}

このコードはとてもシンプルなので、それなりに監査して検証できるでしょう。 それでは次のメソッドを追加してみましょう。

fn make_room(&mut self) {
    // キャパシティを大きくする
    self.cap += 1;
}

このコードは 100% 安全な Rust ですが、同時に完全に不健全です。 キャパシティの変更は、Vec の普遍条件（cap は Vec にアロケートされたスペースを表している）を破ることになります。 Vec の他のコードはこれを防げません。 Vec は cap フィールドを検証できないので、信頼しなくてはならない のです。

unsafe は関数そのものを汚染するだけでなく、モジュール 全体を汚染します。 一般的に、アンセーフなコードのスコープを制限する唯一で完全無欠の方法は、モジュール境界での非公開性を利用することです。

しかしこれは 完璧な やり方です。 make_room は、public メソッドではないので、Vec の健全性の問題にはなりません。 この関数を定義しているモジュールだけがこの関数を呼べるのです。 また、make_room は Vec の private フィールドを直接アクセスしているので、 Vec と同じモジュールでのみ定義できます。

このように、複雑な普遍条件に依存した安全な抽象化を提供することは可能なのです。 これは安全な Rust とアンセーフな Rust の関係において決定的に重要です。 すでに見たように、アンセーフなコードは 特定 の安全なコードを信頼しなくてはなりませんが、 安全なコード 一般 を信頼することはできません。 安全なコードを書くときには気にする必要はないのですが、アンセーフなコードでは、 トレイトの任意の実装や渡された任意の関数が行儀よく振る舞うことを期待することはできないのです。

しかし、安全なコードが状態をあらゆる方法でぐちゃぐちゃにすることを、アンセーフなコードが防げないのだとしたら、 安全性とは絵に描いた餅かもしれません。 ありがたいことに、非公開性を利用することで、 任意のコードが重要な状態をめちゃくちゃにしないよう防ぐことができるのです。

安全性は無事です!

Rust のデータ表現

低レイヤのプログラミングでは、データのレイアウトがとても重要です。本当に重要な問題です。 また言語の残りの部分の多くにわたって影響を及ぼします。 ということで、Rust でどのようにデータが表現されるかを詳しく見るところから始めましょう。

repr(Rust)

最初に重要なこととして、すべての型はバイト単位で指定されたアラインメントに従います。 ある型のアラインメントは、値を格納する有効なアドレスを規定します。 アラインメント n の値は、n の倍数のアドレスにのみ格納できます。 つまりアラインメント 2 は、偶数アドレスにのみ格納できることを意味し、 アラインメント 1 はどこにでも格納できることになります。 アラインメントの最小値は 1 で、常に 2 のべき乗になります。 ほとんどのプリミティブ型はそのサイズにアラインメントされますが、 これはプラットフォーム依存の挙動です。 特に x86 では u64 と f64 は 32ビットにアラインされるかもしれません。

型のサイズは、常にそのアラインメントの倍数でなくてはなりません。 こうすることで、サイズの倍数をオフセットすることで、その型の配列のインデックスアクセスになります。 動的にサイズが決まる型 の場合、型のサイズとアラインメントは静的にはわからない場合があることに注意してください。

Rust では次の方法で複合データのメモリレイアウトを制御することができます。

• 構造体（名前付き直積型）
• タプル（名前なし直積型）
• 配列（同じ種類の型の直積型）
• enum（名前付き直交型。またはタグ付き共用体）

enum のすべての要素が関連データを持たない場合、その enum は C-like と呼ばれます。

複合データのアラインメントは、その要素のうち最大のアラインメントと同じです。 そのために、Rust は必要なときにはパディングを挿入して、 すべてのフィールドが適切にアラインされ、 また全体のサイズがアラインメントの倍数になるようにします。 例えば、

#![allow(unused)]
fn main() {
struct A {
    a: u8,
    b: u32,
    c: u16,
}
}

この構造体は、メンバーのプリミティブ型が対応するサイズにアラインされるアーキテクチャでは、 32ビットにアラインされます。そのため全体の構造体のサイズも 32ビットの倍数になります。 このようになるでしょう。

#![allow(unused)]
fn main() {
struct A {
    a: u8,
    _pad1: [u8; 3], // `b` のアラインメントのため
    b: u32,
    c: u16,
    _pad2: [u8; 2], // 全体のサイズを 4バイトの倍数にするため
}
}

この構造体には 間接参照はありません。C と同様に、すべてのデータは構造体の内部に格納されます。 しかし、配列は例外（配列は隙間なく順にパックされます）ですが、Rust ではデータレイアウトは デフォルトでは規定されていません。以下の 2 つの構造体の定義を見てみましょう。

#![allow(unused)]
fn main() {
struct A {
    a: i32,
    b: u64,
}

struct B {
    a: i32,
    b: u64,
}
}

Rust は A の 2 つのインスタンスが同じようにレイアウトされることを保証します。 しかし、A のインスタンスと B のインスタンスとが同じフィールド順や、同じパディングを持つことを 保証しません。（現実的には同じにならない理由はないのですが）

この A, B の例では、レイアウトが保証されないなんて融通が利かないと思うかもしれませんが、 他の機能を考えると、Rust がデータレイアウトを複雑にいじくれるようにするのは好ましいのです。

例えば、次の構造体を見てみましょう。

#![allow(unused)]
fn main() {
struct Foo<T, U> {
    count: u16,
    data1: T,
    data2: U,
}
}

さて、単体化した Foo<u32, u16> と Foo<u16, u32> とを考えてみます。 もし Rust が指定された順にフィールドをレイアウトしなくてはならないとすると、 アラインメントの要求を満たすために、パディングしなくてはなりません。 つまりもし Rust がフィールドを並び替えられないとすると、次のような型を生成すると思われます。

struct Foo<u16, u32> {
    count: u16,
    data1: u16,
    data2: u32,
}

struct Foo<u32, u16> {
    count: u16,
    _pad1: u16,
    data1: u32,
    data2: u16,
    _pad2: u16,
}

後者の例ははっきり言ってスペースの無駄遣いです。 したがって、スペースを最適に使うには、異なる単体化には異なるフィールド順序が必要になります。

これは仮定の最適化で、Rust 1.0 ではまた実装されていないことに注意してください。

Enum については、もっと複雑な検討が必要になります。つまり、この enum

#![allow(unused)]
fn main() {
enum Foo {
    A(u32),
    B(u64),
    C(u8),
}
}

は、次のようにレイアウトされるでしょう。

#![allow(unused)]
fn main() {
struct FooRepr {
    data: u64, // `tag` によって、u64, u32, u8 のいずれかになります
    tag: u8,   // 0 = A, 1 = B, 2 = C
}
}

実際にこれが、データが一般的にどのようにレイアウトされるかの大体の説明となります。

ところが、このような表現が非効率な場合もあります。 わかりやすい例としては、Rust の "ヌルポインタ最適化" があります。 これは、ある enum がデータを持たないメンバー（たとえば None）と、（ネストしてるかもしれない）ヌルを取らないメンバー（たとえば &T）から構成される場合、ヌルポインタをデータを持たないメンバーと解釈することができるので、タグが不要になります。 その結果、たとえば size_of::<Optiona<&T>>() == size_of::<&T>() となります。

Rust には、ヌルポインタになりえない型や、ヌルポインタを含まない型がたくさんあります。 例えば Box<T>, Vec<T>, String, &T, &mut T などです。 同様に、ネストした複数の enum が、タグを単一の判別子に押し込めることも考えられます。 タグが取り得る値は、定義により限られているからです。 原理的には、enum はとても複雑なアルゴリズムを使って、ネストした型を特別な制約のもとで表現し、 ビットを隠すことができるでしょう。 このため、enum のレイアウトを規定しないでおくことは、現状では 特に 好ましいのです。

奇妙なサイズの型

私たちは、型は 0 以上の固定サイズを持つと通常考えます。でも常にそうであるとは限りません。

動的サイズの型（DST: Dynamically Sized Type）

実際に、Rust は動的にサイズが決まる型（DST）、静的にはサイズやアラインメントがわからない型、 をサポートしています。 一見すると、これは少し馬鹿げているようです。型をうまく扱うためには、 サイズや型を知らなければいけないですから。 こう考えると DST は通常の型ではありません。サイズが静的にわからないので、 ある種のポインタの裏にしか存在できないのです。 DST を指すポインタは結果的に、普通のポインタと DST を補完する情報（以下で詳しく説明します）から構成される、 太った ポインタになります。

言語が提供する DST のうち重要なものが 2 つあります。トレイトオブジェクトとスライスです。

トレイトオブジェクトは、それが指すトレイトを実装するある型を表現します。 元となった型は消去されますが、vtable とリフレクションとによって実行時にはその型を利用することができます。 つまり、Trait オブジェクトを補完する情報とは vtable へのポインタとなります。

スライスとは、単純にある連続したスペース（通常は配列か Vec）のビューです。 スライスを補完する情報とは、単にポインタが指す要素の数です。

構造体は、最後のフィールドとして DST を直接含むことができますが、その構造体自体も DST になります。

#![allow(unused)]
fn main() {
// 直接スタックには置けません。
struct Foo {
    info: u32,
    data: [u8],
}
}

Rust 1.0 時点では、最後のフィールドが正しくアラインメントされていない DST 構造体は正しく動きません

サイズが 0 の型（ZST: Zero Sized Type）

Rust ではなんと、スペースを持たない型を使うことができます。

#![allow(unused)]
fn main() {
struct Foo; // フィールドがない = サイズ 0

// すべてのフィールドのサイズがない = サイズ 0
struct Baz {
    foo: Foo,
    qux: (),      // 空のタプルにはサイズがありません
    baz: [u8; 0], // 空の配列にはサイズがありません
}
}

サイズ 0 の型（ZST）は、当然ながら、それ自体ではほとんど価値がありません。 しかし、多くの興味深いレイアウトの選択肢と組み合わせると、ZST が潜在的に役に立つことがいろいろな ケースで明らかになります。Rust は、ZST を生成したり保存したりするオペレーションが no-op に 還元できることを理解しています。 そもそも、ZST はスペースを要求しないので、保存することには意味がありません。 また ZST は 1 つの値しかとらないので、ZST を読み込む操作は、 代わりに無から ZST を作り出すことができ、この操作もスペースを必要としないので no-op と同じです。

究極の ZST の利用法として、Set と Map を考えてみましょう。 Map<Key, Value> があるときに、Set<Key> を Map<Key, UselessJunk> の 簡単なラッパとして実装することはよくあります。 多くの言語では、UselessJunk のスペースを割り当てる必要があるでしょうし、 結果的に使わない UselessJunk を保存したり読み込んだりする必要もあるでしょう。 こういったことが不要であると示すのはコンパイラにとっては難しい仕事でしょう。

しかし Rust では、単に Set<Key> = Map<Key, ()> と言えばいいだけなのです。 Rust は静的な解析で、読み込みや保存が無意味であること、メモリ割当が必要ないことを理解します。 結果として単態化したコードは、HashSet のためにカスタマイズされ、 HashMap を使う場合のオーバーヘッドはなくなります。

安全なコードは ZST について心配する必要はありませんが、アンセーフなコードは サイズ 0 の型を使った時の結果について注意しなくてはなりません。 特に、ポインタのオフセットは no-op になることや、 （Rust のデフォルトである jemalloc を含む）標準的なメモリアロケータは、 サイズ 0 の割り当て要求には nullptr を返すこと （これはメモリ不足と区別がつきません）に注意してください。

空の型

Rust では、インスタンスを生成できない型を宣言することもできます。 こういう型は、型レベルの話にのみ出てきて、値レベルには出てきません。 空の型は、識別子を持たない enum として宣言できます。

#![allow(unused)]
fn main() {
enum Void {} // 識別子なし = 空
}

空の型は、ZST よりもまれにしか使いません。 空の型がもっとも必要になる例としては、型レベルの到達不可能性を示す時です。 例えば、ある API は、一般に Result を返す必要がありますが、 特定のケースでは絶対に失敗しないことがわかっているとします。 Result<T, Void> を返すことで、この事実を型レベルで伝えることが可能です。 Void 型の値を提供することはできないので、この Result は Err になり得ないと静的にわかります。 そのため、この API の利用者は、自信を持って Result をアンラップすることができます。

原理的に、Rust ではこの事実をもとに、興味深い解析と最適化が可能です。 たとえば、Result<T, Void> は Err にはなり得ないので、 T と表現することができます。以下のコードがコンパイルに通るようにもできるでしょう。

enum Void {}

let res: Result<u32, Void> = Ok(0);

// Err は存在しないので、Ok になることに疑問の余地はありません。
let Ok(num) = res;

ただし、どちらの例も現時点では動きません。 つまり、Void 型による利点は、静的な解析によって、特定の状況が起こらないと確実に言えることだけです。

最後に細かいことを一つ。空の型を指す生ポインタを構成することは有効ですが、 それを参照外しすることは、意味がないので、未定義の挙動となります。 つまり、C における void * と同じような意味で *const Void を使うこと出来ますが、 これは、安全に参照外しできる型（例えば *const ()）と比べて何も利点はありません。

代替メモリレイアウト

Rust では、デフォルトとは異なる、代替のデータレイアウトを指定することができます。

repr(C)

これは最も重要な repr です。意味はとても単純で、「C がやるようにやれ」です。 フィールドの順序、サイズ、アラインメントが、C や C++ に期待するのと全く同じになります。 FFI 境界を超えるであろう型は、すべて repr(C) になるべきです。 C はプログラミング界の共通言語なのですから。 また、値を別の型として再解釈する、といった複雑なトリックをやる場合にも repr(C) は必須です。

しかし、Rust の風変わりなデータレイアウト機能との相互作用も忘れてはいけません。 「FFI のため」と「データレイアウトのため」という二つの目的があるため、 FFI 境界を超えることが無意味または問題になるような型にも repr(C) は適用されます。

• ZST のサイズはやはり 0 になります。これは C の標準的な挙動ではないし、C++ の挙動 （空の型も 1 byte を消費します）とは明確に異なります。

• DST, タプル, タグ付き共用体という概念は C には存在しないため、FFI では安全に使えません。

• repr(C) を適用した状況では、タプルは構造体と似ています。構造体との違いは、フィールドに名前がないことだけです。

• 型に drop flags が付いていても、その型は追加されます。

• enum については、repr(u*) （次のセクションで説明します）と同等です。選んだサイズが、対象となるプラットフォームの C ABI でのデフォルトの enum のサイズとなります。C での enum のデータ表現は実装依存なので、これはベストの推測でしかないことに注意してください。とくに、対象の C コードが特定のフラグつきでコンパイルされた場合に、正しく動かないかもしれません。

repr(u8), repr(u16), repr(u32), repr(u64)

これらは、enum を C っぽくレイアウトするように指示します。 enum の要素が指定した整数をオーバーフローする場合、コンパイルエラーとなります。 オーバーフローする値を 0 に設定するよう Rust に指定することもできますが、 2 つの異なる enum 要素が同じ値を取ることはできません。

C っぽくない enum （訳注：要素がパラメータをとるような enum）に repr(u*) を適用すると、 ヌルポインタ最適化のようなある種の最適化ができなくなります。

この repr を構造体につかっても効果はありません。

repr(packed)

repr(packed) を使うと Rust はパディングを一切取り除き、すべてをバイト単位にアラインします。 メモリ使用量は改善しますが、悪い副作用を引き起こす可能性が高いです。

特にほとんどのアーキテクチャは、値がアラインされていることを強く望んでいます。 つまりアラインされていないデータの読み込みにはペナルティがある（x86）かもしれませんし、 失敗する（いくつかの ARM チップ）かもしれません。 パックされたフィールドを直接読んだり書いたりするという単純なケースでは、 コンパイラがシフトやマスクを駆使してアラインメントの問題を隠してくれるかもしれません。 しかし、パックされたフィールドへの参照を扱う場合には、アラインされてない読み込みを避けるような コードをコンパイラが生成することは期待できないでしょう。

Rust 1.0 時点では、これは未定義な挙動です。

repr(packed) は気軽に使えるものではありません。 極端な要求に応えようとしているのでない限り、使うべきではありません。

この repr は repr(C) や repr(rust) の修飾子として使えます。

所有権とライフタイム

所有権は Rust が爆発的に有名になるきっかけとなった機能です。 所有権により、Rust は完全にメモリ安全かつ、ガーベジコレクションがないため効率的になります。 所有権の詳細に立ち入る前に、この機能がなぜ必要なのかを考えてみましょう。

ガーベジコレクション（GC）が常に最適なソリューションではないこと、 手動のメモリ管理の方が望ましいケースもあることには異論はないと思います。 もしそう思わないなら、別の言語に興味を持った方が良いですよ?

あなたが GC のことをどう思っていようとも、GC はコードを安全にするためにとてつもない恩恵をもたらしました。 オブジェクトが早すぎるタイミングで消えてしまう心配が全く必要ないんです。 （とはいえ、そのオブジェクトへのポインタをその時点まで保有しておくべきかどうかというのは別の問題ですが・・・） これは、C や C++ プログラムが対処しなければならない、広範囲に広がっている問題です。 GC の無い言語を使ったことのあるひとなら誰でも一度はやってしまった、この単純な間違いを見てみましょう。

fn as_str(data: &u32) -> &str {
    // 文字列を生成する
    let s = format!("{}", data);

    // しまった! この関数内でしか存在しないオブジェクトへの
    // 参照を返してしまった!
    // ダングリングポインタだ! メモリ解放後の参照だ! うわーー!
    // （このコードは Rust ではコンパイルエラーになります）
    &s
}

これこそが、Rust の所有権システムが解決する問題なのです。 Rust は &s が生存するスコープを理解し、&s がそのスコープ外に逃げることを防ぎます。 しかし、この単純なケースは、C コンパイラですらうまいこと防ぐことができるでしょう。 コードが大きくなり、様々な関数にポインタが渡されるようになると、やっかいなことになります。 いずれ C コンパイラは、十分なエスケープ解析ができなくなり、コードが健全である証明に失敗し、屈服することになるのです。 結果的に、C コンパイラはあなたのプログラムが正しいと仮定して、それを受け入れることを強制されます。

これは Rust では決して起こりません。全てが健全であるとコンパイラに証明するのはプログラマの責任なのです。

もちろん、参照が参照先のスコープから逃げ出していないことを検証することよりも 所有権に関する Rust の話はもっともっと複雑です。 ポインタが常に有効であることを証明するのは、もっともっと複雑だからです。 例えばこのコードを見てみましょう。

let mut data = vec![1, 2, 3];
// 内部データの参照を取る
let x = &data[0];

// しまった! `push` によって `data` の格納先が再割り当てされてしまった。
// ダングリングポインタだ! メモリ解放後の参照だ! うわーー!
// （このコードは Rust ではコンパイルエラーになります）
data.push(4);

println!("{}", x);

単純なスコープ解析では、このバグは防げません。 data のライフタイムは十分に長いからです。 問題は、その参照を保持している間に、参照先が変わってしまったことです。 Rust で参照を取ると、参照先とその所有者がフリーズされるのは、こういう理由なのです。

参照

このセクションでは、すべての Rust プログラムが満たさなくてはならないメモリモデルを ざっくりと見ていきます。 安全なコードは、借用チェッカによってこのモデルを満たしていることが静的に検証されます。 アンセーフなコードは、借用チェッカの裏をかくかもしれませんが、このモデルを満たします。 この基本的なモデルを満たしている限り、より多くのプログラムがコンパイルに通るように 借用チェッカを拡張することも可能です。

参照には 2 種類あります。

• 共有参照: &
• 可変参照: &mut

参照は次のルールに従います。

• 参照のライフタイムが、参照先のライフタイムより長くなることはできません。
• 可変参照は、別名を持つことができません。

これだけです。これがモデルの全てです。 もちろん、別名を持つとはどういうことかを定義するべきでしょう。 別名を定義するには、パスと生存という概念を定義しなくてはなりません。

これから説明するモデルは疑わしく、問題があるという点に、多くの人が同意しています。 直感的なモデルとして使うにはたぶん大丈夫ですが、望むような意味論を捉えることはできないでしょう。 ここではその点にこだわらず、のちの節で使うための概念を紹介することにします。 将来的にはこの構成は大きく変わるでしょう。TODO: 構成を変える。

パス

もし、Rust が扱うのが値だけ（ポインタはない）であれば、 すべての値はただ一つの変数か複合型に所有されることになります。 ここから所有権の木構造が自然に導かれます。 スタック自身が木のルートになり、変数が直接の子になります。 変数がフィールドを持つのであれば、それは変数の直接の子になるでしょう。

このように見ると、Rust におけるすべての値は、所有権を表す木構造のパスを持つことになります。 特に重要なのは、先祖と子孫です。x が y が所有しているとき、x は y の先祖で、 y は x の子孫です。この関係は内包的であることに注意してください。 x はそれ自身の先祖であり子孫です。

参照は、単純にパスの名前と定義できます。 参照を作成するということは、あるメモリアドレスに所有権の パスが存在することを宣言するということです。

悲惨なことに、スタックに存在しないデータはたくさんあり、この点も考慮しなくてはいけません。 グローバル変数やスレッドローカル変数は、単純にスタックの底に存在すると考えることができます。 （ただし、可変なグローバル変数に注意が必要です）。 ヒープにあるデータは別の問題を提起します。

もし、ヒープにある各データが、スタック上のただ一つのポインタに所有されているのだとすると、 そういうポインタを、ヒープ上の値を所有する構造体だと解釈すればよいだけです。 ヒープ上のデータを独占的に所有する型の例としては、Box, Vec, String, HashMap があります。

残念ながら、ヒープ上のデータは常に独占的に所有されているわけではありません。 例えば Rc によって、共有所有権という概念がでてきます。 値が共有所有されると、その値への一意なパスが存在しないことになります。 一意なパスが存在しない値によって、いろいろな制約が発生します。

一般に、一意ではないパスを参照できるのは、共有参照だけです。 しかし、相互排他を保証するメカニズムがあれば、一時的にその値（とそしてすべての子ども）への唯一のパスを確立し、 「唯一の真の所有者」を確立できるかもしれません。 もしこれが可能なら、その値を変更できるかもしれません。 とくに、可変参照を取ることができるようになります。

そのようなパスを確立するために、Rust で標準的に使われる継承可変性ではなく、 内部可変性がよく使われます。 内部可変性を持った型の例としては、Cell, RefCell, Mutex, RWLock があります。 これらの型は、実行時の制約を用いて、排他的アクセスを提供します。

この効果を使った興味深い例が Rc 自身です。もし Rc の参照カウントが 1 なら、 内部状態を変更したり、ムーブしたりしても安全です。 参照カウント自体も内部可変性を使っています。

変数や構造体のフィールドに内部可変性があることを型システムに正しく伝えるには、 UnsafeCell を使います。 UnsafeCell 自身は、その値に対して内部可変の操作を安全にはしません。 正しく相互排他していることを、あなた自身が保証しなくてはなりません。

生存性

生存性 (liveness) は、この章の次の節で詳しく説明する ライフタイム (lifetime) とは違うことに注意してください。

大雑把に言うと、参照を参照外しできるとき、 その参照は、プログラム中のある時点で 生存している といえます。 共有参照は、文字通り到達不可能な場合（たとえば、解放済みメモリやリークしてるメモリに 存在している場合）を除いて、常に生存しています。 可変参照には、又貸しというプロセスがあるので、到達できても生存していないことがあります。

可変参照は、その子孫を他の共有参照または可変参照に又貸しすることができます。 又貸しした参照は、派生したすべての又貸しの有効期限が切れると、再び生存することになります。 例えば、可変参照は、その参照先の一つのフィールドを指す参照を又貸しすることができます。

#![allow(unused)]
fn main() {
let x = &mut (1, 2);
{
    // x のフィールドを又借りする
    let y = &mut x.0;
    // この時点で y は生存しているが、x は生存していない
    *y = 3;
}
// y がスコープ外に出たので、x が再び生存中になる
*x = (5, 7);
}

複数の可変参照に又貸しすることも可能ですが、その複数の参照は互いに素でなくてはいけません。 つまり、どの参照も他の参照の先祖であってはいけないということです。 Rust は、構造体のフィールドが互いに素であることを静的に証明できるので、 フィールドの又貸しが可能です。

#![allow(unused)]
fn main() {
let x = &mut (1, 2);
{
    // x を 2 つの互いに素なフィールドに又貸しする
    let y = &mut x.0;
    let z = &mut x.1;

    // y と z は生存しているが、x は生存していない
    *y = 3;
    *z = 4;
}
// y と z がスコープ外に出たので、x がふたたび生存中になる
*x = (5, 7);
}

ただし、多くの場合 Rust は十分に賢くないので、複数の借り手が互いに素であることを証明できません。 これはそのような又貸しが禁じられているという意味ではなく、 単に Rust が期待するほど賢くないというだけです。

話を単純にするために、変数を参照型の一種、所有中参照、と仮定してみましょう。 所有中参照は、可変参照とほとんど同じ意味を持ちます。 可変参照または共有参照に又貸しでき、それによって生存中ではなくなります。 生存中の所有中参照は、値を解放（ムーブアウト）できるという特殊な性質があります （とはいえ、可変参照は値をスワップアウトできますが）。 この能力は、生存中の 所有中参照のみに与えられています。 そうでなければ、早すぎるタイミングでその他の参照を無効にすることになります。

不適切な値の変更を lint が検出するので、mut とマークされた変数だけが変更可能なように借用されます。

Box がまさに所有中参照のように振る舞うということを覚えておくと良いでしょう。 Box は値を解放することができ、変数が解放された時と同様に Rust はそのパスについて推論するための 十分な情報を持っています。

別名付け

生存性とパスを定義したので、ようやく別名を適切に定義できます。

可変参照は、その先祖か子孫に他の参照が存在している時、別名を持つといいます。

（二つの生存中の参照が互いの別名になっている、と言うこともできます。 意味上の違いは特にありませんが、プログラムの構造の健全性を検証する時には、 この考え方の方がわかりやすいでしょう。）

これだけです。すげーわかりやすいですよね? この定義に必要なすべての用語を定義するのに 2 ページ必要に なりましたが・・・。すごく、分かりやすい。でしょ?

実際には、もう少し複雑です。参照に加えて Rust には生ポインタもあります。 *const T と *mut T のことです。 生ポインタには、継承可能な所有権も別名という概念もありません。 そのため、Rust は生ポインタを追跡する努力を一切しませんし、生ポインタは極めて危険です。

生ポインタが別名という意味をどの程度持っているのか、というのはまだ答えの出てない問題です。 しかし、この節で出てきた定義が健全であるためには、生ポインタを使うとある種の生存パスが わからなくなるということ重要です。

ライフタイム

Rust は今まで説明してきたルールをライフタイムを使って強制します。 ライフタイムとは、要するにプログラム中のスコープの名前です。 参照と、参照を含むものとは、有効なスコープを示すライフタイムでタグ付けられています。

通常、関数本体では、関係するライフタイムの名前を明示することは求められません。 一般に、ローカルコンテキストにおいてライフタイムを気にする必要はまずないからです。 Rust はすべての情報を持っていて、可能な限りすべてを最適にできます。 省略可能な無名スコープや一時変数は、コードがきちんと動くように自動的に導入されます。

しかし関数の境界を超えると、ライフタイムについて気にしなくてはいけなくなります。 ライフタイムは、'a や 'static などアポストロフィーつきの名前を持ちます。 ライフタイムの世界に足を踏み入れるために、 スコープにライフタイムのラベルをつけられるとして、この章の最初のサンプルコードを 「脱糖 (desugar)」してみましょう。

もともとのサンプルコードは、スコープとライフタイムについて、 果糖がたくさん含まれたコーンシロップのように強烈に甘い書き方でした。 （訳注：ライフタイムを省略できることは syntax sugar で、元のコードは大量の syntax sugar を使っているので、「甘い」と言っている） なぜなら、すべてを明示的に書くのは極めて煩わしいからです。 Rust のコードは、積極的な推論と「明らかな」ことの省略とを当てにしています。

let 文が、スコープを暗黙的に導入するというのは、興味深いシンタックスシュガーでしょう。 ほとんどの場合、これは問題になりません。 しかし、複数の変数がお互いを参照している場合は問題になります。 簡単な例として、この単純な Rust コードを脱糖してみましょう。

#![allow(unused)]
fn main() {
let x = 0;
let y = &x;
let z = &y;
}

借用チェッカは、ライフタイムの長さを最小にしようとするので、 これは次のように脱糖されるでしょう。

// `'a: {` と `&'b x` は正当な構文ではないことに注意してください!
'a: {
    let x: i32 = 0;
    'b: {
        // ここで使用されるライフタイムは 'b です。なぜなら 'b で十分だからです。
        let y: &'b i32 = &'b x;
        'c: {
            // 'c も同様
            let z: &'c &'b i32 = &'c y;
        }
    }
}

おっと。こんなふうに書かなければいけないとしたら・・・これはひどいですね。 ここでしばらく時間をとって、簡単な構文を許してくれる Rust に感謝を意を表しましょう。

参照を外のスコープに返す場合は、Rust はより大きいライフタイムを推論することになります。

#![allow(unused)]
fn main() {
let x = 0;
let z;
let y = &x;
z = y;
}

'a: {
    let x: i32 = 0;
    'b: {
        let z: &'b i32;
        'c: {
            // ここでは 'b を使う必要があります。なぜならこの参照は
            // スコープ `b に渡されるからです。
            let y: &'b i32 = &'b x;
            z = y;
        }
    }
}

例：参照先より長く生きる参照

それでは、以前に出した例を見てみましょう。

fn as_str(data: &u32) -> &str {
    let s = format!("{}", data);
    &s
}

は次のように脱糖されます。

fn as_str<'a>(data: &'a u32) -> &'a str {
    'b: {
        let s = format!("{}", data);
        return &'a s;
    }
}

as_str のシグネチャは、あるライフタイムを持つ u32 への参照をとり、 その参照と同じ長さだけ生きる str への参照を生成することを約束します。 このシグネチャが問題になるかもしれないと、すでに話しました。 このシグネチャは、引数の u32 を指す参照が生成されたスコープか、もしくはそれより以前のスコープで、str を探すことを意味します。これはなかなか難しい注文です。

それから文字列 s を計算し、その参照を返します。 この関数は、返される参照が 'a より長生きすることを約束しているので、この参照のライフタイムとして 'a を使うことを推論します。 残念なことに、s はスコープ 'b の中で定義されているので、 この推論が妥当になるためには、'b が 'a を含んでいなくてはなりません。 ところがこれは明らかに成立しません。'a はこの関数呼び出しそものを含んでいるからです。 結局、この関数は参照先より長生きする参照を生成してしまいました。 そしてこれは文字通り、参照がやってはいけないことの一番目でした。 コンパイラは正当に怒りだします。

よりわかりやすくするために、この例を拡張してみます。

fn as_str<'a>(data: &'a u32) -> &'a str {
    'b: {
        let s = format!("{}", data);
        return &'a s
    }
}

fn main() {
    'c: {
        let x: u32 = 0;
        'd: {
            // この x の借用は、x が有効な全期間より短くて良いので、無名スコープが導入されます。
            // as_str は、この呼び出しより前のどこかにある str を見つけなければいけませんが、
            // そのような str が無いのはあきらかです。
            println!("{}", as_str::<'d>(&'d x));
        }
    }
}

ちくしょう！

この関数を正しく書くと、当然次のようになります。

#![allow(unused)]
fn main() {
fn to_string(data: &u32) -> String {
    format!("{}", data)
}
}

この関数が所有する値を関数内で生成し、それを返さなくてはいけません！ str が &'a u32 のフィールドだとしたら、&'a str を返せるのですが、 もちろんそれはありえません。

（そういえば、単に文字列リテラルを返すこともできたかもしれません。 文字列リテラルはグローバルで、スタックの底に存在すると解釈できますから。 ただこれはこの関数の実装をほんの少しだけ制限してしまいますね。）

例：可変参照の別名付け

もう一つの例はどうでしょう。

let mut data = vec![1, 2, 3];
let x = &data[0];
data.push(4);
println!("{}", x);

'a: {
    let mut data: Vec<i32> = vec![1, 2, 3];
    'b: {
        // スコープ 'b は次の貸し出しに必要なだけ大きくなります。
        // （`println!` を含むまで大きくなります）
        let x: &'b i32 = Index::index::<'b>(&'b data, 0);
        'c: {
            // &mut は長生きする必要が無いので、一時的なスコープ 'c が作られます。
            Vec::push(&'c mut data, 4);
        }
        println!("{}", x);
    }
}

これは、すこし分かりにくいですが面白い問題です。 私たちは、Rust が次のような理由で、このプログラムを拒否するだろうと思っています。 つまり、push するために data への可変参照を取ろうとするとき、 data の子孫への共有参照 x が生存中です。 これは可変参照の別名となり、参照の二番目のルールに違反します。

ところが、Rust がこのプログラムを悪いと推論するやり方は全く違うのです。 Rust は、x が data の部分パスへの参照であることは理解しません。 Rust は Vec のことなど何も知らないのです。 Rust に見えているのは、x は println! のためにスコープ 'b の中で生存しなくてはならないことです。 さらに、Index::index のシグネチャは、data を参照する参照が スコープ 'b の中で生存することを要求します。 push を呼び出すときに、&'c mut data を取ろうとすることを Rust は理解します。 Rust はスコープ 'c が スコープ 'b に含まれていることを知っているので、 このプログラムを拒否します。 なぜなら、&'b data はまだ生きているからです。

ここでは、ライフタイムをチェックするシステムは、私たちが維持したい参照の意味論に比べて とても荒いことを見てきました。 ほとんどの場合、これで全く大丈夫です。 私たちが書いたコードをコンパイラに説明するために丸一日費やさなくてもいいからです。 しかし、ライフタイムのチェックがとてもバカなために、Rust の真の意味論的には全く正しいプログラムでも拒否されることがあるのです。

ライフタイムシステムの限界

次のコードを見てみましょう。

struct Foo;

impl Foo {
    fn mutate_and_share(&mut self) -> &Self { &*self }
    fn share(&self) {}
}

fn main() {
    let mut foo = Foo;
    let loan = foo.mutate_and_share();
    foo.share();
}

このコードはコンパイルを通ると思うかもしれません。 mutate_and_share は、foo を一時的に変更可能に借用しますが、 共有参照を返します。 そうすると、foo は変更可能には借用されていないので、 foo.share() は成功すると思うでしょう。

ところが、このコードをコンパイルすると・・・。

<anon>:11:5: 11:8 error: cannot borrow `foo` as immutable because it is also borrowed as mutable
(エラー: `foo`は可変で借用されているので、不変で借用できません)
<anon>:11     foo.share();
              ^~~
<anon>:10:16: 10:19 note: previous borrow of `foo` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `foo` until the borrow ends
(注釈: 以前の`foo`の借用はここで起きています。可変での借用は、その借用が終わるまで、その後のムーブや、借用、`foo`の変更を防ぎます)
<anon>:10     let loan = foo.mutate_and_share();
                         ^~~
<anon>:12:2: 12:2 note: previous borrow ends here
(注釈: 以前の借用はここで終了しています)
<anon>:8 fn main() {
<anon>:9     let mut foo = Foo;
<anon>:10     let loan = foo.mutate_and_share();
<anon>:11     foo.share();
<anon>:12 }
          ^

何が起こったのでしょう? 前の節の 2 つ目のサンプルと全く同じ推論を行ったのです。 このコードを脱糖すると、次のようになります。

struct Foo;

impl Foo {
    fn mutate_and_share<'a>(&'a mut self) -> &'a Self { &'a *self }
    fn share<'a>(&'a self) {}
}

fn main() {
	'b: {
    	let mut foo: Foo = Foo;
    	'c: {
    		let loan: &'c Foo = Foo::mutate_and_share::<'c>(&'c mut foo);
    		'd: {
    			Foo::share::<'d>(&'d foo);
    		}
    	}
    }
}

loan のライフタイムと mutate_and_share のシグネチャとのため、 &mut foo のライフタイムは 'c に延長されなくてはなりません。 そして、share を呼ぼうとするとき、&'c mut foo の別名を取ろうとすると認識され、大失敗に終わるのです。

このプログラムは、私たちにとって重要な参照の意味的には全く正しいのですが、 ライフタイムシステムはこのプログラムを処理するには粗すぎるのです。

TODO: その他のよくある問題は? 主に SEME 領域とか?

ライフタイムの省略

よくあるパターンをより易しく書けるように、Rust では関数シグネチャのライフタイムを省略できます。

ライフタイムポジション とは、型の定義においてライフタイムを書ける場所のことです。

&'a T
&'a mut T
T<'a>

ライフタイムポジションは、「入力」または「出力」という形で現れます。

• fn 定義では、入力とは仮引数の型のことで、出力とは結果の型のことです。 fn foo(s: *str) -> (&str, &str) では、入力ポジションのライフタイムが一つ省略され、 出力ポジションのライフタイムが二つ省略されています。 fn メソッド定義の入力ポジションには、 メソッドの impl ヘッダに現れるライフタイムは含まれません。 （デフォルトメソッドの場合の trait ヘッダに現れるライフタイムも含まれません。）

• 将来のバージョンでは、impl ヘッダのライフタイムの省略も同様に可能になるでしょう。

省略のルールは次の通りです。

• 入力ポジションの省略されたライフタイムは、それぞれ別のライフタイムパラメータになります。

• 入力ポジションのライフタイム（省略されているかどうかに関わらず）が一つしか無い場合、 省略された出力ライフタイム全てにそのライフタイムが割り当てられます。

• 入力ポジションに複数のライフタイムがあって、そのうちの一つが &self または &mut self の場合、 省略された出力ライフタイム全てに self のライフタイムが割り当てられます。

• それ以外の場合は、出力のライフタイムを省略するとエラーになります。

例：

fn print(s: &str);                                      // 省略した場合
fn print<'a>(s: &'a str);                               // 展開した場合

fn debug(lvl: uint, s: &str);                           // 省略した場合
fn debug<'a>(lvl: uint, s: &'a str);                    // 展開した場合

fn substr(s: &str, until: uint) -> &str;                // 省略した場合
fn substr<'a>(s: &'a str, until: uint) -> &'a str;      // 展開した場合

fn get_str() -> &str;                                   // エラー

fn frob(s: &str, t: &str) -> &str;                      // エラー

fn get_mut(&mut self) -> &mut T;                        // 省略した場合
fn get_mut<'a>(&'a mut self) -> &'a mut T;              // 展開した場合

fn args<T: ToCStr>(&mut self, args: &[T]) -> &mut Command                  // 省略した場合
fn args<'a, 'b, T: ToCStr>(&'a mut self, args: &'b [T]) -> &'a mut Command // 展開した場合

fn new(buf: &mut [u8]) -> BufWriter;                    // 省略した場合
fn new<'a>(buf: &'a mut [u8]) -> BufWriter<'a>          // 展開した場合

無制限のライフタイム

アンセーフなコードはときに、参照やライフタイムを何も無いところから生み出したりします。 そのようなライフタイムは、無制限 なライフタイムとして世界に登場します。 最もよくあるのは、生ポインタの参照外しをし、無制限のライフタイムを持つ参照を作り出すというケースです。 このライフタイムは、そのコンテキストが必要とするだけ大きくなります。そしてこれは 'static よりも強力なしくみです。 &'static &'a T は型チェックをパスしませんが、無制限のライフタイムを使うと必要に応じて &'a &'a T となるからです。 しかし、ほとんどの意図と目的においては、無制限のライフタイムを 'static と解釈できます。

参照が 'static であることはまずありえないので、これはおそらく間違っていると言えるでしょう。 おもに transmute と transmute_copy とがこの状況を作り出します。 できるだけ速く、とくに関数の境界では、無制限のライフタイムに制限をつけるように気をつけて下さい。

関数の入力から導出されない出力のライフタイムは無制限となります。例えば、

fn get_str<'a>() -> &'a str;

このコードは無制限のライフタイムを持った &str を生成します。 無制限のライフタイムを避ける最も簡単な方法は、関数境界でライフタイムを省略することです。 出力ライフタイムが省略された場合、入力ライフタイムで制限されなくてはいけません。 もちろん、間違ったライフタイムで制限されるかもしれませんが、たいていの場合は、メモリ安全性が侵されるのではなく、コンパイルエラーにつながります。

関数内部でライフタイムを制限することは、エラーを生みやすくなります。 ライフタイムを制限する安全で簡単な方法は、制限つきライフタイムの関数から返される値を使うことです。 しかし、これができない場合は、その参照を特定のライフタイムがついた場所に置くと良いでしょう。 残念ながら、関数内のすべてのライフタイムに名前をつけるのは不可能です。

高階トレイト境界

Rust の Fn トレイトはちょっとした魔法です。例えば、次のように書くことができます。

struct Closure<F> {
    data: (u8, u16),
    func: F,
}

impl<F> Closure<F>
    where F: Fn(&(u8, u16)) -> &u8,
{
    fn call(&self) -> &u8 {
        (self.func)(&self.data)
    }
}

fn do_it(data: &(u8, u16)) -> &u8 { &data.0 }

fn main() {
    let clo = Closure { data: (0, 1), func: do_it };
    println!("{}", clo.call());
}

ライフタイムの節と同じように単純に脱糖しようとすると、問題が起こります。

struct Closure<F> {
    data: (u8, u16),
    func: F,
}

impl<F> Closure<F>
    // where F: Fn(&'??? (u8, u16)) -> &'??? u8,
{
    fn call<'a>(&'a self) -> &'a u8 {
        (self.func)(&self.data)
    }
}

fn do_it<'b>(data: &'b (u8, u16)) -> &'b u8 { &'b data.0 }

fn main() {
    'x: {
        let clo = Closure { data: (0, 1), func: do_it };
        println!("{}", clo.call());
    }
}

F のトレイト境界は、一体どうすれば表現できるのでしょう? なんらかのライフタイムを提供する必要がありますが、問題のライフタイムは call 関数が呼ばれるまで名前が無いのです。さらに、ライフタイムは固定されていません。 &self にどんなライフタイムが割り当てられても、call は動作します。

この問題は、高階トレイト境界（HRTB: Higher-Rank Trait Bounds）という魔法で解決できます。 HRTB を使うとつぎのように脱糖できます。

where for<'a> F: Fn(&'a (u8, u16)) -> &'a u8,

（Fn(a, b, c) -> d 自体が、まだ仕様が安定していない本当の Fn トレイトの糖衣構文です。）

for<'a> は、「'a に何を選んだとしても」という意味で、つまり F が満たさなくてはならないトレイト境界の無限リストを生成します。強烈でしょう? Fn トレイトを除けば、HRTB が使われる場所はほとんどありません。Fn トレイトにおいても、ほとんどの場合は魔法の糖衣構文が良いされています。

Subtyping and Variance

Although Rust doesn't have any notion of structural inheritance, it does include subtyping. In Rust, subtyping derives entirely from lifetimes. Since lifetimes are scopes, we can partially order them based on the contains (outlives) relationship. We can even express this as a generic bound.

Subtyping on lifetimes is in terms of that relationship: if 'a: 'b ("a contains b" or "a outlives b"), then 'a is a subtype of 'b. This is a large source of confusion, because it seems intuitively backwards to many: the bigger scope is a subtype of the smaller scope.

This does in fact make sense, though. The intuitive reason for this is that if you expect an &'a u8, then it's totally fine for me to hand you an &'static u8, in the same way that if you expect an Animal in Java, it's totally fine for me to hand you a Cat. Cats are just Animals and more, just as 'static is just 'a and more.

(Note, the subtyping relationship and typed-ness of lifetimes is a fairly arbitrary construct that some disagree with. However it simplifies our analysis to treat lifetimes and types uniformly.)

Higher-ranked lifetimes are also subtypes of every concrete lifetime. This is because taking an arbitrary lifetime is strictly more general than taking a specific one.

Variance

Variance is where things get a bit complicated.

Variance is a property that type constructors have with respect to their arguments. A type constructor in Rust is a generic type with unbound arguments. For instance Vec is a type constructor that takes a T and returns a Vec<T>. & and &mut are type constructors that take two inputs: a lifetime, and a type to point to.

A type constructor's variance is how the subtyping of its inputs affects the subtyping of its outputs. There are two kinds of variance in Rust:

• F is variant over T if T being a subtype of U implies F<T> is a subtype of F<U> (subtyping "passes through")
• F is invariant over T otherwise (no subtyping relation can be derived)

(For those of you who are familiar with variance from other languages, what we refer to as "just" variance is in fact covariance. Rust has contravariance for functions. The future of contravariance is uncertain and it may be scrapped. For now, fn(T) is contravariant in T, which is used in matching methods in trait implementations to the trait definition. Traits don't have inferred variance, so Fn(T) is invariant in T).

Some important variances:

• &'a T is variant over 'a and T (as is *const T by metaphor)
• &'a mut T is variant over 'a but invariant over T
• Fn(T) -> U is invariant over T, but variant over U
• Box, Vec, and all other collections are variant over the types of their contents
• UnsafeCell<T>, Cell<T>, RefCell<T>, Mutex<T> and all other interior mutability types are invariant over T (as is *mut T by metaphor)

To understand why these variances are correct and desirable, we will consider several examples.

We have already covered why &'a T should be variant over 'a when introducing subtyping: it's desirable to be able to pass longer-lived things where shorter-lived things are needed.

Similar reasoning applies to why it should be variant over T. It is reasonable to be able to pass &&'static str where an &&'a str is expected. The additional level of indirection does not change the desire to be able to pass longer lived things where shorted lived things are expected.

However this logic doesn't apply to &mut. To see why &mut should be invariant over T, consider the following code:

fn overwrite<T: Copy>(input: &mut T, new: &mut T) {
    *input = *new;
}

fn main() {
    let mut forever_str: &'static str = "hello";
    {
        let string = String::from("world");
        overwrite(&mut forever_str, &mut &*string);
    }
    // Oops, printing free'd memory
    println!("{}", forever_str);
}

The signature of overwrite is clearly valid: it takes mutable references to two values of the same type, and overwrites one with the other. If &mut T was variant over T, then &mut &'static str would be a subtype of &mut &'a str, since &'static str is a subtype of &'a str. Therefore the lifetime of forever_str would successfully be "shrunk" down to the shorter lifetime of string, and overwrite would be called successfully. string would subsequently be dropped, and forever_str would point to freed memory when we print it! Therefore &mut should be invariant.

This is the general theme of variance vs invariance: if variance would allow you to store a short-lived value into a longer-lived slot, then you must be invariant.

However it is sound for &'a mut T to be variant over 'a. The key difference between 'a and T is that 'a is a property of the reference itself, while T is something the reference is borrowing. If you change T's type, then the source still remembers the original type. However if you change the lifetime's type, no one but the reference knows this information, so it's fine. Put another way: &'a mut T owns 'a, but only borrows T.

Box and Vec are interesting cases because they're variant, but you can definitely store values in them! This is where Rust gets really clever: it's fine for them to be variant because you can only store values in them via a mutable reference! The mutable reference makes the whole type invariant, and therefore prevents you from smuggling a short-lived type into them.

Being variant allows Box and Vec to be weakened when shared immutably. So you can pass a &Box<&'static str> where a &Box<&'a str> is expected.

However what should happen when passing by-value is less obvious. It turns out that, yes, you can use subtyping when passing by-value. That is, this works:

#![allow(unused)]
fn main() {
fn get_box<'a>(str: &'a str) -> Box<&'a str> {
    // string literals are `&'static str`s
    Box::new("hello")
}
}

Weakening when you pass by-value is fine because there's no one else who "remembers" the old lifetime in the Box. The reason a variant &mut was trouble was because there's always someone else who remembers the original subtype: the actual owner.

The invariance of the cell types can be seen as follows: & is like an &mut for a cell, because you can still store values in them through an &. Therefore cells must be invariant to avoid lifetime smuggling.

Fn is the most subtle case because it has mixed variance. To see why Fn(T) -> U should be invariant over T, consider the following function signature:

// 'a is derived from some parent scope
fn foo(&'a str) -> usize;

This signature claims that it can handle any &str that lives at least as long as 'a. Now if this signature was variant over &'a str, that would mean

fn foo(&'static str) -> usize;

could be provided in its place, as it would be a subtype. However this function has a stronger requirement: it says that it can only handle &'static strs, and nothing else. Giving &'a strs to it would be unsound, as it's free to assume that what it's given lives forever. Therefore functions are not variant over their arguments.

To see why Fn(T) -> U should be variant over U, consider the following function signature:

// 'a is derived from some parent scope
fn foo(usize) -> &'a str;

This signature claims that it will return something that outlives 'a. It is therefore completely reasonable to provide

fn foo(usize) -> &'static str;

in its place. Therefore functions are variant over their return type.

*const has the exact same semantics as &, so variance follows. *mut on the other hand can dereference to an &mut whether shared or not, so it is marked as invariant just like cells.

This is all well and good for the types the standard library provides, but how is variance determined for type that you define? A struct, informally speaking, inherits the variance of its fields. If a struct Foo has a generic argument A that is used in a field a, then Foo's variance over A is exactly a's variance. However this is complicated if A is used in multiple fields.

• If all uses of A are variant, then Foo is variant over A
• Otherwise, Foo is invariant over A

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

struct Foo<'a, 'b, A: 'a, B: 'b, C, D, E, F, G, H> {
    a: &'a A,     // variant over 'a and A
    b: &'b mut B, // variant over 'b and invariant over B
    c: *const C,  // variant over C
    d: *mut D,    // invariant over D
    e: Vec<E>,    // variant over E
    f: Cell<F>,   // invariant over F
    g: G,         // variant over G
    h1: H,        // would also be variant over H except...
    h2: Cell<H>,  // invariant over H, because invariance wins
}
}

Drop Check

We have seen how lifetimes provide us some fairly simple rules for ensuring that we never read dangling references. However up to this point we have only ever interacted with the outlives relationship in an inclusive manner. That is, when we talked about 'a: 'b, it was ok for 'a to live exactly as long as 'b. At first glance, this seems to be a meaningless distinction. Nothing ever gets dropped at the same time as another, right? This is why we used the following desugaring of let statements:

let x;
let y;

{
    let x;
    {
        let y;
    }
}

Each creates its own scope, clearly establishing that one drops before the other. However, what if we do the following?

let (x, y) = (vec![], vec![]);

Does either value strictly outlive the other? The answer is in fact no, neither value strictly outlives the other. Of course, one of x or y will be dropped before the other, but the actual order is not specified. Tuples aren't special in this regard; composite structures just don't guarantee their destruction order as of Rust 1.0.

We could specify this for the fields of built-in composites like tuples and structs. However, what about something like Vec? Vec has to manually drop its elements via pure-library code. In general, anything that implements Drop has a chance to fiddle with its innards during its final death knell. Therefore the compiler can't sufficiently reason about the actual destruction order of the contents of any type that implements Drop.

So why do we care? We care because if the type system isn't careful, it could accidentally make dangling pointers. Consider the following simple program:

struct Inspector<'a>(&'a u8);

fn main() {
    let (inspector, days);
    days = Box::new(1);
    inspector = Inspector(&days);
}

This program is totally sound and compiles today. The fact that days does not strictly outlive inspector doesn't matter. As long as the inspector is alive, so is days.

However if we add a destructor, the program will no longer compile!

struct Inspector<'a>(&'a u8);

impl<'a> Drop for Inspector<'a> {
    fn drop(&mut self) {
        println!("I was only {} days from retirement!", self.0);
    }
}

fn main() {
    let (inspector, days);
    days = Box::new(1);
    inspector = Inspector(&days);
    // Let's say `days` happens to get dropped first.
    // Then when Inspector is dropped, it will try to read free'd memory!
}

<anon>:12:28: 12:32 error: `days` does not live long enough
<anon>:12     inspector = Inspector(&days);
                                     ^~~~
<anon>:9:11: 15:2 note: reference must be valid for the block at 9:10...
<anon>:9 fn main() {
<anon>:10     let (inspector, days);
<anon>:11     days = Box::new(1);
<anon>:12     inspector = Inspector(&days);
<anon>:13     // Let's say `days` happens to get dropped first.
<anon>:14     // Then when Inspector is dropped, it will try to read free'd memory!
          ...
<anon>:10:27: 15:2 note: ...but borrowed value is only valid for the block suffix following statement 0 at 10:26
<anon>:10     let (inspector, days);
<anon>:11     days = Box::new(1);
<anon>:12     inspector = Inspector(&days);
<anon>:13     // Let's say `days` happens to get dropped first.
<anon>:14     // Then when Inspector is dropped, it will try to read free'd memory!
<anon>:15 }

Implementing Drop lets the Inspector execute some arbitrary code during its death. This means it can potentially observe that types that are supposed to live as long as it does actually were destroyed first.

Interestingly, only generic types need to worry about this. If they aren't generic, then the only lifetimes they can harbor are 'static, which will truly live forever. This is why this problem is referred to as sound generic drop. Sound generic drop is enforced by the drop checker. As of this writing, some of the finer details of how the drop checker validates types is totally up in the air. However The Big Rule is the subtlety that we have focused on this whole section:

For a generic type to soundly implement drop, its generics arguments must strictly outlive it.

Obeying this rule is (usually) necessary to satisfy the borrow checker; obeying it is sufficient but not necessary to be sound. That is, if your type obeys this rule then it's definitely sound to drop.

The reason that it is not always necessary to satisfy the above rule is that some Drop implementations will not access borrowed data even though their type gives them the capability for such access.

For example, this variant of the above Inspector example will never access borrowed data:

struct Inspector<'a>(&'a u8, &'static str);

impl<'a> Drop for Inspector<'a> {
    fn drop(&mut self) {
        println!("Inspector(_, {}) knows when *not* to inspect.", self.1);
    }
}

fn main() {
    let (inspector, days);
    days = Box::new(1);
    inspector = Inspector(&days, "gadget");
    // Let's say `days` happens to get dropped first.
    // Even when Inspector is dropped, its destructor will not access the
    // borrowed `days`.
}

Likewise, this variant will also never access borrowed data:

use std::fmt;

struct Inspector<T: fmt::Display>(T, &'static str);

impl<T: fmt::Display> Drop for Inspector<T> {
    fn drop(&mut self) {
        println!("Inspector(_, {}) knows when *not* to inspect.", self.1);
    }
}

fn main() {
    let (inspector, days): (Inspector<&u8>, Box<u8>);
    days = Box::new(1);
    inspector = Inspector(&days, "gadget");
    // Let's say `days` happens to get dropped first.
    // Even when Inspector is dropped, its destructor will not access the
    // borrowed `days`.
}

However, both of the above variants are rejected by the borrow checker during the analysis of fn main, saying that days does not live long enough.

The reason is that the borrow checking analysis of main does not know about the internals of each Inspector's Drop implementation. As far as the borrow checker knows while it is analyzing main, the body of an inspector's destructor might access that borrowed data.

Therefore, the drop checker forces all borrowed data in a value to strictly outlive that value.

An Escape Hatch

The precise rules that govern drop checking may be less restrictive in the future.

The current analysis is deliberately conservative and trivial; it forces all borrowed data in a value to outlive that value, which is certainly sound.

Future versions of the language may make the analysis more precise, to reduce the number of cases where sound code is rejected as unsafe. This would help address cases such as the two Inspectors above that know not to inspect during destruction.

In the meantime, there is an unstable attribute that one can use to assert (unsafely) that a generic type's destructor is guaranteed to not access any expired data, even if its type gives it the capability to do so.

That attribute is called may_dangle and was introduced in [RFC 1327] (https://github.com/rust-lang/rfcs/blob/master/text/1327-dropck-param-eyepatch.md). To deploy it on the Inspector example from above, we would write:

struct Inspector<'a>(&'a u8, &'static str);

unsafe impl<#[may_dangle] 'a> Drop for Inspector<'a> {
    fn drop(&mut self) {
        println!("Inspector(_, {}) knows when *not* to inspect.", self.1);
    }
}

Use of this attribute requires the Drop impl to be marked unsafe because the compiler is not checking the implicit assertion that no potentially expired data (e.g. self.0 above) is accessed.

The attribute can be applied to any number of lifetime and type parameters. In the following example, we assert that we access no data behind a reference of lifetime 'b and that the only uses of T will be moves or drops, but omit the attribute from 'a and U, because we do access data with that lifetime and that type:

use std::fmt::Display;

struct Inspector<'a, 'b, T, U: Display>(&'a u8, &'b u8, T, U);

unsafe impl<'a, #[may_dangle] 'b, #[may_dangle] T, U: Display> Drop for Inspector<'a, 'b, T, U> {
    fn drop(&mut self) {
        println!("Inspector({}, _, _, {})", self.0, self.3);
    }
}

It is sometimes obvious that no such access can occur, like the case above. However, when dealing with a generic type parameter, such access can occur indirectly. Examples of such indirect access are:

• invoking a callback,
• via a trait method call.

(Future changes to the language, such as impl specialization, may add other avenues for such indirect access.)

Here is an example of invoking a callback:

struct Inspector<T>(T, &'static str, Box<for <'r> fn(&'r T) -> String>);

impl<T> Drop for Inspector<T> {
    fn drop(&mut self) {
        // The `self.2` call could access a borrow e.g. if `T` is `&'a _`.
        println!("Inspector({}, {}) unwittingly inspects expired data.",
                 (self.2)(&self.0), self.1);
    }
}

Here is an example of a trait method call:

use std::fmt;

struct Inspector<T: fmt::Display>(T, &'static str);

impl<T: fmt::Display> Drop for Inspector<T> {
    fn drop(&mut self) {
        // There is a hidden call to `<T as Display>::fmt` below, which
        // could access a borrow e.g. if `T` is `&'a _`
        println!("Inspector({}, {}) unwittingly inspects expired data.",
                 self.0, self.1);
    }
}

And of course, all of these accesses could be further hidden within some other method invoked by the destructor, rather than being written directly within it.

In all of the above cases where the &'a u8 is accessed in the destructor, adding the #[may_dangle] attribute makes the type vulnerable to misuse that the borrower checker will not catch, inviting havoc. It is better to avoid adding the attribute.

Is that all about drop checker?

It turns out that when writing unsafe code, we generally don't need to worry at all about doing the right thing for the drop checker. However there is one special case that you need to worry about, which we will look at in the next section.

PhantomData

When working with unsafe code, we can often end up in a situation where types or lifetimes are logically associated with a struct, but not actually part of a field. This most commonly occurs with lifetimes. For instance, the Iter for &'a [T] is (approximately) defined as follows:

struct Iter<'a, T: 'a> {
    ptr: *const T,
    end: *const T,
}

However because 'a is unused within the struct's body, it's unbounded. Because of the troubles this has historically caused, unbounded lifetimes and types are forbidden in struct definitions. Therefore we must somehow refer to these types in the body. Correctly doing this is necessary to have correct variance and drop checking.

We do this using PhantomData, which is a special marker type. PhantomData consumes no space, but simulates a field of the given type for the purpose of static analysis. This was deemed to be less error-prone than explicitly telling the type-system the kind of variance that you want, while also providing other useful such as the information needed by drop check.

Iter logically contains a bunch of &'a Ts, so this is exactly what we tell the PhantomData to simulate:

use std::marker;

struct Iter<'a, T: 'a> {
    ptr: *const T,
    end: *const T,
    _marker: marker::PhantomData<&'a T>,
}

and that's it. The lifetime will be bounded, and your iterator will be variant over 'a and T. Everything Just Works.

Another important example is Vec, which is (approximately) defined as follows:

struct Vec<T> {
    data: *const T, // *const for variance!
    len: usize,
    cap: usize,
}

Unlike the previous example, it appears that everything is exactly as we want. Every generic argument to Vec shows up in at least one field. Good to go!

Nope.

The drop checker will generously determine that Vec<T> does not own any values of type T. This will in turn make it conclude that it doesn't need to worry about Vec dropping any T's in its destructor for determining drop check soundness. This will in turn allow people to create unsoundness using Vec's destructor.

In order to tell dropck that we do own values of type T, and therefore may drop some T's when we drop, we must add an extra PhantomData saying exactly that:

use std::marker;

struct Vec<T> {
    data: *const T, // *const for covariance!
    len: usize,
    cap: usize,
    _marker: marker::PhantomData<T>,
}

Raw pointers that own an allocation is such a pervasive pattern that the standard library made a utility for itself called Unique<T> which:

• wraps a *const T for variance
• includes a PhantomData<T>
• auto-derives Send/Sync as if T was contained
• marks the pointer as NonZero for the null-pointer optimization

借用の分割

可変参照の相互排他性は、複合構造体を使用している時に非常に制限を課してくる存在となります。 借用チェッカはいくつか基本事項を理解していますが、本当に簡単にすっ転びます。 借用チェッカは構造体について十分理解しているため、構造体の別々のフィールドを同時に借用することは可能です。 ですから、このコードは今日動作します。

#![allow(unused)]
fn main() {
struct Foo {
    a: i32,
    b: i32,
    c: i32,
}

let mut x = Foo {a: 0, b: 0, c: 0};
let a = &mut x.a;
let b = &mut x.b;
let c = &x.c;
*b += 1;
let c2 = &x.c;
*a += 10;
println!("{} {} {} {}", a, b, c, c2);
}

しかし借用チェッカは、配列やスライスについてはどんな状況でも理解しないため、 このコードは動きません。

let mut x = [1, 2, 3];
let a = &mut x[0];
let b = &mut x[1];
println!("{} {}", a, b);

<anon>:4:14: 4:18 error: cannot borrow `x[..]` as mutable more than once at a time
(エラー: 一度に `x[..]` を可変として 2 回以上借用することはできません)
<anon>:4 let b = &mut x[1];
                      ^~~~
<anon>:3:14: 3:18 note: previous borrow of `x[..]` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `x[..]` until the borrow ends
(注釈: 以前の `x[..]` の借用はここで起きています。可変での借用は、その借用が終わるまで、その後のムーブや、借用、 `x[..]` の変更を防ぎます)
<anon>:3 let a = &mut x[0];
                      ^~~~
<anon>:6:2: 6:2 note: previous borrow ends here
(注釈: 以前の借用はここで終了しています)
<anon>:1 fn main() {
<anon>:2 let mut x = [1, 2, 3];
<anon>:3 let a = &mut x[0];
<anon>:4 let b = &mut x[1];
<anon>:5 println!("{} {}", a, b);
<anon>:6 }
         ^
error: aborting due to 2 previous errors
(エラー: 上記の 2 つのエラーのため中止)

仮に借用チェッカがこの単純なケースを理解しても良さそうに見えるかもしれませんが、 特に、異なるキーが本当に同じ値にマップされているときなど、 木のような一般的なコンテナ内の、各値の素集合性を借用チェッカが理解することを望むのは、 明らかに無駄です。

借用チェッカに我々が行なっていることが問題ないと "教える" ためには、 アンセーフなコードに落とす必要があります。例えば、可変スライスには、 スライスを消費し 2 つの可変スライスを返す split_at_mut 関数を使用します。 片方のスライスはインデックスの左側全てを、もう片方のスライスはインデックスの右側全てを 使用するためのものです。直感的に、これは安全と分かります。互いのスライスが重ならなず、それゆえ これらのスライスは元のスライスのエイリアスとなるからです。 しかし、その実装には少しアンセーフなコードを必要とします。

fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
    let len = self.len();
    let ptr = self.as_mut_ptr();
    assert!(mid <= len);
    unsafe {
        (from_raw_parts_mut(ptr, mid),
         from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
    }
}

これは実際、ちょっと微妙です。 同じ値に対する 2 つの &mut を生成するのを 常に避けるため、生ポインタを通じて明確に完全に新しいスライスを構築します。

しかし、もっと微妙なのは、可変参照を生成するイテレータが どのように動作するかについてです。イテレータのトレイトは以下のように定義されます。

#![allow(unused)]
fn main() {
trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;
}
}

上記の定義によれば、 Self::Item は self と何のつながりも持ちません。 これは、 next を続けて何回か呼ぶことができ、そしてそれらに対する全ての結果を 同時に保持することができることを意味します。これは、値渡しのイテレータに対しては 全く問題ありません。値渡しのイテレータも全く同じセマンティクスを持つからです。 そして、共有参照に対しても問題ありません。これらも同じものに対する任意の数の 参照を認めているからです (イテレータは共有されるオブジェクトと分離されている必要がありますが) 。

しかし、可変参照はこれをごちゃごちゃにします。ひと目見ただけでも、可変参照は この API に全く対応できないように見えるかもしれません。この API が同じオブジェクトに対する 複数の可変参照を生成するからです!

しかし、この API は本当に動作します。まさにイテレータがその場限りのオブジェクトであるからです。 IterMut が生成するすべてのものは高々 1 回しか生成されません。ですから実際には、 常に、何らかのひとかけらのデータに対する可変参照を、複数回生成していないのです。

もしかすると驚くかもしれませんが、可変のイテレータは多くの型に対して 実装する際、アンセーフなコードを必要としないのです!

例えばこれは、片方向リストです。

fn main() {}
type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

pub struct LinkedList<T> {
    head: Link<T>,
}

pub struct IterMut<'a, T: 'a>(Option<&'a mut Node<T>>);

impl<T> LinkedList<T> {
    fn iter_mut(&mut self) -> IterMut<T> {
        IterMut(self.head.as_mut().map(|node| &mut **node))
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.take().map(|node| {
            self.0 = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}

これは可変スライスです。

fn main() {}
use std::mem;

pub struct IterMut<'a, T: 'a>(&'a mut[T]);

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        let slice = mem::replace(&mut self.0, &mut []);
        if slice.is_empty() { return None; }

        let (l, r) = slice.split_at_mut(1);
        self.0 = r;
        l.get_mut(0)
    }
}

impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let slice = mem::replace(&mut self.0, &mut []);
        if slice.is_empty() { return None; }

        let new_len = slice.len() - 1;
        let (l, r) = slice.split_at_mut(new_len);
        self.0 = l;
        r.get_mut(0)
    }
}

そしてこれは二分木です。

fn main() {}
use std::collections::VecDeque;

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

struct Node<T> {
    elem: T,
    left: Link<T>,
    right: Link<T>,
}

pub struct Tree<T> {
    root: Link<T>,
}

struct NodeIterMut<'a, T: 'a> {
    elem: Option<&'a mut T>,
    left: Option<&'a mut Node<T>>,
    right: Option<&'a mut Node<T>>,
}

enum State<'a, T: 'a> {
    Elem(&'a mut T),
    Node(&'a mut Node<T>),
}

pub struct IterMut<'a, T: 'a>(VecDeque<NodeIterMut<'a, T>>);

impl<T> Tree<T> {
    pub fn iter_mut(&mut self) -> IterMut<T> {
        let mut deque = VecDeque::new();
        self.root.as_mut().map(|root| deque.push_front(root.iter_mut()));
        IterMut(deque)
    }
}

impl<T> Node<T> {
    pub fn iter_mut(&mut self) -> NodeIterMut<T> {
        NodeIterMut {
            elem: Some(&mut self.elem),
            left: self.left.as_mut().map(|node| &mut **node),
            right: self.right.as_mut().map(|node| &mut **node),
        }
    }
}


impl<'a, T> Iterator for NodeIterMut<'a, T> {
    type Item = State<'a, T>;

    fn next(&mut self) -> Option<Self::Item> {
        match self.left.take() {
            Some(node) => Some(State::Node(node)),
            None => match self.elem.take() {
                Some(elem) => Some(State::Elem(elem)),
                None => match self.right.take() {
                    Some(node) => Some(State::Node(node)),
                    None => None,
                }
            }
        }
    }
}

impl<'a, T> DoubleEndedIterator for NodeIterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        match self.right.take() {
            Some(node) => Some(State::Node(node)),
            None => match self.elem.take() {
                Some(elem) => Some(State::Elem(elem)),
                None => match self.left.take() {
                    Some(node) => Some(State::Node(node)),
                    None => None,
                }
            }
        }
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.0.front_mut().and_then(|node_it| node_it.next()) {
                Some(State::Elem(elem)) => return Some(elem),
                Some(State::Node(node)) => self.0.push_front(node.iter_mut()),
                None => if let None = self.0.pop_front() { return None },
            }
        }
    }
}

impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        loop {
            match self.0.back_mut().and_then(|node_it| node_it.next_back()) {
                Some(State::Elem(elem)) => return Some(elem),
                Some(State::Node(node)) => self.0.push_back(node.iter_mut()),
                None => if let None = self.0.pop_back() { return None },
            }
        }
    }
}

これらは全て、完全に安全で、安定版の Rust で動作します! これは究極には、 前に見た単純な構造体のケースから外れています。すなわち、 Rust は、 可変参照を複数の副フィールドに安全に分割できると理解しているのです。 ですから Option を通じて、参照を消費することで、永続的にエンコードすることができます。 (あるいはスライスの場合、空のスライスで置き換えます)

型変換

結局の所、全ては単に、どこかにあるビットの山なだけであり、型システムはただただ これらのビットを正しく扱えるように手助けするためにあるのです。ビットを型付けする事には、 2 つの 問題があります。すなわち、ビットを異なる型として解釈する必要性と、同じ意味を異なる型で持たせるために ビットを変更する必要性です。 Rust は型システム内の重要な特性をエンコードすることを奨励しているため、 これらの問題は信じられないほど蔓延しています。ですから、 Rust では結果的に、 これらの問題を解決する複数の方法があります。

まず、安全な Rust が提供する、値を再解釈する方法について見ていきます。 最も平凡なやり方は、単に値をその構成要素に分配し、そしてそれらを用いて 新しい型の値を構築する方法です。

#![allow(unused)]
fn main() {
struct Foo {
    x: u32,
    y: u16,
}

struct Bar {
    a: u32,
    b: u16,
}

fn reinterpret(foo: Foo) -> Bar {
    let Foo { x, y } = foo;
    Bar { a: x, b: y }
}
}

しかしこれは、たとえ最良の方法だとしても、煩わしいです。 一般的な変換に関しては、 Rust はよりエルゴノミックな方法を提供しています。

型強制

特定の状況では、暗黙に型変換を強制することが出来ます。これらの変換は、一般には 単に型を弱くしていて、主にポインタやライフタイム周りに着目されます。 これらはほとんどが、より多くのケースで Rust が "単に動く" ようにするために存在し、 そして大部分において、ほとんど害はありません。

これらは全ての種類の型強制です:

型強制は以下の型の間で認められています:

• 推移性: T_1 から T_3 但し T_1 が T_2 に型強制可能で、 T_2 が T_3 に型強制可能な場合
• ポインタの弱化:
  • &mut T から &T
  • *mut T から *const T
  • &T から *const T
  • &mut T から *mut T
• アンサイジング: T から U 但し T が CoerceUnsized<U> を実装している場合
• 参照外しの型強制: 型 &T の式 &x から型 &U の式 &'x 但し T が U に参照外しされる場合 (例: T: Deref<Target=U>)

CoerceUnsized<Pointer<U>> for Pointer<T> where T: Unsize<U> は 全てのポインタ型 (Box や Rc のようなスマートポインタを含む) で実装されています。 アンサイズは自動的にのみ実装され、以下の変換を有効にします。

• [T; n] => [T]
• T => Trait 但し T: Trait
• Foo<..., T, ...> => Foo<..., U, ...> 但し
  • T: Unsize<U>
  • Foo は構造体
  • Foo の最後のフィールドだけが T を含む型である
  • T は他のフィールドの一部となっていない
  • Bar<T>: Unsize<Bar<U>> 但し Foo の最後のフィールドが Bar<T> の型である場合

型強制は、型強制サイトで起こります。明確に型が指定されている全ての場所で、 その型への型強制が発生します。もし推論が必要ならば、型強制は行われません。 余すことなく言えば、式 e に対する型 U への型強制サイトは以下の通りです。

• let 文、 static、 const: let x: U = e
• 関数に対する引数: takes_a_U(e)
• 返される全ての式: fn foo() -> U { e }
• 構造体リテラル: Foo { some_u: e }
• 配列リテラル: let x: [U; 10] = [e, ..]
• タプルリテラル: let x: (U, ..) = (e, ..)
• ブロックの最後の式: let x: U = { ..; e }

トレイトをマッチさせる場合、型強制が行われないことに注意してください (レシーバは例外です、 以下を見てください) 。もしある型 U に対する impl が存在し、 T が U に型強制される場合、 T に対しては 実装が構成されません。例えば、以下の例では t が &T に型強制されても問題なく、 &T に対する impl が存在するにも関わらず、 型チェックに通りません。

trait Trait {}

fn foo<X: Trait>(t: X) {}

impl<'a> Trait for &'a i32 {}


fn main() {
    let t: &mut i32 = &mut 0;
    foo(t);
}

<anon>:10:5: 10:8 error: the trait bound `&mut i32 : Trait` is not satisfied [E0277]
(エラー: トレイト境界 `&mut i32: Trait` が満たされていません)
<anon>:10     foo(t);
              ^~~

ドットオペレータ

ドットオペレータは型を変換するため、沢山の魔法を使います。 型がマッチするまで、自動参照、自動参照外し、そして型強制を行ないます。

TODO: http://stackoverflow.com/questions/28519997/what-are-rusts-exact-auto-dereferencing-rules/28552082#28552082 から情報を盗ってくる。

キャスト

キャストは型強制のスーパーセットです。すなわち、全ての型強制は、キャストを通じて 明示的に引き起こすことが出来ます。しかし、いくつかの変換はキャストを必要とします。 型強制は普及していて、大体の場合、害はないのですが、これらの "真のキャスト" は稀で、 潜在的に危険です。ですから、キャストは as キーワードを用いて、明示的に 実行しなければなりません: expr as Type

真のキャストは一般的に、生ポインタやプリミティブ型の数値型に関係します。 真のキャストは危険ですが、これらのキャストは実行時に失敗しません。 もしキャストが何か微妙なコーナーケースを引き起こしたとしても、 何の指摘もされないでしょう。キャストは単に成功します。そうは言ったものの、 キャストは型レベルで正しくなければなりません。でなければそのキャストは静的に 防がれます。例えば、 7u8 as bool はコンパイルできません。

そうは言っていますが、キャストは unsafe ではありません。なぜなら、 キャストは一般的に、それ自体でメモリ安全性を侵害しないからです。 例えば、整数を生ポインタに変換すると、非常に簡単にひどい問題を引き起しうるでしょう。 しかしながら、ポインタを生成する事自体は安全です。なぜなら、実際に生ポインタを使用すること が既に unsafe としてマークされているからです。

これは、全ての真のキャストを網羅しているリストです。簡潔にするため、 * を *const か *mut の どちらかとして使い、 integer を整数型プリミティブの何かとして用います。

• *T as *U 但し T, U: Sized
• *T as *U TODO: サイズが不定の場合について説明する
• *T as integer
• integer as *T
• number as number
• C-like-enum as integer
• bool as integer
• char as integer
• u8 as char
• &[T; n] as *const T
• fn as *T 但し T: Sized
• fn as integer

生スライスをキャストする時、その長さは調整されないことに注意してください。 *const [u16] as *const [u8] は、 元のメモリの半分しか含まないスライスを生成します。

キャストは推移的ではありません。つまり、 e as U1 as U2 が有効な式だとしても、 e as U2 は 必ずしも有効とは限りません。

数値のキャストに関しては、かなり多くの事項について考える必要があります。

• 同じ大きさの 2 つの整数の間でのキャスト (例: i32 -> u32) は no-op です
• 大きい方の整数から小さい方の整数へのキャスト (例: u32 -> u8) は切り捨てが発生します
• 小さい方の整数から大きい方の整数へのキャスト (例: u8 -> u32) は
  • もし小さい方の整数が符号なしの場合、ゼロ拡張されます
  • もし小さい方の整数が符号ありの場合、符号拡張されます
• 浮動小数点数から整数へのキャストは、小数点以下が切り捨てられます
  • 注意: 現在もし丸められた値が、キャスト先の整数型で表現できない場合、未定義動作を引き起こします。 これはバグで、将来修正されます。
• 整数から浮動小数点数へのキャストは、整数を浮動小数点数で表現します。必要ならば丸められます (丸めの方針は指定されていません)
• f32 から f64 へのキャストは完全で、損失はありません
• f64 から f32 へのキャストは、最も近い表現可能な値となります (丸めの方針は指定されていません)
  • 注意: 現在もし値が f32 で表現可能な最大の値より大きい、あるいは最小の値より小さい有限の値である場合、未定義動作を引き起こします。 これはバグで、将来修正されます。

トランスミュート

型システムから抜け出しましょう! 何がなんでもビットを再解釈します! この本は アンセーフなもの全てについて書かれていますが、この章でカバーされている操作を やるよりも、他の方法を見つけるよう深刻に考えるべきだということは、 いくら強調しようとも、強調しきれません。これは本当に、マジで、 Rust で出来る 最も恐ろしいアンセーフなことです。ここではガードレールは爪楊枝のように脆いです。

mem::transmute<T, U> は型 T の値を受け取り、その値が型 U であると再解釈します。 唯一の制約は、 T と U が同じサイズを持つとされていることです。 この操作によって未定義動作が起こる方法を考えると、気が遠くなります。

• まず真っ先に、いかなる型においても、無効状態のインスタンスを作ることは、本当に予測不可能な混沌状態を引き起こすでしょう。
• transmute はオーバーロードされたリターン型を持ちます。もしリターン型を指定しなかった場合、 推論を満たす、びっくりするような型を生成するかもしれません。
• 無効なプリミティブを生成することは未定義動作を引き起こします。
• repr(C) でない型の間でのトランスミュートは未定義動作を引き起こします。
• & から &mut へのトランスミュートは未定義動作を引き起こします。
  • & から &mut へのトランスミュートはいつも未定義動作を引き起こします。
  • いいえ、これは出来ません。
  • いいか、君は特別じゃないんだ。
• 明確にライフタイムが指定されていない参照へのトランスミュートは無制限のライフタイムを生成します。

mem::transmute_copy<T, U> は、どうにかして transmute よりも本当に更にアンセーフな事をしようとします。 この関数は &T から size_of<U> バイトコピーし、これらを U として解釈します。 もし U が T よりも大きい場合、未定義動作を引き起こしますが、 mem::transmute の サイズチェックはなくなっています ( T の先頭部分をコピーすることが有効である場合があるためです) 。

そしてもちろん、これらの関数の機能のほとんどを、ポインタのキャストを利用することで 得ることができます。

初期化されないメモリを扱う

すべての Rust の、実行時にアロケートされるメモリは、最初に初期化されません。 この状態では、メモリ上の値は、そのメモリ番地にあると想定される型の、正しい状態を 反映しているかもしれないし、していないかもしれないビットの無限の山です。 このメモリをいかなる型の値として解釈しようとしても、未定義動作を引き起こすでしょう。 絶対にしないでください。

Rust では、初期化されていないメモリを扱う、チェックが入る (安全な) 方法と、 チェックされない (アンセーフな) やり方があります。

チェックされる初期化されていないメモリ

C のように、 Rust の全てのスタック上の変数は、値が明示的に代入されるまでは初期化されません。 C とは違い、 Rust では、 値が代入されるまで、初期化されていない変数を読み込もうとするのを静的に防ぎます。

fn main() {
    let x: i32;
    println!("{}", x);
}

src/main.rs:3:20: 3:21 error: use of possibly uninitialized variable: `x`
(エラー: 初期化されていないかもしれない変数 `x` を使用しています)
src/main.rs:3     println!("{}", x);
                                 ^

これは、基本的な分岐分析に基づいています。すなわち、全ての分岐は、 x が初めに 使用される前に、値を代入しなければなりません。興味深いことに、 Rust では、もし全ての分岐の中で 値がちょうど一回しか代入されない場合、遅延初期化を行なうために変数をミュータブルにする必要がありません。 しかし、この分析は定数の分析や、それに似たものを利用していないため、このコードはコンパイルできます。

fn main() {
    let x: i32;

    if true {
        x = 1;
    } else {
        x = 2;
    }

    println!("{}", x);
}

しかし、このコードはコンパイルできません。

fn main() {
    let x: i32;
    if true {
        x = 1;
    }
    println!("{}", x);
}

src/main.rs:6:17: 6:18 error: use of possibly uninitialized variable: `x`
(エラー: 初期化されていないかもしれない変数 `x` を使用しています)
src/main.rs:6   println!("{}", x);

一方でこのコードはコンパイルできます。

fn main() {
    let x: i32;
    if true {
        x = 1;
        println!("{}", x);
    }
    // 初期化されない分岐があっても構いません。
    // 値をその分岐で使用しないからです。
}

もちろん、分析では実際の値は考慮されませんが、比較的洗練された、依存関係や制御フローに関する 分析は行われます。例えば、このコードは動作します。

#![allow(unused)]
fn main() {
let x: i32;

loop {
    // Rust は、この分岐が状況によらず選択されることは理解しません。
    // なぜならこれは、実際の値に依存するためです。
    if true {
        // しかし Rust は、この分岐がたった一回しか選択されないと理解しています。
        // なぜなら、状況によらず、この分岐を抜け出すからです。
        // それゆえ、`x` はミュータブルとしてマークされる必要がないのです。
        x = 0;
        break;
    }
}
// Rust はまた、 break に到達せずに、ここに来ることが不可能だということを知っています。
// そしてそれゆえに、 `x` はこの場所において初期化されなければならないと知っているのです!
println!("{}", x);
}

もし値の型が Copy を実装しておらず、値が変数からムーブされたら、 論理的にはその変数は初期化されていない事になります。

fn main() {
    let x = 0;
    let y = Box::new(0);
    let z1 = x; // i32 は Copy を実装しているため、 x はまだ有効です
    let z2 = y; // Box は Copy を実装していないため、もはや y は論理的には初期化されていません
}

しかしながらこの例では、 y に値を再代入しようとするのであれば、 y を ミュータブルとしてマークする必要があるでしょう。 安全な Rust のプログラムは y の値が変わったと認識出来るからです。

fn main() {
    let mut y = Box::new(0);
    let z = y; // Box が Copy を実装していないため、もはや y は論理的には初期化されていません
    y = Box::new(1); // y を再初期化します
}

そうでなければ、 y は全く新しい変数のようなものです。

ドロップフラグ

前章の例では、 Rust における興味深い問題を紹介しました。 状況によって、メモリの場所を初期化したり、初期化されていない状態に戻したり、 再初期化したりすることを、完全に安全に行なうことが可能だということを 確認してきました。 Copy を実装している型に関しては、メモリの場所にあるものは 単なるビットのランダムな山であるため、これは特に重要なことではありません。 しかし、デストラクタを備えている型に関しては話が違います。 Rust は変数が代入されたときや、 あるいは変数がスコープを外れたときは毎回、デストラクタを呼ぶかを知る必要があります。 これを、状況に応じた初期化と共に、どのように行えばよいのでしょうか?

全ての代入において心配する必要がある問題ではないことに注意してください。 特に、参照外しを通した代入では、状況によらずドロップしますし、 let を使用した 代入では、状況によらずドロップしません。

let mut x = Box::new(0); // let によって新しい変数が生成されるので、ドロップの必要はありません
let y = &mut x;
*y = Box::new(1); // 参照外しでは、参照される側の変数は初期化されていると見なされているため、この参照されている変数はいつもドロップします

これは、以前に初期化された変数や、その副フィールドの 1 つを上書きする時のみ問題となります。

実際には Rust は実行時に、型がドロップされるべきかそうでないかを追っていると分かります。 変数が初期化されたり、初期化されてない状態になったりすると、その変数に対するドロップフラグが 切り替わります。もし変数がドロップされる必要があるかもしれない状況になると、 本当にドロップされるべきかを決定するため、このフラグが評価されます。

勿論、しばしば値の初期化に関する状態は、プログラムのどの地点においても 知ることが出来ます。もしこれが本当なら、コンパイラは理論的には、 もっと効率的なコードを生成できます! 例えば、分岐のない真っ直ぐなコードは、 このような静的ドロップセマンティクスを持っています。

#![allow(unused)]
fn main() {
let mut x = Box::new(0); // x は初期化されていないので、単に上書きします。
let mut y = x;           // y は初期化されていないので、単に上書きします。そして x を初期化前の状態にします。
x = Box::new(0);         // x は初期化されていないので、単に上書きします。
y = x;                   // y は初期化されているので、 y をドロップし、上書きし、そして x を初期化前の状態にします!
                         // y はスコープを抜けました。 y は初期化されているので、 y をドロップします!
                         // x はスコープを抜けました。 x は初期化されていないので、何もしません。
}

同じように、全ての分岐が初期化の点において、同一のことをする分岐があるコードでは、 静的ドロップセマンティクスを持っています。

#![allow(unused)]
fn main() {
let condition = true;
let mut x = Box::new(0);    // x は初期化されていないので、単に上書きします。
if condition {
    drop(x)                 // x はムーブされたので、 x を初期化前の状態にします。
} else {
    println!("{}", x);
    drop(x)                 // x はムーブされたので、 x を初期化前の状態にします。
}
x = Box::new(0);            // x は初期化されていない状態なので、単に上書きします。
                            // x はスコープを抜けました。 x は初期化されているので、 x をドロップします!
}

しかしながら以下のようなコードでは、正しくドロップするために実行時の情報が必要となります。

#![allow(unused)]
fn main() {
let condition = true;
let x;
if condition {
    x = Box::new(0);        // x は初期化されていないので、単に上書きします。
    println!("{}", x);
}
                            // x はスコープを抜けました。 x は初期化されていないかもしれません。
                            // フラグを確認!
}

勿論この場合、静的ドロップセマンティクスを復活させるのは些細なことです。

#![allow(unused)]
fn main() {
let condition = true;
if condition {
    let x = Box::new(0);
    println!("{}", x);
}
}

ドロップフラグはスタック上で追跡され、ドロップを実装している型に 隠されることはもはやありません。

チェックされない初期化されていないメモリ

この規則の興味深い例外に、配列があります。安全な Rust は、配列を部分的に初期化することを 認めません。配列を初期化するとき、 let x = [val; N] を用いて 全ての値を初期化するか、 let x = [val1, val2, val3] を用いて、 それぞれの要素の値を個別に指定するかのどちらかが出来ます。残念ながら、 特によりインクリメンタルなやり方や、動的な方法で配列を初期化する必要がある場合、 これは非常に融通が利きません。

アンセーフな Rust では、この問題に対処するパワフルなツールが用意されています。 mem::uninitialized です。 この関数は本当に何もせず、値を返すふりをします。これを利用することで、 Rust に 変数が初期化されたと見なさせることができ、状況に応じた、インクリメンタルな初期化を 行ないトリッキーなことが出来ます。

残念ながら、これによってあらゆる種類の問題が浮かび上がります。 変数が初期化されていると Rust が思っているか、思っていないかによって、 代入は異なる意味を持ちます。もし初期化していないと思っている場合、 Rust は、 セマンティクス的には単にビットを初期化していないメモリにコピーし、他には 何もしません。しかし、もし値が初期化していると思っている場合、 Rust は 古い値を Drop しようとします! Rust に、値が初期化されていると信じ込ませるよう トリックをしたので、もはや安全には普通の代入は使えません。

生のシステムアロケータを使用している場合も問題となります。このアロケータは、 初期化されていないメモリへのポインタを返すからです。

これに対処するには、 ptr モジュールを使用しなければなりません。 特にこのモジュールは、古い値をドロップせずに、メモリ上の場所に値を代入することが 可能となる 3 つの関数を提供しています: write、copy、copy_nonoverlappingです。

• ptr::write(ptr, val) は val を受け取り、 ptr が指し示すアドレスに受け取った値を 移します。
• ptr::copy(src, dest, count) は、 T 型の count が占有するビット数だけ、 src から dest に コピーします。 (これは memmove と同じです -- 引数の順序が逆転していることに注意してください!)
• ptr::copy_nonoverlapping(src, dest, count) は copy と同じことをしますが、 2 つのメモリ領域が 重なっていないと見なしているため、若干高速です。 (これは memcpy と同じです -- 引数の 順序が逆転していることに注意してください!)

言うまでもないのですが、もしこれらの関数が誤用されると、甚大な被害を引き起こしたり、 未定義動作を引き起こすでしょう。これらの関数自体が必要とする唯一のものは、 読み書きしたい場所がアロケートされているということです。しかし、 任意のビットを任意のメモリの場所に書き込むことでものを壊すようなやり方は数え切れません!

これらを全部一緒にすると、以下のようなコードとなります。

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

// 配列の大きさはハードコードされていますが，簡単に変えられます。
// これは、配列を初期化するのに [a, b, c] という構文を使えないことを意味しますがね!
const SIZE: usize = 10;

let mut x: [Box<u32>; SIZE];

unsafe {
	// Rust に x が完全に初期化されたと思わせます
	x = mem::uninitialized();
	for i in 0..SIZE {
		// 非常に注意深く、それぞれのインデックスを読み込まずに上書きします
		// 注意: 例外安全性は考慮されていません。 Box はパニックできません
		ptr::write(&mut x[i], Box::new(i as u32));
	}
}

println!("{:?}", x);
}

Drop を実装していない型や、 Drop を実装する型を含まない型との、ptr::write スタイルの いたずらを心配しなくてよいということは注目に値します。なぜなら Rust は、これらをドロップしようと しないと知っているからです。同じように、もし部分的に初期化されている構造体のフィールドに Drop を 実装しているものが存在しない場合、このフィールド群に直接代入できるようにするべきです。

しかし、初期化されていないメモリを扱うとき、生成した値を Rust が、以前に 完全に初期化されたものと見なしてドロップしようとしてしまわないか、常に警戒する必要があります。 値がデストラクタを持つ場合、変数のスコープを通り抜ける全てのコントロールパスは、終了時までに その値を初期化する必要があります。これはコードパニックを含みます

まあ、初期化されていないメモリを扱うことに関してはこんなものです。 基本的にどのような場所でも、初期化されていないメモリが渡されることは予期していません。 ですからもしそのようなメモリを分配する場合、確実に本当に注意深く行なってください。

所有権に基づいたリソース管理(Ownership Based Resource Management, OBRM)の危険性について

OBRM(またの名をRAII: Resource Acquisition Is Initialization)とは、Rustにおいて 関連性の深い概念です。特に標準ライブラリと密接に関与します。

このパターンを簡単に説明すると次のようになります。「リソースを獲得するには そのリソースを管理するオブジェクトを作成し、リソースを解放するにはその オブジェクトを単に破棄すればリソースがクリーンアップされる。」 いうものです。このように管理される最も一般的な「リソース」は単なるメモリです。 Box、Rc、その他std::collectionsの諸々全ては、メモリの管理を便利にするためのものです。 Rustの場合、メモリの管理において一貫したGCに頼るということができないので、これら は特に重要になります。大事なことなので強調しましょう。この「管理」という考え方は Rustの根幹です。それは何もメモリに限った話ではありません。スレッド、ファイル、 ソケットといったほぼ全てのリソースがこういった考え方に基づくAPIを通して扱うように できています。

コンストラクタ

ユーザが定義した型のインスタンスを作る方法はただ一つしかありません: 型名を決めて、 全てのフィールドをいっぺんに初期化することです。

#![allow(unused)]
fn main() {
struct Foo {
    a: u8,
    b: u32,
    c: bool,
}

enum Bar {
    X(u32),
    Y(bool),
}

struct Unit;

let foo = Foo { a: 0, b: 1, c: false };
let bar = Bar::X(0);
let empty = Unit;
}

以上。これ以外の型のインスタンスを作る方法は皆、単にいくつかのことを行なう全く普通の 関数を呼び、結局 1 つの真のコンストラクタに辿り着くのです。

C++ と違い、 Rust は沢山の組み込みコンストラクタを備えていません。 Rust には、 Copy、 Default、 Assignment、 Moveやその他諸々のコンストラクタが ありません。理由は様々ですが、大体 Rust の考え方である、明確であること、という事に 落ち着きます。

Move コンストラクタは Rust においては意味がありません。なぜなら、型が、自身の メモリ上の場所を "気にする" ようにはしないからです。すべての型は何もしなくても、 メモリ中のどこか別の場所にコピー出来るよう準備されなければなりません。 これは、純粋な、スタック上にあるけれどもそれでも動かすことの出来る、 あるノードの次のノードへのポインタをそのノード自身が保持する線形リストは (安全には) 存在し得ない 事を意味します。

Assignment コンストラクタや Copy コンストラクタも同様に存在しません。 なぜなら、ムーブセマンティクスは Rust における唯一のセマンティクスだからです。 せいぜい x = y が単に y のビットを変数 x に移すくらいです。 Rust では C++ の コピー指向のセマンティクスを提供する、 2 つの機能があります。 Copy と Clone です。 Clone は Copy コンストラクタと 同じようなものですが、暗黙に呼び出されることは一切ありません。クローンを生成したい要素に対して、 明示的に clone を呼び出す必要があります。 Copy は Clone の特別なケースで、 実装は単純に "ビットをコピーする" ことです。 Copy を実装する型は、 ムーブが発生すると毎回クローンを生成します。しかし、 Copy の定義によって、 これは、古いコピーを初期化されていないとは扱わない事を単に意味します。つまり no-op なのです。

Rust は Default コンストラクタと同等のものを指定する、 Default トレイトを 提供していますが、このトレイトが使用されるのは驚くほど稀です。なぜなら、 変数は暗黙には初期化されないからです。 Default は、 基本的にはジェネリックプログラミングでのみ有用です。具体例では、 あらゆる種類の "デフォルトの" コンストラクタに対して、このトレイトを実装する型が静的な new メソッドを 提供します。これは他の言語における new とは関係がなく、特に意味はありません。 これはただの命名規則です。

TODO: "placement new" について話す?

デストラクタ

言語が実際に提供しているものは、 Drop トレイトを通じた完全に自動的な デストラクタで、以下のメソッドを提供しています。

fn drop(&mut self);

このメソッドは、型が行なっていたことをなんとか終わらせるための時間を、型に 与えます。

drop が実行された後、 Rust は self の全てのフィールドのドロップを再帰的に実行しようとします。

これは便利な機能で、子フィールドをドロップするための "デストラクタの決まり文句" を 書く必要がありません。もし構造体に、子フィールドをドロップする以外の、ドロップされる際の 特別なロジックが存在しなければ、 Drop を実装する必要が全くありません!

この振る舞いを防ぐステーブルな方法は、 Rust 1.0 の時点で存在しません

&mut self を受け取ることは、再帰ドロップを防ぐことが出来たとしても、例えば self から フィールドをムーブすることが妨げられることに注意してください。 ほとんどの型にとっては、全く問題ありません。

例えば Box のカスタム実装では、以下のような Drop を書くかもしれません。

#![feature(alloc, heap_api, unique)]

extern crate alloc;

use std::ptr::{drop_in_place, Unique};
use std::mem;

use alloc::heap;

struct Box<T>{ ptr: Unique<T> }

impl<T> Drop for Box<T> {
    fn drop(&mut self) {
        unsafe {
            drop_in_place(*self.ptr);
            heap::deallocate((*self.ptr) as *mut u8,
                             mem::size_of::<T>(),
                             mem::align_of::<T>());
        }
    }
}
fn main() {}

そしてこれは、 Rust が ptr フィールドをドロップする際、単に、実際の Drop 実装が ない Unique に着目するため、このコードは問題なく動くのです。 同様に、解放後は ptr を使用することが出来ません。なぜならドロップが存在する場合、 そのドロップ実装にアクセス不可能となるからです。

しかし、このコードは動かないでしょう。

#![feature(alloc, heap_api, unique)]

extern crate alloc;

use std::ptr::{drop_in_place, Unique};
use std::mem;

use alloc::heap;

struct Box<T>{ ptr: Unique<T> }

impl<T> Drop for Box<T> {
    fn drop(&mut self) {
        unsafe {
            drop_in_place(*self.ptr);
            heap::deallocate((*self.ptr) as *mut u8,
                             mem::size_of::<T>(),
                             mem::align_of::<T>());
        }
    }
}

struct SuperBox<T> { my_box: Box<T> }

impl<T> Drop for SuperBox<T> {
    fn drop(&mut self) {
        unsafe {
            // 超最適化: Box の内容を `drop` せずに
            // 内容をデアロケートします
            heap::deallocate((*self.my_box.ptr) as *mut u8,
                             mem::size_of::<T>(),
                             mem::align_of::<T>());
        }
    }
}
fn main() {}

SuperBox のデストラクタで box の ptr をデアロケートした後、 Rust は適切に box に、 自身をドロップするよう通達し、その結果、解放後の使用や二重解放によって全部消し飛びます。

再帰ドロップは、構造体や列挙型が Drop を定義しているかしていないかによらず、 全ての構造体や列挙型に適用されることに注意してください。 ですから、以下のような

#![allow(unused)]
fn main() {
struct Boxy<T> {
    data1: Box<T>,
    data2: Box<T>,
    info: u32,
}
}

ものは、それ自体が Drop を実装していなくても、それがドロップされるときには毎回、 data1 と data2 の フィールドをデストラクトします。これを、そのような型が Drop を必要とすると言います。型が Drop を 実装していなくてもです。

同様に

#![allow(unused)]
fn main() {
enum Link {
    Next(Box<Link>),
    None,
}
}

これは、インスタンスが Next を格納しているとき、そのときだけ内部の Box フィールドを ドロップします。

一般に、これは非常に上手く動きます。なぜなら、データレイアウトをリファクタリングするときに、 ドロップを追加あるいは削除する心配が必要ないからです。もちろん、デストラクタで何か トリッキーなことが必要になる妥当なケースは、たくさんあります。

再帰ドロップを上書きし、 drop の最中に Self からのムーブを可能にする、 古典的で安全な解決策は、 Option を使うことです。

#![feature(alloc, heap_api, unique)]

extern crate alloc;

use std::ptr::{drop_in_place, Unique};
use std::mem;

use alloc::heap;

struct Box<T>{ ptr: Unique<T> }

impl<T> Drop for Box<T> {
    fn drop(&mut self) {
        unsafe {
            drop_in_place(*self.ptr);
            heap::deallocate((*self.ptr) as *mut u8,
                             mem::size_of::<T>(),
                             mem::align_of::<T>());
        }
    }
}

struct SuperBox<T> { my_box: Option<Box<T>> }

impl<T> Drop for SuperBox<T> {
    fn drop(&mut self) {
        unsafe {
            // 超最適化: Box の内容を `drop` せずに
            // 内容をデアロケートします
            // Rust が `box` フィールドをドロップしようとさせないために、
            // `box` フィールドを `None` と設定する必要があります
            let my_box = self.my_box.take().unwrap();
            heap::deallocate((*my_box.ptr) as *mut u8,
                             mem::size_of::<T>(),
                             mem::align_of::<T>());
            mem::forget(my_box);
        }
    }
}
fn main() {}

しかしながら、これはかなり奇妙なセマンティクスです。すなわち、常に Some であるべき フィールドが、 None になりうると言っているからです。なぜならこれが、 デストラクタで起こっているからです。勿論、これは逆に大いに納得がいきます。 デストラクタ内で self に対して任意のメソッドを呼ぶことができ、同じことが、 フィールドが未初期化状態に戻されたあとに行われるのを防ぐはずですから。 だからといって、他の不正状態が生まれることを防ぐわけではありませんが。

結局のところ、これはそれほど悪くないやり方です。明らかに誰もが必要とする機能です。 しかしながら将来、あるフィールドが自動的にドロップされるべきでないと知らせる、 素晴らしい方法が現れると我々は期待しています。

リーク

所有権に基づいたリソース管理は、構成を単純にすることを意図しています。 オブジェクトを生成すると、リソースを獲得します。そして、オブジェクトが 破棄されるとリソースを解放します。オブジェクトは自動的に破棄されるので、 リソースは必ず解放されますし、できるだけ早く解放されるのです! 明らかにこれは完全で、我々の全ての問題は解決します。

実際にはこれは最悪で、我々には新しくそして風変わりな問題が与えられるのです。

多くの人々は、 Rust はリソースのリークを取り除いたと信じることが好きです。 実際、これは基本的には正しいです。安全な Rust のプログラムが、制御不能なやり方で、 リソースをリークしたら驚くでしょう。

しかしながら理論的な観点から見れば、どのように見ても、これは全く真実ではありません。 最も厳密な意味では、 "リーク" は非常に抽象的で、防げるものではありません。 プログラムの始めにコレクションを初期化し、デストラクタと共に沢山のオブジェクトで いっぱいにし、そしてこのコレクションを絶対に参照しない無限イベントループに 突入することは極めて些細なことです。コレクションはプログラムが終わるまで、 貴重な資源を保持し続けたまま、使われず無駄に浪費し続けます (そして OS によって 結局全ての資源は返還されますが) 。

より厳密なリークの形式を考えたほうが良いかもしれません。到達できない値を ドロップし損ねることです。 Rust はこれも防ぐことが出来ません。実際 Rust には、 これを行なう関数があります。 mem::forget です。この関数は渡された値を消費し、 そしてその値のデストラクタを実行しません。

過去に mem::forget は、リントにおいてアンセーフとしてマークされていました。 デストラクタを呼ばないことは、通常行儀の良い方法ではないからです (いくつかの 特別なアンセーフのコードにおいては便利ですが) 。 しかしこれは、一般的に次の意見に対して擁護できない考えだと決定されました。 すなわち、 安全なコードでデストラクタを呼び損ねる方法が沢山存在するのです。 最も有名な例は、内部可変性を使用した、参照カウント方式のポインタの循環を生成 することです。

安全なコードが、デストラクタのリークが起こらないと見なすことは理に適っています。 いかなるプログラムにおいても、デストラクタをリークするようなものは大体間違っていますから。 しかし、アンセーフなコードは、デストラクタがきちんと安全に実行されると信用できません。 ほとんどの型にとっては、これは問題ではありません。もしデストラクタをリークしたら、 当然その型へはアクセス不可能となります。ですからこれは問題ではありません。 そうですよね? 例えば、 Box<u8> をリークしても、いくらかのメモリを無駄にはしますが、 メモリ安全性はほとんど侵害することがないでしょう。

しかし、デストラクタのリークに対して注意深くならなければいけない場合は、プロキシ型です。 これらは、なんとかして異なったオブジェクトにアクセスするものの、そのオブジェクトを 実際には所有しない型です。プロキシオブジェクトは極めて稀です。気を付ける必要のある プロキシオブジェクトに至っては殊更稀です。しかし、ここでは標準ライブラリにある 3 つの 興味深い例について着目していきます。

• vec::Drain
• Rc
• thread::scoped::JoinGuard

Drain

drain は、コンテナを消費せずにコンテナからデータをムーブする、 コレクションの API です。これによって、 Vec の全ての内容の所有権を獲得した後に、 Vec の アロケーションを再利用することが出来ます。 drain は Vec の内容を値で返すイテレータ (Drain) を 生成します。

では、 Drain がイテレーションの真っ最中であるとしましょう。ムーブされた値もあれば、 まだの値もあります。つまりこれは、 Vec の一部のデータが今、論理的には未初期化のデータで 埋まっていることを意味します! 値を削除する度に Vec の要素をずらすことも出来たでしょう。 けれどもこれは結果的に、パフォーマンスをひどく落とすことになるでしょう。

その代わりに Drain がドロップする時に、 Vecの背後にあるストレージを 修正するようにしたいと思います。 Drain を使い終わったら、削除されなかった要素を ずらし (Drain は副範囲をサポートしています) 、そして Vec の len を修正します。 巻き戻し安全でもあります! 安心!

それでは以下の例を考えてみましょう。

let mut vec = vec![Box::new(0); 4];

{
    // ドレインを開始します。 vec にはもうアクセスできません
    let mut drainer = vec.drain(..);

    // 2 つの値を引き出し、即座にドロップします
    drainer.next();
    drainer.next();

    // drainer を取り除きますが、デストラクタは呼び出しません
    mem::forget(drainer);
}

// しまった、 vec[0] はドロップされていたんだった、解放されたメモリを読み出そうとしているぞ!
println!("{}", vec[0]);

これは本当に明らかに良くないです。残念ながら、ある種の板挟みになっています。 すなわち、毎回のステップで一貫性のある状態を維持することは、膨大なコストが 発生するのです (そして API のあらゆる利点を消してしまうでしょう) 。 一貫性のある状態を維持できないことで、安全なコードで未定義動作を起こしてしまいます (これにより API が 不健全となってしまいます) 。

ではどうすればいいのでしょうか? うーん、自明に一貫性のある状態を選択することが出来ます。 すなわち、イテレーションの初めでは Vec の len を 0 に設定し、そしてもし必要ならば、 デストラクタ内で len を修正します。このようにすることで、もしすべてが普通に実行されるなら、 最小限のオーバーヘッドで望まれている振る舞いを得ることが出来ます。 しかし、もし大胆にも mem::forget がイテレーションの真ん中に存在したら、 この関数によって、更に多くのものがリークされます (そして多分 Vec を、 一貫性はあるとしてもユーザが予期しない状態にするでしょう) 。 mem::forget は安全だとして 受け入れたので、このリークは絶対安全です。リークが更に多くのリークを引き起こしてしまうことを、 リークの増幅と呼びます。

Rc

Rc は興味深いケースです。なぜなら、ひと目見ただけでは、 Rc がプロキシな値とは全く見えないからです。 結局、 Rc は自身が指しているデータを操作し、その値に対する Rc が全てドロップされることで、 その値もドロップされます。 Rc をリークすることは特に危険のようには見えません。 参照カウントが永遠にインクリメントされたまま、データが解放されたりドロップされるのを 妨害します。けれどもこれは単に Box に似ています。そうですよね?

いいえ。

では、以下の単純化された Rc の実装を確認しましょう。

struct Rc<T> {
    ptr: *mut RcBox<T>,
}

struct RcBox<T> {
    data: T,
    ref_count: usize,
}

impl<T> Rc<T> {
    fn new(data: T) -> Self {
        unsafe {
            // もし heap::allocate がこのように動作したらよいと思いませんか?
            let ptr = heap::allocate::<RcBox<T>>();
            ptr::write(ptr, RcBox {
                data: data,
                ref_count: 1,
            });
            Rc { ptr: ptr }
        }
    }

    fn clone(&self) -> Self {
        unsafe {
            (*self.ptr).ref_count += 1;
        }
        Rc { ptr: self.ptr }
    }
}

impl<T> Drop for Rc<T> {
    fn drop(&mut self) {
        unsafe {
            (*self.ptr).ref_count -= 1;
            if (*self.ptr).ref_count == 0 {
                // データをドロップしそして解放します
                ptr::read(self.ptr);
                heap::deallocate(self.ptr);
            }
        }
    }
}

このコードは暗黙で微妙な前提を含んでいます。すなわち、 ref_count が usize に 収まるということです。なぜなら、 usize::MAX 個以上の Rc はメモリに存在し得ないからです。 しかしながら、これ自体が ref_count が正確に、メモリ上にある Rc の数を反映しているという 前提の上にあります。ご存知のように、 mem::forget のせいでこれは正しくありません。 mem::forget を 使用することで、 ref_count をオーバーフローさせることが可能です。そして、 Rc が存在していても ref_count を 0 にすることができます。こうしてめでたく、内部データを解放後に使用することができます。 だめだだめだ、最悪だ。

これは単に ref_count を確認し、何かを行なうことで解決可能です。 標準ライブラリにおいては、単にアボートします。なぜならプログラムが ひどく悪化したからです。そしておーまいがっしゅ、これは本当に馬鹿げたコーナーケースなのです。

thread::scoped::JoinGuard

thread::scoped API は、共有されているデータが 1 つでもスコープを抜ける前に、 親がスレッドを join することを保証します。こうすることで、親スレッドのスタック上の データを同期なしに参照するようなスレッドを生成することが可能になります。

pub fn scoped<'a, F>(f: F) -> JoinGuard<'a>
    where F: FnOnce() + Send + 'a

ここで f は、他のスレッドで実行する何らかのクロージャです。 F: Send + 'a ということは、 f は 'a の長さ 生きるデータを内包します。そしてそのデータを所有するか、データは Sync ということになります (&data が Send であることを示唆します) 。

JoinGuard がライフタイムを所有しているため、 JoinGuard は、内包しているデータが 親スレッドで借用されたままの状態にします。これはつまり、 JoinGuard が、もう片方のスレッドが扱っている データよりも長生きできないことを意味します。 JoinGuard が本当にドロップされるとき、 JoinGuard は親スレッドをブロックし、内包されているデータのどれか 1 つでも親のスコープを 抜ける前に、子スレッドを確実に終了させます。

使用法は以下のような感じです。

let mut data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
{
    let guards = vec![];
    for x in &mut data {
        // 可変参照をクロージャ内にムーブします。そして、
        // クロージャを別のスレッド上で実行します。クロージャには
        // 可変参照 `x` のライフタイムによる、ライフタイムの制限があります。
        // 値が返される guard には、代わってクロージャのライフタイムが
        // 代入されます。ですから `x` と同じように、 guard も `data` を可変で借用します。
        // これは、 guard がスコープを抜けるまで `data` にアクセスできないことを意味します。
        let guard = thread::scoped(move || {
            *x *= 2;
        });
        // 後の使用に備えて、スレッドのガードを保存します
        guards.push(guard);
    }
    // 全てのガードはここでドロップされましたので、全てのスレッドを強制的に join します
    // (このスレッドは他のスレッドが終了するまでブロックされます) 。
    // スレッドが join されたら、借用は有効ではなくなり、データは
    // 再びこのスレッドからアクセス可能となります。
}
// data は絶対ここで変化します。

原則として、これは完全に動作します! Rust の所有権システムが見事にこれを確実に行ないます! ...デストラクタが安全に呼ばれるということに頼っている以外は。

let mut data = Box::new(0);
{
    let guard = thread::scoped(|| {
        // これは良くてもデータ競合を引き起こし、最悪、解放後の使用にもなります。
        *data += 1;
    });
    // guard が忘れられたので、このスレッドをブロックせず、
    // 借用が有効ではなくなります。
    mem::forget(guard);
}
// ですからスコープ内のスレッドが Box にアクセスしようとしているかもしれないし、
// しようとしていないかもしれない最中に Box がここでドロップされてしまいます。

ちくしょう。デストラクタが実行されるのは API にとってとても大切だったのですが、 全く別の設計上の理由で破棄しなくてはいけなかったのです。

巻き戻し

Rustのエラーハンドリングには階層的なスキームが存在します。

• もし何かが、明確な理由があって欠如しうる場合、Optionが使われます
• もし何かおかしなことが起こった際に合理的な対処方法がある場合、Resultが使われます
• もし何かおかしなことが起こった際に合理的な対処方法がない場合、そのスレッドはパニックします
• もし何か破滅的な出来事が起こった場合、プログラムはアボートします

大抵の状況では圧倒的にOptionとResultが好まれます。というのもAPIのユーザーの 裁量次第でパニックやアボートさせることも可能だからです。パニックはスレッドの正常処理を 停止し、スタックを巻き戻し、全ての関数が即座にリターンしたかのようにデストラクタ を呼び出します。

バージョン1.0以降のRustはパニック時に２種類の対処法を用いるようになりました。 大昔、Rustは今よりもErlangによく似ていました。Erlangと同様、Rustには軽量のタスク が存在し、タスクが続行不可能な状態に陥った際にはタスクが自分自身をパニックによって killすることを意図して設計されていました。JavaやC++の例外と違い、パニックはいかなる 場合においても捕捉することはできませんでした。パニックを捕捉できるのはタスクの オーナーのみであり、その時点で適切にハンドリングされるか、そのタスク (訳注: オーナーとなるタスク)自体がパニックするかのどちらかでした。

この一連の流れの中では、タスクのデスクトラクタが呼ばれなかった場合にメモリ及び その他のシステムリソースがリークを起こす可能性があったため、巻き戻しが重要でした。 タスクは通常の実行中にも死ぬ可能性があると想定されていたため、Rustのこういった 特徴は長期間実行されるシステムを作る上でとても不適切でした。

Rustが現在の形に近づく過程で、より抽象化を少なくしたいという時流に押された スタイルのプログラミングが確立していき、その過程で軽量のタスクは重量級の OSスレッドに駆逐・統一されました （訳注: いわゆるグリーンスレッドとネイティブスレッドの話）。しかしながら Rust1.0の時点ではパニックはその親スレッドによってのみ補足が可能という仕様であった ため、 パニックの補足時にOSのスレッドを丸ごと巻き戻してしまう必要 があったのです！不幸なことにこれはゼロコスト抽象化というRustの思想と 真っ向からぶつかってしまいました。

一応 catch_panic というunstableなAPIが存在し、これによってスレッドをspawn することなくパニックを捕捉することはできます。

訳注: その後 recover -> catch_unwind と変更され、Rust1.9でstableになりました。

とはいえあくまでこれは代替手段として用いることを推奨します。現在のRustの巻き戻し は「巻き戻ししない」ケースに偏った最適化をしています。巻き戻しが発生しないとわかって いれば、プログラムが巻き戻しの準備をするためのランタイムコストも無くなるためです。 結果として、実際にはJavaのような言語よりも巻き戻しのコストは高くなっています。 したがって通常の状況では巻き戻ししないようなプログラムの作成を心がけるべきです。 非常に大きな問題の発生時やプログラミングエラーに対してのみパニックすべきです。

Rustの巻き戻しの取り扱い方針は、他の言語のそれと根本から同等になるように設計されて はいません。したがって他の言語で発生した巻き戻しがRustに波及したり、逆にRustから 多言語に波及したりといった動作は未定義となっています。 FFIの構築時には絶対に全てのパニックを境界部でキャッチしなくてはなりません。 キャッチの結果どのように対処するかはプログラマ次第ですが、とにかく何かを しなくてはなりません。そうしなければ、良くてアプリケーションがクラッシュ・炎上します。 最悪のケースではアプリケーションがクラッシュ・炎上しません。完全にボロボロの状態 のまま走り続けます。

例外安全性

プログラム内では巻き戻しを注意深く使用するべきですが、パニックし得るコードが たくさんあります。もし None をアンラップしたり、境界外のインデックスを指定したり、 0 で除算したりしたら、プログラムはパニックするでしょう。デバッグビルドでは、 全ての算術演算は、オーバーフロー時にパニックします。非常に注意深く、 そしてどのコードを実行するかを厳しくコントロールしない限り、ほとんどすべての コードが巻き戻しをする可能性があり、これに対して準備をする必要があります。

巻き戻しに対して準備が出来ていることは、もっと広いプログラミングの世界において、 しばしば例外安全と呼ばれています。 Rust では、プログラムが関わる可能性のある、 2 つの例外安全のレベルがあります。

• アンセーフなコードでは、メモリ安全性を侵害しないという点において、 例外安全でなければなりません。これを、最小限の例外安全と呼びます。

• 安全なコードでは、プログラムが正しいことを行なうという点において、 例外安全であると良いです。これを最大限の例外安全と呼びます。

Rust の多くの場において事実なのですが、巻き戻しとなると、アンセーフなコードは、 悪い安全なコードに対処する準備をしなければなりません。一時的に健全ではない 状態を生むコードは、パニックによってその状態が使用されないよう、注意深く 扱わなければなりません。通常これは、このような健全でない状態が存在する間、 パニックを起こさないコードのみを確実に実行させることを意味するか、あるいは パニックの際、その状態を片付けるガードを生成することを意味します。 これは必ずしも、パニックが起きているときの状態が、完全に一貫した状態であるということを 意味しません。安全な状態であると保証されていることだけが必要なのです。

ほとんどのアンセーフなコードは葉のようなもの (訳注: それ以上別の関数を呼ぶことが ない) で、それ故に割と簡単に例外安全に出来ます。実行するコードは完全に制御されていて、 そしてほとんどのコードはパニックしません。しかし、アンセーフなコードが 繰り返し呼び出し側のコードを実行している間に、部分的に初期化されていない配列を 扱うことはよくあります。このようなコードは注意深く扱い、例外安全を考える必要があるのです。

Vec::push_all

Vec::push_all は、特殊化なしに、スライスが確実に効率的であることを利用した、 Vec を伸ばす一時的なハックです。これは単純な実装です。

impl<T: Clone> Vec<T> {
    fn push_all(&mut self, to_push: &[T]) {
        self.reserve(to_push.len());
        unsafe {
            // 今さっき reserve をしたので、オーバーフローするはずがありません
            self.set_len(self.len() + to_push.len());

            for (i, x) in to_push.iter().enumerate() {
                self.ptr().offset(i as isize).write(x.clone());
            }
        }
    }
}

絶対にキャパシティがあると分かっている Vec の capacity と len の余分なチェックを 回避するため、 push を使用していません。論理は完全に正しいです。但し、 このコードに微妙な問題が含まれていることを除く。すなわち、このコードは例外安全 ではないのです! set_len と offset と write は全部問題ありません。 clone は、 我々が見落としていたパニックの起爆装置です。

Clone は全く制御不能で、全く自由にパニックしてしまいます。もしパニックしてしまえば、 この関数は、 Vec の長さが大きすぎる値に設定されたまま、早期に終了してしまいます。 もし Vec が読み出されたりドロップされたりすると、未初期化のメモリが読み出されて しまいます!

この場合、修正は割と簡単です。もし本当に、クローンした値がドロップされたと いうことを保証したいのなら、全てのループのイテレーションにおいて、 len を 設定することが出来ます。もし単に、未初期化のメモリが読まれないようにしたいのなら、 ループの後に len を設定することが出来ます。

BinaryHeap::sift_up

ヒープにおけるアップヒープは Vec を伸ばすことよりちょっと複雑です。擬似コードはこんな感じです。

bubble_up(heap, index):
    while index != 0 && heap[index] < heap[parent(index)]:
        heap.swap(index, parent(index))
        index = parent(index)

このコードを Rust に直訳するのは全く問題ありません。ですが、嫌になるようなパフォーマンス です。すなわち、 self の要素が無駄に交換され続けます。それならむしろ、以下のコードの方が 良いでしょう。

bubble_up(heap, index):
    let elem = heap[index]
    while index != 0 && elem < heap[parent(index)]:
        heap[index] = heap[parent(index)]
        index = parent(index)
    heap[index] = elem

このコードでは確実に、それぞれの要素ができるだけ少ない回数でコピーされます (実は一般的に、要素を 2 回コピーすることが必要なのです) 。しかし、これによって、 いくつか例外安全性の問題が露見しました! 毎回、ある値に対する 2 つのコピーが 存在します。もしこの関数内でパニックしたら、何かが 2 回ドロップされてしまいます。 残念ながら、このコードに関しても、完全にコントロールすることは出来ません。 比較がユーザ定義されているのです!

Vec とは違い、これを直すのは簡単ではありません。一つの選択肢として、ユーザ定義の コードとアンセーフなコードを、 2 つの段階に分割することです。

bubble_up(heap, index):
    let end_index = index;
    while end_index != 0 && heap[end_index] < heap[parent(end_index)]:
        end_index = parent(end_index)

    let elem = heap[index]
    while index != end_index:
        heap[index] = heap[parent(index)]
        index = parent(index)
    heap[index] = elem

もしユーザ定義のコードでトラブっても、もう問題ありません。なぜなら、 ヒープの状態にはまだ触れていないからです。ヒープを実際に弄るとき、 信用しているデータや関数のみを扱っています。ですからもうパニックの心配は ありません。

多分、この設計を嬉しく思わないでしょう。明らかに騙している! そして複雑な ヒープのトラバーサルを 2 回 行わなければならない! 分かった、我慢しよう。 信用していないコードやアンセーフなコードを本気で混ぜてみよう。

もし Rust に Java のような try と finally があったら、コードは こんな感じだったでしょう。

bubble_up(heap, index):
    let elem = heap[index]
    try:
        while index != 0 && element < heap[parent(index)]:
            heap[index] = heap[parent(index)]
            index = parent(index)
    finally:
        heap[index] = elem

基本的な考えは単純です。すなわち、もし比較においてパニックしたのなら、単に要素を 論理的に未初期化のインデックスの位置に保存し、脱出します。このヒープを観察する誰もが、 潜在的には一貫性のないヒープを目にするでしょうが、少なくともこのコードは二重ドロップを 起こしません! もしアルゴリズムが通常通り終了すれば、この操作はコードがどのように終了するかに 関わらず、結果を正確に一致させるために実行されます。

悲しいことに、 Rust にはそのような構造が存在しません。ですので、自分たちで退避させなければ ならないようです! これを行なうには、 "finally" の論理を構成するため、デストラクタと共に アルゴリズムの状態を、別の構造体に保存します。パニックしようがしまいが、デストラクタは 実行され、状態を綺麗にします。

struct Hole<'a, T: 'a> {
    data: &'a mut [T],
    /// `elt` は new で生成されたときからドロップまで、常に Some です
    elt: Option<T>,
    pos: usize,
}

impl<'a, T> Hole<'a, T> {
    fn new(data: &'a mut [T], pos: usize) -> Self {
        unsafe {
            let elt = ptr::read(&data[pos]);
            Hole {
                data: data,
                elt: Some(elt),
                pos: pos,
            }
        }
    }

    fn pos(&self) -> usize { self.pos }

    fn removed(&self) -> &T { self.elt.as_ref().unwrap() }

    unsafe fn get(&self, index: usize) -> &T { &self.data[index] }

    unsafe fn move_to(&mut self, index: usize) {
        let index_ptr: *const _ = &self.data[index];
        let hole_ptr = &mut self.data[self.pos];
        ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1);
        self.pos = index;
    }
}

impl<'a, T> Drop for Hole<'a, T> {
    fn drop(&mut self) {
        // 穴を再び埋めます
        unsafe {
            let pos = self.pos;
            ptr::write(&mut self.data[pos], self.elt.take().unwrap());
        }
    }
}

impl<T: Ord> BinaryHeap<T> {
    fn sift_up(&mut self, pos: usize) {
        unsafe {
            // `pos` にある値を受け取り、穴を作ります。
            let mut hole = Hole::new(&mut self.data, pos);

            while hole.pos() != 0 {
                let parent = parent(hole.pos());
                if hole.removed() <= hole.get(parent) { break }
                hole.move_to(parent);
            }
            // 状況に関わらず、穴はここで埋まります。パニックしてもしなくても!
        }
    }
}

ポイゾニング

全てのアンセーフな型は最低限の例外安全性を満たしていることが必要ですが、全ての アンセーフな型が最大限の例外安全性を満たしている必要はありません。 仮に型自体が満たしていたとしても、実装が別の意味を暗黙に付与してしまう場合も あります。例えば整数型は間違いなく例外安全ですが、その(訳注: 最大限の例外安全性 を担保する)セマンティクスを独自に持つわけではないため、整数をアップデートする 際にパニックを起こすと、プログラムが一貫性のない状態に陥る可能性があります。

これは通常は問題になることはありません。というのも例外を発見した処理は直後に 死ぬためです。例えばVecを別のスレッドに送り、そのスレッドがパニックし、結果として Vecが奇妙な状態に陥ったとしても、ドロップされて永久に闇の彼方に葬られてしまうためです。 とはいえ型によってはパニックの境界をまたいでくる場合もあります。

こういった型は、パニックに直面した際に、意図的に自分自身をポイゾンする可能性があり ます。ポイゾニング自体は特に何か別の事態を引き起こすわけではありません。一般的に 通常の手続きの継続を止めるべきであることを表しています。よく知られた例として 標準ライブラリのMutex型があります。この型は対応するMutexGuards(ロックを取得した際に 返るもの)が、パニックによってドロップされた際に自分自身をポイゾンします。以後Mutexをロック しようとするとErrを返すかパニックします。

Mutexのポイゾンは、通常の文脈で語られるRustの安全性とは異なる用途のためのものです。 Mutexを扱うスレッドがロック中にパニックを引き起こした場合、Mutexの中のデータは変更中 であった可能性が高く、一貫性を欠いていたり変更が未完了の状態であったりするため、 そのようなデータを盲目的に扱う危険性に対する安全装置として動作します。 注意しておきたいのはそのような型が適切に実装されていた場合、メモリ安全性は確実 に満たしているという点です。つまるところ、最低限の例外安全性は満たしていなくては ならないということです。

しかしながら、Mutexが例えばBinaryHeapを持っていたとして、その値が実際にはヒープ として要件を満たさなかったような場合、そのデータ構造を利用するプログラムが作成者の 意図通りの挙動をするということは考えにくいです。通常とは異なる振る舞いをする でしょう。とはいえ、十分に注意すればそのような場合でもその値が何かに使える 可能性はあります。安全ではあるのです。ただ、ナンセンスかもしれませんが。

並行性と並列性

言語としての Rust には、本当に、どのように並行性や並列性を実現するかについての 信条がありません。標準ライブラリは、 OS のスレッドやシステムコールのブロックを 公開しています。なぜなら皆これらを持っていて、そして十分統一されているために、 比較的反論の起きないような、これらに対する抽象化を提供できるからです。メッセージパッシング、 グリーンスレッド、そして async の API はすべて、本当に異なっているため、 これらに対するいかなる抽象化においても、バージョン 1.0 に対するコミットを 行ないたくないようなトレードオフを巻き込む傾向にあります。

しかしながら、 Rust の並行性のモデルは比較的簡単に、ライブラリとして、自分自身の並行パラダイムを 設計することができ、そして、自分のコードと同じように、他の人のコードもちゃんと動かすことも出来ます。 必要なのは正しいライフタイムと、必要に応じて Send と Sync で、これですぐに書くことが出来ます。 あるいは... 競合を... 起こさずに... 済みます。

データ競合と競合状態

安全な Rust では、データ競合が存在しないことが保証されています。 データ競合は、以下のように定義されています。

• 2 つ以上のスレッドが並行にメモリ上の場所にアクセスしている
• この内 1 つは書き込み
• この内 1 つは非同期

データ競合は未定義動作を含み、そしてそれ故に安全な Rust で発生させることは不可能です。 データ競合は Rust の所有権システムによってほとんど防がれています。可変参照の エイリアスを生成することは不可能ですから、データ競合を起こすことは不可能です。 内部可変性はこれをもっと複雑にします。これが、 Send トレイトと Sync トレイトが 何故存在するかということの主な理由です (以下を見てください) 。

しかしながら Rust は、一般的な競合状態を防ぎません。

これは根本的に不可能で、そして多分本当に望まれていないものです。ハードウェアは 競合状態を起こし、 OS も競合状態を起こし、コンピュータの他のプログラムも競合状態を起こし、 そして世界中にある全てのプログラムも競合状態を起こします。どんなシステムでも、 全ての競合状態を防げると喧伝しているようなものは、単に間違っているだけではなく、 本当に使いづらいものとなるでしょう。

ですから、安全な Rust のプログラムがデッドロックに陥ったり、正しくない同期によって何か 馬鹿げたことを行なっても、これは全く "問題ない" のです。明らかにそのようなプログラムは、 本当に良くないです。ですが、 Rust は今までのところ、プログラマに我慢してもらうしか出来ないのです。 それでも Rust のプログラムだけでは、競合状態において、メモリ安全性を侵害することは出来ません。 何か他のアンセーフなコードと組み合わせることだけでしか、実際に競合状態において、 メモリ安全性を侵害することが出来ないのです。例:

#![allow(unused)]
fn main() {
use std::thread;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Arc;

let data = vec![1, 2, 3, 4];
// Arc にすることで、 他のスレッドより前に完全に実行が終了しても、 AtomicUsize が
// 保存されているメモリが、他のスレッドがインクリメントするために存在し続けます。
// これ無しにはコンパイルできません。なぜなら、 thread::spawn が
// ライフタイムを必要とするからです!
let idx = Arc::new(AtomicUsize::new(0));
let other_idx = idx.clone();

// `move` によって other_idx が値でキャプチャされ、このスレッドにムーブされます
thread::spawn(move || {
    // idx を変更しても大丈夫です。この値はアトミックだからです。
    // ですからデータ競合は起こりません。
    other_idx.fetch_add(10, Ordering::SeqCst);
});

// アトミックなものからロードした値を使用してインデックス指定をします。これは安全です。
// なぜなら、アトミックメモリから読み込み、その値のコピーを Vec のインデックス実装に
// 渡すからです。このインデックス指定では、正しく境界チェックが行なわれ、そして途中で
// 値が変わることはありません。しかし、もしスポーンされたスレッドが、なんとかして実行前に
// インクリメントするならば、このプログラムはパニックするかもしれません。
// 正しいプログラムの実行 (パニックすることはほとんど正しくありません) は、スレッドの
// 実行順序に依存するため、競合状態となります。
println!("{}", data[idx.load(Ordering::SeqCst)]);
}

#![allow(unused)]
fn main() {
use std::thread;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Arc;

let data = vec![1, 2, 3, 4];

let idx = Arc::new(AtomicUsize::new(0));
let other_idx = idx.clone();

// `move` によって other_idx が値でキャプチャされ、このスレッドにムーブされます
thread::spawn(move || {
    // idx を変更しても大丈夫です。この値はアトミックだからです。
    // ですからデータ競合起こりません。
    other_idx.fetch_add(10, Ordering::SeqCst);
});

if idx.load(Ordering::SeqCst) < data.len() {
    unsafe {
        // 境界チェックを行なった後、間違えて idx をロードしてしまいます。
        // この値は変わってしまったかもしれません。これは競合状態で、*危険*です。
        // なぜなら `unsafe` である `get_unchecked` を行なったからです。
        println!("{}", data.get_unchecked(idx.load(Ordering::SeqCst)));
    }
}
}

Send and Sync

Not everything obeys inherited mutability, though. Some types allow you to multiply alias a location in memory while mutating it. Unless these types use synchronization to manage this access, they are absolutely not thread safe. Rust captures this through the Send and Sync traits.

• A type is Send if it is safe to send it to another thread.
• A type is Sync if it is safe to share between threads (&T is Send).

Send and Sync are fundamental to Rust's concurrency story. As such, a substantial amount of special tooling exists to make them work right. First and foremost, they're unsafe traits. This means that they are unsafe to implement, and other unsafe code can assume that they are correctly implemented. Since they're marker traits (they have no associated items like methods), correctly implemented simply means that they have the intrinsic properties an implementor should have. Incorrectly implementing Send or Sync can cause Undefined Behavior.

Send and Sync are also automatically derived traits. This means that, unlike every other trait, if a type is composed entirely of Send or Sync types, then it is Send or Sync. Almost all primitives are Send and Sync, and as a consequence pretty much all types you'll ever interact with are Send and Sync.

Major exceptions include:

• raw pointers are neither Send nor Sync (because they have no safety guards).
• UnsafeCell isn't Sync (and therefore Cell and RefCell aren't).
• Rc isn't Send or Sync (because the refcount is shared and unsynchronized).

Rc and UnsafeCell are very fundamentally not thread-safe: they enable unsynchronized shared mutable state. However raw pointers are, strictly speaking, marked as thread-unsafe as more of a lint. Doing anything useful with a raw pointer requires dereferencing it, which is already unsafe. In that sense, one could argue that it would be "fine" for them to be marked as thread safe.

However it's important that they aren't thread safe to prevent types that contain them from being automatically marked as thread safe. These types have non-trivial untracked ownership, and it's unlikely that their author was necessarily thinking hard about thread safety. In the case of Rc, we have a nice example of a type that contains a *mut that is definitely not thread safe.

Types that aren't automatically derived can simply implement them if desired:

#![allow(unused)]
fn main() {
struct MyBox(*mut u8);

unsafe impl Send for MyBox {}
unsafe impl Sync for MyBox {}
}

In the incredibly rare case that a type is inappropriately automatically derived to be Send or Sync, then one can also unimplement Send and Sync:

#![allow(unused)]
#![feature(optin_builtin_traits)]

fn main() {
// I have some magic semantics for some synchronization primitive!
struct SpecialThreadToken(u8);

impl !Send for SpecialThreadToken {}
impl !Sync for SpecialThreadToken {}
}

Note that in and of itself it is impossible to incorrectly derive Send and Sync. Only types that are ascribed special meaning by other unsafe code can possible cause trouble by being incorrectly Send or Sync.

Most uses of raw pointers should be encapsulated behind a sufficient abstraction that Send and Sync can be derived. For instance all of Rust's standard collections are Send and Sync (when they contain Send and Sync types) in spite of their pervasive use of raw pointers to manage allocations and complex ownership. Similarly, most iterators into these collections are Send and Sync because they largely behave like an & or &mut into the collection.

TODO: better explain what can or can't be Send or Sync. Sufficient to appeal only to data races?

Atomics

Rust pretty blatantly just inherits C11's memory model for atomics. This is not due to this model being particularly excellent or easy to understand. Indeed, this model is quite complex and known to have several flaws. Rather, it is a pragmatic concession to the fact that everyone is pretty bad at modeling atomics. At very least, we can benefit from existing tooling and research around C.

Trying to fully explain the model in this book is fairly hopeless. It's defined in terms of madness-inducing causality graphs that require a full book to properly understand in a practical way. If you want all the nitty-gritty details, you should check out C's specification (Section 7.17). Still, we'll try to cover the basics and some of the problems Rust developers face.

The C11 memory model is fundamentally about trying to bridge the gap between the semantics we want, the optimizations compilers want, and the inconsistent chaos our hardware wants. We would like to just write programs and have them do exactly what we said but, you know, fast. Wouldn't that be great?

Compiler Reordering

Compilers fundamentally want to be able to do all sorts of complicated transformations to reduce data dependencies and eliminate dead code. In particular, they may radically change the actual order of events, or make events never occur! If we write something like

x = 1;
y = 3;
x = 2;

The compiler may conclude that it would be best if your program did

x = 2;
y = 3;

This has inverted the order of events and completely eliminated one event. From a single-threaded perspective this is completely unobservable: after all the statements have executed we are in exactly the same state. But if our program is multi-threaded, we may have been relying on x to actually be assigned to 1 before y was assigned. We would like the compiler to be able to make these kinds of optimizations, because they can seriously improve performance. On the other hand, we'd also like to be able to depend on our program doing the thing we said.

Hardware Reordering

On the other hand, even if the compiler totally understood what we wanted and respected our wishes, our hardware might instead get us in trouble. Trouble comes from CPUs in the form of memory hierarchies. There is indeed a global shared memory space somewhere in your hardware, but from the perspective of each CPU core it is so very far away and so very slow. Each CPU would rather work with its local cache of the data and only go through all the anguish of talking to shared memory only when it doesn't actually have that memory in cache.

After all, that's the whole point of the cache, right? If every read from the cache had to run back to shared memory to double check that it hadn't changed, what would the point be? The end result is that the hardware doesn't guarantee that events that occur in the same order on one thread, occur in the same order on another thread. To guarantee this, we must issue special instructions to the CPU telling it to be a bit less smart.

For instance, say we convince the compiler to emit this logic:

initial state: x = 0, y = 1

THREAD 1        THREAD2
y = 3;          if x == 1 {
x = 1;              y *= 2;
                }

Ideally this program has 2 possible final states:

• y = 3: (thread 2 did the check before thread 1 completed)
• y = 6: (thread 2 did the check after thread 1 completed)

However there's a third potential state that the hardware enables:

• y = 2: (thread 2 saw x = 1, but not y = 3, and then overwrote y = 3)

It's worth noting that different kinds of CPU provide different guarantees. It is common to separate hardware into two categories: strongly-ordered and weakly- ordered. Most notably x86/64 provides strong ordering guarantees, while ARM provides weak ordering guarantees. This has two consequences for concurrent programming:

• Asking for stronger guarantees on strongly-ordered hardware may be cheap or even free because they already provide strong guarantees unconditionally. Weaker guarantees may only yield performance wins on weakly-ordered hardware.

• Asking for guarantees that are too weak on strongly-ordered hardware is more likely to happen to work, even though your program is strictly incorrect. If possible, concurrent algorithms should be tested on weakly-ordered hardware.

Data Accesses

The C11 memory model attempts to bridge the gap by allowing us to talk about the causality of our program. Generally, this is by establishing a happens before relationship between parts of the program and the threads that are running them. This gives the hardware and compiler room to optimize the program more aggressively where a strict happens-before relationship isn't established, but forces them to be more careful where one is established. The way we communicate these relationships are through data accesses and atomic accesses.

Data accesses are the bread-and-butter of the programming world. They are fundamentally unsynchronized and compilers are free to aggressively optimize them. In particular, data accesses are free to be reordered by the compiler on the assumption that the program is single-threaded. The hardware is also free to propagate the changes made in data accesses to other threads as lazily and inconsistently as it wants. Most critically, data accesses are how data races happen. Data accesses are very friendly to the hardware and compiler, but as we've seen they offer awful semantics to try to write synchronized code with. Actually, that's too weak.

It is literally impossible to write correct synchronized code using only data accesses.

Atomic accesses are how we tell the hardware and compiler that our program is multi-threaded. Each atomic access can be marked with an ordering that specifies what kind of relationship it establishes with other accesses. In practice, this boils down to telling the compiler and hardware certain things they can't do. For the compiler, this largely revolves around re-ordering of instructions. For the hardware, this largely revolves around how writes are propagated to other threads. The set of orderings Rust exposes are:

• Sequentially Consistent (SeqCst)
• Release
• Acquire
• Relaxed

(Note: We explicitly do not expose the C11 consume ordering)

TODO: negative reasoning vs positive reasoning? TODO: "can't forget to synchronize"

Sequentially Consistent

Sequentially Consistent is the most powerful of all, implying the restrictions of all other orderings. Intuitively, a sequentially consistent operation cannot be reordered: all accesses on one thread that happen before and after a SeqCst access stay before and after it. A data-race-free program that uses only sequentially consistent atomics and data accesses has the very nice property that there is a single global execution of the program's instructions that all threads agree on. This execution is also particularly nice to reason about: it's just an interleaving of each thread's individual executions. This does not hold if you start using the weaker atomic orderings.

The relative developer-friendliness of sequential consistency doesn't come for free. Even on strongly-ordered platforms sequential consistency involves emitting memory fences.

In practice, sequential consistency is rarely necessary for program correctness. However sequential consistency is definitely the right choice if you're not confident about the other memory orders. Having your program run a bit slower than it needs to is certainly better than it running incorrectly! It's also mechanically trivial to downgrade atomic operations to have a weaker consistency later on. Just change SeqCst to Relaxed and you're done! Of course, proving that this transformation is correct is a whole other matter.

Acquire-Release

Acquire and Release are largely intended to be paired. Their names hint at their use case: they're perfectly suited for acquiring and releasing locks, and ensuring that critical sections don't overlap.

Intuitively, an acquire access ensures that every access after it stays after it. However operations that occur before an acquire are free to be reordered to occur after it. Similarly, a release access ensures that every access before it stays before it. However operations that occur after a release are free to be reordered to occur before it.

When thread A releases a location in memory and then thread B subsequently acquires the same location in memory, causality is established. Every write that happened before A's release will be observed by B after its release. However no causality is established with any other threads. Similarly, no causality is established if A and B access different locations in memory.

Basic use of release-acquire is therefore simple: you acquire a location of memory to begin the critical section, and then release that location to end it. For instance, a simple spinlock might look like:

use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};
use std::thread;

fn main() {
    let lock = Arc::new(AtomicBool::new(false)); // value answers "am I locked?"

    // ... distribute lock to threads somehow ...

    // Try to acquire the lock by setting it to true
    while lock.compare_and_swap(false, true, Ordering::Acquire) { }
    // broke out of the loop, so we successfully acquired the lock!

    // ... scary data accesses ...

    // ok we're done, release the lock
    lock.store(false, Ordering::Release);
}

On strongly-ordered platforms most accesses have release or acquire semantics, making release and acquire often totally free. This is not the case on weakly-ordered platforms.

Relaxed

Relaxed accesses are the absolute weakest. They can be freely re-ordered and provide no happens-before relationship. Still, relaxed operations are still atomic. That is, they don't count as data accesses and any read-modify-write operations done to them occur atomically. Relaxed operations are appropriate for things that you definitely want to happen, but don't particularly otherwise care about. For instance, incrementing a counter can be safely done by multiple threads using a relaxed fetch_add if you're not using the counter to synchronize any other accesses.

There's rarely a benefit in making an operation relaxed on strongly-ordered platforms, since they usually provide release-acquire semantics anyway. However relaxed operations can be cheaper on weakly-ordered platforms.

例: Vec の実装

全てをまとめるために、最初から std::Vec を書くことにします。 アンセーフなコードを書くための最良のツールは全部アンステーブルなため、 このプロジェクトは nightly でしか動作しません (Rust 1.9.0 現在) 。 アロケータの API を除いて、使用するアンステーブルなもののほとんどは、 今日の形態に似た状態で、安定版となると予測しています。

しかし、なるべくアンステーブルなコードを書くことを避けようと思います。 特に、いかなる intrinsic も使わないことにします。これらはコードを ちょっと改善したり、効率を良くします。これらを使わない理由は、 intrinsic が永遠にアンステーブルだからです。もっとも、多くの intrinsic は実際に 別の場において安定版になっていますが (std::ptr や std::mem は、 多くの intrinsic を含んでいます) 。

究極には、これは、ここで実装する Vec では可能な最適化を全部は 利用しないということを意味します。だからといって、全く単純という訳ではありません。 その問題によって何か本当に利益を得ることがないとしても、基本的で 細かいところに突っ込んでいきます。

先に進みたいですよね? それでは行きましょう。

レイアウト

まず、構造体のレイアウトを考える必要があります。 Vec は 3 つの部品を 持っています。アロケーションへのポインタと、アロケーションの大きさ、 そして初期化された要素の数です。

愚直に考えると、これは以下の設計で良いということになります。

pub struct Vec<T> {
    ptr: *mut T,
    cap: usize,
    len: usize,
}
fn main() {}

そして実際に、このコードはコンパイルできます。残念ながら、この設計は正しくありません。 まず、コンパイラはあまりに厳密すぎる変性を与えることになります。ですから &Vec<&'a str> が予期されているところで &Vec<&'static str> を使う事が 出来ません。もっと重要なことに、この設計によって正しくない所有権の情報が ドロップチェッカに渡されてしまいます。型 T のいかなる値も所有していないと、 ドロップチェッカが保守的に判断してしまうからです。変性やドロップチェックに 関する全ての詳細は、所有権とライフタイムの章を参照してください。

所有権の章で見てきたように、所有しているアロケーションに対する生ポインタを持つ場合、 *mut T の代わりに Unique<T> を使用するべきです。 Unique はアンステーブルなため、 可能なら使いませんが。

繰り返しになりますが、 Unique は生ポインタのラッパで、以下のことを宣言 します。

• T に対して変性
• 型 T の値を所有する可能性がある (ドロップチェックのため)
• T が Send/Sync を実装している場合、継承される
• *mut T に参照外しをする (つまりコード内では専ら *mut のように振る舞う)
• ポインタはヌルにはならない (つまり Option<Vec<T>> はヌルポインタ最適化される)

上記の最後以外の項は、安定版の Rust で実装可能です。

use std::marker::PhantomData;
use std::ops::Deref;
use std::mem;

struct Unique<T> {
    ptr: *const T,              // 変性のために *const です
    _marker: PhantomData<T>,    // ドロップチェッカ対策
}

// Send と Sync を継承することは安全です。なぜならこのデータの
// Unique を所有しているからです。 Unique<T> は "単なる" T のようなものです。
unsafe impl<T: Send> Send for Unique<T> {}
unsafe impl<T: Sync> Sync for Unique<T> {}

impl<T> Unique<T> {
    pub fn new(ptr: *mut T) -> Self {
        Unique { ptr: ptr, _marker: PhantomData }
    }
}

impl<T> Deref for Unique<T> {
    type Target = *mut T;
    fn deref(&self) -> &*mut T {
        // 参照も受け取っている時に、 *const を *mut に
        // キャストする方法はありません。
        // これらは全て "ただのポインタ" ですのでトランスミュートします。
        unsafe { mem::transmute(&self.ptr) }
    }
}
fn main() {}

残念ながら、値が非 0 であると述べるメカニズムはアンステーブルで、すぐには 安定版はならないでしょう。ですから単に std の Unique を使うことにします。

#![feature(unique)]

use std::ptr::{Unique, self};

pub struct Vec<T> {
    ptr: Unique<T>,
    cap: usize,
    len: usize,
}

fn main() {}

もしヌルポインタ最適化を気にしないなら、安定版のコードを使用することもできます。 しかしながら、残りのコードでは、最適化を有効にするような設計していきます。 特に、 Unique::new を呼ぶことはアンセーフです。なぜなら null を中に突っ込む ことは、未定義動作を引き起こしてしまうからです。安定版のコードの new はアンセーフに する必要はありません。中身についての興味深い保証をしないからです。

メモリのアロケーティング

Unique を使用することで、 Vec の重要な機能に関して (そして実に std の全ての コレクションにおいて) 問題が発生します。すなわち、空の Vec は実際に、 何もアロケートしていないのです。ですからもしアロケート出来ないだけではなく、 ptr にヌルポインタを代入出来ないとしたら、 Vec::new で何をすれば いいのでしょうか? そうだ、単純にそこに何か他のゴミを突っ込みましょう!

これは全く問題ありません。なぜなら、 cap == 0 が既に、アロケーションが ないことを示す番兵となっているからです。もはやこれを特別扱いする必要も ありません。なぜならほとんどすべてのコードで、結局は cap > len か len > 0 を 通常確かめる必要があるからです。伝統的に Rust では、 0x01 を突っ込んでいます。 標準ライブラリでは実際にこれを alloc::heap::EMPTY として公開しています。 null を使ってしまうとコンパイラが悪さをしてしまうけれども、実際の アロケーションが存在しないために heap::EMPTY を使用したい箇所がかなり 多く存在します。

それでも全ての heap の API は、 heap_api フィーチャの下で、 全くアンステーブルです。自ら heap::EMPTY を定義してしまうことも 出来るでしょうが、結局 heap の他の API を使いたくなるため、単にその API を 依存関係に追加しましょう。

こうなります:

#![feature(alloc, heap_api)]

use std::mem;

use alloc::heap::EMPTY;

impl<T> Vec<T> {
    fn new() -> Self {
        // まだ ZST を扱う準備が出来ていません
        assert!(mem::size_of::<T>() != 0, "We're not ready to handle ZSTs");
        unsafe {
            // EMPTY を欲しい実際のポインタ型にキャストする必要があります。
            // 推論してもらいましょう。
            Vec { ptr: Unique::new(heap::EMPTY as *mut _), len: 0, cap: 0 }
        }
    }
}

コードの中に、assert を入れました。サイズが 0 の型は、コード全体において 何か特別な処理をする必要があり、この問題を今は後回しにしたいためです。 この assert がないと、コードの下書きにおいて、なにか非常にまずいことを 起こしてしまいます。

次に、本当にスペースがほしいときに、実際に何をすればいいかを考える 必要があります。そのためには、 heap の他の API を使用する必要があります。 基本的にこれらによって、 Rust のアロケータ (デフォルトでは jemalloc) と 対話できるようになります。

また、メモリ不足 (out-of-memory, OOM) の状態に対処する方法も必要です。 標準ライブラリでは、単に abort intrinsic を呼びます。これは単純に 不正な命令を呼び出して、プログラムをクラッシュさせます。なぜパニックではなく アボートさせるかというと、巻き戻しはアロケーションを起こす事があるため、 アロケータが "なあ、もうメモリがないぜ" と帰ってきたときに巻き戻しを行なうのは まずいからです。

もちろん、通常ならほとんどのプラットフォームにおいて、実際にメモリ不足に 陥ることはないため、これはちょっと馬鹿げています。オペレーティングシステムは、 何らかの理由でアプリケーションが全てのメモリを使用しているなら、 そのアプリケーションを他の手段によって多分 kill するでしょう。 OOM になってしまう、もっともあり得る場合というのは単に、信じられないくらいの メモリ量をいっぺんに確保しようとする場合です (例: 理論上のアドレス空間の半分) 。 ですからパニックしても多分問題なく、何も悪いことは起きません。それでも、 なるべく標準ライブラリに似せるため、ここでは単にプログラム全体を kill します。

intrinsic を使いたくないと述べました。ですので、 std で行なっていることと、 全く同じことをすることは出来ません。代わりに、 std::process::exit を 適当な値と共に呼び出します。

#![allow(unused)]
fn main() {
fn oom() {
    ::std::process::exit(-9999);
}
}

よし、これで Vec の伸長のコードを書くことが出来ます。欲しい ロジックは大体以下のようなものです。

if cap == 0:
    allocate()
    cap = 1
else:
    reallocate()
    cap *= 2

しかし、 Rust が唯一サポートしているアロケータ API は本当に低レベルな ものですので、追加の作業がかなり必要です。また、本当に大きいアロケーションや、 空のアロケーションの際に起こる、特別な状況に対してガードする必要もあります。

特に ptr::offset は、沢山の問題を引き起こします。なぜならこれは、 LLVM の、 GEP インバウンド命令のセマンティクスを持っているからです。もしあなたが 幸運にも、この命令に対処したことがない場合、こちらが GEP に関する 基本的な事柄です: エイリアス分析、エイリアス分析、エイリアス分析。 コンパイラが最適化をする際、データの依存関係や、エイリアシングを 推論できるということは、本当に重要なのです。

単純な例として、以下のコード片を考えてみましょう。

#![allow(unused)]
fn main() {
let x = &mut 0;
let y = &mut 0;
*x *= 7;
*y *= 3;
}

もしコンパイラが、 x と y がメモリ上の別の場所をそれぞれ指していると 証明できるのなら、理論的には、これらの 2 つの命令は並列に行なうことが 可能です (例: 異なるレジスタにロードして、個別に操作する) 。 しかしながら、コンパイラは一般的にこれをすることが出来ません。 なぜなら、 x と y がメモリ上の同一の場所を指しているのなら、操作を 同じ値に対して行なわなければならず、単に最後、統合することは不可能だからです。

GEP インバウンドを使用する際、実行しようとしているオフセットは、 単一の "アロケートされた" エンティティの境界内に収まると、 LLVM に はっきりと伝えることになります。 LLVM を使うことによる究極の利点は、 2 つのポインタが異なるオブジェクトを指すと分かっている時、これらの ポインタの全てのオフセットも、エイリアスではないということが 分かるということです (なぜならメモリ上のどこかランダムな場所を 指さないと分かっているからです) 。 LLVM は、 GEP オフセットを 扱うために激しく最適化されていて、インバウンドオフセットは 全ての中で最良のものです。ですからなるべくこれらを使うことが重要です。

これが、 GEP についてです。ではこれが、どのような問題を引き起こすのでしょうか?

第一に、配列のインデックス指定では符号なし整数を指定しますが、 GEP (そして結果として ptr::offset も) では符号付き整数を受け取ります。 これはつまり、配列のインデックス指定では有効であろう値の半分が、 GEP では オーバーフローしてしまい、実際に間違った方向に進んでしまうのです! ですから 全てのアロケーションを isize::MAX 個の要素に制限しなければなりません。 これは実際には、バイトサイズのオブジェクトに関してのみ、心配する必要があります。 なぜなら、例えば isize::MAX 個以上の u16 などでは、明らかにシステムのメモリを 使い果たしてしまうでしょう。しかし、何らかの、 isize::MAX 個以下のオブジェクトを 持つ配列をバイト群と再解釈するような、微妙なコーナーケースを避けるため、 std では全てのアロケーションを isize::MAX バイトに制限しています。

Rust が現在サポートしている 64 ビットのターゲットでは、 恣意的に、 64 ビットの アドレス空間全体よりも遥かに少なく制限されています (現代の x64 プラットフォームでは、 48 ビットのアドレスしか使用可能ではありません) 。ですから単純に、最初にメモリ不足に なると考えて良いです。しかし 32 ビットのターゲットでは、特に追加のアドレス空間 を使用する拡張に対して (PAE x86 や x32) 、理論的には isize::MAX バイト以上の メモリをアロケートしてしまうことが可能です。

しかしながら、これはチュートリアルですので、ここではベストを尽くしません。 単に、プラットフォーム特有の cfg 等を使用するのではなく、状況に関わりなく チェックします。

心配しなければならない他のコーナーケースは、空のアロケーションです。 空のアロケーションには 2 種類あります。 全ての T における cap = 0 と、 サイズが 0 の型における cap > 0 です。

これらは結局、 LLVM が意味する "アロケートされた" 状態ですので、扱いにくいです。 LLVM におけるアロケーションの概念は、我々が普段使う概念よりも遥かに抽象的です。 LLVM は異なる言語のセマンティクスや、カスタムアロケータを扱う必要があるため、 アロケーションに深入り出来ないのです。その代わり、アロケーションの 背後にある主要な考えは "他のものと重ならない" という事です。つまり、 ヒープアロケーションやスタックアロケーション、そしてグローバルな アロケーションは、ランダムに重なることはありません。ええ、これはエイリアス分析 についてです。ですから、 Rust は一貫性を保つ限り、アロケーションの概念に関しては 技術的に、ちょっと高速に、ちょっと緩く、行なうことが出来ます。

空のアロケーションの場合について戻りましょう。ジェネリックなコードの結果、 0 の オフセットが欲しい場合がいくつかあります。そうすると問題はこうなります。すなわち、 これを行なうことは、一貫性があるのでしょうか? 例えばサイズが 0 の型の場合、 任意の要素数による GEP インバウンドオフセットを行なうことは、実に一貫性が あると結論付けました。これは実行時には no-op です。なぜなら、全ての要素は スペースを消費せず、そして 0x01 に無限の数の、サイズが 0 の型がアロケート されているとしても問題ないからです。どのアロケータも、絶対にそのアドレスには アロケートしません。なぜなら、アロケータは 0x00 にはアロケートせず、 一般的にバイト以上のある最小のアラインメントにアロケートするからです。 また一般的には、メモリの最初のページ全体は、アロケートされることに対し 結局保護されています (多くのプロットフォームでは 4k 全体) 。

しかしながら、サイズが正の型についてはどうでしょうか? これはちょっと トリッキーです。一般には、 0 のオフセットでは LLVM には何の情報も 行き渡らないと論ずる事が出来ます。すなわち、アドレスの前か後ろかの どちらかに要素があるけれども、どっちなのかはわからないということです。 しかし、これによって悪いことが起きると保守的に見なすことを選びました。 ですからこれらの場合に対しては、明示的にガードします。

ふー

よし、ナンセンスな物を退けましたので、実際にメモリをアロケートしてみましょう。

fn grow(&mut self) {
    // これは本当に繊細なので、全部アンセーフにしましょう
    unsafe {
        // 現在の API では、大きさとアラインメントを手動で指定する必要があります。
        let align = mem::align_of::<T>();
        let elem_size = mem::size_of::<T>();

        let (new_cap, ptr) = if self.cap == 0 {
            let ptr = heap::allocate(elem_size, align);
            (1, ptr)
        } else {
            // 不変条件ですので、 `self.cap < isize::MAX` と見なすことが出来ます。
            // ですからチェックする必要はありません。
            let new_cap = self.cap * 2;
            // 同様に、前にアロケートしたのでオーバーフローすることはありません
            let old_num_bytes = self.cap * elem_size;

            // 実際のキャパシティの大きさに関わらず、新しいアロケーションが
            // `isize::MAX` を超過しないか確認します。これは、必要なチェックである、
            // `new_cap <= isize::MAX` と `new_num_bytes <= usize::MAX` を
            // 組み合わせています。もっとも、例えば 32ビットプラットフォーム上では、
            // i16 の単一の Vec で、アドレス空間の 2/3 をアロケートすることは
            // できなくなっていますが。
            // Alas, poor Yorick -- I knew him, Horatio.
            // (訳注: シェイクスピアに登場する、ハムレットのセリフです)
            assert!(old_num_bytes <= (::std::isize::MAX as usize) / 2,
                    "capacity overflow");

            let new_num_bytes = old_num_bytes * 2;
            let ptr = heap::reallocate(*self.ptr as *mut _,
                                        old_num_bytes,
                                        new_num_bytes,
                                        align);
            (new_cap, ptr)
        };

        // もしアロケートや、リアロケートに失敗すると、 `null` が返ってきます
        if ptr.is_null() { oom(); }

        self.ptr = Unique::new(ptr as *mut _);
        self.cap = new_cap;
    }
}

ここでは特にトリッキーなことはしていません。単にサイズとアラインメントを計算し、 掛け算を注意深くチェックしています。

プッシュとポップ

よし、初期化出来ました。アロケート出来ます。それでは実際にいくつか機能を 実装しましょう! まず push 。必要なことは、 grow をするべきか確認し、 状況によらず、次のインデックスの場所に書き込み、そして長さをインクリメント します。

書き込みの際、書き込みたいメモリの値を評価しないよう、注意深く行なう必要が あるます。最悪、そのメモリはアロケータが全く初期化していません。良くても、 ポップした古い値のビットが残っています。いずれにせよ、そのメモリをインデックス指定し、 単に参照外しをするわけにはいきません。なぜならそれによって、メモリ上の値を、 T の 正しいインスタンスとして評価してしまうからです。もっと悪いことに、 foo[idx] = x によって、 foo[idx] の古い値に対して drop を呼ぼうとしてしまいます!

正しい方法は、 ptr::write を使う方法です。これは、ターゲットのアドレスを、 与えた値のビットでそのまま上書きします。何の評価も起こりません。

push においては、もし古い (push が呼ばれる前の) len が 0 であるなら、 0 番目の インデックスに書き込むようにしたいです。ですから古い len の値によるオフセットを使うべきです。

pub fn push(&mut self, elem: T) {
    if self.len == self.cap { self.grow(); }

    unsafe {
        ptr::write(self.ptr.offset(self.len as isize), elem);
    }

    // 絶対成功します。 OOM はこの前に起こるからです。
    self.len += 1;
}

簡単です! では pop はどうでしょうか? この場合、アクセスしたいインデックスにある 値は初期化されていますが、 Rust はメモリ上の値をムーブするために、その場所への 参照外しをする事を許可しません。なぜならこれによって、メモリを未初期化のままにするからです! これに関しては、 ptr::read を必要とします。これは、単にターゲットのアドレスから ビットをコピーし、それを型 T の値として解釈します。これによって、実際には そのアドレスのメモリにある値は完全に T のインスタンスであるけれども、 値を論理的には未初期化の状態のままにします。

pop に関しては、もし古い len の値が 1 の場合、 0 番目のインデックスにある値を 読み出したいです。ですから新しい len によるオフセットを使うべきです。

pub fn pop(&mut self) -> Option<T> {
    if self.len == 0 {
        None
    } else {
        self.len -= 1;
        unsafe {
            Some(ptr::read(self.ptr.offset(self.len as isize)))
        }
    }
}

デアロケーティング

次に、大量のリソースをリークしてしまわないよう、 Drop を実装するべきです。 簡単な方法は、単に pop を、 None が返されるまで呼び出し、そして、 バッファをデアロケートする方法です。もし T: !Drop である場合、 pop を 呼ぶことは必要ない事に注意してください。理論的には、T をドロップする必要が あるかを needs_drop で確かめ、 pop の呼び出しを省略することが出来ます。 しかし実践的には、 LLVM は本当にこのような副作用のない単純なコードを 取り除くことに優れているため、コードが取り除かれていないと気づかない 限りは気にしません (今回はコードが取り除かれています) 。

self.cap == 0 である場合、 heap::deallocate を呼んではいけません。 この時、実際にはメモリをアロケートしていないからです。

impl<T> Drop for Vec<T> {
    fn drop(&mut self) {
        if self.cap != 0 {
            while let Some(_) = self.pop() { }

            let align = mem::align_of::<T>();
            let elem_size = mem::size_of::<T>();
            let num_bytes = elem_size * self.cap;
            unsafe {
                heap::deallocate(*self.ptr as *mut _, num_bytes, align);
            }
        }
    }
}

参照外し

よし! 満足できる最小限のスタックを実装しました。プッシュ、ポップができ、 そして最後に自身を片付けることができます。しかし、我々が欲しい 沢山の機能があります。特に、適切な配列はあるけれども、スライスの 機能がありません。これは実際とても簡単に解決することができます。すなわち、 Deref<Target=[T]> を実装すればよいのです。これによって、 Vec に あらゆる状況において、スライスに型強制したり、スライスのように振る舞わせる ことができるようになります。

必要なのは slice::from_raw_parts です。これによって、正しく空の スライスを扱えます。サイズが 0 の型をサポートしたあとは、 これらも同様に扱えるようになります。

use std::ops::Deref;

impl<T> Deref for Vec<T> {
    type Target = [T];
    fn deref(&self) -> &[T] {
        unsafe {
            ::std::slice::from_raw_parts(*self.ptr, self.len)
        }
    }
}

では DerefMut も実装しましょう。

use std::ops::DerefMut;

impl<T> DerefMut for Vec<T> {
    fn deref_mut(&mut self) -> &mut [T] {
        unsafe {
            ::std::slice::from_raw_parts_mut(*self.ptr, self.len)
        }
    }
}

これで、 len、 first、 last、 インデックス参照、スライス、ソート、 iter、 iter_mut、そして他のスライスによって提供される、あらゆる 魅力的なツールを手に入れました。やったね!

挿入と削除

スライスから提供されないものに、 insert と remove があります。 今度はこれらを実装していきましょう。

挿入では、挿入位置から最後の要素まで、 1 ずつずらす必要があります。 これを行なうために、 ptr::copy を使う必要があります。 C の memmove の、 Rust 版のようなものです。これは、ある場所のメモリを別の場所にコピーします。 そして、2つの場所が重なっていても、正しくコピーされます (今回の場合、 明らかに重なります) 。

インデックス i の位置に挿入する場合、古い len の値を用いて、 [i .. len] を [i+1 .. len+1] にシフトします。

pub fn insert(&mut self, index: usize, elem: T) {
    // 注意: 全要素の後に挿入しても問題ないため、
    // `<=` としています。これは、プッシュと同等です。

    // 境界外インデックスです
    assert!(index <= self.len, "index out of bounds");
    if self.cap == self.len { self.grow(); }

    unsafe {
        if index < self.len {
            // ptr::copy(src, dest, len): "src から dest まで len 個の要素をコピー"
            ptr::copy(self.ptr.offset(index as isize),
                      self.ptr.offset(index as isize + 1),
                      self.len - index);
        }
        ptr::write(self.ptr.offset(index as isize), elem);
        self.len += 1;
    }
}

削除では真逆の事を行ないます。新しい len を使用して、 [i+1 .. len+1] を [i .. len] にシフトします。

pub fn remove(&mut self, index: usize) -> T {
    // 注意: 全要素のあとの物を削除することは*有効ではない*ため、 '<' を使用します

    // 境界外インデックスです
    assert!(index < self.len, "index out of bounds");
    unsafe {
        self.len -= 1;
        let result = ptr::read(self.ptr.offset(index as isize));
        ptr::copy(self.ptr.offset(index as isize + 1),
                  self.ptr.offset(index as isize),
                  self.len - index);
        result
    }
}

IntoIter

イテレータに移行しましょう。 Deref の魔法のおかげで、 iter と iter_mut は 既に書かれています。しかし、 Vec が提供できて、スライスが提供できない 2 つの 興味深いイテレータがあります。 into_iter と drain です。

IntoIter は Vec を値として消費します。その結果、その要素を値で返します。 これを有効にするために、 IntoIter が Vec のアロケーションを操作する 必要があります。

IntoIter は始端と終端の両方から読み出せるように、両頭である必要があります。 後ろから読み込むのは単に pop を呼び出すよう実装すればよいのですが、 前から読み出すのはもっと難しいです。 remove(0) を呼び出してもよいのですが、 そのコストは馬鹿馬鹿しい位大きいです。その代わりに、バッファを全く変化させずに、 ptr::read を使って両端から値をコピーするようにします。

これをするために、 C のごく普通の配列のイテレーションのイディオムを使います。 2 つのポインタを生成します。 1 つは配列の最初を指し、もう 1 つは配列の最後の 1 つ後ろの要素を指します。終端から要素を 1 つ取得したい場合は、ポインタが 指している値を読み出して、ポインタを 1 だけ動かします。もし 2 つのポインタが 等価な場合、全要素が読み出されたことを意味します。

読み出しとオフセットの操作の順序は next と next_back とで逆転することに 注意してください。 next_back では、ポインタは次に読みたい要素の直後の 要素をいつも指しています。対して next では、ポインタは次に読みたい 要素をいつも指しています。なぜこうなのか、 1 つを除いて全ての要素が 既に返された例を見てみましょう。

配列は以下のようになっています。

          S  E
[X, X, X, O, X, X, X]

もし E が、次に返したい値を直接指していたら、返す値が既に存在しない場合と 区別がつかなくなっているでしょう。

イテレーションの途中では気にしないのですが、 IntoIter がドロップされたら Vec を 解放するため、 Vec のアロケーションの情報を保持する必要もあります。

ですから以下のような構造体を使っていきます。

struct IntoIter<T> {
    buf: Unique<T>,
    cap: usize,
    start: *const T,
    end: *const T,
}

そしてこれが初期化のコードです。

impl<T> Vec<T> {
    fn into_iter(self) -> IntoIter<T> {
        // Vec がドロップされてしまうため、 Vec を分配出来ません。
        let ptr = self.ptr;
        let cap = self.cap;
        let len = self.len;

        // Vec をドロップするとバッファを解放してしまうので、ドロップしないようにします。
        mem::forget(self);

        unsafe {
            IntoIter {
                buf: ptr,
                cap: cap,
                start: *ptr,
                end: if cap == 0 {
                    // このポインタのオフセットを取ることが出来ません。アロケートされていないからです!
                    *ptr
                } else {
                    ptr.offset(len as isize)
                }
            }
        }
    }
}

前方へのイテレーションのコードです。

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.start == self.end {
            None
        } else {
            unsafe {
                let result = ptr::read(self.start);
                self.start = self.start.offset(1);
                Some(result)
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = (self.end as usize - self.start as usize)
                  / mem::size_of::<T>();
        (len, Some(len))
    }
}

そして後方へのイテレーションのコードです。

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        if self.start == self.end {
            None
        } else {
            unsafe {
                self.end = self.end.offset(-1);
                Some(ptr::read(self.end))
            }
        }
    }
}

IntoIter はアロケーションの所有権を受け取るので、それを解放するために Drop を 実装する必要があります。しかし、イテレーションの最中に返されなかった要素を ドロップするためにも Drop も実装する必要があります。

impl<T> Drop for IntoIter<T> {
    fn drop(&mut self) {
        if self.cap != 0 {
            // 残っている要素を全てドロップします
            for _ in &mut *self {}

            let align = mem::align_of::<T>();
            let elem_size = mem::size_of::<T>();
            let num_bytes = elem_size * self.cap;
            unsafe {
                heap::deallocate(*self.buf as *mut _, num_bytes, align);
            }
        }
    }
}

RawVec

興味深い状況に突入しました。すなわち、 Vec と IntoIter の、バッファの指定と メモリの解放の論理が重複しているのです。これらを実装し、実際にロジックが 重複していると特定したので、今がロジックを圧縮する丁度良い時です。

(ptr, cap) のペアを取り除き、これにアロケート、伸長そして解放のロジックを 与えます。

struct RawVec<T> {
    ptr: Unique<T>,
    cap: usize,
}

impl<T> RawVec<T> {
    fn new() -> Self {
        assert!(mem::size_of::<T>() != 0, "TODO: implement ZST support");
        unsafe {
            RawVec { ptr: Unique::new(heap::EMPTY as *mut T), cap: 0 }
        }
    }

    // Vec の時と変更ありません
    fn grow(&mut self) {
        unsafe {
            let align = mem::align_of::<T>();
            let elem_size = mem::size_of::<T>();

            let (new_cap, ptr) = if self.cap == 0 {
                let ptr = heap::allocate(elem_size, align);
                (1, ptr)
            } else {
                let new_cap = 2 * self.cap;
                let ptr = heap::reallocate(*self.ptr as *mut _,
                                            self.cap * elem_size,
                                            new_cap * elem_size,
                                            align);
                (new_cap, ptr)
            };

            // もしアロケートや、リアロケートに失敗すると、 `null` が返ってきます
            if ptr.is_null() { oom() }

            self.ptr = Unique::new(ptr as *mut _);
            self.cap = new_cap;
        }
    }
}


impl<T> Drop for RawVec<T> {
    fn drop(&mut self) {
        if self.cap != 0 {
            let align = mem::align_of::<T>();
            let elem_size = mem::size_of::<T>();
            let num_bytes = elem_size * self.cap;
            unsafe {
                heap::deallocate(*self.ptr as *mut _, num_bytes, align);
            }
        }
    }
}

そして Vec を以下のように変更します。

pub struct Vec<T> {
    buf: RawVec<T>,
    len: usize,
}

impl<T> Vec<T> {
    fn ptr(&self) -> *mut T { *self.buf.ptr }

    fn cap(&self) -> usize { self.buf.cap }

    pub fn new() -> Self {
        Vec { buf: RawVec::new(), len: 0 }
    }

    // push/pop/insert/remove は以下以外の変更はありません。
    // * `self.ptr -> self.ptr()`
    // * `self.cap -> self.cap()`
    // * `self.grow -> self.buf.grow()`
}

impl<T> Drop for Vec<T> {
    fn drop(&mut self) {
        while let Some(_) = self.pop() {}
        // デアロケートは RawVec が対処します
    }
}

最終的に、本当に IntoIter が単純になります。

struct IntoIter<T> {
    _buf: RawVec<T>, // これを扱うことはないのですが、ライフタイムは有効でなくてはなりません。
    start: *const T,
    end: *const T,
}

// next と next_back は buf を参照していないため、文字通り変更しません

impl<T> Drop for IntoIter<T> {
    fn drop(&mut self) {
        // 全ての要素が確実に読まれていることだけが必要です。
        // バッファは後で自身を片付けます。
        for _ in &mut *self {}
    }
}

impl<T> Vec<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        unsafe {
            // buf をアンセーフに移動させるため、 ptr:read を必要とします。
            // buf は Copy を実装しておらず、 Vec は Drop を実装しているからです
            // (ですから Vec を分配できません) 。
            let buf = ptr::read(&self.buf);
            let len = self.len;
            mem::forget(self);

            IntoIter {
                start: *buf.ptr,
                end: buf.ptr.offset(len as isize),
                _buf: buf,
            }
        }
    }
}

結構良くなりました。

Drain

Drain に移行しましょう。 Drain は大体 IntoIter と同じですが、 Vec を消費 する代わりに、 Vec を借用し、アロケーションに触れないままにします。 とりあえず、 "基本的な" 全範囲のバージョンだけを実装しましょう。

use std::marker::PhantomData;

struct Drain<'a, T: 'a> {
    // ライフタイムの制限を課す必要があるため、 `&'a mut Vec<T>` という
    // ライフタイムを付与します。セマンティクス的に、これを含んでいるからです。
    // 単に `pop()` と `remove(0)` を呼び出しています。
    vec: PhantomData<&'a mut Vec<T>>
    start: *const T,
    end: *const T,
}

impl<'a, T> Iterator for Drain<'a, T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.start == self.end {
            None

-- 待った、何か似ているな。もっと圧縮してみましょう。 IntoIter と Drain は両方同じ構造を持っています。抽出しましょう。

#![allow(unused)]
fn main() {
struct RawValIter<T> {
    start: *const T,
    end: *const T,
}

impl<T> RawValIter<T> {
    // 値のコンストラクトはアンセーフです。関連付けられているライフタイムが
    // 存在しないからです。 これは、RawValIter を、実際のアロケーションと同一の構造体に
    // 保存するため必要です。プライベートな実装詳細ですので問題ありません。
    unsafe fn new(slice: &[T]) -> Self {
        RawValIter {
            start: slice.as_ptr(),
            end: if slice.len() == 0 {
                // もし `len = 0` なら、実際にはメモリをアロケートしていません。
                // GEP を通して LLVM に間違った情報を渡してしまうため、
                // オフセットを避ける必要があります。
                slice.as_ptr()
            } else {
                slice.as_ptr().offset(slice.len() as isize)
            }
        }
    }
}

// Iterator と DoubleEndedIterator の impl は IntoIter と同一です。
}

そして IntoIter は以下のようになります。

pub struct IntoIter<T> {
    _buf: RawVec<T>, // これを扱うことはないのですが、その存在は必要です。
    iter: RawValIter<T>,
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> { self.iter.next() }
    fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
}

impl<T> Drop for IntoIter<T> {
    fn drop(&mut self) {
        for _ in &mut self.iter {}
    }
}

impl<T> Vec<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        unsafe {
            let iter = RawValIter::new(&self);

            let buf = ptr::read(&self.buf);
            mem::forget(self);

            IntoIter {
                iter: iter,
                _buf: buf,
            }
        }
    }
}

設計の中で、ちょっと奇妙なものを少し含めたことに注意してください。 これは、 Drain を任意の副範囲で動作させるのを、ちょっと簡単にするためです。 特に、 RawValIter がドロップの際に、自身をドレイン出来るでしょうが、 これは、もっと複雑な Drain に対しては正しく動作しません。 スライスも用いて、 Drain の初期化を単純にします。

よし、これで Drain を本当に楽に実装できます。

use std::marker::PhantomData;

pub struct Drain<'a, T: 'a> {
    vec: PhantomData<&'a mut Vec<T>>,
    iter: RawValIter<T>,
}

impl<'a, T> Iterator for Drain<'a, T> {
    type Item = T;
    fn next(&mut self) -> Option<T> { self.iter.next() }
    fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
}

impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
    fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
}

impl<'a, T> Drop for Drain<'a, T> {
    fn drop(&mut self) {
        for _ in &mut self.iter {}
    }
}

impl<T> Vec<T> {
    pub fn drain(&mut self) -> Drain<T> {
        unsafe {
            let iter = RawValIter::new(&self);

            // これは mem::forget に対する安全策です。もし Drain が forget されたら、
            // 単に Vec の内容全体がリークします。そして*結局*これをしなければ
            // なりません。なら今やっちゃいましょう。
            self.len = 0;

            Drain {
                iter: iter,
                vec: PhantomData,
            }
        }
    }
}

mem::forget の詳細は、リークの章を参照してください。

サイズが 0 の型を扱う

時間です。サイズが 0 の型という怪物と戦いましょう。安全な Rust では絶対に これを気にする必要はないのですが、 Vec は非常に生ポインタや生アロケーションを 多用します。これらはまさにサイズが 0 の型に注意しなくてはいけないところです。 以下の 2 つを気にしなければなりません。

• 生アロケータ API は、もしアロケーションのサイズとして 0 を渡すと、 未定義動作を引き起こします。
• 生ポインタのオフセットは、サイズが 0 の型に対しては no-op となります。 これによって C スタイルのポインタによるイテレータが壊れます。

ありがたいことに、ポインタのイテレータと、 RawValIter と RawVec に対する アロケーションの扱いを抽出しました。なんと魔法のように役立つでしょう。

サイズが 0 の型をアロケートする

では、アロケータの API がサイズ 0 の型のアロケーションに対応していないのならば、 一体全体何を、アロケーションとして保存すればいいのでしょうか? そうさ，勿論 heap::EMPTY さ! ZST に対する操作は、 ZSTがちょうど 1 つの値を持つため、 ほとんど全てが no-op となります。 それゆえこの型の値を保存したりロードしたりする場合に、状態を考える必要がありません。 この考えは実際に ptr::read や ptr::write に拡張されます。つまり、これらの操作は、 実際には全くポインタに着目していないのです。ですからポインタを変える必要は全くないのです。

ですが、サイズが 0 の型に対しては、オーバーフローの前にメモリ不足になる、という 前述した前提は最早有効ではないということに注意してください。サイズが 0 の型に対しては、 キャパシティのオーバーフローに対して明示的にガードしなければなりません。

現在のアーキテクチャでは、これは RawVec の各メソッド内に一つずつ、合わせて 3 つの ガードを書くことを意味します。

impl<T> RawVec<T> {
    fn new() -> Self {
        unsafe {
            // !0 は usize::MAX です。この分岐はコンパイル時に取り除かれるはずです。
            let cap = if mem::size_of::<T>() == 0 { !0 } else { 0 };

            // heap::EMPTY は "アロケートされていない" と "サイズが 0 の型のアロケーション" の
            // 2 つの意味を兼ねることになります。
            RawVec { ptr: Unique::new(heap::EMPTY as *mut T), cap: cap }
        }
    }

    fn grow(&mut self) {
        unsafe {
            let elem_size = mem::size_of::<T>();

            // elem_size が 0 の時にキャパシティを usize::MAX にしたので、
            // ここにたどり着いてしまうということは、 Vec が満杯であることを必然的に
            // 意味します。
            assert!(elem_size != 0, "capacity overflow");

            let align = mem::align_of::<T>();

            let (new_cap, ptr) = if self.cap == 0 {
                let ptr = heap::allocate(elem_size, align);
                (1, ptr)
            } else {
                let new_cap = 2 * self.cap;
                let ptr = heap::reallocate(*self.ptr as *mut _,
                                            self.cap * elem_size,
                                            new_cap * elem_size,
                                            align);
                (new_cap, ptr)
            };

            // もしアロケートや、リアロケートに失敗すると、 `null` が返ってきます
            if ptr.is_null() { oom() }

            self.ptr = Unique::new(ptr as *mut _);
            self.cap = new_cap;
        }
    }
}

impl<T> Drop for RawVec<T> {
    fn drop(&mut self) {
        let elem_size = mem::size_of::<T>();

        // サイズが 0 の型のアロケーションは解放しません。そもそもアロケートされていないからです。
        if self.cap != 0 && elem_size != 0 {
            let align = mem::align_of::<T>();

            let num_bytes = elem_size * self.cap;
            unsafe {
                heap::deallocate(*self.ptr as *mut _, num_bytes, align);
            }
        }
    }
}

以上。これで、サイズが 0 の型に対するプッシュとポップがサポートされます。 それでも (スライスの Deref から提供されていない) イテレータは、 まだ壊れているのですが。

サイズが 0 の型のイテレーション

サイズが 0 の型に対するオフセットは no-op です。つまり、現在の設計では start と end を 常に同じ値に初期化し、イテレータは何も値を返しません。これに対する今の所の解決策は、 ポインタを整数にキャストし、インクリメントした後に元に戻すという方法です。

impl<T> RawValIter<T> {
    unsafe fn new(slice: &[T]) -> Self {
        RawValIter {
            start: slice.as_ptr(),
            end: if mem::size_of::<T>() == 0 {
                ((slice.as_ptr() as usize) + slice.len()) as *const _
            } else if slice.len() == 0 {
                slice.as_ptr()
            } else {
                slice.as_ptr().offset(slice.len() as isize)
            }
        }
    }
}

さて、これにより別のバグが発生します。イテレータが全く動作しない代わりに、 このイテレータは永遠に動き続けてしまいます。同じトリックをイテレータの impl に 行なう必要があります。また、 size_hint の計算では、 ZST の場合 0 で割ることになります。 基本的に 2 つのポインタを、それらがバイトサイズの値を指しているとして扱っているため、 サイズが 0 の場合、 1 で割ります。

impl<T> Iterator for RawValIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.start == self.end {
            None
        } else {
            unsafe {
                let result = ptr::read(self.start);
                self.start = if mem::size_of::<T>() == 0 {
                    (self.start as usize + 1) as *const _
                } else {
                    self.start.offset(1)
                };
                Some(result)
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let elem_size = mem::size_of::<T>();
        let len = (self.end as usize - self.start as usize)
                  / if elem_size == 0 { 1 } else { elem_size };
        (len, Some(len))
    }
}

impl<T> DoubleEndedIterator for RawValIter<T> {
    fn next_back(&mut self) -> Option<T> {
        if self.start == self.end {
            None
        } else {
            unsafe {
                self.end = if mem::size_of::<T>() == 0 {
                    (self.end as usize - 1) as *const _
                } else {
                    self.end.offset(-1)
                };
                Some(ptr::read(self.end))
            }
        }
    }
}

出来ました。イテレーションが動作します!

The Final Code

#![feature(unique)]
#![feature(alloc, heap_api)]

extern crate alloc;

use std::ptr::{Unique, self};
use std::mem;
use std::ops::{Deref, DerefMut};
use std::marker::PhantomData;

use alloc::heap;

struct RawVec<T> {
    ptr: Unique<T>,
    cap: usize,
}

impl<T> RawVec<T> {
    fn new() -> Self {
        unsafe {
            // !0 is usize::MAX. This branch should be stripped at compile time.
            let cap = if mem::size_of::<T>() == 0 { !0 } else { 0 };

            // heap::EMPTY doubles as "unallocated" and "zero-sized allocation"
            RawVec { ptr: Unique::new(heap::EMPTY as *mut T), cap: cap }
        }
    }

    fn grow(&mut self) {
        unsafe {
            let elem_size = mem::size_of::<T>();

            // since we set the capacity to usize::MAX when elem_size is
            // 0, getting to here necessarily means the Vec is overfull.
            assert!(elem_size != 0, "capacity overflow");

            let align = mem::align_of::<T>();

            let (new_cap, ptr) = if self.cap == 0 {
                let ptr = heap::allocate(elem_size, align);
                (1, ptr)
            } else {
                let new_cap = 2 * self.cap;
                let ptr = heap::reallocate(*self.ptr as *mut _,
                                            self.cap * elem_size,
                                            new_cap * elem_size,
                                            align);
                (new_cap, ptr)
            };

            // If allocate or reallocate fail, we'll get `null` back
            if ptr.is_null() { oom() }

            self.ptr = Unique::new(ptr as *mut _);
            self.cap = new_cap;
        }
    }
}

impl<T> Drop for RawVec<T> {
    fn drop(&mut self) {
        let elem_size = mem::size_of::<T>();
        if self.cap != 0 && elem_size != 0 {
            let align = mem::align_of::<T>();

            let num_bytes = elem_size * self.cap;
            unsafe {
                heap::deallocate(*self.ptr as *mut _, num_bytes, align);
            }
        }
    }
}





pub struct Vec<T> {
    buf: RawVec<T>,
    len: usize,
}

impl<T> Vec<T> {
    fn ptr(&self) -> *mut T { *self.buf.ptr }

    fn cap(&self) -> usize { self.buf.cap }

    pub fn new() -> Self {
        Vec { buf: RawVec::new(), len: 0 }
    }
    pub fn push(&mut self, elem: T) {
        if self.len == self.cap() { self.buf.grow(); }

        unsafe {
            ptr::write(self.ptr().offset(self.len as isize), elem);
        }

        // Can't fail, we'll OOM first.
        self.len += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            None
        } else {
            self.len -= 1;
            unsafe {
                Some(ptr::read(self.ptr().offset(self.len as isize)))
            }
        }
    }

    pub fn insert(&mut self, index: usize, elem: T) {
        assert!(index <= self.len, "index out of bounds");
        if self.cap() == self.len { self.buf.grow(); }

        unsafe {
            if index < self.len {
                ptr::copy(self.ptr().offset(index as isize),
                          self.ptr().offset(index as isize + 1),
                          self.len - index);
            }
            ptr::write(self.ptr().offset(index as isize), elem);
            self.len += 1;
        }
    }

    pub fn remove(&mut self, index: usize) -> T {
        assert!(index < self.len, "index out of bounds");
        unsafe {
            self.len -= 1;
            let result = ptr::read(self.ptr().offset(index as isize));
            ptr::copy(self.ptr().offset(index as isize + 1),
                      self.ptr().offset(index as isize),
                      self.len - index);
            result
        }
    }

    pub fn into_iter(self) -> IntoIter<T> {
        unsafe {
            let iter = RawValIter::new(&self);
            let buf = ptr::read(&self.buf);
            mem::forget(self);

            IntoIter {
                iter: iter,
                _buf: buf,
            }
        }
    }

    pub fn drain(&mut self) -> Drain<T> {
        unsafe {
            let iter = RawValIter::new(&self);

            // this is a mem::forget safety thing. If Drain is forgotten, we just
            // leak the whole Vec's contents. Also we need to do this *eventually*
            // anyway, so why not do it now?
            self.len = 0;

            Drain {
                iter: iter,
                vec: PhantomData,
            }
        }
    }
}

impl<T> Drop for Vec<T> {
    fn drop(&mut self) {
        while let Some(_) = self.pop() {}
        // allocation is handled by RawVec
    }
}

impl<T> Deref for Vec<T> {
    type Target = [T];
    fn deref(&self) -> &[T] {
        unsafe {
            ::std::slice::from_raw_parts(self.ptr(), self.len)
        }
    }
}

impl<T> DerefMut for Vec<T> {
    fn deref_mut(&mut self) -> &mut [T] {
        unsafe {
            ::std::slice::from_raw_parts_mut(self.ptr(), self.len)
        }
    }
}





struct RawValIter<T> {
    start: *const T,
    end: *const T,
}

impl<T> RawValIter<T> {
    unsafe fn new(slice: &[T]) -> Self {
        RawValIter {
            start: slice.as_ptr(),
            end: if mem::size_of::<T>() == 0 {
                ((slice.as_ptr() as usize) + slice.len()) as *const _
            } else if slice.len() == 0 {
                slice.as_ptr()
            } else {
                slice.as_ptr().offset(slice.len() as isize)
            }
        }
    }
}

impl<T> Iterator for RawValIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.start == self.end {
            None
        } else {
            unsafe {
                let result = ptr::read(self.start);
                self.start = if mem::size_of::<T>() == 0 {
                    (self.start as usize + 1) as *const _
                } else {
                    self.start.offset(1)
                };
                Some(result)
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let elem_size = mem::size_of::<T>();
        let len = (self.end as usize - self.start as usize)
                  / if elem_size == 0 { 1 } else { elem_size };
        (len, Some(len))
    }
}

impl<T> DoubleEndedIterator for RawValIter<T> {
    fn next_back(&mut self) -> Option<T> {
        if self.start == self.end {
            None
        } else {
            unsafe {
                self.end = if mem::size_of::<T>() == 0 {
                    (self.end as usize - 1) as *const _
                } else {
                    self.end.offset(-1)
                };
                Some(ptr::read(self.end))
            }
        }
    }
}




pub struct IntoIter<T> {
    _buf: RawVec<T>, // we don't actually care about this. Just need it to live.
    iter: RawValIter<T>,
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> { self.iter.next() }
    fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
}

impl<T> Drop for IntoIter<T> {
    fn drop(&mut self) {
        for _ in &mut *self {}
    }
}




pub struct Drain<'a, T: 'a> {
    vec: PhantomData<&'a mut Vec<T>>,
    iter: RawValIter<T>,
}

impl<'a, T> Iterator for Drain<'a, T> {
    type Item = T;
    fn next(&mut self) -> Option<T> { self.iter.next_back() }
    fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
}

impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
    fn next_back(&mut self) -> Option<T> { self.iter.next_back() }
}

impl<'a, T> Drop for Drain<'a, T> {
    fn drop(&mut self) {
        // pre-drain the iter
        for _ in &mut self.iter {}
    }
}

/// Abort the process, we're out of memory!
///
/// In practice this is probably dead code on most OSes
fn oom() {
    ::std::process::exit(-9999);
}

fn main() {}

Arc と Mutex の実装

理論を知ることは結構です。ですが、何かを理解するのに最も良い方法は、それを使うことです。 アトミックや内部可変性をもっと理解するために、標準ライブラリの Arc 型と Mutex 型を 実装していきます。

TODO: この章全部