/*
 * Copyright (c) 1998-2006 Caucho Technology -- all rights reserved
 *
 * This file is part of Resin(R) Open Source
 *
 * Each copy or derived work must preserve the copyright notice and this
 * notice unmodified.
 *
 * Resin Open Source is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Resin Open Source 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, or any warranty
 * of NON-INFRINGEMENT.  See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Resin Open Source; if not, write to the
 *   Free SoftwareFoundation, Inc.
 *   59 Temple Place, Suite 330
 *   Boston, MA 02111-1307  USA
 *
 * @author Scott Ferguson
 */

package com.caucho.db.sql;

import java.util.ArrayList;
import java.util.HashSet;

import java.util.logging.Level;
import java.util.logging.Logger;

import java.sql.SQLException;

import com.caucho.db.Database;
import com.caucho.db.table.Column;
import com.caucho.db.table.Table;
import com.caucho.db.table.TableFactory;

import com.caucho.log.Log;

import com.caucho.util.CharBuffer;
import com.caucho.util.IntMap;
import com.caucho.util.L10N;

public class Parser {
  private static final Logger log = Log.open(Parser.class);
  private static final L10N L = new L10N(Parser.class);

  final static int IDENTIFIER = 128;
  final static int INTEGER = IDENTIFIER + 1;
  final static int LONG = INTEGER + 1;
  final static int DOUBLE = LONG + 1;
  final static int STRING = DOUBLE + 1;
  final static int TRUE = STRING + 1;
  final static int FALSE = TRUE + 1;
  final static int UNKNOWN = FALSE + 1;
  final static int NULL = UNKNOWN + 1;
  final static int EXISTS = NULL + 1;

  final static int FROM = EXISTS + 1;
  final static int IN = FROM + 1;
  final static int SELECT = IN + 1;
  final static int DISTINCT = SELECT + 1;
  final static int WHERE = SELECT + 1;
  final static int AS = WHERE + 1;
  final static int ORDER = AS + 1;
  final static int GROUP = ORDER + 1;
  final static int BY = GROUP + 1;
  final static int ASC = BY + 1;
  final static int DESC = ASC + 1;
  final static int LIMIT = DESC + 1;
  final static int OFFSET = LIMIT + 1;

  final static int BETWEEN = OFFSET + 1;
  final static int LIKE = BETWEEN + 1;
  final static int ESCAPE = LIKE + 1;
  final static int IS = ESCAPE + 1;
  final static int CONCAT = IS + 1;

  final static int EQ = CONCAT + 1;
  final static int NE = EQ + 1;
  final static int LT = NE + 1;
  final static int LE = LT + 1;
  final static int GT = LE + 1;
  final static int GE = GT + 1;

  final static int AND = GE + 1;
  final static int OR = AND + 1;
  final static int NOT = OR + 1;

  final static int ARG = NOT + 1;

  final static int CREATE = ARG + 1;
  final static int TABLE = CREATE + 1;
  final static int INSERT = TABLE + 1;
  final static int INTO = INSERT + 1;
  final static int VALUES = INTO + 1;
  final static int DROP = VALUES + 1;
  final static int UPDATE = DROP + 1;
  final static int SET = UPDATE + 1;
  final static int DELETE = SET + 1;

  final static int CONSTRAINT = DELETE + 1;
  final static int UNIQUE = CONSTRAINT + 1;
  final static int PRIMARY = UNIQUE + 1;
  final static int CHECK = PRIMARY + 1;
  final static int FOREIGN = CHECK + 1;
  final static int KEY = FOREIGN + 1;

  private final static IntMap _reserved;

  private Database _database;

  private final String _sql;
  private final char []_sqlChars;
  private final int _sqlLength;

  private int _parseIndex;

  private final CharBuffer _cb = new CharBuffer();

  private String _lexeme;
  private int _token;

  private ArrayList<ParamExpr> _params = new ArrayList<ParamExpr>();

  private Query _query;
  private AndExpr _andExpr;

  private Parser(Database database, String sql)
  {
    _database = database;
    _sql = sql;
    _sqlLength = _sql.length();
    _sqlChars = new char[_sqlLength];
    _sql.getChars(0, _sqlLength, _sqlChars, 0);
  }

  public static Query parse(Database database, String sql)
    throws SQLException
  {
    Parser parser = new Parser(database, sql);

    Query query = parser.parse();

    query.bind();

    return query;
  }

  public static Expr parseExpr(Database database, String sql)
    throws SQLException
  {
    Parser parser = new Parser(database, sql);

    Expr expr = parser.parseExpr();

    return expr.bind(null);
  }

  /**
   * Parses the query.
   */
  private Query parse()
    throws SQLException
  {
    int token = scanToken();

    switch (token) {
    case SELECT:
      return parseSelect();

    case CREATE:
      return parseCreate();

    case INSERT:
      return parseInsert();

    case DELETE:
      return parseDelete();

    case DROP:
      return parseDrop();

    case UPDATE:
      return parseUpdate();

    default:
      throw new SQLParseException(L.l("unknown query at `{0}'",
				      tokenName(token)));
    }
  }

  /**
   * Parses the select.
   */
  private SelectQuery parseSelect()
    throws SQLException
  {
    return parseSelect(new SelectQuery(_database, _sql));
  }

