/*
 * Copyright (c) 2015, 2018, Oracle and/or its affiliates. All rights reserved.
 *
 * This program is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License, version 2.0, as published by the
 * Free Software Foundation.
 *
 * This program is also distributed with certain software (including but not
 * limited to OpenSSL) that is licensed under separate terms, as designated in a
 * particular file or component or in included license documentation. The
 * authors of MySQL hereby grant you an additional permission to link the
 * program and your derivative works with the separately licensed software that
 * they have included with MySQL.
 *
 * Without limiting anything contained in the foregoing, this file, which is
 * part of MySQL Connector/J, is also subject to the Universal FOSS Exception,
 * version 1.0, a copy of which can be found at
 * http://oss.oracle.com/licenses/universal-foss-exception.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
 * for more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA
 */

package com.mysql.cj.xdevapi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.function.Supplier;

import com.mysql.cj.exceptions.WrongArgumentException;
import com.mysql.cj.x.protobuf.MysqlxCrud.Column;
import com.mysql.cj.x.protobuf.MysqlxCrud.Order;
import com.mysql.cj.x.protobuf.MysqlxCrud.Projection;
import com.mysql.cj.x.protobuf.MysqlxExpr.Array;
import com.mysql.cj.x.protobuf.MysqlxExpr.ColumnIdentifier;
import com.mysql.cj.x.protobuf.MysqlxExpr.DocumentPathItem;
import com.mysql.cj.x.protobuf.MysqlxExpr.Expr;
import com.mysql.cj.x.protobuf.MysqlxExpr.FunctionCall;
import com.mysql.cj.x.protobuf.MysqlxExpr.Identifier;
import com.mysql.cj.x.protobuf.MysqlxExpr.Object;
import com.mysql.cj.x.protobuf.MysqlxExpr.Object.ObjectField;
import com.mysql.cj.x.protobuf.MysqlxExpr.Operator;

// Grammar includes precedence & associativity of binary operators:
// (^ refers to the preceding production)
// (c.f. https://dev.mysql.com/doc/refman/5.7/en/operator-precedence.html)
//
// AtomicExpr: [Unary]OpExpr | Identifier | FunctionCall | '(' Expr ')'
//
// AddSubIntervalExpr: ^ (ADD/SUB ^)* | (ADD/SUB 'INTERVAL' ^ UNIT)*
//
// MulDivExpr: ^ (STAR/SLASH/MOD ^)*
//
// ShiftExpr: ^ (LSHIFT/RSHIFT ^)*
//
// BitExpr: ^ (BITAND/BITOR/BITXOR ^)*
//
// CompExpr: ^ (GE/GT/LE/LT/EQ/NE ^)*
//
// IlriExpr(ilri=IS/LIKE/REGEXP/IN/BETWEEN): ^ (ilri ^)
//
// AndExpr: ^ (AND ^)*
//
// OrExpr: ^ (OR ^)*
//
// Expr: ^
//
/**
 * Expression parser for X protocol.
 */
public class ExprParser {
    /** String being parsed. */
    String string;
    /** Token stream produced by lexer. */
    List<Token> tokens = new ArrayList<>();
    /** Parser's position in token stream. */
    int tokenPos = 0;
    /**
     * Mapping of names to positions for named placeholders. Used for both string values ":arg" and numeric values ":2".
     */
    Map<String, Integer> placeholderNameToPosition = new HashMap<>();
    /** Number of positional placeholders. */
    int positionalPlaceholderCount = 0;

    /** Are relational columns identifiers allowed? */
    private boolean allowRelationalColumns;

    public ExprParser(String s) {
        this(s, true);
    }

    public ExprParser(String s, boolean allowRelationalColumns) {
        this.string = s;
        lex();
        // java.util.stream.IntStream.range(0, this.tokens.size()).forEach(i -> System.err.println("[" + i + "] = " + this.tokens.get(i)));
        this.allowRelationalColumns = allowRelationalColumns;
    }

    /**
     * Token types used by the lexer.
     */
    private static enum TokenType {
        NOT, AND, ANDAND, OR, OROR, XOR, IS, LPAREN, RPAREN, LSQBRACKET, RSQBRACKET, BETWEEN, TRUE, NULL, FALSE, IN, LIKE, INTERVAL, REGEXP, ESCAPE, IDENT,
        LSTRING, LNUM_INT, LNUM_DOUBLE, DOT, DOLLAR, COMMA, EQ, NE, GT, GE, LT, LE, BITAND, BITOR, BITXOR, LSHIFT, RSHIFT, PLUS, MINUS, STAR, SLASH, HEX, BIN,
        NEG, BANG, EROTEME, MICROSECOND, SECOND, MINUTE, HOUR, DAY, WEEK, MONTH, QUARTER, YEAR, SECOND_MICROSECOND, MINUTE_MICROSECOND, MINUTE_SECOND,
        HOUR_MICROSECOND, HOUR_SECOND, HOUR_MINUTE, DAY_MICROSECOND, DAY_SECOND, DAY_MINUTE, DAY_HOUR, YEAR_MONTH, DOUBLESTAR, MOD, COLON, ORDERBY_ASC,
        ORDERBY_DESC, AS, LCURLY, RCURLY, DOTSTAR, CAST, DECIMAL, UNSIGNED, SIGNED, INTEGER, DATE, TIME, DATETIME, CHAR, BINARY, JSON, COLDOCPATH
    }

    /**
     * Token. Includes type and string value of the token.
     */
    static class Token {
        TokenType type;
        String value;

        public Token(TokenType x, char c) {
            this.type = x;
            this.value = new String(new char[] { c });
        }

        public Token(TokenType t, String v) {
            this.type = t;
            this.value = v;
        }

        @Override
        public String toString() {
            if (this.type == TokenType.IDENT || this.type == TokenType.LNUM_INT || this.type == TokenType.LNUM_DOUBLE || this.type == TokenType.LSTRING) {
                return this.type.toString() + "(" + this.value + ")";
            }
            return this.type.toString();
        }
    }

