query

package
v1.48.0 Latest Latest
Warning

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

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

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{
	RemoveNullIterators,
	CollapseSingletonUnionAndIntersection,
	WrapOptimizer(PushdownCaveatEvaluation),
}

StaticOptimizations is a list of optimization functions that can be safely applied to any iterator tree without needing runtime information or context.

Functions

func ObjectAndRelationKey added in v1.46.1 

func ObjectAndRelationKey(oar ObjectAndRelation) string

ObjectAndRelationKey returns a unique string key for an ObjectAndRelation

func SimplifyCaveatExpression added in v1.46.1 

func SimplifyCaveatExpression(
	ctx context.Context,
	runner *caveats.CaveatRunner,
	expr *core.CaveatExpression,
	context map[string]any,
	reader datastore.CaveatReader,
) (*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 Alias 

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

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

func NewAlias 

func NewAlias(relation string, subIt Iterator) *Alias

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

func (*Alias) CheckImpl 

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

func (*Alias) Clone 

func (a *Alias) Clone() Iterator

func (*Alias) Explain 

func (a *Alias) Explain() Explain

func (*Alias) IterResourcesImpl 

func (a *Alias) IterResourcesImpl(ctx *Context, subject ObjectAndRelation) (PathSeq, error)

func (*Alias) IterSubjectsImpl 

func (a *Alias) IterSubjectsImpl(ctx *Context, resource Object) (PathSeq, error)

func (*Alias) ReplaceSubiterators added in v1.46.1 

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

func (*Alias) Subiterators added in v1.46.1 

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

type Arrow 

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

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

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

func NewArrow 

func NewArrow(left, right Iterator) *Arrow

func (*Arrow) CheckImpl 

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

func (*Arrow) Clone 

func (a *Arrow) Clone() Iterator

func (*Arrow) Explain 

func (a *Arrow) Explain() Explain

func (*Arrow) IterResourcesImpl 

func (a *Arrow) IterResourcesImpl(ctx *Context, subject ObjectAndRelation) (PathSeq, error)

func (*Arrow) IterSubjectsImpl 

func (a *Arrow) IterSubjectsImpl(ctx *Context, resource Object) (PathSeq, error)

func (*Arrow) ReplaceSubiterators added in v1.46.1 

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

func (*Arrow) Subiterators added in v1.46.1 

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

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) 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) (PathSeq, error)

func (*CaveatIterator) IterSubjectsImpl added in v1.46.1 

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

func (*CaveatIterator) ReplaceSubiterators added in v1.46.1 

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

func (*CaveatIterator) Subiterators added in v1.46.1 

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

type Context 

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

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 (*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) IterResources 

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

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

func (*Context) IterSubjects 

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

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

func (*Context) TraceEnter added in v1.46.1 

func (ctx *Context) TraceEnter(it Iterator, resources []Object, subject ObjectAndRelation)

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 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 Exclusion 

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

Exclusion 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 NewExclusion 

func NewExclusion(mainSet, excluded Iterator) *Exclusion

func (*Exclusion) CheckImpl 

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

func (*Exclusion) Clone 

func (e *Exclusion) Clone() Iterator

func (*Exclusion) Explain 

func (e *Exclusion) Explain() Explain

func (*Exclusion) IterResourcesImpl 

func (e *Exclusion) IterResourcesImpl(ctx *Context, subject ObjectAndRelation) (PathSeq, error)

func (*Exclusion) IterSubjectsImpl 

func (e *Exclusion) IterSubjectsImpl(ctx *Context, resource Object) (PathSeq, error)

func (*Exclusion) ReplaceSubiterators added in v1.46.1 

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

func (*Exclusion) Subiterators added in v1.46.1 

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

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.
	IterSubjects(ctx *Context, it Iterator, resource Object) (PathSeq, error)

	// IterResources returns a sequence of all the relations in this set that match the given subject.
	IterResources(ctx *Context, it Iterator, subject ObjectAndRelation) (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) *FaultyIterator

NewFaultyIterator creates a new FaultyIterator for testing error conditions

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) (PathSeq, error)

func (*FaultyIterator) IterSubjectsImpl 

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

func (*FaultyIterator) ReplaceSubiterators added in v1.46.1 

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

func (*FaultyIterator) Subiterators added in v1.46.1 

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

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) 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) (PathSeq, error)

func (*FixedIterator) IterSubjectsImpl 

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

func (*FixedIterator) ReplaceSubiterators added in v1.46.1 

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

func (*FixedIterator) Subiterators added in v1.46.1 

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

type Intersection 

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

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

func NewIntersection 

func NewIntersection(subiterators ...Iterator) *Intersection

func (*Intersection) CheckImpl 

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

func (*Intersection) Clone 

func (i *Intersection) Clone() Iterator

func (*Intersection) Explain 

func (i *Intersection) Explain() Explain

func (*Intersection) IterResourcesImpl 

func (i *Intersection) IterResourcesImpl(ctx *Context, subject ObjectAndRelation) (PathSeq, error)

func (*Intersection) IterSubjectsImpl 

func (i *Intersection) IterSubjectsImpl(ctx *Context, resource Object) (PathSeq, error)

func (*Intersection) ReplaceSubiterators added in v1.46.1 

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

func (*Intersection) Subiterators added in v1.46.1 

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

type IntersectionArrow added in v1.46.1 

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

IntersectionArrow 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 NewIntersectionArrow added in v1.46.1 

func NewIntersectionArrow(left, right Iterator) *IntersectionArrow

func (*IntersectionArrow) CheckImpl added in v1.46.1 

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

func (*IntersectionArrow) Clone added in v1.46.1 

func (ia *IntersectionArrow) Clone() Iterator

func (*IntersectionArrow) Explain added in v1.46.1 