  /**
   * Parses the select.
   */
  private SelectQuery parseSelect(SelectQuery query)
    throws SQLException
  {
    boolean distinct = false;

    int token = scanToken();

    if (token == DISTINCT)
      distinct = true;
    else
      _token = token;

    ArrayList<Expr> resultItems = new ArrayList<Expr>();

    int startToken = scanToken();
    String startLexeme = _lexeme;
    int startOffset = _parseIndex;

    while ((token = scanToken()) >= 0 && token != FROM) {
    }

    if (token != FROM)
      throw error(L.l("expected FROM at `{0}'", tokenName(token)));

    query.setParent(_query);
    _query = query;

    AndExpr oldAnd = _andExpr;
    _andExpr = new AndExpr();

    ArrayList<FromItem> fromItems = parseFromItems();

    query.setFromItems(fromItems);

    token = scanToken();

    int tailToken = token;
    int tailOffset = _parseIndex;

    _token = startToken;
    _parseIndex = startOffset;
    _lexeme = startLexeme;

    Expr expr = parseSelectExpr();

    resultItems.add(expr);

    while ((token = scanToken()) == ',') {
      expr = parseSelectExpr();

      resultItems.add(expr);
    }

    _token = tailToken;
    _parseIndex = tailOffset;

    token = scanToken();

    if (token == WHERE)
      _andExpr.add(parseExpr());
    else
      _token = token;

    ParamExpr []params = _params.toArray(new ParamExpr[_params.size()]);

    Expr whereExpr = _andExpr.getSingleExpr();
    _andExpr = null;
    query.setWhereExpr(whereExpr);
    query.setParams(params);

    for (int i = resultItems.size() - 1; i >= 0; i--) {
      Expr subExpr = resultItems.get(i);

      if (subExpr instanceof UnboundStarExpr) {
	UnboundStarExpr unboundExpr = (UnboundStarExpr) subExpr;
	ArrayList<Expr> exprList = unboundExpr.expand(query.getFromItems());

	resultItems.remove(i);
	resultItems.addAll(i, exprList);
      }
    }

    ArrayList<Expr> groupItems = null;
    token = scanToken();
    if (token == GROUP) {
      token = scanToken();

      if (token != BY)
	throw error(L.l("expected BY at `{0}'", tokenName(token)));

      groupItems = parseGroup(query);
    }
    else
      _token = token;

    token = scanToken();
    if (token == ORDER) {
      token = scanToken();

      if (token != BY)
	throw error(L.l("expected BY at `{0}'", tokenName(token)));

      Order order = parseOrder(query, resultItems);
    }
    else
      _token = token;

    Expr []resultArray = resultItems.toArray(new Expr[resultItems.size()]);

    query.setResults(resultArray);

    if (query.isGroup()) {
      Expr []resultList = query.getResults();

      bindGroup(query, groupItems);

      for (int i = 0; i < resultList.length; i++) {
	Expr subExpr = resultList[i];

	if (! (subExpr instanceof GroupExpr)) {
	  resultList[i] = new GroupResultExpr(i, subExpr);
	}
      }
    }

    token = scanToken();
    _token = token;
    if (query.getParent() == null &&
	token >= 0 && token != LIMIT && token != OFFSET)
      throw error(L.l("unexpected token at end '{0}'", tokenName(token)));

    _query = query.getParent();
    _andExpr = oldAnd;

    return query;
  }

  private ArrayList<FromItem> parseFromItems()
    throws SQLException
  {
    ArrayList<FromItem> fromItems = new ArrayList<FromItem>();

    int token;

    // XXX: somewhat hacked syntax
    while ((token = scanToken()) == '(') {
    }
    _token = token;
    
    FromItem fromItem = parseFromItem();

    if (fromItem != null)
      fromItems.add(fromItem);

    while (true) {
      token = scanToken();

      boolean isNatural = false;
      boolean isOuter = false;
      boolean isLeft = true;
      boolean isRight = true;

      if (token == ',') {
	fromItem = parseFromItem();
	fromItems.add(fromItem);
	continue;
      }
      else if (token == '(' || token == ')')
	continue;
      else if (token != IDENTIFIER) {
	_token = token;
	break;
      }
      else if ("join".equalsIgnoreCase(_lexeme)) {
      }
      else if ("inner".equalsIgnoreCase(_lexeme)) {
	String join = parseIdentifier();

	if (! "join".equalsIgnoreCase(join))
	  throw error(L.l("expected JOIN at '{0}'", join));
      }
      else if ("left".equalsIgnoreCase(_lexeme)) {
	String name = parseIdentifier();

	if ("outer".equalsIgnoreCase(name))
	  name = parseIdentifier();

	if (! "join".equalsIgnoreCase(name))
	  throw error(L.l("expected JOIN at '{0}'", name));

	isOuter = true;
      }
      else if ("right".equalsIgnoreCase(_lexeme)) {
	String name = parseIdentifier();

	if ("outer".equalsIgnoreCase(name))
	  name = parseIdentifier();

	if (! "join".equalsIgnoreCase(name))
	  throw error(L.l("expected JOIN at '{0}'", name));

	isRight = true;
	isOuter = true;

	throw error(L.l("right outer joins are not supported"));
      }
      else if ("natural".equalsIgnoreCase(_lexeme)) {
	String name = parseIdentifier();

	isNatural = true;

	if ("left".equalsIgnoreCase(name)) {
	  name = parseIdentifier();

	  if ("outer".equalsIgnoreCase(name))
	    name = parseIdentifier();

	  isOuter = true;
	}
	else if ("right".equalsIgnoreCase(name)) {
	  name = parseIdentifier();

	  if ("outer".equalsIgnoreCase(name))
	    name = parseIdentifier();

	  isRight = true;
	  isOuter = true;

	  throw error(L.l("right outer joins are not supported"));
	}

	if (! "join".equalsIgnoreCase(name))
	  throw error(L.l("expected JOIN at '{0}'", name));
      }
      else {
	_token = token;
	break;
      }

      fromItem = parseFromItem();
      fromItems.add(fromItem);

      _query.setFromItems(fromItems);

      token = scanToken();
      if (token == IDENTIFIER && "on".equalsIgnoreCase(_lexeme)) {
	Expr onExpr = parseExpr();

	if (isOuter) {
	  FromItem leftItem = fromItems.get(fromItems.size() - 2);
	  FromItem rightItem = fromItems.get(fromItems.size() - 1);

	  onExpr = new LeftOuterJoinExpr(rightItem, onExpr);

	  rightItem.setDependTable(leftItem);
	}

	_andExpr.add(onExpr);
      }
      else
	_token = token;
    }

    return fromItems;
  }

