// $Id: ExpressionParser.cc 59 2007-07-17 14:43:23Z tb $

/*
 * STX Expression Parser C++ Framework v0.7
 * Copyright (C) 2007 Timo Bingmann
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 *
 * This library 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 Lesser General Public License
 * for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

/** \file ExpressionParser.cc
 * Implementation of the parser using a boost::spirit grammar and a different
 * specializations of ParseNode.
 */

#include "ExpressionParser.h"

#include <boost/spirit/core.hpp>

#include <boost/spirit/tree/ast.hpp>
#include <boost/spirit/tree/tree_to_xml.hpp>

#include <boost/spirit/utility/lists.hpp>
#include <boost/spirit/utility/distinct.hpp>
#include <boost/spirit/utility/escape_char.hpp>
#include <boost/spirit/utility/grammar_def.hpp> 

#include <iostream>
#include <sstream>
#include <cmath>

// #define STX_DEBUG_PARSER

namespace stx {

/// Enclosure for the spirit parser grammar and hidden parse node
/// implementation classes.
namespace Grammar {

using namespace boost::spirit;

/// This enum specifies ids for the parse tree nodes created for each rule.
enum parser_ids
{
    boolean_const_id = 1,
    integer_const_id,
    long_const_id,
    double_const_id,
    string_const_id,
    constant_id,

    function_call_id,
    function_identifier_id,

    varname_id,

    atom_expr_id,

    unary_expr_id,
    mul_expr_id,
    add_expr_id,

    cast_expr_id,
    cast_spec_id,

    comp_expr_id,
    and_expr_id,
    or_expr_id,

