filterparser.go at master ⋅ aporeto-inc/elemental

// Copyright 2019 Aporeto Inc.
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//     http://www.apache.org/licenses/LICENSE-2.0
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package elemental

import (
	"fmt"
	"regexp"
	"strconv"
	"strings"
	"time"
)

type checkRuneFunc = func(ch rune) bool

type parserToken int

const (
	parserTokenILLEGAL parserToken = iota
	parserTokenEOF
	parserTokenWHITESPACE
	parserTokenWORD
	parserTokenLEFTPARENTHESIS
	parserTokenRIGHTPARENTHESIS
	parserTokenAND
	parserTokenOR
	parserTokenQUOTE
	parserTokenSINGLEQUOTE
	parserTokenEQUAL
	parserTokenNOTEQUAL
	parserTokenLT
	parserTokenLTE
	parserTokenGT
	parserTokenGTE
	parserTokenCONTAINS
	parserTokenMATCHES
	parserTokenTRUE
	parserTokenFALSE
	parserTokenLEFTSQUAREBRACKET
	parserTokenRIGHTSQUAREBRACKET
	parserTokenCOMMA
	parserTokenNOTCONTAINS
	// parserTokenNOTMATCHES not implemented yet in filters.
	parserTokenIN
	parserTokenNOTIN
	parserTokenNOT
	parserTokenEXISTS
	parserTokenNOTEXISTS
)

const (
	wordAND         = "AND"
	wordCONTAINS    = "CONTAINS"
	wordEQUAL       = "=="
	wordFALSE       = "FALSE"
	wordGT          = ">"
	wordGTE         = ">="
	wordIN          = "IN"
	wordLT          = "<"
	wordLTE         = "<="
	wordMATCHES     = "MATCHES"
	wordNOTCONTAINS = "NOT CONTAINS"
	wordNOTEQUAL    = "!="
	wordNOTIN       = "NOT IN"
	wordOR          = "OR"
	wordTRUE        = "TRUE"
	wordNOT         = "NOT"
	wordEXISTS      = "EXISTS"
	wordNOTEXISTS   = "NOT EXISTS"
	wordEOF         = "EOF"
)

const (
	runeEOF                = rune(0)
	runeLEFTPARENTHESIS    = '('
	runeRIGHTPARENTHESIS   = ')'
	runeQUOTE              = '"'
	runeSINGLEQUOTE        = '\''
	runeLEFTSQUAREBRACKET  = '['
	runeRIGHTSQUAREBRACKET = ']'
	runeCOMMA              = ','
)

var specialLetters = map[rune]interface{}{
	'-':  nil,
	'_':  nil,
	'@':  nil,
	':':  nil,
	'$':  nil,
	'#':  nil,
	'.':  nil,
	'/':  nil,
	'\\': nil,
	'*':  nil,
}

var operatorStart = map[rune]interface{}{
	'<': nil,
	'>': nil,
	'=': nil,
	'!': nil,
}

var (
	operatorsToToken = map[string]parserToken{
		wordEQUAL:       parserTokenEQUAL,
		wordNOTEQUAL:    parserTokenNOTEQUAL,
		wordLT:          parserTokenLT,
		wordLTE:         parserTokenLTE,
		wordGT:          parserTokenGT,
		wordGTE:         parserTokenGTE,
		wordCONTAINS:    parserTokenCONTAINS,
		wordNOTCONTAINS: parserTokenNOTCONTAINS,
		wordMATCHES:     parserTokenMATCHES,
		wordIN:          parserTokenIN,
		wordNOTIN:       parserTokenNOTIN,
		wordNOT:         parserTokenNOT,
		wordEXISTS:      parserTokenEXISTS,
		wordNOTEXISTS:   parserTokenNOTEXISTS,
	}

	wordToToken = map[string]parserToken{
		wordAND:   parserTokenAND,
		wordOR:    parserTokenOR,
		wordTRUE:  parserTokenTRUE,
		wordFALSE: parserTokenFALSE,
	}

	runeToToken = map[rune]parserToken{
		runeEOF:                parserTokenEOF,
		runeLEFTPARENTHESIS:    parserTokenLEFTPARENTHESIS,
		runeRIGHTPARENTHESIS:   parserTokenRIGHTPARENTHESIS,
		runeQUOTE:              parserTokenQUOTE,
		runeSINGLEQUOTE:        parserTokenSINGLEQUOTE,
		runeLEFTSQUAREBRACKET:  parserTokenLEFTSQUAREBRACKET,
		runeRIGHTSQUAREBRACKET: parserTokenRIGHTSQUAREBRACKET,
		runeCOMMA:              parserTokenCOMMA,
	}
)

var datePattern = regexp.MustCompile(`^date\((.*)\)$`)
var nowPattern = regexp.MustCompile(`^now\((.*)\)$`)
var dateLayout = "2006-01-02"
var dateTimeLayout = "2006-01-02 15:04"
var errorInvalidExpression = fmt.Errorf("invalid expression")

// FilterParser represents a Parser
type FilterParser struct {
	scanner *scanner
	config  filterParserConfig
	buffer  struct {
		token   parserToken // last read token
		literal string      // last read literal
		size    int         // buffer size (max=1)
	}
}

// NewFilterParser returns an instance of FilterParser for the given input
func NewFilterParser(input string, opts ...FilterParserOption) *FilterParser {

	var config filterParserConfig
	for _, o := range opts {
		o(&config)
	}

	return &FilterParser{
		config:  config,
		scanner: newScanner(input),
	}
}

