Precedents and Dependents

[jollytall]

I read in the Wiki that the formulas are stored in a special tree for faster calculations. Using that, is there an easy way to find those cells that depend on a certain cell and those that this cell is dependent on? I guess that information is already available somewhere, so would be a great help to access it, rather than doing it myself.
Thanks,

[wp]

Formula calculation in fpspreadsheet is not optimized at all: when any cell changes all formulas are recalculated. A formula calculation chain is not implemented.

[jollytall]

Thanks,
I started to write a routine to check (i) the formula of my cell and extract from it all the cells it refers to (precedents), and (ii) go through all cells and check if their formula refers to my cell (dependents) but it is not so easy.
I wrote a simplified parser but I am sure most (if not all) of those steps are already written. Could you suggest a way to easily write e.g. a routine that checks one string (a formula) and quickly gives back if it refers to a given cell (probably another string). I did it, but had to do a lot of messy parsing with operators, brackets, functions, etc, and to make sure that e.g. A1 is not found in a formula =A11. It would be great if I could access some of the internal function, around function parsers. E.g. even the most elementary TsExpressionScanner.IsAlpha is a protected method and thus cannot be accessed, while it could even be a class method as it does not use any other part of the class.
Best would be a function, like tCell.Refers(aCell : pCell) : boolean; Isn't there such a function? I would assume you need it when e.g. you move a cell and change all those cells that depend on it.

[wp]

