/*-------------------------------------------------------------------------
 *
 * array_userfuncs.c
 *	  Misc user-visible array support functions
 *
 * Copyright (c) 2003-2025, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *	  src/backend/utils/adt/array_userfuncs.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "catalog/pg_operator_d.h"
#include "catalog/pg_type.h"
#include "common/int.h"
#include "common/pg_prng.h"
#include "libpq/pqformat.h"
#include "miscadmin.h"
#include "nodes/supportnodes.h"
#include "port/pg_bitutils.h"
#include "utils/array.h"
#include "utils/builtins.h"
#include "utils/datum.h"
#include "utils/lsyscache.h"
#include "utils/tuplesort.h"
#include "utils/typcache.h"

/*
 * SerialIOData
 *		Used for caching element-type data in array_agg_serialize
 */
typedef struct SerialIOData
{
	FmgrInfo	typsend;
} SerialIOData;

/*
 * DeserialIOData
 *		Used for caching element-type data in array_agg_deserialize
 */
typedef struct DeserialIOData
{
	FmgrInfo	typreceive;
	Oid			typioparam;
} DeserialIOData;

/*
 * ArraySortCachedInfo
 *		Used for caching catalog data in array_sort
 */
typedef struct ArraySortCachedInfo
{
	ArrayMetaState array_meta;	/* metadata for array_create_iterator */
	Oid			elem_lt_opr;	/* "<" operator for element type */
	Oid			elem_gt_opr;	/* ">" operator for element type */
	Oid			array_type;		/* pg_type OID of array type */
} ArraySortCachedInfo;

static Datum array_position_common(FunctionCallInfo fcinfo);


/*
 * fetch_array_arg_replace_nulls
 *
 * Fetch an array-valued argument in expanded form; if it's null, construct an
 * empty array value of the proper data type.  Also cache basic element type
 * information in fn_extra.
 *
 * Caution: if the input is a read/write pointer, this returns the input
 * argument; so callers must be sure that their changes are "safe", that is
 * they cannot leave the array in a corrupt state.
 *
 * If we're being called as an aggregate function, make sure any newly-made
 * expanded array is allocated in the aggregate state context, so as to save
 * copying operations.
 */
static ExpandedArrayHeader *
fetch_array_arg_replace_nulls(FunctionCallInfo fcinfo, int argno)
{
	ExpandedArrayHeader *eah;
	Oid			element_type;
	ArrayMetaState *my_extra;
	MemoryContext resultcxt;

	/* If first time through, create datatype cache struct */
	my_extra = (ArrayMetaState *) fcinfo->flinfo->fn_extra;
	if (my_extra == NULL)
	{
		my_extra = (ArrayMetaState *)
			MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
							   sizeof(ArrayMetaState));
		my_extra->element_type = InvalidOid;
		fcinfo->flinfo->fn_extra = my_extra;
	}

	/* Figure out which context we want the result in */
	if (!AggCheckCallContext(fcinfo, &resultcxt))
		resultcxt = CurrentMemoryContext;

	/* Now collect the array value */
	if (!PG_ARGISNULL(argno))
	{
		MemoryContext oldcxt = MemoryContextSwitchTo(resultcxt);

		eah = PG_GETARG_EXPANDED_ARRAYX(argno, my_extra);
		MemoryContextSwitchTo(oldcxt);
	}
	else
	{
		/* We have to look up the array type and element type */
		Oid			arr_typeid = get_fn_expr_argtype(fcinfo->flinfo, argno);

		if (!OidIsValid(arr_typeid))
			ereport(ERROR,
					(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
					 errmsg("could not determine input data type")));
		element_type = get_element_type(arr_typeid);
		if (!OidIsValid(element_type))
			ereport(ERROR,
					(errcode(ERRCODE_DATATYPE_MISMATCH),
					 errmsg("input data type is not an array")));

		eah = construct_empty_expanded_array(element_type,
											 resultcxt,
											 my_extra);
	}

	return eah;
}

/*-----------------------------------------------------------------------------
 * array_append :
 *		push an element onto the end of a one-dimensional array
 *----------------------------------------------------------------------------
 */
Datum
array_append(PG_FUNCTION_ARGS)
{
	ExpandedArrayHeader *eah;
	Datum		newelem;
	bool		isNull;
	Datum		result;
	int		   *dimv,
			   *lb;
	int			indx;
	ArrayMetaState *my_extra;

	eah = fetch_array_arg_replace_nulls(fcinfo, 0);
	isNull = PG_ARGISNULL(1);
	if (isNull)
		newelem = (Datum) 0;
	else
		newelem = PG_GETARG_DATUM(1);

	if (eah->ndims == 1)
	{
		/* append newelem */
		lb = eah->lbound;
		dimv = eah->dims;

		/* index of added elem is at lb[0] + (dimv[0] - 1) + 1 */
		if (pg_add_s32_overflow(lb[0], dimv[0], &indx))
			ereport(ERROR,
					(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
					 errmsg("integer out of range")));
	}
	else if (eah->ndims == 0)
		indx = 1;
	else
		ereport(ERROR,
				(errcode(ERRCODE_DATA_EXCEPTION),
				 errmsg("argument must be empty or one-dimensional array")));

	/* Perform element insertion */
	my_extra = (ArrayMetaState *) fcinfo->flinfo->fn_extra;

	result = array_set_element(EOHPGetRWDatum(&eah->hdr),
							   1, &indx, newelem, isNull,
							   -1, my_extra->typlen, my_extra->typbyval, my_extra->typalign);

	PG_RETURN_DATUM(result);
}

/*
 * array_append_support()
 *
 * Planner support function for array_append()
 */
Datum
array_append_support(PG_FUNCTION_ARGS)
{
	Node	   *rawreq = (Node *) PG_GETARG_POINTER(0);
	Node	   *ret = NULL;

	if (IsA(rawreq, SupportRequestModifyInPlace))
	{
		/*
		 * We can optimize in-place appends if the function's array argument
		 * is the array being assigned to.  We don't need to worry about array
		 * references within the other argument.
		 */
		SupportRequestModifyInPlace *req = (SupportRequestModifyInPlace *) rawreq;
		Param	   *arg = (Param *) linitial(req->args);

		if (arg && IsA(arg, Param) &&
			arg->paramkind == PARAM_EXTERN &&
			arg->paramid == req->paramid)
			ret = (Node *) arg;
	}

	PG_RETURN_POINTER(ret);
}

/*-----------------------------------------------------------------------------
 * array_prepend :
 *		push an element onto the front of a one-dimensional array
 *----------------------------------------------------------------------------
 */
Datum
array_prepend(PG_FUNCTION_ARGS)
{
	ExpandedArrayHeader *eah;
	Datum		newelem;
	bool		isNull;
	Datum		result;
	int		   *lb;
	int			indx;
	int			lb0;
	ArrayMetaState *my_extra;

	isNull = PG_ARGISNULL(0);
	if (isNull)
		newelem = (Datum) 0;
	else
		newelem = PG_GETARG_DATUM(0);
	eah = fetch_array_arg_replace_nulls(fcinfo, 1);

	if (eah->ndims == 1)
	{
		/* prepend newelem */
		lb = eah->lbound;
		lb0 = lb[0];

		if (pg_sub_s32_overflow(lb0, 1, &indx))
			ereport(ERROR,
					(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
					 errmsg("integer out of range")));
	}
	else if (eah->ndims == 0)
	{
		indx = 1;
		lb0 = 1;
	}
	else
		ereport(ERROR,
				(errcode(ERRCODE_DATA_EXCEPTION),
				 errmsg("argument must be empty or one-dimensional array")));

	/* Perform element insertion */
	my_extra = (ArrayMetaState *) fcinfo->flinfo->fn_extra;

	result = array_set_element(EOHPGetRWDatum(&eah->hdr),
							   1, &indx, newelem, isNull,
							   -1, my_extra->typlen, my_extra->typbyval, my_extra->typalign);

	/* Readjust result's LB to match the input's, as expected for prepend */
	Assert(result == EOHPGetRWDatum(&eah->hdr));
	if (eah->ndims == 1)
	{
		/* This is ok whether we've deconstructed or not */
		eah->lbound[0] = lb0;
	}

	PG_RETURN_DATUM(result);
}

