Extended formula support for fpspreadsheet
lazarus / 49-FPSpreadsheet

----------------------------------------------------------------------
wp · 2014-01-25 18:29

Trying to understand the RPN formulas required in fpspreadsheet I
decided to extend the set of available formulas and operations. I
added the basic math functions and the comparison operations like
"equal", "less than" etc - that was easy. See the attached patch
containing also a modified testcase for the unit tests. Since
fpspreadsheet does not calculate the formulas on its own, it is not
possible to provide automatic tests, what you have to do is to open
the test file "testmanual.xls" in Excel or LibreOffice and manually
compare the reckognized and expected column.

As usual, I am running against my limitations and am meeting several
difficulties:When I load "testmanual.xls" into Excel, most of my
formula cells are displayed as #VALUE!. I have to press F2 and Enter
for the calculated values to appear (which are correct then). It looks
as if my formulas are not automatically recalculated by Excel. Are
there any settings to control this? Open/LibreOffice, BTW, loads the
worksheets correctly in the first place.I tried to add more functions
like COUNT, AVERAGE, STDEV etc but could not get it to work. I thought
I'd take the SUM function - which is already implemented - as a
template. But this implementation does not refer to the FuncID listed
in section 3.11 of the docs which I thought it has to. Therefore, I do
not understand at all how the SUM works.The formulas are reckognized
by Excel always as being "absolute", i.e. having $ at col and row
index. How to create relative addresses? The documentation says in
section 3.3.3 and 3.3.4 that relative cell indices need to have one or
both of the two highest bits of the column index set. However, there
are differences between the biff versions. What would be the best
strategy to implement such a feature?

----------------------------------------------------------------------
BigChimp · 2014-01-25 18:59

Can't look at the patch right now; just some tops off the top of my
head.

1. IIRC, the BIFF format has a "recalculate formulas" field somewhere
that determines whether formulas should be recalculated. Don't know if
fpspreadsheet sets that or if it should...
FYI There's an open bug report about formulas not being calculated
automatically but AFAIR no fix for it yet.

2. Strange. I implemented some functions as well in a fairly recent
commit; you may want to have a look as they're IIRC (I hope) in a
single commit so fairly self contained.

3. No idea; haven't looked at it, sorry.

----------------------------------------------------------------------
wp · 2014-01-25 19:43

#2: You implemented DATE and TIME. These are simple ones like those
that I did. The problem with SUM, COUNT etc is that they accept any
number of parameters which has to be told the TRPNForumula somehow.

#3: Got it: Added boolean flags "RelCol" and "RelRow" to TRPNFormula.
When writing the file, in WriteRPNFormula, "or" the current column and
row index with the constants MASK_EXCEL_RELATIVE_COL and
MASK_EXCEL_RELATIVE_ROW (already defined in xlsbiff8), if the RelCol
and/or RelRow flags are set in the formula definition. I admire more
and more how nicely this library is set up!

I'll post a modified patch after some more tests.

----------------------------------------------------------------------
wp · 2014-01-26 15:17

OK - here's an updated version. For those who do not want to handle
with patches, I am adding the modified files this time, along with the
patch.

Sorry - this is a rather huge patch. But when I startet, I was not
sure where this trip would end...

