はじめに

コードフォーマッタは最近ではエディタやIDEに標準機能として搭載されるようにもなってきているため，使う機会が増えてきているのではないでしょうか？

中でもclang-formatは，フォーマットのベースとなるコーディングスタイルをいろいろ設定することができ，自分が好きなスタイルでフォーマットをすることができます．
しかし，このスタイルは多数のスタイルオプションから構成されており，人力ではこれらを設定するのが大変だったりします．

そこで，フォーマットの対象となるコードにあったスタイルを遺伝的アルゴリズムを用いて探索してみました．

clang-formatとは？

clang-formatは，C/C++/Java/JavaScript/Objective-C/Protobufなどのコードをフォーマットすることができるコードフォーマッタです．

clang-formatには様々なフォーマットのスタイルオプションが存在します．
このオプションを自由に変更することで，プロジェクトのコードに合わせて柔軟にスタイルを変更することができます．
例えば，IndentCaseLabelsというスタイルオプションは，switch文のcaseラベルをインデントするかどうかをtrue，falseで指定することができます．

どうやってスタイルオプションを設定する？

clang-formatには98個（ver 6.0.0時点）ものスタイルオプションが存在します．
私が自分のプロジェクトにclang-formatを導入しようとしたところ，これらのスタイルオプションをどう設定したらいいのか検討がつかない，という問題が発生しました．

そこで考えついた一つの方針が，「プロジェクトの既存のコードにできる限り合ったスタイルオプションに設定する」というものです．
具体的には，「既存のコードをフォーマットした際に変更される行数がなるべく少なくなるようなスタイルオプションに設定する」ことを考えました．

しかし変更行数が少ないスタイルオプションを人力で探すのはかなりの手間がかかってしまいます．
そこで，人力の代わりに変更行数を少なくするスタイルオプション設定を遺伝的アルゴリズムで自動で探索させてみました．

遺伝的アルゴリズム（GA）

GAは以下の図のような流れで探索を行います．

以下では，それぞれの操作についてざっくり説明します．

初期集団（個体群）を生成

今回のケースでは，個体はスタイルオプション設定の組み合わせの一つ，になります．
初期集団の生成時には，$N$個の個体について，それぞれのスタイルオプション設定を，以下の図のようにそれぞれランダムに初期化して生成します．

個体の評価値を計算

個体の評価値は，個体のスタイルオプション設定を用いてclang-formatを適用したときのコードの変更行数，としました．
「評価値=コードの変更行数」なので，評価値の最小化することが目的となります．

次世代に残す個体を選択

今回はトーナメント選択によって個体を選択するようにしました．
トーナメント選択は以下の流れで個体を選択します．

集団からランダムに複数個の個体を復元抽出
一番評価値が良い（変更行数が少ない）個体を次世代の個体として集団に追加
次世代の個体の数が$N$個になるまで1と2を繰り返す．

交叉

交叉は二点交叉を用いました．
二点交叉は以下の流れで新しい個体を生成します．

集団を２つの個体同士のペアに分割
各ペアに対して一定確率で交叉を行うか決める
交叉を行う場合，以下の図のように交叉点をランダムに二点決定し，その間に挟まれている部分を２つの個体同士で入れ替える

突然変異

集団内の個体の多様性を増加させるために，以下の流れでいくつかの個体を変異させます．

集団内の各個体について，一定確率で突然変異を行うか決める
突然変異を行う場合，個体の各スタイルオプションについて，一定確率でランダムな設定に変更

個体の評価部分の実装

個体の評価は，gitコマンドによって変更行数を取得することで行いました．
具体的には，以下のような処理を評価の際に実行するように実装を行いました．

プロジェクト内のcpp，h，hppファイルに対してclang-formatを適用してコードをフォーマット
git diff --numstatで各ファイルの変更行数（削除行数+追加行数)を取得
全ファイルの変更行数の和を評価値として計算
git checkoutで変更したcpp，h，hppファイルをもとに戻す．

また，明らかに探索の必要がない設定がわかりきっているスタイルオプションがいくつか存在していたため，探索の対象となるスタイルオプションと指定のデフォルト値を使用するスタイルオプションを分けられるようにもしました．

実験

フォーマット対象のコード

フォーマットを行う対象のコードは，clangのexamplesフォルダ内のコードにしてみました．
全体のコード行数は$486$行です．

探索時の設定

集団サイズは$N=100$，トーナメントのサイズは$3$，各個体ペアに交叉を適用する確率は$0.5$，各個体を突然変異させる確率を$0.2$，突然変異の際に各スタイルオプションの設定を変更する確率を$0.05$に設定しました．
また，評価回数は$1,000$回としました．

探索の対象としたスタイルオプションは，98個のうち48個としました．
基本的には，bool値やenum値などの離散的な値を指定するスタイルオプションのみを探索の対象としています．
数値を指定するものや，あらかじめ指定値がわかりきっているものについては，デフォルト値を設定してその値で固定するようにしました¹．

探索結果

評価値の推移は以下のようになりました．

