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 ¶
- type Comparable
- type CompareFn
- type Node
- type RenderSettings
- type ScopeID
- type SubtreeNode
- type Tree
- type TreeNode
- type TreeNodeFilterFunc
- type WalkOption
- func ElidePrefix() WalkOption
- func ElideTreeNodes(f TreeNodeFilterFunc) WalkOption
- func FilterTreeNodes(f TreeNodeFilterFunc) WalkOption
- func MaxDepth(maxDepth uint) WalkOption
- func MaxNodes(maxNodes uint) WalkOption
- func MergePrefix(path ...ScopeID) WalkOption
- func PathPrefix(path ...ScopeID) WalkOption
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Comparable ¶
type Comparable struct {
// The path of the associated SubtreeNode, if one is generated in the
// traversal. This can be used to break comparison ties or to index
// cached weight values.
Path []ScopeID
// The set of TreeNodes of the associated SubtreeNode, if one is generated in
// the traversal.
TreeNodes []TreeNode
}
Comparable describes a comparable argument to CompareFn.
type CompareFn ¶
type CompareFn func(a, b Comparable) (int, error)
CompareFn compares two items, 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 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 TreeNodes corresponding to this SubtreeNode. Only traversals with
// non-empty merge prefix trees (MergePrefix()) or those that elide TreeNodes
// (ElideTreeNodes()) can have more than one TreeNode per SubtreeNode.
TreeNodes []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(root TreeNode, compare CompareFn, opts ...WalkOption) (*SubtreeNode, error)
Walk traverses the tree rooted at the provided root node, returning the root node of the traversed top-down subtree. The traversal algorithm is 'heaviest-first': at each step of the traversal, the 'heaviest' candidate node (as determined by the provided CompareFn) is visited next.
The traversal can be tuned with the provided WalkOptions:
- MaxDepth specifies the maximum depth, past any prefix, to traverse.
- MaxNodes specifies the maximum number of nodes, not including prefix nodes, to traverse.
- ElidePrefix specifies that prefix nodes should be elided from the returned subtree. The root is never elided.
- FilterTreeNodes specifies a TreeNode-filtering function applied to every TreeNode during traversal; TreeNodes for which this function returns false are not visited.
- ElideTreeNodes specifies a TreeNode-filtering function applied to every TreeNode during traversal; TreeNodes for which this function returns true are not included in the returned subtree (but are traversed, and their descendants may appear in it). Specifying ElideTreeNodes may result in returned SubtreeNodes with more than one TreeNode.
- PathPrefix specifies a path from which heaviest-first traversal should begin. This may be provided multiple times to specify a prefix tree: nodes within that tree are visited on the traversal, but non-leaf prefix tree nodes (which are marked with Prefix=true) only visit their children on the prefix tree.
- MergePrefix specifies a path to a TreeNode which should be part of the returned subtree's root node. Like PathPrefix, this may be provided multiple times, defining a merge prefix tree: all leaves in that tree will be unioned into the returned subtree's root, and their descendants will be merged by common path suffix from the merge prefix tree. Specifying more than one MergePrefix may result in returned SubtreeNodes with more than one TreeNode.
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. A tree is by default top-down, but can be explicitly marked as top-down or bottom-up with TopDown() and BottomUp() respectively.
func (*Tree) Node ¶
func (t *Tree) Node(selfMagnitude float64, properties ...util.PropertyUpdate) *Node
Node creates and returns a new root node with the specified magnitude in the tree.
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, but it
// is best for it not to be too expensive.
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 and should be omitted during traversal.
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: TreeNodes for which the provided function returns true are elided, and 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: TreeNodes for which the provided function returns false, and any descendant of such TreeNodes, are not included in the traversal. 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 MergePrefix ¶
func MergePrefix(path ...ScopeID) WalkOption
MergePrefix specifies a path to a TreeNode which should be part of the returned subtree's root node. This may be provided multiple times, defining a merge prefix tree: all leaves in that tree will be unioned into the returned subtree's root, and their descendants will be merged by common path suffix from the merge prefix tree. Specifying more than one MergePrefix may result in returned SubtreeNodes with more than one TreeNode.
func PathPrefix ¶
func PathPrefix(path ...ScopeID) WalkOption
PathPrefix specifies a path from which heaviest-first traversal should begin. This may be provided multiple times to specify a prefix tree: nodes within that tree are visited on the traversal, but non-leaf prefix tree nodes (which are marked with Prefix=true) only visit their children on the prefix tree. Defaults to an empty prefix tree.
Source Files