Introduce jsonb, a structured format for storing json.

The new format accepts exactly the same data as the json type. However, it is
stored in a format that does not require reparsing the orgiginal text in order
to process it, making it much more suitable for indexing and other operations.
Insignificant whitespace is discarded, and the order of object keys is not
preserved. Neither are duplicate object keys kept - the later value for a given
key is the only one stored.

The new type has all the functions and operators that the json type has,
with the exception of the json generation functions (to_json, json_agg etc.)
and with identical semantics. In addition, there are operator classes for
hash and btree indexing, and two classes for GIN indexing, that have no
equivalent in the json type.

This feature grew out of previous work by Oleg Bartunov and Teodor Sigaev, which
was intended to provide similar facilities to a nested hstore type, but which
in the end proved to have some significant compatibility issues.

Authors: Oleg Bartunov,  Teodor Sigaev, Peter Geoghegan and Andrew Dunstan.
Review: Andres Freund

1 files changed, 1872 insertions, 0 deletions

diff --git a/src/backend/utils/adt/jsonb_util.c b/src/backend/utils/adt/jsonb_util.c
new file mode 100644
index 00000000000..4a1d4451301
--- /dev/null
+++ b/src/backend/utils/adt/jsonb_util.c
@@ -0,0 +1,1872 @@
+/*-------------------------------------------------------------------------
+ *
+ * jsonb_util.c
+ *	  Utilities for jsonb datatype
+ *
+ * Copyright (c) 2014, PostgreSQL Global Development Group
+ *
+ *
+ * IDENTIFICATION
+ *	  src/backend/utils/adt/jsonb_util.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/hash.h"
+#include "catalog/pg_collation.h"
+#include "catalog/pg_type.h"
+#include "miscadmin.h"
+#include "utils/builtins.h"
+#include "utils/jsonb.h"
+#include "utils/memutils.h"
+
+/*
+ * Twice as many values may be stored within pairs (for an Object) than within
+ * elements (for an Array), modulo the current MaxAllocSize limitation.  Note
+ * that JSONB_MAX_PAIRS is derived from the number of possible pairs, not
+ * values (as is the case for arrays and their elements), because we're
+ * concerned about limitations on the representation of the number of pairs.
+ * Over twice the memory is required to store n JsonbPairs as n JsonbValues.
+ * It only takes exactly twice as much disk space for storage, though.  The
+ * JsonbPair (not an actual pair of values) representation is used here because
+ * that is what is subject to the MaxAllocSize restriction when building an
+ * object.
+ */
+#define JSONB_MAX_ELEMS (Min(MaxAllocSize / sizeof(JsonbValue), JENTRY_POSMASK))
+#define JSONB_MAX_PAIRS (Min(MaxAllocSize / sizeof(JsonbPair), \
+							 JENTRY_POSMASK))
+
+/*
+ * State used while converting an arbitrary JsonbValue into a Jsonb value
+ * (4-byte varlena uncompressed representation of a Jsonb)
+ *
+ * ConvertLevel:  Bookkeeping around particular level when converting.
+ */
+typedef struct convertLevel
+{
+	uint32		i;		/* Iterates once per element, or once per pair */
+	uint32	   *header; /* Pointer to current container header */
+	JEntry	   *meta;	/* This level's metadata */
+	char	   *begin;	/* Pointer into convertState.buffer */
+} convertLevel;
+
+/*
+ * convertState:  Overall bookkeeping state for conversion
+ */
+typedef struct convertState
+{
+	/* Preallocated buffer in which to form varlena/Jsonb value */
+	Jsonb			   *buffer;
+	/* Pointer into buffer */
+	char			   *ptr;
+
+	/* State for  */
+	convertLevel	   *allState,	/* Overall state array */
+					   *contPtr;	/* Cur container pointer (in allState) */
+
+	/* Current size of buffer containing allState array */
+	Size				levelSz;
+
+}	convertState;
+
+static int compareJsonbScalarValue(JsonbValue * a, JsonbValue * b);
+static int lexicalCompareJsonbStringValue(const void *a, const void *b);
+static Size convertJsonb(JsonbValue * val, Jsonb* buffer);
+static inline short addPaddingInt(convertState * cstate);
+static void walkJsonbValueConversion(JsonbValue * val, convertState * cstate,
+									 uint32 nestlevel);
+static void putJsonbValueConversion(convertState * cstate, JsonbValue * val,
+									uint32 flags, uint32 level);
+static void putScalarConversion(convertState * cstate, JsonbValue * scalarVal,
+								uint32 level, uint32 i);
+static void iteratorFromContainerBuf(JsonbIterator * it, char *buffer);
+static bool formIterIsContainer(JsonbIterator ** it, JsonbValue * val,
+								JEntry * ent, bool skipNested);
+static JsonbIterator *freeAndGetParent(JsonbIterator * it);
+static JsonbParseState *pushState(JsonbParseState ** pstate);
+static void appendKey(JsonbParseState * pstate, JsonbValue * scalarVal);
+static void appendValue(JsonbParseState * pstate, JsonbValue * scalarVal);
+static void appendElement(JsonbParseState * pstate, JsonbValue * scalarVal);
+static int lengthCompareJsonbStringValue(const void *a, const void *b, void *arg);
+static int lengthCompareJsonbPair(const void *a, const void *b, void *arg);
+static void uniqueifyJsonbObject(JsonbValue * object);
+static void uniqueifyJsonbArray(JsonbValue * array);
+
+/*
+ * Turn an in-memory JsonbValue into a Jsonb for on-disk storage.
+ *
+ * There isn't a JsonbToJsonbValue(), because generally we find it more
+ * convenient to directly iterate through the Jsonb representation and only
+ * really convert nested scalar values.  formIterIsContainer() does this, so
+ * that clients of the iteration code don't have to directly deal with the
+ * binary representation (JsonbDeepContains() is a notable exception, although
+ * all exceptions are internal to this module).  In general, functions that
+ * accept a JsonbValue argument are concerned with the manipulation of scalar
+ * values, or simple containers of scalar values, where it would be
+ * inconvenient to deal with a great amount of other state.
+ */
+Jsonb *
+JsonbValueToJsonb(JsonbValue * val)
+{
+	Jsonb	   *out;
+	Size		sz;
+
+	if (IsAJsonbScalar(val))
+	{
+		/* Scalar value */
+		JsonbParseState *pstate = NULL;
+		JsonbValue *res;
+		JsonbValue	scalarArray;
+
+		scalarArray.type = jbvArray;
+		scalarArray.array.rawScalar = true;
+		scalarArray.array.nElems = 1;
+
+		pushJsonbValue(&pstate, WJB_BEGIN_ARRAY, &scalarArray);
+		pushJsonbValue(&pstate, WJB_ELEM, val);
+		res = pushJsonbValue(&pstate, WJB_END_ARRAY, NULL);
+
+		out = palloc(VARHDRSZ + res->estSize);
+		sz = convertJsonb(res, out);
+		Assert(sz <= res->estSize);
+		SET_VARSIZE(out, sz + VARHDRSZ);
+	}
+	else if (val->type == jbvObject || val->type == jbvArray)
+	{
+		out = palloc(VARHDRSZ + val->estSize);
+		sz = convertJsonb(val, out);
+		Assert(sz <= val->estSize);
+		SET_VARSIZE(out, VARHDRSZ + sz);
+	}
+	else
+	{
+		Assert(val->type == jbvBinary);
+		out = palloc(VARHDRSZ + val->binary.len);
+		SET_VARSIZE(out, VARHDRSZ + val->binary.len);
+		memcpy(VARDATA(out), val->binary.data, val->binary.len);
+	}
+
+	return out;
+}
+
+/*
+ * BT comparator worker function.  Returns an integer less than, equal to, or
+ * greater than zero, indicating whether a is less than, equal to, or greater
+ * than b.  Consistent with the requirements for a B-Tree operator class
+ *
+ * Strings are compared lexically, in contrast with other places where we use a
+ * much simpler comparator logic for searching through Strings.  Since this is
+ * called from B-Tree support function 1, we're careful about not leaking
+ * memory here.
+ */
+int
+compareJsonbSuperHeaderValue(JsonbSuperHeader a, JsonbSuperHeader b)
+{
+	JsonbIterator *ita,
+				  *itb;
+	int			res = 0;
+
+	ita = JsonbIteratorInit(a);
+	itb = JsonbIteratorInit(b);
+
+	do
+	{
+		JsonbValue	va,
+					vb;
+		int			ra,
+					rb;
+
+		ra = JsonbIteratorNext(&ita, &va, false);
+		rb = JsonbIteratorNext(&itb, &vb, false);
+
+		/*
+		 * To a limited extent we'll redundantly iterate over an array/object
+		 * while re-performing the same test without any reasonable expectation
+		 * of the same container types having differing lengths (as when we
+		 * process a WJB_BEGIN_OBJECT, and later the corresponding
+		 * WJB_END_OBJECT), but no matter.
+		 */
+		if (ra == rb)
+		{
+			if (ra == WJB_DONE)
+			{
+				/* Decisively equal */
+				break;
+			}
+
+			if (va.type == vb.type)
+			{
+				switch (va.type)
+				{
+					case jbvString:
+						res = lexicalCompareJsonbStringValue(&va, &vb);
+						break;
+					case jbvNull:
+					case jbvNumeric:
+					case jbvBool:
+						res = compareJsonbScalarValue(&va, &vb);
+						break;
+					case jbvArray:
+						/*
+						 * This could be a "raw scalar" pseudo array.  That's a
+						 * special case here though, since we still want the
+						 * general type-based comparisons to apply, and as far
+						 * as we're concerned a pseudo array is just a scalar.
+						 */
+						if (va.array.rawScalar != vb.array.rawScalar)
+							res = (va.array.rawScalar) ? -1 : 1;
+						if (va.array.nElems != vb.array.nElems)
+							res = (va.array.nElems > vb.array.nElems) ? 1 : -1;
+						break;
+					case jbvObject:
+						if (va.object.nPairs != vb.object.nPairs)
+							res = (va.object.nPairs > vb.object.nPairs) ? 1 : -1;
+						break;
+					case jbvBinary:
+						elog(ERROR, "unexpected jbvBinary value");
+				}
+			}
+			else
+			{
+				/* Type-defined order */
+				res = (va.type > vb.type) ? 1 : -1;
+			}
+		}
+		else
+		{
+			/*
+			 * It's safe to assume that the types differed.
+			 *
+			 * If the two values were the same container type, then there'd
+			 * have been a chance to observe the variation in the number of
+			 * elements/pairs (when processing WJB_BEGIN_OBJECT, say).  They
+			 * can't be scalar types either, because then they'd have to be
+			 * contained in containers already ruled unequal due to differing
+			 * numbers of pairs/elements, or already directly ruled unequal
+			 * with a call to the underlying type's comparator.
+			 */
+			Assert(va.type != vb.type);
+			Assert(va.type == jbvArray || va.type == jbvObject);
+			Assert(vb.type == jbvArray || vb.type == jbvObject);
+			/* Type-defined order */
+			res = (va.type > vb.type) ? 1 : -1;
+		}
+	}
+	while (res == 0);
+
+	while (ita != NULL)
+	{
+		JsonbIterator *i = ita->parent;
+		pfree(ita);
+		ita = i;
+	}
+	while (itb != NULL)
+	{
+		JsonbIterator *i = itb->parent;
+		pfree(itb);
+		itb = i;
+	}
+
+	return res;
+}
+
+/*
+ * Find value in object (i.e. the "value" part of some key/value pair in an
+ * object), or find a matching element if we're looking through an array.  Do
+ * so on the basis of equality of the object keys only, or alternatively
+ * element values only, with a caller-supplied value "key".  The "flags"
+ * argument allows the caller to specify which container types are of interest.
+ *
+ * This exported utility function exists to facilitate various cases concerned
+ * with "containment".  If asked to look through an object, the caller had
+ * better pass a Jsonb String, because their keys can only be strings.
+ * Otherwise, for an array, any type of JsonbValue will do.
+ *
+ * In order to proceed with the search, it is necessary for callers to have
+ * both specified an interest in exactly one particular container type with an
+ * appropriate flag, as well as having the pointed-to Jsonb superheader be of
+ * one of those same container types at the top level. (Actually, we just do
+ * whichever makes sense to save callers the trouble of figuring it out - at
+ * most one can make sense, because the super header either points to an array
+ * (possible a "raw scalar" pseudo array) or an object.)
+ *
+ * Note that we can return a jbvBinary JsonbValue if this is called on an
+ * object, but we never do so on an array.  If the caller asks to look through
+ * a container type that is not of the type pointed to by the superheader,
+ * immediately fall through and return NULL.  If we cannot find the value,
+ * return NULL.  Otherwise, return palloc()'d copy of value.
+ *
+ * lowbound can be NULL, but if not it's used to establish a point at which to
+ * start searching.  If the value searched for is found, then lowbound is then
+ * set to an offset into the array or object.  Typically, this is used to
+ * exploit the ordering of objects to avoid redundant work, by also sorting a
+ * list of items to be checked using the internal sort criteria for objects
+ * (object pair keys), and then, when searching for the second or subsequent
+ * item, picking it up where we left off knowing that the second or subsequent
+ * item can not be at a point below the low bound set when the first was found.
+ * This is only useful for objects, not arrays (which have a user-defined
+ * order), so array superheader Jsonbs should just pass NULL.  Moreover, it's
+ * only useful because we only match object pairs on the basis of their key, so
+ * presumably anyone exploiting this is only interested in matching Object keys
+ * with a String.  lowbound is given in units of pairs, not underlying values.
+ */
+JsonbValue *
+findJsonbValueFromSuperHeader(JsonbSuperHeader sheader, uint32 flags,
+							  uint32 *lowbound, JsonbValue * key)
+{
+	uint32			superheader = *(uint32 *) sheader;
+	JEntry		   *array = (JEntry *) (sheader + sizeof(uint32));
+	int				count = (superheader & JB_CMASK);
+	JsonbValue	   *result = palloc(sizeof(JsonbValue));
+
+	Assert((flags & ~(JB_FARRAY | JB_FOBJECT)) == 0);
+
+	if (flags & JB_FARRAY & superheader)
+	{
+		char	   *data = (char *) (array + (superheader & JB_CMASK));
+		int			i;
+
+		for (i = 0; i < count; i++)
+		{
+			JEntry	   *e = array + i;
+
+			if (JBE_ISNULL(*e) && key->type == jbvNull)
+			{
+				result->type = jbvNull;
+				result->estSize = sizeof(JEntry);
+			}
+			else if (JBE_ISSTRING(*e) && key->type == jbvString)
+			{
+				result->type = jbvString;
+				result->string.val = data + JBE_OFF(*e);
+				result->string.len = JBE_LEN(*e);
+				result->estSize = sizeof(JEntry) + result->string.len;
+			}
+			else if (JBE_ISNUMERIC(*e) && key->type == jbvNumeric)
+			{
+				result->type = jbvNumeric;
+				result->numeric = (Numeric) (data + INTALIGN(JBE_OFF(*e)));
+				result->estSize = 2 * sizeof(JEntry) +
+					VARSIZE_ANY(result->numeric);
+			}
+			else if (JBE_ISBOOL(*e) && key->type == jbvBool)
+			{
+				result->type = jbvBool;
+				result->boolean = JBE_ISBOOL_TRUE(*e) != 0;
+				result->estSize = sizeof(JEntry);
+			}
+			else
+				continue;
+
+			if (compareJsonbScalarValue(key, result) == 0)
+				return result;
+		}
+	}
+	else if (flags & JB_FOBJECT & superheader)
+	{
+		/* Since this is an object, account for *Pairs* of Jentrys */
+		char	   *data = (char *) (array + (superheader & JB_CMASK) * 2);
+		uint32		stopLow = lowbound ? *lowbound : 0,
+					stopMiddle;
+
+		/* Object key past by caller must be a string */
+		Assert(key->type == jbvString);
+
+		/* Binary search on object/pair keys *only* */
+		while (stopLow < count)
+		{
+			JEntry	   *entry;
+			int			difference;
+			JsonbValue	candidate;
+
+			/*
+			 * Note how we compensate for the fact that we're iterating through
+			 * pairs (not entries) throughout.
+			 */
+			stopMiddle = stopLow + (count - stopLow) / 2;
+
+			entry = array + stopMiddle * 2;
+
+			candidate.type = jbvString;
+			candidate.string.val = data + JBE_OFF(*entry);
+			candidate.string.len = JBE_LEN(*entry);
+			candidate.estSize = sizeof(JEntry) + candidate.string.len;
+
+			difference = lengthCompareJsonbStringValue(&candidate, key, NULL);
+
+			if (difference == 0)
+			{
+				/* Found our value (from key/value pair) */
+				JEntry	   *v = entry + 1;
+
+				if (lowbound)
+					*lowbound = stopMiddle + 1;
+
+				if (JBE_ISNULL(*v))
+				{
+					result->type = jbvNull;
+					result->estSize = sizeof(JEntry);
+				}
+				else if (JBE_ISSTRING(*v))
+				{
+					result->type = jbvString;
+					result->string.val = data + JBE_OFF(*v);
+					result->string.len = JBE_LEN(*v);
+					result->estSize = sizeof(JEntry) + result->string.len;
+				}
+				else if (JBE_ISNUMERIC(*v))
+				{
+					result->type = jbvNumeric;
+					result->numeric = (Numeric) (data + INTALIGN(JBE_OFF(*v)));
+					result->estSize = 2 * sizeof(JEntry) +
+						VARSIZE_ANY(result->numeric);
+				}
+				else if (JBE_ISBOOL(*v))
+				{
+					result->type = jbvBool;
+					result->boolean = JBE_ISBOOL_TRUE(*v) != 0;
+					result->estSize = sizeof(JEntry);
+				}
+				else
+				{
+					/*
+					 * See header comments to understand why this never happens
+					 * with arrays
+					 */
+					result->type = jbvBinary;
+					result->binary.data = data + INTALIGN(JBE_OFF(*v));
+					result->binary.len = JBE_LEN(*v) -
+						(INTALIGN(JBE_OFF(*v)) - JBE_OFF(*v));
+					result->estSize = 2 * sizeof(JEntry) + result->binary.len;
+				}
+
+				return result;
+			}
+			else
+			{
+				if (difference < 0)
+					stopLow = stopMiddle + 1;
+				else
+					count = stopMiddle;
+			}
+		}
+
+		if (lowbound)
+			*lowbound = stopLow;
+	}
+
+	/* Not found */
+	pfree(result);
+	return NULL;
+}
+
+/*
+ * Get i-th value of Jsonb array from superheader.
+ *
+ * Returns palloc()'d copy of value.
+ */
+JsonbValue *
+getIthJsonbValueFromSuperHeader(JsonbSuperHeader sheader, uint32 i)
+{
+	uint32		superheader = *(uint32 *) sheader;
+	JsonbValue *result;
+	JEntry	   *array,
+			   *e;
+	char	   *data;
+
+	result = palloc(sizeof(JsonbValue));
+
+	if (i >= (superheader & JB_CMASK))
+		return NULL;
+
+	array = (JEntry *) (sheader + sizeof(uint32));
+
+	if (superheader & JB_FARRAY)
+	{
+		e = array + i;
+		data = (char *) (array + (superheader & JB_CMASK));
+	}
+	else
+	{
+		elog(ERROR, "not a jsonb array");
+	}
+
+	if (JBE_ISNULL(*e))
+	{
+		result->type = jbvNull;
+		result->estSize = sizeof(JEntry);
+	}
+	else if (JBE_ISSTRING(*e))
+	{
+		result->type = jbvString;
+		result->string.val = data + JBE_OFF(*e);
+		result->string.len = JBE_LEN(*e);
+		result->estSize = sizeof(JEntry) + result->string.len;
+	}
+	else if (JBE_ISNUMERIC(*e))
+	{
+		result->type = jbvNumeric;
+		result->numeric = (Numeric) (data + INTALIGN(JBE_OFF(*e)));
+		result->estSize = 2 * sizeof(JEntry) + VARSIZE_ANY(result->numeric);
+	}
+	else if (JBE_ISBOOL(*e))
+	{
+		result->type = jbvBool;
+		result->boolean = JBE_ISBOOL_TRUE(*e) != 0;
+		result->estSize = sizeof(JEntry);
+	}
+	else
+	{
+		result->type = jbvBinary;
+		result->binary.data = data + INTALIGN(JBE_OFF(*e));
+		result->binary.len = JBE_LEN(*e) - (INTALIGN(JBE_OFF(*e)) - JBE_OFF(*e));
+		result->estSize = result->binary.len + 2 * sizeof(JEntry);
+	}
+
+	return result;
+}
+
+/*
+ * Push JsonbValue into JsonbParseState.
+ *
+ * Used when parsing JSON tokens to form Jsonb, or when converting an in-memory
+ * JsonbValue to a Jsonb.
+ *
+ * Initial state of *JsonbParseState is NULL, since it'll be allocated here
+ * originally (caller will get JsonbParseState back by reference).
+ *
+ * Only sequential tokens pertaining to non-container types should pass a
+ * JsonbValue.  There is one exception -- WJB_BEGIN_ARRAY callers may pass a
+ * "raw scalar" pseudo array to append that.
+ */
+JsonbValue *
+pushJsonbValue(JsonbParseState ** pstate, int seq, JsonbValue * scalarVal)
+{
+	JsonbValue *result = NULL;
+
+	switch (seq)
+	{
+		case WJB_BEGIN_ARRAY:
+			Assert(!scalarVal || scalarVal->array.rawScalar);
+			*pstate = pushState(pstate);
+			result = &(*pstate)->contVal;
+			(*pstate)->contVal.type = jbvArray;
+			(*pstate)->contVal.estSize = 3 * sizeof(JEntry);
+			(*pstate)->contVal.array.nElems = 0;
+			(*pstate)->contVal.array.rawScalar = (scalarVal &&
+												  scalarVal->array.rawScalar);
+			if (scalarVal && scalarVal->array.nElems > 0)
+			{
+				/* Assume that this array is still really a scalar */
+				Assert(scalarVal->type == jbvArray);
+				(*pstate)->size = scalarVal->array.nElems;
+			}
+			else
+			{
+				(*pstate)->size = 4;
+			}
+			(*pstate)->contVal.array.elems = palloc(sizeof(JsonbValue) *
+													(*pstate)->size);
+			break;
+		case WJB_BEGIN_OBJECT:
+			Assert(!scalarVal);
+			*pstate = pushState(pstate);
+			result = &(*pstate)->contVal;
+			(*pstate)->contVal.type = jbvObject;
+			(*pstate)->contVal.estSize = 3 * sizeof(JEntry);
+			(*pstate)->contVal.object.nPairs = 0;
+			(*pstate)->size = 4;
+			(*pstate)->contVal.object.pairs = palloc(sizeof(JsonbPair) *
+													 (*pstate)->size);
+			break;
+		case WJB_KEY:
+			Assert(scalarVal->type == jbvString);
+			appendKey(*pstate, scalarVal);
+			break;
+		case WJB_VALUE:
+			Assert(IsAJsonbScalar(scalarVal) ||
+				   scalarVal->type == jbvBinary);
+			appendValue(*pstate, scalarVal);
+			break;
+		case WJB_ELEM:
+			Assert(IsAJsonbScalar(scalarVal) ||
+				   scalarVal->type == jbvBinary);
+			appendElement(*pstate, scalarVal);
+			break;
+		case WJB_END_OBJECT:
+			uniqueifyJsonbObject(&(*pstate)->contVal);
+		case WJB_END_ARRAY:
+			/* Steps here common to WJB_END_OBJECT case */
+			Assert(!scalarVal);
+			result = &(*pstate)->contVal;
+
+			/*
+			 * Pop stack and push current array/object as value in parent
+			 * array/object
+			 */
+			*pstate = (*pstate)->next;
+			if (*pstate)
+			{
+				switch ((*pstate)->contVal.type)
+				{
+					case jbvArray:
+						appendElement(*pstate, result);
+						break;
+					case jbvObject:
+						appendValue(*pstate, result);
+						break;
+					default:
+						elog(ERROR, "invalid jsonb container type");
+				}
+			}
+			break;
+		default:
+			elog(ERROR, "unrecognized jsonb sequential processing token");
+	}
+
+	return result;
+}
+
+/*
+ * Given a Jsonb superheader, expand to JsonbIterator to iterate over items
+ * fully expanded to in-memory representation for manipulation.
+ *
+ * See JsonbIteratorNext() for notes on memory management.
+ */
+JsonbIterator *
+JsonbIteratorInit(JsonbSuperHeader sheader)
+{
+	JsonbIterator *it = palloc(sizeof(JsonbIterator));
+
+	iteratorFromContainerBuf(it, sheader);
+	it->parent = NULL;
+
+	return it;
+}
+
+/*
+ * Get next JsonbValue while iterating
+ *
+ * Caller should initially pass their own, original iterator.  They may get
+ * back a child iterator palloc()'d here instead.  The function can be relied
+ * on to free those child iterators, lest the memory allocated for highly
+ * nested objects become unreasonable, but only if callers don't end iteration
+ * early (by breaking upon having found something in a search, for example).
+ *
+ * Callers in such a scenario, that are particularly sensitive to leaking
+ * memory in a long-lived context may walk the ancestral tree from the final
+ * iterator we left them with to its oldest ancestor, pfree()ing as they go.
+ * They do not have to free any other memory previously allocated for iterators
+ * but not accessible as direct ancestors of the iterator they're last passed
+ * back.
+ *
+ * Returns "Jsonb sequential processing" token value.  Iterator "state"
+ * reflects the current stage of the process in a less granular fashion, and is
+ * mostly used here to track things internally with respect to particular
+ * iterators.
+ *
+ * Clients of this function should not have to handle any jbvBinary values
+ * (since recursive calls will deal with this), provided skipNested is false.
+ * It is our job to expand the jbvBinary representation without bothering them
+ * with it.  However, clients should not take it upon themselves to touch array
+ * or Object element/pair buffers, since their element/pair pointers are
+ * garbage.
+ */
+int
+JsonbIteratorNext(JsonbIterator ** it, JsonbValue * val, bool skipNested)
+{
+	JsonbIterState	state;
+
+	/* Guard against stack overflow due to overly complex Jsonb */
+	check_stack_depth();
+
+	/* Recursive caller may have original caller's iterator */
+	if (*it == NULL)
+		return WJB_DONE;
+
+	state = (*it)->state;
+
+	if ((*it)->containerType == JB_FARRAY)
+	{
+		if (state == jbi_start)
+		{
+			/* Set v to array on first array call */
+			val->type = jbvArray;
+			val->array.nElems = (*it)->nElems;
+			/*
+			 * v->array.elems is not actually set, because we aren't doing a
+			 * full conversion
+			 */
+			val->array.rawScalar = (*it)->isScalar;
+			(*it)->i = 0;
+			/* Set state for next call */
+			(*it)->state = jbi_elem;
+			return WJB_BEGIN_ARRAY;
+		}
+		else if (state == jbi_elem)
+		{
+			if ((*it)->i >= (*it)->nElems)
+			{
+				/*
+				 * All elements within array already processed.  Report this to
+				 * caller, and give it back original parent iterator (which
+				 * independently tracks iteration progress at its level of
+				 * nesting).
+				 */
+				*it = freeAndGetParent(*it);
+				return WJB_END_ARRAY;
+			}
+			else if (formIterIsContainer(it, val, &(*it)->meta[(*it)->i++],
+										 skipNested))
+			{
+				/*
+				 * New child iterator acquired within formIterIsContainer.
+				 * Recurse into container.  Don't directly return jbvBinary
+				 * value to top-level client.
+				 */
+				return JsonbIteratorNext(it, val, skipNested);
+			}
+			else
+			{
+				/* Scalar item in array */
+				return WJB_ELEM;
+			}
+		}
+	}
+	else if ((*it)->containerType == JB_FOBJECT)
+	{
+		if (state == jbi_start)
+		{
+			/* Set v to object on first object call */
+			val->type = jbvObject;
+			val->object.nPairs = (*it)->nElems;
+			/*
+			 * v->object.pairs is not actually set, because we aren't doing a
+			 * full conversion
+			 */
+			(*it)->i = 0;
+			/* Set state for next call */
+			(*it)->state = jbi_key;
+			return WJB_BEGIN_OBJECT;
+		}
+		else if (state == jbi_key)
+		{
+			if ((*it)->i >= (*it)->nElems)
+			{
+				/*
+				 * All pairs within object already processed.  Report this to
+				 * caller, and give it back original containing iterator (which
+				 * independently tracks iteration progress at its level of
+				 * nesting).
+				 */
+				*it = freeAndGetParent(*it);
+				return WJB_END_OBJECT;
+			}
+			else
+			{
+				/*
+				 * Return binary item key (ensured by setting skipNested to
+				 * false directly).  No child iterator, no further recursion.
+				 * When control reaches here, it's probably from a recursive
+				 * call.
+				 */
+				if (formIterIsContainer(it, val, &(*it)->meta[(*it)->i * 2], false))
+					elog(ERROR, "unexpected container as object key");
+
+				Assert(val->type == jbvString);
+				/* Set state for next call */
+				(*it)->state = jbi_value;
+				return WJB_KEY;
+			}
+		}
+		else if (state == jbi_value)
+		{
+			/* Set state for next call */
+			(*it)->state = jbi_key;
+
+			/*
+			 * Value may be a container, in which case we recurse with new,
+			 * child iterator.  If it is, don't bother !skipNested callers with
+			 * dealing with the jbvBinary representation.
+			 */
+			if (formIterIsContainer(it, val, &(*it)->meta[((*it)->i++) * 2 + 1],
+									skipNested))
+				return JsonbIteratorNext(it, val, skipNested);
+			else
+				return WJB_VALUE;
+		}
+	}
+
+	elog(ERROR, "invalid iterator state");
+}
+
+/*
+ * Worker for "contains" operator's function
+ *
+ * Formally speaking, containment is top-down, unordered subtree isomorphism.
+ *
+ * Takes iterators that belong to some container type.  These iterators
+ * "belong" to those values in the sense that they've just been initialized in
+ * respect of them by the caller (perhaps in a nested fashion).
+ *
+ * "val" is lhs Jsonb, and mContained is rhs Jsonb when called from top level.
+ * We determine if mContained is contained within val.
+ */
+bool
+JsonbDeepContains(JsonbIterator ** val, JsonbIterator ** mContained)
+{
+	uint32		rval,
+				rcont;
+	JsonbValue	vval,
+				vcontained;
+	/*
+	 * Guard against stack overflow due to overly complex Jsonb.
+	 *
+	 * Functions called here independently take this precaution, but that might
+	 * not be sufficient since this is also a recursive function.
+	 */
+	check_stack_depth();
+
+	rval = JsonbIteratorNext(val, &vval, false);
+	rcont = JsonbIteratorNext(mContained, &vcontained, false);
+
+	if (rval != rcont)
+	{
+		/*
+		 * The differing return values can immediately be taken as indicating
+		 * two differing container types at this nesting level, which is
+		 * sufficient reason to give up entirely (but it should be the case
+		 * that they're both some container type).
+		 */
+		Assert(rval == WJB_BEGIN_OBJECT || rval == WJB_BEGIN_ARRAY);
+		Assert(rcont == WJB_BEGIN_OBJECT || rcont == WJB_BEGIN_ARRAY);
+		return false;
+	}
+	else if (rcont == WJB_BEGIN_OBJECT)
+	{
+		JsonbValue *lhsVal;		/* lhsVal is from pair in lhs object */
+
+		Assert(vcontained.type == jbvObject);
+
+		/* Work through rhs "is it contained within?" object */
+		for (;;)
+		{
+			rcont = JsonbIteratorNext(mContained, &vcontained, false);
+
+			/*
+			 * When we get through caller's rhs "is it contained within?"
+			 * object without failing to find one of its values, it's
+			 * contained.
+			 */
+			if (rcont == WJB_END_OBJECT)
+				return true;
+
+			Assert(rcont == WJB_KEY);
+
+			/* First, find value by key... */
+			lhsVal = findJsonbValueFromSuperHeader((*val)->buffer,
+												   JB_FOBJECT,
+												   NULL,
+												   &vcontained);
+
+			if (!lhsVal)
+				return false;
+
+			/*
+			 * ...at this stage it is apparent that there is at least a key
+			 * match for this rhs pair.
+			 */
+			rcont = JsonbIteratorNext(mContained, &vcontained, true);
+
+			Assert(rcont == WJB_VALUE);
+
+			/*
+			 * Compare rhs pair's value with lhs pair's value just found using
+			 * key
+			 */
+			if (lhsVal->type != vcontained.type)
+			{
+				return false;
+			}
+			else if (IsAJsonbScalar(lhsVal))
+			{
+				if (compareJsonbScalarValue(lhsVal, &vcontained) != 0)
+					return false;
+			}
+			else
+			{
+				/* Nested container value (object or array) */
+				JsonbIterator *nestval, *nestContained;
+
+				Assert(lhsVal->type == jbvBinary);
+				Assert(vcontained.type == jbvBinary);
+
+				nestval = JsonbIteratorInit(lhsVal->binary.data);
+				nestContained = JsonbIteratorInit(vcontained.binary.data);
+
+				/*
+				 * Match "value" side of rhs datum object's pair recursively.
+				 * It's a nested structure.
+				 *
+				 * Note that nesting still has to "match up" at the right
+				 * nesting sub-levels.  However, there need only be zero or
+				 * more matching pairs (or elements) at each nesting level
+				 * (provided the *rhs* pairs/elements *all* match on each
+				 * level), which enables searching nested structures for a
+				 * single String or other primitive type sub-datum quite
+				 * effectively (provided the user constructed the rhs nested
+				 * structure such that we "know where to look").
+				 *
+				 * In other words, the mapping of container nodes in the rhs
+				 * "vcontained" Jsonb to internal nodes on the lhs is
+				 * injective, and parent-child edges on the rhs must be mapped
+				 * to parent-child edges on the lhs to satisfy the condition of
+				 * containment (plus of course the mapped nodes must be equal).
+				 */
+				if (!JsonbDeepContains(&nestval, &nestContained))
+					return false;
+			}
+		}
+	}
+	else if (rcont == WJB_BEGIN_ARRAY)
+	{
+		JsonbValue *lhsConts = NULL;
+		uint32		nLhsElems = vval.array.nElems;
+
+		Assert(vcontained.type == jbvArray);
+
+		/*
+		 * Handle distinction between "raw scalar" pseudo arrays, and real
+		 * arrays.
+		 *
+		 * A raw scalar may contain another raw scalar, and an array may
+		 * contain a raw scalar, but a raw scalar may not contain an array.  We
+		 * don't do something like this for the object case, since objects can
+		 * only contain pairs, never raw scalars (a pair is represented by an
+		 * rhs object argument with a single contained pair).
+		 */
+		if (vval.array.rawScalar && !vcontained.array.rawScalar)
+			return false;
+
+		/* Work through rhs "is it contained within?" array */
+		for (;;)
+		{
+			rcont = JsonbIteratorNext(mContained, &vcontained, true);
+
+			/*
+			 * When we get through caller's rhs "is it contained within?" array
+			 * without failing to find one of its values, it's contained.
+			 */
+			if (rcont == WJB_END_ARRAY)
+				return true;
+
+			Assert(rcont == WJB_ELEM);
+
+			if (IsAJsonbScalar(&vcontained))
+			{
+				if (!findJsonbValueFromSuperHeader((*val)->buffer,
+												   JB_FARRAY,
+												   NULL,
+												   &vcontained))
+					return false;
+			}
+			else
+			{
+				uint32		i;
+
+				/*
+				 * If this is first container found in rhs array (at this
+				 * depth), initialize temp lhs array of containers
+				 */
+				if (lhsConts == NULL)
+				{
+					uint32		j = 0;
+
+					/* Make room for all possible values */
+					lhsConts = palloc(sizeof(JsonbValue) * nLhsElems);
+
+					for (i = 0; i < nLhsElems; i++)
+					{
+						/* Store all lhs elements in temp array*/
+						rcont = JsonbIteratorNext(val, &vval, true);
+						Assert(rcont == WJB_ELEM);
+
+						if (vval.type == jbvBinary)
+							lhsConts[j++] = vval;
+					}
+
+					/* No container elements in temp array, so give up now */
+					if (j == 0)
+						return false;
+
+					/* We may have only partially filled array */
+					nLhsElems = j;
+				}
+
+				/* XXX: Nested array containment is O(N^2) */
+				for (i = 0; i < nLhsElems; i++)
+				{
+					/* Nested container value (object or array) */
+					JsonbIterator  *nestval, *nestContained;
+					bool			contains;
+
+					nestval = JsonbIteratorInit(lhsConts[i].binary.data);
+					nestContained = JsonbIteratorInit(vcontained.binary.data);
+
+					contains = JsonbDeepContains(&nestval, &nestContained);
+
+					if (nestval)
+						pfree(nestval);
+					if (nestContained)
+						pfree(nestContained);
+					if (contains)
+						break;
+				}
+
+				/*
+				 * Report rhs container value is not contained if couldn't
+				 * match rhs container to *some* lhs cont
+				 */
+				if (i == nLhsElems)
+					return false;
+			}
+		}
+	}
+	else
+	{
+		elog(ERROR, "invalid jsonb container type");
+	}
+
+	elog(ERROR, "unexpectedly fell off end of jsonb container");
+}
+
+/*
+ * Convert a Postgres text array to a Jsonb array, sorted and with
+ * de-duplicated key elements.  This is used for searching an object for items
+ * in the array, so we enforce that the number of strings cannot exceed
+ * JSONB_MAX_PAIRS.
+ */
+JsonbValue *
+arrayToJsonbSortedArray(ArrayType *array)
+{
+	Datum	   *key_datums;
+	bool	   *key_nulls;
+	int			elem_count;
+	JsonbValue *result;
+	int			i,
+				j;
+
+	/* Extract data for sorting */
+	deconstruct_array(array, TEXTOID, -1, false, 'i', &key_datums, &key_nulls,
+					  &elem_count);
+
+	if (elem_count == 0)
+		return NULL;
+
+	/*
+	 * A text array uses at least eight bytes per element, so any overflow in
+	 * "key_count * sizeof(JsonbPair)" is small enough for palloc() to catch.
+	 * However, credible improvements to the array format could invalidate that
+	 * assumption.  Therefore, use an explicit check rather than relying on
+	 * palloc() to complain.
+	 */
+	if (elem_count > JSONB_MAX_PAIRS)
+		ereport(ERROR,
+				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
+				 errmsg("number of array elements (%d) exceeds maximum allowed Jsonb pairs (%zu)",
+						elem_count, JSONB_MAX_PAIRS)));
+
+	result = palloc(sizeof(JsonbValue));
+	result->type = jbvArray;
+	result->array.rawScalar = false;
+	result->array.elems = palloc(sizeof(JsonbPair) * elem_count);
+
+	for (i = 0, j = 0; i < elem_count; i++)
+	{
+		if (!key_nulls[i])
+		{
+			result->array.elems[j].type = jbvString;
+			result->array.elems[j].string.val = VARDATA(key_datums[i]);
+			result->array.elems[j].string.len = VARSIZE(key_datums[i]) - VARHDRSZ;
+			j++;
+		}
+	}
+	result->array.nElems = j;
+
+	uniqueifyJsonbArray(result);
+	return result;
+}
+
+/*
+ * Hash a JsonbValue scalar value, mixing in the hash value with an existing
+ * hash provided by the caller.
+ *
+ * Some callers may wish to independently XOR in JB_FOBJECT and JB_FARRAY
+ * flags.
+ */
+void
+JsonbHashScalarValue(const JsonbValue * scalarVal, uint32 * hash)
+{
+	int tmp;
+
+	/*
+	 * Combine hash values of successive keys, values and elements by rotating
+	 * the previous value left 1 bit, then XOR'ing in the new
+	 * key/value/element's hash value.
+	 */
+	*hash = (*hash << 1) | (*hash >> 31);
+	switch (scalarVal->type)
+	{
+		case jbvNull:
+			*hash ^= 0x01;
+			return;
+		case jbvString:
+			tmp = hash_any((unsigned char *) scalarVal->string.val,
+						   scalarVal->string.len);
+			*hash ^= tmp;
+			return;
+		case jbvNumeric:
+			/* Must be unaffected by trailing zeroes */
+			tmp = DatumGetInt32(DirectFunctionCall1(hash_numeric,
+													NumericGetDatum(scalarVal->numeric)));
+			*hash ^= tmp;
+			return;
+		case jbvBool:
+			*hash ^= scalarVal->boolean? 0x02:0x04;
+			return;
+		default:
+			elog(ERROR, "invalid jsonb scalar type");
+	}
+}
+
+/*
+ * Are two scalar JsonbValues of the same type a and b equal?
+ *
+ * Does not use lexical comparisons.  Therefore, it is essentially that this
+ * never be used against Strings for anything other than searching for values
+ * within a single jsonb.
+ */
+static int
+compareJsonbScalarValue(JsonbValue * aScalar, JsonbValue * bScalar)
+{
+	if (aScalar->type == bScalar->type)
+	{
+		switch (aScalar->type)
+		{
+			case jbvNull:
+				return 0;
+			case jbvString:
+				return lengthCompareJsonbStringValue(aScalar, bScalar, NULL);
+			case jbvNumeric:
+				return DatumGetInt32(DirectFunctionCall2(numeric_cmp,
+														 PointerGetDatum(aScalar->numeric),
+														 PointerGetDatum(bScalar->numeric)));
+			case jbvBool:
+				if (aScalar->boolean != bScalar->boolean)
+					return (aScalar->boolean > bScalar->boolean) ? 1 : -1;
+				else
+					return 0;
+			default:
+				elog(ERROR, "invalid jsonb scalar type");
+		}
+	}
+	elog(ERROR, "jsonb scalar type mismatch");
+}
+
+/*
+ * Standard lexical qsort() comparator of jsonb strings.
+ *
+ * Sorts strings lexically, using the default database collation.  Used by
+ * B-Tree operators, where a lexical sort order is generally expected.
+ */
+static int
+lexicalCompareJsonbStringValue(const void *a, const void *b)
+{
+	const JsonbValue *va = (const JsonbValue *) a;
+	const JsonbValue *vb = (const JsonbValue *) b;
+
+	Assert(va->type == jbvString);
+	Assert(vb->type == jbvString);
+
+	return varstr_cmp(va->string.val, va->string.len, vb->string.val,
+					  vb->string.len, DEFAULT_COLLATION_OID);
+}
+
+/*
+ * Given a JsonbValue, convert to Jsonb and store in preallocated Jsonb buffer
+ * sufficiently large to fit the value
+ */
+static Size
+convertJsonb(JsonbValue * val, Jsonb *buffer)
+{
+	convertState	state;
+	Size			len;
+
+	/* Should not already have binary representation */
+	Assert(val->type != jbvBinary);
+
+	state.buffer = buffer;
+	/* Start from superheader */
+	state.ptr = VARDATA(state.buffer);
+	state.levelSz = 8;
+	state.allState = palloc(sizeof(convertLevel) * state.levelSz);
+
+	walkJsonbValueConversion(val, &state, 0);
+
+	len = state.ptr - VARDATA(state.buffer);
+
+	Assert(len <= val->estSize);
+	return len;
+}
+
+/*
+ * Walk the tree representation of Jsonb, as part of the process of converting
+ * a JsonbValue to a Jsonb.
+ *
+ * This high-level function takes care of recursion into sub-containers, but at
+ * the top level calls putJsonbValueConversion once per sequential processing
+ * token (in a manner similar to generic iteration).
+ */
+static void
+walkJsonbValueConversion(JsonbValue * val, convertState * cstate,
+						 uint32 nestlevel)
+{
+	int			i;
+
+	check_stack_depth();
+
+	if (!val)
+		return;
+
+	switch (val->type)
+	{
+		case jbvArray:
+
+			putJsonbValueConversion(cstate, val, WJB_BEGIN_ARRAY, nestlevel);
+			for (i = 0; i < val->array.nElems; i++)
+			{
+				if (IsAJsonbScalar(&val->array.elems[i]) ||
+					val->array.elems[i].type == jbvBinary)
+					putJsonbValueConversion(cstate, val->array.elems + i,
+											WJB_ELEM, nestlevel);
+				else
+					walkJsonbValueConversion(val->array.elems + i, cstate,
+											 nestlevel + 1);
+			}
+			putJsonbValueConversion(cstate, val, WJB_END_ARRAY, nestlevel);
+
+			break;
+		case jbvObject:
+
+			putJsonbValueConversion(cstate, val, WJB_BEGIN_OBJECT, nestlevel);
+			for (i = 0; i < val->object.nPairs; i++)
+			{
+				putJsonbValueConversion(cstate, &val->object.pairs[i].key,
+										WJB_KEY, nestlevel);
+
+				if (IsAJsonbScalar(&val->object.pairs[i].value) ||
+					val->object.pairs[i].value.type == jbvBinary)
+					putJsonbValueConversion(cstate,
+											&val->object.pairs[i].value,
+											WJB_VALUE, nestlevel);
+				else
+					walkJsonbValueConversion(&val->object.pairs[i].value,
+											 cstate, nestlevel + 1);
+			}
+			putJsonbValueConversion(cstate, val, WJB_END_OBJECT, nestlevel);
+
+			break;
+		default:
+			elog(ERROR, "unknown type of jsonb container");
+	}
+}
+
+/*
+ * walkJsonbValueConversion() worker.  Add padding sufficient to int-align our
+ * access to conversion buffer.
+ */
+static inline
+short addPaddingInt(convertState * cstate)
+{
+	short		padlen, p;
+
+	padlen = INTALIGN(cstate->ptr - VARDATA(cstate->buffer)) -
+		(cstate->ptr - VARDATA(cstate->buffer));
+
+	for (p = padlen; p > 0; p--)
+	{
+		*cstate->ptr = '\0';
+		cstate->ptr++;
+	}
+
+	return padlen;
+}
+
+/*
+ * walkJsonbValueConversion() worker.
+ *
+ * As part of the process of converting an arbitrary JsonbValue to a Jsonb,
+ * copy over an arbitrary individual JsonbValue.  This function may copy any
+ * type of value, even containers (Objects/arrays).  However, it is not
+ * responsible for recursive aspects of walking the tree (so only top-level
+ * Object/array details are handled).
+ *
+ * No details about their keys/values/elements are handled recursively -
+ * rather, the function is called as required for the start of an Object/Array,
+ * and the end (i.e.  there is one call per sequential processing WJB_* token).
+ */
+static void
+putJsonbValueConversion(convertState * cstate, JsonbValue * val, uint32 flags,
+						uint32 level)
+{
+	if (level == cstate->levelSz)
+	{
+		cstate->levelSz *= 2;
+		cstate->allState = repalloc(cstate->allState,
+									 sizeof(convertLevel) * cstate->levelSz);
+	}
+
+	cstate->contPtr = cstate->allState + level;
+
+	if (flags & (WJB_BEGIN_ARRAY | WJB_BEGIN_OBJECT))
+	{
+		Assert(((flags & WJB_BEGIN_ARRAY) && val->type == jbvArray) ||
+			   ((flags & WJB_BEGIN_OBJECT) && val->type == jbvObject));
+
+		/* Initialize pointer into conversion buffer at this level */
+		cstate->contPtr->begin = cstate->ptr;
+
+		addPaddingInt(cstate);
+
+		/* Initialize everything else at this level */
+		cstate->contPtr->header = (uint32 *) cstate->ptr;
+		/* Advance past header */
+		cstate->ptr += sizeof(uint32);
+		cstate->contPtr->meta = (JEntry *) cstate->ptr;
+		cstate->contPtr->i = 0;
+
+		if (val->type == jbvArray)
+		{
+			*cstate->contPtr->header = val->array.nElems | JB_FARRAY;
+			cstate->ptr += sizeof(JEntry) * val->array.nElems;
+
+			if (val->array.rawScalar)
+			{
+				Assert(val->array.nElems == 1);
+				Assert(level == 0);
+				*cstate->contPtr->header |= JB_FSCALAR;
+			}
+		}
+		else
+		{
+			*cstate->contPtr->header = val->object.nPairs | JB_FOBJECT;
+			cstate->ptr += sizeof(JEntry) * val->object.nPairs * 2;
+		}
+	}
+	else if (flags & WJB_ELEM)
+	{
+		putScalarConversion(cstate, val, level, cstate->contPtr->i);
+		cstate->contPtr->i++;
+	}
+	else if (flags & WJB_KEY)
+	{
+		Assert(val->type == jbvString);
+
+		putScalarConversion(cstate, val, level, cstate->contPtr->i * 2);
+	}
+	else if (flags & WJB_VALUE)
+	{
+		putScalarConversion(cstate, val, level, cstate->contPtr->i * 2 + 1);
+		cstate->contPtr->i++;
+	}
+	else if (flags & (WJB_END_ARRAY | WJB_END_OBJECT))
+	{
+		convertLevel   *prevPtr;	/* Prev container pointer */
+		uint32			len,
+						i;
+
+		Assert(((flags & WJB_END_ARRAY) && val->type == jbvArray) ||
+			   ((flags & WJB_END_OBJECT) && val->type == jbvObject));
+
+		if (level == 0)
+			return;
+
+		len = cstate->ptr - (char *) cstate->contPtr->begin;
+
+		prevPtr = cstate->contPtr - 1;
+
+		if (*prevPtr->header & JB_FARRAY)
+		{
+			i = prevPtr->i;
+
+			prevPtr->meta[i].header = JENTRY_ISNEST;
+
+			if (i == 0)
+				prevPtr->meta[0].header |= JENTRY_ISFIRST | len;
+			else
+				prevPtr->meta[i].header |=
+					(prevPtr->meta[i - 1].header & JENTRY_POSMASK) + len;
+		}
+		else if (*prevPtr->header & JB_FOBJECT)
+		{
+			i = 2 * prevPtr->i + 1;		/* Value, not key */
+
+			prevPtr->meta[i].header = JENTRY_ISNEST;
+
+			prevPtr->meta[i].header |=
+				(prevPtr->meta[i - 1].header & JENTRY_POSMASK) + len;
+		}
+		else
+		{
+			elog(ERROR, "invalid jsonb container type");
+		}
+
+		Assert(cstate->ptr - cstate->contPtr->begin <= val->estSize);
+		prevPtr->i++;
+	}
+	else
+	{
+		elog(ERROR, "unknown flag encountered during jsonb tree walk");
+	}
+}
+
+/*
+ * As part of the process of converting an arbitrary JsonbValue to a Jsonb,
+ * serialize and copy a scalar value into buffer.
+ *
+ * This is a worker function for putJsonbValueConversion() (itself a worker for
+ * walkJsonbValueConversion()).  It handles the details with regard to Jentry
+ * metadata peculiar to each scalar type.
+ */
+static void
+putScalarConversion(convertState * cstate, JsonbValue * scalarVal, uint32 level,
+					uint32 i)
+{
+	int 		numlen;
+	short		padlen;
+
+	cstate->contPtr = cstate->allState + level;
+
+	if (i == 0)
+		cstate->contPtr->meta[0].header = JENTRY_ISFIRST;
+	else
+		cstate->contPtr->meta[i].header = 0;
+
+	switch (scalarVal->type)
+	{
+		case jbvNull:
+			cstate->contPtr->meta[i].header |= JENTRY_ISNULL;
+
+			if (i > 0)
+				cstate->contPtr->meta[i].header |=
+					cstate->contPtr->meta[i - 1].header & JENTRY_POSMASK;
+			break;
+		case jbvString:
+			memcpy(cstate->ptr, scalarVal->string.val, scalarVal->string.len);
+			cstate->ptr += scalarVal->string.len;
+
+			if (i == 0)
+				cstate->contPtr->meta[0].header |= scalarVal->string.len;
+			else
+				cstate->contPtr->meta[i].header |=
+					(cstate->contPtr->meta[i - 1].header & JENTRY_POSMASK) +
+					scalarVal->string.len;
+			break;
+		case jbvNumeric:
+			numlen = VARSIZE_ANY(scalarVal->numeric);
+			padlen = addPaddingInt(cstate);
+
+			memcpy(cstate->ptr, scalarVal->numeric, numlen);
+			cstate->ptr += numlen;
+
+			cstate->contPtr->meta[i].header |= JENTRY_ISNUMERIC;
+			if (i == 0)
+				cstate->contPtr->meta[0].header |= padlen + numlen;
+			else
+				cstate->contPtr->meta[i].header |=
+					(cstate->contPtr->meta[i - 1].header & JENTRY_POSMASK)
+					+ padlen + numlen;
+			break;
+		case jbvBool:
+			cstate->contPtr->meta[i].header |= (scalarVal->boolean) ?
+				JENTRY_ISTRUE : JENTRY_ISFALSE;
+
+			if (i > 0)
+				cstate->contPtr->meta[i].header |=
+					cstate->contPtr->meta[i - 1].header & JENTRY_POSMASK;
+			break;
+		default:
+			elog(ERROR, "invalid jsonb scalar type");
+	}
+}
+
+/*
+ * Given superheader pointer into buffer, initialize iterator.  Must be a
+ * container type.
+ */
+static void
+iteratorFromContainerBuf(JsonbIterator * it, JsonbSuperHeader sheader)
+{
+	uint32		superheader = *(uint32 *) sheader;
+
+	it->containerType = superheader & (JB_FARRAY | JB_FOBJECT);
+	it->nElems = superheader & JB_CMASK;
+	it->buffer = sheader;
+
+	/* Array starts just after header */
+	it->meta = (JEntry *) (sheader + sizeof(uint32));
+	it->state = jbi_start;
+
+	switch (it->containerType)
+	{
+		case JB_FARRAY:
+			it->dataProper =
+				(char *) it->meta + it->nElems * sizeof(JEntry);
+			it->isScalar = (superheader & JB_FSCALAR) != 0;
+			/* This is either a "raw scalar", or an array */
+			Assert(!it->isScalar || it->nElems == 1);
+			break;
+		case JB_FOBJECT:
+			/*
+			 * Offset reflects that nElems indicates JsonbPairs in an object.
+			 * Each key and each value contain Jentry metadata just the same.
+			 */
+			it->dataProper =
+				(char *) it->meta + it->nElems * sizeof(JEntry) * 2;
+			break;
+		default:
+			elog(ERROR, "unknown type of jsonb container");
+	}
+}
+
+/*
+ * JsonbIteratorNext() worker
+ *
+ * Returns bool indicating if v was a non-jbvBinary container, and thus if
+ * further recursion is required by caller (according to its skipNested
+ * preference).  If it is required, we set the caller's iterator for further
+ * recursion into the nested value.  If we're going to skip nested items, just
+ * set v to a jbvBinary value, but don't set caller's iterator.
+ *
+ * Unlike with containers (either in this function or in any
+ * JsonbIteratorNext() infrastructure), we fully convert from what is
+ * ultimately a Jsonb on-disk representation, to a JsonbValue in-memory
+ * representation (for scalar values only).  JsonbIteratorNext() initializes
+ * container Jsonbvalues, but without a sane private buffer.  For scalar values
+ * it has to be done for real (even if we don't actually allocate more memory
+ * to do this.  The point is that our JsonbValues scalars can be passed around
+ * anywhere).
+ */
+static bool
+formIterIsContainer(JsonbIterator ** it, JsonbValue * val, JEntry * ent,
+					bool skipNested)
+{
+	if (JBE_ISNULL(*ent))
+	{
+		val->type = jbvNull;
+		val->estSize = sizeof(JEntry);
+
+		return false;
+	}
+	else if (JBE_ISSTRING(*ent))
+	{
+		val->type = jbvString;
+		val->string.val = (*it)->dataProper + JBE_OFF(*ent);
+		val->string.len = JBE_LEN(*ent);
+		val->estSize = sizeof(JEntry) + val->string.len;
+
+		return false;
+	}
+	else if (JBE_ISNUMERIC(*ent))
+	{
+		val->type = jbvNumeric;
+		val->numeric = (Numeric) ((*it)->dataProper + INTALIGN(JBE_OFF(*ent)));
+		val->estSize = 2 * sizeof(JEntry) + VARSIZE_ANY(val->numeric);
+
+		return false;
+	}
+	else if (JBE_ISBOOL(*ent))
+	{
+		val->type = jbvBool;
+		val->boolean = JBE_ISBOOL_TRUE(*ent) != 0;
+		val->estSize = sizeof(JEntry);
+
+		return false;
+	}
+	else if (skipNested)
+	{
+		val->type = jbvBinary;
+		val->binary.data = (*it)->dataProper + INTALIGN(JBE_OFF(*ent));
+		val->binary.len = JBE_LEN(*ent) - (INTALIGN(JBE_OFF(*ent)) - JBE_OFF(*ent));
+		val->estSize = val->binary.len + 2 * sizeof(JEntry);
+
+		return false;
+	}
+	else
+	{
+		/*
+		 * Must be container type, so setup caller's iterator to point to that,
+		 * and return indication of that.
+		 *
+		 * Get child iterator.
+		 */
+		JsonbIterator *child = palloc(sizeof(JsonbIterator));
+
+		iteratorFromContainerBuf(child,
+								 (*it)->dataProper + INTALIGN(JBE_OFF(*ent)));
+
+		child->parent = *it;
+		*it = child;
+
+		return true;
+	}
+}
+
+/*
+ * JsonbIteratorNext() worker:  Return parent, while freeing memory for current
+ * iterator
+ */
+static JsonbIterator *
+freeAndGetParent(JsonbIterator * it)
+{
+	JsonbIterator *v = it->parent;
+
+	pfree(it);
+	return v;
+}
+
+/*
+ * pushJsonbValue() worker:  Iteration-like forming of Jsonb
+ */
+static JsonbParseState *
+pushState(JsonbParseState ** pstate)
+{
+	JsonbParseState *ns = palloc(sizeof(JsonbParseState));
+
+	ns->next = *pstate;
+	return ns;
+}
+
+/*
+ * pushJsonbValue() worker:  Append a pair key to state when generating a Jsonb
+ */
+static void
+appendKey(JsonbParseState * pstate, JsonbValue * string)
+{
+	JsonbValue *object = &pstate->contVal;
+
+	Assert(object->type == jbvObject);
+	Assert(string->type == jbvString);
+
+	if (object->object.nPairs >= JSONB_MAX_PAIRS)
+		ereport(ERROR,
+				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
+				 errmsg("number of jsonb object pairs exceeds the maximum allowed (%zu)",
+						JSONB_MAX_PAIRS)));
+
+	if (object->object.nPairs >= pstate->size)
+	{
+		pstate->size *= 2;
+		object->object.pairs = repalloc(object->object.pairs,
+										sizeof(JsonbPair) * pstate->size);
+	}
+
+	object->object.pairs[object->object.nPairs].key = *string;
+	object->object.pairs[object->object.nPairs].order = object->object.nPairs;
+
+	object->estSize += string->estSize;
+}
+
+/*
+ * pushJsonbValue() worker:  Append a pair value to state when generating a
+ * Jsonb
+ */
+static void
+appendValue(JsonbParseState * pstate, JsonbValue * scalarVal)
+{
+	JsonbValue *object = &pstate->contVal;
+
+	Assert(object->type == jbvObject);
+
+	object->object.pairs[object->object.nPairs++].value = *scalarVal;
+	object->estSize += scalarVal->estSize;
+}
+
+/*
+ * pushJsonbValue() worker:  Append an element to state when generating a Jsonb
+ */
+static void
+appendElement(JsonbParseState * pstate, JsonbValue * scalarVal)
+{
+	JsonbValue *array = &pstate->contVal;
+
+	Assert(array->type == jbvArray);
+
+	if (array->array.nElems >= JSONB_MAX_ELEMS)
+		ereport(ERROR,
+				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
+				 errmsg("number of jsonb array elements exceeds the maximum allowed (%zu)",
+						JSONB_MAX_ELEMS)));
+
+	if (array->array.nElems >= pstate->size)
+	{
+		pstate->size *= 2;
+		array->array.elems = repalloc(array->array.elems,
+									  sizeof(JsonbValue) * pstate->size);
+	}
+
+	array->array.elems[array->array.nElems++] = *scalarVal;
+	array->estSize += scalarVal->estSize;
+}
+
+/*
+ * Compare two jbvString JsonbValue values, a and b.
+ *
+ * This is a special qsort_arg() comparator used to sort strings in certain
+ * internal contexts where it is sufficient to have a well-defined sort order.
+ * In particular, object pair keys are sorted according to this criteria to
+ * facilitate cheap binary searches where we don't care about lexical sort
+ * order.
+ *
+ * a and b are first sorted based on their length.  If a tie-breaker is
+ * required, only then do we consider string binary equality.
+ *
+ * Third argument 'binequal' may point to a bool. If it's set, *binequal is set
+ * to true iff a and b have full binary equality, since some callers have an
+ * interest in whether the two values are equal or merely equivalent.
+ */
+static int
+lengthCompareJsonbStringValue(const void *a, const void *b, void *binequal)
+{
+	const JsonbValue *va = (const JsonbValue *) a;
+	const JsonbValue *vb = (const JsonbValue *) b;
+	int			res;
+
+	Assert(va->type == jbvString);
+	Assert(vb->type == jbvString);
+
+	if (va->string.len == vb->string.len)
+	{
+		res = memcmp(va->string.val, vb->string.val, va->string.len);
+		if (res == 0 && binequal)
+			*((bool *) binequal) = true;
+	}
+	else
+	{
+		res = (va->string.len > vb->string.len) ? 1 : -1;
+	}
+
+	return res;
+}
+
+/*
+ * qsort_arg() comparator to compare JsonbPair values.
+ *
+ * Function implemented in terms of lengthCompareJsonbStringValue(), and thus the
+ * same "arg setting" hack will be applied here in respect of the pair's key
+ * values.
+ *
+ * N.B: String comparisons here are "length-wise"
+ *
+ * Pairs with equals keys are ordered such that the order field is respected.
+ */
+static int
+lengthCompareJsonbPair(const void *a, const void *b, void *binequal)
+{
+	const JsonbPair *pa = (const JsonbPair *) a;
+	const JsonbPair *pb = (const JsonbPair *) b;
+	int			res;
+
+	res = lengthCompareJsonbStringValue(&pa->key, &pb->key, binequal);
+
+	/*
+	 * Guarantee keeping order of equal pair.  Unique algorithm will prefer
+	 * first element as value.
+	 */
+	if (res == 0)
+		res = (pa->order > pb->order) ? -1 : 1;
+
+	return res;
+}
+
+/*
+ * Sort and unique-ify pairs in JsonbValue object
+ */
+static void
+uniqueifyJsonbObject(JsonbValue * object)
+{
+	bool		hasNonUniq = false;
+
+	Assert(object->type == jbvObject);
+
+	if (object->object.nPairs > 1)
+		qsort_arg(object->object.pairs, object->object.nPairs, sizeof(JsonbPair),
+				  lengthCompareJsonbPair, &hasNonUniq);
+
+	if (hasNonUniq)
+	{
+		JsonbPair  *ptr = object->object.pairs + 1,
+				   *res = object->object.pairs;
+
+		while (ptr - object->object.pairs < object->object.nPairs)
+		{
+			/* Avoid copying over duplicate */
+			if (lengthCompareJsonbStringValue(ptr, res, NULL) == 0)
+			{
+				object->estSize -= ptr->key.estSize + ptr->value.estSize;
+			}
+			else
+			{
+				res++;
+				if (ptr != res)
+					memcpy(res, ptr, sizeof(JsonbPair));
+			}
+			ptr++;
+		}
+
+		object->object.nPairs = res + 1 - object->object.pairs;
+	}
+}
+
+/*
+ * Sort and unique-ify JsonbArray.
+ *
+ * Sorting uses internal ordering.
+ */
+static void
+uniqueifyJsonbArray(JsonbValue * array)
+{
+	bool hasNonUniq = false;
+
+	Assert(array->type == jbvArray);
+
+	/*
+	 * Actually sort values, determining if any were equal on the basis of full
+	 * binary equality (rather than just having the same string length).
+	 */
+	if (array->array.nElems > 1)
+		qsort_arg(array->array.elems, array->array.nElems,
+				  sizeof(JsonbValue), lengthCompareJsonbStringValue,
+				  &hasNonUniq);
+
+	if (hasNonUniq)
+	{
+		JsonbValue *ptr = array->array.elems + 1,
+				   *res = array->array.elems;
+
+		while (ptr - array->array.elems < array->array.nElems)
+		{
+			/* Avoid copying over duplicate */
+			if (lengthCompareJsonbStringValue(ptr, res, NULL) != 0)
+			{
+				res++;
+				*res = *ptr;
+			}
+
+			ptr++;
+		}
+
+		array->array.nElems = res + 1 - array->array.elems;
+	}
+}