selector.go

Documentation: sigs.k8s.io/kustomize/kyaml/yaml/internal/k8sgen/pkg/labels

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