インターフェイスに関連するトレイト

私たちが構築しているライブラリは、Rust の標準ライブラリにある 2 つのコレクション、BTreeSet¹ と BTreeMap² の代替です。私たちの目標は、同じくよく知られたイディオマティックな API を提供しつつ、最大限の安全性（あらゆるシステム向け）とベアメタルへの移植性（ファームウェアや小型マイクロコントローラ向け）を備えることです。

そこに到達するには、標準ライブラリの API 設計について少し理解する必要があります。具体的には、これらの API がそのジェネリック引数に束縛するトレイトです。こうした設計上の判断は、使いやすさとリソース管理の相互作用を形作ります。

API 設計は、私たちの特定のデータ構造のアルゴリズムとは直交する関心事なので、まずはそこから取り組みましょう。標準ライブラリと同等の機能を実現するために、Rust が「内部で」どのように動作するかについて理解を深めます。

ジェネリクスとトレイトとは、何でしたっけ？

第 3 章で概念と構文を紹介しました。思い出すために、もう一度見てみましょう。

ジェネリクス（例: 具象型 u64 や u32 の代わりとなる T）は、コードの重複を不要にします。単一の関数のソースコードをコンパイラが使用し、その関数が呼び出される各具象型ごとに、機械語コード上の同等物を 1 つ生成できます（単相化）。

トレイト（例: ソートや比較が可能な型を表す T: Ord）は、異なる型の間で共有される振る舞いを定義します。他の言語におけるインターフェイスや抽象基底クラスに似ています。

私たちはしばしば、トレイトをジェネリック引数や戻り値に束縛することで、この 2 つを組み合わせます。これにより、ユーザーが何らかの振る舞い（1 つ以上の特定のトレイト）を実装している任意の[ジェネリック]型に活用できる単一の関数を書けます。まだ発明されていないカスタム型に対してさえもです！

マップの `get` API

マップ（連想配列またはシンボルテーブルとも呼ばれる）は、キーと値のペアを格納するデータ構造です。キーは一意であり、値はキーによって高速に検索できます。

Rust の BTreeMap² は順序付きマップであり、全順序³の概念を持つ任意のキー型をサポートします。くだけた言い方をすれば、キーを論理演算子（>、<=、== など）で比較でき、ソートできるということです。それは、それらが Ord トレイトを実装しているからです。キーを順序付けできないがハッシュ化できる場合は、代わりに HashMap⁴ を使うことになるでしょう。

順序付きマップで検索を実行したいとします。つまり、与えられたキーに関連付けられた値があれば、それを取得するということです。 get メソッドは、キーへの参照を入力として受け取り、Option（キーが見つかった場合の Some ケースでは値への参照を含む）を返すべきです。

標準ライブラリではこのように動作します。以下は公式の例です⁵:

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.get(&1), Some(&"a"));
assert_eq!(map.get(&2), None);

上記に基づくと、BTreeMap<K, V> の get メソッドのシグネチャは次のようになると予想するかもしれません。

impl<K, V> BTreeMap<K, V> {
    /// キーに対応する値への参照を返します。
    pub fn get(&self, key: &K) -> Option<&V>
    where
        K: Ord
    {
        // ...関数本体はここ...
    }
    // ... 残りのメソッド
}

しかし、そうではありません。実際の get メソッドは次のシグネチャを持ちます⁶:

impl<K, V> BTreeMap<K, V> {
    /// キーに対応する値への参照を返します。
    pub fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q> + Ord,
        Q: Ord + ?Sized,
    {
        // ...関数本体はここ...
    }
    // ... 残りのメソッド
}

なぜ 2 つの異なるジェネリック型が関わっているのでしょうか？そして、これらの奇妙に見えるトレイト境界はいったい何なのでしょうか？

各トレイトを個別に説明しながら、これらの疑問に答えられるよう段階的に進めていきましょう。この API を理解できれば、トレイトのイディオマティックな使い方全般を理解する道のりをかなり進んだことになります。

`Ord` トレイト

Ord⁷ は、get のシグネチャにある 3 つのトレイトのうち最も単純で、すでに説明したことのあるものです。ある型が Ord を実装している場合、その型は順序付け可能です⁸。この型の値同士を比較し、2 つが等しいか、または一方が他方より大きいかを判定できます。これにより、値をソートできます。

