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 IsMemberResult
• type MembershipsQueryCache
  • func (q *MembershipsQueryCache) IsMemberOfAny(groups SortedNodeSet) bool
• type Node
• type NodeIndex
• type NodeSet
  • func (ns NodeSet) Add(n NodeIndex)
  • func (ns NodeSet) Sort() SortedNodeSet
  • func (ns NodeSet) Update(another NodeSet)
• type NodeSetDedupper
  • func (nsd NodeSetDedupper) Dedup(ns NodeSet) SortedNodeSet
• type QueryableGraph
  • func BuildQueryable(groups []*protocol.AuthGroup) (*QueryableGraph, error)
  • func (g *QueryableGraph) GroupIndex(group string) (idx NodeIndex, ok bool)
  • func (g *QueryableGraph) IsMember(ident identity.Identity, group string) IsMemberResult
  • func (g *QueryableGraph) MembershipsQueryCache(ident identity.Identity) MembershipsQueryCache
• type SortedNodeSet
  • func (ns SortedNodeSet) Has(idx NodeIndex) bool
  • func (a SortedNodeSet) Intersects(b SortedNodeSet) 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 IsMemberResult

type IsMemberResult byte

IsMemberResult is the possible results for a 'ident in group' check implemented by QueryableGraph.IsMember.

const (
	IdentIsNotMember IsMemberResult = iota
	IdentIsMember
	GroupIsUnknown
)

type MembershipsQueryCache

type MembershipsQueryCache struct {
	// Identity whose memberships are being queried.
	Identity identity.Identity
	// contains filtered or unexported fields
}

MembershipsQueryCache can be used to answer a bunch of IsMemberOfAny questions, caching some internal state in-between them.

func (*MembershipsQueryCache) IsMemberOfAny

func (q *MembershipsQueryCache) IsMemberOfAny(groups SortedNodeSet) bool

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

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

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 NodeSetDedupper

type NodeSetDedupper map[string]SortedNodeSet

NodeSetDedupper helps to find duplicate NodeSet's.

func (NodeSetDedupper) Dedup

func (nsd NodeSetDedupper) Dedup(ns NodeSet) SortedNodeSet

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

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) GroupIndex

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

GroupIndex returns a NodeIndex of the group given its name.

func (*QueryableGraph) IsMember

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

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

func (*QueryableGraph) MembershipsQueryCache

func (g *QueryableGraph) MembershipsQueryCache(ident identity.Identity) MembershipsQueryCache

MembershipsQueryCache prepares a query for memberships of the given identity.

This query can be used to answer a bunch of IsMemberOfAny questions, caching some internal state in-between them.

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) Intersects

func (a SortedNodeSet) Intersects(b SortedNodeSet) bool

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

func (SortedNodeSet) MapKey

func (ns SortedNodeSet) MapKey() string

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