Scala 2.12と2.13とで、ListMapのキーまわりの挙動が違っているので注意しましょう / ライブラリ調査の心得

アプリケーションのコレクションまわりの実装について調査していたところ、Scala 2.12から2.13にかけての更新がscala.collection.immutable.ListMapの挙動を変化させており、実は元々2.13で見せていた振舞いは仕様外のものだったことが判明したのでメモ。

この記事では、ScalaのコレクションクラスListMapのバージョンを跨いだ振舞いの変化について学ぶことができ、また、こういったバージョン間で発生する標準ライブラリの変化の調査を行うための知見について知ることができる。

ListMap -- キー順序を保存するMap
Scala 2.13ではコレクションメソッドの整理が行われた
ListMapの挙動が変化している
- Scala 2.12.17におけるListMapに重複キーを追加した場合の挙動
- Scala 2.13.10におけるListMapに重複キーを追加した場合の挙動
発見の経緯
ライブラリの調査をするときの心得と知見

ListMap -- キー順序を保存するMap

ScalaにはListMapというMap(他の言語で言うところの辞書構造)の実装があり、内部的にListを用いてキーを保持している。

www.scala-lang.org

Listはfindに $O(N)$ のコストが発生するので一見非効率なデータ構造に見えるが、要素追加のコストは常に $O(1)$ で済むことと、順序の保持が可能である点が重宝されて、Listでキーを保持するListMapが使われることがある。

import scala.collection.immutable.ListMap
val m = ListMap(3 -> null, 2 -> null, 1 -> null)
val n = m + (4 -> null)

n.keys // => List(3, 2, 1, 4)

このように、追加した順序が保存される。これがちょうどユースケース上重要なことがあり、たまに使われる。

Scala 2.13ではコレクションメソッドの整理が行われた

さて、少し昔のことになるが、Scala 2.12から2.13へのバージョンアップに伴い、コレクションまわりの大改編が行われた。詳しくは立ち入らないが、以下のような破壊的変更が行われている:

SetBuilderなどのいくつかのクラスの削除
Streamが削除され、LazyListで置換された
breakOutが削除された

詳細は以下のドキュメントを参照してほしい:

docs.scala-lang.org

www.scala-lang.org

ListMapの挙動が変化している

さて、ListMap自体はインターフェイス上の破壊的変更を受けなかった。しかし内部的な修正に起因する振舞いの変更が発生している。

キーの順序が追加した順で保存されるという振舞いは保存される。
ただし、キーが重複した場合の振舞いが破壊的に変更された。
- 2.12の場合: キーが重複した場合は、そのキーが最後のキーとなり、既に存在していたキーは無いものとして扱われる
- 2.13以降の場合: キーが重複した場合は、キーの順序を変更せず、値のみが変更される。

言葉だけだと伝わりにくいと思うので、実際のコードで説明する。こういうとき、自分はオンラインScala実行環境であるScastieを起動して試すようにしている。

Scala 2.12.17における`ListMap`に重複キーを追加した場合の挙動

import scala.collection.immutable.ListMap
val m = ListMap(3 -> "a", 2 -> "b", 1 -> "c")
val n = m + (4 -> "d")

// 追加した順でキーの順序が保存される
n.keys // Set(3, 2, 1, 4)
n // ListMap(3 -> a, 2 -> b, 1 -> c, 4 -> d)

// 同じキーで別の値を入れる
val o = n + (1 -> "new a")

// 最後に追加したキーは最後に移動する
o.keys //Set(3, 2, 4, 1)
o // ListMap(3 -> a, 2 -> b, 4 -> d, 1 -> new a)

Scala 2.13.10における`ListMap`に重複キーを追加した場合の挙動

import scala.collection.immutable.ListMap
val m = ListMap(3 -> "a", 2 -> "b", 1 -> "c")
val n = m + (4 -> "d")

// 追加した順でキーの順序が保存される
n.keys // List(3, 2, 1, 4)
n // ListMap(3 -> a, 2 -> b, 1 -> c, 4 -> d)

// 同じキーで別の値を入れる
val o = n + (1 -> "new a")

// 最後に追加したキーは順序を替えず、値のみ更新される
o.keys // List(3, 2, 1, 4)
o // ListMap(3 -> a, 2 -> b, 1 -> new a, 4 -> d)

このように、挙動が変更されていることがわかる。

しかし、この挙動は元々2.12の時点でバグのある実装であり、2.13になってこれが修正されたと見ることもできる。2.12の時点でのScaladocのListMapのページを参照すると、

This class implements immutable maps using a list-based data structure. List map iterators and traversal methods visit key-value pairs in the order whey were first inserted. Scala Standard Library 2.12.17 - scala.collection.immutable.ListMap

と記述されており、そもそも in the order whey were first inserted最初に追加された順 な順序でキーが返ってくるのが正常であって、おそらく、キーを追加するとそれが最後に回るというのは仕様と乖離した振舞いだったのではないか。そしてこれがScala 2.13で是正され、仕様通りの動作をするようになったと見るのが正しいかもしれない。