path: root/src/mongo/bson/bsonelement.cpp

/**
 *    Copyright (C) 2014 MongoDB Inc.
 *
 *    This program is free software: you can redistribute it and/or  modify
 *    it under the terms of the GNU Affero General Public License, version 3,
 *    as published by the Free Software Foundation.
 *
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU Affero General Public License for more details.
 *
 *    You should have received a copy of the GNU Affero General Public License
 *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *    As a special exception, the copyright holders give permission to link the
 *    code of portions of this program with the OpenSSL library under certain
 *    conditions as described in each individual source file and distribute
 *    linked combinations including the program with the OpenSSL library. You
 *    must comply with the GNU Affero General Public License in all respects for
 *    all of the code used other than as permitted herein. If you modify file(s)
 *    with this exception, you may extend this exception to your version of the
 *    file(s), but you are not obligated to do so. If you do not wish to do so,
 *    delete this exception statement from your version. If you delete this
 *    exception statement from all source files in the program, then also delete
 *    it in the license file.
 */

#define MONGO_LOG_DEFAULT_COMPONENT ::mongo::logger::LogComponent::kDefault

#include "mongo/bson/bsonelement.h"

#include <cmath>
#include <boost/functional/hash.hpp>

#include "mongo/base/compare_numbers.h"
#include "mongo/base/data_cursor.h"
#include "mongo/db/jsobj.h"
#include "mongo/util/base64.h"
#include "mongo/util/hex.h"
#include "mongo/util/log.h"
#include "mongo/util/mongoutils/str.h"

namespace mongo {
    namespace str = mongoutils::str;

    using std::dec;
    using std::hex;
    using std::string;