  /**
   * Parses a select expression.
   */
  private Expr parseSelectExpr()
    throws SQLException
  {
    int token = scanToken();

    if (token == '*')
      return new UnboundStarExpr();
    else {
      _token = token;

      return parseExpr();
    }
  }

  /**
   * Parses a from item
   */
  private FromItem parseFromItem()
    throws SQLException
  {
    String tableName = parseIdentifier();

    if (tableName.equalsIgnoreCase("DUAL"))
      return null;

    Table table = _database.getTable(tableName);

    if (table == null)
      throw error(L.l("'{0}' is an unknown table.  'FROM table' requires an existing table.", tableName));

    String name = table.getName();

    int token = scanToken();
    if (token == AS)
      name = parseIdentifier();
    else if (token == IDENTIFIER)
      name = _lexeme;
    else
      _token = token;

    return new FromItem(table, name);
  }

  /**
   * Parses the ORDER BY
   */
  private Order parseOrder(SelectQuery query,
			   ArrayList<Expr> resultList)
    throws SQLException
  {
    int token;

    Order order = null;

    do {
      Expr expr = parseExpr();

      expr = expr.bind(query);

      token = scanToken();
      boolean isAsc = true;
      if (token == ASC)
	isAsc = true;
      else if (token == DESC)
	isAsc = false;
      else
	_token = token;

      int index;
      for (index = 0; index < resultList.size(); index++) {
	Expr resultExpr = resultList.get(index);

	if (expr.equals(resultExpr))
	  break;
      }

      if (resultList.size() <= index) {
	resultList.add(expr);
      }

      Order tailOrder = expr.createOrder(index);
      tailOrder.setAscending(isAsc);

      order = Order.append(order, tailOrder);

      // ascList.add(isAsc ? Boolean.TRUE : Boolean.FALSE);
    } while ((token = scanToken()) == ',');

    query.setOrder(order);

    _token = token;

    return order;
  }

  /**
   * Parses the GROUP BY
   */
  private ArrayList<Expr> parseGroup(SelectQuery query)
    throws SQLException
  {
    query.setGroup(true);
    int token;

    ArrayList<Expr> groupList = new ArrayList<Expr>();

    do {
      groupList.add(parseExpr());
    } while ((token = scanToken()) == ',');

    _token = token;

    return groupList;
  }

  /**
   * Parses the GROUP BY
   */
  private void bindGroup(SelectQuery query, ArrayList<Expr> groupList)
    throws SQLException
  {
    query.setGroup(true);

    Expr []resultList = query.getResults();

    for (int i = 0; i < groupList.size(); i++) {
      Expr expr = groupList.get(i);

      expr = expr.bind(query);

      int index;
      for (index = 0; index < resultList.length; index++) {
	Expr resultExpr = resultList[index];

	if (expr.equals(resultExpr)) {
	  resultList[index] = new GroupResultExpr(index, resultExpr);

	  break;
	}
      }

      if (resultList.length <= index) {
	throw error(L.l("GROUP BY field '{0}' must refer to a result field.",
			expr));
      }

      query.setGroupResult(index);
    }
  }

  /**
   * Parses the create.
   */
  private Query parseCreate()
    throws SQLException
  {
    int token;

    TableFactory factory = _database.createTableFactory();

    if ((token = scanToken()) != TABLE)
      throw error(L.l("expected TABLE at `{0}'", tokenName(token)));

    if ((token = scanToken()) != IDENTIFIER)
      throw error(L.l("expected identifier at `{0}'", tokenName(token)));

    factory.startTable(_lexeme);

    if ((token = scanToken()) != '(')
      throw error(L.l("expected '(' at `{0}'", tokenName(token)));

    do {
      token = scanToken();

      switch (token) {
      case IDENTIFIER:
	parseCreateColumn(factory, _lexeme);
	break;

      case UNIQUE:
	factory.addUnique(parseColumnNames());
	break;

      case PRIMARY:
	token = scanToken();
	if (token != KEY)
	  throw error(L.l("expected 'key' at {0}", tokenName(token)));

	factory.addPrimaryKey(parseColumnNames());
	break;

      case KEY:
	String key = parseIdentifier();

	parseColumnNames(); // factory.addPrimaryKey(parseColumnNames());
	break;

      case CHECK:
	if ((token = scanToken()) != '(')
	  throw error(L.l("Expected '(' at '{0}'", tokenName(token)));

	parseExpr();

	if ((token = scanToken()) != ')')
	  throw error(L.l("Expected ')' at '{0}'", tokenName(token)));
	break;

      default:
	throw error(L.l("unexpected token `{0}'", tokenName(token)));
      }

      token = scanToken();
    } while (token == ',');

    if (token != ')')
      throw error(L.l("expected ')' at `{0}'", tokenName(token)));

    return new CreateQuery(_database, _sql, factory);
  }

