前半
お題
LRU方式で、最も使われていないキーに紐づくデータを追い出すようなマップを実装する。
- 特定のキーに対して値を設定／取得された場合に使われたとみなす
まずはテストから：
@Test
def マップに１つ値を設定するとそれが取得できる() = {
val lru = new Lru()
lru.put("KEY1", "VALUE1")
assertEquals("VALUE1", lru.get("KEY1"))
}
コンパイルすら通りませんが、外側＝使う側から設計していくのがTDDです。たいしたことのない実装に見えますが、このコードを書いた瞬間に、かなりの設計判断をしています。
- クラスの名前はLruにする。
- Mapと同じように、putで値を設定し、getで取得する。
まずはコンパイルを通るようにして（つまり、クラスとメソッドを空で作って）テストを実行すると、結果はレッドになります（getでnullが返りますので）。これを通すためのコードも簡単です。
class Lru {
var key:String = _
var value:String = _
def put(key: String, value: String) = {
this.key = key
this.value = value
}
def get(key: String):String = {
value
}
おなじみの仮実装ですね（よくよく見ると、keyフィールドも要らなかったですね）。しかし、テストを実行させてグリーンになることを確認するのは大切です。自分たちがすくなくとも、テストの書き方と実行のさせ方をわかっていることが確認できるわけですから。こうして、これからの「黄金の回転」のための基礎ができあがります（この段階ではリファクタリングをやりませんでしたが、今思えば、「クラス名ってLruでいいんだっけ？」という議論をしてもよかったかもしれません）。
次に、この実装に対してレッドになるテストも簡単に書けます。
@Test
def マップに２つ値を設定するとそれが取得できる() = {
val lru = new Lru()
lru.put("KEY1", "VALUE1")
lru.put("KEY2", "VALUE2")
assertEquals("VALUE1", lru.get("KEY1"))
assertEquals("VALUE2", lru.get("KEY2"))
}
もちろん、仮実装で粘ることもできるのですが、ここでフィールドをマップに変えました。
val map = new HashMap[String,String]
個人的には、TDDで一番"難しい"ポイントは「どのタイミングで最終的な実装に切り込むか」にある思っています。テストに通すだけなら、永遠に仮実装で凌ぎ続けることもできるわけです。ただ、もちろんそれでは実際の使用に耐えられません。重要なのは次の２点だと考えています。
- テストは無限な現実の１ケースであり、実装は抽象的に考える必要がある。
- テストをグリーンにするコードは、最終形の途中にある不完全なかたちになる。
この不完全なかたちを作る作業は、頭の中では先読みしつつちょっと手前でとめる作業になります。次にどうすればレッドにできるかわかっている状態でコードを書くことがあるということですね。また逆に言えば、テストをレッドにするという行為は、目指す最終形に対して抽象化／一般化できていない部分を突き崩すものであるべきなのです。
３つ目のテストでいよいよ、核心部に切り込むことになります。
@Test
def マップに3つ値を設定するとそれが最初がnull() = {
val lru = new Lru()
lru.put("KEY1", "VALUE1")
lru.put("KEY2", "VALUE2")
lru.put("KEY3", "VALUE3")
assertEquals(null, lru.get("KEY1"))
}
保持しておくキーの数に特に指定はなかったのですが、とりあえず「２つ持つ」という仕様で作業を始めました。これはある意味現実を抽象化し切れていない部分ですので後で修正することにして、先にコアの実装をやっつけます。
完成形に至る不完全なかたちとしては、「とりあえず受けとった順にキーをリストに詰めていって、３つ以上あったら先頭から消していく」という実装にしました。
class Lru {
val map = new HashMap[String,String]
var keystack = new ListBuffer()
def put(key: String, value: String) = {
keystack += key
if (keystack.size > 2) {
val removeKey = keystack.remove(0)
map.remove(removeKey)
}
map += key -> value
}
これでテストはグリーンになりますが、バグがあることはすでにわかっています。同じキーを連続していれたら他のものを追い出してしまうんですね。そこを突いてレッドにするテストを書きます。
@Test
def マップに2つの値を繰り返しいれて取得できる() = {
val lru = new Lru()
lru.put("KEY1", "VALUE1")
lru.put("KEY2", "VALUE2")
lru.put("KEY1", "VALUE1")
lru.put("KEY1", "VALUE1")
assertEquals("VALUE2", lru.peek("KEY2"))
assertEquals("VALUE1", lru.peek("KEY1"))
}
前の実装だと、keystackの中身が["KEY1","KEY1"]になってしまうので、"KEY2"が追い出されてレッドになります。そこでコードを修正します。「keystackの中にもうすでにキーが入っていたら、keystackをいじるのをやめよう！」if文で囲むだけですね。
class Lru {
val map = new HashMap[String,String]
var keystack = new ListBuffer()
def put(key: String, value: String) = {
if(!keystack.contains(key)) {
keystack += key
if (keystack.size > 2) {
val removeKey = keystack.remove(0)
map.remove(0)
}
}
map += key -> value
}
たしかこのあたりで、「Scalaなんだし、nullを返すのはやめようよ」というリファクタリングが入りました。さて実装自体は一見良さそうに見えたのですが、まだレッドにできます。
@Test
def 値を入れ直した場合に順序が更新される() = {
lru.put("KEY1", "VALUE1")
lru.put("KEY2", "VALUE2")
lru.put("KEY1", "VALUE1")
lru.put("KEY3", "VALUE3")
assertEquals(Some("VALUE1"), lru.peek("KEY1"))
assertEquals(None, lru.get("KEY2"))
assertEquals(Some("VALUE3"), lru.peek("KEY3"))
}
"KEY1"に対応する値がNoneであるということで、レッドになってしまいます。理由は「★」の場所でkeystackの中身が["KEY1","KEY2"]のまま変わらないからですね。["KEY2","KEY1"]にしないといけません。「keystackの中から消して、後ろにつければいいじゃないか」ここでScalaっぽさが炸裂します。
def put(key: String, value: String) = {
keystack = stack.filter( _ != key )
keystack += key
if (keystack.size > 2) {
val removeKey = keystack.remove(0)
map.remove(0)
}
map += key -> value
}
これでグリーンになります。よくよく見ると、keystackに対する2つの操作（★）は１行にできますね（実際にこのリファクタリングを行ったのはもうすこし後のことでしたが）。
keystack = stack.filter( _ != key ) + key
一瞬完成したかと思ったのですが、ここで１つ忘れていたことを思いだしました。「getの時も使ったって考えるんだよね？」
@Test
def 値を取り出した場合に順序が更新される() = {
lru.put("KEY1", "VALUE1")
lru.put("KEY2", "VALUE2")
lru.get("KEY1")
lru.put("KEY3", "VALUE3")
assertEquals(Some("VALUE1"), lru.get("KEY1"))
assertEquals(None, lru.get("KEY2"))
assertEquals(Some("VALUE3"), lru.get("KEY3"))
}
もちろん★の部分でkeystackの中身が更新されないので、"KEY1"が取得できず、テストはレッドになります。実装はそれほど難しくありません。putの先頭でkeystackをいじっているところをprivateメソッドに切り出し、getの先頭でも呼ぶようにしました。
def put(key: String, value: String) = {
touch(key)
map += key -> value
}
def get(key: String): Option[String] = {
touch(key)
map.get(key)
}
これで完成だろうとドヤ顔でテストを実行したところで、和田さんの準備した落し穴に顔面から突き刺さりました。「いままで通っていたテストが通らなくなった！なんだこれは？」こういうとき、原因に一瞬で気づく人がいるのが強力なチームのよいところ。「Assertでgetするときにも順番が変わっちゃうね」
状態を変更しないで値が取れるメソッドpeekを準備して、テストをすべて書き換えました。
def peek(key: String): Option[String] = map.get(key)
「これで要件を満たしただろう」と考えて、ちょっとしたリファクタリングを行いました。keystackを触る処理をメソッドではなくプライベートクラスとして抽出したのです。
class Lru {
val map = new HashMap[String,String]
var keystack = new KeyStack()
def put(key: String, value: String) = {
keystack.touch(key)
map += key -> value
}
[...]
class KeyStack {
var stack = ListBuffer[String]]()
その上で、先ほどのペンディング事項「キャッシュサイズは変えられるようにしないと」を実装しました。
@Test
def キャッシュサイズを３に変更して３つの値を出し入れできる() = {
val lru = new Lru(3)
[...]
Scalaのデフォルト引数機能を使うことで、これまでのテストは触らなくてすみます。
class Lru(var cacheSize:Int = 2) {
ここで前半が終了しました。
なお、どこかのタイミングでテストのリファクタリングを行い、毎回のnew Lru()をテストフィクスチャに追い出しています。
var lru: Lru = _
@Before
def setup = {
lru = new Lru();
}
後半：仕様変更
ここで和田さんから（うれしそうに）仕様変更のお知らせが入りました。
仕様変更
- キャッシュのサイズを後から変更できるようにしたい。
- 時間が経ったら消えるようにしたい。
- スレッドセーフにしてほしい。
後半のセッションの開始時、「存在しないものに対するget」のバグが悔しかった僕は、ついうっかりコードを先に書いてしまいました（和田さんが隣にいたらものすごく怒られたところです。危ない危ない）。
if(!map.contains(key)) None
書いた後で気がつきます。「ごめんね、和田さん」反省して、テストコードを書きました。
@Test
def 値が入っていないものをGetしても状態は変わらない() {
lru.put("KEY1", "VALUE1")
lru.put("KEY2", "VALUE2")
lru.get("KEY3")
assertEquals(None, lru.peek("KEY3"))
assertEquals(Some("VALUE1"), lru.peek("KEY1"))
assertEquals(Some("VALUE2"), lru.peek("KEY2"))
}
しかし、レッド。getで相変わらず状態が変わってしまっています。しばらく眺めて気がつきました。メソッドの途中ではreturnが省略できないんですよね。
if(!map.contains(key)) return None
テストは先に書かなければいけないし、すくなくとも実装したものはテストしないといけないということですね*2。
仕様変更１でちょっと難しいところは、キャッシュサイズを減らした場合にkeystackを削らなければいけない点にあります。この「削り」に関して、またしてもScalaのかっこいいAPIが炸裂します（Scala勉強会@東北のページを紹介して頂きました）。
if (stack.size > cacheSize) {
for(i <- stack.dropRight(cacheSize)){
map.remove(i._1)
}
stack = stack.takeRight(cacheSize)
}
あふれている分を取得（dropRight）してマップから削除し、stackから必要なところだけ取り出して（takeRight）再代入します。
これで、テストはグリーンになります。ここで、すこし大きめのリファクタリングを行いました。仕様変更２で結構大きな変更が想定されたので、それに耐えられるようにこのタイミングできれいにしておきたかったのです。
今書いたコードと、今まで使っていたこのコード：
if (keystack.size > cacheSize) {
val removeKey = keystack.remove(0)
map.remove(0)
}
「やっていることはすごく似ていないだろうか？」すこし考えて、「どちらの場合もcacheSizeに合わせて、keystackとmapを削っているだけだ」ということに気づきました。今まで使っていたコード（すぐ上）は、新しく書いたコード（２つ上）の特殊ケースにすぎないのです。それをまとめた結果、コードはかなりすっきりしました。
def touch(key: String) = {
stack = stack.filter( _ != key ) + key
shrinkIfNeeded()
}
def changeSize(size: Int) = {
cacheSize = size
shrinkIfNeeded()
}
private def shrinkIfNeeded() = {
if (stack.size > cacheSize) {
for(i <- stack.dropRight(cacheSize)){
map.remove(i)
}
stack = stack.takeRight(cacheSize)
}
}
実は、午前中に行った「KeyStackクラスの作成」というリファクタリングの恩恵に、ここであずかることができています。この変更はKeyStackクラスの中に閉じており、外側のLru本体には影響を与えていません。
さて、仕様変更２です。
関心事の分離
「古いものを消す」という仕様を入れるためには、時間の概念を導入しなければなりません。スレッドを新しく走らせる必要もあるでしょう。これをいままでのクラスに入れたくはなかったですし、テストコードも書きにくくなってしまいます。そこで、テストコードを書く前に図を書いて、設計の検討を行いました。
TimerとLruとの間にはRemovable（これも名前の検討は必要ですが）というインターフェイスを立てます。Timerのテスト（＝時間の概念が入る）は、Removableをモック化して定期的にメッセージが送られていることを確認します。Lruのテストは直接Removableに定義されたメソッドを呼び出し、正しくふるまっていることを確認します。
Timerのテスト時にモックが必要になります。本当はjMockやMockitoのようなモックフレームワークがあるとよかったのですが、限られた時間の中で（しかもScala）で動かす自信がなかったので、プライベートクラスとしてごりっと実装してしまいました。
@Test
def 定期的に削除メッセージを送信する() {
val mock = new MockRemovable()
val timer = new LruTimer(mock)
timer.start();
Thread.sleep(15000)
assertTrue("呼び出されている", mock.called)
}
private class MockRemovable extends Removable {
var called = false;
def remove(time:Date) {
called = true;
}
}
ここに重要な設計が１つあって、RemovableのメソッドがDateオブジェクトを受けとるものであることを定めています。本体はこうなりました。
class LruTimer(removable: Removable) extends Thread{
override def run() = {
while(true) {
Thread.sleep(10000)
removable.remove(new Date())
}
}
}
タイマーができたところで、Lru本体に取りかかります。もちろん、テストコードから。
@Test
def ある時点の前のキャッシュを削除する() {
lru = new Lru(3)
lru.put("KEY1", "VALUE1")
lru.remove( new Date(System.currentTimeMillis() + 10000) )
assertEquals(None, lru.peek("KEY1"))
}
「removeに渡されたDateよりも前に使われたものは消そう」と決めました。まずは、keystackに時間の概念を導入します（このとき、Lruクラスには影響がなく、変更はすべてプライベートクラスであるKeystackクラスに閉じています）。
var stack = ListBuffer[Tuple2[String,Date]]()
def touch(key: String) = {
stack = stack.filter( _._1 != key ) + ( key -> new Date )
shrinkIfNeeded()
}
ご覧のとおり、stackにタッチするときに、タイムスタンプを設定しています（new Dateはアレですが、それはリファクタリングできれいになるでしょう）。そして、removeが呼ばれたときにそのタイムスタンプを見て、古いものを削除することになります。
def removeBefore(time:Date) = {
for( i <- stack.filter( ! _._2.after(time) ) ){
map.remove(i._1)
}
stack = stack.filter( _._2.after(time) )
}
このあたりでタイムアップとなりました。
こうしたインターフェイスとモックを使ったTDDのやり方については、「Growing Object-Oriented Software, Guided by Tests (Addison-Wesley Signature Series (Beck))」で詳しく説明されています。講演の中で和田さんがモダンTDDのバイブルとして位置づけていた本ですね。
