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