analysis

package
v0.6.5 Latest Latest
Warning

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

 Go to latest Published: Jan 31, 2026 License: MIT Imports: 3 Imported by: 0

Documentation

Overview

Package analysis provides relation analysis and strategy selection for SQL code generation.

Package analysis provides relation analysis and feature detection for SQL generation.

Overview

This package analyzes OpenFGA authorization models to determine what SQL patterns are needed to evaluate permission checks and list operations. It classifies each relation by its features (direct, implied, userset, TTU, exclusion, intersection) and computes derived metadata used by the code generator.

Analysis Pipeline

The analysis happens in three stages:

  1. AnalyzeRelations: Classify relations and detect features
  2. ComputeCanGenerate: Determine generation eligibility and populate metadata
  3. DetermineListStrategy: Select the appropriate list generation template

Relation Features

Each relation is analyzed to detect which OpenFGA patterns it uses:

  • HasDirect: [user] - allows direct subject type grants
  • HasImplied: viewer: editor - satisfied by another relation via closure
  • HasWildcard: [user:*] - allows wildcard grants for any subject_id
  • HasUserset: [group#member] - grants via membership in another object
  • HasRecursive: viewer from parent - grants inherited through relationships (TTU)
  • HasExclusion: but not blocked - denies access based on conditions
  • HasIntersection: writer and editor - requires all parts to be satisfied

Multiple features can coexist. For example, a relation can have both Direct and Userset features, meaning access is granted either by direct tuple or group membership. The generator produces SQL that ORs these paths together.

Closure and Dependencies

Implied relations create a transitive closure where one relation satisfies another. For example, if "owner" implies "editor" and "editor" implies "viewer", then the closure for "viewer" includes ["viewer", "editor", "owner"].

The analysis partitions closure relations into:

  • SimpleClosureRelations: Can use direct tuple lookup (relation IN (...))
  • ComplexClosureRelations: Need function calls (have exclusions, usersets, TTU, intersection)

This enables efficient tuple lookups for simple cases while delegating to specialized functions for complex authorization logic.

Generation Capabilities

After analysis, each relation has computed Capabilities indicating what can be generated:

  • CheckAllowed: Can generate check_{type}_{relation} function (always true)
  • ListAllowed: Can generate list functions (requires compatible features)
  • ListStrategy: Which list generation approach to use (Direct, Userset, Recursive, etc.)

Check functions are generated for all relations. List functions have stricter requirements - all relations in the closure must have compatible features.

List Strategies

The DetermineListStrategy function selects the template based on relation features:

  • ListStrategyDirect: Direct tuple lookup, possibly with exclusions
  • ListStrategyUserset: Expands usersets via JOINs
  • ListStrategyRecursive: Uses recursive CTEs for parent-child traversal
  • ListStrategySelfRefUserset: Recursive CTEs for self-referential usersets
  • ListStrategyComposed: Composes through TTU/userset paths to reach anchor
  • ListStrategyIntersection: Uses INTERSECT for AND patterns
  • ListStrategyDepthExceeded: Immediately raises depth limit error

Indirect Anchors

For relations without direct/implied access (pure TTU or pure userset patterns), the analysis traces through the pattern to find an anchor relation with direct grants. This enables list generation by composing list functions along the path.

For example, document.viewer: viewer from folder where folder.viewer: [user] creates an indirect anchor at folder.viewer. The list function for document.viewer composes with the list function for folder.viewer.

Metadata Propagation

The analysis propagates metadata through the dependency graph:

  • AllowedSubjectTypes: Union of subject types from satisfying relations
  • HasWildcard: True if any relation in the closure supports wildcards
  • UsersetPatterns: Enriched with SatisfyingRelations and IsComplex flags
  • MaxUsersetDepth: Maximum chain depth for userset patterns

This metadata drives code generation decisions and optimization opportunities.

Index

Constants

This section is empty.

Variables

View Source 
var ComputeRelationClosure = schema.ComputeRelationClosure

Function alias for schema.ComputeRelationClosure.

Functions

func BuildAnalysisLookup 

func BuildAnalysisLookup(analyses []RelationAnalysis) map[string]map[string]*RelationAnalysis

BuildAnalysisLookup creates a nested map for efficient analysis lookups. Returns map[objectType][relation] -> *RelationAnalysis

Types

type AnchorPathStep 

type AnchorPathStep struct {
	// Type is either "ttu" or "userset"
	Type string

	// For TTU patterns (e.g., "viewer from parent"):
	// LinkingRelation is "parent" (the relation that links to the parent object)
	// TargetType is the first parent object type found with an anchor (e.g., "folder")
	// TargetRelation is the relation to check on the parent (e.g., "viewer")
	// AllTargetTypes contains ALL object types that the linking relation can point to
	// when each type has the target relation with direct grants. This is used for
	// generating UNION queries when parent can be multiple types (e.g., [document, folder]).
	// RecursiveTypes contains object types where the target relation is recursive
	// (same type as the object type being checked). These require check_permission_internal
	// instead of list function composition to handle the recursion correctly.
	LinkingRelation string
	TargetType      string
	TargetRelation  string
	AllTargetTypes  []string
	RecursiveTypes  []string

	// For userset patterns (e.g., [group#member]):
	// SubjectType is "group"
	// SubjectRelation is "member"
	SubjectType     string
	SubjectRelation string
}

AnchorPathStep represents one step in the path from a relation to its anchor. Steps can be either TTU (tuple-to-userset) or userset patterns.

type ClosureRow 

type ClosureRow = schema.ClosureRow

Type aliases for schema types used in analysis. This avoids prefixing every usage with "schema." throughout this file.

type GenerationCapabilities 

type GenerationCapabilities struct {
	// CheckAllowed is true if specialized check SQL can be generated.
	// When false, the check dispatcher falls back to check_permission_generic_internal.
	CheckAllowed bool

	// ListAllowed is true if specialized list SQL can be generated.
	// When false, the list dispatcher falls back to list_accessible_*_generic functions.
	ListAllowed bool

	// CheckReason explains why CheckAllowed is false (empty if allowed).
	// Used for debugging and diagnostic output.
	CheckReason string

	// ListReason explains why ListAllowed is false (empty if allowed).
	// Used for debugging and diagnostic output.
	ListReason string
}

GenerationCapabilities represents the unified generation eligibility for a relation. This consolidates the former separate CanGenerate (check) and CanGenerateListValue (list) flags into a single structure with clear semantics.

type IndirectAnchorInfo 

type IndirectAnchorInfo struct {
	// Path describes the traversal from this relation to the anchor.
	// For "document.viewer: viewer from folder" where folder.viewer: [user],
	// Path would contain one TTU step pointing to folder.viewer.
	// For multi-hop chains, Path contains multiple steps.
	Path []AnchorPathStep

	// AnchorType and AnchorRelation identify the relation with direct grants.
	// This is the final destination of the path - a relation that has HasDirect.
	AnchorType     string
	AnchorRelation string
}

IndirectAnchorInfo describes how to reach a relation with direct grants when the relation itself has no direct/implied access paths. This enables list generation for "pure" patterns like pure TTU or pure userset by tracing through to find an anchor relation that has [user] or similar direct grants.

For example, for "document.viewer: viewer from folder" where folder.viewer: [user], the IndirectAnchor would point to folder.viewer with a TTU path step.

type IntersectionGroup 

type IntersectionGroup = schema.IntersectionGroup

Type aliases for schema types used in analysis. This avoids prefixing every usage with "schema." throughout this file.

type IntersectionGroupInfo 

type IntersectionGroupInfo struct {
	Parts []IntersectionPart
}

IntersectionGroupInfo represents a group of parts that must ALL be satisfied (AND). Multiple groups are OR'd together.

type IntersectionPart 

type IntersectionPart struct {
	IsThis           bool                // [user] - direct assignment check on the same relation
	HasWildcard      bool                // For IsThis parts: whether direct assignment allows wildcards
	Relation         string              // Relation to check
	IsSimple         bool                // True if this relation is simply resolvable (can use inline EXISTS)
	ExcludedRelation string              // For nested exclusions like "editor but not owner"
	IsExcludedSimple bool                // True if excluded relation is simply resolvable
	ParentRelation   *ParentRelationInfo // For tuple-to-userset in intersection
}

IntersectionPart represents one part of an intersection check. For "writer and (editor but not owner)", we'd have:

  • {Relation: "writer"}
  • {Relation: "editor", ExcludedRelation: "owner"}

type ListStrategy 

type ListStrategy int

ListStrategy determines which list generation approach to use. Each strategy corresponds to a different code generation path optimized for specific authorization patterns. 

const (
	// ListStrategyDirect handles direct/implied tuple lookups with optional exclusions.
	// Used for relations like "viewer: [user]" or "viewer: [user] but not blocked".
	ListStrategyDirect ListStrategy = iota

	// ListStrategyUserset handles [group#member] pattern expansion via JOINs.
	// Used for relations like "viewer: [group#member]".
	ListStrategyUserset

	// ListStrategyRecursive handles TTU patterns with recursive CTEs or cross-type calls.
	// Used for relations like "viewer: viewer from parent".
	ListStrategyRecursive

	// ListStrategyIntersection handles AND patterns with INTERSECT queries.
	// Used for relations like "viewer: writer and editor".
	ListStrategyIntersection

	// ListStrategyDepthExceeded generates a function that immediately raises M2002.
	// Used for relations with userset chains >= 25 levels deep.
	ListStrategyDepthExceeded

	// ListStrategySelfRefUserset handles self-referential userset patterns.
	// Used for relations like "member: [group#member]" where the userset
	// references the same type and relation, requiring recursive CTEs.
	ListStrategySelfRefUserset

	// ListStrategyComposed handles indirect anchor patterns via function composition.
	// Used for pure TTU patterns that trace through to an anchor with direct grants.
	ListStrategyComposed
)

func DetermineListStrategy 

func DetermineListStrategy(a RelationAnalysis) ListStrategy

DetermineListStrategy computes the appropriate list generation strategy based on the relation's analysis data. The priority order matches the former selectListObjectsTemplate/selectListSubjectsTemplate functions.

Priority (highest to lowest): 1. DepthExceeded - relation exceeds userset depth limit 2. SelfRefUserset - has self-referential userset patterns 3. Composed - has indirect anchor (pure TTU reaching direct grants) 4. Intersection - has intersection patterns (AND groups) 5. Recursive - has TTU patterns or closure TTU patterns 6. Userset - has userset patterns or closure userset patterns 7. Direct - default (handles direct, implied, and exclusion patterns)

func (ListStrategy) String 

func (s ListStrategy) String() string

String returns the strategy name for debugging and diagnostic output.

type ParentRelationCheck 

type ParentRelationCheck = schema.ParentRelationCheck

Type aliases for schema types used in analysis. This avoids prefixing every usage with "schema." throughout this file.

type ParentRelationInfo 

type ParentRelationInfo struct {
	Relation            string   // Relation to check on parent (e.g., "viewer")
	LinkingRelation     string   // Relation that links to parent (e.g., "parent")
	AllowedLinkingTypes []string // Types allowed for linking relation (e.g., ["folder", "org"])
	SourceRelation      string   // For closure patterns: the relation this TTU was inherited from (e.g., "reader" in "can_read: reader")
}

ParentRelationInfo represents a "X from Y" pattern (tuple-to-userset). For "viewer from parent" on a folder type, this would have:

  • Relation: "viewer" (the relation to check on the parent)
  • LinkingRelation: "parent" (the relation that links to the parent)
  • AllowedLinkingTypes: ["folder"] (types the linking relation can point to)

The actual parent type is determined at runtime from the linking relation's subject types. AllowedLinkingTypes captures these for code generation.

type RelationAnalysis 

type RelationAnalysis struct {
	ObjectType string           // The object type (e.g., "document")
	Relation   string           // The relation name (e.g., "viewer")
	Features   RelationFeatures // Feature flags determining what SQL to generate

	// Capabilities holds the unified generation eligibility for check and list functions.
	// Computed by ComputeCanGenerate after all relations are analyzed.
	Capabilities GenerationCapabilities

	// ListStrategy determines which list generation approach to use.
	// Computed by ComputeCanGenerate after Capabilities is set.
	ListStrategy ListStrategy

	// For Direct/Implied patterns - from closure table
	SatisfyingRelations []string // Relations that satisfy this one (e.g., ["viewer", "editor", "owner"])

	// For Exclusion patterns
	ExcludedRelations []string // Relations to exclude (for simple "but not X" patterns)

	// SimpleExcludedRelations are excluded relations that can be checked with
	// a direct tuple lookup (no userset, TTU, exclusion, or intersection).
	SimpleExcludedRelations []string

	// ComplexExcludedRelations are excluded relations that need function calls
	// (have userset, TTU, exclusion, intersection, or implied closure).
	// The generated code will call check_permission_internal for these.
	ComplexExcludedRelations []string

	// ExcludedParentRelations captures "but not X from Y" patterns (TTU exclusions).
	// These are resolved by looking up the linking relation Y and calling
	// check_permission_internal for relation X on each linked object.
	ExcludedParentRelations []ParentRelationInfo

	// ExcludedIntersectionGroups captures "but not (A and B)" patterns.
	// These are resolved by ANDing together check_permission_internal calls
	// for each relation in the group.
	ExcludedIntersectionGroups []IntersectionGroupInfo

	// For Userset patterns
	UsersetPatterns []UsersetPattern // [group#member] patterns

	// For Recursive patterns (tuple-to-userset)
	ParentRelations []ParentRelationInfo

	// For Intersection patterns
	IntersectionGroups []IntersectionGroupInfo

	// HasComplexUsersetPatterns is true if any userset pattern is complex
	// (requires check_permission_internal call). When true, the generated
	// function needs PL/pgSQL with cycle detection.
	HasComplexUsersetPatterns bool

	// Direct subject types (for generating direct tuple checks)
	DirectSubjectTypes []string // e.g., ["user", "org"]

	// AllowedSubjectTypes is the union of all subject types from satisfying relations.
	// This is used to enforce type restrictions in generated SQL.
	// Computed by ComputeCanGenerate.
	AllowedSubjectTypes []string

	// SimpleClosureRelations contains relations in the closure that can use tuple lookup.
	// These are relations without exclusions, usersets, recursion, or intersections.
	// Computed by ComputeCanGenerate.
	SimpleClosureRelations []string

	// ComplexClosureRelations contains relations in the closure that need function calls.
	// These are relations with exclusions that are themselves generatable.
	// Computed by ComputeCanGenerate.
	ComplexClosureRelations []string

	// IntersectionClosureRelations contains relations in the closure that have intersection
	// patterns and are list-generatable. These need to be handled by composing with their
	// list function rather than tuple lookup (since intersection relations have no tuples).
	// Computed by computeCanGenerateList.
	IntersectionClosureRelations []string

	// ClosureUsersetPatterns contains userset patterns from closure relations.
	// For example, if `can_view: viewer` and `viewer: [group#member]`, then
	// can_view's ClosureUsersetPatterns includes group#member.
	// This is used by list functions to expand usersets from implied relations.
	// Computed by ComputeCanGenerate.
	ClosureUsersetPatterns []UsersetPattern

	// ClosureParentRelations contains TTU patterns from closure relations.
	// For example, if `can_view: viewer` and `viewer: viewer from parent`, then
	// can_view's ClosureParentRelations includes the parent relation info.
	// This is used by list functions to traverse TTU paths from implied relations.
	// Computed by ComputeCanGenerate.
	ClosureParentRelations []ParentRelationInfo

	// ClosureExcludedRelations contains excluded relations from closure relations.
	// For example, if `can_read: reader` and `reader: [user] but not restricted`,
	// then can_read's ClosureExcludedRelations includes "restricted".
	// This ensures exclusions are applied when accessing through implied relations.
	// Computed by ComputeCanGenerate.
	ClosureExcludedRelations []string

	// IndirectAnchor describes how to reach a relation with direct grants when this
	// relation has no direct/implied access paths. For pure TTU or pure userset patterns,
	// this traces through the pattern to find an anchor relation with [user] or similar.
	// Nil if the relation has direct/implied access or if no anchor can be found.
	// Computed by ComputeCanGenerate via findIndirectAnchor.
	IndirectAnchor *IndirectAnchorInfo

	// MaxUsersetDepth is the maximum userset chain depth reachable from this relation.
	// -1 means infinite (self-referential userset cycle), 0 means no userset patterns.
	// Values >= 25 indicate the relation will always exceed the depth limit.
	// Computed by ComputeCanGenerate via computeMaxUsersetDepth.
	MaxUsersetDepth int

	// ExceedsDepthLimit is true if MaxUsersetDepth >= 25.
	// These relations generate functions that immediately raise M2002.
	ExceedsDepthLimit bool

	// SelfReferentialUsersets lists userset patterns that reference the same type and relation.
	// e.g., for group.member: [user, group#member], this would contain
	// UsersetPattern{SubjectType: "group", SubjectRelation: "member"}
	// These patterns require recursive CTEs to expand nested group membership.
	// Computed by ComputeCanGenerate.
	SelfReferentialUsersets []UsersetPattern

	// HasSelfReferentialUserset is true if len(SelfReferentialUsersets) > 0.
	// When true, the list templates use recursive CTEs to expand the userset chain.
	HasSelfReferentialUserset bool
}

RelationAnalysis contains all data needed to generate SQL for a relation. This struct is populated by AnalyzeRelations and consumed by the SQL generator.

func AnalyzeRelations 

func AnalyzeRelations(types []TypeDefinition, closure []ClosureRow) []RelationAnalysis

AnalyzeRelations classifies all relations and gathers data needed for SQL generation. It uses the precomputed closure to determine satisfying relations for each relation.

func ComputeCanGenerate 

func ComputeCanGenerate(analyses []RelationAnalysis) []RelationAnalysis

ComputeCanGenerate walks the dependency graph and sets Capabilities on each analysis. It determines generation eligibility and populates derived data used by code generation.

A relation's CheckAllowed is always true (we generate specialized functions for all relations). A relation's ListAllowed is true if: 1. Its own features allow list generation (at least one access path) 2. ALL relations in its satisfying closure are also list-generatable

For relations in the closure that need function calls (have exclusions but are generatable), the generated SQL will call their specialized check function rather than using tuple lookup.

This function also: - Propagates HasWildcard: if ANY relation in the closure supports wildcards - Collects AllowedSubjectTypes: union of all subject types from satisfying relations - Partitions closure relations into SimpleClosureRelations and ComplexClosureRelations - Partitions excluded relations into SimpleExcludedRelations and ComplexExcludedRelations - Computes ListStrategy for selecting the appropriate list code generation path

type RelationDefinition 

type RelationDefinition = schema.RelationDefinition

Type aliases for schema types used in analysis. This avoids prefixing every usage with "schema." throughout this file.

type RelationFeatures 

type RelationFeatures struct {
	HasDirect       bool // [user] - direct tuple lookup, the relation accepts specific subject types
	HasImplied      bool // viewer: editor - this relation is satisfied by another relation via closure
	HasWildcard     bool // [user:*] - allows wildcard grants that match any subject_id
	HasUserset      bool // [group#member] - grants via membership in another object's relation
	HasRecursive    bool // viewer from parent - grants inherited through parent/child relationships (TTU)
	HasExclusion    bool // but not blocked - denies access based on negative conditions
	HasIntersection bool // writer and editor - requires AND of all parts
}

RelationFeatures tracks which features a relation uses. Multiple features can be present and will be composed in generated SQL. For example, a relation with HasDirect, HasUserset, and HasRecursive will generate SQL that ORs together all three access paths.

func (RelationFeatures) CanGenerate 

func (f RelationFeatures) CanGenerate() bool

CanGenerate returns true if we can generate specialized SQL for this feature set. This checks the features themselves - for full generation eligibility, also check that all dependency relations are generatable via RelationAnalysis.CanGenerate.

func (RelationFeatures) IsClosureCompatible 

func (f RelationFeatures) IsClosureCompatible() bool

IsClosureCompatible returns true if this relation can participate in a closure-based tuple lookup (relation IN ('a', 'b', 'c')) WITHOUT additional permission logic.

This returns false for relations with exclusions because when a relation A implies relation B (e.g., can_view: viewer), and B has an exclusion (e.g., viewer: [user] but not blocked), checking A requires applying B's exclusion. A simple closure lookup won't do this.

Note: A relation can still generate code for ITSELF even if it has an exclusion - its generated function handles the exclusion. But it can't be part of another relation's closure lookup.

func (RelationFeatures) IsSimplyResolvable 

func (f RelationFeatures) IsSimplyResolvable() bool

IsSimplyResolvable returns true if this relation can be fully resolved with a simple tuple lookup (no userset JOINs, recursion, exclusions, etc.). This is used to check if excluded relations can be handled with a simple EXISTS check, since exclusions on excluded relations would require full permission resolution.

func (RelationFeatures) NeedsCycleDetection 

func (f RelationFeatures) NeedsCycleDetection() bool

NeedsCycleDetection returns true if the generated function needs cycle detection.

func (RelationFeatures) NeedsPLpgSQL 

func (f RelationFeatures) NeedsPLpgSQL() bool

NeedsPLpgSQL returns true if the generated function needs PL/pgSQL (vs pure SQL). Required for cycle detection (variables, IF statements).

func (RelationFeatures) String 

func (f RelationFeatures) String() string

String returns a human-readable description of the features.

type SubjectTypeRef 

type SubjectTypeRef = schema.SubjectTypeRef

Type aliases for schema types used in analysis. This avoids prefixing every usage with "schema." throughout this file.

type TypeDefinition 

type TypeDefinition = schema.TypeDefinition

Type aliases for schema types used in analysis. This avoids prefixing every usage with "schema." throughout this file.

type UsersetPattern 

type UsersetPattern struct {
	SubjectType     string // e.g., "group"
	SubjectRelation string // e.g., "member"

	// SatisfyingRelations contains all relations in the closure of SubjectRelation.
	// For example, if SubjectRelation="member_c4" and member_c4 is implied by member,
	// this would contain ["member_c4", "member_c3", "member_c2", "member_c1", "member"].
	// This is populated by ComputeCanGenerate from the closure data.
	SatisfyingRelations []string

	// SourceRelation is the relation where this userset pattern is defined.
	// For direct patterns, this is the same as the relation being analyzed.
	// For closure patterns (inherited from implied relations), this is the source relation.
	// e.g., for can_view: viewer where viewer: [group#member], SourceRelation="viewer"
	// This is used by list functions to search for grant tuples in the correct relation.
	SourceRelation string

	// HasWildcard is true if any relation in the closure supports wildcards.
	// When true, the userset check should match membership tuples with subject_id = '*'.
	// This is populated by ComputeCanGenerate from the subject relation's features.
	HasWildcard bool

	// IsComplex is true if any relation in the closure is not closure-compatible
	// (has userset, TTU, exclusion, or intersection). When true, the userset check
	// must call check_permission_internal to verify membership instead of using
	// a simple tuple JOIN.
	// This is populated by ComputeCanGenerate.
	IsComplex bool
}

UsersetPattern represents a [type#relation] pattern in a relation definition. For example, [group#member] would have SubjectType="group" and SubjectRelation="member".

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.