am bd905403: am 3d4a67d1: Address FIXME comments from previous cleanup CL

* commit 'bd905403f4b4d71bc9c361baf62c91c4f09401c7':
  Address FIXME comments from previous cleanup CL

3 files changed, 127 insertions, 57 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;
     }
diff --git a/tests/README.txt b/tests/README.txt
index ee64f0c..b5e6dfe 100644
--- a/tests/README.txt
+++ b/tests/README.txt
@@ -6,7 +6,7 @@ adb install <tree root>/out/target/product/generic/data/app/ExactCalculator/Exac
 3) adb install <tree root>/out/target/product/generic/data/app/ExactCalculatorTests/ExactCalculatorTests.apk
 4) adb shell am instrument -w com.android.exactcalculator.tests/android.test.InstrumentationTestRunner
 
-There are two kinds of tests:
+There are three kinds of tests:
 
 1. A superficial test of calculator functionality through the UI.
 This is a resurrected version of a test that appeared in KitKat.
@@ -20,6 +20,9 @@ terminating decimal expansions.  But it's also used to optimize CR
 computations, and bugs in BoundedRational could result in incorrect
 outputs.)
 
+3. A quick test of Evaluator.testUnflipZeroes(), which we do not know how to
+test manually.
+
 We currently have no automatic tests for display formatting corner cases.
 The following numbers have exhibited problems in the past and would be good
 to test.  Some of them are difficult to test automatically, because they
@@ -27,7 +30,7 @@ require scrolling to both ends of the result.  For those with finite
 decimal expansions, it also worth confirming that the "display with leading
 digits" display shows an exact value when scrolled all the way to the right.
 
-Some interesting test cases:
+Some interesting manual test cases:
 
 10^10 + 10^30
 10^30 + 10^-10
diff --git a/tests/src/com/android/calculator2/EvaluatorTest.java b/tests/src/com/android/calculator2/EvaluatorTest.java
new file mode 100644
index 0000000..307aef2
--- /dev/null
+++ b/tests/src/com/android/calculator2/EvaluatorTest.java
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed 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 com.android.calculator2;
+
+import junit.framework.AssertionFailedError;
+import junit.framework.TestCase;
+
+/**
+ * A test for a few static methods in Evaluator.
+ * The most interesting one is for unflipZeroes(), which we don't know how to test with
+ * real calculator input.
+ */
+public class EvaluatorTest extends TestCase {
+    private static void check(boolean x, String s) {
+        if (!x) throw new AssertionFailedError(s);
+    }
+    public void testUnflipZeroes() {
+        check(Evaluator.unflipZeroes("9.99", 2, "9.998", 3).equals("9.998"), "test 1");
+        check(Evaluator.unflipZeroes("9.99", 2, "10.0000", 4).equals("9.9999"), "test 2");
+        check(Evaluator.unflipZeroes("0.99", 2, "1.00000", 5).equals("0.99999"), "test 3");
+        check(Evaluator.unflipZeroes("0.99", 2, "1.00", 2).equals("0.99"), "test 4");
+        check(Evaluator.unflipZeroes("10.00", 2, "9.9999", 4).equals("9.9999"), "test 5");
+        check(Evaluator.unflipZeroes("-10.00", 2, "-9.9999", 4).equals("-9.9999"), "test 6");
+        check(Evaluator.unflipZeroes("-0.99", 2, "-1.00000000000000", 14)
+                .equals("-0.99999999999999"), "test 7");
+        check(Evaluator.unflipZeroes("12349.99", 2, "12350.00000", 5).equals("12349.99999"),
+                "test 8");
+        check(Evaluator.unflipZeroes("123.4999", 4, "123.5000000", 7).equals("123.4999999"),
+                "test 9");
+    }
+
+    public void testGetMsdIndexOf() {
+        check(Evaluator.getMsdIndexOf("-0.0234") == 4, "getMsdIndexOf(-0.0234)");
+        check(Evaluator.getMsdIndexOf("23.45") == 0, "getMsdIndexOf(23.45)");
+        check(Evaluator.getMsdIndexOf("-0.01") == Evaluator.INVALID_MSD, "getMsdIndexOf(-0.01)");
+    }
+
+    public void testExponentEnd() {
+        check(Evaluator.exponentEnd("xE-2%3", 1) == 4, "exponentEnd(xE-2%3)");
+        check(Evaluator.exponentEnd("xE+2%3", 1) == 1, "exponentEnd(xE+2%3)");
+        check(Evaluator.exponentEnd("xe2%3", 1) == 1, "exponentEnd(xe2%3)");
+        check(Evaluator.exponentEnd("xE123%3", 1) == 5, "exponentEnd(xE123%3)");
+        check(Evaluator.exponentEnd("xE123456789%3", 1) == 1, "exponentEnd(xE123456789%3)");
+    }
+}