schema

README

schema

Package schema provides OpenFGA schema types and transformation logic for Melange.

This package contains the core data structures and algorithms for converting OpenFGA authorization models into database-friendly representations. It sits between the parser package (which parses .fga files) and the SQL code generation (which produces specialized check functions).

Package Responsibilities

The schema package handles three critical transformations:

1. Schema representation (TypeDefinition, RelationDefinition) - parsed FGA models
2. SQL model generation (ToAuthzModels) - flattening rules for SQL generation
3. Precomputation (ComputeRelationClosure, ToUsersetRules) - optimizing runtime checks

Key Types

TypeDefinition

Represents a parsed object type from an .fga schema. Each type has relations that define permissions and roles.

type TypeDefinition struct {
    Name      string
    Relations []RelationDefinition
}

RelationDefinition

Represents a parsed relation with all its rule components:

type RelationDefinition struct {
    Name              string              // Relation name: "owner", "can_read", etc.
    ImpliedBy         []string            // Relations that imply this one
    ParentRelations   []ParentRelationCheck  // Tuple-to-userset inheritance
    ExcludedRelations []string            // Exclusions ("but not")
    SubjectTypeRefs   []SubjectTypeRef    // Direct subject types
    IntersectionGroups []IntersectionGroup // AND groups
}

AuthzModel

Represents a flattened authorization rule used during SQL generation:

type AuthzModel struct {
    ObjectType       string
    Relation         string
    SubjectType      *string
    ImpliedBy        *string
    ParentRelation   *string
    ExcludedRelation *string
    // ... additional fields for complex patterns
}

ClosureRow

Represents precomputed transitive relationships for role hierarchies:

type ClosureRow struct {
    ObjectType         string
    Relation           string
    SatisfyingRelation string
    ViaPath            []string // Debug path
}

Public API

Schema Transformation

// ToAuthzModels converts parsed type definitions to database models.
// Performs transitive closure of implied_by relationships.
func ToAuthzModels(types []TypeDefinition) []AuthzModel

// ComputeRelationClosure computes the transitive closure for all relations.
// Enables O(1) lookups instead of O(depth) recursion.
func ComputeRelationClosure(types []TypeDefinition) []ClosureRow

// ToUsersetRules expands userset references using the relation closure.
func ToUsersetRules(types []TypeDefinition, closureRows []ClosureRow) []UsersetRule

Schema Inspection

// SubjectTypes returns all types that can be subjects in authorization checks.
func SubjectTypes(types []TypeDefinition) []string

// RelationSubjects returns subject types that can have a specific relation.
func RelationSubjects(types []TypeDefinition, objectType, relation string) []string

Schema Validation

// DetectCycles checks for cycles in the relation graph.
// Returns ErrCyclicSchema if a cycle is found.
func DetectCycles(types []TypeDefinition) error

// IsCyclicSchemaErr returns true if err is or wraps ErrCyclicSchema.
func IsCyclicSchemaErr(err error) bool

Usage Examples

Inspecting Schema Types

import (
    "github.com/pthm/melange/pkg/parser"
    "github.com/pthm/melange/pkg/schema"
)

// Parse schema
types, err := parser.ParseSchema("schema.fga")
if err != nil {
    log.Fatal(err)
}

// Find all subject types (who can have permissions)
subjects := schema.SubjectTypes(types)
fmt.Println("Subject types:", subjects) // e.g., ["user", "group"]

// Find who can be repository owners
owners := schema.RelationSubjects(types, "repository", "owner")
fmt.Println("Repository owners:", owners) // e.g., ["user"]

Validating Schemas

types, _ := parser.ParseSchema("schema.fga")

if err := schema.DetectCycles(types); err != nil {
    if schema.IsCyclicSchemaErr(err) {
        log.Fatalf("Schema has cycles: %v", err)
    }
    log.Fatalf("Validation error: %v", err)
}

Computing Relation Closure

types, _ := parser.ParseSchema("schema.fga")

// Compute transitive closure for role hierarchies
closureRows := schema.ComputeRelationClosure(types)

// Closure enables efficient permission checks:
// For owner -> admin -> member hierarchy:
// - member is satisfied by: member, admin, owner
// - admin is satisfied by: admin, owner
// - owner is satisfied by: owner
for _, row := range closureRows {
    fmt.Printf("%s.%s is satisfied by %s\n",
        row.ObjectType, row.Relation, row.SatisfyingRelation)
}