    string BSONElement::jsonString( JsonStringFormat format, bool includeFieldNames, int pretty ) const {
        std::stringstream s;
        if ( includeFieldNames )
            s << '"' << escape( fieldName() ) << "\" : ";
        switch ( type() ) {
        case mongo::String:
        case Symbol:
            s << '"' << escape( string(valuestr(), valuestrsize()-1) ) << '"';
            break;
        case NumberLong:
            if (format == TenGen) {
                s << "NumberLong(" << _numberLong() << ")";
            }
            else {
                s << "{ \"$numberLong\" : \"" << _numberLong() << "\" }";
            }
            break;
        case NumberInt:
            if(format == JS) {
                s << "NumberInt(" << _numberInt() << ")";
                break;
            }
        case NumberDouble:
            if ( number() >= -std::numeric_limits< double >::max() &&
                 number() <= std::numeric_limits< double >::max() ) {
                s.precision( 16 );
                s << number();
            }
            // This is not valid JSON, but according to RFC-4627, "Numeric values that cannot be
            // represented as sequences of digits (such as Infinity and NaN) are not permitted." so
            // we are accepting the fact that if we have such values we cannot output valid JSON.
            else if ( std::isnan(number()) ) {
                s << "NaN";
            }
            else if ( std::isinf(number()) ) {
                s << ( number() > 0 ? "Infinity" : "-Infinity");
            }
            else {
                StringBuilder ss;
                ss << "Number " << number() << " cannot be represented in JSON";
                string message = ss.str();
                massert( 10311 ,  message.c_str(), false );
            }
            break;
        case mongo::Bool:
            s << ( boolean() ? "true" : "false" );
            break;
        case jstNULL:
            s << "null";
            break;
        case Undefined:
            if ( format == Strict ) {
                s << "{ \"$undefined\" : true }";
            }
            else {
                s << "undefined";
            }
            break;
        case Object:
            s << embeddedObject().jsonString( format, pretty );
            break;
        case mongo::Array: {
            if ( embeddedObject().isEmpty() ) {
                s << "[]";
                break;
            }
            s << "[ ";
            BSONObjIterator i( embeddedObject() );
            BSONElement e = i.next();
            if ( !e.eoo() ) {
                int count = 0;
                while ( 1 ) {
                    if( pretty ) {
                        s << '\n';
                        for( int x = 0; x < pretty; x++ )
                            s << "  ";
                    }

                    if (strtol(e.fieldName(), 0, 10) > count) {
                        s << "undefined";
                    }
                    else {
                        s << e.jsonString( format, false, pretty?pretty+1:0 );
                        e = i.next();
                    }
                    count++;
                    if ( e.eoo() )
                        break;
                    s << ", ";
                }
            }
            s << " ]";
            break;
        }
        case DBRef: {
            if ( format == TenGen )
                s << "Dbref( ";
            else
                s << "{ \"$ref\" : ";
            s << '"' << valuestr() << "\", ";
            if ( format != TenGen )
                s << "\"$id\" : ";
            s << '"' << mongo::OID::from(valuestr() + valuestrsize()) << "\" ";
            if ( format == TenGen )
                s << ')';
            else
                s << '}';
            break;
        }
        case jstOID:
            if ( format == TenGen ) {
                s << "ObjectId( ";
            }
            else {
                s << "{ \"$oid\" : ";
            }
            s << '"' << __oid() << '"';
            if ( format == TenGen ) {
                s << " )";
            }
            else {
                s << " }";
            }
            break;
        case BinData: {
            ConstDataCursor reader( value() );
            const int len = reader.readAndAdvance<LittleEndian<int>>();
            BinDataType type = static_cast<BinDataType>(reader.readAndAdvance<uint8_t>());

            s << "{ \"$binary\" : \"";
            base64::encode( s , reader.view() , len );
            s << "\", \"$type\" : \"" << hex;
            s.width( 2 );
            s.fill( '0' );
            s << type << dec;
            s << "\" }";
            break;
        }
        case mongo::Date:
            if (format == Strict) {
                Date_t d = date();
                s << "{ \"$date\" : ";
                // The two cases in which we cannot convert Date_t::millis to an ISO Date string are
                // when the date is too large to format (SERVER-13760), and when the date is before
                // the epoch (SERVER-11273).  Since Date_t internally stores millis as an unsigned
                // long long, despite the fact that it is logically signed (SERVER-8573), this check
                // handles both the case where Date_t::millis is too large, and the case where
                // Date_t::millis is negative (before the epoch).
                if (d.isFormattable()) {
                    s << "\"" << dateToISOStringLocal(date()) << "\"";
                }
                else {
                    s << "{ \"$numberLong\" : \"" << d.toMillisSinceEpoch() << "\" }";
                }
                s << " }";
            }
            else {
                s << "Date( ";
                if (pretty) {
                    Date_t d = date();
                    // The two cases in which we cannot convert Date_t::millis to an ISO Date string
                    // are when the date is too large to format (SERVER-13760), and when the date is
                    // before the epoch (SERVER-11273).  Since Date_t internally stores millis as an
                    // unsigned long long, despite the fact that it is logically signed
                    // (SERVER-8573), this check handles both the case where Date_t::millis is too
                    // large, and the case where Date_t::millis is negative (before the epoch).
                    if (d.isFormattable()) {
                        s << "\"" << dateToISOStringLocal(date()) << "\"";
                    }
                    else {
                        // FIXME: This is not parseable by the shell, since it may not fit in a
                        // float
                        s << d.toMillisSinceEpoch();
                    }
                }
                else {
                    s << date().asInt64();
                }
                s << " )";
            }
            break;
        case RegEx:
            if ( format == Strict ) {
                s << "{ \"$regex\" : \"" << escape( regex() );
                s << "\", \"$options\" : \"" << regexFlags() << "\" }";
            }
            else {
                s << "/" << escape( regex() , true ) << "/";
                // FIXME Worry about alpha order?
                for ( const char *f = regexFlags(); *f; ++f ) {
                    switch ( *f ) {
                    case 'g':
                    case 'i':
                    case 'm':
                        s << *f;
                    default:
                        break;
                    }
                }
            }
            break;

        case CodeWScope: {
            BSONObj scope = codeWScopeObject();
            if ( ! scope.isEmpty() ) {
                s << "{ \"$code\" : \"" << escape(_asCode()) << "\" , "
                  << "\"$scope\" : " << scope.jsonString() << " }";
                break;
            }
        }

        case Code:
            s << "\"" << escape(_asCode()) << "\"";
            break;

        case bsonTimestamp:
            if ( format == TenGen ) {
                s << "Timestamp( "
                  << durationCount<Seconds>(timestampTime().toDurationSinceEpoch())
                  << ", " << timestampInc() << " )";
            }
            else {
                s << "{ \"$timestamp\" : { \"t\" : "
                  << durationCount<Seconds>(timestampTime().toDurationSinceEpoch())
                  << ", \"i\" : " << timestampInc() << " } }";
            }
            break;

        case MinKey:
            s << "{ \"$minKey\" : 1 }";
            break;

        case MaxKey:
            s << "{ \"$maxKey\" : 1 }";
            break;

        default:
            StringBuilder ss;
            ss << "Cannot create a properly formatted JSON string with "
               << "element: " << toString() << " of type: " << type();
            string message = ss.str();
            massert( 10312 ,  message.c_str(), false );
        }
        return s.str();
    }

