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     if (b->err & BSON_NOT_UTF8)
 903         return BSON_ERROR;
 904     if (!b->finished) {
 905         if (bson_ensure_space(b, 1) == BSON_ERROR) return BSON_ERROR;
 906         bson_append_byte(b, 0);
 907         i = b->cur - b->data;
 908         bson_little_endian32(b->data, &i);
 909         b->finished = 1;
 910     }
 911     return BSON_OK;
 912 }
 913
 914 void bson_destroy(bson *b) {
 915     if (b) {
 916         if (b->data && !(b->flags & BSON_FLAG_STACK_ALLOCATED)) {
 917             bson_free(b->data);
 918         }
 919         b->err = 0;
 920         b->data = 0;
 921         b->cur = 0;
 922         b->finished = 1;
 923         if (b->errstr) {
 924             bson_free_func(b->errstr);
 925             b->errstr = NULL;
 926         }
 927     }
 928 }
 929
 930 void bson_del(bson *b) {
 931     if (b) {
 932         bson_destroy(b);
 933         bson_free(b);
 934     }
 935 }
 936
 937 static int bson_append_estart2(bson *b, int type, const char *name, int namelen, const int dataSize);
 938
 939 static int bson_append_estart(bson *b, int type, const char *name, const int dataSize) {
 940     return bson_append_estart2(b, type, name, strlen(name), dataSize);
 941 }
 942
 943 static int bson_append_estart2(bson *b, int type, const char *name, int namelen, const int dataSize) {
 944     const int len = namelen + 1;
 945
 946     if (b->finished) {
 947         b->err |= BSON_ALREADY_FINISHED;
 948         return BSON_ERROR;
 949     }
 950
 951     if (bson_ensure_space(b, 1 + len + dataSize) == BSON_ERROR) {
 952         return BSON_ERROR;
 953     }
 954
 955     if (bson_check_field_name(b, (const char *) name, namelen,
 956             !(b->flags & BSON_FLAG_QUERY_MODE), !(b->flags & BSON_FLAG_QUERY_MODE)) == BSON_ERROR) {
 957         bson_builder_error(b);
 958         return BSON_ERROR;
 959     }
 960     bson_append_byte(b, (char) type);
 961     memcpy(b->cur, name, namelen);
 962     b->cur += namelen;
 963     *(b->cur) = '\0';
 964     b->cur += 1;
 965     return BSON_OK;
 966 }
 967
 968 /* ----------------------------
 969    BUILDING TYPES
 970    ------------------------------ */
 971
 972 int bson_append_int(bson *b, const char *name, const int i) {
 973     if (bson_append_estart(b, BSON_INT, name, 4) == BSON_ERROR)
 974         return BSON_ERROR;
 975     bson_append32(b, &i);
 976     return BSON_OK;
 977 }
 978
 979 int bson_append_long(bson *b, const char *name, const int64_t i) {
 980     if (bson_append_estart(b, BSON_LONG, name, 8) == BSON_ERROR)
 981         return BSON_ERROR;
 982     bson_append64(b, &i);
 983     return BSON_OK;
 984 }
 985
 986 int bson_append_double(bson *b, const char *name, const double d) {
 987     if (bson_append_estart(b, BSON_DOUBLE, name, 8) == BSON_ERROR)
 988         return BSON_ERROR;
 989     bson_append64(b, &d);
 990     return BSON_OK;
 991 }
 992
 993 int bson_append_bool(bson *b, const char *name, const bson_bool_t i) {
 994     if (bson_append_estart(b, BSON_BOOL, name, 1) == BSON_ERROR)
 995         return BSON_ERROR;
 996     bson_append_byte(b, i != 0);
 997     return BSON_OK;
 998 }
 999