Generating Database Models

types, _ := parser.ParseSchema("schema.fga")

// Convert to flattened rules for SQL generation
models := schema.ToAuthzModels(types)

for _, m := range models {
    fmt.Printf("Rule: %s.%s", m.ObjectType, m.Relation)
    if m.ImpliedBy != nil {
        fmt.Printf(" implied by %s", *m.ImpliedBy)
    }
    fmt.Println()
}

Relation Patterns

The schema package understands these OpenFGA patterns:

Pattern	Rule Fields Set	Example
Direct	SubjectType	[user]
Implied	ImpliedBy	viewer: owner
Parent (TTU)	ParentRelation, SubjectType	viewer from org
Exclusion	ExcludedRelation	but not author
Userset	SubjectType, SubjectRelation	[group#member]
Intersection	RuleGroupID, RuleGroupMode	a and b

Dependency Information

This package has no external dependencies (stdlib only) and is imported by:

• pkg/parser - adds OpenFGA DSL parsing
• pkg/migrator - database migration
• pkg/clientgen - client code generation
• internal/sqlgen - SQL code generation

The runtime module (github.com/pthm/melange/melange) does not import this package, keeping it stdlib-only for minimal dependency footprint.

Documentation

Overview

Package schema provides OpenFGA schema types and transformation logic for melange.

This package contains the core data structures and algorithms for converting OpenFGA authorization models into database-friendly representations. It sits between the parser package (which parses .fga files) and the runtime checker (which executes permission checks).

Package Responsibilities

The schema package handles three critical transformations:

1. Schema representation (TypeDefinition, RelationDefinition) - parsed FGA models
2. SQL model generation (ToAuthzModels) - flattening rules for SQL generation
3. Precomputation (ComputeRelationClosure, ToUsersetRules) - optimizing runtime checks

Key Types

TypeDefinition represents a parsed object type from an FGA schema. Each type has relations that define permissions and roles. For example:

type repository
  relations
    define owner: [user]
    define can_read: owner or [user]

AuthzModel represents a flattened authorization rule used during SQL generation. The ToAuthzModels function converts TypeDefinitions into rule rows, performing transitive closure of implied-by relationships to support efficient checks.

ClosureRow represents precomputed transitive relationships. This eliminates recursive SQL during permission checks by answering "what relations satisfy this relation?" with a simple lookup.

Migration Workflow

The Migrator orchestrates loading schemas into PostgreSQL:

1. Parse schema via pkg/parser (returns []TypeDefinition)
2. MigrateWithTypes - validates, transforms, and loads generated SQL

Typical usage:

import (
    "github.com/pthm/melange/pkg/parser"
    "github.com/pthm/melange/pkg/migrator"
)
types, _ := parser.ParseSchema("schemas/schema.fga")
err := migrator.MigrateWithTypes(ctx, db, types)

Code Generation

Use pkg/clientgen to produce type-safe Go constants from schema types:

types, _ := parser.ParseSchema("schema.fga")
files, _ := clientgen.Generate("go", types, cfg)

Generated code includes ObjectType constants, Relation constants, and constructor functions for creating melange.Object values.

Validation

DetectCycles validates schemas before migration. It checks for:

• Implied-by cycles within a type (admin -> owner -> admin)
• Cross-type parent relation cycles
• Allows hierarchical recursion (folder -> parent folder)

Invalid schemas are rejected with ErrCyclicSchema before reaching the database.

Relationship to Other Packages

The schema package is dependency-free (stdlib only) and is imported by:

• pkg/parser (adds OpenFGA DSL parsing)
• pkg/migrator (database migration)
• internal/clientgen (code generation)

The runtime module (github.com/pthm/melange/melange) does not import this package, keeping it stdlib-only.

Index

• Constants
• Variables
• func DetectCycles(types []TypeDefinition) error
• func IsCyclicSchemaErr(err error) bool
• func RelationSubjects(types []TypeDefinition, objectType, relation string) []string
• func SubjectTypes(types []TypeDefinition) []string
• type AuthzModel
  • func ToAuthzModels(types []TypeDefinition) []AuthzModel
• type ClosureRow
  • func ComputeRelationClosure(types []TypeDefinition) []ClosureRow
• type IntersectionGroup
• type ParentRelationCheck
• type RelationDefinition
• type SubjectTypeRef
• type TypeDefinition
• type UsersetRule
  • func ToUsersetRules(types []TypeDefinition, closureRows []ClosureRow) []UsersetRule

Constants

const (
	// RuleGroupModeIntersection indicates all rules in the group must be satisfied (AND).
	// Used for "viewer: writer and editor" patterns.
	RuleGroupModeIntersection = "intersection"

	// RuleGroupModeExcludeIntersection indicates an exclusion where all rules must be
	// satisfied for the exclusion to apply. Used for "but not (editor and owner)" patterns.
	RuleGroupModeExcludeIntersection = "exclude_intersection"
)

RuleGroupMode constants define how rules within a group are combined.

Variables

var ErrCyclicSchema = errors.New("melange/schema: cyclic schema")

ErrCyclicSchema is returned when the schema contains a cycle in the relation graph.

Functions

func DetectCycles

func DetectCycles(types []TypeDefinition) error

DetectCycles checks for cycles in the relation graph. It validates both implied-by cycles (within a single type) and parent relation cycles (across types). Returns an error describing the cycle if one is found.

This function is called by both GenerateGo and MigrateWithTypes to catch invalid schemas before they cause runtime issues.

Example cyclic schemas that would be detected:

// Implied-by cycle:
type resource
  relations
    define admin: [user] or owner
    define owner: [user] or admin  // CYCLE: admin ↔ owner

// Parent relation cycle:
type organization
  relations
    define repo: [repository]
    define can_read: can_read from repo
type repository
  relations
    define org: [organization]
    define can_read: can_read from org  // CYCLE: crosses types

func IsCyclicSchemaErr

func IsCyclicSchemaErr(err error) bool

IsCyclicSchemaErr returns true if err is or wraps ErrCyclicSchema.

func RelationSubjects

func RelationSubjects(types []TypeDefinition, objectType, relation string) []string

RelationSubjects returns the subject types that can have a specific relation on objects of the given type. This is useful for understanding who can be granted a particular permission.

Example:

types, _ := tooling.ParseSchema("schema.fga")
subjects := schema.RelationSubjects(types, "repository", "owner")
// Returns: ["user"] - only users can be repository owners

readers := schema.RelationSubjects(types, "repository", "can_read")
// Returns: ["user", "organization"] - users and orgs can read repositories

func SubjectTypes

func SubjectTypes(types []TypeDefinition) []string

SubjectTypes returns all types that can be subjects in authorization checks. A type is a subject type if it appears in any relation's SubjectTypeRefs list. This is useful for understanding which types can be the "who" in permission checks.

Example:

types, _ := tooling.ParseSchema("schema.fga")
subjects := schema.SubjectTypes(types)
// Returns: ["user", "organization", "team"]

Types

type AuthzModel

type AuthzModel struct {
	ID               int64
	ObjectType       string  // Object type this rule applies to
	Relation         string  // Relation this rule defines
	SubjectType      *string // Allowed subject type (for direct rules)
	ImpliedBy        *string // Implying relation (for role hierarchy)
	ParentRelation   *string // Parent relation to check (for inheritance)
	ExcludedRelation *string // Relation to exclude (for "but not" rules)
	SubjectWildcard  *bool   // Whether wildcard subjects are allowed for SubjectType
	// Excluded parent relation for tuple-to-userset exclusions.
	ExcludedParentRelation *string // Parent relation to exclude (for "but not rel from parent")
	ExcludedParentType     *string // Linking relation for the excluded parent relation
	// New fields for userset references and intersection support
	SubjectRelation       *string // For userset refs [type#relation]: the relation part
	RuleGroupID           *int64  // Groups rules that form an intersection
	RuleGroupMode         *string // RuleGroupModeIntersection or RuleGroupModeExcludeIntersection
	CheckRelation         *string // For intersection: which relation to check
	CheckExcludedRelation *string // For intersection: exclusion on check_relation (e.g., "editor but not owner")
	CheckParentRelation   *string // For intersection: parent relation to check (tuple-to-userset)
	CheckParentType       *string // For intersection: linking relation on current object
}

AuthzModel represents an entry in the flattened authorization model. Each row defines one authorization rule that generated SQL evaluates.

The model stores normalized rules for efficient query execution.

Rule types:

• Direct: SubjectType is set, others NULL (user can have relation)
• Implied: ImpliedBy is set (having one relation grants another)
• Parent: ParentRelation and SubjectType set (inherit from parent object)
• Exclusive: ExcludedRelation set (permission denied if exclusion holds)
• Userset: SubjectType and SubjectRelation set (e.g., [group#member])
• Intersection: RuleGroupID and RuleGroupMode set (AND semantics)

func ToAuthzModels

func ToAuthzModels(types []TypeDefinition) []AuthzModel

ToAuthzModels converts parsed type definitions to database models. This is the critical transformation that enables permission checking.

The conversion performs transitive closure of implied_by relationships to support role hierarchies. For example, if owner → admin and admin → member, the closure ensures owner also implies member without explicit declaration.

Each AuthzModel row represents one authorization rule:

• Direct subject types: "repository.can_read allows user"
• Implied relations: "repository.can_read implied by can_write"
• Parent inheritance: "change.can_read from repository.can_read"
• Exclusions: "change.can_read but not is_author"
• Intersection groups: "viewer: writer and editor" (all must be satisfied)

The check_permission function queries these rows to evaluate permissions recursively, following the graph of implications and parent relationships.

type ClosureRow

type ClosureRow struct {
	ObjectType         string
	Relation           string
	SatisfyingRelation string
	ViaPath            []string // For debugging: path from relation to satisfying_relation
}

ClosureRow represents a precomputed relation closure row. The closure table is a critical optimization that precomputes transitive implied-by relationships at schema load time, eliminating the need for recursive function calls during permission checks.

Each row indicates that having satisfying_relation grants the relation on objects of object_type. For example, in a role hierarchy where owner -> admin -> member:

• {object_type: "repo", relation: "member", satisfying_relation: "owner"}
• {object_type: "repo", relation: "member", satisfying_relation: "admin"}
• {object_type: "repo", relation: "member", satisfying_relation: "member"}

This allows check_permission to evaluate "does user have member?" with a simple JOIN rather than recursive traversal: just check if they have ANY of the satisfying relations.

func ComputeRelationClosure

func ComputeRelationClosure(types []TypeDefinition) []ClosureRow

ComputeRelationClosure computes the transitive closure for all relations. For each relation, it finds all relations that can satisfy it (directly or transitively).

This is a build-time optimization. Without closure, check_permission would need recursive SQL functions to walk implied-by chains. With closure, a single JOIN against the inlined closure resolves the entire hierarchy.

Example: For schema owner -> admin -> member:

• member is satisfied by: member, admin, owner
• admin is satisfied by: admin, owner
• owner is satisfied by: owner

The closure table enables O(1) lookups instead of O(depth) recursion, which is critical for deeply nested role hierarchies.

type IntersectionGroup

type IntersectionGroup struct {
	Relations       []string              // Relations that must all be satisfied (AND)
	ParentRelations []ParentRelationCheck // Parent inheritance checks (tuple-to-userset)
	Exclusions      map[string][]string   // Per-relation exclusions: relation -> list of excluded relations
}

IntersectionGroup represents a group of relations that must ALL be satisfied. For "viewer: writer and editor", the group would be ["writer", "editor"]. For "viewer: writer and (editor but not owner)", the group would be ["writer", "editor"] with Exclusions["editor"] = ["owner"].

type ParentRelationCheck

type ParentRelationCheck struct {
	Relation        string // Relation to check on the parent object (e.g., "viewer")
	LinkingRelation string // Relation that links to the parent object (e.g., "parent")
}

ParentRelationCheck represents a tuple-to-userset (TTU) check. For "viewer from parent" on a folder type, this captures the TTU pattern.

Example: "viewer from parent" where parent: [folder]

• Relation: "viewer" (the relation to check on the parent object)
• LinkingRelation: "parent" (the relation that links to the parent object)

The actual parent type(s) are determined at runtime by looking up what types the linking relation can point to.

type RelationDefinition

type RelationDefinition struct {
	Name              string   // Relation name: "owner", "can_read", etc.
	ImpliedBy         []string // Relations that imply this one: ["owner", "admin"]
	ParentRelations   []ParentRelationCheck
	ExcludedRelations []string // For nested exclusions: "(a but not b) but not c" -> ["b", "c"]
	// ExcludedParentRelations captures tuple-to-userset exclusions like "but not viewer from parent".
	ExcludedParentRelations []ParentRelationCheck
	// ExcludedIntersectionGroups captures exclusions that require ALL relations in a group.
	// For "viewer: writer but not (editor and owner)", this is [[editor, owner]].
	ExcludedIntersectionGroups []IntersectionGroup
	// SubjectTypeRefs provides detailed subject type info including userset relations.
	// For [user, group#member], this would contain:
	//   - {Type: "user", Relation: ""}
	//   - {Type: "group", Relation: "member"}
	SubjectTypeRefs []SubjectTypeRef
	// IntersectionGroups contains groups of relations that must ALL be satisfied.
	// Each group is an AND (intersection), multiple groups are OR'd together.
	// For "viewer: writer and editor", IntersectionGroups = [["writer", "editor"]]
	// For "viewer: (a and b) or (c and d)", IntersectionGroups = [["a","b"], ["c","d"]]
	IntersectionGroups []IntersectionGroup
}

RelationDefinition represents a parsed relation. Relations describe who can have what relationship with an object.

A relation can be:

• Direct: explicitly granted via tuples (SubjectTypeRefs)
• Implied: granted by having another relation (ImpliedBy)
• Inherited: derived from a parent object (ParentRelations)
• Exclusive: granted except for excluded subjects (ExcludedRelations)
• Userset: granted via group membership (SubjectTypeRefs with Relation set)
• Intersection: granted if ALL relations in a group are satisfied

type SubjectTypeRef

type SubjectTypeRef struct {
	Type     string // Subject type: "user", "group", etc.
	Relation string // For userset refs: the relation (e.g., "member" in [group#member])
	Wildcard bool   // True if this is a wildcard reference (user:*)
}

SubjectTypeRef represents a subject type reference in a relation definition. For userset references like [group#member], Type is "group" and Relation is "member". For direct references like [user], Type is "user" and Relation is empty.

type TypeDefinition

type TypeDefinition struct {
	Name      string
	Relations []RelationDefinition
}

TypeDefinition represents a parsed type from an .fga file. Each type definition describes an object type (user, repository, etc.) and the relations that can exist on objects of that type.

type UsersetRule

type UsersetRule struct {
	ObjectType                string
	Relation                  string
	TupleRelation             string
	SubjectType               string
	SubjectRelation           string
	SubjectRelationSatisfying string
}

UsersetRule represents a precomputed userset rule with relation closure applied. Userset rules handle permissions granted via group membership, expressed in OpenFGA as [group#member]. Unlike direct subject types where the tuple directly grants permission, usersets require checking if the subject has the specified relation on the group object.

Each row means: a tuple with tuple_relation on object_type can satisfy relation when the tuple subject is subject_type#subject_relation.

The rules are precomputed by expanding userset references through the relation closure data. This allows SQL to resolve userset permissions efficiently without nested subqueries for each implied relation.

Example: For "viewer: [group#member]" where admin->member, the rules include:

• {relation: "viewer", tuple_relation: "viewer", subject_type: "group", subject_relation: "member", subject_relation_satisfying: "member"}
• {relation: "viewer", tuple_relation: "viewer", subject_type: "group", subject_relation: "member", subject_relation_satisfying: "admin"}

This enables check_permission to match tuples where the subject has either member or admin on the group, without recursive relation resolution at query time.

func ToUsersetRules

func ToUsersetRules(types []TypeDefinition, closureRows []ClosureRow) []UsersetRule

ToUsersetRules expands userset references using the relation closure. This precomputes which tuple relations can satisfy a target relation for userset rules.

The expansion combines two sources of transitivity:

1. Object relation closure: viewer might be satisfied by editor (implied-by)
2. Subject relation closure: member might be satisfied by admin (implied-by)

By precomputing the cross-product of these closures, SQL can match userset permissions with a simple JOIN instead of recursive CTEs for each check.

This is analogous to ComputeRelationClosure but handles the subject-side relation traversal required for userset references.