1// Copyright 2014 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	"io"
20	"math"
21	"path/filepath"
22	"strings"
23
24	"github.com/google/pprof/internal/measurement"
25)
26
27// DotAttributes contains details about the graph itself, giving
28// insight into how its elements should be rendered.
29type DotAttributes struct {
30	Nodes map[*Node]*DotNodeAttributes // A map allowing each Node to have its own visualization option
31}
32
33// DotNodeAttributes contains Node specific visualization options.
34type DotNodeAttributes struct {
35	Shape       string                 // The optional shape of the node when rendered visually
36	Bold        bool                   // If the node should be bold or not
37	Peripheries int                    // An optional number of borders to place around a node
38	URL         string                 // An optional url link to add to a node
39	Formatter   func(*NodeInfo) string // An optional formatter for the node's label
40}
41
42// DotConfig contains attributes about how a graph should be
43// constructed and how it should look.
44type DotConfig struct {
45	Title     string   // The title of the DOT graph
46	LegendURL string   // The URL to link to from the legend.
47	Labels    []string // The labels for the DOT's legend
48
49	FormatValue func(int64) string // A formatting function for values
50	Total       int64              // The total weight of the graph, used to compute percentages
51}
52
53const maxNodelets = 4 // Number of nodelets for labels (both numeric and non)
54
55// ComposeDot creates and writes a in the DOT format to the writer, using
56// the configurations given.
57func ComposeDot(w io.Writer, g *Graph, a *DotAttributes, c *DotConfig) {
58	builder := &builder{w, a, c}
59
60	// Begin constructing DOT by adding a title and legend.
61	builder.start()
62	defer builder.finish()
63	builder.addLegend()
64
65	if len(g.Nodes) == 0 {
66		return
67	}
68
69	// Preprocess graph to get id map and find max flat.
70	nodeIDMap := make(map[*Node]int)
71	hasNodelets := make(map[*Node]bool)
72
73	maxFlat := float64(abs64(g.Nodes[0].FlatValue()))
74	for i, n := range g.Nodes {
75		nodeIDMap[n] = i + 1
76		if float64(abs64(n.FlatValue())) > maxFlat {
77			maxFlat = float64(abs64(n.FlatValue()))
78		}
79	}
80
81	edges := EdgeMap{}
82
83	// Add nodes and nodelets to DOT builder.
84	for _, n := range g.Nodes {
85		builder.addNode(n, nodeIDMap[n], maxFlat)
86		hasNodelets[n] = builder.addNodelets(n, nodeIDMap[n])
87
88		// Collect all edges. Use a fake node to support multiple incoming edges.
89		for _, e := range n.Out {
90			edges[&Node{}] = e
91		}
92	}
93
94	// Add edges to DOT builder. Sort edges by frequency as a hint to the graph layout engine.
95	for _, e := range edges.Sort() {
96		builder.addEdge(e, nodeIDMap[e.Src], nodeIDMap[e.Dest], hasNodelets[e.Src])
97	}
98}
99
100// builder wraps an io.Writer and understands how to compose DOT formatted elements.
101type builder struct {
102	io.Writer
103	attributes *DotAttributes
104	config     *DotConfig
105}
106
107// start generates a title and initial node in DOT format.
108func (b *builder) start() {
109	graphname := "unnamed"
110	if b.config.Title != "" {
111		graphname = b.config.Title
112	}
113	fmt.Fprintln(b, `digraph "`+graphname+`" {`)
114	fmt.Fprintln(b, `node [style=filled fillcolor="#f8f8f8"]`)
115}
116
117// finish closes the opening curly bracket in the constructed DOT buffer.
118func (b *builder) finish() {
119	fmt.Fprintln(b, "}")
120}
121
122// addLegend generates a legend in DOT format.
123func (b *builder) addLegend() {
124	labels := b.config.Labels
125	if len(labels) == 0 {
126		return
127	}
128	title := labels[0]
129	fmt.Fprintf(b, `subgraph cluster_L { "%s" [shape=box fontsize=16`, title)
130	fmt.Fprintf(b, ` label="%s\l"`, strings.Join(escapeAllForDot(labels), `\l`))
131	if b.config.LegendURL != "" {
132		fmt.Fprintf(b, ` URL="%s" target="_blank"`, b.config.LegendURL)
133	}
134	if b.config.Title != "" {
135		fmt.Fprintf(b, ` tooltip="%s"`, b.config.Title)
136	}
137	fmt.Fprintf(b, "] }\n")
138}
139
140// addNode generates a graph node in DOT format.
141func (b *builder) addNode(node *Node, nodeID int, maxFlat float64) {
142	flat, cum := node.FlatValue(), node.CumValue()
143	attrs := b.attributes.Nodes[node]
144
145	// Populate label for node.
146	var label string
147	if attrs != nil && attrs.Formatter != nil {
148		label = attrs.Formatter(&node.Info)
149	} else {
150		label = multilinePrintableName(&node.Info)
151	}
152
153	flatValue := b.config.FormatValue(flat)
154	if flat != 0 {
155		label = label + fmt.Sprintf(`%s (%s)`,
156			flatValue,
157			strings.TrimSpace(measurement.Percentage(flat, b.config.Total)))
158	} else {
159		label = label + "0"
160	}
161	cumValue := flatValue
162	if cum != flat {
163		if flat != 0 {
164			label = label + `\n`
165		} else {
166			label = label + " "
167		}
168		cumValue = b.config.FormatValue(cum)
169		label = label + fmt.Sprintf(`of %s (%s)`,
170			cumValue,
171			strings.TrimSpace(measurement.Percentage(cum, b.config.Total)))
172	}
173
174	// Scale font sizes from 8 to 24 based on percentage of flat frequency.
175	// Use non linear growth to emphasize the size difference.
176	baseFontSize, maxFontGrowth := 8, 16.0
177	fontSize := baseFontSize
178	if maxFlat != 0 && flat != 0 && float64(abs64(flat)) <= maxFlat {
179		fontSize += int(math.Ceil(maxFontGrowth * math.Sqrt(float64(abs64(flat))/maxFlat)))
180	}
181
182	// Determine node shape.
183	shape := "box"
184	if attrs != nil && attrs.Shape != "" {
185		shape = attrs.Shape
186	}
187
188	// Create DOT attribute for node.
189	attr := fmt.Sprintf(`label="%s" id="node%d" fontsize=%d shape=%s tooltip="%s (%s)" color="%s" fillcolor="%s"`,
190		label, nodeID, fontSize, shape, escapeForDot(node.Info.PrintableName()), cumValue,
191		dotColor(float64(node.CumValue())/float64(abs64(b.config.Total)), false),
192		dotColor(float64(node.CumValue())/float64(abs64(b.config.Total)), true))
193
194	// Add on extra attributes if provided.
195	if attrs != nil {
196		// Make bold if specified.
197		if attrs.Bold {
198			attr += ` style="bold,filled"`
199		}
200
201		// Add peripheries if specified.
202		if attrs.Peripheries != 0 {
203			attr += fmt.Sprintf(` peripheries=%d`, attrs.Peripheries)
204		}
205
206		// Add URL if specified. target="_blank" forces the link to open in a new tab.
207		if attrs.URL != "" {
208			attr += fmt.Sprintf(` URL="%s" target="_blank"`, attrs.URL)
209		}
210	}
211
212	fmt.Fprintf(b, "N%d [%s]\n", nodeID, attr)
213}
214
215// addNodelets generates the DOT boxes for the node tags if they exist.
216func (b *builder) addNodelets(node *Node, nodeID int) bool {
217	var nodelets string
218
219	// Populate two Tag slices, one for LabelTags and one for NumericTags.
220	var ts []*Tag
221	lnts := make(map[string][]*Tag)
222	for _, t := range node.LabelTags {
223		ts = append(ts, t)
224	}
225	for l, tm := range node.NumericTags {
226		for _, t := range tm {
227			lnts[l] = append(lnts[l], t)
228		}
229	}
230
231	// For leaf nodes, print cumulative tags (includes weight from
232	// children that have been deleted).
233	// For internal nodes, print only flat tags.
234	flatTags := len(node.Out) > 0
235
236	// Select the top maxNodelets alphanumeric labels by weight.
237	SortTags(ts, flatTags)
238	if len(ts) > maxNodelets {
239		ts = ts[:maxNodelets]
240	}
241	for i, t := range ts {
242		w := t.CumValue()
243		if flatTags {
244			w = t.FlatValue()
245		}
246		if w == 0 {
247			continue
248		}
249		weight := b.config.FormatValue(w)
250		nodelets += fmt.Sprintf(`N%d_%d [label = "%s" id="N%d_%d" fontsize=8 shape=box3d tooltip="%s"]`+"\n", nodeID, i, t.Name, nodeID, i, weight)
251		nodelets += fmt.Sprintf(`N%d -> N%d_%d [label=" %s" weight=100 tooltip="%s" labeltooltip="%s"]`+"\n", nodeID, nodeID, i, weight, weight, weight)
252		if nts := lnts[t.Name]; nts != nil {
253			nodelets += b.numericNodelets(nts, maxNodelets, flatTags, fmt.Sprintf(`N%d_%d`, nodeID, i))
254		}
255	}
256
257	if nts := lnts[""]; nts != nil {
258		nodelets += b.numericNodelets(nts, maxNodelets, flatTags, fmt.Sprintf(`N%d`, nodeID))
259	}
260
261	fmt.Fprint(b, nodelets)
262	return nodelets != ""
263}
264
265func (b *builder) numericNodelets(nts []*Tag, maxNumNodelets int, flatTags bool, source string) string {
266	nodelets := ""
267
268	// Collapse numeric labels into maxNumNodelets buckets, of the form:
269	// 1MB..2MB, 3MB..5MB, ...
270	for j, t := range b.collapsedTags(nts, maxNumNodelets, flatTags) {
271		w, attr := t.CumValue(), ` style="dotted"`
272		if flatTags || t.FlatValue() == t.CumValue() {
273			w, attr = t.FlatValue(), ""
274		}
275		if w != 0 {
276			weight := b.config.FormatValue(w)
277			nodelets += fmt.Sprintf(`N%s_%d [label = "%s" id="N%s_%d" fontsize=8 shape=box3d tooltip="%s"]`+"\n", source, j, t.Name, source, j, weight)
278			nodelets += fmt.Sprintf(`%s -> N%s_%d [label=" %s" weight=100 tooltip="%s" labeltooltip="%s"%s]`+"\n", source, source, j, weight, weight, weight, attr)
279		}
280	}
281	return nodelets
282}
283
284// addEdge generates a graph edge in DOT format.
285func (b *builder) addEdge(edge *Edge, from, to int, hasNodelets bool) {
286	var inline string
287	if edge.Inline {
288		inline = `\n (inline)`
289	}
290	w := b.config.FormatValue(edge.WeightValue())
291	attr := fmt.Sprintf(`label=" %s%s"`, w, inline)
292	if b.config.Total != 0 {
293		// Note: edge.weight > b.config.Total is possible for profile diffs.
294		if weight := 1 + int(min64(abs64(edge.WeightValue()*100/b.config.Total), 100)); weight > 1 {
295			attr = fmt.Sprintf(`%s weight=%d`, attr, weight)
296		}
297		if width := 1 + int(min64(abs64(edge.WeightValue()*5/b.config.Total), 5)); width > 1 {
298			attr = fmt.Sprintf(`%s penwidth=%d`, attr, width)
299		}
300		attr = fmt.Sprintf(`%s color="%s"`, attr,
301			dotColor(float64(edge.WeightValue())/float64(abs64(b.config.Total)), false))
302	}
303	arrow := "->"
304	if edge.Residual {
305		arrow = "..."
306	}
307	tooltip := fmt.Sprintf(`"%s %s %s (%s)"`,
308		escapeForDot(edge.Src.Info.PrintableName()), arrow,
309		escapeForDot(edge.Dest.Info.PrintableName()), w)
310	attr = fmt.Sprintf(`%s tooltip=%s labeltooltip=%s`, attr, tooltip, tooltip)
311
312	if edge.Residual {
313		attr = attr + ` style="dotted"`
314	}
315
316	if hasNodelets {
317		// Separate children further if source has tags.
318		attr = attr + " minlen=2"
319	}
320
321	fmt.Fprintf(b, "N%d -> N%d [%s]\n", from, to, attr)
322}
323
324// dotColor returns a color for the given score (between -1.0 and
325// 1.0), with -1.0 colored green, 0.0 colored grey, and 1.0 colored
326// red. If isBackground is true, then a light (low-saturation)
327// color is returned (suitable for use as a background color);
328// otherwise, a darker color is returned (suitable for use as a
329// foreground color).
330func dotColor(score float64, isBackground bool) string {
331	// A float between 0.0 and 1.0, indicating the extent to which
332	// colors should be shifted away from grey (to make positive and
333	// negative values easier to distinguish, and to make more use of
334	// the color range.)
335	const shift = 0.7
336
337	// Saturation and value (in hsv colorspace) for background colors.
338	const bgSaturation = 0.1
339	const bgValue = 0.93
340
341	// Saturation and value (in hsv colorspace) for foreground colors.
342	const fgSaturation = 1.0
343	const fgValue = 0.7
344
345	// Choose saturation and value based on isBackground.
346	var saturation float64
347	var value float64
348	if isBackground {
349		saturation = bgSaturation
350		value = bgValue
351	} else {
352		saturation = fgSaturation
353		value = fgValue
354	}
355
356	// Limit the score values to the range [-1.0, 1.0].
357	score = math.Max(-1.0, math.Min(1.0, score))
358
359	// Reduce saturation near score=0 (so it is colored grey, rather than yellow).
360	if math.Abs(score) < 0.2 {
361		saturation *= math.Abs(score) / 0.2
362	}
363
364	// Apply 'shift' to move scores away from 0.0 (grey).
365	if score > 0.0 {
366		score = math.Pow(score, (1.0 - shift))
367	}
368	if score < 0.0 {
369		score = -math.Pow(-score, (1.0 - shift))
370	}
371
372	var r, g, b float64 // red, green, blue
373	if score < 0.0 {
374		g = value
375		r = value * (1 + saturation*score)
376	} else {
377		r = value
378		g = value * (1 - saturation*score)
379	}
380	b = value * (1 - saturation)
381	return fmt.Sprintf("#%02x%02x%02x", uint8(r*255.0), uint8(g*255.0), uint8(b*255.0))
382}
383
384func multilinePrintableName(info *NodeInfo) string {
385	infoCopy := *info
386	infoCopy.Name = escapeForDot(ShortenFunctionName(infoCopy.Name))
387	infoCopy.Name = strings.Replace(infoCopy.Name, "::", `\n`, -1)
388	infoCopy.Name = strings.Replace(infoCopy.Name, ".", `\n`, -1)
389	if infoCopy.File != "" {
390		infoCopy.File = filepath.Base(infoCopy.File)
391	}
392	return strings.Join(infoCopy.NameComponents(), `\n`) + `\n`
393}
394
395// collapsedTags trims and sorts a slice of tags.
396func (b *builder) collapsedTags(ts []*Tag, count int, flatTags bool) []*Tag {
397	ts = SortTags(ts, flatTags)
398	if len(ts) <= count {
399		return ts
400	}
401
402	tagGroups := make([][]*Tag, count)
403	for i, t := range (ts)[:count] {
404		tagGroups[i] = []*Tag{t}
405	}
406	for _, t := range (ts)[count:] {
407		g, d := 0, tagDistance(t, tagGroups[0][0])
408		for i := 1; i < count; i++ {
409			if nd := tagDistance(t, tagGroups[i][0]); nd < d {
410				g, d = i, nd
411			}
412		}
413		tagGroups[g] = append(tagGroups[g], t)
414	}
415
416	var nts []*Tag
417	for _, g := range tagGroups {
418		l, w, c := b.tagGroupLabel(g)
419		nts = append(nts, &Tag{
420			Name: l,
421			Flat: w,
422			Cum:  c,
423		})
424	}
425	return SortTags(nts, flatTags)
426}
427
428func tagDistance(t, u *Tag) float64 {
429	v, _ := measurement.Scale(u.Value, u.Unit, t.Unit)
430	if v < float64(t.Value) {
431		return float64(t.Value) - v
432	}
433	return v - float64(t.Value)
434}
435
436func (b *builder) tagGroupLabel(g []*Tag) (label string, flat, cum int64) {
437	if len(g) == 1 {
438		t := g[0]
439		return measurement.Label(t.Value, t.Unit), t.FlatValue(), t.CumValue()
440	}
441	min := g[0]
442	max := g[0]
443	df, f := min.FlatDiv, min.Flat
444	dc, c := min.CumDiv, min.Cum
445	for _, t := range g[1:] {
446		if v, _ := measurement.Scale(t.Value, t.Unit, min.Unit); int64(v) < min.Value {
447			min = t
448		}
449		if v, _ := measurement.Scale(t.Value, t.Unit, max.Unit); int64(v) > max.Value {
450			max = t
451		}
452		f += t.Flat
453		df += t.FlatDiv
454		c += t.Cum
455		dc += t.CumDiv
456	}
457	if df != 0 {
458		f = f / df
459	}
460	if dc != 0 {
461		c = c / dc
462	}
463
464	// Tags are not scaled with the selected output unit because tags are often
465	// much smaller than other values which appear, so the range of tag sizes
466	// sometimes would appear to be "0..0" when scaled to the selected output unit.
467	return measurement.Label(min.Value, min.Unit) + ".." + measurement.Label(max.Value, max.Unit), f, c
468}
469
470func min64(a, b int64) int64 {
471	if a < b {
472		return a
473	}
474	return b
475}
476
477// escapeAllForDot applies escapeForDot to all strings in the given slice.
478func escapeAllForDot(in []string) []string {
479	var out = make([]string, len(in))
480	for i := range in {
481		out[i] = escapeForDot(in[i])
482	}
483	return out
484}
485
486// escapeForDot escapes double quotes and backslashes, and replaces Graphviz's
487// "center" character (\n) with a left-justified character.
488// See https://graphviz.org/doc/info/attrs.html#k:escString for more info.
489func escapeForDot(str string) string {
490	return strings.ReplaceAll(strings.ReplaceAll(strings.ReplaceAll(str, `\`, `\\`), `"`, `\"`), "\n", `\l`)
491}
492