query

package
v1.46.0 Latest Latest
Warning

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

 Go to latest Published: Oct 6, 2025 License: Apache-2.0 Imports: 15 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

This section is empty.

Functions

This section is empty.

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)

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)

type Context 

type Context struct {
	context.Context
	Executor  Executor
	Datastore datastore.ReadOnlyDatastore
	Revision  datastore.Revision
}

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.

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)

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 {
	Info       string
	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)

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 NewConflictingPermissionsFixedIterator 

func NewConflictingPermissionsFixedIterator() *FixedIterator

NewConflictingPermissionsFixedIterator creates a FixedIterator with potential permission conflicts for testing

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 NewGroupMembershipFixedIterator 

func NewGroupMembershipFixedIterator() *FixedIterator

NewGroupMembershipFixedIterator creates a FixedIterator with group membership and nested groups

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)

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

type Iterator 

type Iterator interface {
	Plan

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

Iterator is an interface for manipulating iterators to create more query plans.

A Plan is abstract and more limited, and easier to pass around.

An Iterator is what Iterators (even future datastore-specific ones) implement so that optimizations and reorderings and rebalancing can take place.

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.

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) 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 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) IsExpired added in v1.46.0 

func (p *Path) IsExpired() bool

func (*Path) MergeAnd added in v1.46.0 

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

MergeAnd combines the paths, ANDing the caveats and expiration and metadata together.

func (*Path) MergeAndNot added in v1.46.0 

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

MergeAndNot combines the paths, subtracting the caveats and expiration and metadata together.

func (*Path) MergeOr added in v1.46.0 

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

MergeOr combines the paths, ORing the caveats and expiration and metadata together.

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

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

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.