聞き流しプログラミング言語学習

第61章へようこそ。今日のテーマは「Cow」です。第18章で、文字列を返す関数の戻り値をどう決めるかを見ました。新しく作ったものを呼び出し側に持ち帰らせるならString、借りたまま返すなら文字列スライス。戻り値の型は所有権の流れで決まる、と定めた。この原則で決められない関数がある。入力をそのまま返すこともあれば、加工したものを返すこともある関数だ。どちらになるかは、入力を見るまで決まらない。今日扱うのは、その決まらなさをどう型に持つのか、複製がいつ起きるのか、この型が何を要求するのか、そしてどういう流れで使う形なのか、です。

第60章へようこそ。今日のテーマは「rayon」です。rayonは、Cargoの設定ファイルに書いて取り込む外部のクレートです。コレクションの要素にかける処理を、複数のコアへ分けて走らせる。現在のCPUには、コアが複数ある。だが、イテレータで要素を順に処理するコードは、そのうちの1つしか使わない。要素が100万個あっても、残りのコアはなにも進めていない。rayonが引き受けるのは、この使われていないコアへ要素を配り、かかる時間を減らすことだ。配るには、決めることが増える。どこで分けるのか。分けた先で壊れないと誰が確かめるのか。分けた量が偏ったらどうするのか。rayonは、これらを書き手が書かなくてよい形で引き受けている。ただし、分けること自体に代償がある。今日扱うのは、その引き受け方と代償です。

第59章へようこそ。今日のテーマは「キャッシュと局所性」です。第20章で、スタックは速くヒープは遅いと言われるのを分解しました。差は3つあった。確保にかかる時間、解放にかかる時間、そしてアクセスの局所性だ。このうち確保と解放は、アロケータの手順の差だった。3つ目だけが、置いてある値を読むこと自体の速さの話だ。第20章では、スタックはCPUのキャッシュに乗りやすく、ヒープは散らばるから恩恵を受けにくい、とだけ述べた。今日扱うのは、そのキャッシュが何のためにあるのか、値がどんな単位で運ばれるのか、なぜ連続して並んでいると速いのか、なぜ手数の少ないほうが遅くなることがあるのか、そして型の大きさが速さに何をするのか、です。

第58章へようこそ。今日のテーマは「FFIと所有権」です。第56章で、境界の向こうにRustの保証が1つも届かないと見ました。借用チェッカーも、所有権も、ライフタイムも、ドロップも、境界の手前で止まる。前章では、型の姿を両側で守る契約にして、を外へ渡せる形に整えた。だが、外へ渡したは、いつか解放しなければならない。契約が決めるのは姿までで、後始末までは決めない。今日扱うのは、が境界を越えるとき何が渡るのか、解放の責任をどう取り決めるのか、ドロップが届かない資源をどう扱うのか、パニックが境界へ届くと何が起きるのか、そしてエラーがどんな形になるのか、です。

第57章へようこそ。今日のテーマは「repr(C)」です。第55章で、値はメモリの上ではビット列だと見ました。その並びをどう読むかを決めるのが型だった。だが、複数の値を1つにまとめた構造体が、メモリの上でどう並ぶのかは、まだ見ていない。型は値の読み方だけでなく、構造体のフィールドの置き方も決めている。今日は、その置き方を見ます。第56章では、言語をまたぐ境界で、関数が呼び出し規約という機械語レベルの取り決めでつながると見た。取り決めは、引数と戻り値の受け渡しを決める。だが取り決めが決めるのは、値の置かれる場所までだ。値の中身がどんな順序で並んでいるかは、呼び出し規約は決めない。今日扱うのは、構造体がメモリの上でどう並ぶのか、なぜその姿を外に見せる瞬間に固定が要るのか、レイアウトの約束にはどんな種類があるのか、そして固定に何を差し出すのか、です。

第56章へようこそ。今日のテーマは「FFI境界」です。第52章から前章までで、unsafeが解禁する操作を見てきました。生ポインタのデリファレンス、UnsafeCell、transmute。どれもunsafeだったが、扱っていたのはRustの中の値だった。生ポインタが指すのもRustが確保したメモリ、transmuteが読み替えるのもRustの型のビット列。規則の外側とはいえ、まだRustの世界の中にあった。今日からは、その外に出ます。境界の向こうに、別の言語で書かれた関数がある。Rustから、その関数を呼ぶ。あるいはRustの関数を、別の言語から呼ばせる。今日扱うのは、この言語をまたぐ境界が何と呼ばれるか、なぜ別の言語の関数を呼べて、その呼び出しがなぜunsafeになるのか、境界の向こうにRustの保証が届かないこと、そして両方向の境界を安全な抽象で包むこと、です。

