graph

package
v0.0.0-...-add0f8d Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 22, 2024 License: Apache-2.0 Imports: 9 Imported by: 3

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

Constants

This section is empty.

Variables

View Source
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.

func (*CycleError) Error

func (e *CycleError) Error() string

Error is part of 'error' interface.

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

func (g *Graph) AddEdge(parent, child *Key, title string, trace *builtins.CapturedStacktrace) error

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) Attr

func (g *Graph) Attr(name string) (starlark.Value, error)

Attr is a part of starlark.HasAttrs interface.

func (*Graph) AttrNames

func (g *Graph) AttrNames() []string

AttrNames is a part of starlark.HasAttrs interface.

func (*Graph) Children

func (g *Graph) Children(parent *Key, orderBy string) ([]*Node, error)

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

func (g *Graph) Descendants(root *Key, orderBy, topology string, visitor Visitor) ([]*Node, error)

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) Hash

func (g *Graph) Hash() (uint32, error)

Hash is a part of starlark.Value interface.

func (*Graph) Node

func (g *Graph) Node(k *Key) (*Node, error)

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

func (g *Graph) Parents(child *Key, orderBy string) ([]*Node, error)

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

func (g *Graph) SortNodes(nodes []*Node, orderBy string) error

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.

func (*Graph) String

func (g *Graph) String() string

String is a part of starlark.Value interface

func (*Graph) Truth

func (g *Graph) Truth() starlark.Bool

Truth is a part of starlark.Value interface.

func (*Graph) Type

func (g *Graph) Type() string

Type is a part of starlark.Value interface.

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) Attr

func (k *Key) Attr(name string) (starlark.Value, error)

Attr is a part of starlark.HasAttrs interface.

func (*Key) AttrNames

func (k *Key) AttrNames() []string

AttrNames is a part of starlark.HasAttrs interface.

func (*Key) Container

func (k *Key) Container() *Key

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) Freeze

func (k *Key) Freeze()

Freeze is a part of starlark.Value interface.

func (*Key) Hash

func (k *Key) Hash() (uint32, error)

Hash is a part of starlark.Value interface.

func (*Key) ID

func (k *Key) ID() string

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

func (k *Key) Kind() string

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) Less

func (k *Key) Less(an *Key) bool

Less returns true if this key is lexicographically before another key.

func (*Key) Root

func (k *Key) Root() *Key

Root returns a key with the first (kind, id) pair of this key.

func (*Key) String

func (k *Key) String() string

String is part of starlark.Value interface.

Returns [kind1("id1"), kind2("id2"), ...]. Must not be parsed, only for logging.

func (*Key) Truth

func (k *Key) Truth() starlark.Bool

Truth is a part of starlark.Value interface.

func (*Key) Type

func (k *Key) Type() string

Type is a part of starlark.Value interface.

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.

func (*KeySet) Key

func (k *KeySet) Key(pairs ...string) (*Key, error)

Key returns a *Key given a list of (kind, id) pairs.

There can be at most one kind that starts with '@...' (aka "namespace kind"), and it must come first (if present).

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) Attr

func (n *Node) Attr(name string) (starlark.Value, error)

Attr is a part of starlark.HasAttrs interface.

func (*Node) AttrNames

func (n *Node) AttrNames() []string

AttrNames is a part of starlark.HasAttrs interface.

func (*Node) BelongsTo

func (n *Node) BelongsTo(g *Graph) bool

BelongsTo returns true if the node was declared in the given graph.

func (*Node) Declared

func (n *Node) Declared() bool

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) Freeze

func (n *Node) Freeze()

Freeze is a part of starlark.Value interface.

func (*Node) Hash

func (n *Node) Hash() (uint32, error)

Hash is a part of starlark.Value interface.

func (*Node) String

func (n *Node) String() 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")'.

func (*Node) Truth

func (n *Node) Truth() starlark.Bool

Truth is a part of starlark.Value interface.

func (*Node) Type

func (n *Node) Type() string

Type is a part of starlark.Value interface.

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.

type Visitor

type Visitor func(n *Node, next []*Node) ([]*Node, error)

Visitor visits a node, looks at next possible candidates for a visit and returns ones that it really wants to visit.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL