ast書き換えのバグ

[shinsuke-mat]

立命館丸山先生の指摘で見つかったバグ．

DefaultSourceCodeGenerationクラスのexec()メソッドを見ると， operation一つずつを取り出して，apply()メソッドを呼び出すことで， コード改変を行っています．

たとえば，以下のように複数のoperationが並んでいると，

InsertAfterOperation InsertBeforeOperation ReplaceOperation

2番目のInsertBeforeOperationの適用によって，着目しているASTノードの 位置が1つ後方にずれると思います．このずれを考慮しないまま， JDTASTLocationクラスのlocate()を呼び出し， 次のReplaceOperationを適用するASTノードを特定してしまうと，疑惑値が高く replaceすべきASTノードではなく，1つ手前のASTノードがreplaceの対象となって しまいます．kGenProgを利用した実験を行っている際に，意図的にreplaceしたい ASTノードがどうしてもreplaceの対象にならないことで気付きました．

これが正しいとすると，後世代の個体（＝長い塩基を持つ個体）ほど， 疑惑値から少しずれた改変が行われることになる． 探索効率が劇的に低下する．

よくこれでjGenProgと戦えたという印象．

[shinsuke-mat]

まずはバグの再現から． 極力コードを読まずに，自然なAST書き換えのテストを書いてみた．

以下の題材に対して，

public void foo(int n) {
  n = 0;
  n = 1;
  n = 2;
}

以下2つの操作を持つ塩基を作った．

• n = 1; の後に n = 11; を追記（InsertAfterOperation）
• n = 2; を n = 12; に置換（ReplaceOperation）

最終的な期待は以下．

public void foo(int n) {
  n = 0;
  n = 1;
  n = 11; // inserted
  n = 12; // replaced
}

実際はこう．明らかにreplace対象がずれてる．

public void foo(int n) {
    n = 0;
    n = 1;
    n = 12;
    n = 2;
}

[shinsuke-mat]

InsertAfter → InsertAfter でもやはりずれる． Delete → InsertAfter も同じ． Replace → InsertAfter はずれない．

行位置が変化するOperation（InsertAfter，InsertBefore，Delete）適用後がまずい．

[shinsuke-mat]

丸山先生の指摘通り，JDTASTLocation#locate が原因っぽい． https://github.com/kusumotolab/kGenProg/blob/7871b21e7cc4e6408b34d048393f7aff53b45ae2/src/main/java/jp/kusumotolab/kgenprog/project/jdt/JDTASTLocation.java#L34-L44

Operation が持つ Location は ASTNode のラッパークラスで， この ASTNode は改変されていないオリジナルastと紐付いている．

L43 node.getParent() ではオリジナルastが取得されるため， このメソッドの返値は「オリジナルastから見た」node位置になってしまう．

[shinsuke-mat]

変更先を表す Location を行番号ではなく ASTNode として， つまり参照として持つという実装自体は悪くない． 一方で，ある Operation を適用する際にASTをdeepCopyして書き換えているので， Location のast自体の参照がずれてしまう．

https://github.com/kusumotolab/kGenProg/blob/7871b21e7cc4e6408b34d048393f7aff53b45ae2/src/main/java/jp/kusumotolab/kgenprog/project/jdt/InsertAfterOperation.java#L23

[shinsuke-mat]

上3つは間違ってるっぽいのでhideしておいた．

[shinsuke-mat]

個体生成時には，毎回，初期個体を複製してから遺伝子（＝全塩基）を適用する． これは全個体保持ポリシーのため．親個体を直接書き換えせずにoriginからdeepcopyする． 無駄は多いが機能的に問題なし．

個体が持つ遺伝子は塩基の集合で構成される． 塩基は，操作と位置情報のペア． 操作＝insert/delete/replace．位置＝ASTのノード この位置はASTノードの参照の形で表現される． つまり，FLが適用されたASTの一番怪しい場所への参照である．

仮説1：

この「初期固体から生成」と「ASTの位置情報」の組み合わせがまずい． 初期固体から再生成するので，生成ASTは常に新しい参照を持つ． 一方で，ASTの位置情報は古い，過去に生成したASTへの参照になっている． 古いASTへの参照を使いながら，新ASTを適切に書き換えられるのか？

→ JDTASTLocation.locate() で新ASTと古ASTの対応をうまく探しているっぽい． 確証はないが

仮説2

個体自体が持つ遺伝子自体がおかしい． あり得ない塩基を持っているような気がする．

例えばこれ．#1166 は初期個体からn=2を挿入して生成される．