第55章へようこそ。今日のテーマは「transmuteと未定義動作」です。第52章で、unsafeは規則を破る許可ではなく、保証の主体がコンパイラから人間へ移る境界だと見ました。第53章と第54章では、その移転が起きる場所を見た。生ポインタのデリファレンスでは、指す先に有効な値があることを人間が保証した。UnsafeCellでは、読みと書きが衝突しないことを人間が保証した。だが、保証に失敗したら何が起きるのかは、まだ確かめていない。第54章では、前提と食い違ったプログラムの動作に保証は無い、とだけ言った。今日は、この「保証は無い」の中身を確かめます。unsafeの中には、人間がどう注意しても越えてはいけない線が引かれている。その線がどこにあり、越えると何が起きるのか。入り口は、ビット列を別の型として読み替える関数、transmuteです。今日扱うのは、transmuteが何をするのか、型が持つ有効性の条件、そして未定義動作とは何か、です。

第54章へようこそ。今日のテーマは「UnsafeCell」です。第23章で、内部可変性を見ました。外側の値に不変参照しか持っていないのに、その内側の値を変更できる仕組み。RefCellは、借用の検査を実行時に行うことで、それを安全な操作として提供していた。だが、1つ確かめていないことがある。借用規則は、不変参照の先を書き換えることを許さない。そしてRefCell自身も、Rustで書かれた型だ。同じ規則の下にあるはずのRustのコードが、不変参照の先を書き換えるという動作を、どこかで組み立てていることになる。第52章で、安全な抽象の内側にはunsafeがあると見ました。第53章では、その内側で使われる生ポインタを見た。今日はその2つが実際に働いている場所を、内部可変性で確かめます。Cell、RefCell、ミューテックス、アトミック型。これらすべての内側に、たった1つの型がある。それがUnsafeCellです。今日扱うのは、不変参照が支えている前提、UnsafeCellがその前提をどう外すのか、安全な型がその上にどう立っているのか、そしてスレッドの境界で何が起きるのか、です。

第53章へようこそ。今日のテーマは「生ポインタ」です。第52章で、unsafeが解禁する5つの操作を見ました。その1つ目が、生ポインタのデリファレンスだった。生ポインタは、参照と違って借用規則もライフタイムの保証も持たない、ただのアドレスだ。そう触れただけで、生ポインタそのものは詳しく見ていない。参照は、借用規則とライフタイムに守られていた。第1章から見てきた借用、第13章から見たライフタイム。参照は、その規則に守られた、有効な値へのアクセスだ。メモリの上では、そのアクセスは1つのアドレスとして表される。生ポインタは、そのアドレスから借用規則とライフタイムを取り去ったものだ。今日扱うのは、生ポインタが参照と何が違うのか、なぜ作ることは安全でデリファレンスがunsafeなのか、そしてヌルとNonNullです。

第52章へようこそ。今日のテーマは「unsafe」です。第51章の最後で、コンパイラの検査には外側があると見ました。Pinが移動を止める仕組みは、型が可変参照を返さないところまではコンパイラの検査の中にある。だが、Pinを作る操作と中身を取り出す操作には、が動かないという前提があり、その前提が本当に成り立つかをコンパイラは検査しない。検査されないその一点は、操作を書いた人間が引き受けた。この「検査の外を人間が引き受ける」という形は、Pinだけのものではない。Rustには、検査の外に出て、その正しさを人間が引き受けることを示す、1つのキーワードがある。それがunsafeです。今日扱うのは、unsafeが実際に何をするのか、何を解禁するのか、そしてなぜそれが「安全を捨てる」ではなく「保証する主体が移る」ことなのか、です。

第51章へようこそ。今日のテーマは「Pin」です。第45章で、Pinという型に触れました。asyncをつけた関数から作られるFutureは、状態の中に自己参照を持つことがある。自己参照を持つFutureは、メモリ上で別の場所へ移動すると、内部のポインタが古い場所を指したまま残ってずれる。これを避けるのがPinだと見ました。今日扱うのは、そのPinが移動を止めるとき実際に何をしているのか、なぜFutureへの問い合わせがPinを通して行われるのか、そしてなぜほとんどの型はPinと無関係でいられるのか、です。

第50章へようこそ。今日のテーマは「ブロッキングと協調スケジューリングの衝突」です。第44章で、タスク自身が進行を譲る協調的なスケジューリングを見ました。第46章で、1つの流れの中で複数のタスクを管理して進める実行器を見ました。この2つを積み上げると、1つの帰結が導かれます。awaitで進行を譲らない重い処理をタスクの中に置くと、同じ流れを共有するほかのタスクが進まなくなる。今日扱うのは、なぜそれが起きるのか、そしてそれをどう避けるのか、です。

