| package graph |
| |
| import ( |
| "fmt" |
| "testing" |
| |
| "github.com/google/pprof/profile" |
| ) |
| |
| func edgeDebugString(edge *Edge) string { |
| debug := "" |
| debug += fmt.Sprintf("\t\tSrc: %p\n", edge.Src) |
| debug += fmt.Sprintf("\t\tDest: %p\n", edge.Dest) |
| debug += fmt.Sprintf("\t\tWeight: %d\n", edge.Weight) |
| debug += fmt.Sprintf("\t\tResidual: %t\n", edge.Residual) |
| debug += fmt.Sprintf("\t\tInline: %t\n", edge.Inline) |
| return debug |
| } |
| |
| func edgeMapsDebugString(in, out EdgeMap) string { |
| debug := "" |
| debug += "In Edges:\n" |
| for parent, edge := range in { |
| debug += fmt.Sprintf("\tParent: %p\n", parent) |
| debug += edgeDebugString(edge) |
| } |
| debug += "Out Edges:\n" |
| for child, edge := range out { |
| debug += fmt.Sprintf("\tChild: %p\n", child) |
| debug += edgeDebugString(edge) |
| } |
| return debug |
| } |
| |
| func graphDebugString(graph *Graph) string { |
| debug := "" |
| for i, node := range graph.Nodes { |
| debug += fmt.Sprintf("Node %d: %p\n", i, node) |
| } |
| |
| for i, node := range graph.Nodes { |
| debug += "\n" |
| debug += fmt.Sprintf("=== Node %d: %p ===\n", i, node) |
| debug += edgeMapsDebugString(node.In, node.Out) |
| } |
| return debug |
| } |
| |
| func expectedNodesDebugString(expected []expectedNode) string { |
| debug := "" |
| for i, node := range expected { |
| debug += fmt.Sprintf("Node %d: %p\n", i, node.node) |
| } |
| |
| for i, node := range expected { |
| debug += "\n" |
| debug += fmt.Sprintf("=== Node %d: %p ===\n", i, node.node) |
| debug += edgeMapsDebugString(node.in, node.out) |
| } |
| return debug |
| } |
| |
| // edgeMapsEqual checks if all the edges in this equal all the edges in that. |
| func edgeMapsEqual(this, that EdgeMap) bool { |
| if len(this) != len(that) { |
| return false |
| } |
| for node, thisEdge := range this { |
| if *thisEdge != *that[node] { |
| return false |
| } |
| } |
| return true |
| } |
| |
| // nodesEqual checks if node is equal to expected. |
| func nodesEqual(node *Node, expected expectedNode) bool { |
| return node == expected.node && edgeMapsEqual(node.In, expected.in) && |
| edgeMapsEqual(node.Out, expected.out) |
| } |
| |
| // graphsEqual checks if graph is equivalent to the graph templated by expected. |
| func graphsEqual(graph *Graph, expected []expectedNode) bool { |
| if len(graph.Nodes) != len(expected) { |
| return false |
| } |
| expectedSet := make(map[*Node]expectedNode) |
| for i := range expected { |
| expectedSet[expected[i].node] = expected[i] |
| } |
| |
| for _, node := range graph.Nodes { |
| expectedNode, found := expectedSet[node] |
| if !found || !nodesEqual(node, expectedNode) { |
| return false |
| } |
| } |
| return true |
| } |
| |
| type expectedNode struct { |
| node *Node |
| in, out EdgeMap |
| } |
| |
| type trimTreeTestcase struct { |
| initial *Graph |
| expected []expectedNode |
| keep NodePtrSet |
| } |
| |
| // makeExpectedEdgeResidual makes the edge from parent to child residual. |
| func makeExpectedEdgeResidual(parent, child expectedNode) { |
| parent.out[child.node].Residual = true |
| child.in[parent.node].Residual = true |
| } |
| |
| func makeEdgeInline(edgeMap EdgeMap, node *Node) { |
| edgeMap[node].Inline = true |
| } |
| |
| func setEdgeWeight(edgeMap EdgeMap, node *Node, weight int64) { |
| edgeMap[node].Weight = weight |
| } |
| |
| // createEdges creates directed edges from the parent to each of the children. |
| func createEdges(parent *Node, children ...*Node) { |
| for _, child := range children { |
| edge := &Edge{ |
| Src: parent, |
| Dest: child, |
| } |
| parent.Out[child] = edge |
| child.In[parent] = edge |
| } |
| } |
| |
| // createEmptyNode creates a node without any edges. |
| func createEmptyNode() *Node { |
| return &Node{ |
| In: make(EdgeMap), |
| Out: make(EdgeMap), |
| } |
| } |
| |
| // createExpectedNodes creates a slice of expectedNodes from nodes. |
| func createExpectedNodes(nodes ...*Node) ([]expectedNode, NodePtrSet) { |
| expected := make([]expectedNode, len(nodes)) |
| keep := make(NodePtrSet, len(nodes)) |
| |
| for i, node := range nodes { |
| expected[i] = expectedNode{ |
| node: node, |
| in: make(EdgeMap), |
| out: make(EdgeMap), |
| } |
| keep[node] = true |
| } |
| |
| return expected, keep |
| } |
| |
| // createExpectedEdges creates directed edges from the parent to each of the |
| // children. |
| func createExpectedEdges(parent expectedNode, children ...expectedNode) { |
| for _, child := range children { |
| edge := &Edge{ |
| Src: parent.node, |
| Dest: child.node, |
| } |
| parent.out[child.node] = edge |
| child.in[parent.node] = edge |
| } |
| } |
| |
| // createTestCase1 creates a test case that initially looks like: |
| // 0 |
| // |(5) |
| // 1 |
| // (3)/ \(4) |
| // 2 3. |
| // |
| // After keeping 0, 2, and 3, it expects the graph: |
| // 0 |
| // (3)/ \(4) |
| // 2 3. |
| func createTestCase1() trimTreeTestcase { |
| // Create initial graph |
| graph := &Graph{make(Nodes, 4)} |
| nodes := graph.Nodes |
| for i := range nodes { |
| nodes[i] = createEmptyNode() |
| } |
| createEdges(nodes[0], nodes[1]) |
| createEdges(nodes[1], nodes[2], nodes[3]) |
| makeEdgeInline(nodes[0].Out, nodes[1]) |
| makeEdgeInline(nodes[1].Out, nodes[2]) |
| setEdgeWeight(nodes[0].Out, nodes[1], 5) |
| setEdgeWeight(nodes[1].Out, nodes[2], 3) |
| setEdgeWeight(nodes[1].Out, nodes[3], 4) |
| |
| // Create expected graph |
| expected, keep := createExpectedNodes(nodes[0], nodes[2], nodes[3]) |
| createExpectedEdges(expected[0], expected[1], expected[2]) |
| makeEdgeInline(expected[0].out, expected[1].node) |
| makeExpectedEdgeResidual(expected[0], expected[1]) |
| makeExpectedEdgeResidual(expected[0], expected[2]) |
| setEdgeWeight(expected[0].out, expected[1].node, 3) |
| setEdgeWeight(expected[0].out, expected[2].node, 4) |
| return trimTreeTestcase{ |
| initial: graph, |
| expected: expected, |
| keep: keep, |
| } |
| } |
| |
| // createTestCase2 creates a test case that initially looks like: |
| // 3 |
| // | (12) |
| // 1 |
| // | (8) |
| // 2 |
| // | (15) |
| // 0 |
| // | (10) |
| // 4. |
| // |
| // After keeping 3 and 4, it expects the graph: |
| // 3 |
| // | (10) |
| // 4. |
| func createTestCase2() trimTreeTestcase { |
| // Create initial graph |
| graph := &Graph{make(Nodes, 5)} |
| nodes := graph.Nodes |
| for i := range nodes { |
| nodes[i] = createEmptyNode() |
| } |
| createEdges(nodes[3], nodes[1]) |
| createEdges(nodes[1], nodes[2]) |
| createEdges(nodes[2], nodes[0]) |
| createEdges(nodes[0], nodes[4]) |
| setEdgeWeight(nodes[3].Out, nodes[1], 12) |
| setEdgeWeight(nodes[1].Out, nodes[2], 8) |
| setEdgeWeight(nodes[2].Out, nodes[0], 15) |
| setEdgeWeight(nodes[0].Out, nodes[4], 10) |
| |
| // Create expected graph |
| expected, keep := createExpectedNodes(nodes[3], nodes[4]) |
| createExpectedEdges(expected[0], expected[1]) |
| makeExpectedEdgeResidual(expected[0], expected[1]) |
| setEdgeWeight(expected[0].out, expected[1].node, 10) |
| return trimTreeTestcase{ |
| initial: graph, |
| expected: expected, |
| keep: keep, |
| } |
| } |
| |
| // createTestCase3 creates an initially empty graph and expects an empty graph |
| // after trimming. |
| func createTestCase3() trimTreeTestcase { |
| graph := &Graph{make(Nodes, 0)} |
| expected, keep := createExpectedNodes() |
| return trimTreeTestcase{ |
| initial: graph, |
| expected: expected, |
| keep: keep, |
| } |
| } |
| |
| // createTestCase4 creates a test case that initially looks like: |
| // 0. |
| // |
| // After keeping 0, it expects the graph: |
| // 0. |
| func createTestCase4() trimTreeTestcase { |
| graph := &Graph{make(Nodes, 1)} |
| nodes := graph.Nodes |
| for i := range nodes { |
| nodes[i] = createEmptyNode() |
| } |
| expected, keep := createExpectedNodes(nodes[0]) |
| return trimTreeTestcase{ |
| initial: graph, |
| expected: expected, |
| keep: keep, |
| } |
| } |
| |
| func createTrimTreeTestCases() []trimTreeTestcase { |
| caseGenerators := []func() trimTreeTestcase{ |
| createTestCase1, |
| createTestCase2, |
| createTestCase3, |
| createTestCase4, |
| } |
| cases := make([]trimTreeTestcase, len(caseGenerators)) |
| for i, gen := range caseGenerators { |
| cases[i] = gen() |
| } |
| return cases |
| } |
| |
| func TestTrimTree(t *testing.T) { |
| tests := createTrimTreeTestCases() |
| for _, test := range tests { |
| graph := test.initial |
| graph.TrimTree(test.keep) |
| if !graphsEqual(graph, test.expected) { |
| t.Fatalf("Graphs do not match.\nExpected: %s\nFound: %s\n", |
| expectedNodesDebugString(test.expected), |
| graphDebugString(graph)) |
| } |
| } |
| } |
| |
| func nodeTestProfile() *profile.Profile { |
| mappings := []*profile.Mapping{ |
| { |
| ID: 1, |
| File: "symbolized_binary", |
| }, |
| { |
| ID: 2, |
| File: "unsymbolized_library_1", |
| }, |
| { |
| ID: 3, |
| File: "unsymbolized_library_2", |
| }, |
| } |
| functions := []*profile.Function{ |
| {ID: 1, Name: "symname"}, |
| {ID: 2}, |
| } |
| locations := []*profile.Location{ |
| { |
| ID: 1, |
| Mapping: mappings[0], |
| Line: []profile.Line{ |
| {Function: functions[0]}, |
| }, |
| }, |
| { |
| ID: 2, |
| Mapping: mappings[1], |
| Line: []profile.Line{ |
| {Function: functions[1]}, |
| }, |
| }, |
| { |
| ID: 3, |
| Mapping: mappings[2], |
| }, |
| } |
| return &profile.Profile{ |
| PeriodType: &profile.ValueType{Type: "cpu", Unit: "milliseconds"}, |
| SampleType: []*profile.ValueType{ |
| {Type: "type", Unit: "unit"}, |
| }, |
| Sample: []*profile.Sample{ |
| { |
| Location: []*profile.Location{locations[0]}, |
| Value: []int64{1}, |
| }, |
| { |
| Location: []*profile.Location{locations[1]}, |
| Value: []int64{1}, |
| }, |
| { |
| Location: []*profile.Location{locations[2]}, |
| Value: []int64{1}, |
| }, |
| }, |
| Location: locations, |
| Function: functions, |
| Mapping: mappings, |
| } |
| } |
| |
| // Check that nodes are properly created for a simple profile. |
| func TestCreateNodes(t *testing.T) { |
| testProfile := nodeTestProfile() |
| wantNodeSet := NodeSet{ |
| {Name: "symname"}: true, |
| {Objfile: "unsymbolized_library_1"}: true, |
| {Objfile: "unsymbolized_library_2"}: true, |
| } |
| |
| nodes, _ := CreateNodes(testProfile, &Options{}) |
| if len(nodes) != len(wantNodeSet) { |
| t.Errorf("got %d nodes, want %d", len(nodes), len(wantNodeSet)) |
| } |
| for _, node := range nodes { |
| if !wantNodeSet[node.Info] { |
| t.Errorf("unexpected node %v", node.Info) |
| } |
| } |
| } |
| |
| func TestShortenFunctionName(t *testing.T) { |
| type testCase struct { |
| name string |
| want string |
| } |
| testcases := []testCase{ |
| { |
| "root", |
| "root", |
| }, |
| { |
| "syscall.Syscall", |
| "syscall.Syscall", |
| }, |
| { |
| "net/http.(*conn).serve", |
| "http.(*conn).serve", |
| }, |
| { |
| "github.com/blahBlah/foo.Foo", |
| "foo.Foo", |
| }, |
| { |
| "github.com/BlahBlah/foo.Foo", |
| "foo.Foo", |
| }, |
| { |
| "github.com/blah-blah/foo_bar.(*FooBar).Foo", |
| "foo_bar.(*FooBar).Foo", |
| }, |
| { |
| "encoding/json.(*structEncoder).(encoding/json.encode)-fm", |
| "json.(*structEncoder).(encoding/json.encode)-fm", |
| }, |
| { |
| "github.com/blah/blah/vendor/gopkg.in/redis.v3.(*baseClient).(github.com/blah/blah/vendor/gopkg.in/redis.v3.process)-fm", |
| "redis.v3.(*baseClient).(github.com/blah/blah/vendor/gopkg.in/redis.v3.process)-fm", |
| }, |
| { |
| "java.util.concurrent.ThreadPoolExecutor$Worker.run", |
| "ThreadPoolExecutor$Worker.run", |
| }, |
| { |
| "java.bar.foo.FooBar.run(java.lang.Runnable)", |
| "FooBar.run", |
| }, |
| { |
| "(anonymous namespace)::Bar::Foo", |
| "Bar::Foo", |
| }, |
| { |
| "(anonymous namespace)::foo", |
| "foo", |
| }, |
| { |
| "foo_bar::Foo::bar", |
| "Foo::bar", |
| }, |
| { |
| "foo", |
| "foo", |
| }, |
| } |
| for _, tc := range testcases { |
| name := ShortenFunctionName(tc.name) |
| if got, want := name, tc.want; got != want { |
| t.Errorf("ShortenFunctionName(%q) = %q, want %q", tc.name, got, want) |
| } |
| } |
| } |