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