blob: 9be9e57d3affa91f4b43e5bf4f1412f24a21eb90 [file] [log] [blame]
Scott Bakere7144bc2019-10-01 14:16:47 -07001/*
2Copyright 2014 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 labels
18
19import (
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.
33type Requirements []Requirement
34
35// Selector represents a label selector.
36type 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.
60func Everything() Selector {
61 return internalSelector{}
62}
63
64type nothingSelector struct{}
65
66func (n nothingSelector) Matches(_ Labels) bool { return false }
67func (n nothingSelector) Empty() bool { return false }
68func (n nothingSelector) String() string { return "" }
69func (n nothingSelector) Add(_ ...Requirement) Selector { return n }
70func (n nothingSelector) Requirements() (Requirements, bool) { return nil, false }
71func (n nothingSelector) DeepCopySelector() Selector { return n }
72
73// Nothing returns a selector that matches no labels
74func Nothing() Selector {
75 return nothingSelector{}
76}
77
78// NewSelector returns a nil selector
79func NewSelector() Selector {
80 return internalSelector(nil)
81}
82
83type internalSelector []Requirement
84
85func (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
96func (s internalSelector) DeepCopySelector() Selector {
97 return s.DeepCopy()
98}
99
100// ByKey sorts requirements by key to obtain deterministic parser
101type ByKey []Requirement
102
103func (a ByKey) Len() int { return len(a) }
104
105func (a ByKey) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
106
107func (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
114type 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.
134func 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 {
girishke7ca43b2019-10-10 12:30:03 +0000165 if err := validateLabelValue(key, vals[i]); err != nil {
Scott Bakere7144bc2019-10-01 14:16:47 -0700166 return nil, err
167 }
168 }
169 return &Requirement{key: key, operator: op, strValues: vals}, nil
170}
171
172func (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.
192func (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
239func (r *Requirement) Key() string {
240 return r.key
241}
242
243// Operator returns requirement operator
244func (r *Requirement) Operator() selection.Operator {
245 return r.operator
246}
247
248// Values returns requirement values
249func (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
258func (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.
268func (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
314func 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
325func (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.
340func (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
349func (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.
353func (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
362type Token int
363
364const (
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)
397var 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.
412type ScannedItem struct {
413 tok Token
414 literal string
415}
416
417// isWhitespace returns true if the rune is a space, tab, or newline.
418func 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
423func 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
433type 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
442func (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
452func (l *Lexer) unread() {
453 l.pos--
454}
455
456// scanIDOrKeyword scans string to recognize literal token (for example 'in') or an identifier.
457func (l *Lexer) scanIDOrKeyword() (tok Token, lit string) {
458 var buffer []byte
459IdentifierLoop:
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. "!=", "==", "="
480func (l *Lexer) scanSpecialSymbol() (Token, string) {
481 lastScannedItem := ScannedItem{}
482 var buffer []byte
483SpecialSymbolLoop:
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
509func (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
520func (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
534type 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)'
544type ParserContext int
545
546const (
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
554func (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
566func (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
580func (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.
592func (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
625func (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
654func (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
678func (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)
703func (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
729func (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
765func (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//
811func 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.
823func 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
833func 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
girishke7ca43b2019-10-10 12:30:03 +0000840func validateLabelValue(k, v string) error {
Scott Bakere7144bc2019-10-01 14:16:47 -0700841 if errs := validation.IsValidLabelValue(v); len(errs) != 0 {
girishke7ca43b2019-10-10 12:30:03 +0000842 return fmt.Errorf("invalid label value: %q: at key: %q: %s", v, k, strings.Join(errs, "; "))
Scott Bakere7144bc2019-10-01 14:16:47 -0700843 }
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().
849func 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.
871func 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.
889func ParseToRequirements(selector string) ([]Requirement, error) {
890 return parse(selector)
891}