    int BSONElement::getGtLtOp( int def ) const {
        const char *fn = fieldName();
        if ( fn[0] == '$' && fn[1] ) {
            if ( fn[2] == 't' ) {
                if ( fn[1] == 'g' ) {
                    if ( fn[3] == 0 ) return BSONObj::GT;
                    else if ( fn[3] == 'e' && fn[4] == 0 ) return BSONObj::GTE;
                }
                else if ( fn[1] == 'l' ) {
                    if ( fn[3] == 0 ) return BSONObj::LT;
                    else if ( fn[3] == 'e' && fn[4] == 0 ) return BSONObj::LTE;
                }
            }
            else if ( fn[1] == 'n' && fn[2] == 'e' ) {
                if ( fn[3] == 0 )
                    return BSONObj::NE;
                if ( fn[3] == 'a' && fn[4] == 'r') // matches anything with $near prefix
                    return BSONObj::opNEAR;
            }
            else if ( fn[1] == 'm' ) {
                if ( fn[2] == 'o' && fn[3] == 'd' && fn[4] == 0 )
                    return BSONObj::opMOD;
                if ( fn[2] == 'a' && fn[3] == 'x' && fn[4] == 'D' && fn[5] == 'i' && fn[6] == 's' && fn[7] == 't' && fn[8] == 'a' && fn[9] == 'n' && fn[10] == 'c' && fn[11] == 'e' && fn[12] == 0 )
                    return BSONObj::opMAX_DISTANCE;
            }
            else if ( fn[1] == 't' && fn[2] == 'y' && fn[3] == 'p' && fn[4] == 'e' && fn[5] == 0 )
                return BSONObj::opTYPE;
            else if ( fn[1] == 'i' && fn[2] == 'n' && fn[3] == 0) {
                return BSONObj::opIN;
            } else if ( fn[1] == 'n' && fn[2] == 'i' && fn[3] == 'n' && fn[4] == 0 )
                return BSONObj::NIN;
            else if ( fn[1] == 'a' && fn[2] == 'l' && fn[3] == 'l' && fn[4] == 0 )
                return BSONObj::opALL;
            else if ( fn[1] == 's' && fn[2] == 'i' && fn[3] == 'z' && fn[4] == 'e' && fn[5] == 0 )
                return BSONObj::opSIZE;
            else if ( fn[1] == 'e' ) {
                if ( fn[2] == 'x' && fn[3] == 'i' && fn[4] == 's' && fn[5] == 't' && fn[6] == 's' && fn[7] == 0 )
                    return BSONObj::opEXISTS;
                if ( fn[2] == 'l' && fn[3] == 'e' && fn[4] == 'm' && fn[5] == 'M' && fn[6] == 'a' && fn[7] == 't' && fn[8] == 'c' && fn[9] == 'h' && fn[10] == 0 )
                    return BSONObj::opELEM_MATCH;
            }
            else if ( fn[1] == 'r' && fn[2] == 'e' && fn[3] == 'g' && fn[4] == 'e' && fn[5] == 'x' && fn[6] == 0 )
                return BSONObj::opREGEX;
            else if ( fn[1] == 'o' && fn[2] == 'p' && fn[3] == 't' && fn[4] == 'i' && fn[5] == 'o' && fn[6] == 'n' && fn[7] == 's' && fn[8] == 0 )
                return BSONObj::opOPTIONS;
            else if ( fn[1] == 'w' && fn[2] == 'i' && fn[3] == 't' && fn[4] == 'h' && fn[5] == 'i' && fn[6] == 'n' && fn[7] == 0 )
                return BSONObj::opWITHIN;
            else if (str::equals(fn + 1, "geoIntersects"))
                return BSONObj::opGEO_INTERSECTS;
            else if (str::equals(fn + 1, "geoNear"))
                return BSONObj::opNEAR;
            else if (str::equals(fn + 1, "geoWithin"))
                return BSONObj::opWITHIN;
        }
        return def;
    }

