1/* 2 Based on the "jsonpath" spec/concept. 3 4 http://goessner.net/articles/JsonPath/ 5 https://code.google.com/p/json-path/ 6*/ 7 8package query 9 10import ( 11 "fmt" 12) 13 14const maxInt = int(^uint(0) >> 1) 15 16type queryParser struct { 17 flow chan token 18 tokensBuffer []token 19 query *Query 20 union []pathFn 21 err error 22} 23 24type queryParserStateFn func() queryParserStateFn 25 26// Formats and panics an error message based on a token 27func (p *queryParser) parseError(tok *token, msg string, args ...interface{}) queryParserStateFn { 28 p.err = fmt.Errorf(tok.Position.String()+": "+msg, args...) 29 return nil // trigger parse to end 30} 31 32func (p *queryParser) run() { 33 for state := p.parseStart; state != nil; { 34 state = state() 35 } 36} 37 38func (p *queryParser) backup(tok *token) { 39 p.tokensBuffer = append(p.tokensBuffer, *tok) 40} 41 42func (p *queryParser) peek() *token { 43 if len(p.tokensBuffer) != 0 { 44 return &(p.tokensBuffer[0]) 45 } 46 47 tok, ok := <-p.flow 48 if !ok { 49 return nil 50 } 51 p.backup(&tok) 52 return &tok 53} 54 55func (p *queryParser) lookahead(types ...tokenType) bool { 56 result := true 57 buffer := []token{} 58 59 for _, typ := range types { 60 tok := p.getToken() 61 if tok == nil { 62 result = false 63 break 64 } 65 buffer = append(buffer, *tok) 66 if tok.typ != typ { 67 result = false 68 break 69 } 70 } 71 // add the tokens back to the buffer, and return 72 p.tokensBuffer = append(p.tokensBuffer, buffer...) 73 return result 74} 75 76func (p *queryParser) getToken() *token { 77 if len(p.tokensBuffer) != 0 { 78 tok := p.tokensBuffer[0] 79 p.tokensBuffer = p.tokensBuffer[1:] 80 return &tok 81 } 82 tok, ok := <-p.flow 83 if !ok { 84 return nil 85 } 86 return &tok 87} 88 89func (p *queryParser) parseStart() queryParserStateFn { 90 tok := p.getToken() 91 92 if tok == nil || tok.typ == tokenEOF { 93 return nil 94 } 95 96 if tok.typ != tokenDollar { 97 return p.parseError(tok, "Expected '$' at start of expression") 98 } 99 100 return p.parseMatchExpr 101} 102 103// handle '.' prefix, '[]', and '..' 104func (p *queryParser) parseMatchExpr() queryParserStateFn { 105 tok := p.getToken() 106 switch tok.typ { 107 case tokenDotDot: 108 p.query.appendPath(&matchRecursiveFn{}) 109 // nested parse for '..' 110 tok := p.getToken() 111 switch tok.typ { 112 case tokenKey: 113 p.query.appendPath(newMatchKeyFn(tok.val)) 114 return p.parseMatchExpr 115 case tokenLeftBracket: 116 return p.parseBracketExpr 117 case tokenStar: 118 // do nothing - the recursive predicate is enough 119 return p.parseMatchExpr 120 } 121 122 case tokenDot: 123 // nested parse for '.' 124 tok := p.getToken() 125 switch tok.typ { 126 case tokenKey: 127 p.query.appendPath(newMatchKeyFn(tok.val)) 128 return p.parseMatchExpr 129 case tokenStar: 130 p.query.appendPath(&matchAnyFn{}) 131 return p.parseMatchExpr 132 } 133 134 case tokenLeftBracket: 135 return p.parseBracketExpr 136 137 case tokenEOF: 138 return nil // allow EOF at this stage 139 } 140 return p.parseError(tok, "expected match expression") 141} 142 143func (p *queryParser) parseBracketExpr() queryParserStateFn { 144 if p.lookahead(tokenInteger, tokenColon) { 145 return p.parseSliceExpr 146 } 147 if p.peek().typ == tokenColon { 148 return p.parseSliceExpr 149 } 150 return p.parseUnionExpr 151} 152 153func (p *queryParser) parseUnionExpr() queryParserStateFn { 154 var tok *token 155 156 // this state can be traversed after some sub-expressions 157 // so be careful when setting up state in the parser 158 if p.union == nil { 159 p.union = []pathFn{} 160 } 161 162loop: // labeled loop for easy breaking 163 for { 164 if len(p.union) > 0 { 165 // parse delimiter or terminator 166 tok = p.getToken() 167 switch tok.typ { 168 case tokenComma: 169 // do nothing 170 case tokenRightBracket: 171 break loop 172 default: 173 return p.parseError(tok, "expected ',' or ']', not '%s'", tok.val) 174 } 175 } 176 177 // parse sub expression 178 tok = p.getToken() 179 switch tok.typ { 180 case tokenInteger: 181 p.union = append(p.union, newMatchIndexFn(tok.Int())) 182 case tokenKey: 183 p.union = append(p.union, newMatchKeyFn(tok.val)) 184 case tokenString: 185 p.union = append(p.union, newMatchKeyFn(tok.val)) 186 case tokenQuestion: 187 return p.parseFilterExpr 188 default: 189 return p.parseError(tok, "expected union sub expression, not '%s', %d", tok.val, len(p.union)) 190 } 191 } 192 193 // if there is only one sub-expression, use that instead 194 if len(p.union) == 1 { 195 p.query.appendPath(p.union[0]) 196 } else { 197 p.query.appendPath(&matchUnionFn{p.union}) 198 } 199 200 p.union = nil // clear out state 201 return p.parseMatchExpr 202} 203 204func (p *queryParser) parseSliceExpr() queryParserStateFn { 205 // init slice to grab all elements 206 var start, end, step *int = nil, nil, nil 207 208 // parse optional start 209 tok := p.getToken() 210 if tok.typ == tokenInteger { 211 v := tok.Int() 212 start = &v 213 tok = p.getToken() 214 } 215 if tok.typ != tokenColon { 216 return p.parseError(tok, "expected ':'") 217 } 218 219 // parse optional end 220 tok = p.getToken() 221 if tok.typ == tokenInteger { 222 v := tok.Int() 223 end = &v 224 tok = p.getToken() 225 } 226 if tok.typ == tokenRightBracket { 227 p.query.appendPath(&matchSliceFn{Start: start, End: end, Step: step}) 228 return p.parseMatchExpr 229 } 230 if tok.typ != tokenColon { 231 return p.parseError(tok, "expected ']' or ':'") 232 } 233 234 // parse optional step 235 tok = p.getToken() 236 if tok.typ == tokenInteger { 237 v := tok.Int() 238 if v == 0 { 239 return p.parseError(tok, "step cannot be zero") 240 } 241 step = &v 242 tok = p.getToken() 243 } 244 if tok.typ != tokenRightBracket { 245 return p.parseError(tok, "expected ']'") 246 } 247 248 p.query.appendPath(&matchSliceFn{Start: start, End: end, Step: step}) 249 return p.parseMatchExpr 250} 251 252func (p *queryParser) parseFilterExpr() queryParserStateFn { 253 tok := p.getToken() 254 if tok.typ != tokenLeftParen { 255 return p.parseError(tok, "expected left-parenthesis for filter expression") 256 } 257 tok = p.getToken() 258 if tok.typ != tokenKey && tok.typ != tokenString { 259 return p.parseError(tok, "expected key or string for filter function name") 260 } 261 name := tok.val 262 tok = p.getToken() 263 if tok.typ != tokenRightParen { 264 return p.parseError(tok, "expected right-parenthesis for filter expression") 265 } 266 p.union = append(p.union, newMatchFilterFn(name, tok.Position)) 267 return p.parseUnionExpr 268} 269 270func parseQuery(flow chan token) (*Query, error) { 271 parser := &queryParser{ 272 flow: flow, 273 tokensBuffer: []token{}, 274 query: newQuery(), 275 } 276 parser.run() 277 return parser.query, parser.err 278} 279