[小ネタ]1/4,294,967,297 の死角

#TL;DR

List<T>やらDictionary<TKey,TValue>をforeachで回したり、Enumerator取得後に、内部状態を変えて、列挙を続行してもInvalidOperationExceptionが飛んでこないレアケースが存在して、その確率が大体上記って話。

#EnumeratorはSourceの変更をどう検知しているか

foreach使うにせよEnumerator使うにせよ、その取得した時点から元のコレクションに変更が発生した場合、列挙の続行は一般的に失敗してInvalidOperationExceptionが発生する。これは列挙している最中にコレクションが変更されてしまうと、列挙操作の整合性がとれなくなる可能性があるためである。

この元コレクションが変更されているか否かをどのように検知しているかというと、
各々のコレクションにprivate int _versionというフィールドがあり、Add、Deleteそれにアイテムのセットなどの変更が加わればこのフィールドをインクリメントしている。

他方、foreach等の列挙操作で、GetEnumeratorメソッドが呼ばれた際は、返却するEnumeratorに現在の_versionを引数として渡しておき、MoveNextが呼ばれた時に、Ctorで受け取ったバージョン番号と、元コレクションのバージョン番号を照査して差異があればInvalidOperationExceptionが発生する形となる。

これはとても良い解決法で、例えばイベントの購読やRxの購読となると素朴な実装を行った場合元コレクションにEnumeratorの強参照が残る可能性があるし、また通知自体が結構重い処理となる。
なので、その辺の複雑性を回避しスマートに解決していると思う。

#全てが42になる

さて、変更検知がどのように為されているかざっと検証してきた。
ここで問題なのが、_versionが32bitであり、ライブラリはuncheckedでコンパイルされている。

なので、

private static void Main(string[] args)
{
	List<int> list = new List<int>();
	list.Add(42);
	foreach (var i in list)
	{
		Console.WriteLine(i);
		list.Add(42);
	}
}

こんなこと書いても最初42が出力されてその後InvalidOperationExceptionが発生するのがオチとなる。

けれど、以下のように書き換えたとき

private static void Main(string[] args)
{
	List<int> list = new List<int>();
	list.Add(42);
	foreach (var i in list)
	{
		Console.WriteLine(i);
		list.Add(42);
		for (uint _ = 0; _ < uint.MaxValue; _++) list[0] = 42;
	}
}

このときCountがint.MaxValueを超えるか、実行している環境のメモリを食い尽くすかどちらかで落ちるまでは延々42を出力し続ける。

#ネタばらしとまとめ

やってることは簡単で、_versionが32bitなら2^32+1回の操作をすればWraparoundして、_versionは元に戻る。なので変更無しと誤認していると言うオチ。

列挙途中に32bitの空間食い尽くすような変更操作をすることなんてほぼないだろうし、それにもまして、以上でも以下でもなくJustである必要があるので、コリジョンが発生する可能性は表題通りとなるから、普通一般的には気にする必要も無いと思う。

ただ、何かしらのCriticalな話と絡むと酷くタチの悪いバグを生み出すこともなくはないので、一応まとめてみましたと言うことで一つ。

ご清聴有り難うございました。