<commit_before>/*
 * This file is part of Mapyrus, software for plotting maps.
 * Copyright (C) 2003 <NAME>.
 *
 * Mapyrus 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.
 *
 * Mapyrus 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 for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Mapyrus; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */

/*
 * @(#) $Id$
 */
package au.id.chenery.mapyrus;

import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.regex.PatternSyntaxException;
import java.io.*;

/**
 * An expression tree.  Parser for numeric or string expression that builds
 * a binary tree holding the expression.  The expression can be later 
 * be evaluated and the tree is evaluated to a single value.
 *
 * For example, the expression '(a * 2) + 7' is represented by the tree:
 * <pre>
 *       +
 *      / \
 *     *   7
 *    / \
 *   a   2
 * </pre>
 */
public class Expression
{
	/*
	 * Types of operations allowed between two numbers or strings
	 * (or two expressions).
	 */
	private static final int NO_OPERATION = 0;
	private static final int PLUS_OPERATION = 1;
	private static final int CONCAT_OPERATION = 2; /* 'qw' . 'er' . 7 = 'qwer7' */
	private static final int MINUS_OPERATION = 3;
	private static final int MULTIPLY_OPERATION = 4;
	private static final int REPEAT_OPERATION = 5;	/* 'qw' x 2 = 'qwqw' */
	private static final int DIVIDE_OPERATION = 6;
	private static final int MODULO_OPERATION = 7;

	private static final int LEXICAL_EQUALS_OPERATION = 100;	/* 'foo' eq 'foo' */
	private static final int LEXICAL_NOT_EQUALS_OPERATION = 101;	/* 'foo' ne 'qw' */
	private static final int LEXICAL_GREATER_THAN_OPERATION = 102;	/* 'qw' gt 'foo' */
	private static final int LEXICAL_LESS_THAN_OPERATION = 103;	/* 'foo' lt 'qw' */
	private static final int LEXICAL_GREATER_EQUAL_OPERATION = 104;	/* 'qw' ge 'foo' */
	private static final int LEXICAL_LESS_EQUAL_OPERATION = 105;	/* 'foo' le 'qw' */

	private static final int NUMERIC_EQUALS_OPERATION = 200;	/* 77 == 77 */
	private static final int NUMERIC_NOT_EQUALS_OPERATION = 201;	/* 7 != 77 */
	private static final int NUMERIC_GREATER_THAN_OPERATION = 202;	/* 77 > 7 */
	private static final int NUMERIC_LESS_THAN_OPERATION = 203;	/* 7 < 77 */
	private static final int NUMERIC_GREATER_EQUAL_OPERATION = 204;	/* 77 >= 7 */
	private static final int NUMERIC_LESS_EQUAL_OPERATION = 205;	/* 7 <= 77 */

	private static final int ASSIGN_OPERATION = 300;	/* a = 77 */

	private static final int AND_OPERATION = 400;
	private static final int OR_OPERATION = 401;
	private static final int NOT_OPERATION = 402;
	
	private static final int HASHMAP_REFERENCE = 500;		/* a[77] */

	/*
	 * Names and types of functions we allow on numbers and strings.
	 */
	private static final int ROUND_FUNCTION = 1;	/* round(3.14) = 3 */
	private static final String ROUND_FUNCTION_NAME = "round";
	private static final int RANDOM_FUNCTION = 2;	/* random(3) = [0, 3) */
	private static final String RANDOM_FUNCTION_NAME = "random";
	private static final int LOG10_FUNCTION = 3;	/* log10(1000) = 3 */
	private static final String LOG10_FUNCTION_NAME = "log10";
	private static final int LENGTH_FUNCTION = 4;	/* length("foo") = 3 */
	private static final String LENGTH_FUNCTION_NAME = "length";
	private static final int MATCH_FUNCTION = 5;	/* match('foobar', 'ob') = 3 */
	private static final String MATCH_FUNCTION_NAME = "match";
	private static final int REPLACE_FUNCTION = 6;	/* replace('foobar', 'o*', '_') =  'f_bar' */
	private static final String REPLACE_FUNCTION_NAME = "replace";
	private static final int TEMPNAME_FUNCTION = 7;	/* tempname('.jpg') =  'tmpABC123.jpg' */
	private static final String TEMPNAME_FUNCTION_NAME = "tempname";
	private static final int SUBSTR_FUNCTION = 8;	/* substr('foobar', 2, 3) = 'oob' */
	private static final String SUBSTR_FUNCTION_NAME = "substr";

	/*
	 * Constant for calculating base 10 logarithms.
	 */
	private static final double LOG_OF_10 = Math.log(10.0);
	
	/*
	 * Lookup tables of functions and the number of
	 * arguments that they each take.
	 */
	private static final HashMap mFunctionTypeLookup;
	private static final byte[] mFunctionArgumentCount;
	
	static
	{
		mFunctionTypeLookup = new HashMap();
		mFunctionTypeLookup.put(ROUND_FUNCTION_NAME, new Integer(ROUND_FUNCTION));
		mFunctionTypeLookup.put(RANDOM_FUNCTION_NAME, new Integer(RANDOM_FUNCTION));
		mFunctionTypeLookup.put(LOG10_FUNCTION_NAME, new Integer(LOG10_FUNCTION));
		mFunctionTypeLookup.put(LENGTH_FUNCTION_NAME, new Integer(LENGTH_FUNCTION));
		mFunctionTypeLookup.put(MATCH_FUNCTION_NAME, new Integer(MATCH_FUNCTION));
		mFunctionTypeLookup.put(REPLACE_FUNCTION_NAME, new Integer(REPLACE_FUNCTION));
		mFunctionTypeLookup.put(TEMPNAME_FUNCTION_NAME, new Integer(TEMPNAME_FUNCTION));
		mFunctionTypeLookup.put(SUBSTR_FUNCTION_NAME, new Integer(SUBSTR_FUNCTION));
		
		mFunctionArgumentCount = new byte[SUBSTR_FUNCTION + 1];
		mFunctionArgumentCount[ROUND_FUNCTION] = 1;
		mFunctionArgumentCount[RANDOM_FUNCTION] = 1;
		mFunctionArgumentCount[LOG10_FUNCTION] = 1;
		mFunctionArgumentCount[LENGTH_FUNCTION] = 1;
		mFunctionArgumentCount[MATCH_FUNCTION] = 2;
		mFunctionArgumentCount[REPLACE_FUNCTION] = 3;
		mFunctionArgumentCount[TEMPNAME_FUNCTION] = 1;
		mFunctionArgumentCount[SUBSTR_FUNCTION] = 3;
	}

	/*
	 * Maximum number of compiled regular expressions we'll cache.
	 */
	private static final int MAX_COMPILED_REGEX = 100;
	
	/*
	 * Static table of frequently used regular expressions.
	 */
	private static LRUCache mRegexCache = new LRUCache(MAX_COMPILED_REGEX);

