expand

package
v0.6.13 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 31, 2025 License: Apache-2.0 Imports: 16 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var ErrMaxDepthExceeded = errors.New("max depth exceeded")

ErrMaxDepthExceeded is returned when the expansion graph exceeds the maximum allowed depth.

View Source 
var (
	ErrNoEntitlement = errors.New("no entitlement found")
)

Functions

func PutGrantsInChunks added in v0.6.9 

func PutGrantsInChunks(ctx context.Context, store ExpanderStore, grants []*v2.Grant, minChunkSize int) ([]*v2.Grant, error)

PutGrantsInChunks accumulates grants until the buffer exceeds minChunkSize, then writes all grants to the store at once.

Types

type Edge 

type Edge struct {
	EdgeID          int      `json:"id"`
	SourceID        int      `json:"sid"`
	DestinationID   int      `json:"did"`
	IsExpanded      bool     `json:"e"`
	IsShallow       bool     `json:"s"`
	ResourceTypeIDs []string `json:"rtids"`
}

func (*Edge) Str 

func (edge *Edge) Str() string

type EntitlementGraph 

type EntitlementGraph struct {
	NextNodeID            int                       `json:"next_node_id"`            // Automatically incremented so that each node has a unique ID.
	NextEdgeID            int                       `json:"next_edge_id"`            // Automatically incremented so that each edge has a unique ID.
	Nodes                 map[int]Node              `json:"nodes"`                   // The mapping of all node IDs to nodes.
	EntitlementsToNodes   map[string]int            `json:"entitlements_to_nodes"`   // Internal mapping of entitlements to nodes for quicker lookup.
	SourcesToDestinations map[int]map[int]int       `json:"sources_to_destinations"` // Internal mapping of outgoing edges by node ID.
	DestinationsToSources map[int]map[int]int       `json:"destinations_to_sources"` // Internal mapping of incoming edges by node ID.
	Edges                 map[int]Edge              `json:"edges"`                   // Adjacency list. Source node -> descendant node
	Loaded                bool                      `json:"loaded"`
	Depth                 int                       `json:"depth"`
	Actions               []*EntitlementGraphAction `json:"actions"`
	HasNoCycles           bool                      `json:"has_no_cycles"`
}

EntitlementGraph - a directed graph representing the relationships between entitlements and grants. This data structure is naïve to any business logic. Note that the data of each Node is actually a list or IDs, not a single ID. This is because the graph can have cycles, and we address them by reducing _all_ nodes in a cycle into a single node.

func NewEntitlementGraph 

func NewEntitlementGraph(_ context.Context) *EntitlementGraph

func (*EntitlementGraph) AddEdge 

func (g *EntitlementGraph) AddEdge(
	ctx context.Context,
	srcEntitlementID string,
	dstEntitlementID string,
	isShallow bool,
	resourceTypeIDs []string,
) error

AddEdge - given two entitlements, add an edge with resourceTypeIDs.

func (*EntitlementGraph) AddEntitlement 

func (g *EntitlementGraph) AddEntitlement(entitlement *v2.Entitlement)

AddEntitlement - add an entitlement's ID as an unconnected node in the graph.

func (*EntitlementGraph) ComputeCyclicComponents added in v0.3.49 

func (g *EntitlementGraph) ComputeCyclicComponents(ctx context.Context) ([][]int, *scc.Metrics)

ComputeCyclicComponents runs SCC once and returns only cyclic components. A component is cyclic if len>1 or a singleton with a self-loop.

func (*EntitlementGraph) DeleteEdge added in v0.2.64 

func (g *EntitlementGraph) DeleteEdge(ctx context.Context, srcEntitlementID string, dstEntitlementID string) error

func (*EntitlementGraph) FixCycles 

func (g *EntitlementGraph) FixCycles(ctx context.Context) error

func (*EntitlementGraph) FixCyclesFromComponents added in v0.3.49 

func (g *EntitlementGraph) FixCyclesFromComponents(ctx context.Context, cyclic [][]int) error

FixCyclesFromComponents merges all provided cyclic components in one pass.

func (*EntitlementGraph) ForEachEdgeFrom added in v0.3.51 

func (g *EntitlementGraph) ForEachEdgeFrom(src int, fn func(dst int) bool)

ForEachEdgeFrom implements scc.Source iteration of outgoing edges for src. It enumerates unique destination node IDs.

func (*EntitlementGraph) ForEachNode added in v0.3.51 

func (g *EntitlementGraph) ForEachNode(fn func(id int) bool)

ForEachNode implements scc.Source iteration over nodes (including isolated nodes). It does not import scc; matching the method names/signatures is sufficient.

func (*EntitlementGraph) GetDescendantEntitlements 

func (g *EntitlementGraph) GetDescendantEntitlements(entitlementID string) map[string]*Edge

GetDescendantEntitlements given an entitlementID, return a mapping of child entitlementIDs to edge data.

func (*EntitlementGraph) GetEntitlements 

func (g *EntitlementGraph) GetEntitlements() []string

GetEntitlements returns a combined list of _all_ entitlements from all nodes.

func (*EntitlementGraph) GetExpandableDescendantEntitlements added in v0.6.6 

