granicus.if.org Git - postgresql/blob - src/backend/utils/adt/jsonb_util.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * jsonb_util.c
   4  *        converting between Jsonb and JsonbValues, and iterating.
   5  *
   6  * Copyright (c) 2014, PostgreSQL Global Development Group
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        src/backend/utils/adt/jsonb_util.c
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include "postgres.h"
  15
  16 #include "access/hash.h"
  17 #include "catalog/pg_collation.h"
  18 #include "miscadmin.h"
  19 #include "utils/builtins.h"
  20 #include "utils/jsonb.h"
  21 #include "utils/memutils.h"
  22
  23 /*
  24  * Maximum number of elements in an array (or key/value pairs in an object).
  25  * This is limited by two things: the size of the JEntry array must fit
  26  * in MaxAllocSize, and the number of elements (or pairs) must fit in the bits
  27  * reserved for that in the JsonbContainer.header field.
  28  *
  29  * (the total size of an array's elements is also limited by JENTRY_POSMASK,
  30  * but we're not concerned about that here)
  31  */
  32 #define JSONB_MAX_ELEMS (Min(MaxAllocSize / sizeof(JsonbValue), JB_CMASK))
  33 #define JSONB_MAX_PAIRS (Min(MaxAllocSize / sizeof(JsonbPair), JB_CMASK))
  34
  35 static void fillJsonbValue(JEntry *array, int index, char *base_addr,
  36                            JsonbValue *result);
  37 static bool     equalsJsonbScalarValue(JsonbValue *a, JsonbValue *b);
  38 static int      compareJsonbScalarValue(JsonbValue *a, JsonbValue *b);
  39 static Jsonb *convertToJsonb(JsonbValue *val);
  40 static void convertJsonbValue(StringInfo buffer, JEntry *header, JsonbValue *val, int level);
  41 static void convertJsonbArray(StringInfo buffer, JEntry *header, JsonbValue *val, int level);
  42 static void convertJsonbObject(StringInfo buffer, JEntry *header, JsonbValue *val, int level);
  43 static void convertJsonbScalar(StringInfo buffer, JEntry *header, JsonbValue *scalarVal);
  44
  45 static int reserveFromBuffer(StringInfo buffer, int len);
  46 static void appendToBuffer(StringInfo buffer, const char *data, int len);
  47 static void copyToBuffer(StringInfo buffer, int offset, const char *data, int len);
  48 static short padBufferToInt(StringInfo buffer);
  49
  50 static JsonbIterator *iteratorFromContainer(JsonbContainer *container, JsonbIterator *parent);
  51 static JsonbIterator *freeAndGetParent(JsonbIterator *it);
  52 static JsonbParseState *pushState(JsonbParseState **pstate);
  53 static void appendKey(JsonbParseState *pstate, JsonbValue *scalarVal);
  54 static void appendValue(JsonbParseState *pstate, JsonbValue *scalarVal);
  55 static void appendElement(JsonbParseState *pstate, JsonbValue *scalarVal);
  56 static int      lengthCompareJsonbStringValue(const void *a, const void *b);
  57 static int      lengthCompareJsonbPair(const void *a, const void *b, void *arg);
  58 static void uniqueifyJsonbObject(JsonbValue *object);
  59
  60 /*
  61  * Turn an in-memory JsonbValue into a Jsonb for on-disk storage.
  62  *
  63  * There isn't a JsonbToJsonbValue(), because generally we find it more
  64  * convenient to directly iterate through the Jsonb representation and only
  65  * really convert nested scalar values.  JsonbIteratorNext() does this, so that
  66  * clients of the iteration code don't have to directly deal with the binary
  67  * representation (JsonbDeepContains() is a notable exception, although all
  68  * exceptions are internal to this module).  In general, functions that accept
  69  * a JsonbValue argument are concerned with the manipulation of scalar values,
  70  * or simple containers of scalar values, where it would be inconvenient to
  71  * deal with a great amount of other state.
  72  */
  73 Jsonb *
  74 JsonbValueToJsonb(JsonbValue *val)
  75 {
  76         Jsonb      *out;
  77
  78         if (IsAJsonbScalar(val))
  79         {
  80                 /* Scalar value */
  81                 JsonbParseState *pstate = NULL;
  82                 JsonbValue *res;
  83                 JsonbValue      scalarArray;
  84
  85                 scalarArray.type = jbvArray;
  86                 scalarArray.val.array.rawScalar = true;
  87                 scalarArray.val.array.nElems = 1;
  88
  89                 pushJsonbValue(&pstate, WJB_BEGIN_ARRAY, &scalarArray);
  90                 pushJsonbValue(&pstate, WJB_ELEM, val);
  91                 res = pushJsonbValue(&pstate, WJB_END_ARRAY, NULL);
  92
  93                 out = convertToJsonb(res);
  94         }
  95         else if (val->type == jbvObject || val->type == jbvArray)
  96         {
  97                 out = convertToJsonb(val);
  98         }
  99         else
 100         {
 101                 Assert(val->type == jbvBinary);
 102                 out = palloc(VARHDRSZ + val->val.binary.len);
 103                 SET_VARSIZE(out, VARHDRSZ + val->val.binary.len);
 104                 memcpy(VARDATA(out), val->val.binary.data, val->val.binary.len);
 105         }
 106
 107         return out;
 108 }
 109
 110 /*
 111  * BT comparator worker function.  Returns an integer less than, equal to, or
 112  * greater than zero, indicating whether a is less than, equal to, or greater
 113  * than b.  Consistent with the requirements for a B-Tree operator class
 114  *
 115  * Strings are compared lexically, in contrast with other places where we use a
 116  * much simpler comparator logic for searching through Strings.  Since this is
 117  * called from B-Tree support function 1, we're careful about not leaking
 118  * memory here.
 119  */
 120 int
 121 compareJsonbContainers(JsonbContainer *a, JsonbContainer *b)
 122 {
 123         JsonbIterator *ita,
 124                            *itb;
 125         int                     res = 0;
 126
 127         ita = JsonbIteratorInit(a);
 128         itb = JsonbIteratorInit(b);
 129
 130         do
 131         {
 132                 JsonbValue      va,
 133                                         vb;
 134                 int                     ra,
 135                                         rb;
 136
 137                 ra = JsonbIteratorNext(&ita, &va, false);
 138                 rb = JsonbIteratorNext(&itb, &vb, false);
 139
 140                 if (ra == rb)
 141                 {
 142                         if (ra == WJB_DONE)
 143                         {
 144                                 /* Decisively equal */
 145                                 break;
 146                         }
 147
 148                         if (ra == WJB_END_ARRAY || ra == WJB_END_OBJECT)
 149                         {
 150                                 /*
 151                                  * There is no array or object to compare at this stage of
 152                                  * processing.  jbvArray/jbvObject values are compared
 153                                  * initially, at the WJB_BEGIN_ARRAY and WJB_BEGIN_OBJECT
 154                                  * tokens.
 155                                  */
 156                                 continue;
 157                         }
 158
 159                         if (va.type == vb.type)
 160                         {
 161                                 switch (va.type)
 162                                 {
 163                                         case jbvString:
 164                                         case jbvNull:
 165                                         case jbvNumeric:
 166                                         case jbvBool:
 167                                                 res = compareJsonbScalarValue(&va, &vb);
 168                                                 break;
 169                                         case jbvArray:
 170
 171                                                 /*
 172                                                  * This could be a "raw scalar" pseudo array.  That's
 173                                                  * a special case here though, since we still want the
 174                                                  * general type-based comparisons to apply, and as far
 175                                                  * as we're concerned a pseudo array is just a scalar.
 176                                                  */
 177                                                 if (va.val.array.rawScalar != vb.val.array.rawScalar)
 178                                                         res = (va.val.array.rawScalar) ? -1 : 1;
 179                                                 if (va.val.array.nElems != vb.val.array.nElems)
 180                                                         res = (va.val.array.nElems > vb.val.array.nElems) ? 1 : -1;
 181                                                 break;
 182                                         case jbvObject:
 183                                                 if (va.val.object.nPairs != vb.val.object.nPairs)
 184                                                         res = (va.val.object.nPairs > vb.val.object.nPairs) ? 1 : -1;
 185                                                 break;
 186                                         case jbvBinary:
 187                                                 elog(ERROR, "unexpected jbvBinary value");
 188                                 }
 189                         }
 190                         else
 191                         {
 192                                 /* Type-defined order */
 193                                 res = (va.type > vb.type) ? 1 : -1;
 194                         }
 195                 }
 196                 else
 197                 {
 198                         /*
 199                          * It's safe to assume that the types differed, and that the va
 200                          * and vb values passed were set.
 201                          *
 202                          * If the two values were of the same container type, then there'd
 203                          * have been a chance to observe the variation in the number of
 204                          * elements/pairs (when processing WJB_BEGIN_OBJECT, say).  They're
 205                          * either two heterogeneously-typed containers, or a container and
 206                          * some scalar type.
 207                          *
 208                          * We don't have to consider the WJB_END_ARRAY and WJB_END_OBJECT
 209                          * cases here, because we would have seen the corresponding
 210                          * WJB_BEGIN_ARRAY and WJB_BEGIN_OBJECT tokens first, and
 211                          * concluded that they don't match.
 212                          */
 213                         Assert(ra != WJB_END_ARRAY && ra != WJB_END_OBJECT);
 214                         Assert(rb != WJB_END_ARRAY && rb != WJB_END_OBJECT);
 215
 216                         Assert(va.type != vb.type);
 217                         Assert(va.type != jbvBinary);
 218                         Assert(vb.type != jbvBinary);
 219                         /* Type-defined order */
 220                         res = (va.type > vb.type) ? 1 : -1;
 221                 }
 222         }
 223         while (res == 0);
 224
 225         while (ita != NULL)
 226         {
 227                 JsonbIterator *i = ita->parent;
 228
 229                 pfree(ita);
 230                 ita = i;
 231         }
 232         while (itb != NULL)
 233         {
 234                 JsonbIterator *i = itb->parent;
 235
 236                 pfree(itb);
 237                 itb = i;
 238         }
 239
 240         return res;
 241 }
 242
 243 /*
 244  * Find value in object (i.e. the "value" part of some key/value pair in an
 245  * object), or find a matching element if we're looking through an array.  Do
 246  * so on the basis of equality of the object keys only, or alternatively
 247  * element values only, with a caller-supplied value "key".  The "flags"
 248  * argument allows the caller to specify which container types are of interest.
 249  *
 250  * This exported utility function exists to facilitate various cases concerned
 251  * with "containment".  If asked to look through an object, the caller had
 252  * better pass a Jsonb String, because their keys can only be strings.
 253  * Otherwise, for an array, any type of JsonbValue will do.
 254  *
 255  * In order to proceed with the search, it is necessary for callers to have
 256  * both specified an interest in exactly one particular container type with an
 257  * appropriate flag, as well as having the pointed-to Jsonb container be of
 258  * one of those same container types at the top level. (Actually, we just do
 259  * whichever makes sense to save callers the trouble of figuring it out - at
 260  * most one can make sense, because the container either points to an array
 261  * (possibly a "raw scalar" pseudo array) or an object.)
 262  *
 263  * Note that we can return a jbvBinary JsonbValue if this is called on an
 264  * object, but we never do so on an array.  If the caller asks to look through
 265  * a container type that is not of the type pointed to by the container,
 266  * immediately fall through and return NULL.  If we cannot find the value,
 267  * return NULL.  Otherwise, return palloc()'d copy of value.
 268  */
 269 JsonbValue *
 270 findJsonbValueFromContainer(JsonbContainer *container, uint32 flags,
 271                                                         JsonbValue *key)
 272 {
 273         JEntry     *children = container->children;
 274         int                     count = (container->header & JB_CMASK);
 275         JsonbValue *result = palloc(sizeof(JsonbValue));
 276
 277         Assert((flags & ~(JB_FARRAY | JB_FOBJECT)) == 0);
 278
 279         if (flags & JB_FARRAY & container->header)
 280         {
 281                 char       *base_addr = (char *) (children + count);
 282                 int                     i;
 283
 284                 for (i = 0; i < count; i++)
 285                 {
 286                         fillJsonbValue(children, i, base_addr, result);
 287
 288                         if (key->type == result->type)
 289                         {
 290                                 if (equalsJsonbScalarValue(key, result))
 291                                         return result;
 292                         }
 293                 }
 294         }
 295         else if (flags & JB_FOBJECT & container->header)
 296         {
 297                 /* Since this is an object, account for *Pairs* of Jentrys */
 298                 char       *base_addr = (char *) (children + count * 2);
 299                 uint32          stopLow = 0,
 300                                         stopMiddle;
 301
 302                 /* Object key past by caller must be a string */
 303                 Assert(key->type == jbvString);
 304
 305                 /* Binary search on object/pair keys *only* */
 306                 while (stopLow < count)
 307                 {
 308                         int                     index;
 309                         int                     difference;
 310                         JsonbValue      candidate;
 311
 312                         /*
 313                          * Note how we compensate for the fact that we're iterating
 314                          * through pairs (not entries) throughout.
 315                          */
 316                         stopMiddle = stopLow + (count - stopLow) / 2;
 317
 318                         index = stopMiddle * 2;
 319
 320                         candidate.type = jbvString;
 321                         candidate.val.string.val = base_addr + JBE_OFF(children, index);
 322                         candidate.val.string.len = JBE_LEN(children, index);
 323
 324                         difference = lengthCompareJsonbStringValue(&candidate, key);
 325
 326                         if (difference == 0)
 327                         {
 328                                 /* Found our key, return value */
 329                                 fillJsonbValue(children, index + 1, base_addr, result);
 330
 331                                 return result;
 332                         }
 333                         else
 334                         {
 335                                 if (difference < 0)
 336                                         stopLow = stopMiddle + 1;
 337                                 else
 338                                         count = stopMiddle;
 339                         }
 340                 }
 341         }
 342
 343         /* Not found */
 344         pfree(result);
 345         return NULL;
 346 }
 347
 348 /*
 349  * Get i-th value of a Jsonb array.
 350  *
 351  * Returns palloc()'d copy of the value, or NULL if it does not exist.
 352  */
 353 JsonbValue *
 354 getIthJsonbValueFromContainer(JsonbContainer *container, uint32 i)
 355 {
 356         JsonbValue *result;
 357         char       *base_addr;
 358         uint32          nelements;
 359
 360         if ((container->header & JB_FARRAY) == 0)
 361                 elog(ERROR, "not a jsonb array");
 362
 363         nelements = container->header & JB_CMASK;
 364         base_addr = (char *) &container->children[nelements];
 365
 366         if (i >= nelements)
 367                 return NULL;
 368
 369         result = palloc(sizeof(JsonbValue));
 370
 371         fillJsonbValue(container->children, i, base_addr, result);
 372
 373         return result;
 374 }
 375
 376 /*
 377  * A helper function to fill in a JsonbValue to represent an element of an
 378  * array, or a key or value of an object.
 379  *
 380  * A nested array or object will be returned as jbvBinary, ie. it won't be
 381  * expanded.
 382  */
 383 static void
 384 fillJsonbValue(JEntry *children, int index, char *base_addr, JsonbValue *result)
 385 {
 386         JEntry          entry = children[index];
 387
 388         if (JBE_ISNULL(entry))
 389         {
 390                 result->type = jbvNull;
 391         }
 392         else if (JBE_ISSTRING(entry))
 393         {
 394                 result->type = jbvString;
 395                 result->val.string.val = base_addr + JBE_OFF(children, index);
 396                 result->val.string.len = JBE_LEN(children, index);
 397                 Assert(result->val.string.len >= 0);
 398         }
 399         else if (JBE_ISNUMERIC(entry))
 400         {
 401                 result->type = jbvNumeric;
 402                 result->val.numeric = (Numeric) (base_addr + INTALIGN(JBE_OFF(children, index)));
 403         }
 404         else if (JBE_ISBOOL_TRUE(entry))
 405         {
 406                 result->type = jbvBool;
 407                 result->val.boolean = true;
 408         }
 409         else if (JBE_ISBOOL_FALSE(entry))
 410         {
 411                 result->type = jbvBool;
 412                 result->val.boolean = false;
 413         }
 414         else
 415         {
 416                 Assert(JBE_ISCONTAINER(entry));
 417                 result->type = jbvBinary;
 418                 result->val.binary.data = (JsonbContainer *) (base_addr + INTALIGN(JBE_OFF(children, index)));
 419                 result->val.binary.len = JBE_LEN(children, index) - (INTALIGN(JBE_OFF(children, index)) - JBE_OFF(children, index));
 420         }
 421 }
 422
 423 /*
 424  * Push JsonbValue into JsonbParseState.
 425  *
 426  * Used when parsing JSON tokens to form Jsonb, or when converting an in-memory
 427  * JsonbValue to a Jsonb.
 428  *
 429  * Initial state of *JsonbParseState is NULL, since it'll be allocated here
 430  * originally (caller will get JsonbParseState back by reference).
 431  *
 432  * Only sequential tokens pertaining to non-container types should pass a
 433  * JsonbValue.  There is one exception -- WJB_BEGIN_ARRAY callers may pass a
 434  * "raw scalar" pseudo array to append that.
 435  */
 436 JsonbValue *
 437 pushJsonbValue(JsonbParseState **pstate, JsonbIteratorToken seq,
 438                            JsonbValue *scalarVal)
 439 {
 440         JsonbValue *result = NULL;
 441
 442         switch (seq)
 443         {
 444                 case WJB_BEGIN_ARRAY:
 445                         Assert(!scalarVal || scalarVal->val.array.rawScalar);
 446                         *pstate = pushState(pstate);
 447                         result = &(*pstate)->contVal;
 448                         (*pstate)->contVal.type = jbvArray;
 449                         (*pstate)->contVal.val.array.nElems = 0;
 450                         (*pstate)->contVal.val.array.rawScalar = (scalarVal &&
 451                                                                                          scalarVal->val.array.rawScalar);
 452                         if (scalarVal && scalarVal->val.array.nElems > 0)
 453                         {
 454                                 /* Assume that this array is still really a scalar */
 455                                 Assert(scalarVal->type == jbvArray);
 456                                 (*pstate)->size = scalarVal->val.array.nElems;
 457                         }
 458                         else
 459                         {
 460                                 (*pstate)->size = 4;
 461                         }
 462                         (*pstate)->contVal.val.array.elems = palloc(sizeof(JsonbValue) *
 463                                                                                                                 (*pstate)->size);
 464                         break;
 465                 case WJB_BEGIN_OBJECT:
 466                         Assert(!scalarVal);
 467                         *pstate = pushState(pstate);
 468                         result = &(*pstate)->contVal;
 469                         (*pstate)->contVal.type = jbvObject;
 470                         (*pstate)->contVal.val.object.nPairs = 0;
 471                         (*pstate)->size = 4;
 472                         (*pstate)->contVal.val.object.pairs = palloc(sizeof(JsonbPair) *
 473                                                                                                                  (*pstate)->size);
 474                         break;
 475                 case WJB_KEY:
 476                         Assert(scalarVal->type == jbvString);
 477                         appendKey(*pstate, scalarVal);
 478                         break;
 479                 case WJB_VALUE:
 480                         Assert(IsAJsonbScalar(scalarVal) ||
 481                                    scalarVal->type == jbvBinary);
 482                         appendValue(*pstate, scalarVal);
 483                         break;
 484                 case WJB_ELEM:
 485                         Assert(IsAJsonbScalar(scalarVal) ||
 486                                    scalarVal->type == jbvBinary);
 487                         appendElement(*pstate, scalarVal);
 488                         break;
 489                 case WJB_END_OBJECT:
 490                         uniqueifyJsonbObject(&(*pstate)->contVal);
 491                         /* fall through! */
 492                 case WJB_END_ARRAY:
 493                         /* Steps here common to WJB_END_OBJECT case */
 494                         Assert(!scalarVal);
 495                         result = &(*pstate)->contVal;
 496
 497                         /*
 498                          * Pop stack and push current array/object as value in parent
 499                          * array/object
 500                          */
 501                         *pstate = (*pstate)->next;
 502                         if (*pstate)
 503                         {
 504                                 switch ((*pstate)->contVal.type)
 505                                 {
 506                                         case jbvArray:
 507                                                 appendElement(*pstate, result);
 508                                                 break;
 509                                         case jbvObject:
 510                                                 appendValue(*pstate, result);
 511                                                 break;
 512                                         default:
 513                                                 elog(ERROR, "invalid jsonb container type");
 514                                 }
 515                         }
 516                         break;
 517                 default:
 518                         elog(ERROR, "unrecognized jsonb sequential processing token");
 519         }
 520
 521         return result;
 522 }
 523
 524 /*
 525  * pushJsonbValue() worker:  Iteration-like forming of Jsonb
 526  */
 527 static JsonbParseState *
 528 pushState(JsonbParseState **pstate)
 529 {
 530         JsonbParseState *ns = palloc(sizeof(JsonbParseState));
 531
 532         ns->next = *pstate;
 533         return ns;
 534 }
 535
 536 /*
 537  * pushJsonbValue() worker:  Append a pair key to state when generating a Jsonb
 538  */
 539 static void
 540 appendKey(JsonbParseState *pstate, JsonbValue *string)
 541 {
 542         JsonbValue *object = &pstate->contVal;
 543
 544         Assert(object->type == jbvObject);
 545         Assert(string->type == jbvString);
 546
 547         if (object->val.object.nPairs >= JSONB_MAX_PAIRS)
 548                 ereport(ERROR,
 549                                 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 550                                  errmsg("number of jsonb object pairs exceeds the maximum allowed (%zu)",
 551                                                 JSONB_MAX_PAIRS)));
 552
 553         if (object->val.object.nPairs >= pstate->size)
 554         {
 555                 pstate->size *= 2;
 556                 object->val.object.pairs = repalloc(object->val.object.pairs,
 557                                                                                         sizeof(JsonbPair) * pstate->size);
 558         }
 559
 560         object->val.object.pairs[object->val.object.nPairs].key = *string;
 561         object->val.object.pairs[object->val.object.nPairs].order = object->val.object.nPairs;
 562 }
 563
 564 /*
 565  * pushJsonbValue() worker:  Append a pair value to state when generating a
 566  * Jsonb
 567  */
 568 static void
 569 appendValue(JsonbParseState *pstate, JsonbValue *scalarVal)
 570 {
 571         JsonbValue *object = &pstate->contVal;
 572
 573         Assert(object->type == jbvObject);
 574
 575         object->val.object.pairs[object->val.object.nPairs++].value = *scalarVal;
 576 }
 577
 578 /*
 579  * pushJsonbValue() worker:  Append an element to state when generating a Jsonb
 580  */
 581 static void
 582 appendElement(JsonbParseState *pstate, JsonbValue *scalarVal)
 583 {
 584         JsonbValue *array = &pstate->contVal;
 585
 586         Assert(array->type == jbvArray);
 587
 588         if (array->val.array.nElems >= JSONB_MAX_ELEMS)
 589                 ereport(ERROR,
 590                                 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 591                                  errmsg("number of jsonb array elements exceeds the maximum allowed (%zu)",
 592                                                 JSONB_MAX_ELEMS)));
 593
 594         if (array->val.array.nElems >= pstate->size)
 595         {
 596                 pstate->size *= 2;
 597                 array->val.array.elems = repalloc(array->val.array.elems,
 598                                                                                   sizeof(JsonbValue) * pstate->size);
 599         }
 600
 601         array->val.array.elems[array->val.array.nElems++] = *scalarVal;
 602 }
 603
 604 /*
 605  * Given a JsonbContainer, expand to JsonbIterator to iterate over items
 606  * fully expanded to in-memory representation for manipulation.
 607  *
 608  * See JsonbIteratorNext() for notes on memory management.
 609  */
 610 JsonbIterator *
 611 JsonbIteratorInit(JsonbContainer *container)
 612 {
 613         return iteratorFromContainer(container, NULL);
 614 }
 615
 616 /*
 617  * Get next JsonbValue while iterating
 618  *
 619  * Caller should initially pass their own, original iterator.  They may get
 620  * back a child iterator palloc()'d here instead.  The function can be relied
 621  * on to free those child iterators, lest the memory allocated for highly
 622  * nested objects become unreasonable, but only if callers don't end iteration
 623  * early (by breaking upon having found something in a search, for example).
 624  *
 625  * Callers in such a scenario, that are particularly sensitive to leaking
 626  * memory in a long-lived context may walk the ancestral tree from the final
 627  * iterator we left them with to its oldest ancestor, pfree()ing as they go.
 628  * They do not have to free any other memory previously allocated for iterators
 629  * but not accessible as direct ancestors of the iterator they're last passed
 630  * back.
 631  *
 632  * Returns "Jsonb sequential processing" token value.  Iterator "state"
 633  * reflects the current stage of the process in a less granular fashion, and is
 634  * mostly used here to track things internally with respect to particular
 635  * iterators.
 636  *
 637  * Clients of this function should not have to handle any jbvBinary values
 638  * (since recursive calls will deal with this), provided skipNested is false.
 639  * It is our job to expand the jbvBinary representation without bothering them
 640  * with it.  However, clients should not take it upon themselves to touch array
 641  * or Object element/pair buffers, since their element/pair pointers are
 642  * garbage.  Also, *val will not be set when returning WJB_END_ARRAY or
 643  * WJB_END_OBJECT, on the assumption that it's only useful to access values
 644  * when recursing in.
 645  */
 646 JsonbIteratorToken
 647 JsonbIteratorNext(JsonbIterator **it, JsonbValue *val, bool skipNested)
 648 {
 649         if (*it == NULL)
 650                 return WJB_DONE;
 651
 652         /*
 653          * When stepping into a nested container, we jump back here to start
 654          * processing the child. We will not recurse further in one call, because
 655          * processing the child will always begin in JBI_ARRAY_START or
 656          * JBI_OBJECT_START state.
 657          */
 658 recurse:
 659         switch ((*it)->state)
 660         {
 661                 case JBI_ARRAY_START:
 662                         /* Set v to array on first array call */
 663                         val->type = jbvArray;
 664                         val->val.array.nElems = (*it)->nElems;
 665
 666                         /*
 667                          * v->val.array.elems is not actually set, because we aren't doing
 668                          * a full conversion
 669                          */
 670                         val->val.array.rawScalar = (*it)->isScalar;
 671                         (*it)->i = 0;
 672                         /* Set state for next call */
 673                         (*it)->state = JBI_ARRAY_ELEM;
 674                         return WJB_BEGIN_ARRAY;
 675
 676                 case JBI_ARRAY_ELEM:
 677                         if ((*it)->i >= (*it)->nElems)
 678                         {
 679                                 /*
 680                                  * All elements within array already processed.  Report this
 681                                  * to caller, and give it back original parent iterator (which
 682                                  * independently tracks iteration progress at its level of
 683                                  * nesting).
 684                                  */
 685                                 *it = freeAndGetParent(*it);
 686                                 return WJB_END_ARRAY;
 687                         }
 688
 689                         fillJsonbValue((*it)->children, (*it)->i++, (*it)->dataProper, val);
 690
 691                         if (!IsAJsonbScalar(val) && !skipNested)
 692                         {
 693                                 /* Recurse into container. */
 694                                 *it = iteratorFromContainer(val->val.binary.data, *it);
 695                                 goto recurse;
 696                         }
 697                         else
 698                         {
 699                                 /*
 700                                  * Scalar item in array, or a container and caller didn't
 701                                  * want us to recurse into it.
 702                                  */
 703                                 return WJB_ELEM;
 704                         }
 705
 706                 case JBI_OBJECT_START:
 707                         /* Set v to object on first object call */
 708                         val->type = jbvObject;
 709                         val->val.object.nPairs = (*it)->nElems;
 710
 711                         /*
 712                          * v->val.object.pairs is not actually set, because we aren't
 713                          * doing a full conversion
 714                          */
 715                         (*it)->i = 0;
 716                         /* Set state for next call */
 717                         (*it)->state = JBI_OBJECT_KEY;
 718                         return WJB_BEGIN_OBJECT;
 719
 720                 case JBI_OBJECT_KEY:
 721                         if ((*it)->i >= (*it)->nElems)
 722                         {
 723                                 /*
 724                                  * All pairs within object already processed.  Report this to
 725                                  * caller, and give it back original containing iterator
 726                                  * (which independently tracks iteration progress at its level
 727                                  * of nesting).
 728                                  */
 729                                 *it = freeAndGetParent(*it);
 730                                 return WJB_END_OBJECT;
 731                         }
 732                         else
 733                         {
 734                                 /* Return key of a key/value pair.  */
 735                                 fillJsonbValue((*it)->children, (*it)->i * 2, (*it)->dataProper, val);
 736                                 if (val->type != jbvString)
 737                                         elog(ERROR, "unexpected jsonb type as object key");
 738
 739                                 /* Set state for next call */
 740                                 (*it)->state = JBI_OBJECT_VALUE;
 741                                 return WJB_KEY;
 742                         }
 743
 744                 case JBI_OBJECT_VALUE:
 745                         /* Set state for next call */
 746                         (*it)->state = JBI_OBJECT_KEY;
 747
 748                         fillJsonbValue((*it)->children, ((*it)->i++) * 2 + 1,
 749                                                    (*it)->dataProper, val);
 750
 751                         /*
 752                          * Value may be a container, in which case we recurse with new,
 753                          * child iterator (unless the caller asked not to, by passing
 754                          * skipNested).
 755                          */
 756                         if (!IsAJsonbScalar(val) && !skipNested)
 757                         {
 758                                 *it = iteratorFromContainer(val->val.binary.data, *it);
 759                                 goto recurse;
 760                         }
 761                         else
 762                                 return WJB_VALUE;
 763         }
 764
 765         elog(ERROR, "invalid iterator state");
 766         return -1;
 767 }
 768
 769 /*
 770  * Initialize an iterator for iterating all elements in a container.
 771  */
 772 static JsonbIterator *
 773 iteratorFromContainer(JsonbContainer *container, JsonbIterator *parent)
 774 {
 775         JsonbIterator *it;
 776
 777         it = palloc(sizeof(JsonbIterator));
 778         it->container = container;
 779         it->parent = parent;
 780         it->nElems = container->header & JB_CMASK;
 781
 782         /* Array starts just after header */
 783         it->children = container->children;
 784
 785         switch (container->header & (JB_FARRAY | JB_FOBJECT))
 786         {
 787                 case JB_FARRAY:
 788                         it->dataProper =
 789                                 (char *) it->children + it->nElems * sizeof(JEntry);
 790                         it->isScalar = (container->header & JB_FSCALAR) != 0;
 791                         /* This is either a "raw scalar", or an array */
 792                         Assert(!it->isScalar || it->nElems == 1);
 793
 794                         it->state = JBI_ARRAY_START;
 795                         break;
 796
 797                 case JB_FOBJECT:
 798
 799                         /*
 800                          * Offset reflects that nElems indicates JsonbPairs in an object.
 801                          * Each key and each value contain Jentry metadata just the same.
 802                          */
 803                         it->dataProper =
 804                                 (char *) it->children + it->nElems * sizeof(JEntry) * 2;
 805                         it->state = JBI_OBJECT_START;
 806                         break;
 807
 808                 default:
 809                         elog(ERROR, "unknown type of jsonb container");
 810         }
 811
 812         return it;
 813 }
 814
 815 /*
 816  * JsonbIteratorNext() worker:  Return parent, while freeing memory for current
 817  * iterator
 818  */
 819 static JsonbIterator *
 820 freeAndGetParent(JsonbIterator *it)
 821 {
 822         JsonbIterator *v = it->parent;
 823
 824         pfree(it);
 825         return v;
 826 }
 827
 828 /*
 829  * Worker for "contains" operator's function
 830  *
 831  * Formally speaking, containment is top-down, unordered subtree isomorphism.
 832  *
 833  * Takes iterators that belong to some container type.  These iterators
 834  * "belong" to those values in the sense that they've just been initialized in
 835  * respect of them by the caller (perhaps in a nested fashion).
 836  *
 837  * "val" is lhs Jsonb, and mContained is rhs Jsonb when called from top level.
 838  * We determine if mContained is contained within val.
 839  */
 840 bool
 841 JsonbDeepContains(JsonbIterator **val, JsonbIterator **mContained)
 842 {
 843         uint32          rval,
 844                                 rcont;
 845         JsonbValue      vval,
 846                                 vcontained;
 847
 848         /*
 849          * Guard against stack overflow due to overly complex Jsonb.
 850          *
 851          * Functions called here independently take this precaution, but that
 852          * might not be sufficient since this is also a recursive function.
 853          */
 854         check_stack_depth();
 855
 856         rval = JsonbIteratorNext(val, &vval, false);
 857         rcont = JsonbIteratorNext(mContained, &vcontained, false);
 858
 859         if (rval != rcont)
 860         {
 861                 /*
 862                  * The differing return values can immediately be taken as indicating
 863                  * two differing container types at this nesting level, which is
 864                  * sufficient reason to give up entirely (but it should be the case
 865                  * that they're both some container type).
 866                  */
 867                 Assert(rval == WJB_BEGIN_OBJECT || rval == WJB_BEGIN_ARRAY);
 868                 Assert(rcont == WJB_BEGIN_OBJECT || rcont == WJB_BEGIN_ARRAY);
 869                 return false;
 870         }
 871         else if (rcont == WJB_BEGIN_OBJECT)
 872         {
 873                 JsonbValue *lhsVal;             /* lhsVal is from pair in lhs object */
 874
 875                 Assert(vcontained.type == jbvObject);
 876
 877                 /* Work through rhs "is it contained within?" object */
 878                 for (;;)
 879                 {
 880                         rcont = JsonbIteratorNext(mContained, &vcontained, false);
 881
 882                         /*
 883                          * When we get through caller's rhs "is it contained within?"
 884                          * object without failing to find one of its values, it's
 885                          * contained.
 886                          */
 887                         if (rcont == WJB_END_OBJECT)
 888                                 return true;
 889
 890                         Assert(rcont == WJB_KEY);
 891
 892                         /* First, find value by key... */
 893                         lhsVal = findJsonbValueFromContainer((*val)->container,
 894                                                                                                  JB_FOBJECT,
 895                                                                                                  &vcontained);
 896
 897                         if (!lhsVal)
 898                                 return false;
 899
 900                         /*
 901                          * ...at this stage it is apparent that there is at least a key
 902                          * match for this rhs pair.
 903                          */
 904                         rcont = JsonbIteratorNext(mContained, &vcontained, true);
 905
 906                         Assert(rcont == WJB_VALUE);
 907
 908                         /*
 909                          * Compare rhs pair's value with lhs pair's value just found using
 910                          * key
 911                          */
 912                         if (lhsVal->type != vcontained.type)
 913                         {
 914                                 return false;
 915                         }
 916                         else if (IsAJsonbScalar(lhsVal))
 917                         {
 918                                 if (!equalsJsonbScalarValue(lhsVal, &vcontained))
 919                                         return false;
 920                         }
 921                         else
 922                         {
 923                                 /* Nested container value (object or array) */
 924                                 JsonbIterator *nestval,
 925                                                    *nestContained;
 926
 927                                 Assert(lhsVal->type == jbvBinary);
 928                                 Assert(vcontained.type == jbvBinary);
 929
 930                                 nestval = JsonbIteratorInit(lhsVal->val.binary.data);
 931                                 nestContained = JsonbIteratorInit(vcontained.val.binary.data);
 932
 933                                 /*
 934                                  * Match "value" side of rhs datum object's pair recursively.
 935                                  * It's a nested structure.
 936                                  *
 937                                  * Note that nesting still has to "match up" at the right
 938                                  * nesting sub-levels.  However, there need only be zero or
 939                                  * more matching pairs (or elements) at each nesting level
 940                                  * (provided the *rhs* pairs/elements *all* match on each
 941                                  * level), which enables searching nested structures for a
 942                                  * single String or other primitive type sub-datum quite
 943                                  * effectively (provided the user constructed the rhs nested
 944                                  * structure such that we "know where to look").
 945                                  *
 946                                  * In other words, the mapping of container nodes in the rhs
 947                                  * "vcontained" Jsonb to internal nodes on the lhs is
 948                                  * injective, and parent-child edges on the rhs must be mapped
 949                                  * to parent-child edges on the lhs to satisfy the condition
 950                                  * of containment (plus of course the mapped nodes must be
 951                                  * equal).
 952                                  */
 953                                 if (!JsonbDeepContains(&nestval, &nestContained))
 954                                         return false;
 955                         }
 956                 }
 957         }
 958         else if (rcont == WJB_BEGIN_ARRAY)
 959         {
 960                 JsonbValue *lhsConts = NULL;
 961                 uint32          nLhsElems = vval.val.array.nElems;
 962
 963                 Assert(vcontained.type == jbvArray);
 964
 965                 /*
 966                  * Handle distinction between "raw scalar" pseudo arrays, and real
 967                  * arrays.
 968                  *
 969                  * A raw scalar may contain another raw scalar, and an array may
 970                  * contain a raw scalar, but a raw scalar may not contain an array. We
 971                  * don't do something like this for the object case, since objects can
 972                  * only contain pairs, never raw scalars (a pair is represented by an
 973                  * rhs object argument with a single contained pair).
 974                  */
 975                 if (vval.val.array.rawScalar && !vcontained.val.array.rawScalar)
 976                         return false;
 977
 978                 /* Work through rhs "is it contained within?" array */
 979                 for (;;)
 980                 {
 981                         rcont = JsonbIteratorNext(mContained, &vcontained, true);
 982
 983                         /*
 984                          * When we get through caller's rhs "is it contained within?"
 985                          * array without failing to find one of its values, it's
 986                          * contained.
 987                          */
 988                         if (rcont == WJB_END_ARRAY)
 989                                 return true;
 990
 991                         Assert(rcont == WJB_ELEM);
 992
 993                         if (IsAJsonbScalar(&vcontained))
 994                         {
 995                                 if (!findJsonbValueFromContainer((*val)->container,
 996                                                                                                  JB_FARRAY,
 997                                                                                                  &vcontained))
 998                                         return false;
 999                         }
1000                         else
1001                         {
1002                                 uint32          i;
1003
1004                                 /*
1005                                  * If this is first container found in rhs array (at this
1006                                  * depth), initialize temp lhs array of containers
1007                                  */
1008                                 if (lhsConts == NULL)
1009                                 {
1010                                         uint32          j = 0;
1011
1012                                         /* Make room for all possible values */
1013                                         lhsConts = palloc(sizeof(JsonbValue) * nLhsElems);
1014
1015                                         for (i = 0; i < nLhsElems; i++)
1016                                         {
1017                                                 /* Store all lhs elements in temp array */
1018                                                 rcont = JsonbIteratorNext(val, &vval, true);
1019                                                 Assert(rcont == WJB_ELEM);
1020
1021                                                 if (vval.type == jbvBinary)
1022                                                         lhsConts[j++] = vval;
1023                                         }
1024
1025                                         /* No container elements in temp array, so give up now */
1026                                         if (j == 0)
1027                                                 return false;
1028
1029                                         /* We may have only partially filled array */
1030                                         nLhsElems = j;
1031                                 }
1032
1033                                 /* XXX: Nested array containment is O(N^2) */
1034                                 for (i = 0; i < nLhsElems; i++)
1035                                 {
1036                                         /* Nested container value (object or array) */
1037                                         JsonbIterator *nestval,
1038                                                            *nestContained;
1039                                         bool            contains;
1040
1041                                         nestval = JsonbIteratorInit(lhsConts[i].val.binary.data);
1042                                         nestContained = JsonbIteratorInit(vcontained.val.binary.data);
1043
1044                                         contains = JsonbDeepContains(&nestval, &nestContained);
1045
1046                                         if (nestval)
1047                                                 pfree(nestval);
1048                                         if (nestContained)
1049                                                 pfree(nestContained);
1050                                         if (contains)
1051                                                 break;
1052                                 }
1053
1054                                 /*
1055                                  * Report rhs container value is not contained if couldn't
1056                                  * match rhs container to *some* lhs cont
1057                                  */
1058                                 if (i == nLhsElems)
1059                                         return false;
1060                         }
1061                 }
1062         }
1063         else
1064         {
1065                 elog(ERROR, "invalid jsonb container type");
1066         }
1067
1068         elog(ERROR, "unexpectedly fell off end of jsonb container");
1069         return false;
1070 }
1071
1072 /*
1073  * Hash a JsonbValue scalar value, mixing the hash value into an existing
1074  * hash provided by the caller.
1075  *
1076  * Some callers may wish to independently XOR in JB_FOBJECT and JB_FARRAY
1077  * flags.
1078  */
1079 void
1080 JsonbHashScalarValue(const JsonbValue *scalarVal, uint32 *hash)
1081 {
1082         uint32          tmp;
1083
1084         /* Compute hash value for scalarVal */
1085         switch (scalarVal->type)
1086         {
1087                 case jbvNull:
1088                         tmp = 0x01;
1089                         break;
1090                 case jbvString:
1091                         tmp = DatumGetUInt32(hash_any((const unsigned char *) scalarVal->val.string.val,
1092                                                                                   scalarVal->val.string.len));
1093                         break;
1094                 case jbvNumeric:
1095                         /* Must hash equal numerics to equal hash codes */
1096                         tmp = DatumGetUInt32(DirectFunctionCall1(hash_numeric,
1097                                                                    NumericGetDatum(scalarVal->val.numeric)));
1098                         break;
1099                 case jbvBool:
1100                         tmp = scalarVal->val.boolean ? 0x02 : 0x04;
1101                         break;
1102                 default:
1103                         elog(ERROR, "invalid jsonb scalar type");
1104                         tmp = 0;                        /* keep compiler quiet */
1105                         break;
1106         }
1107
1108         /*
1109          * Combine hash values of successive keys, values and elements by rotating
1110          * the previous value left 1 bit, then XOR'ing in the new
1111          * key/value/element's hash value.
1112          */
1113         *hash = (*hash << 1) | (*hash >> 31);
1114         *hash ^= tmp;
1115 }
1116
1117 /*
1118  * Are two scalar JsonbValues of the same type a and b equal?
1119  */
1120 static bool
1121 equalsJsonbScalarValue(JsonbValue *aScalar, JsonbValue *bScalar)
1122 {
1123         if (aScalar->type == bScalar->type)
1124         {
1125                 switch (aScalar->type)
1126                 {
1127                         case jbvNull:
1128                                 return true;
1129                         case jbvString:
1130                                 return lengthCompareJsonbStringValue(aScalar, bScalar) == 0;
1131                         case jbvNumeric:
1132                                 return DatumGetBool(DirectFunctionCall2(numeric_eq,
1133                                                                            PointerGetDatum(aScalar->val.numeric),
1134                                                                          PointerGetDatum(bScalar->val.numeric)));
1135                         case jbvBool:
1136                                 return aScalar->val.boolean == bScalar->val.boolean;
1137
1138                         default:
1139                                 elog(ERROR, "invalid jsonb scalar type");
1140                 }
1141         }
1142         elog(ERROR, "jsonb scalar type mismatch");
1143         return -1;
1144 }
1145
1146 /*
1147  * Compare two scalar JsonbValues, returning -1, 0, or 1.
1148  *
1149  * Strings are compared using the default collation.  Used by B-tree
1150  * operators, where a lexical sort order is generally expected.
1151  */
1152 static int
1153 compareJsonbScalarValue(JsonbValue *aScalar, JsonbValue *bScalar)
1154 {
1155         if (aScalar->type == bScalar->type)
1156         {
1157                 switch (aScalar->type)
1158                 {
1159                         case jbvNull:
1160                                 return 0;
1161                         case jbvString:
1162                                 return varstr_cmp(aScalar->val.string.val,
1163                                                                   aScalar->val.string.len,
1164                                                                   bScalar->val.string.val,
1165                                                                   bScalar->val.string.len,
1166                                                                   DEFAULT_COLLATION_OID);
1167                         case jbvNumeric:
1168                                 return DatumGetInt32(DirectFunctionCall2(numeric_cmp,
1169                                                                            PointerGetDatum(aScalar->val.numeric),
1170                                                                          PointerGetDatum(bScalar->val.numeric)));
1171                         case jbvBool:
1172                                 if (aScalar->val.boolean == bScalar->val.boolean)
1173                                         return 0;
1174                                 else if (aScalar->val.boolean > bScalar->val.boolean)
1175                                         return 1;
1176                                 else
1177                                         return -1;
1178                         default:
1179                                 elog(ERROR, "invalid jsonb scalar type");
1180                 }
1181         }
1182         elog(ERROR, "jsonb scalar type mismatch");
1183         return -1;
1184 }
1185
1186
1187 /*
1188  * Functions for manipulating the resizeable buffer used by convertJsonb and
1189  * its subroutines.
1190  */
1191
1192 /*
1193  * Reserve 'len' bytes, at the end of the buffer, enlarging it if necessary.
1194  * Returns the offset to the reserved area. The caller is expected to fill
1195  * the reserved area later with copyToBuffer().
1196  */
1197 static int
1198 reserveFromBuffer(StringInfo buffer, int len)
1199 {
1200         int                     offset;
1201
1202         /* Make more room if needed */
1203         enlargeStringInfo(buffer, len);
1204
1205         /* remember current offset */
1206         offset = buffer->len;
1207
1208         /* reserve the space */
1209         buffer->len += len;
1210
1211         /*
1212          * Keep a trailing null in place, even though it's not useful for us;
1213          * it seems best to preserve the invariants of StringInfos.
1214          */
1215         buffer->data[buffer->len] = '\0';
1216
1217         return offset;
1218 }
1219
1220 /*
1221  * Copy 'len' bytes to a previously reserved area in buffer.
1222  */
1223 static void
1224 copyToBuffer(StringInfo buffer, int offset, const char *data, int len)
1225 {
1226         memcpy(buffer->data + offset, data, len);
1227 }
1228
1229 /*
1230  * A shorthand for reserveFromBuffer + copyToBuffer.
1231  */
1232 static void
1233 appendToBuffer(StringInfo buffer, const char *data, int len)
1234 {
1235         int                     offset;
1236
1237         offset = reserveFromBuffer(buffer, len);
1238         copyToBuffer(buffer, offset, data, len);
1239 }
1240
1241
1242 /*
1243  * Append padding, so that the length of the StringInfo is int-aligned.
1244  * Returns the number of padding bytes appended.
1245  */
1246 static short
1247 padBufferToInt(StringInfo buffer)
1248 {
1249         int                     padlen,
1250                                 p,
1251                                 offset;
1252
1253         padlen = INTALIGN(buffer->len) - buffer->len;
1254
1255         offset = reserveFromBuffer(buffer, padlen);
1256
1257         /* padlen must be small, so this is probably faster than a memset */
1258         for (p = 0; p < padlen; p++)
1259                 buffer->data[offset + p] = '\0';
1260
1261         return padlen;
1262 }
1263
1264 /*
1265  * Given a JsonbValue, convert to Jsonb. The result is palloc'd.
1266  */
1267 static Jsonb *
1268 convertToJsonb(JsonbValue *val)
1269 {
1270         StringInfoData buffer;
1271         JEntry          jentry;
1272         Jsonb      *res;
1273
1274         /* Should not already have binary representation */
1275         Assert(val->type != jbvBinary);
1276
1277         /* Allocate an output buffer. It will be enlarged as needed */
1278         initStringInfo(&buffer);
1279
1280         /* Make room for the varlena header */
1281         reserveFromBuffer(&buffer, sizeof(VARHDRSZ));
1282
1283         convertJsonbValue(&buffer, &jentry, val, 0);
1284
1285         /*
1286          * Note: the JEntry of the root is discarded. Therefore the root
1287          * JsonbContainer struct must contain enough information to tell what
1288          * kind of value it is.
1289          */
1290
1291         res = (Jsonb *) buffer.data;
1292
1293         SET_VARSIZE(res, buffer.len);
1294
1295         return res;
1296 }
1297
1298 /*
1299  * Subroutine of convertJsonb: serialize a single JsonbValue into buffer.
1300  *
1301  * The JEntry header for this node is returned in *header. It is filled in
1302  * with the length of this value, but if it is stored in an array or an
1303  * object (which is always, except for the root node), it is the caller's
1304  * responsibility to adjust it with the offset within the container.
1305  *
1306  * If the value is an array or an object, this recurses. 'level' is only used
1307  * for debugging purposes.
1308  */
1309 static void
1310 convertJsonbValue(StringInfo buffer, JEntry *header, JsonbValue *val, int level)
1311 {
1312         check_stack_depth();
1313
1314         if (!val)
1315                 return;
1316
1317         if (IsAJsonbScalar(val) || val->type == jbvBinary)
1318                 convertJsonbScalar(buffer, header, val);
1319         else if (val->type == jbvArray)
1320                 convertJsonbArray(buffer, header, val, level);
1321         else if (val->type == jbvObject)
1322                 convertJsonbObject(buffer, header, val, level);
1323         else
1324                 elog(ERROR, "unknown type of jsonb container");
1325 }
1326
1327 static void
1328 convertJsonbArray(StringInfo buffer, JEntry *pheader, JsonbValue *val, int level)
1329 {
1330         int                     offset;
1331         int                     metaoffset;
1332         int                     i;
1333         int                     totallen;
1334         uint32          header;
1335
1336         /* Initialize pointer into conversion buffer at this level */
1337         offset = buffer->len;
1338
1339         padBufferToInt(buffer);
1340
1341         /*
1342          * Construct the header Jentry, stored in the beginning of the variable-
1343          * length payload.
1344          */
1345         header = val->val.array.nElems | JB_FARRAY;
1346         if (val->val.array.rawScalar)
1347         {
1348                 Assert(val->val.array.nElems == 1);
1349                 Assert(level == 0);
1350                 header |= JB_FSCALAR;
1351         }
1352
1353         appendToBuffer(buffer, (char *) &header, sizeof(uint32));
1354         /* reserve space for the JEntries of the elements. */
1355         metaoffset = reserveFromBuffer(buffer, sizeof(JEntry) * val->val.array.nElems);
1356
1357         totallen = 0;
1358         for (i = 0; i < val->val.array.nElems; i++)
1359         {
1360                 JsonbValue *elem = &val->val.array.elems[i];
1361                 int                     len;
1362                 JEntry          meta;
1363
1364                 convertJsonbValue(buffer, &meta, elem, level + 1);
1365                 len = meta & JENTRY_POSMASK;
1366                 totallen += len;
1367
1368                 if (totallen > JENTRY_POSMASK)
1369                         ereport(ERROR,
1370                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1371                                          errmsg("total size of jsonb array elements exceeds the maximum of %u bytes",
1372                                                         JENTRY_POSMASK)));
1373
1374                 if (i > 0)
1375                         meta = (meta & ~JENTRY_POSMASK) | totallen;
1376                 copyToBuffer(buffer, metaoffset, (char *) &meta, sizeof(JEntry));
1377                 metaoffset += sizeof(JEntry);
1378         }
1379
1380         totallen = buffer->len - offset;
1381
1382         /* Initialize the header of this node, in the container's JEntry array */
1383         *pheader = JENTRY_ISCONTAINER | totallen;
1384 }
1385
1386 static void
1387 convertJsonbObject(StringInfo buffer, JEntry *pheader, JsonbValue *val, int level)
1388 {
1389         uint32          header;
1390         int                     offset;
1391         int                     metaoffset;
1392         int                     i;
1393         int                     totallen;
1394
1395         /* Initialize pointer into conversion buffer at this level */
1396         offset = buffer->len;
1397
1398         padBufferToInt(buffer);
1399
1400         /* Initialize header */
1401         header = val->val.object.nPairs | JB_FOBJECT;
1402         appendToBuffer(buffer, (char *) &header, sizeof(uint32));
1403
1404         /* reserve space for the JEntries of the keys and values */
1405         metaoffset = reserveFromBuffer(buffer, sizeof(JEntry) * val->val.object.nPairs * 2);
1406
1407         totallen = 0;
1408         for (i = 0; i < val->val.object.nPairs; i++)
1409         {
1410                 JsonbPair *pair = &val->val.object.pairs[i];
1411                 int len;
1412                 JEntry meta;
1413
1414                 /* put key */
1415                 convertJsonbScalar(buffer, &meta, &pair->key);
1416
1417                 len = meta & JENTRY_POSMASK;
1418                 totallen += len;
1419
1420                 if (totallen > JENTRY_POSMASK)
1421                         ereport(ERROR,
1422                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1423                                          errmsg("total size of jsonb array elements exceeds the maximum of %u bytes",
1424                                                         JENTRY_POSMASK)));
1425
1426                 if (i > 0)
1427                         meta = (meta & ~JENTRY_POSMASK) | totallen;
1428                 copyToBuffer(buffer, metaoffset, (char *) &meta, sizeof(JEntry));
1429                 metaoffset += sizeof(JEntry);
1430
1431                 convertJsonbValue(buffer, &meta, &pair->value, level);
1432                 len = meta & JENTRY_POSMASK;
1433                 totallen += len;
1434
1435                 if (totallen > JENTRY_POSMASK)
1436                         ereport(ERROR,
1437                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1438                                          errmsg("total size of jsonb array elements exceeds the maximum of %u bytes",
1439                                                         JENTRY_POSMASK)));
1440
1441                 meta = (meta & ~JENTRY_POSMASK) | totallen;
1442                 copyToBuffer(buffer, metaoffset, (char *) &meta, sizeof(JEntry));
1443                 metaoffset += sizeof(JEntry);
1444         }
1445
1446         totallen = buffer->len - offset;
1447
1448         *pheader = JENTRY_ISCONTAINER | totallen;
1449 }
1450
1451 static void
1452 convertJsonbScalar(StringInfo buffer, JEntry *jentry, JsonbValue *scalarVal)
1453 {
1454         int                     numlen;
1455         short           padlen;
1456
1457         switch (scalarVal->type)
1458         {
1459                 case jbvNull:
1460                         *jentry = JENTRY_ISNULL;
1461                         break;
1462
1463                 case jbvString:
1464                         appendToBuffer(buffer, scalarVal->val.string.val, scalarVal->val.string.len);
1465
1466                         *jentry = scalarVal->val.string.len;
1467                         break;
1468
1469                 case jbvNumeric:
1470                         numlen = VARSIZE_ANY(scalarVal->val.numeric);
1471                         padlen = padBufferToInt(buffer);
1472
1473                         appendToBuffer(buffer, (char *) scalarVal->val.numeric, numlen);
1474
1475                         *jentry = JENTRY_ISNUMERIC | (padlen + numlen);
1476                         break;
1477
1478                 case jbvBool:
1479                         *jentry = (scalarVal->val.boolean) ?
1480                                 JENTRY_ISBOOL_TRUE : JENTRY_ISBOOL_FALSE;
1481                         break;
1482
1483                 default:
1484                         elog(ERROR, "invalid jsonb scalar type");
1485         }
1486 }
1487
1488 /*
1489  * Compare two jbvString JsonbValue values, a and b.
1490  *
1491  * This is a special qsort() comparator used to sort strings in certain
1492  * internal contexts where it is sufficient to have a well-defined sort order.
1493  * In particular, object pair keys are sorted according to this criteria to
1494  * facilitate cheap binary searches where we don't care about lexical sort
1495  * order.
1496  *
1497  * a and b are first sorted based on their length.  If a tie-breaker is
1498  * required, only then do we consider string binary equality.
1499  */
1500 static int
1501 lengthCompareJsonbStringValue(const void *a, const void *b)
1502 {
1503         const JsonbValue *va = (const JsonbValue *) a;
1504         const JsonbValue *vb = (const JsonbValue *) b;
1505         int                     res;
1506
1507         Assert(va->type == jbvString);
1508         Assert(vb->type == jbvString);
1509
1510         if (va->val.string.len == vb->val.string.len)
1511         {
1512                 res = memcmp(va->val.string.val, vb->val.string.val, va->val.string.len);
1513         }
1514         else
1515         {
1516                 res = (va->val.string.len > vb->val.string.len) ? 1 : -1;
1517         }
1518
1519         return res;
1520 }
1521
1522 /*
1523  * qsort_arg() comparator to compare JsonbPair values.
1524  *
1525  * Third argument 'binequal' may point to a bool. If it's set, *binequal is set
1526  * to true iff a and b have full binary equality, since some callers have an
1527  * interest in whether the two values are equal or merely equivalent.
1528  *
1529  * N.B: String comparisons here are "length-wise"
1530  *
1531  * Pairs with equals keys are ordered such that the order field is respected.
1532  */
1533 static int
1534 lengthCompareJsonbPair(const void *a, const void *b, void *binequal)
1535 {
1536         const JsonbPair *pa = (const JsonbPair *) a;
1537         const JsonbPair *pb = (const JsonbPair *) b;
1538         int                     res;
1539
1540         res = lengthCompareJsonbStringValue(&pa->key, &pb->key);
1541         if (res == 0 && binequal)
1542                 *((bool *) binequal) = true;
1543
1544         /*
1545          * Guarantee keeping order of equal pair.  Unique algorithm will prefer
1546          * first element as value.
1547          */
1548         if (res == 0)
1549                 res = (pa->order > pb->order) ? -1 : 1;
1550
1551         return res;
1552 }
1553
1554 /*
1555  * Sort and unique-ify pairs in JsonbValue object
1556  */
1557 static void
1558 uniqueifyJsonbObject(JsonbValue *object)
1559 {
1560         bool            hasNonUniq = false;
1561
1562         Assert(object->type == jbvObject);
1563
1564         if (object->val.object.nPairs > 1)
1565                 qsort_arg(object->val.object.pairs, object->val.object.nPairs, sizeof(JsonbPair),
1566                                   lengthCompareJsonbPair, &hasNonUniq);
1567
1568         if (hasNonUniq)
1569         {
1570                 JsonbPair  *ptr = object->val.object.pairs + 1,
1571                                    *res = object->val.object.pairs;
1572
1573                 while (ptr - object->val.object.pairs < object->val.object.nPairs)
1574                 {
1575                         /* Avoid copying over duplicate */
1576                         if (lengthCompareJsonbStringValue(ptr, res) != 0)
1577                         {
1578                                 res++;
1579                                 if (ptr != res)
1580                                         memcpy(res, ptr, sizeof(JsonbPair));
1581                         }
1582                         ptr++;
1583                 }
1584
1585                 object->val.object.nPairs = res + 1 - object->val.object.pairs;
1586         }
1587 }