第49章へようこそ。今日のテーマは「Stream」です。第4章で、複数の値を1つずつ取り出すイテレータを見ました。第45章で、いずれ手に入る1つの結果を表すFutureを見ました。イテレータは複数の値を扱い、Futureは時間をかけて届く1つの値を扱いました。今日扱うのは、この2つが1つに合わさったもの、です。複数の値が、時間をかけて1つずつ届く。この流れを表す型を、Streamと呼びます。今日は、イテレータとFutureをもう一度たどり、その2つがどう合わさってStreamになるのか、Streamから値をどう受け取るのか、そして値とイテレータの関係が、FutureとStreamの間にそのまま成り立つことを、見ていきます。

第48章へようこそ。今日のテーマは「待ち合わせ」です。第45章で、asyncをつけた関数が返すFutureという、いずれ手に入る結果を表す値を見ました。第46章で、そのFutureに問い合わせを繰り返して完了まで進める実行器を見ました。第47章で、タスクを途中でやめるキャンセルが、Futureをドロップすることだと見ました。ここまで扱ってきたのは、いつも1つのFutureでした。今日扱うのは、複数のFutureを同時に待つこと、です。具体的には、複数のFutureを1つにまとめて全部の完了を待つjoin、最初に完了した1つだけを待って残りを捨てるselect、そしてこの待ち合わせが、これまで見てきた待ちとどう違うのか、を扱います。

第47章へようこそ。今日のテーマは「タスクのライフサイクル」です。第44章で、1つの流れの中で複数のタスクを交互に進めることで並行を作る、非同期処理を見ました。第45章で、asyncをつけた関数が返すFutureという、いずれ手に入る結果を表すあたいを見ました。第46章で、そのFutureにpollを繰り返し呼んで完了まで進める実行器を見ました。今日扱うのは、タスクが途中でパニックしたとき何が起きるか、そしてタスクを途中でやめるキャンセルという操作が何を意味するか、です。

第46章へようこそ。今日のテーマは「実行器」です。第45章で、Futureは自分自身を進める手段を持たないと見ました。pollを繰り返し呼んで完了まで進める主体は、Futureの外にいる。今日扱うのは、その外にいる主体が何か、それがどうやって無駄なくpollを繰り返すのか、そしてRustがその主体を標準では持たない設計です。

第45章へようこそ。今日のテーマは「Future」です。第44章で、asyncをつけた関数が、中断と再開ができる関数になることを見ました。asyncをつけた関数を呼ぶと、結果そのものではなく、Futureと呼ばれる値が1つ返ってきます。今日扱うのは、このFutureが何を表すのか、外からの問い合わせにどう答えるのか、そして中断した地点までの進行をどこに保持するのか、です。

第44章へようこそ。今日から、非同期処理を扱う一連の章に入ります。今日のテーマは「非同期入門」です。これまでの一連の章で見たのは、スレッドによる並行処理でした。スレッドを使って流れを複数に分け、それぞれの流れを別々に進める方法です。非同期処理は、並行処理を作るもう1つの道です。スレッドとは異なる方法で、複数の処理を同時に進行させます。今日扱うのは、なぜスレッドとは別の道が要るのか、並行と並列という2つの言葉が指す違い、そして非同期がどちらの軸に位置するのか、という基本構造です。

第43章へようこそ。今日のテーマは「デッドロック」です。ここまで、複数のスレッドが安全に値を共有するための手段を見てきました。MutexやRwLockは、ロックを取った流れだけに接触を許し、ほかの流れを待たせることで、同時の書き換えを防いだ。ロックは、待たせることで安全を作る仕組みでした。しかし、待たせることそのものが、新しい停止を生むことがあります。複数の流れが、互いに相手の解放を待ち、どちらも進めなくなる。この、互いを待ち続けて永遠に進まない状態を、デッドロックと呼びます。デッドロックは、Rustがコンパイル時に防がない種類の問題です。今日扱うのは、デッドロックがなぜ起こるのか、なぜ型システムがそれを防がないのか、そして、取得の順序を統一することがなぜ回避になるのか、という思考法です。

