Source file src/cmd/vendor/github.com/google/pprof/internal/graph/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(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, 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			edge.Src.Info.PrintableName(), arrow, edge.Dest.Info.PrintableName(), w)
   309		attr = fmt.Sprintf(`%s tooltip=%s labeltooltip=%s`, attr, tooltip, tooltip)
   310	
   311		if edge.Residual {
   312			attr = attr + ` style="dotted"`
   313		}
   314	
   315		if hasNodelets {
   316			// Separate children further if source has tags.
   317			attr = attr + " minlen=2"
   318		}
   319	
   320		fmt.Fprintf(b, "N%d -> N%d [%s]\n", from, to, attr)
   321	}
   322	
   323	// dotColor returns a color for the given score (between -1.0 and
   324	// 1.0), with -1.0 colored red, 0.0 colored grey, and 1.0 colored
   325	// green. If isBackground is true, then a light (low-saturation)
   326	// color is returned (suitable for use as a background color);
   327	// otherwise, a darker color is returned (suitable for use as a
   328	// foreground color).
   329	func dotColor(score float64, isBackground bool) string {
   330		// A float between 0.0 and 1.0, indicating the extent to which
   331		// colors should be shifted away from grey (to make positive and
   332		// negative values easier to distinguish, and to make more use of
   333		// the color range.)
   334		const shift = 0.7
   335	
   336		// Saturation and value (in hsv colorspace) for background colors.
   337		const bgSaturation = 0.1
   338		const bgValue = 0.93
   339	
   340		// Saturation and value (in hsv colorspace) for foreground colors.
   341		const fgSaturation = 1.0
   342		const fgValue = 0.7
   343	
   344		// Choose saturation and value based on isBackground.
   345		var saturation float64
   346		var value float64
   347		if isBackground {
   348			saturation = bgSaturation
   349			value = bgValue
   350		} else {
   351			saturation = fgSaturation
   352			value = fgValue
   353		}
   354	
   355		// Limit the score values to the range [-1.0, 1.0].
   356		score = math.Max(-1.0, math.Min(1.0, score))
   357	
   358		// Reduce saturation near score=0 (so it is colored grey, rather than yellow).
   359		if math.Abs(score) < 0.2 {
   360			saturation *= math.Abs(score) / 0.2
   361		}
   362	
   363		// Apply 'shift' to move scores away from 0.0 (grey).
   364		if score > 0.0 {
   365			score = math.Pow(score, (1.0 - shift))
   366		}
   367		if score < 0.0 {
   368			score = -math.Pow(-score, (1.0 - shift))
   369		}
   370	
   371		var r, g, b float64 // red, green, blue
   372		if score < 0.0 {
   373			g = value
   374			r = value * (1 + saturation*score)
   375		} else {
   376			r = value
   377			g = value * (1 - saturation*score)
   378		}
   379		b = value * (1 - saturation)
   380		return fmt.Sprintf("#%02x%02x%02x", uint8(r*255.0), uint8(g*255.0), uint8(b*255.0))
   381	}
   382	
   383	func multilinePrintableName(info *NodeInfo) string {
   384		infoCopy := *info
   385		infoCopy.Name = ShortenFunctionName(infoCopy.Name)
   386		infoCopy.Name = strings.Replace(infoCopy.Name, "::", `\n`, -1)
   387		infoCopy.Name = strings.Replace(infoCopy.Name, ".", `\n`, -1)
   388		if infoCopy.File != "" {
   389			infoCopy.File = filepath.Base(infoCopy.File)
   390		}
   391		return strings.Join(infoCopy.NameComponents(), `\n`) + `\n`
   392	}
   393	
   394	// collapsedTags trims and sorts a slice of tags.
   395	func (b *builder) collapsedTags(ts []*Tag, count int, flatTags bool) []*Tag {
   396		ts = SortTags(ts, flatTags)
   397		if len(ts) <= count {
   398			return ts
   399		}
   400	
   401		tagGroups := make([][]*Tag, count)
   402		for i, t := range (ts)[:count] {
   403			tagGroups[i] = []*Tag{t}
   404		}
   405		for _, t := range (ts)[count:] {
   406			g, d := 0, tagDistance(t, tagGroups[0][0])
   407			for i := 1; i < count; i++ {
   408				if nd := tagDistance(t, tagGroups[i][0]); nd < d {
   409					g, d = i, nd
   410				}
   411			}
   412			tagGroups[g] = append(tagGroups[g], t)
   413		}
   414	
   415		var nts []*Tag
   416		for _, g := range tagGroups {
   417			l, w, c := b.tagGroupLabel(g)
   418			nts = append(nts, &Tag{
   419				Name: l,
   420				Flat: w,
   421				Cum:  c,
   422			})
   423		}
   424		return SortTags(nts, flatTags)
   425	}
   426	
   427	func tagDistance(t, u *Tag) float64 {
   428		v, _ := measurement.Scale(u.Value, u.Unit, t.Unit)
   429		if v < float64(t.Value) {
   430			return float64(t.Value) - v
   431		}
   432		return v - float64(t.Value)
   433	}
   434	
   435	func (b *builder) tagGroupLabel(g []*Tag) (label string, flat, cum int64) {
   436		if len(g) == 1 {
   437			t := g[0]
   438			return measurement.Label(t.Value, t.Unit), t.FlatValue(), t.CumValue()
   439		}
   440		min := g[0]
   441		max := g[0]
   442		df, f := min.FlatDiv, min.Flat
   443		dc, c := min.CumDiv, min.Cum
   444		for _, t := range g[1:] {
   445			if v, _ := measurement.Scale(t.Value, t.Unit, min.Unit); int64(v) < min.Value {
   446				min = t
   447			}
   448			if v, _ := measurement.Scale(t.Value, t.Unit, max.Unit); int64(v) > max.Value {
   449				max = t
   450			}
   451			f += t.Flat
   452			df += t.FlatDiv
   453			c += t.Cum
   454			dc += t.CumDiv
   455		}
   456		if df != 0 {
   457			f = f / df
   458		}
   459		if dc != 0 {
   460			c = c / dc
   461		}
   462	
   463		// Tags are not scaled with the selected output unit because tags are often
   464		// much smaller than other values which appear, so the range of tag sizes
   465		// sometimes would appear to be "0..0" when scaled to the selected output unit.
   466		return measurement.Label(min.Value, min.Unit) + ".." + measurement.Label(max.Value, max.Unit), f, c
   467	}
   468	
   469	func min64(a, b int64) int64 {
   470		if a < b {
   471			return a
   472		}
   473		return b
   474	}
   475	

View as plain text