text: //@file update_internal.cpp
  
  /**
   *    Copyright (C) 2012 10gen Inc.
   *    Copyright (C) 2013 Tokutek 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/>.
   */
  
  #include "pch.h"
  
  #include <algorithm> // for max
  
  #include "mongo/db/field_ref.h"
  #include "mongo/db/jsobjmanipulator.h"
  #include "mongo/db/oplog.h"
  #include "mongo/util/mongoutils/str.h"
  
  #include "update_internal.h"
  
  //#define DEBUGUPDATE(x) cout << x << endl;
  #define DEBUGUPDATE(x)
  
  namespace mongo {
  
      const char* Mod::modNames[] = { "$inc", "$set", "$push", "$pushAll", "$pull", "$pullAll" , "$pop", "$unset" ,
                                      "$bitand" , "$bitor" , "$bit" , "$addToSet", "$rename", "$rename" ,
                                      "$setOnInsert"
                                    };
      unsigned Mod::modNamesNum = sizeof(Mod::modNames)/sizeof(char*);
  
      bool Mod::_pullElementMatch( BSONElement& toMatch ) const {
  
          if ( elt.type() != Object ) {
              // if elt isn't an object, then comparison will work
              return toMatch.woCompare( elt , false ) == 0;
          }
  
          if ( matcherOnPrimitive )
              return matcher->matches( toMatch.wrap( "" ) );
  
          if ( toMatch.type() != Object ) {
              // looking for an object, so this can't match
              return false;
          }
  
          // now we have an object on both sides
          return matcher->matches( toMatch.embeddedObject() );
      }
  
      void Mod::appendIncremented( BSONBuilderBase& builder , const BSONElement& in, ModState& ms ) const {
          BSONType a = in.type();
          BSONType b = elt.type();
  
          if ( a == NumberDouble || b == NumberDouble ) {
              ms.incType = NumberDouble;
              ms.incdouble = elt.numberDouble() + in.numberDouble();
          }
          else if ( a == NumberLong || b == NumberLong ) {
              ms.incType = NumberLong;
              ms.inclong = elt.numberLong() + in.numberLong();
          }
          else {
              int x = elt.numberInt() + in.numberInt();
              if ( x < 0 && elt.numberInt() > 0 && in.numberInt() > 0 ) {
                  // overflow
                  ms.incType = NumberLong;
                  ms.inclong = elt.numberLong() + in.numberLong();
              }
              else {
                  ms.incType = NumberInt;
                  ms.incint = elt.numberInt() + in.numberInt();
              }
          }
  
          ms.appendIncValue( builder , false );
      }
  
      void appendUnset( BSONBuilderBase& builder ) {
          if ( builder.isArray() ) {
              builder.appendNull();
          }
      }
  
      void Mod::apply( BSONBuilderBase& builder , BSONElement in , ModState& ms ) const {
          if ( ms.dontApply ) {
              // Pass the original element through unchanged.
              builder << in;
              return;
          }
  
          switch ( op ) {
  
          case INC: {
              appendIncremented( builder , in , ms );
              break;
          }
  
          case SET_ON_INSERT:
              // There is a corner case that would land us here (making a change to an existing
              // field with $setOnInsert). If we're in an upsert, and the query portion of the
              // update creates a field, we can modify it with $setOnInsert. This degenerates
              // into a $set, so we fall through to the next case.
              // Fall through.
  
          case SET: {
              _checkForAppending( elt );
              builder.appendAs( elt , shortFieldName );
              break;
          }
  
          case UNSET: {
              appendUnset( builder );
              break;
          }
  
          case PUSH: {
              uassert( 10131 ,  "$push can only be applied to an array" , in.type() == Array );
  
              //
              // We can be in a single element push case, a "push all" case, or a "push all" case
              // with a slice requirement (ie, a "push to size"). In each of these, we decide
              // differently how much of the existing- and of the parameter-array to copy to the
              // final object.
              //
  
              // Start the resulting array's builder.
              BSONArrayBuilder bb( builder.subarrayStart( shortFieldName ) );
  
              // If in the single element push case, we'll copy all elements of the existing
              // array and add the new one.
              if ( ! isEach() ) {
                  BSONObjIterator i( in.embeddedObject() );
                  while ( i.more() ) {
                      bb.append( i.next() );
                  }
                  bb.append( elt );
                  bb.done();
              }
  
              // If we're in the "push all" case, we'll copy all element of both the existing and
              // parameter arrays.
              else if ( isEach() && ! isSliceOnly() && ! isSliceAndSort() ) {
                  BSONObjIterator i( in.embeddedObject() );
                  while ( i.more() ) {
                      bb.append( i.next() );
                  }
                  BSONObjIterator j( getEach() );
                  while ( j.more() ) {
                      bb.append( j.next() );
                  }
                  bb.done();
              }
  
              // If we're in the "push with a $each" case with slice, we have to decide how much
              // of each of the existing and parameter arrays to copy to the final object.
              else if ( isSliceOnly() ) {
                  long long slice = getSlice();
                  BSONObj eachArray = getEach();
                  long long arraySize = in.embeddedObject().nFields();
                  long long eachArraySize = eachArray.nFields();
  
                  // Zero slice is equivalent to resetting the array in the final object, so
                  // we won't copy anything.
                  if (slice == 0) {
                      // no-op
                  }
  
                  // If the parameter array alone is larger than the slice, then only copy
                  // object from that array.
                  else if (slice <= eachArraySize) {
                      long long skip = eachArraySize - slice;
                      BSONObjIterator j( getEach() );
                      while ( j.more() ) {
                          if ( skip-- > 0 ) {
                              j.next();
                              continue;
                          }
                          bb.append( j.next() );
                      }
                  }
  
                  // If the parameter array is not sufficient to fill the slice, then some (or all)
                  // the elements from the existing array will be copied too.
                  else {
                      long long skip = std::max(0LL, arraySize - (slice - eachArraySize) );
                      BSONObjIterator i( in.embeddedObject() );
                      while ( i.more() ) {
                          if (skip-- > 0) {
                              i.next();
                              continue;
                          }
                          bb.append( i.next() );
                      }
                      BSONObjIterator j( getEach() );
                      while ( j.more() ) {
                          bb.append( j.next() );
                      }
                  }
                  bb.done();
              }
  
              // If we're in the "push all" case ($push with a $each) with sort, we have to
              // concatenate the existing array with the $each array, sort the result, and then
              // decide how much of each of the resulting work area to copy to the final object.
              else {
                  long long slice = getSlice();
  
                  // Zero slice is equivalent to resetting the array in the final object, so
                  // we only go into sorting if there is anything to sort.
                  if ( slice > 0 ) {
                      vector<BSONObj> workArea;
                      BSONObjIterator i( in.embeddedObject() );
                      while ( i.more() ) {
                          workArea.push_back( i.next().Obj() );
                      }
                      BSONObjIterator j( getEach() );
                      while ( j.more() ) {
                          workArea.push_back( j.next().Obj() );
                      }
                      ProjectKeyCmp cmp( getSort() );
                      sort( workArea.begin(), workArea.end(), cmp );
  
                      long long skip = std::max( 0LL,
                                                 (long long)workArea.size() - slice );
                      for ( vector<BSONObj>::iterator it = workArea.begin();
                           it != workArea.end();
                           ++it ) {
                          if ( skip-- > 0 ) {
                              continue;
                          }
                          bb.append( *it );
                      }
                  }
                  bb.done();
              }
  
              break;
          }
  
          case ADDTOSET: {
              uassert( 12592 ,  "$addToSet can only be applied to an array" , in.type() == Array );
              BSONArrayBuilder bb( builder.subarrayStart( shortFieldName ) );
              BSONObjIterator i( in.embeddedObject() );
  
              if ( isEach() ) {
  
                  BSONElementSet toadd;
                  parseEach( toadd );
  
                  while ( i.more() ) {
                      BSONElement cur = i.next();
                      bb.append( cur );
                      toadd.erase( cur );
                  }
  
                  {
                      BSONObjIterator i( getEach() );
                      while ( i.more() ) {
                          BSONElement e = i.next();
                          if ( toadd.count(e) ) {
                              bb.append( e );
                              toadd.erase( e );
                          }
                      }
                  }
                  bb.done();
              }
              else {
                  bool found = false;
                  while ( i.more() ) {
                      BSONElement cur = i.next();
                      bb.append( cur );
                      if ( elt.woCompare( cur , false ) == 0 ) {
                          found = true;
                      }
                  }
  
                  if ( !found ) {
                      bb.append( elt );
                  }
                  bb.done();
              }
  
              break;
          }
  
          case PUSH_ALL: {
              uassert( 10132 ,  "$pushAll can only be applied to an array" , in.type() == Array );
              uassert( 10133 ,  "$pushAll has to be passed an array" , elt.type() );
  
              BSONArrayBuilder bb( builder.subarrayStart( shortFieldName ) );
  
              BSONObjIterator i( in.embeddedObject() );
              while ( i.more() ) {
                  bb.append( i.next() );
              }
  
              i = BSONObjIterator( elt.embeddedObject() );
              while ( i.more() ) {
                  bb.append( i.next() );
              }
              bb.done();
              break;
          }
  
          case PULL:
          case PULL_ALL: {
              uassert( 10134 ,  "$pull/$pullAll can only be applied to an array" , in.type() == Array );
              BSONArrayBuilder bb( builder.subarrayStart( shortFieldName ) );
  
              //temporarily record the things to pull. only use this set while 'elt' in scope.
              BSONElementSet toPull;
              if ( op == PULL_ALL ) {
                  BSONObjIterator j( elt.embeddedObject() );
                  while ( j.more() ) {
                      toPull.insert( j.next() );
                  }
              }
  
              BSONObjIterator i( in.embeddedObject() );
              while ( i.more() ) {
                  BSONElement e = i.next();
                  bool allowed = true;
  
                  if ( op == PULL ) {
                      allowed = ! _pullElementMatch( e );
                  }
                  else {
                      allowed = ( toPull.find( e ) == toPull.end() );
                  }
  
                  if ( allowed )
                      bb.append( e );
              }
              bb.done();
              break;
          }
  
          case POP: {
              uassert( 10135 ,  "$pop can only be applied to an array" , in.type() == Array );
              BSONArrayBuilder bb( builder.subarrayStart( shortFieldName ) );
  
  
              BSONObjIterator i( in.embeddedObject() );
              if ( elt.isNumber() && elt.number() < 0 ) {
                  // pop from front
                  if ( i.more() ) {
                      i.next();
                  }
  
                  while( i.more() ) {
                      bb.append( i.next() );
                  }
              }
              else {
                  // pop from back
                  while( i.more() ) {
                      BSONElement arrI = i.next();
                      if ( i.more() ) {
                          bb.append( arrI );
                      }
                  }
              }
              bb.done();
              break;
          }
  
          case BIT: {
              uassert( 10136 ,  "$bit needs an object" , elt.type() == Object );
              uassert( 10137 ,  "$bit can only be applied to numbers" , in.isNumber() );
              uassert( 10138 ,  "$bit cannot update a value of type double" , in.type() != NumberDouble );
  
              int x = in.numberInt();
              long long y = in.numberLong();
  
              BSONObjIterator it( elt.embeddedObject() );
              while ( it.more() ) {
                  BSONElement e = it.next();
                  uassert( 10139 ,  "$bit field must be number" , e.isNumber() );
                  if ( str::equals(e.fieldName(), "and") ) {
                      switch( in.type() ) {
                      case NumberInt: x = x&e.numberInt(); break;
                      case NumberLong: y = y&e.numberLong(); break;
                      default: verify( 0 );
                      }
                  }
                  else if ( str::equals(e.fieldName(), "or") ) {
                      switch( in.type() ) {
                      case NumberInt: x = x|e.numberInt(); break;
                      case NumberLong: y = y|e.numberLong(); break;
                      default: verify( 0 );
                      }
                  }
                  else {
                      uasserted(9016, str::stream() << "unknown $bit operation: " << e.fieldName());
                  }
              }
  
              switch( in.type() ) {
  
              case NumberInt:
                  builder.append( shortFieldName , x );
                  ms.incType = NumberInt;
                  ms.incint = x;
                  break;
  
              case NumberLong:
                  builder.append( shortFieldName , y );
                  ms.incType = NumberLong;
                  ms.inclong = y;
                  break;
  
              default: verify( 0 );
              }
  
              break;
          }
  
          case RENAME_FROM: {
              break;
          }
  
          case RENAME_TO: {
              ms.handleRename( builder, shortFieldName );
              break;
          }
  
          default:
              uasserted( 9017 , str::stream() << "Mod::apply can't handle type: " << op );
          }
      }
  
      // -1 inside a non-object (non-object could be array)
      // 0 missing
      // 1 found
      int validRenamePath( BSONObj obj, const char* path ) {
          while( const char* p = strchr( path, '.' ) ) {
              string left( path, p - path );
              BSONElement e = obj.getField( left );
              if ( e.eoo() ) {
                  return 0;
              }
              if ( e.type() != Object ) {
                  return -1;
              }
              obj = e.embeddedObject();
              path = p + 1;
          }
          return !obj.getField( path ).eoo();
      }
  
      auto_ptr<ModSetState> ModSet::prepare(const BSONObj& obj, bool insertion) const {
          DEBUGUPDATE( "\t start prepare" );
          auto_ptr<ModSetState> mss( new ModSetState( obj ) );
  
  
          // Perform this check first, so that we don't leave a partially modified object on uassert.
          for ( ModHolder::const_iterator i = _mods.begin(); i != _mods.end(); ++i ) {
              DEBUGUPDATE( "\t\t prepare : " << i->first );
              mss->_mods[i->first].reset( new ModState() );
              ModState& ms = *mss->_mods[i->first];
  
              const Mod& m = i->second;
  
              // Check for any positional operators that have not been replaced with a numeric field
              // name (from a query match element).
              FieldRef fieldRef;
              fieldRef.parse( m.fieldName );
              StringData positionalOpField( "$" );
              for( size_t i = 0; i < fieldRef.numParts(); ++i ) {
                   uassert( 16650,
                            "Cannot apply the positional operator without a corresponding query "
                            "field containing an array.",
                            fieldRef.getPart( i ).compare( positionalOpField ) != 0 );
              }
  
              BSONElement e = obj.getFieldDotted(m.fieldName);
  
              ms.m = &m;
              ms.old = e;
  
              if ( m.op == Mod::RENAME_FROM ) {
                  int source = validRenamePath( obj, m.fieldName );
                  uassert( 13489, "$rename source field invalid", source != -1 );
                  if ( source != 1 ) {
                      ms.dontApply = true;
                  }
                  continue;
              }
  
              if ( m.op == Mod::RENAME_TO ) {
                  int source = validRenamePath( obj, m.renameFrom() );
                  if ( source == 1 ) {
                      int target = validRenamePath( obj, m.fieldName );
                      uassert( 13490, "$rename target field invalid", target != -1 );
                      ms.newVal = obj.getFieldDotted( m.renameFrom() );
                  }
                  else {
                      ms.dontApply = true;
                  }
                  continue;
              }
  
              if ( m.op != Mod::SET_ON_INSERT && e.eoo() ) {
                  continue;
              }
  
              switch( m.op ) {
              case Mod::INC:
                  uassert( 10140 ,  "Cannot apply $inc modifier to non-number", e.isNumber() || e.eoo() );
                  break;
  
              default:
              case Mod::SET:
                  break;
  
              case Mod::SET_ON_INSERT:
                  // If the document exist (i.e this is an update, not an insert) $setOnInsert
                  // becomes a no-op.
                  if ( !insertion ) {
                      ms.dontApply = true;
                  }
                  break;
  
              case Mod::PUSH:
              case Mod::PUSH_ALL:
                  uassert( 10141,
                           "Cannot apply $push/$pushAll modifier to non-array",
                           e.type() == Array || e.eoo() );
  
                  // Currently, we require the base array of a $sort to be made of
                  // objects (as opposed to base types).
                  if ( !e.eoo() && m.isEach() && m.isSliceAndSort() ) {
                      BSONObjIterator i( e.embeddedObject() );
                      while ( i.more() ) {
                          BSONElement arrayItem = i.next();
                          uassert( 16638,
                                   "$sort can only be applied to an array of objects",
                                   arrayItem.type() == Object );
                      }
                  }
                  break;
  
              case Mod::PULL:
              case Mod::PULL_ALL:
                  uassert( 10142,
                           "Cannot apply $pull/$pullAll modifier to non-array",
                           e.type() == Array || e.eoo() );
                  break;
  
              case Mod::POP:
                  uassert( 10143,
                           "Cannot apply $pop modifier to non-array",
                           e.type() == Array || e.eoo() );
                  break;
  
              case Mod::ADDTOSET:
                  uassert( 12591,
                           "Cannot apply $addToSet modifier to non-array",
                           e.type() == Array || e.eoo() );
                  break;
              }
          }
  
          DEBUGUPDATE( "\t mss\n" << mss->toString() << "\t--" );
  
          return mss;
      }
  
      typedef map<string, vector<ModState*> > NamedModMap;
  
      string ModState::toString() const {
          stringstream ss;
          return ss.str();
      }
  
      void ModState::handleRename( BSONBuilderBase& newObjBuilder, const char* shortFieldName ) {
          newObjBuilder.appendAs( newVal , shortFieldName );
          BSONObjBuilder b;
          b.appendAs( newVal, shortFieldName );
          verify( _objData.isEmpty() );
          _objData = b.obj();
          newVal = _objData.firstElement();
      }
  
      void ModSetState::_appendNewFromMods( const string& root,
                                            ModState& modState,
                                            BSONBuilderBase& builder,
                                            set<string>& onedownseen ) {
          Mod& m = *((Mod*)(modState.m)); // HACK
          switch (m.op) {
          // unset/pull/pullAll on nothing does nothing, so don't append anything. Still,
          // explicitly log that the target array was reset.
          case Mod::POP:
          case Mod::PULL:
          case Mod::PULL_ALL:
          case Mod::UNSET:
              return;
  
          // $rename/$setOnInsert may involve dotted path creation, so we want to make sure we're
          // not creating a path here for a rename that's a no-op. In other words if we're
          // issuing a {$rename: {a.b : c.d} } that's a no-op, we don't want to create the a and
          // c paths here. See test NestedNoName in the 'repl' suite.
          case Mod::RENAME_FROM:
          case Mod::RENAME_TO:
          case Mod::SET_ON_INSERT:
              if (modState.dontApply) {
                  return;
              }
  
          default:
              ;// fall through
          }
          const char*  temp = modState.fieldName();
          temp += root.size();
          const char* dot = strchr( temp , '.' );
          if ( dot ) {
              string nr( modState.fieldName() , 0 , 1 + ( dot - modState.fieldName() ) );
              string nf( temp , 0 , dot - temp );
              if ( onedownseen.count( nf ) )
                  return;
              onedownseen.insert( nf );
              BSONObjBuilder bb ( builder.subobjStart( nf ) );
              // Always insert an object, even if the field name is numeric.
              createNewObjFromMods( nr , bb , BSONObj() );
              bb.done();
          }
          else {
              appendNewFromMod( modState , builder );
          }
      }
  
      bool ModSetState::duplicateFieldName( const BSONElement& a, const BSONElement& b ) {
          return
          !a.eoo() &&
          !b.eoo() &&
          ( a.rawdata() != b.rawdata() ) &&
          str::equals( a.fieldName(), b.fieldName() );
      }
  
      ModSetState::ModStateRange ModSetState::modsForRoot( const string& root ) {
          ModStateHolder::iterator mstart = _mods.lower_bound( root );
          StringBuilder buf;
          buf << root << (char)255;
          ModStateHolder::iterator mend = _mods.lower_bound( buf.str() );
          return make_pair( mstart, mend );
      }
  
      void ModSetState::createNewObjFromMods( const string& root,
                                              BSONObjBuilder& builder,
                                              const BSONObj& obj ) {
          BSONObjIteratorSorted es( obj );
          createNewFromMods( root, builder, es, modsForRoot( root ), LexNumCmp( true ) );
      }
  
      void ModSetState::createNewArrayFromMods( const string& root,
                                                BSONArrayBuilder& builder,
                                                const BSONArray& arr ) {
          BSONArrayIteratorSorted es( arr );
          ModStateRange objectOrderedRange = modsForRoot( root );
          ModStateHolder arrayOrderedMods( LexNumCmp( false ) );
          arrayOrderedMods.insert( objectOrderedRange.first, objectOrderedRange.second );
          ModStateRange arrayOrderedRange( arrayOrderedMods.begin(), arrayOrderedMods.end() );
          createNewFromMods( root, builder, es, arrayOrderedRange, LexNumCmp( false ) );
      }
  
      void ModSetState::createNewFromMods( const string& root,
                                           BSONBuilderBase& builder,
                                           BSONIteratorSorted& es,
                                           const ModStateRange& modRange,
                                           const LexNumCmp& lexNumCmp ) {
  
          DEBUGUPDATE( "\t\t createNewFromMods root: " << root );
          ModStateHolder::iterator m = modRange.first;
          const ModStateHolder::const_iterator mend = modRange.second;
          BSONElement e = es.next();
  
          set<string> onedownseen;
          BSONElement prevE;
          while ( !e.eoo() && m != mend ) {
  
              if ( duplicateFieldName( prevE, e ) ) {
                  // Just copy through an element with a duplicate field name.
                  builder.append( e );
                  prevE = e;
                  e = es.next();
                  continue;
              }
              prevE = e;
  
              string field = root + e.fieldName();
              FieldCompareResult cmp = compareDottedFieldNames( m->second->m->fieldName , field ,
                                                               lexNumCmp );
  
              DEBUGUPDATE( "\t\t\t field:" << field << "\t mod:"
                           << m->second->m->fieldName << "\t cmp:" << cmp
                           << "\t short: " << e.fieldName() );
  
              switch ( cmp ) {
  
              case LEFT_SUBFIELD: { // Mod is embedded under this element
                  uassert( 10145,
                           str::stream() << "LEFT_SUBFIELD only supports Object: " << field
                           << " not: " << e.type() , e.type() == Object || e.type() == Array );
                  if ( onedownseen.count( e.fieldName() ) == 0 ) {
                      onedownseen.insert( e.fieldName() );
                      if ( e.type() == Object ) {
                          BSONObjBuilder bb( builder.subobjStart( e.fieldName() ) );
                          stringstream nr; nr << root << e.fieldName() << ".";
                          createNewObjFromMods( nr.str() , bb , e.Obj() );
                          bb.done();
                      }
                      else {
                          BSONArrayBuilder ba( builder.subarrayStart( e.fieldName() ) );
                          stringstream nr; nr << root << e.fieldName() << ".";
                          createNewArrayFromMods( nr.str() , ba , BSONArray( e.embeddedObject() ) );
                          ba.done();
                      }
                      // inc both as we handled both
                      e = es.next();
                      m++;
                      while ( m != mend &&
                              ( compareDottedFieldNames( m->second->m->fieldName , field , lexNumCmp ) ==
                                LEFT_SUBFIELD ) ) {
                          m++;
                      }
                  }
                  else {
                      massert( 16069 , "ModSet::createNewFromMods - "
                              "SERVER-4777 unhandled duplicate field" , 0 );
                  }
                  continue;
              }
              case LEFT_BEFORE: // Mod on a field that doesn't exist
                  DEBUGUPDATE( "\t\t\t\t creating new field for: " << m->second->m->fieldName );
                  _appendNewFromMods( root , *m->second , builder , onedownseen );
                  m++;
                  continue;
              case SAME:
                  DEBUGUPDATE( "\t\t\t\t applying mod on: " << m->second->m->fieldName );
                  m->second->apply( builder , e );
                  e = es.next();
                  m++;
                  continue;
              case RIGHT_BEFORE: // field that doesn't have a MOD
                  DEBUGUPDATE( "\t\t\t\t just copying" );
                  builder.append( e ); // if array, ignore field name
                  e = es.next();
                  continue;
              case RIGHT_SUBFIELD:
                  massert( 10399 ,  "ModSet::createNewFromMods - RIGHT_SUBFIELD should be impossible" , 0 );
                  break;
              default:
                  massert( 10400 ,  "unhandled case" , 0 );
              }
          }
  
          // finished looping the mods, just adding the rest of the elements
          while ( !e.eoo() ) {
              DEBUGUPDATE( "\t\t\t copying: " << e.fieldName() );
              builder.append( e );  // if array, ignore field name
              e = es.next();
          }
  
          // do mods that don't have fields already
          for ( ; m != mend; m++ ) {
              DEBUGUPDATE( "\t\t\t\t appending from mod at end: " << m->second->m->fieldName );
              _appendNewFromMods( root , *m->second , builder , onedownseen );
          }
      }
  
      BSONObj ModSetState::createNewFromMods() {
          BSONObjBuilder b( (int)(_obj.objsize() * 1.1) );
          createNewObjFromMods( "" , b , _obj );
          return _newFromMods = b.obj();
      }
  
      string ModSetState::toString() const {
          stringstream ss;
          for ( ModStateHolder::const_iterator i=_mods.begin(); i!=_mods.end(); ++i ) {
              ss << "\t\t" << i->first << "\t" << i->second->toString() << "\n";
          }
          return ss.str();
      }
  
      BSONObj ModSet::createNewFromQuery( const BSONObj& query ) {
          BSONObj newObj;
  
          {
              BSONObjBuilder bb;
              EmbeddedBuilder eb( &bb );
              BSONObjIteratorSorted i( query );
              while ( i.more() ) {
                  BSONElement e = i.next();
                  if ( e.fieldName()[0] == '$' ) // for any operators we add
                      continue;
  
                  if ( e.type() == Object && e.embeddedObject().firstElementFieldName()[0] == '$' ) {
                      // we have something like { x : { $gt : 5 } }
                      // this can be a query piece
                      // or can be a dbref or something
  
                      int op = e.embeddedObject().firstElement().getGtLtOp();
                      if ( op > 0 ) {
                          // This means this is a $gt type filter, so don't make it part of the new
                          // object.
                          continue;
                      }
  
                      if ( str::equals( e.embeddedObject().firstElement().fieldName(), "$not" ) ) {
                          // A $not filter operator is not detected in getGtLtOp() and should not
                          // become part of the new object.
                          continue;
                      }
                  }
  
                  eb.appendAs( e , e.fieldName() );
              }
              eb.done();
              newObj = bb.obj();
          }
  
          auto_ptr<ModSetState> mss = prepare( newObj, true /* this is an insertion */ );
          newObj = mss->createNewFromMods();
  
          return newObj;
      }
  
      /* get special operations like $inc
         { $inc: { a:1, b:1 } }
         { $set: { a:77 } }
         { $push: { a:55 } }
         { $pushAll: { a:[77,88] } }
         { $pull: { a:66 } }
         { $pullAll : { a:[99,1010] } }
         NOTE: MODIFIES source from object!
      */
      ModSet::ModSet(
          const BSONObj& from ,
          const IndexPathSet& idxKeys)
          : _isIndexed(0) , _hasDynamicArray( false ) {
  
          BSONObjIterator it(from);
  
          while ( it.more() ) {
              BSONElement e = it.next();
              const char* fn = e.fieldName();
  
              uassert( 10147 ,  "Invalid modifier specified: " + string( fn ), e.type() == Object );
              BSONObj j = e.embeddedObject();
              DEBUGUPDATE( "\t" << j );
  
              BSONObjIterator jt(j);
              Mod::Op op = opFromStr( fn );
  
              while ( jt.more() ) {
                  BSONElement f = jt.next(); // x:44
  
                  const char* fieldName = f.fieldName();
  
                  // Allow remove of invalid field name in case it was inserted before this check
                  // was added (~ version 2.1).
                  uassert( 15896,
                           "Modified field name may not start with $",
                           fieldName[0] != '$' || op == Mod::UNSET );
                  uassert( 10148,
                           "Mod on _id not allowed",
                           strcmp( fieldName, "_id" ) != 0 );
                  uassert( 10149,
                           "Invalid mod field name, may not end in a period",
                           fieldName[ strlen( fieldName ) - 1 ] != '.' );
                  uassert( 10150,
                           "Field name duplication not allowed with modifiers",
                           ! haveModForField( fieldName ) );
                  uassert( 10151,
                           "have conflicting mods in update",
                           ! haveConflictingMod( fieldName ) );
                  uassert( 10152,
                           "Modifier $inc allowed for numbers only",
                           f.isNumber() || op != Mod::INC );
                  uassert( 10153,
                           "Modifier $pushAll/pullAll allowed for arrays only",
                           f.type() == Array || ( op != Mod::PUSH_ALL && op != Mod::PULL_ALL ) );
  
                  // Check whether $each, $slice, and $sort syntax for $push is correct.
                  if ( ( op == Mod::PUSH ) && ( f.type() == Object ) ) {
                      BSONObj pushObj = f.embeddedObject();
                      if ( pushObj.nFields() > 0 &&
                           strcmp(pushObj.firstElement().fieldName(), "$each") == 0 ) {
                          uassert( 16564,
                                   "$each term needs to occur alone (or with $slice/$sort)",
                                   pushObj.nFields() <= 3 );
                          uassert( 16565,
                                   "$each requires an array value",
                                   pushObj.firstElement().type() == Array );
  
                          // If both $slice and $sort are present, they may be switched.
                          if ( pushObj.nFields() > 1 ) {
                              BSONObjIterator i( pushObj );
                              i.next();
  
                              bool seenSlice = false;
                              bool seenSort = false;
                              while ( i.more() ) {
                                  BSONElement nextElem = i.next();
  
                                  if ( str::equals( nextElem.fieldName(), "$slice" ) ) {
                                      uassert( 16567, "$slice appeared twice", !seenSlice);
                                      seenSlice = true;
                                      uassert( 16568,
                                               "$slice value must be a numeric integer",
                                               nextElem.type() == NumberInt ||
                                               nextElem.type() == NumberLong ||
                                               (nextElem.type() == NumberDouble &&
                                                nextElem.numberDouble() ==
                                                (long long)nextElem.numberDouble() ) );
                                      uassert( 16640,
                                               "$slice value must be negative or zero",
                                               nextElem.number() <= 0 );
                                  }
                                  else if ( str::equals( nextElem.fieldName(), "$sort" ) ) {
                                      uassert( 16647, "$sort appeared twice", !seenSort );
                                      seenSort = true;
                                      uassert( 16648,
                                               "$sort component of $push must be an object",
                                               nextElem.type() == Object );
  
                                      BSONObjIterator j( nextElem.embeddedObject() );
                                      while ( j.more() ) {
                                          BSONElement fieldSortElem = j.next();
                                          uassert( 16641,
                                                   "$sort elements' values  must either 1 or -1",
                                                   ( fieldSortElem.type() == NumberInt ||
                                                     fieldSortElem.type() == NumberLong ||
                                                     ( fieldSortElem.type() == NumberDouble &&
                                                       fieldSortElem.numberDouble() ==
                                                       (long long) fieldSortElem.numberDouble() ) ) &&
                                                   ( fieldSortElem.Number() == 1 ||
                                                     fieldSortElem.Number() == -1 ) );
  
                                          FieldRef sortField;
                                          sortField.parse( fieldSortElem.fieldName() );
                                          uassert( 16690,
                                                   "$sort field cannot be empty",
                                                   sortField.numParts() > 0 );
  
                                          for ( size_t i = 0; i < sortField.numParts(); i++ ) {
                                              uassert( 16691,
                                                       "empty field in dotted sort pattern",
                                                       sortField.getPart( i ).size() > 0 );
                                          }
                                      }
  
                                      // Finally, check if the $each is made of objects (as opposed
                                      // to basic types). Currently, $sort only supports operating
                                      // on arrays of objects.
                                      BSONObj eachArray = pushObj.firstElement().embeddedObject();
                                      BSONObjIterator k( eachArray );
                                      while ( k.more() ) {
                                          BSONElement eachItem = k.next();
                                          uassert( 16642,
                                                   "$sort requires $each to be an array of objects",
                                                   eachItem.type() == Object );
                                      }
  
                                  }
                                  else {
                                      uasserted( 16643,
                                                 "$each term takes only $slice (and optionally "
                                                 "$sort) as complements" );
                                  }
                              }
  
                              uassert( 16644, "cannot have a $sort without a $slice", seenSlice );
                          }
                      }
                  }
  
                  if ( op == Mod::RENAME_TO ) {
                      uassert( 13494, "$rename target must be a string", f.type() == String );
                      const char* target = f.valuestr();
                      uassert( 13495,
                               "$rename source must differ from target",
                               strcmp( fieldName, target ) != 0 );
                      uassert( 13496,
                               "invalid mod field name, source may not be empty",
                               fieldName[0] );
                      uassert( 13479,
                               "invalid mod field name, target may not be empty",
                               target[0] );
                      uassert( 13480,
                               "invalid mod field name, source may not begin or end in period",
                               fieldName[0] != '.' && fieldName[ strlen( fieldName ) - 1 ] != '.' );
                      uassert( 13481,
                               "invalid mod field name, target may not begin or end in period",
                               target[0] != '.' && target[ strlen( target ) - 1 ] != '.' );
                      uassert( 13482,
                               "$rename affecting _id not allowed",
                               !( fieldName[0] == '_' && fieldName[1] == 'i' && fieldName[2] == 'd'
                                  && ( !fieldName[3] || fieldName[3] == '.' ) ) );
                      uassert( 13483,
                               "$rename affecting _id not allowed",
                               !( target[0] == '_' && target[1] == 'i' && target[2] == 'd'
                                  && ( !target[3] || target[3] == '.' ) ) );
                      uassert( 13484,
                               "field name duplication not allowed with $rename target",
                               !haveModForField( target ) );
                      uassert( 13485,
                               "conflicting mods not allowed with $rename target",
                               !haveConflictingMod( target ) );
                      uassert( 13486,
                               "$rename target may not be a parent of source",
                               !( strncmp( fieldName, target, strlen( target ) ) == 0
                                  && fieldName[ strlen( target ) ] == '.' ) );
                      uassert( 13487,
                               "$rename source may not be dynamic array",
                               strstr( fieldName , ".$" ) == 0 );
                      uassert( 13488,
                               "$rename target may not be dynamic array",
                               strstr( target , ".$" ) == 0 );
  
                      Mod from;
                      from.init( Mod::RENAME_FROM, f );
                      from.setFieldName( fieldName );
                      updateIsIndexed( from, idxKeys );
                      _mods[ from.fieldName ] = from;
  
                      Mod to;
                      to.init( Mod::RENAME_TO, f );
                      to.setFieldName( target );
                      updateIsIndexed( to, idxKeys );
                      _mods[ to.fieldName ] = to;
  
                      DEBUGUPDATE( "\t\t " << fieldName << "\t" << from.fieldName << "\t" << to.fieldName );
                      continue;
                  }
  
                  _hasDynamicArray = _hasDynamicArray || strstr( fieldName , ".$" ) > 0;
  
                  Mod m;
                  m.init( op , f );
                  m.setFieldName( f.fieldName() );
                  updateIsIndexed( m, idxKeys );
                  _mods[m.fieldName] = m;
  
                  DEBUGUPDATE( "\t\t " << fieldName << "\t" << m.fieldName << "\t" << _hasDynamicArray );
              }
          }
  
      }
  
      ModSet* ModSet::fixDynamicArray( const string& elemMatchKey ) const {
          ModSet* n = new ModSet();
          n->_isIndexed = _isIndexed;
          n->_hasDynamicArray = _hasDynamicArray;
          for ( ModHolder::const_iterator i=_mods.begin(); i!=_mods.end(); i++ ) {
              string s = i->first;
              size_t idx = s.find( ".$" );
              if ( idx == string::npos ) {
                  n->_mods[s] = i->second;
                  continue;
              }
              StringBuilder buf;
              buf << s.substr(0,idx+1) << elemMatchKey << s.substr(idx+2);
              string fixed = buf.str();
              DEBUGUPDATE( "fixed dynamic: " << s << " -->> " << fixed );
              n->_mods[fixed] = i->second;
              ModHolder::iterator temp = n->_mods.find( fixed );
              temp->second.setFieldName( temp->first.c_str() );
          }
          return n;
      }
  
      void ModSet::updateIsIndexed( const IndexPathSet& idxKeys ) {
          for ( ModHolder::const_iterator i = _mods.begin(); i != _mods.end(); ++i )
              updateIsIndexed( i->second, idxKeys );
      }
  
  } // namespace mongo
  