Added SafeNum type SERVER-6399

4 files changed, 595 insertions, 0 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index b60de486459..06022a1d492 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -43,6 +43,7 @@ env.StaticLibrary('md5', [
         ])
 
 env.StaticLibrary('bson', [
+        'util/safe_num.cpp',
         'bson/oid.cpp',
         'db/nonce.cpp',
         'db/jsobj.cpp',
@@ -52,6 +53,9 @@ env.StaticLibrary('bson', [
         'stringutils',
         ])
 
+env.CppUnitTest('safe_num_test', ['util/safe_num_test.cpp'],
+                LIBDEPS=['bson'])
+
 commonFiles = [ "pch.cpp",
                 "buildinfo.cpp",
                 "db/hasher.cpp",
diff --git a/src/mongo/util/safe_num.cpp b/src/mongo/util/safe_num.cpp
new file mode 100644
index 00000000000..f28131ea491
--- /dev/null
+++ b/src/mongo/util/safe_num.cpp
@@ -0,0 +1,252 @@
+/*    Copyright 2012 10gen Inc.
+ *
+ *    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.
+ */
+
+#include <sstream>
+
+#include "mongo/pch.h" // for malloc/realloc/INFINITY pulled from bson
+
+#include "mongo/bson/bsontypes.h"
+#include "mongo/util/safe_num.h"
+
+namespace mongo {
+
+    SafeNum::SafeNum() : _type(EOO) {
+    }
+
+    SafeNum::SafeNum(const SafeNum& rhs) : _type(rhs._type), _value(rhs._value) {
+    }
+
+    SafeNum& SafeNum::operator=(const SafeNum& rhs) {
+        _type = rhs._type;
+        _value = rhs._value;
+        return *this;
+    }
+
+    SafeNum::SafeNum(const BSONElement& element) {
+        switch (element.type()) {
+        case NumberInt:
+            _type = NumberInt;
+            _value.int32Val = element.Int();
+            break;
+        case NumberLong:
+            _type = NumberLong;
+            _value.int64Val = element.Long();
+            break;
+        case NumberDouble:
+            _type = NumberDouble;
+            _value.doubleVal = element.Double();
+            break;
+        default:
+            _type = EOO;
+        }
+    }
+
+    SafeNum::SafeNum(int num) : _type(NumberInt) {
+        _value.int32Val = num;
+    }
+
+    SafeNum::SafeNum(long long int num) : _type(NumberLong) {
+        _value.int64Val = num;
+    }
+
+    SafeNum::SafeNum(double num) : _type(NumberDouble) {
+        _value.doubleVal = num;
+    }
+
+    SafeNum SafeNum::operator+(const SafeNum& rhs) const {
+        return addInternal(*this, rhs);
+    }
+
+    SafeNum& SafeNum::operator+=(const SafeNum& rhs) {
+        return *this = addInternal(*this, rhs);
+    }
+
+    bool SafeNum::operator==(const SafeNum& rhs) const {
+        return isEquivalent(rhs);
+    }
+
+    bool SafeNum::operator!=(const SafeNum& rhs) const {
+        return ! isEquivalent(rhs);
+    }
+
+    std::string SafeNum::debugString() const {
+        ostringstream os;
+        switch (_type) {
+        case NumberInt:
+            os << "(NumberInt)" << _value.int32Val;
+            break;
+        case NumberLong:
+            os << "(NumberLong)" << _value.int64Val;
+            break;
+        case NumberDouble:
+            os << "(NumberDouble)" << _value.doubleVal;
+            break;
+        case EOO:
+            os << "(EOO)";
+            break;
+        default:
+            os << "(unknown type)";
+        }
+
+        return os.str();
+    }
+
+    std::ostream& operator<<(std::ostream& os, const SafeNum& snum) {
+        return os << snum.debugString();
+    }
+
+    //
+    // comparison support
+    //
+
+    bool SafeNum::isEquivalent(const SafeNum& rhs) const {
+        if (_type == EOO && rhs._type == EOO) {
+            return true;
+        }
+
+        // EOO is not equivalent to anything else.
+        if (_type == EOO || rhs._type == EOO) {
+            return false;
+        }
+
+        // If the types of either side are mixed, we'll try to find the shortest type we
+        // can upconvert to that would not sacrifice the accuracy in the process.
+
+        // If none of the sides is a double, compare them as long's.
+        if (_type != NumberDouble && rhs._type != NumberDouble) {
+            return getLongLong(*this) == getLongLong(rhs);
+        }
+
+        // If both sides are doubles, compare them as so.
+        if (_type == NumberDouble && rhs._type == NumberDouble) {
+            return _value.doubleVal == rhs._value.doubleVal;
+        }
+
+        // If we're mixing integers and doubles, we should be carefull. Some integers are
+        // too big to be accuratelly represented in a double. If we're within a safe range
+        // we compare both sides as doubles.
+        const double lhsDouble = getDouble(*this);
+        const double rhsDouble = getDouble(rhs);
+        if (lhsDouble > -maxIntInDouble && lhsDouble < maxIntInDouble &&
+            rhsDouble > -maxIntInDouble && rhsDouble < maxIntInDouble) {
+            return lhsDouble == rhsDouble;
+        }
+
+        return false;
+    }
+
+    bool SafeNum::isIdentical(const SafeNum& rhs) const {
+        if (_type != rhs._type) {
+            return false;
+        }
+
+        switch (_type) {
+        case NumberInt:
+            return _value.int32Val == rhs._value.int32Val;
+        case NumberLong:
+            return _value.int64Val == rhs._value.int64Val;
+        case NumberDouble:
+            return _value.doubleVal == rhs._value.doubleVal;
+        case EOO:
+            // EOO doesn't match anything, including itself.
+        default:
+            return false;
+        }
+    }
+
+    long long SafeNum::getLongLong(const SafeNum& snum) {
+        switch (snum._type) {
+        case NumberInt:
+            return snum._value.int32Val;
+        case NumberLong:
+            return snum._value.int64Val;
+        default:
+            return 0;
+        }
+    }
+
+    double SafeNum::getDouble(const SafeNum& snum) {
+        switch (snum._type) {
+        case NumberInt:
+            return snum._value.int32Val;
+        case NumberLong:
+            return snum._value.int64Val;
+        case NumberDouble:
+            return snum._value.doubleVal;
+        default:
+            return 0.0;
+        }
+    }
+
+    //
+    // addition support
+    //
+
+    SafeNum addInt32Int32(int lInt32, int rInt32) {
+        int sum = lInt32 + rInt32;
+        if ((sum < 0 && lInt32 > 0 && rInt32 > 0) ||
+            (sum > 0 && lInt32 < 0 && rInt32 < 0)) {
+            long long int result = static_cast<long long int>(lInt32) +
+                                   static_cast<long long int>(rInt32);
+            return SafeNum(result);
+        }
+
+        return SafeNum(sum);
+    }
+
+    SafeNum addInt64Int64(long long lInt64, long long rInt64) {
+        long long sum = lInt64 + rInt64;
+        if ((sum < 0 && lInt64 > 0 && rInt64 > 0) ||
+            (sum > 0 && lInt64 < 0 && rInt64 < 0)) {
+            return SafeNum();
+        }
+
+        return SafeNum(sum);
+    }
+
+    SafeNum addFloats(double lDouble, double rDouble) {
+        double sum = lDouble + rDouble;
+        return SafeNum(sum);
+    }
+
+    SafeNum SafeNum::addInternal(const SafeNum& lhs, const SafeNum& rhs) {
+        BSONType lType = lhs._type;
+        BSONType rType = rhs._type;
+
+        if (lType == NumberInt && rType == NumberInt) {
+            return addInt32Int32(lhs._value.int32Val, rhs._value.int32Val);
+        }
+
+        if (lType == NumberInt && rType == NumberLong) {
+            return addInt64Int64(lhs._value.int32Val, rhs._value.int64Val);
+        }
+
+        if (lType == NumberLong && rType == NumberInt) {
+            return addInt64Int64(lhs._value.int64Val, rhs._value.int32Val);
+        }
+
+        if (lType == NumberLong && rType == NumberLong) {
+            return addInt64Int64(lhs._value.int64Val, rhs._value.int64Val);
+        }
+
+        if ((lType == NumberInt || lType == NumberLong || lType == NumberDouble) &&
+            (rType == NumberInt || rType == NumberLong || rType == NumberDouble)) {
+            return addFloats(getDouble(lhs), getDouble(rhs));
+        }
+
+        return SafeNum();
+    }
+
+} // namespace mongo
diff --git a/src/mongo/util/safe_num.h b/src/mongo/util/safe_num.h
new file mode 100644
index 00000000000..e8e099939ec
--- /dev/null
+++ b/src/mongo/util/safe_num.h
@@ -0,0 +1,160 @@
+/*    Copyright 2012 10gen Inc.
+ *
+ *    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.
+ */
+
+#pragma once
+
+#include <iosfwd>
+#include <string>
+
+#include "mongo/bson/bsonelement.h"
+#include "mongo/bson/bsonobj.h"
+
+namespace mongo {
+
+    /**
+     * SafeNum holds and does arithmetic on a number in a safe way, handling overflow
+     * and casting for the user. 32-bit integers will overflow into 64-bit integers. But
+     * 64-bit integers will NOT overflow to doubles. Also, this class does NOT
+     * downcast. This class should be as conservative as possible about upcasting, but
+     * should never lose precision.
+     *
+     * This class does not throw any exceptions, so the user should call type() before
+     * using a SafeNum to ensure that it is valid.  A SafeNum could be invalid
+     * from creation (if, for example, a non-numeric BSONElement was passed to the
+     * constructor) or due to overflow.  NAN is a valid value.
+     *
+     * Usage example:
+     *
+     *      SafeNum counter(doc["count"]);
+     *
+     *      SafeNum newValue = counter + 10;
+     *      // check if valid
+     *      if (newValue.type() == EOO) {
+     *          return;
+     *      }
+     *      // append SafeNum to a BSONObj
+     *      bsonObjBuilder.append(newValue);
+     *
+     */
+    class SafeNum {
+    public:
+        SafeNum();
+        ~SafeNum() { }
+
+        //
+        // construction support
+        //
+
+        // Copy ctor and assignment are allowed.
+        SafeNum(const SafeNum& rhs);
+        SafeNum& operator=(const SafeNum& rhs);
+
+        // Implicit conversions are allowed.
+        SafeNum(const BSONElement& element);
+        SafeNum(int num);
+        SafeNum(long long int num);
+        SafeNum(double num);
+        // TODO: add Paul's mutablebson::Element ctor
+
+        //
+        // comparison support
+        //
+
+        /**
+         * Returns true if the numeric quantity of 'rhs' and 'this' are the same. That is,
+         * an int32(10), an int64(10), and a double(10) are equivalent. An EOO-typed safe
+         * num is equivalent only to another EOO-typed instance. Otherwise, returns false.
+         */
+        bool isEquivalent(const SafeNum& rhs) const;
+        bool operator==(const SafeNum& rhs) const;
+        bool operator!=(const SafeNum& rhs) const;
+
+        /**
+         * Returns true if 'rsh' is equivalent to 'this' (see isEquivalent) _and_ both
+         * types are exactly the same. An EOO-typed safe num is never identical to
+         * anything else, even another EOO-typed instance. Otherwise, returns false.
+         */
+        bool isIdentical(const SafeNum& rhs) const;
+
+        //
+        // arithmetic support
+        //
+
+        /**
+         * Sums the 'rhs' -- right-hand side -- safe num with this, taking care of
+         * upconvertions and overflow (see class header).
+         */
+        SafeNum operator+(const SafeNum& rhs) const;
+        SafeNum& operator+=(const SafeNum& rhs);
+        // TODO other operations than sum
+
+        //
+        // output support
+        //
+
+        // TODO: output to builder
+        // TODO: output to Paul's class Element
+
+        //
+        // accessors
+        //
+
+        BSONType type() const { return _type; }
+        std::string debugString() const;
+
+        //
+        // Below exposed for testing purposes. Treat as private.
+        //
+
+        // Maximum integer that can be converted accuratelly into a double, assuming a
+        // double precission IEEE 754 representation.
+        // TODO use numeric_limits to make this portable
+        static const long long maxIntInDouble = 9007199254740992LL; // 2^53
+
+    private:
+        // One of the following: NumberInt, NumberLong, NumberDouble, or EOO.
+        BSONType _type;
+
+        // Value of the safe num. Indeterminate if _type is EOO.
+        union {
+            int int32Val;
+            long long int int64Val;
+            double doubleVal;
+        } _value;
+
+        /**
+         * Returns the sum of 'lhs' and 'rhs', taking into consideration their types. The
+         * type of the result would upcast, if necessary and permitted. Otherwise, returns
+         * an EOO-type instance.
+         */
+        static SafeNum addInternal(const SafeNum& lhs, const SafeNum& rhs);
+
+        /**
+         * Extracts the value of 'snum' in a long format. It assumes 'snum' is an NumberInt
+         * or a NumberDouble.
+         */
+        static long long getLongLong(const SafeNum& snum);
+
+        /**
+         * Extracts the value of 'snum' in a double format. It assumes 'snum' is a valid
+         * SafeNum, i.e., that _type is not EOO.
+         */
+        static double getDouble(const SafeNum& snum);
+    };
+
+    // Convenience method for unittest code. Please use accessors otherwise.
+    ostream& operator<<(ostream& os, const SafeNum& snum);
+
+} // namespace mongo
diff --git a/src/mongo/util/safe_num_test.cpp b/src/mongo/util/safe_num_test.cpp
new file mode 100644
index 00000000000..b8bdf5800ef
--- /dev/null
+++ b/src/mongo/util/safe_num_test.cpp
@@ -0,0 +1,179 @@
+/*    Copyright 2012 10gen Inc.
+ *
+ *    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.
+ */
+
+#include <limits>
+
+#include "mongo/pch.h" // for malloc/realloc/INFINITY pulled from bson
+
+#include "mongo/bson/bsontypes.h"
+#include "mongo/util/safe_num.h"
+#include "mongo/unittest/unittest.h"
+
+namespace {
+
+    using mongo::SafeNum;
+
+    TEST(Basics, Initialization) {
+        const SafeNum numInt(0);
+        ASSERT_EQUALS(numInt.type(), mongo::NumberInt);
+
+        const SafeNum numLong(0LL);
+        ASSERT_EQUALS(numLong.type(), mongo::NumberLong);
+
+        const SafeNum numDouble(0.0);
+        ASSERT_EQUALS(numDouble.type(), mongo::NumberDouble);
+    }
+
+    TEST(Comparison, EOO) {
+        const SafeNum safeNumA;
+        const SafeNum safeNumB;
+        ASSERT_EQUALS(safeNumA.type(), mongo::EOO);
+        ASSERT_EQUALS(safeNumB.type(), mongo::EOO);
+        ASSERT_TRUE(safeNumA.isEquivalent(safeNumB));
+        ASSERT_FALSE(safeNumA.isIdentical(safeNumB));
+
+        const SafeNum one(1);
+        ASSERT_NOT_EQUALS(one, safeNumA);
+    }
+
+    TEST(Comparison, StrictTypeComparison) {
+        const SafeNum one(1);
+        const SafeNum oneLong(1LL);
+        const SafeNum oneDouble(1.0);
+        ASSERT_FALSE(one.isIdentical(oneLong));
+        ASSERT_FALSE(oneLong.isIdentical(oneDouble));
+        ASSERT_FALSE(oneDouble.isIdentical(one));
+    }
+
+    TEST(Comparison, EquivalenceComparisonNormal) {
+        const SafeNum one(1);
+        const SafeNum oneLong(1LL);
+        const SafeNum oneDouble(1.0);
+        ASSERT_EQUALS(one, oneLong);
+        ASSERT_EQUALS(oneLong, oneDouble);
+        ASSERT_EQUALS(oneDouble, one);
+    }
+
+    TEST(Comparison, MaxIntInDouble) {
+        const SafeNum okToConvert(SafeNum::maxIntInDouble-1);
+        ASSERT_EQUALS(okToConvert, SafeNum(SafeNum::maxIntInDouble-1.0));
+
+        const SafeNum unsafeToConvert(SafeNum::maxIntInDouble + 100);
+        ASSERT_NOT_EQUALS(unsafeToConvert, SafeNum(SafeNum::maxIntInDouble+100.0));
+    }
+
+    TEST(Addition, Zero) {
+        const SafeNum zero(0);
+        ASSERT_EQUALS(zero + 0, zero);
+        ASSERT_EQUALS(zero + zero, zero);
+
+        const SafeNum minusOne(-1);
+        const SafeNum plusOne(1);
+        ASSERT_EQUALS(minusOne + 1, zero);
+        ASSERT_EQUALS(zero + -1, minusOne);
+        ASSERT_EQUALS(plusOne + -1, zero);
+        ASSERT_EQUALS(zero + 1, plusOne);
+    }
+
+    TEST(Addition, UpConvertion) {
+        const SafeNum zeroInt32(0);
+        const SafeNum zeroInt64(0LL);
+        const SafeNum zeroDouble(0.0);
+        ASSERT_EQUALS((zeroInt32 + zeroInt64).type(), mongo::NumberLong);
+        ASSERT_EQUALS((zeroInt64 + zeroInt32).type(), mongo::NumberLong);
+        ASSERT_EQUALS((zeroInt32 + zeroDouble).type(), mongo::NumberDouble);
+        ASSERT_EQUALS((zeroInt64 + zeroDouble).type(), mongo::NumberDouble);
+
+        const SafeNum stillInt32(zeroInt32 + zeroInt32);
+        const SafeNum stillInt64(zeroInt64 + zeroInt64);
+        const SafeNum stillDouble(zeroDouble + zeroDouble);
+        ASSERT_EQUALS(stillInt32.type(), mongo::NumberInt);
+        ASSERT_EQUALS(stillInt64.type(), mongo::NumberLong);
+        ASSERT_EQUALS(stillDouble.type(), mongo::NumberDouble);
+    }
+
+    TEST(Addition, Overflow32to64) {
+        const SafeNum maxInt32(std::numeric_limits<int>::max());
+        ASSERT_EQUALS(maxInt32.type(), mongo::NumberInt);
+
+        const SafeNum int32PlusOne(maxInt32 + 1);
+        ASSERT_EQUALS(int32PlusOne.type(), mongo::NumberLong);
+
+        const SafeNum int32MinusOne(maxInt32 + -1);
+        ASSERT_EQUALS(int32MinusOne.type(), mongo::NumberInt);
+
+        const SafeNum longResult(std::numeric_limits<int>::max() + static_cast<long long>(1));
+        ASSERT_EQUALS(int32PlusOne, longResult);
+    }
+
+    TEST(Addition, Overflow64toDouble) {
+        const SafeNum maxInt64(std::numeric_limits<long long>::max());
+        ASSERT_EQUALS(maxInt64.type(), mongo::NumberLong);
+
+        // We don't overflow int64 to double.
+        const SafeNum int64PlusOne(maxInt64 + 1);
+        ASSERT_EQUALS(int64PlusOne.type(), mongo::EOO);
+
+        const SafeNum int64MinusOne(maxInt64 + -1);
+        ASSERT_EQUALS(int64MinusOne.type(), mongo::NumberLong);
+
+        const SafeNum doubleResult(std::numeric_limits<long long>::max()+static_cast<double>(1));
+        ASSERT_EQUALS(doubleResult.type(), mongo::NumberDouble);
+        ASSERT_NOT_EQUALS(int64PlusOne, doubleResult);
+    }
+
+    TEST(Addition, OverflowDouble) {
+        const SafeNum maxDouble(std::numeric_limits<double>::max());
+        ASSERT_EQUALS(maxDouble.type(), mongo::NumberDouble);
+
+        // can't just add one here, as max double is so sparse max == max+1
+        const SafeNum doublePlusMax(maxDouble + maxDouble);
+        ASSERT_EQUALS(doublePlusMax.type(), mongo::NumberDouble);
+
+        const SafeNum infinity(INFINITY);
+        ASSERT_EQUALS(doublePlusMax, infinity);
+    }
+
+    TEST(Addition, Negative32to64) {
+        const SafeNum minInt32(std::numeric_limits<int>::min());
+        ASSERT_EQUALS(minInt32.type(), mongo::NumberInt);
+
+        const SafeNum int32MinusOne(minInt32 + -1);
+        ASSERT_EQUALS(int32MinusOne.type(), mongo::NumberLong);
+
+        const SafeNum int32PlusOne(minInt32 + 1);
+        ASSERT_EQUALS(int32PlusOne.type(), mongo::NumberInt);
+
+        const SafeNum longResult(std::numeric_limits<int>::min()-static_cast<long long>(1));
+        ASSERT_EQUALS(int32MinusOne, longResult);
+    }
+
+    TEST(Addition, Negative64toDouble) {
+        const SafeNum minInt64(std::numeric_limits<long long>::min());
+        ASSERT_EQUALS(minInt64.type(), mongo::NumberLong);
+
+        // We don't overflow int64 to double.
+        const SafeNum int64MinusOne(minInt64 + -1);
+        ASSERT_EQUALS(int64MinusOne.type(), mongo::EOO);
+
+        const SafeNum int64PlusOne(minInt64 + 1);
+        ASSERT_EQUALS(int64PlusOne.type(), mongo::NumberLong);
+
+        const SafeNum doubleResult(std::numeric_limits<long long>::min()-static_cast<double>(1));
+        ASSERT_EQUALS(doubleResult.type(), mongo::NumberDouble);
+        ASSERT_NOT_EQUALS(int64MinusOne, doubleResult);
+    }
+
+} // unnamed namespace