The formula parser of fpspreadsheet is a variant of the FPExpressionParser coming with FPC (https://wiki.lazarus.freepascal.org/How_To_Use_TFPExpressionParser). It creates a tree of "expression nodes" from a formula string. One extension is the introduction of specific cell and cell range nodes which contain information on the cell or cell range used in that particular element of the expression.

The expression parser has a method IterateNodes() in which the entire tree is traversed recursively so that every node can be visited.

Code: Pascal  [Select][+][-]

1.     function IterateNodes(AProc: TsExprNodeProc; AData1, AData2: Pointer): boolean;
2.  

What happens with each node found depends on the function parameter AProc (signature: procedure(ANode: TsExprNode; AData1, AData2: Pointer; var MustRebuildFormulas: Boolean)). AData1 and AData2 are general-purpose parameters provided by the calling function. The task is to check each node whether it is a cell node and then to collect the cells found in a list. The list can be passed for example in parameter AData1.

Finally the question how to find the formulas: The worksheet collects all formulas in a list accessible in its property Formulas. Each formula record contains the parsed expression as element Parser.

Therefore, the final solution is as follows:

Code: Pascal  [Select][+][-]

1. procedure CollectCells(ANode: TsExprNode; AData1, AData2: Pointer;
2.   var MustRebuildFormulas: Boolean);
3. var
4.   List: TStringList;
5.   cellStr: String;
6.   cellNode: TsCellExprNode;
7.   rngNode: TsCellRangeExprNode;
8.   rng: TsCellRange;
9.   r, c: Cardinal;
10. begin
11.   List := TStringList(AData1);
12.   if ANode.NodeType = rtCell then
13.   begin
14.     cellNode := TsCellExprNode(ANode);
15.     cellStr := GetCellString(cellNode.Row, cellNode.Col);
16.     List.Add(cellStr);
17.   end else
18.   if ANode.NodeType = rtCellRange then
19.   begin
20.     rngNode := TsCellRangeExprNode(ANode);
21.     rng := rngNode.Range;
22.     for r := rng.Row1 to rng.Row2 do
23.       for c := rng.Col1 to rng.Col2 do
24.       begin
25.         cellStr := GetCellString(r, c);
26.         List.Add(cellStr);
27.       end;
28.   end;
29. end;
30.  
31. procedure TForm1.Button1Click(Sender: TObject);
32. var
33.   workbook: TsWorkbook;
34.   worksheet: TsWorksheet;
35.   f: PsFormula;
36.   L: TStringList;
37.   i: Integer;
38. begin
39.   ...
40.   for f in worksheet.Formulas do
41.   begin
42.     Memo1.Lines.Add('Formula in cell ' + GetCellString(f^.Row, f^.Col) +  ': =' + f^.Text);
43.     L := TStringList.Create;
44.     f^.Parser.IterateNodes(@CollectCells, L, nil);
45.     Memo1.Lines.Add('  Used cells: ' + L.CommaText);
46.     Memo1.Lines.Add('');
47.     L.Free;
48.   end;
49. end;    

See attached project as a worked-out example.

But note that the code is a bit simplified because it only considers formulas which have all referenced cells in the same worksheet in which also the cell with the formula itself resides. I am leaving the extension to the more general case of 3d-formulas to you.

[jollytall]

Thanks, it is great. I just made a small function for myself.

Code: Pascal  [Select][+][-]

1. function Precedents(aFormula : tSFormula) : tStringList;
2.   begin
3.   result := tStringList.Create;
4.   result.Duplicates := dupIgnore;
5.   aFormula.Parser.IterateNodes(@CollectCells, result, nil);
6.   end;
7.  

Ideally something like this could be included in the tsFormula, however that is - as I see - a much more general thing and it is only a record, so not even a descendant advanced record can be created from it. Anyway it works as a standalone utility.

I guess the Dependents is a bit more complicated. Am I right that the only way is to iterate through all formulas and check if our cell is in the Precedent list?

[Thaddy]

You are asking for memory leaks with such code, why not:

Code: Pascal  [Select][+][-]

1. procedure Precedents(aFormula : tSFormula;var mylist:TStringlist);
2.   if assigned MyList then
3.   begin
4.     MyList.Duplicates := dupIgnore;
5.     aFormula.Parser.IterateNodes(@CollectCells, MyList, nil);
6.   end;

[wp]

What is your intention? To optimize formula calculation? For this purpose each cell should contain a list of the formulas which reference this cell. So, when this specific cell is changed, the formulas are known which must be recalculated (rather than all as it happens currently).

I refrain from adding additional information to the cell records (TCell) directly because users sometimes have huge spreadsheets and every byte added to the cell record adds to the overall memory load multiplied by the number of cells even if that new feature is needed only by a single cell.

The worksheet already now has several AVLTrees for various purposes: Cells, formulas, cells, hyperlinks. In each of these trees the required information is addressed by means of the row and column indices.

Maybe there should be a new FormulaCalculationTree. Each items in this tree should contain a list of pointers to the formulas which use the associated cell. So, when a formula is entered it is parsed and at this moment it is known which cells are needed by it (similarly as shown in the previous post). Then the formula should be added to the FormulaCalculationTree for each of these cells. When a formula is edited the old formula must be parsed so that it can be deleted from all FormulaCalculationTree items. Likewise, when a formula or cell is deleted.

[jollytall]

@Thaddy, Sure, it is safer, however I am used to generating new class instances and destroying them in the calling routine. If I do not destroy it in the calling routine then it is a (smaller though) memory leak.

@wp, I have some spreadsheets, where columns should look like identical, but sometimes (beyond my control) the same purpose cells are entered into different rows in different columns. So, I try to find if cell1(row1, column1) is the "same" as cell2(row2<>row1, column2<>column1), so make a lot of iteration to "guess" it. One step of the guessing is to check if they add to the same row. E.g. C10 is +C12+C15 and D10 is +D12+D25, so it is likely (a lot of other checks are also done) that C15 and D25 are the same purpose, so I can merge row 25 into row 15. So when I compare C15 and D25 during the guessing, I check where they add into. Now for C15 I iterate all functions (only in column C though) to see that it is C10 where it adds into, and so for D25 to find D10. This step I thought to simplify by a quicker step to find the descendants. Anyway, it is a great package and with one extra iteration I can do it.
Thanks,