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

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