    /** Mapping of reserved words to token types. */
    static Map<String, TokenType> reservedWords = new HashMap<>();

    static {
        reservedWords.put("and", TokenType.AND);
        reservedWords.put("or", TokenType.OR);
        reservedWords.put("xor", TokenType.XOR);
        reservedWords.put("is", TokenType.IS);
        reservedWords.put("not", TokenType.NOT);
        reservedWords.put("like", TokenType.LIKE);
        reservedWords.put("in", TokenType.IN);
        reservedWords.put("regexp", TokenType.REGEXP);
        reservedWords.put("between", TokenType.BETWEEN);
        reservedWords.put("interval", TokenType.INTERVAL);
        reservedWords.put("escape", TokenType.ESCAPE);
        reservedWords.put("div", TokenType.SLASH);
        reservedWords.put("hex", TokenType.HEX);
        reservedWords.put("bin", TokenType.BIN);
        reservedWords.put("true", TokenType.TRUE);
        reservedWords.put("false", TokenType.FALSE);
        reservedWords.put("null", TokenType.NULL);
        reservedWords.put("microsecond", TokenType.MICROSECOND);
        reservedWords.put("second", TokenType.SECOND);
        reservedWords.put("minute", TokenType.MINUTE);
        reservedWords.put("hour", TokenType.HOUR);
        reservedWords.put("day", TokenType.DAY);
        reservedWords.put("week", TokenType.WEEK);
        reservedWords.put("month", TokenType.MONTH);
        reservedWords.put("quarter", TokenType.QUARTER);
        reservedWords.put("year", TokenType.YEAR);
        reservedWords.put("second_microsecond", TokenType.SECOND_MICROSECOND);
        reservedWords.put("minute_microsecond", TokenType.MINUTE_MICROSECOND);
        reservedWords.put("minute_second", TokenType.MINUTE_SECOND);
        reservedWords.put("hour_microsecond", TokenType.HOUR_MICROSECOND);
        reservedWords.put("hour_second", TokenType.HOUR_SECOND);
        reservedWords.put("hour_minute", TokenType.HOUR_MINUTE);
        reservedWords.put("day_microsecond", TokenType.DAY_MICROSECOND);
        reservedWords.put("day_second", TokenType.DAY_SECOND);
        reservedWords.put("day_minute", TokenType.DAY_MINUTE);
        reservedWords.put("day_hour", TokenType.DAY_HOUR);
        reservedWords.put("year_month", TokenType.YEAR_MONTH);
        reservedWords.put("asc", TokenType.ORDERBY_ASC);
        reservedWords.put("desc", TokenType.ORDERBY_DESC);
        reservedWords.put("as", TokenType.AS);
        reservedWords.put("cast", TokenType.CAST);
        reservedWords.put("decimal", TokenType.DECIMAL);
        reservedWords.put("unsigned", TokenType.UNSIGNED);
        reservedWords.put("signed", TokenType.SIGNED);
        reservedWords.put("integer", TokenType.INTEGER);
        reservedWords.put("date", TokenType.DATE);
        reservedWords.put("time", TokenType.TIME);
        reservedWords.put("datetime", TokenType.DATETIME);
        reservedWords.put("char", TokenType.CHAR);
        reservedWords.put("binary", TokenType.BINARY);
        reservedWords.put("json", TokenType.BINARY);
    }

    /**
     * Does the next character equal the given character? (respects bounds)
     * 
     * @param i
     *            The current position in the string
     * @param c
     *            character to compare with
     * @return true if equals
     */
    boolean nextCharEquals(int i, char c) {
        return (i + 1 < this.string.length()) && this.string.charAt(i + 1) == c;
    }

    /**
     * Helper function to match integer or floating point numbers. This function should be called when the position is on the first character of the number (a
     * digit or '.').
     *
     * @param i
     *            The current position in the string
     * @return the next position in the string after the number.
     */
    private int lexNumber(int i) {
        boolean isInt = true;
        char c;
        int start = i;
        for (; i < this.string.length(); ++i) {
            c = this.string.charAt(i);
            if (c == '.') {
                isInt = false;
            } else if (c == 'e' || c == 'E') {
                isInt = false;
                if (nextCharEquals(i, '-') || nextCharEquals(i, '+')) {
                    i++;
                }
            } else if (!Character.isDigit(c)) {
                break;
            }
        }
        if (isInt) {
            this.tokens.add(new Token(TokenType.LNUM_INT, this.string.substring(start, i)));
        } else {
            this.tokens.add(new Token(TokenType.LNUM_DOUBLE, this.string.substring(start, i)));
        }
        --i;
        return i;
    }

