luci: Index | Files

package graph

import ""

Package graph implements handling of the groups graph.

Such graphs are built from list of AuthGroup proto messages that reference each other by name.


Package Files


type Graph Uses

type Graph struct {
    Nodes       []Node               // all graph nodes
    NodesByName map[string]NodeIndex // name => index in Nodes

Graph is a static group graph optimized for traversals.

Not safe for concurrent use.

func Build Uses

func Build(groups []*protocol.AuthGroup) (*Graph, error)

Build constructs the graph from a list of AuthGroup messages.

func (*Graph) Ancestors Uses

func (g *Graph) Ancestors(n NodeIndex) NodeSet

Ancestors returns a set with 'n' and all groups that include it.

func (*Graph) Descendants Uses

func (g *Graph) Descendants(n NodeIndex) NodeSet

Descendants returns a set with 'n' and all groups it includes.

func (*Graph) NodeByName Uses

func (g *Graph) NodeByName(name string) *Node

NodeByName returns a node given its name or nil if not found.

func (*Graph) ToQueryable Uses

func (g *Graph) ToQueryable() (*QueryableGraph, error)

ToQueryable converts the graph to a form optimized for IsMember queries.

func (*Graph) Visit Uses

func (g *Graph) Visit(ns NodeSet, cb func(n *Node) error) error

Visit passes each node in the set to the callback (in arbitrary order).

Stops on a first error returning it as is. Panics if 'ns' has invalid indexes.

type Node Uses

type Node struct {
    *protocol.AuthGroup // the original group proto

    Nested  []NodeIndex // directly nested groups
    Parents []NodeIndex // direct parent (nesting) groups
    Index   NodeIndex   // index of this node within the graph's list of nodes
    // contains filtered or unexported fields

Node is a node in a group graph.

type NodeIndex Uses

type NodeIndex uint16

NodeIndex is an index of a node within graph's list of nodes.

Used essentially as a pointer that occupies x4 less memory than the real one.

Note: when changing the type, make sure to also change SortedNodeSet.MapKey and replace math.MaxUint16 in Build(...) with another bound.

type NodeSet Uses

type NodeSet map[NodeIndex]struct{}

NodeSet is a set of nodes referred by their indexes.

func (NodeSet) Add Uses

func (ns NodeSet) Add(n NodeIndex)

Add adds node 'n' to 'ns'.

func (NodeSet) Sort Uses

func (ns NodeSet) Sort() SortedNodeSet

Sort converts the NodeSet to SortedNodeSet.

func (NodeSet) Update Uses

func (ns NodeSet) Update(another NodeSet)

Update adds all nodes in 'another' to 'ns'.

type NodeSetDedupper Uses

type NodeSetDedupper map[string]SortedNodeSet

NodeSetDedupper helps to find duplicate NodeSet's.

func (NodeSetDedupper) Dedup Uses

func (nsd NodeSetDedupper) Dedup(ns NodeSet) SortedNodeSet

Dedup returns a sorted version of 'ns' (perhaps reusing an existing one).

type QueryableGraph Uses

type QueryableGraph struct {
    // contains filtered or unexported fields

QueryableGraph is a processed Graph optimized for IsMember queries and low memory footprint.

It is built from Graph via ToQueryable method. It is static once constructed and can be queried concurrently.

TODO(vadimsh): Optimize 'memberships' to take less memory. It turns out string keys are quite expensive in terms of memory: a totally empty preallocated map[identity.Identity]SortedNodeSet (with empty keys!) is already *half* the size of the fully populated one.

func BuildQueryable Uses

func BuildQueryable(groups []*protocol.AuthGroup) (*QueryableGraph, error)

BuildQueryable constructs the queryable graph from a list of AuthGroups.

func (*QueryableGraph) GroupIndex Uses

func (g *QueryableGraph) GroupIndex(group string) (idx NodeIndex, ok bool)

GroupIndex returns a NodeIndex of the group given its name.

func (*QueryableGraph) IsMember Uses

func (g *QueryableGraph) IsMember(ident identity.Identity, group string) bool

IsMember returns true if the given identity belongs to the given group.

func (*QueryableGraph) IsMemberOfAny Uses

func (g *QueryableGraph) IsMemberOfAny(ident identity.Identity, groups SortedNodeSet) bool

IsMemberOfAny returns true if the given identity belongs to any of the given groups.

Groups are given as a sorted slice of group indexes obtained via GroupIndex.

type SortedNodeSet Uses

type SortedNodeSet []NodeIndex

SortedNodeSet is a compact representation of NodeSet as a sorted slice.

func (SortedNodeSet) Has Uses

func (ns SortedNodeSet) Has(idx NodeIndex) bool

Has is true if 'idx' is in 'ns'.

func (SortedNodeSet) Intersects Uses

func (a SortedNodeSet) Intersects(b SortedNodeSet) bool

Intersects is true if 'a' and 'b' have common elements.

func (SortedNodeSet) MapKey Uses

func (ns SortedNodeSet) MapKey() string

MapKey converts 'ns' to a string that can be used as a map key.

Package graph imports 7 packages (graph) and is imported by 3 packages. Updated 2020-12-01. Refresh now. Tools for package owners.