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