カーソル入門

OK！！！ これで std の 1.0 実装に肩を並べる LinkedList ができました！ もちろんそれは、私たちの LinkedList がいまだに完全に役立たずだということでもあります。Deque を連結リストとして実装するという途方もない性能ペナルティを受け入れたうえで、それを実際に有用にする API は何も持っていません。

連結リストの「キラーアプリ」に対して、私たちがどうなのかを見てみましょう。

• 🚫 奇妙な intrusive なことができる
• 🚫 奇妙な lockfree なことができる
• 🚫 Dynamically Sized Typesを格納できる
• 🌟 償却なしの O(1) push/pop（malloc が O(1) だと信じる気があるなら）
• 🚫 O(1) のリスト分割
• 🚫 O(1) のリスト結合

まあ…… 6 個中 1 個は…… 何もないよりはマシです！ 私がなぜこれを std から引きはがしたかったのか、わかりますか？

私たちのリストに「奇妙な」ものをサポートさせるつもりはありません。あれは全部アドホックでドメイン固有だからです。でも分割と結合、これはできることです！

ただし問題があります。LinkedList の k^番目の要素に実際に到達するには O(k) 時間がかかります。では、任意の分割やマージを O(1) で行うことなど、いったいどうして可能なのでしょうか？ そのコツは、split_at(index) のような API を持たないことです。ユーザーがリスト内の位置まで状態を持ってイテレートし、その地点で O(1) の変更を行えるような仕組みを作るのです！

おや、イテレータならすでにあります！ これを使えるでしょうか？ ある程度は…… ですが、それらのスーパーパワーの 1 つが邪魔になります。by-ref イテレータのライフタイムを書き出す方法では、それらが返す参照はイテレータに結び付いていない、ということを覚えているかもしれません。これにより、next を繰り返し呼び出しつつ要素を保持できます。

let mut list = ...;
let iter = list.iter_mut();
let elem1 = list.next();
let elem2 = list.next();

if elem1 == elem2 { ... }

返される参照がイテレータを借用していたら、このコードはまったく動きません。コンパイラは next の 2 回目の呼び出しに文句を言うだけです！ この柔軟性は素晴らしいのですが、私たちに暗黙の制約をいくつか課します。

• By-Mutable-Ref イテレータは、後戻りして同じ要素をもう一度 yield することは決してできません。ユーザーが同じ要素に対する 2 つの &mut を取得できてしまい、言語の根本的なルールを破ることになるからです。

• By-Ref イテレータは、すでに yield された参照を無効化するような形で、基底のコレクションを変更し得る追加メソッドを持つことはできません。

残念ながら、これらはどちらも、私たちの LinkedList API にやってほしいことそのものです！ つまりイテレータをそのまま使うことはできず、新しいものが必要です。それがCursorsです。

カーソルとは、コンピューターでテキストを編集しているときに表示される小さく点滅する | とまったく同じものです。シーケンス（テキスト）内の位置であり、（矢印キーで）動かすことができ、何か入力するとその地点で編集が行われます。

ほら、もし私がこう

Enter を

押すと

文章全体が

真っ二つに

分かれます。

すみません、あなたは私の後ろに立って、これをタイプしているのを見ていますよね？ だから完全に意味が通りますよね？ ね。

さて、もし「insert」キー付きのキーボードを使うという不運に見舞われ、実際にそれを押してしまったことがあるなら、カーソルには技術的には 2 つの解釈があることを知っているでしょう。要素（文字）の間にあることも、要素の上にあることもできます。人生で「insert」を意図して押した人など誰もいないと私はかなり確信していますし、あれは純粋に苦痛ボタンとして存在しているのですから、どちらがより良く正しいかは明らかです。カーソルは要素の間に置かれるものです！

かなり盤石な論理ですね。誰も私に異論を唱えられないと思います。

え、何ですって？ Rust の LinkedList に Cursors を追加する RFC が 2018 年にあった？

Cursor を使うと、リスト内を前後に移動して現在の要素を取得できます。CursorMut を使うと、前後に移動して要素への可変参照を取得でき、現在の要素の前後に要素を挿入したり削除したりできます（分割や結合など、いくつかのリスト操作も行えます）。

現在の要素？ このカーソルは要素の間ではなく、要素の上にあります！ 私の完全に盤石な主張を受け入れなかったなんて信じられません！ というわけで、std の Cursor を使えばいいですね…… 待って、2022 年で Rust 1.60 でも Cursor はまだ unstable とマークされている？

ちょっと待って：

カーソルは常にリスト内の 2 つの要素の間に位置し、論理的に循環する形でインデックス付けされます。これに対応するため、リストの先頭と末尾の間には None を yield する「ghost」非要素があります。

ちょっと待って。これは RFC が言っていることの逆？？？ でも待って、メソッドのドキュメントはどれもまだ「current」要素に言及している…… 待てよ、この ghost の話、どこかで見たことがある。ああ、待って、私がプロトタイプを作った昔の linked-list フォークでやったやつじゃなかった？

