graph

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: 51 Imported by: 0

Documentation

Overview

Package graph contains the code to traverse a relationship graph to solve requests like Checks, Expansions and Lookups.

Index

Constants

View Source 
const Ellipsis = "..."

Ellipsis relation is used to signify a semantic-free relationship.

Variables

View Source 
var ErrLimitReached = errors.New("limit has been reached")

Functions

func AlwaysFailExpand 

func AlwaysFailExpand(_ context.Context, resultChan chan<- ExpandResult)

AlwaysFailExpand is a ReduceableExpandFunc which will always fail when reduced.

func NewAlwaysFailErr 

func NewAlwaysFailErr() error

NewAlwaysFailErr constructs a new always fail error.

func NewCheckFailureErr 

func NewCheckFailureErr(baseErr error) error

NewCheckFailureErr constructs a new check failed error.

func NewExpansionFailureErr 

func NewExpansionFailureErr(baseErr error) error

NewExpansionFailureErr constructs a new expansion failed error.

func NewInvalidCursorErr added in v1.23.0 

func NewInvalidCursorErr(dispatchCursorVersion uint32, cursor *dispatch.Cursor) error

NewInvalidCursorErr constructs a new unimplemented error.

func NewRelationMissingTypeInfoErr added in v0.0.2 

func NewRelationMissingTypeInfoErr(nsName string, relationName string) error

NewRelationMissingTypeInfoErr constructs a new relation not missing type information error.

func NewRelationNotFoundErr 

func NewRelationNotFoundErr(nsName string, relationName string) error

NewRelationNotFoundErr constructs a new relation not found error.

func NewSyncONRSet added in v1.35.0 

func NewSyncONRSet() *syncONRSet

func NewTraceID added in v1.40.0 

func NewTraceID() string

NewTraceID generates a new trace ID. The trace IDs will only be unique with a single dispatch request tree and should not be used for any other purpose. This function currently uses the UUID library to generate a new trace ID, which means it should not be invoked from performance-critical code paths.

func NewUnimplementedErr added in v1.14.0 

func NewUnimplementedErr(baseErr error) error

NewUnimplementedErr constructs a new unimplemented error.

func NewWildcardNotAllowedErr added in v1.34.0 

func NewWildcardNotAllowedErr(message string, fieldName string) error

NewWildcardNotAllowedErr constructs an error indicating that a wildcard was not allowed.

Types

type AlwaysFailError added in v1.39.0 

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

AlwaysFailError is returned when an internal error leads to an operation guaranteed to fail.

type CheckFailureError added in v1.39.0 

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

CheckFailureError occurs when check failed in some manner. Note this should not apply to namespaces and relations not being found.

func (CheckFailureError) Unwrap added in v1.39.0 

func (e CheckFailureError) Unwrap() error

type CheckResult 

type CheckResult struct {
	Resp *v1.DispatchCheckResponse
	Err  error
}

CheckResult is the data that is returned by a single check or sub-check.

func (CheckResult) ResultError added in v1.35.0 

func (cr CheckResult) ResultError() error

type CheckResultsMap added in v1.13.0 

type CheckResultsMap map[string]*v1.ResourceCheckResult

CheckResultsMap defines a type that is a map from resource ID to ResourceCheckResult. This must match that defined in the DispatchCheckResponse for the `results_by_resource_id` field.

type ConcurrentChecker added in v0.0.2 

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

ConcurrentChecker exposes a method to perform Check requests, and delegates subproblems to the provided dispatch.Check instance.

func NewConcurrentChecker added in v0.0.2 

func NewConcurrentChecker(d dispatch.Check, concurrencyLimit uint16, dispatchChunkSize uint16) *ConcurrentChecker

NewConcurrentChecker creates an instance of ConcurrentChecker.

func (*ConcurrentChecker) Check added in v0.0.2 

func (cc *ConcurrentChecker) Check(ctx context.Context, req ValidatedCheckRequest, relation *core.Relation) (*v1.DispatchCheckResponse, error)

Check performs a check request with the provided request and context

type ConcurrentExpander added in v0.0.2 

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

ConcurrentExpander exposes a method to perform Expand requests, and delegates subproblems to the provided dispatch.Expand instance.

func NewConcurrentExpander added in v0.0.2 

func NewConcurrentExpander(d dispatch.Expand) *ConcurrentExpander

NewConcurrentExpander creates an instance of ConcurrentExpander

func (*ConcurrentExpander) Expand added in v0.0.2 

func (ce *ConcurrentExpander) Expand(ctx context.Context, req ValidatedExpandRequest, relation *core.Relation) (*v1.DispatchExpandResponse, error)

