golang深入源代码系列之二：反向调用关系的生成

这是系列博文的第二篇，第一篇在此：golang深入源代码之一：AST的遍历。

怎么形成一个项目内部的函数调用关系

ast.FuncDecl

一个例子

如下为测试项目的文件结构：

-- /exmaple/test3.go

-- /exmaple/test4.go

-- /example/inner/itest1.go

中间存在着跨文件调用和跨package调用，以及调用类的函数。

/exmaple/test3.go如下：

package main

import (
    "context"
    "fmt"

    "github.com/baixiaoustc/go_code_analysis/example/inner"
)

func main() {
    fmt.Println("start")

    Test3()
    test3a()
    test3c()

    go receiveFromKafka()
    select {}
}

func Test3() {
    fmt.Println("test3")
    test3b()
}

type XYZ struct {
    Name string
}

func (xyz XYZ) print() {
    fmt.Println(xyz.Name)
    context.WithCancel(nil)
}

func test3a() {
    xyz := XYZ{"hello"}
    xyz.print()
}

func test3b() {
    test3b()
    inner.Itest1()
}

func test3c() {
    go func() {
        fmt.Println("go")
    }()
    test4a("world")
}

/exmaple/test4.go如下：

package main

import (
    "context"
    "fmt"
)

func test4a(a string) {
    fmt.Println(a)
    context.WithCancel(nil)
}

func test4b(a string) {
    fmt.Println(a)
    context.WithCancel(nil)
}

func receiveFromKafka() {
    test4a("kafka")
    test4b("kafka")
}

/example/inner/itest1.go如下：

package inner

import "context"

func Itest1() {
    context.WithCancel(nil)
}

test4a

使用golang提供的静态编译工具链

我们依赖了如下三个golang工具链：

• "golang.org/x/tools/go/loader"
• "golang.org/x/tools/go/pointer"
• "golang.org/x/tools/go/ssa"

go/loader

Package loader loads a complete Go program from source code, parsing and type-checking the initial packages plus their transitive closure of dependencies. The ASTs and the derived facts are retained for later use.

这个包的官方定义如上，大意是指从源代码加载整个项目，解析代码并作类型校验，分析package之间的依赖关系，返回ASTs和衍生的关系。

go/ssa

Package ssa defines a representation of the elements of Go programs (packages, types, functions, variables and constants) using a static single-assignment (SSA) form intermediate representation (IR) for the bodies of functions.