func (g *EntitlementGraph) GetExpandableDescendantEntitlements(ctx context.Context, entitlementID string) iter.Seq2[string, *Edge]

func (*EntitlementGraph) GetExpandableEntitlements added in v0.6.6 

func (g *EntitlementGraph) GetExpandableEntitlements(ctx context.Context) iter.Seq[string]

func (*EntitlementGraph) GetFirstCycle added in v0.2.0 

func (g *EntitlementGraph) GetFirstCycle(ctx context.Context) []int

GetFirstCycle given an entitlements graph, return a cycle by node ID if it exists. Returns nil if no cycle exists. If there is a single node pointing to itself, that will count as a cycle.

func (*EntitlementGraph) GetNode 

func (g *EntitlementGraph) GetNode(entitlementID string) *Node

GetNode - returns the node that contains the given `entitlementID`.

func (*EntitlementGraph) HasCycles added in v0.3.49 

func (g *EntitlementGraph) HasCycles(ctx context.Context) bool

HasCycles returns true if the graph contains any cycle.

func (*EntitlementGraph) HasEntitlement 

func (g *EntitlementGraph) HasEntitlement(entitlementID string) bool

func (*EntitlementGraph) HasUnexpandedAncestors 

func (g *EntitlementGraph) HasUnexpandedAncestors(entitlementID string) bool

HasUnexpandedAncestors returns true if the given entitlement has ancestors that have not been expanded yet.

func (*EntitlementGraph) IsEntitlementExpanded 

func (g *EntitlementGraph) IsEntitlementExpanded(entitlementID string) bool

IsEntitlementExpanded returns true if all the outgoing edges for the given entitlement have been expanded.

func (*EntitlementGraph) IsExpanded 

func (g *EntitlementGraph) IsExpanded() bool

IsExpanded returns true if all entitlements in the graph have been expanded.

func (*EntitlementGraph) MarkEdgeExpanded 

func (g *EntitlementGraph) MarkEdgeExpanded(sourceEntitlementID string, descendantEntitlementID string)

MarkEdgeExpanded given source and destination entitlements, mark the edge between them as "expanded".

func (*EntitlementGraph) Str 

func (g *EntitlementGraph) Str() string

Str lists every `node` line by line followed by every `edge`. Useful for debugging.

func (*EntitlementGraph) Validate 

func (g *EntitlementGraph) Validate() error

Validate checks every node and edge and returns an error if the graph is not valid.

type EntitlementGraphAction 

type EntitlementGraphAction struct {
	SourceEntitlementID     string   `json:"sid"`
	DescendantEntitlementID string   `json:"did"`
	Shallow                 bool     `json:"s"`
	ResourceTypeIDs         []string `json:"rtids"`
	PageToken               string   `json:"pt"`
}

type Expander added in v0.6.7 

type Expander struct {
	// contains filtered or unexported fields
}

Expander handles the grant expansion algorithm. It can be used standalone for testing or called from the syncer.

func NewExpander added in v0.6.7 

func NewExpander(store ExpanderStore, graph *EntitlementGraph) *Expander

NewExpander creates a new Expander with the given store and graph.

func (*Expander) Graph added in v0.6.7 

func (e *Expander) Graph() *EntitlementGraph

Graph returns the entitlement graph.

func (*Expander) IsDone added in v0.6.7 

func (e *Expander) IsDone(ctx context.Context) bool

func (*Expander) Run added in v0.6.7 

func (e *Expander) Run(ctx context.Context) error

Run executes the complete expansion algorithm until the graph is fully expanded. This is useful for testing where you want to run the entire expansion in one call.

func (*Expander) RunSingleStep added in v0.6.7 

func (e *Expander) RunSingleStep(ctx context.Context) error

RunSingleStep executes one step of the expansion algorithm. Returns true when the graph is fully expanded, false if more work is needed. This matches the syncer's step-by-step execution model.

type ExpanderStore added in v0.6.7 

type ExpanderStore interface {
	GetEntitlement(ctx context.Context, req *reader_v2.EntitlementsReaderServiceGetEntitlementRequest) (*reader_v2.EntitlementsReaderServiceGetEntitlementResponse, error)
	ListGrantsForEntitlement(ctx context.Context, req *reader_v2.GrantsReaderServiceListGrantsForEntitlementRequest) (*reader_v2.GrantsReaderServiceListGrantsForEntitlementResponse, error)
	PutGrants(ctx context.Context, grants ...*v2.Grant) error
}

ExpanderStore defines the minimal store interface needed for grant expansion. This interface can be implemented by the connectorstore or by a mock for testing.

type Node 

type Node struct {
	Id             int      `json:"id"`
	EntitlementIDs []string `json:"eids"` // List of entitlements.
}

Node represents a list of entitlements. It is the base element of the graph.

func (*Node) Str 

func (node *Node) Str() string

Source Files

View all Source files

Directories

Path Synopsis
Package scc provides an iterative FW–BW SCC condensation for directed graphs, adapted for Baton’s entitlement graph.
 Package scc provides an iterative FW–BW SCC condensation for directed graphs, adapted for Baton’s entitlement graph.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.