forked from google/cel-go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
attribute_patterns.go
397 lines (364 loc) · 14.8 KB
/
attribute_patterns.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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
// Copyright 2020 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package interpreter
import (
"fmt"
"github.com/authzed/cel-go/common/containers"
"github.com/authzed/cel-go/common/types"
"github.com/authzed/cel-go/common/types/ref"
)
// AttributePattern represents a top-level variable with an optional set of qualifier patterns.
//
// When using a CEL expression within a container, e.g. a package or namespace, the variable name
// in the pattern must match the qualified name produced during the variable namespace resolution.
// For example, if variable `c` appears in an expression whose container is `a.b`, the variable
// name supplied to the pattern must be `a.b.c`
//
// The qualifier patterns for attribute matching must be one of the following:
//
// - valid map key type: string, int, uint, bool
// - wildcard (*)
//
// Examples:
//
// 1. ns.myvar["complex-value"]
// 2. ns.myvar["complex-value"][0]
// 3. ns.myvar["complex-value"].*.name
//
// The first example is simple: match an attribute where the variable is 'ns.myvar' with a
// field access on 'complex-value'. The second example expands the match to indicate that only
// a specific index `0` should match. And lastly, the third example matches any indexed access
// that later selects the 'name' field.
type AttributePattern struct {
variable string
qualifierPatterns []*AttributeQualifierPattern
}
// NewAttributePattern produces a new mutable AttributePattern based on a variable name.
func NewAttributePattern(variable string) *AttributePattern {
return &AttributePattern{
variable: variable,
qualifierPatterns: []*AttributeQualifierPattern{},
}
}
// QualString adds a string qualifier pattern to the AttributePattern. The string may be a valid
// identifier, or string map key including empty string.
func (apat *AttributePattern) QualString(pattern string) *AttributePattern {
apat.qualifierPatterns = append(apat.qualifierPatterns,
&AttributeQualifierPattern{value: pattern})
return apat
}
// QualInt adds an int qualifier pattern to the AttributePattern. The index may be either a map or
// list index.
func (apat *AttributePattern) QualInt(pattern int64) *AttributePattern {
apat.qualifierPatterns = append(apat.qualifierPatterns,
&AttributeQualifierPattern{value: pattern})
return apat
}
// QualUint adds an uint qualifier pattern for a map index operation to the AttributePattern.
func (apat *AttributePattern) QualUint(pattern uint64) *AttributePattern {
apat.qualifierPatterns = append(apat.qualifierPatterns,
&AttributeQualifierPattern{value: pattern})
return apat
}
// QualBool adds a bool qualifier pattern for a map index operation to the AttributePattern.
func (apat *AttributePattern) QualBool(pattern bool) *AttributePattern {
apat.qualifierPatterns = append(apat.qualifierPatterns,
&AttributeQualifierPattern{value: pattern})
return apat
}
// Wildcard adds a special sentinel qualifier pattern that will match any single qualifier.
func (apat *AttributePattern) Wildcard() *AttributePattern {
apat.qualifierPatterns = append(apat.qualifierPatterns,
&AttributeQualifierPattern{wildcard: true})
return apat
}
// VariableMatches returns true if the fully qualified variable matches the AttributePattern
// fully qualified variable name.
func (apat *AttributePattern) VariableMatches(variable string) bool {
return apat.variable == variable
}
// QualifierPatterns returns the set of AttributeQualifierPattern values on the AttributePattern.
func (apat *AttributePattern) QualifierPatterns() []*AttributeQualifierPattern {
return apat.qualifierPatterns
}
// AttributeQualifierPattern holds a wildcard or valued qualifier pattern.
type AttributeQualifierPattern struct {
wildcard bool
value any
}
// Matches returns true if the qualifier pattern is a wildcard, or the Qualifier implements the
// qualifierValueEquator interface and its IsValueEqualTo returns true for the qualifier pattern.
func (qpat *AttributeQualifierPattern) Matches(q Qualifier) bool {
if qpat.wildcard {
return true
}
qve, ok := q.(qualifierValueEquator)
return ok && qve.QualifierValueEquals(qpat.value)
}
// qualifierValueEquator defines an interface for determining if an input value, of valid map key
// type, is equal to the value held in the Qualifier. This interface is used by the
// AttributeQualifierPattern to determine pattern matches for non-wildcard qualifier patterns.
//
// Note: Attribute values are also Qualifier values; however, Attributes are resolved before
// qualification happens. This is an implementation detail, but one relevant to why the Attribute
// types do not surface in the list of implementations.
//
// See: partialAttributeFactory.matchesUnknownPatterns for more details on how this interface is
// used.
type qualifierValueEquator interface {
// QualifierValueEquals returns true if the input value is equal to the value held in the
// Qualifier.
QualifierValueEquals(value any) bool
}
// QualifierValueEquals implementation for boolean qualifiers.
func (q *boolQualifier) QualifierValueEquals(value any) bool {
bval, ok := value.(bool)
return ok && q.value == bval
}
// QualifierValueEquals implementation for field qualifiers.
func (q *fieldQualifier) QualifierValueEquals(value any) bool {
sval, ok := value.(string)
return ok && q.Name == sval
}
// QualifierValueEquals implementation for string qualifiers.
func (q *stringQualifier) QualifierValueEquals(value any) bool {
sval, ok := value.(string)
return ok && q.value == sval
}
// QualifierValueEquals implementation for int qualifiers.
func (q *intQualifier) QualifierValueEquals(value any) bool {
return numericValueEquals(value, q.celValue)
}
// QualifierValueEquals implementation for uint qualifiers.
func (q *uintQualifier) QualifierValueEquals(value any) bool {
return numericValueEquals(value, q.celValue)
}
// QualifierValueEquals implementation for double qualifiers.
func (q *doubleQualifier) QualifierValueEquals(value any) bool {
return numericValueEquals(value, q.celValue)
}
// numericValueEquals uses CEL equality to determine whether two number values are
func numericValueEquals(value any, celValue ref.Val) bool {
val := types.DefaultTypeAdapter.NativeToValue(value)
return celValue.Equal(val) == types.True
}
// NewPartialAttributeFactory returns an AttributeFactory implementation capable of performing
// AttributePattern matches with PartialActivation inputs.
func NewPartialAttributeFactory(container *containers.Container, adapter types.Adapter, provider types.Provider, opts ...AttrFactoryOption) AttributeFactory {
fac := NewAttributeFactory(container, adapter, provider, opts...)
return &partialAttributeFactory{
AttributeFactory: fac,
container: container,
adapter: adapter,
provider: provider,
}
}
type partialAttributeFactory struct {
AttributeFactory
container *containers.Container
adapter types.Adapter
provider types.Provider
}
// AbsoluteAttribute implementation of the AttributeFactory interface which wraps the
// NamespacedAttribute resolution in an internal attributeMatcher object to dynamically match
// unknown patterns from PartialActivation inputs if given.
func (fac *partialAttributeFactory) AbsoluteAttribute(id int64, names ...string) NamespacedAttribute {
attr := fac.AttributeFactory.AbsoluteAttribute(id, names...)
return &attributeMatcher{fac: fac, NamespacedAttribute: attr}
}
// MaybeAttribute implementation of the AttributeFactory interface which ensure that the set of
// 'maybe' NamespacedAttribute values are produced using the partialAttributeFactory rather than
// the base AttributeFactory implementation.
func (fac *partialAttributeFactory) MaybeAttribute(id int64, name string) Attribute {
return &maybeAttribute{
id: id,
attrs: []NamespacedAttribute{
fac.AbsoluteAttribute(id, fac.container.ResolveCandidateNames(name)...),
},
adapter: fac.adapter,
provider: fac.provider,
fac: fac,
}
}
// matchesUnknownPatterns returns true if the variable names and qualifiers for a given
// Attribute value match any of the ActivationPattern objects in the set of unknown activation
// patterns on the given PartialActivation.
//
// For example, in the expression `a.b`, the Attribute is composed of variable `a`, with string
// qualifier `b`. When a PartialActivation is supplied, it indicates that some or all of the data
// provided in the input is unknown by specifying unknown AttributePatterns. An AttributePattern
// that refers to variable `a` with a string qualifier of `c` will not match `a.b`; however, any
// of the following patterns will match Attribute `a.b`:
//
// - `AttributePattern("a")`
// - `AttributePattern("a").Wildcard()`
// - `AttributePattern("a").QualString("b")`
// - `AttributePattern("a").QualString("b").QualInt(0)`
//
// Any AttributePattern which overlaps an Attribute or vice-versa will produce an Unknown result
// for the last pattern matched variable or qualifier in the Attribute. In the first matching
// example, the expression id representing variable `a` would be listed in the Unknown result,
// whereas in the other pattern examples, the qualifier `b` would be returned as the Unknown.
func (fac *partialAttributeFactory) matchesUnknownPatterns(
vars PartialActivation,
attrID int64,
variableNames []string,
qualifiers []Qualifier) (*types.Unknown, error) {
patterns := vars.UnknownAttributePatterns()
candidateIndices := map[int]struct{}{}
for _, variable := range variableNames {
for i, pat := range patterns {
if pat.VariableMatches(variable) {
if len(qualifiers) == 0 {
return types.NewUnknown(attrID, types.NewAttributeTrail(variable)), nil
}
candidateIndices[i] = struct{}{}
}
}
}
// Determine whether to return early if there are no candidate unknown patterns.
if len(candidateIndices) == 0 {
return nil, nil
}
// Resolve the attribute qualifiers into a static set. This prevents more dynamic
// Attribute resolutions than necessary when there are multiple unknown patterns
// that traverse the same Attribute-based qualifier field.
newQuals := make([]Qualifier, len(qualifiers))
for i, qual := range qualifiers {
attr, isAttr := qual.(Attribute)
if isAttr {
val, err := attr.Resolve(vars)
if err != nil {
return nil, err
}
// If this resolution behavior ever changes, new implementations of the
// qualifierValueEquator may be required to handle proper resolution.
qual, err = fac.NewQualifier(nil, qual.ID(), val, attr.IsOptional())
if err != nil {
return nil, err
}
}
newQuals[i] = qual
}
// Determine whether any of the unknown patterns match.
for patIdx := range candidateIndices {
pat := patterns[patIdx]
isUnk := true
matchExprID := attrID
qualPats := pat.QualifierPatterns()
for i, qual := range newQuals {
if i >= len(qualPats) {
break
}
matchExprID = qual.ID()
qualPat := qualPats[i]
// Note, the AttributeQualifierPattern relies on the input Qualifier not being an
// Attribute, since there is no way to resolve the Attribute with the information
// provided to the Matches call.
if !qualPat.Matches(qual) {
isUnk = false
break
}
}
if isUnk {
attr := types.NewAttributeTrail(pat.variable)
for i := 0; i < len(qualPats) && i < len(newQuals); i++ {
if qual, ok := newQuals[i].(ConstantQualifier); ok {
switch v := qual.Value().Value().(type) {
case bool:
types.QualifyAttribute[bool](attr, v)
case float64:
types.QualifyAttribute[int64](attr, int64(v))
case int64:
types.QualifyAttribute[int64](attr, v)
case string:
types.QualifyAttribute[string](attr, v)
case uint64:
types.QualifyAttribute[uint64](attr, v)
default:
types.QualifyAttribute[string](attr, fmt.Sprintf("%v", v))
}
} else {
types.QualifyAttribute[string](attr, "*")
}
}
return types.NewUnknown(matchExprID, attr), nil
}
}
return nil, nil
}
// attributeMatcher embeds the NamespacedAttribute interface which allows it to participate in
// AttributePattern matching against Attribute values without having to modify the code paths that
// identify Attributes in expressions.
type attributeMatcher struct {
NamespacedAttribute
qualifiers []Qualifier
fac *partialAttributeFactory
}
// AddQualifier implements the Attribute interface method.
func (m *attributeMatcher) AddQualifier(qual Qualifier) (Attribute, error) {
// Add the qualifier to the embedded NamespacedAttribute. If the input to the Resolve
// method is not a PartialActivation, or does not match an unknown attribute pattern, the
// Resolve method is directly invoked on the underlying NamespacedAttribute.
_, err := m.NamespacedAttribute.AddQualifier(qual)
if err != nil {
return nil, err
}
// The attributeMatcher overloads TryResolve and will attempt to match unknown patterns against
// the variable name and qualifier set contained within the Attribute. These values are not
// directly inspectable on the top-level NamespacedAttribute interface and so are tracked within
// the attributeMatcher.
m.qualifiers = append(m.qualifiers, qual)
return m, nil
}
// Resolve is an implementation of the NamespacedAttribute interface method which tests
// for matching unknown attribute patterns and returns types.Unknown if present. Otherwise,
// the standard Resolve logic applies.
func (m *attributeMatcher) Resolve(vars Activation) (any, error) {
id := m.NamespacedAttribute.ID()
// Bug in how partial activation is resolved, should search parents as well.
partial, isPartial := toPartialActivation(vars)
if isPartial {
unk, err := m.fac.matchesUnknownPatterns(
partial,
id,
m.CandidateVariableNames(),
m.qualifiers)
if err != nil {
return nil, err
}
if unk != nil {
return unk, nil
}
}
return m.NamespacedAttribute.Resolve(vars)
}
// Qualify is an implementation of the Qualifier interface method.
func (m *attributeMatcher) Qualify(vars Activation, obj any) (any, error) {
return attrQualify(m.fac, vars, obj, m)
}
// QualifyIfPresent is an implementation of the Qualifier interface method.
func (m *attributeMatcher) QualifyIfPresent(vars Activation, obj any, presenceOnly bool) (any, bool, error) {
return attrQualifyIfPresent(m.fac, vars, obj, m, presenceOnly)
}
func toPartialActivation(vars Activation) (PartialActivation, bool) {
pv, ok := vars.(PartialActivation)
if ok {
return pv, true
}
if vars.Parent() != nil {
return toPartialActivation(vars.Parent())
}
return nil, false
}