src/bson/bson.c

   1 /* bson.c */
   2
   3 /*    Copyright 2009, 2010 10gen Inc.
   4  *    Copyright (C) 2012-2015 Softmotions Ltd <info@softmotions.com>
   5  *
   6  *    Licensed under the Apache License, Version 2.0 (the "License");
   7  *    you may not use this file except in compliance with the License.
   8  *    You may obtain a copy of the License at
   9  *
  10  *    http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  *    Unless required by applicable law or agreed to in writing, software
  13  *    distributed under the License is distributed on an "AS IS" BASIS,
  14  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  *    See the License for the specific language governing permissions and
  16  *    limitations under the License.
  17  */
  18
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <stdio.h>
  22 #include <time.h>
  23 #include <limits.h>
  24 #include <assert.h>
  25
  26 #include "bson.h"
  27 #include "encoding.h"
  28 #include "myconf.h"
  29 #include "tcutil.h"
  30
  31 #ifdef _MYBIGEND
  32 #define bson_little_endian64(out, in) ( bson_swap_endian64(out, in) )
  33 #define bson_little_endian32(out, in) ( bson_swap_endian32(out, in) )
  34 #define bson_big_endian64(out, in) ( memcpy(out, in, 8) )
  35 #define bson_big_endian32(out, in) ( memcpy(out, in, 4) )
  36 #else
  37 #define bson_little_endian64(out, in) ( memcpy(out, in, 8) )
  38 #define bson_little_endian32(out, in) ( memcpy(out, in, 4) )
  39 #define bson_big_endian64(out, in) ( bson_swap_endian64(out, in) )
  40 #define bson_big_endian32(out, in) ( bson_swap_endian32(out, in) )
  41 #endif
  42
  43 const int initialBufferSize = 128;
  44
  45 #ifndef MIN
  46 #define        MIN(a,b) (((a)<(b))?(a):(b))
  47 #endif
  48 #ifndef MAX
  49 #define        MAX(a,b) (((a)>(b))?(a):(b))
  50 #endif
  51
  52 /* only need one of these */
  53 static const int zero = 0;
  54
  55 extern void *(*bson_malloc_func)(size_t);
  56 extern void *(*bson_realloc_func)(void *, size_t);
  57 extern void ( *bson_free_func)(void *);
  58 extern bson_printf_func bson_errprintf;
  59
  60 /* Custom standard function pointers. */
  61 void *(*bson_malloc_func)(size_t) = MYMALLOC;
  62 void *(*bson_realloc_func)(void *, size_t) = MYREALLOC;
  63 void ( *bson_free_func)(void *) = MYFREE;
  64
  65 static int _bson_errprintf(const char *, ...);
  66 bson_printf_func bson_errprintf = _bson_errprintf;
  67
  68 /* ObjectId fuzz functions. */
  69 static int ( *oid_fuzz_func)(void) = NULL;
  70 static int ( *oid_inc_func)(void) = NULL;
  71
  72 const char* bson_first_errormsg(bson *b) {
  73     if (b->errstr) {
  74         return b->errstr;
  75     }
  76     if (b->err & BSON_FIELD_HAS_DOT) {
  77         return "BSON key contains '.' character";
  78     } else if (b->err & BSON_FIELD_INIT_DOLLAR) {
  79         return "BSON key starts with '$' character";
  80     } else if (b->err & BSON_ALREADY_FINISHED) {
  81         return "Trying to modify a finished BSON object";
  82     } else if (b->err & BSON_NOT_UTF8) {
  83         return "A key or a string is not valid UTF-8";
  84     } else if (b->err & BSON_NOT_FINISHED) {
  85         return "BSON not finished";
  86     }
  87     return "Unspecified BSON error";
  88 }
  89
  90 void bson_reset(bson *b) {
  91     b->finished = 0;
  92     b->stackPos = 0;
  93     b->err = 0;
  94     b->errstr = NULL;
  95     b->flags = 0;
  96 }
  97
  98 static bson_bool_t bson_isnumstr(const char *str, int len);
  99 static void bson_append_fpath_from_iterator(const char *fpath, const bson_iterator *from, bson *into);
 100 static const char *bson_iterator_value2(const bson_iterator *i, int *klen);
 101
 102 /* ----------------------------
 103    READING
 104    ------------------------------ */
 105
 106 bson* bson_create(void) {
 107     return (bson*) bson_malloc(sizeof (bson));
 108 }
 109
 110 void bson_dispose(bson* b) {
 111     bson_free(b);
 112 }
 113
 114 bson *bson_empty(bson *obj) {
 115     static char *data = "\005\0\0\0\0";
 116     bson_init_data(obj, data);
 117     obj->finished = 1;
 118     obj->err = 0;
 119     obj->errstr = NULL;
 120     obj->stackPos = 0;
 121     obj->flags = 0;
 122     return obj;
 123 }
 124
 125 int bson_copy(bson *out, const bson *in) {
 126     if (!out || !in) return BSON_ERROR;
 127     if (!in->finished) return BSON_ERROR;
 128     bson_init_size(out, bson_size(in));
 129     memcpy(out->data, in->data, bson_size(in));
 130     out->finished = 1;
 131     return BSON_OK;
 132 }
 133
 134 int bson_init_data(bson *b, char *data) {
 135     b->data = data;
 136     return BSON_OK;
 137 }
 138
 139 int bson_init_finished_data(bson *b, const char *data) {
 140     bson_init_data(b, (char*) data);
 141     bson_reset(b);
 142     b->finished = 1;
 143     return BSON_OK;
 144 }
 145
 146 int bson_size(const bson *b) {
 147     int i;
 148     if (!b || !b->data)
 149         return 0;
 150     bson_little_endian32(&i, b->data);
 151     return i;
 152 }
 153
 154 int bson_size2(const void *bsdata) {
 155     int i;
 156     if (!bsdata)
 157         return 0;
 158     bson_little_endian32(&i, bsdata);
 159     return i;
 160 }
 161
 162 int bson_buffer_size(const bson *b) {
 163     return (b->cur - b->data + 1);
 164 }
 165
 166 const char *bson_data(const bson *b) {
 167     return (const char *) b->data;
 168 }
 169
 170 const char* bson_data2(const bson *b, int *bsize) {
 171     *bsize = bson_size(b);
 172     return b->data;
 173 }
 174
 175 EJDB_INLINE char hexbyte(char hex) {
 176     if (hex >= '0' && hex <= '9')
 177         return (hex - '0');
 178     else if (hex >= 'A' && hex <= 'F')
 179         return (hex - 'A' + 10);
 180     else if (hex >= 'a' && hex <= 'f')
 181         return (hex - 'a' + 10);
 182     else
 183         return 0x0;
 184 }
 185
 186 void bson_oid_from_string(bson_oid_t *oid, const char *str) {
 187     int i;
 188     for (i = 0; i < 12; i++) {
 189         oid->bytes[i] = (hexbyte(str[2 * i]) << 4) | hexbyte(str[2 * i + 1]);
 190     }
 191 }
 192
 193 void bson_oid_to_string(const bson_oid_t *oid, char *str) {
 194     static const char hex[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
 195     int i;
 196     for (i = 0; i < 12; i++) {
 197         str[2 * i] = hex[(oid->bytes[i] & 0xf0) >> 4];
 198         str[2 * i + 1] = hex[ oid->bytes[i] & 0x0f ];
 199     }
 200     str[24] = '\0';
 201 }
 202
 203 void bson_set_oid_fuzz(int ( *func)(void)) {
 204     oid_fuzz_func = func;
 205 }
 206
 207 void bson_set_oid_inc(int ( *func)(void)) {
 208     oid_inc_func = func;
 209 }
 210
 211 void bson_oid_gen(bson_oid_t *oid) {
 212     static int incr = 0;
 213     static int fuzz = 0;
 214     int i;
 215     int t = time(NULL);
 216
 217     if (oid_inc_func)
 218         i = oid_inc_func();
 219     else
 220         i = incr++;
 221
 222     if (!fuzz) {
 223         if (oid_fuzz_func)
 224             fuzz = oid_fuzz_func();
 225         else {
 226             srand(t);
 227             fuzz = rand();
 228         }
 229     }
 230
 231     bson_big_endian32(&oid->ints[0], &t);
 232     oid->ints[1] = fuzz;
 233     bson_big_endian32(&oid->ints[2], &i);
 234 }
 235
 236 time_t bson_oid_generated_time(bson_oid_t *oid) {
 237     time_t out = 0;
 238     bson_big_endian32(&out, &oid->ints[0]);
 239     return out;
 240 }
 241
 242 void bson_print_raw(const char *data, int depth) {
 243     FILE *f = stdout;
 244     bson_iterator i;
 245     const char *key;
 246     int temp;
 247     bson_timestamp_t ts;
 248     char oidhex[25];
 249     bson scope;
 250     BSON_ITERATOR_FROM_BUFFER(&i, data);
 251
 252     while (bson_iterator_next(&i)) {
 253         bson_type t = BSON_ITERATOR_TYPE(&i);
 254         if (t == 0)
 255             break;
 256         key = BSON_ITERATOR_KEY(&i);
 257
 258         for (temp = 0; temp <= depth; temp++)
 259             fprintf(f, "\t");
 260         fprintf(f, "%s : %d \t ", key, t);
 261         switch (t) {
 262             case BSON_DOUBLE:
 263                 fprintf(f, "%f", bson_iterator_double(&i));
 264                 break;
 265             case BSON_STRING:
 266                 fprintf(f, "%s", bson_iterator_string(&i));
 267                 break;
 268             case BSON_SYMBOL:
 269                 fprintf(f, "SYMBOL: %s", bson_iterator_string(&i));
 270                 break;
 271             case BSON_OID:
 272                 bson_oid_to_string(bson_iterator_oid(&i), oidhex);
 273                 fprintf(f, "%s", oidhex);
 274                 break;
 275             case BSON_BOOL:
 276                 fprintf(f, "%s", bson_iterator_bool(&i) ? "true" : "false");
 277                 break;
 278             case BSON_DATE:
 279                 fprintf(f, "%" PRId64, bson_iterator_date(&i));
 280                 break;
 281             case BSON_BINDATA:
 282                 fprintf(f, "BSON_BINDATA");
 283                 break;
 284             case BSON_UNDEFINED:
 285                 fprintf(f, "BSON_UNDEFINED");
 286                 break;
 287             case BSON_NULL:
 288                 fprintf(f, "BSON_NULL");
 289                 break;
 290             case BSON_REGEX:
 291                 fprintf(f, "BSON_REGEX: %s", bson_iterator_regex(&i));
 292                 break;
 293             case BSON_CODE:
 294                 fprintf(f, "BSON_CODE: %s", bson_iterator_code(&i));
 295                 break;
 296             case BSON_CODEWSCOPE:
 297                 fprintf(f, "BSON_CODE_W_SCOPE: %s", bson_iterator_code(&i));
 298                 /* bson_init( &scope ); */ /* review - stepped on by bson_iterator_code_scope? */
 299                 bson_iterator_code_scope(&i, &scope);
 300                 fprintf(f, "\n\t SCOPE: ");
 301                 bson_print_raw((const char*) &scope, 0);
 302                 /* bson_destroy( &scope ); */ /* review - causes free error */
 303                 break;
 304             case BSON_INT:
 305                 fprintf(f, "%d", bson_iterator_int(&i));
 306                 break;
 307             case BSON_LONG:
 308                 fprintf(f, "%" PRId64 "", (uint64_t) bson_iterator_long(&i));
 309                 break;
 310             case BSON_TIMESTAMP:
 311                 ts = bson_iterator_timestamp(&i);
 312                 fprintf(f, "i: %d, t: %d", ts.i, ts.t);
 313                 break;
 314             case BSON_OBJECT:
 315             case BSON_ARRAY:
 316                 fprintf(f, "\n");
 317                 bson_print_raw(bson_iterator_value(&i), depth + 1);
 318                 break;
 319             default:
 320                 bson_errprintf("can't print type : %d\n", t);
 321         }
 322         fprintf(f, "\n");
 323     }
 324 }
 325
 326 /* ----------------------------
 327    ITERATOR
 328    ------------------------------ */
 329
 330 bson_iterator* bson_iterator_create(void) {
 331     return (bson_iterator*) malloc(sizeof ( bson_iterator));
 332 }
 333
 334 void bson_iterator_dispose(bson_iterator* i) {
 335     free(i);
 336 }
 337
 338 void bson_iterator_init(bson_iterator *i, const bson *b) {
 339     i->cur = b->data + 4;
 340     i->first = 1;
 341 }
 342
 343 void bson_iterator_from_buffer(bson_iterator *i, const char *buffer) {
 344     i->cur = buffer + 4;
 345     i->first = 1;
 346 }
 347
 348 bson_type bson_find(bson_iterator *it, const bson *obj, const char *name) {
 349     BSON_ITERATOR_INIT(it, (bson *) obj);
 350     while (bson_iterator_next(it)) {
 351         if (strcmp(name, BSON_ITERATOR_KEY(it)) == 0)
 352             break;
 353     }
 354     return BSON_ITERATOR_TYPE(it);
 355 }
 356
 357 bson_type bson_find_from_buffer(bson_iterator *it, const char *buffer, const char *name) {
 358     BSON_ITERATOR_FROM_BUFFER(it, buffer);
 359     while (bson_iterator_next(it)) {
 360         if (strcmp(name, BSON_ITERATOR_KEY(it)) == 0)
 361             break;
 362     }
 363     return BSON_ITERATOR_TYPE(it);
 364 }
 365
 366 static void bson_visit_fields_impl(bson_traverse_flags_t flags, char* pstack, int curr, bson_iterator *it, BSONVISITOR visitor, void *op) {
 367     int klen = 0;
 368     bson_type t;
 369     bson_visitor_cmd_t vcmd = 0;
 370     while (!(vcmd & BSON_VCMD_TERMINATE) && (t = bson_iterator_next(it)) != BSON_EOO) {
 371         const char* key = BSON_ITERATOR_KEY(it);
 372         klen = strlen(key);
 373         if (curr + klen > BSON_MAX_FPATH_LEN) {
 374             continue;
 375         }
 376         //PUSH
 377         if (curr > 0) { //add leading dot
 378             *(pstack + curr) = '.';
 379             curr++;
 380         }
 381         memcpy(pstack + curr, key, klen);
 382         curr += klen;
 383         //Call visitor
 384         vcmd = visitor(pstack, curr, key, klen, it, false, op);
 385         if (vcmd & BSON_VCMD_TERMINATE) {
 386             break;
 387         }
 388         if (!(vcmd & BSON_VCMD_SKIP_NESTED) &&
 389                 ((t == BSON_OBJECT && (flags & BSON_TRAVERSE_OBJECTS_EXCLUDED) == 0) ||
 390                 (t == BSON_ARRAY && (flags & BSON_TRAVERSE_ARRAYS_EXCLUDED) == 0))
 391                 ) {
 392             bson_iterator sit;
 393             BSON_ITERATOR_SUBITERATOR(it, &sit);
 394             bson_visit_fields_impl(flags, pstack, curr, &sit, visitor, op);
 395         }
 396         if (!(vcmd & BSON_VCMD_SKIP_AFTER)) {
 397             vcmd = visitor(pstack, curr, key, klen, it, true, op);
 398         }
 399         //POP
 400         curr -= klen;
 401         if (curr > 0) {
 402             curr--; //remove leading dot
 403         }
 404     }
 405 }
 406
 407 void bson_visit_fields(bson_iterator *it, bson_traverse_flags_t flags, BSONVISITOR visitor, void *op) {
 408     char pstack[BSON_MAX_FPATH_LEN + 1];
 409     bson_visit_fields_impl(flags, pstack, 0, it, visitor, op);
 410 }
 411
 412 static bson_type bson_find_fieldpath_value_impl(char* pstack, int curr, FFPCTX *ffpctx, bson_iterator *it) {
 413     int i;
 414     bson_type t;
 415     int klen = 0;
 416     int fplen = ffpctx->fplen;
 417     const char *fpath = ffpctx->fpath;
 418     while ((t = bson_iterator_next(it)) != BSON_EOO) {
 419         const char* key = BSON_ITERATOR_KEY(it);
 420         klen = strlen(key);
 421         if (curr + klen > fplen) {
 422             continue;
 423         }
 424         //PUSH
 425         if (curr > 0) { //add leading dot
 426             *(pstack + curr) = '.';
 427             curr++;
 428         }
 429         memcpy(pstack + curr, key, klen);
 430         curr += klen;
 431         for (i = 0; i < curr && i < fplen && pstack[i] == fpath[i]; ++i);
 432         if (i == curr && i == fplen) { //Position matched with field path
 433             ffpctx->stopos = i;
 434             return t;
 435         }
 436         if (i == curr && i < fplen && (t == BSON_OBJECT || t == BSON_ARRAY)) { //Only prefix and we can go into nested objects
 437             if (ffpctx->stopnestedarr && t == BSON_ARRAY) {
 438                 int p1 = curr;
 439                 while (fpath[p1] == '.' && p1 < fplen) p1++;
 440                 int p2 = p1;
 441                 while (fpath[p2] != '.' && fpath[p2] > '\0' && p2 < fplen) p2++;
 442                 if (!bson_isnumstr(fpath + p1, p2 - p1)) { //next fpath sections is not an array index
 443                     ffpctx->stopos = i;
 444                     return t;
 445                 }
 446             }
 447             bson_iterator sit;
 448             BSON_ITERATOR_SUBITERATOR(it, &sit);
 449             bson_type st = bson_find_fieldpath_value_impl(pstack, curr, ffpctx, &sit);
 450             if (st != BSON_EOO) { //Found in nested
 451                 *it = sit;
 452                 return st;
 453             }
 454         }
 455         //POP
 456         curr -= klen;
 457         if (curr > 0) {
 458             curr--; //remove leading dot
 459         }
 460     }
 461     return BSON_EOO;
 462 }
 463
 464 bson_type bson_find_fieldpath_value(const char *fpath, bson_iterator *it) {
 465     return bson_find_fieldpath_value2(fpath, strlen(fpath), it);
 466 }
 467
 468 bson_type bson_find_fieldpath_value2(const char *fpath, int fplen, bson_iterator *it) {
 469     FFPCTX ffctx = {
 470         .fpath = fpath,
 471         .fplen = fplen,
 472         .input = it,
 473         .stopnestedarr = false,
 474         .stopos = 0,
 475         .mpos = -1,
 476         .dpos = -1
 477     };
 478     return bson_find_fieldpath_value3(&ffctx);
 479 }
 480
 481 bson_type bson_find_fieldpath_value3(FFPCTX* ffctx) {
 482     char pstackstack[BSON_MAX_FPATH_LEN + 1];
 483     char *pstack;
 484     if (ffctx->fplen <= BSON_MAX_FPATH_LEN) {
 485         pstack = pstackstack;
 486     } else {
 487         pstack = MYMALLOC((ffctx->fplen + 1) * sizeof (char));
 488         if (!pstack) {
 489             return BSON_EOO;
 490         }
 491     }
 492     bson_type bt = bson_find_fieldpath_value_impl(pstack, 0, ffctx, ffctx->input);
 493     if (pstack != pstackstack) {
 494         MYFREE(pstack);
 495     }
 496     return bt;
 497 }
 498
 499 bson_bool_t bson_iterator_more(const bson_iterator *i) {
 500     return *(i->cur);
 501 }
 502
 503 bson_type bson_iterator_next(bson_iterator *i) {
 504     int ds, out, klen = 0;
 505     if (i->first) {
 506         i->first = 0;
 507         return (bson_type) (*i->cur);
 508     }
 509     switch (BSON_ITERATOR_TYPE(i)) {
 510         case BSON_EOO:
 511             return BSON_EOO; /* don't advance */
 512         case BSON_UNDEFINED:
 513         case BSON_NULL:
 514             ds = 0;
 515             break;
 516         case BSON_BOOL:
 517             ds = 1;
 518             break;
 519         case BSON_INT:
 520             ds = 4;
 521             break;
 522         case BSON_LONG:
 523         case BSON_DOUBLE:
 524         case BSON_TIMESTAMP:
 525         case BSON_DATE:
 526             ds = 8;
 527             break;
 528         case BSON_OID:
 529             ds = 12;
 530             break;
 531         case BSON_STRING:
 532         case BSON_SYMBOL:
 533         case BSON_CODE:
 534             bson_little_endian32(&out, bson_iterator_value2(i, &klen));
 535             ds = 4 + out;
 536             break;
 537         case BSON_BINDATA:
 538             bson_little_endian32(&out, bson_iterator_value2(i, &klen));
 539             ds = 5 + out;
 540             break;
 541         case BSON_OBJECT:
 542         case BSON_ARRAY:
 543         case BSON_CODEWSCOPE:
 544             bson_little_endian32(&out, bson_iterator_value2(i, &klen));
 545             ds = out;
 546             break;
 547         case BSON_DBREF:
 548             bson_little_endian32(&out, bson_iterator_value2(i, &klen));
 549             ds = 4 + 12 + out;
 550             break;
 551         case BSON_REGEX:
 552         {
 553             const char *s = bson_iterator_value2(i, &klen);
 554             const char *p = s;
 555             p += strlen(p) + 1;
 556             p += strlen(p) + 1;
 557             ds = p - s;
 558             break;
 559         }
 560
 561         default:
 562         {
 563             char msg[] = "unknown type: 000000000000";
 564             bson_numstr(msg + 14, (unsigned) (i->cur[0]));
 565             bson_fatal_msg(0, msg);
 566             return 0;
 567         }
 568     }
 569     if (klen == 0) {
 570         for (; *(i->cur + 1 + klen) != '\0'; ++klen);
 571     }
 572     i->cur += (1 + klen + 1 + ds);
 573     return (bson_type) (*i->cur);
 574 }
 575
 576 bson_type bson_iterator_type(const bson_iterator *i) {
 577     return (bson_type) i->cur[0];
 578 }
 579
 580 const char *bson_iterator_key(const bson_iterator *i) {
 581     return i->cur + 1;
 582 }
 583
 584 const char *bson_iterator_value(const bson_iterator *i) {
 585     int len = 0;
 586     const char *t = i->cur + 1;
 587     for (; *(t + len) != '\0'; ++len);
 588     t += len + 1;
 589     return t;
 590 }
 591
 592 /* types */
 593
 594 int bson_iterator_int_raw(const bson_iterator *i) {
 595     int out;
 596     bson_little_endian32(&out, bson_iterator_value(i));
 597     return out;
 598 }
 599
 600 double bson_iterator_double_raw(const bson_iterator *i) {
 601     double out;
 602     bson_little_endian64(&out, bson_iterator_value(i));
 603     return out;
 604 }
 605
 606 int64_t bson_iterator_long_raw(const bson_iterator *i) {
 607     int64_t out;
 608     bson_little_endian64(&out, bson_iterator_value(i));
 609     return out;
 610 }
 611
 612 bson_bool_t bson_iterator_bool_raw(const bson_iterator *i) {
 613     return bson_iterator_value(i)[0];
 614 }
 615
 616 bson_oid_t *bson_iterator_oid(const bson_iterator *i) {
 617     return (bson_oid_t *) bson_iterator_value(i);
 618 }
 619
 620 int bson_iterator_int(const bson_iterator *i) {
 621     switch (BSON_ITERATOR_TYPE(i)) {
 622         case BSON_INT:
 623             return bson_iterator_int_raw(i);
 624         case BSON_LONG:
 625             return bson_iterator_long_raw(i);
 626         case BSON_DOUBLE:
 627             return bson_iterator_double_raw(i);
 628         case BSON_BOOL:
 629             return bson_iterator_bool_raw(i) ? 1 : 0;
 630         default:
 631             return 0;
 632     }
 633 }
 634
 635 double bson_iterator_double(const bson_iterator *i) {
 636     switch (BSON_ITERATOR_TYPE(i)) {
 637         case BSON_INT:
 638             return bson_iterator_int_raw(i);
 639         case BSON_LONG:
 640         case BSON_DATE:
 641             return bson_iterator_long_raw(i);
 642         case BSON_DOUBLE:
 643             return bson_iterator_double_raw(i);
 644         case BSON_BOOL:
 645             return bson_iterator_bool_raw(i) ? 1.0 : 0.0;
 646         default:
 647             return 0;
 648     }
 649 }
 650
 651 int64_t bson_iterator_long(const bson_iterator *i) {
 652     switch (BSON_ITERATOR_TYPE(i)) {
 653         case BSON_INT:
 654             return bson_iterator_int_raw(i);
 655         case BSON_LONG:
 656         case BSON_DATE:
 657             return bson_iterator_long_raw(i);
 658         case BSON_DOUBLE:
 659             return bson_iterator_double_raw(i);
 660         case BSON_BOOL:
 661             return bson_iterator_bool_raw(i) ? 1 : 0;
 662         default:
 663             return 0;
 664     }
 665 }
 666
 667 static int64_t bson_iterator_long_ext(const bson_iterator *i) {
 668     switch (BSON_ITERATOR_TYPE(i)) {
 669         case BSON_INT:
 670             return bson_iterator_int_raw(i);
 671         case BSON_LONG:
 672         case BSON_DATE:
 673         case BSON_TIMESTAMP:
 674             return bson_iterator_long_raw(i);
 675         case BSON_DOUBLE:
 676             return bson_iterator_double_raw(i);
 677         case BSON_BOOL:
 678             return bson_iterator_bool_raw(i) ? 1 : 0;
 679         default:
 680             return 0;
 681     }
 682 }
 683
 684 bson_timestamp_t bson_iterator_timestamp(const bson_iterator *i) {
 685     bson_timestamp_t ts;
 686     bson_little_endian32(&(ts.i), bson_iterator_value(i));
 687     bson_little_endian32(&(ts.t), bson_iterator_value(i) + 4);
 688     return ts;
 689 }
 690
 691 int bson_iterator_timestamp_time(const bson_iterator *i) {
 692     int time;
 693     bson_little_endian32(&time, bson_iterator_value(i) + 4);
 694     return time;
 695 }
 696
 697 int bson_iterator_timestamp_increment(const bson_iterator *i) {
 698     int increment;
 699     bson_little_endian32(&increment, bson_iterator_value(i));
 700     return increment;
 701 }
 702
 703 bson_bool_t bson_iterator_bool(const bson_iterator *i) {
 704     switch (BSON_ITERATOR_TYPE(i)) {
 705         case BSON_BOOL:
 706             return bson_iterator_bool_raw(i);
 707         case BSON_INT:
 708             return bson_iterator_int_raw(i) != 0;
 709         case BSON_LONG:
 710         case BSON_DATE:
 711             return bson_iterator_long_raw(i) != 0;
 712         case BSON_DOUBLE:
 713             return bson_iterator_double_raw(i) != 0;
 714         case BSON_EOO:
 715         case BSON_NULL:
 716         case BSON_UNDEFINED:
 717             return 0;
 718         default:
 719             return 1;
 720     }
 721 }
 722
 723 const char *bson_iterator_string(const bson_iterator *i) {
 724     switch (BSON_ITERATOR_TYPE(i)) {
 725         case BSON_STRING:
 726         case BSON_SYMBOL:
 727             return bson_iterator_value(i) + 4;
 728         default:
 729             return "";
 730     }
 731 }
 732
 733 int bson_iterator_string_len(const bson_iterator *i) {
 734     return bson_iterator_int_raw(i);
 735 }
 736
 737 const char *bson_iterator_code(const bson_iterator *i) {
 738     switch (BSON_ITERATOR_TYPE(i)) {
 739         case BSON_STRING:
 740         case BSON_CODE:
 741             return bson_iterator_value(i) + 4;
 742         case BSON_CODEWSCOPE:
 743             return bson_iterator_value(i) + 8;
 744         default:
 745             return NULL;
 746     }
 747 }
 748
 749 void bson_iterator_code_scope(const bson_iterator *i, bson *scope) {
 750     if (BSON_ITERATOR_TYPE(i) == BSON_CODEWSCOPE) {
 751         int code_len;
 752         bson_little_endian32(&code_len, bson_iterator_value(i) + 4);
 753         bson_init_data(scope, (void *) (bson_iterator_value(i) + 8 + code_len));
 754         bson_reset(scope);
 755         scope->finished = 1;
 756     } else {
 757         bson_empty(scope);
 758     }
 759 }
 760
 761 bson_date_t bson_iterator_date(const bson_iterator *i) {
 762     return bson_iterator_long_raw(i);
 763 }
 764
 765 time_t bson_iterator_time_t(const bson_iterator *i) {
 766     return bson_iterator_date(i) / 1000;
 767 }
 768
 769 int bson_iterator_bin_len(const bson_iterator *i) {
 770     return ( bson_iterator_bin_type(i) == BSON_BIN_BINARY_OLD)
 771             ? bson_iterator_int_raw(i) - 4
 772             : bson_iterator_int_raw(i);
 773 }
 774
 775 char bson_iterator_bin_type(const bson_iterator *i) {
 776     return bson_iterator_value(i)[4];
 777 }
 778
 779 const char *bson_iterator_bin_data(const bson_iterator *i) {
 780     return ( bson_iterator_bin_type(i) == BSON_BIN_BINARY_OLD)
 781             ? bson_iterator_value(i) + 9
 782             : bson_iterator_value(i) + 5;
 783 }
 784
 785 const char *bson_iterator_regex(const bson_iterator *i) {
 786     return bson_iterator_value(i);
 787 }
 788
 789 const char *bson_iterator_regex_opts(const bson_iterator *i) {
 790     const char *p = bson_iterator_value(i);
 791     return p + strlen(p) + 1;
 792
 793 }
 794
 795 void bson_iterator_subobject(const bson_iterator *i, bson *sub) {
 796     bson_init_data(sub, (char *) bson_iterator_value(i));
 797     bson_reset(sub);
 798     sub->finished = 1;
 799 }
 800
 801 void bson_iterator_subiterator(const bson_iterator *i, bson_iterator *sub) {
 802     BSON_ITERATOR_FROM_BUFFER(sub, bson_iterator_value(i));
 803 }
 804
 805 /* ----------------------------
 806    BUILDING
 807    ------------------------------ */
 808
 809 static void _bson_init_size(bson *b, int size) {
 810     if (size == 0) {
 811         b->data = NULL;
 812     } else {
 813         b->data = (char *) bson_malloc(size);
 814     }
 815     b->dataSize = size;
 816     b->cur = b->data + 4;
 817     bson_reset(b);
 818 }
 819
 820 void bson_init(bson *b) {
 821     _bson_init_size(b, initialBufferSize);
 822 }
 823
 824 void bson_init_as_query(bson *b) {
 825     bson_init(b);
 826     b->flags |= BSON_FLAG_QUERY_MODE;
 827 }
 828
 829 void bson_init_size(bson *b, int size) {
 830     _bson_init_size(b, size);
 831 }
 832
 833 void bson_init_on_stack(bson *b, char *bstack, int mincapacity, int maxonstack) {
 834     bson_reset(b);
 835     b->data = (mincapacity < maxonstack) ? bstack : bson_malloc_func(mincapacity);
 836     b->cur = b->data + 4;
 837     b->dataSize = (mincapacity < maxonstack) ? maxonstack : mincapacity;
 838     if (b->data == bstack) {
 839         b->flags |= BSON_FLAG_STACK_ALLOCATED;
 840     }
 841 }
 842
 843 void bson_append_byte(bson *b, char c) {
 844     b->cur[0] = c;
 845     b->cur++;
 846 }
 847
 848 void bson_append(bson *b, const void *data, int len) {
 849     memcpy(b->cur, data, len);
 850     b->cur += len;
 851 }
 852
 853 void bson_append32(bson *b, const void *data) {
 854     bson_little_endian32(b->cur, data);
 855     b->cur += 4;
 856 }
 857
 858 void bson_append64(bson *b, const void *data) {
 859     bson_little_endian64(b->cur, data);
 860     b->cur += 8;
 861 }
 862
 863 int bson_ensure_space(bson *b, const int bytesNeeded) {
 864     int pos = b->cur - b->data;
 865     char *orig = b->data;
 866     int new_size;
 867
 868     if (pos + bytesNeeded <= b->dataSize)
 869         return BSON_OK;
 870
 871     new_size = 1.5 * (b->dataSize + bytesNeeded);
 872
 873     if (new_size < b->dataSize) {
 874         if ((b->dataSize + bytesNeeded) < INT_MAX)
 875             new_size = INT_MAX;
 876         else {
 877             b->err = BSON_SIZE_OVERFLOW;
 878             return BSON_ERROR;
 879         }
 880     }
 881
 882     if (b->flags & BSON_FLAG_STACK_ALLOCATED) { //translate stack memory into heap
 883         char *odata = b->data;
 884         b->data = bson_malloc_func(new_size);
 885         if (!b->data) {
 886             bson_fatal_msg(!!b->data, "malloc() failed");
 887             return BSON_ERROR;
 888         }
 889         if (odata) {
 890             memcpy(b->data, odata, MIN(new_size, b->dataSize));
 891         }
 892         b->flags &= ~BSON_FLAG_STACK_ALLOCATED; //reset this flag
 893     } else {
 894         b->data = bson_realloc(b->data, new_size);
 895     }
 896     if (!b->data) {
 897         bson_fatal_msg(!!b->data, "realloc() failed");
 898         return BSON_ERROR;
 899     }
 900
 901     b->dataSize = new_size;
 902     b->cur += b->data - orig;
 903
 904     return BSON_OK;
 905 }
 906
 907 int bson_finish(bson *b) {
 908     int i;
 909     if (b->err & BSON_NOT_UTF8)
 910         return BSON_ERROR;
 911     if (!b->finished) {
 912         if (bson_ensure_space(b, 1) == BSON_ERROR) return BSON_ERROR;
 913         bson_append_byte(b, 0);
 914         i = b->cur - b->data;
 915         bson_little_endian32(b->data, &i);
 916         b->finished = 1;
 917     }
 918     return BSON_OK;
 919 }
 920
 921 void bson_destroy(bson *b) {
 922     if (b) {
 923         if (b->data && !(b->flags & BSON_FLAG_STACK_ALLOCATED)) {
 924             bson_free(b->data);
 925         }
 926         b->err = 0;
 927         b->data = 0;
 928         b->cur = 0;
 929         b->finished = 1;
 930         if (b->errstr) {
 931             bson_free_func(b->errstr);
 932             b->errstr = NULL;
 933         }
 934     }
 935 }
 936
 937 void bson_del(bson *b) {
 938     if (b) {
 939         bson_destroy(b);
 940         bson_free(b);
 941     }
 942 }
 943
 944 static int bson_append_estart2(bson *b, int type, const char *name, int namelen, const int dataSize);
 945
 946 static int bson_append_estart(bson *b, int type, const char *name, const int dataSize) {
 947     return bson_append_estart2(b, type, name, strlen(name), dataSize);
 948 }
 949
 950 static int bson_append_estart2(bson *b, int type, const char *name, int namelen, const int dataSize) {
 951     const int len = namelen + 1;
 952
 953     if (b->finished) {
 954         b->err |= BSON_ALREADY_FINISHED;
 955         return BSON_ERROR;
 956     }
 957
 958     if (bson_ensure_space(b, 1 + len + dataSize) == BSON_ERROR) {
 959         return BSON_ERROR;
 960     }
 961
 962     if (bson_check_field_name(b, (const char *) name, namelen,
 963             !(b->flags & BSON_FLAG_QUERY_MODE), !(b->flags & BSON_FLAG_QUERY_MODE)) == BSON_ERROR) {
 964         bson_builder_error(b);
 965         return BSON_ERROR;
 966     }
 967     bson_append_byte(b, (char) type);
 968     memcpy(b->cur, name, namelen);
 969     b->cur += namelen;
 970     *(b->cur) = '\0';
 971     b->cur += 1;
 972     return BSON_OK;
 973 }
 974
 975 /* ----------------------------
 976    BUILDING TYPES
 977    ------------------------------ */
 978
 979 int bson_append_int(bson *b, const char *name, const int i) {
 980     if (bson_append_estart(b, BSON_INT, name, 4) == BSON_ERROR)
 981         return BSON_ERROR;
 982     bson_append32(b, &i);
 983     return BSON_OK;
 984 }
 985
 986 int bson_append_long(bson *b, const char *name, const int64_t i) {
 987     if (bson_append_estart(b, BSON_LONG, name, 8) == BSON_ERROR)
 988         return BSON_ERROR;
 989     bson_append64(b, &i);
 990     return BSON_OK;
 991 }
 992
 993 int bson_append_double(bson *b, const char *name, const double d) {
 994     if (bson_append_estart(b, BSON_DOUBLE, name, 8) == BSON_ERROR)
 995         return BSON_ERROR;
 996     bson_append64(b, &d);
 997     return BSON_OK;
 998 }
 999
1000 int bson_append_bool(bson *b, const char *name, const bson_bool_t i) {
1001     if (bson_append_estart(b, BSON_BOOL, name, 1) == BSON_ERROR)
1002         return BSON_ERROR;
1003     bson_append_byte(b, i != 0);
1004     return BSON_OK;
1005 }
1006
1007 int bson_append_null(bson *b, const char *name) {
1008     if (bson_append_estart(b, BSON_NULL, name, 0) == BSON_ERROR)
1009         return BSON_ERROR;
1010     return BSON_OK;
1011 }
1012
1013 int bson_append_undefined(bson *b, const char *name) {
1014     if (bson_append_estart(b, BSON_UNDEFINED, name, 0) == BSON_ERROR)
1015         return BSON_ERROR;
1016     return BSON_OK;
1017 }
1018
1019 int bson_append_string_base(bson *b, const char *name,
1020         const char *value, int len, bson_type type) {
1021
1022     int sl = len + 1;
1023     if (bson_check_string(b, (const char *) value, sl - 1) == BSON_ERROR)
1024         return BSON_ERROR;
1025     if (bson_append_estart(b, type, name, 4 + sl) == BSON_ERROR) {
1026         return BSON_ERROR;
1027     }
1028     bson_append32(b, &sl);
1029     bson_append(b, value, sl - 1);
1030     bson_append(b, "\0", 1);
1031     return BSON_OK;
1032 }
1033
1034 int bson_append_string(bson *b, const char *name, const char *value) {
1035     return bson_append_string_base(b, name, value, strlen(value), BSON_STRING);
1036 }
1037
1038 int bson_append_symbol(bson *b, const char *name, const char *value) {
1039     return bson_append_string_base(b, name, value, strlen(value), BSON_SYMBOL);
1040 }
1041
1042 int bson_append_code(bson *b, const char *name, const char *value) {
1043     return bson_append_string_base(b, name, value, strlen(value), BSON_CODE);
1044 }
1045
1046 int bson_append_string_n(bson *b, const char *name, const char *value, int len) {
1047     return bson_append_string_base(b, name, value, len, BSON_STRING);
1048 }
1049
1050 int bson_append_symbol_n(bson *b, const char *name, const char *value, int len) {
1051     return bson_append_string_base(b, name, value, len, BSON_SYMBOL);
1052 }
1053
1054 int bson_append_code_n(bson *b, const char *name, const char *value, int len) {
1055     return bson_append_string_base(b, name, value, len, BSON_CODE);
1056 }
1057
1058 int bson_append_code_w_scope_n(bson *b, const char *name,
1059         const char *code, int len, const bson *scope) {
1060
1061     int sl, size;
1062     if (!scope) return BSON_ERROR;
1063     sl = len + 1;
1064     size = 4 + 4 + sl + bson_size(scope);
1065     if (bson_append_estart(b, BSON_CODEWSCOPE, name, size) == BSON_ERROR)
1066         return BSON_ERROR;
1067     bson_append32(b, &size);
1068     bson_append32(b, &sl);
1069     bson_append(b, code, sl);
1070     bson_append(b, scope->data, bson_size(scope));
1071     return BSON_OK;
1072 }
1073
1074 int bson_append_code_w_scope(bson *b, const char *name, const char *code, const bson *scope) {
1075     return bson_append_code_w_scope_n(b, name, code, strlen(code), scope);
1076 }
1077
1078 int bson_append_binary(bson *b, const char *name, char type, const char *str, int len) {
1079     if (type == BSON_BIN_BINARY_OLD) {
1080         int subtwolen = len + 4;
1081         if (bson_append_estart(b, BSON_BINDATA, name, 4 + 1 + 4 + len) == BSON_ERROR)
1082             return BSON_ERROR;
1083         bson_append32(b, &subtwolen);
1084         bson_append_byte(b, type);
1085         bson_append32(b, &len);
1086         bson_append(b, str, len);
1087     } else {
1088         if (bson_append_estart(b, BSON_BINDATA, name, 4 + 1 + len) == BSON_ERROR)
1089             return BSON_ERROR;
1090         bson_append32(b, &len);
1091         bson_append_byte(b, type);
1092         bson_append(b, str, len);
1093     }
1094     return BSON_OK;
1095 }
1096
1097 int bson_append_oid(bson *b, const char *name, const bson_oid_t *oid) {
1098     if (bson_append_estart(b, BSON_OID, name, 12) == BSON_ERROR)
1099         return BSON_ERROR;
1100     bson_append(b, oid, 12);
1101     return BSON_OK;
1102 }
1103
1104 int bson_append_new_oid(bson *b, const char *name) {
1105     bson_oid_t oid;
1106     bson_oid_gen(&oid);
1107     return bson_append_oid(b, name, &oid);
1108 }
1109
1110 int bson_append_regex(bson *b, const char *name, const char *pattern, const char *opts) {
1111     const int plen = strlen(pattern) + 1;
1112     const int olen = strlen(opts) + 1;
1113     if (bson_append_estart(b, BSON_REGEX, name, plen + olen) == BSON_ERROR)
1114         return BSON_ERROR;
1115     if (bson_check_string(b, pattern, plen - 1) == BSON_ERROR)
1116         return BSON_ERROR;
1117     bson_append(b, pattern, plen);
1118     bson_append(b, opts, olen);
1119     return BSON_OK;
1120 }
1121
1122 int bson_append_bson(bson *b, const char *name, const bson *bson) {
1123     if (!bson) return BSON_ERROR;
1124     if (bson_append_estart(b, BSON_OBJECT, name, bson_size(bson)) == BSON_ERROR)
1125         return BSON_ERROR;
1126     bson_append(b, bson->data, bson_size(bson));
1127     return BSON_OK;
1128 }
1129
1130 int bson_append_element(bson *b, const char *name_or_null, const bson_iterator *elem) {
1131     bson_iterator next = *elem;
1132     int size;
1133
1134     bson_iterator_next(&next);
1135     size = next.cur - elem->cur;
1136
1137     if (name_or_null == NULL) {
1138         if (bson_ensure_space(b, size) == BSON_ERROR)
1139             return BSON_ERROR;
1140         bson_append(b, elem->cur, size);
1141     } else {
1142         int data_size = size - 2 - strlen(BSON_ITERATOR_KEY(elem));
1143         bson_append_estart(b, elem->cur[0], name_or_null, data_size);
1144         bson_append(b, bson_iterator_value(elem), data_size);
1145     }
1146
1147     return BSON_OK;
1148 }
1149
1150 int bson_append_timestamp(bson *b, const char *name, bson_timestamp_t *ts) {
1151     if (bson_append_estart(b, BSON_TIMESTAMP, name, 8) == BSON_ERROR) return BSON_ERROR;
1152
1153     bson_append32(b, &(ts->i));
1154     bson_append32(b, &(ts->t));
1155
1156     return BSON_OK;
1157 }
1158
1159 int bson_append_timestamp2(bson *b, const char *name, int time, int increment) {
1160     if (bson_append_estart(b, BSON_TIMESTAMP, name, 8) == BSON_ERROR) return BSON_ERROR;
1161
1162     bson_append32(b, &increment);
1163     bson_append32(b, &time);
1164     return BSON_OK;
1165 }
1166
1167 int bson_append_date(bson *b, const char *name, bson_date_t millis) {
1168     if (bson_append_estart(b, BSON_DATE, name, 8) == BSON_ERROR) return BSON_ERROR;
1169     bson_append64(b, &millis);
1170     return BSON_OK;
1171 }
1172
1173 int bson_append_time_t(bson *b, const char *name, time_t secs) {
1174     return bson_append_date(b, name, (bson_date_t) secs * 1000);
1175 }
1176
1177 int bson_append_start_object(bson *b, const char *name) {
1178     if (bson_append_estart(b, BSON_OBJECT, name, 5) == BSON_ERROR) return BSON_ERROR;
1179     b->stack[ b->stackPos++ ] = b->cur - b->data;
1180     bson_append32(b, &zero);
1181     return BSON_OK;
1182 }
1183
1184 int bson_append_start_object2(bson *b, const char *name, int namelen) {
1185     if (bson_append_estart2(b, BSON_OBJECT, name, namelen, 5) == BSON_ERROR) return BSON_ERROR;
1186     b->stack[ b->stackPos++ ] = b->cur - b->data;
1187     bson_append32(b, &zero);
1188     return BSON_OK;
1189 }
1190
1191 int bson_append_start_array(bson *b, const char *name) {
1192     return bson_append_start_array2(b, name, strlen(name));
1193 }
1194
1195 int bson_append_start_array2(bson *b, const char *name, int namelen) {
1196     if (bson_append_estart2(b, BSON_ARRAY, name, namelen, 5) == BSON_ERROR) return BSON_ERROR;
1197     b->stack[ b->stackPos++ ] = b->cur - b->data;
1198     bson_append32(b, &zero);
1199     return BSON_OK;
1200 }
1201
1202 int bson_append_finish_object(bson *b) {
1203     char *start;
1204     int i;
1205     if (bson_ensure_space(b, 1) == BSON_ERROR) return BSON_ERROR;
1206     bson_append_byte(b, 0);
1207
1208     start = b->data + b->stack[ --b->stackPos ];
1209     i = b->cur - start;
1210     bson_little_endian32(start, &i);
1211
1212     return BSON_OK;
1213 }
1214
1215 double bson_int64_to_double(int64_t i64) {
1216     return (double) i64;
1217 }
1218
1219 int bson_append_finish_array(bson *b) {
1220     return bson_append_finish_object(b);
1221 }
1222
1223 /* Error handling and allocators. */
1224
1225 static bson_err_handler err_handler = NULL;
1226
1227 bson_err_handler set_bson_err_handler(bson_err_handler func) {
1228     bson_err_handler old = err_handler;
1229     err_handler = func;
1230     return old;
1231 }
1232
1233 void bson_free(void *ptr) {
1234     bson_free_func(ptr);
1235 }
1236
1237 void *bson_malloc(int size) {
1238     void *p;
1239     p = bson_malloc_func(size);
1240     bson_fatal_msg(!!p, "malloc() failed");
1241     return p;
1242 }
1243
1244 void *bson_realloc(void *ptr, int size) {
1245     void *p;
1246     p = bson_realloc_func(ptr, size);
1247     bson_fatal_msg(!!p, "realloc() failed");
1248     return p;
1249 }
1250
1251 int _bson_errprintf(const char *format, ...) {
1252     va_list ap;
1253     int ret;
1254     va_start(ap, format);
1255     ret = vfprintf(stderr, format, ap);
1256     va_end(ap);
1257     return ret;
1258 }
1259
1260 /**
1261  * This method is invoked when a non-fatal bson error is encountered.
1262  * Calls the error handler if available.
1263  *
1264  *  @param
1265  */
1266 void bson_builder_error(bson *b) {
1267     if (err_handler)
1268         err_handler("BSON error.");
1269 }
1270
1271 void bson_fatal(int ok) {
1272     bson_fatal_msg(ok, "");
1273 }
1274
1275 void bson_fatal_msg(int ok, const char *msg) {
1276     if (ok)
1277         return;
1278
1279     if (err_handler) {
1280         err_handler(msg);
1281     }
1282     bson_errprintf("error: %s\n", msg);
1283 }
1284
1285
1286 /* Efficiently copy an integer to a string. */
1287 extern const char bson_numstrs[1000][4];
1288
1289 void bson_numstr(char *str, int64_t i) {
1290     if (i >= 0 && i < 1000)
1291         memcpy(str, bson_numstrs[i], 4);
1292     else
1293         sprintf(str, "%" PRId64 "", (int64_t) i);
1294 }
1295
1296 #pragma GCC diagnostic push
1297 #pragma GCC diagnostic ignored "-Wformat"
1298
1299 int bson_numstrn(char *str, int maxbuf, int64_t i) {
1300     if (i >= 0 && i < 1000 && maxbuf > 4) {
1301         memcpy(str, bson_numstrs[i], 4);
1302         return strlen(bson_numstrs[i]);
1303     } else {
1304         return snprintf(str, maxbuf, "%" PRId64 "", (int64_t) i);
1305     }
1306 }
1307 #pragma GCC diagnostic pop
1308
1309 static bson_bool_t bson_isnumstr(const char *str, int len) {
1310     assert(str);
1311     bool isnum = false;
1312     while (len > 0 && *str > '\0' && *str <= ' ') {
1313         str++;
1314         len--;
1315     }
1316     while (len > 0 && *str >= '0' && *str <= '9') {
1317         isnum = true;
1318         str++;
1319         len--;
1320     }
1321     while (len > 0 && *str > '\0' && *str <= ' ') {
1322         str++;
1323         len--;
1324     }
1325     return (isnum && (*str == '\0' || len == 0));
1326 }
1327
1328 void bson_swap_endian64(void *outp, const void *inp) {
1329     const char *in = (const char *) inp;
1330     char *out = (char *) outp;
1331     out[0] = in[7];
1332     out[1] = in[6];
1333     out[2] = in[5];
1334     out[3] = in[4];
1335     out[4] = in[3];
1336     out[5] = in[2];
1337     out[6] = in[1];
1338     out[7] = in[0];
1339
1340 }
1341
1342 void bson_swap_endian32(void *outp, const void *inp) {
1343     const char *in = (const char *) inp;
1344     char *out = (char *) outp;
1345     out[0] = in[3];
1346     out[1] = in[2];
1347     out[2] = in[1];
1348     out[3] = in[0];
1349 }
1350
1351 static const char *bson_iterator_value2(const bson_iterator *i, int *klen) {
1352     const char *t = i->cur + 1;
1353     *klen = strlen(t);
1354     t += (*klen + 1);
1355     return t;
1356 }
1357
1358 int bson_append_array_from_iterator(const char *key, bson_iterator *from, bson *into) {
1359     assert(key && from && into);
1360     bson_type bt;
1361     bson_append_start_array(into, key);
1362     while ((bt = bson_iterator_next(from)) != BSON_EOO) {
1363         bson_append_field_from_iterator(from, into);
1364     }
1365     bson_append_finish_array(into);
1366     return BSON_OK;
1367 }
1368
1369 int bson_append_object_from_iterator(const char *key, bson_iterator *from, bson *into) {
1370     assert(key && from && into);
1371     bson_type bt;
1372     bson_append_start_object(into, key);
1373     while ((bt = bson_iterator_next(from)) != BSON_EOO) {
1374         bson_append_field_from_iterator(from, into);
1375     }
1376     bson_append_finish_object(into);
1377     return BSON_OK;
1378 }
1379
1380 static void bson_append_fpath_from_iterator(const char *fpath, const bson_iterator *from, bson *into) {
1381     char key[BSON_MAX_FPATH_LEN + 1];
1382     int fplen = strlen(fpath);
1383     if (fplen >= BSON_MAX_FPATH_LEN) { //protect me silently
1384         return; //todo error?
1385     }
1386     const char *fp = fpath;
1387     int keylen = 0;
1388     int nl = 0; //nesting level
1389     while (fplen > 0) { //split fpath with '.' delim
1390         const char *rp = fp;
1391         const char *ep = fp + fplen;
1392         while (rp < ep) {
1393             if (*rp == '.') break;
1394             rp++;
1395         }
1396         keylen = (rp - fp);
1397         memcpy(key, fp, keylen);
1398         key[keylen] = '\0';
1399         rp++;
1400         fplen -= keylen;
1401         if (fplen <= 0) { //last part of fp
1402             bson_append_field_from_iterator2(key, from, into);
1403             while (nl-- > 0) {
1404                 bson_append_finish_object(into); //arrays are covered also
1405             }
1406         } else { //intermediate part
1407             if (bson_isnumstr(key, keylen)) {
1408                 nl++;
1409                 bson_append_start_array2(into, key, keylen);
1410             } else {
1411                 nl++;
1412                 bson_append_start_object2(into, key, keylen);
1413             }
1414         }
1415         fp = rp;
1416     }
1417 }
1418
1419 int bson_append_field_from_iterator2(const char *key, const bson_iterator *from, bson *into) {
1420     assert(key && from && into);
1421     bson_type t = BSON_ITERATOR_TYPE(from);
1422     if (t == BSON_EOO || into->finished) {
1423         return BSON_ERROR;
1424     }
1425     switch (t) {
1426         case BSON_STRING:
1427         case BSON_SYMBOL:
1428             bson_append_string(into, key, bson_iterator_string(from));
1429             break;
1430         case BSON_CODE:
1431             bson_append_code(into, key, bson_iterator_code(from));
1432             break;
1433         case BSON_INT:
1434             bson_append_int(into, key, bson_iterator_int_raw(from));
1435             break;
1436         case BSON_DOUBLE:
1437             bson_append_double(into, key, bson_iterator_double_raw(from));
1438             break;
1439         case BSON_LONG:
1440             bson_append_long(into, key, bson_iterator_long_raw(from));
1441             break;
1442         case BSON_UNDEFINED:
1443             bson_append_undefined(into, key);
1444             break;
1445         case BSON_NULL:
1446             bson_append_null(into, key);
1447             break;
1448         case BSON_BOOL:
1449             bson_append_bool(into, key, bson_iterator_bool_raw(from));
1450             break;
1451         case BSON_TIMESTAMP:
1452         {
1453             bson_timestamp_t ts = bson_iterator_timestamp(from);
1454             bson_append_timestamp(into, key, &ts);
1455             break;
1456         }
1457         case BSON_DATE:
1458             bson_append_date(into, key, bson_iterator_date(from));
1459             break;
1460         case BSON_REGEX:
1461             bson_append_regex(into, key, bson_iterator_regex(from), bson_iterator_regex_opts(from));
1462             break;
1463         case BSON_OID:
1464             bson_append_oid(into, key, bson_iterator_oid(from));
1465             break;
1466         case BSON_OBJECT:
1467         {
1468             bson_iterator sit;
1469             BSON_ITERATOR_SUBITERATOR(from, &sit);
1470             bson_append_start_object(into, key);
1471             while (bson_iterator_next(&sit) != BSON_EOO) {
1472                 bson_append_field_from_iterator(&sit, into);
1473             }
1474             bson_append_finish_object(into);
1475             break;
1476         }
1477         case BSON_ARRAY:
1478         {
1479             bson_iterator sit;
1480             BSON_ITERATOR_SUBITERATOR(from, &sit);
1481             bson_append_start_array(into, key);
1482             while (bson_iterator_next(&sit) != BSON_EOO) {
1483                 bson_append_field_from_iterator(&sit, into);
1484             }
1485             bson_append_finish_array(into);
1486             break;
1487         }
1488         case BSON_DBREF:
1489         case BSON_CODEWSCOPE:
1490             break;
1491         default:
1492             break;
1493     }
1494     return BSON_OK;
1495 }
1496
1497 int bson_append_field_from_iterator(const bson_iterator *from, bson *into) {
1498     assert(from && into);
1499     return bson_append_field_from_iterator2(BSON_ITERATOR_KEY(from), from, into);
1500 }
1501
1502 typedef struct {
1503     bson *bsout;
1504     TCMAP *mfields;
1505     const void *bsdata2; //bsdata to merge with
1506     int nstack; //nested object stack pos
1507     int matched; //number of matched merge fields
1508 } _BSONMERGE3CTX;
1509
1510 static bson_visitor_cmd_t _bson_merge_fieldpaths_visitor(
1511         const char *ipath, int ipathlen,
1512         const char *key, int keylen,
1513         const bson_iterator *it,
1514         bool after, void *op) {
1515
1516     _BSONMERGE3CTX *ctx = op;
1517     assert(ctx && ctx->bsout && ctx->mfields && ipath && key && it && op);
1518     const void *buf;
1519     const char *mpath;
1520     int bufsz;
1521     bson_type bt = BSON_ITERATOR_TYPE(it);
1522     buf = (TCMAPRNUM(ctx->mfields) == 0 || after) ? NULL : tcmapget(ctx->mfields, ipath, ipathlen, &bufsz);
1523     if (buf) {
1524         bson_iterator it2;
1525         BSON_ITERATOR_FROM_BUFFER(&it2, ctx->bsdata2);
1526         off_t it2off;
1527         assert(bufsz == sizeof (it2off));
1528         memcpy(&it2off, buf, sizeof (it2off));
1529         assert(it2off >= 0);
1530         it2.cur = it2.cur + it2off;
1531         it2.first = (it2off == 0);
1532         tcmapout(ctx->mfields, ipath, ipathlen);
1533         bson_append_field_from_iterator2(key, &it2, ctx->bsout);
1534         return (BSON_VCMD_SKIP_AFTER | BSON_VCMD_SKIP_NESTED);
1535     } else {
1536         if (bt == BSON_OBJECT || bt == BSON_ARRAY) {
1537             if (!after) {
1538                 ctx->nstack++;
1539                 if (bt == BSON_OBJECT) {
1540                     bson_append_start_object2(ctx->bsout, key, keylen);
1541                 } else if (bt == BSON_ARRAY) {
1542                     bson_append_start_array2(ctx->bsout, key, keylen);
1543                 }
1544                 return BSON_VCMD_OK;
1545             } else {
1546                 if (ctx->nstack > 0) {
1547                     //do we have something to add into end of nested object?
1548                     tcmapiterinit(ctx->mfields);
1549                     int mpathlen = 0;
1550                     while ((mpath = tcmapiternext(ctx->mfields, &mpathlen)) != NULL) {
1551                         int i = 0;
1552                         for (; i < ipathlen && *(mpath + i) == *(ipath + i); ++i);
1553                         if (i == ipathlen && *(mpath + i) == '.' && *(mpath + i + 1) != '\0') { //ipath prefixed
1554                             bson_iterator it2;
1555                             BSON_ITERATOR_FROM_BUFFER(&it2, ctx->bsdata2);
1556                             buf = tcmapget(ctx->mfields, mpath, mpathlen, &bufsz);
1557                             off_t it2off;
1558                             assert(bufsz == sizeof (it2off));
1559                             memcpy(&it2off, buf, sizeof (it2off));
1560                             assert(it2off >= 0);
1561                             it2.cur = it2.cur + it2off;
1562                             it2.first = (it2off == 0);
1563                             bson_append_fpath_from_iterator(mpath + i + 1, &it2, ctx->bsout);
1564                             tcmapout(ctx->mfields, mpath, mpathlen);
1565                         }
1566                     }
1567                     ctx->nstack--;
1568                     if (bt == BSON_OBJECT) {
1569                         bson_append_finish_object(ctx->bsout);
1570                     } else if (bt == BSON_ARRAY) {
1571                         bson_append_finish_array(ctx->bsout);
1572                     }
1573                 }
1574                 return BSON_VCMD_OK;
1575             }
1576         } else {
1577             bson_append_field_from_iterator(it, ctx->bsout);
1578             return BSON_VCMD_SKIP_AFTER;
1579         }
1580     }
1581 }
1582
1583 //merge with fpath support
1584
1585 int bson_merge_fieldpaths(const void *bsdata1, const void *bsdata2, bson *out) {
1586     assert(bsdata1 && bsdata2 && out);
1587     bson_iterator it1, it2;
1588     bson_type bt;
1589     BSON_ITERATOR_FROM_BUFFER(&it1, bsdata1);
1590     BSON_ITERATOR_FROM_BUFFER(&it2, bsdata2);
1591     const char *it2start = it2.cur;
1592     TCMAP *mfields = tcmapnew2(TCMAPTINYBNUM);
1593     _BSONMERGE3CTX ctx = {
1594         .bsout = out,
1595         .mfields = mfields,
1596         .bsdata2 = bsdata2,
1597         .matched = 0,
1598         .nstack = 0
1599     };
1600     //collect active fpaths
1601     while ((bt = bson_iterator_next(&it2)) != BSON_EOO) {
1602         const char* key = BSON_ITERATOR_KEY(&it2);
1603         off_t it2off = (it2.cur - it2start);
1604         tcmapput(mfields, key, strlen(key), &it2off, sizeof (it2off));
1605     }
1606     bson_visit_fields(&it1, 0, _bson_merge_fieldpaths_visitor, &ctx);
1607     assert(ctx.nstack == 0);
1608     if (TCMAPRNUM(mfields) == 0) { //all merge fields applied
1609         tcmapdel(mfields);
1610         return BSON_OK;
1611     }
1612
1613     //apply the remaining merge fields
1614     tcmapiterinit(mfields);
1615     const char *fpath;
1616     int fplen;
1617     while ((fpath = tcmapiternext(mfields, &fplen)) != NULL) {
1618         BSON_ITERATOR_FROM_BUFFER(&it2, bsdata2);
1619         if (bson_find_fieldpath_value2(fpath, fplen, &it2) != BSON_EOO) {
1620             bson_append_fpath_from_iterator(fpath, &it2, out);
1621         }
1622     }
1623     tcmapdel(mfields);
1624
1625     if (!out->err) {
1626         // check duplicate paths
1627         bson_finish(out);
1628         if (bson_check_duplicate_keys(out)) {
1629             bson bstmp;
1630             bson_copy(&bstmp, out);
1631             bson_destroy(out);
1632             bson_init(out);
1633             bson_fix_duplicate_keys(&bstmp, out);
1634             bson_destroy(&bstmp);
1635         }
1636     }
1637     return out->err;
1638 }
1639
1640 int bson_merge2(const void *b1data, const void *b2data, bson_bool_t overwrite, bson *out) {
1641     bson_iterator it1, it2;
1642     bson_type bt1, bt2;
1643
1644     BSON_ITERATOR_FROM_BUFFER(&it1, b1data);
1645     BSON_ITERATOR_FROM_BUFFER(&it2, b2data);
1646     //Append all fields in B1 overwriten by B2
1647     while ((bt1 = bson_iterator_next(&it1)) != BSON_EOO) {
1648         const char* k1 = BSON_ITERATOR_KEY(&it1);
1649         if (overwrite && strcmp(JDBIDKEYNAME, k1) && (bt2 = bson_find_from_buffer(&it2, b2data, k1)) != BSON_EOO) {
1650             bson_append_field_from_iterator(&it2, out);
1651         } else {
1652             bson_append_field_from_iterator(&it1, out);
1653         }
1654     }
1655     BSON_ITERATOR_FROM_BUFFER(&it1, b1data);
1656     BSON_ITERATOR_FROM_BUFFER(&it2, b2data);
1657     //Append all fields from B2 missing in B1
1658     while ((bt2 = bson_iterator_next(&it2)) != BSON_EOO) {
1659         const char* k2 = BSON_ITERATOR_KEY(&it2);
1660         if ((bt1 = bson_find_from_buffer(&it1, b1data, k2)) == BSON_EOO) {
1661             bson_append_field_from_iterator(&it2, out);
1662         }
1663     }
1664     return BSON_OK;
1665 }
1666
1667 int bson_merge(const bson *b1, const bson *b2, bson_bool_t overwrite, bson *out) {
1668     assert(b1 && b2 && out);
1669     if (!b1->finished || !b2->finished || out->finished) {
1670         return BSON_ERROR;
1671     }
1672     return bson_merge2(bson_data(b1), bson_data(b2), overwrite, out);
1673 }
1674
1675 int bson_merge_recursive2(const void *b1data, const void *b2data, bson_bool_t overwrite, bson *out) {
1676     bson_iterator it1, it2;
1677     bson_type bt1, bt2;
1678     if (out->finished) {
1679         return BSON_ERROR;
1680     }
1681     BSON_ITERATOR_FROM_BUFFER(&it1, b1data);
1682     BSON_ITERATOR_FROM_BUFFER(&it2, b2data);
1683     //Append all fields in B1 merging with fields in B2 (for nested objects & arrays)
1684     while ((bt1 = bson_iterator_next(&it1)) != BSON_EOO) {
1685         const char* k1 = BSON_ITERATOR_KEY(&it1);
1686         bt2 = bson_find_from_buffer(&it2, b2data, k1);
1687         if (bt1 == BSON_OBJECT && bt2 == BSON_OBJECT) {
1688             int res;
1689             bson_append_start_object(out, k1);
1690             if ((res = bson_merge_recursive2(bson_iterator_value(&it1), bson_iterator_value(&it2), overwrite, out)) != BSON_OK) {
1691                 return res;
1692             }
1693             bson_append_finish_object(out);
1694         } else if (bt1 == BSON_ARRAY && bt2 == BSON_ARRAY) {
1695             int c = 0;
1696             bson_iterator sit;
1697             bson_type sbt;
1698
1699             bson_append_start_array(out, k1);
1700             BSON_ITERATOR_SUBITERATOR(&it1, &sit);
1701             while ((sbt = bson_iterator_next(&sit)) != BSON_EOO) {
1702                 bson_append_field_from_iterator(&sit, out);
1703                 ++c;
1704             }
1705             char kbuf[TCNUMBUFSIZ];
1706             BSON_ITERATOR_SUBITERATOR(&it2, &sit);
1707             while ((sbt = bson_iterator_next(&sit)) != BSON_EOO) {
1708                 bson_numstrn(kbuf, TCNUMBUFSIZ, c++);
1709                 bson_append_field_from_iterator2(kbuf, &sit, out);
1710             }
1711
1712             bson_append_finish_array(out);
1713         } else if (overwrite && strcmp(JDBIDKEYNAME, k1) && bt2 != BSON_EOO) {
1714             bson_append_field_from_iterator(&it2, out);
1715         } else {
1716             bson_append_field_from_iterator(&it1, out);
1717         }
1718     }
1719
1720     BSON_ITERATOR_FROM_BUFFER(&it1, b1data);
1721     BSON_ITERATOR_FROM_BUFFER(&it2, b2data);
1722     //Append all fields from B2 missing in B1
1723     while ((bt2 = bson_iterator_next(&it2)) != BSON_EOO) {
1724         const char* k2 = BSON_ITERATOR_KEY(&it2);
1725         if ((bt1 = bson_find_from_buffer(&it1, b1data, k2)) == BSON_EOO) {
1726             bson_append_field_from_iterator(&it2, out);
1727         }
1728     }
1729     return BSON_OK;
1730 }
1731
1732 int bson_merge_recursive(const bson *b1, const bson *b2, bson_bool_t overwrite, bson *out) {
1733     assert(b1 && b2 && out);
1734     if (!b1->finished || !b2->finished || out->finished) {
1735         return BSON_ERROR;
1736     }
1737     return bson_merge_recursive2(bson_data(b1), bson_data(b2), overwrite, out);
1738 }
1739
1740 static bson_bool_t _bson_check_duplicate_keys(bson_iterator *it) {
1741     bson_iterator it2;
1742     bson_type bt, bt2;
1743     while ((bt = bson_iterator_next(it)) != BSON_EOO) {
1744         BSON_ITERATOR_CLONE(it, &it2);
1745         while((bt2 = bson_iterator_next(&it2)) != BSON_EOO) {
1746             if (!strcmp(BSON_ITERATOR_KEY(it), BSON_ITERATOR_KEY(&it2))) {
1747                 return true;
1748             }
1749         }
1750         if (bt == BSON_OBJECT || bt == BSON_ARRAY) {
1751             BSON_ITERATOR_SUBITERATOR(it, &it2);
1752             if (_bson_check_duplicate_keys(&it2)) {
1753                 return true;
1754             }
1755         }
1756     }
1757
1758     return false;
1759 }
1760
1761 bson_bool_t bson_check_duplicate_keys(const bson *bs) {
1762     bson_iterator it;
1763     BSON_ITERATOR_INIT(&it, bs);
1764     return _bson_check_duplicate_keys(&it);
1765 }
1766
1767 static void _bson_fix_duplicate_keys(bson_iterator *it, bson *bso) {
1768     bson_iterator it2;
1769     bson_type bt, bt2;
1770
1771     TCMAP *keys = tcmapnew();
1772     while((bt = bson_iterator_next(it)) != BSON_EOO) {
1773         if (NULL != tcmapget2(keys, BSON_ITERATOR_KEY(it))) {
1774             continue;
1775         }
1776         tcmapput2(keys, BSON_ITERATOR_KEY(it), BSON_ITERATOR_KEY(it));
1777
1778         TCLIST *dups = tclistnew();
1779         off_t itoff  = 0;
1780         tclistpush(dups, &itoff, sizeof(itoff));
1781
1782         BSON_ITERATOR_CLONE(it, &it2);
1783         while((bt2 = bson_iterator_next(&it2)) != BSON_EOO) {
1784             if (!strcmp(BSON_ITERATOR_KEY(it), BSON_ITERATOR_KEY(&it2))) {
1785                 bt2 = BSON_ITERATOR_TYPE(&it2);
1786                 if (bt != bt2 || (bt != BSON_OBJECT && bt != BSON_ARRAY)) {
1787                     tclistclear(dups);
1788                     bt = bt2;
1789                 }
1790                 itoff = it2.cur - it->cur;
1791                 tclistpush(dups, &itoff, sizeof(itoff));
1792             }
1793         }
1794
1795         const char *buf;
1796         int bufsz;
1797
1798         buf = tclistval(dups, TCLISTNUM(dups) - 1, &bufsz);
1799         memcpy(&itoff, buf, sizeof(itoff));
1800         it2.cur = it->cur + itoff;
1801         it2.first = itoff == 0 ? it->first : 0;
1802
1803         bt2 = BSON_ITERATOR_TYPE(&it2);
1804         if (bt2 == BSON_OBJECT) {
1805             bson bst;
1806             bson_init(&bst);
1807             int j = -1;
1808             while(++j < TCLISTNUM(dups)) {
1809                 buf = tclistval(dups, j, &bufsz);
1810                 memcpy(&itoff, buf, sizeof(itoff));
1811                 it2.cur = it->cur + itoff;
1812                 it2.first = itoff == 0 ? it->first : 0;
1813
1814                 bson_iterator sit;
1815                 BSON_ITERATOR_SUBITERATOR(&it2, &sit);
1816                 while(bson_iterator_next(&sit) != BSON_EOO){
1817                     bson_append_field_from_iterator(&sit, &bst);
1818                 }
1819             }
1820             bson_finish(&bst);
1821
1822             bson_append_start_object(bso, BSON_ITERATOR_KEY(it));
1823             BSON_ITERATOR_INIT(&it2, &bst);
1824             _bson_fix_duplicate_keys(&it2, bso);
1825             bson_append_finish_object(bso);
1826         } else if (bt2 == BSON_ARRAY) {
1827             char ibuf[TCNUMBUFSIZ];
1828             memset(ibuf, '\0', TCNUMBUFSIZ);
1829
1830             bson_append_start_array(bso, BSON_ITERATOR_KEY(it));
1831             int ind = 0;
1832             int j = -1;
1833             while(++j < TCLISTNUM(dups)) {
1834                 buf = tclistval(dups, TCLISTNUM(dups) - 1, &bufsz);
1835                 memcpy(&itoff, buf, sizeof(itoff));
1836                 it2.cur = it->cur + itoff;
1837                 it2.first = itoff == 0 ? it->first : 0;
1838
1839                 bson_iterator sit, sit2;
1840                 bson_type sbt;
1841                 BSON_ITERATOR_SUBITERATOR(&it2, &sit);
1842                 while((sbt = bson_iterator_next(&sit)) != BSON_EOO) {
1843                     bson_numstrn(ibuf, TCNUMBUFSIZ, ind++);
1844                     if (sbt == BSON_OBJECT) {
1845                         bson_append_start_object(bso, ibuf);
1846                         BSON_ITERATOR_SUBITERATOR(&sit, &sit2);
1847                         _bson_fix_duplicate_keys(&sit2, bso);
1848                         bson_append_finish_object(bso);
1849                     } else if(sbt == BSON_ARRAY) {
1850                         bson_append_start_array(bso, ibuf);
1851                         BSON_ITERATOR_SUBITERATOR(&sit, &sit2);
1852                         _bson_fix_duplicate_keys(&sit2, bso);
1853                         bson_append_finish_array(bso);
1854                     } else {
1855                         bson_append_field_from_iterator2(ibuf, &sit, bso);
1856                     }
1857                 }
1858             }
1859             bson_append_finish_array(bso);
1860         } else {
1861             bson_append_field_from_iterator(&it2, bso);
1862         }
1863         tclistclear(dups);
1864         tclistdel(dups);
1865     }
1866     tcmapdel(keys);
1867 }
1868
1869 void bson_fix_duplicate_keys(const bson *bsi, bson *bso) {
1870     bson_iterator it;
1871
1872     BSON_ITERATOR_INIT(&it, bsi);
1873     _bson_fix_duplicate_keys(&it, bso);
1874 }
1875
1876
1877 typedef struct {
1878     int nstack; //nested object stack pos
1879     int matched; //number of matched include fields
1880     int astack; //nested array stack pos
1881     BSONSTRIPCTX *sctx;
1882 } _BSONSTRIPVISITORCTX;
1883
1884 /* Discard excluded fields from BSON */
1885 static bson_visitor_cmd_t _bsonstripvisitor_exclude(
1886         const char *ipath, int ipathlen,
1887         const char *key, int keylen,
1888         const bson_iterator *it,
1889         bool after, void *op) {
1890
1891     _BSONSTRIPVISITORCTX *ictx = op;
1892     assert(ictx);
1893     BSONSTRIPCTX *sctx = ictx->sctx;
1894     assert(sctx && sctx->bsout && sctx->ifields && ipath && key && it && op);
1895     TCMAP *ifields = sctx->ifields;
1896     const void *buf;
1897     int bufsz;
1898     const char* ifpath;
1899     bson_type bt = BSON_ITERATOR_TYPE(it);
1900
1901     buf = after ? NULL : tcmapget(ifields, ipath, ipathlen, &bufsz);
1902     if (!buf) {
1903         if (bt == BSON_OBJECT || bt == BSON_ARRAY) {
1904             if (!after) {
1905                 tcmapiterinit(ifields); //check prefix
1906                 while ((ifpath = tcmapiternext2(ifields)) != NULL) {
1907                     int i = 0;
1908                     for (; i < ipathlen && *(ifpath + i) == *(ipath + i); ++i);
1909                     if (i == ipathlen) { //ipath prefixes some exclude object field
1910                         ictx->nstack++;
1911                         if (bt == BSON_OBJECT) {
1912                             bson_append_start_object2(sctx->bsout, key, keylen);
1913                         } else if (bt == BSON_ARRAY) {
1914                             ictx->astack++;
1915                             bson_append_start_array2(sctx->bsout, key, keylen);
1916                         }
1917                         return (BSON_VCMD_OK);
1918                     }
1919                 }
1920                 bson_append_field_from_iterator(it, sctx->bsout);
1921                 return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
1922             } else {
1923                 if (ictx->nstack > 0) {
1924                     --ictx->nstack;
1925                     if (bt == BSON_OBJECT) {
1926                         bson_append_finish_object(sctx->bsout);
1927                     } else if (bt == BSON_ARRAY) {
1928                         --ictx->astack;
1929                         bson_append_finish_array(sctx->bsout);
1930                     }
1931                 }
1932                 return (BSON_VCMD_OK);
1933             }
1934         } else {
1935             bson_append_field_from_iterator(it, sctx->bsout);
1936             return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
1937         }
1938     } else {
1939         if (sctx->collector) {
1940             const char *k = NULL;
1941             char cpath[BSON_MAX_FPATH_LEN + 1];
1942             assert(ipathlen <= BSON_MAX_FPATH_LEN && !sctx->collector->finished);
1943             if (sctx->fkfields) {
1944                 k = tcmapget(sctx->fkfields, ipath, ipathlen, &bufsz);
1945             }
1946             if (!k) {
1947                 memcpy(cpath, ipath, ipathlen);
1948                 cpath[ipathlen] = '\0';
1949                 k = cpath;
1950             }
1951             bson_iterator cit = *it;
1952             bson_append_field_from_iterator2(k, &cit, sctx->collector);
1953         }
1954         if (!after && ictx->astack > 0 && bson_isnumstr(key, keylen)) {
1955             bson_append_undefined(sctx->bsout, key);
1956         }
1957         ictx->matched++;
1958     }
1959     return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
1960 }
1961
1962 /* Accept only included fields into BSON */
1963 static bson_visitor_cmd_t _bsonstripvisitor_include(
1964         const char *ipath, int ipathlen,
1965         const char *key, int keylen,
1966         const bson_iterator *it, bool after, void *op) {
1967
1968     _BSONSTRIPVISITORCTX *ictx = op;
1969     assert(ictx);
1970     BSONSTRIPCTX *sctx = ictx->sctx;
1971     assert(sctx && sctx->bsout && sctx->ifields && ipath && key && it && op);
1972     bson_visitor_cmd_t rv = BSON_VCMD_OK;
1973     TCMAP *ifields = sctx->ifields;
1974     const void *buf;
1975     const char* ifpath;
1976     int bufsz;
1977
1978     const char *k = key;
1979     if (sctx->fkfields) { //find keys to override
1980         k = tcmapget(sctx->fkfields, ipath, ipathlen, &bufsz);
1981     }
1982     if (!k) {
1983         k = key;
1984     }
1985     bson_type bt = BSON_ITERATOR_TYPE(it);
1986     if (bt != BSON_OBJECT && bt != BSON_ARRAY) {
1987         if (after) { //simple primitive case
1988             return BSON_VCMD_OK;
1989         }
1990         buf = tcmapget(ifields, ipath, ipathlen, &bufsz);
1991         if (buf) {
1992             ictx->matched++;
1993             bson_append_field_from_iterator2(k, it, sctx->bsout);
1994         }
1995         return (BSON_VCMD_SKIP_AFTER);
1996     } else { //more complicated case
1997         if (!after) {
1998             buf = tcmapget(ifields, ipath, ipathlen, &bufsz);
1999             if (buf) { //field hitted
2000                 bson_iterator cit = *it; //copy iterator
2001                 bson_append_field_from_iterator(&cit, sctx->bsout);
2002                 ictx->matched++;
2003                 return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2004             } else { //check prefix
2005                 int onstack = ictx->nstack;
2006                 tcmapiterinit(ifields);
2007                 while ((ifpath = tcmapiternext2(ifields)) != NULL) {
2008                     int i = 0;
2009                     for (; i < ipathlen && *(ifpath + i) == *(ipath + i); ++i);
2010                     if (i == ipathlen) { //ipath prefixes some included field
2011                         ictx->nstack++;
2012                         if (bt == BSON_OBJECT) {
2013                             bson_append_start_object2(sctx->bsout, k, keylen);
2014                         } else if (bt == BSON_ARRAY) {
2015                             bson_append_start_array2(sctx->bsout, k, keylen);
2016                         } else {
2017                             assert(0);
2018                         }
2019                         break;
2020                     }
2021                 }
2022                 if (onstack == ictx->nstack) {
2023                     return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2024                 }
2025             }
2026         } else { //after
2027             if (ictx->nstack > 0) {
2028                 --ictx->nstack;
2029                 if (bt == BSON_OBJECT) {
2030                     bson_append_finish_object(sctx->bsout);
2031                 } else if (bt == BSON_ARRAY) {
2032                     bson_append_finish_array(sctx->bsout);
2033                 } else {
2034                     assert(0);
2035                 }
2036             }
2037         }
2038     }
2039
2040     if (ictx->nstack == 0 && ictx->matched == TCMAPRNUM(ifields)) {
2041         return BSON_VCMD_TERMINATE;
2042     }
2043     return rv;
2044 }
2045
2046 int bson_strip(TCMAP *ifields, bool imode, const void *bsbuf, bson *bsout, int *matched) {
2047     BSONSTRIPCTX sctx = {
2048         .ifields = ifields,
2049         .imode = imode,
2050         .bsbuf = bsbuf,
2051         .bsout = bsout,
2052         .fkfields = NULL,
2053         .matched = 0
2054     };
2055     int rc = bson_strip2(&sctx);
2056     *matched = sctx.matched;
2057     return rc;
2058 }
2059
2060 /* Include or exclude fpaths in the specified BSON and put resulting data into `bsout`. */
2061 int bson_strip2(BSONSTRIPCTX *sctx) {
2062     assert(sctx && sctx->bsbuf && sctx->bsout);
2063     if (!sctx->ifields || sctx->bsout->finished) {
2064         return BSON_ERROR;
2065     }
2066     _BSONSTRIPVISITORCTX ictx = {
2067         .nstack = 0,
2068         .astack = 0,
2069         .matched = 0,
2070         .sctx = sctx
2071     };
2072     bson_iterator it;
2073     BSON_ITERATOR_FROM_BUFFER(&it, sctx->bsbuf);
2074     bson_visit_fields(&it, 0, (sctx->imode) ? _bsonstripvisitor_include : _bsonstripvisitor_exclude, &ictx);
2075     assert(ictx.nstack == 0);
2076     sctx->matched = ictx.matched;
2077     return bson_finish(sctx->bsout);
2078 }
2079
2080 int bson_rename(TCMAP *fields, const void *bsbuf, bson *bsout, int *rencnt) {
2081     *rencnt = 0;
2082     if (TCMAPRNUM(fields) == 0) {
2083         return BSON_OK; //nothing to rename
2084     }
2085
2086     int rv;
2087     bson res, collector;
2088     bson_init(&res);
2089     bson_init(&collector);
2090
2091     BSONSTRIPCTX sctx = {
2092         .ifields = fields,
2093         .imode = false,
2094         .bsbuf = bsbuf,
2095         .bsout = &res,
2096         .collector = &collector,
2097         .fkfields = fields
2098     };
2099     if ((rv = bson_strip2(&sctx)) != BSON_OK) {
2100         goto finish;
2101     }
2102     if ((rv = bson_finish(&res)) != BSON_OK) {
2103         goto finish;
2104     }
2105     if ((rv = bson_finish(&collector)) != BSON_OK) {
2106         goto finish;
2107     }
2108     if ((rv = bson_merge_fieldpaths(bson_data(&res),
2109                                     bson_data(&collector),
2110                                     bsout)) != BSON_OK) {
2111         goto finish;
2112     }
2113     *rencnt = sctx.matched;
2114 finish:
2115     bson_destroy(&res);
2116     bson_destroy(&collector);
2117     return rv;
2118 }
2119
2120 int bson_inplace_set_bool(bson_iterator *pos, bson_bool_t val) {
2121     assert(pos);
2122     bson_type bt = BSON_ITERATOR_TYPE(pos);
2123     if (bt != BSON_BOOL) {
2124         return BSON_ERROR;
2125     }
2126     char *t = (char*) pos->cur + 1;
2127     t += strlen(t) + 1;
2128     *t = (val != 0);
2129     return BSON_OK;
2130 }
2131
2132 int bson_inplace_set_long(bson_iterator *pos, int64_t val) {
2133     assert(pos);
2134     bson_type bt = BSON_ITERATOR_TYPE(pos);
2135     if (!BSON_IS_NUM_TYPE(bt)) {
2136         return BSON_ERROR;
2137     }
2138     char *t = (char*) pos->cur + 1;
2139     t += strlen(t) + 1;
2140     if (bt == BSON_INT) {
2141         bson_little_endian32(t, &val);
2142     } else if (bt == BSON_LONG || bt == BSON_DATE) {
2143         bson_little_endian64(t, &val);
2144     } else if (bt == BSON_DOUBLE) {
2145         double dval = (double) val;
2146         bson_little_endian64(t, &dval);
2147     } else {
2148         return BSON_ERROR;
2149     }
2150     return BSON_OK;
2151 }
2152
2153 int bson_inplace_set_double(bson_iterator *pos, double val) {
2154     assert(pos);
2155     bson_type bt = BSON_ITERATOR_TYPE(pos);
2156     if (!BSON_IS_NUM_TYPE(bt)) {
2157         return BSON_ERROR;
2158     }
2159     int64_t ival = (int64_t) val;
2160     char *t = (char*) pos->cur + 1;
2161     t += strlen(t) + 1;
2162     if (bt == BSON_INT) {
2163         bson_little_endian32(t, &ival);
2164     } else if (bt == BSON_LONG || bt == BSON_DATE) {
2165         bson_little_endian64(t, &ival);
2166     } else if (bt == BSON_DOUBLE) {
2167         bson_little_endian64(t, &val);
2168     } else {
2169         return BSON_ERROR;
2170     }
2171     return BSON_OK;
2172 }
2173
2174 int bson_compare_fpaths(const void *bsdata1, const void *bsdata2, const char *fpath1, int fplen1, const char *fpath2, int fplen2) {
2175     assert(bsdata1 && bsdata2 && fpath1 && fpath2);
2176     bson_iterator it1, it2;
2177     BSON_ITERATOR_FROM_BUFFER(&it1, bsdata1);
2178     BSON_ITERATOR_FROM_BUFFER(&it2, bsdata2);
2179     bson_find_fieldpath_value2(fpath1, fplen1, &it1);
2180     bson_find_fieldpath_value2(fpath2, fplen2, &it2);
2181     return bson_compare_it_current(&it1, &it2);
2182 }
2183
2184 /**
2185  *
2186  * Return <0 if value pointing by it1 lesser than from it2.
2187  * Return  0 if values equal
2188  * Return >0 if value pointing by it1 greater than from it2.
2189  * @param it1
2190  * @param i
2191  * @return
2192  */
2193 int bson_compare_it_current(const bson_iterator *it1, const bson_iterator *it2) {
2194     bson_type t1 = BSON_ITERATOR_TYPE(it1);
2195     bson_type t2 = BSON_ITERATOR_TYPE(it2);
2196
2197         if ((BSON_IS_STRING_TYPE(t1) && !BSON_IS_STRING_TYPE(t2)) ||
2198                 (BSON_IS_STRING_TYPE(t2) && !BSON_IS_STRING_TYPE(t1))) {
2199                 return (t1 - t2);
2200         }
2201
2202     if (t1 == BSON_BOOL || t1 == BSON_EOO || t1 == BSON_NULL || t1 == BSON_UNDEFINED) {
2203         int v1 = bson_iterator_bool(it1);
2204         int v2 = bson_iterator_bool(it2);
2205         return (v1 > v2) ? 1 : ((v1 < v2) ? -1 : 0);
2206     } else if (t1 == BSON_INT || t1 == BSON_LONG || t1 == BSON_DATE || t1 == BSON_TIMESTAMP) {
2207         int64_t v1 = bson_iterator_long_ext(it1);
2208         int64_t v2 = bson_iterator_long_ext(it2);
2209         return (v1 > v2) ? 1 : ((v1 < v2) ? -1 : 0);
2210     } else if (t1 == BSON_DOUBLE) {
2211         double v1 = bson_iterator_double_raw(it1);
2212         double v2 = bson_iterator_double(it2);
2213         return (v1 > v2) ? 1 : ((v1 < v2) ? -1 : 0);
2214     } else if (BSON_IS_STRING_TYPE(t1)) {
2215         const char* v1 = bson_iterator_string(it1);
2216         int l1 = bson_iterator_string_len(it1);
2217         const char* v2 = bson_iterator_string(it2);
2218         int l2 = bson_iterator_string_len(it2);
2219         int rv;
2220         TCCMPLEXICAL(rv, v1, l1, v2, l2);
2221         return rv;
2222     } else if (t1 == BSON_BINDATA && t2 == BSON_BINDATA) {
2223         int l1 = bson_iterator_bin_len(it1);
2224         int l2 = bson_iterator_bin_len(it2);
2225         return memcmp(bson_iterator_bin_data(it1), bson_iterator_bin_data(it2), MIN(l1, l2));
2226     } else if (t1 == BSON_OID && t2 == BSON_OID) {
2227         return memcmp(bson_iterator_oid(it1), bson_iterator_oid(it2), sizeof (bson_oid_t));
2228     } else if (t1 == t2 && (t1 == BSON_OBJECT || t1 == BSON_ARRAY)) {
2229         int cv = 0;
2230         bson_type bt1, bt2;
2231         bson_iterator sit1, sit2;
2232         BSON_ITERATOR_SUBITERATOR(it1, &sit1);
2233         BSON_ITERATOR_SUBITERATOR(it2, &sit2);
2234         while ((bt1 = bson_iterator_next(&sit1)) != BSON_EOO) {
2235             bt2 = bson_iterator_next(&sit2);
2236             if (bt2 == BSON_EOO) {
2237                 cv = 1;
2238                 break;
2239             }
2240             cv = bson_compare_it_current(&sit1, &sit2);
2241             if (cv) {
2242                 break;
2243             }
2244         }
2245         if (cv == 0 && bson_iterator_next(&sit2) != BSON_EOO) {
2246             cv = -1;
2247         }
2248         return cv;
2249     }
2250     return (t1 - t2);
2251 }
2252
2253 int bson_compare(const void *bsdata1, const void *bsdata2, const char* fpath, int fplen) {
2254     return bson_compare_fpaths(bsdata1, bsdata2, fpath, fplen, fpath, fplen);
2255 }
2256
2257 int bson_compare_string(const char *cv, const void *bsdata, const char *fpath) {
2258     assert(cv && bsdata && fpath);
2259     bson *bs1 = bson_create();
2260     bson_init(bs1);
2261     bson_append_string(bs1, "$", cv);
2262     bson_finish(bs1);
2263     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2264     bson_del(bs1);
2265     return res;
2266 }
2267
2268 int bson_compare_long(const int64_t cv, const void *bsdata, const char *fpath) {
2269     bson *bs1 = bson_create();
2270     bson_init(bs1);
2271     bson_append_long(bs1, "$", cv);
2272     bson_finish(bs1);
2273     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2274     bson_del(bs1);
2275     return res;
2276 }
2277
2278 int bson_compare_double(double cv, const void *bsdata, const char *fpath) {
2279     bson *bs1 = bson_create();
2280     bson_init(bs1);
2281     bson_append_double(bs1, "$", cv);
2282     bson_finish(bs1);
2283     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2284     bson_del(bs1);
2285     return res;
2286 }
2287
2288 int bson_compare_bool(bson_bool_t cv, const void *bsdata, const char *fpath) {
2289     bson *bs1 = bson_create();
2290     bson_init(bs1);
2291     bson_append_bool(bs1, "$", cv);
2292     bson_finish(bs1);
2293     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2294     bson_del(bs1);
2295     return res;
2296 }
2297
2298 bson* bson_dup(const bson *src) {
2299     assert(src);
2300     bson *rv = bson_create();
2301     int s = bson_size(src);
2302     _bson_init_size(rv, s);
2303     memmove(rv->data, src->data, s);
2304     rv->finished = 1;
2305     return rv;
2306 }
2307
2308 bson* bson_create_from_iterator(bson_iterator *from) {
2309     assert(from);
2310     bson_type bt;
2311     bson *bs = bson_create();
2312     bson_init_as_query(bs);
2313     while ((bt = bson_iterator_next(from)) != BSON_EOO) {
2314         bson_append_field_from_iterator(from, bs);
2315     }
2316     bson_finish(bs);
2317     return bs;
2318 }
2319
2320 bson* bson_create_from_buffer(const void* buf, int bufsz) {
2321     return bson_create_from_buffer2(bson_create(), buf, bufsz);
2322 }
2323
2324 bson* bson_create_from_buffer2(bson *rv, const void* buf, int bufsz) {
2325     assert(buf);
2326     assert(bufsz - 4 > 0);
2327     bson_init_size(rv, bufsz);
2328     bson_ensure_space(rv, bufsz - 4);
2329     bson_append(rv, (char*) buf + 4, bufsz - (4 + 1/*BSON_EOO*/));
2330     bson_finish(rv);
2331     return rv;
2332 }
2333
2334 void bson_init_with_data(bson *bs, const void *bsdata) {
2335     memset(bs, 0, sizeof (*bs));
2336     bs->data = (char*) bsdata;
2337     bson_little_endian32(&bs->dataSize, bsdata);
2338     bs->finished = true;
2339 }
2340
2341 bool bson_find_merged_arrays(const void *mbuf, const void *inbuf, bool expandall) {
2342     assert(mbuf && inbuf);
2343     bool found = false;
2344     bson_iterator it, it2;
2345     bson_type bt, bt2;
2346     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2347
2348     while (!found && (bt = bson_iterator_next(&it)) != BSON_EOO) {
2349         if (expandall && bt != BSON_ARRAY) {
2350             continue;
2351         }
2352         BSON_ITERATOR_FROM_BUFFER(&it2, inbuf);
2353         bt2 = bson_find_fieldpath_value(BSON_ITERATOR_KEY(&it), &it2);
2354         if (bt2 != BSON_ARRAY) {
2355             continue;
2356         }
2357         bson_iterator sit;
2358         BSON_ITERATOR_SUBITERATOR(&it2, &sit);
2359         while (!found && (bt2 = bson_iterator_next(&sit)) != BSON_EOO) {
2360             if (expandall) {
2361                 bson_iterator sit2;
2362                 BSON_ITERATOR_SUBITERATOR(&it, &sit2);
2363                 while ((bt2 = bson_iterator_next(&sit2)) != BSON_EOO) {
2364                     if (!bson_compare_it_current(&sit, &sit2)) {
2365                         found = true;
2366                         break;
2367                     }
2368                 }
2369             } else {
2370                 if (!bson_compare_it_current(&sit, &it)) {
2371                     found = true;
2372                     break;
2373                 }
2374             }
2375         }
2376     }
2377     return found;
2378 }
2379
2380 bool bson_find_unmerged_arrays(const void *mbuf, const void *inbuf) {
2381     assert(mbuf && inbuf);
2382     bool allfound = false;
2383     bson_iterator it, it2;
2384     bson_type bt, bt2;
2385     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2386     while ((bt = bson_iterator_next(&it)) != BSON_EOO) {
2387         BSON_ITERATOR_FROM_BUFFER(&it2, inbuf);
2388         bt2 = bson_find_fieldpath_value(BSON_ITERATOR_KEY(&it), &it2);
2389         if (bt2 == BSON_EOO) { //array missing it will be created
2390             allfound = false;
2391             break;
2392         }
2393         if (bt2 != BSON_ARRAY) { //not an array field
2394             continue;
2395         }
2396         allfound = false;
2397         bson_iterator sit;
2398         BSON_ITERATOR_SUBITERATOR(&it2, &sit);
2399         while ((bt2 = bson_iterator_next(&sit)) != BSON_EOO) {
2400             if (!bson_compare_it_current(&sit, &it)) {
2401                 allfound = true;
2402                 break;
2403             }
2404         }
2405         if (!allfound) {
2406             break;
2407         }
2408     }
2409     return !allfound;
2410 }
2411
2412 typedef struct {
2413     bson *bsout;
2414     const void *mbuf;
2415     int mfields;
2416     int ecode;
2417     bool duty;
2418     bool expandall;
2419     bson_merge_array_mode mode;
2420 } _BSONMARRCTX;
2421
2422
2423 static bson_visitor_cmd_t _bson_merge_arrays_pull_visitor(
2424                         const char *fpath, int fpathlen,
2425                         const char *key, int keylen,
2426                         const bson_iterator *it, bool after, void *op) {
2427
2428     _BSONMARRCTX *ctx = op;
2429     assert(ctx && ctx->mfields >= 0);
2430     bson_iterator mit;
2431     bson_type bt = BSON_ITERATOR_TYPE(it);
2432     if (bt != BSON_OBJECT && bt != BSON_ARRAY) { //trivial case
2433         if (after) {
2434             return (BSON_VCMD_OK);
2435         }
2436         bson_append_field_from_iterator(it, ctx->bsout);
2437         return (BSON_VCMD_SKIP_AFTER);
2438     }
2439     if (bt == BSON_ARRAY) {
2440         BSON_ITERATOR_FROM_BUFFER(&mit, ctx->mbuf);
2441         bt = bson_find_fieldpath_value2(fpath, fpathlen, &mit);
2442         if (bt == BSON_EOO || (ctx->expandall && bt != BSON_ARRAY)) {
2443             bson_append_field_from_iterator(it, ctx->bsout);
2444             return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2445         }
2446         if (ctx->mfields > 0) {
2447             --ctx->mfields;
2448         }
2449         //Find and merge
2450         bson_iterator ait;
2451         BSON_ITERATOR_SUBITERATOR(it, &ait);
2452         bson_append_start_array(ctx->bsout, key);
2453         int c = 0;
2454         bool found = false;
2455         while ((bt = bson_iterator_next(&ait)) != BSON_EOO) {
2456             found = false;
2457             if (ctx->expandall) {
2458                 bson_iterator mitsub;
2459                 BSON_ITERATOR_SUBITERATOR(&mit, &mitsub);
2460                 while ((bt = bson_iterator_next(&mitsub)) != BSON_EOO) {
2461                     if (!bson_compare_it_current(&ait, &mitsub)) {
2462                         found = true;
2463                         break;
2464                     }
2465                 }
2466             } else {
2467                 found = !bson_compare_it_current(&ait, &mit);
2468             }
2469             if (!found) {
2470                 char kbuf[TCNUMBUFSIZ];
2471                 bson_numstrn(kbuf, TCNUMBUFSIZ, c++);
2472                 bson_append_field_from_iterator2(kbuf, &ait, ctx->bsout);
2473             }
2474         }
2475         bson_append_finish_array(ctx->bsout);
2476         return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2477     }
2478     //bt is BSON_OBJECT
2479     if (!after) {
2480         bson_append_start_object(ctx->bsout, key);
2481     } else { //after
2482         bson_append_finish_object(ctx->bsout);
2483     }
2484     return (BSON_VCMD_OK);
2485 }
2486
2487 static bson_visitor_cmd_t _bson_merge_arrays_visitor(
2488                         const char *fpath, int fpathlen,
2489                         const char *key, int keylen,
2490                         const bson_iterator *it,
2491                         bool after, void *op) {
2492
2493     _BSONMARRCTX *ctx = op;
2494     assert(ctx && ctx->mfields >= 0);
2495     bson_iterator mit;
2496     bson_type bt = BSON_ITERATOR_TYPE(it);
2497
2498     if (bt != BSON_OBJECT && bt != BSON_ARRAY) { //trivial case
2499         if (after) {
2500             return (BSON_VCMD_OK);
2501         }
2502         bson_append_field_from_iterator(it, ctx->bsout);
2503         return (BSON_VCMD_SKIP_AFTER);
2504     }
2505     if (bt == BSON_ARRAY) {
2506         if (after) {
2507             bson_append_finish_array(ctx->bsout);
2508             return (BSON_VCMD_OK);
2509         }
2510         BSON_ITERATOR_FROM_BUFFER(&mit, ctx->mbuf);
2511         bt = bson_find_fieldpath_value2(fpath, fpathlen, &mit);
2512         if (bt == BSON_EOO) {
2513             bson_append_start_array(ctx->bsout, key);
2514             return (BSON_VCMD_OK);
2515         }
2516         if (ctx->expandall && bt != BSON_ARRAY) {
2517             bson_append_field_from_iterator(it, ctx->bsout);
2518             return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2519         }
2520         if (ctx->mfields > 0) {
2521             --ctx->mfields;
2522         }
2523         //Find and merge
2524         bson_iterator ait;
2525         BSON_ITERATOR_SUBITERATOR(it, &ait);
2526         bson_append_start_array(ctx->bsout, key);
2527         bool found = false;
2528         int c = 0;
2529         if (ctx->expandall) { //Set of array elements to add
2530             while ((bt = bson_iterator_next(&ait)) != BSON_EOO) { //Flush current array
2531                 bson_append_field_from_iterator(&ait, ctx->bsout);
2532                 ++c;
2533             }
2534             //Iterate over set to add
2535             bson_iterator mitsub;
2536             BSON_ITERATOR_SUBITERATOR(&mit, &mitsub); //mit has BSON_ARRAY type
2537             while ((bt = bson_iterator_next(&mitsub)) != BSON_EOO) {
2538                 found = false;
2539                 if (ctx->mode == BSON_MERGE_ARRAY_ADDSET) {
2540                     BSON_ITERATOR_SUBITERATOR(it, &ait); //Rewind main array iterator
2541                     while ((bt = bson_iterator_next(&ait)) != BSON_EOO) {
2542                         if (!bson_compare_it_current(&ait, &mitsub)) {
2543                             found = true;
2544                             break;
2545                         }
2546                     }
2547                 }
2548                 if (!found) { //Append missing element
2549                     char kbuf[TCNUMBUFSIZ];
2550                     bson_numstrn(kbuf, TCNUMBUFSIZ, c++);
2551                     bson_append_field_from_iterator2(kbuf, &mitsub, ctx->bsout);
2552                     ctx->duty = true;
2553                 }
2554             }
2555         } else { //Single element to add
2556             while ((bt = bson_iterator_next(&ait)) != BSON_EOO) {
2557                 if ((ctx->mode == BSON_MERGE_ARRAY_ADDSET) &&
2558                     !found &&
2559                     !bson_compare_it_current(&ait, &mit)) {
2560                     found = true;
2561                 }
2562                 bson_append_field_from_iterator(&ait, ctx->bsout);
2563                 ++c;
2564             }
2565             if (!found) { //uppend missing element into array
2566                 char kbuf[TCNUMBUFSIZ];
2567                 bson_numstrn(kbuf, TCNUMBUFSIZ, c);
2568                 bson_append_field_from_iterator2(kbuf, &mit, ctx->bsout);
2569                 ctx->duty = true;
2570             }
2571         }
2572         bson_append_finish_array(ctx->bsout);
2573         return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2574     }
2575     //bt is BSON_OBJECT
2576     if (!after) {
2577         bson_append_start_object(ctx->bsout, key);
2578     } else { //after
2579         bson_append_finish_object(ctx->bsout);
2580     }
2581     return (BSON_VCMD_OK);
2582 }
2583
2584 int bson_merge_arrays(const void *mbuf,
2585                       const void *inbuf,
2586                       bson_merge_array_mode mode,
2587                       bool expandall,
2588                       bson *bsout) {
2589
2590     assert(mbuf && inbuf && bsout);
2591     assert(mode == BSON_MERGE_ARRAY_ADDSET ||
2592            mode == BSON_MERGE_ARRAY_PULL ||
2593            mode == BSON_MERGE_ARRAY_PUSH);
2594
2595     if (bsout->finished) {
2596         return BSON_ERROR;
2597     }
2598     _BSONMARRCTX ctx = {
2599         .bsout = bsout,
2600         .mbuf = mbuf,
2601         .mfields = 0,
2602         .duty = false,
2603         .expandall = expandall,
2604         .ecode = BSON_OK,
2605         .mode = mode
2606     };
2607     bson_type bt, bt2;
2608     bson_iterator it, it2;
2609     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2610     while ((bt = bson_iterator_next(&it)) != BSON_EOO) {
2611         if (expandall && bt != BSON_ARRAY) {
2612             continue;
2613         }
2614         ctx.mfields++;
2615     }
2616     BSON_ITERATOR_FROM_BUFFER(&it, inbuf);
2617     if (mode == BSON_MERGE_ARRAY_PULL) {
2618         bson_visit_fields(&it, 0, _bson_merge_arrays_pull_visitor, &ctx);
2619     } else {
2620         bson_visit_fields(&it, 0, _bson_merge_arrays_visitor, &ctx);
2621     }
2622     if (ctx.mfields == 0 || //all fields are merged
2623         mode == BSON_MERGE_ARRAY_PULL) {
2624         return ctx.ecode;
2625     }
2626
2627     //Append missing arrays fields
2628     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2629     while ((bt = bson_iterator_next(&it)) != BSON_EOO) {
2630         const char *fpath = BSON_ITERATOR_KEY(&it);
2631         // all data from inbuf already in bsout
2632         bson_finish(bsout);
2633         BSON_ITERATOR_INIT(&it2, bsout);
2634         bt2 = bson_find_fieldpath_value(fpath, &it2);
2635         if (bt2 != BSON_EOO) continue;
2636         int i = 0;
2637         int lvl = 0;
2638         const char *pdp = fpath;
2639         bson bst;
2640         bson_init(&bst);
2641         while (*(fpath + i) != '\0') {
2642             for (; *(fpath + i) != '\0' && *(fpath + i) != '.'; ++i);
2643             if (*(fpath + i) == '\0') { //EOF
2644                 assert((fpath + i) - pdp > 0);
2645                 bson_append_start_array2(&bst, pdp, (fpath + i) - pdp);
2646                 bson_append_field_from_iterator2("0", &it, &bst);
2647                 bson_append_finish_array(&bst);
2648                 break;
2649             } else {
2650                 ++lvl;
2651                 assert((fpath + i) - pdp > 0);
2652                 bson_append_start_object2(&bst, pdp, (fpath + i) - pdp);
2653             }
2654             pdp = (fpath + i);
2655             while (*pdp == '.') {
2656                 ++pdp;
2657                 ++i;
2658             }
2659         }
2660         for (; lvl > 0; --lvl) {
2661             bson_append_finish_object(&bst);
2662         }
2663         bson_finish(&bst);
2664
2665         bson bsc;
2666         bson_init_finished_data(&bsc, bson_data(bsout));
2667         bson_init_size(bsout, bson_size(bsout));
2668         int res = bson_merge_recursive(&bsc, &bst, false, bsout);
2669         bson_destroy(&bsc);
2670         bson_destroy(&bst);
2671         if (res != BSON_OK) {
2672             return BSON_ERROR;
2673         }
2674     }
2675     return ctx.ecode;
2676 }
2677
2678 typedef struct {
2679     int nlvl; //nesting level
2680     TCXSTR *out; //output buffer
2681 } _BSON2JSONCTX;
2682
2683 static void _jsonxstrescaped(TCXSTR *xstr, const char *str) {
2684     size_t sz = strlen(str);
2685     int s = 0;
2686     int e = 0;
2687     char hb[7];
2688     hb[0] = '\\';
2689     hb[1] = 'u';
2690     hb[2] = '0';
2691     hb[3] = '0';
2692     hb[6] = '\0';
2693     while (e < sz) {
2694         const char * ebuf = NULL;
2695         switch (str[e]) {
2696             case '\r': ebuf = "\\r";
2697                 break;
2698             case '\n': ebuf = "\\n";
2699                 break;
2700             case '\\': ebuf = "\\\\";
2701                 break;
2702             case '/':
2703                 break;
2704             case '"': ebuf = "\\\"";
2705                 break;
2706             case '\f': ebuf = "\\f";
2707                 break;
2708             case '\b': ebuf = "\\b";
2709                 break;
2710             case '\t': ebuf = "\\t";
2711                 break;
2712             default:
2713                 if ((unsigned char) str[e] < 0x20) {
2714                     static const char *hexchar = "0123456789ABCDEF";
2715                     hb[4] = hexchar[str[e] >> 4];
2716                     hb[5] = hexchar[str[e] & 0x0F];
2717                     ebuf = hb;
2718                 }
2719                 break;
2720         }
2721         if (ebuf != NULL) {
2722             if (e > s) {
2723                 tcxstrcat(xstr, str + s, e - s);
2724             }
2725             tcxstrcat2(xstr, ebuf);
2726             s = ++e;
2727         } else {
2728             ++e;
2729         }
2730     }
2731     tcxstrcat(xstr, (str + s), e - s);
2732 }
2733
2734 static int _bson2json(_BSON2JSONCTX *ctx, bson_iterator *it, bool array) {
2735
2736 #define BSPAD(_n) \
2737     for (int i = 0; i < ctx->nlvl + (_n); ++i) tcxstrcat2(ctx->out, " ")
2738
2739     bson_type bt;
2740     TCXSTR *out = ctx->out;
2741     tcxstrcat2(ctx->out, array ? "[\n" : "{\n");
2742     ctx->nlvl += 4;
2743     int c = 0;
2744     while ((bt = bson_iterator_next(it)) != BSON_EOO) {
2745         if (c++ > 0) {
2746             if (array) {
2747                 tcxstrcat2(out, "\n");
2748                 BSPAD(0);
2749             }
2750             tcxstrcat2(out, ",\n");
2751         }
2752         const char *key = BSON_ITERATOR_KEY(it);
2753         BSPAD(0);
2754         if (!array) {
2755             tcxstrcat2(out, "\"");
2756             _jsonxstrescaped(out, key);
2757             tcxstrcat2(out, "\" : ");
2758         }
2759
2760         switch (bt) {
2761             case BSON_LONG:
2762             case BSON_INT:
2763                 tcxstrprintf(out, "%" PRId64, (int64_t) bson_iterator_long_ext(it));
2764                 break;
2765             case BSON_DOUBLE:
2766             {
2767                 tcxstrprintf(out, "%lf", bson_iterator_double(it));
2768                 break;
2769             }
2770             case BSON_STRING:
2771             case BSON_SYMBOL:
2772             {
2773                 tcxstrcat2(out, "\"");
2774                 _jsonxstrescaped(out, bson_iterator_string(it));
2775                 tcxstrcat2(out, "\"");
2776                 break;
2777             }
2778             case BSON_OBJECT:
2779             case BSON_ARRAY:
2780             {
2781                 bson_iterator sit;
2782                 BSON_ITERATOR_SUBITERATOR(it, &sit);
2783                 _bson2json(ctx, &sit, bt == BSON_ARRAY);
2784                 break;
2785             }
2786             case BSON_NULL:
2787                 tcxstrcat2(out, "null");
2788             case BSON_UNDEFINED:
2789                 break;
2790             case BSON_DATE:
2791             {
2792                 bson_date_t t = bson_iterator_date(it);
2793                 char dbuf[49];
2794                 tcdatestrwww(t, INT_MAX, dbuf);
2795                 tcxstrprintf(out, "\"%s\"", dbuf);
2796                 break;
2797             }
2798             case BSON_BOOL:
2799                 tcxstrcat2(out, bson_iterator_bool(it) ? "true" : "false");
2800                 break;
2801             case BSON_OID:
2802             {
2803                 char xoid[25];
2804                 bson_oid_t *oid = bson_iterator_oid(it);
2805                 bson_oid_to_string(oid, xoid);
2806                 tcxstrprintf(out, "\"%s\"", xoid);
2807                 break;
2808             }
2809             case BSON_REGEX:
2810             {
2811                 tcxstrcat2(out, "\"");
2812                 _jsonxstrescaped(out, bson_iterator_regex(it));
2813                 tcxstrcat2(out, "\"");
2814                 break;
2815             }
2816             case BSON_BINDATA:
2817             {
2818                 const char *buf = bson_iterator_bin_data(it);
2819                 int bsz = bson_iterator_bin_len(it);
2820                 char *b64data = tcbaseencode(buf, bsz);
2821                 tcxstrcat2(out, "\"");
2822                 tcxstrcat2(out, b64data);
2823                 tcxstrcat2(out, "\"");
2824                 TCFREE(b64data);
2825                 break;
2826             }
2827             default:
2828                 break;
2829         }
2830     }
2831     tcxstrcat2(out, "\n");
2832     BSPAD(-4);
2833     tcxstrcat2(out, array ? "]" : "}");
2834     ctx->nlvl -= 4;
2835     return 0;
2836 #undef BSPAD
2837 }
2838
2839 int bson2json(const char *bsdata, char **buf, int *sp) {
2840     assert(bsdata && buf && sp);
2841     bson_iterator it;
2842     BSON_ITERATOR_FROM_BUFFER(&it, bsdata);
2843     TCXSTR *out = tcxstrnew();
2844     _BSON2JSONCTX ctx = {
2845         .nlvl = 0,
2846         .out = out
2847     };
2848     int ret = _bson2json(&ctx, &it, false);
2849     if (ret == BSON_OK) {
2850         *sp = TCXSTRSIZE(out);
2851         *buf = tcxstrtomalloc(out);
2852     } else {
2853         *sp = 0;
2854         *buf = NULL;
2855         tcxstrclear(out);
2856     }
2857     return ret;
2858 }
2859
2860
2861 #include "nxjson.h"
2862
2863 static void _json2bson(bson *out, const nx_json *json, const char *forcekey) {
2864     const char *key =  forcekey ? forcekey : json->key;
2865     switch (json->type) {
2866         case NX_JSON_NULL:
2867             assert(key);
2868             bson_append_null(out, key);
2869             break;
2870         case NX_JSON_OBJECT:
2871         {
2872             if (key) {
2873                 bson_append_start_object(out, key);
2874             }
2875             for (nx_json* js = json->child; js; js = js->next) {
2876                 _json2bson(out, js, NULL);
2877             }
2878             if (key) {
2879                 bson_append_finish_object(out);
2880             }
2881             break;
2882         }
2883         case NX_JSON_ARRAY:
2884         {
2885             if (key) {
2886                 bson_append_start_array(out, key);
2887             }
2888             int c = 0;
2889             char kbuf[TCNUMBUFSIZ];
2890             for (nx_json* js = json->child; js; js = js->next) {
2891                  bson_numstrn(kbuf, TCNUMBUFSIZ, c++);
2892                 _json2bson(out, js, kbuf);
2893             }
2894             if (key) {
2895                 bson_append_finish_array(out);
2896             }
2897             break;
2898         }
2899         case NX_JSON_STRING:
2900             assert(key);
2901             bson_append_string(out, key, json->text_value);
2902             break;
2903         case NX_JSON_INTEGER:
2904             assert(key);
2905             if (json->int_value <= INT_MAX && json->int_value >= INT_MIN) {
2906                 bson_append_int(out, key, (int) json->int_value);
2907             } else {
2908                 bson_append_long(out, key, json->int_value);
2909             }
2910             break;
2911         case NX_JSON_DOUBLE:
2912             assert(key);
2913             bson_append_double(out, key, json->dbl_value);
2914             break;
2915         case NX_JSON_BOOL:
2916             assert(key);
2917             bson_append_bool(out, key, json->int_value ? true : false);
2918             break;
2919         default:
2920             break;
2921     }
2922 }
2923
2924 bson* json2bson(const char *jsonstr) {
2925     bool err = false;
2926     bson *out = NULL;
2927     char *json = strdup(jsonstr); //nxjson uses inplace data modification
2928     if (!json) {
2929         return NULL;
2930     }
2931     out = bson_create();
2932     bson_init_as_query(out);
2933     const nx_json *nxjson = nx_json_parse_utf8(json);
2934     if (!nxjson) {
2935         err = true;
2936         goto finish;
2937     }
2938     _json2bson(out, nxjson, NULL);
2939     bson_finish(out);
2940     err = out->err;
2941 finish:
2942     free(json);
2943     if (nxjson) {
2944         nx_json_free(nxjson);
2945     }
2946     if (err && out) {
2947         bson_del(out);
2948         out = NULL;
2949     }
2950     return out;
2951 }
2952
2953
2954 typedef struct {
2955     bson *bs;
2956     bool checkdots;
2957     bool checkdollar;
2958 } _BSONVALIDATECTX;
2959
2960 static bson_visitor_cmd_t _bson_validate_visitor(
2961         const char *ipath, int ipathlen,
2962         const char *key, int keylen,
2963         const bson_iterator *it,
2964         bool after, void *op) {
2965     _BSONVALIDATECTX *ctx = op;
2966     assert(ctx);
2967     if (bson_check_field_name(ctx->bs, key, keylen,
2968                               ctx->checkdots, ctx->checkdollar) == BSON_ERROR) {
2969         return BSON_VCMD_TERMINATE;
2970     }
2971     return (BSON_VCMD_OK | BSON_VCMD_SKIP_AFTER);
2972 }
2973
2974
2975 int bson_validate(bson *bs, bool checkdots, bool checkdollar) {
2976     if (!bs) {
2977         return BSON_ERROR;
2978     }
2979     if (!bs->finished) {
2980         bs->err |= BSON_NOT_FINISHED;
2981         return BSON_ERROR;
2982     }
2983     bson_iterator it;
2984     bson_iterator_init(&it, bs);
2985     _BSONVALIDATECTX ctx = {
2986         .bs = bs,
2987         .checkdots = checkdots,
2988         .checkdollar = checkdollar
2989     };
2990     bson_visit_fields(&it, BSON_TRAVERSE_ARRAYS_EXCLUDED, _bson_validate_visitor, &ctx);
2991     return bs->err ? BSON_ERROR : BSON_OK;
2992 }
2993