Relative cell references in RPNFormula
Add fields RelRow, RelCol, RelRow2, RelCol2 to TRPNFormulaElement. If
set to true the corresponding row/col index will be encoded to be a
relative offset. I should mention that it looks as if RelRow and
RelCol (RelRow2 and RelCol2, as well) need to be interchanged
regarding their relation to row/col because Excel puts the $ sign to
the other index. (I did not yet do this, maybe there's something wrong
with my approach...)
RelRow2 and RelCol2 are needed for the second edge of a cellrange. 
Enable functions with variable parameter count
Add field ParamsNum to TRPNFormulaElement. For functions using a
variable parameter count, such as AVERAGE etc., specify the parameter
count in the same formula element as the one defining the function. I
am aware that there are already two fields Param1 and Param2 in the
declaration of TRPNFormulaElement, which may have been introduced just
for this particular purpose; I think they are not used throughout the
entire library, but I did not dare to touch them. 
Simplify class interheritance
Inherit TSpreadBiff2Writer from TSpreadBiffWriter (instead of
TCustomSpreadWriter). Therefore, the Biff2Writer can inherit the
FormulaElementKindToExcelTokenID function from TSpreadBiffWriter
avoiding duplication of code (in function FEToExcelTokenID which is
dropped now). That's a main time-saver because this is very lengthy
and stupid procedure for adding new functions.TSpreadBiff5Writer
already is inherited from TSpreadBiffWriter but had its own
FEToExcelTokenID which becomes obsolete now because of the inherited
FormulaElementKindtoExcelTokenID.
Extend BIFF2/BIFF5 writers
Add writing of cell ranges
Functions
That's the purpose of the activities mentioned abow: I can now add a
LOT of new functions to the BIFF formats of fpspreadsheet, see TFEKind
in fpspreadsheet.pas. In total, there are now about 75 declarations
for operations and functions in TFEKind! The functions cover basic
math, date/time, logical, statistics functions with a predefined and
variable number of parameters. In the latter case, the number of
function parameters has to be specified by the ParamsNum of the
corresponding RPN array element. All functions deal with numbers only.
I know that there is large amount of Excel function dealing with
strings and arrays. But since I don't know how to handle these in
fpspreadsheet I dropped them for the moment. For each function there's
a test in the unit test provided by BigChimp. Some tests are
conditionally excluded for BIFF2 where the tested function is not
implemented. But in essence, the test runs successfully for all BIFF
versions in the package, i.e. all Excel version before 2007.
What's next?
I am looking forward to ideas for improvements. Once the patch is in
the official version I'll think about string and array functions.In
the meantime, I think I should add some sentences to the wiki
(http://wiki.lazarus.freepascal.org/FPSpreadsheet) in order to better
explain the RPN formulas. Before doing the work with this patch I was
not able to understand this technology, and I guess many others will
have the same difficulty.
[EDIT: Attachment removed - please use the files in the first posting

----------------------------------------------------------------------
BigChimp · 2014-01-26 15:28

Wow. Even the post sounds impressive...

Haven't looked at the patch (and won't for the foreseable future,
sorry), so comments based on post:

1. If the $s are wrong in Excel, I'd suggest you change them with a
remark that the actual Excel implementation doesn't seem to follow the
documentation(!?).... assuming LibreOffice/OpenOffice shows the same
thing
2. Can't the ParamsNum be autocalculated somehow based on how many
parameters the user specified (sorry, may be a naive remark but
looking to keep things simple for the user).
3. No idea about Param1 & Param2 but you probably expected that
4. Looking forward to further improvements/wiki additions

Thanks,
BigChimp

----------------------------------------------------------------------
wp · 2014-01-26 17:27

That's funny: Loading the test file into Open/LibreOffice shows the $
at the correct place, but in Excel relative rows and colums are
interchanged. Seeking for this problem in the net I came across the
official Microsoft documentation of the Excel file format (http://www.
digitalpreservation.gov/formats/digformatspecs/Excel97-
2007BinaryFileFormat%28xls%29Specification.pdf), and they say on page
306 that it's in fact the other way round. This means that OpenOffice
and LibreOffice have issues importing the relative cell references in
binary xls files correctly, at least with the versions that are
available to me (OO 4.0.0, LO 4.0.0.3).

I'll replace the files from the previous posting with modified ones
(and BTW, in order to avoid confusion due to outdated versions, I'll
put all files into the first posting of this thread).

Regarding autocalculation of ParamsNum: No, that's not possible, at
least not easily. The RPN formula uses a stack, and the operators are
pushed onto the stack before the operator. In the formula
corresponding to "=SUM(1,2,3)" the stack contains the elements "1, 2,
3, SUM" with 3 SUM parameters; in the formula "=1+SUM(1,2)" the stack
consists of the elements "1, 1, 2, SUM, +" with two parameters used
for SUM. To distinguish that of the three operands below SUM only two
belong to SUM for the first case, but three for the second case would
require a full analysis of the tree. I think the effect on user-
friendliness would be greater if this effort would be put into the
creation of a string formula parser.

----------------------------------------------------------------------
BigChimp · 2014-01-26 18:58

Interesting find on LibreOffice

Agreed with your opinion regarding the RPN stack etc.

----------------------------------------------------------------------
marcov · 2014-01-26 19:52

Quote from: wp on January 26, 2014, 06:27:07 pmI think the effect on
user-friendliness would be greater if this effort would be put into
the creation of a string formula parser.

Unit Symbolic has an infix to rpn converters (and vv)

----------------------------------------------------------------------
wp · 2014-01-26 21:06

You mean that we can create an rpn stack from analyzing a string
formula by means of "Symbolic"? How does it handle the variable names
which I'd consider a bit awkward (A1, $A1, A$1, $A$1, A$1:$B5)?

----------------------------------------------------------------------
wp · 2014-01-31 09:58

Just added a chapter "Understanding RPN formulas" to the fpspreadsheet
wiki (http://wiki.lazarus.freepascal.org/FPSpreadsheet#Understanding_R
PN_formulas). I hope it is helpful. After catching the basic idea, RPN
formulas are as easy as string formulas!

----------------------------------------------------------------------
marcov · 2014-01-31 10:27

Quote from: wp on January 26, 2014, 10:06:33 pmYou mean that we can
create an rpn stack from analyzing a string formula by means of
"Symbolic"?

Maybe yes. And if not, it is an easy codebase to recycle. The
evaluator uses a kind of record based RPN. (or just PN, can't
remember), so conversion routines are there.

Symbolic basically does string based rpn and infix to parse tree (and
vice versa), and parse-tree to this record based (R?)PN for the
evaluator.

QuoteHow does it handle the variable names which I'd consider a bit
awkward (A1, $A1, A$1, $A$1, A$1:$B5)?

Currently not. Currently it is [A..Z][A.Z,0..9].  But that could be
expanded to be user settable with sets.  Only comma and 0..9 are not
allowed as lead chars, and probably () in general. (the only problem
is that then a case statement should be rewritten, parsexpr.inc:360)

Do you have an example for me to test?  If adaptation or something
custom is needed, I'd like to help.

----------------------------------------------------------------------
wp · 2014-01-31 11:29

QuoteDo you have an example for me to test?Here's one (I am pasting
some fpspreadsheet code into the example since I don't know how
familiar you are with that): A string forumla like "A1 * Sum(B1:$G$6)"
should be transformed to the following rpn array

