Merged revisions 698047 via svnmerge from

https://svn.apache.org/repos/asf/poi/trunk

........
  r698047 | josh | 2008-09-22 17:40:22 -0700 (Mon, 22 Sep 2008) | 1 line
  
  Optimised the FormulaEvaluator to take cell dependencies into account
........


git-svn-id: https://svn.apache.org/repos/asf/poi/branches/ooxml@698370 13f79535-47bb-0310-9956-ffa450edef68

15 files changed, 697 insertions, 275 deletions

diff --git a/src/java/org/apache/poi/hssf/usermodel/HSSFEvaluationWorkbook.java b/src/java/org/apache/poi/hssf/usermodel/HSSFEvaluationWorkbook.java
index 39dbdcd069..d82a9d1144 100644
--- a/src/java/org/apache/poi/hssf/usermodel/HSSFEvaluationWorkbook.java
+++ b/src/java/org/apache/poi/hssf/usermodel/HSSFEvaluationWorkbook.java
@@ -73,11 +73,9 @@ public final class HSSFEvaluationWorkbook implements FormulaRenderingWorkbook, E
 	public Sheet getSheet(int sheetIndex) {

 		return _uBook.getSheetAt(sheetIndex);

 	}

-

-	public Sheet 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 9003c1b3bc..d7a3207383 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;