    /**
     * Lexer for X DevAPI expression language.
     */
    void lex() {
        for (int i = 0; i < this.string.length(); ++i) {
            int start = i; // for routines that consume more than one char
            char c = this.string.charAt(i);
            if (Character.isWhitespace(c)) {
                // ignore
            } else if (Character.isDigit(c)) {
                i = lexNumber(i);
            } else if (!(c == '_' || Character.isUnicodeIdentifierStart(c))) {
                // non-identifier, e.g. operator or quoted literal
                switch (c) {
                    case ':':
                        this.tokens.add(new Token(TokenType.COLON, c));
                        break;
                    case '+':
                        this.tokens.add(new Token(TokenType.PLUS, c));
                        break;
                    case '-':
                        if (nextCharEquals(i, '>')) {
                            i++;
                            this.tokens.add(new Token(TokenType.COLDOCPATH, "->"));
                        } else {
                            this.tokens.add(new Token(TokenType.MINUS, c));
                        }
                        break;
                    case '*':
                        if (nextCharEquals(i, '*')) {
                            i++;
                            this.tokens.add(new Token(TokenType.DOUBLESTAR, "**"));
                        } else {
                            this.tokens.add(new Token(TokenType.STAR, c));
                        }
                        break;
                    case '/':
                        this.tokens.add(new Token(TokenType.SLASH, c));
                        break;
                    case '$':
                        this.tokens.add(new Token(TokenType.DOLLAR, c));
                        break;
                    case '%':
                        this.tokens.add(new Token(TokenType.MOD, c));
                        break;
                    case '=':
                        if (nextCharEquals(i, '=')) {
                            i++;
                        }
                        this.tokens.add(new Token(TokenType.EQ, "=="));
                        break;
                    case '&':
                        if (nextCharEquals(i, '&')) {
                            i++;
                            this.tokens.add(new Token(TokenType.ANDAND, "&&"));
                        } else {
                            this.tokens.add(new Token(TokenType.BITAND, c));
                        }
                        break;
                    case '|':
                        if (nextCharEquals(i, '|')) {
                            i++;
                            this.tokens.add(new Token(TokenType.OROR, "||"));
                        } else {
                            this.tokens.add(new Token(TokenType.BITOR, c));
                        }
                        break;
                    case '^':
                        this.tokens.add(new Token(TokenType.BITXOR, c));
                        break;
                    case '(':
                        this.tokens.add(new Token(TokenType.LPAREN, c));
                        break;
                    case ')':
                        this.tokens.add(new Token(TokenType.RPAREN, c));
                        break;
                    case '[':
                        this.tokens.add(new Token(TokenType.LSQBRACKET, c));
                        break;
                    case ']':
                        this.tokens.add(new Token(TokenType.RSQBRACKET, c));
                        break;
                    case '{':
                        this.tokens.add(new Token(TokenType.LCURLY, c));
                        break;
                    case '}':
                        this.tokens.add(new Token(TokenType.RCURLY, c));
                        break;
                    case '~':
                        this.tokens.add(new Token(TokenType.NEG, c));
                        break;
                    case ',':
                        this.tokens.add(new Token(TokenType.COMMA, c));
                        break;
                    case '!':
                        if (nextCharEquals(i, '=')) {
                            i++;
                            this.tokens.add(new Token(TokenType.NE, "!="));
                        } else {
                            this.tokens.add(new Token(TokenType.BANG, c));
                        }
                        break;
                    case '?':
                        this.tokens.add(new Token(TokenType.EROTEME, c));
                        break;
                    case '<':
                        if (nextCharEquals(i, '<')) {
                            i++;
                            this.tokens.add(new Token(TokenType.LSHIFT, "<<"));
                        } else if (nextCharEquals(i, '=')) {
                            i++;
                            this.tokens.add(new Token(TokenType.LE, "<="));
                        } else {
                            this.tokens.add(new Token(TokenType.LT, c));
                        }
                        break;
                    case '>':
                        if (nextCharEquals(i, '>')) {
                            i++;
                            this.tokens.add(new Token(TokenType.RSHIFT, ">>"));
                        } else if (nextCharEquals(i, '=')) {
                            i++;
                            this.tokens.add(new Token(TokenType.GE, ">="));
                        } else {
                            this.tokens.add(new Token(TokenType.GT, c));
                        }
                        break;
                    case '.':
                        if (nextCharEquals(i, '*')) {
                            i++;
                            this.tokens.add(new Token(TokenType.DOTSTAR, ".*"));
                        } else if (i + 1 < this.string.length() && Character.isDigit(this.string.charAt(i + 1))) {
                            i = lexNumber(i);
                        } else {
                            this.tokens.add(new Token(TokenType.DOT, c));
                        }
                        break;
                    case '"':
                    case '\'':
                    case '`':
                        char quoteChar = c;
                        StringBuilder val = new StringBuilder();
                        try {
                            for (c = this.string.charAt(++i); c != quoteChar
                                    || (i + 1 < this.string.length() && this.string.charAt(i + 1) == quoteChar); c = this.string.charAt(++i)) {
                                if (c == '\\' || c == quoteChar) {
                                    ++i;
                                }
                                val.append(this.string.charAt(i));
                            }
                        } catch (StringIndexOutOfBoundsException ex) {
                            throw new WrongArgumentException("Unterminated string starting at " + start);
                        }
                        this.tokens.add(new Token(quoteChar == '`' ? TokenType.IDENT : TokenType.LSTRING, val.toString()));
                        break;
                    default:
                        throw new WrongArgumentException("Can't parse at pos: " + i);
                }
            } else {
                // otherwise, it's an identifier
                for (; i < this.string.length() && Character.isUnicodeIdentifierPart(this.string.charAt(i)); ++i) {
                }
                String val = this.string.substring(start, i);
                String valLower = val.toLowerCase();
                if (i < this.string.length()) {
                    // last char, this logic is artifact of the preceding loop
                    --i;
                }
                if (reservedWords.containsKey(valLower)) {
                    // Map operator names to values the server understands
                    if ("and".equals(valLower)) {
                        this.tokens.add(new Token(reservedWords.get(valLower), "&&"));
                    } else if ("or".equals(valLower)) {
                        this.tokens.add(new Token(reservedWords.get(valLower), "||"));
                    } else {
                        // we case-normalize reserved words
                        this.tokens.add(new Token(reservedWords.get(valLower), valLower));
                    }
                } else {
                    this.tokens.add(new Token(TokenType.IDENT, val));
                }
            }
        }
    }

    /**
     * Assert that the token at <i>pos</i> is of type <i>type</i>.
     * 
     * @param pos
     *            The current position in the string
     * @param type
     *            {@link TokenType}
     */
    void assertTokenAt(int pos, TokenType type) {
        if (this.tokens.size() <= pos) {
            throw new WrongArgumentException("No more tokens when expecting " + type + " at token pos " + pos);
        }
        if (this.tokens.get(pos).type != type) {
            throw new WrongArgumentException("Expected token type " + type + " at token pos " + pos);
        }
    }

    /**
     * Does the current token have type `t'?
     * 
     * @param t
     *            {@link TokenType}
     * @return true if equals
     */
    boolean currentTokenTypeEquals(TokenType t) {
        return posTokenTypeEquals(this.tokenPos, t);
    }

