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         tclistdel(dups);
1864     }
1865     tcmapdel(keys);
1866 }
1867
1868 void bson_fix_duplicate_keys(const bson *bsi, bson *bso) {
1869     bson_iterator it;
1870
1871     BSON_ITERATOR_INIT(&it, bsi);
1872     _bson_fix_duplicate_keys(&it, bso);
1873 }
1874
1875
1876 typedef struct {
1877     int nstack; //nested object stack pos
1878     int matched; //number of matched include fields
1879     int astack; //nested array stack pos
1880     BSONSTRIPCTX *sctx;
1881 } _BSONSTRIPVISITORCTX;
1882
1883 /* Discard excluded fields from BSON */
1884 static bson_visitor_cmd_t _bsonstripvisitor_exclude(
1885         const char *ipath, int ipathlen,
1886         const char *key, int keylen,
1887         const bson_iterator *it,
1888         bool after, void *op) {
1889
1890     _BSONSTRIPVISITORCTX *ictx = op;
1891     assert(ictx);
1892     BSONSTRIPCTX *sctx = ictx->sctx;
1893     assert(sctx && sctx->bsout && sctx->ifields && ipath && key && it && op);
1894     TCMAP *ifields = sctx->ifields;
1895     const void *buf;
1896     int bufsz;
1897     const char* ifpath;
1898     bson_type bt = BSON_ITERATOR_TYPE(it);
1899
1900     buf = after ? NULL : tcmapget(ifields, ipath, ipathlen, &bufsz);
1901     if (!buf) {
1902         if (bt == BSON_OBJECT || bt == BSON_ARRAY) {
1903             if (!after) {
1904                 tcmapiterinit(ifields); //check prefix
1905                 while ((ifpath = tcmapiternext2(ifields)) != NULL) {
1906                     int i = 0;
1907                     for (; i < ipathlen && *(ifpath + i) == *(ipath + i); ++i);
1908                     if (i == ipathlen) { //ipath prefixes some exclude object field
1909                         ictx->nstack++;
1910                         if (bt == BSON_OBJECT) {
1911                             bson_append_start_object2(sctx->bsout, key, keylen);
1912                         } else if (bt == BSON_ARRAY) {
1913                             ictx->astack++;
1914                             bson_append_start_array2(sctx->bsout, key, keylen);
1915                         }
1916                         return (BSON_VCMD_OK);
1917                     }
1918                 }
1919                 bson_append_field_from_iterator(it, sctx->bsout);
1920                 return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
1921             } else {
1922                 if (ictx->nstack > 0) {
1923                     --ictx->nstack;
1924                     if (bt == BSON_OBJECT) {
1925                         bson_append_finish_object(sctx->bsout);
1926                     } else if (bt == BSON_ARRAY) {
1927                         --ictx->astack;
1928                         bson_append_finish_array(sctx->bsout);
1929                     }
1930                 }
1931                 return (BSON_VCMD_OK);
1932             }
1933         } else {
1934             bson_append_field_from_iterator(it, sctx->bsout);
1935             return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
1936         }
1937     } else {
1938         if (sctx->collector) {
1939             const char *k = NULL;
1940             char cpath[BSON_MAX_FPATH_LEN + 1];
1941             assert(ipathlen <= BSON_MAX_FPATH_LEN && !sctx->collector->finished);
1942             if (sctx->fkfields) {
1943                 k = tcmapget(sctx->fkfields, ipath, ipathlen, &bufsz);
1944             }
1945             if (!k) {
1946                 memcpy(cpath, ipath, ipathlen);
1947                 cpath[ipathlen] = '\0';
1948                 k = cpath;
1949             }
1950             bson_iterator cit = *it;
1951             bson_append_field_from_iterator2(k, &cit, sctx->collector);
1952         }
1953         if (!after && ictx->astack > 0 && bson_isnumstr(key, keylen)) {
1954             bson_append_undefined(sctx->bsout, key);
1955         }
1956         ictx->matched++;
1957     }
1958     return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
1959 }
1960
1961 /* Accept only included fields into BSON */
1962 static bson_visitor_cmd_t _bsonstripvisitor_include(
1963         const char *ipath, int ipathlen,
1964         const char *key, int keylen,
1965         const bson_iterator *it, bool after, void *op) {
1966
1967     _BSONSTRIPVISITORCTX *ictx = op;
1968     assert(ictx);
1969     BSONSTRIPCTX *sctx = ictx->sctx;
1970     assert(sctx && sctx->bsout && sctx->ifields && ipath && key && it && op);
1971     bson_visitor_cmd_t rv = BSON_VCMD_OK;
1972     TCMAP *ifields = sctx->ifields;
1973     const void *buf;
1974     const char* ifpath;
1975     int bufsz;
1976
1977     const char *k = key;
1978     if (sctx->fkfields) { //find keys to override
1979         k = tcmapget(sctx->fkfields, ipath, ipathlen, &bufsz);
1980     }
1981     if (!k) {
1982         k = key;
1983     }
1984     bson_type bt = BSON_ITERATOR_TYPE(it);
1985     if (bt != BSON_OBJECT && bt != BSON_ARRAY) {
1986         if (after) { //simple primitive case
1987             return BSON_VCMD_OK;
1988         }
1989         buf = tcmapget(ifields, ipath, ipathlen, &bufsz);
1990         if (buf) {
1991             ictx->matched++;
1992             bson_append_field_from_iterator2(k, it, sctx->bsout);
1993         }
1994         return (BSON_VCMD_SKIP_AFTER);
1995     } else { //more complicated case
1996         if (!after) {
1997             buf = tcmapget(ifields, ipath, ipathlen, &bufsz);
1998             if (buf) { //field hitted
1999                 bson_iterator cit = *it; //copy iterator
2000                 bson_append_field_from_iterator(&cit, sctx->bsout);
2001                 ictx->matched++;
2002                 return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2003             } else { //check prefix
2004                 int onstack = ictx->nstack;
2005                 tcmapiterinit(ifields);
2006                 while ((ifpath = tcmapiternext2(ifields)) != NULL) {
2007                     int i = 0;
2008                     for (; i < ipathlen && *(ifpath + i) == *(ipath + i); ++i);
2009                     if (i == ipathlen) { //ipath prefixes some included field
2010                         ictx->nstack++;
2011                         if (bt == BSON_OBJECT) {
2012                             bson_append_start_object2(sctx->bsout, k, keylen);
2013                         } else if (bt == BSON_ARRAY) {
2014                             bson_append_start_array2(sctx->bsout, k, keylen);
2015                         } else {
2016                             assert(0);
2017                         }
2018                         break;
2019                     }
2020                 }
2021                 if (onstack == ictx->nstack) {
2022                     return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2023                 }
2024             }
2025         } else { //after
2026             if (ictx->nstack > 0) {
2027                 --ictx->nstack;
2028                 if (bt == BSON_OBJECT) {
2029                     bson_append_finish_object(sctx->bsout);
2030                 } else if (bt == BSON_ARRAY) {
2031                     bson_append_finish_array(sctx->bsout);
2032                 } else {
2033                     assert(0);
2034                 }
2035             }
2036         }
2037     }
2038
2039     if (ictx->nstack == 0 && ictx->matched == TCMAPRNUM(ifields)) {
2040         return BSON_VCMD_TERMINATE;
2041     }
2042     return rv;
2043 }
2044
2045 int bson_strip(TCMAP *ifields, bool imode, const void *bsbuf, bson *bsout, int *matched) {
2046     BSONSTRIPCTX sctx = {
2047         .ifields = ifields,
2048         .imode = imode,
2049         .bsbuf = bsbuf,
2050         .bsout = bsout,
2051         .fkfields = NULL,
2052         .matched = 0
2053     };
2054     int rc = bson_strip2(&sctx);
2055     *matched = sctx.matched;
2056     return rc;
2057 }
2058
2059 /* Include or exclude fpaths in the specified BSON and put resulting data into `bsout`. */
2060 int bson_strip2(BSONSTRIPCTX *sctx) {
2061     assert(sctx && sctx->bsbuf && sctx->bsout);
2062     if (!sctx->ifields || sctx->bsout->finished) {
2063         return BSON_ERROR;
2064     }
2065     _BSONSTRIPVISITORCTX ictx = {
2066         .nstack = 0,
2067         .astack = 0,
2068         .matched = 0,
2069         .sctx = sctx
2070     };
2071     bson_iterator it;
2072     BSON_ITERATOR_FROM_BUFFER(&it, sctx->bsbuf);
2073     bson_visit_fields(&it, 0, (sctx->imode) ? _bsonstripvisitor_include : _bsonstripvisitor_exclude, &ictx);
2074     assert(ictx.nstack == 0);
2075     sctx->matched = ictx.matched;
2076     return bson_finish(sctx->bsout);
2077 }
2078
2079 int bson_rename(TCMAP *fields, const void *bsbuf, bson *bsout, int *rencnt) {
2080     *rencnt = 0;
2081     if (TCMAPRNUM(fields) == 0) {
2082         return BSON_OK; //nothing to rename
2083     }
2084
2085     int rv;
2086     bson res, collector;
2087     bson_init(&res);
2088     bson_init(&collector);
2089
2090     BSONSTRIPCTX sctx = {
2091         .ifields = fields,
2092         .imode = false,
2093         .bsbuf = bsbuf,
2094         .bsout = &res,
2095         .collector = &collector,
2096         .fkfields = fields
2097     };
2098     if ((rv = bson_strip2(&sctx)) != BSON_OK) {
2099         goto finish;
2100     }
2101     if ((rv = bson_finish(&res)) != BSON_OK) {
2102         goto finish;
2103     }
2104     if ((rv = bson_finish(&collector)) != BSON_OK) {
2105         goto finish;
2106     }
2107     if ((rv = bson_merge_fieldpaths(bson_data(&res),
2108                                     bson_data(&collector),
2109                                     bsout)) != BSON_OK) {
2110         goto finish;
2111     }
2112     *rencnt = sctx.matched;
2113 finish:
2114     bson_destroy(&res);
2115     bson_destroy(&collector);
2116     return rv;
2117 }
2118
2119 int bson_inplace_set_bool(bson_iterator *pos, bson_bool_t val) {
2120     assert(pos);
2121     bson_type bt = BSON_ITERATOR_TYPE(pos);
2122     if (bt != BSON_BOOL) {
2123         return BSON_ERROR;
2124     }
2125     char *t = (char*) pos->cur + 1;
2126     t += strlen(t) + 1;
2127     *t = (val != 0);
2128     return BSON_OK;
2129 }
2130
2131 int bson_inplace_set_long(bson_iterator *pos, int64_t val) {
2132     assert(pos);
2133     bson_type bt = BSON_ITERATOR_TYPE(pos);
2134     if (!BSON_IS_NUM_TYPE(bt)) {
2135         return BSON_ERROR;
2136     }
2137     char *t = (char*) pos->cur + 1;
2138     t += strlen(t) + 1;
2139     if (bt == BSON_INT) {
2140         bson_little_endian32(t, &val);
2141     } else if (bt == BSON_LONG || bt == BSON_DATE) {
2142         bson_little_endian64(t, &val);
2143     } else if (bt == BSON_DOUBLE) {
2144         double dval = (double) val;
2145         bson_little_endian64(t, &dval);
2146     } else {
2147         return BSON_ERROR;
2148     }
2149     return BSON_OK;
2150 }
2151
2152 int bson_inplace_set_double(bson_iterator *pos, double val) {
2153     assert(pos);
2154     bson_type bt = BSON_ITERATOR_TYPE(pos);
2155     if (!BSON_IS_NUM_TYPE(bt)) {
2156         return BSON_ERROR;
2157     }
2158     int64_t ival = (int64_t) val;
2159     char *t = (char*) pos->cur + 1;
2160     t += strlen(t) + 1;
2161     if (bt == BSON_INT) {
2162         bson_little_endian32(t, &ival);
2163     } else if (bt == BSON_LONG || bt == BSON_DATE) {
2164         bson_little_endian64(t, &ival);
2165     } else if (bt == BSON_DOUBLE) {
2166         bson_little_endian64(t, &val);
2167     } else {
2168         return BSON_ERROR;
2169     }
2170     return BSON_OK;
2171 }
2172
2173 int bson_compare_fpaths(const void *bsdata1, const void *bsdata2, const char *fpath1, int fplen1, const char *fpath2, int fplen2) {
2174     assert(bsdata1 && bsdata2 && fpath1 && fpath2);
2175     bson_iterator it1, it2;
2176     BSON_ITERATOR_FROM_BUFFER(&it1, bsdata1);
2177     BSON_ITERATOR_FROM_BUFFER(&it2, bsdata2);
2178     bson_find_fieldpath_value2(fpath1, fplen1, &it1);
2179     bson_find_fieldpath_value2(fpath2, fplen2, &it2);
2180     return bson_compare_it_current(&it1, &it2);
2181 }
2182
2183 /**
2184  *
2185  * Return <0 if value pointing by it1 lesser than from it2.
2186  * Return  0 if values equal
2187  * Return >0 if value pointing by it1 greater than from it2.
2188  * @param it1
2189  * @param i
2190  * @return
2191  */
2192 int bson_compare_it_current(const bson_iterator *it1, const bson_iterator *it2) {
2193     bson_type t1 = BSON_ITERATOR_TYPE(it1);
2194     bson_type t2 = BSON_ITERATOR_TYPE(it2);
2195
2196         if ((BSON_IS_STRING_TYPE(t1) && !BSON_IS_STRING_TYPE(t2)) ||
2197                 (BSON_IS_STRING_TYPE(t2) && !BSON_IS_STRING_TYPE(t1))) {
2198                 return (t1 - t2);
2199         }
2200
2201     if (t1 == BSON_BOOL || t1 == BSON_EOO || t1 == BSON_NULL || t1 == BSON_UNDEFINED) {
2202         int v1 = bson_iterator_bool(it1);
2203         int v2 = bson_iterator_bool(it2);
2204         return (v1 > v2) ? 1 : ((v1 < v2) ? -1 : 0);
2205     } else if (t1 == BSON_INT || t1 == BSON_LONG || t1 == BSON_DATE || t1 == BSON_TIMESTAMP) {
2206         int64_t v1 = bson_iterator_long_ext(it1);
2207         int64_t v2 = bson_iterator_long_ext(it2);
2208         return (v1 > v2) ? 1 : ((v1 < v2) ? -1 : 0);
2209     } else if (t1 == BSON_DOUBLE) {
2210         double v1 = bson_iterator_double_raw(it1);
2211         double v2 = bson_iterator_double(it2);
2212         return (v1 > v2) ? 1 : ((v1 < v2) ? -1 : 0);
2213     } else if (BSON_IS_STRING_TYPE(t1)) {
2214         const char* v1 = bson_iterator_string(it1);
2215         int l1 = bson_iterator_string_len(it1);
2216         const char* v2 = bson_iterator_string(it2);
2217         int l2 = bson_iterator_string_len(it2);
2218         int rv;
2219         TCCMPLEXICAL(rv, v1, l1, v2, l2);
2220         return rv;
2221     } else if (t1 == BSON_BINDATA && t2 == BSON_BINDATA) {
2222         int l1 = bson_iterator_bin_len(it1);
2223         int l2 = bson_iterator_bin_len(it2);
2224         return memcmp(bson_iterator_bin_data(it1), bson_iterator_bin_data(it2), MIN(l1, l2));
2225     } else if (t1 == BSON_OID && t2 == BSON_OID) {
2226         return memcmp(bson_iterator_oid(it1), bson_iterator_oid(it2), sizeof (bson_oid_t));
2227     } else if (t1 == t2 && (t1 == BSON_OBJECT || t1 == BSON_ARRAY)) {
2228         int cv = 0;
2229         bson_type bt1, bt2;
2230         bson_iterator sit1, sit2;
2231         BSON_ITERATOR_SUBITERATOR(it1, &sit1);
2232         BSON_ITERATOR_SUBITERATOR(it2, &sit2);
2233         while ((bt1 = bson_iterator_next(&sit1)) != BSON_EOO) {
2234             bt2 = bson_iterator_next(&sit2);
2235             if (bt2 == BSON_EOO) {
2236                 cv = 1;
2237                 break;
2238             }
2239             cv = bson_compare_it_current(&sit1, &sit2);
2240             if (cv) {
2241                 break;
2242             }
2243         }
2244         if (cv == 0 && bson_iterator_next(&sit2) != BSON_EOO) {
2245             cv = -1;
2246         }
2247         return cv;
2248     }
2249     return (t1 - t2);
2250 }
2251
2252 int bson_compare(const void *bsdata1, const void *bsdata2, const char* fpath, int fplen) {
2253     return bson_compare_fpaths(bsdata1, bsdata2, fpath, fplen, fpath, fplen);
2254 }
2255
2256 int bson_compare_string(const char *cv, const void *bsdata, const char *fpath) {
2257     assert(cv && bsdata && fpath);
2258     bson *bs1 = bson_create();
2259     bson_init(bs1);
2260     bson_append_string(bs1, "$", cv);
2261     bson_finish(bs1);
2262     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2263     bson_del(bs1);
2264     return res;
2265 }
2266
2267 int bson_compare_long(const int64_t cv, const void *bsdata, const char *fpath) {
2268     bson *bs1 = bson_create();
2269     bson_init(bs1);
2270     bson_append_long(bs1, "$", cv);
2271     bson_finish(bs1);
2272     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2273     bson_del(bs1);
2274     return res;
2275 }
2276
2277 int bson_compare_double(double cv, const void *bsdata, const char *fpath) {
2278     bson *bs1 = bson_create();
2279     bson_init(bs1);
2280     bson_append_double(bs1, "$", cv);
2281     bson_finish(bs1);
2282     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2283     bson_del(bs1);
2284     return res;
2285 }
2286
2287 int bson_compare_bool(bson_bool_t cv, const void *bsdata, const char *fpath) {
2288     bson *bs1 = bson_create();
2289     bson_init(bs1);
2290     bson_append_bool(bs1, "$", cv);
2291     bson_finish(bs1);
2292     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2293     bson_del(bs1);
2294     return res;
2295 }
2296
2297 bson* bson_dup(const bson *src) {
2298     assert(src);
2299     bson *rv = bson_create();
2300     int s = bson_size(src);
2301     _bson_init_size(rv, s);
2302     memmove(rv->data, src->data, s);
2303     rv->finished = 1;
2304     return rv;
2305 }
2306
2307 bson* bson_create_from_iterator(bson_iterator *from) {
2308     assert(from);
2309     bson_type bt;
2310     bson *bs = bson_create();
2311     bson_init_as_query(bs);
2312     while ((bt = bson_iterator_next(from)) != BSON_EOO) {
2313         bson_append_field_from_iterator(from, bs);
2314     }
2315     bson_finish(bs);
2316     return bs;
2317 }
2318
2319 bson* bson_create_from_buffer(const void* buf, int bufsz) {
2320     return bson_create_from_buffer2(bson_create(), buf, bufsz);
2321 }
2322
2323 bson* bson_create_from_buffer2(bson *rv, const void* buf, int bufsz) {
2324     assert(buf);
2325     assert(bufsz - 4 > 0);
2326     bson_init_size(rv, bufsz);
2327     bson_ensure_space(rv, bufsz - 4);
2328     bson_append(rv, (char*) buf + 4, bufsz - (4 + 1/*BSON_EOO*/));
2329     bson_finish(rv);
2330     return rv;
2331 }
2332
2333 void bson_init_with_data(bson *bs, const void *bsdata) {
2334     memset(bs, 0, sizeof (*bs));
2335     bs->data = (char*) bsdata;
2336     bson_little_endian32(&bs->dataSize, bsdata);
2337     bs->finished = true;
2338 }
2339
2340 bool bson_find_merged_arrays(const void *mbuf, const void *inbuf, bool expandall) {
2341     assert(mbuf && inbuf);
2342     bool found = false;
2343     bson_iterator it, it2;
2344     bson_type bt, bt2;
2345     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2346
2347     while (!found && (bt = bson_iterator_next(&it)) != BSON_EOO) {
2348         if (expandall && bt != BSON_ARRAY) {
2349             continue;
2350         }
2351         BSON_ITERATOR_FROM_BUFFER(&it2, inbuf);
2352         bt2 = bson_find_fieldpath_value(BSON_ITERATOR_KEY(&it), &it2);
2353         if (bt2 != BSON_ARRAY) {
2354             continue;
2355         }
2356         bson_iterator sit;
2357         BSON_ITERATOR_SUBITERATOR(&it2, &sit);
2358         while (!found && (bt2 = bson_iterator_next(&sit)) != BSON_EOO) {
2359             if (expandall) {
2360                 bson_iterator sit2;
2361                 BSON_ITERATOR_SUBITERATOR(&it, &sit2);
2362                 while ((bt2 = bson_iterator_next(&sit2)) != BSON_EOO) {
2363                     if (!bson_compare_it_current(&sit, &sit2)) {
2364                         found = true;
2365                         break;
2366                     }
2367                 }
2368             } else {
2369                 if (!bson_compare_it_current(&sit, &it)) {
2370                     found = true;
2371                     break;
2372                 }
2373             }
2374         }
2375     }
2376     return found;
2377 }
2378
2379 bool bson_find_unmerged_arrays(const void *mbuf, const void *inbuf) {
2380     assert(mbuf && inbuf);
2381     bool allfound = false;
2382     bson_iterator it, it2;
2383     bson_type bt, bt2;
2384     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2385     while ((bt = bson_iterator_next(&it)) != BSON_EOO) {
2386         BSON_ITERATOR_FROM_BUFFER(&it2, inbuf);
2387         bt2 = bson_find_fieldpath_value(BSON_ITERATOR_KEY(&it), &it2);
2388         if (bt2 == BSON_EOO) { //array missing it will be created
2389             allfound = false;
2390             break;
2391         }
2392         if (bt2 != BSON_ARRAY) { //not an array field
2393             continue;
2394         }
2395         allfound = false;
2396         bson_iterator sit;
2397         BSON_ITERATOR_SUBITERATOR(&it2, &sit);
2398         while ((bt2 = bson_iterator_next(&sit)) != BSON_EOO) {
2399             if (!bson_compare_it_current(&sit, &it)) {
2400                 allfound = true;
2401                 break;
2402             }
2403         }
2404         if (!allfound) {
2405             break;
2406         }
2407     }
2408     return !allfound;
2409 }
2410
2411 typedef struct {
2412     bson *bsout;
2413     const void *mbuf;
2414     int mfields;
2415     int ecode;
2416     bool duty;
2417     bool expandall;
2418     bson_merge_array_mode mode;
2419 } _BSONMARRCTX;
2420
2421
2422 static bson_visitor_cmd_t _bson_merge_arrays_pull_visitor(
2423                         const char *fpath, int fpathlen,
2424                         const char *key, int keylen,
2425                         const bson_iterator *it, bool after, void *op) {
2426
2427     _BSONMARRCTX *ctx = op;
2428     assert(ctx && ctx->mfields >= 0);
2429     bson_iterator mit;
2430     bson_type bt = BSON_ITERATOR_TYPE(it);
2431     if (bt != BSON_OBJECT && bt != BSON_ARRAY) { //trivial case
2432         if (after) {
2433             return (BSON_VCMD_OK);
2434         }
2435         bson_append_field_from_iterator(it, ctx->bsout);
2436         return (BSON_VCMD_SKIP_AFTER);
2437     }
2438     if (bt == BSON_ARRAY) {
2439         BSON_ITERATOR_FROM_BUFFER(&mit, ctx->mbuf);
2440         bt = bson_find_fieldpath_value2(fpath, fpathlen, &mit);
2441         if (bt == BSON_EOO || (ctx->expandall && bt != BSON_ARRAY)) {
2442             bson_append_field_from_iterator(it, ctx->bsout);
2443             return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2444         }
2445         if (ctx->mfields > 0) {
2446             --ctx->mfields;
2447         }
2448         //Find and merge
2449         bson_iterator ait;
2450         BSON_ITERATOR_SUBITERATOR(it, &ait);
2451         bson_append_start_array(ctx->bsout, key);
2452         int c = 0;
2453         bool found = false;
2454         while ((bt = bson_iterator_next(&ait)) != BSON_EOO) {
2455             found = false;
2456             if (ctx->expandall) {
2457                 bson_iterator mitsub;
2458                 BSON_ITERATOR_SUBITERATOR(&mit, &mitsub);
2459                 while ((bt = bson_iterator_next(&mitsub)) != BSON_EOO) {
2460                     if (!bson_compare_it_current(&ait, &mitsub)) {
2461                         found = true;
2462                         break;
2463                     }
2464                 }
2465             } else {
2466                 found = !bson_compare_it_current(&ait, &mit);
2467             }
2468             if (!found) {
2469                 char kbuf[TCNUMBUFSIZ];
2470                 bson_numstrn(kbuf, TCNUMBUFSIZ, c++);
2471                 bson_append_field_from_iterator2(kbuf, &ait, ctx->bsout);
2472             }
2473         }
2474         bson_append_finish_array(ctx->bsout);
2475         return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2476     }
2477     //bt is BSON_OBJECT
2478     if (!after) {
2479         bson_append_start_object(ctx->bsout, key);
2480     } else { //after
2481         bson_append_finish_object(ctx->bsout);
2482     }
2483     return (BSON_VCMD_OK);
2484 }
2485
2486 static bson_visitor_cmd_t _bson_merge_arrays_visitor(
2487                         const char *fpath, int fpathlen,
2488                         const char *key, int keylen,
2489                         const bson_iterator *it,
2490                         bool after, void *op) {
2491
2492     _BSONMARRCTX *ctx = op;
2493     assert(ctx && ctx->mfields >= 0);
2494     bson_iterator mit;
2495     bson_type bt = BSON_ITERATOR_TYPE(it);
2496
2497     if (bt != BSON_OBJECT && bt != BSON_ARRAY) { //trivial case
2498         if (after) {
2499             return (BSON_VCMD_OK);
2500         }
2501         bson_append_field_from_iterator(it, ctx->bsout);
2502         return (BSON_VCMD_SKIP_AFTER);
2503     }
2504     if (bt == BSON_ARRAY) {
2505         if (after) {
2506             bson_append_finish_array(ctx->bsout);
2507             return (BSON_VCMD_OK);
2508         }
2509         BSON_ITERATOR_FROM_BUFFER(&mit, ctx->mbuf);
2510         bt = bson_find_fieldpath_value2(fpath, fpathlen, &mit);
2511         if (bt == BSON_EOO) {
2512             bson_append_start_array(ctx->bsout, key);
2513             return (BSON_VCMD_OK);
2514         }
2515         if (ctx->expandall && bt != BSON_ARRAY) {
2516             bson_append_field_from_iterator(it, ctx->bsout);
2517             return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2518         }
2519         if (ctx->mfields > 0) {
2520             --ctx->mfields;
2521         }
2522         //Find and merge
2523         bson_iterator ait;
2524         BSON_ITERATOR_SUBITERATOR(it, &ait);
2525         bson_append_start_array(ctx->bsout, key);
2526         bool found = false;
2527         int c = 0;
2528         if (ctx->expandall) { //Set of array elements to add
2529             while ((bt = bson_iterator_next(&ait)) != BSON_EOO) { //Flush current array
2530                 bson_append_field_from_iterator(&ait, ctx->bsout);
2531                 ++c;
2532             }
2533             //Iterate over set to add
2534             bson_iterator mitsub;
2535             BSON_ITERATOR_SUBITERATOR(&mit, &mitsub); //mit has BSON_ARRAY type
2536             while ((bt = bson_iterator_next(&mitsub)) != BSON_EOO) {
2537                 found = false;
2538                 if (ctx->mode == BSON_MERGE_ARRAY_ADDSET) {
2539                     BSON_ITERATOR_SUBITERATOR(it, &ait); //Rewind main array iterator
2540                     while ((bt = bson_iterator_next(&ait)) != BSON_EOO) {
2541                         if (!bson_compare_it_current(&ait, &mitsub)) {
2542                             found = true;
2543                             break;
2544                         }
2545                     }
2546                 }
2547                 if (!found) { //Append missing element
2548                     char kbuf[TCNUMBUFSIZ];
2549                     bson_numstrn(kbuf, TCNUMBUFSIZ, c++);
2550                     bson_append_field_from_iterator2(kbuf, &mitsub, ctx->bsout);
2551                     ctx->duty = true;
2552                 }
2553             }
2554         } else { //Single element to add
2555             while ((bt = bson_iterator_next(&ait)) != BSON_EOO) {
2556                 if ((ctx->mode == BSON_MERGE_ARRAY_ADDSET) &&
2557                     !found &&
2558                     !bson_compare_it_current(&ait, &mit)) {
2559                     found = true;
2560                 }
2561                 bson_append_field_from_iterator(&ait, ctx->bsout);
2562                 ++c;
2563             }
2564             if (!found) { //uppend missing element into array
2565                 char kbuf[TCNUMBUFSIZ];
2566                 bson_numstrn(kbuf, TCNUMBUFSIZ, c);
2567                 bson_append_field_from_iterator2(kbuf, &mit, ctx->bsout);
2568                 ctx->duty = true;
2569             }
2570         }
2571         bson_append_finish_array(ctx->bsout);
2572         return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2573     }
2574     //bt is BSON_OBJECT
2575     if (!after) {
2576         bson_append_start_object(ctx->bsout, key);
2577     } else { //after
2578         bson_append_finish_object(ctx->bsout);
2579     }
2580     return (BSON_VCMD_OK);
2581 }
2582
2583 int bson_merge_arrays(const void *mbuf,
2584                       const void *inbuf,
2585                       bson_merge_array_mode mode,
2586                       bool expandall,
2587                       bson *bsout) {
2588
2589     assert(mbuf && inbuf && bsout);
2590     assert(mode == BSON_MERGE_ARRAY_ADDSET ||
2591            mode == BSON_MERGE_ARRAY_PULL ||
2592            mode == BSON_MERGE_ARRAY_PUSH);
2593
2594     if (bsout->finished) {
2595         return BSON_ERROR;
2596     }
2597     _BSONMARRCTX ctx = {
2598         .bsout = bsout,
2599         .mbuf = mbuf,
2600         .mfields = 0,
2601         .duty = false,
2602         .expandall = expandall,
2603         .ecode = BSON_OK,
2604         .mode = mode
2605     };
2606     bson_type bt, bt2;
2607     bson_iterator it, it2;
2608     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2609     while ((bt = bson_iterator_next(&it)) != BSON_EOO) {
2610         if (expandall && bt != BSON_ARRAY) {
2611             continue;
2612         }
2613         ctx.mfields++;
2614     }
2615     BSON_ITERATOR_FROM_BUFFER(&it, inbuf);
2616     if (mode == BSON_MERGE_ARRAY_PULL) {
2617         bson_visit_fields(&it, 0, _bson_merge_arrays_pull_visitor, &ctx);
2618     } else {
2619         bson_visit_fields(&it, 0, _bson_merge_arrays_visitor, &ctx);
2620     }
2621     if (ctx.mfields == 0 || //all fields are merged
2622         mode == BSON_MERGE_ARRAY_PULL) {
2623         return ctx.ecode;
2624     }
2625
2626     //Append missing arrays fields
2627     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2628     while ((bt = bson_iterator_next(&it)) != BSON_EOO) {
2629         const char *fpath = BSON_ITERATOR_KEY(&it);
2630         // all data from inbuf already in bsout
2631         bson_finish(bsout);
2632         BSON_ITERATOR_INIT(&it2, bsout);
2633         bt2 = bson_find_fieldpath_value(fpath, &it2);
2634         if (bt2 != BSON_EOO) continue;
2635         int i = 0;
2636         int lvl = 0;
2637         const char *pdp = fpath;
2638         bson bst;
2639         bson_init(&bst);
2640         while (*(fpath + i) != '\0') {
2641             for (; *(fpath + i) != '\0' && *(fpath + i) != '.'; ++i);
2642             if (*(fpath + i) == '\0') { //EOF
2643                 assert((fpath + i) - pdp > 0);
2644                 bson_append_start_array2(&bst, pdp, (fpath + i) - pdp);
2645                 bson_append_field_from_iterator2("0", &it, &bst);
2646                 bson_append_finish_array(&bst);
2647                 break;
2648             } else {
2649                 ++lvl;
2650                 assert((fpath + i) - pdp > 0);
2651                 bson_append_start_object2(&bst, pdp, (fpath + i) - pdp);
2652             }
2653             pdp = (fpath + i);
2654             while (*pdp == '.') {
2655                 ++pdp;
2656                 ++i;
2657             }
2658         }
2659         for (; lvl > 0; --lvl) {
2660             bson_append_finish_object(&bst);
2661         }
2662         bson_finish(&bst);
2663
2664         bson bsc;
2665         bson_init_finished_data(&bsc, bson_data(bsout));
2666         bson_init_size(bsout, bson_size(bsout));
2667         int res = bson_merge_recursive(&bsc, &bst, false, bsout);
2668         bson_destroy(&bsc);
2669         bson_destroy(&bst);
2670         if (res != BSON_OK) {
2671             return BSON_ERROR;
2672         }
2673     }
2674     return ctx.ecode;
2675 }
2676
2677 typedef struct {
2678     int nlvl; //nesting level
2679     TCXSTR *out; //output buffer
2680 } _BSON2JSONCTX;
2681
2682 static void _jsonxstrescaped(TCXSTR *xstr, const char *str) {
2683     size_t sz = strlen(str);
2684     int s = 0;
2685     int e = 0;
2686     char hb[7];
2687     hb[0] = '\\';
2688     hb[1] = 'u';
2689     hb[2] = '0';
2690     hb[3] = '0';
2691     hb[6] = '\0';
2692     while (e < sz) {
2693         const char * ebuf = NULL;
2694         switch (str[e]) {
2695             case '\r': ebuf = "\\r";
2696                 break;
2697             case '\n': ebuf = "\\n";
2698                 break;
2699             case '\\': ebuf = "\\\\";
2700                 break;
2701             case '/':
2702                 break;
2703             case '"': ebuf = "\\\"";
2704                 break;
2705             case '\f': ebuf = "\\f";
2706                 break;
2707             case '\b': ebuf = "\\b";
2708                 break;
2709             case '\t': ebuf = "\\t";
2710                 break;
2711             default:
2712                 if ((unsigned char) str[e] < 0x20) {
2713                     static const char *hexchar = "0123456789ABCDEF";
2714                     hb[4] = hexchar[str[e] >> 4];
2715                     hb[5] = hexchar[str[e] & 0x0F];
2716                     ebuf = hb;
2717                 }
2718                 break;
2719         }
2720         if (ebuf != NULL) {
2721             if (e > s) {
2722                 tcxstrcat(xstr, str + s, e - s);
2723             }
2724             tcxstrcat2(xstr, ebuf);
2725             s = ++e;
2726         } else {
2727             ++e;
2728         }
2729     }
2730     tcxstrcat(xstr, (str + s), e - s);
2731 }
2732
2733 static int _bson2json(_BSON2JSONCTX *ctx, bson_iterator *it, bool array) {
2734
2735 #define BSPAD(_n) \
2736     for (int i = 0; i < ctx->nlvl + (_n); ++i) tcxstrcat2(ctx->out, " ")
2737
2738     bson_type bt;
2739     TCXSTR *out = ctx->out;
2740     tcxstrcat2(ctx->out, array ? "[\n" : "{\n");
2741     ctx->nlvl += 4;
2742     int c = 0;
2743     while ((bt = bson_iterator_next(it)) != BSON_EOO) {
2744         if (c++ > 0) {
2745             if (array) {
2746                 tcxstrcat2(out, "\n");
2747                 BSPAD(0);
2748             }
2749             tcxstrcat2(out, ",\n");
2750         }
2751         const char *key = BSON_ITERATOR_KEY(it);
2752         BSPAD(0);
2753         if (!array) {
2754             tcxstrcat2(out, "\"");
2755             _jsonxstrescaped(out, key);
2756             tcxstrcat2(out, "\" : ");
2757         }
2758
2759         switch (bt) {
2760             case BSON_LONG:
2761             case BSON_INT:
2762                 tcxstrprintf(out, "%" PRId64, (int64_t) bson_iterator_long_ext(it));
2763                 break;
2764             case BSON_DOUBLE:
2765             {
2766                 tcxstrprintf(out, "%lf", bson_iterator_double(it));
2767                 break;
2768             }
2769             case BSON_STRING:
2770             case BSON_SYMBOL:
2771             {
2772                 tcxstrcat2(out, "\"");
2773                 _jsonxstrescaped(out, bson_iterator_string(it));
2774                 tcxstrcat2(out, "\"");
2775                 break;
2776             }
2777             case BSON_OBJECT:
2778             case BSON_ARRAY:
2779             {
2780                 bson_iterator sit;
2781                 BSON_ITERATOR_SUBITERATOR(it, &sit);
2782                 _bson2json(ctx, &sit, bt == BSON_ARRAY);
2783                 break;
2784             }
2785             case BSON_NULL:
2786                 tcxstrcat2(out, "null");
2787             case BSON_UNDEFINED:
2788                 break;
2789             case BSON_DATE:
2790             {
2791                 bson_date_t t = bson_iterator_date(it);
2792                 char dbuf[49];
2793                 tcdatestrwww(t, INT_MAX, dbuf);
2794                 tcxstrprintf(out, "\"%s\"", dbuf);
2795                 break;
2796             }
2797             case BSON_BOOL:
2798                 tcxstrcat2(out, bson_iterator_bool(it) ? "true" : "false");
2799                 break;
2800             case BSON_OID:
2801             {
2802                 char xoid[25];
2803                 bson_oid_t *oid = bson_iterator_oid(it);
2804                 bson_oid_to_string(oid, xoid);
2805                 tcxstrprintf(out, "\"%s\"", xoid);
2806                 break;
2807             }
2808             case BSON_REGEX:
2809             {
2810                 tcxstrcat2(out, "\"");
2811                 _jsonxstrescaped(out, bson_iterator_regex(it));
2812                 tcxstrcat2(out, "\"");
2813                 break;
2814             }
2815             case BSON_BINDATA:
2816             {
2817                 const char *buf = bson_iterator_bin_data(it);
2818                 int bsz = bson_iterator_bin_len(it);
2819                 char *b64data = tcbaseencode(buf, bsz);
2820                 tcxstrcat2(out, "\"");
2821                 tcxstrcat2(out, b64data);
2822                 tcxstrcat2(out, "\"");
2823                 TCFREE(b64data);
2824                 break;
2825             }
2826             default:
2827                 break;
2828         }
2829     }
2830     tcxstrcat2(out, "\n");
2831     BSPAD(-4);
2832     tcxstrcat2(out, array ? "]" : "}");
2833     ctx->nlvl -= 4;
2834     return 0;
2835 #undef BSPAD
2836 }
2837
2838 int bson2json(const char *bsdata, char **buf, int *sp) {
2839     assert(bsdata && buf && sp);
2840     bson_iterator it;
2841     BSON_ITERATOR_FROM_BUFFER(&it, bsdata);
2842     TCXSTR *out = tcxstrnew();
2843     _BSON2JSONCTX ctx = {
2844         .nlvl = 0,
2845         .out = out
2846     };
2847     int ret = _bson2json(&ctx, &it, false);
2848     if (ret == BSON_OK) {
2849         *sp = TCXSTRSIZE(out);
2850         *buf = tcxstrtomalloc(out);
2851     } else {
2852         *sp = 0;
2853         *buf = NULL;
2854         tcxstrclear(out);
2855     }
2856     return ret;
2857 }
2858
2859
2860 #include "nxjson.h"
2861
2862 static void _json2bson(bson *out, const nx_json *json, const char *forcekey) {
2863     const char *key =  forcekey ? forcekey : json->key;
2864     switch (json->type) {
2865         case NX_JSON_NULL:
2866             assert(key);
2867             bson_append_null(out, key);
2868             break;
2869         case NX_JSON_OBJECT:
2870         {
2871             if (key) {
2872                 bson_append_start_object(out, key);
2873             }
2874             for (nx_json* js = json->child; js; js = js->next) {
2875                 _json2bson(out, js, NULL);
2876             }
2877             if (key) {
2878                 bson_append_finish_object(out);
2879             }
2880             break;
2881         }
2882         case NX_JSON_ARRAY:
2883         {
2884             if (key) {
2885                 bson_append_start_array(out, key);
2886             }
2887             int c = 0;
2888             char kbuf[TCNUMBUFSIZ];
2889             for (nx_json* js = json->child; js; js = js->next) {
2890                  bson_numstrn(kbuf, TCNUMBUFSIZ, c++);
2891                 _json2bson(out, js, kbuf);
2892             }
2893             if (key) {
2894                 bson_append_finish_array(out);
2895             }
2896             break;
2897         }
2898         case NX_JSON_STRING:
2899             assert(key);
2900             bson_append_string(out, key, json->text_value);
2901             break;
2902         case NX_JSON_INTEGER:
2903             assert(key);
2904             if (json->int_value <= INT_MAX && json->int_value >= INT_MIN) {
2905                 bson_append_int(out, key, (int) json->int_value);
2906             } else {
2907                 bson_append_long(out, key, json->int_value);
2908             }
2909             break;
2910         case NX_JSON_DOUBLE:
2911             assert(key);
2912             bson_append_double(out, key, json->dbl_value);
2913             break;
2914         case NX_JSON_BOOL:
2915             assert(key);
2916             bson_append_bool(out, key, json->int_value ? true : false);
2917             break;
2918         default:
2919             break;
2920     }
2921 }
2922
2923 bson* json2bson(const char *jsonstr) {
2924     bool err = false;
2925     bson *out = NULL;
2926     char *json = strdup(jsonstr); //nxjson uses inplace data modification
2927     if (!json) {
2928         return NULL;
2929     }
2930     out = bson_create();
2931     bson_init_as_query(out);
2932     const nx_json *nxjson = nx_json_parse_utf8(json);
2933     if (!nxjson) {
2934         err = true;
2935         goto finish;
2936     }
2937     _json2bson(out, nxjson, NULL);
2938     bson_finish(out);
2939     err = out->err;
2940 finish:
2941     free(json);
2942     if (nxjson) {
2943         nx_json_free(nxjson);
2944     }
2945     if (err && out) {
2946         bson_del(out);
2947         out = NULL;
2948     }
2949     return out;
2950 }
2951
2952
2953 typedef struct {
2954     bson *bs;
2955     bool checkdots;
2956     bool checkdollar;
2957 } _BSONVALIDATECTX;
2958
2959 static bson_visitor_cmd_t _bson_validate_visitor(
2960         const char *ipath, int ipathlen,
2961         const char *key, int keylen,
2962         const bson_iterator *it,
2963         bool after, void *op) {
2964     _BSONVALIDATECTX *ctx = op;
2965     assert(ctx);
2966     if (bson_check_field_name(ctx->bs, key, keylen,
2967                               ctx->checkdots, ctx->checkdollar) == BSON_ERROR) {
2968         return BSON_VCMD_TERMINATE;
2969     }
2970     return (BSON_VCMD_OK | BSON_VCMD_SKIP_AFTER);
2971 }
2972
2973
2974 int bson_validate(bson *bs, bool checkdots, bool checkdollar) {
2975     if (!bs) {
2976         return BSON_ERROR;
2977     }
2978     if (!bs->finished) {
2979         bs->err |= BSON_NOT_FINISHED;
2980         return BSON_ERROR;
2981     }
2982     bson_iterator it;
2983     bson_iterator_init(&it, bs);
2984     _BSONVALIDATECTX ctx = {
2985         .bs = bs,
2986         .checkdots = checkdots,
2987         .checkdollar = checkdollar
2988     };
2989     bson_visit_fields(&it, BSON_TRAVERSE_ARRAYS_EXCLUDED, _bson_validate_visitor, &ctx);
2990     return bs->err ? BSON_ERROR : BSON_OK;
2991 }
2992