第 3 章では、OS プロセスを表す構造体に対して Ord トレイトを実装しました。これにより、特定の優先度の定義（私たちの場合はプロセスの現在の状態）に基づいてプロセスのリストをソートできるようになりました。

`Sized` トレイト

Sized⁹ は、マーカートレイトとして知られるものです。 Ord とは異なり、Sized にはそれ自体の振る舞いがないため、実装すべき「インターフェイス」メソッドはありません。マーカートレイトは、振る舞いを指定するのではなくプロパティをマークします（どんでん返しです！）。

トレイト境界 T: Sized は、型 T のすべての値がメモリ上で同じサイズを持ち、そのサイズがコンパイル時に既知であることをコンパイラに伝えます¹⁰。たとえば、u32 は常に 4 バイト長です。

ここから面白くなります。上記のシグネチャで使われている束縛である T: ?Sized（先頭の ? に注意）は、型 T の値が任意でサイズ付きである、つまり Sized である場合もない場合もあることを意味します。これは妙に曖昧に思えませんか？

実は、この曖昧さによって、UB を一切導入することなく柔軟性が得られます。標準ライブラリの設計者は、一般的なケースと例外の両方を扱いたいと考えました。 Rust の型の大半はサイズ付きですが、そうでない型も少数あります。サイズなし型の例には、次のものがあります。

スライス: スライス [T] は 0 個以上の連続した T を含むことができます。そのため、異なるスライス値は異なるサイズを持つ可能性があります。
- &[T]、つまりスライスへの参照は、常にファットポインタ（通常のポインタにスライス長のメタデータを加えたもの）のサイズであることに注意してください。
トレイトオブジェクト: Rust には動的ディスパッチ¹¹のための仕組みがあります。dyn キーワードはトレイトオブジェクト、つまり与えられたトレイトを実装する値を示します。その値は、そのトレイトを実装している限り、任意の型であり、任意のサイズを持つことができます。
- たとえば、Box<dyn Error> は、Error トレイトを実装する任意の型のインスタンスへのポインタです。

さて、BTreeMap のようなコレクションに格納される値は Sized でなければなりません。そうでなければ、それらをメモリにどのように格納すればよいかわからないからです。しかし、get はパラメーターとしてサイズ付き型とサイズなし型の両方をサポートするため（Q: ?Sized）、BTreeMap の検索は柔軟です。対応する型のサイズなしキーを使って、サイズ付きキーに関連付けられた値を見つけられます。このセクションの終わり近くで具体例を見ていきます。

`Borrow` トレイト

Borrow<T>¹² を実装する型は、参照 &T を借用できます。似たトレイトである AsRef¹³ とは異なり、Borrow は借用された &T が T と同じ比較およびハッシュのセマンティクスを持つことを要求します。 BTreeMap（比較の列による検索）や HashMap（ハッシュによる検索）に関係がありそうですよね？

まさにその通りです。Borrow トレイトは、コレクションの検索をより簡単かつ効率的にするために設計されています。実際、標準ライブラリには、すべての型 T が自分自身を借用できるようにする「ブランケット実装」（常に事前実装されているトレイト）が含まれています（つまり、T: Borrow<T> を「無料で」得られます）。

これにより、キーのコピーをメモリ上に作成しなくてもキー検索が可能になります。そのため、BTreeMap<String, T> を &str 型のキーで検索する場合、追加のヒープ割り当ては不要です。

すべてを組み合わせる

Ord、Sized、Borrow が組み合わさって API の利用にどのように影響するかを本当に理解するために、例を見ていきましょう。

たとえば、8バイトの hexspeak¹⁴ ワード、つまり [u8; 8] 型の値を、セットに格納するとします。その後、ユーザーが提供した可変サイズの hexspeak ワードのリスト、つまり Vec<u8> 型の値を受け取ります。長さが8バイトのものもあれば、そうでないものもあります。

ユーザーが提供したワードのいずれかが、すでにセット内に存在するかを確認するために、get メソッドを使えるようにしたいとします。幸い、get を使うとスライス（サイズなしの [u8]）を検索できます。任意サイズのユーザー提供ワードを、固定サイズ（8バイトワード）のセットに対する検索キーとして使用できます！