    /** transform a BSON array into a vector of BSONElements.
        we match array # positions with their vector position, and ignore
        any fields with non-numeric field names.
        */
    std::vector<BSONElement> BSONElement::Array() const {
        chk(mongo::Array);
        std::vector<BSONElement> v;
        BSONObjIterator i(Obj());
        while( i.more() ) {
            BSONElement e = i.next();
            const char *f = e.fieldName();

            unsigned u;
            Status status = parseNumberFromString( f, &u );
            if ( status.isOK() ) {
                verify( u < 1000000 );
                if( u >= v.size() )
                    v.resize(u+1);
                v[u] = e;
            }
            else {
                // ignore?
            }
        }
        return v;
    }
    
    /* wo = "well ordered" 
       note: (mongodb related) : this can only change in behavior when index version # changes
    */
    int BSONElement::woCompare( const BSONElement &e,
                                bool considerFieldName ) const {
        int lt = (int) canonicalType();
        int rt = (int) e.canonicalType();
        int x = lt - rt;
        if( x != 0 && (!isNumber() || !e.isNumber()) )
            return x;
        if ( considerFieldName ) {
            x = strcmp(fieldName(), e.fieldName());
            if ( x != 0 )
                return x;
        }
        x = compareElementValues(*this, e);
        return x;
    }


    BSONObj BSONElement::embeddedObjectUserCheck() const {
        if ( MONGO_likely(isABSONObj()) )
            return BSONObj(value());
        std::stringstream ss;
        ss << "invalid parameter: expected an object (" << fieldName() << ")";
        uasserted( 10065 , ss.str() );
        return BSONObj(); // never reachable
    }

    BSONObj BSONElement::embeddedObject() const {
        verify( isABSONObj() );
        return BSONObj(value());
    }

    BSONObj BSONElement::codeWScopeObject() const {
        verify( type() == CodeWScope );
        int strSizeWNull = ConstDataView(value() + 4).read<LittleEndian<int>>();
        return BSONObj( value() + 4 + 4 + strSizeWNull );
    }

    // wrap this element up as a singleton object.
    BSONObj BSONElement::wrap() const {
        BSONObjBuilder b(size()+6);
        b.append(*this);
        return b.obj();
    }

    BSONObj BSONElement::wrap( StringData newName ) const {
        BSONObjBuilder b(size() + 6 + newName.size());
        b.appendAs(*this,newName);
        return b.obj();
    }

    void BSONElement::Val(BSONObj& v) const { 
        v = Obj(); 
    }

    BSONObj BSONElement::Obj() const { 
        return embeddedObjectUserCheck(); 
    }

    BSONElement BSONElement::operator[] (const std::string& field) const {
        BSONObj o = Obj();
        return o[field];
    }