	/**
	 * Compile a regular expression string into a Pattern that can be used for matching.
	 * Patterns are cached to avoid recomputing them again and again.
	 * Synchronized because LRUCache is not thread-safe.
	 * @param regex is regular expression to compile.
	 * @return compiled pattern
	 */
	private static synchronized Pattern compileRegex(String regex) throws MapyrusException
	{
		Pattern retval = (Pattern)(mRegexCache.get(regex));

		if (retval == null)
		{
			try
			{
				retval = Pattern.compile(regex);
			}
			catch (PatternSyntaxException e)
			{
				throw new MapyrusException(MapyrusMessages.get(MapyrusMessages.INVALID_REGEX) +
					": " + e.getMessage());
			}

			/*
			 * Cache newly compiled regular expression.
			 */
			mRegexCache.put(regex, retval);
		}
		return(retval);
	}

	/*
	 * Nodes in binary tree describing an arithmetic expression.
	 */
	private class ExpressionTreeNode
	{
		boolean mIsLeaf;
		Argument mLeafArg;

		int mOperation;
		ExpressionTreeNode mLeftBranch, mRightBranch;

		boolean mIsFunction;
		int mFunction;
		ExpressionTreeNode mThirdFunctionExpression;

		/**
		 * Create a leaf value containing either a number,
		 * string or variable name.
		 * @param arg is leaf argument value.
		 */
		public ExpressionTreeNode(Argument arg)
		{
			mIsLeaf = true;
			mIsFunction = false;
			mLeafArg = arg;
		}
	
		/**
		 * Create a node joining two sub-expressions with an
		 * operation between them.
		 * @param left is left hand side of expression.
		 * @param operation is operation between left and right handside expressions.
		 * @param right is right hand side of expression.
		 */
		public ExpressionTreeNode(ExpressionTreeNode left,
			int operation,
			ExpressionTreeNode right)
		{
			mIsLeaf = mIsFunction = false;			
			mLeftBranch = left;
			mRightBranch = right;
			mOperation = operation;
		}

		/**
		 * Create a node containing a call to a function.
		 * @param functionType is identifier of function being called.
		 * @param arg1 is first argument to function.
		 * @param arg2 is second argument to function (or null for single
		 * argument functions).
		 * @param arg3 is third argument to function (or null for functions
		 * with less than 3 arguments)
		 */
		public ExpressionTreeNode(int functionType, ExpressionTreeNode arg1,
			ExpressionTreeNode arg2, ExpressionTreeNode arg3)
		{
			mIsLeaf = false;
			mIsFunction = true;
			mFunction = functionType;
			mLeftBranch = arg1;
			mRightBranch = arg2;
			mThirdFunctionExpression = arg3;
		}

		/**
		 * Evaluate binary tree expression..
		 * @param context variable definitions and other context information.
		 * @param interpreterFilename name of file being interpreted.
		 * @return numeric or string value of the expression.
		 */
		public Argument evaluate(ContextStack context, String interpreterFilename)
			throws MapyrusException
		{
			return(traverse(this, context, interpreterFilename));
		}

		/**
		 * Evalute internal function.
		 * @param context is context containing variable values
		 * @param interpreterFilename name of file being interpreted.
		 * @return result of function
		 */
		private Argument evaluateFunction(ContextStack context,
			String interpreterFilename)
			throws MapyrusException
		{
			Argument leftValue, rightValue, thirdValue;
			Argument retval;
			String s;
			double l, d = 0.0;

			/*
			 * Evaluate function.
			 */
			if (mFunction == ROUND_FUNCTION || mFunction == RANDOM_FUNCTION ||
				mFunction == LOG10_FUNCTION)
			{
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				l = leftValue.getNumericValue();
						
				if (mFunction == ROUND_FUNCTION)
					d = Math.round(l);
				else if (mFunction == RANDOM_FUNCTION)
					d = Math.random() * l;
				else
				{
					if (l <= 0.0)
						throw new MapyrusException(MapyrusMessages.get(MapyrusMessages.NUMERIC_OVERFLOW));
	
					d = Math.log(l) / LOG_OF_10;
				}
				retval = new Argument(d);
			}
			else if (mFunction == LENGTH_FUNCTION)
			{
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				retval = new Argument(leftValue.toString().length());
			}
			else if (mFunction == MATCH_FUNCTION)
			{
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				rightValue = traverse(mRightBranch, context, interpreterFilename);
	
				/*
				 * Find index of start of regular expression in string.
				 */
				Pattern pattern = compileRegex(rightValue.toString());
				Matcher matcher = pattern.matcher(leftValue.toString());
				if (matcher.find())
					retval = new Argument(matcher.start() + 1);
				else
					retval = Argument.numericZero;
			}
			else if (mFunction == REPLACE_FUNCTION)
			{
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				rightValue = traverse(mRightBranch, context, interpreterFilename);
				thirdValue = traverse(mThirdFunctionExpression, context, interpreterFilename);
	
				/*
				 * Replace all occurrences of pattern given in second string
				 * with the third string.
				 */
				Pattern pattern = compileRegex(rightValue.toString());
				Matcher matcher = pattern.matcher(leftValue.toString());
				if (matcher.find())
				{
					/*
					 * Replace all matching patterns.
					 */
					retval = new Argument(Argument.STRING, matcher.replaceAll(thirdValue.toString()));
				}
				else
				{
					/*
					 * No match so return original string.
					 */
					retval = leftValue;
				}
			}
			else if (mFunction == TEMPNAME_FUNCTION)
			{
				/*
				 * Generate temporary file with given suffix.
				 */
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				retval = new Argument(Argument.STRING,
					TransientFileFactory.generate(leftValue.toString(), Constants.HTTP_TEMPFILE_LIFESPAN));
			}
			else /* SUBSTR_FUNCTION */
			{
				int startIndex, extractLen, len;
	
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				s = leftValue.toString();
				rightValue = traverse(mRightBranch, context, interpreterFilename);
				thirdValue = traverse(mThirdFunctionExpression, context, interpreterFilename);
	
				/*
				 * Convert to zero-based indexing used by java.
				 */
				startIndex = (int)(Math.floor(rightValue.getNumericValue()));
				startIndex--;
				if (startIndex < 0)
					startIndex = 0;
				extractLen = (int)(Math.floor(thirdValue.getNumericValue()));
						
				len = s.length();
				if (extractLen < 1 || startIndex >= len)
				{
					/*
					 * Substring is totally to the left or right of
					 * the string.  So substring is empty. 
					 */
					retval = Argument.emptyString;
				}
				else
				{
					if (startIndex + extractLen > len)
						extractLen = len - startIndex;
	
					retval = new Argument(Argument.STRING,
						s.substring(startIndex, startIndex + extractLen));
				}
			}
			return(retval);
		}
		