  /**
   * Parses a column declaration.
   */
  private void parseCreateColumn(TableFactory factory, String name)
    throws SQLException
  {
    int token;

    if ((token = scanToken()) != IDENTIFIER)
      throw error(L.l("expected column type at {0}", tokenName(token)));

    String type = _lexeme;
    int length = -1;
    int scale = -1;

    if (type.equalsIgnoreCase("double")) {
      if ((token = scanToken()) == IDENTIFIER) {
	if (_lexeme.equalsIgnoreCase("precision")) {
	}
	else
	  throw error(L.l("unexpected double type at {0}", _lexeme));
      }
      else
	_token = token;
    }

    if ((token = scanToken()) == '(') {
      if ((token = scanToken()) != INTEGER)
	throw error(L.l("expected column width at `{0}'", tokenName(token)));

      length = Integer.parseInt(_lexeme);

      if ((token = scanToken()) == ',') {
	if ((token = scanToken()) != INTEGER)
	  throw error(L.l("expected column scale at `{0}'", tokenName(token)));

	scale = Integer.parseInt(_lexeme);

	token = scanToken();
      }

      if (token != ')')
	throw error(L.l("expected ')' at '{0}'", tokenName(token)));
    }
    else
      _token = token;

    if (type.equalsIgnoreCase("varchar")) {
      if (length < 0)
	throw error(L.l("VARCHAR needs a defined length"));

      factory.addVarchar(name, length);
    }
    else if (type.equalsIgnoreCase("char")) {
      if (length < 0)
	length = 1;

      factory.addVarchar(name, length);
    }
    else if (type.equalsIgnoreCase("blob")) {
      factory.addBlob(name);
    }
    else if (type.equalsIgnoreCase("integer") ||
	     type.equalsIgnoreCase("int") ||
	     type.equalsIgnoreCase("smallint") ||
	     type.equalsIgnoreCase("tinyint") ||
	     type.equalsIgnoreCase("mediumint") ||
	     type.equalsIgnoreCase("bit")) {
      factory.addInteger(name);
    }
    else if (type.equalsIgnoreCase("bigint")) {
      factory.addLong(name);
    }
    else if (type.equalsIgnoreCase("double") ||
	     type.equalsIgnoreCase("float") ||
	     type.equalsIgnoreCase("real")) {
      factory.addDouble(name);
    }
    else if (type.equalsIgnoreCase("datetime") ||
	     type.equalsIgnoreCase("timestamp")) {
      factory.addDateTime(name);
    }
    else if (type.equalsIgnoreCase("text") ||
	     type.equalsIgnoreCase("clob")) {
      factory.addVarchar(name, 255);
    }
    else if (type.equalsIgnoreCase("decimal") ||
	     type.equalsIgnoreCase("numeric")) {
      factory.addNumeric(name, length, scale);
    }
    else
      throw error(L.l("Unknown type {0}", type));

    token = scanToken();
    if (token == IDENTIFIER && _lexeme.equalsIgnoreCase("default")) {
      Expr defaultExpr = parseExpr();

      factory.setDefault(name, defaultExpr);
    }
    else
      _token = token;

    while (true) {
      token = scanToken();

      // XXX: stuff like NOT NULL

      switch (token) {
      case ')':
      case ',':
	_token = token;
	return;

      case UNIQUE:
	factory.setUnique(name);
	break;

      case PRIMARY:
	token = scanToken();
	if (token != KEY)
	  throw error(L.l("expected key at {0}", tokenName(token)));

	factory.setPrimaryKey(name);
	break;

      case CHECK:
	if ((token = scanToken()) != '(')
	  throw error(L.l("Expected '(' at '{0}'", tokenName(token)));

	parseExpr();

	if ((token = scanToken()) != ')')
	  throw error(L.l("Expected ')' at '{0}'", tokenName(token)));
	break;

      case IDENTIFIER:
	String id = _lexeme;
	if (id.equalsIgnoreCase("references")) {
	  ArrayList<String> foreignKey = new ArrayList<String>();
	  foreignKey.add(name);
	  parseReferences(foreignKey);
	}
	else if (id.equalsIgnoreCase("default")) {
	  Expr expr = parseExpr();
	}
	else if (id.equalsIgnoreCase("auto_increment")) {
	  factory.setAutoIncrement(name, 1);
	}
	else if (id.equalsIgnoreCase("unsigned")) {
	}
	else if (id.equalsIgnoreCase("binary")) {
	}
	else
	  throw error(L.l("unexpected token '{0}'", tokenName(token)));
	break;

      case NULL:
	break;

      case NOT:
	if ((token = scanToken()) == NULL)
	  factory.setNotNull(name);
	else
	  throw error(L.l("unexpected token '{0}'", tokenName(token)));
	break;

      default:
	throw error(L.l("unexpected token '{0}'", tokenName(token)));
      }
    }
  }
  
  /**
   * Parses a key constraint declaration.
   */
  private void parseKeyConstraint(TableFactory factory)
    throws SQLException
  {
    String key = parseIdentifier();

    int token = scanToken();

    if (token == '(') {
      parseIdentifier();

      token = scanToken();
      if (token != ')')
	throw error("expected ')'");
    }
    else
      _token = token;
  }

  /**
   * Parses the references clause.
   */
  public void parseReferences(ArrayList<String> name)
    throws SQLException
  {
    String foreignTable = parseIdentifier();

    int token = scanToken();

    ArrayList<String> foreignColumns = new ArrayList<String>();

    if (token == '(') {
      _token = token;

      foreignColumns = parseColumnNames();
    }
    else
      _token = token;
  }