1000 int bson_append_null(bson *b, const char *name) {
1001     if (bson_append_estart(b, BSON_NULL, name, 0) == BSON_ERROR)
1002         return BSON_ERROR;
1003     return BSON_OK;
1004 }
1005
1006 int bson_append_undefined(bson *b, const char *name) {
1007     if (bson_append_estart(b, BSON_UNDEFINED, name, 0) == BSON_ERROR)
1008         return BSON_ERROR;
1009     return BSON_OK;
1010 }
1011
1012 int bson_append_string_base(bson *b, const char *name,
1013         const char *value, int len, bson_type type) {
1014
1015     int sl = len + 1;
1016     if (bson_check_string(b, (const char *) value, sl - 1) == BSON_ERROR)
1017         return BSON_ERROR;
1018     if (bson_append_estart(b, type, name, 4 + sl) == BSON_ERROR) {
1019         return BSON_ERROR;
1020     }
1021     bson_append32(b, &sl);
1022     bson_append(b, value, sl - 1);
1023     bson_append(b, "\0", 1);
1024     return BSON_OK;
1025 }
1026
1027 int bson_append_string(bson *b, const char *name, const char *value) {
1028     return bson_append_string_base(b, name, value, strlen(value), BSON_STRING);
1029 }
1030
1031 int bson_append_symbol(bson *b, const char *name, const char *value) {
1032     return bson_append_string_base(b, name, value, strlen(value), BSON_SYMBOL);
1033 }
1034
1035 int bson_append_code(bson *b, const char *name, const char *value) {
1036     return bson_append_string_base(b, name, value, strlen(value), BSON_CODE);
1037 }
1038
1039 int bson_append_string_n(bson *b, const char *name, const char *value, int len) {
1040     return bson_append_string_base(b, name, value, len, BSON_STRING);
1041 }
1042
1043 int bson_append_symbol_n(bson *b, const char *name, const char *value, int len) {
1044     return bson_append_string_base(b, name, value, len, BSON_SYMBOL);
1045 }
1046
1047 int bson_append_code_n(bson *b, const char *name, const char *value, int len) {
1048     return bson_append_string_base(b, name, value, len, BSON_CODE);
1049 }
1050
1051 int bson_append_code_w_scope_n(bson *b, const char *name,
1052         const char *code, int len, const bson *scope) {
1053
1054     int sl, size;
1055     if (!scope) return BSON_ERROR;
1056     sl = len + 1;
1057     size = 4 + 4 + sl + bson_size(scope);
1058     if (bson_append_estart(b, BSON_CODEWSCOPE, name, size) == BSON_ERROR)
1059         return BSON_ERROR;
1060     bson_append32(b, &size);
1061     bson_append32(b, &sl);
1062     bson_append(b, code, sl);
1063     bson_append(b, scope->data, bson_size(scope));
1064     return BSON_OK;
1065 }
1066
1067 int bson_append_code_w_scope(bson *b, const char *name, const char *code, const bson *scope) {
1068     return bson_append_code_w_scope_n(b, name, code, strlen(code), scope);
1069 }
1070
1071 int bson_append_binary(bson *b, const char *name, char type, const char *str, int len) {
1072     if (type == BSON_BIN_BINARY_OLD) {
1073         int subtwolen = len + 4;
1074         if (bson_append_estart(b, BSON_BINDATA, name, 4 + 1 + 4 + len) == BSON_ERROR)
1075             return BSON_ERROR;
1076         bson_append32(b, &subtwolen);
1077         bson_append_byte(b, type);
1078         bson_append32(b, &len);
1079         bson_append(b, str, len);
1080     } else {
1081         if (bson_append_estart(b, BSON_BINDATA, name, 4 + 1 + len) == BSON_ERROR)
1082             return BSON_ERROR;
1083         bson_append32(b, &len);
1084         bson_append_byte(b, type);
1085         bson_append(b, str, len);
1086     }
1087     return BSON_OK;
1088 }
1089
1090 int bson_append_oid(bson *b, const char *name, const bson_oid_t *oid) {
1091     if (bson_append_estart(b, BSON_OID, name, 12) == BSON_ERROR)
1092         return BSON_ERROR;
1093     bson_append(b, oid, 12);
1094     return BSON_OK;
1095 }
1096
1097 int bson_append_new_oid(bson *b, const char *name) {
1098     bson_oid_t oid;
1099     bson_oid_gen(&oid);
1100     return bson_append_oid(b, name, &oid);
1101 }
1102
1103 int bson_append_regex(bson *b, const char *name, const char *pattern, const char *opts) {
1104     const int plen = strlen(pattern) + 1;
1105     const int olen = strlen(opts) + 1;
1106     if (bson_append_estart(b, BSON_REGEX, name, plen + olen) == BSON_ERROR)
1107         return BSON_ERROR;
1108     if (bson_check_string(b, pattern, plen - 1) == BSON_ERROR)
1109         return BSON_ERROR;
1110     bson_append(b, pattern, plen);
1111     bson_append(b, opts, olen);
1112     return BSON_OK;
1113 }
1114
1115 int bson_append_bson(bson *b, const char *name, const bson *bson) {
1116     if (!bson) return BSON_ERROR;
1117     if (bson_append_estart(b, BSON_OBJECT, name, bson_size(bson)) == BSON_ERROR)
1118         return BSON_ERROR;
1119     bson_append(b, bson->data, bson_size(bson));
1120     return BSON_OK;
1121 }
1122
1123 int bson_append_element(bson *b, const char *name_or_null, const bson_iterator *elem) {
1124     bson_iterator next = *elem;
1125     int size;
1126
1127     bson_iterator_next(&next);
1128     size = next.cur - elem->cur;
1129
1130     if (name_or_null == NULL) {
1131         if (bson_ensure_space(b, size) == BSON_ERROR)
1132             return BSON_ERROR;
1133         bson_append(b, elem->cur, size);
1134     } else {
1135         int data_size = size - 2 - strlen(BSON_ITERATOR_KEY(elem));
1136         bson_append_estart(b, elem->cur[0], name_or_null, data_size);
1137         bson_append(b, bson_iterator_value(elem), data_size);
1138     }
1139
1140     return BSON_OK;
1141 }
1142
1143 int bson_append_timestamp(bson *b, const char *name, bson_timestamp_t *ts) {
1144     if (bson_append_estart(b, BSON_TIMESTAMP, name, 8) == BSON_ERROR) return BSON_ERROR;
1145
1146     bson_append32(b, &(ts->i));
1147     bson_append32(b, &(ts->t));
1148
1149     return BSON_OK;
1150 }
1151
1152 int bson_append_timestamp2(bson *b, const char *name, int time, int increment) {
1153     if (bson_append_estart(b, BSON_TIMESTAMP, name, 8) == BSON_ERROR) return BSON_ERROR;
1154
1155     bson_append32(b, &increment);
1156     bson_append32(b, &time);
1157     return BSON_OK;
1158 }
1159
1160 int bson_append_date(bson *b, const char *name, bson_date_t millis) {
1161     if (bson_append_estart(b, BSON_DATE, name, 8) == BSON_ERROR) return BSON_ERROR;
1162     bson_append64(b, &millis);
1163     return BSON_OK;
1164 }
1165
1166 int bson_append_time_t(bson *b, const char *name, time_t secs) {
1167     return bson_append_date(b, name, (bson_date_t) secs * 1000);
1168 }
1169
1170 int bson_append_start_object(bson *b, const char *name) {
1171     if (bson_append_estart(b, BSON_OBJECT, name, 5) == BSON_ERROR) return BSON_ERROR;
1172     b->stack[ b->stackPos++ ] = b->cur - b->data;
1173     bson_append32(b, &zero);
1174     return BSON_OK;
1175 }
1176
1177 int bson_append_start_object2(bson *b, const char *name, int namelen) {
1178     if (bson_append_estart2(b, BSON_OBJECT, name, namelen, 5) == BSON_ERROR) return BSON_ERROR;
1179     b->stack[ b->stackPos++ ] = b->cur - b->data;
1180     bson_append32(b, &zero);
1181     return BSON_OK;
1182 }
1183
1184 int bson_append_start_array(bson *b, const char *name) {
1185     return bson_append_start_array2(b, name, strlen(name));
1186 }
1187
1188 int bson_append_start_array2(bson *b, const char *name, int namelen) {
1189     if (bson_append_estart2(b, BSON_ARRAY, name, namelen, 5) == BSON_ERROR) return BSON_ERROR;
1190     b->stack[ b->stackPos++ ] = b->cur - b->data;
1191     bson_append32(b, &zero);
1192     return BSON_OK;
1193 }
1194
1195 int bson_append_finish_object(bson *b) {
1196     char *start;
1197     int i;
1198     if (bson_ensure_space(b, 1) == BSON_ERROR) return BSON_ERROR;
1199     bson_append_byte(b, 0);
1200
1201     start = b->data + b->stack[ --b->stackPos ];
1202     i = b->cur - start;
1203     bson_little_endian32(start, &i);
1204
1205     return BSON_OK;
1206 }
1207
1208 double bson_int64_to_double(int64_t i64) {
1209     return (double) i64;
1210 }
1211
1212 int bson_append_finish_array(bson *b) {
1213     return bson_append_finish_object(b);
1214 }
1215
1216 /* Error handling and allocators. */
1217
1218 static bson_err_handler err_handler = NULL;
1219
1220 bson_err_handler set_bson_err_handler(bson_err_handler func) {
1221     bson_err_handler old = err_handler;
1222     err_handler = func;
1223     return old;
1224 }
1225
1226 void bson_free(void *ptr) {
1227     bson_free_func(ptr);
1228 }
1229
1230 void *bson_malloc(int size) {
1231     void *p;
1232     p = bson_malloc_func(size);
1233     bson_fatal_msg(!!p, "malloc() failed");
1234     return p;
1235 }
1236
1237 void *bson_realloc(void *ptr, int size) {
1238     void *p;
1239     p = bson_realloc_func(ptr, size);
1240     bson_fatal_msg(!!p, "realloc() failed");
1241     return p;
1242 }
1243
1244 int _bson_errprintf(const char *format, ...) {
1245     va_list ap;
1246     int ret;
1247     va_start(ap, format);
1248     ret = vfprintf(stderr, format, ap);
1249     va_end(ap);
1250     return ret;
1251 }
1252
1253 /**
1254  * This method is invoked when a non-fatal bson error is encountered.
1255  * Calls the error handler if available.
1256  *
1257  *  @param
1258  */
1259 void bson_builder_error(bson *b) {
1260     if (err_handler)
1261         err_handler("BSON error.");
1262 }
1263
1264 void bson_fatal(int ok) {
1265     bson_fatal_msg(ok, "");
1266 }
1267
1268 void bson_fatal_msg(int ok, const char *msg) {
1269     if (ok)
1270         return;
1271
1272     if (err_handler) {
1273         err_handler(msg);
1274     }
1275     bson_errprintf("error: %s\n", msg);
1276 }
1277
1278
1279 /* Efficiently copy an integer to a string. */
1280 extern const char bson_numstrs[1000][4];
1281
1282 void bson_numstr(char *str, int64_t i) {
1283     if (i >= 0 && i < 1000)
1284         memcpy(str, bson_numstrs[i], 4);
1285     else
1286         sprintf(str, "%" PRId64 "", (int64_t) i);
1287 }
1288
1289 #pragma GCC diagnostic push
1290 #pragma GCC diagnostic ignored "-Wformat"
1291
1292 int bson_numstrn(char *str, int maxbuf, int64_t i) {
1293     if (i >= 0 && i < 1000 && maxbuf > 4) {
1294         memcpy(str, bson_numstrs[i], 4);
1295         return strlen(bson_numstrs[i]);
1296     } else {
1297         return snprintf(str, maxbuf, "%" PRId64 "", (int64_t) i);
1298     }
1299 }
1300 #pragma GCC diagnostic pop
1301
1302 static bson_bool_t bson_isnumstr(const char *str, int len) {
1303     assert(str);
1304     bool isnum = false;
1305     while (len > 0 && *str > '\0' && *str <= ' ') {
1306         str++;
1307         len--;
1308     }
1309     while (len > 0 && *str >= '0' && *str <= '9') {
1310         isnum = true;
1311         str++;
1312         len--;
1313     }
1314     while (len > 0 && *str > '\0' && *str <= ' ') {
1315         str++;
1316         len--;
1317     }
1318     return (isnum && (*str == '\0' || len == 0));
1319 }
1320
1321 void bson_swap_endian64(void *outp, const void *inp) {
1322     const char *in = (const char *) inp;
1323     char *out = (char *) outp;
1324     out[0] = in[7];
1325     out[1] = in[6];
1326     out[2] = in[5];
1327     out[3] = in[4];
1328     out[4] = in[3];
1329     out[5] = in[2];
1330     out[6] = in[1];
1331     out[7] = in[0];
1332
1333 }
1334
1335 void bson_swap_endian32(void *outp, const void *inp) {
1336     const char *in = (const char *) inp;
1337     char *out = (char *) outp;
1338     out[0] = in[3];
1339     out[1] = in[2];
1340     out[2] = in[1];
1341     out[3] = in[0];
1342 }
1343
1344 static const char *bson_iterator_value2(const bson_iterator *i, int *klen) {
1345     const char *t = i->cur + 1;
1346     *klen = strlen(t);
1347     t += (*klen + 1);
1348     return t;
1349 }
1350
1351 int bson_append_array_from_iterator(const char *key, bson_iterator *from, bson *into) {
1352     assert(key && from && into);
1353     bson_type bt;
1354     bson_append_start_array(into, key);
1355     while ((bt = bson_iterator_next(from)) != BSON_EOO) {
1356         bson_append_field_from_iterator(from, into);
1357     }
1358     bson_append_finish_array(into);
1359     return BSON_OK;
1360 }
1361
1362 int bson_append_object_from_iterator(const char *key, bson_iterator *from, bson *into) {
1363     assert(key && from && into);
1364     bson_type bt;
1365     bson_append_start_object(into, key);
1366     while ((bt = bson_iterator_next(from)) != BSON_EOO) {
1367         bson_append_field_from_iterator(from, into);
1368     }
1369     bson_append_finish_object(into);
1370     return BSON_OK;
1371 }
1372
1373 static void bson_append_fpath_from_iterator(const char *fpath, const bson_iterator *from, bson *into) {
1374     char key[BSON_MAX_FPATH_LEN + 1];
1375     int fplen = strlen(fpath);
1376     if (fplen >= BSON_MAX_FPATH_LEN) { //protect me silently
1377         return; //todo error?
1378     }
1379     const char *fp = fpath;
1380     int keylen = 0;
1381     int nl = 0; //nesting level
1382     while (fplen > 0) { //split fpath with '.' delim
1383         const char *rp = fp;
1384         const char *ep = fp + fplen;
1385         while (rp < ep) {
1386             if (*rp == '.') break;
1387             rp++;
1388         }
1389         keylen = (rp - fp);
1390         memcpy(key, fp, keylen);
1391         key[keylen] = '\0';
1392         rp++;
1393         fplen -= keylen;
1394         if (fplen <= 0) { //last part of fp
1395             bson_append_field_from_iterator2(key, from, into);
1396             while (nl-- > 0) {
1397                 bson_append_finish_object(into); //arrays are covered also
1398             }
1399         } else { //intermediate part
1400             if (bson_isnumstr(key, keylen)) {
1401                 nl++;
1402                 bson_append_start_array2(into, key, keylen);
1403             } else {
1404                 nl++;
1405                 bson_append_start_object2(into, key, keylen);
1406             }
1407         }
1408         fp = rp;
1409     }
1410 }
1411
1412 int bson_append_field_from_iterator2(const char *key, const bson_iterator *from, bson *into) {
1413     assert(key && from && into);
1414     bson_type t = BSON_ITERATOR_TYPE(from);
1415     if (t == BSON_EOO || into->finished) {
1416         return BSON_ERROR;
1417     }
1418     switch (t) {
1419         case BSON_STRING:
1420         case BSON_SYMBOL:
1421             bson_append_string(into, key, bson_iterator_string(from));
1422             break;
1423         case BSON_CODE:
1424             bson_append_code(into, key, bson_iterator_code(from));
1425             break;
1426         case BSON_INT:
1427             bson_append_int(into, key, bson_iterator_int_raw(from));
1428             break;
1429         case BSON_DOUBLE:
1430             bson_append_double(into, key, bson_iterator_double_raw(from));
1431             break;
1432         case BSON_LONG:
1433             bson_append_long(into, key, bson_iterator_long_raw(from));
1434             break;
1435         case BSON_UNDEFINED:
1436             bson_append_undefined(into, key);
1437             break;
1438         case BSON_NULL:
1439             bson_append_null(into, key);
1440             break;
1441         case BSON_BOOL:
1442             bson_append_bool(into, key, bson_iterator_bool_raw(from));
1443             break;
1444         case BSON_TIMESTAMP:
1445         {
1446             bson_timestamp_t ts = bson_iterator_timestamp(from);
1447             bson_append_timestamp(into, key, &ts);
1448             break;
1449         }
1450         case BSON_DATE:
1451             bson_append_date(into, key, bson_iterator_date(from));
1452             break;
1453         case BSON_REGEX:
1454             bson_append_regex(into, key, bson_iterator_regex(from), bson_iterator_regex_opts(from));
1455             break;
1456         case BSON_OID:
1457             bson_append_oid(into, key, bson_iterator_oid(from));
1458             break;
1459         case BSON_OBJECT:
1460         {
1461             bson_iterator sit;
1462             BSON_ITERATOR_SUBITERATOR(from, &sit);
1463             bson_append_start_object(into, key);
1464             while (bson_iterator_next(&sit) != BSON_EOO) {
1465                 bson_append_field_from_iterator(&sit, into);
1466             }
1467             bson_append_finish_object(into);
1468             break;
1469         }
1470         case BSON_ARRAY:
1471         {
1472             bson_iterator sit;
1473             BSON_ITERATOR_SUBITERATOR(from, &sit);
1474             bson_append_start_array(into, key);
1475             while (bson_iterator_next(&sit) != BSON_EOO) {
1476                 bson_append_field_from_iterator(&sit, into);
1477             }
1478             bson_append_finish_array(into);
1479             break;
1480         }
1481         case BSON_DBREF:
1482         case BSON_CODEWSCOPE:
1483             break;
1484         default:
1485             break;
1486     }
1487     return BSON_OK;
1488 }
1489
1490 int bson_append_field_from_iterator(const bson_iterator *from, bson *into) {
1491     assert(from && into);
1492     return bson_append_field_from_iterator2(BSON_ITERATOR_KEY(from), from, into);
1493 }
1494
1495 typedef struct {
1496     bson *bsout;
1497     TCMAP *mfields;
1498     const void *bsdata2; //bsdata to merge with
1499     int nstack; //nested object stack pos
1500     int matched; //number of matched merge fields
1501 } _BSONMERGE3CTX;
1502
1503 static bson_visitor_cmd_t _bson_merge3_visitor(const char *ipath, int ipathlen, const char *key, int keylen,
1504         const bson_iterator *it, bool after, void *op) {
1505     _BSONMERGE3CTX *ctx = op;
1506     assert(ctx && ctx->bsout && ctx->mfields && ipath && key && it && op);
1507     const void *buf;
1508     const char *mpath;
1509     int bufsz;
1510     bson_type bt = BSON_ITERATOR_TYPE(it);
1511     buf = (TCMAPRNUM(ctx->mfields) == 0 || after) ? NULL : tcmapget(ctx->mfields, ipath, ipathlen, &bufsz);
1512     if (buf) {
1513         bson_iterator it2;
1514         BSON_ITERATOR_FROM_BUFFER(&it2, ctx->bsdata2);
1515         off_t it2off;
1516         assert(bufsz == sizeof (it2off));
1517         memcpy(&it2off, buf, sizeof (it2off));
1518         assert(it2off >= 0);
1519         it2.cur = it2.cur + it2off;
1520         it2.first = (it2off == 0);
1521         tcmapout(ctx->mfields, ipath, ipathlen);
1522         bson_append_field_from_iterator2(key, &it2, ctx->bsout);
1523         return (BSON_VCMD_SKIP_AFTER | BSON_VCMD_SKIP_NESTED);
1524     } else {
1525         if (bt == BSON_OBJECT || bt == BSON_ARRAY) {
1526             if (!after) {
1527                 ctx->nstack++;
1528                 if (bt == BSON_OBJECT) {
1529                     bson_append_start_object2(ctx->bsout, key, keylen);
1530                 } else if (bt == BSON_ARRAY) {
1531                     bson_append_start_array2(ctx->bsout, key, keylen);
1532                 }
1533                 return BSON_VCMD_OK;
1534             } else {
1535                 if (ctx->nstack > 0) {
1536                     //do we have something to add into end of nested object?
1537                     tcmapiterinit(ctx->mfields);
1538                     int mpathlen = 0;
1539                     while ((mpath = tcmapiternext(ctx->mfields, &mpathlen)) != NULL) {
1540                         int i = 0;
1541                         for (; i < ipathlen && *(mpath + i) == *(ipath + i); ++i);
1542                         if (i == ipathlen && *(mpath + i) == '.' && *(mpath + i + 1) != '\0') { //ipath prefixed
1543                             bson_iterator it2;
1544                             BSON_ITERATOR_FROM_BUFFER(&it2, ctx->bsdata2);
1545                             buf = tcmapget(ctx->mfields, mpath, mpathlen, &bufsz);
1546                             off_t it2off;
1547                             assert(bufsz == sizeof (it2off));
1548                             memcpy(&it2off, buf, sizeof (it2off));
1549                             assert(it2off >= 0);
1550                             it2.cur = it2.cur + it2off;
1551                             it2.first = (it2off == 0);
1552                             bson_append_fpath_from_iterator(mpath + i + 1, &it2, ctx->bsout);
1553                             tcmapout(ctx->mfields, mpath, mpathlen);
1554                         }
1555                     }
1556                     ctx->nstack--;
1557                     if (bt == BSON_OBJECT) {
1558                         bson_append_finish_object(ctx->bsout);
1559                     } else if (bt == BSON_ARRAY) {
1560                         bson_append_finish_array(ctx->bsout);
1561                     }
1562                 }
1563                 return BSON_VCMD_OK;
1564             }
1565         } else {
1566             bson_append_field_from_iterator(it, ctx->bsout);
1567             return BSON_VCMD_SKIP_AFTER;
1568         }
1569     }
1570 }
1571
1572 //merge with fpath support
1573
1574 int bson_merge3(const void *bsdata1, const void *bsdata2, bson *out) {
1575     assert(bsdata1 && bsdata2 && out);
1576     bson_iterator it1, it2;
1577     bson_type bt;
1578     BSON_ITERATOR_FROM_BUFFER(&it1, bsdata1);
1579     BSON_ITERATOR_FROM_BUFFER(&it2, bsdata2);
1580     const char *it2start = it2.cur;
1581     TCMAP *mfields = tcmapnew2(TCMAPTINYBNUM);
1582     _BSONMERGE3CTX ctx = {
1583         .bsout = out,
1584         .mfields = mfields,
1585         .bsdata2 = bsdata2,
1586         .matched = 0,
1587         .nstack = 0
1588     };
1589     //collect active fpaths
1590     while ((bt = bson_iterator_next(&it2)) != BSON_EOO) {
1591         const char* key = BSON_ITERATOR_KEY(&it2);
1592         off_t it2off = (it2.cur - it2start);
1593         tcmapput(mfields, key, strlen(key), &it2off, sizeof (it2off));
1594     }
1595     bson_visit_fields(&it1, 0, _bson_merge3_visitor, &ctx);
1596     assert(ctx.nstack == 0);
1597     if (TCMAPRNUM(mfields) == 0) { //all merge fields applied
1598         tcmapdel(mfields);
1599         return BSON_OK;
1600     }
1601
1602     //apply the remaining merge fields
1603     tcmapiterinit(mfields);
1604     const char *fpath;
1605     int fplen;
1606     while ((fpath = tcmapiternext(mfields, &fplen)) != NULL) {
1607         BSON_ITERATOR_FROM_BUFFER(&it2, bsdata2);
1608         if (bson_find_fieldpath_value2(fpath, fplen, &it2) != BSON_EOO) {
1609             bson_append_fpath_from_iterator(fpath, &it2, out);
1610         }
1611     }
1612     tcmapdel(mfields);
1613     return out->err;
1614 }
1615
1616 int bson_merge2(const void *b1data, const void *b2data, bson_bool_t overwrite, bson *out) {
1617     bson_iterator it1, it2;
1618     bson_type bt1, bt2;
1619
1620     BSON_ITERATOR_FROM_BUFFER(&it1, b1data);
1621     BSON_ITERATOR_FROM_BUFFER(&it2, b2data);
1622     //Append all fields in B1 overwriten by B2
1623     while ((bt1 = bson_iterator_next(&it1)) != BSON_EOO) {
1624         const char* k1 = BSON_ITERATOR_KEY(&it1);
1625         if (overwrite && strcmp(JDBIDKEYNAME, k1) && (bt2 = bson_find_from_buffer(&it2, b2data, k1)) != BSON_EOO) {
1626             bson_append_field_from_iterator(&it2, out);
1627         } else {
1628             bson_append_field_from_iterator(&it1, out);
1629         }
1630     }
1631     BSON_ITERATOR_FROM_BUFFER(&it1, b1data);
1632     BSON_ITERATOR_FROM_BUFFER(&it2, b2data);
1633     //Append all fields from B2 missing in B1
1634     while ((bt2 = bson_iterator_next(&it2)) != BSON_EOO) {
1635         const char* k2 = BSON_ITERATOR_KEY(&it2);
1636         if ((bt1 = bson_find_from_buffer(&it1, b1data, k2)) == BSON_EOO) {
1637             bson_append_field_from_iterator(&it2, out);
1638         }
1639     }
1640     return BSON_OK;
1641 }
1642
1643 int bson_merge(const bson *b1, const bson *b2, bson_bool_t overwrite, bson *out) {
1644     assert(b1 && b2 && out);
1645     if (!b1->finished || !b2->finished || out->finished) {
1646         return BSON_ERROR;
1647     }
1648     return bson_merge2(bson_data(b1), bson_data(b2), overwrite, out);
1649 }
1650
1651 int bson_merge_recursive2(const void *b1data, const void *b2data, bson_bool_t overwrite, bson *out) {
1652     bson_iterator it1, it2;
1653     bson_type bt1, bt2;
1654
1655     BSON_ITERATOR_FROM_BUFFER(&it1, b1data);
1656     BSON_ITERATOR_FROM_BUFFER(&it2, b2data);
1657     //Append all fields in B1 merging with fields in B2 (for nested objects & arrays)
1658     while ((bt1 = bson_iterator_next(&it1)) != BSON_EOO) {
1659         const char* k1 = BSON_ITERATOR_KEY(&it1);
1660         bt2 = bson_find_from_buffer(&it2, b2data, k1);
1661         if (bt1 == BSON_OBJECT && bt2 == BSON_OBJECT) {
1662             int res;
1663             bson_append_start_object(out, k1);
1664             if ((res = bson_merge_recursive2(bson_iterator_value(&it1), bson_iterator_value(&it2), overwrite, out)) != BSON_OK) {
1665                 return res;
1666             }
1667             bson_append_finish_object(out);
1668         } else if (bt1 == BSON_ARRAY && bt2 == BSON_ARRAY) {
1669             int c = 0;
1670             bson_iterator sit;
1671             bson_type sbt;
1672
1673             bson_append_start_array(out, k1);
1674             BSON_ITERATOR_SUBITERATOR(&it1, &sit);
1675             while ((sbt = bson_iterator_next(&sit)) != BSON_EOO) {
1676                 bson_append_field_from_iterator(&sit, out);
1677                 ++c;
1678             }
1679             char kbuf[TCNUMBUFSIZ];
1680             BSON_ITERATOR_SUBITERATOR(&it2, &sit);
1681             while ((sbt = bson_iterator_next(&sit)) != BSON_EOO) {
1682                 bson_numstrn(kbuf, TCNUMBUFSIZ, c++);
1683                 bson_append_field_from_iterator2(kbuf, &sit, out);
1684             }
1685
1686             bson_append_finish_array(out);
1687         } else if (overwrite && strcmp(JDBIDKEYNAME, k1) && bt2 != BSON_EOO) {
1688             bson_append_field_from_iterator(&it2, out);
1689         } else {
1690             bson_append_field_from_iterator(&it1, out);
1691         }
1692     }
1693
1694     BSON_ITERATOR_FROM_BUFFER(&it1, b1data);
1695     BSON_ITERATOR_FROM_BUFFER(&it2, b2data);
1696     //Append all fields from B2 missing in B1
1697     while ((bt2 = bson_iterator_next(&it2)) != BSON_EOO) {
1698         const char* k2 = BSON_ITERATOR_KEY(&it2);
1699         if ((bt1 = bson_find_from_buffer(&it1, b1data, k2)) == BSON_EOO) {
1700             bson_append_field_from_iterator(&it2, out);
1701         }
1702     }
1703     return BSON_OK;
1704 }
1705
1706 int bson_merge_recursive(const bson *b1, const bson *b2, bson_bool_t overwrite, bson *out) {
1707     assert(b1 && b2 && out);
1708     if (!b1->finished || !b2->finished || out->finished) {
1709         return BSON_ERROR;
1710     }
1711     return bson_merge_recursive2(bson_data(b1), bson_data(b2), overwrite, out);
1712 }
1713
1714 typedef struct {
1715     int nstack; //nested object stack pos
1716     int matched; //number of matched include fields
1717     int astack; //nested array stack pos
1718     BSONSTRIPCTX *sctx;
1719 } _BSONSTRIPVISITORCTX;
1720
1721 /* Discard excluded fields from BSON */
1722 static bson_visitor_cmd_t _bsonstripvisitor_exclude(const char *ipath, int ipathlen, const char *key, int keylen,
1723         const bson_iterator *it, bool after, void *op) {
1724     _BSONSTRIPVISITORCTX *ictx = op;
1725     assert(ictx);
1726     BSONSTRIPCTX *sctx = ictx->sctx;
1727     assert(sctx && sctx->bsout && sctx->ifields && ipath && key && it && op);
1728     TCMAP *ifields = sctx->ifields;
1729     const void *buf;
1730     int bufsz;
1731     const char* ifpath;
1732     bson_type bt = BSON_ITERATOR_TYPE(it);
1733
1734     buf = after ? NULL : tcmapget(ifields, ipath, ipathlen, &bufsz);
1735     if (!buf) {
1736         if (bt == BSON_OBJECT || bt == BSON_ARRAY) {
1737             if (!after) {
1738                 tcmapiterinit(ifields); //check prefix
1739                 while ((ifpath = tcmapiternext2(ifields)) != NULL) {
1740                     int i = 0;
1741                     for (; i < ipathlen && *(ifpath + i) == *(ipath + i); ++i);
1742                     if (i == ipathlen) { //ipath prefixes some exclude object field
1743                         ictx->nstack++;
1744                         if (bt == BSON_OBJECT) {
1745                             bson_append_start_object2(sctx->bsout, key, keylen);
1746                         } else if (bt == BSON_ARRAY) {
1747                             ictx->astack++;
1748                             bson_append_start_array2(sctx->bsout, key, keylen);
1749                         }
1750                         return (BSON_VCMD_OK);
1751                     }
1752                 }
1753                 bson_append_field_from_iterator(it, sctx->bsout);
1754                 return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
1755             } else {
1756                 if (ictx->nstack > 0) {
1757                     --ictx->nstack;
1758                     if (bt == BSON_OBJECT) {
1759                         bson_append_finish_object(sctx->bsout);
1760                     } else if (bt == BSON_ARRAY) {
1761                         --ictx->astack;
1762                         bson_append_finish_array(sctx->bsout);
1763                     }
1764                 }
1765                 return (BSON_VCMD_OK);
1766             }
1767         } else {
1768             bson_append_field_from_iterator(it, sctx->bsout);
1769             return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
1770         }
1771     } else {
1772         if (!after && ictx->astack > 0 && bson_isnumstr(key, keylen)) {
1773             bson_append_undefined(sctx->bsout, key);
1774         }
1775         ictx->matched++;
1776     }
1777     return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
1778 }
1779
1780 /* Accept only included fields into BSON */
1781 static bson_visitor_cmd_t _bsonstripvisitor_include(const char *ipath, int ipathlen, const char *key, int keylen,
1782         const bson_iterator *it, bool after, void *op) {
1783     _BSONSTRIPVISITORCTX *ictx = op;
1784     assert(ictx);
1785     BSONSTRIPCTX *sctx = ictx->sctx;
1786     assert(sctx && sctx->bsout && sctx->ifields && ipath && key && it && op);
1787     bson_visitor_cmd_t rv = BSON_VCMD_OK;
1788     TCMAP *ifields = sctx->ifields;
1789     const void *buf;
1790     const char* ifpath;
1791     int bufsz;
1792
1793     const char *k = key;
1794     if (sctx->fkfields) { //find keys to override
1795         k = tcmapget(sctx->fkfields, ipath, ipathlen, &bufsz);
1796     }
1797     if (!k) {
1798         k = key;
1799     }
1800     bson_type bt = BSON_ITERATOR_TYPE(it);
1801     if (bt != BSON_OBJECT && bt != BSON_ARRAY) {
1802         if (after) { //simple primitive case
1803             return BSON_VCMD_OK;
1804         }
1805         buf = tcmapget(ifields, ipath, ipathlen, &bufsz);
1806         if (buf) {
1807             ictx->matched++;
1808             bson_append_field_from_iterator2(k, it, sctx->bsout);
1809         }
1810         return (BSON_VCMD_SKIP_AFTER);
1811     } else { //more complicated case
1812         if (!after) {
1813             buf = tcmapget(ifields, ipath, ipathlen, &bufsz);
1814             if (buf) { //field hitted
1815                 bson_iterator cit = *it; //copy iterator
1816                 bson_append_field_from_iterator(&cit, sctx->bsout);
1817                 ictx->matched++;
1818                 return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
1819             } else { //check prefix
1820                 int onstack = ictx->nstack;
1821                 tcmapiterinit(ifields);
1822                 while ((ifpath = tcmapiternext2(ifields)) != NULL) {
1823                     int i = 0;
1824                     for (; i < ipathlen && *(ifpath + i) == *(ipath + i); ++i);
1825                     if (i == ipathlen) { //ipath prefixes some included field
1826                         ictx->nstack++;
1827                         if (bt == BSON_OBJECT) {
1828                             bson_append_start_object2(sctx->bsout, k, keylen);
1829                         } else if (bt == BSON_ARRAY) {
1830                             bson_append_start_array2(sctx->bsout, k, keylen);
1831                         } else {
1832                             assert(0);
1833                         }
1834                         break;
1835                     }
1836                 }
1837                 if (onstack == ictx->nstack) {
1838                     return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
1839                 }
1840             }
1841         } else { //after
1842             if (ictx->nstack > 0) {
1843                 --ictx->nstack;
1844                 if (bt == BSON_OBJECT) {
1845                     bson_append_finish_object(sctx->bsout);
1846                 } else if (bt == BSON_ARRAY) {
1847                     bson_append_finish_array(sctx->bsout);
1848                 } else {
1849                     assert(0);
1850                 }
1851             }
1852         }
1853     }
1854
1855     if (ictx->nstack == 0 && ictx->matched == TCMAPRNUM(ifields)) {
1856         return BSON_VCMD_TERMINATE;
1857     }
1858     return rv;
1859 }
1860
1861 int bson_strip(TCMAP *ifields, bool imode, const void *bsbuf, bson *bsout, int *matched) {
1862     BSONSTRIPCTX sctx = {
1863         .ifields = ifields,
1864         .imode = imode,
1865         .bsbuf = bsbuf,
1866         .bsout = bsout,
1867         .fkfields = NULL,
1868         .matched = 0
1869     };
1870     int rc = bson_strip2(&sctx);
1871     *matched = sctx.matched;
1872     return rc;
1873 }
1874
1875 /* Include or exclude fpaths in the specified BSON and put resulting data into `bsout`. */
1876 int bson_strip2(BSONSTRIPCTX *sctx) {
1877     assert(sctx && sctx->bsbuf && sctx->bsout);
1878     if (!sctx->ifields || sctx->bsout->finished) {
1879         return BSON_ERROR;
1880     }
1881     _BSONSTRIPVISITORCTX ictx = {
1882         .nstack = 0,
1883         .astack = 0,
1884         .matched = 0,
1885         .sctx = sctx
1886     };
1887     bson_iterator it;
1888     BSON_ITERATOR_FROM_BUFFER(&it, sctx->bsbuf);
1889     bson_visit_fields(&it, 0, (sctx->imode) ? _bsonstripvisitor_include : _bsonstripvisitor_exclude, &ictx);
1890     assert(ictx.nstack == 0);
1891     sctx->matched = ictx.matched;
1892     return bson_finish(sctx->bsout);
1893 }
1894
1895 int bson_inplace_set_bool(bson_iterator *pos, bson_bool_t val) {
1896     assert(pos);
1897     bson_type bt = BSON_ITERATOR_TYPE(pos);
1898     if (bt != BSON_BOOL) {
1899         return BSON_ERROR;
1900     }
1901     char *t = (char*) pos->cur + 1;
1902     t += strlen(t) + 1;
1903     *t = (val != 0);
1904     return BSON_OK;
1905 }
1906
1907 int bson_inplace_set_long(bson_iterator *pos, int64_t val) {
1908     assert(pos);
1909     bson_type bt = BSON_ITERATOR_TYPE(pos);
1910     if (!BSON_IS_NUM_TYPE(bt)) {
1911         return BSON_ERROR;
1912     }
1913     char *t = (char*) pos->cur + 1;
1914     t += strlen(t) + 1;
1915     if (bt == BSON_INT) {
1916         bson_little_endian32(t, &val);
1917     } else if (bt == BSON_LONG || bt == BSON_DATE) {
1918         bson_little_endian64(t, &val);
1919     } else if (bt == BSON_DOUBLE) {
1920         double dval = (double) val;
1921         bson_little_endian64(t, &dval);
1922     } else {
1923         return BSON_ERROR;
1924     }
1925     return BSON_OK;
1926 }
1927
1928 int bson_inplace_set_double(bson_iterator *pos, double val) {
1929     assert(pos);
1930     bson_type bt = BSON_ITERATOR_TYPE(pos);
1931     if (!BSON_IS_NUM_TYPE(bt)) {
1932         return BSON_ERROR;
1933     }
1934     int64_t ival = (int64_t) val;
1935     char *t = (char*) pos->cur + 1;
1936     t += strlen(t) + 1;
1937     if (bt == BSON_INT) {
1938         bson_little_endian32(t, &ival);
1939     } else if (bt == BSON_LONG || bt == BSON_DATE) {
1940         bson_little_endian64(t, &ival);
1941     } else if (bt == BSON_DOUBLE) {
1942         bson_little_endian64(t, &val);
1943     } else {
1944         return BSON_ERROR;
1945     }
1946     return BSON_OK;
1947 }
1948
1949 int bson_compare_fpaths(const void *bsdata1, const void *bsdata2, const char *fpath1, int fplen1, const char *fpath2, int fplen2) {
1950     assert(bsdata1 && bsdata2 && fpath1 && fpath2);
1951     bson_iterator it1, it2;
1952     BSON_ITERATOR_FROM_BUFFER(&it1, bsdata1);
1953     BSON_ITERATOR_FROM_BUFFER(&it2, bsdata2);
1954     bson_find_fieldpath_value2(fpath1, fplen1, &it1);
1955     bson_find_fieldpath_value2(fpath2, fplen2, &it2);
1956     return bson_compare_it_current(&it1, &it2);
1957 }
1958
1959 /**
1960  *
1961  * Return <0 if value pointing by it1 lesser than from it2.
1962  * Return  0 if values equal
1963  * Return >0 if value pointing by it1 greater than from it2.
1964  * @param it1
1965  * @param i
1966  * @return
1967  */
1968 int bson_compare_it_current(const bson_iterator *it1, const bson_iterator *it2) {
1969     bson_type t1 = BSON_ITERATOR_TYPE(it1);
1970     bson_type t2 = BSON_ITERATOR_TYPE(it2);
1971
1972         if ((BSON_IS_STRING_TYPE(t1) && !BSON_IS_STRING_TYPE(t2)) ||
1973                 (BSON_IS_STRING_TYPE(t2) && !BSON_IS_STRING_TYPE(t1))) {
1974                 return (t1 - t2);
1975         }
1976
1977     if (t1 == BSON_BOOL || t1 == BSON_EOO || t1 == BSON_NULL || t1 == BSON_UNDEFINED) {
1978         int v1 = bson_iterator_bool(it1);
1979         int v2 = bson_iterator_bool(it2);
1980         return (v1 > v2) ? 1 : ((v1 < v2) ? -1 : 0);
1981     } else if (t1 == BSON_INT || t1 == BSON_LONG || t1 == BSON_DATE || t1 == BSON_TIMESTAMP) {
1982         int64_t v1 = bson_iterator_long_ext(it1);
1983         int64_t v2 = bson_iterator_long_ext(it2);
1984         return (v1 > v2) ? 1 : ((v1 < v2) ? -1 : 0);
1985     } else if (t1 == BSON_DOUBLE) {
1986         double v1 = bson_iterator_double_raw(it1);
1987         double v2 = bson_iterator_double(it2);
1988         return (v1 > v2) ? 1 : ((v1 < v2) ? -1 : 0);
1989     } else if (BSON_IS_STRING_TYPE(t1)) {
1990         const char* v1 = bson_iterator_string(it1);
1991         int l1 = bson_iterator_string_len(it1);
1992         const char* v2 = bson_iterator_string(it2);
1993         int l2 = bson_iterator_string_len(it2);
1994         int rv;
1995         TCCMPLEXICAL(rv, v1, l1, v2, l2);
1996         return rv;
1997     } else if (t1 == BSON_BINDATA && t2 == BSON_BINDATA) {
1998         int l1 = bson_iterator_bin_len(it1);
1999         int l2 = bson_iterator_bin_len(it2);
2000         return memcmp(bson_iterator_bin_data(it1), bson_iterator_bin_data(it2), MIN(l1, l2));
2001     } else if (t1 == BSON_OID && t2 == BSON_OID) {
2002         return memcmp(bson_iterator_oid(it1), bson_iterator_oid(it2), sizeof (bson_oid_t));
2003     } else if (t1 == t2 && (t1 == BSON_OBJECT || t1 == BSON_ARRAY)) {
2004         int cv = 0;
2005         bson_type bt1, bt2;
2006         bson_iterator sit1, sit2;
2007         BSON_ITERATOR_SUBITERATOR(it1, &sit1);
2008         BSON_ITERATOR_SUBITERATOR(it2, &sit2);
2009         while ((bt1 = bson_iterator_next(&sit1)) != BSON_EOO) {
2010             bt2 = bson_iterator_next(&sit2);
2011             if (bt2 == BSON_EOO) {
2012                 cv = 1;
2013                 break;
2014             }
2015             cv = bson_compare_it_current(&sit1, &sit2);
2016             if (cv) {
2017                 break;
2018             }
2019         }
2020         if (cv == 0 && bson_iterator_next(&sit2) != BSON_EOO) {
2021             cv = -1;
2022         }
2023         return cv;
2024     }
2025     return (t1 - t2);
2026 }
2027
2028 int bson_compare(const void *bsdata1, const void *bsdata2, const char* fpath, int fplen) {
2029     return bson_compare_fpaths(bsdata1, bsdata2, fpath, fplen, fpath, fplen);
2030 }
2031
2032 int bson_compare_string(const char *cv, const void *bsdata, const char *fpath) {
2033     assert(cv && bsdata && fpath);
2034     bson *bs1 = bson_create();
2035     bson_init(bs1);
2036     bson_append_string(bs1, "$", cv);
2037     bson_finish(bs1);
2038     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2039     bson_del(bs1);
2040     return res;
2041 }
2042
2043 int bson_compare_long(const int64_t cv, const void *bsdata, const char *fpath) {
2044     bson *bs1 = bson_create();
2045     bson_init(bs1);
2046     bson_append_long(bs1, "$", cv);
2047     bson_finish(bs1);
2048     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2049     bson_del(bs1);
2050     return res;
2051 }
2052
2053 int bson_compare_double(double cv, const void *bsdata, const char *fpath) {
2054     bson *bs1 = bson_create();
2055     bson_init(bs1);
2056     bson_append_double(bs1, "$", cv);
2057     bson_finish(bs1);
2058     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2059     bson_del(bs1);
2060     return res;
2061 }
2062
2063 int bson_compare_bool(bson_bool_t cv, const void *bsdata, const char *fpath) {
2064     bson *bs1 = bson_create();
2065     bson_init(bs1);
2066     bson_append_bool(bs1, "$", cv);
2067     bson_finish(bs1);
2068     int res = bson_compare_fpaths(bson_data(bs1), bsdata, "$", 1, fpath, strlen(fpath));
2069     bson_del(bs1);
2070     return res;
2071 }
2072
2073 bson* bson_dup(const bson *src) {
2074     assert(src);
2075     bson *rv = bson_create();
2076     int s = bson_size(src);
2077     _bson_init_size(rv, s);
2078     memmove(rv->data, src->data, s);
2079     rv->finished = 1;
2080     return rv;
2081 }
2082
2083 bson* bson_create_from_iterator(bson_iterator *from) {
2084     assert(from);
2085     bson_type bt;
2086     bson *bs = bson_create();
2087     bson_init_as_query(bs);
2088     while ((bt = bson_iterator_next(from)) != BSON_EOO) {
2089         bson_append_field_from_iterator(from, bs);
2090     }
2091     bson_finish(bs);
2092     return bs;
2093 }
2094
2095 bson* bson_create_from_buffer(const void* buf, int bufsz) {
2096     return bson_create_from_buffer2(bson_create(), buf, bufsz);
2097 }
2098
2099 bson* bson_create_from_buffer2(bson *rv, const void* buf, int bufsz) {
2100     assert(buf);
2101     assert(bufsz - 4 > 0);
2102     bson_init_size(rv, bufsz);
2103     bson_ensure_space(rv, bufsz - 4);
2104     bson_append(rv, (char*) buf + 4, bufsz - (4 + 1/*BSON_EOO*/));
2105     bson_finish(rv);
2106     return rv;
2107 }
2108
2109 void bson_init_with_data(bson *bs, const void *bsdata) {
2110     memset(bs, 0, sizeof (*bs));
2111     bs->data = (char*) bsdata;
2112     bson_little_endian32(&bs->dataSize, bsdata);
2113     bs->finished = true;
2114 }
2115
2116 bool bson_find_merged_arrays(const void *mbuf, const void *inbuf, bool expandall) {
2117     assert(mbuf && inbuf);
2118     bool found = false;
2119     bson_iterator it, it2;
2120     bson_type bt, bt2;
2121     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2122
2123     while (!found && (bt = bson_iterator_next(&it)) != BSON_EOO) {
2124         if (expandall && bt != BSON_ARRAY) {
2125             continue;
2126         }
2127         BSON_ITERATOR_FROM_BUFFER(&it2, inbuf);
2128         bt2 = bson_find_fieldpath_value(BSON_ITERATOR_KEY(&it), &it2);
2129         if (bt2 != BSON_ARRAY) {
2130             continue;
2131         }
2132         bson_iterator sit;
2133         BSON_ITERATOR_SUBITERATOR(&it2, &sit);
2134         while (!found && (bt2 = bson_iterator_next(&sit)) != BSON_EOO) {
2135             if (expandall) {
2136                 bson_iterator sit2;
2137                 BSON_ITERATOR_SUBITERATOR(&it, &sit2);
2138                 while ((bt2 = bson_iterator_next(&sit2)) != BSON_EOO) {
2139                     if (!bson_compare_it_current(&sit, &sit2)) {
2140                         found = true;
2141                         break;
2142                     }
2143                 }
2144             } else {
2145                 if (!bson_compare_it_current(&sit, &it)) {
2146                     found = true;
2147                     break;
2148                 }
2149             }
2150         }
2151     }
2152     return found;
2153 }
2154
2155 bool bson_find_unmerged_arrays(const void *mbuf, const void *inbuf) {
2156     assert(mbuf && inbuf);
2157     bool allfound = false;
2158     bson_iterator it, it2;
2159     bson_type bt, bt2;
2160     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2161     while ((bt = bson_iterator_next(&it)) != BSON_EOO) {
2162         BSON_ITERATOR_FROM_BUFFER(&it2, inbuf);
2163         bt2 = bson_find_fieldpath_value(BSON_ITERATOR_KEY(&it), &it2);
2164         if (bt2 == BSON_EOO) { //array missing it will be created
2165             allfound = false;
2166             break;
2167         }
2168         if (bt2 != BSON_ARRAY) { //not an array field
2169             continue;
2170         }
2171         allfound = false;
2172         bson_iterator sit;
2173         BSON_ITERATOR_SUBITERATOR(&it2, &sit);
2174         while ((bt2 = bson_iterator_next(&sit)) != BSON_EOO) {
2175             if (!bson_compare_it_current(&sit, &it)) {
2176                 allfound = true;
2177                 break;
2178             }
2179         }
2180         if (!allfound) {
2181             break;
2182         }
2183     }
2184     return !allfound;
2185 }
2186
2187 typedef struct {
2188     bson *bsout;
2189     const void *mbuf;
2190     int mfields;
2191     int ecode;
2192     bool duty;
2193     bool expandall;
2194     bson_merge_array_mode mode;
2195 } _BSONMARRCTX;
2196
2197
2198 static bson_visitor_cmd_t _bson_merge_arrays_pull_visitor(
2199                         const char *fpath, int fpathlen,
2200                         const char *key, int keylen,
2201                         const bson_iterator *it, bool after, void *op) {
2202
2203     _BSONMARRCTX *ctx = op;
2204     assert(ctx && ctx->mfields >= 0);
2205     bson_iterator mit;
2206     bson_type bt = BSON_ITERATOR_TYPE(it);
2207     if (bt != BSON_OBJECT && bt != BSON_ARRAY) { //trivial case
2208         if (after) {
2209             return (BSON_VCMD_OK);
2210         }
2211         bson_append_field_from_iterator(it, ctx->bsout);
2212         return (BSON_VCMD_SKIP_AFTER);
2213     }
2214     if (bt == BSON_ARRAY) {
2215         BSON_ITERATOR_FROM_BUFFER(&mit, ctx->mbuf);
2216         bt = bson_find_fieldpath_value2(fpath, fpathlen, &mit);
2217         if (bt == BSON_EOO || (ctx->expandall && bt != BSON_ARRAY)) {
2218             bson_append_field_from_iterator(it, ctx->bsout);
2219             return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2220         }
2221         if (ctx->mfields > 0) {
2222             --ctx->mfields;
2223         }
2224         //Find and merge
2225         bson_iterator ait;
2226         BSON_ITERATOR_SUBITERATOR(it, &ait);
2227         bson_append_start_array(ctx->bsout, key);
2228         int c = 0;
2229         bool found = false;
2230         while ((bt = bson_iterator_next(&ait)) != BSON_EOO) {
2231             found = false;
2232             if (ctx->expandall) {
2233                 bson_iterator mitsub;
2234                 BSON_ITERATOR_SUBITERATOR(&mit, &mitsub);
2235                 while ((bt = bson_iterator_next(&mitsub)) != BSON_EOO) {
2236                     if (!bson_compare_it_current(&ait, &mitsub)) {
2237                         found = true;
2238                         break;
2239                     }
2240                 }
2241             } else {
2242                 found = !bson_compare_it_current(&ait, &mit);
2243             }
2244             if (!found) {
2245                 char kbuf[TCNUMBUFSIZ];
2246                 bson_numstrn(kbuf, TCNUMBUFSIZ, c++);
2247                 bson_append_field_from_iterator2(kbuf, &ait, ctx->bsout);
2248             }
2249         }
2250         bson_append_finish_array(ctx->bsout);
2251         return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2252     }
2253     //bt is BSON_OBJECT
2254     if (!after) {
2255         bson_append_start_object(ctx->bsout, key);
2256     } else { //after
2257         bson_append_finish_object(ctx->bsout);
2258     }
2259     return (BSON_VCMD_OK);
2260 }
2261
2262 static bson_visitor_cmd_t _bson_merge_arrays_visitor(
2263                         const char *fpath, int fpathlen,
2264                         const char *key, int keylen,
2265                         const bson_iterator *it,
2266                         bool after, void *op) {
2267
2268     _BSONMARRCTX *ctx = op;
2269     assert(ctx && ctx->mfields >= 0);
2270     bson_iterator mit;
2271     bson_type bt = BSON_ITERATOR_TYPE(it);
2272
2273     if (bt != BSON_OBJECT && bt != BSON_ARRAY) { //trivial case
2274         if (after) {
2275             return (BSON_VCMD_OK);
2276         }
2277         bson_append_field_from_iterator(it, ctx->bsout);
2278         return (BSON_VCMD_SKIP_AFTER);
2279     }
2280     if (bt == BSON_ARRAY) {
2281         if (after) {
2282             bson_append_finish_array(ctx->bsout);
2283             return (BSON_VCMD_OK);
2284         }
2285         BSON_ITERATOR_FROM_BUFFER(&mit, ctx->mbuf);
2286         bt = bson_find_fieldpath_value2(fpath, fpathlen, &mit);
2287         if (bt == BSON_EOO) {
2288             bson_append_start_array(ctx->bsout, key);
2289             return (BSON_VCMD_OK);
2290         }
2291         if (ctx->expandall && bt != BSON_ARRAY) {
2292             bson_append_field_from_iterator(it, ctx->bsout);
2293             return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2294         }
2295         if (ctx->mfields > 0) {
2296             --ctx->mfields;
2297         }
2298         //Find and merge
2299         bson_iterator ait;
2300         BSON_ITERATOR_SUBITERATOR(it, &ait);
2301         bson_append_start_array(ctx->bsout, key);
2302         bool found = false;
2303         int c = 0;
2304         if (ctx->expandall) { //Set of array elements to add
2305             while ((bt = bson_iterator_next(&ait)) != BSON_EOO) { //Flush current array
2306                 bson_append_field_from_iterator(&ait, ctx->bsout);
2307                 ++c;
2308             }
2309             //Iterate over set to add
2310             bson_iterator mitsub;
2311             BSON_ITERATOR_SUBITERATOR(&mit, &mitsub); //mit has BSON_ARRAY type
2312             while ((bt = bson_iterator_next(&mitsub)) != BSON_EOO) {
2313                 found = false;
2314                 if (ctx->mode == BSON_MERGE_ARRAY_ADDSET) {
2315                     BSON_ITERATOR_SUBITERATOR(it, &ait); //Rewind main array iterator
2316                     while ((bt = bson_iterator_next(&ait)) != BSON_EOO) {
2317                         if (!bson_compare_it_current(&ait, &mitsub)) {
2318                             found = true;
2319                             break;
2320                         }
2321                     }
2322                 }
2323                 if (!found) { //Append missing element
2324                     char kbuf[TCNUMBUFSIZ];
2325                     bson_numstrn(kbuf, TCNUMBUFSIZ, c++);
2326                     bson_append_field_from_iterator2(kbuf, &mitsub, ctx->bsout);
2327                     ctx->duty = true;
2328                 }
2329             }
2330         } else { //Single element to add
2331             while ((bt = bson_iterator_next(&ait)) != BSON_EOO) {
2332                 if ((ctx->mode == BSON_MERGE_ARRAY_ADDSET) &&
2333                     !found &&
2334                     !bson_compare_it_current(&ait, &mit)) {
2335                     found = true;
2336                 }
2337                 bson_append_field_from_iterator(&ait, ctx->bsout);
2338                 ++c;
2339             }
2340             if (!found) { //uppend missing element into array
2341                 char kbuf[TCNUMBUFSIZ];
2342                 bson_numstrn(kbuf, TCNUMBUFSIZ, c);
2343                 bson_append_field_from_iterator2(kbuf, &mit, ctx->bsout);
2344                 ctx->duty = true;
2345             }
2346         }
2347         bson_append_finish_array(ctx->bsout);
2348         return (BSON_VCMD_SKIP_NESTED | BSON_VCMD_SKIP_AFTER);
2349     }
2350     //bt is BSON_OBJECT
2351     if (!after) {
2352         bson_append_start_object(ctx->bsout, key);
2353     } else { //after
2354         bson_append_finish_object(ctx->bsout);
2355     }
2356     return (BSON_VCMD_OK);
2357 }
2358
2359 int bson_merge_arrays(const void *mbuf,
2360                       const void *inbuf,
2361                       bson_merge_array_mode mode,
2362                       bool expandall,
2363                       bson *bsout) {
2364
2365     assert(mbuf && inbuf && bsout);
2366     assert(mode == BSON_MERGE_ARRAY_ADDSET ||
2367            mode == BSON_MERGE_ARRAY_PULL ||
2368            mode == BSON_MERGE_ARRAY_PUSH);
2369
2370     if (bsout->finished) {
2371         return BSON_ERROR;
2372     }
2373     _BSONMARRCTX ctx = {
2374         .bsout = bsout,
2375         .mbuf = mbuf,
2376         .mfields = 0,
2377         .duty = false,
2378         .expandall = expandall,
2379         .ecode = BSON_OK,
2380         .mode = mode
2381     };
2382     bson_type bt, bt2;
2383     bson_iterator it, it2;
2384     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2385     while ((bt = bson_iterator_next(&it)) != BSON_EOO) {
2386         if (expandall && bt != BSON_ARRAY) {
2387             continue;
2388         }
2389         ctx.mfields++;
2390     }
2391     BSON_ITERATOR_FROM_BUFFER(&it, inbuf);
2392     if (mode == BSON_MERGE_ARRAY_PULL) {
2393         bson_visit_fields(&it, 0, _bson_merge_arrays_pull_visitor, &ctx);
2394     } else {
2395         bson_visit_fields(&it, 0, _bson_merge_arrays_visitor, &ctx);
2396     }
2397     if (ctx.mfields == 0 || //all fields are merged
2398         mode == BSON_MERGE_ARRAY_PULL) {
2399         return ctx.ecode;
2400     }
2401
2402     //Append missing arrays fields
2403     BSON_ITERATOR_FROM_BUFFER(&it, mbuf);
2404     while ((bt = bson_iterator_next(&it)) != BSON_EOO) {
2405         const char *fpath = BSON_ITERATOR_KEY(&it);
2406         // all data from inbuf already in bsout
2407         bson_finish(bsout);
2408         BSON_ITERATOR_INIT(&it2, bsout);
2409         bt2 = bson_find_fieldpath_value(fpath, &it2);
2410         if (bt2 != BSON_EOO) continue;
2411         int i = 0;
2412         int lvl = 0;
2413         const char *pdp = fpath;
2414         bson bst;
2415         bson_init(&bst);
2416         while (*(fpath + i) != '\0') {
2417             for (; *(fpath + i) != '\0' && *(fpath + i) != '.'; ++i);
2418             if (*(fpath + i) == '\0') { //EOF
2419                 assert((fpath + i) - pdp > 0);
2420                 bson_append_start_array2(&bst, pdp, (fpath + i) - pdp);
2421                 bson_append_field_from_iterator2("0", &it, &bst);
2422                 bson_append_finish_array(&bst);
2423                 break;
2424             } else {
2425                 ++lvl;
2426                 assert((fpath + i) - pdp > 0);
2427                 bson_append_start_object2(&bst, pdp, (fpath + i) - pdp);
2428             }
2429             pdp = (fpath + i);
2430             while (*pdp == '.') {
2431                 ++pdp;
2432                 ++i;
2433             }
2434         }
2435         for (; lvl > 0; --lvl) {
2436             bson_append_finish_object(&bst);
2437         }
2438         bson_finish(&bst);
2439
2440         bson bsc;
2441         bson_init_finished_data(&bsc, bson_data(bsout));
2442         bson_init_size(bsout, bson_size(bsout));
2443         int res = bson_merge_recursive(&bsc, &bst, false, bsout);
2444         bson_destroy(&bsc);
2445         bson_destroy(&bst);
2446         if (res != BSON_OK) {
2447             return BSON_ERROR;
2448         }
2449     }
2450     return ctx.ecode;
2451 }
2452
2453 typedef struct {
2454     int nlvl; //nesting level
2455     TCXSTR *out; //output buffer
2456 } _BSON2JSONCTX;
2457
2458 static void _jsonxstrescaped(TCXSTR *xstr, const char *str) {
2459     size_t sz = strlen(str);
2460     int s = 0;
2461     int e = 0;
2462     char hb[7];
2463     hb[0] = '\\';
2464     hb[1] = 'u';
2465     hb[2] = '0';
2466     hb[3] = '0';
2467     hb[6] = '\0';
2468     while (e < sz) {
2469         const char * ebuf = NULL;
2470         switch (str[e]) {
2471             case '\r': ebuf = "\\r";
2472                 break;
2473             case '\n': ebuf = "\\n";
2474                 break;
2475             case '\\': ebuf = "\\\\";
2476                 break;
2477             case '/':
2478                 break;
2479             case '"': ebuf = "\\\"";
2480                 break;
2481             case '\f': ebuf = "\\f";
2482                 break;
2483             case '\b': ebuf = "\\b";
2484                 break;
2485             case '\t': ebuf = "\\t";
2486                 break;
2487             default:
2488                 if ((unsigned char) str[e] < 0x20) {
2489                     static const char *hexchar = "0123456789ABCDEF";
2490                     hb[4] = hexchar[str[e] >> 4];
2491                     hb[5] = hexchar[str[e] & 0x0F];
2492                     ebuf = hb;
2493                 }
2494                 break;
2495         }
2496         if (ebuf != NULL) {
2497             if (e > s) {
2498                 tcxstrcat(xstr, str + s, e - s);
2499             }
2500             tcxstrcat2(xstr, ebuf);
2501             s = ++e;
2502         } else {
2503             ++e;
2504         }
2505     }
2506     tcxstrcat(xstr, (str + s), e - s);
2507 }
2508
2509 static int _bson2json(_BSON2JSONCTX *ctx, bson_iterator *it, bool array) {
2510
2511 #define BSPAD(_n) \
2512     for (int i = 0; i < ctx->nlvl + (_n); ++i) tcxstrcat2(ctx->out, " ")
2513
2514     bson_type bt;
2515     TCXSTR *out = ctx->out;
2516     tcxstrcat2(ctx->out, array ? "[\n" : "{\n");
2517     ctx->nlvl += 4;
2518     int c = 0;
2519     while ((bt = bson_iterator_next(it)) != BSON_EOO) {
2520         if (c++ > 0) {
2521             if (array) {
2522                 tcxstrcat2(out, "\n");
2523                 BSPAD(0);
2524             }
2525             tcxstrcat2(out, ",\n");
2526         }
2527         const char *key = BSON_ITERATOR_KEY(it);
2528         BSPAD(0);
2529         if (!array) {
2530             tcxstrcat2(out, "\"");
2531             _jsonxstrescaped(out, key);
2532             tcxstrcat2(out, "\" : ");
2533         }
2534
2535         switch (bt) {
2536             case BSON_LONG:
2537             case BSON_INT:
2538                 tcxstrprintf(out, "%" PRId64, (int64_t) bson_iterator_long_ext(it));
2539                 break;
2540             case BSON_DOUBLE:
2541             {
2542                 tcxstrprintf(out, "%lf", bson_iterator_double(it));
2543                 break;
2544             }
2545             case BSON_STRING:
2546             case BSON_SYMBOL:
2547             {
2548                 tcxstrcat2(out, "\"");
2549                 _jsonxstrescaped(out, bson_iterator_string(it));
2550                 tcxstrcat2(out, "\"");
2551                 break;
2552             }
2553             case BSON_OBJECT:
2554             case BSON_ARRAY:
2555             {
2556                 bson_iterator sit;
2557                 BSON_ITERATOR_SUBITERATOR(it, &sit);
2558                 _bson2json(ctx, &sit, bt == BSON_ARRAY);
2559                 break;
2560             }
2561             case BSON_NULL:
2562                 tcxstrcat2(out, "null");
2563             case BSON_UNDEFINED:
2564                 break;
2565             case BSON_DATE:
2566             {
2567                 bson_date_t t = bson_iterator_date(it);
2568                 char dbuf[49];
2569                 tcdatestrwww(t, INT_MAX, dbuf);
2570                 tcxstrprintf(out, "\"%s\"", dbuf);
2571                 break;
2572             }
2573             case BSON_BOOL:
2574                 tcxstrcat2(out, bson_iterator_bool(it) ? "true" : "false");
2575                 break;
2576             case BSON_OID:
2577             {
2578                 char xoid[25];
2579                 bson_oid_t *oid = bson_iterator_oid(it);
2580                 bson_oid_to_string(oid, xoid);
2581                 tcxstrprintf(out, "\"%s\"", xoid);
2582                 break;
2583             }
2584             case BSON_REGEX:
2585             {
2586                 tcxstrcat2(out, "\"");
2587                 _jsonxstrescaped(out, bson_iterator_regex(it));
2588                 tcxstrcat2(out, "\"");
2589                 break;
2590             }
2591             case BSON_BINDATA:
2592             {
2593                 const char *buf = bson_iterator_bin_data(it);
2594                 int bsz = bson_iterator_bin_len(it);
2595                 char *b64data = tcbaseencode(buf, bsz);
2596                 tcxstrcat2(out, "\"");
2597                 tcxstrcat2(out, b64data);
2598                 tcxstrcat2(out, "\"");
2599                 TCFREE(b64data);
2600                 break;
2601             }
2602             default:
2603                 break;
2604         }
2605     }
2606     tcxstrcat2(out, "\n");
2607     BSPAD(-4);
2608     tcxstrcat2(out, array ? "]" : "}");
2609     ctx->nlvl -= 4;
2610     return 0;
2611 #undef BSPAD
2612 }
2613
2614 int bson2json(const char *bsdata, char **buf, int *sp) {
2615     assert(bsdata && buf && sp);
2616     bson_iterator it;
2617     BSON_ITERATOR_FROM_BUFFER(&it, bsdata);
2618     TCXSTR *out = tcxstrnew();
2619     _BSON2JSONCTX ctx = {
2620         .nlvl = 0,
2621         .out = out
2622     };
2623     int ret = _bson2json(&ctx, &it, false);
2624     if (ret == BSON_OK) {
2625         *sp = TCXSTRSIZE(out);
2626         *buf = tcxstrtomalloc(out);
2627     } else {
2628         *sp = 0;
2629         *buf = NULL;
2630         tcxstrclear(out);
2631     }
2632     return ret;
2633 }
2634
2635
2636 #include "nxjson.h"
2637
2638 static void _json2bson(bson *out, const nx_json *json, const char *forcekey) {
2639     const char *key =  forcekey ? forcekey : json->key;
2640     switch (json->type) {
2641         case NX_JSON_NULL:
2642             assert(key);
2643             bson_append_null(out, key);
2644             break;
2645         case NX_JSON_OBJECT:
2646         {
2647             if (key) {
2648                 bson_append_start_object(out, key);
2649             }
2650             for (nx_json* js = json->child; js; js = js->next) {
2651                 _json2bson(out, js, NULL);
2652             }
2653             if (key) {
2654                 bson_append_finish_object(out);
2655             }
2656             break;
2657         }
2658         case NX_JSON_ARRAY:
2659         {
2660             if (key) {
2661                 bson_append_start_array(out, key);
2662             }
2663             int c = 0;
2664             char kbuf[TCNUMBUFSIZ];
2665             for (nx_json* js = json->child; js; js = js->next) {
2666                  bson_numstrn(kbuf, TCNUMBUFSIZ, c++);
2667                 _json2bson(out, js, kbuf);
2668             }
2669             if (key) {
2670                 bson_append_finish_array(out);
2671             }
2672             break;
2673         }
2674         case NX_JSON_STRING:
2675             assert(key);
2676             bson_append_string(out, key, json->text_value);
2677             break;
2678         case NX_JSON_INTEGER:
2679             assert(key);
2680             if (json->int_value <= INT_MAX && json->int_value >= INT_MIN) {
2681                 bson_append_int(out, key, (int) json->int_value);
2682             } else {
2683                 bson_append_long(out, key, json->int_value);
2684             }
2685             break;
2686         case NX_JSON_DOUBLE:
2687             assert(key);
2688             bson_append_double(out, key, json->dbl_value);
2689             break;
2690         case NX_JSON_BOOL:
2691             assert(key);
2692             bson_append_bool(out, key, json->int_value ? true : false);
2693             break;
2694         default:
2695             break;
2696     }
2697 }
2698
2699 bson* json2bson(const char *jsonstr) {
2700     bool err = false;
2701     bson *out = NULL;
2702     char *json = strdup(jsonstr); //nxjson uses inplace data modification
2703     if (!json) {
2704         return NULL;
2705     }
2706     out = bson_create();
2707     bson_init_as_query(out);
2708     const nx_json *nxjson = nx_json_parse_utf8(json);
2709     if (!nxjson) {
2710         err = true;
2711         goto finish;
2712     }
2713     _json2bson(out, nxjson, NULL);
2714     bson_finish(out);
2715     err = out->err;
2716 finish:
2717     free(json);
2718     if (nxjson) {
2719         nx_json_free(nxjson);
2720     }
2721     if (err && out) {
2722         bson_del(out);
2723         out = NULL;
2724     }
2725     return out;
2726 }
2727