graph

package
v0.2.1 Latest Latest
Warning

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

 Go to latest Published: Mar 25, 2026 License: Apache-2.0 Imports: 14 Imported by: 3

Documentation

Index

Constants

View Source 
const (
	// DirectEdge leads directly to a single type or type#rel
	//
	// e.g. define rel1: [user]
	// define rel2: [group#member]
	//define rel2: [user, employee, user:*, user:* with xcond, employee with xcond, group#member, group#member with xcond]
	DirectEdge EdgeType = 0

	// RewriteEdge leads from an operator to a relation
	//
	// in `define rel1: a OR b`, the edge from `OR --> b` and the edge from rel1 -> OR
	RewriteEdge EdgeType = 1

	// TTUEdge points to a tuple to userset relation
	//
	// e.g. define rel1: admin from parent
	TTUEdge EdgeType = 2

	// ComputedEdge points to another relation
	//
	// e.g. define rel1: rel2
	ComputedEdge EdgeType = 3

	// DirectLogicalEdge points to the LogicalDirectGrouping of multiple direct edges that are part of an operator node
	//
	// define rel1: [user, employee, group#member] or rel2
	// in this case OR node has two edges, one rewrite edge that goes to rel2 and another one that goes the direct edges grouping
	// however, when there is not operator node involved then the LogicalDirectGrouping is not created to avoid unnecesary nested nodes creation
	// for example in this use case,
	// define rel1: [user, employee, group#member]
	// the node rel1 has three direct edges
	DirectLogicalEdge EdgeType = 4

	// TTULogicalEdge points to the LogicalTTUGrouping when a TTU has multiple possible parents and are part of an operator node
	// For example, if both team and group below had a #viewer relation and viewer from parent is defined as part of a union operation
	// then a new node is create to group the TTUs
	//
	// define parent: [team, group]
	// define can_view: viewer from parent or member
	// however, when there is not operator node involved then the LogicalTTUGrouping is not created to avoid unnecesary nested nodes creation
	// for example in this use case no LogicalTTUGrouping is created, the two ttu edges are referenced directly from the can_view relation node
	// define can_view: viewer from parent
	// define parent: [team, group]
	TTULogicalEdge EdgeType = 5

	// When an edge does not have cond in the model, it will have a condition with value none.
	// This is required to differentiate when an edge need to support condition and no condition
	// like define rel1: [user, user with condX], in this case the edge will have [none, condX]
	// or an edge needs to support only condition like define rel1: [user with condX], the edge will have [condX]
	// in the case the edge does not have any condition like define rel1: [user], the edge will have [none].
	NoCond string = ""
)
View Source 
const Infinite = math.MaxInt32

Variables

View Source 
var (
	ErrBuildingGraph = errors.New("cannot build graph")
	ErrQueryingGraph = errors.New("cannot query graph")
)
View Source 
var ErrContrainstTupleCycle = fmt.Errorf("%w: operands AND or BUT NOT cannot be involved in a cycle", ErrTupleCycle)
View Source 
var ErrInvalidModel = errors.New("invalid model")
View Source 
var ErrModelCycle = errors.New("model cycle")
View Source 
var ErrTupleCycle = errors.New("tuple cycle")

Functions

This section is empty.

Types

type AuthorizationModelEdge 

type AuthorizationModelEdge struct {
	graph.Line
	// contains filtered or unexported fields
}

func (*AuthorizationModelEdge) Attributes 

func (n *AuthorizationModelEdge) Attributes() []encoding.Attribute

func (*AuthorizationModelEdge) EdgeType 

func (n *AuthorizationModelEdge) EdgeType() EdgeType

func (*AuthorizationModelEdge) TuplesetRelation 

func (n *AuthorizationModelEdge) TuplesetRelation() string

TuplesetRelation returns the TTU relation. For example, relation define viewer: viewer from parent gives the graph "document#viewer" -> "document#viewer" and the edge is conditioned on "document#parent".

type AuthorizationModelGraph 

type AuthorizationModelGraph struct {
	*multi.DirectedGraph
	// contains filtered or unexported fields
}

func NewAuthorizationModelGraph 

func NewAuthorizationModelGraph(model *openfgav1.AuthorizationModel) (*AuthorizationModelGraph, error)

NewAuthorizationModelGraph builds an authorization model in graph form. For example, types such as `group`, usersets such as `group#member` and wildcards `group:*` are encoded as nodes. By default, the graph is drawn from bottom to top (i.e. terminal types have outgoing edges and no incoming edges). Conditions are not encoded in the graph.

func (*AuthorizationModelGraph) Attributes 

func (g *AuthorizationModelGraph) Attributes() []encoding.Attribute

