src/com/android/calculator2/Evaluator.java

/*
 * 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 android.app.AlertDialog;
import android.content.Context;
import android.content.DialogInterface;
import android.content.SharedPreferences;
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;

import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
import java.math.BigInteger;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Random;
import java.util.TimeZone;

/**
 * This implements the calculator evaluation logic.  The underlying expression is constructed and
 * edited with append(), delete(), and clear().  An evaluation an then be started with a call to
 * evaluateAndShowResult() or requireResult().  This starts an asynchronous computation, which
 * requests display of the initial result, when available.  When initial evaluation is complete,
 * it calls the calculator onEvaluate() method.  This occurs in a separate event, possibly quite a
 * bit later.  Once a result has been computed, and before the underlying expression is modified,
 * the getString() method may be used to produce Strings that represent approximations to various
 * precisions.
 *
 * Actual expressions being evaluated are represented as {@link CalculatorExpr}s.
 *
 * The Evaluator owns the expression being edited and all associated state needed for evaluating
 * it.  It provides functionality for saving and restoring this state.  However the current
 * CalculatorExpr is exposed to the client, and may be directly accessed after cancelling any
 * in-progress computations by invoking the cancelAll() method.
 *
 * When evaluation is requested, we invoke the eval() method on the CalculatorExpr from a
 * background AsyncTask.  A subsequent getString() callback returns immediately, though it may
 * return a result containing placeholder ' ' characters.  If we had to return palceholder
 * characters, we start a background task, which invokes the onReevaluate() callback when it
 * completes.  In either case, the background task computes the appropriate result digits by
 * evaluating the constructive real (CR) returned by CalculatorExpr.eval() to the required
 * precision.
 *
 * We cache the best decimal approximation we have already computed.  We compute generously to
 * allow for some scrolling without recomputation and to minimize the chance of digits flipping
 * from "0000" to "9999".  The best known result approximation is maintained as a string by
 * mResultString (and in a different format by the CR representation of the result).  When we are
 * in danger of not having digits to display in response to further scrolling, we also initiate a
 * background computation to higher precision, as if we had generated placeholder characters.
 *
 * The code is designed to ensure that the error in the displayed result (excluding any
 * placeholder characters) is always strictly less than 1 in the last displayed digit.  Typically
 * we actually display a prefix of a result that has this property and additionally is computed to
 * a significantly higher precision.  Thus we almost always round correctly towards zero.  (Fully
 * correct rounding towards zero is not computable, at least given our representation.)
 *
 * Initial expression evaluation may time out.  This may happen in the case of domain errors such
 * as division by zero, or for large computations.  We do not currently time out reevaluations to
 * higher precision, since the original evaluation precluded a domain error that could result in
 * non-termination.  (We may discover that a presumed zero result is actually slightly negative
 * when re-evaluated; but that results in an exception, which we can handle.)  The user can abort
 * either kind of computation.
 *
 * We ensure that only one evaluation of either kind (AsyncEvaluator or AsyncReevaluator) is
 * running at a time.
 */
class Evaluator {

    // When naming variables and fields, "Offset" denotes a character offset in a string
    // representing a decimal number, where the offset is relative to the decimal point.  1 =
    // tenths position, -1 = units position.  Integer.MAX_VALUE is sometimes used for the offset
    // of the last digit in an a nonterminating decimal expansion.  We use the suffix "Index" to
    // denote a zero-based absolute index into such a string.

    private static final String KEY_PREF_DEGREE_MODE = "degree_mode";

    // The minimum number of extra digits we always try to compute to improve the chance of
    // producing a correctly-rounded-towards-zero result.  The extra digits can be displayed to
    // avoid generating placeholder digits, but should only be displayed briefly while computing.
    private static final int EXTRA_DIGITS = 20;

    // We adjust EXTRA_DIGITS by adding the length of the previous result divided by
    // EXTRA_DIVISOR.  This helps hide recompute latency when long results are requested;
    // We start the recomputation substantially before the need is likely to be visible.
    private static final int EXTRA_DIVISOR = 5;

    // In addition to insisting on extra digits (see above), we minimize reevaluation
    // frequency by precomputing an extra PRECOMPUTE_DIGITS
    // + <current_precision_offset>/PRECOMPUTE_DIVISOR digits, whenever we are forced to
    // reevaluate.  The last term is dropped if prec < 0.
    private static final int PRECOMPUTE_DIGITS = 30;
    private static final int PRECOMPUTE_DIVISOR = 5;

    // Initial evaluation precision.  Enough to guarantee that we can compute the short
    // representation, and that we rarely have to evaluate nonzero results to MAX_MSD_PREC_OFFSET.
    // It also helps if this is at least EXTRA_DIGITS + display width, so that we don't
    // immediately need a second evaluation.
    private static final int INIT_PREC = 50;

    // The largest number of digits to the right of the decimal point to which we will evaluate to
    // compute proper scientific notation for values close to zero.  Chosen to ensure that we
    // always to better than IEEE double precision at identifying nonzeros.
    private static final int MAX_MSD_PREC_OFFSET = 320;

