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