@@ -53,14 +54,7 @@ public class HSSFFormulaEvaluator /* almost implements FormulaEvaluator */ {
 		}

 	}

 	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));

 	}

 

 	/**

@@ -84,12 +78,23 @@ public class HSSFFormulaEvaluator /* almost implements FormulaEvaluator */ {
 		_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 <code>null</code>. 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(Sheet sheet, int rowIndex, int columnIndex) {

-		_bookEvaluator.clearCachedResultValue(sheet, rowIndex, columnIndex);

+	public void setCachedPlainValue(Sheet 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);

 	}

 

 	/**

@@ -98,7 +103,9 @@ public class HSSFFormulaEvaluator /* almost implements FormulaEvaluator */ {
 	 * 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 <code>null</code> signifying that the cell is not present (or blank)

+	 * @return <code>null</code> if the supplied cell is <code>null</code> or blank

 	 */

 	public CellValue evaluate(Cell cell) {

 		if (cell == null) {

@@ -116,6 +123,8 @@ public class HSSFFormulaEvaluator /* almost implements FormulaEvaluator */ {
 				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.<br/>
+ */
+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.<br/>

+ * Stores details about the current evaluation of a cell.<br/>

  */

 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 <code>null</code>, (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 73f8d4d900..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.ss.usermodel.Cell;

-import org.apache.poi.ss.usermodel.Sheet;

-

-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(Cell cell) {

-

-        if (cell == null) {

-            return BlankEval.INSTANCE;

-        }

-        switch (cell.getCellType()) {

-            case Cell.CELL_TYPE_NUMERIC:

-                return new NumberEval(cell.getNumericCellValue());

-            case Cell.CELL_TYPE_STRING:

-                return new StringEval(cell.getRichStringCellValue().getString());

-            case Cell.CELL_TYPE_FORMULA:

-                return _bookEvaluator.internalEvaluate(cell, _tracker);

-            case Cell.CELL_TYPE_BOOLEAN:

-                return BoolEval.valueOf(cell.getBooleanCellValue());

-            case Cell.CELL_TYPE_BLANK:

-                return BlankEval.INSTANCE;

-            case Cell.CELL_TYPE_ERROR:

-                return ErrorEval.valueOf(cell.getErrorCellValue());

-        }

-        throw new RuntimeException("Unexpected cell type (" + cell.getCellType() + ")");

-    }

-

-	public String getSheetName(Sheet 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.<br/>
+ */
+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. <code>null</code> 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 <code>null</code>
+	 * @return only ever <code>null</code> 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 <code>null</code>, (possibly zero length) array of all cells actually 
+	 * directly used when evaluating the formula
+	 * @param isPlainValue pass <code>true</code> if cellLoc refers to a plain value (non-formula) 
+	 * cell, <code>false</code> for a formula cell.
+	 * @param value the value of a non-formula cell or the result of evaluating the cell formula
+	 * Pass <code>null</code> 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 <code>true</code> if the specified cell has not been visited yet in the current 
 	 * evaluation. <code>false</code> 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 
+	 * <tt>usedCell<tt> 
+	 * @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 adf69d0d51..02917d82a4 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 {
 

 	Sheet getSheet(int sheetIndex);

 

-	Sheet getSheetByExternSheetIndex(int externSheetIndex);

+	int convertFromExternSheetIndex(int externSheetIndex);

 	EvaluationName getName(NamePtg namePtg);

 	String resolveNameXText(NameXPtg ptg);

 	Ptg[] getFormulaTokens(Cell 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}.<br/>
+ * 
+ * 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 5816f0052b..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.ss.usermodel.Cell;
-import org.apache.poi.ss.usermodel.Row;
-import org.apache.poi.ss.usermodel.Sheet;
 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 Sheet _sheet;
-	private final CellEvaluator _evaluator;
+	private final SheetRefEvaluator _evaluator;
 
-	public LazyAreaEval(AreaI ptg, Sheet 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;
 		
-		Row row = _sheet.getRow(rowIx);
-		if (row == null) {
-			return BlankEval.INSTANCE;
-		}
-		Cell 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 2d80585fcb..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.ss.usermodel.Cell;

-import org.apache.poi.ss.usermodel.Row;

-import org.apache.poi.ss.usermodel.Sheet;

 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 Sheet _sheet;

-	private final CellEvaluator _evaluator;

+	private final SheetRefEvaluator _evaluator;

 

-

-	public LazyRefEval(RefPtg ptg, Sheet sheet, CellEvaluator evaluator) {

+	public LazyRefEval(RefPtg ptg, SheetRefEvaluator sre) {

 		super(ptg.getRow(), ptg.getColumn());

-		_sheet = sheet;

-		_evaluator = evaluator;

+		_evaluator = sre;

 	}

-	public LazyRefEval(Ref3DPtg ptg, Sheet 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();

-		

-		Row row = _sheet.getRow(rowIx);

-		if (row == null) {

-			return BlankEval.INSTANCE;

-		}

-		Cell 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..4f46e31a21
--- /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.ss.usermodel.Sheet;

+/**

+ * 

+ * 

+ * @author Josh Micich

+ */

+final class SheetRefEvaluator {

+

+	private final WorkbookEvaluator _bookEvaluator;

+	private final EvaluationTracker _tracker;

+	private final Sheet _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 e2eddbd5b1..b41e2c2c3f 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;
@@ -52,6 +54,7 @@ import org.apache.poi.hssf.record.formula.eval.StringEval;
 import org.apache.poi.hssf.record.formula.eval.ValueEval;
 import org.apache.poi.hssf.util.CellReference;
 import org.apache.poi.ss.usermodel.Cell;
+import org.apache.poi.ss.usermodel.Row;
 import org.apache.poi.ss.usermodel.Sheet;
 
 /**
@@ -67,43 +70,28 @@ import org.apache.poi.ss.usermodel.Sheet;
  */
 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(Sheet 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(Sheet sheet, int rowIndex, int columnIndex) {
+	/**
+	 * Sets the cached value for a plain (non-formula) cell.
+	 * @param never <code>null</code>. 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(Sheet 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(Sheet 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(Sheet 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(Cell 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 <code>null</code>, never {@link BlankEval}
 	 */
-	/* package */ ValueEval internalEvaluate(Cell srcCell, EvaluationTracker tracker) {
-		int srcRowNum = srcCell.getRowIndex();
-		int srcColNum = srcCell.getCellNum();
+	private ValueEval internalEvaluate(Cell 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 <code>null</code>
+	 * @return {@link BlankEval} if cell is <code>null</code> or blank, <code>null</code> if cell 
+	 * is a formula cell.
+	 */
+	private static ValueEval getValueFromNonFormulaCell(Cell cell) {
+		if (cell == null) {
+			return BlankEval.INSTANCE;
+		}
+		int cellType = cell.getCellType();
+		switch (cellType) {
+			case Cell.CELL_TYPE_FORMULA:
+				return null;
+			case Cell.CELL_TYPE_NUMERIC:
+				return new NumberEval(cell.getNumericCellValue());
+			case Cell.CELL_TYPE_STRING:
+				return new StringEval(cell.getRichStringCellValue().getString());
+			case Cell.CELL_TYPE_BOOLEAN:
+				return BoolEval.valueOf(cell.getBooleanCellValue());
+			case Cell.CELL_TYPE_BLANK:
+				return BlankEval.INSTANCE;
+			case Cell.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 Sheet 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);
-		Sheet 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;
-			Sheet 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;
-			Sheet 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(Sheet sheet, int sheetIndex, int rowIndex,
+			int columnIndex, EvaluationTracker tracker) {
+		
+		Row row = sheet.getRow(rowIndex);
+		Cell 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/java/org/apache/poi/ss/usermodel/FormulaEvaluator.java b/src/java/org/apache/poi/ss/usermodel/FormulaEvaluator.java
index 1234c9564f..629d4f5a12 100644
--- a/src/java/org/apache/poi/ss/usermodel/FormulaEvaluator.java
+++ b/src/java/org/apache/poi/ss/usermodel/FormulaEvaluator.java
@@ -17,6 +17,14 @@
 
 package org.apache.poi.ss.usermodel;
 
+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.HSSFSheet;
+
 
 /**
  * Evaluates formula cells.<p/>
@@ -36,7 +44,21 @@ public interface FormulaEvaluator {
      * of the evaluate~ methods of this class
      */
     void clearAllCachedResultValues();
-    void clearCachedResultValue(Sheet sheet, int rowIndex, int columnIndex);
+	/**
+	 * 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 <code>null</code>. 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.
+	 */
+    void setCachedPlainValue(Sheet sheet, int rowIndex, int columnIndex, ValueEval 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 
+	 */
+	void notifySetFormula(HSSFSheet sheet, int rowIndex, int columnIndex);
     /**
      * If cell contains a formula, the formula is evaluated and returned,
      * else the CellValue simply copies the appropriate cell value from