Go言語の静的解析の仕組みについて調べた

公開日: 2019年12月10日GitHub

この記事は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で指定した別の型に置き換え、コード生成をしてくれます。

たとえば以下のようなテンプレートがあるとします。

1package queue
2
3import "github.com/cheekybits/genny/generic"
4
5// NOTE: this is how easy it is to define a generic type
6type Something generic.Type
7
8// SomethingQueue is a queue of Somethings.
9type SomethingQueue struct {
10  items []Something
11}
12
13func NewSomethingQueue() *SomethingQueue {
14  return &SomethingQueue{items: make([]Something, 0)}
15}
16func (q *SomethingQueue) Push(item Something) {
17  q.items = append(q.items, item)
18}
19func (q *SomethingQueue) Pop() Something {
20  item := q.items[0]
21  q.items = q.items[1:]
22  return item
23}
24

以下のコマンドを実行すると

1cat source.go | genny gen "Something=string"
2

上記の結果は以下になります。 type Something generic.Typeとして定義している Somethingがすべてstringに置換され、SomethingQueueがStringQueueに置き換えられていることがわかります。

1// This file was automatically generated by genny.
2// Any changes will be lost if this file is regenerated.
3// see https://github.com/cheekybits/genny
4
5package queue
6
7// StringQueue is a queue of Strings.
8type StringQueue struct {
9  items []string
10}
11
12func NewStringQueue() *StringQueue {
13  return &StringQueue{items: make([]string, 0)}
14}
15func (q *StringQueue) Push(item string) {
16  q.items = append(q.items, item)
17}
18func (q *StringQueue) Pop() string {
19  item := q.items[0]
20  q.items = q.items[1:]
21  return item
22}
23

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などを取得するだけです。

表示する

1package main
2
3import (
4    "go/ast"
5    "go/parser"
6    "go/token"
7    "log"
8)
9
10const hello = `package main
11
12import "fmt"
13
14func main() {
15        fmt.Println("Hello, world")
16}`
17
18func main() {
19    fset := token.NewFileSet()
20
21    // Parse the input string, []byte, or io.Reader,
22    // recording position information in fset.
23    // ParseFile returns an *ast.File, a syntax tree.
24    f, err := parser.ParseFile(fset, "", hello, 0)
25    if err != nil {
26        log.Fatal(err) // parse error
27    }
28
29    ast.Print(fset, f)
30}
31

出力

