-
Notifications
You must be signed in to change notification settings - Fork 254
/
membershipset.go
200 lines (171 loc) · 5.97 KB
/
membershipset.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
package graph
import (
"github.com/authzed/spicedb/internal/caveats"
core "github.com/authzed/spicedb/pkg/proto/core/v1"
v1 "github.com/authzed/spicedb/pkg/proto/dispatch/v1"
)
var (
caveatOr = caveats.Or
caveatAnd = caveats.And
caveatSub = caveats.Subtract
wrapCaveat = caveats.CaveatAsExpr
)
// 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 CheckResultsMap map[string]*v1.ResourceCheckResult
// NewMembershipSet constructs a new helper set for tracking the membership found for a dispatched
// check request.
func NewMembershipSet() *MembershipSet {
return &MembershipSet{
hasDeterminedMember: false,
membersByID: map[string]*core.CaveatExpression{},
}
}
func membershipSetFromMap(mp map[string]*core.CaveatExpression) *MembershipSet {
ms := NewMembershipSet()
for resourceID, result := range mp {
ms.addMember(resourceID, result)
}
return ms
}
// 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.
type MembershipSet struct {
membersByID map[string]*core.CaveatExpression
hasDeterminedMember bool
}
// AddDirectMember adds a resource ID that was *directly* found for the dispatched check, with
// optional caveat found on the relationship.
func (ms *MembershipSet) AddDirectMember(resourceID string, caveat *core.ContextualizedCaveat) {
ms.addMember(resourceID, wrapCaveat(caveat))
}
// 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 (ms *MembershipSet) AddMemberViaRelationship(
resourceID string,
resourceCaveatExpression *core.CaveatExpression,
parentRelationship *core.RelationTuple,
) {
intersection := caveatAnd(wrapCaveat(parentRelationship.Caveat), resourceCaveatExpression)
ms.addMember(resourceID, intersection)
}
func (ms *MembershipSet) addMember(resourceID string, caveatExpr *core.CaveatExpression) {
existing, ok := ms.membersByID[resourceID]
if !ok {
ms.hasDeterminedMember = ms.hasDeterminedMember || caveatExpr == nil
ms.membersByID[resourceID] = caveatExpr
return
}
// If a determined membership result has already been found (i.e. there is no caveat),
// then nothing more to do.
if existing == nil {
return
}
// If the new caveat expression is nil, then we are adding a determined result.
if caveatExpr == nil {
ms.hasDeterminedMember = true
ms.membersByID[resourceID] = nil
return
}
// Otherwise, the caveats get unioned together.
ms.membersByID[resourceID] = caveatOr(existing, caveatExpr)
}
// UnionWith combines the results found in the given map with the members of this set.
// The changes are made in-place.
func (ms *MembershipSet) UnionWith(resultsMap CheckResultsMap) {
for resourceID, details := range resultsMap {
ms.addMember(resourceID, details.Expression)
}
}
// IntersectWith intersects the results found in the given map with the members of this set.
// The changes are made in-place.
func (ms *MembershipSet) IntersectWith(resultsMap CheckResultsMap) {
for resourceID := range ms.membersByID {
if _, ok := resultsMap[resourceID]; !ok {
delete(ms.membersByID, resourceID)
}
}
ms.hasDeterminedMember = false
for resourceID, details := range resultsMap {
existing, ok := ms.membersByID[resourceID]
if !ok {
continue
}
if existing == nil && details.Expression == nil {
ms.hasDeterminedMember = true
continue
}
ms.membersByID[resourceID] = caveatAnd(existing, details.Expression)
}
}
// Subtract subtracts the results found in the given map with the members of this set.
// The changes are made in-place.
func (ms *MembershipSet) Subtract(resultsMap CheckResultsMap) {
ms.hasDeterminedMember = false
for resourceID, expression := range ms.membersByID {
if details, ok := resultsMap[resourceID]; ok {
// If the incoming member has no caveat, then this removal is absolute.
if details.Expression == nil {
delete(ms.membersByID, resourceID)
continue
}
// Otherwise, the caveat expression gets combined with an intersection of the inversion
// of the expression.
ms.membersByID[resourceID] = caveatSub(expression, details.Expression)
} else {
if expression == nil {
ms.hasDeterminedMember = true
}
}
}
}
// HasConcreteResourceID returns whether the resourceID was found in the set
// and has no caveat attached.
func (ms *MembershipSet) HasConcreteResourceID(resourceID string) bool {
if ms == nil {
return false
}
found, ok := ms.membersByID[resourceID]
return ok && found == nil
}
// Size returns the number of elements in the membership set.
func (ms *MembershipSet) Size() int {
if ms == nil {
return 0
}
return len(ms.membersByID)
}
// IsEmpty returns true if the set is empty.
func (ms *MembershipSet) IsEmpty() bool {
if ms == nil {
return true
}
return len(ms.membersByID) == 0
}
// HasDeterminedMember returns whether there exists at least one non-caveated member of the set.
func (ms *MembershipSet) HasDeterminedMember() bool {
if ms == nil {
return false
}
return ms.hasDeterminedMember
}
// AsCheckResultsMap converts the membership set back into a CheckResultsMap for placement into
// a DispatchCheckResult.
func (ms *MembershipSet) AsCheckResultsMap() CheckResultsMap {
resultsMap := make(CheckResultsMap, len(ms.membersByID))
for resourceID, caveat := range ms.membersByID {
membership := v1.ResourceCheckResult_MEMBER
if caveat != nil {
membership = v1.ResourceCheckResult_CAVEATED_MEMBER
}
resultsMap[resourceID] = &v1.ResourceCheckResult{
Membership: membership,
Expression: caveat,
}
}
return resultsMap
}