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

   1 /*
   2 Copyright 2014 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 labels
  18
  19 import (
  20         "bytes"
  21         "fmt"
  22         "sort"
  23         "strconv"
  24         "strings"
  25
  26         "k8s.io/apimachinery/pkg/selection"
  27         "k8s.io/apimachinery/pkg/util/sets"
  28         "k8s.io/apimachinery/pkg/util/validation"
  29         "k8s.io/klog"
  30 )
  31
  32 // Requirements is AND of all requirements.
  33 type Requirements []Requirement
  34
  35 // Selector represents a label selector.
  36 type Selector interface {
  37         // Matches returns true if this selector matches the given set of labels.
  38         Matches(Labels) bool
  39
  40         // Empty returns true if this selector does not restrict the selection space.
  41         Empty() bool
  42
  43         // String returns a human readable string that represents this selector.
  44         String() string
  45
  46         // Add adds requirements to the Selector
  47         Add(r ...Requirement) Selector
  48
  49         // Requirements converts this interface into Requirements to expose
  50         // more detailed selection information.
  51         // If there are querying parameters, it will return converted requirements and selectable=true.
  52         // If this selector doesn't want to select anything, it will return selectable=false.
  53         Requirements() (requirements Requirements, selectable bool)
  54
  55         // Make a deep copy of the selector.
  56         DeepCopySelector() Selector
  57 }
  58
  59 // Everything returns a selector that matches all labels.
  60 func Everything() Selector {
  61         return internalSelector{}
  62 }
  63
  64 type nothingSelector struct{}
  65
  66 func (n nothingSelector) Matches(_ Labels) bool              { return false }
  67 func (n nothingSelector) Empty() bool                        { return false }
  68 func (n nothingSelector) String() string                     { return "" }
  69 func (n nothingSelector) Add(_ ...Requirement) Selector      { return n }
  70 func (n nothingSelector) Requirements() (Requirements, bool) { return nil, false }
  71 func (n nothingSelector) DeepCopySelector() Selector         { return n }
  72
  73 // Nothing returns a selector that matches no labels
  74 func Nothing() Selector {
  75         return nothingSelector{}
  76 }
  77
  78 // NewSelector returns a nil selector
  79 func NewSelector() Selector {
  80         return internalSelector(nil)
  81 }
  82
  83 type internalSelector []Requirement
  84
  85 func (s internalSelector) DeepCopy() internalSelector {
  86         if s == nil {
  87                 return nil
  88         }
  89         result := make([]Requirement, len(s))
  90         for i := range s {
  91                 s[i].DeepCopyInto(&result[i])
  92         }
  93         return result
  94 }
  95
  96 func (s internalSelector) DeepCopySelector() Selector {
  97         return s.DeepCopy()
  98 }
  99
 100 // ByKey sorts requirements by key to obtain deterministic parser
 101 type ByKey []Requirement
 102
 103 func (a ByKey) Len() int { return len(a) }
 104
 105 func (a ByKey) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
 106
 107 func (a ByKey) Less(i, j int) bool { return a[i].key < a[j].key }
 108
 109 // Requirement contains values, a key, and an operator that relates the key and values.
 110 // The zero value of Requirement is invalid.
 111 // Requirement implements both set based match and exact match
 112 // Requirement should be initialized via NewRequirement constructor for creating a valid Requirement.
 113 // +k8s:deepcopy-gen=true
 114 type Requirement struct {
 115         key      string
 116         operator selection.Operator
 117         // In huge majority of cases we have at most one value here.
 118         // It is generally faster to operate on a single-element slice
 119         // than on a single-element map, so we have a slice here.
 120         strValues []string
 121 }
 122
 123 // NewRequirement is the constructor for a Requirement.
 124 // If any of these rules is violated, an error is returned:
 125 // (1) The operator can only be In, NotIn, Equals, DoubleEquals, NotEquals, Exists, or DoesNotExist.
 126 // (2) If the operator is In or NotIn, the values set must be non-empty.
 127 // (3) If the operator is Equals, DoubleEquals, or NotEquals, the values set must contain one value.
 128 // (4) If the operator is Exists or DoesNotExist, the value set must be empty.
 129 // (5) If the operator is Gt or Lt, the values set must contain only one value, which will be interpreted as an integer.
 130 // (6) The key is invalid due to its length, or sequence
 131 //     of characters. See validateLabelKey for more details.
 132 //
 133 // The empty string is a valid value in the input values set.
 134 func NewRequirement(key string, op selection.Operator, vals []string) (*Requirement, error) {
 135         if err := validateLabelKey(key); err != nil {
 136                 return nil, err
 137         }
 138         switch op {
 139         case selection.In, selection.NotIn:
 140                 if len(vals) == 0 {
 141                         return nil, fmt.Errorf("for 'in', 'notin' operators, values set can't be empty")
 142                 }
 143         case selection.Equals, selection.DoubleEquals, selection.NotEquals:
 144                 if len(vals) != 1 {
 145                         return nil, fmt.Errorf("exact-match compatibility requires one single value")
 146                 }
 147         case selection.Exists, selection.DoesNotExist:
 148                 if len(vals) != 0 {
 149                         return nil, fmt.Errorf("values set must be empty for exists and does not exist")
 150                 }
 151         case selection.GreaterThan, selection.LessThan:
 152                 if len(vals) != 1 {
 153                         return nil, fmt.Errorf("for 'Gt', 'Lt' operators, exactly one value is required")
 154                 }
 155                 for i := range vals {
 156                         if _, err := strconv.ParseInt(vals[i], 10, 64); err != nil {
 157                                 return nil, fmt.Errorf("for 'Gt', 'Lt' operators, the value must be an integer")
 158                         }
 159                 }
 160         default:
 161                 return nil, fmt.Errorf("operator '%v' is not recognized", op)
 162         }
 163
 164         for i := range vals {
 165                 if err := validateLabelValue(vals[i]); err != nil {
 166                         return nil, err
 167                 }
 168         }
 169         return &Requirement{key: key, operator: op, strValues: vals}, nil
 170 }
 171
 172 func (r *Requirement) hasValue(value string) bool {
 173         for i := range r.strValues {
 174                 if r.strValues[i] == value {
 175                         return true
 176                 }
 177         }
 178         return false
 179 }
 180
 181 // Matches returns true if the Requirement matches the input Labels.
 182 // There is a match in the following cases:
 183 // (1) The operator is Exists and Labels has the Requirement's key.
 184 // (2) The operator is In, Labels has the Requirement's key and Labels'
 185 //     value for that key is in Requirement's value set.
 186 // (3) The operator is NotIn, Labels has the Requirement's key and
 187 //     Labels' value for that key is not in Requirement's value set.
 188 // (4) The operator is DoesNotExist or NotIn and Labels does not have the
 189 //     Requirement's key.
 190 // (5) The operator is GreaterThanOperator or LessThanOperator, and Labels has
 191 //     the Requirement's key and the corresponding value satisfies mathematical inequality.
 192 func (r *Requirement) Matches(ls Labels) bool {
 193         switch r.operator {
 194         case selection.In, selection.Equals, selection.DoubleEquals:
 195                 if !ls.Has(r.key) {
 196                         return false
 197                 }
 198                 return r.hasValue(ls.Get(r.key))
 199         case selection.NotIn, selection.NotEquals:
 200                 if !ls.Has(r.key) {
 201                         return true
 202                 }
 203                 return !r.hasValue(ls.Get(r.key))
 204         case selection.Exists:
 205                 return ls.Has(r.key)
 206         case selection.DoesNotExist:
 207                 return !ls.Has(r.key)
 208         case selection.GreaterThan, selection.LessThan:
 209                 if !ls.Has(r.key) {
 210                         return false
 211                 }
 212                 lsValue, err := strconv.ParseInt(ls.Get(r.key), 10, 64)
 213                 if err != nil {
 214                         klog.V(10).Infof("ParseInt failed for value %+v in label %+v, %+v", ls.Get(r.key), ls, err)
 215                         return false
 216                 }
 217
 218                 // There should be only one strValue in r.strValues, and can be converted to a integer.
 219                 if len(r.strValues) != 1 {
 220                         klog.V(10).Infof("Invalid values count %+v of requirement %#v, for 'Gt', 'Lt' operators, exactly one value is required", len(r.strValues), r)
 221                         return false
 222                 }
 223
 224                 var rValue int64
 225                 for i := range r.strValues {
 226                         rValue, err = strconv.ParseInt(r.strValues[i], 10, 64)
 227                         if err != nil {
 228                                 klog.V(10).Infof("ParseInt failed for value %+v in requirement %#v, for 'Gt', 'Lt' operators, the value must be an integer", r.strValues[i], r)
 229                                 return false
 230                         }
 231                 }
 232                 return (r.operator == selection.GreaterThan && lsValue > rValue) || (r.operator == selection.LessThan && lsValue < rValue)
 233         default:
 234                 return false
 235         }
 236 }
 237
 238 // Key returns requirement key
 239 func (r *Requirement) Key() string {
 240         return r.key
 241 }
 242
 243 // Operator returns requirement operator
 244 func (r *Requirement) Operator() selection.Operator {
 245         return r.operator
 246 }
 247
 248 // Values returns requirement values
 249 func (r *Requirement) Values() sets.String {
 250         ret := sets.String{}
 251         for i := range r.strValues {
 252                 ret.Insert(r.strValues[i])
 253         }
 254         return ret
 255 }
 256
 257 // Empty returns true if the internalSelector doesn't restrict selection space
 258 func (lsel internalSelector) Empty() bool {
 259         if lsel == nil {
 260                 return true
 261         }
 262         return len(lsel) == 0
 263 }
 264
 265 // String returns a human-readable string that represents this
 266 // Requirement. If called on an invalid Requirement, an error is
 267 // returned. See NewRequirement for creating a valid Requirement.
 268 func (r *Requirement) String() string {
 269         var buffer bytes.Buffer
 270         if r.operator == selection.DoesNotExist {
 271                 buffer.WriteString("!")
 272         }
 273         buffer.WriteString(r.key)
 274
 275         switch r.operator {
 276         case selection.Equals:
 277                 buffer.WriteString("=")
 278         case selection.DoubleEquals:
 279                 buffer.WriteString("==")
 280         case selection.NotEquals:
 281                 buffer.WriteString("!=")
 282         case selection.In:
 283                 buffer.WriteString(" in ")
 284         case selection.NotIn:
 285                 buffer.WriteString(" notin ")
 286         case selection.GreaterThan:
 287                 buffer.WriteString(">")
 288         case selection.LessThan:
 289                 buffer.WriteString("<")
 290         case selection.Exists, selection.DoesNotExist:
 291                 return buffer.String()
 292         }
 293
 294         switch r.operator {
 295         case selection.In, selection.NotIn:
 296                 buffer.WriteString("(")
 297         }
 298         if len(r.strValues) == 1 {
 299                 buffer.WriteString(r.strValues[0])
 300         } else { // only > 1 since == 0 prohibited by NewRequirement
 301                 // normalizes value order on output, without mutating the in-memory selector representation
 302                 // also avoids normalization when it is not required, and ensures we do not mutate shared data
 303                 buffer.WriteString(strings.Join(safeSort(r.strValues), ","))
 304         }
 305
 306         switch r.operator {
 307         case selection.In, selection.NotIn:
 308                 buffer.WriteString(")")
 309         }
 310         return buffer.String()
 311 }
 312
 313 // safeSort sort input strings without modification
 314 func safeSort(in []string) []string {
 315         if sort.StringsAreSorted(in) {
 316                 return in
 317         }
 318         out := make([]string, len(in))
 319         copy(out, in)
 320         sort.Strings(out)
 321         return out
 322 }
 323
 324 // Add adds requirements to the selector. It copies the current selector returning a new one
 325 func (lsel internalSelector) Add(reqs ...Requirement) Selector {
 326         var sel internalSelector
 327         for ix := range lsel {
 328                 sel = append(sel, lsel[ix])
 329         }
 330         for _, r := range reqs {
 331                 sel = append(sel, r)
 332         }
 333         sort.Sort(ByKey(sel))
 334         return sel
 335 }
 336
 337 // Matches for a internalSelector returns true if all
 338 // its Requirements match the input Labels. If any
 339 // Requirement does not match, false is returned.
 340 func (lsel internalSelector) Matches(l Labels) bool {
 341         for ix := range lsel {
 342                 if matches := lsel[ix].Matches(l); !matches {
 343                         return false
 344                 }
 345         }
 346         return true
 347 }
 348
 349 func (lsel internalSelector) Requirements() (Requirements, bool) { return Requirements(lsel), true }
 350
 351 // String returns a comma-separated string of all
 352 // the internalSelector Requirements' human-readable strings.
 353 func (lsel internalSelector) String() string {
 354         var reqs []string
 355         for ix := range lsel {
 356                 reqs = append(reqs, lsel[ix].String())
 357         }
 358         return strings.Join(reqs, ",")
 359 }
 360
 361 // Token represents constant definition for lexer token
 362 type Token int
 363
 364 const (
 365         // ErrorToken represents scan error
 366         ErrorToken Token = iota
 367         // EndOfStringToken represents end of string
 368         EndOfStringToken
 369         // ClosedParToken represents close parenthesis
 370         ClosedParToken
 371         // CommaToken represents the comma
 372         CommaToken
 373         // DoesNotExistToken represents logic not
 374         DoesNotExistToken
 375         // DoubleEqualsToken represents double equals
 376         DoubleEqualsToken
 377         // EqualsToken represents equal
 378         EqualsToken
 379         // GreaterThanToken represents greater than
 380         GreaterThanToken
 381         // IdentifierToken represents identifier, e.g. keys and values
 382         IdentifierToken
 383         // InToken represents in
 384         InToken
 385         // LessThanToken represents less than
 386         LessThanToken
 387         // NotEqualsToken represents not equal
 388         NotEqualsToken
 389         // NotInToken represents not in
 390         NotInToken
 391         // OpenParToken represents open parenthesis
 392         OpenParToken
 393 )
 394
 395 // string2token contains the mapping between lexer Token and token literal
 396 // (except IdentifierToken, EndOfStringToken and ErrorToken since it makes no sense)
 397 var string2token = map[string]Token{
 398         ")":     ClosedParToken,
 399         ",":     CommaToken,
 400         "!":     DoesNotExistToken,
 401         "==":    DoubleEqualsToken,
 402         "=":     EqualsToken,
 403         ">":     GreaterThanToken,
 404         "in":    InToken,
 405         "<":     LessThanToken,
 406         "!=":    NotEqualsToken,
 407         "notin": NotInToken,
 408         "(":     OpenParToken,
 409 }
 410
 411 // ScannedItem contains the Token and the literal produced by the lexer.
 412 type ScannedItem struct {
 413         tok     Token
 414         literal string
 415 }
 416
 417 // isWhitespace returns true if the rune is a space, tab, or newline.
 418 func isWhitespace(ch byte) bool {
 419         return ch == ' ' || ch == '\t' || ch == '\r' || ch == '\n'
 420 }
 421
 422 // isSpecialSymbol detect if the character ch can be an operator
 423 func isSpecialSymbol(ch byte) bool {
 424         switch ch {
 425         case '=', '!', '(', ')', ',', '>', '<':
 426                 return true
 427         }
 428         return false
 429 }
 430
 431 // Lexer represents the Lexer struct for label selector.
 432 // It contains necessary informationt to tokenize the input string
 433 type Lexer struct {
 434         // s stores the string to be tokenized
 435         s string
 436         // pos is the position currently tokenized
 437         pos int
 438 }
 439
 440 // read return the character currently lexed
 441 // increment the position and check the buffer overflow
 442 func (l *Lexer) read() (b byte) {
 443         b = 0
 444         if l.pos < len(l.s) {
 445                 b = l.s[l.pos]
 446                 l.pos++
 447         }
 448         return b
 449 }
 450
 451 // unread 'undoes' the last read character
 452 func (l *Lexer) unread() {
 453         l.pos--
 454 }
 455
 456 // scanIDOrKeyword scans string to recognize literal token (for example 'in') or an identifier.
 457 func (l *Lexer) scanIDOrKeyword() (tok Token, lit string) {
 458         var buffer []byte
 459 IdentifierLoop:
 460         for {
 461                 switch ch := l.read(); {
 462                 case ch == 0:
 463                         break IdentifierLoop
 464                 case isSpecialSymbol(ch) || isWhitespace(ch):
 465                         l.unread()
 466                         break IdentifierLoop
 467                 default:
 468                         buffer = append(buffer, ch)
 469                 }
 470         }
 471         s := string(buffer)
 472         if val, ok := string2token[s]; ok { // is a literal token?
 473                 return val, s
 474         }
 475         return IdentifierToken, s // otherwise is an identifier
 476 }
 477
 478 // scanSpecialSymbol scans string starting with special symbol.
 479 // special symbol identify non literal operators. "!=", "==", "="
 480 func (l *Lexer) scanSpecialSymbol() (Token, string) {
 481         lastScannedItem := ScannedItem{}
 482         var buffer []byte
 483 SpecialSymbolLoop:
 484         for {
 485                 switch ch := l.read(); {
 486                 case ch == 0:
 487                         break SpecialSymbolLoop
 488                 case isSpecialSymbol(ch):
 489                         buffer = append(buffer, ch)
 490                         if token, ok := string2token[string(buffer)]; ok {
 491                                 lastScannedItem = ScannedItem{tok: token, literal: string(buffer)}
 492                         } else if lastScannedItem.tok != 0 {
 493                                 l.unread()
 494                                 break SpecialSymbolLoop
 495                         }
 496                 default:
 497                         l.unread()
 498                         break SpecialSymbolLoop
 499                 }
 500         }
 501         if lastScannedItem.tok == 0 {
 502                 return ErrorToken, fmt.Sprintf("error expected: keyword found '%s'", buffer)
 503         }
 504         return lastScannedItem.tok, lastScannedItem.literal
 505 }
 506
 507 // skipWhiteSpaces consumes all blank characters
 508 // returning the first non blank character
 509 func (l *Lexer) skipWhiteSpaces(ch byte) byte {
 510         for {
 511                 if !isWhitespace(ch) {
 512                         return ch
 513                 }
 514                 ch = l.read()
 515         }
 516 }
 517
 518 // Lex returns a pair of Token and the literal
 519 // literal is meaningfull only for IdentifierToken token
 520 func (l *Lexer) Lex() (tok Token, lit string) {
 521         switch ch := l.skipWhiteSpaces(l.read()); {
 522         case ch == 0:
 523                 return EndOfStringToken, ""
 524         case isSpecialSymbol(ch):
 525                 l.unread()
 526                 return l.scanSpecialSymbol()
 527         default:
 528                 l.unread()
 529                 return l.scanIDOrKeyword()
 530         }
 531 }
 532
 533 // Parser data structure contains the label selector parser data structure
 534 type Parser struct {
 535         l            *Lexer
 536         scannedItems []ScannedItem
 537         position     int
 538 }
 539
 540 // ParserContext represents context during parsing:
 541 // some literal for example 'in' and 'notin' can be
 542 // recognized as operator for example 'x in (a)' but
 543 // it can be recognized as value for example 'value in (in)'
 544 type ParserContext int
 545
 546 const (
 547         // KeyAndOperator represents key and operator
 548         KeyAndOperator ParserContext = iota
 549         // Values represents values
 550         Values
 551 )
 552
 553 // lookahead func returns the current token and string. No increment of current position
 554 func (p *Parser) lookahead(context ParserContext) (Token, string) {
 555         tok, lit := p.scannedItems[p.position].tok, p.scannedItems[p.position].literal
 556         if context == Values {
 557                 switch tok {
 558                 case InToken, NotInToken:
 559                         tok = IdentifierToken
 560                 }
 561         }
 562         return tok, lit
 563 }
 564
 565 // consume returns current token and string. Increments the position
 566 func (p *Parser) consume(context ParserContext) (Token, string) {
 567         p.position++
 568         tok, lit := p.scannedItems[p.position-1].tok, p.scannedItems[p.position-1].literal
 569         if context == Values {
 570                 switch tok {
 571                 case InToken, NotInToken:
 572                         tok = IdentifierToken
 573                 }
 574         }
 575         return tok, lit
 576 }
 577
 578 // scan runs through the input string and stores the ScannedItem in an array
 579 // Parser can now lookahead and consume the tokens
 580 func (p *Parser) scan() {
 581         for {
 582                 token, literal := p.l.Lex()
 583                 p.scannedItems = append(p.scannedItems, ScannedItem{token, literal})
 584                 if token == EndOfStringToken {
 585                         break
 586                 }
 587         }
 588 }
 589
 590 // parse runs the left recursive descending algorithm
 591 // on input string. It returns a list of Requirement objects.
 592 func (p *Parser) parse() (internalSelector, error) {
 593         p.scan() // init scannedItems
 594
 595         var requirements internalSelector
 596         for {
 597                 tok, lit := p.lookahead(Values)
 598                 switch tok {
 599                 case IdentifierToken, DoesNotExistToken:
 600                         r, err := p.parseRequirement()
 601                         if err != nil {
 602                                 return nil, fmt.Errorf("unable to parse requirement: %v", err)
 603                         }
 604                         requirements = append(requirements, *r)
 605                         t, l := p.consume(Values)
 606                         switch t {
 607                         case EndOfStringToken:
 608                                 return requirements, nil
 609                         case CommaToken:
 610                                 t2, l2 := p.lookahead(Values)
 611                                 if t2 != IdentifierToken && t2 != DoesNotExistToken {
 612                                         return nil, fmt.Errorf("found '%s', expected: identifier after ','", l2)
 613                                 }
 614                         default:
 615                                 return nil, fmt.Errorf("found '%s', expected: ',' or 'end of string'", l)
 616                         }
 617                 case EndOfStringToken:
 618                         return requirements, nil
 619                 default:
 620                         return nil, fmt.Errorf("found '%s', expected: !, identifier, or 'end of string'", lit)
 621                 }
 622         }
 623 }
 624
 625 func (p *Parser) parseRequirement() (*Requirement, error) {
 626         key, operator, err := p.parseKeyAndInferOperator()
 627         if err != nil {
 628                 return nil, err
 629         }
 630         if operator == selection.Exists || operator == selection.DoesNotExist { // operator found lookahead set checked
 631                 return NewRequirement(key, operator, []string{})
 632         }
 633         operator, err = p.parseOperator()
 634         if err != nil {
 635                 return nil, err
 636         }
 637         var values sets.String
 638         switch operator {
 639         case selection.In, selection.NotIn:
 640                 values, err = p.parseValues()
 641         case selection.Equals, selection.DoubleEquals, selection.NotEquals, selection.GreaterThan, selection.LessThan:
 642                 values, err = p.parseExactValue()
 643         }
 644         if err != nil {
 645                 return nil, err
 646         }
 647         return NewRequirement(key, operator, values.List())
 648
 649 }
 650
 651 // parseKeyAndInferOperator parse literals.
 652 // in case of no operator '!, in, notin, ==, =, !=' are found
 653 // the 'exists' operator is inferred
 654 func (p *Parser) parseKeyAndInferOperator() (string, selection.Operator, error) {
 655         var operator selection.Operator
 656         tok, literal := p.consume(Values)
 657         if tok == DoesNotExistToken {
 658                 operator = selection.DoesNotExist
 659                 tok, literal = p.consume(Values)
 660         }
 661         if tok != IdentifierToken {
 662                 err := fmt.Errorf("found '%s', expected: identifier", literal)
 663                 return "", "", err
 664         }
 665         if err := validateLabelKey(literal); err != nil {
 666                 return "", "", err
 667         }
 668         if t, _ := p.lookahead(Values); t == EndOfStringToken || t == CommaToken {
 669                 if operator != selection.DoesNotExist {
 670                         operator = selection.Exists
 671                 }
 672         }
 673         return literal, operator, nil
 674 }
 675
 676 // parseOperator return operator and eventually matchType
 677 // matchType can be exact
 678 func (p *Parser) parseOperator() (op selection.Operator, err error) {
 679         tok, lit := p.consume(KeyAndOperator)
 680         switch tok {
 681         // DoesNotExistToken shouldn't be here because it's a unary operator, not a binary operator
 682         case InToken:
 683                 op = selection.In
 684         case EqualsToken:
 685                 op = selection.Equals
 686         case DoubleEqualsToken:
 687                 op = selection.DoubleEquals
 688         case GreaterThanToken:
 689                 op = selection.GreaterThan
 690         case LessThanToken:
 691                 op = selection.LessThan
 692         case NotInToken:
 693                 op = selection.NotIn
 694         case NotEqualsToken:
 695                 op = selection.NotEquals
 696         default:
 697                 return "", fmt.Errorf("found '%s', expected: '=', '!=', '==', 'in', notin'", lit)
 698         }
 699         return op, nil
 700 }
 701
 702 // parseValues parses the values for set based matching (x,y,z)
 703 func (p *Parser) parseValues() (sets.String, error) {
 704         tok, lit := p.consume(Values)
 705         if tok != OpenParToken {
 706                 return nil, fmt.Errorf("found '%s' expected: '('", lit)
 707         }
 708         tok, lit = p.lookahead(Values)
 709         switch tok {
 710         case IdentifierToken, CommaToken:
 711                 s, err := p.parseIdentifiersList() // handles general cases
 712                 if err != nil {
 713                         return s, err
 714                 }
 715                 if tok, _ = p.consume(Values); tok != ClosedParToken {
 716                         return nil, fmt.Errorf("found '%s', expected: ')'", lit)
 717                 }
 718                 return s, nil
 719         case ClosedParToken: // handles "()"
 720                 p.consume(Values)
 721                 return sets.NewString(""), nil
 722         default:
 723                 return nil, fmt.Errorf("found '%s', expected: ',', ')' or identifier", lit)
 724         }
 725 }
 726
 727 // parseIdentifiersList parses a (possibly empty) list of
 728 // of comma separated (possibly empty) identifiers
 729 func (p *Parser) parseIdentifiersList() (sets.String, error) {
 730         s := sets.NewString()
 731         for {
 732                 tok, lit := p.consume(Values)
 733                 switch tok {
 734                 case IdentifierToken:
 735                         s.Insert(lit)
 736                         tok2, lit2 := p.lookahead(Values)
 737                         switch tok2 {
 738                         case CommaToken:
 739                                 continue
 740                         case ClosedParToken:
 741                                 return s, nil
 742                         default:
 743                                 return nil, fmt.Errorf("found '%s', expected: ',' or ')'", lit2)
 744                         }
 745                 case CommaToken: // handled here since we can have "(,"
 746                         if s.Len() == 0 {
 747                                 s.Insert("") // to handle (,
 748                         }
 749                         tok2, _ := p.lookahead(Values)
 750                         if tok2 == ClosedParToken {
 751                                 s.Insert("") // to handle ,)  Double "" removed by StringSet
 752                                 return s, nil
 753                         }
 754                         if tok2 == CommaToken {
 755                                 p.consume(Values)
 756                                 s.Insert("") // to handle ,, Double "" removed by StringSet
 757                         }
 758                 default: // it can be operator
 759                         return s, fmt.Errorf("found '%s', expected: ',', or identifier", lit)
 760                 }
 761         }
 762 }
 763
 764 // parseExactValue parses the only value for exact match style
 765 func (p *Parser) parseExactValue() (sets.String, error) {
 766         s := sets.NewString()
 767         tok, lit := p.lookahead(Values)
 768         if tok == EndOfStringToken || tok == CommaToken {
 769                 s.Insert("")
 770                 return s, nil
 771         }
 772         tok, lit = p.consume(Values)
 773         if tok == IdentifierToken {
 774                 s.Insert(lit)
 775                 return s, nil
 776         }
 777         return nil, fmt.Errorf("found '%s', expected: identifier", lit)
 778 }
 779
 780 // Parse takes a string representing a selector and returns a selector
 781 // object, or an error. This parsing function differs from ParseSelector
 782 // as they parse different selectors with different syntaxes.
 783 // The input will cause an error if it does not follow this form:
 784 //
 785 //  <selector-syntax>         ::= <requirement> | <requirement> "," <selector-syntax>
 786 //  <requirement>             ::= [!] KEY [ <set-based-restriction> | <exact-match-restriction> ]
 787 //  <set-based-restriction>   ::= "" | <inclusion-exclusion> <value-set>
 788 //  <inclusion-exclusion>     ::= <inclusion> | <exclusion>
 789 //  <exclusion>               ::= "notin"
 790 //  <inclusion>               ::= "in"
 791 //  <value-set>               ::= "(" <values> ")"
 792 //  <values>                  ::= VALUE | VALUE "," <values>
 793 //  <exact-match-restriction> ::= ["="|"=="|"!="] VALUE
 794 //
 795 // KEY is a sequence of one or more characters following [ DNS_SUBDOMAIN "/" ] DNS_LABEL. Max length is 63 characters.
 796 // VALUE is a sequence of zero or more characters "([A-Za-z0-9_-\.])". Max length is 63 characters.
 797 // Delimiter is white space: (' ', '\t')
 798 // Example of valid syntax:
 799 //  "x in (foo,,baz),y,z notin ()"
 800 //
 801 // Note:
 802 //  (1) Inclusion - " in " - denotes that the KEY exists and is equal to any of the
 803 //      VALUEs in its requirement
 804 //  (2) Exclusion - " notin " - denotes that the KEY is not equal to any
 805 //      of the VALUEs in its requirement or does not exist
 806 //  (3) The empty string is a valid VALUE
 807 //  (4) A requirement with just a KEY - as in "y" above - denotes that
 808 //      the KEY exists and can be any VALUE.
 809 //  (5) A requirement with just !KEY requires that the KEY not exist.
 810 //
 811 func Parse(selector string) (Selector, error) {
 812         parsedSelector, err := parse(selector)
 813         if err == nil {
 814                 return parsedSelector, nil
 815         }
 816         return nil, err
 817 }
 818
 819 // parse parses the string representation of the selector and returns the internalSelector struct.
 820 // The callers of this method can then decide how to return the internalSelector struct to their
 821 // callers. This function has two callers now, one returns a Selector interface and the other
 822 // returns a list of requirements.
 823 func parse(selector string) (internalSelector, error) {
 824         p := &Parser{l: &Lexer{s: selector, pos: 0}}
 825         items, err := p.parse()
 826         if err != nil {
 827                 return nil, err
 828         }
 829         sort.Sort(ByKey(items)) // sort to grant determistic parsing
 830         return internalSelector(items), err
 831 }
 832
 833 func validateLabelKey(k string) error {
 834         if errs := validation.IsQualifiedName(k); len(errs) != 0 {
 835                 return fmt.Errorf("invalid label key %q: %s", k, strings.Join(errs, "; "))
 836         }
 837         return nil
 838 }
 839
 840 func validateLabelValue(v string) error {
 841         if errs := validation.IsValidLabelValue(v); len(errs) != 0 {
 842                 return fmt.Errorf("invalid label value: %q: %s", v, strings.Join(errs, "; "))
 843         }
 844         return nil
 845 }
 846
 847 // SelectorFromSet returns a Selector which will match exactly the given Set. A
 848 // nil and empty Sets are considered equivalent to Everything().
 849 func SelectorFromSet(ls Set) Selector {
 850         if ls == nil || len(ls) == 0 {
 851                 return internalSelector{}
 852         }
 853         var requirements internalSelector
 854         for label, value := range ls {
 855                 r, err := NewRequirement(label, selection.Equals, []string{value})
 856                 if err == nil {
 857                         requirements = append(requirements, *r)
 858                 } else {
 859                         //TODO: double check errors when input comes from serialization?
 860                         return internalSelector{}
 861                 }
 862         }
 863         // sort to have deterministic string representation
 864         sort.Sort(ByKey(requirements))
 865         return requirements
 866 }
 867
 868 // SelectorFromValidatedSet returns a Selector which will match exactly the given Set.
 869 // A nil and empty Sets are considered equivalent to Everything().
 870 // It assumes that Set is already validated and doesn't do any validation.
 871 func SelectorFromValidatedSet(ls Set) Selector {
 872         if ls == nil || len(ls) == 0 {
 873                 return internalSelector{}
 874         }
 875         var requirements internalSelector
 876         for label, value := range ls {
 877                 requirements = append(requirements, Requirement{key: label, operator: selection.Equals, strValues: []string{value}})
 878         }
 879         // sort to have deterministic string representation
 880         sort.Sort(ByKey(requirements))
 881         return requirements
 882 }
 883
 884 // ParseToRequirements takes a string representing a selector and returns a list of
 885 // requirements. This function is suitable for those callers that perform additional
 886 // processing on selector requirements.
 887 // See the documentation for Parse() function for more details.
 888 // TODO: Consider exporting the internalSelector type instead.
 889 func ParseToRequirements(selector string) ([]Requirement, error) {
 890         return parse(selector)
 891 }