vta: adds the VTA call graph construction
This CL uses the results of propagating types and functions over the VTA
graph to create a VTA-based call graph.
Change-Id: I1481641dc6682f8fb874823de3073bf81187f6b7
Reviewed-on: https://go-review.googlesource.com/c/tools/+/323051
Run-TryBot: Zvonimir Pavlinovic <zpavlinovic@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Trust: Zvonimir Pavlinovic <zpavlinovic@google.com>
Reviewed-by: Roland Shoemaker <roland@golang.org>
diff --git a/go/callgraph/vta/graph_test.go b/go/callgraph/vta/graph_test.go
index 08866c8..61bb05a 100644
--- a/go/callgraph/vta/graph_test.go
+++ b/go/callgraph/vta/graph_test.go
@@ -6,77 +6,16 @@
import (
"fmt"
- "go/ast"
- "go/parser"
"go/types"
- "io/ioutil"
"reflect"
"sort"
"strings"
"testing"
"golang.org/x/tools/go/callgraph/cha"
- "golang.org/x/tools/go/ssa"
"golang.org/x/tools/go/ssa/ssautil"
-
- "golang.org/x/tools/go/loader"
)
-// want extracts the contents of the first comment
-// section starting with "WANT:\n". The returned
-// content is split into lines without // prefix.
-func want(f *ast.File) []string {
- for _, c := range f.Comments {
- text := strings.TrimSpace(c.Text())
- if t := strings.TrimPrefix(text, "WANT:\n"); t != text {
- return strings.Split(t, "\n")
- }
- }
- return nil
-}
-
-// testProg returns an ssa representation of a program at
-// `path`, assumed to define package "testdata," and the
-// test want result as list of strings.
-func testProg(path string) (*ssa.Program, []string, error) {
- content, err := ioutil.ReadFile(path)
- if err != nil {
- return nil, nil, err
- }
-
- conf := loader.Config{
- ParserMode: parser.ParseComments,
- }
-
- f, err := conf.ParseFile(path, content)
- if err != nil {
- return nil, nil, err
- }
-
- conf.CreateFromFiles("testdata", f)
- iprog, err := conf.Load()
- if err != nil {
- return nil, nil, err
- }
-
- prog := ssautil.CreateProgram(iprog, 0)
- // Set debug mode to exercise DebugRef instructions.
- prog.Package(iprog.Created[0].Pkg).SetDebugMode(true)
- prog.Build()
- return prog, want(f), nil
-}
-
-func firstRegInstr(f *ssa.Function) ssa.Value {
- for _, b := range f.Blocks {
- for _, i := range b.Instrs {
- if v, ok := i.(ssa.Value); ok {
- return v
- }
- }
- }
- return nil
-}
-
func TestNodeInterface(t *testing.T) {
// Since ssa package does not allow explicit creation of ssa
// values, we use the values from the program testdata/simple.go:
diff --git a/go/callgraph/vta/helpers_test.go b/go/callgraph/vta/helpers_test.go
new file mode 100644
index 0000000..4451f57
--- /dev/null
+++ b/go/callgraph/vta/helpers_test.go
@@ -0,0 +1,83 @@
+// Copyright 2021 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 vta
+
+import (
+ "go/ast"
+ "go/parser"
+ "io/ioutil"
+ "strings"
+
+ "golang.org/x/tools/go/ssa/ssautil"
+
+ "golang.org/x/tools/go/loader"
+ "golang.org/x/tools/go/ssa"
+)
+
+// want extracts the contents of the first comment
+// section starting with "WANT:\n". The returned
+// content is split into lines without // prefix.
+func want(f *ast.File) []string {
+ for _, c := range f.Comments {
+ text := strings.TrimSpace(c.Text())
+ if t := strings.TrimPrefix(text, "WANT:\n"); t != text {
+ return strings.Split(t, "\n")
+ }
+ }
+ return nil
+}
+
+// testProg returns an ssa representation of a program at
+// `path`, assumed to define package "testdata," and the
+// test want result as list of strings.
+func testProg(path string) (*ssa.Program, []string, error) {
+ content, err := ioutil.ReadFile(path)
+ if err != nil {
+ return nil, nil, err
+ }
+
+ conf := loader.Config{
+ ParserMode: parser.ParseComments,
+ }
+
+ f, err := conf.ParseFile(path, content)
+ if err != nil {
+ return nil, nil, err
+ }
+
+ conf.CreateFromFiles("testdata", f)
+ iprog, err := conf.Load()
+ if err != nil {
+ return nil, nil, err
+ }
+
+ prog := ssautil.CreateProgram(iprog, 0)
+ // Set debug mode to exercise DebugRef instructions.
+ prog.Package(iprog.Created[0].Pkg).SetDebugMode(true)
+ prog.Build()
+ return prog, want(f), nil
+}
+
+func firstRegInstr(f *ssa.Function) ssa.Value {
+ for _, b := range f.Blocks {
+ for _, i := range b.Instrs {
+ if v, ok := i.(ssa.Value); ok {
+ return v
+ }
+ }
+ }
+ return nil
+}
+
+// funcName returns a name of the function `f`
+// prefixed with the name of the receiver type.
+func funcName(f *ssa.Function) string {
+ recv := f.Signature.Recv()
+ if recv == nil {
+ return f.Name()
+ }
+ tp := recv.Type().String()
+ return tp[strings.LastIndex(tp, ".")+1:] + "." + f.Name()
+}
diff --git a/go/callgraph/vta/testdata/callgraph_collections.go b/go/callgraph/vta/testdata/callgraph_collections.go
new file mode 100644
index 0000000..bc418e3
--- /dev/null
+++ b/go/callgraph/vta/testdata/callgraph_collections.go
@@ -0,0 +1,67 @@
+// Copyright 2021 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.
+
+// go:build ignore
+
+package testdata
+
+type I interface {
+ Foo()
+}
+
+type A struct{}
+
+func (a A) Foo() {}
+
+type B struct{}
+
+func (b B) Foo() {}
+
+func Do(a A, b B) map[I]I {
+ m := make(map[I]I)
+ m[a] = B{}
+ m[b] = b
+ return m
+}
+
+func Baz(a A, b B) {
+ var x []I
+ for k, v := range Do(a, b) {
+ k.Foo()
+ v.Foo()
+
+ x = append(x, k)
+ }
+
+ x[len(x)-1].Foo()
+}
+
+// Relevant SSA:
+// func Baz(a A, b B):
+// ...
+// t4 = Do(t2, t3)
+// t5 = range t4
+// jump 1
+// 1:
+// t6 = phi [0: nil:[]I, 2: t16] #x
+// t7 = next t5
+// t8 = extract t7 #0
+// if t8 goto 2 else 3
+// 2:
+// t9 = extract t7 #1
+// t10 = extract t7 #2
+// t11 = invoke t9.Foo()
+// t12 = invoke t10.Foo()
+// ...
+// jump 1
+// 3:
+// t17 = len(t6)
+// t18 = t17 - 1:int
+// t19 = &t6[t18]
+// t20 = *t19
+// t21 = invoke t20.Foo()
+// return
+
+// WANT:
+// Baz: Do(t2, t3) -> Do; invoke t10.Foo() -> B.Foo; invoke t20.Foo() -> A.Foo, B.Foo; invoke t9.Foo() -> A.Foo, B.Foo
diff --git a/go/callgraph/vta/testdata/callgraph_ho.go b/go/callgraph/vta/testdata/callgraph_ho.go
new file mode 100644
index 0000000..0e5fa0d
--- /dev/null
+++ b/go/callgraph/vta/testdata/callgraph_ho.go
@@ -0,0 +1,45 @@
+// Copyright 2021 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.
+
+// go:build ignore
+
+package testdata
+
+func Foo() {}
+
+func Do(b bool) func() {
+ if b {
+ return Foo
+ }
+ return func() {}
+}
+
+func Finish(h func()) {
+ h()
+}
+
+func Baz(b bool) {
+ Finish(Do(b))
+}
+
+// Relevant SSA:
+// func Baz(b bool):
+// t0 = Do(b)
+// t1 = Finish(t0)
+// return
+
+// func Do(b bool) func():
+// if b goto 1 else 2
+// 1:
+// return Foo
+// 2:
+// return Do$1
+
+// func Finish(h func()):
+// t0 = h()
+// return
+
+// WANT:
+// Baz: Do(b) -> Do; Finish(t0) -> Finish
+// Finish: h() -> Do$1, Foo
diff --git a/go/callgraph/vta/testdata/callgraph_interfaces.go b/go/callgraph/vta/testdata/callgraph_interfaces.go
new file mode 100644
index 0000000..123468c
--- /dev/null
+++ b/go/callgraph/vta/testdata/callgraph_interfaces.go
@@ -0,0 +1,61 @@
+// Copyright 2021 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.
+
+// go:build ignore
+
+package testdata
+
+type I interface {
+ Foo()
+}
+
+type A struct{}
+
+func (a A) Foo() {}
+
+type B struct{}
+
+func (b B) Foo() {}
+
+type C struct{}
+
+func (c C) Foo() {}
+
+func NewB() B {
+ return B{}
+}
+
+func Do(b bool) I {
+ if b {
+ return A{}
+ }
+
+ c := C{}
+ c.Foo()
+
+ return NewB()
+}
+
+func Baz(b bool) {
+ Do(b).Foo()
+}
+
+// Relevant SSA:
+// func Baz(b bool):
+// t0 = Do(b)
+// t1 = invoke t0.Foo()
+// return
+
+// func Do(b bool) I:
+// ...
+// t3 = local C (c)
+// t4 = *t3
+// t5 = (C).Foo(t4)
+// t6 = NewB()
+// t7 = make I <- B (t6)
+// return t7
+
+// WANT:
+// Baz: Do(b) -> Do; invoke t0.Foo() -> A.Foo, B.Foo
+// Do: (C).Foo(t4) -> C.Foo; NewB() -> NewB
diff --git a/go/callgraph/vta/testdata/callgraph_nested_ptr.go b/go/callgraph/vta/testdata/callgraph_nested_ptr.go
new file mode 100644
index 0000000..a6afc3b
--- /dev/null
+++ b/go/callgraph/vta/testdata/callgraph_nested_ptr.go
@@ -0,0 +1,59 @@
+// Copyright 2021 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.
+
+// go:build ignore
+
+package testdata
+
+type I interface {
+ Foo()
+}
+
+type A struct{}
+
+func (a A) Foo() {}
+
+type B struct{}
+
+func (b B) Foo() {}
+
+func Do(i **I) {
+ **i = A{}
+}
+
+func Bar(i **I) {
+ **i = B{}
+}
+
+func Baz(i **I) {
+ Do(i)
+ (**i).Foo()
+}
+
+// Relevant SSA:
+// func Baz(i **I):
+// t0 = Do(i)
+// t1 = *i
+// t2 = *t1
+// t3 = invoke t2.Foo()
+// return
+
+// func Bar(i **I):
+// t0 = *i
+// t1 = local B (complit)
+// t2 = *t1
+// t3 = make I <- B (t2)
+// *t0 = t3
+// return
+
+// func Do(i **I):
+// t0 = *i
+// t1 = local A (complit)
+// t2 = *t1
+// t3 = make I <- A (t2)
+// *t0 = t3
+// return
+
+// WANT:
+// Baz: Do(i) -> Do; invoke t2.Foo() -> A.Foo, B.Foo
diff --git a/go/callgraph/vta/testdata/callgraph_pointers.go b/go/callgraph/vta/testdata/callgraph_pointers.go
new file mode 100644
index 0000000..e07f969
--- /dev/null
+++ b/go/callgraph/vta/testdata/callgraph_pointers.go
@@ -0,0 +1,71 @@
+// Copyright 2021 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.
+
+// go:build ignore
+
+package testdata
+
+type I interface {
+ Foo()
+}
+
+type A struct {
+ f *I
+}
+
+func (a A) Foo() {}
+
+type B struct{}
+
+func (b B) Foo() {}
+
+func Do(a A, i I, c bool) *I {
+ if c {
+ *a.f = a
+ } else {
+ a.f = &i
+ }
+ (*a.f).Foo()
+ return &i
+}
+
+func Baz(a A, b B, c bool) {
+ x := Do(a, b, c)
+ (*x).Foo()
+}
+
+// Relevant SSA:
+// func Baz(a A, b B, c bool):
+// t0 = local A (a)
+// ...
+// t5 = Do(t2, t4, c)
+// t6 = *t5
+// t7 = invoke t6.Foo()
+// return
+
+// func Do(a A, i I, c bool) *I:
+// t0 = local A (a)
+// *t0 = a
+// ...
+// if c goto 1 else 3
+// 1:
+// t2 = &t0.f [#0]
+// ...
+// jump 2
+// 2:
+// t6 = &t0.f [#0]
+// ...
+// t9 = invoke t8.Foo()
+// return t1
+// 3:
+// t10 = &t0.f [#0] alias between A.f and t10
+// *t10 = t1 alias between t10 and t1
+// jump 2
+
+// The command a.f = &i introduces aliasing that results in
+// A and B reaching both *A.f and return value of Do(a, b, c).
+
+// WANT:
+// Baz: Do(t2, t4, c) -> Do; invoke t6.Foo() -> A.Foo, B.Foo
+// Do: invoke t8.Foo() -> A.Foo, B.Foo
diff --git a/go/callgraph/vta/testdata/callgraph_static.go b/go/callgraph/vta/testdata/callgraph_static.go
new file mode 100644
index 0000000..1ed904f
--- /dev/null
+++ b/go/callgraph/vta/testdata/callgraph_static.go
@@ -0,0 +1,30 @@
+// Copyright 2021 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.
+
+// go:build ignore
+
+package testdata
+
+type A struct{}
+
+func (a A) foo() {}
+
+func Bar() {}
+
+func Baz(a A) {
+ a.foo()
+ Bar()
+ Baz(A{})
+}
+
+// Relevant SSA:
+// func Baz(a A):
+// ...
+// t2 = (A).foo(t1)
+// t3 = Bar()
+// ...
+// t6 = Baz(t5)
+
+// WANT:
+// Baz: (A).foo(t1) -> A.foo; Bar() -> Bar; Baz(t5) -> Baz
diff --git a/go/callgraph/vta/utils.go b/go/callgraph/vta/utils.go
index 3142893..69361ab 100644
--- a/go/callgraph/vta/utils.go
+++ b/go/callgraph/vta/utils.go
@@ -136,3 +136,32 @@
return false
}
}
+
+// calls returns the set of call instructions in `f`.
+func calls(f *ssa.Function) []ssa.CallInstruction {
+ var calls []ssa.CallInstruction
+ for _, bl := range f.Blocks {
+ for _, instr := range bl.Instrs {
+ if c, ok := instr.(ssa.CallInstruction); ok {
+ calls = append(calls, c)
+ }
+ }
+ }
+ return calls
+}
+
+// intersect produces an intersection of functions in `fs1` and `fs2`.
+func intersect(fs1, fs2 []*ssa.Function) []*ssa.Function {
+ m := make(map[*ssa.Function]bool)
+ for _, f := range fs1 {
+ m[f] = true
+ }
+
+ var res []*ssa.Function
+ for _, f := range fs2 {
+ if m[f] {
+ res = append(res, f)
+ }
+ }
+ return res
+}
diff --git a/go/callgraph/vta/vta.go b/go/callgraph/vta/vta.go
index 2769df4..6a0e55d 100644
--- a/go/callgraph/vta/vta.go
+++ b/go/callgraph/vta/vta.go
@@ -54,4 +54,120 @@
package vta
-// TODO(zpavlinovic): add exported VTA library functions.
+import (
+ "go/types"
+
+ "golang.org/x/tools/go/callgraph"
+ "golang.org/x/tools/go/ssa"
+)
+
+// CallGraph uses the VTA algorithm to compute call graph for all functions
+// f such that f:true is in `funcs`. VTA refines the results of 'initial'
+// callgraph and uses it to establish interprocedural data flow. VTA is
+// sound if 'initial` is sound modulo reflection and unsage. The resulting
+// callgraph does not have a root node.
+func CallGraph(funcs map[*ssa.Function]bool, initial *callgraph.Graph) *callgraph.Graph {
+ vtaG, canon := typePropGraph(funcs, initial)
+ types := propagate(vtaG, canon)
+
+ c := &constructor{types: types, initial: initial, cache: make(methodCache)}
+ return c.construct(funcs)
+}
+
+// constructor type linearly traverses the input program
+// and constructs a callgraph based on the results of the
+// VTA type propagation phase.
+type constructor struct {
+ types propTypeMap
+ cache methodCache
+ initial *callgraph.Graph
+}
+
+func (c *constructor) construct(funcs map[*ssa.Function]bool) *callgraph.Graph {
+ cg := &callgraph.Graph{Nodes: make(map[*ssa.Function]*callgraph.Node)}
+ for f, in := range funcs {
+ if in {
+ c.constrct(cg, f)
+ }
+ }
+ return cg
+}
+
+func (c *constructor) constrct(g *callgraph.Graph, f *ssa.Function) {
+ caller := g.CreateNode(f)
+ for _, call := range calls(f) {
+ for _, c := range c.callees(call) {
+ callgraph.AddEdge(caller, call, g.CreateNode(c))
+ }
+ }
+}
+
+// callees computes the set of functions to which VTA resolves `c`. The resolved
+// functions are intersected with functions to which `initial` resolves `c`.
+func (c *constructor) callees(call ssa.CallInstruction) []*ssa.Function {
+ cc := call.Common()
+ if cc.StaticCallee() != nil {
+ return []*ssa.Function{cc.StaticCallee()}
+ }
+
+ // Skip builtins as they are not *ssa.Function.
+ if _, ok := cc.Value.(*ssa.Builtin); ok {
+ return nil
+ }
+
+ // Cover the case of dynamic higher-order and interface calls.
+ return intersect(resolve(call, c.types, c.cache), siteCallees(call, c.initial))
+}
+
+// resolve returns a set of functions `c` resolves to based on the
+// type propagation results in `types`.
+func resolve(c ssa.CallInstruction, types propTypeMap, cache methodCache) []*ssa.Function {
+ n := local{val: c.Common().Value}
+ var funcs []*ssa.Function
+ for p := range types.propTypes(n) {
+ funcs = append(funcs, propFunc(p, c, cache)...)
+ }
+ return funcs
+}
+
+// propFunc returns the functions modeled with the propagation type `p`
+// assigned to call site `c`. If no such funciton exists, nil is returned.
+func propFunc(p propType, c ssa.CallInstruction, cache methodCache) []*ssa.Function {
+ if p.f != nil {
+ return []*ssa.Function{p.f}
+ }
+
+ if c.Common().Method == nil {
+ return nil
+ }
+
+ return cache.methods(p.typ, c.Common().Method.Name(), c.Parent().Prog)
+}
+
+// methodCache serves as a type -> method name -> methods
+// cache when computing methods of a type using the
+// ssa.Program.MethodSets and ssa.Program.MethodValue
+// APIs. The cache is used to speed up querying of
+// methods of a type as the mentioned APIs are expensive.
+type methodCache map[types.Type]map[string][]*ssa.Function
+
+// methods returns methods of a type `t` named `name`. First consults
+// `mc` and otherwise queries `prog` for the method. If no such method
+// exists, nil is returned.
+func (mc methodCache) methods(t types.Type, name string, prog *ssa.Program) []*ssa.Function {
+ if ms, ok := mc[t]; ok {
+ return ms[name]
+ }
+
+ ms := make(map[string][]*ssa.Function)
+ mset := prog.MethodSets.MethodSet(t)
+ for i, n := 0, mset.Len(); i < n; i++ {
+ // f can be nil when t is an interface or some
+ // other type without any runtime methods.
+ if f := prog.MethodValue(mset.At(i)); f != nil {
+ ms[f.Name()] = append(ms[f.Name()], f)
+ }
+ }
+ mc[t] = ms
+ return ms[name]
+}
diff --git a/go/callgraph/vta/vta_test.go b/go/callgraph/vta/vta_test.go
new file mode 100644
index 0000000..79ab31c
--- /dev/null
+++ b/go/callgraph/vta/vta_test.go
@@ -0,0 +1,109 @@
+// Copyright 2021 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 vta
+
+import (
+ "fmt"
+ "sort"
+ "strings"
+ "testing"
+
+ "golang.org/x/tools/go/callgraph"
+ "golang.org/x/tools/go/callgraph/cha"
+ "golang.org/x/tools/go/ssa"
+
+ "golang.org/x/tools/go/ssa/ssautil"
+)
+
+// callGraphStr stringifes `g` into a list of strings where
+// each entry is of the form
+// f: cs1 -> f1, f2, ...; ...; csw -> fx, fy, ...
+// f is a function, cs1, ..., csw are call sites in f, and
+// f1, f2, ..., fx, fy, ... are the resolved callees.
+func callGraphStr(g *callgraph.Graph) []string {
+ var gs []string
+ for f, n := range g.Nodes {
+ c := make(map[string][]string)
+ for _, edge := range n.Out {
+ cs := edge.Site.String()
+ c[cs] = append(c[cs], funcName(edge.Callee.Func))
+ }
+
+ var cs []string
+ for site, fs := range c {
+ sort.Strings(fs)
+ entry := fmt.Sprintf("%v -> %v", site, strings.Join(fs, ", "))
+ cs = append(cs, entry)
+ }
+
+ sort.Strings(cs)
+ entry := fmt.Sprintf("%v: %v", funcName(f), strings.Join(cs, "; "))
+ gs = append(gs, entry)
+ }
+ return gs
+}
+
+func TestVTACallGraph(t *testing.T) {
+ for _, file := range []string{
+ "testdata/callgraph_static.go",
+ "testdata/callgraph_ho.go",
+ "testdata/callgraph_interfaces.go",
+ "testdata/callgraph_pointers.go",
+ "testdata/callgraph_collections.go",
+ } {
+ t.Run(file, func(t *testing.T) {
+ prog, want, err := testProg(file)
+ if err != nil {
+ t.Fatalf("couldn't load test file '%s': %s", file, err)
+ }
+ if len(want) == 0 {
+ t.Fatalf("couldn't find want in `%s`", file)
+ }
+
+ g := CallGraph(ssautil.AllFunctions(prog), cha.CallGraph(prog))
+ if got := callGraphStr(g); !subGraph(want, got) {
+ t.Errorf("computed callgraph %v should contain %v", got, want)
+ }
+ })
+ }
+}
+
+// TestVTAProgVsFuncSet exemplifies and tests different possibilities
+// enabled by having an arbitrary function set as input to CallGraph
+// instead of the whole program (i.e., ssautil.AllFunctions(prog)).
+func TestVTAProgVsFuncSet(t *testing.T) {
+ prog, want, err := testProg("testdata/callgraph_nested_ptr.go")
+ if err != nil {
+ t.Fatalf("couldn't load test `testdata/callgraph_nested_ptr.go`: %s", err)
+ }
+ if len(want) == 0 {
+ t.Fatal("couldn't find want in `testdata/callgraph_nested_ptr.go`")
+ }
+
+ allFuncs := ssautil.AllFunctions(prog)
+ g := CallGraph(allFuncs, cha.CallGraph(prog))
+ // VTA over the whole program will produce a call graph that
+ // includes Baz:(**i).Foo -> A.Foo, B.Foo.
+ if got := callGraphStr(g); !subGraph(want, got) {
+ t.Errorf("computed callgraph %v should contain %v", got, want)
+ }
+
+ // Prune the set of program functions to exclude Bar(). This should
+ // yield a call graph that includes different set of callees for Baz
+ // Baz:(**i).Foo -> A.Foo
+ //
+ // Note that the exclusion of Bar can happen, for instance, if Baz is
+ // considered an entry point of some data flow analysis and Bar is
+ // provably (e.g., using CHA forward reachability) unreachable from Baz.
+ noBarFuncs := make(map[*ssa.Function]bool)
+ for f, in := range allFuncs {
+ noBarFuncs[f] = in && (funcName(f) != "Bar")
+ }
+ want = []string{"Baz: Do(i) -> Do; invoke t2.Foo() -> A.Foo"}
+ g = CallGraph(noBarFuncs, cha.CallGraph(prog))
+ if got := callGraphStr(g); !subGraph(want, got) {
+ t.Errorf("pruned callgraph %v should contain %v", got, want)
+ }
+}