  /**
   * Parses a list of column names
   */
  public ArrayList<String> parseColumnNames()
    throws SQLException
  {
    ArrayList<String> columns = new ArrayList<String>();

    int token = scanToken();
    if (token == '(') {
      do {
	columns.add(parseIdentifier());

	token = scanToken();
      } while (token == ',');

      if (token != ')')
	throw error(L.l("expected ')' at '{0}'", tokenName(token)));
    }
    else if (token == IDENTIFIER) {
      columns.add(_lexeme);

      _token = token;
    }
    else
      throw error(L.l("expected '(' at '{0}'", tokenName(token)));

    return columns;
  }

  /**
   * Parses the insert.
   */
  private Query parseInsert()
    throws SQLException
  {
    int token;

    if ((token = scanToken()) != INTO)
      throw error(L.l("expected INTO at `{0}'", tokenName(token)));

    if ((token = scanToken()) != IDENTIFIER)
      throw error(L.l("expected identifier at `{0}'", tokenName(token)));

    Table table = _database.getTable(_lexeme);

    if (table == null)
      throw error(L.l("unknown table `{0}'", tokenName(token)));

    FromItem fromItem = new FromItem(table, table.getName());
    FromItem[] fromList = new FromItem[] { fromItem };

    ArrayList<Column> columns = new ArrayList<Column>();

    if ((token = scanToken()) == '(') {
      do {
	String columnName = parseIdentifier();

	Column column = table.getColumn(columnName);

	if (column == null)
	  throw new SQLException(L.l("`{0}' is not a valid column in {1}",
				     columnName, table.getName()));
	columns.add(column);
      } while ((token = scanToken()) == ',');

      if (token != ')')
	throw error(L.l("expected ')' at `{0}'", tokenName(token)));

      token = scanToken();
    }
    else {
      Column []columnArray = table.getColumns();

      for (int i = 0; i < columnArray.length; i++)
	columns.add(columnArray[i]);
    }

    if (token != VALUES)
      throw error(L.l("expected VALUES at `{0}'", tokenName(token)));

    if ((token = scanToken()) != '(')
      throw error(L.l("expected '(' at `{0}'", tokenName(token)));

    ArrayList<Expr> values = new ArrayList<Expr>();

    InsertQuery query = new InsertQuery(_database, _sql, table, columns);
    _query = query;

    int i = 0;
    do {
      Expr expr = parseExpr();

      expr = expr.bind(new TempQuery(fromList));

      values.add(expr);

      i++;
    } while ((token = scanToken()) == ',');

    if (token != ')')
      throw error(L.l("expected ')' at {0}", tokenName(token)));

    if (columns.size() != values.size())
      throw error(L.l("number of columns does not match number of values"));

    ParamExpr []params = _params.toArray(new ParamExpr[_params.size()]);

    query.setParams(params);
    query.setValues(values);
    query.init();

    return query;
  }

  /**
   * Parses the delete.
   */
  private Query parseDelete()
    throws SQLException
  {
    int token;

    if ((token = scanToken()) != FROM)
      throw error(L.l("expected FROM at `{0}'", tokenName(token)));

    if ((token = scanToken()) != IDENTIFIER)
      throw error(L.l("expected identifier at `{0}'", tokenName(token)));

    Table table = _database.getTable(_lexeme);

    if (table == null)
      throw error(L.l("unknown table `{0}'", tokenName(token)));

    DeleteQuery query = new DeleteQuery(_database, _sql, table);
    _query = query;

    Expr whereExpr = null;

    token = scanToken();
    if (token == WHERE)
      whereExpr = parseExpr();
    else if (token >= 0)
      throw error(L.l("expected WHERE at `{0}'", tokenName(token)));

    ParamExpr []params = _params.toArray(new ParamExpr[_params.size()]);

    query.setParams(params);
    query.setWhereExpr(whereExpr);

    return query;
  }

  /**
   * Parses the insert.
   */
  private Query parseDrop()
    throws SQLException
  {
    int token;

    if ((token = scanToken()) != TABLE)
      throw error(L.l("expected TABLE at `{0}'", tokenName(token)));

    if ((token = scanToken()) != IDENTIFIER)
      throw error(L.l("expected identifier at `{0}'", tokenName(token)));

    String table = _lexeme;

    if ((token = scanToken()) >= 0)
      throw error(L.l("expected end of query at `{0}'", tokenName(token)));

    return new DropQuery(_sql, _database, table);
  }

  /**
   * Parses the select.
   */
  private Query parseUpdate()
    throws SQLException
  {
    int token;

    if ((token = scanToken()) != IDENTIFIER)
      throw error(L.l("expected identifier at `{0}'", tokenName(token)));

    String name = _lexeme;

    Table table = _database.getTable(name);

    if (table == null)
      throw error(L.l("`{0}' is an unknown table in INSERT.", name));

    if ((token = scanToken()) != SET)
      throw error(L.l("expected SET at {0}", tokenName(token)));

    UpdateQuery query = new UpdateQuery(_database, _sql, table);
    _query = query;

    ArrayList<SetItem> setItemList = new ArrayList<SetItem>();

    do {
      SetItem item = parseSetItem(table);

      setItemList.add(item);
    } while ((token = scanToken()) == ',');

    Expr whereExpr = null;

    if (token == WHERE)
      whereExpr = parseExpr();

    SetItem []setItems = new SetItem[setItemList.size()];
    setItemList.toArray(setItems);

    ParamExpr []params = _params.toArray(new ParamExpr[_params.size()]);

    query.setSetItems(setItems);
    query.setParams(params);
    query.setWhereExpr(whereExpr);

    return query;
  }

  /**
   * Parses a set item.
   */
  private SetItem parseSetItem(Table table)
    throws SQLException
  {
    int token;

    if ((token = scanToken()) != IDENTIFIER)
      throw error(L.l("expected identifier at `{0}'", tokenName(token)));

    Column column = table.getColumn(_lexeme);

    if (column == null)
      throw error(L.l("`{0}' is an unknown column in table {1}.",
		      _lexeme, table.getName()));

    if ((token = scanToken()) != EQ)
      throw error(L.l("expected `=' at {0}", tokenName(token)));

    Expr expr = parseExpr();

    return new SetItem(table, column, expr);
  }