Code: [Select]type
  TFEKind = (fekCell, fekCellRange, fekNum, fekString, ..., fekAdd,
fekMul, ..., fekSum, ..);
  TsFormulaElement = record
    ElementKind: TFEKind;
    Row, Row2: Word; // zero-based
    Col, Col2: Word; // zero-based
    RelFlags: TsRelFlags;  // store info on relative/absolute cell
addresses
    DoubleValue: double;
    StringValue: String;
    ParamsNum: Byte;  // count of arguments used
  end;
  TsRPNFormula = array of TsFormulaElement;
var
  formula: TsRPNFormula;
  r,c: Integer;
  r2,c2: Integer;
  flags: TsRelFlags;   // is "set of (rfRelRow, rfRelCol, rfRelRow2,
rfRelCol2)"
begin
  SetLength(formula, 4);

  formula[0].ElementKind := fekCell;
  ParseCellString('A1', r,c, flags);
    // already existing. Determines absolute/relative row and column
address from "A1"
  formula[0].Row := r;
  formula[0].Col := c;
  formula[0].RelFlags := flags;

  formula[1].ElementKind := fekCellRange;
  ParseCellRangeString('B1:$G$6', r,c, r2,c2, flags);
    // dto as above.
  formula[1].Row := r;
  formula[1].Col := c;
  formula[1].Row2 := r2;
  formula[1].Col2 := c2;
  formula[2].RelFlags := flags;

  formula[2].ElementKind := fekSum;
  formula[2].ParamsNum := 1;   // 1 argument in SUM function here,
