1 files changed, 63 insertions, 55 deletions

diff --git a/src/com/android/calculator2/Evaluator.java b/src/com/android/calculator2/Evaluator.java
index e1bcaf6..fca757d 100644
--- a/src/com/android/calculator2/Evaluator.java
+++ b/src/com/android/calculator2/Evaluator.java
@@ -24,6 +24,7 @@ import android.net.Uri;
 import android.os.AsyncTask;
 import android.os.Handler;
 import android.preference.PreferenceManager;
+import android.support.annotation.VisibleForTesting;
 import android.util.Log;
 
 import com.hp.creals.CR;
@@ -413,6 +414,38 @@ class Evaluator {
     }
 
     /**
+     * Check whether a new higher precision result flips previously computed trailing 9s
+     * to zeroes.  If so, flip them back.  Return the adjusted result.
+     * Assumes newPrecOffset >= oldPrecOffset > 0.
+     * Since our results are accurate to < 1 ulp, this can only happen if the true result
+     * is less than the new result with trailing zeroes, and thus appending 9s to the
+     * old result must also be correct.  Such flips are impossible if the newly computed
+     * digits consist of anything other than zeroes.
+     * It is unclear that there are real cases in which this is necessary,
+     * but we have failed to prove there aren't such cases.
+     */
+    @VisibleForTesting
+    static String unflipZeroes(String oldDigs, int oldPrecOffset, String newDigs,
+            int newPrecOffset) {
+        final int oldLen = oldDigs.length();
+        if (oldDigs.charAt(oldLen - 1) != '9') {
+            return newDigs;
+        }
+        final int newLen = newDigs.length();
+        final int precDiff = newPrecOffset - oldPrecOffset;
+        final int oldLastInNew = newLen - 1 - precDiff;
+        if (newDigs.charAt(oldLastInNew) != '0') {
+            return newDigs;
+        }
+        // Earlier digits could not have changed without a 0 to 9 or 9 to 0 flip at end.
+        // The former is OK.
+        if (!newDigs.substring(newLen - precDiff).equals(repeat('0', precDiff))) {
+            throw new AssertionError("New approximation invalidates old one!");
+        }
+        return oldDigs + repeat('9', precDiff);
+    }
+
+    /**
      * Result of asynchronous reevaluation.
      */
     private static class ReevalResult {
@@ -445,6 +478,7 @@ class Evaluator {
                 return null;
             }
         }