    expr_id,
    exprlist_id,
};

/// Keyword parser used for matching words with () and spaces as separators.
distinct_parser<> keyword_p("a-zA-Z0-9_");

/// The boost::spirit expression parser grammar
struct ExpressionGrammar : public grammar<ExpressionGrammar>
{
    /// The boost::spirit expression parser grammar definition (for a specific
    /// scanner) with two entry points.
    template <typename ScannerT>
    struct definition : public grammar_def<rule<ScannerT, parser_context<>, parser_tag<expr_id> >,
					   rule<ScannerT, parser_context<>, parser_tag<exprlist_id> > >
    {
	/// Real definition function of the grammar.
	definition(ExpressionGrammar const& /*self*/)
	{
	    // *** Constants

	    constant
		= double_const
		| integer_const
		| long_const
		| boolean_const
		| string_const
		;
	    
	    boolean_const
		= as_lower_d[keyword_p("true") | keyword_p("false")]
		;

	    integer_const
		= int_p
		;

	    // this is needed because spirit's int_parsers don't work with
	    // these long numbers
	    long_const
		= token_node_d[ lexeme_d[ !( ch_p('+') | ch_p('-' ) ) >> +( range_p('0','9') ) ] ]
		;

	    double_const
		= strict_real_p
		;

            string_const
                = lexeme_d[
		    token_node_d[ '"' >> *(c_escape_ch_p - '"') >> '"' ]
                    ]
                ;

	    // *** Function call and function identifier

            function_call
                = root_node_d[function_identifier]
		>> discard_node_d[ ch_p('(') ] >> exprlist >> discard_node_d[ ch_p(')') ]
                ;

            function_identifier
                = lexeme_d[ 
		    token_node_d[ alpha_p >> *(alnum_p | ch_p('_')) ]
                    ]
                ;

	    // *** Expression names

            varname
                = lexeme_d[ 
		    token_node_d[ alpha_p >> *(alnum_p | ch_p('_')) ]
                    ]
                ;

	    // *** Valid Expressions, from small to large

            atom_expr
                = constant
                | inner_node_d[ ch_p('(') >> expr >> ch_p(')') ]
                | function_call
		| varname
                ;

            unary_expr
                = !( root_node_d[ as_lower_d[ch_p('+') | ch_p('-') | ch_p('!') | str_p("not")] ] )
		>> atom_expr
                ;

	    cast_spec
		= discard_node_d[ ch_p('(') ]
		>> (
		    keyword_p("bool") |
		    keyword_p("char") | keyword_p("short") | keyword_p("int") | keyword_p("integer") | keyword_p("long") |
		    keyword_p("byte") | keyword_p("word") | keyword_p("dword") | keyword_p("qword") |
		    keyword_p("float") | keyword_p("double") |
		    keyword_p("string")
		    )
		>> discard_node_d[ ch_p(')') ]
		;

            cast_expr
		= root_node_d[ !cast_spec ] >> unary_expr
		;

            mul_expr
                = cast_expr
		>> *( root_node_d[ch_p('*') | ch_p('/')] >> cast_expr )
                ;

	    add_expr
		= mul_expr
		>> *( root_node_d[ch_p('+') | ch_p('-')] >> mul_expr )
		;

	    comp_expr
		= add_expr
		>> *( root_node_d[( str_p("==") | str_p("!=") |
				    str_p("<=") | str_p(">=") | str_p("=<") | str_p("=>") |
				    ch_p('=') | ch_p('<') | ch_p('>') )] >> add_expr )
		;

	    and_expr
		= comp_expr
		>> *( root_node_d[ as_lower_d[str_p("and") | str_p("&&")] ] >> comp_expr )
		;

	    or_expr
		= and_expr
		>> *( root_node_d[ as_lower_d[str_p("or") | str_p("||")] ] >> and_expr )
		;

	    // *** Base Expression and List

	    expr
		= or_expr
		;

	    exprlist
		= infix_node_d[ !list_p(expr, ch_p(',')) ]
		;

	    // Special spirit feature to declare multiple grammar entry points
	    this->start_parsers(expr, exprlist); 

#ifdef STX_DEBUG_PARSER
	    BOOST_SPIRIT_DEBUG_RULE(constant);

	    BOOST_SPIRIT_DEBUG_RULE(boolean_const);
	    BOOST_SPIRIT_DEBUG_RULE(integer_const);
	    BOOST_SPIRIT_DEBUG_RULE(long_const);
	    BOOST_SPIRIT_DEBUG_RULE(double_const);
	    BOOST_SPIRIT_DEBUG_RULE(string_const);

	    BOOST_SPIRIT_DEBUG_RULE(function_call);
	    BOOST_SPIRIT_DEBUG_RULE(function_identifier);
	    
	    BOOST_SPIRIT_DEBUG_RULE(varname);

	    BOOST_SPIRIT_DEBUG_RULE(atom_expr);

	    BOOST_SPIRIT_DEBUG_RULE(unary_expr);
	    BOOST_SPIRIT_DEBUG_RULE(mul_expr);
	    BOOST_SPIRIT_DEBUG_RULE(add_expr);

	    BOOST_SPIRIT_DEBUG_RULE(cast_spec);
	    BOOST_SPIRIT_DEBUG_RULE(cast_expr);

	    BOOST_SPIRIT_DEBUG_RULE(comp_expr);
	    BOOST_SPIRIT_DEBUG_RULE(and_expr);
	    BOOST_SPIRIT_DEBUG_RULE(or_expr);

	    BOOST_SPIRIT_DEBUG_RULE(expr);
	    BOOST_SPIRIT_DEBUG_RULE(exprlist);
#endif
	}

	/// Rule for a constant: one of the three scalar types integer_const,
	/// double_const or string_const
        rule<ScannerT, parser_context<>, parser_tag<constant_id> > 		constant;

	/// Boolean value constant rule: "true" or "false"
        rule<ScannerT, parser_context<>, parser_tag<boolean_const_id> > 	boolean_const;
	/// Integer constant rule: "1234"
        rule<ScannerT, parser_context<>, parser_tag<integer_const_id> > 	integer_const;
	/// Long integer constant rule: "12345452154"
        rule<ScannerT, parser_context<>, parser_tag<long_const_id> > 		long_const;
	/// Float constant rule: "1234.3"
        rule<ScannerT, parser_context<>, parser_tag<double_const_id> > 		double_const;
	/// String constant rule: with quotes "abc"
        rule<ScannerT, parser_context<>, parser_tag<string_const_id> > 		string_const;

	/// Function call rule: func1(a,b,c) where a,b,c is a list of exprs
        rule<ScannerT, parser_context<>, parser_tag<function_call_id> > 	function_call;
	/// Function rule to match a function identifier: alphanumeric and _
	/// are allowed.
        rule<ScannerT, parser_context<>, parser_tag<function_identifier_id> > 	function_identifier;

	/// Rule to match a variable name: alphanumeric with _
        rule<ScannerT, parser_context<>, parser_tag<varname_id> > 		varname;

	/// Helper rule which implements () bracket grouping.
        rule<ScannerT, parser_context<>, parser_tag<atom_expr_id> > 		atom_expr;

	/// Unary operator rule: recognizes + - ! and "not".
        rule<ScannerT, parser_context<>, parser_tag<unary_expr_id> > 		unary_expr;
	/// Binary operator rule taking precedent before add_expr:
	/// recognizes * and /
        rule<ScannerT, parser_context<>, parser_tag<mul_expr_id> > 		mul_expr;
	/// Binary operator rule: recognizes + and -
        rule<ScannerT, parser_context<>, parser_tag<add_expr_id> > 		add_expr;

	/// Match all the allowed cast types: short, double, etc.
        rule<ScannerT, parser_context<>, parser_tag<cast_spec_id> >        	cast_spec;
	/// Cast operator written like in C: (short)
        rule<ScannerT, parser_context<>, parser_tag<cast_expr_id> >        	cast_expr;

	/// Comparison operator: recognizes == = != <= >= < > => =<
        rule<ScannerT, parser_context<>, parser_tag<comp_expr_id> >        	comp_expr;
	/// Boolean operator: recognizes && and "and" and works only on boolean
	/// values
        rule<ScannerT, parser_context<>, parser_tag<and_expr_id> >        	and_expr;
	/// Boolean operator: recognizes || and "or" and works only on boolean
	/// values
        rule<ScannerT, parser_context<>, parser_tag<or_expr_id> >        	or_expr;

	/// Base rule to match an expression 
        rule<ScannerT, parser_context<>, parser_tag<expr_id> >        		expr;
	/// Base rule to match a comma-separated list of expressions (used for
	/// function arguments and lists of expressions)
        rule<ScannerT, parser_context<>, parser_tag<exprlist_id> >    		exprlist;
    };
};

// *** Classes representing the nodes in the resulting parse tree, these need
// *** not be publicly available via the header file.

/// Constant value nodes of the parse tree. This class holds any of the three
/// constant types in the enclosed AnyScalar object.
class PNConstant : public ParseNode
{
private:
    /// The constant parsed value.
    class AnyScalar	value;

public:
    /// Assignment from the string received from the parser.
    PNConstant(AnyScalar::attrtype_t type, std::string strvalue)
	: ParseNode(), value(type)
    {
	// check whether to dequote the incoming string.
	if (type == AnyScalar::ATTRTYPE_STRING)
	    value.setStringQuoted(strvalue);
	else
	    value.setString(strvalue); // not a string, but an integer or double or boolean value
    }

    /// constructor for folded constant values.
    PNConstant(const AnyScalar &_value)
	: value(_value)
    {
    }

    /// Easiest evaluation: return the constant.
    virtual AnyScalar evaluate(const class SymbolTable &) const
    {
	return value;
    }

    /// Returns true, because value is constant
    virtual bool evaluate_const(AnyScalar *dest) const
    {
	if (dest) *dest = value;
	return true;
    }