Excel allows up to 30.

  formula[3].ElementKind := fekMul;

  //...
end;

----------------------------------------------------------------------
marcov · 2014-02-01 07:54

Quote from: wp on January 31, 2014, 12:29:14 pmQuoteDo you have an
example for me to test?Here's one (I am pasting some fpspreadsheet
code into the example since I don't know how familiar you are with
that): A string forumla like "A1 * Sum(B1:$G$6)" should be transformed
to the following rpn array

I've played a bit, and symbolic has one fundamental limitation atm, no
variable number of parameters.  The format is a bit odd anyway,
stuffing the number of items to pop into a field.

I continue playing, but hope of some very shortterm success is
limited. (I have a half finished development version with some
restrictions lifted, that I would have to bring up to speed)

----------------------------------------------------------------------
wp · 2014-02-01 23:06

Just replaced the zip in the first posting of this thread by a new
version.

This is new:
The "monster" case instruction in the method
"FormulaElementKindToExcelTokenID" of TsSpreadBiffWriter has been
replaced by a lookup table.The RPN formula elements now accept string
constants. This opens a wide range of new functions that were added.I
also added some more statistical and financial functions. The library
now has access to more than 100 Excel functions. There are still many,
many more to be added, but I think it's enough for now.Anyway, if
there would be a need to add more functions, here are short
instructions: In the BIFF documentation ("excelfileformat.pdf" in the
fpspreadsheet installation, section 3.11) look for the Excel ID of the
new function. In unit "fpspreadsheet, add a new item to the
enumeration TFEKind, use the prefix "fek" and the name of the function
to be compatible with the other declarations, insert the new item in
alphabetic order in the group indicated by comments. Then open
"xlscommon" and go to
"TsSpreadBIFFWriter.FormulaElementKindToExcelTokenID". The constant
array "TokenID" is in the same order as the TFEKind elements. Insert
the new Excel ID item at the position corresponding to the FEKind
entry. If the new function requires a fixed number of parameters, use
"1" as first element of the new entry, in case of variable parameter
count use "2" - just follow the other declarations as examples.
Each function has at least one test case in the test project.Since the
test cases extend over almost 2000 lines of code I split them off into
a separate include file (rpntests.inc).Getting bored of the current
way of defining RPN elements as a array I wrote a methodology of
nested function calls, similar to the way how in old Turbo Vision
menus were setup. Please see the comments in fpspreadsheet, or, of
course, the test cases - they are all written in this way. As an
example, the rpn array for the expression "=SIN($A1*5)" in now created
byCode: [Select]var
  rpn: TsRPNFormula;
//...
  rpn := CreateRPNFormula(
    RPNCellValue('$A1',
    RPNNumber(5,
    RPNFunc(fekSIN,
    nil))));
