From 5ee76b8fb71c69a6ef4800476a28059c739c2822 Mon Sep 17 00:00:00 2001 From: Josh Micich Date: Tue, 23 Sep 2008 00:40:22 +0000 Subject: [PATCH] Optimised the FormulaEvaluator to take cell dependencies into account git-svn-id: https://svn.apache.org/repos/asf/poi/trunk@698047 13f79535-47bb-0310-9956-ffa450edef68 --- src/documentation/content/xdocs/changes.xml | 1 + src/documentation/content/xdocs/status.xml | 1 + .../usermodel/HSSFEvaluationWorkbook.java | 8 +- .../hssf/usermodel/HSSFFormulaEvaluator.java | 31 +- .../apache/poi/ss/formula/CellCacheEntry.java | 114 ++++ .../poi/ss/formula/CellEvaluationFrame.java | 66 ++- .../apache/poi/ss/formula/CellEvaluator.java | 54 -- .../apache/poi/ss/formula/CellLocation.java | 81 +++ .../poi/ss/formula/EvaluationCache.java | 200 +++++-- .../poi/ss/formula/EvaluationTracker.java | 50 +- .../poi/ss/formula/EvaluationWorkbook.java | 2 +- .../poi/ss/formula/IEvaluationListener.java | 39 ++ .../apache/poi/ss/formula/LazyAreaEval.java | 25 +- .../apache/poi/ss/formula/LazyRefEval.java | 36 +- .../poi/ss/formula/SheetRefEvaluator.java | 49 ++ .../poi/ss/formula/WorkbookEvaluator.java | 193 ++++--- .../org/apache/poi/hssf/HSSFTests.java | 2 + .../formula/eval/TestCircularReferences.java | 5 +- .../usermodel/TestFormulaEvaluatorBugs.java | 39 +- .../usermodel/TestHSSFFormulaEvaluator.java | 17 +- .../poi/ss/formula/EvaluationListener.java | 53 ++ .../poi/ss/formula/TestEvaluationCache.java | 492 ++++++++++++++++++ .../formula/WorkbookEvaluatorTestHelper.java | 37 ++ 23 files changed, 1313 insertions(+), 282 deletions(-) create mode 100644 src/java/org/apache/poi/ss/formula/CellCacheEntry.java delete mode 100644 src/java/org/apache/poi/ss/formula/CellEvaluator.java create mode 100644 src/java/org/apache/poi/ss/formula/CellLocation.java create mode 100644 src/java/org/apache/poi/ss/formula/IEvaluationListener.java create mode 100644 src/java/org/apache/poi/ss/formula/SheetRefEvaluator.java create mode 100644 src/testcases/org/apache/poi/ss/formula/EvaluationListener.java create mode 100644 src/testcases/org/apache/poi/ss/formula/TestEvaluationCache.java create mode 100644 src/testcases/org/apache/poi/ss/formula/WorkbookEvaluatorTestHelper.java diff --git a/src/documentation/content/xdocs/changes.xml b/src/documentation/content/xdocs/changes.xml index 3afe4e077b..c054f65be1 100644 --- a/src/documentation/content/xdocs/changes.xml +++ b/src/documentation/content/xdocs/changes.xml @@ -37,6 +37,7 @@ + Optimised the FormulaEvaluator to take cell dependencies into account 16936 - Initial support for whole-row cell styling Update hssf.extractor.ExcelExtractor to optionally output blank cells too Include the sheet name in the output of examples.XLS2CSVmra diff --git a/src/documentation/content/xdocs/status.xml b/src/documentation/content/xdocs/status.xml index d745ce41eb..b416d344fa 100644 --- a/src/documentation/content/xdocs/status.xml +++ b/src/documentation/content/xdocs/status.xml @@ -34,6 +34,7 @@ + Optimised the FormulaEvaluator to take cell dependencies into account 16936 - Initial support for whole-row cell styling Update hssf.extractor.ExcelExtractor to optionally output blank cells too Include the sheet name in the output of examples.XLS2CSVmra diff --git a/src/java/org/apache/poi/hssf/usermodel/HSSFEvaluationWorkbook.java b/src/java/org/apache/poi/hssf/usermodel/HSSFEvaluationWorkbook.java index 16ef3b2a9f..a9c16b090d 100644 --- a/src/java/org/apache/poi/hssf/usermodel/HSSFEvaluationWorkbook.java +++ b/src/java/org/apache/poi/hssf/usermodel/HSSFEvaluationWorkbook.java @@ -71,11 +71,9 @@ public final class HSSFEvaluationWorkbook implements FormulaRenderingWorkbook, E public HSSFSheet getSheet(int sheetIndex) { return _uBook.getSheetAt(sheetIndex); } - - public HSSFSheet getSheetByExternSheetIndex(int externSheetIndex) { - int sheetIndex = _iBook.getSheetIndexFromExternSheetIndex(externSheetIndex); - return _uBook.getSheetAt(sheetIndex); - } + public int convertFromExternSheetIndex(int externSheetIndex) { + return _iBook.getSheetIndexFromExternSheetIndex(externSheetIndex); +} public HSSFWorkbook getWorkbook() { return _uBook; diff --git a/src/java/org/apache/poi/hssf/usermodel/HSSFFormulaEvaluator.java b/src/java/org/apache/poi/hssf/usermodel/HSSFFormulaEvaluator.java index 1e6aa163c0..ab75f8ba88 100644 --- a/src/java/org/apache/poi/hssf/usermodel/HSSFFormulaEvaluator.java +++ b/src/java/org/apache/poi/hssf/usermodel/HSSFFormulaEvaluator.java @@ -19,6 +19,7 @@ package org.apache.poi.hssf.usermodel; import java.util.Iterator; +import org.apache.poi.hssf.record.formula.eval.BlankEval; import org.apache.poi.hssf.record.formula.eval.BoolEval; import org.apache.poi.hssf.record.formula.eval.ErrorEval; import org.apache.poi.hssf.record.formula.eval.NumberEval; @@ -50,14 +51,7 @@ public class HSSFFormulaEvaluator { } } public HSSFFormulaEvaluator(HSSFWorkbook workbook) { - _bookEvaluator = new WorkbookEvaluator(HSSFEvaluationWorkbook.create(workbook)); - } - - /** - * TODO for debug/test use - */ - /* package */ int getEvaluationCount() { - return _bookEvaluator.getEvaluationCount(); + _bookEvaluator = new WorkbookEvaluator(HSSFEvaluationWorkbook.create(workbook)); } /** @@ -81,12 +75,23 @@ public class HSSFFormulaEvaluator { _bookEvaluator.clearAllCachedResultValues(); } /** + * Sets the cached value for a plain (non-formula) cell. * Should be called whenever there are changes to individual input cells in the evaluated workbook. * Failure to call this method after changing cell values will cause incorrect behaviour * of the evaluate~ methods of this class + * @param never null. Use {@link BlankEval#INSTANCE} when the cell is being + * cleared. Otherwise an instance of {@link NumberEval}, {@link StringEval}, {@link BoolEval} + * or {@link ErrorEval} to represent a plain cell value. */ - public void clearCachedResultValue(HSSFSheet sheet, int rowIndex, int columnIndex) { - _bookEvaluator.clearCachedResultValue(sheet, rowIndex, columnIndex); + public void setCachedPlainValue(HSSFSheet sheet, int rowIndex, int columnIndex, ValueEval value) { + _bookEvaluator.setCachedPlainValue(sheet, rowIndex, columnIndex, value); + } + /** + * Should be called to tell the cell value cache that the specified cell has just become a + * formula cell, or the formula text has changed + */ + public void notifySetFormula(HSSFSheet sheet, int rowIndex, int columnIndex) { + _bookEvaluator.notifySetFormula(sheet, rowIndex, columnIndex); } /** @@ -95,7 +100,9 @@ public class HSSFFormulaEvaluator { * the cell and also its cell type. This method should be preferred over * evaluateInCell() when the call should not modify the contents of the * original cell. - * @param cell + * + * @param cell may be null signifying that the cell is not present (or blank) + * @return null if the supplied cell is null or blank */ public CellValue evaluate(HSSFCell cell) { if (cell == null) { @@ -113,6 +120,8 @@ public class HSSFFormulaEvaluator { return new CellValue(cell.getNumericCellValue()); case HSSFCell.CELL_TYPE_STRING: return new CellValue(cell.getRichStringCellValue().getString()); + case HSSFCell.CELL_TYPE_BLANK: + return null; } throw new IllegalStateException("Bad cell type (" + cell.getCellType() + ")"); } diff --git a/src/java/org/apache/poi/ss/formula/CellCacheEntry.java b/src/java/org/apache/poi/ss/formula/CellCacheEntry.java new file mode 100644 index 0000000000..861874c25b --- /dev/null +++ b/src/java/org/apache/poi/ss/formula/CellCacheEntry.java @@ -0,0 +1,114 @@ +/* ==================================================================== + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +==================================================================== */ + +package org.apache.poi.ss.formula; + +import java.util.HashSet; +import java.util.Set; + +import org.apache.poi.hssf.record.formula.eval.BoolEval; +import org.apache.poi.hssf.record.formula.eval.ErrorEval; +import org.apache.poi.hssf.record.formula.eval.NumberEval; +import org.apache.poi.hssf.record.formula.eval.StringEval; +import org.apache.poi.hssf.record.formula.eval.ValueEval; + +/** + * Stores the parameters that identify the evaluation of one cell.
+ */ +final class CellCacheEntry { + private ValueEval _value; + private final Set _consumingCells; + private CellLocation[] _usedCells; + private boolean _isPlainValueCell; + + public CellCacheEntry() { + _consumingCells = new HashSet(); + } + public boolean updatePlainValue(ValueEval value) { + boolean wasChanged = false; + if (!_isPlainValueCell) { + wasChanged = true; + } + if (!areValuesEqual(_value, value)) { + wasChanged = true; + } + _isPlainValueCell = true; + _value = value; + _usedCells = null; + return wasChanged; + } + private boolean areValuesEqual(ValueEval a, ValueEval b) { + if (a == null) { + return false; + } + Class cls = a.getClass(); + if (cls != b.getClass()) { + // value type is changing + return false; + } + if (cls == NumberEval.class) { + return ((NumberEval)a).getNumberValue() == ((NumberEval)b).getNumberValue(); + } + if (cls == StringEval.class) { + return ((StringEval)a).getStringValue().equals(((StringEval)b).getStringValue()); + } + if (cls == BoolEval.class) { + return ((BoolEval)a).getBooleanValue() == ((BoolEval)b).getBooleanValue(); + } + if (cls == ErrorEval.class) { + return ((ErrorEval)a).getErrorCode() == ((ErrorEval)b).getErrorCode(); + } + throw new IllegalStateException("Unexpected value class (" + cls.getName() + ")"); + } + public void setFormulaResult(ValueEval value, CellLocation[] usedCells) { + _isPlainValueCell = false; + _value = value; + _usedCells = usedCells; + } + public void addConsumingCell(CellLocation cellLoc) { + _consumingCells.add(cellLoc); + + } + public CellLocation[] getConsumingCells() { + int nItems = _consumingCells.size(); + if (nItems < 1) { + return CellLocation.EMPTY_ARRAY; + } + CellLocation[] result = new CellLocation[nItems]; + _consumingCells.toArray(result); + return result; + } + public CellLocation[] getUsedCells() { + return _usedCells; + } + public void clearConsumingCell(CellLocation fc) { + if(!_consumingCells.remove(fc)) { + throw new IllegalStateException("Cell '" + fc.formatAsString() + "' does not use this cell"); + } + + } + public ValueEval getValue() { + ValueEval result = _value; + if (result == null) { + if (_isPlainValueCell) { + throw new IllegalStateException("Plain value cell should always have a value"); + + } + } + return result; + } +} \ No newline at end of file diff --git a/src/java/org/apache/poi/ss/formula/CellEvaluationFrame.java b/src/java/org/apache/poi/ss/formula/CellEvaluationFrame.java index b6f542a082..1d438527ae 100644 --- a/src/java/org/apache/poi/ss/formula/CellEvaluationFrame.java +++ b/src/java/org/apache/poi/ss/formula/CellEvaluationFrame.java @@ -17,55 +17,47 @@ package org.apache.poi.ss.formula; +import java.util.HashSet; +import java.util.Set; + /** - * Stores the parameters that identify the evaluation of one cell.
+ * Stores details about the current evaluation of a cell.
*/ final class CellEvaluationFrame { - private final int _sheetIndex; - private final int _srcRowNum; - private final int _srcColNum; - private final int _hashCode; - - public CellEvaluationFrame(int sheetIndex, int srcRowNum, int srcColNum) { - if (sheetIndex < 0) { - throw new IllegalArgumentException("sheetIndex must not be negative"); - } - _sheetIndex = sheetIndex; - _srcRowNum = srcRowNum; - _srcColNum = srcColNum; - _hashCode = sheetIndex + 17 * (srcRowNum + 17 * srcColNum); - } + private final CellLocation _cellLocation; + private final Set _usedCells; - public boolean equals(Object obj) { - CellEvaluationFrame other = (CellEvaluationFrame) obj; - if (_sheetIndex != other._sheetIndex) { - return false; - } - if (_srcRowNum != other._srcRowNum) { - return false; - } - if (_srcColNum != other._srcColNum) { - return false; - } - return true; - } - public int hashCode() { - return _hashCode; + public CellEvaluationFrame(CellLocation cellLoc) { + _cellLocation = cellLoc; + _usedCells = new HashSet(); } - - /** - * @return human readable string for debug purposes - */ - public String formatAsString() { - return "R=" + _srcRowNum + " C=" + _srcColNum + " ShIx=" + _sheetIndex; + public CellLocation getCoordinates() { + return _cellLocation; } public String toString() { StringBuffer sb = new StringBuffer(64); sb.append(getClass().getName()).append(" ["); - sb.append(formatAsString()); + sb.append(_cellLocation.formatAsString()); sb.append("]"); return sb.toString(); } + public void addUsedCell(CellLocation coordinates) { + _usedCells.add(coordinates); + } + /** + * @return never null, (possibly empty) array of all cells directly used while + * evaluating the formula of this frame. For non-formula cells this will always be an empty + * array; + */ + public CellLocation[] getUsedCells() { + int nItems = _usedCells.size(); + if (nItems < 1) { + return CellLocation.EMPTY_ARRAY; + } + CellLocation[] result = new CellLocation[nItems]; + _usedCells.toArray(result); + return result; + } } \ No newline at end of file diff --git a/src/java/org/apache/poi/ss/formula/CellEvaluator.java b/src/java/org/apache/poi/ss/formula/CellEvaluator.java deleted file mode 100644 index 22846c2d4f..0000000000 --- a/src/java/org/apache/poi/ss/formula/CellEvaluator.java +++ /dev/null @@ -1,54 +0,0 @@ -package org.apache.poi.ss.formula; - -import org.apache.poi.hssf.record.formula.eval.BlankEval; -import org.apache.poi.hssf.record.formula.eval.BoolEval; -import org.apache.poi.hssf.record.formula.eval.ErrorEval; -import org.apache.poi.hssf.record.formula.eval.NumberEval; -import org.apache.poi.hssf.record.formula.eval.StringEval; -import org.apache.poi.hssf.record.formula.eval.ValueEval; -import org.apache.poi.hssf.usermodel.HSSFCell; -import org.apache.poi.hssf.usermodel.HSSFSheet; - -final class CellEvaluator { - - private final WorkbookEvaluator _bookEvaluator; - private final EvaluationTracker _tracker; - - public CellEvaluator(WorkbookEvaluator bookEvaluator, EvaluationTracker tracker) { - _bookEvaluator = bookEvaluator; - _tracker = tracker; - } - - /** - * Given a cell, find its type and from that create an appropriate ValueEval - * impl instance and return that. Since the cell could be an external - * reference, we need the sheet that this belongs to. - * Non existent cells are treated as empty. - */ - public ValueEval getEvalForCell(HSSFCell cell) { - - if (cell == null) { - return BlankEval.INSTANCE; - } - switch (cell.getCellType()) { - case HSSFCell.CELL_TYPE_NUMERIC: - return new NumberEval(cell.getNumericCellValue()); - case HSSFCell.CELL_TYPE_STRING: - return new StringEval(cell.getRichStringCellValue().getString()); - case HSSFCell.CELL_TYPE_FORMULA: - return _bookEvaluator.internalEvaluate(cell, _tracker); - case HSSFCell.CELL_TYPE_BOOLEAN: - return BoolEval.valueOf(cell.getBooleanCellValue()); - case HSSFCell.CELL_TYPE_BLANK: - return BlankEval.INSTANCE; - case HSSFCell.CELL_TYPE_ERROR: - return ErrorEval.valueOf(cell.getErrorCellValue()); - } - throw new RuntimeException("Unexpected cell type (" + cell.getCellType() + ")"); - } - - public String getSheetName(HSSFSheet sheet) { - return _bookEvaluator.getSheetName(sheet); - } - -} diff --git a/src/java/org/apache/poi/ss/formula/CellLocation.java b/src/java/org/apache/poi/ss/formula/CellLocation.java new file mode 100644 index 0000000000..d6bb9b7bfb --- /dev/null +++ b/src/java/org/apache/poi/ss/formula/CellLocation.java @@ -0,0 +1,81 @@ +/* ==================================================================== + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +==================================================================== */ + +package org.apache.poi.ss.formula; + +/** + * Stores the parameters that identify the evaluation of one cell.
+ */ +final class CellLocation { + public static final CellLocation[] EMPTY_ARRAY = { }; + + private final int _sheetIndex; + private final int _rowIndex; + private final int _columnIndex; + private final int _hashCode; + + public CellLocation(int sheetIndex, int rowIndex, int columnIndex) { + if (sheetIndex < 0) { + throw new IllegalArgumentException("sheetIndex must not be negative"); + } + _sheetIndex = sheetIndex; + _rowIndex = rowIndex; + _columnIndex = columnIndex; + _hashCode = sheetIndex + 17 * (rowIndex + 17 * columnIndex); + } + public int getSheetIndex() { + return _sheetIndex; + } + public int getRowIndex() { + return _rowIndex; + } + public int getColumnIndex() { + return _columnIndex; + } + + public boolean equals(Object obj) { + CellLocation other = (CellLocation) obj; + if (getSheetIndex() != other.getSheetIndex()) { + return false; + } + if (getRowIndex() != other.getRowIndex()) { + return false; + } + if (getColumnIndex() != other.getColumnIndex()) { + return false; + } + return true; + } + public int hashCode() { + return _hashCode; + } + + /** + * @return human readable string for debug purposes + */ + public String formatAsString() { + return "ShIx=" + getSheetIndex() + " R=" + getRowIndex() + " C=" + getColumnIndex(); + } + + public String toString() { + StringBuffer sb = new StringBuffer(64); + sb.append(getClass().getName()).append(" ["); + sb.append(formatAsString()); + sb.append("]"); + return sb.toString(); + } +} \ No newline at end of file diff --git a/src/java/org/apache/poi/ss/formula/EvaluationCache.java b/src/java/org/apache/poi/ss/formula/EvaluationCache.java index d78f4a7286..fdc933f6fa 100644 --- a/src/java/org/apache/poi/ss/formula/EvaluationCache.java +++ b/src/java/org/apache/poi/ss/formula/EvaluationCache.java @@ -17,9 +17,13 @@ package org.apache.poi.ss.formula; +import java.util.Arrays; +import java.util.Collections; +import java.util.Comparator; import java.util.HashMap; -import java.util.List; +import java.util.HashSet; import java.util.Map; +import java.util.Set; import org.apache.poi.hssf.record.formula.eval.ValueEval; import org.apache.poi.hssf.usermodel.HSSFFormulaEvaluator; @@ -34,66 +38,176 @@ import org.apache.poi.hssf.usermodel.HSSFFormulaEvaluator; */ final class EvaluationCache { - private static final CellEvaluationFrame[] EMPTY_CEF_ARRAY = { }; - private final Map _valuesByKey; - private final Map _consumingCellsByDest; + private final Map _entriesByLocation; + private final Map _consumingCellsByUsedCells; + /** only used for testing. null otherwise */ + private final IEvaluationListener _evaluationListener; - /* package */EvaluationCache() { - _valuesByKey = new HashMap(); - _consumingCellsByDest = new HashMap(); + /* package */EvaluationCache(IEvaluationListener evaluationListener) { + _evaluationListener = evaluationListener; + _entriesByLocation = new HashMap(); + _consumingCellsByUsedCells = new HashMap(); } - public ValueEval getValue(int sheetIndex, int srcRowNum, int srcColNum) { - return getValue(new CellEvaluationFrame(sheetIndex, srcRowNum, srcColNum)); + /** + * @param cellLoc never null + * @return only ever null for formula cells that have had their cached value cleared + */ + public ValueEval getValue(CellLocation cellLoc) { + return getEntry(cellLoc).getValue(); } - /* package */ ValueEval getValue(CellEvaluationFrame key) { - return (ValueEval) _valuesByKey.get(key); + /** + * @param cellLoc + * @param usedCells never null, (possibly zero length) array of all cells actually + * directly used when evaluating the formula + * @param isPlainValue pass true if cellLoc refers to a plain value (non-formula) + * cell, false for a formula cell. + * @param value the value of a non-formula cell or the result of evaluating the cell formula + * Pass null to signify clearing the cached result of a formula cell) + */ + public void setValue(CellLocation cellLoc, boolean isPlainValue, + CellLocation[] usedCells, ValueEval value) { + + CellCacheEntry existingEntry = (CellCacheEntry) _entriesByLocation.get(cellLoc); + if (existingEntry != null && existingEntry.getValue() != null) { + if (isPlainValue) { + // can set a plain cell cached value any time + } else if (value == null) { + // or clear the cached value of a formula cell at any time + } else { + // but a formula cached value would only be getting updated if the cache didn't have a value to start with + throw new IllegalStateException("Already have cached value for this cell: " + + cellLoc.formatAsString()); + } + } + if (_evaluationListener == null) { + // optimisation - don't bother sorting if there is no listener. + } else { + // for testing + // make order of callbacks to listener more deterministic + Arrays.sort(usedCells, CellLocationComparator); + } + CellCacheEntry entry = getEntry(cellLoc); + CellLocation[] consumingFormulaCells = entry.getConsumingCells(); + CellLocation[] prevUsedCells = entry.getUsedCells(); + if (isPlainValue) { + + if(!entry.updatePlainValue(value)) { + return; + } + } else { + entry.setFormulaResult(value, usedCells); + for (int i = 0; i < usedCells.length; i++) { + getEntry(usedCells[i]).addConsumingCell(cellLoc); + } + } + // need to tell all cells that were previously used, but no longer are, + // that they are not consumed by this cell any more + unlinkConsumingCells(prevUsedCells, usedCells, cellLoc); + + // clear all cells that directly or indirectly depend on this one + recurseClearCachedFormulaResults(consumingFormulaCells, 0); } - public void setValue(int sheetIndex, int srcRowNum, int srcColNum, ValueEval value) { - setValue(new CellEvaluationFrame(sheetIndex, srcRowNum, srcColNum), value); + private void unlinkConsumingCells(CellLocation[] prevUsedCells, CellLocation[] usedCells, + CellLocation cellLoc) { + if (prevUsedCells == null) { + return; + } + int nPrevUsed = prevUsedCells.length; + if (nPrevUsed < 1) { + return; + } + int nUsed = usedCells.length; + Set usedSet; + if (nUsed < 1) { + usedSet = Collections.EMPTY_SET; + } else { + usedSet = new HashSet(nUsed * 3 / 2); + for (int i = 0; i < nUsed; i++) { + usedSet.add(usedCells[i]); + } + } + for (int i = 0; i < nPrevUsed; i++) { + CellLocation prevUsed = prevUsedCells[i]; + if (!usedSet.contains(prevUsed)) { + // previously was used by cellLoc, but not anymore + getEntry(prevUsed).clearConsumingCell(cellLoc); + if (_evaluationListener != null) { + //TODO _evaluationListener.onUnconsume(prevUsed.getSheetIndex(), etc) + } + } + } + } - /* package */ void setValue(CellEvaluationFrame key, ValueEval value) { - if (_valuesByKey.containsKey(key)) { - throw new RuntimeException("Already have cached value for this cell"); + /** + * Calls formulaCell.setFormulaResult(null, null) recursively all the way up the tree of + * dependencies. Calls usedCell.clearConsumingCell(fc) for each child of a cell that is + * cleared along the way. + * @param formulaCells + */ + private void recurseClearCachedFormulaResults(CellLocation[] formulaCells, int depth) { + int nextDepth = depth+1; + for (int i = 0; i < formulaCells.length; i++) { + CellLocation fc = formulaCells[i]; + CellCacheEntry formulaCell = getEntry(fc); + CellLocation[] usedCells = formulaCell.getUsedCells(); + if (usedCells != null) { + for (int j = 0; j < usedCells.length; j++) { + CellCacheEntry usedCell = getEntry(usedCells[j]); + usedCell.clearConsumingCell(fc); + } + } + if (_evaluationListener != null) { + ValueEval value = formulaCell.getValue(); + _evaluationListener.onClearDependentCachedValue(fc.getSheetIndex(), fc.getRowIndex(), fc.getColumnIndex(), value, nextDepth); + } + formulaCell.setFormulaResult(null, null); + recurseClearCachedFormulaResults(formulaCell.getConsumingCells(), nextDepth); } - _valuesByKey.put(key, value); } + private CellCacheEntry getEntry(CellLocation cellLoc) { + CellCacheEntry result = (CellCacheEntry)_entriesByLocation.get(cellLoc); + if (result == null) { + result = new CellCacheEntry(); + _entriesByLocation.put(cellLoc, result); + } + return result; + } /** * Should be called whenever there are changes to input cells in the evaluated workbook. */ public void clear() { - _valuesByKey.clear(); - } - - public void clearValue(int sheetIndex, int rowIndex, int columnIndex) { - clearValuesRecursive(new CellEvaluationFrame(sheetIndex, rowIndex, columnIndex)); - - } - - private void clearValuesRecursive(CellEvaluationFrame cef) { - CellEvaluationFrame[] consumingCells = getConsumingCells(cef); - for (int i = 0; i < consumingCells.length; i++) { - clearValuesRecursive(consumingCells[i]); + if(_evaluationListener != null) { + _evaluationListener.onClearWholeCache(); } - _valuesByKey.remove(cef); - _consumingCellsByDest.remove(cef); + _entriesByLocation.clear(); + _consumingCellsByUsedCells.clear(); } - private CellEvaluationFrame[] getConsumingCells(CellEvaluationFrame cef) { - List temp = (List) _consumingCellsByDest.get(cef); - if (temp == null) { - return EMPTY_CEF_ARRAY; - } - int nItems = temp.size(); - if (temp.size() < 1) { - return EMPTY_CEF_ARRAY; + + private static final Comparator CellLocationComparator = new Comparator() { + + public int compare(Object a, Object b) { + CellLocation clA = (CellLocation) a; + CellLocation clB = (CellLocation) b; + + int cmp; + cmp = clA.getSheetIndex() - clB.getSheetIndex(); + if (cmp != 0) { + return cmp; + } + cmp = clA.getRowIndex() - clB.getRowIndex(); + if (cmp != 0) { + return cmp; + } + cmp = clA.getColumnIndex() - clB.getColumnIndex(); + + return cmp; } - CellEvaluationFrame[] result = new CellEvaluationFrame[nItems]; - temp.toArray(result); - return result; - } + + }; } diff --git a/src/java/org/apache/poi/ss/formula/EvaluationTracker.java b/src/java/org/apache/poi/ss/formula/EvaluationTracker.java index 20ab3299af..834941e9be 100755 --- a/src/java/org/apache/poi/ss/formula/EvaluationTracker.java +++ b/src/java/org/apache/poi/ss/formula/EvaluationTracker.java @@ -18,7 +18,9 @@ package org.apache.poi.ss.formula; import java.util.ArrayList; +import java.util.HashSet; import java.util.List; +import java.util.Set; import org.apache.poi.hssf.record.formula.eval.ErrorEval; import org.apache.poi.hssf.record.formula.eval.ValueEval; @@ -36,11 +38,13 @@ import org.apache.poi.hssf.usermodel.HSSFCell; final class EvaluationTracker { private final List _evaluationFrames; + private final Set _currentlyEvaluatingCells; private final EvaluationCache _cache; public EvaluationTracker(EvaluationCache cache) { _cache = cache; _evaluationFrames = new ArrayList(); + _currentlyEvaluatingCells = new HashSet(); } /** @@ -58,14 +62,17 @@ final class EvaluationTracker { * @return true if the specified cell has not been visited yet in the current * evaluation. false if the specified cell is already being evaluated. */ - public ValueEval startEvaluate(int sheetIndex, int srcRowNum, int srcColNum) { - CellEvaluationFrame cef = new CellEvaluationFrame(sheetIndex, srcRowNum, srcColNum); - if (_evaluationFrames.contains(cef)) { + public ValueEval startEvaluate(CellLocation cellLoc) { + if (cellLoc == null) { + throw new IllegalArgumentException("cellLoc must not be null"); + } + if (_currentlyEvaluatingCells.contains(cellLoc)) { return ErrorEval.CIRCULAR_REF_ERROR; } - ValueEval result = _cache.getValue(cef); + ValueEval result = _cache.getValue(cellLoc); if (result == null) { - _evaluationFrames.add(cef); + _currentlyEvaluatingCells.add(cellLoc); + _evaluationFrames.add(new CellEvaluationFrame(cellLoc)); } return result; } @@ -83,24 +90,41 @@ final class EvaluationTracker { * and form more meaningful error messages. * @param result */ - public void endEvaluate(int sheetIndex, int srcRowNum, int srcColNum, ValueEval result) { + public void endEvaluate(CellLocation cellLoc, ValueEval result, boolean isPlainValueCell) { + int nFrames = _evaluationFrames.size(); if (nFrames < 1) { throw new IllegalStateException("Call to endEvaluate without matching call to startEvaluate"); } nFrames--; - CellEvaluationFrame cefExpected = (CellEvaluationFrame) _evaluationFrames.get(nFrames); - CellEvaluationFrame cefActual = new CellEvaluationFrame(sheetIndex, srcRowNum, srcColNum); - if (!cefActual.equals(cefExpected)) { + CellEvaluationFrame frame = (CellEvaluationFrame) _evaluationFrames.get(nFrames); + CellLocation coordinates = frame.getCoordinates(); + if (!coordinates.equals(cellLoc)) { throw new RuntimeException("Wrong cell specified. " + "Corresponding startEvaluate() call was for cell {" - + cefExpected.formatAsString() + "} this endEvaluate() call is for cell {" - + cefActual.formatAsString() + "}"); + + coordinates.formatAsString() + "} this endEvaluate() call is for cell {" + + cellLoc.formatAsString() + "}"); } // else - no problems so pop current frame _evaluationFrames.remove(nFrames); - - _cache.setValue(cefActual, result); + _currentlyEvaluatingCells.remove(coordinates); + + // TODO - don't cache results of volatile formulas + _cache.setValue(coordinates, isPlainValueCell, frame.getUsedCells(), result); + } + /** + * Tells the currently evaluating cell frame that it has a dependency on the specified + * usedCell + * @param usedCell location of cell which is referenced (and used) by the current cell. + */ + public void acceptDependency(CellLocation usedCell) { + int prevFrameIndex = _evaluationFrames.size()-1; + if (prevFrameIndex < 0) { + throw new IllegalStateException("Call to acceptDependency without prior call to startEvaluate"); + } + CellEvaluationFrame consumingFrame = (CellEvaluationFrame) _evaluationFrames.get(prevFrameIndex); + consumingFrame.addUsedCell(usedCell); } + } diff --git a/src/java/org/apache/poi/ss/formula/EvaluationWorkbook.java b/src/java/org/apache/poi/ss/formula/EvaluationWorkbook.java index 29083f7a5d..664df2c6ab 100644 --- a/src/java/org/apache/poi/ss/formula/EvaluationWorkbook.java +++ b/src/java/org/apache/poi/ss/formula/EvaluationWorkbook.java @@ -35,7 +35,7 @@ public interface EvaluationWorkbook { HSSFSheet getSheet(int sheetIndex); - HSSFSheet getSheetByExternSheetIndex(int externSheetIndex); + int convertFromExternSheetIndex(int externSheetIndex); EvaluationName getName(NamePtg namePtg); String resolveNameXText(NameXPtg ptg); Ptg[] getFormulaTokens(HSSFCell cell); diff --git a/src/java/org/apache/poi/ss/formula/IEvaluationListener.java b/src/java/org/apache/poi/ss/formula/IEvaluationListener.java new file mode 100644 index 0000000000..deba4d59b0 --- /dev/null +++ b/src/java/org/apache/poi/ss/formula/IEvaluationListener.java @@ -0,0 +1,39 @@ +/* ==================================================================== + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +==================================================================== */ + +package org.apache.poi.ss.formula; + +import org.apache.poi.hssf.record.formula.Ptg; +import org.apache.poi.hssf.record.formula.eval.ValueEval; + +/** + * Tests can implement this class to track the internal working of the {@link WorkbookEvaluator}.
+ * + * For POI internal testing use only + * + * @author Josh Micich + */ +interface IEvaluationListener { + + void onCacheHit(int sheetIndex, int rowIndex, int columnIndex, ValueEval result); + void onReadPlainValue(int sheetIndex, int srcRowNum, int srcColNum, ValueEval value); + void onStartEvaluate(int sheetIndex, int rowIndex, int columnIndex, Ptg[] ptgs); + void onEndEvaluate(int sheetIndex, int rowIndex, int columnIndex, ValueEval result); + void onClearWholeCache(); + void onClearCachedValue(int sheetIndex, int rowIndex, int columnIndex, ValueEval value); + void onClearDependentCachedValue(int sheetIndex, int rowIndex, int columnIndex, ValueEval value, int depth); +} diff --git a/src/java/org/apache/poi/ss/formula/LazyAreaEval.java b/src/java/org/apache/poi/ss/formula/LazyAreaEval.java index 07c368ed0f..3b891fbbb8 100644 --- a/src/java/org/apache/poi/ss/formula/LazyAreaEval.java +++ b/src/java/org/apache/poi/ss/formula/LazyAreaEval.java @@ -21,11 +21,7 @@ import org.apache.poi.hssf.record.formula.AreaI; import org.apache.poi.hssf.record.formula.AreaI.OffsetArea; import org.apache.poi.hssf.record.formula.eval.AreaEval; import org.apache.poi.hssf.record.formula.eval.AreaEvalBase; -import org.apache.poi.hssf.record.formula.eval.BlankEval; import org.apache.poi.hssf.record.formula.eval.ValueEval; -import org.apache.poi.hssf.usermodel.HSSFCell; -import org.apache.poi.hssf.usermodel.HSSFRow; -import org.apache.poi.hssf.usermodel.HSSFSheet; import org.apache.poi.hssf.util.CellReference; /** @@ -34,12 +30,10 @@ import org.apache.poi.hssf.util.CellReference; */ final class LazyAreaEval extends AreaEvalBase { - private final HSSFSheet _sheet; - private final CellEvaluator _evaluator; + private final SheetRefEvaluator _evaluator; - public LazyAreaEval(AreaI ptg, HSSFSheet sheet, CellEvaluator evaluator) { + public LazyAreaEval(AreaI ptg, SheetRefEvaluator evaluator) { super(ptg); - _sheet = sheet; _evaluator = evaluator; } @@ -48,30 +42,21 @@ final class LazyAreaEval extends AreaEvalBase { int rowIx = (relativeRowIndex + getFirstRow() ) & 0xFFFF; int colIx = (relativeColumnIndex + getFirstColumn() ) & 0x00FF; - HSSFRow row = _sheet.getRow(rowIx); - if (row == null) { - return BlankEval.INSTANCE; - } - HSSFCell cell = row.getCell(colIx); - if (cell == null) { - return BlankEval.INSTANCE; - } - return _evaluator.getEvalForCell(cell); + return _evaluator.getEvalForCell(rowIx, colIx); } public AreaEval offset(int relFirstRowIx, int relLastRowIx, int relFirstColIx, int relLastColIx) { AreaI area = new OffsetArea(getFirstRow(), getFirstColumn(), relFirstRowIx, relLastRowIx, relFirstColIx, relLastColIx); - return new LazyAreaEval(area, _sheet, _evaluator); + return new LazyAreaEval(area, _evaluator); } public String toString() { CellReference crA = new CellReference(getFirstRow(), getFirstColumn()); CellReference crB = new CellReference(getLastRow(), getLastColumn()); StringBuffer sb = new StringBuffer(); sb.append(getClass().getName()).append("["); - String sheetName = _evaluator.getSheetName(_sheet); - sb.append(sheetName); + sb.append(_evaluator.getSheetName()); sb.append('!'); sb.append(crA.formatAsString()); sb.append(':'); diff --git a/src/java/org/apache/poi/ss/formula/LazyRefEval.java b/src/java/org/apache/poi/ss/formula/LazyRefEval.java index fa1f3a383d..f25e86fc40 100644 --- a/src/java/org/apache/poi/ss/formula/LazyRefEval.java +++ b/src/java/org/apache/poi/ss/formula/LazyRefEval.java @@ -22,12 +22,8 @@ import org.apache.poi.hssf.record.formula.Ref3DPtg; import org.apache.poi.hssf.record.formula.RefPtg; import org.apache.poi.hssf.record.formula.AreaI.OffsetArea; import org.apache.poi.hssf.record.formula.eval.AreaEval; -import org.apache.poi.hssf.record.formula.eval.BlankEval; import org.apache.poi.hssf.record.formula.eval.RefEvalBase; import org.apache.poi.hssf.record.formula.eval.ValueEval; -import org.apache.poi.hssf.usermodel.HSSFCell; -import org.apache.poi.hssf.usermodel.HSSFRow; -import org.apache.poi.hssf.usermodel.HSSFSheet; import org.apache.poi.hssf.util.CellReference; /** @@ -36,34 +32,19 @@ import org.apache.poi.hssf.util.CellReference; */ final class LazyRefEval extends RefEvalBase { - private final HSSFSheet _sheet; - private final CellEvaluator _evaluator; + private final SheetRefEvaluator _evaluator; - - public LazyRefEval(RefPtg ptg, HSSFSheet sheet, CellEvaluator evaluator) { + public LazyRefEval(RefPtg ptg, SheetRefEvaluator sre) { super(ptg.getRow(), ptg.getColumn()); - _sheet = sheet; - _evaluator = evaluator; + _evaluator = sre; } - public LazyRefEval(Ref3DPtg ptg, HSSFSheet sheet, CellEvaluator evaluator) { + public LazyRefEval(Ref3DPtg ptg, SheetRefEvaluator sre) { super(ptg.getRow(), ptg.getColumn()); - _sheet = sheet; - _evaluator = evaluator; + _evaluator = sre; } public ValueEval getInnerValueEval() { - int rowIx = getRow(); - int colIx = getColumn(); - - HSSFRow row = _sheet.getRow(rowIx); - if (row == null) { - return BlankEval.INSTANCE; - } - HSSFCell cell = row.getCell(colIx); - if (cell == null) { - return BlankEval.INSTANCE; - } - return _evaluator.getEvalForCell(cell); + return _evaluator.getEvalForCell(getRow(), getColumn()); } public AreaEval offset(int relFirstRowIx, int relLastRowIx, int relFirstColIx, int relLastColIx) { @@ -71,15 +52,14 @@ final class LazyRefEval extends RefEvalBase { AreaI area = new OffsetArea(getRow(), getColumn(), relFirstRowIx, relLastRowIx, relFirstColIx, relLastColIx); - return new LazyAreaEval(area, _sheet, _evaluator); + return new LazyAreaEval(area, _evaluator); } public String toString() { CellReference cr = new CellReference(getRow(), getColumn()); StringBuffer sb = new StringBuffer(); sb.append(getClass().getName()).append("["); - String sheetName = _evaluator.getSheetName(_sheet); - sb.append(sheetName); + sb.append(_evaluator.getSheetName()); sb.append('!'); sb.append(cr.formatAsString()); sb.append("]"); diff --git a/src/java/org/apache/poi/ss/formula/SheetRefEvaluator.java b/src/java/org/apache/poi/ss/formula/SheetRefEvaluator.java new file mode 100644 index 0000000000..6babc272cc --- /dev/null +++ b/src/java/org/apache/poi/ss/formula/SheetRefEvaluator.java @@ -0,0 +1,49 @@ +/* ==================================================================== + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +==================================================================== */ + +package org.apache.poi.ss.formula; + +import org.apache.poi.hssf.record.formula.eval.ValueEval; +import org.apache.poi.hssf.usermodel.HSSFSheet; +/** + * + * + * @author Josh Micich + */ +final class SheetRefEvaluator { + + private final WorkbookEvaluator _bookEvaluator; + private final EvaluationTracker _tracker; + private final HSSFSheet _sheet; + private final int _sheetIndex; + + public SheetRefEvaluator(WorkbookEvaluator bookEvaluator, EvaluationTracker tracker, + EvaluationWorkbook _workbook, int sheetIndex) { + _bookEvaluator = bookEvaluator; + _tracker = tracker; + _sheet = _workbook.getSheet(sheetIndex); + _sheetIndex = sheetIndex; + } + + public String getSheetName() { + return _bookEvaluator.getSheetName(_sheetIndex); + } + + public ValueEval getEvalForCell(int rowIndex, int columnIndex) { + return _bookEvaluator.evaluateReference(_sheet, _sheetIndex, rowIndex, columnIndex, _tracker); + } +} diff --git a/src/java/org/apache/poi/ss/formula/WorkbookEvaluator.java b/src/java/org/apache/poi/ss/formula/WorkbookEvaluator.java index 199d35b66e..36ad65b7f1 100644 --- a/src/java/org/apache/poi/ss/formula/WorkbookEvaluator.java +++ b/src/java/org/apache/poi/ss/formula/WorkbookEvaluator.java @@ -17,6 +17,8 @@ package org.apache.poi.ss.formula; +import java.util.IdentityHashMap; +import java.util.Map; import java.util.Stack; import org.apache.poi.hssf.record.formula.Area3DPtg; @@ -51,6 +53,7 @@ import org.apache.poi.hssf.record.formula.eval.RefEval; import org.apache.poi.hssf.record.formula.eval.StringEval; import org.apache.poi.hssf.record.formula.eval.ValueEval; import org.apache.poi.hssf.usermodel.HSSFCell; +import org.apache.poi.hssf.usermodel.HSSFRow; import org.apache.poi.hssf.usermodel.HSSFSheet; import org.apache.poi.hssf.util.CellReference; @@ -67,43 +70,28 @@ import org.apache.poi.hssf.util.CellReference; */ public class WorkbookEvaluator { - /** - * used to track the number of evaluations - */ - private static final class Counter { - public int value; - public int depth; - public Counter() { - value = 0; - } - } - private final EvaluationWorkbook _workbook; private final EvaluationCache _cache; - private Counter _evaluationCounter; + private final IEvaluationListener _evaluationListener; + private final Map _sheetIndexesBySheet; public WorkbookEvaluator(EvaluationWorkbook workbook) { + this (workbook, null); + } + /* package */ WorkbookEvaluator(EvaluationWorkbook workbook, IEvaluationListener evaluationListener) { _workbook = workbook; - _cache = new EvaluationCache(); - _evaluationCounter = new Counter(); + _evaluationListener = evaluationListener; + _cache = new EvaluationCache(evaluationListener); + _sheetIndexesBySheet = new IdentityHashMap(); } /** - * for debug use. Used in toString methods + * also for debug use. Used in toString methods */ - /* package */ String getSheetName(HSSFSheet sheet) { - return getSheetName(getSheetIndex(sheet)); - } - private String getSheetName(int sheetIndex) { + /* package */ String getSheetName(int sheetIndex) { return _workbook.getSheetName(sheetIndex); } - /** - * for debug/test use - */ - public int getEvaluationCount() { - return _evaluationCounter.value; - } private static boolean isDebugLogEnabled() { return false; @@ -121,56 +109,122 @@ public class WorkbookEvaluator { */ public void clearAllCachedResultValues() { _cache.clear(); + _sheetIndexesBySheet.clear(); } - public void clearCachedResultValue(HSSFSheet sheet, int rowIndex, int columnIndex) { + /** + * Sets the cached value for a plain (non-formula) cell. + * @param never null. Use {@link BlankEval#INSTANCE} when the cell is being + * cleared. Otherwise an instance of {@link NumberEval}, {@link StringEval}, {@link BoolEval} + * or {@link ErrorEval} to represent a plain cell value. + */ + public void setCachedPlainValue(HSSFSheet sheet, int rowIndex, int columnIndex, ValueEval value) { + if (value == null) { + throw new IllegalArgumentException("value must not be null"); + } + int sheetIndex = getSheetIndex(sheet); + _cache.setValue(new CellLocation(sheetIndex, rowIndex, columnIndex), true, CellLocation.EMPTY_ARRAY, value); + + } + /** + * Should be called to tell the cell value cache that the specified cell has just become a + * formula cell, or the formula text has changed + */ + public void notifySetFormula(HSSFSheet sheet, int rowIndex, int columnIndex) { int sheetIndex = getSheetIndex(sheet); - _cache.clearValue(sheetIndex, rowIndex, columnIndex); + _cache.setValue(new CellLocation(sheetIndex, rowIndex, columnIndex), false, CellLocation.EMPTY_ARRAY, null); } private int getSheetIndex(HSSFSheet sheet) { - // TODO cache sheet indexes too - return _workbook.getSheetIndex(sheet); + Integer result = (Integer) _sheetIndexesBySheet.get(sheet); + if (result == null) { + result = new Integer(_workbook.getSheetIndex(sheet)); + _sheetIndexesBySheet.put(sheet, result); + } + return result.intValue(); } public ValueEval evaluate(HSSFCell srcCell) { - return internalEvaluate(srcCell, new EvaluationTracker(_cache)); + int sheetIndex = getSheetIndex(srcCell.getSheet()); + CellLocation cellLoc = new CellLocation(sheetIndex, srcCell.getRowIndex(), srcCell.getCellNum()); + return internalEvaluate(srcCell, cellLoc, new EvaluationTracker(_cache)); } /** - * Dev. Note: Internal evaluate must be passed only a formula cell - * else a runtime exception will be thrown somewhere inside the method. - * (Hence this is a private method.) * @return never null, never {@link BlankEval} */ - /* package */ ValueEval internalEvaluate(HSSFCell srcCell, EvaluationTracker tracker) { - int srcRowNum = srcCell.getRowIndex(); - int srcColNum = srcCell.getCellNum(); + private ValueEval internalEvaluate(HSSFCell srcCell, CellLocation cellLoc, EvaluationTracker tracker) { + int sheetIndex = cellLoc.getSheetIndex(); + int rowIndex = cellLoc.getRowIndex(); + int columnIndex = cellLoc.getColumnIndex(); ValueEval result; - int sheetIndex = getSheetIndex(srcCell.getSheet()); - result = tracker.startEvaluate(sheetIndex, srcRowNum, srcColNum); + result = tracker.startEvaluate(cellLoc); + IEvaluationListener evalListener = _evaluationListener; if (result != null) { + if(evalListener != null) { + evalListener.onCacheHit(sheetIndex, rowIndex, columnIndex, result); + } return result; } - _evaluationCounter.value++; - _evaluationCounter.depth++; + boolean isPlainFormulaCell = false; try { - Ptg[] ptgs = _workbook.getFormulaTokens(srcCell); - result = evaluateCell(sheetIndex, srcRowNum, (short)srcColNum, ptgs, tracker); + result = getValueFromNonFormulaCell(srcCell); + if (result != null) { + isPlainFormulaCell = true; + if(evalListener != null) { + evalListener.onReadPlainValue(sheetIndex, rowIndex, columnIndex, result); + } + } else { + isPlainFormulaCell = false; + Ptg[] ptgs = _workbook.getFormulaTokens(srcCell); + if(evalListener == null) { + result = evaluateCell(sheetIndex, rowIndex, (short)columnIndex, ptgs, tracker); + } else { + evalListener.onStartEvaluate(sheetIndex, rowIndex, columnIndex, ptgs); + result = evaluateCell(sheetIndex, rowIndex, (short)columnIndex, ptgs, tracker); + evalListener.onEndEvaluate(sheetIndex, rowIndex, columnIndex, result); + } + } } finally { - tracker.endEvaluate(sheetIndex, srcRowNum, srcColNum, result); - _evaluationCounter.depth--; + tracker.endEvaluate(cellLoc, result, isPlainFormulaCell); } if (isDebugLogEnabled()) { String sheetName = getSheetName(sheetIndex); - CellReference cr = new CellReference(srcRowNum, srcColNum); + CellReference cr = new CellReference(rowIndex, columnIndex); logDebug("Evaluated " + sheetName + "!" + cr.formatAsString() + " to " + result.toString()); } return result; } + /** + * Gets the value from a non-formula cell. + * @param cell may be null + * @return {@link BlankEval} if cell is null or blank, null if cell + * is a formula cell. + */ + private static ValueEval getValueFromNonFormulaCell(HSSFCell cell) { + if (cell == null) { + return BlankEval.INSTANCE; + } + int cellType = cell.getCellType(); + switch (cellType) { + case HSSFCell.CELL_TYPE_FORMULA: + return null; + case HSSFCell.CELL_TYPE_NUMERIC: + return new NumberEval(cell.getNumericCellValue()); + case HSSFCell.CELL_TYPE_STRING: + return new StringEval(cell.getRichStringCellValue().getString()); + case HSSFCell.CELL_TYPE_BOOLEAN: + return BoolEval.valueOf(cell.getBooleanCellValue()); + case HSSFCell.CELL_TYPE_BLANK: + return BlankEval.INSTANCE; + case HSSFCell.CELL_TYPE_ERROR: + return ErrorEval.valueOf(cell.getErrorCellValue()); + } + throw new RuntimeException("Unexpected cell type (" + cellType + ")"); + } private ValueEval evaluateCell(int sheetIndex, int srcRowNum, short srcColNum, Ptg[] ptgs, EvaluationTracker tracker) { Stack stack = new Stack(); @@ -268,10 +322,6 @@ public class WorkbookEvaluator { return operation.evaluate(ops, srcRowNum, (short)srcColNum); } - private HSSFSheet getOtherSheet(int externSheetIndex) { - return _workbook.getSheetByExternSheetIndex(externSheetIndex); - } - /** * returns an appropriate Eval impl instance for the Ptg. The Ptg must be * one of: Area3DPtg, AreaPtg, ReferencePtg, Ref3DPtg, IntPtg, NumberPtg, @@ -311,23 +361,24 @@ public class WorkbookEvaluator { if (ptg instanceof ErrPtg) { return ErrorEval.valueOf(((ErrPtg) ptg).getErrorCode()); } - CellEvaluator ce = new CellEvaluator(this, tracker); - HSSFSheet sheet = _workbook.getSheet(sheetIndex); - if (ptg instanceof RefPtg) { - return new LazyRefEval(((RefPtg) ptg), sheet, ce); - } - if (ptg instanceof AreaPtg) { - return new LazyAreaEval(((AreaPtg) ptg), sheet, ce); - } if (ptg instanceof Ref3DPtg) { Ref3DPtg refPtg = (Ref3DPtg) ptg; - HSSFSheet xsheet = getOtherSheet(refPtg.getExternSheetIndex()); - return new LazyRefEval(refPtg, xsheet, ce); + int otherSheetIndex = _workbook.convertFromExternSheetIndex(refPtg.getExternSheetIndex()); + SheetRefEvaluator sre = new SheetRefEvaluator(this, tracker, _workbook, otherSheetIndex); + return new LazyRefEval(refPtg, sre); } if (ptg instanceof Area3DPtg) { - Area3DPtg a3dp = (Area3DPtg) ptg; - HSSFSheet xsheet = getOtherSheet(a3dp.getExternSheetIndex()); - return new LazyAreaEval(a3dp, xsheet, ce); + Area3DPtg aptg = (Area3DPtg) ptg; + int otherSheetIndex = _workbook.convertFromExternSheetIndex(aptg.getExternSheetIndex()); + SheetRefEvaluator sre = new SheetRefEvaluator(this, tracker, _workbook, otherSheetIndex); + return new LazyAreaEval(aptg, sre); + } + SheetRefEvaluator sre = new SheetRefEvaluator(this, tracker, _workbook, sheetIndex); + if (ptg instanceof RefPtg) { + return new LazyRefEval(((RefPtg) ptg), sre); + } + if (ptg instanceof AreaPtg) { + return new LazyAreaEval(((AreaPtg) ptg), sre); } if (ptg instanceof UnknownPtg) { @@ -345,4 +396,22 @@ public class WorkbookEvaluator { } return getEvalForPtg(ptgs[0], sheetIndex, tracker); } + + /** + * Used by the lazy ref evals whenever they need to get the value of a contained cell. + */ + /* package */ ValueEval evaluateReference(HSSFSheet sheet, int sheetIndex, int rowIndex, + int columnIndex, EvaluationTracker tracker) { + + HSSFRow row = sheet.getRow(rowIndex); + HSSFCell cell; + if (row == null) { + cell = null; + } else { + cell = row.getCell(columnIndex); + } + CellLocation cellLoc = new CellLocation(sheetIndex, rowIndex, columnIndex); + tracker.acceptDependency(cellLoc); + return internalEvaluate(cell, cellLoc, tracker); + } } diff --git a/src/testcases/org/apache/poi/hssf/HSSFTests.java b/src/testcases/org/apache/poi/hssf/HSSFTests.java index 1edaf7e151..aa5bf46d31 100644 --- a/src/testcases/org/apache/poi/hssf/HSSFTests.java +++ b/src/testcases/org/apache/poi/hssf/HSSFTests.java @@ -28,6 +28,7 @@ import org.apache.poi.hssf.model.AllModelTests; import org.apache.poi.hssf.record.AllRecordTests; import org.apache.poi.hssf.usermodel.AllUserModelTests; import org.apache.poi.hssf.util.AllHSSFUtilTests; +import org.apache.poi.ss.formula.TestEvaluationCache; /** * Test Suite for all sub-packages of org.apache.poi.hssf
@@ -52,6 +53,7 @@ public final class HSSFTests { } suite.addTest(new TestSuite(TestEventRecordFactory.class)); suite.addTest(new TestSuite(TestModelFactory.class)); + suite.addTest(new TestSuite(TestEvaluationCache.class)); return suite; } } diff --git a/src/testcases/org/apache/poi/hssf/record/formula/eval/TestCircularReferences.java b/src/testcases/org/apache/poi/hssf/record/formula/eval/TestCircularReferences.java index 3fb2ed8d86..5de348bdaf 100755 --- a/src/testcases/org/apache/poi/hssf/record/formula/eval/TestCircularReferences.java +++ b/src/testcases/org/apache/poi/hssf/record/formula/eval/TestCircularReferences.java @@ -71,8 +71,9 @@ public final class TestCircularReferences extends TestCase { // This formula should evaluate to the contents of B2, testCell.setCellFormula("INDEX(A1:B4,2,2)"); // However the range A1:B4 also includes the current cell A4. If the other parameters - // were 4 and 1, this would represent a circular reference. Since POI 'fully' evaluates - // arguments before invoking operators, POI must handle such potential cycles gracefully. + // were 4 and 1, this would represent a circular reference. Prior to v3.2 POI would + // 'fully' evaluate ref arguments before invoking operators, which raised the possibility of + // cycles / StackOverflowErrors. CellValue cellValue = evaluateWithCycles(wb, testCell); diff --git a/src/testcases/org/apache/poi/hssf/usermodel/TestFormulaEvaluatorBugs.java b/src/testcases/org/apache/poi/hssf/usermodel/TestFormulaEvaluatorBugs.java index c2f11cfcc9..baa72743d0 100644 --- a/src/testcases/org/apache/poi/hssf/usermodel/TestFormulaEvaluatorBugs.java +++ b/src/testcases/org/apache/poi/hssf/usermodel/TestFormulaEvaluatorBugs.java @@ -31,6 +31,10 @@ import org.apache.poi.hssf.record.aggregates.FormulaRecordAggregate; import org.apache.poi.hssf.record.formula.AreaPtg; import org.apache.poi.hssf.record.formula.FuncVarPtg; import org.apache.poi.hssf.record.formula.Ptg; +import org.apache.poi.hssf.record.formula.eval.ValueEval; +import org.apache.poi.ss.formula.EvaluationListener; +import org.apache.poi.ss.formula.WorkbookEvaluator; +import org.apache.poi.ss.formula.WorkbookEvaluatorTestHelper; /** * @@ -287,6 +291,29 @@ public final class TestFormulaEvaluatorBugs extends TestCase { } } + private static final class EvalListener extends EvaluationListener { + private int _countCacheHits; + private int _countCacheMisses; + + public EvalListener() { + _countCacheHits = 0; + _countCacheMisses = 0; + } + public int getCountCacheHits() { + return _countCacheHits; + } + public int getCountCacheMisses() { + return _countCacheMisses; + } + + public void onCacheHit(int sheetIndex, int srcRowNum, int srcColNum, ValueEval result) { + _countCacheHits++; + } + public void onStartEvaluate(int sheetIndex, int rowIndex, int columnIndex, Ptg[] ptgs) { + _countCacheMisses++; + } + } + /** * The HSSFFormula evaluator performance benefits greatly from caching of intermediate cell values */ @@ -312,16 +339,20 @@ public final class TestFormulaEvaluatorBugs extends TestCase { // Choose cell A9, so that the failing test case doesn't take too long to execute. HSSFCell cell = row.getCell(8); - HSSFFormulaEvaluator evaluator = new HSSFFormulaEvaluator(wb); + EvalListener evalListener = new EvalListener(); + WorkbookEvaluator evaluator = WorkbookEvaluatorTestHelper.createEvaluator(wb, evalListener); evaluator.evaluate(cell); - int evalCount = evaluator.getEvaluationCount(); - // With caching, the evaluationCount is 8 which is a big improvement - assertTrue(evalCount > 0); // make sure the counter is actually working + int evalCount = evalListener.getCountCacheMisses(); if (evalCount > 10) { // Without caching, evaluating cell 'A9' takes 21845 evaluations which consumes // much time (~3 sec on Core 2 Duo 2.2GHz) System.err.println("Cell A9 took " + evalCount + " intermediate evaluations"); throw new AssertionFailedError("Identifed bug 45376 - Formula evaluator should cache values"); } + // With caching, the evaluationCount is 8 which is a big improvement + // Note - these expected values may change if the WorkbookEvaluator is + // ever optimised to short circuit 'if' functions. + assertEquals(8, evalCount); + assertEquals(24, evalListener.getCountCacheHits()); } } \ No newline at end of file diff --git a/src/testcases/org/apache/poi/hssf/usermodel/TestHSSFFormulaEvaluator.java b/src/testcases/org/apache/poi/hssf/usermodel/TestHSSFFormulaEvaluator.java index 06213b762c..ce77bfd025 100644 --- a/src/testcases/org/apache/poi/hssf/usermodel/TestHSSFFormulaEvaluator.java +++ b/src/testcases/org/apache/poi/hssf/usermodel/TestHSSFFormulaEvaluator.java @@ -17,10 +17,10 @@ package org.apache.poi.hssf.usermodel; +import junit.framework.TestCase; + import org.apache.poi.hssf.HSSFTestDataSamples; import org.apache.poi.hssf.usermodel.HSSFFormulaEvaluator.CellValue; - -import junit.framework.TestCase; /** * * @author Josh Micich @@ -79,4 +79,17 @@ public final class TestHSSFFormulaEvaluator extends TestCase { } row.createCell(colIndex).setCellValue(value); } + + /** + * {@link HSSFFormulaEvaluator#evaluate(HSSFCell)} should behave the same whether the cell + * is null or blank. + */ + public void testEvaluateBlank() { + HSSFWorkbook wb = new HSSFWorkbook(); + HSSFFormulaEvaluator fe = new HSSFFormulaEvaluator(wb); + assertNull(fe.evaluate(null)); + HSSFSheet sheet = wb.createSheet("Sheet1"); + HSSFCell cell = sheet.createRow(0).createCell(0); + assertNull(fe.evaluate(cell)); + } } diff --git a/src/testcases/org/apache/poi/ss/formula/EvaluationListener.java b/src/testcases/org/apache/poi/ss/formula/EvaluationListener.java new file mode 100644 index 0000000000..e6ae025a85 --- /dev/null +++ b/src/testcases/org/apache/poi/ss/formula/EvaluationListener.java @@ -0,0 +1,53 @@ +/* ==================================================================== + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +==================================================================== */ + +package org.apache.poi.ss.formula; + +import org.apache.poi.hssf.record.formula.Ptg; +import org.apache.poi.hssf.record.formula.eval.ValueEval; + +/** + * Tests should extend this class if they need to track the internal working of the {@link WorkbookEvaluator}.
+ * + * Default method implementations all do nothing + * + * @author Josh Micich + */ +public abstract class EvaluationListener implements IEvaluationListener { + public void onCacheHit(int sheetIndex, int rowIndex, int srcColNum, ValueEval result) { + // do nothing + } + public void onReadPlainValue(int sheetIndex, int srcRowNum, int srcColNum, ValueEval value) { + // do nothing + } + public void onStartEvaluate(int sheetIndex, int rowIndex, int columnIndex, Ptg[] ptgs) { + // do nothing + } + public void onEndEvaluate(int sheetIndex, int rowIndex, int columnIndex, ValueEval result) { + // do nothing + } + public void onClearWholeCache() { + // do nothing + } + public void onClearCachedValue(int sheetIndex, int rowIndex, int columnIndex, ValueEval value) { + // do nothing + } + public void onClearDependentCachedValue(int sheetIndex, int rowIndex, int columnIndex, + ValueEval value,int depth) { + // do nothing + } +} diff --git a/src/testcases/org/apache/poi/ss/formula/TestEvaluationCache.java b/src/testcases/org/apache/poi/ss/formula/TestEvaluationCache.java new file mode 100644 index 0000000000..bba2ec0d05 --- /dev/null +++ b/src/testcases/org/apache/poi/ss/formula/TestEvaluationCache.java @@ -0,0 +1,492 @@ +/* ==================================================================== + Licensed to the Apache Software Foundation (ASF) under one or more + contributor license agreements. See the NOTICE file distributed with + this work for additional information regarding copyright ownership. + The ASF licenses this file to You under the Apache License, Version 2.0 + (the "License"); you may not use this file except in compliance with + the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +==================================================================== */ + +package org.apache.poi.ss.formula; + +import java.io.PrintStream; +import java.util.ArrayList; +import java.util.List; + +import junit.framework.AssertionFailedError; +import junit.framework.TestCase; + +import org.apache.poi.hssf.model.HSSFFormulaParser; +import org.apache.poi.hssf.record.formula.Ptg; +import org.apache.poi.hssf.record.formula.eval.BlankEval; +import org.apache.poi.hssf.record.formula.eval.BoolEval; +import org.apache.poi.hssf.record.formula.eval.ErrorEval; +import org.apache.poi.hssf.record.formula.eval.NumberEval; +import org.apache.poi.hssf.record.formula.eval.StringEval; +import org.apache.poi.hssf.record.formula.eval.ValueEval; +import org.apache.poi.hssf.usermodel.HSSFCell; +import org.apache.poi.hssf.usermodel.HSSFRow; +import org.apache.poi.hssf.usermodel.HSSFSheet; +import org.apache.poi.hssf.usermodel.HSSFWorkbook; +import org.apache.poi.hssf.util.CellReference; + +/** + * Tests {@link EvaluationCache}. Makes sure that where possible (previously calculated) cached + * values are used. Also checks that changing cell values causes the correct (minimal) set of + * dependent cached values to be cleared. + * + * @author Josh Micich + */ +public class TestEvaluationCache extends TestCase { + private static final class EvalListener extends EvaluationListener { + + private final List _logList; + private final HSSFWorkbook _book; + + public EvalListener(HSSFWorkbook wb) { + _book = wb; + _logList = new ArrayList(); + } + public void onCacheHit(int sheetIndex, int rowIndex, int columnIndex, ValueEval result) { + log("hit", rowIndex, columnIndex, result); + } + public void onReadPlainValue(int sheetIndex, int rowIndex, int columnIndex, ValueEval value) { + log("value", rowIndex, columnIndex, value); + } + public void onStartEvaluate(int sheetIndex, int rowIndex, int columnIndex, Ptg[] ptgs) { + log("start", rowIndex, columnIndex, ptgs); + } + public void onEndEvaluate(int sheetIndex, int rowIndex, int columnIndex, ValueEval result) { + log("end", rowIndex, columnIndex, result); + } + public void onClearCachedValue(int sheetIndex, int rowIndex, int columnIndex, ValueEval value) { + log("clear", rowIndex, columnIndex, value); + } + public void onClearDependentCachedValue(int sheetIndex, int rowIndex, int columnIndex, + ValueEval value,int depth) { + log("clear" + depth, rowIndex, columnIndex, value); + } + private void log(String tag, int rowIndex, int columnIndex, Object value) { + StringBuffer sb = new StringBuffer(64); + sb.append(tag).append(' '); + sb.append(new CellReference(rowIndex, columnIndex).formatAsString()); + if (value != null) { + sb.append(' ').append(formatValue(value)); + } + _logList.add(sb.toString()); + } + private String formatValue(Object value) { + if (value instanceof Ptg[]) { + Ptg[] ptgs = (Ptg[]) value; + return HSSFFormulaParser.toFormulaString(_book, ptgs); + } + if (value instanceof NumberEval) { + NumberEval ne = (NumberEval) value; + return ne.getStringValue(); + } + if (value instanceof StringEval) { + StringEval se = (StringEval) value; + return "'" + se.getStringValue() + "'"; + } + if (value instanceof BoolEval) { + BoolEval be = (BoolEval) value; + return be.getStringValue(); + } + if (value == BlankEval.INSTANCE) { + return "#BLANK#"; + } + if (value instanceof ErrorEval) { + ErrorEval ee = (ErrorEval) value; + return ErrorEval.getText(ee.getErrorCode()); + } + throw new IllegalArgumentException("Unexpected value class (" + + value.getClass().getName() + ")"); + } + public String[] getAndClearLog() { + String[] result = new String[_logList.size()]; + _logList.toArray(result); + _logList.clear(); + return result; + } + } + /** + * Wrapper class to manage repetitive tasks from this test, + * + * Note - this class does a little bit more than just plain set-up of data. The method + * {@link WorkbookEvaluator#clearCachedResultValue(HSSFSheet, int, int)} is called whenever a + * cell value is changed. + * + */ + private static final class MySheet { + + private final HSSFSheet _sheet; + private final WorkbookEvaluator _evaluator; + private final HSSFWorkbook _wb; + private final EvalListener _evalListener; + + public MySheet() { + _wb = new HSSFWorkbook(); + _evalListener = new EvalListener(_wb); + _evaluator = WorkbookEvaluatorTestHelper.createEvaluator(_wb, _evalListener); + _sheet = _wb.createSheet("Sheet1"); + } + + public void setCellValue(String cellRefText, double value) { + HSSFCell cell = getOrCreateCell(cellRefText); + // be sure to blank cell, in case it is currently a formula + cell.setCellType(HSSFCell.CELL_TYPE_BLANK); + // otherwise this line will only set the formula cached result; + cell.setCellValue(value); + _evaluator.setCachedPlainValue(_sheet, cell.getRowIndex(), cell.getCellNum(), new NumberEval(value)); + } + + public void setCellFormula(String cellRefText, String formulaText) { + HSSFCell cell = getOrCreateCell(cellRefText); + cell.setCellFormula(formulaText); + _evaluator.notifySetFormula(_sheet, cell.getRowIndex(), cell.getCellNum()); + } + + private HSSFCell getOrCreateCell(String cellRefText) { + CellReference cr = new CellReference(cellRefText); + int rowIndex = cr.getRow(); + HSSFRow row = _sheet.getRow(rowIndex); + if (row == null) { + row = _sheet.createRow(rowIndex); + } + int cellIndex = cr.getCol(); + HSSFCell cell = row.getCell(cellIndex); + if (cell == null) { + cell = row.createCell(cellIndex); + } + return cell; + } + + public ValueEval evaluateCell(String cellRefText) { + return _evaluator.evaluate(getOrCreateCell(cellRefText)); + } + + public String[] getAndClearLog() { + return _evalListener.getAndClearLog(); + } + + public void clearAllCachedResultValues() { + _evaluator.clearAllCachedResultValues(); + } + } + + private static MySheet createMediumComplex() { + MySheet ms = new MySheet(); + + // plain data in D1:F3 + ms.setCellValue("D1", 12); + ms.setCellValue("E1", 13); + ms.setCellValue("D2", 14); + ms.setCellValue("E2", 15); + ms.setCellValue("D3", 16); + ms.setCellValue("E3", 17); + + + ms.setCellFormula("C1", "SUM(D1:E2)"); + ms.setCellFormula("C2", "SUM(D2:E3)"); + ms.setCellFormula("C3", "SUM(D3:E4)"); + + ms.setCellFormula("B1", "C2-C1"); + ms.setCellFormula("B2", "B3*C1-C2"); + ms.setCellValue("B3", 2); + + ms.setCellFormula("A1", "MAX(B1:B2)"); + ms.setCellFormula("A2", "MIN(B3,D2:F2)"); + ms.setCellFormula("A3", "B3*C3"); + + // clear all the logging from the above initialisation + ms.getAndClearLog(); + ms.clearAllCachedResultValues(); + return ms; + } + + public void testMediumComplex() { + + MySheet ms = createMediumComplex(); + // completely fresh evaluation + confirmEvaluate(ms, "A1", 46); + confirmLog(ms, new String[] { + "start A1 MAX(B1:B2)", + "start B1 C2-C1", + "start C2 SUM(D2:E3)", + "value D2 14", "value E2 15", "value D3 16", "value E3 17", + "end C2 62", + "start C1 SUM(D1:E2)", + "value D1 12", "value E1 13", "hit D2 14", "hit E2 15", + "end C1 54", + "end B1 8", + "start B2 B3*C1-C2", + "value B3 2", + "hit C1 54", + "hit C2 62", + "end B2 46", + "end A1 46", + }); + + + // simple cache hit - immediate re-evaluation with no changes + confirmEvaluate(ms, "A1", 46); + confirmLog(ms, new String[] { "hit A1 46", }); + + // change a low level cell + ms.setCellValue("D1", 10); + confirmLog(ms, new String[] { + "clear1 C1 54", + "clear2 B1 8", + "clear3 A1 46", + "clear2 B2 46", + }); + confirmEvaluate(ms, "A1", 42); + confirmLog(ms, new String[] { + "start A1 MAX(B1:B2)", + "start B1 C2-C1", + "hit C2 62", + "start C1 SUM(D1:E2)", + "hit D1 10", "hit E1 13", "hit D2 14", "hit E2 15", + "end C1 52", + "end B1 10", + "start B2 B3*C1-C2", + "hit B3 2", + "hit C1 52", + "hit C2 62", + "end B2 42", + "end A1 42", + }); + + // Reset and try changing an intermediate value + ms = createMediumComplex(); + confirmEvaluate(ms, "A1", 46); + ms.getAndClearLog(); + + ms.setCellValue("B3", 3); // B3 is in the middle of the dependency tree + confirmLog(ms, new String[] { + "clear1 B2 46", + "clear2 A1 46", + }); + confirmEvaluate(ms, "A1", 100); + confirmLog(ms, new String[] { + "start A1 MAX(B1:B2)", + "hit B1 8", + "start B2 B3*C1-C2", + "hit B3 3", + "hit C1 54", + "hit C2 62", + "end B2 100", + "end A1 100", + }); + } + + public void testMediumComplexWithDependencyChange() { + + // Changing an intermediate formula + MySheet ms = createMediumComplex(); + confirmEvaluate(ms, "A1", 46); + ms.getAndClearLog(); + ms.setCellFormula("B2", "B3*C2-C3"); // used to be "B3*C1-C2" + confirmLog(ms, new String[] { + "clear1 A1 46", + }); + + confirmEvaluate(ms, "A1", 91); + confirmLog(ms, new String[] { + "start A1 MAX(B1:B2)", + "hit B1 8", + "start B2 B3*C2-C3", + "hit B3 2", + "hit C2 62", + "start C3 SUM(D3:E4)", + "hit D3 16", "hit E3 17", "value D4 #BLANK#", "value E4 #BLANK#", + "end C3 33", + "end B2 91", + "end A1 91", + }); + + //---------------- + // Note - From now on the demonstrated POI behaviour is not optimal + //---------------- + + // Now change a value that should no longer affect B2 + ms.setCellValue("D1", 11); + confirmLog(ms, new String[] { + "clear1 C1 54", + // note there is no "clear2 B2 91" here because B2 doesn't depend on C1 anymore + "clear2 B1 8", + "clear3 A1 91", + }); + + confirmEvaluate(ms, "B2", 91); + confirmLog(ms, new String[] { + "hit B2 91", // further confirmation that B2 was not cleared due to changing D1 above + }); + + // things should be back to normal now + ms.setCellValue("D1", 11); + confirmLog(ms, new String[] { }); + confirmEvaluate(ms, "B2", 91); + confirmLog(ms, new String[] { + "hit B2 91", + }); + } + + /** + * verifies that when updating a plain cell, depending (formula) cell cached values are cleared + * only when the palin cell's value actually changes + */ + public void testRedundantUpdate() { + MySheet ms = new MySheet(); + + ms.setCellValue("B1", 12); + ms.setCellValue("C1", 13); + ms.setCellFormula("A1", "B1+C1"); + + // evaluate twice to confirm caching looks OK + ms.evaluateCell("A1"); + ms.getAndClearLog(); + confirmEvaluate(ms, "A1", 25); + confirmLog(ms, new String[] { + "hit A1 25", + }); + + // Make redundant update, and check re-evaluation + ms.setCellValue("B1", 12); // value didn't change + confirmLog(ms, new String[] {}); + confirmEvaluate(ms, "A1", 25); + confirmLog(ms, new String[] { + "hit A1 25", + }); + + ms.setCellValue("B1", 11); // value changing + confirmLog(ms, new String[] { + "clear1 A1 25", // expect consuming formula cached result to get cleared + }); + confirmEvaluate(ms, "A1", 24); + confirmLog(ms, new String[] { + "start A1 B1+C1", + "hit B1 11", + "hit C1 13", + "end A1 24", + }); + } + + /** + * Changing any input to a formula may cause the formula to 'use' a different set of cells. + * Functions like INDEX and OFFSET make this effect obvious, with functions like MATCH + * and VLOOKUP the effect can be subtle. The presence of error values can also produce this + * effect in almost every function and operator. + */ + public void testSimpleWithDependencyChange() { + + MySheet ms = new MySheet(); + + ms.setCellFormula("A1", "INDEX(C1:E1,1,B1)"); + ms.setCellValue("B1", 1); + ms.setCellValue("C1", 17); + ms.setCellValue("D1", 18); + ms.setCellValue("E1", 19); + ms.clearAllCachedResultValues(); + ms.getAndClearLog(); + + confirmEvaluate(ms, "A1", 17); + confirmLog(ms, new String[] { + "start A1 INDEX(C1:E1,1,B1)", + "value B1 1", + "value C1 17", + "end A1 17", + }); + ms.setCellValue("B1", 2); + ms.getAndClearLog(); + + confirmEvaluate(ms, "A1", 18); + confirmLog(ms, new String[] { + "start A1 INDEX(C1:E1,1,B1)", + "hit B1 2", + "value D1 18", + "end A1 18", + }); + + // change C1. Note - last time A1 evaluated C1 was not used + ms.setCellValue("C1", 15); + ms.getAndClearLog(); + confirmEvaluate(ms, "A1", 18); + confirmLog(ms, new String[] { + "hit A1 18", + }); + + // but A1 still uses D1, so if it changes... + ms.setCellValue("D1", 25); + ms.getAndClearLog(); + confirmEvaluate(ms, "A1", 25); + confirmLog(ms, new String[] { + "start A1 INDEX(C1:E1,1,B1)", + "hit B1 2", + "hit D1 25", + "end A1 25", + }); + + } + + private static void confirmEvaluate(MySheet ms, String cellRefText, double expectedValue) { + ValueEval v = ms.evaluateCell(cellRefText); + assertEquals(NumberEval.class, v.getClass()); + assertEquals(expectedValue, ((NumberEval)v).getNumberValue(), 0.0); + } + + private static void confirmLog(MySheet ms, String[] expectedLog) { + String[] actualLog = ms.getAndClearLog(); + int endIx = actualLog.length; + PrintStream ps = System.err; + if (endIx != expectedLog.length) { + ps.println("Log lengths mismatch"); + dumpCompare(ps, expectedLog, actualLog); + throw new AssertionFailedError("Log lengths mismatch"); + } + for (int i=0; i< endIx; i++) { + if (!actualLog[i].equals(expectedLog[i])) { + String msg = "Log entry mismatch at index " + i; + ps.println(msg); + dumpCompare(ps, expectedLog, actualLog); + throw new AssertionFailedError(msg); + } + } + + } + + private static void dumpCompare(PrintStream ps, String[] expectedLog, String[] actualLog) { + int max = Math.max(actualLog.length, expectedLog.length); + ps.println("Index\tExpected\tActual"); + for(int i=0; i