    /// String representation of the constant AnyScalar value.
    virtual std::string toString() const
    {
	if (value.getType() == AnyScalar::ATTRTYPE_STRING) {
	    return value.getStringQuoted();
	}
	return value.getString();
    }
};

/// Parse tree node representing a variable place-holder. It is filled when
/// parameterized by a symbol table.
class PNVariable : public ParseNode
{
private:
    /// String name of the variable
    std::string		varname;

public:
    /// Constructor from the string received from the parser.
    PNVariable(std::string _varname)
	: ParseNode(), varname(_varname)
    {
    }

    /// Check the given symbol table for the actual value of this variable.
    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
	return st.lookupVariable(varname);
    }

    /// Returns false, because value isn't constant.
    virtual bool evaluate_const(AnyScalar *) const
    {
	return false;
    }

    /// Nothing but the variable name.
    virtual std::string toString() const
    {
	return varname;
    }
};

/// Parse tree node representing a function place-holder. It is filled when
/// parameterized by a symbol table.
class PNFunction : public ParseNode
{
public:
    /// Type of sequence of subtrees to evaluate as function parameters.
    typedef std::vector<const class ParseNode*> paramlist_type;

private:
    /// String name of the function
    std::string		funcname;

    /// The array of function parameter subtrees
    paramlist_type	paramlist;

public:
    /// Constructor from the string received from the parser.
    PNFunction(std::string _funcname, const paramlist_type& _paramlist)
	: ParseNode(), funcname(_funcname), paramlist(_paramlist)
    {
    }

    /// Delete the paramlist
    ~PNFunction()
    {
	for(unsigned int i = 0; i < paramlist.size(); ++i)
	    delete paramlist[i];
    }

    /// Check the given symbol table for the actual value of this variable.
    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
	std::vector<AnyScalar> paramvalues;

	for(unsigned int i = 0; i < paramlist.size(); ++i)
	{
	    paramvalues.push_back( paramlist[i]->evaluate(st) );
	}

	return st.processFunction(funcname, paramvalues);
    }

    /// Returns false, because value isn't constant.
    virtual bool evaluate_const(AnyScalar *) const
    {
	return false;
    }

    /// Nothing but the function and its parameters
    virtual std::string toString() const
    {
	std::string str = funcname + "(";
	for(unsigned int i = 0; i < paramlist.size(); ++i)
	{
	    if (i != 0) str += ",";
	    str += paramlist[i]->toString();
	}
	return str + ")";
    }
};

/// Parse tree node representing an unary operator: '+', '-', '!' or
/// "not". This node has one child.
class PNUnaryArithmExpr : public ParseNode
{
private:
    /// Pointer to the single operand
    const ParseNode 	*operand;

    /// Arithmetic operation to perform: either '+', '-' or '!'. Further
    /// optimization would be to create an extra class for each op
    char	op;

public:
    /// Constructor from the parser: operand subnode and operator id.
    PNUnaryArithmExpr(const ParseNode* _operand, char _op)
	: ParseNode(), operand(_operand), op(_op)
    {
	if (op == 'n' || op == 'N') op = '!';
    }

    /// Recursively delete the parse tree.
    virtual ~PNUnaryArithmExpr()
    {
	delete operand;
    }

    /// Applies the operator to the recursively calculated value.
    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
	AnyScalar dest = operand->evaluate(st);

	if (op == '-') {
	    dest = -dest;	    
	}
	else if (op == '!')
	{
	    // This should not happend, as types are constant in the parse tree
	    if (dest.getType() != AnyScalar::ATTRTYPE_BOOL)
		throw(BadSyntaxException("Invalid operand for !. Operand must be of type bool."));

	    dest = -dest;
 	}
	else {
	    assert(op == '+');
	}

	return dest;
    }

    /// Calculates subnodes and returns result if the operator can be applied.
    virtual bool evaluate_const(AnyScalar *dest) const
    {
	if (!dest) return false;

	bool b = operand->evaluate_const(dest);

	if (op == '-') {
	    *dest = -(*dest);
	}
	else if (op == '!')
	{
	    if (dest->getType() != AnyScalar::ATTRTYPE_BOOL)
		throw(BadSyntaxException("Invalid operand for !. Operand must be of type bool."));

	    *dest = -(*dest);
	}
	else {
	    assert(op == '+');
	}
	
	return b;
    }

    /// Return the subnode's string with this operator prepended.
    virtual std::string toString() const
    {
	return std::string("(") + op + " " + operand->toString() + ")";
    }
};

/// Parse tree node representing a binary operators: +, -, * and / for numeric
/// values. This node has two children.
class PNBinaryArithmExpr : public ParseNode
{
private:
    /// Pointers to the left of the two child parse trees.
    const ParseNode 	*left;

    /// Pointers to the right of the two child parse trees.
    const ParseNode	*right;

    /// Arithmetic operation to perform: left op right.
    /// Further optimization would be to create an extra class for each op
    char	op;

public:
    /// Constructor from the parser: both operand subnodes and the operator id.
    PNBinaryArithmExpr(const ParseNode* _left,
		       const ParseNode* _right,
		       char _op)
	: ParseNode(),
	  left(_left), right(_right), op(_op)
    { }

    /// Recursively delete parse tree.
    virtual ~PNBinaryArithmExpr()
    {
	delete left;
	delete right;
    }

    /// Applies the operator to the two recursive calculated values. The actual
    /// switching between types is handled by AnyScalar's operators.
    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
	AnyScalar vl = left->evaluate(st);
	AnyScalar vr = right->evaluate(st);

	if (op == '+') {
	    return (vl + vr);
	}
	else if (op == '-') {
	    return (vl - vr);
	}
	else if (op == '*') {
	    return (vl * vr);
	}
	else if (op == '/') {
	    return (vl / vr);
	}

