Android Room における隣接リストから閉包テーブルへのMigration

隣接リストにて作成してしまった木構造のデータを、深さ付きの閉包テーブルにマイグレーションしたのでそのときの備忘録です。

そもそもの木構造の表現方法には触れず、あくまでMigrationの手順についてのみ記載しています。

# モチベーション

AndroidでTwitterAPI（Twitter4J）を利用したアプリを作っており、要件としてツイートとそれに連なるリプライをローカルに保持する必要がありました。  
当初はあまり深く考えず、`Tweet`オブジェクトに[`Status#inReplyToStatusId`](https://developer.twitter.com/en/docs/twitter-api/v1/data-dictionary/object-model/tweet)プロパティが含まれていることから、ローカルに`previousId`としてこのIdを保持していました（後々めんどうになる予感はしていたが、当初は閉包テーブルを知らなかった）。

隣接リストでは、任意のツイートを含む、任意の深さの根～葉までの経路を取得することが困難であることが分かり、閉包テーブルにマイグレーションしたものです。

# サンプルデータ

ベースとなる木構造はこちら。番号はTweetIdを表すものとします。

なお、便宜上親が存在しないツイートは `previousId = -1` としています。

![TweetTree_base.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/209042/3bb83a10-8e28-a447-3cd6-bf721afa900d.png)


* `tweet`テーブル

| tweetId | previousId |
| ------- | ---------- |
| 1 | -1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 3 |
| 6 | 3 |
| 7 | 4 |

`tweet`テーブルから`closure（閉包）`テーブルを作成し、最終的に次のようなデータを作ります（プライマリキーとする`id`列は省略）。

親子関係の探索は**深さ優先探索**により実行しました。

* `closure`テーブル

| ancestor | descendant | depth |
| -------- | ---------- | ----- |
| 1 | 1 | 0 |
| 1 | 2 | 1 |
| 1 | 3 | 2 |
| 1 | 4 | 2 |
| 1 | 5 | 3 |
| 1 | 6 | 3 |
| 1 | 7 | 3 |
| 2 | 2 | 0 |
| 2 | 3 | 1 |
| 2 | 4 | 1 |
| 2 | 5 | 2 |
| 2 | 6 | 2 |
| 2 | 7 | 2 |
| 3 | 3 | 0 |
| 3 | 5 | 1 |
| 3 | 6 | 1 |
| 4 | 4 | 0 |
| 4 | 7 | 1 |
| 5 | 5 | 0 |
| 6 | 6 | 0 |
| 7 | 7 | 0 |

自身への参照を`depth = 0`とし、直接の子を`depth = 1`、孫を`depth = 2`……とすることでデータを作成します。

# 実装

## 下準備

マイグレーションにあたり、スキーマのエクスポート及びテストを作成します。基本的には公式のやり方に従います。

https://developer.android.com/training/data-storage/room/migrating-db-versions#kotlin

### スキーマをエクスポートする

テスト用データベースを作成するため、現在のスキーマをJSON形式で出力します。
スキーマの出力部分は`javaCompileOptions`の部分ですが、ついでに`sourceSets`と依存関係も追加しておきます。

`app.build.gradle`に下記を追記し、いったんビルドしておきます。

```groovy
// app.build.gradle
android {
  defaultConfig {
    javaCompileOptions {
      annotationProcessorOptions {
        arguments = ["room.schemaLocation": "$projectDir/schemas".toString()]
      }
    }
  }

  sourceSets {
    // Adds exported schema location as test app assets.
    androidTest.assets.srcDirs += files("$projectDir/schemas".toString())
  }
}

dependencies {
  // 公式では testImplementation だが、テストはInstrumentationテストで行うので androidTestImplementation にする（なぜ公式が testImplementation なのか謎。。。）
  androidTestImplementation "androidx.room:room-testing:${versions.room_testing}"
}
```

ビルドすると`app/schemas/yourPackage.AppDatabase/1.json`が出力されます。

なお、この際`RoomDatabase`のアノテーションにて、`exportSchema = true`としておかないと正常に出力されないようです。

```kotlin
@Database(
  entities = [TweetEntity::class, ...],
  version = 1,
  exportSchema = true
)
abstract class AppDatabase : RoomDatabase() {}
```

### テストメソッドを作成

`androidTest`パッケージに`MigrationTest.kt`を作成します。

```kotlin
@RunWith(AndroidJUnit4::class)
class MigrationTest {
  @Before
  fun setUp() {

  }

  @Test
  @Throws(IOException::class)
  fun migrate1To2Test() {

  }
}
```

ここまでで下準備は完了です。

## テストを実装する

### テスト用データベースの初期化

テスト用データベースの初期化から始めます。
[`MigrationTestHelper`](https://developer.android.com/reference/androidx/room/testing/MigrationTestHelper)により、インメモリデータベースを生成します。

```kotlin
@RunWith(AndroidJUnit4::class)
class MigrationTest {
  private val TEST_DB = "migration-test"

  @get:Rule
  val helper = MigrationTestHelper(
    InstrumentationRegistry.getInstrumentation(),
    AppDatabase::class.java.canonicalName,
    FrameworkSQLiteOpenHelperFactory()
  )

  @Before
  fun setUp() {
    helper.createDatabase(TEST_DB, 1).apply {
      // 初期データを tweet に挿入
      execSQL(
        "Insert into tweet (tweetId, previousId) " +
         "values (1 , -1), (2, 1), (3, 2), (4, 2), (5, 3), (6, 3), (7, 4)"
      )
      close()
    }
  }
}
```

次に、データベースのバージョンを1から2に上げる処理を規定した`Migration`を作成します。
`runMigrationsAndValidate`の引数に`Migration`オブジェクトを渡してやることで、指定したバージョン（1→2）へのマイグレートを行うときの処理を指定します。

```kotlin
@RunWith(AndroidJUnit4::class)
class MigrationTest {
  private val TEST_DB = "migration-test"

  @get:Rule
  val helper = MigrationTestHelper(...)

  @Test
  @Throws(IOException::class)
  fun migrate1To2() {
    // Re-open the database with version 2 and provide
    // MIGRATION_1_2 as the migration process.
    val db = helper.runMigrationsAndValidate(TEST_DB, 2, true, Migrations.migrate1To2())
  }
}

object Migrations {

  fun migration1To2(): Migration {
    return object : Migration(1, 2) {
      override fun migrate(db: SupportSQLiteDatabase) {
        db.execSQL("CREATE TABLE IF NOT EXISTS closure " +
          "(`id` INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL, " +
          "`ancestor` INTEGER NOT NULL, " +
          "`descendant` INTEGER NOT NULL, " +
          "`depth` INTEGER NOT NULL)")
      }
    }
  }
}
```

この時点で`migrate1To2`を実行すると、`setUp()`で`tweet`テーブルとデータが作成され、さらに`MIGRATION_1_2`により空の`closure`テーブルが作成されます。

### `Migrations.migrate1To2`の実装

`tweet`テーブルを基に、`closure`テーブルにデータを作成する処理を定義します。

親子関係の探索は、再帰処理を用いた**深さ優先探索**により行います。
探索は`makeDescendantTree`にて実装します。

```kotlin
object Migrations {

  fun migrate1To2() {

    // seedId として渡されたIdを基に、子孫を深さ優先探索する。
    // 返り値は List<Pair<previousId, depth>>
    fun makeDescendantTree(
      seedId: Long,
      list: List<Pair<Long, Long>>
    ): List<Pair<Long, Int>> {

      fun search(id: Long, depth: Int, result: MutableList<Pair<Long, Int>>) {
        list.filter {
          id == it.second
        }.let {
          if (it.isNotEmpty()) {
            result.addAll(it.map { pair ->
              Pair(pair.first, depth)
            })
            it.forEach { pair ->
              search(pair.first, depth + 1, result)
            }
          }
        }
      }

      val result = mutableListOf<Pair<Long, Int>>()
      search(seedId, 1, result)

      return result
    }

    return object : Migration(1, 2) {
      override fun migrate(db: SupportSQLiteDatabase) {
        db.execSQL("CREATE TABLE IF NOT EXISTS closure " +
          "(`id` INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL, " +
          "`ancestor` INTEGER NOT NULL, " +
          "`descendant` INTEGER NOT NULL, " +
          "`depth` INTEGER NOT NULL)")

        // Pair<tweetId, previousId> を格納するリスト
        val list = mutableListOf<Pair<Long, Long>>()

        // レコードを全件取得
        val cursor = db.query("Select tweetId, previousId from tweet")

        cursor.moveToFirst()

        while (!cursor.isAfterLast) {
          val tweetId = cursor.getLong(0)
          val previousId = cursor.getLong(1)
          list.add(Pair(tweetId, previousId))
          cursor.moveToNext()
        }

        cursor.close()

        // 実データの都合上、previousId 列にしか存在しない Id があるため、マージ＆重複削除する
        val mergedIds =
          (list.map { it.first } + list.map { it.second }.filter { it != -1L }).distinct()

        // mergedIds を走査する
        mergedIds.forEach { seedId ->

          // 自身の参照を深さゼロで挿入
          db.execSQL("Insert into closure (ancestor, descendant, depth) values($seedId, $seedId, 0)")

          // seedId の子孫（descendant）のリストを作成する
          val descendantTree = makeDescendantTree(seedId, list)

          // 生成された子孫リストを closure テーブルに挿入する
          descendantTree.forEach {
            println("| $seedId | ${it.first} | ${it.second} |")
            db.execSQL("Insert into closure (ancestor, descendant, depth) values($seedId, ${it.first}, ${it.second})")
          }
        }
      }
    }
  }
}
```

`seedId = 2`のときの`makeDescendantTree`の再帰処理のイメージはこんな感じです。

![TweetTree_saiki.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/209042/eed31081-436d-1e00-e771-2e637a8505bf.png)

### 実行結果の確認

`migrate1To2Test`に確認用のクエリを記述して、`closure`に保存されているレコードを確認します。

適宜`assert`してください。

```kotlin
@RunWith(AndroidJUnit4::class)
class MigrationTest {

  @Test
  @Throws(IOException::class)
  fun migrate1To2() {
    // Re-open the database with version 2 and provide
    // MIGRATION_1_2 as the migration process.
    val db = helper.runMigrationsAndValidate(TEST_DB, 2, true, Migrations.migrate1To2())

    val cursor = db.query("Select * from closure order by ancestor ASC, depth ASC")

    cursor.moveToFirst()

    println("| id | ancestor | descendant | depth |")

    while (!cursor.isAfterLast) {
      println(
        "| ${cursor.getInt(0)} | ${cursor.getLong(1)} | ${cursor.getLong(2)} | ${cursor.getInt(3)} |"
      )
      cursor.moveToNext()
    }
  }
}
```

## 本番環境への移植

`RoomDatabase`の`Room.databaseBuilder.addMigrations`に`Migration`オブジェクトを指定します。

```kotlin
// closure テーブルは次のようなdata classにより定義
@Entity(tableName = "closure")
data class ClosureEntity(
  @PrimaryKey(autoGenerate = true)
  val id: Int,
  val ancestor: Long,
  val descendant: Long,
  val depth: Int
)

@Database(
  entities = [TweetEntity::class, ClosureEntity::class, ...],
  version = 2,
  exportSchema = true
)
abstract class AppDatabase : RoomDatabase() {
  abstract fun service(): TwitterControlServiceDao

  companion object {
    private var INSTANCE: AppDatabase? = null
    private val lock = Any()

    fun getInstance(context: Context): AppDatabase =
      INSTANCE ?: synchronized(lock) {
        INSTANCE ?: Room.databaseBuilder(
          context.applicationContext,
          AppDatabase::class.java, "AppDatabase.db"
        )
          .addMigrations(Migrations.migrate1To2) // ← ここに追加
          .build()
          .also { INSTANCE = it }
      }
  }
}
```

アプリ起動後、`AppDatabase.getInstance`が呼ばれた時点でマイグレートされると思います。

## 所感

* 基本的には公式のやり方でOKだが、ちょいちょいトラップがあるので要注意。
* 保持しているデータ量が多いと、再帰処理でSOFやOOMしたりするかも。
* 普通に再帰でクエリ発行した方が安全かもしれない。

次は、深さ付き閉包テーブルへのレコード追加処理のテストについて書きたいです。

# 参考としたページ

## 閉包テーブル

https://tociyuki.hatenablog.jp/entry/20170621/1498051748

https://blog.amedama.jp/entry/2016/05/18/234343

https://teitei-tk.hatenablog.com/entry/2020/11/30/130000

## Roomのマイグレーション

https://developer.android.com/training/data-storage/room/migrating-db-versions#kotlin

https://developer.android.com/training/data-storage/room/testing-db?hl=ja

https://github.com/android/architecture-components-samples/tree/master/PersistenceMigrationsSample/app/src/androidTestRoom/java/com/example/android/persistence/migrations

https://star-zero.medium.com/room%E3%81%AE%E3%83%9E%E3%82%A4%E3%82%B0%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%BE%E3%81%A8%E3%82%81-a07593aa7c78

https://qiita.com/naoi/items/08557d87c919617b8d17