    // If we can replace an exponent by this many leading zeroes, we do so.  Also used in
    // estimating exponent size for truncating short representation.
    private static final int EXP_COST = 3;

    private final Calculator mCalculator;
    private final CalculatorResult mResult;

    // The current caluclator expression.
    private CalculatorExpr mExpr;

    // Last saved expression.  Either null or contains a single CalculatorExpr.PreEval node.
    private CalculatorExpr mSaved;

    //  A hopefully unique name associated with mSaved.
    private String mSavedName;

    // The expression may have changed since the last evaluation in ways that would affect its
    // value.
    private boolean mChangedValue;

    private SharedPreferences mSharedPrefs;

    private boolean mDegreeMode;       // Currently in degree (not radian) mode.

    private final Handler mTimeoutHandler;  // Used to schedule evaluation timeouts.

    // The following are valid only if an evaluation completed successfully.
        private CR mVal;               // Value of mExpr as constructive real.
        private BoundedRational mRatVal; // Value of mExpr as rational or null.

    // We cache the best known decimal result in mResultString.  Whenever that is
    // non-null, it is computed to exactly mResultStringOffset, which is always > 0.
    // The cache is filled in by the UI thread.
    // Valid only if mResultString is non-null and !mChangedValue.
    private String mResultString;
    private int mResultStringOffset = 0;

    // Number of digits to which (possibly incomplete) evaluation has been requested.
    // Only accessed by UI thread.
    private int mResultStringOffsetReq;  // Number of digits that have been

    public static final int INVALID_MSD = Integer.MAX_VALUE;

    // Position of most significant digit in current cached result, if determined.  This is just
    // the index in mResultString holding the msd.
    private int mMsdIndex = INVALID_MSD;

    // Currently running expression evaluator, if any.
    private AsyncEvaluator mEvaluator;

    // The one and only un-cancelled and currently running reevaluator. Touched only by UI thread.
    private AsyncReevaluator mCurrentReevaluator;

    Evaluator(Calculator calculator,
              CalculatorResult resultDisplay) {
        mCalculator = calculator;
        mResult = resultDisplay;
        mExpr = new CalculatorExpr();
        mSaved = new CalculatorExpr();
        mSavedName = "none";
        mTimeoutHandler = new Handler();

        mSharedPrefs = PreferenceManager.getDefaultSharedPreferences(calculator);
        mDegreeMode = mSharedPrefs.getBoolean(KEY_PREF_DEGREE_MODE, false);
    }

    /**
     * Result of initial asynchronous result computation.
     * Represents either an error or a result computed to an initial evaluation precision.
     */
    private static class InitialResult {
        public final int errorResourceId;    // Error string or INVALID_RES_ID.
        public final CR val;                 // Constructive real value.
        public final BoundedRational ratVal; // Rational value or null.
        public final String newResultString;       // Null iff it can't be computed.
        public final int newResultStringOffset;
        public final int initDisplayOffset;
        InitialResult(CR v, BoundedRational rv, String s, int p, int idp) {
            errorResourceId = Calculator.INVALID_RES_ID;
            val = v;
            ratVal = rv;
            newResultString = s;
            newResultStringOffset = p;
            initDisplayOffset = idp;
        }
        InitialResult(int errorId) {
            errorResourceId = errorId;
            val = CR.valueOf(0);
            ratVal = BoundedRational.ZERO;
            newResultString = "BAD";
            newResultStringOffset = 0;
            initDisplayOffset = 0;
        }
        boolean isError() {
            return errorResourceId != Calculator.INVALID_RES_ID;
        }
    }

    private void displayCancelledMessage() {
        new AlertDialog.Builder(mCalculator)
            .setMessage(R.string.cancelled)
            .setPositiveButton(R.string.dismiss,
                new DialogInterface.OnClickListener() {
                    public void onClick(DialogInterface d, int which) { }
                })
            .create()
            .show();
    }

    // Timeout handling.
    // Expressions are evaluated with a sort timeout or a long timeout.
    // Each implies different maxima on both computation time and bit length.
    // We recheck bit length separetly to avoid wasting time on decimal conversions that are
    // destined to fail.

    /**
     * Is a long timeout in effect for the main expression?
     */
    private boolean mLongTimeout = false;

    /**
     * Is a long timeout in effect for the saved expression?
     */
    private boolean mLongSavedTimeout = false;

    /**
     * Return the timeout in milliseconds.
     * @param longTimeout a long timeout is in effect
     */
    private long getTimeout(boolean longTimeout) {
        return longTimeout ? 15000 : 2000;
        // Exceeding a few tens of seconds increases the risk of running out of memory
        // and impacting the rest of the system.
    }

    /**
     * Return the maximum number of bits in the result.  Longer results are assumed to time out.
     * @param longTimeout a long timeout is in effect
     */
    private int getMaxResultBits(boolean longTimeout) {
        return longTimeout ? 350000 : 120000;
    }

    /**
     * Timeout for unrequested, speculative evaluations, in milliseconds.
     */
    private final long QUICK_TIMEOUT = 1000;