	assert(0);
	return 0;
    }

    /// Returns false because this node isn't always constant. Tries to
    /// calculate a constant subtree's value.
    virtual bool evaluate_const(AnyScalar *dest) const
    {
	if (!dest) return false;

	AnyScalar vl(AnyScalar::ATTRTYPE_INVALID), vr(AnyScalar::ATTRTYPE_INVALID);
	
	bool bl = left->evaluate_const(&vl);
	bool br = right->evaluate_const(&vr);

	if (op == '+') {
	    *dest = vl + vr;
	}
	else if (op == '-') {
	    *dest = vl - vr;
	}
	else if (op == '*') {
	    *dest = vl * vr;
	}
	else if (op == '/') {
	    *dest = vl / vr;
	}

	return (bl && br);
    }

    /// String representing (operandA op operandB)
    virtual std::string toString() const
    {
	return std::string("(") + left->toString() + " " + op + " " + right->toString() + ")";
    }
};

/// Parse tree node handling type conversions within the tree.
class PNCastExpr : public ParseNode
{
private:
    /// Child tree of which the return value should be casted.
    const ParseNode*	operand;

    /// AnyScalar type to cast the value to.
    AnyScalar::attrtype_t	type;

public:
    /// Constructor from the parser: operand subnode and the cast type as
    /// recognized by AnyScalar.
    PNCastExpr(const ParseNode* _operand, AnyScalar::attrtype_t _type)
	: ParseNode(),
	  operand(_operand), type(_type)
    { }

    /// Recursively delete parse tree.
    virtual ~PNCastExpr()
    {
	delete operand;
    }

    /// Recursive calculation of the value and subsequent casting via
    /// AnyScalar's convertType method.
    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
	AnyScalar val = operand->evaluate(st);
	val.convertType(type);
	return val;
    }

    /// Returns false because this node isn't always constant.
    virtual bool evaluate_const(AnyScalar *dest) const
    {
	if (!dest) return false;

	bool b = operand->evaluate_const(dest);
	dest->convertType(type);
	return b;
    }

    /// c-like representation of the cast
    virtual std::string toString() const
    {
	return std::string("((") + AnyScalar::getTypeString(type) + ")" + operand->toString() + ")";
    }
};

/// Parse tree node representing a binary comparison operator: ==, =, !=, <, >,
/// >=, <=, =>, =<. This node has two children.
class PNBinaryComparisonExpr : public ParseNode
{
private:
    /// Pointers to the left of the two child parse trees.
    const ParseNode 	*left;

    /// Pointers to the right of the two child parse trees.
    const ParseNode	*right;

    /// Comparison operation to perform: left op right
    enum { EQUAL, NOTEQUAL, LESS, GREATER, LESSEQUAL, GREATEREQUAL } op;

    /// String saved for toString()
    std::string		opstr;

public:
    /// Constructor from the parser: both operand subnodes and the operator id.
    PNBinaryComparisonExpr(const ParseNode* _left,
			   const ParseNode* _right,
			   std::string _op)
	: ParseNode(),
	  left(_left), right(_right), opstr(_op)
    {
	if (_op == "==" || _op == "=")
	    op = EQUAL;
	else if (_op == "!=")
	    op = NOTEQUAL;
	else if (_op == "<")
	    op = LESS;
	else if (_op == ">")
	    op = GREATER;
	else if (_op == "<=" || _op == "=<")
	    op = LESSEQUAL;
	else if (_op == ">=" || _op == "=>")
	    op = GREATEREQUAL;
	else
	    throw(BadSyntaxException("Program Error: invalid binary comparision operator."));
    }

    /// Recursively delete parse tree.
    virtual ~PNBinaryComparisonExpr()
    {
	delete left;
	delete right;
    }

    /// Applies the operator to the two recursive calculated values. The actual
    /// switching between types is handled by AnyScalar's operators. This
    /// result type of this processing node is always bool.
    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
	AnyScalar vl = left->evaluate(st);
	AnyScalar vr = right->evaluate(st);

	AnyScalar dest(AnyScalar::ATTRTYPE_BOOL);

	switch(op)
	{
	case EQUAL:
	    dest = AnyScalar( vl.equal_to(vr) );
	    break;

	case NOTEQUAL:
	    dest = AnyScalar( vl.not_equal_to(vr) );
	    break;

	case LESS:
	    dest = AnyScalar( vl.less(vr) );
	    break;

	case GREATER:
	    dest = AnyScalar( vl.greater(vr) );
	    break;

	case LESSEQUAL:
	    dest = AnyScalar( vl.less_equal(vr) );
	    break;

	case GREATEREQUAL:
	    dest = AnyScalar( vl.greater_equal(vr) );
	    break;

	default:
	    assert(0);
	}

	return dest;
    }

    /// Returns false because this node isn't always constant.
    virtual bool evaluate_const(AnyScalar *dest) const
    {
	if (!dest) return false;

	AnyScalar vl(AnyScalar::ATTRTYPE_INVALID), vr(AnyScalar::ATTRTYPE_INVALID);
	
	bool bl = left->evaluate_const(&vl);
	bool br = right->evaluate_const(&vr);

	switch(op)
	{
	case EQUAL:
	    *dest = AnyScalar( vl.equal_to(vr) );
	    break;

	case NOTEQUAL:
	    *dest = AnyScalar( vl.not_equal_to(vr) );
	    break;

	case LESS:
	    *dest = AnyScalar( vl.less(vr) );
	    break;

	case GREATER:
	    *dest = AnyScalar( vl.greater(vr) );
	    break;

	case LESSEQUAL:
	    *dest = AnyScalar( vl.less_equal(vr) );
	    break;

	case GREATEREQUAL:
	    *dest = AnyScalar( vl.greater_equal(vr) );
	    break;

	default:
	    assert(0);
	}

	return (bl && br);
    }

    /// String (operandA op operandB)
    virtual std::string toString() const
    {
	return std::string("(") + left->toString() + " " + opstr + " " + right->toString() + ")";
    }
};