SSA(Static Single Assignment，静态单赋值），是源代码和机器码中间的表现形式。从AST转换到SSA之后，编译器会进行一系列的优化。这些优化被应用于代码的特定阶段使得处理器能够更简单和快速地执行。

go/pointer

Package pointer implements Andersen's analysis, an inclusion-based pointer analysis algorithm first described in (Andersen, 1994).

指针分析是一类特殊的数据流问题，它是其它静态程序分析的基础。算法最终建立各节点间的指向关系，具体可以参考文章Anderson's pointer analysis。

在此没有进行理论上的研究，单单尝试使用golang提供的工具链做源代码的语义分析：

var Analysis *analysis

type analysis struct {
    prog   *ssa.Program
    conf   loader.Config
    pkgs   []*ssa.Package
    mains  []*ssa.Package
    result *pointer.Result
}

func doAnalysis(buildCtx *build.Context, tests bool, args []string) {
    t0 := time.Now()
    conf := loader.Config{Build: buildCtx}
    _, err := conf.FromArgs(args, tests)
    if err != nil {
        log.Printf("invalid args:", err)
        return
    }
    load, err := conf.Load()
    if err != nil {
        log.Printf("failed conf load:", err)
        return
    }
    log.Printf("loading.. %d imported (%d created) took: %v",
        len(load.Imported), len(load.Created), time.Since(t0))

    t0 = time.Now()

    prog := ssautil.CreateProgram(load, 0)
    prog.Build()
    pkgs := prog.AllPackages()

    var mains []*ssa.Package
    if tests {
        for _, pkg := range pkgs {
            if main := prog.CreateTestMainPackage(pkg); main != nil {
                mains = append(mains, main)
            }
        }
        if mains == nil {
            log.Fatalln("no tests")
        }
    } else {
        mains = append(mains, ssautil.MainPackages(pkgs)...)
        if len(mains) == 0 {
            log.Printf("no main packages")
        }
    }
    log.Printf("building.. %d packages (%d main) took: %v",
        len(pkgs), len(mains), time.Since(t0))

    t0 = time.Now()
    ptrcfg := &pointer.Config{
        Mains:          mains,
        BuildCallGraph: true,
    }
    result, err := pointer.Analyze(ptrcfg)
    if err != nil {
        log.Fatalln("analyze failed:", err)
    }
    log.Printf("analysis took: %v", time.Since(t0))

    Analysis = &analysis{
        prog:   prog,
        conf:   conf,
        pkgs:   pkgs,
        mains:  mains,
        result: result,
    }
}

resultpointer.Resultcallgraph.Graphcallgraph.GraphVisitEdges

需要注意三个坑：

$

我们定义了如下结构表示函数之间的两两调用关系：

//函数定义
type FuncDesc struct {
    File    string //文件路径
    Package string //package名
    Name    string //函数名，格式为Package.Func
}

//描述一个函数调用N个函数的一对多关系
type CallerRelation struct {
    Caller  FuncDesc
    Callees []FuncDesc
}

如上例子的最终结果为：

2019/01/17 22:28:27 loading.. 1 imported (0 created) took: 1.335481764s
2019/01/17 22:28:28 building.. 24 packages (1 main) took: 250.771602ms
2019/01/17 22:28:28 analysis took: 301.707762ms
2019/01/17 22:28:28 0 limit prefixes: []
2019/01/17 22:28:28 0 ignore prefixes: []
2019/01/17 22:28:28 0 include prefixes: []
2019/01/17 22:28:28 no std packages: true
2019/01/17 22:28:29 call node: n11:github.com/baixiaoustc/go_code_analysis/example.receiveFromKafka -> n719:github.com/baixiaoustc/go_code_analysis/example.test4a
2019/01/17 22:28:29 call node: n11:github.com/baixiaoustc/go_code_analysis/example.receiveFromKafka -> n720:github.com/baixiaoustc/go_code_analysis/example.test4b
2019/01/17 22:28:30 call node: n9:github.com/baixiaoustc/go_code_analysis/example.test3a -> n81:(github.com/baixiaoustc/go_code_analysis/example.XYZ).print
2019/01/17 22:28:31 call node: n717:github.com/baixiaoustc/go_code_analysis/example.test3b -> n717:github.com/baixiaoustc/go_code_analysis/example.test3b
2019/01/17 22:28:31 call node: n717:github.com/baixiaoustc/go_code_analysis/example.test3b -> n797:github.com/baixiaoustc/go_code_analysis/example/inner.Itest1
2019/01/17 22:28:31 call node: n8:github.com/baixiaoustc/go_code_analysis/example.Test3 -> n717:github.com/baixiaoustc/go_code_analysis/example.test3b
2019/01/17 22:28:31 call node: n6:github.com/baixiaoustc/go_code_analysis/example.main -> n8:github.com/baixiaoustc/go_code_analysis/example.Test3
2019/01/17 22:28:31 call node: n6:github.com/baixiaoustc/go_code_analysis/example.main -> n9:github.com/baixiaoustc/go_code_analysis/example.test3a
2019/01/17 22:28:31 call node: n10:github.com/baixiaoustc/go_code_analysis/example.test3c -> n718:github.com/baixiaoustc/go_code_analysis/example.test3c$1
2019/01/17 22:28:31 call node: n10:github.com/baixiaoustc/go_code_analysis/example.test3c -> n719:github.com/baixiaoustc/go_code_analysis/example.test4a
2019/01/17 22:28:31 call node: n6:github.com/baixiaoustc/go_code_analysis/example.main -> n10:github.com/baixiaoustc/go_code_analysis/example.test3c
2019/01/17 22:28:31 call node: n6:github.com/baixiaoustc/go_code_analysis/example.main -> n11:github.com/baixiaoustc/go_code_analysis/example.receiveFromKafka
2019/01/17 22:28:31 6/1991 edges

2019/01/17 22:28:31 正向调用关系:example.Test3 {Caller:{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:Test3} Callees:[{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:test3b}]}

2019/01/17 22:28:31 正向调用关系:example.main {Caller:{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:main} Callees:[{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:Test3} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:test3a} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:test3c} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4.go Package:main Name:receiveFromKafka}]}

2019/01/17 22:28:31 正向调用关系:example.test3c {Caller:{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:test3c} Callees:[{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4.go Package:main Name:test4a}]}

2019/01/17 22:28:31 正向调用关系:example.receiveFromKafka {Caller:{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4.go Package:main Name:receiveFromKafka} Callees:[{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4.go Package:main Name:test4a} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4.go Package:main Name:test4b}]}

2019/01/17 22:28:31 正向调用关系:example.test3a {Caller:{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:test3a} Callees:[{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:XYZ@print}]}

2019/01/17 22:28:31 正向调用关系:example.test3b {Caller:{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:test3b} Callees:[{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/inner/itest1.go Package:inner Name:Itest1}]}

test4a

形成反向调用关系

test4a

实际上可以将其转为树形结构，如图：

test4a

构造多叉树

用如下结构表示多叉树的节点：

type MWTNode struct {
    Key      string
    Value    FuncDesc
    N        int
    Children []*MWTNode
}

FuncDesc.NamecallMap