// Parse parses the input string and returns a new Filter.
func (p *FilterParser) Parse() (*Filter, error) {

	token, literal := p.peekIgnoreWhitespace()

	// The input needs to start with a word, a quote or a left parenthesis.
	if token != parserTokenWORD &&
		token != parserTokenQUOTE &&
		token != parserTokenSINGLEQUOTE &&
		token != parserTokenLEFTPARENTHESIS {
		return nil, fmt.Errorf("invalid start of expression. found %s", literal)
	}

	// Stack all discovered the filters
	var stack []*Filter
	// Default conjunction is an and.
	var conjunction parserToken = -1

	finalFilter := NewFilterComposer()
	for {
		token, literal := p.scanIgnoreWhitespace()

		if token == parserTokenEOF || token == parserTokenRIGHTPARENTHESIS {
			// In case of EOF or ")", we need to finalize the filter.

			switch len(stack) {
			case 0:
				// Nothing to do here.
			case 1:
				// No specific combination
				finalFilter = stack[0]
			default:
				// Combination depending on the conjunction
				if conjunction == parserTokenOR {
					finalFilter.Or(stack...)
				} else {
					finalFilter.And(stack...)
				}
			}
			break
		}

		if token == parserTokenQUOTE || token == parserTokenSINGLEQUOTE {
			// Handle expression starting with QUOTE like "a" operator b
			key, err := p.parseUntilQuoteSimilar(token)
			if err != nil {
				return nil, err
			}

			operator, value, err := p.parseOperatorAndValue()
			if err != nil {
				return nil, err
			}

			filter, err := p.makeFilter(key, operator, value)
			if err != nil {
				return nil, err
			}

			stack = append(stack, filter)
			continue
		}

		if token == parserTokenWORD {
			// Handle expression without QUOTE like a operator b
			// In that case, the literal is the word scanned.
			operator, value, err := p.parseOperatorAndValue()
			if err != nil {
				return nil, err
			}

			filter, err := p.makeFilter(literal, operator, value)
			if err != nil {
				return nil, err
			}

			stack = append(stack, filter)
			continue
		}

		if token == parserTokenAND {
			// Switch the conjunction to an AND
			if conjunction != -1 && conjunction == parserTokenOR && len(stack) > 1 {
				filter := NewFilterComposer().Or(stack...).Done()
				stack = []*Filter{filter}
			}
			conjunction = token
			continue
		}

		if token == parserTokenOR {
			// Switch the conjunction to an OR
			if conjunction != -1 && conjunction == parserTokenAND && len(stack) > 1 {
				filter := NewFilterComposer().And(stack...).Done()
				stack = []*Filter{filter}
			}
			conjunction = token
			continue
		}

		if token == parserTokenLEFTPARENTHESIS {
			// In case of "(", a subfilter needs to be computed
			// and stacked to the previously found filters.

			subFilter, err := p.Parse()
			if err != nil {
				return nil, err
			}
			stack = append(stack, subFilter)
		}
	}

	return finalFilter.Done(), nil
}

// scan returns the next token scanned or the last bufferred one
func (p *FilterParser) scan() (parserToken, string) {
	// If a token has been buffered, use it
	if p.buffer.size != 0 {
		p.buffer.size = 0
		return p.buffer.token, p.buffer.literal
	}

	// Otherwise scan the next token
	token, literal := p.scanner.scan()

	// Save it to the buffer in case we unscan later.
	p.buffer.token, p.buffer.literal = token, literal

	return token, literal
}

// unscan put back the token into the buffer.
func (p *FilterParser) unscan() {
	p.buffer.size = 1
}

// peekIgnoreWhitespace scans to the next whitespace and unscan it
func (p *FilterParser) peekIgnoreWhitespace() (tok parserToken, lit string) {

	tok, lit = p.scanIgnoreWhitespace()
	p.unscan()
	return
}

// scanIgnoreWhitespace scans the next non-whitespace token.
func (p *FilterParser) scanIgnoreWhitespace() (tok parserToken, lit string) {

	tok, lit = p.scan()

	if tok == parserTokenWHITESPACE {
		tok, lit = p.scan()
	}

	return
}

func (p *FilterParser) parseOperatorAndValue() (parserToken, interface{}, error) {

	operator, err := p.parseOperator()
	if err != nil {
		return parserTokenILLEGAL, nil, err
	}

	if _, ok := p.config.unsupportedComparators[operator]; ok {
		return parserTokenILLEGAL, nil, fmt.Errorf("unsupported comparator: %s", tokenToOperator(operator))
	}

	if operator == parserTokenEXISTS || operator == parserTokenNOTEXISTS {
		return operator, nil, nil
	}

	value, err := p.parseValue()
	if err != nil {
		return parserTokenILLEGAL, nil, err
	}

	return operator, value, nil
}

func tokenToOperator(t parserToken) string {

	for operator, token := range operatorsToToken {
		if t == token {
			return operator
		}
	}

	return ""
}