Expand performs an expand request with the provided request and context.

type ConcurrentLookupSubjects added in v1.12.0 

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

func NewConcurrentLookupSubjects added in v1.12.0 

func NewConcurrentLookupSubjects(d dispatch.LookupSubjects, concurrencyLimit uint16, dispatchChunkSize uint16) *ConcurrentLookupSubjects

NewConcurrentLookupSubjects creates an instance of ConcurrentLookupSubjects.

func (*ConcurrentLookupSubjects) LookupSubjects added in v1.12.0 

func (cl *ConcurrentLookupSubjects) LookupSubjects(
	req ValidatedLookupSubjectsRequest,
	stream dispatch.LookupSubjectsStream,
) error

type CursoredLookupResources2 added in v1.35.0 

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

func NewCursoredLookupResources2 added in v1.35.0 

func NewCursoredLookupResources2(dl dispatch.LookupResources2, dc dispatch.Check, caveatTypeSet *caveattypes.TypeSet, concurrencyLimit uint16, dispatchChunkSize uint16) *CursoredLookupResources2

func (*CursoredLookupResources2) LookupResources2 added in v1.35.0 

func (crr *CursoredLookupResources2) LookupResources2(
	req ValidatedLookupResources2Request,
	stream dispatch.LookupResources2Stream,
) error

type CursoredLookupResources3 added in v1.45.4 

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

CursoredLookupResources3 is a dispatch implementation for the LookupResources3 operation.

func NewCursoredLookupResources3 added in v1.45.4 

func NewCursoredLookupResources3(
	dl dispatch.LookupResources3,
	dc dispatch.Check,
	caveatTypeSet *caveattypes.TypeSet,
	concurrencyLimit uint16,
	dispatchChunkSize uint16,
	chunkCache cache.Cache[cache.StringKey, any],
) (*CursoredLookupResources3, error)

NewCursoredLookupResources3 creates a new CursoredLookupResources3 instance with the given parameters.

func (*CursoredLookupResources3) LookupResources3 added in v1.45.4 

func (crr *CursoredLookupResources3) LookupResources3(req ValidatedLookupResources3Request, stream dispatch.LookupResources3Stream) error

LookupResources3 implements the LookupResources operation, which finds all resources of a given type that a subject can access via a specific permission.

Algorithm Overview

LookupResources3 uses a multi-phase iterator-based approach to efficiently traverse the permission graph and find accessible resources. The algorithm operates in two main portions:

## Portion #1: Direct Subject Match

If the subject's type and relation exactly match the resource's type and relation, the subject IDs are immediately returned as accessible resources (a permission always grants access to itself). 

Example: user:alice#... accessing user:alice#... → immediate match

## Portion #2: Entrypoint-Based Traversal

For cases where traversal is needed, the algorithm identifies "entrypoints" - relations or permissions that provide paths from the subject type to the target resource permission. 

Example: user:alice → document:doc1#read
Entrypoints might be: document#viewer, document#editor (both lead to #read)

Iterator Architecture

The implementation uses a sophisticated iterator pipeline built from three core iterator patterns: 

┌──────────────────────────────────────────────────────────────────────────────┐
│                         LookupResources3 Iterator Flow                       │
├──────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│  ┌─────────────────┐    ┌──────────────────────────────────────────────────┐ │
│  │ Direct Subject  │    │              Entrypoints Iterator                │ │
│  │ Match Iterator  │    │                                                  │ │
│  │                 │    │  ┌─────────────────────────────────────────────┐ │ │
│  │ CursoredWith    │ ┌──┤  │         Parallel Entrypoint Executors       │ │ │
│  │ IntegerHeader   │ │  │  │                                             │ │ │
│  │                 │ │  │  │  ┌──────────┐  ┌──────────┐  ┌──────────┐   │ │ │
│  └─────────────────┘ │  │  │  │Entrypoint│  │Entrypoint│  │Entrypoint│   │ │ │
│                      │  │  │  │    #1    │  │    #2    │  │    #N    │   │ │ │
│                      │  │  │  └──────────┘  └──────────┘  └──────────┘   │ │ │
│                      │  │  │        │            │            │          │ │ │
│                      │  │  └─────────────────────────────────────────────┘ │ │
│                      │  │                     │                            │ │
│                      │  │  ┌─────────────────────────────────────────────┐ │ │
│                      │  │  │     CursoredParallelIterators               │ │ │
│                      │  │  │   (executes entrypoints concurrently)       │ │ │
│                      │  │  └─────────────────────────────────────────────┘ │ │
│                      │  └──────────────────────────────────────────────────┘ │
│                      │                                                       │
│                      └──────────────────┬────────────────────────────────────┘
│                                         │                                    │
│                              ┌─────────────────────┐                         │
│                              │   Combined Results  │                         │
│                              │    (yields to       │                         │
│                              │   response stream)  │                         │
│                              └─────────────────────┘                         │
└──────────────────────────────────────────────────────────────────────────────┘