    /**
     * Maximum result bit length for unrequested, speculative evaluations.
     */
    private final int QUICK_MAX_RESULT_BITS = 50000;

    private void displayTimeoutMessage() {
        AlertDialogFragment.showMessageDialog(mCalculator, mCalculator.getString(R.string.timeout),
                (mLongTimeout ? null : mCalculator.getString(R.string.ok_remove_timeout)));
    }

    public void setLongTimeOut() {
        mLongTimeout = true;
    }

    /**
     * Compute initial cache contents and result when we're good and ready.
     * We leave the expression display up, with scrolling disabled, until this computation
     * completes.  Can result in an error display if something goes wrong.  By default we set a
     * timeout to catch runaway computations.
     */
    class AsyncEvaluator extends AsyncTask<Void, Void, InitialResult> {
        private boolean mDm;  // degrees
        private boolean mRequired; // Result was requested by user.
        private boolean mQuiet;  // Suppress cancellation message.
        private Runnable mTimeoutRunnable = null;
        AsyncEvaluator(boolean dm, boolean required) {
            mDm = dm;
            mRequired = required;
            mQuiet = !required;
        }
        private void handleTimeOut() {
            boolean running = (getStatus() != AsyncTask.Status.FINISHED);
            if (running && cancel(true)) {
                mEvaluator = null;
                // Replace mExpr with clone to avoid races if task
                // still runs for a while.
                mExpr = (CalculatorExpr)mExpr.clone();
                if (mRequired) {
                    suppressCancelMessage();
                    displayTimeoutMessage();
                }
            }
        }
        private void suppressCancelMessage() {
            mQuiet = true;
        }
        @Override
        protected void onPreExecute() {
            long timeout = mRequired ? getTimeout(mLongTimeout) : QUICK_TIMEOUT;
            mTimeoutRunnable = new Runnable() {
                @Override
                public void run() {
                    handleTimeOut();
                }
            };
            mTimeoutHandler.postDelayed(mTimeoutRunnable, timeout);
        }
        /**
         * Is a computed result too big for decimal conversion?
         */
        private boolean isTooBig(CalculatorExpr.EvalResult res) {
            int maxBits = mRequired ? getMaxResultBits(mLongTimeout) : QUICK_MAX_RESULT_BITS;
            if (res.ratVal != null) {
                return res.ratVal.wholeNumberBits() > maxBits;
            } else {
                return res.val.get_appr(maxBits).bitLength() > 2;
            }
        }
        @Override
        protected InitialResult doInBackground(Void... nothing) {
            try {
                CalculatorExpr.EvalResult res = mExpr.eval(mDm);
                if (isTooBig(res)) {
                    // Avoid starting a long uninterruptible decimal conversion.
                    return new InitialResult(R.string.timeout);
                }
                int precOffset = INIT_PREC;
                String initResult = res.val.toString(precOffset);
                int msd = getMsdIndexOf(initResult);
                if (BoundedRational.asBigInteger(res.ratVal) == null
                        && msd == INVALID_MSD) {
                    precOffset = MAX_MSD_PREC_OFFSET;
                    initResult = res.val.toString(precOffset);
                    msd = getMsdIndexOf(initResult);
                }
                final int lsdOffset = getLsdOffset(res.ratVal, initResult,
                        initResult.indexOf('.'));
                final int initDisplayOffset = getPreferredPrec(initResult, msd, lsdOffset);
                final int newPrecOffset = initDisplayOffset + EXTRA_DIGITS;
                if (newPrecOffset > precOffset) {
                    precOffset = newPrecOffset;
                    initResult = res.val.toString(precOffset);
                }
                return new InitialResult(res.val, res.ratVal,
                        initResult, precOffset, initDisplayOffset);
            } catch (CalculatorExpr.SyntaxException e) {
                return new InitialResult(R.string.error_syntax);
            } catch (BoundedRational.ZeroDivisionException e) {
                return new InitialResult(R.string.error_zero_divide);
            } catch(ArithmeticException e) {
                return new InitialResult(R.string.error_nan);
            } catch(CR.PrecisionOverflowException e) {
                // Extremely unlikely unless we're actually dividing by zero or the like.
                return new InitialResult(R.string.error_overflow);
            } catch(CR.AbortedException e) {
                return new InitialResult(R.string.error_aborted);
            }
        }
        @Override
        protected void onPostExecute(InitialResult result) {
            mEvaluator = null;
            mTimeoutHandler.removeCallbacks(mTimeoutRunnable);
            if (result.isError()) {
                if (result.errorResourceId == R.string.timeout) {
                    if (mRequired) {
                        displayTimeoutMessage();
                    }
                    mCalculator.onCancelled();
                } else {
                    mCalculator.onError(result.errorResourceId);
                }
                return;
            }
            mVal = result.val;
            mRatVal = result.ratVal;
            // TODO: If the new result ends in lots of zeroes, and we have a rational result which
            // is greater than (in absolute value) the result string, we should subtract 1 ulp
            // from the result string.  That will prevent a later change from zeroes to nines.  We
            // know that the correct, rounded-toward-zero result has nines.
            mResultString = result.newResultString;
            mResultStringOffset = result.newResultStringOffset;
            final int dotIndex = mResultString.indexOf('.');
            String truncatedWholePart = mResultString.substring(0, dotIndex);
            // Recheck display precision; it may change, since display dimensions may have been
            // unknow the first time.  In that case the initial evaluation precision should have
            // been conservative.
            // TODO: Could optimize by remembering display size and checking for change.
            int initPrecOffset = result.initDisplayOffset;
            final int msdIndex = getMsdIndexOf(mResultString);
            final int leastDigOffset = getLsdOffset(mRatVal, mResultString, dotIndex);
            final int newInitPrecOffset = getPreferredPrec(mResultString, msdIndex, leastDigOffset);
            if (newInitPrecOffset < initPrecOffset) {
                initPrecOffset = newInitPrecOffset;
            } else {
                // They should be equal.  But nothing horrible should happen if they're not. e.g.
                // because CalculatorResult.MAX_WIDTH was too small.
            }
            mCalculator.onEvaluate(initPrecOffset, msdIndex, leastDigOffset, truncatedWholePart);
        }
        @Override
        protected void onCancelled(InitialResult result) {
            // Invoker resets mEvaluator.
            mTimeoutHandler.removeCallbacks(mTimeoutRunnable);
            if (mRequired && !mQuiet) {
                displayCancelledMessage();
            } // Otherwise, if mRequired, timeout processing displayed message.
            mCalculator.onCancelled();
            // Just drop the evaluation; Leave expression displayed.
            return;
        }
    }