    /**
     * Does the next token have type `t'?
     * 
     * @param t
     *            {@link TokenType}
     * @return true if equals
     */
    boolean nextTokenTypeEquals(TokenType t) {
        return posTokenTypeEquals(this.tokenPos + 1, t);
    }

    /**
     * Does the token at position `pos' have type `t'?
     * 
     * @param pos
     *            The current position in the string
     * @param t
     *            {@link TokenType}
     * @return true if equals
     */
    boolean posTokenTypeEquals(int pos, TokenType t) {
        return this.tokens.size() > pos && this.tokens.get(pos).type == t;
    }

    /**
     * Consume token.
     *
     * @param t
     *            {@link TokenType}
     * @return the string value of the consumed token
     */
    String consumeToken(TokenType t) {
        assertTokenAt(this.tokenPos, t);
        String value = this.tokens.get(this.tokenPos).value;
        this.tokenPos++;
        return value;
    }

    /**
     * Parse a paren-enclosed expression list. This is used for function params or IN params.
     *
     * @return a List of expressions
     */
    List<Expr> parenExprList() {
        List<Expr> exprs = new ArrayList<>();
        consumeToken(TokenType.LPAREN);
        if (!currentTokenTypeEquals(TokenType.RPAREN)) {
            exprs.add(expr());
            while (currentTokenTypeEquals(TokenType.COMMA)) {
                consumeToken(TokenType.COMMA);
                exprs.add(expr());
            }
        }
        consumeToken(TokenType.RPAREN);
        return exprs;
    }

    /**
     * Parse a function call of the form: IDENTIFIER PAREN_EXPR_LIST.
     *
     * @return an Expr representing the function call.
     */
    Expr functionCall() {
        Identifier id = identifier();
        FunctionCall.Builder b = FunctionCall.newBuilder();
        b.setName(id);
        b.addAllParam(parenExprList());
        return Expr.newBuilder().setType(Expr.Type.FUNC_CALL).setFunctionCall(b.build()).build();
    }

    Expr starOperator() {
        Operator op = Operator.newBuilder().setName("*").build();
        return Expr.newBuilder().setType(Expr.Type.OPERATOR).setOperator(op).build();
    }

    /**
     * Parse an identifier for a function call: [schema.]name
     * 
     * @return {@link Identifier}
     */
    Identifier identifier() {
        Identifier.Builder builder = Identifier.newBuilder();
        assertTokenAt(this.tokenPos, TokenType.IDENT);
        if (nextTokenTypeEquals(TokenType.DOT)) {
            builder.setSchemaName(this.tokens.get(this.tokenPos).value);
            consumeToken(TokenType.IDENT);
            consumeToken(TokenType.DOT);
            assertTokenAt(this.tokenPos, TokenType.IDENT);
        }
        builder.setName(this.tokens.get(this.tokenPos).value);
        consumeToken(TokenType.IDENT);
        return builder.build();
    }

    /**
     * Parse a document path member.
     * 
     * @return {@link DocumentPathItem}
     */
    DocumentPathItem docPathMember() {
        consumeToken(TokenType.DOT);
        Token t = this.tokens.get(this.tokenPos);
        String memberName;
        if (currentTokenTypeEquals(TokenType.IDENT)) {
            // this shouldn't be allowed to be quoted with backticks, but the lexer allows it
            if (!t.value.equals(ExprUnparser.quoteIdentifier(t.value))) {
                throw new WrongArgumentException("'" + t.value + "' is not a valid JSON/ECMAScript identifier");
            }
            consumeToken(TokenType.IDENT);
            memberName = t.value;
        } else if (currentTokenTypeEquals(TokenType.LSTRING)) {
            consumeToken(TokenType.LSTRING);
            memberName = t.value;
        } else {
            throw new WrongArgumentException("Expected token type IDENT or LSTRING in JSON path at token pos " + this.tokenPos);
        }
        DocumentPathItem.Builder item = DocumentPathItem.newBuilder();
        item.setType(DocumentPathItem.Type.MEMBER);
        item.setValue(memberName);
        return item.build();
    }

    /**
     * Parse a document path array index.
     * 
     * @return {@link DocumentPathItem}
     */
    DocumentPathItem docPathArrayLoc() {
        DocumentPathItem.Builder builder = DocumentPathItem.newBuilder();
        consumeToken(TokenType.LSQBRACKET);
        if (currentTokenTypeEquals(TokenType.STAR)) {
            consumeToken(TokenType.STAR);
            consumeToken(TokenType.RSQBRACKET);
            return builder.setType(DocumentPathItem.Type.ARRAY_INDEX_ASTERISK).build();
        } else if (currentTokenTypeEquals(TokenType.LNUM_INT)) {
            Integer v = Integer.valueOf(this.tokens.get(this.tokenPos).value);
            if (v < 0) {
                throw new WrongArgumentException("Array index cannot be negative at " + this.tokenPos);
            }
            consumeToken(TokenType.LNUM_INT);
            consumeToken(TokenType.RSQBRACKET);
            return builder.setType(DocumentPathItem.Type.ARRAY_INDEX).setIndex(v).build();
        } else {
            throw new WrongArgumentException("Expected token type STAR or LNUM_INT in JSON path array index at token pos " + this.tokenPos);
        }
    }

    /**
     * Parse a JSON-style document path, like WL#7909, but prefix by @. instead of $.
     * 
     * @return list of {@link DocumentPathItem} objects
     */
    public List<DocumentPathItem> documentPath() {
        List<DocumentPathItem> items = new ArrayList<>();
        while (true) {
            if (currentTokenTypeEquals(TokenType.DOT)) {
                items.add(docPathMember());
            } else if (currentTokenTypeEquals(TokenType.DOTSTAR)) {
                consumeToken(TokenType.DOTSTAR);
                items.add(DocumentPathItem.newBuilder().setType(DocumentPathItem.Type.MEMBER_ASTERISK).build());
            } else if (currentTokenTypeEquals(TokenType.LSQBRACKET)) {
                items.add(docPathArrayLoc());
            } else if (currentTokenTypeEquals(TokenType.DOUBLESTAR)) {
                consumeToken(TokenType.DOUBLESTAR);
                items.add(DocumentPathItem.newBuilder().setType(DocumentPathItem.Type.DOUBLE_ASTERISK).build());
            } else {
                break;
            }
        }
        if (items.size() > 0 && items.get(items.size() - 1).getType() == DocumentPathItem.Type.DOUBLE_ASTERISK) {
            throw new WrongArgumentException("JSON path may not end in '**' at " + this.tokenPos);
        }
        return items;
    }

