最新記事公開時にプッシュ通知します
連結リストを実装して学ぶRustの所有権
2026年1月19日
Rust.Tokyo オーガナイザー
Sansan株式会社のソフトウェアエンジニア。金融機関向けのリスク管理計算機の開発に携わってから、しばらく広告配信の仕事に従事した。前職のUSの企業では実務でRustを利用した。本業のかたわら、Rustの国内カンファレンス「Rust.Tokyo」の運営や、いくつかのOSSの開発や貢献を行っている。共著で『実践Rustプログラミング入門』（秀和システム）、『RustによるWebアプリケーション開発』（講談社サイエンティフィク）など。また、『Web開発で学ぶ最新言語Rust』（日経クロステック）の連載を持つなどした。
※アイキャッチとプロフィールに使用しているアイコンは「めぶイカメーカー」を使用し生成しております
GitHub: https://github.com/yuk1ty
Rustに入門した際最初に立ちはだかる壁は、Rust特有のメモリ管理です。Rustはメモリ安全なプログラミング言語だと言われていますが、メモリ管理はほかのプログラミング言語と比べて独特です。それがRustのイノベーションのポイントでもあるわけですが、初心者のうちのとっつきにくさの原因でもあります。
この記事では、いくつかの題材を通じてRustのメモリ管理を学んでいきます。いわゆる連結リスト（Linked List）と呼ばれるデータ構造を通じてRustに特徴的なメモリ管理を学びます。最初は単方向連結リスト（Singly Linked List）からスタートし、その後元の実装を拡張する形で双方向連結リスト（Doubly Linked List）を実装します。
なぜ連結リストなのかというと、2種類の連結リストを実装する過程でRustのさまざまなメモリ管理機構や、unsafeと呼ばれる機能群まで足を伸ばして実装する必要があるからです。
この記事を終えたころには、Rustのメモリ管理機構については一通り学習し終えていることでしょう。
リポジトリ
今回使用するサンプルコードは下記のGitHubリポジトリにまとめています。合わせてご覧ください。
https://github.com/yuk1ty/learn-ownership-with-linked-lists
基礎編: 単方向連結リストの実装でメモリ管理の基礎を学ぶ
最初に単方向連結リストと呼ばれるデータ構造を実装して、「スタック」と「ヒープ」と呼ばれるメモリ領域を意識したプログラミングを体感していきます。Rustでコードを書く場合、スタックとヒープの知識がなければ始まりません。加えてRustのメモリ管理で欠かせない、もう一つの機能「スマートポインタ」も合わせて理解していきます。
単方向連結リストとは
単方向連結リストは、要素と次の要素への参照を持つ「ノード」を複数個連結させて構成されるデータ構造です。挿入や削除の操作に強く、計算量が小さく保てるのが特徴です。
この記事では、単方向連結リストを次の2つの要素で行います。
1. List: 最初のノードへの参照を保持する構造体
2. Node: 自身の値と、次のノードへの参照を持つ構造体
「次のノードへの参照」について補足ですが、自ノードが終端で次のノードを持たないケースがありえます。そのためこのポインタはNULLを考慮している必要があります。RustではOption型を使用することでNULLを考慮できます。
Rustによる最初の実装
これらを踏まえると、Rustでも次のように実装できそうです。これでコンパイルが通りそうに見えます。
/// 単方向連結リスト全体を表現する構造体
struct List<T> {
head: Link<T>,
}
/// 次のノードへのポインタを表現する型
type Link<T> = Option<Node<T>>;
/// ノードを表現する構造体
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
/// 新しく単方向連結リスト用のインスタンスを生成する関数
fn new() -> Self {
List { head: None }
}
}
しかし実際にコンパイルしてみるとこのコードではコンパイルが通りません。次のコンパイルエラーメッセージを見ることになるでしょう。
error[E0072]: recursive type `Node` has infinite size
--> src/bin/singly-first.rs:7:1
|
7 | struct Node<T> {
| ^^^^^^^^^^^^^^
8 | elem: T,
9 | next: Link<T>,
| ------- recursive without indirection
|
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
|
9 | next: Box<Link<T>>,
| ++++ +
コンパイルを通せる実装
いったんまずはコンパイルを通してみましょう。コンパイラの指示通りにNodeをBoxでラップする実装に書き換えてみます。すると、コンパイルが通るようになります。
struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
fn new() -> Self {
List { head: None }
}
}
Boxは中の値をヒープ上に確保する「スマートポインタ」です。Rustの文脈でいうスマートポインタとは、ポインタをラップして、さらになんらかのケイパビリティ（機能ないしは能力）を追加したラッパー型のことを指します。Boxの持つケイパビリティは「ヒープ領域に値を割り当てる」です。
では、なぜヒープ領域に値を割り当てるように調整しただけでコンパイルを通せるようになったのでしょうか？ この一連の修正が必要となった背景を理解するためには、「再帰型Nodeはサイズが無限である」というコンパイルエラーの意味を理解しなければなりません。そのためには、メモリのスタック領域とヒープ領域について改めて学ばなければなりません。これらはRustのメモリ管理を理解する上で重要な要素のひとつであるため、簡単におさらいしておきましょう。
スタックとヒープ
メモリの領域にはいくつか目的別に領域があります。この中にスタック領域とヒープ領域が含まれています。
スタック領域は、いわゆるスタックというデータ構造にならったメモリ管理の仕方をするメモリ領域です。スタック領域の特徴は一般的には、データ構造の方のスタックがそうであるように、データへのアクセスが高速なことです。単に最後にスタックに追加された値を一番上から取り出せばよいためです。
一方で、スタック領域に格納するデータはすべて既知の固定サイズでなければなりません。つまりコンパイル時にその値のサイズがわかっていなければならないということです。
なおRustの値は、通常何も指定しなければスタック領域に格納されていきます。
ヒープ領域はスタックとは異なり、動的に都度確保されるメモリ領域です。必要に応じて領域のサイズを大きくしたり小さくしたりすることができます。なので、実行時に必要な分だけメモリ領域を確保して使用するといった使い方ができます。
ヒープ領域のデータのアクセスはポインタをたどりながら行われるため、スタック領域へのデータアクセスに比べれば相対的に低速なことが多いと言えます。スタック上に確保したヒープ領域へのポインタが格納されており、それをたどってデータにアクセスします。
Rustでは、Vec<T>やStringなどは値をヒープ領域に格納します。ヒープ領域に値を格納したい場合は、ユーザーが明示的に操作を行う必要があります。
先ほどの最初のコードがコンパイルエラーになったのは、コンパイル時点ではList<T>やNode<T>がどのくらいのメモリ領域を必要とするかわからないからです。これらの型は、同一の型をフィールドに含む型になっています。中に2つのノードが含まれていれば2つ分必要としますし、3つノードが含まれているなら3つ分必要としますが、要するに無限個あれば無限個のノードが入る可能性があるのです。
したがって、実際にいくつ入ってくるかはコンパイル時には決定できず、スタック領域の確保に必要なメモリサイズを計算できません。この場合実行時に必要なメモリ領域を計算して確保する必要があるため、ヒープ領域に値を格納するようBox<T>を使って明示しなければならなかった、ということになります。
イメージを掴むための説明は、The Rust Programming Language（通称: TRPL）の4.1節で読むことができます。併せて読んでおくと理解が深まるでしょう。
4.1 所有権とは？
https://doc.rust-jp.rs/book-ja/ch04-01-what-is-ownership.html
ムーブ
さて次は、リストの初期化、pushやpop、peekといった基本的な操作を実装してみます。各操作は次のように行います。
・push: リストの先頭にノードを追加する。
・pop: リストの先頭から値を取り出す。なかった場合はNoneを返す。
・peek: リストの先頭の値を見る（取り出さない）。なかった場合はNoneを返す。
実装した例は下記です。
impl<T> List<T> {
fn new() -> Self {
List { head: None }
}
/// 先頭に要素を追加する
pub fn push(&mut self, elem: T) {
// 新しいノードをヒープに確保する
// Box::new でヒープにメモリを割り当て、ポインタをスタックに保持
let new_node = Box::new(Node {
elem,
// self.head.take()で既存のheadを取り出し、新ノードのnextに設定
// takeによりself.headはNoneになる
next: self.head.take(),
});
// 新ノードをリストの先頭に設定
self.head = Some(new_node);
}
/// 先頭の要素を取り出す
pub fn pop(&mut self) -> Option<T> {
// self.headからノードを取り出す（takeで元の値はNoneになる）
// map()でOption<T>の中身がある場合のみ処理を実行
self.head.take().map(|node| {
// 取り出したノードのnextをリストの新しいheadに設定
// Boxの所有権が移動するため、旧headのメモリは自動的に解放される
self.head = node.next;
// ノードから要素を取り出して返す
// nodeはここでスコープを抜けるが、nextは既に移動済みなので安全
node.elem
})
}
/// 先頭の要素を参照する（取り出さないので参照が返る）
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|node| &node.elem)
}
}
この実装で重要なのは、pushやpopの実装内部に現れるOption::takeという関数です。
Option::takeは「Optionから値を取り出し、元の場所にNoneを埋めておく」という操作を行います。self.head.take()の結果、headに値があった場合はSome(T)が取り出され、self.headにはNoneが代わりに埋められます。この関数は、構造体の一部のフィールドから一時的に所有権を得たい場合に利用されます。今回のケースでは、List<T>の所有権は奪わずに内部のフィールドであるheadのみをムーブさせるために使われています。
ドロップ
Dropトレイトは変数がスコープを抜けた際に実行させる処理を実装しておくことのできる、Rust標準ライブラリのユーティリティトレイトの一つです。ユーティリティトレイトにはほかに、Clone（値をクローンできるようにする）、Copy（値をコピーできるようにする）、Deref（値の参照外しをできるようにする）やDefault（値のデフォルト値を設定する）などがあります。
また、Rustでは値がスコープを抜けるとき、その値が所有しているリソース（ヒープメモリ、ファイルハンドルなど）を後始末する仕組みがあり、これを一般に「ドロップ（drop）」と呼びます。他のプログラミング言語ではRustのドロップに似たような概念として、「デストラクタ」と呼ばれるものを持つプログラミング言語もあります。
通常Dropトレイトの実装された型を使用する限り、ドロップが走るタイミングで再帰的にドロップが走るため、複雑に入り組んだ構造体であってもDropトレイトを自分で実装する必要はありません。自動的に走るので普段は意識することのない処理ではあります。
一方で今回使用しているBoxは、Boxの中の値がドロップされた後には、中の値をさらに再帰的にたどってはドロップしてくれません。今回のように再帰的なデータ構造を用意した場合には、自前でこの問題を回避できるような実装を用意しておく必要があるのです。
下記の実装では、先に紹介したOption::take関数を使って、リストのheadの値をまずムーブさせ、さらに次のノードの値のムーブを起こすことで、実質的なドロップを再帰的に走らせていき、この問題を回避しています。
impl<T> Drop for List<T> {
fn drop(&mut self) {
// リストの先頭ノードを取り出す（self.headはNoneになる）
let mut cur = self.head.take();
// ノードが存在する限りループ
while let Some(mut boxed_node) = cur {
// 現在のノードのnextを取り出し、curに移動
// これにより現在のノードへの参照がなくなり、自動的に解放される
// takeを使うことで、明示的にリンクを切断し、スタックオーバーフローを防ぐ
cur = boxed_node.next.take();
// boxed_nodeはここでスコープを抜け、nextが既に移動済みなので安全にドロップされる
}
}
}
発展編: 双方向連結リストを実装してメモリ管理の真髄に迫る
次に双方向連結リストを実装しながら、Rustの所有権・借用システムと、それがデータ構造の設計に与える制約について見ていきます。
双方向連結リストでは、各ノードが前後のノードを参照するため、ひとつのノードが複数の参照元から共有される構造になります。このような構造は、単一の所有者と静的に検証可能な参照関係を前提とするRustの基本的な所有権モデルでは、そのまま表現することができません。加えてノードの追加や削除の際には、共有されているノードの内部状態を更新する必要がありますが、これはコンパイル時に安全性を保証できず、通常の参照では許可されません。こうした問題を解決するためには、特別なスマートポインタが必要になります。
双方向連結リストとは
双方向連結リストは、単方向連結リストの各ノードが「次のノードへの参照」に加えて「前のノードへの参照」を持つようになった連結リストです。そして前のノードへの参照を持たなければそのノードは先頭、次のノードへの参照を持たなければそのノードは末尾ということになります。
Rustでの実装方針としては基本的には単方向連結リストと変わりなく、LinkとNodeの二つの構造体を用意し、それぞれに前後のノードへのポインタを持たせるなどを実装するのみです。
Rustによる最初の実装
素直に実装するのであれば、単方向連結リストにさらにtailとprevの二つをそれぞれ追加すれば完成しそうです。実際、データ構造を組み上げるだけであればtailをListに追加し、prevをNodeに追加するだけでコンパイルそれ自体は通せます。
struct List<T> {
head: Link<T>,
tail: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
prev: Link<T>,
next: Link<T>,
}
impl<T> Node<T> {
fn new(elem: T) -> Self {
Node {
elem,
next: None,
prev: None,
}
}
}
続いてpushやpopといった各操作を実装します。先頭に要素を追加する「push_front」という関数を追加してみましょう。
impl<T> List<T> {
fn new() -> Self {
List {
head: None,
tail: None,
}
}
// ここが要は問題になる
fn push_front(&mut self, elem: T) {
let mut new_node = Box::new(Node::new(elem));
match self.head.take() {
Some(mut old_head) => {
old_head.prev = Some(new_node);
new_node.next = Some(old_head);
self.head = Some(new_node);
}
None => {
self.tail = Some(new_node);
self.head = Some(new_node);
}
}
}
}
ただしここで問題が露呈します。このコードをコンパイルすると、次のコンパイルエラーが発生します。
error[E0382]: assign to part of moved value: `*new_node` --> src/bin/doubly-first.rs:38:17 | 34 | let mut new_node = Box::new(Node::new(elem)); | ------------ move occurs because `new_node` has type `Box<Node<T>>`, which does not implement the `Copy` trait ... 37 | old_head.prev = Some(new_node); | -------- value moved here 38 | new_node.next = Some(old_head); | ^^^^^^^^^^^^^ value partially assigned here after move error[E0382]: use of moved value: `new_node` --> src/bin/doubly-first.rs:43:34 | 34 | let mut new_node = Box::new(Node::new(elem)); | ------------ move occurs because `new_node` has type `Box<Node<T>>`, which does not implement the `Copy` trait ... 42 | self.tail = Some(new_node); | -------- value moved here 43 | self.head = Some(new_node); | ^^^^^^^^ value used here after move
このコンパイルエラーは、new_node を old_head.prev に渡してしまった後で、さらに new_node.next を操作しようとしているために発生しています。Rustにおいて、Box はその中身の唯一の所有者でなければなりません。したがって、一度どこかへムーブしてしまった new_node を、元の場所から操作することはできないのです。
今回の実装が直面しているのは、Rustの「値の所有者は常に一人である」という鉄の掟です。双方向リストでは、あるノードが「次のノード」から指されると同時に「リストのhead（または前のノード）」からも指される必要があります。つまり、「二つの場所から同時に所有される」ことが構造上避けられません。鉄の掟を守れないのです。
これはボローチェッカーの不備ではなく、むしろメモリ安全性を担保するためのボローチェッカーの正当な制約です。
しかし一方で、他のプログラミング言語では双方向連結リストを実装できるのに、Rustでだけ実装できないということはありえるのでしょうか？ そんなことはありません。
一つの値に複数の所有者が紐づきつつ、可変な操作も同時に行えるようなケースをRustで扱うためには、別のスマートポインタの力を借りる必要があります。RcとRefCellがそれにあたります。
RcとRefCellを使った実装
Rcは参照カウンタ（Reference Counter）の略です。参照カウンタは他のプログラミング言語でも見られる機構で、値への参照が増えれば内部のカウンタを1増やし、参照が削除されるとカウンタを1減らすというケイパビリティを持つスマートポインタです。その値への参照がいくつあるかを保持しておき、数が0になったら値もまとめてドロップします。Rustにおける意味合いでは、これは所有者が複数名いても構わないことを意味します。これによりRustの所有権ルールの一つである値の所有者は常に一人のみという制約を少し緩和させることができます。
Rcは値を複数箇所から共有できるようにしますが、そのままでは中身を書き換えることはできません。これでは困ってしまうのが今回のケースです。ノードをリストに追加するタイミングで、新しいノードのnextを更新したいからです。ここで導入されるのが「内部可変性」という概念です。内部可変性とは、いわゆる不変参照（&Tのこと）を介しても中のデータを変更できるようにする仕組みのことです。コンパイル時にはいったん変更の安全性チェックを飛ばしておき、実行時に安全性チェックをかけるよう変更する仕組みです。
内部可変性はRefCellというスマートポインタを用います。先ほどの参照カウンタと重ねて、Rc<RefCell<T>>という型を宣言します。こうすると、「内部可変性をもち」「複数の所有者をもつことができる」というケイパビリティをT型に対して与えられます。双方向連結リストではこう宣言すると、push_frontをはじめとするリストへの変更操作を実装できます。
RcとRefCellを使って実装し直してみた例が次です。
use std::{
cell::{Ref, RefCell},
rc::Rc,
};
struct List<T> {
head: Link<T>,
tail: Link<T>,
}
type Link<T> = Option<Rc<RefCell<Node<T>>>>;
struct Node<T> {
elem: T,
next: Link<T>,
prev: Link<T>,
}
impl<T> Node<T> {
fn new(elem: T) -> Self {
Node {
elem,
next: None,
prev: None,
}
}
}
impl<T> List<T> {
fn new() -> Self {
List {
head: None,
tail: None,
}
}
// Rc<RefCell<Node<T>>> を使うことで、複数の所有権と可変借用を実現
fn push_front(&mut self, elem: T) {
// 新しいノードを作成し、Rc<RefCell<>>でラップする
// Rc: 複数の所有者を持てる参照カウント型
// RefCell: 実行時に可変借用のチェックを行う型
let new_node = Rc::new(RefCell::new(Node::new(elem)));
// self.headからリンクを取り出す（takeでOptionの中身を移動し、元の値はNoneになる）
match self.head.take() {
// リストに既存の要素がある場合
Some(old_head) => {
// 旧headの前方リンク(prev)を新ノードに設定
// borrow_mut()でRefCellの可変参照を取得
old_head.borrow_mut().prev = Some(new_node.clone());
// 新ノードの次のリンク(next)を旧headに設定
new_node.borrow_mut().next = Some(old_head);
// リストのheadを新ノードに更新
self.head = Some(new_node);
}
// リストが空の場合
None => {
// tailとheadの両方を新ノードに設定
// clone()でRcの参照カウントを増やす
self.tail = Some(new_node.clone());
self.head = Some(new_node);
}
}
}
}
続いてpop_frontやDropトレイトといった処理も追加していきましょう。
ところで今回、Dropトレイトを実装する意味について少し解説しておきましょう。ちなみにここからは少々踏み込んだ話なので、次のセクションまで飛ばし読みをしても構いません。
実は、参照カウンタには循環参照問題という弱点があります。参照カウンタは循環参照が含まれてしまうと、お互いがお互いにカウントを進め続け、一向にカウントをゼロにできず値をドロップさせられない事象が起こります。メモリリークが起こるケースがあるのです。
そのため循環参照がありえる場所には弱参照Weak<T>をRc<T>の代わりに使用することがあります。これを利用すると、Rcの通常の参照カウンタとは別に弱参照用の参照カウンタを用意します。Rc側の参照カウンタが0になると弱参照カウンタが仮に0でなかろうと解放されるため、これにより循環参照問題を防ぐことができるようになっています。
双方向連結リストの実装では誤って循環参照を発生させてしまう可能性が高く、Dropトレイトでこれを発生させないような処理を追加しています。たとえばListのtailをWeak<T>に変えておくことで防ぐ手はよく使われます。今回の実装ではDropトレイトでpop_front関数を呼び出すことで循環参照問題を実質的に回避させています。これにより、Weak<T>を使うことなくList<T>を定義できているというわけです。
// impl<T> List<T> {
fn pop_front(&mut self) -> Option<T> {
// self.headからリンクを取り出す（takeで元の値はNoneになる）
// map()でOption<T>の中身がある場合のみ処理を実行
self.head.take().map(|old_head| {
// 旧headのnextリンクを取り出す（循環参照を切るためtakeで移動）
if let Some(next_node) = old_head.borrow_mut().next.take() {
// 次ノードのprevリンクを削除（循環参照を切る）
// これにより old_head への参照が1つ減る
next_node.borrow_mut().prev.take();
// リストのheadを次ノードに更新
self.head = Some(next_node);
} else {
// nextがない場合はリストが空になるのでtailもクリア
self.tail.take();
}
// Rc::try_unwrap: Rcの参照カウントが1の場合のみ中身を取り出せる
// ok().unwrap(): Result<T, E>をOption<T>に変換してから中身を取り出す
// into_inner(): RefCell<T>からTを取り出す
// .elem: Nodeから要素を取り出して返す
Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
})
}
// }
impl<T> Drop for List<T> {
fn drop(&mut self) {
// ここでpop_frontを使い、明示的に次ノードのprevをNoneにしていく処理を行い、
// 最後にRc::try_unwrapを行い明示的にサイクルを壊していることから、循環参照を防ぎメモリリークを防げている。
while self.pop_front().is_some() {}
}
}
RcやRefCellを使用するメリットやデメリット
両者を使用して実装する最大のメリットは、通常のRust（safeなRust。つまり、unsafeを使用しなくて良いこと）の範囲で双方向連結リストを記述できるようになる点でしょう。
一方で、スマートポインタの中には実行時チェックや参照カウント更新など、用途に応じたオーバーヘッドを伴うものがあります。たとえば、RefCellはborrow/borrow_mutのたびに実行時の借用チェックを行います。これにより、unsafeで同等の仕組みを自前実装した場合と比べて（あるいは設計を変えて静的に表現できた場合と比べて）、追加のコストが発生します。
読者への課題
・unsafeを使ってRc<RefCell<T>>を用いない双方向連結リストを実装する。
・双方向連結リストをGhostCellで実装する。
・その他さまざまな操作を実装してみる。
・簡単なアプリケーションを実装してみる。
unsafeを使ってRc<RefCell<T>>を用いない双方向連結リストを実装する
Rc<RefCell<T>>でカバーできるユースケースであればよいのですが、採用したことによって発生するオーバーヘッドが気になる場合はそもそも採用が難しくなります。そういう場合には、生ポインタを使って実装することになります。unsafeの出番というわけです。ちなみに「unsafe」というのは安全でないコードという意味ではなく、単にRustコンパイラによる自動的な安全性検証の支援を受けられないため、プログラマが手動で安全性の保証をする必要があり、コンパイラはその前提に立つという程度の意味合いです。
双方向連結リストをunsafeで実装する場合、まずRc<RefCell<Node<T>>>を可変生ポインタである*mut Tに変更します。ノード間のポインタは、type Link<T> = Option<*mut T>とすることで実装できます。
struct List<T> {
head: Link<T>,
tail: Link<T>,
}
type Link<T> = Option<*mut Node<T>>;
struct Node<T> {
elem: T,
next: Link<T>,
prev: Link<T>,
}
unsafeバージョンでは、push_frontやpop_frontといった操作の際、メモリを手動で管理することになります。とくに古いノードと新しいノードのそれぞれの参照先の付け替えのタイミングで*old_nodeのような生ポインタの参照外しが必要になりますが、ここがunsafeな操作にあたります。
impl<T> List<T> {
fn push_front(&mut self, elem: T) {
unsafe {
let new_node = Box::into_raw(Box::new(Node::new(elem)));
match self.head {
Some(old_head) => {
(*old_head).prev = Some(new_node);
(*new_node).next = Some(old_head);
self.head = Some(new_node);
}
None => {
self.tail = Some(new_node);
self.head = Some(new_node);
}
}
}
}
}
リポジトリにサンプル実装を用意しておいたので、ぜひご自身でもチャレンジの上、答え合わせをしてみてください。コメントに解説をいくらか残してあるので、理解の助けになるでしょう。
RcやRefCellのオーバーヘッドをなくすGhostCell
GhostCellという手法を用いると、unsafeに頼らずともこれらのオーバーヘッドをなくすことができます。この手法は、値の内部可変性の管理をコンパイル時に型レベルで行えるようにしたものです。GhostCellを用いるとRustのボローチェッカーが苦手とするような今回の双方向連結リストをはじめとするデータ構造を、ボローチェッカーの恩恵を受けながらunsafeなしに実装できるようになります。
元々は「GhostCell: Separating Permissions from Data in Rust」という論文にオリジナルのアイデアが掲載されており、発表当時は少し話題になりました。GhostCellそれ自体はghost-cellというクレートで実装内容が提供されており、これとTyped Arenaというクレートを組み合わせると双方向連結リストを実装できます。Typed Arenaは、メモリに割り当てたオブジェクトを一度に同じタイミングで破棄することのできる機能を持つクレートです。
GhostCellを使うと、双方向連結リストは次のようなデータ構造に変わります。RcやRefCellを使用する必要はなくなったのにも関わらず、unsafeを利用する必要もないことがわかります。
use ghost_cell::{GhostCell, GhostToken};
use typed_arena::Arena;
struct List<'arena, 'id, T> {
arena: &'arena Arena<GhostCell<'id, Node<'arena, 'id, T>>>,
head: Link<'arena, 'id, T>,
tail: Link<'arena, 'id, T>,
}
type Link<'arena, 'id, T> = Option<&'arena GhostCell<'id, Node<'arena, 'id, T>>>;
struct Node<'arena, 'id, T> {
elem: T,
prev: Link<'arena, 'id, T>,
next: Link<'arena, 'id, T>,
}
双方向連結リストの実装で問題になるpush_frontなどのリストに対する可変操作を行う関数も、次のようにunsafeなしで実装できるようになっています。またGhostCellの使用においては、borrow(token)はコンパイル時に解決されるため、RefCell使用時に発生していたような実行時のオーバーヘッドも一切発生しなくなるのが特徴です。
impl<'arena, 'id, T> List<'arena, 'id, T> {
fn push_front(&mut self, elem: T, token: &mut GhostToken<'id>) {
let new_node = Node::new(elem, self.arena);
match self.head {
Some(old_head) => {
old_head.borrow_mut(token).prev = new_node;
if let Some(node) = new_node {
node.borrow_mut(token).next = Some(old_head);
}
}
None => {
self.tail = new_node;
}
}
self.head = new_node;
}
}
詳しいGhostCellの説明やリストの実装の全体像はGitHubリポジトリをご覧ください。
Rustのボローチェッカーはプログラミング言語研究の叡智の結集であると同時に、GhostCellに代表されるように、まだまだ発見されていない使われ方があります。今後研究が進みさらなるデータ構造やボローチェッカーの使い方が発見されたり、あるいはボローチェッカーそのものの使い心地が改良されたりするかもしれません。
その他さまざまな操作を実装してみる
今回は単方向連結リスト、双方向連結リストともに一部の操作しか実装する例を示せませんでした。たとえば次のような操作を実装してみると、よりリストを実用的なものに近づけられるのではないでしょうか。
・リストから要素をひとつ削除する。
・イテレータを実装する。
・双方向連結リスト向け
・push_back、pop_backを実装する。
・DoubleEndedIterator（最後尾から前に向かって要素を走査できるイテレータ）を実装する。
簡単なアプリケーションを実装してみる
最後に、このデータ構造を利用して何かしらのアプリケーションを実装してみるとおもしろいでしょう。
連結リストはたとえば、テキストエディタの「元に戻す」「やり直し」やブラウザの「戻る」「進む」といった履歴管理の機能として利用されることがあります。これらのアプリケーションでは、ユーザーが履歴をたどっている最中に別の操作をして新しい歴史を書き込むことが頻繁に発生しますが、連結リストはこうしたリストの途中に値を書き込んだり、途中の値を削除したりする操作に強いです。
ぜひ一度ご自身で実装してみるとおもしろいのではないでしょうか。
まとめ
この記事では、二つの連結リストの実装を通じてRustのメモリ管理について学びました。Rustにはボローチェッカーというメモリ安全性を担保するための強力な機能がありはするのですが、ときにボローチェッカーの制約に引っかかってしまうケースがあることを学びました。
そうしたケースでは、safe Rustで書き続けるうちは、スマートポインタのように実行時に実際の状況を確かめてから値に対する特定の操作を許可する機構を利用する必要があります。スマートポインタが行うような実行時のチェックや追加の裏の操作を嫌う場合、unsafe Rustを利用しなければなりません。その場合、安全性の担保は書き手であるプログラマの責任になります。
読者課題として、unsafe Rustによる実装と、GhostCellという研究を紹介しました。とくにGhostCellは内部可変性の課題をコンパイル時に解決できる優れもので、スマートポインタが乗せるオーバーヘッドを回避できる点が魅力的です。
この記事の内容をこなせばだいたいRustのメモリ管理は習熟できたと言えると思いますが、扱わなかったトピックもまだまだあります。そうしたトピックはたとえばRust公式ドキュメントやRust Nomiconと呼ばれるドキュメントに記載がありますので、ぜひ併せてご覧ください。
参考文献
・『プログラミングRust』
・『詳解Rustプログラミング』
・『アルゴリズムイントロダクション第4版』
また、この記事はRustで双方向連結リストを実装する過程を通じて、Rustの所有権システムを深く学ぶことのできる「Learning Rust With Entirely Too Many Linked Lists」というチュートリアルに多くを依っています。
関連記事
Rust.Tokyoオーガナイザー・豊田優貴が薦めるRust本6選
アウトプットのお題に選ぶ、奥深い自作「TODOアプリ」。mattn氏が教える、さらなる技術力の向上を目指すためのノウハウとは
気合いや根性では不可能。継続的アウトプットにつながるモチベーション管理術
人気記事
5億画素だがUSBポートなし。人間という「デバイス」に接続し、脳内イメージを画像化する技術
React状態管理ライブラリの選択指針：「ローカル/グローバル/サーバー」における使い分けの基準
【2/4(水)オンライン開催！】型定義＆インタラクションテストでAIフロントエンド開発のガードレールを整備する
