はじめに
連結リストの循環を検出する実装では、Floydの循環検出法のように速度の異なる2つのポインタを進めます。今回は、QuixBugsのJava版に含まれるDETECT_CYCLEを題材に、テスト失敗からhareがnullになる経路を追い、条件式だけを修正します。
この記事は本番障害の事例ではなく、QuixBugsに含まれるバグ入りプログラムを使ったデバッグ練習です。最初に失敗を再現し、入力と例外を観測した後で、正解実装を答え合わせとして確認します。
QuixBugsとは
QuixBugs公式リポジトリは、PythonとJavaの小規模なプログラムに意図的なバグを含めた、プログラム修正・デバッグ練習用のベンチマークです。
今回扱うプログラム
対象はjava_programs/DETECT_CYCLE.javaです。Nodeのsuccessorをたどり、循環があればtrue、末尾に到達すればfalseを返す仕様です。テストには循環するリストと循環しないリストの両方が含まれています。
環境はOpenJDK 21、Gradle 8.10、JUnit 4です。対象テストはjava_testcases.junit.DETECT_CYCLE_TESTです。
バグ入りコード
修正前の中心部分は次の形でした。
while (true) {
if (hare.getSuccessor() == null)
return false;
tortoise = tortoise.getSuccessor();
hare = hare.getSuccessor().getSuccessor();
if (hare == tortoise)
return true;
}
hare.getSuccessor()を確認してから、2つ先へ進めています。この条件が成り立てば、2ホップの移動式自体は評価できます。ただし、移動後のhareがnullになることまでは防げません。
テストを実行する
修正前に対象テストを実行しました。
/home/ubuntu/tools/gradle-8.10/bin/gradle test \
--tests java_testcases.junit.DETECT_CYCLE_TEST \
--console=plain --no-daemon
6ケース中5ケースは成功しましたが、test4がNullPointerExceptionで失敗しました。
failing testを確認する
失敗ケースは、短い非循環リストを検査するテストです。ログでは次の例外が確認できました。
DETECT_CYCLE_TEST > test4 FAILED
java.lang.NullPointerException
at DETECT_CYCLE_TEST.java:88
at DETECT_CYCLE.java:18
循環を見逃したのではなく、循環がないことを返す前に例外が発生しています。この点から、問題は「同じノードに戻ったか」という比較よりも、次のポインタを安全に進められるかの判定にありそうです。
正常ケースと比較する
長い非循環リストや循環リストでは、hareがnullになる前にhare.getSuccessor() == nullの判定で終了するか、2つのポインタが一致します。一方、短い非循環リストでは、次のような状態になります。
| 時点 | hare |
hare.getSuccessor() |
次の処理 |
|---|---|---|---|
| ループ開始 | 末尾の1つ前 | 末尾ノード |
hareを2つ先へ進める |
| 2つ先へ移動後 | null |
呼び出せない | 次のループでNPE |
hare自身がnullになる可能性を、ループ先頭の条件が考慮していません。
デバッガーまたはログで処理を追う
この処理で重要なのは、1回のループでhareが2ホップ進むことです。hare.getSuccessor() != nullであれば2ホップの移動式自体は評価できますが、その結果としてhareがnullになる可能性があります。元の実装は、次の反復でそのnullを確認せずhare.getSuccessor()を呼び出していました。
したがって、hare = hare.getSuccessor().getSuccessor()の直後には、次のループでhare == nullとなる状態が発生し得ます。循環リストであれば通常はこの状態に到達しませんが、非循環リストの末尾付近では到達します。
原因を特定する
原因は、ループ継続条件がhare自身のnullを確認していないことです。
因果関係をまとめると、次のようになります。
-
hareは1回の反復で2つ先へ進む。 - ループ先頭では
hare.getSuccessor() == nullだけを検査している。 - 現在の
hareが存在しても、2つ先へ進んだ結果はnullになり得る。 - 次の反復で
hare.getSuccessor()を呼び出し、NullPointerExceptionになる。
循環検出法のポインタ移動自体を変更する必要はなく、非循環リストの末尾に到達したと判定する条件を補うのが最小修正です。
最小修正を行う
hare自身のnullを先に確認する条件を追加しました。
- if (hare.getSuccessor() == null)
+ if (hare == null || hare.getSuccessor() == null)
return false;
||の左側でhare == nullを確認するため、hareがnullのとき右側のメソッド呼び出しは評価されません。ポインタの進め方や循環判定は変更していません。
テストを再実行する
修正後、同じテストを再実行しました。
/home/ubuntu/tools/gradle-8.10/bin/gradle test \
--tests java_testcases.junit.DETECT_CYCLE_TEST \
--console=plain --no-daemon
結果はBUILD SUCCESSFULでした。修正前に失敗した短い非循環リストのケースと、もともと成功していた循環・非循環の5ケースがすべて成功しました。
正解実装と比較する
対象テストが成功した後、QuixBugsのcorrect_java_programs/DETECT_CYCLE.javaと比較しました。正解実装もhare == null || hare.getSuccessor() == nullを確認しており、今回の修正と一致します。
| 観点 | 今回の修正 | 正解実装 |
|---|---|---|
hare自身の確認 |
追加した | 同じ |
| 1つ先の確認 | 維持した | 同じ |
| ポインタの移動 | 変更なし | 同じ |
| 循環判定 | 変更なし | 同じ |
テストを通してから答え合わせをしたことで、単に正解実装を写すのではなく、「各反復の開始時にhare自身と1つ先のノードを検査する必要がある」と説明できます。
今回のデバッグから学べること
高速ポインタを使うアルゴリズムでは、複数ホップ進んだ結果、ポインタ自身がnullになる可能性も考慮する必要があります。1回の処理で複数回リンクをたどるコードでは、各反復で参照するポインタの状態を確認します。
また、5ケースが成功して1ケースだけが例外になる場合でも、成功したケースだけを見て実装が安全だと判断してはいけません。ポインタが末尾付近にいる最小ケースを追加し、nullになる瞬間を観測すると、条件不足を特定しやすくなります。
例外が出た行の直前にある状態更新を見る
例外が発生した行だけではなく、その変数をnullにした直前の更新も確認します。今回の処理は、次の順序で進みます。
hareがnullになる
↓
その時点では例外は発生しない
↓
次のループでhareを参照する
↓
NullPointerExceptionになる
NullPointerExceptionが発生したのはhare.getSuccessor()を呼んだ行です。しかし、hareがnullになったのは前の反復にあるhare = hare.getSuccessor().getSuccessor()です。例外が起きた行だけを見るのではなく、変数の状態を変えた直前の代入や更新まで戻ると、原因を切り分けやすくなります。
この見方は、連結リストだけに限りません。ループ内の状態更新や非同期処理でも、例外が現れた時点と不正な状態が作られた時点がずれることがあります。
まとめ
DETECT_CYCLEのバグは、hareが2ホップ進んだ結果nullになる可能性を、次のループで検査していなかったことでした。hare == null || hare.getSuccessor() == nullという条件を追加する1行の修正で、既存の循環判定を維持したまま例外を防げました。
修正後は対象JUnit 6ケースがすべて成功し、QuixBugsの正解実装とも一致しました。
参考資料
[1] QuixBugs公式リポジトリ
[3] JUnit 4