/*
 * array_prepend_support()
 *
 * Planner support function for array_prepend()
 */
Datum
array_prepend_support(PG_FUNCTION_ARGS)
{
	Node	   *rawreq = (Node *) PG_GETARG_POINTER(0);
	Node	   *ret = NULL;

	if (IsA(rawreq, SupportRequestModifyInPlace))
	{
		/*
		 * We can optimize in-place prepends if the function's array argument
		 * is the array being assigned to.  We don't need to worry about array
		 * references within the other argument.
		 */
		SupportRequestModifyInPlace *req = (SupportRequestModifyInPlace *) rawreq;
		Param	   *arg = (Param *) lsecond(req->args);

		if (arg && IsA(arg, Param) &&
			arg->paramkind == PARAM_EXTERN &&
			arg->paramid == req->paramid)
			ret = (Node *) arg;
	}

	PG_RETURN_POINTER(ret);
}

/*-----------------------------------------------------------------------------
 * array_cat :
 *		concatenate two nD arrays to form an nD array, or
 *		push an (n-1)D array onto the end of an nD array
 *----------------------------------------------------------------------------
 */
Datum
array_cat(PG_FUNCTION_ARGS)
{
	ArrayType  *v1,
			   *v2;
	ArrayType  *result;
	int		   *dims,
			   *lbs,
				ndims,
				nitems,
				ndatabytes,
				nbytes;
	int		   *dims1,
			   *lbs1,
				ndims1,
				nitems1,
				ndatabytes1;
	int		   *dims2,
			   *lbs2,
				ndims2,
				nitems2,
				ndatabytes2;
	int			i;
	char	   *dat1,
			   *dat2;
	bits8	   *bitmap1,
			   *bitmap2;
	Oid			element_type;
	Oid			element_type1;
	Oid			element_type2;
	int32		dataoffset;

	/* Concatenating a null array is a no-op, just return the other input */
	if (PG_ARGISNULL(0))
	{
		if (PG_ARGISNULL(1))
			PG_RETURN_NULL();
		result = PG_GETARG_ARRAYTYPE_P(1);
		PG_RETURN_ARRAYTYPE_P(result);
	}
	if (PG_ARGISNULL(1))
	{
		result = PG_GETARG_ARRAYTYPE_P(0);
		PG_RETURN_ARRAYTYPE_P(result);
	}

	v1 = PG_GETARG_ARRAYTYPE_P(0);
	v2 = PG_GETARG_ARRAYTYPE_P(1);

	element_type1 = ARR_ELEMTYPE(v1);
	element_type2 = ARR_ELEMTYPE(v2);

	/* Check we have matching element types */
	if (element_type1 != element_type2)
		ereport(ERROR,
				(errcode(ERRCODE_DATATYPE_MISMATCH),
				 errmsg("cannot concatenate incompatible arrays"),
				 errdetail("Arrays with element types %s and %s are not "
						   "compatible for concatenation.",
						   format_type_be(element_type1),
						   format_type_be(element_type2))));

	/* OK, use it */
	element_type = element_type1;

	/*----------
	 * We must have one of the following combinations of inputs:
	 * 1) one empty array, and one non-empty array
	 * 2) both arrays empty
	 * 3) two arrays with ndims1 == ndims2
	 * 4) ndims1 == ndims2 - 1
	 * 5) ndims1 == ndims2 + 1
	 *----------
	 */
	ndims1 = ARR_NDIM(v1);
	ndims2 = ARR_NDIM(v2);

	/*
	 * short circuit - if one input array is empty, and the other is not, we
	 * return the non-empty one as the result
	 *
	 * if both are empty, return the first one
	 */
	if (ndims1 == 0 && ndims2 > 0)
		PG_RETURN_ARRAYTYPE_P(v2);

	if (ndims2 == 0)
		PG_RETURN_ARRAYTYPE_P(v1);

	/* the rest fall under rule 3, 4, or 5 */
	if (ndims1 != ndims2 &&
		ndims1 != ndims2 - 1 &&
		ndims1 != ndims2 + 1)
		ereport(ERROR,
				(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
				 errmsg("cannot concatenate incompatible arrays"),
				 errdetail("Arrays of %d and %d dimensions are not "
						   "compatible for concatenation.",
						   ndims1, ndims2)));

	/* get argument array details */
	lbs1 = ARR_LBOUND(v1);
	lbs2 = ARR_LBOUND(v2);
	dims1 = ARR_DIMS(v1);
	dims2 = ARR_DIMS(v2);
	dat1 = ARR_DATA_PTR(v1);
	dat2 = ARR_DATA_PTR(v2);
	bitmap1 = ARR_NULLBITMAP(v1);
	bitmap2 = ARR_NULLBITMAP(v2);
	nitems1 = ArrayGetNItems(ndims1, dims1);
	nitems2 = ArrayGetNItems(ndims2, dims2);
	ndatabytes1 = ARR_SIZE(v1) - ARR_DATA_OFFSET(v1);
	ndatabytes2 = ARR_SIZE(v2) - ARR_DATA_OFFSET(v2);

	if (ndims1 == ndims2)
	{
		/*
		 * resulting array is made up of the elements (possibly arrays
		 * themselves) of the input argument arrays
		 */
		ndims = ndims1;
		dims = (int *) palloc(ndims * sizeof(int));
		lbs = (int *) palloc(ndims * sizeof(int));

		dims[0] = dims1[0] + dims2[0];
		lbs[0] = lbs1[0];

		for (i = 1; i < ndims; i++)
		{
			if (dims1[i] != dims2[i] || lbs1[i] != lbs2[i])
				ereport(ERROR,
						(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
						 errmsg("cannot concatenate incompatible arrays"),
						 errdetail("Arrays with differing element dimensions are "
								   "not compatible for concatenation.")));

			dims[i] = dims1[i];
			lbs[i] = lbs1[i];
		}
	}
	else if (ndims1 == ndims2 - 1)
	{
		/*
		 * resulting array has the second argument as the outer array, with
		 * the first argument inserted at the front of the outer dimension
		 */
		ndims = ndims2;
		dims = (int *) palloc(ndims * sizeof(int));
		lbs = (int *) palloc(ndims * sizeof(int));
		memcpy(dims, dims2, ndims * sizeof(int));
		memcpy(lbs, lbs2, ndims * sizeof(int));

		/* increment number of elements in outer array */
		dims[0] += 1;

		/* make sure the added element matches our existing elements */
		for (i = 0; i < ndims1; i++)
		{
			if (dims1[i] != dims[i + 1] || lbs1[i] != lbs[i + 1])
				ereport(ERROR,
						(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
						 errmsg("cannot concatenate incompatible arrays"),
						 errdetail("Arrays with differing dimensions are not "
								   "compatible for concatenation.")));
		}
	}
	else
	{
		/*
		 * (ndims1 == ndims2 + 1)
		 *
		 * resulting array has the first argument as the outer array, with the
		 * second argument appended to the end of the outer dimension
		 */
		ndims = ndims1;
		dims = (int *) palloc(ndims * sizeof(int));
		lbs = (int *) palloc(ndims * sizeof(int));
		memcpy(dims, dims1, ndims * sizeof(int));
		memcpy(lbs, lbs1, ndims * sizeof(int));

		/* increment number of elements in outer array */
		dims[0] += 1;

		/* make sure the added element matches our existing elements */
		for (i = 0; i < ndims2; i++)
		{
			if (dims2[i] != dims[i + 1] || lbs2[i] != lbs[i + 1])
				ereport(ERROR,
						(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
						 errmsg("cannot concatenate incompatible arrays"),
						 errdetail("Arrays with differing dimensions are not "
								   "compatible for concatenation.")));
		}
	}

	/* Do this mainly for overflow checking */
	nitems = ArrayGetNItems(ndims, dims);
	ArrayCheckBounds(ndims, dims, lbs);

	/* build the result array */
	ndatabytes = ndatabytes1 + ndatabytes2;
	if (ARR_HASNULL(v1) || ARR_HASNULL(v2))
	{
		dataoffset = ARR_OVERHEAD_WITHNULLS(ndims, nitems);
		nbytes = ndatabytes + dataoffset;
	}
	else
	{
		dataoffset = 0;			/* marker for no null bitmap */
		nbytes = ndatabytes + ARR_OVERHEAD_NONULLS(ndims);
	}
	result = (ArrayType *) palloc0(nbytes);
	SET_VARSIZE(result, nbytes);
	result->ndim = ndims;
	result->dataoffset = dataoffset;
	result->elemtype = element_type;
	memcpy(ARR_DIMS(result), dims, ndims * sizeof(int));
	memcpy(ARR_LBOUND(result), lbs, ndims * sizeof(int));
	/* data area is arg1 then arg2 */
	memcpy(ARR_DATA_PTR(result), dat1, ndatabytes1);
	memcpy(ARR_DATA_PTR(result) + ndatabytes1, dat2, ndatabytes2);
	/* handle the null bitmap if needed */
	if (ARR_HASNULL(result))
	{
		array_bitmap_copy(ARR_NULLBITMAP(result), 0,
						  bitmap1, 0,
						  nitems1);
		array_bitmap_copy(ARR_NULLBITMAP(result), nitems1,
						  bitmap2, 0,
						  nitems2);
	}

	PG_RETURN_ARRAYTYPE_P(result);
}