func BuildFromCallMap(head *MWTNode, callMap map[string]CallerRelation) {
    nodeMap := make(map[string]struct{})
    nodeList := make([]*MWTNode, 1)
    nodeList[0] = head

    for {
        if len(nodeList) == 0 {
            break
        }

        tmp := nodeList[0]
        log.Printf("tmp %+v", tmp)
        for callerName, callRelation := range callMap {
            for _, callee := range callRelation.Callees {
                if tmp.Key == fmt.Sprintf("%s.%s", callee.Package, callee.Name) {
                    log.Printf("found caller:%s -> callee:%s", callerName, callee)

                    key := fmt.Sprintf("%s.%s", callRelation.Caller.Package, callRelation.Caller.Name)
                    if _, ok := nodeMap[key]; !ok {
                        newNode := &MWTNode{
                            Key:      key,
                            Value:    FuncDesc{callRelation.Caller.File, callRelation.Caller.Package, callRelation.Caller.Name},
                            Children: make([]*MWTNode, 0),
                        }
                        tmp.N++
                        tmp.Children = append(tmp.Children, newNode)
                        nodeList = append(nodeList, newNode)
                    } else {
                        nodeMap[key] = struct{}{}
                    }
                }
            }
        }
        nodeList = nodeList[1:]

        //log.Printf("head %+v", head)
        log.Printf("nodeList len:%d", len(nodeList))
    }
}

形成反向调用链

再定义一个结构用于描述反向调用链：

//描述关键函数的一条反向调用关系
type CalledRelation struct {
    Callees []FuncDesc
    CanFix  bool //该调用关系能反向找到gin.Context即可以自动修复
}

再利用深度优先比例该树，期望得到如下结论：

• test4a <- test3c <- main
• test4a <- receiveFromKafka <- main

func depthTraversal(head *MWTNode, s string, re CalledRelation, list *[]CalledRelation) {
    s = fmt.Sprintf("%s<-%s", s, head.Key)
    re.Callees = append(re.Callees, head.Value)
    //log.Printf("%+v: %s %+v", head, s, re.Callees)

    if head.N == 0 {
        log.Printf("找到反向调用链:%s", s)
        log.Printf("re.Callees:%+v", re.Callees)
        *list = append(*list, re)
        s = ""
        re.Callees = make([]FuncDesc, 0)
    } else {
        for _, node := range head.Children {
            depthTraversal(node, s, re, list)
        }
    }
}

TestAnalysisReverceCallGraphy

2019/01/20 21:53:32 tmp &{Key:main.test4a Value:{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4a.go Package:main Name:test4a} N:0 Level:0 Children:[]}

2019/01/20 21:53:32 found caller:example.receiveFromKafka -> callee:{/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4.go main test4a}

2019/01/20 21:53:32 found caller:example.test3c -> callee:{/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4.go main test4a}

2019/01/20 21:53:32 nodeList len:2

2019/01/20 21:53:32 tmp &{Key:main.receiveFromKafka Value:{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4.go Package:main Name:receiveFromKafka} N:0 Level:0 Children:[]}

2019/01/20 21:53:32 found caller:example.main -> callee:{/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4.go main receiveFromKafka}

2019/01/20 21:53:32 nodeList len:2

2019/01/20 21:53:32 tmp &{Key:main.test3c Value:{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:test3c} N:0 Level:0 Children:[]}

2019/01/20 21:53:32 found caller:example.main -> callee:{/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go main test3c}

2019/01/20 21:53:32 nodeList len:2

2019/01/20 21:53:32 tmp &{Key:main.main Value:{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:main} N:0 Level:0 Children:[]}

2019/01/20 21:53:32 nodeList len:1

2019/01/20 21:53:32 tmp &{Key:main.main Value:{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:main} N:0 Level:0 Children:[]}

2019/01/20 21:53:32 nodeList len:0

2019/01/20 21:53:32 找到反向调用链:<-main.test4a<-main.receiveFromKafka<-main.main

2019/01/20 21:53:32 re.Callees:[{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4a.go Package:main Name:test4a} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4.go Package:main Name:receiveFromKafka} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:main}]

2019/01/20 21:53:32 找到反向调用链:<-main.test4a<-main.test3c<-main.main

2019/01/20 21:53:32 re.Callees:[{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4a.go Package:main Name:test4a} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:test3c} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:main}]

2019/01/20 21:53:32 list0: {Callees:[{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4a.go Package:main Name:test4a} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4.go Package:main Name:receiveFromKafka} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:main}] CanFix:false}

2019/01/20 21:53:32 list1: {Callees:[{File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test4a.go Package:main Name:test4a} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:test3c} {File:/Users/baixiao/Go/src/github.com/baixiaoustc/go_code_analysis/example/test3.go Package:main Name:main}] CanFix:false}

原文载于