SERVER-18579: Clang-Format - reformat code, no comment reflow

1 files changed, 2342 insertions, 2399 deletions

diff --git a/src/mongo/bson/mutable/document.cpp b/src/mongo/bson/mutable/document.cpp
index ddff3e694f2..c03b4d197f3 100644
--- a/src/mongo/bson/mutable/document.cpp
+++ b/src/mongo/bson/mutable/document.cpp
@@ -42,2528 +42,2475 @@
 namespace mongo {
 namespace mutablebson {
 
-    /** Mutable BSON Implementation Overview
-     *
-     *  If you haven't read it already, please read the 'Mutable BSON Overview' comment in
-     *  document.h before reading further.
-     *
-     *  In the following discussion, the capitalized terms 'Element' and 'Document' refer to
-     *  the classes of the same name. At times, it is also necessary to refer to abstract
-     *  'elements' or 'documents', in the sense of bsonspec.org. These latter uses are
-     *  non-capitalized. In the BSON specification, there are two 'classes' of
-     *  elements. 'Primitive' or 'leaf' elements are those elements which do not contain other
-     *  elements. In practice, all BSON types except 'Array' and 'Object' are primitives. The
-     *  CodeWScope type is an exception, but one that we sidestep by considering its BSONObj
-     *  payload to be opaque.
-     *
-     *  A mutable BSON Document and its component Elements are implemented in terms of four
-     *  data structures. These structures are owned by a Document::Impl object. Each Document
-     *  owns a unique Document::Impl, which owns the relevant data structures and provides
-     *  accessors, mutators, and helper methods related to those data structures. Understanding
-     *  these data structures is critical for understanding how the system as a whole operates.
-     *
-     *  - The 'Elements Vector': This is a std::vector<ElementRep>, where 'ElementRep' is a
-     *    structure type defined below that contains the detailed information about an entity
-     *    in the Document (e.g. an Object, or an Array, or a NumberLong, etc.). The 'Element'
-     *    and 'ConstElement' objects contain a pointer to a Document (which allows us to reach
-     *    the Document::Impl for the Document), and an index into the Elements Vector in the
-     *    Document::Impl. These two pieces of information make it possible for us to obtain the
-     *    ElementRep associated with a given Element. Note that the Elements Vector is append
-     *    only: ElementReps are never removed from it, even if the cooresponding Element is
-     *    removed from the Document. By never removing ElementReps, and by using indexes into
-     *    the Elements Vector, we can ensure that Elements are never invalidated. Note that
-     *    every Document comes with an automatically provided 'root' element of mongo::Object
-     *    type. The ElementRep for the root is always in the first slot (index zero) of the
-     *    Elements Vector.
-     *
-     *  - The 'Leaf Builder': This is a standard BSONObjBuilder. When a request is made to the
-     *    Document to add new data to the Document via one of the Document::makeElement[TYPE]
-     *    calls, the element is constructed by invoking the appropriate method on the Leaf
-     *    Builder, forwarding the arguments provided to the call on Document. This results in a
-     *    contiguous region of memory which encodes this element, capturing its field name, its
-     *    type, and the bytes that encode its value, in the same way it normally does when
-     *    using BSONObjBuilder. We then build an ElementRep that indexes into the BufBuilder
-     *    behind the BSONObjBuilder (more on how this happens below, in the section on the
-     *    'Objects Vector'), then insert that new ElementRep into the ElementsVector, and
-     *    finally return an Element that dereferences to the new ElementRep. Subsequently,
-     *    requests for the type, fieldname or value bytes via the Element are satisfied by
-     *    obtaining the contiguous memory region for the element, which may be used to
-     *    construct a BSONElement over that memory region.
-     *
-     *  - The 'Objects Vector': This is a std::vector<BSONObj>. Any BSONObj object that
-     *    provides values for parts of the Document is stored in the Objects Vector. For
-     *    instance, in 'Example 2' from document.h, the Document we construct wraps an existing
-     *    BSONObj, which is passed in to the Document constructor. That BSONObj would be stored
-     *    in the Objects Vector. The data content of the BSONObj is not copied, but the BSONObj
-     *    is copied, so the if the BSONObj is counted, we will up its refcount. In any event
-     *    the lifetime of the BSONObj must exceed our lifetime by some mechanism. ElementReps
-     *    that represent the component elements of the BSONObj store the index of their
-     *    supporting BSONObj into the 'objIdx' field of ElementRep. Later, when Elements
-     *    referring to those ElementReps are asked for properties like the field name or type
-     *    of the Element, the underlying memory region in the appropriate BSONObj may be
-     *    examined to provide the relevant data.
-     *
-     *  - The 'Field Name Heap': For some elements, particularly those in the Leaf Builder or
-     *    those embedded in a BSONObj in the Objects Vector, we can easily obtain the field
-     *    name by reading it from the encoded BSON. However, some elements are not so
-     *    fortunate. Newly created elements of mongo::Array or mongo::Object type, for
-     *    instance, don't have a memory region that provides values. In such cases, the field
-     *    name is stored in the field name heap, which is simply std::vector<char>, where the
-     *    field names are null-byte-delimited. ElementsReps for such elements store an offset
-     *    into the Field Name Heap, and when asked for their field name simply return a pointer
-     *    to the string data the offset identifies. This exploits the fact that in BSON, valid
-     *    field names are null terinated and do not contain embedded null bytes.
-     *
-     *  - The 'root' Element. Each Document contains a well known Element, which always refers
-     *    to a pre-constructed ElementRep at offset zero in the Elements Vector. This is an
-     *    Object element, and it is considered as the root of the document tree. It is possible
-     *    for ElementReps to exist in the Document data structures, but not be in a child
-     *    relationship to the root Element. Newly created Elements, for instance, are in this
-     *    sort of 'detached' state until they are attched to another element. Only Element's
-     *    that are children of the root element are traversed when calling top level
-     *    serialization or comparision operations on Document.
-     *
-     *  When you construct a Document that obtains its values from an underlying BSONObj, the
-     *  entire BSONObj is not 'unpacked' into ElementReps at Document construction
-     *  time. Instead, as you ask for Elements with the Element navigation API, the Elements
-     *  for children and siblings are created on demand. Subobjects which are never visited
-     *  will never have ElementReps constructed for them. Similarly, when writing a Document
-     *  back out to a builder, regions of memory that provide values for the Document and which
-     *  have not been modified will be block copied, instead of being recursively explored and
-     *  written.
-     *
-     *  To see how these data structures interoperate, we will walk through an example. You may
-     *  want to read the comments for ElementRep before tackling the example, since we will
-     *  refer to the internal state of ElementRep here. The example code used here exists as a
-     *  unit test in mutable_bson_test.cpp as (Documentation, Example3).
-     *
-     *
-     *  Legend:
-     *   oi   : objIdx
-     *   +/-  : bitfield state (s: serialized, a: array)
-     *   x    : invalid/empty rep idx
-     *   ?    : opaque rep idx
-     *   ls/rs: left/right sibling
-     *   lc/rc: left/right child
-     *   p    : parent
-
-        static const char inJson[] =
-            "{"
-            "  'xs': { 'x' : 'x', 'X' : 'X' },"
-            "  'ys': { 'y' : 'y' }"
-            "}";
-        mongo::BSONObj inObj = mongo::fromjson(inJson);
-        mmb::Document doc(inObj);
-
-     *    _elements
-     *      oi      flags                offset                  ls  rs  lc  rc  p
-     *    +-----------------------------------------------------------------------------+
-     *  0 | 1 | s:- | ...       | off 0       into _fieldNames | x | x | ? | ? | x      |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _objects
-     *    +-----------------------------------------------------------------------------+
-     *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _fieldNames
-     *    +-----------------------------------------------------------------------------+
-     *    | \0                                                                          |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _leafBuf
-     *    +-----------------------------------------------------------------------------+
-     *    | {}                                                                          |
-     *    +-----------------------------------------------------------------------------+
-
-
-        mmb::Element root = doc.root();
-        mmb::Element xs = root.leftChild();
-
-     *    _elements
-     *      oi      flags                offset                  ls  rs  lc  rc  p
-     *    +-----------------------------------------------------------------------------+
-     *  0 | 1 | s:- | ...       | off 0       into _fieldNames | x | x | 1 | ? | x      | *
-     *  1 | 1 | s:+ | ...       | off of 'xs' into _objects[1] | x | ? | ? | ? | 0      | *
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _objects
-     *    +-----------------------------------------------------------------------------+
-     *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _fieldNames
-     *    +-----------------------------------------------------------------------------+
-     *    | \0                                                                          |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _leafBuf
-     *    +-----------------------------------------------------------------------------+
-     *    | {}                                                                          |
-     *    +-----------------------------------------------------------------------------+
-
-
-        mmb::Element ys = xs.rightSibling();
-
-     *    _elements
-     *      oi      flags                offset                  ls  rs  lc  rc  p
-     *    +-----------------------------------------------------------------------------+
-     *  0 | 1 | s:- | ...       | off 0       into _fieldNames | x | x | 1 | ? | x      |
-     *  1 | 1 | s:+ | ...       | off of 'xs' into _objects[1] | x | 2 | ? | ? | 0      | *
-     *  2 | 1 | s:+ | ...       | off of 'ys' into _objects[1] | 1 | ? | ? | ? | 0      | *
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _objects
-     *    +-----------------------------------------------------------------------------+
-     *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _fieldNames
-     *    +-----------------------------------------------------------------------------+
-     *    | \0                                                                          |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _leafBuf
-     *    +-----------------------------------------------------------------------------+
-     *    | {}                                                                          |
-     *    +-----------------------------------------------------------------------------+
-
-
-        mmb::Element dne = ys.rightSibling();
-
-     *    _elements
-     *      oi      flags                offset                  ls  rs  lc  rc  p
-     *    +-----------------------------------------------------------------------------+
-     *  0 | 1 | s:- | ...       | off 0       into _fieldNames | x | x | 1 | 2 | x      | *
-     *  1 | 1 | s:+ | ...       | off of 'xs' into _objects[1] | x | 2 | ? | ? | 0      |
-     *  2 | 1 | s:+ | ...       | off of 'ys' into _objects[1] | 1 | x | ? | ? | 0      | *
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _objects
-     *    +-----------------------------------------------------------------------------+
-     *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _fieldNames
-     *    +-----------------------------------------------------------------------------+
-     *    | \0                                                                          |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _leafBuf
-     *    +-----------------------------------------------------------------------------+
-     *    | {}                                                                          |
-     *    +-----------------------------------------------------------------------------+
-
-
-        mmb::Element ycaps = doc.makeElementString("Y", "Y");
-
-     *    _elements
-     *      oi      flags                offset                  ls  rs  lc  rc  p
-     *    +-----------------------------------------------------------------------------+
-     *  0 | 1 | s:- | ...       | off 0       into _fieldNames | x | x | 1 | 2 | x      |
-     *  1 | 1 | s:+ | ...       | off of 'xs' into _objects[1] | x | 2 | ? | ? | 0      |
-     *  2 | 1 | s:+ | ...       | off of 'ys' into _objects[1] | 1 | x | ? | ? | 0      |
-     *  3 | 0 | s:+ | ...       | off of 'Y'  into _objects[0] | x | x | x | x | x      | *
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _objects
-     *    +-----------------------------------------------------------------------------+
-     *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _fieldNames
-     *    +-----------------------------------------------------------------------------+
-     *    | \0                                                                          |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _leafBuf
-     *    +-----------------------------------------------------------------------------+
-     *    | { "Y" : "Y" }                                                               | *
-     *    +-----------------------------------------------------------------------------+
-
-
-        ys.pushBack(ycaps);
-
-     *    _elements
-     *      oi      flags                offset                    ls  rs  lc  rc  p
-     *    +-----------------------------------------------------------------------------+
-     *  0 | 1 | s:- | ...       | off 0         into _fieldNames | x | x | 1 | 2 | x    |
-     *  1 | 1 | s:+ | ...       | off of 'xs'   into _objects[1] | x | 2 | ? | ? | 0    |
-     *  2 | 1 | s:- | ...       | off of 'ys'   into _objects[1] | 1 | x | 4 | 3 | 0    | *
-     *  3 | 0 | s:+ | ...       | off of 'Y'    into _objects[0] | 4 | x | x | x | 2    | *
-     *  4 | 1 | s:+ | ...       | off of 'ys.y' into _objects[1] | x | 3 | x | x | 2    | *
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _objects
-     *    +-----------------------------------------------------------------------------+
-     *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _fieldNames
-     *    +-----------------------------------------------------------------------------+
-     *    | \0                                                                          |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _leafBuf
-     *    +-----------------------------------------------------------------------------+
-     *    | { "Y" : "Y" }                                                               |
-     *    +-----------------------------------------------------------------------------+
-
-
-        mmb::Element pun = doc.makeElementArray("why");
-
-     *    _elements
-     *      oi      flags                offset                     ls  rs  lc  rc  p
-     *    +-----------------------------------------------------------------------------+
-     *  0 | 1  | s:- | ...       | off 0         into _fieldNames | x | x | 1 | 2 | x   |
-     *  1 | 1  | s:+ | ...       | off of 'xs'   into _objects[1] | x | 2 | ? | ? | 0   |
-     *  2 | 1  | s:- | ...       | off of 'ys'   into _objects[1] | 1 | x | 4 | 3 | 0   |
-     *  3 | 0  | s:+ | ...       | off of 'Y'    into _objects[0] | 4 | x | x | x | 2   |
-     *  4 | 1  | s:+ | ...       | off of 'ys.y' into _objects[1] | x | 3 | x | x | 2   |
-     *  5 | -1 | s:- | a:+ | ... | off of 'why'  into _fieldNames | x | x | x | x | x   | *
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _objects
-     *    +-----------------------------------------------------------------------------+
-     *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _fieldNames
-     *    +-----------------------------------------------------------------------------+
-     *    | \0why\0                                                                     | *
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _leafBuf
-     *    +-----------------------------------------------------------------------------+
-     *    | { "Y" : "Y" }                                                               |
-     *    +-----------------------------------------------------------------------------+
-
-
-        ys.pushBack(pun);
-
-     *    _elements
-     *      oi      flags                offset                     ls  rs  lc  rc  p
-     *    +-----------------------------------------------------------------------------+
-     *  0 | 1  | s:- | ...       | off 0         into _fieldNames | x | x | 1 | 2 | x   |
-     *  1 | 1  | s:+ | ...       | off of 'xs'   into _objects[1] | x | 2 | ? | ? | 0   |
-     *  2 | 1  | s:- | ...       | off of 'ys'   into _objects[1] | 1 | x | 4 | 5 | 0   | *
-     *  3 | 0  | s:+ | ...       | off of 'Y'    into _objects[0] | 4 | 5 | x | x | 2   | *
-     *  4 | 1  | s:+ | ...       | off of 'ys.y' into _objects[1] | x | 3 | x | x | 2   |
-     *  5 | -1 | s:- | a:+ | ... | off of 'why'  into _fieldNames | 3 | x | x | x | 2   | *
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _objects
-     *    +-----------------------------------------------------------------------------+
-     *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _fieldNames
-     *    +-----------------------------------------------------------------------------+
-     *    | \0why\0                                                                     |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _leafBuf
-     *    +-----------------------------------------------------------------------------+
-     *    | { "Y" : "Y" }                                                               |
-     *    +-----------------------------------------------------------------------------+
-
-
-        pun.appendString("na", "not");
-
-     *    _elements
-     *      oi      flags                offset                     ls  rs  lc  rc  p
-     *    +-----------------------------------------------------------------------------+
-     *  0 | 1  | s:- | ...       | off 0         into _fieldNames | x | x | 1 | 2 | x   |
-     *  1 | 1  | s:+ | ...       | off of 'xs'   into _objects[1] | x | 2 | ? | ? | 0   |
-     *  2 | 1  | s:- | ...       | off of 'ys'   into _objects[1] | 1 | x | 4 | 5 | 0   |
-     *  3 | 0  | s:+ | ...       | off of 'Y'    into _objects[0] | 4 | 5 | x | x | 2   |
-     *  4 | 1  | s:+ | ...       | off of 'ys.y' into _objects[1] | x | 3 | x | x | 2   |
-     *  5 | -1 | s:- | a:+ | ... | off of 'why'  into _fieldNames | 3 | x | 6 | 6 | 2   | *
-     *  6 | 0  | s:+ | ...       | off of 'na'   into _objects[0] | x | x | x | x | 5   | *
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _objects
-     *    +-----------------------------------------------------------------------------+
-     *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _fieldNames
-     *    +-----------------------------------------------------------------------------+
-     *    | \0why\0                                                                     |
-     *    +-----------------------------------------------------------------------------+
-     *
-     *    _leafBuf
-     *    +-----------------------------------------------------------------------------+
-     *    | { "Y" : "Y", "na" : "not" }                                                 | *
-     *    +-----------------------------------------------------------------------------+
-     *
-     */
-
-// Work around http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29365. Note that the selection of
-// minor version 4 is somewhat arbitrary. It does appear that the fix for this was backported
-// to earlier versions. This is a conservative choice that we can revisit later. We need the
-// __clang__ here because Clang claims to be gcc of some version.
-#if defined(__clang__) || !defined(__GNUC__) || (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4)
-    namespace {
-#endif
+/** Mutable BSON Implementation Overview
+ *
+ *  If you haven't read it already, please read the 'Mutable BSON Overview' comment in
+ *  document.h before reading further.
+ *
+ *  In the following discussion, the capitalized terms 'Element' and 'Document' refer to
+ *  the classes of the same name. At times, it is also necessary to refer to abstract
+ *  'elements' or 'documents', in the sense of bsonspec.org. These latter uses are
+ *  non-capitalized. In the BSON specification, there are two 'classes' of
+ *  elements. 'Primitive' or 'leaf' elements are those elements which do not contain other
+ *  elements. In practice, all BSON types except 'Array' and 'Object' are primitives. The
+ *  CodeWScope type is an exception, but one that we sidestep by considering its BSONObj
+ *  payload to be opaque.
+ *
+ *  A mutable BSON Document and its component Elements are implemented in terms of four
+ *  data structures. These structures are owned by a Document::Impl object. Each Document
+ *  owns a unique Document::Impl, which owns the relevant data structures and provides
+ *  accessors, mutators, and helper methods related to those data structures. Understanding
+ *  these data structures is critical for understanding how the system as a whole operates.
+ *
+ *  - The 'Elements Vector': This is a std::vector<ElementRep>, where 'ElementRep' is a
+ *    structure type defined below that contains the detailed information about an entity
+ *    in the Document (e.g. an Object, or an Array, or a NumberLong, etc.). The 'Element'
+ *    and 'ConstElement' objects contain a pointer to a Document (which allows us to reach
+ *    the Document::Impl for the Document), and an index into the Elements Vector in the
+ *    Document::Impl. These two pieces of information make it possible for us to obtain the
+ *    ElementRep associated with a given Element. Note that the Elements Vector is append
+ *    only: ElementReps are never removed from it, even if the cooresponding Element is
+ *    removed from the Document. By never removing ElementReps, and by using indexes into
+ *    the Elements Vector, we can ensure that Elements are never invalidated. Note that
+ *    every Document comes with an automatically provided 'root' element of mongo::Object
+ *    type. The ElementRep for the root is always in the first slot (index zero) of the
+ *    Elements Vector.
+ *
+ *  - The 'Leaf Builder': This is a standard BSONObjBuilder. When a request is made to the
+ *    Document to add new data to the Document via one of the Document::makeElement[TYPE]
+ *    calls, the element is constructed by invoking the appropriate method on the Leaf
+ *    Builder, forwarding the arguments provided to the call on Document. This results in a
+ *    contiguous region of memory which encodes this element, capturing its field name, its
+ *    type, and the bytes that encode its value, in the same way it normally does when
+ *    using BSONObjBuilder. We then build an ElementRep that indexes into the BufBuilder
+ *    behind the BSONObjBuilder (more on how this happens below, in the section on the
+ *    'Objects Vector'), then insert that new ElementRep into the ElementsVector, and
+ *    finally return an Element that dereferences to the new ElementRep. Subsequently,
+ *    requests for the type, fieldname or value bytes via the Element are satisfied by
+ *    obtaining the contiguous memory region for the element, which may be used to
+ *    construct a BSONElement over that memory region.
+ *
+ *  - The 'Objects Vector': This is a std::vector<BSONObj>. Any BSONObj object that
+ *    provides values for parts of the Document is stored in the Objects Vector. For
+ *    instance, in 'Example 2' from document.h, the Document we construct wraps an existing
+ *    BSONObj, which is passed in to the Document constructor. That BSONObj would be stored
+ *    in the Objects Vector. The data content of the BSONObj is not copied, but the BSONObj
+ *    is copied, so the if the BSONObj is counted, we will up its refcount. In any event
+ *    the lifetime of the BSONObj must exceed our lifetime by some mechanism. ElementReps
+ *    that represent the component elements of the BSONObj store the index of their
+ *    supporting BSONObj into the 'objIdx' field of ElementRep. Later, when Elements
+ *    referring to those ElementReps are asked for properties like the field name or type
+ *    of the Element, the underlying memory region in the appropriate BSONObj may be
+ *    examined to provide the relevant data.
+ *
+ *  - The 'Field Name Heap': For some elements, particularly those in the Leaf Builder or
+ *    those embedded in a BSONObj in the Objects Vector, we can easily obtain the field
+ *    name by reading it from the encoded BSON. However, some elements are not so
+ *    fortunate. Newly created elements of mongo::Array or mongo::Object type, for
+ *    instance, don't have a memory region that provides values. In such cases, the field
+ *    name is stored in the field name heap, which is simply std::vector<char>, where the
+ *    field names are null-byte-delimited. ElementsReps for such elements store an offset
+ *    into the Field Name Heap, and when asked for their field name simply return a pointer
+ *    to the string data the offset identifies. This exploits the fact that in BSON, valid
+ *    field names are null terinated and do not contain embedded null bytes.
+ *
+ *  - The 'root' Element. Each Document contains a well known Element, which always refers
+ *    to a pre-constructed ElementRep at offset zero in the Elements Vector. This is an
+ *    Object element, and it is considered as the root of the document tree. It is possible
+ *    for ElementReps to exist in the Document data structures, but not be in a child
+ *    relationship to the root Element. Newly created Elements, for instance, are in this
+ *    sort of 'detached' state until they are attched to another element. Only Element's
+ *    that are children of the root element are traversed when calling top level
+ *    serialization or comparision operations on Document.
+ *
+ *  When you construct a Document that obtains its values from an underlying BSONObj, the
+ *  entire BSONObj is not 'unpacked' into ElementReps at Document construction
+ *  time. Instead, as you ask for Elements with the Element navigation API, the Elements
+ *  for children and siblings are created on demand. Subobjects which are never visited
+ *  will never have ElementReps constructed for them. Similarly, when writing a Document
+ *  back out to a builder, regions of memory that provide values for the Document and which
+ *  have not been modified will be block copied, instead of being recursively explored and
+ *  written.
+ *
+ *  To see how these data structures interoperate, we will walk through an example. You may
+ *  want to read the comments for ElementRep before tackling the example, since we will
+ *  refer to the internal state of ElementRep here. The example code used here exists as a
+ *  unit test in mutable_bson_test.cpp as (Documentation, Example3).
+ *
+ *
+ *  Legend:
+ *   oi   : objIdx
+ *   +/-  : bitfield state (s: serialized, a: array)
+ *   x    : invalid/empty rep idx
+ *   ?    : opaque rep idx
+ *   ls/rs: left/right sibling
+ *   lc/rc: left/right child
+ *   p    : parent
+
+    static const char inJson[] =
+        "{"
+        "  'xs': { 'x' : 'x', 'X' : 'X' },"
+        "  'ys': { 'y' : 'y' }"
+        "}";
+    mongo::BSONObj inObj = mongo::fromjson(inJson);
+    mmb::Document doc(inObj);
+
+ *    _elements
+ *      oi      flags                offset                  ls  rs  lc  rc  p
+ *    +-----------------------------------------------------------------------------+
+ *  0 | 1 | s:- | ...       | off 0       into _fieldNames | x | x | ? | ? | x      |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _objects
+ *    +-----------------------------------------------------------------------------+
+ *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _fieldNames
+ *    +-----------------------------------------------------------------------------+
+ *    | \0                                                                          |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _leafBuf
+ *    +-----------------------------------------------------------------------------+
+ *    | {}                                                                          |
+ *    +-----------------------------------------------------------------------------+
 
-        // The designated field name for the root element.
-        const char kRootFieldName[] = "";
 
-        // How many reps do we cache before we spill to heap. Use a power of two. For debug
-        // builds we make this very small so it is less likely to mask vector invalidation
-        // logic errors. We don't make it zero so that we do execute the fastRep code paths.
-        const size_t kFastReps = kDebugBuild ? 2 : 128;
+    mmb::Element root = doc.root();
+    mmb::Element xs = root.leftChild();
 
-        // An ElementRep contains the information necessary to locate the data for an Element,
-        // and the topology information for how the Element is related to other Elements in the
-        // document.
-#pragma pack(push, 1)
-        struct ElementRep {
-
-            // The index of the BSONObj that provides the value for this Element. For nodes
-            // where serialized is 'false', this value may be kInvalidObjIdx to indicate that
-            // the Element does not have a supporting BSONObj.
-            typedef uint16_t ObjIdx;
-            ObjIdx objIdx;
-
-            // This bit is true if this ElementRep identifies a completely serialized
-            // BSONElement (i.e. a region of memory with a bson type byte, a fieldname, and an
-            // encoded value). Changes to children of a serialized element will cause it to be
-            // marked as unserialized.
-            uint16_t serialized: 1;
-
-            // For object like Elements where we cannot determine the type of the object by
-            // looking a region of memory, the 'array' bit allows us to determine whether we
-            // are an object or an array.
-            uint16_t array: 1;
-
-            // Reserved for future use.
-            uint16_t reserved: 14;
-
-            // This word either gives the offset into the BSONObj associated with this
-            // ElementRep where this serialized BSON element may be located, or the offset into
-            // the _fieldNames member of the Document where the field name for this BSON
-            // element may be located.
-            uint32_t offset;
-
-            // The indexes of our left and right siblings in the Document.
-            struct {
-                Element::RepIdx left;
-                Element::RepIdx right;
-            } sibling;
-
-            // The indexes of our left and right chidren in the Document.
-            struct {
-                Element::RepIdx left;
-                Element::RepIdx right;
-            } child;
-
-            // The index of our parent in the Document.
-            Element::RepIdx parent;
-
-            // The cached field name size of this element, or -1 if unknown.
-            int32_t fieldNameSize;
-        };
-#pragma pack(pop)
+ *    _elements
+ *      oi      flags                offset                  ls  rs  lc  rc  p
+ *    +-----------------------------------------------------------------------------+
+ *  0 | 1 | s:- | ...       | off 0       into _fieldNames | x | x | 1 | ? | x      | *
+ *  1 | 1 | s:+ | ...       | off of 'xs' into _objects[1] | x | ? | ? | ? | 0      | *
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _objects
+ *    +-----------------------------------------------------------------------------+
+ *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _fieldNames
+ *    +-----------------------------------------------------------------------------+
+ *    | \0                                                                          |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _leafBuf
+ *    +-----------------------------------------------------------------------------+
+ *    | {}                                                                          |
+ *    +-----------------------------------------------------------------------------+
 
-        BOOST_STATIC_ASSERT(sizeof(ElementRep) == 32);
 
-        // We want ElementRep to be a POD so Document::Impl can grow the std::vector with
-        // memmove.
-        //
-        // TODO: C++11 static_assert(std::is_pod<ElementRep>::value);
-
-        // The ElementRep for the root element is always zero.
-        const Element::RepIdx kRootRepIdx = Element::RepIdx(0);
-
-        // This is the object index for elements in the leaf heap.
-        const ElementRep::ObjIdx kLeafObjIdx = ElementRep::ObjIdx(0);
-
-        // This is the sentinel value to indicate that we have no supporting BSONObj.
-        const ElementRep::ObjIdx kInvalidObjIdx = ElementRep::ObjIdx(-1);
-
-        // This is the highest valid object index that does not overlap sentinel values.
-        const ElementRep::ObjIdx kMaxObjIdx = ElementRep::ObjIdx(-2);
-
-        // Returns the offset of 'elt' within 'object' as a uint32_t. The element must be part
-        // of the object or the behavior is undefined.
-        uint32_t getElementOffset(const BSONObj& object, const BSONElement& elt) {
-            dassert(!elt.eoo());
-            const char* const objRaw = object.objdata();
-            const char* const eltRaw = elt.rawdata();
-            dassert(objRaw < eltRaw);
-            dassert(eltRaw < objRaw + object.objsize());
-            dassert(eltRaw + elt.size() <= objRaw + object.objsize());
-            const ptrdiff_t offset = eltRaw - objRaw;
-            // BSON documents express their size as an int32_t so we should always be able to
-            // express the offset as a uint32_t.
-            verify(offset > 0);
-            verify(offset <= std::numeric_limits<int32_t>::max());
-            return offset;
-        }
+    mmb::Element ys = xs.rightSibling();
 
-        // Returns true if this ElementRep is 'detached' from all other elements and can be
-        // added as a child, which helps ensure that we maintain a tree rather than a graph
-        // when adding new elements to the tree. The root element is never considered to be
-        // attachable.
-        bool canAttach(const Element::RepIdx id, const ElementRep& rep) {
-            return
-                (id != kRootRepIdx) &&
-                (rep.sibling.left == Element::kInvalidRepIdx) &&
-                (rep.sibling.right == Element::kInvalidRepIdx) &&
-                (rep.parent == Element::kInvalidRepIdx);
-        }
+ *    _elements
+ *      oi      flags                offset                  ls  rs  lc  rc  p
+ *    +-----------------------------------------------------------------------------+
+ *  0 | 1 | s:- | ...       | off 0       into _fieldNames | x | x | 1 | ? | x      |
+ *  1 | 1 | s:+ | ...       | off of 'xs' into _objects[1] | x | 2 | ? | ? | 0      | *
+ *  2 | 1 | s:+ | ...       | off of 'ys' into _objects[1] | 1 | ? | ? | ? | 0      | *
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _objects
+ *    +-----------------------------------------------------------------------------+
+ *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _fieldNames
+ *    +-----------------------------------------------------------------------------+
+ *    | \0                                                                          |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _leafBuf
+ *    +-----------------------------------------------------------------------------+
+ *    | {}                                                                          |
+ *    +-----------------------------------------------------------------------------+
 
-        // Returns a Status describing why 'canAttach' returned false. This function should not
-        // be inlined since it just makes the callers larger for no real gain.
-        NOINLINE_DECL Status getAttachmentError(const ElementRep& rep);
-        Status getAttachmentError(const ElementRep& rep) {
-            if (rep.sibling.left != Element::kInvalidRepIdx)
-                return Status(ErrorCodes::IllegalOperation, "dangling left sibling");
-            if (rep.sibling.right != Element::kInvalidRepIdx)
-                return Status(ErrorCodes::IllegalOperation, "dangling right sibling");
-            if (rep.parent != Element::kInvalidRepIdx)
-                return Status(ErrorCodes::IllegalOperation, "dangling parent");
-            return Status(ErrorCodes::IllegalOperation, "cannot add the root as a child");
-        }
 
+    mmb::Element dne = ys.rightSibling();
 
-        // Enable paranoid mode to force a reallocation on mutation of the princple data
-        // structures in Document::Impl. This is really slow, but can be very helpful if you
-        // suspect an invalidation logic error and want to find it with valgrind. Paranoid mode
-        // only works in debug mode; it is ignored in release builds.
-        const bool paranoid = false;
+ *    _elements
+ *      oi      flags                offset                  ls  rs  lc  rc  p
+ *    +-----------------------------------------------------------------------------+
+ *  0 | 1 | s:- | ...       | off 0       into _fieldNames | x | x | 1 | 2 | x      | *
+ *  1 | 1 | s:+ | ...       | off of 'xs' into _objects[1] | x | 2 | ? | ? | 0      |
+ *  2 | 1 | s:+ | ...       | off of 'ys' into _objects[1] | 1 | x | ? | ? | 0      | *
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _objects
+ *    +-----------------------------------------------------------------------------+
+ *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _fieldNames
+ *    +-----------------------------------------------------------------------------+
+ *    | \0                                                                          |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _leafBuf
+ *    +-----------------------------------------------------------------------------+
+ *    | {}                                                                          |
+ *    +-----------------------------------------------------------------------------+
+
+
+    mmb::Element ycaps = doc.makeElementString("Y", "Y");
+
+ *    _elements
+ *      oi      flags                offset                  ls  rs  lc  rc  p
+ *    +-----------------------------------------------------------------------------+
+ *  0 | 1 | s:- | ...       | off 0       into _fieldNames | x | x | 1 | 2 | x      |
+ *  1 | 1 | s:+ | ...       | off of 'xs' into _objects[1] | x | 2 | ? | ? | 0      |
+ *  2 | 1 | s:+ | ...       | off of 'ys' into _objects[1] | 1 | x | ? | ? | 0      |
+ *  3 | 0 | s:+ | ...       | off of 'Y'  into _objects[0] | x | x | x | x | x      | *
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _objects
+ *    +-----------------------------------------------------------------------------+
+ *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _fieldNames
+ *    +-----------------------------------------------------------------------------+
+ *    | \0                                                                          |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _leafBuf
+ *    +-----------------------------------------------------------------------------+
+ *    | { "Y" : "Y" }                                                               | *
+ *    +-----------------------------------------------------------------------------+
+
+
+    ys.pushBack(ycaps);
+
+ *    _elements
+ *      oi      flags                offset                    ls  rs  lc  rc  p
+ *    +-----------------------------------------------------------------------------+
+ *  0 | 1 | s:- | ...       | off 0         into _fieldNames | x | x | 1 | 2 | x    |
+ *  1 | 1 | s:+ | ...       | off of 'xs'   into _objects[1] | x | 2 | ? | ? | 0    |
+ *  2 | 1 | s:- | ...       | off of 'ys'   into _objects[1] | 1 | x | 4 | 3 | 0    | *
+ *  3 | 0 | s:+ | ...       | off of 'Y'    into _objects[0] | 4 | x | x | x | 2    | *
+ *  4 | 1 | s:+ | ...       | off of 'ys.y' into _objects[1] | x | 3 | x | x | 2    | *
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _objects
+ *    +-----------------------------------------------------------------------------+
+ *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _fieldNames
+ *    +-----------------------------------------------------------------------------+
+ *    | \0                                                                          |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _leafBuf
+ *    +-----------------------------------------------------------------------------+
+ *    | { "Y" : "Y" }                                                               |
+ *    +-----------------------------------------------------------------------------+
+
+
+    mmb::Element pun = doc.makeElementArray("why");
+
+ *    _elements
+ *      oi      flags                offset                     ls  rs  lc  rc  p
+ *    +-----------------------------------------------------------------------------+
+ *  0 | 1  | s:- | ...       | off 0         into _fieldNames | x | x | 1 | 2 | x   |
+ *  1 | 1  | s:+ | ...       | off of 'xs'   into _objects[1] | x | 2 | ? | ? | 0   |
+ *  2 | 1  | s:- | ...       | off of 'ys'   into _objects[1] | 1 | x | 4 | 3 | 0   |
+ *  3 | 0  | s:+ | ...       | off of 'Y'    into _objects[0] | 4 | x | x | x | 2   |
+ *  4 | 1  | s:+ | ...       | off of 'ys.y' into _objects[1] | x | 3 | x | x | 2   |
+ *  5 | -1 | s:- | a:+ | ... | off of 'why'  into _fieldNames | x | x | x | x | x   | *
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _objects
+ *    +-----------------------------------------------------------------------------+
+ *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _fieldNames
+ *    +-----------------------------------------------------------------------------+
+ *    | \0why\0                                                                     | *
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _leafBuf
+ *    +-----------------------------------------------------------------------------+
+ *    | { "Y" : "Y" }                                                               |
+ *    +-----------------------------------------------------------------------------+
+
+
+    ys.pushBack(pun);
+
+ *    _elements
+ *      oi      flags                offset                     ls  rs  lc  rc  p
+ *    +-----------------------------------------------------------------------------+
+ *  0 | 1  | s:- | ...       | off 0         into _fieldNames | x | x | 1 | 2 | x   |
+ *  1 | 1  | s:+ | ...       | off of 'xs'   into _objects[1] | x | 2 | ? | ? | 0   |
+ *  2 | 1  | s:- | ...       | off of 'ys'   into _objects[1] | 1 | x | 4 | 5 | 0   | *
+ *  3 | 0  | s:+ | ...       | off of 'Y'    into _objects[0] | 4 | 5 | x | x | 2   | *
+ *  4 | 1  | s:+ | ...       | off of 'ys.y' into _objects[1] | x | 3 | x | x | 2   |
+ *  5 | -1 | s:- | a:+ | ... | off of 'why'  into _fieldNames | 3 | x | x | x | 2   | *
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _objects
+ *    +-----------------------------------------------------------------------------+
+ *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _fieldNames
+ *    +-----------------------------------------------------------------------------+
+ *    | \0why\0                                                                     |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _leafBuf
+ *    +-----------------------------------------------------------------------------+
+ *    | { "Y" : "Y" }                                                               |
+ *    +-----------------------------------------------------------------------------+
+
+
+    pun.appendString("na", "not");
+
+ *    _elements
+ *      oi      flags                offset                     ls  rs  lc  rc  p
+ *    +-----------------------------------------------------------------------------+
+ *  0 | 1  | s:- | ...       | off 0         into _fieldNames | x | x | 1 | 2 | x   |
+ *  1 | 1  | s:+ | ...       | off of 'xs'   into _objects[1] | x | 2 | ? | ? | 0   |
+ *  2 | 1  | s:- | ...       | off of 'ys'   into _objects[1] | 1 | x | 4 | 5 | 0   |
+ *  3 | 0  | s:+ | ...       | off of 'Y'    into _objects[0] | 4 | 5 | x | x | 2   |
+ *  4 | 1  | s:+ | ...       | off of 'ys.y' into _objects[1] | x | 3 | x | x | 2   |
+ *  5 | -1 | s:- | a:+ | ... | off of 'why'  into _fieldNames | 3 | x | 6 | 6 | 2   | *
+ *  6 | 0  | s:+ | ...       | off of 'na'   into _objects[0] | x | x | x | x | 5   | *
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _objects
+ *    +-----------------------------------------------------------------------------+
+ *    | BSONObj for _leafBuilder | BSONObj for inObj |                              |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _fieldNames
+ *    +-----------------------------------------------------------------------------+
+ *    | \0why\0                                                                     |
+ *    +-----------------------------------------------------------------------------+
+ *
+ *    _leafBuf
+ *    +-----------------------------------------------------------------------------+
+ *    | { "Y" : "Y", "na" : "not" }                                                 | *
+ *    +-----------------------------------------------------------------------------+
+ *
+ */
 
-#if defined(__clang__) || !defined(__GNUC__) || (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4)
-    } // namespace
+// Work around http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29365. Note that the selection of
+// minor version 4 is somewhat arbitrary. It does appear that the fix for this was backported
+// to earlier versions. This is a conservative choice that we can revisit later. We need the
+// __clang__ here because Clang claims to be gcc of some version.
+#if defined(__clang__) || !defined(__GNUC__) || (__GNUC__ > 4) || \
+    (__GNUC__ == 4 && __GNUC_MINOR__ >= 4)
+namespace {
 #endif
 
-    /** Document::Impl holds the Document state. Please see the file comment above for details
-     *  on the fields of Impl and how they are used to realize the implementation of mutable
-     *  BSON. Impl provides various utility methods to insert, lookup, and interrogate the
-     *  Elements, BSONObj objects, field names, and builders associated with the Document.
-     *
-     *  TODO: At some point, we could remove the firewall and inline the members of Impl into
-     *  Document.
-     */
-    class Document::Impl {
-        MONGO_DISALLOW_COPYING(Impl);
-
-    public:
-        Impl(Document::InPlaceMode inPlaceMode)
-            : _numElements(0)
-            , _slowElements()
-            , _objects()
-            , _fieldNames()
-            , _leafBuf()
-            , _leafBuilder(_leafBuf)
-            , _fieldNameScratch()
-            , _damages()
-            , _inPlaceMode(inPlaceMode) {
-
-            // We always have a BSONObj for the leaves, and we often have
-            // one for our base document, so reserve 2.
-            _objects.reserve(2);
-
-            // We always have at least one byte for the root field name, and we would like
-            // to be able to hold a few short field names without reallocation.
-            _fieldNames.reserve(8);
-
-            // We need an object at _objects[0] so that we can access leaf elements we
-            // construct with the leaf builder in the same way we access elements serialized in
-            // other BSONObjs. So we call asTempObj on the builder and store the result in slot
-            // 0.
-            dassert(_objects.size() == kLeafObjIdx);
-            _objects.push_back(_leafBuilder.asTempObj());
-            dassert(_leafBuf.len() != 0);
-        }
-
-        ~Impl() {
-            _leafBuilder.abandon();
-        }
-
-        void reset(Document::InPlaceMode inPlaceMode) {
-            // Clear out the state in the vectors.
-            _slowElements.clear();
-            _numElements = 0;
-
-            _objects.clear();
-            _fieldNames.clear();
-
-            // There is no way to reset the state of a BSONObjBuilder, so we need to call its
-            // dtor, reset the underlying buf, and re-invoke the constructor in-place.
-            _leafBuilder.abandon();
-            _leafBuilder.~BSONObjBuilder();
-            _leafBuf.reset();
-            new (&_leafBuilder) BSONObjBuilder(_leafBuf);
+// The designated field name for the root element.
+const char kRootFieldName[] = "";
 
-            _fieldNameScratch.clear();
-            _damages.clear();
-            _inPlaceMode = inPlaceMode;
-
-            // Ensure that we start in the same state as the ctor would leave us in.
-            _objects.push_back(_leafBuilder.asTempObj());
-        }
-
-        // Obtain the ElementRep for the given rep id.
-        ElementRep& getElementRep(Element::RepIdx id) {
-            return const_cast<ElementRep&>(const_cast<const Impl*>(this)->getElementRep(id));
-        }
+// How many reps do we cache before we spill to heap. Use a power of two. For debug
+// builds we make this very small so it is less likely to mask vector invalidation
+// logic errors. We don't make it zero so that we do execute the fastRep code paths.
+const size_t kFastReps = kDebugBuild ? 2 : 128;
 
-        // Obtain the ElementRep for the given rep id.
-        const ElementRep& getElementRep(Element::RepIdx id) const {
-            dassert(id < _numElements);
-            if (id < kFastReps)
-                return _fastElements[id];
-            else
-                return _slowElements[id - kFastReps];
-        }
-
-        // Construct and return a new default initialized ElementRep. The RepIdx identifying
-        // the new rep is returned in the out parameter.
-        ElementRep& makeNewRep(Element::RepIdx* newIdx) {
-
-            const ElementRep defaultRep = {
-                kInvalidObjIdx,
-                false, false, 0,
-                0,
-                { Element::kInvalidRepIdx, Element::kInvalidRepIdx },
-                { Element::kInvalidRepIdx, Element::kInvalidRepIdx },
-                Element::kInvalidRepIdx,
-                -1
-            };
-
-            const Element::RepIdx id = *newIdx = _numElements++;
-
-            if (id < kFastReps) {
-                return _fastElements[id] = defaultRep;
-            }
-            else {
-                verify(id <= Element::kMaxRepIdx);
-
-                if (kDebugBuild && paranoid) {
-                    // Force all reps to new addresses to help catch invalid rep usage.
-                    std::vector<ElementRep> newSlowElements(_slowElements);
-                    _slowElements.swap(newSlowElements);
-                }
-
-                return *_slowElements.insert(_slowElements.end(), defaultRep);
-            }
-        }
-
-        // Insert a new ElementRep for a leaf element at the given offset and return its ID.
-        Element::RepIdx insertLeafElement(int offset, int fieldNameSize = -1) {
-            // BufBuilder hands back sizes in 'int's.
-            Element::RepIdx inserted;
-            ElementRep& rep = makeNewRep(&inserted);
-
-            rep.fieldNameSize = fieldNameSize;
-            rep.objIdx = kLeafObjIdx;
-            rep.serialized = true;
-            dassert(offset >= 0);
-            // TODO: Is this a legitimate possibility?
-            dassert(static_cast<unsigned int>(offset) < std::numeric_limits<uint32_t>::max());
-            rep.offset = offset;
-            _objects[kLeafObjIdx] = _leafBuilder.asTempObj();
-            return inserted;
-        }
-
-        // Obtain the object builder for the leaves.
-        BSONObjBuilder& leafBuilder() {
-            return _leafBuilder;
-        }
-
-        // Obtain the BSONObj for the given object id.
-        BSONObj& getObject(ElementRep::ObjIdx objIdx) {
-            dassert(objIdx < _objects.size());
-            return _objects[objIdx];
-        }
-
-        // Obtain the BSONObj for the given object id.
-        const BSONObj& getObject(ElementRep::ObjIdx objIdx) const {
-            dassert(objIdx < _objects.size());
-            return _objects[objIdx];
-        }
-
-        // Insert the given BSONObj and return an ID for it.
-        ElementRep::ObjIdx insertObject(const BSONObj& newObj) {
-            const size_t objIdx = _objects.size();
-            verify(objIdx <= kMaxObjIdx);
-            _objects.push_back(newObj);
-            if (kDebugBuild && paranoid) {
-                // Force reallocation to catch use after invalidation.
-                std::vector<BSONObj> new_objects(_objects);
-                _objects.swap(new_objects);
-            }
-            return objIdx;
-        }
-
-        // Given a RepIdx, return the BSONElement that it represents.
-        BSONElement getSerializedElement(const ElementRep& rep) const {
-            const BSONObj& object = getObject(rep.objIdx);
-            return BSONElement(
-                object.objdata() + rep.offset,
-                rep.fieldNameSize,
-                BSONElement::FieldNameSizeTag());
-        }
-
-        // A helper method that either inserts the field name into the field name heap and
-        // updates element.
-        void insertFieldName(ElementRep& rep, StringData fieldName) {
-            dassert(!rep.serialized);
-            rep.offset = insertFieldName(fieldName);
-        }
-
-        // Retrieve the fieldName, given a rep.
-        StringData getFieldName(const ElementRep& rep) const {
-            // The root element has no field name.
-            if (&rep == &getElementRep(kRootRepIdx))
-                return StringData();
-
-            if (rep.serialized || (rep.objIdx != kInvalidObjIdx))
-                return getSerializedElement(rep).fieldNameStringData();
-
-            return getFieldName(rep.offset);
-        }
-
-        StringData getFieldNameForNewElement(const ElementRep& rep) {
-            StringData result = getFieldName(rep);
-            if (rep.objIdx == kLeafObjIdx) {
-                _fieldNameScratch.assign(result.rawData(), result.size());
-                result = StringData(_fieldNameScratch);
-            }
-            return result;
-        }
-
-        // Retrieve the type, given a rep.
-        BSONType getType(const ElementRep& rep) const {
-            // The root element is always an Object.
-            if (&rep == &getElementRep(kRootRepIdx))
-                return mongo::Object;
-
-            if (rep.serialized || (rep.objIdx != kInvalidObjIdx))
-                return getSerializedElement(rep).type();
-
-            return rep.array ? mongo::Array : mongo::Object;
-        }
-
-        static bool isLeafType(BSONType type) {
-            return ((type != mongo::Object) && (type != mongo::Array));
-        }
-
-        // Returns true if rep is not an object or array.
-        bool isLeaf(const ElementRep& rep) const {
-            return isLeafType(getType(rep));
-        }
-
-        bool isLeaf(const BSONElement& elt) const {
-            return isLeafType(elt.type());
-        }
-
-        // Returns true if rep's value can be provided as a BSONElement.
-        bool hasValue(const ElementRep& rep) const {
-            // The root element may be marked serialized, but it doesn't have a BSONElement
-            // representation.
-            if (&rep == &getElementRep(kRootRepIdx))
-                return false;
-
-            return rep.serialized;
-        }
-
-        // Return the index of the left child of the Element with index 'index', resolving the
-        // left child to a realized Element if it is currently opaque. This may also cause the
-        // parent elements child.right entry to be updated.
-        Element::RepIdx resolveLeftChild(Element::RepIdx index) {
-            dassert(index != Element::kInvalidRepIdx);
-            dassert(index != Element::kOpaqueRepIdx);
-
-            // If the left child is anything other than opaque, then we are done here.
-            ElementRep* rep = &getElementRep(index);
-            if (rep->child.left != Element::kOpaqueRepIdx)
-                return rep->child.left;
-
-            // It should be impossible to have an opaque left child and be non-serialized,
-            dassert(rep->serialized);
-            BSONElement childElt = (
-                hasValue(*rep) ?
-                getSerializedElement(*rep).embeddedObject() :
-                getObject(rep->objIdx)).firstElement();
-
-            if (!childElt.eoo()) {
-
-                // Do this now before other writes so compiler can exploit knowing
-                // that we are not eoo.
-                const int32_t fieldNameSize = childElt.fieldNameSize();
-
-                Element::RepIdx inserted;
-                ElementRep& newRep = makeNewRep(&inserted);
-                // Calling makeNewRep invalidates rep since it may cause a reallocation of
-                // the element vector. After calling insertElement, we reacquire rep.
-                rep = &getElementRep(index);
-
-                newRep.serialized = true;
-                newRep.objIdx = rep->objIdx;
-                newRep.offset =
-                    getElementOffset(getObject(rep->objIdx), childElt);
-                newRep.parent = index;
-                newRep.sibling.right = Element::kOpaqueRepIdx;
-                // If this new object has possible substructure, mark its children as opaque.
-                if (!isLeaf(childElt)) {
-                    newRep.child.left = Element::kOpaqueRepIdx;
-                    newRep.child.right = Element::kOpaqueRepIdx;
-                }
-                newRep.fieldNameSize = fieldNameSize;
-                rep->child.left = inserted;
-            } else {
-                rep->child.left = Element::kInvalidRepIdx;
-                rep->child.right = Element::kInvalidRepIdx;
-            }
-
-            dassert(rep->child.left != Element::kOpaqueRepIdx);
-            return rep->child.left;
-        }
-
-        // Return the index of the right child of the Element with index 'index', resolving any
-        // opaque nodes. Note that this may require resolving all of the right siblings of the
-        // left child.
-        Element::RepIdx resolveRightChild(Element::RepIdx index) {
-            dassert(index != Element::kInvalidRepIdx);
-            dassert(index != Element::kOpaqueRepIdx);
-
-            Element::RepIdx current = getElementRep(index).child.right;
-            if (current == Element::kOpaqueRepIdx) {
-                current = resolveLeftChild(index);
-                while (current != Element::kInvalidRepIdx) {
-                    Element::RepIdx next = resolveRightSibling(current);
-                    if (next == Element::kInvalidRepIdx)
-                        break;
-                    current = next;
-                }
-
-                // The resolveRightSibling calls should have eventually updated this nodes right
-                // child pointer to point to the node we are about to return.
-                dassert(getElementRep(index).child.right == current);
-            }
-
-            return current;
-        }
-
-        // Return the index of the right sibling of the Element with index 'index', resolving
-        // the right sibling to a realized Element if it is currently opaque.
-        Element::RepIdx resolveRightSibling(Element::RepIdx index) {
-            dassert(index != Element::kInvalidRepIdx);
-            dassert(index != Element::kOpaqueRepIdx);
-
-            // If the right sibling is anything other than opaque, then we are done here.
-            ElementRep* rep = &getElementRep(index);
-            if (rep->sibling.right != Element::kOpaqueRepIdx)
-                return rep->sibling.right;
-
-            BSONElement elt = getSerializedElement(*rep);
-            BSONElement rightElt(elt.rawdata() + elt.size());
-
-            if (!rightElt.eoo()) {
-
-                // Do this now before other writes so compiler can exploit knowing
-                // that we are not eoo.
-                const int32_t fieldNameSize = rightElt.fieldNameSize();
-
-                Element::RepIdx inserted;
-                ElementRep& newRep = makeNewRep(&inserted);
-                // Calling makeNewRep invalidates rep since it may cause a reallocation of
-                // the element vector. After calling insertElement, we reacquire rep.
-                rep = &getElementRep(index);
-
-                newRep.serialized = true;
-                newRep.objIdx = rep->objIdx;
-                newRep.offset =
-                    getElementOffset(getObject(rep->objIdx), rightElt);
-                newRep.parent = rep->parent;
-                newRep.sibling.left = index;
-                newRep.sibling.right = Element::kOpaqueRepIdx;
-                // If this new object has possible substructure, mark its children as opaque.
-                if (!isLeaf(rightElt)) {
-                    newRep.child.left = Element::kOpaqueRepIdx;
-                    newRep.child.right = Element::kOpaqueRepIdx;
-                }
-                newRep.fieldNameSize = fieldNameSize;
-                rep->sibling.right = inserted;
-            } else {
-                rep->sibling.right = Element::kInvalidRepIdx;
-                // If we have found the end of this object, then our (necessarily existing)
-                // parent's necessarily opaque right child is now determined to be us.
-                dassert(rep->parent <= Element::kMaxRepIdx);
-                ElementRep& parentRep = getElementRep(rep->parent);
-                dassert(parentRep.child.right == Element::kOpaqueRepIdx);
-                parentRep.child.right = index;
-            }
-
-            dassert(rep->sibling.right != Element::kOpaqueRepIdx);
-            return rep->sibling.right;
-        }
-
-        // Find the ElementRep at index 'index', and mark it and all of its currently
-        // serialized parents as non-serialized.
-        void deserialize(Element::RepIdx index) {
-            while (index != Element::kInvalidRepIdx) {
-                ElementRep& rep = getElementRep(index);
-                // It does not make sense for leaf Elements to become deserialized, and
-                // requests to do so indicate a bug in the implementation of the library.
-                dassert(!isLeaf(rep));
-                if (!rep.serialized)
-                    break;
-                rep.serialized = false;
-                index = rep.parent;
-            }
-        }
-
-        inline bool doesNotAlias(StringData s) const {
-            // StringData may come from either the field name heap or the leaf builder.
-            return doesNotAliasLeafBuilder(s) && !inFieldNameHeap(s.rawData());
-        }
-
-        inline bool doesNotAliasLeafBuilder(StringData s) const {
-            return !inLeafBuilder(s.rawData());
-        }
-
-        inline bool doesNotAlias(const BSONElement& e) const {
-            // A BSONElement could alias the leaf builder.
-            return !inLeafBuilder(e.rawdata());
-        }
-
-        inline bool doesNotAlias(const BSONObj& o) const {
-            // A BSONObj could alias the leaf buildr.
-            return !inLeafBuilder(o.objdata());
-        }
-
-        // Returns true if 'data' points within the leaf BufBuilder.
-        inline bool inLeafBuilder(const char* data) const {
-            // TODO: Write up something documenting that the following is technically UB due
-            // to illegality of comparing pointers to different aggregates for ordering. Also,
-            // do we need to do anything to prevent the optimizer from compiling this out on
-            // that basis? I've seen clang do that. We may need to declare these volatile. On
-            // the other hand, these should only be being called under a dassert, so the
-            // optimizer is maybe not in play, and the UB is unlikely to be a problem in
-            // practice.
-            const char* const start = _leafBuf.buf();
-            const char* const end = start + _leafBuf.len();
-            return (data >= start) && (data < end);
-        }
-
-        // Returns true if 'data' points within the field name heap.
-        inline bool inFieldNameHeap(const char* data) const {
-            if (_fieldNames.empty())
-                return false;
-            const char* const start = &_fieldNames.front();
-            const char* const end = &_fieldNames.back();
-            return (data >= start) && (data < end);
-        }
-
-        void reserveDamageEvents(size_t expectedEvents) {
-            _damages.reserve(expectedEvents);
-        }
-
-        bool getInPlaceUpdates(DamageVector* damages, const char** source, size_t* size) {
-
-            // If some operations were not in-place, set source to NULL and return false to
-            // inform upstream that we are not returning in-place result data.
-            if (_inPlaceMode == Document::kInPlaceDisabled) {
-                damages->clear();
-                *source = NULL;
-                if (size)
-                    *size = 0;
-                return false;
-            }
-
-            // Set up the source and source size out parameters.
-            *source = _objects[0].objdata();
-            if (size)
-                *size = _objects[0].objsize();
-
-            // Swap our damage event queue with upstream, and reset ours to an empty vector. In
-            // princple, we can do another round of in-place updates.
-            damages->swap(_damages);
-            _damages.clear();
-
-            return true;
-        }
-
-        void disableInPlaceUpdates() {
-            _inPlaceMode = Document::kInPlaceDisabled;
-        }
-
-        Document::InPlaceMode getCurrentInPlaceMode() const {
-            return _inPlaceMode;
-        }
-
-        bool isInPlaceModeEnabled() const {
-            return getCurrentInPlaceMode() == Document::kInPlaceEnabled;
-        }
-
-        void recordDamageEvent(DamageEvent::OffsetSizeType targetOffset,
-                               DamageEvent::OffsetSizeType sourceOffset,
-                               size_t size) {
-            _damages.push_back(DamageEvent());
-            _damages.back().targetOffset = targetOffset;
-            _damages.back().sourceOffset = sourceOffset;
-            _damages.back().size = size;
-            if (kDebugBuild && paranoid) {
-                // Force damage events to new addresses to catch invalidation errors.
-                DamageVector new_damages(_damages);
-                _damages.swap(new_damages);
-            }
-        }
-
-        // Check all preconditions on doing an in-place update, except for size match.
-        bool canUpdateInPlace(const ElementRep& sourceRep, const ElementRep& targetRep) {
-
-            // NOTE: CodeWScope might arguably be excluded since it has substructure, but
-            // mutable doesn't permit navigation into its document, so we can handle it.
-
-            // We can only do an in-place update to an element that is serialized and is not in
-            // the leaf heap.
-            //
-            // TODO: In the future, we can replace values in the leaf heap if they are of the
-            // same size as the origin was. For now, we don't support that.
-            if (!hasValue(targetRep) || (targetRep.objIdx == kLeafObjIdx))
-                return false;
+// An ElementRep contains the information necessary to locate the data for an Element,
+// and the topology information for how the Element is related to other Elements in the
+// document.
+#pragma pack(push, 1)
+struct ElementRep {
+    // The index of the BSONObj that provides the value for this Element. For nodes
+    // where serialized is 'false', this value may be kInvalidObjIdx to indicate that
+    // the Element does not have a supporting BSONObj.
+    typedef uint16_t ObjIdx;
+    ObjIdx objIdx;
+
+    // This bit is true if this ElementRep identifies a completely serialized
+    // BSONElement (i.e. a region of memory with a bson type byte, a fieldname, and an
+    // encoded value). Changes to children of a serialized element will cause it to be
+    // marked as unserialized.
+    uint16_t serialized : 1;
+
+    // For object like Elements where we cannot determine the type of the object by
+    // looking a region of memory, the 'array' bit allows us to determine whether we
+    // are an object or an array.
+    uint16_t array : 1;
+
+    // Reserved for future use.
+    uint16_t reserved : 14;
+
+    // This word either gives the offset into the BSONObj associated with this
+    // ElementRep where this serialized BSON element may be located, or the offset into
+    // the _fieldNames member of the Document where the field name for this BSON
+    // element may be located.
+    uint32_t offset;
+
+    // The indexes of our left and right siblings in the Document.
+    struct {
+        Element::RepIdx left;
+        Element::RepIdx right;
+    } sibling;
+
+    // The indexes of our left and right chidren in the Document.
+    struct {
+        Element::RepIdx left;
+        Element::RepIdx right;
+    } child;
+
+    // The index of our parent in the Document.
+    Element::RepIdx parent;
+
+    // The cached field name size of this element, or -1 if unknown.
+    int32_t fieldNameSize;
+};
+#pragma pack(pop)
 
-            // sourceRep should be newly created, so it must have a value representation.
-            dassert(hasValue(sourceRep));
-
-            // For a target that has substructure, we only permit in-place updates if there
-            // cannot be ElementReps that reference data within the target. We don't need to
-            // worry about ElementReps for source, since it is newly created. The only way
-            // there can be ElementReps referring into substructure is if the Element has
-            // non-empty non-opaque child references.
-            if (!isLeaf(targetRep)) {
-                if (((targetRep.child.left != Element::kOpaqueRepIdx) &&
-                     (targetRep.child.left != Element::kInvalidRepIdx)) ||
-                    ((targetRep.child.right != Element::kOpaqueRepIdx) &&
-                     (targetRep.child.right != Element::kInvalidRepIdx)))
-                    return false;
-            }
+BOOST_STATIC_ASSERT(sizeof(ElementRep) == 32);
+
+// We want ElementRep to be a POD so Document::Impl can grow the std::vector with
+// memmove.
+//
+// TODO: C++11 static_assert(std::is_pod<ElementRep>::value);
+
+// The ElementRep for the root element is always zero.
+const Element::RepIdx kRootRepIdx = Element::RepIdx(0);
+
+// This is the object index for elements in the leaf heap.
+const ElementRep::ObjIdx kLeafObjIdx = ElementRep::ObjIdx(0);
+
+// This is the sentinel value to indicate that we have no supporting BSONObj.
+const ElementRep::ObjIdx kInvalidObjIdx = ElementRep::ObjIdx(-1);
+
+// This is the highest valid object index that does not overlap sentinel values.
+const ElementRep::ObjIdx kMaxObjIdx = ElementRep::ObjIdx(-2);
+
+// Returns the offset of 'elt' within 'object' as a uint32_t. The element must be part
+// of the object or the behavior is undefined.
+uint32_t getElementOffset(const BSONObj& object, const BSONElement& elt) {
+    dassert(!elt.eoo());
+    const char* const objRaw = object.objdata();
+    const char* const eltRaw = elt.rawdata();
+    dassert(objRaw < eltRaw);
+    dassert(eltRaw < objRaw + object.objsize());
+    dassert(eltRaw + elt.size() <= objRaw + object.objsize());
+    const ptrdiff_t offset = eltRaw - objRaw;
+    // BSON documents express their size as an int32_t so we should always be able to
+    // express the offset as a uint32_t.
+    verify(offset > 0);
+    verify(offset <= std::numeric_limits<int32_t>::max());
+    return offset;
+}
+
+// Returns true if this ElementRep is 'detached' from all other elements and can be
+// added as a child, which helps ensure that we maintain a tree rather than a graph
+// when adding new elements to the tree. The root element is never considered to be
+// attachable.
+bool canAttach(const Element::RepIdx id, const ElementRep& rep) {
+    return (id != kRootRepIdx) && (rep.sibling.left == Element::kInvalidRepIdx) &&
+        (rep.sibling.right == Element::kInvalidRepIdx) && (rep.parent == Element::kInvalidRepIdx);
+}
+
+// Returns a Status describing why 'canAttach' returned false. This function should not
+// be inlined since it just makes the callers larger for no real gain.
+NOINLINE_DECL Status getAttachmentError(const ElementRep& rep);
+Status getAttachmentError(const ElementRep& rep) {
+    if (rep.sibling.left != Element::kInvalidRepIdx)
+        return Status(ErrorCodes::IllegalOperation, "dangling left sibling");
+    if (rep.sibling.right != Element::kInvalidRepIdx)
+        return Status(ErrorCodes::IllegalOperation, "dangling right sibling");
+    if (rep.parent != Element::kInvalidRepIdx)
+        return Status(ErrorCodes::IllegalOperation, "dangling parent");
+    return Status(ErrorCodes::IllegalOperation, "cannot add the root as a child");
+}
+
+
+// Enable paranoid mode to force a reallocation on mutation of the princple data
+// structures in Document::Impl. This is really slow, but can be very helpful if you
+// suspect an invalidation logic error and want to find it with valgrind. Paranoid mode
+// only works in debug mode; it is ignored in release builds.
+const bool paranoid = false;
+
+#if defined(__clang__) || !defined(__GNUC__) || (__GNUC__ > 4) || \
+    (__GNUC__ == 4 && __GNUC_MINOR__ >= 4)
+}  // namespace
+#endif
 
-            return true;
-        }
+/** Document::Impl holds the Document state. Please see the file comment above for details
+ *  on the fields of Impl and how they are used to realize the implementation of mutable
+ *  BSON. Impl provides various utility methods to insert, lookup, and interrogate the
+ *  Elements, BSONObj objects, field names, and builders associated with the Document.
+ *
+ *  TODO: At some point, we could remove the firewall and inline the members of Impl into
+ *  Document.
+ */
+class Document::Impl {
+    MONGO_DISALLOW_COPYING(Impl);
+
+public:
+    Impl(Document::InPlaceMode inPlaceMode)
+        : _numElements(0),
+          _slowElements(),
+          _objects(),
+          _fieldNames(),
+          _leafBuf(),
+          _leafBuilder(_leafBuf),
+          _fieldNameScratch(),
+          _damages(),
+          _inPlaceMode(inPlaceMode) {
+        // We always have a BSONObj for the leaves, and we often have
+        // one for our base document, so reserve 2.
+        _objects.reserve(2);
+
+        // We always have at least one byte for the root field name, and we would like
+        // to be able to hold a few short field names without reallocation.
+        _fieldNames.reserve(8);
+
+        // We need an object at _objects[0] so that we can access leaf elements we
+        // construct with the leaf builder in the same way we access elements serialized in
+        // other BSONObjs. So we call asTempObj on the builder and store the result in slot
+        // 0.
+        dassert(_objects.size() == kLeafObjIdx);
+        _objects.push_back(_leafBuilder.asTempObj());
+        dassert(_leafBuf.len() != 0);
+    }
+
+    ~Impl() {
+        _leafBuilder.abandon();
+    }
+
+    void reset(Document::InPlaceMode inPlaceMode) {
+        // Clear out the state in the vectors.
+        _slowElements.clear();
+        _numElements = 0;
+
+        _objects.clear();
+        _fieldNames.clear();
+
+        // There is no way to reset the state of a BSONObjBuilder, so we need to call its
+        // dtor, reset the underlying buf, and re-invoke the constructor in-place.
+        _leafBuilder.abandon();
+        _leafBuilder.~BSONObjBuilder();
+        _leafBuf.reset();
+        new (&_leafBuilder) BSONObjBuilder(_leafBuf);
+
+        _fieldNameScratch.clear();
+        _damages.clear();
+        _inPlaceMode = inPlaceMode;
+
+        // Ensure that we start in the same state as the ctor would leave us in.
+        _objects.push_back(_leafBuilder.asTempObj());
+    }
+
+    // Obtain the ElementRep for the given rep id.
+    ElementRep& getElementRep(Element::RepIdx id) {
+        return const_cast<ElementRep&>(const_cast<const Impl*>(this)->getElementRep(id));
+    }
+
+    // Obtain the ElementRep for the given rep id.
+    const ElementRep& getElementRep(Element::RepIdx id) const {
+        dassert(id < _numElements);
+        if (id < kFastReps)
+            return _fastElements[id];
+        else
+            return _slowElements[id - kFastReps];
+    }
+
+    // Construct and return a new default initialized ElementRep. The RepIdx identifying
+    // the new rep is returned in the out parameter.
+    ElementRep& makeNewRep(Element::RepIdx* newIdx) {
+        const ElementRep defaultRep = {kInvalidObjIdx,
+                                       false,
+                                       false,
+                                       0,
+                                       0,
+                                       {Element::kInvalidRepIdx, Element::kInvalidRepIdx},
+                                       {Element::kInvalidRepIdx, Element::kInvalidRepIdx},
+                                       Element::kInvalidRepIdx,
+                                       -1};
+
+        const Element::RepIdx id = *newIdx = _numElements++;
+
+        if (id < kFastReps) {
+            return _fastElements[id] = defaultRep;
+        } else {
+            verify(id <= Element::kMaxRepIdx);
 
-        template<typename Builder>
-        void writeElement(Element::RepIdx repIdx, Builder* builder,
-                          const StringData* fieldName = NULL) const;
-
-        template<typename Builder>
-        void writeChildren(Element::RepIdx repIdx, Builder* builder) const;
-
-    private:
-
-        // Insert the given field name into the field name heap, and return an ID for this
-        // field name.
-        int32_t insertFieldName(StringData fieldName) {
-            const uint32_t id = _fieldNames.size();
-            if (!fieldName.empty())
-                _fieldNames.insert(
-                    _fieldNames.end(),
-                    fieldName.rawData(),
-                    fieldName.rawData() + fieldName.size());
-            _fieldNames.push_back('\0');
             if (kDebugBuild && paranoid) {
-                // Force names to new addresses to catch invalidation errors.
-                std::vector<char> new_fieldNames(_fieldNames);
-                _fieldNames.swap(new_fieldNames);
+                // Force all reps to new addresses to help catch invalid rep usage.
+                std::vector<ElementRep> newSlowElements(_slowElements);
+                _slowElements.swap(newSlowElements);
             }
-            return id;
-        }
-
-        // Retrieve the field name with the given id.
-        StringData getFieldName(uint32_t fieldNameId) const {
-            dassert(fieldNameId < _fieldNames.size());
-            return &_fieldNames[fieldNameId];
-        }
-
-        size_t _numElements;
-        ElementRep _fastElements[kFastReps];
-        std::vector<ElementRep> _slowElements;
-
-        std::vector<BSONObj> _objects;
-        std::vector<char> _fieldNames;
-
-        // We own a BufBuilder to avoid BSONObjBuilder's ref-count mechanism which would throw
-        // off our offset calculations.
-        BufBuilder _leafBuf;
-        BSONObjBuilder _leafBuilder;
-
-        // Sometimes, we need a temporary storage area for a fieldName, because the source of
-        // the fieldName is in the same buffer that we want to write to, potentially
-        // reallocating it. In such cases, we temporarily store the value here, rather than
-        // creating and destroying a string and its buffer each time.
-        std::string _fieldNameScratch;
-
-        // Queue of damage events and status bit for whether  in-place updates are possible.
-        DamageVector _damages;
-        Document::InPlaceMode _inPlaceMode;
-    };
-
-    Status Element::addSiblingLeft(Element e) {
-        verify(ok());
-        verify(e.ok());
-        verify(_doc == e._doc);
-
-        Document::Impl& impl = getDocument().getImpl();
-        ElementRep& newRep = impl.getElementRep(e._repIdx);
-
-        // check that new element roots a clean subtree.
-        if (!canAttach(e._repIdx, newRep))
-            return getAttachmentError(newRep);
-
-        ElementRep& thisRep = impl.getElementRep(_repIdx);
-
-        dassert(thisRep.parent != kOpaqueRepIdx);
-        if (thisRep.parent == kInvalidRepIdx)
-            return Status(
-                ErrorCodes::IllegalOperation,
-                "Attempt to add a sibling to an element without a parent");
-
-        ElementRep& parentRep = impl.getElementRep(thisRep.parent);
-        dassert(!impl.isLeaf(parentRep));
-
-        impl.disableInPlaceUpdates();
-
-        // The new element shares our parent.
-        newRep.parent = thisRep.parent;
-
-        // We are the new element's right sibling.
-        newRep.sibling.right = _repIdx;
-
-        // The new element's left sibling is our left sibling.
-        newRep.sibling.left = thisRep.sibling.left;
 
-        // If the new element has a left sibling after the adjustments above, then that left
-        // sibling must be updated to have the new element as its right sibling.
-        if (newRep.sibling.left != kInvalidRepIdx)
-            impl.getElementRep(thisRep.sibling.left).sibling.right = e._repIdx;
-
-        // The new element becomes our left sibling.
-        thisRep.sibling.left = e._repIdx;
-
-        // If we were our parent's left child, then we no longer are. Make the new right
-        // sibling the right child.
-        if (parentRep.child.left == _repIdx)
-            parentRep.child.left = e._repIdx;
-
-        impl.deserialize(thisRep.parent);
-
-        return Status::OK();
-    }
-
-    Status Element::addSiblingRight(Element e) {
-        verify(ok());
-        verify(e.ok());
-        verify(_doc == e._doc);
-
-        Document::Impl& impl = getDocument().getImpl();
-        ElementRep* newRep = &impl.getElementRep(e._repIdx);
-
-        // check that new element roots a clean subtree.
-        if (!canAttach(e._repIdx, *newRep))
-            return getAttachmentError(*newRep);
-
-        ElementRep* thisRep = &impl.getElementRep(_repIdx);
-
-        dassert(thisRep->parent != kOpaqueRepIdx);
-        if (thisRep->parent == kInvalidRepIdx)
-            return Status(
-                ErrorCodes::IllegalOperation,
-                "Attempt to add a sibling to an element without a parent");
-
-        ElementRep* parentRep = &impl.getElementRep(thisRep->parent);
-        dassert(!impl.isLeaf(*parentRep));
-
-        impl.disableInPlaceUpdates();
-
-        // If our current right sibling is opaque it needs to be resolved. This will invalidate
-        // our reps so we need to reacquire them.
-        Element::RepIdx rightSiblingIdx = thisRep->sibling.right;
-        if (rightSiblingIdx == kOpaqueRepIdx) {
-            rightSiblingIdx = impl.resolveRightSibling(_repIdx);
-            dassert(rightSiblingIdx != kOpaqueRepIdx);
-            newRep = &impl.getElementRep(e._repIdx);
-            thisRep = &impl.getElementRep(_repIdx);
-            parentRep = &impl.getElementRep(thisRep->parent);
+            return *_slowElements.insert(_slowElements.end(), defaultRep);
         }
-
-        // The new element shares our parent.
-        newRep->parent = thisRep->parent;
-
-        // We are the new element's left sibling.
-        newRep->sibling.left = _repIdx;
-
-        // The new element right sibling is our right sibling.
-        newRep->sibling.right = rightSiblingIdx;
-
-        // The new element becomes our right sibling.
-        thisRep->sibling.right = e._repIdx;
-
-        // If the new element has a right sibling after the adjustments above, then that right
-        // sibling must be updated to have the new element as its left sibling.
-        if (newRep->sibling.right != kInvalidRepIdx)
-            impl.getElementRep(rightSiblingIdx).sibling.left = e._repIdx;
-
-        // If we were our parent's right child, then we no longer are. Make the new right
-        // sibling the right child.
-        if (parentRep->child.right == _repIdx)
-            parentRep->child.right = e._repIdx;
-
-        impl.deserialize(thisRep->parent);
-
-        return Status::OK();
-    }
-
-    Status Element::remove() {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-
-        // We need to realize any opaque right sibling, because we are going to need to set its
-        // left sibling. Do this before acquiring thisRep since otherwise we would potentially
-        // invalidate it.
-        impl.resolveRightSibling(_repIdx);
-
-        ElementRep& thisRep = impl.getElementRep(_repIdx);
-
-        if (thisRep.parent == kInvalidRepIdx)
-            return Status(ErrorCodes::IllegalOperation, "trying to remove a parentless element");
-        impl.disableInPlaceUpdates();
-
-        // If our right sibling is not the end of the object, then set its left sibling to be
-        // our left sibling.
-        if (thisRep.sibling.right != kInvalidRepIdx)
-            impl.getElementRep(thisRep.sibling.right).sibling.left = thisRep.sibling.left;
-
-        // Similarly, if our left sibling is not the beginning of the obejct, then set its
-        // right sibling to be our right sibling.
-        if (thisRep.sibling.left != kInvalidRepIdx) {
-            ElementRep& leftRep = impl.getElementRep(thisRep.sibling.left);
-            leftRep.sibling.right = thisRep.sibling.right;
-        }
-
-        // If this element was our parent's right child, then our left sibling is the new right
-        // child.
-        ElementRep& parentRep = impl.getElementRep(thisRep.parent);
-        if (parentRep.child.right == _repIdx)
-            parentRep.child.right = thisRep.sibling.left;
-
-        // Similarly, if this element was our parent's left child, then our right sibling is
-        // the new left child.
-        if (parentRep.child.left == _repIdx)
-            parentRep.child.left = thisRep.sibling.right;
-
-        impl.deserialize(thisRep.parent);
-
-        // The Element becomes detached.
-        thisRep.parent = kInvalidRepIdx;
-        thisRep.sibling.left = kInvalidRepIdx;
-        thisRep.sibling.right = kInvalidRepIdx;
-
-        return Status::OK();
     }
 
-    Status Element::rename(StringData newName) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-
-        if (_repIdx == kRootRepIdx)
-            return Status(ErrorCodes::IllegalOperation,
-                          "Invalid attempt to rename the root element of a document");
-
-        dassert(impl.doesNotAlias(newName));
-
-        // TODO: Some rename operations may be possible to do in-place.
-        impl.disableInPlaceUpdates();
-
-        // Operations below may invalidate thisRep, so we may need to reacquire it.
-        ElementRep* thisRep = &impl.getElementRep(_repIdx);
-
-        // For non-leaf serialized elements, we can realize any opaque relatives and then
-        // convert ourselves to deserialized.
-        if (thisRep->objIdx != kInvalidObjIdx && !impl.isLeaf(*thisRep)) {
-
-            const bool array = (impl.getType(*thisRep) == mongo::Array);
-
-            // Realize any opaque right sibling or left child now, since otherwise we will lose
-            // the ability to do so.
-            impl.resolveLeftChild(_repIdx);
-            impl.resolveRightSibling(_repIdx);
-
-            // The resolve calls above may have invalidated thisRep, we need to reacquire it.
-            thisRep = &impl.getElementRep(_repIdx);
-
-            // Set this up as a non-supported deserialized element. We will set the fieldName
-            // in the else clause in the block below.
-            impl.deserialize(_repIdx);
-
-            thisRep->array = array;
-
-            // TODO: If we ever want to be able to add to the left or right of an opaque object
-            // without expanding, this may need to change.
-            thisRep->objIdx = kInvalidObjIdx;
-        }
-
-        if (impl.hasValue(*thisRep)) {
-            // For leaf elements we just create a new Element with the current value and
-            // replace. Note that the 'setValue' call below will invalidate thisRep.
-            Element replacement = _doc->makeElementWithNewFieldName(newName, *this);
-            setValue(replacement._repIdx);
-        } else {
-            // The easy case: just update what our field name offset refers to.
-            impl.insertFieldName(*thisRep, newName);
-        }
+    // Insert a new ElementRep for a leaf element at the given offset and return its ID.
+    Element::RepIdx insertLeafElement(int offset, int fieldNameSize = -1) {
+        // BufBuilder hands back sizes in 'int's.
+        Element::RepIdx inserted;
+        ElementRep& rep = makeNewRep(&inserted);
 
-        return Status::OK();
+        rep.fieldNameSize = fieldNameSize;
+        rep.objIdx = kLeafObjIdx;
+        rep.serialized = true;
+        dassert(offset >= 0);
+        // TODO: Is this a legitimate possibility?
+        dassert(static_cast<unsigned int>(offset) < std::numeric_limits<uint32_t>::max());
+        rep.offset = offset;
+        _objects[kLeafObjIdx] = _leafBuilder.asTempObj();
+        return inserted;
     }
 
-    Element Element::leftChild() const {
-        verify(ok());
-
-        // Capturing Document::Impl by non-const ref exploits the constness loophole
-        // created by our Impl so that we can let leftChild be lazily evaluated, even for a
-        // const Element.
-        Document::Impl& impl = _doc->getImpl();
-        const Element::RepIdx leftChildIdx = impl.resolveLeftChild(_repIdx);
-        dassert(leftChildIdx != kOpaqueRepIdx);
-        return Element(_doc, leftChildIdx);
+    // Obtain the object builder for the leaves.
+    BSONObjBuilder& leafBuilder() {
+        return _leafBuilder;
     }
 
-    Element Element::rightChild() const {
-        verify(ok());
-
-        // Capturing Document::Impl by non-const ref exploits the constness loophole
-        // created by our Impl so that we can let leftChild be lazily evaluated, even for a
-        // const Element.
-        Document::Impl& impl = _doc->getImpl();
-        const Element::RepIdx rightChildIdx = impl.resolveRightChild(_repIdx);
-        dassert(rightChildIdx != kOpaqueRepIdx);
-        return Element(_doc, rightChildIdx);
+    // Obtain the BSONObj for the given object id.
+    BSONObj& getObject(ElementRep::ObjIdx objIdx) {
+        dassert(objIdx < _objects.size());
+        return _objects[objIdx];
     }
 
-    bool Element::hasChildren() const {
-        verify(ok());
-        // Capturing Document::Impl by non-const ref exploits the constness loophole
-        // created by our Impl so that we can let leftChild be lazily evaluated, even for a
-        // const Element.
-        Document::Impl& impl = _doc->getImpl();
-        return impl.resolveLeftChild(_repIdx) != kInvalidRepIdx;
+    // Obtain the BSONObj for the given object id.
+    const BSONObj& getObject(ElementRep::ObjIdx objIdx) const {
+        dassert(objIdx < _objects.size());
+        return _objects[objIdx];
     }
 
-    Element Element::leftSibling(size_t distance) const {
-        verify(ok());
-        const Document::Impl& impl = getDocument().getImpl();
-        Element::RepIdx current = _repIdx;
-        while ((current != kInvalidRepIdx) && (distance-- != 0)) {
-            // We are (currently) never left opaque, so don't need to resolve.
-            current = impl.getElementRep(current).sibling.left;
+    // Insert the given BSONObj and return an ID for it.
+    ElementRep::ObjIdx insertObject(const BSONObj& newObj) {
+        const size_t objIdx = _objects.size();
+        verify(objIdx <= kMaxObjIdx);
+        _objects.push_back(newObj);
+        if (kDebugBuild && paranoid) {
+            // Force reallocation to catch use after invalidation.
+            std::vector<BSONObj> new_objects(_objects);
+            _objects.swap(new_objects);
         }
-        return Element(_doc, current);
+        return objIdx;
     }
 
-    Element Element::rightSibling(size_t distance) const {
-        verify(ok());
-
-        // Capturing Document::Impl by non-const ref exploits the constness loophole
-        // created by our Impl so that we can let rightSibling be lazily evaluated, even for a
-        // const Element.
-        Document::Impl& impl = _doc->getImpl();
-        Element::RepIdx current = _repIdx;
-        while ((current != kInvalidRepIdx) && (distance-- != 0))
-            current = impl.resolveRightSibling(current);
-        return Element(_doc, current);
+    // Given a RepIdx, return the BSONElement that it represents.
+    BSONElement getSerializedElement(const ElementRep& rep) const {
+        const BSONObj& object = getObject(rep.objIdx);
+        return BSONElement(
+            object.objdata() + rep.offset, rep.fieldNameSize, BSONElement::FieldNameSizeTag());
     }
 
-    Element Element::parent() const {
-        verify(ok());
-        const Document::Impl& impl = getDocument().getImpl();
-        const Element::RepIdx parentIdx = impl.getElementRep(_repIdx).parent;
-        dassert(parentIdx != kOpaqueRepIdx);
-        return Element(_doc, parentIdx);
+    // A helper method that either inserts the field name into the field name heap and
+    // updates element.
+    void insertFieldName(ElementRep& rep, StringData fieldName) {
+        dassert(!rep.serialized);
+        rep.offset = insertFieldName(fieldName);
     }
 
-    Element Element::findNthChild(size_t n) const {
-        verify(ok());
-        Document::Impl& impl = _doc->getImpl();
-        Element::RepIdx current = _repIdx;
-        current = impl.resolveLeftChild(current);
-        while ((current != kInvalidRepIdx) && (n-- != 0))
-            current = impl.resolveRightSibling(current);
-        return Element(_doc, current);
-    }
+    // Retrieve the fieldName, given a rep.
+    StringData getFieldName(const ElementRep& rep) const {
+        // The root element has no field name.
+        if (&rep == &getElementRep(kRootRepIdx))
+            return StringData();
 
-    Element Element::findFirstChildNamed(StringData name) const {
-        verify(ok());
-        Document::Impl& impl = _doc->getImpl();
-        Element::RepIdx current = _repIdx;
-        current = impl.resolveLeftChild(current);
-        // TODO: Could DRY this loop with the identical logic in findElementNamed.
-        while ((current != kInvalidRepIdx) &&
-               (impl.getFieldName(impl.getElementRep(current)) != name))
-            current = impl.resolveRightSibling(current);
-        return Element(_doc, current);
-    }
+        if (rep.serialized || (rep.objIdx != kInvalidObjIdx))
+            return getSerializedElement(rep).fieldNameStringData();
 
-    Element Element::findElementNamed(StringData name) const {
-        verify(ok());
-        Document::Impl& impl = _doc->getImpl();
-        Element::RepIdx current = _repIdx;
-        while ((current != kInvalidRepIdx) &&
-               (impl.getFieldName(impl.getElementRep(current)) != name))
-            current = impl.resolveRightSibling(current);
-        return Element(_doc, current);
+        return getFieldName(rep.offset);
     }
 
-    size_t Element::countSiblingsLeft() const {
-        verify(ok());
-        const Document::Impl& impl = getDocument().getImpl();
-        Element::RepIdx current = _repIdx;
-        size_t result = 0;
-        while (true) {
-            // We are (currently) never left opaque, so don't need to resolve.
-            current = impl.getElementRep(current).sibling.left;
-            if (current == kInvalidRepIdx)
-                break;
-            ++result;
+    StringData getFieldNameForNewElement(const ElementRep& rep) {
+        StringData result = getFieldName(rep);
+        if (rep.objIdx == kLeafObjIdx) {
+            _fieldNameScratch.assign(result.rawData(), result.size());
+            result = StringData(_fieldNameScratch);
         }
         return result;
     }
 
-    size_t Element::countSiblingsRight() const {
-        verify(ok());
-        Document::Impl& impl = _doc->getImpl();
-        Element::RepIdx current = _repIdx;
-        size_t result = 0;
-        while (true) {
-            current = impl.resolveRightSibling(current);
-            if (current == kInvalidRepIdx)
-                break;
-            ++result;
-        }
-        return result;
-    }
+    // Retrieve the type, given a rep.
+    BSONType getType(const ElementRep& rep) const {
+        // The root element is always an Object.
+        if (&rep == &getElementRep(kRootRepIdx))
+            return mongo::Object;
 
-    size_t Element::countChildren() const {
-        verify(ok());
-        Document::Impl& impl = _doc->getImpl();
-        Element::RepIdx current = _repIdx;
-        current = impl.resolveLeftChild(current);
-        size_t result = 0;
-        while (current != kInvalidRepIdx) {
-            ++result;
-            current = impl.resolveRightSibling(current);
-        }
-        return result;
-    }
+        if (rep.serialized || (rep.objIdx != kInvalidObjIdx))
+            return getSerializedElement(rep).type();
 
-    bool Element::hasValue() const {
-        verify(ok());
-        const Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        return impl.hasValue(thisRep);
+        return rep.array ? mongo::Array : mongo::Object;
     }
 
-    bool Element::isNumeric() const {
-        verify(ok());
-        const Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const BSONType type = impl.getType(thisRep);
-        return ((type == mongo::NumberLong) ||
-                (type == mongo::NumberInt) ||
-                (type == mongo::NumberDouble));
+    static bool isLeafType(BSONType type) {
+        return ((type != mongo::Object) && (type != mongo::Array));
     }
 
-    bool Element::isIntegral() const {
-        verify(ok());
-        const Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const BSONType type = impl.getType(thisRep);
-        return ((type == mongo::NumberLong) ||
-                (type == mongo::NumberInt));
+    // Returns true if rep is not an object or array.
+    bool isLeaf(const ElementRep& rep) const {
+        return isLeafType(getType(rep));
     }
 
-    const BSONElement Element::getValue() const {
-        verify(ok());
-        const Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        if (impl.hasValue(thisRep))
-            return impl.getSerializedElement(thisRep);
-        return BSONElement();
+    bool isLeaf(const BSONElement& elt) const {
+        return isLeafType(elt.type());
     }
 
-    SafeNum Element::getValueSafeNum() const {
-        switch (getType()) {
-        case mongo::NumberInt:
-            return static_cast<int>(getValueInt());
-        case mongo::NumberLong:
-            return static_cast<long long int>(getValueLong());
-        case mongo::NumberDouble:
-            return getValueDouble();
-        default:
-            return SafeNum();
-        }
-    }
-
-    int Element::compareWithElement(const ConstElement& other, bool considerFieldName) const {
-        verify(ok());
-        verify(other.ok());
-
-        // Short circuit a tautological compare.
-        if ((_repIdx == other.getIdx()) && (_doc == &other.getDocument()))
-            return 0;
-
-        // If either Element can represent its current value as a BSONElement, then we can
-        // obtain its value and use compareWithBSONElement. If both Elements have a
-        // representation as a BSONElement, compareWithBSONElement will notice that the first
-        // argument has a value and delegate to BSONElement::woCompare.
+    // Returns true if rep's value can be provided as a BSONElement.
+    bool hasValue(const ElementRep& rep) const {
+        // The root element may be marked serialized, but it doesn't have a BSONElement
+        // representation.
+        if (&rep == &getElementRep(kRootRepIdx))
+            return false;
 
-        const Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-
-        // Subtle: we must negate the comparison result here because we are reversing the
-        // argument order in this call.
-        //
-        // TODO: Andy has suggested that this may not be legal since woCompare is not reflexive
-        // in all cases.
-        if (impl.hasValue(thisRep))
-            return -other.compareWithBSONElement(
-                impl.getSerializedElement(thisRep), considerFieldName);
-
-        const Document::Impl& oimpl = other.getDocument().getImpl();
-        const ElementRep& otherRep = oimpl.getElementRep(other.getIdx());
-
-        if (oimpl.hasValue(otherRep))
-            return compareWithBSONElement(
-                oimpl.getSerializedElement(otherRep), considerFieldName);
-
-        // Leaf elements should always have a value, so we should only be dealing with Objects
-        // or Arrays here.
-        dassert(!impl.isLeaf(thisRep));
-        dassert(!oimpl.isLeaf(otherRep));
-
-        // Obtain the canonical types for this Element and the BSONElement, if they are
-        // different use the difference as the result. Please see BSONElement::woCompare for
-        // details. We know that thisRep is not a number, so we don't need to check that
-        // particular case.
-        const int leftCanonType = canonicalizeBSONType(impl.getType(thisRep));
-        const int rightCanonType = canonicalizeBSONType(oimpl.getType(otherRep));
-        const int diffCanon = leftCanonType - rightCanonType;
-        if (diffCanon != 0)
-            return diffCanon;
-
-        // If we are considering field names, and the field names do not compare as equal,
-        // return the field name ordering as the element ordering.
-        if (considerFieldName) {
-            const int fnamesComp = impl.getFieldName(thisRep).compare(oimpl.getFieldName(otherRep));
-            if (fnamesComp != 0)
-                return fnamesComp;
-        }
-
-        const bool considerChildFieldNames =
-            (impl.getType(thisRep) != mongo::Array) &&
-            (oimpl.getType(otherRep) != mongo::Array);
-
-        // We are dealing with either two objects, or two arrays. We need to consider the child
-        // elements individually. We walk two iterators forward over the children and compare
-        // them. Length mismatches are handled by checking early for reaching the end of the
-        // children.
-        ConstElement thisIter = leftChild();
-        ConstElement otherIter = other.leftChild();
-
-        while (true) {
-            if (!thisIter.ok())
-                return !otherIter.ok() ? 0 : -1;
-            if (!otherIter.ok())
-                return 1;
-
-            const int result = thisIter.compareWithElement(otherIter, considerChildFieldNames);
-            if (result != 0)
-                return result;
-
-            thisIter = thisIter.rightSibling();
-            otherIter = otherIter.rightSibling();
-        }
+        return rep.serialized;
     }
 
-    int Element::compareWithBSONElement(const BSONElement& other, bool considerFieldName) const {
-        verify(ok());
-
-        const Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-
-        // If we have a representation as a BSONElement, we can just use BSONElement::woCompare
-        // to do the entire comparison.
-        if (impl.hasValue(thisRep))
-            return impl.getSerializedElement(thisRep).woCompare(other, considerFieldName);
-
-        // Leaf elements should always have a value, so we should only be dealing with Objects
-        // or Arrays here.
-        dassert(!impl.isLeaf(thisRep));
-
-        // Obtain the canonical types for this Element and the BSONElement, if they are
-        // different use the difference as the result. Please see BSONElement::woCompare for
-        // details. We know that thisRep is not a number, so we don't need to check that
-        // particular case.
-        const int leftCanonType = canonicalizeBSONType(impl.getType(thisRep));
-        const int rightCanonType = canonicalizeBSONType(other.type());
-        const int diffCanon = leftCanonType - rightCanonType;
-        if (diffCanon != 0)
-            return diffCanon;
-
-        // If we are considering field names, and the field names do not compare as equal,
-        // return the field name ordering as the element ordering.
-        if (considerFieldName) {
-            const int fnamesComp = impl.getFieldName(thisRep).compare(other.fieldNameStringData());
-            if (fnamesComp != 0)
-                return fnamesComp;
-        }
-
-        const bool considerChildFieldNames =
-            (impl.getType(thisRep) != mongo::Array) &&
-            (other.type() != mongo::Array);
+    // Return the index of the left child of the Element with index 'index', resolving the
+    // left child to a realized Element if it is currently opaque. This may also cause the
+    // parent elements child.right entry to be updated.
+    Element::RepIdx resolveLeftChild(Element::RepIdx index) {
+        dassert(index != Element::kInvalidRepIdx);
+        dassert(index != Element::kOpaqueRepIdx);
 
-        return compareWithBSONObj(other.Obj(), considerChildFieldNames);
-    }
-
-    int Element::compareWithBSONObj(const BSONObj& other, bool considerFieldName) const {
-        verify(ok());
-
-        const Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        verify(!impl.isLeaf(thisRep));
-
-        // We are dealing with either two objects, or two arrays. We need to consider the child
-        // elements individually. We walk two iterators forward over the children and compare
-        // them. Length mismatches are handled by checking early for reaching the end of the
-        // children.
-        ConstElement thisIter = leftChild();
-        BSONObjIterator otherIter(other);
-
-        while (true) {
-            const BSONElement otherVal = otherIter.next();
-
-            if (!thisIter.ok())
-                return otherVal.eoo() ? 0 : -1;
-            if (otherVal.eoo())
-                return 1;
+        // If the left child is anything other than opaque, then we are done here.
+        ElementRep* rep = &getElementRep(index);
+        if (rep->child.left != Element::kOpaqueRepIdx)
+            return rep->child.left;
 
-            const int result = thisIter.compareWithBSONElement(otherVal, considerFieldName);
-            if (result != 0)
-                return result;
+        // It should be impossible to have an opaque left child and be non-serialized,
+        dassert(rep->serialized);
+        BSONElement childElt = (hasValue(*rep) ? getSerializedElement(*rep).embeddedObject()
+                                               : getObject(rep->objIdx)).firstElement();
 
-            thisIter = thisIter.rightSibling();
-        }
-    }
+        if (!childElt.eoo()) {
+            // Do this now before other writes so compiler can exploit knowing
+            // that we are not eoo.
+            const int32_t fieldNameSize = childElt.fieldNameSize();
 
-    void Element::writeTo(BSONObjBuilder* const builder) const {
-        verify(ok());
-        const Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        verify(impl.getType(thisRep) == mongo::Object);
-        if (thisRep.parent == kInvalidRepIdx && _repIdx == kRootRepIdx) {
-            // If this is the root element, then we need to handle it differently, since it
-            // doesn't have a field name and should embed directly, rather than as an object.
-            impl.writeChildren(_repIdx, builder);
+            Element::RepIdx inserted;
+            ElementRep& newRep = makeNewRep(&inserted);
+            // Calling makeNewRep invalidates rep since it may cause a reallocation of
+            // the element vector. After calling insertElement, we reacquire rep.
+            rep = &getElementRep(index);
+
+            newRep.serialized = true;
+            newRep.objIdx = rep->objIdx;
+            newRep.offset = getElementOffset(getObject(rep->objIdx), childElt);
+            newRep.parent = index;
+            newRep.sibling.right = Element::kOpaqueRepIdx;
+            // If this new object has possible substructure, mark its children as opaque.
+            if (!isLeaf(childElt)) {
+                newRep.child.left = Element::kOpaqueRepIdx;
+                newRep.child.right = Element::kOpaqueRepIdx;
+            }
+            newRep.fieldNameSize = fieldNameSize;
+            rep->child.left = inserted;
         } else {
-            impl.writeElement(_repIdx, builder);
+            rep->child.left = Element::kInvalidRepIdx;
+            rep->child.right = Element::kInvalidRepIdx;
         }
-    }
 
-    void Element::writeArrayTo(BSONArrayBuilder* const builder) const {
-        verify(ok());
-        const Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        verify(impl.getType(thisRep) == mongo::Array);
-        return impl.writeChildren(_repIdx, builder);
+        dassert(rep->child.left != Element::kOpaqueRepIdx);
+        return rep->child.left;
     }
 
-    Status Element::setValueDouble(const double value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-        ElementRep thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementDouble(fieldName, value);
-        return setValue(newValue._repIdx);
-    }
+    // Return the index of the right child of the Element with index 'index', resolving any
+    // opaque nodes. Note that this may require resolving all of the right siblings of the
+    // left child.
+    Element::RepIdx resolveRightChild(Element::RepIdx index) {
+        dassert(index != Element::kInvalidRepIdx);
+        dassert(index != Element::kOpaqueRepIdx);
 
-    Status Element::setValueString(StringData value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
+        Element::RepIdx current = getElementRep(index).child.right;
+        if (current == Element::kOpaqueRepIdx) {
+            current = resolveLeftChild(index);
+            while (current != Element::kInvalidRepIdx) {
+                Element::RepIdx next = resolveRightSibling(current);
+                if (next == Element::kInvalidRepIdx)
+                    break;
+                current = next;
+            }
 
-        dassert(impl.doesNotAlias(value));
+            // The resolveRightSibling calls should have eventually updated this nodes right
+            // child pointer to point to the node we are about to return.
+            dassert(getElementRep(index).child.right == current);
+        }
 
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementString(fieldName, value);
-        return setValue(newValue._repIdx);
+        return current;
     }
 
-    Status Element::setValueObject(const BSONObj& value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
+    // Return the index of the right sibling of the Element with index 'index', resolving
+    // the right sibling to a realized Element if it is currently opaque.
+    Element::RepIdx resolveRightSibling(Element::RepIdx index) {
+        dassert(index != Element::kInvalidRepIdx);
+        dassert(index != Element::kOpaqueRepIdx);
 
-        dassert(impl.doesNotAlias(value));
-
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementObject(fieldName, value);
-        return setValue(newValue._repIdx);
-    }
+        // If the right sibling is anything other than opaque, then we are done here.
+        ElementRep* rep = &getElementRep(index);
+        if (rep->sibling.right != Element::kOpaqueRepIdx)
+            return rep->sibling.right;
 
-    Status Element::setValueArray(const BSONObj& value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
+        BSONElement elt = getSerializedElement(*rep);
+        BSONElement rightElt(elt.rawdata() + elt.size());
 
-        dassert(impl.doesNotAlias(value));
+        if (!rightElt.eoo()) {
+            // Do this now before other writes so compiler can exploit knowing
+            // that we are not eoo.
+            const int32_t fieldNameSize = rightElt.fieldNameSize();
 
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementArray(fieldName, value);
-        return setValue(newValue._repIdx);
+            Element::RepIdx inserted;
+            ElementRep& newRep = makeNewRep(&inserted);
+            // Calling makeNewRep invalidates rep since it may cause a reallocation of
+            // the element vector. After calling insertElement, we reacquire rep.
+            rep = &getElementRep(index);
+
+            newRep.serialized = true;
+            newRep.objIdx = rep->objIdx;
+            newRep.offset = getElementOffset(getObject(rep->objIdx), rightElt);
+            newRep.parent = rep->parent;
+            newRep.sibling.left = index;
+            newRep.sibling.right = Element::kOpaqueRepIdx;
+            // If this new object has possible substructure, mark its children as opaque.
+            if (!isLeaf(rightElt)) {
+                newRep.child.left = Element::kOpaqueRepIdx;
+                newRep.child.right = Element::kOpaqueRepIdx;
+            }
+            newRep.fieldNameSize = fieldNameSize;
+            rep->sibling.right = inserted;
+        } else {
+            rep->sibling.right = Element::kInvalidRepIdx;
+            // If we have found the end of this object, then our (necessarily existing)
+            // parent's necessarily opaque right child is now determined to be us.
+            dassert(rep->parent <= Element::kMaxRepIdx);
+            ElementRep& parentRep = getElementRep(rep->parent);
+            dassert(parentRep.child.right == Element::kOpaqueRepIdx);
+            parentRep.child.right = index;
+        }
+
+        dassert(rep->sibling.right != Element::kOpaqueRepIdx);
+        return rep->sibling.right;
+    }
+
+    // Find the ElementRep at index 'index', and mark it and all of its currently
+    // serialized parents as non-serialized.
+    void deserialize(Element::RepIdx index) {
+        while (index != Element::kInvalidRepIdx) {
+            ElementRep& rep = getElementRep(index);
+            // It does not make sense for leaf Elements to become deserialized, and
+            // requests to do so indicate a bug in the implementation of the library.
+            dassert(!isLeaf(rep));
+            if (!rep.serialized)
+                break;
+            rep.serialized = false;
+            index = rep.parent;
+        }
     }
 
-    Status Element::setValueBinary(const uint32_t len, mongo::BinDataType binType,
-                                   const void* const data) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-
-        // TODO: Alias check for binary data?
-
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementBinary(
-            fieldName, len, binType, data);
-        return setValue(newValue._repIdx);
+    inline bool doesNotAlias(StringData s) const {
+        // StringData may come from either the field name heap or the leaf builder.
+        return doesNotAliasLeafBuilder(s) && !inFieldNameHeap(s.rawData());
     }
 
-    Status Element::setValueUndefined() {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementUndefined(fieldName);
-        return setValue(newValue._repIdx);
+    inline bool doesNotAliasLeafBuilder(StringData s) const {
+        return !inLeafBuilder(s.rawData());
     }
 
-    Status Element::setValueOID(const OID value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementOID(fieldName, value);
-        return setValue(newValue._repIdx);
+    inline bool doesNotAlias(const BSONElement& e) const {
+        // A BSONElement could alias the leaf builder.
+        return !inLeafBuilder(e.rawdata());
     }
 
-    Status Element::setValueBool(const bool value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-        ElementRep thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementBool(fieldName, value);
-        return setValue(newValue._repIdx);
+    inline bool doesNotAlias(const BSONObj& o) const {
+        // A BSONObj could alias the leaf buildr.
+        return !inLeafBuilder(o.objdata());
     }
 
-    Status Element::setValueDate(const Date_t value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementDate(fieldName, value);
-        return setValue(newValue._repIdx);
+    // Returns true if 'data' points within the leaf BufBuilder.
+    inline bool inLeafBuilder(const char* data) const {
+        // TODO: Write up something documenting that the following is technically UB due
+        // to illegality of comparing pointers to different aggregates for ordering. Also,
+        // do we need to do anything to prevent the optimizer from compiling this out on
+        // that basis? I've seen clang do that. We may need to declare these volatile. On
+        // the other hand, these should only be being called under a dassert, so the
+        // optimizer is maybe not in play, and the UB is unlikely to be a problem in
+        // practice.
+        const char* const start = _leafBuf.buf();
+        const char* const end = start + _leafBuf.len();
+        return (data >= start) && (data < end);
     }
 
-    Status Element::setValueNull() {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementNull(fieldName);
-        return setValue(newValue._repIdx);
+    // Returns true if 'data' points within the field name heap.
+    inline bool inFieldNameHeap(const char* data) const {
+        if (_fieldNames.empty())
+            return false;
+        const char* const start = &_fieldNames.front();
+        const char* const end = &_fieldNames.back();
+        return (data >= start) && (data < end);
     }
 
-    Status Element::setValueRegex(StringData re, StringData flags) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-
-        dassert(impl.doesNotAlias(re));
-        dassert(impl.doesNotAlias(flags));
-
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementRegex(fieldName, re, flags);
-        return setValue(newValue._repIdx);
+    void reserveDamageEvents(size_t expectedEvents) {
+        _damages.reserve(expectedEvents);
     }
 
-    Status Element::setValueDBRef(StringData ns, const OID oid) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-
-        dassert(impl.doesNotAlias(ns));
-
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementDBRef(fieldName, ns, oid);
-        return setValue(newValue._repIdx);
-    }
+    bool getInPlaceUpdates(DamageVector* damages, const char** source, size_t* size) {
+        // If some operations were not in-place, set source to NULL and return false to
+        // inform upstream that we are not returning in-place result data.
+        if (_inPlaceMode == Document::kInPlaceDisabled) {
+            damages->clear();
+            *source = NULL;
+            if (size)
+                *size = 0;
+            return false;
+        }
 
-    Status Element::setValueCode(StringData value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
+        // Set up the source and source size out parameters.
+        *source = _objects[0].objdata();
+        if (size)
+            *size = _objects[0].objsize();
 
-        dassert(impl.doesNotAlias(value));
+        // Swap our damage event queue with upstream, and reset ours to an empty vector. In
+        // princple, we can do another round of in-place updates.
+        damages->swap(_damages);
+        _damages.clear();
 
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementCode(fieldName, value);
-        return setValue(newValue._repIdx);
+        return true;
     }
 
-    Status Element::setValueSymbol(StringData value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-
-        dassert(impl.doesNotAlias(value));
-
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementSymbol(fieldName, value);
-        return setValue(newValue._repIdx);
+    void disableInPlaceUpdates() {
+        _inPlaceMode = Document::kInPlaceDisabled;
     }
 
-    Status Element::setValueCodeWithScope(StringData code, const BSONObj& scope) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-
-        dassert(impl.doesNotAlias(code));
-        dassert(impl.doesNotAlias(scope));
-
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementCodeWithScope(
-            fieldName, code, scope);
-        return setValue(newValue._repIdx);
+    Document::InPlaceMode getCurrentInPlaceMode() const {
+        return _inPlaceMode;
     }
 
-    Status Element::setValueInt(const int32_t value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-        ElementRep thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementInt(fieldName, value);
-        return setValue(newValue._repIdx);
+    bool isInPlaceModeEnabled() const {
+        return getCurrentInPlaceMode() == Document::kInPlaceEnabled;
     }
 
-    Status Element::setValueTimestamp(const Timestamp value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementTimestamp(fieldName, value);
-        return setValue(newValue._repIdx);
+    void recordDamageEvent(DamageEvent::OffsetSizeType targetOffset,
+                           DamageEvent::OffsetSizeType sourceOffset,
+                           size_t size) {
+        _damages.push_back(DamageEvent());
+        _damages.back().targetOffset = targetOffset;
+        _damages.back().sourceOffset = sourceOffset;
+        _damages.back().size = size;
+        if (kDebugBuild && paranoid) {
+            // Force damage events to new addresses to catch invalidation errors.
+            DamageVector new_damages(_damages);
+            _damages.swap(new_damages);
+        }
     }
 
-    Status Element::setValueLong(const int64_t value) {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-        ElementRep thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementLong(fieldName, value);
-        return setValue(newValue._repIdx);
-    }
+    // Check all preconditions on doing an in-place update, except for size match.
+    bool canUpdateInPlace(const ElementRep& sourceRep, const ElementRep& targetRep) {
+        // NOTE: CodeWScope might arguably be excluded since it has substructure, but
+        // mutable doesn't permit navigation into its document, so we can handle it.
 
-    Status Element::setValueMinKey() {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementMinKey(fieldName);
-        return setValue(newValue._repIdx);
-    }
+        // We can only do an in-place update to an element that is serialized and is not in
+        // the leaf heap.
+        //
+        // TODO: In the future, we can replace values in the leaf heap if they are of the
+        // same size as the origin was. For now, we don't support that.
+        if (!hasValue(targetRep) || (targetRep.objIdx == kLeafObjIdx))
+            return false;
+
+        // sourceRep should be newly created, so it must have a value representation.
+        dassert(hasValue(sourceRep));
+
+        // For a target that has substructure, we only permit in-place updates if there
+        // cannot be ElementReps that reference data within the target. We don't need to
+        // worry about ElementReps for source, since it is newly created. The only way
+        // there can be ElementReps referring into substructure is if the Element has
+        // non-empty non-opaque child references.
+        if (!isLeaf(targetRep)) {
+            if (((targetRep.child.left != Element::kOpaqueRepIdx) &&
+                 (targetRep.child.left != Element::kInvalidRepIdx)) ||
+                ((targetRep.child.right != Element::kOpaqueRepIdx) &&
+                 (targetRep.child.right != Element::kInvalidRepIdx)))
+                return false;
+        }
 
-    Status Element::setValueMaxKey() {
-        verify(ok());
-        Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementMaxKey(fieldName);
-        return setValue(newValue._repIdx);
+        return true;
     }
 
-    Status Element::setValueBSONElement(const BSONElement& value) {
-        verify(ok());
-
-        if (value.type() == mongo::EOO)
-            return Status(ErrorCodes::IllegalOperation, "Can't set Element value to EOO");
-
-        Document::Impl& impl = getDocument().getImpl();
+    template <typename Builder>
+    void writeElement(Element::RepIdx repIdx,
+                      Builder* builder,
+                      const StringData* fieldName = NULL) const;
 
-        dassert(impl.doesNotAlias(value));
-
-        ElementRep thisRep = impl.getElementRep(_repIdx);
-        const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
-        Element newValue = getDocument().makeElementWithNewFieldName(fieldName, value);
-        return setValue(newValue._repIdx);
-    }
+    template <typename Builder>
+    void writeChildren(Element::RepIdx repIdx, Builder* builder) const;
 
-    Status Element::setValueSafeNum(const SafeNum value) {
-        verify(ok());
-        switch (value.type()) {
-        case mongo::NumberInt:
-            return setValueInt(value._value.int32Val);
-        case mongo::NumberLong:
-            return setValueLong(value._value.int64Val);
-        case mongo::NumberDouble:
-            return setValueDouble(value._value.doubleVal);
-        default:
-            return Status(
-                ErrorCodes::UnsupportedFormat,
-                "Don't know how to handle unexpected SafeNum type");
+private:
+    // Insert the given field name into the field name heap, and return an ID for this
+    // field name.
+    int32_t insertFieldName(StringData fieldName) {
+        const uint32_t id = _fieldNames.size();
+        if (!fieldName.empty())
+            _fieldNames.insert(
+                _fieldNames.end(), fieldName.rawData(), fieldName.rawData() + fieldName.size());
+        _fieldNames.push_back('\0');
+        if (kDebugBuild && paranoid) {
+            // Force names to new addresses to catch invalidation errors.
+            std::vector<char> new_fieldNames(_fieldNames);
+            _fieldNames.swap(new_fieldNames);
         }
+        return id;
     }
 
-    BSONType Element::getType() const {
-        verify(ok());
-        const Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        return impl.getType(thisRep);
+    // Retrieve the field name with the given id.
+    StringData getFieldName(uint32_t fieldNameId) const {
+        dassert(fieldNameId < _fieldNames.size());
+        return &_fieldNames[fieldNameId];
     }
 
-    StringData Element::getFieldName() const {
-        verify(ok());
-        const Document::Impl& impl = getDocument().getImpl();
-        const ElementRep& thisRep = impl.getElementRep(_repIdx);
-        return impl.getFieldName(thisRep);
-    }
+    size_t _numElements;
+    ElementRep _fastElements[kFastReps];
+    std::vector<ElementRep> _slowElements;
 
-    Status Element::addChild(Element e, bool front) {
-        // No need to verify(ok()) since we are only called from methods that have done so.
-        dassert(ok());
-
-        verify(e.ok());
-        verify(_doc == e._doc);
-
-        Document::Impl& impl = getDocument().getImpl();
-        ElementRep& newRep = impl.getElementRep(e._repIdx);
-
-        // check that new element roots a clean subtree.
-        if (!canAttach(e._repIdx, newRep))
-            return getAttachmentError(newRep);
-
-        // Check that this element is eligible for children.
-        ElementRep& thisRep = impl.getElementRep(_repIdx);
-        if (impl.isLeaf(thisRep))
-            return Status(
-                ErrorCodes::IllegalOperation,
-                "Attempt to add a child element to a non-object element");
-
-        impl.disableInPlaceUpdates();
-
-        // TODO: In both of the following cases, we call two public API methods each. We can
-        // probably do better by writing this explicitly here and drying it with the public
-        // addSiblingLeft and addSiblingRight implementations.
-        if (front) {
-            // TODO: It is cheap to get the left child. However, it still means creating a rep
-            // for it. Can we do better?
-            Element lc = leftChild();
-            if (lc.ok())
-                return lc.addSiblingLeft(e);
-        } else {
-            // TODO: It is expensive to get the right child, since we have to build reps for
-            // all of the opaque children. But in principle, we don't really need them. Could
-            // we potentially add this element as a right child, leaving its left sibling
-            // opaque? We would at minimum need to update leftSibling, which currently assumes
-            // that your left sibling is never opaque. But adding new Elements to the end is a
-            // quite common operation, so it would be nice if we could do this efficiently.
-            Element rc = rightChild();
-            if (rc.ok())
-                return rc.addSiblingRight(e);
-        }
+    std::vector<BSONObj> _objects;
+    std::vector<char> _fieldNames;
 
-        // It must be the case that we have no children, so the new element becomes both the
-        // right and left child of this node.
-        dassert((thisRep.child.left == kInvalidRepIdx) && (thisRep.child.right == kInvalidRepIdx));
-        thisRep.child.left = thisRep.child.right = e._repIdx;
-        newRep.parent = _repIdx;
-        impl.deserialize(_repIdx);
-        return Status::OK();
-    }
+    // We own a BufBuilder to avoid BSONObjBuilder's ref-count mechanism which would throw
+    // off our offset calculations.
+    BufBuilder _leafBuf;
+    BSONObjBuilder _leafBuilder;
 
-    Status Element::setValue(const Element::RepIdx newValueIdx) {
-        // No need to verify(ok()) since we are only called from methods that have done so.
-        dassert(ok());
+    // Sometimes, we need a temporary storage area for a fieldName, because the source of
+    // the fieldName is in the same buffer that we want to write to, potentially
+    // reallocating it. In such cases, we temporarily store the value here, rather than
+    // creating and destroying a string and its buffer each time.
+    std::string _fieldNameScratch;
 
-        if (_repIdx == kRootRepIdx)
-            return Status(ErrorCodes::IllegalOperation, "Cannot call setValue on the root object");
+    // Queue of damage events and status bit for whether  in-place updates are possible.
+    DamageVector _damages;
+    Document::InPlaceMode _inPlaceMode;
+};
 
-        Document::Impl& impl = getDocument().getImpl();
+Status Element::addSiblingLeft(Element e) {
+    verify(ok());
+    verify(e.ok());
+    verify(_doc == e._doc);
 
-        // Establish our right sibling in case it is opaque. Otherwise, we would lose the
-        // ability to do so after the modifications below. It is important that this occur
-        // before we acquire thisRep and valueRep since otherwise we would potentially
-        // invalidate them.
-        impl.resolveRightSibling(_repIdx);
+    Document::Impl& impl = getDocument().getImpl();
+    ElementRep& newRep = impl.getElementRep(e._repIdx);
 
-        ElementRep& thisRep = impl.getElementRep(_repIdx);
-        ElementRep& valueRep = impl.getElementRep(newValueIdx);
+    // check that new element roots a clean subtree.
+    if (!canAttach(e._repIdx, newRep))
+        return getAttachmentError(newRep);
 
-        if (impl.isInPlaceModeEnabled() && impl.canUpdateInPlace(valueRep, thisRep)) {
+    ElementRep& thisRep = impl.getElementRep(_repIdx);
 
-            // Get the BSONElement representations of the existing and new value, so we can
-            // check if they are size compatible.
-            BSONElement thisElt = impl.getSerializedElement(thisRep);
-            BSONElement valueElt = impl.getSerializedElement(valueRep);
+    dassert(thisRep.parent != kOpaqueRepIdx);
+    if (thisRep.parent == kInvalidRepIdx)
+        return Status(ErrorCodes::IllegalOperation,
+                      "Attempt to add a sibling to an element without a parent");
 
-            if (thisElt.size() == valueElt.size()) {
+    ElementRep& parentRep = impl.getElementRep(thisRep.parent);
+    dassert(!impl.isLeaf(parentRep));
 
-                // The old and new elements are size compatible. Compute the base offsets
-                // of each BSONElement in the object in which it resides. We use these to
-                // calculate the source and target offsets in the damage entries we are
-                // going to write.
+    impl.disableInPlaceUpdates();
 
-                const DamageEvent::OffsetSizeType targetBaseOffset =
-                    getElementOffset(impl.getObject(thisRep.objIdx), thisElt);
+    // The new element shares our parent.
+    newRep.parent = thisRep.parent;
 
-                const DamageEvent::OffsetSizeType sourceBaseOffset =
-                    getElementOffset(impl.getObject(valueRep.objIdx), valueElt);
+    // We are the new element's right sibling.
+    newRep.sibling.right = _repIdx;
 
-                // If this is a type change, record a damage event for the new type.
-                if (thisElt.type() != valueElt.type()) {
-                    impl.recordDamageEvent(targetBaseOffset, sourceBaseOffset, 1);
-                }
+    // The new element's left sibling is our left sibling.
+    newRep.sibling.left = thisRep.sibling.left;
 
-                dassert(thisElt.fieldNameSize() == valueElt.fieldNameSize());
-                dassert(thisElt.valuesize() == valueElt.valuesize());
+    // If the new element has a left sibling after the adjustments above, then that left
+    // sibling must be updated to have the new element as its right sibling.
+    if (newRep.sibling.left != kInvalidRepIdx)
+        impl.getElementRep(thisRep.sibling.left).sibling.right = e._repIdx;
 
-                // Record a damage event for the new value data.
-                impl.recordDamageEvent(
-                    targetBaseOffset + thisElt.fieldNameSize() + 1,
-                    sourceBaseOffset + thisElt.fieldNameSize() + 1,
-                    thisElt.valuesize());
-            } else {
+    // The new element becomes our left sibling.
+    thisRep.sibling.left = e._repIdx;
 
-                // We couldn't do it in place, so disable future in-place updates.
-                impl.disableInPlaceUpdates();
+    // If we were our parent's left child, then we no longer are. Make the new right
+    // sibling the right child.
+    if (parentRep.child.left == _repIdx)
+        parentRep.child.left = e._repIdx;
 
-            }
-        }
-
-        // If we are not rootish, then wire in the new value among our relations.
-        if (thisRep.parent != kInvalidRepIdx) {
-            valueRep.parent = thisRep.parent;
-            valueRep.sibling.left = thisRep.sibling.left;
-            valueRep.sibling.right = thisRep.sibling.right;
-        }
-
-        // Copy the rep for value to our slot so that our repIdx is unmodified.
-        thisRep = valueRep;
+    impl.deserialize(thisRep.parent);
 
-        // Be nice and clear out the source rep to make debugging easier.
-        valueRep = ElementRep();
+    return Status::OK();
+}
 
-        impl.deserialize(thisRep.parent);
-        return Status::OK();
-    }
+Status Element::addSiblingRight(Element e) {
+    verify(ok());
+    verify(e.ok());
+    verify(_doc == e._doc);
 
+    Document::Impl& impl = getDocument().getImpl();
+    ElementRep* newRep = &impl.getElementRep(e._repIdx);
 
-    namespace {
-
-        // A helper for Element::writeElement below. For cases where we are building inside an
-        // array, we want to ignore field names. So the specialization for BSONArrayBuilder ignores
-        // the third parameter.
-        template<typename Builder>
-        struct SubBuilder;
-
-        template<>
-        struct SubBuilder<BSONObjBuilder> {
-            SubBuilder(BSONObjBuilder* builder, BSONType type, StringData fieldName)
-                : buffer(
-                    (type == mongo::Array) ?
-                    builder->subarrayStart(fieldName) :
-                    builder->subobjStart(fieldName)) {}
-            BufBuilder& buffer;
-        };
-
-        template<>
-        struct SubBuilder<BSONArrayBuilder> {
-            SubBuilder(BSONArrayBuilder* builder, BSONType type, StringData)
-                : buffer(
-                    (type == mongo::Array) ?
-                    builder->subarrayStart() :
-                    builder->subobjStart()) {}
-            BufBuilder& buffer;
-        };
-
-        static void appendElement(BSONObjBuilder* builder,
-                                  const BSONElement& element,
-                                  const StringData* fieldName) {
-            if (fieldName)
-                builder->appendAs(element, *fieldName);
-            else
-                builder->append(element);
-        }
+    // check that new element roots a clean subtree.
+    if (!canAttach(e._repIdx, *newRep))
+        return getAttachmentError(*newRep);
 
-        // BSONArrayBuilder should not be appending elements with a fieldName
-        static void appendElement(BSONArrayBuilder* builder,
-                                  const BSONElement& element,
-                                  const StringData* fieldName) {
-            invariant(!fieldName);
-            builder->append(element);
-        }
+    ElementRep* thisRep = &impl.getElementRep(_repIdx);
 
-    } // namespace
+    dassert(thisRep->parent != kOpaqueRepIdx);
+    if (thisRep->parent == kInvalidRepIdx)
+        return Status(ErrorCodes::IllegalOperation,
+                      "Attempt to add a sibling to an element without a parent");
 
-    template<typename Builder>
-    void Document::Impl::writeElement(Element::RepIdx repIdx, Builder* builder,
-                                      const StringData* fieldName) const {
+    ElementRep* parentRep = &impl.getElementRep(thisRep->parent);
+    dassert(!impl.isLeaf(*parentRep));
 
-        const ElementRep& rep = getElementRep(repIdx);
+    impl.disableInPlaceUpdates();
 
-        if (hasValue(rep)) {
-            appendElement(builder, getSerializedElement(rep), fieldName);
-        } else {
-            const BSONType type = getType(rep);
-            const StringData subName = fieldName ? *fieldName : getFieldName(rep);
-            SubBuilder<Builder> subBuilder(builder, type, subName);
-
-            // Otherwise, this is a 'dirty leaf', which is impossible.
-            dassert((type == mongo::Array) || (type == mongo::Object));
-
-            if (type == mongo::Array) {
-                BSONArrayBuilder child_builder(subBuilder.buffer);
-                writeChildren(repIdx, &child_builder);
-                child_builder.doneFast();
-            } else {
-                BSONObjBuilder child_builder(subBuilder.buffer);
-                writeChildren(repIdx, &child_builder);
-                child_builder.doneFast();
-            }
-        }
+    // If our current right sibling is opaque it needs to be resolved. This will invalidate
+    // our reps so we need to reacquire them.
+    Element::RepIdx rightSiblingIdx = thisRep->sibling.right;
+    if (rightSiblingIdx == kOpaqueRepIdx) {
+        rightSiblingIdx = impl.resolveRightSibling(_repIdx);
+        dassert(rightSiblingIdx != kOpaqueRepIdx);
+        newRep = &impl.getElementRep(e._repIdx);
+        thisRep = &impl.getElementRep(_repIdx);
+        parentRep = &impl.getElementRep(thisRep->parent);
     }
 
-    template<typename Builder>
-    void Document::Impl::writeChildren(Element::RepIdx repIdx, Builder* builder) const {
-
-        // TODO: In theory, I think we can walk rightwards building a write region from all
-        // serialized embedded children that share an obj id and form a contiguous memory
-        // region. For arrays we would need to know something about how many elements we wrote
-        // that way so that the indexes would come out right.
-        //
-        // However, that involves walking the memory twice: once to build the copy region, and
-        // another time to actually copy it. It is unclear if this is better than just walking
-        // it once with the recursive solution.
-
-        const ElementRep& rep = getElementRep(repIdx);
-
-        // OK, need to resolve left if we haven't done that yet.
-        Element::RepIdx current = rep.child.left;
-        if (current == Element::kOpaqueRepIdx)
-            current = const_cast<Impl*>(this)->resolveLeftChild(repIdx);
-
-        // We need to write the element, and then walk rightwards.
-        while (current != Element::kInvalidRepIdx) {
-            writeElement(current, builder);
-
-            // If we have an opaque region to the right, and we are not in an array, then we
-            // can bulk copy from the end of the element we just wrote to the end of our
-            // parent.
-            const ElementRep& currentRep = getElementRep(current);
+    // The new element shares our parent.
+    newRep->parent = thisRep->parent;
 
-            if (currentRep.sibling.right == Element::kOpaqueRepIdx) {
+    // We are the new element's left sibling.
+    newRep->sibling.left = _repIdx;
 
-                // Obtain the current parent, so we can see if we can bulk copy the right
-                // siblings.
-                const ElementRep& parentRep = getElementRep(currentRep.parent);
+    // The new element right sibling is our right sibling.
+    newRep->sibling.right = rightSiblingIdx;
 
-                // Bulk copying right only works on objects
-                if ((getType(parentRep) == mongo::Object) &&
-                    (currentRep.objIdx != kInvalidObjIdx) &&
-                    (currentRep.objIdx == parentRep.objIdx)) {
+    // The new element becomes our right sibling.
+    thisRep->sibling.right = e._repIdx;
 
-                    BSONElement currentElt = getSerializedElement(currentRep);
-                    const uint32_t currentSize = currentElt.size();
+    // If the new element has a right sibling after the adjustments above, then that right
+    // sibling must be updated to have the new element as its left sibling.
+    if (newRep->sibling.right != kInvalidRepIdx)
+        impl.getElementRep(rightSiblingIdx).sibling.left = e._repIdx;
 
-                    const BSONObj parentObj = (currentRep.parent == kRootRepIdx) ?
-                        getObject(parentRep.objIdx) :
-                        getSerializedElement(parentRep).Obj();
-                    const uint32_t parentSize = parentObj.objsize();
+    // If we were our parent's right child, then we no longer are. Make the new right
+    // sibling the right child.
+    if (parentRep->child.right == _repIdx)
+        parentRep->child.right = e._repIdx;
 
-                    const uint32_t currentEltOffset = getElementOffset(parentObj, currentElt);
-                    const uint32_t nextEltOffset = currentEltOffset + currentSize;
+    impl.deserialize(thisRep->parent);
 
-                    const char* copyBegin = parentObj.objdata() + nextEltOffset;
-                    const uint32_t copyBytes = parentSize - nextEltOffset;
+    return Status::OK();
+}
 
-                    // The -1 is because we don't want to copy in the terminal EOO.
-                    builder->bb().appendBuf(copyBegin, copyBytes - 1);
+Status Element::remove() {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
 
-                    // We are done with all children.
-                    break;
-                }
-
-                // We couldn't bulk copy, and our right sibling is opaque. We need to
-                // resolve. Note that the call to resolve may invalidate 'currentRep', so
-                // rather than falling through and acquiring the index by examining currentRep,
-                // update it with the return value of resolveRightSibling and restart the loop.
-                current = const_cast<Impl*>(this)->resolveRightSibling(current);
-                continue;
-            }
+    // We need to realize any opaque right sibling, because we are going to need to set its
+    // left sibling. Do this before acquiring thisRep since otherwise we would potentially
+    // invalidate it.
+    impl.resolveRightSibling(_repIdx);
 
-            current = currentRep.sibling.right;
-        }
-    }
+    ElementRep& thisRep = impl.getElementRep(_repIdx);
 
-    Document::Document()
-        : _impl(new Impl(Document::kInPlaceDisabled))
-        , _root(makeRootElement()) {
-        dassert(_root._repIdx == kRootRepIdx);
-    }
+    if (thisRep.parent == kInvalidRepIdx)
+        return Status(ErrorCodes::IllegalOperation, "trying to remove a parentless element");
+    impl.disableInPlaceUpdates();
 
-    Document::Document(const BSONObj& value, InPlaceMode inPlaceMode)
-        : _impl(new Impl(inPlaceMode))
-        , _root(makeRootElement(value)) {
-        dassert(_root._repIdx == kRootRepIdx);
-    }
+    // If our right sibling is not the end of the object, then set its left sibling to be
+    // our left sibling.
+    if (thisRep.sibling.right != kInvalidRepIdx)
+        impl.getElementRep(thisRep.sibling.right).sibling.left = thisRep.sibling.left;
 
-    void Document::reset() {
-        _impl->reset(Document::kInPlaceDisabled);
-        MONGO_COMPILER_VARIABLE_UNUSED const Element newRoot = makeRootElement();
-        dassert(newRoot._repIdx == _root._repIdx);
-        dassert(_root._repIdx == kRootRepIdx);
+    // Similarly, if our left sibling is not the beginning of the obejct, then set its
+    // right sibling to be our right sibling.
+    if (thisRep.sibling.left != kInvalidRepIdx) {
+        ElementRep& leftRep = impl.getElementRep(thisRep.sibling.left);
+        leftRep.sibling.right = thisRep.sibling.right;
     }
 
-    void Document::reset(const BSONObj& value, InPlaceMode inPlaceMode) {
-        _impl->reset(inPlaceMode);
-        MONGO_COMPILER_VARIABLE_UNUSED const Element newRoot = makeRootElement(value);
-        dassert(newRoot._repIdx == _root._repIdx);
-        dassert(_root._repIdx == kRootRepIdx);
-    }
+    // If this element was our parent's right child, then our left sibling is the new right
+    // child.
+    ElementRep& parentRep = impl.getElementRep(thisRep.parent);
+    if (parentRep.child.right == _repIdx)
+        parentRep.child.right = thisRep.sibling.left;
 
-    Document::~Document() {}
+    // Similarly, if this element was our parent's left child, then our right sibling is
+    // the new left child.
+    if (parentRep.child.left == _repIdx)
+        parentRep.child.left = thisRep.sibling.right;
 
-    void Document::reserveDamageEvents(size_t expectedEvents) {
-        return getImpl().reserveDamageEvents(expectedEvents);
-    }
+    impl.deserialize(thisRep.parent);
 
-    bool Document::getInPlaceUpdates(DamageVector* damages,
-                                     const char** source, size_t* size) {
-        return getImpl().getInPlaceUpdates(damages, source, size);
-    }
+    // The Element becomes detached.
+    thisRep.parent = kInvalidRepIdx;
+    thisRep.sibling.left = kInvalidRepIdx;
+    thisRep.sibling.right = kInvalidRepIdx;
 
-    void Document::disableInPlaceUpdates() {
-        return getImpl().disableInPlaceUpdates();
-    }
+    return Status::OK();
+}
 
-    Document::InPlaceMode Document::getCurrentInPlaceMode() const {
-        return getImpl().getCurrentInPlaceMode();
-    }
+Status Element::rename(StringData newName) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
 
-    Element Document::makeElementDouble(StringData fieldName, const double value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
+    if (_repIdx == kRootRepIdx)
+        return Status(ErrorCodes::IllegalOperation,
+                      "Invalid attempt to rename the root element of a document");
 
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.append(fieldName, value);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
+    dassert(impl.doesNotAlias(newName));
 
-    Element Document::makeElementString(StringData fieldName, StringData value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-        dassert(impl.doesNotAlias(value));
+    // TODO: Some rename operations may be possible to do in-place.
+    impl.disableInPlaceUpdates();
 
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.append(fieldName, value);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
-
-    Element Document::makeElementObject(StringData fieldName) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-
-        Element::RepIdx newEltIdx;
-        ElementRep& newElt = impl.makeNewRep(&newEltIdx);
-        impl.insertFieldName(newElt, fieldName);
-        return Element(this, newEltIdx);
-    }
-
-    Element Document::makeElementObject(StringData fieldName, const BSONObj& value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAliasLeafBuilder(fieldName));
-        dassert(impl.doesNotAlias(value));
+    // Operations below may invalidate thisRep, so we may need to reacquire it.
+    ElementRep* thisRep = &impl.getElementRep(_repIdx);
 
-        // Copy the provided values into the leaf builder.
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.append(fieldName, value);
-        Element::RepIdx newEltIdx = impl.insertLeafElement(leafRef, fieldName.size() + 1);
-        ElementRep& newElt = impl.getElementRep(newEltIdx);
+    // For non-leaf serialized elements, we can realize any opaque relatives and then
+    // convert ourselves to deserialized.
+    if (thisRep->objIdx != kInvalidObjIdx && !impl.isLeaf(*thisRep)) {
+        const bool array = (impl.getType(*thisRep) == mongo::Array);
 
-        newElt.child.left = Element::kOpaqueRepIdx;
-        newElt.child.right = Element::kOpaqueRepIdx;
+        // Realize any opaque right sibling or left child now, since otherwise we will lose
+        // the ability to do so.
+        impl.resolveLeftChild(_repIdx);
+        impl.resolveRightSibling(_repIdx);
 
-        return Element(this, newEltIdx);
-    }
+        // The resolve calls above may have invalidated thisRep, we need to reacquire it.
+        thisRep = &impl.getElementRep(_repIdx);
 
-    Element Document::makeElementArray(StringData fieldName) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
+        // Set this up as a non-supported deserialized element. We will set the fieldName
+        // in the else clause in the block below.
+        impl.deserialize(_repIdx);
 
-        Element::RepIdx newEltIdx;
-        ElementRep& newElt = impl.makeNewRep(&newEltIdx);
-        newElt.array = true;
-        impl.insertFieldName(newElt, fieldName);
-        return Element(this, newEltIdx);
+        thisRep->array = array;
+
+        // TODO: If we ever want to be able to add to the left or right of an opaque object
+        // without expanding, this may need to change.
+        thisRep->objIdx = kInvalidObjIdx;
+    }
+
+    if (impl.hasValue(*thisRep)) {
+        // For leaf elements we just create a new Element with the current value and
+        // replace. Note that the 'setValue' call below will invalidate thisRep.
+        Element replacement = _doc->makeElementWithNewFieldName(newName, *this);
+        setValue(replacement._repIdx);
+    } else {
+        // The easy case: just update what our field name offset refers to.
+        impl.insertFieldName(*thisRep, newName);
+    }
+
+    return Status::OK();
+}
+
+Element Element::leftChild() const {
+    verify(ok());
+
+    // Capturing Document::Impl by non-const ref exploits the constness loophole
+    // created by our Impl so that we can let leftChild be lazily evaluated, even for a
+    // const Element.
+    Document::Impl& impl = _doc->getImpl();
+    const Element::RepIdx leftChildIdx = impl.resolveLeftChild(_repIdx);
+    dassert(leftChildIdx != kOpaqueRepIdx);
+    return Element(_doc, leftChildIdx);
+}
+
+Element Element::rightChild() const {
+    verify(ok());
+
+    // Capturing Document::Impl by non-const ref exploits the constness loophole
+    // created by our Impl so that we can let leftChild be lazily evaluated, even for a
+    // const Element.
+    Document::Impl& impl = _doc->getImpl();
+    const Element::RepIdx rightChildIdx = impl.resolveRightChild(_repIdx);
+    dassert(rightChildIdx != kOpaqueRepIdx);
+    return Element(_doc, rightChildIdx);
+}
+
+bool Element::hasChildren() const {
+    verify(ok());
+    // Capturing Document::Impl by non-const ref exploits the constness loophole
+    // created by our Impl so that we can let leftChild be lazily evaluated, even for a
+    // const Element.
+    Document::Impl& impl = _doc->getImpl();
+    return impl.resolveLeftChild(_repIdx) != kInvalidRepIdx;
+}
+
+Element Element::leftSibling(size_t distance) const {
+    verify(ok());
+    const Document::Impl& impl = getDocument().getImpl();
+    Element::RepIdx current = _repIdx;
+    while ((current != kInvalidRepIdx) && (distance-- != 0)) {
+        // We are (currently) never left opaque, so don't need to resolve.
+        current = impl.getElementRep(current).sibling.left;
+    }
+    return Element(_doc, current);
+}
+
+Element Element::rightSibling(size_t distance) const {
+    verify(ok());
+
+    // Capturing Document::Impl by non-const ref exploits the constness loophole
+    // created by our Impl so that we can let rightSibling be lazily evaluated, even for a
+    // const Element.
+    Document::Impl& impl = _doc->getImpl();
+    Element::RepIdx current = _repIdx;
+    while ((current != kInvalidRepIdx) && (distance-- != 0))
+        current = impl.resolveRightSibling(current);
+    return Element(_doc, current);
+}
+
+Element Element::parent() const {
+    verify(ok());
+    const Document::Impl& impl = getDocument().getImpl();
+    const Element::RepIdx parentIdx = impl.getElementRep(_repIdx).parent;
+    dassert(parentIdx != kOpaqueRepIdx);
+    return Element(_doc, parentIdx);
+}
+
+Element Element::findNthChild(size_t n) const {
+    verify(ok());
+    Document::Impl& impl = _doc->getImpl();
+    Element::RepIdx current = _repIdx;
+    current = impl.resolveLeftChild(current);
+    while ((current != kInvalidRepIdx) && (n-- != 0))
+        current = impl.resolveRightSibling(current);
+    return Element(_doc, current);
+}
+
+Element Element::findFirstChildNamed(StringData name) const {
+    verify(ok());
+    Document::Impl& impl = _doc->getImpl();
+    Element::RepIdx current = _repIdx;
+    current = impl.resolveLeftChild(current);
+    // TODO: Could DRY this loop with the identical logic in findElementNamed.
+    while ((current != kInvalidRepIdx) && (impl.getFieldName(impl.getElementRep(current)) != name))
+        current = impl.resolveRightSibling(current);
+    return Element(_doc, current);
+}
+
+Element Element::findElementNamed(StringData name) const {
+    verify(ok());
+    Document::Impl& impl = _doc->getImpl();
+    Element::RepIdx current = _repIdx;
+    while ((current != kInvalidRepIdx) && (impl.getFieldName(impl.getElementRep(current)) != name))
+        current = impl.resolveRightSibling(current);
+    return Element(_doc, current);
+}
+
+size_t Element::countSiblingsLeft() const {
+    verify(ok());
+    const Document::Impl& impl = getDocument().getImpl();
+    Element::RepIdx current = _repIdx;
+    size_t result = 0;
+    while (true) {
+        // We are (currently) never left opaque, so don't need to resolve.
+        current = impl.getElementRep(current).sibling.left;
+        if (current == kInvalidRepIdx)
+            break;
+        ++result;
+    }
+    return result;
+}
+
+size_t Element::countSiblingsRight() const {
+    verify(ok());
+    Document::Impl& impl = _doc->getImpl();
+    Element::RepIdx current = _repIdx;
+    size_t result = 0;
+    while (true) {
+        current = impl.resolveRightSibling(current);
+        if (current == kInvalidRepIdx)
+            break;
+        ++result;
+    }
+    return result;
+}
+
+size_t Element::countChildren() const {
+    verify(ok());
+    Document::Impl& impl = _doc->getImpl();
+    Element::RepIdx current = _repIdx;
+    current = impl.resolveLeftChild(current);
+    size_t result = 0;
+    while (current != kInvalidRepIdx) {
+        ++result;
+        current = impl.resolveRightSibling(current);
+    }
+    return result;
+}
+
+bool Element::hasValue() const {
+    verify(ok());
+    const Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    return impl.hasValue(thisRep);
+}
+
+bool Element::isNumeric() const {
+    verify(ok());
+    const Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const BSONType type = impl.getType(thisRep);
+    return ((type == mongo::NumberLong) || (type == mongo::NumberInt) ||
+            (type == mongo::NumberDouble));
+}
+
+bool Element::isIntegral() const {
+    verify(ok());
+    const Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const BSONType type = impl.getType(thisRep);
+    return ((type == mongo::NumberLong) || (type == mongo::NumberInt));
+}
+
+const BSONElement Element::getValue() const {
+    verify(ok());
+    const Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    if (impl.hasValue(thisRep))
+        return impl.getSerializedElement(thisRep);
+    return BSONElement();
+}
+
+SafeNum Element::getValueSafeNum() const {
+    switch (getType()) {
+        case mongo::NumberInt:
+            return static_cast<int>(getValueInt());
+        case mongo::NumberLong:
+            return static_cast<long long int>(getValueLong());
+        case mongo::NumberDouble:
+            return getValueDouble();
+        default:
+            return SafeNum();
     }
+}
+
+int Element::compareWithElement(const ConstElement& other, bool considerFieldName) const {
+    verify(ok());
+    verify(other.ok());
+
+    // Short circuit a tautological compare.
+    if ((_repIdx == other.getIdx()) && (_doc == &other.getDocument()))
+        return 0;
+
+    // If either Element can represent its current value as a BSONElement, then we can
+    // obtain its value and use compareWithBSONElement. If both Elements have a
+    // representation as a BSONElement, compareWithBSONElement will notice that the first
+    // argument has a value and delegate to BSONElement::woCompare.
+
+    const Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+
+    // Subtle: we must negate the comparison result here because we are reversing the
+    // argument order in this call.
+    //
+    // TODO: Andy has suggested that this may not be legal since woCompare is not reflexive
+    // in all cases.
+    if (impl.hasValue(thisRep))
+        return -other.compareWithBSONElement(impl.getSerializedElement(thisRep), considerFieldName);
+
+    const Document::Impl& oimpl = other.getDocument().getImpl();
+    const ElementRep& otherRep = oimpl.getElementRep(other.getIdx());
+
+    if (oimpl.hasValue(otherRep))
+        return compareWithBSONElement(oimpl.getSerializedElement(otherRep), considerFieldName);
+
+    // Leaf elements should always have a value, so we should only be dealing with Objects
+    // or Arrays here.
+    dassert(!impl.isLeaf(thisRep));
+    dassert(!oimpl.isLeaf(otherRep));
+
+    // Obtain the canonical types for this Element and the BSONElement, if they are
+    // different use the difference as the result. Please see BSONElement::woCompare for
+    // details. We know that thisRep is not a number, so we don't need to check that
+    // particular case.
+    const int leftCanonType = canonicalizeBSONType(impl.getType(thisRep));
+    const int rightCanonType = canonicalizeBSONType(oimpl.getType(otherRep));
+    const int diffCanon = leftCanonType - rightCanonType;
+    if (diffCanon != 0)
+        return diffCanon;
+
+    // If we are considering field names, and the field names do not compare as equal,
+    // return the field name ordering as the element ordering.
+    if (considerFieldName) {
+        const int fnamesComp = impl.getFieldName(thisRep).compare(oimpl.getFieldName(otherRep));
+        if (fnamesComp != 0)
+            return fnamesComp;
+    }
+
+    const bool considerChildFieldNames =
+        (impl.getType(thisRep) != mongo::Array) && (oimpl.getType(otherRep) != mongo::Array);
+
+    // We are dealing with either two objects, or two arrays. We need to consider the child
+    // elements individually. We walk two iterators forward over the children and compare
+    // them. Length mismatches are handled by checking early for reaching the end of the
+    // children.
+    ConstElement thisIter = leftChild();
+    ConstElement otherIter = other.leftChild();
+
+    while (true) {
+        if (!thisIter.ok())
+            return !otherIter.ok() ? 0 : -1;
+        if (!otherIter.ok())
+            return 1;
+
+        const int result = thisIter.compareWithElement(otherIter, considerChildFieldNames);
+        if (result != 0)
+            return result;
 
-    Element Document::makeElementArray(StringData fieldName, const BSONObj& value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAliasLeafBuilder(fieldName));
-        dassert(impl.doesNotAlias(value));
-
-        // Copy the provided array values into the leaf builder.
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendArray(fieldName, value);
-        Element::RepIdx newEltIdx = impl.insertLeafElement(leafRef, fieldName.size() + 1);
-        ElementRep& newElt = impl.getElementRep(newEltIdx);
-        newElt.child.left = Element::kOpaqueRepIdx;
-        newElt.child.right = Element::kOpaqueRepIdx;
-        return Element(this, newEltIdx);
+        thisIter = thisIter.rightSibling();
+        otherIter = otherIter.rightSibling();
     }
+}
 
-    Element Document::makeElementBinary(StringData fieldName,
-                                        const uint32_t len,
-                                        const mongo::BinDataType binType,
-                                        const void* const data) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-        // TODO: Alias check 'data'?
+int Element::compareWithBSONElement(const BSONElement& other, bool considerFieldName) const {
+    verify(ok());
 
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendBinData(fieldName, len, binType, data);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
+    const Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
 
-    Element Document::makeElementUndefined(StringData fieldName) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
+    // If we have a representation as a BSONElement, we can just use BSONElement::woCompare
+    // to do the entire comparison.
+    if (impl.hasValue(thisRep))
+        return impl.getSerializedElement(thisRep).woCompare(other, considerFieldName);
 
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendUndefined(fieldName);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
-
-    Element Document::makeElementNewOID(StringData fieldName) {
-        OID newOID;
-        newOID.init();
-        return makeElementOID(fieldName, newOID);
-    }
+    // Leaf elements should always have a value, so we should only be dealing with Objects
+    // or Arrays here.
+    dassert(!impl.isLeaf(thisRep));
 
-    Element Document::makeElementOID(StringData fieldName, const OID value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
+    // Obtain the canonical types for this Element and the BSONElement, if they are
+    // different use the difference as the result. Please see BSONElement::woCompare for
+    // details. We know that thisRep is not a number, so we don't need to check that
+    // particular case.
+    const int leftCanonType = canonicalizeBSONType(impl.getType(thisRep));
+    const int rightCanonType = canonicalizeBSONType(other.type());
+    const int diffCanon = leftCanonType - rightCanonType;
+    if (diffCanon != 0)
+        return diffCanon;
 
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.append(fieldName, value);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+    // If we are considering field names, and the field names do not compare as equal,
+    // return the field name ordering as the element ordering.
+    if (considerFieldName) {
+        const int fnamesComp = impl.getFieldName(thisRep).compare(other.fieldNameStringData());
+        if (fnamesComp != 0)
+            return fnamesComp;
     }
 
-    Element Document::makeElementBool(StringData fieldName, const bool value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
+    const bool considerChildFieldNames =
+        (impl.getType(thisRep) != mongo::Array) && (other.type() != mongo::Array);
 
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendBool(fieldName, value);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
+    return compareWithBSONObj(other.Obj(), considerChildFieldNames);
+}
 
-    Element Document::makeElementDate(StringData fieldName, const Date_t value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
+int Element::compareWithBSONObj(const BSONObj& other, bool considerFieldName) const {
+    verify(ok());
 
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendDate(fieldName, value);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
+    const Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    verify(!impl.isLeaf(thisRep));
 
-    Element Document::makeElementNull(StringData fieldName) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
+    // We are dealing with either two objects, or two arrays. We need to consider the child
+    // elements individually. We walk two iterators forward over the children and compare
+    // them. Length mismatches are handled by checking early for reaching the end of the
+    // children.
+    ConstElement thisIter = leftChild();
+    BSONObjIterator otherIter(other);
 
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendNull(fieldName);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
+    while (true) {
+        const BSONElement otherVal = otherIter.next();
 
-    Element Document::makeElementRegex(StringData fieldName,
-                                       StringData re,
-                                       StringData flags) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-        dassert(impl.doesNotAlias(re));
-        dassert(impl.doesNotAlias(flags));
+        if (!thisIter.ok())
+            return otherVal.eoo() ? 0 : -1;
+        if (otherVal.eoo())
+            return 1;
 
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendRegex(fieldName, re, flags);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
+        const int result = thisIter.compareWithBSONElement(otherVal, considerFieldName);
+        if (result != 0)
+            return result;
 
-    Element Document::makeElementDBRef(StringData fieldName,
-                                       StringData ns, const OID value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendDBRef(fieldName, ns, value);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
+        thisIter = thisIter.rightSibling();
+    }
+}
+
+void Element::writeTo(BSONObjBuilder* const builder) const {
+    verify(ok());
+    const Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    verify(impl.getType(thisRep) == mongo::Object);
+    if (thisRep.parent == kInvalidRepIdx && _repIdx == kRootRepIdx) {
+        // If this is the root element, then we need to handle it differently, since it
+        // doesn't have a field name and should embed directly, rather than as an object.
+        impl.writeChildren(_repIdx, builder);
+    } else {
+        impl.writeElement(_repIdx, builder);
+    }
+}
+
+void Element::writeArrayTo(BSONArrayBuilder* const builder) const {
+    verify(ok());
+    const Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    verify(impl.getType(thisRep) == mongo::Array);
+    return impl.writeChildren(_repIdx, builder);
+}
+
+Status Element::setValueDouble(const double value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+    ElementRep thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementDouble(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueString(StringData value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+
+    dassert(impl.doesNotAlias(value));
+
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementString(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueObject(const BSONObj& value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+
+    dassert(impl.doesNotAlias(value));
+
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementObject(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueArray(const BSONObj& value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+
+    dassert(impl.doesNotAlias(value));
+
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementArray(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueBinary(const uint32_t len,
+                               mongo::BinDataType binType,
+                               const void* const data) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+
+    // TODO: Alias check for binary data?
+
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementBinary(fieldName, len, binType, data);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueUndefined() {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementUndefined(fieldName);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueOID(const OID value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementOID(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueBool(const bool value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+    ElementRep thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementBool(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueDate(const Date_t value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementDate(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueNull() {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementNull(fieldName);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueRegex(StringData re, StringData flags) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+
+    dassert(impl.doesNotAlias(re));
+    dassert(impl.doesNotAlias(flags));
+
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementRegex(fieldName, re, flags);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueDBRef(StringData ns, const OID oid) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+
+    dassert(impl.doesNotAlias(ns));
+
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementDBRef(fieldName, ns, oid);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueCode(StringData value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+
+    dassert(impl.doesNotAlias(value));
+
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementCode(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueSymbol(StringData value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+
+    dassert(impl.doesNotAlias(value));
+
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementSymbol(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueCodeWithScope(StringData code, const BSONObj& scope) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+
+    dassert(impl.doesNotAlias(code));
+    dassert(impl.doesNotAlias(scope));
+
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementCodeWithScope(fieldName, code, scope);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueInt(const int32_t value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+    ElementRep thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementInt(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueTimestamp(const Timestamp value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementTimestamp(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueLong(const int64_t value) {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+    ElementRep thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementLong(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueMinKey() {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementMinKey(fieldName);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueMaxKey() {
+    verify(ok());
+    Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementMaxKey(fieldName);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueBSONElement(const BSONElement& value) {
+    verify(ok());
+
+    if (value.type() == mongo::EOO)
+        return Status(ErrorCodes::IllegalOperation, "Can't set Element value to EOO");
+
+    Document::Impl& impl = getDocument().getImpl();
+
+    dassert(impl.doesNotAlias(value));
+
+    ElementRep thisRep = impl.getElementRep(_repIdx);
+    const StringData fieldName = impl.getFieldNameForNewElement(thisRep);
+    Element newValue = getDocument().makeElementWithNewFieldName(fieldName, value);
+    return setValue(newValue._repIdx);
+}
+
+Status Element::setValueSafeNum(const SafeNum value) {
+    verify(ok());
+    switch (value.type()) {
+        case mongo::NumberInt:
+            return setValueInt(value._value.int32Val);
+        case mongo::NumberLong:
+            return setValueLong(value._value.int64Val);
+        case mongo::NumberDouble:
+            return setValueDouble(value._value.doubleVal);
+        default:
+            return Status(ErrorCodes::UnsupportedFormat,
+                          "Don't know how to handle unexpected SafeNum type");
+    }
+}
+
+BSONType Element::getType() const {
+    verify(ok());
+    const Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    return impl.getType(thisRep);
+}
+
+StringData Element::getFieldName() const {
+    verify(ok());
+    const Document::Impl& impl = getDocument().getImpl();
+    const ElementRep& thisRep = impl.getElementRep(_repIdx);
+    return impl.getFieldName(thisRep);
+}
+
+Status Element::addChild(Element e, bool front) {
+    // No need to verify(ok()) since we are only called from methods that have done so.
+    dassert(ok());
+
+    verify(e.ok());
+    verify(_doc == e._doc);
+
+    Document::Impl& impl = getDocument().getImpl();
+    ElementRep& newRep = impl.getElementRep(e._repIdx);
+
+    // check that new element roots a clean subtree.
+    if (!canAttach(e._repIdx, newRep))
+        return getAttachmentError(newRep);
+
+    // Check that this element is eligible for children.
+    ElementRep& thisRep = impl.getElementRep(_repIdx);
+    if (impl.isLeaf(thisRep))
+        return Status(ErrorCodes::IllegalOperation,
+                      "Attempt to add a child element to a non-object element");
+
+    impl.disableInPlaceUpdates();
+
+    // TODO: In both of the following cases, we call two public API methods each. We can
+    // probably do better by writing this explicitly here and drying it with the public
+    // addSiblingLeft and addSiblingRight implementations.
+    if (front) {
+        // TODO: It is cheap to get the left child. However, it still means creating a rep
+        // for it. Can we do better?
+        Element lc = leftChild();
+        if (lc.ok())
+            return lc.addSiblingLeft(e);
+    } else {
+        // TODO: It is expensive to get the right child, since we have to build reps for
+        // all of the opaque children. But in principle, we don't really need them. Could
+        // we potentially add this element as a right child, leaving its left sibling
+        // opaque? We would at minimum need to update leftSibling, which currently assumes
+        // that your left sibling is never opaque. But adding new Elements to the end is a
+        // quite common operation, so it would be nice if we could do this efficiently.
+        Element rc = rightChild();
+        if (rc.ok())
+            return rc.addSiblingRight(e);
+    }
+
+    // It must be the case that we have no children, so the new element becomes both the
+    // right and left child of this node.
+    dassert((thisRep.child.left == kInvalidRepIdx) && (thisRep.child.right == kInvalidRepIdx));
+    thisRep.child.left = thisRep.child.right = e._repIdx;
+    newRep.parent = _repIdx;
+    impl.deserialize(_repIdx);
+    return Status::OK();
+}
+
+Status Element::setValue(const Element::RepIdx newValueIdx) {
+    // No need to verify(ok()) since we are only called from methods that have done so.
+    dassert(ok());
+
+    if (_repIdx == kRootRepIdx)
+        return Status(ErrorCodes::IllegalOperation, "Cannot call setValue on the root object");
+
+    Document::Impl& impl = getDocument().getImpl();
+
+    // Establish our right sibling in case it is opaque. Otherwise, we would lose the
+    // ability to do so after the modifications below. It is important that this occur
+    // before we acquire thisRep and valueRep since otherwise we would potentially
+    // invalidate them.
+    impl.resolveRightSibling(_repIdx);
+
+    ElementRep& thisRep = impl.getElementRep(_repIdx);
+    ElementRep& valueRep = impl.getElementRep(newValueIdx);
+
+    if (impl.isInPlaceModeEnabled() && impl.canUpdateInPlace(valueRep, thisRep)) {
+        // Get the BSONElement representations of the existing and new value, so we can
+        // check if they are size compatible.
+        BSONElement thisElt = impl.getSerializedElement(thisRep);
+        BSONElement valueElt = impl.getSerializedElement(valueRep);
+
+        if (thisElt.size() == valueElt.size()) {
+            // The old and new elements are size compatible. Compute the base offsets
+            // of each BSONElement in the object in which it resides. We use these to
+            // calculate the source and target offsets in the damage entries we are
+            // going to write.
+
+            const DamageEvent::OffsetSizeType targetBaseOffset =
+                getElementOffset(impl.getObject(thisRep.objIdx), thisElt);
+
+            const DamageEvent::OffsetSizeType sourceBaseOffset =
+                getElementOffset(impl.getObject(valueRep.objIdx), valueElt);
+
+            // If this is a type change, record a damage event for the new type.
+            if (thisElt.type() != valueElt.type()) {
+                impl.recordDamageEvent(targetBaseOffset, sourceBaseOffset, 1);
+            }
 
-    Element Document::makeElementCode(StringData fieldName, StringData value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-        dassert(impl.doesNotAlias(value));
+            dassert(thisElt.fieldNameSize() == valueElt.fieldNameSize());
+            dassert(thisElt.valuesize() == valueElt.valuesize());
 
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendCode(fieldName, value);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
+            // Record a damage event for the new value data.
+            impl.recordDamageEvent(targetBaseOffset + thisElt.fieldNameSize() + 1,
+                                   sourceBaseOffset + thisElt.fieldNameSize() + 1,
+                                   thisElt.valuesize());
+        } else {
+            // We couldn't do it in place, so disable future in-place updates.
+            impl.disableInPlaceUpdates();
+        }
+    }
+
+    // If we are not rootish, then wire in the new value among our relations.
+    if (thisRep.parent != kInvalidRepIdx) {
+        valueRep.parent = thisRep.parent;
+        valueRep.sibling.left = thisRep.sibling.left;
+        valueRep.sibling.right = thisRep.sibling.right;
+    }
+
+    // Copy the rep for value to our slot so that our repIdx is unmodified.
+    thisRep = valueRep;
+
+    // Be nice and clear out the source rep to make debugging easier.
+    valueRep = ElementRep();
+
+    impl.deserialize(thisRep.parent);
+    return Status::OK();
+}
+
+
+namespace {
+
+// A helper for Element::writeElement below. For cases where we are building inside an
+// array, we want to ignore field names. So the specialization for BSONArrayBuilder ignores
+// the third parameter.
+template <typename Builder>
+struct SubBuilder;
+
+template <>
+struct SubBuilder<BSONObjBuilder> {
+    SubBuilder(BSONObjBuilder* builder, BSONType type, StringData fieldName)
+        : buffer((type == mongo::Array) ? builder->subarrayStart(fieldName)
+                                        : builder->subobjStart(fieldName)) {}
+    BufBuilder& buffer;
+};
+
+template <>
+struct SubBuilder<BSONArrayBuilder> {
+    SubBuilder(BSONArrayBuilder* builder, BSONType type, StringData)
+        : buffer((type == mongo::Array) ? builder->subarrayStart() : builder->subobjStart()) {}
+    BufBuilder& buffer;
+};
+
+static void appendElement(BSONObjBuilder* builder,
+                          const BSONElement& element,
+                          const StringData* fieldName) {
+    if (fieldName)
+        builder->appendAs(element, *fieldName);
+    else
+        builder->append(element);
+}
+
+// BSONArrayBuilder should not be appending elements with a fieldName
+static void appendElement(BSONArrayBuilder* builder,
+                          const BSONElement& element,
+                          const StringData* fieldName) {
+    invariant(!fieldName);
+    builder->append(element);
+}
+
+}  // namespace
+
+template <typename Builder>
+void Document::Impl::writeElement(Element::RepIdx repIdx,
+                                  Builder* builder,
+                                  const StringData* fieldName) const {
+    const ElementRep& rep = getElementRep(repIdx);
+
+    if (hasValue(rep)) {
+        appendElement(builder, getSerializedElement(rep), fieldName);
+    } else {
+        const BSONType type = getType(rep);
+        const StringData subName = fieldName ? *fieldName : getFieldName(rep);
+        SubBuilder<Builder> subBuilder(builder, type, subName);
+
+        // Otherwise, this is a 'dirty leaf', which is impossible.
+        dassert((type == mongo::Array) || (type == mongo::Object));
+
+        if (type == mongo::Array) {
+            BSONArrayBuilder child_builder(subBuilder.buffer);
+            writeChildren(repIdx, &child_builder);
+            child_builder.doneFast();
+        } else {
+            BSONObjBuilder child_builder(subBuilder.buffer);
+            writeChildren(repIdx, &child_builder);
+            child_builder.doneFast();
+        }
+    }
+}
+
+template <typename Builder>
+void Document::Impl::writeChildren(Element::RepIdx repIdx, Builder* builder) const {
+    // TODO: In theory, I think we can walk rightwards building a write region from all
+    // serialized embedded children that share an obj id and form a contiguous memory
+    // region. For arrays we would need to know something about how many elements we wrote
+    // that way so that the indexes would come out right.
+    //
+    // However, that involves walking the memory twice: once to build the copy region, and
+    // another time to actually copy it. It is unclear if this is better than just walking
+    // it once with the recursive solution.
+
+    const ElementRep& rep = getElementRep(repIdx);
+
+    // OK, need to resolve left if we haven't done that yet.
+    Element::RepIdx current = rep.child.left;
+    if (current == Element::kOpaqueRepIdx)
+        current = const_cast<Impl*>(this)->resolveLeftChild(repIdx);
+
+    // We need to write the element, and then walk rightwards.
+    while (current != Element::kInvalidRepIdx) {
+        writeElement(current, builder);
+
+        // If we have an opaque region to the right, and we are not in an array, then we
+        // can bulk copy from the end of the element we just wrote to the end of our
+        // parent.
+        const ElementRep& currentRep = getElementRep(current);
+
+        if (currentRep.sibling.right == Element::kOpaqueRepIdx) {
+            // Obtain the current parent, so we can see if we can bulk copy the right
+            // siblings.
+            const ElementRep& parentRep = getElementRep(currentRep.parent);
+
+            // Bulk copying right only works on objects
+            if ((getType(parentRep) == mongo::Object) && (currentRep.objIdx != kInvalidObjIdx) &&
+                (currentRep.objIdx == parentRep.objIdx)) {
+                BSONElement currentElt = getSerializedElement(currentRep);
+                const uint32_t currentSize = currentElt.size();
+
+                const BSONObj parentObj = (currentRep.parent == kRootRepIdx)
+                    ? getObject(parentRep.objIdx)
+                    : getSerializedElement(parentRep).Obj();
+                const uint32_t parentSize = parentObj.objsize();
+
+                const uint32_t currentEltOffset = getElementOffset(parentObj, currentElt);
+                const uint32_t nextEltOffset = currentEltOffset + currentSize;
+
+                const char* copyBegin = parentObj.objdata() + nextEltOffset;
+                const uint32_t copyBytes = parentSize - nextEltOffset;
+
+                // The -1 is because we don't want to copy in the terminal EOO.
+                builder->bb().appendBuf(copyBegin, copyBytes - 1);
+
+                // We are done with all children.
+                break;
+            }
 
-    Element Document::makeElementSymbol(StringData fieldName, StringData value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
+            // We couldn't bulk copy, and our right sibling is opaque. We need to
+            // resolve. Note that the call to resolve may invalidate 'currentRep', so
+            // rather than falling through and acquiring the index by examining currentRep,
+            // update it with the return value of resolveRightSibling and restart the loop.
+            current = const_cast<Impl*>(this)->resolveRightSibling(current);
+            continue;
+        }
+
+        current = currentRep.sibling.right;
+    }
+}
+
+Document::Document() : _impl(new Impl(Document::kInPlaceDisabled)), _root(makeRootElement()) {
+    dassert(_root._repIdx == kRootRepIdx);
+}
+
+Document::Document(const BSONObj& value, InPlaceMode inPlaceMode)
+    : _impl(new Impl(inPlaceMode)), _root(makeRootElement(value)) {
+    dassert(_root._repIdx == kRootRepIdx);
+}
+
+void Document::reset() {
+    _impl->reset(Document::kInPlaceDisabled);
+    MONGO_COMPILER_VARIABLE_UNUSED const Element newRoot = makeRootElement();
+    dassert(newRoot._repIdx == _root._repIdx);
+    dassert(_root._repIdx == kRootRepIdx);
+}
+
+void Document::reset(const BSONObj& value, InPlaceMode inPlaceMode) {
+    _impl->reset(inPlaceMode);
+    MONGO_COMPILER_VARIABLE_UNUSED const Element newRoot = makeRootElement(value);
+    dassert(newRoot._repIdx == _root._repIdx);
+    dassert(_root._repIdx == kRootRepIdx);
+}
+
+Document::~Document() {}
+
+void Document::reserveDamageEvents(size_t expectedEvents) {
+    return getImpl().reserveDamageEvents(expectedEvents);
+}
+
+bool Document::getInPlaceUpdates(DamageVector* damages, const char** source, size_t* size) {
+    return getImpl().getInPlaceUpdates(damages, source, size);
+}
+
+void Document::disableInPlaceUpdates() {
+    return getImpl().disableInPlaceUpdates();
+}
+
+Document::InPlaceMode Document::getCurrentInPlaceMode() const {
+    return getImpl().getCurrentInPlaceMode();
+}
+
+Element Document::makeElementDouble(StringData fieldName, const double value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.append(fieldName, value);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementString(StringData fieldName, StringData value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+    dassert(impl.doesNotAlias(value));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.append(fieldName, value);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementObject(StringData fieldName) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    Element::RepIdx newEltIdx;
+    ElementRep& newElt = impl.makeNewRep(&newEltIdx);
+    impl.insertFieldName(newElt, fieldName);
+    return Element(this, newEltIdx);
+}
+
+Element Document::makeElementObject(StringData fieldName, const BSONObj& value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAliasLeafBuilder(fieldName));
+    dassert(impl.doesNotAlias(value));
+
+    // Copy the provided values into the leaf builder.
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.append(fieldName, value);
+    Element::RepIdx newEltIdx = impl.insertLeafElement(leafRef, fieldName.size() + 1);
+    ElementRep& newElt = impl.getElementRep(newEltIdx);
+
+    newElt.child.left = Element::kOpaqueRepIdx;
+    newElt.child.right = Element::kOpaqueRepIdx;
+
+    return Element(this, newEltIdx);
+}
+
+Element Document::makeElementArray(StringData fieldName) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    Element::RepIdx newEltIdx;
+    ElementRep& newElt = impl.makeNewRep(&newEltIdx);
+    newElt.array = true;
+    impl.insertFieldName(newElt, fieldName);
+    return Element(this, newEltIdx);
+}
+
+Element Document::makeElementArray(StringData fieldName, const BSONObj& value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAliasLeafBuilder(fieldName));
+    dassert(impl.doesNotAlias(value));
+
+    // Copy the provided array values into the leaf builder.
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendArray(fieldName, value);
+    Element::RepIdx newEltIdx = impl.insertLeafElement(leafRef, fieldName.size() + 1);
+    ElementRep& newElt = impl.getElementRep(newEltIdx);
+    newElt.child.left = Element::kOpaqueRepIdx;
+    newElt.child.right = Element::kOpaqueRepIdx;
+    return Element(this, newEltIdx);
+}
+
+Element Document::makeElementBinary(StringData fieldName,
+                                    const uint32_t len,
+                                    const mongo::BinDataType binType,
+                                    const void* const data) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+    // TODO: Alias check 'data'?
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendBinData(fieldName, len, binType, data);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementUndefined(StringData fieldName) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendUndefined(fieldName);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementNewOID(StringData fieldName) {
+    OID newOID;
+    newOID.init();
+    return makeElementOID(fieldName, newOID);
+}
+
+Element Document::makeElementOID(StringData fieldName, const OID value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.append(fieldName, value);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementBool(StringData fieldName, const bool value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendBool(fieldName, value);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementDate(StringData fieldName, const Date_t value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendDate(fieldName, value);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementNull(StringData fieldName) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendNull(fieldName);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementRegex(StringData fieldName, StringData re, StringData flags) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+    dassert(impl.doesNotAlias(re));
+    dassert(impl.doesNotAlias(flags));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendRegex(fieldName, re, flags);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementDBRef(StringData fieldName, StringData ns, const OID value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendDBRef(fieldName, ns, value);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementCode(StringData fieldName, StringData value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+    dassert(impl.doesNotAlias(value));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendCode(fieldName, value);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementSymbol(StringData fieldName, StringData value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+    dassert(impl.doesNotAlias(value));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendSymbol(fieldName, value);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementCodeWithScope(StringData fieldName,
+                                           StringData code,
+                                           const BSONObj& scope) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+    dassert(impl.doesNotAlias(code));
+    dassert(impl.doesNotAlias(scope));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendCodeWScope(fieldName, code, scope);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementInt(StringData fieldName, const int32_t value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.append(fieldName, value);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementTimestamp(StringData fieldName, const Timestamp value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.append(fieldName, value);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementLong(StringData fieldName, const int64_t value) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.append(fieldName, static_cast<long long int>(value));
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementMinKey(StringData fieldName) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendMinKey(fieldName);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElementMaxKey(StringData fieldName) {
+    Impl& impl = getImpl();
+    dassert(impl.doesNotAlias(fieldName));
+
+    BSONObjBuilder& builder = impl.leafBuilder();
+    const int leafRef = builder.len();
+    builder.appendMaxKey(fieldName);
+    return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
+}
+
+Element Document::makeElement(const BSONElement& value) {
+    Impl& impl = getImpl();
+
+    // Attempts to create an EOO element are translated to returning an invalid
+    // Element. For array and object nodes, we flow through the custom
+    // makeElement{Object|Array} methods, since they have special logic to deal with
+    // opaqueness. Otherwise, we can just insert via appendAs.
+    if (value.type() == mongo::EOO)
+        return end();
+    else if (value.type() == mongo::Object)
+        return makeElementObject(value.fieldNameStringData(), value.Obj());
+    else if (value.type() == mongo::Array)
+        return makeElementArray(value.fieldNameStringData(), value.Obj());
+    else {
         dassert(impl.doesNotAlias(value));
-
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendSymbol(fieldName, value);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
-
-    Element Document::makeElementCodeWithScope(StringData fieldName,
-                                               StringData code, const BSONObj& scope) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-        dassert(impl.doesNotAlias(code));
-        dassert(impl.doesNotAlias(scope));
-
         BSONObjBuilder& builder = impl.leafBuilder();
         const int leafRef = builder.len();
-        builder.appendCodeWScope(fieldName, code, scope);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
-
-    Element Document::makeElementInt(StringData fieldName, const int32_t value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-
+        builder.append(value);
+        return Element(this, impl.insertLeafElement(leafRef, value.fieldNameSize()));
+    }
+}
+
+Element Document::makeElementWithNewFieldName(StringData fieldName, const BSONElement& value) {
+    Impl& impl = getImpl();
+
+    // See the above makeElement for notes on these cases.
+    if (value.type() == mongo::EOO)
+        return end();
+    else if (value.type() == mongo::Object)
+        return makeElementObject(fieldName, value.Obj());
+    else if (value.type() == mongo::Array)
+        return makeElementArray(fieldName, value.Obj());
+    else {
+        dassert(getImpl().doesNotAliasLeafBuilder(fieldName));
+        dassert(getImpl().doesNotAlias(value));
         BSONObjBuilder& builder = impl.leafBuilder();
         const int leafRef = builder.len();
-        builder.append(fieldName, value);
+        builder.appendAs(value, fieldName);
         return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
     }
+}
 
-    Element Document::makeElementTimestamp(StringData fieldName, const Timestamp value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.append(fieldName, value);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
-
-    Element Document::makeElementLong(StringData fieldName, const int64_t value) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.append(fieldName, static_cast<long long int>(value));
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
-
-    Element Document::makeElementMinKey(StringData fieldName) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendMinKey(fieldName);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
-
-    Element Document::makeElementMaxKey(StringData fieldName) {
-        Impl& impl = getImpl();
-        dassert(impl.doesNotAlias(fieldName));
-
-        BSONObjBuilder& builder = impl.leafBuilder();
-        const int leafRef = builder.len();
-        builder.appendMaxKey(fieldName);
-        return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-    }
-
-    Element Document::makeElement(const BSONElement& value) {
-        Impl& impl = getImpl();
-
-        // Attempts to create an EOO element are translated to returning an invalid
-        // Element. For array and object nodes, we flow through the custom
-        // makeElement{Object|Array} methods, since they have special logic to deal with
-        // opaqueness. Otherwise, we can just insert via appendAs.
-        if (value.type() == mongo::EOO)
-            return end();
-        else if(value.type() == mongo::Object)
-            return makeElementObject(value.fieldNameStringData(), value.Obj());
-        else if(value.type() == mongo::Array)
-            return makeElementArray(value.fieldNameStringData(), value.Obj());
-        else {
-            dassert(impl.doesNotAlias(value));
-            BSONObjBuilder& builder = impl.leafBuilder();
-            const int leafRef = builder.len();
-            builder.append(value);
-            return Element(this, impl.insertLeafElement(leafRef, value.fieldNameSize()));
-        }
-    }
-
-    Element Document::makeElementWithNewFieldName(StringData fieldName,
-                                                  const BSONElement& value) {
-        Impl& impl = getImpl();
+Element Document::makeElementSafeNum(StringData fieldName, SafeNum value) {
+    dassert(getImpl().doesNotAlias(fieldName));
 
-        // See the above makeElement for notes on these cases.
-        if (value.type() == mongo::EOO)
-            return end();
-        else if(value.type() == mongo::Object)
-            return makeElementObject(fieldName, value.Obj());
-        else if(value.type() == mongo::Array)
-            return makeElementArray(fieldName, value.Obj());
-        else {
-            dassert(getImpl().doesNotAliasLeafBuilder(fieldName));
-            dassert(getImpl().doesNotAlias(value));
-            BSONObjBuilder& builder = impl.leafBuilder();
-            const int leafRef = builder.len();
-            builder.appendAs(value, fieldName);
-            return Element(this, impl.insertLeafElement(leafRef, fieldName.size() + 1));
-        }
-    }
-
-    Element Document::makeElementSafeNum(StringData fieldName, SafeNum value) {
-
-        dassert(getImpl().doesNotAlias(fieldName));
-
-        switch (value.type()) {
+    switch (value.type()) {
         case mongo::NumberInt:
             return makeElementInt(fieldName, value._value.int32Val);
         case mongo::NumberLong:
@@ -2573,93 +2520,89 @@ namespace mutablebson {
         default:
             // Return an invalid element to indicate that we failed.
             return end();
-        }
     }
-
-    Element Document::makeElement(ConstElement element) {
-        return makeElement(element, NULL);
-    }
-
-    Element Document::makeElementWithNewFieldName(StringData fieldName,
-                                                  ConstElement element) {
-        return makeElement(element, &fieldName);
-    }
-
-    Element Document::makeRootElement() {
-        return makeElementObject(StringData(kRootFieldName, StringData::LiteralTag()));
-    }
-
-    Element Document::makeRootElement(const BSONObj& value) {
-        Impl& impl = getImpl();
-        Element::RepIdx newEltIdx = Element::kInvalidRepIdx;
-        ElementRep* newElt = &impl.makeNewRep(&newEltIdx);
-
-        // A BSONObj provided for the root Element is stored in _objects rather than being
-        // copied like all other BSONObjs.
-        newElt->objIdx = impl.insertObject(value);
-        impl.insertFieldName(*newElt, kRootFieldName);
-
-        // Strictly, the following is a lie: the root isn't serialized, because it doesn't
-        // have a contiguous fieldname. However, it is a useful fiction to pretend that it
-        // is, so we can easily check if we have a 'pristine' document state by checking if
-        // the root is marked as serialized.
-        newElt->serialized = true;
-
-        // If the provided value is empty, mark it as having no children, otherwise mark the
-        // children as opaque.
-        if (value.isEmpty())
-            newElt->child.left = Element::kInvalidRepIdx;
-        else
-            newElt->child.left = Element::kOpaqueRepIdx;
-        newElt->child.right = newElt->child.left;
-
-        return Element(this, newEltIdx);
-    }
-
-    Element Document::makeElement(ConstElement element, const StringData* fieldName) {
-
-        Impl& impl = getImpl();
-
-        if (this == &element.getDocument()) {
-
-            // If the Element that we want to build from belongs to this Document, then we have
-            // to first copy it to the side, and then back in, since otherwise we might be
-            // attempting both read to and write from the underlying BufBuilder simultaneously,
-            // which will not work.
-            BSONObjBuilder builder;
-            impl.writeElement(element.getIdx(), &builder, fieldName);
-            BSONObj built = builder.done();
-            BSONElement newElement = built.firstElement();
-            return makeElement(newElement);
-
-        } else {
-
-            // If the Element belongs to another document, then we can just stream it into our
-            // builder. We still do need to dassert that the field name doesn't alias us
-            // somehow.
-            if (fieldName) {
-                dassert(impl.doesNotAlias(*fieldName));
-            }
-            BSONObjBuilder& builder = impl.leafBuilder();
-            const int leafRef = builder.len();
-
-            const Impl& oImpl = element.getDocument().getImpl();
-            oImpl.writeElement(element.getIdx(), &builder, fieldName);
-            return Element(this, impl.insertLeafElement(leafRef));
+}
+
+Element Document::makeElement(ConstElement element) {
+    return makeElement(element, NULL);
+}
+
+Element Document::makeElementWithNewFieldName(StringData fieldName, ConstElement element) {
+    return makeElement(element, &fieldName);
+}
+
+Element Document::makeRootElement() {
+    return makeElementObject(StringData(kRootFieldName, StringData::LiteralTag()));
+}
+
+Element Document::makeRootElement(const BSONObj& value) {
+    Impl& impl = getImpl();
+    Element::RepIdx newEltIdx = Element::kInvalidRepIdx;
+    ElementRep* newElt = &impl.makeNewRep(&newEltIdx);
+
+    // A BSONObj provided for the root Element is stored in _objects rather than being
+    // copied like all other BSONObjs.
+    newElt->objIdx = impl.insertObject(value);
+    impl.insertFieldName(*newElt, kRootFieldName);
+
+    // Strictly, the following is a lie: the root isn't serialized, because it doesn't
+    // have a contiguous fieldname. However, it is a useful fiction to pretend that it
+    // is, so we can easily check if we have a 'pristine' document state by checking if
+    // the root is marked as serialized.
+    newElt->serialized = true;
+
+    // If the provided value is empty, mark it as having no children, otherwise mark the
+    // children as opaque.
+    if (value.isEmpty())
+        newElt->child.left = Element::kInvalidRepIdx;
+    else
+        newElt->child.left = Element::kOpaqueRepIdx;
+    newElt->child.right = newElt->child.left;
+
+    return Element(this, newEltIdx);
+}
+
+Element Document::makeElement(ConstElement element, const StringData* fieldName) {
+    Impl& impl = getImpl();
+
+    if (this == &element.getDocument()) {
+        // If the Element that we want to build from belongs to this Document, then we have
+        // to first copy it to the side, and then back in, since otherwise we might be
+        // attempting both read to and write from the underlying BufBuilder simultaneously,
+        // which will not work.
+        BSONObjBuilder builder;
+        impl.writeElement(element.getIdx(), &builder, fieldName);
+        BSONObj built = builder.done();
+        BSONElement newElement = built.firstElement();
+        return makeElement(newElement);
+
+    } else {
+        // If the Element belongs to another document, then we can just stream it into our
+        // builder. We still do need to dassert that the field name doesn't alias us
+        // somehow.
+        if (fieldName) {
+            dassert(impl.doesNotAlias(*fieldName));
         }
-    }
+        BSONObjBuilder& builder = impl.leafBuilder();
+        const int leafRef = builder.len();
 
-    inline Document::Impl& Document::getImpl() {
-        // Don't use unique_ptr<Impl>::operator* since it may generate assertions that the
-        // pointer is non-null, but we already know that to be always and forever true, and
-        // otherwise the assertion code gets spammed into every method that inlines the call to
-        // this function. We just dereference the pointer returned from 'get' ourselves.
-        return *_impl.get();
+        const Impl& oImpl = element.getDocument().getImpl();
+        oImpl.writeElement(element.getIdx(), &builder, fieldName);
+        return Element(this, impl.insertLeafElement(leafRef));
     }
+}
 
-    inline const Document::Impl& Document::getImpl() const {
-        return *_impl.get();
-    }
+inline Document::Impl& Document::getImpl() {
+    // Don't use unique_ptr<Impl>::operator* since it may generate assertions that the
+    // pointer is non-null, but we already know that to be always and forever true, and
+    // otherwise the assertion code gets spammed into every method that inlines the call to
+    // this function. We just dereference the pointer returned from 'get' ourselves.
+    return *_impl.get();
+}
+
+inline const Document::Impl& Document::getImpl() const {
+    return *_impl.get();
+}
 
-} // namespace mutablebson
-} // namespace mongo
+}  // namespace mutablebson
+}  // namespace mongo