/*
 * ARRAY_AGG(anynonarray) aggregate function
 */
Datum
array_agg_transfn(PG_FUNCTION_ARGS)
{
	Oid			arg1_typeid = get_fn_expr_argtype(fcinfo->flinfo, 1);
	MemoryContext aggcontext;
	ArrayBuildState *state;
	Datum		elem;

	if (arg1_typeid == InvalidOid)
		ereport(ERROR,
				(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
				 errmsg("could not determine input data type")));

	/*
	 * Note: we do not need a run-time check about whether arg1_typeid is a
	 * valid array element type, because the parser would have verified that
	 * while resolving the input/result types of this polymorphic aggregate.
	 */

	if (!AggCheckCallContext(fcinfo, &aggcontext))
	{
		/* cannot be called directly because of internal-type argument */
		elog(ERROR, "array_agg_transfn called in non-aggregate context");
	}

	if (PG_ARGISNULL(0))
		state = initArrayResult(arg1_typeid, aggcontext, false);
	else
		state = (ArrayBuildState *) PG_GETARG_POINTER(0);

	elem = PG_ARGISNULL(1) ? (Datum) 0 : PG_GETARG_DATUM(1);

	state = accumArrayResult(state,
							 elem,
							 PG_ARGISNULL(1),
							 arg1_typeid,
							 aggcontext);

	/*
	 * The transition type for array_agg() is declared to be "internal", which
	 * is a pass-by-value type the same size as a pointer.  So we can safely
	 * pass the ArrayBuildState pointer through nodeAgg.c's machinations.
	 */
	PG_RETURN_POINTER(state);
}

Datum
array_agg_combine(PG_FUNCTION_ARGS)
{
	ArrayBuildState *state1;
	ArrayBuildState *state2;
	MemoryContext agg_context;
	MemoryContext old_context;

	if (!AggCheckCallContext(fcinfo, &agg_context))
		elog(ERROR, "aggregate function called in non-aggregate context");

	state1 = PG_ARGISNULL(0) ? NULL : (ArrayBuildState *) PG_GETARG_POINTER(0);
	state2 = PG_ARGISNULL(1) ? NULL : (ArrayBuildState *) PG_GETARG_POINTER(1);

	if (state2 == NULL)
	{
		/*
		 * NULL state2 is easy, just return state1, which we know is already
		 * in the agg_context
		 */
		if (state1 == NULL)
			PG_RETURN_NULL();
		PG_RETURN_POINTER(state1);
	}

	if (state1 == NULL)
	{
		/* We must copy state2's data into the agg_context */
		state1 = initArrayResultWithSize(state2->element_type, agg_context,
										 false, state2->alen);

		old_context = MemoryContextSwitchTo(agg_context);

		for (int i = 0; i < state2->nelems; i++)
		{
			if (!state2->dnulls[i])
				state1->dvalues[i] = datumCopy(state2->dvalues[i],
											   state1->typbyval,
											   state1->typlen);
			else
				state1->dvalues[i] = (Datum) 0;
		}

		MemoryContextSwitchTo(old_context);

		memcpy(state1->dnulls, state2->dnulls, sizeof(bool) * state2->nelems);

		state1->nelems = state2->nelems;

		PG_RETURN_POINTER(state1);
	}
	else if (state2->nelems > 0)
	{
		/* We only need to combine the two states if state2 has any elements */
		int			reqsize = state1->nelems + state2->nelems;
		MemoryContext oldContext = MemoryContextSwitchTo(state1->mcontext);

		Assert(state1->element_type == state2->element_type);

		/* Enlarge state1 arrays if needed */
		if (state1->alen < reqsize)
		{
			/* Use a power of 2 size rather than allocating just reqsize */
			state1->alen = pg_nextpower2_32(reqsize);
			state1->dvalues = (Datum *) repalloc(state1->dvalues,
												 state1->alen * sizeof(Datum));
			state1->dnulls = (bool *) repalloc(state1->dnulls,
											   state1->alen * sizeof(bool));
		}

		/* Copy in the state2 elements to the end of the state1 arrays */
		for (int i = 0; i < state2->nelems; i++)
		{
			if (!state2->dnulls[i])
				state1->dvalues[i + state1->nelems] =
					datumCopy(state2->dvalues[i],
							  state1->typbyval,
							  state1->typlen);
			else
				state1->dvalues[i + state1->nelems] = (Datum) 0;
		}

		memcpy(&state1->dnulls[state1->nelems], state2->dnulls,
			   sizeof(bool) * state2->nelems);

		state1->nelems = reqsize;

		MemoryContextSwitchTo(oldContext);
	}

	PG_RETURN_POINTER(state1);
}

/*
 * array_agg_serialize
 *		Serialize ArrayBuildState into bytea.
 */
Datum
array_agg_serialize(PG_FUNCTION_ARGS)
{
	ArrayBuildState *state;
	StringInfoData buf;
	bytea	   *result;

	/* cannot be called directly because of internal-type argument */
	Assert(AggCheckCallContext(fcinfo, NULL));

	state = (ArrayBuildState *) PG_GETARG_POINTER(0);

	pq_begintypsend(&buf);

	/*
	 * element_type. Putting this first is more convenient in deserialization
	 */
	pq_sendint32(&buf, state->element_type);

	/*
	 * nelems -- send first so we know how large to make the dvalues and
	 * dnulls array during deserialization.
	 */
	pq_sendint64(&buf, state->nelems);

	/* alen can be decided during deserialization */

	/* typlen */
	pq_sendint16(&buf, state->typlen);

	/* typbyval */
	pq_sendbyte(&buf, state->typbyval);

	/* typalign */
	pq_sendbyte(&buf, state->typalign);

	/* dnulls */
	pq_sendbytes(&buf, state->dnulls, sizeof(bool) * state->nelems);

	/*
	 * dvalues.  By agreement with array_agg_deserialize, when the element
	 * type is byval, we just transmit the Datum array as-is, including any
	 * null elements.  For by-ref types, we must invoke the element type's
	 * send function, and we skip null elements (which is why the nulls flags
	 * must be sent first).
	 */
	if (state->typbyval)
		pq_sendbytes(&buf, state->dvalues, sizeof(Datum) * state->nelems);
	else
	{
		SerialIOData *iodata;
		int			i;

		/* Avoid repeat catalog lookups for typsend function */
		iodata = (SerialIOData *) fcinfo->flinfo->fn_extra;
		if (iodata == NULL)
		{
			Oid			typsend;
			bool		typisvarlena;

			iodata = (SerialIOData *)
				MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
								   sizeof(SerialIOData));
			getTypeBinaryOutputInfo(state->element_type, &typsend,
									&typisvarlena);
			fmgr_info_cxt(typsend, &iodata->typsend,
						  fcinfo->flinfo->fn_mcxt);
			fcinfo->flinfo->fn_extra = iodata;
		}

		for (i = 0; i < state->nelems; i++)
		{
			bytea	   *outputbytes;

			if (state->dnulls[i])
				continue;
			outputbytes = SendFunctionCall(&iodata->typsend,
										   state->dvalues[i]);
			pq_sendint32(&buf, VARSIZE(outputbytes) - VARHDRSZ);
			pq_sendbytes(&buf, VARDATA(outputbytes),
						 VARSIZE(outputbytes) - VARHDRSZ);
		}
	}

	result = pq_endtypsend(&buf);

	PG_RETURN_BYTEA_P(result);
}

