2 Copyright 2015 The Kubernetes Authors.
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
8 http://www.apache.org/licenses/LICENSE-2.0
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
47 ErrSyntax = errors.New("invalid syntax")
48 dictKeyRex = regexp.MustCompile(`^'([^']*)'$`)
49 sliceOperatorRex = regexp.MustCompile(`^(-?[\d]*)(:-?[\d]*)?(:[\d]*)?$`)
52 // Parse parsed the given text and return a node Parser.
53 // If an error is encountered, parsing stops and an empty
54 // Parser is returned with the error
55 func Parse(name, text string) (*Parser, error) {
64 func NewParser(name string) *Parser {
70 // parseAction parsed the expression inside delimiter
71 func parseAction(name, text string) (*Parser, error) {
72 p, err := Parse(name, fmt.Sprintf("%s%s%s", leftDelim, text, rightDelim))
73 // when error happens, p will be nil, so we need to return here
77 p.Root = p.Root.Nodes[0].(*ListNode)
81 func (p *Parser) Parse(text string) error {
85 return p.parseText(p.Root)
88 // consumeText return the parsed text since last cosumeText
89 func (p *Parser) consumeText() string {
90 value := p.input[p.start:p.pos]
95 // next returns the next rune in the input.
96 func (p *Parser) next() rune {
97 if p.pos >= len(p.input) {
101 r, w := utf8.DecodeRuneInString(p.input[p.pos:])
107 // peek returns but does not consume the next rune in the input.
108 func (p *Parser) peek() rune {
114 // backup steps back one rune. Can only be called once per call of next.
115 func (p *Parser) backup() {
119 func (p *Parser) parseText(cur *ListNode) error {
121 if strings.HasPrefix(p.input[p.pos:], leftDelim) {
123 cur.append(newText(p.consumeText()))
125 return p.parseLeftDelim(cur)
131 // Correctly reached EOF.
133 cur.append(newText(p.consumeText()))
138 // parseLeftDelim scans the left delimiter, which is known to be present.
139 func (p *Parser) parseLeftDelim(cur *ListNode) error {
140 p.pos += len(leftDelim)
145 return p.parseInsideAction(cur)
148 func (p *Parser) parseInsideAction(cur *ListNode) error {
149 prefixMap := map[string]func(*ListNode) error{
150 rightDelim: p.parseRightDelim,
151 "[?(": p.parseFilter,
152 "..": p.parseRecursive,
154 for prefix, parseFunc := range prefixMap {
155 if strings.HasPrefix(p.input[p.pos:], prefix) {
156 return parseFunc(cur)
160 switch r := p.next(); {
161 case r == eof || isEndOfLine(r):
162 return fmt.Errorf("unclosed action")
165 case r == '@' || r == '$': //the current object, just pass it
168 return p.parseArray(cur)
169 case r == '"' || r == '\'':
170 return p.parseQuote(cur, r)
172 return p.parseField(cur)
173 case r == '+' || r == '-' || unicode.IsDigit(r):
175 return p.parseNumber(cur)
176 case isAlphaNumeric(r):
178 return p.parseIdentifier(cur)
180 return fmt.Errorf("unrecognized character in action: %#U", r)
182 return p.parseInsideAction(cur)
185 // parseRightDelim scans the right delimiter, which is known to be present.
186 func (p *Parser) parseRightDelim(cur *ListNode) error {
187 p.pos += len(rightDelim)
190 return p.parseText(cur)
193 // parseIdentifier scans build-in keywords, like "range" "end"
194 func (p *Parser) parseIdentifier(cur *ListNode) error {
203 value := p.consumeText()
206 v, err := strconv.ParseBool(value)
208 return fmt.Errorf("can not parse bool '%s': %s", value, err.Error())
211 cur.append(newBool(v))
213 cur.append(newIdentifier(value))
216 return p.parseInsideAction(cur)
219 // parseRecursive scans the recursive desent operator ..
220 func (p *Parser) parseRecursive(cur *ListNode) error {
223 cur.append(newRecursive())
224 if r := p.peek(); isAlphaNumeric(r) {
225 return p.parseField(cur)
227 return p.parseInsideAction(cur)
230 // parseNumber scans number
231 func (p *Parser) parseNumber(cur *ListNode) error {
233 if r == '+' || r == '-' {
238 if r != '.' && !unicode.IsDigit(r) {
243 value := p.consumeText()
244 i, err := strconv.Atoi(value)
246 cur.append(newInt(i))
247 return p.parseInsideAction(cur)
249 d, err := strconv.ParseFloat(value, 64)
251 cur.append(newFloat(d))
252 return p.parseInsideAction(cur)
254 return fmt.Errorf("cannot parse number %s", value)
257 // parseArray scans array index selection
258 func (p *Parser) parseArray(cur *ListNode) error {
263 return fmt.Errorf("unterminated array")
268 text := p.consumeText()
269 text = text[1 : len(text)-1]
275 strs := strings.Split(text, ",")
277 union := []*ListNode{}
278 for _, str := range strs {
279 parser, err := parseAction("union", fmt.Sprintf("[%s]", strings.Trim(str, " ")))
283 union = append(union, parser.Root)
285 cur.append(newUnion(union))
286 return p.parseInsideAction(cur)
290 value := dictKeyRex.FindStringSubmatch(text)
292 parser, err := parseAction("arraydict", fmt.Sprintf(".%s", value[1]))
296 for _, node := range parser.Root.Nodes {
299 return p.parseInsideAction(cur)
303 value = sliceOperatorRex.FindStringSubmatch(text)
305 return fmt.Errorf("invalid array index %s", text)
308 params := [3]ParamsEntry{}
309 for i := 0; i < 3; i++ {
312 value[i] = value[i][1:]
314 if i > 0 && value[i] == "" {
315 params[i].Known = false
318 params[i].Known = true
319 params[i].Value, err = strconv.Atoi(value[i])
321 return fmt.Errorf("array index %s is not a number", value[i])
326 params[i].Known = true
327 params[i].Value = params[0].Value + 1
329 params[i].Known = false
334 cur.append(newArray(params))
335 return p.parseInsideAction(cur)
338 // parseFilter scans filter inside array selection
339 func (p *Parser) parseFilter(cur *ListNode) error {
351 return fmt.Errorf("unterminated filter")
354 //save the paired rune
359 //only add when met paired rune
360 if p.input[p.pos-2] != '\\' && r == pair {
364 //in rightParser below quotes only appear zero or once
365 //and must be paired at the beginning and end
372 return fmt.Errorf("unclosed array expect ]")
374 reg := regexp.MustCompile(`^([^!<>=]+)([!<>=]+)(.+?)$`)
375 text := p.consumeText()
376 text = text[:len(text)-2]
377 value := reg.FindStringSubmatch(text)
379 parser, err := parseAction("text", text)
383 cur.append(newFilter(parser.Root, newList(), "exists"))
385 leftParser, err := parseAction("left", value[1])
389 rightParser, err := parseAction("right", value[3])
393 cur.append(newFilter(leftParser.Root, rightParser.Root, value[2]))
395 return p.parseInsideAction(cur)
398 // parseQuote unquotes string inside double or single quote
399 func (p *Parser) parseQuote(cur *ListNode, end rune) error {
404 return fmt.Errorf("unterminated quoted string")
406 //if it's not escape break the Loop
407 if p.input[p.pos-2] != '\\' {
412 value := p.consumeText()
413 s, err := UnquoteExtend(value)
415 return fmt.Errorf("unquote string %s error %v", value, err)
417 cur.append(newText(s))
418 return p.parseInsideAction(cur)
421 // parseField scans a field until a terminator
422 func (p *Parser) parseField(cur *ListNode) error {
426 value := p.consumeText()
428 cur.append(newWildcard())
430 cur.append(newField(strings.Replace(value, "\\", "", -1)))
432 return p.parseInsideAction(cur)
435 // advance scans until next non-escaped terminator
436 func (p *Parser) advance() bool {
440 } else if isTerminator(r) {
447 // isTerminator reports whether the input is at valid termination character to appear after an identifier.
448 func isTerminator(r rune) bool {
449 if isSpace(r) || isEndOfLine(r) {
453 case eof, '.', ',', '[', ']', '$', '@', '{', '}':
459 // isSpace reports whether r is a space character.
460 func isSpace(r rune) bool {
461 return r == ' ' || r == '\t'
464 // isEndOfLine reports whether r is an end-of-line character.
465 func isEndOfLine(r rune) bool {
466 return r == '\r' || r == '\n'
469 // isAlphaNumeric reports whether r is an alphabetic, digit, or underscore.
470 func isAlphaNumeric(r rune) bool {
471 return r == '_' || unicode.IsLetter(r) || unicode.IsDigit(r)
474 // isBool reports whether s is a boolean value.
475 func isBool(s string) bool {
476 return s == "true" || s == "false"
479 //UnquoteExtend is almost same as strconv.Unquote(), but it support parse single quotes as a string
480 func UnquoteExtend(s string) (string, error) {
491 if quote != '"' && quote != '\'' {
495 // Is it trivial? Avoid allocation.
496 if !contains(s, '\\') && !contains(s, quote) {
500 var runeTmp [utf8.UTFMax]byte
501 buf := make([]byte, 0, 3*len(s)/2) // Try to avoid more allocations.
503 c, multibyte, ss, err := strconv.UnquoteChar(s, quote)
508 if c < utf8.RuneSelf || !multibyte {
509 buf = append(buf, byte(c))
511 n := utf8.EncodeRune(runeTmp[:], c)
512 buf = append(buf, runeTmp[:n]...)
515 return string(buf), nil
518 func contains(s string, c byte) bool {
519 for i := 0; i < len(s); i++ {