第42章へようこそ。今日のテーマは「アトミック」です。これまでの章で、共有した値を複数のスレッドから安全に書き換える手段として、ロックを見てきました。MutexやRwLockは、ロックを取った流れだけに値への接触を許し、ほかの流れを待たせる。ロックを取り、解放するという手順そのものにコストがかかる。しかし、共有したい値が1つの数や1つの真偽の値のように単純なとき、ロックでひとくくりに囲むのは大げさです。ロックを使わずに、その1つの値の更新だけを安全に行う手段がある。それがアトミックです。第37章と第39章で、参照カウントの操作が「原子的」であるかどうかを見ました。今日は、その「原子的」を正面から扱います。今日扱うのは、アトミックが何を保証するのか、メモリ順序という付随する指定、そしてアトミックで扱える範囲の限界です。

第41章へようこそ。今日のテーマは「RwLock」です。前章のミューテックスは、読み取りでも書き換えでも、一度に1つの流れだけにあたいへの接触を許しました。触れる目的が読み取りであっても、ロックを取った1つの流れが終えるまで、ほかの流れは待つ。しかし、複数の流れが同じ値をただ読むだけなら、同時に触れても問題は起こりません。第37章で見たように、読み取りしか起こらないなら、書き換えによる競合は生じないからです。読み取りどうしは衝突しないのに、Mutexはそれも1つずつに制限する。読み取りが多い場面では、この制限が並行性を必要以上に下げる。RwLockは、読み取りと書き換えを区別するロックです。読み取りは複数の流れに同時に許し、書き換えだけを1つの流れに絞る。排他の範囲を、接触の目的によって変える。今日扱うのは、RwLockが提供する2種類のロック、その取得の規則が借用の規則とどう重なるのか、そして、どういう場面でこの区別が効くのか、です。

第40章へようこそ。今日のテーマは「Mutex」です。前章で、Arcが共有された読み取りのアクセスを与えることを見ました。複数のスレッドが1つの値を共通の所有者として持ち、それぞれが読める。ただし、Arcが解決するのは「誰がその値を所有するか」までで、「いつその値を書き換えてよいか」は別の問題でした。複数のスレッドが同じ値を同時に書き換えれば、書き込みが互いに干渉し、データ競合が起こる。Mutexは、この「いつ書き換えてよいか」を解く仕組みです。1つの値に対して、一度に1つのスレッドだけが触れることを保証する。触れている流れがいる間、ほかの流れは待つ。この「一度に1つだけ」という保証を、排他アクセスと呼びます。今日扱うのは、Mutexが排他アクセスをどう保証するのか、それを支えるガードの仕組み、そしてArcと組み合わせて複数のスレッドで可変な値を共有する形です。

第39章へようこそ。今日のテーマは「Arc」です。ここまで、並行処理で値を扱う道は、所有権を移すことでした。第36章のmoveは、値の所有権を新しいスレッドへ移した。第38章のチャネルは、値の所有権を流れの間で送って受け渡した。どちらも、値は常にどこか1つの流れにあり、移ることで次の流れへ渡っていく。しかし、値を移すのではなく、1つの値を複数のスレッドが同時に保持したい場面があります。大きな値を、それぞれのスレッドへ複製して配るのは無駄が大きい。1つの値を、複数のスレッドが共通の所有者として持ちたい。ここから、所有権を渡さずに共有する道に入ります。今日扱うのは、複数のスレッドが1つの値を共有して所有するための型、Arcです。第22章のRcを振り返りながら、なぜRcではスレッドを越えられないのか、Arcがそれをどう解決するのか、その代償は何か、という核心を見ていきます。

第38章へようこそ。今日のテーマは「チャネル」です。第36章で、moveが値の所有権を新しいスレッドへ移すことを見ました。あのときの移動は、スレッドを生成する一度きりのものでした。クロージャに渡した値が、新しいスレッドへ移って、そこで使われる。チャネルは、この所有権の移動を、スレッドが動いている間ずっと繰り返せるようにする仕組みです。1つの流れが値を送り出し、別の流れがそれを受け取る。送り出した側は、その値の所有権を手放す。受け取った側が、新しい所有者になる。スレッドを生成するときの一度きりの移動が、実行の途中で何度でも起こる形に広がる。これは、第36章のmoveの延長です。所有権を移して受け渡すという同じ考え方が、動き続ける流れの間の通信に使われる。今日扱うのは、チャネルがどう所有権を運ぶのか、受け取る側がどう待つのか、複数の送り手をどう束ねるのか、そして送る速さと受け取る速さをどう調停するのか、です。