Datum
array_agg_deserialize(PG_FUNCTION_ARGS)
{
	bytea	   *sstate;
	ArrayBuildState *result;
	StringInfoData buf;
	Oid			element_type;
	int64		nelems;
	const char *temp;

	if (!AggCheckCallContext(fcinfo, NULL))
		elog(ERROR, "aggregate function called in non-aggregate context");

	sstate = PG_GETARG_BYTEA_PP(0);

	/*
	 * Initialize a StringInfo so that we can "receive" it using the standard
	 * recv-function infrastructure.
	 */
	initReadOnlyStringInfo(&buf, VARDATA_ANY(sstate),
						   VARSIZE_ANY_EXHDR(sstate));

	/* element_type */
	element_type = pq_getmsgint(&buf, 4);

	/* nelems */
	nelems = pq_getmsgint64(&buf);

	/* Create output ArrayBuildState with the needed number of elements */
	result = initArrayResultWithSize(element_type, CurrentMemoryContext,
									 false, nelems);
	result->nelems = nelems;

	/* typlen */
	result->typlen = pq_getmsgint(&buf, 2);

	/* typbyval */
	result->typbyval = pq_getmsgbyte(&buf);

	/* typalign */
	result->typalign = pq_getmsgbyte(&buf);

	/* dnulls */
	temp = pq_getmsgbytes(&buf, sizeof(bool) * nelems);
	memcpy(result->dnulls, temp, sizeof(bool) * nelems);

	/* dvalues --- see comment in array_agg_serialize */
	if (result->typbyval)
	{
		temp = pq_getmsgbytes(&buf, sizeof(Datum) * nelems);
		memcpy(result->dvalues, temp, sizeof(Datum) * nelems);
	}
	else
	{
		DeserialIOData *iodata;

		/* Avoid repeat catalog lookups for typreceive function */
		iodata = (DeserialIOData *) fcinfo->flinfo->fn_extra;
		if (iodata == NULL)
		{
			Oid			typreceive;

			iodata = (DeserialIOData *)
				MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
								   sizeof(DeserialIOData));
			getTypeBinaryInputInfo(element_type, &typreceive,
								   &iodata->typioparam);
			fmgr_info_cxt(typreceive, &iodata->typreceive,
						  fcinfo->flinfo->fn_mcxt);
			fcinfo->flinfo->fn_extra = iodata;
		}

		for (int i = 0; i < nelems; i++)
		{
			int			itemlen;
			StringInfoData elem_buf;

			if (result->dnulls[i])
			{
				result->dvalues[i] = (Datum) 0;
				continue;
			}

			itemlen = pq_getmsgint(&buf, 4);
			if (itemlen < 0 || itemlen > (buf.len - buf.cursor))
				ereport(ERROR,
						(errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
						 errmsg("insufficient data left in message")));

			/*
			 * Rather than copying data around, we just initialize a
			 * StringInfo pointing to the correct portion of the message
			 * buffer.
			 */
			initReadOnlyStringInfo(&elem_buf, &buf.data[buf.cursor], itemlen);

			buf.cursor += itemlen;

			/* Now call the element's receiveproc */
			result->dvalues[i] = ReceiveFunctionCall(&iodata->typreceive,
													 &elem_buf,
													 iodata->typioparam,
													 -1);
		}
	}

	pq_getmsgend(&buf);

	PG_RETURN_POINTER(result);
}

Datum
array_agg_finalfn(PG_FUNCTION_ARGS)
{
	Datum		result;
	ArrayBuildState *state;
	int			dims[1];
	int			lbs[1];

	/* cannot be called directly because of internal-type argument */
	Assert(AggCheckCallContext(fcinfo, NULL));

	state = PG_ARGISNULL(0) ? NULL : (ArrayBuildState *) PG_GETARG_POINTER(0);

	if (state == NULL)
		PG_RETURN_NULL();		/* returns null iff no input values */

	dims[0] = state->nelems;
	lbs[0] = 1;

	/*
	 * Make the result.  We cannot release the ArrayBuildState because
	 * sometimes aggregate final functions are re-executed.  Rather, it is
	 * nodeAgg.c's responsibility to reset the aggcontext when it's safe to do
	 * so.
	 */
	result = makeMdArrayResult(state, 1, dims, lbs,
							   CurrentMemoryContext,
							   false);

	PG_RETURN_DATUM(result);
}

/*
 * ARRAY_AGG(anyarray) aggregate function
 */
Datum
array_agg_array_transfn(PG_FUNCTION_ARGS)
{
	Oid			arg1_typeid = get_fn_expr_argtype(fcinfo->flinfo, 1);
	MemoryContext aggcontext;
	ArrayBuildStateArr *state;

	if (arg1_typeid == InvalidOid)
		ereport(ERROR,
				(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
				 errmsg("could not determine input data type")));

	/*
	 * Note: we do not need a run-time check about whether arg1_typeid is a
	 * valid array type, because the parser would have verified that while
	 * resolving the input/result types of this polymorphic aggregate.
	 */

	if (!AggCheckCallContext(fcinfo, &aggcontext))
	{
		/* cannot be called directly because of internal-type argument */
		elog(ERROR, "array_agg_array_transfn called in non-aggregate context");
	}


	if (PG_ARGISNULL(0))
		state = initArrayResultArr(arg1_typeid, InvalidOid, aggcontext, false);
	else
		state = (ArrayBuildStateArr *) PG_GETARG_POINTER(0);

	state = accumArrayResultArr(state,
								PG_GETARG_DATUM(1),
								PG_ARGISNULL(1),
								arg1_typeid,
								aggcontext);

	/*
	 * The transition type for array_agg() is declared to be "internal", which
	 * is a pass-by-value type the same size as a pointer.  So we can safely
	 * pass the ArrayBuildStateArr pointer through nodeAgg.c's machinations.
	 */
	PG_RETURN_POINTER(state);
}

