これは 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 をつくってみてはどうでしょうか?