Documentation
¶
Overview ¶
Types and functions for traversing weighted trees in 'heaviest-first' order -- the next node visited is always the node with the 'highest' total weight whose parent has also been visited.
A weighted tree is comprised of TreeNodes, each of which has a path of ScopeIDs indicating its location in the tree and a set of child TreeNodes. Except for the root TreeNode, each TreeNode has a ScopeID (the last element in its path). TreeNodes must conform to tree constraints:
- the root TreeNode's path is empty;
- a non-root TreeNode's path must be its parent's path with its own ScopeID appended at the end;
- all children of a single TreeNode must have distinct ScopeIDs.
'Highest' is determined by a provided comparator, and may be arbitrary (and of course may actually be 'lowest'.)
Walk(TreeNode, Compare, WalkOptions...) traverses the specified TreeNode in 'heaviest-first' order (as determined by the provided Compare function), and with the walk limited by the provided WalkOptions. It returns a slice of traversal root SubtreeNodes representing a view on the tree. Each SubtreeNode corresponds to a single TreeNode, and includes that TreeNode and its Path, and the SubtreeNode's parent and children. Note that, due to node elision via ElidePrefix and ElideTreeNodes (see below), given a SubtreeNode SN corresponding to TreeNode TN, SN's parent and children may not correspond to TN's parent and children.
A variety of traversal options are supported, including:
- PathPrefix(ids...): specify ids... as a traversal path prefix. When one or more path prefix is defined, then traversals only begin from specified path prefixes. If multiple path prefixes are defined, then a prefix tree is constructed from their union, and traversal begins from the leaves of that tree.
- ElidePrefix(): elide non-leaf nodes in specified prefixes. If at least one path prefix is specified and ElidePrefix is not, SubtreeNodes lying within a specified path prefix are returned with Prefix=true.
- MaxDepth(n): do not traverse deeper than n nodes from a specified path prefix.
- MaxNodes(n): do not return more than n non-prefix nodes.
- FilterTreeNodes(func(TreeNode) bool): only traverse nodes for which the specified filter function returns true.
- ElideTreeNodes(func(TreeNode) bool): Traverse normally, but only return SubtreeNodes for TreeNodes for which the specified filter function returns true.
Subtrees returned from Walk() may be rapidly constructed into the TraceViz data format with SubtreeNode.BuildResponse().
Package weightedtree provides structural helpers for defining weighted tree data. Given a DataBuilder db, a new Tree may be constructed via:
tree := New(db, renderSettings, properties...)
Trees may also be annotated with additional properties, via:
tree.With(properties...)
A tree has one or more root nodes, defined via:
root := tree.Node(selfMagnitude, properties...)
And nodes may have other nodes as children:
child := root.Node(selfMagnitude, properties...)
Each node's self-magnitude is provided at its creation; a node's total- magnitude is computed as the sum of its self-magnitude and the total- magnitude of all its children. Generally, a node's displayed width is proportional to its total-magnitude.
Arbitrary payloads may be composed into trees under Nodes, via
payload.New(node)
which allocate the payload and return its *util.DataBuilder. See payload.go for more detail.
Encoded into the TraceViz data model, a tree is:
tree
properties * render settings definition * <decorators> children * repeated root nodes
node
properties * selfMagnitudeKEy: self magnitude * <decorators> children * repeated nodes and payloads
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Compare ¶
Compare compares two arbitrary TreeNodes, returning <0, 0, or >0 if the first compares less than, equal to, or greater than the second. It may return an error if some relationship invariant between the two is not met.
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node represents a node within a Tree.
func (*Node) Node ¶
func (n *Node) Node(selfMagnitude float64, properties ...util.PropertyUpdate) *Node
Node creates and returns a new child node with the specified magnitude beneath the receiver.
func (*Node) Payload ¶
func (n *Node) Payload() util.DataBuilder
Payload creates and returns a DataBuilder that can be used to attach arbitrary structured information to the receiving Node.
type NodeCallback ¶
type NodeCallback func(inputNode *SubtreeNode, outputNode util.DataBuilder)
NodeCallback describes a callback invoked on each SubtreeNode in an invocation of SubtreeNode.BuildResponse.
type RenderSettings ¶
type RenderSettings struct {
// The height of a frame in pixels.
FrameHeightPx int64
}
RenderSettings is a collection of rendering settings for trees.
func (*RenderSettings) Define ¶
func (rs *RenderSettings) Define() util.PropertyUpdate
Define applies the receiver as a set of properties.
type ScopeID ¶
type ScopeID uint
ScopeID is the unique ID of a scope. The same scope may appear at multiple places throughout a tree.
type SubtreeNode ¶
type SubtreeNode struct {
// Parent is set to this node's parent SubtreeNode. It is nil if this
// SubtreeNode corresponds to a root TreeNode, and may be nil for
// SubtreeNodes corresponding to non-root TreeNodes, if scopes are elided.
Parent *SubtreeNode
// Prefix is true if this SubtreeNode lies within (but not at the leaf of) a
// traversal prefix path as specified by PrefixPath(). If the traversal
// options include ElidePrefix(), prefix nodes are elided.
Prefix bool
// Path is set to this node's full path. It is empty if this SubtreeNode
// corresponds to the tree root.
Path []ScopeID
// The TreeNode corresponding to this SubtreeNode.
TreeNode TreeNode
// The children of this SubtreeNode.
Children []*SubtreeNode
}
SubtreeNode is a node on a traversal subtree returned by Walk. Every SubtreeNode corresponds directly to a TreeNode, which it includes as a member field.
func Walk ¶
func Walk(tn TreeNode, compare Compare, opts ...WalkOption) (*SubtreeNode, error)
Walk returns the subtree of tree rooted at the provided TreeNode, traversed with the provided walk options. The entire traversed subtree, modulo prefix nodes (if ElidePrefix is specified) and any nodes elided by ElideScopeIDs, is constructed and returned, so Walk is unsuitable for very large traversals; it should return visualizable quantities of data. Note that zero SubtreeNodes may be returned if all TreeNodes are filtered out, and more than one SubtreeNodes may be returned if TreeNodes are elided. An invocation of Walk with no nodes elided or filtered out will always return a slice containing one SubtreeNode, corresponding to the provided TreeNode.
Walk is thread-compatible; if Path() and Children() are thread-safe for tn and all its descendants, Walk is thread-safe.
func (*SubtreeNode) BuildResponse ¶
func (sn *SubtreeNode) BuildResponse(db util.DataBuilder, nodeCallback NodeCallback)
BuildResponse builds a TraceViz response tree mirroring the subtree rooted at the receiver, with the provided DataBuilder representing the receiver. BuildResponse assembles the structure of the tree but sets no properties; instead, node properties (and response node children apart from the receiver's tree structure) may be set using the supplied callback, which is invoked once for every SubtreeNode in the receiver's subtree with that SubtreeNode and its corresponding response DataBuilder node.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree represents a tree of hierarchical, weighted data, such as the aggregated callstacks presented in a flame chart.
func New ¶
func New(db util.DataBuilder, renderSettings *RenderSettings, properties ...util.PropertyUpdate) *Tree
New returns a new Tree populating the provided data builder.
type TreeNode ¶
type TreeNode interface {
// The path of this node. It:
// * must be empty for the tree root;
// * must be unique for all nodes in the tree;
// * must, for a child C of parent P, be P.Path() with a single scope ID
// appended at the end. That ScopeID is the node's unique scope ID.
// During Walk, Path() is cached, so it may be dynamically computed.
Path() []ScopeID
// The children of this node with the specified scope IDs. If no scope IDs
// are provided, all children should be returned. Requested scope IDs
// without corresponding children should just be dropped.
Children(...ScopeID) ([]TreeNode, error)
}
TreeNode represents a node of a weighted tree.
type TreeNodeFilterFunc ¶
TreeNodeFilterFunc defines a callback implementing a TreeNode filter, and returning true for nodes that satisfy that filter.
type WalkOption ¶
type WalkOption func(wo *walkOptions) error
WalkOption specifies an option configuring a tree traversal.
func ElidePrefix ¶
func ElidePrefix() WalkOption
ElidePrefix specifies whether nodes lying on specified prefix paths are included in the traversal response. If not provided, such prefix nodes will be included, but will be marked with Prefix=true. The root is never elided. Defaults to true.
func ElideTreeNodes ¶
func ElideTreeNodes(f TreeNodeFilterFunc) WalkOption
ElideTreeNodes elides traversed nodes based on a provided TreeNode filter. Elided nodes are traversed normally, but do not result in output SubTreeNodes.
func FilterTreeNodes ¶
func FilterTreeNodes(f TreeNodeFilterFunc) WalkOption
FilterTreeNodes filters the traversal based on a provided TreeNode filter. This can be used to dynamically react to viewport size: a TreeNode may be constructed using the viewport width in pixels (e.g., as a TraceViz DataQuery parameter) and the width of the Tree's root node to ensure that only frames that will render at or above a minimum pixel width are returned.
func MaxDepth ¶
func MaxDepth(maxDepth uint) WalkOption
MaxDepth specifies the maximum depth (or path length) that a walk may traverse, as counted from the most proximate specified prefix (so that nodes at different absolute depths may be returned if they have different- length prefixes). Defaults to no limit.
func MaxNodes ¶
func MaxNodes(maxNodes uint) WalkOption
MaxNodes specifies the maximum number of non-prefix nodes that a walk may traverse. Defaults to no limit.
func PathPrefix ¶
func PathPrefix(path ...ScopeID) WalkOption
PathPrefix specifies a path prefix from which a walk should begin. If the traversal was invoked without ElidePrefix(), the nodes on the prefix path are returned, and marked with Prefix=true. PathPrefix may be specified multiple times, in which case the traversal will choose the next largest descendant of any specified prefix at each step, but if one specified PathPrefix is itself a prefix of another specified PathPrefix, only the more specific (=longer) one will apply. All nodes lying on any specified path prefix will be included in the response and marked with Prefix=true, even those whose children are not traversed, unless ElidePrefix() is also specified. Defaults to the empty path, i.e., no prefix.
Source Files