I found the bug which caused Excel to display #VALUE! in some of the
formula cells created by fpspreadsheet. So far, cell addresses had
been written by using "reference" tokens, but Excel expects them to be
"value" tokens. My understanding is currently such that whenever a
cell value is needed in a formula (such as in "=SIN(A1)" Excel
requests the "value" token which is inserted by the RPNCellValue
function shown above. There are other functions such as "=ROW(A1)"
which extract some other information from a cell - in this case the
"reference" token must be used which is done by the RPNCellRef
function.After having done this modification, I see also that
Open/LibreOffice import relative and absolute cell addresses correctly
(see a few postings above).

----------------------------------------------------------------------
wp · 2014-03-22 17:05

BigChimp: I see you are active here again - can I bring this posting
back to your mind? There's also a feature request in BugTracker
(http://mantis.freepascal.org/view.php?id=25718).

----------------------------------------------------------------------
BigChimp · 2014-03-22 17:11

I'll have a look... don't know when as I'm working on dataset stuff as
well..

----------------------------------------------------------------------
BigChimp · 2014-03-23 13:20

(Well there you go - been busy all morning "just looking at the
spreadsheet thingy.... while I intended to do some work on sdfdataset
)

I've added support for ODF/.ods tests by simply copying the .xls file
and writing it as .ods.

Found out there's a time-only format; added partial support for it
(requires date mode 1900/1904 support)

Test output:
Code: [Select]    00.010  TestReadODFDate13  Failed: Could not read
date time for cell Dates!A14
    00.009  TestReadODFDate14  Failed: Test date/time value mismatch
cell Dates!A15 expected: <3178.5> but was: <1716.5>
    00.010  TestReadODFDate15  Failed: Could not read date time for
cell Dates!A16
    00.009  TestReadODFDate16  Failed: Could not read date time for
cell Dates!A17
    00.010  TestReadODFDate19  Failed: Test date/time value mismatch
cell Dates!A20 expected: <3178.5> but was: <1716.5>
    00.009  TestReadODFDate20  Failed: Test date/time value mismatch
cell Dates!A21 expected: <0> but was: <1462>
    00.009  TestReadODFDate21  Failed: Could not read date time for
cell Dates!A22
    00.009  TestReadODFDate23  Failed: Could not read date time for
cell Dates!A24
    00.010  TestReadODFDate24  Failed: Could not read date time for
cell Dates!A25
    00.009  TestReadODFDate25  Failed: Test date/time value mismatch
cell Dates!A26 expected: <0> but was: <1462>
    00.010  TestReadODFDate26  Failed: Test date/time value mismatch
cell Dates!A27 expected: <0> but was: <1462>
    00.009  TestReadODFDate28  Failed: Test date/time value mismatch
cell Dates!A29 expected: <1> but was: <1463>
    00.010  TestReadODFDate29  Failed: Could not read date time for
cell Dates!A30
    00.010  TestReadODFDate31  Failed: Could not read date time for
cell Dates!A32
    00.009  TestReadODFDate32  Failed: Could not read date time for
cell Dates!A33
    00.010  TestReadODFDate33  Failed: Test date/time value mismatch
cell Dates!A34 expected: <1> but was: <1463>
    00.009  TestReadODFDate34  Failed: Test date/time value mismatch
cell Dates!A35 expected: <1> but was: <1463>
    00.009  TestReadODFDate1899_13  Failed: Could not read date time
for cell Dates!A14
    00.010  TestReadODFDate1899_15  Failed: Could not read date time
for cell Dates!A16
    00.009  TestReadODFDate1899_16  Failed: Could not read date time
for cell Dates!A17
    00.009  TestReadODFDate1899_21  Failed: Could not read date time
for cell Dates!A22
    00.009  TestReadODFDate1899_23  Failed: Could not read date time
for cell Dates!A24
    00.010  TestReadODFDate1899_24  Failed: Could not read date time
for cell Dates!A25
    00.009  TestReadODFDate1899_29  Failed: Could not read date time
for cell Dates!A30
    00.009  TestReadODFDate1899_31  Failed: Could not read date time
for cell Dates!A32
    00.009  TestReadODFDate1899_32  Failed: Could not read date time
for cell Dates!A33
    00.010  TestReadODFNumber13  Failed: Test value mismatch cell
Numbers!A14 expected: <0.3536> but was: <0>
    00.009  TestReadODFNumber14  Failed: Test value mismatch cell
Numbers!A15 expected: <0.3536> but was: <0>
    00.009  TestReadODFString7  Failed: Test value mismatch cell
Texts!A8 expected: <35%> but was: <>
    00.010  TestReadODFString8  Failed: Test value mismatch cell
Texts!A9 expected: <35.36%> but was: <>
    00.009  TestReadODFString9  Failed: Test value mismatch cell
Texts!A10 expected: <59,000,000> but was: <59000000.1234>
    00.010  TestReadODFString10  Failed: Test value mismatch cell
Texts!A11 expected: <59,000,000.12> but was: <59000000.1234>
    00.009  TestReadODFString11  Failed: Test value mismatch cell
Texts!A12 expected: <-59.0E6> but was: <-59000000.1234>
    00.010  TestReadODFString12  Failed: Test value mismatch cell
Texts!A13 expected: <-5.90E+07> but was: <-59000000.1234>

The errors in TestReadODFDate are expected as the current code
defaults to the 1899/1900 date system for time-only fields.

The "could not read date/time" errors may be because of an inadvisable
optimization in commit 2908... will have to look at that... but it may
be something else.

The other errors are not expected but at least we have a baseline for
ODS functoinality.

My suggestion: could you split up the patch so we can first implement
and run the tests part (should be easy enough by going to the tests
directory & doing svn diff to get only those changes).

Then we can run the tests, have a look at and commit the other part
and see if there are any regressions...

What do you think?

----------------------------------------------------------------------
wp · 2014-03-23 15:07

Sorry I'm a bit confused: my patch was about formula support for biff,
but you are talking about date/time support in ods...

----------------------------------------------------------------------
BigChimp · 2014-03-23 17:06

Yes. I first want to have proper tests for ODF format before
introducing a new patch that may change behaviour.

I was describing what I hit on when implementing those tests, which
happens to be date/time stuff... Just background info.

----------------------------------------------------------------------
wp · 2014-03-24 22:01

QuoteMy suggestion: could you split up the patch so we can first
implement and run the tests part (should be easy enough by going to
the tests directory & doing svn diff to get only those changes).
My patch and the related tests are completely separate from your
changes for ods. For the formula support, I added tests\rpntests.inc
and modified tests\manualtests, the xlsbiff* units, xlscommon,
fprspreadsheet and fpsutils.

----------------------------------------------------------------------
BigChimp · 2014-03-25 14:53

Quote from: wp on March 24, 2014, 11:01:15 pmQuoteMy suggestion: could
you split up the patch so we can first implement and run the tests
part (should be easy enough by going to the tests directory & doing
svn diff to get only those changes).
My patch and the related tests are completely separate from your
changes for ods. For the formula support, I added tests\rpntests.inc
and modified tests\manualtests, the xlsbiff* units, xlscommon,
fprspreadsheet and fpsutils.
I have understood already you intended no changes to ODF. Running the
unit tests that include ODF files will however confirm that there are
no inadvertent side effects in case manual review fails.

I'd suggest you just leave things and I'll have a look at your
existing patch and split it out myself when I have time.

Thanks

----------------------------------------------------------------------
BigChimp · 2014-04-08 09:49

Tested & committed, thanks a lot!

----------------------------------------------------------------------
wp · 2014-04-08 19:05

Thanks for committing. Seems to work fine. I'll add a chapter to the
wiki.

Maybe you already know that, but the ODS test reports some issues, I
am attaching the xml output of the test suite. Some of them are due to
rounding errors:

"TSpreadReadStringTests.TestReadODFString10: Test value mismatch cell
Texts!A11 expected: 59.000.000,12 but was: 59000000,1234"

----------------------------------------------------------------------
BigChimp · 2014-04-09 07:34

Quote from: wp on April 08, 2014, 09:05:01 pmMaybe you already know
that, but the ODS test reports some issues,
Why do you think I've been investing in more test coverage
I first want to make sure there are no regressions; then aim at fixing
existing bugs.
After that, I think it's time for another stable release...

Code: [Select]SELECT r.OS, r.CPU, r.TESTSUITE,
    r.TESTNAME, r.TESTRESULT,
    r.EXCEPTIONCLASS, r.EXCEPTIONMESSAGE
FROM FLATSORTED r
where r.revisionid=2931
and (r.testresult<>'OK') and (r.testresult<>'Ignored')
order by r.testresultid,r.testid
gives attached results on fpc trunk