func (p *FilterParser) makeFilter(key string, operator parserToken, value interface{}) (*Filter, error) {

	if strings.HasPrefix(key, "$") {
		return nil, fmt.Errorf("could not start a parameter with $. Found %s", key)
	}

	filter := NewFilterComposer()

	// Create filter
	switch operator {
	case parserTokenEQUAL:
		filter.WithKey(key).Equals(value)
	case parserTokenNOTEQUAL:
		filter.WithKey(key).NotEquals(value)
	case parserTokenLT:
		filter.WithKey(key).LesserThan(value)
	case parserTokenLTE:
		filter.WithKey(key).LesserOrEqualThan(value)
	case parserTokenGT:
		filter.WithKey(key).GreaterThan(value)
	case parserTokenGTE:
		filter.WithKey(key).GreaterOrEqualThan(value)
	case parserTokenCONTAINS:
		if values, ok := value.([]interface{}); ok {
			filter.WithKey(key).Contains(values...)
		} else {
			filter.WithKey(key).Contains(value)
		}
	case parserTokenNOTCONTAINS:
		if values, ok := value.([]interface{}); ok {
			filter.WithKey(key).NotContains(values...)
		} else {
			filter.WithKey(key).NotContains(value)
		}
	case parserTokenIN:
		if values, ok := value.([]interface{}); ok {
			filter.WithKey(key).In(values...)
		} else {
			filter.WithKey(key).In(value)
		}
	case parserTokenNOTIN:
		if values, ok := value.([]interface{}); ok {
			filter.WithKey(key).NotIn(values...)
		} else {
			filter.WithKey(key).NotIn(value)
		}
	case parserTokenMATCHES:
		if values, ok := value.([]interface{}); ok {
			filter.WithKey(key).Matches(values...)
		} else {
			filter.WithKey(key).Matches(value)
		}
	case parserTokenEXISTS:
		filter.WithKey(key).Exists()
	case parserTokenNOTEXISTS:
		filter.WithKey(key).NotExists()
	default:
		return nil, fmt.Errorf("unsupported operator")
	}

	token, literal := p.peekIgnoreWhitespace()
	if token != parserTokenAND &&
		token != parserTokenOR &&
		token != parserTokenRIGHTPARENTHESIS &&
		token != parserTokenEOF {

		if token == parserTokenEOF {
			literal = wordEOF
		}
		return nil, fmt.Errorf("invalid keyword after %s. found %s", filter.Done().String(), literal)
	}

	return filter.Done(), nil
}

func (p *FilterParser) parseOperator() (parserToken, error) {

	token, literal := p.scanIgnoreWhitespace()

	operatorNot := false
	if token == parserTokenNOT {
		operatorNot = true
		token, literal = p.scanIgnoreWhitespace()
	}

	if !tokenIsOperator(token) {
		if token == parserTokenEOF {
			literal = wordEOF
		}

		return parserTokenILLEGAL, fmt.Errorf("invalid operator. found %s instead of (==, !=, <, <=, >, >=, contains, in, matches, exists)", literal)
	}

	if operatorNot {
		switch token {
		case parserTokenCONTAINS:
			return parserTokenNOTCONTAINS, nil
		case parserTokenIN:
			return parserTokenNOTIN, nil
		case parserTokenEXISTS:
			return parserTokenNOTEXISTS, nil
		default:
			return parserTokenILLEGAL, fmt.Errorf("invalid usage of operator NOT before %s", literal)
		}
	}

	return token, nil
}

func (p *FilterParser) parseValue() (interface{}, error) {

	token, literal := p.scanIgnoreWhitespace()

	if token == parserTokenQUOTE || token == parserTokenSINGLEQUOTE {
		return p.parseStringValue()
	}

	if token == parserTokenLEFTSQUAREBRACKET {
		return p.parseArrayValue()
	}

	if token == parserTokenTRUE {
		return true, nil
	}

	if token == parserTokenFALSE {
		return false, nil
	}

	if i, err := strconv.ParseInt(literal, 10, 0); err == nil {
		return i, nil
	}

	if f, err := strconv.ParseFloat(literal, 0); err == nil {
		return f, nil
	}

	datetime, err := p.parseDateValue()
	if err == nil {
		return datetime, nil
	}
	if err != errorInvalidExpression {
		return nil, err
	}

	duration, err := p.parseDurationValue()
	if err == nil {
		return duration, nil
	}
	if err != errorInvalidExpression {
		return nil, err
	}

	v, err := p.parseStringValue()
	if err != nil {
		return nil, err
	}

	return v, nil
}

// parseExpression parse an expression with the regex if the prefix matches and returns the matching value.
func (p *FilterParser) parseExpression(prefix string, regex *regexp.Regexp) (string, error) {

	p.unscan()
	_, literal := p.scanIgnoreWhitespace()

	if literal != prefix {
		p.unscan()
		return "", errorInvalidExpression
	}

	expression := literal
	token, literal := p.scanIgnoreWhitespace()
	if token != parserTokenLEFTPARENTHESIS {
		p.unscan()
		return "", errorInvalidExpression
	}

	expression += literal
	for { // Read the expression until the next )
		token, literal = p.scan()
		expression += literal

		if token == parserTokenLEFTPARENTHESIS ||
			token == parserTokenEOF {
			return "", errorInvalidExpression
		}

		if token == parserTokenRIGHTPARENTHESIS {
			break
		}
	}

	matches := regex.FindStringSubmatch(expression)
	if len(matches) != 2 {
		return "", errorInvalidExpression
	}

	return strings.Trim(matches[1], " \""), nil
}

func (p *FilterParser) parseDurationValue() (time.Duration, error) {

	expression, err := p.parseExpression("now", nowPattern)
	if err != nil {
		return -1, err
	}

	if expression == "" {
		return time.Duration(0), nil
	}

	d, err := time.ParseDuration(expression)
	if err != nil {
		return -1, fmt.Errorf("unable to parse duration %s: %s", expression, err.Error())
	}
	return d, nil
}

func (p *FilterParser) parseDateValue() (time.Time, error) {

	expression, err := p.parseExpression("date", datePattern)
	if err != nil {
		return time.Time{}, err
	}

	// RFC3339 Layout
	t, err := time.Parse(time.RFC3339, expression)
	if err == nil {
		return t, nil
	}
	// YYYY-MM-DD HH:MM Layout
	t, err = time.Parse(dateTimeLayout, expression)
	if err == nil {
		return t, nil
	}
	// YYYY-MM-DD Layout
	t, err = time.Parse(dateLayout, expression)
	if err == nil {
		return t, nil
	}

	return t, fmt.Errorf("unable to parse date format %s", expression)
}

