query

package
v1.49.2 Latest Latest
Warning

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

 Go to latest Published: Feb 27, 2026 License: Apache-2.0 Imports: 25 Imported by: 0

README

Query Package

The query package implements SpiceDB's query plan system for evaluating permissions and relationships. It provides a tree-based iterator architecture for efficient graph traversal and permission checking.

Overview

Query plans are built from schema definitions and executed to answer three fundamental questions:

  1. Check: Does a specific subject have access to a resource?
  2. IterSubjects: Which subjects have access to a given resource?
  3. IterResources: Which resources can a given subject access?

Each iterator in the tree implements these three methods, allowing complex permission queries to be evaluated by composing simple operations.

Iterator Types

Iterators are organized into several categories based on their role in the query plan:

Iterator Description
LEAF ITERATORS Data source iterators with no subiterators
DatastoreIterator Queries the datastore for stored relationships. The fundamental data source for all queries.
FixedIterator Contains pre-computed paths. Used in testing and as frontier in recursive queries.
SelfIterator Produces reflexive relations (object→object). Used for self keyword checks.
RecursiveSentinelIterator Placeholder marking recursion points during tree construction. Replaced at runtime.
UNARY ITERATORS Wrap a single child iterator
AliasIterator Rewrites the relation field of paths. Maps computed permissions to their defining relation.
BINARY ITERATORS Combine two child iterators
ArrowIterator Graph walk operator (→). Chains two iterators for path composition.
IntersectionArrowIterator Conditional intersection. Implements all() semantics - ALL left subjects must satisfy right.
ExclusionIterator Set difference (-). Removes excluded paths from main set.
N-ARY ITERATORS Combine multiple child iterators
UnionIterator Logical OR (|). Concatenates results from all children with deduplication.
IntersectionIterator Logical AND (&). Intersects results from all children.
FILTER ITERATORS Apply filtering conditions to results
CaveatIterator Evaluates caveat conditions on paths. Filters results based on runtime context.
CONTROL FLOW ITERATORS Manage execution flow and recursion
RecursiveIterator Manages recursive schema definitions with and represents the transitive closure operation.

Key Concepts

Iterator Interface

All iterators implement the Iterator interface with these core methods:

type Iterator interface {
    // Evaluation methods
    CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)
    IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)
    IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

    // Tree navigation
    Clone() Iterator
    Subiterators() []Iterator
    ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

    // Metadata
    ID() string
    Explain() Explain
    ResourceType() ([]ObjectType, error)
    SubjectTypes() ([]ObjectType, error)
}
Path Sequences

Results are returned as PathSeq (Go 1.23 iterators - iter.Seq2[Path, error]), allowing lazy evaluation and streaming of results without materializing entire result sets in memory.

Context

The Context type carries execution state including:

  • Datastore reader
  • Optional trace logger for debugging
  • Execution depth tracking
  • Analysis/statistics collection

Usage Example

// Build a query plan from schema
it, err := BuildIteratorFromSchema(schema, "document", "viewer")

// Create execution context
ctx := NewContext(datastoreReader)

// Execute a check query
resources := []Object{NewObject("document", "doc1")}
subject := NewObject("user", "alice").WithEllipses()

pathSeq, err := ctx.Check(it, resources, subject)
for path, err := range pathSeq {
    if err != nil {
        return err
    }
    // Process path...
}

Documentation

Overview

This package provides the structures, interfaces, and functions for a sort of Lego-set to build query trees. It should depend on as few other packages as possible, as in the longer future, these can be passed around a lot, and refactoring to reduce import loops is a pain.

The underlying philosophy of a query plan is that we build query trees out of iterators. Iterators are nodes in the tree and represent a logical set of valid relations that match or don't match.

Take the example schema: 

definition foo {
  relation bar: foo
}

For example, the simplest set is that of `bar` -- all relationships written directly with `bar` as the Relation type, `foo:a#bar@foo:b#...`

But by combining different operations on these sets, we can invent arbitrary permissions, using standard set operations like And and Or, along with a few special ones that come from relational algebra, like Arrow (as a form of the Join operation).

Index

Constants

This section is empty.

Variables

View Source 
var StaticOptimizations = []OptimizerFunc{
	WrapOptimizer(PushdownCaveatEvaluation),
}

Functions

func FormatAnalysis added in v1.49.0 

func FormatAnalysis(tree Iterator, analyze map[CanonicalKey]AnalyzeStats) string

FormatAnalysis returns a formatted string showing the iterator tree with execution statistics for each iterator. Stats are looked up by iterator canonical key from the analyze map.

func ObjectAndRelationKey added in v1.46.1 

func ObjectAndRelationKey(oar ObjectAndRelation) string

ObjectAndRelationKey returns a unique string key for an ObjectAndRelation

func OutlineCompare added in v1.49.2 

func OutlineCompare(a, b Outline) int

OutlineCompare defines a total ordering on Outline for canonicalization. Returns -1 if a < b, 0 if a == b, 1 if a > b. Compatible with slices.SortFunc.

func PathOrder added in v1.49.2 

func PathOrder(a, b Path) int

PathOrder defines ordering for Path objects Returns -1 if a < b, 0 if a == b, 1 if a > b

Compatible with slices.SortFunc.

func SimplifyCaveatExpression added in v1.46.1 

func SimplifyCaveatExpression(
	ctx context.Context,
	runner *caveats.CaveatRunner,
	expr *core.CaveatExpression,
	context map[string]any,
	reader caveats.CaveatDefinitionLookup,
) (*core.CaveatExpression, bool, error)

SimplifyCaveatExpression simplifies a caveat expression by applying AND/OR logic and running them with a CaveatRunner if they match the expected caveat: - For AND: if a caveat evaluates to true, remove it from the expression - For OR: if a caveat evaluates to true, the entire expression becomes true Returns:

  • simplified: the simplified expression (nil if unconditionally true)
  • passes: true if passes unconditionally or conditionally, false if fails
  • error: any error that occurred during simplification

Types

type AliasIterator added in v1.49.2 

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

AliasIterator is an iterator that rewrites the Resource's Relation field of all paths streamed from the sub-iterator to a specified alias relation.

func NewAliasIterator added in v1.49.2 

func NewAliasIterator(relation string, subIt Iterator) *AliasIterator

NewAliasIterator creates a new Alias iterator that rewrites paths from the sub-iterator to use the specified relation name.

func (*AliasIterator) CanonicalKey added in v1.49.2 

func (a *AliasIterator) CanonicalKey() CanonicalKey

func (*AliasIterator) CheckImpl added in v1.49.2 

