702 の作業中にaprの探索効率が極めて悪いことに気づいた．

小さな題材ですぐに直せそうなプログラムなのに100世代使っても修正できなかった．

flの計算結果（suspのリスト）を確認してみると，なぜか {return 0} というブロック行に対して，複数のsuspが割当たっていることを確認した．図ハイライト箇所の1個目と3個目が重複（2個目は問題なし）．

suspと行は常に1対1の関係なのに，1対Nの関係になってしまっている．

根本原因は？

fl時にast inferの結果をうまくハンドルできていない．

flやjacocoは「行」が処理の基本単位となる．一方，mutationでは「ast」が基本単位となる．よって「行→ast」の変換が必須となる（通称，翻訳問題）．翻訳を行うのがast infer．大昔にarimaが作成してくれた処理．

ast inferの振る舞いはこう．

1  m() {
2    if (f) {
3      x();
4    }
5  }

この題材の3行目をinferすると m(){if(f){x()}} if(f){x()} {x()} x()の4種類のASTが返ってくる． inferは，その行が該当しうる全ての箇所を列挙して返してくる．これ自体はOK．

FL時には，上記inferの結果を「最後の要素」をとることで行対ASTの1体1変換を行っている．つまり3行目 = x() という解釈．これもOK．

問題はブロックを持つast要素をinferした場合．例えば2行目のif文をinferした場合， m(){if(f){x()}} if(f){x()} {x()} の3種類となる．その結果，1対1変換により2行目 = {x()} こうなる．これはまずい． if文をinferしたのに，その条件ではなくifブロックがsusp計算の対象になってしまう．

結果的に，例えばifの条件がバグっていた場合，ifブロックの疑惑値が高くなる．よって，kgpはif条件ではなくifブロックをなんとかして修正しようとしてしまう．

これを修正できるとif条件バグの修正効率が劇的に上がりそう．

shinsuke-mat commented 4 years ago

ast inferの振る舞いを変えるのはどうか？

A. ブロックを持つast要素はブロックではなく内部のexpressionを返す．

x if(f){x();} {x()} o if(f){x();} f

if文をinferしたのだから，返すのはifの式であるべき，という考え．式ではなくブロック要素側にバグがある，という可能性もある．しかし，ブロック要素は行単位で分割されていることが多いので，あえてif文inferの際に計算する必要はない．

B. ブロック要素は排除するこれは怪しい．ブロックをまるごと書き換える，という修正能力を殺すことになる．それが有効かは知らんけど．

C. 単一要素しか持たないブロック要素は排除するこれはアリ．絶対無駄なので．

YoshikiHigo commented 4 years ago

このバグを発現する最小のデータセットがほしいです．

shinsuke-mat commented 4 years ago

あらゆる題材で再現できますが，既存の KGenProgMainTest#testGCD01 がわかりやすいです．

  public int gcd(int a, int b) {
    if (a == 0) {
      return 0; // to be "return b"
    }
    while (b != 0) {
      if (a > b) {
        a = a - b;
      } else {
        b = b - a;
      }
    }
    return a;
  }

本issueの最初に張った図も上記題材で出てきたsuspの結果です．

kusumotolab / kGenProg

行とastの対応変換のバグ #704

tl;dr

バグ発見の過程

702 の作業中にaprの探索効率が極めて悪いことに気づいた．

根本原因は？