blockchain/query/filter/parser.go

   1 package filter
   2
   3 import (
   4         "fmt"
   5         "strconv"
   6
   7         "github.com/vapor/errors"
   8 )
   9
  10 // ErrBadFilter is returned from Parse when
  11 // it encounters an invalid filter expression.
  12 var ErrBadFilter = errors.New("invalid query filter")
  13
  14 // Predicate represents a parsed filter predicate.
  15 type Predicate struct {
  16         expr          expr
  17         selectorTypes map[string]Type
  18         Parameters    int
  19 }
  20
  21 // String returns a cleaned, canonical representation of the
  22 // predicate.
  23 func (p Predicate) String() string {
  24         if p.expr == nil {
  25                 return ""
  26         }
  27         return p.expr.String()
  28 }
  29
  30 // MarshalText implements the encoding.TextMarshaler interface and
  31 // returns a cleaned, canonical representation of the predicate.
  32 func (p Predicate) MarshalText() ([]byte, error) {
  33         return []byte(p.expr.String()), nil
  34 }
  35
  36 // Parse parses a predicate and returns an internal representation of the
  37 // predicate or an error if it fails to parse.
  38 func Parse(predicate string, tbl *Table, vals []interface{}) (p Predicate, err error) {
  39         expr, parser, err := parse(predicate)
  40         if err != nil {
  41                 return p, errors.WithDetail(ErrBadFilter, err.Error())
  42         }
  43         selectorTypes, err := typeCheck(expr, tbl, vals)
  44         if err != nil {
  45                 return p, errors.WithDetail(ErrBadFilter, err.Error())
  46         }
  47
  48         return Predicate{
  49                 expr:          expr,
  50                 selectorTypes: selectorTypes,
  51                 Parameters:    parser.maxPlaceholder,
  52         }, nil
  53 }
  54
  55 // Field is a type for simple expressions that simply access an attribute of
  56 // the queried object. They're used for GROUP BYs.
  57 type Field struct {
  58         expr expr
  59 }
  60
  61 func (f Field) String() string {
  62         return f.expr.String()
  63 }
  64
  65 // ParseField parses a field expression (either an attrExpr or a selectorExpr).
  66 func ParseField(s string) (f Field, err error) {
  67         expr, _, err := parse(s)
  68         if err != nil {
  69                 return f, errors.WithDetail(ErrBadFilter, err.Error())
  70         }
  71         if expr == nil {
  72                 return f, errors.WithDetail(ErrBadFilter, "empty field expression")
  73         }
  74
  75         switch expr.(type) {
  76         case attrExpr, selectorExpr:
  77                 return Field{expr: expr}, nil
  78         default:
  79                 return f, errors.WithDetailf(ErrBadFilter, "%q is not a valid field expression", s)
  80         }
  81 }
  82
  83 func parse(exprString string) (expr expr, parser *parser, err error) {
  84         defer func() {
  85                 r := recover()
  86                 if perr, ok := r.(parseError); ok {
  87                         err = perr
  88                 } else if r != nil {
  89                         panic(r)
  90                 }
  91         }()
  92         parser = newParser([]byte(exprString))
  93
  94         // An empty expression is a valid predicate.
  95         if parser.tok == tokEOF {
  96                 return nil, parser, nil
  97         }
  98
  99         expr = parseExpr(parser)
 100         parser.parseTok(tokEOF)
 101         return expr, parser, err
 102 }
 103
 104 func newParser(src []byte) *parser {
 105         p := new(parser)
 106         p.scanner.init(src)
 107         p.next() // advance onto the first input token
 108         return p
 109 }
 110
 111 // The parser structure holds the parser's internal state.
 112 type parser struct {
 113         scanner scanner
 114
 115         maxPlaceholder int
 116
 117         // Current token
 118         pos int    // token position
 119         tok token  // one token look-ahead
 120         lit string // token literal
 121 }
 122
 123 func determineBinaryOp(p *parser, minPrecedence int) (op *binaryOp, ok bool) {
 124         op, ok = binaryOps[p.lit]
 125         return op, ok && op.precedence >= minPrecedence
 126 }
 127
 128 // next advances to the next token.
 129 func (p *parser) next() {
 130         p.pos, p.tok, p.lit = p.scanner.Scan()
 131 }
 132
 133 func (p *parser) parseLit(lit string) {
 134         if p.lit != lit {
 135                 p.errorf("got %s, expected %s", p.lit, lit)
 136         }
 137         p.next()
 138 }
 139
 140 func (p *parser) parseTok(tok token) {
 141         if p.tok != tok {
 142                 p.errorf("got %s, expected %s", p.lit, tok.String())
 143         }
 144         p.next()
 145 }
 146
 147 func parseExpr(p *parser) expr {
 148         // Uses the precedence-climbing algorithm:
 149         // https://en.wikipedia.org/wiki/Operator-precedence_parser#Precedence_climbing_method
 150         expr := parsePrimaryExpr(p)
 151         return parseExprCont(p, expr, 0)
 152 }
 153
 154 func parseExprCont(p *parser, lhs expr, minPrecedence int) expr {
 155         for {
 156                 op, ok := determineBinaryOp(p, minPrecedence)
 157                 if !ok {
 158                         break
 159                 }
 160                 p.next()
 161
 162                 rhs := parsePrimaryExpr(p)
 163
 164                 for {
 165                         op2, ok := determineBinaryOp(p, op.precedence+1)
 166                         if !ok {
 167                                 break
 168                         }
 169                         rhs = parseExprCont(p, rhs, op2.precedence)
 170                 }
 171                 lhs = binaryExpr{l: lhs, r: rhs, op: op}
 172         }
 173         return lhs
 174 }
 175
 176 func parsePrimaryExpr(p *parser) expr {
 177         x := parseOperand(p)
 178         for p.lit == "." {
 179                 x = parseSelectorExpr(p, x)
 180         }
 181         return x
 182 }
 183
 184 func parseOperand(p *parser) expr {
 185         switch {
 186         case p.lit == "(":
 187                 p.next()
 188                 expr := parseExpr(p)
 189                 p.parseLit(")")
 190                 return parenExpr{inner: expr}
 191         case p.tok == tokString:
 192                 v := valueExpr{typ: p.tok, value: p.lit}
 193                 p.next()
 194                 return v
 195         case p.tok == tokInteger:
 196                 // Parse the literal into an integer so that we store the string
 197                 // representation of the *decimal* value, never the hex.
 198                 integer, err := strconv.ParseInt(p.lit, 0, 64)
 199                 if err != nil {
 200                         // can't happen; scanner guarantees it
 201                         p.errorf("invalid integer: %q", p.lit)
 202                 }
 203                 v := valueExpr{typ: p.tok, value: strconv.Itoa(int(integer))}
 204                 p.next()
 205                 return v
 206         case p.tok == tokPlaceholder:
 207                 num, err := strconv.Atoi(p.lit[1:])
 208                 if err != nil || num <= 0 {
 209                         p.errorf("invalid placeholder: %q", p.lit)
 210                 }
 211                 v := placeholderExpr{num: num}
 212                 p.next()
 213
 214                 if num > p.maxPlaceholder {
 215                         p.maxPlaceholder = num
 216                 }
 217                 return v
 218         default:
 219                 return parseEnvironmentExpr(p)
 220         }
 221 }
 222
 223 func parseSelectorExpr(p *parser, objExpr expr) expr {
 224         p.next() // move past the '.'
 225
 226         ident := p.lit
 227         p.parseTok(tokIdent)
 228         return selectorExpr{
 229                 ident:   ident,
 230                 objExpr: objExpr,
 231         }
 232 }
 233
 234 func parseEnvironmentExpr(p *parser) expr {
 235         name := p.lit
 236         p.parseTok(tokIdent)
 237         if p.lit != "(" {
 238                 return attrExpr{attr: name}
 239         }
 240         p.next()
 241         expr := parseExpr(p)
 242         p.parseLit(")")
 243         return envExpr{
 244                 ident: name,
 245                 expr:  expr,
 246         }
 247 }
 248
 249 type parseError struct {
 250         pos int
 251         msg string
 252 }
 253
 254 func (err parseError) Error() string {
 255         return fmt.Sprintf("col %d: %s", err.pos, err.msg)
 256 }
 257
 258 func (p *parser) errorf(format string, args ...interface{}) {
 259         panic(parseError{pos: p.pos, msg: fmt.Sprintf(format, args...)})
 260 }