/// Parse tree node representing a binary logic operator: and, or, &&, ||. This
/// node has two children.
class PNBinaryLogicExpr : public ParseNode
{
private:
    /// Pointers to the left of the two child parse trees.
    ParseNode*		left;

    /// Pointers to the right of the two child parse trees.
    ParseNode*		right;

    /// Comparison operation to perform: left op right
    enum { OP_AND, OP_OR } op;

public:
    /// Constructor from the parser: both operand subnodes and the operator id.
    PNBinaryLogicExpr(ParseNode* _left,
		      ParseNode* _right,
		      std::string _op)
	: ParseNode(),
	  left(_left), right(_right)
    {
	if (_op == "and" || _op == "&&")
	    op = OP_AND;
	else if (_op == "or" || _op == "||")
	    op = OP_OR;
	else
	    throw(BadSyntaxException("Program Error: invalid binary logic operator."));
    }

    /// Recursively delete parse tree.
    virtual ~PNBinaryLogicExpr()
    {
	if (left) delete left;
	if (right) delete right;
    }

    /// Calculate the operator
    inline bool do_operator(bool left, bool right) const
    {
	if (op == OP_AND)
	    return left && right;
	else if (op == OP_OR)
	    return left || right;
	else
	    return false;
    }

    /// Return the string of this operator
    inline std::string get_opstr() const
    {
	return (op == OP_AND) ? "&&" : "||";
    }

    /// Applies the operator to the two recursive calculated values. The actual
    /// switching between types is handled by AnyScalar's operators.
    virtual AnyScalar evaluate(const class SymbolTable &st) const
    {
	AnyScalar vl = left->evaluate(st);
	AnyScalar vr = right->evaluate(st);

	// these should never happen.
	if (vl.getType() != AnyScalar::ATTRTYPE_BOOL)
	    throw(BadSyntaxException(std::string("Invalid left operand for ") + get_opstr() + ". Both operands must be of type bool."));
	if (vr.getType() != AnyScalar::ATTRTYPE_BOOL)
	    throw(BadSyntaxException(std::string("Invalid right operand for ") + get_opstr() + ". Both operands must be of type bool."));

	int bvl = vl.getInteger();
	int bvr = vr.getInteger();

	return AnyScalar( do_operator(bvl, bvr) );
    }

    /// Applies the operator to the two recursive calculated const
    /// values. Determining if this node is constant is somewhat more tricky
    /// than with the other parse nodes: AND with a false operand is always
    /// false. OR with a true operand is always true.
    virtual bool evaluate_const(AnyScalar *dest) const
    {
	if (!dest) return false; // returns false because this node isn't always constant

	AnyScalar vl(AnyScalar::ATTRTYPE_INVALID), vr(AnyScalar::ATTRTYPE_INVALID);
	
	bool bl = left->evaluate_const(&vl);
	bool br = right->evaluate_const(&vr);

	if (vl.getType() != AnyScalar::ATTRTYPE_BOOL)
	    throw(BadSyntaxException(std::string("Invalid left operand for ") + get_opstr() + ". Both operands must be of type bool."));
	if (vr.getType() != AnyScalar::ATTRTYPE_BOOL)
	    throw(BadSyntaxException(std::string("Invalid right operand for ") + get_opstr() + ". Both operands must be of type bool."));

	int bvl = vl.getInteger();
	int bvr = vr.getInteger();

	*dest = AnyScalar( do_operator(bvl, bvr) );

	if (op == OP_AND)
	{
	    // true if either both ops are themselves constant, or if either of
	    // the ops are constant and evaluates to false.
	    return (bl && br) || (bl && !bvl) || (br && !bvr);
	}
	else if (op == OP_OR)
	{
	    // true if either both ops are themselves constant, or if either of
	    // the ops is constant and evaluates to true.
	    return (bl && br) || (bl && bvl) || (br && bvr);
	}
	else {
	    assert(0);
	    return false;
	}
    }

    /// String (operandA op operandB)
    virtual std::string toString() const
    {
	return std::string("(") + left->toString() + " " + get_opstr() + " " + right->toString() + ")";
    }

    /// Detach left node
    inline ParseNode* detach_left()
    {
	ParseNode *n = left;
	left = NULL;
	return n;
    }

    /// Detach right node
    inline ParseNode* detach_right()
    {
	ParseNode *n = right;
	right = NULL;
	return n;
    }
};

// *** Functions which translate the resulting parse tree into our expression
// *** tree, simultaneously folding constants.

/// Iterator type used by spirit's parsers.
typedef std::string::const_iterator InputIterT;

/// Resulting match tree after parsing
typedef tree_match<InputIterT> ParseTreeMatchT;

/// The iterator of the match tree used in build_expr()
typedef ParseTreeMatchT::const_tree_iterator TreeIterT;