		/*
		 * Recursively traverse binary expression tree to
		 * determine its value.
		 */
		private Argument traverse(ExpressionTreeNode t, ContextStack context,
			String interpreterFilename) throws MapyrusException
		{
			Argument retval;
			Argument leftValue, rightValue;
			int returnType = Argument.NUMERIC;
			double l, r, d = 0.0;
			String s = null;

			if (t.mIsLeaf)
			{
				/*
				 * Evaluate any variable name.  Variables that are not assigned
				 * are given the value of an empty string (which converts to the
				 * numeric value 0), like in awk(1) and Perl.
				 */
				if (t.mLeafArg.getType() == Argument.VARIABLE)
				{
					retval = context.getVariableValue(t.mLeafArg.getVariableName(), interpreterFilename);
					if (retval == null)
						retval = Argument.emptyString;
				}
				else
				{
					retval = t.mLeafArg;
				}
			}
			else if (t.mIsFunction)
			{
				retval = t.evaluateFunction(context, interpreterFilename);
			}
			else if (t.mOperation == NOT_OPERATION)
			{
				/*
				 * Negation operates on a single expression.
				 */
				leftValue = traverse(t.mLeftBranch, context, interpreterFilename);
				if (leftValue.getType() == Argument.NUMERIC)
				{
					l = leftValue.getNumericValue();
					retval = NumericalAnalysis.equals(l, 0.0) ?
						Argument.numericOne : Argument.numericZero;
				}
				else
				{
					retval = (leftValue.getStringValue().length() == 0) ?
						Argument.numericOne : Argument.numericZero;
				}
			}
			else if (t.mOperation == ASSIGN_OPERATION)
			{
				rightValue = traverse(t.mRightBranch, context, interpreterFilename);
				if (t.mLeftBranch.mIsLeaf)
				{
					/*
					 * Simple assignment: a = b.
					 */
					String varName = t.mLeftBranch.mLeafArg.getVariableName();
					context.defineVariable(varName, rightValue);
				}
				else
				{
					/*
					 * Assign value as entry in a hashmap: a[55] = "foo".
					 */
					String hashMapName = t.mLeftBranch.mLeftBranch.mLeafArg.getVariableName();
					Argument key = traverse(t.mLeftBranch.mRightBranch, context,
						interpreterFilename);
					if (key.getType() != Argument.NUMERIC && key.getType() != Argument.STRING)
					{
						throw new MapyrusException(MapyrusMessages.get(MapyrusMessages.INVALID_HASHMAP_KEY));
					}
					context.defineHashMapEntry(hashMapName, key.getStringValue(),
						rightValue);
				}

				/*
				 * Return value assigned.
				 */
				retval = rightValue;
			}
			else if (t.mOperation == HASHMAP_REFERENCE)
			{
				/*
				 * Lookup an individual entry in a hash map from a hash map
				 * variable name and key.
				 */
				String varName = t.mLeftBranch.mLeafArg.getStringValue();
				Argument key = traverse(t.mRightBranch, context, interpreterFilename);
				if (key.getType() != Argument.NUMERIC && key.getType() != Argument.STRING)
				{
					throw new MapyrusException(MapyrusMessages.get(MapyrusMessages.INVALID_HASHMAP_KEY));
				}
				Argument hashMapVar = context.getVariableValue(varName, interpreterFilename);
				if (hashMapVar == null || hashMapVar.getType() != Argument.HASHMAP)
				{
					/*
					 * No hash map exists with this name so return empty string.
					 */
					retval = Argument.emptyString;
				}
				else
				{
					/*
					 * Return value assigned to this key value in hash map.
					 */
					retval = hashMapVar.getHashMapEntry(key.getStringValue());
				}
			}
			else
			{
				/*
				 * Either expression can be a number or a string.
				 */
				leftValue = traverse(t.mLeftBranch, context, interpreterFilename);
				rightValue = traverse(t.mRightBranch, context, interpreterFilename);

				switch (t.mOperation)
				{
				case PLUS_OPERATION:
					d = leftValue.getNumericValue() + rightValue.getNumericValue();
					returnType = Argument.NUMERIC;
					break;
				case CONCAT_OPERATION:
					s = leftValue.toString() + rightValue.toString();
					returnType = Argument.STRING;
					break;
				case MINUS_OPERATION:
					d = leftValue.getNumericValue() - rightValue.getNumericValue();
					returnType = Argument.NUMERIC;
					break;
				case MULTIPLY_OPERATION:
					d = leftValue.getNumericValue() * rightValue.getNumericValue();
					returnType = Argument.NUMERIC;
					break;
				case REPEAT_OPERATION:
					/*
					 * Repeat string N times.
					 */
					StringBuffer sb = new StringBuffer();
					int repeatCount = (int)(Math.floor(rightValue.getNumericValue()));
					for (int i = 0; i < repeatCount; i++)
					{
						sb.append(leftValue.toString());
					}
					s = sb.toString();
					returnType = Argument.STRING;
					break;
				case DIVIDE_OPERATION:
					d = leftValue.getNumericValue() / rightValue.getNumericValue();
					returnType = Argument.NUMERIC;
					break;
				case MODULO_OPERATION:
					d = NumericalAnalysis.fmod(leftValue.getNumericValue(),
						rightValue.getNumericValue());
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_EQUALS_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = NumericalAnalysis.equals(l, r) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_NOT_EQUALS_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = NumericalAnalysis.equals(l, r) ? 0 : 1;
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_GREATER_THAN_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = (l > r && (!NumericalAnalysis.equals(l, r))) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_GREATER_EQUAL_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = (l > r || NumericalAnalysis.equals(l, r)) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_LESS_THAN_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = (l < r && (!NumericalAnalysis.equals(l, r))) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_LESS_EQUAL_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = (l < r || NumericalAnalysis.equals(l, r)) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case AND_OPERATION:
					d = (leftValue.getNumericValue() != 0 &&
						rightValue.getNumericValue() != 0) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case OR_OPERATION:
					d = (leftValue.getNumericValue() != 0 ||
						rightValue.getNumericValue() != 0) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_EQUALS_OPERATION:
					d = leftValue.toString().equals(rightValue.toString()) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_NOT_EQUALS_OPERATION:
					d = leftValue.toString().equals(rightValue.toString()) ? 0 : 1;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_GREATER_THAN_OPERATION:
					d = leftValue.toString().compareTo(rightValue.toString()) > 0 ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_GREATER_EQUAL_OPERATION:
					d = leftValue.toString().compareTo(rightValue.toString()) >= 0 ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_LESS_THAN_OPERATION:
					d = leftValue.toString().compareTo(rightValue.toString()) < 0 ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_LESS_EQUAL_OPERATION:
					d = leftValue.toString().compareTo(rightValue.toString()) <= 0 ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				}

				if (returnType == Argument.NUMERIC)
				{
					/*
					 * Fail on numeric overflow and divide by zero.
					 */
					if (Double.isInfinite(d) || Double.isNaN(d))
						throw new MapyrusException(MapyrusMessages.get(MapyrusMessages.NUMERIC_OVERFLOW));

					if (d == 0.0)
						retval = Argument.numericZero;
					else if (d == 1.0)
						retval = Argument.numericOne;
					else
						retval = new Argument(d);
				}
				else
				{
					if (s.length() == 0)
						retval = Argument.emptyString;
					else
						retval = new Argument(Argument.STRING, s);
				}
			}
			return(retval);
		}
		