func (*AuthorizationModelGraph) DOTAttributers 

func (g *AuthorizationModelGraph) DOTAttributers() (encoding.Attributer, encoding.Attributer, encoding.Attributer)

func (*AuthorizationModelGraph) GetCycles 

func (g *AuthorizationModelGraph) GetCycles() CycleInformation

func (*AuthorizationModelGraph) GetDOT 

func (g *AuthorizationModelGraph) GetDOT() string

GetDOT returns the DOT visualization. The output text is stable. It should only be used for debugging.

func (*AuthorizationModelGraph) GetDrawingDirection 

func (g *AuthorizationModelGraph) GetDrawingDirection() DrawingDirection

func (*AuthorizationModelGraph) GetNodeByLabel 

func (g *AuthorizationModelGraph) GetNodeByLabel(label string) (*AuthorizationModelNode, error)

GetNodeByLabel provides O(1) access to a node. If the node doesn't exist, it returns ErrQueryingGraph.

func (*AuthorizationModelGraph) PathExists 

func (g *AuthorizationModelGraph) PathExists(fromLabel, toLabel string) (bool, error)

PathExists returns true if both nodes exist and there is a path starting at 'fromLabel' extending to 'toLabel'. If both labels are equal, it returns true. If either node doesn't exist, it returns false and ErrQueryingGraph. Note: if somewhere in the path there is an IntersectionOperator or ExclusionOperator, it will NOT return false if there is some child that does NOT reach 'toLabel'.

func (*AuthorizationModelGraph) Reversed 

func (g *AuthorizationModelGraph) Reversed() (*AuthorizationModelGraph, error)

Reversed returns a full copy of the graph, but with the direction of the arrows flipped.

type AuthorizationModelGraphBuilder 

type AuthorizationModelGraphBuilder struct {
	graph.DirectedMultigraphBuilder
	// contains filtered or unexported fields
}

func (*AuthorizationModelGraphBuilder) AddEdge 

func (g *AuthorizationModelGraphBuilder) AddEdge(from, to graph.Node, edgeType EdgeType, tuplesetRelation string, conditions []string) *AuthorizationModelEdge

type AuthorizationModelNode 

type AuthorizationModelNode struct {
	graph.Node
	// contains filtered or unexported fields
}

func (*AuthorizationModelNode) Attributes 

func (n *AuthorizationModelNode) Attributes() []encoding.Attribute

func (*AuthorizationModelNode) Label 

func (n *AuthorizationModelNode) Label() string

func (*AuthorizationModelNode) NodeType 

func (n *AuthorizationModelNode) NodeType() NodeType

type CycleInformation 

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

CycleInformation encapsulates whether the graph has cycles.

type DrawingDirection 

type DrawingDirection bool
const (
	// DrawingDirectionListObjects is when terminal types have outgoing edges and no incoming edges.
	DrawingDirectionListObjects DrawingDirection = true
	// DrawingDirectionCheck is when terminal types have incoming edges and no outgoing edges.
	DrawingDirectionCheck DrawingDirection = false
)

type EdgeType 

type EdgeType int64

type NodeLabelsToIDs 

type NodeLabelsToIDs map[string]int64

type NodeType 

type NodeType int64
const (
	SpecificType            NodeType = 0 // e.g. `group`
	SpecificTypeAndRelation NodeType = 1 // e.g. `group#viewer`
	OperatorNode            NodeType = 2 // e.g. union
	SpecificTypeWildcard    NodeType = 3 // e.g. `group:*`
	LogicalDirectGrouping   NodeType = 4 // e.g. `[user, employee, type1#rel]`
	LogicalTTUGrouping      NodeType = 5 // e.g. `member from parent, wherer parent can have multiple terminal types`

	UnionOperator        = "union"
	IntersectionOperator = "intersection"
	ExclusionOperator    = "exclusion"
)

type WeightedAuthorizationModelEdge 

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

func (*WeightedAuthorizationModelEdge) GetConditions 

func (edge *WeightedAuthorizationModelEdge) GetConditions() []string

GetConditions returns the conditions field, e.g. "none, condX".

func (*WeightedAuthorizationModelEdge) GetEdgeType 

func (edge *WeightedAuthorizationModelEdge) GetEdgeType() EdgeType

GetEdgeType returns the edge type.

func (*WeightedAuthorizationModelEdge) GetFrom 

func (edge *WeightedAuthorizationModelEdge) GetFrom() *WeightedAuthorizationModelNode

GetFrom returns the from node.

func (*WeightedAuthorizationModelEdge) GetRecursiveRelation 

