feat: connect to spicedb

7 files changed, 783 insertions, 0 deletions

diff --git a/vendor/github.com/authzed/spicedb/internal/namespace/aliasing.go b/vendor/github.com/authzed/spicedb/internal/namespace/aliasing.go
new file mode 100644
index 0000000..adbaa94
--- /dev/null
+++ b/vendor/github.com/authzed/spicedb/internal/namespace/aliasing.go
@@ -0,0 +1,82 @@
+package namespace
+
+import (
+	"sort"
+
+	"github.com/authzed/spicedb/pkg/schema"
+)
+
+// computePermissionAliases computes a map of aliases between the various permissions in a
+// namespace. A permission is considered an alias if it *directly* refers to another permission
+// or relation without any other form of expression.
+func computePermissionAliases(typeDefinition *schema.ValidatedDefinition) (map[string]string, error) {
+	aliases := map[string]string{}
+	done := map[string]struct{}{}
+	unresolvedAliases := map[string]string{}
+
+	for _, rel := range typeDefinition.Namespace().Relation {
+		// Ensure the relation has a rewrite...
+		if rel.GetUsersetRewrite() == nil {
+			done[rel.Name] = struct{}{}
+			continue
+		}
+
+		// ... with a union ...
+		union := rel.GetUsersetRewrite().GetUnion()
+		if union == nil {
+			done[rel.Name] = struct{}{}
+			continue
+		}
+
+		// ... with a single child ...
+		if len(union.Child) != 1 {
+			done[rel.Name] = struct{}{}
+			continue
+		}
+
+		// ... that is a computed userset.
+		computedUserset := union.Child[0].GetComputedUserset()
+		if computedUserset == nil {
+			done[rel.Name] = struct{}{}
+			continue
+		}
+
+		// If the aliased item is a relation, then we've found the alias target.
+		aliasedPermOrRel := computedUserset.GetRelation()
+		if !typeDefinition.IsPermission(aliasedPermOrRel) {
+			done[rel.Name] = struct{}{}
+			aliases[rel.Name] = aliasedPermOrRel
+			continue
+		}
+
+		// Otherwise, add the permission to the working set.
+		unresolvedAliases[rel.Name] = aliasedPermOrRel
+	}
+
+	for len(unresolvedAliases) > 0 {
+		startingCount := len(unresolvedAliases)
+		for relName, aliasedPermission := range unresolvedAliases {
+			if _, ok := done[aliasedPermission]; ok {
+				done[relName] = struct{}{}
+
+				if alias, ok := aliases[aliasedPermission]; ok {
+					aliases[relName] = alias
+				} else {
+					aliases[relName] = aliasedPermission
+				}
+				delete(unresolvedAliases, relName)
+				continue
+			}
+		}
+		if len(unresolvedAliases) == startingCount {
+			keys := make([]string, 0, len(unresolvedAliases))
+			for key := range unresolvedAliases {
+				keys = append(keys, key)
+			}
+			sort.Strings(keys)
+			return nil, NewPermissionsCycleErr(typeDefinition.Namespace().Name, keys)
+		}
+	}
+
+	return aliases, nil
+}
diff --git a/vendor/github.com/authzed/spicedb/internal/namespace/annotate.go b/vendor/github.com/authzed/spicedb/internal/namespace/annotate.go
new file mode 100644
index 0000000..d85edff
--- /dev/null
+++ b/vendor/github.com/authzed/spicedb/internal/namespace/annotate.go
@@ -0,0 +1,29 @@
+package namespace
+
+import "github.com/authzed/spicedb/pkg/schema"
+
+// AnnotateNamespace annotates the namespace in the type system with computed aliasing and cache key
+// metadata for more efficient dispatching.
+func AnnotateNamespace(def *schema.ValidatedDefinition) error {
+	aliases, aerr := computePermissionAliases(def)
+	if aerr != nil {
+		return aerr
+	}
+
+	cacheKeys, cerr := computeCanonicalCacheKeys(def, aliases)
+	if cerr != nil {
+		return cerr
+	}
+
+	for _, rel := range def.Namespace().Relation {
+		if alias, ok := aliases[rel.Name]; ok {
+			rel.AliasingRelation = alias
+		}
+
+		if cacheKey, ok := cacheKeys[rel.Name]; ok {
+			rel.CanonicalCacheKey = cacheKey
+		}
+	}
+
+	return nil
+}
diff --git a/vendor/github.com/authzed/spicedb/internal/namespace/canonicalization.go b/vendor/github.com/authzed/spicedb/internal/namespace/canonicalization.go
new file mode 100644
index 0000000..24fa61e
--- /dev/null
+++ b/vendor/github.com/authzed/spicedb/internal/namespace/canonicalization.go
@@ -0,0 +1,282 @@
+package namespace
+
+import (
+	"encoding/hex"
+	"hash/fnv"
+
+	"github.com/authzed/spicedb/pkg/schema"
+	"github.com/authzed/spicedb/pkg/spiceerrors"
+
+	"github.com/dalzilio/rudd"
+
+	"github.com/authzed/spicedb/pkg/graph"
+	core "github.com/authzed/spicedb/pkg/proto/core/v1"
+)
+
+const computedKeyPrefix = "%"
+
+// computeCanonicalCacheKeys computes a map from permission name to associated canonicalized
+// cache key for each non-aliased permission in the given type system's namespace.
+//
+// Canonicalization works by taking each permission's userset rewrite expression and transforming
+// it into a Binary Decision Diagram (BDD) via the `rudd` library.
+//
+// Each access of a relation or arrow is assigned a unique integer ID within the *namespace*,
+// and the operations (+, -, &) are converted into binary operations.
+//
+// For example, for the namespace:
+//
+//	definition somenamespace {
+//	   relation first: ...
+//	   relation second: ...
+//	   relation third: ...
+//	   permission someperm = second + (first - third->something)
+//	}
+//
+// We begin by assigning a unique integer index to each relation and arrow found for all
+// expressions in the namespace:
+//
+//	  definition somenamespace {
+//		 relation first: ...
+//	              ^ index 0
+//	     relation second: ...
+//	              ^ index 1
+//	     relation third: ...
+//	              ^ index 2
+//	     permission someperm = second + (first - third->something)
+//	                           ^ 1       ^ 0     ^ index 3
+//	  }
+//
+// These indexes are then used with the rudd library to build the expression:
+//
+//	someperm => `bdd.Or(bdd.Ithvar(1), bdd.And(bdd.Ithvar(0), bdd.NIthvar(2)))`
+//
+// The `rudd` library automatically handles associativity, and produces a hash representing the
+// canonical representation of the binary expression. These hashes can then be used for caching,
+// representing the same *logical* expressions for a permission, even if the relations have
+// different names.
+func computeCanonicalCacheKeys(typeDef *schema.ValidatedDefinition, aliasMap map[string]string) (map[string]string, error) {
+	varMap, err := buildBddVarMap(typeDef.Namespace().Relation, aliasMap)
+	if err != nil {
+		return nil, err
+	}
+
+	if varMap.Len() == 0 {
+		return map[string]string{}, nil
+	}
+
+	bdd, err := rudd.New(varMap.Len())
+	if err != nil {
+		return nil, err
+	}
+
+	// For each permission, build a canonicalized cache key based on its expression.
+	cacheKeys := make(map[string]string, len(typeDef.Namespace().Relation))
+	for _, rel := range typeDef.Namespace().Relation {
+		rewrite := rel.GetUsersetRewrite()
+		if rewrite == nil {
+			// If the relation has no rewrite (making it a pure relation), then its canonical
+			// key is simply the relation's name.
+			cacheKeys[rel.Name] = rel.Name
+			continue
+		}
+
+		hasher := fnv.New64a()
+		node, err := convertRewriteToBdd(rel, bdd, rewrite, varMap)
+		if err != nil {
+			return nil, err
+		}
+
+		bdd.Print(hasher, node)
+		cacheKeys[rel.Name] = computedKeyPrefix + hex.EncodeToString(hasher.Sum(nil))
+	}
+
+	return cacheKeys, nil
+}
+
+func convertRewriteToBdd(relation *core.Relation, bdd *rudd.BDD, rewrite *core.UsersetRewrite, varMap bddVarMap) (rudd.Node, error) {
+	switch rw := rewrite.RewriteOperation.(type) {
+	case *core.UsersetRewrite_Union:
+		return convertToBdd(relation, bdd, rw.Union, bdd.Or, func(childIndex int, varIndex int) rudd.Node {
+			return bdd.Ithvar(varIndex)
+		}, varMap)
+
+	case *core.UsersetRewrite_Intersection:
+		return convertToBdd(relation, bdd, rw.Intersection, bdd.And, func(childIndex int, varIndex int) rudd.Node {
+			return bdd.Ithvar(varIndex)
+		}, varMap)
+
+	case *core.UsersetRewrite_Exclusion:
+		return convertToBdd(relation, bdd, rw.Exclusion, bdd.And, func(childIndex int, varIndex int) rudd.Node {
+			if childIndex == 0 {
+				return bdd.Ithvar(varIndex)
+			}
+			return bdd.NIthvar(varIndex)
+		}, varMap)
+
+	default:
+		return nil, spiceerrors.MustBugf("Unknown rewrite kind %v", rw)
+	}
+}
+
+type (
+	combiner func(n ...rudd.Node) rudd.Node
+	builder  func(childIndex int, varIndex int) rudd.Node
+)
+
+func convertToBdd(relation *core.Relation, bdd *rudd.BDD, so *core.SetOperation, combiner combiner, builder builder, varMap bddVarMap) (rudd.Node, error) {
+	values := make([]rudd.Node, 0, len(so.Child))
+	for index, childOneof := range so.Child {
+		switch child := childOneof.ChildType.(type) {
+		case *core.SetOperation_Child_XThis:
+			return nil, spiceerrors.MustBugf("use of _this is disallowed")
+
+		case *core.SetOperation_Child_ComputedUserset:
+			cuIndex, err := varMap.Get(child.ComputedUserset.Relation)
+			if err != nil {
+				return nil, err
+			}
+
+			values = append(values, builder(index, cuIndex))
+
+		case *core.SetOperation_Child_UsersetRewrite:
+			node, err := convertRewriteToBdd(relation, bdd, child.UsersetRewrite, varMap)
+			if err != nil {
+				return nil, err
+			}
+
+			values = append(values, node)
+
+		case *core.SetOperation_Child_TupleToUserset:
+			arrowIndex, err := varMap.GetArrow(child.TupleToUserset.Tupleset.Relation, child.TupleToUserset.ComputedUserset.Relation)
+			if err != nil {
+				return nil, err
+			}
+
+			values = append(values, builder(index, arrowIndex))
+
+		case *core.SetOperation_Child_FunctionedTupleToUserset:
+			switch child.FunctionedTupleToUserset.Function {
+			case core.FunctionedTupleToUserset_FUNCTION_ANY:
+				arrowIndex, err := varMap.GetArrow(child.FunctionedTupleToUserset.Tupleset.Relation, child.FunctionedTupleToUserset.ComputedUserset.Relation)
+				if err != nil {
+					return nil, err
+				}
+
+				values = append(values, builder(index, arrowIndex))
+
+			case core.FunctionedTupleToUserset_FUNCTION_ALL:
+				arrowIndex, err := varMap.GetIntersectionArrow(child.FunctionedTupleToUserset.Tupleset.Relation, child.FunctionedTupleToUserset.ComputedUserset.Relation)
+				if err != nil {
+					return nil, err
+				}
+
+				values = append(values, builder(index, arrowIndex))
+
+			default:
+				return nil, spiceerrors.MustBugf("unknown function %v", child.FunctionedTupleToUserset.Function)
+			}
+
+		case *core.SetOperation_Child_XNil:
+			values = append(values, builder(index, varMap.Nil()))
+
+		default:
+			return nil, spiceerrors.MustBugf("unknown set operation child %T", child)
+		}
+	}
+	return combiner(values...), nil
+}
+
+type bddVarMap struct {
+	aliasMap map[string]string
+	varMap   map[string]int
+}
+
+func (bvm bddVarMap) GetArrow(tuplesetName string, relName string) (int, error) {
+	key := tuplesetName + "->" + relName
+	index, ok := bvm.varMap[key]
+	if !ok {
+		return -1, spiceerrors.MustBugf("missing arrow key %s in varMap", key)
+	}
+	return index, nil
+}
+
+func (bvm bddVarMap) GetIntersectionArrow(tuplesetName string, relName string) (int, error) {
+	key := tuplesetName + "-(all)->" + relName
+	index, ok := bvm.varMap[key]
+	if !ok {
+		return -1, spiceerrors.MustBugf("missing intersection arrow key %s in varMap", key)
+	}
+	return index, nil
+}
+
+func (bvm bddVarMap) Nil() int {
+	return len(bvm.varMap)
+}
+
+func (bvm bddVarMap) Get(relName string) (int, error) {
+	if alias, ok := bvm.aliasMap[relName]; ok {
+		return bvm.Get(alias)
+	}
+
+	index, ok := bvm.varMap[relName]
+	if !ok {
+		return -1, spiceerrors.MustBugf("missing key %s in varMap", relName)
+	}
+	return index, nil
+}
+
+func (bvm bddVarMap) Len() int {
+	return len(bvm.varMap) + 1 // +1 for `nil`
+}
+
+func buildBddVarMap(relations []*core.Relation, aliasMap map[string]string) (bddVarMap, error) {
+	varMap := map[string]int{}
+	for _, rel := range relations {
+		if _, ok := aliasMap[rel.Name]; ok {
+			continue
+		}
+
+		varMap[rel.Name] = len(varMap)
+
+		rewrite := rel.GetUsersetRewrite()
+		if rewrite == nil {
+			continue
+		}
+
+		_, err := graph.WalkRewrite(rewrite, func(childOneof *core.SetOperation_Child) (interface{}, error) {
+			switch child := childOneof.ChildType.(type) {
+			case *core.SetOperation_Child_TupleToUserset:
+				key := child.TupleToUserset.Tupleset.Relation + "->" + child.TupleToUserset.ComputedUserset.Relation
+				if _, ok := varMap[key]; !ok {
+					varMap[key] = len(varMap)
+				}
+			case *core.SetOperation_Child_FunctionedTupleToUserset:
+				key := child.FunctionedTupleToUserset.Tupleset.Relation + "->" + child.FunctionedTupleToUserset.ComputedUserset.Relation
+
+				switch child.FunctionedTupleToUserset.Function {
+				case core.FunctionedTupleToUserset_FUNCTION_ANY:
+					// Use the key.
+
+				case core.FunctionedTupleToUserset_FUNCTION_ALL:
+					key = child.FunctionedTupleToUserset.Tupleset.Relation + "-(all)->" + child.FunctionedTupleToUserset.ComputedUserset.Relation
+
+				default:
+					return nil, spiceerrors.MustBugf("unknown function %v", child.FunctionedTupleToUserset.Function)
+				}
+
+				if _, ok := varMap[key]; !ok {
+					varMap[key] = len(varMap)
+				}
+			}
+			return nil, nil
+		})
+		if err != nil {
+			return bddVarMap{}, err
+		}
+	}
+	return bddVarMap{
+		aliasMap: aliasMap,
+		varMap:   varMap,
+	}, nil
+}
diff --git a/vendor/github.com/authzed/spicedb/internal/namespace/caveats.go b/vendor/github.com/authzed/spicedb/internal/namespace/caveats.go
new file mode 100644
index 0000000..5ddfa9d
--- /dev/null
+++ b/vendor/github.com/authzed/spicedb/internal/namespace/caveats.go
@@ -0,0 +1,69 @@
+package namespace
+
+import (
+	"fmt"
+
+	"golang.org/x/exp/maps"
+
+	"github.com/authzed/spicedb/pkg/caveats"
+	caveattypes "github.com/authzed/spicedb/pkg/caveats/types"
+	core "github.com/authzed/spicedb/pkg/proto/core/v1"
+	"github.com/authzed/spicedb/pkg/schema"
+)
+
+// ValidateCaveatDefinition validates the parameters and types within the given caveat
+// definition, including usage of the parameters.
+func ValidateCaveatDefinition(ts *caveattypes.TypeSet, caveat *core.CaveatDefinition) error {
+	// Ensure all parameters are used by the caveat expression itself.
+	parameterTypes, err := caveattypes.DecodeParameterTypes(ts, caveat.ParameterTypes)
+	if err != nil {
+		return schema.NewTypeWithSourceError(
+			fmt.Errorf("could not decode caveat parameters `%s`: %w", caveat.Name, err),
+			caveat,
+			caveat.Name,
+		)
+	}
+
+	deserialized, err := caveats.DeserializeCaveatWithTypeSet(ts, caveat.SerializedExpression, parameterTypes)
+	if err != nil {
+		return schema.NewTypeWithSourceError(
+			fmt.Errorf("could not decode caveat `%s`: %w", caveat.Name, err),
+			caveat,
+			caveat.Name,
+		)
+	}
+
+	if len(caveat.ParameterTypes) == 0 {
+		return schema.NewTypeWithSourceError(
+			fmt.Errorf("caveat `%s` must have at least one parameter defined", caveat.Name),
+			caveat,
+			caveat.Name,
+		)
+	}
+
+	referencedNames, err := deserialized.ReferencedParameters(maps.Keys(caveat.ParameterTypes))
+	if err != nil {
+		return err
+	}
+
+	for paramName, paramType := range caveat.ParameterTypes {
+		_, err := caveattypes.DecodeParameterType(ts, paramType)
+		if err != nil {
+			return schema.NewTypeWithSourceError(
+				fmt.Errorf("type error for parameter `%s` for caveat `%s`: %w", paramName, caveat.Name, err),
+				caveat,
+				paramName,
+			)
+		}
+
+		if !referencedNames.Has(paramName) {
+			return schema.NewTypeWithSourceError(
+				NewUnusedCaveatParameterErr(caveat.Name, paramName),
+				caveat,
+				paramName,
+			)
+		}
+	}
+
+	return nil
+}
diff --git a/vendor/github.com/authzed/spicedb/internal/namespace/doc.go b/vendor/github.com/authzed/spicedb/internal/namespace/doc.go
new file mode 100644
index 0000000..1546280
--- /dev/null
+++ b/vendor/github.com/authzed/spicedb/internal/namespace/doc.go
@@ -0,0 +1,2 @@
+// Package namespace provides functions for dealing with and validating types, relations and caveats.
+package namespace
diff --git a/vendor/github.com/authzed/spicedb/internal/namespace/errors.go b/vendor/github.com/authzed/spicedb/internal/namespace/errors.go
new file mode 100644
index 0000000..abe7fe6
--- /dev/null
+++ b/vendor/github.com/authzed/spicedb/internal/namespace/errors.go
@@ -0,0 +1,171 @@
+package namespace
+
+import (
+	"fmt"
+	"strings"
+
+	"github.com/rs/zerolog"
+
+	"github.com/authzed/spicedb/internal/sharederrors"
+)
+
+// NamespaceNotFoundError occurs when a namespace was not found.
+type NamespaceNotFoundError struct {
+	error
+	namespaceName string
+}
+
+// NotFoundNamespaceName is the name of the namespace not found.
+func (err NamespaceNotFoundError) NotFoundNamespaceName() string {
+	return err.namespaceName
+}
+
+// MarshalZerologObject implements zerolog object marshalling.
+func (err NamespaceNotFoundError) MarshalZerologObject(e *zerolog.Event) {
+	e.Err(err.error).Str("namespace", err.namespaceName)
+}
+
+// DetailsMetadata returns the metadata for details for this error.
+func (err NamespaceNotFoundError) DetailsMetadata() map[string]string {
+	return map[string]string{
+		"definition_name": err.namespaceName,
+	}
+}
+
+// RelationNotFoundError occurs when a relation was not found under a namespace.
+type RelationNotFoundError struct {
+	error
+	namespaceName string
+	relationName  string
+}
+
+// NamespaceName returns the name of the namespace in which the relation was not found.
+func (err RelationNotFoundError) NamespaceName() string {
+	return err.namespaceName
+}
+
+// NotFoundRelationName returns the name of the relation not found.
+func (err RelationNotFoundError) NotFoundRelationName() string {
+	return err.relationName
+}
+
+func (err RelationNotFoundError) MarshalZerologObject(e *zerolog.Event) {
+	e.Err(err.error).Str("namespace", err.namespaceName).Str("relation", err.relationName)
+}
+
+// DetailsMetadata returns the metadata for details for this error.
+func (err RelationNotFoundError) DetailsMetadata() map[string]string {
+	return map[string]string{
+		"definition_name":             err.namespaceName,
+		"relation_or_permission_name": err.relationName,
+	}
+}
+
+// DuplicateRelationError occurs when a duplicate relation was found inside a namespace.
+type DuplicateRelationError struct {
+	error
+	namespaceName string
+	relationName  string
+}
+
+// MarshalZerologObject implements zerolog object marshalling.
+func (err DuplicateRelationError) MarshalZerologObject(e *zerolog.Event) {
+	e.Err(err.error).Str("namespace", err.namespaceName).Str("relation", err.relationName)
+}
+
+// DetailsMetadata returns the metadata for details for this error.
+func (err DuplicateRelationError) DetailsMetadata() map[string]string {
+	return map[string]string{
+		"definition_name":             err.namespaceName,
+		"relation_or_permission_name": err.relationName,
+	}
+}
+
+// PermissionsCycleError occurs when a cycle exists within permissions.
+type PermissionsCycleError struct {
+	error
+	namespaceName   string
+	permissionNames []string
+}
+
+// MarshalZerologObject implements zerolog object marshalling.
+func (err PermissionsCycleError) MarshalZerologObject(e *zerolog.Event) {
+	e.Err(err.error).Str("namespace", err.namespaceName).Str("permissions", strings.Join(err.permissionNames, ", "))
+}
+
+// DetailsMetadata returns the metadata for details for this error.
+func (err PermissionsCycleError) DetailsMetadata() map[string]string {
+	return map[string]string{
+		"definition_name":  err.namespaceName,
+		"permission_names": strings.Join(err.permissionNames, ","),
+	}
+}
+
+// UnusedCaveatParameterError indicates that a caveat parameter is unused in the caveat expression.
+type UnusedCaveatParameterError struct {
+	error
+	caveatName string
+	paramName  string
+}
+
+// MarshalZerologObject implements zerolog object marshalling.
+func (err UnusedCaveatParameterError) MarshalZerologObject(e *zerolog.Event) {
+	e.Err(err.error).Str("caveat", err.caveatName).Str("param", err.paramName)
+}
+
+// DetailsMetadata returns the metadata for details for this error.
+func (err UnusedCaveatParameterError) DetailsMetadata() map[string]string {
+	return map[string]string{
+		"caveat_name":    err.caveatName,
+		"parameter_name": err.paramName,
+	}
+}
+
+// NewNamespaceNotFoundErr constructs a new namespace not found error.
+func NewNamespaceNotFoundErr(nsName string) error {
+	return NamespaceNotFoundError{
+		error:         fmt.Errorf("object definition `%s` not found", nsName),
+		namespaceName: nsName,
+	}
+}
+
+// NewRelationNotFoundErr constructs a new relation not found error.
+func NewRelationNotFoundErr(nsName string, relationName string) error {
+	return RelationNotFoundError{
+		error:         fmt.Errorf("relation/permission `%s` not found under definition `%s`", relationName, nsName),
+		namespaceName: nsName,
+		relationName:  relationName,
+	}
+}
+
+// NewDuplicateRelationError constructs an error indicating that a relation was defined more than once in a namespace.
+func NewDuplicateRelationError(nsName string, relationName string) error {
+	return DuplicateRelationError{
+		error:         fmt.Errorf("found duplicate relation/permission name `%s` under definition `%s`", relationName, nsName),
+		namespaceName: nsName,
+		relationName:  relationName,
+	}
+}
+
+// NewPermissionsCycleErr constructs an error indicating that a cycle exists amongst permissions.
+func NewPermissionsCycleErr(nsName string, permissionNames []string) error {
+	return PermissionsCycleError{
+		error:           fmt.Errorf("under definition `%s`, there exists a cycle in permissions: %s", nsName, strings.Join(permissionNames, ", ")),
+		namespaceName:   nsName,
+		permissionNames: permissionNames,
+	}
+}
+
+// NewUnusedCaveatParameterErr constructs indicating that a parameter was unused in a caveat expression.
+func NewUnusedCaveatParameterErr(caveatName string, paramName string) error {
+	return UnusedCaveatParameterError{
+		error:      fmt.Errorf("parameter `%s` for caveat `%s` is unused", paramName, caveatName),
+		caveatName: caveatName,
+		paramName:  paramName,
+	}
+}
+
+var (
+	_ sharederrors.UnknownNamespaceError = NamespaceNotFoundError{}
+	_ sharederrors.UnknownRelationError  = RelationNotFoundError{}
+)
diff --git a/vendor/github.com/authzed/spicedb/internal/namespace/util.go b/vendor/github.com/authzed/spicedb/internal/namespace/util.go
new file mode 100644
index 0000000..497bdfb
--- /dev/null
+++ b/vendor/github.com/authzed/spicedb/internal/namespace/util.go
@@ -0,0 +1,148 @@
+package namespace
+
+import (
+	"context"
+
+	"github.com/authzed/spicedb/pkg/datastore"
+	"github.com/authzed/spicedb/pkg/genutil/mapz"
+	core "github.com/authzed/spicedb/pkg/proto/core/v1"
+)
+
+// ReadNamespaceAndRelation checks that the specified namespace and relation exist in the
+// datastore.
+//
+// Returns NamespaceNotFoundError if the namespace cannot be found.
+// Returns RelationNotFoundError if the relation was not found in the namespace.
+// Returns the direct downstream error for all other unknown error.
+func ReadNamespaceAndRelation(
+	ctx context.Context,
+	namespace string,
+	relation string,
+	ds datastore.Reader,
+) (*core.NamespaceDefinition, *core.Relation, error) {
+	config, _, err := ds.ReadNamespaceByName(ctx, namespace)
+	if err != nil {
+		return nil, nil, err
+	}
+
+	for _, rel := range config.Relation {
+		if rel.Name == relation {
+			return config, rel, nil
+		}
+	}
+
+	return nil, nil, NewRelationNotFoundErr(namespace, relation)
+}
+
+// TypeAndRelationToCheck is a single check of a namespace+relation pair.
+type TypeAndRelationToCheck struct {
+	// NamespaceName is the namespace name to ensure exists.
+	NamespaceName string
+
+	// RelationName is the relation name to ensure exists under the namespace.
+	RelationName string
+
+	// AllowEllipsis, if true, allows for the ellipsis as the RelationName.
+	AllowEllipsis bool
+}
+
+// CheckNamespaceAndRelations ensures that the given namespace+relation checks all succeed. If any fail, returns an error.
+//
+// Returns NamespaceNotFoundError if the namespace cannot be found.
+// Returns RelationNotFoundError if the relation was not found in the namespace.
+// Returns the direct downstream error for all other unknown error.
+func CheckNamespaceAndRelations(ctx context.Context, checks []TypeAndRelationToCheck, ds datastore.Reader) error {
+	nsNames := mapz.NewSet[string]()
+	for _, toCheck := range checks {
+		nsNames.Insert(toCheck.NamespaceName)
+	}
+
+	if nsNames.IsEmpty() {
+		return nil
+	}
+
+	namespaces, err := ds.LookupNamespacesWithNames(ctx, nsNames.AsSlice())
+	if err != nil {
+		return err
+	}
+
+	mappedNamespaces := make(map[string]*core.NamespaceDefinition, len(namespaces))
+	for _, namespace := range namespaces {
+		mappedNamespaces[namespace.Definition.Name] = namespace.Definition
+	}
+
+	for _, toCheck := range checks {
+		nsDef, ok := mappedNamespaces[toCheck.NamespaceName]
+		if !ok {
+			return NewNamespaceNotFoundErr(toCheck.NamespaceName)
+		}
+
+		if toCheck.AllowEllipsis && toCheck.RelationName == datastore.Ellipsis {
+			continue
+		}
+
+		foundRelation := false
+		for _, rel := range nsDef.Relation {
+			if rel.Name == toCheck.RelationName {
+				foundRelation = true
+				break
+			}
+		}
+
+		if !foundRelation {
+			return NewRelationNotFoundErr(toCheck.NamespaceName, toCheck.RelationName)
+		}
+	}
+
+	return nil
+}
+
+// CheckNamespaceAndRelation checks that the specified namespace and relation exist in the
+// datastore.
+//
+// Returns datastore.NamespaceNotFoundError if the namespace cannot be found.
+// Returns RelationNotFoundError if the relation was not found in the namespace.
+// Returns the direct downstream error for all other unknown error.
+func CheckNamespaceAndRelation(
+	ctx context.Context,
+	namespace string,
+	relation string,
+	allowEllipsis bool,
+	ds datastore.Reader,
+) error {
+	config, _, err := ds.ReadNamespaceByName(ctx, namespace)
+	if err != nil {
+		return err
+	}
+
+	if allowEllipsis && relation == datastore.Ellipsis {
+		return nil
+	}
+
+	for _, rel := range config.Relation {
+		if rel.Name == relation {
+			return nil
+		}
+	}
+
+	return NewRelationNotFoundErr(namespace, relation)
+}
+
+// ListReferencedNamespaces returns the names of all namespaces referenced in the
+// given namespace definitions. This includes the namespaces themselves, as well as
+// any found in type information on relations.
+func ListReferencedNamespaces(nsdefs []*core.NamespaceDefinition) []string {
+	referencedNamespaceNamesSet := mapz.NewSet[string]()
+	for _, nsdef := range nsdefs {
+		referencedNamespaceNamesSet.Insert(nsdef.Name)
+
+		for _, relation := range nsdef.Relation {
+			if relation.GetTypeInformation() != nil {
+				for _, allowedRel := range relation.GetTypeInformation().AllowedDirectRelations {
+					referencedNamespaceNamesSet.Insert(allowedRel.GetNamespace())
+				}
+			}
+		}
+	}
+	return referencedNamespaceNamesSet.AsSlice()
+}