1//  Copyright 2016 Google Inc. All Rights Reserved.
2//
3//  Licensed under the Apache License, Version 2.0 (the "License");
4//  you may not use this file except in compliance with the License.
5//  You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9//  Unless required by applicable law or agreed to in writing, software
10//  distributed under the License is distributed on an "AS IS" BASIS,
11//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//  See the License for the specific language governing permissions and
13//  limitations under the License.
14
15package graph
16
17import (
18	"fmt"
19	"testing"
20
21	"github.com/google/pprof/profile"
22)
23
24func edgeDebugString(edge *Edge) string {
25	debug := ""
26	debug += fmt.Sprintf("\t\tSrc: %p\n", edge.Src)
27	debug += fmt.Sprintf("\t\tDest: %p\n", edge.Dest)
28	debug += fmt.Sprintf("\t\tWeight: %d\n", edge.Weight)
29	debug += fmt.Sprintf("\t\tResidual: %t\n", edge.Residual)
30	debug += fmt.Sprintf("\t\tInline: %t\n", edge.Inline)
31	return debug
32}
33
34func edgeMapsDebugString(in, out EdgeMap) string {
35	debug := ""
36	debug += "In Edges:\n"
37	for parent, edge := range in {
38		debug += fmt.Sprintf("\tParent: %p\n", parent)
39		debug += edgeDebugString(edge)
40	}
41	debug += "Out Edges:\n"
42	for child, edge := range out {
43		debug += fmt.Sprintf("\tChild: %p\n", child)
44		debug += edgeDebugString(edge)
45	}
46	return debug
47}
48
49func graphDebugString(graph *Graph) string {
50	debug := ""
51	for i, node := range graph.Nodes {
52		debug += fmt.Sprintf("Node %d: %p\n", i, node)
53	}
54
55	for i, node := range graph.Nodes {
56		debug += "\n"
57		debug += fmt.Sprintf("===  Node %d: %p  ===\n", i, node)
58		debug += edgeMapsDebugString(node.In, node.Out)
59	}
60	return debug
61}
62
63func expectedNodesDebugString(expected []expectedNode) string {
64	debug := ""
65	for i, node := range expected {
66		debug += fmt.Sprintf("Node %d: %p\n", i, node.node)
67	}
68
69	for i, node := range expected {
70		debug += "\n"
71		debug += fmt.Sprintf("===  Node %d: %p  ===\n", i, node.node)
72		debug += edgeMapsDebugString(node.in, node.out)
73	}
74	return debug
75}
76
77// edgeMapsEqual checks if all the edges in this equal all the edges in that.
78func edgeMapsEqual(this, that EdgeMap) bool {
79	if len(this) != len(that) {
80		return false
81	}
82	for node, thisEdge := range this {
83		if *thisEdge != *that[node] {
84			return false
85		}
86	}
87	return true
88}
89
90// nodesEqual checks if node is equal to expected.
91func nodesEqual(node *Node, expected expectedNode) bool {
92	return node == expected.node && edgeMapsEqual(node.In, expected.in) &&
93		edgeMapsEqual(node.Out, expected.out)
94}
95
96// graphsEqual checks if graph is equivalent to the graph templated by expected.
97func graphsEqual(graph *Graph, expected []expectedNode) bool {
98	if len(graph.Nodes) != len(expected) {
99		return false
100	}
101	expectedSet := make(map[*Node]expectedNode)
102	for i := range expected {
103		expectedSet[expected[i].node] = expected[i]
104	}
105
106	for _, node := range graph.Nodes {
107		expectedNode, found := expectedSet[node]
108		if !found || !nodesEqual(node, expectedNode) {
109			return false
110		}
111	}
112	return true
113}
114
115type expectedNode struct {
116	node    *Node
117	in, out EdgeMap
118}
119
120type trimTreeTestcase struct {
121	initial  *Graph
122	expected []expectedNode
123	keep     NodePtrSet
124}
125
126// makeExpectedEdgeResidual makes the edge from parent to child residual.
127func makeExpectedEdgeResidual(parent, child expectedNode) {
128	parent.out[child.node].Residual = true
129	child.in[parent.node].Residual = true
130}
131
132func makeEdgeInline(edgeMap EdgeMap, node *Node) {
133	edgeMap[node].Inline = true
134}
135
136func setEdgeWeight(edgeMap EdgeMap, node *Node, weight int64) {
137	edgeMap[node].Weight = weight
138}
139
140// createEdges creates directed edges from the parent to each of the children.
141func createEdges(parent *Node, children ...*Node) {
142	for _, child := range children {
143		edge := &Edge{
144			Src:  parent,
145			Dest: child,
146		}
147		parent.Out[child] = edge
148		child.In[parent] = edge
149	}
150}
151
152// createEmptyNode creates a node without any edges.
153func createEmptyNode() *Node {
154	return &Node{
155		In:  make(EdgeMap),
156		Out: make(EdgeMap),
157	}
158}
159
160// createExpectedNodes creates a slice of expectedNodes from nodes.
161func createExpectedNodes(nodes ...*Node) ([]expectedNode, NodePtrSet) {
162	expected := make([]expectedNode, len(nodes))
163	keep := make(NodePtrSet, len(nodes))
164
165	for i, node := range nodes {
166		expected[i] = expectedNode{
167			node: node,
168			in:   make(EdgeMap),
169			out:  make(EdgeMap),
170		}
171		keep[node] = true
172	}
173
174	return expected, keep
175}
176
177// createExpectedEdges creates directed edges from the parent to each of the
178// children.
179func createExpectedEdges(parent expectedNode, children ...expectedNode) {
180	for _, child := range children {
181		edge := &Edge{
182			Src:  parent.node,
183			Dest: child.node,
184		}
185		parent.out[child.node] = edge
186		child.in[parent.node] = edge
187	}
188}
189
190// createTestCase1 creates a test case that initially looks like:
191//     0
192//     |(5)
193//     1
194// (3)/ \(4)
195//   2   3.
196//
197// After keeping 0, 2, and 3, it expects the graph:
198//     0
199// (3)/ \(4)
200//   2   3.
201func createTestCase1() trimTreeTestcase {
202	// Create initial graph
203	graph := &Graph{make(Nodes, 4)}
204	nodes := graph.Nodes
205	for i := range nodes {
206		nodes[i] = createEmptyNode()
207	}
208	createEdges(nodes[0], nodes[1])
209	createEdges(nodes[1], nodes[2], nodes[3])
210	makeEdgeInline(nodes[0].Out, nodes[1])
211	makeEdgeInline(nodes[1].Out, nodes[2])
212	setEdgeWeight(nodes[0].Out, nodes[1], 5)
213	setEdgeWeight(nodes[1].Out, nodes[2], 3)
214	setEdgeWeight(nodes[1].Out, nodes[3], 4)
215
216	// Create expected graph
217	expected, keep := createExpectedNodes(nodes[0], nodes[2], nodes[3])
218	createExpectedEdges(expected[0], expected[1], expected[2])
219	makeEdgeInline(expected[0].out, expected[1].node)
220	makeExpectedEdgeResidual(expected[0], expected[1])
221	makeExpectedEdgeResidual(expected[0], expected[2])
222	setEdgeWeight(expected[0].out, expected[1].node, 3)
223	setEdgeWeight(expected[0].out, expected[2].node, 4)
224	return trimTreeTestcase{
225		initial:  graph,
226		expected: expected,
227		keep:     keep,
228	}
229}
230
231// createTestCase2 creates a test case that initially looks like:
232//   3
233//   | (12)
234//   1
235//   | (8)
236//   2
237//   | (15)
238//   0
239//   | (10)
240//   4.
241//
242// After keeping 3 and 4, it expects the graph:
243//   3
244//   | (10)
245//   4.
246func createTestCase2() trimTreeTestcase {
247	// Create initial graph
248	graph := &Graph{make(Nodes, 5)}
249	nodes := graph.Nodes
250	for i := range nodes {
251		nodes[i] = createEmptyNode()
252	}
253	createEdges(nodes[3], nodes[1])
254	createEdges(nodes[1], nodes[2])
255	createEdges(nodes[2], nodes[0])
256	createEdges(nodes[0], nodes[4])
257	setEdgeWeight(nodes[3].Out, nodes[1], 12)
258	setEdgeWeight(nodes[1].Out, nodes[2], 8)
259	setEdgeWeight(nodes[2].Out, nodes[0], 15)
260	setEdgeWeight(nodes[0].Out, nodes[4], 10)
261
262	// Create expected graph
263	expected, keep := createExpectedNodes(nodes[3], nodes[4])
264	createExpectedEdges(expected[0], expected[1])
265	makeExpectedEdgeResidual(expected[0], expected[1])
266	setEdgeWeight(expected[0].out, expected[1].node, 10)
267	return trimTreeTestcase{
268		initial:  graph,
269		expected: expected,
270		keep:     keep,
271	}
272}
273
274// createTestCase3 creates an initially empty graph and expects an empty graph
275// after trimming.
276func createTestCase3() trimTreeTestcase {
277	graph := &Graph{make(Nodes, 0)}
278	expected, keep := createExpectedNodes()
279	return trimTreeTestcase{
280		initial:  graph,
281		expected: expected,
282		keep:     keep,
283	}
284}
285
286// createTestCase4 creates a test case that initially looks like:
287//   0.
288//
289// After keeping 0, it expects the graph:
290//   0.
291func createTestCase4() trimTreeTestcase {
292	graph := &Graph{make(Nodes, 1)}
293	nodes := graph.Nodes
294	for i := range nodes {
295		nodes[i] = createEmptyNode()
296	}
297	expected, keep := createExpectedNodes(nodes[0])
298	return trimTreeTestcase{
299		initial:  graph,
300		expected: expected,
301		keep:     keep,
302	}
303}
304
305func createTrimTreeTestCases() []trimTreeTestcase {
306	caseGenerators := []func() trimTreeTestcase{
307		createTestCase1,
308		createTestCase2,
309		createTestCase3,
310		createTestCase4,
311	}
312	cases := make([]trimTreeTestcase, len(caseGenerators))
313	for i, gen := range caseGenerators {
314		cases[i] = gen()
315	}
316	return cases
317}
318
319func TestTrimTree(t *testing.T) {
320	tests := createTrimTreeTestCases()
321	for _, test := range tests {
322		graph := test.initial
323		graph.TrimTree(test.keep)
324		if !graphsEqual(graph, test.expected) {
325			t.Fatalf("Graphs do not match.\nExpected: %s\nFound: %s\n",
326				expectedNodesDebugString(test.expected),
327				graphDebugString(graph))
328		}
329	}
330}
331
332func nodeTestProfile() *profile.Profile {
333	mappings := []*profile.Mapping{
334		{
335			ID:   1,
336			File: "symbolized_binary",
337		},
338		{
339			ID:   2,
340			File: "unsymbolized_library_1",
341		},
342		{
343			ID:   3,
344			File: "unsymbolized_library_2",
345		},
346	}
347	functions := []*profile.Function{
348		{ID: 1, Name: "symname"},
349		{ID: 2},
350	}
351	locations := []*profile.Location{
352		{
353			ID:      1,
354			Mapping: mappings[0],
355			Line: []profile.Line{
356				{Function: functions[0]},
357			},
358		},
359		{
360			ID:      2,
361			Mapping: mappings[1],
362			Line: []profile.Line{
363				{Function: functions[1]},
364			},
365		},
366		{
367			ID:      3,
368			Mapping: mappings[2],
369		},
370	}
371	return &profile.Profile{
372		PeriodType: &profile.ValueType{Type: "cpu", Unit: "milliseconds"},
373		SampleType: []*profile.ValueType{
374			{Type: "type", Unit: "unit"},
375		},
376		Sample: []*profile.Sample{
377			{
378				Location: []*profile.Location{locations[0]},
379				Value:    []int64{1},
380			},
381			{
382				Location: []*profile.Location{locations[1]},
383				Value:    []int64{1},
384			},
385			{
386				Location: []*profile.Location{locations[2]},
387				Value:    []int64{1},
388			},
389		},
390		Location: locations,
391		Function: functions,
392		Mapping:  mappings,
393	}
394}
395
396// TestCreateNodes checks that nodes are properly created for a simple profile.
397func TestCreateNodes(t *testing.T) {
398	testProfile := nodeTestProfile()
399	wantNodeSet := NodeSet{
400		{Name: "symname"}:                   true,
401		{Objfile: "unsymbolized_library_1"}: true,
402		{Objfile: "unsymbolized_library_2"}: true,
403	}
404
405	nodes, _ := CreateNodes(testProfile, &Options{})
406	if len(nodes) != len(wantNodeSet) {
407		t.Errorf("got %d nodes, want %d", len(nodes), len(wantNodeSet))
408	}
409	for _, node := range nodes {
410		if !wantNodeSet[node.Info] {
411			t.Errorf("unexpected node %v", node.Info)
412		}
413	}
414}
415
416func TestShortenFunctionName(t *testing.T) {
417	type testCase struct {
418		name string
419		want string
420	}
421	testcases := []testCase{
422		{
423			"root",
424			"root",
425		},
426		{
427			"syscall.Syscall",
428			"syscall.Syscall",
429		},
430		{
431			"net/http.(*conn).serve",
432			"http.(*conn).serve",
433		},
434		{
435			"github.com/blahBlah/foo.Foo",
436			"foo.Foo",
437		},
438		{
439			"github.com/BlahBlah/foo.Foo",
440			"foo.Foo",
441		},
442		{
443			"github.com/blah-blah/foo_bar.(*FooBar).Foo",
444			"foo_bar.(*FooBar).Foo",
445		},
446		{
447			"encoding/json.(*structEncoder).(encoding/json.encode)-fm",
448			"json.(*structEncoder).(encoding/json.encode)-fm",
449		},
450		{
451			"github.com/blah/blah/vendor/gopkg.in/redis.v3.(*baseClient).(github.com/blah/blah/vendor/gopkg.in/redis.v3.process)-fm",
452			"redis.v3.(*baseClient).(github.com/blah/blah/vendor/gopkg.in/redis.v3.process)-fm",
453		},
454		{
455			"github.com/foo/bar/v4.(*Foo).Bar",
456			"bar.(*Foo).Bar",
457		},
458		{
459			"github.com/foo/bar/v4/baz.Foo.Bar",
460			"baz.Foo.Bar",
461		},
462		{
463			"github.com/foo/bar/v123.(*Foo).Bar",
464			"bar.(*Foo).Bar",
465		},
466		{
467			"github.com/foobar/v0.(*Foo).Bar",
468			"v0.(*Foo).Bar",
469		},
470		{
471			"github.com/foobar/v1.(*Foo).Bar",
472			"v1.(*Foo).Bar",
473		},
474		{
475			"example.org/v2xyz.Foo",
476			"v2xyz.Foo",
477		},
478		{
479			"github.com/foo/bar/v4/v4.(*Foo).Bar",
480			"v4.(*Foo).Bar",
481		},
482		{
483			"github.com/foo/bar/v4/foo/bar/v4.(*Foo).Bar",
484			"v4.(*Foo).Bar",
485		},
486		{
487			"java.util.concurrent.ThreadPoolExecutor$Worker.run",
488			"ThreadPoolExecutor$Worker.run",
489		},
490		{
491			"java.bar.foo.FooBar.run(java.lang.Runnable)",
492			"FooBar.run",
493		},
494		{
495			"(anonymous namespace)::Bar::Foo",
496			"Bar::Foo",
497		},
498		{
499			"(anonymous namespace)::foo",
500			"foo",
501		},
502		{
503			"cpp::namespace::Class::method()::$_100::operator()",
504			"Class::method",
505		},
506		{
507			"foo_bar::Foo::bar",
508			"Foo::bar",
509		},
510		{
511			"cpp::namespace::Class::method<float, long, int>()",
512			"Class::method<float, long, int>",
513		},
514		{
515			"foo",
516			"foo",
517		},
518		{
519			"com.google.perftools.gwp.benchmark.FloatBench.lambda$run$0",
520			"FloatBench.lambda$run$0",
521		},
522		{
523			"java.bar.foo.FooBar.run$0",
524			"FooBar.run$0",
525		},
526	}
527	for _, tc := range testcases {
528		name := ShortenFunctionName(tc.name)
529		if got, want := name, tc.want; got != want {
530			t.Errorf("ShortenFunctionName(%q) = %q, want %q", tc.name, got, want)
531		}
532	}
533}
534