func (a *AliasIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

func (*AliasIterator) Clone added in v1.49.2 

func (a *AliasIterator) Clone() Iterator

func (*AliasIterator) Explain added in v1.49.2 

func (a *AliasIterator) Explain() Explain

func (*AliasIterator) IterResourcesImpl added in v1.49.2 

func (a *AliasIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

func (*AliasIterator) IterSubjectsImpl added in v1.49.2 

func (a *AliasIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

func (*AliasIterator) ReplaceSubiterators added in v1.49.2 

func (a *AliasIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*AliasIterator) ResourceType added in v1.49.2 

func (a *AliasIterator) ResourceType() ([]ObjectType, error)

func (*AliasIterator) Subiterators added in v1.49.2 

func (a *AliasIterator) Subiterators() []Iterator

func (*AliasIterator) SubjectTypes added in v1.49.2 

func (a *AliasIterator) SubjectTypes() ([]ObjectType, error)

type AnalyzeObserver added in v1.49.2 

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

AnalyzeObserver is a thread-safe Observer that collects execution statistics keyed by CanonicalKey.

func NewAnalyzeObserver added in v1.49.2 

func NewAnalyzeObserver() *AnalyzeObserver

NewAnalyzeObserver creates a new thread-safe analyze observer.

func (*AnalyzeObserver) GetStats added in v1.49.2 

func (a *AnalyzeObserver) GetStats() map[CanonicalKey]AnalyzeStats

GetStats returns a copy of all collected stats.

func (*AnalyzeObserver) ObserveEnterIterator added in v1.49.2 

func (a *AnalyzeObserver) ObserveEnterIterator(op ObserverOperation, key CanonicalKey)

ObserveEnterIterator increments the call counter and records the start time.

func (*AnalyzeObserver) ObservePath added in v1.49.2 

func (a *AnalyzeObserver) ObservePath(op ObserverOperation, key CanonicalKey, _ Path)

ObservePath increments the result counter for the given iterator key and operation.

func (*AnalyzeObserver) ObserveReturnIterator added in v1.49.2 

func (a *AnalyzeObserver) ObserveReturnIterator(op ObserverOperation, key CanonicalKey)

ObserveReturnIterator records elapsed time since ObserveEnterIterator was called.

type AnalyzeStats added in v1.49.0 

type AnalyzeStats struct {
	CheckCalls           int
	IterSubjectsCalls    int
	IterResourcesCalls   int
	CheckResults         int
	IterSubjectsResults  int
	IterResourcesResults int
	CheckTime            time.Duration
	IterSubjectsTime     time.Duration
	IterResourcesTime    time.Duration
}

AnalyzeStats collects the number of operations performed for each iterator as a query takes place.

func AggregateAnalyzeStats added in v1.49.0 

func AggregateAnalyzeStats(analyze map[CanonicalKey]AnalyzeStats) AnalyzeStats

AggregateAnalyzeStats combines all the analyze stats from a map into a single aggregated AnalyzeStats. This is useful for getting total counts across all iterators in a query execution.

type ArrowIterator added in v1.49.2 

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

ArrowIterator is an iterator that represents the set of paths that follow from a walk in the graph.

Ex: `folder->owner` and `left->right`

func NewArrowIterator added in v1.49.2 

func NewArrowIterator(left, right Iterator) *ArrowIterator

func NewSchemaArrow added in v1.49.1 

func NewSchemaArrow(left, right Iterator) *ArrowIterator

func (*ArrowIterator) CanonicalKey added in v1.49.2 

func (a *ArrowIterator) CanonicalKey() CanonicalKey

func (*ArrowIterator) CheckImpl added in v1.49.2 

func (a *ArrowIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

func (*ArrowIterator) Clone added in v1.49.2 

func (a *ArrowIterator) Clone() Iterator

func (*ArrowIterator) Explain added in v1.49.2 

func (a *ArrowIterator) Explain() Explain

func (*ArrowIterator) IterResourcesImpl added in v1.49.2 

func (a *ArrowIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

func (*ArrowIterator) IterSubjectsImpl added in v1.49.2 

func (a *ArrowIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

func (*ArrowIterator) ReplaceSubiterators added in v1.49.2 

func (a *ArrowIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*ArrowIterator) ResourceType added in v1.49.2 

func (a *ArrowIterator) ResourceType() ([]ObjectType, error)

func (*ArrowIterator) Subiterators added in v1.49.2 

func (a *ArrowIterator) Subiterators() []Iterator

func (*ArrowIterator) SubjectTypes added in v1.49.2 

func (a *ArrowIterator) SubjectTypes() ([]ObjectType, error)

type CanonicalKey added in v1.49.2 

type CanonicalKey string

CanonicalKey is a unique string identifier for a canonical Outline subtree. It is computed after canonicalization and represents the entire structure in a compact, deterministic format.

func (CanonicalKey) Hash added in v1.49.2 

func (k CanonicalKey) Hash() uint64

Hash returns a hash fingerprint of the key for use in maps

func (CanonicalKey) IsEmpty added in v1.49.2 

func (k CanonicalKey) IsEmpty() bool

IsEmpty returns true if the key is empty (not yet computed)

func (CanonicalKey) String added in v1.49.2 

func (k CanonicalKey) String() string

String returns the string representation of the key

type CanonicalOutline added in v1.49.2 

type CanonicalOutline struct {
	Root          Outline
	CanonicalKeys map[OutlineNodeID]CanonicalKey
}

CanonicalOutline is an Outline tree that has been fully canonicalized. It pairs the root Outline (with every node's ID assigned) with a map from those IDs to their CanonicalKeys. Only CanonicalOutlines can be Compiled, ensuring every iterator in the resulting tree receives its canonical key.

func BuildOutlineFromSchema added in v1.49.2 

func BuildOutlineFromSchema(fullSchema *schema.Schema, definitionName string, relationName string) (CanonicalOutline, error)

BuildOutlineFromSchema builds a canonical Outline tree from the schema.

func CanonicalizeOutline added in v1.49.2 

func CanonicalizeOutline(outline Outline) (CanonicalOutline, error)

CanonicalizeOutline transforms an Outline into canonical form, returning a CanonicalOutline that pairs the transformed tree with a map of node IDs to their CanonicalKeys.

The canonicalization process has two phases: 1. Filter Lifting: Extract all caveats, sort them, and nest them at the top 2. Bottom-Up Canonicalization: Apply five transformation steps sequentially

The function is idempotent: applying it multiple times produces the same result.

func (CanonicalOutline) Compile added in v1.49.2 

func (co CanonicalOutline) Compile() (Iterator, error)

Compile converts a CanonicalOutline into the actual Iterator representation. All iterators in the resulting tree have their canonical keys set.

type CaveatIterator added in v1.46.1 

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

CaveatIterator wraps another iterator and applies caveat evaluation to its results. It checks caveat conditions on relationships during iteration and only yields relationships that satisfy the caveat constraints.

func NewCaveatIterator added in v1.46.1 

func NewCaveatIterator(subiterator Iterator, caveat *core.ContextualizedCaveat) *CaveatIterator

NewCaveatIterator creates a new caveat iterator that wraps the given subiterator and applies the specified caveat conditions.

func (*CaveatIterator) CanonicalKey added in v1.49.2 

func (c *CaveatIterator) CanonicalKey() CanonicalKey

func (*CaveatIterator) CheckImpl added in v1.46.1 

func (c *CaveatIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

func (*CaveatIterator) Clone added in v1.46.1 

func (c *CaveatIterator) Clone() Iterator

func (*CaveatIterator) Explain added in v1.46.1 

func (c *CaveatIterator) Explain() Explain

func (*CaveatIterator) IterResourcesImpl added in v1.46.1 

func (c *CaveatIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

func (*CaveatIterator) IterSubjectsImpl added in v1.46.1 

func (c *CaveatIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

func (*CaveatIterator) ReplaceSubiterators added in v1.46.1 

func (c *CaveatIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*CaveatIterator) ResourceType added in v1.49.0 

func (c *CaveatIterator) ResourceType() ([]ObjectType, error)

func (*CaveatIterator) Subiterators added in v1.46.1 

func (c *CaveatIterator) Subiterators() []Iterator

func (*CaveatIterator) SubjectTypes added in v1.49.0 

func (c *CaveatIterator) SubjectTypes() ([]ObjectType, error)

type Context 

type Context struct {
	context.Context
	Executor          Executor
	Reader            datalayer.RevisionedReader // Datastore reader for this query at a specific revision
	CaveatContext     map[string]any
	CaveatRunner      *caveats.CaveatRunner
	TraceLogger       *TraceLogger // For debugging iterator execution (used by TraceStep calls inside iterators)
	MaxRecursionDepth int          // Maximum depth for recursive iterators (0 = use default of 10)

	// Pagination options for IterSubjects and IterResources
	PaginationCursors map[string]*tuple.Relationship // Cursors for pagination, keyed by iterator ID
	PaginationLimit   *uint64                        // Limit for pagination (max number of results to return)
	PaginationSort    options.SortOrder              // Sort order for pagination
	// contains filtered or unexported fields
}

Context represents a single execution of a query. It is both a standard context.Context and all the query-time specific handles needed to evaluate a query, such as which datastore it is running against.

Context is the concrete type that contains the overall handles, and uses the executor as a strategy for continuing execution.

func NewLocalContext added in v1.49.0 

func NewLocalContext(stdContext context.Context, opts ...ContextOption) *Context

NewLocalContext creates a new query execution context with a LocalExecutor. This is a convenience constructor for tests and local execution scenarios.

func (*Context) Check 

func (ctx *Context) Check(it Iterator, resources []Object, subject ObjectAndRelation) (PathSeq, error)

Check tests if, for the underlying set of relationships (which may be a full expression or a basic lookup, depending on the iterator) any of the `resources` are connected to `subject`. Returns the sequence of matching paths, if they exist, at most `len(resources)`.

func (*Context) CollectFrontierObject added in v1.49.2 

func (ctx *Context) CollectFrontierObject(iteratorID uint64, obj Object)

CollectFrontierObject appends an object to the frontier collection. Only appends if collection mode is enabled (non-nil entry exists).

func (*Context) EnableFrontierCollection added in v1.49.2 

func (ctx *Context) EnableFrontierCollection(iteratorID uint64)

EnableFrontierCollection enables frontier collection for a RecursiveIterator. Creates a non-nil entry in the map, which signals collection mode.

func (*Context) ExtractFrontierCollection added in v1.49.2 

func (ctx *Context) ExtractFrontierCollection(iteratorID uint64) []Object

ExtractFrontierCollection retrieves and removes the collected frontier.

func (*Context) GetPaginationCursor added in v1.49.2 

func (ctx *Context) GetPaginationCursor(iteratorID string) *tuple.Relationship

GetPaginationCursor retrieves the cursor for a specific iterator ID.

func (*Context) IsCollectingFrontier added in v1.49.2 

func (ctx *Context) IsCollectingFrontier(iteratorID uint64) bool

IsCollectingFrontier checks if collection mode is enabled (non-nil entry exists).

func (*Context) IterResources 

func (ctx *Context) IterResources(it Iterator, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

IterResources returns a sequence of all the relations in this set that match the given subject. The filterResourceType parameter filters results to only include resources matching the specified ObjectType. If filterResourceType.Type is empty, no filtering is applied.

func (*Context) IterSubjects 

func (ctx *Context) IterSubjects(it Iterator, resource Object, filterSubjectType ObjectType) (PathSeq, error)

IterSubjects returns a sequence of all the paths in this set that match the given resource. The filterSubjectType parameter filters results to only include subjects matching the specified ObjectType. If filterSubjectType.Type is empty, no filtering is applied.

func (*Context) SetPaginationCursor added in v1.49.2 

func (ctx *Context) SetPaginationCursor(iteratorID string, cursor *tuple.Relationship)

SetPaginationCursor sets the cursor for a specific iterator ID.

func (*Context) TraceEnter added in v1.46.1 

func (ctx *Context) TraceEnter(it Iterator, traceString string)

func (*Context) TraceExit added in v1.46.1 

func (ctx *Context) TraceExit(it Iterator, paths []Path)

func (*Context) TraceStep added in v1.46.1 

func (ctx *Context) TraceStep(it Iterator, step string, data ...any)

type ContextOption added in v1.49.0 

type ContextOption func(*Context)

ContextOption is a function that configures a Context.

func WithCaveatContext added in v1.49.0 

func WithCaveatContext(caveatCtx map[string]any) ContextOption

WithCaveatContext sets the caveat context for the context.

func WithCaveatRunner added in v1.49.0 

func WithCaveatRunner(runner *caveats.CaveatRunner) ContextOption

WithCaveatRunner sets the caveat runner for the context.

func WithMaxRecursionDepth added in v1.49.0 

func WithMaxRecursionDepth(depth int) ContextOption

WithMaxRecursionDepth sets the maximum recursion depth for the context.

func WithObserver added in v1.49.2 

func WithObserver(o Observer) ContextOption

WithObserver adds an Observer to the context.

func WithPaginationLimit added in v1.49.2 

func WithPaginationLimit(limit uint64) ContextOption

WithPaginationLimit sets the pagination limit for the context.

func WithPaginationSort added in v1.49.2 

func WithPaginationSort(sort options.SortOrder) ContextOption

WithPaginationSort sets the pagination sort order for the context.

func WithReader added in v1.49.0 

func WithReader(reader datalayer.RevisionedReader) ContextOption

WithReader sets the datastore reader for the context.

func WithTraceLogger added in v1.49.0 

func WithTraceLogger(logger *TraceLogger) ContextOption

WithTraceLogger sets the trace logger for the context.

type DatastoreIterator added in v1.49.2 

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

DatastoreIterator is a common leaf iterator. It represents the set of all relationships of the given schema.BaseRelation, ie, relations that have a known resource and subject type and may contain caveats or expiration.

The DatastoreIterator, being the leaf, generates this set by calling the datastore.

func NewDatastoreIterator added in v1.49.2 

func NewDatastoreIterator(base *schema.BaseRelation) *DatastoreIterator

func (*DatastoreIterator) CanonicalKey added in v1.49.2 

func (r *DatastoreIterator) CanonicalKey() CanonicalKey

func (*DatastoreIterator) CheckImpl added in v1.49.2 

func (r *DatastoreIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

func (*DatastoreIterator) Clone added in v1.49.2 

func (r *DatastoreIterator) Clone() Iterator

func (*DatastoreIterator) Explain added in v1.49.2 

func (r *DatastoreIterator) Explain() Explain

func (*DatastoreIterator) IterResourcesImpl added in v1.49.2 

func (r *DatastoreIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

func (*DatastoreIterator) IterSubjectsImpl added in v1.49.2 

func (r *DatastoreIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

func (*DatastoreIterator) ReplaceSubiterators added in v1.49.2 

func (r *DatastoreIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*DatastoreIterator) ResourceType added in v1.49.2 

func (r *DatastoreIterator) ResourceType() ([]ObjectType, error)

func (*DatastoreIterator) Subiterators added in v1.49.2 

func (r *DatastoreIterator) Subiterators() []Iterator

func (*DatastoreIterator) SubjectTypes added in v1.49.2 

func (r *DatastoreIterator) SubjectTypes() ([]ObjectType, error)

type Estimate added in v1.48.0 

type Estimate struct {
	Cardinality int // Cardinality is the estimated number of results this iterator will produce.

	// CheckSelectivity is the estimated probability (0.0-1.0) that a Check operation
	// will return true. Higher values mean the check is more likely to pass.
	CheckSelectivity float64

	// CheckCost is the estimated cost to perform a Check operation on this iterator.
	// This represents the computational cost of verifying if a specific resource-subject
	// relationship exists.
	CheckCost int

	// IterResourcesCost is the estimated cost to iterate over all resources
	// accessible through this iterator.
	IterResourcesCost int

	// IterSubjectsCost is the estimated cost to iterate over all subjects
	// that have access through this iterator.
	IterSubjectsCost int
}

Estimate represents the estimated worst-case cost and selectivity metrics for an iterator. These estimates are used by the query optimizer to make decisions about query plan structure.

Costs are a completely made-up unit, relevant only to the source of the statistics. They are not portable between different statistics sources, and are only comparable to each other. However, something of zero-cost is rare (and often useless), so a good value for a cost is on the range (1, MAXINT)

type ExclusionIterator added in v1.49.2 

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

ExclusionIterator represents the set of relations that are in the mainSet but not in the excluded set. This is equivalent to `permission foo = bar - baz`

func NewExclusionIterator added in v1.49.2 

func NewExclusionIterator(mainSet, excluded Iterator) *ExclusionIterator

func (*ExclusionIterator) CanonicalKey added in v1.49.2 

func (e *ExclusionIterator) CanonicalKey() CanonicalKey

func (*ExclusionIterator) CheckImpl added in v1.49.2 

func (e *ExclusionIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

func (*ExclusionIterator) Clone added in v1.49.2 

func (e *ExclusionIterator) Clone() Iterator

func (*ExclusionIterator) Explain added in v1.49.2 

func (e *ExclusionIterator) Explain() Explain

func (*ExclusionIterator) IterResourcesImpl added in v1.49.2 

func (e *ExclusionIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

func (*ExclusionIterator) IterSubjectsImpl added in v1.49.2 

func (e *ExclusionIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

func (*ExclusionIterator) ReplaceSubiterators added in v1.49.2 

func (e *ExclusionIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*ExclusionIterator) ResourceType added in v1.49.2 

func (e *ExclusionIterator) ResourceType() ([]ObjectType, error)

func (*ExclusionIterator) Subiterators added in v1.49.2 

func (e *ExclusionIterator) Subiterators() []Iterator

func (*ExclusionIterator) SubjectTypes added in v1.49.2 

func (e *ExclusionIterator) SubjectTypes() ([]ObjectType, error)

type Executor 

type Executor interface {
	// Check tests if, for the underlying set of relationships (which may be a full expression or a basic lookup, depending on the iterator)
	// any of the `resources` are connected to `subject`.
	// Returns the sequence of matching relations, if they exist, at most `len(resources)`.
	Check(ctx *Context, it Iterator, resources []Object, subject ObjectAndRelation) (PathSeq, error)

	// IterSubjects returns a sequence of all the relations in this set that match the given resource.
	// The filterSubjectType parameter filters results to only include subjects matching the
	// specified ObjectType. If filterSubjectType.Type is empty, no filtering is applied.
	IterSubjects(ctx *Context, it Iterator, resource Object, filterSubjectType ObjectType) (PathSeq, error)

	// IterResources returns a sequence of all the relations in this set that match the given subject.
	// The filterResourceType parameter filters results to only include resources matching the
	// specified ObjectType. If filterResourceType.Type is empty, no filtering is applied.
	IterResources(ctx *Context, it Iterator, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)
}

Executor as chooses how to proceed given an iterator -- perhaps in parallel, perhaps by RPC, etc -- and chooses how to process iteration from the subtree. The correctness logic for the results that are generated are up to each iterator, and each iterator may use statistics to choose the best, yet still correct, logical evaluation strategy. The Executor, meanwhile, makes that evaluation happen in the most convienent form, based on its implementation.

type Explain 

type Explain struct {
	Name       string // Short name for tracing (e.g., "Arrow", "Union")
	Info       string // Full info for display
	SubExplain []Explain
}

Explain describes the state of an iterator tree, in a human-readable fashion, with an Info line at each node.

TODO: This can be extended with other interesting stats about the tree.

func (Explain) IndentString 

func (e Explain) IndentString(depth int) string

IndentString pretty-prints an Explain tree with a given indentation.

func (Explain) String 

func (e Explain) String() string

type FaultyIterator 

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

FaultyIterator is a test helper that simulates iterator errors

func NewFaultyIterator 

func NewFaultyIterator(shouldFailOnCheck, shouldFailOnCollect bool, resourceType ObjectType, subjectTypes []ObjectType) *FaultyIterator

NewFaultyIterator creates a new FaultyIterator for testing error conditions

func (*FaultyIterator) CanonicalKey added in v1.49.2 

func (f *FaultyIterator) CanonicalKey() CanonicalKey

func (*FaultyIterator) CheckImpl 

func (f *FaultyIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

func (*FaultyIterator) Clone 

func (f *FaultyIterator) Clone() Iterator

func (*FaultyIterator) Explain 

func (f *FaultyIterator) Explain() Explain

func (*FaultyIterator) IterResourcesImpl 

func (f *FaultyIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

func (*FaultyIterator) IterSubjectsImpl 

func (f *FaultyIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

func (*FaultyIterator) ReplaceSubiterators added in v1.46.1 

func (f *FaultyIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*FaultyIterator) ResourceType added in v1.49.0 

func (f *FaultyIterator) ResourceType() ([]ObjectType, error)

func (*FaultyIterator) Subiterators added in v1.46.1 

func (f *FaultyIterator) Subiterators() []Iterator

func (*FaultyIterator) SubjectTypes added in v1.49.0 

func (f *FaultyIterator) SubjectTypes() ([]ObjectType, error)

type FixedIterator 

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

For example: document->folder->ownerGroup->user -- and we'd like to find all documents (IterResources) that traverse a known folder->ownerGroup relationship

func NewDocumentAccessFixedIterator 

func NewDocumentAccessFixedIterator() *FixedIterator

NewDocumentAccessFixedIterator creates a FixedIterator with typical document access patterns

func NewEmptyFixedIterator 

func NewEmptyFixedIterator() *FixedIterator

NewEmptyFixedIterator creates an empty FixedIterator for testing edge cases

func NewFixedIterator 

func NewFixedIterator(paths ...Path) *FixedIterator

func NewFolderHierarchyFixedIterator 

func NewFolderHierarchyFixedIterator() *FixedIterator

NewFolderHierarchyFixedIterator creates a FixedIterator with folder hierarchy relations

func NewLargeFixedIterator 

func NewLargeFixedIterator() *FixedIterator

NewLargeFixedIterator creates a FixedIterator with many relations for performance testing

func NewMultiRoleFixedIterator 

func NewMultiRoleFixedIterator() *FixedIterator

NewMultiRoleFixedIterator creates a FixedIterator where users have multiple roles on the same resources

func NewSingleUserFixedIterator 

func NewSingleUserFixedIterator(userID string) *FixedIterator

NewSingleUserFixedIterator creates a FixedIterator with relations for a single user across multiple resources

func (*FixedIterator) CanonicalKey added in v1.49.2 

func (f *FixedIterator) CanonicalKey() CanonicalKey

func (*FixedIterator) CheckImpl 

func (f *FixedIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

func (*FixedIterator) Clone 

func (f *FixedIterator) Clone() Iterator

func (*FixedIterator) Explain 

func (f *FixedIterator) Explain() Explain

func (*FixedIterator) IterResourcesImpl 

func (f *FixedIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

func (*FixedIterator) IterSubjectsImpl 

func (f *FixedIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

func (*FixedIterator) ReplaceSubiterators added in v1.46.1 

func (f *FixedIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*FixedIterator) ResourceType added in v1.49.0 

func (f *FixedIterator) ResourceType() ([]ObjectType, error)

func (*FixedIterator) Subiterators added in v1.46.1 

func (f *FixedIterator) Subiterators() []Iterator

func (*FixedIterator) SubjectTypes added in v1.49.0 

func (f *FixedIterator) SubjectTypes() ([]ObjectType, error)

type IntersectionArrowIterator added in v1.49.2 

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

IntersectionArrowIterator is an iterator that represents the set of relations that follow from a walk in the graph where ALL subjects on the left must satisfy the right side condition.

Ex: `group.all(member)` - user must be member of ALL groups

func NewIntersectionArrowIterator added in v1.49.2 

func NewIntersectionArrowIterator(left, right Iterator) *IntersectionArrowIterator

func (*IntersectionArrowIterator) CanonicalKey added in v1.49.2 

func (ia *IntersectionArrowIterator) CanonicalKey() CanonicalKey

func (*IntersectionArrowIterator) CheckImpl added in v1.49.2 

func (ia *IntersectionArrowIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

func (*IntersectionArrowIterator) Clone added in v1.49.2 

func (ia *IntersectionArrowIterator) Clone() Iterator

func (*IntersectionArrowIterator) Explain added in v1.49.2 

func (ia *IntersectionArrowIterator) Explain() Explain

func (*IntersectionArrowIterator) IterResourcesImpl added in v1.49.2 

func (ia *IntersectionArrowIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

func (*IntersectionArrowIterator) IterSubjectsImpl added in v1.49.2 

func (ia *IntersectionArrowIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

func (*IntersectionArrowIterator) ReplaceSubiterators added in v1.49.2 

func (ia *IntersectionArrowIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*IntersectionArrowIterator) ResourceType added in v1.49.2 

func (ia *IntersectionArrowIterator) ResourceType() ([]ObjectType, error)

func (*IntersectionArrowIterator) Subiterators added in v1.49.2 

func (ia *IntersectionArrowIterator) Subiterators() []Iterator

func (*IntersectionArrowIterator) SubjectTypes added in v1.49.2 

func (ia *IntersectionArrowIterator) SubjectTypes() ([]ObjectType, error)

type IntersectionIterator added in v1.49.2 

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

IntersectionIterator the set of paths that are in all of underlying subiterators. This is equivalent to `permission foo = bar & baz`

func (*IntersectionIterator) CanonicalKey added in v1.49.2 

func (i *IntersectionIterator) CanonicalKey() CanonicalKey

func (*IntersectionIterator) CheckImpl added in v1.49.2 

func (i *IntersectionIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

func (*IntersectionIterator) Clone added in v1.49.2 

func (i *IntersectionIterator) Clone() Iterator

func (*IntersectionIterator) Explain added in v1.49.2 

func (i *IntersectionIterator) Explain() Explain

func (*IntersectionIterator) IterResourcesImpl added in v1.49.2 

func (i *IntersectionIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

func (*IntersectionIterator) IterSubjectsImpl added in v1.49.2 

func (i *IntersectionIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

func (*IntersectionIterator) ReplaceSubiterators added in v1.49.2 

func (i *IntersectionIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*IntersectionIterator) ResourceType added in v1.49.2 

func (i *IntersectionIterator) ResourceType() ([]ObjectType, error)

func (*IntersectionIterator) Subiterators added in v1.49.2 

func (i *IntersectionIterator) Subiterators() []Iterator

func (*IntersectionIterator) SubjectTypes added in v1.49.2 

func (i *IntersectionIterator) SubjectTypes() ([]ObjectType, error)

type Iterator 

type Iterator interface {
	Plan

	// Clone does a deep-copy to duplicate the iterator tree at this point.
	Clone() Iterator

	// Subiterators returns the child iterators of this iterator, if any.
	// Returns nil or empty slice for leaf iterators.
	Subiterators() []Iterator

	// ReplaceSubiterators returns a new iterator with the given subiterators replacing the current ones.
	// This method always returns a new iterator instance.
	// For leaf iterators (those with no subiterators), this returns an error.
	// For composite iterators, the length of newSubs should match the length of Subiterators().
	// Returns an error if the replacement fails or if the length of newSubs doesn't match expectations.
	ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

	// CanonicalKey returns the canonical key for this iterator.
	// Cloned iterators share the same canonical key since they represent the same query plan node.
	CanonicalKey() CanonicalKey

	// ResourceType returns the ObjectType(s) of this iterator's resources.
	// Returns a slice to support iterators that can return multiple types (e.g., unions).
	ResourceType() ([]ObjectType, error)

	// SubjectTypes returns all the ObjectTypes for this iterator tree.
	// Returns an error if subject types cannot be determined.
	SubjectTypes() ([]ObjectType, error)
}

Iterator is a Plan that forms a tree structure through its Subiterators, where the tree represents the query execution plan that can be traversed and optimized. While Plan provides a read-only query interface, Iterator adds methods for cloning, inspecting, and rebuilding iterator trees. This enables query optimization by rewriting the tree.

Implementations should form a composite tree structure where leaf nodes (e.g., datastore scans) have no subiterators, and composite nodes (e.g., unions, intersections) combine multiple subiterators.

Most tree transformations should use the Walk helper function rather than manually calling Subiterators and ReplaceSubiterators.

func ApplyOptimizations added in v1.47.1 

func ApplyOptimizations(it Iterator, fns []OptimizerFunc) (Iterator, bool, error)

ApplyOptimizations recursively applies a list of optimizer functions to an iterator tree, transforming it into an optimized form.

The function operates bottom-up, optimizing leafs and subiterators first, and replacing the subtrees up to the top, which it then returns.

Parameters:

  • it: The iterator tree to optimize
  • fns: A list of optimizer functions to apply

Returns:

  • The optimized iterator (which may be the same as the input if no optimizations applied)
  • A boolean indicating whether any changes were made
  • An error if any optimization failed

func BuildIteratorFromSchema 

func BuildIteratorFromSchema(fullSchema *schema.Schema, definitionName string, relationName string) (Iterator, error)

BuildIteratorFromSchema takes a schema and walks the schema tree for a given definition namespace and a relationship or permission therein. From this, it generates an iterator tree, rooted on that relationship.

func NewIntersectionIterator added in v1.49.2 

func NewIntersectionIterator(subiterators ...Iterator) Iterator

func NewUnionIterator added in v1.49.2 

func NewUnionIterator(subiterators ...Iterator) Iterator

func PushdownCaveatEvaluation added in v1.47.1 

func PushdownCaveatEvaluation(c *CaveatIterator) (Iterator, bool, error)

PushdownCaveatEvaluation pushes caveat evaluation down through certain composite iterators to allow earlier filtering and better performance.

This optimization transforms: 

Caveat(Union[A, B]) -> Union[Caveat(A), B] (if only A contains the caveat)
Caveat(Union[A, B]) -> Union[Caveat(A), Caveat(B)] (if both contain the caveat)

The pushdown does NOT occur through IntersectionArrow iterators, as they have special semantics that require caveat evaluation to happen after the intersection.

func Walk added in v1.46.1 

func Walk(root Iterator, callback func(Iterator) (Iterator, error)) (Iterator, error)

Walk traverses an iterator tree depth-first, calling the callback for each node. If the callback returns a different iterator than the input, that iterator replaces the current node. The callback is applied bottom-up (children are processed before parents). Panics if ReplaceSubiterators returns an error (should never happen in normal operation).

type IteratorArgs added in v1.49.2 

type IteratorArgs struct {
	Relation       *schema.BaseRelation
	DefinitionName string
	RelationName   string
	Caveat         *core.ContextualizedCaveat
	FixedPaths     []Path
}

IteratorArgs represents all the possible arguments to the Iterator constructors. It is used by the Outline to carry the context of an Iterator.

type IteratorType added in v1.49.2 

type IteratorType byte

IteratorType is an enum to represent each basic type of iterator by a well-known byte.

Remember to also update the allIteratorTypes list below when adding a new one. 

const (
	NullIteratorType              IteratorType = '0'
	DatastoreIteratorType         IteratorType = 'D'
	UnionIteratorType             IteratorType = '|'
	IntersectionIteratorType      IteratorType = '&'
	FixedIteratorType             IteratorType = 'F'
	ArrowIteratorType             IteratorType = '>'
	ExclusionIteratorType         IteratorType = 'X'
	CaveatIteratorType            IteratorType = 'C'
	AliasIteratorType             IteratorType = '@'
	RecursiveIteratorType         IteratorType = 'R'
	RecursiveSentinelIteratorType IteratorType = 'r'
	IntersectionArrowIteratorType IteratorType = 'A'
	SelfIteratorType              IteratorType = '='
)

type LocalExecutor 

type LocalExecutor struct{}

LocalExecutor is the simplest executor. It simply calls the iterator's implementation directly.

func (LocalExecutor) Check 

func (l LocalExecutor) Check(ctx *Context, it Iterator, resources []Object, subject ObjectAndRelation) (PathSeq, error)

Check tests if, for the underlying set of relationships (which may be a full expression or a basic lookup, depending on the iterator) any of the `resources` are connected to `subject`. Returns the sequence of matching paths, if they exist, at most `len(resources)`.

func (LocalExecutor) IterResources 

func (l LocalExecutor) IterResources(ctx *Context, it Iterator, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

IterResources returns a sequence of all the paths in this set that match the given subject.

func (LocalExecutor) IterSubjects 

func (l LocalExecutor) IterSubjects(ctx *Context, it Iterator, resource Object, filterSubjectType ObjectType) (PathSeq, error)

IterSubjects returns a sequence of all the paths in this set that match the given resource.

type Object 

type Object struct {
	ObjectID   string
	ObjectType string
}

Object represents a single object, without specifying the relation.

func GetObject 

func GetObject(oar ObjectAndRelation) Object

GetObject extracts the Object part from an ObjectAndRelation.

func NewObject 

func NewObject(objectType, objectID string) Object

NewObject creates a new Object with the given object type and ID.

func NewObjects 

func NewObjects(objectType string, objectIDs ...string) []Object

NewObjects creates a slice of Objects of the same type with the given object IDs.

func (Object) Equals 

func (o Object) Equals(other Object) bool

func (Object) Key added in v1.46.1 

func (o Object) Key() string

Key returns a unique string key for this Object

func (Object) WithEllipses 

func (o Object) WithEllipses() ObjectAndRelation

WithEllipses builds an ObjectAndRelation from an object with the default ellipses relation.

func (Object) WithRelation 

func (o Object) WithRelation(relation string) ObjectAndRelation

WithRelation builds a full ObjectAndRelation out of the given Object.

type ObjectAndRelation 

type ObjectAndRelation = tuple.ObjectAndRelation

func NewObjectAndRelation 

func NewObjectAndRelation(objectID, objectType, relation string) ObjectAndRelation

NewObjectAndRelation creates a new ObjectAndRelation with the given object ID, type, and relation.

type ObjectType added in v1.49.0 

type ObjectType struct {
	Type        string
	Subrelation string
}

func NewType added in v1.49.0 

func NewType(typename string, subrelation ...string) ObjectType

func NoObjectFilter added in v1.49.0 

func NoObjectFilter() ObjectType

NoObjectFilter returns an empty ObjectType that indicates no filtering should be applied. Use this instead of ObjectType{} for clarity when calling IterResources or IterSubjects.

func (ObjectType) String added in v1.49.0 

func (t ObjectType) String() string

type Observer added in v1.49.2 

type Observer interface {
	ObserveEnterIterator(op ObserverOperation, key CanonicalKey)
	ObservePath(op ObserverOperation, key CanonicalKey, path Path)
	ObserveReturnIterator(op ObserverOperation, key CanonicalKey)
}

type ObserverOperation added in v1.49.2 

type ObserverOperation int
const (
	CheckOperation ObserverOperation = iota
	IterSubjectsOperation
	IterResourcesOperation
)

type OptimizerFunc added in v1.47.1 

type OptimizerFunc func(it Iterator) (Iterator, bool, error)

OptimizerFunc is a type-erased wrapper around TypedOptimizerFunc[T] that can be stored in a homogeneous list while maintaining type safety at runtime.

func WrapOptimizer added in v1.47.1 

func WrapOptimizer[T Iterator](fn TypedOptimizerFunc[T]) OptimizerFunc

WrapOptimizer wraps a typed TypedOptimizerFunc[T] into a type-erased OptimizerFunc. This allows optimizer functions for different concrete iterator types to be stored together in a heterogeneous list.

type Outline added in v1.49.2 

type Outline struct {
	Type        IteratorType
	Args        *IteratorArgs
	SubOutlines []Outline
	ID          OutlineNodeID // Populated only inside a CanonicalOutline
}

Outline is a single type representing the tree of yet-to-be-compiled Iterators.

func Decompile added in v1.49.2 

func Decompile(it Iterator) (Outline, error)

Decompile converts an Iterator back to its Outline representation

func MutateOutline added in v1.49.2 

func MutateOutline(outline Outline, fns []OutlineMutation) Outline

MutateOutline performs a bottom-up traversal of the outline tree, applying all the given transformation functions to each node after processing its children.

func (Outline) Equals added in v1.49.2 

func (outline Outline) Equals(other Outline) bool

Equals checks if two Outlines are structurally equal

func (Outline) Serialize added in v1.49.2 

func (outline Outline) Serialize() CanonicalKey

Serialize generates a compact, deterministic string representation of an Outline subtree based on its Type, Args, and SubOutlines. The ID field is not included in serialization. Format: <Type>(<Args>)[<Sub1>,<Sub2>,...] Returns a CanonicalKey wrapping the serialized string.

CaveatIterator nodes are identified solely by their caveat name, independent of their position in the tree. Their subiterators are not included in the key.

type OutlineMutation added in v1.49.2 

type OutlineMutation func(Outline) Outline

type OutlineNodeID added in v1.49.2 

type OutlineNodeID uint64

OutlineNodeID is a numeric identifier assigned to each node in a CanonicalOutline. It is populated by CanonicalizeOutline; plain (non-canonical, non-filter) Outlines have a zero-valued ID and cannot be compiled.

type Path added in v1.46.0 

type Path struct {
	Resource   Object
	Relation   string
	Subject    ObjectAndRelation
	Caveat     *core.CaveatExpression
	Expiration *time.Time
	Integrity  []*core.RelationshipIntegrity

	Metadata map[string]any
}

Path is an abstract notion of an individual relation. While tuple.Relation is what is stored under the hood, this represents a virtual relation, one that may either be backed by a real tuple, or one that is constructed from a query path, equivalent to a subtree of a query.Plan. `permission foo = bar | baz`, for example, is a Path named foo that can be constructed by either the bar path or the baz path (which themselves may be other paths, down to individual, stored, relations.)

func CollectAll 

func CollectAll(seq PathSeq) ([]Path, error)

CollectAll is a helper function to build read a complete PathSeq and turn it into a fully realized slice of Paths.

func FromRelationship added in v1.46.0 

func FromRelationship(rel tuple.Relationship) Path

FromRelationship creates a new Path from a tuple.Relationship.

func MustPathFromString added in v1.46.0 

func MustPathFromString(relationshipStr string) Path

MustPathFromString is a helper function for tests that creates a Path from a relationship string. It uses tuple.MustParse to parse the string and then converts it to a Path using FromRelationship. Example: MustPathFromString("document:doc1#viewer@user:alice")

func (Path) EndpointsKey added in v1.47.1 

func (p Path) EndpointsKey() string

EndpointsKey returns a unique string key for this Path based on its resource and subject only, excluding the relation. This matches the semantics of EqualsEndpoints.

func (Path) Equals added in v1.46.1 

func (p Path) Equals(other Path) bool

Equals checks if two paths are fully equal (all fields match)

func (Path) EqualsEndpoints added in v1.46.1 

func (p Path) EqualsEndpoints(other Path) bool

EqualsEndpoints checks if two paths have the same Resource and Subject endpoints (types and IDs only)

func (Path) IsExpired added in v1.46.0 

func (p Path) IsExpired() bool

func (Path) Key added in v1.46.1 

func (p Path) Key() string

Key returns a unique string key for this Path based on its resource and subject

func (Path) MergeAnd added in v1.46.0 

func (p Path) MergeAnd(other Path) (Path, error)

MergeAnd combines the paths, ANDing the caveats and expiration and metadata together. Returns a new Path with the merged values.

func (Path) MergeAndNot added in v1.46.0 

func (p Path) MergeAndNot(other Path) (Path, error)

MergeAndNot combines the paths, subtracting the caveats and expiration and metadata together. Returns a new Path with the merged values.

func (Path) MergeOr added in v1.46.0 

func (p Path) MergeOr(other Path) (Path, error)

MergeOr combines the paths, ORing the caveats and expiration and metadata together. Returns a new Path with the merged values.

func (Path) ResourceOAR added in v1.46.0 

func (p Path) ResourceOAR() ObjectAndRelation

ResourceOAR returns the resource as an ObjectAndRelation with the current relation type.

func (Path) ToRelationship added in v1.46.0 

func (p Path) ToRelationship() (tuple.Relationship, error)

ToRelationship converts the Path to a tuple.Relationship.

type PathSeq added in v1.46.0 

type PathSeq iter.Seq2[Path, error]

PathSeq is the intermediate iter closure that any of the planning calls return.

func DeduplicatePathSeq added in v1.47.1 

func DeduplicatePathSeq(seq PathSeq) PathSeq

DeduplicatePathSeq returns a new PathSeq that deduplicates paths based on their endpoints (resource and subject, excluding relation). Paths with the same endpoints are merged using OR semantics (caveats are OR'd, no caveat wins over caveat). This collects all paths first, deduplicates with merging, then yields results.

func EmptyPathSeq added in v1.46.0 

func EmptyPathSeq() PathSeq

EmptyPathSeq returns an empty iterator, that is error-free but empty.

func FilterResourcesByType added in v1.49.0 

func FilterResourcesByType(seq PathSeq, filter ObjectType) PathSeq

FilterResourcesByType filters a PathSeq to only include paths where the resource matches the specified ObjectType. If filter.Type is empty, no filtering is applied.

func FilterSubjectsByType added in v1.49.0 

func FilterSubjectsByType(seq PathSeq, filter ObjectType) PathSeq

FilterSubjectsByType filters a PathSeq to only include paths where the subject matches the specified ObjectType. If filter.Type is empty, no filtering is applied.

func FilterWildcardSubjects added in v1.49.0 

func FilterWildcardSubjects(seq PathSeq) PathSeq

FilterWildcardSubjects filters out any paths with wildcard subjects.

func PathSeqFromSlice added in v1.49.2 

func PathSeqFromSlice(paths []Path) PathSeq

PathSeqFromSlice creates a PathSeq that yields all paths from the given slice.

func RewriteSubject added in v1.49.0 

func RewriteSubject(seq PathSeq, subject ObjectAndRelation) PathSeq

type Plan 

type Plan interface {
	// CheckImpl tests if, for the underlying set of relationships (which may be a full expression or a basic lookup, depending on the iterator)
	// any of the `resourceIDs` are connected to `subjectID`.
	// Returns the sequence of matching paths, if they exist, at most `len(resourceIDs)`.
	CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

	// IterSubjectsImpl returns a sequence of all the paths in this set that match the given resourceID.
	// The filterSubjectType parameter filters the results to only include subjects matching the
	// specified ObjectType. If filterSubjectType.Type is empty, no filtering is applied.
	IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

	// IterResourcesImpl returns a sequence of all the paths in this set that match the given subjectID.
	// The filterResourceType parameter filters the results to only include resources matching the
	// specified ObjectType. If filterResourceType.Type is empty, no filtering is applied.
	IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

	// Explain generates a human-readable tree that describes each iterator and its state.
	Explain() Explain
}

Plan is the external-facing notion of a query plan. These follow the general API for querying anything in the database as well as describing the plan.

type RecursiveIterator added in v1.46.1 

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

RecursiveIterator is the root controller that manages iterative deepening for recursive schemas. It wraps an iterator tree that contains RecursiveSentinel sentinels, and executes the tree repeatedly with increasing depth until a fixed point is reached or max depth is exceeded.

func NewRecursiveIterator added in v1.46.1 

func NewRecursiveIterator(templateTree Iterator, definitionName, relationName string) *RecursiveIterator

NewRecursiveIterator creates a new recursive iterator controller

func (*RecursiveIterator) CanonicalKey added in v1.49.2 

func (r *RecursiveIterator) CanonicalKey() CanonicalKey

func (*RecursiveIterator) CheckImpl added in v1.46.1 

func (r *RecursiveIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

CheckImpl implements traversal for Check operations with strategy selection

func (*RecursiveIterator) Clone added in v1.46.1 

func (r *RecursiveIterator) Clone() Iterator

Clone creates a deep copy of the RecursiveIterator

func (*RecursiveIterator) Explain added in v1.46.1 

func (r *RecursiveIterator) Explain() Explain

Explain returns a description of this recursive iterator

func (*RecursiveIterator) IterResourcesImpl added in v1.46.1 

func (r *RecursiveIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

IterResourcesImpl implements BFS traversal for IterResources operations

func (*RecursiveIterator) IterSubjectsImpl added in v1.46.1 

func (r *RecursiveIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

IterSubjectsImpl implements BFS traversal for IterSubjects operations

func (*RecursiveIterator) ReplaceSubiterators added in v1.46.1 

func (r *RecursiveIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*RecursiveIterator) ResourceType added in v1.49.0 

func (r *RecursiveIterator) ResourceType() ([]ObjectType, error)

func (*RecursiveIterator) Subiterators added in v1.46.1 

func (r *RecursiveIterator) Subiterators() []Iterator

func (*RecursiveIterator) SubjectTypes added in v1.49.0 

func (r *RecursiveIterator) SubjectTypes() ([]ObjectType, error)

type RecursiveSentinelIterator added in v1.49.2 

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

RecursiveSentinelIterator is a sentinel iterator that marks recursion points during iterator tree construction. It acts as a placeholder that will be replaced during execution by RecursiveIterator.

func NewRecursiveSentinelIterator added in v1.49.2 

func NewRecursiveSentinelIterator(definitionName, relationName string, withSubRelations bool) *RecursiveSentinelIterator

NewRecursiveSentinelIterator creates a new sentinel marking a recursion point

func (*RecursiveSentinelIterator) CanonicalKey added in v1.49.2 

func (r *RecursiveSentinelIterator) CanonicalKey() CanonicalKey

func (*RecursiveSentinelIterator) CheckImpl added in v1.49.2 

func (r *RecursiveSentinelIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

CheckImpl returns an empty PathSeq. If collection mode is enabled, it collects the queried resources to the frontier collection instead of returning paths.

func (*RecursiveSentinelIterator) Clone added in v1.49.2 

func (r *RecursiveSentinelIterator) Clone() Iterator

Clone returns a shallow copy of the sentinel

func (*RecursiveSentinelIterator) DefinitionName added in v1.49.2 

func (r *RecursiveSentinelIterator) DefinitionName() string

DefinitionName returns the definition name this sentinel represents

func (*RecursiveSentinelIterator) Explain added in v1.49.2 

func (r *RecursiveSentinelIterator) Explain() Explain

Explain returns a description of this sentinel for debugging

func (*RecursiveSentinelIterator) IterResourcesImpl added in v1.49.2 

func (r *RecursiveSentinelIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

IterResourcesImpl returns an empty PathSeq since sentinels don't execute during construction

func (*RecursiveSentinelIterator) IterSubjectsImpl added in v1.49.2 

func (r *RecursiveSentinelIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

IterSubjectsImpl returns an empty PathSeq. If collection mode is enabled, it collects the queried resource to the frontier collection instead of returning paths.

func (*RecursiveSentinelIterator) RelationName added in v1.49.2 

func (r *RecursiveSentinelIterator) RelationName() string

RelationName returns the relation name this sentinel represents

func (*RecursiveSentinelIterator) ReplaceSubiterators added in v1.49.2 

func (r *RecursiveSentinelIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*RecursiveSentinelIterator) ResourceType added in v1.49.2 

func (r *RecursiveSentinelIterator) ResourceType() ([]ObjectType, error)

func (*RecursiveSentinelIterator) Subiterators added in v1.49.2 

func (r *RecursiveSentinelIterator) Subiterators() []Iterator

func (*RecursiveSentinelIterator) SubjectTypes added in v1.49.2 

func (r *RecursiveSentinelIterator) SubjectTypes() ([]ObjectType, error)

func (*RecursiveSentinelIterator) WithSubRelations added in v1.49.2 

func (r *RecursiveSentinelIterator) WithSubRelations() bool

WithSubRelations returns whether subrelations should be included

type RelationNotFoundError added in v1.47.1 

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

RelationNotFoundError is returned when a relation or permission is not found in a definition

func (RelationNotFoundError) Error added in v1.47.1 

func (e RelationNotFoundError) Error() string

type SelfIterator added in v1.49.2 

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

SelfIterator is an iterator that produces a synthetic relation for every Resource in the subiterator that connects it to streamed from the sub-iterator to a specified alias relation.

func NewSelfIterator added in v1.49.2 

func NewSelfIterator(relation string, typeName string) *SelfIterator

func (*SelfIterator) CanonicalKey added in v1.49.2 

func (s *SelfIterator) CanonicalKey() CanonicalKey

func (*SelfIterator) CheckImpl added in v1.49.2 

func (s *SelfIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

func (*SelfIterator) Clone added in v1.49.2 

func (s *SelfIterator) Clone() Iterator

func (*SelfIterator) Explain added in v1.49.2 

func (s *SelfIterator) Explain() Explain

func (*SelfIterator) IterResourcesImpl added in v1.49.2 

func (s *SelfIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

func (*SelfIterator) IterSubjectsImpl added in v1.49.2 

func (s *SelfIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

func (*SelfIterator) ReplaceSubiterators added in v1.49.2 

func (s *SelfIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*SelfIterator) ResourceType added in v1.49.2 

func (s *SelfIterator) ResourceType() ([]ObjectType, error)

func (*SelfIterator) Subiterators added in v1.49.2 

func (s *SelfIterator) Subiterators() []Iterator

func (*SelfIterator) SubjectTypes added in v1.49.2 

func (s *SelfIterator) SubjectTypes() ([]ObjectType, error)

type StaticStatistics added in v1.48.0 

type StaticStatistics struct {
	// NumberOfTuplesInRelation is the assumed number of tuples in any relation (a complete average).
	NumberOfTuplesInRelation int

	// Fanout is the assumed average number of subjects per resource or
	// resources per subject.
	Fanout int

	// CheckSelectivity is the default probability (0.0-1.0) that a Check
	// operation will return true.
	CheckSelectivity float64
}

StaticStatistics provides static cost estimates for iterators based on configurable parameters. This is useful for basic query planning and when dynamic statistics are not available.

Costs are static for StaticStatistics -- we take the base cost of a check to be 1 tuple check. For iterating subjects and resources, we take it to iterate all tuples for a given relation.

func DefaultStaticStatistics added in v1.48.0 

func DefaultStaticStatistics() StaticStatistics

DefaultStaticStatistics returns a StaticStatistics instance with default values

func (StaticStatistics) Cost added in v1.48.0 

func (s StaticStatistics) Cost(iterator Iterator) (Estimate, error)

Cost returns a cost estimate for the given iterator using static assumptions. It recursively estimates costs for composite iterators by combining the costs of their subiterators according to their operational semantics.

type StatisticsOptimizer added in v1.48.0 

type StatisticsOptimizer struct {
	Source StatisticsSource
}

StatisticsOptimizer uses cost estimates to optimize iterator trees.

func (StatisticsOptimizer) Optimize added in v1.48.0 

func (s StatisticsOptimizer) Optimize(it Iterator) (Iterator, bool, error)

Optimize applies statistics-based optimizations to an iterator tree. It uses cost estimates to make decisions about reordering and restructuring.

type StatisticsSource added in v1.48.0 

type StatisticsSource interface {
	// Cost returns a cost estimate for the given iterator.
	Cost(it Iterator) (Estimate, error)
}

StatisticsSource provides cost estimates for iterators. Implementations can provide static estimates or dynamic estimates based on actual datastore statistics.

type TraceLogger added in v1.46.1 

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

TraceLogger is used for debugging iterator execution

func NewTraceLogger added in v1.46.1 

func NewTraceLogger() *TraceLogger

NewTraceLogger creates a new trace logger

func NewTraceLoggerWithWriter added in v1.49.2 

func NewTraceLoggerWithWriter(w io.Writer) *TraceLogger

NewTraceLoggerWithWriter creates a new trace logger with an optional writer for real-time trace output

func (*TraceLogger) DumpTrace added in v1.46.1 

func (t *TraceLogger) DumpTrace() string

DumpTrace returns all traces as a string

func (*TraceLogger) EnterIterator added in v1.46.1 

func (t *TraceLogger) EnterIterator(it Iterator, traceString string)

EnterIterator logs entering an iterator and pushes it onto the stack

func (*TraceLogger) ExitIterator added in v1.46.1 

func (t *TraceLogger) ExitIterator(it Iterator, paths []Path)

ExitIterator logs exiting an iterator and pops it from the stack

func (*TraceLogger) LogStep added in v1.46.1 

func (t *TraceLogger) LogStep(it Iterator, step string, data ...any)

LogStep logs an intermediate step within an iterator, using the iterator pointer to find the correct indentation level

type TypedOptimizerFunc added in v1.47.1 

type TypedOptimizerFunc[T Iterator] func(it T) (Iterator, bool, error)

TypedOptimizerFunc is a function that transforms an iterator of a specific type T into a potentially optimized iterator. It returns the optimized iterator, a boolean indicating whether any optimization was performed, and an error if the optimization failed.

The type parameter T constrains the function to operate only on specific iterator types, providing compile-time type safety when creating typed optimizers.

type UnionIterator added in v1.49.2 

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

UnionIterator the set of paths that are in any of underlying subiterators. This is equivalent to `permission foo = bar | baz`

func (*UnionIterator) CanonicalKey added in v1.49.2 

func (u *UnionIterator) CanonicalKey() CanonicalKey

func (*UnionIterator) CheckImpl added in v1.49.2 

func (u *UnionIterator) CheckImpl(ctx *Context, resources []Object, subject ObjectAndRelation) (PathSeq, error)

func (*UnionIterator) Clone added in v1.49.2 

func (u *UnionIterator) Clone() Iterator

func (*UnionIterator) Explain added in v1.49.2 

func (u *UnionIterator) Explain() Explain

func (*UnionIterator) IterResourcesImpl added in v1.49.2 

func (u *UnionIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation, filterResourceType ObjectType) (PathSeq, error)

func (*UnionIterator) IterSubjectsImpl added in v1.49.2 

func (u *UnionIterator) IterSubjectsImpl(ctx *Context, resource Object, filterSubjectType ObjectType) (PathSeq, error)

func (*UnionIterator) ReplaceSubiterators added in v1.49.2 

func (u *UnionIterator) ReplaceSubiterators(newSubs []Iterator) (Iterator, error)

func (*UnionIterator) ResourceType added in v1.49.2 

func (u *UnionIterator) ResourceType() ([]ObjectType, error)

func (*UnionIterator) Subiterators added in v1.49.2 

func (u *UnionIterator) Subiterators() []Iterator

func (*UnionIterator) SubjectTypes added in v1.49.2 

func (u *UnionIterator) SubjectTypes() ([]ObjectType, error)

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.