    int BSONElement::size( int maxLen ) const {
        if ( totalSize >= 0 )
            return totalSize;

        int remain = maxLen - fieldNameSize() - 1;

        int x = 0;
        switch ( type() ) {
        case EOO:
        case Undefined:
        case jstNULL:
        case MaxKey:
        case MinKey:
            break;
        case mongo::Bool:
            x = 1;
            break;
        case NumberInt:
            x = 4;
            break;
        case bsonTimestamp:
        case mongo::Date:
        case NumberDouble:
        case NumberLong:
            x = 8;
            break;
        case jstOID:
            x = OID::kOIDSize;
            break;
        case Symbol:
        case Code:
        case mongo::String:
            massert( 10313 ,  "Insufficient bytes to calculate element size", maxLen == -1 || remain > 3 );
            x = valuestrsize() + 4;
            break;
        case CodeWScope:
            massert( 10314 ,  "Insufficient bytes to calculate element size", maxLen == -1 || remain > 3 );
            x = objsize();
            break;

        case DBRef:
            massert( 10315 ,  "Insufficient bytes to calculate element size", maxLen == -1 || remain > 3 );
            x = valuestrsize() + 4 + 12;
            break;
        case Object:
        case mongo::Array:
            massert( 10316 ,  "Insufficient bytes to calculate element size", maxLen == -1 || remain > 3 );
            x = objsize();
            break;
        case BinData:
            massert( 10317 ,  "Insufficient bytes to calculate element size", maxLen == -1 || remain > 3 );
            x = valuestrsize() + 4 + 1/*subtype*/;
            break;
        case RegEx: {
            const char *p = value();
            size_t len1 = ( maxLen == -1 ) ? strlen( p ) : strnlen( p, remain );
            massert( 10318 ,  "Invalid regex string", maxLen == -1 || len1 < size_t(remain) );
            p = p + len1 + 1;
            size_t len2;
            if( maxLen == -1 )
                len2 = strlen( p );
            else {
                size_t x = remain - len1 - 1;
                verify( x <= 0x7fffffff );
                len2 = strnlen( p,  x );
                massert( 10319 ,  "Invalid regex options string", len2 < x );
            }
            x = (int) (len1 + 1 + len2 + 1);
        }
        break;
        default: {
            StringBuilder ss;
            ss << "BSONElement: bad type " << (int) type();
            std::string msg = ss.str();
            massert( 13655 , msg.c_str(),false);
        }
        }
        totalSize =  x + fieldNameSize() + 1; // BSONType

        return totalSize;
    }

    int BSONElement::size() const {
        if ( totalSize >= 0 )
            return totalSize;

        int x = 0;
        switch ( type() ) {
        case EOO:
        case Undefined:
        case jstNULL:
        case MaxKey:
        case MinKey:
            break;
        case mongo::Bool:
            x = 1;
            break;
        case NumberInt:
            x = 4;
            break;
        case bsonTimestamp:
        case mongo::Date:
        case NumberDouble:
        case NumberLong:
            x = 8;
            break;
        case jstOID:
            x = OID::kOIDSize;
            break;
        case Symbol:
        case Code:
        case mongo::String:
            x = valuestrsize() + 4;
            break;
        case DBRef:
            x = valuestrsize() + 4 + 12;
            break;
        case CodeWScope:
        case Object:
        case mongo::Array:
            x = objsize();
            break;
        case BinData:
            x = valuestrsize() + 4 + 1/*subtype*/;
            break;
        case RegEx: 
            {
                const char *p = value();
                size_t len1 = strlen(p);
                p = p + len1 + 1;
                size_t len2;
                len2 = strlen( p );
                x = (int) (len1 + 1 + len2 + 1);
            }
            break;
        default: 
            {
                StringBuilder ss;
                ss << "BSONElement: bad type " << (int) type();
                std::string msg = ss.str();
                massert(10320 , msg.c_str(),false);
            }
        }
        totalSize =  x + fieldNameSize() + 1; // BSONType

        return totalSize;
    }

    std::string BSONElement::toString( bool includeFieldName, bool full ) const {
        StringBuilder s;
        toString(s, includeFieldName, full);
        return s.str();
    }
    
