parser.go

Documentation: go.einride.tech/aip/filtering

     1  package filtering
     2  
     3  import (
     4  	"errors"
     5  	"fmt"
     6  	"io"
     7  	"strconv"
     8  	"strings"
     9  
    10  	expr "google.golang.org/genproto/googleapis/api/expr/v1alpha1"
    11  )
    12  
    13  // Parser for filter expressions.
    14  type Parser struct {
    15  	filter    string
    16  	lexer     Lexer
    17  	id        int64
    18  	positions []int32
    19  }
    20  
    21  // Init (re-)initializes the parser to parse the provided filter.
    22  func (p *Parser) Init(filter string) {
    23  	filter = strings.TrimSpace(filter)
    24  	*p = Parser{
    25  		filter:    filter,
    26  		positions: p.positions[:0],
    27  		id:        -1,
    28  	}
    29  	p.lexer.Init(filter)
    30  }
    31  
    32  // Parse the filter.
    33  func (p *Parser) Parse() (*expr.ParsedExpr, error) {
    34  	e, err := p.ParseExpression()
    35  	if err != nil {
    36  		return nil, err
    37  	}
    38  	end := p.lexer.Position()
    39  	if token, err := p.lexer.Lex(); err != nil {
    40  		if !errors.Is(err, io.EOF) {
    41  			return nil, err
    42  		}
    43  	} else {
    44  		return nil, p.errorf(end, "unexpected trailing token %s", token.Type)
    45  	}
    46  	return &expr.ParsedExpr{
    47  		Expr:       e,
    48  		SourceInfo: p.SourceInfo(),
    49  	}, nil
    50  }
    51  
    52  func (p *Parser) SourceInfo() *expr.SourceInfo {
    53  	positions := make(map[int64]int32, len(p.positions))
    54  	for id, position := range p.positions {
    55  		positions[int64(id)] = position
    56  	}
    57  	return &expr.SourceInfo{
    58  		LineOffsets: p.lexer.LineOffsets(),
    59  		Positions:   positions,
    60  	}
    61  }
    62  
    63  // ParseExpression parses an Expression.
    64  //
    65  // EBNF
    66  //
    67  //	expression
    68  //	  : sequence {WS AND WS sequence}
    69  //	  ;
    70  func (p *Parser) ParseExpression() (_ *expr.Expr, err error) {
    71  	start := p.lexer.Position()
    72  	defer func() {
    73  		if err != nil {
    74  			err = p.wrapf(err, start, "expression")
    75  		}
    76  	}()
    77  	sequences := make([]*expr.Expr, 0, 1)
    78  	for {
    79  		_ = p.eatTokens(TokenTypeWhitespace)
    80  		sequence, err := p.ParseSequence()
    81  		if err != nil {
    82  			return nil, err
    83  		}
    84  		sequences = append(sequences, sequence)
    85  		if err := p.eatTokens(TokenTypeWhitespace, TokenTypeAnd, TokenTypeWhitespace); err != nil {
    86  			break
    87  		}
    88  	}
    89  	exp := sequences[0]
    90  	for _, seq := range sequences[1:] {
    91  		exp = parsedExpression(p.nextID(start), exp, seq)
    92  	}
    93  	return exp, nil
    94  }
    95  
    96  // ParseSequence parses a Sequence.
    97  //
    98  // EBNF
    99  //
   100  //	sequence
   101  //	  : factor {WS factor}
   102  //	  ;
   103  func (p *Parser) ParseSequence() (_ *expr.Expr, err error) {
   104  	start := p.lexer.Position()
   105  	defer func() {
   106  		if err != nil {
   107  			err = p.wrapf(err, start, "sequence")
   108  		}
   109  	}()
   110  	factors := make([]*expr.Expr, 0, 2)
   111  	for {
   112  		factor, err := p.ParseFactor()
   113  		if err != nil {
   114  			return nil, err
   115  		}
   116  		factors = append(factors, factor)
   117  		if p.sniffTokens(TokenTypeWhitespace, TokenTypeAnd) {
   118  			break
   119  		}
   120  		if err := p.eatTokens(TokenTypeWhitespace); err != nil {
   121  			break
   122  		}
   123  	}
   124  	if len(factors) == 1 {
   125  		return factors[0], nil
   126  	}
   127  	result := parsedSequence(p.nextID(start), factors[0], factors[1])
   128  	for _, factor := range factors[2:] {
   129  		result = parsedSequence(p.nextID(start), result, factor)
   130  	}
   131  	return result, nil
   132  }
   133  
   134  // ParseFactor parses a Factor.
   135  //
   136  // EBNF
   137  //
   138  //	factor
   139  //	  : term {WS OR WS term}
   140  //	  ;
   141  func (p *Parser) ParseFactor() (_ *expr.Expr, err error) {
   142  	start := p.lexer.Position()
   143  	defer func() {
   144  		if err != nil {
   145  			err = p.wrapf(err, start, "factor")
   146  		}
   147  	}()
   148  	terms := make([]*expr.Expr, 0, 2)
   149  	for {
   150  		term, err := p.ParseTerm()
   151  		if err != nil {
   152  			return nil, err
   153  		}
   154  		terms = append(terms, term)
   155  		if err := p.eatTokens(TokenTypeWhitespace, TokenTypeOr, TokenTypeWhitespace); err != nil {
   156  			break
   157  		}
   158  	}
   159  	if len(terms) == 1 {
   160  		return terms[0], nil
   161  	}
   162  	result := parsedFactor(p.nextID(start), terms[0], terms[1])
   163  	for _, factor := range terms[2:] {
   164  		result = parsedFactor(p.nextID(start), result, factor)
   165  	}
   166  	return result, nil
   167  }
   168  
   169  // ParseTerm parses a Term.
   170  //
   171  // EBNF
   172  //
   173  //	term
   174  //	  : [(NOT WS | MINUS)] simple
   175  //	  ;
   176  func (p *Parser) ParseTerm() (_ *expr.Expr, err error) {
   177  	start := p.lexer.Position()
   178  	defer func() {
   179  		if err != nil {
   180  			err = p.wrapf(err, start, "term")
   181  		}
   182  	}()
   183  	var not, minus bool
   184  	if err := p.eatTokens(TokenTypeNot, TokenTypeWhitespace); err == nil {
   185  		not = true
   186  	} else if err := p.eatTokens(TokenTypeMinus); err == nil {
   187  		minus = true
   188  	}
   189  	simple, err := p.ParseSimple()
   190  	if err != nil {
   191  		return nil, err
   192  	}
   193  	switch {
   194  	case not, minus:
   195  		if minus {
   196  			// Simplify MINUS number to negation of the constant value.
   197  			if constExpr, ok := simple.GetExprKind().(*expr.Expr_ConstExpr); ok {
   198  				switch constantKind := constExpr.ConstExpr.GetConstantKind().(type) {
   199  				case *expr.Constant_Int64Value:
   200  					constantKind.Int64Value *= -1
   201  					return simple, nil
   202  				case *expr.Constant_DoubleValue:
   203  					constantKind.DoubleValue *= -1
   204  					return simple, nil
   205  				}
   206  			}
   207  		}
   208  		return parsedFunction(p.nextID(start), FunctionNot, simple), nil
   209  	default:
   210  		return simple, nil
   211  	}
   212  }
   213  
   214  // ParseSimple parses a Simple.
   215  //
   216  // EBNF
   217  //
   218  //	simple
   219  //	  : restriction
   220  //	  | composite
   221  //	  ;
   222  func (p *Parser) ParseSimple() (_ *expr.Expr, err error) {
   223  	start := p.lexer.Position()
   224  	defer func() {
   225  		if err != nil {
   226  			err = p.wrapf(err, start, "simple")
   227  		}
   228  	}()
   229  	if p.sniffTokens(TokenTypeLeftParen) {
   230  		return p.ParseComposite()
   231  	}
   232  	return p.ParseRestriction()
   233  }
   234  
   235  // ParseRestriction parses a Restriction.
   236  //
   237  // EBNF
   238  //
   239  //	restriction
   240  //	  : comparable [comparator arg]
   241  //	  ;
   242  func (p *Parser) ParseRestriction() (_ *expr.Expr, err error) {
   243  	start := p.lexer.Position()
   244  	defer func() {
   245  		if err != nil {
   246  			err = p.wrapf(err, start, "restriction")
   247  		}
   248  	}()
   249  	comp, err := p.ParseComparable()
   250  	if err != nil {
   251  		return nil, err
   252  	}
   253  	if !(p.sniff(TokenType.IsComparator) || p.sniff(TokenTypeWhitespace.Test, TokenType.IsComparator)) {
   254  		return comp, nil
   255  	}
   256  	_ = p.eatTokens(TokenTypeWhitespace)
   257  	comparatorToken, err := p.parseToken(TokenType.IsComparator)
   258  	if err != nil {
   259  		return nil, err
   260  	}
   261  	_ = p.eatTokens(TokenTypeWhitespace)
   262  	arg, err := p.ParseArg()
   263  	if err != nil {
   264  		return nil, err
   265  	}
   266  	// Special case for `:`
   267  	if comparatorToken.Type == TokenTypeHas && arg.GetIdentExpr() != nil {
   268  		// m:foo - true if m contains the key "foo".
   269  		arg = parsedString(arg.GetId(), arg.GetIdentExpr().GetName())
   270  	}
   271  	return parsedFunction(p.nextID(start), comparatorToken.Type.Function(), comp, arg), nil
   272  }
   273  
   274  // ParseComparable parses a Comparable.
   275  //
   276  // EBNF
   277  //
   278  //	comparable
   279  //	  : member
   280  //	  | function
   281  //	  | number (custom)
   282  //	  ;
   283  func (p *Parser) ParseComparable() (_ *expr.Expr, err error) {
   284  	start := p.lexer.Position()
   285  	defer func() {
   286  		if err != nil {
   287  			err = p.wrapf(err, start, "comparable")
   288  		}
   289  	}()
   290  	if function, ok := p.TryParseFunction(); ok {
   291  		return function, nil
   292  	}
   293  	if number, ok := p.TryParseNumber(); ok {
   294  		return number, nil
   295  	}
   296  	return p.ParseMember()
   297  }
   298  
   299  // ParseMember parses a Member.
   300  //
   301  // EBNF
   302  //
   303  //	member
   304  //	  : value {DOT field}
   305  //	  ;
   306  //
   307  //	value
   308  //	  : TEXT
   309  //	  | STRING
   310  //	  ;
   311  //
   312  //	field
   313  //	  : value
   314  //	  | keyword
   315  //	  | number
   316  //	  ;
   317  func (p *Parser) ParseMember() (_ *expr.Expr, err error) {
   318  	start := p.lexer.Position()
   319  	defer func() {
   320  		if err != nil {
   321  			err = p.wrapf(err, start, "member")
   322  		}
   323  	}()
   324  	valueToken, err := p.parseToken(TokenType.IsValue)
   325  	if err != nil {
   326  		return nil, err
   327  	}
   328  	if !p.sniffTokens(TokenTypeDot) {
   329  		if valueToken.Type == TokenTypeString {
   330  			return parsedString(p.nextID(valueToken.Position), valueToken.Unquote()), nil
   331  		}
   332  		return parsedText(p.nextID(valueToken.Position), valueToken.Value), nil
   333  	}
   334  	value := parsedText(p.nextID(valueToken.Position), valueToken.Unquote())
   335  	_ = p.eatTokens(TokenTypeDot)
   336  	firstFieldToken, err := p.parseToken(TokenType.IsField)
   337  	if err != nil {
   338  		return nil, err
   339  	}
   340  	member := parsedMember(p.nextID(start), value, firstFieldToken.Unquote())
   341  	for {
   342  		if err := p.eatTokens(TokenTypeDot); err != nil {
   343  			break
   344  		}
   345  		fieldToken, err := p.parseToken(TokenType.IsField)
   346  		if err != nil {
   347  			return nil, err
   348  		}
   349  		member = parsedMember(p.nextID(start), member, fieldToken.Unquote())
   350  	}
   351  	return member, nil
   352  }
   353  
   354  // ParseFunction parses a Function.
   355  //
   356  // EBNF
   357  //
   358  //	function
   359  //	  : name {DOT name} LPAREN [argList] RPAREN
   360  //	  ;
   361  //
   362  //	name
   363  //	  : TEXT
   364  //	  | keyword
   365  //	  ;
   366  func (p *Parser) ParseFunction() (_ *expr.Expr, err error) {
   367  	start := p.lexer.Position()
   368  	defer func() {
   369  		if err != nil {
   370  			err = p.wrapf(err, start, "function")
   371  		}
   372  	}()
   373  	var name strings.Builder
   374  	for {
   375  		nameToken, err := p.parseToken(TokenType.IsName)
   376  		if err != nil {
   377  			return nil, err
   378  		}
   379  		_, _ = name.WriteString(nameToken.Unquote())
   380  		if err := p.eatTokens(TokenTypeDot); err != nil {
   381  			break
   382  		}
   383  		_ = name.WriteByte('.')
   384  	}
   385  	if err := p.eatTokens(TokenTypeLeftParen); err != nil {
   386  		return nil, err
   387  	}
   388  	_ = p.eatTokens(TokenTypeWhitespace)
   389  	args := make([]*expr.Expr, 0)
   390  	for !p.sniffTokens(TokenTypeRightParen) {
   391  		arg, err := p.ParseArg()
   392  		if err != nil {
   393  			return nil, err
   394  		}
   395  		args = append(args, arg)
   396  		_ = p.eatTokens(TokenTypeWhitespace)
   397  		if err := p.eatTokens(TokenTypeComma); err != nil {
   398  			break
   399  		}
   400  		_ = p.eatTokens(TokenTypeWhitespace)
   401  	}
   402  	_ = p.eatTokens(TokenTypeWhitespace)
   403  	if err := p.eatTokens(TokenTypeRightParen); err != nil {
   404  		return nil, err
   405  	}
   406  	return parsedFunction(p.nextID(start), name.String(), args...), nil
   407  }
   408  
   409  func (p *Parser) TryParseFunction() (*expr.Expr, bool) {
   410  	start := *p
   411  	function, err := p.ParseFunction()
   412  	if err != nil {
   413  		*p = start
   414  		return nil, false
   415  	}
   416  	return function, true
   417  }
   418  
   419  // ParseComposite parses a Composite.
   420  //
   421  // EBNF
   422  //
   423  //	composite
   424  //	  : LPAREN expression RPAREN
   425  //	  ;
   426  func (p *Parser) ParseComposite() (_ *expr.Expr, err error) {
   427  	start := p.lexer.Position()
   428  	defer func() {
   429  		if err != nil {
   430  			err = p.wrapf(err, start, "composite")
   431  		}
   432  	}()
   433  	if err := p.eatTokens(TokenTypeLeftParen); err != nil {
   434  		return nil, err
   435  	}
   436  	_ = p.eatTokens(TokenTypeWhitespace)
   437  	expression, err := p.ParseExpression()
   438  	if err != nil {
   439  		return nil, err
   440  	}
   441  	_ = p.eatTokens(TokenTypeWhitespace)
   442  	if err := p.eatTokens(TokenTypeRightParen); err != nil {
   443  		return nil, err
   444  	}
   445  	return expression, nil
   446  }
   447  
   448  // ParseNumber parses a number.
   449  //
   450  // EBNF
   451  //
   452  //	number
   453  //	  : float
   454  //	  | int
   455  //	  ;
   456  //
   457  //	float
   458  //	  : MINUS? (NUMBER DOT NUMBER* | DOT NUMBER) EXP?
   459  //	  ;
   460  //
   461  //	int
   462  //	  : MINUS? NUMBER
   463  //	  | MINUS? HEX
   464  //	  ;
   465  func (p *Parser) ParseNumber() (_ *expr.Expr, err error) {
   466  	start := p.lexer.Position()
   467  	defer func() {
   468  		if err != nil {
   469  			err = p.wrapf(err, start, "number")
   470  		}
   471  	}()
   472  	if float, ok := p.TryParseFloat(); ok {
   473  		return float, nil
   474  	}
   475  	return p.ParseInt()
   476  }
   477  
   478  func (p *Parser) TryParseNumber() (*expr.Expr, bool) {
   479  	start := *p
   480  	result, err := p.ParseNumber()
   481  	if err != nil {
   482  		*p = start
   483  		return nil, false
   484  	}
   485  	return result, true
   486  }
   487  
   488  // ParseFloat parses a float.
   489  //
   490  // EBNF
   491  //
   492  //	float
   493  //	  : MINUS? (NUMBER DOT NUMBER* | DOT NUMBER) EXP?
   494  //	  ;
   495  func (p *Parser) ParseFloat() (_ *expr.Expr, err error) {
   496  	start := p.lexer.Position()
   497  	defer func() {
   498  		if err != nil {
   499  			err = p.wrapf(err, start, "float")
   500  		}
   501  	}()
   502  	var minusToken Token
   503  	if p.sniffTokens(TokenTypeMinus) {
   504  		minusToken, _ = p.lexer.Lex()
   505  	}
   506  	var intToken Token
   507  	var hasIntToken bool
   508  	if p.sniffTokens(TokenTypeNumber) {
   509  		intToken, err = p.lexer.Lex()
   510  		if err != nil {
   511  			return nil, err
   512  		}
   513  		hasIntToken = true
   514  	}
   515  	dotToken, err := p.parseToken(TokenTypeDot.Test)
   516  	if err != nil {
   517  		return nil, err
   518  	}
   519  	var fractionToken Token
   520  	var hasFractionToken bool
   521  	if p.sniffTokens(TokenTypeNumber) {
   522  		fractionToken, err = p.lexer.Lex()
   523  		if err != nil {
   524  			return nil, err
   525  		}
   526  		hasFractionToken = true
   527  	}
   528  	// TODO: Support exponents.
   529  	if !hasFractionToken && !hasIntToken {
   530  		return nil, p.errorf(start, "expected int or fraction")
   531  	}
   532  	var stringValue strings.Builder
   533  	stringValue.Grow(
   534  		len(minusToken.Value) + len(intToken.Value) + len(dotToken.Value) + len(fractionToken.Value),
   535  	)
   536  	_, _ = stringValue.WriteString(minusToken.Value)
   537  	_, _ = stringValue.WriteString(intToken.Value)
   538  	_, _ = stringValue.WriteString(dotToken.Value)
   539  	_, _ = stringValue.WriteString(fractionToken.Value)
   540  	floatValue, err := strconv.ParseFloat(stringValue.String(), 64)
   541  	if err != nil {
   542  		return nil, err
   543  	}
   544  	return parsedFloat(p.nextID(start), floatValue), nil
   545  }
   546  
   547  func (p *Parser) TryParseFloat() (*expr.Expr, bool) {
   548  	start := *p
   549  	result, err := p.ParseFloat()
   550  	if err != nil {
   551  		*p = start
   552  		return nil, false
   553  	}
   554  	return result, true
   555  }
   556  
   557  // ParseInt parses an int.
   558  //
   559  // EBNF
   560  //
   561  //	int
   562  //	  : MINUS? NUMBER
   563  //	  | MINUS? HEX
   564  //	  ;
   565  func (p *Parser) ParseInt() (_ *expr.Expr, err error) {
   566  	start := p.lexer.Position()
   567  	defer func() {
   568  		if err != nil {
   569  			err = p.wrapf(err, start, "int")
   570  		}
   571  	}()
   572  	minus := p.eatTokens(TokenTypeMinus) == nil
   573  	token, err := p.parseToken(TokenTypeNumber.Test, TokenTypeHexNumber.Test)
   574  	if err != nil {
   575  		return nil, err
   576  	}
   577  	intValue, err := strconv.ParseInt(token.Value, 0, 64)
   578  	if err != nil {
   579  		return nil, err
   580  	}
   581  	if minus {
   582  		intValue *= -1
   583  	}
   584  	return parsedInt(p.nextID(start), intValue), nil
   585  }
   586  
   587  // ParseArg parses an Arg.
   588  //
   589  // EBNF
   590  //
   591  //	arg
   592  //	  : comparable
   593  //	  | composite
   594  //	  ;
   595  func (p *Parser) ParseArg() (_ *expr.Expr, err error) {
   596  	start := p.lexer.Position()
   597  	defer func() {
   598  		if err != nil {
   599  			err = p.wrapf(err, start, "arg")
   600  		}
   601  	}()
   602  	if p.sniffTokens(TokenTypeLeftParen) {
   603  		return p.ParseComposite()
   604  	}
   605  	return p.ParseComparable()
   606  }
   607  
   608  func (p *Parser) parseToken(fns ...func(TokenType) bool) (Token, error) {
   609  	start := p.lexer.Position()
   610  	token, err := p.lexer.Lex()
   611  	if err != nil {
   612  		return Token{}, p.wrapf(err, start, "parse token")
   613  	}
   614  	for _, fn := range fns {
   615  		if fn(token.Type) {
   616  			return token, nil
   617  		}
   618  	}
   619  	return Token{}, p.errorf(token.Position, "unexpected token %s", token.Type)
   620  }
   621  
   622  func (p *Parser) sniff(fns ...func(TokenType) bool) bool {
   623  	start := *p
   624  	defer func() {
   625  		*p = start
   626  	}()
   627  	for _, fn := range fns {
   628  		if token, err := p.lexer.Lex(); err != nil || !fn(token.Type) {
   629  			return false
   630  		}
   631  	}
   632  	return true
   633  }
   634  
   635  func (p *Parser) sniffTokens(wantTokenTypes ...TokenType) bool {
   636  	start := *p
   637  	defer func() {
   638  		*p = start
   639  	}()
   640  	for _, wantTokenType := range wantTokenTypes {
   641  		if token, err := p.lexer.Lex(); err != nil || token.Type != wantTokenType {
   642  			return false
   643  		}
   644  	}
   645  	return true
   646  }
   647  
   648  func (p *Parser) eatTokens(wantTokenTypes ...TokenType) error {
   649  	start := *p
   650  	for _, wantTokenType := range wantTokenTypes {
   651  		if token, err := p.lexer.Lex(); err != nil || token.Type != wantTokenType {
   652  			*p = start
   653  			return p.errorf(start.lexer.Position(), "expected %s", wantTokenType)
   654  		}
   655  	}
   656  	return nil
   657  }
   658  
   659  func (p *Parser) errorf(position Position, format string, args ...interface{}) error {
   660  	return &parseError{
   661  		filter:   p.filter,
   662  		position: position,
   663  		message:  fmt.Sprintf(format, args...),
   664  	}
   665  }
   666  
   667  func (p *Parser) wrapf(err error, position Position, format string, args ...interface{}) error {
   668  	return &parseError{
   669  		filter:   p.filter,
   670  		position: position,
   671  		message:  fmt.Sprintf(format, args...),
   672  		err:      err,
   673  	}
   674  }
   675  
   676  func (p *Parser) nextID(position Position) int64 {
   677  	p.id++
   678  	p.positions = append(p.positions, position.Offset)
   679  	return p.id
   680  }
   681
View as plain text