func (fs *filterScanner) stateBeginLiteral(scan *filterScanner, c byte) int {
	switch c {
	case '"':
		scan.step = fs.stateInStringLiteral
		return scanFilterBeginLiteral
	case 't', 'T', 'f', 'F', '-', '+', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
		scan.step = fs.stateInNonStringLiteral
		return scanFilterBeginLiteral
	}
	return fs.error(c, "invalid literal")
}
Intermediate state at the start of a literal. We distinguish between string and non-string literal.
package expr
import (
	"fmt"
	"github.com/imulab/go-scim/pkg/v2/spec"
	"strings"
)
func CompileFilter(filter string) (*Expression, error) {
	compiler := &filterCompiler{
		scan:    &filterScanner{},
		data:    append(copyOf(filter), 0, 0),
		off:     0,
		op:      scanFilterSkipSpace,
		opStack: make([]*Expression, 0),
		rsStack: make([]*Expression, 0),
	}
	compiler.scan.init()
	for compiler.hasMore() {
		step, err := compiler.next()
		if err != nil {
			return nil, err
		}
		if step == nil {
			break
		}
		if step.IsLiteral() || step.IsPath() {
			if err := compiler.pushBuildResult(step); err != nil {
				return nil, err
			}
			continue
		}
		switch compiler.pushOperator(step) {
		case pushOpOk:
			break
		case pushOpRightParenthesis:
			for {
				popped := compiler.popOperatorIf(func(top *Expression) bool {
					return !top.IsLeftParenthesis()
				})
				if popped != nil {
					_ = compiler.pushBuildResult(popped)
				} else {
					break
				}
			}
			if len(compiler.opStack) == 0 {
				return nil, fmt.Errorf("%w: mismatched parenthesis", spec.ErrInvalidFilter)
			} else {
				compiler.opStack = compiler.opStack[:len(compiler.opStack)-1]
			}
			break
		case pushOpInsufficientPriority:
			minPriority := opPriority(step.token)
			for {
				popped := compiler.popOperatorIf(func(top *Expression) bool {
					return opPriority(top.token) >= minPriority
				})
				if popped != nil {
					_ = compiler.pushBuildResult(popped)
				} else {
					break
				}
			}
			if compiler.pushOperator(step) != pushOpOk {
				panic("flaw in algorithm")
			}
			break
		}
	}
	for len(compiler.opStack) > 0 {
		_ = compiler.pushBuildResult(compiler.popOperatorIf(func(top *Expression) bool {
			return true
		}))
	}
	if len(compiler.rsStack) != 1 || !compiler.rsStack[0].IsOperator() {
		panic("flaw in algorithm")
	}
	root := compiler.rsStack[0]
	compiler.rsStack = nil
	return root, nil
}
var (
	opPriority = func(op string) int {
		switch strings.ToLower(op) {
		case And, Or, Not:
			return 50
		case Eq, Ne, Sw, Ew, Co, Pr, Gt, Ge, Lt, Le:
			return 100
		default:
			panic("not an operator")
		}
	}
	opLeftAssociative = func(op string) bool {
		switch strings.ToLower(op) {
		case Not:
			return false
		case And, Or, Eq, Ne, Sw, Ew, Co, Pr, Gt, Ge, Lt, Le:
			return true
		default:
			panic("not an operator")
		}
	}
	opCardinality = func(op string) int {
		switch op {
		case Not, Pr:
			return 1
		case And, Or, Eq, Ne, Sw, Ew, Co, Gt, Ge, Lt, Le:
			return 2
		default:
			panic("not an operator")
		}
	}
)
type filterCompiler struct {
	scan *filterScanner
	data []byte
	off int
	op int
	opStack []*Expression
	rsStack []*Expression
}
func (c *filterCompiler) pushOperator(step *Expression) int {
	if step.IsRightParenthesis() {
		return pushOpRightParenthesis
	}
	if step.IsOperator() && len(c.opStack) > 0 {
		p := c.opStack[len(c.opStack)-1]
		if p.IsOperator() {
			if opLeftAssociative(step.token) && opPriority(step.token) <= opPriority(p.token) {
				return pushOpInsufficientPriority
			} else if opLeftAssociative(step.token) && opPriority(step.token) < opPriority(p.token) {
				return pushOpInsufficientPriority
			}
		}
	}
	c.opStack = append(c.opStack, step)
	return pushOpOk
}
func (c *filterCompiler) popOperatorIf(condition func(top *Expression) bool) *Expression {
	if len(c.opStack) == 0 {
		return nil
	}
	top := c.opStack[len(c.opStack)-1]
	if condition(top) {
		c.opStack = c.opStack[0 : len(c.opStack)-1]
		return top
	}
	return nil
}
func (c *filterCompiler) pushBuildResult(step *Expression) error {
	if step.IsLiteral() {
		c.rsStack = append(c.rsStack, step)
		return nil
	}
	if step.IsPath() {
		head, err := CompilePath(step.token)
		if err != nil {
			return fmt.Errorf("%w: invalid path in filter", spec.ErrInvalidFilter)
		} else if head.ContainsFilter() {
			return fmt.Errorf("%w: illegal nested filter", spec.ErrInvalidFilter)
		}
		c.rsStack = append(c.rsStack, head)
		return nil
	}
	if !step.IsOperator() || len(c.rsStack) == 0 {
		panic("algorithm flaw")
	}
	switch opCardinality(step.token) {
	case 1:
		{
			first := c.rsStack[len(c.rsStack)-1]
			c.rsStack = c.rsStack[:len(c.rsStack)-1]
			step.left = first
		}
	case 2:
		{
			first, second := c.rsStack[len(c.rsStack)-1], c.rsStack[len(c.rsStack)-2]
			c.rsStack = c.rsStack[:len(c.rsStack)-2]
			step.left = second
			step.right = first
		}
	default:
		panic("unsupported cardinality")
	}
	c.rsStack = append(c.rsStack, step)
	return nil
}
func (c *filterCompiler) hasMore() bool {
	return c.op != scanFilterEnd && c.op != scanFilterError
}
func (c *filterCompiler) next() (*Expression, error) {
	if c.op == scanFilterError {
		return nil, c.scan.err
	}
	_ = c.scanWhile(scanFilterSkipSpace)
	switch c.op {
	case scanFilterEnd:
		return nil, nil
	case scanFilterParenthesis:
		return newParenthesis(string(c.data[c.off-1])), nil
	case scanFilterBeginAny:
		return c.scanOperatorOrPath()
	case scanFilterBeginPath:
		return c.scanPath()
	case scanFilterBeginOp:
		return c.scanOperator()
	case scanFilterBeginLiteral:
		return c.scanLiteral()
	default:
		return nil, c.errCompile()
	}
}
func (c *filterCompiler) scanLiteral() (*Expression, error) {
	start := c.off - 1
	end := c.scanWhile(scanFilterContinue)
	switch c.op {
	case scanFilterEndLiteral, scanFilterEnd:
		return newLiteral(string(c.data[start:end])), nil
	default:
		return nil, c.errCompile()
	}
}
func (c *filterCompiler) scanOperator() (*Expression, error) {
	start := c.off - 1
	end := c.scanWhile(scanFilterContinue)
	switch c.op {
	case scanFilterEndOp, scanFilterEnd:
		return newOperator(string(c.data[start:end])), nil
	default:
		return nil, c.errCompile()
	}
}
func (c *filterCompiler) scanPath() (*Expression, error) {
	start := c.off - 1
	end := c.scanWhile(scanFilterContinue)
	switch c.op {
	case scanFilterEndPath, scanFilterEnd:
		return newPath(string(c.data[start:end])), nil
	default:
		return nil, c.errCompile()
	}
}
func (c *filterCompiler) scanOperatorOrPath() (*Expression, error) {
	start := c.off - 1
	end := c.scanWhile(scanFilterContinue)
	switch c.op {
	case scanFilterEndPath:
		return newPath(string(c.data[start:end])), nil
	case scanFilterEndOp:
		return newOperator(string(c.data[start:end])), nil
	default:
		return nil, c.errCompile()
	}
}
func (c *filterCompiler) scanWhile(op int) int {
	for c.off < len(c.data) {
		c.op = c.scan.step(c.scan, c.data[c.off])
		if c.op == scanFilterInsertSpace {
			c.op = c.scan.step(c.scan, ' ')
			return c.off
		}
		c.off++
		if c.op != op {
			return c.off - 1
		}
	}
	return len(c.data) + 1
}
func (c *filterCompiler) errCompile() error {
	return fmt.Errorf("%w: error compiling filter", spec.ErrInvalidFilter)
}
const (
	scanFilterContinue = iota
	scanFilterSkipSpace
	scanFilterInsertSpace
	scanFilterBeginAny
	scanFilterBeginPath
	scanFilterEndPath
	scanFilterBeginOp
	scanFilterEndOp
	scanFilterBeginLiteral
	scanFilterEndLiteral
	scanFilterParenthesis
	scanFilterError
	scanFilterEnd
)
const (
	pushOpOk = iota
	pushOpRightParenthesis
	pushOpInsufficientPriority
)
func explainFilterEvent(op int) string {
	switch op {
	case scanFilterContinue:
		return "continue"
	case scanFilterSkipSpace:
		return "space"
	case scanFilterInsertSpace:
		return "insert space"
	case scanFilterBeginAny:
		return "any"
	case scanFilterBeginPath:
		return "begin path"
	case scanFilterEndPath:
		return "end path"
	case scanFilterBeginOp:
		return "begin op"
	case scanFilterEndOp:
		return "end op"
	case scanFilterBeginLiteral:
		return "begin literal"
	case scanFilterEndLiteral:
		return "end literal"
	case scanFilterParenthesis:
		return "paren"
	case scanFilterError:
		return "error"
	case scanFilterEnd:
		return "end"
	default:
		return "unknown"
	}
}
type filterScanner struct {
	step func(*filterScanner, byte) int
	parenLevel int
	err error
	bytes int64
}
func (fs *filterScanner) init() {
	fs.step = fs.stateBeginPredicate
	fs.parenLevel = 0
	fs.err = nil
	fs.bytes = 0
}
func (fs *filterScanner) stateBeginPredicate(scan *filterScanner, c byte) int {
	if c == ' ' {
		return scanFilterSkipSpace
	}
	switch c {
	case 'n', 'N':
		scan.step = fs.stateN
		return scanFilterBeginAny
	case '(':
		fs.parenLevel++
		scan.step = fs.stateBeginPredicate
		return scanFilterParenthesis
	}
	if isFirstAlphabet(c) {
		scan.step = fs.stateInPath
		return scanFilterBeginPath
	}
	return fs.error(c, "invalid character at the start of the predicate")
}
func (fs *filterScanner) stateEndPredicate(scan *filterScanner, c byte) int {
	if c == ' ' {
		return scanFilterSkipSpace
	}
	switch c {
	case ')':
		scan.parenLevel--
		return scanFilterParenthesis
	case 'a', 'A':
		scan.step = fs.stateOpA
		return scanFilterBeginOp
	case 'o', 'O':
		scan.step = fs.stateOpO
		return scanFilterBeginOp
	case 0:
		scan.step = fs.stateEof
		return scanFilterEnd
	}
	return fs.error(c, "invalid character at the end of the predicate")
}
func (fs *filterScanner) stateN(scan *filterScanner, c byte) int {
	switch c {
	case 'o', 'O':
		scan.step = fs.stateNo
		return scanFilterContinue
	}
	if c == '.' || c == ':' || isNonFirstAlphabet(c) {
		scan.step = fs.stateInPath
		return scanFilterContinue
	}
	return fs.error(c, "invalid character in path")
}
func (fs *filterScanner) stateNo(scan *filterScanner, c byte) int {
	switch c {
	case 't', 'T':
		scan.step = fs.stateNot
		return scanFilterContinue
	}
	if c == '.' || c == ':' || isNonFirstAlphabet(c) {
		scan.step = fs.stateInPath
		return scanFilterContinue
	}
	return fs.error(c, "invalid character in path")
}
func (fs *filterScanner) stateNot(scan *filterScanner, c byte) int {
	switch c {
	case ' ':
		scan.step = fs.stateBeginPredicate
		return scanFilterEndOp
	case '(':
		return scanFilterInsertSpace
	}
	if c == '.' || c == ':' || isNonFirstAlphabet(c) {
		scan.step = fs.stateInPath
		return scanFilterContinue
	}
	return fs.error(c, "invalid character in path")
}
func (fs *filterScanner) stateInPath(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginOp
		return scanFilterEndPath
	}
	if c == '.' || c == ':' || isNonFirstAlphabet(c) {
		return scanFilterContinue
	}
	return fs.error(c, "invalid character in path")
}
func (fs *filterScanner) stateBeginOp(scan *filterScanner, c byte) int {
	if c == ' ' {
		return scanFilterSkipSpace
	}
	switch c {
	case 'a', 'A':
		scan.step = fs.stateOpA
		return scanFilterBeginOp
	case 'c', 'C':
		scan.step = fs.stateOpC
		return scanFilterBeginOp
	case 'e', 'E':
		scan.step = fs.stateOpE
		return scanFilterBeginOp
	case 'g', 'G':
		scan.step = fs.stateOpG
		return scanFilterBeginOp
	case 'l', 'L':
		scan.step = fs.stateOpL
		return scanFilterBeginOp
	case 'n', 'N':
		scan.step = fs.stateOpN
		return scanFilterBeginOp
	case 'o', 'O':
		scan.step = fs.stateOpO
		return scanFilterBeginOp
	case 'p', 'P':
		scan.step = fs.stateOpP
		return scanFilterBeginOp
	case 's', 'S':
		scan.step = fs.stateOpS
		return scanFilterBeginOp
	}
	return fs.error(c, "invalid character in operator")
}
func (fs *filterScanner) stateOpA(scan *filterScanner, c byte) int {
	if c == 'n' || c == 'N' {
		scan.step = fs.stateOpAn
		return scanFilterContinue
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpAn(scan *filterScanner, c byte) int {
	if c == 'd' || c == 'D' {
		scan.step = fs.stateOpAnd
		return scanFilterContinue
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpAnd(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginPredicate
		return scanFilterEndOp
	}
	if c == '(' {
		return scanFilterInsertSpace
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpC(scan *filterScanner, c byte) int {
	if c == 'o' || c == 'O' {
		scan.step = fs.stateOpCo
		return scanFilterContinue
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpCo(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginLiteral
		return scanFilterEndOp
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpE(scan *filterScanner, c byte) int {
	switch c {
	case 'q', 'Q':
		scan.step = fs.stateOpEq
		return scanFilterContinue
	case 'w', 'W':
		scan.step = fs.stateOpEw
		return scanFilterContinue
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpEq(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginLiteral
		return scanFilterEndOp
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpEw(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginLiteral
		return scanFilterEndOp
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpG(scan *filterScanner, c byte) int {
	switch c {
	case 't', 'T':
		scan.step = fs.stateOpGt
		return scanFilterContinue
	case 'e', 'E':
		scan.step = fs.stateOpGe
		return scanFilterContinue
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpGt(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginLiteral
		return scanFilterEndOp
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpGe(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginLiteral
		return scanFilterEndOp
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpL(scan *filterScanner, c byte) int {
	switch c {
	case 't', 'T':
		scan.step = fs.stateOpLt
		return scanFilterContinue
	case 'e', 'E':
		scan.step = fs.stateOpLe
		return scanFilterContinue
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpLt(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginLiteral
		return scanFilterEndOp
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpLe(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginLiteral
		return scanFilterEndOp
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpN(scan *filterScanner, c byte) int {
	switch c {
	case 'o', 'O':
		scan.step = fs.stateOpNo
		return scanFilterContinue
	case 'e', 'E':
		scan.step = fs.stateOpNe
		return scanFilterContinue
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpNe(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginLiteral
		return scanFilterEndOp
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpNo(scan *filterScanner, c byte) int {
	if c == 't' || c == 'T' {
		scan.step = fs.stateOpNot
		return scanFilterContinue
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpNot(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginPredicate
		return scanFilterEndOp
	}
	if c == '(' {
		return scanFilterInsertSpace
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpO(scan *filterScanner, c byte) int {
	if c == 'r' || c == 'R' {
		scan.step = fs.stateOpOr
		return scanFilterContinue
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpOr(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginPredicate
		return scanFilterEndOp
	}
	if c == '(' {
		return scanFilterInsertSpace
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpP(scan *filterScanner, c byte) int {
	if c == 'r' || c == 'R' {
		scan.step = fs.stateOpPr
		return scanFilterContinue
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpPr(scan *filterScanner, c byte) int {
	if c == ' ' || c == 0 {
		scan.step = fs.stateEndPredicate
		return scanFilterEndOp
	}
	if c == ')' {
		return scanFilterInsertSpace
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpS(scan *filterScanner, c byte) int {
	if c == 'w' || c == 'W' {
		scan.step = fs.stateOpSw
		return scanFilterContinue
	}
	return fs.errInvalidOperator(c)
}
func (fs *filterScanner) stateOpSw(scan *filterScanner, c byte) int {
	if c == ' ' {
		scan.step = fs.stateBeginLiteral
		return scanFilterEndOp
	}
	return fs.errInvalidOperator(c)
}