func (edge *WeightedAuthorizationModelEdge) GetRecursiveRelation() string

GetRecursiveRelation returns a string of the recursive relation in a tuple cycle. A recursive relation only exists when the node is self-referential without any intermediate nodes of SpecificTypeAndRelation.

func (*WeightedAuthorizationModelEdge) GetRelationDefinition 

func (edge *WeightedAuthorizationModelEdge) GetRelationDefinition() string

GetRelationDefinition returns the relationDefinition field, e.g. "document#parent".

func (*WeightedAuthorizationModelEdge) GetTo 

func (edge *WeightedAuthorizationModelEdge) GetTo() *WeightedAuthorizationModelNode

GetTo returns the to node.

func (*WeightedAuthorizationModelEdge) GetTuplesetRelation 

func (edge *WeightedAuthorizationModelEdge) GetTuplesetRelation() string

GetTuplesetRelation returns the tuplesetRelation field, e.g. "document#parent".

func (*WeightedAuthorizationModelEdge) GetWeight 

func (edge *WeightedAuthorizationModelEdge) GetWeight(key string) (int, bool)

GetWeight returns the weight for a specific type. It can return Infinite to indicate recursion.

func (*WeightedAuthorizationModelEdge) GetWeights 

func (edge *WeightedAuthorizationModelEdge) GetWeights() map[string]int

GetWeights returns the entire weights map.

func (*WeightedAuthorizationModelEdge) GetWildcards 

func (edge *WeightedAuthorizationModelEdge) GetWildcards() []string

GetWildcards returns an array of types, e.g. "user". This means that in the direction of this edge there is a path to node user:*.

func (*WeightedAuthorizationModelEdge) IsPartOfTupleCycle 

func (edge *WeightedAuthorizationModelEdge) IsPartOfTupleCycle() bool

IsPartOfTupleCycle returns a true if the edge is part of a cycle path that involves more than one node of type SpecificTypeAndRelation.

type WeightedAuthorizationModelGraph 

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

func NewWeightedAuthorizationModelGraph 

func NewWeightedAuthorizationModelGraph() *WeightedAuthorizationModelGraph

NewWeightedAuthorizationModelGraph creates a new WeightedAuthorizationModelGraph.

func (*WeightedAuthorizationModelGraph) AddEdge 

func (wg *WeightedAuthorizationModelGraph) AddEdge(fromID, toID string, edgeType EdgeType, relationDefinition string, tuplesetRelation string, conditions []string)

func (*WeightedAuthorizationModelGraph) AddNode 

func (wg *WeightedAuthorizationModelGraph) AddNode(uniqueLabel, label string, nodeType NodeType)

AddNode adds a node to the graph with optional nodeType and weight.

func (*WeightedAuthorizationModelGraph) AssignWeights 

func (wg *WeightedAuthorizationModelGraph) AssignWeights() error

AssignWeights assigns weights to all the edges and nodes of the graph.

func (*WeightedAuthorizationModelGraph) GetDirectEdgeForUserType 

func (wg *WeightedAuthorizationModelGraph) GetDirectEdgeForUserType(node *WeightedAuthorizationModelNode, userType string) (*WeightedAuthorizationModelEdge, bool)

when a relation is defined as a combination of algebraic operations, direct edges are then linked to the operation nodes and not the relation, However to validate a specific direct assignment, we need to traverse the graph and find the direct edge for the relation node that is linked to the usertype node.

func (*WeightedAuthorizationModelGraph) GetDirectEdgesAssignation 

func (wg *WeightedAuthorizationModelGraph) GetDirectEdgesAssignation(node *WeightedAuthorizationModelNode) ([]*WeightedAuthorizationModelEdge, bool)

when a relation is defined as a combination of algebraic operations, direct edges are then linked to the operation nodes and not the relation, However to validate the direct assignments, we need to traverse the graph and collect all direct edges for the relation node.

func (*WeightedAuthorizationModelGraph) GetEdgeWeight 

func (wg *WeightedAuthorizationModelGraph) GetEdgeWeight(edge *WeightedAuthorizationModelEdge, key string) (int, bool)

GetWeight returns the weight for the given key in the node, it could be a userset key or a terminal type key

func (*WeightedAuthorizationModelGraph) GetEdges 

func (wg *WeightedAuthorizationModelGraph) GetEdges() map[string][]*WeightedAuthorizationModelEdge

GetEdges returns the edges map.

func (*WeightedAuthorizationModelGraph) GetEdgesFromNode 

func (wg *WeightedAuthorizationModelGraph) GetEdgesFromNode(node *WeightedAuthorizationModelNode) ([]*WeightedAuthorizationModelEdge, bool)