func (p *FilterParser) parseUntilQuoteSimilar(tokenQuote parserToken) (string, error) {

	var word string
	// Scan everything until the next quote or the end of the input
	for {
		token, literal := p.scan()
		if token == parserTokenEOF {
			return "", fmt.Errorf("missing quote after %s", word)
		}

		if token == tokenQuote {
			return word, nil
		}

		// Add anything to the value
		word += literal
	}
}

func (p *FilterParser) parseStringValue() (string, error) {

	p.unscan()
	token, literal := p.scanIgnoreWhitespace()

	// Quoted string
	if token == parserTokenQUOTE || token == parserTokenSINGLEQUOTE {
		return p.parseUntilQuoteSimilar(token)
	}

	// Unquoted string can have only one word
	if token != parserTokenWORD {
		if token == parserTokenEOF {
			literal = wordEOF
		}
		return "", fmt.Errorf("invalid value. found %s", literal)
	}

	token, next := p.peekIgnoreWhitespace()
	switch token {
	case parserTokenQUOTE, parserTokenSINGLEQUOTE:
		return "", fmt.Errorf("missing quote before the value: %s", literal)
	case parserTokenWORD:
		return "", fmt.Errorf("missing parentheses to protect value: %s %s", literal, next)
	}

	return literal, nil
}

func (p *FilterParser) parseArrayValue() ([]interface{}, error) {

	p.unscan()

	token, literal := p.scanIgnoreWhitespace()
	if token != parserTokenLEFTSQUAREBRACKET {
		return nil, fmt.Errorf("invalid start of list. found %s", literal)
	}

	values := []interface{}{}

	for {

		token, literal := p.scanIgnoreWhitespace()

		if token == parserTokenEOF ||
			token == parserTokenLEFTPARENTHESIS ||
			token == parserTokenRIGHTPARENTHESIS {
			return nil, fmt.Errorf("invalid end of array. found %s", literal)
		}

		if token == parserTokenRIGHTSQUAREBRACKET {
			break
		}

		if token == parserTokenCOMMA {
			continue
		}

		p.unscan()
		value, err := p.parseValue()
		if err != nil {
			return nil, err
		}

		values = append(values, value)
	}

	return values, nil
}

func isWhitespace(ch rune) bool { return ch == ' ' || ch == '\t' || ch == '\n' }
func isDigit(ch rune) bool      { return (ch >= '0' && ch <= '9') }
func isLetter(ch rune) bool {

	if _, ok := specialLetters[ch]; ok {
		return true
	}

	if _, ok := operatorStart[ch]; ok {
		return true
	}

	return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')
}

func isOperatorStart(ch rune) bool {

	_, ok := operatorStart[ch]
	return ok
}

func isOperator(runes ...rune) (parserToken, string, bool) {
	word := string(runes)
	token, ok := operatorsToToken[word]

	return token, word, ok
}

func tokenIsOperator(token parserToken) bool {

	return token == parserTokenEQUAL ||
		token == parserTokenNOTEQUAL ||
		token == parserTokenLT ||
		token == parserTokenLTE ||
		token == parserTokenGT ||
		token == parserTokenGTE ||
		token == parserTokenCONTAINS ||
		token == parserTokenIN ||
		token == parserTokenMATCHES ||
		token == parserTokenEXISTS ||
		token == parserTokenNOTEXISTS ||
		token == parserTokenNOTCONTAINS ||
		token == parserTokenNOTIN
}

Read our documentation on viewing source code .

Navigation	Overlay
`t` Navigate files	`h` Toggle hits
`y` Change url to tip of branch	`m` Toggle misses
`b / v` Jump to prev/next hit line	`p` Toggle partial
`z / x` Jump to prev/next missed or partial line	`1..9` Toggle flags
`shift + o` Open current page in GitHub	`a` Toggle all on
`/ or ?` Show keyboard shortcuts dialog	`c` Toggle context lines or commits

