Make BSONObj::woCompare a total ordering

Changes:
* Date and Timestamp are now distinct with all Dates before all Timestamps.
* Numeric comparisons now correctly handle Doubles and Long > 2**53.
* CodeWScope doesn't strcmp BSONObjs or strings which may contain NULs.

There should be no changes in any of the cases where woCompare defined a
correct total ordering before. The new behavior matches the ordering defined
by KeyString.

Related tickets:
* SERVER-3304 Error comparing Date and Timestamp
* SERVER-3719 Total ordering over Longs and Doubles
* SERVER-7804 CodeWScope comparisons are broken
* SERVER-16632 Change WiredTiger index key format

Changes to the comparison function for aggregation will be handled separately
as SERVER-16708.

1 files changed, 138 insertions, 1 deletions

diff --git a/src/mongo/bson/bson_obj_test.cpp b/src/mongo/bson/bson_obj_test.cpp
index 88d866f531a..1ee6dc743f9 100644
--- a/src/mongo/bson/bson_obj_test.cpp
+++ b/src/mongo/bson/bson_obj_test.cpp
@@ -32,11 +32,148 @@
 
 namespace {
 
-    TEST(ToString, EmptyArray) {
+    TEST(BSONObjToString, EmptyArray) {
         const char text[] = "{ x: [] }";
         mongo::BSONObj o1 = mongo::fromjson(text);
         const std::string o1_str = o1.toString();
         ASSERT_EQUALS(text, o1_str);
     }
 
+    TEST(BSONObjCompare, NumberDouble) {
+        ASSERT_LT(BSON("" << 0.0), BSON("" << 1.0));
+        ASSERT_LT(BSON("" << -1.0), BSON("" << 0.0));
+        ASSERT_LT(BSON("" << -1.0), BSON("" << 1.0));
+
+        ASSERT_LT(BSON("" << 0.0), BSON("" << 0.1));
+        ASSERT_LT(BSON("" << 0.1), BSON("" << 1.0));
+        ASSERT_LT(BSON("" << -1.0), BSON("" << -0.1));
+        ASSERT_LT(BSON("" << -0.1), BSON("" << 0.0));
+        ASSERT_LT(BSON("" << -0.1), BSON("" << 0.1));
+
+        ASSERT_LT(BSON("" << 0.0), BSON("" << std::numeric_limits<double>::denorm_min()));
+        ASSERT_GT(BSON("" << 0.0), BSON("" << -std::numeric_limits<double>::denorm_min()));
+
+        ASSERT_EQ(BSON("" << 0.0), BSON("" << -0.0));
+
+        ASSERT_GT(BSON("" << std::numeric_limits<double>::infinity()), BSON("" << 0.0));
+        ASSERT_GT(BSON("" << std::numeric_limits<double>::infinity()),
+                  BSON("" << std::numeric_limits<double>::max())); // max is finite
+        ASSERT_GT(BSON("" << std::numeric_limits<double>::infinity()),
+                  BSON("" << -std::numeric_limits<double>::infinity()));
+
+        ASSERT_LT(BSON("" << -std::numeric_limits<double>::infinity()), BSON("" << 0.0));
+        ASSERT_LT(BSON("" << -std::numeric_limits<double>::infinity()),
+                  BSON("" << std::numeric_limits<double>::min())); // min is finite
+        ASSERT_LT(BSON("" << -std::numeric_limits<double>::infinity()),
+                  BSON("" << std::numeric_limits<double>::infinity()));
+
+        ASSERT_LT(BSON("" << std::numeric_limits<double>::quiet_NaN()), BSON("" << 0.0));
+        ASSERT_LT(BSON("" << std::numeric_limits<double>::quiet_NaN()),
+                  BSON("" << std::numeric_limits<double>::min()));
+        ASSERT_LT(BSON("" << std::numeric_limits<double>::quiet_NaN()),
+                  BSON("" << std::numeric_limits<double>::infinity()));
+        ASSERT_LT(BSON("" << std::numeric_limits<double>::quiet_NaN()),
+                  BSON("" << -std::numeric_limits<double>::infinity()));
+
+        // TODO in C++11 use hex floating point to test distinct NaN representations
+        ASSERT_EQ(BSON("" << std::numeric_limits<double>::quiet_NaN()),
+                  BSON("" << std::numeric_limits<double>::signaling_NaN()));
+    }
+
+    TEST(BSONObjCompare, NumberLong_Double) {
+        ASSERT_EQ(BSON("" << 0ll), BSON("" << 0.0));
+        ASSERT_EQ(BSON("" << 0ll), BSON("" << -0.0));
+
+        ASSERT_EQ(BSON("" << 1ll), BSON("" << 1.0));
+        ASSERT_EQ(BSON("" << -1ll), BSON("" << -1.0));
+
+        ASSERT_LT(BSON("" << 0ll), BSON("" << 1.0));
+        ASSERT_LT(BSON("" << -1ll), BSON("" << 0.0));
+        ASSERT_LT(BSON("" << -1ll), BSON("" << 1.0));
+
+        ASSERT_LT(BSON("" << 0ll), BSON("" << 0.1));
+        ASSERT_LT(BSON("" << 0.1), BSON("" << 1ll));
+        ASSERT_LT(BSON("" << -1ll), BSON("" << -0.1));
+        ASSERT_LT(BSON("" << -0.1), BSON("" << 0ll));
+
+        ASSERT_LT(BSON("" << 0ll), BSON("" << std::numeric_limits<double>::denorm_min()));
+        ASSERT_GT(BSON("" << 0ll), BSON("" << -std::numeric_limits<double>::denorm_min()));
+
+        ASSERT_GT(BSON("" << std::numeric_limits<double>::infinity()), BSON("" << 0ll));
+        ASSERT_GT(BSON("" << std::numeric_limits<double>::infinity()),
+                  BSON("" << std::numeric_limits<long long>::max()));
+        ASSERT_GT(BSON("" << std::numeric_limits<double>::infinity()),
+                  BSON("" << std::numeric_limits<long long>::min()));
+
+        ASSERT_LT(BSON("" << -std::numeric_limits<double>::infinity()), BSON("" << 0ll));
+        ASSERT_LT(BSON("" << -std::numeric_limits<double>::infinity()),
+                  BSON("" << std::numeric_limits<long long>::max()));
+        ASSERT_LT(BSON("" << -std::numeric_limits<double>::infinity()),
+                  BSON("" << std::numeric_limits<long long>::min()));
+
+        ASSERT_LT(BSON("" << std::numeric_limits<double>::quiet_NaN()), BSON("" << 0ll));
+        ASSERT_LT(BSON("" << std::numeric_limits<double>::quiet_NaN()),
+                  BSON("" << std::numeric_limits<long long>::min()));
+
+        for (int powerOfTwo = 0; powerOfTwo < 63; powerOfTwo++) {
+            const long long lNum = 1ll << powerOfTwo;
+            const double dNum = double(lNum);
+
+            // All powers of two in this range can be represented exactly as doubles.
+            invariant(lNum == static_cast<long long>(dNum));
+
+            ASSERT_EQ(BSON("" << lNum), BSON("" << dNum));
+            ASSERT_EQ(BSON("" << -lNum), BSON("" << -dNum));
+
+            ASSERT_GT(BSON("" << (lNum + 1)), BSON("" << dNum));
+            ASSERT_LT(BSON("" << (lNum - 1)), BSON("" << dNum));
+            ASSERT_GT(BSON("" << (-lNum + 1)), BSON("" << -dNum));
+            ASSERT_LT(BSON("" << (-lNum - 1)), BSON("" << -dNum));
+
+            if (powerOfTwo <= 52) { // is dNum - 0.5 representable?
+                ASSERT_GT(BSON("" << lNum), BSON("" << (dNum - 0.5)));
+                ASSERT_LT(BSON("" << -lNum), BSON("" << -(dNum - 0.5)));
+            }
+
+            if (powerOfTwo <= 51) { // is dNum + 0.5 representable?
+                ASSERT_LT(BSON("" << lNum), BSON("" << (dNum + 0.5)));
+                ASSERT_GT(BSON("" << -lNum), BSON("" << -(dNum + 0.5)));
+            }
+        }
+
+        {
+            // Numbers around +/- numeric_limits<long long>::max() which can't be represented
+            // precisely as a double.
+            const long long maxLL = std::numeric_limits<long long>::max();
+            const double closestAbove = 9223372036854775808.0; // 2**63
+            const double closestBelow = 9223372036854774784.0; // 2**63 - epsilon
+
+            ASSERT_GT(BSON("" << maxLL), BSON("" << (maxLL - 1)));
+            ASSERT_LT(BSON("" << maxLL), BSON("" << closestAbove));
+            ASSERT_GT(BSON("" << maxLL), BSON("" << closestBelow));
+
+            ASSERT_LT(BSON("" << -maxLL), BSON("" << -(maxLL - 1)));
+            ASSERT_GT(BSON("" << -maxLL), BSON("" << -closestAbove));
+            ASSERT_LT(BSON("" << -maxLL), BSON("" << -closestBelow));
+        }
+
+        {
+            // Numbers around numeric_limits<long long>::min() which can be represented precisely as
+            // a double, but not as a positive long long.
+            const long long minLL = std::numeric_limits<long long>::min();
+            const double closestBelow = -9223372036854777856.0; // -2**63 - epsilon
+            const double equal = -9223372036854775808.0; // 2**63
+            const double closestAbove = 9223372036854774784.0; // -2**63 + epsilon
+
+            invariant(static_cast<double>(minLL) == equal);
+            invariant(static_cast<long long>(equal) == minLL);
+
+            ASSERT_LT(BSON("" << minLL), BSON("" << (minLL + 1)));
+
+            ASSERT_EQ(BSON("" << minLL), BSON("" << equal));
+            ASSERT_LT(BSON("" << minLL), BSON("" << closestAbove));
+            ASSERT_GT(BSON("" << minLL), BSON("" << closestBelow));
+        }
+    }
+
 } // unnamed namespace