use std::collections::BTreeSet;

// 2つの hexspeak ワード
let bad_code: [u8; 8] = [0xB, 0xA, 0xA, 0xD, 0xC, 0x0, 0xD, 0xE];
let bad_food: [u8; 8] = [0xB, 0xA, 0xA, 0xD, 0xF, 0x0, 0x0, 0xD];

// セットには均一なサイズの値を格納しようとしていることに注目してください
assert_eq!(std::mem::size_of_val(&bad_code), 8);
assert_eq!(std::mem::size_of_val(&bad_food), 8);

// 2つのワードをセットに格納します
let mut set = BTreeSet::new();
set.insert(bad_code);
set.insert(bad_food);

// Vec<u8> はサイズ付きで、実際にはヒープバッファーへのファットポインターです。
// しかし、vec のスライスはサイズなしです！ たとえば、次のようになります。
//     &my_vec[0..5] は最初の5要素
//     &my_vec[1..] は最初の要素を除くすべて
//     &my_vec[..] はすべての要素
let bad_food_vec: Vec<u8> = vec![0xB, 0xA, 0xA, 0xD, 0xF, 0x0, 0x0, 0xD];
let bad_dude_vec: Vec<u8> = vec![0xB, 0xA, 0xA, 0xD, 0xD, 0x0, 0x0, 0xD];
let cafe_bad_food_vec: Vec<u8> = vec![
    0xC, 0xA, 0xF, 0xE, 0xB, 0xA, 0xA, 0xD, 0xF, 0x0, 0x0, 0xD
];

// 存在する [u8; 8] を検索します
assert_eq!(
    set.get(&bad_food_vec[..]),         // 0xBAADFOOD
    Some(&[0xB, 0xA, 0xA, 0xD, 0xF, 0x0, 0x0, 0xD])
);

// 存在しない [u8; 4] を検索します
assert_eq!(
    set.get(&bad_food_vec[..4]),        // 0xBAAD
    None
);

// 存在しない [u8; 8] を検索します
assert_eq!(
    set.get(&bad_dude_vec[..]),         // 0xBAADDUDE
    None
);

// 存在する [u8; 8] を検索します
assert_eq!(
    set.get(&cafe_bad_food_vec[4..]),   // 0xBAADF00D
    Some(&[0xB, 0xA, 0xA, 0xD, 0xF, 0x0, 0x0, 0xD]),
);

// 存在しない [u8; 12] を検索します
assert_eq!(
    set.get(&cafe_bad_food_vec[..]),    // 0xCAFEBAADF00D
    None
);

では、任意長（[u8]）のキーを使って固定長のセット要素（[u8; 8]）を検索できるようにするために、何が起きたのでしょうか？モノモーフィゼーションの魔法によって、コンパイラーが私たちのジェネリックな get 呼び出し箇所を何に変換したのかを考えてみましょう。

pub fn get(&self, key: &[u8]) -> Option<&[u8; 8]>
{
    // ...コンパイル済みバイナリ内のこのコードの関数本体...
}

Ord と Sized - トレイト境界 Q: Ord + ?Sized は、スライスの内容をソートできる限り、任意サイズのスライスを使って自由に検索できることを意味します。[u8] はその基準を満たします。上記では、ユーザー提供のベクターをスライスに変換しました。
Ord と Borrow - トレイト境界 K: Borrow<Q> + Ord により、その変換が可能になります。前述の任意サイズかつソート可能なスライスを借用できる任意のキーを使って検索できます。Vec は、格納されている要素数に関係なく、自身の要素を連続したスライスとして見ることができます。Vec<T> は Borrow<[T]> を実装しているため、Vec はそのスライスを自分自身から借用することもできます（データはコピーされません！）。したがって、&my_vec[..]（my_vec.as_slice() のスライス記法による省略形）により、検索用の &[u8] キーを渡せます。

結論として、BTreeMap の get は3つのトレイト（Ord、?Sized、Borrow）を組み合わせることで、柔軟で効率的な API を実現しています。

さらに一歩進める: `Default` トレイト

