Rustの「うわ、swapできない」を解消するパッケージを作った

次のようなパッケージ (クレート) を作ったので解説します。

https://github.com/qnighy/omniswap

https://crates.io/crates/omniswap

動機

Rustには所有権があるため、普通のswapパターンが動かない場合があります。これに対応するため、std::mem::swapという関数が用意されています。

let mut x = 'a';
let mut y = 'b';
std::mem::swap(&mut x, &mut y);
assert_eq!((x, y), ('b', 'a'));

ところが、この方法は2つの参照が互いに重ならないことが保証できるときにしか使えません。

よくあるのが、同じ配列内でswapしたい場合です。

let mut a = [1, 2, 3];
std::mem::swap(&mut a[0], &mut a[2]); // compile error

この場合、インデックスの定数値を見れば実際には重ならないことがわかります。しかし一般的には、2つのインデックスが等しいかどうかは判定できないため、Rustではこのような配慮はせず一律にコンパイルエラーにしています。

この配列の例の場合は特別に、以下のようなメソッドが用意されています。

let mut a = [1, 2, 3];
a.swap(0, 2);

しかし、たとえば二次元配列では同じ手法は使えません。

let mut a = [[1, 2], [3, 4]];
std::mem::swap(&mut a[0][0], &mut a[1][1]);

本パッケージが提供する解決策

端的に言うと、 std::mem::replace を使って以下のようなswapを実現します。

let tmp = std::mem::replace(a, sentinel);
let tmp = std::mem::replace(b, tmp);
*a = tmp;

そのためには番兵となる値 (sentinel) を決定する必要があります。これには大きく2つの方法が考えられます。

• 固定の値を使う (Default)
• 既に入っている値を再利用する (Clone or Copy)

どちらが最適かは時と場合によるので、本パッケージの swap! はより効率的と考えられる方法を自動で選択します。

swapに関して詳しく

古典的なswapは以下のように実装されます。

let tmp = *a;
*a = *b;
*b = tmp;

もちろん std::mem::swap も基本的には似たような実装になっているのですが、Rustでは所有権の問題があるので、デストラクタが二重実行されないことをコンパイラに保証してやる必要があります。

実装上はunsafe関数であるread / writeを慎重に使う……みたいな話になるのですが、根本的な問題として巻き戻し安全性の問題があります。

もし、上の手順の途中でパニックが起きた場合、その状態のまま巻き戻しが起こって呼び出し元に制御が戻されます。この時点で *a と *b に有効な値が入っていないといけないのですが、上の手順の途中では所有権が tmp に移っているので、少なくとも *a と *b のどちらかは無効な値です。そのため、Undefined Behaviorを回避できません。

実際には上の処理を慎重に書けばパニックは起きないのですが、パニックが起きないことをコンパイラに対して形式的に保証する手段がないため、unsafeを使わざるを得ません。それを毎回書くかわりに、あらかじめ標準ライブラリで安全なパターンを std::mem::swap として抽象化して提供しているわけですが、その抽象化でカバーできない範囲があるというのが元々の問題だったと言えます。

本パッケージは、パニックが起きないことを保証するのではなく、パニックが起きてもいいように安全な番兵を用意するという考え方を取っているのが特徴です。

swapをするときはテンポラリ領域が1つ増えるので、値に対して場所が1つ多いことが問題になりますが、番兵を置くことで値と場所の個数を一致させることができます。

なぜマクロなのか

通常のswapと違い、omniswapが提供するswapは各参照が互いに(空間的に)オーバーラップしてもいいようになっています。これは参照の有効期間を時間的にずらすことで実現されています。

さらに、そのためには2つの参照のうちのどちらかに2回アクセスする (借用を一度解放してから、再度アクセスする) 必要があります。

こういった処理は通常の関数では実現できません。そのため、マクロにする必要があります。

実際、このマクロは第一引数を2回展開します。もし副作用がある場合は副作用が2回実行されることになります。 (これはドキュメントにも記載しています)

どのように実装を選択するのか

Rustでは、2つのトレイトの (disjointではない) OR をとるのは基本的にできません。重複している部分で、どちらの実装を優先するのかを決定する必要がありますが、そのための安定した仕組みがないので、これはある意味当然のことです。

nightlyではマーカートレイトと特殊化を悪用することで実現できるのですが、基本的にはトレイトレベルでのORはできないと考えるのがいいでしょう。

今回は前提としてマクロを使うことが確定しているので、より上位のレイヤで実装の選択を行います。これにはメソッド解決の仕組みを悪用します。

Rustではドット記法で書かれたメソッドを非常に柔軟に解釈します。たとえばderefがある場合は以下のようなパターンを順番に試すことになります。

x.method();
x.deref().method();
x.deref().deref().method();
// ...

そして、各ステップではそのメソッド定義が存在するかだけではなくそのメソッドが要求するトレイト制約が満たされているかどうかもチェックされます。

そこで、以下のような条件分岐が実行されるように型を作っておきます。

x.take(); // T: Copy のとき有効になるメソッド
x.deref().take(); // T: Default のとき有効になるメソッド
x.deref().deref().take(); // T: Clone のとき有効になるメソッド

こうすることで、 x.take() と書くことで優先順で最初に満たされたトレイトに対応する処理が実行できます。

まとめ

• Rustでは所有権の問題から値を交換するために専用の関数・メソッドが必要になることがある
• しかし、参照先が互いに重複する可能性がある場合のうまい抽象化がないため、特定のケースではうまくswap処理を書けないという問題があった
• 今回作ったomniswapは、多くの型で番兵にあたる値を用意できることを利用して、これまで std::mem::swap でカバーできなかったケースに対して汎用性の高い安全なswapの手段を提供した。