    /**
     * Parse a document field.
     * 
     * @return {@link Expr}
     */
    public Expr documentField() {
        ColumnIdentifier.Builder builder = ColumnIdentifier.newBuilder();
        if (currentTokenTypeEquals(TokenType.IDENT)) {
            builder.addDocumentPath(DocumentPathItem.newBuilder().setType(DocumentPathItem.Type.MEMBER).setValue(consumeToken(TokenType.IDENT)).build());
        }
        builder.addAllDocumentPath(documentPath());
        return Expr.newBuilder().setType(Expr.Type.IDENT).setIdentifier(builder.build()).build();
    }

    /**
     * Parse a column identifier (which may optionally include a JSON document path).
     * 
     * @return {@link Expr}
     */
    Expr columnIdentifier() {
        List<String> parts = new LinkedList<>();
        parts.add(consumeToken(TokenType.IDENT));
        while (currentTokenTypeEquals(TokenType.DOT)) {
            consumeToken(TokenType.DOT);
            parts.add(consumeToken(TokenType.IDENT));
            // identifier can be at most three parts
            if (parts.size() == 3) {
                break;
            }
        }
        Collections.reverse(parts);
        ColumnIdentifier.Builder id = ColumnIdentifier.newBuilder();
        for (int i = 0; i < parts.size(); ++i) {
            switch (i) {
                case 0:
                    id.setName(parts.get(0));
                    break;
                case 1:
                    id.setTableName(parts.get(1));
                    break;
                case 2:
                    id.setSchemaName(parts.get(2));
                    break;
            }
        }
        if (currentTokenTypeEquals(TokenType.COLDOCPATH)) {
            consumeToken(TokenType.COLDOCPATH);
            if (currentTokenTypeEquals(TokenType.DOLLAR)) {
                consumeToken(TokenType.DOLLAR);
                id.addAllDocumentPath(documentPath());
            } else if (currentTokenTypeEquals(TokenType.LSTRING)) {
                String path = consumeToken(TokenType.LSTRING);
                if (path.charAt(0) != '$') {
                    throw new WrongArgumentException("Invalid document path at " + this.tokenPos);
                }
                id.addAllDocumentPath(new ExprParser(path.substring(1, path.length())).documentPath());
            }
            if (id.getDocumentPathCount() == 0) {
                throw new WrongArgumentException("Invalid document path at " + this.tokenPos);
            }
        }
        return Expr.newBuilder().setType(Expr.Type.IDENT).setIdentifier(id.build()).build();
    }

    /**
     * Build a unary operator expression.
     * 
     * @param name
     *            operator name
     * @param param
     *            operator parameter
     * @return {@link Expr}
     */
    Expr buildUnaryOp(String name, Expr param) {
        Operator op = Operator.newBuilder().setName(name).addParam(param).build();
        return Expr.newBuilder().setType(Expr.Type.OPERATOR).setOperator(op).build();
    }

