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