  /**
   * Parses an expression.
   */
  private Expr parseExpr()
    throws SQLException
  {
    int token = scanToken();

    if (token == SELECT)
      return parseSubSelect();
    else {
      _token = token;
      return parseOrExpr();
    }
  }

  /**
   * Parses a sub-select expression.
   */
  private Expr parseSubSelect()
    throws SQLException
  {
    return parseSubSelect(new SelectQuery(_database, _sql));
  }

  /**
   * Parses a sub-select expression.
   */
  private Expr parseSubSelect(SelectQuery query)
    throws SQLException
  {
    parseSelect(query);

    SubSelectExpr expr = new SubSelectExpr(query);

    query.setSubSelect(expr);

    _andExpr.add(new SubSelectEvalExpr(expr));

    return expr;
  }

  /**
   * Parses an OR expression.
   */
  private Expr parseOrExpr()
    throws SQLException
  {
    Expr left = parseAndExpr();

    while (true) {
      int token = scanToken();

      switch (token) {
      case OR:
	left = new OrExpr(left, parseAndExpr());
	break;

      default:
	_token = token;
	return left;
      }
    }
  }

  /**
   * Parses an AND expression.
   */
  private Expr parseAndExpr()
    throws SQLException
  {
    AndExpr oldAndExpr = _andExpr;
    AndExpr andExpr = new AndExpr();
    _andExpr = andExpr;

    andExpr.add(parseNotExpr());

    while (true) {
      int token = scanToken();

      switch (token) {
      case AND:
	andExpr.add(parseNotExpr());
	break;

      default:
	_token = token;

	_andExpr = oldAndExpr;

	return andExpr.getSingleExpr();
      }
    }
  }

  /**
   * Parses a term.
   */
  private Expr parseNotExpr()
    throws SQLException
  {
    int token = scanToken();

    switch (token) {
    case NOT:
      return new NotExpr(parseNotExpr());

    default:
      _token = token;
      return parseCmpExpr();
    }
  }

  /**
   * Parses a CMP expression.
   */
  private Expr parseCmpExpr()
    throws SQLException
  {
    Expr left = parseConcatExpr();

    int token = scanToken();
    boolean isNot = false;

    if (token == NOT) {
      isNot = true;

      token = scanToken();

      if (token != BETWEEN && token != LIKE && token != IN) {
	_token = token;
	
	return left;
      }
    }

    switch (token) {
    case EQ:
      return new EqExpr(left, parseConcatExpr());

    case LT:
    case LE:
    case GT:
    case GE:
    case NE:
      return new CmpExpr(left, parseConcatExpr(), token);

    case BETWEEN:
      {
	Expr min = parseConcatExpr();

	token = scanToken();
	if (token != AND)
	  throw error(L.l("expected AND at '{0}'", tokenName(token)));

	Expr max = parseConcatExpr();

	return new BetweenExpr(left, min, max, isNot);
      }

    case IS:
      {
	token = scanToken();
	isNot = false;
	if (token == NOT) {
	  token = scanToken();
	  isNot = true;
	}

	if (token == NULL)
	  return new IsNullExpr(left, isNot);
	else
	  throw error(L.l("expected NULL at '{0}'", tokenName(token)));
      }

    case LIKE:
      {
	token = scanToken();

	if (token == STRING)
	  return new LikeExpr(left, _lexeme, isNot);
	else
	  throw error(L.l("expected string at '{0}'", tokenName(token)));
      }

    case IN:
      {
	HashSet<String> values = parseInValues();

	return new InExpr(left, values, isNot);
      }

    default:
      _token = token;
      return left;
    }
  }

  /**
   * Parses the IN values.
   */
  private HashSet<String> parseInValues()
    throws SQLException
  {
    int token = scanToken();

    if (token != '(')
      throw error(L.l("Expected '('"));

    HashSet<String> values = new HashSet<String>();

    while ((token = scanToken()) != ')') {
      if (token == STRING) {
	values.add(_lexeme);
      }
      else
	throw error(L.l("expected STRING at {0}", tokenName(token)));
	
      if ((token = scanToken()) != ',')
	break;
    }

    if (token != ')')
	throw error(L.l("expected ')' at {0}", tokenName(token)));

    return values;
  }

  /**
   * Parses a concat expression.
   */
  private Expr parseConcatExpr()
    throws SQLException
  {
    Expr left = parseAddExpr();

    while (true) {
      int token = scanToken();

      switch (token) {
      case CONCAT:
	left = new ConcatExpr(left, parseAddExpr());
	break;

      default:
	_token = token;
	return left;
      }
    }
  }

  /**
   * Parses a +/- expression.
   */
  private Expr parseAddExpr()
    throws SQLException
  {
    Expr left = parseMulExpr();

    while (true) {
      int token = scanToken();

      switch (token) {
      case '+':
      case '-':
	left = new BinaryExpr(left, parseMulExpr(), token);
	break;

      default:
	_token = token;
	return left;
      }
    }
  }

  /**
   * Parses a mul/div expression
   */
  private Expr parseMulExpr()
    throws SQLException
  {
    Expr left = parseTerm();

    while (true) {
      int token = scanToken();

      switch (token) {
      case '*':
      case '/':
      case '%':
	left = new BinaryExpr(left, parseTerm(), token);
	break;

      default:
	_token = token;
	return left;
      }
    }
  }

