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