    void BSONElement::toString( StringBuilder& s, bool includeFieldName, bool full, int depth ) const {

        if ( depth > BSONObj::maxToStringRecursionDepth ) {
            // check if we want the full/complete string
            if ( full ) {
                StringBuilder s;
                s << "Reached maximum recursion depth of ";
                s << BSONObj::maxToStringRecursionDepth;
                uassert(16150, s.str(), full != true);
            }
            s << "...";
            return;
        }

        if ( includeFieldName && type() != EOO )
            s << fieldName() << ": ";
        switch ( type() ) {
        case EOO:
            s << "EOO";
            break;
        case mongo::Date:
            s << "new Date(" << date().toMillisSinceEpoch() << ')';
            break;
        case RegEx: {
            s << "/" << regex() << '/';
            const char *p = regexFlags();
            if ( p ) s << p;
        }
        break;
        case NumberDouble:
            s.appendDoubleNice( number() );
            break;
        case NumberLong:
            s << _numberLong();
            break;
        case NumberInt:
            s << _numberInt();
            break;
        case mongo::Bool:
            s << ( boolean() ? "true" : "false" );
            break;
        case Object:
            embeddedObject().toString(s, false, full, depth+1);
            break;
        case mongo::Array:
            embeddedObject().toString(s, true, full, depth+1);
            break;
        case Undefined:
            s << "undefined";
            break;
        case jstNULL:
            s << "null";
            break;
        case MaxKey:
            s << "MaxKey";
            break;
        case MinKey:
            s << "MinKey";
            break;
        case CodeWScope:
            s << "CodeWScope( "
              << codeWScopeCode() << ", " << codeWScopeObject().toString(false, full) << ")";
            break;
        case Code:
            if ( !full &&  valuestrsize() > 80 ) {
                s.write(valuestr(), 70);
                s << "...";
            }
            else {
                s.write(valuestr(), valuestrsize()-1);
            }
            break;
        case Symbol:
        case mongo::String:
            s << '"';
            if ( !full &&  valuestrsize() > 160 ) {
                s.write(valuestr(), 150);
                s << "...\"";
            }
            else {
                s.write(valuestr(), valuestrsize()-1);
                s << '"';
            }
            break;
        case DBRef:
            s << "DBRef('" << valuestr() << "',";
            s << mongo::OID::from(valuestr() + valuestrsize()) << ')';
            break;
        case jstOID:
            s << "ObjectId('";
            s << __oid() << "')";
            break;
        case BinData:
            s << "BinData(" << binDataType() << ", ";
            {
                int len;
                const char *data = binDataClean(len);
                if ( !full && len > 80 ) {
                    s << toHex(data, 70) << "...)";
                }
                else {
                    s << toHex(data, len) << ")";
                }
            }
            break;
        case bsonTimestamp:
            s << "Timestamp " << timestampTime().toMillisSinceEpoch() << "|" << timestampInc();
            break;
        default:
            s << "?type=" << type();
            break;
        }
    }

    std::string BSONElement::_asCode() const {
        switch( type() ) {
        case mongo::String:
        case Code:
            return std::string(valuestr(), valuestrsize()-1);
        case CodeWScope:
            return std::string(codeWScopeCode(),
                               ConstDataView(valuestr()).read<LittleEndian<int>>() - 1);
        default:
            log() << "can't convert type: " << (int)(type()) << " to code" << std::endl;
        }
        uassert( 10062 ,  "not code" , 0 );
        return "";
    }

    std::ostream& operator<<( std::ostream &s, const BSONElement &e ) {
        return s << e.toString();
    }

    StringBuilder& operator<<( StringBuilder &s, const BSONElement &e ) {
        e.toString( s );
        return s;
    }

    template<> bool BSONElement::coerce<std::string>( std::string* out ) const {
        if ( type() != mongo::String )
            return false;
        *out = String();
        return true;
    }

    template<> bool BSONElement::coerce<int>( int* out ) const {
        if ( !isNumber() )
            return false;
        *out = numberInt();
        return true;
    }

    template<> bool BSONElement::coerce<long long>( long long* out ) const {
        if ( !isNumber() )
            return false;
        *out = numberLong();
        return true;
    }

    template<> bool BSONElement::coerce<double>( double* out ) const {
        if ( !isNumber() )
            return false;
        *out = numberDouble();
        return true;
    }

    template<> bool BSONElement::coerce<bool>( bool* out ) const {
        *out = trueValue();
        return true;
    }