これから構築するライブラリでは、4つ目のトレイト Default¹⁵ を加えます。名前の通り、このトレイトはデフォルト値を持つ型のためのものです。たとえば、次のようになります。

isize のデフォルトは 0 です。
Option のデフォルトは None です。
任意の動的コレクション（Vec、BTreeSet、HashMap など）のデフォルトは、そのコレクションの空のインスタンスです。

私たちの API は次のようになります。

/// キーに対応する値への参照を返します。
pub fn get<Q>(&self, key: &Q) -> Option<&V>
where
    K: Borrow<Q> + Ord + Default,
    Q: Ord + Default + ?Sized,
{
    // ...ここに関数本体...
}

心配しないでください。読むより使う方が簡単です。とはいえ、キーと値に Default を要求するという選択は制約になります。私たちのライブラリのユーザーは、私たちのコレクションのいずれかに格納したい任意のカスタム型について、そのトレイトが実装されていることを保証しなければなりません。

なぜそのような制限を強制するのでしょうか？ Default は「引数なしコンストラクター」のようなものであり、ある型の値が常に安全に初期化されることを保証します。

これは、前の章でアリーナアロケーターに使用した、サードパーティの #![forbid(unsafe_code)] ライブラリである tinyvec¹⁶ に格納される要素の要件です。つまり、Default の制約は依存関係から継承されています。

それを課すことは、保証に関するトレードオフです。私たちは、100% 安全なバイナリ、つまり私たちのすべてのコードとそのコードのすべての依存関係（たとえば、ライブラリのサプライチェーン全体）がメモリ安全性を最大化するという保証と引き換えに、ユーザーに少し多くを求めます。

Default を要求することに道徳的に反対で、標準ライブラリと完全に API 互換のままでいたい場合は、今すぐアロケーター内の tinyvec を smallvec¹⁷ に置き換え、この本の残りの非テストコードをすべて調整してかまいません。 smallvec は、もう1つのスタックベースの Vec 代替です。 Mozilla の Servo ブラウザーエンジンで使用されています。

残念ながら、smallvec には unsafe コードが含まれています。セキュリティ研究者は、smallvec に複数のメモリ安全性脆弱性を発見しており、それらには CVE が割り当てられています（例: CVE-2021-25900、CVE-2019-15554、CVE-2018-20991 など）。

smallvec は人気があり、十分に検証されていますが、まだ存在する未発見のメモリ安全性脆弱性の数については、何も保証できません。対照的に、tinyvec がメモリ破壊攻撃の被害を受けることは決してありません。これは #![forbid(unsafe_code)] だからです。

他に知っておくべきトレイトはありますか？

すべての Rust プログラマーが知っておくべきトレイトの公式な一覧はありません。しかし、メモリの割り当てと解放に関連する 3 つのトレイト、Clone、Copy、Drop にはほぼ間違いなく出会うことになります。これらのいくつかには以前触れましたが、改めて見直す価値があります。

Clone¹⁸ は深いコピーのロジックを定義します。Clone 型は Sized でなければなりません。元の値を再帰的にたどる必要がある場合、クローンは高コストになる可能性があります。所有しているすべてのものに対応する相手を割り当てなければならないためです。

たとえば、Vec<String> をコピーするということは、各 String をコピーするということです。String は内部的には Vec<u8> なので、各 String をコピーするということは、各 u8 をコピーするということです。これは再帰が 2 レベルにすぎませんでしたが、Clone は任意の深さを必要とする可能性があります。

コードに my_structure.clone() 呼び出しが散らばっているなら、それらを取り除くことは「手軽に得られる」性能最適化かもしれません。所有権の流れを、主に参照を処理するようにリファクタリングできるなら（たとえば String を &str に置き換える）、貴重な時間とメモリを節約できるかもしれません。「かもしれない」と言っているのは、性能最適化は時期尚早ではなく、データ駆動で行う必要があるためです。第 12 章でマイクロベンチマークについて扱います。

Copy¹⁹ は、浅いバイト単位のコピーだけで完全にクローンできる型のためのマーカートレイトです。これは、たどるべきポインタや、ハンドルを複製すべき外部リソースがないことを意味します。

プラットフォーム固有の符号付き整数型である isize を考えてみましょう。整数の値をエンコードする、固定サイズで連続した小さなバイト列を複製すれば、元の完全な複製が得られます。