1     0  *ast.File {
2     1  .  Package: 1:1
3     2  .  Name: *ast.Ident {
4     3  .  .  NamePos: 1:9
5     4  .  .  Name: "main"
6     5  .  }
7     6  .  Decls: []ast.Decl (len = 2) {
8     7  .  .  0: *ast.GenDecl {
9     8  .  .  .  TokPos: 3:1
10     9  .  .  .  Tok: import
11    10  .  .  .  Lparen: -
12    11  .  .  .  Specs: []ast.Spec (len = 1) {
13    12  .  .  .  .  0: *ast.ImportSpec {
14    13  .  .  .  .  .  Path: *ast.BasicLit {
15    14  .  .  .  .  .  .  ValuePos: 3:8
16    15  .  .  .  .  .  .  Kind: STRING
17    16  .  .  .  .  .  .  Value: "\"fmt\""
18    17  .  .  .  .  .  }
19    18  .  .  .  .  .  EndPos: -
20    19  .  .  .  .  }
21    20  .  .  .  }
22    21  .  .  .  Rparen: -
23    22  .  .  }
24    23  .  .  1: *ast.FuncDecl {
25    24  .  .  .  Name: *ast.Ident {
26    25  .  .  .  .  NamePos: 5:6
27    26  .  .  .  .  Name: "main"
28    27  .  .  .  .  Obj: *ast.Object {
29    28  .  .  .  .  .  Kind: func
30    29  .  .  .  .  .  Name: "main"
31    30  .  .  .  .  .  Decl: *(obj @ 23)
32    31  .  .  .  .  }
33    32  .  .  .  }
34    33  .  .  .  Type: *ast.FuncType {
35    34  .  .  .  .  Func: 5:1
36    35  .  .  .  .  Params: *ast.FieldList {
37    36  .  .  .  .  .  Opening: 5:10
38    37  .  .  .  .  .  Closing: 5:11
39    38  .  .  .  .  }
40    39  .  .  .  }
41    40  .  .  .  Body: *ast.BlockStmt {
42    41  .  .  .  .  Lbrace: 5:13
43    42  .  .  .  .  List: []ast.Stmt (len = 1) {
44    43  .  .  .  .  .  0: *ast.ExprStmt {
45    44  .  .  .  .  .  .  X: *ast.CallExpr {
46    45  .  .  .  .  .  .  .  Fun: *ast.SelectorExpr {
47    46  .  .  .  .  .  .  .  .  X: *ast.Ident {
48    47  .  .  .  .  .  .  .  .  .  NamePos: 6:9
49    48  .  .  .  .  .  .  .  .  .  Name: "fmt"
50    49  .  .  .  .  .  .  .  .  }
51    50  .  .  .  .  .  .  .  .  Sel: *ast.Ident {
52    51  .  .  .  .  .  .  .  .  .  NamePos: 6:13
53    52  .  .  .  .  .  .  .  .  .  Name: "Println"
54    53  .  .  .  .  .  .  .  .  }
55    54  .  .  .  .  .  .  .  }
56    55  .  .  .  .  .  .  .  Lparen: 6:20
57    56  .  .  .  .  .  .  .  Args: []ast.Expr (len = 1) {
58    57  .  .  .  .  .  .  .  .  0: *ast.BasicLit {
59    58  .  .  .  .  .  .  .  .  .  ValuePos: 6:21
60    59  .  .  .  .  .  .  .  .  .  Kind: STRING
61    60  .  .  .  .  .  .  .  .  .  Value: "\"Hello, world\""
62    61  .  .  .  .  .  .  .  .  }
63    62  .  .  .  .  .  .  .  }
64    63  .  .  .  .  .  .  .  Ellipsis: -
65    64  .  .  .  .  .  .  .  Rparen: 6:35
66    65  .  .  .  .  .  .  }
67    66  .  .  .  .  .  }
68    67  .  .  .  .  }
69    68  .  .  .  .  Rbrace: 7:1
70    69  .  .  .  }
71    70  .  .  }
72    71  .  }
73    72  .  Scope: *ast.Scope {
74    73  .  .  Objects: map[string]*ast.Object (len = 1) {
75    74  .  .  .  "main": *(obj @ 27)
76    75  .  .  }
77    76  .  }
78    77  .  Imports: []*ast.ImportSpec (len = 1) {
79    78  .  .  0: *(obj @ 12)
80    79  .  }
81    80  .  Unresolved: []*ast.Ident (len = 1) {
82    81  .  .  0: *(obj @ 46)
83    82  .  }
84    83  }
85

ASTを探索する

ast.Inspect関数

ast.Inspectを利用するとast.Node（*ast.Fileもこれを満たす）を深さ優先探索でひとつひとつのnodeを探索することができます。 https://golang.org/pkg/go/ast/#Inspect

1package main
2
3import (
4    "fmt"
5    "go/ast"
6    "go/parser"
7    "go/token"
8    "log"
9)
10
11const hello = `package main
12
13import "fmt"
14
15func main() {
16        fmt.Println("Hello, world")
17}`
18
19func main() {
20    fset := token.NewFileSet()
21
22    // Parse the input string, []byte, or io.Reader,
23    // recording position information in fset.
24    // ParseFile returns an *ast.File, a syntax tree.
25    f, err := parser.ParseFile(fset, "", hello, 0)
26    if err != nil {
27        log.Fatal(err) // parse error
28    }
29
30    ast.Inspect(f, func(n ast.Node) bool {
31        var s string
32        switch x := n.(type) {
33        case *ast.BasicLit:
34            s = x.Value
35        case *ast.Ident:
36            s = x.Name
37        }
38        if s != "" {
39            fmt.Printf("%s:\t%s\n", fset.Position(n.Pos()), s)
40        }
41        return true
42    })
43}
44

