Preevaluate nested expressions to avoid stack overflow
Bug: 33262515
Before we evaluate an expression, find all referenced expressions,
and evaluate them in an order likely to minimize recursion.
This compensates for the fact that our normal evaluation mechanism
relies on a simple recursive descent parser, which tends to need
a fair amount of stack space for each expression, and the fact that
we process previously unevaluated referenced expressions recursively,
effectively stacking many such parse stacks on top of each other.
This largely avoids the latter phenomenon, getting us back to roughly
the same situation we had before we added history.
This could be improved, at some cost, but doing a real topological
sort, or, with more difficulty, by replacing the parser with something
less recursive.
Includes some minor drive-by comment and formatting fixes.
Change-Id: Ie0a900c82d8bfbb48896fc2b938ef28e588163bb
diff --git a/src/com/android/calculator2/CalculatorExpr.java b/src/com/android/calculator2/CalculatorExpr.java
index c6eb9af..06aa264 100644
--- a/src/com/android/calculator2/CalculatorExpr.java
+++ b/src/com/android/calculator2/CalculatorExpr.java
@@ -27,6 +27,8 @@
import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
/**
* A mathematical expression represented as a sequence of "tokens".
@@ -55,7 +57,7 @@
*/
CalculatorExpr getExpr(long index);
/*
- * Retrive the degree mode associated with the expression at index i.
+ * Retrieve the degree mode associated with the expression at index i.
*/
boolean getDegreeMode(long index);
/*
@@ -575,7 +577,7 @@
*/
public Object clone() {
CalculatorExpr result = new CalculatorExpr();
- for (Token t: mExpr) {
+ for (Token t : mExpr) {
if (t instanceof Constant) {
result.mExpr.add((Token)(((Constant)t).clone()));
} else {
@@ -703,11 +705,9 @@
final long index = ((PreEval)t).mIndex;
UnifiedReal res = ec.mExprResolver.getResult(index);
if (res == null) {
- CalculatorExpr nestedExpr = ec.mExprResolver.getExpr(index);
- EvalContext newEc = new EvalContext(ec.mExprResolver.getDegreeMode(index),
- nestedExpr.trailingBinaryOpsStart(), ec.mExprResolver);
- EvalRet new_res = nestedExpr.evalExpr(0, newEc);
- res = ec.mExprResolver.putResultIfAbsent(index, new_res.val);
+ // We try to minimize this recursive evaluation case, but currently don't
+ // completely avoid it.
+ res = nestedEval(index, ec.mExprResolver);
}
return new EvalRet(i+1, res);
}
@@ -982,7 +982,7 @@
* Does the expression contain trig operations?
*/
public boolean hasTrigFuncs() {
- for (Token t: mExpr) {
+ for (Token t : mExpr) {
if (t instanceof Operator) {
Operator o = (Operator)t;
if (KeyMaps.isTrigFunc(o.id)) {
@@ -994,6 +994,58 @@
}
/**
+ * Add the indices of unevaluated PreEval expressions embedded in the current expression to
+ * argument. This includes only directly referenced expressions e, not those indirectly
+ * referenced by e. If the index was already present, it is not added. If the argument
+ * contained no duplicates, the result will not either. New indices are added to the end of
+ * the list.
+ */
+ private void addReferencedExprs(ArrayList<Long> list, ExprResolver er) {
+ for (Token t : mExpr) {
+ if (t instanceof PreEval) {
+ Long index = ((PreEval) t).mIndex;
+ if (er.getResult(index) == null && !list.contains(index)) {
+ list.add(index);
+ }
+ }
+ }
+ }
+
+ /**
+ * Return a list of unevaluated expressions transitively referenced by the current one.
+ * All expressions in the resulting list will have had er.getExpr() called on them.
+ * The resulting list is ordered such that evaluating expressions in list order
+ * should trigger few recursive evaluations.
+ */
+ public ArrayList<Long> getTransitivelyReferencedExprs(ExprResolver er) {
+ // We could avoid triggering any recursive evaluations by actually building the
+ // dependency graph and topologically sorting it. Note that sorting by index works
+ // for positive and negative indices separately, but not their union. Currently we
+ // just settle for reverse breadth-first-search order, which handles the common case
+ // of simple dependency chains well.
+ ArrayList<Long> list = new ArrayList<Long>();
+ int scanned = 0; // We've added expressions referenced by [0, scanned) to the list
+ addReferencedExprs(list, er);
+ while (scanned != list.size()) {
+ er.getExpr(list.get(scanned++)).addReferencedExprs(list, er);
+ }
+ Collections.reverse(list);
+ return list;
+ }
+
+ /**
+ * Evaluate the expression at the given index to a UnifiedReal.
+ * Both saves and returns the result.
+ */
+ UnifiedReal nestedEval(long index, ExprResolver er) throws SyntaxException {
+ CalculatorExpr nestedExpr = er.getExpr(index);
+ EvalContext newEc = new EvalContext(er.getDegreeMode(index),
+ nestedExpr.trailingBinaryOpsStart(), er);
+ EvalRet new_res = nestedExpr.evalExpr(0, newEc);
+ return er.putResultIfAbsent(index, new_res.val);
+ }
+
+ /**
* Evaluate the expression excluding trailing binary operators.
* Errors result in exceptions, most of which are unchecked. Should not be called
* concurrently with modification of the expression. May take a very long time; avoid calling
@@ -1005,6 +1057,15 @@
// And unchecked exceptions thrown by UnifiedReal, CR,
// and BoundedRational.
{
+ // First evaluate all indirectly referenced expressions in increasing index order.
+ // This ensures that subsequent evaluation never encounters an embedded PreEval
+ // expression that has not been previously evaluated.
+ // We could do the embedded evaluations recursively, but that risks running out of
+ // stack space.
+ ArrayList<Long> referenced = getTransitivelyReferencedExprs(er);
+ for (long index : referenced) {
+ nestedEval(index, er);
+ }
try {
// We currently never include trailing binary operators, but include other trailing
// operators. Thus we usually, but not always, display results for prefixes of valid
@@ -1025,7 +1086,7 @@
// Produce a string representation of the expression itself
SpannableStringBuilder toSpannableStringBuilder(Context context) {
SpannableStringBuilder ssb = new SpannableStringBuilder();
- for (Token t: mExpr) {
+ for (Token t : mExpr) {
ssb.append(t.toCharSequence(context));
}
return ssb;
diff --git a/src/com/android/calculator2/CalculatorFormula.java b/src/com/android/calculator2/CalculatorFormula.java
index 210372c..c681760 100644
--- a/src/com/android/calculator2/CalculatorFormula.java
+++ b/src/com/android/calculator2/CalculatorFormula.java
@@ -317,7 +317,7 @@
final MenuInflater inflater = new MenuInflater(getContext());
createContextMenu(inflater, contextMenu);
mContextMenu = contextMenu;
- for(int i = 0; i < contextMenu.size(); i++) {
+ for (int i = 0; i < contextMenu.size(); i++) {
contextMenu.getItem(i).setOnMenuItemClickListener(CalculatorFormula.this);
}
}
diff --git a/src/com/android/calculator2/CalculatorResult.java b/src/com/android/calculator2/CalculatorResult.java
index c1750ef..a320942 100644
--- a/src/com/android/calculator2/CalculatorResult.java
+++ b/src/com/android/calculator2/CalculatorResult.java
@@ -1040,7 +1040,7 @@
final MenuInflater inflater = new MenuInflater(getContext());
createCopyMenu(inflater, contextMenu);
mContextMenu = contextMenu;
- for(int i = 0; i < contextMenu.size(); i ++) {
+ for (int i = 0; i < contextMenu.size(); i ++) {
contextMenu.getItem(i).setOnMenuItemClickListener(CalculatorResult.this);
}
}
diff --git a/src/com/android/calculator2/Evaluator.java b/src/com/android/calculator2/Evaluator.java
index ddfb0d6..4c2be92 100644
--- a/src/com/android/calculator2/Evaluator.java
+++ b/src/com/android/calculator2/Evaluator.java
@@ -721,7 +721,6 @@
// This should only be possible in the extremely rare case of encountering a
// domain error while reevaluating or in case of a precision overflow. We don't
// know of a way to get the latter with a plausible amount of user input.
- // FIXME: Doesn't currently work. Didn't work in earlier releases either.
mListener.onError(mIndex, R.string.error_nan);
} else {
if (result.newResultStringOffset < mExprInfo.mResultStringOffset) {