SERVER-8046 Fix broken mutable bson algorithm

5 files changed, 133 insertions, 28 deletions

diff --git a/src/mongo/bson/mutable/algorithm.h b/src/mongo/bson/mutable/algorithm.h
index c11158053b4..4b3e993a0c4 100644
--- a/src/mongo/bson/mutable/algorithm.h
+++ b/src/mongo/bson/mutable/algorithm.h
@@ -131,8 +131,8 @@ namespace mutablebson {
     template<typename ElementType>
     ElementType getNthSibling(ElementType element, int n) {
         return (n < 0) ?
-            advanceToNthLeftSibling(element, n) :
-            advanceToNthRightSibling(element, n);
+            getNthLeftSibling(element, -n) :
+            getNthRightSibling(element, n);
     }
 
     /** Get the child that is 'n' Elements to the right of 'element's left child. */
diff --git a/src/mongo/bson/mutable/mutable_bson_algo_test.cpp b/src/mongo/bson/mutable/mutable_bson_algo_test.cpp
index 5872a7d7981..5fe293baa6e 100644
--- a/src/mongo/bson/mutable/mutable_bson_algo_test.cpp
+++ b/src/mongo/bson/mutable/mutable_bson_algo_test.cpp
@@ -18,6 +18,7 @@
 #include "mongo/bson/mutable/algorithm.h"
 
 #include "mongo/bson/mutable/document.h"
+#include "mongo/bson/mutable/mutable_bson_test_utils.h"
 #include "mongo/platform/basic.h"
 #include "mongo/unittest/unittest.h"
 
@@ -204,4 +205,57 @@ namespace {
         ASSERT_EQUALS(countChildren(threeChildren), 3u);
     }
 
+    TEST_F(ManyChildrenTest, getNthSibling) {
+        const Element leftChild = doc().root().leftChild();
+        ASSERT_TRUE(leftChild.ok());
+        const Element rightChild = doc().root().rightChild();
+        ASSERT_TRUE(rightChild.ok());
+
+        // Check that moving zero is a no-op
+        Element zeroAway = getNthSibling(leftChild, 0);
+        ASSERT_TRUE(zeroAway.ok());
+        ASSERT_EQUALS(leftChild, zeroAway);
+        zeroAway = getNthSibling(rightChild, 0);
+        ASSERT_TRUE(zeroAway.ok());
+        ASSERT_EQUALS(rightChild, zeroAway);
+
+        // Check that moving left of leftmost gets a not-ok element.
+        Element badLeft = getNthSibling(leftChild, -1);
+        ASSERT_FALSE(badLeft.ok());
+
+        // Check that moving right of rightmost gets a non-ok element.
+        Element badRight = getNthSibling(rightChild, 1);
+        ASSERT_FALSE(badRight.ok());
+
+        // Check that the moving one right from leftmost gets us the expected element.
+        Element target = leftChild.rightSibling();
+        ASSERT_TRUE(target.ok());
+        Element query = getNthSibling(leftChild, 1);
+        ASSERT_TRUE(target.ok());
+        ASSERT_EQUALS(target, query);
+
+        // And the same from the other side
+        target = rightChild.leftSibling();
+        ASSERT_TRUE(target.ok());
+        query = getNthSibling(rightChild, -1);
+        ASSERT_TRUE(target.ok());
+        ASSERT_EQUALS(target, query);
+
+        // Ensure that walking more chidren than we have gets us past the end
+        const int children = countChildren(doc().root());
+        query = getNthSibling(leftChild, children);
+        ASSERT_FALSE(query.ok());
+        query = getNthSibling(rightChild, -children);
+        ASSERT_FALSE(query.ok());
+
+        // Ensure that walking all the children in either direction gets
+        // us to the other right/left child.
+        query = getNthSibling(leftChild, children - 1);
+        ASSERT_TRUE(query.ok());
+        ASSERT_EQUALS(rightChild, query);
+        query = getNthSibling(rightChild, -(children - 1));
+        ASSERT_TRUE(query.ok());
+        ASSERT_EQUALS(leftChild, query);
+    }
+
 } // namespace
