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.