    /**
     * Parse an atomic expression. (c.f. grammar at top)
     * 
     * @return {@link Expr}
     */
    Expr atomicExpr() { // constant, identifier, variable, function call, etc
        if (this.tokenPos >= this.tokens.size()) {
            throw new WrongArgumentException("No more tokens when expecting one at token pos " + this.tokenPos);
        }
        Token t = this.tokens.get(this.tokenPos);
        this.tokenPos++; // consume
        switch (t.type) {
            case EROTEME:
            case COLON: {
                String placeholderName;
                if (currentTokenTypeEquals(TokenType.LNUM_INT)) {
                    // int pos = Integer.valueOf(consumeToken(TokenType.LNUM_INT));
                    // return Expr.newBuilder().setType(Expr.Type.PLACEHOLDER).setPosition(pos).build();
                    placeholderName = consumeToken(TokenType.LNUM_INT);
                } else if (currentTokenTypeEquals(TokenType.IDENT)) {
                    placeholderName = consumeToken(TokenType.IDENT);
                } else if (t.type == TokenType.EROTEME) {
                    placeholderName = String.valueOf(this.positionalPlaceholderCount);
                } else {
                    throw new WrongArgumentException("Invalid placeholder name at token pos " + this.tokenPos);
                }
                Expr.Builder placeholder = Expr.newBuilder().setType(Expr.Type.PLACEHOLDER);
                if (this.placeholderNameToPosition.containsKey(placeholderName)) {
                    placeholder.setPosition(this.placeholderNameToPosition.get(placeholderName));
                } else {
                    placeholder.setPosition(this.positionalPlaceholderCount);
                    this.placeholderNameToPosition.put(placeholderName, this.positionalPlaceholderCount);
                    this.positionalPlaceholderCount++;
                }
                return placeholder.build();
            }
            case LPAREN: {
                Expr e = expr();
                consumeToken(TokenType.RPAREN);
                return e;
            }
            case LCURLY: { // JSON object
                Object.Builder builder = Object.newBuilder();
                if (currentTokenTypeEquals(TokenType.LSTRING)) {
                    parseCommaSeparatedList(() -> {
                        String key = consumeToken(TokenType.LSTRING);
                        consumeToken(TokenType.COLON);
                        Expr value = expr();
                        return Collections.singletonMap(key, value);
                    }).stream().map(pair -> pair.entrySet().iterator().next()).map(e -> ObjectField.newBuilder().setKey(e.getKey()).setValue(e.getValue()))
                            .forEach(builder::addFld);
                }
                consumeToken(TokenType.RCURLY);
                return Expr.newBuilder().setType(Expr.Type.OBJECT).setObject(builder.build()).build();
            }
            case LSQBRACKET: { // Array
                Array.Builder builder = Expr.newBuilder().setType(Expr.Type.ARRAY).getArrayBuilder();
                parseCommaSeparatedList(() -> {
                    return expr();
                }).stream().forEach(builder::addValue);

                consumeToken(TokenType.RSQBRACKET);
                return Expr.newBuilder().setType(Expr.Type.ARRAY).setArray(builder).build();
            }
            case CAST: {
                consumeToken(TokenType.LPAREN);
                Operator.Builder builder = Operator.newBuilder().setName(TokenType.CAST.toString().toLowerCase());
                builder.addParam(expr());
                consumeToken(TokenType.AS);
                StringBuilder typeStr = new StringBuilder(this.tokens.get(this.tokenPos).value.toUpperCase());
                // ensure next token is a valid type argument to CAST
                if (currentTokenTypeEquals(TokenType.DECIMAL)) {
                    this.tokenPos++;
                    if (currentTokenTypeEquals(TokenType.LPAREN)) {
                        typeStr.append(consumeToken(TokenType.LPAREN));
                        typeStr.append(consumeToken(TokenType.LNUM_INT));
                        if (currentTokenTypeEquals(TokenType.COMMA)) {
                            typeStr.append(consumeToken(TokenType.COMMA));
                            typeStr.append(consumeToken(TokenType.LNUM_INT));
                        }
                        typeStr.append(consumeToken(TokenType.RPAREN));
                    }
                } else if (currentTokenTypeEquals(TokenType.CHAR) || currentTokenTypeEquals(TokenType.BINARY)) {
                    this.tokenPos++;
                    if (currentTokenTypeEquals(TokenType.LPAREN)) {
                        typeStr.append(consumeToken(TokenType.LPAREN));
                        typeStr.append(consumeToken(TokenType.LNUM_INT));
                        typeStr.append(consumeToken(TokenType.RPAREN));
                    }
                } else if (currentTokenTypeEquals(TokenType.UNSIGNED) || currentTokenTypeEquals(TokenType.SIGNED)) {
                    this.tokenPos++;
                    if (currentTokenTypeEquals(TokenType.INTEGER)) {
                        // don't add optional INTEGER to type string argument
                        consumeToken(TokenType.INTEGER);
                    }
                } else if (currentTokenTypeEquals(TokenType.JSON) || currentTokenTypeEquals(TokenType.DATE) || currentTokenTypeEquals(TokenType.DATETIME)
                        || currentTokenTypeEquals(TokenType.TIME)) {
                    this.tokenPos++;
                } else {
                    throw new WrongArgumentException("Expected valid CAST type argument at " + this.tokenPos);
                }
                consumeToken(TokenType.RPAREN);
                // TODO charset?
                builder.addParam(ExprUtil.buildLiteralScalar(typeStr.toString().getBytes()));
                return Expr.newBuilder().setType(Expr.Type.OPERATOR).setOperator(builder.build()).build();
            }
            case PLUS:
            case MINUS:
                if (currentTokenTypeEquals(TokenType.LNUM_INT) || currentTokenTypeEquals(TokenType.LNUM_DOUBLE)) {
                    // unary operators are handled inline making positive or negative numeric literals
                    this.tokens.get(this.tokenPos).value = t.value + this.tokens.get(this.tokenPos).value;
                    return atomicExpr();
                }
                return buildUnaryOp(t.value, atomicExpr());

            case NOT:
            case NEG:
            case BANG:
                return buildUnaryOp(t.value, atomicExpr());
            case LSTRING:
                return ExprUtil.buildLiteralScalar(t.value);
            case NULL:
                return ExprUtil.buildLiteralNullScalar();
            case LNUM_INT:
                return ExprUtil.buildLiteralScalar(Long.valueOf(t.value));
            case LNUM_DOUBLE:
                return ExprUtil.buildLiteralScalar(Double.valueOf(t.value));
            case TRUE:
            case FALSE:
                return ExprUtil.buildLiteralScalar(t.type == TokenType.TRUE);
            case DOLLAR:
                return documentField();
            case STAR:
                // special "0-ary" consideration of "*" as an operator (for COUNT(*), etc)
                return starOperator();
            case IDENT:
                this.tokenPos--; // stay on the identifier
                // check for function call which may be: func(...) or schema.func(...)
                if (nextTokenTypeEquals(TokenType.LPAREN) || (posTokenTypeEquals(this.tokenPos + 1, TokenType.DOT)
                        && posTokenTypeEquals(this.tokenPos + 2, TokenType.IDENT) && posTokenTypeEquals(this.tokenPos + 3, TokenType.LPAREN))) {
                    return functionCall();
                }
                if (this.allowRelationalColumns) {
                    return columnIdentifier();
                }
                return documentField();
            default:
                break;
        }
        throw new WrongArgumentException("Cannot find atomic expression at token pos: " + (this.tokenPos - 1));
    }

    /**
     * An expression parser. (used in {@link #parseLeftAssocBinaryOpExpr(TokenType[], ParseExpr)})
     */
    @FunctionalInterface
    static interface ParseExpr {
        Expr parseExpr();
    }

    /**
     * Parse a left-associated binary operator.
     *
     * @param types
     *            The token types that denote this operator.
     * @param innerParser
     *            The inner parser that should be called to parse operands.
     * @return an expression tree of the binary operator or a single operand
     */
    Expr parseLeftAssocBinaryOpExpr(TokenType[] types, ParseExpr innerParser) {
        Expr lhs = innerParser.parseExpr();
        while (this.tokenPos < this.tokens.size() && Arrays.asList(types).contains(this.tokens.get(this.tokenPos).type)) {
            Operator.Builder builder = Operator.newBuilder().setName(this.tokens.get(this.tokenPos).value).addParam(lhs);
            this.tokenPos++;
            builder.addParam(innerParser.parseExpr());
            lhs = Expr.newBuilder().setType(Expr.Type.OPERATOR).setOperator(builder.build()).build();
        }
        return lhs;
    }