  /**
   * Parses a term.
   */
  private Expr parseTerm()
    throws SQLException
  {
    int token = scanToken();

    switch (token) {
    case '+':
      return parseTerm();

    case '-':
      return new UnaryExpr(parseTerm(), token);

    case '(':
      Expr expr = parseExpr();
      int peekToken;
      if ((peekToken = scanToken()) != ')')
	throw error(L.l("expected ')' at {0}", tokenName(peekToken)));
      return expr;

    default:
      _token = token;
      return parseSimpleTerm();
    }
  }

  /**
   * Parses a simple term.
   */
  private Expr parseSimpleTerm()
    throws SQLException
  {
    int token = scanToken();

    switch (token) {
    case IDENTIFIER:
      {
	String name = _lexeme;

	token = scanToken();
	if (token == '.') {
	  token = scanToken();

	  if (token == IDENTIFIER) {
	    String column = _lexeme;
	    return _query.bind(name, column);
	  }
	  else if (token == '*') {
	    return new UnboundStarExpr(name);
	  }
	  else
	    throw error("expected IDENTIFIER");
	}
	else if (token == '(') {
	  FunExpr fun = null;
	  if (name.equalsIgnoreCase("max"))
	    fun = new MaxExpr();
	  else if (name.equalsIgnoreCase("min"))
	    fun = new MinExpr();
	  else if (name.equalsIgnoreCase("sum"))
	    fun = new SumExpr();
	  else if (name.equalsIgnoreCase("avg"))
	    fun = new AvgExpr();
	  else if (name.equalsIgnoreCase("count")) {
	    fun = new CountExpr();

	    token = scanToken();
	    if (token == '*') {
	      fun.addArg(new UnboundStarExpr());
	    }
	    else
	      _token = token;
	  }
	  else if (name.equalsIgnoreCase("exists")) {
	    token = scanToken();

	    if (token != SELECT)
	      throw error(L.l("exists requires SELECT at '{0}'",
			      tokenName(token)));

	    ExistsQuery query = new ExistsQuery(_database, _sql);

	    parseSelect(query);

	    ExistsExpr expr = new ExistsExpr(query);

	    query.setSubSelect(expr);

	    _andExpr.add(new ExistsEvalExpr(expr));

	    token = scanToken();

	    if (token != ')')
	      throw error(L.l("exists requires ')' at '{0}'",
			      tokenName(token)));

	    return expr;
	  }
	  else {
	    String funName = (Character.toUpperCase(name.charAt(0)) +
			      name.substring(1).toLowerCase());

	    funName = "com.caucho.db.fun." + funName + "Expr";

	    try {
	      Class cl = Class.forName(funName);

	      fun = (FunExpr) cl.newInstance();
	    } catch (ClassNotFoundException e) {
	      log.finer(e.toString());
	    } catch (Throwable e) {
	      log.log(Level.FINER, e.toString(), e);
	    }

	    if (fun == null)
	      throw error(L.l("`{0}' is an unknown function.", name));
	  }

	  token = scanToken();
	  while (token > 0 && token != ')') {
	    _token = token;

	    Expr arg = parseExpr();

	    fun.addArg(arg);

	    token = scanToken();

	    if (token == ',')
	      token = scanToken();
	  }

	  return fun;
	}
	else {
	  _token = token;
	  return _query.bind(null, name);
	}
      }

    case STRING:
      return new StringExpr(_lexeme);

    case DOUBLE:
    case INTEGER:
    case LONG:
      return NumberExpr.create(_lexeme);

    case NULL:
      return new NullExpr();

    case TRUE:
      return BooleanLiteralExpr.create(true);

    case FALSE:
      return BooleanLiteralExpr.create(false);

    case '?':
      ParamExpr param = new ParamExpr(_params.size());
      _params.add(param);
      return param;

    default:
      throw error(L.l("unexpected term {0}", tokenName(token)));
    }
  }

  /**
   * Parses an identifier.
   */
  private String parseIdentifier()
    throws SQLException
  {
    int token = scanToken();

    if (token != IDENTIFIER)
      throw error(L.l("expected identifier at {0}", tokenName(token)));

    return _lexeme;
  }