第37章へようこそ。今日のテーマは、SendとSyncです。前章で、スレッドに値を渡すときは所有権ごと渡すことを見ました。moveが、外側の値の所有権をクロージャへ移し、新しいスレッドへ持ち込む。ただし、すべての値がスレッド境界を越えてよいわけではありません。ある値をスレッドに渡すと、データ競合という危険が生じる場合がある。データ競合は、複数の流れが同じ値に同時に触れ、少なくとも一方が書き換えるときに起こる、結果の定まらない状態のことです。Rustは、この危険を実行してから気づくのではなく、コンパイルの時点で防ぐ。そのために、どの型がスレッド境界を越えてよいかを、型のうえで区別する。この区別を担うのが、SendとSyncという2つのトレイトです。今日扱うのは、SendとSyncがそれぞれ何を表すのか、これらがどう自動的に決まるのか、そして、なぜRcがこの境界を越えられないのか、という核心です。

第36章へようこそ。今日から、並行処理を扱う一連の章に入ります。最初のテーマは「スレッド」です。スレッドは、プログラムの中で独立して進む実行の流れのことです。1つのプログラムが複数の流れを同時に持つと、別々の処理が並行して進む。並行処理は、所有権の規律が新しい場面に置かれる領域です。これまで所有権は、1つの実行の流れの中で、値がいつ生きていつ解放されるかを決めてきました。スレッドが増えると、値が2つ以上の流れにまたがる可能性が出てくる。値が流れをまたぐとき、誰がそれを所有し、いつ解放するかを決める規律が要る。Rustはこれを、型と所有権の規律で扱います。今日扱うのは、スレッドの生成、スレッドの終了を待つ仕組み、そして、なぜスレッドに渡す値は所有権ごと渡さなければならないのか、という核心です。

第35章へようこそ。今日のテーマは「手続き的マクロ」です。これまでの3章で扱ってきたのは宣言的マクロでした。macro_rules!の宣言で、パターンと展開の組をルールとして並べる。入力のトークンがパターンに照らされ、対応する展開が呼び出し位置に差し込まれる。宣言的マクロには表現の限界があります。パターンと展開の対応で書ける範囲を超えた変換、たとえば構造体のフィールド名を文字列として取り出して別のコードに埋め込む、こうした処理は宣言的の枠を超える。これを扱うために用意されているのが、今日扱う手続き的マクロです。今日扱うのは、宣言的マクロの限界、手続き的マクロが解く問題、3つの形態、トークンストリームという界面、synとquoteによる分業、そして別クレートとしてコンパイルされる構造的な理由です。

第34章へようこそ。今日のテーマは「繰り返しと衛生性」です。前章で、フラグメント指定子がトークン列の中の特定の位置を捕捉する仕組みを見ました。式を1つ、識別子を1つ、型を1つ、それぞれ捕捉する。固定の個数なら、これだけで足りる。しかしマクロは、任意個のトークンを受け取りたい場面がある。vecマクロは要素を何個でも受け取って配列を作る。また、マクロが導入した変数の名前が、呼び出し側の変数の名前と衝突しないように、識別子のスコープにも工夫が要る。今日扱うのは、可変長のトークンを扱う繰り返し構文、繰り返しでは難しい変換を担う再帰的展開、マクロの識別子が呼び出し側に漏れない衛生性、そしてマクロ内のパスがクレート境界を越えても壊れない仕組みです。

第33章へようこそ。今日のテーマは「マクロのパターン」です。前章で、マクロ定義はパターンと展開の組であるルールの集まりだと見ました。呼び出し位置にあるトークン列がパターンに照らされ、一致したルールの展開部分が差し込まれる。ではパターンの中身はどう書くのか。ここで中心になるのが、フラグメント指定子と呼ばれる仕組みです。パターンの中の特定の位置に「ここは式が来る」「ここは識別子が来る」「ここは型が来る」と宣言することで、トークン列に意味の粒度を与える。今日扱うのは、フラグメント指定子の体系、特に万能だが粗い「任意のトークンツリー」の役割、指定子の後ろに何が来てよいかの制約、複数のルールがどう選ばれるかの順序、そして指定子の粒度の設計判断です。

第32章へようこそ。今日のテーマは「宣言的マクロ」です。これまでの章では、関数を使ってコードの構造を組み立ててきました。引数を取り、処理を行い、戻り値を返す。再利用したい処理を関数として切り出す。ほとんどの抽象は関数で書ける。しかし関数では書けないものがあります。要素の個数を決めずに配列を作る、引数の型に応じてフォーマットを組み立てる、ある構造体に対する一連のメソッドをまとめて生成する。こうした操作は関数の枠を出ている。これらを書くために、Rustにはマクロという別の仕組みが用意されている。今日扱うのは、マクロが関数では届かない領域を扱う仕組みであること、コンパイル時にコードを変換するという位置づけ、そして基本の道具であるmacro_rules!の構造です。