diff --git a/src/mongo/bson/mutable/mutable_bson_test.cpp b/src/mongo/bson/mutable/mutable_bson_test.cpp
index 16861f8a86b..cff5b999be3 100644
--- a/src/mongo/bson/mutable/mutable_bson_test.cpp
+++ b/src/mongo/bson/mutable/mutable_bson_test.cpp
@@ -20,38 +20,13 @@
 #include "mongo/base/status.h"
 #include "mongo/bson/bsonobj.h"
 #include "mongo/bson/mutable/algorithm.h"
+#include "mongo/bson/mutable/mutable_bson_test_utils.h"
 #include "mongo/db/json.h"
 #include "mongo/unittest/unittest.h"
 #include "mongo/util/timer.h"
 
 #include "mongo/client/dbclientinterface.h"
 
-namespace mongo {
-namespace mutablebson {
-
-    // TODO: Move to a utility or testing utility header.
-    std::ostream& operator<<(std::ostream& stream, const ConstElement& elt) {
-        stream << "Element("<< static_cast<const void*>(&elt.getDocument()) << ", ";
-        if (elt.ok())
-            stream << elt.getIdx();
-        else
-            stream << "kInvalidIndex";
-        stream << ")";
-
-        if (elt.ok()) {
-            stream << " of type '" << typeName(elt.getType()) << "'";
-            if (elt.hasValue())
-                stream << " with accessible value '" << elt.getValue() << "'";
-            else
-                stream << " with no accessible value";
-        }
-
-        return stream;
-    }
-
-} // namespace mutablebson
-} // namespace mongo
-
 namespace {
 
     namespace mmb = mongo::mutablebson;
diff --git a/src/mongo/bson/mutable/mutable_bson_test_utils.cpp b/src/mongo/bson/mutable/mutable_bson_test_utils.cpp
new file mode 100644
index 00000000000..65306db5de1
--- /dev/null
+++ b/src/mongo/bson/mutable/mutable_bson_test_utils.cpp
@@ -0,0 +1,47 @@
+/* Copyright 2013 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 "mongo/platform/basic.h"
+
+#include "mongo/bson/mutable/mutable_bson_test_utils.h"
+
+#include <ostream>
+
+#include "mongo/bson/mutable/const_element.h"
+
+namespace mongo {
+namespace mutablebson {
+
+    std::ostream& operator<<(std::ostream& stream, const ConstElement& elt) {
+        stream << "Element("<< static_cast<const void*>(&elt.getDocument()) << ", ";
+        if (elt.ok())
+            stream << elt.getIdx();
+        else
+            stream << "kInvalidIndex";
+        stream << ")";
+
+        if (elt.ok()) {
+            stream << " of type '" << typeName(elt.getType()) << "'";
+            if (elt.hasValue())
+                stream << " with accessible value '" << elt.getValue() << "'";
+            else
+                stream << " with no accessible value";
+        }
+
+        return stream;
+    }
+
+} // namespace mutablebson
+} // namespace mongo
diff --git a/src/mongo/bson/mutable/mutable_bson_test_utils.h b/src/mongo/bson/mutable/mutable_bson_test_utils.h
new file mode 100644
index 00000000000..603026353fd
--- /dev/null
+++ b/src/mongo/bson/mutable/mutable_bson_test_utils.h
@@ -0,0 +1,29 @@
+/* Copyright 2013 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 <iosfwd>
+
+namespace mongo {
+namespace mutablebson {
+
+    // Utilities for mutable BSON unit tests.
+
+    class ConstElement;
+
+    // Stream out an element; useful within ASSERT calls.
+    std::ostream& operator<<(std::ostream& stream, const ConstElement& elt);
+
+} // namespace mutablebson
+} // namespace mongo