luci-go: github.com/luci/luci-go/lucicfg/graph Index | Files

package graph

import "github.com/luci/luci-go/lucicfg/graph"

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

Package Files

doc.go graph.go key.go keyset.go node.go

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

type CycleError Uses

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 Uses

func (e *CycleError) Backtrace() string

Backtrace returns an error message with a backtrace where it happened.

func (*CycleError) Error Uses

func (e *CycleError) Error() string

Error is part of 'error' interface.

type DanglingEdgeError Uses

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 Uses

func (e *DanglingEdgeError) Backtrace() string

Backtrace returns an error message with a backtrace where it happened.

func (*DanglingEdgeError) Error Uses

func (e *DanglingEdgeError) Error() string

Error is part of 'error' interface.

type Edge Uses

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 Uses

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 Uses

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 Uses

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 Uses

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

Attr is a part of starlark.HasAttrs interface.

func (*Graph) AttrNames Uses

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

AttrNames is a part of starlark.HasAttrs interface.

func (*Graph) Children Uses

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 Uses

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 Uses

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 Uses

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 Uses

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

Hash is a part of starlark.Value interface.

func (*Graph) Node Uses

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 Uses

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 Uses

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 Uses

func (g *Graph) String() string

String is a part of starlark.Value interface

func (*Graph) Truth Uses

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

Truth is a part of starlark.Value interface.

func (*Graph) Type Uses

func (g *Graph) Type() string

Type is a part of starlark.Value interface.

type Key Uses

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 Uses

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

Attr is a part of starlark.HasAttrs interface.

func (*Key) AttrNames Uses

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

AttrNames is a part of starlark.HasAttrs interface.

func (*Key) Container Uses

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 Uses

func (k *Key) Freeze()

Freeze is a part of starlark.Value interface.

func (*Key) Hash Uses

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

Hash is a part of starlark.Value interface.

func (*Key) ID Uses

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 Uses

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 Uses

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

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

func (*Key) Root Uses

func (k *Key) Root() *Key

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

func (*Key) String Uses

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 Uses

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

Truth is a part of starlark.Value interface.

func (*Key) Type Uses

func (k *Key) Type() string

Type is a part of starlark.Value interface.

type KeySet Uses

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 Uses

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 Uses

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 Uses

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

Attr is a part of starlark.HasAttrs interface.

func (*Node) AttrNames Uses

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

AttrNames is a part of starlark.HasAttrs interface.

func (*Node) BelongsTo Uses

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

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

func (*Node) Declared Uses

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 Uses

func (n *Node) Freeze()

Freeze is a part of starlark.Value interface.

func (*Node) Hash Uses

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

Hash is a part of starlark.Value interface.

func (*Node) String Uses

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 Uses

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

Truth is a part of starlark.Value interface.

func (*Node) Type Uses

func (n *Node) Type() string

Type is a part of starlark.Value interface.

type NodeRedeclarationError Uses

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 Uses

func (e *NodeRedeclarationError) Backtrace() string

Backtrace returns an error message with a backtrace where it happened.

func (*NodeRedeclarationError) Error Uses

func (e *NodeRedeclarationError) Error() string

Error is part of 'error' interface.

type Visitor Uses

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.

Package graph imports 9 packages (graph). Updated 2019-10-29. Refresh now. Tools for package owners.