Debian Codegraph @

src/backend/utils/adt/jsonb_util.c

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