    template<> bool BSONElement::coerce< std::vector<std::string> >( std::vector<std::string>* out ) const {
        if ( type() != mongo::Array )
            return false;
        return Obj().coerceVector<std::string>( out );
    }

    template<typename T> bool BSONObj::coerceVector( std::vector<T>* out ) const {
        BSONObjIterator i( *this );
        while ( i.more() ) {
            BSONElement e = i.next();
            T t;
            if ( ! e.coerce<T>( &t ) )
                return false;
            out->push_back( t );
        }
        return true;
    }

    // used by jsonString()
    std::string escape( const std::string& s , bool escape_slash) {
        StringBuilder ret;
        for ( std::string::const_iterator i = s.begin(); i != s.end(); ++i ) {
            switch ( *i ) {
            case '"':
                ret << "\\\"";
                break;
            case '\\':
                ret << "\\\\";
                break;
            case '/':
                ret << (escape_slash ? "\\/" : "/");
                break;
            case '\b':
                ret << "\\b";
                break;
            case '\f':
                ret << "\\f";
                break;
            case '\n':
                ret << "\\n";
                break;
            case '\r':
                ret << "\\r";
                break;
            case '\t':
                ret << "\\t";
                break;
            default:
                if ( *i >= 0 && *i <= 0x1f ) {
                    //TODO: these should be utf16 code-units not bytes
                    char c = *i;
                    ret << "\\u00" << toHexLower(&c, 1);
                }
                else {
                    ret << *i;
                }
            }
        }
        return ret.str();
    }

    /**
     * l and r must be same canonicalType when called.
     */
    int compareElementValues(const BSONElement& l, const BSONElement& r) {
        int f;

        switch ( l.type() ) {
        case EOO:
        case Undefined: // EOO and Undefined are same canonicalType
        case jstNULL:
        case MaxKey:
        case MinKey:
            f = l.canonicalType() - r.canonicalType();
            if ( f<0 ) return -1;
            return f==0 ? 0 : 1;
        case Bool:
            return *l.value() - *r.value();
        case bsonTimestamp:
            // unsigned compare for timestamps - note they are not really dates but (ordinal + time_t)
            if ( l.date() < r.date() )
                return -1;
            return l.date() == r.date() ? 0 : 1;
        case Date:
            // Signed comparisons for Dates.
            {
                const Date_t a = l.Date();
                const Date_t b = r.Date();
                if( a < b ) 
                    return -1;
                return a == b ? 0 : 1;
            }

        case NumberInt: {
            // All types can precisely represent all NumberInts, so it is safe to simply convert to
            // whatever rhs's type is.
            switch (r.type()) {
            case NumberInt: return compareInts(l._numberInt(), r._numberInt());
            case NumberLong: return compareLongs(l._numberInt(), r._numberLong());
            case NumberDouble: return compareDoubles(l._numberInt(), r._numberDouble());
            default: invariant(false);
            }
        }

        case NumberLong: {
            switch (r.type()) {
            case NumberLong: return compareLongs(l._numberLong(), r._numberLong());
            case NumberInt: return compareLongs(l._numberLong(), r._numberInt());
            case NumberDouble: return compareLongToDouble(l._numberLong(), r._numberDouble());
            default: invariant(false);
            }
        }

        case NumberDouble: {
            switch (r.type()) {
            case NumberDouble: return compareDoubles(l._numberDouble(), r._numberDouble());
            case NumberInt: return compareDoubles(l._numberDouble(), r._numberInt());
            case NumberLong: return compareDoubleToLong(l._numberDouble(), r._numberLong());
            default: invariant(false);
            }
        }

        case jstOID:
            return memcmp(l.value(), r.value(), OID::kOIDSize);
        case Code:
        case Symbol:
        case String:
            /* todo: a utf sort order version one day... */
            {
                // we use memcmp as we allow zeros in UTF8 strings
                int lsz = l.valuestrsize();
                int rsz = r.valuestrsize();
                int common = std::min(lsz, rsz);
                int res = memcmp(l.valuestr(), r.valuestr(), common);
                if( res ) 
                    return res;
                // longer std::string is the greater one
                return lsz-rsz;
            }
        case Object:
        case Array:
            return l.embeddedObject().woCompare( r.embeddedObject() );
        case DBRef: {
            int lsz = l.valuesize();
            int rsz = r.valuesize();
            if ( lsz - rsz != 0 ) return lsz - rsz;
            return memcmp(l.value(), r.value(), lsz);
        }
        case BinData: {
            int lsz = l.objsize(); // our bin data size in bytes, not including the subtype byte
            int rsz = r.objsize();
            if ( lsz - rsz != 0 ) return lsz - rsz;
            return memcmp(l.value()+4, r.value()+4, lsz+1 /*+1 for subtype byte*/);
        }
        case RegEx: {
            int c = strcmp(l.regex(), r.regex());
            if ( c )
                return c;
            return strcmp(l.regexFlags(), r.regexFlags());
        }
        case CodeWScope : {
            int cmp = StringData(l.codeWScopeCode(), l.codeWScopeCodeLen() - 1).compare(
                      StringData(r.codeWScopeCode(), r.codeWScopeCodeLen() - 1));
            if (cmp) return cmp;

            return l.codeWScopeObject().woCompare(r.codeWScopeObject());
        }
        default:
            verify( false);
        }
        return -1;
    }
 