+
         @Override
         protected void onPostExecute(ReevalResult result) {
             if (result == null) {
@@ -456,23 +490,8 @@ class Evaluator {
                 if (result.newResultStringOffset < mResultStringOffset) {
                     throw new AssertionError("Unexpected onPostExecute timing");
                 }
-                // FIXME: We are assuming that the most significant digit never moves to the left,
-                // i.e. that 0.99999 doesn't ever change to 1.00000.  Informally that makes sense,
-                // in that we can only produce the former result after a computation showing that
-                // the true answer is < 1 (otherwise we would have violated our 1 ulp error
-                // bound), and higher precision evaluations should preserve that bound.  But I
-                // don't know how to prove that.  Indeed, it seems like this could be violated
-                // if one of the CR operations, before rounding, produced an error that was
-                // almost exactly at it's error bound of 1/2ulp.  (Since we calculate ahead
-                // so far, we really mean "almost exactly", which makes it very difficult to
-                // generate a test case.)
-                // Instead, we should just check whether (a) all added digits are zeroes, and (b)
-                // any trailing 9's have been replaced.  In that case, we just use the original
-                // result with 9's appended.  This must be correct, since our 1 ulp error bound
-                // implies that the correct answer is between the two.  This has the unfortunate
-                // consequence that we are introducing code that is extremely unlikely to ever be
-                // exercised, and thus very difficult to test.
-                mResultString = result.newResultString;
+                mResultString = unflipZeroes(mResultString, mResultStringOffset,
+                        result.newResultString, result.newResultStringOffset);
                 mResultStringOffset = result.newResultStringOffset;
                 mCalculator.onReevaluate();
             }
@@ -521,8 +540,12 @@ class Evaluator {
         return result;
     }
 
+    // TODO: We may want to consistently specify the position of the current result
+    // window using the left-most visible digit index instead of the offset for the rightmost one.
+    // It seems likely that would simplify the logic.
+
     /**
-     * Retrieve the preferred precision for the currently displayed result.
+     * Retrieve the preferred precision "offset" for the currently displayed result.
      * May be called from non-UI thread.
      * @param cache Current approximation as string.
      * @param msd Position of most significant digit in result.  Index in cache.
@@ -676,13 +699,16 @@ class Evaluator {
      * Return most significant digit index in the currently computed result.
      * Returns an index in the result character array.  Return INVALID_MSD if the current result
      * is too close to zero to determine the result.
+     * Result is almost consistent through reevaluations: It may increase by one, once.
      */
     private int getMsdIndex() {
-        // FIXME: We currently never adjust msd once computed, even if the result changes
-        // from 0.100000...  to 0.0999999...  (We know it can't change in the other direction.)
-        // It would be cheap to increment it if the current "most significant digit" is zero.
-        // And it would make it easier to reason about the code.  We should do that.
-        if (mMsdIndex != INVALID_MSD) return mMsdIndex;
+        if (mMsdIndex != INVALID_MSD) {
+            // 0.100000... can change to 0.0999999...  We may have to correct once by one digit.
+            if (mResultString.charAt(mMsdIndex) == '0') {
+                mMsdIndex++;
+            }
+            return mMsdIndex;
+        }
         if (mRatVal != null && mRatVal.signum() == 0) {
             return INVALID_MSD;  // None exists
         }
@@ -690,39 +716,18 @@ class Evaluator {
         if (mResultString != null) {
             result = getMsdIndexOf(mResultString);
         }
-        // FIXME: I think the following conditional is no longer needed.  The initial
-        // background evaluation already ensures that either the msd is know, or we've
-        // evaluated to MAX_MSD_PREC_OFFSET.
-        if (result == INVALID_MSD && mEvaluator == null
-            && mCurrentReevaluator == null && mResultStringOffset < MAX_MSD_PREC_OFFSET) {
-            // We assert that mResultString is not null, since there is no
-            // evaluator running.
-            ensureCachePrec(MAX_MSD_PREC_OFFSET);
-            // Could reevaluate more incrementally, but we suspect that if
-            // we have to reevaluate at all, the result is probably zero.
-        }
         return result;
     }
 
     /**
-     * Return a string with n placeholder characters.
+     * Return a string with n copies of c.
      */
-    private String getPadding(int n) {
-        StringBuilder padding = new StringBuilder();
+    private static String repeat(char c, int n) {
+        StringBuilder result = new StringBuilder();
         for (int i = 0; i < n; ++i) {
-            padding.append(' ');   // To be replaced during final translation.
+            result.append(c);
         }
-        return padding.toString();
-    }
-
-    /**
-     * Return the number of zero characters at the beginning of s.
-     */
-    private int leadingZeroes(String s) {
-        int result = 0;
-        final int len = s.length();
-        for (result = 0; result < len && s.charAt(result) == '0'; ++result) {}
-        return result;
+        return result.toString();
     }
 
     // Refuse to scroll past the point at which this many digits from the whole number
@@ -746,7 +751,7 @@ class Evaluator {
      *
      * @param precOffset Zeroth element indicates desired and actual precision
      * @param maxPrecOffset Maximum adjusted precOffset[0]
-     * @param maxDigs Maximum length of result 
+     * @param maxDigs Maximum length of result
      * @param truncated Zeroth element is set if leading nonzero digits were dropped
      * @param negative Zeroth element is set of the result is negative.
      */
@@ -758,7 +763,7 @@ class Evaluator {
             ensureCachePrec(currentPrecOffset + EXTRA_DIGITS);
             // Nothing else to do now; seems to happen on rare occasion with weird user input
             // timing; Will repair itself in a jiffy.
-            return getPadding(1);
+            return " ";
         } else {
             ensureCachePrec(currentPrecOffset + EXTRA_DIGITS + mResultString.length()
                     / EXTRA_DIVISOR);
@@ -792,7 +797,8 @@ class Evaluator {
         truncated[0] = (startIndex > getMsdIndex());
         String result = mResultString.substring(startIndex, endIndex);
         if (deficit > 0) {
-            result += getPadding(deficit);
+            result += repeat(' ', deficit);
+            // Blank character is replaced during translation.
             // Since we always compute past the decimal point, this never fills in the spot
             // where the decimal point should go, and we can otherwise treat placeholders
             // as though they were digits.
@@ -851,7 +857,7 @@ class Evaluator {
      * Start required evaluation of result and display when ready.
      * Will eventually call back mCalculator to display result or error, or display
      * a timeout message.  Uses longer timeouts than optional evaluation.
-     */ 
+     */
     public void requireResult() {
         if (mResultString == null || mChangedValue) {
             // Restart evaluator in requested mode, i.e. with longer timeout.
@@ -909,7 +915,6 @@ class Evaluator {
         mChangedValue = true;
         try {
             CalculatorExpr.initExprInput();
-            // FIXME: Do we still need to restore DegreeMode here?
             mDegreeMode = in.readBoolean();
             mExpr = new CalculatorExpr(in);
             mSavedName = in.readUTF();
@@ -1087,12 +1092,15 @@ class Evaluator {
         if (KeyMaps.keyForChar(s.charAt(i)) == R.id.op_sub) {
             ++i;
         }
-        if (i == len || i > offset + MAX_EXP_CHARS || !Character.isDigit(s.charAt(i))) {
+        if (i == len || !Character.isDigit(s.charAt(i))) {
             return offset;
         }
         ++i;
         while (i < len && Character.isDigit(s.charAt(i))) {
             ++i;
+            if (i > offset + MAX_EXP_CHARS) {
+                return offset;
+            }
         }
         return i;
     }