    Expr addSubIntervalExpr() {
        Expr lhs = atomicExpr();
        while ((currentTokenTypeEquals(TokenType.PLUS) || currentTokenTypeEquals(TokenType.MINUS)) && nextTokenTypeEquals(TokenType.INTERVAL)) {
            Token op = this.tokens.get(this.tokenPos);
            this.tokenPos++;
            Operator.Builder builder = Operator.newBuilder().addParam(unquoteWorkaround(lhs));

            // INTERVAL expression
            consumeToken(TokenType.INTERVAL);

            if (op.type == TokenType.PLUS) {
                builder.setName("date_add");
            } else {
                builder.setName("date_sub");
            }

            builder.addParam(unquoteWorkaround(bitExpr())); // amount

            // ensure next token is an interval unit
            if (currentTokenTypeEquals(TokenType.MICROSECOND) || currentTokenTypeEquals(TokenType.SECOND) || currentTokenTypeEquals(TokenType.MINUTE)
                    || currentTokenTypeEquals(TokenType.HOUR) || currentTokenTypeEquals(TokenType.DAY) || currentTokenTypeEquals(TokenType.WEEK)
                    || currentTokenTypeEquals(TokenType.MONTH) || currentTokenTypeEquals(TokenType.QUARTER) || currentTokenTypeEquals(TokenType.YEAR)
                    || currentTokenTypeEquals(TokenType.SECOND_MICROSECOND) || currentTokenTypeEquals(TokenType.MINUTE_MICROSECOND)
                    || currentTokenTypeEquals(TokenType.MINUTE_SECOND) || currentTokenTypeEquals(TokenType.HOUR_MICROSECOND)
                    || currentTokenTypeEquals(TokenType.HOUR_SECOND) || currentTokenTypeEquals(TokenType.HOUR_MINUTE)
                    || currentTokenTypeEquals(TokenType.DAY_MICROSECOND) || currentTokenTypeEquals(TokenType.DAY_SECOND)
                    || currentTokenTypeEquals(TokenType.DAY_MINUTE) || currentTokenTypeEquals(TokenType.DAY_HOUR)
                    || currentTokenTypeEquals(TokenType.YEAR_MONTH)) {
            } else {
                throw new WrongArgumentException("Expected interval units at " + this.tokenPos);
            }
            // xplugin demands that intervals be sent uppercase
            // TODO: we need to propagate the appropriate encoding here? it's ascii but it might not *always* be a superset encoding??
            builder.addParam(ExprUtil.buildLiteralScalar(this.tokens.get(this.tokenPos).value.toUpperCase().getBytes()));
            this.tokenPos++;

            lhs = Expr.newBuilder().setType(Expr.Type.OPERATOR).setOperator(builder.build()).build();
        }
        return lhs;
    }

    Expr mulDivExpr() {
        return parseLeftAssocBinaryOpExpr(new TokenType[] { TokenType.STAR, TokenType.SLASH, TokenType.MOD }, this::addSubIntervalExpr);
    }

    Expr addSubExpr() {
        return parseLeftAssocBinaryOpExpr(new TokenType[] { TokenType.PLUS, TokenType.MINUS }, this::mulDivExpr);
    }

    Expr shiftExpr() {
        return parseLeftAssocBinaryOpExpr(new TokenType[] { TokenType.LSHIFT, TokenType.RSHIFT }, this::addSubExpr);
    }

    Expr bitExpr() {
        return parseLeftAssocBinaryOpExpr(new TokenType[] { TokenType.BITAND, TokenType.BITOR, TokenType.BITXOR }, this::shiftExpr);
    }

    Expr compExpr() {
        return parseLeftAssocBinaryOpExpr(new TokenType[] { TokenType.GE, TokenType.GT, TokenType.LE, TokenType.LT, TokenType.EQ, TokenType.NE },
                this::bitExpr);
    }

    /**
     * Workaround for improper comparisons in the server. (lack of JSON_UNQUOTE())
     * 
     * @param e
     *            {@link Expr}
     * @return {@link Expr}
     */
    private Expr unquoteWorkaround(Expr e) {
        if (e.getType() == Expr.Type.IDENT && e.getIdentifier().getDocumentPathList().size() > 0) {
            Identifier id = Identifier.newBuilder().setName("JSON_UNQUOTE").build();
            FunctionCall.Builder b = FunctionCall.newBuilder().setName(id).addParam(e);
            return Expr.newBuilder().setType(Expr.Type.FUNC_CALL).setFunctionCall(b.build()).build();
        }
        return e;
    }

