graph

Documentation

Overview

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

• type Graph
  • func Build(groups []*protocol.AuthGroup) (*Graph, error)
  • func (g *Graph) Ancestors(n NodeIndex) NodeSet
  • func (g *Graph) Descendants(n NodeIndex) NodeSet
  • func (g *Graph) NodeByName(name string) *Node
  • func (g *Graph) ToQueryable() (*QueryableGraph, error)
  • func (g *Graph) Visit(ns NodeSet, cb func(n *Node) error) error
• type Node
• type NodeIndex
• type NodeSet
  • func (ns NodeSet) Add(n NodeIndex)
  • func (ns NodeSet) Sort() SortedNodeSet
  • func (ns NodeSet) Update(another NodeSet)
• type QueryableGraph
  • func BuildQueryable(groups []*protocol.AuthGroup) (*QueryableGraph, error)
  • func (g *QueryableGraph) IsMember(ident identity.Identity, group string) bool
• type SortedNodeSet
  • func (ns SortedNodeSet) Has(idx NodeIndex) bool
  • func (ns SortedNodeSet) MapKey() string

Types

type Graph

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

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

Build constructs the graph from a list of AuthGroup messages.

func (*Graph) Ancestors

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

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

func (*Graph) Descendants

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

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

func (*Graph) NodeByName

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

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

func (*Graph) ToQueryable

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

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

func (*Graph) Visit

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

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

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

type NodeSet map[NodeIndex]struct{}

NodeSet is a set of nodes referred by their indexes.

func (NodeSet) Add

func (ns NodeSet) Add(n NodeIndex)

Add adds node 'n' to 'ns'.

func (NodeSet) Sort

func (ns NodeSet) Sort() SortedNodeSet

Sort converts the NodeSet to SortedNodeSet.

func (NodeSet) Update

func (ns NodeSet) Update(another NodeSet)

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

type QueryableGraph

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

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

BuildQueryable constructs the queryable graph from a list of AuthGroups.

func (*QueryableGraph) IsMember

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

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

type SortedNodeSet

type SortedNodeSet []NodeIndex

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

func (SortedNodeSet) Has

func (ns SortedNodeSet) Has(idx NodeIndex) bool

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

func (SortedNodeSet) MapKey

func (ns SortedNodeSet) MapKey() string

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