Copy の実装は控えめに行うべきです。これは、代入演算子 = が単に所有権を移す（「ムーブセマンティクス」）のではなく、バイトをコピーする（暗黙の「コピーセマンティクス」）ことを意味します。

Drop²⁰ は「デストラクタ」を定義します。実装している型の変数がスコープを抜けるときに呼び出される、ユーザー定義可能な解放ロジックです。すべてのメモリと共有リソースは解放されなければなりません。Copy を実装する型は Drop を実装することを許可されていません（これらは相互排他的であるべきです。ビット単位でコピー可能なメモリはビット単位で消去できます）。

変数の束縛のスコープが条件文に依存する場合、ムーブセマンティクスは実行時に追跡されることに注意してください。プログラムの実行中、どの分岐が選ばれるかに基づいて、値はあちらこちらへ移動できます。しかし最終的に Rust はそれを一度だけドロップします。最後にムーブされた場所がスコープを抜けるときです。

要点

標準ライブラリの BTreeSet/BTreeMap の単なるユーザーである私たちには、Ord、?Sized、Borrow の細かなニュアンスはおそらく実感しにくいでしょう。マップの get シグネチャがなぜあのような形をしているのかを考えなくても、長く実りあるキャリアを送ることはできるでしょう。

しかし、API 互換の代替実装を設計し実装する立場としては、標準ライブラリが提供するのと同じ柔軟な抽象化をユーザーに提供したいと考えます。そのためには、これらのトレイトと、それらがどのように相互作用するかを理解する必要があります。

標準ライブラリが、このセクションの冒頭で使ったより直感的なシグネチャ（pub fn get<K: Ord>(&self, key: &K) -> Option<&V>）を採用していたなら、上の hexspeak の例はコンパイルすらできなかったでしょう。したがって、ここまで扱ってきた複雑さには大きな見返りがあります。同じコードが、より広い範囲のユースケースをシームレスにサポートできるのです。

これでトレイト束縛の背景をひととおり押さえたので、特定のインターフェイスがどのように、そしてなぜそのように設計されているのかがわかりました。では次に、それらを支えるロジック、つまり自己平衡スケープゴート木の中核操作に取り組みましょう。

構造体 std::collections::BTreeSet. The Rust Team（2022年アクセス）。 ↩
構造体 std::collections::BTreeMap. The Rust Team（2022年アクセス）。 ↩ ↩2
全順序 Wikipedia（2022年アクセス）。 ↩
構造体 std::collections::HashMap. The Rust Team（2022年アクセス）。 ↩
BTreeMap の get API の例. The Rust Team（2022年アクセス）。 ↩
BTreeMap の get API. The Rust Team（2022年アクセス）。 ↩
トレイト std::cmp::Ord. The Rust Team（2022年アクセス）。 ↩
全順序 Wikipedia（2022年アクセス）。 ↩
トレイト std::marker::Sized. The Rust Team（2022年アクセス）。 ↩
Rust における Sizedness. pretzelhammer（2020）。 ↩
動的ディスパッチ. Wikipedia（2022年アクセス）。動的ディスパッチのユースケースの 1 つは、異種コレクションを可能にすることです。たとえば Vec<Box<dyn Error>> を使うと、型が異なる可能性のある Error オブジェクトのベクターを格納できます。 ↩
トレイト std::borrow::Borrow. The Rust Team（2022年アクセス）。 ↩
トレイト std::convert::AsRef. The Rust Team（2022年アクセス）。 ↩
Hexspeak. Wikipedia（2022年アクセス）。 ↩
トレイト std::default::Default. The Rust Team（2022年アクセス）。 ↩
tinyvec. Lokathor（2022年アクセス）。 ↩
smallvec. Simon Sapin、Ms2ger、Servo project（2022年アクセス）。 ↩
トレイト std::clone::Clone. The Rust Team（2022年アクセス）。 ↩
トレイト std::marker::Copy. The Rust Team（2022年アクセス）。 ↩
トレイト std::ops::Drop. The Rust Team（2022年アクセス）。 ↩

Keyboard shortcuts

High Assurance Rust: Developing Secure and Robust Software 日本語版