    Expr ilriExpr() {
        Expr lhs = compExpr();
        List<TokenType> expected = Arrays
                .asList(new TokenType[] { TokenType.IS, TokenType.IN, TokenType.LIKE, TokenType.BETWEEN, TokenType.REGEXP, TokenType.NOT });
        while (this.tokenPos < this.tokens.size() && expected.contains(this.tokens.get(this.tokenPos).type)) {
            boolean isNot = false;
            if (currentTokenTypeEquals(TokenType.NOT)) {
                consumeToken(TokenType.NOT);
                isNot = true;
            }
            if (this.tokenPos < this.tokens.size()) {
                List<Expr> params = new ArrayList<>();
                params.add(unquoteWorkaround(lhs));
                String opName = this.tokens.get(this.tokenPos).value.toLowerCase();
                switch (this.tokens.get(this.tokenPos).type) {
                    case IS: // for IS, NOT comes AFTER
                        consumeToken(TokenType.IS);
                        if (currentTokenTypeEquals(TokenType.NOT)) {
                            consumeToken(TokenType.NOT);
                            opName = "is_not";
                        }
                        params.add(compExpr());
                        break;
                    case IN:
                        consumeToken(TokenType.IN);
                        if (currentTokenTypeEquals(TokenType.LPAREN)) {
                            params.addAll(parenExprList());
                        } else {
                            if (!currentTokenTypeEquals(TokenType.LSQBRACKET)) {
                                opName = "cont_in";
                            }
                            params.add(compExpr());
                        }
                        break;
                    case LIKE:
                        consumeToken(TokenType.LIKE);
                        params.add(unquoteWorkaround(compExpr()));
                        if (currentTokenTypeEquals(TokenType.ESCAPE)) {
                            consumeToken(TokenType.ESCAPE);
                            // add as a third (optional) param
                            params.add(unquoteWorkaround(compExpr()));
                        }
                        break;
                    case BETWEEN:
                        consumeToken(TokenType.BETWEEN);
                        params.add(compExpr());
                        assertTokenAt(this.tokenPos, TokenType.AND);
                        consumeToken(TokenType.AND);
                        params.add(compExpr());
                        break;
                    case REGEXP:
                        consumeToken(TokenType.REGEXP);
                        params.add(compExpr());
                        break;
                    default:
                        throw new WrongArgumentException("Unknown token after NOT at pos: " + this.tokenPos);
                }
                if (isNot) {
                    opName = "not_" + opName;
                }
                Operator.Builder builder = Operator.newBuilder().setName(opName).addAllParam(params);
                lhs = Expr.newBuilder().setType(Expr.Type.OPERATOR).setOperator(builder.build()).build();
            }
        }
        return lhs;
    }

    Expr andExpr() {
        return parseLeftAssocBinaryOpExpr(new TokenType[] { TokenType.AND, TokenType.ANDAND }, this::ilriExpr);
    }

    Expr orExpr() {
        return parseLeftAssocBinaryOpExpr(new TokenType[] { TokenType.OR, TokenType.OROR }, this::andExpr);
    }

    Expr expr() {
        Expr e = orExpr();
        return e;
    }

    /**
     * Parse the entire string as an expression.
     *
     * @return an X protocol expression tree
     */
    public Expr parse() {
        try {
            Expr e = expr();
            if (this.tokenPos != this.tokens.size()) {
                throw new WrongArgumentException("Only " + this.tokenPos + " tokens consumed, out of " + this.tokens.size());
            }
            return e;
        } catch (IllegalArgumentException ex) {
            throw new WrongArgumentException("Unable to parse query '" + this.string + "'", ex);
        }
    }

    /**
     * Utility method to wrap a parser of a list of elements separated by comma.
     *
     * @param <T>
     *            the type of element to be parsed
     * @param elementParser
     *            the single element parser
     * @return a list of elements parsed
     */
    private <T> List<T> parseCommaSeparatedList(Supplier<T> elementParser) {
        List<T> elements = new ArrayList<>();
        boolean first = true;
        while (first || currentTokenTypeEquals(TokenType.COMMA)) {
            if (!first) {
                consumeToken(TokenType.COMMA);
            } else {
                first = false;
            }
            elements.add(elementParser.get());
        }
        return elements;
    }

    /**
     * Parse an ORDER BY specification which is a comma-separated list of expressions, each may be optionally suffixed by ASC/DESC.
     * 
     * @return list of {@link Order} objects
     */
    public List<Order> parseOrderSpec() {
        return parseCommaSeparatedList(() -> {
            Order.Builder builder = Order.newBuilder();
            builder.setExpr(expr());
            if (currentTokenTypeEquals(TokenType.ORDERBY_ASC)) {
                consumeToken(TokenType.ORDERBY_ASC);
                builder.setDirection(Order.Direction.ASC);
            } else if (currentTokenTypeEquals(TokenType.ORDERBY_DESC)) {
                consumeToken(TokenType.ORDERBY_DESC);
                builder.setDirection(Order.Direction.DESC);
            }
            return builder.build();
        });
    }

    /**
     * Parse a SELECT projection which is a comma-separated list of expressions, each optionally suffixed with a target alias.
     * 
     * @return list of {@link Projection} objects
     */
    public List<Projection> parseTableSelectProjection() {
        return parseCommaSeparatedList(() -> {
            Projection.Builder builder = Projection.newBuilder();
            builder.setSource(expr());
            if (currentTokenTypeEquals(TokenType.AS)) {
                consumeToken(TokenType.AS);
                builder.setAlias(consumeToken(TokenType.IDENT));
            }
            return builder.build();
        });
    }

    /**
     * Parse an INSERT field name.
     * 
     * @return {@link Column}
     */
    // TODO unit test
    public Column parseTableInsertField() {
        return Column.newBuilder().setName(consumeToken(TokenType.IDENT)).build();
    }

    /**
     * Parse an UPDATE field which can include can document paths.
     * 
     * @return {@link ColumnIdentifier}
     */
    public ColumnIdentifier parseTableUpdateField() {
        return columnIdentifier().getIdentifier();
    }

    /**
     * Parse a document projection which is similar to SELECT but with document paths as the target alias.
     * 
     * @return list of {@link Projection} objects
     */
    public List<Projection> parseDocumentProjection() {
        this.allowRelationalColumns = false;
        return parseCommaSeparatedList(() -> {
            Projection.Builder builder = Projection.newBuilder();
            builder.setSource(expr());
            // alias is not optional for document projection
            consumeToken(TokenType.AS);
            builder.setAlias(consumeToken(TokenType.IDENT));
            return builder.build();
        });
    }

    /**
     * Parse a list of expressions used for GROUP BY.
     * 
     * @return list of {@link Expr} objects
     */
    public List<Expr> parseExprList() {
        return parseCommaSeparatedList(this::expr);
    }

    /**
     * Return the number of positional placeholders in the expression.
     * 
     * @return the number of positional placeholders in the expression
     */
    public int getPositionalPlaceholderCount() {
        return this.positionalPlaceholderCount;
    }

    /**
     * @return a mapping of parameter names to positions.
     */
    public Map<String, Integer> getPlaceholderNameToPositionMap() {
        return Collections.unmodifiableMap(this.placeholderNameToPosition);
    }
}