Datum
array_agg_array_combine(PG_FUNCTION_ARGS)
{
	ArrayBuildStateArr *state1;
	ArrayBuildStateArr *state2;
	MemoryContext agg_context;
	MemoryContext old_context;

	if (!AggCheckCallContext(fcinfo, &agg_context))
		elog(ERROR, "aggregate function called in non-aggregate context");

	state1 = PG_ARGISNULL(0) ? NULL : (ArrayBuildStateArr *) PG_GETARG_POINTER(0);
	state2 = PG_ARGISNULL(1) ? NULL : (ArrayBuildStateArr *) PG_GETARG_POINTER(1);

	if (state2 == NULL)
	{
		/*
		 * NULL state2 is easy, just return state1, which we know is already
		 * in the agg_context
		 */
		if (state1 == NULL)
			PG_RETURN_NULL();
		PG_RETURN_POINTER(state1);
	}

	if (state1 == NULL)
	{
		/* We must copy state2's data into the agg_context */
		old_context = MemoryContextSwitchTo(agg_context);

		state1 = initArrayResultArr(state2->array_type, InvalidOid,
									agg_context, false);

		state1->abytes = state2->abytes;
		state1->data = (char *) palloc(state1->abytes);

		if (state2->nullbitmap)
		{
			int			size = (state2->aitems + 7) / 8;

			state1->nullbitmap = (bits8 *) palloc(size);
			memcpy(state1->nullbitmap, state2->nullbitmap, size);
		}

		memcpy(state1->data, state2->data, state2->nbytes);
		state1->nbytes = state2->nbytes;
		state1->aitems = state2->aitems;
		state1->nitems = state2->nitems;
		state1->ndims = state2->ndims;
		memcpy(state1->dims, state2->dims, sizeof(state2->dims));
		memcpy(state1->lbs, state2->lbs, sizeof(state2->lbs));
		state1->array_type = state2->array_type;
		state1->element_type = state2->element_type;

		MemoryContextSwitchTo(old_context);

		PG_RETURN_POINTER(state1);
	}

	/* We only need to combine the two states if state2 has any items */
	else if (state2->nitems > 0)
	{
		MemoryContext oldContext;
		int			reqsize = state1->nbytes + state2->nbytes;
		int			i;

		/*
		 * Check the states are compatible with each other.  Ensure we use the
		 * same error messages that are listed in accumArrayResultArr so that
		 * the same error is shown as would have been if we'd not used the
		 * combine function for the aggregation.
		 */
		if (state1->ndims != state2->ndims)
			ereport(ERROR,
					(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
					 errmsg("cannot accumulate arrays of different dimensionality")));

		/* Check dimensions match ignoring the first dimension. */
		for (i = 1; i < state1->ndims; i++)
		{
			if (state1->dims[i] != state2->dims[i] || state1->lbs[i] != state2->lbs[i])
				ereport(ERROR,
						(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
						 errmsg("cannot accumulate arrays of different dimensionality")));
		}


		oldContext = MemoryContextSwitchTo(state1->mcontext);

		/*
		 * If there's not enough space in state1 then we'll need to reallocate
		 * more.
		 */
		if (state1->abytes < reqsize)
		{
			/* use a power of 2 size rather than allocating just reqsize */
			state1->abytes = pg_nextpower2_32(reqsize);
			state1->data = (char *) repalloc(state1->data, state1->abytes);
		}

		if (state2->nullbitmap)
		{
			int			newnitems = state1->nitems + state2->nitems;

			if (state1->nullbitmap == NULL)
			{
				/*
				 * First input with nulls; we must retrospectively handle any
				 * previous inputs by marking all their items non-null.
				 */
				state1->aitems = pg_nextpower2_32(Max(256, newnitems + 1));
				state1->nullbitmap = (bits8 *) palloc((state1->aitems + 7) / 8);
				array_bitmap_copy(state1->nullbitmap, 0,
								  NULL, 0,
								  state1->nitems);
			}
			else if (newnitems > state1->aitems)
			{
				int			newaitems = state1->aitems + state2->aitems;

				state1->aitems = pg_nextpower2_32(newaitems);
				state1->nullbitmap = (bits8 *)
					repalloc(state1->nullbitmap, (state1->aitems + 7) / 8);
			}
			array_bitmap_copy(state1->nullbitmap, state1->nitems,
							  state2->nullbitmap, 0,
							  state2->nitems);
		}

		memcpy(state1->data + state1->nbytes, state2->data, state2->nbytes);
		state1->nbytes += state2->nbytes;
		state1->nitems += state2->nitems;

		state1->dims[0] += state2->dims[0];
		/* remaining dims already match, per test above */

		Assert(state1->array_type == state2->array_type);
		Assert(state1->element_type == state2->element_type);

		MemoryContextSwitchTo(oldContext);
	}

	PG_RETURN_POINTER(state1);
}

/*
 * array_agg_array_serialize
 *		Serialize ArrayBuildStateArr into bytea.
 */
Datum
array_agg_array_serialize(PG_FUNCTION_ARGS)
{
	ArrayBuildStateArr *state;
	StringInfoData buf;
	bytea	   *result;

	/* cannot be called directly because of internal-type argument */
	Assert(AggCheckCallContext(fcinfo, NULL));

	state = (ArrayBuildStateArr *) PG_GETARG_POINTER(0);

	pq_begintypsend(&buf);

	/*
	 * element_type. Putting this first is more convenient in deserialization
	 * so that we can init the new state sooner.
	 */
	pq_sendint32(&buf, state->element_type);

	/* array_type */
	pq_sendint32(&buf, state->array_type);

	/* nbytes */
	pq_sendint32(&buf, state->nbytes);

	/* data */
	pq_sendbytes(&buf, state->data, state->nbytes);

	/* abytes */
	pq_sendint32(&buf, state->abytes);

	/* aitems */
	pq_sendint32(&buf, state->aitems);

	/* nullbitmap */
	if (state->nullbitmap)
	{
		Assert(state->aitems > 0);
		pq_sendbytes(&buf, state->nullbitmap, (state->aitems + 7) / 8);
	}

	/* nitems */
	pq_sendint32(&buf, state->nitems);

	/* ndims */
	pq_sendint32(&buf, state->ndims);

	/* dims: XXX should we just send ndims elements? */
	pq_sendbytes(&buf, state->dims, sizeof(state->dims));

	/* lbs */
	pq_sendbytes(&buf, state->lbs, sizeof(state->lbs));

	result = pq_endtypsend(&buf);

	PG_RETURN_BYTEA_P(result);
}

Datum
array_agg_array_deserialize(PG_FUNCTION_ARGS)
{
	bytea	   *sstate;
	ArrayBuildStateArr *result;
	StringInfoData buf;
	Oid			element_type;
	Oid			array_type;
	int			nbytes;
	const char *temp;

	/* cannot be called directly because of internal-type argument */
	Assert(AggCheckCallContext(fcinfo, NULL));

	sstate = PG_GETARG_BYTEA_PP(0);

	/*
	 * Initialize a StringInfo so that we can "receive" it using the standard
	 * recv-function infrastructure.
	 */
	initReadOnlyStringInfo(&buf, VARDATA_ANY(sstate),
						   VARSIZE_ANY_EXHDR(sstate));

	/* element_type */
	element_type = pq_getmsgint(&buf, 4);

	/* array_type */
	array_type = pq_getmsgint(&buf, 4);

	/* nbytes */
	nbytes = pq_getmsgint(&buf, 4);

	result = initArrayResultArr(array_type, element_type,
								CurrentMemoryContext, false);

	result->abytes = 1024;
	while (result->abytes < nbytes)
		result->abytes *= 2;

	result->data = (char *) palloc(result->abytes);

	/* data */
	temp = pq_getmsgbytes(&buf, nbytes);
	memcpy(result->data, temp, nbytes);
	result->nbytes = nbytes;

	/* abytes */
	result->abytes = pq_getmsgint(&buf, 4);

	/* aitems: might be 0 */
	result->aitems = pq_getmsgint(&buf, 4);

	/* nullbitmap */
	if (result->aitems > 0)
	{
		int			size = (result->aitems + 7) / 8;

		result->nullbitmap = (bits8 *) palloc(size);
		temp = pq_getmsgbytes(&buf, size);
		memcpy(result->nullbitmap, temp, size);
	}
	else
		result->nullbitmap = NULL;

	/* nitems */
	result->nitems = pq_getmsgint(&buf, 4);

	/* ndims */
	result->ndims = pq_getmsgint(&buf, 4);

	/* dims */
	temp = pq_getmsgbytes(&buf, sizeof(result->dims));
	memcpy(result->dims, temp, sizeof(result->dims));

	/* lbs */
	temp = pq_getmsgbytes(&buf, sizeof(result->lbs));
	memcpy(result->lbs, temp, sizeof(result->lbs));

	pq_getmsgend(&buf);

	PG_RETURN_POINTER(result);
}

