diff options
Diffstat (limited to 'src/mongo/bson/mutable/document.cpp')
-rw-r--r-- | src/mongo/bson/mutable/document.cpp | 4741 |
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 |