カーソルは常にリスト内の 2 つの要素の間に位置し、論理的に循環する形でインデックス付けされます。これに対応するため、List の先頭と末尾の間には None を yield する「ghost」非要素があります。

ちょっと待て、何なんだこれ。これは冗談ではなく、私は今本当にドキュメントを読もうとしているんです。std は実際に私が 2015 年に提案したものとは違う設計を RFC にしたのに、その後で私のプロトタイプからドキュメントをコピペしたの？？？ std は、私が LinkedList をどれほど嫌いかについて本を書いていることに対して、メタクソ投稿で煽ってきてるの？？？？？ いやまあ、LinkedList を役立たずでなくすために std に追加させてもらうべく、その概念を示すためにプロトタイプを作ったわけだけど、qu’est-ce que le fuck??????????????

よし、わかりました。明らかに std は私の設計を客観的に優れたものとして祝福しているので、私たちは私の設計で行きます。あと、この章全体は文字どおり私がそのライブラリをゼロから書き直しているものなので、API を変えないというのは私としても良さそうです！

私が書いた最上位ドキュメント全文は次のとおりです。

Cursor はイテレータに似ていますが、前後へ自由に移動でき、イテレーション中に安全にリストを変更できます。これは、yield する参照のライフタイムが、基底のリストだけではなく、Cursor 自身のライフタイムに結び付いているためです。つまり、Cursor は複数の要素を同時に yield できません。

カーソルは常にリスト内の 2 つの要素の間に位置し、論理的に循環する形でインデックス付けされます。これに対応するため、List の先頭と末尾の間には None を yield する「ghost」非要素があります。

作成されたとき、カーソルは ghost とリストの先頭の間から開始します。つまり、next はリストの先頭を yield し、prev は None を yield します。もう一度 prev を呼び出すと末尾を yield します。

かわいいですね。「sentinel-node」全体は割に合わないほど面倒だという結論に至ったにもかかわらず、結局は、カーソルがリストの反対側に回り込めるように sentinel node があるかのように「見せかける」セマンティクスを持つことになります。

昔の API をもう少し流し読みする

fn splice(&mut self, other: &mut LinkedList<T>)

カーソルの直後にリスト全体の内容を挿入します。

ああそうだ、思い出してきた。これは、組合せ爆発に本気で腹を立てていたときに書いたもので、各操作のコピーが 1 つだけで済むような方法を考え出そうとしていたんだ。残念ながら、これは……意味論的に問題がある。というのも、ユーザーがあるリストを別のリストにスプライスしたいとき、カーソルがスプライスの前に来てほしい場合もあれば、後に来てほしい場合もある。挿入されるリストは任意の大きさになり得るので、片方だけを許して、挿入されたリスト全体をユーザーに走査させることを期待するのは、本当に問題になる！

結局、この設計は一からやり直さないといけない。Cursor 型には何が必要だろう？ そうだな、必要なのは次のことだ。

• 2 つの要素の「間」を指す
• ちょっとした便利機能として、次の「インデックス」が何かを追跡する
• リスト自体を更新して front/back/len を変更する。

2 つの要素の間をどうやって指すのか？ まあ、指さない。ただ「次の」要素を指すだけだ。つまり、そう、外には「カーソルは間に入る」という意味論を公開しているけれど、実際には「カーソルは上にある」として実装し、その位置の前または後であらゆることが起きるふりをしているだけだ。

でもこれには理由がある！ スプライスのユースケースでは、ユーザーがリストの前に最終的にいるか後に最終的にいるかを選べるようにしたいのだけれど、これは……std API で表現するにはひどく複雑だ！ splice_after と splice_before はあるけれど、どちらもカーソルの位置を変えないので、実際には splice_after_before と splice_after_after が必要になる……

いや待て、バカなことを言っている。std API では、最終的に乗りたいノードを選んで、それに応じて splice_after/splice_before を使えばいいだけだ。

目を細める

待て、std API って実は良いのか。

コードをざっと読む

OK、std API は実際に良い。

よし、もういい、RFC を実装する。少なくとも、その面白い部分は実装する。

std が使っている用語にはいくつか引っかかるところがあるけれど、カーソルというものは常にちょっと頭が溶けるものだ。iter().next_back() は back() を返してくれるので、そこまではよい。でもその後の各 next_back() は実際にはfront に近づいているのであり、実際、たどっているポインタはすべて「front」ポインタなのだ！ この一見パラドックスのようなものについて考えすぎると頭が痛くなるので、これを避けるために別の用語を選ぶことは確かに理解できる。

std API では、「before」（front 方向）と「after」（back 方向）の前に対する操作について語っており、next と next_back の代わりに……move_next と move_prev と呼んでいる。うーん。つまり、少しイテレータ用語に寄せているわけだが、少なくとも next は front/back を想起させないし、イテレータと比べて物事がどう振る舞うかを把握する助けにはなる。

これならやっていける。