フューチャー Advent Calendar 2022の17日目です。
昨日は@kaedemaluさんのAWSで特定のパスに対してIP制御を実現するパターンでした。

普段使っているフォーマッターがどういう設計になっているのか気になったので調べてみました。
といっても細部まで見るわけではなく、自分の気になる点だけをざっくりみたいと思います。

rustfmt

まずはじめにrustfmtを見てみたいと思います。
設計思想等はDesign.mdに書かれているようです。

フォーマッターの実現方法として、トークン列を元にフォーマットする方法とASTを元にフォーマットする方法の2通り考えられますが、Design.mdによるとASTアプローチを取っているそうです。どちらのアプローチでも同様の機能を実装できるものの、ASTアプローチの方が早く有益なツールが作れるため、という理由のようです。

ソースコードを見ると、ASTの構築はrustc_parseというRustコンパイラが使用してるparserをライブラリとして使用しているようですね。AST構築後、FmtVisitorという構造体がASTのノードを訪問し、フォーマットしています。

FmtVisitorは下記のようになっていて、主に

フォーマットの設定
フォーマット結果を保持する文字列(buffer)
フォーマッターの状態

という情報を保持しているようです。

pub(crate) struct FmtVisitor<'a> {
    parent_context: Option<&'a RewriteContext<'a>>,
    pub(crate) parse_sess: &'a ParseSess,
    pub(crate) buffer: String,
    pub(crate) last_pos: BytePos,
    // FIXME: use an RAII util or closure for indenting
    pub(crate) block_indent: Indent,
    pub(crate) config: &'a Config,
    pub(crate) is_if_else_block: bool,
    pub(crate) snippet_provider: &'a SnippetProvider,
    pub(crate) line_number: usize,
    /// List of 1-based line ranges which were annotated with skip
    /// Both bounds are inclusifs.
    pub(crate) skipped_range: Rc<RefCell<Vec<(usize, usize)>>>,
    pub(crate) macro_rewrite_failure: bool,
    pub(crate) report: FormatReport,
    pub(crate) skip_context: SkipContext,
    pub(crate) is_macro_def: bool,
}

今回rustfmtについて調べてみて下記二点が面白いなと思いました。
一点目はASTアプローチなのでコメントの扱いが漏れているところがあるとフォーマット時にコメントが消えてしまうことがある点です。実際にこういうissueが上がっていました。

Rustfmt silently removes comments after enum/struct field #5464
rustfmt removes comment between doc comment and generic params #5320

rustfmt程広く使われているフォーマッターでも通常コメントを書かない箇所については対応が漏れていたりするのがわかると、これからフォーマッターを開発する際には勇気付けられますね。

二点目は、2つのやり方でフォーマットしてみて良さそうな結果を選択するという処理をしているところです¹²。あまりこういうアドホックなやり方をフォーマッターが行っているイメージがなかったので新鮮でした。

google-java-format

次に google-java-format を見てみました。
フォーマットの流れを知るにはFormatter#formatメソッドを読めば良さそうです。
本質的ではない分岐を削除し抜粋すると、以下のようになっています。

    OpsBuilder builder = new OpsBuilder(javaInput, javaOutput);
    // Output the compilation unit.
    JavaInputAstVisitor visitor;
    visitor = new JavaInputAstVisitor(builder, options.indentationMultiplier());
    visitor.scan(unit, null);
    builder.sync(javaInput.getText().length());
    builder.drain();
    Doc doc = new DocBuilder().withOps(builder.build()).build();
    doc.computeBreaks(javaOutput.getCommentsHelper(), MAX_LINE_LENGTH, new Doc.State(+0, 0));
    doc.write(javaOutput);
    javaOutput.flush();

ざっくりとした流れは下記のようになっているようです。

visitor.scan(unit, null) のメソッド呼び出しを起点に、JavaInputAstVisitorでASTを辿る
ASTを辿りながら OpsBuilder にフォーマット対象のトークン、空白、改行等を追加
OpsBuilder から Doc を構築
Doc#computeBreaks で改行位置等を計算（改行位置の候補はASTを辿ったときに決定していて Doc#computeBreaks ではそこで改行すべきかどうか判定している？）
出力

ちなみに lexer は com.sun.tools.javac.parser.Scanner を, parser は com.sun.tools.javac.parser.JavacParser を使用しており、こちらもrustfmtと同様にコンパイラと同じものを使用しているようですね。

uroboroSQL-formatter

弊社で開発しているSQLフォーマッターで、こちらは前2つと違いトークンアプローチのフォーマッターとなっています。
今回は時間がなく読むことができなかったので、時間がとれたら見てみたいです。

感想

今回2つのフォーマッターの設計について調べてみましたが、いずれもコンパイラが利用しているparserを使用しているのが印象的でした。
全体的に浅い部分しか読み込めなかったのが残念ですが、ドキュメントやソースコードを読むのは勉強になるので時間が取れたらまたやっていきたいと思います。

https://github.com/rust-lang/rustfmt/blob/master/src/chains.rs#L671 の辺りです ↩
余談ですが、そのあたりが原因なのか計算量オーダーが指数時間になっており機械的に生成したコードだと非常に時間がかかるケースがあるようです。メモ化で計算量を抑えようとしたPRがあったようですが、それは不具合があったためrevertされていました。（メモ化の変更のMR, revertされたMR） ↩