結果

11:9:    main
23:8:    "fmt"
35:6:    main
46:9:    fmt
56:13:   Println
66:21:   "Hello, world"
7

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（定数評価）

サンプル

1package main
2
3import (
4    "fmt"
5    "go/ast"
6    "go/importer"
7    "go/parser"
8    "go/token"
9    "go/types"
10    "log"
11)
12
13const hello = `package main
14
15import "fmt"
16
17type Hoge struct {
18    Foo string
19    Bar int
20}
21
22func main() {
23        fmt.Println("Hello, world")
24}`
25
26func main() {
27    fset := token.NewFileSet()
28
29    // Parse the input string, []byte, or io.Reader,
30    // recording position information in fset.
31    // ParseFile returns an *ast.File, a syntax tree.
32    f, err := parser.ParseFile(fset, "", hello, 0)
33    if err != nil {
34        log.Fatal(err) // parse error
35    }
36
37    // A Config controls various options of the type checker.
38    // The defaults work fine except for one setting:
39    // we must specify how to deal with imports.
40    conf := types.Config{Importer: importer.Default()}
41
42    info := &types.Info{
43        Defs: make(map[*ast.Ident]types.Object),
44        Uses: make(map[*ast.Ident]types.Object),
45    }
46
47    // Type-check the package containing only file f.
48    // Check returns a *types.Package.
49    pkg, err := conf.Check("cmd/hello", fset, []*ast.File{f}, info)
50    if err != nil {
51        log.Fatal(err) // type error
52    }
53
54    fmt.Println("=== Package ===")
55    fmt.Printf("Package  %q\n", pkg.Path())
56    fmt.Printf("Name:    %s\n", pkg.Name())
57    fmt.Printf("Imports: %s\n", pkg.Imports())
58    fmt.Printf("Scope:   %s\n", pkg.Scope())
59
60    fmt.Println("")
61
62    // info
63    fmt.Println("=== Info ===")
64    for id, obj := range info.Defs {
65        fmt.Printf("%s: %q defines %v\n",
66            fset.Position(id.Pos()), id.Name, obj)
67    }
68    for id, obj := range info.Uses {
69        fmt.Printf("%s: %q uses %v\n",
70            fset.Position(id.Pos()), id.Name, obj)
71    }
72
73    fmt.Println("")
74
75    // object
76    fmt.Println("=== Object ===")
77    scope := pkg.Scope()
78
79    for _, name := range scope.Names() {
80        obj := scope.Lookup(name)
81        fmt.Printf("%s: %+v\n", name, obj)
82    }
83}
84

実行結果

1=== Package ===
2Package  "cmd/hello"
3Name:    main
4Imports: [package fmt ("fmt")]
5Scope:   package "cmd/hello" scope 0xc0000b94a0 {
6.  type cmd/hello.Hoge struct{Foo string; Bar int}
7.  func cmd/hello.main()
8}
9
10
11=== Info ===
126:2: "Foo" defines field Foo string
137:2: "Bar" defines field Bar int
141:9: "main" defines <nil>
155:6: "Hoge" defines type cmd/hello.Hoge struct{Foo string; Bar int}
1610:6: "main" defines func cmd/hello.main()
176:6: "string" uses type string
187:6: "int" uses type int
1911:9: "fmt" uses package fmt
2011:13: "Println" uses func fmt.Println(a ...interface{}) (n int, err error)
21
22=== Object ===
23Hoge: type cmd/hello.Hoge struct{Foo string; Bar int}
24main: func cmd/hello.main()
25

主な概念

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

1    info := &types.Info{
2        Defs: make(map[*ast.Ident]types.Object),
3        Uses: make(map[*ast.Ident]types.Object),
4    }
5
6    // Type-check the package containing only file f.
7    // Check returns a *types.Package.
8    pkg, err := conf.Check("cmd/hello", fset, []*ast.File{f}, info)
9

で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