		/**
		 * String representation of an expression tree.
		 * @return expression as a string.
		 */
		public String toString()
		{
			String retval;
			StringBuffer sb;
			
			if (mIsLeaf)
			{
				retval = mLeafArg.toString();
			}
			else
			{
				String operation = "";
				switch (mOperation)
				{
					case PLUS_OPERATION:
						operation = "+";
						break;
					case CONCAT_OPERATION:
						operation = ".";
						break;
					case MINUS_OPERATION:
						operation = "-";
						break;
					case MULTIPLY_OPERATION:
						operation = "*";
						break;
					case REPEAT_OPERATION:
						operation = "x";
						break;
					case DIVIDE_OPERATION:
						operation = "/";
						break;
					case MODULO_OPERATION:
						operation = "%";
						break;
					case LEXICAL_EQUALS_OPERATION:
						operation = "eq";
						break;
					case LEXICAL_NOT_EQUALS_OPERATION:
						operation = "ne";
						break;
					case LEXICAL_GREATER_THAN_OPERATION:
						operation = "gt";
						break;
					case LEXICAL_LESS_THAN_OPERATION:
						operation = "lt";
						break;
					case LEXICAL_GREATER_EQUAL_OPERATION:
						operation = "ge";
						break;
					case LEXICAL_LESS_EQUAL_OPERATION:
						operation = "le";
						break;
					case NUMERIC_EQUALS_OPERATION:
						operation = "==";
						break;
					case NUMERIC_NOT_EQUALS_OPERATION:
						operation = "!=";
						break;
					case NUMERIC_GREATER_THAN_OPERATION:
						operation = ">";
						break;
					case NUMERIC_LESS_THAN_OPERATION:
						operation  = "<";
						break;
					case NUMERIC_GREATER_EQUAL_OPERATION:
						operation = ">=";
						break;
					case NUMERIC_LESS_EQUAL_OPERATION:
						operation = "<=";
						break;
					case ASSIGN_OPERATION:
						operation = "=";
						break;
					case AND_OPERATION:
						operation = "and";
						break;
				 	case OR_OPERATION:
				 		operation  = "or";
				 		break;
				 	case NOT_OPERATION:
				 		operation = "not";
				 		break;
					case HASHMAP_REFERENCE:
						operation = "[";
						break;
				}
				
				sb = new StringBuffer();
				sb.append(mLeftBranch.toString());
				sb.append(' ');
				sb.append(operation);
				sb.append(' ');

				if (mOperation != NOT_OPERATION)
					sb.append(mRightBranch.toString());
				if (mOperation == HASHMAP_REFERENCE)
					sb.append(']');
				retval = sb.toString();
			}
			return(retval);
		}
	}

	ExpressionTreeNode mExprTree;
	
	/*
	 * Parse expression including "or" boolean operations.
	 */
	private ExpressionTreeNode parseOrBoolean(Preprocessor p)
		throws IOException, MapyrusException
	{
		ExpressionTreeNode expr, b;
		int op1, op2;

		expr = parseAndBoolean(p);
		while (true)
		{
			/*
			 * If next two characters spell "or" then parse
			 * right hand side of expression.
			 */
			op1 = p.readNonSpace();
			if (op1 == 'o' || op1 == 'O')
			{
				op2 = p.read();
				if (op2 == 'r' || op2 == 'R')
				{
					b = parseAndBoolean(p);
					expr = new ExpressionTreeNode(expr, OR_OPERATION, b);
				}
				else
				{
					p.unread(op2);
					p.unread(op1);
					break;
				}
			}
			else				
			{
				p.unread(op1);
				break;
			}
		}
		return(expr);
	}

	/*
	 * Parse expression including "and" boolean operations.
	 */
	private ExpressionTreeNode parseAndBoolean(Preprocessor p)
		throws IOException, MapyrusException
	{
		ExpressionTreeNode expr, b;
		int op1, op2, op3;

		expr = parseNotBoolean(p);
		while (true)
		{
			/*
			 * If next three characters spell "and" then parse
			 * right hand side of expression.
			 */
			op1 = p.readNonSpace();
			if (op1 == 'a' || op1 == 'A')
			{
				op2 = p.read();
				if (op2 == 'n' || op2 == 'N')
				{
					op3 = p.read();
					if (op3 == 'd' || op3 == 'D')
					{
						b = parseNotBoolean(p);
						expr = new ExpressionTreeNode(expr, AND_OPERATION, b);
					}
					else
					{
						p.unread(op3);
						p.unread(op2);
						p.unread(op1);
						break;
					}
				}
				else
				{
					p.unread(op2);
					p.unread(op1);
					break;
				}
			}
			else				
			{
				p.unread(op1);
				break;
			}
		}
		return(expr);
	}

	/*
	 * Parse expression including "not" boolean operations.
	 */
	private ExpressionTreeNode parseNotBoolean(Preprocessor p)
		throws IOException, MapyrusException
	{
		ExpressionTreeNode b, expr = null;
		int op1, op2, op3, op4;

		/*
		 * If next three characters spell "not" then parse
		 * expression to be negated.
		 */
		op1 = p.readNonSpace();
		if (op1 == 'n' || op1 == 'N')
		{
			op2 = p.read();
			if (op2 == 'o' || op2 == 'O')
			{
				op3 = p.read();
				if (op3 == 't' || op3 == 'T')
				{
					op4 = p.read();
					if (!Character.isLetterOrDigit((char)op4) && op4 != '_' && op4 != '.')
					{
						b = parseNotBoolean(p);
						expr = new ExpressionTreeNode(b, NOT_OPERATION, null);
					}
					else
					{
						p.unread(op4);
						p.unread(op3);
						p.unread(op2);
						p.unread(op1);
					}
				}
				else
				{
					p.unread(op3);
					p.unread(op2);
					p.unread(op1);
				}
			}
			else
			{
				p.unread(op2);
				p.unread(op1);
			}
		}
		else				
		{
			p.unread(op1);
		}

		if (expr == null)
			expr = parseAssignment(p);
		return(expr);
	}

	/*
	 * Parse expression including assignment to variables.
	 */
	private ExpressionTreeNode parseAssignment(Preprocessor p)
		throws IOException, MapyrusException
	{
		ExpressionTreeNode expr, value;
		int op1, op2;

		expr = parseComparison(p);
		while (true)
		{
			/*
			 * If next character is '=' then we have an assignment
			 * to a variable.
			 */
			op1 = p.readNonSpace();
			if (op1 == '=')
			{
				op2 = p.read();
				if (op2 != '=')
				{
					/*
					 * Check that lefthandside of an assignment is a variable name,
					 * or an element in a hashmap.
					 */
					if (expr.mIsLeaf)
					{
						if (expr.mLeafArg.getType() != Argument.VARIABLE)
						{
							throw new MapyrusException(p.getCurrentFilenameAndLineNumber() + ": " +
								MapyrusMessages.get(MapyrusMessages.VARIABLE_EXPECTED));
						}
					}
					else
					{
						if (expr.mOperation != HASHMAP_REFERENCE)
						{
							throw new MapyrusException(p.getCurrentFilenameAndLineNumber() + ": " +
								MapyrusMessages.get(MapyrusMessages.VARIABLE_EXPECTED));
						}
					}
					value = parseAssignment(p);
					expr = new ExpressionTreeNode(expr, ASSIGN_OPERATION, value);
				}
				else
				{
					p.unread(op2);
					p.unread(op1);
					break;
				}
			}
			else				
			{
				p.unread(op1);
				break;
			}
		}
		return(expr);
	}