1		// Copyright 2019 Aporeto Inc.
2		// Licensed under the Apache License, Version 2.0 (the "License");
3		// you may not use this file except in compliance with the License.
4		// You may obtain a copy of the License at
5		// http://www.apache.org/licenses/LICENSE-2.0
6		// Unless required by applicable law or agreed to in writing, software
7		// distributed under the License is distributed on an "AS IS" BASIS,
8		// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
9		// See the License for the specific language governing permissions and
10		// limitations under the License.
11
12		package elemental
13
14		import (
15		"fmt"
16		"regexp"
17		"strconv"
18		"strings"
19		"time"
20		)
21
22		type checkRuneFunc = func(ch rune) bool
23
24		type parserToken int
25
26		const (
27		parserTokenILLEGAL parserToken = iota
28		parserTokenEOF
29		parserTokenWHITESPACE
30		parserTokenWORD
31		parserTokenLEFTPARENTHESIS
32		parserTokenRIGHTPARENTHESIS
33		parserTokenAND
34		parserTokenOR
35		parserTokenQUOTE
36		parserTokenSINGLEQUOTE
37		parserTokenEQUAL
38		parserTokenNOTEQUAL
39		parserTokenLT
40		parserTokenLTE
41		parserTokenGT
42		parserTokenGTE
43		parserTokenCONTAINS
44		parserTokenMATCHES
45		parserTokenTRUE
46		parserTokenFALSE
47		parserTokenLEFTSQUAREBRACKET
48		parserTokenRIGHTSQUAREBRACKET
49		parserTokenCOMMA
50		parserTokenNOTCONTAINS
51		// parserTokenNOTMATCHES not implemented yet in filters.
52		parserTokenIN
53		parserTokenNOTIN
54		parserTokenNOT
55		parserTokenEXISTS
56		parserTokenNOTEXISTS
57		)
58
59		const (
60		wordAND = "AND"
61		wordCONTAINS = "CONTAINS"
62		wordEQUAL = "=="
63		wordFALSE = "FALSE"
64		wordGT = ">"
65		wordGTE = ">="
66		wordIN = "IN"
67		wordLT = "<"
68		wordLTE = "<="
69		wordMATCHES = "MATCHES"
70		wordNOTCONTAINS = "NOT CONTAINS"
71		wordNOTEQUAL = "!="
72		wordNOTIN = "NOT IN"
73		wordOR = "OR"
74		wordTRUE = "TRUE"
75		wordNOT = "NOT"
76		wordEXISTS = "EXISTS"
77		wordNOTEXISTS = "NOT EXISTS"
78		wordEOF = "EOF"
79		)
80
81		const (
82		runeEOF = rune(0)
83		runeLEFTPARENTHESIS = '('
84		runeRIGHTPARENTHESIS = ')'
85		runeQUOTE = '"'
86		runeSINGLEQUOTE = '\''
87		runeLEFTSQUAREBRACKET = '['
88		runeRIGHTSQUAREBRACKET = ']'
89		runeCOMMA = ','
90		)
91
92		var specialLetters = map[rune]interface{}{
93		'-': nil,
94		'_': nil,
95		'@': nil,
96		':': nil,
97		'$': nil,
98		'#': nil,
99		'.': nil,
100		'/': nil,
101		'\\': nil,
102		'*': nil,
103		}
104
105		var operatorStart = map[rune]interface{}{
106		'<': nil,
107		'>': nil,
108		'=': nil,
109		'!': nil,
110		}
111
112		var (
113		operatorsToToken = map[string]parserToken{
114		wordEQUAL: parserTokenEQUAL,
115		wordNOTEQUAL: parserTokenNOTEQUAL,
116		wordLT: parserTokenLT,
117		wordLTE: parserTokenLTE,
118		wordGT: parserTokenGT,
119		wordGTE: parserTokenGTE,
120		wordCONTAINS: parserTokenCONTAINS,
121		wordNOTCONTAINS: parserTokenNOTCONTAINS,
122		wordMATCHES: parserTokenMATCHES,
123		wordIN: parserTokenIN,
124		wordNOTIN: parserTokenNOTIN,
125		wordNOT: parserTokenNOT,
126		wordEXISTS: parserTokenEXISTS,
127		wordNOTEXISTS: parserTokenNOTEXISTS,
128		}
129
130		wordToToken = map[string]parserToken{
131		wordAND: parserTokenAND,
132		wordOR: parserTokenOR,
133		wordTRUE: parserTokenTRUE,
134		wordFALSE: parserTokenFALSE,
135		}
136
137		runeToToken = map[rune]parserToken{
138		runeEOF: parserTokenEOF,
139		runeLEFTPARENTHESIS: parserTokenLEFTPARENTHESIS,
140		runeRIGHTPARENTHESIS: parserTokenRIGHTPARENTHESIS,
141		runeQUOTE: parserTokenQUOTE,
142		runeSINGLEQUOTE: parserTokenSINGLEQUOTE,
143		runeLEFTSQUAREBRACKET: parserTokenLEFTSQUAREBRACKET,
144		runeRIGHTSQUAREBRACKET: parserTokenRIGHTSQUAREBRACKET,
145		runeCOMMA: parserTokenCOMMA,
146		}
147		)
148
149		var datePattern = regexp.MustCompile(`^date\((.*)\)$`)
150		var nowPattern = regexp.MustCompile(`^now\((.*)\)$`)
151		var dateLayout = "2006-01-02"
152		var dateTimeLayout = "2006-01-02 15:04"
153		var errorInvalidExpression = fmt.Errorf("invalid expression")
154
155		// FilterParser represents a Parser
156		type FilterParser struct {
157		scanner *scanner
158		config filterParserConfig
159		buffer struct {
160		token parserToken // last read token
161		literal string // last read literal
162		size int // buffer size (max=1)
163		}
164		}
165
166		// NewFilterParser returns an instance of FilterParser for the given input
167		func NewFilterParser(input string, opts ...FilterParserOption) *FilterParser {
168
169	14	var config filterParserConfig
170		for _, o := range opts {
171	14	o(&config)
172		}
173
174	14	return &FilterParser{
175	14	config: config,
176	14	scanner: newScanner(input),
177		}
178		}
179
180		// Parse parses the input string and returns a new Filter.
181		func (p FilterParser) Parse() (Filter, error) {
182
183	14	token, literal := p.peekIgnoreWhitespace()
184
185		// The input needs to start with a word, a quote or a left parenthesis.
186	14	if token != parserTokenWORD &&
187	14	token != parserTokenQUOTE &&
188	14	token != parserTokenSINGLEQUOTE &&
189	14	token != parserTokenLEFTPARENTHESIS {
190	0	return nil, fmt.Errorf("invalid start of expression. found %s", literal)
191		}
192
193		// Stack all discovered the filters
194	14	var stack []*Filter
195		// Default conjunction is an and.
196	14	var conjunction parserToken = -1
197
198	14	finalFilter := NewFilterComposer()
199		for {
200	14	token, literal := p.scanIgnoreWhitespace()
201
202	14	if token == parserTokenEOF \|\| token == parserTokenRIGHTPARENTHESIS {
203		// In case of EOF or ")", we need to finalize the filter.
204
205	14	switch len(stack) {
206	0	case 0:
207		// Nothing to do here.
208	14	case 1:
209		// No specific combination
210	14	finalFilter = stack[0]
211	14	default:
212		// Combination depending on the conjunction
213	14	if conjunction == parserTokenOR {
214	14	finalFilter.Or(stack...)
215	14	} else {
216	14	finalFilter.And(stack...)
217		}
218		}
219	14	break
220		}
221
222	14	if token == parserTokenQUOTE \|\| token == parserTokenSINGLEQUOTE {
223		// Handle expression starting with QUOTE like "a" operator b
224	14	key, err := p.parseUntilQuoteSimilar(token)
225	14	if err != nil {
226	14	return nil, err
227		}
228
229	14	operator, value, err := p.parseOperatorAndValue()
230	14	if err != nil {
231	14	return nil, err
232		}
233
234	14	filter, err := p.makeFilter(key, operator, value)
235	14	if err != nil {
236	0	return nil, err
237		}
238
239	14	stack = append(stack, filter)
240	14	continue
241		}
242
243	14	if token == parserTokenWORD {
244		// Handle expression without QUOTE like a operator b
245		// In that case, the literal is the word scanned.
246	14	operator, value, err := p.parseOperatorAndValue()
247	14	if err != nil {
248	14	return nil, err
249		}
250
251	14	filter, err := p.makeFilter(literal, operator, value)
252	14	if err != nil {
253	14	return nil, err
254		}
255
256	14	stack = append(stack, filter)
257	14	continue
258		}
259
260	14	if token == parserTokenAND {
261		// Switch the conjunction to an AND
262	14	if conjunction != -1 && conjunction == parserTokenOR && len(stack) > 1 {
263	14	filter := NewFilterComposer().Or(stack...).Done()
264	14	stack = []*Filter{filter}
265		}
266	14	conjunction = token
267	14	continue
268		}
269
270	14	if token == parserTokenOR {
271		// Switch the conjunction to an OR
272	14	if conjunction != -1 && conjunction == parserTokenAND && len(stack) > 1 {
273	14	filter := NewFilterComposer().And(stack...).Done()
274	14	stack = []*Filter{filter}
275		}
276	14	conjunction = token
277	14	continue
278		}
279
280	14	if token == parserTokenLEFTPARENTHESIS {
281		// In case of "(", a subfilter needs to be computed
282		// and stacked to the previously found filters.
283
284	14	subFilter, err := p.Parse()
285	14	if err != nil {
286	14	return nil, err
287		}
288	14	stack = append(stack, subFilter)
289		}
290		}
291
292	14	return finalFilter.Done(), nil
293		}
294
295		// scan returns the next token scanned or the last bufferred one
296		func (p *FilterParser) scan() (parserToken, string) {
297		// If a token has been buffered, use it
298	14	if p.buffer.size != 0 {
299	14	p.buffer.size = 0
300	14	return p.buffer.token, p.buffer.literal
301		}
302
303		// Otherwise scan the next token
304	14	token, literal := p.scanner.scan()
305
306		// Save it to the buffer in case we unscan later.
307	14	p.buffer.token, p.buffer.literal = token, literal
308
309	14	return token, literal
310		}
311
312		// unscan put back the token into the buffer.
313		func (p *FilterParser) unscan() {
314	14	p.buffer.size = 1
315		}
316
317		// peekIgnoreWhitespace scans to the next whitespace and unscan it
318		func (p *FilterParser) peekIgnoreWhitespace() (tok parserToken, lit string) {
319
320	14	tok, lit = p.scanIgnoreWhitespace()
321	14	p.unscan()
322	14	return
323		}
324
325		// scanIgnoreWhitespace scans the next non-whitespace token.
326		func (p *FilterParser) scanIgnoreWhitespace() (tok parserToken, lit string) {
327
328	14	tok, lit = p.scan()
329
330	14	if tok == parserTokenWHITESPACE {
331	14	tok, lit = p.scan()
332		}
333
334	14	return
335		}
336
337		func (p *FilterParser) parseOperatorAndValue() (parserToken, interface{}, error) {
338
339	14	operator, err := p.parseOperator()
340	14	if err != nil {
341	14	return parserTokenILLEGAL, nil, err
342		}
343
344	14	if _, ok := p.config.unsupportedComparators[operator]; ok {
345	14	return parserTokenILLEGAL, nil, fmt.Errorf("unsupported comparator: %s", tokenToOperator(operator))
346		}
347
348	14	if operator == parserTokenEXISTS \|\| operator == parserTokenNOTEXISTS {
349	14	return operator, nil, nil
350		}
351
352	14	value, err := p.parseValue()
353	14	if err != nil {
354	14	return parserTokenILLEGAL, nil, err
355		}
356
357	14	return operator, value, nil
358		}
359
360		func tokenToOperator(t parserToken) string {
361
362		for operator, token := range operatorsToToken {
363	14	if t == token {
364	14	return operator
365		}
366		}
367
368	14	return ""
369		}
370
371		func (p FilterParser) makeFilter(key string, operator parserToken, value interface{}) (Filter, error) {
372
373	14	if strings.HasPrefix(key, "$") {
374	14	return nil, fmt.Errorf("could not start a parameter with $. Found %s", key)
375		}
376
377	14	filter := NewFilterComposer()
378
379		// Create filter
380	14	switch operator {
381	14	case parserTokenEQUAL:
382	14	filter.WithKey(key).Equals(value)
383	14	case parserTokenNOTEQUAL:
384	14	filter.WithKey(key).NotEquals(value)
385	14	case parserTokenLT:
386	14	filter.WithKey(key).LesserThan(value)
387	14	case parserTokenLTE:
388	14	filter.WithKey(key).LesserOrEqualThan(value)
389	14	case parserTokenGT:
390	14	filter.WithKey(key).GreaterThan(value)
391	14	case parserTokenGTE:
392	14	filter.WithKey(key).GreaterOrEqualThan(value)
393	14	case parserTokenCONTAINS:
394	14	if values, ok := value.([]interface{}); ok {
395	14	filter.WithKey(key).Contains(values...)
396	14	} else {
397	14	filter.WithKey(key).Contains(value)
398		}
399	14	case parserTokenNOTCONTAINS:
400	14	if values, ok := value.([]interface{}); ok {
401	14	filter.WithKey(key).NotContains(values...)
402	14	} else {
403	0	filter.WithKey(key).NotContains(value)
404		}
405	14	case parserTokenIN:
406	14	if values, ok := value.([]interface{}); ok {
407	14	filter.WithKey(key).In(values...)
408	14	} else {
409	0	filter.WithKey(key).In(value)
410		}
411	14	case parserTokenNOTIN:
412	14	if values, ok := value.([]interface{}); ok {
413	14	filter.WithKey(key).NotIn(values...)
414	14	} else {
415	0	filter.WithKey(key).NotIn(value)
416		}
417	14	case parserTokenMATCHES:
418	14	if values, ok := value.([]interface{}); ok {
419	14	filter.WithKey(key).Matches(values...)
420	14	} else {
421	14	filter.WithKey(key).Matches(value)
422		}
423	14	case parserTokenEXISTS:
424	14	filter.WithKey(key).Exists()
425	14	case parserTokenNOTEXISTS:
426	14	filter.WithKey(key).NotExists()
427	0	default:
428	0	return nil, fmt.Errorf("unsupported operator")
429		}
430
431	14	token, literal := p.peekIgnoreWhitespace()
432	14	if token != parserTokenAND &&
433	14	token != parserTokenOR &&
434	14	token != parserTokenRIGHTPARENTHESIS &&
435	14	token != parserTokenEOF {
436
437	14	if token == parserTokenEOF {
438	0	literal = wordEOF
439		}
440	14	return nil, fmt.Errorf("invalid keyword after %s. found %s", filter.Done().String(), literal)
441		}
442
443	14	return filter.Done(), nil
444		}
445
446		func (p *FilterParser) parseOperator() (parserToken, error) {
447
448	14	token, literal := p.scanIgnoreWhitespace()
449
450	14	operatorNot := false
451	14	if token == parserTokenNOT {
452	14	operatorNot = true
453	14	token, literal = p.scanIgnoreWhitespace()
454		}
455
456	14	if !tokenIsOperator(token) {
457	14	if token == parserTokenEOF {
458	0	literal = wordEOF
459		}
460
461	14	return parserTokenILLEGAL, fmt.Errorf("invalid operator. found %s instead of (==, !=, <, <=, >, >=, contains, in, matches, exists)", literal)
462		}
463
464	14	if operatorNot {
465	14	switch token {
466	14	case parserTokenCONTAINS:
467	14	return parserTokenNOTCONTAINS, nil
468	14	case parserTokenIN:
469	14	return parserTokenNOTIN, nil
470	14	case parserTokenEXISTS:
471	14	return parserTokenNOTEXISTS, nil
472	0	default:
473	0	return parserTokenILLEGAL, fmt.Errorf("invalid usage of operator NOT before %s", literal)
474		}
475		}
476
477	14	return token, nil
478		}
479
480		func (p *FilterParser) parseValue() (interface{}, error) {
481
482	14	token, literal := p.scanIgnoreWhitespace()
483
484	14	if token == parserTokenQUOTE \|\| token == parserTokenSINGLEQUOTE {
485	14	return p.parseStringValue()
486		}
487
488	14	if token == parserTokenLEFTSQUAREBRACKET {
489	14	return p.parseArrayValue()
490		}
491
492	14	if token == parserTokenTRUE {
493	14	return true, nil
494		}
495
496	14	if token == parserTokenFALSE {
497	14	return false, nil
498		}
499
500	14	if i, err := strconv.ParseInt(literal, 10, 0); err == nil {
501	14	return i, nil
502		}
503
504	14	if f, err := strconv.ParseFloat(literal, 0); err == nil {
505	14	return f, nil
506		}
507
508	14	datetime, err := p.parseDateValue()
509	14	if err == nil {
510	14	return datetime, nil
511		}
512	14	if err != errorInvalidExpression {
513	14	return nil, err
514		}
515
516	14	duration, err := p.parseDurationValue()
517	14	if err == nil {
518	14	return duration, nil
519		}
520	14	if err != errorInvalidExpression {
521	0	return nil, err
522		}
523
524	14	v, err := p.parseStringValue()
525	14	if err != nil {
526	14	return nil, err
527		}
528
529	14	return v, nil
530		}
531
532		// parseExpression parse an expression with the regex if the prefix matches and returns the matching value.
533		func (p FilterParser) parseExpression(prefix string, regex regexp.Regexp) (string, error) {
534
535	14	p.unscan()
536	14	_, literal := p.scanIgnoreWhitespace()
537
538	14	if literal != prefix {
539	14	p.unscan()
540	14	return "", errorInvalidExpression
541		}
542
543	14	expression := literal
544	14	token, literal := p.scanIgnoreWhitespace()
545	14	if token != parserTokenLEFTPARENTHESIS {
546	0	p.unscan()
547	0	return "", errorInvalidExpression
548		}
549
550	14	expression += literal
551	14	for { // Read the expression until the next )
552	14	token, literal = p.scan()
553	14	expression += literal
554
555	14	if token == parserTokenLEFTPARENTHESIS \|\|
556	14	token == parserTokenEOF {
557	0	return "", errorInvalidExpression
558		}
559
560	14	if token == parserTokenRIGHTPARENTHESIS {
561	14	break
562		}
563		}
564
565	14	matches := regex.FindStringSubmatch(expression)
566	14	if len(matches) != 2 {
567	0	return "", errorInvalidExpression
568		}
569
570	14	return strings.Trim(matches[1], " \""), nil
571		}
572
573		func (p *FilterParser) parseDurationValue() (time.Duration, error) {
574
575	14	expression, err := p.parseExpression("now", nowPattern)
576	14	if err != nil {
577	14	return -1, err
578		}
579
580	14	if expression == "" {
581	14	return time.Duration(0), nil
582		}
583
584	14	d, err := time.ParseDuration(expression)
585	14	if err != nil {
586	0	return -1, fmt.Errorf("unable to parse duration %s: %s", expression, err.Error())
587		}
588	14	return d, nil
589		}
590
591		func (p *FilterParser) parseDateValue() (time.Time, error) {
592
593	14	expression, err := p.parseExpression("date", datePattern)
594	14	if err != nil {
595	14	return time.Time{}, err
596		}
597
598		// RFC3339 Layout
599	14	t, err := time.Parse(time.RFC3339, expression)
600	14	if err == nil {
601	14	return t, nil
602		}
603		// YYYY-MM-DD HH:MM Layout
604	14	t, err = time.Parse(dateTimeLayout, expression)
605	14	if err == nil {
606	14	return t, nil
607		}
608		// YYYY-MM-DD Layout
609	14	t, err = time.Parse(dateLayout, expression)
610	14	if err == nil {
611	14	return t, nil
612		}
613
614	14	return t, fmt.Errorf("unable to parse date format %s", expression)
615		}
616
617		func (p *FilterParser) parseUntilQuoteSimilar(tokenQuote parserToken) (string, error) {
618
619	14	var word string
620		// Scan everything until the next quote or the end of the input
621		for {
622	14	token, literal := p.scan()
623	14	if token == parserTokenEOF {
624	14	return "", fmt.Errorf("missing quote after %s", word)
625		}
626
627	14	if token == tokenQuote {
628	14	return word, nil
629		}
630
631		// Add anything to the value
632	14	word += literal
633		}
634		}
635
636		func (p *FilterParser) parseStringValue() (string, error) {
637
638	14	p.unscan()
639	14	token, literal := p.scanIgnoreWhitespace()
640
641		// Quoted string
642	14	if token == parserTokenQUOTE \|\| token == parserTokenSINGLEQUOTE {
643	14	return p.parseUntilQuoteSimilar(token)
644		}
645
646		// Unquoted string can have only one word
647	14	if token != parserTokenWORD {
648	14	if token == parserTokenEOF {
649	0	literal = wordEOF
650		}
651	14	return "", fmt.Errorf("invalid value. found %s", literal)
652		}
653
654	14	token, next := p.peekIgnoreWhitespace()
655	14	switch token {
656	14	case parserTokenQUOTE, parserTokenSINGLEQUOTE:
657	14	return "", fmt.Errorf("missing quote before the value: %s", literal)
658	14	case parserTokenWORD:
659	14	return "", fmt.Errorf("missing parentheses to protect value: %s %s", literal, next)
660		}
661
662	14	return literal, nil
663		}
664
665		func (p *FilterParser) parseArrayValue() ([]interface{}, error) {
666
667	14	p.unscan()
668
669	14	token, literal := p.scanIgnoreWhitespace()
670	14	if token != parserTokenLEFTSQUAREBRACKET {
671	0	return nil, fmt.Errorf("invalid start of list. found %s", literal)
672		}
673
674	14	values := []interface{}{}
675
676		for {
677
678	14	token, literal := p.scanIgnoreWhitespace()
679
680	14	if token == parserTokenEOF \|\|
681	14	token == parserTokenLEFTPARENTHESIS \|\|
682	14	token == parserTokenRIGHTPARENTHESIS {
683	0	return nil, fmt.Errorf("invalid end of array. found %s", literal)
684		}
685
686	14	if token == parserTokenRIGHTSQUAREBRACKET {
687	14	break
688		}
689
690	14	if token == parserTokenCOMMA {
691	14	continue
692		}
693
694	14	p.unscan()
695	14	value, err := p.parseValue()
696	14	if err != nil {
697	0	return nil, err
698		}
699
700	14	values = append(values, value)
701		}
702
703	14	return values, nil
704		}
705
706	14	func isWhitespace(ch rune) bool { return ch == ' ' \|\| ch == '\t' \|\| ch == '\n' }
707	14	func isDigit(ch rune) bool { return (ch >= '0' && ch <= '9') }
708		func isLetter(ch rune) bool {
709
710	14	if _, ok := specialLetters[ch]; ok {
711	14	return true
712		}
713
714	14	if _, ok := operatorStart[ch]; ok {
715	14	return true
716		}
717
718	14	return (ch >= 'a' && ch <= 'z') \|\| (ch >= 'A' && ch <= 'Z')
719		}
720
721		func isOperatorStart(ch rune) bool {
722
723	14	_, ok := operatorStart[ch]
724	14	return ok
725		}
726
727		func isOperator(runes ...rune) (parserToken, string, bool) {
728	14	word := string(runes)
729	14	token, ok := operatorsToToken[word]
730
731	14	return token, word, ok
732		}
733
734		func tokenIsOperator(token parserToken) bool {
735
736	14	return token == parserTokenEQUAL \|\|
737	14	token == parserTokenNOTEQUAL \|\|
738	14	token == parserTokenLT \|\|
739	14	token == parserTokenLTE \|\|
740	14	token == parserTokenGT \|\|
741	14	token == parserTokenGTE \|\|
742	14	token == parserTokenCONTAINS \|\|
743	14	token == parserTokenIN \|\|
744	14	token == parserTokenMATCHES \|\|
745	14	token == parserTokenEXISTS \|\|
746	14	token == parserTokenNOTEXISTS \|\|
747	14	token == parserTokenNOTCONTAINS \|\|
748	14	token == parserTokenNOTIN
749		}