第31章へようこそ。今日のテーマはCargoです。Cargoはビルドツール、パッケージマネージャ、テストランナーを兼ねた、Rustに同梱されているツールです。コマンドの使い方は調べれば分かるので、本章では扱わない。扱うのは「Cargoがあることで、Rustの言語側で何が成立しているか」です。Rustは、コンパイラだけが用意されている言語ではない。言語仕様、コンパイラ、標準ツール、この3つが一体となって配布されている。標準ツールとしてCargoがあることが、Rustの言語そのものの設計判断にどう関わっているか。今日はその関係を扱います。

第30章へようこそ。ここまでの章では、型、所有権、参照、コレクションといった個々の仕組みを扱ってきました。これらを使ってプログラムを実際に組み立てると、コードは大きくなる。大きくなったコードを「どう配置し、何を外に見せ、どう参照するか」を決めるのが、モジュールシステムの役割です。Rustのモジュールシステムには3つの構文があります。モジュール宣言、public指定、use宣言の3つです。ソースコード上では、moduleを3文字に略してエム・オー・ディーと綴るのがモジュール宣言、publicを3文字に略してピー・ユー・ビーと綴るのがpublic指定、useをそのままユー・エス・イーと綴るのがuse宣言です。本章では、この3つの構文をそれぞれモジュール宣言、public指定、use宣言という名前で呼んでいきます。モジュール宣言は名前空間を組み立てる。public指定は何を外から見えるかを選ぶ。use宣言は別の場所の名前を短く参照するためにスコープに持ち込む。それぞれの機能は単純で、1文ずつで言い切れる。3つが別々の軸を扱うために、別々の構文として分かれている。今日扱うのは、それぞれが何をしているかと、3つを別々の軸として読むことが何を整理するか。構造の軸、境界の軸、名前の軸。この3つの分けで章を進めます。

第29章へようこそ。これまでに扱ったHashMapとHashSetには、共通する性質がありました。内部はハッシュテーブルで、要素はハッシュ関数によって決まる位置に置かれる。そのため、要素は挿入順にも整列順にも並ばず、イテレーションの順序は保証されない。個々の操作はほぼ一定時間で動くが、順序にまつわる操作は構造的に難しい。順序が必要な場面があります。キーが範囲で問い合わされる場合。たとえば「ある日付以降のすべてのエントリ」「キーが10から20の間にあるもの」。イテレーション順序が一定であることが望ましい場合。出力順を整えたい、結果を予測可能にしたい。最小のキーや最大のキーを高速に取り出したい場合。これらの場面のために用意されているのがBTreeMapとBTreeSetです。役割はHashMapとHashSetと同じく、ペアの対応表と要素の集合。違うのは内部構造で、ハッシュテーブルではなくBツリーと呼ばれる木構造を使う。今日扱うのは、Bツリーがどう順序を保つか、その代償は何か、求められるトレイトはなぜ変わるか、そして範囲クエリという固有の操作です。

第28章へようこそ。これまでの章では、Vecが連続した領域に要素を並べる構造、HashMapがハッシュ関数でキーと値を対応させる構造として扱ってきました。この2つはRustでよく使われるコレクションだが、すべての用途を覆えるわけではない。VecとHashMapには、それぞれの構造から来る向き不向きがある。Vecは連続配置のため、両端のうち末尾は高速だが、先頭への操作は重い。HashMapはペアを管理するため、あたいを持たない単純な「要素の集合」を表現するには余分な情報を持つことになる。これらの不足を埋めるために、VecとHashMapの構造を別の用途に特化させた派生形がある。今日扱うのは、HashSetとVecDeque。HashSetはHashMapを集合用に特化させたもの、VecDequeはVecを両端操作用に特化させたものです。それぞれが何を変えて、何を引き継いでいるかを構造から見ていきます。

第27章へようこそ。今日のテーマはEntry APIです。前章ではHashMapの内部構造と基本操作を扱いました。キーをハッシュ関数に通して整数を得て、その整数からテーブル上の位置を決め、スロットを確認してあたいを取り出す。挿入、取得、削除、存在確認、いずれも内部ではハッシュ計算とテーブル探索を組み合わせて動きます。今日扱うのは、この基本操作だけでは無駄が出てしまう典型的な場面と、その無駄を解消するために用意された別の操作です。「キーが存在していたら既存の値を変更する。存在していなければ新しいあたいを挿入する」という処理を、HashMapに対してどう書くか。素朴に書くと、同じキーに対するハッシュ計算と探索が複数回走ってしまう。これを1回で済ませるための仕組みがEntry APIです。今日はEntry APIが解決している問題、Entryという型の構造、or_insert、or_insert_with、and_modifyの動作、そしてEntry APIが借用とどう関わっているかを扱います。