Datum
array_agg_array_finalfn(PG_FUNCTION_ARGS)
{
	Datum		result;
	ArrayBuildStateArr *state;

	/* cannot be called directly because of internal-type argument */
	Assert(AggCheckCallContext(fcinfo, NULL));

	state = PG_ARGISNULL(0) ? NULL : (ArrayBuildStateArr *) PG_GETARG_POINTER(0);

	if (state == NULL)
		PG_RETURN_NULL();		/* returns null iff no input values */

	/*
	 * Make the result.  We cannot release the ArrayBuildStateArr because
	 * sometimes aggregate final functions are re-executed.  Rather, it is
	 * nodeAgg.c's responsibility to reset the aggcontext when it's safe to do
	 * so.
	 */
	result = makeArrayResultArr(state, CurrentMemoryContext, false);

	PG_RETURN_DATUM(result);
}

/*-----------------------------------------------------------------------------
 * array_position, array_position_start :
 *			return the offset of a value in an array.
 *
 * IS NOT DISTINCT FROM semantics are used for comparisons.  Return NULL when
 * the value is not found.
 *-----------------------------------------------------------------------------
 */
Datum
array_position(PG_FUNCTION_ARGS)
{
	return array_position_common(fcinfo);
}

Datum
array_position_start(PG_FUNCTION_ARGS)
{
	return array_position_common(fcinfo);
}

/*
 * array_position_common
 *		Common code for array_position and array_position_start
 *
 * These are separate wrappers for the sake of opr_sanity regression test.
 * They are not strict so we have to test for null inputs explicitly.
 */
static Datum
array_position_common(FunctionCallInfo fcinfo)
{
	ArrayType  *array;
	Oid			collation = PG_GET_COLLATION();
	Oid			element_type;
	Datum		searched_element,
				value;
	bool		isnull;
	int			position,
				position_min;
	bool		found = false;
	TypeCacheEntry *typentry;
	ArrayMetaState *my_extra;
	bool		null_search;
	ArrayIterator array_iterator;

	if (PG_ARGISNULL(0))
		PG_RETURN_NULL();

	array = PG_GETARG_ARRAYTYPE_P(0);

	/*
	 * We refuse to search for elements in multi-dimensional arrays, since we
	 * have no good way to report the element's location in the array.
	 */
	if (ARR_NDIM(array) > 1)
		ereport(ERROR,
				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
				 errmsg("searching for elements in multidimensional arrays is not supported")));

	/* Searching in an empty array is well-defined, though: it always fails */
	if (ARR_NDIM(array) < 1)
		PG_RETURN_NULL();

	if (PG_ARGISNULL(1))
	{
		/* fast return when the array doesn't have nulls */
		if (!array_contains_nulls(array))
			PG_RETURN_NULL();
		searched_element = (Datum) 0;
		null_search = true;
	}
	else
	{
		searched_element = PG_GETARG_DATUM(1);
		null_search = false;
	}

	element_type = ARR_ELEMTYPE(array);
	position = (ARR_LBOUND(array))[0] - 1;

	/* figure out where to start */
	if (PG_NARGS() == 3)
	{
		if (PG_ARGISNULL(2))
			ereport(ERROR,
					(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
					 errmsg("initial position must not be null")));

		position_min = PG_GETARG_INT32(2);
	}
	else
		position_min = (ARR_LBOUND(array))[0];

	/*
	 * We arrange to look up type info for array_create_iterator only once per
	 * series of calls, assuming the element type doesn't change underneath
	 * us.
	 */
	my_extra = (ArrayMetaState *) fcinfo->flinfo->fn_extra;
	if (my_extra == NULL)
	{
		fcinfo->flinfo->fn_extra = MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
													  sizeof(ArrayMetaState));
		my_extra = (ArrayMetaState *) fcinfo->flinfo->fn_extra;
		my_extra->element_type = ~element_type;
	}

	if (my_extra->element_type != element_type)
	{
		get_typlenbyvalalign(element_type,
							 &my_extra->typlen,
							 &my_extra->typbyval,
							 &my_extra->typalign);

		typentry = lookup_type_cache(element_type, TYPECACHE_EQ_OPR_FINFO);

		if (!OidIsValid(typentry->eq_opr_finfo.fn_oid))
			ereport(ERROR,
					(errcode(ERRCODE_UNDEFINED_FUNCTION),
					 errmsg("could not identify an equality operator for type %s",
							format_type_be(element_type))));

		my_extra->element_type = element_type;
		fmgr_info_cxt(typentry->eq_opr_finfo.fn_oid, &my_extra->proc,
					  fcinfo->flinfo->fn_mcxt);
	}

	/* Examine each array element until we find a match. */
	array_iterator = array_create_iterator(array, 0, my_extra);
	while (array_iterate(array_iterator, &value, &isnull))
	{
		position++;

		/* skip initial elements if caller requested so */
		if (position < position_min)
			continue;

		/*
		 * Can't look at the array element's value if it's null; but if we
		 * search for null, we have a hit and are done.
		 */
		if (isnull || null_search)
		{
			if (isnull && null_search)
			{
				found = true;
				break;
			}
			else
				continue;
		}

		/* not nulls, so run the operator */
		if (DatumGetBool(FunctionCall2Coll(&my_extra->proc, collation,
										   searched_element, value)))
		{
			found = true;
			break;
		}
	}

	array_free_iterator(array_iterator);

	/* Avoid leaking memory when handed toasted input */
	PG_FREE_IF_COPY(array, 0);

	if (!found)
		PG_RETURN_NULL();

	PG_RETURN_INT32(position);
}

/*-----------------------------------------------------------------------------
 * array_positions :
 *			return an array of positions of a value in an array.
 *
 * IS NOT DISTINCT FROM semantics are used for comparisons.  Returns NULL when
 * the input array is NULL.  When the value is not found in the array, returns
 * an empty array.
 *
 * This is not strict so we have to test for null inputs explicitly.
 *-----------------------------------------------------------------------------
 */
Datum
array_positions(PG_FUNCTION_ARGS)
{
	ArrayType  *array;
	Oid			collation = PG_GET_COLLATION();
	Oid			element_type;
	Datum		searched_element,
				value;
	bool		isnull;
	int			position;
	TypeCacheEntry *typentry;
	ArrayMetaState *my_extra;
	bool		null_search;
	ArrayIterator array_iterator;
	ArrayBuildState *astate = NULL;

	if (PG_ARGISNULL(0))
		PG_RETURN_NULL();

	array = PG_GETARG_ARRAYTYPE_P(0);

	/*
	 * We refuse to search for elements in multi-dimensional arrays, since we
	 * have no good way to report the element's location in the array.
	 */
	if (ARR_NDIM(array) > 1)
		ereport(ERROR,
				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
				 errmsg("searching for elements in multidimensional arrays is not supported")));

	astate = initArrayResult(INT4OID, CurrentMemoryContext, false);

	/* Searching in an empty array is well-defined, though: it always fails */
	if (ARR_NDIM(array) < 1)
		PG_RETURN_DATUM(makeArrayResult(astate, CurrentMemoryContext));

	if (PG_ARGISNULL(1))
	{
		/* fast return when the array doesn't have nulls */
		if (!array_contains_nulls(array))
			PG_RETURN_DATUM(makeArrayResult(astate, CurrentMemoryContext));
		searched_element = (Datum) 0;
		null_search = true;
	}
	else
	{
		searched_element = PG_GETARG_DATUM(1);
		null_search = false;
	}

	element_type = ARR_ELEMTYPE(array);
	position = (ARR_LBOUND(array))[0] - 1;

	/*
	 * We arrange to look up type info for array_create_iterator only once per
	 * series of calls, assuming the element type doesn't change underneath
	 * us.
	 */
	my_extra = (ArrayMetaState *) fcinfo->flinfo->fn_extra;
	if (my_extra == NULL)
	{
		fcinfo->flinfo->fn_extra = MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
													  sizeof(ArrayMetaState));
		my_extra = (ArrayMetaState *) fcinfo->flinfo->fn_extra;
		my_extra->element_type = ~element_type;
	}

	if (my_extra->element_type != element_type)
	{
		get_typlenbyvalalign(element_type,
							 &my_extra->typlen,
							 &my_extra->typbyval,
							 &my_extra->typalign);

		typentry = lookup_type_cache(element_type, TYPECACHE_EQ_OPR_FINFO);

		if (!OidIsValid(typentry->eq_opr_finfo.fn_oid))
			ereport(ERROR,
					(errcode(ERRCODE_UNDEFINED_FUNCTION),
					 errmsg("could not identify an equality operator for type %s",
							format_type_be(element_type))));

		my_extra->element_type = element_type;
		fmgr_info_cxt(typentry->eq_opr_finfo.fn_oid, &my_extra->proc,
					  fcinfo->flinfo->fn_mcxt);
	}

	/*
	 * Accumulate each array position iff the element matches the given
	 * element.
	 */
	array_iterator = array_create_iterator(array, 0, my_extra);
	while (array_iterate(array_iterator, &value, &isnull))
	{
		position += 1;

		/*
		 * Can't look at the array element's value if it's null; but if we
		 * search for null, we have a hit.
		 */
		if (isnull || null_search)
		{
			if (isnull && null_search)
				astate =
					accumArrayResult(astate, Int32GetDatum(position), false,
									 INT4OID, CurrentMemoryContext);

			continue;
		}

		/* not nulls, so run the operator */
		if (DatumGetBool(FunctionCall2Coll(&my_extra->proc, collation,
										   searched_element, value)))
			astate =
				accumArrayResult(astate, Int32GetDatum(position), false,
								 INT4OID, CurrentMemoryContext);
	}

	array_free_iterator(array_iterator);

	/* Avoid leaking memory when handed toasted input */
	PG_FREE_IF_COPY(array, 0);

	PG_RETURN_DATUM(makeArrayResult(astate, CurrentMemoryContext));
}