/// Build_expr is the constructor method to create a parse tree from the
/// AST-tree returned by the spirit parser.
static ParseNode* build_expr(TreeIterT const& i)
{
#ifdef STX_DEBUG_PARSER
    std::cout << "In build_expr. i->value = " <<
        std::string(i->value.begin(), i->value.end()) <<
        " i->children.size() = " << i->children.size() << 
	" i->value.id = " << i->value.id().to_long() << std::endl;
#endif

    switch(i->value.id().to_long())
    {
    // *** Constant node cases

    case boolean_const_id:
    {
	return new PNConstant(AnyScalar::ATTRTYPE_BOOL,
			      std::string(i->value.begin(), i->value.end()));
    }

    case integer_const_id:
    {
	return new PNConstant(AnyScalar::ATTRTYPE_INTEGER,
			      std::string(i->value.begin(), i->value.end()));
    }

    case long_const_id:
    {
	return new PNConstant(AnyScalar::ATTRTYPE_LONG,
			      std::string(i->value.begin(), i->value.end()));
    }

    case double_const_id:
    {
	return new PNConstant(AnyScalar::ATTRTYPE_DOUBLE,
			      std::string(i->value.begin(), i->value.end()));
    }

    case string_const_id:
    {
	return new PNConstant(AnyScalar::ATTRTYPE_STRING,
			      std::string(i->value.begin(), i->value.end()));
    }

    // *** Arithmetic node cases

    case unary_expr_id:
    {
	char arithop = *i->value.begin();
	assert(i->children.size() == 1);

	const ParseNode *val = build_expr(i->children.begin());

	if (val->evaluate_const(NULL))
	{
	    // construct a constant node
	    PNUnaryArithmExpr tmpnode(val, arithop);
	    AnyScalar constval(AnyScalar::ATTRTYPE_INVALID);

	    tmpnode.evaluate_const(&constval);

	    return new PNConstant(constval);
	}
	else
	{
	    // calculation node
	    return new PNUnaryArithmExpr(val, arithop);
	}
    }

    case add_expr_id:
    case mul_expr_id:
    {
	char arithop = *i->value.begin();
	assert(i->children.size() == 2);

	// auto_ptr needed because of possible parse exceptions in build_expr.

	std::auto_ptr<const ParseNode> left( build_expr(i->children.begin()) );
	std::auto_ptr<const ParseNode> right( build_expr(i->children.begin()+1) );

	if (left->evaluate_const(NULL) && right->evaluate_const(NULL))
	{
	    // construct a constant node
	    PNBinaryArithmExpr tmpnode(left.release(), right.release(), arithop);
	    AnyScalar both(AnyScalar::ATTRTYPE_INVALID);

	    tmpnode.evaluate_const(&both);

	    // left and right are deleted by tmpnode's deconstructor

	    return new PNConstant(both);
	}
	else
	{
	    // calculation node
	    return new PNBinaryArithmExpr(left.release(), right.release(), arithop);
        }
    }

    // *** Cast node case

    case cast_spec_id:
    {
	assert(i->children.size() == 1);

	std::string tname(i->value.begin(), i->value.end());
	AnyScalar::attrtype_t at = AnyScalar::stringToType(tname);
	
	const ParseNode *val = build_expr(i->children.begin());

	if (val->evaluate_const(NULL))
	{
	    // construct a constant node
	    PNCastExpr tmpnode(val, at);

	    AnyScalar constval(AnyScalar::ATTRTYPE_INVALID);

	    tmpnode.evaluate_const(&constval);

	    return new PNConstant(constval);
	}
	else
	{
	    return new PNCastExpr(val, at);
	}
    }

    // *** Binary Comparison Operator

    case comp_expr_id:
    {
	assert(i->children.size() == 2);

	std::string arithop(i->value.begin(), i->value.end());

	// we need auto_ptr because of possible parse exceptions in build_expr.

	std::auto_ptr<const ParseNode> left( build_expr(i->children.begin()) );
	std::auto_ptr<const ParseNode> right( build_expr(i->children.begin()+1) );

	if (left->evaluate_const(NULL) && right->evaluate_const(NULL))
	{
	    // construct a constant node
	    PNBinaryComparisonExpr tmpnode(left.release(), right.release(), arithop);
	    AnyScalar both(AnyScalar::ATTRTYPE_INVALID);

	    tmpnode.evaluate_const(&both);

	    // left and right are deleted by tmpnode's deconstructor

	    return new PNConstant(both);
	}
	else
	{
	    // calculation node
	    return new PNBinaryComparisonExpr(left.release(), right.release(), arithop);
        }
    }

    // *** Binary Logic Operator

    case and_expr_id:
    case or_expr_id:
    {
	assert(i->children.size() == 2);

	std::string logicop(i->value.begin(), i->value.end());
	std::transform(logicop.begin(), logicop.end(), logicop.begin(), tolower);

	// auto_ptr needed because of possible parse exceptions in build_expr.

	std::auto_ptr<ParseNode> left( build_expr(i->children.begin()) );
	std::auto_ptr<ParseNode> right( build_expr(i->children.begin()+1) );

	bool constleft = left->evaluate_const(NULL);
	bool constright = right->evaluate_const(NULL);

	// a logical node is constant if one of the two ops is constant. so we
	// construct a calculation node and check later.
	std::auto_ptr<PNBinaryLogicExpr> node( new PNBinaryLogicExpr(left.release(), right.release(), logicop) );

	if (constleft || constright)
	{
	    AnyScalar both(AnyScalar::ATTRTYPE_INVALID);

	    // test if the node is really const.
	    if (node->evaluate_const(&both))
	    {
		// return a constant node instead, node will be deleted by
		// auto_ptr, left,right by node's destructor.
		return new PNConstant(both);
	    }
	}
	if (constleft)
	{
	    // left node is constant, but the evaluation is not
	    // -> only right node is meaningful.
	    return node->detach_right();
	}
	if (constright)
	{
	    // right node is constant, but the evaluation is not
	    // -> only left node is meaningful.
	    return node->detach_left();
	}

	return node.release();
    }

    // *** Variable and Function name place-holder

    case varname_id:
    {
	assert(i->children.size() == 0);

	std::string varname(i->value.begin(), i->value.end());

        return new PNVariable(varname);
    }

    case function_identifier_id:
    {
	std::string funcname(i->value.begin(), i->value.end());
	std::vector<const class ParseNode*> paramlist;

	if (i->children.size() > 0)
	{
	    TreeIterT const& paramlistchild = i->children.begin();

	    if (paramlistchild->value.id().to_long() == exprlist_id)
	    {
		try
		{
		    for(TreeIterT ci = paramlistchild->children.begin(); ci != paramlistchild->children.end(); ++ci)
		    {
			const ParseNode *pas = build_expr(ci);
			paramlist.push_back(pas);
		    }
		}
		catch (...) // need to clean-up
		{
		    for(unsigned int i = 0; i < paramlist.size(); ++i)
			delete paramlist[i];
		    throw;
		}
	    }
	    else
	    {
		// just one subnode and its not a full expression list
		paramlist.push_back( build_expr(paramlistchild) );
	    }
	}

        return new PNFunction(funcname, paramlist);
    }

    default:
	throw(ExpressionParserException("Unknown AST parse tree node found. This should never happen."));
    }
}