    size_t BSONElement::Hasher::operator()(const BSONElement& elem) const {
        size_t hash = 0;

        boost::hash_combine(hash, elem.canonicalType());

        const StringData fieldName = elem.fieldNameStringData();
        if (!fieldName.empty()) {
            boost::hash_combine(hash, StringData::Hasher()(fieldName));
        }

        switch (elem.type()) {
            // Order of types is the same as in compareElementValues().

        case mongo::EOO:
        case mongo::Undefined:
        case mongo::jstNULL:
        case mongo::MaxKey:
        case mongo::MinKey:
            // These are valueless types
            break;

        case mongo::Bool:
            boost::hash_combine(hash, elem.boolean());
            break;

        case mongo::bsonTimestamp:
            boost::hash_combine(hash, elem.timestamp().asULL());
            break;

        case mongo::Date:
            boost::hash_combine(hash, elem.date().asInt64());
            break;

        case mongo::NumberDouble:
        case mongo::NumberLong:
        case mongo::NumberInt: {
            // This converts all numbers to doubles, which ignores the low-order bits of
            // NumberLongs > 2**53, but that is ok since the hash will still be the same for
            // equal numbers and is still likely to be different for different numbers.
            // SERVER-16851
            const double dbl = elem.numberDouble();
            if (std::isnan(dbl)) {
                boost::hash_combine(hash, std::numeric_limits<double>::quiet_NaN());
            }
            else {
                boost::hash_combine(hash, dbl);
            }
            break;
        }

        case mongo::jstOID:
            elem.__oid().hash_combine(hash);
            break;

        case mongo::Code:
        case mongo::Symbol:
        case mongo::String:
            boost::hash_combine(hash, StringData::Hasher()(elem.valueStringData()));
            break;

        case mongo::Object:
        case mongo::Array:
            boost::hash_combine(hash, BSONObj::Hasher()(elem.embeddedObject()));
            break;

        case mongo::DBRef:
        case mongo::BinData:
            // All bytes of the value are required to be identical.
            boost::hash_combine(hash, StringData::Hasher()(StringData(elem.value(),
                                                                      elem.valuesize())));
            break;

        case mongo::RegEx:
            boost::hash_combine(hash, StringData::Hasher()(elem.regex()));
            boost::hash_combine(hash, StringData::Hasher()(elem.regexFlags()));
            break;

        case mongo::CodeWScope: {
            boost::hash_combine(hash, StringData::Hasher()(
                                        StringData(elem.codeWScopeCode(),
                                                   elem.codeWScopeCodeLen())));
            boost::hash_combine(hash, BSONObj::Hasher()(elem.codeWScopeObject()));
            break;
        }
        }
        return hash;
    }

} // namespace mongo