For each entrypoint, implements a producer-mapper pattern: - Producer: Fetches relationship chunks from the datastore - Mapper: Processes chunks by dispatching or checking, then recursively calling LookupResources3 

┌─────────────────────────────────────────────────────────────────────────────┐
│                    Per-Entrypoint Processing Flow                           │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│  ┌─────────────────┐     ┌──────────────────┐     ┌──────────────────────┐  │
│  │   Entrypoint    │────▶│  Relationships   │────▶│     Processing       │  │
│  │   Analyzer      │     │     Iterator     │     │      (Mapper)        │  │
│  │                 │     │   (Producer)     │     │                      │  │
│  │ • Relation EP   │     │                  │     │ ┌──────────────────┐ │  │
│  │ • Computed EP   │     │ Fetches chunks   │     │ │  Filter via      │ │  │
│  │ • TTU EP        │     │ of relationships │     │ │  Check (if not   │ │  │
│  │                 │     │ from datastore   │     │ │  direct result)  │ │  │
│  └─────────────────┘     │                  │     │ └──────────────────┘ │  │
│                          │ Honors cursor    │     │          │           │  │
│                          │ for resumption   │     │          ▼           │  │
│                          │                  │     │ ┌──────────────────┐ │  │
│                          └──────────────────┘     │ │ Dispatch to      │ │  │
│                                                   │ │ LookupResources3 │ │  │
│                                                   │ │ (recursive)      │ │  │
│                                                   │ └──────────────────┘ │  │
│                                                   └──────────────────────┘  │
└─────────────────────────────────────────────────────────────────────────────┘

Entrypoint Types

The algorithm handles three types of entrypoints based on schema reachability analysis:

1. **Relation Entrypoints**: Direct relation traversal

  • Example: document#viewer → find all documents where subjects are viewers
  • Query: SELECT resource_id FROM relations WHERE subject IN (...) AND relation = 'viewer'

2. **Computed User Set Entrypoints**: Permission rewrites

  • Example: document#view = viewer → rewrite subjects as document#view
  • Structural transformation without datastore queries

3. **Tupleset-to-Userset Entrypoints** (Arrows): Indirect relation traversal

  • Example: document#read = viewer + parent->read
  • Find documents where subjects are in 'parent' relation, then check 'read' on those parents

Chunk Processing and Dispatch

Relationships are processed in configurable chunks (dispatchChunkSize) to balance memory usage and dispatch efficiency. Each chunk undergoes:

1. **Caveat Evaluation**: Relationships with caveats are evaluated against the request context

  • Caveats that fail are filtered out early (tree shearing)
  • Partial results collect missing context parameters

2. **Check Filtering**: For non-direct entrypoints, found resources are validated via Check dispatch

  • Filters out resources that don't actually grant the permission (intersection/exclusion handling)
  • Only validated resources proceed to recursive dispatch

3. **Recursive Dispatch**: Validated resource IDs become subject IDs for the next LookupResources3 call

  • Creates new dispatch requests with found resources as subjects
  • Continues until reaching the target resource type and permission

Cursor Management

The cursor system enables efficient pagination and resumption: 

Cursor Structure: [header_index, entrypoint_index, datastore_cursor, remaining...]
                   │             │                 │                 │
                   │             │                 │                 └─ Nested dispatch cursor
                   │             │                 └─ Position in relationship stream
                   │             └─ Which entrypoint is being processed
                   └─ Position in subject IDs list (-1 = header complete)

This allows the operation to resume at any point in the complex iteration hierarchy without losing progress or re-processing completed work.

type ExpandReducer 

type ExpandReducer func(
	ctx context.Context,
	start *core.ObjectAndRelation,
	requests []ReduceableExpandFunc,
) ExpandResult

ExpandReducer is a type for the functions Any and All which combine check results.

type ExpandResult 

type ExpandResult struct {
	Resp *v1.DispatchExpandResponse
	Err  error
}

ExpandResult is the data that is returned by a single expand or sub-expand.

func (ExpandResult) ResultError added in v1.35.0 

func (er ExpandResult) ResultError() error

type ExpansionFailureError added in v1.39.0 

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

ExpansionFailureError occurs when expansion failed in some manner. Note this should not apply to namespaces and relations not being found.