-- base.size = 1
(#22c3) package example;
public class CloseToZero {
  public int close_to_zero(int n) {
    n = 1; //
    n = 2; //
    n = 3; //
    return n; //
  }
}
>> applying "insert_after" [n=2;] for [n=1;](#22c3)
(#1166) package example;
public class CloseToZero {
  public int close_to_zero(int n) {
    n = 1; //
    n = 2;
    n = 2; //
    n = 3; //
    return n; //
  }
}

#1166 は他の個体の改変時にも，塩基内のAST位置情報としてよく出現する． 常に，初期個体+2ステップで発生する． 以下は問題のない個体の例．

-- base.size = 2
(#22c3) package example;
public class CloseToZero {
  public int close_to_zero(int n) {
    n = 1; //
    n = 2; //
    n = 3; //
    return n; //
  }
}
>> applying "insert_after" [n=2;] for [n=1;](#22c3)
(#2fe2) package example;
public class CloseToZero {
  public int close_to_zero(int n) {
    n = 1; //
    n = 2;
    n = 2; //
    n = 3; //
    return n; //
  }
}
>> applying "delete" [] for [n=1;](#1166)
(#7a58) package example;
public class CloseToZero {
  public int close_to_zero(int n) {
    n = 2;
    n = 2; //
    n = 3; //
    return n; //
  }
}

問題はこれ．初期個体+1ステップで突然 #1166 が出てくる．

-- base.size = 2
(#22c3) package example;
public class CloseToZero {
  public int close_to_zero(int n) {
    n = 1; //
    n = 2; //
    n = 3; //
    return n; //
  }
}
>> applying "insert_after" [n=3;] for [n=3;](#1166)
(#52ec) package example;
public class CloseToZero {
  public int close_to_zero(int n) {
    n = 1; //
    n = 2; //
    n = 3; //
    return n; //
    n = 3;
  }
}

#1166 からの改変では上記個体は絶対に生まれない． 初期個体に n=3 を挿入，と捉えるのが自然だが，位置がやはりおかしい．

どうも仮説2が諸悪の根源っぽい．

[shinsuke-mat]

次なる疑問：「なぜ仮説2の問題が発生するのか？」

@YoshikiHigo とprint-debugの結果を見比べながら議論． 30m くらい作業して気付いた．

結論：crossover + ゼロ生成の組み合わせが悪そう．mutationは問題なさそう． （ゼロ生成＝初期個体から全塩基適用による個体の生成方法）

まず，print-debugで出力している情報はこんなん． これは前コメントで指摘した #1166 のあたりでおかしくなるケース．

-- base.size = 2
(#22c3) package example;
public class CloseToZero {
  public int close_to_zero(int n) {
    n = 1; //
    n = 2; //
    n = 3; //
    return n; //
  }
}
>> applying "insert_after" [n=3;] for [n=3;](#1166)
(#52ec) package example;
public class CloseToZero {
  public int close_to_zero(int n) {
    n = 1; //
    n = 2; //
    n = 3; //
    return n; //
    n = 3;
  }
}

一応フルセット．1166で検索すると良い． https://sdl.ist.osaka-u.ac.jp/~shinsuke/kgp/20200713-apr-stdout-ast-bug.log

各個体がどんな遺伝子（塩基）を適用して生成されていくか，という過程を出力している． ゼロ生成の全手順，あるいは塩基適用の過程ともいえる．

これを眺めるとmutationがおかしいように見えるが，実はこのケースはcrossoverの生成過程である． mutationとは単純な塩基適用の系列であり， crossoverは親からの塩基の選択という手順を含んだmutation（塩基適用）だといえる． このcrossoverでの塩基適用が諸悪の根源っぽい．

crossover限定のバグであり，crossover生成個数を0にすると問題は発生しない． なんとなく目視で眺めておかしくないことを確認済み． https://sdl.ist.osaka-u.ac.jp/~shinsuke/kgp/20200713-apr-stdout-ast-bug-wo-crossover.log

---

以下の例を考える．2つの個体がある． x: ast0 → (base1) → ast1 → (base2) → ast2 y: ast0 → (base3) → ast3

個体xとyをcrossoverしたい．選択候補となる塩基は3つ（base1，base2，base3）． 今回はbase2とbase3を適用しよう． 2つの塩基の中身はこう．

base2: 位置ast1のn++，操作insert n=1 base3: 位置ast0のn--，操作delete

問題 塩基base2，base3の適用対象となるASTはどこであるべきか？ base3は簡単でast0を基準に考えて良い．base2は？

ここを真面目に考えておらず，毎回ast0を基準にゼロ生成（塩基適用）を行っているのが問題． そのため，塩基base2を適用する瞬間に，ast1のn++という位置情報を無理矢理ast0に当てはめるので， 結果操作対象の位置がずれる． 今回，base3の基準がast0なので簡単に見えるが，base3の基準すらast0でないケースもたくさんある．

---

どう修正すべきか？ これがよくわからん．修正方法以前に，どうあるべきかが分からない．

少なくとも，塩基適用時のチェックは追加できる． 改変astの内容と塩基位置が指すastの内容を見比べて，ずれていたら生成をやめる． ただ，これは根本的な解決ではなく，ほぼ全てのcrossoverが上記チェックにひっかかってしまいそう． crossover=0でいいやん．