dotgraph.go

     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  
    15  package graph
    16  
    17  import (
    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.
    29  type 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.
    34  type 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.
    44  type 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  
    53  const 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.
    57  func 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.
   101  type builder struct {
   102  	io.Writer
   103  	attributes *DotAttributes
   104  	config     *DotConfig
   105  }
   106  
   107  // start generates a title and initial node in DOT format.
   108  func (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.
   118  func (b *builder) finish() {
   119  	fmt.Fprintln(b, "}")
   120  }
   121  
   122  // addLegend generates a legend in DOT format.
   123  func (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.
   141  func (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.
   216  func (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  
   265  func (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.
   285  func (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).
   330  func 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  
   384  func 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.
   396  func (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  
   428  func 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  
   436  func (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  
   470  func 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.
   478  func 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.
   489  func escapeForDot(str string) string {
   490  	return strings.ReplaceAll(strings.ReplaceAll(strings.ReplaceAll(str, `\`, `\\`), `"`, `\"`), "\n", `\l`)
   491  }
   492
View as plain text