func (ExpansionFailureError) Unwrap added in v1.39.0 

func (e ExpansionFailureError) Unwrap() error

type InvalidCursorError added in v1.39.0 

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

InvalidCursorError is returned when a cursor is no longer valid.

func (InvalidCursorError) GRPCStatus added in v1.39.0 

func (err InvalidCursorError) GRPCStatus() *status.Status

GRPCStatus implements retrieving the gRPC status for the error.

type MembershipSet added in v1.13.0 

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

MembershipSet is a helper set that trackes the membership results for a dispatched Check request, including tracking of the caveats associated with found resource IDs.

func NewMembershipSet added in v1.13.0 

func NewMembershipSet() *MembershipSet

NewMembershipSet constructs a new helper set for tracking the membership found for a dispatched check request.

func (*MembershipSet) AddDirectMember added in v1.13.0 

func (ms *MembershipSet) AddDirectMember(resourceID string, caveat *core.ContextualizedCaveat)

AddDirectMember adds a resource ID that was *directly* found for the dispatched check, with optional caveat found on the relationship.

func (*MembershipSet) AddMemberViaRelationship added in v1.13.0 

func (ms *MembershipSet) AddMemberViaRelationship(
	resourceID string,
	resourceCaveatExpression *core.CaveatExpression,
	parentRelationship tuple.Relationship,
)

AddMemberViaRelationship adds a resource ID that was found via another relationship, such as the result of an arrow operation. The `parentRelationship` is the relationship that was followed before the resource itself was resolved. This method will properly apply the caveat(s) from both the parent relationship and the resource's result itself, assuming either have a caveat associated.

func (*MembershipSet) AddMemberWithOptionalCaveats added in v1.35.0 

func (ms *MembershipSet) AddMemberWithOptionalCaveats(
	resourceID string,
	caveats []*core.CaveatExpression,
)

AddMemberWithOptionalCaveats adds the given resource ID as a member with the optional caveats combined via intersection.

func (*MembershipSet) AddMemberWithParentCaveat added in v1.36.0 

func (ms *MembershipSet) AddMemberWithParentCaveat(
	resourceID string,
	resourceCaveatExpression *core.CaveatExpression,
	parentCaveat *core.ContextualizedCaveat,
)

AddMemberWithParentCaveat adds the given resource ID as a member with the parent caveat combined via intersection with the resource's caveat. The parent caveat may be nil.

func (*MembershipSet) AsCheckResultsMap added in v1.13.0 

func (ms *MembershipSet) AsCheckResultsMap() CheckResultsMap

AsCheckResultsMap converts the membership set back into a CheckResultsMap for placement into a DispatchCheckResult.

func (*MembershipSet) GetResourceID added in v1.35.0 

func (ms *MembershipSet) GetResourceID(resourceID string) (bool, *core.CaveatExpression)

GetResourceID returns a bool indicating whether the resource is found in the set and the associated caveat expression, if any.

func (*MembershipSet) HasConcreteResourceID added in v1.16.0 

func (ms *MembershipSet) HasConcreteResourceID(resourceID string) bool

HasConcreteResourceID returns whether the resourceID was found in the set and has no caveat attached.

func (*MembershipSet) HasDeterminedMember added in v1.13.0 

func (ms *MembershipSet) HasDeterminedMember() bool

HasDeterminedMember returns whether there exists at least one non-caveated member of the set.

func (*MembershipSet) IntersectWith added in v1.13.0 

func (ms *MembershipSet) IntersectWith(resultsMap CheckResultsMap)

IntersectWith intersects the results found in the given map with the members of this set. The changes are made in-place.

func (*MembershipSet) IsEmpty added in v1.13.0 

func (ms *MembershipSet) IsEmpty() bool

IsEmpty returns true if the set is empty.

func (*MembershipSet) Size added in v1.16.0 

func (ms *MembershipSet) Size() int

Size returns the number of elements in the membership set.

func (*MembershipSet) Subtract added in v1.13.0 

func (ms *MembershipSet) Subtract(resultsMap CheckResultsMap)

Subtract subtracts the results found in the given map with the members of this set. The changes are made in-place.

func (*MembershipSet) UnionWith added in v1.13.0 

func (ms *MembershipSet) UnionWith(resultsMap CheckResultsMap)

UnionWith combines the results found in the given map with the members of this set. The changes are made in-place.

type ReduceableExpandFunc 

type ReduceableExpandFunc func(ctx context.Context, resultChan chan<- ExpandResult)

ReduceableExpandFunc is a function that can be bound to a execution context.

