3 ms·
It's proprietary for the time being; but in short, it is more straightforward than I thought it would be. We are working with LibreOffice Calc ODS sheets, whic
by microcolonel 7y ago
It's proprietary for the time being; but in short, it is more straightforward than I thought it would be.
We are working with LibreOffice Calc ODS sheets, which are pretty terrible as a format (since the references are not normalized in the formulas, they can't repeat them even when they behave identically, and they duplicate most of the XML namespaces in the attributes).
We parse and normalize the references from A1 to R1C1 form, and then deduplicate the formulas (by text) and extract all of the immediates (and mark some of them as input, so that they can be varied at runtime).
Then we pass the deduplicated formulas through instaparse (which is spectacular) with a relatively simple grammar, and propagate some of the constants.
I then extract the references from the AST, while at the same time replacing SUMIF/MINIFS/MAXIFS/AVERAGEIF and similar with simple addition/min/max of known cells, where the tests are known at compile time. Then those ASTs are complied to functions (ignoring our cross-function optimizations).
Then it's just down to generating a complete DAG of dependencies, and using that to sort the assignments (cells) topologically.
The sheet can be evaluated naiively at that point by injecting the references into each subsequent assignment/cell and storing the result in a map (ranges injected as a seq over a range).
There's a lot more to it, and it's getting better all the time, but that's the gist of it. Many real spreadsheets are not well-behaved, and they have dependency patterns which are more difficult to handle (i.e. ranges that refer to the current cell, or future cells, dynamically). The compiled output is getting more and more static, and will probably be reduced to some form of ssa, possibly even well-formed enough to be popped casually into LLVM.
It would be some help if the ODS format were improved, it takes several seconds just to parse the hundreds of megabytes of XML in our amazing spreadsheet, and a lot of it is redundant.
- networked 7y agoInteresting project! Could you explain what you mean by "since the references are not normalized in the formulas, they can't repeat them even when they behave identically"? Do you mean the normalization from A1 to R1C1 that you mention later in the post or something else?
- microcolonel 7y agoYes, I mean exactly that. :- )
- networked 7y agoHow does this normalization affect being able to repeat formulas (or references in formulas)?
- microcolonel 7y agoWhile spreadsheets usually display references as though they refer to a specific cell (i.e. A3, B2, etc.), but underneath, the references are relative (unless specifically made absolute, with $ in the case of A1). The common pattern in spreadsheets is to have a set of columns of repeated formulas. i.e. | A | B | C | D | |-----|-----|----------------|-----| 1 | | | | 0.12| 2 | 42| 42| =A2*B2+C1*$D$1 | | 3 | 69| 69| =A3*B3+C2*$D$1 | | Where, you'll note, although the function and reference shape in C2 and C3 is identical, the text is not. Whereas, with R1C1-type references. | 1 | 2 | 3 | 4 | |-----|-----|----------------------------|-----| 1 | | | | 0.12| 2 | 42| 42| =RC[-2]*RC[-1]+R[-1]C*R1C4 | | 3 | 69| 69| =RC[-2]*RC[-1]+R[-1]C*R1C4 | | The text of the formula is exactly the same in both copies. This makes it a lot cheaper to deduplicate them, because we don't need to run the whole parser on the 400k+ formula invocations in our sheet, and then compare the ASTs rather than text; since in this form, there are only a few thousand unique expressions rather than a few hundred thousand.
- networked 7y agoThanks for the explanation. I was confused about the meaning of "repeat". It's a missed opportunity that ODS doesn't store formulas as ASTs in the first place.
- microcolonel 7y ago