  /**
   * Scan the next token.  If the lexeme is a string, its string
   * representation is in "lexeme".
   *
   * @return integer code for the token
   */
  private int scanToken()
    throws SQLException
  {
    if (_token > 0) {
      int value = _token;
      _token = -1;
      return value;
    }

    int sign = 1;
    int ch;

    for (ch = read(); Character.isWhitespace((char) ch); ch = read()) {
    }

    switch (ch) {
    case -1:
    case '(':
    case ')':
    case '.':
    case '*':
    case '/':
    case '%':
    case ',':
    case '?':
      return ch;

    case '+':
      if ((ch = read()) >= '0' && ch <= '9')
        break;
      else {
        unread(ch);
        return '+';
      }

    case '-':
      if ((ch = read()) >= '0' && ch <= '9') {
        sign = -1;
        break;
      }
      else {
        unread(ch);
        return '-';
      }

    case '=':
      return EQ;

    case '<':
      if ((ch = read()) == '=')
        return LE;
      else if (ch == '>')
        return NE;
      else {
        unread(ch);
        return LT;
      }

    case '>':
      if ((ch = read()) == '=')
        return GE;
      else {
        unread(ch);
        return GT;
      }

    case '|':
      if ((ch = read()) == '|')
        return CONCAT;
      else {
        throw error(L.l("'|' expected at {0}", charName(ch)));
      }

      // @@ is useless?
    case '@':
      if ((ch = read()) != '@')
        throw error(L.l("`@' expected at {0}", charName(ch)));
      return scanToken();
    }

    if (Character.isJavaIdentifierStart((char) ch)) {
      CharBuffer cb = _cb;
      cb.clear();

      for (; ch > 0 && Character.isJavaIdentifierPart((char) ch); ch = read())
        cb.append((char) ch);

      unread(ch);

      _lexeme = cb.toString();
      String lower = _lexeme.toLowerCase();

      int token = _reserved.get(lower);

      if (token > 0)
        return token;
      else
        return IDENTIFIER;
    }
    else if (ch >= '0' && ch <= '9') {
      CharBuffer cb = _cb;
      cb.clear();

      int type = INTEGER;

      if (sign < 0)
        cb.append('-');

      for (; ch >= '0' && ch <= '9'; ch = read())
        cb.append((char) ch);

      if (ch == '.') {
        type = DOUBLE;

        cb.append('.');
        for (ch = read(); ch >= '0' && ch <= '9'; ch = read())
          cb.append((char) ch);
      }

      if (ch == 'e' || ch == 'E') {
        type = DOUBLE;

        cb.append('e');
        if ((ch = read()) == '+' || ch == '-') {
          cb.append((char) ch);
          ch = read();
        }

        if (! (ch >= '0' && ch <= '9'))
          throw error(L.l("exponent needs digits at {0}",
                          charName(ch)));

        for (; ch >= '0' && ch <= '9'; ch = read())
          cb.append((char) ch);
      }

      if (ch == 'F' || ch == 'D')
        type = DOUBLE;
      else if (ch == 'L') {
        type = LONG;
      }
      else
        unread(ch);

      _lexeme = cb.toString();

      return type;
    }
    else if (ch == '\'') {
      CharBuffer cb = _cb;
      cb.clear();

      for (ch = read(); ch >= 0; ch = read()) {
	if (ch == '\'') {
	  if ((ch = read()) == '\'')
	    cb.append('\'');
	  else {
	    unread(ch);
	    break;
	  }
	}
	else if (ch == '\\') {
	  ch = read();

	  if (ch >= 0)
	    cb.append(ch);
	}
	else
	  cb.append((char) ch);
      }

      _lexeme = cb.toString();

      return STRING;
    }
    else if (ch == '#') {
      // skip comment
      while ((ch = read()) >= 0 && ch != '\n' && ch != '\r') {
      }

      // XXX: cleanup to avoid recursion
      return scanToken();
    }

    throw error(L.l("unexpected char at {0} ({1})", "" + (char) ch,
		    String.valueOf(ch)));
  }

  /**
   * Returns the next character.
   */
  private int read()
  {
    if (_parseIndex < _sqlLength)
      return _sqlChars[_parseIndex++];
    else
      return -1;
  }

  /**
   * Unread the last character.
   */
  private void unread(int ch)
  {
    if (ch >= 0)
      _parseIndex--;
  }

  /**
   * Returns the name for a character
   */
  private String charName(int ch)
  {
    if (ch < 0)
      return L.l("end of query");
    else
      return String.valueOf((char) ch);
  }

  /**
   * Returns the name of a token
   */
  private String tokenName(int token)
  {
    switch (token) {
    case AS: return "AS";
    case ARG: return "?";
    case FROM: return "FROM";
    case IN: return "IN";
    case SELECT: return "SELECT";
    case WHERE: return "WHERE";
    case OR: return "OR";
    case AND: return "AND";
    case NOT: return "NOT";
    case BETWEEN: return "BETWEEN";
    case TRUE: return "TRUE";
    case FALSE: return "FALSE";
    case NULL: return "NULL";
    case GROUP: return "GROUP";
    case ORDER: return "ORDER";
    case BY: return "BY";
    case ASC: return "ASC";
    case DESC: return "DESC";
    case LIMIT: return "LIMIT";

    case -1:
      return L.l("end of query");

    default:
      if (token < 128)
        return "'" + String.valueOf((char) token) + "'";
      else
        return "'" + _lexeme + "'";
    }
  }

  private SQLException error(String msg)
  {
    return new SQLParseException(msg + "\n" + _sql);
  }

  static {
    _reserved = new IntMap();
    _reserved.put("as", AS);
    _reserved.put("from", FROM);
    _reserved.put("in", IN);
    _reserved.put("select", SELECT);
    _reserved.put("distinct", DISTINCT);
    _reserved.put("where", WHERE);
    _reserved.put("order", ORDER);
    _reserved.put("group", GROUP);
    _reserved.put("by", BY);
    _reserved.put("asc", ASC);
    _reserved.put("desc", DESC);
    _reserved.put("limit", LIMIT);
    _reserved.put("offset", OFFSET);

    _reserved.put("or", OR);
    _reserved.put("and", AND);
    _reserved.put("not", NOT);

    _reserved.put("between", BETWEEN);
    _reserved.put("like", LIKE);
    _reserved.put("escape", ESCAPE);
    _reserved.put("is", IS);

    _reserved.put("true", TRUE);
    _reserved.put("false", FALSE);
    _reserved.put("unknown", UNKNOWN);
    _reserved.put("null", NULL);

    _reserved.put("create", CREATE);
    _reserved.put("table", TABLE);
    _reserved.put("insert", INSERT);
    _reserved.put("into", INTO);
    _reserved.put("values", VALUES);
    _reserved.put("drop", DROP);
    _reserved.put("update", UPDATE);
    _reserved.put("set", SET);
    _reserved.put("delete", DELETE);

    _reserved.put("constraint", CONSTRAINT);
    _reserved.put("unique", UNIQUE);
    _reserved.put("check", CHECK);
    _reserved.put("primary", PRIMARY);
    _reserved.put("key", KEY);
    _reserved.put("foreign", FOREIGN);
  }
}
