Search poi

Developing Formula Evaluation

Introduction

This document is for developers wishing to contribute to the FormulaEvaluator API functionality.

Currently, contribution is desired for implementing the standard MS excel functions. Place holder classes for these have been created, contributors only need to insert implementation for the individual "evaluate()" methods that do the actual evaluation.

Overview of FormulaEvaluator

Briefly, a formula string (along with the sheet and workbook that form the context in which the formula is evaluated) is first parsed into RPN tokens using the FormulaParser class in POI-HSSF main. (If you dont know what RPN tokens are, now is a good time to read this.)

The big picture

RPN tokens are mapped to Eval classes. (Class hierarchy for the Evals is best understood if you view the class diagram in a class diagram viewer.) Depending on the type of RPN token (also called as Ptgs henceforth since that is what the FormulaParser calls the classes) a specific type of Eval wrapper is constructed to wrap the RPN token and is pushed on the stack.... UNLESS the Ptg is an OperationPtg. If it is an OperationPtg, an OperationEval instance is created for the specific type of OperationPtg. And depending on how many operands it takes, that many Evals are popped of the stack and passed in an array to the OperationEval instance's evaluate method which returns an Eval of subtype ValueEval.Thus an operation in the formula is evaluated.

Note
An Eval is of subinterface ValueEval or OperationEval. Operands are always ValueEvals, Operations are always OperationEvals.

OperationEval.evaluate(Eval[]) returns an Eval which is supposed to be of type ValueEval (actually since ValueEval is an interface, the return value is instance of one of the implementations of ValueEval). The valueEval resulting from evaluate() is pushed on the stack and the next RPN token is evaluated.... this continues till eventually there are no more RPN tokens at which point, if the formula string was correctly parsed, there should be just one Eval on the stack - which contains the result of evaluating the formula.

Ofcourse I glossed over the details of how AreaPtg and ReferencePtg are handled a little differently, but the code should be self explanatory for that. Very briefly, the cells included in AreaPtg and RefPtg are examined and their values are populated in individual ValueEval objects which are set into the AreaEval and RefEval (ok, since AreaEval and RefEval are interfaces, the implementations of AreaEval and RefEval - but you'll figure all that out from the code)

OperationEvals for the standard operators have been implemented and tested.

FunctionEval and FuncVarEval

FunctionEval is an abstract super class of FuncVarEval. The reason for this is that in the FormulaParser Ptg classes, there are two Ptgs, FuncPtg and FuncVarPtg. In my tests, I did not see FuncPtg being used so there is no corresponding FuncEval right now. But in case the need arises for a FuncVal class, FuncEval and FuncVarEval need to be isolated with a common interface/abstract class, hence FunctionEval.

FunctionEval also contains the mapping of which function class maps to which function index. This mapping has been done for all the functions, so all you really have to do is implement the evaluate method in the function class that has not already been implemented. The Function indexes are defined in AbstractFunctionPtg class in POI main.

Walkthrough of an "evaluate()" implementation.

So here is the fun part - lets walk through the implementation of the excel function... NOT()

The Code

public final class Not implements Function {

	public Eval evaluate(Eval[] args, int srcCellRow, short srcCellCol) {
		if (args.length != 1) {
			return ErrorEval.VALUE_INVALID;
		}
		boolean boolArgVal;
		try {
			ValueEval ve = OperandResolver.getSingleValue(args[0], srcCellRow, srcCellCol);
			Boolean b = OperandResolver.coerceValueToBoolean(ve, false);
			boolArgVal = b == null ? false : b.booleanValue();
		} catch (EvaluationException e) {
			return e.getErrorEval();
		}
		
		return BoolEval.valueOf(!boolArgVal);
	}
}

	

Implementation Details

  • The first thing to realise is that classes already exist, even for functions that are not yet implemented. Just that they extend from NotImplementedFunction whose behaviour is to return an ErrorEval.FUNCTION_NOT_IMPLEMENTED value.
  • In order to implement NOT(..), we need to implement the interface 'Function' which has a method 'evaluate(..)'
  • Since NOT(..) takes a single argument, we verify the length of the operands array else set the return value to ErrorEval.VALUE_INVALID
  • Next we normalize each operand to a limited set of ValueEval subtypes, specifically, we call the function OperandResolver.getSingleValue to do conversions of different value eval types to one of: NumericValueEval, BlankEval and ErrorEval. The conversion logic is performed by OperandResolver.coerceValueToBoolean()
  • Next perform the appropriate java operation (if an error didnt occur already).
  • Finally return the BoolEval wrapping primitive boolean result. Note - in the case of numeric results you should check for NaN and Infinity, because exel likes these translated into specific error codes like VALUE_INVALID, NUM_ERROR, DIV_ZERO etc. (Thanks to Avik for bringing this issue up early!)

Modelling Excel Semantics

Strings are ignored. Booleans are ignored!!!. Actually here's the info on Bools: if you have formula: "=TRUE+1", it evaluates to 2. So also, when you use TRUE like this: "=SUM(1,TRUE)", you see the result is: 2. So TRUE means 1 when doing numeric calculations, right? Wrong! Because when you use TRUE in referenced cells with arithmetic functions, it evaluates to blank - meaning it is not evaluated - as if it was string or a blank cell. eg. "=SUM(1,A1)" when A1 is TRUE evaluates to 1. This behaviour changes depending on which function you are using. eg. SQRT(..) that was described earlier treats a TRUE as 1 in all cases. The various conversion logic has been refactored into common places like the following classes: OperandResolver, TextFunction, NumericFunction, MultiOperandNumericFunction and FinanceFunction.

Note that when you are extending from an abstract function class like NumericFunction (rather than implementing the interface o.a.p.hssf.record.formula.eval.Function directly) you can use the utility methods in the super class - singleOperandEvaluate(..) - to quickly reduce the different ValueEval subtypes to a small set of possible types. However when implemenitng the Function interface directly, you will have to handle the possiblity of all different ValueEval subtypes being sent in as 'operands'. (Hard to put this in word, please have a look at the code for NumericFunction for an example of how/why different ValueEvals need to be handled)

Testing Framework

Automated testing of the implemented Function is easy. The source code for this is in the file: o.a.p.h.record.formula.TestFormulasFromSpreadsheet.java This class has a reference to the Excel test sample file 'FormulaEvalTestData.xls'. In this file, locate the entry for the function that you have implemented and enter different tests in a cell in the FORMULA row. Then copy the "value of" the formula that you entered in the cell just below it (this is easily done in excel as: [copy the formula cell] > [go to cell below] > Edit > Paste Special > Values > "ok"). You can enter multiple such formulas and paste their values in the cell below and the test framework will automatically test if the formula evaluation matches the expected value (Please take time to quickly look at the code and the currently entered tests in the file "FormulaEvalTestData.xls").

by Amol Deshmukh