Goの静的解析ライブラリでDSMを求めてみる

あくあたん工房 Advent Calendar10日目の記事です．taxioが頑張ります．

この記事ではGoの静的解析ライブラリを使ってみながら，簡単なDSMを求める方法を紹介していきます．

Goで静的解析

Goは素晴らしい言語なので，標準ライブラリで静的解析が十分できたりします．¹

最近どうやらanalysisというライブラリがgo/toolsに追加されたらしいですが，まだちゃんと情報を追えてません(すいません)．Go Advent Calendarの方で強い人が書いてくれるでしょう．

今回はASTに関する型や関数を提供しているgo/ast，構文解析の機能を提供しているgo/parserを使っていきます．

ASTの生成に使うgo/parserにはいくつかの入力段階が存在し，

式ならparser.ParseFile()
ファイルならparser.ParseFile()
ディレクトリならparser.ParseDir()

などを使います．

また，ファイルとディレクトリのパースにはパースの対象をどこまでするかなど，いくつか設定を変えられるparser.Modeを渡すことができます．²

parser/Parse*で作成したASTを走査したい場合は，自分でゴリゴリ再帰関数を書いていくのもいいですが，ast.Inspect(),ast.Walk()という深さ優先探索をしてくれる便利な関数があるのでそれを使いましょう．

ただ，これらはin-orderでの深さ優先探索となっています．post-orderやpre-orderでの深さ優先探索をしたい場合はgolang.org/x/tools/go/ast/astutilにあるApplyを使うといいかもしれないです．³

DSMを求めてみる

ここからは実際に簡単なDSMを求める静的解析タスクを行っていきます．

Dependenct Structure Matrix(DSM)とは，システムのモデルの品質を確認する手法の一つです．⁴

各モジュールの依存を有向グラフと見て，隣接行列で表現します．

本来は製品開発プロセスを最適化するためのメトリクスなのですが，ソースコード解析にも応用できるという論文が出ているので，それを参考にGoで簡単に算出していこうと思います．⁵

例えば以下のようなすごく簡単なレイヤードっぽいコードがあったとします．

package main

import (
    "fmt"
)

func presen() {
    app()
}

func app() {
    domain()
}

func domain() {
func infra() {
    fmt.Println("Aquatan!")
}

このコードの関数レベルの依存を解析してみます．

解析用のソースコードはこんな感じです．

package main

import (
    "fmt"
    "go/ast"
    "go/parser"
    "go/token"
    "log"

    "gonum.org/v1/gonum/mat"
)

type Func struct {
    Name  string
    Calls []string
}

func main() {
    fset := token.NewFileSet()

    f, err := parser.ParseFile(fset, "layered.go", nil, 0)
    if err != nil {
        log.Fatal(err)
    }

    funcs := []Func{}
    ast.Inspect(f, func(n ast.Node) bool {
        funcDecl, ok := n.(*ast.FuncDecl)
        if !ok {
            return true
        }

        funcs = append(funcs, Func{
            Name:  funcDecl.Name.Name,
            Calls: parseChild(funcDecl),
        })

        return true
    })

    m := toMat(funcs)
    fa := mat.Formatted(m, mat.Prefix(""), mat.Squeeze())
    fmt.Printf("%v\n", fa)
}

func parseChild(parent ast.Node) []string {
    calls := []string{}

    ast.Inspect(parent, func(n ast.Node) bool {
        callExpr, ok := n.(*ast.CallExpr)
        if !ok {
            return true
        }

        ident, ok := callExpr.Fun.(*ast.Ident)
        if !ok {
            return true
        }

        name := ident.Name
        calls = append(calls, name)

        return true
    })

    return calls
}

func toMat(funcs []Func) mat.Matrix {
    funcList := map[string]int{}
    for i, v := range funcs {
        funcList[v.Name] = i
    }

    ad := mat.NewDense(len(funcs), len(funcs), nil)
    for i, v := range funcs {
        for _, c := range v.Calls {
            ad.Set(i, funcList[c], 1)
        }
    }

    return ad.T()
}

出力はこうなります．

go run main.go

⎡0  0  0  0⎤
⎢1  0  0  0⎥
⎢0  1  0  0⎥
⎣0  0  1  0⎦

参照がある場合は1，無い場合は0としています．各層が一つ下の層しか参照していないというのが見てとれますね．

処理の流れとしては，

parser.ParseFile()によって出力されたASTの根(*ast.File)を走査
関数の宣言(*ast.FuncDecl)が見つかったらその下に続く部分木を走査
関数またはメソッド呼び出し(*ast.CallExpr)を見つけたら記録していく
全ての関数宣言に対して処理を終えるまで2,3を繰り返す
gonumで隣接行列を作成

という感じになっています．簡単にファイル内の依存関係を表した隣接行列が生成できましたね！！

今回はファイル内の関数の依存関係を出しましたが，プロジェクト単位で算出させるようなツールにすれば品質チェックのメトリクスに使えそうです！

analysisを使ってもう少しいい感じに静的解析したい...(勉強中)

おわりに

Goの標準パッケージを使って簡単な静的解析を行っていきました．新作スマブラの誘惑に負けずにちゃんと記事を公開できてよかったです．

あくあたん工房およびそふらぼでは，Goを書きたい人・静的解析をしたい人を常に(僕が個人的に)大募集しています！在校生の人はぜひ！話だけでも！

参考文献

tenntennさんやmotemenさんの資料を大変参考にさせていただきました．