/// build_exprlist constructs the vector holding the ParseNode parse tree for
/// each parse tree.
ParseTreeList build_exprlist(TreeIterT const &i)
{
#ifdef STX_DEBUG_PARSER
    std::cout << "In build_exprlist. i->value = " <<
        std::string(i->value.begin(), i->value.end()) <<
        " i->children.size() = " << i->children.size() << 
	" i->value.id = " << i->value.id().to_long() << std::endl;
#endif

    ParseTreeList ptlist;

    for(TreeIterT ci = i->children.begin(); ci != i->children.end(); ++ci)
    {
	ParseNode *vas = build_expr(ci);

	ptlist.push_back( ParseTree(vas) );
    }

    return ptlist;
}

/// Uses boost::spirit function to convert the parse tree into a XML document.
static inline void tree_dump_xml(std::ostream &os, const std::string &input, const tree_parse_info<InputIterT> &info)
{
    // map used by the xml dumper to label the nodes

    std::map<parser_id, std::string> rule_names;

    rule_names[boolean_const_id] = "boolean_const";
    rule_names[integer_const_id] = "integer_const";
    rule_names[long_const_id] = "long_const";
    rule_names[double_const_id] = "double_const";
    rule_names[string_const_id] = "string_const";
    rule_names[constant_id] = "constant";

    rule_names[function_call_id] = "function_call";
    rule_names[function_identifier_id] = "function_identifier";

    rule_names[varname_id] = "varname";

    rule_names[unary_expr_id] = "unary_expr";
    rule_names[mul_expr_id] = "mul_expr";
    rule_names[add_expr_id] = "add_expr";

    rule_names[cast_expr_id] = "cast_expr";
    rule_names[cast_spec_id] = "cast_spec";

    rule_names[comp_expr_id] = "comp_expr";
    rule_names[and_expr_id] = "and_expr";
    rule_names[or_expr_id] = "or_expr";

    rule_names[expr_id] = "expr";
    rule_names[exprlist_id] = "exprlist";

    tree_to_xml(os, info.trees, input.c_str(), rule_names);
}

} // namespace Grammar

const ParseTree parseExpression(const std::string &input)
{
    // instance of the grammar
    Grammar::ExpressionGrammar g;

#ifdef STX_DEBUG_PARSER
    BOOST_SPIRIT_DEBUG_GRAMMAR(g);
#endif

    Grammar::tree_parse_info<Grammar::InputIterT> info =
	boost::spirit::ast_parse(input.begin(), input.end(),
				 g.use_parser<0>(),	// use first entry point: expr
				 boost::spirit::space_p);

    if (!info.full)
    {
	std::ostringstream oss;
	oss << "Syntax error at position "
	    << static_cast<int>(info.stop - input.begin())
	    << " near " 
	    << std::string(info.stop, input.end());

	throw(BadSyntaxException(oss.str()));
    }

    return ParseTree( Grammar::build_expr(info.trees.begin()) );
}

std::string parseExpressionXML(const std::string &input)
{
    // instance of the grammar
    Grammar::ExpressionGrammar g;

#ifdef STX_DEBUG_PARSER
    BOOST_SPIRIT_DEBUG_GRAMMAR(g);
#endif

    Grammar::tree_parse_info<Grammar::InputIterT> info =
	boost::spirit::ast_parse(input.begin(), input.end(),
				 g.use_parser<0>(),	// use first entry point: expr
				 boost::spirit::space_p);

    if (!info.full)
    {
	std::ostringstream oss;
	oss << "Syntax error at position "
	    << static_cast<int>(info.stop - input.begin())
	    << " near " 
	    << std::string(info.stop, input.end());

	throw(BadSyntaxException(oss.str()));
    }

    std::ostringstream oss;
    Grammar::tree_dump_xml(oss, input, info);
    return oss.str();
}

ParseTreeList parseExpressionList(const std::string &input)
{
    // instance of the grammar
    Grammar::ExpressionGrammar g;

#ifdef STX_DEBUG_PARSER
    BOOST_SPIRIT_DEBUG_GRAMMAR(g);
#endif

    Grammar::tree_parse_info<Grammar::InputIterT> info =
	boost::spirit::ast_parse(input.begin(), input.end(),
				 g.use_parser<1>(),	// use second entry point: exprlist
				 boost::spirit::space_p);

    if (!info.full)
    {
	std::ostringstream oss;
	oss << "Syntax error at position "
	    << static_cast<int>(info.stop - input.begin())
	    << " near " 
	    << std::string(info.stop, input.end());

	throw(BadSyntaxException(oss.str()));
    }

    return Grammar::build_exprlist(info.trees.begin());
}

std::vector<AnyScalar> ParseTreeList::evaluate(const class SymbolTable &st) const
{
    std::vector<AnyScalar> vl;

    for(parent_type::const_iterator i = parent_type::begin(); i != parent_type::end(); i++)
    {
	vl.push_back( i->evaluate(st) );
    }

    return vl;
}

