前回の記事を書いてから、考えてるだけじゃだめだなとすこし書いてみたところいろいろわかった。
Rcによるリスト
Rcはリファレンスカウントで管理できる。RcはWeakをつくれるので、たとえばnext方向にRcをつなげておき(先頭ノードはリスト本体が保持)、prev方向へはWeakを持たせればいいのではないか？ と考えてみたのだった。
やってみたところこの方針では書けないということがわかった。Rcの参照先は基本的には更新ができない。ノードを追加したらprevやnextを書き換えないといけないけど、書き換えができない。書き換えをするには mutable なリファレンスを一時的に獲得する必要があるが、weakも含めたリファレンスカウンタが1でないといけない(これは安全性のためだろう)。prevとnextで基本的にノードにはstrongが1つとweakが1つ常にあるので、mutableなリファレンスを獲得できない。
なのでこの方針で書くことはできないのだった。マジで？
Arc / mutex によるリスト
ArcはRcのようなリファレンスカウンタだが非同期でアクセスできるようになっている。mutexと組み合わせると一時的に書き換えができたりする。どう考えてもオーバーヘッドが大きいから現実的じゃないけど、これならRcの問題は解決されるんじゃないだろうか？
解決される、というふうには思う。だが問題があった。要素の参照を返せないのだ。
たとえば、先頭要素を返す front() メソッドを書いてみたとする。こんな感じになる。
pub fn front(&self) -> Option<T> {
if let Some(n) = &self.head {
let node = n.lock().unwrap();
Some(node.element.clone())
} else {
None
}
}このコードでは結果の値を clone して返している。単純に&node.elementとする場合、そのライフタイムはnodeのライフタイムに縛られる(Mutexのlockというのはそういうものだ)。なので返される値はifの中が終わった瞬間に無効になるのでコンパイルできない。
こういうインタフェースを実装していくのは可能だが、cloneできるものに限定するのもイマイチだし、要素アクセスのたびにcloneされるのはまったく現実的ではなさそうだし、要素を書き換えたいときのイディオムが変わってしまう(front_mutみたいなものは書けない)。イテレータのインタフェースも標準的なものとは変わってしまう。
というわけで、やはり現実的ではなさそうだ。
他の誰かに所有してもらう
ノード間でオーナーシップを持つのはおかしいんじゃないかという気がする。ノードのオーナーはリスト本体であってそいつが所有していればいい。あとは適当にリファレンスを持てばいいんじゃないか。こんな感じ。
struct Node<'a, T> {
element: T,
next: Option<&'a Node<'a, T>>,
prev: Option<&'a Node<'a, T>>,
}
struct LinkedListVec<'a, T> {
nodes: Vec<Node<'a, T>>,
head: Option<&'a Node<'a, T>>,
tail: Option<&'a Node<'a, T>>,
}ノードをベクタで管理していて連結リストとは……という気持になるが、適切にreservedなサイズを増やしていけば追記するだけならamortized costはO(1)なのでいいんじゃないか。本気でやるなら削除したノードを管理しないといけないが……。
だがどうもライフタイム解析で失敗してしまい、うまくいかない。リストがノードを保有していてその生存範囲では有効ではあるが、そのようなことをうまく表現できていないような気がする。
というわけでこの方向性もうまくいかなさそうだ。
ちなみにだが、next/prevをusizeにしてしまい、nodesの中の場所をインデックスで指定する、という方法ならたぶん大丈夫だと思う。しかしそれはなんというかもはや、nodesをメモリ領域にしてインデックスをポインタがわりにしているのとほぼ同じことである。そりゃまぁ unsafe という言語機能は使わないが、インデックスの先がほんとうに生きているものかの保証があやういので(途中でノードを破棄したときとか)、ぜんぜん安全な感じがしない。さすがにアホっぽい気がするのでこれは試していません。
まとめ
というわけで、double-linked-listをsafe Rustの範囲内で作るのはどうも無理っぽいというので正解という気がする。raw pointerとunsafeバリバリなstdのリスト実装が一番現実的なのであった。そこまで複雑じゃないからね、という話なのかもしれない。
しかし、linked listていどのことすら適切に表現できないような言語仕様というのはどうなんだろうか。どうも自分は不思議な気持ちになるんだよな。なにかもっとうまい仕組みがあったりしないんだろうか？
ところで single-linked-list なら、まぁ Box とかを使えばいけそうな気がする。双方向イテレータも zipper とかを使えば実現できるんじゃないかな。でも実際にやってみたらいろいろ罠があるんだろうか。
Jun Mukai's blog 