blob: e3e4453b64f1ec5a6af9876c71977eee258625d5 [file] [log] [blame]
sslobodrd046be82019-01-16 10:02:22 -05001/*
2Copyright 2015 The Kubernetes Authors.
3
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15*/
16
17package fields
18
19import (
20 "bytes"
21 "fmt"
22 "sort"
23 "strings"
24
25 "k8s.io/apimachinery/pkg/selection"
26)
27
28// Selector represents a field selector.
29type Selector interface {
30 // Matches returns true if this selector matches the given set of fields.
31 Matches(Fields) bool
32
33 // Empty returns true if this selector does not restrict the selection space.
34 Empty() bool
35
36 // RequiresExactMatch allows a caller to introspect whether a given selector
37 // requires a single specific field to be set, and if so returns the value it
38 // requires.
39 RequiresExactMatch(field string) (value string, found bool)
40
41 // Transform returns a new copy of the selector after TransformFunc has been
42 // applied to the entire selector, or an error if fn returns an error.
43 // If for a given requirement both field and value are transformed to empty
44 // string, the requirement is skipped.
45 Transform(fn TransformFunc) (Selector, error)
46
47 // Requirements converts this interface to Requirements to expose
48 // more detailed selection information.
49 Requirements() Requirements
50
51 // String returns a human readable string that represents this selector.
52 String() string
53
54 // Make a deep copy of the selector.
55 DeepCopySelector() Selector
56}
57
58type nothingSelector struct{}
59
60func (n nothingSelector) Matches(_ Fields) bool { return false }
61func (n nothingSelector) Empty() bool { return false }
62func (n nothingSelector) String() string { return "" }
63func (n nothingSelector) Requirements() Requirements { return nil }
64func (n nothingSelector) DeepCopySelector() Selector { return n }
65func (n nothingSelector) RequiresExactMatch(field string) (value string, found bool) { return "", false }
66func (n nothingSelector) Transform(fn TransformFunc) (Selector, error) { return n, nil }
67
68// Nothing returns a selector that matches no fields
69func Nothing() Selector {
70 return nothingSelector{}
71}
72
73// Everything returns a selector that matches all fields.
74func Everything() Selector {
75 return andTerm{}
76}
77
78type hasTerm struct {
79 field, value string
80}
81
82func (t *hasTerm) Matches(ls Fields) bool {
83 return ls.Get(t.field) == t.value
84}
85
86func (t *hasTerm) Empty() bool {
87 return false
88}
89
90func (t *hasTerm) RequiresExactMatch(field string) (value string, found bool) {
91 if t.field == field {
92 return t.value, true
93 }
94 return "", false
95}
96
97func (t *hasTerm) Transform(fn TransformFunc) (Selector, error) {
98 field, value, err := fn(t.field, t.value)
99 if err != nil {
100 return nil, err
101 }
102 if len(field) == 0 && len(value) == 0 {
103 return Everything(), nil
104 }
105 return &hasTerm{field, value}, nil
106}
107
108func (t *hasTerm) Requirements() Requirements {
109 return []Requirement{{
110 Field: t.field,
111 Operator: selection.Equals,
112 Value: t.value,
113 }}
114}
115
116func (t *hasTerm) String() string {
117 return fmt.Sprintf("%v=%v", t.field, EscapeValue(t.value))
118}
119
120func (t *hasTerm) DeepCopySelector() Selector {
121 if t == nil {
122 return nil
123 }
124 out := new(hasTerm)
125 *out = *t
126 return out
127}
128
129type notHasTerm struct {
130 field, value string
131}
132
133func (t *notHasTerm) Matches(ls Fields) bool {
134 return ls.Get(t.field) != t.value
135}
136
137func (t *notHasTerm) Empty() bool {
138 return false
139}
140
141func (t *notHasTerm) RequiresExactMatch(field string) (value string, found bool) {
142 return "", false
143}
144
145func (t *notHasTerm) Transform(fn TransformFunc) (Selector, error) {
146 field, value, err := fn(t.field, t.value)
147 if err != nil {
148 return nil, err
149 }
150 if len(field) == 0 && len(value) == 0 {
151 return Everything(), nil
152 }
153 return &notHasTerm{field, value}, nil
154}
155
156func (t *notHasTerm) Requirements() Requirements {
157 return []Requirement{{
158 Field: t.field,
159 Operator: selection.NotEquals,
160 Value: t.value,
161 }}
162}
163
164func (t *notHasTerm) String() string {
165 return fmt.Sprintf("%v!=%v", t.field, EscapeValue(t.value))
166}
167
168func (t *notHasTerm) DeepCopySelector() Selector {
169 if t == nil {
170 return nil
171 }
172 out := new(notHasTerm)
173 *out = *t
174 return out
175}
176
177type andTerm []Selector
178
179func (t andTerm) Matches(ls Fields) bool {
180 for _, q := range t {
181 if !q.Matches(ls) {
182 return false
183 }
184 }
185 return true
186}
187
188func (t andTerm) Empty() bool {
189 if t == nil {
190 return true
191 }
192 if len([]Selector(t)) == 0 {
193 return true
194 }
195 for i := range t {
196 if !t[i].Empty() {
197 return false
198 }
199 }
200 return true
201}
202
203func (t andTerm) RequiresExactMatch(field string) (string, bool) {
204 if t == nil || len([]Selector(t)) == 0 {
205 return "", false
206 }
207 for i := range t {
208 if value, found := t[i].RequiresExactMatch(field); found {
209 return value, found
210 }
211 }
212 return "", false
213}
214
215func (t andTerm) Transform(fn TransformFunc) (Selector, error) {
216 next := make([]Selector, 0, len([]Selector(t)))
217 for _, s := range []Selector(t) {
218 n, err := s.Transform(fn)
219 if err != nil {
220 return nil, err
221 }
222 if !n.Empty() {
223 next = append(next, n)
224 }
225 }
226 return andTerm(next), nil
227}
228
229func (t andTerm) Requirements() Requirements {
230 reqs := make([]Requirement, 0, len(t))
231 for _, s := range []Selector(t) {
232 rs := s.Requirements()
233 reqs = append(reqs, rs...)
234 }
235 return reqs
236}
237
238func (t andTerm) String() string {
239 var terms []string
240 for _, q := range t {
241 terms = append(terms, q.String())
242 }
243 return strings.Join(terms, ",")
244}
245
246func (t andTerm) DeepCopySelector() Selector {
247 if t == nil {
248 return nil
249 }
250 out := make([]Selector, len(t))
251 for i := range t {
252 out[i] = t[i].DeepCopySelector()
253 }
254 return andTerm(out)
255}
256
257// SelectorFromSet returns a Selector which will match exactly the given Set. A
258// nil Set is considered equivalent to Everything().
259func SelectorFromSet(ls Set) Selector {
260 if ls == nil {
261 return Everything()
262 }
263 items := make([]Selector, 0, len(ls))
264 for field, value := range ls {
265 items = append(items, &hasTerm{field: field, value: value})
266 }
267 if len(items) == 1 {
268 return items[0]
269 }
270 return andTerm(items)
271}
272
273// valueEscaper prefixes \,= characters with a backslash
274var valueEscaper = strings.NewReplacer(
275 // escape \ characters
276 `\`, `\\`,
277 // then escape , and = characters to allow unambiguous parsing of the value in a fieldSelector
278 `,`, `\,`,
279 `=`, `\=`,
280)
281
282// EscapeValue escapes an arbitrary literal string for use as a fieldSelector value
283func EscapeValue(s string) string {
284 return valueEscaper.Replace(s)
285}
286
287// InvalidEscapeSequence indicates an error occurred unescaping a field selector
288type InvalidEscapeSequence struct {
289 sequence string
290}
291
292func (i InvalidEscapeSequence) Error() string {
293 return fmt.Sprintf("invalid field selector: invalid escape sequence: %s", i.sequence)
294}
295
296// UnescapedRune indicates an error occurred unescaping a field selector
297type UnescapedRune struct {
298 r rune
299}
300
301func (i UnescapedRune) Error() string {
302 return fmt.Sprintf("invalid field selector: unescaped character in value: %v", i.r)
303}
304
305// UnescapeValue unescapes a fieldSelector value and returns the original literal value.
306// May return the original string if it contains no escaped or special characters.
307func UnescapeValue(s string) (string, error) {
308 // if there's no escaping or special characters, just return to avoid allocation
309 if !strings.ContainsAny(s, `\,=`) {
310 return s, nil
311 }
312
313 v := bytes.NewBuffer(make([]byte, 0, len(s)))
314 inSlash := false
315 for _, c := range s {
316 if inSlash {
317 switch c {
318 case '\\', ',', '=':
319 // omit the \ for recognized escape sequences
320 v.WriteRune(c)
321 default:
322 // error on unrecognized escape sequences
323 return "", InvalidEscapeSequence{sequence: string([]rune{'\\', c})}
324 }
325 inSlash = false
326 continue
327 }
328
329 switch c {
330 case '\\':
331 inSlash = true
332 case ',', '=':
333 // unescaped , and = characters are not allowed in field selector values
334 return "", UnescapedRune{r: c}
335 default:
336 v.WriteRune(c)
337 }
338 }
339
340 // Ending with a single backslash is an invalid sequence
341 if inSlash {
342 return "", InvalidEscapeSequence{sequence: "\\"}
343 }
344
345 return v.String(), nil
346}
347
348// ParseSelectorOrDie takes a string representing a selector and returns an
349// object suitable for matching, or panic when an error occur.
350func ParseSelectorOrDie(s string) Selector {
351 selector, err := ParseSelector(s)
352 if err != nil {
353 panic(err)
354 }
355 return selector
356}
357
358// ParseSelector takes a string representing a selector and returns an
359// object suitable for matching, or an error.
360func ParseSelector(selector string) (Selector, error) {
361 return parseSelector(selector,
362 func(lhs, rhs string) (newLhs, newRhs string, err error) {
363 return lhs, rhs, nil
364 })
365}
366
367// ParseAndTransformSelector parses the selector and runs them through the given TransformFunc.
368func ParseAndTransformSelector(selector string, fn TransformFunc) (Selector, error) {
369 return parseSelector(selector, fn)
370}
371
372// TransformFunc transforms selectors.
373type TransformFunc func(field, value string) (newField, newValue string, err error)
374
375// splitTerms returns the comma-separated terms contained in the given fieldSelector.
376// Backslash-escaped commas are treated as data instead of delimiters, and are included in the returned terms, with the leading backslash preserved.
377func splitTerms(fieldSelector string) []string {
378 if len(fieldSelector) == 0 {
379 return nil
380 }
381
382 terms := make([]string, 0, 1)
383 startIndex := 0
384 inSlash := false
385 for i, c := range fieldSelector {
386 switch {
387 case inSlash:
388 inSlash = false
389 case c == '\\':
390 inSlash = true
391 case c == ',':
392 terms = append(terms, fieldSelector[startIndex:i])
393 startIndex = i + 1
394 }
395 }
396
397 terms = append(terms, fieldSelector[startIndex:])
398
399 return terms
400}
401
402const (
403 notEqualOperator = "!="
404 doubleEqualOperator = "=="
405 equalOperator = "="
406)
407
408// termOperators holds the recognized operators supported in fieldSelectors.
409// doubleEqualOperator and equal are equivalent, but doubleEqualOperator is checked first
410// to avoid leaving a leading = character on the rhs value.
411var termOperators = []string{notEqualOperator, doubleEqualOperator, equalOperator}
412
413// splitTerm returns the lhs, operator, and rhs parsed from the given term, along with an indicator of whether the parse was successful.
414// no escaping of special characters is supported in the lhs value, so the first occurrence of a recognized operator is used as the split point.
415// the literal rhs is returned, and the caller is responsible for applying any desired unescaping.
416func splitTerm(term string) (lhs, op, rhs string, ok bool) {
417 for i := range term {
418 remaining := term[i:]
419 for _, op := range termOperators {
420 if strings.HasPrefix(remaining, op) {
421 return term[0:i], op, term[i+len(op):], true
422 }
423 }
424 }
425 return "", "", "", false
426}
427
428func parseSelector(selector string, fn TransformFunc) (Selector, error) {
429 parts := splitTerms(selector)
430 sort.StringSlice(parts).Sort()
431 var items []Selector
432 for _, part := range parts {
433 if part == "" {
434 continue
435 }
436 lhs, op, rhs, ok := splitTerm(part)
437 if !ok {
438 return nil, fmt.Errorf("invalid selector: '%s'; can't understand '%s'", selector, part)
439 }
440 unescapedRHS, err := UnescapeValue(rhs)
441 if err != nil {
442 return nil, err
443 }
444 switch op {
445 case notEqualOperator:
446 items = append(items, &notHasTerm{field: lhs, value: unescapedRHS})
447 case doubleEqualOperator:
448 items = append(items, &hasTerm{field: lhs, value: unescapedRHS})
449 case equalOperator:
450 items = append(items, &hasTerm{field: lhs, value: unescapedRHS})
451 default:
452 return nil, fmt.Errorf("invalid selector: '%s'; can't understand '%s'", selector, part)
453 }
454 }
455 if len(items) == 1 {
456 return items[0].Transform(fn)
457 }
458 return andTerm(items).Transform(fn)
459}
460
461// OneTermEqualSelector returns an object that matches objects where one field/field equals one value.
462// Cannot return an error.
463func OneTermEqualSelector(k, v string) Selector {
464 return &hasTerm{field: k, value: v}
465}
466
467// OneTermNotEqualSelector returns an object that matches objects where one field/field does not equal one value.
468// Cannot return an error.
469func OneTermNotEqualSelector(k, v string) Selector {
470 return &notHasTerm{field: k, value: v}
471}
472
473// AndSelectors creates a selector that is the logical AND of all the given selectors
474func AndSelectors(selectors ...Selector) Selector {
475 return andTerm(selectors)
476}