package jmespath
import (
"encoding/json"
"fmt"
"strconv"
"strings"
)
type astNodeType int
//go:generate stringer -type astNodeType
const (
ASTEmpty astNodeType = iota
ASTComparator
ASTCurrentNode
ASTExpRef
ASTFunctionExpression
ASTField
ASTFilterProjection
ASTFlatten
ASTIdentity
ASTIndex
ASTIndexExpression
ASTKeyValPair
ASTLiteral
ASTMultiSelectHash
ASTMultiSelectList
ASTOrExpression
ASTAndExpression
ASTNotExpression
ASTPipe
ASTProjection
ASTSubexpression
ASTSlice
ASTValueProjection
)
// ASTNode represents the abstract syntax tree of a JMESPath expression.
type ASTNode struct {
nodeType astNodeType
value interface{}
children []ASTNode
}
func (node ASTNode) String() string {
return node.PrettyPrint(0)
}
// PrettyPrint will pretty print the parsed AST.
// The AST is an implementation detail and this pretty print
// function is provided as a convenience method to help with
// debugging. You should not rely on its output as the internal
// structure of the AST may change at any time.
func (node ASTNode) PrettyPrint(indent int) string {
spaces := strings.Repeat(" ", indent)
output := fmt.Sprintf("%s%s {\n", spaces, node.nodeType)
nextIndent := indent + 2
if node.value != nil {
if converted, ok := node.value.(fmt.Stringer); ok {
// Account for things like comparator nodes
// that are enums with a String() method.
output += fmt.Sprintf("%svalue: %s\n", strings.Repeat(" ", nextIndent), converted.String())
} else {
output += fmt.Sprintf("%svalue: %#v\n", strings.Repeat(" ", nextIndent), node.value)
}
}
lastIndex := len(node.children)
if lastIndex > 0 {
output += fmt.Sprintf("%schildren: {\n", strings.Repeat(" ", nextIndent))
childIndent := nextIndent + 2
for _, elem := range node.children {
output += elem.PrettyPrint(childIndent)
}
}
output += fmt.Sprintf("%s}\n", spaces)
return output
}
var bindingPowers = map[tokType]int{
tEOF: 0,
tUnquotedIdentifier: 0,
tQuotedIdentifier: 0,
tRbracket: 0,
tRparen: 0,
tComma: 0,
tRbrace: 0,
tNumber: 0,
tCurrent: 0,
tExpref: 0,
tColon: 0,
tPipe: 1,
tOr: 2,
tAnd: 3,
tEQ: 5,
tLT: 5,
tLTE: 5,
tGT: 5,
tGTE: 5,
tNE: 5,
tFlatten: 9,
tStar: 20,
tFilter: 21,
tDot: 40,
tNot: 45,
tLbrace: 50,
tLbracket: 55,
tLparen: 60,
}
// Parser holds state about the current expression being parsed.
type Parser struct {
expression string
tokens []token
index int
}
// NewParser creates a new JMESPath parser.
func NewParser() *Parser {
p := Parser{}
return &p
}
// Parse will compile a JMESPath expression.
func (p *Parser) Parse(expression string) (ASTNode, error) {
lexer := NewLexer()
p.expression = expression
p.index = 0
tokens, err := lexer.tokenize(expression)
if err != nil {
return ASTNode{}, err
}
p.tokens = tokens
parsed, err := p.parseExpression(0)
if err != nil {
return ASTNode{}, err
}
if p.current() != tEOF {
return ASTNode{}, p.syntaxError(fmt.Sprintf(
"Unexpected token at the end of the expresssion: %s", p.current()))
}
return parsed, nil
}
func (p *Parser) parseExpression(bindingPower int) (ASTNode, error) {
var err error
leftToken := p.lookaheadToken(0)
p.advance()
leftNode, err := p.nud(leftToken)
if err != nil {
return ASTNode{}, err
}
currentToken := p.current()
for bindingPower < bindingPowers[currentToken] {
p.advance()
leftNode, err = p.led(currentToken, leftNode)
if err != nil {
return ASTNode{}, err
}
currentToken = p.current()
}
return leftNode, nil
}
func (p *Parser) parseIndexExpression() (ASTNode, error) {
if p.lookahead(0) == tColon || p.lookahead(1) == tColon {
return p.parseSliceExpression()
}
indexStr := p.lookaheadToken(0).value
parsedInt, err := strconv.Atoi(indexStr)
if err != nil {
return ASTNode{}, err
}
indexNode := ASTNode{nodeType: ASTIndex, value: parsedInt}
p.advance()
if err := p.match(tRbracket); err != nil {
return ASTNode{}, err
}
return indexNode, nil
}
func (p *Parser) parseSliceExpression() (ASTNode, error) {
parts := []*int{nil, nil, nil}
index := 0
current := p.current()
for current != tRbracket && index < 3 {
if current == tColon {
index++
p.advance()
} else if current == tNumber {
parsedInt, err := strconv.Atoi(p.lookaheadToken(0).value)
if err != nil {
return ASTNode{}, err
}
parts[index] = &parsedInt
p.advance()
} else {
return ASTNode{}, p.syntaxError(
"Expected tColon or tNumber" + ", received: " + p.current().String())
}
current = p.current()
}
if err := p.match(tRbracket); err != nil {
return ASTNode{}, err
}
return ASTNode{
nodeType: ASTSlice,
value: parts,
}, nil
}
func (p *Parser) match(tokenType tokType) error {
if p.current() == tokenType {
p.advance()
return nil
}
return p.syntaxError("Expected " + tokenType.String() + ", received: " + p.current().String())
}
func (p *Parser) led(tokenType tokType, node ASTNode) (ASTNode, error) {
switch tokenType {
case tDot:
if p.current() != tStar {
right, err := p.parseDotRHS(bindingPowers[tDot])
return ASTNode{
nodeType: ASTSubexpression,
children: []ASTNode{node, right},
}, err
}
p.advance()
right, err := p.parseProjectionRHS(bindingPowers[tDot])
return ASTNode{
nodeType: ASTValueProjection,
children: []ASTNode{node, right},
}, err
case tPipe:
right, err := p.parseExpression(bindingPowers[tPipe])
return ASTNode{nodeType: ASTPipe, children: []ASTNode{node, right}}, err
case tOr:
right, err := p.parseExpression(bindingPowers[tOr])
return ASTNode{nodeType: ASTOrExpression, children: []ASTNode{node, right}}, err
case tAnd:
right, err := p.parseExpression(bindingPowers[tAnd])
return ASTNode{nodeType: ASTAndExpression, children: []ASTNode{node, right}}, err
case tLparen:
name := node.value
var args []ASTNode
for p.current() != tRparen {
expression, err := p.parseExpression(0)
if err != nil {
return ASTNode{}, err
}
if p.current() == tComma {
if err := p.match(tComma); err != nil {
return ASTNode{}, err
}
}
args = append(args, expression)
}
if err := p.match(tRparen); err != nil {
return ASTNode{}, err
}
return ASTNode{
nodeType: ASTFunctionExpression,
value: name,
children: args,
}, nil
case tFilter:
return p.parseFilter(node)
case tFlatten:
left := ASTNode{nodeType: ASTFlatten, children: []ASTNode{node}}
right, err := p.parseProjectionRHS(bindingPowers[tFlatten])
return ASTNode{
nodeType: ASTProjection,
children: []ASTNode{left, right},
}, err
case tEQ, tNE, tGT, tGTE, tLT, tLTE:
right, err := p.parseExpression(bindingPowers[tokenType])
if err != nil {
return ASTNode{}, err
}
return ASTNode{
nodeType: ASTComparator,
value: tokenType,
children: []ASTNode{node, right},
}, nil
case tLbracket:
tokenType := p.current()
var right ASTNode
var err error
if tokenType == tNumber || tokenType == tColon {
right, err = p.parseIndexExpression()
if err != nil {
return ASTNode{}, err
}
return p.projectIfSlice(node, right)
}
// Otherwise this is a projection.
if err := p.match(tStar); err != nil {
return ASTNode{}, err
}
if err := p.match(tRbracket); err != nil {
return ASTNode{}, err
}
right, err = p.parseProjectionRHS(bindingPowers[tStar])
if err != nil {
return ASTNode{}, err
}
return ASTNode{
nodeType: ASTProjection,
children: []ASTNode{node, right},
}, nil
}
return ASTNode{}, p.syntaxError("Unexpected token: " + tokenType.String())
}
func (p *Parser) nud(token token) (ASTNode, error) {
switch token.tokenType {
case tJSONLiteral:
var parsed interface{}
err := json.Unmarshal([]byte(token.value), &parsed)
if err != nil {
return ASTNode{}, err
}
return ASTNode{nodeType: ASTLiteral, value: parsed}, nil
case tStringLiteral:
return ASTNode{nodeType: ASTLiteral, value: token.value}, nil
case tUnquotedIdentifier:
return ASTNode{
nodeType: ASTField,
value: token.value,
}, nil
case tQuotedIdentifier:
node := ASTNode{nodeType: ASTField, value: token.value}
if p.current() == tLparen {
return ASTNode{}, p.syntaxErrorToken("Can't have quoted identifier as function name.", token)
}
return node, nil
case tStar:
left := ASTNode{nodeType: ASTIdentity}
var right ASTNode
var err error
if p.current() == tRbracket {
right = ASTNode{nodeType: ASTIdentity}
} else {
right, err = p.parseProjectionRHS(bindingPowers[tStar])
}
return ASTNode{nodeType: ASTValueProjection, children: []ASTNode{left, right}}, err
case tFilter:
return p.parseFilter(ASTNode{nodeType: ASTIdentity})
case tLbrace:
return p.parseMultiSelectHash()
case tFlatten:
left := ASTNode{
nodeType: ASTFlatten,
children: []ASTNode{{nodeType: ASTIdentity}},
}
right, err := p.parseProjectionRHS(bindingPowers[tFlatten])
if err != nil {
return ASTNode{}, err
}
return ASTNode{nodeType: ASTProjection, children: []ASTNode{left, right}}, nil
case tLbracket:
tokenType := p.current()
//var right ASTNode
if tokenType == tNumber || tokenType == tColon {
right, err := p.parseIndexExpression()
if err != nil {
return ASTNode{}, nil
}
return p.projectIfSlice(ASTNode{nodeType: ASTIdentity}, right)
} else if tokenType == tStar && p.lookahead(1) == tRbracket {
p.advance()
p.advance()
right, err := p.parseProjectionRHS(bindingPowers[tStar])
if err != nil {
return ASTNode{}, err
}
return ASTNode{
nodeType: ASTProjection,
children: []ASTNode{{nodeType: ASTIdentity}, right},
}, nil
} else {
return p.parseMultiSelectList()
}
case tCurrent:
return ASTNode{nodeType: ASTCurrentNode}, nil
case tExpref:
expression, err := p.parseExpression(bindingPowers[tExpref])
if err != nil {
return ASTNode{}, err
}
return ASTNode{nodeType: ASTExpRef, children: []ASTNode{expression}}, nil
case tNot:
expression, err := p.parseExpression(bindingPowers[tNot])
if err != nil {
return ASTNode{}, err
}
return ASTNode{nodeType: ASTNotExpression, children: []ASTNode{expression}}, nil
case tLparen:
expression, err := p.parseExpression(0)
if err != nil {
return ASTNode{}, err
}
if err := p.match(tRparen); err != nil {
return ASTNode{}, err
}
return expression, nil
case tEOF:
return ASTNode{}, p.syntaxErrorToken("Incomplete expression", token)
}
return ASTNode{}, p.syntaxErrorToken("Invalid token: "+token.tokenType.String(), token)
}
func (p *Parser) parseMultiSelectList() (ASTNode, error) {
var expressions []ASTNode
for {
expression, err := p.parseExpression(0)
if err != nil {
return ASTNode{}, err
}
expressions = append(expressions, expression)
if p.current() == tRbracket {
break
}
err = p.match(tComma)
if err != nil {
return ASTNode{}, err
}
}
err := p.match(tRbracket)
if err != nil {
return ASTNode{}, err
}
return ASTNode{
nodeType: ASTMultiSelectList,
children: expressions,
}, nil
}
func (p *Parser) parseMultiSelectHash() (ASTNode, error) {
var children []ASTNode
for {
keyToken := p.lookaheadToken(0)
if err := p.match(tUnquotedIdentifier); err != nil {
if err := p.match(tQuotedIdentifier); err != nil {
return ASTNode{}, p.syntaxError("Expected tQuotedIdentifier or tUnquotedIdentifier")
}
}
keyName := keyToken.value
err := p.match(tColon)
if err != nil {
return ASTNode{}, err
}
value, err := p.parseExpression(0)
if err != nil {
return ASTNode{}, err
}
node := ASTNode{
nodeType: ASTKeyValPair,
value: keyName,
children: []ASTNode{value},
}
children = append(children, node)
if p.current() == tComma {
err := p.match(tComma)
if err != nil {
return ASTNode{}, nil
}
} else if p.current() == tRbrace {
err := p.match(tRbrace)
if err != nil {
return ASTNode{}, nil
}
break
}
}
return ASTNode{
nodeType: ASTMultiSelectHash,
children: children,
}, nil
}
func (p *Parser) projectIfSlice(left ASTNode, right ASTNode) (ASTNode, error) {
indexExpr := ASTNode{
nodeType: ASTIndexExpression,
children: []ASTNode{left, right},
}
if right.nodeType == ASTSlice {
right, err := p.parseProjectionRHS(bindingPowers[tStar])
return ASTNode{
nodeType: ASTProjection,
children: []ASTNode{indexExpr, right},
}, err
}
return indexExpr, nil
}
func (p *Parser) parseFilter(node ASTNode) (ASTNode, error) {
var right, condition ASTNode
var err error
condition, err = p.parseExpression(0)
if err != nil {
return ASTNode{}, err
}
if err := p.match(tRbracket); err != nil {
return ASTNode{}, err
}
if p.current() == tFlatten {
right = ASTNode{nodeType: ASTIdentity}
} else {
right, err = p.parseProjectionRHS(bindingPowers[tFilter])
if err != nil {
return ASTNode{}, err
}
}
return ASTNode{
nodeType: ASTFilterProjection,
children: []ASTNode{node, right, condition},
}, nil
}
func (p *Parser) parseDotRHS(bindingPower int) (ASTNode, error) {
lookahead := p.current()
if tokensOneOf([]tokType{tQuotedIdentifier, tUnquotedIdentifier, tStar}, lookahead) {
return p.parseExpression(bindingPower)
} else if lookahead == tLbracket {
if err := p.match(tLbracket); err != nil {
return ASTNode{}, err
}
return p.parseMultiSelectList()
} else if lookahead == tLbrace {
if err := p.match(tLbrace); err != nil {
return ASTNode{}, err
}
return p.parseMultiSelectHash()
}
return ASTNode{}, p.syntaxError("Expected identifier, lbracket, or lbrace")
}
func (p *Parser) parseProjectionRHS(bindingPower int) (ASTNode, error) {
current := p.current()
if bindingPowers[current] < 10 {
return ASTNode{nodeType: ASTIdentity}, nil
} else if current == tLbracket {
return p.parseExpression(bindingPower)
} else if current == tFilter {
return p.parseExpression(bindingPower)
} else if current == tDot {
err := p.match(tDot)
if err != nil {
return ASTNode{}, err
}
return p.parseDotRHS(bindingPower)
} else {
return ASTNode{}, p.syntaxError("Error")
}
}
func (p *Parser) lookahead(number int) tokType {
return p.lookaheadToken(number).tokenType
}
func (p *Parser) current() tokType {
return p.lookahead(0)
}
func (p *Parser) lookaheadToken(number int) token {
return p.tokens[p.index+number]
}
func (p *Parser) advance() {
p.index++
}
func tokensOneOf(elements []tokType, token tokType) bool {
for _, elem := range elements {
if elem == token {
return true
}
}
return false
}
func (p *Parser) syntaxError(msg string) SyntaxError {
return SyntaxError{
msg: msg,
Expression: p.expression,
Offset: p.lookaheadToken(0).position,
}
}
// Create a SyntaxError based on the provided token.
// This differs from syntaxError() which creates a SyntaxError
// based on the current lookahead token.
func (p *Parser) syntaxErrorToken(msg string, t token) SyntaxError {
return SyntaxError{
msg: msg,
Expression: p.expression,
Offset: t.position,
}
}