type RelationMissingTypeInfoError added in v1.39.0 

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

RelationMissingTypeInfoError defines an error for when type information is missing from a relation during a lookup.

func (RelationMissingTypeInfoError) DetailsMetadata added in v1.39.0 

func (err RelationMissingTypeInfoError) DetailsMetadata() map[string]string

DetailsMetadata returns the metadata for details for this error.

func (RelationMissingTypeInfoError) MarshalZerologObject added in v1.39.0 

func (err RelationMissingTypeInfoError) MarshalZerologObject(e *zerolog.Event)

func (RelationMissingTypeInfoError) NamespaceName added in v1.39.0 

func (err RelationMissingTypeInfoError) NamespaceName() string

NamespaceName returns the name of the namespace in which the relation was found.

func (RelationMissingTypeInfoError) RelationName added in v1.39.0 

func (err RelationMissingTypeInfoError) RelationName() string

RelationName returns the name of the relation missing type information.

type RelationNotFoundError added in v1.39.0 

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

RelationNotFoundError occurs when a relation was not found under a namespace.

func (RelationNotFoundError) DetailsMetadata added in v1.39.0 

func (err RelationNotFoundError) DetailsMetadata() map[string]string

DetailsMetadata returns the metadata for details for this error.

func (RelationNotFoundError) MarshalZerologObject added in v1.39.0 

func (err RelationNotFoundError) MarshalZerologObject(e *zerolog.Event)

func (RelationNotFoundError) NamespaceName added in v1.39.0 

func (err RelationNotFoundError) NamespaceName() string

NamespaceName returns the name of the namespace in which the relation was not found.

func (RelationNotFoundError) NotFoundRelationName added in v1.39.0 

func (err RelationNotFoundError) NotFoundRelationName() string

NotFoundRelationName returns the name of the relation not found.

type Traits added in v1.40.0 

type Traits struct {
	HasCaveats    bool
	HasExpiration bool
}

func TraitsForArrowRelation added in v1.40.0 

func TraitsForArrowRelation(ctx context.Context, reader datastore.Reader, namespaceName string, relationName string) (Traits, error)

TraitsForArrowRelation returns traits such as HasCaveats and HasExpiration if *any* of the subject types of the given relation support caveats or expiration.

type UnimplementedError added in v1.39.0 

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

UnimplementedError is returned when some functionality is not yet supported.

func (UnimplementedError) Unwrap added in v1.39.0 

func (e UnimplementedError) Unwrap() error

type UniquelyKeyed added in v1.45.4 

type UniquelyKeyed interface {
	// UniqueKey returns a unique key for the item, which is used to track concurrency limits.
	UniqueKey() (string, error)
}

UniquelyKeyed is an interface that requires implementing a UniqueKey method.

type ValidatedCheckRequest added in v1.3.0 

type ValidatedCheckRequest struct {
	*v1.DispatchCheckRequest
	Revision datastore.Revision

	// OriginalRelationName is the original relation/permission name that was used in the request,
	// before being changed due to aliasing.
	OriginalRelationName string
}

ValidatedCheckRequest represents a request after it has been validated and parsed for internal consumption.

type ValidatedExpandRequest added in v1.3.0 

type ValidatedExpandRequest struct {
	*v1.DispatchExpandRequest
	Revision datastore.Revision
}

ValidatedExpandRequest represents a request after it has been validated and parsed for internal consumption.

type ValidatedLookupResources2Request added in v1.35.0 

type ValidatedLookupResources2Request struct {
	*v1.DispatchLookupResources2Request
	Revision datastore.Revision
}

type ValidatedLookupResources3Request added in v1.45.4 

type ValidatedLookupResources3Request struct {
	*v1.DispatchLookupResources3Request
	Revision datastore.Revision
}

ValidatedLookupResources3Request is a wrapper around the DispatchLookupResources3Request that includes a revision for the datastore reader, and indicates that the request has been validated.

type ValidatedLookupSubjectsRequest added in v1.12.0 

type ValidatedLookupSubjectsRequest struct {
	*v1.DispatchLookupSubjectsRequest
	Revision datastore.Revision
}

ValidatedLookupSubjectsRequest represents a request after it has been validated and parsed for internal consumption.

type WildcardNotAllowedError added in v1.39.0 

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

WildcardNotAllowedError occurs when a request sent has an invalid wildcard argument.

func (WildcardNotAllowedError) GRPCStatus added in v1.39.0 

func (err WildcardNotAllowedError) GRPCStatus() *status.Status

GRPCStatus implements retrieving the gRPC status for the error.

Source Files

View all Source files

Directories

Path Synopsis

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.