これは Aizu LT feat. CyberAgent での発表に補足を加えた記事です。
発表資料は 👇
gofmt
Go には標準でさまざまなツールが揃っています。
その中でも自分が好きなものに gofmt があります。
gofmt は所謂コードフォーマッタの一つで、ソースコードを整形してくれるツールです。
例えば、以下のようなコードがあります。
package main import "fmt" func main() { fmt.Println("Hello, "+"World") }
これを gofmt で整形すると以下のようになります。
package main import "fmt" func main() { fmt.Println("Hello, " + "World") }
package・import・main 間に改行が追加されていたり、スペースがタブに置換されていたり、+ 演算子の前後にスペースが一つ追加されていたりしているのがわかるかと思います。
このように、スタイルを強制的にフォーマットしてくれるので、開発者間でスタイルを統一できて便利です。
他の言語でも似たような実装がたくさん存在していて、例えば Python であれば YAPF、JavaScript であれば Prettier などが有名です。
では、gofmt は一体どのようにして整形を行っているのでしょうか？
以降では上のサンプルコードに対して gofmt を実行した場合を想定してコードを見ていきます。
なお、ソースをすべて紹介すると無限に時間がかかるので、以下の前提環境に記載しているコマンドを実行したときのケースのみ追っていきます。
前提環境
以下の環境を前提にしています。
- golang/go
- 157d8cfbc13fbc4c849075e905b0001fb248b5e6
- ソース: golang/go/src/cmd/gofmt
- 実行方法: gofmt main.go
読んでいく
エントリポイントの main を見ると gofmtMain を呼び出しています
func main() { // call gofmtMain in a separate function // so that it can use defer and have them // run before the exit. gofmtMain() os.Exit(exitCode) }
gofmtMain の中では引数をパースした後、ファイル名を回しています。
ファイルが存在し、ディレクトリではない場合、processFile を呼び出しています。
ディレクトリの場合、 walkDir を呼び出し、その walk 中で processFile を呼び出しています。
for i := 0; i < flag.NArg(); i++ { path := flag.Arg(i) switch dir, err := os.Stat(path); { case err != nil: report(err) case dir.IsDir(): walkDir(path) default: if err := processFile(path, nil, os.Stdout, false); err != nil { report(err) } } }
processFile では、ファイルの中身を読み込み、parse を呼んでいます。
src, err := ioutil.ReadAll(in) if err != nil { return err } file, sourceAdj, indentAdj, err := parse(fileSet, filename, src, stdin) if err != nil { return err }
parse では go/parser パッケージの parser.ParseFile を呼んで、成功した場合、関数を return しています。
go/parser パッケージは Go のソースコードから AST (Abstract Syntax Tree: 抽象構文木) を構築するためのパッケージです。
parser - The Go Programming Language
// Try as whole source file. file, err = parser.ParseFile(fset, filename, src, parserMode) // If there's no error, return. If the error is that the source file didn't begin with a // package line and source fragments are ok, fall through to // try as a source fragment. Stop and return on any other error. if err == nil || !fragmentOk || !strings.Contains(err.Error(), "expected 'package'") { return }
parser.ParseFile 関数から戻ってきて再び parse です。
AST を取得した後、SortImports を呼び出しています。
ここではあまり触れませんが、重複して import しているパッケージの削除やパッケージのソートを行っています。
また、simplifyAST オプションを有効にしていた場合、AST へ破壊的変更を加え、構造をシンプルにします。
例えば、s[a:len(s)] のような箇所は s[a:] と等価なので、後者の方へ統一します (この例は simplify.go#L52-53 より引用しました)
これらの処理の後に、format を呼び出しています。
ast.SortImports(fileSet, file) if *simplifyAST { simplify(file) } res, err := format(fileSet, file, sourceAdj, indentAdj, src, printer.Config{Mode: printerMode, Tabwidth: tabWidth}) if err != nil { return err }
format では cfg.Fprint を呼び出した後にその結果を返しています。
上の format の呼び出しを見ると、cfg に対応する引数として printer.Config{Mode: printerMode, Tabwidth: tabWidth} を渡しています。
これは go/printer パッケージの構造体です。
go/printer パッケージは AST の出力を担うパッケージで、Fprint の説明には "Fprint "pretty-prints" an AST node to output for a given configuration cfg." とあることから、AST を整形して出力してくれることがわかります。
cfg.Fprint 以降の処理は引数のフラグに対応するアウトプットを行うだけなので、実際に gofmt での整形を担っているのは go/printer パッケージとなっています。
var buf bytes.Buffer err := cfg.Fprint(&buf, fset, file) if err != nil { return nil, err } return buf.Bytes(), nil
Fprint はその中ですぐに fprint という unexported なメソッドを呼んでいます。
ここで、printNode というメソッドを呼んでいます。
if err = p.printNode(node); err != nil { return }
printNode は AST を再帰的に呼び出すためのメソッドです。
ここで一旦、今回のソースの AST の構造を確認しておきたいと思います。
go/ast パッケージにある Print を使うと AST を見やすく出力してくれます。
0 *ast.File {
1 . Package: 1:1
2 . Name: *ast.Ident {
3 . . NamePos: 1:9
4 . . Name: "main"
5 . }
6 . Decls: []ast.Decl (len = 2) {
7 . . 0: *ast.GenDecl {
8 . . . TokPos: 3:1
9 . . . Tok: import
10 . . . Lparen: -
11 . . . Specs: []ast.Spec (len = 1) {
12 . . . . 0: *ast.ImportSpec {
13 . . . . . Path: *ast.BasicLit {
14 . . . . . . ValuePos: 3:8
15 . . . . . . Kind: STRING
16 . . . . . . Value: "\"fmt\""
17 . . . . . }
18 . . . . . EndPos: -
19 . . . . }
20 . . . }
21 . . . Rparen: -
22 . . }
23 . . 1: *ast.FuncDecl {
24 . . . Name: *ast.Ident {
25 . . . . NamePos: 5:6
26 . . . . Name: "main"
27 . . . . Obj: *ast.Object {
28 . . . . . Kind: func
29 . . . . . Name: "main"
30 . . . . . Decl: *(obj @ 23)
31 . . . . }
32 . . . }
33 . . . Type: *ast.FuncType {
34 . . . . Func: 5:1
35 . . . . Params: *ast.FieldList {
36 . . . . . Opening: 5:10
37 . . . . . Closing: 5:11
38 . . . . }
39 . . . }
40 . . . Body: *ast.BlockStmt {
41 . . . . Lbrace: 5:13
42 . . . . List: []ast.Stmt (len = 1) {
43 . . . . . 0: *ast.ExprStmt {
44 . . . . . . X: *ast.CallExpr {
45 . . . . . . . Fun: *ast.SelectorExpr {
46 . . . . . . . . X: *ast.Ident {
47 . . . . . . . . . NamePos: 6:2
48 . . . . . . . . . Name: "fmt"
49 . . . . . . . . }
50 . . . . . . . . Sel: *ast.Ident {
51 . . . . . . . . . NamePos: 6:6
52 . . . . . . . . . Name: "Println"
53 . . . . . . . . }
54 . . . . . . . }
55 . . . . . . . Lparen: 6:13
56 . . . . . . . Args: []ast.Expr (len = 1) {
57 . . . . . . . . 0: *ast.BinaryExpr {
58 . . . . . . . . . X: *ast.BasicLit {
59 . . . . . . . . . . ValuePos: 6:14
60 . . . . . . . . . . Kind: STRING
61 . . . . . . . . . . Value: "\"Hello, \""
62 . . . . . . . . . }
63 . . . . . . . . . OpPos: 6:24
64 . . . . . . . . . Op: +
65 . . . . . . . . . Y: *ast.BasicLit {
66 . . . . . . . . . . ValuePos: 6:26
67 . . . . . . . . . . Kind: STRING
68 . . . . . . . . . . Value: "\"World\""
69 . . . . . . . . . }
70 . . . . . . . . }
71 . . . . . . . }
72 . . . . . . . Ellipsis: -
73 . . . . . . . Rparen: 6:33
74 . . . . . . }
75 . . . . . }
76 . . . . }
77 . . . . Rbrace: 7:1
78 . . . }
79 . . }
80 . }
81 . Scope: *ast.Scope {
82 . . Objects: map[string]*ast.Object (len = 1) {
83 . . . "main": *(obj @ 27)
84 . . }
85 . }
86 . Imports: []*ast.ImportSpec (len = 1) {
87 . . 0: *(obj @ 12)
88 . }
89 . Unresolved: []*ast.Ident (len = 1) {
90 . . 0: *(obj @ 46)
91 . }
92 }
*ast.File 型がトップレベルに位置し、この構造体が package の情報や import、関数の宣言等を保持していることがわかるかと思います。
main の部分を見てみると、main 自体は *ast.FuncDecl 型で表されていて、関数の中身に相当する部分である Body フィールドを持っています。
Body フィールドは *ast.BlockStmt の名前の通り、ブロックを表す型となっていて、子にいくつかのステートメントを持ちます。
ソースコードでは fmt.Println しかないので、当然子も一つだけです。
fmt.Println に対応するステートメントの型は ExprStmt となっています。
ExprStmt は一つの式を表しています。expression + statement なので、なんとも不思議な感じがしますが、 stand-alone とある通り、評価されても値を返さない式のことを指していて、それを文としているようです。 (要確認)
ExprStmt は Node インターフェースを埋め込んでいて、Node 型は各式に対応する型が実装しています。
例えば、今回のように、 *ast.CallExpr もその一つです。
*ast.CallExpr は対象の関数を識別するための *ast.SelectorExpr 、引数の情報等を持っています。
引数には "Hello, " + "World" があったことを思い出してください。
これは見て分かる通り二項演算なので、 *ast.BinaryExpr が引数の一番目にあることがわかると思います。
この式は X も Y もリテラルなので、2つの *ast.BasicLit を持っています。
ちょっと複雑ですが、これらを踏まえて、printNode を読んでいきます。
switch n := node.(type) { case ast.Expr: p.expr(n) case ast.Stmt: // A labeled statement will un-indent to position the label. // Set p.indent to 1 so we don't get indent "underflow". if _, ok := n.(*ast.LabeledStmt); ok { p.indent = 1 } p.stmt(n, false) case ast.Decl: p.decl(n) case ast.Spec: p.spec(n, 1, false) case []ast.Stmt: // A labeled statement will un-indent to position the label. // Set p.indent to 1 so we don't get indent "underflow". for _, s := range n { if _, ok := s.(*ast.LabeledStmt); ok { p.indent = 1 } } p.stmtList(n, 0, false) case []ast.Decl: p.declList(n) case *ast.File: p.file(n) default: goto unsupported }
package
package は *ast.File で表されていました。
つまり、ここでは case *ast.File が該当するので p.file(n) が呼ばれます。
func (p *printer) file(src *ast.File) { p.setComment(src.Doc) p.print(src.Pos(), token.PACKAGE, blank) p.expr(src.Name) p.declList(src.Decls) p.print(newline) }
file は package のトップレベルのドキュメントコメントを出力した後、package という文字を出力し、スペース (blank) を空けたあと、src.Name を引数に p.expr を呼び出しています。
expr はすぐに expr1 を呼び出します。
これは各式を再帰的に呼び出すためのメソッドです。
とても長いので、expr1 の内容をすべて貼ることはできませんが、switch によって各式へ振り分けるとともに、式を整形して出力しています。
src.Name は *ast.Ident なので、その箇所を見てみると、
switch x := expr.(type) { case *ast.Ident: p.print(x)
ただ出力しているだけでした。
さて、file メソッドに戻ります。 p.expr のあとには p.declList を呼んで、そのあとに改行を一つ出力しています。
declList は名前の通り、*ast.Decl のスライスを扱うためのメソッドです。
今回の AST には GenDecl (import) と FuncDecl (main) がありました。
func (p *printer) declList(list []ast.Decl) { tok := token.ILLEGAL for _, d := range list { prev := tok tok = declToken(d) // If the declaration token changed (e.g., from CONST to TYPE) // or the next declaration has documentation associated with it, // print an empty line between top-level declarations. // (because p.linebreak is called with the position of d, which // is past any documentation, the minimum requirement is satisfied // even w/o the extra getDoc(d) nil-check - leave it in case the // linebreak logic improves - there's already a TODO). if len(p.output) > 0 { // only print line break if we are not at the beginning of the output // (i.e., we are not printing only a partial program) min := 1 if prev != tok || getDoc(d) != nil { min = 2 } p.linebreak(p.lineFor(d.Pos()), min, ignore, false) } p.decl(d) } }
ここで、コメントに詳細にかかれているとおり、現在の宣言の token の値が変わっていれば空行を一行挟むことがわかります。
つまり、import と main では token の値がそれぞれ import と func で異なるため、その間に空行が挿入されることになります。
このあと、p.decl でそれぞれの出力を行います。
ここでやっと package の部分が終わり、import へ移ります。
import
p.decl の中では、毎度と同様にそれぞれの宣言へ振り分けられます
func (p *printer) decl(decl ast.Decl) { switch d := decl.(type) { case *ast.BadDecl: p.print(d.Pos(), "BadDecl") case *ast.GenDecl: p.genDecl(d) case *ast.FuncDecl: p.funcDecl(d) default: panic("unreachable") } }
p.genDecl では最初に左のパーレンが有効 (ソースコードで書かれている) かどうかをチェックしています。今回はシングルラインなので、この部分は省略します。
func (p *printer) genDecl(d *ast.GenDecl) { p.setComment(d.Doc) p.print(d.Pos(), d.Tok, blank) if d.Lparen.IsValid() { ... } else { // single declaration p.spec(d.Specs[0], 1, true) } }
p.spec では、*ast.ImportSpec に該当する箇所が実行されます。
func (p *printer) spec(spec ast.Spec, n int, doIndent bool) { switch s := spec.(type) { case *ast.ImportSpec: p.setComment(s.Doc) if s.Name != nil { p.expr(s.Name) p.print(blank) } p.expr(sanitizeImportPath(s.Path)) p.setComment(s.Comment) p.print(s.EndPos)
ここで、コメントを出力したあと、s.Name が存在するかをチェックしています。
これは、無名関数かどうかをチェックしていて、もし無名関数でなければ関数名とその後に一つスペースを挿入します。
その後、path をそれぞれ出力し、EndPos を出力しますが、今回はシングルラインなので何も出力されません。
main
やっと main 関数です。(長かった…)
import とほぼ同様に、p.decl で p.funcDecl が呼び出されます。
p.funcDecl は以下のようになっています。
func (p *printer) funcDecl(d *ast.FuncDecl) { p.setComment(d.Doc) p.print(d.Pos(), token.FUNC, blank) if d.Recv != nil { p.parameters(d.Recv) // method: print receiver p.print(blank) } p.expr(d.Name) p.signature(d.Type.Params, d.Type.Results) p.funcBody(p.distanceFrom(d.Pos()), vtab, d.Body) }
コメントを出力した後、func の文字とスペースを出力し、その関数がメソッドであるならばレシーバの部分 ((p *Pointer) の様な部分)を出力しています。
その後は、関数名、引数と返り値、関数の中身と順番に出力していっています。
func (p *printer) funcBody(headerSize int, sep whiteSpace, b *ast.BlockStmt) { if b == nil { return } // save/restore composite literal nesting level defer func(level int) { p.level = level }(p.level) p.level = 0 const maxSize = 100 if headerSize+p.bodySize(b, maxSize) <= maxSize { p.print(sep, b.Lbrace, token.LBRACE) if len(b.List) > 0 { p.print(blank) for i, s := range b.List { if i > 0 { p.print(token.SEMICOLON, blank) } p.stmt(s, i == len(b.List)-1) } p.print(blank) } p.print(noExtraLinebreak, b.Rbrace, token.RBRACE, noExtraLinebreak) return }
funcBody では、body が空であれば何もせずに return します。
if headerSize+p.bodySize(b, maxSize) <= maxSize で関数の header から body までの長さを検査して、 maxSize を超えていない場合を処理しています。
ここが true になるのは、
- ブロックの終わり (}) が、始まり ({) と異なる行にある (= 関数が一行で収まっていない)
- 一行で収まっているが、ステートメントが 5 つ以上存在する
- それ以外 (e.g. 関数名) の要因でで単純に body のサイズが maxSize を超える場合
です
この中でまず左のブレース ({) を出力したあと、ステートメントを順に出力しています。
ここで、SEMICOLON が出力されているのは、関数が一行で収まっているということは、ステートメント間が改行ではなくセミコロンで区切られていることを意味するためです。
それ以外の場合、つまり、今回のような関数が一行でない場合、上の部分は実行されずに、p.block が呼ばれます。
func (p *printer) block(b *ast.BlockStmt, nindent int) { p.print(b.Lbrace, token.LBRACE) p.stmtList(b.List, nindent, true) p.linebreak(p.lineFor(b.Rbrace), 1, ignore, true) p.print(b.Rbrace, token.RBRACE) }
ここでは、p.stmtList で body のステートメントをすべて表示し、その前後にブレースを挿入しています。
func (p *printer) stmtList(list []ast.Stmt, nindent int, nextIsRBrace bool) { i := 0 for _, s := range list { ... p.stmt(s, nextIsRBrace && i == len(list)-1) ...
p.stmtList では、それぞれのステートメントを出力しています。
第二引数が true となるのは、nextIsRBrace が true かつ現在のステートメントが最後のステートメントの場合です。
ブロックの持つステートメントは fmt.Println を含んでいる *ast.ExprStmt のみなので、p.stmt はその条件を通ります。
func (p *printer) stmt(stmt ast.Stmt, nextIsRBrace bool) { p.print(stmt.Pos()) switch s := stmt.(type) { ... case *ast.ExprStmt: const depth = 1 p.expr0(s.X, depth)
s.X は、実際には埋め込まれている *ast.CallExpr を指しているので、 s.CallExpr.X と等価です。
p.expr0 は、 p.expr1 を呼び出します。p.expr1 は package の部分を読んでいるときにも出てきました。各式を処理するメソッドでした。
*ast.CallExpr の部分を見るとこのようになっています。
case *ast.CallExpr: if len(x.Args) > 1 { depth++ } var wasIndented bool if _, ok := x.Fun.(*ast.FuncType); ok { // conversions to literal function types require parentheses around the type p.print(token.LPAREN) wasIndented = p.possibleSelectorExpr(x.Fun, token.HighestPrec, depth) p.print(token.RPAREN) } else { wasIndented = p.possibleSelectorExpr(x.Fun, token.HighestPrec, depth) } p.print(x.Lparen, token.LPAREN) if x.Ellipsis.IsValid() { p.exprList(x.Lparen, x.Args, depth, 0, x.Ellipsis) p.print(x.Ellipsis, token.ELLIPSIS) if x.Rparen.IsValid() && p.lineFor(x.Ellipsis) < p.lineFor(x.Rparen) { p.print(token.COMMA, formfeed) } } else { p.exprList(x.Lparen, x.Args, depth, commaTerm, x.Rparen) } p.print(x.Rparen, token.RPAREN) if wasIndented { p.print(unindent) }
まず *ast.SelectorExpr を表す部分を出力し、その後左パーレンを出力しています。
その後、この関数の引数リストを p.exprList へ渡して、最後に右パーレンで括弧を閉じています。
p.exprList はかなり複雑ですが、ステートメントのリストが一つだけの場合、
p.expr0(x, depth)
内容は実質これだけです。
引数には *ast.BinaryExpr が入っているので、これが p.expr0 -> p.expr1 へと渡されます。
case *ast.BinaryExpr: if depth < 1 { p.internalError("depth < 1:", depth) depth = 1 } p.binaryExpr(x, prec1, cutoff(x, depth), depth)
p.expr1 のこの部分で p.binaryExpr が呼ばれます。
cutoff 関数では、子ノードを walk することで子に現れる優先度を探しています。
今回、BinaryExpr はトップレベル (depth = 1) となっているので、優先度は unary precedence に相当する 6 となっています。
func (p *printer) binaryExpr(x *ast.BinaryExpr, prec1, cutoff, depth int) { prec := x.Op.Precedence() ... printBlank := prec < cutoff ws := indent p.expr1(x.X, prec, depth+diffPrec(x.X, prec)) if printBlank { p.print(blank) } xline := p.pos.Line // before the operator (it may be on the next line!) yline := p.lineFor(x.Y.Pos()) p.print(x.OpPos, x.Op) if xline != yline && xline > 0 && yline > 0 { // at least one line break, but respect an extra empty line // in the source if p.linebreak(yline, 1, ws, true) { ws = ignore printBlank = false // no blank after line break } } if printBlank { p.print(blank) } p.expr1(x.Y, prec+1, depth+1) if ws == ignore { p.print(unindent) } }
*ast.BinaryExpr の持つ演算子の優先度と cutoff で求めた優先度を比較し、cutoff の方が大きければスペースを入れるようになります。
スペースが入らないパターンは、例えば 1 + 2/3 のような場合があります。
これを AST へ変換すると、*ast.BinaryExpr の X に 1 に対応する *ast.BasicLit、 Y に 2/3 に対応する *ast.BinaryExpr が入ります。
Y に入っている *ast.BinaryExpr が引数として binaryExpr へ入ってきた時、prec は / の優先度である 5、cutoff は 4 が入っているため、printBlank が false となり、Y の出力ではスペースが入らなくなります。
もう少し読み進めていくと、 p.expr1 で x.X を評価・出力、同じように、x.Op とスペース、そして x.Y を出力しているのがわかります。
まとめ
ここまでで、ようやくサンプルコードを gofmt で整形するときの処理がすべて終わりました。
まとめてみると、
大きく分けてこの様な部分から成り立っていることがわかりました。
AST さえ構築できれば整形ルールに従って整形することは意外と簡単でした。
また、上記の理由から任意の言語でも同じようなアプローチで整形できそうです。
LT の発表で紹介するために簡単なマークダウンを整形するツールを書いてみました。
すべてのブロック、インラインをパースしているわけではないので、未対応なものが含まれているマークダウンでは一部上手く動かないと思いますが、デモ用には十分だと思います。(言い訳)
AST の構築には russross/blackfriday を利用させていただきました。
マークダウンはプログラミング言語と異なり、式などがないため比較するとかなりシンプルでした。
意外と簡単に実装できたので、一度みなさんもオリジナルの fmt をつくってみてはどうでしょうか？
