Imported Upstream version 2.6.11upstream/2.6.11

1 files changed, 241 insertions, 0 deletions

diff --git a/src/mongo/db/exec/sort_test.cpp b/src/mongo/db/exec/sort_test.cpp
new file mode 100644
index 00000000000..c890fb4dd15
--- /dev/null
+++ b/src/mongo/db/exec/sort_test.cpp
@@ -0,0 +1,241 @@
+/**
+ *    Copyright (C) 2013 mongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+/**
+ * This file contains tests for mongo/db/exec/sort.cpp
+ */
+
+#include "mongo/db/exec/sort.h"
+
+#include "mongo/db/json.h"
+#include "mongo/db/exec/mock_stage.h"
+#include "mongo/unittest/unittest.h"
+
+using namespace mongo;
+
+namespace {
+
+
+    TEST(SortStageTest, SortEmptyWorkingSet) {
+        WorkingSet ws;
+
+        // MockStage will be owned by SortStage.
+        MockStage* ms = new MockStage(&ws);
+        SortStageParams params;
+        SortStage sort(params, &ws, ms);
+
+        // Check initial EOF state.
+        ASSERT_TRUE(ms->isEOF());
+        ASSERT_FALSE(sort.isEOF());
+
+        // First call to work() initializes sort key generator.
+        WorkingSetID id = WorkingSet::INVALID_ID;
+        PlanStage::StageState state = sort.work(&id);
+        ASSERT_EQUALS(state, PlanStage::NEED_TIME);
+
+        // Second call to work() sorts data in vector.
+        state = sort.work(&id);
+        ASSERT_EQUALS(state, PlanStage::NEED_TIME);
+
+        // Finally we hit EOF.
+        state = sort.work(&id);
+        ASSERT_EQUALS(state, PlanStage::IS_EOF);
+
+        ASSERT_TRUE(sort.isEOF());
+    }
+
+    /**
+     * Test function to verify sort stage.
+     * SortStageParams will be initialized using patternStr, queryStr and limit.
+     * inputStr represents the input data set in a BSONObj.
+     *     {input: [doc1, doc2, doc3, ...]}
+     * expectedStr represents the expected sorted data set.
+     *     {output: [docA, docB, docC, ...]}
+     */
+    void testWork(const char* patternStr, const char* queryStr, int limit,
+                  const char* inputStr, const char* expectedStr) {
+
+        // WorkingSet is not owned by stages
+        // so it's fine to declare
+        WorkingSet ws;
+
+        // MockStage will be owned by SortStage.
+        MockStage* ms = new MockStage(&ws);
+        BSONObj inputObj = fromjson(inputStr);
+        BSONElement inputElt = inputObj.getField("input");
+        ASSERT(inputElt.isABSONObj());
+        BSONObjIterator inputIt(inputElt.embeddedObject());
+        while (inputIt.more()) {
+            BSONElement elt = inputIt.next();
+            ASSERT(elt.isABSONObj());
+            BSONObj obj = elt.embeddedObject();
+
+            // Insert obj from input array into working set.
+            WorkingSetMember wsm;
+            wsm.state = WorkingSetMember::OWNED_OBJ;
+            wsm.obj = obj;
+            ms->pushBack(wsm);
+        }
+
+        // Initialize SortStageParams
+        // Setting limit to 0 means no limit
+        SortStageParams params;
+        params.pattern = fromjson(patternStr);
+        params.query = fromjson(queryStr);
+        params.limit = limit;
+
+        SortStage sort(params, &ws, ms);
+
+        WorkingSetID id = WorkingSet::INVALID_ID;
+        PlanStage::StageState state = PlanStage::NEED_TIME;
+
+        // Keep working sort stage until data is available.
+        while (state == PlanStage::NEED_TIME) {
+            state = sort.work(&id);
+        }
+
+        // Child's state should be EOF when sort is ready to advance.
+        ASSERT_TRUE(ms->isEOF());
+
+        // While there's data to be retrieved, state should be equal to ADVANCED.
+        // Insert documents into BSON document in this format:
+        //     {output: [docA, docB, docC, ...]}
+        BSONObjBuilder bob;
+        BSONArrayBuilder arr(bob.subarrayStart("output"));
+        while (state == PlanStage::ADVANCED) {
+            WorkingSetMember* member = ws.get(id);
+            const BSONObj& obj = member->obj;
+            arr.append(obj);
+            state = sort.work(&id);
+        }
+        arr.doneFast();
+        BSONObj outputObj = bob.obj();
+
+        // Sort stage should be EOF after data is retrieved.
+        ASSERT_EQUALS(state, PlanStage::IS_EOF);
+        ASSERT_TRUE(sort.isEOF());
+
+        // Finally, we get to compare the sorted results against what we expect.
+        BSONObj expectedObj = fromjson(expectedStr);
+        if (outputObj != expectedObj) {
+            mongoutils::str::stream ss;
+            // Even though we have the original string representation of the expected output,
+            // we invoke BSONObj::toString() to get a format consistent with outputObj.
+            ss << "Unexpected sort result with query=" << queryStr << "; pattern=" << patternStr
+               << "; limit=" << limit << ":\n"
+               << "Expected: " << expectedObj.toString() << "\n"
+               << "Actual:   " << outputObj.toString() << "\n";
+            FAIL(ss);
+        }
+    }
+
+    //
+    // Limit values
+    // The server interprets limit values from the user as follows:
+    //     0: no limit on query results. This is passed along unchanged to the sort stage.
+    //     >0: soft limit. Also unchanged in sort stage.
+    //     <0: hard limit. Absolute value is stored in parsed query and passed to sort stage.
+    // The sort stage treats both soft and hard limits in the same manner
+
+    //
+    // Sort without limit
+    // Implementation should keep all items fetched from child.
+    //
+
+    TEST(SortStageTest, SortAscending) {
+        testWork("{a: 1}", "{}", 0,
+                 "{input: [{a: 2}, {a: 1}, {a: 3}]}",
+                 "{output: [{a: 1}, {a: 2}, {a: 3}]}");
+    }
+
+    TEST(SortStageTest, SortDescending) {
+        testWork("{a: -1}", "{}", 0,
+                 "{input: [{a: 2}, {a: 1}, {a: 3}]}",
+                 "{output: [{a: 3}, {a: 2}, {a: 1}]}");
+    }
+
+    TEST(SortStageTest, SortIrrelevantSortKey) {
+        testWork("{b: 1}", "{}", 0,
+                 "{input: [{a: 2}, {a: 1}, {a: 3}]}",
+                 "{output: [{a: 2}, {a: 1}, {a: 3}]}");
+    }
+
+    //
+    // Sorting with limit > 1
+    // Implementation should retain top N items
+    // and discard the rest.
+    //
+
+    TEST(SortStageTest, SortAscendingWithLimit) {
+        testWork("{a: 1}", "{}", 2,
+                 "{input: [{a: 2}, {a: 1}, {a: 3}]}",
+                 "{output: [{a: 1}, {a: 2}]}");
+    }
+
+    TEST(SortStageTest, SortDescendingWithLimit) {
+        testWork("{a: -1}", "{}", 2,
+                 "{input: [{a: 2}, {a: 1}, {a: 3}]}",
+                 "{output: [{a: 3}, {a: 2}]}");
+    }
+
+    //
+    // Sorting with limit > size of data set
+    // Implementation should retain top N items
+    // and discard the rest.
+    //
+
+    TEST(SortStageTest, SortAscendingWithLimitGreaterThanInputSize) {
+        testWork("{a: 1}", "{}", 10,
+                 "{input: [{a: 2}, {a: 1}, {a: 3}]}",
+                 "{output: [{a: 1}, {a: 2}, {a: 3}]}");
+    }
+
+    TEST(SortStageTest, SortDescendingWithLimitGreaterThanInputSize) {
+        testWork("{a: -1}", "{}", 10,
+                 "{input: [{a: 2}, {a: 1}, {a: 3}]}",
+                 "{output: [{a: 3}, {a: 2}, {a: 1}]}");
+    }
+
+    //
+    // Sorting with limit 1
+    // Implementation should optimize this into a running maximum.
+    //
+
+    TEST(SortStageTest, SortAscendingWithLimitOfOne) {
+        testWork("{a: 1}", "{}", 1,
+                 "{input: [{a: 2}, {a: 1}, {a: 3}]}",
+                 "{output: [{a: 1}]}");
+    }
+
+    TEST(SortStageTest, SortDescendingWithLimitOfOne) {
+        testWork("{a: -1}", "{}", 1,
+                 "{input: [{a: 2}, {a: 1}, {a: 3}]}",
+                 "{output: [{a: 3}]}");
+    }
+
+}  // namespace