luci: go.chromium.org/luci/server/auth/authdb/internal/graph Index | Files

package graph

import "go.chromium.org/luci/server/auth/authdb/internal/graph"

Package graph implements handling of the groups graph.

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

Index

Package Files

graph.go

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 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) IsMember Uses

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

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

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) 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 2 packages. Updated 2019-12-14. Refresh now. Tools for package owners.