発見された最良のスタイルオプション設定によるコード変更行数は，$55$行という結果となりました．
評価値の推移から案外いい感じに探索が進んでいることがわかります．
ちなみに，最良のスタイルは以下のようになりました．

---
Language:        Cpp
AccessModifierOffset: -2
AlignAfterOpenBracket: Align
AlignConsecutiveAssignments: false
AlignConsecutiveDeclarations: false
AlignEscapedNewlines: DontAlign
AlignOperands:   true
AlignTrailingComments: false
AllowAllParametersOfDeclarationOnNextLine: false
AllowShortBlocksOnASingleLine: true
AllowShortCaseLabelsOnASingleLine: false
AllowShortFunctionsOnASingleLine: Inline
AllowShortIfStatementsOnASingleLine: false
AllowShortLoopsOnASingleLine: false
AlwaysBreakAfterDefinitionReturnType: None
AlwaysBreakAfterReturnType: None
AlwaysBreakBeforeMultilineStrings: false
AlwaysBreakTemplateDeclarations: true
BinPackArguments: false
BinPackParameters: true
BraceWrapping:   
  AfterClass:      false
  AfterControlStatement: false
  AfterEnum:       false
  AfterFunction:   false
  AfterNamespace:  false
  AfterObjCDeclaration: false
  AfterStruct:     false
  AfterUnion:      false
  AfterExternBlock: false
  BeforeCatch:     false
  BeforeElse:      false
  IndentBraces:    false
  SplitEmptyFunction: true
  SplitEmptyRecord: true
  SplitEmptyNamespace: true
BreakBeforeBinaryOperators: None
BreakBeforeBraces: Attach
BreakBeforeInheritanceComma: true
BreakBeforeTernaryOperators: false
BreakConstructorInitializersBeforeComma: false
BreakConstructorInitializers: BeforeColon
BreakAfterJavaFieldAnnotations: false
BreakStringLiterals: false
ColumnLimit:     80
CommentPragmas:  '^ IWYU pragma:'
CompactNamespaces: false
ConstructorInitializerAllOnOneLineOrOnePerLine: false
ConstructorInitializerIndentWidth: 4
ContinuationIndentWidth: 4
Cpp11BracedListStyle: true
DerivePointerAlignment: false
DisableFormat:   false
ExperimentalAutoDetectBinPacking: false
FixNamespaceComments: false
ForEachMacros:   
  - foreach
  - Q_FOREACH
  - BOOST_FOREACH
IncludeBlocks:   Regroup
IncludeCategories: 
  - Regex:           '^"(llvm|llvm-c|clang|clang-c)/'
    Priority:        2
  - Regex:           '^(<|"(gtest|gmock|isl|json)/)'
    Priority:        3
  - Regex:           '.*'
    Priority:        1
IncludeIsMainRegex: '(Test)?$'
IndentCaseLabels: false
IndentPPDirectives: None
IndentWidth:     2
IndentWrappedFunctionNames: true
JavaScriptQuotes: Leave
JavaScriptWrapImports: true
KeepEmptyLinesAtTheStartOfBlocks: true
MacroBlockBegin: ''
MacroBlockEnd:   ''
MaxEmptyLinesToKeep: 1
NamespaceIndentation: None
ObjCBinPackProtocolList: Auto
ObjCBlockIndentWidth: 2
ObjCSpaceAfterProperty: false
ObjCSpaceBeforeProtocolList: true
PenaltyBreakAssignment: 2
PenaltyBreakBeforeFirstCallParameter: 19
PenaltyBreakComment: 300
PenaltyBreakFirstLessLess: 120
PenaltyBreakString: 1000
PenaltyExcessCharacter: 1000000
PenaltyReturnTypeOnItsOwnLine: 60
PointerAlignment: Right
ReflowComments:  false
SortIncludes:    false
SortUsingDeclarations: false
SpaceAfterCStyleCast: true
SpaceAfterTemplateKeyword: true
SpaceBeforeAssignmentOperators: true
SpaceBeforeCtorInitializerColon: true
SpaceBeforeInheritanceColon: true
SpaceBeforeParens: ControlStatements
SpaceBeforeRangeBasedForLoopColon: true
SpaceInEmptyParentheses: false
SpacesBeforeTrailingComments: 1
SpacesInAngles:  false
SpacesInContainerLiterals: false
SpacesInCStyleCastParentheses: false
SpacesInParentheses: false
SpacesInSquareBrackets: false
Standard:        Cpp11
TabWidth:        8
UseTab:          Never
...

おわりに

今回はGAで探索を行いましたが，現実的にはGAを使う必要はそこまでない可能性があります．
というのも，山登り法のような探索アルゴリズムでもほぼ同等の結果が少ない評価回数で得られるためです．

山登り法を含めた実装コードはGithubのリポジトリに公開しています．
お遊び気分で使ってみてもらえると幸いです．

読んでくださりありがとうございました．

例えば，DisableFormatというスタイルオプションはtrueで固定しました．これをfalseにしてしまうと，clang-formatによるフォーマットが行われなくなってしまい，変更行数が0となってしまいます． ↩

遺伝的アルゴリズムでコードフォーマッタのスタイルを最適化する