cmd/bpa-operator/vendor/k8s.io/apimachinery/pkg/fields/selector.go

   1 /*
   2 Copyright 2015 The Kubernetes Authors.
   3
   4 Licensed under the Apache License, Version 2.0 (the "License");
   5 you may not use this file except in compliance with the License.
   6 You may obtain a copy of the License at
   7
   8     http://www.apache.org/licenses/LICENSE-2.0
   9
  10 Unless required by applicable law or agreed to in writing, software
  11 distributed under the License is distributed on an "AS IS" BASIS,
  12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 See the License for the specific language governing permissions and
  14 limitations under the License.
  15 */
  16
  17 package fields
  18
  19 import (
  20         "bytes"
  21         "fmt"
  22         "sort"
  23         "strings"
  24
  25         "k8s.io/apimachinery/pkg/selection"
  26 )
  27
  28 // Selector represents a field selector.
  29 type 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
  58 type nothingSelector struct{}
  59
  60 func (n nothingSelector) Matches(_ Fields) bool                                      { return false }
  61 func (n nothingSelector) Empty() bool                                                { return false }
  62 func (n nothingSelector) String() string                                             { return "" }
  63 func (n nothingSelector) Requirements() Requirements                                 { return nil }
  64 func (n nothingSelector) DeepCopySelector() Selector                                 { return n }
  65 func (n nothingSelector) RequiresExactMatch(field string) (value string, found bool) { return "", false }
  66 func (n nothingSelector) Transform(fn TransformFunc) (Selector, error)               { return n, nil }
  67
  68 // Nothing returns a selector that matches no fields
  69 func Nothing() Selector {
  70         return nothingSelector{}
  71 }
  72
  73 // Everything returns a selector that matches all fields.
  74 func Everything() Selector {
  75         return andTerm{}
  76 }
  77
  78 type hasTerm struct {
  79         field, value string
  80 }
  81
  82 func (t *hasTerm) Matches(ls Fields) bool {
  83         return ls.Get(t.field) == t.value
  84 }
  85
  86 func (t *hasTerm) Empty() bool {
  87         return false
  88 }
  89
  90 func (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
  97 func (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
 108 func (t *hasTerm) Requirements() Requirements {
 109         return []Requirement{{
 110                 Field:    t.field,
 111                 Operator: selection.Equals,
 112                 Value:    t.value,
 113         }}
 114 }
 115
 116 func (t *hasTerm) String() string {
 117         return fmt.Sprintf("%v=%v", t.field, EscapeValue(t.value))
 118 }
 119
 120 func (t *hasTerm) DeepCopySelector() Selector {
 121         if t == nil {
 122                 return nil
 123         }
 124         out := new(hasTerm)
 125         *out = *t
 126         return out
 127 }
 128
 129 type notHasTerm struct {
 130         field, value string
 131 }
 132
 133 func (t *notHasTerm) Matches(ls Fields) bool {
 134         return ls.Get(t.field) != t.value
 135 }
 136
 137 func (t *notHasTerm) Empty() bool {
 138         return false
 139 }
 140
 141 func (t *notHasTerm) RequiresExactMatch(field string) (value string, found bool) {
 142         return "", false
 143 }
 144
 145 func (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
 156 func (t *notHasTerm) Requirements() Requirements {
 157         return []Requirement{{
 158                 Field:    t.field,
 159                 Operator: selection.NotEquals,
 160                 Value:    t.value,
 161         }}
 162 }
 163
 164 func (t *notHasTerm) String() string {
 165         return fmt.Sprintf("%v!=%v", t.field, EscapeValue(t.value))
 166 }
 167
 168 func (t *notHasTerm) DeepCopySelector() Selector {
 169         if t == nil {
 170                 return nil
 171         }
 172         out := new(notHasTerm)
 173         *out = *t
 174         return out
 175 }
 176
 177 type andTerm []Selector
 178
 179 func (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
 188 func (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
 203 func (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
 215 func (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
 229 func (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
 238 func (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
 246 func (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().
 259 func 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
 274 var 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
 283 func EscapeValue(s string) string {
 284         return valueEscaper.Replace(s)
 285 }
 286
 287 // InvalidEscapeSequence indicates an error occurred unescaping a field selector
 288 type InvalidEscapeSequence struct {
 289         sequence string
 290 }
 291
 292 func (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
 297 type UnescapedRune struct {
 298         r rune
 299 }
 300
 301 func (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.
 307 func 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.
 350 func 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.
 360 func 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.
 368 func ParseAndTransformSelector(selector string, fn TransformFunc) (Selector, error) {
 369         return parseSelector(selector, fn)
 370 }
 371
 372 // TransformFunc transforms selectors.
 373 type 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.
 377 func 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
 402 const (
 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.
 411 var 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.
 416 func 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
 428 func 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.
 463 func 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.
 469 func 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
 474 func AndSelectors(selectors ...Selector) Selector {
 475         return andTerm(selectors)
 476 }