Go言語の静的解析の仕組みについて調べた
この記事はGo5の11日目の記事です。 Goは静的解析ツール（特にコード生成まわり）が非常に強力です。Goの静的解析の仕組みについて調べたことについてまとめました。
（本当は何かツールを作りたかったのですが、どういう仕組みなのかだけの解説になっているのでご容赦ください。）
Golangと静的解析
Golangは静的解析をしやすいことを目指してシンプルな言語デザインになっています。
Why is the syntax so different from C? Other than declaration syntax, the differences are not major and stem from two desires. First, the syntax should feel light, without too many mandatory keywords, repetition, or arcana. Second, the language has been designed to be easy to analyze and can be parsed without a symbol table. This makes it much easier to build tools such as debuggers, dependency analyzers, automated documentation extractors, IDE plug-ins, and so on. C and its descendants are notoriously difficult in this regard.
https://golang.org/doc/faq#different_syntax
golangの静的解析を利用したライブラリ
golangの静的解析のしやすさを活用して、以下のようなライブラリで実際にコードの静的解析が行われています。
Genny
https://github.com/cheekybits/genny star数 1.1k
Goによるgenericsをgeneratorで実装したライブラリ。
あらかじめ、Goの文法としてvalidなテンプレートを作成しておき、内部に埋め込まれたgeneric.TypeをCLIで指定した別の型に置き換え、コード生成をしてくれます。
たとえば以下のようなテンプレートがあるとします。
package queue
import "github.com/cheekybits/genny/generic"
// NOTE: this is how easy it is to define a generic type
type Something generic.Type
// SomethingQueue is a queue of Somethings.
type SomethingQueue struct {
items []Something
}
func NewSomethingQueue() *SomethingQueue {
return &SomethingQueue{items: make([]Something, 0)}
}
func (q *SomethingQueue) Push(item Something) {
q.items = append(q.items, item)
}
func (q *SomethingQueue) Pop() Something {
item := q.items[0]
q.items = q.items[1:]
return item
}以下のコマンドを実行すると
cat source.go | genny gen "Something=string"上記の結果は以下になります。
type Something generic.Typeとして定義している Somethingがすべてstringに置換され、SomethingQueueがStringQueueに置き換えられていることがわかります。
// This file was automatically generated by genny.
// Any changes will be lost if this file is regenerated.
// see https://github.com/cheekybits/genny
package queue
// StringQueue is a queue of Strings.
type StringQueue struct {
items []string
}
func NewStringQueue() *StringQueue {
return &StringQueue{items: make([]string, 0)}
}
func (q *StringQueue) Push(item string) {
q.items = append(q.items, item)
}
func (q *StringQueue) Pop() string {
item := q.items[0]
q.items = q.items[1:]
return item
}gqlgen
https://github.com/99designs/gqlgen スター数 3.6k
Golangで実装されたGraphQLライブラリです。 GraphQLのスキーマ上で定義されたtypeやscalarは、まずGolangで実装されたstructとマッピングできるかチェックされます。もしもすでにあるstructのフィールド、またはメソッドにシグネチャが対応していればあえてresolverを実装する必要はありません。
そのあたりの既存のgoの定義チェックをして、生成するコードを調整するという実装に静的解析が活用されています。 https://github.com/99designs/gqlgen/blob/9cfd817e013b951206bc969ba517c98ff208a11c/codegen/config/binder.go
実際にやってみる
GolangではGo言語の静的解析ライブラリを標準で提供しています。なので標準ライブラリの使い方を覚えて、ASTの操作方法を覚えれば大丈夫（なはず）です。
抽象構文木（AST）にする
まず字句解析をしてプログラムをASTに変換してみます。このためには"go/parser"モジュールを用います。字句解析ではプログラムをトークンに変換, トークンの種類, positionなどを取得するだけです。
表示する
package main
import (
"go/ast"
"go/parser"
"go/token"
"log"
)
const hello = `package main
import "fmt"
func main() {
fmt.Println("Hello, world")
}`
func main() {
fset := token.NewFileSet()
// Parse the input string, []byte, or io.Reader,
// recording position information in fset.
// ParseFile returns an *ast.File, a syntax tree.
f, err := parser.ParseFile(fset, "", hello, 0)
if err != nil {
log.Fatal(err) // parse error
}
ast.Print(fset, f)
}出力
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:9
48 . . . . . . . . . Name: "fmt"
49 . . . . . . . . }
50 . . . . . . . . Sel: *ast.Ident {
51 . . . . . . . . . NamePos: 6:13
52 . . . . . . . . . Name: "Println"
53 . . . . . . . . }
54 . . . . . . . }
55 . . . . . . . Lparen: 6:20
56 . . . . . . . Args: []ast.Expr (len = 1) {
57 . . . . . . . . 0: *ast.BasicLit {
58 . . . . . . . . . ValuePos: 6:21
59 . . . . . . . . . Kind: STRING
60 . . . . . . . . . Value: "\"Hello, world\""
61 . . . . . . . . }
62 . . . . . . . }
63 . . . . . . . Ellipsis: -
64 . . . . . . . Rparen: 6:35
65 . . . . . . }
66 . . . . . }
67 . . . . }
68 . . . . Rbrace: 7:1
69 . . . }
70 . . }
71 . }
72 . Scope: *ast.Scope {
73 . . Objects: map[string]*ast.Object (len = 1) {
74 . . . "main": *(obj @ 27)
75 . . }
76 . }
77 . Imports: []*ast.ImportSpec (len = 1) {
78 . . 0: *(obj @ 12)
79 . }
80 . Unresolved: []*ast.Ident (len = 1) {
81 . . 0: *(obj @ 46)
82 . }
83 }ASTを探索する
ast.Inspect関数
ast.Inspectを利用するとast.Node（*ast.Fileもこれを満たす）を深さ優先探索でひとつひとつのnodeを探索することができます。 https://golang.org/pkg/go/ast/#Inspect
package main
import (
"fmt"
"go/ast"
"go/parser"
"go/token"
"log"
)
const hello = `package main
import "fmt"
func main() {
fmt.Println("Hello, world")
}`
func main() {
fset := token.NewFileSet()
// Parse the input string, []byte, or io.Reader,
// recording position information in fset.
// ParseFile returns an *ast.File, a syntax tree.
f, err := parser.ParseFile(fset, "", hello, 0)
if err != nil {
log.Fatal(err) // parse error
}
ast.Inspect(f, func(n ast.Node) bool {
var s string
switch x := n.(type) {
case *ast.BasicLit:
s = x.Value
case *ast.Ident:
s = x.Name
}
if s != "" {
fmt.Printf("%s:\t%s\n", fset.Position(n.Pos()), s)
}
return true
})
}結果
1:9: main
3:8: "fmt"
5:6: main
6:9: fmt
6:13: Println
6:21: "Hello, world"
ast.Walk関数
ast.Inspectよりも更に柔軟にastを探索したいときはast.Walk関数を利用します。これはVisitorパターンを利用しており、nodeを調べるときの処理を別の関数に差し替えすることができます。
https://golang.org/pkg/go/ast/#Walk
詳細については 抽象構文木（AST）をトラバースする #golangに詳しいのでご参照ください。
型を取り出す
ここで主に使われるパッケージは "go/types"です go/typesについては、公式で用意されているドキュメントが非常に参考になります。ぜひ確認しましょう。 https://github.com/golang/example/blob/master/gotypes/README.md
とにかくこのパッケージがやっていることは主に3つです。
The Go type checker does three main things. First, for every name in the program, it determines which declaration the name refers to; this is known as identifier resolution. Second, for every expression in the program, it determines what type that expression has, or reports an error if the expression has no type, or has an inappropriate type for its context; this is known as type deduction. Third, for every constant expression in the program, it determines the value of that constant; this is known as constant evaluation.
- Identifier resolution（定義と名前を紐付ける）
- Type deduction(型定義と型エラーのチェック)
- Constant evaluetion（定数評価）
サンプル
package main
import (
"fmt"
"go/ast"
"go/importer"
"go/parser"
"go/token"
"go/types"
"log"
)
const hello = `package main
import "fmt"
type Hoge struct {
Foo string
Bar int
}
func main() {
fmt.Println("Hello, world")
}`
func main() {
fset := token.NewFileSet()
// Parse the input string, []byte, or io.Reader,
// recording position information in fset.
// ParseFile returns an *ast.File, a syntax tree.
f, err := parser.ParseFile(fset, "", hello, 0)
if err != nil {
log.Fatal(err) // parse error
}
// A Config controls various options of the type checker.
// The defaults work fine except for one setting:
// we must specify how to deal with imports.
conf := types.Config{Importer: importer.Default()}
info := &types.Info{
Defs: make(map[*ast.Ident]types.Object),
Uses: make(map[*ast.Ident]types.Object),
}
// Type-check the package containing only file f.
// Check returns a *types.Package.
pkg, err := conf.Check("cmd/hello", fset, []*ast.File{f}, info)
if err != nil {
log.Fatal(err) // type error
}
fmt.Println("=== Package ===")
fmt.Printf("Package %q\n", pkg.Path())
fmt.Printf("Name: %s\n", pkg.Name())
fmt.Printf("Imports: %s\n", pkg.Imports())
fmt.Printf("Scope: %s\n", pkg.Scope())
fmt.Println("")
// info
fmt.Println("=== Info ===")
for id, obj := range info.Defs {
fmt.Printf("%s: %q defines %v\n",
fset.Position(id.Pos()), id.Name, obj)
}
for id, obj := range info.Uses {
fmt.Printf("%s: %q uses %v\n",
fset.Position(id.Pos()), id.Name, obj)
}
fmt.Println("")
// object
fmt.Println("=== Object ===")
scope := pkg.Scope()
for _, name := range scope.Names() {
obj := scope.Lookup(name)
fmt.Printf("%s: %+v\n", name, obj)
}
}実行結果
=== Package ===
Package "cmd/hello"
Name: main
Imports: [package fmt ("fmt")]
Scope: package "cmd/hello" scope 0xc0000b94a0 {
. type cmd/hello.Hoge struct{Foo string; Bar int}
. func cmd/hello.main()
}
=== Info ===
6:2: "Foo" defines field Foo string
7:2: "Bar" defines field Bar int
1:9: "main" defines <nil>
5:6: "Hoge" defines type cmd/hello.Hoge struct{Foo string; Bar int}
10:6: "main" defines func cmd/hello.main()
6:6: "string" uses type string
7:6: "int" uses type int
11:9: "fmt" uses package fmt
11:13: "Println" uses func fmt.Println(a ...interface{}) (n int, err error)
=== Object ===
Hoge: type cmd/hello.Hoge struct{Foo string; Bar int}
main: func cmd/hello.main()
主な概念
https://github.com/golang/example/blob/master/gotypes/README.md から重要な箇所をピックアップしています。
types.Object
types.Objectはinterfaceです。 ast.Identと対応していて、以下のどれかのstructに変換することができます。
Object = *Func // function, concrete method, or abstract method | *Var // variable, parameter, result, or struct field | *Const // constant | *TypeName // type name | *Label // statement label | *PkgName // package name, e.g. json after import "encoding/json" | *Builtin // predeclared function such as append or len | *Nil // predeclared nil
types.Scope
types.Scopeはグローバル、パッケージ、関数といったスコープを定義します。
Scope内の定義は、Names()関数で取得でき、またInspect(name)でtypes.Objectを取得できます。
types.Info
info := &types.Info{
Defs: make(map[*ast.Ident]types.Object),
Uses: make(map[*ast.Ident]types.Object),
}
// Type-check the package containing only file f.
// Check returns a *types.Package.
pkg, err := conf.Check("cmd/hello", fset, []*ast.File{f}, info)でconf.Checkの第4引数に渡っている構造体です。 これはどのast.Identがtypes.Objectに変換されているのかをマッピングしています。 状況によってtypes.Objectで取得した情報を元にASTの書き換えを行う際には、このtypes.Infoの情報に基づいてASTをトラバースするようです。
まとめ
若干尻切れなのですが、この記事ではGoの静的解析の基本を解説しました。Golangで静的解析ができるようになると非常に強力なので、静的解析で良きGopherライフをお送りください！
参考
https://github.com/golang/example/blob/master/gotypes/README.md https://qiita.com/tenntenn/items/dfc112ae7bb8c9703ab9