第26章へようこそ。今日のテーマはHashMapです。前章で扱ったVecは、要素が連続して並んでいる構造でした。0番、1番、2番というインデックスで要素を取り出す。インデックスがあらかじめ整数として与えられているなら、即座に要素にアクセスできる。しかし扱いたい関係が「整数で並べたもの」ではない場合があります。ユーザー名と設定情報の対応、商品コードと在庫数の対応、英単語とその訳語の対応。キーになる側が文字列や任意の型で、そのキーに対応する値を引きたい。これを実現するのがHashMapです。今日はHashMapの内部構造、ハッシュ関数の役割、衝突の扱い、キーに要求される性質、操作の動作、イテレーション順序が保証されない理由を扱います。

第25章へようこそ。今日のテーマはVecの詳細、その中でも容量と成長です。Vecはこれまでの章でも何度か登場してきました。第20章では、Vecがスタックとヒープにまたがる型として、ヘッダ部分にポインタと長さと容量の3つを持つことを確認しました。要素を追加する基本的な動作は、第4章のイテレータの章で扱っています。今回はVec自身の動きを内側から扱います。容量とは何か、長さとどう違うのか。要素を追加するときに何が起きるのか。なぜ容量は約2倍に増えるのか。事前確保と縮小はどう動くのか。要素へのアクセスにどんな種類があるか。構造として理解すると、Vecの動きが予測可能になり、コストも見えるようになる。

第24章へようこそ。今日のテーマは「Weakと循環参照」です。第22章で扱ったRcは、参照カウントが0になった瞬間にヒープ上のあたいを解放する型でした。誰か1人でも所有者が残っている限り、あたいは生き続ける。この設計には1つの構造的な弱点があります。複数のRcが互いに相手を所有し合うとき、カウントがどの所有者から見ても1以上のままで、永久に0に達しない状況が起こり得る。誰もアクセスできなくなった後も、ヒープ上のあたいが解放されないまま残る。これが循環参照と呼ばれる問題で、メモリリークの典型的な発生源です。この問題を解くために用意されているのがWeakです。今日はWeakの構造、強い参照と弱い参照の違い、循環をどう解くか、Rcの内部に弱カウントがどう存在しているかを扱います。

第23章へようこそ。今日のテーマは「RefCellと内部可変性」です。前章で扱ったRcは、複数の所有者が同じヒープ上の値を共有できる型でした。しかしRcから取り出せるのは中身への不変参照だけで、可変参照は得られない。これは「可変参照は同時に1つだけ」という借用規則と整合させるための設計でした。それでも実用上、共有している値を変更したい状況は頻繁にあります。ツリー構造で複数のノードが共通の状態を更新する。あるオブジェクトの内部キャッシュを書き換える。こういう状況のために用意されているのが、内部可変性という枠組みです。今日はRefCellを通じて、内部可変性の構造、実行時の借用検査、パニックの条件、Rcとの組み合わせを扱います。

第22章へようこそ。今日のテーマは「Rc」です。RcはReference Countedの頭文字で、日本語にすれば参照カウントを持つ型ということ。前章で扱ったBoxは、ヒープ上のあたいに対して所有者が1人だけの型でした。ヒープを所有する型は所有者が1人というルールに従い、ムーブで所有権が移り、Copyトレイトを持たない。しかし、複数の場所から同じヒープ上のあたいを所有したい状況があります。グラフ構造で複数のノードが同じノードを指す。設定データを複数の処理が共有する。こういう構造を、所有者を1人に絞ったまま実現するのは難しい。このための型がRcです。今日はRcの内部構造、参照カウントの動き、cloneの意味、なぜ中身が読み取り専用なのか、なぜシングルスレッド専用なのかを扱います。

第21章へようこそ。今日のテーマは「Box」です。前章でスタックとヒープという2つの領域を扱いました。スタックは関数呼び出しに合わせて伸び縮みし、サイズがコンパイル時に決まるあたいを置く領域。ヒープは関数の生存期間と独立に確保解放され、サイズが実行時に決まるあたいを置く領域。StringやVecはこの2つの領域にまたがる型でした。スタック側にポインタと長さと容量の3つを持ち、ヒープ側に実データを持つ。ではStringのような「特定の中身に縛られた」二層構造ではなく、任意の型をヒープに置きたいときはどうするのか。そのための型がBoxです。今日はBoxの構造、Derefによる透過アクセス、Dropによる自動解放、そしてBoxが構造として必要になる場面を扱います。