	/*
	 * Parse a comparison expression.
	 */
	private ExpressionTreeNode parseComparison(Preprocessor p)
		throws IOException, MapyrusException
	{
		ExpressionTreeNode expr, cond;<commit_msg>Fix lost character parse error for assignment expression.<commit_after>/*
 * This file is part of Mapyrus, software for plotting maps.
 * Copyright (C) 2003 <NAME>.
 *
 * Mapyrus 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.
 *
 * Mapyrus 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 for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Mapyrus; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */

/*
 * @(#) $Id$
 */
package au.id.chenery.mapyrus;

import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.regex.PatternSyntaxException;
import java.io.*;

/**
 * An expression tree.  Parser for numeric or string expression that builds
 * a binary tree holding the expression.  The expression can be later 
 * be evaluated and the tree is evaluated to a single value.
 *
 * For example, the expression '(a * 2) + 7' is represented by the tree:
 * <pre>
 *       +
 *      / \
 *     *   7
 *    / \
 *   a   2
 * </pre>
 */
public class Expression
{
	/*
	 * Types of operations allowed between two numbers or strings
	 * (or two expressions).
	 */
	private static final int NO_OPERATION = 0;
	private static final int PLUS_OPERATION = 1;
	private static final int CONCAT_OPERATION = 2; /* 'qw' . 'er' . 7 = 'qwer7' */
	private static final int MINUS_OPERATION = 3;
	private static final int MULTIPLY_OPERATION = 4;
	private static final int REPEAT_OPERATION = 5;	/* 'qw' x 2 = 'qwqw' */
	private static final int DIVIDE_OPERATION = 6;
	private static final int MODULO_OPERATION = 7;

	private static final int LEXICAL_EQUALS_OPERATION = 100;	/* 'foo' eq 'foo' */
	private static final int LEXICAL_NOT_EQUALS_OPERATION = 101;	/* 'foo' ne 'qw' */
	private static final int LEXICAL_GREATER_THAN_OPERATION = 102;	/* 'qw' gt 'foo' */
	private static final int LEXICAL_LESS_THAN_OPERATION = 103;	/* 'foo' lt 'qw' */
	private static final int LEXICAL_GREATER_EQUAL_OPERATION = 104;	/* 'qw' ge 'foo' */
	private static final int LEXICAL_LESS_EQUAL_OPERATION = 105;	/* 'foo' le 'qw' */

	private static final int NUMERIC_EQUALS_OPERATION = 200;	/* 77 == 77 */
	private static final int NUMERIC_NOT_EQUALS_OPERATION = 201;	/* 7 != 77 */
	private static final int NUMERIC_GREATER_THAN_OPERATION = 202;	/* 77 > 7 */
	private static final int NUMERIC_LESS_THAN_OPERATION = 203;	/* 7 < 77 */
	private static final int NUMERIC_GREATER_EQUAL_OPERATION = 204;	/* 77 >= 7 */
	private static final int NUMERIC_LESS_EQUAL_OPERATION = 205;	/* 7 <= 77 */

	private static final int ASSIGN_OPERATION = 300;	/* a = 77 */

	private static final int AND_OPERATION = 400;
	private static final int OR_OPERATION = 401;
	private static final int NOT_OPERATION = 402;
	
	private static final int HASHMAP_REFERENCE = 500;		/* a[77] */

	/*
	 * Names and types of functions we allow on numbers and strings.
	 */
	private static final int ROUND_FUNCTION = 1;	/* round(3.14) = 3 */
	private static final String ROUND_FUNCTION_NAME = "round";
	private static final int RANDOM_FUNCTION = 2;	/* random(3) = [0, 3) */
	private static final String RANDOM_FUNCTION_NAME = "random";
	private static final int LOG10_FUNCTION = 3;	/* log10(1000) = 3 */
	private static final String LOG10_FUNCTION_NAME = "log10";
	private static final int LENGTH_FUNCTION = 4;	/* length("foo") = 3 */
	private static final String LENGTH_FUNCTION_NAME = "length";
	private static final int MATCH_FUNCTION = 5;	/* match('foobar', 'ob') = 3 */
	private static final String MATCH_FUNCTION_NAME = "match";
	private static final int REPLACE_FUNCTION = 6;	/* replace('foobar', 'o*', '_') =  'f_bar' */
	private static final String REPLACE_FUNCTION_NAME = "replace";
	private static final int TEMPNAME_FUNCTION = 7;	/* tempname('.jpg') =  'tmpABC123.jpg' */
	private static final String TEMPNAME_FUNCTION_NAME = "tempname";
	private static final int SUBSTR_FUNCTION = 8;	/* substr('foobar', 2, 3) = 'oob' */
	private static final String SUBSTR_FUNCTION_NAME = "substr";

	/*
	 * Constant for calculating base 10 logarithms.
	 */
	private static final double LOG_OF_10 = Math.log(10.0);
	
	/*
	 * Lookup tables of functions and the number of
	 * arguments that they each take.
	 */
	private static final HashMap mFunctionTypeLookup;
	private static final byte[] mFunctionArgumentCount;
	
	static
	{
		mFunctionTypeLookup = new HashMap();
		mFunctionTypeLookup.put(ROUND_FUNCTION_NAME, new Integer(ROUND_FUNCTION));
		mFunctionTypeLookup.put(RANDOM_FUNCTION_NAME, new Integer(RANDOM_FUNCTION));
		mFunctionTypeLookup.put(LOG10_FUNCTION_NAME, new Integer(LOG10_FUNCTION));
		mFunctionTypeLookup.put(LENGTH_FUNCTION_NAME, new Integer(LENGTH_FUNCTION));
		mFunctionTypeLookup.put(MATCH_FUNCTION_NAME, new Integer(MATCH_FUNCTION));
		mFunctionTypeLookup.put(REPLACE_FUNCTION_NAME, new Integer(REPLACE_FUNCTION));
		mFunctionTypeLookup.put(TEMPNAME_FUNCTION_NAME, new Integer(TEMPNAME_FUNCTION));
		mFunctionTypeLookup.put(SUBSTR_FUNCTION_NAME, new Integer(SUBSTR_FUNCTION));
		
		mFunctionArgumentCount = new byte[SUBSTR_FUNCTION + 1];
		mFunctionArgumentCount[ROUND_FUNCTION] = 1;
		mFunctionArgumentCount[RANDOM_FUNCTION] = 1;
		mFunctionArgumentCount[LOG10_FUNCTION] = 1;
		mFunctionArgumentCount[LENGTH_FUNCTION] = 1;
		mFunctionArgumentCount[MATCH_FUNCTION] = 2;
		mFunctionArgumentCount[REPLACE_FUNCTION] = 3;
		mFunctionArgumentCount[TEMPNAME_FUNCTION] = 1;
		mFunctionArgumentCount[SUBSTR_FUNCTION] = 3;
	}

	/*
	 * Maximum number of compiled regular expressions we'll cache.
	 */
	private static final int MAX_COMPILED_REGEX = 100;
	
	/*
	 * Static table of frequently used regular expressions.
	 */
	private static LRUCache mRegexCache = new LRUCache(MAX_COMPILED_REGEX);

	/**
	 * Compile a regular expression string into a Pattern that can be used for matching.
	 * Patterns are cached to avoid recomputing them again and again.
	 * Synchronized because LRUCache is not thread-safe.
	 * @param regex is regular expression to compile.
	 * @return compiled pattern
	 */
	private static synchronized Pattern compileRegex(String regex) throws MapyrusException
	{
		Pattern retval = (Pattern)(mRegexCache.get(regex));

		if (retval == null)
		{
			try
			{
				retval = Pattern.compile(regex);
			}
			catch (PatternSyntaxException e)
			{
				throw new MapyrusException(MapyrusMessages.get(MapyrusMessages.INVALID_REGEX) +
					": " + e.getMessage());
			}

			/*
			 * Cache newly compiled regular expression.
			 */
			mRegexCache.put(regex, retval);
		}
		return(retval);
	}

	/*
	 * Nodes in binary tree describing an arithmetic expression.
	 */
	private class ExpressionTreeNode
	{
		boolean mIsLeaf;
		Argument mLeafArg;

		int mOperation;
		ExpressionTreeNode mLeftBranch, mRightBranch;

		boolean mIsFunction;
		int mFunction;
		ExpressionTreeNode mThirdFunctionExpression;

		/**
		 * Create a leaf value containing either a number,
		 * string or variable name.
		 * @param arg is leaf argument value.
		 */
		public ExpressionTreeNode(Argument arg)
		{
			mIsLeaf = true;
			mIsFunction = false;
			mLeafArg = arg;
		}
	
		/**
		 * Create a node joining two sub-expressions with an
		 * operation between them.
		 * @param left is left hand side of expression.
		 * @param operation is operation between left and right handside expressions.
		 * @param right is right hand side of expression.
		 */
		public ExpressionTreeNode(ExpressionTreeNode left,
			int operation,
			ExpressionTreeNode right)
		{
			mIsLeaf = mIsFunction = false;			
			mLeftBranch = left;
			mRightBranch = right;
			mOperation = operation;
		}

		/**
		 * Create a node containing a call to a function.
		 * @param functionType is identifier of function being called.
		 * @param arg1 is first argument to function.
		 * @param arg2 is second argument to function (or null for single
		 * argument functions).
		 * @param arg3 is third argument to function (or null for functions
		 * with less than 3 arguments)
		 */
		public ExpressionTreeNode(int functionType, ExpressionTreeNode arg1,
			ExpressionTreeNode arg2, ExpressionTreeNode arg3)
		{
			mIsLeaf = false;
			mIsFunction = true;
			mFunction = functionType;
			mLeftBranch = arg1;
			mRightBranch = arg2;
			mThirdFunctionExpression = arg3;
		}

		/**
		 * Evaluate binary tree expression..
		 * @param context variable definitions and other context information.
		 * @param interpreterFilename name of file being interpreted.
		 * @return numeric or string value of the expression.
		 */
		public Argument evaluate(ContextStack context, String interpreterFilename)
			throws MapyrusException
		{
			return(traverse(this, context, interpreterFilename));
		}

		/**
		 * Evalute internal function.
		 * @param context is context containing variable values
		 * @param interpreterFilename name of file being interpreted.
		 * @return result of function
		 */
		private Argument evaluateFunction(ContextStack context,
			String interpreterFilename)
			throws MapyrusException
		{
			Argument leftValue, rightValue, thirdValue;
			Argument retval;
			String s;
			double l, d = 0.0;

			/*
			 * Evaluate function.
			 */
			if (mFunction == ROUND_FUNCTION || mFunction == RANDOM_FUNCTION ||
				mFunction == LOG10_FUNCTION)
			{
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				l = leftValue.getNumericValue();
						
				if (mFunction == ROUND_FUNCTION)
					d = Math.round(l);
				else if (mFunction == RANDOM_FUNCTION)
					d = Math.random() * l;
				else
				{
					if (l <= 0.0)
						throw new MapyrusException(MapyrusMessages.get(MapyrusMessages.NUMERIC_OVERFLOW));
	
					d = Math.log(l) / LOG_OF_10;
				}
				retval = new Argument(d);
			}
			else if (mFunction == LENGTH_FUNCTION)
			{
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				retval = new Argument(leftValue.toString().length());
			}
			else if (mFunction == MATCH_FUNCTION)
			{
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				rightValue = traverse(mRightBranch, context, interpreterFilename);
	
				/*
				 * Find index of start of regular expression in string.
				 */
				Pattern pattern = compileRegex(rightValue.toString());
				Matcher matcher = pattern.matcher(leftValue.toString());
				if (matcher.find())
					retval = new Argument(matcher.start() + 1);
				else
					retval = Argument.numericZero;
			}
			else if (mFunction == REPLACE_FUNCTION)
			{
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				rightValue = traverse(mRightBranch, context, interpreterFilename);
				thirdValue = traverse(mThirdFunctionExpression, context, interpreterFilename);
	
				/*
				 * Replace all occurrences of pattern given in second string
				 * with the third string.
				 */
				Pattern pattern = compileRegex(rightValue.toString());
				Matcher matcher = pattern.matcher(leftValue.toString());
				if (matcher.find())
				{
					/*
					 * Replace all matching patterns.
					 */
					retval = new Argument(Argument.STRING, matcher.replaceAll(thirdValue.toString()));
				}
				else
				{
					/*
					 * No match so return original string.
					 */
					retval = leftValue;
				}
			}
			else if (mFunction == TEMPNAME_FUNCTION)
			{
				/*
				 * Generate temporary file with given suffix.
				 */
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				retval = new Argument(Argument.STRING,
					TransientFileFactory.generate(leftValue.toString(), Constants.HTTP_TEMPFILE_LIFESPAN));
			}
			else /* SUBSTR_FUNCTION */
			{
				int startIndex, extractLen, len;
	
				leftValue = traverse(mLeftBranch, context, interpreterFilename);
				s = leftValue.toString();
				rightValue = traverse(mRightBranch, context, interpreterFilename);
				thirdValue = traverse(mThirdFunctionExpression, context, interpreterFilename);
	
				/*
				 * Convert to zero-based indexing used by java.
				 */
				startIndex = (int)(Math.floor(rightValue.getNumericValue()));
				startIndex--;
				if (startIndex < 0)
					startIndex = 0;
				extractLen = (int)(Math.floor(thirdValue.getNumericValue()));
						
				len = s.length();
				if (extractLen < 1 || startIndex >= len)
				{
					/*
					 * Substring is totally to the left or right of
					 * the string.  So substring is empty. 
					 */
					retval = Argument.emptyString;
				}
				else
				{
					if (startIndex + extractLen > len)
						extractLen = len - startIndex;
	
					retval = new Argument(Argument.STRING,
						s.substring(startIndex, startIndex + extractLen));
				}
			}
			return(retval);
		}
		
		/*
		 * Recursively traverse binary expression tree to
		 * determine its value.
		 */
		private Argument traverse(ExpressionTreeNode t, ContextStack context,
			String interpreterFilename) throws MapyrusException
		{
			Argument retval;
			Argument leftValue, rightValue;
			int returnType = Argument.NUMERIC;
			double l, r, d = 0.0;
			String s = null;

			if (t.mIsLeaf)
			{
				/*
				 * Evaluate any variable name.  Variables that are not assigned
				 * are given the value of an empty string (which converts to the
				 * numeric value 0), like in awk(1) and Perl.
				 */
				if (t.mLeafArg.getType() == Argument.VARIABLE)
				{
					retval = context.getVariableValue(t.mLeafArg.getVariableName(), interpreterFilename);
					if (retval == null)
						retval = Argument.emptyString;
				}
				else
				{
					retval = t.mLeafArg;
				}
			}
			else if (t.mIsFunction)
			{
				retval = t.evaluateFunction(context, interpreterFilename);
			}
			else if (t.mOperation == NOT_OPERATION)
			{
				/*
				 * Negation operates on a single expression.
				 */
				leftValue = traverse(t.mLeftBranch, context, interpreterFilename);
				if (leftValue.getType() == Argument.NUMERIC)
				{
					l = leftValue.getNumericValue();
					retval = NumericalAnalysis.equals(l, 0.0) ?
						Argument.numericOne : Argument.numericZero;
				}
				else
				{
					retval = (leftValue.getStringValue().length() == 0) ?
						Argument.numericOne : Argument.numericZero;
				}
			}
			else if (t.mOperation == ASSIGN_OPERATION)
			{
				rightValue = traverse(t.mRightBranch, context, interpreterFilename);
				if (t.mLeftBranch.mIsLeaf)
				{
					/*
					 * Simple assignment: a = b.
					 */
					String varName = t.mLeftBranch.mLeafArg.getVariableName();
					context.defineVariable(varName, rightValue);
				}
				else
				{
					/*
					 * Assign value as entry in a hashmap: a[55] = "foo".
					 */
					String hashMapName = t.mLeftBranch.mLeftBranch.mLeafArg.getVariableName();
					Argument key = traverse(t.mLeftBranch.mRightBranch, context,
						interpreterFilename);
					if (key.getType() != Argument.NUMERIC && key.getType() != Argument.STRING)
					{
						throw new MapyrusException(MapyrusMessages.get(MapyrusMessages.INVALID_HASHMAP_KEY));
					}
					context.defineHashMapEntry(hashMapName, key.getStringValue(),
						rightValue);
				}

				/*
				 * Return value assigned.
				 */
				retval = rightValue;
			}
			else if (t.mOperation == HASHMAP_REFERENCE)
			{
				/*
				 * Lookup an individual entry in a hash map from a hash map
				 * variable name and key.
				 */
				String varName = t.mLeftBranch.mLeafArg.getStringValue();
				Argument key = traverse(t.mRightBranch, context, interpreterFilename);
				if (key.getType() != Argument.NUMERIC && key.getType() != Argument.STRING)
				{
					throw new MapyrusException(MapyrusMessages.get(MapyrusMessages.INVALID_HASHMAP_KEY));
				}
				Argument hashMapVar = context.getVariableValue(varName, interpreterFilename);
				if (hashMapVar == null || hashMapVar.getType() != Argument.HASHMAP)
				{
					/*
					 * No hash map exists with this name so return empty string.
					 */
					retval = Argument.emptyString;
				}
				else
				{
					/*
					 * Return value assigned to this key value in hash map.
					 */
					retval = hashMapVar.getHashMapEntry(key.getStringValue());
				}
			}
			else
			{
				/*
				 * Either expression can be a number or a string.
				 */
				leftValue = traverse(t.mLeftBranch, context, interpreterFilename);
				rightValue = traverse(t.mRightBranch, context, interpreterFilename);

				switch (t.mOperation)
				{
				case PLUS_OPERATION:
					d = leftValue.getNumericValue() + rightValue.getNumericValue();
					returnType = Argument.NUMERIC;
					break;
				case CONCAT_OPERATION:
					s = leftValue.toString() + rightValue.toString();
					returnType = Argument.STRING;
					break;
				case MINUS_OPERATION:
					d = leftValue.getNumericValue() - rightValue.getNumericValue();
					returnType = Argument.NUMERIC;
					break;
				case MULTIPLY_OPERATION:
					d = leftValue.getNumericValue() * rightValue.getNumericValue();
					returnType = Argument.NUMERIC;
					break;
				case REPEAT_OPERATION:
					/*
					 * Repeat string N times.
					 */
					StringBuffer sb = new StringBuffer();
					int repeatCount = (int)(Math.floor(rightValue.getNumericValue()));
					for (int i = 0; i < repeatCount; i++)
					{
						sb.append(leftValue.toString());
					}
					s = sb.toString();
					returnType = Argument.STRING;
					break;
				case DIVIDE_OPERATION:
					d = leftValue.getNumericValue() / rightValue.getNumericValue();
					returnType = Argument.NUMERIC;
					break;
				case MODULO_OPERATION:
					d = NumericalAnalysis.fmod(leftValue.getNumericValue(),
						rightValue.getNumericValue());
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_EQUALS_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = NumericalAnalysis.equals(l, r) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_NOT_EQUALS_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = NumericalAnalysis.equals(l, r) ? 0 : 1;
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_GREATER_THAN_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = (l > r && (!NumericalAnalysis.equals(l, r))) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_GREATER_EQUAL_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = (l > r || NumericalAnalysis.equals(l, r)) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_LESS_THAN_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = (l < r && (!NumericalAnalysis.equals(l, r))) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case NUMERIC_LESS_EQUAL_OPERATION:
					l = leftValue.getNumericValue();
					r = rightValue.getNumericValue();
					d = (l < r || NumericalAnalysis.equals(l, r)) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case AND_OPERATION:
					d = (leftValue.getNumericValue() != 0 &&
						rightValue.getNumericValue() != 0) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case OR_OPERATION:
					d = (leftValue.getNumericValue() != 0 ||
						rightValue.getNumericValue() != 0) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_EQUALS_OPERATION:
					d = leftValue.toString().equals(rightValue.toString()) ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_NOT_EQUALS_OPERATION:
					d = leftValue.toString().equals(rightValue.toString()) ? 0 : 1;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_GREATER_THAN_OPERATION:
					d = leftValue.toString().compareTo(rightValue.toString()) > 0 ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_GREATER_EQUAL_OPERATION:
					d = leftValue.toString().compareTo(rightValue.toString()) >= 0 ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_LESS_THAN_OPERATION:
					d = leftValue.toString().compareTo(rightValue.toString()) < 0 ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				case LEXICAL_LESS_EQUAL_OPERATION:
					d = leftValue.toString().compareTo(rightValue.toString()) <= 0 ? 1 : 0;
					returnType = Argument.NUMERIC;
					break;
				}

				if (returnType == Argument.NUMERIC)
				{
					/*
					 * Fail on numeric overflow and divide by zero.
					 */
					if (Double.isInfinite(d) || Double.isNaN(d))
						throw new MapyrusException(MapyrusMessages.get(MapyrusMessages.NUMERIC_OVERFLOW));

					if (d == 0.0)
						retval = Argument.numericZero;
					else if (d == 1.0)
						retval = Argument.numericOne;
					else
						retval = new Argument(d);
				}
				else
				{
					if (s.length() == 0)
						retval = Argument.emptyString;
					else
						retval = new Argument(Argument.STRING, s);
				}
			}
			return(retval);
		}
		
		/**
		 * String representation of an expression tree.
		 * @return expression as a string.
		 */
		public String toString()
		{
			String retval;
			StringBuffer sb;
			
			if (mIsLeaf)
			{
				retval = mLeafArg.toString();
			}
			else
			{
				String operation = "";
				switch (mOperation)
				{
					case PLUS_OPERATION:
						operation = "+";
						break;
					case CONCAT_OPERATION:
						operation = ".";
						break;
					case MINUS_OPERATION:
						operation = "-";
						break;
					case MULTIPLY_OPERATION:
						operation = "*";
						break;
					case REPEAT_OPERATION:
						operation = "x";
						break;
					case DIVIDE_OPERATION:
						operation = "/";
						break;
					case MODULO_OPERATION:
						operation = "%";
						break;
					case LEXICAL_EQUALS_OPERATION:
						operation = "eq";
						break;
					case LEXICAL_NOT_EQUALS_OPERATION:
						operation = "ne";
						break;
					case LEXICAL_GREATER_THAN_OPERATION:
						operation = "gt";
						break;
					case LEXICAL_LESS_THAN_OPERATION:
						operation = "lt";
						break;
					case LEXICAL_GREATER_EQUAL_OPERATION:
						operation = "ge";
						break;
					case LEXICAL_LESS_EQUAL_OPERATION:
						operation = "le";
						break;
					case NUMERIC_EQUALS_OPERATION:
						operation = "==";
						break;
					case NUMERIC_NOT_EQUALS_OPERATION:
						operation = "!=";
						break;
					case NUMERIC_GREATER_THAN_OPERATION:
						operation = ">";
						break;
					case NUMERIC_LESS_THAN_OPERATION:
						operation  = "<";
						break;
					case NUMERIC_GREATER_EQUAL_OPERATION:
						operation = ">=";
						break;
					case NUMERIC_LESS_EQUAL_OPERATION:
						operation = "<=";
						break;
					case ASSIGN_OPERATION:
						operation = "=";
						break;
					case AND_OPERATION:
						operation = "and";
						break;
				 	case OR_OPERATION:
				 		operation  = "or";
				 		break;
				 	case NOT_OPERATION:
				 		operation = "not";
				 		break;
					case HASHMAP_REFERENCE:
						operation = "[";
						break;
				}
				
				sb = new StringBuffer();
				sb.append(mLeftBranch.toString());
				sb.append(' ');
				sb.append(operation);
				sb.append(' ');

				if (mOperation != NOT_OPERATION)
					sb.append(mRightBranch.toString());
				if (mOperation == HASHMAP_REFERENCE)
					sb.append(']');
				retval = sb.toString();
			}
			return(retval);
		}
	}

	ExpressionTreeNode mExprTree;
	
	/*
	 * Parse expression including "or" boolean operations.
	 */
	private ExpressionTreeNode parseOrBoolean(Preprocessor p)
		throws IOException, MapyrusException
	{
		ExpressionTreeNode expr, b;
		int op1, op2;

		expr = parseAndBoolean(p);
		while (true)
		{
			/*
			 * If next two characters spell "or" then parse
			 * right hand side of expression.
			 */
			op1 = p.readNonSpace();
			if (op1 == 'o' || op1 == 'O')
			{
				op2 = p.read();
				if (op2 == 'r' || op2 == 'R')
				{
					b = parseAndBoolean(p);
					expr = new ExpressionTreeNode(expr, OR_OPERATION, b);
				}
				else
				{
					p.unread(op2);
					p.unread(op1);
					break;
				}
			}
			else				
			{
				p.unread(op1);
				break;
			}
		}
		return(expr);
	}

	/*
	 * Parse expression including "and" boolean operations.
	 */
	private ExpressionTreeNode parseAndBoolean(Preprocessor p)
		throws IOException, MapyrusException
	{
		ExpressionTreeNode expr, b;
		int op1, op2, op3;

		expr = parseNotBoolean(p);
		while (true)
		{
			/*
			 * If next three characters spell "and" then parse
			 * right hand side of expression.
			 */
			op1 = p.readNonSpace();
			if (op1 == 'a' || op1 == 'A')
			{
				op2 = p.read();
				if (op2 == 'n' || op2 == 'N')
				{
					op3 = p.read();
					if (op3 == 'd' || op3 == 'D')
					{
						b = parseNotBoolean(p);
						expr = new ExpressionTreeNode(expr, AND_OPERATION, b);
					}
					else
					{
						p.unread(op3);
						p.unread(op2);
						p.unread(op1);
						break;
					}
				}
				else
				{
					p.unread(op2);
					p.unread(op1);
					break;
				}
			}
			else				
			{
				p.unread(op1);
				break;
			}
		}
		return(expr);
	}

	/*
	 * Parse expression including "not" boolean operations.
	 */
	private ExpressionTreeNode parseNotBoolean(Preprocessor p)
		throws IOException, MapyrusException
	{
		ExpressionTreeNode b, expr = null;
		int op1, op2, op3, op4;

		/*
		 * If next three characters spell "not" then parse
		 * expression to be negated.
		 */
		op1 = p.readNonSpace();
		if (op1 == 'n' || op1 == 'N')
		{
			op2 = p.read();
			if (op2 == 'o' || op2 == 'O')
			{
				op3 = p.read();
				if (op3 == 't' || op3 == 'T')
				{
					op4 = p.read();
					if (!Character.isLetterOrDigit((char)op4) && op4 != '_' && op4 != '.')
					{
						b = parseNotBoolean(p);
						expr = new ExpressionTreeNode(b, NOT_OPERATION, null);
					}
					else
					{
						p.unread(op4);
						p.unread(op3);
						p.unread(op2);
						p.unread(op1);
					}
				}
				else
				{
					p.unread(op3);
					p.unread(op2);
					p.unread(op1);
				}
			}
			else
			{
				p.unread(op2);
				p.unread(op1);
			}
		}
		else				
		{
			p.unread(op1);
		}

		if (expr == null)
			expr = parseAssignment(p);
		return(expr);
	}

	/*
	 * Parse expression including assignment to variables.
	 */
	private ExpressionTreeNode parseAssignment(Preprocessor p)
		throws IOException, MapyrusException
	{
		ExpressionTreeNode expr, value;
		int op1, op2;

		expr = parseComparison(p);
		while (true)
		{
			/*
			 * If next character is '=' then we have an assignment
			 * to a variable.
			 */
			op1 = p.readNonSpace();
			if (op1 == '=')
			{
				op2 = p.read();
				p.unread(op2);
				if (op2 != '=')
				{
					/*
					 * Check that lefthandside of an assignment is a variable name,
					 * or an element in a hashmap.
					 */
					if (expr.mIsLeaf)
					{
						if (expr.mLeafArg.getType() != Argument.VARIABLE)
						{
							throw new MapyrusException(p.getCurrentFilenameAndLineNumber() + ": " +
								MapyrusMessages.get(MapyrusMessages.VARIABLE_EXPECTED));
						}
					}
					else
					{
						if (expr.mOperation != HASHMAP_REFERENCE)
						{
							throw new MapyrusException(p.getCurrentFilenameAndLineNumber() + ": " +
								MapyrusMessages.get(MapyrusMessages.VARIABLE_EXPECTED));
						}
					}
					value = parseAssignment(p);
					expr = new ExpressionTreeNode(expr, ASSIGN_OPERATION, value);
				}
				else
				{
					p.unread(op1);
					break;
				}
			}
			else				
			{
				p.unread(op1);
				break;
			}
		}
		return(expr);
	}

	/*
	 * Parse a comparison expression.
	 */
	private ExpressionTreeNode parseComparison(Preprocessor p)
		throws IOException, MapyrusException
	{
		ExpressionTreeNode expr, cond;
{'fraction_non_alphanumeric': 0.10801848328350096, 'fraction_numerical': 0.011089970100570808, 'mean_word_length': 2.89127062473558, 'pattern_counts': {'":': 6, '<': 33, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1761537', 'n_tokens_mistral': 22775, 'n_tokens_neox': 17188, 'n_words': 4486}