diff options
Diffstat (limited to 'vendor/github.com/authzed/spicedb/internal/developmentmembership')
5 files changed, 618 insertions, 0 deletions
diff --git a/vendor/github.com/authzed/spicedb/internal/developmentmembership/doc.go b/vendor/github.com/authzed/spicedb/internal/developmentmembership/doc.go new file mode 100644 index 0000000..325981d --- /dev/null +++ b/vendor/github.com/authzed/spicedb/internal/developmentmembership/doc.go @@ -0,0 +1,2 @@ +// Package developmentmembership defines operations with sets. To be used in tests only. +package developmentmembership diff --git a/vendor/github.com/authzed/spicedb/internal/developmentmembership/foundsubject.go b/vendor/github.com/authzed/spicedb/internal/developmentmembership/foundsubject.go new file mode 100644 index 0000000..bf93d56 --- /dev/null +++ b/vendor/github.com/authzed/spicedb/internal/developmentmembership/foundsubject.go @@ -0,0 +1,127 @@ +package developmentmembership + +import ( + "sort" + "strings" + + core "github.com/authzed/spicedb/pkg/proto/core/v1" + + "github.com/authzed/spicedb/pkg/tuple" +) + +// NewFoundSubject creates a new FoundSubject for a subject and a set of its resources. +func NewFoundSubject(subject *core.DirectSubject, resources ...tuple.ObjectAndRelation) FoundSubject { + return FoundSubject{tuple.FromCoreObjectAndRelation(subject.Subject), nil, subject.CaveatExpression, NewONRSet(resources...)} +} + +// FoundSubject contains a single found subject and all the relationships in which that subject +// is a member which were found via the ONRs expansion. +type FoundSubject struct { + // subject is the subject found. + subject tuple.ObjectAndRelation + + // excludedSubjects are any subjects excluded. Only should be set if subject is a wildcard. + excludedSubjects []FoundSubject + + // caveatExpression is the conditional expression on the found subject. + caveatExpression *core.CaveatExpression + + // resources are the resources under which the subject lives that informed the locating + // of this subject for the root ONR. + resources ONRSet +} + +// GetSubjectId is named to match the Subject interface for the BaseSubjectSet. +// +//nolint:all +func (fs FoundSubject) GetSubjectId() string { + return fs.subject.ObjectID +} + +func (fs FoundSubject) GetCaveatExpression() *core.CaveatExpression { + return fs.caveatExpression +} + +func (fs FoundSubject) GetExcludedSubjects() []FoundSubject { + return fs.excludedSubjects +} + +// Subject returns the Subject of the FoundSubject. +func (fs FoundSubject) Subject() tuple.ObjectAndRelation { + return fs.subject +} + +// WildcardType returns the object type for the wildcard subject, if this is a wildcard subject. +func (fs FoundSubject) WildcardType() (string, bool) { + if fs.subject.ObjectID == tuple.PublicWildcard { + return fs.subject.ObjectType, true + } + + return "", false +} + +// ExcludedSubjectsFromWildcard returns those subjects excluded from the wildcard subject. +// If not a wildcard subject, returns false. +func (fs FoundSubject) ExcludedSubjectsFromWildcard() ([]FoundSubject, bool) { + if fs.subject.ObjectID == tuple.PublicWildcard { + return fs.excludedSubjects, true + } + + return nil, false +} + +func (fs FoundSubject) excludedSubjectStrings() []string { + excludedStrings := make([]string, 0, len(fs.excludedSubjects)) + for _, excludedSubject := range fs.excludedSubjects { + excludedSubjectString := tuple.StringONR(excludedSubject.subject) + if excludedSubject.GetCaveatExpression() != nil { + excludedSubjectString += "[...]" + } + excludedStrings = append(excludedStrings, excludedSubjectString) + } + + sort.Strings(excludedStrings) + return excludedStrings +} + +// ToValidationString returns the FoundSubject in a format that is consumable by the validationfile +// package. +func (fs FoundSubject) ToValidationString() string { + onrString := tuple.StringONR(fs.Subject()) + validationString := onrString + if fs.caveatExpression != nil { + validationString = validationString + "[...]" + } + + excluded, isWildcard := fs.ExcludedSubjectsFromWildcard() + if isWildcard && len(excluded) > 0 { + validationString = validationString + " - {" + strings.Join(fs.excludedSubjectStrings(), ", ") + "}" + } + + return validationString +} + +func (fs FoundSubject) String() string { + return fs.ToValidationString() +} + +// ParentResources returns all the resources in which the subject was found as per the expand. +func (fs FoundSubject) ParentResources() []tuple.ObjectAndRelation { + return fs.resources.AsSlice() +} + +// FoundSubjects contains the subjects found for a specific ONR. +type FoundSubjects struct { + // subjects is a map from the Subject ONR (as a string) to the FoundSubject information. + subjects *TrackingSubjectSet +} + +// ListFound returns a slice of all the FoundSubject's. +func (fs FoundSubjects) ListFound() []FoundSubject { + return fs.subjects.ToSlice() +} + +// LookupSubject returns the FoundSubject for a matching subject, if any. +func (fs FoundSubjects) LookupSubject(subject tuple.ObjectAndRelation) (FoundSubject, bool) { + return fs.subjects.Get(subject) +} diff --git a/vendor/github.com/authzed/spicedb/internal/developmentmembership/membership.go b/vendor/github.com/authzed/spicedb/internal/developmentmembership/membership.go new file mode 100644 index 0000000..caa5e8f --- /dev/null +++ b/vendor/github.com/authzed/spicedb/internal/developmentmembership/membership.go @@ -0,0 +1,167 @@ +package developmentmembership + +import ( + "fmt" + + core "github.com/authzed/spicedb/pkg/proto/core/v1" + + "github.com/authzed/spicedb/pkg/spiceerrors" + "github.com/authzed/spicedb/pkg/tuple" +) + +// Set represents the set of membership for one or more ONRs, based on expansion +// trees. +type Set struct { + // objectsAndRelations is a map from an ONR (as a string) to the subjects found for that ONR. + objectsAndRelations map[string]FoundSubjects +} + +// SubjectsByONR returns a map from ONR (as a string) to the FoundSubjects for that ONR. +func (ms *Set) SubjectsByONR() map[string]FoundSubjects { + return ms.objectsAndRelations +} + +// NewMembershipSet constructs a new membership set. +// +// NOTE: This is designed solely for the developer API and should *not* be used in any performance +// sensitive code. +func NewMembershipSet() *Set { + return &Set{ + objectsAndRelations: map[string]FoundSubjects{}, + } +} + +// AddExpansion adds the expansion of an ONR to the membership set. Returns false if the ONR was already added. +// +// NOTE: The expansion tree *should* be the fully recursive expansion. +func (ms *Set) AddExpansion(onr tuple.ObjectAndRelation, expansion *core.RelationTupleTreeNode) (FoundSubjects, bool, error) { + onrString := tuple.StringONR(onr) + existing, ok := ms.objectsAndRelations[onrString] + if ok { + return existing, false, nil + } + + tss, err := populateFoundSubjects(onr, expansion) + if err != nil { + return FoundSubjects{}, false, err + } + + fs := tss.ToFoundSubjects() + ms.objectsAndRelations[onrString] = fs + return fs, true, nil +} + +// AccessibleExpansionSubjects returns a TrackingSubjectSet representing the set of accessible subjects in the expansion. +func AccessibleExpansionSubjects(treeNode *core.RelationTupleTreeNode) (*TrackingSubjectSet, error) { + return populateFoundSubjects(tuple.FromCoreObjectAndRelation(treeNode.Expanded), treeNode) +} + +func populateFoundSubjects(rootONR tuple.ObjectAndRelation, treeNode *core.RelationTupleTreeNode) (*TrackingSubjectSet, error) { + resource := rootONR + if treeNode.Expanded != nil { + resource = tuple.FromCoreObjectAndRelation(treeNode.Expanded) + } + + switch typed := treeNode.NodeType.(type) { + case *core.RelationTupleTreeNode_IntermediateNode: + switch typed.IntermediateNode.Operation { + case core.SetOperationUserset_UNION: + toReturn := NewTrackingSubjectSet() + for _, child := range typed.IntermediateNode.ChildNodes { + tss, err := populateFoundSubjects(resource, child) + if err != nil { + return nil, err + } + + err = toReturn.AddFrom(tss) + if err != nil { + return nil, err + } + } + + toReturn.ApplyParentCaveatExpression(treeNode.CaveatExpression) + return toReturn, nil + + case core.SetOperationUserset_INTERSECTION: + if len(typed.IntermediateNode.ChildNodes) == 0 { + return nil, fmt.Errorf("found intersection with no children") + } + + firstChildSet, err := populateFoundSubjects(rootONR, typed.IntermediateNode.ChildNodes[0]) + if err != nil { + return nil, err + } + + toReturn := NewTrackingSubjectSet() + err = toReturn.AddFrom(firstChildSet) + if err != nil { + return nil, err + } + + for _, child := range typed.IntermediateNode.ChildNodes[1:] { + childSet, err := populateFoundSubjects(rootONR, child) + if err != nil { + return nil, err + } + + updated, err := toReturn.Intersect(childSet) + if err != nil { + return nil, err + } + + toReturn = updated + } + + toReturn.ApplyParentCaveatExpression(treeNode.CaveatExpression) + return toReturn, nil + + case core.SetOperationUserset_EXCLUSION: + if len(typed.IntermediateNode.ChildNodes) == 0 { + return nil, fmt.Errorf("found exclusion with no children") + } + + firstChildSet, err := populateFoundSubjects(rootONR, typed.IntermediateNode.ChildNodes[0]) + if err != nil { + return nil, err + } + + toReturn := NewTrackingSubjectSet() + err = toReturn.AddFrom(firstChildSet) + if err != nil { + return nil, err + } + + for _, child := range typed.IntermediateNode.ChildNodes[1:] { + childSet, err := populateFoundSubjects(rootONR, child) + if err != nil { + return nil, err + } + toReturn = toReturn.Exclude(childSet) + } + + toReturn.ApplyParentCaveatExpression(treeNode.CaveatExpression) + return toReturn, nil + + default: + return nil, spiceerrors.MustBugf("unknown expand operation") + } + + case *core.RelationTupleTreeNode_LeafNode: + toReturn := NewTrackingSubjectSet() + for _, subject := range typed.LeafNode.Subjects { + fs := NewFoundSubject(subject) + err := toReturn.Add(fs) + if err != nil { + return nil, err + } + + fs.resources.Add(resource) + } + + toReturn.ApplyParentCaveatExpression(treeNode.CaveatExpression) + return toReturn, nil + + default: + return nil, spiceerrors.MustBugf("unknown TreeNode type") + } +} diff --git a/vendor/github.com/authzed/spicedb/internal/developmentmembership/onrset.go b/vendor/github.com/authzed/spicedb/internal/developmentmembership/onrset.go new file mode 100644 index 0000000..ad7fcfd --- /dev/null +++ b/vendor/github.com/authzed/spicedb/internal/developmentmembership/onrset.go @@ -0,0 +1,87 @@ +package developmentmembership + +import ( + "github.com/ccoveille/go-safecast" + + "github.com/authzed/spicedb/pkg/genutil/mapz" + "github.com/authzed/spicedb/pkg/tuple" +) + +// TODO(jschorr): Replace with the generic set over tuple.ObjectAndRelation + +// ONRSet is a set of ObjectAndRelation's. +type ONRSet struct { + onrs *mapz.Set[tuple.ObjectAndRelation] +} + +// NewONRSet creates a new set. +func NewONRSet(onrs ...tuple.ObjectAndRelation) ONRSet { + created := ONRSet{ + onrs: mapz.NewSet[tuple.ObjectAndRelation](), + } + created.Update(onrs) + return created +} + +// Length returns the size of the set. +func (ons ONRSet) Length() uint64 { + // This is the length of a set so we should never fall out of bounds. + length, _ := safecast.ToUint64(ons.onrs.Len()) + return length +} + +// IsEmpty returns whether the set is empty. +func (ons ONRSet) IsEmpty() bool { + return ons.onrs.IsEmpty() +} + +// Has returns true if the set contains the given ONR. +func (ons ONRSet) Has(onr tuple.ObjectAndRelation) bool { + return ons.onrs.Has(onr) +} + +// Add adds the given ONR to the set. Returns true if the object was not in the set before this +// call and false otherwise. +func (ons ONRSet) Add(onr tuple.ObjectAndRelation) bool { + return ons.onrs.Add(onr) +} + +// Update updates the set by adding the given ONRs to it. +func (ons ONRSet) Update(onrs []tuple.ObjectAndRelation) { + for _, onr := range onrs { + ons.Add(onr) + } +} + +// UpdateFrom updates the set by adding the ONRs found in the other set to it. +func (ons ONRSet) UpdateFrom(otherSet ONRSet) { + if otherSet.onrs == nil { + return + } + ons.onrs.Merge(otherSet.onrs) +} + +// Intersect returns an intersection between this ONR set and the other set provided. +func (ons ONRSet) Intersect(otherSet ONRSet) ONRSet { + return ONRSet{ons.onrs.Intersect(otherSet.onrs)} +} + +// Subtract returns a subtraction from this ONR set of the other set provided. +func (ons ONRSet) Subtract(otherSet ONRSet) ONRSet { + return ONRSet{ons.onrs.Subtract(otherSet.onrs)} +} + +// Union returns a copy of this ONR set with the other set's elements added in. +func (ons ONRSet) Union(otherSet ONRSet) ONRSet { + return ONRSet{ons.onrs.Union(otherSet.onrs)} +} + +// AsSlice returns the ONRs found in the set as a slice. +func (ons ONRSet) AsSlice() []tuple.ObjectAndRelation { + slice := make([]tuple.ObjectAndRelation, 0, ons.Length()) + _ = ons.onrs.ForEach(func(onr tuple.ObjectAndRelation) error { + slice = append(slice, onr) + return nil + }) + return slice +} diff --git a/vendor/github.com/authzed/spicedb/internal/developmentmembership/trackingsubjectset.go b/vendor/github.com/authzed/spicedb/internal/developmentmembership/trackingsubjectset.go new file mode 100644 index 0000000..00f8836 --- /dev/null +++ b/vendor/github.com/authzed/spicedb/internal/developmentmembership/trackingsubjectset.go @@ -0,0 +1,235 @@ +package developmentmembership + +import ( + "github.com/authzed/spicedb/internal/datasets" + core "github.com/authzed/spicedb/pkg/proto/core/v1" + "github.com/authzed/spicedb/pkg/tuple" +) + +// TrackingSubjectSet defines a set that tracks accessible subjects and their associated +// relationships. +// +// NOTE: This is designed solely for the developer API and testing and should *not* be used in any +// performance sensitive code. +type TrackingSubjectSet struct { + setByType map[tuple.RelationReference]datasets.BaseSubjectSet[FoundSubject] +} + +// NewTrackingSubjectSet creates a new TrackingSubjectSet +func NewTrackingSubjectSet() *TrackingSubjectSet { + tss := &TrackingSubjectSet{ + setByType: map[tuple.RelationReference]datasets.BaseSubjectSet[FoundSubject]{}, + } + return tss +} + +// MustNewTrackingSubjectSetWith creates a new TrackingSubjectSet, and adds the specified +// subjects to it. +func MustNewTrackingSubjectSetWith(subjects ...FoundSubject) *TrackingSubjectSet { + tss := NewTrackingSubjectSet() + for _, subject := range subjects { + err := tss.Add(subject) + if err != nil { + panic(err) + } + } + return tss +} + +// AddFrom adds the subjects found in the other set to this set. +func (tss *TrackingSubjectSet) AddFrom(otherSet *TrackingSubjectSet) error { + for key, oss := range otherSet.setByType { + err := tss.getSetForKey(key).UnionWithSet(oss) + if err != nil { + return err + } + } + return nil +} + +// MustAddFrom adds the subjects found in the other set to this set. +func (tss *TrackingSubjectSet) MustAddFrom(otherSet *TrackingSubjectSet) { + err := tss.AddFrom(otherSet) + if err != nil { + panic(err) + } +} + +// RemoveFrom removes any subjects found in the other set from this set. +func (tss *TrackingSubjectSet) RemoveFrom(otherSet *TrackingSubjectSet) { + for key, oss := range otherSet.setByType { + tss.getSetForKey(key).SubtractAll(oss) + } +} + +// MustAdd adds the given subjects to this set. +func (tss *TrackingSubjectSet) MustAdd(subjectsAndResources ...FoundSubject) { + err := tss.Add(subjectsAndResources...) + if err != nil { + panic(err) + } +} + +// Add adds the given subjects to this set. +func (tss *TrackingSubjectSet) Add(subjectsAndResources ...FoundSubject) error { + for _, fs := range subjectsAndResources { + err := tss.getSet(fs).Add(fs) + if err != nil { + return err + } + } + return nil +} + +func (tss *TrackingSubjectSet) getSetForKey(key tuple.RelationReference) datasets.BaseSubjectSet[FoundSubject] { + if existing, ok := tss.setByType[key]; ok { + return existing + } + + created := datasets.NewBaseSubjectSet( + func(subjectID string, caveatExpression *core.CaveatExpression, excludedSubjects []FoundSubject, sources ...FoundSubject) FoundSubject { + fs := NewFoundSubject(&core.DirectSubject{ + Subject: &core.ObjectAndRelation{ + Namespace: key.ObjectType, + ObjectId: subjectID, + Relation: key.Relation, + }, + CaveatExpression: caveatExpression, + }) + fs.excludedSubjects = excludedSubjects + fs.caveatExpression = caveatExpression + for _, source := range sources { + fs.resources.UpdateFrom(source.resources) + } + return fs + }, + ) + tss.setByType[key] = created + return created +} + +func (tss *TrackingSubjectSet) getSet(fs FoundSubject) datasets.BaseSubjectSet[FoundSubject] { + return tss.getSetForKey(fs.subject.RelationReference()) +} + +// Get returns the found subject in the set, if any. +func (tss *TrackingSubjectSet) Get(subject tuple.ObjectAndRelation) (FoundSubject, bool) { + set, ok := tss.setByType[subject.RelationReference()] + if !ok { + return FoundSubject{}, false + } + + return set.Get(subject.ObjectID) +} + +// Contains returns true if the set contains the given subject. +func (tss *TrackingSubjectSet) Contains(subject tuple.ObjectAndRelation) bool { + _, ok := tss.Get(subject) + return ok +} + +// Exclude returns a new set that contains the items in this set minus those in the other set. +func (tss *TrackingSubjectSet) Exclude(otherSet *TrackingSubjectSet) *TrackingSubjectSet { + newSet := NewTrackingSubjectSet() + + for key, bss := range tss.setByType { + cloned := bss.Clone() + if oss, ok := otherSet.setByType[key]; ok { + cloned.SubtractAll(oss) + } + + newSet.setByType[key] = cloned + } + + return newSet +} + +// MustIntersect returns a new set that contains the items in this set *and* the other set. Note that +// if wildcard is found in *both* sets, it will be returned *along* with any concrete subjects found +// on the other side of the intersection. +func (tss *TrackingSubjectSet) MustIntersect(otherSet *TrackingSubjectSet) *TrackingSubjectSet { + updated, err := tss.Intersect(otherSet) + if err != nil { + panic(err) + } + return updated +} + +// Intersect returns a new set that contains the items in this set *and* the other set. Note that +// if wildcard is found in *both* sets, it will be returned *along* with any concrete subjects found +// on the other side of the intersection. +func (tss *TrackingSubjectSet) Intersect(otherSet *TrackingSubjectSet) (*TrackingSubjectSet, error) { + newSet := NewTrackingSubjectSet() + + for key, bss := range tss.setByType { + if oss, ok := otherSet.setByType[key]; ok { + cloned := bss.Clone() + err := cloned.IntersectionDifference(oss) + if err != nil { + return nil, err + } + + newSet.setByType[key] = cloned + } + } + + return newSet, nil +} + +// ApplyParentCaveatExpression applies the given parent caveat expression (if any) to each subject set. +func (tss *TrackingSubjectSet) ApplyParentCaveatExpression(parentCaveatExpr *core.CaveatExpression) { + if parentCaveatExpr == nil { + return + } + + for key, bss := range tss.setByType { + tss.setByType[key] = bss.WithParentCaveatExpression(parentCaveatExpr) + } +} + +// removeExact removes the given subject(s) from the set. If the subject is a wildcard, only +// the exact matching wildcard will be removed. +func (tss *TrackingSubjectSet) removeExact(subjects ...tuple.ObjectAndRelation) { + for _, subject := range subjects { + if set, ok := tss.setByType[subject.RelationReference()]; ok { + set.UnsafeRemoveExact(FoundSubject{ + subject: subject, + }) + } + } +} + +func (tss *TrackingSubjectSet) getSubjects() []string { + var subjects []string + for _, subjectSet := range tss.setByType { + for _, foundSubject := range subjectSet.AsSlice() { + subjects = append(subjects, tuple.StringONR(foundSubject.subject)) + } + } + return subjects +} + +// ToSlice returns a slice of all subjects found in the set. +func (tss *TrackingSubjectSet) ToSlice() []FoundSubject { + subjects := []FoundSubject{} + for _, bss := range tss.setByType { + subjects = append(subjects, bss.AsSlice()...) + } + + return subjects +} + +// ToFoundSubjects returns the set as a FoundSubjects struct. +func (tss *TrackingSubjectSet) ToFoundSubjects() FoundSubjects { + return FoundSubjects{tss} +} + +// IsEmpty returns true if the tracking subject set is empty. +func (tss *TrackingSubjectSet) IsEmpty() bool { + for _, bss := range tss.setByType { + if !bss.IsEmpty() { + return false + } + } + return true +} |