    /**
     * 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 {
        public final String newResultString;
        public final int newResultStringOffset;
        ReevalResult(String s, int p) {
            newResultString = s;
            newResultStringOffset = p;
        }
    }

    /**
     * Compute new mResultString contents to prec digits to the right of the decimal point.
     * Ensure that onReevaluate() is called after doing so.  If the evaluation fails for reasons
     * other than a timeout, ensure that onError() is called.
     */
    private class AsyncReevaluator extends AsyncTask<Integer, Void, ReevalResult> {
        @Override
        protected ReevalResult doInBackground(Integer... prec) {
            try {
                final int precOffset = prec[0].intValue();
                return new ReevalResult(mVal.toString(precOffset), precOffset);
            } catch(ArithmeticException e) {
                return null;
            } catch(CR.PrecisionOverflowException e) {
                return null;
            } catch(CR.AbortedException e) {
                // Should only happen if the task was cancelled, in which case we don't look at
                // the result.
                return null;
            }
        }

        @Override
        protected void onPostExecute(ReevalResult result) {
            if (result == null) {
                // 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.
                mCalculator.onError(R.string.error_nan);
            } else {
                if (result.newResultStringOffset < mResultStringOffset) {
                    throw new AssertionError("Unexpected onPostExecute timing");
                }
                mResultString = unflipZeroes(mResultString, mResultStringOffset,
                        result.newResultString, result.newResultStringOffset);
                mResultStringOffset = result.newResultStringOffset;
                mCalculator.onReevaluate();
            }
            mCurrentReevaluator = null;
        }
        // On cancellation we do nothing; invoker should have left no trace of us.
    }

    /**
     * If necessary, start an evaluation to precOffset.
     * Ensure that the display is redrawn when it completes.
     */
    private void ensureCachePrec(int precOffset) {
        if (mResultString != null && mResultStringOffset >= precOffset
                || mResultStringOffsetReq >= precOffset) return;
        if (mCurrentReevaluator != null) {
            // Ensure we only have one evaluation running at a time.
            mCurrentReevaluator.cancel(true);
            mCurrentReevaluator = null;
        }
        mCurrentReevaluator = new AsyncReevaluator();
        mResultStringOffsetReq = precOffset + PRECOMPUTE_DIGITS;
        if (mResultString != null) {
            mResultStringOffsetReq += mResultStringOffsetReq / PRECOMPUTE_DIVISOR;
        }
        mCurrentReevaluator.execute(mResultStringOffsetReq);
    }

