luci: go.chromium.org/luci/lucicfg/graph Index | Files

package graph

import "go.chromium.org/luci/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. Once constructed, a key is an opaque
  label (e.g. there's no way to explore what's inside the key through
  Starlark, to keep the API simple). Examples of keys:
     [core.Bucket("ci")]
     [core.Bucket("ci"), core.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

Structs exposed by this package are not safe for concurrent use without external locking.

Index

Package Files

doc.go graph.go key.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 EdgeRedeclarationError Uses

type EdgeRedeclarationError struct {
    Trace    *builtins.CapturedStacktrace // where it is added second time
    Previous *Edge                        // the previously added edge
}

EdgeRedeclarationError is returned when adding an edge that has exact same end points and a title as some existing edge.

Edges that link same nodes (in same direction) and differ only in title are OK and do not cause this error.

Nodes referenced by the edge 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 (*EdgeRedeclarationError) Backtrace Uses

func (e *EdgeRedeclarationError) Backtrace() string

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

func (*EdgeRedeclarationError) Error Uses

func (e *EdgeRedeclarationError) Error() string

Error is part of 'error' interface.

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={}, 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, kind: string, 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.

Returns an error if there's already an edge between the given nodes with exact same title or the new edge introduces a cycle.

func (*Graph) AddNode Uses

func (g *Graph) AddNode(k *Key, props *starlark.Dict, trace *builtins.CapturedStacktrace) (*Node, error)

AddNode adds a node to the graph or returns an error if such node already exists.

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, kind, orderBy string) ([]*Node, error)

Children returns direct children of a node (given by its key) that have the given kind (based on the last component of their keys).

The order of the result depends on a value of 'orderBy':

'key': nodes are ordered lexicographically by their keys (smaller first).
'exec': nodes are ordered by the order edges to them were defined during
     the execution (earlier first).

Any other value of 'orderBy' causes an error.

Trying to use Children 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) 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) 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) Last Uses

func (k *Key) Last() (kind, id string)

Last returns 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) 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.

Assumes strings don't have zero bytes. No other restrictions.

type Node Uses

type Node struct {
    Key   *Key                         // unique ID of the node
    Props *starlarkstruct.Struct       // struct(...) with frozen properties
    Trace *builtins.CapturedStacktrace // where the node was defined
    // 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) 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 last component of its key. It's not globally unique, but usually "unique enough" to identify the node in error messages.

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.

Package graph imports 8 packages (graph) and is imported by 1 packages. Updated 2018-12-14. Refresh now. Tools for package owners.