フォーマッターの設計を調べてみた

フューチャー Advent Calendar 2022の17日目です。  
昨日は@kaedemaluさんの[AWSで特定のパスに対してIP制御を実現するパターン](https://qiita.com/kaedemalu/items/cd31ba952cc78ca02d21)でした。

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

## [rustfmt](https://github.com/rust-lang/rustfmt)

まずはじめにrustfmtを見てみたいと思います。  
設計思想等は[Design.md](https://github.com/rust-lang/rustfmt/blob/master/Design.md)に書かれているようです。  

フォーマッターの実現方法として、トークン列を元にフォーマットする方法とASTを元にフォーマットする方法の2通り考えられますが、[Design.md](https://github.com/rust-lang/rustfmt/blob/ee2bed96d60fd7e46b1fb868f6a8f27e3a8058d0/Design.md#operate-on-the-ast)によるとASTアプローチを取っているそうです。どちらのアプローチでも同様の機能を実装できるものの、ASTアプローチの方が早く有益なツールが作れるため、という理由のようです。

[ソースコード](https://github.com/rust-lang/rustfmt/blob/a36dc368d7c914014356c3d1f240f2caaf4692c2/src/parse/parser.rs#L7)を見ると、ASTの構築は[rustc_parse](https://doc.rust-lang.org/beta/nightly-rustc/rustc_parse/index.html)というRustコンパイラが使用してるparserをライブラリとして使用しているようですね。AST構築後、[FmtVisitor](https://github.com/rust-lang/rustfmt/blob/ee2bed96d60fd7e46b1fb868f6a8f27e3a8058d0/src/visitor.rs#L72)という構造体がASTのノードを訪問し、フォーマットしています。

FmtVisitorは下記のようになっていて、主に
- フォーマットの設定
- フォーマット結果を保持する文字列(buffer)
- フォーマッターの状態

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

```rust
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](https://github.com/rust-lang/rustfmt/issues/5464)
- [rustfmt removes comment between doc comment and generic params #5320](https://github.com/rust-lang/rustfmt/issues/5320)

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

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

## [google-java-format](https://github.com/google/google-java-format)

次に google-java-format を見てみました。  
フォーマットの流れを知るには[Formatter#format](https://github.com/google/google-java-format/blob/8afb866e7c5f26846c475c0cf6d7e314861b072c/core/src/main/java/com/google/googlejavaformat/java/Formatter.java#L112)メソッドを読めば良さそうです。  
本質的ではない分岐を削除し抜粋すると、以下のようになっています。

```java
    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();
```

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

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

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

## [uroboroSQL-formatter](https://github.com/future-architect/uroboroSQL-formatter)

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

## 感想

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

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