    /**
     * Return the rightmost nonzero digit position, if any.
     * @param ratVal Rational value of result or null.
     * @param cache Current cached decimal string representation of result.
     * @param decIndex Index of decimal point in cache.
     * @result Position of rightmost nonzero digit relative to decimal point.
     *         Integer.MIN_VALUE if ratVal is zero.  Integer.MAX_VALUE if there is no lsd,
     *         or we cannot determine it.
     */
    int getLsdOffset(BoundedRational ratVal, String cache, int decIndex) {
        if (ratVal != null && ratVal.signum() == 0) return Integer.MIN_VALUE;
        int result = BoundedRational.digitsRequired(ratVal);
        if (result == 0) {
            int i;
            for (i = -1; decIndex + i > 0 && cache.charAt(decIndex + i) == '0'; --i) { }
            result = i;
        }
        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 "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.
     *            Can be INVALID_MSD if we haven't found it yet.
     * @param lastDigitOffset Position of least significant digit (1 = tenths digit)
     *                  or Integer.MAX_VALUE.
     */
    private int getPreferredPrec(String cache, int msd, int lastDigitOffset) {
        final int lineLength = mResult.getMaxChars();
        final int wholeSize = cache.indexOf('.');
        final int negative = cache.charAt(0) == '-' ? 1 : 0;
        // Don't display decimal point if result is an integer.
        if (lastDigitOffset == 0) {
            lastDigitOffset = -1;
        }
        if (lastDigitOffset != Integer.MAX_VALUE) {
            if (wholeSize <= lineLength && lastDigitOffset <= 0) {
                // Exact integer.  Prefer to display as integer, without decimal point.
                return -1;
            }
            if (lastDigitOffset >= 0
                    && wholeSize + lastDigitOffset + 1 /* decimal pt. */ <= lineLength) {
                // Display full exact number wo scientific notation.
                return lastDigitOffset;
            }
        }
        if (msd > wholeSize && msd <= wholeSize + EXP_COST + 1) {
            // Display number without scientific notation.  Treat leading zero as msd.
            msd = wholeSize - 1;
        }
        if (msd > wholeSize + MAX_MSD_PREC_OFFSET) {
            // Display a probable but uncertain 0 as "0.000000000",
            // without exponent.  That's a judgment call, but less likely
            // to confuse naive users.  A more informative and confusing
            // option would be to use a large negative exponent.
            return lineLength - 2;
        }
        // Return position corresponding to having msd at left, effectively
        // presuming scientific notation that preserves the left part of the
        // result.
        return msd - wholeSize + lineLength - negative - 1;
    }

    private static final int SHORT_TARGET_LENGTH  = 8;
    private static final String SHORT_UNCERTAIN_ZERO = "0.00000" + KeyMaps.ELLIPSIS;

    /**
     * Get a short representation of the value represented by the string cache.
     * We try to match the CalculatorResult code when the result is finite
     * and small enough to suit our needs.
     * The result is not internationalized.
     * @param cache String approximation of value.  Assumed to be long enough
     *              that if it doesn't contain enough significant digits, we can
     *              reasonably abbreviate as SHORT_UNCERTAIN_ZERO.
     * @param msdIndex Index of most significant digit in cache, or INVALID_MSD.
     * @param lsdOffset Position of least significant digit in finite representation,
     *            relative to decimal point, or MAX_VALUE.
     */
    private String getShortString(String cache, int msdIndex, int lsdOffset) {
        // This somewhat mirrors the display formatting code, but
        // - The constants are different, since we don't want to use the whole display.
        // - This is an easier problem, since we don't support scrolling and the length
        //   is a bit flexible.
        // TODO: Think about refactoring this to remove partial redundancy with CalculatorResult.
        final int dotIndex = cache.indexOf('.');
        final int negative = cache.charAt(0) == '-' ? 1 : 0;
        final String negativeSign = negative == 1 ? "-" : "";

        // Ensure we don't have to worry about running off the end of cache.
        if (msdIndex >= cache.length() - SHORT_TARGET_LENGTH) {
            msdIndex = INVALID_MSD;
        }
        if (msdIndex == INVALID_MSD) {
            if (lsdOffset < INIT_PREC) {
                return "0";
            } else {
                return SHORT_UNCERTAIN_ZERO;
            }
        }
        // Avoid scientific notation for small numbers of zeros.
        // Instead stretch significant digits to include decimal point.
        if (lsdOffset < -1 && dotIndex - msdIndex + negative <= SHORT_TARGET_LENGTH
            && lsdOffset >= -CalculatorResult.MAX_TRAILING_ZEROES - 1) {
            // Whole number that fits in allotted space.
            // CalculatorResult would not use scientific notation either.
            lsdOffset = -1;
        }
        if (msdIndex > dotIndex) {
            if (msdIndex <= dotIndex + EXP_COST + 1) {
                // Preferred display format inthis cases is with leading zeroes, even if
                // it doesn't fit entirely.  Replicate that here.
                msdIndex = dotIndex - 1;
            } else if (lsdOffset <= SHORT_TARGET_LENGTH - negative - 2
                    && lsdOffset <= CalculatorResult.MAX_LEADING_ZEROES + 1) {
                // Fraction that fits entirely in allotted space.
                // CalculatorResult would not use scientific notation either.
                msdIndex = dotIndex -1;
            }
        }
        int exponent = dotIndex - msdIndex;
        if (exponent > 0) {
            // Adjust for the fact that the decimal point itself takes space.
            exponent--;
        }
        if (lsdOffset != Integer.MAX_VALUE) {
            final int lsdIndex = dotIndex + lsdOffset;
            final int totalDigits = lsdIndex - msdIndex + negative + 1;
            if (totalDigits <= SHORT_TARGET_LENGTH && dotIndex > msdIndex && lsdOffset >= -1) {
                // Fits, no exponent needed.
                return negativeSign + cache.substring(msdIndex, lsdIndex + 1);
            }
            if (totalDigits <= SHORT_TARGET_LENGTH - 3) {
                return negativeSign + cache.charAt(msdIndex) + "."
                        + cache.substring(msdIndex + 1, lsdIndex + 1) + "E" + exponent;
            }
        }
        // We need to abbreviate.
        if (dotIndex > msdIndex && dotIndex < msdIndex + SHORT_TARGET_LENGTH - negative - 1) {
            return negativeSign + cache.substring(msdIndex,
                    msdIndex + SHORT_TARGET_LENGTH - negative - 1) + KeyMaps.ELLIPSIS;
        }
        // Need abbreviation + exponent
        return negativeSign + cache.charAt(msdIndex) + "."
                + cache.substring(msdIndex + 1, msdIndex + SHORT_TARGET_LENGTH - negative - 4)
                + KeyMaps.ELLIPSIS + "E" + exponent;
    }

    /**
     * Return the most significant digit index in the given numeric string.
     * Return INVALID_MSD if there are not enough digits to prove the numeric value is
     * different from zero.  As usual, we assume an error of strictly less than 1 ulp.
     */
    public static int getMsdIndexOf(String s) {
        final int len = s.length();
        int nonzeroIndex = -1;
        for (int i = 0; i < len; ++i) {
            char c = s.charAt(i);
            if (c != '-' && c != '.' && c != '0') {
                nonzeroIndex = i;
                break;
            }
        }
        if (nonzeroIndex >= 0 && (nonzeroIndex < len - 1 || s.charAt(nonzeroIndex) != '1')) {
            return nonzeroIndex;
        } else {
            return INVALID_MSD;
        }
    }

    /**
     * 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() {
        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
        }
        int result = INVALID_MSD;
        if (mResultString != null) {
            result = getMsdIndexOf(mResultString);
        }
        return result;
    }

    /**
     * Return a string with n copies of c.
     */
    private static String repeat(char c, int n) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            result.append(c);
        }
        return result.toString();
    }

    // Refuse to scroll past the point at which this many digits from the whole number
    // part of the result are still displayed.  Avoids sily displays like 1E1.
    private static final int MIN_DISPLAYED_DIGS = 5;

    /**
     * Return result to precOffset[0] digits to the right of the decimal point.
     * PrecOffset[0] is updated if the original value is out of range.  No exponent or other
     * indication of precision is added.  The result is returned immediately, based on the current
     * cache contents, but it may contain question marks for unknown digits.  It may also use
     * uncertain digits within EXTRA_DIGITS.  If either of those occurred, schedule a reevaluation
     * and redisplay operation.  Uncertain digits never appear to the left of the decimal point.
     * PrecOffset[0] may be negative to only retrieve digits to the left of the decimal point.
     * (precOffset[0] = 0 means we include the decimal point, but nothing to the right.
     * precOffset[0] = -1 means we drop the decimal point and start at the ones position.  Should
     * not be invoked before the onEvaluate() callback is received.  This essentially just returns
     * a substring of the full result; a leading minus sign or leading digits can be dropped.
     * Result uses US conventions; is NOT internationalized.  Use getRational() to determine
     * whether the result is exact, or whether we dropped trailing digits.
     *
     * @param precOffset Zeroth element indicates desired and actual precision
     * @param maxPrecOffset Maximum adjusted precOffset[0]
     * @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.
     */
    public String getString(int[] precOffset, int maxPrecOffset, int maxDigs, boolean[] truncated,
            boolean[] negative) {
        int currentPrecOffset = precOffset[0];
        // Make sure we eventually get a complete answer
        if (mResultString == null) {
            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 " ";
        } else {
            ensureCachePrec(currentPrecOffset + EXTRA_DIGITS + mResultString.length()
                    / EXTRA_DIVISOR);
        }
        // Compute an appropriate substring of mResultString.  Pad if necessary.
        final int len = mResultString.length();
        final boolean myNegative = mResultString.charAt(0) == '-';
        negative[0] = myNegative;
        // Don't scroll left past leftmost digits in mResultString unless that still leaves an
        // integer.
            int integralDigits = len - mResultStringOffset;
                            // includes 1 for dec. pt
            if (myNegative) {
                --integralDigits;
            }
            int minPrecOffset = Math.min(MIN_DISPLAYED_DIGS - integralDigits, -1);
            currentPrecOffset = Math.min(Math.max(currentPrecOffset, minPrecOffset),
                    maxPrecOffset);
            precOffset[0] = currentPrecOffset;
        int extraDigs = mResultStringOffset - currentPrecOffset; // trailing digits to drop
        int deficit = 0;  // The number of digits we're short
        if (extraDigs < 0) {
            extraDigs = 0;
            deficit = Math.min(currentPrecOffset - mResultStringOffset, maxDigs);
        }
        int endIndex = len - extraDigs;
        if (endIndex < 1) {
            return " ";
        }
        int startIndex = Math.max(endIndex + deficit - maxDigs, 0);
        truncated[0] = (startIndex > getMsdIndex());
        String result = mResultString.substring(startIndex, endIndex);
        if (deficit > 0) {
            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.
        }
        return result;
    }

    /**
     * Return rational representation of current result, if any.
     * Return null if the result is irrational, or we couldn't track the rational value,
     * e.g. because the denominator got too big.
     */
    public BoundedRational getRational() {
        return mRatVal;
    }

    private void clearCache() {
        mResultString = null;
        mResultStringOffset = mResultStringOffsetReq = 0;
        mMsdIndex = INVALID_MSD;
    }


    private void clearPreservingTimeout() {
        mExpr.clear();
        clearCache();
    }

    public void clear() {
        clearPreservingTimeout();
        mLongTimeout = false;
    }

    /**
     * Start asynchronous result evaluation of formula.
     * Will result in display on completion.
     * @param required result was explicitly requested by user.
     */
    private void evaluateResult(boolean required) {
        clearCache();
        mEvaluator = new AsyncEvaluator(mDegreeMode, required);
        mEvaluator.execute();
        mChangedValue = false;
    }

    /**
     * Start optional evaluation of result and display when ready.
     * Can quietly time out without a user-visible display.
     */
    public void evaluateAndShowResult() {
        if (!mChangedValue) {
            // Already done or in progress.
            return;
        }
        // In very odd cases, there can be significant latency to evaluate.
        // Don't show obsolete result.
        mResult.clear();
        evaluateResult(false);
    }

    /**
     * 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.
            cancelAll(true);
            evaluateResult(true);
        } else {
            // Notify immediately, reusing existing result.
            final int dotIndex = mResultString.indexOf('.');
            final String truncatedWholePart = mResultString.substring(0, dotIndex);
            final int leastDigOffset = getLsdOffset(mRatVal, mResultString, dotIndex);
            final int msdIndex = getMsdIndex();
            final int preferredPrecOffset = getPreferredPrec(mResultString, msdIndex,
                    leastDigOffset);
            mCalculator.onEvaluate(preferredPrecOffset, msdIndex, leastDigOffset,
                    truncatedWholePart);
        }
    }

    /**
     * Cancel all current background tasks.
     * @param quiet suppress cancellation message
     * @return      true if we cancelled an initial evaluation
     */
    public boolean cancelAll(boolean quiet) {
        if (mCurrentReevaluator != null) {
            mCurrentReevaluator.cancel(true);
            mResultStringOffsetReq = mResultStringOffset;
            // Backgound computation touches only constructive reals.
            // OK not to wait.
            mCurrentReevaluator = null;
        }
        if (mEvaluator != null) {
            if (quiet) {
                mEvaluator.suppressCancelMessage();
            }
            mEvaluator.cancel(true);
            // There seems to be no good way to wait for cancellation
            // to complete, and the evaluation continues to look at
            // mExpr, which we will again modify.
            // Give ourselves a new copy to work on instead.
            mExpr = (CalculatorExpr)mExpr.clone();
            // Approximation of constructive reals should be thread-safe,
            // so we can let that continue until it notices the cancellation.
            mEvaluator = null;
            mChangedValue = true;    // Didn't do the expected evaluation.
            return true;
        }
        return false;
    }

    /**
     * Restore the evaluator state, including the expression and any saved value.
     */
    public void restoreInstanceState(DataInput in) {
        mChangedValue = true;
        try {
            CalculatorExpr.initExprInput();
            mDegreeMode = in.readBoolean();
            mLongTimeout = in.readBoolean();
            mLongSavedTimeout = in.readBoolean();
            mExpr = new CalculatorExpr(in);
            mSavedName = in.readUTF();
            mSaved = new CalculatorExpr(in);
        } catch (IOException e) {
            Log.v("Calculator", "Exception while restoring:\n" + e);
        }
    }

    /**
     * Save the evaluator state, including the expression and any saved value.
     */
    public void saveInstanceState(DataOutput out) {
        try {
            CalculatorExpr.initExprOutput();
            out.writeBoolean(mDegreeMode);
            out.writeBoolean(mLongTimeout);
            out.writeBoolean(mLongSavedTimeout);
            mExpr.write(out);
            out.writeUTF(mSavedName);
            mSaved.write(out);
        } catch (IOException e) {
            Log.v("Calculator", "Exception while saving state:\n" + e);
        }
    }


    /**
     * Append a button press to the current expression.
     * @param id Button identifier for the character or operator to be added.
     * @return false if we rejected the insertion due to obvious syntax issues, and the expression
     * is unchanged; true otherwise
     */
    public boolean append(int id) {
        if (id == R.id.fun_10pow) {
            add10pow();  // Handled as macro expansion.
            return true;
        } else {
            mChangedValue = mChangedValue || !KeyMaps.isBinary(id);
            return mExpr.add(id);
        }
    }

    public void delete() {
        mChangedValue = true;
        mExpr.delete();
        if (mExpr.isEmpty()) {
            mLongTimeout = false;
        }
    }

    void setDegreeMode(boolean degreeMode) {
        mChangedValue = true;
        mDegreeMode = degreeMode;

        mSharedPrefs.edit()
                .putBoolean(KEY_PREF_DEGREE_MODE, degreeMode)
                .apply();
    }

    boolean getDegreeMode() {
        return mDegreeMode;
    }

    /**
     * @return the {@link CalculatorExpr} representation of the current result.
     */
    private CalculatorExpr getResultExpr() {
        final int dotIndex = mResultString.indexOf('.');
        final int leastDigOffset = getLsdOffset(mRatVal, mResultString, dotIndex);
        return mExpr.abbreviate(mVal, mRatVal, mDegreeMode,
                getShortString(mResultString, getMsdIndexOf(mResultString), leastDigOffset));
    }

    /**
     * Abbreviate the current expression to a pre-evaluated expression node.
     * This should not be called unless the expression was previously evaluated and produced a
     * non-error result.  Pre-evaluated expressions can never represent an expression for which
     * evaluation to a constructive real diverges.  Subsequent re-evaluation will also not
     * diverge, though it may generate errors of various kinds.  E.g.  sqrt(-10^-1000) .
     */
    public void collapse() {
        final CalculatorExpr abbrvExpr = getResultExpr();
        clearPreservingTimeout();
        mExpr.append(abbrvExpr);
        mChangedValue = true;
    }

    /**
     * Abbreviate current expression, and put result in mSaved.
     * mExpr is left alone.  Return false if result is unavailable.
     */
    public boolean collapseToSaved() {
        if (mResultString == null) {
            return false;
        }
        final CalculatorExpr abbrvExpr = getResultExpr();
        mSaved.clear();
        mSaved.append(abbrvExpr);
        mLongSavedTimeout = mLongTimeout;
        return true;
    }

    private Uri uriForSaved() {
        return new Uri.Builder().scheme("tag")
                                .encodedOpaquePart(mSavedName)
                                .build();
    }

    /**
     * Collapse the current expression to mSaved and return a URI describing it.
     * describing this particular result, so that we can refer to it
     * later.
     */
    public Uri capture() {
        if (!collapseToSaved()) return null;
        // Generate a new (entirely private) URI for this result.
        // Attempt to conform to RFC4151, though it's unclear it matters.
        final TimeZone tz = TimeZone.getDefault();
        DateFormat df = new SimpleDateFormat("yyyy-MM-dd");
        df.setTimeZone(tz);
        final String isoDate = df.format(new Date());
        mSavedName = "calculator2.android.com," + isoDate + ":"
                + (new Random().nextInt() & 0x3fffffff);
        return uriForSaved();
    }

    public boolean isLastSaved(Uri uri) {
        return uri.equals(uriForSaved());
    }

    public void appendSaved() {
        mChangedValue = true;
        mLongTimeout |= mLongSavedTimeout;
        mExpr.append(mSaved);
    }

    /**
     * Add the power of 10 operator to the expression.
     * This is treated essentially as a macro expansion.
     */
    private void add10pow() {
        CalculatorExpr ten = new CalculatorExpr();
        ten.add(R.id.digit_1);
        ten.add(R.id.digit_0);
        mChangedValue = true;  // For consistency.  Reevaluation is probably not useful.
        mExpr.append(ten);
        mExpr.add(R.id.op_pow);
    }

    /**
     * Retrieve the main expression being edited.
     * It is the callee's reponsibility to call cancelAll to cancel ongoing concurrent
     * computations before modifying the result.  The resulting expression should only
     * be modified by the caller if either the expression value doesn't change, or in
     * combination with another add() or delete() call that makes the value change apparent
     * to us.
     * TODO: Perhaps add functionality so we can keep this private?
     */
    public CalculatorExpr getExpr() {
        return mExpr;
    }

    /**
     * Maximum number of characters in a scientific notation exponent.
     */
    private static final int MAX_EXP_CHARS = 8;

    /**
     * Return the index of the character after the exponent starting at s[offset].
     * Return offset if there is no exponent at that position.
     * Exponents have syntax E[-]digit* .  "E2" and "E-2" are valid.  "E+2" and "e2" are not.
     * We allow any Unicode digits, and either of the commonly used minus characters.
     */
    public static int exponentEnd(String s, int offset) {
        int i = offset;
        int len = s.length();
        if (i >= len - 1 || s.charAt(i) != 'E') {
            return offset;
        }
        ++i;
        if (KeyMaps.keyForChar(s.charAt(i)) == R.id.op_sub) {
            ++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;
    }

    /**
     * Add the exponent represented by s[begin..end) to the constant at the end of current
     * expression.
     * The end of the current expression must be a constant.  Exponents have the same syntax as
     * for exponentEnd().
     */
    public void addExponent(String s, int begin, int end) {
        int sign = 1;
        int exp = 0;
        int i = begin + 1;
        // We do the decimal conversion ourselves to exactly match exponentEnd() conventions
        // and handle various kinds of digits on input.  Also avoids allocation.
        if (KeyMaps.keyForChar(s.charAt(i)) == R.id.op_sub) {
            sign = -1;
            ++i;
        }
        for (; i < end; ++i) {
            exp = 10 * exp + Character.digit(s.charAt(i), 10);
        }
        mExpr.addExponent(sign * exp);
        mChangedValue = true;
    }
}