func (ia *IntersectionArrow) Explain() Explain

func (*IntersectionArrow) IterResourcesImpl added in v1.46.1 

func (ia *IntersectionArrow) IterResourcesImpl(ctx *Context, subject ObjectAndRelation) (PathSeq, error)

func (*IntersectionArrow) IterSubjectsImpl added in v1.46.1 

func (ia *IntersectionArrow) IterSubjectsImpl(ctx *Context, resource Object) (PathSeq, error)

func (*IntersectionArrow) ReplaceSubiterators added in v1.46.1 

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

func (*IntersectionArrow) Subiterators added in v1.46.1 

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

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)
}

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 CollapseSingletonUnionAndIntersection added in v1.47.1 

func CollapseSingletonUnionAndIntersection(it Iterator) (Iterator, bool, error)

CollapseSingletonUnionAndIntersection removes unnecessary union and intersection wrappers that contain only a single subiterator.

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 RemoveNullIterators added in v1.47.1 

func RemoveNullIterators(it Iterator) (Iterator, bool, error)

RemoveNullIterators removes null iterators from union and intersection operations. Unions, removes the empty set (A | 0 = A), Intersection, returns a null itself (A & 0 = 0)

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 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) (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) (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 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 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.

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.
	IterSubjectsImpl(ctx *Context, resource Object) (PathSeq, error)

	// IterResourcesImpl returns a sequence of all the paths in this set that match the given subjectID.
	IterResourcesImpl(ctx *Context, subject ObjectAndRelation) (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) CheckImpl added in v1.46.1 

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

CheckImpl implements iterative deepening for Check operations

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) (PathSeq, error)

IterResourcesImpl implements iterative deepening for IterResources operations

func (*RecursiveIterator) IterSubjectsImpl added in v1.46.1 

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

IterSubjectsImpl implements iterative deepening for IterSubjects operations

func (*RecursiveIterator) ReplaceSubiterators added in v1.46.1 

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

func (*RecursiveIterator) Subiterators added in v1.46.1 

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

type RecursiveSentinel added in v1.46.1 

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

RecursiveSentinel 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 NewRecursiveSentinel added in v1.46.1 

func NewRecursiveSentinel(definitionName, relationName string, withSubRelations bool) *RecursiveSentinel

NewRecursiveSentinel creates a new sentinel marking a recursion point

func (*RecursiveSentinel) CheckImpl added in v1.46.1 

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

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

func (*RecursiveSentinel) Clone added in v1.46.1 

func (r *RecursiveSentinel) Clone() Iterator

Clone returns a shallow copy of the sentinel

func (*RecursiveSentinel) DefinitionName added in v1.46.1 

func (r *RecursiveSentinel) DefinitionName() string

DefinitionName returns the definition name this sentinel represents

func (*RecursiveSentinel) Explain added in v1.46.1 

func (r *RecursiveSentinel) Explain() Explain

Explain returns a description of this sentinel for debugging

func (*RecursiveSentinel) ID added in v1.46.1 

func (r *RecursiveSentinel) ID() string

ID returns the unique identifier for this sentinel

func (*RecursiveSentinel) IterResourcesImpl added in v1.46.1 

func (r *RecursiveSentinel) IterResourcesImpl(ctx *Context, subject ObjectAndRelation) (PathSeq, error)

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

func (*RecursiveSentinel) IterSubjectsImpl added in v1.46.1 

func (r *RecursiveSentinel) IterSubjectsImpl(ctx *Context, resource Object) (PathSeq, error)

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

func (*RecursiveSentinel) RelationName added in v1.46.1 

func (r *RecursiveSentinel) RelationName() string

RelationName returns the relation name this sentinel represents

func (*RecursiveSentinel) ReplaceSubiterators added in v1.46.1 

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

func (*RecursiveSentinel) Subiterators added in v1.46.1 

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

func (*RecursiveSentinel) WithSubRelations added in v1.46.1 

func (r *RecursiveSentinel) WithSubRelations() bool

WithSubRelations returns whether subrelations should be included

type RelationIterator 

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

RelationIterator 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 RelationIterator, being the leaf, generates this set by calling the datastore.

func NewRelationIterator 

func NewRelationIterator(base *schema.BaseRelation) *RelationIterator

func (*RelationIterator) CheckImpl 

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

func (*RelationIterator) Clone 

func (r *RelationIterator) Clone() Iterator

func (*RelationIterator) Explain 

func (r *RelationIterator) Explain() Explain

func (*RelationIterator) IterResourcesImpl 

func (r *RelationIterator) IterResourcesImpl(ctx *Context, subject ObjectAndRelation) (PathSeq, error)

func (*RelationIterator) IterSubjectsImpl 

func (r *RelationIterator) IterSubjectsImpl(ctx *Context, resource Object) (PathSeq, error)

func (*RelationIterator) ReplaceSubiterators added in v1.46.1 

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

func (*RelationIterator) Subiterators added in v1.46.1 

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

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 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 (*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, resources []Object, subject ObjectAndRelation)

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 Union 

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

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

func NewUnion 

func NewUnion(subiterators ...Iterator) *Union

func (*Union) CheckImpl 

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

func (*Union) Clone 

func (u *Union) Clone() Iterator

func (*Union) Explain 

func (u *Union) Explain() Explain

func (*Union) IterResourcesImpl 

func (u *Union) IterResourcesImpl(ctx *Context, subject ObjectAndRelation) (PathSeq, error)

func (*Union) IterSubjectsImpl 

func (u *Union) IterSubjectsImpl(ctx *Context, resource Object) (PathSeq, error)

func (*Union) ReplaceSubiterators added in v1.46.1 

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

func (*Union) Subiterators added in v1.46.1 

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

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.