| // Copyright 2014 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| // Package static computes the call graph of a Go program containing |
| // only static call edges. |
| package static |
| |
| import ( |
| "go/types" |
| |
| "golang.org/x/tools/go/callgraph" |
| "golang.org/x/tools/go/ssa" |
| ) |
| |
| // CallGraph computes the static call graph of the specified program. |
| // |
| // The resulting graph includes: |
| // - all package-level functions; |
| // - all methods of package-level non-parameterized non-interface types; |
| // - pointer wrappers (*C).F for source-level methods C.F; |
| // - and all functions reachable from them following only static calls. |
| // |
| // It does not consider exportedness, nor treat main packages specially. |
| func CallGraph(prog *ssa.Program) *callgraph.Graph { |
| cg := callgraph.New(nil) |
| |
| // Recursively follow all static calls. |
| seen := make(map[int]bool) // node IDs already seen |
| var visit func(fnode *callgraph.Node) |
| visit = func(fnode *callgraph.Node) { |
| if !seen[fnode.ID] { |
| seen[fnode.ID] = true |
| |
| for _, b := range fnode.Func.Blocks { |
| for _, instr := range b.Instrs { |
| if site, ok := instr.(ssa.CallInstruction); ok { |
| if g := site.Common().StaticCallee(); g != nil { |
| gnode := cg.CreateNode(g) |
| callgraph.AddEdge(fnode, site, gnode) |
| visit(gnode) |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| // If we were ever to redesign this function, we should allow |
| // the caller to provide the set of root functions and just |
| // perform the reachability step. This would allow them to |
| // work forwards from main entry points: |
| // |
| // rootNames := []string{"init", "main"} |
| // for _, main := range ssautil.MainPackages(prog.AllPackages()) { |
| // for _, rootName := range rootNames { |
| // visit(cg.CreateNode(main.Func(rootName))) |
| // } |
| // } |
| // |
| // or to control whether to include non-exported |
| // functions/methods, wrapper methods, and so on. |
| // Unfortunately that's not consistent with its historical |
| // behavior and existing tests. |
| // |
| // The logic below is a slight simplification and |
| // rationalization of ssautil.AllFunctions. (Having to include |
| // (*T).F wrapper methods is unfortunate--they are not source |
| // functions, and if they're reachable, they'll be in the |
| // graph--but the existing tests will break without it.) |
| |
| methodsOf := func(T types.Type) { |
| if !types.IsInterface(T) { |
| mset := prog.MethodSets.MethodSet(T) |
| for i := 0; i < mset.Len(); i++ { |
| visit(cg.CreateNode(prog.MethodValue(mset.At(i)))) |
| } |
| } |
| } |
| |
| // Start from package-level symbols. |
| for _, pkg := range prog.AllPackages() { |
| for _, mem := range pkg.Members { |
| switch mem := mem.(type) { |
| case *ssa.Function: |
| // package-level function |
| visit(cg.CreateNode(mem)) |
| |
| case *ssa.Type: |
| // methods of package-level non-interface non-parameterized types |
| if !types.IsInterface(mem.Type()) { |
| if named, ok := mem.Type().(*types.Named); ok && |
| named.TypeParams() == nil { |
| methodsOf(named) // T |
| methodsOf(types.NewPointer(named)) // *T |
| } |
| } |
| } |
| } |
| } |
| |
| return cg |
| } |