Documentation
¶
Overview ¶
Package graph implements a DAG used internally to represent config objects.
All entities in the LUCI config are represented by nodes in a graph. Nodes are linked with directional edges. Cycles are forbidden. Each edge is annotated with a name of the relation that added it (e.g. "triggered_by"). There can be multiple edges between a given pair of nodes, e.g. "triggered_by" and "triggers" edges between a builder(...) and a trigger(...). When detecting cycles or traversing the graph, edge annotations are not considered. They are used only to improve error messages when reporting dangling edges (e.g. Builder X references undefined trigger T via "triggered_by").
Each node:
- Has a unique identifier, called key. A key is a list of (string kind, string id) pairs. Examples of keys: [luci.bucket("ci")] [luci.bucket("ci"), luci.builder("infra-builder")]
- Has a props dict of arbitrary properties (all keys are strings, values are arbitrary).
- Has a captured stack trace of where in Starlark it was defined (for error messages).
- Is immutable.
Key kinds support special syntax to express special sorts of kinds:
- '_...' kinds are "private". When printing nodes names, (kind, id) pairs where the kind is private are silently skipped.
- '@...' kinds are "namespace kinds". There may be at most one namespace kind in a key, and it must come first. When printing node names, the namespace ID is conveyed by "<id>:" prefix (instead of "<id>/"). If <id> is empty, the namespace qualifier is completely omitted.
Structs exposed by this package are not safe for concurrent use without external locking.
Index ¶
- Variables
- type CycleError
- type DanglingEdgeError
- type Edge
- type Graph
- func (g *Graph) AddEdge(parent, child *Key, title string, trace *builtins.CapturedStacktrace) error
- func (g *Graph) AddNode(k *Key, props *starlark.Dict, idempotent bool, ...) error
- func (g *Graph) Attr(name string) (starlark.Value, error)
- func (g *Graph) AttrNames() []string
- func (g *Graph) Children(parent *Key, orderBy string) ([]*Node, error)
- func (g *Graph) Descendants(root *Key, orderBy, topology string, visitor Visitor) ([]*Node, error)
- func (g *Graph) Finalize() (errs errors.MultiError)
- func (g *Graph) Freeze()
- func (g *Graph) Hash() (uint32, error)
- func (g *Graph) Node(k *Key) (*Node, error)
- func (g *Graph) Parents(child *Key, orderBy string) ([]*Node, error)
- func (g *Graph) SortNodes(nodes []*Node, orderBy string) error
- func (g *Graph) String() string
- func (g *Graph) Truth() starlark.Bool
- func (g *Graph) Type() string
- type Key
- func (k *Key) Attr(name string) (starlark.Value, error)
- func (k *Key) AttrNames() []string
- func (k *Key) Container() *Key
- func (k *Key) Freeze()
- func (k *Key) Hash() (uint32, error)
- func (k *Key) ID() string
- func (k *Key) Kind() string
- func (k *Key) Less(an *Key) bool
- func (k *Key) Root() *Key
- func (k *Key) String() string
- func (k *Key) Truth() starlark.Bool
- func (k *Key) Type() string
- type KeySet
- type Node
- func (n *Node) Attr(name string) (starlark.Value, error)
- func (n *Node) AttrNames() []string
- func (n *Node) BelongsTo(g *Graph) bool
- func (n *Node) Declared() bool
- func (n *Node) Freeze()
- func (n *Node) Hash() (uint32, error)
- func (n *Node) String() string
- func (n *Node) Truth() starlark.Bool
- func (n *Node) Type() string
- type NodeRedeclarationError
- type Visitor
Constants ¶
This section is empty.
Variables ¶
var ( // ErrFinalized is returned by Graph methods that modify the graph when they // are used on a finalized graph. ErrFinalized = errors.New("cannot modify a finalized graph") // ErrNotFinalized is returned by Graph traversal/query methods when they are // used with a non-finalized graph. ErrNotFinalized = errors.New("cannot query a graph under construction") )
Functions ¶
This section is empty.
Types ¶
type CycleError ¶
type CycleError struct {
Trace *builtins.CapturedStacktrace // where the edge is being added
Edge *Edge // an edge being added
Path []*Edge // the rest of the cycle
}
CycleError is returned when adding an edge that introduces a cycle.
Nodes referenced by edges may not be fully declared yet (i.e. they may not yet have properties or trace associated with them). They do have valid keys though.
func (*CycleError) Backtrace ¶
func (e *CycleError) Backtrace() string
Backtrace returns an error message with a backtrace where it happened.
type DanglingEdgeError ¶
type DanglingEdgeError struct {
Edge *Edge
}
DanglingEdgeError is returned by Finalize if a graph has an edge whose parent or child (or both) haven't been declared by AddNode.
Use Edge.(Parent|Child).Declared() to figure out which end is not defined.
func (*DanglingEdgeError) Backtrace ¶
func (e *DanglingEdgeError) Backtrace() string
Backtrace returns an error message with a backtrace where it happened.
func (*DanglingEdgeError) Error ¶
func (e *DanglingEdgeError) Error() string
Error is part of 'error' interface.
type Edge ¶
type Edge struct {
Parent *Node
Child *Node
Title string // arbitrary title for error messages
Trace *builtins.CapturedStacktrace // where it was defined
}
Edge is a single 'Parent -> Child' edge in the graph.
type Graph ¶
type Graph struct {
KeySet
// contains filtered or unexported fields
}
Graph is a DAG of keyed nodes.
It is initially in "under construction" state, in which callers can use AddNode and AddEdge (in any order) to build the graph, but can't yet query it.
Once the construction is complete, the graph should be finalized via Finalize() call, which checks there are no dangling edges and freezes the graph (so AddNode/AddEdge return errors), making it queryable.
Graph implements starlark.HasAttrs interface and have the following methods:
- key(kind1: string, id1: string, kind2: string, id2: string, ...): graph.key
- add_node(key: graph.key, props={}, idempotent=False, trace=stacktrace()): graph.node
- add_edge(parent: graph.Key, child: graph.Key, title=”, trace=stacktrace())
- finalize(): []string
- node(key: graph.key): graph.node
- children(parent: graph.key, order_by='key'): []graph.node
- descendants(root: graph.key, callback=None, order_by='key', topology='breadth'): []graph.node
- parents(child: graph.key, order_by='key'): []graph.node
- sorted_nodes(nodes: iterable<graph.node>, order_by='key'): []graph.node
func (*Graph) AddEdge ¶
AddEdge adds an edge to the graph.
Trying to use AddEdge after the graph has been finalized is an error.
Neither of the nodes have to exist yet: it is OK to declare nodes and edges in arbitrary order as long as at the end of the graph construction (when it is finalized) the graph is complete.
It is OK to add the same edge (with the same title) more than once. Only the trace of the first definition is recorded.
Returns an error if the new edge introduces a cycle.
func (*Graph) AddNode ¶
func (g *Graph) AddNode(k *Key, props *starlark.Dict, idempotent bool, trace *builtins.CapturedStacktrace) error
AddNode adds a node to the graph.
If such node already exists, either returns an error right away (if 'idempotent' is false), or verifies the existing node has also been marked as idempotent and has exact same props dict as being passed here.
Trying to use AddNode after the graph has been finalized is an error.
Freezes props.values() as a side effect.
func (*Graph) Children ¶
Children returns direct children of a node (given by its key).
The order of the result depends on a value of 'orderBy':
'key': nodes are ordered lexicographically by their keys (smaller first).
'def': nodes are ordered by the order edges to them were defined during
the execution (earlier first).
Any other value of 'orderBy' causes an error.
A missing node is considered to have no children.
Trying to use Children before the graph has been finalized is an error.
func (*Graph) Descendants ¶
Descendants recursively visits 'root' and all its children, in breadth or depth first order.
Returns the list of all visited nodes, in order they were visited, including 'root' itself. If 'root' is missing, returns an empty list.
The order of enumeration of direct children of a node depends on a value of 'orderBy':
'key': nodes are ordered lexicographically by their keys (smaller first).
'def': nodes are ordered by the order edges to them were defined during
the execution (earlier first).
'~' in front (i.e. ~key' and '~def') means "reverse order".
Any other value of 'orderBy' causes an error.
Each node is visited only once, even if it is reachable through multiple paths. Note that the graph has no cycles (by construction).
The visitor callback (if not nil) is called for each visited node. It decides what children to visit next. The callback always sees all children of the node, even if some of them (or all) have already been visited. Visited nodes will be skipped even if the visitor returns them.
Trying to use Descendants before the graph has been finalized is an error.
func (*Graph) Finalize ¶
func (g *Graph) Finalize() (errs errors.MultiError)
Finalize finishes the graph construction by verifying there are no "dangling" edges: all edges ever added by AddEdge should connect nodes that were at some point defined by AddNode.
Finalizing an already finalized graph is not an error.
A finalized graph is immutable (and frozen in Starlark sense): all subsequent calls to AddNode/AddEdge return an error. Conversely, freezing the graph via Freeze() finalizes it, panicking if the finalization fails. Users of Graph are expected to finalize the graph themselves (checking errors) before Starlark tries to freeze it.
Once finalized, the graph becomes queryable.
func (*Graph) Freeze ¶
func (g *Graph) Freeze()
Freeze is a part of starlark.Value interface.
It finalizes the graph, panicking on errors. Users of Graph are expected to finalize the graph themselves (checking errors) before Starlark tries to freeze it.
func (*Graph) Node ¶
Node returns a node by the key or (nil, nil) if there's no such node.
Trying to use Node before the graph has been finalized is an error.
func (*Graph) Parents ¶
Parents returns direct parents of a node (given by its key).
The order of the result depends on a value of 'orderBy':
'key': nodes are ordered lexicographically by their keys (smaller first).
'def': nodes are ordered by the order edges to them were defined during
the execution (earlier first).
Any other value of 'orderBy' causes an error.
A missing node is considered to have no parents.
Trying to use Parents before the graph has been finalized is an error.
func (*Graph) SortNodes ¶
SortNodes sorts a slice of nodes of this graph in-place.
The order of the result depends on the value of 'orderBy':
'key': nodes are ordered lexicographically by their keys (smaller first). 'def': nodes are ordered by the order they were defined in the graph.
Any other value of 'orderBy' causes an error.
type Key ¶
type Key struct {
// contains filtered or unexported fields
}
Key is a unique identifier of a node in the graph.
It is constructed from a series of (kind: string, id: string) pairs, and once constructed it acts as an opaque label, not examinable through Starlark.
From the Starlark side it looks like a ref-like hashable object: keys can be compared to each other via == and !=, and can be used in dicts and sets.
Keys live in a KeySet, which represents a universe of all keys and it is also responsible for their construction. Keys from different key sets (even if they represent same path) are considered not equal and shouldn't be used together.
func (*Key) Container ¶
Container returns a key with all (kind, id) pairs of this key, except the last one, or nil if this key has only one (kind, id) pair.
Usually it represents a container that holds an object represented by the this key.
func (*Key) ID ¶
ID returns id of the last (kind, id) pair in the key, which usually holds a user-friendly name of an object this key represents.
func (*Key) Kind ¶
Kind returns kind of the last (kind, id) pair in the key, which usually defines what sort of an object this key represents.
func (*Key) String ¶
String is part of starlark.Value interface.
Returns [kind1("id1"), kind2("id2"), ...]. Must not be parsed, only for logging.
type KeySet ¶
type KeySet struct {
// contains filtered or unexported fields
}
KeySet is a set of all keys ever defined in a graph.
Each key is a singleton object: asking for the same key twice returns exact same *Key object. This simplifies comparison of keys and using keys as, well, keys in a map.
type Node ¶
type Node struct {
Key *Key // unique ID of the node
Index int // index of the node in the graph
Props *starlarkstruct.Struct // struct(...) with frozen properties
Trace *builtins.CapturedStacktrace // where the node was defined
Idempotent bool // true if it's fine to redeclare this node
// contains filtered or unexported fields
}
Node is an element of the graph.
func (*Node) Declared ¶
Declared is true if the node was fully defined via AddNode and false if it was only "predeclared" by being referenced in some edge (via AddEdge).
In a finalized graph there are no dangling edges: all nodes are guaranteed to be declared.
func (*Node) String ¶
String is a part of starlark.Value interface.
Returns a node title as derived from the kind of last component of its key and IDs of all key components. It's not 1-to-1 mapping to the full info in the key, but usually good enough to identify the node in error messages.
Key components with kinds that start with '_' are skipped.
If the kind of the first key component starts with '@' and its ID ("<id>") is not empty, the final string will have a form 'kind("<id>:a/b/c")'.
type NodeRedeclarationError ¶
type NodeRedeclarationError struct {
Trace *builtins.CapturedStacktrace // where it is added second time
Previous *Node // the previously added node
}
NodeRedeclarationError is returned when a adding an existing node.
func (*NodeRedeclarationError) Backtrace ¶
func (e *NodeRedeclarationError) Backtrace() string
Backtrace returns an error message with a backtrace where it happened.
func (*NodeRedeclarationError) Error ¶
func (e *NodeRedeclarationError) Error() string
Error is part of 'error' interface.
Source Files