/*
 * array_shuffle_n
 *		Return a copy of array with n randomly chosen items.
 *
 * The number of items must not exceed the size of the first dimension of the
 * array.  We preserve the first dimension's lower bound if keep_lb,
 * else it's set to 1.  Lower-order dimensions are preserved in any case.
 *
 * NOTE: it would be cleaner to look up the elmlen/elmbval/elmalign info
 * from the system catalogs, given only the elmtyp. However, the caller is
 * in a better position to cache this info across multiple calls.
 */
static ArrayType *
array_shuffle_n(ArrayType *array, int n, bool keep_lb,
				Oid elmtyp, TypeCacheEntry *typentry)
{
	ArrayType  *result;
	int			ndim,
			   *dims,
			   *lbs,
				nelm,
				nitem,
				rdims[MAXDIM],
				rlbs[MAXDIM];
	int16		elmlen;
	bool		elmbyval;
	char		elmalign;
	Datum	   *elms,
			   *ielms;
	bool	   *nuls,
			   *inuls;

	ndim = ARR_NDIM(array);
	dims = ARR_DIMS(array);
	lbs = ARR_LBOUND(array);

	elmlen = typentry->typlen;
	elmbyval = typentry->typbyval;
	elmalign = typentry->typalign;

	/* If the target array is empty, exit fast */
	if (ndim < 1 || dims[0] < 1 || n < 1)
		return construct_empty_array(elmtyp);

	deconstruct_array(array, elmtyp, elmlen, elmbyval, elmalign,
					  &elms, &nuls, &nelm);

	nitem = dims[0];			/* total number of items */
	nelm /= nitem;				/* number of elements per item */

	Assert(n <= nitem);			/* else it's caller error */

	/*
	 * Shuffle array using Fisher-Yates algorithm.  Scan the array and swap
	 * current item (nelm datums starting at ielms) with a randomly chosen
	 * later item (nelm datums starting at jelms) in each iteration.  We can
	 * stop once we've done n iterations; then first n items are the result.
	 */
	ielms = elms;
	inuls = nuls;
	for (int i = 0; i < n; i++)
	{
		int			j = (int) pg_prng_uint64_range(&pg_global_prng_state, i, nitem - 1) * nelm;
		Datum	   *jelms = elms + j;
		bool	   *jnuls = nuls + j;

		/* Swap i'th and j'th items; advance ielms/inuls to next item */
		for (int k = 0; k < nelm; k++)
		{
			Datum		elm = *ielms;
			bool		nul = *inuls;

			*ielms++ = *jelms;
			*inuls++ = *jnuls;
			*jelms++ = elm;
			*jnuls++ = nul;
		}
	}

	/* Set up dimensions of the result */
	memcpy(rdims, dims, ndim * sizeof(int));
	memcpy(rlbs, lbs, ndim * sizeof(int));
	rdims[0] = n;
	if (!keep_lb)
		rlbs[0] = 1;

	result = construct_md_array(elms, nuls, ndim, rdims, rlbs,
								elmtyp, elmlen, elmbyval, elmalign);

	pfree(elms);
	pfree(nuls);

	return result;
}

/*
 * array_shuffle
 *
 * Returns an array with the same dimensions as the input array, with its
 * first-dimension elements in random order.
 */
Datum
array_shuffle(PG_FUNCTION_ARGS)
{
	ArrayType  *array = PG_GETARG_ARRAYTYPE_P(0);
	ArrayType  *result;
	Oid			elmtyp;
	TypeCacheEntry *typentry;

	/*
	 * There is no point in shuffling empty arrays or arrays with less than
	 * two items.
	 */
	if (ARR_NDIM(array) < 1 || ARR_DIMS(array)[0] < 2)
		PG_RETURN_ARRAYTYPE_P(array);

	elmtyp = ARR_ELEMTYPE(array);
	typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
	if (typentry == NULL || typentry->type_id != elmtyp)
	{
		typentry = lookup_type_cache(elmtyp, 0);
		fcinfo->flinfo->fn_extra = typentry;
	}

	result = array_shuffle_n(array, ARR_DIMS(array)[0], true, elmtyp, typentry);

	PG_RETURN_ARRAYTYPE_P(result);
}

/*
 * array_sample
 *
 * Returns an array of n randomly chosen first-dimension elements
 * from the input array.
 */
Datum
array_sample(PG_FUNCTION_ARGS)
{
	ArrayType  *array = PG_GETARG_ARRAYTYPE_P(0);
	int			n = PG_GETARG_INT32(1);
	ArrayType  *result;
	Oid			elmtyp;
	TypeCacheEntry *typentry;
	int			nitem;

	nitem = (ARR_NDIM(array) < 1) ? 0 : ARR_DIMS(array)[0];

	if (n < 0 || n > nitem)
		ereport(ERROR,
				(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
				 errmsg("sample size must be between 0 and %d", nitem)));

	elmtyp = ARR_ELEMTYPE(array);
	typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
	if (typentry == NULL || typentry->type_id != elmtyp)
	{
		typentry = lookup_type_cache(elmtyp, 0);
		fcinfo->flinfo->fn_extra = typentry;
	}

	result = array_shuffle_n(array, n, false, elmtyp, typentry);

	PG_RETURN_ARRAYTYPE_P(result);
}


/*
 * array_reverse_n
 *		Return a copy of array with reversed items.
 *
 * NOTE: it would be cleaner to look up the elmlen/elmbval/elmalign info
 * from the system catalogs, given only the elmtyp. However, the caller is
 * in a better position to cache this info across multiple calls.
 */