第20章へようこそ。今日のテーマは「スタックとヒープ」です。ここまでの章で「スタック上のポインタ」「ヒープ上のデータ」という言葉を何度か使ってきました。所有権の章ではStringの代入時にスタック上の情報が渡されると話し、文字列の章ではヒープにバイト列が置かれると話した。これらの説明は、すべてスタックとヒープという2つの領域があることを前提にしていた。今日はその2つの領域そのものを扱います。2つの領域はそれぞれどう動き、なぜ分かれているのか。そしてここまで学んだムーブやCopyトレイトが、なぜそういう形になっているのか。

第19章へようこそ。今日のテーマは「UTF-8」です。Stringも文字列スライスも、中身はUTF-8でエンコードされたバイト列でした。ここまでの章で何度か触れてきましたが、深く踏み込んでいなかった。文字列を扱うとき、「文字」と「バイト」の間にずれがあることが、さまざまな場面で現れる。長さの意味、インデックスの禁止、イテレートの方法、絵文字の扱い。これらすべての根にあるのがUTF-8の性質です。今日はその性質を見ていきます。

第18章へようこそ。今日のテーマは「文字列の変換」です。前の2章で、文字列が2つの型に分かれることを見ました。所有するStringと、借りる文字列スライス。2つの型がある以上、その間を行き来する必要が生じます。文字列スライスからStringを作る場面。Stringから文字列スライスを取り出す場面。この2方向の変換は、形は似ていますが中身はまったく違う。片方はヒープ割当てを伴う重い操作、もう片方は参照を組み立てるだけの軽い操作です。この非対称な関係を今日は見ていきます。

第17章へようこそ。今日のテーマは「文字列スライス」です。前章でStringを扱いました。ヒープに持つ所有権付きの可変長文字列です。文字列のもう一方の型が、今日の主役、文字列スライス。借りている文字列、参照としての文字列です。表記は＆str。str単体ではほぼ使われず、参照の形でだけ現れる。所有を持たず、読み取り専用で、サイズも固定されている。Stringと対になる存在として理解します。

第16章へようこそ。今日のテーマは「String」です。多くのプログラミング言語では、文字列は1つの型で扱われる。しかしRustでは、文字列を2つの型に分けている。所有する文字列と、借りている文字列。所有する方がString。借りる方が文字列スライスと呼ばれる別の型。この2つの区別は、所有権と借用の区別を文字列にも持ち込んだ結果です。今日はStringを見ていきます。ヒープに持つ所有権付きの、可変長文字列です。

第15章へようこそ。今日のテーマは「ライフタイム省略と'static」です。前の2章でライフタイム注釈の書き方を学びました。しかし、実際のRustコードを見ると、ライフタイム注釈が書かれている関数は意外と少ない。参照を受け取って参照を返す関数でも、注釈なしで書かれていることが多い。これは、コンパイラが自動的に注釈を補っているからです。この補完の仕組みをライフタイム省略規則と呼ぶ。もう1つ、今日扱うのは'staticという特別なライフタイム。プログラムの実行中、ずっと有効であり続ける参照のライフタイムです。この2つを理解すれば、ライフタイム編の基礎が完成します。

第14章へようこそ。今日のテーマは「関数と構造体のライフタイム」です。前章でライフタイムの概念を学びました。参照には有効期間があり、それが型システムの一部として扱われる。今日は、ライフタイム注釈を実際に書く場面を見ていきます。関数が参照を受け取って参照を返すとき。構造体が参照をフィールドに持つとき。メソッドを定義するとき。それぞれで注釈がどう書かれ、何を意味するかを見ていきます。

第13章へようこそ。今日のテーマは「ライフタイム」です。第1章で所有権と借用を学びました。値の所有者は常に1つ。参照を作ることで値を借りられる。借りている間、元の値は動かせない。しかし、第1章では触れなかった問いがあります。参照はいつまで有効なのか。参照が指している先の値が消えたら、参照はどうなるのか。この問いに答える仕組みが、ライフタイムです。ライフタイムは、参照の有効期間を型システムの一部として扱う仕組み。Rustの安全性保証の中核をなす概念です。

第12章へようこそ。今日のテーマは「関連型」です。第4章でイテレータを学んだとき、Itemという言葉が出てきました。イテレータが返す要素の型。整数のイテレータなら整数。文字列のイテレータなら文字列。このItemは、Iteratorトレイトの中で定義された型です。トレイトの中に型が定義されている。これが関連型。関連型は、第10章の型パラメータと似た役割を持つように見える。どちらも「後から決まる型」を表現する。しかし、型パラメータと関連型には構造的な違いがあります。なぜRustは両方を用意したのか。どう使い分けるのか。今日はこの違いを見ていきます。