func (*WeightedAuthorizationModelGraph) GetEdgesFromNodeId 

func (wg *WeightedAuthorizationModelGraph) GetEdgesFromNodeId(nodeID string) ([]*WeightedAuthorizationModelEdge, bool)

func (*WeightedAuthorizationModelGraph) GetNodeByID 

func (wg *WeightedAuthorizationModelGraph) GetNodeByID(uniqueLabel string) (*WeightedAuthorizationModelNode, bool)

func (*WeightedAuthorizationModelGraph) GetNodeWeight 

func (wg *WeightedAuthorizationModelGraph) GetNodeWeight(node *WeightedAuthorizationModelNode, key string) (int, bool)

GetWeight returns the weight for the given key in the node, it could be a userset key or a terminal type key

func (*WeightedAuthorizationModelGraph) GetNodes 

func (wg *WeightedAuthorizationModelGraph) GetNodes() map[string]*WeightedAuthorizationModelNode

GetNodes returns the nodes map.

func (*WeightedAuthorizationModelGraph) GetOrAddNode 

func (wg *WeightedAuthorizationModelGraph) GetOrAddNode(uniqueLabel, label string, nodeType NodeType) *WeightedAuthorizationModelNode

AddNode adds a node to the graph with optional nodeType and weight.

func (*WeightedAuthorizationModelGraph) HasEdge 

func (wg *WeightedAuthorizationModelGraph) HasEdge(fromNode, toNode *WeightedAuthorizationModelNode, edgeType EdgeType, tuplesetRelation string) bool

func (*WeightedAuthorizationModelGraph) UpsertEdge 

func (wg *WeightedAuthorizationModelGraph) UpsertEdge(fromNode, toNode *WeightedAuthorizationModelNode, edgeType EdgeType, relationDefinition string, tuplesetRelation string, condition string) error

type WeightedAuthorizationModelGraphBuilder 

type WeightedAuthorizationModelGraphBuilder struct {
	graph.DirectedMultigraphBuilder
	// contains filtered or unexported fields
}

func NewWeightedAuthorizationModelGraphBuilder 

func NewWeightedAuthorizationModelGraphBuilder() *WeightedAuthorizationModelGraphBuilder

func (*WeightedAuthorizationModelGraphBuilder) Build 

func (wgb *WeightedAuthorizationModelGraphBuilder) Build(model *openfgav1.AuthorizationModel) (*WeightedAuthorizationModelGraph, error)

type WeightedAuthorizationModelNode 

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

func (*WeightedAuthorizationModelNode) GetDirectAssigns 

func (node *WeightedAuthorizationModelNode) GetDirectAssigns() []string

func (*WeightedAuthorizationModelNode) GetLabel 

func (node *WeightedAuthorizationModelNode) GetLabel() string

GetLabel returns the label, e.g. "user", "group#member", UnionOperator, IntersectionOperator or ExclusionOperator.

func (*WeightedAuthorizationModelNode) GetNodeType 

func (node *WeightedAuthorizationModelNode) GetNodeType() NodeType

GetNodeType returns the node type.

func (*WeightedAuthorizationModelNode) GetRecursiveRelation 

func (node *WeightedAuthorizationModelNode) GetRecursiveRelation() string

GetRecursiveRelation returns a string of the recursive relation in a tuple cycle. A recursive relation only exists when the node is self-referential without any intermediate nodes of SpecificTypeAndRelation.

func (*WeightedAuthorizationModelNode) GetUniqueLabel 

func (node *WeightedAuthorizationModelNode) GetUniqueLabel() string

GetUniqueLabel returns the unique label. It is the same as GetLabel, except for operation nodes, where it takes the form "operation:ULID".

func (*WeightedAuthorizationModelNode) GetWeight 

func (node *WeightedAuthorizationModelNode) GetWeight(key string) (int, bool)

GetWeight returns the weight for a specific type. It can return Infinite to indicate recursion.

func (*WeightedAuthorizationModelNode) GetWeights 

func (node *WeightedAuthorizationModelNode) GetWeights() map[string]int

GetWeights returns the entire weights map.

func (*WeightedAuthorizationModelNode) GetWildcards 

func (node *WeightedAuthorizationModelNode) GetWildcards() []string

GetWildcards returns an array of types, e.g. "user". This means that from this node there is a path to node user:*.

func (*WeightedAuthorizationModelNode) IsPartOfTupleCycle 

func (node *WeightedAuthorizationModelNode) IsPartOfTupleCycle() bool

IsPartOfTupleCycle returns a true if the node is part of a cycle that involves more than one node of type SpecificTypeAndRelation.

Source Files

View all Source files

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.