static ArrayType *
array_reverse_n(ArrayType *array, Oid elmtyp, TypeCacheEntry *typentry)
{
	ArrayType  *result;
	int			ndim,
			   *dims,
			   *lbs,
				nelm,
				nitem,
				rdims[MAXDIM],
				rlbs[MAXDIM];
	int16		elmlen;
	bool		elmbyval;
	char		elmalign;
	Datum	   *elms,
			   *ielms;
	bool	   *nuls,
			   *inuls;

	ndim = ARR_NDIM(array);
	dims = ARR_DIMS(array);
	lbs = ARR_LBOUND(array);

	elmlen = typentry->typlen;
	elmbyval = typentry->typbyval;
	elmalign = typentry->typalign;

	deconstruct_array(array, elmtyp, elmlen, elmbyval, elmalign,
					  &elms, &nuls, &nelm);

	nitem = dims[0];			/* total number of items */
	nelm /= nitem;				/* number of elements per item */

	/* Reverse the array */
	ielms = elms;
	inuls = nuls;
	for (int i = 0; i < nitem / 2; i++)
	{
		int			j = (nitem - i - 1) * nelm;
		Datum	   *jelms = elms + j;
		bool	   *jnuls = nuls + j;

		/* Swap i'th and j'th items; advance ielms/inuls to next item */
		for (int k = 0; k < nelm; k++)
		{
			Datum		elm = *ielms;
			bool		nul = *inuls;

			*ielms++ = *jelms;
			*inuls++ = *jnuls;
			*jelms++ = elm;
			*jnuls++ = nul;
		}
	}

	/* Set up dimensions of the result */
	memcpy(rdims, dims, ndim * sizeof(int));
	memcpy(rlbs, lbs, ndim * sizeof(int));
	rdims[0] = nitem;

	result = construct_md_array(elms, nuls, ndim, rdims, rlbs,
								elmtyp, elmlen, elmbyval, elmalign);

	pfree(elms);
	pfree(nuls);

	return result;
}

/*
 * array_reverse
 *
 * Returns an array with the same dimensions as the input array, with its
 * first-dimension elements in reverse order.
 */
Datum
array_reverse(PG_FUNCTION_ARGS)
{
	ArrayType  *array = PG_GETARG_ARRAYTYPE_P(0);
	ArrayType  *result;
	Oid			elmtyp;
	TypeCacheEntry *typentry;

	/*
	 * There is no point in reversing empty arrays or arrays with less than
	 * two items.
	 */
	if (ARR_NDIM(array) < 1 || ARR_DIMS(array)[0] < 2)
		PG_RETURN_ARRAYTYPE_P(array);

	elmtyp = ARR_ELEMTYPE(array);
	typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
	if (typentry == NULL || typentry->type_id != elmtyp)
	{
		typentry = lookup_type_cache(elmtyp, 0);
		fcinfo->flinfo->fn_extra = (void *) typentry;
	}

	result = array_reverse_n(array, elmtyp, typentry);

	PG_RETURN_ARRAYTYPE_P(result);
}

/*
 * array_sort
 *
 * Sorts the first dimension of the array.
 */
static ArrayType *
array_sort_internal(ArrayType *array, bool descending, bool nulls_first,
					FunctionCallInfo fcinfo)
{
	ArrayType  *newarray;
	Oid			collation = PG_GET_COLLATION();
	int			ndim,
			   *dims,
			   *lbs;
	ArraySortCachedInfo *cache_info;
	Oid			elmtyp;
	Oid			sort_typ;
	Oid			sort_opr;
	Tuplesortstate *tuplesortstate;
	ArrayIterator array_iterator;
	Datum		value;
	bool		isnull;
	ArrayBuildStateAny *astate = NULL;

	ndim = ARR_NDIM(array);
	dims = ARR_DIMS(array);
	lbs = ARR_LBOUND(array);

	/* Quick exit if we don't need to sort */
	if (ndim < 1 || dims[0] < 2)
		return array;

	/* Set up cache area if we didn't already */
	cache_info = (ArraySortCachedInfo *) fcinfo->flinfo->fn_extra;
	if (cache_info == NULL)
	{
		cache_info = (ArraySortCachedInfo *)
			MemoryContextAllocZero(fcinfo->flinfo->fn_mcxt,
								   sizeof(ArraySortCachedInfo));
		fcinfo->flinfo->fn_extra = cache_info;
	}

	/* Fetch and cache required data if we don't have it */
	elmtyp = ARR_ELEMTYPE(array);
	if (elmtyp != cache_info->array_meta.element_type)
	{
		TypeCacheEntry *typentry;

		typentry = lookup_type_cache(elmtyp,
									 TYPECACHE_LT_OPR | TYPECACHE_GT_OPR);
		cache_info->array_meta.element_type = elmtyp;
		cache_info->array_meta.typlen = typentry->typlen;
		cache_info->array_meta.typbyval = typentry->typbyval;
		cache_info->array_meta.typalign = typentry->typalign;
		cache_info->elem_lt_opr = typentry->lt_opr;
		cache_info->elem_gt_opr = typentry->gt_opr;
		cache_info->array_type = typentry->typarray;
	}

	/* Identify the sort operator to use */
	if (ndim == 1)
	{
		/* Need to sort the element type */
		sort_typ = elmtyp;
		sort_opr = (descending ? cache_info->elem_gt_opr : cache_info->elem_lt_opr);
	}
	else
	{
		/* Otherwise we're sorting arrays */
		sort_typ = cache_info->array_type;
		if (!OidIsValid(sort_typ))
			ereport(ERROR,
					(errcode(ERRCODE_UNDEFINED_OBJECT),
					 errmsg("could not find array type for data type %s",
							format_type_be(elmtyp))));
		/* We know what operators to use for arrays */
		sort_opr = (descending ? ARRAY_GT_OP : ARRAY_LT_OP);
	}

	/*
	 * Fail if we don't know how to sort.  The error message is chosen to
	 * match what array_lt()/array_gt() will say in the multidimensional case.
	 */
	if (!OidIsValid(sort_opr))
		ereport(ERROR,
				errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
				errmsg("could not identify a comparison function for type %s",
					   format_type_be(elmtyp)));

	/* Put the things to be sorted (elements or sub-arrays) into a tuplesort */
	tuplesortstate = tuplesort_begin_datum(sort_typ,
										   sort_opr,
										   collation,
										   nulls_first,
										   work_mem,
										   NULL,
										   TUPLESORT_NONE);

	array_iterator = array_create_iterator(array, ndim - 1,
										   &cache_info->array_meta);
	while (array_iterate(array_iterator, &value, &isnull))
	{
		tuplesort_putdatum(tuplesortstate, value, isnull);
	}
	array_free_iterator(array_iterator);

	/* Do the sort */
	tuplesort_performsort(tuplesortstate);

	/* Extract results into a new array */
	while (tuplesort_getdatum(tuplesortstate, true, false, &value, &isnull, NULL))
	{
		astate = accumArrayResultAny(astate, value, isnull,
									 sort_typ, CurrentMemoryContext);
	}
	tuplesort_end(tuplesortstate);

	newarray = DatumGetArrayTypeP(makeArrayResultAny(astate,
													 CurrentMemoryContext,
													 true));

	/* Adjust lower bound to match the input */
	ARR_LBOUND(newarray)[0] = lbs[0];

	return newarray;
}

Datum
array_sort(PG_FUNCTION_ARGS)
{
	ArrayType  *array = PG_GETARG_ARRAYTYPE_P(0);

	PG_RETURN_ARRAYTYPE_P(array_sort_internal(array,
											  false,
											  false,
											  fcinfo));
}

Datum
array_sort_order(PG_FUNCTION_ARGS)
{
	ArrayType  *array = PG_GETARG_ARRAYTYPE_P(0);
	bool		descending = PG_GETARG_BOOL(1);

	PG_RETURN_ARRAYTYPE_P(array_sort_internal(array,
											  descending,
											  descending,
											  fcinfo));
}

Datum
array_sort_order_nulls_first(PG_FUNCTION_ARGS)
{
	ArrayType  *array = PG_GETARG_ARRAYTYPE_P(0);
	bool		descending = PG_GETARG_BOOL(1);
	bool		nulls_first = PG_GETARG_BOOL(2);

	PG_RETURN_ARRAYTYPE_P(array_sort_internal(array,
											  descending,
											  nulls_first,
											  fcinfo));
}