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

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    This section is empty.

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

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

                                          func (*QueryableGraph) IsMemberOfAny

                                          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

                                            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.

                                                    Source Files