std::string ParseTreeList::toString() const
{
    std::string sl;

    for(parent_type::const_iterator i = parent_type::begin(); i != parent_type::end(); i++)
    {
	if (i != parent_type::begin()) {
	    sl += ", ";
	}

	sl += i->toString();
    }

    return sl;
}

/// *** SymbolTable, EmptySymbolTable and BasicSymbolTable implementation

SymbolTable::~SymbolTable()
{
}

EmptySymbolTable::~EmptySymbolTable()
{
}

AnyScalar EmptySymbolTable::lookupVariable(const std::string &varname) const
{
    throw(UnknownSymbolException(std::string("Unknown variable ") + varname));
}

AnyScalar EmptySymbolTable::processFunction(const std::string &funcname,
					    const paramlist_type &) const
{
    throw(UnknownSymbolException(std::string("Unknown function ") + funcname + "()"));
}

BasicSymbolTable::BasicSymbolTable()
{
    addStandardFunctions();
}

BasicSymbolTable::~BasicSymbolTable()
{
}

void BasicSymbolTable::setVariable(const std::string& varname, const AnyScalar &value)
{
    std::string vn = varname;
    std::transform(vn.begin(), vn.end(), vn.begin(), tolower);

    variablemap[vn] = value;
}

void BasicSymbolTable::setFunction(const std::string& funcname, int arguments, functionptr_type funcptr)
{
    std::string fn = funcname;
    std::transform(fn.begin(), fn.end(), fn.begin(), toupper);

    functionmap[fn] = FunctionInfo(arguments, funcptr);
}

void BasicSymbolTable::clearVariables()
{
    variablemap.clear();
}

void BasicSymbolTable::clearFunctions()
{
    functionmap.clear();
}

AnyScalar BasicSymbolTable::funcPI(const paramlist_type &)
{
    return AnyScalar(3.14159265358979323846);
}

AnyScalar BasicSymbolTable::funcSIN(const paramlist_type &paramlist)
{
    return AnyScalar( std::sin(paramlist[0].getDouble()) );
}

AnyScalar BasicSymbolTable::funcCOS(const paramlist_type &paramlist)
{
    return AnyScalar( std::cos(paramlist[0].getDouble()) );
}

AnyScalar BasicSymbolTable::funcTAN(const paramlist_type &paramlist)
{
    return AnyScalar( std::tan(paramlist[0].getDouble()) );
}

AnyScalar BasicSymbolTable::funcABS(const paramlist_type &paramlist)
{
    if (paramlist[0].isIntegerType()) {
	return AnyScalar( std::abs(paramlist[0].getInteger()) );
    }
    else if (paramlist[0].isFloatingType()) {
	return AnyScalar( std::fabs(paramlist[0].getDouble()) );
    }
    else {
	throw(BadFunctionCallException("Function ABS() takes exactly one parameter"));
    }
}

AnyScalar BasicSymbolTable::funcEXP(const paramlist_type &paramlist)
{
    return AnyScalar( std::exp(paramlist[0].getDouble()) );
}

AnyScalar BasicSymbolTable::funcLOGN(const paramlist_type &paramlist)
{
    return AnyScalar( std::log(paramlist[0].getDouble()) );
}

AnyScalar BasicSymbolTable::funcPOW(const paramlist_type &paramlist)
{
    return AnyScalar( std::pow(paramlist[0].getDouble(), paramlist[1].getDouble()) );
}

AnyScalar BasicSymbolTable::funcSQRT(const paramlist_type &paramlist)
{
    return AnyScalar( std::sqrt(paramlist[0].getDouble()) );
}

void BasicSymbolTable::addStandardFunctions()
{
    setFunction("PI", 0, funcPI);

    setFunction("SIN", 1, funcSIN);
    setFunction("COS", 1, funcCOS);
    setFunction("TAN", 1, funcTAN);

    setFunction("ABS", 1, funcABS);
    setFunction("EXP", 1, funcEXP);
    setFunction("LOGN", 1, funcLOGN);
    setFunction("POW", 2, funcPOW);
    setFunction("SQRT", 1, funcSQRT);
}

AnyScalar BasicSymbolTable::lookupVariable(const std::string &_varname) const
{
    std::string varname = _varname;
    std::transform(varname.begin(), varname.end(), varname.begin(), tolower);

    variablemap_type::const_iterator fi = variablemap.find(varname);

    if (fi != variablemap.end())
    {
	return fi->second;
    }

    throw(UnknownSymbolException(std::string("Unknown variable ") + varname));
}

AnyScalar BasicSymbolTable::processFunction(const std::string &_funcname,
					    const paramlist_type &paramlist) const
{
    std::string funcname = _funcname;
    std::transform(funcname.begin(), funcname.end(), funcname.begin(), toupper);

    functionmap_type::const_iterator fi = functionmap.find(funcname);

    if (fi != functionmap.end())
    {
	if (fi->second.arguments >= 0)
	{
	    if (fi->second.arguments == 0 && paramlist.size() != 0)
	    {
		throw(BadFunctionCallException(std::string("Function ") + funcname + "() does not take any parameter."));
	    }
	    else if (fi->second.arguments == 1 && paramlist.size() != 1)
	    {
		throw(BadFunctionCallException(std::string("Function ") + funcname + "() takes exactly one parameter."));
	    }
	    else if (static_cast<unsigned int>(fi->second.arguments) != paramlist.size())
	    {
		std::ostringstream oss;
		oss << "Function " << funcname << "() takes exactly " << fi->second.arguments << " parameters.";
		throw(BadFunctionCallException(oss.str()));
	    }
	}
	return fi->second.func(paramlist);
    }

    throw(UnknownSymbolException(std::string("Unknown function ") + funcname + "()"));
}

} // namespace stx